REAL TIME CODING OF HAND DRAWN CURVES by RICHARD STEPHEN SZELISKI B.Eng., M c G i l l U n i v e r i s t y , 1979 THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of E l e c t r i c a l E n g i n e e r i n g ) We a c c e p t t h i s t h e s i s a s c o n f o r m i n g to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August 1981 © R i c h a r d Stephen S z e l i s k i , 1981 In p r e s e n t i n g requirements this thesis f o r an of British it freely available agree for that advanced Columbia, understood that Library shall for reference and study. I for extensive be her copying or shall t /ectrica.1 The U n i v e r s i t y o f B r i t i s h 2075 Wesbrook P l a c e V a n c o u v e r , Canada V6T 1W5 Date DE-6 (2/79) A«ju<t lo j 196/ the publication not be of further this Columbia thesis this my It is thesis a l l o w e d w i t h o u t my £~n^; nee<-"^y make head o f representatives. permission. Department of copying of g r a n t e d by the University the h i s or f i n a n c i a l gain the that s c h o l a r l y p u r p o s e s may by f u l f i l m e n t of degree at I agree permission department or for in partial written Abstract This thesis examines some c o d i n g of hand drawn c u r v e s . techniques f o r the r e a l - t i m e These c u r v e s a r e drawn on t a b l e t or o t h e r g r a p h i c a l i n p u t d e v i c e . a data As they a r e drawn, they are coded f o r t r a n s m i s s i o n over a d i g i t a l l i n k and r e c o n s t r u c t e d at a receiving terminal. The r e a l time r e q u i r e m e n t a l l o w s system t o be used f o r i n s t a n t graphical communications. this One p o s s i b l e a p p l i c a t i o n i s as a s k e t c h p a d f a c i l i t y t o a i d t e l e p h o n e conferencing. The points techniques examined i n v o l v e sending parametric The i n t e r p o l a t o r used i s t h e cubic spline. Several members f u n c t i o n s a r e i n t r o d u c e d and e v a l u a t e d . generating An two of t h i s c l a s s of technique t h e c o n t r o l p o i n t s (subsampling) i s r e v i e w e d , and Automated based on i n f o r m a t i o n i n t h e o r i g i n a l c u r v e Test runs a r e made u s i n g t h e v a r i o u s t e c h n i q u e s , drawn. dimensional existing a new shape dependant a l g o r i t h m i s proposed. fitting control a l o n g t h e c u r v e , and u s i n g an i n t e r p o l a t i n g f u n c t i o n f o r reconstruction. for selected curve i s examined. and c o n c l u s i o n s iii Table of Contents Abstract Table List i i of C o n t e n t s i i i of F i g u r e s vi Acknowledgement ix 1 2 3 Introduction 1 1.1 Objectives 1 1.2 Approach 3 1.3 D e s c r i p t i o n of s y s t e m 5 1.4 Structure 6 The C u b i c [C 1 of t h e t h e s i s - Hermite] S p l i n e 2.1 Spline functions 2.2 The one d i m e n s i o n a l 2.3 The D i g i t a l 2.4 The two d i m e n s i o n a l 9 9 formulation Differential Analyser formulation 14 18 20 A p p l i c a t i o n s of t h e S p l i n e 24 3.1 F l e x i b i l i t y and v e r s a t i l i t y 24 3.2 Hand 26 fitting and c u r v e design iv 3.3 4 5 6 7 The Applications Hermite to Cubic problem The 4.2 Determining 4.3 Applications 4.4 Continuity 4.5 Comparison of the 33 Interpolator 4.1 Segmenting Videotex 37 formulation 37 the 38 slope to Digital Signal Processing requirements 59 63 techniques 67 Curve 68 5.1 Subsampling 69 5.2 Other 73 5.3 Derivative 5.4 Direction 5.5 Corner 5.5 Relationship Automated techniques and and 6.1 Traditional 6.2 Non-linear 6.3 The 6.4 Limitations to 7.1 Error 7.2 Comparison 7.3 Other and 75 segmentation reconstruction reconstruction Fitting methods methods iterative and estimation inflection detection Curve Experiments angle solution method 81 88 95 96 97 102 106 112 Results measures of coding 115 115 techniques techniques 121 126 V 8 Conclusions 129 8.1 Discussion 129 8.2 Applications 132 8.3 Further 134 8.4 Summary research 135 Bibliography - A p p e n d i x A: 137 F o r m u l a s and derivations A.1 The Hermite cubic A.2 The Digital Differential A.3 The ellipse drawer A.4 The circular A.5 The polynomial A. 6 The sine A.7 The least A.8 E r r o r measure a l g o r i t h m Appendix B: 141 Analyzer 142 144 three point fits filter squares 141 fit 145 147 149 fit Sample R e s u l t s 151 152 154 vi List Figures 2.1 The b r o k e n 2.2 The c u b i c 2.3 M a p p i n g a segment into 2.4 The H e r m i t e C u b i c Basis 2.5 The g l o b a l H e r m i t e c u b i c 2.6 A parametric 3.1 Curvature 3.2 Effect o f t a n g e n t m a g n i t u d e on c u r v a t u r e 27 3.3 Effect o f t a n g e n t d i r e c t i o n on c u r v e 28 3.4 Curves designed 3.5 Hand f i t t i n g 3.6 Node r e p r e s e n t a t i o n s 3.7 Ellipse 4.1 A circular 4.2 C i r c u l a r completion 41 4.3 Parabolic 43 4.4 Bessel - 1D 44 4.5 Bessel - 2D 45 4.6 Akima - 1D 47 4.7 Akima - 2D 48 4.8 Quartic, uniform mesh - 1D 50 4.9 Quartic, uniform mesh - 2D 51 7 point interpolator 10 spline interpolator 12 (0,1) 15 functions basis representation 17 functions of a c u r v e of a p l a n e c u r v e with Hermite cubics a design drawn w i t h 4.10 The s i n e 4.11 line of curve f o r the e l l i p s e cubic a r c through segments 3 points f i t to 3 points function Hanning filter 19 21 25 shape 29 31 32 34 39 54 - 1D 56 vii 4.12 7 point Hanning filter 4.13 Smoothing e f f e c t 4.14 Least 4.15 FIR sine 4.16 FIR filtering 4.17 Impulse 4.18 Discontinuity in derivative - 1D 66 4.19 D i s c o n t i n u i t y i n d e r i v a t i v e - 2D 66 5.1 Increase 5.2 Subsampling - 4 different 5.3 Reumann and Witkam's s t r i p s 5.4 Williams' 5.5 C u r v e d e r i v a t i v e and 5.6 Least 5.7 Treatment 5.8 Mapping 5.9 Segmentation b a s e d on 5.10 Segmentation for 3 d i f f e r e n t 5.11 Quartic f i t t o sampled p o i n t s 83 . 5.12 Optimal f i t t o sampled p o i n t s 84 5.13 Effect 5.14 Thresholding 5.15 R o u n d i n g of c o r n e r s 5.16 M i s l o c a t i o n of a c o r n e r 5.17 A corner 5.18 S t a r t i n g the segmentation 5.19 Segmentation with of 60 i n t e r p o l a t o r response impulse 60 response 62 62 r e p o n s e by superposition in density angle squares 57 least-squares squares slopes filter - 2D near c o r n e r s 64 (subsampling) 70 rates of 72 tolerance 74 measure 74 angle measure 76 fit of end 78 point derivatives transformations of m i s s i n g used for arctan direction inflection is a local 80 change 82 thresholds 82 points inflection 86 points 86 interpolation 87 90 extremum o f corner function angle angle in detecting during 78 search G' beyond t h e detection 90 corner ... 92 93 vi i i 5.20 A segmented fragment of script 94 6.1 Smoothing 6.2 Decomposing 6.3 Incorrect f i t o b t a i n e d from 6.4 Alternate decomposition 6.5 C u r v a t u r e d e r i v e d from 6.6 D i s t a n c e measured p e r p e n d i c u l a r t o t h e c h o r d 105 6.7 The 108 6.8 C o n t r o l of the 6.9 Antisymmetric t a n g e n t s on a c i r c u l a r arc 111 6.10 Overshoot t o non-symmetric fitting 113 7.1 Points in original 7.2 D i s t a n c e measure u s e d 7.3 Visual 7.4 Chain f i t of a c u b i c p i e c e — an x-y curve into 1 dimension i t s x and y components above 101 3 points 103 effects encoding iteration vs. and 100 101 o r t h o g o n a l c o o r d i n a t e s (u,v) due 98 111 curve r e c o n s t r u c t e d drawings t o compare c u r v e s absolute error 116 118 120 127 ix Acknowledgement I would guidance I like and would of relevant 9054. I Shlien fellow of also throughout Dr. also for Uri like their Dr. the Ascher his to Mabo R. Ito course of this for agreeing valuable thank helpful a Dr. for his work. to read suggestions David suggestions Postgraduate from the Engineering acknowledge graduate and acknowledge and am g r a t e f u l professors thank and Benjamin and my and provisions references. Assistantship I would Sciences form to providing gratefully Natural the thank for I Seymour I to and corrections. Dr. like encouragement like manuscript to the financial University for a l l teachers the and have of help for been assistance Research Council Scholarship the students, financial under assistance British and the to and advice in the Canada in the of a grant A Teaching Columbia. given inspiration me of of the to that past. me by my various 1 Chapter 1 Introduction The problem studied in the drawings are of field s t i l l communications. for storage to engage in This drawing coding automatically time, the so that remote locations 1.1 a problem. type can In coding of these Systems allow people that has been many years. Line of interpersonal is necessary both perform the that in be of particular, code hand remote This locations long-distance it general is line desired curves in of system between people would in to real near-instantaneously type communications the drawn reconstructed location. of for means subproblem efficiently they one communications. addresses graphical — a primary data is graphics transmission. receiving interactive the graphical and drawings computer of graphical thesis line efficient for of of one The and transmission coding at allow separate sketchpad. Objectives In a classic paper Line-Drawing Images" philosophical and processing. on [23], Freeman theoretical What information conveyed information which must is by be the "Computer points considerations actually the out line preserved being drawing" by a Processing many of of the basic underlying such processed and it coding/decoding is "the is this system. 2 Freeman points sources: out that abstract dimensional line geometrical (halftone) images. those curves of the results obtained in the area of display of the storage and Both classified inputs derived by Freeman and Thus, efficient coding manipulation reasons, of Any as are in going representation the the such is such also of as itself to Some applications line for drawings since are of two [35][46]. are both the themselves thrust pictures of arcs the or from is line towards the transmission, the interest. implementation in method succeeded. drawings special the For and these resolution drawing drawing is curves lost computer never if or be as they splines. drawing involves can a such input However, not inside primitives, actual necessarily original. contained has primary and curves. have manipulation, processes the reconstructed of of geometric of reproduction drawn to curves terms The the seen line segments, internal hand represents straight-line process restricts three important. that so be from tracing, transmission types objects originate thesis i.e. also the of of This geometric while these scheme do Thus, will can models, tracing, considerations independence must by outputs drawings. drawings to an quantization. be the a perfect information distorted, then the 3 The from that overlap the of do of one coding The contour also Some will take advantage shape information. for Preservation of features"[22]) be traded techniques available outside 1.2 the while real-time information is the area primary will curve the use will of drawing of will also curves for be to use to is only examine drawn ("the curves. significant Thus, fidelity Some sequential of (such possible. coding. the hand (subsampling) is hand of information course of of for curves try then, Applications coding time form coding other consideration. efficiency tracings. of others coding in The and research, areas parametric of are different although techniques techniques this against a coding sequential the the using is of the information these techniques discussed. Approach The problem transmission approaches the of investigated from the this, Hybrid off coding, segmentation of the of curves considerations. that the objective techniques must of waveform from in available. The new differs plots) dimensional necessity introduces curves two dimensional occur. curve drawn as problem basic context of has used method the of been coding examined have used been should previous work. previously. different be efficient However, from explained that and storage and since the presented situated in here, the 4 The technique using the that are the breakpoints sent. points The — is then Some interaction to aid knots has the control a been of the that is both has coding, data points passes through automated relied placement f i t t i n g Some [41][47], for picture. examined, technique. proposed as the the widely curve work in problem the curve points previous The also - reconstruct computer been decision must control this simple these user spline but but on of a and with is an segmentation are designed interpolation. Freeman whether the should they here to the have segment segmentation the procedures taken to of iterative As the used of off-line linear is interpolator [3][6][30]. variable for of An generation real-time. points used points segments be is in order to the approach to should small add allow a out, and "be opposite to large greater complexity small a in to and few number" the be in [23]. made number, The interpolating number of points that of chain to be as or approach algorithm sent. encoding to This taken is by Freeman. Some techniques approaches include minimum-energy interpolating and more for recontruction quadratic curve approach B-splines associated with includes sophisticated involve the techniques [3] [ 3 0 ] , chain simple such smoothing. encoding linear as FIR Such and the [22], The interpolant, f i l t e r i n g [46]. 5 The interpolant The approach original curve generated these and sent points are interpolator, define 1.3 the as described. drawn, along to only the 100 control data of the as At using are the a number cubic•spline. follows. points link. small and to Even of keep so, the running of As the periodically receiving cubic For end, spline points based needed with not applications software library 12 a bit The resolution as to is device, design written routines for in and a through the real-time fitting) a custom of was with graphics. the done is storage 7000 Megatek 10 and vector 7000 animation is 840 input tablet for be Nova rate sampling Megatek Since a graphical the bits FORTRAN, the the hardware should on sampling of 12 resolution. curve was to done attached research, as used The maximum device storage was RDOS. tablet converted output research hardware research this The the the under data control. The unit made Hz. manipulation. callable case summarized minicomputer. is The special system bulk which refresh a Computek software display be the possible. a is bits, a interpolated, was The is tablet such is minicomputer interface a thus of attempt device is interpolator. independent 16-bit here can with Description An under used is (for possible. special FORTRAN The software 6 development was for acquiring the pictures modular. drawings reconstructing error kept from the Separate tablet, in various ways, the drawings using measures, and programs were written segmenting and coding calculating the interpolation, displaying the derivatives, generating drawings on the the output device. The this actual thesis plots, were figures, generated f a c i l i t y , an Amdahl was on Calcomp and drawn with the Integrated V-8 running graphics routines available drawings residing on data was transferred link (HDLC). coded 1.4 A drawings into Structure The Chapter 2 *IG of segments the Nova MTS. A l l plotters, package MTS. had In to of those be written form suitable for the output been generated FORTRAN callable where actual the coded reproduced, then in computing graphical cases was a included UBC having program an interprocessor to convert the plotters. thesis the C is under through introduces representation main system the given, the MTS of is using the the A tables (*IG) on remainder representation. and Houston Graphics to graphs 1 simple and presented thesis cubic spline algorithm the and is two structured and for the follows. Hermite calculating dimensional discussed. as the basis cubic parametric 7 Chapter The 3 presents versatility makes it as to a interpolator are new techniques Subsampling and algorithm for deals is are one also and with shape of parametric design given, spline. representation and with this curve the drawing. spline being primitive. and reviewed for its on the two dimensional determining compared 5 the cubic 1 spline data. derivative as an Various old at the nodes evaluated. the and C problem is found dependent of to curve be a segmentation. good segmentation is technique. then A presented discussed. Chapter curve coding 6 reviewed A and introduced shows to 7 presents the coding measuring algorithm made the better to f i t t i n g achieve a can be good automated fit without (non-paramteric) be unsuitable. the results A for new the user approach is technique is discussed. evaluating using curve traditional found and Chapter how problem, interaction. for both applications curve elaborates for Chapter new for the in geometric 4 presented, of spline Videotex new Chapter and the useful Applications proposed of some methods is various and of techniques presented. techniques variations are The this research. discussed, results are then are selected. of and the discussed, The Criteria an error test runs and best the coding 8 methods to emerge Chapter from 8 contains methods developped relative merits. are then adoption. The that sample the the 7). in are also are tabular shown error and for for of the further and comparative of form, purposes. discusses and made best their techniques as to their mentioned. appendices. Appendix (as various the are obtained and and of B contains algorithms performance summarizes research summaries were identified. algorithms two Appendix that graphical It recommendations used. results thus research, contains coding/reconstruction The this and areas are conclusions. derivations algorithms of the Applications F i n a l l y , the research during discussed, thesis contains this from the formulas an test actual and illustrative runs discussed techniques A in is made Chapter given reconstructed on both drawings 9 Chapter The This chapter be used as in this thesis. case the of Cubic presents The Hermite "splines". are 2.1 functions Spline cubic functions by pieces There of are in case are of a spline cubic consists of spline. This introduced as one- two-dimensional the research w i l l cubic is the function for and called is the and a is cubic extra they spline segment were described a special f i r s t examined been fields composed term not is be each of used as curve polynomial degree These that are pair too afford A simple 2.1). The of k). need far they (Fig. 4. < that examined. interpolator order of splines f l e x i b i l i t y between general methods. [1][12], of of have generalized w i l l class diverse order pieces broken-line a such are highest polynomial for in that a They finite-element (the functions of functions 1940's. 1960's and member These the k spline a Spline function simple functions application, of a the numerically our A in order consist complex is "splines". since other cubic Both interpolation Splines not spline mathematicians f i t t i n g , Hermite] presented. called extensively - 1 the interpolating formulations The [C 2 function breakpoints. Fig. This is 2.1 a The simple broken example line of a interpolator spline function. 11 Many authors use the continuous in its be to here referred various orders different detailed term f i r s t as and on splines as sufficient f l e x i b i l i t y of w i l l the reconstructing "Given can the of the N data be cubic Thus, {(x ,F(xi)} x 2.2). on any of are the data f ^ ( x ) = a i has 4 parameters determined. For as it is the cubic 3 x 3 the smooth the data stated we standard of this is of solved as through them." problem. simple) in to In the choose points. subintervals points, more complex. be (and many spline be curve of for any must interpolation natural to in unnecessarily can w i l l and cubic which a used purposes the is functions these, found which function are the drawing pass correspond Each being (sampled) points, be For sub-problems spline, to can a Spline of later, without function conditions shown to a Such spline". Descriptions referred breakpoints (Fig. "smooth be coded such derivatives. formulations, key a for [1][17][45]. research, case a applications. reference This k-1 continuity mathematical One "spline" (x ,Xi x + 1 have a cubic x + a\. ) where the polynomial polynomial + {a^j}. a i 2 x There interpolation, + 2 are we a x l thus must 4(N-1) have 0 parameters to be 12 Fig. A piecewise-cubic 2.2 The c u b i c function that spline interpolator passes through the data points,. 13 fi(xi) This ties = Fi up and two f i ( x x + ) 1 parameters = F on x + each i 1 = segment, 1,2,...,N. leaving 2(N-1) free. The "smooth derivatives be spline" requires continuous. f l ( x t+ 1 ) This that the yields f i r s t the and second conditions f 'i+ 1 ( x ^ ! ) = + and f Y (x This leaves values to The , ) x + two = smooth choice property of x + f'(x,) [18], Bessel are spline i for and has and several has greater later. a l l in spline f i t t i n g but sufficiently to piecewise-cubic Hermite f i r s t order derivative cubic or C that is It cubic 1 also In that has accuracy to set make the of the used spline the calculation required. to such available. Some simplified as of This recent these application. is [45,pp. addition a second methods have be it smoothness application. our giving than be for by ) . N norm [29][31] w i l l usually properties curve-coding continuity). continuity f ' ( x points advances the the N use The = However, its not are integral precludes calculations, for 1,2,...,N-2. which f ( b ) the presented requires = interpolation. minimizing derivative , ) parameters, spline popular the f \l , ( x free f'(a) that = variously 24-29] (C known 1 interpolation, as refers f i r s t 14 f ' i ( x u i ) These the N in must in arises this draw f i t t i n g the 4. The algorithm simple receiving approaches ) i i = = 1,2,...,N-2 1,2,...,N}, one As can can then be be chosen as segments To (0,1). achieved by by for determines the these along can then and send algorithm this is to (interpolator) for e a c h F{ , are have sample a and investigated sophisticated optimal slopes from with sample points. the draw the comparisons the cubics. A Both drawn. formulation from the consist two matters, retaining the doing w i l l This to Methods sends whose is approaches values seen simplify approach coding slope investigated, curve the reasonable terminal be f i r s t in reconstruction dimensional interpolating known. The s p l i t second approach that and will The values 1 , The cubics. drawing into + fundamental only. input cubic the determine Chapter 2.2 i ( x i research. points then then + parameters. Here (data) f ' i slopes,{f'(x^) free used = of we data discussion, drawing endpoint w i l l normalizing the above values map a n y a connected and and slope of values are (xi,X( (Fig. multiplying the set segment transformation values drawing 2.3) the + 1 ) is slope Fig. This 2.3 Mapping normalising by a segment function multiplying the f s into is by (0,1) achieved d-. 16 d i Given - cubic far that The representation are also basis >(1) in known functions - t ) involves as blending are defined + the use of functions basis [4] [ 2 0 ] . as 2 F i g . 2 . 4 , and have detailed i,j = 0 is e representation The local its advantages of these 0 construction + - following other ' ( : jth of properties: of bases is 0 then derivative cardinal c a n be found g(1) * g'(1) property f property the cubic g(o) * ( t ) g'(0) *,(t) over {0,1}, a general d i s c u s s i o n of = the = 6 ij orthogonality g(t) + 2 2 a r e shown The is 3 * i < i ' (0) more and g ' (1) these = (2t + 1)(1 = t (1 t ) 0 This g ' (0) conditions [ 2 g ( 0 ) - 2 g ( l ) + g ' ( 0 ) + g ' ( D ] t [3g(D - 3g(0) - 2 g ' (0) - g ' (1)] t g' (0) t + g(0) cubic • i i , the end matches which l x -i. elegant •* (t) *,(t) These , with = more functions, + g(D , g(t) A l the cubic g(0) the x in very of bases. f A [20], simple: d - t ) + *,(1-t) the Hermite such as basis is one of B-splines. The *l(t) g. 2.4 The Hermite Cubic Basis functions 18 parameters value and visual that the first It formulation The global is the used can be basis This effect again allows of each when is a derived spline of other required, the function for a good the four of the local two-dimensional one. [1][21] is An where limited equivalent the to two support intervals (i.e. the the consists DDAs are algorithm because only c i r c l e only of by efficient cubic of the is no integer numerical set of derivatives given very and 155-156], in is Appendix is errors, need or an derivation and It is should much be faster divisions are used. Unlike The accuracy is controlled by exact. which in A. It be equations function The efficient. arithmetic it needed technique difference multiplications drawers) roundoff representation polynomial. a [I3][26,pp. algorithm this an the values Analyser two-dimensional drawings, fashion and the evaluating for that limited to algorithm incremental noted of for solve summary Differential passing coding The DDAs the representation Digital introduced than value. are 2.5). The that behaviour introduced. cardinal Before for of be representation (Fig. function derivative w i l l above each 2.3 the representation parameters. of control can be many 19 B (x) 2 i Fig. These are 2.5 The obtained global by Hermite mapping domains of the cubic basis local basis support. functions functions onto 20 appropriate scaling. It does not introduce any systemic errors [16]. The uses of cubic splines [35]. Their given set presented 2.4 The curve, most i.e. and a a of set = = may to Chapter values Moss to and for Lindgard interpolate some of for a the a techniques 4. formulation representation parametric to equations may two-dimensional 90-94], cross functions x y in by splines relationship explained generate proposed smooth functional curve been to and i t s e l f . of a be used. curve provides Using parameter s two-dimensional This f l e x i b i l i t y , approach, (Fig. the representation great this is both x 2.6). (s) (s) representation for the curve is achieved by using notation. f (s) = notation (space Its approach compact vector The uses dimensional become more is devise the y points. here equations previously 50-51][21][42,pp. x y A of common [l,pp. has technique two To difference curves). ( can x (s) thus , y be (s) ) easily extended to three dimensions 21 Fig. 2.6 Both A parametric x and y are representation functions of a of a parameter curve s. 22 The along parameter the maintain also y This smoothness. It the by has S = si., + (Ui-x = s i. , + | we m a p a n y € s on found as to the the arc-length arc-length that good cumulative is used results chord to are distance points. 0 t been setting = i related dependence s, If into is • usually curve. obtained between s - segment the (0,1), f i v , ) + 2 f i. , of ) 2 ' 1 2 | the function ( y i - y i . ! ) cubic f_ i s spline obtained by s e (s\,s-i summing the + 1 ) x and natural to components. f(t) = f_(si) * (t) f ' ( s i ) = F\ + 0 di *,(t) * (t) + 0 F'i di f ( s i F (t) l - + , + ) 1 * (1-t) f ' ( s * ( 0 F\ , i + 1 i-t) di + + 0 ) di *,(l-t) + *, (1-t) where di The handle units. = than the These evidently breakpoint. i.e. is F quantities breakpoints. that | i + 1 F \ - Fi | • d\ and F \ + , • unsealed derivatives, quantities For require the that However, required is that represent f_ the function the for the f/(s) a visual tangents di as are more they come tangent out vectors to be be continuous effect l i e in in C 1 of the screen at the continuous, at continuity, same we each a l l direction, 23 f \ ( s The i effects Chapter A + ) 1 of = k not i + requiring final in note on vector [34], underlying coordinate orientation the form, isotropic any f ' 1 ( s i + 1 ) strict continuity are discussed in 4. expressed in • that is, parametric it evident independent system. with is curve equal This ease. of allows representation. that the the the curve orientation coding When of of is the curves 24 Chapter Applications This of the chapter piecewise-cubic hand-fitted curves, discussed. use in 3.1 The strict f i r s t Fig. 2.5) both in in effects curve of curve a at magnitude curvature is of where two where curve possible, node. the advantages (spline). and of the choice Applications to c i r c l e drawers are as primitive for a new systems. of of Hermite the two allows basis This for locality cubic is its functions (see is an real-time reduces advantage processing, the extraneous change. is as is The curve the intervals. locality advantage that the proposed support to design, second node The small is advantage limited coding, A each is cubic Spline versatility major locality. of design Videotex and the polynomial Hermite F l e x i b i l i t y of some curve alpha-geometric The and discusses 3 that limited control of curvature derivative is control the curvature direction directly (Fig. of 3.1). dependent The of on formula at the the for is ii' r p = , | This curvature f' x is f' ' p : radius of curvature | defined at a l l points excepting the 25 Fig. 3.1 Curvature of a plane curve 26 breakpoints, here, the of where however, magnitude various form the of The piecewise only can a tensed shape and on the same Fig 3.2 shape of as limiting is to as related the in to effects parametric tensed magnitude curve Even curve. control the f_' ' . shows the similarly case in curvature derivative behave limiting the of vector. with to slope direction of curve the magnitude curve 3.2 line, discontinuity in splines approaches the case 0 of splines. The the cubic shown a impression values The straight be tangent derivative be may visual the [15][25][37]. is there design Hand The and simplification [21]. completion by the of (Fig curve applicability from 3.3). gives f i t t i n g f i t t i n g apparent design (Fig control and (tangent) of Similar used combination basis basis to examples. has work Rutkowski this be great to of control direction f l e x i b i l i t y in 3.4). this that The also design previous one can [44], been in In used this and curve area design fact, this by is should Dube that interpolation basis for done by be is a curve in shape Midgeley [34]. The has the work extra done by Dube f l e x i b i l i t y and uses a more precision complex needed basis, for curve and thus design. Fig. As the 3.2 Effect magnitude shrinks curve of tangent the magnitude apparent collapses to a tension straight on curvature increases line and the Fig. 3.3 Effect of tangent direction on c u r v e shape 29 Fig. Great 3.4 flexibility Curves designed with Hermite i s p o s s i b l e by a d j u s t i n g direction of the tangents. the cubics. magnitude and 30 The cubic basis, however, composition, such program written nodes was and changing graphically method as as was the major incentive the fit, the allowing cubic The major minor major-minor The It raster vector devices database curves which 3.5). It hand f i t t i n g similar further research by moving found the that this curve This into A represented the work). drawing entry. were was non-interactive of be this is given intercepts give drawer to a success was automation of coding. in display. this well [19][27]. The form, technique [36][42]. parametric spline using A by four integer and that ellipse representing An point a the alternative and one several parameteric in vector conversion more c i r c l e 3.6a). is use good if discovery set of 3.6b). form as the points center for Other as efficient (Fig. (Fig. was an the intended raster research used as intercepts [10][16], to the to is (calligraphic) proposed can is axis for of simple drawing axis e l l i p s e [42]. [6] ellipse representation values, for for Videotex design (Fig byproduct drawer. and slope in in the real-time, e l l i p s e Hermite allow (see adequate used satisfactory drawing Another be tangents also and to the previous Circle may is a vector algorithms method graphics have designed especially of segments required, line is a well been for from established detailed discussion of the arithmetic can in [35], be found 31 Fig. The procedure i n i t i a l 3.5 goes Hand from interpolant, f i t t i n g a specifying modifiying design. the design the curve nodes slopes to and getting to a an final 3.6 Node r e p r e s e n t a t i o n s a) center 4 major-minor axis and 2 m a j o r - m i n o r for the ellipse intercepts axis intercepts 33 The try f o r m u l a t i o n f o r any q u a r t e r segment t o match c u r v a t u r e a t t h e n o d e s . segment between f(t) r_, and = jr ( F i g . 3.6b) 2 r, # (t) + 0 3 / r 0 T h i s makes t h e implementation simple fast. While approximation to true relative i s less and greater 3.3 error accuracy Videotex database retrieval store and the system [7] The for i s an coding 0 segment Hermite DDA is (Fig. 3.7), very only the an maximum those a p p l i c a t i o n s where the Hermite c u b i c make i t a g r a p h i c s element in a Videotex generic TV set. graphical. and *i(1-t) the i t i s a good a l g o r i t h m . of name s y s t e m s where t h e graphics, alpha-mosaic (li-r ) cubic For simplicity i s the (or o f f i c e ) textual and candidate system. a home 2 cubic %. required, assumption, to Videotex versatility attractive the ellipse 2.8 than i s not Applications The an the V + the this we + 0 of if is * (1-t) 2 *i(t) (r.2-r ) 2 Under i s obtained The two o f an scheme u s e d Description geometric primitives popular [11][8]. stored is The i n the T e l i d o n straight lines PDIs and Canadian on both used approaches alpha-geometric Instructions, are computerized information i s displayed information most alpha-geometric Picture to Many t e c h n i q u e s a r e c u r r e n t l y the example given to being Telidon system. system [9]. circular consists The of current arcs. The ' 34 Fig. 3.7 E l l i p s e drawn w i t h c u b i c segments A t r u e e l l i p s e , and a c u b i c e l l i p s e w i t h 16 l i n e p i e c e s per q u a r t e r are drawn. 35 system also has future extensions. The in its coding extension to Coordinates packed is (control data as character) is used need following. extensions ARC [9,p. command In only must the slopes integer generate data step to is be d can generate to be add of sort in in arcs. the Only indicate the system left for thus very exact same the lead-in that spline have already their description to Telidon extension whether The If in d i ' s to the bypassed. circular the algorithm ( F V i = t the transmitted. segments. necessary can designers calculate exists). ' and to transmitted cubic points. in. be is is transmitted different an as should the step built made and F'ui This such shift necessary expansion be nodes should splines lines this codes of the 30]. proposing decision be of are for The anticipated unassigned cubic straightforward. form scheme It • are d i + 1 nodes and In former only (for which used to obtain ) (di d- / sampling interval be noted already • or case, / the 4. be a The used to computation good Chebyshev i) x + for is unevenly uniform, that has di then a system, slopes, other di smoothness arcs F't can obtain should the form (DDA) The the the the any spaced even terminal distance this that measure 36 Several slope in advantages representation. designing this presented simpler in the next compression (or decision adopt clear done Telidon. primitive terminal sketches the The in final could of a in could would as a in be This Videotex that reciever any reduced supported by only such cubic the in data A standard The a database). system, a of to lower can for research. communications. available algorithms is to and sections the including greatly is leading paid have analyses. is node determining price of a previous necessary, particular this be the requirements system, used coded interoffice The advantage be not technique Videotex then being are using f l e x i b i l i t y slope marketing context hardware/software graphical and in the storage either from greater discussed chapter higher the gained terminal. cost/benefit within as Secondly, receiving to be F i r s t l y , curves, chapter. can need be as spline Videotex hand-draw for setting new up 37 Chapter The This chapter problem: Hermite a set information), use curve. problem The proposed. Cubic presents given an Various a of slope sample The merits and performance are discussed, The To problem restate of the set the the free interpolation s i where + , = di On any = | interval fi(t) parameter = 0 s\ 5, = + d i F u i that F^s using is ( S i , S i (no and the original alternate solutions algorithms in derivative are presented of simplicity terms recommendations made. we Fi * (t) + + 1 0 given problem: of d a t a p o i n t s {F{ s u c h t h a t f_(si)=F_i , , s^ 51] such , ) required the only that [l,p. i=1,2,...,N}, i =1 ,2 , . . . ,N. " i = 1 , 2 , . . . ,N-1 Zi I " F'i d i A l l interpolation reconstruct methods and the formulation " G i v e n an o r d e r e d s e t g e n e r a t e a c u r v e f_(s) Here, to determining compared. to points formulated, and 4.1 Interpolator solution interpolator is 4 have F i *, (t) then sample is + - to 1 * 0-t) F' i + , obtain points. + 0 di * , ( 1 -t) local estimates of the 38 The Hermite to the FIR (Finite is interpolation [46]. theirs, and equivalent to research of the their the For but completion), the into two slope is scalar a F \ good f i l t e r i n g follows techniques used possible approach used along here solutions by the w i l l is that Shlien same be of and lines shown as to be slope the f i r s t one-dimensional weighted Z Fj = several Another here determination down of method. Determining a l l one Response) The some just problem. Impulse Allard 4.2 cubic sum method of the examined derivative subproblems. of the This sample (circular can be is broken because the points wtj j where the method w^j involves The Bessel, f i l t e r cross methods Akima's and Circular The the depend slope on the products examined method, least d|,. Only between are as higher the the follows: order circular completion F j ' s . circular completion, polynomials, the sine squares. completion idea is of taken passing from a c i r c l e Midgeley through [34]. 3 points Referring to to determine F i g . 4.1, . 4 . 1 The A circular angle arc through relationships are 3 points shown 40 t = satisfies d the r^/d, 2 + given yields the vector, in a below. To adjust angle direction form d, 2 / d 2 relationships (not the identical the r to magnitude) the magnitude {Appendix Bessel for a of A). the derivative interpolator circular fit, This described we use 4 I L\ I The endpoint arcs 2 + cose, derivatives + are cose 2 similarly calculated using circular [34]. As and attractive as smoothness, rounded prove not - of it drawings. this point. shrink to this proves An | r_^ to seems be is + because r_ | 2 terms example the does. in unusable illustrative This 0 as method of except on (Fig. 4.2) derivative The simplicity method the most should magnitude is not does further examined. Bessel For parabolic along the the Bessel (quadratic) with the fit case. summing the through remainder one-dimensional straightforward, interpolant, F^ of the slopes 3 points. chapter, Extension and F^ to to obtain are determined This will two F'. by a interpolant, be discussed dimensions in is Fig. Excessive 4.2 roundness Circular makes this completion interpolant unusable. 42 The and to new drop d\ where The di notation the = is vector x T- l + the divided followed sign difference = Si The be notation F (x i ) slope Si = the t slope through di this spaced reason, the F_\. be We to replace s t i l l s with x, have between is introduced F (Xj ) - Xj at x{, F[xi.,,Xi] = (Fig. + d i . , + F i and F_i + 1 . F'(x{). 4.3) is F [ x i , x i easily + derived. ] 1 d i . . contribute interpolator also S i 3 points points distance - di Closely will x •{ X let from two-dimensional F [ x i , Xj ] Also, here more performs to the well slope on value. unevenly For spaced data. For actual precision those greater The are (Figs. important, presented accuracy, Bessel 4.4 numerical interpolator and the here. higher 4.5). interpolation, Bessel For order is interpolant applications smooth shown on where a splines number is accuracy the best and of that require even are normally used. of sample data sets F i 1 + F. i-1 x V l i-l Fig. 4.3 Parabolic fit to 3 points 44 Fig. 4.4 Bessel - 1D 45 Fig. 4.5 B e s s e l - 2D 46 Akima's method Akima ripples [2] that introduced commonly interpolation. Si. The = occur slope | mi,-m |m 3 a |m„-m in |m + + _ 2 designed polynomial estimate 2 j 3 method to or eliminate smooth the spline is m, |m 3 |m -m | 2 1 with = = = = n»i n»2 m m This 3 ft method is fairly not allow spaced data. ripple + + 1 + eliminates closely 4.6 two 2 and However, 4.7). This the dimensions higher points is added accuracy However, simple the is higher locality that view the (see is to not be a presence of ripple For form), these It the slope measure with unevenly disadvantage is not as reasons, as both the also and linear. dominate can function does noticeable x(s) and y(s) method is not polynomials a a it interpolating further. order Using the (parametric simultaneously. Higher in spaced points Also, investigated 2 ripples efficient. (Figs. in F [ x i. ,x i. , ] F[x i. , , x i ] F[x i,x i , ] F [ x i , x ^ ] is next order (kth extension of gained, order the since from the a polynomial Bessel polynomials desirable section). order) interpolant. interpolant introduce signal through a processing Because symmetry is is k No cubic. decreased point desirable of in 47 Fig. 4.6 Akima - 1D Fig. 4.7 A k i m a - 2D 49 the coding need be of considered. quartic becomes weighting The weighted S The sum of = x the / should be divided differences, In added and performs simplicity the "ripple" quartic is reduced as mentioned dimensions. of the - to locality 1 a some well. two for (Figs. increase. the previously, 4.8 This method. are not r X i + 2 is are available is A). in for very mesh and as (constant) (Appendix made close actually effects It of together, has the constant. (Figs. 4.9), terms for non-uniform solution being Bessel The spacing ] formulation is The + equally mesh factors the i are nodes the complex. uniform a the i.e. F [ x uniform weighting a F [ x i . , , x i ] Vs the The results of 3 allowance unless the / 2 if in A). more expressed as uniform since (uniform) seen the ] + on that fact, Comparing + even etc.) even 5 products are simplified be for Appendix differences, , x i ] i formulation (see then (quartics, involving Solutions polynomials noted method 2 case. order this can divided higher the polynomials greatly F [ x i , x 3 quartic spacing. is F [ x i _ -We polynomials term order solution the 2 for each higher formulation assumed. even complicated, of for only Unfortunately, too factor formulations is drawings, 4.4 the a of and amount reflection this objectionable 4.5) of of ripple, in two Fig. 4.8 Quartic, uniform mesh Fig. 4.9 Quartic, uniform mesh 52 Between solution, the f u l l there exist approximating the p o s s i b i l i t i e s are: S\ = Si = the to as the that the to and fashion to Lindgard [35]. the mesh Lindgard computed. the smooth the 0 an case The is The / u Thus, spline. In The a f i r s t uniform emphasize both based Two on such is reminiscent differences methods, double method mesh closely determination. where nodes the of in spaced This are has will present desired. is also spline X i . 2 , x i ] F [ x j , x i the factors. mesh related in interpolant for the an used second interesting by Moss and of the Moss and calculation is approximation to moment is exact only techniques second method, slope solution F [ 8 on not advantage slope the notation). does smooth V the if for hybrid uniform 1 limiting quartic = is { mesh q u a r t i c 3 This a uniform t / the 2 the be M hj } and E hT } J E hj } j to be uniform { much. later The in as more 5), terms (dj's) contribute (Chapter of solution. points seen number / interpolant, sizes solution, h?} A its exact Bessel interval dominant Appendix advantage same a { E D ; / J { I Dj / J and (refer quartic same f i r s t the + ! ] - 3 - 1 solution term quartic in fit /« / 8 as F[xi.,,xi] F [ x f X that their is V 1 + 2 ] obtained moment really + an by 53 Sine f i l t e r s Sine commonly sine f i l t e r s used in function sine The sine are = (between by Shlien and interpolation The zero mesh and are is a [46] being most [39] f i l t e r s based for on the (FIR) f i l t e r , have in been this the this we same per by sucessfully the a used type of thesis. sine function concept get point approximated exactly of Extending inflection well f i l t e r s the one is examined of /k. windowed at sine A l l a r d (-1) interpolating processing crossings) These as low-pass IT X / having derivatives crossings signal tr x sin piecewise-cubic. of 4.10) function, interval class d i g i t a l (Fig. (x) a the to a at its 0 non-uniform simplified f i l t e r m S\ = E { F [ X i , x i + j ] + F[xi.: ,Xi]} (~1) J 1 w: j =1 where A). Wj The (linear is a window necessary precision) function and of width sufficient m condition is m E 2 (-1 ) J " 1 j =1 One suitable = W: J window is 1 , v. (details > 0 for in Appendix linearity Fig. 4.10 The sine function 55 Hanning: Other but windows, they w i l l precision it is in i<1, and This results closed in yield a the for N the are can "wrapped This is the As examples, same S x = S x = A around" approach the and m=3) V 2 used FIR [39], precision. are may be This used, lack of interpolation many simple Thus coded Hamming than reconstruction. closer (weather to in 0 = x case. possible solution F[x ,Xj] end-slopes being 2m) numerical there i>N. / or in two-dimensional data (m=2 curve j linear problem values. makes be 2 technique, Ft = F curves windows of end-point tr cos ( Triangular always more this handling >N. as two-dimensional With for such not is = WJ to For or set F i ^ F , i or j with or visual applications where maps), end-point splines for <1 good determine formulations to topographic periodic of is if 0, ways the values. [l,p. f i r s t the 15]. two Hanning are: F [ x i . 2 , x i ] + 1 / x i ] + V« ] - 2 F [ x x . , , x i ] and F [ x i . V, The response Figs. 4.11 of and the 2 F [ x i , x 7 4.12. f x point + 1 (m=3) 1 /„ F [ x f . 1 f F[xi,x{ Hanning x i ] + 2 + ] f i l t e r is given in Fig. 4.11 7 p o i n t Hanning filter Fig. 4.12 7 p o i n t Hanning filter 58 Relationship between Comparing (i.e. the from the This form. sine f i l t e r = { 2 = { 3 different actual Since the Least are most in Appendix 1 , 1 of for f i l t e r = the sine and uniform f i l t e r fact, the setting the quartic (uniform /« ) (Hanning, makes local, that fit they is are obtained quartic) m=3) very the always their polynomial solution mesh (compare polynomials f i t s weights } mesh mesh shows /6 weightings polynomial l i t t l e two yield coefficients difference set in of figures). linear precision w i l l be used. passing. This approximation method common Si , 3 more final the by f i l t e r s reconstruction squares One the In /« uniform and squares / set curve f i l t e r s , and in WJ i n s t e a d of WJ (sine) solutions quartic) identical FIR slope A). should f i l t e r , The be mentioned namely windowed, least inverse in squares distance is (derivation weighted least is m I w: j=1 {F[Xv,xi ; + J ] + F[xi_-. J , x j } J with m 2WJ I j = The only absence = 1 and wj > 0 1 difference of the between alternating this sign and (-1) J the - 1 . FIR This f i l t e r abscence, is the though, 59 is fundamental these two classes The The to FIR least of is a fit, but difference by is true on rather obtained behaviour between a hand, (Fig. piecewise different thus interpolating other smoother using is low-pass the a totally approach in f i l t e r s . squares representation squares major f i l t e r interpolator, response the unusable is 4.13). for not an The cubic (Fig. f i l t e r . actual interpolating 4.14). the The least interpolating application. This smoothing determining because the the local components. just this purpose. 4.3 Applications Splines being when an have set alternative on rate It will Digital been local. real-time complete to have They more slope sampling frequency [283[32]. f i l t e r , used the however, a hand drawn is much higher be used Signal advantage performance is of points. The to FIR f i l t e r s . in very useful in This is curve. the than next the signal chapter for Processing previously Smooth is over splines, in many DSP polynomial however, required, due Hermite cubic to are the can applications functions not need then be of suitable for used a as 60 Fig. 4.14 Least squares slopes interpolator response 61 A h(t) traditional in then a lookup table convolves (Fig. FIR implementation (Fig. the input stores 4.15). For points with the each the impulse output reponse point impulse it response 4.16). y(k) For a N, and Nm z x(k+j) j = -Nm = simple the subsampling f i l t e r order h(j) problem, is m, 2m m u l t i p l i c a t i o n / a d d i t i o n s Using weighted the sum Hermite of 2m the Nm t a b l e are cubic, where needed each subsampling entries for slope are each is rate is required and point. generated by a points. m Si = (x(i+Nj)-x(i-Nj)} Z w,j,* j =1 with w* Only m is point is Thus, in than the terms To needed 1 certain Wj / j factors to generate generated in a need FIR to be few addition/shifts use f i l t e r of and memory. see that the piecewise-cubic impulse response (to should within be F i n a l l y , Hermite be greatly is the in fact only The 2m more tap output the cubic DDA. rather efficient equivalent approximation examined. a each using the could time f i l t e r and slope. of sine stored, each applications, traditional traditional the (-1)J" weighting memory in = to a accuracy), normal Hermite h(k) 'Ill 1 Fig. i' I I I I2Nl I 4.15 FIR Nm v a l u e s sine are x(k) input signal impulse usually is 4.16 convolved FIR with response stored. y(K) h(k) Fig. The f i l t e r 3N f i l t e r i n g the impulse response h(k) 63 cubic cannot response be said consists of derivative at becomes a weighted response can The he {WJ} He can sets a is free any (being design free a low response, so the 6 .few near pass long set of linearity f i l t e r of arbitrary impulse the slope impulse 4.17). the the the single violate as and weightings condition). order response and maintains i} requirements data points problems at to choose The condition. = However, the sharp derivatives be arise that the assume sample corners, In A hybrid to breakpoints. when slopes. better. differences, to value when designer interpolators local However, divided reponse. data f i l t e r Continuity as 2.5). the (Fig. derivatives such sum o f both supersposition hi(j) data, (Fig. to impulse by thus spaced, true obtained desires When a reactions point interpolating 4.4 have be frequency the a to these method, to zero reconstructed with In fact, uniform for corners the is also next spaced, is given to as Bessel are chapter, usable. of best. unevenly such the types perform weight interpolators evenly scaling these become in fairly to spacing points presented at regards insufficient cases, are which 64 Fig. The response is 4.17 Impulse obtained the two by basis reponse by superposition function superposition of (Fig. weighted 2.5). r copies of 65 It has been transmit and to This = the F spacing fi(x) * (t) v = is a however, For with one since is a it the sine natural is need way in to to screen calulate the the + . 1 is di not limited the type need as derivative ( di 1 + 1 * 1 d - t ) 0 F'{ d{ + 1 + 1 *, (1-t) which (Fig. 4.18). scaling a would In since 2 the be very dimensions, direction of 4.19). would more must be then, the yield interpolating scaling + derivative applications, where write / d i in (Fig. for *,(i-t) we c a n as noticeable, f i l t e r for F', + + 0 uniform, dimension However, such i # (1-t) 1 - *, (t) maintained with complexity. points, F' effect is di + F i discontinutiy certain dispense needed, = 1 the + 0 in tangent this + F { relatively F i * (t) jump noticeable to F{«di however, *, (t) di Fi' i + 0 is which gives f ( ( x ) the slopes, implies, F{ There that obtain f{(x) When before manipulate coordinates. d{'s mentioned it may be derivative. an a l g o r i t h m s general Combining of minimal interpolator arbitrarily retained. possible spaced is data Fig. The discontinuity Fig. The 4.18 4.19 discontinuity Discontinuity arises from not Discontinuity arises from not in derivative rescaling in the derivative rescaling the - ID derivative - 2D derivative 67 4.5 Comparison Actual deferred also can of numerical to chapter deffered be drawn The is from be parametric because in case. of the complete The sine well for certain relatively areas unsuitable, as the higher they of techniques are techniques is conclusions, DSP. are accuracy method is but order (including however, They smoothers no for too and points preclude mesh data. can squares and not rounded. The precision. It useful for advantages perform their where ripple in considered. the 2D better However, being polynomials) Their very drawing applications polynomials of spaced very has uniform Least are dimensional complexity evenly suitable produces one number simplicity. of it highest those increased f i l t e r s choice not dimension, solutions' extreme is Akima's The various Some g e n e r a l pictures in one the chapter. has desired. elimination their The from preferred fit preferred is The then. circular accuracy the 7. this interpolator to results until reconstruction. Bessel techniques greatest used. perform value is applied to easily be type f i l t e r s interpolators. are 68 Chapter Segmenting The curve previous given a chapters set of curvilinear pictures, generated. The must obviously these be input device) This sample to As generate well, curve a points the should small time This given, along the not be delay c r i t e r i a , the relationship of the problem be reviews with the discussed. of of if any of segment. be in before any must any to be curve indicate as well, pen (or an other location. generating The intermediate objective without real of first markers one coding continuous the a user time. here interaction. Completion segmentation is can begin, of a but acceptable. some of the existing straightforward introduced second in automatically, would then points sent long should reconstruct perform special too necessary starting are is points To to applications, be continuous how points with should for generation techniques method any end real-time leaves chapter techniques, sample indicator on examined these For s t i l l Curve points. and remains the sample start events. end-of-segment have 5 based which segmentation subsampling. on detects process segmentation shape corners. to the and Two new direction Finally, the reconstruction 69 5.1 Subsampling Subsampling coding, Nth and sample is also point the one and graphical input pens) operate a is usually then relying an to For the method data has more networks where graphical With a user case with is might of simply natural motion become more is the also for densely fairly matched be stored be desirable. system, coding. more works the scale or to at the good to It the every (node). tablets or light This software is to rate control. sampling receiving robust has a rate, terminal the finer channel capacity. than detail 5.1). independent. is near so The For a packet if more the compact control over required, dependence advantage down, with Moreover, some This simple. bandwidth, links has and fixed desired. user slow (Fig. taking 100Hz). or curve point manipulated, slowly. pen packed is When data (i.e. dedicated to drawn as channel compression data for [46], advantages. data of effective picture is optimal physiology also the the algorithm the a hardware rate subsampling accuracy is of data representation picture where as rate available consists (such reduces many It it sampling original transmission is is the best. under simply applications This the fixed interpolation reconstruct This the devices either Subsampling on of technique transmitting Many at simplest the on the corners. The that the subsampling example, the points method time Fig. This is 5.1 due Increase to the in density physical near necessity corners of (subsampling) decelerating the pen. 71 required to to code it, is What it only does compression database It a symbol, not is storage, should be yield (Chapter — chain control can On These (Fig. such that not or as points used First and size. have? with packet techniques a l l as may as When networks be techniques compact predictive dependent. the lead whole, or better. based other on special differential final also very much sampling rate of data by the with rate. speed dependence. however, subsampling gracefully compared well. to As of inexperienced scale degrade When quite to is The especially results 5.2). method exercised also the performs are its of compressed p i c t u r e s . segmentation encoding determines disadvantage, This on number method optimally however, subsampling implementation user the encoding 7). The device this important, other noted hence dependent does sampling/reconstruction techniques and slightly disadvantages foremost, higher draw as other the hardware the well, the writing or produces sampling segmentation or graphics degree can hesitant be of a users. good results. rate decreases techniques, it Fig. The 5.2 Subsampling sampling intervals - 4 different are 8 12 16 rates and 20. 73 5.2 Other techniques Other based on popular distance approximation they are measures [33], very tolerable radically for the As error pointed segment without and the out locally. types the curve Two Reumann use be measures is depends symbol. used that to on a changes As well, reconstruct the accurate. [38], it piecewise of (polygonal) segmentation same are usually and may then methods, known. sensible polynomial to iterative be as approximation adjust well are the as techniques They to polygonal that thus not operate in fit require suitable for coding. other and determine angle promising Witkam the improvement on the constraints, [33][40], real-time a distance the are line Segmentation lines not assuming to with of Pavlidis approximation complete is curves straight Thus straight by These segmenting or problem sizes measure continuity [40] error. not curve for dependent. different splines curve, The scale maximum since techniques [41] segmentation of this measure eliminating raster (Fig. too be to strips for straight the efficient of tolerance line proposed 5.4). noise However, do use technique approximation. dense techniques Both or by segmentation when spline (Fig. time. 5.3) approximation. Williams methods when real using points are [47] An relies good straight produced interpolation to is for line are used. Fig. 5.4 Williams' O n l y a maximum a n g l e angle spread is measure allowed. 75 The idea and is of an angle incorporated Bearing techniques, following into — good — real the mind a segmentation compression time proposed the interesting in this drawbacks algorithm f_(t) the this is of chapter. the desired one, previous that has the only sophisticated suf f i c i e n t . spline interpolation) (corners, inflection points) y'(t) for / x'(t) we w i s h direction {1 segmentation is based on ) due to to e(t) cos 9(t) as a obtained by the techniques this the estimation known be where derivative f_(t), the procedure but ( | f ' ( t ) | must inaccurate curve and angle = is features proposed, curve and from possible, of (assuming arctan a derivative More of Derivative f'(t) of is = Given Since method an operation method e(t) f_' ( t ) a l l nevertheless independence direction 5.3 the in — preservation a is properties: — scale Such measure determine ( F i g . 5.5) + j set of application, as a of derivative where e(t)} sample digital emphasis such sin the points, the differentiation, quantization smoothing normal splines slope an noise. [33] are f i l t e r is 76 Curve derivative and angle measure 77 The was formulation introduced in for The distance window is the Si = is m E — the relatively computation 4. spacing uniform, of (Fig F[xJ j.: = j1 6(t), it is linear squares it was acceptable least slope found for squares f i l t e r to be smoothing. with a square input device 5.6) r of + F [ x i , x i x\] the and we least Although weighted simplest 2m since linear interpolation, 1 Now, the Chapter unsuitable inverse for data since : ] + coming scaling from is not the needed for the get m x \ = E ( x i. ; - x .- ) / j (yi+j - y i-j ) / j + t j = 1 m The y \ = Q\ = treatment defining This the arctan in = Ii -j = 11 IM*J = IN between with the " puts any x.\) points f_i f o r + (Fig. / end t segment As of (xi,y ) effect (y'^ i < is 1 and fairly i " Ii) images" J> of by N J > (IN - IH-J > "ghost > straightforward 1 1 the sample points beyond 5.7). smoothing elimination of technique, quantization a tradeoff noise and must the be loss made of Fig. 5.7 Treatment Ghost of images of end p o i n t p o i n t s are derivatives used. 79 significant features minimum amount (0 due error is of this here. in x' This in very typical y') is values m a small later the application, keep to f i l t e r , with for to to used simple combination this necessary and Thresholding well Once the direction where must the maxint computer. zero, is by the other angle value j i t t e r 10°) the effects fairly noisy, techniques order) the (say reduce while ( f i l t e r map true angle into 6. The the 4° noise. extended each which final The is arctan are presented between 4 is worrying of the way to on +ir the about ^ mapping 0* = than The minimal. care for [ -maxint, +maxint) representable |y*| integer division. thus [-ir,+ir) .to is to approximation less estimate convenient where simplification far an the to - i r overflow. (x*,y*) by very takes without obtained This A integer integer resulting integer point of obtained, map maximum into then approximation. to automatically (x,y) is been derived. is the means obtain has be angle This wraparound To derivative e(t) manipulate at noise j i t t e r . Good smoothing For 6. and of to performed. performs an of (corners). the use (Fig. arctan 9* := introduces j i t t e r algorithm cost x* of division due 5.8). The y*/x* back ir/4 a to • y*/x* maximum the requires computing by the as error derivative only one direction 80 Fig. 5.8 Mapping transformations for arctan function 81 5.4 Direction The change (Fig. first in desirable of result curve is with the that is segmentation node that the exceeded data spline same along is the (segmentation a tangents proceeds relative is the a same. curve (Fig. 5.10). are more Also, the criterion can if Thus the until a gives spaced is be error This densely net point) segment points curvature. choice smaller e allowable been Thus is D angle found fitted, to however, angle larger becomes The the angle density for more (and increment be a To for around larger than 90° increment, hence accuracy chosen. in obviously angle is not greater good normal 60° compression but get 90° desired controls factor) data of the the If be the used because a maximum interpolation 5.11). may the bandwidth, results, spline (Fig. of 0j>, has curves (Fig. obtaining are 5.12). a good control are d i f f i c u l t . second major inflection higher of sampling technique. local this change for independent. effective fit for a used previous between angle higher The An reason the algorithm predetermined scale from difference segmentation measure reproduce segmentation areas major The to angle the inflection direction 5.9). expected the and points. order maxima feature While derivatives or minima of used these of f, the are they 0 for segmentation normally can defined easily function. be in terms expressed Inflection points of as are 82 Fig. 5.9 Segmentation Segmentation Fig. 5.10 occurs Segmentation 0p = based for 45° on direction when |AG| > 3 different 60° and 90°. angle change 6^. angle thresholds 83 Fig. 5.11 Quartic e D = 45° f i t t o sampled 60° and 90°. points 85 examples useful of for [24]. c r i t i c a l segmentation It is spline cannot placed on to (Fig. those points prevent To to to express that are recognition inflection these problems points unless also because a a node is 5.13). j i t t e r this features pattern reproduce in detection Under high/deep. maximum the are detect (Fig. the which some to expected of 5.14). in desirable be Because used points, the of method, this angle, spurious the in thresholding must inflection minimax must mathematical be be points at least notation, e for T a exist Let 6 0 = 9(t ) : direction at last 0, = 9(t,) : " " possible 0 segmentation point inflection point > 0(t ) Then AG = 01 i > - 6o 0 > T and t 2 t, s.t. V and The definition With smooth these a these "curvy" angles when for and they are points special devised. ©, a minimum two the detected, and method - 0 2 is > , 2 © the algorithm algorithm for interpolator detecting > and works drawings misses execessive rounding for 0(t*) 2 T However, the 0(t,) similar. c r i t e r i a , pictures. corners, t,<t*<t these does occurs handling well with for sharp features. not (Fig. corners Even distinguish 5.15). had Thus, to be Fig. Fig. 5.13 The spline 5.14 This Effect missing interpolator Thresholding is of to used supress cannot in minor inflection reconstuct detecting maxima and points them. inflection minima. points Fig. A special 5.15 Rounding treatment for is of these shown as corners during must devised. be dashed line). interpolation (Original curve 88 5.5 Corner The detection problem reconstruction subject The the desired As with effect derivative simple in the solution to the to amount faithfully interpreted cubics to as are which put these at being used, double node to them. a be 26), be a much Since need used to the be found, discontinuity this where to node [25], both signal at but it pictures. knot. the is nodes and However, interpretation of case, very This necessary This since zero A corner. is to This corners. each in corresponds interpolating transmitted, the a points normal double double the have (p. case, the data a to zero reconstruct using is 3 In of out "corners" Chapter f i t t i n g sent. is finding corners some m e c h a n i s m must increases order at curve are of turns f i r s t . from the however, that dealt seen corners dictates setting derivatives of than method is slope. simple reconstruction reconstruction simpler this and could the in be Hermite derivative is retained. The sets the define derivatives the divided F [ x , x t (as opposed interpolators x ] to such idea to works zero for difference as = 0 the as 0 / 0 = normal Bessel if the such interpolating an interpretation work fine. algorithm occurrence. of However, F ' ( x the If x ) ) , we then polynomial 89 and sinc-type occurrence of interpolators a double node must and to be modified then set to the detect the derivative to zero. This treatment alternative overhead, start a is new to f i t t i n g algorithm coding, corner has impossible The work in local area a of A corner 5.17). Once or must correctly located, the then, node [43]. is at His need curvature, be for result. the the corner node zero however, more and and detected, a An slightly no way just an area again, the this to slope since the derivative. or a Sophisiticated algorithms might be is no some telling of high described of possible, very good fit such some as a location. maximum is Therefore, a in or 9' (Fig. differentiation threshold very done corner a and below. dependent a corner starting digital f i l t e r i n g but a extremum sensible matched if for curvature. local is a Rosenfeld has searches problem value frequency. of as Moreover, detecting given is be of apex. method defined since one its can possible, simply the detection noise. at For determine corner introduces only end-of-curve location. desired 5.16). there corner method be in Unfortunately, new to same the introduces the corner problem, maximum indeed the w i l l locating this the (Fig. main properly at produces which signal curve of is corners treatment, method The of of for the spike simple 9' is sampling detection technique is 90 Fig. 5.16 No Fig. 5.17 Noise Mislocation good fit A corner also is is a introduces of a corner possible. local extremum such extrema. of 8' 91 used instead. Since within is a the small some is so that then | ei - this work never lag well 0 {.j, can effect than then a one chance to were found This previous (Figs. be 0 the the to measure f i l t e r show \B\ - order determine then C quite found and is node solve segmentation the > is a large 0 \.p \ (i.e. the jump where 4). p This presence of a corner. to be this is method with in of for corners rarely very method For high problem, the started ensures to that 5.18). 6 © c will causes curvature direction based techniques that two search until the (in some when if 0 = C for of combined good next interval 0 for 30°, corner the fixed order produces produces separate values the it for value Suitable samples is example generate detection, 5.20). values ©i> o r < sometimes (Fig. 4 this corner an c areas of 5.19 © suitable technique corners. not This about corner heuristic, only some stabilize a noticeable. will point is (obviously problem at i This then not corner To beyond | serious 90° nodes. expected to detected). A more more to thresholded mis-segmentation, the use similar method be where we is that if While function interval, fixed quantity corner, 6 has this a lag p). with the segmentation 92 e(s) Fig. This 5.18 avoids Starting the the problem of segmentation multiple search beyond segmentation of the one corner corner. Fig. 5.19 Segmentation Compare with with F i g . corner 5.15. detection Fig. 5.20 A s e g m e n t e d f r a g m e n t of script 95 5.5 Relationship The from performance instance, an a of depends while curve then spacing. examples the These in a reconstructed heavily corners interpolation automatic used, reconstruction performance measured in to best types 7. segmentation technique picture. turns on be scheme, f i t t e r . Chapter must Also, the It this if a out reconstruction flagged interpolator of method by is sending not one considerations only that be this method. double For nodes necessary with subsampling is can segmentation that assumes are discussed the is uniform with 96 Chapter Automated The the idea of adjusting original Piecewise-cubics with others elements of both introducing work has coding, also such The the in Chapter Instead, interactive This curve and other interpolators as a on the p o s s i b i l i t i e s the limitations here or upon segmentation point. segmentation is This but adjusted a as a the by way Other for curve [30]. work presented algorithms discussed to also and [15]. slope points can used B-splines The method as been elements quadratic fit previously. [4][25], basic builds starting slope of reviews why is for the they proposed are such an method some give be generation (Chapter a best used not preliminary traditional f a i l in where a points. details and [6] The first control whose different arcs curves, shows method generate have to 4) are fit to only for step in design. chapter non-linear solution, of derivatives into using the mentioned design drawing. coding been derivatives curve presented used spline for and only original has chapters. 5 are used. methods, done lines based automated to as previous methods the been Fitting cubic adjustable "tension" technique in not as Curve the drawing 6 This leads are to The are explained. f i t t i n g application. distance considered. algorithm this curve mapping an various discussed. is A used iterative parameters Finally, 97 6.1 Traditional The least best known squares previous slope f i l t e r must to formulation In to be is of can be the is squares methods presented fit can of the magnitude of (recall Fig. be are in used the as a derivative the f_'. derivative 3.2). Thus, a needed. dimensional points used. f i t t i n g As direction adjusted both noisy smoother norm yields the fit, or set a data a good one to least determine a curve smoothing. linear normal fitted traditional spline known that the the the obtain also of and chapter, However, error methods case, (such as where the a curve data A minimization of is tablet the to be input), following desired, E j , = [ I {f (x ) - F }M '> t 1 i i where p=2 the and maximum are error, our end-point are assumptions For as points. known application, are (Fig. about two data as The various absolute error, cases for p=1, least-squares and respectively. values adjusted written the p = oo For be F{ known, 6.1). f'tx-i.,) dimensions, f(x) and is whose f'(x-i,) and the a end-point can f ' ( x { cubic + least 1 be segment whose derivatives adjusted by must making ) . squares error norm can be 98 Fig. 6.1 The Smoothing end fit derivatives of are a cubic adjusted piece for — 1 a best dimension fit. 99 E = 2 E i E i = Thus, the into two take the of the the used (Fig. to downfall correct s method can What design of fact a problems. decompose then the decomposed simple its at the case, x and y corner, = x-y (2~ ' ,0). 1 curve, An = that one when the x-y (x',y') f_'(xi) highly the alternate Which for reveals a is has using a 2 wrong to v a l i d , parametric of appropriate is been cubic found. (Fig. possible not This parametric with f i t t i n g method. proves What is non-linear known problem splines, respect representation curve the the multitude normal account is decomposition adjustment, into problem. (0,0). non-linear parametric the solutions tension arc-length. a (x',y') local takes is into fit and that 2 As it dimensional from apparent gives best procedure one that, be y i ) 6.3). result value - problem interpolate going exist. the (y(s^) is above in immediately from curve into is occurs correct and used, representation. parameter a method disjoint arc-length. is 6.2 of decompositions for F i g . assumption is E i minimization the the + 2 one-dimensional this error 2 t of It the x ) Examination yields stems in obtained x(s),y(s) until 1 Ft one-dimensional The when is the 6.4) - 4 drawing However, but (x(s ) disjoint regardless The - t two-dimensional components. result |f(s ) to its to the power be needed mapping the then, of s 100 Fig. 6.2 From Decomposing this, best an x-y curve fits can be into obtained its in x and each y components dimension H — >< x(a) Fig. This is 6.3 due Incorrect to the Fig. 6.4 This x(b) fit nonlinear obtained mapping Alternate yields the from necessary decomposition correct above result. for s. 1 02 6.2 Non-linear One special possible parameter curvature may be of mapping the to the curvature usable. An through three sensitive corner curvature the works f i t t i n g of is only (x*,y*). the in the (Fig the to 3 points. Moving the noise in matching is thus not the input some of sense counter Instead the distance free variable, of to and a circular a from measure to a be fit is example, too if a zero radius of closer to the suitable drawing. we digital use this we measure. intuitive them, then it when If method points picking arises this of the though for For result for The drawing. F ' ' , However, the nature actual noise need even problem and is correct found. F' much 6.5). of the the curvature. defined, The increases attempt. minimizing for be too of with match well of approach the away to is function location present, try curvature a points Curvature because as does breakpoint. introduces cannot breakpoint the to spline the alternative to is at that is cubic determine differentiation t* approach discontinuous trying write methods One to the points technique, approach that original curve (xi»y-i.) and start by selecting this deriving the a value point 103 Fig. This measure 6.5 is Curvature sensitive to derived the from location 3 points of the points. 104 The t*, method 0<t*<l/2, (assuming to the obtain some (x(t*),y(t*)) works x* value original The then and for the distance of y* f'). curve, onto as and the cubic Then find the adjust (x*,y*) to more measured perpendicular the the is This original the same curve as [(x,y) The quantity for f_'. the "bulge" It is - the must actually on one the by shape would step be from the values the parallel f' of and the • 0 be here distance formula of (x*,y*) f_' to the curve is not easy quantity defining fairly simply directed put [(x*,y*) used to calculate has controlling from only performed . A method of the if such measures depend on its been on must curves convenient the distance the cubic by moving distance > away is along to segment along the chord i.e. be the segment of r by curve (x*,y*) parameter value chord (x*,y*), because procedure controlled of may given the useful caclulated until 0 is of to (x ,y )] d/d* This It in that The based is a curve. A computationally 6.6). For from compute. (Fig. follows. on the as f_' , perpendicular (x ,y )] - 0 the the defining for both segments be defined both sides. d/d*. f_' controls one whose to could segment. behaviour adjust be distance f_' will of f_' obtained Unfortunately, changing value chord. described f_' I necessary tension, optimal • 0 affect (x*,y*) since both from (x (x 0 5 6.6 l 5 yi) y ) 0 Distance T h i s measure is measured p e r p e n d i c u l a r used to adjust the to the chord derivative. 1 06 Thus, ( OfYo)' x procedure does new repeated. necessary, One-step a and An reason convergence is not possible, quickly 6.3 The iterative The presentation for these, the and the original to update questions f_' a the given — what is do the the you — what are — what is a and therefore method but is the becomes non-linear. fortunately updating details given The slope here. The direction those areas where and with value estimate may the to the choices method for f_' (x*,y*). the of be These for both distances This (also f_\ has choosing From (x*,y*) are used raises some distances this for incorrect uncertainty and and d*? f.'{ i)? + the of d algorithm? the method? section. is t\ in , t\. t*? efficiency used chord far method: the for of obtaining parameter in thus consists repeated. conditions stability problems. t *, the free stopping dealt of values of starting method procedure _f'{ solution calculated. starting are The distances the update the the iterative parameter are choice the questions Finding curve the why appropriate descriptive. and about are These of perpendicular — what — how the calculated solution intentionally then if be solution the made. and iterative is are f_', must this converge been (x*,y*) one Chapter by in a of the 5 can also small amount, direction is easier be but used in greatest 1 07 (areas of highest eventually be alternative is The local uses to of the starting slope the small magnitude becomes more The f i t t i n g and indeed the limiting t* depends on derivative. fit As to u 0, the a f_' from case as 4. since it curve. found, using The Chapter original be will minimized. preferred, starting t* the the values ) since the interpolation, F[X{,XJ], of magnitude the mid-point whole of 1 is segmentation for t* are locality let along introduce the chord is more to 0, value of the this well, Wn or must We- usually not segment orthogonal local, the other is (Fig. since i.e. segment in the direction locality the of the us goes of but between uncertainty curve the monotonically, V 2 1 approaches controls method assumed considerations, good is combination distance lies f_, • * , ( t * - 1 the at related discussion, where closer from less is t* directed this contribution Typical the When linear parameter the (u,v), fit is also direction. is coordinates to must Thus, to desire _f' 5 in 1. It two Chapter always procedure. These estimates is the bettter slope a For a effect present for only of For of of this usually end-points. 6.7). the magnitude dense. choice linearly, of information is the that estimate yields derivative reasonable, one magnitude f i l t e r whose so use direction more A curvature), method end-point reduced, is but obtained. end-condition be the balanced and off. 108 Fig. The cubic 6.7 function The is orthogonal represented normal coordinates in terms contributions. of (u,v) parallel and 109 How to update different The the upon Adjusting approach. according and to the plus only ratio d/d* [d./d* minus complex desire and k 'Af' 2 possible does not original fit is to curve. examined For d the basically methods are magnitude new f_' simpler method / d * ] + ' 1 only, (magnitude and of the to a at these further. The direction a l l be each the to reasons, between stable the the | f_' | . problem control set namely updating from to is f_' , (x*,y*)]. one is more iteration exists, - and new f_' 2 distinguish for [(x,y) with correspond far simple signs combined. up the = difficult end adjust can be is Two hybrid direction, must it a • formula increments, that to is variable conflicting somehow is Control free magnitude we very • one although re-calculate magnitude and question. iteration. segments. A more 6.7, to such f' complex exist, is the the := next both a approach each One f' because f i r s t second direction) where is approaches possible. while f_' one used. This side of simple, that adjusts will the this iteration. the quite Referring with for previous local only the F i g . yield two node, which approach As well, derivative the to f_' direction magnitude it is is that of the adjusting 110 Returning iteration is to not (magnitude). (Fig. accuracy, the enough reached then these 2 is 5%), set zero the The one 1) ensure fit need is only small usually of method of a certain in |f'| of of is |f'| j f' is is | occurs, stopped. Using very is variable looping change is the no value converges the be value iteration free that the negative rapidly also (1 very to good, controlled. problem 1 and f_\. if one of is f_'i+i how when to choose adjusting the other Several f\. exist: f . t . 1 a n d _f\+1 to zero. This causes overshoot to be antisymmetric orthogonal coordinates, in the f i t t e r . 2) Set = + to fou• analagous work i f.\. referring not the stability looping a control only to stopped if and method derivatives Set curve well, the with sufficiently remaining p o s s i b i l i t i e s fin to the is a As excessive end-point made Since or approach, problem are .05). iterations). The d i f f i c u l t iteration c r i t e r i a , since first 6.8). (< (< |f'| a Checks occurring small the and + the While to f_\ , the well this is behaviour because the copies set intuitively appealing of arcs circular actual f_\. , and f' f_\, -fo = 1v i.e. because (Fig. f.\+1 of 6.9), may V it it be and is does vastly different. 3) Use e ( s l + 1 ) to the generate This works well _f\ ! turns out + direction guesses unless to be information the far similar actual from one. to fitted available the first magnitude e(s .i) t guess of for t\., and £{. or 111 allowed Fig. Possible not 6.8 Control looping of the situations allowed iteration are not allowed. f. Fig. 6.9 Expressed in Antisymmetric (u,v) tangents coordinates, f' 1Y on = a -f v 0 circular a n d f'm arc = + f ou • 1 12 4) As an previously This of is the improvement generated, the next The best question t_\ segment, using perfect fit in 6.4 Limitat point is of a l l a algorithm, The JL'i+1 " a to without to why If we f. V "a the e ©i+i , s i n p r i o r i " next f i t t i n g fit only f_\. •, l + 1 ). knowledge segments the preceding determined, Unfortunately, segment considered both on previously 1 possible. be c o s use f.'i+1 . of the obvious used and the yields be on limitation each by the segment using 0<t**<t*. generated, done method, |f.Vil*^ - 1+ as value on overcome say f_' , be arise above at (Fig. the same this a could 6.10). Thus, time. ions f i r s t t**, the need The easily can the necessary. overshoot segments is may is set value should both one that derivative surrounding result and on more The f_\ i s at expense p r i o r i " , basic deficiency sort of of in more limitation which cannot leads be forward-backward fit to technique the whole i.e. by a the overcome iteration, geometrical performance of mean addition the f i t t i n g time. problem without point similarly This sub-optimal only This another measures. the that are weighted computing is is curve. add (x**,y**) distance improvement serious to points, updated small more this points perpendicular the of of values not for resorting essentially knowing t\. to removing This some the 113 Fig. This 6.10 occurs only Overshoot when the due to non-symmetric preceding segment is curve used f i t t i n g to determine 1 14 real-time off-line nature of technique obtainable by using the is a technique. feasible, two-pass a In those very procedure. situations good fit were should an be 115 Chapter Experiments This that chapter are made previously. are f i r s t from this other 7.1 a loss be coding rms This and error, is the to of the presented as and and compared. encoding presented qualitative, techniques chain methods techniques best any give two a are as such l e g i b i l i t y . to emerge Finally, mentioned. transmit c r i t e r i a would error can be easily some not sort distance a of of error for input two as and the end seem to without be are it maximum is no points (or methods, more rigorously be must or purpose experimental output Sophisticated deviation, information curves error comparison. in there time-warping rms measures figure, matter, dynamic required. more measure simple Thus, sort used as graphical methods, for Since quantitative thus coding basis However, a is to visual between algorithm the quantitative quantitative, such correspondance some both compare introduced system obtain is coding/decoding combining such to strictly content, important. To be able qualitative, defined, then Results various Some techniques being can of are and measures must strictly of measures, research Before These by introduced. Error the possible Error possible measures compares 7 be work. error or defined. one-to-one (Fig. .7.1). distance-warping) such as dynamic Fig. 7.1 There is Points no in original one-to-one and reconstructed correspondance between drawings points. 1 17 programming this The some the been application, technique to have is a algorithm The allows a minimum but far missing Appendix A the few of size problem, almost due the the let maximum to match a exceeded in of minimum (Fig. but distance for mapping the the every the output point distance continues between until some 7.2). This thresholding presence of quantization search whole loop. The should be about is points of the some the from going algorithm around too given in is error pass to a more measures can based data. Second, we measure, each Lastly, out at the subjective used. rms 3 data the half a the s t r i c t l y error output file overcome segments error screen this are also measure for units. This is tablet. technique c r i t e r i a . The run To line on F i r s t , resulting in point.. around the if the point quantitative be algorithm. heuristic, reconstructing noise established this rather input bottoms quantization made error measure. methods us is because to error € output exactly mid Having well, for prevents through This a l l to a the file corresponds in problem, curve minimization search threshold of zero! used is hopefully comments subsampled is simple this A. choice step handle trying search difference noise, by through threshold and rather works point points. for to sufficient. input two designed maximum Both that the error works rms is and more 118 reconstructed curve match Fig. The 7.2 search for Distance a minimum measure used continues exceeded. to until compare some curves threshold is 119 meaningful visually, errors. Other are annoying more indicate. system high features, that and are due as the the stringently, a guidelines of to frequency error of applies the to corners. a would the visual loss The l o s s larger (Fig. 7.3). of j i t t e r , measure sensitivity than one-shot of this quantitative Other curves, of features accurate start to put should down be these set. considerations A good coding should: 2) have 3) reproduce 4) not introduce extra 5) not introduce high and end methods classes of technique absolute corners in this to pictures depends to "wiggles" frequency w i l l noise (jitter) be c o n s i d e r e d when comparing the made the chapter. these, being some "curvy" drawing error well properties passing Smooth free-hand accurately reasonable desired Before sent. also closure impossible few the an a r c the as high their to This sensitive crossings. start various part of 1) These than important include is such rounding and curve it more noise, in mid-point important Since also frequencies. end p o i n t s , system of c a n be more along is visually is such information error types This to but should a comment coded. extent drawings produce on should be The performance the such type as different of script results of on a coding curve being writing than and "choppy" Fig. Effect 7.3 Visual s u c h as c o r n e r effects vs. absolute r o u n d i n g can have more absolute errors. error impact than large 121 pictures such been made final test, as to print test each however, has to as 7.2 Comparison of Of those techniques of the restricts terms. includes of the actual error As with An members each the of attempt has class. The intended application, communications. ones that have are compared here. been these mostly to discussing results are contained coded/decoded drawings, presented in and previously, This in qualitative Appendix the chapter tables B, which and graphs measures. mentioned previously, limited usefulness reasons, they given the in on diagrams. techniques better the be interoffice itself The schematic algorithm such some graphical and are in used previous quantitative comparing as guides, coding and the section are also a approach error measures are of techniques. For these qualitative properties discussed. Subsampling Subsampling robustness. and Test runs reconstruction reconstruction uniform does is not method method. compute This good were made using methods (see in of terms method divided differences. to its various a is B). by a uniform For a simplicity subsampling Appendix error assumes due The small data 3rd and rates "best" margin the spacing, and order uniform 1 22 f i l t e r , the Si No • great f i l t e r . slope di = error The thus chosen subsampling. compression The / decrease as Some factors. works It compression significant that that sends divided it and on is the very low to starts F i . to a f i l t e r order 3rd - 2 a 2 ] order 4th is faster uniform f i l t e r technique plot of for error vs. technique introduced. original wide to The of speed. compression compression, round error, drawing range medium degrades corners but at and miss segmentation different one for + going subsampling a i features. Shape dependent technique best by { F B. compression over 2 reconstruction Appendix the 1 order The drawings of / 1 lower delay). dependent operates Two in greater very a coded performance is of - obtained preferred given as F*.,} is time the Subsampling higher " 3 (less are gracefully however, 2 advantage reconstruction is is does a segmentation not have double works node best differences a techniques special for with each a are treatment corner normal for included corners, detected. slope and The estimate here: one first based on 1 23 S = 2 / (F[x 3 Vs Once again, the selected as a delay. The any double The deals range order the above f i r s t technique often this problem at The symbol is yields widely The 'maximal' curve shape detection is nodes not are corners varying compression with as a correctly and one which to while extra time with a zero at the operate over higher than to points a limited that represent but a which of given speed. ones tolerable second data drawing on uses was found technique, which is for since anyhow. point improvement segmentation basis generated, one best is This are in error. fit used uses of and to B) and slopes corners, figures, respect measure the needed size Appendix B). usually points in works sets rounds is its dependent that that techniques of 3' error expense that of ('Filter Appendix the number independent sense in Both one 2 technique f i l t e r 3' - F[xi. ,Xi]j between detecting compression, Automated + f i l t e r compromise compression). of + F[x i.., ,-xi]} ,Xi] ('Special subsampling. some 1 node with (lower third good of + ( F l x ^ a ^ i ] corner modification i the the Test side two points in going simpler, curve f i t t i n g runs each to technique of were the on two was fit. made with to side. points, selected corner However, algorithm node each with so w i l l an No that treat algorithm perform for double the fit, significant the the f i r s t sample 124 drawings and The graphs. results of this although unforseen dependent segmentation compression shares The error nodes scale and figures only doubling glitches factors the which span a time for data segmentation this limited sent occur. As range. are the price (halving the the various results is in Appendix the greatest with The much pleasing, is properties technique However, visually technique invariance this are sometimes on techniques. of technique shape based, the technique also with lower that the is compression) the than former. for the paid is the for the same density. Summary Drawing composite together graph conclusions. preferred of the reconstruction general present, it performance uniform f i l t e r For third works is mesh can necessary real-time only to not based f i l t e r calculate on in the we can and 'Special to the the normal than subsampled data. those cases divided at f l e x i b i l i t y , 3', poorer above arrive When d o u b l e significantly j u s t i f i e d operation. is f i l t e r . identically also be generality method order B), discussed (a some the modification nodes are not f i l t e r . Its that the of The 'uniform' the division differences prevents where 125 The choice trade-off. 'Special with 2' the Bessel A Where a f i l t e r or former assumptions. consider fixed The hence to input will some extent does the points any symbol, for compression known ahead preferable. error graph), (note but factor, of The the these shape at a points in known it according time. For technique dispersed errors to It is higher more nature only and B). under different techniques, since data it a yields the ratio, fixed given will better writing number to error of resulting bandwidth, this and dependent The compression, for hence speed, fixed size. small and Shape a and frequency symbol, size. the we transmitted. channel a precision operate sensitive affect The dependent of of measure. shape generates data the and any to delay possible, Appendix compression regardless necessary in produces for both greater #1 one, increase opposite. or has time necessary, error dependent according segmentation is better they vs. are subsampling device, vary a picture detecting of error delay usually since small number legibility, having operates frequency output. its a good interpolator two corner a time (i.e. easy, the for Subsampling Bessel between not the results minimal better Of only yields however, comparison is order normally performs segmentation a 3rd interpolator, sometimes visual of is method not is mis-segmentation vs. compression neighborhood. 126 Automated curve shape dependent yields good f i t t i n g segmentation f i t s , the justified under compression viewpoint. with not the a advantage as applications As method dictated error of encoding a in required for determined made with step be its is it cannot be an system error already not this used curve vs. exists primitive, be the Although sent from can in compression to design, is good or in choice of necessary. discussion, compression exist that curves. are and the not so much by the performance. and would Chain two such be suitable encoding [23] and p o s s i b i l i t i e s . simple method, it is for the predictive Since examined chain further purposes. of consist eight the varying grid mesh of a linked directions each move, by technique application, popular encoding one is as techniques coding moves as its techniques Chain a by Other comparative where above vs. differential for based. the coding is it form Other coding the maximal properties must representation preliminary is that However, a seen which same circumstances well, be real-time on As where the data normal can quantitative 7.3 extra node-and-slope problem. has (Fig. series 7.4). and the accuracy mesh size [22]. sizes. The of incremental Thus, 3 bits are the method is of Several test reconstruction runs were method was (1) (2) Fig. (1) 7.4 C o d i n g scheme Chain (2) encoding Chain 001020765 128 simple the linear method, smoother that to the well, for Such a system coding chain pair (12 dealt minimum-energy curve the mesh bit comparison strategies we bytes Thus, while real on the It is true justice a type of (MEC) the pack techniques presented application and two usually which to spline is of coding they to be based fairly similar to examined. be points to of be exist directly f i r s t system. size. For For each As example, node coordinate consideration particular this knowledge byte. send this in a screen per to compare on and without implementation very rate schemes cannot here to types a is schemes d i s c u s s e d required These context other time, have error d i f f i c u l t have sampling would can are would resolution). within in size rate. resolution, 4 be do [22], segment/interpolate with curves the encoding encoding, not should of the does reconstruction compute to This the subsampling technique of as effect of thesis. since known d i f f i c u l t The interpolation. are best application. for transmission compared defining the to of the intended 129 Chapter 8 Conclusions This this chapter thesis. It also disadvantages. applications presented. 8.1 the the discusses coding their Recommendations of the curve Finally, for relative are coding areas techniques and presented advantages made about interpolating further in research and possible algorithms are discussed. Discussion The the summarizes coding techniques examined segmentation/interpolation original derivatives Hermite curve at these cubic drawing. The are coding are is type. this Thus, transmitted, points. splines in done used to have selected possibly Interpolating then thesis points along algorithms reconstruct automatically, been of from with the based on the original without any user interaction. Other B-splines representations [30] interactive control are or methods points lies smoothers representation on the any change Bezier has curve. in and a As fit the curve are possible, These usually curve. itself, The since interpolators. advantage well, control [36], the not the curves curves to off for with point or that the the The control Hermite derivative cubic, is as involve location these such of the techniques cubic points the s t r i c t l y spline do lie effect of local, 1 30 confined The the to the cubic of using DDA. The the when cubic The reconstruction can be made at lower to of interpolation are as complexity. Hermite to a can The when compact, other FIR are to smooth cubic fairly f i l t e r i n g [46]. also possible dimensional Previous used It f i l t e r , cubic be curve sine one processing. the basis. simple with There spline direction transmitted. FIR approximation used the also favorably such signal to of work spline at in for considerably cost. The f i r s t node Hermite various and cubic several method the major part slope as the formulas. case under when thesis techniques third for capacity the is introduction coded The part s t i l l channel curves, second on the is the introduced slope examination performs is of and different Subsampling circumstances fixed was based strategies. some a the interpolator. The segmentation which of representation interpolation determining is The points cubic has is control curve computationally compares digital [28] interpolation. the good the in field lower a computational applications this also local the f l e x i b i l i t y is control The both representation interpolators, give of good segment the spline it. advantages. control giving cubic only adjoining other for thus calculation especially has allows curvature, the segments basis derivative and two an existing best. available of for This the 131 transmission of needed. The drawing speed a new the of yields some a constant sense, desired the accomodate is also The It is to and manipulated, be as in this the has coding both based and from the is is depend not on the advantages local It and coding for a for a be preferred where the system the where the subsampling segmentation thus symbol. fast are In level where of coding enough segmentation drawings It given is is removes process. given maximal of direction, largely would complexity preferred on thesis. distortion method the compression previously.. compression added of This dependence important, the maximal segmentation, relative fidelity. compression user. introduced scale and fidelity discussed dependent and data, and the as technique time coded error disadvantages, Shape the to algorithm. to does be stored not scale the thesis well. Automated research. are new this determined original to In curve the curve. original algorithm exists predict in the is the f i t t i n g case, the from the These are drawing. The iterative method limitation, the control would results to last at need to the for yield such algorithm due point a to this. quite of control present best is fit. derivative. overcome are the iteration perform obtained part information adjusted real-time the derivatives local presented next forms good. points in the curve fit shown, A the and a limitation inability An Even The to off-line, with need this to 1 32 send both from being only the nodes competitive methods. representation f l e x i b i l i t y f i t t i n g It here, the In should noted be coding of techniques, such manipulation (i.e. point 8.2 by then manipulation more exists technique encoding) sensitive to of of as in system, or curves control is with node node-and-slope where the desired, of the extra the points techniques and possibly straightforward. encoding, scaling). do Techniques predictive in technique curve attractive. sample errors the this efficiency the a l l chain coding where slope that prevents case becomes the or however, terms the already on slopes, in afforded based (chain and which transmission slopes, make Certain not (differential presented allow are for easy incremental encoding) than other are also straightforward encoding. Applications The possible techniques applications. real-time coding configuration, permissible, aid telephone of interactive first drawn of the and examined and primary here of have these curves. Depending and computational bandwidth application techniques of conferencing, graphical video The hand several A primary exchange of channel usable. to introduced such system has for would the Research been done is the the system complexity presented allowing information. communications a on several here be as are an interactive into [5][14]. such The 133 techniques proposed efficiently A spline Telidon. the the slope the as such standard for the as The is such Videotex such systems to in Videotex that ties in The for primitives terminals were graphical such as would transmitted. to existing of greater added then cubic primitive selection even could a be neatly the systems such could arcs. allow by of Telidon node and versatility to be a As the used as communications in system, receivers application above. of this drawer research. tolerable DDA a l g o r i t h m c i r c l e would e l l i p s e / c i r c l e byproduct error and in introduction afforded drawings lines If the primitive interactive envisaged (most is For described applications non-technical an in attractive this thesis where computer is the 2.8% graphics), alternative to a the standard drawers. Another byproduct cubic sinc-type cubic segment The of representation then and new used data. is representation primitives. fast a range be curvilinear f l e x i b i l i t y node primitives could application The increase well, transmit related Hermite here the slope resulting designer s t i l l of the interpolator DDA a l g o r i t h m is computed algorithm has the as is research to digital requires a very to the application signal only weighted thus freedom is sum fast. select processing. additions of As of and sample well, the appropriate the The shifts, values. f i l t e r f i l t e r 134 orders and window factors used in Lastly, used as a drawings functions the the slope curve composition. The control well of make information 8.3 It has primary two use The of also automated is done output of other within factors has in curve ease the presented design of weighting afforded applications One such Videotex or here by where are be graphic of local application which can computer manipulation for terminals this derivative precision could be is in the used in composing theory and algorithms systems. the that devices, available established Hermite cubics introduced for the in coding has The of have a computational hardware, the and stayed away be such drawn from of as techniques hand evaluation chain considered nature of and being Their too much techniques encoding Some include algorithms capacity and curves. these application. complexity interpolation. techniques. of given to f i t t i n g coding techniques context coding segmentation curve however, basic curve real-time dependent. would the some dimensional research, implementation against of research thesis use for choice techniques f l e x i b i l i t y suited provider Further the the importance. entries This for it maximal database f i t t i n g stage and the calculation. preliminary representation, not through of must of the input and the be and speed data 1 35 channel, effect of vs. simplicity would have examine to tests and for would would errors, f l e x i b i l i t y . refine them conventions transmission simplify stability and have to to be be coding A particular and have and the error devised made in efficiency implementation algorithms, control. and also Specific and implemented. the actual coding As well, intended working environment. Thus, area the would be are However, within thrust in of the bulk the of context of any subsequent implementation. doubtless the segmentation other the of There a work that particular are and approaches development remains this p o s s i b i l i t i e s f i t t i n g to in for strategies. these two needs to problems. be done application. Summary The cubic dimensioaal coding is main refinement There 8.4 the two used, various dimensional various are curve is examined, new are and been In old and a popular applied to particular, techniques reviewed. method the the for in one problem of Hermite cubic determining The merits of the these compared. segmentation some has curves. proposed examined and interpolator, f i t t i n g , techniques The points curve and derivatives spline next. new necessary The to standard techniques generate method for of the control subsampling shape is dependent 136 segmentation introduced are as an proposed. alternative solely on control is to determine used proposed to techniques This do points. the this. runs the from derivative the and a are made f i t t i n g based original new is curve algorithm and the is above evaluated. research, then, for the Several of the techniques should be considered be Information Test curve determining derivative, available to to Automated implemented. presents real-time in coding examined those a class of hand yield good applications where of techniques drawn curves. results, such coding and is 137 Bibliography [I] J . H . Ahlberg, E.N. Nilson and S p l i n e s and t h e i r A p p l i c a t i o n s , 1967. J . L . Walsh, The T h e o r y of New Y o r k , Academic Press, [2] H. A k i m a , " A New M e t h o d f o r I n t e r p o l a t i o n and Smooth F i t t i n g B a s e d on L o c a l P r o c e d u r e s " , Journal of the vol. 17, no. 4, pp. 589-602, October 1970. [3] P.E. Allard and H . G . Bown, "On the Generation R e p r e s e n t a t i o n o f L i n e D r a w i n g s " , CRC T e c h n i c a l Note Department of C o m m u n i c a t i o n s , O t t a w a , F e b r u a r y 1978. [4] A.A. Ball, "A Simple S p e c i f i c a t i o n of Segment", Computer Aided Design, p p . 1 8 1 - 1 8 2 , May 1978. [5] D. B e n j a m i n , R. J o h n s t o n and B. P r a s a d a , "A Model for Computer-Mediated Interactive Visual Communications", pp. 5 6 . 2 . 1 - 5 6 . 2 . 6 , ICC P r o c e d i n g s , 1979. [6] M.D. Benjamin, "Picture Description Primitives Alpha-geometric Data bases", pp. 3 . 1 . 1 - 3 . 1 . 6 , Proceedings, 1980. [7] H . G . Bown, C D . O'Brien, W. S a w c h u k and J.R. Storey, "A G e n e r a l D e s c r i p t i o n of T e l i d o n : - A Canadian Proposal for Vidotex Systems", CRC Technical Note 697, Department of Communications, Ottawa, December 1978. [8] H . G . Bown, C D . O'Brien, W. S a w c h u k and J . Storey, " T e l i d o n : A New A p p r o a c h t o a V i d e o t e x S y s t e m D e s i g n " , IEEE Trans. on Consumer Electronics, v o l . CE-25, no. 3, pp. 256-268, July 1979. [9] H . G . Bown, C D . O'Brien, W. S a w c h u k "Picture Description Instructions, PDI, Videotex System", CRC Technical Note Communications, Ottawa, November 1979. [10] C M . Chaikin, Generation", v o l . 3, no. 4, [II] W. C i c i o r a , G . S g r i g n o l i , W. T h o m a s , "An Introduction to T e l e t e x t a n d V i e w d a t a w i t h Comments on C o m p a t i b i l i t y " , IEEE Trans. on Consumer Electronics., v o l . CE-25, no. 3, pp. 235-245, J u l y 1979. Curve ACM, and 689, the Parametric Cubic vol. 10, no. 3, and for 699, for ICC J.R. Storey, the Telidon Department of "An Algorithm for High Speed Curve Computer Graphics and Image Processing, pp. 346-349, December 1974. 138 12] A . K . C l i n e , " S c a l a r - and P l a n a r - Valued Curve S p l i n e s Under T e n s i o n " , C o m m u n i c a t i o n s of the no. 4, pp. 218-223, A p r i l 1974. 13] D. C o h e n , "On L i n e a r D i f f e r e n c e Curves", Advanced Computer Graphics, R.D. Parslow and R . E . Green, e d s . , Plenum P r e s s , London, 1971. 14] "Conversational Graphics via v o l . 3, no. 5, p. 158, J a n / F e b 15] S.A. Coons, "Modification of the shape of piecewise c u r v e s " , Computer A i d e d D e s i g n , v o l . 9, no. 3, p p . 178-180, July 1977. 16] P.E. Danielson, on Computers, 1 970. 17] C . de Boor, Approximation 18] C. deBoor, A P r a c t i c a l New Y o r k , 1978. 19] E. Denert, "A Method f o r Computing P o i n t s of a only I n t e g e r s " , Computer Graphics and Image v o l . 2 , n o . 1, p p . 8 3 - 9 1 , A u g u s t 1973. 20] R . P . Dube, Alternatives", vol. 6, no. 4, 21] R . P . Dube, IEEE Trans, April 1979. 22] H. Freeman Line-Drawing Cybernetics, 23] H. Freeman, "Computer ACM C o m p u t i n g S u r v e y s , 1974. 24] H. Freeman, "Shape Description via the Use Points", Pattern Recognition and Image Conference, pp. 168-174, IEEE P r e s s , 1977. 25] A . N . Godwin, "Family of Cubic Freedom", Computer A i d e d D e s i g n , January 1979. Scribblephone", 1974. "Incremental Curve v o l . C-19, no. 9, to Telesis, G e n e r a t i o n " , IEEE Trans. pp. 783-793, September "On Calculating with Theory, v o l . 6, no. 1, Guide Fitting Using ACM, v o l . 17, B-splines", Journal of pp. 50-62, J u l y 1972. Splines, "Univariate Blending Computer Graphics and pp. 394-408, August 1977. Springer-Verlag, Circle Using Processing, Functions and Image Processing, "Preliminary Specification of S p l i n e on C o m p u t e r s , v o l . C - 2 8 , no. 4, pp. Curves", 286-290, and J.M. Glass, "On the Quantization of D a t a " , IEEE Trans. on System Science and v o l . SSC-5, no. 1, p p . 7 0 - 7 9 , J a n u a r y 1969. P r o c e s s i n g of L i n e D r a w i n g v o l . 6, no. 1, pp. 57-97, Splines with vol. 11, no. Images", January of C r i t i c a l Processing One D e g r e e of 1, p p . 13-18, 1 39 [26] R.W. Hamming, Numerical Methods for E n g i n e e r s , M c G r a w - H i l l , New Y o r k , 1973. Scientists [27] B.K.P. Horn, "Circle Computer G r a p h i c s and pp. 280-288, June 1976. [28] H . S . Hou and H.C. Andrews, "Cubic Splines for Image Interpolation and Digital F i l t e r i n g " , IEEE Trans. on Acoustics, Speech and Signal Processing, vol. ASSP-26, no. 6, pp. 5 0 8 - 5 1 7 , December 1978. [29] K.T. Ichida, " C u r v e F i t t i n g by a One-pass Piecewise Cubic Polynomial", ACM T r a n s . Software, v o l . 3, no. 2, pp. 164-174, June [30] R . S . L a p a l m e , An I n t e r a c t i v e D a t a Line Drawings, M. E n g . T h e s i s , Canada, Kingston, June 1977. [31] M-L. L i o u , Computers, [32] D.G. McCaughey, "An Image Coding Algorithm Functions", Applications of Digital Image vol. 149, pp. 5 1 - 6 1 , 1972. [33] D. M c C l u r e , "Computation of Approximately Optimal Compressed R e p r e s e n t a t i o n s of Discretized Plane Curves", Pattern Recognition and Image Processing Conference Proceedings, pp. 175-183, 1977. [34] J . E . Midgeley, "Isotropic Four-Point Computer Graphics and Image Processing, pp. 192-196, February 1979. [35] R. Moss and A. Lindgard, "Parametric Spline Curves in Integer Arithmetic Designed for Use in Microcomputer Controlled Plotters", Computers & G r a p h i c s , v o l . 4, no. 1, pp. 51-61, 1979. [36] W . M . Newman and R.F. Sproull, Computer G r a p h i c s , M c G r a w - H i l l , [37] G . M . N i e l s e n , "Some Splines under Ten R.E. Barnhill and A c a d e m i c P r e s s , New [38] T. P a v l i d i s and S.L. Horowitz, "Segmentation of Curves", IEEE Trans. on Computers, vol. C-23, pp. 866-870, August 1974. Generators for Display Image Processing, vol. "Spline Fit v o l . C-25, no. Devices", 5, no. 2, Method with a on Mathematical 1977. Reduction Technique for Royal Military College of Made Easy", IEEE 5, p p . 5 2 2 - 5 2 7 , May Piecew sion", R.F. R York, and Trans. 1976. on using Spline Processing, Interpolation", v o l . 9, no. 2, Principles of New Y o r k , 1973. Interactive ise Polynomial Alternatives to Computer Aided Geometric Design, iesenfeld, eds., pp. 209-235, 1974. Plane no. 8, 1 40 [39] L . R . R a b i n e r and B. Signal Processing, 1975. G o l d , Theory and Prentice-Hall, [40] U. Ramer, "An Iterative Procedure for the Polygonal Approximation of P l a n e C u r v e s " , Computer G r a p h i c s and Image Processing, vol. 1, n o . 3 , p p . 2 4 4 - 2 5 6 , N o v e m b e r 1972. [41] K . R e u m a n n a n d W. W i t k a m , "Optimizing Computer Graphics", International pp. 467-472, North Holland, 1974. [42] D.F. Roger and J . A . Adams, Mathematical C o m p u t e r G r a p h i c s , M c G r a w - H i l l , New Y o r k , [43] A. Rosenfeld and E. Johnston, "Angle Detection on Curves", IEEE Trans. on Computers, vol. C-22, pp. 875-878, September 1973. [44] W.S. Rutkowski, "Shape C o m p l e t i o n " , Computer G r a p h i c s and I m a g e P r o c e s s i n g , v o l . 9 , n o . 1, p p . 8 9 - 1 0 1 , J a n u a r y 1979. [45] M.H. Schultz, Spline C l i f f s , N J , 1973. [46] S. S h l i e n and P. A l l a r d , "A FIR o f Smooth C u r v e s on a G r a p h i c s copy (CRC, Ottawa, 1980). [47] C M . Williams, "An Efficient A l g o r i t h m for the Piecewise Linear Approximation of P l a n a r C u r v e s " , Computer Graphics and Image P r o c e s s i n g , v o l . 8 . , n o . 2 , p p . 2 8 6 - 2 9 3 , October 1 978. Analysis, Application of Digital Englewood C l i f f s , NJ, Curve Segmentation in Comput i n g Symposium, Elements 1976. Prentice-Hall, Approach for Terminal", for Digital no. 9, Englewood the Generation pre-publication 141 Appendix Formulas This f i r s t algorithms presented also presented A.1 The of its the cubic basis 0 0 the = = ( > (0) contains this cases a summary thesis. where cubic of Detailed they were the formulas derivations previously (2t + 1)(1 t (1 t) in its and are omitted. expanded - in + 3 are form is 2g(1) + g'(0) + g'(D] t 3g(0) - 2 g ' (0) - g ' (1)] t + g(0) functions = expressed partials [2g(0) [3g(D g'(0) t following n 3 derivations cubic endpoint = * (t) * (t) with in normalized g(t) The in Hermite The terms appendix and A defined t) 2 + as 2 2 property (orthogonality): 6i; i,j e { 0,1} * i 3 > (1 ) = 0 ( The representation of the cubic in terms of the is g(t) = g(o) * ( t ) 0 g'(0) *,(t) + g d ) - g'(1) * 0-t) 0 *,(1-t) + basis functions 1 42 If we m a p a n y (0,1), the segment function f (t) = of the cubic f_ i s the 2 dimensional parametric F + F \ -* (t) F'idi A.2 + 0 where di and t = The Digital To generate I F i = (s *,(t) + - i s i) Analyzer can be used. n, then on This g'''(t+At) = g ' " ( t ) g' ' (t+At) = g " g'(t+At) = g'(t) g(t+At) = g(t) into t € spline *,(l-t) s\) interval, knowing g ' ( l ) , a another name the Digital for a endpoint Differential set of linear and g'(1) g " ' ( 0 ) = 12{g(0) = 1/n. points g"M0) At [ g " ( t ) + g ' ' (t+At) ]/2 A t [ g ' ( t ) + g (t+At)3/2 - + At ' (0) 1 At /12 3 be obtained in terms of as 6g(1) of + can = number g'"(0) = + g " ( 0 ) At - an is (t) partials g(0),g(1),g'(0) the di (s.,,s-,.+ ,) equations. original If i + 1 € Analyzer and g " The F' 0 + cubic g(0),g(1),g*(0) * (1-t) (s i ! Differential a , s | / partials, difference - Ii " 1 + spline - to 6g(0) be g(1)} - 4g'(0) + - 2 g ' ( D 6{g'(0) generated on + the g'(1)} (0,1) interval is 1 43 The following is the DDA algorithm: Variables and v vi vi v g ' ' ' / l 2 g''«n/8 g «n/4 g«n (third derivative) (second d e r i v a t i v e s ) (first derivatives) (scaled values) 1 & V , 0 h[k] = g(t) for t=k/n k =0, 1 , Setup = = = = = vi' v h[0] 0 {g(0)-g(1)} + {g'(0)+g'(1)}/2 {3gd)-3g(0)-2g'(O)-g'(1)}-n/4 g(0)-n/4 g(0)-n g(0) Iteration for i := 1 t o begin n do = = = = v, h[i] v i ' + vi + v + v,/n 0 3 v ' ' ' / 2 (vj'+vl'l/n (vi+v\)/(n/2) - v' ' */n : Vo vi v end; 0 The scaling (precision n=l6. and The multiplication power of 2. factors were selected dynamic range) above algorithm or division for (using 16 for bit can only optimal integer be shift performance arithmetic implemented and add) with without for n a 1 44 A.3 The ellipse The as 4 and The starting segments, the drawer assumption with breakpoints r_ 2 3.6b), f(x) = Y.i ( have * (t) *,(t) condition the minor r v cubic two be drawn intercepts such being points, say r_, + 0 2 will piece * ( l - t ) *,(1-t) 2 ellipse axis Between the + - 0 that and 3.6a). we r, v, end 1 major (Fig. (Fig. desired the is are: Ii~Io) , v J_ , f " ( D 2 ( r - r 2 ) 0 and f " ( 0 ) The last 'circular' / / (r,-r ) 0 two conditions at Let v, = Then f " ( 0 ) the end k , ( r = = 2 - r that this that does The final f' v = 2 1 2 k, x - r 0 ) the k ( r 2 0 ellipse is - r , ) f " 2 0 2 1 2 0 1 ) 0 3/2 3/2 produces I exactly 0 = = method | not and 2 I I' P that 2 6(r -r,) - 4 k ( r - r ) 2 k ( r - r (6-2k )(r -r ) + (6-4k , ) ( r - r ) Thus and s i m i l a r l y Note ensure ( r points. ) 0 / / a curvature 3|r 3 4 | r, | match formulation 2 that is of thus - r [ - r | 0 at the endpoints 2 0 the true e l l i p s e . truly 1 45 f (x) with The = the r , * V ( l 2 (t) 0 + - I o ) 2 * 2 (1-t) 0 *i(t) - . .+ / 3 2 ( l i - I o ) *i(1-t) partials f*(0) = 3 ( r f''(0) = 3(r -r ) f " = 6(r -r , ) '(0) maximum r 0 = £o f = r ) / 2 0 1 2 error f_c - r 2 occurs 1 1 + for t=1/2 (£i~Io /i6 when l2 £o) + (cubic) _ whereas t + 0 Relative A.4 2 " error = The circular three A tangent t relations given t = d d, = |r,| 2 in r 1 1 ' point that 1 0 + r 2 - r 0 ) (ellipse) 2.77% fit satisfies Fig. / d (r,-r 2 4.1 + d 1 the required geometrical is r / d 2 2 where This can and easily be d = 2 verified |r | 2 by computing £ , • ( £ , + £ 3 ) cos 0, = t • r Ilillli l2| |t||r | + This yields vector, in the a 2 = direction form (not identical to 2 the the magnitude) Bessel of the interpolator tangent slope. 1 46 To the adjust midpoint h [This for (see = is the F i g . of 4.1) = 2 slope reason why measure]. a circular fit, the height h at is 2|t|sine»*i(V ) another the magnitude |t|sine F «di/4 is x From / 4 used circular as geometry a natural (Fig. unit 4 . 1 ) , we have d h = = 2 sin h = d 2sine p 6 p - /> cos 6 Thus (1 - cose) = both on |t| sine / 4 and |t| = 1 + Now, since IF, | t = 2d cose F_i«di, 1 + Finally, formula since t cose depends proposed by 2 + Midgeley 4 cose, + e, [34], cose 2 and & , 2 we use the hybrid 147 A.5 The A using The polynomial simple a fits extension quartic fit to the through Full Quartic Solution The quartic polynomial fi(x) = Fi + Bessel 5 points passing Si(x-xi) C i (x-xi ) For ease of D, D D D„ = = = = 2 3 Then, the which Si F [ F t F [ F[x h, h h h„ 2 3 the h hi h§ h . 2 2 x x i t + 1 + 2 F{ i ( x - x ) possible the slope. is + 2 t 1 3 h hi Si C i hi c 3 the 5 points = 2 hjj solution = = = = 2 through u d i d i + d i , " d i . i ] + di_ ) + 2 satisfies D, D D D, 2 3 3 i is D hj 2 C«i ( x - x i ) h, h h h« 2 4 E j= i determine through C is let x , x i ] x i , x ] x i , x . ] ,x ] quartic 1 1 1 1 For notation, to + + 3 3 interpolant 4 E -n(hj-h ) k k*j j = 1 hj - n ( h j - h ) k by 1 48 Uniform Spacing Assume Then, in the h, The that = h, d solution Si = = d i notation 1 1 1 2 1 -1 1 -2 is a l l = given = 2d 1 1 4 8 1 -1 4 -8 / 2 Si -d h« = -2d 3 3 + D } + 2 / F[xi,x x + above We + 3 ,] 2 •+ D«} / F [ x i . ,,x ] 2 3 - is *D V F [ x i , x i 6 used + x to + 2 ] determine higher order fits i.e. V oF[xi. 2 3 2 2 3 6 as D, D D = -V F[xi. ,Xi] spacing, = = 3 2 {D, 3 same m e t h o d uniform h Si C i / d C i / d C«i/d 3 on above, of 2 The d. 3 ,x i ] - /„F[xi , x i , ] + 3 - /i 3 / 0 1 0 F[xi.. F [ x i ,Xi] + 2 ,Xi + 2 3 ] + / « F [ x i . ,, x i ] + V 2 0 F[xi (6th , x i + 3 ] order) End-points The the Di's solution and the at endpoints h-i's. For is obtained example, for by suitably a quartic fit defining let 1 49 D, D D D„ = = = = 2 3 The uniform S, F F F F [ [ [ [ x x x,,x x , , x x x 1 1 f 2 f spacing = 3 5 ] ] J ] h, h h h„ 2 3 solution 4-F[x,,x ] 4'F[x,,x„] A.6 The sine The simple 6 ' F [ x , , x - F [ x , , x ] + + d+ d + d 2 + d + d 2 2 5 3 + d„ ] sine f i l t e r , sine (x) assuming = ir a uniform mesh, x^ = k is x = v x with ^ f ' ( x ) k v x cos ir non-uniform x (-1 ) = k k a pseudo-sinc definition of the , k*0 , k=0 k 0 meshes, the kir = = extending cos k = IT For 3 3 f i l t e r sin f(x) d, d, d, d, is ~ 2 = = = = function can derivative at be created the by crossing points g (x,) 6 i = w k (-1 g' ( k Between Using X l ) the this as - x ) 1 ' k = , k*l = 0 , k=l k ' s , the the basic function interpolating consists of function, cubic we have segments. 1 50 The f(x) = S = t f i l t e r this as E F • k f' ( x i ) given reason, is the function g (x) obtain f i n i t e f(x) = Si = k = E F an w-(x^) can be w (x,) a = k = Si = = we been window • w (x) = k {g (xi)w (xi) k g (xi>w (xj) k E F k E F k that it is function |i-k|. f i l t e r . vague. w (x) > k For If the 0, we k k k an + k involving F i w j U i ) function). XJ'S. )} k + k even g (xi)wv; (xi Now, For w (xi) k simplicity, set Thus (-1 ) " l linear left function g (x) E k*0 desire a has response E F • k f ' ( x i ) F k x; Since impulse f i l t e r , (so j by ) { response complex Wj, k impulse k 0 g (x index multiplied = Set • k infinite summation is k a g (x) k w , i . . , — x. k - precision, we write S{ in terms of F[xt,x 3 K S Now, x -E F [ x i , x k*0 s i n c e -w j i . j k Si The = window = is k only m E { F [ x i , x j =1 coefficients Wj ] • (-1 ) ^ 1 _ non-zero i + i ] + for w^.k, |i-k| F [ x i , x i . ; J are ]} < m • (window (-1) J 1 size) w: J chosen for linear precision so 151 that m E 2 (-1 ) > w.- = squares fit 1 1 , w; > 0 j-1 A.7 {Fj} The least To fit the line f(x) F{ = + S (x-x{) where = w(d j t )) E [f ( X J ) E {[Si-Ui-Xj) are dE dS{ = E j*i S{ = E the - data points Fj ] w ( d i j ) ) 2 (F\ - F j ) ] - weighting Some of the uniform, Si [Si-Cxt-Xj) ) ( X J - x i ) F [ x i ,Xj ] 2 This choices w(dij) = 1 = d?j F [ x i ,Xj ] / unsuitable, as method further inverse is for the (d ij ) } - 2 / (Fi-Fj)] E weighting E j^i = 0 w ( d ij ) ( X J - x , ) squared, it w(d j) x function are: d?j gives out. distance 2 j*i possible E j#i 1 factors. w ( d ij ) ( x i - X j ) w(dij w ' j*i b) the define E a) to = 6\j more weight to points 152 S This = x E method F[x i f / Xj] is usable, inverse distance N, N but a = # points gradual considered windowing would preferred c) windowed Si m E = squared, w; { F [ x i , x i + j ] + w(d j) = x w ( l .j| / d ^2 F [ x i , X i . . - ]} j =1 with m E j =1 This A.8 is Error type the best of measure vector procedure = = WJ 1 the / 2 simple least squares methods. algorithm array error [1..maxint] of_ integer (x1 , y1 : v e c t o r ; n1 x2 , y2 : v e c t o r ; n2 v a r n s , sum2 , maxd : : : integer; integer; integer); { original points : (x1,y1) decoded points : (x2,y2) error s t a t i s t i c s : ns,sumd,maxd, rms e r r o r = sqrt (sum2/ns), with max } var i1 , i2 , eps , function imag ( i x , begin i m a g := s q r t end; begin i1 := 1; for i 2 := begin 1 to di , iy dj : (ix n2 j : integer) * do , ix + iy integer; : integer; * iy) error = maxd be 1 53 eps eps di for := i m a g ( x 2 [ i 2 ] - x 2 [ i 2 - l ] , y2[i2] - y2[i2-1]); := m a x ( e p s , 1 6 ) ; := maxint; j : = i 1 t o n1 d o begin d j := i m a g ( x l [ j ] - x 2 [ i 2 ] , yl[j] y2[i2]); if (dj-di) > eps then break if dj < di then begin i 1 := j ; d i := d j end end; ns := n s + 1 ; s u m 2 := s u m 2 + d i * d i ; m a x d := m a x ( m a x d , d i ) end; end; 1 54 Appendix Sample This test first runs. various These does take up illustrate is over the There first not a various types indicating technique second entry given graph the error number of the obtained given of is of the vs. input plot compression, advantage by using segmentation the the results, subset gained in this for preferred as these to appendix. The obtained with particular The underlined ("best") the number The drawing for is of third a as points graphs technique segmentation is defined coded These reconstruction the one. The compression coding). where The shown one combination. by by is reconstructed where divided technique, of preferred of of techniques. density. the the combinations measurements techniques is points a from 7. error and a results using set entries segmentation/reconstruction of (i.e. in reconstruction type complete Chapter recontruction a a made technique the by Instead, segmentation of made pages. three table some reconstruction contain points are were and 90 Results contains runs segmentation appendix would appendix B are for a density is segmentation and varied. A l l entries reconstruction for the various are labelled, techniques used. reconstruction showing The the following techniques: names are used 1 55 Linear - simple linear Bessel - slope determined by a parabolic Quartic - slope determined by a quartic fit Uniform - slope determined by a sum o f value F V ' d i. , interpolant = F V d { m I = Wj { F j=1 note Nonuniform- as - F i l t e r that this above, slope makes except determined m I F'v + through - j through F ij derivatives the by a sum o f divided j ,xi ] F [ x .j 1 + x 5 points points } discontinuous derivative - 3 differences that {F[x WJ the i fit is continuous differences ,x{ ]} j=1 Special For the - adaptation at a of used tablet (Chapter 1). reconstructed technique. case, double the of for using the above Special name impulse thing derivative is continuous f i l t e r which sets F^ = 0 node. through f i l t e r the first pictures data an the width The this Uniform following the in the the response that the is is test slope order of m. the presented here These hardware setup are followed pictures and graphs, Note the that number m is half f i l t e r . runs. These f i l t e r s , by were are the obtained described tables, arranged original by from the previously drawings of segmentation O r i g i n a l p i c t u r e no. 1 157 Original picture no. 3 O r i g i n a l p i c t u r e no. 4 1 60 Error Segmentation: P i c t u r e no. : No. of points: Density : Compression : Errors: Linear Bessel Quartic Uniform 2 Uniform 3 Uniform 4 F i l t e r 2 Filter 3 Filter 4 Nonuniform Nonuniform Nonuniform Subsampling, 1 31 8 . 63 % '1 1 . 5 9 RMS 2 3 4 measurements Abs 3 7 . 5 4 106 26.26 90 26.69 89 23.59 81 1 9.97 70 18.75 65 25.68 86 77 23.30 22.57 75 82 24.80 2 2 . 14 84 20.98 84 rate = 12 2 91 8 . 62 % 1 1 . 60 RMS 4.99 4.12 4.48 3.53 3.45 3.43 3.85 3.86 3.85 3.62 3.53 3.52 Abs 16 16 16 10 9 9 15 15 15 12 12 12 3 140 9 .17 % 1 0 .91 RMS 18.25 15.48 16.11 12.41 10.24 9.44 15.00 14.57 14.21 15.00 13.19 12.98 4 143 11 .26 8 .88 Abs RMS 108 1 07 1 07 1 07 94 94 107 1 07 1 08 1 09 11 3 11 5 4.89 4.80 4.87 4.06 4.09 4.09 4.37 4.31 4.28 4.32 4.11 4.09 Abs 18 16 19 15 12 12 16 15 15 15 15 14 Picture no. 3 Segmentation Subsampling No. 140 of points 9.17% Density Compression 10.91 Reconstruction Uniform Error 10.24 (RMS/abs) 3 / 94 , rate = 12 162 CO Picture no. Segmentation Subsampling No. 107 of points Density 7.15 % Compression 13.99 Reconstruction Uniform Error 19.60 (RMS/abs) , 3 / 113 rate = 1 6 163 60 25 50 20 4- 40 RMS RMS E R R 0 R 3 0 15 E R R O R •1 0 20 1 0 H 5 10 15 20 5 C O M P R E S S I O N 1 1 0 1 1 5 1 20 1 25 1 30 \35 C O M P R E S S I O N 25 1 5 20 RMS 15 RMS E R R O R 10 E R R O R 1 0 5 1 5 10 15 C O M P R E S S I O N Segmentation o — Subsampling 2 0 5 10 15 C O M P R E S S I O N Reconstruction Uniform 3 164 Error Segmentation: Picture no. : No. of points: Density : Compression : Errors: Linear Bessel Quartic Uniform 2 Uniform 3 Uniform 4 Filter 2 Filter 3 Filter 4 Nonuniform Nonuniform Nonuniform Shape 2 3 4 dependent, 1 29 8 . 09 % 1 2 . 36 RMS 38.69 38.77 37.32 56. 1 1 50.52 51 . 7 9 33.62 20.41 21 . 2 8 29.27 28.58 29.41 measurements Abs 11 4 178 178 1 78 1 78 1 78 1 78 88 94 1 06 108 108 without 2 41 3 . 99 % 2 5 . 06 RMS Abs 71 1 9.49 1 4.27 85 2 2 . 10 1 7 8 16.28 69 1 6.07 67 67 1 6.98 77 13.81 12.99 78 12.82 78 68 13.99 1 3.32 66 14.51 64 corners, 3 1 56 10 . 1 5 % 9 .85 RMS 12.46 1 1 .09 1 1 .38 12.18 13.47 1 4.03 8.92 8.16 8.28 9.55 8.78 9.19 Abs 56 85 97 63 63 63 47 41 43 49 38 40 e D = 60° 4 78 7. 1 7 1 3 . 95 RMS 12.00 10.60 8.93 7.22 8.09 8.48 7.12 7.22 7.28 6.81 6.98 7.22 Abs 72 78 55 53 52 48 55 53 52 52 53 53 165 Picture Segmentation No. of points Density Shape no. dependant, 78 7.17 % Compression 13.95 Reconstruction Filter 3 7.22 / Error (RMS/abs) 4 53 without corners, 9^ = 60' 166 25 60 50 20 40 RMS RMS E R R OR 30 15 E R R O R 1 0 20 1 0 5 10 15 5 20 1 0 15.20 25 3 0 35 C O M P R E S S I O N C O M P R E S S I O N • 25 15 1 20 RMS RMS 15 10 E R R O R E R R O R 1 0 5 10 15 5 20 Segmentation — Shape dependant 15 C O M P R E S S I O N C O M P R E S S I O N n 10 Reconstruction (no corner detection) F i l t e r 3 167 Error Segmentation: Picture no. : No. of points: Density : Compression : Errors: Linear Bessel Quartic Uniform 2 Uniform 3 Uniform 4 Special 2 Special 3 Special 4 Filter 2 Filter 3 Filter 4 Nonuniform Nonuniform Nonuniform Shape 2 3 4 dependent, 1 - 33 9 . 16 % 1 0 . 92 RMS 60 . 7 0 51 . 7 2 74 . 0 9 101 . 9 9 103 . 6 0 1 04 . 9 8 63 . 1 2 62 . 9 9 62 . 9 4 64 . 8 5 61 . 1 6 59 . 9 5 89 . 2 8 90 . 4 7 92 . 7 4 measurements Abs 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 78 78 78 78 78 78 78 78 78 78 78 78 78 78 78 with corners, 2 31 3 . 06 % 3 2 . 68 RMS Abs 23 . 7 4 18 . 9 4 22 . 1 0 21 . 0 0 22 . 6 8 24 . 1 9 18 . 1 8 17.82 18 . 0 6 18 . 2 1 17.75 17.99 19 . 7 8 20 .21 23 . 0 9 95 69 109 82 83 83 76 75 76 76 75 76 77 75 77 e D 3 165 10 . 7 0 % 9 .35 RMS 16. 12. 14. 15. 17. 18. 10. 10. 10. 10. 10. 10. 14. 14. 15. 15 59 54 15 09 20 93 83 72 01 32 01 07 81 49 Abs 68 87 78 70 78 93 64 64 64 52 48 48 62 70 85 = 60° 4 81 7 . 36 1 3 . 59 RMS 1 1 . 78 1 0 . 55 8 . 88 7. 1 7 8 . 27 8 . 70 6 . 93 7 . 06 7. 1 0 6 . 94 7 . 05 7 . 09 6 . 60 6 . 97 8 . 02 Abs 72 78 55 53 52 48 55 53 52 55 53 52 52 53 53 cc Picture Segmentation No. of points Density Shape 81 7.36 % 13.59 Reconstruction Special (RMS/abs) 7.06 4 dependant, Compression Error no. 3 / 53 with corners, 6 = 60' 169 60 25 50 2 0 40 RMS ERR RMS 0 R 3 0 15 E R R O R 1 0 20 1 0 -i 5 10 15 2 0 1 5 1 0 C O M P R E S S I O N 1 1 1 5 2 0 1 1 25 1- 3 0 3 5 C O M P R E S S I O N 25 1 5 20 RMS 15 RMS E R R O R 10 E R R O R 1 0 b J 5 10 15 20 5 C O M P R E S S I O N - Shape dependant 15 C O M P R E S S I O N Segmentation A . 1 0 . Reconstruction (with corner detection) Special 3 170 Error Segmentation; Picture no. No. of points Density Compression Errors: Two p o i n t Four point Automated 1 30 16.31 6.13 RMS Abs 50.89 46.10 178 178 measurements e> f i t , = 90° 2 39 7.33 % 1 3.65 RMS 7.41 8.59 Abs 38 51 3 1 15 20.53 % 4.87 RMS 7.06 8.23 Abs 52 67 4 1 16 16.66 6.00 RMS 3.93 4.02 Abs j_9 16 171 Picture Segmentat No. of ion points Automated 7.65 Compression 6.54 Error (RMS/abs) 3 curve 1 22 Density Reconstruction no. Two % point 9.94 / fit 71 fit, 9^ = 90' 172 Picture no. Segmentation Automated No. 103 of points Density 7.69 Compression 6.50 Reconstruction Error (RMS/abs) Two curve % point 4.10 4 / fit 19 fit, e D = 90° 173 25 GO 50 2 0 40 RMS RMS 15 E R R O R ERR 0 R 3 0 1 0 20 1 0 5 10 15 5 2 0 1 0 1 5 2 0 25 C O M P R E S S C O M P R E S S I O N 3 0 I 35 ON 25 1 5 20 RMS RMS 15 10 E R R O R E R R O R 1 0 5 10 15 C O M P R E S S I O N Segmentat i o n o — Automated c u r v e 2 0 5 10 15 C O M P R E S S I O N Reconstruction fit 2 point fit 174 60 25 50 20 HO RMS RM S 15 E R R O R E R R 0 R 3 0 10 20 ] 0 ^ 1 5 10 CO 1 h- 15 2 0 5 M P R E S S I O N 10 1 5 2 0 2 5 3 0 3 5 C O M P R E S S I ON 25 1 5 2.0 RMS 15 RMS E R R O R 10 E R R O R 1.0 o o D o 5 10 15 2 0 5 C O M P R E S S I O N C 0 M P R Segmentation 15 E S S I ON Reconstruction o — Subsampling n — Shape d e p e n d a n t (no A — Shape d e p e n d a n t (with corner • — Automated curve 10 Uniform fit corner detection) detection) Filter Special 2 point 3 3 3 fit 175 Error Segmentation: Picture no. No. of points Density Compression Errors: RMS/abs Picture no. No. of points Density Compression Errors: RMS/abs Picture no. No. of points Density Compression Errors: RMS/abs Chain encoding, 1 159 4 3 . 13 % 2.32 13.01 32 1 216 58.35 1 .71 11.85 32 1 326 88.01 1.14 11.26 measurements 44 linear 2 1 18 1 1 .07 9.03 7.65 22 2 1 58 14.78 5 6.77 6.27 20 2 236 22.01 4.54 4.89 16 interpolation 3 285 17.75 % 5.63 12.09 108 3 394 24.39 I 4.10 8.21 36 3 595 36.70 2.72 6.78 32 4 209 14.27 % 7.01 9.06 32 4 279 18.68 % 5.35 7.32 16 4 419 27.51 3.63 5.72 16 1 76 Picture Segmentat No. of ion points Density Reconstruct 3 encoding 595 36.70 Compression Error Chain no. % 2.72 ion (RMS/abs) Linear 6.78 / 32
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Real time coding of hand drawn curves
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Real time coding of hand drawn curves Szeliski, Richard Stephen 1981
pdf
Page Metadata
Item Metadata
Title | Real time coding of hand drawn curves |
Creator |
Szeliski, Richard Stephen |
Date Issued | 1981 |
Description | This thesis examines some techniques for the real-time coding of hand drawn curves. These curves are drawn on a data tablet or other graphical input device. As they are drawn, they are coded for transmission over a digital link and reconstructed at a receiving terminal. The real time requirement allows this system to be used for instant graphical communications. One possible application is as a sketchpad facility to aid telephone conferencing. The techniques examined involve sending selected control points along the curve, and using an interpolating function for reconstruction. The interpolator used is the two dimensional parametric cubic spline. Several members of this class of functions are introduced and evaluated. An existing technique for generating the control points (subsampling) is reviewed, and a new shape dependant algorithm is proposed. Automated curve fitting based on information in the original curve is examined. Test runs are made using the various techniques, and conclusions drawn. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-03-29 |
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.0095253 |
URI | http://hdl.handle.net/2429/22827 |
Degree |
Master of Applied Science - MASc |
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 |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1981_A7 S98.pdf [ 5.27MB ]
- Metadata
- JSON: 831-1.0095253.json
- JSON-LD: 831-1.0095253-ld.json
- RDF/XML (Pretty): 831-1.0095253-rdf.xml
- RDF/JSON: 831-1.0095253-rdf.json
- Turtle: 831-1.0095253-turtle.txt
- N-Triples: 831-1.0095253-rdf-ntriples.txt
- Original Record: 831-1.0095253-source.json
- Full Text
- 831-1.0095253-fulltext.txt
- Citation
- 831-1.0095253.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0095253/manifest