(a) 
`
`(b) 
`
`(c) 
`
`(d) 
`
`  (a)  Radiograph,   (b)  Window,  (c) 
`Fig.  4.7   Using  the  Hough  technique   for  circular  shapes,
`Accumulator  array  for r = 3. (d)
` Results  of  maxima  detection. 
`
`circular  boundaries  detected   by the  Hough  technique  are overlaid  on the  original 
`image. 
`
`4.3.3  Trading  Off  Work  in Parameter  Space for Work  in  Image  Space 
`
` to be  oriented  so  that  a 
`Consider the  example  of  detecting ellipses that are known
`principal  axis  is  parallel  to the x  axis.  These  can be  specified   by  four  parameters. 
` for 
`Using the  equation  for  the ellipse together  with its derivative, and substituting
`the known gradient as before, one can solve
` for  two parameters. In the equation 
`
`Ch.  4   Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 142
`
`

`

`( x ­ x o ) 2
`+ ^ y z ^  =  1  
`a2 
`o­
`0, yo,  a,  and  b are parameters. The equation  for  its deriva­
`
`, 
`
`x is an  edge point  and  x
`tive is 
`
`i ^ ^ + o ^^  = 0  
`
`(44) 
`
`dx 
`b 
`a 
`where  dy/dx  =  tan  4>  (x). The  Hough algorithm  becomes: 
`
`Algorithm 4.2:  Hough technique applied to ellipses 
`
`For each discrete value of xand.y,  increment  the point in parameter space given by 
`a, b, x 0,  y 0,  where 
`
`X =  XQ± 
`
`(l  +   /> 2/a 2tan 2<^ 
`
`y­y**   "   ■   u n~2*,*\* 
`(1 +  a 2 tan 2 4>/b 2) 
`
`(4.5) 
`
`( 4 ­ 6) 
`
`that is, 
`
`A (a,  b,  XQ, yo)  := A  (a,  b,  XQ, yo)
`
`  +  1 
`
`For a and   b  each having  m values the computational cost is proportional to  m
`Now  suppose  that  we  consider  all  pairwise  combinations  of  edge  elements. 
`This  introduces  two  additional  equations  like  (4.3)  and  (4.4),  and  now  the  four­
`parameter  point can be determined  exactly. That is, the following  equations can  be 
`solved for a unique x
`0,  yo,  a,  b. 
`
`2. 
`
`  = 1  
`
`(Xl ~  Xo)2   +  ^ pt
`a2 
`b 2 
`  >   (y 2  ­   y 0)2 
`(x2  ­   XQ) 2
`a2 
`
`^_^+yiZ/l±  = 0  
`a1 
`b l 
`dx 
`^Z^L  +  £1Z/1±  = 0 
`b l  dx ­f­ =  tan0 
`a2 
`
`dx 
`
`(—f­  is known  from  the  edge  operator) 
`dx 
`
`(4.7a) 
`
`(4.7b) 
`
`(4.7c) 
`
`(4 .7d) 
`
`4.3  The   Hough Method for
`
` Curve  Detection 
`
`127 
`
`IPR2021-00921
`Apple EX1015 Page 143
`
`

`

`Their solution is left  as an exercise. The amount  of effort  in the former  case 
`was  proportional  to  the  product  of  the  number  of  discrete  values  of  a  and  b, 
`whereas this case involves effort  proportional to the square of the number of edge 
`elements. 
`
`4.3.4  Generalizing the Hough Transform 
`
`Consider  the case where the object  being sought has no simple analytic form,  but 
`has a particular silhouette. Since the Hough technique is so closely related to tem­
`plate matching, and template matching can handle this case, it is not surprising that 
`the Hough technique can be generalized  to handle this case also.  Suppose for  the 
`moment  that  the object  appears in the image with known shape, orientation,  and 
`scale. (If orientation and scale are unknown, they can be handled in the same way 
`that additional parameters were handled earlier.) Now pick a reference point in the 
`silhouette and draw a line to the boundary. At the boundary point compute the gra­
`dient direction and store the reference point as a function  of this direction. Thus it 
`is possible to precompute the location of the reference point from  boundary points 
`given  the gradient angle. The set of all such locations, indexed  by gradient angle, 
`comprises a table termed the i?­table [Ballard
` 1981].  Remember that the basic stra­
`tegy of the Hough technique is to compute the possible loci of reference  points in 
`parameter space from  edge point data in image space and increment the parameter 
`points in an accumulator array. Figure 4.8 shows the relevant geometry and Table 
`4.1 shows the form  of  the i?­table. For  the  moment,  the  reference  point  coordi­
`nates  (x c,  y c)  are  the  only  parameters  (assuming  that  rotation  and  scaling  have 
`been fixed). Thus an edge point  (x, y)  with gradient orientation 0  constrains the 
`possible reference  points to be at {x +  r\
`  (<f>)  cos [«i   (</>)],  y  +  r\(<f>)   sin  [a\ (</>)]} 
`and so on. 
`
`Fig.  4.8  Geometry used to form  the 
`fl­Table. 
`
`128 
`
`Ch.  4  Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 144
`
`

`

`Table 4.1 
`
`INCREMENTATION  IN THE GENERALIZED HOUGH  CASE 
`
`Angle  measured 
`from  figure  boundary 
`to reference point  
`
`k]  where 
`Set of radii [i
`r =   (r,  a) 
`
`</>! 
`4>i 
`
`rj, 
`r/, t\ 
`rlil  ...,xl 
`
`m, ...,  r£ 
`if",  r 2
`
`The generalized Hough algorithm may be described as follows: 
`
`Algorithm 4.3:   Generalized Hough 
`
`reference 
`
`Step  0.   Make a table (like Table 4.1) for the shape to be located. 
`array   of   possible 
`Step  1.   Form   an   accumulator 
`A (x cmm:  x cmax,  y cmm  :y cmax)  initialized to zero. 
`Step  2.   For each edge point do the following: 
`Step 2.1.   Compute 0(x) 
`Step 2.2a.  Calculate the possible centers; that is, for  each table entry  for 
`<f>, compute 
`xc:=x  +  r<f>   cos[a(0)] 
`yc  :=  y  + r   (f>   sinia(</>)] 
`
`points 
`
`Step 2.2b. 
`
`Increment the accumulator array 
`
`A (x c, y c)  := A (x c, y c)  +  1 
`Step  3.  Possible locations for the shape are given by maxima in array A. 
`
` a  shape are shown in  Fig. 4.9. 
`The  results of  using this transform  to detect
`Figure 4.9a shows an image of shapes. The R­table has been  made for the middle 
`shape.  Figure  4.9b  shows  the  Hough  transform  for  the  shape,  that  is, A (x
`displayed  as an  image.  Figure  4.9c  shows  the  shape  given  by  the  maxima  of 
`
`c,  y c) 
`
`Sec.  4.3   The   Hough Method for
`
` Curve  Detection 
`
`129 
`
`IPR2021-00921
`Apple EX1015 Page 145
`
`

`

`Fig.  4.9  Applying  the  Generalized  Hough  technique,  (a)  Synthetic  image,  (b)  Hough 
`Transform  A (x c,  y c)  for  middle  shape,  (c)  Detected  shape,  (d)  Same  shape  in  an  aerial 
`image setting. 
`
`A (x c, y c)  overlaid  on  top  of  the  image.  Finally,  Fig.  4.9d  shows  the  Hough 
`transform  used to detect a pond of the same shape in an aerial image. 
`What about the parameters of scale and rotation, Sand  01 These are readily 
`accommodated by expanding the accumulator array and doing more work in the in­
`crementation step.  Thus in step  1   the accumulator array is changed to 
`
`^■ X­cmi n • ­*rmax >  .Vcmin  • J'emax '  "^min  •   *^max>  min  •  "max 
`and step 2.2a is changed to 
`
`130 
`
`Ch.  4  Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 146
`
`

`

`  <f>   do 
`
`for each table entry for
`for each S  and 9 
`xc  :=  x+   r(<j))Scos  [a($)  +  9] 
`yc  := y  +  r  (0)Ssin  [a (</>)  + 9] 
`
`Finally, step 2.2b is now 
`
`A (x c,  y c,  S, 9)  :=  A  (x c> y c,  S, 9)  + 1 
`
`4.4  EDGE FOLLOWING AS GRAPH SEARCHING 
`
`A graph  is a general  object  that  consists  of  a set  of  nodes  {«,•} and  arcs  between 
`nodes  <n h  «,­>. In this section we consider graphs whose arcs may have numeri­
`cal weights or  costs  associated with them. The search for the boundary of an object 
`is cast as a search for the lowest­cost path between two nodes of a weighted graph. 
`Assume  that  a gradient  operator  is applied to the gray­level  image, creating 
` <j>(x).   Now interpret  the elements 
`the magnitude image six)  and direction  image
`of the direction image  <f>(x)   as nodes in a graph, each with a weighting factor s (x). 
` <f>  (x,),  </> (x,) are ap­
`Nodes x h  Xj have arcs between them if the contour directions
`propriately aligned with the arc directed in the same sense as the contour direction. 
`Figure 4.10 shows the interpretation. To generate Fig. 4.10b impose the following 
`restrictions.  For an arc to connect from  x, to x,­, Xj must be one of the three possi­
` </> (x,) and, furthermore, g (x
`ble eight­neighbors in front of the contour direction
`
`;) 
`
`\
`
`/
`
`\
`
`\
`
`\
`
`/
`
`\ 
`
`/ 
`/
`\ 1 
`\ 
`
`\
`
`\ 
`
`1 
`I 
`
`/ 
`
`/ 
`
`\ 
`
`\ 
`
`\ 
`
`\ 
`
`1  — 
`— 
`
`\
`
`I 
`
`\
`
`Fig.  4.10 
`
`Interpreting  a  gradient image as  a  graph (see text). 
`
`Sec.  4.4  Edge  Following  as Graph  Searching 
`
`1 31 
`
`IPR2021-00921
`Apple EX1015 Page 147
`
`

`

` |{[<£  (x,) ­   <f>  (xj)]  mod  2TT}\  < 
`>  T, g(xj)  >  T, where  Tis a chosen constant, and
`it 12.   (Any or all of these restrictions may be modified to suit the requirements of a 
`particular problem.) 
`A  to x B  one can apply  the  well­known 
`To generate  a path  in a graph  from  x
`technique  of heuristic  search  [Nilsson  1971, 1980]. The  specific  use of  heuristic 
` 1972].  Suppose: 
`search to follow edges in images was first proposed by [Martelli
`1.  That the path should follow contours that are directed from  x
`A  to  x B 
`2.  That  we have a method  for  generating  the  successor  nodes  of a given  node 
`(such as the heuristic described above) 
`3.  That we have an evaluation function /(xj)  which is an estimate of the optimal 
`cost path from  x A  to x B  constrained to go through x, 
`Nilsson expresses /(x,)  as the sum of two components: g(x,­), the estimated cost 
`of journeying from  the  start node  x A  to x h  and h (x,), the estimated cost of the path 
`from x, to x B,  the goal node. 
`With the foregoing preliminaries, the heuristic search algorithm  (called the A 
`algorithm by Nilsson) can be stated as: 
`
`Algorithm 4.4:   Heuristic Search (the A Algorithm) 
`
`1.  "Expand"  the  start  node  (put  the  successors  on  a  list  called  OPEN  with 
`pointers back to the start node). 
`B,  then stop. Trace 
`2.  Remove the node x, of minimum /from  OPEN. If x,  =  x
`back through pointers to find optimal path. If OPEN is empty, fail. 
`3.  Else expand node x,, putting successors on OPEN with pointers back to x,. Go 
`to step 2. 
`
`The component h (x,) plays an important role in the performance of the algorithm; 
` is  a minimum­cost
` search as  opposed to a  heuristic 
`if h (x,)  =  0 for all /, the algorithm
`search. If h (x,)  >  /J*(X,)  (the actual optimal cost), the algorithm may run  faster, 
`but  may miss the minimum­cost  path.  If  h (x
`;)  <  /?*(x,), the search  will always 
`produce  a  minimum­cost  path,  provided  that  h also  satisfies  the  following  con­
`sistency condition: 
`
`If for any two nodes  x,­  and  Xj,  k  (x,­,
`Xj to  Xj  (if possible), then 
`k(xh  Xj)  >  hHxJ  ­  hHxj) 
`
` x,­) is the minimum cost of getting from 
`
`With our edge elements, there is no guarantee that a path can be found  since 
`there  may be insurmountable  gaps between x^  and x
`B.  If finding the edge is cru­
`cial, steps should be taken to interpolate edge elements prior to the search, or gaps 
`may be crossed by using the edge element definition of [Martelli 1972].  He defines 
`
`132 
`
`Ch.  4  Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 148
`
`

`

`edges on the image grid structure so that an edge can have a direction even though 
`there is  no local gray­level change. This definition is depicted in Fig.
` 4.1  la. 
`
`4.4.1  Good Evaluation Functions 
`
`A good evaluation function  has components specific to the particular task as well as 
`components  that are  relatively  task­independent.  The  latter  components  are dis­
`cussed here. 
`1.  Edge  strength.   If edge strength  is a factor,  the cost of adding a particular  edge 
`element at x can be included as 
`M  —   six) 
`
`where M   —   max  5(x) 
`
`X 
`
`2.  Curvature.   If low­curvature  boundaries  are desirable, curvature  can be meas­
`ured as some monotonically increasing function of 
`difftyix:)  ­  <f>(Xj)] 
` Xj  and x (. 
`where diff measures the angle between the edge elements at
`3.  Proximity   to an  approximation.   If  an  approximate  boundary  is known,  boun­
`daries near this approximation can be favored by adding: 
`
`d  =  dist  (x hB) 
`to the cost measure. The dist operator measures the minimum distance of the 
`new point x ; to the approximate boundary B. 
`4.  Estimates  of  the distance to the
` goal.  If the curve is reasonably linear, points near 
`the goal may  be favored  by estimating  h as d{x
`h  x goal), where dis  a distance 
`measure. 
`Specific  implementations  of  these  measures  appear  in  [Ashkar  and  Modestino 
`1978; Lester etal. 1978]. 
`
`4.4.2  Finding All the Boundaries 
`
`What if the objective is to find
` all  boundaries in the image using heuristic search? 
`In  one  system  [Ramer  1975]  Hueckel's  operator  (Chapter  3)  is used  to  obtain 
`
`7*K 
`
`(a) 
`
`J 0 
`
`(b) 
`
`^ 
`
`(c) 
`
`Fig.  4.11  Successor conventions in heuristic search  (see text). 
`
`Sec. 4.4  Edge Following  as Graph  Searching 
`
`133 
`
`IPR2021-00921
`Apple EX1015 Page 149
`
`

`

`strokes, another  name  for  the  magnitude  and  direction  of  the  local  gray­level 
`changes.  Then these strokes are combined  by heuristic search to form  sequences 
`of edge elements called  streaks.  Streaks are an intermediate organization which are 
`used  to  assure  a  slightly  broader  coherence  than  is  provided  by  the  individual 
`Hueckel edges. A bidirectional search is used with four eight­neighbors defined in 
`front of the edge and four eight­neighbors behind the edge, as shown in Fig.
`The search algorithm is as follows: 
`1.  Scan the stroke (edge) array for the most prominent edge. 
`2.  Search in front of the edge until no more successors exist (i.e.,
`tered) . 
`3.  Search behind the edge until no more predecessors exist. 
`4. 
`If the bidirectional  search generates a path of
` 3  or more strokes, the path is a 
`streak. Store it in a streak list and go to step 1. 
`Strokes that are part of a streak cannot be reused; they are marked when used 
`and subsequently skipped. 
`There  are other  heuristic  procedures  for  pruning  the  streaks to  retain  only 
`prime streaks.  These are shown in Fig. 4.12.  They are essentially similar to the re­
`
` a  gap is encoun­
`
` 4.1  lb. 
`
`/ 
`
`/
`
`S 
`i
`\
`
`s
`
`4, </
`
`** 
`
`\
`\
`
`\
`\
`
`Fig.  4.12  Operations  in the creation  of prime  streaks. 
`
`134 
`
`Ch. 4   Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 150
`
`

`

`(a) 
`
`Fig.  4.13  Ramer's results. 
`
`Iaxation  operations  described  in Section  3.3.5. The resultant  streaks  must  still be 
`analyzed  to  determine  the  objects  they  represent.  Nevertheless,  this  method 
`represents a cogent attempt to organize bottom­up edge following in an image. Fig. 
`4.13 shows an example of Ramer's technique. 
`
`Sec. 4.4  Edge Following  as Graph  Searching 
`
`135 
`
`IPR2021-00921
`Apple EX1015 Page 151
`
`

`

`4.4.3  Alternatives to the  A  Algorithm 
`
`The  primary  disadvantage  with  the heuristic  search  method  is that  the  algorithm 
`must  keep track  of a set of current  best  paths  (nodes), and  this set  may  become 
`very large. These nodes represent  tip nodes for  the portion  of the tree of possible 
`paths that has been already  examined.  Also, since all the costs are nonnegative, a 
`good  path  may  eventually  look  expensive  compared  to  tip  nodes  near  the  start 
`node. Thus, paths from  these newer nodes will be extended by the algorithm even 
`though,  from  a practical standpoint,  they are unlikely. Because of these disadvan­
`tages, other less rigorous search procedures have proven to be more practical, five 
`of which are described below. 
`Pruning the Tree  of Alternatives 
`At  various  points  in  the  algorithm  the  tip  nodes  on  the  OPEN  list  can  be 
`pruned in some way. For example, paths that are short or have a high cost per unit 
`length  can  be  discriminated  against.  This  pruning  operation  can  be  carried  out 
`whenever the number of alternative tip nodes exceeds some bound. 
`Modified Depth­First Search 
`Depth­first  search is a meaningful  concept if the search space is structured as 
`a tree. Depth­first  search means always evaluating the most recent expanded  son. 
`This type of search is performed  if the OPEN list is structured  as a stack in the A 
`algorithm and the top node is always evaluated  next. Modifications  to this method 
`use  an  evaluation  function  /  to rate  the successor  nodes  and  expand  the  best of 
`these. Practical examples can be seen in  [Ballard and Sklansky  1976; Wechsler and 
`Sklansky 1977; Persoon 1976]. 
`Least Maximum  Cost 
`In this elegant idea  [Lester 1978], only the maximum­cost arc of each path is 
` g.  This is like finding a mountain pass at minimum altitude. 
`kept as an estimate of
`The advantage  is that g does  not  build  up continuously  with  depth  in  the  search 
`tree, so that good paths may be followed  for a long time. This technique has been 
`applied to finding the boundaries of blood cells in optical microscope images. Some 
`results are shown in Fig. 4.14. 
`Branch and Bound 
`The crux of this method is to have some upper bound on the cost of the path 
`[Chien and Fu  1974].  This may be known beforehand  or may be computed by actu­
`ally generating a path  between  the desired  end  points. Also, the evaluation  func­
`tion must be monotonically increasing with the length of the path.  With these con­
`ditions  we  start  generating  paths,  excluding  partial  paths  when  they  exceed  the 
`current bound. 
`Modified Heuristic Search 
`Sometimes  an  evaluation  function  that  assigns negative  costs leads to good 
`results. Thus good  paths keep getting  better with  respect  to the evaluation  func­
`tion,  avoiding  the  problem  of  having  to  look at all paths  near  the starting  point. 
`
`136 
`
`Ch.  4  Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 152
`
`

`

`(a) 
`
`(b) 
`
`  in  heuristic  search   to   find  cell  boundaries
`Fig.  4.14   Using  least  maximum  cost
`  (b)  The completed  boundary. 
`scope  images,   (a)  A stage  in the  search  process,
`
`  in   micro­
`
`However,  the  price  paid  is the  sacrifice   of  the  mathematical  guarantee  of   finding 
`  be   reflected   in   unsatisfactory  boundaries.  This 
`the  least­cost  path.  This  could
`method  has  been  used   in  cineangiograms  with  satisfactory  results  [Ashkar
` and 
`Modestino 1978]. 
`
`4.5  EDGE FOLLOWING  AS DYNAMIC  PROGRAMMING 
`
`4.5.1  Dynamic  Programming 
`
` a  technique  for  solving op­
`Dynamic programming  [Bellman and Dreyfus  1962] is
`timization  problems when  not all  variables  in the  evaluation  function  are interre­
`lated simultaneously. Consider the problem 
`max h  Cxi,  x 2, x 3, x 4) 
`
`(4.8) 
`
` a  global maximum 
` /?,  the only technique that guarantees
`If nothing is known about
`is  exhaustive  enumeration   of all  combinations   of  discrete  values   of  x\,...  
`,x 4. 
`Suppose that 
`
`(4.9) 
`hi­)   = hi (x h  x 2)  + h 2 (x 2, x 3)  +  /? 3 Gc 3, x 4) 
`xi  only depends on Xi in
` h\.  Maximize over  xi in hi
` and tabulate the best value of 
`hi (xj   x 2) for each  x 2: 
`
`fi  (x 2) = max hi (x
`x\
`Since the values  of  h 2 and A 3 do not depend o n x
`
`h  x 2) 
`
`(4.10) 
`
`h  they need not be considered
`
` at 
`
`Sec. 4.5   Edge Following  as Dynamic  Programming 
`
`137 
`
`IPR2021-00921
`Apple EX1015 Page 153
`
`

`

`2  by computing f
`this point. Continue in this manner and eliminate x
`f2  (x 3)  = maxl/j  Gc 2) + h 2 {x 2, x 3)] 
`
`2  Gc 3) as 
`(4.11) 
`
`and 
`
`so that  finally 
`
`/ 3  (x 4)  =  max  l/
`xi 
`
`2  Gc 3) +  /? 3U3, x 4)] 
`
`max  h =  max f
`
`3  (x 4) 
`
`(4.12) 
`
`(4.13) 
`
`  =   0, 
`Generalizing the example to ./V variables, where/o (­*i)
`/„_,  (x„) = max  [f„_ 2 (jc„­i)  +   /?„_  1  C^c„_!,  x n)] 
`x„­\ 
`max h  (x h  . ..  ,x N)  =  max/^­,  (*#) 
`*/  
`X N 
`N  (x N+i)  one must evaluate 
`If each  X;  took on 20 discrete values, then to compute f
`the maximand  for  20 different  combinations of x
`N  and x N+\,  so that the resultant 
`computational effort  involves (TV  —   1)20 2 +  20 such evaluations. This is a striking 
`improvement over exhaustive evaluation, which would involve 20^ evaluations of 
`hi 
`
`(4.14) 
`
`Consider  the  artificial  example  summarized  in  Table  4.2.  In  this  example, 
` h,  are completely described by 
`each x can take on one of three discrete values.  The
`their respective tables. For example, the value of/?,(0,  1)  =  5. The solution steps 
` x\   that maximizes 
`are summarized  in Table  4.3.  In step 1, for each x
`2  the value of
` h.  Store 
`h\{x\,  x 2)  is computed.  This is the largest entry in each of the columns of
` x\   also as a function  of
`the function  value as f\  (x
`2)  and the optimizing value of
`  x 2. 
`In step 2, add  f\(x 2) 
`to h 2(x2,  x 3).  This is done by adding f\  to each row of  h
`2, 
`thus computing the quantity inside the braces of  (4.11). Now to complete step 2, 
`for each x 3,  compute the x 2  that maximizes h 2  + f\  by selecting the largest entry 
`in each row of the appropriate table. The rest of the steps are straightforward  once 
`these are understood. The solution is found  by tracing back through the tables. For 
`3 is —  1,  and therefore the best x
`2 is  3  and 
`example, for x 4 =   2  we see that the best x
`x\  is 1. This step is denoted by arrows. 
`
`X  X 2 
`
`0 
`
`1 
`
`2 
`
`3 
`
`3 
`
`8 
`
`3 
`
`2 
`
`7 
`
`1 
`
`3 
`
`1 
`
`5 
`
`2 
`
`6 
`
`/), 
`
`Table 4.2 
`
`DEFINITION  OF h
`
`0 
`
`7 
`
`1 
`
`6 
`
`\ 3 
`*2 
`
`\  ­1 
`
`1 
`
`2 
`
`3 
`
`1 
`
`1 
`
`5 
`
`h 2 
`
`1 
`
`1 
`
`3 
`
`2 
`
`138 
`
`Ch.  4  Boundary  Detection 
`
`0 
`
`1 
`
`2 
`
`5 
`
`3 
`
`4 
`
`6 
`
`1 
`
`h 3 
`
`X 
`3 ­1 
`
`8 
`
`1 
`
`7 
`
`2 
`
`9 
`
`IPR2021-00921
`Apple EX1015 Page 154
`
`

`

`M E T H OD  OF  S O L U T I ON  USING  D Y N A M IC  P R O G R A M M I NG 
`
`Table  4.3 
`
`Step 1 
`
`x 2 
`
`1 
`
`2 
`
`'vO 
`
`u
`
`6 
`
`7 
`
`*i 
`
`2 
`
`0 
`
`8  0 
`
`\ *3 
`
`2 
`
`Step 2 
`
`1 
`
`2 
`
`7 
`
`8 
`
`\  ­1 
`
`0 
`
`1 
`
`7 
`
`13 
`
`8  0 
`
`x 
`
`2 
`
`\  \  \ 
`\ 0 
`
`/ 
`
`\ 
`
`x, 
`
`\  \  \  \ 
`\ ­1 
`(0­­1 
`
`13 
`
`14 
`
`10 
`
`20 
`
`21 
`
`3  0 0  ­0 
`
`\  1 
`
`\ \  \ 
`
`\ x 4 
`X'J 
`
`\ 
`
`1 
`
`2 
`
`3 ­1  0  0  0 
`
`Step 3 
`
`0 
`
`1 
`
`16 
`
`15 
`
`17 
`
`14 
`
`20 
`
`11 
`
`Step 4:  Optimal x/s  are found by examing tables 
`(dashed line shows the order  in which they 
`are recovered). 
`
`Solution:  h*  = 22 
`x*  = 1,x£  = 3 , x!  = ­ 1 , *4  =2 
`
`4.5.2  Dynamic  Programming for  Images 
`
`© 
`
`To  formulate  the  boundary­following  procedure  as  dynamic  programming,  one 
`must define an evaluation function  that embodies a notion of the "best  boundary" 
`[Montanari  1971; Ballard 1976].  Suppose that a local edge detection operator is ap­
`
`4.5  Edge Following  as Dynamic  Programming 
`
`139 
`
`IPR2021-00921
`Apple EX1015 Page 155
`
`

`

`plied to a gray­level picture to produce edge magnitude and direction  information. 
`Then one possible criterion for a "good  boundary" is a weighted sum of high cu­
`mulative  edge  strength  and  low  cumulative  curvature;  that  is, for  an  ^­segment 
`curve, 
`
`«—1 
`n 
`/I(XJ, . .. ,x„)  =  £ s ( x *)  +  oc^q(x
`*=1 
`k=\ 
`where the implicit constraint is that consecutive x
`k's  must be grid neighbors: 
`| | x , ­ x , + 1 K V2 
`q(xk>  x k+l)  ­  diff[<f>(x k), <f>(x k+l)] 
`
`x k+i) 
`
`k, 
`
`(4.16) 
`
`(4.17) 
`(4.18) 
`
` Ox)  =  s  (x). 
`where a is negative. The function g we take to be edge strength, i.e., g
`Notice that this evaluation function  is in the form of (4.9) and can be optimized in 
`stages: 
`
`/o(xi)=0 
`h  x 2)  + / 0(x,)l 
`
`/i  (x 2)  =  max Ls(xi)  +  aq(x
`x\ 
`fk(xk+\)  ­  max  Is (x*)   +  aq{x k,  x k+l)  +/ Jfc_1(xA)] 
`xk 
`These equations can be put into the following steps: 
`
`(4.19) 
`(4.20) 
`
`(4.21) 
`
`Algorithm 4.5:   Dynamic Programming for Edge Finding 
`
`1.  S e t / t ­ 1. 
` 5  (x)  ^   T.  For each of these x, define  low­curvature 
`2.  Consider only x such that
`pixels "in front of"  the contour direction. 
`3.  Each of these pixels may have a curve emanating from it.  For k = 1, the curve 
`is one pixel in length. Join  the curve to x that optimizes the left­hand  side of 
`the recursion equation. 
`If k = N, pick the best f
`2. 
`
`N­\  and stop. Otherwise, set k  =  k +1  and go to step 
`
`4. 
`
` curve  emanating from  x 
`This algorithm can be generalized to the case of picking a
`(that we have already generated): Find the end of that curve, and join the best of 
`three curves emanating from  the end of that curve. Figure 4.15 shows this process. 
`The equations for the general case are 
`
`140 
`
`Ch. 4   Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 156
`
`

`

`/ / 
`
`s  \  s 
`
`Fig.  4.15  DP optimization for boundary tracing. 
`
`/o  (xj)  =  0 
`//  (x k+\)  = max[s(x k)  + aq(x k, 
`xk 
`+  //­i(x*)] 
`
`t(x k+l)) 
`
`(4.22) 
`
`where the curve length n is related to a  by a building sequence n (l)  such that n (1) 
`=  1,  n(L)  =  N,  and  nil)  ­  n{l­\) 
`is a member  of  {n(k)\k  =  1,  ...,  / ­  1}. 
`is a function  that  extracts  the  tail  pixel  of  the  curve  headed  by  x
`Also,  t(x k) 
`Further details may be found in [Ballard 1976]. 
`Results from  the area  of tumor  detection  in radiographs give a sense of this 
`method's  performance.  Here it is known  that  the  boundary  inscribes an approxi­
`mately circular tumor, so that circular cues can be used to assist the search. In Fig. 
`4.16, (a) shows the image containing the tumor,  (b) shows the cues, and  (c) shows 
`the boundary found by dynamic programming overlaid on the image. 
`Another  application  of dynamic programming  may  be found  in the pseudo­
`parallel road finder of Barrow [Barrow 1976]. 
`
`4.5.3  Lower Resolution Evaluation Functions 
`
`In  the dynamic programming formulation  just  developed,  the components  g(x
`and  q (x k,  x k+\)  in the  evaluation  function  are very  localized;  the variables x for 
`successive sand qare  in fact constrained to be grid neighbors. This need not be the 
`case: The  x can  be very  distant  from  each  other  without  altering  the  basic  tech­
`nique. Furthermore,  the functions   g  and q need not be local gradient and absolute 
`curvature,  respectively,  but  can  be any  functions  defined  on  permissible  x. This 
`general formulation  of the problem for images was first described by  [Fischler and 
`
`k. 
`
`k) 
`
`Sec. 4.5  Edge Following  as Dynamic  Programming 
`
`141 
`
`IPR2021-00921
`Apple EX1015 Page 157
`
`

`

`Elschlager  1973]. The  Fischler  and  Elschlager  formulation  models  an  object  as a 
`set  of  parts  and  relations  between  parts,  represented  as a graph.  Template  func­
`tions, denoted by g(x),  measure how well a part of the model matches a part of the 
`image at the point x. (These local functions  may be defined  in any manner whatso­
`ever.)  "Relational  functions,"  denoted  by q
`kj  (x, y), measure  how well the posi­
`tion of the match of the /cth part at  (x) agrees with the position of the match of the 
`y'thpartat  (y). 
`The  basic notions  are shown  by a technique  simplified  from  [Chien and Fu 
`1974]  to  find  the  boundaries  of  lungs  in  chest  films.  The  lung  boundaries  are 
`modeled  with  a  polygonal  approximation  defined  by  the  five  key  points.  These 
`points are  the top of  the  lung,  the  two clavicle­lung junctions, and  the two lower 
`corners. To locate these points, local functions  g(x
`k)  are defined  which should be 
`maximized  when  the  corresponding  point  x
`k  is correctly  determined.  Similarly, 
`q (x k,  Xj) is a function  relating points x
`k  and x y. In their case, Chien and Fu used 
`the following  functions: 
`
`Ch.  4  Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 158
`
`

`

`T(\)  =  template centered at x computed as 
`an aggregate of a set of chest radiographs 
`—  T(\­ 
`x k)f(x) 
`g(*k> = L  
`VfV[T\ 
`
`x 
`
`I  ■ * I  1/  I 
`
`and 
`
`9(xk,  Xj) = expected angular orientation of x
`Kxk,  x,)­arctan 
`q (x k  Xj)  = 
`
`k  from  x 
`
`Xj 
`Xk 
`With this formulation  no further  modifications  are necessary and the solution may 
`be obtained by solving Eqs. (4.19) through  (4.21), as before. For purposes of com­
`parison,  this  method  was formalized  using  a lower­resolution  objective  function. 
`Figure  4.17  shows  Chien  and  Fu's  results  using  this  method  with  five  template 
`functions. 
`
`4.5.4  Theoretical Questions about Dynamic  Programming 
`
`The Interaction Graph 
`This graph describes the interdependence  of variables in the objective  func­
`tion. In the examples the interaction graph was simple: Each variable depended on 
`only  two others, resulting  in the graph  of Fig. 4.18a.  A more complicated  case is 
`the one in 4.18b, which describes an objective function  of the following  form: 
`
` Gc 3  x 4,  x 5,  x e) 
`h ()  =  h\ (x\,  x
`2)  + h 2 (x 2,  Xi, x 4)  +  h­t,
`For these cases the dynamic programming technique still applies, but the computa­
`tional  effort  increases  exponentially  with  the  number  of  interdependencies.  For 
`example, to eliminate x 2  in h 2, all possible combinations of x
`3 and x 4 must be con­
`sidered. To eliminate  X3   in  A3,  all possible combinations of x
`4,  x 5,  and xe, and so 
`forth. 
`
`Dynamic Programming versus Heuristic Search 
`It has been shown  [Martelli  1976] that for finding a path in a graph  between 
`two points, which is an abstraction  of the work we are doing here, heuristic search 
`methods can be more efficient  than dynamic programming methods. However, the 
`point  to remember  about  dynamic programming  is that  it efficiently  builds paths 
`from  multiple starting points. If this is required  by a particular  task, then dynamic 
`programming  would  be  the  method  of  choice,  unless  a  very  powerful  heuristic 
`were available. 
`
`4.6  CONTOUR  FOLLOWING 
`
`If nothing is known about the boundary shape, but regions have been found in the 
`image,  the  boundary  is recovered  by  one  of  the  simplest  edge­following  opera­
`tions: "blob finding" in images.  The ideas are easiest to present for binary images: 
`
`Sec.  4.6  Contour  Following 
`
`143 
`
`IPR2021-00921
`Apple EX1015 Page 159
`
`

`

`(a) 
`
`(b) 
`
`Fig.  4.17   Results  of  using local templates and  global  relations,
`
`  (a)  Model,   (b)  Results. 
`
`Given a  binary image,  the  goal  is  find  the  boundaries  of  all  distinct regions  in the 
`image. 
`This  can be  done  simply   by a  procedure  that  functions  like  Papert's  turtle 
`[Papert 1973;  Duda and Hart 1973]: 
`1.  Scan the image until a region pixel is encountered. 
`2. 
`If it is a region pixel, turn left and
` step;  else, turn right and step. 
`3.  Terminate upon return to the starting pixel. 
`Figure 4.19 shows  the  path  traced  out by the  procedure. This procedure  requires 
`the  region   to be  four­connected   for  a  consistent  boundary.  Parts   of an   eight­
` is  necessary to generate 
`connected  region can be missed. Also, some bookkeeping
`an exact sequence of boundary pixels without duplications. 
`A slightly  more  elaborate  algorithm   due to   [Rosenfeld  1968]  generates  the 
`boundary  pixels  exactly.   It   works   by  first finding  a  four­connected  background 
` is the  first pixel  en­
`pixel from   a  known boundary pixel.  The next boundary pixel
`countered  when   the  eight  neighbors   are  examined   in a  counter  clockwise  order 
`  to be  introduced  into  algorithms 
`from  the  background  pixel.  Many  details  have
`that  follow  contours   of  irregular  eight­connected  figures.
`  A  good  exposition  of 
`these is  given in [Rosenfeld and Kak 1976]. 
`
`4.6.1  Extension to Gray­Level  Images 
`
`  is to  start with  a  point  that  is  believed  to 
`The main idea behind contour  following
`be on the  boundary   and to  keep extending  the  boundary  by  adding points  in  the 
`contour directions. The details of these operations vary from  task
` to  task. The gen­
`
`144 
`
`Ch. 4   Boundary  Detection 
`
`IPR2021-00921
`Apple EX1015 Page 160
`
`

`

`*6 
`
`*5 
`
`Fig.  4.18 
`
`Interaction graphs for DP (see text). 
`
`eralization of the contour follower  to gray­level images uses local gradients with a 
`magnitude  s (x)  and  direction   </> (x)  associated  with each  point x. 0  points in  the 
` x  is on the boundary of an image object,  neigh­
`direction of maximum  change.  If
`boring  points on  the  boundary  should  be in  the general  direction  of  the  contour 
`directions,  <f>(x)   ±   ir/2,  as  shown  by  Fig.  4.20.  A  representative  procedure  is 
`adapted from  [Martelli 1976]: 
`
`1.  Assume that an edge has been detected  up to a point x,.  Move to the point x
`adjacent  to  x,  in  the direction  perpendicular  to the gradient  of x,.  Apply  the 
`gradient operator to x/,  if its magnitude is greater than  (some)  threshold,  this 
`point is added to the edge. 
`2.  Otherwise, compute  the average gray level of the 3 x  3 array centered  on Xj, 
`compare it with a suitably  chosen  threshold,  and determine  whether  Xj is in­
`side or outside the object. 
`k  adjacent to x, in the direction perpendic­
`3.  Make another attempt with a point x
`ular to the gradient at x, plus or minus (7r/4), according to the outcome of the 
`previous test. 
`
`y 
`
`JUi 
`
`Sec.  4.6  Contour  Following 
`
`145 
`
`Fig.  4.19  Finding the boundary in
`binary image. 
`
` a 
`
`IPR2021-00921
`Apple EX1015 Page 161
`
`

`

`1 
`lllw 
`
`Local edge 
`
`Search 
`space 
`
`Fig.  4.20  Angular orientations  for 
`contour  following. 
`
`^ 
`
`ll 
`
`4.6.2  Generalization to Higher­Dimensional  Image Data 
`
`The  generalization  of  contour  following  to  higher­dimensional  spaces  is  straight­
`forward