Framework for Aligning Curves

• Alignment between the curves is a pairing of points of two curves C, C'

• Goal is to find

• "good" alignment between the curves

• defines a distance between the curves

Representation of alignment

• Previous approaches [Cohen:ECCV 92, Younes:JAM 96] represent alignment by a function g : s->s'

• a single point on the first curve (C) cannot be mapped to a segment of second curve (C')

• inherently asymmetric [Tagare:ICCV95]

New representation of alignment

• Alignment is treated as a pairing of points, one on each curve

• represented in terms of a pair of functions h, h' which  relate arclengths of C and C' to a new parameter 

• Can do the optimization explicitly in the space of two functions [Tagare:ICCV95]

• two functions introduce a superfluous degree of freedom

• different traversals h,h' give rise to the same alignment, but can represent the same pairing

• Pairing of points is specified by arc-lengths (s,s') along C and C'

• Alignment is then represented as a monotonic path in 2D, alignment curve in the domain s,s'

• Alignment can now be represented by a single function, instead of two

• We use the angle between the tangent of the alignment curve and x-axis, 

• coordinates of the alignment curve can be obtained by integration
 

•   is constrained to lie in  by monotonicity condition

Goodness measure for an alignment

• we assume that goodness of the optimal match is sum of the goodness of matching subsegments

• hence, consider the cost matching two infinitesimal curve segments of C (AB) and C' (A'B')

• as intrinsic properties are to be compared, we align start points and their tangents





• cost of matching is defined as length and curvature differences
• the goodness measure can be expressed in terms of  of the alignment curve

• the optimal alignment is found as
• distance between C, C' is then defined as

• distance  is a metric

II. Finding the optimal alignment curve

• Uses dynamic programming to find the global optimum

• Corresponds to a shortest path problem

• Alignment curve is discretized

• Discretize x-axis (curve C) as 

• Discretize y-axis (curve C') as 

• Template consisting of nine incoming curves (at different slopes) is used to update  cost

• Complexity of algorithm is 

Extension to closed curves

• Have to try all start points on the first curve (C)

• Brute-force search increases complexity by n

• We use the fact that alignment curves do not intersect to reduce the search space [Maes:IPL90]

• Complexity of algorithm is