A SOFM Improves a Real Time Quality Assurance Machine Vision System J. Martín-Herrero, M. Ferreiro-Armán, J.L. Alba-Castro
[email protected],
[email protected],
[email protected] Dpt. of Signal Theory and Communications, University of Vigo, SPAIN
Abstract1 We present a high speed machine vision system for the inspection and quality assurance of canned tuna, which is currently working at a rate over 1000 cans per minute. The system inspects the geometry of the can and its contents at a resolution of 4 pixels/mm. It is the evolution of a first prototype through the introduction of a Kohonen network, which maps texture features into a two dimensional grid where the user defines quality neighbourhoods. The inspection time, increased from 35 ms to 38 ms per can, allows the introduction of the system in the same production lines without affecting total performance, but with higher accuracy and user satisfaction.
1. Introduction Several recent works have shown the suitability of Self Organizing Feature Maps (SOM) [1] for machine vision applications [2-4]. A SOM maps a high dimensional space of feature vectors into a lower dimensional map while preserving the neighbourhood, such that feature vectors which are close together in the input space are also close to each other in the lower dimension output space, and feature vectors which are separated from each other in the input space are assigned separate nodes in the output map. Therefore, connected neighbourhoods can be defined in the output map which correspond to arbitrary shaped connected regions in the higher dimension input map. A drawback of SOM is speed: for every feature vector to be classified as appertaining to a given neighbourhood, it has to be confronted with every node in the map, which involves the computation of an Euclidean distance or a dot product per node, in order to find the best matching unit or winner node. Several methods have been proposed to speed up the winner search [5-7] but their suitability for a given map and application depends on the dimension of the feature vector, the size of the map, the required accuracy on the selection of the winner, 1
This work has been supported by the Spanish Ministry of Science and Technology, under contract DPI2000-0446-P4-03.
Proceedings of the 17th International Conference on Pattern Recognition (ICPR’04) 1051-4651/04 $ 20.00 IEEE
and the presence or absence of local minima in the surface of distances to the feature vectors. Driven by the encouraging results reported by Niskanen et al. [2] and the clear improvement in the user interface which this would entail [4], we resolved to include a SOM into our machine vision system for the quality assurance of canned tuna [8]. The system inspects the geometry of a can, the suitability of its edge for a correct closure, and the quality (uniformity of the meat, proportion of crumb, presence of strange bodies, dark tissue, blood stains, or bruises) and integrity (absence of significant holes) of its contents at a rate over 1000 cans per minute. Section 2 summarizes the original system, section 3 describes the SOM approach and how the system was adapted to work with it, and section 4 analyzes the performance of the new system and discusses its opportunity.
2. The original system 2.1. Hardware The system uses an 8-bit 1024-pixel greyscale line scan CCD camera connected via a digital frame-grabber to an
[email protected] desktop computer (PC) running under MS WindowsXP. The high can rate, over 1000 cans per minute, forces a very short integration time, so the light source is a 150 W halogen lamp guided into a slot feeder via optical fibre which allows the camera to work at a line rate of 12000 lines per second, with a spatial resolution in the order of 4 pixels/mm. A line scan camera was selected in order to minimize hardware necessities, increasing robustness, and to eliminate speed limiting elements such as an infrared barrier for target detection. Line scan cameras do not need frame scan reset prior to acquisition, and can be run in constant acquisition mode, such that speed is further improved. Can detection is entirely performed by dedicated image processing software routines, which examine the camera output on a per-line basis. For the rejection of the defective cans, we also avoided movable components because quick response, high speed, and robust long term functionality was required. We use a compressed air system controlled
by electro valves directly attached to an I/O card in the computer. This allows very fast, accurate control of the electro valve, such that it will reflect the state of a bit at a given memory address in the computer.
2.2. Software Can detection is performed through the modelling of the carrying belt as a stationary random process, and the observation of the current grey level histogram. At the same time, we check its shape and parameterize its border in search of global deformation and local defects in the metal: notches, dents, lack of protective coating, faulty welded seam, and presence of strange bodies (sometimes just a small piece of tuna) which could affect the closure. The width of the border is also measured along the whole perimeter. The process is indistinctly performed in round and oval cans. Based on the parameterized edge of the can, a region of interest (ROI) is determined inside the can, to analyze its contents. First, the system measures the similarity between several affine transformations of the ROI, to measure the degree of large-scale uniformity and to detect noticeable strange bodies (usually fishbone and scales) and big holes (absence of product). Then, a grey level cooccurrence matrix is computed [8], and its entropy measured as: 255 255
E = −¦¦ pij log( pij ),
(1)
i =0 j =0
where pij is the ij element on the co-occurrence matrix, divided by the total number of pixels in the ROI. Given the lack of a precise definition separating crumb from bulk meat, or bad from good-looking tuna, we tested the suitability of this set of measurements by its goodness of fit to the 'mean opinion score' (MOS) of a number of quality assurance operators. Then the system segments the ROI grey level in three clusters, such that three major types of features can be distinguished: 1) light tuna meat, 2) dark tuna meat, and 3) holes, crevices, blood stains, and bruises. The statistical parameterization of each of the three features, by modelling the histogram as a mixture of three Gaussian distributions, allows us to draw conclusions about the relative ratio of light meat (good quality tuna) to dark meat (poor quality), and the quantity of holes and bruises. It also gives us an adaptive grey level threshold for the extraction of holes, crevices, bloodstains, and bruises, as the maximum likelihood threshold between the two lower mean Gaussians. At first we used the EM algorithm to strictly model the histogram as a Gaussian mixture, but later we found that k-means was a good enough approximation with a considerable increase in speed (only integer arithmetic is involved).
Proceedings of the 17th International Conference on Pattern Recognition (ICPR’04) 1051-4651/04 $ 20.00 IEEE
Blood stains and bruises (bruise-like areas, BLA hereafter) cause a negative impact in the appearance of the product and may affect its organoleptic properties. In the thresholded ROI we detect and measure the extent and number of the possible BLA via a specifically designed algorithm [8]. The use of full-custom highly efficient code allows the system to achieve an average total inspection time as low as 35 ms per can (localization, extraction, edge analysis, contents inspection, decision, and reaction).
2.3. Drawback There is a threshold (tolerance) for each of the measured characteristics, which the user can tune on-line according to the production requisites. But it is precisely here where the two major drawbacks of the system arise: 1) the high number of characteristics analyzed implies a high number of sliders to control by the user. 2) Some of the characteristics are closely related, and sometimes hardly distinguishable (for instance: good appearance, percentage of crumb, uniformity), such that it may be very difficult to achieve the desired results just by changing a set of sliders. In other words, it is quite possible that the desired decision region in the feature space cannot be drawn by means of straight lines parallel to the axes, which is the only kind of decision region allowed by a tunable threshold per feature.
3. The SOM approach To deal with the mentioned constraints inherent to the system described in the previous section, we resolved to include in the system the approach described by Niskanen et al. [2], which used a SOM to map a feature vector into a two dimensional map where the user can draw a series of quality neighbourhoods. Thus, the interface becomes more intuitive and friendly while the decision capacity of the system is enhanced, since the definition of arbitrary decision regions in the feature space becomes possible. Moreover, increasing the dimension of the feature space, i.e., using more parameters to characterize the product, results in no cost for the user, provided that the quality of the mapping is not reduced (the neighbourhood is kept in the dimensionality reduction). A new feature doesn’t imply a new slider for the user. He still will be presented a two dimensional map where he just has to draw cluster boundaries defining different quality products (see Figure 3, explained later on). In the analysis of the contents, a ROI is determined exactly as before, but now it is not parameterized as a whole, but divided into square blocks 50×50 pixels in size with a 60% horizontal and vertical overlap. It is each block that is now parameterized to compose a feature vector which is mapped into the SOM.
First, a set of cans is used to form a train set of blocks, from which the SOM is constructed. A new set of cans can be added in any moment to the train set such that the SOM will learn the new cans without forgetting the previous knowledge. This is achieved by keeping the previous nodes as initial point for the re-training, replacing the oldest blocks In the training set with the new ones, and updating neighbourhood influence depending on the number of new blocks added. Mathematically, wl wl
j +1
(1) = w l (T j ),
j +1
(t + 1) = w l
j
j +1
(t ) + α
j +1
l ∈ Neighbourhood winner (t +1)
[
(t + 1) x(t + 1) − w l
§ § (w winner − w l (t )) ntotal j +1 σ (t + 1) n new © ©
α j +1 (t + 1) = exp¨¨ − ¨¨
j +1
4. SOM system performance
]
(t ) ,
(2) · ¸ ¸ ¹
2
· ¸ ¸ ¹
where j is the ordinal of re-trainings, Tj denotes the last update iteration at jth re-training; nnew is the number of new blocks added to the training set, ntotal is the number of blocks in the training set, and σ(t) is a decreasing standard deviation Besides all the parameters we were using in the original system we added the next features: •
•
Provided the real time constraints of the system, our major concern about the SOM was the winner search. It involves the floating point computation of an Euclidean distance between feature vectors per map node, a considerable computational overhead per block. However, given the current performance of desktop computers, an exhaustive search proved not to be a real load for the system when compared to non-optimal search methods described in the literature.
The percentage of block pixels belonging to a BLA (it characterizes the block and contributes to establish a classification between the different kinds of dark areas in the image). The uniform local binary patterns, LBP8, as defined in [9], but using nearest neighbour instead of bilinear interpolation. This improves the speed at the cost of a slightly deteriorated rotation invariance.
The uniform LBP8 is obtained for a 3×3 neighbourhood constructing a chain code by assigning 1 to every pixel in the neighbourhood around the central pixel which has a greater grey level than the central pixel, and 0 to the rest. Codes with more than one transition 0/1 (non uniform local binary patterns) are assigned label 9. Uniform codes (only one transition 0/1) are assigned a label equal to the number of consecutive 1s. To obtain the uniform LBP8 distribution, the LBP for every pixel in the block is computed, and the number of each type of LBP in the block is recorded, thus obtaining a histogram with 10 bins. After extensive statistical analysis of the LBP patterns that obtained from over 3000 tuna meat blocks, we decided to eliminate the LBP type 9 (non uniform LBP), 1, 4, and 5, because of reiterative correlation with the other LBP. This resulted in a final 8−dimensional feature space, which we mapped into a 17×9 map.
Proceedings of the 17th International Conference on Pattern Recognition (ICPR’04) 1051-4651/04 $ 20.00 IEEE
We compared the system that used the SOM with the system that did not use it in classification of standard round ∅ 7 cm cans. Each of the images included in the experiment has about 300 blocks. The main fact that distinguishes the SOM system from the no-SOM system, apart from the user interface, is that the SOM gives us more robustness against rotation variant illumination. This fact is illustrated in Figures 1 and 2, where we classified the same can in two different positions. In Figure 1, the system classified 56% of blocks as good quality tuna (marked with green circles), 37% as regular quality tuna (marked with yellow circles) and 7% as bad quality tuna, e.g. BLA, (marked with red circles). In Figure 2, the percentages were, respectively, 53%, 37% and 10%. It can also be observed that the cans in Figures 1 and 2 are not illuminated the same way, as the illumination used is not rotation invariant. Another important feature of the SOM system is that the total time spent during the classification of a can is approximately the same as the no-SOM system. The average time spent per can during the different stages of classification are 27 ms for extracting the feature vector (8-dimensional) and 11 ms for performing the winner node search (with an exhaustive search in a 17×9 node map). This gives us a total of 38 ms per can, whereas the average time spent per can in the no-SOM system was 35 ms. Therefore, the time loss due to the SOM
Figure 1. Classification of a ∅ 7cm can.
Figure 2. Classification of a rotated version of the can in Figure 1.
implementation is almost negligible. This time loss can be smaller or even negative if we consider the possibility of performing a sub-optimal winner search instead of the exhaustive winner search. The goodness of a sub-optimal search can be calculated by means of the sub-optimality rate (SOR), given by [2]
n SOR = i , nt
yielded a real time performance that is almost the same as the original system.
6. References [1] T. Kohonen, Self-organizing Maps, Springer-Verlag, Berlin, 1997.
(3)
where ni is the number of vectors for which the best matching unit was not found, and nt is the total number of vectors. Generally, a sub-optimal search with a higher SOR is performed in a shorter time. The user interface has improved considerably with respect to the no-SOM system. In the SOM system, the user can select more clearly the clusters which will determine the three types of tuna (bad, poor, or good), as he can drag the mouse over the map to establish limits for
[2] M. Niskanen, H. Kauppinen and O. Silvén, “Real-time Aspects of SOM-based Visual Surface Inspection”, Proceedings of SPIE, Vol. 4664, pp. 123-134, 2002. [3] M. Niskanen, O. Silvén, and H. Kauppinen, “Experiments with SOM Based Inspection of Wood”, International Conference on Quality Control by Artificial Vision (QCAV2001), 2, pp. 311-316, Le Creusot, 2001. [4] H. Kauppinen, O. Silvén, and T. Piirainen, “Selforganizing map based user interface for visual surface inspection”, 11th Scandinavian Conference on Image Analysis (SCIA99), pp. 801-808, Kangerlussuaq, 1999. [5] E. S. H. Cheung and A. G. Constantinides. “Fast Nearest Neighbour Algorithms for self-Organising Map and Vector Quantisation”, 27th Asilomar Conference on Signals, Systems and Computers, 2, pp. 946-950, Los Alamitos, 1993. [6] S. Kaski, “Fast Winner Search for SOM-Based Monitoring and Retrieval of High-Dimensional Data”, 9th Conference on Artificial Neural Networks, 2, pp. 940-945, London, 1999.
Figure 3.The user interface. these clusters. Figure 3 shows an example of clustering. This user interface uses the fact that the resulting SOM map is ordered to give a better view of the different types of tuna, which makes clustering easier for the user.
5. Conclusions We have developed a SOM based system which improved a real time system for inspection of canned tuna. The main reason for implementing this system is its friendlier user interface for tuning defective material and the possibility of adapting the map to match the type of tuna. Additionally, the robustness against rotation variant illumination was improved. Finally, increasing the complexity of the feature vector is now possible without increasing the complexity of the user interface. Using highly efficient, full custom code, the SOM system
Proceedings of the 17th International Conference on Pattern Recognition (ICPR’04) 1051-4651/04 $ 20.00 IEEE
[7] E. Kushilevitz, R. Ostrovsky, and Y. Rabani, “Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces”, 30th ACM Symposium on Theory of Computing, pp. 614-623, Dallas, 1998. [8] J. Martín-Herrero and J. L. Alba-Castro, “High speed machine vision: The canned tuna case”, in J. Billingsley (ed.) Mechatronics and Machine Vision in Practice: Future Trends, Research Studies Press, Hertfordshire, 2003. [9] T. Mäenpää, T. Ojala, M. Pietikäinen, and M. Soriano, “Robust texture classification by subsets of Local Binary Patterns”, Proceedings of the 15th International Conference on Pattern Recognition, Barcelona, 2000.
