Fig.  3.1 1  Edg e model s fo r orientatio n 
`and displacemen t sensitivit y analyses . 
`
`ifO  <   d>   <   tan" 1 
`
`if ta n ­
`
`l 
`
`<  0   <   <f>   <   TT/ 4 
`
`(3.25 ) 
`
`<f> 
`
`*
`
`'
`
`­ ■  
`
`tan"1 
`
`7tan2</>  +   6tan</ > ­   1 ­9tan 2</>  +   22tan 0  ­   1 
`
`Arguments fro m  symmetr y sho w tha t onl y th e 0   <   <f>   <   IT  I '4 case s nee d b e exam ­
`ined. Simila r studie s coul d b e mad e usin g ram p edg e models . 
`A  rathe r  specialize d  kin d  o f  gradien t  i s  tha t  take n  "betwee n  pixels. "  Thi s 
`scheme i s show n i n Fig . 3.12 . Her e a  pixe l ma y b e though t o f a s havin g fou r crack 
`edges surroundin g  it , whos e direction s  o f ar e fixed  b y th e pixe l t o b e multiple s o f 
`7r/2. Th e magnitud e o f th e edg e i s determine d b y |/(x )  ­   /(y )  | , wher e x  an d y  ar e 
`the coordinate s o f th e pixel s tha t hav e th e edg e i n common . On e advantag e o f thi s 
`formulation  i s  tha t  i t  provide s  a n  effectiv e  wa y  o f  separatin g  region s  an d  thei r 
`boundaries. Th e disadvantag e i s tha t th e edg e orientatio n i s crude . 
`The  Laplacian  i s a n edg e  detectio n  operato r  tha t  i s a n approximatio n  t o  th e 
`mathematical Laplacia n d 2f/dx2  +  d 2f/dy2 
`i n th e sam e wa y tha t th e gradien t i s a n 
`approximation t o th e first  partia l derivatives . On e versio n o f th e discret e Laplacia n 
`is give n b y 
`
`x 
`
`y 
`1 _ 
`
`'Crack" edg e 
`
`Fig .  3.1 2  "Crack " edg e representation . 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 96
`
`

`

`(3.26 ) 
`
`L U   y)   =  fix,   y)   ­   V4fix,   y   +   1 )  +   fix,   y   ­   1 ) 
`+ fix   +   \,y)   +  fix­  
`\,y)] 
`The Laplacia n ha s tw o disadvantage s a s a n edg e measure : (1 ) usefu l  directiona l in ­
`formation  i s no t  available ,  an d  (2 )  th e Laplacian ,  bein g a n approximatio n  t o  th e 
`second derivative , doubl y enhance s an y nois e i n th e image . Becaus e o f thes e disad ­
`vantages, th e Laplacia n ha s falle n  int o disuse , althoug h som e author s hav e use d i t 
`as a n adjunc t  t o th e gradien t  [Wechsle r an d Sklansk y  1977 ; Akatsuk a  1974 ] i n th e 
`following manner : Ther e i s a n edg e a t x  wit h magnitud e g  (x ) an d directio n <f>  (x ) i f 
`gix)  >   r , a n d L ( x )  >   T 2. 
`Edge Templates 
`The Kirsch  operator  [Kirsc h  1971 ] i s relate d t o th e edg e gradien t an d i s give n 
`
`by 
`
`k +  l 
`Six)  =  ma x [1 ,  max£/(xfc) ] 
`k­l 
`ar e th e eigh t  neighborin g pixel s t o  x  an d wher e subscript s  ar e com ­
`where fi\ k) 
`puted  modul o  8 . A  3­bi
`t directio n  ca n als o  b e extracte d  fro m  th e valu e o f  k  tha t 
`yields th e maximu m i n (3.27) . I n practice , "pure " templat e matchin g ha s replace d 
`the  us e  o f  (3.27) .  Fou r  separat e  template s  ar e  matche d  wit h  th e  imag e  an d  th e 
`operator report s th e magnitud e an d directio n associate d wit h th e maximu m match . 
`As on e migh t expect , th e operato r i s sensitiv e t o th e magnitud e o f fix),  
`s o tha t i n 
`practice  variant s  usin g  larg e  template s  ar e  generall y  used .  Figur e  3.1 3  show s 
`
`(3.27) 
`
`1  ­ 1 
`
`1  1  0 
`1  0  ­ 1 
`0  ­ 1  ­ 1 
`
`1 1 1 1 0 
`1 
`1 1 
`1 0 ­
`1 
`1  1  
`0 ­ 1 ­
`1  0   ­ 1 ­
`1  ­ 1 
`0  ­ 1  ­ 1  ­ 1  ­ 1 
`
`Kirsch­motivate d template s wit h differen t  spans . ­ 1  1 
`
`1 ­ 1 
`
`n  =   1  ­ 1  0 
`1 ­ 1  0 
`1 ­ 1  0  1 
`
`1  1   1 
`
`0 
`
`1   1 
`
`0  0   0  ­ 1  0   1 ­ 1  ­ 1  ­ 1  ­ 1  ­ 1  o 
`
`n =  2  ­ 1  0   1 ­ 1  0   1 ­ 1  0   1 ­ 1  0   1 ­ 1  0   1 
`
`Sec. 3.3   Finding   Local  Edges 
`
`1 1 1 1 1 
`
`1 1 1 1 1 
`0 
`
`0   0   0   0 ­ 1  ­ 1  ­ 1  ­ 1  ­ 1 ­ 1  ­ 1 ­
`
`1  ­ 1  ­ 1 
`
`0 
`
`1 1 1
`
`1 ­ 1 0 
`1 1 1 ­ 1 ­ 1 0 
`1   1 ­ 1  ­ 1 ­ 1
`1 ­ 1  ­ 1  ­ 1  ­ 1  0 
`
`0 
`
`Fig.  3.1 3  Kirsc h templates . 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 97
`
`

`

`This  brie f  discussio n  o f edg e  template s  shoul d  no t  b e  construe d  a s a  com ­
`ment  o n thei r appropriatenes s o r popularity .  I n fact ,  the y ar e widel y used , an d th e 
`template­matchin g  concep t  i s th e  essenc e  o f  th e  othe r  approaches . Ther e  i s als o 
`evidence  tha t  th e  mammalia n  visua l  syste m  respond s  t o  edge s  throug h  specia l 
`low­leve l template­matchin g edg e detector s [Hube l an d Wiese l 1979] . 
`
`3.3.2  Edg e Thresholdin g  Strategie s 
`
`For mos t image s ther e wil l b e bu t fe w place s wher e th e gradien t magnitud e i s equa l 
`to zero . Furthermore ,  i n th e absenc e o f an y specia l context , smal l magnitude s ar e 
`most  likel y  t o  b e  du e  t o  rando m  fluctuations ,  o r  nois e  i n  th e  imag e  functio n  / . 
`Thus i n practica l case s on e  ma y us e th e expedien t  o f onl y reportin g  a n  edg e ele ­
`ment  a t x   i f g  (x )  i s greater   tha n  som e  threshold ,  i n orde r  t o reduc e  thes e nois e 
`effects. 
`This strateg y  i s computationall y  efficien t  bu t  ma y no t  b e th e best . A n  alter ­
`native  thresholdin g  strateg y  [Fre i  an d  Che n  1977 ]  view s differenc e  operator s  a s 
`part  o f a  se t  o f orthogona l  basi s function s  analogou s  t o  th e  Fourie r  basi s o f Sec ­
`tion  2.2.4 .  Figur e  3.1 4  show s  th e  nin e  Frei­Che n  basi s  functions .  Usin g  thi s 
`basis, th e imag e nea r a  poin t x 0 ca n b e represente d a s 
`
`fix)  ­   £   (f,   h k)hk(x  ­   x 0)/(hk,  h k) 
`* ­
`i 
`where th e (/ ,  h k)  i s th e correlatio n operatio n give n b y 
`
`(3.28 ) 
`
`(/,A*)  =   Z / ( x o ) M x ­ x o ) 
`D 
`and D  i s th e nonzer o domai n o f th e basi s functions . Thi s operatio n i s als o regarde d 
`as th e projection   o f th e  imag e int o  th e  basi s functio n  h k.  Whe n  th e  imag e ca n  b e 
`reconstructed  fro m  th e  basi s function s  an d  thei r  coefficients ,  th e  basi s  function s 
`span th e space . I n th e cas e o f a  smalle r se t o f functions ,  th e basi s function s spa n a 
`subspace. 
`The valu e o f a  projectio n  int o an y basi s functio n  i s highes t whe n  th e  imag e 
`function  i s identica l t o th e basi s function .  Thu s on e wa y o f measurin g  th e  "edge ­
`ness" o f a  loca l are a i n a n imag e i s t o measur e th e relativ e projectio n  o f th e imag e 
`
`(3.29 ) 
`
`1 ­ 1 
`1 ­ 1 
`
`1 ­ 1 
`1 ­ 1 
`
`1 
`
`1 
`
`1 
`
`1 
`
`1 
`
`1 
`
`1 
`
`1 
`
`1  4 
`
`1  ­ 2  1  ­ 2 
`1 
`V2 
`1 ­ 2  1  ­ 2 
`
`V2  ­ 1 ­ 1 
`1 V2 ­ 1 
`V2 ­ 1 
`
`1 
`
`1 
`
`Fig.  3.1 4  Frei­Che n orthogona l basis . 
`
`80 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 98
`
`

`

`into th e edg e basi s functions . Th e relativ e projectio n int o th e particula r "edg e sub ­
`space" i s give n b y 
`
`where 
`
`and 
`
`B.u 
`cos 0  =   (— ) 
`S 
`
`« ­ ! «  h k)2 
`k=\ 
`
`s ­   Z  if,  h) 2 
`
`(3.30) 
`
`k=0 
`Thus i f 9   <   T,  repor t a n edge ; otherwise , not . Figur e 3.1 5 show s th e potentia l ad ­
`vantage o f thi s techniqu e compare d  t o th e techniqu e o f thresholdin g  th e gradien t 
`magnitude,  usin g tw o hypothetica l  projection s  B\   an d  B 2­  Eve n  thoug h  B 2  ha s a 
`small magnitude , it s relativ e projectio n  int o edg e subspac e i s larg e an d thu s woul d 
`be counte d a s a n edg e wit h th e Frei­Che n criterion . Thi s i s no t tru e fo r  B\. 
`Under  man y circumstance s i t i s appropriat e t o us e mode l informatio n  abou t 
`the imag e edges . Thi s informatio n  ca n affec t  th e wa y th e edge s ar e interprete d  afte r 
`they hav e bee n compute d o r i t ma y affec t  th e computatio n proces s itself . A s a n ex ­
`ample o f th e first  case , on e ma y stil l us e a  gradien t operator , bu t var y th e threshol d 
`for reportin g a n edge . Man y version s o f th e second , mor e extrem e strategie s o f us ­
`ing specia l spatiall y varian t detectio n method s hav e bee n trie d  [Pingl e an d Tenen ­
`baum  1971 ; Griffit h  1973 ; Shira i  1975] . Th e  basi c ide a i s illustrate d  i n Fig . 3.16 . 
`Knowledge  o f  th e  orientatio n  o f  a n  edg e  allow s  a   specia l  orientation­sensitiv e 
`operator t o b e brough t t o bea r o n it . 
`
`3.3.3  Three­Dimensiona l  Edg e Operator s 
`
`In  man y  imagin g  applications ,  particularl y  medicine ,  th e  image s  ar e  three ­
`dimensional. Conside r th e example s o f th e reconstructe d  plane s describe d i n Sec ­
`tions  1. 1  an d  2.3.4 . Th e  medica l  scanne r  tha t  acquire s thes e  dat a  follow s  severa l 
`parallel imag e planes , effectivel y  producin g a  three­dimensiona l volum e o f data . 
`
`Edg e 
`subspace 
`"gW 
`
`T, 
`
`(a) 
`
`(b) 
`
`Fig.  3.1 5  Compariso n o f thresholdin g 
`techniques . 
`
`3.3  Finding   Local  Edges 
`
`81 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 99
`
`

`

`/ 
`
`z 
`/  
`
`/ 
`
`/  
`
`/   /  
`/ 
`. 7? /
`/
`/ 
`/ 
`/ 
`
`/  
`/
`
`/■  
`
`/ 
`
`Fig.  3.1 6  Model­directe d edg e 
`detection. 
`
`In three­dimensiona l data , boundarie s o f object s ar e surfaces . Edg e element s 
`in  tw o  dimension s  becom e  surfac e  element s  i n  thre e  dimensions .  Th e  two ­
`dimensional  imag e  gradient ,  whe n  generalize d  t o  thre e  dimensions ,  i s th e  loca l 
`surface normal . Jus t a s i n th e two­dimensiona l case , man y differen t  basi s operator s 
`can  b e use d  [Li u  1977 ; Zucke r an d  Humme l  1979] . Tha t o f Zucke r an d  Humme l 
`uses  a n  optima l  basi s  assumin g  a n  underlyin g  continuou s  model .  W e  shal l jus t 
`describe th e operato r here ; th e proo f o f it s correctnes s give n th e continuou s imag e 
`model  ma y  b e  foun d  i n  th e  reference .  Th e  basi s  function s  fo r  th e  three ­
`dimensional operato r ar e give n b y 
`
`g\bc,y,  z)   =  — 
`r 
`
`g2(x,  y,z)   =  2­
`
`g3(x,y,  z)   =   ­
`
`(3.31) 
`
`where r   =   (x 2  +   y 2  +  z 2)y\  Th e discret e for m  o f thes e operator s i s show n i n Fig . 
`3.17 fo r a  3  x   3  x   3  pixe l domai n D . Onl y g i i s show n sinc e th e other s ar e obviou s 
`by symmetry . T o appl y th e operato r a t a  poin t x 0, ,yo,  ?o  comput e projection s a,   b, 
`and c , wher e 
`a  =   (g\,  f)   =   L £ i ( x ) / ( x ­ x 0 ) 
`D 
`
`b  =   (gi,   f) 
`
`(3.32) 
`
`C ­   (ft .  / ) 
`The resul t o f thes e computation s i s th e surfac e norma l n   =   (a,  b,  c)  a t Gco , ^o , zn) ­
`Surface  thresholdin g  i s analogou s t o edg e thresholding : Repor t  a  surfac e  elemen t 
`
`82 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 100
`
`

`

`• *­  y 
`
`v/3 
`3 
`
`V ^ 
`2 
`
`2  ­ 1 
`
`N / 3 
`3 
`
`2 
`
`3 
`
`2 
`
`V ^ 
`3 
`
`0 
`
`0 
`
`0 
`
`0 
`
`0 
`
`0 
`
`0 
`
`0 
`
`0 
`
`3 
`
`2 
`
`v/3 
`3 
`
`v / 2 
`2 
`
`1 
`
`2 
`
`3 
`
`2 
`v/3 
`3 
`
`Fig.  3.1 7  Th e 3  x  3  x  3  edg e basi s 
`functiong\(x,  y,   z). 
`
`only  i f six,   y,   z)   =  \n  |  exceed s  som e  threshold .  Figur e  3.1 8  show s th e result s o f 
`applying  th e  operato r  t o  a   syntheti c  three­dimensiona l  imag e  o f  a   torus .  Th e 
`display show s smal l detecte d surfac e patches . 
`
`3.3.4  Ho w Goo d ar e Edg e Operators ? 
`
`The plethor a o f edg e operator s i s ver y difficul t  t o compar e an d evaluate . Fo r exam ­
`ple, som e operator s ma y fin d mos t edge s bu t als o respon d  t o noise ; other s ma y b e 
`
`X 
`
`Fig.  3.1 8  Result s o f applyin g th e Zucker­Humme l  3­ D operato r t o syntheti c im ­
`age dat a i n th e shap e o f a  torus . 
`
`3  Finding   Local  Edges 
`
`83 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 101
`
`

`

`noise­insensitiv e  bu t mis s som e crucia l edges . Th e followin g figure  o f meri t  [Prat t 
`1978] ma y b e use d t o compar e edg e operators : 
`
`max (N A,  TV/) ~ t  1  +   {ad?) 
`
`where  N A  an d  Nj   represen t  th e  numbe r  o f  actua l  an d  idea l  edg e  points , respec ­
`tively,  a  i s a  scalin g constant ,  an d  d  i s th e signe d  separatio n  distanc e o f a n actua l 
`edge poin t  norma l  t o a  lin e o f idea l edg e points . Th e ter m  ad}  penalize s detecte d 
`edges whic h ar e offse t  fro m  thei r  tru e position ;  th e penalt y ca n b e adjuste d  vi a a. 
`Using  thi s measure , al l operator s  hav e surprisingl y  simila r  behaviors .  Unsurpris ­
`ingly, th e performanc e  o f eac h deteriorate s i n th e presence  o f nois e [Abdo u 1978] . 
`(Pratt  define s  a  signal­to­nois
`e  rati o a s th e squar e  o f th e ste p edg e amplitud e di ­
`vided b y th e standar d deviatio n o f Gaussia n whit e noise. )  Figur e 3.1 9 show s som e 
`typical curve s fo r differen t  operators . T o mak e thi s figure,  th e threshol d fo r report ­
`ing  a n  edg e  wa s  chose n  independentl y  fo r  eac h  operato r  s o  a s  t o  maximiz e  Eq . 
`(3.33). 
`These  comparison s  ar e  importan t  a s  the y  provid e  a   gros s  measur e  o f 
`differences  i n  performanc e  o f  operator s  eve n  thoug h  eac h  operato r  embodie s a 
`specific  edg e  mode l  an d  ma y  b e  bes t  i n  specia l  circumstances .  Bu t  perhap s  th e 
`more importan t  poin t  i s tha t sinc e al l real­worl d  image s hav e significan t  amount s 
`of noise ,  al l edg e  operator s  wil l generall y  produc e  imperfec t  results . Thi s  means 
`that i n considerin g  th e overal l compute r  visio n problem ,  tha t o f buildin g descrip ­
`tions o f objects ,  th e effort s  ar e usuall y bes t spen t  i n developin g method s tha t ca n 
`use o r improv e th e measurement s fro m  unreliabl e edge s rathe r tha n i n a  searc h fo r 
`the idea l edg e detector . 
`
`o 
`
`1.0 
`
`1  
`2. 0 
`
`1  
`5. 0 
`
`1  
`1 0 
`
`1  
`2 0 
`
`1  
`5 0 
`
`1_» . 
`10 0 
`
`h2/a2 
`
`Fig.  3.1 9  Edg e operato r  performanc e  usin g Pratt' s  measur e  (Eq .  3.33) . 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 102
`
`

`

`3.3.5  Edg e Relaxatio n 
`
`One wa y t o improv e edg e operato r measurement s i s t o adjus t  the m base d o n meas ­
`urements o f neighborin g edges . Thi s i s a  natura l thin g t o wan t t o do : I f a  wea k hor ­
`izontal edg e i s positione d betwee n tw o stron g horizonta l edges , i t shoul d gai n cred ­
`ibility.  Th e  edge s  ca n  b e  adjuste d  base d  o n  loca l  informatio n  usin g  parallel ­
`iterative  techniques .  Thi s sor t  o f proces s i s relate d  t o  mor e globa l analysi s an d i s 
`complementary t o sequentia l approache s suc h a s edg e trackin g  (Chapte r 4) . 
`Early  cooperativ e  edg e  detectio n  technique s  use d  pairwis e  measurement s 
`between pixel s  [Zucke r e t al . 1977] . A  late r versio n  [Prage r  1980 ] allow s fo r  mor e 
`complicated  adjustmen t  formulas .  I n  describin g  th e  edg e  relaxatio n  scheme , w e 
`essentially  follo w  Prager' s  developmen t  an d  us e  th e crac k  edge s describe d  a t  th e 
`end o f th e discussio n o n gradient s  (Sec . 3.31) . Th e developmen t  ca n b e extende d 
`to th e othe r kind s o f edge s an d th e reade r i s invite d t o d o jus t thi s i n th e Exercises . 
`The  overal l  strateg y  i s  t o  recogniz e  loca l  edg e  pattern s  whic h  caus e  th e 
`confidence  i n a n edg e t o b e modified .  Prage r recognize s  thre e group s o f patterns : 
`patterns wher e th e confidenc e  o f a n edg e ca n  b e increased ,  decreased ,  o r lef t  th e 
`same. Th e overal l structur e o f th e algorith m i s a s follows : 
`
`Algorithm 3. 1  Edg e Relaxatio n 
`
`0.  Comput e th e initia l confidenc e  o f eac h edg e C°(e)   a s th e normalize d gradien t 
`magnitude normalize d b y th e maximu m gradien t magnitud e i n th e image . 
`1. 
`k=\; 
`2.  Comput e eac h edg e typ e base d o n th e confidenc e  o f edg e neighbors ; 
`3.  Modif y  th e confidenc e  o f eac h edg e  C k(e)  base d  o n it s edg e typ e an d it s pre ­
`vious confidenc e  C k~l(e); 
`4.  Tes t  th e  C k{eYs  t o se e i f the y hav e al l converge d  t o eithe r 0  o r  1 . I f so , stop ; 
`else, incremen t /can d g o t o 2 . 
`
`The tw o importan t part s o f th e algorith m ar e ste p 2 , computin g th e edg e type , an d 
`step 3 , modifyin g th e edg e confidence . 
`The edge­typ e classificatio n  relie s o n th e notation   fo r edge s  (Fig . 3.20) . Th e 
`edge  typ e  i s  a  concatenatio n  o f  th e  lef t  an d  righ t  verte x  types .  Verte x  type s  ar e 
`computed  fro m  th e strengt h  o f edge s emanatin g fro m  a  vertex . Vertica l edge s ar e 
`handled  i n  th e sam e way , exploitin g  th e  obviou s symmetrie s  wit h  th e  horizonta l 
`case. Beside s th e centra l edg e e,  th e lef t verte x i s th e en d poin t fo r thre e othe r pos ­
`sible edges . Classifyin g  thes e possibl e edge s int o "edge " an d "no­edge "  provide s 
`the underpinning s fo r th e verte x type s i n Fig . 3.21 . 
`
`Sec.  3.3   Finding   Local   Edges 
`
`85 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 103
`
`

`

`(a) 
`
`(c) 
`
`mm 
`
`(b) 
`
`(d) 
`
`(e) 
`
`Fig.  3.2 0  Edg e notation ,  (a )  Edg e 
`position  wit h  n o edge ,  (b )  Edg e  positio n 
`with edge ,  (c )  Edg e t o b e  updated ,  (d ) 
`Edge o f unknow n  strength ,  (e ) 
`Configuration  o f edge s aroun d  a  centra l 
`edge e . 
`
`To  comput e  verte x  type ,  choos e  th e  maximu m  confidenc e  vertex ,  i.e. ,  th e 
`vertex i s typ e j  wher e j  maximize s con f (/ ) 
`
`and 
`
`(m ­  a)(m­   b)  (m  ­  c) 
`aim ­  b)(m­   c) 
`ab im  ­  c) 
`abc 
`
`conf(0) 
`conf(l) 
`conf(2) 
`conf (3 ) 
`where 
`m =  ma x (a,  b,  c,  q) 
`q i s a  constan t  (0. 1 i s abou t right ) 
`and  a,   b,   an d  c  ar e  th e  normalize d  gradien t  magnitude s  fo r  th e  thre e  edges . 
`Without  los s  o f  generality ,  a   ^   b   ^   c.   Th e  paramete r  m   adjust s  th e  verte x 
`classification  s o tha t  i t  i s relativ e  t o  th e  loca l  maximum .  Thu s  {a,  b,  c)   =   (0.25 , 
`0.01,  0.01 )  i s a  typ e  1  vertex . Th e  paramete r  q  force s  wea k  vertice s t o  typ e zer o 
`[e.g.,  (0.01 , 0.001 , 0.001 )  i s typ e zero] . 
`Once th e verte x typ e ha s bee n computed , th e edg e typ e i s simple . I t i s merel y 
`the concatenatio n o f th e tw o verte x types .  Tha t is , th e edg e typ e i s ((/) , wher e /an d 
`y'are th e verte x types . (Fro m symmetry , onl y conside r /   ^j.) 
`
`(a) 
`
`(b) 
`
`(c)  mm  
`
`1 
`
`1 
`
`i  
`
`i 
`
`(d)  EM3  1 
`
`mm 
`
`I 
`1 
`
`I 
`
`mm  cz ] 
`
`Fig.  3.2 1  Classificatio n  o f verte x  typ e 
`of left­han d  endpoin t  o f edg e e ,  Fig . 3.20 . 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 104
`
`

`

`Decisions  i n  th e  secon d  ste p  o f  modifyin g  edg e  confidenc e  base d  o n  edg e 
`type appea r i n Tabl e 3.1 . Th e updatin g formul a is : 
`C k+l(e)  =  mi n (1 ,  C k(e)  +  8 ) 
`increment: 
`C k+l(e)  =   ma x (0 ,  C k(e)  ­   8 ) 
`decrement: 
`C k+l(e)  =   C k(e) 
`leave a s is : 
`where 8  i s a  constan t  (value s fro m  0. 1 t o 0. 3 ar e appropriate) . Th e resul t o f usin g 
`the relaxatio n schem e i s show n i n Fig . 3.22 . Th e figures  o n th e left­han d  sid e sho w 
`
`Fig.  3.2 2  Edg e relaxatio n results , (a ) Ra w edg e data .  Edg e strength s hav e bee n threshold ­
`ed a t 0.2 5 fo r displa y purpose s only ,  (b )  Result s afte r  fiv e iteration s o f relaxatio n applie d t o 
`(a),  (c )  Differen t  versio n o f  (a) .  Edg e strength s  hav e bee n  thresholde d  a t 0.2 5 fo r displa y 
`purposes only , (d ) Result s afte r five  iteration s o f relaxatio n applie d t o (c) . 
`
`Sec.  3.3   Finding   Local  Edges 
`
`87 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 105
`
`

`

`the edge s wit h normalize d magnitude s greate r tha n 0.25 . Wea k edge s caus e man y 
`gaps i n th e boundaries . Th e figures  o n th e righ t sid e sho w th e result s o f five  itera ­
`tions o f edg e relaxation . Her e th e confidenc e o f th e wea k edge s ha s bee n increase d 
`owing t o th e proximit y o f othe r edges , usin g th e rule s i n Tabl e 3.1 . 
`
`Table 3. 1 
`
`Decrement  Increment   Leave  as  is 
`
`0­0  
`0­2  
`0­3  
`
`1­1  
`1­2  
`1­3  
`
`0­1 
`2­2 
`2­3 
`3­3 
`
`3.4  RANG E INFORMATIO N  FRO M  GEOMETR Y 
`
`Neither th e perspectiv e o r orthogona l projectio n  operations , whic h tak e th e three ­
`dimensional  worl d  t o  a   two­dimensiona l  image ,  i s invertibl e  i n  th e  usua l  sense . 
`Since projectio n map s a n infinit e lin e ont o a  poin t i n th e image , informatio n  i s lost . 
`For a  fixed  viewpoin t an d direction , infinitel y  man y continuou s an d discontinuou s 
`three­dimensiona l configuration s  o f point s coul d projec t o n ou r retin a i n a n imag e 
`of,  say , ou r grandmother .  Simpl e case s ar e grandmother s o f variou s size s cleverl y 
`placed  a t  varyin g  distance s  s o  a s  t o  projec t  ont o  th e  sam e  area .  A n  astronome r 
`might  imagin e million s o f point s distribute d  perhap s  throug h  light­year s o f spac e 
`which  happe n  t o  lin e  u p  int o  a   "grandmothe r  constellation. "  Al l  tha t  ca n  b e 
`mathematically  guarantee d  b y  imagin g  geometr y  i s  tha t  th e  imag e  poin t 
`corresponds t o on e o f th e infinit e numbe r o f point s o n tha t three­dimensiona l  lin e 
`of  sight .  Th e  "invers e  perspective "  transformatio n  (Appendi x  1 )  simpl y  deter ­
`mines th e equatio n o f th e infinit e  lin e o f sigh t fro m  th e parameter s o f th e imagin g 
`process modele d a s a  poin t projection . 
`However, a  lin e an d a  plan e no t includin g i t intersec t i n jus t on e point . Line s 
`of sigh t ar e eas y t o compute , an d s o i t i s possibl e t o tel l wher e an y imag e poin t pro ­
`jects  o n t o an y know n  plan e  (th e supportin g  groun d  o r tabl e plan e i s a  favorite) . 
`Similarly,  i f  tw o  image s  fro m  differen t  viewpoint s  ca n  b e  place d  i n  correspon ­
`dence, th e intersectio n o f th e line s o f sigh t fro m  tw o matchin g imag e point s deter ­
`mines  a   poin t  i n  three­space .  Thes e  simpl e  observation s  ar e  th e  basi s  o f  light ­
`striping rangin g (Sectio n 2.3.3 ) an d ar e importan t i n stere o imaging . 
`
`3.4.1.  Stere o Visio n an d Triangulatio n 
`
`One o f th e first  idea s tha t occur s t o on e wh o want s t o d o three­dimensiona l sensin g 
`is  th e  biologicall y  motivate d  on e  o f  stere o  vision .  Tw o  cameras ,  o r  on e  camer a 
`from  tw o positions , ca n giv e relativ e dept h o r absolut e three­dimensiona l  location , 
`depending o n th e elaboratio n o f th e processin g an d measurement .  Ther e ha s bee n 
`
`88 
`
`C/i.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 106
`
`

`

`considerable effor t  i n thi s directio n  [Morave c 1977 ; Qua m an d Hanna h  1974 ; Bin ­
`ford  1971 ; Turne r  1974 ; Shapir a 1974] . Th e techniqu e i s conceptuall y simple : 
`1.  Tak e tw o image s separate d b y a  baseline . 
`2. 
`Identif y  point s betwee n th e tw o images . 
`3.  Us e  th e  invers e  perspectiv e  transfor m  (Appendi x  1 )  o r  simpl e  tri ­
`angulation  (Sectio n  2.2.2 )  t o deriv e th e tw o line s o n whic h th e worl d 
`point lies . 
`Intersec t th e lines . 
`
`4. 
`
`The resultin g poin t i s i n three­dimensiona l worl d coordinates . 
`The hardes t  par t  o f thi s metho d  i s ste p 2 , tha t  o f identifyin g  correspondin g 
`points i n th e tw o images . On e wa y o f doin g thi s i s t o us e correlation ,  o r templat e 
`matching,  a s describe d  i n Sectio n  3.2.1 . Th e  ide a i s t o tak e a  patc h  o f on e imag e 
`and matc h i t agains t th e othe r image , finding  th e plac e o f bes t matc h i n th e secon d 
`image,  an d  assignin g  a  relate d  "disparity "  (th e  amoun t  th e  patc h  ha s  bee n  dis ­
`placed) t o th e patch . 
`Correlation  i s a  relativel y expensiv e operation ,  it s naiv e implementatio n  re ­
`quiring Q(n 2m2)  multiplication s an d addition s fo r a n  mxm   patc h an d  nxn   image . 
`This requiremen t ca n b e drasticall y improve d b y capitalizin g o n th e ide a o f variabl e 
`resolution; th e improve d techniqu e i s describe d i n Sectio n 3.7.2 . 
`Efficient  correlatio n  i s o f technologica l  concern ,  bu t eve n  i f i t wer e fre e  an d 
`instantaneous, i t woul d stil l b e inadequate .  Th e basi c problem s wit h correlatio n i n 
`stereo imagin g hav e t o d o wit h th e fac t  tha t  thing s ca n loo k significantl y  differen t 
`from  differen t  point s  o f  view .  I t  i s  possibl e  fo r  th e  tw o  stere o  view s  t o  b e 
`sufficiently  differen t  tha t  correspondin g  area s  ma y  no t  b e  matche d  correctly . 
`Worse, i n scene s wit h muc h obscuration , ver y importan t feature s o f th e scen e ma y 
`be presen t i n onl y on e view . Thi s proble m i s alleviate d b y decreasin g th e baseline , 
`but  o f  cours e  the n  th e  accurac y  o f  dept h  determination s  suffers ;  a t  a   baselin e 
`length o f zer o ther e i s n o problem , bu t n o stere o either . On e solutio n i s t o  identif y 
`world features , no t imag e appearance , i n th e tw o views , an d matc h thos e (th e nos e 
`of a  person ,  th e corne r  o f a  cube) . However ,  i f three­dimensiona l  informatio n  i s 
`sought a s a  hel p i n perception ,  i t i s unreasonabl e t o hav e t o d o perceptio n first  i n 
`order t o d o stereo . 
`
`3.4.2  A  Relaxatio n Algorith m fo r Stere o 
`
`Human  stereopsis,   o r fusin g  th e input s fro m  th e eye s int o a  stere o image , doe s no t 
`necessarily  involv e bein g awar e o f feature s  t o matc h  i n eithe r  view . Mos t  huma n 
`beings ca n fus e quit e efficientl y  stere o pair s whic h individuall y consis t o f randoml y 
`placed  dots , an d  thu s ca n perceiv e three­dimensiona l  shape s withou t  recognizin g 
`monocular clue s i n eithe r image . Fo r example , conside r th e stere o pai r o f Fig . 3.23 . 
`In  eithe r  fram e  b y itself ,  nothin g  bu t  a  randoml y  speckle d  rectangl e  ca n  b e  per ­
`ceived. Al l th e stere o informatio n  i s presen t i n th e relativ e displacemen t o f dot s i n 
`the tw o rectangles . T o mak e th e right­han d  membe r  o f th e stere o pair , a  patc h o f 
`
`Sec.  3.4   Range   Formation  
`
`from   Geometry 
`
`89 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 107
`
`

`

`Fig.  3.2 3  A  random­do t  stereogram . 
`
`the  randoml y  place d  dot s  o f  th e  left­han d  imag e  i s  displace d  sideways . Th e  dot s 
`which ar e thu s covere d ar e lost , an d th e spac e lef t b y displacin g th e patc h i s filled  i n 
`with rando m dots . 
`Interestingly enough , a  ver y simpl e algorith m  [Mar r an d Poggi o 1976 ] ca n b e 
`formulated  tha t  compute s  disparit y  fro m  rando m  do t  stereograms.  Firs t  conside r 
`the  simple r  proble m  o f  matchin g  one­dimensiona l  image s o f  fou r  point s  a s de ­
`picted  i n  Fig .  3.24 .  Althoug h  onl y  on e  dept h  plan e  allow s  al l fou r  point s  t o  b e 
`placed  i n  correspondence ,  lesse r  number s  o f  point s  ca n  b e  matche d  i n  othe r 
`planes. 
`The cru x o f th e algorith m i s th e rules , whic h hel p determine , o n a  loca l basis , 
`the appropriatenes s o f a  match . Tw o rule s aris e fro m  th e observatio n tha t mos t im ­
`ages ar e o f opaqu e object s wit h smoot h surface s  an d dept h  discontinuitie s onl y a t 
`object boundaries : 
`
`1.  Eac h poin t i n a n imag e ma y hav e onl y on e dept h value . 
`2.  A  poin t i s almos t sur e t o hav e a  dept h valu e nea r th e value s o f it s neighbors . 
`
`Fig.  3.2 4  Th e stere o matchin g problem . 
`
`90 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 108
`
`

`

`Figure  3.2 4 ca n b e viewe d  a s a  binar y  networ k  wher e  eac h  possibl e  matc h i s 
`represented  b y a  binar y state . Matche s hav e valu e 1   an d nonmatche s valu e 0 . Fig ­
`ure  3.2 5  show s a n expande d  versio n o f Fig . 3.24 . Th e connection s  o f alternativ e 
`matches fo r a  poin t inhibi t eac h othe r an d connection s  betwee n matche s o f equa l 
`depth reinforc e eac h other . T o exten d thi s ide a t o tw o dimensions , us e paralle l ar ­
`rays fo r differen t  value s o f y  wher e equa l dept h  matche s hav e reinforcin g  connec ­
`tions.  Thu s  th e extende d  arra y  i s modele d  a s th e matri x  C  (x,  y,  d)  wher e th e 
`point  x,  y,  d  correspond s  t o a  particula r  matc h  betwee n  a  poin t  (xi , y {) i n  th e 
`right  imag e an d a  poin t  (x 2, yi)  i n th e lef t  image . Th e  stereopsi s algorith m  pro ­
`duces  a  serie s o f matrice s  C„   whic h  converge s  t o th e correc t  solutio n  fo r  mos t 
`cases. Th e initia l matri x  CQ{X,  y,  d)  ha s value s o f on e wher e x,  y,  d  correspon d t o 
`a matc h i n th e origina l dat a an d ha s value s o f zer o o r otherwise . 
`
`Algorithm 3. 2 
`[Mar r an d Poggi o 1976 ] 
`Until C  satisfie s som e convergenc e criterion , d o 
`
`C w +,U y,d)  =  .   £   C„  (x' t y\  d')  ­   £   C„  ix',  y',d')   +  C 0(x,  y,  d) 
`x',y',d'ZS 
`x',y',d'€9 
`
`(3.34) 
`
`where th e ter m i n brace s i s handle d a s follows : 
`jl 
`i f t  >   T 
`'  ~   0   otherwis e 
`
`' 
`
`S  =  se t o f point s x',  y',  d'  suc h  tha t | x —   x'| < 1  an d d  =   d' 
`$ =  se t o f point s x',  y',  d'  suc h tha t | x —   x' | <   1  an d \d  —   d'\  =   1 
`
`Disparity 
`
`Match betwee n 
`x an d x' 
`
`/ 
`
`Inhibitory 
`connection 
`
`Excitatory 
`connection 
`
`Fig.  3.2 5  Extensio n o f stere o  matching . 
`
`Sec. 3.4   Range   Formation  
`
`from   Geometry 
`
`91 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 109
`
`

`

`One  convergenc e  criterio n  i s tha t  th e  numbe r  o f point s  modifie d  o n  a n  iteratio n 
`must b e les s tha n som e  threshol d  T.  Fig . 3.2 6 show s th e result s o f thi s computa ­
`tion; th e disparit y i s encode d a s a  gra y leve l an d displaye d a s a n imag e fo r  differen t 
`values o f n. 
`A  mor e  genera l  versio n  o f  thi s  algorith m  matche s  imag e  feature s  suc h  a s 
`edges  rathe r  tha n  point s  (i n  th e  random­do t  stereogram ,  th e  onl y  feature s  ar e 
`
`V&tt} 
`
`i K 1 
`
`jpi 
`
`Fig.  3.2 6  Th e result s o f relaxatio n computation s  fo r  stereo . 
`
`Ch.  3   Early   Processing 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 110
`
`

`

`points),  bu t  th e principle s ar e th e same . Th e extractio n  o f feature s  mor e compli ­
`cated  tha n  edge s o r point s i s itsel f  a  thorn y  proble m an d  th e subjec t  o f Par t II .  I t 
`should b e mentione d tha t Mar r an d Poggi o hav e refine d  thei r stereopsi s algorith m 
`to agre e bette r wit h psychologica l dat a [Mar r an d Poggi o 1977] . 
`
`3.5  SURFAC E ORIENTATIO N  FRO M REFLECTANC E MODEL S 
`
`The  ordinar y  visua l  worl d  i s  mostl y  compose d  o f  opaqu e  three­dimensiona l  ob ­
`jects. Th e intensit y  (gra y level ) o f a  pixe l i n a  digita l imag e i s produce d b y th e ligh t 
`reflected  b y a  smal l are a o f surfac e nea r th e correspondin g poin t o n th e object . 
`It i s easies t t o ge t consisten t shap e (orientation )  informatio n fro m a n imag e i f 
`the  lightin g  an d  surfac e  reflectanc e  d o  no t  chang e  fro m  on e  scen e  locatio n  t o 
`another. Analytically , i t i s possibl e t o trea t suc h lightin g a s unifor m illumination , a 
`point sourc e a t infinity ,  o r a n infinit e linea r source .  Practically , th e huma n shape ­
`from­shadin g  transfor m  i s  relativel y  robust .  O f  course ,  th e  perceptio n  o f  shap e 
`may  b e  manipulate d  b y changin g  th e  surfac e  shadin g  i n calculate d  ways . I n  part , 
`cosmetics wor k b y changin g th e reflectivit y  propertie s o f th e ski n an d misdirectin g 
`our huma n shape­from­shadin g  algorithms . 
`The recover y transformatio n  t o obtai n informatio n  abou t surfac e  orientatio n 
`is possibl e i f som e informatio n  abou t th e ligh t sourc e an d th e object' s reflectivit y i s 
`known.  Genera l  algorithm s  t o  obtai n  an d  quantif y  thi s  informatio n  ar e  compli ­
`cated bu t practica l simplification s  ca n b e mad e  [Hor n  1975 ; Woodha m  1978 ; Ikeu ­
`chi 1980] . Th e mai n complicatin g facto r  i s tha t eve n wit h mathematicall y  tractabl e 
`object surfac e properties , a  singl e imag e intensit y doe s no t uniquel y defin e th e sur ­
`face orientation . W e shal l stud y tw o way s o f overcomin g thi s difficulty .  Th e first  al ­
`gorithm  use s intensit y  image s a s inpu t  an d determine s  th e surfac e  orientatio n b y 
`using  multipl e  ligh t  sourc e  position s  t o remov e  ambiguit y  i n surfac e  orientation . 
`The secon d algorith m use s a  singl e sourc e bu t exploit s constraint s betwee n neigh ­
`boring surfac e elements . Suc h a n algorith m assign s initia l range s o f orientation s t o 
`surface  element s  (actuall y t o thei r correspondin g  imag e pixels )  o n th e basi s o f in ­
`tensity. Th e neighborin g  orientation s  ar e  "relaxed "  agains t eac h othe r unti l eac h 
`converges t o a  uniqu e orientatio n  (Sectio n 3.5.4) . 
`
`3.5.1  Reflectivit y Function s