`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) ]
`kl
`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 3bi
`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
`
`Kirschmotivate 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
`templatematchin 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
`lowleve l templatematchin 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 FreiChe 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 FreiChe 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 FreiChe 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 orientationsensitiv e
`operator t o b e brough t t o bea r o n it .
`
`3.3.3 ThreeDimensiona 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 threedimensiona 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 Modeldirecte d edg e
`detection.
`
`In threedimensiona 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 twodimensiona 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 threedimensiona 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 ZuckerHumme 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
`
`
`
`noiseinsensitiv 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 signaltonois
`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 realworl 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 edgetyp 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 "noedge " 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 lefthan 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 lefthan 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
`
`00
`02
`03
`
`11
`12
`13
`
`01
`22
`23
`33
`
`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 twodimensiona 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
`threedimensiona 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 lightyear 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 threedimensiona 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 threespace . 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 threedimensiona 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 threedimensiona 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 threedimensiona 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 threedimensiona 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 threedimensiona 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 righthan 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 randomdo t stereogram .
`
`the randoml y place d dot s o f th e lefthan 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 onedimensiona 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 randomdo 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 threedimensiona 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
`fromshadin 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 shapefromshadin 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