ON THE MEASUREMENT OF THE CURVATURE OF THE BOUNDARIES OF TWO-DIMENSIONAL QUANTIZED SHAPES by JOHN REAVELY BENNETT B.Sc, Queen's University, 1966 M.A.Sc, University of British Columbia, 1968 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in the Department of Ele c t r i c a l Engineering We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA January, 1972 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the requirements f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head o f my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be allowed without my w r i t t e n p e r m i s s i o n . Department The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada ABSTRACT The use of the mathematical concept of curvature as a p r a c t i c a l descriptor of shape for pattern recognition and image processing application i s investigated. A mathematical analogy between the construction of a two-dimensional curve from a given curvature function and the frequency modulation of a s i n u s o i d a l c a r r i e r with a message, i s drawn. I t i s shown that the curve describing the boundary of a two-dimensional shape i s i n fa c t a c i r c l e , frequency modulated with appropriate curvature information. The accuracy to which the curvature of the boundary of a binary shape can be estimated from a given quantized version of that shape, depends upon two factors i n the estimation process: - the contour t r a c i n g algorithm by which boundary points on the quantized shape are defined and the method whereby the curvature function i s smoothed to p a r t i a l l y remove the quantization noise r e s u l t i n g from the d i g i t i z a t i o n of the o r i g i n a l shape. In t h i s t h e s i s , s i x contour t r a c i n g algorithms are described and used to extract curvature functions from quantized t e s t shapes i n the absence of smoothing of any kind. Models of the average quantization noise c h a r a c t e r i s t i c s i n the frequency domain are then developed for the curvature functions corresponding to each of the s i x contour t r a c i n g algorithms. The models are used to compare the performance of the s i x algorithms on the basis of the quantization noise c h a r a c t e r i s t i c s of each. I t i s found that the u s e f u l bandx^idth of curvature functions obtained from quantized shapes i s somewhat less than the t h e o r e t i c a l l i m i t imposed by the Nyquist Sampling Theorem. The models developed serve to demonstrate the v a r i a t i o n i n the useful bandwidth of the curvature functions corresponding to each, contour tracing algorithm. The variation in bandwidth- with- quantizing array resolution can also be predicted with the models. The relationship between the bandwidth of a curvature function and the amount of detail representable in the corresponding curve in the plane is then qualitatively explored. Finally, three approaches to the problem of smoothing curvature functions to eliminate quantization noise are studied and methods are developed to compare their effectiveness on sample shapes TABLE OF CONTENTS Page ABSTRACT i TABLE OF CONTENTS " i i i LIST OF ILLUSTRATIONS v LIST OF TABLES x i ACKNOWLEDGEMENT x i i i 1. INTRODUCTION 1 1.1 Scope of the Thesis 2 1.2 Reasons for the Use of Curvature 3 2. THE THEORY OF CURVATURE 8 2.1 Classical Theory of Curves i n the Plane 8 2.2 Curvature in the Frequency Domain 10 2.3 Organization of Approach 21 2.4 General Comments on Procedure . . . . . 22 3. CONTOUR TRACING ALGORITHMS AND QUANTIZATION NOISE 24 3.1 Basic Curvature Functions 24 3.2 Quantization Noise Definitions 29 3.3 Quantization Noise Experiments 32 3.4 A Model for the Signal-to-Noise Characteristics of the . ' Basic Curvature Functions •••• 51 3.5 Curvature Domain Bandwidth and Boundary Detai l 64 3.6 Discussion on the Quantization Noise Experiments 69 3.7 An Introduction to Curvature Function Smoothing 71 4. TWO ERROR CRITERIA AND THE SLOPE APPROXIMATION METHOD 74 4.1 Two Error Cr i ter ia for Assessing the Effectiveness of the Smoothing of Curvature Functions 74 4.2 The Original Test Shapes for the Smoothing Study 79 4.3 The Slope Approximation Approach to the Smoothing of Curvature Functions 81 4.4 Some Conclusions on the Slope Approximation Approach to Curvature Measurement 96 5. AREA OPERATORS AND CURVATURE MEASUREMENT 98 5.1 Physiological Basis of Area Operators 99 5.2 Area Operators and Stimuli of Constant Curvature 105 5.3 The Response of the Area Operator to Impulses of Curvature 114 5.4 Discrete Area Operators 118 5.5 Experiments with Discrete Area Operators . 125 5.6 Curvature Domain F i l t e r i n g Methods 137 5.7 Some Conclusions Concerning the Various Curvature Measurement Methods 147 i i i Page 5.8 General Conclusions 153 APPENDIX I , 158 APPENDIX II 161 APPENDIX III 163 APPENDIX IV 165 REFERENCES . 168 iv LIST OF ILLUSTRATIONS Figure Page 1.2.1 Relative frequency of point placement for the preservation of shape (Attneave (36)) 5 1.2.2 The points of maximum curvature on a sleeping cat (Attneave (36)) 6 2.1.1 A closed curve i n the plane described i n parametric form by the vector R(s) 8 2.2.1 The two-dimensional curves i n the plane corresponding to i n d i v i d u a l Fourier harmonics i n the curvature domain. Harmonic numbers are i n d i c a t e d i n a l l cases 15 2.2.2 Examples of the closure technique applied to two curves i n the plane... 15 3.1.1 The s i x contour t r a c i n g algorithms and the corresponding b a s i c curvature functions. Column A shows the d i r e c t i o n s of search for successive boundary points i n each case. Column B shows the boundary points found by each algorithm on a simple shape (black dots) and column C shows the corresponding b a s i c curvature functions. 25 3.3.1 Samples of the o r i g i n a l shapes used i n the quantization noise study (A) and the average frequency component amplitude spectrum (B ) of the curvature function over the 100 sample shapes 3 3 3.3.2 The average frequency component amplitude spectra (U n) of the b a s i c curvature functions for the eighteen combinations of s i x contour t r a c i n g algorithms and three average array s i z e s 40 3.3.3 The average frequency amplitude spectra of the quantization noise on the basic curvature functions (N n) for the eighteen combinations of s i x contour t r a c i n g algorithms and three average array s i z e s 42 3.3.4 The values of the c o r r e l a t i o n c o e f f i c i e n t (p n) between i n d i v i d u a l s i g n a l frequency component amplitudes (S n) and the noise components (N n) for the eighteen combinations of s i x contour t r a c i n g algorithms and three average array s i z e s 45 3.3.5 The values of the c o r r e l a t i o n c o e f f i c i e n t (e n) between i n d i v i d u a l s i g n a l frequency component amplitudes(A Q n) and the components ( A ^ ) of the b a s i c curvature functions tor the eighteen combinations of s i x contour t r a c i n g a l g o r i -thms and three average array s i z e s 48 v Figure Page 3 . 3 . 6 The values of the sig n a l - t o - n o i s e c h a r a c t e r i s t i c CZ n ) at each frequency component for the eighteen combinations of s i x contour t r a c i n g algorithms and three average array s i z e s 50 3.4.1 A demonstration of the l e a s t squares f i t of the t h e o r e t i c a l curve (1/(1+3F)) to the experimental Z n values over the frequency range, 0 to .25 cycles per unit sampling distance f o r contour t r a c i n g algorithms 1 to 3 and at the three average array resolutions 3.4.2 A demonstration of the l e a s t squares f i t of the t h e o r e t i c a l curve (1/(1+3F)) to the experimental Z n values over the frequency range, 0 to .25 cycles per unit of the sampling distance f o r contour t r a c i n g algorithms 4 to 6 and at the three average array resolutions 53 3.4.3 The values of the "3" parameters as functions of periods for the s i x contour t r a c i n g algorithms found by a l e a s t squares f i t t i n g of the curve (1/(1+0F)) to the experimental Z values 55 _ i 3 . 4 . 4 The t h e o r e t i c a l Z n curves for the s i x contour t r a c i n g algorithms f o r approximately the same average array s i z e . . . 56 3.4.5 The t h e o r e t i c a l Z^ curves for the s i x contour t r a c i n g a l g -orithms f o r the same period (T=100) of the corresponding b a s i c curvature functions 59 4.2.1 F i f t e e n of the t h i r t y test shapes used i n the assessment of the curvature measurement methods and t h e i r corresponding curvature functions. V e r t i c a l s c a l i n g of the curvature functions was a r b i t r a r i l y s e l e c ted f o r pr e s e n t a t i o n a l c l a r i t y 80 4.2.2 Five of the test shapes quantized at each of the three array resolutions 82 4.3.1 Three sample frequency attenuation curves f o r the slope approximation approach to smoothing the ba s i c curvature functions 85 4 . 3 . 2 "Curvature Domain" and "Reconstructed Boundary Domain" errors averaged over t h i r t y test shapes f o r each of eleven d i f f e r e n t degrees of x(s):y(s) domain f i l t e r i n g and for each array r e s o l u t i o n , p l o t t e d versus the "Reciprocal of Absolute Bandwidth" i n cycles per unit sampling distance... 86 4 . 3 . 3 The r e s u l t s of the a p p l i c a t i o n of the slope approximation method to the f i v e quantized shapes at the three array resolutions of F i g . 4 . 2 . 2 . The curvature functions and corresponding reconstructed boundary curves were obtained v i Figure at the minimum ERRORi bandwidth values i n a l l cases Page 89 4.3.4 The r e s u l t s of the a p p l i c a t i o n of the slope approximation method t o three of the t e s t shapes quantized at an average array r e s o l u t i o n of 37x37, at f i v e degrees of x ( s ) : y ( s ) domain f i l t e r i n g . . . . . . 91 4.3.5 "Curvature Domain" and "Reconstructed Boundary Domain" e r r o r s averaged over t h i r t y t e s t shapes f o r each of eleven d i f f e r e n t degrees of smoothing and f o r each average array r e s o l u t i o n , p l o t t e d versus the " R e c i p r o c a l of Harmonic Bandwidth" (xlOO) 95 5.1.1 Receptive f i e l d o r g a n i z a t i o n (a) and s e n s i t i v i t y p r o f i l e (b) f o r an i d e a l r e c e p t i v e f i e l d . Impulse v o l l e y s from the c e n t r a l region (C+) have an e x c i t a t o r y (+) e f f e c t on the ganglion c e l l (G) i f the surround region v o l l e y s (S+) have an i n h i b i t o r y (-) e f f e c t and v i c e versa. The s e n s i -t i v i t y p r o f i l e s d e scribe the r e l a t i v e i n f l u e n c e of a photoreceptor on the ganglion c e l l f i r i n g frequency according to i t s distance from the r e c e p t i v e f i e l d center (r) 102 5.1.2 The response p r o f i l e of the i d e a l r e c e p t i v e f i e l d to a s t r a i g h t edge of i n t e n s i t y . The curve was obtained by moving the r e c e p t i v e f i e l d along a l i n e p e r p e n d i c u l a r to the i n t e n s i t y edge r e c o r d i n g the response at each p o i n t on the way. Distance of the r e c e p t i v e f i e l d center from the i n t e n s i t y edge i s i n u n i t s of the r e c e p t i v e f i e l d para-meter r„ (see equation 5.1.2). The r a t i o r ^ / r =.4.0 104 fa C 5.2.1 The response of the i d e a l r e c e p t i v e f i e l d to c i r c u l a r s t i m u l i of d i f f e r e n t r a d i i . The stimulus r a d i i , shown above each p r o f i l e curve, are i n u n i t s of the r e c e p t i v e f i e l d parameter r s . The r a t i o r s / r c = 4.0. The i n d i v i d u a l curves were obtained by moving the r e c e p t i v e f i e l d along a diameter of the c i r c u l a r s t i m u l i , s t a r t i n g at the center, r e c o r d i n g the response at each p o i n t along the way 107 5.2.2 The r e l a t i o n s h i p between the r e c e p t i v e f i e l d response centered over the boundary of a c i r c u l a r stimulus and the curvature of the boundary f o r r e c e p t i v e f i e l d s w i t h r s = 1.0 u n i t s (A), r g = .7 u n i t s (B) and r s = .4 u n i t s (C). D i s t a n c e , i n u n i t s of l / r g , r e f e r s to a value of r s = 1.0. The r a t i o r s / r c = 4.0 was h e l d constant i n a l l cases 109 5.2.3 The e f f e c t on the r e c e p t i v e f i e l d response to a c i r c u l a r s timulus of decreasing the width of the c e n t r a l r e g i o n , keeping r constant. In A, r s / r c = 2 . 0 ; B, r s / r c = 2.5; C, r s / r c i 3.33; D, r g / r c = 4.0; and E, r s / r c = °° 110 5.2.4 The response of the area operator to c i r c u l a r s t i m u l i of d i f f e r e n t r a d i i . The stimulus r a d i i , shown above each curve are i n u n i t s of the area operator parameter r s . v i i Figure Page The i n d i v i d u a l curves were obtained by moving the area operator along a diameter of the c i r c u l a r s t i m u l i , s t a r t i n g at the center and recording the response at each- point along the way 112 5.2.5 The r e l a t i o n s h i p between the area operator response centered over the boundary of a c i r c u l a r stimulus and the curvature of the boundary for area operator parameters r s = 1.0 (A), r s = .7 (B) and r g = .4 (C). Distance, i n units of l / r g i s for r s = 1.0 i n a l l cases 113 5.3.1 The d e f i n i t i o n of an impulse of curvature 1 1 5 5.3.2 The area operator response to impulses (wedges) of curvature of varying s i z e . Area operator response curves are shown as s o l i d l i n e s and the corresponding l i n e a r responses as dashed l i n e s . The l i n e a r curves were obtained by m u l t i p l y i n g the area operator response to a very small impulse by the appropriate constant. Impulse areas are A(23TT/24), B ( 5 T T / 6 ) , C(2ir/3), D(TT/2) , E(T T/3), and F ( T T / 6 ) radians per unit of arc length or1 distance from the impulse i n units of the area operator p r o f i l e parameter r s along the boundary 117 5.4.1 The d i s c r e t e area operator configuration of Connor (38) shown i n (a) with associated weights c a l c u l a t e d according to the Gaussian weighting p r o f i l e . The operator i s shown i n (b), (c) and (d) i n three possible boundary p o s i t i o n s on two p o s s i b l e o r i e n t a t i o n s of a s t r a i g h t edge of i n t e n s i t y . . . . 119 5.4.2 The d i s c r e t e " f i c t i t i o u s centered" area operator i s shown i n (a) with associated weights calculated according to the Gaussian weighting p r o f i l e . The operator i s shown i n (b), (c) and (d) located at two p o s s i b l e orientations of a s t r a i g h t edge of i n t e n s i t y i n each of the three p o s s i b l e boundary point p o s i t i o n s as defined by the boundary point detection l o g i c 123 5.5.1 Three sample frequency attenuation p l o t s f or the area opera-tor approach to the smoothing of the basic curvature functions 127 5.5.2 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y test shapes for each of eleven d i f f e r e n t sized area operators, quantized at each of three array sizes and p l o t t e d versus the "Reciprocal of Absolute Bandwidth" i n (cycles/U.S.D.)~1. The Gaussian weighting p r o f i l e was used throughout 128 5.5.3 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y test shapes for each of eleven d i f f e r e n t area operator s i z e s , quantized at each of three array res o l u -tions and p l o t t e d versus the "Reciprocal of Harmonic Bandwidth (xlOO)". The Gaussian weighting p r o f i l e was used throughout.. 129 v i i i Figure Page 5.5.4 The r e s u l t s of the a p p l i c a t i o n of the area operator as a curvature measurement device to the f i v e quantized shapes at the three array resolutions of F i g . 3.3.2. For each function, the operator s i z e was s elected so as to produce a minimum curvature domain e r r o r . Corresponding e r r o r and bandwidth values are provided i n table 5.5.1 132 5.5.5 The r e s u l t s of the a p p l i c a t i o n of the area operator to three of the test shapes quantized at an array r e s o l u t i o n of approximately 37 x 37, at f i v e operator s i z e s . Corresponding er r o r and bandwidth values are provided i n table 5.5.2 133 5.5.6 The two types of overlapping errors encountered i n the use of area operators to measure curvature. The black dots represent the discrete points of a quantized shape and the c i r c l e s represent the d i s c r e t e points of an area operator.... 136 5.6.1 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y t e s t shapes f o r each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and p l o t t e d versus the "Reciprocal of Absolute Bandwidth" i n (cycles per U.S.D.) -!. The exponential low-pass impulse response was used i n the curva-ture domain f i l t e r i n g 139 5.6.2 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y test shapes f o r each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and p l o t t e d versus the "Reciprocal of Harmonic Bandwidth". The exponential low-pass impulse response was used i n the curvature domain f i l t e r 140 5.6.3 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors f o r the t h i r t y test shapes for each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and p l o t t e d versus the "Reciprocal of Absolute Bandwidth" i n (cycles per U.S.D.) - 1. The "brick w a l l " f i l t e r was used i n the curvature domain 141 5.6.4 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y t e s t shapes for each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and p l o t t e d versus the "Reciprocal of Harmonic Bandwidth". The " b r i c k w a l l " f i l t e r was used i n the curvature domain 142 5.6.5 The r e s u l t s of the a p p l i c a t i o n of the curvature domain f i l t e r i n g methods of curvature measurement to f i v e of the te s t shapes, quantized at the 50 * 50 average array r e s o l u -t i o n . F i l t e r i n g i n each case was such as to produce a mini-mum ERRORS value. The exponential low-pass f i l t e r was used for r e s u l t s (a to e) and the b r i c k w a l l for r e s u l t s (f to j ) . . 2.44 i x Figure Page 5.6.6 The r e s u l t s of the a p p l i c a t i o n of the curvature domain f i l t e r i n g methods of curvature measurement to one t e s t shape quantized at the 37 x 37 array r e s o l u t i o n . F i v e degrees of f i l t e r i n g are shown- f o r the exponential low-pass f i l t e r (a to e) and for the "brick w a l l " f i l t e r (f to j) 146 5.7.1 A comparison of the r e s u l t s obtained with the d i f f e r e n t approaches to curvature measurement. Curves are averages fo r the t h i r t y t e s t shapes at a quantizing array r e s o l u t i o n of approximately 50 * 50. Methods are designated as slope approximation (S.A.), area operator (A.O.), curvature domain exponential low-pass f i l t e r i n g (C.D.L.P.) and curvature domain "brick w a l l " f i l t e r i n g (C.D.B.W.) 148 5.7.2 A comparison of the r e s u l t s obtained with the d i f f e r e n t approaches to curvature measurement. Curves are averages for the t h i r t y test shapes at a quantizing array r e s o l u t i o n of approximately 37 * 37. Methods are designated as slope approximation (S.A.), area operator (A.O.), curvature domain exponential low-pass f i l t e r i n g (C.D.L.P.) and curvature domain "brick w a l l " f i l t e r i n g (C.D.B.W.) 149 5.7.3 A comparison of the r e s u l t s obtained with the d i f f e r e n t approaches to curvature measurement. Curves are averages for the t h i r t y test shapes at a quantizing array r e s o l u t i o n of approximately 25 x 25. Methods are designated as slope approximation (S.A.), area operator (A.O.), curvature domain exponential low-pass f i l t e r i n g (C.D.L.P.) and curva-ture domain "brick w a l l " f i l t e r i n g (C.D.B.W.) 150 A. 1.1 A t y p i c a l portion of a d i s c r e t e o r i g i n a l boundary (black dots) i s shown superimposed on a square quantizing array ( i n t e r s e c t i o n s of g r i d l i n e s ) . The boundary points of the array as found by the quantization algorithm are shown as c i r c l e s 160 A.2.1 The r e l a t i o n s h i p between the b a s i c square of a square quantizing array ( c i r c l e s ) and the equivalent b a s i c t r i a n g l e (black dots) of an hexagonal quantizing array 161 A. 3.1 A possible l o g i c arrangement for the two-dimensional imple-mentation of area operators 163 x LIST OF TABLES Table Page 3.3.1 The average periods of the b a s i c curvature functions corresponding to the s i x contour t r a c i n g algorithms f o r three average array s i z e s 38 3.4.1 The a r b i t r a r i l y defined usable bandwidth of the s i x b a s i c curvature functions i n harmonics and cycles per unit sampling distance for approximately the same average array s i z e 58 3.4.2 The a r b i t r a r i l y defined usable bandwidth of the s i x b a s i c curvature functions i n harmonics and cycles per unit sampling distance for the same-period (T - 100) 60 4.3.1 The curvature domain e r r o r values (ERROR^) , the reconstructed boundary domain errors ( E R R O R 2 ) , the r e c i p r o c a l of absolute bandwidth values (C./U.S,D.) -l and the r e c i p r o c a l of harmonic bandwidth values f or the f i f t e e n shapes and functions of F i g . 4.3.3. The bandwidths i n a l l cases were such as to y i e l d a minimum ERROR^ value i n each case 90 4.3.2 The curvature domain e r r o r values (ERROR^), the recon-structed boundary domain errors ( E R R O R 2 ) , the r e c i p r o c a l of absolute bandwidth values (C./U.S.D.)~1 and the r e c i p -r o c a l of harmonic bandwidth values for the f i f t e e n shapes and functions of F i g . 4.3.4 92 5.5.1 The curvature domain errors (ERROR^) , the reconstructed boundary domain errors (ERROR?), the r e c i p r o c a l of absolute bandwidth values (C./U.S.D.)-I and the r e c i p r o c a l of harmonic bandwidth values for the functions and curves of F i g . 5.5.4. The curvature domain bandwidth was such as to produce a minimum value of ERROR-^ i n each case 131 5.5.2 The curvature domain errors (ERROR^), the reconstructed boundary domain errors (ERROR?), the r e c i p r o c a l of absolute bandwidth values (C./U.S.D.)~1 and the r e c i p r o c a l of harmonic bandwidth values f or the functions and curves of F i g . 5.5.5 134 5.6.1 The curvature domain errors (ERROR^) , the reconstructed boundary domain errors ( E R R O R 2 ) , the r e c i p r o c a l of absolute bandwith values (C./U.S.D.)~1 and the r e c i p r o c a l of harmonic bandwidth values for the curves and functions of F i g . 5.6.5 143 5.6.2 The curvature domain errors (ERROR^) , the reconstructed boundary domain errors (ERROR?), the r e c i p r o c a l of absolute bandwidth values (C./U.S.D.)~l and the r e c i p r o c a l of harmonic bandwidth values f or the curves and functions of F i g . 5.6.5 145 x i Table Page A.4.1 The o v e r a l l averages, the standard deviation values and the averages of f i v e subsets of 20 samples each for the amplitude of f i v e a r b i t r a r i l y selected harmonics of the 100 te s t shape curvature functions 165 A.4.2 The o v e r a l l averages, the standard deviation values and the averages of f i v e subsets of 20 samples each for f i v e a r b i t r a r y harmonic amplitude values of the quantization noise (N n) on the 100 quantized t e s t shape b a s i c curvature functions. Algorithm 1 was used i n the e x t r a c t i o n of the b a s i c curvature functions 166 A.4.3 The o v e r a l l averages, the standard deviation values and the averages of f i v e subsets of 20 samples each for f i v e a r b i t r a r y harmonic amplitude values of the quantization noise (N n) on the 100 quantized test shape b a s i c curvature functions. Algorithm 3 was used i n the e x t r a c t i o n of the b a s i c curvature functions 167 x i i ACKNOWLEDGEMENT I wish to extend my sincere thanks to Dr. J. S. MacDonald for his guidance and encouragement as supervisor of this thesis. I would also like to thank the National Research Council of Canada and the Northern Electric Company for their financial assistance in the course of the work. Finally, I would like to thank Miss Linda Morris for her cooperation and assistance in the typing of the thesis and my wife Myrna for her understanding and encouragement throughout these past few years of graduate school. 1 1. INTRODUCTION Of the schemes proposed f o r the machine categorization of two-dimensional, binary shapes or pattern silhouettes, (1-35), many employ measurements of boundary tangent angle or curvature i n the construction of the feature space. For example, the I.B.M. al p h a b e t i c a l character reading machine, based on the work of Grenias et a l . (10), uses contour t r a c i n g and tangent angle measurements i n the preprocessing stages. Ledley's scheme (15) for the c l a s s i f i c a t i o n of blood c e l l s and other b i o l o g i c a l shapes extracts boundary curvature as a function of arc length. Kasvand (25,26) has in v e s t i g a t e d the use of curvature i n nerve ending and water droplet counting. At the U n i v e r s i t y of Ohio, B r i l l (22, 23), Raudseps (21), C o s g r i f f (20) and F r i t z s c h e (19) have extensively investigated the use of boundary tangent angle as a function of arc length as a b a s i c descriptor for the c l a s s i f i c a t i o n of al p h a b e t i c a l characters. Others who have used curvature or tangent angle measurements for pattern recognition and other two-dimensional data processing applications include Masnikosa (11), Zahn (24), Connor (27), Freeman (33-35), Tomita et a l . (83) and R i n t a l a and Hsu (84). In s p i t e of the reasonably extensive a p p l i c a t i o n of these measures, two problems associated with t h e i r use have been l a r g e l y ignored. With few exceptions (.25-27), the methods used to measure these q u a n t i t i e s are r e l a t i v e l y complex and time consuming, and hence, i n r e a l time a p p l i -cations where speed i s important, these methods are at a disadvantage. Secondly, the problem of quantization noise on both curvature and tangent angle functions i s usually not considered. In preprocessing schemes where features are extracted by matched f i l t e r i n g on areas of the incoming patterns, quantization noise i s probably not a s i g n i f i c a n t problem. However, when contour t r a c i n g i s employed, this may not be the case since the areas of i n t e r e s t are r e s t r i c t e d to those regions of the patterns where the quantization noise i s the greatest. Furthermore, the processes of curvature and tangent angle measurement employ d i f f e r e n t i a t i o n , an operation with inherently poor noise properties since i t has a trans f e r function which increases l i n e a r l y with frequency. As w i l l be seen, the processes of curvature and tangent angle e x t r a c t i o n serve to take the quantization noise which has been amplified by the d i f f e r e n t i a t i o n and d i s t r i b u t e i t over the e n t i r e frequency range, hence preventing i t s r e -moval by simple low-pass f i l t e r i n g . This quantization noise can c o n t r i -bute s i g n f i c a n t l y to the variance of any qu a n t i t i e s extracted from the curvature or tangent angle functions, thereby degrading the performance of any scheme using those q u a n t i t i e s . 1,1 Scope of the Thesis This work represents an i n v e s t i g a t i o n i n t o the problem of measuring the boundary curvature or tangent angle functions of binary two-dimensional shapes, i n the presence of quantization noise. Broadly stated, the objectives are: 1. to i n v e s t i g a t e the nature of curvature as a shape descripto and to study and compare various approaches to the problem of measuring the curvature (and tangent angle) of the boundaries of quantized figures ( i n t h i s regard, a f a s t and accurate method i s sought), 2. to obtain a model for the quantization noise on the curva-ture and tangent angle functions which can be applied to the p r e d i c t i o n of the v a r i a t i o n i n the quantization noise with quantizing array r e s o l u -t i o n , 3. to compare square versus hexagonal quantizing array c o n f i g -urations on the basis of the magnitude of the quantization noise on the r e s u l t i n g curvature functions and, 4. to compare various contour t r a c i n g algorithms on the basis of the magnitude of the quantization noise on the r e s u l t i n g curvature functions. The r e s u l t s of the thesis have implications concerning many of the approaches to pattern recognition and two-dimensional data processing problems. However, the r e s u l t s are p a r t i c u l a r l y applicable to a scheme i n v o l v i n g the extraction of curvature or tangent angle as a function of arc length or distance around the boundary of quantized shapes and the subsequent expansion of the r e s u l t i n g p e r i o d i c function i n a Fourier s e r i e s . One object i n such a procedure would be to then use the se r i e s c o e f f i c i e n t s as "d e s c r i p t o r s " of the boundary shape i n a pattern recog-n i t i o n device. Such a scheme has been applied to the machine "recogni-t i o n " of a l p h a b e t i c a l characters by several authors, i n c l u d i n g Masnikosa (11) a n a most extensively by the Un i v e r s i t y of Ohio group, B r i l l (22, 23), C o s g r i f f (20), Raudseps (21) and F r i t s z c h e (19). There-fore, from the point of view of innovations i n the f i e l d of pattern "recognition" by machine, the contribution of the present work l i e s not as much i n the novelty of the transduction-feature detection scheme studied, as i n the methodology of i t s a p p l i c a t i o n . 1.2 Reasons f o r the Use of Curvature I f curvature i s time consuming to measure and has inherently poor noise c h a r a c t e r i s t i c s , then i t s use i n the preprocessing of two-dimensional data requires some j u s t i f i c a t i o n . The greatest support f o r 4 the use of curvature as a shape descriptor i s found i n the r e s u l t s of research i n the areas of physiology and psychology. Recent micro-elec-trode studies of the neural networks i n the v i s u a l systems of l i v i n g organisms, i n c l u d i n g primates, have shown that the structures present are such as to accentuate i n t e n s i t y and colour boundaries i n images f a l l i n g on the retinas and to some extent, r e f l e c t the degree of curva-ture of those boundaries (39-49). Such studies have motivated the design of some preprocessing techniques (27, 50-52) for p i c t o r i a l data study and a method of measuring curvature, presented i n t h i s t h e s i s , was derived from models of receptive f i e l d organization proposed by physi-o l o g i c a l i n v e s t i g a t o r s (41-44). From the f i e l d of psychology, the work of Attneave i n l o c a t i n g the information content of shape i s s i g n i f i c a n t (36-38). By applying a vari a n t of the "guessing game" technique with which Shannon (53) studied the redundancy i n p r i n t e d E n g l i s h , Attneave showed that the information content of scenes i s concentrated at points of contrast ( e i t h e r between i n t e n s i t i e s or colours), i . e . , boundaries, and furthermore, at points on those boundaries where d i r e c t i o n i s changing most r a p i d l y , i . e . , points of high curvature. Attneave performed two a d d i t i o n a l experiments relevant to the p r i n c i p l e that information i n shape i s concentrated at points where a contour changes d i r e c t i o n most r a p i d l y . In the f i r s t experiment, t e s t subjects were i n s t r u c t e d to draw, for each of se v e r a l test shapes, a pattern of 10 dots which would resemble the shape as c l o s e l y as p o s s i b l e and then to i n d i c a t e on the o r i g i n a l o u t l i n e , the exact places which the dots represented. A good example of the r e s u l t s i s shown i n F i g . 1.2.1. In F i g . 1.2.1, the r a d i a l bars i n d i c a t e the r e l a t i v e frequency with which dots were placed on each of the segments i n t o which the contour F i g . 1.2.1 Relative frequency of point placement f o r the preservation of shape (Attneave (36)), was divided for scoring purposes. On t h i s sample f i g u r e and others, the re s u l t s c l e a r l y indicated that subjects show a great deal of agreement i n t h e i r abstractions of points best representing shape and most of these points are taken from the regions where the contour i s most d i f f e r e n t from a s t r a i g h t l i n e . The second experiment performed by Attneave (36) demonstrates how common objects may be represented with good f i d e l i t y by copying the points at which t h e i r contours change d i r e c t i o n maximally, and then connecting these points appropriately with s t r a i g h t l i n e s . F i g . 1.2.2 i s an example of the a p p l i c a t i o n of t h i s technique to a r e a l sleeping cat. Attneave's experiments demonstrate that the c r i t i c a l features for the recognition of a shape are the points of maximum contour curvature, t h e i r r e l a t i v e l o c a t i o n and t h e i r c o n n e c t i v i t y . The curvature function i t s e l f has properties which render i t F i g . 1.2.2 The points of maximum curvature on a sleeping cat (Attneave (36)). a t t r a c t i v e for use i n the preprocessing stages of pattern recognition systems. Being a one-dimensional function, i t represents an immediate data reduction from the o r i g i n a l two-dimensional representation but s t i l l r etains s u f f i c i e n t information f o r the reconstruction of the boundary of the o r i g i n a l f i g u r e . The curvature function i s unchanged under trans-l a t i o n and, except for a phase s h i f t , r o t a t i o n of the o r i g i n a l f i g u r e . In other words, curvature i s defined i n terms of quantities which are i n t r i n s i c to the curve i t s e l f . V a r i a t i o n s i n s i z e of the o r i g i n a l f i g u r e r e s u l t i n v a r i a t i o n s i n length of the curvature function and can be re-moved by appropriate normalization. The f a c t that the o r i g i n a l shape 7 can be reconstructed from the curvature function i s u s e f u l i n evaluating the e f f e c t s of processing techniques on the curvature function. 2. THE THEORY OF CURVATURE * 2.1 Classical Theory of Curves in the Plane Fig. 2.1.1 A closed curve i n the plane described in parametric form by the vector R(s). The boundaries of two-dimensional binary patterns describe closed curves in the plane, (Fig. 2.1.1). One can represent such a curve in parametric form as a vector: R(s) = i x ( s ) + l y ( s ) , (2.1.1) where the parameter s represents arc length or the distance along the curve from an arbitrary starting point s , i and j represent unit vectors o * / ,s Reference (54) . 9 i n the two a x i a l d i r e c t i o n s x and y r e s p e c t i v e l y , and x(s) and y(s) represent the values of the x and y coordinates of points on the curve as functions of s. D i f f e r e n t i a t i o n of R(s) with respect to s y i e l d s the tangent vector: "T(s) = " i x(s) + " j f y ( s ) , (2.1.2) where x(s) and y(s) represent derivatives with respect to s of x(s) and y(s) r e s p e c t i v e l y . The tangent angle <j>(s), also a function of s, i s de-fi n e d as: <Ks) = t a n _ 1 %Q . (2.1.3) x(s) Curvature, a s c a l a r , i s defined i n terms of the functions x(s) and y(s) and t h e i r derivatives with respect to s as: K( S) = *(s ) y ( s ) - y ( s ) x(s) ( 2 m l A ) ( x ( s r + y ( s n 3 / 2 or equivalently (54), i n terms of <j>(s) as: K(s) = <J>(s), (2.1.5) where again, the dot represents the " d e r i v a t i v e with respect to s". The reconstruction of the o r i g i n a l boundary from 4>(s) i s achieved by f i r s t i n t e g r a t i n g ^(s) with respect to s to obtain <j>(s): <j>(s) - /*(s)ds + 6. (2.1.6) The i n t e g r a t i o n constant 6 defines an i n i t i a l value f or the tangential angle cf>(s) and hence determines the r o t a t i o n of the curve with, respect to the coordinate axes x and y. Its loss i n the d i f f e r e n t i a t i o n of <j>(s) gives the curvature function i t s r o t a t i o n independence. The tangent vector i s obtained by s u b s t i t u t i n g equation 2.1.6 i n the r e l a t i o n s : x(s) = cos(4>(s)) (2.1.7a) y(s) = sin(<j>(s)) (2.1.7b) and i n turn s u b s t i t u t i n g equations 2.1.7 (a and b) in t o equation 2.1.2. 10 This y i e l d s the equation: "T(s) =~i cos[/4>(s)ds + 6] + j " s i n [ / i ( s ) d s + 6]. (2.1.8) Integration of T(s) with respect to s y i e l d s the vector: R(s) = i / cos [/^(s)ds + <5]ds + ~1 C + T / s i n L/4>(s)ds + 5]ds + ^ C 2. (2.1.9) The constants i and j define the t r a n s l a t i o n of the curve R(s) with respect to the x a n d y axes. Their loss i n the d i f f e r e n t i o n of R(s) gives the curvature function i t s t r a n s l a t i o n a l independence of the x and y axes. The fact that the curves of i n t e r e s t are closed implies that the curvature function i s p e r i o d i c (period = T arc length units) and the following conditions must hold: s +T / ° cl(s)ds = 2-rr, (2.1.10) o s +T / 0 cos[/<j>(s)ds + 6]ds = 0, (2.1.11a) o s +T / ° sin[J>(s)ds + 6]ds = 0. (2.1.11b) o These imply that the average value of the curvature function i s -^r over one period and the net change over an integer multiple of periods i n x(s) and y(s) i s zero. 2.2 Curvature i n the Frequency Domain Further i n s i g h t into the nature of the curvature e x t r a c t i o n process can be gained i f the reverse operation, i . e . , the geometric reconstruction of a shape from a curvature function, i s analyzed i n the frequency domain. 11 Consider the class of curvature functions of i n t e r e s t to be p e r i o d i c with period T arc length u n i t s . As was pointed out i n Sec. 2.1, t h i s i s the case for a l l closed curves i n the plane, but i s not r e s t r i c t e d to them. Assuming the period T to be constant, we can expand a p e r i o d i c curvature function i n a Fourier s e r i e s as follows. oo K(s) = E A cos(^r- s+e ) • n T n n=o 00 = A D + I A c o s ( ^ + 9 ), (2.2.1) o i n T n n=l where D = cos(9 ). Integration of K(s) y i e l d s the tangent angle <f>(s) : o. °° A T <f>(s) = A Ds + E ^ ~ s i n ( ^ ^ - + 6 ) + 6. (2.2.2) o . /TO 1 n n=l The constant <5 corresponds to the r o t a t i o n constant of equation 2.1.6. The tangent vector i s reconstructed from the tangent angle by s u b s t i t u t i n g equation 2.2.2 in t o equations 2.1.7 and 2.1.2. The r e s u l t i s : 0 0 A T T(s) = i cos [A Ds + E -z 3- s i n C ^ j r ^ + 6 ) + 6] o , zTrn x n n=l » A T + T s i n [ A Ds + Z - s 5 - s i n ( - ~ ^ + Q ) + 6]. (2.2.3) o . 27m T n n=l Applying the f i r s t of the closure conditions of equation 2.1.10 reveals that: A D = —-. . (2.2.4) o I The construction of the tangent vector from the curvature function i s mathematically analogous to the frequency modulation of a two-dimensional vector " c a r r i e r " with the curvature information. One can therefore regard a two-dimensional shape as a medium f o r the conveyance of curvature information just as a frequency modulated carrier i s a medium for the conveyance of a message. Alternative expansions for each of the compon-ents of equation 2.2 .3 have been developed for the analysis of frequency modulation systems ( 5 5 ) and can be readily applied to equation 2.2 .3 to yield, for the tangent vector: A T f(s) = t I { I L L (-z~~) }cos(~r- + I L ( ^ s + e )+6) T n L ZTrn i ti n i n L =-» n n + T Z'{IIJT ( ^ ) } s ' i n ( - ^ + I L ( ^ - + 9 ) + 6 ) . (2.2 . 4 ) T n L Zun T n n T n L =-oo n n In this expression, A T A T L » / i \ m A T 2m J T (•—) = (-T-) N • I F - T P / t i L i s • ( 7 ^ ) 1 (2.2 . 5 ) L 2Trn 4 mi n L m ! r ( L +m+l) 4 7 m n m=0 n i.e., the Bessel's function of the f i r s t kind, order L . n The vector R(s) is obtained by integrating equation 2.2 .5 as previously illustrated. The following examples serve to i l l u s t r a t e some of the important features of the frequency domain analysis of curvature. Consider the case when the curvature function is a constant. That i s , K(s) = (2.2.6) Equation 2 . 2 . 4 , under these circumstances reduces to: T(s) = t cos(-^- + 6) + " J s i n ( - ^ - + 6) (2.2.7) and the reconstructed boundary curve becomes: R(s) = 1-^ s i n ( ^ - + 6) - j" ^ cos(^p- + 6 ) . (2.2.8) A striking analogy appears here. Just as a pure sinusoidal wave is used as a device for the transmission of a message by the modulation of the frequency of that wave, so the cir c l e in the plane is used as a device for the transmission of curvature information, again by the modulation of the frequency of i t s two s i n u s o i d a l components. Alone, n e i t h e r the c i r c l e , nor the pure s i n u s o i d a l wave convey useful information. A second example which serves to i l l u s t r a t e a d d i t i o n a l features of the nature of curvature i s the case where only one harmonic i s present i n addition to the c a r r i e r . Under these circumstances, equation 2.2.4 reduces to: A T , f ( s ) = i E J T ( ^ 2 _ ) c o s ( ^ - + L. + L e + 6 ) T Ln /im 1 1 1 i n L^=-°° 1 + V V ^ ' ^ + h ^ + V n + a- (2.Z.9, L^=-<» 1 Expanding each of the two components of equation 2.2.9 y i e l d s : A T f ( s ) = i J <-IL_)cos(^.+ 6) U /nn 1 A T , + i j ( _ S _ ) { C o s [ ( l + n ) ^ . + Q + 6 ] } l Zim 1 n A T . + i J . ( ^ - ) { c o s [ ( l + 2 n ) ~ . + 26 + 6] - cos [ (l-2n)^j£ - 2 0 + 6 ] } z 2Tm i n i n ^ A T 9 9 o + i J ( _ 2 _ ) { c o s [ ( l + p n ) ^ - + P 6 n + &) - c o s t ( l - p n ) - ^ - - Pe + 6]} p zim i n i n A T + J J , ( ^ - ) { s i n [ ( l + n ' ) ^ +6 + 6] - s i n [ ( l - n ) ^ . - 0^ + 5]} ± zTrn 1 n 1 n + j* J 2 ( ^ ) { s i n [ ( l + 2 n ) ^ - + 20 n + 6] - s i n [ ( l - 2 n ) ^ - _ 2 0 n + 6]} + j J p ( ^ ) { s i n [ ( l + p n ) ^ - + p0 n + 6] - s i n [ ( l - p n ) ^ p - - P 0 n + 5]} ! (2.2.10) From equation 2.2.10, i t can be seen that a s i n g l e harmonic i n the curvature function generates an i n f i n i t e number of harmonics i n ^ ^ A T the vector T(s) and hence i n R(s) . In p r a c t i c e , J (~—) diminishes A T p 2im r a p i d l y f or p > and the number of s i g n i f i c a n t harmonics i s hence f i n i t e and decreases with i n c r e a s i n g harmonic number. In the s p e c i a l case when n = 1, i . e . , only the f i r s t harmonic i s present i n the curvature function, a n o n - o s c i l l a t o r y term emerges i n each component of T(s) of the form: _^ A T - i J_ (—-) cos(-e.+6) 1 Z7T 1 ^ A T - j J-LCJT") s i n ( - 0 ^ 6 ) . (2.2.11) On i n t e g r a t i o n to obtain the vector R(s) and hence the corres-ponding curve i n the plane, the n o n - o s c i l l a t o r y components of T(s) are e f f e c t i v e l y m u l t i p l i e d by " s " and a ramp function appears i n each com-ponent of R(s). In the absence of t h i s ramp component, the conditions for closure (eqs. 2.1.10, 2.1.11) are s a t i s f i e d and R(s) describes a closed curve i n the plane. However, i f a ramp or "s" term i s present, then the closure conditions cannot be s a t i s f i e d and the corresponding curve i n the plane w i l l not close. I f only 1 harmonic i s present i n the curvature function (eq. 2.2.10), then a n o n - o s c i l l a t o r y term can be gen-erated only i f that s i n g l e harmonic i s the f i r s t . Therefore, the curves i n the plane corresponding to i n d i v i d u a l harmonics i n the curvature func-t i o n are closed for a l l harmonics but the f i r s t . F i g . 2.2.1 shows a few of the two-dimensional curves i n the plane corresponding to i n d i v i d u a l harmonics of curvature. When two harmonics are present, equation 2.2.4 reduces to: & 9 The two-dimensional curves i n the plane corresponding to i n d i v i d u a l Fourier har-monics i n the curvature domain. Harmonic numbers are indicated i n a l l cases. F i g . 2.2.2 Examples of the closure technique applied to two curves i n the plane. A T _^ _^ 0 0 °° A T n„ „ L-2Tfn-S L 927rn 9s T(s) = i Z E J T ( ~ - ) J V ( ~ - ) c o s { ^ g - + ~ + % +L.8 • +L 9 L i =-oo L ^ - O O 4 2 ™ 1 L 2 2 T O 2 T T T 1 " l 2 ' A T A T _^ 0 0 » n.. n„ „ L, 2-rrn7s L ?2Tm 9s L^=_<» L L J L 2Tm 1 L 2 2 r a 2 T T T 1 2 n (2.2.12) This r e s u l t shows that the spectrum i s now much more complicated than f o r a s i n g l e harmonic and that i n the T(s) and R(s) domains, f r e -2ir quencies are produced at spacings from the " c a r r i e r " (-—) given by a l l L l n l L 2 n 2 possible combinations 4- — r — - — • Some i n s i g h t i n t o the differ e n c e between open and closed p e r i o d i c curves i n the plane can be gained from equation 2 .2 .12 . A non—zero contribution to the n o n - o s c i l l a t o r y term i n the tangent vector w i l l be made for each combination of + L^n^ + L 2 n 2 such that: 1 + L±n1 + L 2 n 2 = 0 (2.2.13) I f the algebraic sum of a l l such contributions i s zero, then the corresponding curve i n the plane w i l l be closed. I f p harmonics are present i n the curvature function, then a contribution to the n o n - o s c i l -l a t o r y term i n the tangent vector w i l l be made for each combination of 4- L.n, + L„n„ 4- ... 4- L n such that : 1 1 - 2 2 - - .p p 1 4- L.n. 4- L„n- 4- ... 4- L n =0. (2.2.14) - 1 1 - 2 2 - - p p I f the algeb r a i c sum of a l l such combinations i s zero, then the corresponding curve i n the plane i s closed. Note that i f only even harmonics are present i n the curvature function, the corresponding curve i n the plane n e c e s s a r i l y closes. Another point of i n t e r e s t p e r t a i n i n g to the closure of curves i n the plane i s the following. I f a curvature function which defines a closed curve i n the plane i s passed through any kind of system ( l i n e a r or non-linear) which removes some of the frequency components i n the function, then the so a l t e r e d curvature function no longer n e c e s s a r i l y describes a closed curve i n the plane on geometric reconstruction. Examples of t h i s phenomenon occur throughout the t h e s i s . Under c e r t a i n circumstances, i t may be desirable to close a reconstructed boundary which on reconstruction does not normally close. This i s accomplished by determining the magnitude of the " s " or "ramp" term i n each of the boundary functions x(s) and y ( s ) . This can be e a s i l y done by measuring the displacement between the i n i t i a l and f i n a l values of these functions over one period. Denoting these displacement values by V and V r e s p e c t i v e l y , then the two ramp functions are simply V v.s X i X and V^.s and the boundary can be closed by subtracting these ramp func-tions from the x(s) and y(s) functions r e s p e c t i v e l y . F i g . 2.2.2 shows a few examples of the a p p l i c a t i o n of th i s technique to sample functions. A frequency domain analysis of the process of e x t r a c t i n g a curvature function from a given boundary i s considerably less t r a c t a b l e than the reverse procedure j u s t described. However, i n the l i g h t of the previous discussion, some general comments can be made concerning t h i s process. The f i r s t step i n the e x t r a c t i o n of the curvature function from the boundary functions x(s) and y(s) involves the d i f f e r e n t i a t i o n of these functions, the e f f e c t being to amplify the higher frequency components of each function. The second step involves the non-linear process of e x t r a c t i n g the tangent angle as a function of arc length (see equation 2.1.3). The e f f e c t of th i s process i s to d i s t r i b u t e the a m p l i f i c a t i o n e f f e c t of the f i r s t step over the e n t i r e frequency range of the tangent angle function. As w i l l be seen i n l a t e r s e c t i o n s , t h i s phenomenon has the undesirable e f f e c t of amplifying high frequency quantization noise on the x ( s ) ; y(s) functions and then d i s t r i b u t i n g t h i s noise approximately uniformly over the e n t i r e frequency range of the tan-gent angle function. The f i n a l step i n the curvature e x t r a c t i o n process i s the d i f f e r e n t i a t i o n of the tangent angle function to y i e l d the curva-ture function (equation 2.1.5). The e f f e c t once again i s to amplify the high frequency components of these functions. I t i s the i n i t i a l a m p l i f i c a t i o n and subsequent d i s t r i b u t i o n of the quantization noise which gives curvature i t s poor noise c h a r a c t e r i s t i c s . A f i n a l point concerning the r e l a t i o n s h i p between the tangent angle function and the curvature function w i l l be found u s e f u l i n l a t e r sections of this t h e s i s . The amplitude of the tangent angle function does not change for the same figure at d i f f e r e n t s i z e s . That i s , normalization of the length of the tangent angle function, which corresponds to a crude nor-malization of the s i z e of the two-dimensional shape, does not a f f e c t the amplitude of the tangent angle function. Therefore a tangent angle function can be expressed as a function of s and T as: -- CO 4><s,T) = ~ + Z * c o s ( - ^ - + 6 ), (2.2.15) 1 n=l n i n where the "B " are not functions of the period T, but are constant for n ^ ' a given shape^ for a l l T. Curvature, as a function of s and T, i s ob-tained by taking the d e r i v a t i v e of 2.2.15 with respect to s to y i e l d : oo K ( s , T ) = 4 f + I B n 4 - ^ ) . s i n ( ^ . + 6 ) . (2.2.16) I . n l i n n=l • 2 The c o e f f i c i e n t s of the curvature function [B •( —).] are functions of n J. the period T and hence the normalization of the curvature function to a new length, corresponding to a change i n the s i z e of the two-dimensional 19 shape,results i n a change i n the amplitude of the curvature function as w e l l as the lengthy the shorter the period, ( i . e . , the smaller the two-dimensional shape) the larger the amplitude of the curvature function. An i l l u s t r a t i v e example of t h i s phenomenon i s afforded by a c i r c l e i n the plane, the curvature of which i s equal to the r e c i p r o c a l of the radius. In terms of the theory described by equations 2.2.1 through 2.2.12, the c o e f f i c i e n t s "A n" are i n r e a l i t y functions of the period T i n that a change i n T r e s u l t s i n an inverse change i n the A^. The theory of curvature and tangent angle functions i s a t t r a c -t i v e i n that i t appears to o f f e r many advantages as a descriptor of shape for pattern recognition and information processing a p p l i c a t i o n s . However, most of the work done i n these two f i e l d s of endeavour, p a r t i -c u l a r l y i n pattern recognition, involves the use of d i g i t a l computers and the patterns or shapes being studied must be d i g i t i z e d or quantized onto d i s c r e t e point arrays before further processing can take place. Hence the curvature and tangent angle measurements are most often performed on d i g i t i z e d or quantized versions of the o r i g i n a l patterns or shapes. As a r e s u l t , "quantization noise" i s introduced onto the pattern boundaries and, as previously shown, th i s quantization noise i s amplified and d i s t r i b u t e d over the e n t i r e frequency spectrum by the process of boundary curvature or tangent angle e x t r a c t i o n . The remainder of t h i s thesis i s concerned with the problem of measuring boundary curvature and tangent angle i n t h i s d i g i t i z e d or quantized environment. A f i n a l comment i s i n order. The theory presented i n Sees. 2.1 and 2.2 i s f o r the continuous or analog case. However, throughout the t h e s i s , d i s c r e t e approximations to curvature and r e l a t e d functions are the object of study. Therefore, the functions and operations referred to throughout the thesis r e l a t i n g to curvature are i n r e a l i t y d i s c r e t e approximations to those of Sees. 2.1 and 2.2. Some of the more important d i s c r e t e approximations can be described as follows. A di s c r e t e two-dimensional boundary i s represented over one period as: t(Si) = T x ( S i ) + t y ( s . ) , i = 1, T, (2.2.17) where T i s the function period i n units of the sampling i n t e r v a l . Also, x(s,,) - x ( s i ) - x ( s i _ 1 ) y ( s . ) = y(s.) - y C s . ^ ) i - l , T. (2.2.18) The d i s c r e t e form of the tangent angle function i s computed as: -1 * ( s i > d>(s.) = tan (--T-k), i = 1, T, (2.2.19) T I x(s.) ' ' and the curvature function i s given by: K(s i ) = <f1(si) - 4>(s i_ 1), i = 1, T. (2.2.20) Geometric reconstruction of the o r i g i n a l curves i n the plane i s conducted according to: 3 <J>(s.) = 2 K(s.) + 6 (2.2.21) 2 i = l 1 1 * j S T where 6 represents a r o t a t i o n constant, and f i n a l l y , x(s^) = cos[cj>(s..)] (2.2.22a) y(s. ,) = s i n C M s ^ ) ] (2.2.22b) L x ( s T ) = Z c o s H ( s . ) ] + C l (2.2.23a) j = l J 1 -L y ( s T ) = Z cos[<Ks.)]+c«, (2.2.23b) j-1 J 2 R(s L) = i x ( s L ) + t y ( s L ) . (2.2.24) The constants c^ and ave the t r a n s l a t i o n constants of Sec. 2.1. 2.3 Organization of Approach When measuring the curvature of the boundary of a quantized shape, the objective i s to obtain a one-dimensional d i g i t a l sequence of points representing boundary curvature as a function of arc length ( d i s -tance along the quantized boundary) which resembles, as c l o s e l y as p o s s i b l e , the sampled curvature function of the boundary of the o r i g i n a l shape from which the quantized version was derived. Due to the presence of the quantization noise on the measured function, a discrepancy or " e r r o r " e x i s t s between the measured curvature function and the o r i g i n a l . The magnitude of this error depends upon two factors i n the measurement pro-cess:- the algorithm by which successive boundary points of the quantized shape are selected, r e f e r r e d to as the "contour t r a c i n g algorithm", and the method whereby excessive quantization noise i s attenuated, referred to as "smoothing" or " f i l t e r i n g " . In Chapter three of t h i s t h e s i s , s i x d i f f e r e n t contour t r a c i n g algorithms are used to extract curvature functions i n the absence of smoothing of any kind. The r e s u l t i n g "unsmoothed" or " u n f i l t e r e d " cur-vature functions, r e f e r r e d to as "basic" curvature functions are studied from the point of view of modelling the quantization noise c h a r a c t e r i s t i c s of each-. Four of the contour t r a c i n g algorithms and corresponding basic curvature functions are defined on a square quantizing point array and two on an hexagonal quantizing point array. Then, i n Chapters four and five, three approaches to the problem of attenuating the quantization noise on the b a s i c curvature functions are studied and compared. For each approach, the same contour t r a c i n g algorithm i s used to ensure an unbiased comparison of the three methods. Although the quantization noise cannot be completely removed from curvature functions measured on quantized shapes, the r e s u l t s of the thesis do contribute to the understanding of the quantization noise c h a r a c t e r i s t i c s , of how changes i n array r e s o l u t i o n and contour t r a c i n g algorithm both a f f e c t the quantization noise c h a r a c t e r i s t i c s and of the degree to which the d i f f e r e n t approaches to smoothing of the curvature functions are e f f e c t i v e i n e l i m i n a t i n g the quantization noise. 2.A General Comments on Procedure The procedure involved i n the study of both the contour t r a c i n g algorithms and the smoothing techniques i s b a s i c a l l y the same. A set of o r i g i n a l or known curvature functions are obtained through synthesis and/ or measurement on sketched shapes (the d e t a i l s of t h i s procedure are provided i n Sec. 3.3). The two-dimensional boundaries corresponding to these known curvature functions are geometrically reconstructed according to the equations of Sec. 2.2. These reconstructed boundaries are then placed over a discre t e array of points and a l l of the array points l y i n g on or within the reconstructed boundary are assigned a value "1" and a l l others a value "0". The boundary curvature functions of the t e s t shapes and the quantized shapes are then compared. In s e l e c t i n g the form of the o r i g i n a l t e s t shapes f o r each of the studies, consideration was given to the degree of dependence of the re s u l t s on the complexity of the shapes used. Since smoothing, as an operation, i s l a r g e l y independent of the curvature function being smoothed, a wide v a r i e t y of t e s t shapes i n terms of boundary complexity were used i n the smoothing study. The object i n using a wide v a r i a t i o n i n shape was to convey a sense of how a given amount of smoothing a f f e c t s the amount of shape d e t a i l representable. In the case of the contour t r a c i n g algorithm study however, the quantization noise c h a r a c t e r i s t i c s are c o r r e l a t e d with the shape being quantized. It was decided therefore, to study the quantization noise c h a r a c t e r i s t i c s on a somewhat r e s t r i c t e d , but widely used, set of t e s t shapes:- hand p r i n t e d a l p h a b e t i c a l characters and numerals. Alphab e t i c a l characters ate probably the most commonly used set of t e s t shapes i n pattern recognition work i n recent years and t h e i r use therefore affords a broad a p p l i c a b i l i t y of the r e s u l t s . The methods employed i n the t h e s i s , however, are not r e s t r i c t e d i n t h e i r a p p l i c a t i o n and could, i n the future, be applied to any set of shapes. Further d e t a i l s on the test shapes are provided i n sections to follow. In the next chapter, s i x contour t r a c i n g algorithms and t h e i r corresponding b a s i c curvature functions are defined. Experiments on sample shapes are then performed to i l l u s t r a t e the behaviour of the quantization noise for each of the s i x algorithms. On the basis of the r e s u l t s , a model for the quantization noise on curvature functions i n the absence of smoothing i s proposed. 3. CONTOUR TRACING ALGORITHMS AND QUANTIZATION NOISE 3.1 Basic Curvature Functions In the absence of smoothing or f i l t e r i n g of any kind, a d i s c r e t e curvature function can be defined for the boundary of a given quantized shape i n d i f f e r e n t ways, depending upon how successive boundary points are defined and how distances between those points are recorded. A cur-vature function obtained from a quantized shape i n the absence of smoothing i s r e f e r r e d to as a " b a s i c " curvature function and a set of rules by which boundary points are selected and recorded i s referred to as a "contour t r a c i n g algorithm". In t h i s chapter, s i x of the more common contour t r a c i n g algorithms and t h e i r corresponding b a s i c curvature functions are studied, four defined on a square point array and two on an hexagonal point array. The s i x contour t r a c i n g algorithms and t h e i r corresponding b a s i c curva-ture functions can be described with reference to F i g . 3.1.1. The f i r s t contour t r a c i n g algorithm, i l l u s t r a t e d i n F i g . 3.1.1 (1-A,B,C), defines a boundary point as l y i n g at the centroid of any four of the array points forming a "minimum square". In F i g . 3.1.1 (1A), the small black dots designate four of the array points i n the minimum square configuration. The c i r c l e at the centroid of the minimum square would be designated as a boundary point whenever 1, 2 or 3 of the four points of the minimum square have been designated a "1" by the quantiza-tion procedure of Sec. 2.4.. I f a l l or none of the four points are de-signated "1", then the centroid p o i n t i s not a boundary point. The arrows i n F i g . 3.1.1 (1A) i n d i c a t e the four possible d i r e c t i o n s i n which the next boundary point (centroid) i s sought. The four d i r e c t i o n s are interrogated i n counterclockwise order f o r a counterclockwise contour trace, the f i r s t d i r e c t i o n interrogated depending upon which of the minimum square points (A) 3 o I (B) fC) ? 2) 2o«-«-o< o 4 5 6 3) 3o*^fo7 2 1 8 4 5 6 o o o 2 / 0 5 4 °\ /° 1 6 F i g . 3.1.1 o<-o CK-O o+-o o o o .? ?. 04-0 o o*-o fL-o .O—O—0-»0 o • L. r. : i . . i » i t •-« »• «> .« i L s- • • i + • * • • • • • n T" o-n - 4 -4--S-n. *f-o--9-: i r i i ' ..i i ir II II Hll II IIIU..III.JI The s i x contour t r a c i n g algorithms and the corresponding b a s i c curvature f u n c t i o n s . Column A shows the d i r e c t i o n s of search f o r successive boundary p o i n t s i n each case. Column B shows the boundary points found by each a l g o r i t h m on a simple shape v j l u c k dots) and column C shows the corres b a s i c curvature f u n c t i o n s . i s (or are) "1". In F i g . 3.1.1 (IB), a sample shape i s shown a f t e r quantization on a square array, the " l " s being i n d i c a t e d as black dots, the "0"s being omitted (see quantization procedure of Sec. 2.A). The c i r c l e s are located at the successive boundary points defined by this algorithm (algorithm 1) and the sequence i n which they are found i s i n -dicated by arrows, s t a r t i n g at the point marked (+). The b a s i c curvature function corresponding to algorithm 1 for the simple shape of F i g . 3.1.1 (IB), i s shown i n F i g . 3.1.1 (1C) and * consists s o l e l y of impulses of area +TT/2 or 0, spaced equally apart. Using algorithm 1, a basic curvature function of t h i s form can be defined fo r any quantized shape and a moments consideration reveals that t h i s function i s consistent with the theory of curvature of Chapter two i n both the method whereby i t i s obtained from the quantized boundary and the method whereby the same quantized boundary can be reconstructed from i t . A second contour tr a c i n g algorithm (algorithm 2 ) , also defined on a square array, and s i m i l a r to the f i r s t , i s shown i n F i g . 3.1.1 (2). A boundary point i s defined to be coincident with an input array point and successive boundary points are again sought i n the four p o s s i b l e d i r e c t i o n s shown i n F i g . 3.1.1 (2A). F i g . 3.1.1 (2B) shows the successive boundary points (enlarged black dots) found by t h i s algorithm i n t r a c i n g the con-tour of a simple quantized shape and (2c) shows the r e s u l t i n g b a s i c curva-ture function obtained, again s t a r t i n g at the point marked "+". Four values of the impulse areas i n the curvature function are p o s s i b l e with algorithm 2; TT, + T T / 2 and 0 radians per unit of arc length. In Chapter f i v e of the t h e s i s , i t i s shown that a corner i n the boundary of a shape corresponds to an impulse i n the curvature function of the boundary and the area associated with the impulse i s equal to the angle change i n rounding the corner. Hence the weights of + ir/2 or 0 associated with F i g . 3.1.1 (IB and 1C). Algorithms 3 and 4 ( F i g . 3.1.1 (3 and 4)) are also defined for a square array and define boundary point locations coincident with input array points. In both algorithms, successive boundary points are found by moving i n one of eight possible d i r e c t i o n s as shown i n F i g . 3.1.1 (3A and 4A) from the current boundary point. The points detected i n t r a c i n g the boundary of a quantized f i g u r e are i d e n t i c a l as i s shown i n (3B) and (4B) (enlarged black dots) and the r e s u l t i n g b a s i c curvature function impulse areas both assume s i x possible values; — , + IT/2, +TT/4 and 0 radians per unit of arc length on any quantized f i g u r e . The difference between algorithms 3 and 4 l i e s i n the way distances between successive boundary points are recorded. I f i t i s assumed that the spacing between input array points along the array a x i a l d i r e c t i o n s i s one unit, then algorithm 3 assigns a value of one unit to the distance between successive points i n a l l cases. Hence algorithm 3 introduces d i s t o r t i o n i n the boundary length whenever adjacent boundary points are s i t u a t e d along a l i n e at 45 degrees to the array a x i a l d i r e c t i o n s since the separation i n t h i s case i s a c t u a l l y )/2 u n i t s . In algorithm 4, the a c t u a l distance i s recorded i n each case, being 1 f o r points along the a x i a l d i r e c t i o n s and -/l f o r points spaced along the 45 degree d i r e c t i o n s . Hence the curvature function r e s u l t i n g from the use of algorithm 4 i s longer than that r e s u l t i n g from the use of algorithm 3 i n most cases. Algorithm 4, while more accurate than 3, i s much more cumbersome to use with a d i g i t a l computer since i t requires extra storage to record the distance values associated with each point and the r e s u l t i n g b a s i c curvature function i s much more d i f f i c u l t to manipulate i n further processing. Algorithm 3, while l e s s accurate, i s much more e a s i l y stored and manipulated. Algorithm 4 i s used by the U n i v e r s i t y of Ohio group, B r i l l et a l . (19-23). 28 Algorithm 5, ( F i g . 3.1.1 (5)), i s defined for an hexagonal quantizing point array and, as with algorithms 2 through 4, defines boundary points c o i n c i d e n t a l with the input array points. In (5A), the s i x d i r e c t i o n s i n which the next boundary point i s sought from any given boundary point are shown and i n (5B), the successive boundary points detected by t h i s algorithm on a sample quantized f i g u r e are shown, again as enlarged black dots. The r e s u l t i n g b a s ic curvature function (5C) assumes values ir, + 2ir/3, +TT/3 and 0 for the sample figure and a moments consideration r e v e a l s that these are the only p o s s i b l e values obtainable with t h i s algorithm. Algorithm 6 i s the hexagonal equivalent of algorithm 1. A boundary point i s defined at the centroid of three input array points and an adjacent boundary point i s sought by moving i n one of three d i r e c t i o n s from any given point as shown i n F i g . 3.1.1 (6B) . The boundary points defined by t h i s algorithm on the quantized sample shape are shown i n (6B) as small c i r c l e s and the r e s u l t i n g b a s i c curvature function i n (6C). The number of l e v e l s assumed by the curvature functions obtained using algorithm 6 cannot exceed two, i . e . , +TV/3 radians per unit of arc length. This b a s i c curvature function i s of i n t e r e s t since i t s amplitude l e v e l s can be represented by a s i n g l e " b i t " . The advantage of t h i s f a c t i s that i f further processing i s to be performed on the b a s i c curvature function, the complexity of that processing would, i n many cases, be considerably reduced by the presence of a binary valued function. A l l of the algorithms can be implemented on a d i g i t a l computer using a sequential boundary trace to extract the b a s i c curvature function. However, i n c e r t a i n a p p l i c a t i o n s , i t i s desirable to implement the processes of boundary point i s o l a t i o n or detection and curvature measurement using a parallel or two-dimensional scheme. A detailed discussion of two-dimensional arrays for the extraction of boundary curvature is l e f t u n t i l Chapter five. However, i t is shown in Chapter five, that algorithms one and six lead to particularly simple logic in the construction of two-dimensional arrays for the isolation and extraction of boundary curvature. This is the primary reason for their inclusion in this study. The remainder of this Chapter is concerned with a study and comparison of the quantization noise characteristics of the six basic curvature functions. In Sec. 3.2, the quantization noise i s defined. In Sec. 3.3, the experimental procedure for the study of the quantization noise is discussed and the experimental results are presented and in Sec. 3.4, an empirical model for the quantization noise is proposed. 3.2 Quantization Noise Definitions The quantization noise power 1 i s arb i t r a r i l y defined in the following manner. If T represents a discrete curvature function period in units of the sampling distance (U.S.D.), ^ ( s ^ ) , i = 1, T represents the discrete version of an original curvature function (normalized to the period T and sampled) and K ^ ( s ^ + j ) , i = 1, T represents the basic curvature function obtained from the quantized version of the original shape corresponding to K q ( S ^ ) and shifted by a value j , then the quantization noise "power" is defined as: T N 2 = Min4 Z (K (s.) - K.(s ,)) 2}. (3.2.1) j i==l A X+l This i s , the quantization noise power is equal to the minimum mean square error between the two functions K (s.) and K.(s...), i = 1, T, n o l A l+j 30 computed over the period T . Since the average value of both functions i s the same (2TT/T) , these values cancel out i n the computation of the mean square er r o r and are therefore omitted from equation 3.2.1. An equivalent expression for equation 3.2.1 can be developed i n the frequency domain. Denoting: T 2Trns. A™ = 2 2 KJs.) cos ( — — ) on . - O i i i = l T 2Trns. B ™ = 2 £ K„<s.) s i n (—=-*•) on , _ o i T 1=1 T 27ms. AAn = 2 1 K A ( s i ) C 0 S ( ~ T J L ) (3.2.2) i = l T 27rns. BAN - 2 , Z 1 K A ( s i ) s i n ^ T"^' I=1 then i t can be shown that an expression proportional to the quantization noise power of equation 3.2.1 i s given by: T/2 N 2 = £ [(A -A. ) 2 + (B -B. ) 2 ] , (3:2.3) - on An on An n=l where i t has been assumed that the c o e f f i c i e n t s A ^ and B ^ were c a l c u l a t e d with the function K,(s..,) s h i f t e d to the p o s i t i o n of minimum erro r with A l+j respect to K- (s.^) . The constant of p r o p o r t i o n a l i t y i s equal to l/(2*T ) so that : N 2 = 1/(2'.T 2)-N 2 (3.2.4) I t was shown i n Sec. 2.2, that when the period (T) of a curvature function i s changed, representing a change i n the s i z e of the corresponding reconstructed shape boundaries, the amplitudes of the *Because the b a s i c curvature functions are impulsive functions, the s h i f t i n g of the two functions K 0(s£) and K^(si-fj) to minimize the quanti-zation noise power i s a n o n - t r i v i a l problem. The problem i s circumvented however i n the quantization procedure to be described i n Sec. 3.3. 31 frequency components are changed by an amount pro p o r t i o n a l to the inverse of the period change. I t i s convenient therefore, to represent a l l curvature functions and t h e i r frequency spectra scaled by the f a c t o r T. The c o e f f i c i e n t s of equation 3.2.2 represent the Fourier s e r i e s c o e f f i -cients scaled by t h i s f a c t o r and the curvature function corresponding to any a r b i t r a r y period ( T ) can be found by d i v i d i n g these c o e f f i c i e n t s by T, computing the inverse transform of the r e s u l t and adding the D.C. term 2TT/T. I t i s found p a r t i c u l a r l y i l l u m i n a t i n g to consider the quanti-zation noise on an i n d i v i d u a l harmonic b a s i s . The amplitude of the quantization noise on a given harmonic (N ) i s given by: N = >/(A -A. ) 2 + (B -B. ) 2 (3.2.5) n on An on An and the quantization noise power i s hence: 9 o F 2 N = 1/(2.T) £ N . i n n=l ^T, T even T - l , T odd (3.2.6) The quantization noise amplitude on the i n d i v i d u a l harmonics of the basic curvature functions 0$^) i s the object of study i n the quantization noise experiments to be described. I t i s found that the behaviour of can be simply modelled, enabling the p r e d i c t i o n of the v a r i a t i o n of the quantization noise c h a r a c t e r i s t i c s with both array r e s o l u t i o n and contour t r a c i n g algorithm. A t h e o r e t i c a l development of a model f o r the quantization noise on i n d i v i d u a l harmonics of the b a s i c curvature functions of F i g . 3.1.1 poses some d i f f i c u l t y since the quantization noise w i l l , i n general, be correlated with the " s i g n a l " or shape c h a r a c t e r i s t i c s and also since a rigorous mathematical d e s c r i p t i o n of the process of curvature e x t r a c t i o n i s i n i t s e l f an i n t r a c t a b l e problem. Therefore, an experimental approach, 32 to the study of the quantization noise on the s i x b a s i c curvature functions was undertaken. 3.3 Quantization Noise Experiments The quantization noise experiments were performed with two objectives i n mind. The f i r s t o b j e c t i v e , as described i n Sec. 3.1, was to compare the s i x contour t r a c i n g algorithms on the basis of the quanti-zation noise c h a r a c t e r i s t i c s of each. The second o b j e c t i v e , described i n the introduction,was to p r e d i c t the v a r i a t i o n i n quantization noise c h a r a c t e r i s t i c s with array configuration and r e s o l u t i o n . However, i n attempting to s a t i s f y these o b j e c t i v e s , three problems are immediately encountered. As previously noted, quantization noise i s , i n general, c o r r e l a t e d with the shapes being quantized. As a r e s u l t , the g e n e r a l ity of the r e s u l t s obtained using a given class of shapes i s l i m i t e d . Such r e s u l t s are applicable only to classes of shapes whose c h a r a c t e r i s t i c s are s i m i l a r to those of the shapes o r i g i n a l l y used. The set of shapes s e l e c t e d f o r t h i s study consisted of one hundred, hand-printed, a l p h a b e t i c a l characters and numerals. The choice of t e s t shapes was a r b i t r a r y except that alpha-b e t i c a l characters represent an average degree of shape complexity, are e a s i l y obtained and have been the subject of considerable i n t e r e s t i n pattern recognition x^ork i n recent years. The generality of the r e s u l t s obtained with- the data set i s discussed i n the conclusions of t h i s chapter. The second problem encountered i n the quantization noise e x p e r i -ments was the problem of obtaining accurate " o r i g i n a l " curvature functions without the introduction of excessive quantization noise i n the process. Although complete elimination of quantization noise i s V i r t u a l l y impossible, the noise l e v e l s were kept down through the use of the following procedure. Each te s t shape was i n i t i a l l y generated by hand, using a compu-te r i z e d i n t e r a c t i v e l i g h t pen and d i s p l a y . Each shape i n turn was sketched onto a square matrix of points, approximately 250 points to a sid e . Cur-vature functions were then extracted by machine, using algorithm 4 of F i g . 3.1.1. The average period of the curvature functions obtained i n t h i s manner was approximately 1000 u n i t s . On the quantized shapes, care was taken to avoid "ragged" boundaries and the i n t r o d u c t i o n of unnecessary quantization noise. Following t h i s procedure, the F o u r i e r transform of each function was obtained and curvature functions were then constructed from the f i r s t 100 harmonics of the spectra. The length of the disc r e t e curvature functions so constructed was 200 u n i t s . It was found that 100 harmonics provided approximately the best compromise between the retention of d e t a i l and r e j e c t i o n of high, frequency noise f o r the function lengths considered. As was pointed out i n the theory of Sec. 2.2 and as w i l l be seen i n the following chapters, the curvature functions obtained using the procedure just described do not n e c e s s a r i l y form closed curves i n the plane upon geometric reconstruction according to equations 2.2.21 through 2.2.23. Therefore, the f i n a l step i n the preparation of the o r i g i n a l curvature functions was to reconstruct the two-dimensional boundary curves corresponding to each }according to the equations 2.2.21 through 2.2.23, to close those curves by removing the "ramp" or "S" term (see section 2.2) and to r e c a l c u l a t e the curvature function from the closed boundary curves. Some examples of the reconstructed boundaries of the figures used are shown in F i g . 3.3.1(A), and the average frequency amplitude spectrum of the 100 sample function i s shown i n F i g . 3.3.1 (B). The average spectrum was obtained by f i r s t f i n d i n g the frequency amplitude Values (S ) f o r each-(A) o 1 ! i |,.' • 1 1 !" II Samples of the o r i g i n a l shapes used i n the quantisation noise study (A) and the average frequency component amplitude spectrum (B ) of the curvature functions over the 100 sample shapes. 35 sample function according to the equation: S - A + B (3.3.1) n on on where n denotes the harmonic number and A and B are the c o e f f i c i e n t s on on of equation 3.2.2. Denoting S ^ as the frequency amplitude value (S^) for the i th sample ( i = 1, 100), then the average spectrum of F i g . 3.3.1 (B) i s given by: 1 100 § n " 100 . \ Sni> ( 3 - 3 ' 2 ) i = l c a l c u lated for n = 1, 100. The t h i r d problem encountered i n the development of a model for the quantization noise on the b a s i c curvature functions i s whether to model the noise as a function of the period (T) of the b a s i c functions i n units of the sampling distance or to model the noise as a function of the array s i z e used i n the quantization. In many p r a c t i c a l a p p l i c a t i o n s , shapes of varying s i z e and complexity are quantized onto an array of f i x e d r e s o l u t i o n , r e s u l t i n g i n boundary periods (T) of considerable v a r i a t i o n . When attempting to model the quantization noise as a function of array r e s o l u t i o n however, a d i f f i c u l t y a r i s e s i n d e f i n i n g array r e s o l u t i o n for a given shape since, because of the wide v a r i e t y of s i z e s and shapes p o s s i b l e , each i n d i v i d u a l shape can occupy only a portion of the prescribed array and i n some a p p l i -cations, the s p e c i f i e d array may contain more than one shape. Furthermore, i t was found i n the r e s u l t s of preliminary quantization noise studies, that the behaviour of the quantization noise i s c l o s e l y r e l a t e d to the curvature function period, for a given algorithm rather than to the array s i z e used i n the quantization. The approach adopted for t h i s thesis was to develop a model for the quantization noise on the b a s i c curvature functions as a function of the period i n units of the sampling distance and to compare the s i x 36 contour t r a c i n g algorithms on the basis of the r e s u l t s . It i s then shown how the r e s u l t s can be applied to p r e d i c t the average quantization noise on an ensemble of b a s i c curvature functions of varying period such as would occur i n many p r a c t i c a l s i t u a t i o n s , f or any of the s i x algorithms, given an estimate of the d i s t r i b u t i o n of the periods. Quantized versions of the o r i g i n a l t e s t shapes were obtained from reconstructed boundaries corresponding to the o r i g i n a l curvature functions previously described. The quantization procedure was e s s e n t i a l l y that described i n Sec. 2.4, but because of the large number of quanti-zations necessary, a computer algorithm was developed to perform the task. A b r i e f d e s c r i p t i o n of that algorithm i s provided i n Appendix I. To study the quantization noise as a function of period requires, for each of the s i x contour t r a c i n g algorithms treated separately, the quantization of each test shape at an array r e s o l u t i o n which i s such that the r e s u l t i n g period, as measured by each algorithm, i s equal to some prescribed value. This was e a s i l y done using the quantization technique described i n Appendix I to an accuracy of +2 u n i t s , and was done for each of the 100 t e s t shapes, f o r a l l s i x algorithms and at three period lengths for each algorithm. However, to a f f o r d a meaningful comparison of the quantization noise c h a r a c t e r i s t i c s of the s i x algorithms, i t i s desirable to use the same quantized shapes (or equivalent hexagonally quantized shapes i n the case of algorithms 5 and 6) f o r each algorithm. The advantages of doing t h i s are: 1) i t provides an estimate of the r e l a t i v e average periods of the s i x algorithms for the same quantized shapes and 2) i t enables the determination of the r e l a t i v e s i g n a l - t o - n o i s e c h a r a c t e r i s t i c s of the s i x algorithms for the same quantized shapes. This however, cannot be accom-37 pli s h e d exactly since the same quantized shapes, while they may have equal boundary periods f o r one algorithm, do not n e c e s s a r i l y y i e l d equal boundary periods for another algorithm. The problem was approximately solved i n the following manner. The 100 t e s t shapes, which had a l l been normalized to the same period (200) as previously described, were each quantized at the same three array r e s o l u t i o n s . In the case of the hexagonal arrays, equivalent spacing of the points for square and hexagonal arrays was used as computed according to the method of Appendix 2. Each of the s i x algorithms was then used to measure the periods i n units of the sampling distance f o r a l l the quantized shapes. Average periods for each contour t r a c i n g a l -gorithm at each array r e s o l u t i o n were found and are l i s t e d i n Table 3.3.1. The v a r i a t i o n of periods for any one algorithm ranged between 5 and 10 u n i t s . Then, to equalize the periods for each algorithm, the shapes were requantized, varying the array r e s o l u t i o n s l i g h t l y i n each case, so as to y i e l d periods, for each algorithm, equal to the average for that algorithm (Table 3.3.1). These f i n a l array resolutions were used i n the study to follow. To convey a f e e l i n g for the array sizes involved, estimates of the average s i z e were made by f i t t i n g the minimum square array to samples of the quantized shapes. The three average s i z e s were approximately 15 x 15, 25 x 25 and 40 x 40 for a l l algorithms. Since the quantization was performed by computer, the o r i e n t a -ti o n of the shapes with respect to the array a x i a l d i r e c t i o n s was not c o n t r o l l e d , the appropriate o r i e n t a t i o n constants being unknown. Examina-t i o n of the quantized shapes revealed that the o r i e n t a t i o n was s u b j e c t i v e l y random. The s i x contour t r a c i n g algorithms were used to extract b a s i c ALGORITHM PERIODS 15x15 25^25 40x40 Array Array Array 1 74.32 128.13 182.81 2 70.32 124.13 178.81 3 50.53 89.77 128.65 4 58.95 104.58 149.38 5 56.37 101.47 146.23 6 118.20 208.92 297.59 Table 3.3.1 The .average periods of the b a s i c curvature functions corresponding to the s i x contour tracing algorithms for three average array s i z e s . curvature functions from each of the quantized shapes as described. The c o e f f i c i e n t s A ^ and were computed for each function and the ampli-tude quantities (U ) were found for each Fourier component (n) according to the equation: U = A2. + B 2 . (3. n An An ; where A ^ and B ^ are as defined i n equation 3.2.2. Denoting U ^ as the amplitude value (U ) f o r the i th sample, the average amplitude spectrum was computed f o r the 100 samples according to the equation: fn ~ 100 . 1 100 E U 1=1 1 n i (3.3.5) fo r the eighteen combinations of the s i x contour t r a c i n g algorithms and three average array s i z e s . The r e s u l t i n g average spectra are shown i n F i g . 3.3.2. In t h i s f i g u r e , each row represents the three spectra for a given algorithm, ranging i n order from algorithm L (row 1) to algorithm 6 (row 6). Column A corresponds to the 15 x 15 average array, column B to the 25 x 25 average array and column C to the 40 x 40 average array. The absolute frequency range of each p l o t i s 0 to .5 cycles per unit of the sampling distance (U.S.D.), warranting some explanation. The Fourier transform of a d i s c r e t e p e r i o d i c function (period = T units) produces amplitude and phase values for T/2 frequency components (T even). Nor-mally, these frequency components are r e f e r r e d to as "harmonics of the fundamental period (T)" or simply as "harmonics" and when the Fourier frequency spectra of two p e r i o d i c d i s c r e t e functions are compared, the comparison i s normally made on a harmonic by harmonic b a s i s . For t h i s study however, t h i s approach has two shortcomings. F i r s t the eighteen categories of functions being considered are characterized by r a d i c a l l y varying periods (T) and hence the Fourier spectra contain 'different numbers of harmonics. Secondly, and more importantly, the quantity of i n t e r e s t , the quantization noise amplitude on each Fourier component, e x h i b i t s a behaviour which i s consistent, not with the harmonic number of the Fourier component, but with the harmonic number divided by the period (T), i . e . , the frequency i n cycles per unit sampling distance (A moment's consider-ation reveals that t h i s must be the case). The range of the Fourier com-ponents i n cycles per unit sampling distance i s independent of the period T, being 0 to .5 for any function. Hence the spectra of F i g . 3.3.2 are a l l of the same length i n s p i t e of the f a c t that the number of harmonics A B C The average frequency component amplitude spectra (Un) of the basic curvature functions for the eighteen combinations of six contour tracing algorithms and three average array s i 41 i n each i s not the same. The frequency, i n cycles per unit sampling distance (F), of a given harmonic (n) i s not the same i n any of the spectra because the period (T) varies f o r each pl o t and F = n/T. The average quantization noise amplitude on each Fourier component was c a l c u l a t e d for each of the s i x b a s i c curvature functions at each average array s i z e . Denoting N ^ as the quantization noise ampli-tude (N ) on the i th Fourier component (see N^-equation 3 .2 . -$ - ) , then the average quantization noise on the n th component over the 100 samples i s given by: . ' 100 N * E N .. ( 3 . 3 . 6 ) n 100 . , n i i = l F i g . 3 . 3 . 3 shows the average quantization noise p l o t s for the eighteen combinations of s i x algorithms and three average array r e s o l u t i o n s , ranging from algorithm 1 (row 1) to algorithm 6 (row 6 ) and the 15 x 15 average array (column A) to the 40 x 40 average array (column C). The noise amplitude i s shown p l o t t e d versus frequency i n cycles per unit sampling distance which, as previously noted, ranges from 0 to .5 i n a l l cases. To a reasonable f i r s t approximation, the quantization noise increases l i n e a r l y with frequency i n each spectrum. An exception to this however, i s found i n the p l o t s corresponding the algorithm 6 . Here the average noise amplitude reaches a maximum at approximately . 3 cycles per unit sampling distance and subsequently decreases at higher frequencies. In the range 0 to . 3 cycles per unit sampling distance, the noise amplitude does r i s e approximately l i n e a r l y with frequency. While the slope of the l i n e a r approximation varies considerably from algorithm to algorithm, the v a r i a t i o n within any one algorithm for varying array s i z e i s not great. This phenomenon r e f l e c t s the r e l a t i v e consistency of the quantization noise with frequency (F) i n cycles per unit sampling distance. This A B C . . i i i i i l i l N I! o.s Jill o.s a-O.Zi si i ! iiiliilii iiiiiililiiiiiiiiii ^ ! El,?, IsisiSt I hfalWlIlpllIiPpllIIplIS^ O 1 ffjr o.zs 02 S O.S Fig. 3.3.3 The average frequency amplitude spectra of the quantization noise on the basic curvature functions (Nn) for the eighteen combinations of six contour tracing algorithms and three average array sizes. consistency i s further demonstrated i n the p l o t s corresponding to algorithm 6 where the maximum noise point i s constant i n terms of i t s frequency (F) of occurrence. At f i r s t glance, the r e s u l t s of F i g . 3.3.3 may appear to contradict the i n t u i t i v e notion that at higher array r e s o l u t i o n s , the quantization noise at a given frequency should be lower. This notion a r i s e s from the fact that shapes can be quantized with the preservation of more boundary d e t a i l on arrays of higher r e s o l u t i o n . In f a c t , no such contradiction e x i s t s . For any given contour t r a c i n g algorithm, the quantization noise at a given frequency (F) i s approximately the same fo r any array s i z e ( a c t u a l l y i t increases s l i g h t l y ) . The amount of d e t a i l representable i n a shape contour however, i s not a d i r e c t function of frequency (F) i n cycles per unit sampling distance. Rather, i t i s a function of the frequency content i n harmonics (n) of the curvature function*. Hence, for a given algorithm, although the quantization noise at a given frequency (F) i s the same for a l l array s i z e s , the noise on a given harmonic (n) i s less for the f i n e r array and the representable shape d e t a i l i s greater for the f i n e r array. In general, the quantization noise amplitude (N ) w i l l be correlated with the s i g n a l amplitude (S ). To i l l u s t r a t e the d i s t r i b u t i o n n of t h i s c o r r e l a t i o n over the frequency range (F = 0 - .5), c o r r e l a t i o n c o e f f i c i e n t s were computed according to the formula: Hence the terms "harmonic bandwidth" and "frequency bandwidth i n c y c l e s / U.S.D." used i n subsequent sections are based on these two representations. 100 z (s . - s ) 2 , n i n (3.3.7) where n represents the Fourier component number, the v e r t i c a l bars denote absolute value and i , the sample number. The d i s t r i b u t i o n of c o r r e l a t i o n with frequency (F) i s shown for the eighteen cases of Fig s . 3.3.2 and 3.3.3 i n F i g . 3.3.4. The degree of c o r r e l a t i o n i s generally independent of algorithm type, but shows a tendency to decrease with both increasing frequency (F) and increasing average array r e s o l u t i o n . The decrease i n c o r r e l a t i o n with increasing average array r e s o l u t i o n i s consistent with findings f o r the standard one-dimensional, amplitude quantization problem, where i t has been found (81) that the c o r r e l a t i o n between s i g n a l and quantization noise decreases with increasing quantization l e v e l number. t i o n were used f o r the quantization of the te s t shapes and the r e s u l t i n g periods f o r the s i x algorithms therefore varied. The values were provided i n Table 3.3.1. In a l l but the two l a r g e r s i z e s with algorithm 6, the periods were l e s s than the period (200) of the o r i g i n a l functions. In the two cases where the b a s i c function average spectra contain components exceeding 100 i n number, the c o r r e l a t i o n between S and N for the higher components i s zero since S was set n n o r n to zero beyond n = 100. The fac t that = 0 beyond n = 100 had no apparent e f f e c t on the and curves of Fi g s . 3.3.2 and 3.3.3 since, as w i l l be seen, the c o r r e l a t i o n between the s i g n a l components (A ) and the components of the b a s i c curvature functions (A ) i s . As previously noted, arrays of approximately the same r e s o l u -on 45 Fig. 3.3.4 The values of the correlation coefficient (p n) between individual signal frequency component amplitudes (S n) and the noise components (Nn) for the eighteen combinations of six contour tracing algorithms and three average array sizes. 46 n e g l i g i b l e at these higher frequencies. An important f a c t o r i n the s e l e c t i o n of an array r e s o l u t i o n f o r the quantization of a given shape i s the amount of d e t a i l i n the o r i g i n a l shape boundary, d i s c e r n i b l e a f t e r the quantization. C l e a r l y , the f i n e r the array, the more the d e t a i l that can be represented i n the quantized shapes. The amount of d e t a i l representable i n the boundaries of shapes i s determined by the harmonic bandwidth of the curvature function of those boundaries. Therefore, i t i s important to have an estimate of the "usable" bandwidth of the basic curvature functions for various periods ( i . e . , various array r e s o l u t i o n s ) . Although the t h e o r e t i c a l harmonic bandwidth of a d i s c r e t e b a s ic curvature function of period T i s T/2, the large amplitude of the quantization noise on the higher frequencies l i m i t s the "meaningful" bandwidth of the basic curvature functions to something l e s s than the t h e o r e t i c a l l i m i t . As i n d i c a t o r s of the u s e f u l bandwidth of the basic curvature functions, two q u a n t i t i e s have been defined and c a l c u l a t e d . The f i r s t quantity was designed to measure the degree of c o r r e l a t i o n between the o r i g i n a l harmonic component amplitudes (A ) and the corresponding component amplitudes of the basic curvature functions (A^ ) and was defined as: E (A .-A )(A. .-A ) . , oni on Am An 1=1 E n ~ /TOTS ~ 1 TOD ~ T / E (A .-A r • E (A. .-A. r / . , oni on . , Ani An V i = l i = l where the bars denote mean values over the 100 samples and A . and oni A. . represent the c o e f f i c i e n t s A and A. of equations 3.2.2 f o r Am on An the i th sample. The c o e f f i c i e n t can assume values ranging between +1.0 and because i t i s s e n s i t i v e to both amplitude and phase dif f e r e n c e s between the o r i g i n a l and the approximate function frequency components, i t i s a more meaningful measure of useful bandwidth than a s t r a i g h t amplitude c o r r e l a t i o n such as that depicted by equation 3.3.7. P l o t s of versus frequency i n cycles per unit of the sampling distance f o r each of the eighteen combinations of the s i x contour t r a c i n g algorithms and each of the three average array sizes are shown i n F i g . 3.3.5. In every case, the c o r r e l a t i o n i s highest for the low frequency components as would be expected from the r e l a t i v e s i g n a l and noise amplitudes at these frequencies. In a l l cases, the degree of c o r r e l a t i o n at frequen-c i e s beyond .25 cycles per unit sampling distance i s e s s e n t i a l l y random and of r e l a t i v e l y low magnitude. Since the degree of c o r r e l a t i o n between the A and A, values r e f l e c t s the "degree of confidence" one on An can place i n the U measurements, the r e s u l t s of F i g . 3.3.5 suggest n that the maximum usable or meaningful bandwidth for any of the s i x algorithms i s l e s s than .25 cycles per unit sampling distance and i n some cases, appears to be considerably l e s s (notably algorithm 6). Again the consistency i n the general form of the c o r r e l a t i o n p l o t s of F i g . 3.3.5 lends support to the i n i t i a l d e c i s i o n to study the quantization noise as a function of frequency (F) i n cycles per unit of the sampling distance. Note that while the usable bandwidth may be the same for several of the eighteen cases i n cycles / U.S.D., the usable "harmonic" bandwidth i s not the same. A second quantity revealing information concerning the usable bandwidth of the basic curvature functions i s the s i g n a l - t o -noise r a t i o of the amplitudes. However, since the noise can on occasion approach zero, t h i s r a t i o tends to be unstable. A s i m i l a r problem a r i s e s with the inverse quantity, the n o i s e - t o - s i g n a l r a t i o 48 individual signal frequency component amplitudes (A o n) and the components (A^ n) of the basic curvature- functions for the eighteen combinations of six contour tracing algorithms and three average array sizes. since the signal amplitude on a given harmonic can be zero. A related quantity which i s stable in both limits of signal or noise amplitude approaching zero i s the quantity ; 100. .S.. z n = Too" . E 1 ( ^ + ¥ T ) > ( 3 ' 3 ' 9 ) 1=1 n i n i where N . and S . denote the quantities N (equation 3.2.4-) and S ni n i n n (equation 3.3.1) respectively for the i th sample. In the limit as S 0, Z approaches 0 and in the limit as N 0, Z approaches 1.0. ni ni n£ xi± In the rare cases where S .and N were identically zero simultaneously, ni ni J Z • was assumed undefined and the sample was ignored. Fig. 3.3.6 shows ni the Z^ plots for the eighteen combinations of the six contour tracing algorithms and three average array resolutions. The Z^ curves show a reasonably high degree of uniformity over the range of both array size and algorithm type. Each plot decays from an i n i t i a l l y high value at the low frequencies to a low value at a freqeuncy of approximately .25 cycles per unit sampling distance after which i t i s relatively constant or only slightly decreasing. The rate of decrease of Z^ over the frequency range 0 to .25C./U.S.D. and the magnitude of the "plateau" value in the frequency range .25 to .5 C/U.S.D. vary with both average array resolution and algorithm type. In the next section, a model for the Z characteristics of n the six algorithms at the different average array resolutions i s pro-posed. It i s shown that the model provides a reasonably accurate f i t to the Z curves over the "useful" bandwidth (0 - .25C./U. S.D.) . The n model i s then used to quantitatively compare the contour tracing algorithms on the basis of the Z^ characteristics and to demonstrate the variation in those characteristics with changes in array resolution. 50 Fig. 3.3.6 The values of the signal-to-noise characteristic (Z n) at each frequency component for the eighteen combinations of six contour tracing algorithms and three average array sizes. 51 3.4 A Model for the Signal-to-Noise Characteristics of the Basic Curvature Functions The Z characteristics of the basic curvature functions for n the six contour tracing algorithms were selected as the basis of a model for two reasons. F i r s t , the behaviour of the Z plots was the n most "well-behaved" or consistent of the two indicators of bandwidth (Z and e ). Secondly, the nature of the S (Fig. 3.3.1) and the n n n N (Fig. 3.3.3) plots suggest an approximate analytical form for the n Z curves. Since the signal spectrum (S ) is essentially f l a t (with n n the exception of the low frequency harmonics) and since the noise spectrum (N ) shows an approximately linear increase with frequency in most cases, a possible analytical form for the Z^ curves is expressed in the assumption: " - _ 1 _ 1 . _1 Z n 100 . E 1 N . ~ 1 + $F * (3.4.1) i=l i | n l 1 + sT n i where N . and S . have been previously defined, n represents the Fourier component number and F = ^ , (3.4.2) where T is the function period in units of the sampling distance. The parameter " f i " i s a constant for a given algorithm and period (T), but varies with both algorithm and period changes. While the relationship expressed in equation 3.4.1 is essentially empirically derived, the curve described by "j" A V > provides an accurate f i t to the Z n plots of Fig. 3.3.6 over the useful bandwidth range (0 - .25 cycles/unit sampling distance) as can be seen in Figs. 3.4.1 and 3.4.2. A B C 3 F i g . 3.4.1 A demonstration of the l e a s t squares f i t of the t h e o r t i c a l curve (l/(l+gF)) to the experimental Z n values over the frequency range, 0 to .25 cycles per u n i t sampling distance for contour t r a c i n g algorithms 1 to 3 and at the three average array r e s o l u t i o n s . Ln r 1 i — 1OUENCT0'(C/U.S.D'.1) —I— 0.2 -1 0.23 -I 1 I— 0,03 0.1 O.IS FREQUENCY IC/U.S.D.) —1 3.23 —I 1 1 0.05 0.1 O.IS FREQUENCY [C/U.S.D.J - I — 3.2 —I 0.23 ^?OUENa'ic/U.S.u'." - 1 — 0.2 3.23 0.0 • i i i i 0 OS 0.1 0.13 0.2 3 FREQUENCY (C.'U.S.O.J .23 lfccTtU(C/U.S.°D1? ° l —1 3.25 0.3 F i g . 3.4.2 A demonstration of the least squares f i t of the theoretical curve (1/U+3F)) to the experimental Z values over the frequency range, 0 to .25 cycles per unit of the sampling distance for contour tracing algorithms 4 to 6 and at the three average array resolutions. 54 In F i g s . 3.4.1 and 3.4.2, the crosses denote the amplitude values of the v e r t i c a l strokes taken from the Z p l o t s of F i g . 3.3.6 n over the frequency range 0 - .25 cycles per unit sampling distance i n each of the eighteen cases. The t h e o r e t i c a l curves were f i t t e d to the Z sample points (crosses) i n each of the eighteen cases i n d i v i d u a l l y , n using a standard l e a s t squares f i t algorithm. In each case, a value f o r "8" was found, through successive i t e r a t i o n , which minimized the quantity: M E W(n) (Z - ) 2 , (3.4.3) 1 1 1 1_1_D n n=l 1+B • -where M, an integer, represents the highest order harmonic corresponding M to a frequency (F = —) i n cycles per unit sampling distance^less or equal to .25, and W(n) represents a weighting factor associated with the n th component. The weighting factor W(n) was used i n the l e a s t squares f i t to vary the emphasis placed on p a r t i c u l a r sample points (crosses) i n determining the f i t . In the range F = 0 to .25, a weight of unity was assigned to a l l points except the point corresponding to n = 1 which was given a weight of zero. It was found that the sample Z value of the f i r s t harmonic (Z.,) was much lower i n a l l cases than n 1 that predicted by the t h e o r e t i c a l curve and that i t s i n c l u s i o n with a weight of unity resulted i n a downward s h i f t of the e n t i r e curve, causing a poorer f i t i n the frequency region of i n t e r e s t (.05-*. 25C./U. S .D. ) . With the exception of the lowest (1-4) order frequency components, i t can be seen i n the graphs of F i g . 3.4.1 and 3.4.2, that the t h e o r e t i c a l curves (-;—rr—) provide an accurate estimate of the 1 +3 F observed Z^ values, given that the appropriate value of the parameter g i s known. CD c5-> F i g . 3.4.3 The values of the "3" parameters as functions of period f o r the s i x contour t r a c i n g algorithms found by a l e a s t squares f i t t i n g of the curve (1/(1+3F)) to the experimental Z n values. Values of the parameter 3 f o r each of the s i x contour t r a c i n g algorithms are shown as functions of the average period (T) i n F i g . 3.4.3. In F i g . 3.4.3, the algorithm corresponding to each curve i s i n d i c a t e d by number. In the case of algorithm 6, the value of 6 f o r a fourth and smaller average period i s also included enabling a wider range of comparison of the r e s u l t s . Generally, the smaller the value of 3, 56 the wider the usable bandwidth i n cycles per unit of the sampling distance (but not necessarily in terms of harmonics as w i l l be seen). The signal-to-noise characteristics of the basic curvature-functionshave been modelled as functions of frequency in cycles per unit sampling distance. However, as was noted earlier, the amount of shape boundary detail representable in a curvature function i s related to the usable bandwidth in harmonics of the function period, not in cycles per unit sampling distance. However, since harmonic number is simply related to absolute frequency in cycles per unit sampling distance by the relation: n = | , (3.4.4) the periods provided in Table 3.3.1 and the g parameter values provided in Fig. 3.4.3 can be used to compare the six contour tracing algorithms on the basis of the usable harmonic bandwidth available in their respec-tive basic curvature functions. The comparison can be done in at least two ways. One approach i s to determine, for approximately the same average array size, which contour tracing algorithm produces the basic curvature function with the widest harmonic bandwidth, given that the value of the highest harmonic i s greater or equal to some specified value. To afford such a comparison, the six theoretical Z curves (Z*) for the 25 x 25 n n average array are plotted in Fig. 3.4.4. The values of the six "g" i parameters used to plot the curves were those found by the least squares f i t t i n g algorithm for the 25 x 25 average array size and in Fig. 3.4.3, correspond to the middle "dot" in each trace (second from i right in algorithm 6). If the minimum acceptable Z value i s ar b i t r a r i l y set at .5, the bandwidth i n cycles per unit sampling distance f o r each algorithm can be read from F i g . 3 .4.4 (dotted l i n e s have been drawn fo r t h i s purpose). Applying equation 3 .4.4 and using the periods (T) from Table 3 . 3 . 1 , the harmonic bandwidthswere c a l c u l a t e d and are shown i n Table 3.4 .1. As can be seen i n Table 3 . 4 . 1 , algorithm 4 produces Contour Tracing Algorithm Function Period Approx. Average Array Size Bandwidth (C./U.S.D.) Bandwidth (Harmonics) 1 128.13 25x25 .102 13.09 2 124.13 25x25 .112 13.92 3 89.77 25x25 .149 13.35 4 104.58 25x25 .156 16.31 5 101.47 25x25 .155 15.71 6 208.92 25x25 .067 14.00 Table 3 .4 .1 The a r b i t r a r i l y defined usable bandwidth of the s i x b a s i c curvature functions i n harmonics and cycles per unit sampling distance for approximately the same average array s i the basic curvature function with the widest harmonic bandwidth f o r a given average array s i z e , but i t does so at the expense of considerable increase i n computational complexity. A good compromise seems to be av a i l a b l e i n algorithm f i v e which y i e l d s good harmonic bandwidth c a p a b i l i t i e s f o r a minimal computational complexity, provided an hexagonal array can be e a s i l y implemented. An a l t e r n a t i v e approach to the comparison of the s i x algorithms i s to determine, for the same period (X) of the basic curvature functions, which- contour t r a c i n g algorithm produces the b a s i c curva-ture function with widest harmonic bandwidth, given that the Z^ value of the highest harmonic i s greater or equal to a s p e c i f i e d value. The t h e o r e t i c a l Z' curves for the s i x contour t r a c i n g algorithms are shown n ° pl o t t e d i n F i g . 3.4.5, the value of the " 3 " parameter corresponding to T = 100 being used i n each case. The bandwidth i n cycles per unit sampling distance for a minimum Z^ :value of .5 were measured from F i g . 3.4.5 (dotted l i n e s are provided f o r th i s purpose) and the harmonic bandwidths were computed. Table 3.4.2 shows both the measured bandwidth Contour Tracing Algorithm Function Period Bandwidth (C./U.S.D.) Bandwidth (Harmonics) 1 100 .113 11.3 2 100 .117 11.7 3 100 .143 14.3 4 100 .159 15.9 5 100 .155 15.5 6 100 .069 6.9 Table 3.4.2 The a r b i t r a r i l y defined usable bandwidth of the s i x b a s i c curvature functions i n harmonics and cycles per unit sampling distance f o r the same period (T=100). 60 IN" 0.0 0.05 0 FREQUENCY (C/U.S 0.15 D . 3 0.25 F i g . 3.A.5 The t h e o r e t i c a l Z n curves f o r the s i x contour t r a c i n g algorithms f o r the same period (T=100) of the corresponding basic curvature functions. 61 i n cycles per unit sampling distance and the computed bandwidth i n harmonics for each algorithm. Once again, the widest usable bandwidth i s provided by algorithm 4 but again a good compromise i s provided i n algorithm 5, assuming an hexagonal array can be e a s i l y implemented. A complete comparison of the r e l a t i v e advantages and d i s -advantages of the s i x contour t r a c i n g algorithms must take several factors i n t o account, i n c l u d i n g the r e l a t i v e periods of the basic curvature functions for a given average array s i z e , the number of amplitude l e v e l s occupied by each function, the r e l a t i v e complexity of measurement of each, in c l u d i n g a consideration of sequential versus p a r a l l e l implementation, and the usable harmonic bandwidth of the respective functions. In most a p p l i c a t i o n s , the importance attached to each of these considerations w i l l depend upon the nature of the problem and the r e s t r i c t i o n s imposed by the environment i n which the problem i s to be solved (memory capacity, input device e t c . ) , but some general comments can be made. Algorithm 1 produces poorer quantization noise c h a r a c t e r i s t i c s for a given average array s i z e or period than most of the other algorithms. However, as w i l l be seen i n Chapter f i v e , t h i s algorithm leads to a p a r t i c u l a r l y convenient p a r a l l e l or two-dimensional array configuration for the i s o l a t i o n and measurement of boundary curvature. Hence, the use of algorithm 1 would appear to be r e s t r i c t e d to s i t u a t i o n s where a p a r a l l e l configuration i s d e s i r a b l e . E i t h e r algorithm 2 or 3 appear to o f f e r , f o r a sequential scheme, the best compromise, f o r a square array,between implementation complexity and noise c h a r a c t e r i s t i c s . Algorithm 2, although i t appears to o f f e r a s l i g h t l y l a r ger usable harmonic bandwidth than algorithm 3 f o r a given average array s i z e , does so at the cost of a much longer function period. This may not be acceptable in situations where much further processing i s to be done on the functions. For the same period, algorithm 3 has a sub-stantially larger usable harmonic bandwidth. While algorithm 4 yields the largest usable harmonic bandwidth for both a fixed average array size and a fixed period, i t does so at the cost of considerable increase in measurement and storage complexity. Subsequent operations on the basic curvature function by computer are also costly since the spacing of the function points i s not constant in units of the sampling distance. Algorithm 5 appears to offer almost as good harmonic bandwidth capa-b i l i t i e s and produces a basic curvature function with points of con-stant spacing. It does, however, require an hexagonal input array configuration. While algorithm 6 . does provide a reasonable harmonic bandwidth for a given average array size, the periods of the basic curvature functions are exceptionally long. Hence the use of algorithm 6 would seem to be restricted to applications where i t i s particularly advantageous to have a function with binary amplitude. Such an application is the case where the basic curvature function i s to under-go a Walsh function transformation (56,57). Since Walsh functions are also binary valued (+1), t n e multiplicands, multipliers and quotients in the transformation computations would a l l be +1, essentially reducing multiplication to sign changes. Considerable saving in implementation complexity and execution time could be achieved. Such an application (use of the Walsh transform) has been proposed for Pattern Recognition applications, the object being to use the Walsh coefficients as feature values. In most practical applications, the periods of the curvature functions of the quantized shapes being considered would not be con-stant since the size and shape of the patterns being considered often vary widely. In such situations, i t i s useful to have an assessment of the average usable harmonic bandwidth of the basic curvature functions over the range and distribution of the periods involved. This can be achieved as follows. Let ct^ be a random variable which can assume any of the possible values of Z . where: r n l n n and Z , denotes the value Z for a function of period T, . Similarly, nl n 1 a„, a„,...a are random variables corresponding to the values of 2. S m Z Z „...Z . The problem of determining the average noise charac-nz nj nm ter i s t i c s of a set of m basic curvature functions of varying period can be restated as a problem of finding the expected value or mean value of the sum of m random variables. That i s , the problem is one of finding the expected value of a. + a„ + a„...a . To solve this ° 1 2 3 m problem, i t i s necessary to apply the linearity property of expecta-tion which states that: E{a,+a9+av..a } = V{a,} + E{ a„} + E{a-}...E{a } , ( 3 . 4 . 6 ) where E{ } denotes "expected value of" or "mean value of". Assuming that: E{a,} = Z (3.4.7) 1 n i where Z , represents Z (equation 3.3 .9) for a function of period T„ , nl n 1 then the average signal-to-noise characteristics of the basic curvature functions of varying periods can be calculated from a knowledge of the period values and the "3" plots of Fig. 3.4.3. For example, the average noise characteristic for the n th harmonic of m basic curvature functions of periods Ti> T2**' T m> denoted is given by: 1 m i Z = - I — — — , (3.4.8) n m i = l l+fc.2-i where is the value of the 3 parameter obtained from Fig. 3.4.3 for the period 1\. The values of 3_^ can be read directly from Fig. 3.4.3 or, for computational expediency, they can be expressed as functions of the period T^ since 3 is approximately linearly related to T_^ for a l l six algorithms. 3.5 Curvature Domain Bandwidth and Boundary Detail. As previously stated, the amount of detail representable in a boundary reconstructed from a given curvature function, depends upon the harmonic bandwidth of that curvature function. However, since "boundary detail" i s a subjective quantity, i t is d i f f i c u l t to establish an exact relationship between this detail and the curvature function bandwidth. Furthermore, the amount of detail required and hence the necessary curvature function bandwidth, varies for the same shape, depending upon the nature of the problem being considered. However, some general aspects of the relationship between harmonics of the curvature function and the detail in the reconstruction boundary can be described with reference to Figs. 3.5.1 and 3.5.2. Fig. 3.5.1, column A, shows five hand printed alphabetical characters reconstructed from their respective basic curvature 65 D k 1=154 lM.ll— I .mi ItJ.. . I L . H . iL T=166 T=120 InLiuLdiiimih inh i i T=156 I l l U i m i . n l l i i h W M . L T=144 3.5.1 Column A shows five sample shapes reconstructed from basic curvature functions (algorithm-.l). Column B shows Fourier component spectra of the basic curvature and tangent angle s functions. Columns C to F show shapes reconstructed from curvature functions in turn constructed using P 5 2P, 3P and 4P harmonics where P represents the a r b i t r a r i l y selected number of points of maximum positive curvature (indicated by dots in column A ) . B C D E F Fig. 3.5.2 Column A shows f i v e sample shapes reconstructed from b a s i c curvature functions (algorithm 1). Column B shows Fourier component spectra of the b a s i c curvature and tangent angle functions. Columns C to F show shapes reconstructed from curvature functions i n turn constructed using P, 2P, 3P and 4 P harmonics where P represents the a r b i t r a r i l y selected number of points of maximum p o s i t i v e curvature (indicated by dots i n column A). 67 functions. Although i n p r a c t i c e , the reconstructed boundaries are discret e functions, the i n d i v i d u a l points have been joined i n the figures shown. The characters were obtained by sketching each on a square array of d i s c r e t e points, using an i n t e r a c t i v e l i g h t pen and display u n i t . The b a s i c curvature functions were extracted from the so quantized shapes using algorithm 1 of F i g . 3.1.1. The three shapes of F i g . 3.5.2 were obtained i n a s i m i l a r fashion, on arrays of somewhat higher r e s o l u t i o n . In column B of Fi g s . 3.5.1 and 3.5.2, p l o t s of the amplitude of the f i r s t 60 frequency harmonics of the b a s i c curvature function are shown (top spectrum) f or each shape. In the lower spectrum f o r each case, are shown the f i r s t 60 harmonics of the tangent angle function as described i n equation 2.2.2. These c o e f f i c i e n t amplitudes are equal to the curvature function component amplitudes m u l t i p l i e d by the factor (T/2irn) as described i n equation 2.2.2. Each spectrum s t a r t s at the f i r s t harmonic ( i . e . the constant term i s omitted) and the v e r t i c a l or amplitude s c a l i n g i s the same f o r a l l curvature function spectra and f o r a l l tangent angle function spectra but the s c a l i n g f o r the curvature function spectra i s not the same as for the tangent angle function spectra. The periods i n units of the sampling distance of each corresponding basic curvature functions are shown for each shape. The shape of the reconstructed boundaries i s strongly r e f l e c t e d i n the magnitude of the lower order harmonic amplitudes of the curva-ture spectra. Generally, i f the reconstructed boundary has a t o t a l of m s i g n i f i c a n t l y large points of high (+ve) curvature (see dots on the shapes of column A), then the n th harmonic of both the corresponding 68 curvature and tangent angle function spectra i s large and in the tangent angle function spectrum, often dominant. For example, in Fig. 3.5.1 (1 and 2), each shape has two "ends" representing two points of extremely high curvature and the second harmonic in each tangent angle function is dominant. Similarly, the fourth harmonic is dominant in shape (3) of Fig. 3.5.1, the third is dominant in Fig. 3.5.1 (5), and the twelfth in Fig. 3.5.2 (1). A convenient rule of thumb for estimating the required bandwidth in the curvature function for a suitable representation of a given shape can be described with reference to Figs. 3.5.1 and 3.5.2, columns (C) to (F). The reconstructed boundaries shown i n these columns were obtained from curvature functions constructed with varying harmonic bandwidth. In each case, the number of points of maximum (+ve) curvature on the reconstructed boundary (column A) were counted, (the points included are marked with a dot in a l l cases). The shapes of columns C to F were constructed from curvature functions of bandwidth equal to P, 2P, 3P and 4P respectively, where P i s the number of curvature points selected. As can be seen, a reasonable amount of boundary detail is obtained in a l l cases using a curvature domain bandwidth of 3P or 4P. Hence, to determine the required bandwidth for a given shape, an approximate rule would be to count the points of maximum positive curvature on the boundary contour, including a l l points deemed significant for the problem under con-sideration and to then design for a bandwidth in harmonics of three to four times that value. It i s interesting to note in passing that B r i l l et a l . (19-23) used the tangent angle harmonic coefficients as defined by equation 2.2.2 as feature values in a scheme for the machine categorization of alphabetical and numerical characters. They found that the optimum number of harmonics which yielded the highest recognition rate was in the v i c i n i t y of 15 to 20. Since the most complex of the alphabetical characters have five points of maximum positive curvature (e.g. E, M, W, 5, 3, 4), the optimum multiple of "P" for this problem would seem to be 3 to 4 as previously proposed. With a required bandwidth specified in this way, and a minimum signal-to-noise characteristic arb i t r a r i l y selected, the necessary array resolution (or period) can be chosen using the results of this chapter. '3.6 Discussion on the Quantization Noise Experiments A source of error in the quantization noise experiments is the quantization noise already existing on the original test shapes. While this possibility does not negate the results as presented, i t does pose the problem of the extent to which the average signal spectrum (S^ of Fig. 3.3.1) is truly representative of the average spectrum for alphabetical characters in the absence of quantization noise. Although this question cannot be resolved completely, a qualitative estimate of the noise levels on the individual harmonics can be made from the results of this chapter. The average period of the original functions before the low-passing (see preparation of original shapes in Sec. 3.3) was approximately 1000 units and hence the number of harmonics in the range 0 to .5C./U.S.D. was 500. In the f i n a l version of the test shapes, 100 of these were used and hence the highest frequency in C./U.S.D. used as .1. To the extent that the results of the experiments of Sec. 3.3 can be applied in this period range, i t would appear that the lowest Z characteristic, being that for the 100 th harmonic, would n be greater than .5. That is^the relative signal and noise amplitudes were, at worst, equal. In the computation of many of the spectra of Figs. 3.3.2 through 3.3.6, considerably less than the 100 signal harmonics were used. In these cases, the relative signal-to-noise amplitudes on the original harmonics would be much higher than unity. The applicability of the noise model to other problems in pattern recognition or picture processing work is probably limited to shapes with approximately f l a t curvature function spectra. Such would be the case with most shapes containing corners in their boundaries since corners yield impulses in the curvature domain which in turn contribute to f l a t frequency spectra. The range of periods ( 50 to 200 units of the sampling distance) is a useful range for shapes of the complexity of alphabetical characters. The methods employed in the thesis however, could be used to extend the range to higher periods and hence finer arrays in a straight forward manner. The assumption of essentially random orientation of the shapes with respect to the array axial directions is somewhat restricting In some applications, such as machine printed characters, many of the character boundaries or portions thereof could appear consistently aligned with array axial directions, changing the noise characteristics. This problem is characteristic of the limitations of any quantization noise model and each case of this kind can only be handled individually. The quantization noise study has been performed on curvature functions exclusively. However, since the harmonic amplitudes of the -tangent angle function, as defined in equation 2.2.2, are related to 71 those of the curvature function, many of the results such as the and curves apply to the tangent angle functions as well. An application of this fact w i l l be discussed in the f i n a l thesis summary at the end of Chapter five. 3.7 An Introduction to Curvature Function Smoothing The basic curvature functions serve to i l l u s t r a t e many of the characteristics of the quantization noise on curvature functions extracted from quantized shapes. However, for many applications, these basic curvature functions, being trains of impulses, are not suitable. Often, a smooth curvature function is desirable for further processing operations such as locating points of maximum or minimum curvature, measuring the spacing between curvature peaks, etc. Therefore, the remainder of the thesis i s concerned with a study of three approaches to the problem of obtaining smoothed curvature functions for this purpose. The contour tracing algorithm used in each case i s algorithm 1. This algorithm was selected, in spite of i t s poor noise characteristics, since i t leads to a particularly simple realization of one of the smoothing methods, namely area operators, to be discussed in Chapter five. The same algorithm was used in a l l three studies so as to enable an unbiased comparison of the smoothing methods themselves. However, with the exception of area operators, the smoothing methods can be combined with any of the six algorithms with no d i f f i c u l t y . The approaches to smoothing of the curvature functions to eliminate quantization noise studied in this thesis differ in both the mechanics of the smoothing operation and in the "domain" in which the smoothing is performed i.e., either on the boundary functions of the quantized shapes themselves (x(s^):y(s^) domain) before curvature extraction or on the basic curvature function (K(s_^) domain) after curvature extraction. The f i r s t approach to the smoothing problem, studied in Chapter four, is referred, to as slope approximation. The methodology involves the extraction of the two boundary functions x(s^) and y(s^), i = 1, T and the passing of each through a low-pass f i l t e r . From these smoothed functions, the tangent angle or slope is approximated according to equations 2.2.18 and 2.2.19. Curvature i s then computed according to 2.2.20 from the tangent angle function. The second approach to obtaining a smooth curvature function, studied in Chapter five, involves spatial averaging of the array point values (0 or 1) within a specified circumference of a given boundary point. This method is referred to as the spatial or area operator approach and can be designed to extract the curvature function and smooth i t simultaneously. The third and f i n a l approach to obtaining a smoothed curvature function is to extract the basic curvature function as exemplified by Fig. 3.1.1(c) and to pass that function through a simulated low-pass f i l t e r . This approach, referred to as curvature domain f i l t e r i n g , is also studied in Chapter five. Although the three approaches to smoothing differ in the mechanics of application, each can be treated as an operation (either linear or non-linear) on the basic curvature function and the frequency attenuation characteristics of each method in the curvature domain can be found by comparing the spectrum of the basic curvature function and that of the smoothed curvature function from the same quantized shape. The frequency attenuation characteristics of the smoothing i n each case are found to show a suppression of high frequencies and a d i s t o r t i o n , to a greater or l e s s e r extent, of the low frequencies. Therefore, from these frequency attenuation c h a r a c t e r i s t i c s , estimates of the bandwidth i n the curvature domain f o r a given degree of smoothing and for each smoothing approach can be made. The basis of comparison of the three methods i s then to measure, f or the same curvature domain bandwidth, the erro r between the smoothed curvature function and that of the o r i g i n a l shape boundary. 74 4. TWO ERROR CRITERIA AND THE SLOPE APPROXIMATION METHOD In this chapter, two error c r i t e r i a are described to measure the the performance of the three approaches to the smoothing of curvature functions. Then, the test shapes used in the smoothing study are described and the results for the slope approximation method are presented. 4.1 Two Error Criteria for Assessing the Effectiveness of the Smoothing of Curvature Functions If both the original curvature function of the boundary of a figure and the approximate function obtained from a quantized version of the same figure are compared, then the method used to obtain the approximate function can be evaluated by computing the mean square error between them, over the period (T). The following error criterion was therefore devised for comparing the various approaches to the smoothing of curvature functions studied in Chapters four and five. A quantized figure which has a quantized boundary length of T units produces a discrete periodic curvature function composed of T sample points. Hence i f : K,(s.), i = 1, T represents the discrete A l v approximate curvature function obtained from the quantized figure, K (s^) , i = 1, T represents the discrete version of the curvature function of the original shape from which the quantized shape was derived, ! T K A(s) = f E K A(s.) i=l 75 1 T and K Q(s) = - E K o(s.) i=l t h e n ' I [ ( K A ( s I + . ) - K A ( s ) ) - ( K o ( s . ) - K o ( s ) ) ] 2 ERROR^ = Min ^ — • (4.1.1) j E [ ( K A ( s . ) - K ^ ) ) 2 + ( K o ( s . ) - l T ( s " ) ) 2 ] i=l , Equation 4.1.1 was used to calculate ERROR^ at each of the integer values of the "delay" parameter j between 0 and T. Varying j effectively shifts one function with respect to the other and hence eliminates the effect on the error of rotation of the shapes, one with respect to the other. With a l l of the smoothing methods, in the limit of i n f i n i t e smoothing (zero bandwidth), the functions K (s.), i = 1, T and K Q ( S ^ ) , i = 1, T approach the constant 2TT/T and ERROR^ approaches unity. The function K . ( s . ) , i = 1, T contains the information of A 1 interest concerning the shape of the original boundary before quantiza-tion (i.e. the "signal"), and quantization noise. While the objective in the smoothing is to eliminate the noise without distorting the signal information, each of the smoothing operations studied does, in practice, affect both the signal and quantization noise components. Hence, the ideal error criterion would yield information concerning the effects of the smoothing on both the signal and the noise. It w i l l be seen in practice, that ERROR^ as defined, is highly sensitive to the effects of the smoothing on the quantization noise in the curvature function but is relatively insensitive to the effects on the signal components. This i s due to two characteristics of the quantization noise distribution over the frequency range of the curvature functions. As was seen i n the previous chapter, the quantization noise l e v e l s on a l l but the very low order harmonics i s r e l a t i v e l y high compared to the s i g n a l . Secondly, a mean square e r r o r c r i t e r i o n weights each frequency of the curvature function equally. This can be seen i n the expressions for mean square e r r o r i n terms of harmonics of Chapter three (equations 3.2.3 and 3.2.4). Therefore the ERROR^ error c r i t e r i o n w i l l be s e n s i t i v e to those frequencies where the harmonic amplitudes and hence the quantization noise i s greatest, i . e . , the high frequencies, and i t s behaviour as the bandwidth i s reduced w i l l be governed by the e f f e c t s of the smoothing on these high frequencies. To o f f s e t t h i s phenomenon i t was found useful to include a second e r r o r measurement which would r e f l e c t the e f f e c t s of the smoothing on the " s i g n a l " components of the curvature function. This was accomplished as follows. I f curves i n the plane corresponding to the boundaries of two-dimensional shapes are geometrically reconstructed from both the o r i g i n a l and the approximate versions of the curvature function f o r the same f i g u r e , then the e r r o r between them can be used to evaluate the method used to obtain the approximate curvature function. Such an err o r measurement i s found to r e f l e c t the e f f e c t s of the smoothing or f i l t e r i n g on the " s i g n a l " components of the approximate curvature function since i t i s measured i n a domain (x(s_^) : y(s^)) where the si g n a l - t o - q u a n t i z a t i o n noise r a t i o i s r e l a t i v e l y high and where the high frequency components have been attenuated by i n t e g r a t i o n . This second e r r o r c r i t e r i o n was devised i n such a manner as to be i n s e n s i t i v e to those aspects of the boundary curves which are not considered important i n the i d e n t i f i c a t i o n of the shapes, i . e . , s i z e , o r i e n t a t i o n and t r a n s l a t i o n with respect to a Cartesian co-ordinate system. Independence of relative translation and rotation of the curves was achieved by locating the centroid of the two boundary curves at the origin of the x and y axes and by then rotating one curve with respect to the other to find the relative rotation of minimum error. Relative size independence was achieved as follows. Applying the notation of Sec. 2.2, the discrete version of the equation for a boundary curve in the plane i s : RCV) =tx(s.) +Ty(si) i = 1, T. (4.1.3) The magnitude of the discrete vector R(s_^) , i = 1, T is hence given by: |R(s.)| = /(x(s.) 2 + y ( s . ) 2 i = 1, T, (4.1.4) and the average value over the period by: i T AVG{|R(s.)|} = Z |R(s.)|. (4.1.5) i=l Size normalization of boundary curves i s achieved by normalizing equation 4.1.3 with respect to the average value, "AVG{ | R(s_^) | }" to get the equation: t(s.) _^ x(s.) y ( S i ) AVG{|R(s.) | } = 1 AVG{'|R(s.)T} + j AVG{ | R(s ) | }' (4.1.6) The averaging of the vector R(s^) i = 1, T amounts to finding the radius of a circle in the plane. This radius in turn reflects the size of the figure. By normalizing the boundary functions x(s^): y(s^), i = 1,T with respect to this radius value, the two figures are normalized with respect to size. The second error criterion involved the calculation of the sum of the two mean square errors between the exact and the approximate versions of both the x(si)/AVG{ | R(s ) \ } i = l , T and the y (s ')/AVG{ | R ^ ) | } i = 1, T functions and normalizing the results so that the error for a 78 constant curvature function ( c i r c l e i n the plane) was unity. This normalization was done to allow comparison of the behaviour of the two error c r i t e r i a by having both approach the same value i n the l i m i t of i n f i n i t e smoothing (zero bandwidth) of the curvature functions. The mechanics of c a l c u l a t i n g the second error (ERROILp involved f i r s t the computation of the di s c r e t e version of the o r i g i n a l boundary curve R (s.) = i x (s.) + i y ( s . ) , i = 1, T from the d i s c r e t e o r i g i n a l o x o x' J J o I ' ' ° curvature function K ( s . ) , i = 1, T and the d i s c r e t e version of the o x approximate boundary curve R.(s.) = i x.(s.) + j y ( s . ) , i = 1, T from A X A X A X the approximate curvature function K.(s.), i = 1, T, one rotated with A X respect to the other by a constant 6. That i s : t o ( 8 i ) = ? x o ( s i ) + ^ y 0 ( s ± ) = i E cost E K ( s T ) + 6] j = l L=l -A i J + j Z s i n [ Z K ( s T ) + 6J, i = 1, T (4.1.7) j = l L=l ° L and R A ( s i ) = 1 X A ( s i } + j y A ( s i ) = i Z cos[ Z K.(s )] j = l L=l A L + j Z s i n [ E K A ( s L ) l , i = 1, T. (4.1.8) J j = l L=l In equations 4.1.7 and 4.2.8, the t r a n s l a t i o n a l constants ( i and j i n equation 2.2.23) have been set to zero, assuring that the boundary functions x ( s . ) , x . ( s . ) , y (s.) and y . ( s . ) , i = 1, T, J o x ' A x Jo x J A x have zero means. Next the quantity: 79 x A ( s . ) * 0 < s i T ERROR = s ! — - _ ^ _ r 0 X=l 1 A 1 -' * o 1 ' T yA(s±) y o ( s i ) 2 i ^ 1 l A V G { l R A ( s . ) j"} AVG{|R o(s.) |> was c a l c u l a t e d with new values of x (s.) and y ( s . ) , i = 1, T being o 1 o 1 found for d i f f e r e n t values of the constant 6 according to equation 4.1.7, u n t i l the minimum value of "ERROR" was found. F i n a l l y , denoting ERROR' as the value of "ERROR" for K (s.) , i = 1, T equal to a constant, ERROR* = ERROR/ERROR'. (4.1.10) 4.2 The O r i g i n a l Test Shapes for the Smoothing Study The test shapes selected for the smoothing study were a r b i t r a r y except that an attempt was made to s e l e c t shapes whose boundary curvature functions represented a reasonably wide v a r i a t i o n i n complexity and frequency content. T h i r t y test shapes were used i n a l l and f i f t e e n representative examples are provided i n F i g . 4.2.1, each with i t s corresponding boundary curvature function beneath i t . The s c a l i n g of the curvature functions was a r b i t r a r i l y chosen f o r p r e s e n t a t i o n a l c l a r i t y . The t e s t shapes were constructed from synthesized curvature functions. The synthesis method varied. Some were generated by simply adding several sine and cosine harmonics i n the arc length domain (e.g. c, f, g, h, 1). Others were generated by adding rectangular (Walsh) functions i n the arc length domain (e,i) and s t i l l others were obtained from sketched figures i n the manner of the al p h a b e t i c a l characters of Chapter three except that a lower r e s o l u t i o n array was used (100 x 100). The terms " E R R O R 2 " and "Reconstructed Boundary Domain E r r o r " w i l l be used interchangably f o r the er r o r of equation 4.1.10. S i m i l a r l y , the terms "ERROR^" and "Curvature Domain E r r o r " w i l l be used interchangably to r e f e r to the er r o r of equation 4.1.1. A B C D VtoAAMAMWtf w m W H W V t v ^ r V ^ M f l v w ^ v w ^ w l ^ F i g . 4.2.1 F i f t e e n of the t h i r t y test shapes used i n the assessment of the curvature measurement methods and t h e i r corresponding curvature functions. V e r t i c a l s c a l i n g of the curvature functions was a r b i t r a r i l y s e l e c t e d f o r presentational c l a r i t y . Examples of the l a t t e r method are (a, b, d, j , k, n, 0). These curvature functions and corresponding reconstructed boundaries formed the set of o r i g i n a l functions, i . e . , K (s.) and R (s.) = i x (s.) + i y ( s . ) , 6 ' ' o x o x o x J •'o 1 i = 1, T, of equations 4.1.1 and 4.1.9. The performance of the various smoothing techniques as assessed by the two e r r o r c r i t e r i a depends upon the r e s o l u t i o n of the array used i n the quantization of the test shapes. To i l l u s t r a t e the degree of t h i s dependence, each te s t shape was quantized onto arrays of three d i f f e r e n t r e s o l u t i o n s . As with the quantization noise study, the array r e s o l u t i o n for each shape was v a r i e d so that the period of the quantized boundary equalled a s p e c i f i e d value as measured using algorithm for three d i f f e r e n t s p e c i f i e d periods. The average array resolutions were approximately 25 x 25, 37 x 37 and 50 x 50 and the periods were 200, 150 and 100 + 2 units.. F i g . 4.2.2 shows f i v e of the t e s t shapes a f t e r quantization at the three array size's . 4.3 The Slope Approximation Approach to the Smoothing of Curvature Functions In the approaches to curvature or tangent angle measurement on quantized shapes to be found i n the l i t e r a t u r e , most accomplish the smoothing of those functions by smoothing the boundary functions (x(s):y(s)) of the quantized shapes before curvature e x t r a c t i o n . For example, Masnikosa (11) proposes the e x t r a c t i o n of the d i s c r e t e boundary functions x(s_^) and y(s^) from the quantized shapes, averaging or f i l t e r i n g over several points i n each function to smooth i t , and then the a p p l i c a t i o n of equation 2.1.4 to obtain curvature. Ledley (15) finds smoothed tangent vectors to the quantized boundaries by averaging over the boundary points and then extracts curvature by recording the change i n tangent angle around the shape perimeter. The U n i v e r s i t y of Ohio group, B r i l l (22, 23), C o s g r i f f (20), Raudseps (21) and F r i t z s c h e (19) use a s i m i l a r procedure i n the measurement of t h e i r "AVL" or "angle versus length" function. Although the approaches of these authors d i f f e r i n d e t a i l , each seeks an approximation to the o r i g i n a l curvature or tangent angle function by smoothing the boundary functions of the quantized shapes, i . e . x(s^) and y(s^) , i = 1, T, before the a p p l i c a t i o n of the formulas f o r curvature e x t r a c t i o n . These methods are r e f e r r e d to as slope approximation methods of curvature or tangent angle measurement. To inve s t i g a t e various properties of these approaches to the problem of curvature function smoothing, a representative slope approximation method was formulated and tested as follows. From each quantized shape, the two boundary functions x(s^) and y(s_^) , i = 1, T were extracted using algorithm 1 of Chapter three. Each function was then passed through a d i g i t a l low-pass f i l t e r , the impulse response of the f i l t e r being given by: h(s) = ) A ' (4.3.1) ^ 0 j |s| ^ A s= arc length i . e . , a t r i a n g u l a r impulse response. The f i l t e r e d boundary functions were then used to c a l c u l a t e curvature according to equations 2.2.18 and 2.2.19. For each quantized shape, the slope approximation method of smoothing was applied at eleven d i f f e r e n t degrees of smoothing ( i . e . eleven d i f f e r e n t values of A i n equation 4.3.1). For each degree of smoothing, the two values of the e r r o r c r i t e r i a , ERROR^ or "curvature domain e r r o r " and ERR0R« or "reconstructed boundary domain e r r o r " were computed. As mentioned i n Sec. 3.6, the errors were then p l o t t e d versus the estimated bandwidth of the smoothed curvature functions. Estimates of the curvature function bandwidth for a given degree of smoothing were made from frequency attenuation p l o t s obtained as follows. Let represent the magnitude of the nth frequency component of the basic curvature function corresponding to a given quantized shape and l e t U g n represent the magnitude of the nth frequency component of the smoothed curvature function. Then the frequency attenuation curves were obtained by p l o t t i n g the quantity: U. -U ~* S n , (4.3.2) An versus the quantity "log(n/T)" where T represents the function period i n units of the sampling distance and n, the frequency component number which ranges between 1 and T/2. F i g . 4.3.1 shows t y p i c a l frequency attenuation p l o t s for the slope approximation method at three degrees of smoothing. As can be seen, although l i n e a r f i l t e r i n g was used i n the x(s^) :y(s_^) domain, the r e s u l t i n g operation i n the curvature domain i s highly non-linear. From averages of frequency attenuation curves l i k e those of F i g . 4.3.1, estimates of the approximate curvature domain bandwidth for a given amount of x(s^):y(s_^) domain smoothing were obtained by f i n d i n g the frequency at which the average attenuation was -.5. The choice of the t r i a n g u l a r impulse response f o r the x ( s ^ ) : yCs^) domain f i l t e r was a r b i t r a r y . Changing the form of th i s impulse response was found to a f f e c t the average high frequency attenuation r o l l - o f f "steepness" i n the curvature domain i n a manner s i m i l a r to l i n e a r t r a n s f e r function behaviour. 85 log (n/T) F i g . 4.3.1 Three sample frequency attenuation curves for the slope approximation approach to smoothing the basic curvature functions. For each of the three average array s i z e s and for each test shape, the slope approximation method was used i n the e x t r a c t i o n of curvature functions at eleven d i f f e r e n t degrees of x(s^):y(s^) domain smoothing. The average errors f or the t h i r t y t e s t shapes for each quantized period are shown i n F i g . 4.3.2, p l o t t e d versus the r e c i p r o c a l _1 of the curvature domain bandwidth i n (cycles per U.S.B.) . Both average ERROR^ (curvature domain error) and average ERRC^ (reconstructed boundary domain error) values are shown f o r each period length. 1 — ' — I — ' — I 1 I ' I 1 I ' I 1 I — ' 0.0 8.0 16.0 24.0 32.0 40.0 48.0 56.0 Reciprocal of Absolute Bandwidth ( C./y $ Q j-1 F i g . 4.3.2, "Curvature Domain" and "Reconstructed Boundary Domain" errors averaged over t h i r t y t e s t shapes for each of eleven d i f f e r e n t degrees of x(s):y(s) domain f i l t e r i n g and for each array r e s o l u t i o n , p l o t t e d versus the "Reciprocal of Absolute Bandwidth" i n cycles per unit sampling distance. As described i n Sec. 3 . 2 , both the curvature domain err o r (ERROR^) and the reconstructed boundary domain e r r o r (ERRQ^) were designed to approach unity i n the l i m i t of zero bandwidth. The l e f t most point on each of the graphs of F i g . 4 . 3 . 2 . corresponds to the b a s i c curvature function, obtained using no x(s):y(s) domain f i l t e r i n g , and has a band-width, l i m i t e d by the sampling "rate", of .5 cycles per unit sampling distance i n a l l cases. In t h i s u n f i l t e r e d case, the curvature domain er r o r increases with increasing array r e s o l u t i o n , i n apparent contradiction to what would be expected. This phenomenon arises from the fact that the basic curvature functions consist s o l e l y of impulses of height + T T / 2 or 0 radians per unit of arc length, regardless of the period (T) of the function as was shown i n Chapter three. In the computation of e r r o r s , the o r i g i n a l curvature functions were normalized to the same period as those for the quantized shapes and hence, for the shorter periods, the o r i g i n a l curvature function amplitudes were la r g e r than f o r the longer period functions. This can be appreciated with reference to the theory of Sec. 2 . 2 , equations 2 . 2.15 and 2 . 2.16. Therefore, the shorter the period, the smaller the distance between the impulse areas +77 / 2 and the average amplitude of the o r i g i n a l functions and hence the smaller the mean square e r r o r . As l i g h t x(s^):y(s^) domain f i l t e r i n g i s applied, t h i s s i t u a t i o n however i s quickly reversed and the curvature domain errors decrease r a p i d l y to a minimum value due to the removal of the high frequency noise depicted i n F i g . 3^.3.2 of the quantization noise study. At the minimum e r r o r point, the curvature domain e r r o r varies i n v e r s e l y with array or g r i d r e s o l u t i o n as one would expect, although the differences are not great for the three array resolutions shown because of the r e l a t i v e l y high amounts of quantization noise s t i l l present on the curvature functions. It i s reassuring to compare the minimum e r r o r bandwidth from F i g . 4.3.2 with the p l o t s of F i g . 3.3.5 (1). Although d i f f e r e n t test shapes were used f o r the two studies, the average complexity of the shapes are comparable and the minimum erro r bandwidth of F i g . 4.3.2 which i s approximately .2 cycles per unit of the sampling distance, coincides with the approximate l i m i t of the usable bandwidth depicted i n the plots of F i g . 3.3.5. I t would appear therefore, that the minimum er r o r point marks the frequency at which the extraneous quantization noise has been removed and attenuation of meaningful s i g n a l components begins. F i g . 4.3.3 shows the r e s u l t s of the a p p l i c a t i o n of the slope approximation smoothing method i n the measurement of the curvature of the boundaries of the f i f t e e n quantized shapesof F i g . 4.2.2. The amount of x(s^):y(s^) domain f i l t e r i n g applied i n each case was such as to coincide with the minimum e r r o r point on the curvature domain err o r curves for each shape considered i n d i v i d u a l l y . In F i g . 4.3.3, both the reconstructed boundaries and r e s u l t i n g curvature functions are shown and the corresponding e r r o r and r e c i p r o c a l of bandwidth values are provided i n Table 4.3.1. As can be seen, the amount of quantization noise present i n most cases i s quite l a r g e , r e s u l t i n g i n large values f o r ERROR^. As further smoothing i s applied, the curvature domain errors begin to increase, the s i z e of e r r o r varying i n v e r s e l y with array r e s o l u t i and the e r r o r increase being due to loss of s i g n a l d e t a i l . To appreciate t h i s phenomenon, the curves and functions of F i g . 4.3.4 are provided. Again, the e r r o r and r e c i p r o c a l of bandwidth values are provided i n C D E F i g . 4.3.3 The res u l t s of the a p p l i c a t i o n of the slope approximation method to the f i v e quantized shapes at the three array resolutions of F i g . 4.2,2. The curvature functions and corresponding reconstructed boundary curves were obtained at the minimum ERROR^ bandwidth values i n a l l cases. oo VO Reciprocal Figure ERROR1 ERROR^ ^ l u t e Bandwidth 3.65 4.44 3.85 3.19 2.04 4.84 5.84 5.38 4.33 2.65 7.28 8.90 8.03 6.31 4.21 Table 4.3.1 - The curvature domain err o r values (ERROR^), the reconstructed boundary domain errors (ERROR-)y the r e c i p r o c a l of absolute -1 bandwidth values (C./U.S.D.) and the r e c i p r o c a l , of harmonic bandwidth values for the f i f t e e n shapes and functions of F i g . 4.3.3. The bandwidths i n a l l cases were such as to y i e l d minimum ERROR values i n a l l cases. Table 4.3.2. In F i g . 4.3.4, three of the o r i g i n a l test shapes are shown at f i v e degrees of f i l t e r i n g . At the l e f t are the u n f i l t e r e d or b a s i c curvature functions and the r e s u l t s of successively decreasing bandwidth are shewn to the r i g h t . I t has been demonstrated i n Chapter three that an o v e r a l l e f f e c t of e x t r a c t i n g curvature from quantized boundaries i s to increase the amount of quantization noise generally and to emphasize the Reciprocal of Harmonic Bandwidth (xlOO) a .222 .008 7.30 b .365 .015 8.88 c .685 .159 7.70 d .560 .013 6.38 e .791 .121 4.08 f .283 .024 7.25 g .516 .021 8.83 h .690 .218 8.07 i .621 .066 6.50 3 .800 .233 3.98 k .398 .063 7.28 1 .658 .045 8.90 m .710 .281 8.03 n .653 .095 6.31 6 .825 .295 4.21 F i g . 4.3.4 The res u l t s of the a p p l i c a t i o n of the slope approximation method to three of the t e s t shapes quantized at an average array r e s o l u t i o n of 37x37, at f i v e degrees of x(s):y(s) domain f i l t e r i n g . 92 Figure E r r o r ^ E r r o r ^ Reciprocal of Absolute Bandwidth Reciprocal of Harmoni c Bandwidth (xlOO) a .866 .165 2.00 1.33 b .691 .127 5.63 3.76 c .753 .142 9.37 6.25 d .890 .257 25.61 L 17.40 e .931 .579 42.51 28.40 f .851 .159 2.00 1.33 g .671 .101 5.63 3.76 h .678 .125 9.37 6.25 i .849 .145 25.61 17.40 j .938 .253 42.51 28.40 k .878 .141 2.00 1.33 1 .573 .070 5.63 3.76 m .399 .040 9.37 6.25 n .475 .090 25.61 17.40 0 .625 .175 42.51 28.40 Table 4.3.2 - The curvature domain e r r o r values, (ERROR^), the reconstructed boundary domain errors (ERROR^), the r e c i p r o c a l of absolute bandwidth Values (C./U.S.D.) and the r e c i p r o c a l of harmonic bandwidth values f o r the f i f t e e n shapes and functions of F i g . 4.3.4. high frequency components of both the signal and the quantization noise in the curvature function. Because of these effects, the curvature domain error curves are largely dominated by the quantization noise on the high frequency components and the resulting errors are relatively large. When the two-dimensional boundary curves are geometrically reconstructed from the curvature functions according to the equations of Sec. 2.25the opposite effect occurs, reducing the high frequency quantization noise, and the reconstructed boundary domain errors are largely dominated by the effects of the smoothing on the low frequency curvature function components. Hence, these errors are generally much lower than the curvature domain errors as can be seen in Fig. 4.3.2. As light xCs^ryCs^) domain f i l t e r i n g i s applied, the reconstructed boundary domain error (ERROR^) decreases s l i g h t l y with the removal of the high frequency quantization noise but this effect i s considerably less than that observed in the ERROR^ curves. The effect of varying array resolution i s much more noticeable i n the ERRORp curves than in the ERROR^ curves, being almost directly proportional in the former for light f i l t e r i n g . Hence the reconstructed boundary domain error i s the much more sensitive of the two error c r i t e r i a i n terms of reflecting "signal" f i d e l i t y . It i s interesting to note that the amount of x(s^):y(s^) domain f i l t e r i n g required to produce a minimum error in the average ERROR^ and ERROR^ curves of Fig. 4.3.2 is vir t u a l l y independent of the array size used in the quantization. This fact was found to be consis-tently true for individual shapes as well as the average, as can be seen i n the minimum e r r o r r e c i p r o c a l of bandwidth values quoted i n Table 4.3.1. However, the minimum err o r bandwidth does Vary with the complexity of the shape under consideration, being l a r g e r i n general f o r the more complex shapes. <; That the minimum e r r o r bandwidth i s l a r g e l y independent of array s i z e i s also consistent with the e plo t s of F i g . 3.3.5 which in d i c a t e that the maximum usable bandwidth i n cycles per unit sampling distance i s l a r g e l y independent of array s i z e . This fact i s also demonstrated by the t h e o r e t i c a l Z' curves since the value of the "3" n parameter does not change much for the same contour t r a c i n g algorithm at d i f f e r e n t array s i z e s . Because of the wide range of shape complexity considered, the variance of the average e r r o r values quoted i n Table 4.3.1 i s quite large. The e r r o r values, l i k e the r e c i p r o c a l of bandwidth values, are dependent on shape complexity and are la r g e r f o r the more complex shapes. The amount of d e t a i l representable i n a figu r e i s more c l o s e l y r e l a t e d to the harmonic bandwidth of the curvature function i n cycles per period (T), than i t i s to the absolute bandwidth i n cycles per sampling u n i t . That i s , the d e t a i l i s r e l a t e d to the number of high order frequency harmonics of the period T which are present i n the curva-ture function. Therefore, the e r r o r values of F i g . 4.3.2 are shown p l o t t e d versus the r e c i p r o c a l of harmonic bandwidth (xlOO) values of the curvature measurement method i n F i g . 4.3.5. The harmonic bandwidth values corresponding to each e r r o r value are e a s i l y obtained from the knowledge of the bandwidth i n cycles per sampling unit and the curvature function period (T) i n sample u n i t s . The curves of F i g . 4.3.5 reveal f u r t h e r i n t e r e s t i n g aspects of the behaviour of the two e r r o r types. For the 8.0 12.0 16.0 20.0 24.0 28.0 Reciprocal of Harmonic Bandwidth (x100) "Curvature Domain" and "Reconstructed Boundary Domain" errors averaged over t h i r t y t e s t shapes for each of eleven d i f f e r e n t degrees of .smoothing and f o r each average array r e s o l u t i o n , p l o t t e d versus the "Reciprocal of Harmonic Bandwidth" (xlOO). curvature domain e r r o r s , i n the l i g h t or u n f i l t e r e d region, although the actual e r r o r values do not vary s i g n i f i c a n t l y f or a f i x e d amount of smoothing, the harmonic bandwidth decreases with decreasing array r e s o l u t i o n , representing a greater loss i n representable s i g n a l d e t a i l . Rather unexpectedly however, at high degrees of f i l t e r i n g , the curvature domain e r r o r , for a given harmonic bandwidth, tends to increase with i n c r e a s i n g array r e s o l u t i o n . This phenomenon occurs because of the d i s c r e t e nature of the e r r o r c r i t e r i a (Sec. 4.1). Before computation of the e r r o r s , the o r i g i n a l curvature functions were normalized to the appropriate length and sampled i n preparation for the a p p l i c a t i o n of the d i s c r e t e e r r o r c r i t e r i a of equations 4.1.1 and 4.1.9. The r e s u l t of the sampling i s to reduce the harmonic bandwidth of the o r i g i n a l s i g n a l s by an amount which varies with the period T. Hence, the shorter period functions are compared to o r i g i n a l functions of lower harmonic content than are the longer ones. Since the approximate functions a l l have the same harmonic bandwidth, the errors are smaller for the shorter period functions. This e f f e c t i s not as noticeable i n the reconstructed boundary domain, s i n c e , as previously pointed out, these errors are l a r g e l y dominated by the low frequency harmonics of the functions involved. In Tables 4.3.1 and 4.3.2, the r e c i p r o c a l of harmonic bandwidth values are provided for each shape of F i g s . 4.3.3. and 4.3.4. 4.4 Some Conclusions on the Slope Approximation Approach to Curvature Measurement The slope approximation method of curvature smoothing i s mathematically analogous to bandpass f i l t e r i n g of a frequency modulated c a r r i e r before demodulation to extract the modulation information or 9 7 "message". In t h i s case, curvature corresponds to the message. In the curvature domain, t h i s approach to smoothing represents a non-l i n e a r operation on the basic curvature function. The high-frequency attenuation c h a r a c t e r i s t i c s of the non-linear smoothing of the b a s i c curvature function are not unlike those of a low-pass f i l t e r i n the curvature domain i n that high frequencies are on the average attenuated. Low frequencies however can be severely d i s t o r t e d as was seen i n F i g . 4.3.1. In the following chapter, the area operator approach to smoothing of curvature functions i s studied. The r e l a t i o n s h i p between area operators and p h y s i o l o g i c a l "receptive f i e l d s " i s f i r s t examined and then the smoothing c h a r a c t e r i s t i c s of area operators are studied using the two e r r o r c r i t e r i a of t h i s chapter. F i n a l l y , the curvature domain f i l t e r i n g methods are studied and the three approaches to smoothing of curvature functions are compared. 5. AREA OPERATORS AND CURVATURE MEASUREMENT For on-line pattern recognition applications where speed i s a primary consideration, the slope approximation method of curvature smoothing i s i m p r a c t i c a l because of the complexity of the computations involved. This f a c t has stimulated the development of some simpler methods of curvature e x t r a c t i o n and smoothing. For example, Ledley (15) "approximates the curvature function by assuming that the tangent of the tangent angle i s equal to the tangent angle i t s e l f . From the examples of the previous s e c t i o n , i t can be seen that t h i s assumption would only be v a l i d where severe smoothing has been applied. This method s t i l l involves most of the complex c a l c u l a t i o n s of the slope approximation mathod as w e l l . Kasvand (25,26) at NRC, has proposed the use of an hexagonal operator array which can be incorporated i n t o a two-dimensional p a r a l l e l scheme and which can be used to obtain a function which i s non - l i n e a r l y r e l a t e d to curvature. Connor (27) has also studied the use of area operators to obtain a function r e l a t e d to curvature. Area operators have an advantage over the slope approximation approach since the complicated computation of curvature measurement and smoothing can be approximated instantaneously. The one-dimensional curvature function can then be extracted by measuring the operator output at successive boundary points or a l t e r n a t i v e l y , further processing can be performed on the two-dimensional output array. I t w i l l also be seen i n t h i s chapter, that a two-dimensional array of area operators can be constructed to respond only at boundary points of the input shapes. Hence the problem of i s o l a t i n g boundary points can be solved instantaneously as w e l l . A second advantage of the area operator approach i s that once a s p e c i f i e d boundary point i s located, an area operator can be used to extract and smooth the boundary curvature at the point without the necessity of l o c a l i z e d boundary t r a c i n g on e i t h e r side of the s p e c i f i e d point. Hence an area operator can be used to advantage i n s i t u a t i o n s where i s o l a t e d .points of boundary curvature are to be extracted. Kasvand (25,26) has exploited this property of area operators. This chapter i s devoted to a study of the use of area operators for the i s o l a t i o n of boundary points and the extraction and smoothing of the curvature at those points. The chapter begins with a discussion of the p h y s i o l o g i c a l o r i g i n or basis of area operators; - the receptive f i e l d s of the r e t i n a s of l i v i n g organisms, and some simple experiments are performed using continuous or analog models of receptive f i e l d s and area operators. Some problems r e l a t i n g to the design of d i s c r e t e area operators are then discussed and the use of area operators to measure the boundary curvature of quantized shapes i s studied. F i n a l l y , the use of curvature domain f i l t e r i n g methods for the smoothing of the b a s i c curvature functions i s investigated, and the three approaches to the smoothing problem are compared using the two e r r o r c r i t e r i a of Sec. 4.1. 5.1 P h y s i o l o g i c a l Basis of Area Operators Much of the use of area operators for pattern recognition and p i c t u r e processing applications has been stimulated by t h e i r close analogy with the structure of the v i s u a l systems of l i v i n g organisms. Ever since the work of Ernst Mach (49), f i r s t published over 100 years ago, i t has been known that the neural networks comprising 100 the v i s u a l systems of the higher mammals, in c l u d i n g man, possess the a b i l i t y to accentuate i n t e n s i t y and colour boundaries i n images f a l l i n g on the r e t i n a s . Recently, (since about 1930), through the use o f micro-electrode sensing techniques which enable the recording of the a c t i v i t y of s i n g l e neurons or nerve c e l l s , p h y s i o l o g i s t s have been able to study the d e t a i l e d structure of these networks. As a r e s u l t of this work, a ' f a i r l y c l e a r p i c t u r e has emerged as to how boundary contrast and shape detection i s accomplished, at l e a s t at the r e t i n a l l e v e l . The general nature of th i s organization i s s i m i l a r i n a l l of the higher mammals and can be described as follows. Light energy, upon entering the eye, excites photoreceptor neurons (rods and/or cones) i n the r e t i n a at the back of the eye, causing these neurons to send v o l l e y s of nerve impulses along t h e i r respective output f i b r e s or axons. The axons unite with layers of interconnected b i p o l a r and h o r i z o n t a l c e l l s which i n turn send axons to large ganglion c e l l s . It i s the axons of these ganglion c e l l s that form the f i b r e s of the op t i c t r a c t . I t i s found that the nerve impulse frequency i n the axon of any one ganglion c e l l i s influenced only by photoreceptor neurons i n a high l y s p e c i f i c region of the r e t i n a and the receptors within t h i s region comprise the "receptive f i e l d " of the ganglion c e l l . Furthermore, the receptors within a given receptive f i e l d can serve to increase the ganglion c e l l axon f i r i n g frequency (excitatory receptors) or decrease i t ( i n h i b i t o r y receptors). The e x c i t a t o r y - i n h i b i t o r y e f f e c t can take place at the onset of i l l u m i n a t i o n Con-type receptors) or at the o f f s e t of i l l u m i n a t i o n (off-type receptors). The s e n s i t i v i t y of the gangion c e l l axon f i r i n g frequency to i n d i v i d u a l receptors w i t h i n i t s receptive f i e l d v a ries with the receptor's p o s i t i o n i n the receptive f i e l d and hence a s e n s i t i v i t y p r o f i l e or "weighting 101 p r o f i l e " can be described for a receptive f i e l d , s p e c i f y i n g the magnitude and sign (excitatory (+) or i n h i b i t o r y (-)) of the s e n s i t i v i t y of the ganglion c e l l f i r i n g to receptors at any l o c a t i o n i n the receptive f i e l d . Receptive f i e l d s are characterized by the form of t h e i r s e n s i t i v i t y p r o f i l e s . A large v a r i e t y of receptive f i e l d s are found i n the retinas of l i v i n g organisms (39-49, 60-71). However, i n most of the retinas studied, one p a r t i c u l a r type seems to predominate; - the concentric "on-type" center and " o f f - t y p e " surround and i t s complement, the " o f f -type" center and "on-type" surround. The s e n s i t i v i t y p r o f i l e for t h i s type of f i e l d consists o f a c i r c u l a r center of e x c i t a t o r y ( i n h i b i t o r y ) neurons and a annular surround of i n h i b i t o r y (excitatory) neurons.. It has been found that the retinas of the cat (41-44), the monkey (66) and man (.72-74) are composed e x c l u s i v e l y of v a r i a t i o n s of t h i s type of f i e l d . The concentric on-off f i e l d s of the cat's r e t i n a have been the subject of considerable i n v e s t i g a t i o n i n recent years and much q u a l i t a -t i v e and q u a n t i t a t i v e data have been published d e s c r i b i n g t h e i r charac-t e r i s t i c s . Rodieck (44) has proposed a mathematical d e s c r i p t i o n of the s e n s i t i v i t y behaviour of an i d e a l receptive f i e l d based on h i s study of cat r e t i n a l ganglion c e l l s . This d e s c r i p t i o n has been l a r g e l y substantiated by the findings of others, p a r t i c u l a r l y Enroth-Cugell and Cleland (41,42), although both groups emphatically point out that the d e s c r i p t i o n i s , at best, a f i r s t order approximation to a highly complex and non-linear process. An i d e a l "on-off" receptive f i e l d operation can be described with reference to F i g . 5.1.1., reproduced from (42). F i g . 5.1.1 (a) represents the two concentric regions of the receptive f i e l d as they influence the f i r i n g of the gangion c e l l (G). The center (C) has an F i g . 5.1.1 Receptive f i e l d organization (a) and s e n s i t i v i t y p r o f i l e (b) f o r an i d e a l receptive f i e l d . Impulse v o l l e y s from the c e n t r a l region (C+) have an ex c i t a t o r y (+) e f f e c t on the ganglion c e l l (G) i f the surround region v o l l e y s (S+). have an i n h i b i t o r y (-) e f f e c t and vice versa. The s e n s i -t i v i t y p r o f i l e s describe the r e l a t i v e influence of a photoreceptor on the ganglion c e l l f i r i n g frequency according to i t s distance from the receptive f i e l d center ( r ) . e x c i t a t o r y (+) e f f e c t i f the annular surround (S) has an i n h i b i t o r y (-) e f f e c t and vice versa. F i g . 5.1.1 (b) shows the s e n s i t i v i t y p r o f i l e s f o r the ex c i t a t o r y (center) portion of the f i e l d and the i n h i b i t o r y portion (shown extending over the e n t i r e f i e l d ) . Mathematically: 2 W (r) = K EXP (-£5) C 2r ° (5.1.1) 2 W (r) = K EXP(- ~ ^ r ) S S 2 r 2 s and the s e n s i t i v i t y p r o f i l e over the whole f i e l d i s given by: W(r) = W c(r) - W ( r ) , (5.1.2) where r represents the distance from the center of the f i e l d along a 2 2 radius. The r a t i o K r /K r has been estimated from q u a n t i t a t i v e data s s c c for s everal f i e l d s i n the cat's r e t i n a and values close to unity were observed i n most cases. This i s substantiated by the fact that the response to uniform i l l u m i n a t i o n i s weak or non-existent (41, 42, 44). T y p i c a l r a t i o s of the parameters r / r were 3.0 to 5.0, giving an idea s c of the r a t i o of the surround diameter to the center diameter. The response, R(x,y) of the i d e a l receptive f i e l d to an i n t e n s i t y d i s t r i b u t i o n , I ( x , y ) , i s given by the equation: O O -R(*,y) " 2 L I(x*-x,y'-y)W(x\y')dx'dy' (5.1.3) i . e . , the convolution of the f i e l d s e n s i t i v t y or weighting function, expressed here i n rectangular coordinates, over the i n t e n s i t y d i s t r i b u t i o n (42). A l t e r n a t i v e l y , one can think of equation 5.1.3 as representing the response of an i n f i n i t e r e t i n a of overlapping receptive f i e l d s operating on the i n t e n s i t y d i s t r i b u t i o n . The response of the i d e a l receptive f i e l d to an i n t e n s i t y boundary i s shown i n F i g . 5.1.2. F i g . 5.1.2 was constructed as follows. An i n t e n s i t y d i s t r i b u t i o n c o n s i s t i n g of a s i n g l e s t r a i g h t i n t e n s i t y boundary with an i n t e n s i t y of 1 " u n i t " on one side of the boundary and zero on the other was used i n equation 5.1.3. That i s Hx,y) « ) 0, x < x.; a l l y < 1 (5.1.4) J 1, x >, x ^ a l l y The parameters of the s e n s i t i v i t y p r o f i l e s of equation 5.1.1 were chosen so that : 104 Fig. 5.1.2 The response profile of the ideal receptive f i e l d to a straight edge of intensity. The curve was obtained by moving the receptive f i e l d along a line perpendicular to the intensity edge recording the response at each point on the way. Distance of the receptive f i e l d center from the intensity edge is in units of the receptive f i e l d parameter r (see equation 5.1.2). The ratio r IT = 4.0. S s c L> L> Wc(x,y)dxdy = . £ Wg(x,y)dxdy = 1.0, (5.1.5) and the ratio r ,/r was arb i t r a r i l y set at 4.0. The curve of Fig. 5.1.2 s c was obtained by plotting the response R(x,y) versus distance from the boundary along a line parallel to the axis. The response is zero except in the v i c i n i t y of the intensity boundary;- a phenomenon which has been experimentally v e r i f i e d i n the cat receptive f i e l d s (42). This a b i l i t y of the concentric receptive f i e l d or "area operator" as i t i s sometimes c a l l e d , to accentuate regions i n a two-dimensional scene where i n t e n s i t y i s changing, has been the subject of much i n t e r e s t i n pattern recognition work (12, 50, 51). By a l t e r i n g the s e n s i t i v i t y p r o f i l e s i n various ways, area operators have been designed to be s e n s i t i v e to i n t e n s i t y boundaries of,-specific shape and o r i e n t a t i o n and at l e a s t two authors (12, 50) have proposed feature e x t r a c t i o n schemes using only area operators of t h i s kind. Many of these s p e c i f i c area operators have analogs'in the higher v i s u a l centers of l i v i n g organisms (49, 50, 52). It i s interesting to note i n passing, that as many of the receptive f i e l d s e n s i t i v i t y p r o f i l e s found i n (49, 50, 52) are made progressively smaller, the l i m i t i n g cases form a class of d i f f e r e n t i a l operators which are commonly employed i n p i c t u r e processing problems to eliminate noise and accentuate regions of i n t e r e s t (61-63). 5.2 Area Operators and St i m u l i of Constant Curvature An a d d i t i o n a l property of the response of the i d e a l receptive f i e l d model of F i g . 5.1.1 to i n t e n s i t y boundaries, which has been l a r g e l y overlooked i n pattern recognition work, i s i t s s e n s i t i v i t y to changes i n the curvature of those i n t e n s i t y boundaries*. The r e s u l t s of,a simple experiment serve to i l l u s t r a t e the nature of t h i s s e n s i t i v i t y Ten s t i m u l i were presented i n turn to a simulated i d e a l recep-t i v e f i e l d , the s t i m u l i c o n s i s t i n g of s i n g l e c i r c u l a r i l l u m i n a t e d regions each of a d i f f e r e n t radius, superimposed on a uniformly dark background and centered over the o r i g i n of a rectangular co-ordinate system. Exceptions to t h i s are the work of Connor (27) and Kasvand (25,26). In terms of equation 5.1.3, (1.0 x 2+y 2 s R2 I(x,y) = } (5.2.1) ( 0 x 2+y 2 > R2 The receptive f i e l d s e n s i t i v i t y p r o f i l e of equations 5.1.1 and 5.1.2 was used with r =1.0 u n i t s , r = .25 units and K and K s ' c s r were such that the i n d i v i d u a l responses of the center and surround regions on uniform i l l u m i n a t i o n were unity. The ten s t i m u l i r a d i i were 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.5, 1.0, .75 and .5 un i t s . F i g . 5.2.1 shows the ten response curves, one f o r each stimulus, obtained by p l o t t i n g the response, R(x,y) of equation 5.1.3, as a function of distance along a l i n e p a r a l l e l to the x-axis, s t a r t i n g with the receptive f i e l d centered over the stimulus at the o r i g i n . The b a s i c unit of distance i n F i g . 5.2.1 i s the receptive f i e l d parameter r , (standard deviation s of the Gaussian s e n s i t i v i t y p r o f i l e ) . Referring to F i g . 5.2.1, for large s t i m u l i ( r a d i i equal to 3 to 5 times r g ) , the response curves are s i m i l a r to that of the s t r a i g h t edge ( F i g . 5.1.2) except that the non-zero portion i s s h i f t e d v e r t i c a l l y s l i g h t l y , by an amount which increases as the stimulus radius decreases. The curvature of each stimulus boundary i n the experiment of F i g . 5.2.1 i s constant, equal to the r e c i p r o c a l of the radius. The r e l a t i o n s h i p between the curvature of the c i r c u l a r s t i m u l i and the 0 amount of the v e r t i c a l s h i f t of the response was explored by repeating the experiment of F i g . 5.2.1 for stimulus curvature ranging from zero ( s t r a i g h t edge) up to values exceeding the curvature of the c e n t r a l region of the receptive f i e l d ( a r b i t r a r i l y defined to be l / r c ) , f o r both p o s i t i v e curvature and negative (negative curvature corresponded 1 0, 2.2 4.4 6.6 a.a 11.0 Distance From Stimulus Center (Units of rs ) F i g . 5.2.1 The response of the i d e a l receptive f i e l d to c i r c u l a r s t i m u l i of d i f f e r e n t r a d i i . The stimulus r a d i i , shown above each p r o f i l e curve, are i n units of the receptive f i e l d parameter r . The r a t i o r /r =4.0. The i n d i v i d u a l curves s s c were obtained by moving the receptive f i e l d along a diameter of the c i r c u l a r stimuli, s t a r t i n g at the center, recording the response at each point along the way. to dark c i r c l e s of i n t e n s i t y zero on a l i g h t background of i n t e n s i t y 1). For each stimulus, the receptive f i e l d was located with i t s centroid exactly on the i n t e n s i t y boundary of the s t i m u l i . For the s t r a i g h t edge, the response at the boundary i s zero and for the c i r c u l a r boundaries, the response deviates from zero by an amount equal to the v e r t i c a l s h i f t of the t o t a l response curve ( F i g . 5.2.1). This value was p l o t t e d versus the curvature of the i n t e n s i t y boundary and the r e s u l t s are shown i n F i g . 5.2.2. The experiment was repeated for receptive f i e l d s of three d i f f e r e n t r a d i i , the r a t i o r / r being held at 4.0. 5 s c b Curve A i n F i g . 5.2.2 was p l o t t e d for a f i e l d of radius r = 1.0,curve s B for r - .7 and C for r = .4 u n i t s . The r e l a t i o n s h i p i s i n general s s non-linear but over the range of curvature between +2/r , the r e l a t i o n s h i p S i s approximately l i n e a r . In preparation for the a p p l i c a t i o n of the i d e a l receptive f i e l d as a curvature measurement device, a s i m p l i f i c a t i o n can be achieved by decreasing the c e n t r a l region radius ( r £ ) to zero, maintaining r g constant and keeping the area defined by the s e n s i t i v i t y p r o f i l e curve ( F i g . 5.1.1) constant. In the l i m i t , r ^ = 0, the c e n t r a l region p r o f i l e curve i s an impulse of unit weight* and the s e n s i t i v i t y p r o f i l e can be expressed as: W (r) = 6(r) - K g EXP(- r 2 / 2 r g ) , (5.2.1) where: 2ir oo f f K EXP(- r 2 / 2 r 2 ) dr d0 = 1. (5.2.2.) s s 0 F i g . 5.2.3 i l l u s t r a t e s the e f f e c t on the response p r o f i l e R(x,y) to an i n t e n s i t y boundary., of decreasing the width of the c e n t r a l region i n the manner j u s t described. Curve A corresponds to a value r / r =2.0, s c See L i g h t h i l l (79) f o r proof of t h i s f a c t . A B C i 1 1 1 1 1 -7.0 -4.2 -1.4 1.4 4.2 7.0 Curvature of Stimulus Boundary (Units of 1/rs) 5.2.2 The r e l a t i o n s h i p between the receptive f i e l d response centered over the boundary of a c i r c u l a r stimulus and the curvature of the boundary for receptive f i e l d s with r s = 1.0 units (A), r s = .7 units (B) and r s = .4 units (C). Distance, i n units of l / r s , r e f e r s to a value of r g = 1.0. The r a t i o r g / r c = 4.0 was held constant i n a l l cases. 110 F i g . 5.2.3 The e f f e c t on the receptive f i e l d response to a c i r c u l a r stimulus of decreasing the width of the c e n t r a l region, keeping r s constant. In A, r g / r c = 2.0; B, r s / r c = 2.5; C, r s / r c = 3.33; D, r s / r c = 4.0; and E, r s / r c = 0 0. curve B to r / r = 2.5, C to r / r =3.33, D to r s / r = 4.0 and E to the s c ' s c c impulse center. Curve E contains a d i s c o n t i n u i t y at the point corresponding to the s i t u a t i o n where the ce n t r a l impulse of the receptive f i e l d l i e s exactly at the i n t e n s i t y boundary. The receptive f i e l d with a c e n t r a l I l l region c o n s i s t i n g of an impulse of unity weight i s analogous to the area operator proposed by Connor (27) except that Connor imposed the s t i p u l a t i o n that the response was non-zero only when the c e n t r a l impulse or receptor was "excited" by a non-zero p o r t i o n of the stimulus. That i s , negative responses were set to zero. The response of the receptive f i e l d with a c e n t r a l region co n s i s t i n g of an impulse* to i n t e n s i t y boundaries of non-zero curvature i s i l l u s t r a t e d i n F i g . 5.2.4. The curves of F i g . 5.2.4. were obtained by repeating the experiment of F i g . 5.2.1 exactly except that the s e n s i t i v i t y p r o f i l e of equations 5.1.1 and 5.1.2 was replaced with that of equations 5.2.1 and 5.2.2. Again, the non-zero portion of the response curves i s s h i f t e d v e r t i c a l l y i n each case by an amount which increases with in c r e a s i n g stimulus curvature. F i g . 5.2.5 shows a p l o t of the amount of this v e r t i c a l s h i f t as a function of the curvature of the stimulus i n t e n s i t y boundary. These curves were obtained i n the manner described for those of F i g . 5.2.2 except that the weighting function of equations 5.2.1 and 5.2.2 was used. Curve A was p l o t t e d for r - 1.0, B for r = .7 and C f o r r = .4 (same as f o r F i g . 5.2.2). s s s b The i n t e n s i t y boundary response was defined as the mid point of the d i s c o n t i n u i t y i n the response p r o f i l e s of F i g . 5.2.4 i n the p l o t t i n g of the curves of F i g . 5.2.5. Again the o v e r - a l l r e l a t i o n s h i p i s non-linear but i s approximately l i n e a r over the range of curvature +2/r g. The main difference between the curves of F i g . 5.2.5 and those of F i g . 5.2.1 i s that i n the former case, the response approaches a l i m i t i n g value of .5 assymptotically as the stimulus diameter approaches zero whereas i n the l a t t e r case, the response drops o f f to approach Henceforth, the receptive f i e l d with the c e n t r a l region c o n s i s t i n g of an impulse w i l l be referred to as an "area operator" a f t e r Connor (27). 112. 2.2 Distance from Stimulus Centre (Units of r g ) F i g . 5.2.4 The response of the area operator to c i r c u l a r s t i m u l i of d i f f e r e n t r a d i i . The stimulus r a d i i , shown above each curve are i n units of the area operator parameter r . The i n d i v i d u a l curves were obtained by moving the area operator along a diameter of the c i r c u l a r s t i m u l i , s t a r t i n g at the center and recording the response at each point along the way. Curvature of Stimulus Boundary (Units of 1/pJ F i g . 5.2.5 The r e l a t i o n s h i p between the area operator response centered over the boundary of a c i r c u l a r stimulus and the curvature of the boundary for area operator parameters r s = 1.0 (A), r s = .7 (B) and r s = . 4 (C). Distance, i n units of l / r s ^ i s for r g = 1.0 i n a l l cases. zero i n the same l i m i t . In both cases, the l i n e a r region extends to values of curvature between +2/r . Hence the smaller the receptive - s r f i e l d or area operator, the wider the " l i n e a r " range. 114 5.3 The Response of the Area Operator to Impulses of Curvature. When centered over an i n t e n s i t y boundary of constant curvature i n the manner described i n Sec. 5.2, an area operator responds i n an approximately l i n e a r fashion to the curvature of the boundary over a reasonably wide range; the smaller the diameter of the operator, the wider the l i n e a r range. Some i n s i g h t i n t o the nature of the response of an area operator s i t u a t e d on i n t e n s i t y boundaries of non-constant curvature can be gained by considering the operator response to impulses of curvature. An impulse of curvature corresponds to a sharp corner i n the i n t e n s i t y boundary of a figu r e i n the plane as can be shown with reference to F i g . 5.3.1. F i g . 5.3.1(a) shows a por t i o n of a stimulus boundary c o n s i s t i n g of two s t r a i g h t edges meeting at a corner (point s= 0) , and oriented such that one edge subtends an angle of ir/12 radians and the other 11 TT/12 radians at the x-axis (angles measured counter-clockwise). F i g . 5.3.1(b) shows the angle subtended by the tangent to the boundary at the x-axis as a function of distance along the boundary from the corner (s=0). The corner r e s u l t s i n a d i s c o n t i n u i t y i n the tangent angle, the magnitude of which i s given by the change i n the tangent angle i n rounding the corner, i . e . , 5 u/6 radians. F i g . 5.3.1(c) shows a plo t of curvatureas a function of the distance along the boundary from the corner. Since curvature i s defined as the deriva-t i v e of the tangent angle function with respect to arc length, the curve of F i g . 5:3.1(c) i s the d e r i v a t i v e of 5.3.1(b), and the i n t e n s i t y corner hence represents an impulse of curvature, (the unit impulse i s defined as the de r i v a t i v e of the unit step function a f t e r Papoulis (80)), of area 5 TT/6 radians per unit of arc length. The response of the area operator to impulses of curvature was found by l o c a t i n g the operator on the boundary of " i n t e n s i t y wedges" of the type shown i n F i g . 5.3.1(a) and p l o t t i n g the operator response versus distance along the boundary of the wedge from the corner (s=0). The r e s u l t s are shown i n F i g . 5.3.2 f o r s i x wedges, describing tan g e n t i a l angle changes of TT/6, TT/3, TT/2, 2 TT/3, -^ p and 23 IT/24 radians. The corresponding response curves are shown as s o l i d l i n e s l a b e l l e d F to A r e s p e c t i v e l y . Also shown, i n dashed l i n e s , are the corresponding l i n e a r response curves, representing the curves which would be obtained, were the area operator responding l i n e a r l y to impulses of d i f f e r e n t amplitude. These l i n e a r curves were computed by f i n d i n g the area operator response to a wedge describing a very small tan g e n t i a l angle change (TT/25 radians) and m u l t i p l y i n g t h i s response by the appropriate constant i n each case. Were the operator response l i n e a r l y r e l a t e d to the impulse amplitude, the dashed and s o l i d l i n e s would coincide i n each case. As can be seen with reference to F i g . 5.3.2, the response i s approximately l i n e a r f o r wedges describing tangential angle changes up to TT/2 radians ( i . e . for impulses of curvature with areas up to TT/2 radians per unit of arc length) and for higher values, the l i n e a r i t y breaks down severely at portions of the boundary on e i t h e r side of the wedge corner. This breakdown phenomenon i s referred to as " s a t u r a t i o n " of the area operator and r e s u l t s i n the assignment of higher curvature to boundary points on e i t h e r side of the wedge corner than i s warranted i n r e a l i t y . From the r e s u l t s of F i g . 5.2.5 and 5.3.2, i t i s tempting to conclude that the area operator, as a curvature measurement device, can be modelled as a l i n e a r low-pass f i l t e r with an impulse response as shown i n F i g . 5.3.2 (.curves D, E and F) , over a reasonable range of 117 Distance from Wedge Corner (Units of rs) F i g . 5 . 3 . 2 The area operator response to impulses (wedges) of curvature of varying s i z e . Area operator response curves are shown as s o l i d l i n e s and the corresponding l i n e a r responses as dashed l i n e s . The l i n e a r curves were obtained by m u l t i -p l y i n g the area operator response to a very small impulse . . by the appropriate constant. Impulse areas are A ( 2 3 T T / 2 A ) , B C 5 T T / 6 ) , C ( 2 T T / 3 > . , D(ir / 2 ) , E ( T T / 3 ) , and F(T T / 6 ) radians per unit of arc length or distance from the impulse i n units of the area operator p r o f i l e parameter r along the boundary. curvature values. As w i l l be demonstrated i n Sec. 5.5 however, t h i s i s not true i n general. 5.4 Discrete Area Operators In the d i s c r e t e or quantized environment, a binary i n t e n s i t y d i s t r i b u t i o n i s defined over an arrayof points, a value 1 being associated with a l l points l y i n g on or within the i n t e n s i t y boundaries and a 0 with- a l l points l y i n g outside the boundary. A d i s c r e t e area operator i s also defined over an array of points by s p e c i f y i n g a weighting function which assigns a numerical value or weight to each point i n the array. To c a l c u l a t e the response of the d i s c r e t e area operator to a p a r t i c u l a r point on the input array, i t i s f i r s t assumed that the input array i s of i n f i n i t e extent^being zero everywhere except at points on or w i t h i n the i n t e n s i t y boundaries. The area operator array i s then centered over the point of i n t e r e s t on the input array thereby associating a weight with each point on the input array. The response i s defined as the sum of the products of the input array point values (0 or 1) and the corresponding operator weight. F i g . 5.4.1(b) shows an operator located over a boundary point of an input rectangular i n t e n s i t y array ( l ' s are shown as black dots, 0's are omitted). The operator response i s found by summing a l l those weights l y i n g over the black dots and i s zero f o r F i g . 5.4.1(b). C a l c u l a t i n g the area operator response i n t h i s way f o r a l l points on the input array i s the disc r e t e equivalent of the convolution operation of equation 5.1.3. Area operators can be implemented i n two ways f o r the e x t r a c t i o n and smoothing of curvature as a function of distance around a boundary. One approach i s to s e q u e n t i a l l y trace around the boundary of a quantized 0 0 0 0 0 © 9 © • © c 0 O -01 -04 -07 -04 -01 • • • e 0 0 e • 0 0 0 O o 0 9 9 0 9 0 0 -04 -26 -51 -26 -04 o o @ ® © © e © 0 0 o 0 0 0 0 @ ® @ 0 © 0 0 0 -07 -57 +244 -51 -07 o o • © © o 0 0 0 9 0 0 0 0 O o o (1) d ® • 0 9 0 0 -04 -26 -51 -26 -04 o o ® ® ® © • 9 0 0 0 0 0 0 0 • © © © 0 0 0 0 -01 -04 -07 -04 -07 0 8 0 0 0 0 0 (a) (h) © 0 0 © e © a © » • • 0 0 0 0 0 @ » © © o o o ® © S o o o ® @ © 9 © o o © ® ® • • o o © @ o © © o ®-^- ® • • o ® ® © ® © © S ® ® © © ® e © ® @ © @ © 0 © O © @ © ® © © © © © © © © 0 © o © © • © 9 « © 9 © o • © 9 0 © © © © « 0 © e e e 9 6 © 0 0 9 0 (c) F i g . 5.4.1 The di s c r e t e area operator configuration of Connor (38) shown i n (a) with associated weights calculated according to the Gaussian weighting p r o f i l e . The operator i s shown i n (b), (c) and (d) i n three p o s s i b l e boundary posi t i o n s on two possible orientations of a s t r a i g h t edge of i n t e n s i t y . shape using one of the contour t r a c i n g algorithms of Sec. 3.1. At each boundary point, the area operator i s centered over that point and i t s response i s computed i n the manner j u s t described. The second approach i s to construct a two-dimensional array of overlapping area 120 operators i n a manner described i n Appendix I I I . As w i l l be seen, such a two-dimensional array can be designed to produce a non-zero output only at boundary points and at these points, the magnitude values correspond to smoothed values of boundary curvature. Curvature as a function of arc length i s then extracted by s e q u e n t i a l l y recording the response values at points around the boundaries. The properties of d i s c r e t e versions of area operators s i m i l a r to that discussed i n Sees. 5.2 and 5.3 have been extensively i n v e s t i g a t e d by Connor (27). Following the example of Connor, a d i s c r e t e version of the area operator of Sees. 5.2 and 5.3 can be constructed by assigning the c e n t r a l impulse area to a s i n g l e array point or "receptor" and negative weights to array points surrounding the c e n t r a l receptor according to t h e i r distance from the c e n t r a l point and the p r o f i l e equations 5.2.1 and 5.2.2. F i g . 5.4.1(a) shows a d i s c r e t e area operator on a square array with the i n h i b i t o r y f i e l d negatively weighted according to the Gaussian p r o f i l e of equation 5.2.1. In assigning a weight to the c e n t r a l receptor (shown as a"+" i n F i g . 5.4.1(a)), a value must be selected so that the operator response, c a l c u l a t e d i n the manner ju s t described, i s zero whenever the c e n t r a l "receptor" i s located on a " s t r a i g h t edge" of i n t e n s i t y . This s i t u a t i o n i s shown i n F i g . 5.4.1(b). To ensure a zero response i n t h i s s i t u a t i o n , the p o s i t i v e weight associated with the c e n t r a l point of the operator array must equal the negative of the sum of a l l those weights overlying dots i n F i g . 5.4.1(b). For the weighting of F i g . 5.4.1(a), t h i s value corresponds to 244 units as shown. However, when the operator, so weighted, was applied i n the measurement of boundary curvature of sample quantized f i g u r e s , i t was found that for small operators, a bias i s introduced i n t o the response which can completely overwhelm the operator's s e n s i t i v i t y to boundary curvature. The nature of t h i s bias can be demonstrated with reference to F i g . 5.4.1(c). Here the operator i s shown s i t u a t e d on the boundary of a quantized array with a s t r a i g h t edge oriented at 45 degrees to the array a x i a l d i r e c t i o n s . Here however, the operator response i s non-zero (+31 units) and as the operator i s moved along the boundary, a p o s i t i v e bias i s assigned to each point, introducing severe d i s t o r t i o n i n t o the curvature function. I f the contour t r a c i n g algorithm employed, sele c t s adjacent boundary points by moving only i n the array a x i a l d i r e c t i o n s (that i s movements along the 45° l i n e s are not permitted), then the operator p o s i t i o n adjacent to that shown i n F i g . 5.4.1(c) would be that shown i n F i g . 5.4.1(d). In t h i s p o s i t i o n , the operator response would also be non-zero, but now negative (-79) units and as successive boundary points were encountered, the average response over the length of the s t r a i g h t edge would show a net negative bias (31-79= -48 u n i t s ) . This net response would hence be equivalent to that of a boundary with negative'curvature. This b i a s i n g problem i s d i f f i c u l t to overcome with simple contour t r a c i n g algorithms but can be overcome by averaging the operator response at d i f f e r e n t points i n the v i c i n i t y of a boundary point. This approach however, adds considerably to the complexity of a p p l i c a t i o n of area operators and i s therefore less desirable than other methods to be described. A simple way of circumventing the b i a s i n g problem i s to use a rectangular weighting p r o f i l e which assigns an equal weight to a l l points w i t h i n the operator f i e l d . This type of operator, when used with contour t r a c i n g algorithm 3 or 4, removes the bias i n the response. However, t h i s operator i s of l i m i t e d f l e x i b i l i t y since only one weighting p r o f i l e ( a l b e i t a simple one to implement) can be used without the i n t r o d u c t i o n of bias i n the response. A second disadvantage of t h i s type of operator becomes evident when i t i s to be incorporated i n t o two-dimensional array. A d i f f i c u l t y i n d e f i n i n g the l o g i c of a boundary point a r i s e s , n e c e s s i t a t i n g rather complicated l o g i c networks i n v o l v i n g the nine c e n t r a l points of the operator array. Kasyand (25, 26) has employed an hexagonal area operator array to measure the curvature of figure boundaries. When a rectangular weighting p r o f i l e i s used i n such an operator, an unbiased response i s obtained. However, when a weighting p r o f i l e other than rectangular i s used, a bias i s again introduced i n t o the response. Hexagonal arrays do have other properties which make them a t t r a c t i v e i n that the quanti-zation noise properties of an hexagonal contour t r a c i n g algorithm (algorithm 5) are very good as was demonstrated i n Chapter three-A second approach to d i s c r e t e area operator design which enables greater f l e x i b i l i t y of p r o f i l e type without the i n t r o d u c t i o n of bias i n the response can be described as follows. An operator weight p r o f i l e i s formulated which i s symmetrical, not about a point coincident with an array point, but about a point located at the centroid of any four adjacent array points as shown i n F i g . 5.4.2(a). Here, the negative weights have again been assigned according to equation 5.2.1 and t h e i r distance from the centroid point as opposed to an array point. A p o s i t i v e weight i s assigned to the " f i c t i t i o u s " centroid point. The operator i s defined to l i e oVer a boundary point whenever 1, 2 or 3 of the four centroid points overly a "1" on the input array. I f none or a l l four overlie a "1", then the operator i s defined to be located over a non-boundary point. This simple l o g i c i s e a s i l y implemented i n a 123 O O O O O O -01 -03 - 07 -07 -03 -01 O O O O O O -03 -17 -37 -37 -17 -03 O O O O O O -07 -37 -81 +-81 -37 -07 o o o 3 8 6 o O O -07 -37 -81 -81 -37 -07 O O O O O O -03 -17 -37 -37 -17 -03 O O O O O O -01 -03 -07 -07 -03 -01 (a) 9 9 e O O O O O O * © e o o o o o ® • © © O O 0 + 0 © @ © » © o o o @ ® @ © • • O O ® © © © © 9 © o ® © © © © • ® 8 9 9 9 9 8 G 9 9 9 (c) s 9 • • © • 9 9 9 9 e 9 9 9 o o o ® © ® • © O 9 9 o o O ® ® ® • © 9 9 9 o o o ® © © • © 9 9 9 o o o © © ® 9 9 9 9 9 o o o © @ ® 9 0 © 9 9 o o o © © ® 9 © O 9 © • 9 9 9 O 9 9 9 e 9 9 9 (b) 0 9 © 9 9 9 0 o o o o ® • 9 o 0 o o ® ® © 9 0 o ® ® © ® • 9 O 0 ® @ 9 9 o © ® © ® O 9 ® ® ® © ® © • 9 9 9 e • • © © o 9 • 9 9 9 9 • 9 9 9 9 (d) F i g . 5.4.2 The discre t e " f i c t i t i o u s centered" area operator i s shown i n (a) with associated weights calculated according to the Gaussian weighting p r o f i l e . The operator i s shown i n (b)„ (c) and (d) located at two possible o r i e n t a t i o n s of a s t r a i g h t edge of i n t e n s i t y i n each of the three p o s s i b l e boundary point p o s i t i o n s as defined by the boundary point detection l o g i c . 124 two-dimensional array of area operators and enables one to design sucb an array to extract only boundary responses. Some considerations i n the design of such a device are provided i n Appendix I I I . In F i g . 5.4.2(b) the " f i c t i t i o u s center" version of the area operator i s shown centered over a quantized s t r a i g h t edge of i n t e n s i t y , aligned with the array a x i a l d i r e c t i o n s . The operator can be seen to be i n one of the three p o s s i b l e boundary detecting p o s i t i o n s as defined by the simple l o g i c previously described. For a zero response i n t h i s p o s i t i o n , i t i s necessary that the weight associated with the c e n t r a l point be +386 units as shown i n F i g . 5.4.2(a). For a s t r a i g h t edge oriented at 45 degrees to the array a x i a l d i r e c t i o n s , the two possible and successive boundary configurations, defined by the boundary detecting l o g i c are shown i n F i g . 5.4.2(c) and (d). The operator response to the configuration of F i g . 5.4.2(c) works out to +99 as can be seen by adding a l l those weights ov e r l y i n g the input l ' s (black dots) and subtracting this value from the c e n t r a l weight. The response of the configuration of F i g . 5.4.2(d), obtained i n the same manner, i s -99 u n i t s . Therefore, as the operator moves along the s t r a i g h t edge oriented at 45 degrees, the net average response i s zero and the cum-mulative bias i s non-existent. This operator has been extensively i n -vestigated and found to accurately measure boundary curvature, f o r a wide v a r i e t y of weighting p r o f i l e s . Some experiments demonstrating i t s performance are described i n the next s e c t i o n . The reason for the incorporation of algorithm 1 i n t o the study of the s i x contour t r a c i n g algorithms i s now evident since algorithm 1 must be used with the area operator, on a square array, to obtain an unbiased response when the operator i s used i n a sequential scheme. 125 The minimum operator at the "heart" of the f i c t i t i o u s center area operator i s one c o n s i s t i n g s o l e l y of the four c e n t r a l points forming the "minimum" square. Such a minimum operator response i s , as was seen i n Chapter three, confined to one of three values, + TT/2 and 0 for a boundary point whenever 1, 2 or 3 of the four points are "1" or "0" on the input array. An equivalent minimum operator with a f i c t i t i o u s center can be defined f o r an hexagonal array. In t h i s case, the mini-mum operator consists of the b a s i c t r i a n g l e composed of three array points and i t s response i s confined to one of two values + IT/3. Just as with the square four point minimum operator, a l a r g e r area operator can be described, centered about the three point operator on an hexa-gonal array. Such an area operator also gives an unbiased response for any weighting p r o f i l e . A two-dimensional device, s i m i l a r to that described for the square array i n Appendix I I I , can be defined for a hexagonal array as w e l l , using the area operator with a three point center. Algorithm 6 of F i g . 3.1.1 i s the contour t r a c i n g algorithm by which successive boundary points must be defined for the three point hexagonal operator i n order to obtain an unbiased curvature function. Note that the use of e i t h e r the minimum square operator or the minimum t r i a n g l e operator to obtain curvature functions using e i t h e r the two-dimensional array approach or the sequential trace with the appropriate contour t r a c i n g algorithm, r e s u l t s i n the b a s i c curvature functions ( l c ) and C6c) r e s p e c t i v e l y of F i g . 3.1.1. 5.5 Experiments with Discrete Area Operators Area operators can be used to extract and smooth curvature functions of the boundaries of quantized shapes i n two ways. One 126 method i s to use a two-dimensional configuration such as that described i n Appendix I I I which, i s o l a t e s boundary points, and extracts smoothed measures of the boundary curvature. A one-dimensional function of curvature versus distance around the boundary i s obtained by arranging to record the output of the operator array at successive boundary points s e q u e n t i a l l y around the boundary. A second approach, which amounts to the .same thing i s to s e q u e n t i a l l y trace the boundary of a quantized shape using algorithm 1 of F i g . 3.1.1, centering the area operator about each boundary point and c a l c u l a t i n g i t s response by the methods previously described. This l a t t e r method was used to obtain curvature functions from the same quantized versions of the t h i r t y test shapes described i n Chapter four at eleven d i f f e r e n t s i z e s (diameters) of area operators using the Gaussian weighting p r o f i l e i n a l l cases. The two e r r o r c r i t e r i a of Sec. 4.1 were used to measure the curvature domain and reconstructed boundary domain errors i n a l l cases. As with the slope approximation method, the errors were p l o t t e d versus the r e c i p r o c a l of the curvature domain bandwidth as measured from average frequency attenuation curves, obtained as follows. When the minimum or four point area operator i s used i n conjunction with contour t r a c i n g algorithm 1, the r e s u l t i n g curvature function i s p r e c i s e l y the b a s i c curvature function of F i g . 3.1.1 (1) • Therefore, the frequency attentuation c h a r a c t e r i s t i c s were obtained by comparing the spectrum of the curvature function obtained using an area operator of some f i x e d s i z e with the spectrum of the b a s i c curvature function. The d e t a i l s of the computation are as described i n Sec. 3.3. -The frequency attentuation c h a r a c t e r i s t i c s at three operator 127 F i g . 5.5.1 Three sample frequency attenuation p l o t s for the area operator approach to the smoothing of the b a s i c curvature functions. s i z e s are shown i n F i g . 5.5.1 for the same quantized shape as was used for F i g . 4.3.1 with the slope approximation method. As can be seen, the area operator i s a non-linear device i n the curvature domain. From average frequency attenuation spectra s i m i l a r to F i g . 5.5.1, estimates of the approximate bandwidth (-.5 amplitude frequency) i n the curvature domain corresponding to area operators of varying s i z e were found. For each te s t shape, and at each array r e s o l u t i o n , the curva-ture domain and reconstructed boundary domain errors were found at 128 oo to o' o ' -oT=200 •ci T=150 -* T=100 0.0 F i g . 5.5.2 8.0 16.0 Reciprocal 24.0 32.0 40.0 of Absolute Bandwidth 4 8.0 56.0 (%.S.D.)-1 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors f o r the t h i r t y t e s t shapes f o r each of eleven d i f f e r e n t s i z e d area operators, quantized at each of three array s i z e s and p l o t t e d versus the "Reciprocal of Absolute Bandwidth" i n (cycles/U.S.D.)-l. The Gaussian weighting p r o f i l e was used throughout. 129 0.0 4.0 8.0 12.0 16.0 20.0 24.0 28.0 Reciprocal of Harmonic Bandwidth fx 100) F i g . 5.5.3 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors f or the t h i r t y t e s t shapes f o r each of eleven d i f f e r e n t . area operator s i z e s , quantized at each of three array resolutions and p l o t t e d versus the. "Reciprocal of Harmonic Bandwidth (xlOO)". The Gaussian weighting p r o f i l e was used throughout. 130 eleven different curvature domain bandwidths corresponding to sizes of area operators ranging from 2 x 2 to approximately 40 x 40. The average errors are shown plotted in Figs. 5.5.2 and 5.5.3. Once again, the array sizes are denoted by the resulting lengths of the curvature functions i n units of the sampling distance, T = 200 corresponding to the 50 x 50 average array, T « 150 to the 37 x 37 average array and" T=100 to the 25x25 array. The errors are plotted versus the reciprocal of absolute bandwidth (cycles/U.S .D.) ^ in F i g . 5.5.2 and versus the reciprocal of the harmonic bandwidth (xlOO) in F ig . 5.5.3. The behaviour of the curvature domain error curves is similar to the corresponding curves of F i g . 4.3.2 for the slope approximation method, showing an i n i t i a l sharp drop with the removal of some of the high frequency quantization noise followed by a gradual increase, for larger operators., due to the loss of signal d e t a i l . Again, the average minimum error bandwidth does not vary s ignif icant ly with array size and is approximately the same as observed with the slope approximation method. F i g . 5.5.4 shows the results of the application of the area operator to the five test shapes of F i g . 4.2.2, at the three array resolutions. The area operator size i n each case was such as to correspond to the minimum curvature domain error bandwidth, determined for each shape individual ly . The minimum error bandwidth for individual shapes varies with shape complexity, being largest for the more complex shapes. Values of the reciprocal of absolute bandwidth and the reciprocal of harmonic bandwidth are shown, along with the corresponding error values, in Table 5.5.1. F i g . 5.5.5 shows the area operator results for the three test shapes of F i g . 4.3.4. The reciprocal of absolute bandwidth values, the reciprocal of harmonic bandwidth values and the corresponding error 131 Figure ERROR ERROR^ Reciprocal of Absolute Bandwidth, Reciprocal of Harmonic Bandwidth (xlOO) a .263 .090 7.10 3.55 b .462 .136 8.83 4.42 c .702 .247 8.23 4.12 d .633 .139 5.50 2.75 e .890 .462 3.88 1.94 f .300 .087 7.16 4.77 g .556 .288 8.81 5.87 h .721 .221 8.11 5.41 i .698 .201 5.29 3.53 j .888 .491 4.01 2.68 k .421 .110 7.03 7.03 1 .582 .223 8.75 8.75 m .783 .358 8.03 8.03 n. .701 .349 5.71 5.71 0 .875 .403 4.13 4.13 Table 5.5.1 - The curvature domain errors (iJRROR^) , the reconstructed boundary domain errors (ERROR,) » the r e c i p r o c a l of absolute bandwidth values (cycles per U.S.D.) and the r e c i p r o c a l of harmonic bandwidth values for the functions and curves of F i g . 5.5.4. The curvature domain bandwidth i s such as to produce a minimum value of "ERR0R^ _.in each case. M N O F i g . 5.5.4 The res u l t s of the a p p l i c a t i o n of the area operator as a curvature measurement device to the f i v e quantized shapes at the three array resolutions of F i g . 3.3.2. For each function, the operator size was selected so as to produce a minimum curvature domain error. Corresponding e r r o r and bandwidth values are provided i n table 5.5.1. G M N 0 — — —»-F i g . 5.5.5 The results of the a p p l i c a t i o n of the area operator to three of the t e s t shapes quantized at an array r e s o l u t i o n of approximately 37x37, at f i v e operator s i z e s . Corresponding e r r o r and bandwidth values are provided i n table 5.5.2. Co 00 are provided i n Table 5.5.2. Figure ERROR^ ERR0R2 Reciprocal of Absolute Bandwidth Reciprocal of Harmonic Bandwidth (X100) a .866 .165 2.00 1.33 b .701 .203 5.70 3.79 c .777 .462 11.32 7.55 d .853 .623 32.10 21.40 e .915 .677 45.20 30.10 f .851 .159 2.00 1.33 g .725 .231 5.70 3.79 h .703 .209 11.32 7.55 i .838 .362 32.10 21.40 3 .877 .581 45.20 30.10 k .938 .253 2.00 1.33 1 • .888 .289 5.70 3.79 in .671 .309 11.32 7.55 n .523 .311 32.10 21.40 0 .736 .308 45.20 30.10 Table 5.5.2 - The curvature domain errors (ERROR^) , the reconstructed boundary domain errors ( E R R O R 2 ) , the r e c i p r o c a l of absolute bandwidth values (cycles per U.S.D.) and the r e c i p r o c a l of harmonic bandwidth values f o r the functions and curves of F i g . 5.5.5. In Figs. 5.5.2 and 5.5.3, the reconstructed boundary domain errors do not show an i n i t i a l drop with the removal of some of the high 135 frequency quantization noise and i n f a c t , r i s e quite sharply with in c r e a s i n g operator s i z e . This phenomenon i s due to the f a c t that area operators are subject to p a r t i c u l a r kinds of errors which the slope approximation method i s not. I t was found i n the experiment depicted by F i g . 5.3.1, that the area operator "saturates" i n the v i c i n i t y of "wedges" of curvature d e f i n i n g impulse weights exceeding TT/2 radiansper unit of arc length. I t was found that the area operator assigns higher values of curvature to boundary portions on e i t h e r side of the wedge "corner" than e x i s t e d i n r e a l i t y . This phenomenon, which was r e f e r r e d to as"saturation e r r o r " , l a r g e l y accounts f o r the poorer performance of the area operator as a curvature measurement device at smaller operator diameters as depicted by the reconstructed boundary domain e r r o r curves. Many examples of the e f f e c t s of sat u r a t i o n errors on the reconstructed boundaries can be seen i n F i g . 5.5.4 and by comparing these shapes with the quantized versions of F i g . 4.2.2. The curves of F i g . 5.5.4 (e,j and 0), represent "worst cases" of saturation e r r o r d i s t o r t i o n . Comparing these curves with the corresponding quantized shapes of F i g . 4.2.2 reveals that these quantized shapes contain many boundary regions resembling wedges representing impulses of curvature i n excess of TT/2 radians per unit of arc length. The operator has severely saturated i n the v i c i n i t y of these regions, producing the badly d i s t o r t e d curves of F i g . 5.5.4 (e, j and 0). Less severe examples of saturation e r r o r can be seen by comparing shapes (a), (c) (f) and (m) of Fi g s . 5.5.4 and 4.2.2. In (a), the operator has saturated on the two l a t e r a l "ends" of the f i g u r e , assigning greater curvature to these regions than e x i s t s i n r e a l i t y . The r e s u l t i s a s l i g h t v e r t i c a l compression of the o v e r a l l shape. In (c) and (m), the operator has saturated at the junction of the r i g h t " l e g " of the "R" with the top p o r t i o n . The r e s u l t again i s to assign higher curvature to t h i s region than i s warranted and the e n t i r e " l e g " i s l i f t e d as a r e s u l t . In ( f ) , the operator has saturated at the four "ends" of the f i g u r e , r e s u l t i n g i n an o v e r a l l rounding of the shape. A second type of e r r o r to which the area operator i s s e n s i t i v e i s the more obvious s i t u a t i o n where the operator i s s u f f i c i e n t l y large as to extend from the boundary on one side of a figure across the figure and beyond another portion of the boundary as shown i n F i g . 5 . 5 . 6 ( a ) . a • • • • 0 • 0 e e • • • ® o o o o ® o e o • © ® ® @ ® ® • • ® o o o o o • ® ® ® ® ® © • • ® o o o o o • + ® O o o o o o • ® @ ® o 9 0 + o 0 O 0 o o • © © © o © @ e o o o o o o o o o o o o o o o o o o ( a) (b) F i g . 5 . 5 . 6 The two types of overlapping errors encountered i n the use of area operators to measure curvature. The black dots represent the d i s c r e t e points of a quantized shape and the c i r c l e s represent the d i s c r e t e points of an area operator. 137 Another version of t h i s type of problem, shown i n F i g . 5.5.6(b), occurs when the operator overlaps two completely separate portions of the fi g u r e simultaneously. These s i t u a t i o n s are r e f e r r e d to as "overlapping" errors and l a r g e l y account f o r the large e r r o r values at small bandwidths (large operators). Some overlapping has occurred i n shapes (e) and (j) of F i g . 5.5.4 and an e x c e l l e n t example i s shown i n F i g . 5.5.5(c). In the l i m i t i n g case of the 2x2 area operator, both saturation and overlapping errors vanish since, on a square array, t h i s s i z e d operator can never "see" a wedge greater than TT/2 radians per unit of arc length. The curvature function obtained using such an operator i s shown i n functions (a), (f) and (k) of F i g . 5.5.5 and i s , as previously pointed out, the basic curvature function of contour t r a c i n g algorithm 1. The e f f e c t of the use of d i f f e r e n t weighting p r o f i l e s with the area operators was b r i e f l y i n v e s t i g a t e d . I t was found that a change i n p r o f i l e resulted i n a change i n the average steepness of the high frequency " r o l l - o f f " of the frequency attenuation curves much i n the same manner as a l i n e a r f i l t e r . Further comment on area operators as curvature smoothing devices i s l e f t to Sec. 5.7, following the r e s u l t s of the study of curvature domain f i l t e r i n g methods. 5.6 Curvature Domain F i l t e r i n g Methods Both the slope approximation and area operator methods of curvature measurement have been represented as non-linear smoothing operations on the basic curvature function corresponding to algorithm 1. In both cases, the frequency attenuation c h a r a c t e r i s t i c s are e s s e n t i a l l y "low-pass" i n t h e i r a f f e c t since high frequencies are generally attenuated, 138 but each r e s u l t s i n i r r e g u l a r d i s t o r t i o n of the lower frequencies. The t h i r d and f i n a l approach to smoothing the b a s i c curvature functions studied i n this t h e s i s , was to extract the b a s i c curvature functions using algorithm 1 and to pass these functions through a d i g i t a l l i n e a r low-pass f i l t e r . Two impulse responses were used, a simple exponential impulse response of the form h(s) = A. EXP C-B| s | ), s = arc length (5.6.1) and an i d e a l "brick w a l l " f i l t e r with impulse response of the form, h(s) - A . — — i • s s = arc length (5.6.2) The l a t t e r impulse response was simulated by representing the function i n a Fourier s e r i e s and truncating the s e r i e s at the desired harmonic. The curvature domain f i l t e r i n g method was applied to the same t h i r t y test shapes used i n connection with the previous methods and the error curves of Figs. 5.6.1 through 5.6.4 were calculated i n the same manner as described i n Sec. 4.1. The impulse response of equation 5.6.1 was used to obtain the r e s u l t s of F i g s . 5.6.1 and 5.6.2 and that of equation 5.6.2 for the curves of F i g . 5.6.3 and 5.6.4. The r e s u l t s i n a l l cases e x h i b i t behaviour s i m i l a r to that observed with the other methods. For both impulse responses, the average minimum erro r bandwidth appears to be about the same and does not vary s i g n i f i c a n t l y with array r e s o l u t i o n d i f f e r e n c e s . This phenomenon was again observed to hold for i n d i v i d u a l shapes although as with the other methods, the minimum erro r bandwidth varied with shape complexity. S i m i l a r l y , the e r r o r values for a given bandwidth va r i e d with 139 d l ' [ ' 1 ' I 1 I 1 I 1 I ' I ' 0.0 8.0 16.0 24.0 32.0 4 0.0 48.0 56.0 Reciprocal of Absolute Bandwidth ( c / f j ^ ^ ^ - 1 F i g . 5.6.1 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y test shapes f o r each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and p l o t t e d versus the "Reciprocal of absolute Bandwidth" i n (cycles per U.S.D.) -!. The exponential low-pass impulse response was used i n the curvature domain f i l t e r i n g . 140 o l ' I 1 I ' I ' I 1 1 ' 1 ' 1 ' 0-0 4.0 8.0 12.0 16.0 20.0 24.0 28.0 Reciprocal of Harmonic Bandwidth (xi00 ) F i g . 5.6.2 Average "Curvature Domain" and "Reconstructed Boundary Domain" errors for the t h i r t y test shapes for each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and p l o t t e d versus the "Reciprocal of Harmonic Bandwidth". The exponential low-pass impulse response was used i n the curvature domain f i l t e r . 0.0 8.0 16.0 24.0 32.0 40.0 48.0 - 56.0 Reciprocal of Absolute Bandwidth (C-/{j s D)~^ ' F i g . 5 . 6 . 3 Average "Curvature Domain" and "Reconstructed Boundary. Domain" errors for the thir ty test shapes for each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array resolutions and plotted versus the "Reciprocal of Absolute Bandwidth" in (cycles per U . S . D . ) - 1 . The "brick w a l l " f i l t e r was used in the curvature domain. N J CD i— o c O 03 6 :D J2 S c o Or-, T 0.0 Fig. 5.6.4 4.0 8.0 12.0 16.0 20.0 24.0 2 8.0 Reciprocal of Harmonic Bandwidth (x 100) Average "Curvature Domain".and "Reconstructed Boundary Domain" e r r o r s f o r the t h i r t y test shapes f o r each of eleven degrees of curvature domain f i l t e r i n g , quantized at each of three array r e s o l u t i o n s and p l o t t e d versus the " R e c i p r o c a l of Harmonic Band-. w i d t h " . The " b r i c k w a l l " f i l t e r was used i n the curvature domain. 143 the complexity of the fi g u r e , the e r r o r being generally l a r g e r , the more complex the shape. In F i g . 5.6.5, a few sample curvature functions and reconstructed boundaries are shown as obtained using the curvature domain f i l t e r i n g methods. Each was obtained using a f i l t e r bandwidth equal to the minimum error bandwidth and the values of the errors obtained are provided i n Table 5.6.1. Shapes (a) through (e) were obtained using the impulse Figure ERROR^ ERR0R2 Reciprocal of Absolute Bandwidth Reciprocal of Harmonic Bandwidth (xlOO) a .302 .010 7.68 3.84 b .460 .030 9.20 4.64 c .704 .165 7.81 3.89 d .633 .012 5.62 2.80 e .821 .124 4.29 1.80 f .103 .015 8.00 4.0 g .289 .023 9.10 4.55 h .600 .183 7.70 ' 3.85 i .563 .015 5.72 2.86 j .771 .131 4.00 2.00 Table 5.6.1 - The curvature domain errors (ERROR-^) , the reconstructed boundary domain errors (ERROR^) , the r e c i p r o c a l of absolute bandwidth values (cycles per U.S.D.) and the r e c i p r o c a l of harmonic bandwidth values for the curves and functions of F i g . 5.6.5. F i l t e r i n g i n each case was such as to produce a minimum curvature domain e r r o r . Fig. 5.6.5 The results of the application of the curvature domain f i l t e r i n g methods of curvature measurement to five of the test shapes, quantized at the 50x50 average array resolution. F i l t e r i n g in each case was such as to produce a minimum ERROR-^ value. The exponential low-pass f i l t e r was used for results (a to e) and the brick wall for results (f to j ) . (—• 1 -EN •:• response of equation 5.6.1 and shapes f through, j , using that of equation 5.6.2. F i n a l l y , i n F i g . 5.6.6, the e f f e c t s of extensive f i l t e r i n g are demonstrated f or the exponential low-pass f i l t e r (a to e) and f o r the "brick w a l l " f i l t e r (f to j ) , the errors and bandwidth values being l i s t e d i n Table 5.6.2. Figure ERROR^ ERR0R2 Reciprocal of Absolute Bandwidth Reciprocal of Harmonic Bandwidth (xlOO) a .866 .165 2.0 1.33 b .815 .141 3.78 2.51 c .712 .181 5.65 3.76 d .752 .201 10.21 6.82 e .899 .611 31.21 20.8 f .866 .165 2.0 1.33 g .797 .141 3.75 2.50 h .673 .137 5.55 3.70 i .751 .153 10.00 6.67 j .903 .301 30.00 20.00 Table 5.6.2 - The curvature domain errors ( E R R O R ^ ) , the reconstructed boundary domain errors ( E R R O R ^ » t n e r e c i p r o c a l of absolute bandwidth values (cycles per U.S.D.) ^ and the r e c i p r o c a l of harmonic bandwidth values f o r the curves and functions of F i g . 5.6.6. .•*••• • " , ^ i X \ } T.'._ .f: 6.6 The r e s u l t of the a p p l i c a t i o n of the curvature domain f i l t e r i n g methods of curvature measurement to one shape quantized at the 37x37 array r e s o l u t i o n . Five degrees of f i l t e r i n g are shown for the exponential low-pass f i l t e r (a to e) and for the "brick w a l l " f i l t e r (f to j ) . 147 5.7 Some Conclusions 'Concerning theVarious.Curvature Measurement Methods To compare the various e r r o r curves obtained using the d i f f e r e n t methods of curvature measurement, Fi g s . 5.7.1 through 5.7.3 were prepared. In F i g . 5.7.1, the err o r curves corresponding to the largest of the three average array sizes are shown for the slope approximation method (S. A.), the area operator (A. 6 . ) , the curvature domain exponential low-pass (C. D. L. P.) and the curvature domain b r i c k w a l l (C. D. B. W.) f i l t e r s . -In Figs. 5.7.2 and 5.7.3 are the corresponding e r r o r curves for the 37 x 37 and 25 x 25 array s i z e s r e s p e c t i v e l y . The behaviour of the curvature domain errors appears to be related more to the high frequency cut-off c h a r a c t e r i s t i c s of the method than to any other d e t a i l s of the frequency attenuation c h a r a c t e r i s t i c s of the three methods. Hence, the low frequency d i s t o r t i o n of the slope approximation and area operator approaches would not appear to be s i g n i f i c a n t i n terms of i t s influence on the curvature function. The minimum err o r bandwidth for each method i s approximately the same and the value of the e r r o r at t h i s point i s lowest f o r the method with the sharpest high frequency cut-off and highest f o r the le a s t sharp. As further bandwidth reduction i s applied however, a point i s reached where the errors are a l l approximately equal, regardless of the high frequency attenuation c h a r a c t e r i s t i c s . Upon s t i l l f u r t h e r bandwidth reduction, the behaviour reverses and errors are lower f o r the less steep high frequency cut-o f f methods. This behaviour of the curvature domain errors can be explained as follows. The curvature domain err o r i s l a r g e l y dominated by quantization noise and high frequency components. The i n i t i a l drop i n the errors coincident with the removal of some of the highest frequency components CD 148 o l~ Ui cc • —^ s O Q o • • QD CD. • C.D.L.P. a C.D.B.W. • CD CD D CD C CD - I u CU ~ " — I — I — I — ' — I — ' — I — ' — I — ' — I — 1 — I — • 0.0 4.0 8.0 12.0 16.0 20.0 24.0 28.0 Reciprocal of Harmonic Bandwidth (xlOO) F i g . 5.7.1 A comparison of.the r e s u l t s obtained with the d i f f e r e n t approaches to curvature measurement. Curves are averages f o r the t h i r t y test shapes at a quantizing array r e s o l u t i o n of approximately 50*.5Q. Methods are designate as slope approximation (S.A.), area operator (A.O.), curvature domain exponential low-pass f i l t e r i n g (C.D.L.P.) and curvature domain "brick w a l l " f i l t e r i n g (C.D.B.W.). * C.D.L.P. a C.D.B.W. 0.0 5.7.2 T 4.0 8.0 12.0 16.0 20.0 24.0 28.0 Reciprocal of Harmonic Bandwidth ('x100) A comparison of the r e s u l t s obtained with the d i f f e r e n t approaches to curvature measurement. Curves are averages for the t h i r t y t e s t shapes at a quantizing array r e s o l u t i o n of approximately 37*37. Methods are . designated .as slope approximation .(S.A.)., area operator (A.O.), curva-ture domain exponential low-pass f i l t e r i n g (C.D.L.P.) and curvature domain "brick w a l l " f i l t e r i n g (C.D.B.W.). 150 o L U c o £ o Q CD c D <3 QD CD* ts, CD*" CD ' NT CD o tD C o CQ ° CO CD" CD* o ct: CD I 1 I ' I ' I ' | ' 1 ' 1 ' 0.0 4.0 6.0 12.0 16.0 20.0 24.0 28.0 Reciprocal of Harmonic Bandwidth fx 100) F i g . 5.7.3 A comparison of the r e s u l t s obtained with the d i f f e r e n t approaches to curvature, measurement. Curves are averages f o r the t h i r t y test ..shapes at a quantizing array r e s o l u t i o n of approximately 25x25. Methods are designated as slope approximation (S.A.), area operator (A.O.), curvature domain exponential low-pass f i l t e r i n g (C.D.L.P.) and curvature domain "brick w a l l " f i l t e r i n g (C.D.B.W.). 151 i s most e f f e c t i v e l y achieved w i t h a sharp cut-o f f f i l t e r as the components being discarded are predominantly noise as was i l l u s t r a t e d i n the £ n curves of F i g . 3 . 3 . 5 . Beyond the point where the e r r o r curves merge, the high frequency s i g n a l attenuation i s contri b u t i n g to the r i s e i n e r r o r values. Therefore, the attenuation c h a r a c t e r i s t i c s which l e a s t attenuate these high frequencies, f o r a given 1/2 amplitude bandwidth, produces a minimum e r r o r . Therefore, the exponential low-pass f i l t e r shows a minimum curvature domain error at narrow bandwidths. With the exception of the area operator, the reconstructed boundary domain errors are also mainly determined by the average frequency attenuation c h a r a c t e r i s t i c s of the method and the e f f e c t of the amplitude d i s t o r t i o n introduced by the slope approximation methods i s not apparent. Since these errors (ERROR^) are mainly determined by the low frequency components i n the curvature function, i t i s the average attenu-ation of the low frequency components which i s c r i t i c a l i n determining the behaviour of ERROR^. Therefore, the methods with the steepest r o l l -o f f i n the attenuation c h a r a c t e r i s t i c s and hence the least average attenuation of low frequencies, produce the smallest errors for a given bandwidth. In the l i g h t of the r e s u l t s of the preceeding sections, the following conclusions can be made concerning the curvature measurement methods. An area operator performs best as a high r e s o l u t i o n device. Most of the errors contributing to the poor r e s u l t s obtained with area operators arose from a l a c k of r e s o l u t i o n i n the array, f o r c i n g the use of area operators which were large i n comparison with the t o t a l s i z e of the quantized shapes. I f a high r e s o l u t i o n array i s used, a reasonably 152 large area operator i n terms of array points could be used without the int r o d u c t i o n of the "overlapping" type of errors discussed i n the previous section (Sec. 5.5). Saturation e r r o r s , also discussed i n that s e c t i o n , would be avoided to a large extent by using high r e s o l u t i o n arrays. The chief advantage of area operators i s that they can be <. incorporated i n t o a two-dimensional array. Hence, the mechanics of boundary point i s o l a t i o n , curvature e x t r a c t i o n and smoothing can be performed instantaneously. Such a two-dimensional configuration would be advantageous i n s i t u a t i o n s where speed was of high importance or where a p a r a l l e l structure was desired for other reasons. A second s i t u a t i o n where area operators are advantageous i s i n applications where only a few i s o l a t e d points of boundary curvature are required. The area operator can measure boundary curvature without knowledge of the h i s t o r y or future of the boundary i n the v i c i n i t y of the point i n question since i t simply counts "excited" points within i t s circumference. Other methods require l o c a l i z e d boundary t r a c i n g to accomplish the same r e s u l t . For the sequential e x t r a c t i o n of the curvature function, the use of the slope approximation methods i s d i f f i c u l t to j u s t i f y i n the l i g h t of the r e s u l t s obtained since the curvature domain f i l t e r i n g methods are much f a s t e r and computationally simpler, giving as good i f not bette r r e s u l t s . The curvature domain f i l t e r i n g methods have been demonstrated on the b a s i c curvature function corresponding to algorithm 1. In p r a c t i c e , the l o g i c a l approach would be to use these methods i n conjunction with a contour t r a c i n g algorithm with superior noise c h a r a c t e r i s t i c s such as algorithm 3, 4 or 5. 153 5.8 General Conclusions In considering the use of curvature or tangent angle functions i n pattern recognition a p p l i c a t i o n s , the problem a r i s e s as to which function i s the most s u i t a b l e . While t h i s question i s best resolved with a s p e c i f i c problem i n mind, some general comments can be made. The main advantage to the use of curvature as opposed to the tangent angle function i s i t s ease of measurement, p a r t i c u l a r l y since i t can be measured using a two-dimensional array of area operators and hence leads to the p o s s i b l i t y of a l l p a r a l l e l systems. This type of implementation for tangent angle measurement i s considerably more d i f f i c u l t to achieve. The main d i f f i c u l t y with curvature i s the f a c t that the high frequency components, which are predominantly noise, are amplified by the second d i f f e r e n t i a t i o n i n the e x t r a c t i o n process, causing the curvature functions to be exceptionally noisy. This noise can only be removed by severe smoothing of the functions which, i n turn, r e s u l t s i n the loss of considerable s i g n a l d e t a i l . A second disadvantage of the curvature function i s that i t s amplitude changes with changes i n the s i z e of the corresponding shape. To normalize curvature functions to a fixed period, which represents a crude normali-zation of the s i z e of the corresponding shape, requires corresponding amplitude s c a l i n g . ? i t.i~•. :. Tangent angle functions, while they possess superior.-noise c h a r a c t e r i s t i c s i n that the high frequencies are not amplified by the second d i f f e r e n t i a t i o n , s u f f e r from the disadvantage that they are not o r i e n t a t i o n independent, p r i m a r i l y because of the "ramp" or "s" term (see equation 2.2.2). Tangent angle functions are also d i f f i c u l t 154 to measure quickly, r e q u i r i n g a sequential contour t r a c i n g algorithm. The amplitude of tangent angle functions however, remains constant for changes i n the s i z e of the Corresponding shapes. A s a t i s f a c t o r y compromise between the two functions i s the "Angle Versus Length" or "AVL" function used by the U n i v e r s i t y of Ohio group, B r i l l , Raudseps, C o s g r i f f et a l . , (19-23). B r i l l et a l . have proposed measuring the tangent angle function (<J>(s)) and subtracting the "ramp" function (2 I T S ) to y i e l d the AVL function ^ ( s ) : T ^ C s ) = <i>(s) - l i s . (5.8.1) T B r i l l et a l , then apply the Fourier transform to <i> (s) and use the t h i r t y amplitude c o e f f i c i e n t s corresponding to the f i r s t f i f t e e n harmonics, which they c a l l "Fourier Descriptors", as feature values f o r the c l a s s i f i c a t i o n of a l p h a b e t i c a l characters. The AVL function has the b e t t e r noise c h a r a c t e r i s t i c s of the tangent angle function and the o r i e n t a t i o n independence of the curvature function. The r e s u l t s of t h i s thesis suggest many refinements on the method of B r i l l et a l . From the theory of Sec. 2,2, i t can be seen that the Fourier Descriptors of B r i l l et a l . are simply r e l a t e d to the Fourier components of the curvature function. In terms of the frequency components A ^ and B ^ as defined for curvature functions i n equation 3.2.2, the "Fourier Descriptors" of B r i l l et a l . , for the sine and cosine components of the n th harmonic, denoted as F and F res-r ' sn cn p e c t i v e l y , are given by: F = A, /n cn An F * B. /n. (5.8.2) sn An The c o e f f i c i e n t s A ^ and B ^ are r e a d i l y supplied by most "Fast Fourier Transform" algorithms such as the Cooley-Tukey algorithm (82) which do not divide by the period (T). Hence, any of the curvature measurement methods of t h i s thesis can be used to extract a curvature function and to then compute the Fourier descriptors according to equation 5.8.2. In t h e i r experimental work, B r i l l et a l . used contour tr a c i n g algorithm 4 i n the e x t r a c t i o n of t h e i r AVL function. Since the r e s u l t i n g functions did not have equally spaced points, the computational complexity of c a l c u l a t i n g the Fourier descriptors was considerably increased. The r e s u l t s of the quantization noise study of t h i s thesis suggest that other simpler algorithms could be used to achieve the same noise c h a r a c t e r i s t i c s on the Fourier descriptors by using an hexagonal array or a s l i g h t l y higher r e s o l u t i o n i n a square array. The r e s u l t s of the thesis also form a contribution to the area of contour coding which has been inv e s t i g a t e d by s e v e r a l authors i n c l u d i n g Zahn (24), Tomita and Nouguchi (83), R i n t a l a and Hsu (84), Huang et a l . (85) and most extensively by Freeman (33-35). Although i t i s not r e f e r r e d to as such, the- contour coding scheme of Freeman (33-35) amounts to the coding of an u n f i l t e r e d or "basic" tangent angle function around the boundary of a quantized shape, obtained using contour t r a c i n g algorithm 4 of F i g . 3.1.1. Such a coding scheme requires 3 b i t s per sample point of coding for e i t h e r the b a s i c tangent angle or curirature functions. One r e s u l t of the thesis i s to show that by coding curvature instead of tangent angle and by employing d i f f e r e n t contour t r a c i n g algorithms, more e f f i c i e n t coding of contours i s p o s s i b l e . The thesis r e s u l t s also contribute to the knowledge of the amount of shape d e t a i l representable i n a given coded contour. In this t h e s i s , an attempt has been made to contribute to the Understanding of the nature of the problems involved i n estimating the curvature of the boundaries of quantized shapes. An attempt has also been made to show that the mathematical concept of boundary curvature i s both meaningful and v i a b l e as a descriptor of shape for pattern recognition and contour coding a p p l i c a t i o n s . The problem of e x t r a c t i n g the curvature of the boundaries of quantized shapes has been treated as a two step process:- the e x t r a c t i o n of a basic or u n f i l t e r e d curvature function and the smoothing of that basic function. Six contour t r a c i n g algorithms have been described and used i n the e x t r a c t i o n of b a s i c curvature functions and three approaches to the smoothing problem have been considered. A curvature function extracted from the boundary of a quantized shape i s composed to two q u a n t i t i e s : - i r r e l e v a n t information or "quantization noise" r e s u l t i n g from the d i g i t i z a t i o n of the o r i g i n a l shape and relevant information concerning the d e t a i l s of the shape, i . e . , the " s i g n a l " . In the frequency domain, the quantization noise was modelled as a function of frequency i n cycles per unit sampling distance. The v a r i a t i o n i n the quantization noise with algorithm type and array r e s o l u t i o n was studied and estimates of the useful bandwidth of d i f f e r e n t basic curvature functions were obtained. The s i g n a l content of the b a s i c curvature functions i s , i n the frequency domain, a function of the harmonic content rather than frequency content i n cycles per unit sampling distance. Therefore, the r e l a t i o n s h i p between harmonic content of basic curvature functions and the d e t a i l i n the corresponding geometrically reconstructed boundaries has been b r i e f l y i n v e s t i g a t e d . It has been shown how the quantization noise model and the r e s u l t s of the harmonic content study can be used to s e l e c t a matrix r e s o l u t i o n so^that the r e s u l t i n g b a s i c curvature function has a usable bandwidth s u f f i c i e n t l y wide as to preserve the required d e t a i l i n the given shape boundary. The approach, used i n the study and comparison of the three approaches to smoothing curvature functions has been to regard each as an operation i n the curvature frequency domain. The r e s u l t s i n d i c a t e that each of the three methods studied can, to a reasonable f i r s t approximation, be regarded as a low-pass f i l t e r acting on the b a s i c curvature function. A technique has been developed to study the behaviour of the curvature function as d i f f e r e n t degrees of t h i s "low-pass" smoothing are applied. A v a r i e t y of extensions of the work, described i n t h i s thesis are p o s s i b l e . The e n t i r e t h e s i s has been based on the representation of the basic curvature functions by Fourier s e r i e s expansions. The Fourier s e r i e s was selected for t h i s i n i t i a l study since i t i s the most frequently used s e r i e s i n the s o l u t i o n of engineering problems and also since i t appears to o f f e r c e r t a i n advantages i n pattern r e c o g n i t i o n a p p l i c a t i o n s (19-20). However the experimental procedures described i n the thesis are not r e s t r i c t e d to the Fourier s e r i e s and could be extended to studies of the Walsh function representation, Chebyshev polynomials and others. The extension of the work to three dimensions and a study of t o r s i o n i s another p o s s i b i l i t y . Such a study might f i n d a p p l i c a t i o n i n the s o l u t i o n of three-dimensional space problems and pursuit or tracking problems. A f e e l i n g for the behaviour of both the s i g n a l and quantization noise components of curvature functions has been established i n the t h e s i s . The p o s s i b i l i t y of a more t h e o r e t i c a l l y oriented approach to the same problem remains. APPENDIX I Quantization Procedure A computer algorithm was developed to simulate the quanti-zation of the t e s t shapes from the reconstructed boundaries of those shapes. In most r e a l systems used i n the d i g i t i z a t i o n or quantization of binary shapes, those shapes are presented to the quantizing device as a binary i n t e n s i t y d i s t r i b u t i o n . The device interrogates a two-dimensional matrix of points over the i n t e n s i t y d i s t r i b u t i o n , measures the i n t e n s i t y at each point and records a "0" or "1" depending on whether or not the l i g h t i n t e n s i t y i s above or below a s p e c i f i e d threshold. I f c e r t a i n of the points interrogated by the system happen to l i e at the dark-light boundary of the binary shape, then the value CO or 1) recorded i s influenced by the system uncertainty or noise and a source of e r r o r i s introduced i n t o the quantization pro-cedure. For t h i s study however, an i d e a l quantizer was simulated i n that no uncertainty or e r r o r i s introduced at the boundary points. The simulated system placed the d i s c r e t e reconstructed boundary over a two-dimensional array of d i s c r e t e points. The o r i e n t a t i o n of the shape with- respect to the array was e s s e n t i a l l y random. F i g . A.1.1 shows a portion of a d i s c r e t e boundary (black dots) shown i n an a r b i t r a r y p o s i t i o n over a square array of points (designated as the i n t e r s e c t i o n s of V e r t i c a l and h o r i z o n t a l l i n e s ) . In proceding from point to point around the boundary, s t a r t i n g at "+", the i d e a l quantizer assumed that the d i r e c t i o n of motion i s counterclockwise around the figure and assigns a Value "1" to a l l points on or w i t h i n the boundary (to the r i g h t ) and a "0" to a l l others. Since only boundary points of the quantized shapes are of i n t e r e s t , the quantizer need only record those array points on or within the boundary and nearest to i t . S p e c i f i c a l l y , i t records those boundary points nearest the o r i g i n a l boundary points and seeks those points (of the quantizing array) by moving only i n the array a x i a l d i r e c t i o n s . In F i g . A.1.1, the points of the array l a b e l l e d boundary points are shown c i r c l e d . The basis of the algorithm for s e l e c t i n g boundary points on the array i s to determine, for a given point on the o r i g i n a l boundary, i n which "minimum square" formed by four array points, the point i n question resides. Also, the algorithm determines the previous square occupied by the o r i g i n a l boundary and the next square to be occupied. In most cases, these three squares, the previous one, the current and the next w i l l l i e h o r i z o n t a l l y or v e r t i c a l l y arranged with respect to the current square. That i s the next and the previous squares w i l l be found e i t h e r v e r t i c a l l y or h o r i z o n t a l l y located with respect to the current square. In t h i s case, simple rules can be e s t a b l i s h e d f o r assigning values (1 or 0) to each corner point of the current array, depending upon the locations of the previous and next squares. A s p e c i a l case arises when a previous or next square i s one at any of the four diagonal d i r e c t i o n s from the current square. In such instances, i t i s assumed that the portions between the d i s c r e t e points of the o r i g i n a l boundary are s t r a i g h t l i n e s and points on those l i n e s are c alculated u n t i l one i s found which l i e s w i t h i n a square e i t h e r V e r t i c a l l y or h o r i z o n t a l l y located with respect to the current square. Assignment of values (0 or 1) to the current points then proceeds. I t was pointed out i n the main text, that a problem a r i s e s i n attempting to e s t a b l i s h the proper phase s h i f t between the ba s i c curvature functions and the corresponding o r i g i n a l curvature functions. This problem was circumvented i n the quantization procedure by a l i g n i n g the functions i n the reconstructed boundary domain where the " s i g n a l - t o -noise" r a t i o i s much higher. In p r a c t i s e the f i r s t point of the o r i g i n a l reconstructed boundary was used for alignment. This f i r s t point was assumed to coincide with the c l o s e s t point on the quantized array boundary. From the two so aligned functions, curvature was then calculated i n the same way to ensure that the same s h i f t i n g was applied to each i n the c a l c u l a t i o n of curvature. 1 • \ t Of • 0 9 p ' • \ • • 1 • • • > • X • • * f ' 1 i 1 A > • • 1 u-4 O -..Fig. A. 1.1 A t y p i c a l portion of a di s c r e t e o r i g i n a l boundary (black dots) i s shown superimposed on a square quantizing array (i n t e r s e c t i o n s of g r i d l i n e s ) . The boundary points of the array as found by the quantization algorithm are shown as c i r c l e s . lbl APPENDIX I I For comparison, purposes, i t was deemed desirable to quantize the t e s t shapes on square and hexagonal arrays of approximately the same r e s o l u t i o n . This was done by f i n d i n g appropriate dimensions of the "minimum t r i a n g l e " of the hexagonal array i n terms of the dimensions of the "minimum square" of the square array which, upon the quanti-zation of a given shape, would y i e l d a quantized figure containing approximately the same number of points f o r both array configurations. F i g . A.2.1 shows the r e l a t i o n s h i p i n dimensions used f o r the minimum tr i a n g l e (dots) versus the minimum square ( c i r c l e s ) . For a square array spacing of w, the corresponding hexagonal F i g . A.2.1 The r e l a t i o n s h i p between the basic square of a square quantizing array ( c i r c l e s ) and the equivalent b a s i c t r i a n g l e (black dots) of an hexagonal quantizing array. array spacing i s such that, h o r i z o n t a l l y the spacing exceeds the spacing of the square array by an amount (x) equal to that by which, i n the v e r t i c a l d i r e c t i o n , the square spacing exceeds the t r i a n g l e spacing. That i s : w-x = - y -(w+x). (A.2.1) Hence: X « w , . ( 2 - / ^ ). (A.2.2) 2+/3 Therefore the side length of the b a s i c t r i a n g l e of the hexagonal array (H) i n terms of the side length (w) of the b a s i c square i s given by: H » ( — - — ) • w. (A.2.3) 2H-/3 This r e l a t i v e spacing of hexagonal and square array points was used throughout. c APPENDIX III A two-dimensional array of d i s c r e t e area operators can be constructed to i s o l a t e boundary points on binary, quantized two-dimensional shapes and to measure and smooth the curvature of the boundaries at those points. The organization of such a two-dimensional device i s depicted i n F i g . A.3.1. An N x N input array of transducers i s required to transform the incoming information ( i n t h i s case, most probably a binary d i s t r i b u t i o n of l i g h t i n t e n s i t y ) i n t o a d i g i t a l or NxN Transducer Logic Array Array F i g . A.3.1 A possible l o g i c arrangement for the two-dimensional imple-mentation of area operators. quantized array of binary voltage l e v e l s . A voltage l e v e l "1" occurs whenever the corresponding transducer l i e s under dark portions of the 2 input i n t e n s i t y and "0" under l i g h t portions. The N output l i n e s of the transducer array are fed i n t o a l o g i c network which performs the l o g i c a l operations of area operators. The l o g i c network might consist of three stages. The f i r s t stage would serve to i s o l a t e boundary points. In the case of the f i c t i t i o u s center area operator of Sec. 5.5, t h i s would be accomplished with simple l o g i c a l functions of each possible combination of four l i n e s from the input array which co r r -esponded to a basic or minimum square on the transducer array. As previously described, i f 1, 2 or 3 of these l i n e s have voltages "1" or "0", the "point" defined i s a boundary point. The second stage of the l o g i c network would perform the weighted summation portion of the area operator a c t i v i t y as described i n connection with F i g . 5.4.2. Such a weighted summation would be performed f o r points surrounding 2 each of the (N-l) "centroid" boundary points. I.e. since a boundary point i s defined at the centroid of four input array points, i f the input array i s N x N, the "boundary point" array i s (N-l)x ( N - l ) . The f i n a l stage of the l o g i c would be to produce an output array of area operator responses (N-l)x(N-l) enabled by the boundary point array c of stage 1. That i s . o n l y those area operator responses corresponding to boundary points would have an "enabled" output. Further processing on the (N-l)x(N-l) output array could be done i n a two-dimensional system or by e x t r a c t i n g the boundary curvature values s e q u e n t i a l l y . APPENDIX IV The degree of confidence to be associated with the average values of the many s p e c t r a l p l o t s of Chapter three was inv e s t i g a t e d i n two ways and samples of the r e s u l t s are provided i n t h i s appendix. For the average s i g n a l spectrum of F i g . 3.3.1, the actual values f o r f i v e t y p i c a l harmonics are shown i n Table A.4.1, along with the standard Harmonic Number Ov e r a l l Average Standard Deviation Average Std. Dev. 1 Subset Averages 2 3 4 5 1 4.44 2.70 1.64 4.77 4.55 3.87 4.00 5.01 4 15.71 9.63 1.63 16.43 15.01 15.87 14.92 16.32 10 9.50 4.57 2.08 9.12 8.87 10.13 9.ftl 9.47 40 8.10 4.11 1.97 8.01 8.21 8.92 7.63 7.73 70 9.91 5.54 1.79 10.53 9.28 10.02 9.97 9.75 i Table A.4.1 - The o v e r a l l averages, the standard deviation values and the averages of f i v e subsets of 20 samples each for ° the amplitude of f i v e a r b i t r a r i l y selected harmonics of the 100 t e s t shape curvature functions. deviation values. The r a t i o of the mean value to the standard deviation was found to co n s i s t e n t l y vary over the same range (randomly) c for a l l of the average s p e c t r a l p l o t s and i s therefore also included. The s t a b i l i t y of the mean value estimates was studied by d i v i d i n g the 100 samples i n t o f i v e subsets of twenty samples each, and computing the mean value of each subset. The r e s u l t s are also shown i n Table A.4.1. No d e f i n i t e trends could be detected over the f i v e subsets and i n most cases, the f i v e values are s u f f i c i e n t l y close to warrant a reasonable confidence i n the o v e r a l l mean values. 166 Similar i n v e s t i g a t i o n s were conducted on a l l of the average s p e c t r a l p l o t s of Chapter three. Some t y p i c a l r e s u l t s f o r the average noise CN ) s p e c t r a l plots are shown i n Tables A.4.2 and A.4.3 for algorithm 1 and algorithm 3 on the 15 X 15 array r e s p e c t i v e l y . These values are t y p i c a l f o r the remainder of the s p e c t r a l p l o t s as w e l l . Harmonic Number Overall Average Standard Deviation Average Std. Dev. 1 Subset 2 Averages 3 4 5 1 .776 .364 2.13 .751 .831 .859 .712 . 727 4 5.63 2.98 1.89 5.64 5.63 5 .21 5.83 5. 84 10 9.47 6.23 1.52 10.31 9.09 9 .22 10.61 8. 12 20 18.63 10.76 1.73 17.93 17.42 20 .11 18.60 19. 09 30 29.92 20.08 1.49 27.31 29.97 32 .41 27.61 32. 30 The o v e r a l l averages, the standard deviation values and the averages of f i v e subsets of 20 samples each f or f i v e a r b i t r a r y harmonic amplitude values of the quantization noise (N ) on the 100 quantized t e s t shape basic curvature functions. Algorithm 1 was used i n the ext r a c t i o n of the bas i c curvature functions. Table A.4.2 -Harmonic O v e r a l l Standard Ave rage Subset Averages Number Average Deviation Std. Dev. z 1 1.89 .931 2.03 1.77 1.93 1.87 1.84 2. 04 4 6.84 3.12 2.19 7.32 7.31 6.55 6.77 6. 25 10 10.28 5.81 1.77 10.33 10.03 11.01 9.88 10. 15 20 13.95 6.71 2.08 13.94 13.13 13.16 14.23 15. 29 25 14.71 9.03 1.63 14.31 14.88 15.21 15.07 14. 08 Table A.4.3 - The o v e r a l l averages, the standard deviation values and the averages of f i v e subsets of 20 samples each for f i v e a r b i t r a r y harmonic amplitude values of the quantiza-tion noise 0$^) on the 100 quantized t e s t shape basic curvature functions. Algorithm 3 was used i n the e x t r a c t i o n of the b a s i c curvature functions. 168 REFERENCES 1. Mendel, J . M . and Fu, K. S. , Adaptive, Learning and Pattern Recognition Systems, Academic Press, Nex^ York, 1970. 2. Nagy, G . , "State of the Art i n Pattern Recognition", Proceedings of the I . E . E . E . , V o l . 56, No. 5, pp. 836-862, 1968. 3. Levine, M. D . , "Feature Extraction: A Survey", Proceedings of the I . E . E . E . , V o l . 57, No. 8, pp. 1391-1407, August, 1969. 4. Tou, J . T . and Wilcox, R . H . , Computer and Information Sciences, Spartan Books, 1964. 5. Uhr, L . , Pattern Recognition, J . Wiley and Sons, New York, 1966. 6. Watanabe, S. , Methodologies of Pattern Recognition, Academic Press, 1969. " ~ ~ — — — 7. Cheng, G . C . , Ledley, R . S . , Pollock, D.K. and Rosenfeld, A . , P i c t o r i a l Pattern Recognition, Thompson Book Company, 1968. 8. Armitage, J . D . and Lohmann, A.W., "Character Recognition by Incoherent Spatial F i l e r i n g " , Applied Optics, V o l . 4, pp. 461-467, 1965. 9. Kanal, L . N . , Pattern Recognition-Proceedings of the I . E . E . E . Workshop on Pattern Recognition, 1968. 10. Greanias, E . C . , Meagher, P . F . , Norman, R . J . and Essinger, P . , "The Recognition of Handwritten Numerals by Contour Analysis" , IBM Journal of Research and Development, V o l . 7, No. 1, pp. 14-21, January, 1963. . . 11. Masnikosa, V . , "Practical Realization of a Pattern Recognition Algorithm on a D i g i t a l Computer", Engineering Cybernetics, No. 1, pp. 143-147, 1968. 12. Fukushima, K . , "Visual Feature Extraction by a Multilayered Network of Analog Threshold Elements", I . E . E . E . Transactions on Systems Science and Cybernetics, V o l . SSC-5, No. 4, pp. 322-333, 1969. 13. Glucksman, H . A . , "Class i f i ca t ion of Mixed-Font Alphabetics by Characteristic L o c i " , Digest of 1st Annual I . E . E . E . Computer Conference, pp. 138-141, September, 1967. 14. Hu, M.K. , "Visual Pattern Recognition by Moment Invariants", IRE Transactions on Information Theory, V o l . IT-8, pp. 179-187, February, 1962. 15. Ledley, R . S . , "Automatic Pattern Recognition for C l i n i c a l Medicine", Proceedings of the I . E . E . E . , V o l . 57, No. 11, pp. 2017-2025, November, 1969. 169 16. Nagy, G . , "Feature-Extraction on-Binary Patterns", I . E . E . E . Transactions on Systems Science and Cybernetics, V o l . SSC-5, No. 4, pp. 273-278, 1969. 17. Andrews, H . C , "Orthogonal Transforms and Feature Selection in Pattern Recognition", Fourth Hawaii International Conference on System Sciences, 1971. 18. Vinea, A. and Vinea, V . , "A Distance Criterion for Figural Pattern Recognition", I . E . E . E . Transactions on Computers, V o l . C-20, No. 6, June, 19 71. 19. Frtizsche, D . L . , "A Systematic Method for Character Recognition", Report 1222-4, (AD-268,360) prepared under Contract AF33 (616)-7843 for Aeronautical Systems Divis ion, Wright-Patterson A i r Force Base, Ohio, by the Antenna Laboratory, The Ohio State University Research Foundation, November 15, 1961. 20. Cosgriff , R . L . , "Identif ication of Shape", Report 820-11 (AD-254, 792) prepared under Contract AF33(616)-5590 for Aeronautical Systems Divis ion, Wright-Patterson Air Force Base, Ohio, by Antenna Laboratory, The Ohio State University Research Foundation, November 15, 1961. 21. Raudseps, J . G . , "Some Aspects of the Tangent-Angle vs. Arc Length Representation of Contours", Report 1801-6 prepared under Contract AF33.(615)-126 7 for A i r Force Avionics Laboratory, Wright-Patterson Air Force Base, Ohio, by Communications and Control Systems Laboratory, The Ohio State University Research Foundation, March, 1965. 22. B r i l l , E . L . , "Character Recognition via Fourier Descriptors", Wescon Technical Papers, Session 25, Qualitative Pattern Recognition Through Image Shaping, 1968. 23. B r i l l , E . L . , Heydorn, R.P. and H i l l , J . D . , "Some Approaches to Character Recognition for Postal Address Reader Applications" , Proceedings of Automatic Pattern Recognition, May 6, 1969. 24. Zahn, C . T . , "Two-Dimensional Pattern Description and Recognition via Curvature Points", Technical Report prepared under Contract AT(04-3)-515 for the USAEC, San Francisco Operations Office by Stanford Linear Accelerator Center, Stanford University, Standard, Cal i fornia , December, 1966. 25. Kasvand, T . , "Pattern Recognition Applied to the Counting of Nerve Fibre Cross-sections and water droplets", i n Methodologies of Pattern Recognition, (Watanabe, S . -edi tor ) , pp. 333-339, 1969. 26. Kasvand, T . , "Pattern Recognition Applied to the Counting of Nerve Fibre Cross-sections", National Research Council Report, 1969. 170 27. Connor, D . J . "Lateral Inhibition and the Area Operator i n Visual Pattern Recognition", Ph.D. Thesis - The University of - British, Columbia, 'Department of E l e c t r i c a l Engineering, 1969. 2 8 . Munson, J . H . , "Experiments i n the Recognition of Hand-Printed Text: Part 1 - Character Recognition", ' F a l l Joint Computer Conference, pp. 1125-1137, 1968. 29. Tou, J . T . , "Computer and Information Sciences - II , Academic Press, New York, 1967. 30. Kanal, L .N. . , "Pattern Recognition", Thompson Book Company, Washington, D . C . , 1968. 31. Clemens, J . K . , "Optical Character Recognition for Reading Machine Applications" , Ph.D. Thesis, Massachusetts Institute of Technology, 1965. 32. Andrews, H . C , "Multidimensional Rotations i n Feature Selection", I.E . E . E . Transactions oh Computers, V o l . C-20, No. 9, September, 1971. 33. Freeman, H . , "On the Encoding of Arbitrary Geometric Configurations", IRE Transactions on Electronic Computers, EC-10, pp. 260-268, June, 1961. 34. Freeman, H. and Garder, L . , "Apic tor ia l Jigsaw Puzzles: the Computer Solution of a Problem i n Pattern Recognition", I . E . E . E . Transactions on Electronic Computers, EC-13, pp. 118-127, A p r i l , 1964. 35. Freeman, H . , "On the Digi ta l Computer Class i f ica t ion of Geometric Line Patterns", Proceedings of the National Electronics Conference, Chicago I l l i n o i s , V o l . 18, pp. 312-324, 1962. n 36. Attneave, F . , "Some Informational Aspects of Visual Perception", Psychological Review, V o l . 61, No. 3, 1954. 37. Attneave, F . , "The Relative Importance of Parts of a Contour", USAF Human Resources Research Center, Research B u l l e t i n , No. 51-8, 1951. 38. Attneave, F . , "The Quantitative Study of Shape and Pattern Perception", Psychological B u l l e t i n , V o l . 53, pp. 452-471, 1956. 39. Wagner, H . C , "The Spatial Summation of Light Stimuli in the Retina as Revealed by the Neuron Response Patterns", in Symposium Sponsored by the Visual Sciences Study Section, National Institute of Health, Brown University, 1964. 40. Schipperheyn, J . J . , "Contrast Detection i n Frog's Retina", Acta. Physiologica Pharmacdlogica, V o l . 13, pp. 231*-277, 1965. 41. Cleland, B . C and Enroth-Cugell, C , "Quantitative Aspects of Sensit ivity and Summation in the Cat Retina", Journal of Physiology, V o l . 198, pp. 14-38, 1968. 171 42. Enrotlv-Cugell, C. and Robson, J . G . , "The Contrast Sensit ivi ty of Retinal Ganglion Cells of the Cat", Journal of Physiology, V o l . 187, pp. 517-552, 1966. 43. Rodieck, R.W. and St'one, J . , "Analysis of Receptive Fields of Cat Retinal Ganglion C e l l s " , Journal of Neurophysiology, V o l . 28, pp. 833-849, 1965. 44. Rodieck, R.W., "Quantitative Analysis of Cat Retinal Ganglion C e l l Response to Visual S t imuli " , Vision Research, V o l . 5, pp. 583-601, 1965. 45. Hubel, D.H. and Wiesel, T . N . "Spatial and Chromatic Interactions i n the Lateral Geniculate Body of the Rhesus Monkey", Journal of Neurophysiology,Vol. 29, pp. 1115-1156, 1966. 46. Gouras, P. "The Effects of Light-Adaptation on Rod and Cone Receptive Field Organization of Monkey Ganglion C e l l s " , Journal of Physiology, V o l . 192, pp. 747-760, 1967. 47. Michael, C R . , "Receptive Fields of Single Optic Nerve Fibres in a Mammal with an All-Cone Retina", I : Contrast-Sensitive Uni ts" , Journal of Neurophysiology, V o l . 31, pp. 249-256, 1967. 48. Michael, C R . , "Receptive Fields of Single Optic Nerve Fibres i n a Mammal with an All-Cone Retina", III : Opponent Colour Uni ts" , Journal of Neurophysiology, V o l . 31, pp. 268-281, 1967. 49. R a t l i f f , F. "Mach Bands: Quantitative Studies on Neural Networks in the Retina", Holden-Day, Inc . , San Francisco, 1965. 50. Deutsch, S. , "Conjectures on Mammalian Neuron Networks for Visual Pattern Recognition", I . E . E . E . Transactions on Systems Science and Cybernetics, V o l . SSC-2, No. 2, 1966. 51. Kulikowski, J . J . , "Adaptive Visual Signal Preprocessor with a Finite Number of States", I . E . E . E . Transactions on Systems Science and Cybernetics, V o l . SSC-2, No. 2, 1966. 52. Rosenfeld, A. and Thurston, M . , "Edge and Curve Detection for Visual Scene Analysis" , I . E . E . E . Transactions on Computers, V o l . C-20, No. 5, 19 71 53. Shannon, C . E . , "Prediction and Entropy of Printed English" , B e l l System Technical Journal, No. 30, pp. 50-64, 1951. 54. Thomas, G . B . , "Calculus and Analytic Geometry", Addison-Wesley Publishing Company, Massachusetts, Third Edi t ion, 1961. 55. Goldsmith, A . N . , Van Dyck, A . F . , Burnap, R.S. Dickey, E . T . and Baker, G . M . K . , " Frequency Modulation", RCA Review, Princeton, New Jersey, January, 1948. 172 56. Harmuth-, R . F . , "Applications of Walsh- Functions i n Communications", I . E . E . E . Spectrum, pp. 82-91, November, 1969. 57. Harmuth, H . F . , "A Generalized Concept of Frequency and Some Applications" , I . E . E . E . Transactions on Information Theory, V o l . IT-14, No. 3, May 1968. 58. Golay, M . J . E . , "Hexagonal P a r a l l e l Pattern Transformations", I . E . E . E . Transactions on Computers, V o l . C-18, No. 8, August, 1969. 59. Preston, K . , "Feature Extraction by Golay Hexagonal Pattern Transforms", I . E . E . E . Transactions brt Computers, V o l . C-20, No. 9, September, 1971. 60. Hartl ine, H . K . , "The Receptive Fields of Optic Nerve Fibres" , American Journal of Physiology, V o l . 130, pp. 690-699, 1940. 61. Barlow, H . B . . "Summation and Inhibition in the Frog's Retina", Journal of Physiology, V o l . 119, pp. 69-88, 1953. 62. Lettvin, J . Y . , Maturana, H.R. , P i t t s , W.H. and McCulloch, W.S., "What the Frog's Eye Tells the Frog's Brain" , Proceedings of the IRE, November, 1959. 63. Brown, K . J . , "Dendritic Fields of Retinal Ganglion Cells of the Rat", Journal of Neurophysiology, V o l . 28, pp. 1091-1100, 1965. 64. Hubel, D.H. and Wiesel, J . N . , "Receptive Fields of Single Neurons in the Cat's Striate Cortex", Journal of Physiology, V o l . 148, pp. 574-591, 1959. 65. Hubel, D.H. and Wiesel, J . N . , "Receptive Fields and Functional Architecture in Two Nonstriate Visual Areas (18 and 19) of the Cat", Journal of Neurophysiology , Vol . 28, pp. 229-289, 1965. 66. Hubel, D.H. and Wiesel, J . N . , "Receptive Fields of Optic Nerve Fibres in the Spider Monkey", Journal of Physiology, Vol . 154, pp. 572-580, 1960. 67. Hubel, D.H. and Wiesel, J . N . , "Receptive Fields and Functional Architecture of Monkey Striate Cortex", Journal of Physiology, V o l . 195, pp. 215-243, 1968. 68. Levick, W.R., "Receptive Fields and Trigger Features of Ganglion Cells in the Visual Streak of the Rabbit's Retina", Journal of Physiology, V o l . 188, pp. 285-307, 1967. 69. Wagner, H . G . , MacNichol, E . F. and Wolbarsht, M . L . , "The Response Properties of Single Ganglion Cells in the Goldfish Retina", Journal of General Physiology, V o l . 43, No. 2, pp. 45-62, 1960. 70. Hart l ine , H . K . , "The Response of Single Optic Nerve Fibres of the Vertebrate Eye to Illumination of the Retina", American Journal of Physiology, V o l . 121, pp. 400-415, 1938. 173 .71. Hartl ine, H.K. and R a t l i f f , R,, "Inhibitory Interaction of Receptor Units i n the Eye of Limulus," Journal of General Physiology, V o l . 40, pp. 357-376, 1957. 72. Glezer, V . D . , "The Receptive Fields of the Retina", Vision Research, V o l . 5, pp. 497-525, 1965. 73. Van Nes, F . L . and Bouman, M . A . , "Spatial Modulation Transfer in the Human Eye", Journal of the Optical Society of America, V o l . 57, No. 3, March, 1967. 74. Schade, O . H . , "Optical and Photoelectric Analog of the Eye", Journal of the Optical Society of America, V o l . 46, No. 9, Sept. 1956. .75. Trabka, E .A. and Roetling, P . G . , "Image Transformations for Pattern Recognition using Incoherent Illumination and Bipolar Aperture Masks", Journal of the Optical Society of America, V o l . 54, No. 10, October, 1964. 76. Graham, D.N. , "Image Transmission by Two-Dimensional Contour Coding", Proceedings of the I . E . E . E . , V o l . 55, No. 3, March, 1967. 77. K e l l y , D . H . , "Image-Processing Experiments", Journal of the Optical Society of America^ V o l . 51, No. 10, October, 1961. 78. Kovasznay, L . S . G . and Joseph, H . M . , "Image Processing", Proceedings-of the IRE, V o l . 43, pp. 560-570, May, 1955. 79. L i g h t h i l l , F . R . S . , "Introduction to Fourier Analysis and Generalized Functions", Cambridge University Press, 1962. n 80. Papoulis, A . , "Systems and Transforms with Applications in Optics" , McGraw-Hill Book Company, New York, 1968. 81 Bennett, W.R., "Spectra of Quantized Signals", B e l l System Technical Journal, V o l . 27, pp. 446-472, 1948. 82. Cooley, James W. and Tukey, John W., "An Algorithm for the Machine Calculation of Complex Fourier Series", Mathematics of Computation, V o l . 19, No. 90, pp. 297-301, 1965. 83. Tomita, S. and Nouguchi, S . , "Recognition of Handwritten Katakana Characters", Electronics and Communications i n Japan, Journal of the Institute of Electronic Communication Engineers of Japan, V o l . 50, No. 4, pp. 174-183, A p r i l , 1967. 84. Rintala, W.M. and Hsu, C . C . , "A Feature - Detection Program for Patterns with Overlapping C e l l s " , I . E . E . E . Transactions on Systems Science and Cybernetics, V o l . SSC-4, pp. 16-23, March, 1968. Huang,...T..S..,.. S c k r e i b e r W . F . and Tretiak, O . J . , "Image Processing' Proceedings of the I . E . E . E . , V o l . 59, No. 11, pp. 1586-1609, November, 1971.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On the measurement of the curvature of the boundaries...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On the measurement of the curvature of the boundaries of two-dimensional quantized shapes Bennett, John Reavely 1972
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | On the measurement of the curvature of the boundaries of two-dimensional quantized shapes |
Creator |
Bennett, John Reavely |
Publisher | University of British Columbia |
Date Issued | 1972 |
Description | The use of the mathematical concept of curvature as a practical descriptor of shape for pattern recognition and image processing application is investigated. A mathematical analogy between the construction of a two-dimensional curve from a given curvature function and the frequency modulation of a sinusoidal carrier with a message, is drawn. It is shown that the curve describing the boundary of a two-dimensional shape is in fact a circle, frequency modulated with appropriate curvature information. The accuracy to which the curvature of the boundary of a binary shape can be estimated from a given quantized version of that shape, depends upon two factors in the estimation process: - the contour tracing algorithm by which boundary points on the quantized shape are defined and the method whereby the curvature function is smoothed to partially remove the quantization noise resulting from the digitization of the original shape. In this thesis, six contour tracing algorithms are described and used to extract curvature functions from quantized test shapes in the absence of smoothing of any kind. Models of the average quantization noise characteristics in the frequency domain are then developed for the curvature functions corresponding to each of the six contour tracing algorithms. The models are used to compare the performance of the six algorithms on the basis of the quantization noise characteristics of each. It is found that the useful bandwidth of curvature functions obtained from quantized shapes is somewhat less than the theoretical limit imposed by the Nyquist Sampling Theorem. The models developed serve to demonstrate the variation in the useful bandwidth of the curvature functions corresponding to each, contour tracing algorithm. The variation in bandwidth- with- quantizing array resolution can also be predicted with the models. The relationship between the bandwidth of a curvature function and the amount of detail representable in the corresponding curve in the plane is then qualitatively explored. Finally, three approaches to the problem of smoothing curvature functions to eliminate quantization noise are studied and methods are developed to compare their effectiveness on sample shapes. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-14 |
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.0093086 |
URI | http://hdl.handle.net/2429/32421 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1972_A1 B45.pdf [ 8.77MB ]
- Metadata
- JSON: 831-1.0093086.json
- JSON-LD: 831-1.0093086-ld.json
- RDF/XML (Pretty): 831-1.0093086-rdf.xml
- RDF/JSON: 831-1.0093086-rdf.json
- Turtle: 831-1.0093086-turtle.txt
- N-Triples: 831-1.0093086-rdf-ntriples.txt
- Original Record: 831-1.0093086-source.json
- Full Text
- 831-1.0093086-fulltext.txt
- Citation
- 831-1.0093086.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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0093086/manifest