Two choice s fo r  primitives : 
`
`^ 
`
`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 trade­of 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  four­tupl 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  one­to­on 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  seven­side d pol ­
`ygon split s int o a  six­side d polygo n an d a  five­side 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 four­side 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  tree­arra 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 
`left­han 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 low­resolutio 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  two­dimensiona 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 feature­spac 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 
`nearest­neighbor  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 , gray­leve l dependencies—an d  con ­
`clude wit h feature s  define d  o n  higher­leve 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 
`high­leve 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  histogram­equalize 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 Gray­Leve l  Dependenc e 
`
`Spatial  gray­leve 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 low­orde 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 gray­leve 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 well­ordere 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)ij­Hy)Sit,j\d,9) 
`
`crxo­ y 
`
`1id, 0 ) ­ £  f  
`/ = 0  j=0 
`
`ii­j) 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 
`
`Px­t,   lt.SU .MB) 
`/=o y= o 
`f * , ­ f y £  scute* ) 
`
`/=0  y= 0 
`
`» i ­ f 
`
`(i­V x)*tf(U\d,0) 
`,=o 
`y= o 
`
`°>2=s£  <J­fiy) 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 image­base 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  five­parameter   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  five­parameter   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 
`gray­leve 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 
`
`H­i  
`
`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 
`h­m —i 
`i — 1 1  I B  I I 
`M—H—M 
`
`1 
`
`I 
`
`H­H—H­4­ 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  r­9  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