Industrial Applications of Genetic Algorithms:Image-Calibration Transformation Matrix Solution Using a Genetic Algorithm

Previous | Table of Contents | Next

CONCLUSIONS

A Genetic Algorithm has been successfully implemented to locate an acceptable transformation matrix to map one image into the space of another image. The current state of the GA does find an acceptable solution below the desired target of 0.4 in 42% of the runs in the 2,560-run test-case. Tests with another image-set test-case yields similar results. The desire to better the time using the GA algorithm over the existing iterative approach was achieved for the test case, but the average distance result did not achieve its goal.

Total-Comet-Strike (TCS) Operator

The idea of re-initializing the GA every MG/N generations, by implementing the Total-Comet-Strike operator, was prompted by this effort and looks promising. The next logical addition is to cache all of the final values of the N sub-runs, and if the solution has not converged in the N sub-runs, then either the best of the five should be used and the run terminates, or the best of the N is used and the run continues for another period of time. A time-based or maximum-generation termination needs to be maintained to avoid the rouge case which refuses to converge.

GA Use in a Time-constrained Environment

Revisiting the requirement of achieving a 0.4 distance goal within 20 seconds, on a per-individual case, this goal cannot be guaranteed with the GA approach. However, this requirement needs to be considered for the overall population of runs in the job-set, and if no one run is time critical and the desire is for the entire job-set to complete faster, this GA approach is usable. With the addition of the sub-run TCS technique as described above, the times should be improved even more. As a last resort, for a run which fails to converge, the run can be processed with the existing method with a maximum run-time of twice the targeted 20 seconds (20 for the failed GA, and 20 for the non-GA run). This time could be reduced by avoiding the initialization overhead by carrying both algorithms which share the same front and back ends in the same program (Figures 2.3 and 2.4). This hybrid approach would result in an overall reduction in time for a set of runs, and will also guarantee all runs reach the specified minimum distance value.

Applicability in a Production Environment

With the above mentioned additions to make the algorithm finite in execution time with an acceptable convergence value, this GA-based hybrid method will result in a net time savings without sacrificing the quality of the solution.

Repeatability

A concern with using algorithms which utilize randomness is the repeatability of the solution for the same dataset. In my experience working with engineers, answers, even good answers, which are different for the same set of inputs, are regarded as suspect. With computer-generated randomness as used by the GA, the random-number generator could be seeded with a calculated value derived from the two input images. This would generate the exact same calculated value for the same set of images and parameter settings, which would generate in the same exact result. If the code is to be run on a variety of computers or operating system versions, care should be taken to ensure that the random number generators on the set of computers and operating systems, all behave the same; generating the same set of “random” values. A custom random-number generator could be implemented as part of the GA code, which would run the same across different platforms. The drawback to this is that the random number generator provided with the OS has generally been tuned to perform well on the specific hardware. With the time-critical nature of the requirement, this trade-off would need to be weighed carefully.

Matrix Techniques

The technique of calculating an initial transformation matrix, and then using the GA to find the deltas to this initial matrix, proved to be effective. Identifying the necessary matrix locations and not utilizing the remaining locations also proved to be useful in the performance of this GA implementation. The creation of a sub-matrix crossover which groups matrix values which are related to the matrix usage worked well; it was not the only crossover method required, but the addition of this method aided the algorithm in general.

REFERENCES

  1 Dasgupta, D.; McGregor, D.R. (1992). Digital image registration using structured genetic algorithms. Proceedings of the SPIE - The International Society for Optical Engineering, 1766, 226-34.
  2 Nagao, T.; Agui, T.; Nagahashi, H. (1995). Fitting three-dimensional models to stereo images using a genetic algorithm. Proceedings of the SPIE -The International Society for Optical Engineering Conference Title: Proceedings of the SPIE (USA), 2501, 129-39.
  3 Wallet, B.C.; Marchette, D.J.; Solka, J.L. (1996). A matrix representation for genetic algorithms. Proceedings of the SPIE. 2756, 206-14.
  4 John J. Craig. (1986). Introduction to Robotics: Mechanics & Control. Reading, MA: Addison-Wesley Publishing Company.
  5 F. S. Hill Jr. (1990). Computer Graphics. New York: Macmillan Publishing Company.
  6 David E. Goldberg. (1989). Genetic Algorithms in Search, Optimization & Machine Learning. Reading, MA: Addison-Wesley Publishing Company.
  7 Robert Dain is a student in this class and should have his project included in this publication. He was a fellow Boeing employee, but has since left Boeing to pursue his fortune at Microsoft.
  8 William H. Press et al. (1992). Numerical Recipes in C: The Art of Scientific Computing, second edition. Cambridge, MA: Cambridge University Press.

Previous | Table of Contents | Next

Copyright © CRC Press LLC