Image processing to monitor coffee usage.docx

Using image processing to monitor coffee usage Image processing techniques have been applied in many different fields such as identification in security systems, space exploration and automated machines in factories. This project applies image processing to monitor the level of a non-transparent fluid in a transparent container, in this case coffee in a glass coffee pot at a coffee machine. If the level of coffee is measured over a period of time valuable statistical information can be extracted. This information can be used to monitor the workload of the coffee machine and determine the current status of the coffee pot. It can even be used to predict when the next fresh pot of coffee will be made by examining the intervals between refills! Image processing is chosen above methods involving the weight of the container or other methods which require mechanical hardware. The system developed in this project takes the onus off the coffee machine manufacturers to implement monitoring systems in their machines. Also, image processing makes the system more adaptable as it overcomes many of the physical obstacles that more mechanical methods may experience. Three stages are involved in the use of the system namely setup, calibration and operation. The setup stage involves the physical installation of a computer and attached camera to monitor the coffee machine. The calibration stage requires a user to supply the system with a background image and an image of a full pot. Since these images change each time the camera or the coffee machine is moved recalibration may be necessary from time to time. After calibration the system enters the operation stage where it will continually capture images of the coffee pot and take measurements. These measurements and the time at which they were made are stored in a database. The data in the database can then be accessed and processed to determine any statistical information a user may require. 1.2 The work this project is based on Image and signal processing techniques are widely used in several communication and automation systems. Most of the techniques used during the development of this project are already standardised and well established in the industry. This project builds upon standardised techniques as far as possible to help ensure a high quality end result. Literature explaining these techniques is abundant and chosen for this project is Gonzales and Woods’ Digital Image Processing. This book was found to be most comprehensive and the reader is urged to acquire a copy if he/she is interested in the subject of image processing. 1.3 Project objectives A number of objectives were pursued in the course of this project and can be summarised as follows: Locate a coffee pot in an image containing other objects in the background. Measure the amount of coffee in a pot using a camera attached to a computer and applying image processing techniques. Create a system which can monitor coffee usage and calculate statistics. Create a web interface to control the measuring system and view its results. This thesis will examine the suitability, effectiveness and practicality of different methods of achieving these objectives. 1.4 Contributions made by this work The contributions made by this project are the following: A method for determining the level of fluid in a container from an image in the presence of background noise, changing light conditions and other practical problems. An example of the practical application of selected image processing techniques. A demonstration of how a web interface can be used effectively to control a remote system by means of CGI. 1.5 Thesis overview Chapter 2 explains the techniques used in this project. Some are standard image processing techniques and others techniques which have been developed during the course of this project. Chapter 3 demonstrates the application of the techniques detailed in Chapter 2 to the problem of measuring coffee levels with a camera. Chapter 4 gives an overview of the entire coffee usage monitoring system which combines the techniques discussed in chapter 3 with a web interface. The programming languages and software used throughout the system development are mentioned. Some practical complications that were encountered during implementation are also discussed. Chapter 5 discusses the main experiments and tests conducted during the project development. Chapter 6 draws some conclusions from this project and makes recommendations for future development. Chapter 2 Theoretical work and techniques Introduction This chapter explains all the techniques used in this project in order to clarify the ensuing discussions in chapter 3. The explanations will be accompanied by simple examples. The standardised techniques covered in this chapter are two-dimensional correlation as well as the subtraction, thresholding and edge detection of images. Some non-standard techniques were developed during this project and are discussed in this chapter as well. These are an algorithm for finding the largest area of contiguous pixels in a binary image and an algorithm for finding the point of maximum symmetry in an image. 2.2 Standardised techniques This section discusses the standardised techniques used in the project. 2.2.1 Subtraction of images An image can be represented as a matrix where each element represents the grey level of the corresponding pixel. Given this representation, image subtraction becomes a simple matrix operation. If two images are represented by As and At then this operation can be written as IMAGE1 – IMAGE2 = As – At. (2.1) This operation is discussed at greater length by Gonzales and Woods [1]. 2.2.2 Thresholding of images Image thresholding is the process of applying a hard limiter to the grey level of each pixel in an image. If matrix A represents an image then thresholding can be written as (2.2) where m is the grey level threshold. Figure 2.1(a) shows a test image with the grey levels indicated on the figure. Figure 2.1(b) shows the limiter function. Setting m = 150 and applying the limiter to the test image produces the binary image in figure 2.1(c). (a) (b) (c) Figure 2.1: The result of thresholding an image. (a) A test image with grey levels indicated by the numbers on the figure. (b) The thresholding function. (c) Thresholded image with white indicating 1 and black indicating 0. Image thresholding is discussed by Gonzales and Woods [2]. 2.2.3 Detection of edges in an image Edges in images are indicated by sharp jumps in grey levels. The sharper the jump in grey level is the clearer the edge will be. For example, if an image depicts a black pot in front of a white wall then the edges of the pot can easily be found, but if the pot had an off-white colour then the edges would be less clear. Figure 2.2(a) below is a test image with its edges shown in figures 2.2(b)-(d). Figure 2.2(b) (edges in horizontal direction) and figure 2.2(c) (edges in vertical direction) are the results of applying the filters in figures 2.2(e) and (f) respectively. Figure 2.2(d) is the sum of figure 2.2(b) and (c) and shows all the edges of the test image. (a) (b) (c) (d) (e) (f) Figure 2.2: Edge detection. (a) A test image. (b)The horizontal edges of the test image. (c) The vertical edges of the test image. (d) The sum of (b) and (c) shows all the edges of the test image. (e) The filter applied to the test image to obtain (b). (f) The filter applied to the test image to obtain (c). The filters in figure 2.2(e) and (f) are applied to each pixel in the test image. The way the filter in figure 2.2(e), for example, is applied to a point T(x,y) is clarified by the following equation: Eh(x,y) = - 1T(x-1,y-1) - 2T(x+0,y-1) - 1T(x+1,y-1) +0T(x-1,y+0) +0T(x+0,y+0) +0T(x+1,y+0) +1T(x-1,y+1) +2T(x+0,y+1) +1T(x+1,y+1) (2.3) where T is the test image in figure 2.2(a) and Eh is the horizontal edges image in figure 2.2(b). Edge detection is discussed in more detail by Gonzales and Woods [3]. 2.2.4 Two-dimensional correlation The convolution of two one-dimensional signals is intuitively described as a function giving the size of the areas that overlap as one signal is slid over a mirror image of the other. For one-dimensional signals convolution is defined as . (2.4) The values of the resulting function c(n) each correspond to one possible way of overlapping the two signals. Figure 2.3(a) shows a square signal to be convolved with a translated version of itself in figure 2.3(b). The result of this convolution is shown in figure 2.3(c). t f(t) * g(t) 0 100 0 100 200 t -50 0 50 t f(t) 1 0 50 150 0 1 g(t) t f(t) * g(t) 0 100 0 100 200 t -50 0 50 t f(t) 1 0 50 150 0 1 g(t) (a) (b) (c) Figure 2.3: One-dimensional convolution. (a) A square signal f(t). (b) A translated version of f(t). (c) The result of convolving f(t) with g(t). Note that the position of the peak value in figure 2.3(c) is the same as the centre position of the square in figure 2.3(b). This result shows that a known signal form can be found in a longer signal using convolution. The signals in the above example are symmetrical, but if they were not then one of them had to be mirrored before convolving to obtain the peak in figure 2.3(c). The reason is that the convolution operation mirrors one of the signals before starting. If one mirrors an asymmetrical signal then the result can never match the original signal by simply translating it. Thus the peak value in the example will never be found. If, however, the signal is mirrored and then mirrored again by the convolution operation the signals will match perfectly at some point as they are slid over one another. One may argue that the convolution can then be replaced by correlation (2.5) and the twofold mirroring can thus be avoided. After all, correlation is the same as convolution except for the mirroring step that convolution starts with. The reason convolution is used instead, however, is that unlike correlation the convolution of two signals can be computed efficiently on a computer using the Fast Fourier Transform (FFT). Both convolution and correlation require many multiplications on a computer and is therefore computationally expensive. However, convolution can be calculated in the Fourier domain using (2.6) which requires much less processing power. The proof of equation 2.6 is found in [5]. From this point onward correlation will be the subject of discussion, but bear in mind that it is implemented using convolution and the FFT. One-dimensional correlation is a well-known operation in engineering, but two-dimensional correlation is a bit less intuitive. Like the one-dimensional case two-dimensional correlation gives the area under the overlapping region of two functions. In this case, however, the correlation is a function of two variables each representing a dimension (or axis) of the functions being convolved. The following equation defines two-dimensional correlation: . (2.7) If an image is represented as a two-dimensional function of x and y coordinates then the position of a known image portion can be found in a larger image using two-dimensional correlation. This works exactly as it did with the one-dimensional case. Correlate the larger image with a centred version of the known image portion and look for the peak value in the resulting function. The position of the peak will reveal the translation of the image portion in the larger image. The matrices in figure 2.4 represent discrete two-dimensional functions or images. Figure 2.4(a) shows the known matrix portion centred at the origin of its axes. Figure 2.4(b) shows the larger image containing a translated version of the known matrix portion. Figure 2.4(c) shows the result of correlating the matrix in figure 2.4(a) with the matrix in figure 2.4(b). 1 2 3 7 4 2 9 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 0 0 0 7 4 2 0 0 0 9 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 8 23 30 27 0 0 0 16 44 104 70 39 0 0 0 35 88 184 88 35 0 0 0 39 70 104 44 16 0 0 0 27 30 23 8 2 0 0 0 0 0 0 0 0 0 0 (a) (b) (c) Figure 2.4: Two-dimensional correlation. (a) A known matrix portion. (b) A larger matrix containing a translated version of the matrix portion in (a). (c) The two-dimensional correlation of the matrices in (a) and (b). Note that the peak value of the matrix in figure 2.4(c) is at row 5 column 4. This position can be used to obtain the position of the known image portion in the matrix of figure 2.4(b). Suppose the peak value in the correlation result occurs at (xp,yp). The translation of the known matrix portion is then (2.8) where Wc and Hc are the width and height respectively of the known image portion. The fix function discards the fractional part of a decimal number in order to make it an integer, so that fix(2.5) = 2. The reader may investigate the application of two-dimensional correlation as applied to image processing by referring to [7]. 2.3 Techniques developed during this project The following techniques have been developed in the course of this project. Finding the largest area of contiguous pixels in a binary image The idea of the algorithm described in this section is to find the largest area of non-zero pixels in an image and discard the smaller areas. Pixels are part of the same area if they are 8-adjacent. 8-adjacency is illustrated in figure 2.5. The centre pixel and its 8-adjacent neighbours are surrounded by a dashed line. Figure 2.5: 8-adjacency. The centre pixel and its 8-adjacent neighbours are surrounded by a dashed line. In this project the areas in the image will often represent the positions of objects. To ensure that the area entirely encloses the object it is necessary to use 8-adjacency. This is because 8-adjacency causes the areas detected by the algorithm to be as large as possible without jumping over zero pixels. 4-adjacency may for example cut an object in two if two parts of the object are connected only by diagonally connected pixels. Refer to Gonzales and Woods [4] for further discussions of 8-adjacency and other connectivity concepts. The figure below depicts an image with two areas of non-zero pixels. Both areas are numbered and surrounded by unnumbered zero pixels. x-coordinate y-coordinate x-coordinate y-coordinate Figure 2.6: An image with two numbered areas. The first step is to mark all non-zero pixels as ‘unexamined’ meaning that the algorithm must at some time examine these pixels to determine which area they belong to. The algorithm uses three lists of pixel coordinates: A list of pixels belonging to the current largest area called LARGEST A list of pixels belonging to the area currently under investigation called CURRENT A list of unexamined pixels connected to the area currently under investigation called NEIGHBOURS The pseudo code below describes the operation of the algorithm: Mark all non-zero pixels as ‘unexamined’ Clear LARGEST. Repeat until no more unexamined non-zero pixels are left { Clear CURRENT and NEIGHBOURS. Find next ‘unexamined’ non-zero pixel at (xn,yn). Add (xn,yn) to CURRENT. Mark (xn,yn) as ‘examined’. Add all non-zero 8-adjacent neighbours of (xn,yn) to NEIGHBOURS. Repeat until NEIGHBOURS is empty { Remove first pixel from NEIGHBOURS ?(xi,yi) Add (xi,yi) to CURRENT Mark (xi,yi) as ‘examined’ Add all non-zero unexamined 8-adjacent neighbours of (xi,yi) to NEIGHBOURS. } If LARGEST is shorter than CURRENT then { Move all pixels from CURRENT to LARGEST } } 14859009906000 Algorithm 2.1: Pseudo code for finding the largest area in a binary image. Observe the status of the three lists as the algorithm progresses. Working through the algorithm with the example in figure 2.6 should reveal that LARGEST will contain the coordinates of the largest area in the image. The reason for using lists instead of writing a recursive algorithm is given in section 4.4.1. 2.3.2 Finding the point of maximum symmetry in a binary image It is well known what is meant by symmetry about a point on an axis of a signal or image. Figure 2.7(a) shows a symmetrical signal and figure 2.7(b) a symmetrical image, both symmetrical about x = 0. Figure 2.7(c) shows an asymmetrically distorted version of the image in figure 2.7(b). (a) (b) (c) Figure 2.7: Symmetrical signals and images. (a) A symmetrical signal. (b) A symmetrical image. (c) An asymmetrically distorted version of the image in (b). A perfectly symmetrical image requires everything to the left of the point of symmetry to be a perfect mirror image of everything to the right. In figure 2.7(c) it is clear that no point of perfect symmetry exists, however, a point of maximum symmetry does exist. The difference between the image portion to the left of the point of maximum symmetry and the mirror image of the portion to its right is at a minimum. The algorithm described in this section uses this minimum difference criterion to find the point of maximum symmetry. A brute force algorithm is fast enough for the purposes of this project. The pseudo code on the next page details the workings of this algorithm. IMAGE is a matrix representing a binary image. xn is a candidate for the point of maximum symmetry currently being examined and ymax and xmax are the ranges of the y-axis and x-axis respectively . Repeat for all xmin xi xmax { d = min[xi-xmin , xmax-xi] LEFT = IMAGE[(xi – d)…xi , 0…ymax] RIGHT = IMAGE[xi …(xi + d) , 0…ymax] LEFT_MIRRORLEFT = LEFT concatenated from the right by the mirror image of LEFT and superimposed on a black image of the same size as IMAGE MIRRORRIGHT_RIGHT = RIGHT concatenated from the left by the mirror image of RIGHT and superimposed on a black image of the same size as IMAGE diff_left_mirrorleft[i] = amount of non-zero pixels in (IMAGE – LEFT_MIRRORLEFT) diff_mirrorright_right[i] = amount of non-zero pixels in (IMAGE – MIRRORRIGHT_RIGHT) } max_symmetry_point = min[ min[ diff_left_mirrorleft ] , min[ diff_mirrorright_right] ] 14859009906000 Algorithm 2.2: Pseudo code for finding the point of maximum symmetry in a binary image. The images below illustrate the process in algorithm 2.2 above. Figure 2.8(a) is the image of which the point of maximum symmetry must be found. Figure 2.8(b) shows LEFT_MIRRORLEFT at a non-optimal point of symmetry. Figure 2.8(c) shows MIRRORRIGHT_RIGHT at the point of maximum symmetry. In both figure 2.8(b) and (c) the point of symmetry is indicated by a dashed line. (a) (b) (c) Figure 2.8: Finding the point of maximum symmetry. (a) The distorted symmetrical image in which to find the point of maximum symmetry. (b) The image mirrored about a non-optimal point of symmetry. (c) The image mirrored about the point of maximum symmetry. Note that figure 2.8(c) is the distorted symmetrical image in figure 2.8(a), but with the distortion removed. This algorithm is therefore a way to remove lopsided distortion from a symmetrical image (or signal). 2.4 Conclusion After reading this chapter the reader should have no trouble with the concepts used later in the thesis. The image processing techniques explained in this chapter are image subtraction, thresholding and edge detection. It was also shown how two-dimensional correlation can be used to determine the translation of a known signal or image portion. An algorithm for finding the largest area in a binary image was described using pseudo code. Another algorithm which finds the point of maximum symmetry was also described with pseudo code and shown to rid a symmetrical image of its asymmetrical distortions. Chapter 3 Practical applications – measuring coffee Introduction This chapter shows how a technique for measuring coffee from an image has been developed. The first complication was in automatically finding the coffee pot in the image (i.e. to separate it from the background). Correlation will be discussed as a method for finding the coffee pot since intuitively this seems like the most obvious solution. It will be shown, however, that using correlation is less effective than expected. Edge detection as a means for improving the effectiveness of correlation will then be discussed. Another approach which circumvents the need for locating the pot (and consequently correlation and edge detection as well) is also discussed. This method is the one chosen for the final system design. The above mentioned approaches have a common problem in dealing with shadows and small background changes. The shadow problems can be solved using an algorithm for detecting the point of maximum symmetry. It is also shown how small background changes are handled using an algorithm for finding the largest area in an image. 3.2 Using two-dimensional correlation to locate a coffee pot Before reading this section the reader is urged to read chapter 2 as it explains all the methods used in the following discussions. 3.2.1 Correlation and the problem of light backgrounds Given an image of a coffee pot shown in figure 3.1(a) correlation can be used to find its position in the larger image shown in figure 3.1(b). (a) (b) Figure 3.1: Correlation can be used to locate (a) the pot in (b) the larger image. By correlating the two images and then searching for the peak in the result one should be able to find the position of the coffee pot. The problem, however, is that if the background of the image is lighter than the coffee pot then the peak value in the result will be in the wrong position. Figure 3.2 illustrates the problem. Figure 3.2(a) is a matrix representing the coffee pot while figure 3.2(b) represents the larger image. Note that the high values in figure 3.2(b) represent the high grey level of the background. Figure 3.2(c) shows the result of the correlation. 1 2 3 4 7 5 8 9 1 20 20 20 20 20 20 20 20 20 1 2 3 20 20 20 4 7 5 20 20 20 8 9 1 20 20 20 20 20 20 20 20 20 20 20 20 20 200 360 360 360 360 340 160 120 440 680 661 491 349 263 104 180 540 800 689 420 253 190 72 180 540 800 651 412 250 152 31 180 540 800 692 590 493 400 169 180 540 800 764 743 709 571 241 160 340 440 440 440 440 280 100 60 100 120 120 120 120 60 20 (a) (b) (c) Figure 3.2: Two-dimensional correlation of an object with an image of itself on a light background. (a) A matrix representing the coffee pot. (b) A matrix representing the coffee pot with the high values indicating a light background. (c) The two-dimensional correlation of the matrices in (a) and (b). The peak value of 800 is encountered in several positions in figure 2.8(c), none of which indicate the position of the object in figure 2.8(b). This result reveals that using correlation to find an object in an image with a light background is problematic. One may argue that this problem can be circumvented by making light pixels dark and vice versa. This will work if the background is only lighter than the object. If the background is partly darker and partly lighter than the object then this solution will obviously not work. The problem described above can be solved using image thresholding. By thresholding the image before correlation the portions of the image which are lighter than the object can be forced to black. The threshold, of course, is the maximum grey level of the coffee pot itself. It was found by means of experimentation that the grey levels of the coffee pot lies within the lower twenty percent of the grey levels of the entire image. If the rest is forced to white all that should remain is a binary image with the non-zero portions indicating the positions of the dark areas in the original image. This is indicated in figure 3.3. (a) (b) Figure 3.3: After thresholding only areas of lower or equal grey levels than the coffee pot remains. (a) An image of the coffee pot and other darker objects on a light background. (b) The result of thresholding (a). Now there are no lighter areas in the image to confuse the correlation operation by generating peak values in the wrong positions. Another problem arises however and is discussed in the following section. 3.2.2 Correlation and the problem of big black objects It was shown in section 2.7 how a known object can be found in an image using correlation. In section 3.2.1 a problem with using correlation to find an object against a partially lighter and partially darker background was discussed. The solution to the problem was to remove all portions of the image which are lighter than the object using image thresholding. Thresholding leaves areas which are darker than the object and areas which have more or less the same grey level. The darker areas can be ignored since they will not generate peak values during correlation. On the other hand the areas with grey levels and size close to that of the object may generate peak values which are in the wrong positions. This is similar to the problem of light backgrounds discussed in the previous section. In this case, however, image thresholding cannot be used because the object has the same grey levels as the unwanted image portions. This problem is better understood if one imagines a photograph of a big black egg on a table next to a smaller or equally sized black coffee pot. Correlation will generate peak values indicating the position of the coffee pot as well as the position of the big black egg. The problem of distinguishing between different objects of the same grey level and size is not a trivial one. In fact, no method of doing this without extra information could be conceived. This need for extra information forces a calibration or setup stage upon the system and thus makes it less automated. The extra information needed may come in different forms. For example, one may require the user of the system to distinguish between the different objects. This can be done by drawing an outline around the coffee pot or by clicking as close to the centre of the coffee pot as possible. Another approach is to capture the background (i.e. the image without the coffee pot) during the calibration of the system. Most of the methods for gathering the required extra information will result in fairly simple solutions and simple user interfaces. The method to choose depends on the environment the system will be used in and its practical implications. The one mentioned last was chosen for this project because it entails the least complicated programming. If the background image can be captured and subtracted from the image containing the coffee pot then the non-zero pixels in the result should indicate the position of the pot. The figure on the next page depicts two possible scenarios depending on the background directly behind the coffee pot. The first shows what will happen when the background is partly darker and partly lighter and the second when it is partly lighter and partly the same grey level. The circles in the images represent objects in the background while the squares represent the background directly behind the coffee pot. Images in the first column show the coffee pot with different backgrounds. The second column shows the backgrounds without the coffee pot. The third column shows in white the non-zero pixels of the difference between the first two columns. First scenario (a) (b) (c) Second scenario (d) (e) (f) Figure 3.4: Subtracting the background to extract the position of the coffee pot. (a) Image of pot with partly darker and partly lighter background. (b) The background of (a) without the pot. (c) The non-zero pixels in the difference between (a) and (b). (d) Image of pot with partly darker and partly equal grey level background. (e) The background of (d) without the pot. (f) The non-zero pixels in the difference between (d) and (e). Note that in the first scenario the coffee pot has been extracted successfully, however, in the second scenario the bottom half has been cut off. The experiment illustrated in figure 3.4 shows that the coffee pot can be extracted successfully using subtraction of the background. This is true as long as the background directly behind the coffee pot does not contain pixels of the same grey level as the coffee pot itself. This result introduces a constraint on the system – the coffee pot may not stand in front of a background of the same grey level as coffee (i.e. a dark background). Another constraint is introduced when one considers what would happen when the background changes over time. If some object is placed near the coffee pot then this object will appear in the image in figure 3.4(a). The background image in figure 3.4(b) was captured during system calibration and therefore does not include this newly introduced object. The subtraction of these two images will yield the coffee pot as well as the newly introduced object. The algorithm for finding the largest area in an image may be used to remove objects which are smaller than the pot, but not larger. The constraint introduced here is therefore that no dark objects which are larger than the coffee pot may be introduced to the background. This may mean that the camera has to be placed close to the pot or zoomed so that the pot fills most of the image. It may also mean frequent re-calibration depending on the reasons for the changing background. 3.2.3 Using correlation to locate the coffee pot The next step in locating the pot is to centre the image in figure 3.4(c) about the origin of the x- and y-axes of the image. This can be done by cropping the coffee pot from the image. The result is shown in figure 3.5(b). (a) (b) Figure 3.5: Moving the coffee pot to the origin of its axis. (a) The image obtained through subtraction of the background. (b) The image in (a) cropped so that the middle of the image is equal to the middle of the pot. The images are now ready for the correlation process. The centring of the pot will ensure that the peak value in the correlation result will correspond to the centre of the image in figure 3.5(b) instead of the centre of the image in figure 3.5(a). Figure 3.6 illustrates how this correlation process works. The calibration stage requires a user to supply an image of a full pot of coffee shown in figure 3.6(a) and the background in figure 3.6(b). These are then subtracted from each other and the result is cropped to obtain the coffee pot in figure 3.6(c). During the operation stage of the system images like the one in figure 3.6(d) will be captured. Note that the coffee pot has been placed slightly more to the right than in figure 3.6(a). Subtracting the background in figure 3.6(e) yields the image in figure 3.6(f) which shows the extracted coffee pot in a different position than it was during calibration. The amount it is placed to the right from its original position is not known hence the need to locate it. The result of correlating figures 3.6(c) and (f) is shown in figure 3.6(g). The position of the peak value in this image can be used to determine the position of the pot in figure 3.6(f). Calibration stage (a) (b) (c) Operation stage (d) (e) (f) (g) Figure 3.6: The two stages of the system. (a) An image of the coffee pot and its background. (b) The background of the coffee pot. (c) The result of subtracting (b) from (a) and then cropping it. (d) An image of the coffee pot and its background with the pot placed slightly to the right. (e) The background obtained from the calibration step. (f) The result of subtracting (e) from (d). (g) The result of correlating (c) with (f). 3.2.4 Correlation and the problem of half full pots of coffee So far it was assumed that the coffee pot in the image captured during operation is filled to the same level as it was during calibration. This is obviously not true in most cases since people tend to consume most of the coffee in the pot. The result of subtracting the background from an image of a half full pot is shown in figure 3.7(b) below. (a) (b) (c) (d) Figure 3.7: The correlation between a full pot and a half full pot. (a) The centred image of a full pot obtained from the calibration stage. (b) The image of a half full pot obtained during the operation stage of the system. (c) The result of correlating (a) and (b). (d) The result of correlating (a) with an image of a full pot in the same position as the half full pot in (b). The problem is that an image of a full pot does not correlate very well with that of a half full pot, or rather, it correlates ‘too well’. The result of correlating figure 3.7(a) with figure 3.7(b) is shown in figure 3.7(c). Note the difference between figures 3.7(c) and (d). The peak value in figure 3.7(d) can be seen clearly, but there are many peak values in figure 3.7(c). This is because there are many ways in which figure 3.7(b) can be encased by the full pot in figure 3.7(a). The crux is that correlation is less effective if one of the pots is not entirely full. This problem can be overcome by using edge detection. The edges of a half full pot matches that of a full pot better than their areas do. There are fewer ways for edges to match perfectly than there are ways for areas to encase one another. Edge detection is applied on figures 3.7(a) and (b) before correlation. The result is shown in figure 3.8(a) and (b) respectively. The correlation of these two images is shown in figure 3.8(c). (a) (b) (c) Figure 3.8: Edge detection before correlation. (a) The edges of the centred pot obtained from the calibration stage. (b) The edges of the image obtained from the operation stage. (c) The correlation of (a) and (b). The position of the peak value in figure 3.8(c) is very close to what it would have been if the image in figure 3.8(b) was that of a full pot. If the pot in figure 3.8(b) is completely empty then the correlation process will yield only a black image as a result and of course no peak value. There are two more problems left with the process described so far and they are discussed in the following two sections. 3.2.5 Correlation and the problem of small distortions A problem of the practical kind has been neglected so far. The images of pots obtained after subtraction of the background were always perfectly black except for the coffee pot itself like the image shown in figure 3.9(a). In practice, however, some small spots may be present in the background like in the image shown in figure 3.9(b). (a) (b) Figure 3.9: Noise after subtraction of the background. Image of the pot (a) without noise and (b) with noise. The noise in figure 3.9(b) may be due to changing directional light, small objects introduced to the scene like a pen placed next to the coffee pot or someone moving the camera or the pot slightly. The camera itself may even introduce static noise like televisions do. This noise can fortunately be removed using an algorithm which finds the largest area of contiguous non-zero pixels in an image. As long as the noise is small enough and does not touch the coffee pot it can be removed. There is, however, one type of distortion which cannot be removed by the use of the above mentioned algorithm and is discussed in the following section. 3.2.6 Correlation and the problem with the shadow of a coffee pot If the background is subtracted from an image of the coffee pot in which the shadow of the pot is visible and dark enough this may cause the shadow to appear in the result as well. Figure 3.10 illustrates this problem. The reason for the problem of course is that the shadow of the pot is not part of the background as it will not be present if the pot is not present. It is not part of the coffee either which means that is has to be removed in some way. Figure 3.10: The shadow of the coffee pot causes distortion when the background is subtracted. An important fact to note is that the shadow in figure 3.10 appears only to one side of the coffee pot. This means that it may be removed using an algorithm which detects the point of maximum symmetry in the image. 3.2.7 The problem with changing light conditions Changing light conditions pose a problem when subtracting the background from an image. If the image captured during calibration is much lighter than the image captured during operation the subtraction of the two will result in large areas of non-zero pixels. When this happens the system will not be able to discern the coffee pot. Some way of cancelling out the effect of light must therefore be developed. One way would be to normalise the image regarding its brightness. Ambient light can be modelled by a constant offset in grey level throughout the entire image. The average grey level of the image can then simply be subtracted from each pixel in the image. Another method was chosen though. It was noted in section 3.2.1 that the grey levels of the coffee pot are within the lower 20 percent of the grey levels of the entire image. If a constant grey level is added to all pixels in the image then the grey levels of the pot will still be within the lower 20 percent. This means that the image must be thresholded to the lower 20 percent of grey levels instead of a constant threshold. This way the pot and other darker areas will be extracted independent of the amount of ambient light. Another class of lighting is directional light. Directional light has a constant component (i.e. adds a constant grey level to all pixels in the image) which is handled by the method discussed above. However, directional light also causes changes in the direction and reach of the shadows of objects. When subtracting the background these changing shadows cause background noise. A solution to this problem is discussed in detail in section 3.2.5. A system to locate the coffee pot The final design of the system which will find the pot can now be assembled from all the components discussed so far. Figure 3.11 on the following page gives an overview of the entire system. During the calibration stage the user supplies an image of a full pot to the system as well as an image of the background without the pot. Thereafter the system will capture images of pots filled to various levels and determine their positions. Remember that mirroring an image before convolving it with another is the same as correlating them without mirroring. -800100-11430000 . Figure 3.11: The entire process of locating the coffee pot using correlation. 3.2.9 Correlation and the fundamental flaw So far the system is able to locate the coffee pot in a given image. In the process of doing this it has to separate the pot from the background in order to prepare it for the correlation process. At this point in the process, however, the system is ready for determining the coffee level and thus eliminates the need to locate the pot. A method for measuring the coffee level without locating the coffee pot is discussed in the following section. 3.3 Measuring coffee without using correlation The original idea was to find the coffee pot using correlation. After locating it the amount of black pixels in the area of the pot could be counted and used as an indication of the coffee level. However, it would be superb if correlation could be avoided altogether as it is computationally expensive. Correlation may take very long when a large amount of pixels (i.e. large or high resolution images) are involved. This is true despite the fact that correlation can be calculated efficiently using convolution and consequently the FFT. Figure 3.12(a) below shows the coffee pot as it was extracted during calibration. Figure 3.12(b) shows a half full coffee pot extracted during the operation stage of the system. (a) (b) Figure 3.12: The coffee pots extracted during (a) the calibration stage and (b) the operation stage of the system. The white areas are caused by dark areas in the original images. The process so far has removed all the white areas which are not caused by the coffee itself. These are the small objects discussed in section 3.2.5 and the shadow of the coffee pot discussed in section 3.2.6. The white seen in figures 3.12(a) and (b) therefore can only be attributed to the presence of coffee in the original images. A simpler method for measuring coffee would be to count the amount of pixels in both these images and calculate their ratio. The ratio will indicate to what percentage the pot in figure 3.12(b) is filled. The above method will work as long as the pot captured during the calibration stage was completely full and the resolutions of the two images are the same. A high resolution image of a full pot has more pixels than a low resolution image of a full pot. This will cause the ratio between the amounts of pixels in the images to be wrong. If the percentage of white pixels in each image is determined instead of the amount then this problem of unequal resolutions can be overcome. This can be seen as normalising the image resolution. The figure on the following page illustrates the final measuring process. -685800-34290000 Figure 3.13: The entire process of measuring the coffee level 3.4 Conclusion In section 3.2 correlation as a means of locating an object was explored. Many practical complications were encountered. The handling of most of these practical complications constitutes the pre-processing required for the final design. The final design avoided the use of correlation altogether and is discussed in section 3.3. Some constraints were introduced during the development of the system. One such constraint is that the coffee pot may not stand in front of a dark background. Another constraint is that no dark objects which are larger than the coffee pot may be introduced to the background. The reasons for these constraints are discussed in section 3.2.2. The system designed in this chapter is the measurement component of the final coffee usage monitor. The other component, namely the web interface, is discussed in chapter 4 when an overview of the entire monitoring system is given. Chapter 4 The system layout and implementation 4.1 Introduction This chapter gives an overview of the entire coffee usage monitoring system. It shows how a web interface is used to control the system and view the measurements it has taken. The measurements are also stored in a database to be retrieved on demand by the user. Section 4.2 details the system architecture and section 4.3 discusses the programming languages and software used for its implementation. Section 4.4 discusses some of the most prominent practical issues that were encountered. 4.2 System layout Figure 4.1 below illustrates the layout of the system. 342900255905Web page Database User Central system accesses controls serves updates accesses camera coffee pot 00Web page Database User Central system accesses controls serves updates accesses camera coffee pot Figure 4.1: The layout of the entire system. The central system includes a web-server to serve the web page as well as a continuously running program to measure coffee and update the database. The software and programming languages that were used to implement these two functions are discussed in section 4.3. The continuously running program runs on the computer attached to the camera. It captures images of the coffee pot and determines the coffee level. It then stores this information in the database together with the date and time of the measurement. The web page has three major functions. The first function is to control the monitoring system. It may stop or start the monitoring system at any time. The second function is to calibrate the system. This involves the user putting a full pot of coffee in front of the camera and pushing a button on the web page to capture the image. The user then takes the pot away and pushes another button. This calibration should be done each time the camera or coffee machine is moved as well as when the background changes significantly. The third function of the webpage is to display statistics of the coffee usage over a period of time specified by the user. One of these statistics involves calculating the amount of pots of coffee made over a period of time. This can be calculated by examining the database. Two consecutive measurements jumping from around 0 percent to around 100 percent indicates that the pot has been refilled. As will be explained in section 4.3 the web page accomplishes all this by using CGI. Any other statistics (like the current and average age of the coffee) can also be calculated by examining the database. The database was implemented using a text file rather than a full-scale relational database. The main reason for this is that text files are more easily accessible to programmers who wish to expand the project in the future. Another reason is that a text file circumvents the need for a database management system (DBMS). One may argue that a DBMS offers more functions than can reasonably be implemented by this tailor-made text file solution. The simplicity of the data to be stored (namely a date, time and measurement) and the information to be retrieved makes the extra functionality offered by a DBMS unnecessary. 4.3 Software and programming languages Many different programming languages and software packages were used during the development of the project and are still used during its operation. If the reader wishes to implement this project or one similar to it, it is recommended that these languages and packages be used. Developing an image processing system requires a considerable amount of debugging as well as the writing of small test programs. Doing this development in a normal programming language like C or even a very high level language like Python is quite tedious. It is therefore recommended that the development of the image processing algorithms be done in MATLAB. This package offers many tools and built-in functions which accelerate the algorithm development noticeably. The central system performs a wide variety of functions. It must be able to capture images, perform image processing, serve a web page and handle a text file database. A rather powerful programming language is therefore required to implement this component. Python was found to be the most versatile in this regard. Python can make operating system calls on many different operating systems. This ability can be used to capture images using the camera. On a Linux system ‘video for Linux (v4l)’ and ‘streamer’ can be used to capture images from the command line. This command line command can be run from within a Python program using Python’s os.popen() or os.system() function. A set of modules called the Python Imaging Library (PIL) can be installed with Python. This library provides rather advanced functions and was used to implement the image processing algorithms designed with MATLAB. Python also provides modules for Common Gateway Interface (CGI) functionality. CGI is used to invoke programs on the web server from the web page. The web page serving component is not part of the central system and can actually be implemented using other languages. However, if this component is to be integrated into the central system at a later time it would be advantageous if it is already in the same language. HTML forms are entities on a web page which contain text boxes, drop boxes, etc. for a user to enter information into. CGI lets the user submit an HTML form to a specific CGI program on the web server. The web server then invokes the specified program which will process the submitted form. The first line in the CGI program usually indicates an interpreter (Python in this case) which must be launched in order to run the program. After processing the form the program sends a web page back to the user and the process repeats. An example of this is when the user requests information by entering two dates on a form on the web page and submits this form by pushing a button. The form is then processed by a CGI program which extracts measurements made between those dates from the database and possibly calculates some statistics. A web page is then sent back to the user displaying the requested information. The Apache web server was chosen for this project as it is effective and easy to come by. Python makes the creation and modification of text files very easy and is therefore used to implement the database as well. 4.4 Practical complications Most (if not all) engineering endeavours are accompanied by practical complications. Most of the complications encountered in this project were caused by shadows, directional light and image background characteristics as was seen in chapter 3. These complications are part of the development process and methods were designed and adjusted to accommodate them. The following subsections discuss some of the complications caused by the environment in which this project was implemented. 4.4.1 Programming languages A common source of complication is the unexpected attributes of software and programming languages. A programmer often depends on a programming language having a specific attribute and plans accordingly. Later, when it is discovered that the language lacks the desired attribute, the programmer has to change his/her designs. One such unexpected attribute of Python is that the amount of recursions it allows is limited. This problem was encountered during the implementation of the algorithm which finds the largest area in an image. The first effort was a recursive function which calls to itself for every pixel belonging to the area currently under investigation. Because areas can get fairly large (mostly due to high image resolutions) the recursion limit of Python was quickly reached. The solution was to implement the algorithm using lists as explained in section 2.3.1. 4.4.2 Coffee pot attributes The coffee pot itself caused some unforeseen problems as well. Some coffee pots have black plastic handles which may cause problems during calibration and subsequent measurements. Figure 4.2 shows an image of a typical coffee pot with a black handle. Figure 4.2: A typical coffee pot with a black handle. Assume that a black handle is attached to the top of the pot. The handle is not removed during image thresholding because clearly it is dark enough to be seen as coffee. It also touches the coffee, so the algorithm for finding the largest area will not remove it. The handle is thus seen as coffee which is a problem since it may or may not be seen as part of the coffee in subsequent measurements. It will be seen as part of the coffee if the coffee level is close enough to the handle like it is during calibration. When the coffee level is low enough it will be far enough from the handle and therefore unattached to it. However, if the coffee level is too low then the handle may become larger than the area of the coffee and the handle will be seen as the coffee. The measurements taken below a certain coffee level will then all be the same. The solution to this problem is to include an empty pot in the background image taken during calibration. The handle will then be seen as part of the background so that it will be removed when the background is subtracted. Figure 4.3 illustrates the difference this modification makes to the thresholded images. The pot in figure 4.2 is used as an example. (a) (b) (c) (d) (e) (f) Figure 4.3: Using an empty pot as background instead of no pot at all. (a) Background without an empty pot. (b) Full pot after subtracting (a). (c) Near-empty pot after subtracting (a). (d) Background with an empty pot. (e) Full pot after subtracting (d). (f) Near-empty pot after subtracting (d). 4.4.3 Movement between the camera and the pot If the camera is placed in such a way that movement between the camera and the pot is possible then this may cause inaccurate measurements. A person, for example, standing in front of the camera or walking past it may cause the system to capture an image of that person. The system will then try to determine the amount of coffee it sees, but will obviously fail. If one assumes that a person will not stand in the absolute same position for a long time or that most people will walk by then this problem can be overcome. The solution is to take a few measurements per minute and examine to what extent they agree. If the measurements are all more or less the same then this indicates that a person is standing absolutely still or very close to the camera or that no-one is on front of the camera. The system will then assume that this measurement is correct and enter it into the database. If, however, the measurements do not agree at all then it indicates someone is moving in front of the camera. In this case a median of the measurements can be stored in the database or the system can keep on measuring until the measurements remain constant. The system will then judge a measurement as correct if it stays the same over a long period of time. Making this period long enough will eliminate most of the errors. A period of 5 minutes was chosen for this project as very few people stand still for longer than 5 minutes. The suggested solution, however, is to place the camera as close to the pot as possible. This will reduce the movement between the camera and the pot as well as reduce the effect of new objects that are added to the background (refer to section 3.2.2). 4.4.4 Reflections The problem with round glass coffee pots like the one shown in figure 4.2 is that they reflect light sources. These reflections cause small holes to appear in the black areas representing the coffee as seen in figure 4.3(e). These reflections are, however, not evenly distributed and therefore comparing a half full pot with few reflections to a full pot with many reflections will cause reduced accuracy. Note that the near-empty pot shown in figure 4.3(f) does not have many of these holes in it. The same problem occurs if the coffee machine has black buttons or panels directly behind the coffee pot. These small black objects cause the same small holes that the reflections do. Although the loss in accuracy is small enough to neglect there is a way to improve the situation. The holes in the area representing the coffee can be removed by filling them. This process is called region filling and is discussed by Gonzales and Woods [6]. Due to time constraints this method was not implemented. Another problem is caused by the reflections of large objects like the walls of the room. These reflections cause the grey level of coffee to be higher than expected. In section 3.2.1 it was assumed that the grey level of coffee is within the lower twenty percent of the grey level range of the entire image. This number was raised considerably by reflections and had to be adjusted to the lower fifty percent. 4.5 Conclusion Section 4.2 gave an overview of the layout of the entire system. It illustrated how the components interconnect – how the web page controls the central system, how the central system uses the camera and how the database is managed. Section 4.3 detailed the specific programming languages and software packages that were used. It also explained why these languages and packages are well suited to the task and how they are applied. Section 4.4 discussed some of the practical complications encountered during implementation. Most of these complications were coped with during design and development and are discussed at greater length in chapter 3. Chapter 5 Measurements and tests 5.1 Introduction A number of tests were conducted to ensure that the image processing component of the system functions correctly. These tests involve capturing test images and then applying the image processing methods described in Chapter 2. The resulting images are then examined to determine whether they are in accordance with the results the theory depends upon. These tests are discussed in section 5.2. Measurements have also been taken on test images to determine the accuracy of the system under typical conditions. The results of the measurements are discussed in section 5.3. Testing the image processing component This section examines the results of the image processing techniques discussed in chapter 3 when applied to test images captured by a camera. This is done to ensure, step-by-step, that the image processing component of the system functions properly. Figures 5.1(a), (b) and (c) show the images of a full, half full, and empty pot respectively. The result of thresholding these three images at 50 percent is shown in figures 5.1(d), (e) and (f) each directly below its original counterpart. (a) (b) (c) (d) (e) (f) Figure 5.1: Thresholding the (a) image of a full pot, (b) image of a half full pot and (c) the background image at fifty percent to obtain the binary images in (d),(e) and (f) respectively. The next step in the process is to subtract the background in figure 5.1(f) from the images in figures 5.1(d) and (e). Figure 5.2 shows the result. (a) (b) Figure 5.2: Result of subtracting the background. (a) The image of a full pot after subtraction and (b) the image of a half full pot after subtraction. The two images in figure 5.2 will be used to determine the coffee level by counting the white pixels in each and calculating the ratio. There are, however, two steps left before this can be done. The first step is to remove all the noise in the background by finding the largest areas in these images. The result is shown in figure 5.3. (a) (b) Figure 5.3: Finding the largest area in the binary images after background subtraction. The largest areas in the images of (a) the full pot and (b) the half full pot are shown. After finding the largest area the shadow of the pot must be removed. Applying the algorithm which finds the point of maximum symmetry in an image yields the results shown in figure 5.4. Figures 5.4(a) and (b) show the images in figures 5.3(a) and (b) respectively, but with their shadows removed. (a) (b) Figure 5.4: Removing the shadow of the coffee pot from (a) the full pot and (b) the half full pot. After examining the results in figure 5.4 and doing similar tests at different coffee levels it can be concluded that the image processing component functions properly. The coffee level can now be determined from the two images shown in figure 5.4. 5.3 Measurements and accuracy In section 5.2 it was shown that the image processing component of the system functions correctly. The two images shown in figure 5.4 are examples of the output from this component. These output images will be compared by counting their white pixels and calculating the ratio for different coffee levels. This ratio will then be multiplied by 1.8 litres (i.e. the capacity of the test coffee pot). The results are shown in figure 5.5. The dotted line indicates the true coffee level in millilitres while the solid line indicates the measured coffee level. Figure 5.5: Measured coffee level (solid line) compared to the true coffee level (dotted line). From the data collected during this test some useful statistics can be calculated. The maximum error made by the system is 144 ml which is 8% of the capacity of the pot. The standard deviation of the absolute error (i.e. the magnitude of the error) is 36.15 ml and its mean value is 61.10 ml. 5.4 Conclusion The aim of this chapter was to examine the accuracy of the system as a whole. Tests were conducted on the image processing component and it was found that it functions satisfactorily. The output from this component was then used to take measurements at different known coffee levels. The results were compared to the true coffee levels and statistics regarding the magnitude of the error were calculated. Chapter 6 Conclusions and recommendations 6.1 Introduction This chapter summarises the achievements of this project, draws some conclusions and makes recommendations for future development. Achievements and conclusions The main achievement of this project is the development of an automatic coffee usage monitoring system using image processing techniques alone. The exclusive use of image processing makes the system more adaptable to its physical environment than many existing mechanical or electronic systems. The accuracy of the system is high enough to regard the coffee level detection as a success. The constraints introduced during system development do not make the system impractical in typical environments. From these two properties of the system one may conclude that the system as a whole is a success. This project shows that it is possible to measure dark fluid levels in a transparent container. One of the shortcomings of this system, however, is that fluids in an opaque container cannot be measured. In addition, clear fluids cannot be measured either. In these situations existing mechanical and/or electronic systems are better suited. Recommendations for future development A few suggestions can be made to future developers interested in this project. These suggestions include possible methods of increasing the accuracy of the system as well as methods of automating the system further. The accuracy of the system was examined in section 5.3. One of the reasons for the errors in measurements, mentioned in section 4.4.4, is the reflection of light sources in a glass container. These reflections were shown to create small holes in the white area representing the fluid in the container. It was also suggested that this problem can be solved using region filling. In section 3.2.1 it was mentioned that the grey levels of the fluid in the container are within the lower twenty percent of the grey levels of the entire image. This number was obtained through experimentation and had to be changed manually due to the unexpected effect of reflections. One way of automating the system more would be to find a way of automatically determining this grey level range.