COMFUT
`
`OMPUT=
`VISION
`
`
`
`DANA H . BALLAR D ­  CHRISTOPHE R M . BROW N 
`DANA H. BALLARD = CHRISTOPHER M. BROWN
`
`
`
`IPR2022-00092 - LGE
`
`Ex. 1015 - Page 1
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 1
`
`

`

`COMPUTER 
`VISION 
`
`DanaH.Ballard 
`Christopher  M . Brow n 
`
`Department  of   Computer   Science 
`University  of   Rochester 
`Rochester,  New   York 
`
`PRENTICE­HALL,  
`
`INC.,   Englewood   Cliffs,   New   Jersey   07632 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 2
`
`

`

`Library of   Congress   Cataloging   in  Publication   Data 
`
`I .  Brown ,  Christophe r  M . 
`
`BALLARD.  DAN A  HARRY . 
`Computer  vision . 
`Bibliography:  p . 
`Includes  index . 
`I.  Imag e  processing . 
`II.  Title . 
`TA1632.B34 
`ISBN  0­13­165316­
`
`621.38'04I 4 
`4 
`
`81­2097 4 
`AACR 2 
`
`Cover  desig n  b y  Robi n  Breit e 
`
`,  Inc . 
`©  198 2  b y  Prentice­Hall
`Englewood  Cliffs ,  Ne w  Jerse y  0763 2 
`
`All  right s  reserved .  N o  par t  o f  thi s  boo k 
`may  b e  reproduce d  i n  an y  for m  o r  b y  an y  mean s 
`without  permissio n  i n  writin g  fro m  th e  publisher . 
`
`Printed  i n  th e  Unite d  State s  o f  Americ a 
`
`10  9   8   7  6   5   4   3   2 
`
`ISBN  D­13­XtS31b­ M 
`
`PRENTICE­HAL L  INTERNATIONAL ,  INC. ,  London 
`PRENTICE­HAL L  O F  AUSTRALI A  PTY .  LIMITED ,  Sydney 
`PRENTICE­HAL L  O F  CANADA ,  LTD. ,  Toronto 
`PRENTICE­HAL L  O F  INDI A  PRIVAT E  LIMITED ,  New   Delhi 
`PRENTICE­HAL L  O F  JAPAN ,  INC. ,  Tokyo 
`PRENTICE­HAL L  O F  SOUTHEAS T  ASI A  PTE .  LTD. ,  Singapore 
`WHITEHALL  BOOK S  LIMITED ,  Wellington,   New   Zealand 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 3
`
`

`

`Preface 
`
`xii i 
`
`Acknowledgments 
`
`x v 
`
`Mnemonics  fo r  Proceeding s  an d  Specia l  Collection s  Cite d  i n 
`References 
`xi x 
`
`1  COMPUTE R  VISIO N 
`
`1 
`1.1  Achievin g Simpl e Visio n Goal s 
`1.2  High­Leve l  an d  Low­Leve l  Capabilitie s 
`1.3  A   Rang e  o f  Representation s 
`6 
`1.4  Th e  Rol e  o f  Computer s 
`9 
`1.5  Compute r  Visio n  Researc h  an d  Application s 
`
`2 
`
`1 2 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 4
`
`

`

`Part  I 
`GENERALIZED  IMAGE S 
`13 
`
`IMAGE  FORMATIO N 
`
`2.1 
`2.2 
`
`2.3 
`
`1 7 
`Image s 
`1 8 
`Imag e  Mode l 
`2.2.1 
`Imag e Functions ,  1 8 
`2.2.2 
`Imagin g  Geometry ,  1 9 
`2.2.3  Reflectance ,  2 2 
`2.2.4  Spatia l  Properties ,  2 4 
`2.2.5  Color ,  3 1 
`2.2.6  Digita l  Images ,  3 5 
`Imagin g  Device s  fo r  Compute r  Visio n 
`2.3.1  Photographi c  Imaging , 4 4 
`2.3.2  Sensin g  Range ,  5 2 
`2.3.3  Reconstructio n  Imaging ,  5 6 
`
`42 
`
`EARLY  PROCESSIN G 
`
`6 3 
`
`8 8 
`
`9 3 
`
`3.1 
`3.2 
`
`3.3 
`
`3.7 
`
`Recoverin g  Intrinsi c  Structur e 
`Filterin g  th e  Imag e 
`6 5 
`3.2.1  Templat e  Matching ,  6 5 
`3.2.2  Histogra m  Transformations ,  7 0 
`3.2.3  Backgroun d  Subtraction ,  7 2 
`3.2.4  Filterin g  an d  Reflectanc e  Models ,  7 3 
`Findin g  Loca l  Edge s 
`7 5 
`3.3.1  Type s o f  Edg e Operators , 7 6 
`3.3.2  Edg e  Thresholdin g  Strategies ,  8 0 
`3.3.3  Three­Dimensiona l  Edg e  Operators ,  8 1 
`3.3.4  Ho w  Goo d  Ar e  Edg e  Operators ?  8 3 
`3.3.5  Edg e  Relaxation ,  8 5 
`3.4  Rang e  Informatio n  fro m  Geometr y 
`3.4.1  Stere o  Visio n  an d  Triangulation ,  8 8 
`3.4.2  A   Relaxatio n  Algorith m  fo r  Stereo ,  8 9 
`3.5  Surfac e  Orientatio n  fro m  Reflectanc e  Model s 
`3.5.1  Reflectivit y  Functions , 9 3 
`3.5.2  Surfac e  Gradient ,  9 5 
`3.5.3  Photometri c  Stereo ,  9 8 
`3.5.4  Shap e  fro m  Shadin g  b y  Relaxation ,  9 9 
`3.6  Optica l  Flo w 
`10 2 
`3.6.1  Th e Fundamenta l  Flo w Constraint ,  10 2 
`3.6.2  Calculatin g  Optica l  Flo w  b y  Relaxation ,  10 3 
`Resolutio n  Pyramid s 
`10 6 
`3.7.1  Gray­Leve l  Consolidation ,  10 6 
`3.7.2  Pyramida l  Structure s  i n  Correlation ,  10 7 
`3.7.3  Pyramida l  Structure s  i n  Edg e  Detection ,  10 9 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 5
`
`

`

`PART  I I 
`SEGMENTED  IMAGE S 
`115 
`
`4.3 
`
`4.4 
`
`4.5 
`
`4  BOUNDAR Y  DETECTIO N 
`11 9 
`4.1  O n  Associatin g  Edg e  Element s 
`4.2 
`Searchin g  N e a r  a n  Approximat e  Locatio n 
`4.2.1  Adjustin g  A   Prior i  Boundaries ,  12 1 
`4.2.2  Non­Linea r  Correlatio n  i n  Edg e  Space ,  12 1 
`4.2.3  Divide­and­Conque
`r  Boundar y  Detection ,  12 2 
`T h e  H o u g h  Metho d  fo r  Curv e  Detectio n 
`12 3 
`4.3.1  Us e o f th e Gradient ,  12 4 
`4.3.2  Som e  Examples ,  12 5 
`4.3.3  Tradin g  Of f  Wor k  i n  Paramete r  Spac e  fo r  Wor k  i n 
`Image  Space ,  12 6 
`4.3.4  Generalizin g th e  Houg h  Transform ,  12 8 
`Edg e  Followin g  a s  G r a p h  Searchin g 
`4.4.1  Goo d Evaluatio n Functions , 13 3 
`4.4.2  Findin g  Al l  th e  Boundaries ,  13 3 
`4.4.3  Alternative s  t o  th e  A   Algorithm ,  13 6 
`Edg e  Followin g  a s  Dynami c  Programmin g 
`4.5.1  Dynami c  Programming ,  13 7 
`4.5.2  Dynami c  Programmin g  fo r  Images ,  13 9 
`4.5.3  Lowe r  Resolutio n  Evaluatio n  Functions ,  14 1 
`4.5.4  Theoretica l  Question s  abou t  Dynami c 
`Programming,  14 3 
`14 3 
`4.6  Contou r  Followin g 
`4.6.1  Extensio n  t o Gray­Leve l  Images ,  14 4 
`4.6.2  Generalizatio n  t o  Higher­Dimensiona l  Imag e 
`Data,  14 6 
`
`12 1 
`
`13 1 
`
`13 7 
`
`5  REGIO N  GROWIN G 
`Region s 
`14 9 
`5.1 
`15 1 
`5.2  A   Loca l  Technique :  Blo b  Colorin g 
`5.3  Globa l  Techniques :  Regio n  Growin g  vi a  Thresholdin g 
`5.3.1  Thresholdin g i n Multidimensiona l  Space ,  15 3 
`5.3.2  Hierarchica l  Refinement ,  15 5 
`Splittin g  an d  Mergin g 
`15 5 
`5.4.1  State­Spac e Approac h  t o  Regio n  Growing ,  15 7 
`5.4.2  Low­Leve l  Boundar y  Dat a  Structures ,  15 8 
`5.4.3  Graph­Oriente d  Regio n  Structures ,  15 9 
`Incorporatio n  o f  Semantic s 
`16 0 
`
`5.4 
`
`5.5 
`
`6  TEXTUR E 
`6.1  W h a t  I s  Texture ? 
`
`6.2 
`
`Textur e  Primitive s 
`
`16 6 
`
`16 9 
`
`Contents 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 6
`
`

`

`6.3 
`
`6.4 
`
`Structura l  Model s  o f  Texe l  Placemen t 
`6.3.1  Grammatica l  Models ,  17 2 
`6.3.2  Shap e  Grammars ,  17 3 
`6.3.3  Tre e  Grammars ,  17 5 
`6.3.4  Arra y  Grammars ,  17 8 
`Textur e  a s  a   Patter n  Recognitio n  Proble m 
`6.4.1  Textur e  Energy ,  18 4 
`6.4.2  Spatia l  Gray­Leve l  Dependence ,  18 6 
`6.4.3  Regio n  Texels ,  18 8 
`6.5  Th e  Textur e  Gradien t 
`
`17 0 
`
`18 1 
`
`18 9 
`
`7  MOTIO N 
`
`19 5 
`7.1  M o t i o n  Understandin g 
`7.1.1  Domain­Independen t  Understanding ,  19 6 
`7.1.2  Domain­Dependen t  Understanding ,  19 6 
`7.2  Understandin g  Optica l  Flo w 
`19 9 
`7.2.1  Focuso f  Expansion ,  19 9 
`7.2.2  Adjacency ,  Depth ,  an d  Collision ,  20 1 
`7.2.3  Surfac e  Orientatio n  an d  Edg e  Detection ,  20 2 
`7.2.4  Egomotion ,  20 6 
`20 7 
`7.3  Understandin g  Imag e  Sequence s 
`7.3.1  Calculatin g  Flo w  fro m  Discret e  Images , 20 7 
`7.3.2  Rigi d  Bodie s  fro m  Motion ,  21 0 
`7.3.3 
`Interpretatio n  o f  Movin g  Ligh t  Displays— A 
`Domain­Independen t  Approach ,  21 4 
`7.3.4  Huma n  Motio n  Understanding— A  Model ­
`Directed  Approach ,  21 7 
`7.3.5  Segmente d  Images ,  22 0 
`
`Part  II I 
`GEOMETRICAL  STRUCTURE S 
`227 
`
`8  REPRESENTATIO N  O F  TWO­DIMENSIONA L 
`GEOMETRIC STRUCTURE S 
`8.1  Two­Dimensiona l  Geometri c  Structure s 
`8.2  Boundar y  Representation s 
`23 2 
`8.2.1  Polylines , 23 2 
`8.2.2  Chai n  Codes ,  23 5 
`8.2.3  Th e  ty­j
`  Curve ,  23 7 
`8.2.4  Fourie r  Descriptors ,  23 8 
`8.2.5  Coni c  Sections ,  23 9 
`8.2.6  B­Splines ,  23 9 
`8.2.7  Stri p  Trees ,  24 4 
`
`23 1 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 7
`
`

`

`8.3 
`
`8.4 
`
`24 7 
`Regio n  Representation s 
`8.3.1  Spatia l  Occupanc y  Array ,  24 7 
`8.3.2  y   Axis ,  24 8 
`8.3.3  Qua d  Trees ,  24 9 
`8.3.4  Media l  Axi s  Transform ,  25 2 
`8.3.5  Decomposin g  Comple x  Areas ,  25 3 
`Simpl e  Shap e  Propertie s 
`25 4 
`8.4.1  Area , 25 4 
`8.4.2  Eccentricity ,  25 5 
`8.4.3  Eule r  Number ,  25 5 
`8.4.4  Compactness ,  25 6 
`8.4.5  Slop e  Densit y  Function ,  25 6 
`8.4.6  Signatures ,  25 7 
`8.4.7  Concavit y  Tree ,  25 8 
`8.4.8  Shap e  Numbers ,  25 8 
`
`26 4 
`
`9  REPRESENTATIO N  O F  THREE­DIMENSIONA L 
`STRUCTURES 
`9.1  Solid s  an d  Thei r  Representatio n 
`9.2  Surfac e  Representation s 
`26 5 
`9.2.1  Surface s  wit h  Faces , 26 5 
`9.2.2  Surface s  Base d  o n  Splines ,  26 8 
`9.2.3  Surface s  Tha t  Ar e  Function s  o n  th e  Sphere ,  27 0 
`9.3  Generalize d  Cylinde r  Representation s 
`27 4 
`9.3.1  Generalize d  Cylinde r Coordinat e  System s  an d 
`Properties,  27 5 
`9.3.2  Extractin g  Generalize d  Cylinders ,  27 8 
`9.3.3  A   Discret e  Volumetri c  Versio n  o f  th e Skeleton ,  27 9 
`9.4  Volumetri c  Representation s 
`28 0 
`9.4.1  Spatia l  Occupancy ,  28 0 
`9.4.2  Cel l  Decomposition ,  28 1 
`9.4.3  Constructiv e  Soli d  Geometry ,  28 2 
`9.4.4  Algorithm s  fo r  Solid   Representations ,  28 4 
`9.5  Understandin g  Lin e  Drawing s 
`29 1 
`9.5.1  Matchin g  Lin e Drawing s t o  Three­Dimensiona l 
`Primitives,  29 3 
`9.5.2  Groupin g  Region s  Int o  Bodies ,  29 4 
`9.5.3  Labelin g  Lines ,  29 6 
`9.5.4  Reasonin g  Abou t  Planes ,  30 1 
`
`Part  I V 
`RELATIONAL  STRUCTURE S 
`313 
`
`1 0  KNOWLEDG E  REPRESENTATIO N  AN D  US E 
`10.1  Representation s 
`31 7 
`10.1.1  Th e Knowledg e  Base—Model s  an d  Processes , 31 8 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 8
`
`

`

`10.1.2  Analogica l  an d  Propositiona l  Representations , 
`319 
`10.1.3  Procedura l  Knowledge ,  32 1 
`10.1.4  Compute r  Implementations ,  32 2 
`10.2  Semanti c  Net s 
`32 3 
`10.2.1  Semanti c  Ne t  Basics , 32 3 
`10.2.2  Semanti c  Net s  fo r  Inference ,  32 7 
`10.3  Semanti c  Ne t  Example s 
`33 4 
`10.3.1  Fram e  Implementations ,  33 4 
`10.3.2  Locatio n  Networks ,  33 5 
`10.4  Contro l  Issue s  i n  Comple x  Visio n  System s 
`10.4.1  Paralle l an d  Seria l Computation ,  34 1 
`10.4.2  Hierarchica l  an d  Heterarchica l  Control ,  34 1 
`10.4.3  Belie f  Maintenanc e  an d  Goa l  Achievement ,  34 6 
`
`34 0 
`
`1 1  MATCHIN G 
`
`35 2 
`
`35 5 
`
`35 2 
`1.1  Aspect s  o f  Matchin g 
`11.1.1 
`Interpretation :  Construction ,  Matching ,  an d 
`Labeling  35 2 
`I l.l. 2  Matchin g  Iconic ,  Geometric ,  an d  Relationa l 
`Structures,  35 3 
`1.2  Graph­Theoreti c  Algorithm s 
`11.2.1  Th e Algorithms , 35 7 
`11.2.2  Complexity ,  35 9 
`Implementin g  Graph­Theoreti c  Algorithm s 
`11.3.1  Matchin g  Metrics , 36 0 
`11.3.2  Backtrac k  Search ,  36 3 
`11.3.3  Associatio n  Grap h  Techniques ,  36 5 
`1.4  Matchin g  i n  Practic e 
`36 9 
`11.4.1  Decisio n  Trees , 37 0 
`11.4.2  Decisio n  Tre e  an d  Subgrap h  Isomorphism ,  37 5 
`11.4.3 
`Informa l  Featur e  Classification ,  37 6 
`11.4.4  A   Comple x  Matcher ,  37 8 
`
`1.3 
`
`36 0 
`
`1 2 
`
`INFERENC E 
`
`38 3 
`
`12.1 
`
`38 4 
`First­Orde r  Predicat e  Calculu s 
`12.1.1  Clause­For m  Synta x  (Informal) ,  38 4 
`12.1.2  Nonclausa l  Synta x  an d  Logi c  Semantic s 
`(Informal),  38 5 
`12.1.3  Convertin g  Nonclausa l  For m  t o  Clauses , 38 7 
`12.1.4  Theore m  Proving ,  38 8 
`12.1.5  Predicat e  Calculu s  an d  Semanti c  Networks ,  39 0 
`12.1.6  Predicat e  Calculu s  an d  Knowledg e 
`Representation,  39 2 
`39 5 
`12.2  Compute r  Reasonin g 
`39 6 
`12.3  Productio n  System s 
`12.3.1  Productio n  Syste m  Details ,  39 8 
`12.3.2  Patter n  Matching ,  39 9 
`
`Contents 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 9
`
`

`

`40 8 
`
`12.3.3  A n  Example ,  40 1 
`12.3.4  Productio n  Syste m  Pro s  an d  Cons ,  40 6 
`12.4  Scen e  Labelin g  an d  Constrain t  Relaxatio n 
`12.4.1  Consisten t  an d  Optima l  Labelings , 40 8 
`12.4.2  Discret e  Labelin g  Algorithms ,  41 0 
`12.4.3  A   Linea r  Relaxatio n  Operato r  an d  a   Line ­
`Labeling  Example ,  41 5 
`12.4.4  A  Nonlinea r  Operator ,  41 9 
`12.4.5  Relaxatio n  a s  Linea r  Programming ,  42 0 
`12.5  Activ e  Knowledg e 
`43 0 
`12.5.1  Hypotheses , 43 1 
`12.5.2  HOW­T O  an d  SO­WHA T  Processes ,  43 1 
`12.5.3  Contro l  Primitives ,  43 1 
`12.5.4  Aspect s  o f  Activ e  Knowledge ,  43 3 
`
`13  GOA L  ACHIEVEMEN T 
`
`43 9 
`13.1  Symboli c  Plannin g 
`13.1.1  Representin g th e World , 43 9 
`13.1.2  Representin g  Actions ,  44 1 
`13.1.3  Stackin g  Blocks ,  44 2 
`13.1.4  Th e  Fram e  Problem ,  44 4 
`Plannin g  wit h  Cost s 
`44 5 
`13.2.1  Planning ,  Scoring , an d  Thei r  Interaction , 44 6 
`13.2.2  Scorin g  Simpl e  Plans ,  44 6 
`13.2.3  Scorin g  Enhance d  Plans ,  45 1 
`13.2.4  Practica l  Simplifications ,  45 2 
`13.2.5  A   Visio n  Syste m  Base d  o n  Planning ,  45 3 
`
`13.2 
`
`APPENDICES 
`465 
`
`43 8 
`
`A 1  SOM E  MATHEMATICA L  TOOL S 
`
`46 5 
`
`A l . 2 
`
`46 5 
`
`Al.l  Coordinat e  System s 
`A l . I . I   Cartesian ,  46 5 
`Al.l.2  Pola r  an d  Pola r  Space ,  46 5 
`Al.l.3  Spherica l  an d  Cylindrical ,  46 6 
`Al.l.4  Homogeneou s  Coordinates ,  46 7 
`Trigonometr y 
`46 8 
`Al.2.1  Plan e Trigonometry ,  46 8 
`A 1.2. 2  Spherica l  Trigonometry ,  46 9 
`A 1. 3  Vector s 
`46 9 
`A 1. 4  Matrice s 
`47 1 
`A 1. 5 
`Line s 
`47 4 
`A 1.5. 1  Tw o  Points , 47 4 
`A 1.5. 2  Poin t  an d  Direction ,  47 4 
`A 1.5. 3  Slop e  an d  Intercept ,  47 4 
`
`Contents 
`
`xi 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 10
`
`

`

`A 1.5. 4  Ratios ,  47 4 
`Al.5.5  Norma l  an d  Distanc e  fro m  Origi n  (Lin e 
`Equation),  47 5 
`A 1.5. 6  Parametric , 47 6 
`A 1. 6  Plane s 
`47 6 
`A 1. 7  Geometri c  Transformation s 
`A 1.7. 1  Rotation , 47 7 
`A 1.7. 2  Scaling ,  47 8 
`A 1.7. 3  Skewing ,  47 9 
`Al.7.4  Translation ,  47 9 
`A 1.7. 5  Perspective ,  47 9 
`Al.7.6  Transformin g  Line s  an d  Planes ,  48 0 
`A 1.7. 7  Summary ,  48 0 
`A 1. 8  Camer a  Calibratio n  an d  Invers e  Perspectiv e 
`A1.8.1  Camer a  Calibration ,  48 2 
`A 1.8. 2 
`Invers e  Perspective ,  48 3 
`48 4 
`A 1. 9  Least­Squared­Erro r  Fittin g 
`A1.9.1  Pseudo­Invers e Method , 48 5 
`A 1.9. 2  Principa l  Axi s  Method ,  48 6 
`Al.9.3  Fittin g  Curve s  b y  th e  Pseudo­Invers e  Method , 
`487 
`48 8 
`A 1.1 0  Conie s 
`48 9 
`A 1.1 1 
`Interpolatio n 
`,  48 9 
`Al.11.1  One­Dimensional
`A 1.11. 2  Two­Dimensional
`,  49 0 
`A 1.1 2  Th e  Fas t  Fourie r  Transfor m 
`A 1.1 3  Th e  Icosahedro n 
`49 2 
`A 1.1 4  Roo t  Findin g 
`49 3 
`
`48 1 
`
`47 7 
`
`49 0 
`
`A 2  ADVANCE D  CONTRO L  MECHANISM S 
`
`49 7 
`
`A2.2 
`
`A2.1  Standar d  Contro l  Structure s 
`A2.1.1  Recursion , 49 8 
`A2.1.2  Co­Routining ,  49 8 
`Inherentl y  Sequentia l  Mechanism s 
`A2.2.1  Automati c  Backtracking , 49 9 
`A2.2.2  Contex t  Switching ,  50 0 
`A2.3  Sequentia l  o r  Paralle l  Mechanism s 
`A2.3.1  Module s  an d  Messages , 50 0 
`A2.3.2  Priorit y  Jo b  Queue ,  50 2 
`A2.3.3  Pattern­Directe d  Invocation ,  50 4 
`A2.3.4  Blackboar d  Systems ,  50 5 
`
`49 9 
`
`50 0 
`
`AUTHOR  INDE X 
`
`SUBJECT INDE X 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 11
`
`

`

`Preface 
`
`The drea m o f intelligen t automat a goe s bac k t o antiquity ; it s first  majo r  articulatio n 
`in  th e  contex t  o f  digita l  computer s  wa s  b y  Turin g  aroun d  1950 . Sinc e  then ,  thi s 
`dream  ha s  bee n  pursue d  primaril y  b y  worker s  i n  th e field  o f artificial   intelligence, 
`whose  goa l  i s  t o  endo w  computer s  wit h  information­processin g  capabilitie s 
`comparable  t o  thos e o f biologica l  organisms . Fro m  th e outset ,  on e o f th e goal s o f 
`artificial  intelligenc e ha s bee n t o equi p machine s wit h th e capabilit y o f dealin g wit h 
`sensory  inputs . 
`Computer vision  i s  th e  constructio n  o f  explicit ,  meaningfu l  description s  o f 
`physical  object s  fro m  images .  Imag e  understandin g  i s  ver y  differen t  fro m  imag e 
`processing,  whic h  studie s  image­to­imag e  transformations ,  no t  explici t  descriptio n 
`building.  Description s  ar e  a   prerequisit e  fo r  recognizing ,  manipulating ,  an d 
`thinking  abou t  objects . 
`We  perceiv e  a   worl d  o f  coheren t  three­dimensiona l  object s  wit h  man y 
`invariant  properties .  Objectively ,  th e  incomin g  visua l  dat a  d o  no t  exhibi t 
`corresponding  coherenc e  o r  invariance ;  the y  contai n  muc h  irrelevan t  o r  eve n 
`misleading  variation .  Someho w  ou r  visua l  system ,  fro m  th e  retina l  t o  cognitiv e 
`levels, understands ,  o r  impose s orde r  on ,  chaoti c visua l  input .  I t  doe s s o b y usin g 
`intrinsic information  tha t ma y reliabl y b e extracte d fro m  th e input,  an d als o throug h 
`assumptions  an d  knowledge  tha t  ar e applie d  a t  variou s  level s i n visua l processing . 
`The  challeng e  o f  compute r  visio n  i s  on e  o f  explicitness.   Exactl y  wha t 
`information  abou t  scene s  ca n  b e  extracte d  fro m  a n  imag e  usin g  onl y  ver y  basi c 
`assumptions  abou t  physic s  an d  optics ?  Explicitly ,  wha t  computation s  mus t  b e 
`performed?  Then ,  a t  wha t  stag e  mus t  domain­dependent
`,  prio r  knowledg e  abou t 
`the  worl d  b e incorporate d  int o th e understandin g  process ? Ho w ar e worl d  model s 
`and  knowledg e  represente d  an d  used ? Thi s  boo k  i s abou t  th e representation s  an d 
`mechanisms tha t allo w imag e informatio n  an d prio r knowledg e t o interac t i n imag e 
`understanding. 
`Computer  visio n  i s  a   relativel y  ne w  an d  fast­growin g  field.   Th e  first 
`experiments  wer e  conducte d  i n th e  lat e  1950s , an d  man y  o f th e essentia l  concept s 
`xiii 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 12
`
`

`

`have bee n develope d durin g th e las t five  years . Wit h thi s rapi d growth , crucia l idea s 
`have  arise n  i n  disparat e  area s  suc h  a s artificia l  intelligence ,  psychology ,  compute r 
`graphics, an d imag e processing . Ou r inten t i s t o assembl e a  selectio n o f thi s materia l 
`in  a   for m  tha t  wil l  serv e  bot h  a s  a  senior/graduate­leve l  academi c  tex t  an d  a s  a 
`useful  referenc e  t o  thos e buildin g  visio n  systems . Thi s boo k  ha s  a  stron g  artificia l 
`intelligence flavor,  an d w e hop e thi s wil l provok e thought . W e believ e tha t bot h th e 
`intrinsic  imag e  informatio n  an d  th e interna l  mode l  o f  th e worl d  ar e  importan t  i n 
`successful  visio n  systems . 
`The boo k i s organize d  int o fou r parts , base d  o n description s o f object s a t fou r 
`different  level s o f  abstraction . 
`
`1.  Generalize d images—image s an d image­lik e entities . 
`2.  Segmente d  images—image s  organize d  int o  subimage s  tha t  ar e  likel y  t o 
`correspond  t o "interestin g  objects. " 
`3.  Geometri c structures—quantitativ e model s o f imag e an d worl d structures . 
`4.  Relationa l  structures—comple x  symboli c description s  o f imag e an d  worl d 
`structures. 
`The part s follo w  a  progressio n  o f  increasin g  abstractness .  Althoug h  th e  fou r 
`parts ar e mos t naturall y studie d i n succession , the y ar e no t tightl y interdependent . Par t 
`I i s a  prerequisit e fo r  Par t II , bu t  Part s II I an d  I V ca n  b e rea d  independently . 
`Parts  o f  th e  boo k  assum e  som e  mathematica l  an d  computin g  backgroun d 
`(calculus, linea r algebra , dat a structures , numerica l methods) . However , throughou t 
`the boo k mathematica l rigo r take s a  backsea t t o concepts . Ou r inten t i s t o transmi t a  se t 
`of idea s abou t  a  ne w field  t o th e wides t possibl e audience . 
`In on e boo k i t i s impossibl e t o d o justic e t o th e scop e an d dept h o f prio r wor k i n 
`computer vision . Further , w e realiz e tha t i n a  fast­developin g field,  th e rapi d influ x o f 
`new idea s wil l continue . W e hop e tha t ou r reader s wil l b e challenge d t o think , criticize , 
`read  further ,  an d  quickl y g o beyon d th e confine s  o f thi s volume . 
`
`xiv 
`
`Preface 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 13
`
`

`

`Acknowledgments 
`
`Jerry  Feldma n  an d  Her b Voelcke r (an d throug h the m  th e Universit y  o f Rochester ) 
`provided  man y  resource s  fo r  thi s work .  On e  o f th e mos t  importan t  wa s a  capabl e 
`and  forgivin g  staf f  (secretarial ,  technical ,  an d  administrative) .  Fo r  massiv e  tex t 
`editing,  valuabl e  advice ,  an d  goo d  humo r  w e ar e especiall y  gratefu l  t o  Ros e  Peet . 
`Peggy  Meeker ,  Jil l  Orioli ,  an d  Bet h  Zimmerma n  al l  helpe d  a t  variou s  stages . 
`Several  colleague s  mad e  suggestion s  o n  earl y  drafts :  thank s  t o  Jame s  Allen , 
`Norm  Badler ,  Larr y  Davis , Take o  Kanade ,  Joh n  Render ,  Dary l  Lawton ,  Josep h 
`O'Rourke,  Ar i  Requicha ,  E d  Riseman ,  Azrie l  Rosenfeld ,  Mik e  Schneier ,  Ke n 
`Sloan,  Stev e Tanimoto ,  Mart y  Tenenbaum ,  an d  Stev e  Zucker . 
`Graduate student s helpe d  i n man y differen t  ways : thank s especiall y t o  Miche l 
`Denber,  Ala n  Frisch ,  Lydi a  Hrechanyk ,  Mar k  Kahrs ,  Keit h  Lantz ,  Jo e  Maleson , 
`Lee Moore ,  Mar k  Peairs , Do n  Perlis , Ric k  Rashid , Da n  Russell , Da n Sabbah , Bo b 
`Schudy, Pete r Selfridge ,  Ur i Shani , an d Bo b Tilove . Bernhar d Stut h deserve s specia l 
`mention  fo r  muc h carefu l  an d critica l reading . 
`Finally, thank s g o t o  Jan e Ballard ,  mostl y  fo r  standin g  steadfas t  throug h th e 
`cycles  o f elatio n  an d  depressio n  an d  fo r  numerou s  engineering­to­Englis h  transla ­
`tions. 
`As Pa t Winsto n pu t it : " A willingnes s t o hel p i s no t a n implie d endorsement. " 
`The  ai d  o f  other s  wa s  invaluable ,  bu t  w e  alon e  ar e  responsibl e  fo r  th e  opinions , 
`technical  details ,  an d  fault s  o f  thi s  book . 
`Funding  assistanc e wa s provide d b y th e Sloa n  Foundatio n  unde r Gran t 78­4 ­
`15, b y th e Nationa l  Institute s  o f Healt h  unde r Gran t  HL21253 , an d b y th e  Defens e 
`Advanced  Researc h  Project s  Agenc y  unde r  Gran t  N00014­78­C­0164
`. 
`The  author s  wis h  t o  credi t  th e  followin g  source s  fo r  figure s  an d  tables .  Fo r 
`complete  citation s  give n  her e  i n  abbreviate d  for m  (a s  "fro m  .  .  . "  o r  "afte r  .  .   .") , 
`refer  t o  th e  appropriat e  chapter­en d  references . 
`
`Fig.  1. 2  fro m  Shani ,  U. ,  " A  3­ D  model­drive n  syste m  fo r  th e  recognitio n  o f  abdomina l 
`anatomy  fro m  C T scans, " TR77 ,  Dept . o f Compute r  Science , Universit y  o f  Rochester ,  Ma y 
`1980. 
`
`Acknowledgments 
`
`xv 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 14
`
`

`

`Fig.  1. 4  courtes y  o f  Alle n  Hanso n  an d  E d  Riseman ,  COIN S  Researc h  Project ,  Universit y  o f 
`Massachusetts,  Amherst ,  MA . 
`Fig.  2. 4  afte r  Hor n  an d  Sjoberg ,  1978 . 
`Figs.  2.5 ,  2.9 ,  2.10 ,  3.2 ,  3.6 ,  an d  3. 7  courtes y  o f  Bil l  Lampeter . 
`Fig. 2.7 a  paintin g  b y  Loui s  Condax ;  courtes y  o f  Eastma n  Koda k  Compan y  an d  th e  Optica l 
`Society  o f  America . 
`Fig. 2.8 a  courtes y  o f  D . Greenber g  an d  G .  Joblove ,  Cornel l  Progra m  o f Compute r  Graphics . 
`Fig.  2.8 b  courtes y  o f  To m  Check . 
`Table  2. 3  afte r  Gonzale z  an d  Wintz ,  1977 . 
`Fig.  2.1 8  courtes y  o f  ERO S  Dat a  Center ,  Siou x  Falls ,  SD . 
`Figs.  2.1 9  an d  2.2 0  fro m  Herrick ,  C.N. ,  Television   Theory   and   Servicing:   Black/White   and 
`Color,  2n d  Ed .  Reston ,  VA :  Reston ,  1976 . 
`Figs.  2.21 , 2.22 ,  2.23 ,  an d  2.2 4  courtes y  o f  Miche l  Denber . 
`Fig.  2.2 5  fro m  Poppleston e  e t  al. ,  1975 . 
`Fig.  2.2 6  courtes y  o f  Productio n  Automatio n  Project ,  Universit y  o f  Rochester . 
`Fig.  2.2 7  fro m  Waa g  an d  Gramiak ,  1976 . 
`Fig.  3. 1  courtes y  o f  Mart y  Tenenbaum . 
`Fig.  3. 8  afte r  Horn ,  1974 . 
`Figs.  3.1 4  an d  3.1 5  afte r  Fre i  an d  Chen ,  1977 . 
`Figs.  3.1 7  an d  3.1 8  fro m  Zucker ,  S.W .  an d  R.A .  Hummel ,  "A n  optima l  3­ D  edg e  operator, " 
`IEEE  Trans.   PAMI3,   Ma y  1981 , pp .  324­331 . 
`Fig.  3.1 9  curve s  ar e  base d  o n  dat a  i n  Abdou ,  1978 . 
`Figs. 3.20 ,  3.21 , an d  3.2 2  fro m  Prager ,  J.M. ,  "Extractin g  an d  labelin g  boundar y  segment s  i n 
`natural  scenes, "  IEEE   Tans.   PAMI   12,   1 , Januar y  1980 . ©   198 0  IEEE . 
`Figs.  3.23 , 3.28 , 3.29 ,  an d  3.3 0 courtes y  o f  Berthol d  Horn . 
`Figs.  3.2 4  an d  3.2 6  fro m  Marr ,  D .  an d  T .  Poggio ,  "Cooperativ e  computatio n  o f  stere o  dis ­
`parity,"  Science,   Vol .  194 ,  1976 , pp . 283­287 .  ©   197 6 b y th e America n  Associatio n  fo r  th e 
`Advancement  o f  Science . 
`Fig.  3.3 1  fro m  Woodham ,  R.J. ,  "Photometri c  stereo : A   reflectanc e  ma p  techniqu e  fo r  deter ­
`mining  surfac e  orientatio n  fro m  imag e  intensity, "  Proc.   SPIE,   Vol .  155 ,  Augus t  1978 . 
`Figs.  3.3 3  an d  3.3 4  afte r  Hor n  an d  Schunck ,  1980 . 
`Fig.  3.3 7  fro m  Tanimoto ,  S .  an d  T .  Pavlidis ,  " A  hierarchica l  dat a  structur e  fo r  pictur e  pro ­
`cessing,"  CGIP   4,   2 ,  Jun e  1975 ,  pp .  104­119 . 
`Fig.  4. 6  fro m  Kimm e  e t  al. ,  1975 . 
`Figs.  4. 7  an d  4.1 6  fro m  Ballar d  an d  Sklansky ,  1976 . 
`Fig.  4. 9  courtes y  o f  Dan a  Ballar d  an d  Ke n  Sloan . 
`Figs. 4.1 2 an d  4.1 3 fro m  Ramer ,  U. ,  "Extractio n  o f  lin e structure s  fro m  photgraph s  o f curve d 
`objects,"  CGIP   4,   2,   Jun e  1975 ,  pp .  81­103 . 
`Fig.  4.1 4  courtes y  o f  Ji m  Lester ,  Tufts/Ne w  Englan d  Medica l  Center . 
`Fig.  4.1 7  fro m  Chien ,  Y.P .  an d  K.S .  Fu ,  " A  decisio n  functio n  metho d  fo r  boundar y  detec ­
`tion,"  CGIP   3,   2 ,  Jun e  1974 ,  pp .  125­140 . 
`Fig.  5. 3  fro m  Ohlander ,  R. ,  K .  Price , an d  D.R .  Reddy ,  "Pictur e  segmentatio n  usin g  a   recur ­
`sive regio n  splittin g  method, "  CGIP   8,   3 ,  Decembe r  1979 . 
`Fig.  5. 4  courtes y  o f  Sa m  Kapilivsky . 
`Figs.  6.1 ,  11.16 ,  an d  A  1.1 3  courtes y  o f  Chri s  Brown . 
`Fig.  6. 3  courtes y  o f  Jo e  Maleso n  an d  Joh n  Kender . 
`Fig.  6. 4  fro m  Connors ,  1979 .  Textur e  image s  b y  Phi l  Brodatz ,  i n  Brodatz ,  Textures.   Ne w 
`York:  Dover ,  1966 . 
`Fig.  6. 9  textur e  imag e  b y  Phi l  Brodatz ,  i n  Brodatz ,  Textures.   Ne w  York :  Dover ,  1966 . 
`Figs.  6.11 ,  6.12 ,  an d  6.1 3  fro m  Lu ,  S.Y .  an d  K.S .  Fu ,  " A  syntacti c  approac h  t o  textur e 
`analysis,"  CGIP   7,  3 ,  Jun e  1978 ,  pp .  303­330 . 
`
`xvi 
`
`Acknowledgments 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 15
`
`

`

`Fig.  6.1 4  fro m  Jayaramamurthy ,  S.N. ,  "Multileve l  arra y  grammar s  fo r  generatin g  textur e 
`scenes,"  Proc.   PRIP,   Augus t  1979 , pp . 391­398 . ©   197 9  IEEE . 
`Fig. 6.2 0  fro m  Laws ,  1980 . 
`Figs.  6.2 1  an d  6.2 2  fro m  Maleso n  e t  al. ,  1977 . 
`Fig.  6.2 3  courtes y  o f  Jo e  Maleson . 
`Figs.  7. 1  an d  7. 3  courtes y  o f  Dary l  Lawton . 
`Fig.  7. 2  afte r  Prager ,  1979 . 
`Figs. 7. 4 an d  7. 5  fro m  Clocksin ,  W.F. ,  "Compute r  predictio n  o f  visua l  threshold s  fo r  surfac e 
`slant  an d  edg e  detectio n  fro m  optica l  flow  fields,"   Ph.D .  dissertation ,  Universit y  o f  Edin ­
`burgh,  1980 . 
`Fig.  7. 7  courtes y  o f  Stev e  Barnar d  an d  Bil l  Thompson . 
`Figs.  7. 8  an d  7. 9  fro m  Rashid ,  1980 . 
`Fig.  7.1 0  courtes y  o f  Josep h  O'Rourke . 
`Figs.  7.1 1  an d  7.1 2  afte r  Aggarwa l  an d  Duda ,  1975 . 
`Fig.  7.1 3  courtes y  o f  Hans­Hellmu t  Nagel . 
`Fig.  8.I d  afte r  Requicha ,  1977 . 
`Figs.  8.2 ,  8.3 ,  8.21a ,  8.22 ,  an d  8.2 6  afte r  Pavlidis ,  1977 . 
`Figs.  8.10 ,  8.11 ,  9.6 ,  an d  9.1 6  courtes y  o f  Ur i  Shani . 
`Figs.  8.12 ,  8.13 ,  8.14 ,  8.15 ,  an d  8.1 6  fro m  Ballard ,  1981 . 
`Fig.  8.2 1  b   fro m  Preston ,  K. ,  Jr. ,  M.J.B .  Duff ;  S .  Levialdi ,  P.E .  Norgren ,  an d  J­i
`.  Toriwaki , 
`"Basics o f cellula r  logi c wit h  som e application s  i n  medica l  imag e  processing, "  Proc.   IEEE, 
`Vol.  67 ,  No .  5 ,  Ma y  1979 ,  pp .  826­856 . 
`Figs.  8.25 ,  9.8 ,  9.9 ,  9.10 ,  an d  11. 3  courtes y  o f  Rober t  Schudy . 
`Fig.  8.2 9  afte r  Bribiesc a  an d  Guzman ,  1979 . 
`Figs.  9.1 , 9.18 ,  9.19 ,  an d  9.2 7  courtes y  o f  Ar i  Requicha . 
`Fig.  9. 2  fro m  Requicha ,  A.A.G. ,  "Representation s  fo r  rigi d  solids :  theory ,  methods , 
`systems,"  Computer   Surveys   12,  4 ,  Decembe r  1980 . 
`Fig.  9. 3  courtes y  o f  Lydi a  Hrechanyk . 
`Figs.  9. 4  an d  9. 5  afte r  Baumgart ,  1972 . 
`Fig.  9. 7  courtes y  o f  Pete r  Selfridge . 
`Fig.  9.1 1  afte r  Requicha ,  1980 . 
`Figs. 9.1 4 an d  9.15 b  fro m  Agin , G.J .  an d  T.O .  Binford ,  "Compute r  descriptio n  o f curve d  ob ­
`jects,"  IEEE   Trans,   on   Computers   25,   1 ,  Apri l  1976 . 
`Fig.  9.15 a  courtes y  o f  Geral d  Agin . 
`Fig.  9.1 7  courtes y  o f  A .  Christensen ;  publishe d  a s  frontispiec e  o f  ACM   SIGGRAPH   80 
`Proceedings. 
`Fig.  9.2 0  fro m  Mar r  an d  Nishihara ,  1978 . 
`Fig.  9.2 1  afte r  Tilove ,  1980 . 
`Fig.  9.22 b  courtes y  o f  Gen e  Hartquist . 
`Figs.  9.24 ,  9.25 ,  an d  9.2 6  fro m  Le e  an d  Requicha ,  1980 . 
`Figs. 9.28a ,  9.29 ,  9.30 ,  9.31 , 9.32 , 9.35 , an d  9.3 7  an d  Tabl e  9. 1  fro m  Brown ,  C .  an d  R .  Pop ­
`plestone,  "Case s  i n scen e  analysis, "  i n  Pattern   Recognition,   ed .  B.G .  Batchelor .  New   York : 
`Plenum,  1978 . 
`Fig. 9.28 b fro m  Guzman , A. , "Decompositio n  o f a  visua l scen e int o three­dimensiona l  bodies, " 
`in  Automatic   Interpretation   and   Classification   of   Images,   A.   Grasseli ,  ed. ,  Ne w  York : 
`Academic  Press ,  1969 . 
`Fig.  9.28 c  fro m  Waltz ,  D. ,  "Understandin g  lin e  drawin g  o f  scene s  wit h  shadows, "  i n  The 
`Psychology  of   Computer   Vision,  ed .  P.H .  Winston .  New   York :  McGraw­Hill
`,  1975 . 
`Fig.  9.28 d  afte r  Turner ,  1974 . 
`Figs.  9.33 ,  9.38 ,  9.40 ,  9.42 ,  9.43 ,  an d  9.4 4  afte r  Mackworth ,  1973 . 
`
`Acknowledgments 
`
`xvii 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 16
`
`

`

`Figs.  9.39 ,  9.45 ,  9.46 ,  an d  9.4 7  an d  Tabl e  9. 2  afte r  Kanade ,  1978 . 
`Figs.  10. 2  an d  A2. 1  courtes y  o f  Dan a  Ballard . 
`Figs.  10.16 ,  10.17 ,  an d  10.1 8  afte r  Russell ,  1979 . 
`Fig.  11. 5  afte r  Fischle r  an d  Elschlager ,  1973 . 
`Fig.  11. 8  afte r  Amble r  e t  al. ,  1975 . 
`Fig.  11.1 0  fro m  Winston ,  P.H. ,  "Learnin g  structura l  description s  fro m  examples, "  i n  The 
`Psychology  of   Computer   Vision,   ed .  P.H .  Winston .  Ne w  York :  McGraw­Hill
`,  1975 . 
`Fig.  11.1 1  fro m  Nevatia ,  1974 . 
`Fig.  11.1 2  afte r  Nevatia ,  1974 . 
`Fig.  11.1 7  afte r  Barro w  an d  Popplestone ,  1971 . 
`Fig.  11.1 8  fro m  Davis ,  L.S. ,  "Shap e  matchin g  usin g  relaxatio n  techniques, "  IEEE   Trans. 
`PA MI   1,   4 ,  Januar y  1979 ,  pp .  60­72 . 
`Figs.  12. 4  an d  12. 5  fro m  Sloa n  an d  Bajcsy ,  1979 . 
`Fig.  12. 6  afte r  Barro w  an d  Tenenbaum ,  1976 . 
`Fig.  12. 8  afte r  Freuder .  1978 . 
`Fig.  12.1 0 fro m  Rosenfeld ,  A.R. , A . Hummel ,  an d S.W . Zucker , "Scen e labelin g b y  relaxatio n 
`operations,"  IEEE   Trans.   SMC   6,   6 , Jun e  1976 , p . 420 . 
`Figs.  12.11 ,  12.12 ,  12.13 ,  12.14 ,  an d  12.1 5  afte r  Hinton ,  1979 . 
`Fig.  13. 3  courtes y  o f  Aaro n  Sloman . 
`Figs.  13.6 ,  13.7 ,  an d  13. 8  fro m  Garvey ,  1976 . 
`Fig.  A  1.1 1  afte r  Dud a  an d  Hart ,  1973 . 
`Figs. A2. 2 an d  A2. 3 fro m  Hanson ,  A.R .  an d  E.M .  Riseman ,  "VISIONS : A  compute r  syste m 
`for  interpretin g  scenes, "  i n  Computer   Vision  Systems,   ed . A.R .  Hanso n  an d  E.M .  Riseman . 
`New  York :  Academi c  Press ,  1978 . 
`
`Acknowledgments 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 17
`
`

`

`Mnemonics 
`for  Proceeding s  an d  Specia l  Collection s 
`Cited  i n  th e  Reference s 
`
`CGIP 
`Computer  Graphics  and   Image   Processing 
`COMPSAC 
`IEEE Compute r  Society' s 3r d  Internationa l  Compute r Softwar e  an d Applica ­
`tions  Conference ,  Chicago ,  Novembe r  1979 . 
`
`cvs 
`
`Imag e  Understandin g 
`
`Hanson,  A .  R .  an d  E .  M .  Risema n  (Eds.) .  Computer  Vision   Systems.  Ne w 
`York:  Academi c  Press ,  1978 . 
`DARPA  I U 
`Defense  Advance d  Researc h  Project s  Agenc y 
`Workshop,  Minneapolis ,  MN ,  Apri l  1977 . 
`Defense  Advance d  Researc h  Project s  Agenc y 
`Workshop,  Pal o  Alto ,  CA ,  Octobe r  1977 . 
`Defense  Advance d  Researc h  Project s  Agenc y 
`Workshop,  Cambridge ,  MA ,  Ma y  1978 . 
`Imag e  Understandin g 
`Defense  Advance d  Researc h  Project s  Agenc y 
`Workshop,  Carnegie­Mello n  University ,  Pittsburgh ,  PA ,  Novembe r  1978 . 
`Defense  Advance d  Researc h  Project s  Agenc y 
`Imag e  Understandin g 
`Workshop,  Universit y  o f  Maryland ,  Colleg e  Park ,  MD ,  Apri l  1980 . 
`IJCAI 
`2nd  Internationa l  Join t  Conferenc e  o n  Artificia l  Intelligence ,  Imperia l 
`College,  London ,  Se