UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Real time coding of hand drawn curves Szeliski, Richard Stephen 1981

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

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items