The goal of registration is to align three-dimensional (3D) range images taken from different views by determining the optimal transformation parameters. In order
to reduce the computing time, the procedure of registering 3D range images general-
ly consists of two stages: (1) rough registration and (2) refined registration. Rough
registration is to roughly register two 3D range images so that the relative positions
between the registered images are close, whereas refined registration is to obtain a
more accurate transformation parameters. The iterative closest point (ICP) algorithm
is commonly adopted for refined registration. The purpose of the study is to solve the
rough registration problem by matching the attributes of certain data points on the
3D range images. Because the attribute matching is highly combinatorial, a heuristic
method is developed.

ACKNOWLEDGEMENTS : : : : : : : : : : : : : : : : : : : : : : : : : : : ii
LIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : v
LIST OF IGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : vi
LIST OF APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : viii

CHAPTER
I. INTRODUCTION . .. . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Assumptions . . .. . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

II. LITERATURE REVIEW . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Object Reconstruction Procedure . . . . . . . . . . . . . . . . . 4
2.1.1 Acquisition of Range Images . . . . . . . . . . . . . . . . . . 4
2.1.2 Registration of Range Images . . . . . . . . . . . . . . . . . . 6
2.1.3 Integration of Range Images . . . . . . . . . . . . . .. . . . . 7
2.2 Registration . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Rough Registration . . . . . . . . . . . .. . . . . . . . . . . 8
2.2.2 Refined Registration . . . . . . . . . . . . . . . .. . . . . . 10
2.3 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Applications of Genetic Algorithms . . . . . . . . . . . . . . . . 13

III. METHODOLOGY . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 Parabolic Points . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Formulating Rough Registration Problem . . . . . . . . . . . . . . 19
3.3 Genetic Optimization . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.2 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.3 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.4 Evaluation Function . . . . . . . . . . . .. . . . . . . . . .. 22
3.4 Mean Square Error Function . . . . . . . . . . . . . . . . . . . . 24

IV. EXPERIMENTAL STUDY . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1 Fully-Contained Rough Registration . . . . . . . . . . . . . . . . 26
4.2 Partially-Overlapping Rough Registration . . . . . . . . . . . . . 31

V. SUMMARY AND FUTURE DIRECTIONS . . . . . . . . . . . . . . . . . . . 40
REFERENCES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44

Besl, P. and Jain, R. Invariant surface characteristics for 3d object recognition in range image. Computer Vision, Graphics, and Image Processing, 33, 33–80, 1986.

Besl, P. and McKay, N. Segmentation through variable-order surface fitting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(2), 167-192, 1988.

Besl, P. and McKay, N. A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14, 239–256, 1992.

Bolle, R. and Cooper, D. Bayesian recognition of local 3-d shape by approximating im-age intensity functions with quadric polynomials. IEEE Transactions on Pattern Analysis and Machine Intelligence(4), 418-429, 1984.

Brunnstrom, K. and Stoddart, A. 1996. Genetic algorithms for free-form surface
matching. In Proceedings of the IEEE conference on pattern recognition (pp.
689–692). In ICPR’96.

Champleboux, G., Lavallee, G., Szeliski, S. and Brunie, L. From accurate range imaging sensor calibration to accurate model-based 3-d object localization. In Proceed-ings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 83–89, 1992.

Chen, C., Hung, Y. and Cheng, J. 1998. A fast automatic method for registration for partially-overlapping range image. In Sixth international conference on computer vision (pp. 242–248). In ICCV 98.

Chen, H., Chung, Y. and Ramsey, M. An intelligent personal spider (agent) for dynamic Internet/Intranet searching. Decision Support Systems, 21(1), 41-58, 1998.

Chen, Y. and Medioni, G. Object modeling by registration of multiple range images. Image and Vision Computing, 10(3), 145–155, 1992.

Davis, L. 1985. Applying adaptive algorithms to epistatic domains. In Proceedings of the international joint conference of artificial intelligence (p. 162-164). Joint Conf. on AI.

Disney, S., Naim, M. and Towill, D. Genetic algorithm optimisation of a class of inventory control systems. International Journal of Production Economics, 68(3), 259-278, 2000.

Gen, M. and Cheng, R. Genetic Algorithms and Engineering Design. Wiley-
Interscience, 1997.

Goldberg, D. and Lingle, R. 1985. Allels, loci and the traveling salesman problem. In Proceedings of the first international conference on genetic algorithms (p. 154-159).

Goshtasby, A. Three-dimensional model construction from multiview range images:
survey with results. Pattern Recognition, 31(11), 1705–1714, 1998.

Haralick, R. Digital step edges from zero crossings of second directional derivatives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1), 58-68, 1984.

Holland, J. Outline for logical theory of adaptive systems. Journal of Association of Computing Machinery, 3, 297–314, 1962.

Horn, B., Hilden, H. and Negahdaripour, S. Closed-form solution of absolute orienta-tion using unit quaternions. Optical Society of America, 4(4), 629–642, 1987.

Masuda, T. and Yokoya, N. A robust method for registration and segmentation of
multiple range images. Computer Vision Image Understanding, 61(3), 295–307,
1995.

Rouet, J., Jacq, J. and Roux, C. Genetic algorithms for robust 3-d MR-CT registration. IEEE Transactions on Information Technology In Biomedicine, 4(2), 126–136, 2000.

Stein, F. and Medioni, G. Structural indexing: eŽcient 3d object recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2), 125-145, 1992.

Thirion, J. 1994. Extremal point: definition and application to 3-d image registration. In Proceedings of the IEEE robotics and automation (pp. 587–592). Seattle, WA.

Turk, G. and Levoy, M. 1994. Zippered polygon meshes from range image. In Siggraph (pp. 331–318). Orlando, Florida.

Vidyarthi, D. and Tripathi, A. Maximizing reliability of distributed computing sys-tem with task allocation using simple genetic algorithm. Journal of of Systems Architecture, 47, 549-554, 2001.