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 T H E DEGREE OF DOCTOR OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES D E P A R T M E N T OF COMPUTER SCIENCE We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA October 1990 F © Farzin Mokhtarian, 1990 In presenting degree this thesis at the University in partial fulfilment of of British Columbia, I agree that freely available for reference copying of this department publication or thesis by of this and study. for scholarly his thesis or her purposes for financial Computer Science The University of British Columbia Vancouver, Canada Date DE-6 (2/88) October 5, 1990 agree that It is for an advanced the Library shall make it permission may be granted representatives. permission. Department of I further the requirements by the head understood gain shall not be allowed for extensive that without of my copying or my written 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, uniqueness, stability, efficiency, ease of implementation and computation of shape pro- perties. The regular representation for planar curves is referred to as the curvature 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 convolving 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 convolutions 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 contains 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 • List of Figures List of Tables Acknowledgments 1. Introduction 1.1. Criteria for shape representation 1.2. Contents of thesis 2. Survey of literature 3. A theory of multi-scale shape representation for planar curves • 3.1. The curvature scale space image 3.2. The renormalized curvature scale space image 3.3. The resampled curvature scale space image 3.4. Evolution and arc length evolution properties of planar curves 4. A theory of multi-scale shape representation for space curves '. 4.1. The curvature and torsion scale space images 4.2. The renormalized curvature and torsion scale space images 4.3. The resampled curvature and torsion scale space images 4.4. Evolution and arc length evolution properties of space curves 5. Algorithms and implementation 5.1. The convolution masks 5.2. The sampling algorithm 5.3. Algorithms for representations of planar curves 5.4. Algorithms for representations of space curves 5.5. Efficiency issues 5.6. Matching scale space images 6. Experimental results and evaluation 6.1. Planar curves 6.2. Space curves 6.3. Evaluation of the representations 7. Summary, conclusions and future directions 7.1. Summary 11 v vii viii 1 2 3 5 11 13 17 18 20 23 24 30 32 34 36 36 38 39 41 44 46 48 48 80 100 109 109 iv 7.2. Conclusions 110 7.3. Directions for future research Ill References Appendix A . Proofs of results on planar curves Appendix B. Proofs of results on space curves 114 120 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 Figure 6.1.1 Coastline of Africa Figure 6.1.2 Africa during evolution Figure 6.1.3 The curvature scale space image of Africa Figure 6.1.4 Koch's snowflake curve Figure 6.1.5 Snowflake curve during evolution Figure 6.1.6 The curvature scale space image of the snowflake Figure 6.1.7 Design from a Persian carpet Figure 6.1.8 Carpet design during evolution Figure 6.1.9 The curvature scale space image of the carpet design Figure 6.1.10 Coastline of Africa with uniform, random noise 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 Figure 6.1.14 Coastline of Africa with non-uniform, random noise Figure 6.1.15 The curvature scale space image of Africa with nonuniform noise Figure 6.1.16 The renormalized curvature scale space image of Africa 25 49 50 51 53 54 55 56 57 58 59 60 61 62 63 64 66 Figure 6.1.17 The renormalized curvature scale space image of Africa with non-uniform noise Figure 6.1.18 The renormalized CSS image of Africa with non-uniform noise superimposed on the renormalized CSS image of Africa 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 Figure 6.1.21 The resampled CSS image of Africa with non-uniform noise superimposed on the resampled CSS image of Africa Figure 6.1.22 A self-crossing curve during evolution Figure 6.1.23 The CSS image of the curve of figure 6.1.22 67 68 69 70 71 74 75 vi Figure Figure Figure Figure Figure Figure Figure Figure Figure Figure Figure Figure Figure Figure Figure 6.1.24 6.1.25 6.1.26 6.1.27 6.2.1 6.2.2 6.2.3 6.2.4 6.2.5 6.2.6 6.2.7 6.2.8 6.2.9 6.2.10 6.2.11 A convex, self-crossing curve during evolution The CSS image of the curve of figure 6.1.24 A simple curve during (regular) evolution Curve of figure 6.1.26 during arc length evolution Two views of a space curve depicting a fork The fork during evolution The torsion scale space image of the fork Two views of a space curve depicting a bottle-opener The bottle-opener during evolution The torsion scale space image of the bottle-opener A space curve depicting an armchair The armchair during evolution The torsion scale space image of the armchair The armchair with random noise The torsion scale space image of the armchair with noise 76 77 78 79 81 82 83 84 85 86 87 88 89 90 91 Figure 6.2.12 The renormalized torsion scale space image of armchair with noise Figure 6.2.13 The TSS image of armchair with noise superimposed on the TSS image of armchair Figure 6.2.14 The armchair with severe random noise Figure 6.2.15 The torsion scale space image of armchair with severe noise Figure 6.2.16 The resampled torsion scale space image of the armchair 92 93 94 95 96 Figure 6.2.17 The resampled torsion scale space image of armchair with severe noise Figure 6.2.18 The resampled TSS image of armchair with severe noise superimposed on the resampled TSS image of armchair Figure 6.3.1 A planar curve made up of straight line segments Figure 6.3.2 The curve of figure 6.3.1 with added random noise Figure 6.3.3 The curvature scale space image of the curve of figure 6.3.1 Figure 6.3.4 The curvature scale space image of the curve of figure 6.3.2 Figure 6.3.5 The CSS image shown in figure 6.3.3 superimposed on the CSS image shown in figure 6.3.4 97 98 102 103 104 105 106 vii L i s t o f T a b l e s Table 6.1.1 Comparison of regular, renormalized and resampled curvature scale space images 72 Table A . l Moment-pairs in equations (A.2) and (A.3) 128 Table B . l Moment-triples with M' ' 150 Table B.2 Moment-triples with M ' 150 Table B.3 Moment-triples with M ' 151 Table B.4 Moment-triples with M\ 151 Table B.5 Moment-triples with M ' 151 Table B.6 Moment-triples with 151 Table B.7 Moment-triples with AfJ Q 1 1 1 7 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 contributed 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 understanding 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 considerably 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 important area of research within Computer Vision is the problem of shape representation. This thesis considers the problem of representing the shapes of twodimensional 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(tt) = (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 formally 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 f o r s h a p e r e p r e s e n t a t i o n In the following, when two planar or space curves are described as having the same shape, there exists a transformation consisting of uniform scaling, rotation 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 possible 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 accurate 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 perform real-time recognition. By efficient we mean that the computational complexity 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 implementation 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. C o n t e n t s o f 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 representation 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 generalize 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 representation 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 curvature 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 discussion 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 S u r v e y 2 : 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 possible way to generalize it to apply to space curves is explained. The reason is that almost all three-dimensional shape representation techniques proposed in computer vision have been concerned with surfaces but not curves. A n 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 circumstances. The criteria listed in chapter 1 have been proposed for a generalpurpose shape representation technique independent of any particular applications. Furthermore, note that some of the representations were not originally proposed 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. 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 invariance criterion is not satisfied. a . Hough transform: 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 threedimensional 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 approximating 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 computes 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 occupancy 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 (perimeter /area) and eccentricity (ratio of the principal axes of inertia). Some, of these measurements, such as perimeter, can also be computed for space 2 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 information. 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 curvature. 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 endpoints 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 shapepreserving 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. [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. k. Fourier descriptors 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 varying 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 computed 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 primitiveedge tokens into coarser scale edge maps, and (b) pairwise grouping of symmetrically 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 w of w, s(w ) 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(w ). 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. Q 0 0 p. Volumetric diffusion [Koenderink & van Doorn 1986]: A geometrical object is defined by way of its "characteristic function" x ( ) 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 equation. The boundary of each blurred object is defined by the equation x(r) = 0.5. Alternatively, the boundary can be extracted by applying a Laplacian operator to the blurred function. This method does not generalize to space curves. The invariance criterion is not satisfied by this method since shapepreserving transformations of the object also affect the blurred objects computed by this method. This problem may be remedied by locating the curvature zero-crossing points of those curves and mapping those points to a curvature scale space representation as described in chapter 3. The stability criterion 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 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 [Babaud et al. 1986]. r 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 function 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 Gaussian 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 somewhat 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 deformations of a curve are not invariant with respect to shape-preserving transformations of that curve. This shortcoming may be remedied by locating the curvature zero-crossing points of those curves and mapping those points to a curvature 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 criteria 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], organization 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, approximate 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 proposed by Stansfield [1980] and later developed by Witkin [1983]. The function j{x) is convolved with a Gaussian function as its variance a 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. 2 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 suitable 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 curvature 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 [Mackworth & 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 technique presented in this chapter. 13 3.1. T h e c u r v a t u r e scale space i m a g e 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 (3.1-1) r(u) = (x(u),y(u)) 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. ., dr x For any parametrization f(u) = (x(u), y(u)) \r(u)\ = (x + y) 2 t ( U ) = W = 2 ^ (x + yy/ \x 2 2 2 1/2 + yY 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(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 du —— ds du = — — / c n = , •, |r|rcn. Hence K(U) 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 ) (x + y ) / 1 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))^ To see this, note that it follows from equation (3.1.2) that: ds Therefore ^ \ ( )\ r u Furthermore, t(-) = M) = 1 15 t ( » = (x(s), n ( » y(s)) = (-T/0), x(s)) • K(S) = t(s)-n(.s) and K(S) = x(s)yls) - x(s)y(s). Note also « W 2 = |t(3)| « (3) = 2 x\s)+y\s). 2 If the parameter is a linear rescaling of the arc length ranging over [0,1], the normalized path length parameter w, then W s = T |r(«,)| = I () n w - ^r(-y( ), K )) w K(W) = w - x(w)y(w)) and * 2 W = ^ ( i ' V ) + ii W). 2 This concludes the review of differential geometry of planar curves. Given a planar curve r = {(i(w) )(t ))|ii)6[o,i]} )! D 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/T 2 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 explicitly by X(u,(x) = f x(v) J -oo \—e 2<t2 CTV27T dv and Y(u,o) = f y{v)—^e 2 °* dv. -oo The curvature of T is given by a K(U,O) X (u,o)Y (u,o-) (X (u,a) + = u uu 2 u X (u,o)Y (u,o) Y (u,o) f uu u 2 2 u where du Y (u,a) = y(u) u ®g (u,o) u and uu(w) Y = 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 proportional 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 advantageous 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 normalized arc length parameter on the original curve T, the parameter u is not, in general, the normalized arc length parameter on the evolved curve T . In other words, arc length does not shrink uniformly everywhere on the curve during evolution. To correct this problem, Mackworth and Mokhtarian [1988] proposed the renormalized curvature scale space image. a Let R(u,a) = (X(u,cr), Y(u,o)) and w= § (u) a where u f\R (v,*)\dv v * » = 1 • J\R (v,a)\dv v o Now define X(w,a) = X($-\w),a) That is, each evolved curve parameter w. Y(w,a) = Y($-\w),o). is reparametrized by its normalized arc length Notice that *,(0) and (3.2.1) = 0 18 = > 0 du at non-singular points. 1 f\R (v,a)\dv v o Also $ (u) = u. 0 $<,.(«) 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 curvature of the curve with the normalized path length parameter is given by K(w,a) = -^-[X (w,a)Y (w,a) w - ww X (w,a)Y (w,a)}. ww w The function defined implicitly by K(W,(J) — 0 is the renormalized curvature scale space image of T. 3.3. T h e r e s a m p l e d c u r v a t u r e scale s p a c e i m a g e Note that as a planar curve evolves according to the process defined in section 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 The generalized evolution which maps T to [0,1]}. is now defined by: where r = {(X(w,a),Y(w ^))|w e[o,i]} r <r r X(W,a) = x(W)®g(W,a) Y(W,o) = y(W)®g(W,o-). and Note that 19 W= W(w,a) and W(w,o ) 0 where cr 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 T . 0 ff 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 & Hamilton 1986]. Let R(W,o) = (X(W,o-),Y(W,o-)). The Frenet equations for a planar curve are given by dt | dR dn Ih i , dR , , • == ~'"9T'.' c Let t = <T /2. Observe that 2 •dt" du l) ~ dt du ' du ~' { ) du ' dudt ' 1 ] Note that dR dR, du ~ du = { 1 1 and dR ——- = n K dt since the Gaussian function satisfies the heat equation. It follows that | ( i f i) = <ifr i' 2 - 2 2 ( l fr | t ( t - n Therefore A or c V dt du -~ ] ] Zl du 1 ' f ^ 2 t ) ) = - 2 | f | 2 " 2 20 d , dR , _ ; 3R , "r5F *a7 " "^T ' 2 1 l_ l l c Let L denote the length of the curve. Now observe that L 1 L —— = / -r-|——I du = - / I ——\n du = - IK Aw. dt {dt du< J du Q 2 { l 2 1 Q Since the value w of the normalized arc length parameter to at a point P measures the length of the curve from the starting point to point P, it follows that Q W dt J 0 and therefore tW W(w,t) = -JJ (W,t)dWdt 2 K + 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 computed 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 standard 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 invariant 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 evolution and arc length evolution. Theorem 3.4.4. The center of mass of a planar curve does not move during evolution 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 curvature 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 zerocrossing 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 . If all evolved and arc length evolved curves are in C , then all extrema of contours in the regular, renormalized and resampled curvature scale space images of V are maxima. 2 2 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 T be an evolved or arc length evolved version of T with a cusp point at u . There is a <5>0 such that intersects itself in a neighborhood of point u . a 0 Q 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 during 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 T be an evolved or arc length evolved version of T with a cusp point at u . There is a «5>0 such that T^+g has two new curvature zero-crossings in a neighborhood of w . a Q 0 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 economically. These bounding contours are space curves and can be extracted by thinning 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 proposed 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 information 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 vectorvalued 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 arclength 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 P be a common point of a space curve and a plane and let P be a 0 25 variable point of the curve. Let h denote the arc length between P and P and let dfr denote the distance of P from the plane. The curve and the plane are said to 0 have a contact of order at least n [Goetz 1970] at P if d = 0(h ). The plane n 0 h with the highest possible order of contact with the curve at P 1 S 0 called the oscu- lating plane at P . 0 With every point P of a space curve of class C is associated an orthonormal 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 vector 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 triple. The plane containing t and n is the osculating plane. The plane containing 2 n and b is the normal plane and the one containing b and t is the plane. Figure 4.1.1. The Frenet trihedron for a space curve rectifying 26 The derivatives of t, n and b with respect to the arc length parameter give us: dt —— = /cn, ds dn ,, , — — = -/ct 4- rb, ds dh — — = -rn. 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: y(u) = asinii x(u) = acosu 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 ~ a + b' 2 2 Since the curve is represented in parametric form, in order to compute curvature and torsion at each point on the curve, we need to express those quantities 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) + (y) 2 + 2 (i') 2 Given an arbitrary parametrization of the curve: £(r(tt)/|f(i»)|) «(«) = |t,| = |r(«)| _ |r(tt)xr(u)| |p(u)| \r(u)\ 3 In coordinate form VA 2 K(U) = ((i) + B + (y) 2 2 2 + C + 2 (z) f 2 2 where A = y z y z B z X - c z X i x = y 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 = -b n = s -(txn),n =.-(t,xn)n - (txnjn = Note that tnn is the mixed (txn)n^. We now make use of 4 , . t = r(a), of vectors t, n and product r(s) r(s) n = -r^f-, K tnn . s and is equal to n 3 s N n =—^--—r(s) s K to obtain x x x r(s) r(3)r(s) r(» " 2 (x) 2 y z y z y 'z + (y) 2 + In case of an arbitrary parametrization, we make use of: r(s) and = r(u)-^-, r(s) = r ( + *( )-J^, U (z) 2 28 to obtain / > > _ f(u)*r*(u)r'(u) |f(»| |r(u)[ '(f(u)xr(u)) 6 f(u)'r'(tt) r(tt) 6 ~ 2 (r(u)xr(u)) 2 In coordinate form x y z x y z x y 'z T = A + B+ C 1 2 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 T . The convolution of a function f(u) and the Gaussian kernel is defined as: a oo F(u,°-)=f(u)®9(%cr)= / / ( * ) — 4 — e J 2<P iv. ovzir Furthermore, it is known that du du F(u,cr) = &nu,o) du 2 and du du 6 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 T is given by ff V D + E + F 2 K = 2 2 (X(u,cr) + Y(u,cr) + 2 Z{u,a) fl 2 2 2 where D = E = Y(u,a) Y(u,cr) Z(u,a) Z(U,CT) Z(u,a) X(u,a) X(u,a) X(u,a) X(u,a) Y(u,a) Y(u,cr) Z(U,<J) and F = and torsion on evolved curve T is given by a X(u,a) &V.,CT) X r = (u,<7) Y(u,a) Y\u,a) Y(u,a) ?(u,cr) Zlu,a) Z(u,cr) D + E + F 2 2 2 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 T are computed as a varies from a small to a large value. The torsion zero-crossing points of each Y 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. a a The curvature scale space image of a space curve is constructed in a similar 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 magnitude 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 T 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 Y where a € [OjCrJ and a 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. a a 0 t 4.2. T h e renormalized curvature images and t o r s i o n scale space Mackworth and Mokhtarian [1988] observed that although w is the normalized arc length parameter on the original curve T, the parameter u is not, in general, the normalized arc length parameter on the evolved curve T . To correct this problem, we propose the renormalized curvature and torsion scale space images. a Let H(u,a) = (X(u,a), Y(u,o), Z(u,o~)) and w= $ (u) a where u J]R ( >°~)\ v dv v *„(«) = 1 f\KM\dv o Now define • 31 X(w,o) = X(*-\W),<T) Y(w,a) = Y(Z-\w),o) Z(w,o) = (4.2.1) 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 T . That is, each evolved curve is reparametrized by its normalized arc length parameter w. a Notice that *„(0) = 0 and d$ (u) a du = |R„(tt,<7)| 1 >0 at non-singular points. J]KM\dv o Also * o ( « ) = «• $ (u) deviates from the identity function $ (u) = u only to the extent to which the scale-related statistics deviate from stationarity along the original curve. CT a 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 r e s a m p l e d c u r v a t u r e a n d t o r s i o n scale space i m a g e s Note that as a space curve evolves according to the process defined in section 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 parameter u of the smoothed coordinate functions X(u,cr), Y(u,o) and Z(u,o) 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 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 T is now denned by: a r r „ = {(X( W,a), Y( W,a),Z{ W,o))\W G [0,1]} where X(W,cr) = x(W) ®g(W,a) Y(W,a) = y(W) ®g(W,a) and Z(W,a) = z(W)®g(W,a). Note that W= W(w,o) and W(w,cr ) Q where cr 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 T . 0 a 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 = -dul lKn and du du du Let t = a /2. Observe that 2 d ,, cTR . d dR dR. _ dR cPR, dt" du ~ dt du ' du' ~ ^ du' dudt >' |2 1 } Note that = ( ( { 33 8R _ . dR . and dR —— = /cn since the Gaussian function satisfies the heat equation. It follows that ^'ftT 1 ) = 2 ( | -aT *•1^ l 17 ( / c n ) ) = 2 ( l • l 1 "-'"aT 1 K t + l 17 l K r b ) ) = - 2 | 17 l Therefore 2{ ~du~ dt d u - ~ l 1 ] du 2 { ] or di du ~~ 1 l du * • ] 1 Let i denote the length of the curve. Now observe that M a< = [JL \^\du = -} A { dt* du v /c du = -}/c aV o 2 5 [ u 2 Since the value w of the normalized arc length parameter w at a point P measures the length of the curve from the starting point to point P, it follows that Q W 2*L = -S \W t)dW o K % and therefore tW W(w,t) = -JJK\ W,t) dWdt + w. oo (4.3.1) 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 computed 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 resulting curve is reparametrized by the normalized arc length parameter and convolved 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 zerocrossings 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 evolution 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 invariant 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 evolution 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 . 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 renormalized torsion scale space image of V determines the function /3(IA) = T(U)K (U) uniquely modulo a scale factor (except on a set of measure zero). 3 2 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 T are in C and torsion is bounded at every point of V during evolution, then all extrema of contours in the regular, renormalized and resampled torsion scale space images of T are maxima. a 3 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 C 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 W or two projections of T _g intersect themselves in a neighborhood of point WQ. x Q ff 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 W , then either r g has two new torsion zero-crossings in a neighborhood of W or a torsion zero-crossing point exists at Wo on T _g and T^g. 0 <T+ 0 a 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 c o n v o l u t i o n m a s k s The convolution masks are approximations to the Gaussian function G(u,er) its first derivative -u-,2 -u G (u,cr) u cr \/2lT 3 its second derivative G (u,cr) uu and its third derivative uuu( i°) G u = 3^ - 2 tt 3 ^ cr V 27T 7 / 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 corresponding 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) e 2 ^ -360* 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 sampled input curve). The following is an algorithm for a function that computes a mask approximating the Gaussian function (or one of its derivatives): Algorithm: M A S K 1. 2. 3. 45. Let size = 12 o~ If size is even then size = size + 1 Let start = (1 - size) / 2 Let finish = (size - 1) / 2 For i = start to finish do mask[i] = Gauss(i, a) End of Algorithm: M A S K 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 element 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.) All products are then added up. The result is the value of convolution at element number k. 5.2. T h e s a m p l i n g a l g o r i t h m 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, P > ••• » Pm t sequence of points representing the original curve and let Qi> Q21 ••• > Qn be * sequence of sampled points on that curve. Note that Pi = Qi- If the input curve is open, P = Q . 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. D e n e 2 n e m Algorithm: S A M P L E 1. Let Qi = Pi 2. Letk = 2 3. For i = 2 to n do 3.1. Let old_k = k 3.2. Let D = d ^ Q Pk 3.3. while ( D < A 3 ) do 3.3.1. k = k+1 5.5.2. D = D + d ^ PkP 3.4. If ( k> oldjc ) then do 3.4.1. w = ( D - A s ) I d j> P M 3.4.2. Qi = w P _i + (1-w) P else do 3.4.3. w = ( D - A s ) I D 3.44- Qi = v, Qi_i + (1-w) P k k End of Algorithm: S A M P L E k n 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 sampling 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: C U R V A T U R E _ S C A L E _ S P A C E 1. Read(input curve) 2. Call SAMPLE —* n (* no. of sampled points *) 8. Let a = o~ (* o~ 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 Q 0 End of Algorithm: C U R V A T U R E _ S C A L E _ S P A C E 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(na ) to compute a curvature scale space image using algorithm CURVATURE_SCALE_SPACE. 2 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. a.2. a. 3. a.4. a.5. a. 6. Let distflj = 0 (* array dist holds the distances up to each point *) Let L = 0 (* L holds the total length of the sampled curve *) Call MASK_GAUSS(o) (* computes a mask based on the Gaussian fn *) Call CONVOLVE(x)],mask_gau3s[-» X[lJ Call C0NV0LVE(y[],mask_gauss[],1) -»• YflJ 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] else css[(dist[i]/L)n,o] = 1 =1 Algorithm RENORMALIZED_CURVATURE_SCALE_SPACE also takes 0(ncr ) 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. 2 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 coordinate functions with a mask corresponding to a small o. The output curve is sampled 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 algorithm 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 -> n 0 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)n ,cr] = 1 else c s s ^ i / n ) ^ ^ = 1 0 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 sampling 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 straightforward and that variations in its magnitude significantly affected the structure of the curvature scale space image. Therefore the curvature scale space representation 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 distinguish 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 representations. 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 3. Let a = cr (* a 0 4- Let p=l —> n (* no. of sampled points *) is relatively small; usually two Q *) (* p holds the no. of torsion zero-crossings 5. While (p > p ) do Q 5.1. Letp (* where p 0 found *) is a small number *) = 0 5.2. Call MASK_lST_DERIV((x) (* 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 MASK_3RD_DERIV(a) (* computes mask based on 3rd deriv. of Gaussian *) mm 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[ 5.8..Call ],mask_2ndf CONVOLVE(xf 5.9. Call CONVOLVEfyf ],1) z'fi] J,l) -> x"fl] J,mask_2ndfJ,l)^y"flJ 5.10. Call CONVOLVE(z[J,mask_2ndf 5.11. Call CONVOLVE(xf J,mask_Srd[ J,l) -+ x"'[lj 5.12. Call CONVOLVE(yf J,mask_Srdf -+ 5.13. - A Call CONVOLVE(z) , T 1 r-i l ],1) -+ J,l) J,mask_Srd[ J,l) in 1 n in n 1. . 111 1 - z x y + y zx 5.15. For i = 2 to do n y'fl] —> z'flj 11 5.14- Let r[lj = z xy z'flj 111 1 - y xz 5.15.1. Call CONVOLVE(xf ],mask_lst[],i) 5.15.2. Call CONVOLVE(yf ],mask_lstf n '// . ' 11 + x yz -> z'fij J,mask_2nd[ J,i) -> 5.15.5. Call CONVOLVER J,mask_2ndf J,i) -> x'fi] y'fi] 5.15.6. Call C0NV0LVE(z[J,mask_2ndfJ,i) -» z'fi] 5.15.7. Call CONVOLVER -• x'fi] J,mask_3rdfJ,i) 5.15.8. Call CONVOLVER],mask_Srd[ 5.15.9. Call CONVOLVE(zf],mask_Srd[],i) wn T . r -i III I II III II I , /// 11 zy -+ x'fi] 5.15.4. Call CONVOLVE(xf w 1 ],i) -> y'fi] 5.15.3. Call CONVOLVE(z[J,mask_lstfJ,i) - HI - x / II ],i) -+ y'fi] -+ z'fi] 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 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 = 1 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 coordinate 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 convolved 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 therefore 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)n aJ = 1 Q) Similar analyses show that algorithms TORSION_SCALE_SPACE and RENORMALIZED_TORSION_SCALE_SPACE take 0(na ) time to compute torsion scale space images and algorithm RESAMPLEDJTORSION_SCALE_SPACE takes 0(rn) time to compute a torsion scale space image. 2 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 investigate 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 , then the location of those points at level a +Aa can be determined by searching only a neighborhood of the zero-crossing points at level cr . 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. 0 0 Q Let n and c be the number of sampled points and the number of curvature zero-crossings on the input curve respectively. It follows that the curvature scale space image can be computed in 0(ca ) 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. 2 45 2. Fast Fourier transforms can also be used to speed up the computation of curvature 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 description 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 description. To see why this is possible, note that if f(x) is a continuous function and <7l(x) and (7 ( ) Gaussian functions with widths CTJ and <r, then x axe 2 2 (J®9i) ®92 = (f®9 ) ®9i 2 = f®9z where </ is another Gaussian function with width <r and 3 3 <7 2 3 = a x 2 + <T . 2 2 The computation of the curvature scale space image again takes 0(na ) 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. 2 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 maximum 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 processor 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 magnitude of the step size in a. The low-resolution scale space image will be considerably 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 follows 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. M a t c h i n g 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 structure. The following is a scale space matching algorithm which should run considerably 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 distinguishable 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 R to be matched. Let E^ and E be the set of points thus 2 2 obtained. Let P , P , • • • , P be the extrema in E ordered by height and let Q\i Qi-> ' ' ' > Q be the extrema in E also ordered by height. The problem now is to assign each point of E to a distinct point of E which will minimize the total matching cost. The cost of assigning a point P 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 x 2 n n x 2 1 2 i 47 algorithm then is as follows: Algorithm: S C A L E _ S P A C E _ M A T C H E R 1. Create n nodes corresponding to the possible match of Pi and each of the extrema in E . Assign a cost of 0 to each node. 2 2. For each node (P\, QJ, compute the scale space transformation parameters which will transform the scale space coordinates of Q to the scale space coordinates of P j . / / the node (P\, represents a correct match, then these transformation parameters will cause the remaining extrema of to overlap with the remaining extrema of E in a one-to-one fashion. t 2 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 E to P 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 E and add the assignment cost to the node cost. 6. If there are no more unassigned extrema from either E± or E in the lowest cost node, then STOP: the lowest cost match has been found. Otherwise, go to step 5. 2 2 2 2 End of Algorithm: S C A L E _ S P A C E _ M A T C H E R Note that in general, if representation R is a good match for representa1 tion R , then point Pj will usually match point Q 2 the lt P will match Q , etc. and 2 2 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 R have roughly the same height. 2 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 C u r v e s Algorithm CURVATURE_SCALE_SPACE in section 5.3 was used to compute 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. Figure 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 perform a very good job of filtering out the detail on the curve and bringing out its basic structure. A very large value of sigmafiltersout 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 offigure6.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 , _ Figure 6.1.2. Africa during evolution (f) a = 64 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 infigure6.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 offigure6.1.7. This curve is the outline of a design taken from a Persian carpet. Figure 6.1.8 shows the carpet design during evolution andfigure6.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 vector 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 representations 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 A • III! f] <r=20 \ (7=10 \ : i <r=5 -i /\ i AA Wttty4 4UJ- \ 10 WW m \ A 1 Figure 6.1.6. The curvature scale space image of the snowflake A: 56 Figure 6.1.7. Design from a Persian carpet 57 Figure 6.1.8. Carpet design during evolution 58 F i g u r e 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 • F i g u r e 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 regular 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 curvature 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 F i g u r e 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 The Regular Curvature Scale Space Image The Renormalized Curvature Scale Space Image The Resampled Curvature Scale Space Image Advantages • Suitable for transformations consisting of uniform scaling, rotation and translation. • Suitable when uniform, low-intensity noise has corrupted the curve. • More suitable when there is non-uniform noise on the curve or local shape differences exist. • Most suitable when there is high-intensity, non-uniform noise or local shape differences exist. Disadvantages • Non-uniform noise or local difference in shape can cause problems. • Most computationally intensive. • 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 location of curves in an image or their locations with respect to each other is important. 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 translation. 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 evolution 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 representation 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 curvature 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 evolution 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 indicates that new "structure" is not created in the curvature scale space representations of simple curves [Marr & Nishihara 1978]. Note that a subclass of selfcrossing 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 boundaries 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) (d) <J — 28 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) (c) cr = 16 (d) a = 25 (e) <r = 32 (f) cr = 48 (7 = 4 F i g u r e 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. 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.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 depicting 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 infigure6.2.6. Horizontal lines have been drawn across that image to indicate the values of a which were used to compute the curves offigure6.2.5. The third example is the curve shown infigure6.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 proposed 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 torsion 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 infigure6.2.15, no longer matches well with the torsion scale space image of the original armchair shown infigure6.2.9. However, 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 infigures6.2.16 and 6.2.17. Figure 6.2.1. T w o views of a space curve depicting a fork 82 (b) a = 5 10 Figure 6.2.2. The fork during evolution (d) a = 20 83 F i g u r e 6.2.3. The torsion scale space image of the fork 84 F i g u r e 6.2.4. Two views of a space curve depicting a bottle opener 85 (b)<r (c) a= 4 (d) a F i g u r e 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 F i g u r e 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 arguments 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 threedimensional 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 location 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 threedimensional 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 /?(«) = « («) r(u) where K(U) and r(w) are the curvature and torsion functions of that curve respectively. This shows that the torsion scale space images are often sufficient to distinguish 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 representation. 2 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 evolution 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 evolution 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 evolution. 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 representations, 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 reconstructed 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 representations 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 therefore 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 conjectured that they are not suitable for application to curves with straight segments 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 nonzero curvature and the computations will stabilize. Figure 6.3.1 shows a planar curve made up of straight line segments andfigure6.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 offigure6.3.1 andfigure6.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 infigures6.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 infigure6.3.3 superimposed on the CSS image shown infigure6.3.4 107 The error present on a space curve may be non-isotropic since most sensors 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 complexities 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 zerocrossings 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 offinite-sizedneighborhoods. 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 therefore 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 compute 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 deformation 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 threedimensional curves. Two-dimensional curves are boundaries of two-dimensional objects and three-dimensional curves can be considered to be abstract representations 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 computed 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 representations. 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 representations which again provides a sound, theoretical foundation for those representations. 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, renormalized and resampled curvature and torsion scale space images were given. Complexity 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 proposed 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 representation for planar and space curves. The representations are referred to as the curvature 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 properties 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 representations 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 possible 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 properties. 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 formally. 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 generalize 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 multiscale, geometric-based representation of the shape of that surface. Results about the local, global and convergence properties of the surface during evolution as well as the uniqueness properties of its representation would constitute a sound theoretical foundation for such a representation. A matching algorithm 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 problem. 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 zerocrossing 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 conditions under which it can be made stable with respect to noise. A similar argument 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 Mackworth [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 conditions. 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 Gaussian 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 drawings," 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, Englewood 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 incorporating 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 algorithm," 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 1982. convolution •product and some applications, D. Reidel, Boston, MA, 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," vol. 53, pp. 383-396, 1986. Biological Cybernetics, Lowe, D., "Organization of smooth image curves at multiple scales," ICCV, pp. 558-567, Tampa, Florida, 1988. Proc. 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. 275, pp. 483-519, 1976. R. Soc. Lond. B, vol. Marr, D., "Representing visual information," AI memo 415, MIT AI Lab, 1977. Marr, D. and E. C. Hildreth, "Theory of edge detection," vol. 207, pp. 187-217, 1980. Proc. R. Soc. Lond. B, Marr, D. and H. K. Hishihara, "Representation and recognition of the spatial organization of 3D structures," Proc. R. Soc. Lond. B, vol. 200, pp. 269294, 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. 3443, 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 Computational geometry, G. Toussaint (Ed.), North-Holland, Amsterdam, 1985. Pavlidis, T., "Segmentation of pictures and maps through functional approximations," 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 approximation of functions of one 2 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 pictures," 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 contours," 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. 445448, 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 generalized 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 twodimensional 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, d . W. Richards, pp. 97-125, Ablex publishing corp., Norwood, NJ, 1984. e 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. 362365, 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 T a evolved version of F = (x(w),y(w)). If T ff = (X( W,cr), Y( W,cr)) be an arc length is transformed according to an affine transform, then at its new coordinates, X-± and Yi, are given by X ( W,a) = aX( W,a) + b Y( W,a) + c x 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 X 2 and Y of the new curve are 2 X (W,a) 2 = (ax(W) + by(W) + c) ®g(W,cr) Y (W,o) = (dx{W) + ey{W) + f) 2 ®g{W,o). Since the convolution operator is distributive [Kecs 1982], it follows that X {W,o) = XyiW,*) 2 Y (W,a)= 2 Y^W,a) 121 a n d t h e t h e o r e m follows. • Proof of theorem 3.4.2: = Let T = (x(w),y(w)) be a closed curve and let ( X ( W,cr), Y{W,o) b e 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 o f T. O n T: (x(0),»(0)) = (x(l),i<l)). On T,: (X(0,Cr), F(0,(7)) = (X(l,Cr), It f o l l o w s t h a t T^. is c l o s e d . Proof of theorem 3.4.3: x(w) T = (x(w),y(w)) Let a n d y(w) are continuous Y{ W,o~) a r e a l s o c o n t i n u o u s . L e t W 0 an b e t h e v a l u e s o f X( W,a) infinitesimal infinitesimal change, functions a n d Y( W,cr) a t W 0 then a n d therefore be a n y value ofparameter Q y be a connected planar curve a n d b e 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 o f t h a t c u r v e . S i n c e T is Tg. = (X(W,cr),Y(W,cr)) connected, • X( W,a) respectively. a n d Y( W,a) will X( W,o~) a n d W a n d let x a n d 0 If W goes t h r o u g h also go through changes: X(W ,<r)-> 0 -> y + e. Y(W ,a) 0 A s a result, point P(x ,y ) 0 0 xo + 6 0 o n I V goes t o p o i n t P'(x + 6, yo + 00 * n e distance between P a n d P ' be D . T h e n D = VFTW < SV2 assuming |cS| is t h e l a r g e r o f \6\ a n d |^|. It f o l l o w s 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 parameter W also r e s u l t s i n a n i n f i n i t e s i m a l c h a n g e valued function T . a Therefore Y a Proof of theorem 3.4.4: coordinates (xj^,y ). M Let M be t h e center o f mass o f V — Then 1 fx(w)dw x = — M i n the value o f the vector- is a connected curve. j = fx(w)dw x fdw o • (x(w),y(w)) with 122 1 fy(w)dw y M = — 1 = fy(w)dw. x fdw 0 Let Tg. = (X( W,a), Y{ W,a)) be an arc length evolved version of T with N = (X ,Y ) as its center of mass. Observe that N N 1 X = Jx(W,a)dW N 0 1 OO j OO = f J g(v,a)x(W-v)dvdW = / g(v,o)(fx( W-v)dW)dv 0 -oo 0 -oo W covers Vg. exactly once. Therefore l Jx(W-v)dW= o x_ M So X N = M. X Similarly Y N ' 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(w )>c for every point w on T. Let T^ be an arc length evolved version of T. Every point of r is a weighted average of all the points of T. Therefore X(W ,a)>c for every point W on and is also contained in the same half-plane. This result holds for every line tangent to G therefore T is contained inside the intersection of all the left (or right) halfplanes created by the tangent lines of G. It follows that is also inside G. • 0 Q a 0 0 ff 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 zerocrossing 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 system 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( ,t) = —Le-'' / ' is G{u) = t^K 2 4 u Let = (x(u, t ), y(u, <)) be a curve obtained by convolving x(u) and y(u) with G(u, <Q). Assume that is in C^. Such a t 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 0 0 0 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) = x(u, t) = J J e-^'e*" (-w )i(u;)(L;. u 2 The Implicit Function Theorem guarantees that the contours u(t) are in a neighborhood of t . Let £ be a parameter of the curvature zero-crossing contour. Then Q d di du d di du _dt_ d di dt d k On the curvature zero-crossing contour, a = 0 and — - a = 0 for all integers k. di is known, all the derivaFurthermore, since the curvature zero-crossing contour tives of u and t with respect to i are known as well. k 124 We can now compute the derivatives of a with respect to £ at (u , ig). The first derivative is given by: 0 •|-«(«o,<b) = J t^t»Xiu)xXu>)fa -jjjK/t^t^iiwfy^)^ _ J -^ ^ (iu;) x(w)(L) f u e e^ e™ (iu)y(u)dJ) 3 2t e - fe-^'e^^xi^daj Note that the moment of order by: k (A.l) u Je^e^i^yi^dJ) of function /(w) = . e^ e \kS)x\u}) t w is defined oo M= 1 k J (*j)*e^;" (iw)x(w)Aj u —OO and the moment of order & of function /'(u>) = e~ ^ e (iu;)y(Lj) L t MU is defined by: OO \ p. i Affc = J ( i w ) * e ^ > ( « « ; ) j f ( u ; ) < L ; . u As a result, equation (A.l) can be re-written as: k) = ^ ( ^ M n - M M J ) (A.2) 2 + • ^ • ( J f J f J + M' M - M M, - M Mo). 2 dt. Z Q 2 3 Furthermore, the second derivative is given by: ^"K, <o) = ^t( M M - M M$ 2 (A.3) 125 + ^(M Mi + M^M - M' M - M M^) 2 + (±L)\ ^M M Q X + Q + 2-^j±(M^M 0 + 2 - M M' -M M'Z-M' M ) X 2 % X 2 MM) {M^M[ + 2M' M + 2 3 v 3 M'SMQ- 2 M'^M X - 2M M 3 2 M MQ). - 5 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 thefirstsix moments of those functions. In general, the &+lst equation, ——£a(u, t) — 0 is a quadratic equation in the first 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 w = 0. The next section shows that the moments of f(u>) and /'(u;) are the coefficients a and b in the expression of functions x(u) and y(u) in functions related to the Hermite polynomials. Therefore, having computed the first n derivatives of a at (u , t ), we have n+1 homogeneous equations in the first 4n+4 coefficients a and b . To determine the a and b , we need 3ra+3 additional and independent equations which can be provided by considering three neighboring curvature zero-crossing contours at 0 k k Q k Q k k k 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 d k —-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> (%a) related to the Hermite polynomials H (u) by k k 126 H (u) = (-l) e^e^ k k x(u) =Y,H( )<l k( ^)cr ) u The coefficients a (o~) of the expansion are given by k «jfc0) = <w (u,a),x(u)> k where <,> denotes inner product in L and {w (u,cr)} is the set of functions biorthogonal to {<f> (u,a)}. The {^j.(u,cr)} are given explicitly by 2 k k 2Jb-l U^<r) = —=e k\ v 27r — 2a jk -— — e ° dvr 2 and the w (u,o) by k w (u,a) = ( - 1 ) * — k e Since x(u) = -4= f e™\iu)x{u) dw the a are given by k V27T * du" The inner product is just the inverse Fourier transform of w (u,cr). Therefore k V < T a (a) = j(iu) e k 2 k 2 (iu) x(u>) dut 2 which is equal to M modulus a factor e^", since t = —. 2 Similarly, the function k M = -7-2/0) du can be expanded in terms of the functions (f> (u,a) by k y(u) =Y,b (a)<f> (u,a) k k and it again follows that b (a) = J(iu) e k 2 k which is equal to M' modulus a factor e . wu k (iu)y(u)<kj 127 Furthermore, a' (cx) and b' (er), the coefficients of expansion of functions x\u) and y(u) in terms of the functions <f> (u,a), can be seen to be related to a (o~) and b (a) according to the following relationships: k k k k k 4-1 = a 'k-\ = k{ ) a h(°)- h Therefore K(U), the curvature function of T can be expressed as: K(U) = x(u)'y\u) - y(u)x(u) = YI k(v)<t>k( ,<7). E a = JJ X u a 6 fc( )^(^ ) - S a M) 'k(^) l>j( ^ ) f k( ^) b ( u a < > a a -S u = S S ( j( ) *+lO) 6 6 S. h I] 4(°')^ik(«> ) cr j( ) k(a)<l>i( ,°)<l>k(u,o) a a u ;( ) Hl( ))^(^ ')^(^ ')c r a c r 0 It follows that if the pairs a {o-)b (o-), j,k — 0, ture function of T can be reconstructed. } hWM^v) c r k • • • 0 ,2n+l, are all known, the curva- 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 e (iu>)x(u}) and e^U" \iw)yXu;) at point O',* )t u W e tJU h a v e 0 x(u+u') = Je™e» \iu)xlu>)du = £ c cf> (u) y(u+u') = J\™e™\iw)y{u)<Lo = J] d <f> (u). u k k and . k k Now observe that Yi k<l>k{ ) = X) c u a kfa( + ') u u and That is, <j) (u+u) can be expressed as a linear combination of (f> (u) with j<k as has been shown in [Yuille and Poggio 1983]. k 3 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 functions f(u>) and f'(u>). The first n+1 equations form a system of homogeneous quadratic equations in the unknowns: M (u), • • • , Af (u) . and Mo( )> ' ' ' >^2n+i( )- The other points, u+u^ l<k<3, provide additional equations in the unknowns: M (u+u ), • • • , Af n+l( + Jt) ^MQ(u+u ), • • • , M (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. 0 u 2n+1 u u 0 k u aXi 2 2n+1 k Equations (A.2) and (A.3) can be converted into homogeneous linear equations 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 MQ + + Mi M 2 M 3 M 4 M + + + X X M 2 3 + M' M' X X A 5 X X X X 5 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 existing ones using the following relationships: MM'• M j ^ M ' r M i M^M'^ M * i _ M,-+IM;.^M; M M' i+1 m + 1 ^ Mjti^.MuM'j M^M'^ MjM^.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 contain 0(n ) moment-pairs. Therefore additional equations are required to constrain the system. To obtain those equations, we proceed as follows: w m 2 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 (u ,t ), the number of equations obtained will be equal to the number of moment-pairs and our linear system will be constrained. Q Q 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 computed 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 reconstructed 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 curvature 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 derivatives. The value of a in the resulting equations is then set to zero. Consequently, the arc length evolved curve T , where a corresponds to the scale at which the derivatives were computed, is reconstructed modulus uniform scaling, rotation and translation. ff The next step is to recover the original curve I\ This is done by applying reverse arc length evolution to V . Let the arc length evolved curve T be defined a 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 ff 130 x(w) = X(w,a) ©D^^cr) y(w) = Y(w,a) ®Dflw,(j) where D is a deblurring operator defined in [Hummel et al. 1987] and N aw 00 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 T is again reconstructed. Then each of its coordinate functions is deblurred by convolving it with the deblurring operator D . Once again T • is recovered modulo uniform scaling, rotation and translation. ff N Proof of theorem 3.4.7: Since by assumption all evolved and arc length evolved curves are in C , 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. 2 On any contour in the curvature scale space image K(U,CT) Since all = 0. are in C this is equivalent to: 2 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 convenient to change variables and let So we define x(u,t) = X(u,(j) y(u,t) = a(u,t) = x (u,t)y (u,t) u uu Y(U,(T) - x (u,t)y (u,t). uu u (AA) 131 X uuM = t( ^) x ( -) U A 2/« (M) = 5 (A.6) u On contours a (u,t) = 0: t = flu) t(u) = dt _ du ~ a a u t 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 a (u,t) = 0. u At an extremum where (A.7) holds, we have . 9 / - » \ du a ' d {- u\ du a , d (~u\ dt dt a du Q a v t a t t ~ a a uu t So we must show that if a(u,t) = a (u,t) = 0 u then > 0. u u a, We shall show that these conditions require —— = 1 which proves the theorem. a, From (A.4), (A.5) and (A.6) we have a = x y - xy u a u = x uuVt + t t u uVut ~ utVu ~ tVuu- x x x But using (A.5) a u = uVut - utVux ( -8) x A Similarly uu a = ( uVtt ~ ttyu) + ( tVut x x If a = a = 0 then using (A.4) and (A.8) u x x utVt)- 132 tVut - utVt x x = t(vut - ut—) = t(vut x x x ut—) u = -r( uVut u x t x x x - uty ) = x 0 u x SO a uu = uVtt - ttVux x We also have « t = ( uVtt ~ ttVu) ~ ( tVut ~ utVt) x x x x so t a and hence a uu = uVtt - ttVu x x = a as claimed. t Notice, incidentally, that a(u,t) satisfies the diffusion equation at the maxima 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 arbitrary 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 T . Since the class of polynomial functions is closed under convolution with a Gaussian [Hummel et ai, 1987], it follows that X(u,cr) and Y(u,a) are also polynomial functions: ff X(u, a) = a + a u + a^v? 4- a u + • • • 3 0 x 3 Y(u,a) = b + b u + b v? + b v? + 0 x 2 3 Suppose that Vg. goes through the origin of the coordinate system at u=0. It follows that a=&n=0. Assume further that there is a singularity on Tg at u=0. We have: 0 X (u, a) = a 4- la^u + 3a u 4- 4a u 4- • • • 2 u x 3 3 4 Y (u,a) = b + 2b u + Zb v? + 46 u 4- • • • 3 u x 2 3 4 Since X (u,o~) and Y (u,o~) are zero at a singular point, it also follows that a =6 =0. u 1 u 1 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 r (u,cr) = (X (u,a), u Y (u,<r)) = {mu^\ u nvT ). 1 u it follows that = (me - , ne"") = e -\m, m rJie,*) 1 1 m ne™) and r (-e,a) = (m(-e)^\ u 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 (-e,<7) = (-me™- , -ne"" ) = - e ^ m , 1 1 u ne™). A comparison of r (e,cr) and r (-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. u u 2. m and n are both odd. m-1 and n-1 are both even. Hence r (-e,<r) = (me -\ ne"- ) = e ^ m , ne^" ). m 1 1 0 Comparing r (e,cr) to r (-e, cr) now shows that the tangent direction does not change with u in a small neighborhood of the singular point. Therefore this singular point is not a cusp point. u u 3. m is odd and n is even. m-1 is even and n-1 is odd. Hence r (-<:,<7) = ( u m me -\ -ne"- ) = e -\m, 1 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 r H,a) u = (-me™" , ne"- ) = e -\-m, 1 1 m ne™). An infinitesimal change in u now results in a large change in the tangent direction. Therefore this singular point is a cusp point. It follows from the case analysis above that only the singular points in 134 cases 1 a n d 4 are cusp points. W e w i l l n o w derive analytical expressions for t h e curve T _g so t h a t i t can be analyzed i n a s m a l l neighborhood of the cusp p o i n t . a T o deblur function j[u) = u , we convolve a rescaled version of that funck t i o n w i t h the function —f=-e~* (l-x ), : > a n a p p r o x i m a t i o n to the d e b l u r r i n g opera- 2 V7T tor derived i n ( H u m m e l et al, 1987) good for s m a l l amounts of d e b l u r r i n g , as follows: oo or (D f)(y) t = -*(l-x )(y 2 e + 2xVT) dx k - O O where t is the scale factor a n d controls the amount of deblurring. S o l v i n g the i n t e g r a l above yields wjM> i.3.5 • • • = £ ( H ^ y ^ t - i ) ) - ( ^ i ) ; ( H ) . , / P=O (p even) T h e following are four functions o f the form /(tt) = u a n d their deblurred versions: k a . / ( « ) = v? c. /(tt) = tt /(tt) = = u -2t (D f)(u) = u -6tu {D f)(u) =tt t b. /(«) = tt d. (D f)(u) 3 4 t 4 2 5 (D f)(u) 5 3 - 12*u - 36* =tt - 20tu - lSOr^tt . t tt 2 t 2 3 W e c a n now analyze the cusp points identified i n cases 1 a n d 4 above. I n case 1 , the curve T is a p p r o x i m a t e d b y ( t t ,tt")where m a n d n are b o t h even m a numbers. W e n o w deblur the curve t o o b t a i n : m-2 (D x)(u) t = u m C l itt m - 2 ctu -2 m • • •- 4 2 Cj2± t 2 tt m 2 2 2 n-2 (D y)(u) t =tt"- c > " - 2 - c ' ^ u ^ - • • •-c'„_2* 4 2 - Cjlt 2 2 _n tt - c'„t 2 2 . 7 Note that a l l powers of u are even a n d the constants Cj a n d c'j are a l l positive as follows from a n examination o f (A.9). It follows that 135 ro-2 (D x)(u) = mu m - (m-2)c tu - 1 m t - 3 1 • • • - 2c ^ t u 2 2 (D y)(u) = nu"" - (71-2)0'! to'*- 1 • • • - 2c'„_2 * 3 t « 2 "2" contain only odd powers of u and (2? f)(e) = -(/J f)(-e). Hence there is also a cusp point on the curve at u = 0. In fact, the cusp point must also exist on r itself. This is a contradiction of the assumption that T is in C . It follows that can not have a cusp point of this kind at u . t t 0 2 Q We shall now turn to the cusp points encountered in case 4. Recall that, in that case, the curve T is approximated, in a small neighborhood of the cusp point, by (u ,u ) where m is even and n is odd. Again we deblur the curve to obtain: a m n ro-2 (D x)(u) = u - c^u™- - c2f?vr^ m 2 t ••• -c^t 2 m v?-c t 2 m 2 T n-1 c\ivr (D y)(u) = u n t 2 - 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, such that x{u ) = x(u ) 1 and x^, (A.10) 2 !<«i) = (A.11) Since (D x)(u) contains even powers of u only, it follows from (A.10) that tij = -Vy. Since (D y)(u) contains odd powers of u only, substituting = -v^ in (A.ll) and simplifying yields: t t n-1 V- C'I^I"" 2 - c' < tt 2 2 n-4 1 - ••• - c'^t tij = 0. 2 "T" Since r _^ is of interest to us, we let t = S. We now obtain ff n-1 V - c'^u^ - c^V" 2 4 - ••• - 2 = 0. (A.12) 2 tti = 0 is one of the roots of this equation. For very small values of w the LHS of (A.12) is negative since the first term will be smaller than each of the other terms (which are negative). As u grows larger, the first term becomes larger than the 1? x 136 sum of all other terms and therefore the LHS of (A.12) becomes positive. It follows 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 T be such a curve. There are two distinct neighborhoods of T which contain point P. Let these neighborhoods be 5j and S . Note that Si and S 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 T does not self-intersect for c < a . a a 2 2 0 ff Recall that the infinitesimal movement of each point of Si and S is determined by the equation: 2 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 direction of the normal vector by an amount equal to the curvature at that point. It follows that if Si and S 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 S are on the same side of L. Note that S and S 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 simple before touching itself. Let S be the segment inside S , i.e., the tangent to S always has Si to the same side. It can be seen that Si has a larger curvature at P than S . It follows that after an infinitesimal amount of reverse arc length evolution, Si and ^ will intersect which is again a contradiction. It follows that T remains simple during arc length evolution. • 2 2 x 2 x 2 2 2 Proof of theorem 3.4.10: It will be shown that this theorem holds for an arbitrary parametrization of T . Therefore it must also be true of arc length parametrization or close approximations. a Let (x(u), y(u)) be an arbitrary parametrization of Tg. with a cusp point at u . 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 u , 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 (u ,u ) in a neighborhood of UQ where m and ~n are both even. This type of cusp point can not arise on T if T is in C We now 0 Q m n ff v 137 turn to the cusp points of case 4. Recall that in case 4, the curve T is approximated, in a neighborhood of u , by (u ,u ) where m is even and n is odd. Observe that ff m n Q x(u) = mu ~ m 1 x(u) = m(m-l)u m y(u) = nu ~ n 2 1 y(u) = n(n-\)u ~ n 2 and m+n-3 _ ( \ _ x(u)'y(u) - y(u)x(u) _ mn(n-l)u " _A\ m+n-Z - m(m-l) m+ K { U ) ~ (i(u) + y(u) f 2 2 ~ 2 ( A vn + W n 2 nu ^ f Since 7i>m, K(U) is always positive on either side of the cusp point in a neighborhood of u . Therefore no curvature zero-crossings exist in that neighborhood on 0 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) = u , we convolve a rescaled ver+ k 1 sion of that function with the function —^-e V7T lows: , the deblurring operator, as fol- oo F(u) = / -^e-*j(u+2xVt)dx -oo or oo F(u) = / e-* (u+2xVt) dx V 7T d 2 k - 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) The following are four functions of the form f(u) = u and their blurred versions a. f(u) = v? b. X«) = u c. j{u) = u 3 4 F(u) = u + 2t F{u) = v? + Qtu F[u) = u 4- 12tu + I2t> 2 4 2 138 d. J[u) = u F{u) = u + 20tu + 60t u . 5 5 3 2 An expression for r < T + 5 in a neighborhood of the cusp point can be obtained by by blurring each of its coordinate functions: X(u) = u + m c^u™- 2 m-2 v? + c^t + c r u - + ••• + c 2 m 4 2 n 2 + c'^vJ^ 2 ~2 2 Y(u) = u + c\ivT m 2 + • • • +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) = mu ~ + (m-2)c tu m l m + 3 1 • • • + 2c _ t m u 2 are odd, all powers of u in m-2 X(u) = m(m-l)u m + (m-2)(m-3)c ^ - + • • • + 2c 2 m 4 2 1 are even, all powers of u in n-l Y(u) = nvT 1 + (n^c'jtu"- 3 + • • • + c'^t 2 2 are even and all powers of u in n-3 Y(u) = n{n-l)vr + (n-2)(n-3)c' ^ " + • • • + c „_ t 2 ~2~ 2 n 4 1 3 are odd. The curvature of T a+0 in a neighborhood of UQ is given by = ^ ' x(u)nu)-nu)x(tt) (X(u) 2 + Y(u) f 2 2 Since the denominator of K(U) never goes to zero in a neighborhood of ti , the zero-crossings of K(U) are the same as those of 0 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)u ~ and the term with the highest power of u in Y(u)X(u) is rn{m-l)nu ~ 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. m+n m+n 3 3 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 T . • + ff 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, X , Y± and Zi are given by x X { W,CT) = a l ( W,cr) + b Y( W,a) + cZ( W,cr) + d x Y {W,a) = eX(W,cr) + fY(W,a) X + 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 X , Y and Z of the new curve are 2 X (W,a) 2 2 2 = (ax(W) + by(W) + cz(W) + d) ®g(W,a) Y { W,a) = 2 (e x( W) + fy{ W) + gz( W) + h) ®g( W,a) Z { W,a) = (ix( W)+jy{W) 2 + kz(W) + t)®g( W,a). Since the convolution operator is distributive [Kecs 1982], it follows that 141 X (W,a) = X (W,a) 2 1 Y { W,a) = Y { W,o) 2 x Z (W,a) = Z {W,a) 2 x • and the theorem follows. 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 T is closed. • ff 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 W be any value of parameter W and let x , y and z 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: Q Q 0 Q X(W ,a) ^ x + 6 0 0 Z( W ,(j) ^z 0 + e. 0 As a result, point P(x ,y ) on goes to point P'(x + 6,y -{- £, z + e). Let the distance between P and P' be D. Then 0 Q 0 D= 0 Q VS + i + e < SV2 2 2 2 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 T . 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 {^MIHMI M)- Then ff Z 142 fx(w)dw : x= = fx(w)dw. M fdw 0 Let IV = be an arc length evolved version of T with as its center of mass. Observe that (X(W,CT),Y(W,CT),Z(W,O-)) N = (X ,Y ,Z ) N N N 1 1 oo X = fx(W,cr)dW= N 0 oo j f f g(v,cr)x(W-v)dvdW = / g(v,a)(Jx{ W-v)dW)dv. 0 -oo -oo 0 W covers Y exactly once. Therefore l A fx(W-v)dW = x K o So XN — M. X Similarly Y N = VM and %N = MZ 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(w )>c for every point w on T. Let r be an arc length evolved version of T. Every point of T is a weighted average of all the points of T. Therefore X(W ,a)>c for every point W on and is also contained in the same half-space. This result holds for every plane tangent to G therefore T is contained inside the intersection of all the left (or right) halfspaces created by the tangent planes of G. It follows that T is also inside G. • 0 ff Q a 0 0 a a 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 zerocrossing 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)K (U). 2 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 Gaus4 sian filter G(u, t) = —Le^/ ' is G{u) = e-A Let = (x(u, io),y(u, t ),z(u, t )) be a curve obtained by convolving x(u), y(u) and z(u) with G(u,t ). 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 neighborhood of t . It follows that the torsion zero-crossings are given by solutions of j3(u, t) = 0 where [Goetz 1970] 0 Q 0 Q /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) K (U, t). 2 Using the convolution theorem, x(u, t), y(u,t) and as following: x( u, t) y(u, t) = Je^*e^iu) z(u,t) and therefore x(u, t) y(u,t) y(u>)dw (B.2) t) can be expressed 144 z(u, t) = . X (ti, t) = j e^ e^"(-icj )x(u;)ftu; 2t 3 y(u,t) = ^ z\u,t) = jf e^e^i-iuj )^) dw. 3 Note that the moment of order k of the function f(w) = e"" *e™"(vJ) x(w) is defined by: 2 oo M = J(u) e^e™(ia))i(u) dw l K - O O the moment of order k of the function f'(w) = e*^* e {iw) y(w) is defined by: >wu OO J\iw) e^ e {iw)y{w)dw M' = k K t iuu -oo and the moment of order k of the function f"(w) — €~^ e (iw) z(w) is defined by: 1 MU oo M = J (iwfe^te^tiw) z(w) dw. K -oo Therefore equation (B.2) can be written as: /3(u, t) = M M{M 0 2 M M'{M' Q - MQM M 2 X 2 + MQM M'{ + MQM^ 2 - MQM M{. 2 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 d£~ du d di du dt d di dt' d 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, t ). Thefirstderivative is given by: k 0 145 d Ql u . du ^(«o,<o) , <fr dffto.fr) where ffi(tto»*o) = M ' M M ; 3 du 0 M M 3 M ; ' - 0 M;MQM + M M' M X 3 Q - + M MQM X 3 X M M 3 0 ' M ; and d/?Po, <o=) M dt 3 + ilf 'M Mi - M M M M M2 4 0 + M MQM'{ 0 3 + M M' M A 3 Q Q - M±M M - 2 Q + M MQM 2 3 3 + M^MQM 2 - MlM' M M MQM X Q 2 - M^MQM[ X - x M MQM 3 2 and the second derivative is given by: a /? _^_a£ 2 = ^ 2 du . £ < _a/? / <% dt ^d£' du d + 2 2 _s £ , jujttj?(3_ 2 (dt\ a /? 2 2 i 2 di dudt , 2 ^di ef J . ' { ) where du = M 'ilf Mi + 4 0 MMM 2 3 - - M[M M'i 0 Q MMM 2 3 - M'^MQM 0 - X M M MQ 2 3 2 + M MQM A + M M M' X 2 3 + M^MQM Q + M M' MQ X 2 - M MQM{ Z - 4 M M MQ 2 3 a /? 2 dudt = M;M M[ + M M M' - M^M M'i - M M M Q 2 X + MMM + M MQM 5 3 2 x 3 Q + X 2 M^MQM x 3 M'^M' M - M M' % X Q + M M' M - M MQM' 2 3 X 5 X 2 3 - M M M{ 2 X 3 and ^ = MsM M + 2M';M M + M'sM M' + M M\M[ - M'^M M - 2M' M M Q 2 3 0 - MiM M - M M[M'{ 0 x + M' M^M'i + M MQM 6 2 2 x + M^MQM x Q M MQM S + X 2 3 2M 'M Afo + 3 & Q - 2M'^M MQ - M£MQM 2 + M M±M - M MQM[ 2 x X M£MQM 4 2 - + M^MQM 2 - M' M^M[ - 2M M MQ2 2 3 A i 3 0 M M^M 2 X + 2Jtf M M ' 4 3 0 M^MQM . 2 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 thefirstseven moments of those functions. In general, the fc+lst equation, —r/?( ) = 0 is a w 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 a , b and c in the expression of functions x(u), y(u) and z(u) in functions <f> (u,a) related to Hermite polynomials. Therefore we have n+1 equations in the first 6ra+9 coefficients a , b and c . To determine the a , b and c , we need 5n+8 additional and independent equations which can be provided by considering six neighboring torsion zero-crossing contours at (u^to), («2,tf ), (u^,t ), (tt , ig), k k k fc k k k k fc 0 0 4 («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 d k —T^( ' 0 w 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> (u,cr) related to the Hermite polynomials H (u) by k k d> (u,a) = (-1)* ^ (V2)* V7r k +1 H (u) = k ( - l ) k e ^ e - « g^-» ) <rv2 2 The coefficients ajt(cr) of the expansion are given by a k( ) = <w (u,cr),i(u)> a fc where <,> denotes inner product in L and {^(t^cr)} is the set of functions biorthogonal to {4> (u,cr)}. The {<j> (u,a)} are given explicitly by 2 k k k 147 2k-\ kK -^r jk —Z- k\V^ } du k and the w (u, a) by k W k k -— (-l) ^je~^ du" = M k Since x(u) = ^J" Je^\iw)x{w) du the a are given by k k * T I e ^ , e - « > (*,)*(«) <k = - J L (-l) J< aM fc v27r _ du ^ The inner product is just the inverse Fourier transform of w (u,cr). Therefore k a {cr) — J(iuj) e k (iu>) x{w) dw 2 k which is equal to M modulo a factor e^", since t = a ji. 1 k K Similarly, the functions 2/0) - -7-2/O) du can be expanded in terms of the functions <f> (u,o) by k 2/0) =S z(u) h(°)h(. ,°) u =J]c (a)(j) (u,a) k k and it again follows that = f(iu) e b (a) k k 2 c (cr) = / (iw) e k fc 2 (iw)y(u)dw (jw) z(u) dw which are equal to M' and M' respectively modulo a factor e . wu k k Furthermore, a, (<j), b' (a) and c' (o~), the coefficients of expansion of functions x'O), y(u) and z(u) in <f) (u,a) respectively, can be seen to be related to a (o~), b (cr) and c (a) according to the following relationships: k k k k k k k 148 = hW) (B.5) and <4'(cr), b'{.{a) and c (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 a (cr), b (a) and c (a) by the following relationships: k k k k 4-2(°") = JfcO) a &w(«0 = (B.6) Now observe that the function T(U) K (U) can be expressed as: 2 T(U)K (U) 2 = 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 ( ° ) ^ . ( ^ ) S ^ ' H ^ - O ^ S cfayhi***) R CR + E .( ) r .(^ )S °i< )^.<«» )S .VM«>*) c (T < i <7 =S S S ff <7 6 tfaWfaWMM^W^^Mw) - S S S «( ) i'( )4(°')^.(^ ^ c r ) ^ ( c ) a " S E E <T i 6 <7 .{ )«i( ) iW^ . )^{«»^)^«.^ <r ff <: tt ff 149 + S E E b + S E E - E S S i{°) K )4( )$i( > Wu,v)fa(u,<7) a a a u a iW) l )K{^) t>i{^^)<t>l^(r)(t) {u,a) c a a < k c =S E E i( ) i'(°') Jfe(^)^i(^^)^{^ )^jfc(^ ') <T a cr 6 + &.(*K0)4(*) + (a&Ho-Kio) -a (*)bjXo)c' (a) t 0 - b {a)a£cr)c&a) k c,<a)aj((r)6^) - cla)a'-(a)b {a)) t k 4>lu, a)(f> (u, <r)<t> (u, a). } k Using (B.5) and (B.6) we obtain =SSE( T{U)K\V) f f i . ( ) W ) w ( ) + i°) j+2(°) k+l(°) f f a - «i()6 i + 2 c f f (cr)cjt + h j(cr) - a + c 6,(a)a i + 1 (cr)c J t + 2 i(<r) H-l(<7)h+2(<7) c a c^a^^b^a)) ((T) - <£,P,o-)<^0, o-)4> (u,a). k It follows that if the triples a,{a)bj{a)c (a) in the equation above are all known, the function /3(u) = T{U)K (U) can be reconstructed. k 2 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~^ t (iu})x(u), 'e (iw)y{u) and e~~^ e' (iuj)z(u) at point (u\ ^). We have i t ,wu Vj)n uu x(u+u') = Je™ e" '(ko)x(u)dw = J] d <f> (u) z(u+u') = Je^e^\kj)~z(u;)dw = u u k k and Now observe that E d = E kM ) u a k l k( + ') ( > u u E ^fc( )=S fc^0+ ') e and u 6 u f <f> (u) k k 150 That is, u+u) can be expressed as a linear combination of <j> {u) with j< k as has been shown in [Yuille and Poggio 1983]. 3 iv. Reconstructing the function T(U)K (U) 2 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 equations 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' , 0 < k<6. K M M' 0 M5 Mi 2 M'Q M[ M 2 M 0 M X M 2 M + + + M X M 3 A 5 M 6 + + + X 3 M4 M5 M'e + + M 0 M' x X M X X X X M 2 M M M X X X X M 6 Table B.l. Moment-triples with M ' 0 3 4 5 + + X X X X X Table B.2. Moment-triples with M'{ 151 2 0 3 0 + x X M M M M M M M Mo M' M' M' M i M M x + + X M + M + X M M4 X M M M' M' M' M5 M'e M x A X 2 3 5 M'e 0 X x 2 2 + 3 X z X 4 X 5 5 6 6 Table B.3. Moment-triples with M 2 Mo M' M M M + x M M + X M X M X M M Me x 2 3 4 Table B.4. Moment-triples with M M'o M' M M Af M$ M^ M 5 Mg x Mo M M M M M M 0 x 2 3 X x X 2 X 2 3 4 X 3 3 4 4 5 5 6 Table B.5. Moment-triples with M'l Table B.6. Moment-triples with M ' 5 M'o M[ M M M[ M' M'e 2 Mo M M M M M Me 3 b X X x 2 3 A 5 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: = * j k MjM'^MlM^M-M'i M^M'^M'i MjM'^MlM^M'i M^M'^M'i 152 M i-l j+l k M i+l 'j+l 'k M M M&'^MU " MtM'jM'U.M^M'jMl Af MjiW;' l+1 M M MiM'^M'U _ M . M' MlM M' M \ , i 1 j i j k l . Jlf^M-M^ +1 Again we proceed to compute the first n derivatives at point (u ,t ) 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. Q Q Since this system is in terms of the first 2n+3 moments of functions f(w), and f"(ijS), it will contain 0(n ) moment-triples. Therefore additional equations are required to constrain the system. To obtain those equations, we proceed as follows: z 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 (u ,t ), the number of equations obtained will be equal to the number of moment-triples and our linear system will be constrained. Q Q 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 computed from the known ones using the relationships given above. Since all the momentTtriples MiMjM together determine function of (3(u), it follows that function (3(u) can be determined modulo constant scaling. k Yuille and Poggio [1983] have shown that a 1-D signal can be reconstructed 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 derivatives. The value of a in the resulting equations is then set to zero. Consequently, the arc length evolved curve T , where a corresponds to the. scale at which the derivatives were computed, is reconstructed modulus uniform scaling, rotation and translation. a 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 tw w(W,t) = JJ K (w,t)dwdt. 2 oo where t = cr /2. As a result, T is recovered modulo function j3(u). 2 To prove the same result about the renormalized torsion scale space image, evolved curve is again reconstructed, then each of its coordinate functions 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 , 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. 3 The torsion of each evolved curve V = (x(u,o-),y(u,o-),z(u,cr)) is given by: a 154 , T zxy - zy'x + y zx - yx'z 4- xyz - x zy \ M = (yz-zy) . . n 2 — . . , . . J — . . . . 2 +{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 T are in C that: a 3 fl(u,t) = "zxy - zy'x + yzx - yx'z + xyz - x zy where again . represents derivative with respect to u and t = c r / 2 . The functions x(u,t), y(u,t) and z(u,t) satisfy the heat equation: 2 Z ( M ) = t( J)z UU u Since evolved curves are all in C , the conditions of the implicit function theorem are satisfied on contours )3(u,t) •— 0: 3 t =i p ) i( ) - JL - I?i u du fi t The theorem will be proven if it is shown that if t(u) = 0 at any point on a torsion zero-crossing contour, then t(u) < 0 at that point. Observe that t(u) = 0 if and only if P (u,i) = 0 . It follows that at a point where t(u) = 0 : u d ( -Pu\ Pu\ <„> = ±(^L)= du ±(^L) [3 ' K du t x j3 ' t . + d( ~Pu\ ±(^L)JL dt -Puu dV- f3 ' du t = f3 t Therefore it must be shown that if /3(u,t) = fl (u,t) = 0 then f3 /f3 > 0 . u uu t We will now derive explicit expressions for j3 and /3 . Differentiating the expression for /3(u,t) with respect to u and simplifying yields: uu P (u,t) = z x y u tt u t - zyx tt u t + yzx tt u t - yxz ti u t t + x y ztt u t x z y. tt u t Differentiating the expression for /3 with respect to u and simplifying yields: U where 155 * 1 = ttu uVt Z + Vttu u t ~ Vttu u t + ttuVu t - ttu uVt X z x x z x z x z and * 2 = Vtu*tPu - tu ttVu + tuVtt u ~ t ytt?u + tu ttVu ~ Vt*Fu*ux z x z z z x 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 whereft(u,t)= (3 (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 (u ,u",u ) 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 u m x = mti™" 1 u x = m(m-l) M " 1 - 2 t z = m(m-l)(m-2) u™ -3 tu x = m(m-l)(m-2)(m-3)u - m 4 tt x = m(m-l)(m-2)(m-3)(m-4)ti - m 5 ttM and that y = u nuT> ~ 1 y = n(n-l) ii" -2 t y =n{n-l){n-2)vr z tu y = n(n-l)(n-2)(n-3)^ t t y = n(n-l)(n-2)(n-3)(r -4)t r ttu i and that * = pu^ 1 0 z = t z tu = vT 2 p(p-l)(p-2)u^ z t = P(p-l)(p-2)(p-3)u^ t i 5 p 156 htu = ?(?-l)(p-2)(p-3)(p-4) It now follows that at point P: Poo ~ " l t ~ H ^ + "2" t r n + n + 1 —1 + —2 ^ -E u P8 m+n+ ~ S - S & 2 x 2 where Hi = (p-l)(p-2)(p-3)( -4)(n-l) - (p-l)(p-2)(p-3)( -4)(m-l) P P + (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 = ( -l)(p-2)(p-3)(r -l)(n-2) - (p-l)(p-2)(p-3)(m-l)(m-2) 2 p l + (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)(p + (n+m-10)p + n + m + mn - lOn - 10m + 35) 2 2 2 and that: E = (p-n)(p-m)(n-m)(p(n+m) - 3(n+m) - dp + mn + 7). 2 It can now be concluded that to prove the theorem, it must be shown that: |3il>|S | 2 or > |A | 2 where Ai = p +ra +m +7ip+mp+mn-10p-10n-10m+35 2 2 2 and A = np+mp+mn-3p-Zn-^3m+7. 2 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 (u ,u",u ) was used to approximate the curve around point P. It follows that in a neighborhood of P, torsion is given by: m p , v = A t t P+n+m-6 where A, A A and A 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: l5 2 3 lim r(u) = , ^ , U r u^o s £ + 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 . Therefore we will consider only odd values of m. 3 Case 1. Suppose m>7. Recall that p>n>m. It is easily seen that both A j and A are positive. So the absolute value signs can be dropped and the inequality: 2 A!>A 2 can be simplified. As a result, we must now show that the following inequality holds: p +n +m > 7p+7n+7m-28. 2 2 2 Note that m >7m, n >7n and p >7p. It follows that the inequality does hold. 2 2 2 Case 2. Suppose m = 5. Again, it can be seen that both A j and A are positive. We must again show that: 2 158 p +n +m > 7p+7n+7m-28. 2 2 2 Substitute m=5 in the above inequality. We now have: p +n > 7p+7n-18. 2 2 Since n>6, n >7ra-18 and since p>ll, p >7p. Hence the inequality again holds. 2 2 Case 3 . Suppose m = 3. Substitute this value for m in Aj. As a result, A simplifies to: p +n +np-7p-7n+14. 2 x 2 Note that 7i>4 and p>8. So p >7p. Hence to show that A is positive, it is sufficient to show that: 2 x n +np-7n+14: > 0. 2 Since p>8, np>8n. Therefore: n +np-7n+14 > n +8n-7n+l4 = n 4-n+14 > 0. 2 2 2 Now substitute m=3 in A . As a result A simphfies to: 2 2 7ip+3p+3n-3p-3n-9+7=np-2 which is always positive. Therefore we must again show that: p +n +m > 7p+7n+7m-28. 2 2 2 Substituting m=3 in the above inequality yields: p +n > 7p+7n-l6. 2 2 Since p>8, p >7p and it is sufficient to show that: 2 n > 7n-16. 2 It is easily seen that this inequality is satisfied for n>4. Case 4. Suppose m=l. Substituting this value in A simphfies it to: x p +n +np-9p-9n+26. 2 2 Since p>4, p -9p>-20. Hence to show that Aj is non-negative, it is sufficient to show that: 2 n +np-9n+6 > 0 2 Again since p>4: n +np-9n+6 >n +4n-9n+Q = ri -57i+6 2 2 2 which is non-negative for n>2. Now substitute for m=l in A to obtain: 2 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 is also non-negative. Therefore we must again show that: 2 p +n +m > 7p+7n+7m-28 2 2 2 Substitute for m= 1 in the above expression to obtain: p +n > 7p+7n-22 2 2 which is equivalent to: (p ~7p) + (n -7n)+22 > 0. 2 2 If n=2, then n -7n = -10 and p>4. It follows from p>4 that p -7p > -12. As a result, the inequality above is satisfied. If n>2, then n -7n > -12 and p>5. It follows from p>5 that p -7p > -10. Therefore, the inequality above is again satisfied. 2 2 2 2 This completes the case analysis. We have shown that the inequality: |Ail > | A | 2 and therefore the inequality: ISil > | 3 | 2 is satisfied for all valid triples of values of m, n and p. Therefore f3 //3t is always positive. Hence all extrema of contours in all torsion scale space images of T are maxima. • uu Proof of theorem 4.4.8: It will be shown that this theorem holds for an arbitrary parametrization of T . Therefore it must also be true of arc length parametrization or close approximations. a 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) = a + a u + a^u + a u + • • • 2 Q 3 x 3 Y(u,a) = b + b u 4- b u + b v? 4- • • • 2 0 x 2 3 Z(u,a) = c 4- c u 4- c u + c v? -f • • • 2 0 x 2 3 Let T,,. go through the origin of the coordinate system at u =0. It follows that 0 160 a =& =c =0. Every cusp point is also a singular point of the curve. Therefore has a singularity at UQ. NOW observe that 0 0 0 X (u,o) = a + 202^ + 3a u + 4a u 4- • • • 2 u x 3 3 4 Y (u,a) = b + 2b u + 3b u + 46 u 4- • • • 2 u x 2 3 z 4 Z (u,o) — c 4- 2c ii + 3c u 4- 4c u 4- • • • 2 u X (u,a), u x 3 3 2 4 Y (u,a) and Z (u,o~) are zero at a singular point. It follows that u u ^=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 u is also a cusp point. Since is examined in a small neighborhood of point u =0, it can be approximated using the lowest degree terms in X(u,a), Y(u,a) 0 Q and Z(u,a): T = {u ,u ,v?) m n a Assume without loss of generality that p>n>m. Observe that r (u,<r) = (X (u,o-), Y (U,<T),Z (U,(T)) = u u u {mu^^nu^^pvT ) 1 u Therefore r (e,a) = (me" - ,!!^ ,?^ ) = 1 1 1 1 u e - (m,ne - ,pe - ) m 1 n m p 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 r (-e,<7) = (-me - -nt - ,-j)e^ ) = n, 1 n 1 1 ) u -e - (m,ne - ,pe^ ) m l n m m Comparing r (e,cr) to r (-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. u u 2. m and n are even, p is odd. m-1 and n-1 are odd and p-l is even. Therefore r (-e,cr) = ( - m e ^ , - " ^ , ? ^ ) = 1 u 1 1 e^\-m-ne^ ,pe^ ) m m A comparison of r (e,cr) and r (-e,<r) again shows that an infinitesimal change in u u 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 r (-e,a) = (-me^ , ne^-peT ) 1 = 1 u ^{-m^ne^-pt™) An infinitesimal change in u again results in a large change in the tangent direction. 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"- ^^ ) = e"^\-m, n e ^ p e ^ ™ ) 1 1 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 r (-e,<r) = (me "- ,-ne - ,-pe - ) = e - (m,-ne - ,-pe^ ) r 1 ,, 1 p 1 m 1 n m m u A comparison of r (e,cr) and r (-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. u u 6. m is odd, n is even, p is odd. m-1 is even, n-1 is odd and p-1 is even. So o(- >cr) = (me" - ,-^^ ,?^ ) = r e 1 1 1 1 e ^\m,-ne - ,pe - ) T n m p 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 r (-e,cr) = ( m e ^ n e ^ - p e ^ ) = e ^ m , ne"- ,-pe^ ) 1 m m u 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 r (-e,<r) = ( m e ^ n e " - , ^ ) = e^\m, 1 ne^pe**-™) 1 u 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) = u , a rescaled version of that function is conk volved with the function —y=.e~^(l-u). This function is an approximation to the 2 V7T deblurring operator derived in [Hummel et al. 1987] and is good for small amounts of deblurring. The convolution can be expressed as oo (D f)(u)= \ -Z=e- {l-v )f{u + 2vVt)dv J V 7T x? t 2 or J e^il-v^u (D f)(u) = t + 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) T _ can now be analyzed in each of the cases 1-4: ff s Case 1: r is approximated by u ) where m, n and p are even. p a To obtain analytical expressions for functions: we deblur each of its coordinate m-2 (D x)(u) = u m t tu m Cl 2 - ••• - Cjn± t 2 m v? - c^t 2 2 n-2 (D y)(u) = u - c[tvT - ••• -c'^ t n t 2 2 2 2 _n u - c' t 2 2 n 163 P-2 (D z)(u) = vP- cltvT - •• • • - c"^ t 2 t 2 2 _P u - c" t 2 2 L Note that all powers of u are even and all constants are positive. It follows that (D x)(u) = mu - - (m-2)c tu "- - • • • -2c _ m 1 r t ro-2 z 1 m t 2 2 « 2 rt-2 (D y)(u) = nu"- - (n-2)c{to"- - • • • - 2c '„_ 2 1 3 t 2 « 2 u 2 ~2~ p-2 (2? i)(u) = pu^" - (p-2)c>^- - • • • - 2c'^t ~T~ 1 3 t contain only odd powers of u and (D r)(e) = -(£> f)(-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 contradiction of the assumption that T is in C . Therefore can not have a cusp point of this kind at t ^ . t t x Case 2: T is approximated by (u , u", u ) where m and n are even and p is odd. m p a T _g is obtained by deblurring each of its coordinate functions: a m m-2 (D x)(u) = u - c tu - - • • • - c^f^u m m t 2 - c„t 2 x 2 2 n-2 (D y)(u) = u - c' tvr - ••• - c'^t n t 2 2 _n u -c'„t 2 2 x 2 2 2 P-1 (D z)(u) = uP~ c'i~iuPt 2 - ••• - c"p_!* 2 tt Note that (Z?x) and (D y) contain even powers of u only, (D z) contains odd powers of u only and all constants are positive. t t t The deblurred curve intersects itself if there are two values of u, u and t^, such that x x ( l) = u !<«i) = M X K«2) 164 Z(U ) Z(U2) = X It follows from the first two constraints above that u = -u^. Substituting for in the third constraint and simplifying yields: x p-l uf - c \tuf~ - • • • - c " 2 M i uj = 0 2 Now let t = 6 to obtain V- c\8u r- 2 x - ••• - u = 0 2 (B.8) x 2 The LHS of (B.8) is negative for very small values of u since the first term will be smaller than all other terms, which are negative. As u grows, thefirstterm becomes larger than the sum of all other terms and the LHS of (B.8) becomes positive. Therefore there is a positive value of u at which (B.8) is satisfied. Hence intersects itself in a neighborhood of UQ. x x x Case 3: T is approximated by (u ,u ,u ) where m is even, n is odd and p is m n n ff even. As in the previous case, we obtain analytical expressions for T _^: ff m-2 (D x)(u) = u m t c^u™- - •• • 2 Cjs± t m u - c^i 2 2 2 2 2 n-1 (D y)(u) = u - c[tvr - • • • - c'^t n 2 t 2 u 2 P-2 (D z)(u) = uP-c " ivr t x 2 - ••• - C t ~ 2 P V? - C " t 2 p J In this case, (D x) and (D z) contain only even powers of u and (D y) contains only odd powers of u. Again, T _g can be shown to intersect itself if there are two values of u, u and such that t t t a x x{u ) = x x^) y(u ) = y^) x z(u ) = z(u2) x It now follows from thefirstand third constraints above that u = -u^. Substituting for U2 in the second constraint, letting t = 6 and simplifying yields x 165 n-1 u n x - c[8u - - • • • n 2 u = 0 2 x (B.9) x 2 An argument similar to the one used in the previous case shows that there exists a positive value of u at which (B.9) is satisfied. Therefore T _s again intersects itself in a neighborhood of UQ. x a Case 4: T is approximated by (u , u , u ) where m is even and n and p are odd. m n p ff An analytical expression for in a neighborhood of UQ is given by m-2 (D x)(u) = u - c tu - - • • m m t 2 x • - C j 2 t _2 m - c^i 2 V? 2 2 2 n-1 (D y)(u) = u - c' tvr - •• • - c'^t 2 n 2 t u 2 x (D z)(u) = u - c " tvr - • • • - c p t 2 t x 2 u All powers of u in (D x) are even and all powers of u in (D y) and (D z) are odd. As before, T _ intersects itself if the three constraints t a t t s x(u ) = x(u2) x y(u ) = y(u2) x z(u ) = z(u2) x are satisfied simultaneously. It follows from the first constraint that u = -v^. Now substitute for in the second and third constraints, let t = 8 and simplify: x n-l u n x c' 8u - - • • • n x 2 =0 2 x (B.10) ~2~ P-1 UP X - c " 6U P- 2 x X - • • • - c "^6 (B.ll) u = 0 2 x ~2~ Each of the equations (B.10) and (B.ll) is satisfied at a positive value of u but, in general, the same value of u will not satisfy both. It follows that, in this case, T _s does not intersect itself. However, an argument similar to the ones in the previous two cases shows that the planar curves defined by (D x) and (D y) and by (D x) and (D z), that is, the projections of T _ on the XY and XZ planes respectively, do intersect themselves in a neighborhood of u . x x a t t t ff s Q t 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 arbitrary 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 T 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 T at u , we again conclude that only the singular points in cases 1-4 are cusp points. ff a 0 We now derive analytical expressions for T g so that it can be analyzed in a neighborhood of UQ. To blur function ftu) = u , we convolve a rescaled vera+ k sion of that function with the function , the blurring operator, as follows: V7T F(u) = / -L=.e~ j{u+2vVt)dv J V 7T ,? or F(u) = -j=~f e-^u + lvVt) dv 1 where t is the scale factor and controls the amount of blurring. Solving the integral above yields #w = £ 1.3.5 • •' • ( 2 p=0 i ' p / 2 ^ - 1 ) ; p (p even) • • ( ^ + 1 > ( B . 1 2 ) ' An expression for T in a neighborhood of the cusp point can be obtained by blurring each of its coordinate functions. Furthermore, expressions for T _g in a neighborhood of the cusp point can be obtained by deblurring each of its coordinate functions according to (B.7). ff+S a Each of the cases 1-4 can now be analyzed in turn: • Case 1: r„. is approximated by (u , u , u ) where m, n and p are even. m n p 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: T is approximated by a Observe that u , u ) where m and n are even and p is odd. n p 167 x(u) = mu™- x(u) = m(m-l)u - 1 m x(u) = m(m-l)(m-2)^i - 2 ^7, y{u) - riv."- y\u) = n(n-l)tt"- y(u) = n(n-l)(n-2)u"- z(u) = vv?- z(u) = p(p-l)uP- z(u) = p(p-l)(p-2)u - 1 2 1 2 3 3 p 3 Torsion on T^. is given by: , x "z'x'y - "z'yx + y z'x - y xz + xy'z - x zy n«) = TTT:—.. (yz-zy) ....—r + (zx-xz) 2 2 —T7-r . + (xy - yx)' or ««) = A + B+C • ( B , 1 3 ) where A = ((np(p-l) - pn(n-l))u^ ) B = ((pm(m-l) - mp(p-l))uP - ) 3 +rn C = ((mn(rc-l) - nm(m-l)) 2 3 2 u ^) m+ 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) = (p -3p+2)(n-m) + (n -3n+2)(m-p) + (m -3m+2)(p-n) 2 2 2 = np - mp - 3pn + 3pm + 2n - 2m + mn - 3mn + 2m - pr? 2 2 2 • + 3pn - 2p + pm - 3pm + 2p - nm + 3mn - 2n 2 2 = (n-m)p + (m -n )p + mn - nm 2 2 2 2 2 = (n-m)p + (m+n)(m-n)p + mn(n-m) 2 = (n-m)(p - (m+n)p + mn) 2 = (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 T . It follows from (B.12) that T^g is given ff+6 by: m-2 X(u) = u + c tu - + • • • + m m 2 x Cj2 _2 < m v? + 2 Cjl 2 t 2 2 n-2 Y(tt) = U + C ^ u " " + N • • • + C^_2 < 2 _n U + 2 c'^t 2 2 ~7~ 2 P-l 2(u) = vP + c ItvT + • • • + c "^t 2 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 T g. Since r is zero at u = 0, T has a torsion zero-crossing point at u = 0. a+ a+6 We next investigate T(U) on T^. From (B.7) it follows that is given by: m-2 (D x)(u) = u - d < « - - • • • - d„_21 m m t 2 m u- 2 d^t 2 1 ~2 2 n-2 (D y)(u) = u - d'^ivT - • • • - d'„_ t n 2 t 2 • n_ u - d'^t 2 2 2 2 ~2~ 7 £± (D z)(u) = vP-d'^vT 2 t - • • • - d'^t 2 2 u where all constants are positive, all powers of u in D x and D y are even, all powers of u in D z are odd and t equals 8, a small constant. It again follows that r = 0 a t t i = 0 , T i s positive for positive u and negative for negative u. Therefore there is also a torsion zero-crossing point at u = 0 on T _g. It follows that there is a torsion zero-crossing point at on T _g before the formation of the cusp point and on r<T+5 after the formation of the cusp point. t t ff ff t 169 Case 3: T is approximated by (u ,u ,u ) where m is even, n is odd and p is even. m n p a The proof is analogous to that of case 2, and the same result follows. Case 4: T^. is approximated by (u , u , u ) where m is even, and n and p are odd. m n p 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 u on T^. Therefore there are no torsion zero-crossing points in the neighborhood of UQ on Q IV We now investigate T(U) on T . It follows from (B.12) that T g is given ff+S ff+ by: m-2 X(u) = u + c^u™- + • • • + m 2 Cj2± t 2 TO V? + c^i 2 2 2 n-1 Y(u) = u 4- c^u"- + • • • + c'^t n 2 2 U ~2~ P-l Z{u) = u + p c '[tvT + • • • + 2 c" _ t 'u 2 p l ~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) (Z(u)X(u)) + (Y(u)X(u)) 2 2 = X(u)(Y\u)Z(u)-Z(u)Y(u)) (Z(u)X(u)) + (Y(u)X(u)) 2 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 , ^ = L3.5 • • • (n-2)W \, n-1 c'^t 2 —r2 . n-1 n-1 = 1.3.5 • • • n2 n l (n-1)! 2 i Similarly, at u = 0, the non-zero term of Z(u) is: P-1 c'^i 2 p-1 P-1 = 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 6 '„_ * — C 3 2 n-3 , 7 . n-3 n-3 = 6(1.3.5 • • • (n-4)) *] \ f = (1.3.5 • • • n)(n-l)2 6 (n-3)! (2 2 t 2 Similarly, at u = 0, the non-zero term of Z (u) is: p-3 6^3* p-3 p-3 =(1.3.5- -p)(p-l)2 2 2 2 2 Therefore Y(u)Z(u) - Z(u)Y(u) = (1.3.5 • • • n)(n-l)2 n-3 n-3 p-1 p-1 22 1 -*2 /"i q c . . . _\ o2 2 J 2 t n-1 - (1.3.5 • • • n)2 2 (1.3.5 • • • p)2 t (1.3.5 • • • p){p-l)2 2 n-1 < 2 p-3 p-3 * 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 negative 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 u on T ^. 0 ff+ 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 arbitrary 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 T = (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 a 171 UQ = 0 and that at ti T^ goes through the origin of the coordinate system. It follows that T can be approximated in a neighborhood of UQ by: 0 a r , = (tt",tt»uP) (B.14) where u , u and u 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. m n p SinceTO,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 Y at UQ. We will therefore look at the remaining four cases in whichTOis odd: a Case 1.TOis odd and n and p are even. Torsion on T 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 T 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 a a+ 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 u . Therefore torsion is zero at UQ on T g. As u grows, u , u and u ,. 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 T g in a neighborhood of UQ. Hence no new torsion zero-crossings have been created. 0 m n p ff+ a+ Case 2.TOis odd, n is even and p is odd. Torsion on T is again given by ( B . 1 3 ) . Since p+n+m-S is even, torsion is positive for positive and negative u on T . We now investigate torsion on T . 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 T at tiQ is given by: a ff ff+0 ff+6 . v _ ZXY- XZY _ (ZY) + (XY) 2 2 YjZX-XZ) ~ (ZY) + (XY) ' 2 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 u and is therefore positive in that neighborhood. Again no new torsion zero-crossings have been created. Q 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 T 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 T at u is given by: ff+ a+S Q , XYZ-YXZ Z(XY-YX) T\u) = r-rrr-rr^ = i-rrrrr^-. . ( YZf + (XZ) ( YZf + (XZ) x 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) (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+^. 2 Case 4. m, n and p are odd. Torsion on T 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 investigate torsion on T . 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 negative for negative u. Hence there are no new torsion zero-crossings in a neighborhood of u on T . • a a+S Q ff+S
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A theory of multi-scale, curvature and torsion based...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A theory of multi-scale, curvature and torsion based shape representation for planar and space curves Mokhtarian, Farzin 1990
pdf
Page Metadata
Item Metadata
Title | A theory of multi-scale, curvature and torsion based shape representation for planar and space curves |
Creator |
Mokhtarian, Farzin |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | 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, uniqueness, stability, efficiency, ease of implementation and computation of shape properties. The regular representation for planar curves is referred to as the curvature 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 convolving 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 convolutions 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 contains 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. |
Subject |
Curves, Plane Computer vision Curvature Torsion |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-01-20 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0052040 |
URI | http://hdl.handle.net/2429/30740 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
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
Cite
Citation Scheme:
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>
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