`
`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
`
`PRENTICEHALL,
`
`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 013165316
`
`621.38'04I 4
`4
`
`812097 4
`AACR 2
`
`Cover desig n b y Robi n Breit e
`
`, Inc .
`© 198 2 b y PrenticeHall
`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 D13XtS31b M
`
`PRENTICEHAL L INTERNATIONAL , INC. , London
`PRENTICEHAL L O F AUSTRALI A PTY . LIMITED , Sydney
`PRENTICEHAL L O F CANADA , LTD. , Toronto
`PRENTICEHAL L O F INDI A PRIVAT E LIMITED , New Delhi
`PRENTICEHAL L O F JAPAN , INC. , Tokyo
`PRENTICEHAL 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 HighLeve l an d LowLeve 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 ThreeDimensiona 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 GrayLeve 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 NonLinea r Correlatio n i n Edg e Space , 12 1
`4.2.3 DivideandConque
`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 GrayLeve l Images , 14 4
`4.6.2 Generalizatio n t o HigherDimensiona 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 StateSpac e Approac h t o Regio n Growing , 15 7
`5.4.2 LowLeve l Boundar y Dat a Structures , 15 8
`5.4.3 GraphOriente 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 GrayLeve 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 DomainIndependen t Understanding , 19 6
`7.1.2 DomainDependen 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
`DomainIndependen 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 TWODIMENSIONA L
`GEOMETRIC STRUCTURE S
`8.1 TwoDimensiona 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 tyj
` Curve , 23 7
`8.2.4 Fourie r Descriptors , 23 8
`8.2.5 Coni c Sections , 23 9
`8.2.6 BSplines , 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 THREEDIMENSIONA 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 ThreeDimensiona 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 GraphTheoreti c Algorithm s
`11.2.1 Th e Algorithms , 35 7
`11.2.2 Complexity , 35 9
`Implementin g GraphTheoreti 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
`FirstOrde r Predicat e Calculu s
`12.1.1 ClauseFor 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 HOWT O an d SOWHA 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 LeastSquaredErro r Fittin g
`A1.9.1 PseudoInvers 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 PseudoInvers e Method ,
`487
`48 8
`A 1.1 0 Conie s
`48 9
`A 1.1 1
`Interpolatio n
`, 48 9
`Al.11.1 OneDimensional
`A 1.11. 2 TwoDimensional
`, 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 CoRoutining , 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 PatternDirecte 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 informationprocessin 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 imagetoimag 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 threedimensiona 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 domaindependent
`, 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 fastgrowin 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/graduateleve 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 imagelik 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 fastdevelopin 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 engineeringtoEnglis 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 784
`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 N0001478C0164
`.
`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 chapteren d references .
`
`Fig. 1. 2 fro m Shani , U. , " A 3 D modeldrive 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 . 324331 .
`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 . 283287 . © 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 . 104119 .
`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 . 81103 .
`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 . 125140 .
`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 . 303330 .
`
`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 . 391398 . © 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 HansHellmu 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 Ji
`. 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 . 826856 .
`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 threedimensiona 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 : McGrawHill
`, 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 : McGrawHill
`, 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 . 6072 .
`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, CarnegieMello 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