OTHER METHODS USED

The problem of image-transformation and image-registration occurs in many other fields, such as aerial and satellite photography, medical imaging, industrial imaging, and computer-vision systems. There has been work in these fields with applying genetic algorithms to search for image-to-image and image-to-object mappings.

Dasgupta et al. [1] designed and implemented a structured GA (sGA) for image-to-image registration. The key to their system is a 2-level GA hierarchy with the higher-level genes activating or deactivating sets of lower-level genes, thus achieving a GA which: (1) can maintain diversity over a large number of generations, (2) can achieve a large effect with a single-bit change, and (3) discover potential areas of search space quickly. For their image-to-image registration, they used simple 2-D image vectors at each of the four corners of the image. This method would be too limited for the image-to-image registration used here.

Nagao et al. [2] look at mapping a 3-D object onto a pair of stereo images using a GA. There are many assumptions they make in their system, including camera-to-camera coordination, thus their use of the basic set of x, y, and z rotation and translation parameters is sufficient without needing the additional operators for scaling and perspective. This method uses too many constraints and assumptions to be used for the images in the current problem.

The effort by Wallet et al. [3] looks at the general problem of using a matrix representation with GAs for various problems. Their focus is on a matrix-based crossover operator which operates on a subset of the matrix rather than a sequence of linear-ordered values. For example, a 2×3 sub-set of a 4×4 matrix can be targeted for crossover and operated on as a set. This allows logical groupings of terms within the matrix to be operated on at the same time, thus manipulating high-level concepts within the matrix. This holds true for some cases in a geometry-based 4×4 transformation matrix, such as the upper four values representing the Z rotation. However, the Y rotation uses the non-adjacent matrix locations R11, R13, R31, and R33, and a global scaling uses the locations R11, R22 and R33. The gains achieved by their suggested matrix-grouping could be further expanded upon by defining a set of N crossover templates to use based on the setup of the matrix usage in the particular GA problem. Another approach is to have the GA manipulate the higher-level parameters directly, such as the rotations, scalings, and transformations, then compose the composite matrix when the transformation is required. The work by Wallet et al. has inspired the creation of some advanced matrix operators which are detailed below.

TEST ENVIRONMENT

A set of eight image pairs was identified to use for this initial GA investigation. Given these sixteen images (eight pairs), fifteen of them have been transformed into the space of the sixteenth, and this has been done for all of the sixteen different combinations. Additionally, each of the sixteen images was transformed to itself to ensure that the system can correctly generate an identity matrix. This yielded a total of 256 image-pair transformations to use for testing.

A second group of eight image pairs was then used to validate the results.

GA CODING SCHEME

To scope the problem, the 256 transformation solutions were run using the existing method. These solutions were analyzed to find “typical” ranges for each of the 16 matrix values, which were used to help define the subset of the search-space which is applicable for this problem. Follow-on tests were run and confirmed that this restricted space is reasonable for the problem in general.

The survey data looks at the average as well as the minimum and maximum values for the non-GA run of 256 transformations. Table 2.1 shows the results of applying a single rotation, scaling, then transformation for the initial calculated guess.