UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A theory of multi-scale, curvature and torsion based shape representation for planar and space curves Mokhtarian, Farzin 1990

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1990_A1 M64.pdf [ 8.36MB ]
Metadata
JSON: 831-1.0052040.json
JSON-LD: 831-1.0052040-ld.json
RDF/XML (Pretty): 831-1.0052040-rdf.xml
RDF/JSON: 831-1.0052040-rdf.json
Turtle: 831-1.0052040-turtle.txt
N-Triples: 831-1.0052040-rdf-ntriples.txt
Original Record: 831-1.0052040-source.json
Full Text
831-1.0052040-fulltext.txt
Citation
831-1.0052040.ris

Full Text

A Theory of Multi-Scale, Curvature and Torsion Based Shape Representation for Planar and Space Curves By Farzin Mokhtarian B.E.S., The Johns Hopkins University, 1982 M.Sc, The University of British Columbia, 1984 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE F A C U L T Y OF GRADUATE STUDIES DEPARTMENT OF COMPUTER SCIENCE We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA October 1990 F © Farzin Mokhtarian, 1990 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer Science The University of British Columbia Vancouver, Canada Date October 5, 1990 DE-6 (2/88) ii i A b s t r a c t This thesis presents a theory of multi-scale, curvature and torsion based shape representation for planar and space curves. The theory presented has been developed to satisfy various criteria considered useful for evaluating shape representation methods in computer vision. The criteria are: invariance, unique-ness, stability, efficiency, ease of implementation and computation of shape pro-perties. The regular representation for planar curves is referred to as the curva-ture scale space image and the regular representation for space curves is referred to as the torsion scale space image. Two variants of the regular representations, referred to as the renormalized and resampled curvature and torsion scale space images, have also been proposed. A number of experiments have been carried out on the representations which show that they are very stable under severe noise conditions and very useful for tasks which call for recognition of a noisy curve of arbitrary shape at an arbitrary scale or orientation. Planar or space curves are described at varying levels of detail by convolv-ing their parametric representations with Gaussian functions of varying standard deviations. The curvature or torsion of each such curve is then computed using mathematical equations which express curvature and torsion in terms of the con-volutions of derivatives of Gaussian functions and parametric representations of the input curves. Curvature or torsion zero-crossing points of those curves are then located and combined to form one of the representations mentioned above. The process of describing a curve at increasing levels of abstraction is referred to as the evolution or arc length evolution of that curve. This thesis con-tains a number of theorems about evolution and arc length evolution of planar and space curves along with their proofs. Some of these theorems demonstrate that evolution and arc length evolution do not change the physical interpretation of curves as object boundaries and others are in fact statements on the global properties of planar and space curves during evolution and arc length evolution and their representations. Other theoretical results shed light on the local behavior of planar and space curves just before and just after the formation of a cusp point during evolution and arc length evolution. Together these results provide a sound theoretical foundation for the representation methods proposed in this thesis. iii T a b l e o f C o n t e n t s Abstract • 1 1 List of Figures v List of Tables vii Acknowledgments viii 1. Introduction 1 1.1. Criteria for shape representation 2 1.2. Contents of thesis 3 2. Survey of literature 5 3. A theory of multi-scale shape representation for planar curves • 11 3.1. The curvature scale space image 13 3.2. The renormalized curvature scale space image 17 3.3. The resampled curvature scale space image 18 3.4. Evolution and arc length evolution properties of planar curves 20 4. A theory of multi-scale shape representation for space curves '. 23 4.1. The curvature and torsion scale space images 24 4.2. The renormalized curvature and torsion scale space images 30 4.3. The resampled curvature and torsion scale space images 32 4.4. Evolution and arc length evolution properties of space curves 34 5 . Algorithms and implementation 36 5.1. The convolution masks 36 5.2. The sampling algorithm 38 5.3. Algorithms for representations of planar curves 39 5.4. Algorithms for representations of space curves 41 5.5. Efficiency issues 44 5.6. Matching scale space images 46 6. Experimental results and evaluation 48 6.1. Planar curves 48 6.2. Space curves 80 6.3. Evaluation of the representations 100 7. Summary, conclusions and future directions 109 7.1. Summary 109 iv 7.2. Conclusions 110 7.3. Directions for future research I l l References 114 Appendix A. Proofs of results on planar curves 120 Appendix B. Proofs of results on space curves 140 V L i s t o f F i g u r e s Figure 4.1.1 The Frenet trihedron for a space curve 25 Figure 6.1.1 Coastline of Africa 49 Figure 6.1.2 Africa during evolution 50 Figure 6.1.3 The curvature scale space image of Africa 51 Figure 6.1.4 Koch's snowflake curve 53 Figure 6.1.5 Snowflake curve during evolution 54 Figure 6.1.6 The curvature scale space image of the snowflake 55 Figure 6.1.7 Design from a Persian carpet 56 Figure 6.1.8 Carpet design during evolution 57 Figure 6.1.9 The curvature scale space image of the carpet design 58 Figure 6.1.10 Coastline of Africa with uniform, random noise 59 Figure 6.1.11 The CSS image of Africa with uniform noise superim-posed on the CSS image of Africa 60 Figure 6.1.12 Coastline of Africa with severe, uniform noise 61 Figure 6.1.13 The CSS image of Africa with severe noise superimposed on the CSS image of Africa 62 Figure 6.1.14 Coastline of Africa with non-uniform, random noise 63 Figure 6.1.15 The curvature scale space image of Africa with non-uniform noise 64 Figure 6.1.16 The renormalized curvature scale space image of Africa 66 Figure 6.1.17 The renormalized curvature scale space image of Africa with non-uniform noise 67 Figure 6.1.18 The renormalized CSS image of Africa with non-uniform noise superimposed on the renormalized CSS image of Africa 68 Figure 6.1.19 The resampled curvature scale space image of Africa 69 Figure 6.1.20 The resampled curvature scale space image of Africa with non-uniform noise 70 Figure 6.1.21 The resampled CSS image of Africa with non-uniform noise superimposed on the resampled CSS image of Africa 71 Figure 6.1.22 A self-crossing curve during evolution 74 Figure 6.1.23 The CSS image of the curve of figure 6.1.22 75 vi Figure 6.1.24 A convex, self-crossing curve during evolution 76 Figure 6.1.25 The CSS image of the curve of figure 6.1.24 77 Figure 6.1.26 A simple curve during (regular) evolution 78 Figure 6.1.27 Curve of figure 6.1.26 during arc length evolution 79 Figure 6.2.1 Two views of a space curve depicting a fork 81 Figure 6.2.2 The fork during evolution 82 Figure 6.2.3 The torsion scale space image of the fork 83 Figure 6.2.4 Two views of a space curve depicting a bottle-opener 84 Figure 6.2.5 The bottle-opener during evolution 85 Figure 6.2.6 The torsion scale space image of the bottle-opener 86 Figure 6.2.7 A space curve depicting an armchair 87 Figure 6.2.8 The armchair during evolution 88 Figure 6.2.9 The torsion scale space image of the armchair 89 Figure 6.2.10 The armchair with random noise 90 Figure 6.2.11 The torsion scale space image of the armchair with noise 91 Figure 6.2.12 The renormalized torsion scale space image of armchair with noise 92 Figure 6.2.13 The TSS image of armchair with noise superimposed on the TSS image of armchair 93 Figure 6.2.14 The armchair with severe random noise 94 Figure 6.2.15 The torsion scale space image of armchair with severe noise 95 Figure 6.2.16 The resampled torsion scale space image of the armchair 96 Figure 6.2.17 The resampled torsion scale space image of armchair with severe noise 97 Figure 6.2.18 The resampled TSS image of armchair with severe noise superimposed on the resampled TSS image of armchair 98 Figure 6.3.1 A planar curve made up of straight line segments 102 Figure 6.3.2 The curve of figure 6.3.1 with added random noise 103 Figure 6.3.3 The curvature scale space image of the curve of figure 6.3.1 104 Figure 6.3.4 The curvature scale space image of the curve of figure 6.3.2 105 Figure 6.3.5 The CSS image shown in figure 6.3.3 superimposed on the CSS image shown in figure 6.3.4 106 vii L i s t o f T a b l e s Table 6.1.1 Comparison of regular, renormalized and resampled curva-ture scale space images 72 Table A . l Moment-pairs in equations (A.2) and (A.3) 128 Table B . l Moment-triples with M'Q' 150 Table B.2 Moment-triples with M1' 150 Table B.3 Moment-triples with M1' 151 Table B.4 Moment-triples with M\ 151 Table B.5 Moment-triples with M1' 151 Table B.6 Moment-triples with 151 Table B.7 Moment-triples with AfJ7 151 viii A c k n o w l e d g m e n t s I am specially grateful to Alan Mackworth, my thesis supervisor, who con-tributed significantly to the development of this thesis. That contribution ranged from specific research results to general guidelines and ideas about how to proceed from a specific point. His enthusiasm, approachability and understand-ing helped produce work that I feel quite proud of. I am also grateful to David Kirkpatrick, Peter Lawrence, Jim Little and David Lowe, members of my' supervisory committee, and to Bob Woodham for discussions and for offering criticisms of earlier drafts of my thesis which helped improve both its quality and the presentation of its results. Tom Hurd of the Math department helped me gain further insight into the mathematical aspects of the problems I encountered. Alex Kean, Jane Mulligan, Marc Romanycia, and Ying Zhang listened to various aspects of my work at our group meetings and provided helpful comments. I have no doubt that without the strong and continued support from my parents, I would not have been able to complete this work as it stands. Their love outlasted the dark clouds. I owe much to them and so does this thesis. Roxana has only recently entered my life but has already added consider-ably to it in special ways. She too, has left her mark on this work. 1 C h a p t e r 1 : I n t r o d u c t i o n Computer Vision is an area within the field of Artificial Intelligence which aims to develop techniques for analysis and interpretation of images. Those images may depict two- or three-dimensional real or synthetic objects. An impor-tant area of research within Computer Vision is the problem of shape representa-tion. This thesis considers the problem of representing the shapes of two-dimensional or planar and three-dimensional or space curves. A planar or a space curve is a set of points whose position vectors are the values of a continuous vector-valued function [Goetz 1970]. A planar curve can be represented by the parametric vector equation r(u) = (x(u),y(u)) and a space curve can be represented by r ( t t ) = (x(u),y(u),z(u)) where coordinate functions x(u), y(u) and z(u) are components of T(U) and u <E [a,b] is the parametrization variable. Note that a planar or space curve as defined above is connected and has no branches. A note on the title of this thesis is appropriate. The title speaks of a "theory of multi-scale, curvature and torsion based shape representation for planar and space curves" rather than a "multi-scale, curvature and torsion based shape representation technique for planar and space curves." The word theory was chosen to indicate the approach used by the author in proposing a shape representation technique in this thesis. That approach is to propose and motivate a number of criteria that a general purpose shape representation technique should satisfy. Then shape representations were developed and evaluated according to those criteria. The evaluation shows that the representations satisfy nearly all of the proposed criteria. The properties of the representations were also studied for-mally and in detail in order to understand their possible behaviours. The result is 2 a number of theorems which clearly describe properties of the representations under conditions specified by the theorems. It is believed that the approach taken justifies the use of the term theory. 1.1. C r i t e r i a for shape representation In the following, when two planar or space curves are described as having the same shape, there exists a transformation consisting of uniform scaling, rota-tion and translation which will cause one of those curves to overlap the other. We believe that it is important for a general-purpose shape representation to satisfy the following criteria: Invariance: if two curves have the same shape, they should also have the same representation. Uniqueness: if two curves do not have the same shape, they should have different representations. Stability: if two curves have a small shape difference, their representations should also have a small difference and if two representations have a small difference, the curves they represent should also have a small shape difference. The importance of the invariance criterion is that it guarantees that all curves with the same shape will have the same representation. It will therefore be possible to conclude that two curves have different shapes by observing that they have different representations. Without the invariance criterion, two curves with the same shape may have different representations. The uniqueness criterion is important since it guarantees that two curves with different shapes will have different representations. It will therefore be possi-ble to conclude that two curves have the same shape by observing that they have the same representation. Without the uniqueness criterion, two curves with different shapes may have the same representation. The significance of the stability criterion is that it guarantees that a small change in the shape of a curve will not cause a large change in its representation and a small difference between two representations does not indicate a large shape difference between the curves they represent. As a result, when two representations are close, the curves they represent are close in shape and when two representations are not close, the curves they represent are not close in shape. When this criterion is satisfied, the representation can be considered to be stable with respect to noise. One way to measure the shape difference between two planar or space curves is the Hausdorf distance [Hong & Tan 1988]. 3 A useful shape representation in computational vision should make accu-rate and reliable recognition of a shape possible. Therefore it is useful for a shape representation to satisfy a number of additional properties in order to become suitable for shape recognition tasks in computer vision. The following is a list of such criteria. Note that similar criteria have been proposed in [Nishihara 1981], [Mokhtarian & Mackworth 1986] and [Haralick et al. 1989]. Efficiency: The representation should be efficient to compute and store. This is important since it may be necessary for an object recognition system to per-form real-time recognition. By efficient we mean that the computational com-plexity should be a low-order polynomial in time and space (and in the number of processors if a parallel computing architecture is used) as a function of the size of the input curve. Ease of implementation: If two or more competing representations exist, it is advantageous to choose one of those representations such that the implementa-tion of the computer program which computes that representation requires the least time spent on programming and debugging. Computation of shape properties: It may be useful to be able to determine properties of the shape of a curve using its representation. For example, if a curve has a symmetric shape, it may be desirable to be able to determine that fact from its representation (the symmetry criterion). Furthermore, if the shape of a whole curve or part of a curve is the same as the shape of part of another curve, it may be useful to be able to determine that relationship using their representations (the part/whole criterion). 1.2. Contents of thesis The following is a description of the contents of the remaining chapters of this thesis: Chapter 2 reviews the computer vision literature in the area of shape representa-tion which is relevant to planar and space curves. A comprehensive survey of techniques for representation of shapes of planar curves is given and ways to gen-eralize each technique to apply to space curves are described. Each technique is then evaluated according to the criteria proposed in this chapter. Chapters 3 and 4 propose a novel theory of multi-scale shape representation for planar and space curves. Chapter 3 introduces a multi-scale, curvature based theory of shape representation for planar curves. Three variations of the represen-tation have been developed, each most suitable for particular applications. A number of theorems provide a sound theoretical foundation for the 4 representation. Chapter 4 introduces a multi-scale, torsion based theory of shape representation for space curves. Again three variations of the representation are described. A number of parallel theorems provide a similarly sound theoretical foundation for the representation. Chapter 5 discusses a number of issues which arise when implementing the curva-ture and torsion scale space representations of planar and space curves and gives algorithms to compute various curvature and torsion scale space representations proposed in chapters 3 and 4. It also presents a complexity analysis of each of those algorithms. Chapter 6 provides a number of examples of curvature scale space representations of planar curves and torsion scale space representations of space curves. It also provides examples of curves distorted by uniform and non-uniform noise and its effect on the representations of those curves. This chapter also includes a discus-sion of the significance of the theorems of chapters 3 and 4 and an evaluation of the curvature and torsion scale space representations according to the criteria set forth in chapter 1. Chapter 7 presents a summary and the conclusions of this thesis. It also proposes avenues of further research on multi-scale geometry-based shape representation techniques. Appendix A contains the proofs of the theorems of chapter 3 and appendix B contains the proofs of the theorems of chapter 4. 5 C h a p t e r 2 : S u r v e y o f L i t e r a t u r e This chapter contains a comprehensive survey of representation techniques for the shapes of planar and space curves. Each technique is described and a pos-sible way to generalize it to apply to space curves is explained. The reason is that almost all three-dimensional shape representation techniques proposed in com-puter vision have been concerned with surfaces but not curves. An evaluation of each technique according to the criteria proposed in chapter 1 is also presented. By default, each technique satisfies all criteria of chapter 1 except the ones pointed out following the description of that technique. It should be noted that any of the techniques listed below may be quite suitable for special-purpose shape representation and recognition tasks. Therefore failure to satisfy one or more of the criteria listed in chapter 1 does not imply that a particular shape representation should not be used under any cir-cumstances. The criteria listed in chapter 1 have been proposed for a general-purpose shape representation technique independent of any particular applica-tions. Furthermore, note that some of the representations were not originally pro-posed for shape matching applications and therefore invariance, stability and other issues were not a major concern. It may well be possible to deal with some of these issues through, for example, the use of normalization techniques. a . Hough transform: Has been used to detect lines [Hough 1962], circles [Duda & Hart 1972] and arbitrary shapes [Ballard 1981]. Edge elements in the image vote for the parameters of the objects of which they are parts. The votes are accumulated in a parameter space. The peaks of the parameter space then indicate the parameters of the objects searched for. In theory, the Hough transform can be generalized to space curves by increasing the dimensions of the parameter space. However, the parameters which define an object change when it undergoes rotation, uniform scaling or translation therefore the invari-ance criterion is not satisfied. 6 b. Chain encoding [Freeman 1974, McKee &; Aggarwal 1977, Gallus & Neurath 1970]: The curve is approximated using connected line segments which lie on a grid. This method can be generalized to space curves by using a three-dimensional instead of a two-dimensional grid. Note that this technique was originally used to encode contour data but was later used for recognition as well. This method does not satisfy the invariance criterion since the approxi-mating chain code rotates, scales and moves as the original curve rotates, scales and moves. The uniqueness criterion is not fully satisfied either since the mapping of a curve to its chain code involves loss of information. The degree of information loss depends on the resolution of the approximating grid. c. Medial axis transform [Blum 1973, Marr 1977]: The medial axis transform com-putes the skeleton of a two-dimensional object by a thinning algorithm that preserves connectivity of regions. This method can be generalized to space curves by using a three-dimensional thinning algorithm. Let S be the set of boundary points of a region. For each point P in that region, find its closest neighbors on the region boundary. If more than one boundary point is at a minimum distance from P, then P is on the skeleton of the region. This method does not satisfy the invariance criterion since the skeleton of an object rotates, scales and moves as the original curve rotates, scales and moves. It also fails to satisfy the stability criterion since a small change in the shape of the object could result in a significant change in its representation. d. Quad trees [Samet 1980, Schneier 1979]: A spatial occupancy array is first computed for a region on a raster device by assigning the value 1 to any array element which is in the region and value 0 otherwise. The quad tree can then be thought of as an intermediate pyramid representation of the spatial occu-pancy array. Each pixel in images above the lowest level has one of three values: black, white or gray. A pixel in an upper level is black or white if all its corresponding pixels in the next lower level are black or white respectively. If some of the lower level pixels are black and others are white, the corresponding pixel in the higher level is gray. This method is area-based and can not be applied to space curves. Note that Quad trees were proposed mainly for use in computer graphics and image processing. Quad trees do not satisfy the invariance criterion since shape-preserving transformations of the object change the structure of the representation. They also do not satisfy the stability criterion since making a small change to the spatial occupancy array can cause a dramatic change in the resulting quad tree. e. Shape factors and quantitative measurements [Danielsson 1978, Brown 1979]: The shape of the object is described using one or more global quantitative measurements of the object such as area, perimeter, compactness (perimeter2/area) and eccentricity (ratio of the principal axes of inertia). Some, of these measurements, such as perimeter, can also be computed for space 7 curves. The uniqueness criterion is not satisfied by this class of representations since there is a drastic reduction in data. However, they may be useful when the global measurements are sufficient to distinguish among a class of objects. f. Slope density function [Nahin 1974]: Let <f> be the angle made between a fixed vector and a tangent to a curve. The slope density function is the histogram or frequency distribution of <f> collected over the entire length of the curve. Note that the SDF is flat for a circle or any curve with a rnonotonically varying <j>. This method can be applied to space curves as well. The uniqueness criterion is not satisfied by this method since the mapping involves a loss of informa-tion. The stability criterion may also be violated if the input curve is noisy. However, smoothing the curve may remedy this problem. g. Polyline or polygonal approximation [Pavlidis 1972, 1973, 1975, 1977, Pavlidis & Horowitz 1974, Horowitz & Pavlidis 1976, Tomek 1974, Sklansky & Kibler 1976, Turner 1974, Roberts 1965, Shirai 1975]: A polyline or polygon (when the curve to be approximated is closed) is used to approximate the curve to any desired level of accuracy. The problem is to find corners or breakpoints that yield the "best" polyline or polygon. Various criteria have been used to solve that problem which can be characterized by the concepts of splitting and merging. In a merging algorithm, points along a curve are accepted into a linear segment as long as they fit sufficiently well. A concept of scale can be introduced by adjusting the number of breakpoints or the total approximation error allowed. This method can easily be applied to space curves by using three-dimensional polylines or polygons. This class of representations does not satisfy the invariance criterion since the approximating polyline or polygon rotates, scales and moves with the curve. The uniqueness criterion is satisfied well when the input curve consists mainly of segments with little or no curva-ture. Otherwise, the approximation error depends on the size (measured in terms of the number of vertices) of the approximating polygon. h. Strip trees [Davis 1977, Ballard 1981]: A strip tree is a set of approximating polygons or polylines ordered such that each polygon or polyline approximates the curve with less approximation error than the previous polygon or polyline. Initially, an open curve is approximated by a line segment which joins its end-points and a closed curve is approximated by a line segment joining two points on the curve that are furthest away. At each level of refinement, a point on a curve segment that is furthest away from its approximating line segment is joined to the endpoints of that line segment to obtain better approximations. This method can be generalized to space curves by using three-dimensional polygons or polylines to approximate the curves. Strip trees do not satisfy the invariance criterion since they move, rotate and scale with the curve. They also do not satisfy the stability criterion since a small change in the shape of the curve can result in a large change in its representation. 8 i. Splines [deBoor 1978, Barnhill & Riesenfeld 1974, Ballard & Brown 1982]: The curve is represented using a set of analytic and smooth curves. This method can also be generalized to space curves by making use of three-dimensional splines. Note that splines have been used primarily in computer graphics for object modelling. The invariance criterion is not satisfied since shape-preserving transformations of the curve and the choice of knot points for the approximating splines change the parameters of those splines. The uniqueness criterion is partially satisfied. The approximation error depends on the degree of approximating splines. j. Smoothing splines [Shahraray & Anderson 1989]: The curve is parametrized to obtain two coordinate functions. Cross-validated regularization [Wahba 1977] is then used to arrive at an "optimal" smoothing of each coordinate function. The smoothed functions together define a new smooth curve. This technique can also be generalized to space curves: three coordinate functions instead of two are obtained by parametrizing the curve. The invariance criterion is not satisfied since shape-preserving transformations of the curve also change the smoothing splines. k. Fourier descriptors [Persoon & Fu 1974, Schwartz et al. 1983, Richard & Hemami 1974]: The curve is represented by the coefficients of the Fourier expansion of a parametric representation of the curve. This method can be applied to both two-dimensional and three-dimensional curves. The invariance criterion is not satisfied by this class since shape-preserving transformations of the curve will change its Fourier coefficients. 1. Curvature primal sketch [Asada & Brady 1986]: The curve is approximated using a library of well-defined, analytic curves. Then the curvature function of the approximating curve is computed and convolved with a Gaussian of vary-ing standard deviation. This technique can be generalized to space curves by computing either the curvature or the torsion function of those curves. This method may fail to satisfy the stability criterion. If the original curve is noisy, then computing its curvature function is an error-prone process and the com-puted representation may change significantly. m. Scale space blackboard [Saund 1989]: A scale space blackboard is constructed by adding a notion of scale to Marr's [1976] Primal Sketch. Two types of grouping operations are introduced: (a) Aggregation of fine scale primitive-edge tokens into coarser scale edge maps, and (b) pairwise grouping of sym-metrically placed primitive-edges into primitive-partial-region type tokens denoting curved-contour, primitive-corner, and bar events. It is possible to compute a scale space blackboard for space curves by introducing grouping operations for three-dimensional edges. However, the method fails to satisfy the invariance criterion since the primitive-edges move, rotate and scale as the 9 curve to be represented moves, rotates and scales. It also does not fully satisfy the uniqueness criterion since the process of approximating curved objects using straight line segments involves some loss of information. n. Extended circular image [Horn & Weldon 1986]: This representation is the two-dimensional equivalent of the extended Gaussian image. In the extended circular image, one is given the radius of curvature as a function of normal direction. This technique can also be generalized to space curves. However, the resulting representation will be spherical rather than circular since the normal vectors will not all lie in the same plane. The invariance criterion is not fully satisfied by this method since the representation rotates as the original curve rotates. The uniqueness criterion is satisfied only for the class of simple and convex curves. o. Curve signatures [O'Rourke & Washington 1985]: The signature of a planar curve r in class Cj is a function s(w) where w is the normalized arc length parameter on T. For each value wQ of w, s(w0) is defined to be the total length of those segments of C which are to the left of the tangent vector to C at point P=C(w0). This technique is also generalizable to space curves. The stability criterion is not satisfied by curve signatures since noise on the curve can significantly alter the representation. p. Volumetric diffusion [Koenderink & van Doorn 1986]: A geometrical object is defined by way of its "characteristic function" x ( r ) which equals unity when the point r belongs to the object and zero otherwise. The object is then blurred by requiring that its characteristic function satisfy the diffusion equa-tion. The boundary of each blurred object is defined by the equation x(r) = 0.5. Alternatively, the boundary can be extracted by applying a Lapla-cian operator to the blurred function. This method does not generalize to space curves. The invariance criterion is not satisfied by this method since shape-preserving transformations of the object also affect the blurred objects com-puted by this method. This problem may be remedied by locating the curva-ture zero-crossing points of those curves and mapping those points to a curva-ture scale space representation as described in chapter 3. The stability cri-terion may also be violated since a small change to the shape of an object could result in a significant change in its computed deformations. For exam-ple, the contour of a dumbbell may remain a connected curve or may split into two disconnected contours when the thickness of its neck varies by an infinitesimal amount [Babaud et al. 1986]. q. Scale space image [Witkin 1983]: The scale space image was in fact introduced as a representation for one-dimensional signals and functions. The input func-tion f(x) is convolved with a filter approximating the second derivative of the Gaussian. The standard deviation a of the Gaussian is varied from a small to a 10 large value and the zero-crossing points of the convolved functions are located and marked in the x-o space. A scale space volume can also be computed for a 2D function or image f(x,y) by convolving it with the Laplacian of a 2D Gaus-sian function as the standard deviation a varies from a small to a large value and marking the zero-crossing points in the x-y-a space. r. Reactive and diffusive deformations of shape [Kimia et al. 1989]: Chapters 3 and 4 will introduce multi-scale theories of shape representation for planar and space curves which are based on computing specific deformations of the curves to be represented. Kimia, Tannenbaum and Zucker [1989] have proposed some-what different deformations of shape. Let 7 be the input curve and let ff* be the normal vector. The deformation of 7 is defined as: = /?(«) If where is a function of curvature and t is time and determines the amount of deformation. This method is somewhat similar to the technique described in this thesis and can also be applied to space curves. However, it fails to satisfy the stability criterion since a small change to the shape of an object could result in a significant change in its computed deformations. For example, the contour of a dumbbell may remain a connected curve or may split into two disconnected contours when the thickness of its neck varies by an infinitesimal amount. The method also fails to satisfy the invariance criterion since defor-mations of a curve are not invariant with respect to shape-preserving transfor-mations of that curve. This shortcoming may be remedied by locating the cur-vature zero-crossing points of those curves and mapping those points to a cur-vature scale space representation as described in chapter 3. As demonstrated, each of the existing shape representation techniques for planar and space curves in computer vision fails to satisfy one or more of the cri-teria considered useful for a general-purpose representation. Chapters 3 and 4 present theories of shape representation for planar and space curves which attempt to meet the criteria for shape representations proposed in chapter 1. An evaluation of those representations is presented in chapter 6. 11 Chapter 3: A Theory of Multi-Scale Shape Representation for Planar Curves Multi-scale approaches to various computer vision problems have been investigated by many vision researchers recently. Multi-scale analyses of those problems have proven more fruitful than attempts at solving those problems at a single scale. A multi-scale approach allows one to obtain an initial approximate solution at a stable higher scale. Such a solution can be obtained efficiently by searching a reduced search space. That initial solution can then be used to guide one through lower scales in order to obtain more accurate solutions at any desired level of accuracy. Examples are signal matching using scale space [Witkin et al. 1987], multi-resolution computation of surfaces [Terzopoulos 1984], organi-zation of image curves at multiple scales [Lowe 1988], hierarchical models of three-dimensional objects [Koenderink & van Doorn 1986], hierarchical surface interpolation [Szeliski 1989] and solving the depth interpolation problem using a multi-grid approach [Choi & Render 1988]. Similarly, multi-scale approaches to the shape representation problem have been proposed in the vision literature. Some examples can be found among the shape representation techniques reviewed in chapter 2. Using a multi-scale representation of an object, a matching algorithm can obtain a quick, approxi-mate match at a coarse scale where the shapes of the objects are relatively simple and then use that initial match to guide the search through the finer scales and obtain more accurate matches. A number of multi-scale shape representation techniques can be identified among methods reviewed in chapter 2. However, as it was pointed out in that chapter, each one fails to satisfy some of the criteria listed in chapter 1. This 12 chapter introduces a multi-scale shape representation which satisfies nearly all the criteria proposed in chapter 1. A multi-scale representation for one-dimensional functions was first pro-posed by Stansfield [1980] and later developed by Witkin [1983]. The function j{x) is convolved with a Gaussian function as its variance a2 varies from a small to a large value. The zero-crossings of the second derivative of each convolved function are extracted and marked in the x-a plane. The result is the scale space image of the function. The curvature scale space image was introduced in [Mokhtarian & Mack-worth 1986] as a new shape representation for planar curves. The representation is computed by convolving a path-based parametric representation of the curve with a Gaussian function, as the standard deviation of the Gaussian varies from a small to a large value, and extracting the curvature zero-crossing points of the resulting curves. The representation is invariant under rotation, uniform scaling and translation of the curve. This and a number of other properties makes it suit-able for recognizing a noisy curve of arbitrary shape at any scale or orientation. The process of describing a curve at increasing levels of abstraction is referred to as the evolution of that curve. The evolution of a planar curve and the curvature scale space image are described in detail in section 3.1. Mackworth and Mokhtarian [1988] introduced a modification of the curva-ture scale space image referred to as the renormalized curvature scale space image. This representation is computed in a similar fashion but the curve is reparametrized by arc length after convolution. As was demonstrated in [Mack-worth & Mokhtarian 1988], the renormalized curvature scale space image is more suitable for recognizing a curve with non-uniform noise added to it. However, the renormalized curvature scale space image is more computationally intensive than the regular curvature scale space image. The renormalized curvature scale space image is described in detail in section 3.2. The resampled curvature scale space image is a substantial refinement of the curvature scale space which is based on the concept of arc length evolution. It is shown that the resampled curvature scale space image is more suitable than the renormalized curvature scale space image for recognition of curves with added non-uniform noise or when local shape differences exist. The comparison table in chapter 6 lists the advantages and disadvantages of each representation. The arc length evolution of a planar curve and the resampled curvature scale space image are described in detail in section 3.3. Section 3.4 contains a number of theorems which demonstrate a number of global and local properties of planar curves during evolution. Together, these theorems constitute a sound theoretical foundation for the representation tech-nique presented in this chapter. 1 3 3.1. T h e curvature scale space image The following is a review of those concepts of differential geometry of planar curves which are relevant to the theory presented in this chapter. A planar curve is a set of points whose position vectors are the values of a continuous vector-valued function. It can be represented by the parametric vector equation r(u) = (x(u),y(u)) (3.1-1) The function r(it) is a parametric representation of the curve and u € [a,b] is the parametrization variable. A planar curve has an infinite number of distinct parametric representations. A parametric representation in which the parameter is the arc length s is called a natural parametrization of the curve. A natural parametrization can be computed from an arbitrary parametrization using the following equation s = f\r(v)\dv. (3.1.2) o where . represents the derivative, i.e. . , x dr For any parametrization f(u) = (x(u), y(u)) \r(u)\ = (x2 + y2)1/2 t ( U ) = W = ^ (x2 + yy/2\x2 + y Y 2 ) and = ^ (# !^-,2W2 V -2 , ,^1/2) [x + y ) 1 (x + y ) ' where t(u) and n(u) are the tangent and normal vectors at u respectively. For any planar curve the vectors t(u) and n(u) must satisfy the simplified Serret-Frenet vector equations [Goetz 1970]: t(s) = n(s) = -n(s)t(3) where K(S) is the curvature of the curve at 3 and is defined as the limit of the ratio of the angle (f> between t(s) and t(s+h) to h as /i—>0. That is 14 K(U) = K(S) = lim^r-. />-*o h A straight line has zero curvature everywhere. A circle is an example of a closed curve with constant curvature. An ellipse is another closed curve with positive (but not constant) curvature everywhere. Now observe that: */ s dt dt du t(s) = — = . ds du ds Therefore dt ds , •, — — = — — / c n = | r | r c n . du du Hence t . n 1*1 ' Differentiating the expression for t(u), we obtain: i(u\ = ( -y(*y-*v) x(xy-xy) \ ^ ' V / -2 , -2N3/2 ' / -2 . -2N3/2 / ' [x + y ) 1 (x + y ) / It now follows that: , v = i(u)y\u) - y(u)x(u) {x{uf + y{uff'2 ' Therefore it is possible to compute the curvature of a planar curve from its parametric representation. Two special cases of the parametrization, of interest here, yield simplifications of these formulas. If we have a natural path representation with s, the arc length parameter, ranging over [0,i] then: | f ( 3 ) | = | (x(s\ y(s)) | = (x\s)+y\s))^ = 1 To see this, note that it follows from equation (3.1.2) that: ds Therefore Furthermore, ^ \r(u)\ t(-) = M) and Note also 15 t ( » = (x(s), y(s)) n ( » = ( -T /0) , x(s)) • K(S) = t(s)-n(.s) K(S) = x(s)yls) - x(s)y(s). « 2 W = | t ( 3 ) | 2 « 2 ( 3 ) = x\s)+y\s). If the parameter is a linear rescaling of the arc length ranging over [0,1] , the normalized path length parameter w, then s W = T |r(«,)| = I n(w) - ^r(-y(w), Kw)) K(W) = - x(w)y(w)) and * 2 W = ^ ( i ' V ) + i i 2 W ) . This concludes the review of differential geometry of planar curves. Given a planar curve r = {( i(w) ) ! )(t D ))| i i )6[o , i ] } where w is the normalized arc length parameter, an evolved version of that curve is denned by r„ = {(X(u,o), Y[u,*))\u e [0 ,1]} where X(u,o) = x(u) ®g(u,a) Y(u,a) = y(u) ®g(u,a) 16 and 0 represents the convolution operator. Function g(u,o) denotes a Gaussian of width a [Marr & Hildreth 1980] and is defined by . . 1 O/T2 g(u,a) = —7==e . As it will become clear in appendices A and B, the use of the Gaussian filter results in a number of important properties of the representations which other smoothing filters do not provide. Functions X(u,o) and Y(u,o) are given expli-citly by X(u,(x) = f x(v) \—e 2 < t 2 dv J CTV27T -oo and Y(u,o) = f y{v)—^e 2°* dv. -oo The curvature of Ta is given by Xu(u,o)Yuu(u,o-) - Xuu(u,o)Yu(u,o) K(U,O) = where (Xu(u,a)2 + Yu(u,o)2f2 and du Yu(u,a) = y(u) ®gu(u,o) Yuu(w) = M ®9uu(u>°~)-The process of generating the ordered sequence of curves {rjcr^O} is referred to as the evolution of T. Note that when a planar curve evolves according to the process defined above, its total arc length shrinks. The amount of shrinkage is directly propor-tional to the value of a. In certain applications, this may be an undesirable feature. For example, the evolution process defined above may be used to smooth edges extracted from an image by an edge detector. However, it may be advanta-geous to have the smoothed edges close to the physical location of the original edges. This can be accomplished by estimating the amount of movement at each 17 point on the smoothed edges and adding a vector to the location vector of that point to compensate for that movement [Lowe 1988]. The result is a smoothed curve which is physically close to the original curve. The function denned implicitly by K(U,CT) = 0 is the curvature scale space image of T [Mokhtarian & Mackworth 1986]. 3.2, The renormalized curvature scale space image Mackworth and Mokhtarian [1988] observed that although w is the nor-malized arc length parameter on the original curve T, the parameter u is not, in general, the normalized arc length parameter on the evolved curve Ta. In other words, arc length does not shrink uniformly everywhere on the curve during evo-lution. To correct this problem, Mackworth and Mokhtarian [1988] proposed the renormalized curvature scale space image. Let R(u,a) = (X(u,cr), Y(u,o)) and w = §a(u) where u f\Rv(v,*)\dv * » = 1 • J\Rv(v,a)\dv o Now define X(w,a) = X($-\w),a) Y(w,a) = Y($-\w),o). (3.2.1) That is, each evolved curve is reparametrized by its normalized arc length parameter w. Notice that *,(0) = 0 and 18 = > 0 at non-singular points. du 1 f\Rv(v,a)\dv o Also $0(u) = u. $<,.(«) deviates from the identity function $o-(u) = u only to the extent to which the scale-related statistics deviate from stationarity along the original curve. Once we have changed parameters according to equations (3.2.1), the cur-vature of the curve with the normalized path length parameter is given by K(w,a) = -^-[Xw(w,a)Yww(w,a) - Xww(w,a)Yw(w,a)}. The function defined implicitly by K(W,(J) — 0 is the renormalized curvature scale space image of T. 3.3. T h e resampled curva ture scale space image Note that as a planar curve evolves according to the process defined in sec-tion 3.1, the parametrization of its coordinate functions x(u) and y(u) does not change. In other words, the function mapping values of the parameter u of the original coordinate functions x(u) and y(u) to the values of the parameter u of the smoothed coordinate functions X(u,a) and Y(u,a) is the identity function. For both theoretical and practical reasons, it is interesting to generalize the definition of evolution so that the mapping function can be different from the identity function. Again let T be defined by: T = {(x(w),y(w))\w e [0,1]}. The generalized evolution which maps T to is now defined by: where r < r = {(X(w,a),Y(wr^))|wre[o,i]} X(W,a) = x(W)®g(W,a) and Y(W,o) = y(W)®g(W,o-). Note that 19 W= W(w,a) and W(w,o0) where cr0 is any value of <r, is a continuous and monotonic function of w. This condition is necessary to ensure physical plausibility since W is the parameter of the evolved curve Tff. An important case is when W always remains the arc length parameter as the curve evolves. When this criterion is satisfied, the evolution of T is referred to as arc length evolution. An explicit formula for W can be derived [Gage & Hamil-ton 1986]. Let R(W,o) = (X(W,o-),Y(W,o-)). The Frenet equations for a planar curve are given by dt | dR i dn , dR , , • Ih = = ~'"9T' . ' c Let t = <T 2 /2. Observe that •dt" dul) ~ dt{ du ' du ) ~ ' 1 du ' dudt]' Note that and dR = {dR, du ~ 1 du1 dR ——- = K n dt since the Gaussian function satisfies the heat equation. It follows that | ( i f i2) = 2 < i f r i ' - 2 ( l f r | t ( t n - ' f ^ 2 t ) ) = - 2 | f | 2 " 2 Therefore A c V dt] du]-~Zl du1 or 20 d , dR , _ ; 3R , 2 "r5F 1*a7 l _" l"^T l' c-Let L denote the length of the curve. Now observe that L L 1 —— = / -r-|——I du = - / I ——\n2du = - IK2 Aw. dt {dt{ du< JQl du1 Q Since the value wQ of the normalized arc length parameter to at a point P meas-ures the length of the curve from the starting point to point P, it follows that W dt J0 and therefore tW W(w,t) = -JJK2(W,t)dWdt + w. (3.3.1) 0 0 Note that W(w,0) = w. The function denned implicitly by K( W,a) = 0 is the resampled curvature scale space of T. Since the function K( W,t) in (3.3.1) is unknown, W(w,t) can not be com-puted directly from (3.3.1). However, the resampled curvature scale space can be computed in a simple way. A Gaussian filter based on a small value of the stan-dard deviation is computed. The curve T is parametrized by the normalized arc length parameter and convolved with the filter. The resulting curve is reparametrized by the normalized arc length parameter and convolved again with the same filter. This process is repeated until the curve is convex and no longer has any curvature zero-crossing points. The curvature zero-crossings of each curve are marked in the resampled curvature scale space image. Note that the standard deviation of the Gaussian chosen above should be small enough so that the deviation from arc length parametrization after each iteration is negligible. Then the entire process can be considered to model arc length evolution. 3.4. Evolution and arc length evolution properties of planar curves This section contains a number of important results on evolution and arc length evolution of planar curves as defined in sections 3.1 and 3.3. The proofs can be found in appendix A. 21 The first five theorems express a number of global properties of planar curves during evolution and arc length evolution. Theorem 3.4.1. Evolution and arc length evolution of a planar curve are invari-ant under the shape preserving transformations (rotation, uniform scaling and translation) of the curve. Theorem 3.4.2. A closed planar curve remains closed during its evolution and arc length evolution. Theorem 3.4.3. A connected planar curve remains connected during its evolu-tion and arc length evolution. Theorem 3.4.4. The center of mass of a planar curve does not move during evo-lution and arc length evolution of that curve. Theorem 3.4.5. Let T be a closed planar curve and let G be its convex hull. Every point on T remains in G during evolution and arc length evolution. Theorem 3.4.6 shows that the mapping from a planar curve to its curva-ture scale space image is an invertible one. Theorem 3.4.6. Let T be a planar curve in Cj. The derivatives at a single point on one curvature zero-crossing contour in the regular, renormalized or resampled curvature scale space image of V determines T uniquely up to uniform scaling, rotation and translation (except on a set of measure zero). Theorem 3.4.7 states that under certain conditions, new curvature zero-crossing points are not created during evolution and arc length evolution of planar curves. Theorem 3.4.7. Let T be a planar curve in C 2 . If all evolved and arc length evolved curves are in C 2 , then all extrema of contours in the regular, renor-malized and resampled curvature scale space images of V are maxima. Theorem 3.4.8 locally characterizes the behaviour of planar curves during evolution and arc length evolution just before the creation of a cusp point. Theorem 3.4.8. Let V = (x(u),y(u)) be a planar curve in C± and let x(y) and y(u) be polynomial functions of u. Let Ta be an evolved or arc length evolved ver-sion of T with a cusp point at u0. There is a <5>0 such that intersects itself in a neighborhood of point uQ. The following theorem holds only for arc length evolution. 22 Theorem 3.4.9. Simple curves remain simple during arc length evolution. Theorem 3.4.10 locally characterizes the behaviour of a planar curve dur-ing evolution and arc length evolution just after the creation of a cusp point. Theorem 3.4.10: Let T = (x(u),y(u)) be a planar curve in C\ and let x(u) and y(u) be polynomial functions of u. Let Ta be an evolved or arc length evolved ver-sion of T with a cusp point at uQ. There is a «5>0 such that T^+g has two new curvature zero-crossings in a neighborhood of w0. 23 Chapter 4: A Theory of Multi-Scale Shape Representation for Space Curves Almost all work done in computer vision on shape representation has focused either on planar curves and two-dimensional shapes, as shown in chapter 2, or on three-dimensional objects and surfaces [Bentley 1975, Voelcker Sz Requicha 1977, O'Rourke & Badler 1979, Jackins & Tanimoto 1980, Requicha 1980, Faugeras & Ponce 1983, Brady et al. 1985, Weiss 1985]. This chapter addresses the problem of describing the shape of three-dimensional curves. A space curve may be directly computed from an image [Watson & Shapiro 1982, Barnard & Pentland 1983]. It may also represent a surface reconstructed using stereo [Woodham 1984, Grimson 1985], "shape from" techniques [Ikeuchi & Horn 1981, Witkin 1981, Stevens 1982], or laser range finders [Faugeras et al. 1984], as described below. Why study the problem of representing the shape of space curves? Space curves are useful to study for the following reasons: a. Trajectories of objects in outer space and paths taken by atomic particles are space curves. Often, such an object or particle can be recognized by studying the shape of its path when subjected to specific forces. Trajectories of robot arms and robot vehicles are also space curves. b. Axes of generalized cones and cylinders [Agin & Binford 1973] are also space curves. A generalized cone or cylinder representation of a three-dimensional object can itself be efficiently represented by its axes. 24 c. Bounding contours of objects that consist of flat or nearly flat surfaces are rich in information and can be used to represent the object effectively and economi-cally. These bounding contours are space curves and can be extracted by thin-ning the object into lines and planes. An attempt to describe such objects using three-dimensional surfaces may not add much useful information but can significantly increase storage and processing requirements. This chapter proposes a multi-scale theory of shape representation for space curves. This theory is a generalization of the multi-scale theory of shape representation for planar curves which was proposed in chapter 3. Section 4.1 develops the concept of curvature and torsion scale space representation for space curves. This representation was first proposed in [Mokhtarian 1988a]. Section 4.2 introduces a modification of the representation proposed in section 4.1 referred to as the renormalized curvature and torsion scale space representation. Section 4.3 proposes a significant further refinement of the earlier representations referred to as the resampled curvature and torsion scale space representations. Section 4.4 presents a number of important theoretical results on the evolution properties of space curves. These results further understanding of the evolution process and constitute a sound theoretical foundation for the representation techniques pro-posed in this chapter. 4.1. The curvature and torsion scale space images This section introduces the parametric representation of space curves and describes the Frenet Trihedron for space curves. Curvature and torsion of a space curve are then defined and geometrical interpretations given to them. Next, it is shown how to compute curvature and torsion on a space curve at varying levels of detail. A multi-scale representation for a space curve which combines informa-tion about the curvature and torsion of the curve at varying levels of detail is then proposed. i. The parametric representation of a space curve The set of points of a space curve are the values of a continuous vector-valued function [Goetz 1970]: r = r(u) = (x(u), y(u), z(u)) (4.1.1) where x(u), y[u) and z(y) are the components of r(u) and u is a function of arc-length s of the curve, s is also called the natural parameter. The function r(u) or the triple of functions (x(u), y(u), z(u)) is called a parametric representation of the curve. ii. Frenet Trihedron and formulae for space curves Let P0 be a common point of a space curve and a plane and let P be a 25 variable point of the curve. Let h denote the arc length between P 0 and P and let dfr denote the distance of P from the plane. The curve and the plane are said to have a contact of order at least n [Goetz 1970] at P 0 if dh = 0(hn). The plane with the highest possible order of contact with the curve at P 0 1 S called the oscu-lating plane at P 0 . With every point P of a space curve of class C2 is associated an orthonor-mal triple of unit vectors: the tangent vector t, the principal normal vector n and the binormal vector b (Figure 4.1.1). The principal normal vector is the unit vec-tor normal to the curve at P which lies in the osculating plane. The binormal vector is the unit vector perpendicular to the osculating plane such that the three vectors t, n and b in that order form a positively oriented or a right-handed tri-ple. The plane containing t and n is the osculating plane. The plane containing n and b is the normal plane and the one containing b and t is the rectifying plane. Figure 4.1.1. The Frenet trihedron for a space curve 26 The derivatives of t, n and b with respect to the arc length parameter give us: dt dn , , , dh —— = /cn, — — = -/ct 4- rb, — — = -rn. ds ds ds These formulae are called the Frenet or the Serret-Frenet formulae. The coefficients K and r are called the curvature and torsion of the curve respectively. Curvature is the instantaneous rate of change of the tangent vector to the curve with respect to the arc length parameter. Curvature of a space curve has no sign. Torsion is the instantaneous rate of change of the binormal vector with respect to the arc length parameter. A sign is assigned to the absolute measure of torsion as following: Let point P correspond to value 5 of the arc length parameter and let point Q correspond to value s+h. Let line I be the intersection of the osculating planes at P and Q. Note that I is parallel to the vector h(s) x b(s-\-h) since b(s) and b(s+h) are perpendicular to the osculating planes at points P and Q respectively. Let w be a vector on line I which points into the same half-space determined by the normal plane into which the vector t(s) is pointing. If b(s), h(s+h) and w form a positively oriented or a right-handed triple, then torsion at point P has positive sign, otherwise it has negative sign. A planar curve has zero torsion everywhere. The helix is a space curve with constant torsion. To see this, note that the parametric representation of the helix is given by: x(u) = acosu y(u) = asini i z(u) = bu. Therefore x(u) = -asinu y(u) = acosu z(u) = b x\u) — -acosu 2/0) = -as'mu z(u) = 0 'x(u) = asinu v 0 ) : = -acosu z(u) = 0 A = absinu B = -ab cosu C= a 2 and = b  T ~ a2 + b2' Since the curve is represented in parametric form, in order to compute cur-vature and torsion at each point on the curve, we need to express those quanti-ties in terms of the derivatives of its coordinate functions x(), y() and z(). Note that as in chapter 3, . represents the derivative. 27 iii. Curvature In case of an arc-length parametrization, we have: «(*) = \r(s)\ = V(x)2 + (y)2 + (i') 2 Given an arbitrary parametrization of the curve: «(«) = |t,| = £ ( r ( t t)/|f(i»)|) |r(«)| |p(u)| _ |r(tt)xr(u)| \r(u)\3 In coordinate form K(U) = VA2 + B 2 + C 2 ((i) 2 + (y)2 + (z)2f2 where A = y z B -z X c = i y y z z X x y iv. Torsion We will first derive an expression for the torsion of a space curve with arc-length parametrization [Goetz 1970]. Multiplying both sides of the third Frenet formula by n results in r = -bsn = -(txn),n =.-(t,xn)n - (txnjn = tnns. Note that tnn 4 is the mixed product of vectors t, n and n3 and is equal to (txn)n^. We now make use of , . r(s) r(s) Ks N t = r(a), n = -r^f-, ns=—^--—r(s) K to obtain x y z x y z x y 'z r(s) r(3)r(s)  r ( » 2 " (x)2 + (y)2 + (z)2 In case of an arbitrary parametrization, we make use of: r(s) = r(u)-^-, r(s) = r ( + *(U)-J^, and 28 to obtain / >  _ f(u)*r*(u)r'(u) |r(u)[6 f(u)'r'(tt) r(tt) | f ( » | 6 '(f(u)xr(u)) 2 ~ (r(u)xr(u))2 In coordinate form x y z x y z x y 'z T = A1 + B2+ C where A , B and C are as before. v. Computing curvature and torsion at varying levels of detail In order to compute K and r at varying levels of detail of the curve T, functions x(u), y(u) and z(u) are convolved with a Gaussian kernel g(u,a) of width a: = —7^=e 2 a 2 • <TV2TT The convolved functions together define the evolved curve Ta. The convolution of a function f(u) and the Gaussian kernel is defined as: oo F(u,°-)=f(u)®9(%cr)= / / ( * ) — 4 — e 2<P iv. J ovzir Furthermore, it is known that du F(u,cr) = &nu,o) du2 du and du6 du These properties of convolution can be used to compute curvature and torsion on evolved versions of a space curve. Let X(u,o) = x(u) ®g(u,o) 29 Y(U,CT) = y(u) ®g(u,a) and Z(u,a) = z(u) ®g(u,cr). It follows that curvature on an evolved curve Tff is given by V D2 + E2 + F2  (X(u,cr)2 + Y(u,cr)2 + Z{u,a)2fl2 K = where D = E = and F = Y(u,a) Z(u,a) Y(u,cr) Z(U,CT) Z(U,<J) X(u,a) Z(u,a) X(u,a) X(u,a) Y(u,a) X(u,a) Y(u,cr) and torsion on evolved curve Ta is given by r = X(u,a) Y(u,a) ?(u,cr) &V.,CT) Y\u,a) Zlu,a) X (u,<7) Y(u,a) Z(u,cr) D2 + E2 + F2 where D, E and F are as before. vi. A multi-scale representation for space curves The curvature and torsion functions of a space curve specify that curve uniquely up to rotation and translation [Do Carmo 1976]. We therefore propose a representation for a space curve that consists of the curvature scale s-pace and torsion scale space images of the curve. This representation is a generalization of the curvature scale space representation proposed for planar curves in [Mokhtarian & Mackworth 1986]. The function defined implicitly by the level-crossings K(U,CT) = c is the curvature scale space image of T and the function defined implicitly by r(u,cr) = 0 is the torsion scale space image of T. 30 To compute the torsion scale space image of a space curve r = (x(u), y(u), z(u)), evolved curves Ta are computed as a varies from a small to a large value. The torsion zero-crossing points of each Ya are extracted and recorded in the u-a space. The smallest value of a used is slightly larger than zero and the largest value of a used in the smallest value of a that results in a Tg. with very few torsion zero-crossing points. The curvature scale space image of a space curve is constructed in a simi-lar fashion. The only difference is that level-crossings rather than zero-crossings are searched for. This is because the curvature of a space curve has only magni-tude and no sign. Some care should be given to choosing a suitable value for level c. If c is too large, the number of level-crossing points found on curves Ta drops to zero quickly as a increases and the resulting curvature scale space image will not be very rich and therefore not suitable for matching. If c is too small, the resulting curvature scale space image will contain excessive detail. The actual value used for c is the average of curvature values of points of Ya where a0 € [OjCrJ and at is the largest value of a used to compute the torsion scale space image of T. Using such a value ensures that the resulting curvature scale space image will be sufficiently rich for matching and will represent roughly the same range of values of a represented in the torsion scale space image of V. 4.2. T h e renormal ized c u r v a t u r e a n d tors ion scale space images Mackworth and Mokhtarian [1988] observed that although w is the nor-malized arc length parameter on the original curve T, the parameter u is not, in general, the normalized arc length parameter on the evolved curve Ta. To correct this problem, we propose the renormalized curvature and torsion scale space images. Let H(u,a) = (X(u,a), Y(u,o), Z(u,o~)) and w = $a(u) where u J]Rv(v>°~)\dv *„(«) = 1 • f\KM\dv o Now define 31 X(w,o) = X(*-\W),<T) Y(w,a) = Y(Z-\w),o) (4.2.1) Z(w,o) = Z($-\w),o). Functions X(w,cr), Y(w,a) and Z(w,o) defined by equations (4.2.1) define the renormalized version of each Ta. That is, each evolved curve is reparametrized by its normalized arc length parameter w. Notice that *„(0) = 0 and d$a(u) |R„ ( t t ,<7)| = > 0 at non-singular points. du 1 J]KM\dv o Also *o (« ) = «• $CT(u) deviates from the identity function $a(u) = u only to the extent to which the scale-related statistics deviate from stationarity along the original curve. The function defined implicitly by K(W,O~) = c is the renormalized curvature scale space image of T and the function defined implicitly by r{w,o) = 0 is the renormalized torsion scale space image of T. 4.3. T h e resampled curva ture a n d tors ion scale space images Note that as a space curve evolves according to the process defined in sec-tion B, the parametrization of its coordinate functions x(u), y(u) and z(u) does not change. In other words, the function mapping values of the parameter u of the original coordinate functions z(u), y(u) and z(u) to the values of the parame-ter u of the smoothed coordinate functions X(u,cr), Y(u,o) and Z(u,o) is the iden-tity function. For both theoretical and practical reasons, it is interesting to generalize the definition of evolution so that the mapping function can be different from the 32 identity function. Again let T be denned by: r = {(x(w),y(w),z(w))\we [0,1]}. The generalized evolution which maps T to Ta is now denned by: r r„ = {(X( W,a), Y( W,a),Z{ W,o))\W G [0,1]} where and Note that X(W,cr) = x(W) ®g(W,a) Y(W,a) = y(W) ®g(W,a) Z(W,a) = z(W)®g(W,a). W= W(w,o) and W(w,crQ) where cr0 is any value of cr, is a continuous and monotonic function of w. This condition is necessary to ensure physical plausibility since W is the parameter of the evolved curve Ta. A specially interesting case is when W always remains the arc length parameter as the curve evolves. When this criterion is satisfied, the evolution of T is referred to as arc length evolution. An explicit formula for W can be derived [Gage & Hamilton 1986]. . Let R( W, cr) = (X( W,a), Y( W, a), Z( W, cr)). The Frenet equations for a planar curve are given by dt ,dR, -bH = l-du-lKn and du du du Let t = a2/2. Observe that d ,, cTR |2. = d ( dR dR. _ (dR cPR, dt" du1 } ~ dt{ du ' du' ~ ^ du' dudt >' Note that 33 8R _ . dR . and dR —— = /cn since the Gaussian function satisfies the heat equation. It follows that ^ ' f t T 1 ) = 2 ( | - a T l * • 1 ^ ( / c n ) ) = 2 ( l 1 7 l 1 • " - ' " a T 1 K t + l 1 7 l K r b ) ) = - 2 | 1 7 l Therefore 2{~du~l dt1 d u ] - ~ 2 { du] or di1 dul~~] du1* • Let i denote the length of the curve. Now observe that M = [JL \^\du = -} A /c2du = -}/c2 aV a< { dt* du[ v 5 u o Since the value wQ of the normalized arc length parameter w at a point P meas-ures the length of the curve from the starting point to point P, it follows that W 2*L = -SK\W%t)dW o and therefore tW W(w,t) = -JJK\ W,t) dWdt + w. (4.3.1) o o Note that W(wfi) = w. The function defined implicitly by n(W,a) = c is the resampled curvature scale space of T and the function defined implicitly by T(W,O-) = 0 is the resampled torsion scale space of T. Since the function K(W,t) in (4.3.1) is unknown, W(w,t) can not be com-puted directly from (4.3.1). However, the resampled curvature and torsion scale 34 space images can be computed in a simple way: A Gaussian filter based on a small value of the standard deviation is computed. The curve T is parametrized by the normalized arc length parameter and convolved with the filter. The result-ing curve is reparametrized by the normalized arc length parameter and con-volved again with the same filter. This process is repeated until the curve has very few torsion zero-crossing points. The curvature level-crossings of each curve are marked in the resampled curvature scale space image and the torsion zero-crossings of each curve are marked in the resampled torsion scale space image. 4.4. Evolution and arc length evolution properties of space curves This section contains a number of results on evolution and arc length evo-lution of space curves as denned in sections 4.1 and 4.3. The proofs can be found in appendix B. The first five theorems express a number of global properties of space curves during evolution and arc length evolution. Theorem 4.4.1. Evolution and arc length evolution of a space curve are invari-ant under rotation, uniform scaling and translation of the curve. Theorem 4.4.2. A closed space curve remains closed during evolution and arc length evolution. Theorem 4.4.3. A connected space curve remains connected during evolution and arc length evolution. Theorem 4.4.4. The center of mass of a space curve is invariant during evolu-tion and arc length evolution. Theorem 4.4.5. Let T be a closed space curve and let G be its convex hull. T remains inside G during evolution and arc length evolution. The following theorem also appeared in Mokhtarian [1989]. It concerns the uniqueness properties of the torsion scale space image. Theorem 4.4.6. Let T be a space curve in C 3. Let T(U) and K(U) represent the torsion and curvature functions of T respectively. The derivatives at a single point on one torsion zero-crossing contour in the regular, resampled or renormal-ized torsion scale space image of V determines the function /3(IA) = T(U)K2(U) uniquely modulo a scale factor (except on a set of measure zero). 35 The following theorem makes explicit the conditions under which new torsion zero-crossings will not be observed at the higher scales of torsion scale space images. Theorem 4.4.7. Let T be a space curve in C3. If all evolved and arc length evolved curves Ta are in C 3 and torsion is bounded at every point of V during evolution, then all extrema of contours in the regular, renormalized and resam-pled torsion scale space images of T are maxima. Theorems 4.4.8 and 4.4.9 first appeared in [Mokhtarian 1988b]. They concern the local behaviour of space curves just before and just after the formation of cusp points during evolution. Theorem 4.4.8. Let T = (x(w),y(w),z(w)) be a space curve in Cx and let x(io), y(w) and z(w) be polynomial functions of w. Let = (X(W,cr),Y(W,cr),Z(W,cr)) be an evolved or arc length evolved version of V with a cusp point at WQ. There is a 6>0 such that either intersects itself in a neighborhood of point WQ or two projections of Tff_g intersect themselves in a neighborhood of point WQ. Theorem 4.4.9: Let Y = (x(w),y(w),z(w)) be a space curve in C\ and let x(w), y(w) and z(w) be polynomial functions of w. Let = (X(W,cr), Y(W,a),Z(W,cr)) be an evolved or arc length evolved version of T with a cusp point at W0, then either r < T + g has two new torsion zero-crossings in a neighborhood of W0 or a tor-sion zero-crossing point exists at Wo on Ta_g and T^g. The last theorem defines other conditions under which new torsion zero-crossings can appear on a space curve. Theorem 4.4.10: New torsion zero-crossings can appear on a smooth space curve during evolution or arc length evolution in a neighborhood of a point of zero curvature. 36 C h a p t e r 5 : A l g o r i t h m s a n d I m p l e m e n t a t i o n This chapter contains a number of key algorithms which have been used to implement the theories presented in chapters 3 and 4. Each algorithm is followed by a brief complexity analysis. It also contains a discussion of efficiency issues raised when implementing those theories. Chapter 5 ends by proposing a new scale space matching algorithm which has not been implemented yet. 5.1. T h e convolution masks The convolution masks are approximations to the Gaussian function G(u,er) its first derivative -u-,2 Gu(u,cr) -u cr3\/2lT its second derivative Guu(u,cr) and its third derivative Guuu(ui°) = 3 ^ 2 - tt3 ^ cr7V/27T The Gaussian function and its derivatives have infinite extent but in order to compute convolutions, they must be approximated by finite masks. For a 37 given value of a, the width of the Gaussian function, the size of the correspond-ing mask is set to 12a. As a result, the ratio of the height of the function at the cutoff point to its height at its center point is: -(6<T)2 - 3 6 0 * e 2 ^ = e ^ = e " 1 8 which is a very small ratio and negligible. Furthermore, the size of the mask is always set to an odd number so that it will be symmetric. Integer values of u are used to compute the mask elements. The mask elements are stored in a double C array and all computations are carried out using double arithmetic. As a result, the mask elements add up to values very close to one and no adjustments to their values were considered necessary. In fact, for o =1.0, the sum of mask elements computed using algorithm MASK was equal to 1.000000. Our experience shows that computations which use the first two derivatives, such as. computation of curvature, are stable for values of cr larger than 1.0 (corresponding to a mask which covers 13 points on the sampled input curve) and computations which use the first three derivatives, such as computation of torsion, are stable for values of a higher than 2.0 (corresponding to a mask which covers 25 points on the sam-pled input curve). The following is an algorithm for a function that computes a mask approximating the Gaussian function (or one of its derivatives): Algorithm: MASK 1. Let size = 12 o~ 2. If size is even then size = size + 1 3. Let start = (1 - size) / 2 4- Let finish = (size - 1) / 2 5. For i = start to finish do mask[i] = Gauss(i, a) End of Algorithm: MASK Note that algorithm MASK runs in time linearly proportional to a or in 0(o) time since the size of the computed mask is a linear function of the value of a. To convolve a mask with an array of data at element number k, the center element of the mask (corresponding to u = 0, where u is the first parameter in G(u,o)) is multiplied by array element k, the mask element corresponding to u=l is multiplied by array element £+1, the mask element corresponding to u=-l is multiplied by array element fc-1, and so on. This process is repeated until there are no more mask elements left to multiply. If the first or last array element is reached and the input curve is closed, there will be a wrap around: the array ele-ment after the last element is the first element. If the first or last array element is 38 reached and the input curve is open, the first or last array element is repeated as many times as necessary (This is the method that was used in this thesis. Note that other methods such as the extrapolation of the curve beyond the endpoint are also possible.) Al l products are then added up. The result is the value of con-volution at element number k. 5.2. T h e sampling algorithm The input curve, whether two-dimensional or three-dimensional, is represented by a sequence of points. Consecutive points of that sequence are assumed to be connected by straight line segments. However, the lengths of these line segments are not necessarily equal. It is therefore necessary to sample the input curve at equal-length intervals so that its evolved versions or its multi-scale representations can be computed. The sampling function takes the number of points to be sampled as an input parameter, determines the size of the sampling interval, As, and returns a list of points such that each pair of consecutive points on that list have a distance equal to As on the original curve. Let - Pi, P2> ••• » Pm D e t n e sequence of points representing the original curve and let Qi> Q21 ••• > Qn be * n e sequence of sampled points on that curve. Note that Pi = Qi- If the input curve is open, Pm = Qn. The following is an algorithm which describes how the sampling function generates its output. Note that function d returns the Euclidean distance between two points. Algorithm: SAMPLE 1. Let Qi = Pi 2. Letk = 2 3. For i = 2 to n do 3.1. Let old_k = k 3.2. Let D = dQ^Pk 3.3. while ( D < A 3 ) do 3.3.1. k = k+1 5.5.2. D = D + dPkP^ 3.4. If ( k> oldjc ) then do 3.4.1. w = ( D - A s ) I dPj>M 3.4.2. Qi = w Pk_i + (1-w) Pk else do 3.4.3. w = ( D - A s ) I D 3.44- Qi = v, Qi_i + (1-w) Pk End of Algorithm: S A M P L E 39 Note that algorithm SAMPLE runs in time linearly proportional to the larger of m and n. 5.3. Algorithms for representations of planar curves This section contains algorithms for functions which compute the regular, renormalized and resampled curvature scale space images of planar curves. Note that an evolved version of a planar curve is computed by first sam-pling it according to algorithm SAMPLE and then convolving each of its x and y coordinate functions with a mask corresponding to the input value of a. The following is an algorithm to compute the curvature scale space image of a planar curve. Note that this image is stored in array ess which is assumed to be initialized to zero. Algorithm: CURVATURE_SCALE_SPACE 1. Read(input curve) 2. Call SAMPLE —* n (* no. of sampled points *) 8. Let a = o~Q (* o~0 is relatively small; usually one *) 4- Let p=l (* p holds the no. of curvature zero-crossings found *) 5. While (p > 0) do 5.1. Letp = 0 5.2. Call MASK_lST_DERIV(o) (* computes mask based on 1st deriv. of Gaussian *) 5.8. Call MASK_2ND_DERIV(a) (* computes mask based on 2nd deriv. of Gaussian *) 5.4. Call CONVOLVER],mask_lst[],1) -+ x'flj 5.5. Call CONVOLVER J,mask_lst[-* y'flj 5.6. Call CONVOLVE(x[J,mask_2nd[},1) x'flj 5.7. Call CONVOLVER],mask_2nd[J,l) -» y"[l] 5.8. Let K[\) = x'[l\y"[l\ - x"[l]y'[l] 5.9. For i = 2 to n do 5.9.1. Call CONVOLVER],maskjst[J,i) x'[ij 5.9.2. Call CONVOLVERJ,mask_lst[J,i) -> y'[ij 5.9.8. Call C0NV0LVE(x[J,mask_2nd[J,i) -> x"[i] 5.9.4. Call CONVOLVE(y[J,mask_2ndf J,i) -> y"[i] 5.9.5. Let «[?] = -5.9.6. If((n[i] > 0) and (K[U1J < 0)) or ((n[ij < 0) and > 0)) then 5.9.6.1. If(\K[i]\ > \n[i-lj\) then cssfi-l,a] = 1 else cssfi,a] = 1 5.9.6.2. p = p + 1 5.9.7. a = cr + ACT End of Algorithm: CURVATURE_SCALE_SPACE 40 Function CONVOLVE takes 0(a) time to return a value. Therefore each row of the curvature scale space image takes O(rur) time to compute. Since the number of rows of a curvature scale space image is linearly related to a, it takes 0(na2) to compute a curvature scale space image using algorithm CURVATURE_SCALE_SPACE. The algorithm to compute the renormalized curvature scale space image is similar to algorithm CURVATURE_SCALE_SPACE and therefore only the differences will be pointed out: Algorithm RENORMALIZED J3URVATURE_SCALE_SP ACE has a few extra steps between steps 5.1 and 5.2 to compute the total length of the curve and the length up to each point of the curve as following: a.l. Let distflj = 0 (* array dist holds the distances up to each point *) a.2. Let L = 0 (* L holds the total length of the sampled curve *) a. 3. Call MASK_GAUSS(o) (* computes a mask based on the Gaussian fn *) a.4. Call CONVOLVE(x)],mask_gau3s[-» X[lJ a.5. Call C0NV0LVE(y[],mask_gauss[],1) - » • YflJ a. 6. For i = 2 to n do a.6.1. Call C0NV0LVE(x[],mask_gauss[J,i) -* X[iJ a.6.2. Call C0NV0LVE(y[J,mask_gauss[J,i) -* YfiJ a.6.3. L = L + d{{x\(\,Y\{\U^ilY\i-\])) a.6.4- distfij = L Step 5.9.6.1 in algorithm CURVATURE_SCALE_SPACE should also be modified as following: 5.9.6.1. If(\K[iJ\ > \K[i-lJ\) then css[(dist[i-lj/L)n,o] = 1 else css[(dist[i]/L)n,o] = 1 Algorithm RENORMALIZED_CURVATURE_SCALE_SPACE also takes 0(ncr2) time to compute a curvature scale space image, however, in practice it takes longer than algorithm CURVATURE_SCALE_SPACE due to the extra time needed to compute the length of the evolved curve in each iteration. Note that an arc length evolved version of a planar curve is computed by first sampling it using function SAMPLE and then convolving its x and y coordi-nate functions with a mask corresponding to a small o. The output curve is sam-pled again using SAMPLE and its a: and y coordinate functions are convolved again with the same mask. This process is repeated for as many iterations as necessary. 41 The third algorithm in this section computes the resampled curvature scale space image of a planar curve. Again only the differences between this algo-rithm and algorithm CURVATURE_SCALE_SPACE will be pointed out: Algorithm RESAMPLED_CURVATURE_SCALE_SPACE makes only one call to MASK_1ST_DERIV and MASK_2ND_DERIV and therefore these two calls come just before step 5. Furthermore, step 2 should now be: 2. Call SAMPLE -> n0 step 5.9.7 should be changed to 5.9.7. Call SAMPLE -> n and step 5.9.6.1 should be modified as following: 5.9.6.1. If(\K[i]\ > |«[i-l]|) then css[((i-l)/n)n0,cr] = 1 else css^i/n)^^ = 1 Algorithm RESAMPLED_CURVATURE_SCALE_SPACE always uses masks of constant size and therefore takes 0(n) time to compute each row of a resampled curvature scale space image and 0{rn) time to compute an entire image with r rows. 5.4. Algorithms for representations of space curves This section contains algorithms for functions which compute the regular, renormalized and resampled torsion scale space images of space curves. Note that an evolved version of a space curve is computed by first sam-pling it according to algorithm SAMPLE and then convolving each of its x, y and z coordinate functions with a mask corresponding to the input value of a. Our experience showed that choosing a threshold value to be used when computing the curvature scale space image of a space curve was not straightfor-ward and that variations in its magnitude significantly affected the structure of the curvature scale space image. Therefore the curvature scale space representa-tion of a space curve is not invariant with respect to scaling since scaling changes curvature values on a space curve. Since the torsion scale space image of a space curve is in fact invariant with respect to scaling and is usually sufficient to distin-guish the curve from other curves it is being compared to, it was decided not to compute the curvature scale space image of the space curves shown in chapter 6. It is therefore not necessary to present an algorithm for this class of representa-tions. Note however, that the algorithm would be quite similar to algorithm CURVATURE_SCALE_SPACE in section 5.3. The following is an algorithm to compute the torsion scale space image of a space curve. Note that this image is stored in array tss which is assumed to be 42 initialized to zero. Algorithm: TORSION_SCALE_SPACE 1. Read(input curve) 2. Call SAMPLE —> n (* no. of sampled points *) 3. Let a = cr0 (* aQ is relatively small; usually two *) 4- Let p=l (* p holds the no. of torsion zero-crossings found *) 5. While (p > pQ) do (* where p0 is a small number *) 5.1. Letp = 0 5.2. Call MASK_lST_DERIV((x) (* computes mask based on 1st deriv. of Gaussian *) 5.8. Call MASKmm2ND_DERIV(a) (* computes mask based on 2nd deriv. of Gaussian *) 5.4. Call MASK_3RD_DERIV(a) (* computes mask based on 3rd deriv. of Gaussian *) 5.5. Call CONVOLVERJ,mask_lst[],1) -+ x'flj 5.6. Call CONVOLVER],mask_lstf],1) -+ y'fl] 5.7. Call CONVOLVE(z) ],mask_lst[ ],1) z'fi] 5.8..Call CONVOLVE(xf ],mask_2ndf J,l) -> x"fl] 5.9. Call CONVOLVEfyf J,mask_2ndfJ,l)^y"flJ 5.10. Call CONVOLVE(z[J,mask_2ndf ],1) -+ z'flj 5.11. Call CONVOLVE(xf J,mask_Srd[ J,l) -+ x"'[lj 5.12. Call CONVOLVE(yf J,mask_Srdf J,l) -+ y'fl] 5.13. Call CONVOLVE(z) J,mask_Srd[ J,l) —> z'flj - A , T 1 r-i l in 1 n in n 1. . 111 1 11 111 1 n . '// ' 11 HI 1 11 5.14- Let r[lj = z xy - z x y + y zx - y xz + x yz - x zy 5.15. For i = 2 to n do 5.15.1. Call CONVOLVE(xf ],mask_lst[],i) -+ x'fi] 5.15.2. Call CONVOLVE(yf ],mask_lstf ],i) -> y'fi] 5.15.3. Call CONVOLVE(z[J,mask_lstfJ,i) -> z'fij 5.15.4. Call CONVOLVE(xf J,mask_2nd[ J,i) -> x'fi] 5.15.5. Call CONVOLVER J,mask_2ndf J,i) -> y'fi] 5.15.6. Call C0NV0LVE(z[J,mask_2ndfJ,i) -» z'fi] 5.15.7. Call CONVOLVER J,mask_3rdfJ,i) -• x'fi] 5.15.8. Call CONVOLVER],mask_Srd[ ],i) -+ y'fi] 5.15.9. Call CONVOLVE(zf],mask_Srd[],i) -+ z'fi] - w w n T . r -i III I II III II I , /// / II III I II , /// / // /'/ / '/ 5.15.10. Let T[I\ = z xy - z x y + y z x - y xz -f x y z - x zy 5.15.11. If ((rfi] > 0) and (rfi-1] < 0)) or ((rfi] < 0) and (rfi-lj > 0)) then 5.15.11.1. If.(\T[i]\ > \rfi-lj\) then tssfi-l,aj = 1 else tss[i,a] = 1 5.15.11.2. p = p + 1 5.15.12. a = a + ACT End of Algorithm: TORSION.SC A L E . S P A C E 43 The algorithm to compute the renormalized torsion scale space image is similar to algorithm TORSION_SCALE_SPACE and therefore only the differences will be pointed out: Algorithm RENORMALIZEDJTORSION_SCALE_SPACE has a few extra steps between steps 5.1 and 5.2 to compute the total length of the curve and the length up to each point of the curve as following: a.l. Let dist[l] = 0 (* array dist holds the distances up to each point *) a.2. Let L = 0 (* L holds the total length of the sampled curve *) a.S. Call MASK_GAUSS(o) (* computes a mask based on the Gaussian fn *) a.4. Call CONVOL VE(x[ J,mask_gauss[],1) -> XflJ a.5. Call CONVOLVERJ,mask_gaussf ],1) Y[l] a.6. Call CONVOLVE(z)],mask_gauss)-> Z[l] a.l. For i = 2 to n do a.7.1. Call CONVOLVE(x[J,mask_gauss[],i) -+ Xfi] a.l.2. Call CONVOLVER],mask_gauss[J,i) YfiJ a. 7. S. Call CON VOL VE(z[ ], mask_gauss[ ], i) -> Z[i] a.l.4. L = L + ^ (A[i]>n»1,2[il),(AlW]>VIi-l],2l*-l])) a.1.5. dist[ij — L Step 5.15.11.1 in algorithm TORSION_SCALE_SPACE should also be modified as following: 5.15.11.1. If(\r[i]\ > \r[i-l]\) then tss[(dist[i-l]/L)n,a] = 1 else tss[(dist[i]/L)n,o~] = 1 Note that an arc length evolved version of a space curve is computed by first sampling it using function SAMPLE and then convolving its x, y and z coor-dinate functions with a mask corresponding to a small a. The output curve is sampled again using SAMPLE and its x, y and z coordinate functions are con-volved again with the same mask. This process is repeated for as many iterations as necessary. The third algorithm in this section computes the resampled torsion scale space image of a space curve. Again only the differences between this algorithm and algorithm TORSION_SCALE_SPACE will be pointed out: Algorithm RESAMPLED_TORSION_SCALE_SPACE makes only one call to MASK_1ST_DERIV, MASK_2ND_DERIV and MASK_3RD_DERIV and there-fore these two calls come just before step 5. Furthermore, step 2 should now be: 44 2. Call SAMPLE - » 7 ^ step 5.15.12 should be changed to 5.15.12. Call SAMPLE —• n and step 5.15.11.1 should be modified as following: 5.15.11.1. If (\r[i]\ > \r[i-l]\) then tss[((i-l)/n)nQ,a] = 1 else tss[(i/n)nQ)aJ = 1 Similar analyses show that algorithms TORSION_SCALE_SPACE and RENORMALIZED_TORSION_SCALE_SPACE take 0(na2) time to compute tor-sion scale space images and algorithm RESAMPLEDJTORSION_SCALE_SPACE takes 0(rn) time to compute a torsion scale space image. 5.5. Efficiency issues Since the computation of curvature and torsion scale space images calls for the computation of a large number of convolutions, it is appropriate to investi-gate ways of rendering those computations more efficient: 1. The computation of curvature and torsion scale space images can be made more efficient by tracking the zero-crossing points across scales. A small change in the value of a, the width of the Gaussian, will result in a small change in the location of a curvature or torsion zero-crossing point. It follows that if the location of curvature or torsion zero-crossing points of a curve are known at level ( 7 0 , then the location of those points at level a0+Aa can be determined by searching only a neighborhood of the zero-crossing points at level crQ. This method is specially useful when it is known that no new zero-crossing points will be encountered at the higher levels of the scale space image, for example when computing the resampled curvature scale space image of a simple curve. This method was used to speed up the computation of several curvature scale space images shown in chapter 6. Let n and c be the number of sampled points and the number of curva-ture zero-crossings on the input curve respectively. It follows that the curva-ture scale space image can be computed in 0(ca2) time. Note, however, that in general after a small number of iterations, the number of zero-crossings drops to a small number. If it is assumed that after a constant number of iterations, the number of zero-crossings drops below a constant, then it follows that the curvature scale space image can be computed in 0(n) + 0(a) time. 45 2. Fast Fourier transforms can also be used to speed up the computation of cur-vature and torsion scale space images when a becomes large. This method is an alternative to tracking when there is reason to believe that new curvature or torsion zero-crossing points will be encountered at the higher scales of the curvature or torsion scale space image. Since using the FFT method, it takes O(n\ogn) time to compute each row [Aho et al. 1974], computation of the entire curvature scale space image takes O(crnlogn) time. 3. The computation of curvature and torsion scale space images can also be made more efficient by using an incremental method. Note that algorithm CURVATUREJSCALE_SPACE in section 5.3 uses the original data in each iteration and a larger value of a to compute the next higher level of descrip-tion of the input curve. This can lead to quite large values of a and a long computation time. The computation time can be significantly reduced by using the data obtained at the last scale level to compute the next level of descrip-tion. To see why this is possible, note that if f(x) is a continuous function and <7l(x) and (72(x) axe Gaussian functions with widths CTJ and <r2, then (J®9i) ®92 = (f®92) ®9i = f®9z where </3 is another Gaussian function with width <r3 and < 7 3 2 = a x 2 + <T22. The computation of the curvature scale space image again takes 0(na2) time, however, this technique results in much smaller values of a used to compute the curvature or torsion scale space image. This method was used to speed up the computations of the torsion scale space images shown in chapter 6. 4. Another way to speed up the computation of curvature and torsion scale space images is to use parallelism and specialized hardware such as convolution chips. This method can also be combined with methods 1,2 and 3 for max-imum efficiency. For example, suppose we wish to compute the curvature scale space image of a planar curve, and that n processors are available for parallel use. The curvature scale space image can be divided into n segments using lines perpendicular to the cr-axis or lines perpendicular to the u-axis and each processor given the job of computing the curvature scale space image of the segment assigned to it. If segmentation is done along the cr-axis, fast Fourier transforms can be used to compute the evolved curve at the starting scale level of each segment and the incremental method or the tracking method can be used to compute the rest of the segment. If it is assumed that enough processors are available such that each pro-cessor computes a constant number of rows of the curvature or torsion scale 46 space image, then the entire curvature or torsion scale space image can be computed in O(n\ogn) time. Note that almost all the curvature and torsion scale space images shown in chapter 6 have been computed at high resolution so that small details as well as the basic structure of the scale space images can be recognized. In practice, one may wish to compute the curvature or torsion scale space image at a considerably lower resolution by increasing the length of the sampling interval and the magni-tude of the step size in a. The low-resolution scale space image will be consider-ably faster to compute and should be adequate for most recognition tasks. For example if the length of the sampling interval is doubled, the number of sampled points and the largest value of a used will be reduced by a factor of two. It fol-lows that the required computation time using algorithm CURVATURE_SCALE_SPACE or algorithm TORSION_SCALE_SPACE will be reduced by a factor of eight. 5.6. Matching scale space images The scale space matching algorithm in [Mokhtarian & Mackworth 1986] makes assumptions about curvature scale space representations which are not always true. For example, it assumes that CSS representations always have a hierarchical structure, i.e., curvature zero-crossing contours never intersect and that two curves which are close in shape always have the same hierarchical struc-ture. The following is a scale space matching algorithm which should run consid-erably faster than the algorithm in Mokhtarian & Mackworth [1986]. It also does not make possibly incorrect assumptions about the structure of a scale space representation. This algorithm has not been implemented yet. Note that the extrema of the curvature or torsion zero-crossing contours in a curvature or torsion scale space representation are important and distinguish-able points. They occur at different scales and provide us with an abundance of features to be used for the matching process. They can be located easily and they are the natural candidate points to use in order to determine the correspondence between the scale space images to be matched since, unlike other zero-crossings, each extremum is isolated in a region which contains it. We therefore proceed by extracting all extrema of the zero-crossing contours from both scale space representations and R2 to be matched. Let E^ and E2 be the set of points thus obtained. Let Px, P2, • • • , Pn be the extrema in Ex ordered by height and let Q\i Qi-> ' ' ' > Qn be the extrema in E2 also ordered by height. The problem now is to assign each point of E1 to a distinct point of E2 which will minimize the total matching cost. The cost of assigning a point Pi to point Qj is equal to the Euclidean distance between those two points multiplied by the height of those points since matches at higher scales are considered more important. The actual 47 algorithm then is as follows: Algorithm: SCALE_SPACE_MATCHER 1. Create n nodes corresponding to the possible match of Pi and each of the extrema in E2. Assign a cost of 0 to each node. 2. For each node (P\, QJ, compute the scale space transformation parameters which will transform the scale space coordinates of Qt to the scale space coordi-nates of Pj. / / the node (P\, represents a correct match, then these transformation parameters will cause the remaining extrema of to overlap with the remaining extrema of E2 in a one-to-one fashion. 3. For each node, apply the transformation parameters to the coordinates of Qj (l<j<n) to compute their new coordinates for that node. 4- Expand each node one step: for each node find the closest unassigned extremum in E2 to P2 and assign them to each other. Note that the two extrema that are assigned to each other should be of the same type: minima or maxima. Compute the cost of that assignment and add it to the node cost. 5. Find the lowest cost node and expand it one step: assign the next unassigned extremum in E± to its closest unassigned extremum in E2 and add the assign-ment cost to the node cost. 6. If there are no more unassigned extrema from either E± or E2 in the lowest cost node, then STOP: the lowest cost match has been found. Otherwise, go to step 5. End of Algorithm: SCALE_SPACE_MATCHER Note that in general, if representation R1 is a good match for representa-tion R2, then point Pj will usually match point Qlt P2 will match Q2, etc. and the algorithm will terminate quickly. However, the algorithm above has been designed to have the capability to handle situations in which two or more of the highest extrema of or R2 have roughly the same height. 48 Chapter 6: Experimental Results and Evaluation This chapter shows a number of planar and space curves which were used as input data to the programs described in chapter 5 along with the output obtained from those programs. It also describes a number of experiments which were carried out on the representations. The chapter also contains a discussion of the significance of the theorems of chapters 3 and 4. It ends with an evaluation of the curvature and torsion scale space representations proposed in chapters 3 and 4 according to the criteria proposed in chapter 1. 6.1. Planar Curves Algorithm CURVATURE_SCALE_SPACE in section 5.3 was used to com-pute the curvature scale space image of three different planar curves. Figure 6.1.1 shows the coastline of Africa. This curve was used as the first input curve. Fig-ure 6.1.2 shows several evolved version of the coastline of Africa for increasing values of <r, the width of the Gaussian filter. It can be observed that as a increases, the small-scale features on the curve disappear. Larger values of a per-form a very good job of filtering out the detail on the curve and bringing out its basic structure. A very large value of sigma filters out nearly all of the structure and the curve tends to a circle. Figure 6.1.3 shows the curvature scale space image of Africa. Horizontal lines have been drawn across that image to indicate the values of a which were used to compute the evolved curves of figure 6.1.2. It can be observed that the smaller features show up as contours which are confined to the fine scales of the curvature scale space image whereas the basic features result in contours which last until the larger scales. Figure 6.1.1. Coastline of Africa 50 (e) a - 32 , _ (f) a = 64 Figure 6.1.2. Africa during evolution 51 Figure 6.1.3. The curvature scale space image of Africa 52 The second input curve is shown in figure 6.1.4. This is Koch's snowflake curve. Several evolved versions of that curve are shown in figure 6.1.5 and the curvature scale space image of the curve is shown in figure 6.1.6. Horizontal fines have been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.1.5. Note that Koch's snowflake curve is a fractal curve and its curvature scale space image also has a fractal property. The third input curve is the curve of figure 6.1.7. This curve is the outline of a design taken from a Persian carpet. Figure 6.1.8 shows the carpet design dur-ing evolution and figure 6.1.9 shows the curvature scale space image of the carpet design. Horizontal lines have been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.1.8. Note that since the carpet design is a symmetric curve, its curvature scale space image is also symmetric. We then carried out a number of experiments to test the suitability of the representations under various conditions. The purpose of the first experiment was to test the behaviour of the curvature scale space image when a considerable amount of noise corrupts the shape of the input curve. Figure 6.1.10 shows the coastline of Africa with a significant amount of random and uniform noise added to it. The noise at each point of the curve is added along the direction of the vec-tor normal to the curve at that point. Note that the curve can intersect itself. It follows from theorems 3.4.3 and 3.4.5 that new curvature zero-crossings can appear during its evolution. Figure 6.1.11 shows the curvature scale space image of the curve of figure 6.1.10 superimposed on the curvature scale space image of the original Africa figure. As expected, the images shown in figure 6.1.11 show differences in detail. However, a remarkable similarity in the basic structures of the two images can be observed. This experiment shows that the curvature scale space image is very stable and reliable even when a significant amount of uniform noise corrupts the shape of the input curve. The next experiment tested the behaviour of the curvature scale space image under severe noise conditions. Figure 6.1.12 shows the coastline of Africa with severe, uniform noise added to it. Figure 6.1.13 shows the curvature scale space image of the curve of figure 6.1.12 superimposed on the curvature scale space image of the original Africa figure. Even with the presence of severe noise, a very close similarity can be observed between the two images. The next experiment examined the behaviour of the proposed representa-tions when non-uniform noise corrupts the shape of the input curve. Figure 6.1.14 shows the coastline of Africa with random, non-uniform noise added to its lower half. Note that the curve remains simple after the addition of noise. Figure 6.1.15 shows the curvature scale space image of Africa with non-uniform noise. 53 Figure 6.1.4. Koch's snowflake curve 54 Figure 6.1.5. Snowflake curve during evolution 55 <r=20 (7=10 <r=5 • A f] I I I ! \ : i \ / \ i A A \ \ A 1 10 A : -i 4UJ-Wttty 4 WW m Figure 6.1.6. The curvature scale space image of the snowflake 56 Figure 6.1.7. Design from a Persian carpet 57 Figure 6.1.8. Carpet design during evolution 58 Figure 6.1.9. The curvature scale space image of the carpet design Figure 6.1.10. Coastline of Africa with uniform, random noise 60 Figure 6.1.11. The CSS image of Africa with uniform noise superimposed on the CSS image of Africa • Figure 6.1.12. Coastline of Africa with severe, uniform noise Figure 6.1.13. The CSS image of Africa with severe noise superimposed on the CSS image of Africa 6 3 Figure 6.1.14. Coastline of Africa with non-uniform, random noise Figure 6.1.15. The curvature scale space image of Africa with non-uniform noise 65 When compared to the curvature scale space image of Africa shown in figure 6.1.3, it is clear that there does not exist a good overall match of the two images. Figure 6.1.16 shows the renormalized curvature scale space image of Africa and figure 6.1.17 shows the renormalized curvature scale space image of Africa with non-uniform noise. Figure 6.1.18 shows the superposition of the images shown in figures 6.1.16 and 6.1.17. It can be seen that the degree of match shown in figure 6; 1.18 is much better than the degree of match of figure 6.1.3 to figure 6.1.15. As expected, the degree of match is much better at higher scales. Finally, figure 6.1.19 shows the resampled curvature scale space image of Africa and figure 6.1.20 shows the resampled curvature scale space image of Africa with non-uniform noise. Figure 6.1.21 shows the superposition of the images shown in figures 6.1.19 and 6.1.20. Note that a very close match exists between those two images. Three different multi-scale representation techniques for planar curves were described in this thesis. These three are: the regular curvature scale space image, the renormalized curvature scale space image and the resampled curvature scale space image. Each representation technique is suitable for a class of specific applications. When low to moderate, uniform noise exists on the curve, the regu-lar curvature scale space image can be used. However, when there is non-uniform or severe noise on the curve or when there are local shape differences between the model curves and the image curves, either the renormalized or the resampled cur-vature scale space images should be used. Note that the renormalized curvature scale space image is the most computationally intensive. Observations indicate that when there are local shape differences, the resampled curvature scale space images show the best overall match whereas the renormalized curvature scale space images match well at high scales but are more influenced by the shape differences at lower scales. Therefore the choice of the representation technique should depend on the scale level of the curve features that one wishes to emphasize. Table 6.1.1 summarizes the advantages and disadvantages of each representation technique. This concludes the experiments which were carried out on planar curves. The following is a discussion of the practical significance of the theorems of chapter 3. Theorem 3.4.1 showed that evolution and arc length evolution of a planar curve are invariant under rotation, uniform scaling and translation of the curve. This shows that the regular, renormalized and resampled curvature scale space images of a planar curve have the invariance property [Mokhtarian & Mackworth 1986]. The invariance property is essential since it makes it possible to match a planar curve to another of similar shape which has undergone a transformation consisting of arbitrary amounts of rotation, uniform scaling and translation. 66 Figure 6.1.16. The renormalized curvature scale space image of Africa 67 Figure 6.1.17. The renormalized curvature scale space image of Africa with non-uniform noise 68 Figure 6.1.18. The Renormalized CSS image of Africa with non-uniform noise superimposed on the Renormalized CSS image of Africa 69 Figure 6.1.19. The Resampled curvature scale space image of Africa Figure 6.1.20. The Resampled curvature scale space image of Africa with non-uniform noise 71 Figure 6.1.21. The Resampled CSS image of Africa with non-uniform noise superimposed on the Resampled CSS image of Africa 72 Theorems 3.4.2 and 3.4.3 showed that connectedness and closedness of a planar curve are preserved during evolution and arc length evolution. These theorems demonstrate that evolution and arc length evolution of a planar curve do not change the physical interpretation of that curve as the boundary of a two-dimensional object. Representation technique Advantages Disadvantages The Regular Curvature Scale Space Image • Suitable for transformations consisting of uniform scaling, rotation and translation. • Suitable when uniform, low-intensity noise has corrupted the curve. • Non-uniform noise or local difference in shape can cause problems. The Renormalized Curvature Scale Space Image • More suitable when there is non-uniform noise on the curve or local shape differences exist. • Most computationally intensive. The Resampled Curvature Scale Space Image • Most suitable when there is high-intensity, non-uniform noise or local shape differences exist. • De-emphasizes shape differences at fine scales. Table 6.1.1. Comparison of Regular, Renormalized and Resampled Curvature Scale Space Images. Theorem 3.4.4 showed that the center of mass of a planar curve does not move as the curve evolves and theorem 3.4.5 showed that a planar curve remains inside its convex hull during evolution and arc length evolution. Together, theorems 3.4.4 and 3.4.5 impose constraints on the physical location of a planar curve as it evolves. These constraints become useful whenever the physical loca-tion of curves in an image or their locations with respect to each other is impor-tant. A possible application area is stereo matching in which it is advantageous to carry out matching at coarser levels of detail first and then match at fine detail levels to increase accuracy. Theorem 3.4.6 showed that the curvature scale space images of a planar curve determines that curve uniquely modulo uniform scaling, rotation and trans-lation. This shows that the curvature scale space images satisfy the uniqueness property [Mokhtarian & Mackworth 1986]. This property ensures that curves of different shapes do not have the same representation. 73 Theorems 3.4.8 and 3.4.10 together locally characterize the behaviour of a planar curve just before and just after the formation of a cusp point during evolu-tion and arc length evolution. This behaviour can be used to detect any cusp points that form during evolution or arc length evolution of a planar curve. Such cusp points can then be used effectively to facilitate matching since they provide us with a set of distinctive and easily recognizable features. These theorems also show that self-intersecting curves are described in a natural way by our represen-tation technique. The self-intersection loop gradually grows smaller until it turns into a cusp point and vanishes. In contrast, Asada and Brady's method [1986] enlarges the smaller loop until it becomes as large as the larger loop. Figure 6.1.22 shows a self-intersecting curve during evolution. The self-intersection is resolved through the formation of a cusp point after which the curve becomes simple. Figure 6.1.23 shows the curvature scale space image of the curve of figure 6.1.22. Horizontal lines have been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.1.22. Figure 6.1.24 shows a convex, self-crossing curve during evolution and figure 6.1.25 shows the curva-ture scale space image of the curve of figure 6.1.24. Horizontal lines have again been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.1.24. Theorem 3.4.7 showed that if a planar curve remains smooth during evolu-tion or arc length evolution, then no new curvature zero-crossings will be observed in its curvature scale space images. Theorem 3.4.8 showed that every planar curve intersects itself during evolution or arc length evolution just before the formation of a cusp point and theorem 3.4.9 showed that simple curves remain simple during arc length evolution. Combining theorems 3.4.7, 3.4.8 and 3.4.9, we conclude that no new curvature zero-crossing points are created during arc length evolution of simple curves. This is an important result since it indi-cates that new "structure" is not created in the curvature scale space representa-tions of simple curves [Marr & Nishihara 1978]. Note that a subclass of self-crossing curves also shares this property. The result stated by theorem 3.4.9 is also very important. Simple planar curves usually represent the boundaries of two-dimensional objects. Arc length evolved versions of those curves can only have physical interpretation as boun-daries of two-dimensional objects if they are also simple. Theorem 3.4.9 shows that this is in fact the case. Figure 6.1.26 shows a simple curve and its evolved versions. It can be seen that the curve intersects itself during evolution. Figure 6.1.27 shows the same curve and its arc length evolved versions. As expected, the curve remains simple during arc length evolution. 74 (a) Original curve (b) a = 16 ( c ) <J — 28 (d) 40 Figure 6.1.22. A self-crossing curve during evolution 75 Figure 6.1.23. The CSS image of the curve of figure 6.1.22 76 (a) Original curve (b) <r = 20 (c) a — 32 (d) a = 40 Figure 6.1.24. A self-crossing curve during evolution 77 (7 = 32 <r=20 Figure 6.1.25. The CSS image of the curve of figure 6.1.24 78 A lAAAAA/WWW\AAAAA/VWW\i (a) A simple curve (b) (7 = 4 (c) cr = 16 (d) a = 25 (e) <r = 32 (f) cr = 48 Figure 6.1.26. A simple curve during (regular) evolution 79 [imimmimjWmN V J (a) A simple curve (b) After 3 iterations (c) After 6 iterations (d) After 10 iterations (e) After 30 iterations (f) After 50 iterations Figure 6.1.27. Curve of figure 6.1.26 during arc length evolution 80 6.2. Space Curves We used algorithm TORSION_SCALE_SPACE given in section 5.4 to compute the torsion scale space images of several input space curves. Figure 6.2.1 shows a space curve depicting a fork. Figure 6.2.2 shows several evolved versions of the fork and figure 6.2.3 shows the torsion scale space image of the fork. Hor-izontal lines have been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.2.2. Again note that as cr, the width of the Gaussian function, increases, small-scale features on the curve disappear but the more basic features are preserved. Figure 6.2.4 shows a space curve dep-icting a bottle-opener. Several evolved versions of the bottle-opener are shown in figure 6.2.5 and its torsion scale space image is shown in figure 6.2.6. Horizontal lines have been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.2.5. The third example is the curve shown in figure 6.2.7. This curve depicts an armchair. Figure 6.2.8 shows several evolved versions of the armchair and figure 6.2.9 shows the torsion scale space image of the armchair. Horizontal lines have been drawn across that image to indicate the values of a which were used to compute the curves of figure 6.2.8. Note that since the fork, the bottle-opener and the armchair are all depicted by symmetric curves, their torsion scale space images are all symmetric as well. Experiments were also carried out to examine the behaviour of the pro-posed torsion scale space representations when input curves are corrupted by noise. Figure 6.2.10 shows the armchair with a significant amount of noise added to it. The direction as well as the magnitude of the noise is random. Figure 6.2.11 shows the torsion scale space image of armchair with noise and figure 6.2.12 shows the renormalized torsion scale space image of armchair with noise. It can be observed that despite the addition of a considerable amount of noise, the tor-sion scale space image retains its basic structure very well. Figure 6.2.13 shows the superposition of the image of figure 6.2.11 and the image of figure 6.2.9. A very close match can be observed between the two images. Figure 6.2.14 shows the armchair corrupted with severe random noise. The torsion scale space image of armchair with severe noise, shown in figure 6.2.15, no longer matches well with the torsion scale space image of the original armchair shown in figure 6.2.9. How-ever, the resampled torsion scale space image of the armchair, shown in figure 6.2.16, and the resampled torsion scale space image of the armchair with severe noise, shown in figure 6.2.17, show a very close match. Figure 6.2.18 shows the superposition of the images shown in figures 6.2.16 and 6.2.17. Figure 6.2.1. T w o v i e w s of a space c u r v e d e p i c t i n g a f o r k 82 (b) a = 5 10 (d) a = 20 Figure 6.2.2. The fork during evolution 83 Figure 6.2.3. The torsion scale space image of the fork 84 Figure 6.2.4. Two views of a space curve depicting a bottle opener 85 (b)<r (c) a = 4 (d) a Figure 6.2.5. The bottle opener during evolution 86 Figure 6.2.7. A space curve depicting an armchair 8 8 Figure 6.2.8. The armchair during evolution 89 Figure 6.2.9. The torsion scale space image of the armchair 90 Figure 6.2.10. The armchair with random noise Figure 6.2.11. The torsion scale space image of the armchair with noise 92 Figure 6.2.12. The Renormalized TSS image of armchair with noise Figure 6.2.13. The TSS image of armchair with noise superimposed on the TSS image of armchair 95 96 Figure 6.2.16. The Resampled torsion scale space image of the armchair 97 Figure 6.2.17. The Resampled TSS image of armchair with severe noise 98 Figure 6.2.18. The Resampled TSS image of armchair with severe noise superimposed on the Resampled TSS image of armchair 99 For a comparison of regular, renormalized and resampled torsion scale space images and the advantages and disadvantages of each see the discussion of section 6.1 on the regular, renormalized and resampled curvature scale space images and table 6.1.1 on their advantages and disadvantages. The same argu-ments apply fully to torsion scale space representations. This concludes the experiments which were carried out on space curves. The following is a discussion of the practical significance of the theorems of chapter 4. Theorem 4.4.1 showed that evolution and arc length evolution of a space curve are invariant under rotation, uniform scaling and translation of the curve. This shows that the regular, renormalized and resampled torsion scale space images of a space curve have the invariance property. The invariance property is essential since it makes it possible to match a space curve to another of similar shape which has undergone a transformation consisting of arbitrary amounts of rotation, uniform scaling and translation. Theorems 4.4.2 and 4.4.3 showed that closedness and connectedness of a space curve are preserved during evolution and arc length evolution. These theorems demonstrate that evolution and arc length evolution of a space curve do not change the physical interpretation of that curve as the boundary of a three-dimensional object. Theorem 4.4.4 showed that the center of mass of a space curve does not move as the curve evolves and theorem 4.4.5 showed that a space curve remains inside its convex hull during evolution and arc length evolution. Together, theorems 4.4.4 and 4.4.5 impose constraints on the physical location of a space curve as it evolves. These constraints become useful whenever the physical loca-tion of curves in a scene or their locations with respect to each other is important for example when two or more space curves are used to represent a three-dimensional object. Theorem 4.4.6 showed that the torsion scale space images of a space curve determine that curve modulo the class denned by the function /?(«) = «2(«) r(u) where K(U) and r(w) are the curvature and torsion functions of that curve respec-tively. This shows that the torsion scale space images are often sufficient to dis-tinguish a space curve from other space curves it is being compared to. In such cases, the torsion scale space can be said to satisfy the uniqueness property. This property ensures that curves of different shapes do not have the same representa-tion. Theorems 4.4.8 and 4.4.9 together locally characterize the behaviour of a space curve just before and just after the formation of a cusp point during evolu-tion and arc length evolution. This behaviour can be used to detect any cusp 100 points that form during evolution or arc length evolution of a space curve. Such cusp points can then be used effectively to facilitate matching since they provide us with a set of distinctive and easily recognizable features. Theorem 4.4.7 showed that if a space curve remains smooth during evolu-tion or arc length evolution and torsion remains bounded at every point of that curve, then no new torsion zero-crossings will be observed in its torsion scale space images and theorem 4.4.10 showed that new torsion zero-crossings can indeed occur on a space curve that remains smooth during evolution at points of zero curvature. Together, theorems 4.4.9 and 4.4.10 describe all situations that can lead to creation of new torsion zero-crossings on a space curve during evolu-tion. This enables one to make inferences about a space curve when new torsion zero-crossings are observed in its torsion scale space image. 6.3. Evaluation of the Representations The following is an evaluation of the curvature and torsion scale space representations according to the criteria proposed in chapter 1. Criterion: Invariance Recall that by invariance, we meant that the representation for the shape of a curve should not change when shape-preserving transformations (rotation, uniform scaling and translation) are applied to that curve. Translation of the curve causes no change in the curvature and torsion scale space representations proposed here. Uniform scaling causes the curvature and torsion scale space representations to undergo uniform scaling as well. If the represented curves are closed, then their curvature and torsion scale space representations can be normalized and invariance with respect to uniform scaling will also be achieved. If the represented curves are open, changes due to uniform scaling can be handled by a matching algorithm such as SCALE_SPACE_MATCHER in chapter 5. Rotation causes only a horizontal shift in the curvature and torsion scale space representations. However, due to the multi-scale nature of those representa-tions, an algorithm such as SCALE_SPACE_MATCHER can determine the shift difference between two matching CSS or TSS representations. Criterion: Uniqueness The uniqueness criterion required that two curves with different shapes be mapped to different representations. This is necessary in order to be able to recognize two or more curves with the same shape by observing that their representations are the same. 101 As argued earlier, theorem 3.4.6 shows that a planar curve can be recon-structed from any of its curvature scale space representations and therefore the curvature scale space representations satisfy the uniqueness criterion. Theorem 4.4.6 shows that a space curve can be constructed modulo an equivalence class from any of its torsion scale space representations therefore the torsion scale space representations satisfy the uniqueness criterion with respect to the class of curves defined by theorem 4.4.6. Nevertheless, since torsion scale space represen-tations are very rich representations, it is believed that in practical shape representation and matching tasks, they will be more than enough to distinguish space curves of different shapes from each other. The only arbitrary choice to be made when computing the curvature and torsion scale space representations is the starting point for parametrization on a closed curve. This only causes a horizontal shift in the curvature and torsion scale space representations but it causes no structural change. Criterion: Stability The stability criterion requires that s small change in the shape of a curve lead to a small change in its representation and vice versa. Theorems 3.4.3 and 4.4.3 show that planar and space curves respectively remain connected during evolution and arc length evolution and therefore their curvature and torsion scale space representations can always be constructed. Furthermore, while a planar or space curve evolves, a small change in the standard deviation of the Gaussian filter always results in a small change in the locations of the curvature or torsion zero-crossings on that curve. The experiments of chapter 6 also show that the curvature and torsion scale space representations are stable with respect to significant uniform and non-uniform noise on the curves they represent and there-fore satisfy the stability criterion. Since the representation methods proposed in this thesis involve identification of curvature zero-crossing points on planar curves, it may be con-jectured that they are not suitable for application to curves with straight seg-ments on them. However, it should be noted that while the presence of straight line segments on a curve might introduce instabilities at the finest scale levels, after a small number of iterations the originally straight segments will have non-zero curvature and the computations will stabilize. Figure 6.3.1 shows a planar curve made up of straight line segments and figure 6.3.2 shows the curve of figure 6.3.1 with added random noise. Figure 6.3.3 shows the curvature scale space representation of the curve of figure 6.3.1 and figure 6.3.4 shows the curvature scale space representation of the curve of figure 6.3.2. Figure 6.3.5 shows the superposition of the images shown in figures 6.3.3 and 6.3.4. It can be seen that while there is disagreement between the two representations at the finest scale levels, a very close match exists at the higher levels of the representations. Figure 6.3.1. A planar curve made up of straight line segments 103 Figure 6.3.2. The curve of figure 6.3.1 with added random noise 104 Figure 6.3.3. The curvature scale space image of the curve of figure 105 Figure 6.3.4. The curvature scale space image of the curve of figure 6.3.2 106 Figure 6.3.5. The CSS image shown in figure 6.3.3 superimposed on the CSS image shown in figure 6.3.4 107 The error present on a space curve may be non-isotropic since most sen-sors provide 3D data that is much more accurate in the x and y directions than in the z direction. This type of error can be handled by applying more smoothing to the 2-coordinate than to the x- and y-coordinates. The amount of smoothing for each coordinate can be determined by the variance of the error present on each of the x-, y- and ^ -coordinates. Criterion: Efficiency The computation of the representations proposed here calls for evaluation of a large number of convolutions. As discussed in chapter 5, this process can be rendered efficient using one or more of the following techniques: i. Fast Fourier transforms ii. Parallelism iii. Expression of convolutions involving Gaussians of large widths in terms of convolutions involving Gaussians of small widths only iv. Tracking the curvature and torsion zero-crossing points across multiple scales: when it is known that new curvature zero-crossings will not be created at higher scales, convolutions can be carried out only in a small neighborhood of the existing zero-crossings in order to find the zero-crossings at the next higher level. Furthermore, curvature and torsion scale space representations can be stored very efficiently as encoded binary images. An alternative is to store only a selected subset of points from those scale space representations which will be used for matching. In general, all algorithms proposed are efficient in that their com-plexities are low order polynomials in the size of the input. Criterion: Ease of implementation Specific algorithms for computing the representations discussed in this thesis were given in chapter 5. The procedures needed to compute the curvature and torsion scale space images are not difficult to implement. Convolutions with Gaussian filters are at the heart of the computations. These are standard and well-understood procedures in the computational vision area. It follows that this criterion is also satisfied. Criterion: Computation of shape properties The curvature and torsion scale space representations of symmetric shapes are also symmetric since two symmetric shapes have curvature or torsion zero-crossings at the same locations across scales. Therefore the symmetry criterion is satisfied. Furthermore, curvature and torsion scale space computations are carried 108 out using finite Gaussian filters and making use of finite-sized neighborhoods. Therefore a curvature or torsion scale space representation can also be computed for an open curve and, except near the endpoints of the curve, will resemble the corresponding representation for a closed curve of which it is a part. It is there-fore believed that the representations also satisfy the part/whole criterion. Finally note that Volumetric diffusion [Koenderink & van Doom 1986] and Reactive and diffusive deformations of shape [Kimia et al. 1989] are shape representation techniques which are the most similar to ours since they also com-pute deformations of shapes of two-dimensional and three-dimensional curves. It may therefore be suggested that an alternative way to compute the curvature and torsion scale space representations is to use one of the above techniques to compute deformations of the curves to be represented and then locate curvature and torsion zero-crossing points on each deformed curve and map them to the appropriate representations. However, as noted in chapter 2, the application of each of the techniques mentioned above might result in disconnected curves. In such cases, it will no longer be possible to construct the curvature or torsion scale space representations. Furthermore, our technique combines the curve deforma-tion and the computation of curvature or torsion into one step and is therefore more numerically accurate than the aforementioned techniques which separate the processes of curve deformation and computation of curvature or torsion. It follows that the curvature and torsion scale space representations satisfy nearly all the criteria for general-purpose shape representation methods proposed in chapter 1. t 109 Chapter 7: Summary, Conclusions and Future Directions This chapter contains a summary and the conclusions of this thesis and a discussion of directions for further research. 7 .1. Summary This thesis dealt with the area of shape representation and recognition which is an important area of research within computer vision. The problem of shape representation was considered here for two-dimensional and three-dimensional curves. Two-dimensional curves are boundaries of two-dimensional objects and three-dimensional curves can be considered to be abstract representa-tions of some three-dimensional objects as argued in chapter 4. Chapter 1 proposed a number of criteria considered necessary or useful for any shape representation technique in computer vision. Chapter 2 reviewed several previously proposed shape representation methods for planar curves and discussed ways of generalizing those methods to compute representations of space curves. Each method was also evaluated according to the criteria proposed in chapter 1 . Each method fails to satisfy one or more of those criteria. Chapter 3 proposed a novel theory of multi-scale shape representation for planar curves. A path-based parametric representation of the curve was com-puted and convolved with a Gaussian function of varying width to obtain descriptions of the curve at multiple levels of detail. The curvature zero-crossing points on each curve were identified and mapped to the u-cr space where u is the parameter along the the curve and & is the width of the Gaussian function. Chapter 3 proposed three different versions of the representation, each suitable for particular applications and developed a theory for the proposed 110 representations which provides a sound, theoretical foundation for those represen-tations. The proofs of the theorems of chapter 3 are given in appendix A. Chapter 4 generalized the theory of chapter 3 to propose a theory of multi-scale shape representation for space curves. Multiple descriptions of the curve at varying levels of scale were computed in a similar manner and torsion zero-crossing and curvature level-crossing points on each curve were located and again mapped to u-a spaces. Chapter 4 proposed three different versions of the representation as well and developed a parallel theory for the proposed represen-tations which again provides a sound, theoretical foundation for those representa-tions. The proofs of the theorems of chapter 4 are given in appendix B. Chapter 5 discussed the implementation issues associated with the task of implementing the shape representation theories proposed in chapters 3 and 4. Procedures to sample the input curves and to compute the Gaussian masks for convolution were described and algorithms for computing the regular, renormal-ized and resampled curvature and torsion scale space images were given. Com-plexity analyses for those algorithms were also presented. Finally, chapter 6 presented a number of examples of planar and space curves used as input to the programs and the curvature and torsion scale space representations of those curves. Experiments were carried out to study the behaviour of the representations when considerable noise was added to the input curves and to illustrate the particular applications for which each representation is useful. The significance of the theoretical results of chapters 3 and 4 were also demonstrated. Chapter 6 ended with an evaluation of the curvature and torsion scale space representations proposed in this thesis according to the criteria pro-posed in chapter 1. It was shown that the proposed representations satisfy nearly all of the criteria. 7 . 2 . Conclusions The contribution of this thesis is to present a theory of shape representa-tion for planar and space curves. The representations are referred to as the curva-ture and torsion scale space images and are general-purpose because they satisfy a number of criteria that are considered useful for general-purpose shape representations. They are nearly invariant with respect to the shape-preserving transformations of the curves since they make use of invariant geometric proper-ties of the curves and experiments indicate that they are stable with respect to even severe uniform or non-uniform random noise on the curves because they combine information about the curves at a continuum of scales. Furthermore, they represent curves uniquely since it is possible in theory to reconstruct those curves using their representations (modulo uniform scaling and a rigid motion in case of planar curves and modulo a larger class in case of space curves). These Ill properties make the representations very useful for shape recognition tasks. A new and efficient scale space matching algorithm was also presented. The theoretical results of this thesis significantly contribute to a proper understanding of the proposed representations. These results define the properties of both the representations and the underlying processes of evolution and arc length evolution. It follows from theorems 3.4.1 and 4.4.1 that the representa-tions are in fact invariant with respect to shape preserving transformations of the curves they represent. Theorems 3.4.2 and 4.4.2 show that (arc length) evolution preserves closedness of planar and space curves and therefore does not change the physical interpretation of those curves as boundaries of objects. Theorems 3.4.3 and 4.4.3 are very important since they show that connectedness of planar and space curves is preserved by (arc length) evolution. As a result, it is always possi-ble to construct the curvature and torsion scale space representations. Theorems 3.4.4, 3.4.5, 4.4.4 and 4.4.5 impose strong constraints on the location of planar and space curves during (arc length) evolution. These constraints are useful for matching of image curves at multiple scales. Theorems 3.4.6 and 4.4.6 show that the curvature and torsion scale space images in fact uniquely represent the curves they are computed from. This property is crucial for matching and distinguishing shapes from each other. Theorems 3.4.7 and 4.4.7 make explicit the conditions under which new curvature or torsion zero-crossings will not be created in scale space representations. They can be used to speed up the computation of those representations by tracking the zero-crossings across scales. Theorem 3.4.9 shows that arc length evolution has further physical plausibility since it preserves the simplicity of planar curves. Theorems 3.4.8, 3.4.10, 4.4.8 and 4.4.9 together locally characterize the behaviour of planar and space curves just before and after the creation of cusp points during (arc length) evolution. Theorems 3.4.7, 3.4.8 and 3.4.9 also combine to conclude that no new curvature zero-crossings are created during arc length evolution of simple curves. Finally, theorem 4.4.10 shows that new torsion zero-crossings can form on smooth space curves during (arc length) evolution. Together with theorem 4.4.9, they describe all conditions under which new torsion zero-crossings can appear on space curves during (arc length) evolution. This information can also be used to speed up the compution of the torsion scale space representation by tracking of torsion zero-crossings whenever possible. 7.3. Directions for future research The following are a number of possible areas of research that are related to the curvature and torsion scale space representations for planar and space curves proposed in this thesis. • In order to complete the theoretical results which form a sound foundation for 112 the representations, it would be useful to show that the curvature and torsion scale space representations proposed here have desirable convergence proper-ties. Observations show that a planar curve eventually becomes simple and convex after undergoing a process of evolution or arc length evolution and that once such a curve becomes simple and convex, it will always remain simple and convex. This implies that the search for curvature zero-crossing points can stop as soon as the curve becomes simple and convex. Gage and Hamilton [1986] have shown that simple and convex planar curves remain simple and convex during arc length evolution. Other properties remain to be shown for-mally. Similarly, observations show that a space curve eventually enters a state in which each of the two-dimensional curves obtained by disregarding one of its coordinate functions, is simple and convex and in which it has few torsion zero-crossing points after undergoing a process of evolution or arc length evolution. Observations further show that once such a curve enters that state, it will always remain in that state. Again, this implies that the search for torsion zero-crossing points can stop as soon as that state is reached. These properties also remain to be shown formally. • For both theoretical and practical reasons, it would be interesting to fully gen-eralize the shape representation theory proposed in this thesis and apply it to three-dimensional surfaces. In such an approach, the surface would be parametrized in an appropriate way and convolved with a two-dimensional Gaussian function to obtain descriptions of the surface at multiple levels of detail. Contours of zero curvature can then be identified on each surface and mapped to a suitable generalized scale space. The result would be a multi-scale, geometric-based representation of the shape of that surface. Results about the local, global and convergence properties of the surface during evolu-tion as well as the uniqueness properties of its representation would constitute a sound theoretical foundation for such a representation. A matching algo-rithm to find good matches of two such representations would also be useful. • The aim of this thesis has been to solve the curve representation problem but not the segmentation problem. In other words, it is assumed that the curves to be represented have been satisfactorily segmented beforehand. However, the tools developed in this thesis can also be used to tackle the segmentation prob-lem. For example, Lowe [1988] computed curvature on Gaussian smoothed image curves and segmented those curves at points where the rate of change of curvature was high. More work should be done towards the application of the tools developed in this thesis to the segmentation problem. • Theorem 3.4.6 states that the derivatives at a single point on a curvature zero-crossing contour in the curvature scale space image of a planar curve 113 determine that curve uniquely up to uniform scaling and a rigid motion. The proof of that theorem provides us with a constructive algorithm. It would be interesting to actually attempt such a reconstruction and determine the condi-tions under which it can be made stable with respect to noise. A similar argu-ment applies to theorem 4.4.6. • The curve description and recognition methods developed in this thesis should be further applied to practical vision problems. Recognition of characters, shorelines in aerial images [Mokhtarian & Mackworth 1986] and organisms in microscopic images as well as handwriting analysis are examples of problems which can be attacked using the tools developed here. Stereo matching should also be easier by first using an edge detector to extract image edges at a fine level of detail and then using our method to describe the candidate curves at coarse levels of scale where unnecessary detail has been removed and matching is more efficient and more reliable. This method would have clear advantages over blurring the image since image-blurring followed by edge detection totally removes many of the candidate curves and results in the joining of curves from unrelated parts of the image which complicates the matching problem. It would also be advantageous to develop a new matching algorithm to match curvature and torsion scale space images since the matching algorithm in [Mokhtarian & Mackworth 1986] makes assumptions about curvature scale space representations which are not always true as pointed out in chapter 5. The matching algorithm in [Witkin et al. 1987] provides an example of a multi-scale signal matching algorithm. It may be possible to generalize some of the concepts employed in that algorithm to the matching of curves. The matching algorithm in [Kishon Sz Wolfson 1987] provides an example of a curve matching algorithm but it can have problems when scale changes exist between an observed curve and a model curve and when noise exists on the observed curve. Algorithm SCALE_SPACE_MATCHER proposed in chapter 5 should run considerably faster than the algorithm in Mokhtarian and Mack-worth [1986]. It also does not make possibly incorrect assumptions about the structure of a scale space representation. In summary, this thesis proposes multi-scale, geometric-based, shape representations for planar and space curves. A number of important theoretical issues about those representations have been investigated and as a result, their properties are well-understood. A number of experiments have also been carried out on them in order to illustrate their practical utility under various noise condi-tions. It has also been shown that the proposed representations satisfy a number of criteria considered useful for shape recognition tasks. Finally, several directions for future research have been outlined. 114 References Agin, G. J. and T. O. Binford, "Computer description of curved objects," Proc. IJCAI, pp. 629-640, Palo Alto, CA, 1973. Aho, A. V., J. E. Hopcroft, and J. D. Ullman, The design and analysis of com-puter algorithms, Addison-Wesley, Reading, MA, 1974. Asada, H. and M. Brady, "The curvature primal sketch," IEEE PAMI, vol. 8, pp. 2-14, 1986. Babaud, J., A. P. Witkin, M. Baudin, and R. O. Duda, "Uniqueness of the Gaus-sian kernel for scale space filtering," IEEE PAMI, vol. 8, pp. 26-33, 1986. Ballard, D. H., "Generalizing the Hough transform to detect arbitrary shapes," Pattern Recognition, vol. 13, pp. 111-122, 1981. Ballard, D. H. and C. M. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, NJ, 1982. Barnard, S. T. and A. P. Pentland, "Three-dimensional shape from line draw-ings," Proc. IJCAI, pp. 1062-1064, Vancouver, B.C., 1983. Barnhill, R. E. and R. F. Riesenfeld, Computer Aided Geometric Design, Academic Press, New York, 1974. Bentley, J. L., "Multidimensional search trees used for associative searching," Comm. ACM, vol. 18, no. 9, pp. 509-517, 1975. Blum, H., "Biological shape and visual science (part I)," J. Theoretical Biology, vol. 38, pp. 205-287, 1973. Brady, M., J. Ponce, A. L. Yuille, and H. Asada, "Describing surfaces," AI memo 822, MIT AI Lab, Cambridge, MA, 1985. Brown, C. M., "Two descriptions and a two-sample test for 3-d vector data," TR 49, Computer Science Dept., Univ. Rochester, 1979. Choi, D. J. and J. R. Render, "Solving the depth interpolation problem on a parallel architecture with a multigrid approach," Proc. CVPR, pp. 189-194, 115 Ann Arbor, Michigan, 1988. Danielsson, P. E., "A new shape factor," CGIP, vol. 7, pp. 292-299, 1978. Davis, L. S., "Understanding shape: Angles and sides," IEEE Trans. Computers, vol. C-26, pp. 236-242, 1977. DeBoor, C , A practical guide to splines, Springer-Verlag, New York, 1978. DoCarmo, M., Differential geometry of curves and surfaces, Prentice-Hall, Engle-wood Cliffs, NJ, 1976. Duda, R. 0. and P. E. Hart, "Use of the Hough transformation to detect lines and curves in pictures," Comm. ACM, vol. 15, pp. 11-15, 1972. Faugeras, 0. D., et al, "Object representation, identification and positioning from range data," in First International Symposium on Robotics Research, ed. R. Paul, pp. 425-446, MIT press, 1984. Faugeras, 0. D. and J. Ponce, "Prism trees: a hierarchical representation for 3-D objects," Proc. IJCAI, pp. 982-988, Vancouver, B.C., 1983. Freeman, H., "Computer processing of line-drawing images," Comput. Surveys, vol. 6, 1974. Gage, M. and R. S. Hamilton, "The heat equation shrinking convex plane curves," J. Differential Geometry, vol. 23, pp. 69-96, 1986. Gallus, G. and P. W. Neurath, "Improved computer chromosome analysis incor-porating preprocessing and boundary analysis," Physics in Medicine and Biology, vol. 15, p. 435, 1970. Goetz, A., Introduction to differential geometry, Addison-Wesley, Reading, MA, 1970. Grimson, W. E. L., "Computational experiments with feature based stereo algo-rithm," IEEE PAMI, vol. 7, pp. 24-27, 1985. Haralick, R. M., A. K. Mackworth, and S. L. Tanimoto, "Computer vision update," Handbook of Al, vol. IV, Ed. A. Barr, Addison-Wesley, N. Y., 1989. Hong, J. and X. Tan, "Recognize the similarity between shapes under affine transformation," Proc. ICCV, pp. 489-493, Tarpon Springs, Florida, 1988. Horn, B. K. P. and E. J. Weldon, "Filtering closed curves," IEEE PAMI, vol. 8, pp. 665-668, 1986. Horowitz, S. L. and T. P. Pavlidis, "Picture segmentation by a tree traversal algorithm," J. ACM, vol. 23, pp. 368-388, 1976. 116 Hough, P. V. C , "Method and means for recognizing complex patterns," U.S. patent 3 069 654, 1962. Hummel, R. A., B. Kimia, and S. W. Zucker, "Deblurring Gaussian blur," CVGIP, vol. 38, pp. 66-80, 1987. Ikeuchi, K. and B. K. P. Horn, "Numerical shape from shading and occluding boundaries," Artificial Intelligence, vol. 17, pp. 141-184, 1981. Jackins, C. L. and S. L. Tanimoto, "Oct-trees and their use in representing three-dimensional objects," CGIP, vol. 14, no. 3, pp. 249-270, 1980. Kecs, W., The convolution •product and some applications, D. Reidel, Boston, MA, 1982. Kimia, B. B., A. Tannenbaum, and S. W. Zucker, "Toward a computational theory of shape: an overview," TR-CIM-89-13, McGill University, 1989. Kishon, E. and H. Wolfson, "3-D curve matching," TR 283, Courant Inst. Math. Sciences, New York University, 1987. Koenderink, J. J. and A. J. van Doorn, "Dynamic shape," Biological Cybernetics, vol. 53, pp. 383-396, 1986. Lowe, D., "Organization of smooth image curves at multiple scales," Proc. ICCV, pp. 558-567, Tampa, Florida, 1988. Mackworth, A. K. and F. Mokhtarian, "The renormalized curvature scale space and the evolution properties of planar curves," Proc. IEEE CVPR, pp. 318-326, Ann Arbor, Michigan, 1988. Marr, D., "Early processing of visual information," Proc. R. Soc. Lond. B, vol. 275, pp. 483-519, 1976. Marr, D., "Representing visual information," AI memo 415, MIT AI Lab, 1977. Marr, D. and E. C. Hildreth, "Theory of edge detection," Proc. R. Soc. Lond. B, vol. 207, pp. 187-217, 1980. Marr, D. and H. K. Hishihara, "Representation and recognition of the spatial organization of 3D structures," Proc. R. Soc. Lond. B, vol. 200, pp. 269-294, 1978. McKee, J. W. and J. K. Aggarwal, "Computer recognition of partial views of curved objects," IEEE Trans. Computers, vol. C-26, pp. 790-800, 1977. Mokhtarian, F. and A. K. Mackworth, "Scale-based description and recognition of planar curves and two-dimensional shapes," IEEE PAMI, vol. 8, pp. 34-43, 1986. 117 Mokhtarian, F., "Multi-scale description of space curves and three-dimensional objects," Proc. IEEE CVPR, pp. 298-303, Ann Arbor, Michigan, 1988a. Mokhtarian, F., "Evolution properties of space curves," Proc. ICCV, pp. 100-105, Tarpon Springs, Florida, 1988b. Mokhtarian, F., "Fingerprint theorems for curvature and torsion zero-crossings," Proc. IEEE CVPR, pp. 269-275, San Diego, California, 1989. Nahin, P. J., "The theory and measurement of a silhouette descriptor for image preprocessing and recognition," Pattern Recognition, vol. 6, no. 2, 1974. Nishihara, H. K., "Intensity, visible-surface, and volumetric representations," Artificial Intelligence, vol. 17, pp. 265-284, 1981. O'Rourke, J. and N. I. Badler, "Decomposition of three-dimensional objects into spheres," IEEE PAMI, vol. 1, 1979. O'Rourke, J. and R. Washington, "Curve similarity via signatures," in Computa-tional geometry, G. Toussaint (Ed.), North-Holland, Amsterdam, 1985. Pavlidis, T., "Segmentation of pictures and maps through functional approxima-tions," CGIP, vol. 1, pp. 360-372, 1972. Pavlidis, T., "Waveform segmentation through functional approximation," IEEE Trans. Comput, vol. C-22, pp. 689-697, 1973. Pavlidis, T., "Optimal piecewise polynomial L 2 approximation of functions of one and two variables," IEEE Trans. Comput, vol. C-24, pp. 98-102, 1975. Pavlidis, T., "Polygonal approximations by Newton's method," IEEE Trans. Computers, vol. C-26, pp. 800-807, 1977. Pavlidis, T., Structural Pattern Recognition, Springer-Verlag, New York, 1977. Pavlidis, T. and S. L. Horowitz, "Segmentation of plane curves," IEEE Trans. Comput, vol. C-23, pp. 860-870, 1974. Persoon, E. and K. S. Fu, "Shape discrimination using Fourier descriptors," Proc. IJCPR, pp. 126-130, Copenhagen, Denmark, 1974. Requicha, A. A. G., "Representations of rigid solid objects," Computer Surveys, vol. 12, no. 4, 1980. Richard, C. W. and H. Hemami, "Identification of 3D objects using Fourier descriptors of the boundary curve," IEEE Trans, on Systems, Man, and Cybernetics, vol. SMC-4, no. 4, pp. 371-378, 1974. Roberts, L. G., "Machine perception of three-dimensional solids," In Optical and electro-optical information processing, Eds. J. P. Tippett et al., MIT press, 118 Cambridge, MA, 1965. Samet, H., "Region representation: quadtrees from boundary codes," Comm. ACM, vol. 23, pp. 163-170, 1980. Saund, E., "Adding scale to the primal sketch," Proc. IEEE CVPR, pp. 70-78, San Diego, California, 1989. Schneier, M., "Linear time calculations of geometric properties using quadtrees," TR 770, Computer Science Center, Univ. Maryland, 1979. Schwartz, E. L., R. Desimone, T. Albright and C. G. Gross, "Shape recognition and inferior temporal neurons," Proc. of the National Academy of Sciences, 1983. Shahraray, B. and D. J. Anderson, "Optimal estimation of contour properties by cross-validated regularization," IEEE PAMI, vol. 11, no. 6, pp. 600-610, 1989. Shirai, Y., "Analyzing intensity arrays using knowledge about scenes," In PCV, 1975. Sklansky, J. and D. P. Kibler, "A theory of non-uniformly digitizing binary pic-tures," IEEE Trans. SMC, vol. 6, no. 9, pp. 637-647, 1976. Stansfield, J. L., "Conclusions from the commodity expert project," AI memo 601, MIT AI Lab, Cambridge, MA, 1980. Stevens, K. A., "Implementation of a theory for inferring surface shape from con-tours," AI memo 676, MIT AI Lab, Cambridge, MA, 1982. Szeliski, R., "Fast surface interpolation using hierarchical basis functions," Proc. CVPR, pp. 222-228, San Diego, CA, 1989. Terzopoulos, D., Multiresolution computation of visible-surface representations, PhD thesis, MIT, Cambridge, MA, 1984. Tomek, I., "Two algorithms for piecewise linear continuous approximation of functions of one variable," IEEE Trans. Computers, vol. 23, no. 4, pp. 445-448, 1974. Turner, K. J., "Computer perception of curves objects using a television camera," Ph.D. dissertation, Univ. Edinburgh, 1974. Voelcker, H. B. and A. A. G. Requicha, "Geometric modeling of mechanical parts and processes," Computer, vol. 10, pp. 48-57, 1977. Wahba, G., "A survey of some smoothing problems and the method of general-ized cross-validation for solving them," in Applications of Statistics, P. R. Krishnaiah, Ed., North-Holland, Amsterdam, The Netherlands, pp. 507-523, 119 1977. Watson, L. T. and L. G. Shapiro, "Identification of space curves from two-dimensional perspective views," IEEE PAMI, vol. 4, pp. 469-475, 1982. Weiss, I., "3-D shape representation by contours," Proc. IJCAI, pp. 969-972, Los Angeles, CA, 1985. Witkin, A. P., "Recovering surface shape and orientation from texture," Artificial Intelligence, vol. 17, pp. 17-45, 1981. Witkin, A. P., "Scale space filtering," Proc. IJCAI, pp. 1019-1023, Karlsruhe, W. Germany, 1983. Witkin, A., D. Terzopoulos, and M. Kass, "Signal matching through scale space," IJCV, vol. 1, pp. 133-144, 1987. Woodham, R. J., "Photometric method for determining shape from shading," in Image Understanding 1984, e d. W. Richards, pp. 97-125, Ablex publishing corp., Norwood, NJ, 1984. Yuille, A. L. and T. A. Poggio, "Fingerprint theorems for zero crossings," AI Memo 730, MIT AI Lab., Cambridge, MA, 1983. Yuille, A. L. and T. A. Poggio, "Fingerprint theorems," Proc. AAAI, pp. 362-365, Austin, Texas, 1984. Yuille, A. L. and T. A. Poggio, "Scaling theorems for zero-crossings," IEEE PAMI, vol. 8, pp. 15-25, 1986. 120 Appendix A: Proofs of Results on Planar Curves v This appendix contains the proofs of the theorems of chapter 3. The proofs of the theorems 3.4.1 - 3.4.5 have been given for arc length evolution only since the proofs for regular evolution are similar and simpler. Theorems 3.4.6 and 3.4.7 have been shown to hold for regular, renormalized and resampled curvature scale space images. Furthermore, theorems 3.4.8 and 3.4.10 have been shown to hold for both regular and arc length evolution. Proof of theorem 3.4.1: It will be shown that arc length evolution is invariant under a general affine transform. Let Ta = (X( W,cr), Y( W,cr)) be an arc length evolved version of F = (x(w),y(w)). If Tff is transformed according to an affine transform, then at its new coordinates, X-± and Yi, are given by Xx( W,a) = aX( W,a) + b Y( W,a) + c yj( W,a) = dX( W,a) + e Y( W,a) + f. Now suppose T is transformed according to an affine transform and then evolved. The coordinates X2 and Y2 of the new curve are X2(W,a) = (ax(W) + by(W) + c) ®g(W,cr) Y2(W,o) = (dx{W) + ey{W) + f) ®g{W,o). Since the convolution operator is distributive [Kecs 1982], it follows that X2{W,o) = XyiW,*) Y2(W,a)= Y^W,a) 121 a n d t h e t h e o r e m follows. • Proof of theorem 3.4.2: L e t T = (x(w),y(w)) be a closed c u r v e a n d let = ( X ( W,cr), Y{W,o) be a n a r c l e n g t h e v o l v e d v e r s i o n of T. O n T: (x(0),»(0)) = (x(l),i<l)). O n T , : (X(0,Cr), F(0,(7)) = (X(l,Cr), It fol lows t h a t T^. is closed. • Proof of theorem 3.4.3: L e t T = (x(w),y(w)) be a c o n n e c t e d p l a n a r c u r v e a n d Tg. = (X(W,cr),Y(W,cr)) be a n arc l e n g t h e v o l v e d v e r s i o n of t h a t c u r v e . S i n c e T is c o n n e c t e d , x(w) a n d y(w) are c o n t i n u o u s f u n c t i o n s a n d therefore X( W,o~) a n d Y{ W,o~) are also c o n t i n u o u s . L e t WQ be a n y v a l u e of p a r a m e t e r W a n d let x0 a n d y0 be t h e v a l u e s o f X( W,a) a n d Y( W,cr) at W0 respect ively . If W goes t h r o u g h a n i n f i n i t e s i m a l c h a n g e , t h e n X( W,a) a n d Y( W,a) w i l l also go t h r o u g h i n f i n i t e s i m a l changes: X(W0,<r)-> xo + 6 Y(W0,a) -> y0 + e. A s a r e s u l t , p o i n t P(x0,y0) o n I V goes to p o i n t P'(x0 + 6, yo + 0- * n e d i s t a n c e b e t w e e n P a n d P ' b e D . T h e n D = VFTW < SV2 a s s u m i n g |cS| is t h e larger of \6\ a n d |^|. It fol lows t h a t a n i n f i n i t e s i m a l c h a n g e i n p a r a m e t e r W also results i n a n i n f i n i t e s i m a l c h a n g e i n the v a l u e of t h e v e c t o r -v a l u e d f u n c t i o n Ta. T h e r e f o r e Ya is a c o n n e c t e d c u r v e . • Proof of theorem 3.4.4: L e t M b e t h e c e n t e r of mass of V — (x(w),y(w)) w i t h c o o r d i n a t e s (xj^,yM). T h e n 1 fx(w)dw j xM = —x = fx(w)dw fdw o 122 1 fy(w)dw 1 yM = —x = fy(w)dw. fdw 0 Let Tg. = (X( W,a), Y{ W,a)) be an arc length evolved version of T with N = (XN,YN) as its center of mass. Observe that 1 1 O O O O j XN = Jx(W,a)dW = f J g(v,a)x(W-v)dvdW = / g(v,o)(fx( W-v)dW)dv 0 0 -oo -oo 0 W covers Vg. exactly once. Therefore l Jx(W-v)dW= xM_ o So XN = XM. Similarly YN ' VM. It follows that M and N are the same point. • Proof of theorem 3.4.5: Since G is simple and convex, every line L tangent to G contains that curve in the left (or right) half-plane it creates. Since T is inside G, T is also contained in the same half-plane. Now rotate L and V so that L becomes parallel to the y axis. L is now described by the equation x = c. Since L does not intersect T, it follows that x(w0)>c for every point wQ on T. Let T^ be an arc length evolved version of T. Every point of ra is a weighted average of all the points of T. Therefore X(W0,a)>c for every point W0 on and is also contained in the same half-plane. This result holds for every line tangent to G therefore Tff is contained inside the intersection of all the left (or right) half-planes created by the tangent lines of G. It follows that is also inside G. • Proof of theorem 3.4.6: The proof will first be given for the regular curvature scale space of T, then the modifications needed to apply the same proof to the resampled and renormalized curvature scale space images will be explained. The proof of this theorem for the regular curvature scale space image only was first given in [Mokhtarian 1989]. Section i shows that the derivatives at a point on a curvature zero-crossing contour provide homogeneous equations in the moments of the Fourier transforms of the coordinate functions of the curve. Section ii shows that the 123 moments are related to the coefficients of expansion of the coordinate functions of the curve in functions related to the Hermite polynomials. Section iii shows that the moments at one curvature zero-crossing point can be related to the moments at other curvature zero-crossing points. Section iv shows that the quadratic equations obtained in section i can be converted into a homogeneous linear sys-tem of equations which can be solved uniquely for the curvature function of the curve. i. Constraints from the curvature zero-crossing contours Let r = (x(u), y(u)) be the arc-length parametrization of the curve with Fourier transform T = (x(u)),y(uj)). The Fourier transform of the Gaussian filter G(u,t) = —Le-'' 2/ 4' is G{u) = t^K Let = (x(u, t0), y(u, <0)) be a curve obtained by convolving x(u) and y(u) with G(u, <Q). Assume that is in C^. Such a t0 exists since T is in C\. The curvature zero-crossings in a neighborhood of t§ are given by solutions of a(u, t) = 0 where a(u,t) = x(u,t)y(u,t) - y(u,t)'x(u,t) where . represents derivative with respect to u. Using the convolution theorem, the terms in a(u, t) can be expressed as following: x(u, t) = J y\u,t) = J y(u, t) = J x(u, t) = J e-^'e*"u(-w2)i(u;)(L;. The Implicit Function Theorem guarantees that the contours u(t) are in a neighborhood of tQ. Let £ be a parameter of the curvature zero-crossing con-tour. Then d du d _dt_ d di di du di dt dk On the curvature zero-crossing contour, a = 0 and — - a = 0 for all integers k. dik Furthermore, since the curvature zero-crossing contour is known, all the deriva-tives of u and t with respect to i are known as well. 124 We can now compute the derivatives of a with respect to £ at (u0, ig). The first derivative is given by: • | - « ( « o , < b ) = - j j j K / t ^ t ^ i i w f y ^ ) ^ J t^t»Xiu)xXu>)fa (A.l) _ J e-^ e^u(iu;) 3x(w)(L) f e^2te™u(iu)y(u)dJ) - fe-^'e^^xi^daj Je^e^i^yi^dJ) . Note that the moment of order k of function /(w) = e^tew\kS)x\u}) is defined by: oo 1 Mk= J (*j)*e^;"u(iw)x(w)Aj — O O and the moment of order & of function /'(u>) = e~ L^ teMU(iu;)y(Lj) is defined by: O O \ p. i Affc = J ( iw)*e^> u (««;)j f (u;)<L;. As a result, equation (A.l) can be re-written as: k) = ^ ( ^ M n - M 2 MJ) (A.2) + •^ • (J f 2 J f J + M'ZMQ - M2M, - M3Mo). dt. Furthermore, the second derivative is given by: ^"K, <o) = ^t(MM - M2M$ (A.3) 125 In general, the &+lst equation, ——£a(u, t) — 0 is a quadratic equation in the first + ^(M2Mi + M^MQ - M'2MX - M3M^) + (±L)\M^MQ + MXM'2-M%M'Z-M'XM2) + 2-^j±(M^M0 - MM) + 2{M^M[ + 2M'3M2 + M'SMQ- M'^MX - 2M3M2 - M5MQ). v d ? Since the parametric derivatives along the curvature zero-crossing contours are zero, equations (A.2) and (A.3) are equal to zero. Note that equation (A.2) is a quadratic equation in the first four moments of functions f(u>) and f'(oj) and equation (A.3) is a quadratic equation in the first six moments of those functions. de 2k+2 moments of each of the functions /(w) and f'(uj) or a total of 4&-f4 moments. Our axes are chosen such that w0 = 0. The next section shows that the moments of f(u>) and /'(u;) are the coefficients ak and bk in the expression of functions x(u) and y(u) in functions related to the Hermite polynomials. There-fore, having computed the first n derivatives of a at (uQ, tQ), we have n+1 homo-geneous equations in the first 4n+4 coefficients ak and bk. To determine the ak and bk, we need 3ra+3 additional and independent equations which can be pro-vided by considering three neighboring curvature zero-crossing contours at ii. The moments and the coefficients of expansion of x(u) and y{u) This section shows that the moments and the moment-pairs in equations dk —-a(u,t) are related respectively to the coefficients of the expression of the func-^ • tions y(u) and the curvature function of V, K ( U ) , in functions related to the Hermite polynomials. Expand function x(u) = -~x(u) du in terms of the functions <f>k(%a) related to the Hermite polynomials Hk(u) by 126 Hk(u) = ( - l ) k e ^ e ^ x(u) =Y,H(cr)<l)k(u^)-The coefficients ak(o~) of the expansion are given by «jfc0) = <wk(u,a),x(u)> where <,> denotes inner product in L2 and {wk(u,cr)} is the set of functions biorthogonal to {<f>k(u,a)}. The {^j.(u,cr)} are given explicitly by 2Jb-l — jk -— U^<r) = —=e2a — e 2° k\ v 27r dvr and the wk(u,o) by Since wk(u,a) = ( - 1 ) * — e x(u) = -4= f e™\iu)x{u) dw the ak are given by V27T * du" The inner product is just the inverse Fourier transform of wk(u,cr). Therefore V < T 2 ak(a) = j(iu)ke 2 (iu) x(u>) dut 2 which is equal to Mk modulus a factor e^ ", since t = —. 2 Similarly, the function M = -7-2/0) du can be expanded in terms of the functions (f>k(u,a) by y(u) =Y,bk(a)<f>k(u,a) and it again follows that bk(a) = J(iu)ke 2 (iu)y(u)<kj which is equal to M'k modulus a factor ewu. 127 Furthermore, a'k(cx) and b'k(er), the coefficients of expansion of functions x\u) and y(u) in terms of the functions <f>k(u,a), can be seen to be related to ak(o~) and bk(a) according to the following relationships: 4-1 = ak{a) h'k-\ = h(°)-Therefore K(U), the curvature function of T can be expressed as: K(U) = x(u)'y\u) - y(u)x(u) = YI ak(v)<t>k(u,<7). E 6 f c ( a )^ (^ c r ) - S hWM^v) I] 4(°')^ik(«> c r) = JJ X aM)b'k(^)(l>j(u^a)<f>k(u^) - S S. hj(a)ak(a)<l>i(u,°)<l>k(u,o) = S S (aj(a)6*+lO) - 6 ; ( c r ) a H l ( c r ) ) ^ ( ^ 0 ' ) ^ ( ^ 0 ' ) -It follows that if the pairs a}{o-)bk(o-), j,k — 0, • • • ,2n+l, are all known, the curva-ture function of T can be reconstructed. iii. Combining information from more than one contours To solve the system of equations obtained in section i, we need to obtain additional equations from other points of the curvature scale space image and relate them to the equations obtained from the first point. Suppose additional equations are obtained in the moments of functions tetJU (iu>)x(u}) and e^U"u\iw)yXu;) at point O',*0)- W e h a v e x(u+u') = Je™e»u\iu)xlu>)du = £ ckcf>k(u) and . y(u+u') = J\™e™\iw)y{u)<Lo = J] dk<f>k(u). Now observe that Yi ck<l>k{u) = X) akfa(u+u') and That is, <j)k(u+u) can be expressed as a linear combination of (f>3(u) with j<k as has been shown in [Yuille and Poggio 1983]. 128 iv. Reconstructing the curvature function It was shown in section I that four points from four curvature scale space contours give us 4n+4 equations in the first 2n+2 moments of each of the func-tions f(u>) and f'(u>). The first n+1 equations form a system of homogeneous qua-dratic equations in the unknowns: M0(u), • • • , Af 2 n + 1 (u) . and Mo(u)> ' ' ' >^2n+i(u)- The other points, u+u^ l<k<3, provide additional equations in the unknowns: M0(u+uk), • • • , Af2n+l(u+uJt) aXi^-MQ(u+uk), • • • , M2n+1(u4-tijfc). As shown in section iii, the moments at u+u^ can be expressed as a linear combination of the moments at u. Therefore it is possible to express all the equations in terms of the moments at u. The result is a system of 4n+4 homogeneous quadratic equations in 4n+4 unknowns. That system has at least one solution since the moments of order higher than 2n+l of and f'(<jj) are assumed to be zero. However, the solution obtained from a quadratic system of equations is in general not unique. Equations (A.2) and (A.3) can be converted into homogeneous linear equa-tions by assuming that each moment-pair appearing in those equations is a new variable. Table (A.l) shows the moment-pairs in equations (A.2) and (A.3). The 4- signs designate the moment-pairs in equation (A.2) and the 4- and x signs together designate the moment-pairs in equation (A.3). M Q M 2 M 3 M'A M'5 + + X X Mi + X M2 + + X M 3 + X M 4 X X M5 X Table A. l . Moment-pairs in equations (A.2) and (A.3) Note that all other moment-pairs in table (A.l) can be computed from the exist-ing ones using the following relationships: MM'- M ^ M ' r M i M * i _ M , - + I M ; . ^ M ; + 1 ^ Mjti^.MuM'j MjM^.M^M} • j M^M'^ Mi+1M'm M^M'^ M m M ' H As before, we proceed to compute the first n derivatives at point (^0,^0) on one of the curvature zero-crossing contours. We now obtain n4-l homogeneous linear equations in some of the moment-pairs M{Mj by assuming that each moment-pair is a new variable. 129 Since this system is in terms of the first 2n+2 moments of functions f(u>) and f'(w), it w m contain 0(n2) moment-pairs. Therefore additional equations are required to constrain the system. To obtain those equations, we proceed as fol-lows: Assume that moments of order higher than 2n+2 are zero. Compute derivatives of order higher than n at (^0,^0) but set moments of order higher than 2n + 2 to zero in the resulting equations. If a sufficient number of derivatives are computed at (uQ,tQ), the number of equations obtained will be equal to the number of moment-pairs and our linear system will be constrained. It follows from an assumption of generality that the system will have a unique zero eigenvector and therefore a unique solution modulus scaling. Once the moment-pairs in the system are known, all other moment-pairs can be com-puted from the known ones using the relationships given above. Since all the moment-pairs M,Mj together determine the curvature function of the curve, it follows that the curve can be determined modulus a rigid motion and constant scaling. Yuille and Poggio [1983] have shown that a 1-D signal can be recon-structed using two points from its scale space image. Note that our result implies that only one point is sufficient for the reconstruction of that signal. The theorem has now been proven for the regular curvature scale space image. To prove the same result about the resampled curvature scale space, recall that derivatives at one point (at any scale) on any curvature zero-crossing contour in the curvature scale space of T were computed and it was shown that the resulting equations can be solved for the coefficients of expansion of the cur-vature function of T in functions related to the Hermite polynomials. As before, we choose a point on a zero-crossing contour at any scale of the resampled curvature scale space image of V and compute the necessary deriva-tives. The value of a in the resulting equations is then set to zero. Consequently, the arc length evolved curve Tff, where a corresponds to the scale at which the derivatives were computed, is reconstructed modulus uniform scaling, rotation and translation. The next step is to recover the original curve I\ This is done by applying reverse arc length evolution to Va. Let the arc length evolved curve Tff be defined by: T, = {(X(W,o-),Y(W,cr))\We [0,1]} . A reverse arc length evolved curve T is defined by: T = {(x(w),y(w))\w e [0,1]} where 130 x(w) = X(w,a) ©D^^cr) y(w) = Y(w,a) ®Dflw,(j) where DN is a deblurring operator defined in [Hummel et al. 1987] and a w 0 0 As a result, T is recovered modulo uniform scaling, rotation and translation. To prove the same result about the renormalized curvature scale space image, evolved curve Tff is again reconstructed. Then each of its coordinate func-tions is deblurred by convolving it with the deblurring operator DN. Once again T Proof of theorem 3.4.7: Since by assumption all evolved and arc length evolved curves are in C 2, the conditions of the implicit function theorem are satisfied on contours K(U,(T), «(w,cr) and K(W,CT) = 0 in the regular, renormalized and resampled curvature scale space images of T. Since the proofs are identical, the theorem will be proven here for the regular curvature scale space image. On any contour in the curvature scale space image is recovered modulo uniform scaling, rotation and translation. • K(U,CT) = 0. Since all are in C 2 this is equivalent to: X{u,o)Y(u,a)-X(u,a)Y(u,o) = 0. To exploit the properties of the heat equation (Hummel et al, 1987), it is con-venient to change variables and let So we define x(u,t) = X(u,(j) y(u,t) = Y(U,(T) a(u,t) = xu(u,t)yuu(u,t) - xuu(u,t)yu(u,t). (AA) 1 3 1 XuuM = xt(U^) (A-5) 2/«u(M) = (A.6) On contours a (u,t) = 0: t(u) = t = flu) dt _ ~ a u du at The theorem will be proven if we can show that for all points such that t(u) = 0 we have t (u) < 0. Now, i(u) = 0 (A.7) if and only if au(u,t) = 0. At an extremum where (A.7) holds, we have . d {-au\ 9 / - Q » \ , d (~ au\ dt ~ a uu du v at du at ' dt at du at So we must show that if a(u,t) = au(u,t) = 0 then a, u u > 0. We shall show that these conditions require —— = 1 which proves the theorem. a, From (A.4), (A.5) and (A.6) we have a = xuyt - xtyu a u = xuuVt + xuVut ~ xutVu ~ xtVuu-But using (A.5) a u = xuVut - xutVu- (A-8) Similarly auu = (xuVtt ~ xttyu) + (xtVut - xutVt)-If a = au = 0 then using (A.4) and (A.8) 132 xtVut - xutVt = xt(vut - xut—) = xt(vut - xut—) = -r(xuVut - xutyu) = 0 xt xu xu SO auu = xuVtt - xttVu-We also have « t = (xuVtt ~ xttVu) ~ (xtVut ~ xutVt) so at = xuVtt - xttVu and hence auu = at as claimed. Notice, incidentally, that a(u,t) satisfies the diffusion equation at the max-ima of the contours and that all such contours have a curvature of -1 at their maxima in (u,t) curvature scale space. • Proof of theorem 3.4.8: It will be shown that this theorem holds for an arbi-trary parametrization of T^. Therefore it must also be true of arc length parametrization or close approximations. Let (X(u,o~), Y(u,a)) be an arbitrary parametrization of Tff. Since the class of polynomial functions is closed under convolution with a Gaussian [Hum-mel et ai, 1987], it follows that X(u,cr) and Y(u,a) are also polynomial functions: X(u, a) = a0 + axu + a^v? 4- a3u3 + • • • Y(u,a) = b0 + bxu + b2v? + b3v? + Suppose that Vg. goes through the origin of the coordinate system at u=0. It fol-lows that a0=&n=0. Assume further that there is a singularity on Tg at u=0. We have: Xu(u, a) = ax 4- la^u + 3a3u2 4- 4a4u3 4- • • • Yu(u,a) = bx + 2b2u + Zb3v? + 464u3 4- • • • Since Xu(u,o~) and Yu(u,o~) are zero at a singular point, it also follows that a1=61=0. We will now perform a case analysis of the singular point at u = 0 to determine when it corresponds to a cusp point. Since we will examine a small neighborhood of point u = 0, we will approximate the curve using the lowest degree terms in X(u,o) and Y(u,o): Assume w.l.o.g. that n > m. From above we know that m > 1. 133 Using ru(u,cr) = (Xu(u,a), Yu(u,<r)) = {mu^\ nvT1). it follows that rJie,*) = (mem-1, ne""1) = em-\m, ne™) and ru(-e,a) = (m(-e)^\ n{-e)^). We can now analyze the singular point in each of the four possible cases: 1. m and n are both even numbers. m-1 and n-1 are both odd numbers. Therefore r u (-e ,<7) = (-me™-1, -ne""1) = - e ^ m , ne™). A comparison of ru(e,cr) and ru(-e,cr) shows that an infinitesimal change in the parameter u results in a large change in the direction of the tangent vector. Therefore the singular point is also a cusp point in this case. 2. m and n are both odd. m-1 and n-1 are both even. Hence r0(-e,<r) = (mem-\ ne"-1) = e ^ m , ne^"1). Comparing ru(e,cr) to ru(-e, cr) now shows that the tangent direction does not change with u in a small neighborhood of the singular point. Therefore this singu-lar point is not a cusp point. 3. m is odd and n is even. m-1 is even and n-1 is odd. Hence ru(-<:,<7) = (mem-\ -ne"-1) = em-\m, -ne™). An infinitesimal change in u also results in an infinitesimal change in the tangent direction. Again, this singular point is not a cusp point. 4. m is even and n is odd. m-1 is odd and n-1 is even. So ruH,a) = (-me™"1, ne"-1) = em-\-m, ne™). An infinitesimal change in u now results in a large change in the tangent direc-tion. Therefore this singular point is a cusp point. It follows from the case analysis above that only the singular points in 134 cases 1 and 4 are cusp points. W e w i l l now derive analytical expressions for the curve Ta_g so that it can be analyzed i n a small neighborhood of the cusp point . T o deblur function j[u) = uk, we convolve a rescaled version of that func-t ion w i t h the function —f=-e~:*>(l-x2), an approximation to the deblurring opera-V7T tor derived i n (Hummel et al, 1987) good for small amounts of deblurring , as follows: oo or (Dtf)(y) = e-*(l-x2)(y + 2xVT)kdx - O O where t is the scale factor and controls the amount of deblurring. Solving the integral above yields wjM> = £ i.3.5 • • • ( H ) ^ y ^ t - i ) ; - ( ^ i ) ( H ) / . , P=O (p even) The following are four functions of the form /(tt) = uk and their deblurred versions: a . / ( « ) = v? (Dtf)(u) = u2-2t b. /(«) = tt3 (Dtf)(u) = u3-6tu c. /(tt) = tt4 {Dtf)(u) = tt4 - 12*u2 - 36*2 d. /(tt) = tt5 (Dtf)(u) = tt5 - 20tu3 - lSOr^ tt . W e can now analyze the cusp points identified i n cases 1 and 4 above. In case 1, the curve Ta is approximated by (ttm, tt") where m and n are both even numbers. W e now deblur the curve to obtain: m-2 m (Dtx)(u) = um- C l i t t m - 2 - c2t2um-4- • • • -Cj2±t 2 tt2 - Cjlt 2 2 2 n-2 _n (Dty)(u) = tt" - c > " - 2 - c ' ^ u ^ 4 - • • • - c ' „ _ 2 * 2 tt2 - c'„t2 . 2 7 Note that a l l powers of u are even and the constants Cj and c'j are a l l positive as follows from an examination of (A.9). It follows that 135 ro-2 (Dtx)(u) = mum-1 - (m-2)c1tum-3 - • • • - 2c ^  t 2 u 2 (Dty)(u) = nu""1 - (71-2)0'! to'*-3 - • • • - 2c'„_2 * 2 « " 2 " contain only odd powers of u and (2?tf)(e) = -(/Jtf)(-e). Hence there is also a cusp point on the curve at u0 = 0. In fact, the cusp point must also exist on r itself. This is a contradiction of the assumption that T is in C 2 . It follows that can not have a cusp point of this kind at uQ. We shall now turn to the cusp points encountered in case 4. Recall that, in that case, the curve Ta is approximated, in a small neighborhood of the cusp point, by (um,un) where m is even and n is odd. Again we deblur the curve to obtain: ro-2 m (Dtx)(u) = um - c^u™-2 - c2f?vr^ - ••• - c ^ t 2 v ? - c m t 2 2 T n-1 (Dty)(u) = un- c\ivr2 - c'^u"-4 - • • • - cVi t 2 «• Again note that constants Cj and c'j are all positive. The deblurred curve intersects itself if there are two values of u, and x^ , such that x{u1) = x(u2) (A.10) !<«i) = (A.11) Since (Dtx)(u) contains even powers of u only, it follows from (A.10) that tij = -Vy. Since (Dty)(u) contains odd powers of u only, substituting = -v^ in (A.ll) and simplifying yields: n-1 V - C'I^I"" 2 - c'2<2tt1n-4 - • • • - c'^t 2 tij = 0. "T" Since r f f _^ is of interest to us, we let t = S. We now obtain n-1 V - c'^u^2 - c^V"4 - • • • - 2 = 0. (A.12) 2 tti = 0 is one of the roots of this equation. For very small values of w1? the LHS of (A.12) is negative since the first term will be smaller than each of the other terms (which are negative). As ux grows larger, the first term becomes larger than the 136 sum of all other terms and therefore the LHS of (A.12) becomes positive. It fol-lows that there exists a positive value of % at which (A.12) is satisfied. Therefore is self-intersecting in a small neighborhood of the cusp point of T^. • Proof of theorem 3.4.9: Assume by contradiction that T is a simple curve which intersects itself during arc length evolution. T must touch itself at point P before self-intersection. Let Ta be such a curve. There are two distinct neighbor-hoods of Ta which contain point P. Let these neighborhoods be 5j and S2. Note that Si and S2 have colinear tangents at P. Let L be the line of those tangents. The tangents exist since it follows from theorem 3.4.8 that P can not be a cusp point because Tff does not self-intersect for c < a0. Recall that the infinitesimal movement of each point of Si and S2 is deter-mined by the equation: Therefore during arc length evolution every point will move in the direction of the normal vector by an amount equal to the curvature at that point. Similarly, during reverse arc length evolution, every point will move in the opposite direc-tion of the normal vector by an amount equal to the curvature at that point. It follows that if Si and S2 are on opposite sides of L, after an infinitesimal amount of reverse arc length evolution, they will intersect. This is a contradiction of the assumption that T was simple before touching itself. Assume then that Si and S2 are on the same side of L. Note that Sx and S2 can not be overlapping since they would still be overlapping after an inifinitesimal amount of reverse arc length evolution which is also a contradiction of the assumption that T was sim-ple before touching itself. Let Sx be the segment inside S2, i.e., the tangent to S2 always has Si to the same side. It can be seen that Si has a larger curvature at P than S2. It follows that after an infinitesimal amount of reverse arc length evolu-tion, Si and ^ will intersect which is again a contradiction. It follows that T remains simple during arc length evolution. • Proof of theorem 3.4.10: It will be shown that this theorem holds for an arbi-trary parametrization of Ta. Therefore it must also be true of arc length parametrization or close approximations. Let (x(u), y(u)) be an arbitrary parametrization of Tg. with a cusp point at u0. Using a case analysis similar to the one in the proof of theorem 3.4.8 to characterize all possible kinds of singularities of at uQ, we can again conclude that only the singular points in cases 1 and 4 are cusp points. In case 1, the curve is approximated by (um,un) in a neighborhood of UQ where m and ~n are both even. This type of cusp point can not arise on Tff if T is in Cv We now 137 turn to the cusp points of case 4. Recall that in case 4, the curve Tff is approxi-mated, in a neighborhood of uQ, by (um,un) where m is even and n is odd. Observe that x(u) = mum~1 x(u) = m(m-l)um-2 y(u) = nun~1 y(u) = n(n-\)un~2 and m+n-3 _ vn_A\num+n-Z ( \ _ x(u)'y(u) - y(u)x(u) _ mn(n-l)um+" - m(m-l) K { U ) ~ (i(u)2 + y(u)2f2 ~ ( A W + n 2 ^ f Since 7i>m, K(U) is always positive on either side of the cusp point in a neighbor-hood of u0. Therefore no curvature zero-crossings exist in that neighborhood on We now derive analytical expressions for Tg+g so that it can be analyzed in a neighborhood of UQ. T O blur function j[u) = uk, we convolve a rescaled ver-1 sion of that function with the function —^-e , the deblurring operator, as fol-V7T lows: oo F(u) = / -^e-*j(u+2xVt)dx -oo oo F(u) = / e-*2(u+2xVt)kdx V 7T d - O O where t is the scale factor and controls the amount of blurring. Solving the integral above yields /(.) = Y 1-3.5 • • • (^(zy^-D-'-^+D -^P, (p even) or The following are four functions of the form f(u) = u and their blurred versions a. f(u) = v? F(u) = u2 + 2t b. X«) = u3 F{u) = v? + Qtu c. j{u) = u4 F[u) = u4 4 - 12tu2 + I2t> 138 d. J[u) = u5 F{u) = u5 + 20tu3 + 60t2u . An expression for r< T + 5 in a neighborhood of the cusp point can be obtained by by blurring each of its coordinate functions: m-2 m X(u) = um+ c^u™-2 + c 2r 2um- 4 + • • • + c 2 v? + c^t 2 2 ~2 Y(u) = un + c\ivT2 + c'^vJ^ + • • • +cVi< 2 u. ~2~ Note that all constants are positive, all powers of u in X(u) are even and all powers of u in Y(u) are odd. It follows that all powers of u in m-2 X(u) = mum~l + (m-2)c1tum-3 + • • • + 2c m_2 t u are odd, all powers of u in m-2 X(u) = m(m-l)um-2 + (m-2)(m-3)c1^m-4 + • • • + 2c 2 n-3 2 are even, all powers of u in n-l Y(u) = nvT1 + (n^c'jtu"-3 + • • • + c'^t 2 2 are even and all powers of u in Y(u) = n{n-l)vr2 + (n-2)(n-3)c'1^n"4 + • • • + c „_3 t ~2~ are odd. The curvature of Ta+0 in a neighborhood of UQ is given by = x ( u ) n u ) - n u ) x ( t t ) ^ ' (X(u)2 + Y(u)2f2 Since the denominator of K(U) never goes to zero in a neighborhood of ti0, the zero-crossings of K(U) are the same as those of K'(U) = X(u)Y(u) - Y(u)X(u). Observe that the term with the highest power of u in X(u) Y(u) is mn(n-l)um+n~3 and the term with the highest power of u in Y(u)X(u) is rn{m-l)num+n~3 and that in both X(u)Y{u) and Y(u)X(u), all powers of ti are even and all constants are positive. Furthermore, note that at ti=0, X(u)Y(u) is zero and Y(u)X(u) > 0. 139 Therefore at u=0, K < 0. As u grows larger in absolute value, the terms in X(u)Y(u) and Y(u)X(u) with highest powers of u become dominant (all other terms have positive powers of t=6 in them). Since the dominant terms have equal powers of u, the one with the larger coefficient becomes the larger term. Since n > m, the largest term in X(u)Y(u) becomes larger than the largest term in Y(u)X(u). Therefore as u grows in absolute value, K becomes positive. It follows that there are two curvature zero-crossings in the neighborhood of UQ on r +^^ . These zero-crossings are new since it was shown that no zero-crossings exist in the neighborhood of UQ on Tff. • 140 Appendix B: Proofs of Results on Space Curves This appendix contains the proofs of the theorems of chapter 4. The proofs of theorems 4.4.1 - 4.4.5 have been given for arc length evolution only since the proofs for regular evolution are similar and simpler. Theorems 4.4.6 and 4.4.7 have been shown to hold for regular, renormalized and resampled torsion scale space images. Furthermore, theorems 4.4.8, 4.4.9 and 4.4.10 have been shown to hold for both regular and arc length evolution. Proof of theorem 4.4.1: It will be shown that arc length evolution is invariant under a general affine transform. Let = (X( W,a), Y{ W,a),Z( W,o)) be an arc length evolved version of T = (x(w),y(w),z(w)). If is transformed according to an affine transform, then its new coordinates, Xx, Y± and Zi are given by Xx{ W,CT) = a l ( W,cr) + b Y( W,a) + cZ( W,cr) + d YX{W,a) = eX(W,cr) + fY(W,a) + gZ{W,a) + h Zj( W,a) = iX( W,cr) + j Y( W,a) + kZ{ W,o) + l Now suppose r is transformed according to an affine transform and then evolved. The coordinates X2, Y2 and Z2 of the new curve are X2(W,a) = (ax(W) + by(W) + cz(W) + d) ®g(W,a) Y2{ W,a) = (e x( W) + fy{ W) + gz( W) + h) ®g( W,a) Z2{ W,a) = (ix( W)+jy{W) + kz(W) + t)®g( W,a). Since the convolution operator is distributive [Kecs 1982], it follows that 141 and the theorem follows. X2(W,a) = X1(W,a) Y2{ W,a) = Yx{ W,o) Z2(W,a) = Zx{W,a) • Proof of theorem 4.4.2: Let T = (x(w),y(w),z(w)) be a closed curve and let IV = (X( W,a), Y( W,<T),Z( W,a)) be an arc length evolved version of T. On T: (*(0), 2/(0), z(0)) = (x(l), y(l),z(l)). On T,: (X(0,a), Y(0,o),Z(0,o)) = (X(l,a), Y(l,a),Z(l,<j)). It follows that Tff is closed. • Proof of theorem 4.4.3: Let T = (x(w),y(w),z(w)) be a connected planar curve and r^ . = (X( W,a), Y( W,a),Z( W,a)) be an arc length evolved version of that curve. Since V is connected, x(w), y(w) and z(w) are continuous functions and therefore X(W,a), Y(W,a) and Z(W,a) are also continuous. Let WQ be any value of parameter W and let xQ, y0 and zQ be the values of X( W,o~), Y( W,a) and Z\W,o) at WQ respectively. If W goes through an infinitesimal change, then X( W,(T), Y( W,a) and Z{ W,a) will also go through infinitesimal changes: X(W0,a) ^ x0 + 6 Z( W0,(j) ^z0 + e. As a result, point P(x0,yQ) on goes to point P'(x0 + 6,y0-{- £, zQ + e). Let the dis-tance between P and P' be D. Then D = VS2 + i2 + e2 < SV2 assuming \6\ is the largest of \6\, |£| and |e|. It follows that an infinitesimal change in parameter W also results in an infinitesimal change in the value of the vector-valued function Tff. Therefore T^ is a connected curve. • Proof of theorem 4.4.4: Let M be the center of mass of T = (x(w),y(w),z(w)) with coordinates {^MIHMIZM)- Then 142 fx(w)dw : xM= = fx(w)dw. fdw 0 Let IV = (X(W,CT),Y(W,CT),Z(W,O-)) be an arc length evolved version of T with N = (XN,YN,ZN) as its center of mass. Observe that 1 1 oo oo j XN = fx(W,cr)dW= f f g(v,cr)x(W-v)dvdW = / g(v,a)(Jx{ W-v)dW)dv. 0 0 -oo -oo 0 W covers YA exactly once. Therefore l fx(W-v)dW = xK o So XN — XM. Similarly YN = VM and %N = ZM-It follows that M and N are the same point. • Proof of theorem 4.4.5: Since G is simple and convex, every plane P tangent to G contains that curve in the left (or right) half-space it creates. Since V is inside G, T is also contained in the same half-space. Now rotate P and V so that P becomes parallel to the Y2T-plane. P is now described by the equation x = c. Since P does not intersect T, it follows that x(w0)>c for every point wQ on T. Let rff be an arc length evolved version of T. Every point of Ta is a weighted average of all the points of T. Therefore X(W0,a)>c for every point W0 on and is also contained in the same half-space. This result holds for every plane tangent to G therefore Ta is contained inside the intersection of all the left (or right) half-spaces created by the tangent planes of G. It follows that Ta is also inside G. • Proof of theorem 4.4.6: The proof will first be given for the regular torsion scale space of T, then the modifications needed to apply the same proof to the resampled and renormalized torsion scale space images of T will be explained. Section i shows that the derivatives at a point on a torsion zero-crossing contour provide homogeneous equations in the moments of the coordinate 143 functions of the curve. Section ii shows that the moments are related to the coefficients of expansion of the coordinate functions of the curve in functions related to the Hermite polynomials. Section iii shows that the moments at one torsion zero-crossing point can be related to the moments at other torsion zero-crossing points. Section iv shows that the cubic equations obtained in section i can be converted into a homogeneous linear system of equations which can be solved uniquely for function T(U)K2(U). i. Constraints from the torsion zero-crossing contours Let r = (x(u), y{u), z(u)) be the arc-length parametrization of the curve with Fourier transform f = (x(uj),y(u),z(uj)). The Fourier transform of the Gaus-sian filter G(u, t) = —Le^/4' is G{u) = e-A Let = (x(u, io),y(u, t0),z(u, tQ)) be a curve obtained by convolving x(u), y(u) and z(u) with G(u,t0). Assume that is in C^. Such a <Q exists since T is in C\. Assume that K(U, t) J= 0 on the torsion zero-crossing contours in a neigh-borhood of tQ. It follows that the torsion zero-crossings are given by solutions of j3(u, t) = 0 where [Goetz 1970] /5(ti, t) = x(y "z - y z) - y(x "z - x z) + z(x y - x y) (B.l) where . represents derivative with respect to u. Note that on Y (2 = 0), fi(u,t) is given by /?0, t) = T(U, t) K2(U, t). (B.2) Using the convolution theorem, x(u, t), y(u,t) and t) can be expressed as following: x( u, t) y(u, t) z(u,t) and therefore x(u, t) y(u,t) = Je^*e^iu) y(u>)dw 144 z(u, t) = . X (ti, t) = j e^2te^"(-icj3)x(u;)ftu; y(u,t) = ^ z\u,t) = j f e^e^i-iuj3)^) dw. Note that the moment of order k of the function f(w) = e""2*e™"(vJ) x(w) is defined by: oo MK = J(u)le^e™(ia))i(u) dw - O O the moment of order k of the function f'(w) = e*^* e>wu{iw) y(w) is defined by: O O M'K= J\iw)ke^teiuu{iw)y{w)dw -oo and the moment of order k of the function f"(w) — €~^1 eMU(iw) z(w) is defined by: oo MK = J (iwfe^te^tiw) z(w) dw. -oo Therefore equation (B.2) can be written as: /3(u, t) = M0M{M2- MQM'{M'2 - MQMXM2 + MQM2M'{ + MQM^ - MQM2M{. The Implicit Function Theorem guarantees that the contours u(t) are in a neighborhood of <Q. Let £ be a parameter of the torsion zero-crossing contour. Then _d du d dt d d£~ di du di dt' dk On the torsion zero-crossing contour, /? = 0 and —-ft = 0 for all integers k. di Furthermore, since the torsion zero-crossing contour is known, all the derivatives of u and t with respect to i are known as well. We now compute the derivatives of /? with respect to i at (tig, t0). The first derivative is given by: 145 where ffi(tto»*o) du and d/?Po, <o) dt d Ql u. du ^(«o,<o) , <fr dffto.fr) = M 3 ' M 0 M ; - M 3 M 0 M ; ' - M;MQMX + M3M'QMX + M3MQMX - M 3 M 0 ' M ; = M 3 M 0 M 2 + ilf4'M0Mi - M3MQM2 - M±MQMX- M3MQM2 - MlM'QMx + MAMQM'{ + M3M'QM2 + M3MQM2 + M^MQMX - M^MQM[ - M3MQM2 and the second derivative is given by: a2/? = _ ^ _ a £ . £ < _a/? / 2 _ s 2 £ , 2jujttj?(3_ (dt\2a2/? , . ^ 2 du + <%2 dt ^d£' du2 d i di dudt ^diJ ef { ' ) where = M4'ilf0Mi + M2M3M0 - M[MQM'i - M2M3M0 - M'^MQMX - M2M3MQ du2 + MAMQMX + M2M3M'Q + M^MQMX + M2M'ZMQ - M4MQM{ - M2M3MQ a2/? = M;MQM[ + M2M3M'X - M^MQM'i - M2M3MX- M'^M'QMX - M2M'3% dudt + M5MQMx + M2M3MX + M^MQMx + M2M'3MX - M5MQM'X - M2M3M{ and ^ = MsMQM2 + 2M';M3M0 + M'sMQM'x + M2M\M[ - M'^MQM2 - 2M'iM3M0 - MiM0Mx - M2M[M'{ - MSMQM2 - 2M'^M3MQ - M£MQMX - M2M^MX + M6MQMx + M'2M^M'i + 2M3'M4Afo + M£MQM2 + M^MQM2 + 2Jtf 4 M 3 M 0 ' + M^MQMx + M2M±MX - M&MQM[ - M'2M^M[ - 2M3MAMQ- M^MQM2. Since the parametric derivatives along the torsion zero-crossing contours are zero, equation (B.3) is equal to zero. Note that equation (B.3) is in the first five 146 moments of functions f(u), f'(w) and equation (B.4) is in the first seven moments of those functions. In general, the fc+lst equation, —r/?(w) = 0 is a del cubic equation in the first 2k+3 moments of each of the functions f(u>), /'(<*>) and /V). It follows that the first n+1 equations at (UQ, 2Q) are in a total of 3(2n+3) = 6n+9 moments. Our axes are again chosen such that UQ = 0. The next section shows that the moments of f(u>), f'(u>) and f"{oj) are the coefficients ak, bk and ck in the expression of functions x(u), y(u) and z(u) in functions <f>k(u,a) related to Hermite polynomials. Therefore we have n+1 equations in the first 6ra+9 coefficients afc, bk and ck. To determine the ak, bk and cfc, we need 5n+8 additional and independent equations which can be provided by considering six neighboring torsion zero-crossing contours at (u^to), («2,tf0), (u^,t0), (tt4, ig), («5,<b) and («6,<b)-ii. The moments and the coefficients of expansion of x(u), y(u) and z(u) This section shows that the moments and the moment-triples in equations dk —T^(w' 0 a r e rented respectively to the coefficients of the expression of the func-tions x(u), y(u) and z(u) and function f3(u) in functions related to the Hermite polynomials. Expand function x(u) = -^-x(u) du in terms of the functions (f>k(u,cr) related to the Hermite polynomials Hk(u) by d>k(u,a) = (-1)* ^ g ^ - » ) (V2)* + 1 V7r <rv2 Hk(u) = ( - l ) k e ^ e - « 2 The coefficients ajt(cr) of the expansion are given by ak(a) = <wfc(u,cr),i(u)> where <,> denotes inner product in L2 and {^ (t^ cr)} is the set of functions biorthogonal to {4>k(u,cr)}. The {<j>k(u,a)} are given explicitly by 147 and the wk(u, a) by Since the ak are given by 2k-\ -^r jk —Z-kK } k\V^ du k k -— W k M = (-l)k^je~^ du" x(u) = ^J" Je^\iw)x{w) du k * aM = - J L (-l) f c J< T I e _ ^ , e - « > (*,)*(«) <k v27r ^ du The inner product is just the inverse Fourier transform of wk(u,cr). Therefore ak{cr) — J(iuj) ke  2 (iu>) x{w) dw which is equal to Mk modulo a factor e^ ", since t = a 1 ji. K Similarly, the functions 2/0) - -7-2/O) du can be expanded in terms of the functions <f>k(u,o) by 2/0) =S h(°)h(.u,°) z(u) =J]ck(a)(j)k(u,a) and it again follows that bk(a) = f(iu) ke  2 (iw)y(u)dw cfc(cr) = / (iw) k e  2 (jw) z(u) dw which are equal to M'k and M'k respectively modulo a factor ewu. Furthermore, a,k(<j), b'k(a) and c'k(o~), the coefficients of expansion of func-tions x'O), y(u) and z(u) in <f)k(u,a) respectively, can be seen to be related to ak(o~), bk(cr) and ck(a) according to the following relationships: 148 = hW) (B.5) and <4'(cr), b'{.{a) and ck(a), the coefficients of expansion of functions x(u), y(u) and "z\u) in <^(ii,<7) respectively, can be seen to be related to ak(cr), bk(a) and ck(a) by the following relationships: 4 -2(°") = aJfcO) &w(«0 = (B.6) Now observe that the function T(U) K2(U) can be expressed as: T(U)K2(U) = x(u)('y(u)'z (u) - 'y'(u)z(u)) - y{u)('x(u)"z(u) - x(v)'z\u)) + z{u){x{u)y\u) - x(u)y\u)) = x(u)'y\u)'z(u) - x(u)y(u)'z(u) - y\u)'x\u)'z\u) + y\u)'x (u)'z'(u) + z{u)'x\u)'y (u) - z(u)'x (u)'y\u) +s & i ( ° R )^ . (^ C R )S ^ ' H ^ - O ^ S cfayhi***) + E c.( ( T) <r i.(^ < 7)S °i<ff)^.<«»<7)S 6.VM«>*) = S S S tfaWfaWMM^W^^Mw) - S S S a«(<T)6i'(<7)4(°')^.(^ ^ c r ) ^ ( c ) " S E E i . { < r )« i ( f f ) < : iW^ t t . f f ) ^ {«»^ )^« .^ 149 + S E E bi{°)aKa)4(a)$i(u>aWu,v)fa(u,<7) + S E E ciW)ala)K{^)<t>i{^^)<t>l^(r)(t)k{u,a) - E S S ci(<T)ai'(°')6Jfe(^)^i(^^)^{^ c r)^jfc(^ 0') = S E E (a&Ho-Kio) + &.(*K0)4(*) + c,<a)aj((r)6^) -at(*)bjXo)c'k(a) - bt{a)a£cr)c&a) - cla)a'-(a)bk{a)) 4>lu, a)(f>}(u, <r)<t>k(u, a). Using (B.5) and (B.6) we obtain T{U)K\V) = S S E ( f f i . ( f f ) W a ) c w ( f f ) + hi°)aj+2(°)ck+l(°) + ci(<r)aH-l(<7)h+2(<7) - «i()6 i + 2 ( c r ) c j t + j ( c r ) - 6 , ( a ) a i + 1 ( c r ) c J t + 2 ( ( T ) - c^a^^b^a)) <£,P,o-)<^ 0, o-)4>k(u,a). It follows that if the triples a,{a)bj{a)ck(a) in the equation above are all known, the function /3(u) = T{U)K2(U) can be reconstructed. iii. Combining information from more than one contours To solve the system of equations obtained in section i, we need to obtain additional equations from other points of the torsion scale space image and relate them to the equations obtained from the first point. Suppose additional equations are obtained in the moments of functions t~^itVj)n (iu})x(u), 'e,wu (iw)y{u) and e~~^te'uu (iuj)z(u) at point (u\ ^). We have x(u+u') = Je™ue"u'(ko)x(u)dw = J] dk<f>k(u) and z(u+u') = Je^e^\kj)~z(u;)dw = fk<f>k(u) Now observe that E dkMu) = E ak(l>k(u+u') E e ^fc ( u )=S 6 fc^0+ u ' ) and 150 That is, u+u) can be expressed as a linear combination of <j>3{u) with j< k as has been shown in [Yuille and Poggio 1983]. iv. Reconstructing the function T(U)K2(U) It was shown in section i that seven points from seven torsion scale space contours give us 6n+9 cubic equations in the first 2n+3 moments of each of the functions f(u), f'(oj) and f"{io). Section iii showed that the moments of order k of any function at u+u can be expressed as a linear combination of the moments of order less than or equal to k of that function at u. Therefore we obtain a system of homogeneous cubic equations in the first 6n+9 coefficients of functions x(u), y(u) and z(u) using seven points from the torsion scale space image of T (Note that only three equations from the seventh point need be used). That system has at least one solution since the moments of order higher than 2n+2 of f(u>), f'(u) and f"{ijS) are assumed to be zero. However, the solution obtained from a cubic system of equations is in general not unique. Equations (B.3) and (B.4) can be converted into homogeneous linear equa-tions by assuming that each moment-triple appearing in those equations is a new variable. Tables B.1-B.7 show the moment-triples in equations (B.3) and (B.4). The + signs designate the moment-triples in equation (B.3) and the + and the x signs together designate the moment-triples in equation (B.4). Each table shows those moment-triples which share the same M'K, 0 < k<6. M0 M'2 M5 Mi M'Q M[ M2 M'3 M4 M5 M'e M0 M0 + + x X MX + + X X MX M2 + X M2 X X M 3 + + X M 3 + X MA + X M 4 + X M5 X X M 5 X M6 X M6 X Table B.l. Moment-triples with M0' Table B.2. Moment-triples with M'{ 151 M0 M'2 M'3 M'A M5 M'e Mo M'x M'2 M'3 Mi M 5 M'e M0 + X M0 + + x Mx X X Mx + X M2 M2 + X M3 + X Mz M4 X M4 X M5 X M5 M6 M6 Table B.3. Moment-triples with M2 Table B.4. Moment-triples with M3 Mo M'x M2 M3 M 4 M 5 Mg M'o M'x M2 M3 Af 4 M$ M^ M0 + x Mo X X Mx + X Mx X M2 X M2 X M3 X M3 M 4 M 4 M 5 M5 Me M6 Table B.5. Moment-triples with M'l Table B.6. Moment-triples with M 5 ' M'o M[ M2 M3 M[ M'b M'e Mo X Mx X M2 M3 MA M5 Me Table B.7. Moment-triples with M'e Note that all other moment-triples in tables B.1-B.7 can be computed from the existing ones using the following relationships: = MjM'^MlM^M-M'i MjM'^MlM^M'i * j k M^M'^M'i M^M'^M'i 152 Mi-lMj+lMk Mi+lM'j+lM'k M&'^MU " MiM'^M'U MtM'jM'U.M^M'jMl _ Mi.1M'jMlMiM'jM,k\l . Afl+1MjiW;'+1 J l f ^ M - M ^ Again we proceed to compute the first n derivatives at point (uQ,tQ) on one of the torsion zero-crossing contours. We now obtain n+1 homogeneous linear equations in some of the moment-triples M,MjMjJ.' by assuming that each moment-triple is a new variable. Since this system is in terms of the first 2n+3 moments of functions f(w), and f"(ijS), it will contain 0(nz) moment-triples. Therefore additional equa-tions are required to constrain the system. To obtain those equations, we proceed as follows: Assume that moments of order higher than 2n+2 are zero. Compute derivatives of order higher than n at {v^,to) but set moments of order higher than 2n + 2 to zero in the resulting equations. If a sufficient number of derivatives are computed at (uQ,tQ), the number of equations obtained will be equal to the number of moment-triples and our linear system will be constrained. It follows from an assumption of generality that the system will have a unique zero eigenvector and therefore a unique solution modulo scaling. Once the moment-triples in the system are known, all other moment-triples can be com-puted from the known ones using the relationships given above. Since all the momentTtriples MiMjMk together determine function of (3(u), it follows that func-tion (3(u) can be determined modulo constant scaling. Yuille and Poggio [1983] have shown that a 1-D signal can be recon-structed using two points from its scale space image. Note that our result implies that only one point is sufficient for the reconstruction of that signal. The theorem has now been proven for the regular torsion scale space image. To prove the same result about the resampled torsion scale space image, recall that derivatives at one point (at any scale) on any torsion zero-crossing 153 contour in the torsion scale space of T were computed and it was shown that the resulting equations can be solved for the coefficients of expansion of the function 0(u) in functions related to the Hermite polynomials. As before, we choose a point on a zero-crossing contour at any scale of the resampled curvature scale space image of T and compute the necessary deriva-tives. The value of a in the resulting equations is then set to zero. Consequently, the arc length evolved curve Ta, where a corresponds to the. scale at which the derivatives were computed, is reconstructed modulus uniform scaling, rotation and translation. The next step is to recover the original curve Y modulo function fi(y). This is done by applying reverse arc length evolution to T^. Let the arc length evolved curve be defined by: I\, = {{X{ W,er), Y( W,a), Z{ W,a)\ W € [0,1]} A reverse arc length evolved curve T is defined by: T = {(x(w),y(w),z(w))\w€ [0,1]} where x(w) = X(w,a) ©D^w^) y(w) = Y(w,a) ©D^a) and z(w) = Z(w,a) ©D^w^a) where is a deblurring operator defined in [Hummel et al. 1987] and t w w(W,t) = JJ K2(w,t)dwdt. oo where t = cr2/2. As a result, T is recovered modulo function j3(u). To prove the same result about the renormalized torsion scale space image, evolved curve is again reconstructed, then each of its coordinate func-tions is deblurred by convolving it with the deblurring operator D^. Once again, r is recovered modulo function (3(u). • Proof of theorem 4.4.7: Since by assumption all evolved and arc length evolved curves Tg. are in C 3, the conditions of the implicit function theorem are satisfied on contours T(U,CT), T(W,O) and r( W,o) = 0 in the regular, renormalized and resampled torsion scale space images of T. Since the proofs are identical, the theorem will be proven here for the regular torsion scale space image. The torsion of each evolved curve Va = (x(u,o-),y(u,o-),z(u,cr)) is given by: 154 , \ zxy - zy'x + y zx - yx'z 4- xyz - x zy T M = . . n 2 — . . , 2 — . . . . . . J (yz-zy) +{zx-xz) +(xy-yx) where . represents derivative with respect to u. On any contour in the torsion scale space image of V: T(U,O-) = 0. It follows from the assumption that all Ta are in C 3 that: fl(u,t) = "zxy - zy'x + yzx - yx'z + xyz - x zy where again . represents derivative with respect to u and t = cr 2 /2 . The functions x(u,t), y(u,t) and z(u,t) satisfy the heat equation: ZU U (M) = zt(uJ)-Since evolved curves are all in C 3, the conditions of the implicit function theorem are satisfied on contours )3(u,t) •— 0: t = i p ) i(u) - JL - I?i du fit The theorem will be proven if it is shown that if t(u) = 0 at any point on a tor-sion zero-crossing contour, then t(u) < 0 at that point. Observe that t(u) = 0 if and only if Pu(u,i) = 0. It follows that at a point where t(u) = 0: Pu\ d ( -Pu\ . d( ~Pu\ dt -Puu <„> = ±(^L)= ±(^L) +±(^L)JL = duK [3t ' dux j3t ' dV- f3t ' du f3t Therefore it must be shown that if /3(u,t) = flu(u,t) = 0 then f3uu/f3t > 0. We will now derive explicit expressions for j3uu and /3t. Differentiating the expression for /3(u,t) with respect to u and simplifying yields: Pu(u,t) = zttxuyt - zttyuxt + yttzuxt - ytixuzt + xttyuzt- xttzuyt. Differentiating the expression for /3U with respect to u and simplifying yields: where 155 * 1 = ZttuXuVt - + Vttuzuxt ~ Vttuxuzt + xttuVuzt - xttuzuVt and * 2 = Vtu*tPu - xtuzttVu + xtuVttzu ~ ztUytt?u + ztuxttVu ~ Vt*Fu*u-Differentiating the expression for /3(u,t) with respect to t and simplifying yields: fit = * 1 - * 2 -Let P be a point on an evolved curve where ft(u,t) = (3u(u,t) = 0. The coordinate functions of can be locally approximated at P using polynomial functions. Furthermore, assume that u=0 at point P. It follows that (um,u",up) is a local approximation to around P where m, n and p are the lowest non-zero powers of the polynomials approximating functions x(u,t), y(u,t) and z(u,t) respectively. Also assume without loss of generality that p>n>m. Observe that xu = mti™"1 xt = m(m-l) M " 1 - 2 z t u = m(m-l)(m-2) u™-3 xtt = m(m-l)(m-2)(m-3)um-4 x t t M = m(m-l)(m-2)(m-3)(m-4)tim-5 and that and that yu = nuT>~1 yt = n(n-l) ii" -2 ytu=n{n-l){n-2)vrz y t t= n(n-l)(n - 2)(n - 3 ) ^ y t t u = n(n-l)(n-2)(n-3)(r i-4)t i r- 5 * 0 = pu^ 1 zt = vT2 ztu = p(p-l)(p-2)u^ ztt = P(p-l)(p-2)(p-3)u^ 156 htu = ?(?-l)(p-2)(p-3)(p-4) It now follows that at point P: Poo " l t t + " 2 " —1 + —2 ~ ~ H 1 ^ r n + n + ^ 8 -E2um+n+P-& ~ Sx - S 2 where Hi = (p-l)(p-2)(p-3)(P-4)(n-l) - (p-l)(p-2)(p-3)(P-4)(m-l) + (n-l)(n-2)(n-3)(n-4)(m-l) - (n-l)(n-2)(n-3)(n-4)(p-l) + (m-l)(m-2)(m-3)(m-4)(>-l) - (m-l)(m-2)(m-3)(m-4)(n-l) and S 2 = (p-l)(p-2)(p-3)(rl-l)(n-2) - (p-l)(p-2)(p-3)(m-l)(m-2) + (n-l)(n-2)(n-3)(m-l)(m-2) - (n-l)(n-2)(n-3)(p-l)(p-2) + (m-l)(m-2)(m-3)(p-l)(p-2) - (m-l)(m-2)(m-3)(n-l)(n-2). It can be shown that: = (p-n)(p-m)(n-m)(p2 + (n+m-10)p + n2 + m2 + mn - lOn - 10m + 35) and that: E 2 = (p-n)(p-m)(n-m)(p(n+m) - 3(n+m) - dp + mn + 7). It can now be concluded that to prove the theorem, it must be shown that: |3il>|S 2 | or > | A 2 | where Ai = p2+ra2+m2+7ip+mp+mn-10p-10n-10m+35 and A 2 = np+mp+mn-3p-Zn-^3m+7. We shall now use a case analysis to prove that the inequality above holds for all valid triples of values of m, n and p. The analysis below shows that only triples of values which satisfy the inequality: p > m+n are valid: 157 Recall that (um,u",up) was used to approximate the curve around point P. It fol-lows that in a neighborhood of P, torsion is given by: , v = A t t P + n + m - 6  where A, A l 5 A2 and A3 are constants. The expression above is ambiguous at u=0. To resolve the ambiguity, l'Hopital's rule can be applied repeatedly. Since both the numerator and the denominator are polynomials, to have T(U) = 0 at u=0, repeated application of l'Hopital's rule should result in: lim r(u) = , ^Ur, s u^o £ + f(u) where ip and £ are constants, i>0 and f(u) = Q at u = 0. This can only happen when one of the following three conditions are met: a. p+n+m-6 > 2(p+n-3) b. p+n+m-6 > 2(p+m-3) c. p+n+m-6 > 2(m+n-3). Conditions a and b are not possible since they violate the assumption that p> n> m. However, condition c is possible. It follows from this condition that: p > m + n. We can now proceed with the case analysis. All triples of values for m, n and p in which m is even correspond to cusp points which are excluded by the assumption that all evolved curves Tg. are in C 3. Therefore we will consider only odd values of m. Case 1. Suppose m>7. Recall that p>n>m. It is easily seen that both Aj and A 2 are positive. So the absolute value signs can be dropped and the ine-quality: A ! > A 2 can be simplified. As a result, we must now show that the following ine-quality holds: p2+n2+m2 > 7p+7n+7m-28. Note that m2>7m, n2>7n and p2>7p. It follows that the inequality does hold. Case 2. Suppose m = 5. Again, it can be seen that both Aj and A 2 are positive. We must again show that: 158 p2+n2+m2 > 7p+7n+7m-28. Substitute m=5 in the above inequality. We now have: p2+n2 > 7p+7n-18. Since n>6, n2>7ra-18 and since p>ll, p2>7p. Hence the inequality again holds. Case 3 . Suppose m = 3. Substitute this value for m in Aj. As a result, A x simplifies to: p2+n2+np-7p-7n+14. Note that 7i>4 and p>8. So p2>7p. Hence to show that A x is positive, it is sufficient to show that: n2+np-7n+14: > 0. Since p>8, np>8n. Therefore: n2+np-7n+14 > n2+8n-7n+l4 = n24-n+14 > 0. Now substitute m=3 in A 2 . As a result A 2 simphfies to: 7ip+3p+3n-3p-3n-9+7=np-2 which is always positive. Therefore we must again show that: p2+n2+m2 > 7p+7n+7m-28. Substituting m=3 in the above inequality yields: p2+n2 > 7p+7n-l6. Since p>8, p2>7p and it is sufficient to show that: n2 > 7n-16. It is easily seen that this inequality is satisfied for n>4. Case 4. Suppose m=l. Substituting this value in A x simphfies it to: p2+n2+np-9p-9n+26. Since p>4, p2-9p>-20. Hence to show that Aj is non-negative, it is sufficient to show that: n2+np-9n+6 > 0 Again since p>4: n2+np-9n+6 >n2+4n-9n+Q = ri2-57i+6 which is non-negative for n>2. Now substitute for m=l in A 2 to obtain: 159 pn-2p-2n+4 = p(n-2)-2n+4. Since p>4 p(n-2)-2n-f-4 > 4(n-2)-2n+4 = 4n-8-2n+4 = 2n-4 which is non-negative since n>2. So A 2 is also non-negative. Therefore we must again show that: p2+n2+m2 > 7p+7n+7m-28 Substitute for m= 1 in the above expression to obtain: p2+n2 > 7p+7n-22 which is equivalent to: (p2~7p) + (n2-7n)+22 > 0. If n=2, then n2-7n = -10 and p>4. It follows from p>4 that p2-7p > -12. As a result, the inequality above is satisfied. If n>2, then n2-7n > -12 and p>5. It follows from p>5 that p2-7p > -10. There-fore, the inequality above is again satisfied. This completes the case analysis. We have shown that the inequality: |Ai l > | A 2 | and therefore the inequality: ISil > | 3 2 | is satisfied for all valid triples of values of m, n and p. Therefore f3uu//3t is always positive. Hence all extrema of contours in all torsion scale space images of T are maxima. • Proof of theorem 4.4.8: It will be shown that this theorem holds for an arbi-trary parametrization of Ta. Therefore it must also be true of arc length parametrization or close approximations. Let (Jf(u,cr), Y(u, a), Z(u, a)) be an arbitrary parametrization of T with a cusp point at UQ. It has been shown by [Hummel et al. 1987] that the class of polynomial functions is closed under convolution with a Gaussian. Therefore X(u,a), Y(u,o~) and Z(u,a) are also polynomial functions: X(u, a) = aQ + axu + a^u2 + a3u3 + • • • Y(u,a) = b0 + bxu 4- b2u2 + b3v? 4- • • • Z(u,a) = c 0 4- cxu 4- c2u2 + c3v? -f • • • Let T,,. go through the origin of the coordinate system at u0=0. It follows that 160 a0=&0=c0=0. Every cusp point is also a singular point of the curve. Therefore has a singularity at UQ. NOW observe that Xu(u,o) = ax + 202^ + 3a3u2 + 4a4u3 4- • • • Yu(u,a) = bx + 2b2u + 3bzu2 + 464u3 4- • • • Zu(u,o) — cx 4- 2c2ii + 3c3u2 4- 4c4u3 4- • • • Xu(u,a), Yu(u,a) and Zu(u,o~) are zero at a singular point. It follows that ^=62=02=0. As a result, all powers of u in X(u,a), Y(u,cr) and Z(u,a) are larger than one. The following case analysis identifies the cases in which the singular point at u0 is also a cusp point. Since is examined in a small neighborhood of point uQ=0, it can be approximated using the lowest degree terms in X(u,a), Y(u,a) and Z(u,a): Ta = {um,un,v?) Assume without loss of generality that p>n>m. Observe that ru(u,<r) = (Xu(u,o-), Yu(U,<T),Zu(U,(T)) = {mu^^nu^^pvT1) Therefore ru(e,a) = (me"1-1,!!^1,?^1) = em-1(m,nen-m,pep-m) and r„(-e,a) = (m(-e)^\ n ^ ^ K " ^ 1 ) Since m, n and p can be odd or even, the singular point at UQ must be analyzed in each of eight possible cases: 1. m, n and p are even. m-1, n-1 and p-l are odd. So ru(-e,<7) = (-men,-1)-ntn-1,-j)e^1) = -em-l(m,nen-m,pe^m) Comparing ru(e,cr) to ru(-e,cr) shows that an infinitesimal change in parameter u in a neighborhood of the singular point results in a large change in the direction of the tangent vector. Therefore this singularity is a cusp point. 2. m and n are even, p is odd. m-1 and n-1 are odd and p-l is even. Therefore ru(-e,cr) = (-me^ 1 ,-"^ 1 ,?^ 1) = e^\-m-ne^m,pe^m) A comparison of ru(e,cr) and ru(-e,<r) again shows that an infinitesimal change in 161 u causes a large change in the tangent direction. Hence this singular point is also a cusp point. 3. m is even, n is odd and p is even. m-1 is odd, n-1 is even and p-1 is odd. Hence ru(-e,a) = (-me^1, ne^-peT1) = ^{-m^ne^-pt™) An infinitesimal change in u again results in a large change in the tangent direc-tion. This singularity is a cusp point as well. 4. m is even, n and p are odd. m-1 is odd, n-1 and p-1 are even. So r„(-e,cr) = (-me^ne"- 1^^ 1) = e"^\-m, n e ^ p e ^ ™ ) A large change in the tangent direction is caused by an infinitesimal change in u. Therefore this singularity also corresponds to a cusp point. 5. m is odd, n and p are even. m-1 is even, n-1 and p-1 are odd. Therefore ru(-e,<r) = (mer"-1,-ne,,-1,-pep-1) = em-1(m,-nen-m,-pe^m) A comparison of ru(e,cr) and ru(-e,cr) now shows that an infinitesimal change in u in the neighborhood of the singular point also results in an infinitesimal change in the tangent direction. Hence, this singular point is not a cusp point. 6. m is odd, n is even, p is odd. m-1 is even, n-1 is odd and p-1 is even. So ro(-e>cr) = (me"1-1,-^^1,?^1) = eT^\m,-nen-m,pep-m) The tangent direction changes only infinitesimally in the neighborhood of the singular point. Therefore this singularity is not a cusp point either. 7. m and n are odd, p is even. m-1 and n-1 are even and p-1 is odd. Hence ru(-e,cr) = (me^ne^-pe^ 1 ) = e ^ m , ne"-m,-pe^m) This singularity is again not a cusp point since the tangent direction changes only infinitesimally in its neighborhood. 8. m, n and p are odd. 162 m-1, n-1 and p-l are even. Therefore ru(-e,<r) = (me^ne"- 1 ,^ 1 ) = e^\m, ne^pe**-™) The last singular point is not a cusp point either since the changes in the tangent direction are again infinitesimal. It follows from the case analysis above that only the singular points in cases 1-4 are cusp points. We next derive analytical expressions for the curve T ^ so that it can be analyzed in a small neighborhood of the cusp point. To deblur function f(u) = uk, a rescaled version of that function is con-volved with the function —y=.e~^ (l-u2). This function is an approximation to the V7T deblurring operator derived in [Hummel et al. 1987] and is good for small amounts of deblurring. The convolution can be expressed as oo (Dtf)(u)= \ -Z=e-x?{l-v2)f{u + 2vVt)dv J V 7T or (Dtf)(u) = J e^il-v^u + lvVlfdv -oo where t is the scale factor and controls the amount of deblurring. Solving the integral above yields W ) W = £ 1.3.5 • • • fr.Dpy"^);-^'),.^ p=0 (p even) Tff_s can now be analyzed in each of the cases 1-4: Case 1: r a is approximated by up) where m, n and p are even. To obtain analytical expressions for we deblur each of its coordinate functions: m-2 m (Dtx)(u) = um- Cltum-2 - • • • - Cjn±t 2 v? - c^t 2 2 2 n-2 _n (Dty)(u) = un - c[tvT2 - ••• -c'^2t2 u2 - c'nt2 163 P -2 _P (Dtz)(u) = vP- cltvT2 - •• • • - c"^2t 2 u2 - c"Lt2 Note that all powers of u are even and all constants are positive. It follows that ro-2 (Dtx)(u) = mum-1 - (m-2)c1tur"-z - • • • -2cm_2t 2 « 2 rt-2 (Dty)(u) = nu"-1 - (n-2)c{to"-3 - • • • - 2c '„_2 2 2 « ~ 2 ~ p-2 (2?ti)(u) = pu^"1 - (p-2)c>^-3 - • • • - 2c'^t 2 u ~T~ contain only odd powers of u and (Dtr)(e) = -(£> tf)(-e). Hence there is also a cusp point on at ILQ. Since that cusp point is of the same kind as the cusp point on T ,^ it follows that a cusp point must also exist on T. This is a contradic-tion of the assumption that T is in Cx. Therefore can not have a cusp point of this kind at t ^ . Case 2: Ta is approximated by (um, u", up) where m and n are even and p is odd. Ta_g is obtained by deblurring each of its coordinate functions: m-2 m (Dtx)(u) = um- cxtum-2 - • • • - c^f^u2 - c„t 2 2 2 n-2 _n (Dty)(u) = un- c'xtvr2 - ••• - c'^t 2 u2-c'„t2 2 2 P-1 (Dtz)(u) = uP~ c'i~iuP-2 - • • • - c " p _ ! * 2 t t Note that (Z?tx) and (Dty) contain even powers of u only, (Dtz) contains odd powers of u only and all constants are positive. The deblurred curve intersects itself if there are two values of u, ux and t^, such that x(ul) = XM !<«i) = K « 2 ) 164 Z(UX) = Z(U2) It follows from the first two constraints above that ux = -u^. Substituting for in the third constraint and simplifying yields: p-l uf - c \tuf~2 - • • • - c " M i 2 uj = 0 Now let t = 6 to obtain V - c\8uxr-2 - • • • - 2 ux = 0 (B.8) 2 The LHS of (B.8) is negative for very small values of ux since the first term will be smaller than all other terms, which are negative. As ux grows, the first term becomes larger than the sum of all other terms and the LHS of (B.8) becomes positive. Therefore there is a positive value of ux at which (B.8) is satisfied. Hence intersects itself in a neighborhood of UQ. Case 3: Tff is approximated by (um,un,un) where m is even, n is odd and p is even. As in the previous case, we obtain analytical expressions for Tff_^: m-2 m (Dtx)(u) = um- c^u™-2 - •• • - Cjs±t 2 u2 - c^i 2 2 2 n-1 (Dty)(u) = un- c[tvr2 - • • • - c'^t 2 u 2 P-2 P (Dtz)(u) = uP-c "xivr2 - • • • - C t 2 V? - C "p t2 ~ J In this case, (Dtx) and (Dtz) contain only even powers of u and (Dty) contains only odd powers of u. Again, Ta_g can be shown to intersect itself if there are two values of u, ux and such that x{ux) = x^) y(ux) = y^) z(ux) = z(u2) It now follows from the first and third constraints above that ux = -u^. Substitut-ing for U2 in the second constraint, letting t = 6 and simplifying yields 165 n-1 uxn - c[8uxn-2 - • • • - 2 ux = 0 (B.9) 2 An argument similar to the one used in the previous case shows that there exists a positive value of ux at which (B.9) is satisfied. Therefore Ta_s again intersects itself in a neighborhood of UQ. Case 4: Tff is approximated by (um, un, up) where m is even and n and p are odd. An analytical expression for in a neighborhood of UQ is given by m-2 m (Dtx)(u) = um- cxtum-2 - • • • - C j 2 _ 2 t 2 V? - c^i 2 2 2 n-1 (Dty)(u) = un- c'xtvr2 - •• • - c'^t 2 u 2 (Dtz)(u) = up- c "xtvr2 - • • • - c t 2 u All powers of u in (Dtx) are even and all powers of u in (Dty) and (Dtz) are odd. As before, Ta_s intersects itself if the three constraints x(ux) = x(u2) y(ux) = y(u2) z(ux) = z(u2) are satisfied simultaneously. It follows from the first constraint that ux = -v^. Now substitute for in the second and third constraints, let t = 8 and simplify: n - l uxn- c'x8uxn-2 - • • • - 2 = 0 (B.10) ~2~ P-1 UXP - c "x6UXP-2 - • • • - c "^6 2 ux = 0 (B.ll) ~2~ Each of the equations (B.10) and (B.ll) is satisfied at a positive value of ux but, in general, the same value of ux will not satisfy both. It follows that, in this case, Ta_s does not intersect itself. However, an argument similar to the ones in the previous two cases shows that the planar curves defined by (Dtx) and (Dty) and by (Dtx) and (Dtz), that is, the projections of Tff_s on the XY and XZ planes respectively, do intersect themselves in a neighborhood of uQ. 166 This completes the proof of theorem 4.4.8. • Proof of theorem 4.4.9: It will be shown that this theorem holds for an arbi-trary parametrization of Vg. Therefore it must also be true of arc length parametrization or close approximations. Let (x(u),y(u),z(u)) be an arbitrary parametrization of Tff with a cusp point at UQ. Using a case analysis similar to the one in the proof of theorem 4.4.8 to characterize all the possible singularities of Ta at u0, we again conclude that only the singular points in cases 1-4 are cusp points. We now derive analytical expressions for Ta+g so that it can be analyzed in a neighborhood of UQ. To blur function ftu) = uk, we convolve a rescaled ver-of that function with the function , the blurring operator, as follows: V7T sion F(u) = / -L=.e~,?j{u+2vVt)dv J V 7T or F(u) = -j=~f e-^u + lvVt)1 dv where t is the scale factor and controls the amount of blurring. Solving the integral above yields #w = £ 1.3.5 • •' • ( 2 i ' p / 2 ^ - 1 ) ; • • ( ^ + 1 > ( B . 1 2 ) p=0 p ' (p even) An expression for Tff+S in a neighborhood of the cusp point can be obtained by blurring each of its coordinate functions. Furthermore, expressions for Ta_g in a neighborhood of the cusp point can be obtained by deblurring each of its coordi-nate functions according to (B.7). Each of the cases 1-4 can now be analyzed in turn: • Case 1: r„. is approximated by (um, un, up) where m, n and p are even. An argument similar to the one used in case 1 of theorem 4.4.8 shows that this kind of cusp point can not arise during evolution of T. Case 2: Ta is approximated by un, up) where m and n are even and p is odd. Observe that 167 x(u) = mu™-1 x(u) = m(m-l)um-2 x(u) = m(m-l)(m-2)^i^7,-3 y{u) - riv."-1 y\u) = n(n-l)tt"-2 y(u) = n(n-l)(n-2)u"-3 z(u) = vv?-1 z(u) = p(p-l)uP-2 z(u) = p(p-l)(p-2)up-3 Torsion on T^ . is given by: , x "z'x'y - "z'yx + y z'x - y xz + xy'z - x zy n « ) = T T T : — . . 2 ....—r 2 . — T 7 - r or (yz-zy) + (zx-xz) + (xy - yx)' ««) = A + B+C • ( B , 1 3 ) where A = ((np(p-l) - pn(n-l))u^3)2 B = ((pm(m-l) - mp(p-l))uP+rn-3)2 C = ((mn(rc-l) - nm(m-l)) um+^3)2 and K = (p-\)(p-2)(n-m) + (n-l)(n-2)(m-p) + (m-\)(m-2)(p-n). At u = 0 (cusp point), r is undefined. When u is positive or negative, the sign of T(U) depends on the sign of K. Observe that K= (p~\)(p-2)(n-m) + (n-l)(n-2)(m-p) + (m-l)(m-2)(p-n) = (p2-3p+2)(n-m) + (n2-3n+2)(m-p) + (m2-3m+2)(p-n) = np2 - mp2 - 3pn + 3pm + 2n - 2m + mn2 - 3mn + 2m - pr? • + 3pn - 2p + pm2 - 3pm + 2p - nm2 + 3mn - 2n = (n-m)p2 + (m2-n2)p + mn2 - nm2 = (n-m)p2 + (m+n)(m-n)p + mn(n-m) = (n-m)(p2 - (m+n)p + mn) = (n-m) (p-m) (p-n) which is positive because of the assumption that p>n>m. Since p+n+m-6, the power of u in the numerator, is odd, it follows that T(U) is positive for positive u and negative for negative u. 168 We now investigate T(U) on Tff+6. It follows from (B.12) that T^g is given by: m-2 m X(u) = um + cxtum-2 + • • • + C j 2_2 < 2 v? + Cjlt 2 2 2 n-2 _n Y(tt) = U N + C^u"" 2 + • • • + C^_2 < 2 U 2 + c'^t2 ~7~ 2 P-l 2(u) = vP + c ItvT2 + • • • + c "^t 2 u 2 where all constants are positive, all powers of u in X(u) and Y(u) are even, all powers of u in Z(u) are odd and t equals 8, a small constant. Note also that the last terms in X(u) and Y(u) do not contain any positive powers of u but all terms in Z(u) contain positive powers of u. It follows that the last terms in X(u), Y(u), Z(y) and Z (u) do not contain positive powers of u whereas all terms in X(u), X(u), Y[u), Y(u) and Z{v) contain positive powers of u. Therefore, at u = 0, X(u) = X (u) — Y(u) = Y(u) — Z(u) = 0 and r = 0. As u grows, the terms in X(u), X(u), JT'(ti), Y(u), Y(u), r'(tt), Z(tt), Z\u) and Z(u) with the largest power of u (which are also the only terms without 8) become dominant and torsion is again given by (B.13). It follows that T(U) is positive for positive u and negative for negative u on Ta+g. Since r is zero at u = 0, Ta+6 has a torsion zero-crossing point at u = 0. We next investigate T(U) on T^. From (B.7) it follows that is given by: m-2 m (Dtx)(u) = um - d 1 < « m - 2 - • • • - d„_21 2 u2- d^t2 2 ~2 • n-2 n_ (Dty)(u) = un- d'^ivT2 - • • • - d'„_2t 2 u2- d'^t2 ~2~ 7 £± (Dtz)(u) = vP-d'^vT2 - • • • - d'^t 2 u 2 where all constants are positive, all powers of u in Dtx and Dty are even, all powers of u in Dtz are odd and t equals 8, a small constant. It again follows that r=0at t i=0 ,Tis positive for positive u and negative for negative u. Therefore there is also a torsion zero-crossing point at u = 0 on Tff_g. It follows that there is a torsion zero-crossing point at on Tff_g before the formation of the cusp point and on r<T+5 after the formation of the cusp point. 169 Case 3: Ta is approximated by (um,un,up) where m is even, n is odd and p is even. The proof is analogous to that of case 2, and the same result follows. Case 4: T^ . is approximated by (um, un, up) where m is even, and n and p are odd. At u = 0, the cusp point, r is undefined. At all other points, T(U) is given by (B.13). Since the coefficient of the numerator of (B.13) is positive (as shown in the proof of case 2) and p+n+m-6, the power of u in the numerator, is even, r(u) is positive for positive and negative values of u in the neighborhood of uQ on T^. Therefore there are no torsion zero-crossing points in the neighborhood of UQ on I V We now investigate T(U) on Tff+S. It follows from (B.12) that Tff+g is given by: m-2 TO X(u) = um+ c^u™-2 + • • • + Cj2±t 2 V? + c^i 2 2 2 n-1 Y(u) = un 4- c^u"-2 + • • • + c'^t 2 U ~2~ P-l Z{u) = up+ c '[tvT2 + • • • + c"p_lt2'u ~2~ where all constants are positive, all powers of u in X(u) are even, all powers of u in Y(u) and Z(u) are odd and t equals 8, a small constant. Furthermore, note that the last term in X(u) does not contain a positive power of u but all terms in Y(u) and Z(u) contain positive powers of u. Therefore the last terms in X(u), Y(u), Y(u), Z(u) and Z (u) do not contain positive powers of u whereas all terms in X(u), X(u), Y(u) and Z(u) contain positive powers of u. Hence at u=0, X(u) = jf (u) = Y(u) = Z(u) = 0 and , x = Y\u)Z(u)X(u) - Z\u)Y(u)X(u) = X(u)(Y\u)Z(u)-Z(u)Y(u)) (Z(u)X(u))2 + (Y(u)X(u))2 (Z(u)X(u))2 + (Y(u)X(u))2 Since the denominator is positive and X(u) is positive, to determine the sign of T(U), we must determine the sign of the expression: Y(u)Z(u) - Z(u)Y(u). At u=0, using (B.12) we conclude that the non-zero term of Y(u) is: 170 n-1 n-1 , , ^ . n-1 n-1 c'^t 2 = L3.5 • • • (n-2)W \ , n l = 1.3.5 • • • n2 2 i —r- (n-1)! 2 Similarly, at u = 0, the non-zero term of Z(u) is: P-1 p-1 P-1 c ' ^ i 2 = 1.3.5 • • • p 2 2 i 2 Using (B.12), it follows that at u = 0, the non-zero term of Y(u) is: n-3 n-3 , , 7 . n-3 n-3 6 C '„_ 3* 2 = 6(1.3.5 • • • (n-4))(2*] \ f = (1.3.5 • • • n)(n-l)2 2 t 2 — 6 (n-3)! Similarly, at u = 0, the non-zero term of Z (u) is: p-3 p-3 p-3 6 ^ 3 * 2 =(1.3.5- -p)(p-l)2 2 2 2 Therefore n-3 n-3 p-1 p-1 2 -*2 /"i q c . . . _\ o 2 J 2 Y(u)Z(u) - Z(u)Y(u) = (1.3.5 • • • n)(n-l)2 2 t 1 (1.3.5 • • • p)2 2 t n-1 n-1 p-3 p-3 - (1.3.5 • • • n)2 2 < 2 (1.3.5 • • • p){p-l)2 2 * 2 p+n-4 = (2t) 2 (1.3.5 • • • n)(1.3.5 • • • p)(n-p) and it follows that Y(u)Z(u) - Z (u) Y(u) < 0 since n< p. Therefore T(U) is nega-tive at u = 0 on As u grows the terms in X(u), X(u), X (u), Y(u), Y(u), Y(u), Z(u), Z(u) and Z(u) with the largest power of u (which are also the only terms without 6) become dominant and r(u) is again given by (B.13). Since p+n+m-6, the power of u in the numerator, in now even, T(U) becomes positive as u grows in absolute value. Therefore there exist two new torsion zero-crossings in a neighborhood of u0 on Tff+^. This completes the proof of theorem 4.4.9. • Proof of theorem 4.4.10: It will be shown that this theorem holds for an arbi-trary parametrization of T .^ Therefore it must also be true of arc length parametrization or close approximations. Let r = (x(u),y(u),z(u)) be a space curve and let x(u), y(u) and z(u) be polynomial functions of u. Let Ta = (X(u,a), Y(u,a), Z(u,a)) be an evolved version of T with a point of zero curvature at UQ. Assume without loss of generality that 171 UQ = 0 and that at ti0 T^ goes through the origin of the coordinate system. It fol-lows that Ta can be approximated in a neighborhood of UQ by: r , = ( t t " , t t » u P ) ( B . 1 4 ) where um, un and up are the lowest degree terms in X(u,a), Y(u,a) and Z(u,o~) respectively. Assume without loss of generality that p>n>m. Since TO, n and p can be odd or even, point UQ must be analyzed in each of eight possible cases. The analysis in the proof of theorem 4.4.8 showed that when TO is even, a cusp point exists on Ya at UQ. We will therefore look at the remain-ing four cases in which TO is odd: Case 1. TO is odd and n and p are even. Torsion on Ta is given by equation ( B . 1 3 ) . Since p+n+m-6 is odd, torsion is positive for positive u and negative for negative u in a neighborhood of UQ. We now investigate torsion on Ta+g where 5 is a small, positive number. Expressions for X(u,cr), Y(u,a) and Z(u,a) can be obtained using equation ( B . 1 2 ) . Note that all powers of u in X(u,o~) are odd and all powers of u in Y(u,cr) and Z(u,cr) are even. It follows that all powers of u in X(u), X(u), Y(u) and Z(u) are even and all powers of uin X(u), Y(u), Y(u), Z(u) and Z (u) are odd. Note also that those terms in which all powers of u are odd, are equal to zero at u0. Therefore torsion is zero at UQ on Tff+g. As u grows, um, un and up,. that is the terms in X(u,a), Y(u,o~) and Z(u,er) with the largest powers of u, become dominant and torsion is again given by equation ( B . 1 3 ) . It follows that torsion is positive for positive u and negative for negative u on Ta+g in a neighborhood of UQ. Hence no new torsion zero-crossings have been created. Case 2. TO is odd, n is even and p is odd. Torsion on Ta is again given by ( B . 1 3 ) . Since p+n+m-S is even, torsion is positive for positive and negative u on Tff. We now investigate torsion on Tff+0. Note that all powers of u in X(u,a) are odd, all powers of u in Y(u,o) are even and all powers of u in Z(u,(x) are odd. It follows that all powers of u in X(u), X(u), Y(u), Z(u) and Z (u) are even and all powers of ti in X(u), Y(u), Y(u) and Z(u) are odd. Note also that those terms in which all powers of ti are odd, are equal to zero at UQ. It follows that torsion on Tff+6 at tiQ is given by: . v _ ZXY- XZY _ YjZX-XZ) (ZY)2 + (XY)2 ~ (ZY)2 + (XY)2' Since the denominator of the expression above is positive and Y is positive, the sign of T(U) is the same as the sign of the expression: ZX - XZ. At UQ, using ( B . 1 2 ) it can be shown that: 172 p+m-A ZX-XZ= (2t) 2 (1.3.5 • • • p)(1.3.5 • • • m)(p-m) which is positive at UQ. A S U grows larger, torsion is again given by (B.13) in a neighborhood of uQ and is therefore positive in that neighborhood. Again no new torsion zero-crossings have been created. Case 3. m and n are odd and p is even. Torsion is again given by (B.13) on T^. Since p+n+m-6 is even, torsion is positive for positive and negative u on T^. We now investigate torsion on Tff+f. Note that all powers of u in X(u,o) and Y(u,o) are odd and all powers of u in Z(u,a) are even. Hence all powers of u \nX(u), X(u), Y(u), Y(u) and Z(u) are even and all powers of u in X(u), Y(u), Z(u) and Z (u) are odd. Note also that those terms in which all powers of u are odd, are equal to zero at UQ. Therefore torsion on Ta+S at uQ is given by: , x XYZ-YXZ Z(XY-YX) T\u) = r-rr- r-rr^ = i-rr- rrr^-. . ( YZf + (XZ) ( YZf + (XZ) Since the denominator of the expression above is positive and Z is positive, the sign of T(U) is the same as the sign of the expression: XY — Y X. At UQ, using (B.12) it can be shown that: n+m-4 XY- YX = (2t) 2 (1.3.5 • • • n)(1.3.5 • • • m)(m-n) which is negative since n>m. Therefore torsion is negative at UQ on r,,.^ .^ . As u grows larger, torsion is again given by (B.13) in a neighborhood of UQ and is therefore positive for positive and negative u. It follows that there are two new torsion zero-crossings in a neighborhood of UQ on r<T+^. Case 4. m, n and p are odd. Torsion on Ta is again given by equation (B.13). Since p+n+m-6 is odd, torsion is positive for positive u and negative for negative u on We now inves-tigate torsion on Ta+S. Note that all powers of u in X(u,o), Y(u,er) and Z(u,a) are odd. Hence all powers of u in X(u), Y(u), Z(u), X(u), Y(u) and Z(u) are even and all powers of u in X(u), Y(u) and Z(u) are odd. Note also that those terms in which all powers of u are odd, are equal to zero at UQ. It follows that torsion is unbounded at UQ on As u grows larger, torsion is again given by (B.13) in a neighborhood of UQ and is therefore positive for positive u and nega-tive for negative u. Hence there are no new torsion zero-crossings in a neighbor-hood of uQ on Tff+S. • 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052040/manifest

Comment

Related Items