EXERCISES 
`
` numbers  of   sons. 
`
`8.1  Consider a region  segmentation  where regions are of
` two   types:  (1)  filled  in and (2) 
`with holes. Relate the number
` of  junctions,  boundaries,  and filled­in regions to the 
`Euler number. 
`8.2  Write  a  procedure  for  finding  where  two   chain codes intersect. 
` representation. 
`8.3  Devise algorithms  to  intersect  and union two  regions  in the^­axis
`8.4  Show that the number of
` intersections  of the curves under a clear strip intersection 
`is odd. 
`8.5  Modify  Algorithm  8.4 to work with strip trees with varying
`8.6  Derive  Eq.   (8.9) from  Eq.   (8.7). 
` equivalent. 
`8.7  Show that  Eqs.   (8.12) and (8.13) are
`8.8  Given two points Xj and x
`2 and  slopes (j>(x\)   and(/>(x 2), find  the  ellipse  with major 
`axis a  that fits the points. 
`8.9  Write a  procedure  to intersect two regions represented by quad trees,
`quad tree of  the   intersection. 
`8.10  Determine the shape numbers for  (a) a circle and  (b) an octagon. What is the
`tance between them? 
`
` producing  the 
`
` dis­
`
`REFERENCES 
`
`  POPPLESTONE.   "A  versatile 
`  BURSTALL,   and  R.  J.
`  BROWN,   R.  M.
`  BARROW,   C.  M.
`AMBLER,  A.  P.,  H.  G.
`system  for  computer  controlled  assembly."  Artificial Intelligence 6, 2,  1975,  129­156. 
`
`BALLARD,  D. H.  "Strip  trees: A  hierarchical  representation  for  curves."  Comm.  ACM  24, 5,  May  1981, 
`310­321. 
`
`BARNHILL,  R.  E. and  R.  F.
`1974,  160. 
`
`  RIESENFELD.   Computer Aided  Geometric Design. New  York:  Academic  Press, 
`
`BARROW,  H. G.  and  R. J.
`
`  POPPLESTONE.   "Relational  descriptions  in picture processing."  In MI6,  1971. 
`
`BLUM,  H. "Biological  shape and  visual science  (Part  I)." J.  Theoretical Biology 38,  1973, 205­287. 
`
`  GUZMAN.  " H OW   to describe  pure  form  and  how to  measure  differences  in  shapes 
`BRIBIESCA,  E. and  A.
`using shape  numbers."  Proc,  PRIP,  August  1979, 427­436. 
`
`BRICE,  C.  R.  and  C.  L.
`205­226. 
`
`  FENNEMA.   "Scene  analysis  using  regions."  Artificial Intelligence  I,  3, Fall  1970, 
`
`  "TWO   descriptions  and  a  two­sample  test  for  3­d  vector  data."  TR49,  Computer  Sci­
`BROWN,  C.  M.
`ence Dept.,  Univ.  Rochester,  February  1979. 
`
`DEBOOR,  C. A Practical Guide to Splines. New  York: Springer­Verlag,  1978. 
`
`DUDA,  R. O. and  P. E.
`
`  HART.   Pattern Recognition and Scene Analysis. New  York: Wiley,  1973. 
`
`FREEMAN,  H.  "Computer  processing  of  line  drawing  images."  Computer  Surveys  6,  1,  March  1974, 
`57­98. 
`
`  NEURATH.   "Improved  computer  chromosome  analysis  incorporating  prepro­
`GALLUS,  G.  and  P.  W.
`cessing and  boundary analysis."  Physics in Medicine and Biology 15, 1970, 435. 
`
`GORDON,  W.  J.  "Spline­blended  surface  interpolation  through  curve  networks."  J.  Mathematics  and 
`Mechanics  18,  10,  1969, 931­952. 
`
` PAVLIDIS.   "Picture  segmentation  by a tree  traversal  algorithm."  J. ACM  23, 
`HOROWITZ,  S.  L. and  T.  P.
`2,  April  1976, 368­388. 
`
`Ch.  8  Representation  of  Two­Dimensional  Geometric  Structures 
`
`IPR2021-00921
`Apple EX1015 Page 276
`
`

`

`  LUDWICK,   "Automatic  radiographic 
`  DWYER,   and  G.  S.
`  HALL,   S. J.
`  TOWNE,   D.  L.
`KRUGER,  R.  P.,  J.  R.
`diagnosis  via  feature  extraction  and  classification
`  of  cardiac  size  and  shape  descriptors."  IEEE 
`Trans. Biomedical Engineering  79, 3, May  1972. 
`MARR,  D.  "Representing  visual  information."  AI Memo  415, AI Lab,  MIT,  May  1977. 
`MERRILL,  R. D.
`  "Representations   of  contours   and  regions   for  efficient  computer  search."  Comm. 
`ACM16,  2, February  1973,  69­82 
`NAHIN,  P. J.
`  "The  theory   and  measurement   of a  silhouette  descriptor   for  image  preprocessing  and 
`recognition."  Pattern Recognition  6, 2, October  1974. 
`
` In  MI5,  1970. 
`PATON,  K. A. "Conic  sections in automatic  chromosome  analysis."
`PAVLIDIS, T. Structural Pattern Recognition. New  York: Springer­Verlag,  1977. 
`PERSOON,  E.  and   K. S.  Fu.  "Shape  discrimination  using  Fourier  descriptors."  Proc,  2nd  IJCPR,  Au­
`gust  1974,126­130. 
`REQUICHA,  A. A. G.
` "Mathematical  models   of  rigid  solid  objects."  TM­28,  Production  Automation 
`Project,  Univ.  Rochester,  November  1977. 
`  In  Optical and  Electro­optical Infor­
`ROBERTS,  L.  G.  "Machine  perception   of  three­dimensional  solids."
`mation Processing, J.P.  Tippett
` et  al.  (Eds.). Cambridge,  MA: MIT  Press,  1965. 
`ROSENFELD,  A. and  A. C.
`  KAK.   Digital  Picture  Processing.   New  York: Academic  Press,  1976. 
`SAMET,  H.   "Region  representation:  quadtrees  from  boundary  codes."  Comm.
`  ACM  23,   3,   March 
`1980,163­170. 
`SCHNEIER,  M.  "Linear  time  calculations  of geometric  properties  using quadtrees." TR­770,  Computer 
`Science Center,  Univ. Maryland,  May  1979. 
` In  PCV,  1975. 
`SHIRAI,  Y. "Analyzing  intensity  arrays  using  knowledge  about  scenes."
`SKLANSKY,  J.   "Measuring  concavity   on a   rectangular  mosaic."  IEEE  Trans.  Computers  21,
`cember  1972. 
` KIBLER.   "A  theory   of  non­uniformly  digitizing  binary  pictures."  IEEE  Trans. 
`SKLANSKY,  J.  and   D. P.
`SMC  6, 9, September  1976, 637­647. 
`TOMEK,  I.  "Two  algorithms   for  piecewise  linear  continuous  approximation
`able."  IEEE  Trans. Computers 23,
` 4,   April  1974, 445­448. 
`TURNER,  K.  J.  "Computer  perception  of curved  objects  using
` a  television  camera."  Ph.D.  dissertation, 
`Univ. Edinburgh,  1974. 
`VOELCKER,  H.  B. and  A.  A.
` G.  REQUICHA.   "Geometric  modelling  of  mechanical  parts and  processes." 
`Computer  10, December  1977, 48­57. 
`Wu,  S., J. F.
` ABEL,   and D. P.
` GREENBERG.   " An  interactive  computer  graphics  approach
`representations."  Comm.  ACM20,  10, October  1977,
` 703­711. 
`YOUNG,  I. T.,
` J.  E.   WALKER,   and  J.
` E.  BOWIE.   "An  analysis  technique
`tion and Control 25,  1974. 
`
`  12,  De­
`
`  of  functions   of  one  vari­
`
`  to   surface 
`
` for  biological shape  I."  Informa­
`
`References 
`
`263 
`
`IPR2021-00921
`Apple EX1015 Page 277
`
`

`

`Representations of 
`Three­Dimensional Structures 
`
`9 
`
`9.1  SOLIDS AND THEIR  REPRESENTATION 
`
`We consider three general classes of representations for rigid solids
`1.  Surface or boundary 
`2.  Sweep (in general, generalized cylinders) 
`3.  Volumetric  (in general, constructive solid geometry) 
`The  semantics  of  solid  representations  is  intuitively  clear  but  sometimes 
`mathematically  tricky. The  representations  have different  computational  proper­
`ties, and readers should keep this in mind when assessing a representation for pos­
`sible use. As a simple example, a surface representation can describe how an object 
`looks;  a volumetric  version,  which  expresses  the  solid  as a combination  of sub­
`parts, may not explicitly contain information  about the surface of the object. How­
`ever, the solid representation may be better for matching, if it can be structured  to 
`reflect functional  subparts. 
`Certainly  we  believe,  as do  others,  that  model­based  vision  will  ultimately 
`have to confront  the issues of geometric modeling in three dimensions  [Nishihara 
`1979]. Ultimately, nonrigid as well as rigid solids will have to be represented. The 
`characterization of nonrigid solids presents very challenging problems. 
`Nonrigid  solids are often  a useful  way to model time­varying aspects of ob­
`jects. Here, again,  the kind  of model  that  is best depends heavily  on the domain. 
`For example, a useful  mammal  model may be one with a piecewise rigid  linkage 
`(for the skeleton) and some elastic covering (for the flesh). Computer vision in the 
`domain of mammals, either static in various positions or actually moving, might be 
`based on generalized cylinders (Section 9.3). However, another nonrigid domain is 
`that  of  heart  chambers,  that  change  through  time  as  the  heart  beats.  Here  the 
`skeleton is a much less intuitive notion, so a different  model of nonrigidity may ap­
`ply. In most cases, nonrigid objects are modeled as parameterized  rigid objects. In 
`
`264 
`
`IPR2021-00921
`Apple EX1015 Page 278
`
`­
`

`

`the example of the human figure, the parameters  may be joint angles for linkages 
`representing the skeleton. 
`The  last  part  of  this  chapter  deals  with  understanding  line  drawings,  an 
`influential  and well­publicized  subfield  of computer vision. This seemingly simple 
`and accessible domain avoids many of the problems involving early processing and 
`segmentation,  yet it is important  because it has furnished  several  important algo­
`rithmic and geometric  insights.  An important  breakthrough  in this domain was a 
`move from  "image  understanding"  in two dimensions to to an approach based on 
`the three­dimensional world and laws governing three­dimensional solids. 
`
`9.2  SURFACE REPRESENTATIONS 
`
`The  enclosing   surface,  or  boundary, of  a  well­behaved  three­dimensional  object 
`should unambiguously specify  the object  [Requicha  1980]. Since surfaces are what 
`is  seen,  these  representations  are  important  for  computer  vision.  Section  9.2.1 
`considers mainly planar polyhedral surface representations. More complex "sculp­
`tured  surfaces"  [Forrest  1972; Barnhill  and  Riesenfeld  1974; Barnhill  1977]  are 
`treated  in  Section  9.2.2.  Some  useful  surfaces  are  defined  as functions  of  three­
`dimensional  directions from  a central point of origin. Two of these are mentioned 
`in Section 9.2.3. 
`
`9.2.1  Surfaces with Faces 
`
`Figure 9.1 shows the solid representation scheme most familiar  to computer scien­
`tists. Solids are represented  by their  boundaries, or enclosing surfaces,  which are 
`represented  in  terms  of such  primitive  entities  as unbounded  mathematical  sur­
`faces, curves, and points which together may be used to define  "faces." 
` faces;  faces are represented 
`In general, a boundary is made up of a number of
`by mathematical surfaces and by information  about their own boundaries  (consist­
`ing of edges and possibly vertices). A closed surface such as the sphere or a spheri­
`cal harmonic surface of Section 9.2.3 may be thought of as having only one face. 
`To  specify  a  boundary  representation,  one  must  answer  several  important 
`questions of representation  design. What is a face, and how are faces represented? 
`What  is an  edge,  and  how  are  edges  represented?  How  much  extra  information 
`(i.e., useful  but redundant relationships and geometric data) should be kept? 
`What  is a face?  "Face" is an initially appealing  but imprecise notion; it is at 
`its clearest in the context of planar polyhedra. A face should probably always be a 
`subset  of the boundary  of an object;  presumably,  it should have area but no dan­
`gling edges or isolated  points, and  the union  of all the faces  should  make  up  the 
`boundary or the object. Beyond this little can be said. For many purposes it makes 
`sense to have faces overlap; it may be elegant to consider the letter on an alphabet 
`block a special kind of face on the block that is a subset of the face making up the 
`side  of  the  block.  On  the  other  hand,  it  is easy  to  imagine  applications  in  which 
`faces should not overlap in area  (then one easily can compute the surface area of a 
`solid from  its faces). In some objects, just what  the faces are is purely  a matter of 
`
`Sec.  9.2  Surface  Representations 
`
`265 
`
`IPR2021-00921
`Apple EX1015 Page 279
`
`

`

`1 
`4, wm 
`
`^m^ 
`
`Fig.  9.1  A volume and the faces of a 
`boundary representation. 
`
`opinion  (Fig. 9.2). In short, any single definition  of face is likely to be inadequate 
`for some important application. 
`The availability of explicit representations of
` edges,  faces, and vertices makes 
`boundary representations quite useful  in computer vision and graphics. The com­
`putational advantages of polyhedral surfaces are so great that they are often  pressed 
`into service as approximate representations of nonpolyhedra  (Fig. 9.3). 
`An  influential  system  for  using  face­based  representations  for  planar  po­
`lyhedral objects is the "winged edge" representation  [Baumgart
` 1972].  Included in 
`the system is an editor for creating complex polyhedral objects  (such as that of Fig. 
`9.3)  interactively. The system uses rules for construction based on the theorem of 
`Euler that if  Fis the number  of vertices in a polyhedron,  is the number of edges, 
`and Fthe  number  of faces,  then  V
` —   E  +  F =  2. In fact,  the formula  can be ex­
`tended  to  deal  with  non­simply  connected  bodies.  The  extended  relation  is 
`V  ­  E  + F =  2(2?
` —   H) y  with  B being  the  number  of  bodies  and  H  being  the 
`
`266 
`
`Ch.  9  Representations  of  Three­Dimensional  Structures 
`
`Fig.  9.2  What are the faces? 
`
`IPR2021-00921
`Apple EX1015 Page 280
`
`

`

`Fig.  9.3  A  polyhedral  approximation  to  a  portion  of  a  canine  heart  at  systole  and 
`diastole. Both  exterior  (coarse grid)  and  interior  surfaces  (fine  grid)  are  shown. 
`
`number of holes, or "handles," each resulting from  a hole through a body  [Laka­
`tos 1976]. Baumgart's system uses these rules to oversee and check certain validity 
`conditions on the constructions made by the editor. 
`The "winged edge" polyhedron  representation achieves many desiderata  for 
`boundary  representations  in  an  elegant  way.  This  representation  is  presented 
`below  to  give  a flavor of  the  features  that  have  been  traditionally  found  useful. 
`Given  as  primitives  the  vertices,  edges,  faces,  and  polyhedra  themselves,  and 
`given various relations between these primitives, one is naturally thinks of a record 
`and pointer  (relational) structure in which the pointers capture the binary relations 
`and  the  records  represent  primitives  and  contain  data  about  their  locations  or 
`parameters. 
`In the winged edge representation, there are data structure records, or nodes, 
`which contain fields holding  data or  links  (pointers)  to other  nodes. An  example 
`using this structure  to describe a tetrahedron  is shown  in Fig. 9.4. There are  four 
`kinds  of nodes: vertices, edges,  faces,  and  bodies. To allow convenient  access to 
`these nodes, they are arranged in a circular doubly linked list.  The body nodes are 
`actually  the  heads  of  circular  structures  for  the  faces,  edges,  and  vertices  of  the 
`body. Each face points to one of its perimeter edges, and each vertex points to one 
`of the edges impinging on it. Each edge node has links to the faces on each side of 
`it, and the vertices at either end. 
`Figure  9.4  shows  only  the  last­mentioned  links  associated  with  each  edge 
`node.  The  reader  may  notice  the  similarity  of  this  data  structure  with  the  data 
`structure  for  region  merging  in  Section  5.4.  They  are  topologically  equivalent. 
`Each edge also has associated four links which give the name "winged edge" to the 
`representation.  These  links  specify  neighboring  edges  in  order  around  the  two 
`faces  which  are  associated  with  the  edge.  The  complete  link  set  for  an  edge  is 
`shown  in  Fig.  9.5,  together  with  the  link  information  for  bodies,  vertices,  and 
`faces. To allow unambiguous traversal around faces, and to preserve the notion of 
`
`Sec.  9.2  Surface  Representations 
`
`267 
`
`IPR2021-00921
`Apple EX1015 Page 281
`
`

`

`Fig.  9.4  A subset of edge links for
`tetrahedron  using the "winged edge" 
`representation. 
`
` a 
`
`interior and exterior of  a  polyhedron, a preferential  ordering of vertices and lines is 
`picked  (counterclockwise, say, as seen from outside the polyhedron). 
`Data fields in each  vertex  allow storage  of  three­dimensional  world coordi­
`nates,  and  also  of  three­dimensional  perspective  coordinates  for  display.  Each 
`node has fields specifying  its node type, hidden line elimination  information,  and 
`other  general  information.  Faces  have fields for  surface  normal  vector  informa­
`tion, surface reflectance,  and color characteristics. Body nodes carry links to relate 
`them to a tree structure of bodies in a scene, allowing for hierarchical arrangement 
`of subbodies into complex  bodies. Thus body node data describe the scene struc­
`ture; face node data describe surface characteristics; edge node data give the topo­
`logical  information  needed  to  relate faces,  edges,  and  vertices;  and  vertex  node 
`data describe the three­dimensional vertex location. 
`This rich and redundant structure lends itself to efficient  calculation of useful 
`functions  involving  these  bodies.  For  instance,  one  can easily follow  pointers  to 
`extract the list of points around a face, faces around a point, or lines around a face. 
`Winged edges are not a universal boundary representation for polyhedra,  but they 
`do give an idea of the components to a representation  that are likely to be  useful. 
`Such a representation  can be made efficient  for  accessing all faces,  edges, or ver­
`tices;  for  accessing  vertex  or  edge  perimeters;  for  polyhedron  building;  and  for 
`splitting  edges  and  faces  (useful  in  construction  and  hidden­line  picture produc­
`tion, for instance). 
`
`9.2.2  Surfaces Based on Splines 
`
`The natural extension  of polyhedral surfaces is to allow the surfaces  to be curved. 
`However,  with an arbitrary  number  of edges for  the surface,  the  interpolation  of 
`
`268 
`
`Ch.  9  Representations  of  Three­Dimensional  Structures 
`
`IPR2021-00921
`Apple EX1015 Page 282
`
`

`

`Boundary  Representation  Node Accessing  Functions 
`
`To enter and traverse Face ring of
` a  body: 
`NextFace, PreviousFace: 
`Body or  Face  ­»■  Face 
`
`To enter and traverse Edge ring of
` a  body: 
`NextEdge, PreviousEdge:  Body or  Edge  ­*■  Edge 
`
`To enter and traverse Vertex  ring of a body: 
`NextVert, PreviousVert: 
`Body or  Vertex ­* Vertex 
`First  Edge of a Face: 
`FirstEdge:  Face ­* Edge 
`FirstEdge of a Vertex: 
`FirstEdge:  Vertex ­> Edge 
`Faces of  an  Edge: 
`[see diagram in  (a)] 
`N(ext) Face,  P(revious)  Face:   Edge ­>  Face 
`Vertices of an Edge: 
`[see diagram in  (a)] 
`N(extVert,  P(revious)Vert: 
`Edge  ­►  Vertex 
`Neighboring Wing Edges of an Edge: 
`[see diagram in  (a)] 
`NCW, NCCW:  Edge  ­<•  Edge 
`(NFace Edge Clockwise, 
`NFace Edge Counterclockwise) 
`(PFace Edge Clockwise, 
`PFace Edge Counterclockwise 
`
`PCW, PCCW:  Edge ­* Edge 
`
`(b) 
`
`NCCW(£) 
`
`PCW{£) 
`
`5. 
`
`NFacelf) 
`
`PFace(£) 
`
`{  Edge 
`e
`
`NVert(f) 
`
`NCW(£) 
`
`PCCW(£) 
`
`(a) 
`
`Fig.  9.5 
`
`(a) Node accessing functions,  (b) Semantics of winged edge functions. 
`
`interior face points becomes impractically complex. For that reason, the number of 
`edges for  a  curved face is usually restricted to three or four. 
`A  general  technique  for  approximating  surfaces  with  four­sided  surface 
`patches is that  of Coons  [Coons  1974]. Coons specifies  the four  sides of the patch 
`with  polynomials.  These  polynomials  are  used  to  interpolate  interior  points. 
`Although this is appropriate for synthesis, it is not so easy to use for analysis. This 
`is because of the difficulty  of registering the patch edges with image data. A given 
`surface will admit to many patch decompositions. 
`An  attractive  representation  for  patches  is  splines  (Fig.  9.6).  In  general, 
`two­dimensional spline interpolation is complex: For two parameters wand  vinter­
`polate with 
`
`x(w,  v)  =  £  X  VijBijiu, v) 
`'
`J
`similar to Eq.  (8.4). However, for certain applications a further  simplification  can 
`be  made.  In  a  manner  analogous  to  (8.9)  define  a  grid  of  knot  points  v
`corresponding to  Xy  and related by 
`
`(9.1; 
`
`y 
`
`(9.2) 
`
`Xij  ­  MVij 
`Now  rather  than  interpolating  in  two  dimensions  simultaneously,  interpolate  in 
`one direction, say /, to obtain 
`xiJ(t)=[P 
`
`t 2 
`
`t 
`
`l][C][v ;_ U o,v,, 0,v / + U o (v / + 2,, 0] 7" 
`
`(9.3) 
`
`for each value ofj.  Now compute v„(f)  by solving 
`
`Xij(t)  =   M\jj(t) 
`
`Sec. 9.2  Surface  Representations 
`
`(9.4) 
`
`269 
`
`IPR2021-00921
`Apple EX1015 Page 283
`
`

`

`Fig.  9.6  Using spline curves to model 
`the surface of an object: a portion of a 
`human spinal column taken from  CAT 
`data. 
`for each value of  t.  Finally, interpolate in the other direction and solve: 
`s 2  s 
`xiJ(s,t)=[s3 
`l][C][r l­ l.jU),TuU),vl+ijU),v,+2jO)] 
`This is the basis for the spline filtering algorithm discussed in Section 3.2.3. 
`Some advantages of spline surfaces for vision are the following. 
`1.  The spline representation  is economical: the space curves are represented as a 
`sparse set of knot points from which the underlying curves can be interpolated. 
`It  is easy  to  define  splines  interactively  by giving  the  knot  points;  reference 
`representations may be built up easily. 
`It is often  useful  to search the image in a direction perpendicular to the model 
`reference surface. This direction is a simple function  of the local knot points. 
`
`(9.5) 
`
`2. 
`
`3. 
`
`9.2.3  Surfaces That Are Functions on the Sphere 
`
`Some surfaces  can  be expressed  as functions  on the "Gaussian  sphere."  (the dis­
`tance from  the origin to a point  on the surface  is a function  of the direction of the 
`point,  or of its longitude  and latitude if it were radially projected  on a sphere with 
`the  center  at  the  origin.)  This  class of  surfaces,  although  restricted,  is useful  in 
`some  application  areas  [Schudy  and  Ballard  1978,  1979]. This  section  explores 
`briefly  two schemes for  representation  of these surfaces.  The first specifies  expli­
`citly  the distance of the surface  from  the origin for a set of vector directions  from 
`the origin. The second is akin to Fourier descriptors; an economically specified  set 
`of  coefficients  characterizes  the  surface  with  greater  accuracy  as  the  number  of 
`coefficients  increases. 
`Direction­Magnitude  Sets 
`One  approximation  to a spherical  function  is to specify  a number  of  three­
`dimensional  direction  vectors  from  the  origin  and  for  each  a magnitude.  This is 
`</>, p)  points in a spherical  coordinate system 
`equivalent  to specifying  a set of  (0,
`(Appendix  1). These points are on the surface to be represented; connecting them 
`yields an approximation. 
`
`270 
`
`Ch.  9  Representations  of  Three­Dimensional  Structures 
`
`IPR2021-00921
`Apple EX1015 Page 284
`
` 
`

`

`It is often convenient to represent directions as points on the unit  (Gaussian) 
`sphere  centered  on  the  origin.  The  points  may  be connected  by straight  lines  to 
`form  a  polyhedron  with  triangular,  hexagonal  or  rhomboidal  faces.  Moving  the 
`points  on  the  sphere  out  (or  in)  by  their  associated  magnitude  distorts  this  po­
`lyhedron, moving its vertices radically out or in. 
`The spherical function  determines the distance of face vertices from  the ori­
`gin.  Resolution  at  the  surface  increases  with  the  number  of  faces.  An  approxi­
`mately  isotropic  distribution  of  directions  over  the  surface  may  be  obtained  by 
`placing the face vertices (directions) in accordance with "geodesic dome"­like cal­
`culations which make the faces approximately equilateral triangles [Clinton 1971]. 
`Although  the  geodesic  tesselation  of  the  sphere's  surface  is more  complex 
`than a straightforward  (latitude and longitude, say) division, its pleasant properties 
`of isotropy and display  [Brown 1979a; 1979b; Schudy and Ballard 1978] sometimes 
`recommend  it.  Some  example  shapes  indicating  the  range  of  representable  sur­
`faces are given in Fig. 9.7. Methods for tesselating the sphere are given in Appen­
`dix 1. 
`
`Spherical Harmonic Surfaces 
`In  two dimensions,  Fourier  coefficients  can  give approximations  to  certain 
`curved  boundaries  (Section  8.3.4).  Analogously  in  three  dimensions,  a  set  of 
`orthogonal  functions  may  be  used  to  express  a  closed  boundary  as  a  set  of 
`coefficients  when the boundary is a function  on the sphere. One such decomposi­
`tion is  spherical  harmonics.   Low order coefficients  capture gross shape characteris­
`tics;  higher  order  coefficients  represent  surface  shape  variations  of higher  spatial 
`  1  represent 
`frequency.  The function  with  m  =  0 is a sphere, the three with  m =
`translation  about  the origin,  the five with  m  =  2 are similar  to prolate and  oblate 
`spheroids, and so forth,  the lobedness of the surfaces increasing with m. A sample 
`three dimensional shape and its "description" is shown in Fig. 9.8. 
`Spherical  harmonics  are  analogs  on  the  sphere  of  Fourier  functions  on  the 
`plane; like Fourier functions,  they are smooth and continuous to every order. They 
` n;  thus they are a doubly infinite set 
`may be parameterized  by two numbers, m and
`of functions which are continuous, orthogonal, single­valued, and complete on the 
`
`t
`
`Sec.  9.2  Surface  Representations 
`
`271 
`
`Fig.  9.7  Sample surfaces described  by 
`some  320 triangular  facets  in a geodesic 
`tesselation. 
`
`IPR2021-00921
`Apple EX1015 Page 285
`
`

`

`Fig.  9.8  A  spherical  harmonic  function  description  of  an  ellipsoid.  Coefficients 
`are displayed  on  the right as grey  levels in the  matrix  format 
`
`"oo 
`
`"01 
`« ,,  
`
`v I2  
`
`v 22 
`
`^li 
`w 02 
`
`"12 
`
`"21 
`
`R(0,4>)=j: 
`
`sphere.  In  combination,  the  harmonics  can  thus  produce  all  "well­behaved" 
`spherical functions. 
`The spherical  harmonic  functions  U mn  (9,<f>)   and  V mn  (9,<f>)   are defined  in 
`polar coordinates by: 
`Um„(9,<f>)  =  cos  (nO)  sin"  (<f>)P(m,   n, cos(0)) 
`  n, cos(</>)) 
`Ymn(0>  0)  =  sin (n9) sin" (<p)P(m,
`with in =  0,1,2,  ..., M\  n
` —   0,1, ..., m. Here P(m,  n, x)  is the «th  derivative of 
` x.   To represent an arbitrary shape, 
`the  /wth Legendre polynomial as a function  of
`let the radius R in polar coordinates be a linear sum of these spherical harmonics: 
`M 
`m 
`Z   A m„ U mn(9,  <f>)   +  B mn V mn(9,  0) 
`OT  = 0  « =  o 
`Any  continuous  surface  on  the  sphere may  be represented  by a set  of  these  real 
`constants;  reasonable  approximations  to heart  volumes are obtained  with  m <  5 
`[Schudy and Ballard 1979]. 
`Figure  9.9  shows  a few  simple  combinations  of  functions  of  low  values of 
`(m,  n). The sphere, or  (0,0)  surface, is added to the more complex ones to ensure 
`positive volumes and drawable surfaces. 
`Spherical harmonics have the following attractive properties. 
`1.  They are orthogonal on the sphere under the inner product; 
`
`(9.6) 
`(9.7) 
`
`(9.8) 
`
`272 
`
`Ch.  9  Representations  of  Three­Dimensional  Structures 
`
`IPR2021-00921
`Apple EX1015 Page 286
`
`

`

`Fig.  9.9  Simple combinations of functions. 
`
`(«,  v)   —   J  uv   s'm<f>   dO  d<f> 
`
`2.  The functions are arranged in increasing order of spatial complexity. 
`3.  The whole set is complete; any twice­differentiable  function  on the sphere can 
`be approximated arbitrarily closely. 
`Spherical harmonics can provide compact, nonredundant descriptions of sur­
`faces  that  are  useful  for  analysis  of shape,  but  are  less useful  for  synthesis.  The 
`principal disadvantages are that the primitive functions  are not necessarily  related 
`to  the  desired  final  shape  in  an  intuitive  way,  and  changing  a  single  coefficient 
`affects the entire resulting surface. 
`An example of the use of spherical harmonics as a volume representation is 
`the representation of heart volume  [Schudy and Ballard 1978, 1979]. In extracting 
`a volume associated with the heart from  ultrasound data, a large mass of data is in­
`volved.  The data is originally in the form  of echo measurements  taken  in a set of 
`two­dimensional  planes  through  the  heart.  The  task  is  to  choose  a surface  sur­
`rounding the heart volume of interest by optimization techniques that will fit three 
`dimensional  time­varying  data.  The  optimization  involved  is  to  find  the  best 
`coefficients  for the spherical harmonics that define the surface.  The goodness of  fit 
`of a surface is measured by how well it matches the edge of the volume as it appears 
`in the data slices.  To extend spherical harmonics to time­varying periodic data, let 
`the radius R in polar coordinates be a linear sum of these spherical harmonics: 
`M  m 
`R(0,  4>,t)   =H 
`A
`m=0  w=0 
`
`mnU)Umn{9,  0)  +  B mnU)Vmn{9,  0) 
`
`Sec. 9.2  Surface  Representations 
`
`(9.9) 
`
`273 
`
`IPR2021-00921
`Apple EX1015 Page 287
`
`

`

`The functions A  it)  and  B it)  are given by Fourier time series: 
`/ 
`Am„(t)  = a mm  + 2   a >w,icos O­trt/r)  +   b mnism  (2irt/r) 
`/=i 
`
`(9.10) 
`
`Bm„{i) =  b mno + X   c /ww cos  (2TT­r/r)   +   d„ wis\n iltrt/r) 
`i=i 
`where t\s  time, the  a mnh  b mnh  c mnh  and  d mni are arbitrary real constants, and
` T   the 
`period.  Any   continuous  periodically  moving  surface
`  on  the   sphere   may be 
`represented  by  some selection   of  these  real  constants;
`  in the  cardiac application, 
`reasonable approximations to the temporal behavior are obtained with
` t  ^   3. Fig­
`ure 9.10 shows three stages from  a moving­harmonic­surface  representation of the 
`heart in  early systole. The atria,
` at the  top, contract and pump blood into the ven­
`tricles below, after which there is a ventricular contraction. 
`
`(9.11) 
`
`9.3  GENERALIZED  CYLINDER  REPRESENTATIONS 
`
` as 
`
`The volume  of  many biological and manufactured  objects is naturally described
`the  "swept  volume"   of a   two­dimensional
`  set  moved  along  some  three­space 
`curve. Figure 9.11 shows a "translational  sweep" wherein a solid is represented
` as 
`the  volume  swept   by a  two­dimensional
`  set  when   it is  translated  along  a  line.  A 
`"rotational sweep" is similarly defined  by rotating the two­dimensional set around 
`an axis.  In  "three­dimensional  sweeps," volumes are swept. In
` a  "general" sweep 
`scheme,  the  two­dimensional
`  set or   volume   is  swept  along   an  arbitrary  space 
`curve, and  the  set  may vary parametrically along the curve  [Binford  1971; Soroka 
`and Bajcsy  1976; Soroka 1979a; 1979b; Shani
` 1980].  General sweeps are quite a po­
`pular  representation   in  computer  vision,  where  they  go by the  name  generalized 
`cylinders (sometimes "generalized cones"). 
`
`Fig.  9.10  Three stages from a moving har­
`monic surface   (see  text  and  color  insert). 
`
`274 
`
`Ch. 9   Representations   of  Three­Dimensional  Structures 
`
`IPR2021-00921
`Apple EX1015 Page 288
`
`

`

`Sweep 
`
`A, 
`
`Fig.  9.11  A translational sweep. 
`A generalized cylinder  (GC) is a solid whose axis is a 3­D space curve  (Fig. 
`9.12a). At any point on the axis a closed cross section is defined. A usual restriction 
`is that the axis be normal to the cross section. Usually it is easiest to think of an axis 
`space  curve  and  a  cross  section  point  set  function,  both  parameterized  by  arc 
`length  along  the axis curve.  For any solid, there are infinitely  many pairs of axis 
`and cross section functions that can define it. 
`Generalized  cylinders present certain  technical  subtleties in their  definition. 
`For instance, can it be determined whether any two cross sections intersect, as they 
`would if the axis of a circular cylinder were sharply bent  (Fig. 9.12b)
` ?  If the solid is 
`defined as the volume swept by the cross section, there is no conceptual or compu­
`tational  problem.  A problem might occur when computing the surface  of such an 
`object.  If the surface  is expressed  in terms of the axis and cross­section  functions 
`(as below),  the domain  of objects  must  be limited  so that  the boundary  formula 
`indeed gives only points on the boundary. 
`Generalized  cylinders are intuitive and  appealing. Let  us grant  that  "patho­
`logical"  cases  are  barred,  so  that  relatively  simple  mathematics  is adequate  for 
`representing them. There are still technical decisions to make about the represen­
`tation. The axis curve presents  no difficulties,  but a usable representation  for  the 
`cross­section  set  is often  not so straightforward.  The main problem  is to choose a 
`usable coordinate system in which to express the cross section. 
`
`9.3.1  Generalized  Cylinder Coordinate Systems and Properties 
`
`Two mathematical functions  defining axis and cross section for each point define a 
`unique solid with the "sweeping" semantics described above. In a fixed Cartesian 
`coordinate system x, y, z, the axis may be represented  parametrically as a function 
`of arc lengths: 
`
`(9.12) 
`z(s)) 
`a(s)  ­  (x(s),y(s), 
`It is convenient to have a local coordinate system defined  with origin at each 
`point of a (s). It is in this coordinate system that the cross section is defined.  This 
`system  may change  in  orientation  as  the axis winds  through  space, or