Curve matching by energy minimization in unit quaternions.

Curve matching is essential to many design and manufacturing applications as well as in image processing. In this thesis, several techniques are developed to facilitate the three steps involved in the matching process: representation, correspondence and alignment. For representation, a 3D curve is represented as a unit quaternion curve by quaternion mapping. Through the Serret-Frenet frame, a 3D curve can be considered as the combination of successive rotations. The quaternion mapping is the conversion from these rotations to the unit quaternions. Since curves differing only in scaling have the same image in the quaternion space, this new representation facilitates the matching between objects in different scales. Since the quaternion space has the same structure as the rotation group, this new representation enables the development of efficient algorithms for later alignment. For correspondence, instead of the $L\sb2$ norm as commonly used in identifying the corresponding features, an energy minimization model is formulated. With different correspondences, the strain energy which measures the magnitude of deformation between two curves is computed. Since the strain energy only consists of intrinsic properties of curves, the method is independent of initial positions. The best match is defined as the configuration which has the minimal energy. This energy minimization model is formulated as a functional and the solution is derived by solving the Euler-Lagrange equations. It is shown that the energy minimization process is equivalent to finding the shortest path on a surface. Such an energy surface is derived to represent the terrain of the minimization space. This surface not only serves as a visualization tool, it gives a qualitative prediction of the result of matching. For alignment, two new methods which utilize quaternion distance as the metric in the objective functions are offered. These two methods not only provide faster and more accurate results as compared to the existing ones, one of the two always gives a simple closed form solution which greatly reduces the complexity of implementation.PhDApplied SciencesComputer scienceIndustrial engineeringMechanical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/130951/2/9825213.pd