Comparison poses a difficult problem in image processing. For instance, conventional metrics sometimes output a large difference value for rotated or mirror versions of the same image. An identical problem occurs when comparing representations of the same object recorded at different angles, or under different illumination conditions or backgrounds. Measuring the similarity of images of different objects is even more challenging. These recognition problems are commonly addressed using systems that can be taught to classify objects by recognizing similarities between the images. Examples are eigenvector-based, neural networks, and fuzzy logic-based systems.
We seek to develop image comparison algorithms that exclude prior teaching to avoid limiting the system to recognizing only cases for which it was trained beforehand.1,2 Our solution is to use morphology transforms based on a cellular genetic algorithm (CGA) that limits neither image comparison nor object recognition. The advantage of such a system is that it can be fed any group of images for processing. It then returns difference metrics based on the number of CGA morphological transforms required to change each image into another.
Figure 1 illustrates the CGA principle. Transformation occurs by taking one pixel at a time from the destination image. The corresponding pixel and its local neighborhood in the starting image then form the CGA local population. Some additional individuals are also generated by genetic operators in this population. Finally, the starting image pixel value is changed to the value in the population that is closest to the destination value.1
Figure 1. Morphological transforms of image pixel gray values based on the CGA. The original image (a) is morphing toward the next image (b). The values in (c) reflect the difference between the local neighborhood pixel values (a) and the pixel value (61) in the middle of the morphed image (b). After one round of CGA-based morphological operations, a new version of a is generated (‘a new’).
Figure 2 shows a step-by-step transformation during the CGA morphing process. Image similarity order is obtained by using a simple traveling salesman problem (TSP) algorithm that can be fed image difference metrics instead of city distances. Figure 3 shows a series of rotated pictures perfectly ordered using a TSP solver. More complex examples are provided elsewhere.1 The difference metric value between the compared images is simply the total sum of the pixel value changes during the morphological transform series, such as the one shown in Figure 2. Usually (∼)50–100 update rounds are required to transform an entire image.
Figure 2. The morphological CGA transform process, from left to right.
Figure 3. Series of rotated images ordered with a traveling salesman solver using image difference metrics based on CGA transforms.
Our results show that comparison based on CGA works reasonably well. The main problem is the long processing time required by morphological operations. To test larger data sets, we have started improving the algorithm for faster processing. One approach would be to use preselection methods that could rapidly eliminate objects not located close to the recognition target. We anticipate that working with such a reduced group of objects would speed up identification.
Department of Electrical Engineering and Automation
University of Vaasa
Tino Mantere obtained a BSc in electric power engineering in 1992, an MS in economics and business administration in 1996, and a PhD in computer science in 2003. He is now a researcher and lecturer in automation technology at the University of Vaasa. His interests are focused mainly on signal processing methods and optimization enhancements using evolutionary algorithms.