Abstract:
An image processing technique for detecting and measuring the size of bruises on fruit, such as apples, is disclosed. A line scan camera is employed to obtain a gray level image of each piece of fruit as it is rotated in front of the camera. The image is digitized, and transferred to a computer which performs a plurality of steps on the image to determine the sizes of any bruises on the fruit from the gray level data. The image data is filtered to remove interference due to pixel-to-pixel variations in the camera, background noise, etc., and is then thresholded to obtain a binary image representation. Clusters of zeros in the resulting binary image that are representative of potential bruises are analyzed to determine their size and shape. If the shape of the cluster is nearly circular, it is determined to be a bruise. From this information, the amount of bruise area on the fruit may be determined, and the fruit graded accordingly.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to an automated system for detecting bruises on apples, or similar fruit, which employs an unique image processing technique to distinguish bruised tissue from non-bruised tissue. 
     Apples are graded according to the amount of bruised skin on their surface. In New York State, for example, apples for processing are reduced in value when greater than 5% of the total apple surface is bruised. Fresh market apples, on the other hand, are graded not only on the size of bruises, but also on the number of bruises. Most apples are graded for size and bruises by U.S.D.A. inspectors who examine a small portion of apples randomly selected from each truck load. Differences in inspector evaluation methods and judgement allow for significant and undesirable variations in the application of the U.S.D.A. standards. What would be desirable then, is for an automated system to be devised which can quickly and accurately determine the amount of bruising on an apple&#39;s surface. 
     In recent years, considerable development work on automated apple grading systems has been conducted. For example, U.S. Pat. No. 3,867,041, to Brown et al., discloses a method for detecting bruises in fruit which employs the use of diffuse surface reflectance of near infrared radiation to differentiate bruised tissue from non-bruised tissue. In ASAE Paper No. 81-3537 (1981), Graf et al. demonstrates this diffuse reflectance detection technique using digital imaging as a means to perform the detection by a non-contact process in a laboratory environment. Experimentation with different image analysis techniques showed that a multivariable linear statistical classification of each pixel in an apple image to be the most successful approach to classify imaged apple tissue bruised or non-bruised. The classification algorithms classified bruised and non-bruised tissue areas as well as a human inspector. 
     In 1984, R. W. Taylor et al. demonstrated that a digital line scan camera could be used in this system in place of a digital matrix camera (Taylor, R. W., Rehkugler, G. E., Throop, J. A., Apple Bruise Detection Using a Digital Line Scan Camera System, Agricultural Electronics-1983 and Beyond. American Society of Agricultural Engineers, pp. 652-662). This eliminated perspective spatial distortion in one dimension and allowed, with careful camera placement, the elimination of the background in the image. Taylor found that the quadratic statistical classification process used was not robust enough to handle the variability of the data. Due to the lack of manufactured uniformity between pixels, an elaborate, time-consuming process of normalization of pixel response was required to improve this classification process. The conversion of Taylor&#39;s algorithms from a quadratic to a linear classifier has failed to improve their performance. Therefore, a non-statistical approach for image analysis for classifying apple tissue and a new algorithm was needed. A suitable algorithm and classification process would be one that gave equal or better results of classification on the same apple images as the algorithm used by Graf et al. 
     SUMMARY OF THE INVENTION 
     It is therefore the object of the present invention to provide an improved digital image processing technique for use with an automated fruit grading system which allows the amount of bruise area on apples, or similar fruit, to be quickly and accurately determined. 
     This, and other objects of the present invention are achieved through the use of a line scan camera such as that employed by Taylor, and a unique image processing technique that eliminates the time consuming normalization process employed by Taylor. In addition, the processing technique eliminates the need for careful camera placement by enabling the background in the image to be filtered out. 
     More particularly, the present invention utilizes an apple or fruit handling system comprised of an orienting section, and a spindling and imaging section. A continuously moving transport cup conveyor is employed for transporting fruit to the spindling and imaging section. Each transport cup is conical in shape for reception of a single apple, or similar fruit, and has an open bottom so that a spinning orienting wheel can engage the bottom of the fruit as it approaches the spindling and imaging section. The orienting wheel insures that the stem-calyx axis of the apple will remain vertical during imaging, and that only the cheek of the apple will be exposed to the line scan camera. This type of fruit orienting device is disclosed in U.S. Pat. No. 3,225,892 to Keesling, which is hereby incorporated by reference. 
     Near each transport cup is a single extended pin coupler link used to engage a spindle mechanism at the spindling and imaging section, and carry it along with each transport cup. The spindle mechanism is mounted on two parallel linear motion guides and is spring loaded to resist movement in the direction of the transport cup travel. After traveling through its sequence of operations, the spindle mechanism springs backward to be picked up by the next transport cup drive pin. 
     The purpose of the spindle mechanism is to engage each apple, and raise it out of its transport cup so that the apple may be viewed by a line scan camera. In addition, the spindle mechanism includes a drive motor which rotates the apple in front of the camera so that an image of the apple&#39;s entire surface may be obtained. 
     A 64 pixel linear photodiode array camera is mounted on a pivot arm that is attached to the spindle mechanism, and causes the camera to rotate slightly as the transport cup moves the spindle mechanism, so that the camera will remain focused on the fruit center as it moves past the camera. The camera pivot arm returns by spring force to the initial starting point every time the spindle mechanism reciprocates to be picked up by the next transport cup. 
     An optoelectronic shaft encoder is mounted on the spindle mechanism, and has a 250 pulse per revolution output that is supplied as start pulses to the camera, so that a two-dimensional 64×250 pixel image is recorded for each apple. The shaft encoder signal is withheld from the camera until an optoelectronic switch disposed near the camera pivot arm is switched on due to movement of the pivot arm. This allows the camera to obtain an image. An interface is provided which includes an 8 bit A to D converter that digitizes the image data and transfers it to the memory of a data processor, such as a minicomputer. 
     A slightly translucent acrylic plastic diffuser is disposed in front of four tubular tungsten bulbs which are mounted in an apple lighting box for illuminating the apples in accordance with the teachings of the Brown et al. patent. This patent is also hereby incorporated by reference. A long pass filter is placed in front of the camera lens to eliminate the transmittance of radiation of less than 750 nanometers in wavelength. 
     The primary obstacle in easily defining the difference between bruised and non-bruised apple tissue in an image is that the reflectance difference of these two tissues is only between 10 and 20 percent gray level difference. Due to indistinct boundaries between the regions, noise present in the images, and pixel-to-pixel variations in manufacturing, classification of tissue types becomes even more difficult. 
     As compared to a matrix digital image such as was employed by Graf et al., the pixel variations become very pronounced in the line scan digital image. In the 64 pixel×250 pixel image, each of 250 pixel values in a row have been sensed by the same camera pixel. This results in a gray level image composed of light and dark rows characteristic of individual pixels. Other gray level changes due to bruising, uneven lighting, and noise are then superimposed on the individual pixel response. If these variations are removed by a normalization process (Taylor, 1984), then the classification of tissue type by gray level becomes clearer. To avoid this normalization process and the processing time it requires, the present invention makes use of a unique image processing technique which processes each image on a row-by-row basis. 
     This processing technique includes the following steps. Each of the 250 pixel values in a single row of the gray level image is an 8 bit data word between 0 and 255, with 0 representing black, and 255 representing white. A digital linear operator applied to the gray level image performs a low-pass filtering of the original image on each of the 64 rows, on a row-by-row basis. This digital operator takes a user selected filter pixel width, such as the first 31 pixel values of a row, finds their average value, and assigns the average value to the middle or sixteenth pixel of the 31 pixel values. The average of pixel values 2-32 is next found, and assigned to pixel 17. This process continues until all 250 pixel values in each of the 64  rows have been replaced by a 31 pixel average. For the last 30 pixels in each row, a wrap around technique is employed to obtain this average. Thus, for example, the value for pixel 250 will be the average of the original values of pixels 235-250, and pixels 1-15. 
     The low pass filtering technique thus effectively substitutes each pixel value in a row of data words, with an average of that value and the values of a plurality of adjacent pixel values, in the same row. It should be noted that the first and last pixel values in a row can be said to be adjacent to one another, since the two-dimensional image that is formed as the apple rotates is actually &#34;wrapped around&#34; on itself. 
     This low pass filtering technique has the effect of smoothing the image so that sharp transitions in the image due, for example, to bruise edges are eliminated. Thus, the resulting low pass filtered image tends to represent the undesirable part of the original image which is due to pixel-to-pixel variations, background, noise, etc. 
     By next subtracting the original image from the low pass filtered image, and then setting all negative values to zero, a resulting filtered image is obtained which represents the gray level of the apple&#39;s surface, without adverse effects from pixel variations, background, or noise. The image thus obtained is inverted, however, with zeros representing light areas, and positive values representing dark areas on the apple&#39;s surface. 
     The resultant filtered image is next thresholded at an arbitrarily selected gray level difference to form a binary image which has 255 as pixel values everywhere except at the original darkest values of the gray level image. These darkest values are assigned the value 0. Thus, any data words having values at or above the threshold will be assigned the value 0, while those data words having values below the threshold, will be assigned the value 255. The value of the threshold is varied in accordance with image quality, background lighting, etc., and typically is set at a value between 0 and 30. 
     Next, the obtained binary image is processed to eliminate stray zeros or 255&#39;s. Thus, for example, if a zero valued data word is located in a row, and is surrounded by data words having 255 as their values, that zero valued data word is changed to 255. Similarly, if a 255 valued data word is found surrounded by a cluster of zero valued data words, that data word is changed to zero. This process helps to further filter out responses that are not due to bruises. 
     The binary image is now circularly shifted until no zero valued data words are present in the first column. This is to insure that a cluster of zeros representing a bruise will not be split into two sections in the image, and eliminates complicated &#34;wrap around&#34; processing of the image. If after the entire image is shifted, no column is found having no zeros in it, the user is informed that the threshold value is too low, and must be increased. The above process is then repeated with the new threshold value. 
     A form of contour following is now applied to each zero valued cluster in the binary image. This locates and counts the perimeter pixels, and counts the total pixels in each cluster for area determination. 
     Finally, a dimensionless measure of shape, called the thinness ratio, T, is now computed for each cluster of zeros, where T=4π(A/P 2 ), and where A=area of cluster of zeros, and P=perimeter of cluster of zeros. 
     From this thinness ratio, the shape of each cluster of zeros in the image can be determined. By thresholding the T value between a minimum and maximum value, only clusters of a nearly circular shape are counted. For a perfect circle, T=1, and thus T is thresholded between some value less than 1 (e.g. 0.4), and some value greater than 1 (e.g. 1.5). Since bruises on apples tend to be circular in shape, the use of the thinness ratio in this manner helps insure that only clusters of zeros that represent bruises will be counted. The area of each counted cluster can now be used to determine the total bruise area, and from this, the apple grade. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and additional objects, features and advantages of the present invention will become apparent to those of skill in the art from the following more detailed consideration thereof taken in conjunction with the accompanying drawings in which: 
     FIG. 1 is a diagrammatic side elevational view of the overall system utilized in the present invention to obtain an image of an apple; 
     FIG. 2 is a general block diagram of the image circuitry for the present invention; and 
     FIG. 3 is a flow chart showing the image processing technique of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Turning now to a more detailed consideration of the present invention, there is illustrated in FIG. 1, the overall system employed by the present invention to obtain an image of an apple, or similar fruit. Specifically, there is shown in FIG. 1, an apple, or similar piece of fruit 10, disposed in a transport cup 12. It will be understood that a plurality of these transport cups that form a conveyor will be utilized in the system, however, for purposes of the present invention, it is sufficient to illustrate only one such transport cup. Transport cup 12 is shown disposed at a spindling and imaging section of the system, and apple 10 is oriented so that its stem-calyx axis is vertical. This orientation is carried out prior to arrival at the spindling and imaging section by a mechanism similar to that disclosed in U.S. Pat. No. 3,225,892 to Keesling. 
     The spindling mechanism shown generally at 14 includes a pair of spindles 16 and 18 for lifting the apple out of transport cup 12, and rotating the apple in front of an apple illumination box 20. The lifting of the apple is achieved through the action of a spindle drive motor 22, a ball screw 24, and a ball nut 26, while the rotation of the apple is controlled by an apple rotation drive motor 28, and an associated gear and chain type transmission mechanism generally depicted at 30. 
     Spindling mechanism 14 is carried along with transport cup 12 by a drive pin 32 on cup 12, and slides along a pair of linear motion guides 34 and 36. A plurality of limit and location switches 38, 40, 42, and 44 are provided on spindling mechanism 14 to control the sequencing of the various movements of the mechanism by associated circuitry, which is not shown. 
     The imaging section includes apple illumination box 20 which has a plurality of tubular tungsten bulbs 46 disposed therein. A slightly translucent acrylic plastic diffuser 48 is mounted on box 20 in front of bulbs 46 so that apple 10 will be illuminated by diffuse near infrared radiation in accordance with the method set forth in U.S. Pat. No. 3,867,041 to Brown et al. Light reflected off of the surface of apple 10, is directed through a passage 50 in box 20 to a lens 52 of a line scan camera 54. Lens 52 has a long pass filter disposed in front of it (not shown), to eliminate the transmittance of radiation having a wavelength of less than 750 nanometers. Line scan camera 54 is preferably a 64 pixel linear photodiode array camera, such as an EG&amp;G Reticon Model LC 600, and is mounted on a shaft 56. This shaft is connected to a pivot arm 58, which in turn is connected to spindling mechanism 14, and enables the camera to remain focused on the apple as it travels along with the conveyor and spindling mechanism. 
     To control the operation of line scan camera 54, an optoelectronic shaft encoder 60 is connected to the lower end of spindle 16, which generates 250 electrical pulses for every revolution of the spindle. These pulses are utilized as start pulses for line scan camera 54, and enable a 64×250 pixel image to be recorded for each apple. An optoelectronic switch 62 is provided which is activated by pivot arm 58 that prevents these pulses from being transmitted to the camera until the pivot arm begins to move. 
     Turning now to FIG. 2, a general block diagram of the imaging circuitry is illustrated. Specifically, line scan camera 54 is shown as being controlled through optoelectronic switch 62, by shaft encoder 60. An interface 64 is provided which includes an A to D converter (not shown) so that the image data from camera 54 can be digitized, and transferred to either a computer 66, or a display device 68. 
     FIG. 3 shows the flow chart for the image processing technique utilized by computer 66 to detect and calculate the area of any bruises on the surface of apple 10. This process is set forth below, and involves a number of steps which are implemented on the computer by subroutines. A sample program for implementing the process is included at the end of this description as an Appendix, and is hereby incorporated by reference. 
     After the line scan camera 54 obtains a complete two-dimensional image of the apple, the image data is stored in the computer&#39;s memory, such as on a floppy disk. As shown in the flow chart of FIG. 3, after the various process parameters are entered into the computer, the apple image data is read from the disk, and is low pass filtered. This low pass filtering is done on a row-by-row basis for each of the 64 rows of the image, and is achieved in the following manner. Each of the 250 pixels in a row are represented by an 8 bit data word, and have a value between 0 and 255, with 0 representing a totally black image, and 255 representing a totally white image. A digital linear operator that performs the low pass filtering takes a user selected filter pixel width (one of the process parameters), such as the first 31 pixel values of a row, finds their average value, and assigns the average value to the middle or sixteenth of the 31 pixel values. The average of pixel values 2-32 is now found, and assigned to pixel 17. This process continues until all 250 pixel values in each of the 64 rows have been replaced by a 31 pixel average. For the last 30 pixels in each row, a wrap around technique is employed to obtain this average. Thus, for example, the value of pixel 250 will be the average of the original values of pixels 235-250, and pixels 1-15. 
     The low pass filtering technique thus effectively substitutes each pixel value in a row, with an average of that value and the values of a plurality of adjacent pixel values, in the same row. It should be noted that the first and last pixel values in a row can be said to be adjacent to one another, since the two-dimensional image that is formed as the apple rotates is actually &#34;wrapped around&#34; on itself. 
     The purpose of the low pass filtering procedure is to smooth out the gray tone image to show only fluctuations of the general background. This is necessary for a number of reasons including: pixel-to-pixel variations created by the line scan camera which generate streaks in the image, indistinct boundaries between regions of the image, and noise present in the image. The low pass filtering technique averages the gray tones, and has the effect of filtering out sharp color transitions which are indicative, for example, of bruise edges. 
     To obtain a filtered image which represents only variations due to apple bruises, the original gray tone image is subtracted from the low pass filtered image, with the resultant filtered image being effectively the inverse of an image which includes variations due only to bruises. By setting all negative values of the resultant filtered image to zero, only darker portions of the image (those indicative of bruises) will have positive pixel values. 
     The next step in the process is to threshold the resultant filtered image so that a two-dimensional binary image can be obtained. Thus all data words having a pixel value below the threshold, and thus indicative of unbruised tissue, are set to the value 255, while all data words having a pixel value at or above the threshold, and thus indicative of bruised tissue, are set to the value 0. The value of the threshold is arbitrarily chosen, and is typically somewhere between 0 and 30, depending on image quality, background lighting, etc. 
     Next, the obtained binary image is processed to eliminate stray zeros or 255&#39;s. Thus, for example, if a zero valued data word is located in a row, and is surrounded by data words having 255 as their values, that zero valued data word is changed to 255. Similarly, if a 255 valued data word is found surrounded by a cluster of zero valued data words, that data word is changed to zero. This process helps to further filter out responses that are not due to bruises. 
     Next, the resultant binary image is circularly shifted until no zero valued data words are present in the first column of the image. The purpose of this is to insure that clusters of zeros representing apple bruises will not show up in two sections of the image, and eliminates complicated &#34;wrap around&#34; processing of the image. If after the entire image is shifted, no column is found having no zeros in it, the user is informed that the threshold value is too low, and must be increased. The above process is then repeated with the new threshold value. 
     A form of contour following is now applied to each 0 pixel value cluster in the binary image. This locates and counts the perimeter pixels, and counts the total pixels in each cluster for area determination. 
     The size and shape of each cluster of zeros must now be measured to determine if in fact, the cluster represents a bruise. Clearly, some dark portions of the image may not represent bruises, but may instead represent spots of dirt, dark regions caused by geometric contours on the apple, or slight variations in lighting at the top and bottom edges of the apple image. These areas must not be counted as bruised areas. 
     To insure that only clusters of zeros that represent bruises are counted, a dimensionless measure of shape called the thinness ratio, T, is computed for each cluster of zeros where: 
     
         T=4π(A/P.sup.2) 
    
     and, 
     A=area of cluster 
     P=perimeter of cluster 
     The area and perimeter of each cluster is easily obtained by counting the total number of zeros in the cluster, and the number of zeros in the perimeter of the cluster. 
     By thresholding the value of T between a minimum and a maximum value, only clusters of a nearly circular shape will be counted. For a perfect circle, T=1, and thus T is thresholded between some value less than 1 (e.g. 0.4), and some value greater than 1 (e.g. 1.5). Since most apple bruises tend to be circular in shape, this will result in only clusters that represent bruises being counted. 
     Finally, the total bruise area on the apple can now be easily computed, and from this, the apple can be graded. 
     The above process eliminates the time consuming normalization procedure employed by Taylor, and has proven experimentally to be both accurate and quick, with a grading accuracy equal to or better than U.S.D.A. inspectors, and a speed as high as 30 apples per minute. It is expected that further refinement of the imaging and processing systems could increase the performance of the overall system considerably. 
     Although the invention has been illustrated in terms of a preferred embodiment, it will be understood that numerous variations and modifications can be made from those of skill in the art without departing from the true spirit and scope of the inventive concept as set forth in the following claims: ##SPC1##