`
`^
`
`Fig. 6. 7 Ambiguou s texture .
`
`grammars correspondingl y mor e complicated . A particula r textur e tha t ca n b e
`described i n eigh t rule s i n a shap e gramma r require s 8 5 rule s i n a tre e gramma r [L u
`and F u 1978] . Th e compensatin g tradeof f i s tha t pixel s ar e grati s wit h th e image ;
`considerable processin g mus t b e don e t o deriv e th e mor e comple x primitive s use d
`by th e shap e grammar .
`
`6.3.2 Shap e Grammar s
`
`A shap e gramma r [Stin y an d Gip s 1972 ] i s define d a s a fourtupl e < V ti V m, R, S>
`where:
`1. V t i s a finit e se t o f shape s
`2. V m i s a finit e se t o f shape s suc h tha t V, f) V m = <j>
`3. R i s a finite se t o f ordere d pair s (u, v ) suc h tha t u i s a shap e consistin g o f ele
`ments o f V, + an d vi s a shap e consistin g o f a n elemen t o f V* combine d wit h a n
`element o f V* m
`4. S i s a shap e consistin g o f a n elemen t o f V* combine d wit h a n elemen t o f V* m.
`Elements o f th e se t V, ar e calle d termina l shap e element s (o r terminals) . Element s
`of th e se t V m ar e calle d nontermina l shap e element s (o r markers) . Th e set s V, an d
`Vm mus t b e disjoint . Element s o f th e se t V, + ar e forme d b y th e finit e arrangemen t
`of on e o r mor e element s o f V, i n whic h an y element s and/o r thei r mirro r image s
`may b e use d a multipl e numbe r o f time s i n an y location , orientation , o r scale . Th e
`set Vf = V, + U {A} , wher e A i s th e empt y shape . Th e set s V„ an d V* m ar e
`defined similarly . Element s (u, v ) o f R ar e calle d shap e rule s an d ar e writte n uv.
`ins calle d th e lef t sid e o f th e rule ; v th e righ t sid e o f th e rule , u an d v usuall y ar e en
`closed i n identica l dashe d rectangle s t o sho w th e correspondenc e betwee n th e tw o
`shapes. S i s calle d th e initia l shap e an d normall y contain s a u suc h tha t ther e i s a
`(u, v ) whic h i s a n elemen t o f R.
`
`Sec. 6. 3 Structural Models of Texel Placement
`
`173
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 189
`
`
`
`1.
`
`A textur e i s generate d fro m a shap e gramma r b y beginnin g wit h th e initia l
`shape an d repeatedl y applyin g th e shap e rules . Th e resul t o f applyin g a shap e rul e
`R t o a give n shap e s i s anothe r shape , consistin g o f 5 wit h th e righ t sid e o f R substi
`tuted i n S fo r a n occurrenc e o f th e lef t sid e o f R. Rul e applicatio n t o a shap e
`proceeds a s follows :
`Find par t o f th e shap e tha t i s geometricall y simila r t o th e lef t sid e o f a rul e i n
`terms o f bot h termina l element s an d nontermina l element s (markers) . Ther e
`must b e a onetoon e correspondenc e betwee n th e terminal s an d marker s i n
`the lef t sid e o f th e rul e an d th e terminal s an d marker s i n th e par t o f th e shap e
`to whic h th e rul e i s t o b e applied .
`Find th e geometri c transformation s (scale , translation , rotation , mirro r im
`age) whic h mak e th e lef t sid e o f th e rul e identica l t o th e correspondin g par t i n
`the shape .
`Apply thos e transformation s t o th e righ t sid e o f th e rule .
`Substitute th e transforme d righ t sid e o f th e rul e fo r th e par t o f th e shap e tha t
`corresponds t o th e lef t sid e o f th e rule .
`The generatio n proces s i s terminate d whe n n o rul e i n th e gramma r ca n b e applied .
`As a simpl e example , on e o f th e man y way s o f specifyin g a hexagona l textur e
`{F„ V miRyS) i s
`
`2.
`
`3.
`4.
`
`v . I • )
`
`(6.1)
`
`Hexagonal texture s ca n b e generated b y th e repeate d applicatio n o f th e singl e rul e
`in R. The y ca n b e recognized b y th e applicatio n o f th e rul e i n th e opposit e directio n
`to a give n textur e unti l th e initia l shape , / , i s produced . O f course , th e rul e wil l
`generate onl y hexagona l textures . Similarly , th e hexagona l textur e i n Fig . 6.8 a wil l
`be recognize d bu t th e variant s i n Fig . 6.8 b wil l not .
`
`Fig. 6. 8 Texture s t o b e recognize d (se e text) .
`
`(b)
`
`174
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 190
`
`
`
`A mor e difficul t exampl e i s give n b y th e "reptile " texture . Excep t fo r th e oc
`casional ne w rows , a (3,6,3,6 ) tesselatio n o f primitive s woul d mode l thi s textur e
`exactly. A s show n i n Fig . 6.9 , th e ne w ro w i s introduce d whe n a sevenside d pol
`ygon split s int o a sixside d polygo n an d a fiveside d polygon . T o captur e thi s wit h a
`shape grammar , w e examin e th e dua l o f thi s graph , whic h i s th e primitiv e place
`ment graph , Fig . 6.9b . Thi s grap h provide s a simpl e explanatio n o f ho w th e extr a
`row i s created ; tha t is , th e diamon d patter n split s int o two . Notic e tha t th e dua l
`graph i s compose d solel y o f fourside d polygon s bu t tha t som e vertice s ar e (4,4,4 )
`and som e ar e (4,4,4,4,4,4) . A shap e gramma r fo r th e dua l i s show n i n Fig . 6.10 .
`The imag e textur e ca n b e obtaine d b y formin g th e dua l o f thi s graph . On e furthe r
`refinement shoul d b e adde d t o rule s (6 ) an d (7) ; s o tha t rul e (7 ) i s use d les s often ,
`the appropriat e probabilitie s shoul d b e associate d wit h eac h rule . Thi s woul d mak e
`the gramma r stochastic .
`
`(a ) Th e reptil e texture , (b ) Th e reptil e textur e a s a (3,6 , 3,6 ) semireg
`Fig. 6. 9
`ular tesselatio n wit h loca l deformations .
`
`6.3.3 Tre e Grammar s
`
`The symboli c for m o f a tre e gramma r i s ver y simila r t o tha t o f a shap e grammar . A
`grammar
`
`G,= (V r, V m>r,R,S)
`
`is a tre e gramma r i f
`V, i s a se t o f termina l symbol s
`Vm i s a se t o f symbol s suc h tha t
`ym n v, = 0
`r :V,—> N (wher e ./Vi s th e se t o f nonnegativ e integers )
`is th e ran k associate d wit h symbol s i n V,
`Sis th e star t symbo l
`R i s th e se t o f rule s o f th e for m
`X0 —*X
`o r X 0 — x
`
`X0...Xr(x)
`with x in V, an d X 0... X r(x) i n V m
`For a tre e gramma r t o generat e array s o f pixels , i t i s necessar y t o choos e som e wa y
`of embeddin g th e tre e i n th e array . Figur e 6.1 1 show s tw o suc h embeddings .
`
`Sec. 6.3 Structural Models oi Texel Placement
`
`175
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 191
`
`
`
`• %
`
`= > e—e e e—e e
`=> o ®
`
`= > © « —
`
`= >
`
`= >
`
`= >
`
`o
`
`o
`
`Fig. 6.1 0 Shap e gramma r fo r th e reptil e texture .
`
`In th e applicatio n t o textur e [L u an d F u 1978] , th e notio n o f pyramid s o r
`hierarchical level s o f resolutio n i n textur e i s used . On e leve l describe s th e place
`ment o f repeatin g pattern s i n textur e windows— a rectangula r texe l placemen t
`tesselation—and anothe r leve l describe s texel s i n term s o f pixels . W e shal l illus
`
`176
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 192
`
`
`
`Start!ng
`point
`
`starting
`point
`
`f —
`
`F"
`
`« —
`
`(a) S t r u c t u r e A
`
`(b) Structur e B
`
`Fig. 6.1 1 Tw o way s o f embeddin g a tre e structur e i n a n array .
`
`trate thes e idea s wit h L u an d Fu' s gramma r fo r "wir e braid. " Th e textur e window s
`are show n i n Fig . 6.12a . Eac h o f thes e ca n b e describe d b y a "sentence " i n a
`second tre e grammar . Th e gramma r i s give n by :
`
`where
`
`Gw= (V,, V mir,R,S)
`
`r * U i . C i ]
`Vm = [X, Y, Z)
`r = {0 , 1 , 2 }
`R:X
`j
`Y
`X
`Y+ C x
`Z
`
`/
`
`or/I ,
`Y
`o r d
`
`Z —* A i
`
`o r A i
`
`Y
`
`(6.2)
`
`and th e firs t embeddin g i n Fig . 6.1 1 i s used . Th e patter n insid e eac h o f thes e win
`dows i s specifie d b y anothe r grammatica l level :
`G= (V ti V mr,R,S)
`
`Sec. 6. 3 Structural Models of Texel Placement ■ [77
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 193
`
`
`
`where
`
`R:
`
`V, = {1 , 0 }
`Vm = {Ai, A 2,A3, A4, A 5, A(„ AT, C\, C 2, C 3, C 4, CS, Ce, C7 ,
`N0, N h N 2, Ns, N 4}
`r = {0 , 1 , 2 }
`S = {Ah d)
`
`N0 A 2 N 0
`
`*.*
`
`/ I \
`"0 A 3
`
`\
`
`No
`
`\
`
`N o
`
`N, A 5
`
`\
`
`0
`
`N2 A 6 N 2
`
`N3 A 7
`
`" j
`
`\
`
`C 2 N i ,
`
`0
`
`s * / i \
`<
`C 3 M 4
`
`V / 1 \
`
`<
`
`C «, N 4
`
`'* * / 1 \
`N3 C 5 N 3
`
`0
`
`V / | \
`N2 C 6 N 2
`
`C6
`
`\
`/ |
`N, C 7 N ,
`
`H o *
`
`N. *
`
`N 2
`
`V
`
`»**
`
`1
`No
`
`1
`
`Mo
`
`0
`1
`N.
`
`0
`1
`N2
`
`0
`1
`N3
`
`V
`
`0
`\ 1
`i
`/
`*(, A ? N< |
`
`0
`\
`/
`N ^ H 4
`
`C^ /
`\
`l
`N0 C 7 %
`
`'
`
`1
`\
`
`/
`
`The applicatio n o f thes e rule s generate s th e tw o differen t pattern s o f pixel s
`shown i n Fig . 6.13 .
`
`6.3.4 Arra y Grammar s
`
`Like tre e grammars , arra y grammar s us e hierarchica l level s o f resolutio n [Milgra m
`and Rosenfel d 1971 ; Rosenfel d 1971] . Arra y grammar s ar e differen t fro m tre e
`grammars i n tha t the y d o no t us e th e treearra y embedding . Instead , prodigiou s
`use o f a blan k o r nul l symbo l i s use d t o mak e sur e th e rule s ar e applie d i n appropri
`ate contexts . A simpl e arra y gramma r fo r generatin g a checkerboar d patter n i s
`
`G = [V„ V n,R)
`
`178
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 194
`
`
`
`Fig. 6.1 2 Textur e windo w an d gramma r (se e text) .
`
`where
`
`V, = {0, 1 } (correspondin g t o blac k an d whit e pixels , respectively )
`
`V„ = [b, S}
`
`b i s a "blank " symbo l use d t o provid e contex t fo r th e applicatio n o f th e rules .
`Another notationa l convenienc e i s t o us e a subscrip t t o denot e th e orientatio n o f
`symbols. Fo r example , whe n describin g th e rule s R w e us e
`0xb » 0. vl
`to summariz e th e fou r rule s
`
`wher e x i s on e o f [U, D, L, R)
`
`0^—'01 ,
`0 ^ 0 '
`2 ~ * 1 '
`Thus th e checkerboar d rul e se t i s give n b y
`R: S — 0 o r 1
`0xb^ 0 X1
`\xb 1, 0
`
`x i n {U f.D, L, R)
`
`6 0 1 0
`
`A compac t encodin g o f textura l pattern s [Jayaramamurth y 1979 ] use s level s o f ar
`ray grammar s denne d o n a pyramid . Th e termina l symbol s o f on e laye r ar e th e star t
`symbols o f th e nex t grammatica l laye r define d lowe r dow n i n th e pyramid . Thi s
`corresponds nicel y t o th e ide a o f havin g on e gramma r t o generat e primitive s an d
`another t o generat e th e primitiv e placemen t tesselations .
`As anothe r example , conside r th e herringbon e patter n i n Fig . 6.14a , whic h i s
`composed o f 4x 3 array s o f a particula r placemen t patter n a s show n i n Fig . 6.14b .
`The followin g gramma r i s sufficien t t o generat e th e placemen t pattern .
`
`GW={V,, V m,R,S)
`
`Sec. 6. 3 Structural Models of Texel Placement
`
`179
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 195
`
`
`
`V
`
`^"^"v^ v v~ V
`. ?
`< X 5
`
`TIL.' '• '
`
`J »
`
`where
`
`jJ**W"«C
`
`iw ■ •■ ■ ■
`
`* » ■
`
`» "
`
`* v
`
`.
`
`* .
`
`jmm,
`
`, « ■ » . ■ ■ ■
`
`• ■ ■
`
`., «
`
`•
`
`» ■ » ■
`
`»
`
`«
`
`Fig. 6.1 3 Textur e generate d b y tre e
`grammar.
`
`y„ (f t 5 }
`R:S>a
`ax6 —* a xa
`x i n {£/ , D , L , R}
`We hav e no t bee n precis e i n specifyin g ho w th e termina l symbo l i s projecte d ont o
`the lowe r level . Assum e withou t los s o f generalit y tha t i t i s place d i n th e uppe r
`lefthan d corner , th e res t o f th e subarra y bein g initiall y blan k symbols . Thu s a sim
`ple gramma r fo r th e primitiv e i s
`
`G,= [V lt V n>R,S)
`
`#'
`
`S'
`#:
`#'
`
`INITIAL ARRA Y A T LEVE L 1
`
`O'
`
`TERMINAL ARRA Y A T LEVE L 1
`
`FINAL ARRA Y
`
`180
`
`Fig. 6.1 4 Step s i n generatin g a
`herringbone textur e wit h a n arra y
`grammar.
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 196
`
`
`
`where
`
`V, {0 , 1 }
`Vn {a, b)
`1 0
`a b b b
`0 0
`R:b b b b — 0 1 0 1
`b b b b
`1 0
`0 0
`
`6.4 TEXTUR E A S A PATTER N RECOGNITIO N PROBLE M
`
`Many texture s d o no t hav e th e nic e geometrica l regularit y o f "reptile " o r "wir e
`braid"; instead , the y exhibi t variation s tha t ar e no t satisfactoril y describe d b y
`shapes, bu t ar e bes t describe d b y statistica l models . Statistical pattern recognition i s a
`paradigm tha t ca n classif y statistica l variation s i n patterns . (Ther e ar e othe r statisti
`cal method s o f describin g textur e [Prat t e t al . 1981] , bu t w e wil l focu s o n statistica l
`pattern recognitio n sinc e i t i s th e mos t widel y use d fo r compute r visio n purposes. )
`There i s a voluminou s literatur e o n patter n recognition , includin g severa l excel
`lent text s (e.g. , [F u 1968 ; To u an d Gonzale z 1974 ; Fukunag a 1972] , an d th e idea s
`have muc h wide r applicatio n tha n thei r us e here , bu t the y see m particularl y ap
`propriate fo r lowresolutio n textures , suc h a s thos e see n i n aeria l image s [Weszk a
`et al . 1976] . Th e patter n recognitio n approac h t o th e proble m i s t o classif y in
`stances o f a textur e i n a n imag e int o a se t o f classes . Fo r example , give n th e tex
`tures i n Fig . 6.15 , th e choic e migh t b e betwee n th e classe s "orchard, " "field, "
`"residential," "water. "
`The basi c notio n o f patter n recognitio n i s th e feature vector. Th e featur e vec
`tor v i s a se t o f measurement s {v i • • • v m) whic h i s suppose d t o condens e th e
`description o f relevan t propertie s o f th e texture d imag e int o a small , Euclidea n
`feature space o f m dimensions . Eac h poin t i n featur e spac e represent s a valu e fo r
`the featur e vecto r applie d t o a differen t imag e (o r subimage ) o f texture . Th e meas
`urement value s fo r a featur e shoul d b e correlate d wit h it s clas s membership . Fig
`ure 6.1 6 show s a twodimensiona l spac e i n whic h th e feature s exhibi t th e desire d
`correlation property . Featur e vecto r value s cluste r accordin g t o th e textur e fro m
`which the y wer e derived . Figur e 6.1 6 show s a ba d choic e o f feature s (measure
`ments) whic h doe s no t separat e th e differen t classes .
`The patter n recognitio n paradig m divide s th e proble m int o tw o phases : train
`ing an d test . Usually , durin g a trainin g phase , featur e vector s fro m know n sample s
`are use d t o partitio n featur e spac e int o region s representin g th e differen t classes .
`However, sel f teachin g ca n b e done ; th e classifie r derive s it s ow n partitions .
`Feature selectio n ca n b e base d o n parametri c o r nonparametri c model s o f th e dis
`tributions o f point s i n featur e space . I n th e forme r case , analyti c solution s ar e
`sometimes available . I n th e latter , featur e vector s ar e clustered int o group s whic h
`are take n t o indicat e partitions . Durin g a tes t phas e th e featurespac e partition s ar e
`used t o classif y featur e vector s fro m unknow n samples . Figur e 6.1 7 show s thi s
`process.
`Given tha t th e dat a ar e reasonabl y wel l behaved , ther e ar e man y method s fo r
`clustering featur e vector s [Fukunag a 1972 ; To u an d Gonzale s 1974 ; F u 1974] .
`
`Sec. 6. 4 Texture as a Pattern Recognition Problem
`
`181
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 197
`
`
`
`I^fl^^
`
`yf :>':/)",
`
`'/■
`
`'■
`
`/'
`
`.j ■ Hi H H H H H
`
`J it
`
`182
`
`Ch. 6 Texture
`
`Fig. 6.1 5 Aeria l imag e texture s fo r
`discrimination.
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 198
`
`
`
`(cont. )
`Fig. 6.1 5
`One popula r wa y o f doin g thi s i s t o us e prototyp e point s fo r eac h clas s an d a
`nearestneighbor rul e [Cove r 1968] :
`assign v t o clas s w, i f / minimize s
`mindiv,
`\ w)
`i
`'
`where v^ . i s th e prototyp e poin t fo r clas s H> 7.
`Parametric technique s assum e informatio n abou t th e featur e vecto r probabil
`ity distribution s t o find rule s tha t maximiz e th e likelihoo d o f correc t classification :
`
`assign v t o clas s w t i f i maximize s
`max/?(w/|v)
`
`+ +
`+
`+
`
`a a
`
`o o o o 0
`o °
`° o
`
`D
`+ "
`D +
`o o
`
`O
`
`O +
`
`+
`o
`
`(a)
`
`(b)
`
`Fig. 6.1 6 Featur e spac e fo r textur e discrimination , (a ) effectiv e feature s (b )
`ineffective features .
`
`Sec. 6.4 Texture as a Pattern Recognition Problem
`
`183
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 199
`
`
`
`o °
`o o
`
`o °
`
`D °
`° c
`+ +
`+
`+ +
`
`(a)
`
`(b)
`
`• Classifie d a s w ,
`
`Fig. 6.1 7 Patter n recognitio n paradigm .
`
`The distribution s ma y als o b e use d t o formulat e rule s tha t minimiz e errors .
`Picking goo d feature s i s th e essenc e o f patter n recognition . N o elaborat e for
`malism wil l wor k wel l fo r ba d feature s suc h a s thos e o f Fig . 6.15b . O n th e othe r
`hand, almos t an y metho d wil l wor k fo r ver y goo d features . Fo r thi s reason , textur e
`is a goo d domai n fo r patter n recognition : i t i s fairl y eas y t o defin e feature s tha t (1 )
`cluster i n featur e spac e accordin g t o differen t classes , an d (2 ) ca n separat e textur e
`classes.
`The ensuin g subsection s describ e feature s tha t hav e worke d well . Thes e sub
`sections ar e i n revers e orde r fro m thos e o f Sectio n 6. 2 i n tha t w e begi n wit h
`features define d o n pixels—Fourie r subspaces , grayleve l dependencies—an d con
`clude wit h feature s define d o n higherleve l texel s suc h a s regions . However , th e
`lesson i s th e sam e a s wit h th e grammatica l approach : har d wor k spen t i n obtainin g
`highleve l primitive s ca n bot h improv e an d simplif y th e textur e model . Spac e doe s
`not permi t a discussio n o f man y textur e features ; instead , w e limi t ourselve s t o a
`few representativ e samples . Fo r furthe r reading , se e [Haralic k 1978] .
`
`6.4.1 Textur e Energ y
`
`Fourier Domain Basis
`If a textur e i s a t al l spatiall y periodi c o r directional , it s powe r spectru m wil l
`tend t o hav e peak s fo r correspondin g spatia l frequencies . Thes e peak s ca n for m th e
`basis o f feature s o f a patter n recognitio n discriminator . On e wa y t o defin e feature s
`is t o searc h Fourie r spac e directl y [Bajcs y an d Lieberma n 1976] . Anothe r i s t o par
`tition Fourie r spac e int o bins . Tw o kind s o f bins , radia l an d angular , ar e commonl y
`used, a s show n i n Fig . 6.18 . Thes e bins , togethe r wit h th e Fourie r powe r spectru m
`are use d t o defin e features . I f F\s th e Fourie r transform , th e Fourie r powe r spec
`trum i s give n b y \F\ 2.
`Radial feature s ar e give n b y
`vrir2 = Jf\F(.u,v)\ 2dudv
`
`(6.5 )
`
`184
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 200
`
`
`
`(a)
`
`(b)
`
`Fig. 6.1 8 Partitionin g th e Fourie r domai n int o bins .
`
`where th e limit s o f integratio n ar e define d b y
`u2 + v 2 < rl
`r\ < w 2 + v 2
`0 < u, v < n\
`where [r\ t r 2\ i s on e o f th e radia l bin s an d v i s th e vecto r (no t relate d t o v ) define d
`by differen t value s o f n an d r 2. Radia l feature s ar e correlate d wit h textur e coarse
`fo r smal l radii , wherea s a
`ness. A smoot h textur e wil l hav e hig h values o f V r
`coarse, grain y textur e wil l ten d t o hav e relativel y highe r value s fo r large r radii .
`Features tha t measur e angula r orientatio n ar e give n b y
`v)\ 2dudv
`= Jf\F(u,
`
`(6.6)
`
`V V 2
`where th e limit s o f integratio n ar e define d b y
`
`01 < tan 1
`
`<
`
`0 < u, v < n 1
`where [9 U 9 2) i s on e o f th e sector s an d v i s define d b y differen t value s o f 0 j an d 9 2.
`These feature s exploi t th e sensitivit y o f th e powe r spectru m t o th e directionalit y o f
`the texture . I f a textur e ha s a s man y line s o r edge s i n a give n directio n 9, \F\ 2 wil l
`tend t o hav e hig h value s clustere d aroun d th e directio n i n frequenc y spac e 9 +
`T T / 2 .
`
`Texture Energy in the Spatial Domain
`From Sectio n 2.2. 4 w e kno w tha t th e Fourie r approac h coul d als o b e carrie d
`out i n th e imag e domain . Thi s i s th e approac h take n i n [Law s 1980] . Th e advantag e
`of thi s approac h i s tha t th e basi s i s no t th e Fourie r basi s bu t a varian t tha t i s mor e
`
`Sec. 6.4 Texture as a Pattern Recognition Problem
`
`185
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 201
`
`
`
`matched t o intuitio n abou t textur e features . Figur e 6.1 9 show s th e mos t importan t
`of Laws ' 1 2 basi s functions .
`The imag e i s first histogramequalize d (Sectio n 3.2) . The n 1 2 ne w image s ar e
`made b y convolvin g th e origina l imag e wit h eac h o f th e basi s function s (\.t.,f' k =
`/ * h k fo r basi s function s h\, ... , /z 12). The n eac h o f thes e image s i s transforme d
`into a n "energy " imag e b y th e followin g transformation : Eac h pixe l i n th e con
`volved imag e i s replace d b y a n averag e o f th e absolut e value s i n a loca l windo w o f
`15x15 pixel s centere d ove r th e pixel :
`/;(%*)
`
`I
`
`(!/*(*:/ ) I)
`
`x',y' i n windo w
`The transformatio n f—+ /* , k = 1 , .. . 1 2 i s terme d a "textur e energ y transform "
`by Law s an d i s analogou s t o th e Fourie r powe r spectrum . Th e f k", k = 1 , .. . 1 2
`form a se t o f feature s fo r eac h poin t i n th e imag e whic h ar e use d i n a nearest
`neighbor classifier . Classificatio n detail s ma y b e foun d i n [Law s 1980] . Ou r in
`terest i s i n th e particula r choic e o f basi s function s used .
`Figure 6.2 0 show s a composit e o f natura l texture s [Brodat z 1966 ] use d i n
`Laws's experiments . Eac h textur e i s digitize d int o a 12 8 x 12 8 pixe l subimage . Th e
`texture energ y transform s wer e applie d t o thi s composit e imag e an d eac h pixe l wa s
`classified int o on e o f th e eigh t categories . Th e averag e classificatio n accurac y wa s
`about 87 % fo r interio r region s o f th e subimages . Thi s i s a ver y goo d resul t fo r tex
`tures tha t ar e similar .
`
`(6.7)
`
`6.4.2 Spatia l GrayLeve l Dependenc e
`
`Spatial grayleve l dependenc e (SGLD ) matrice s ar e on e o f th e mos t popula r
`sources o f feature s [Kruge r e t al . 1974 ; Hal l e t al . 1971 ; Haralic k e t al . 1973] . Th e
`SGLD approac h compute s a n intermediat e matri x o f measure s fro m th e digitize d
`image data , an d the n define s feature s a s function s o n thi s intermediat e matrix .
`Given a n imag e f wit h a se t o f discret e gra y level s I , w e defin e fo r eac h o f a se t o f
`discrete value s o f d and 9 th e intermediat e matri x S id, 9) a s follows :
`
`S(/, j\d, 9), a n entr y i n th e matrix , i s th e numbe r o f time s gra y leve l / i s
`oriented wit h respec t t o gra y leve l j suc h tha t wher e
`fix) = / an d
`/(y ) = j
`the n
`
`y = x + (dcos9, ds'm9) 1 4 6 4 1 2 8 1 2 8 2
`
`6 4
`1 4
`1 6 2 4 1 6 4
`6 2 4 3 6 2 4
`1 6 2 4 1 6 4
`1 4
`6 4
`
`1 4
`6 4
`1 1
`0 1 4 0 8 0
`1 1
`0 1 2 0 4 0
`4 6
`0 6 4 0 8 0
`4 1
`
`0
`0 0
`2
`8 1 2
`1 4
`6
`
`0 0
`8
`2
`4
`1
`
`0
`
`2
`
`2
`
`0
`2
`
`0
`
`0
`0
`0
`0 4 0
`2
`1 0 2 0
`
`0
`
`2
`
`0 1 2
`
`0
`
`2
`
`0 1
`
`Fig. 6.1 9 Laws'basi s function s (thes e
`are th e loworde r fou r o f twelv e actuall y
`used).
`
`186
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 202
`
`
`
`Fig. 6.2 0
`
`(a ) Textur e composite , (b ) Classification .
`
`Note tha t w e th e grayleve l value s appea r a s indice s o f th e matri x S, implyin g tha t
`they ar e take n fro m som e wellordere d discret e se t 0,... , K . Sinc e
`Sid, 9) = Sid, 9 + T T ) .
`common practic e i s t o restric t 9 t o multiple s o f TT/4 . Furthermore , informatio n i s
`not usuall y retaine d a t bot h 9 an d 9 + IT. Th e reasonin g fo r th e latte r ste p i s tha t
`for mos t textur e discriminatio n tasks , th e informatio n i s redundant . Thu s w e
`define
`
`Sid, 9) = >/2 [Sid, 9) + Sid, 9 + TT)]
`The intermediat e matrice s S yiel d potentia l features . Commonl y use d feature s are :
`1. Energy
`
`2. Entropy
`
`3. Correlation
`
`4. Inertia
`
`Eid,9) = j ^ £ [SO,M9)] 1
`/=o j=0
`
`K
`K
`Hid, 9) = ^ £ Sii,j\d,9)
`
`lo g fii,j\d,0)
`
`K
`K
`Z L
`^
`
`Cid, 9) = ^
`
`ii* x)ijHy)Sit,j\d,9)
`
`crxo y
`
`1id, 0 ) £ f
`/ = 0 j=0
`
`iij) 2Sii,j\d,9)
`
`Sec. 6.4 Texture as a Pattern Recognition Problem
`
`(6.8 )
`
`(6.9 )
`
`(6.10 )
`
`(6.11 )
`
`187
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 203
`
`
`
`5. Local Homogeneity
`
`L U * ) £ £
`
`r
`
`^SU,j\d,9)
`
`(6.12 )
`
`where S (/ , y |</ , 0 ) i s th e (/ , j) t h elemen t o f id, 9) , an d
`
`Pxt, lt.SU .MB)
`/=o y= o
`f * , f y £ scute* )
`
`/=0 y= 0
`
`» i f
`
`(iV x)*tf(U\d,0)
`,=o
`y= o
`
`°>2=s£ <Jfiy) 2tfb>M0)
`7=0
`1 0
`
`(6.13a )
`
`(6.i3b )
`
`(6.13c )
`
`(6.13d )
`
`and
`
`One importan t aspec t o f thi s approac h i s tha t th e feature s chose n d o no t hav e
`psychological correlate s [Tamur a e t al . 1978] . Fo r example , non e o f th e measure s
`described woul d tak e o n specifi c value s correspondin g t o ou r notion s o f "rough "
`or "smooth. " Also , th e textur e gradien t i s difficul t t o defin e i n term s o f SGL D
`feature value s [Bajcs y an d Lieberma n 1976] .
`
`6.4.3 Regio n Texel s
`
`Region texel s ar e a n imagebase d wa y o f definin g primitive s abov e th e leve l o f pix
`els. Rathe r tha n definin g feature s directl y a s function s o f pixels , a regio n segmen
`tation o f th e imag e i s create d first. Feature s ca n the n b e define d i n term s o f th e
`shape o f th e resultan t regions , whic h ar e ofte n mor e intuitiv e tha n th e pixel
`related features . Naturally , th e approac h o f usin g edg e element s i s als o possible .
`We shal l discus s thi s i n th e contex t o f textur e gradients .
`The ide a o f usin g region s a s textur e primitive s wa s pursue d i n [Maleso n e t al .
`1977]. I n tha t implementation , al l region s ar e ultimatel y modele d a s ellipse s an d a
`corresponding fiveparameter shap e descriptio n i s compute d fo r eac h region .
`These parameter s onl y defin e gros s regio n shape , bu t th e fiveparameter primi
`tives see m t o wor k wel l fo r man y domains . Th e textur e imag e i s segmente d int o
`regions i n tw o steps . Initially , th e modifie d versio n o f Algorith m 5. 1 tha t work s fo r
`grayleve l image s i s used . Figur e 6.2 1 show s thi s exampl e o f th e segmentatio n ap
`plied t o a sampl e o f "straw " texture . Next , parameter s o f th e regio n growe r ar e
`controlled s o a s t o encourag e conve x region s whic h ar e fit wit h ellipses . Figur e 6.2 2
`shows th e resultan t ellipse s fo r th e "straw " texture . On e se t o f ellips e parameter s
`is x 0, a, b, 9 wher e x 0 i s th e origin , a an d b ar e th e majo r an d mino r axi s length s
`and 9 i s th e orientatio n o f th e majo r axi s (Appendi x 1) . Beside s thes e shap e param
`eters, elliptica l texel s ar e als o describe d b y thei r averag e gra y level . Figur e 6.2 3
`gives a qualitativ e indicatio n o f ho w range s o n featur e value s reflec t differen t tex
`els.
`
`188
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 204
`
`
`
`(a) Imag e
`
`(b > Wit h Regio n Boundarie s
`.
`.
`*ig. 6.2 1 Regio n segmentatio n fo r stra w texture .
`
`6.5 TH E TEXTUR E GRADIEN T
`
`methods ar e depicte d i n F i 6 2 4 MUklTZ^
`embedded o n a plana r surfac e
`
`** " " b e d M e ' T h e *
`h ° d S a S s u m e t h a t t h e texture i s
`
`eu S1 ze o i thes e primitive s constrain s th e orientatio n o f
`
`Sec. 6.5 The Texture Gradient
`
`Fig. 6.2 2 Ellipse s fo r stra w texture .
`
`189
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 205
`
`
`
`H
`
`H ■ + H
`
`Average siz e f H H— H H
`
`H
`
`l
`M i
`I I I I
`
`I
`
`I
`I I
`^
`
`I
`
`Hi
`
`1—I
`1
`1 1— H 1 1
`
`h 1
`f
`H H
`
`90
`
`Bubbles
`Fiber
`Grass
`Leather
`Paper
`Raffia
`Sand
`Screen
`Straw
`Water
`
`35
`
`Bubbles
`Fiber
`Grass
`Leather
`Paper
`Raffia
`Sand
`Screen
`Straw
`Water
`
`0.1
`
`H—H—}H
`I II I
`I I I — I
`llll I II I
`hm —i
`i — 1 1 I B I I
`M—H—M
`
`1
`
`I
`
`HH—H4 H
`
`H — H i
`
`W
`
`1
`
`I—l H
`
`1 1 1
`
`0.7
`
`Average eccentricit y
`
`Fig. 6.2 3 Feature s define d o n ellipses .
`
`the plan e i n th e followin g manner . Th e directio n o f maximu m rat e o f chang e o f
`projected primitiv e siz e i s th e directio n o f th e texture gradient. Th e orientatio n o f
`this directio n wit h respec t t o th e imag e coordinat e fram e determine s ho w muc h
`the plan e i s rotate d abou t th e camer a lin e o f sight . Th e magnitud e o f th e gradien t
`can hel p determin e ho w muc h th e plan e i s tilte d wit h respec t t o th e camera , bu t
`knowledge abou t th e camer a geometr y i s als o required . W e hav e see n thes e idea s
`before i n th e for m o f gradien t space ; th e rotatio n an d til t characterizatio n i s a pola r
`coordinate representatio n o f gradients .
`
`(a)
`
`(b )
`
`(c )
`
`Fig. 6.2 4 Method s fo r calculatin g surfac e orientatio n fro m texture .
`
`1 9 0
`
`Ch. 6 Texture
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 206
`
`
`
`The secon d wa y t o measur e surfac e orientatio n i s b y knowin g th e shap e o f
`the texe l itself . Fo r example , a textur e compose d o f circle s appear s a s ellipse s o n
`the tilte d surface . Th e orientatio n o f th e principa l axe s define s rotatio n wit h respec t
`to th e camera , an d th e rati o o f mino r t o majo r axe s define s til t [Steven s 1979] .
`Finally, i f th e textur e i s compose d o f a regula r gri d o f texels , w e ca n comput e
`vanishing points . Fo r a perspectiv e image , vanishin g point s o n a plan e P ar e th e
`projection ont o th e imag e plan e o f th e point s a t infinit y i n a give n direction . I n th e
`examples here , th e texel s themselve s ar e (conveniently ) smal l lin e segment s o n a
`plane tha t ar e oriente d i n tw o orthogona l direction s i n th e physica l world . Th e gen
`eral metho d applie s wheneve r th e placemen t tesselatio n define s line s o f texels .
`Two vanishin g point s tha t aris e fro m texel s o n th e sam e surfac e ca n b e use d t o
`determine orientatio n a s follows . Th e lin e joinin g th e vanishin g point s provide s
`the orientatio n o f th e surfac e an d th e vertica l positio n o f th e plan e wit h respec t t o
`the z axi s (i.e. , th e intersectio n o f th e lin e joinin g th e vanishin g point s wit h x = 0 )
`determines th e til t o f th e plane .
`Line segmen t texture s indicat e vanishin g point s [Kende r 1978] . A s show n i n
`Fig. 6.25 , thes e segment s coul d aris e quit e naturall y fro m a n urba n imag e o f th e
`windows o f a buildin g whic h ha s bee n processe d wit h a n edg e operator .
`As discusse d i n Chapte r 4 , line s i n image s ca n b e detecte d b y detectin g thei r
`parameters wit h a Houg h algorithm . Fo r example , b y usin g th e lin e parameteriza
`tion
`
`x co s 6 + y si n 9 = r
`and b y knowin g th e orientatio n o f th e lin e i n term s o f it s gradien t g = (Ax , Ay), a
`line segmen t (x, y, Ax , Ay) ca n b e mappe d int o r, 9 spac e b y usin g th e relation s
`= Ax x + Ayy
`A / A X 2 + Aj; 2
`
`(6.14)
`
`= tan 1
`
`Ax
`
`(6.15)
`
`These relationship s ca n b e derive d b y usin g Fig . 6.2 6 an d som e geometry . Th e
`Cartesian coordinate s o f th e r—9 spac e vecto r ar e give n b y
`
`a =
`
`g*x g
`
`(6.16)
`
`Fig. 6.2 5 Orthogona l lin e segment s comprisin g a texture .
`
`Sec. 6. 5 The Texture Gradient
`
`191
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 207
`
`
`
`Fig. 6.2 6 r9 transform .
`
`Using thi s transformation , th e se t o f lin e segment s L\ show n i n Fig . 6.2 7 ar e al l
`mapped int o a singl e poin t i n r—B space . Furthermore , th e se t