SLANT FROM TEXTURE: Computational methods for recovering surface slant from images of textured scenes by Heinz Breu B.Sc, University of British Columbia, 1978 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Department of Computer Science) We accept this thesis as conforming to the required standard The University of British Columbia March, 1980 Heinz Breu, 1980 In p r e s e n t i n g this an a d v a n c e d degree the L i b r a r y shall I further for agree thesis at make it this extensive i s understood Gcitncs„ Columbia requirements reference copying of that copying not permission. / oywpv "e(Z the I agree and this or for that study. thesis by t h e Head o f my D e p a r t m e n t f i n a n c i a l gain shall The U n i v e r s i t y o f B r i t i s h 2075 Wesbrook P l a c e V a n c o u v e r , Canada V6T 1W5 I E It of B r i t i s h Columbia, available for that permission for thesis for Department of B P 75-51 freely of s c h o l a r l y p u r p o s e s may be g r a n t e d written DE-6 fulfilment the U n i v e r s i t y by h i s r e p r e s e n t a t i v e s . of in partial or publication be a l l o w e d w i t h o u t my ii Abstract This thesis examines the problem of computationally determining the slant of a Images are restricted to those orthographic surface of from planar recovering or an image of that surface. surfaces produced by projection. This thesis is concerned only with those cues obtainable from the image texture. These cues arise primarily due to the foreshortening property of orthographic projection. Texture measures have typically been partitioned into three classes: statistical approaches, micro-structural approaches, and macrostructural approaches. classes are orientation. and, indeed, texture. used to In this thesis, measures develop algorithms from each of these capable of detecting surface It i s concluded that these three classes are not distinct are a r t i f i c i a l l y rendered by the prevailing definition of A new definition involving nested structures is suggested. Acknowledgements I would like to thank my suggestions which I have advisor incorporated Alan Mackworth in this for his many thesis and for his friendly guidance when my work seemed to be at an impasse. also to my wife Wendy for a l l her support while I was in school and especially for her extensive help in the production of the final of this thesis. Thanks copy iv Table of Contents 1. INTRODUCTION 1 1.0. PHYSICAL ASSUMPTIONS 1 1.1. 2 DEFINITIONS Texture 2 Surface Slant 3 1.2. MOTIVATION 4 1.3. THESIS OUTLINE 9 1.5. READING PATHS 10 2. RELATED RESEARCH 12 2.1. THE DEFINITION OF TEXTURE 12 2.2. APPROACHES TO TEXTURE MEASURES 14 Gray-level Statistics 14 Structural Analysis 18 Frequency Domain 19 Hough Transforms 20 2.3. APPLICATIONS 31 Discrimination 31 Surface Slant 32 Depth Cue 33 2.4. 3. '. SUMMARY 34 APPROACHES TO COMPUTATIONAL DETERMINATION OF SURFACE SLANT FROM TEXTURE MEASURES 35 3.1. 35 INTRODUCTION Theorem 3.1.1: The Foreshortening Projection Effect of Orthographic 39 V 3.2. STATISTICAL APPROACHES 42 Regular Dots 42 Circles 43 Other Micro-structures 49 Uniform Dots 49 Theorem 3.2.1: The Non-directionality of Random Textures ....52 Conclusions 3.3. STRUCTURAL APPROACHES: THE MICRO-STRUCTURE 53 54 The Single Surface 56 One Diagonal 56 Theorem 3.3.1: a S.l.d. is a U.i.l 61 One or More Diagonals 63 Theorem 3.3.2: Effect of more than one S.l.d 65 Single Surface Results 70 More Than One Surface 70 Details of the Implementation 90 Conclusions 93 3.4. STRUCTURAL APPROACHES: THE MACRO-STRUCTURE 94 "Grid-like" Textures 94 Results 106 4. AN INTERPRETATION OF THE RESULTS 4.1. SUMMARY 4.2. FALLACIES, OR WHY 3.2, 3.3, AND 3.4 ALL START WITH 3 112 112 113 The Fallacy of the Statistical-Structural Dichotomy 113 The Fallacy of the Micro/Macro-Structure Dichotomy 114 vi 5. CONCLUSION 5.1. DIRECTIONS FOR FURTHER RESEARCH 117 119 Extensions 119 Formalize the Definition 121 Application to the Origami World 121 5.2. SYNOPSIS 6. APPENDICES 6.1. APPENDIX TO 2.2 Derivation of the Rho-theta Equation of a Line 6.2. APPENDIX TO 3.3 Least Squares F i t of Data to An Ellipse 6.3. APPENDIX TO 3.4 124 125 125 125 127 127 130 Orientation of a Surface from True Shape and Projected Shape 130 Bibliography 133 vii Table of Figures Figure f1.1.1: Picture and Gradient of a Line 5 Figure f1.2.1: Labellings of a "cube" 7 Figure fl.2.2: Gradients of Figure fl.2.1 8 Figure f2.2.1: Divided Squares 15 Figure f2.2.2: Checkerboard 15 Figure f2.2.3: Virtual Line 17 Figure f2.2.4: "Mesh-like" Textures 21 Figure f2.2.5: Rho-theta Parametrization of a Line 23 Figure f2.2.6: Hough Transform of "City Streets" 24 Figure 12.2.1\ 27 Polar Plot of Hough Transform of "City Streets" Figure f2.2.8: Derivation of T 29 Figure f3.3.1: Orthographic Projection of a Line 36 Figure f3.1.2: Surface Slant Notation 38 Figure f3.1.3: Figure for theorem 3.1.1 40 Figure f3.2.1: Examples of Deltas 44 Figure f3.2.2: Second Order Statistics of a Circle 46 Figure f3.2.3: Intercircle Deltas 47 Figure f3.2.4: Digitization of a Circle 48 Figure f3.2.5: Effect of Rotation on Co-occurrence Matrices 50 Figure f3.2.6: Effect of Rotation on Inter-texel Distances 51 Figure f3.3.1: "Cube" Textured with Squares 55 Figure f3.3.2: Tilted Surface Textured with Line Segments 57 Figure f3.3.2: Polar Plot of L-0-list Taken of Figure f3.3.2 59 Figure f3.3.4: Examples of Micro-structures Sufficiently Long Diagonal with Exactly One 62 viii Figure f3.3.5: Examples of Micro-structures Containing One Or More Sufficiently Long Diagonals 64 Figure f3.3.6: Figure for theorem f3.3.2 66 Figure f3.3.7: Tilted Surface Textured with Squares 68 Figure f3.3.8: Polar-plot of L-6-list Taken of Figure f3.3.7 69 Figure f3.3.9: "Cube" Textured with Line Segments 73 Figure f3.3.10: Polar of the L-6-list Taken of Figure f3.3.9 74 Figure f3.3.11: Ellipse Detected for Noisy Points 77 Figure f3.3.12: Iyy v.s. I 81 x v Taken of Figure f3.3.1 Figure f3.3.13: Application of the Clustering Algorithm Figure f3.3.14: Flow of Control 82 of the Micro-structural Analysis Algorithm 91 Figure f3.3.15: Data Structures for the Micro-structural Analysis Algorithm 92 Figure f3.4.1: "Complete" Grid Texture 95 Figure f3.4.2: "Line-segments" Grid Texture 96 Figure f3.4.3: "Boxes" Grid Texture 97 Figure f3.4.4: The Relationship Between Lj and dj 100 Figure f3.4.5: Illustration of p^and ^2 Figure f3.4.6: Slanted Surface Textured with "boxes" Grid 104 Figure f3.4.7: Polar Plot of Hough Transform of Figure f3.4.6 105 Figure f3.4.8: Flow of Control for the Macro-structural Analysis Algorithm Figure f3.4.9: Data Structures for 108 the Macro-structural Algorithm Analysis 109 Figure f4.2.1: Hierarchical Texture I 115 Figure f4.2.2: Hierarchical Texture II 117 Figure f5.1.1: "Cube" Labelling and Gradients 122 ix Figure f5.1.2: Two "possible" Gradient Configurations f5.1.1 Figure f6.1.1: Rho-theta Equation of a Line of Figure 123 126 Figure f6.3.1: "Squashing" Effect of the Orthographic Projection ..131 1 1. INTRODUCTION "There is more to seeing a pikestaff than is commonly believed ..." (Boden, *77) This thesis is about deducing certain properties of a scene from an image of that scene. These properties are the orientations of the surfaces making up the scene and the deduction of these properties is made on the basis of knowledge about the texture present in the image. 1.0 PHYSICAL ASSUMPTIONS In order to study how perceived texture can enable construction of the scene, the properties and the events to be must be isolated. simplify the world. outline One way of accomplishing The following assumptions and our simplification. this a re- analysed isolation is to restrictions, then, They w i l l be mentioned again in the thesis as they become appropriate. 1) A l l surfaces are planar. 2) A l l images are produced by an orthographic projection. 3) The scenes contain only continuous surfaces. 4) Some preprocessing of the image w i l l always be assumed. The nature of this preprocessing will be mentioned when required. 5) "Nearby" regions of the image that have "similar" textures are really the same region. The term, "similar", will be defined when i t i s needed. The term, "nearby", i s not defined nor i s i t used by us. This assumption is made largely to allow the following assumption. 6) The images are segmentable into regions, each of which corresponds to a unique surface of the scene. In most cases, we w i l l assume that this segmentation has taken place. 7) Assumptions w i l l be made throughout the thesis as to the nature of the actual texture. So assumptions 1) - 3) simplify the physical "reality", 4) - 6) ? represent work already done which we assume and may c a l l upon, and 7) is our major heuristic, for, without 7), any given image could have been produced from an infinite number of scenes. 1.1 DEFINITIONS This thesis, then, confronts the task of recovering three- dimensional scene information (namely, surface slant) using texture as a cue from a two-dimensional image produced by an orthographic of the scene. To proceed, projection the terms "texture" and "surface slant" require clarification. Texture Texture certainly deserves to be a nebulous concept (there is a pun in there somewhere) and no definition to date has made i t very Texture clear. in an image normally consists of intensity variations in the image over space. These variations may be produced by two distinct means: 1) Variations in albedo. 2) Variations in the surface normal. This thesis assumes the former. This assumption is made as a further simplification of the world, for i t i s now the case that perceived texture does not depend on the position of the scene's light source(s). The variations in albedo and the surface markings are referred to 3 as the actual or scene texture and the variations in the image's intensity as the apparent or image texture. further in Chapters texture as being elements, each 2 and 4. This will be discussed For now, i t is sufficient to think of a large number of of which is small similar (visible) patterns or relative to the textured surface, arranged over the surface according to some set of placement rules. Note that the apparent texture then depends on the scale of the image since different things w i l l become the basic elements as the scale varies. For example, wheat fields viewed aerially from one kilometer have a definite apparent fields viewed from texture quite distinct six centimeters. Image associated with scale, resolution decreasing ratio. from the same wheat resolution is often with the image-to-scene Some A r t i f i c i a l Intelligence paradigms (Kelly, 1971) (Tanimoto and Pavlidis, 1975) vary resolution with the level of attention . Hence the apparent determination texture also depends on of what the constitutes the level basic of attention. The elements for any given textured image is quite d i f f i c u l t and we will largely assume that this has been done for us i f we need i t (assumption 4). It is f e l t that this determination problem is one created by an texture. insufficient definition of This opinion i s discussed in Chapter 4.2. Surface Slant Fortunately, concrete. 1971) the definition of "surface slant" is somewhat more We w i l l generally talk about the (Mackworth, 1973) of gradient vector (Huffman, a surface or minor variations of i t . The gradient, (p,q), of a line in a scene i s a vector "whose direction is in 4 the direction of the picture line and whose length is the tangent of the angle the scene line makes with the picture plane." See Figure fl.1.1, gradient a of from surface (Mackworth, is the 1976). (Mackworth, 1976). We will direction length as 0 . of this that the gradient of the set of parallel lines having the steepest inclination to the picture plane. the say gradient We will refer to vector as o and to the arctan of i t s The cartesian co-ordinates, (p,q), and these angles are related by the following equations: p = tanjzJ cosa q = tanjzJ sincr In most cases, we will find i t more convenient to determine a and than to compute the cartesian co-ordinates of the gradient directly as Kender (see Chapter 2.2) does. We will also c a l l slant and a the direction of the amount of slant . 1.2 MOTIVATION It i s not within the scope of this thesis to give motivations for recovering 3-D scenes from 2-D assumed. But why study images, texture and so such motivations will be surface slant? We w i l l use an application to illustrate our motives. The origami world is a model of the visual world where surfaces, which may stand alone, (Kanade, 1978) are the basic elements rather than polyhedra. objects That i s , the origami world includes as a subset studied by the solid- (Huffman, 1971), (Clowes, 1971), (Waltz, 1972) and (Mackworth, 1973) but allows other objects as well. The origami world is (a) A p i c t u r e of an edge. .. picture and gradient of a line Figure f1.1.1 > 6 defined on line-drawings and an object i s "understood" by assigning one of four l a b e l s , + (convex edge), - (concave edge) and, <-, and -> (occluding edge) to each l i n e i n the image of the object. Kanade's system y i e l d s the 3 (up to rotation) l a b e l l i n g s shown i n Figure f l . 2 . 1 f o r the l i n e drawing shown. We can think of a) as a cubel i k e c o n f i g u r a t i o n , b) as a concave corner and c) as a "roof" placed on a plane. Kanade uses edge p r o f i l e s to determine which l a b e l l i n g i s " c o r r e c t " for a given image, but l e t us see how texture can help us here. f i r s t note that the gradients of the surfaces f o r Figure f l . 2 . 1 Let us a), b) and c) are r e l a t e d as shown i n Figure f l . 2 . 2 a ) , b) and c) r e s p e c t i v e l y . Suppose that a l l the surfaces have been textured and on t h i s basis we have determined the gradient vector of each surface ( i t i s the of t h i s t h e s i s to demonstrate that t h i s can be done). will purpose Then our f i n d i n g s e a s i l y d i s t i n g u i s h between Figures f l . 2 . 1 a) and c ) , f o r example. Note that we w i l l not be able to d i s t i n g u i s h f i g u r e s f l . 2 . 1 a) and b) on t h i s b a s i s since texture cues w i l l only y i e l d the surface o r i e n t a t i o n to w i t h i n Necker r e v e r s a l , that i s , texture w i l l give us two gradients f o r any given surface, the " r e a l " gradient and i t s negative or reflection about the o r i g i n . Note that textures are easily whereas i n t e n s i t y p r o f i l e s are not. return carried Hence, over into l i n e drawings i t i s not necessary to to the o r i g i n a l image, which may be a photograph f o r example, to determine surface s l a n t from texture. photograph profiles. This i s e s p e c i a l l y u s e f u l i f the i s not of s u f f i c i e n t r e s o l u t i o n to allow u t i l i z a t i o n of edge 7 1A a) A b) q /\ c) gradients of Figure f1.2.1 Figure fl.2.2 9 1.3 THESIS OUTLINE I t i s proposed, determination of then, that surface texture slant from is a useful orthographic cue f o r the images. d i f f e r e n t "kinds" o f textures w i l l be examined and d i f f e r e n t w i l l be used to analyse them. Three techniques Programs w i l l be implemented to determine surface s l a n t f o r two of these texture c l a s s e s . Let us now give a summary o f the t h e s i s by chapter. Chapter 1 This thesis. 1.2 Introduction chapter opens Section 1.1 discusses concepts c r u c i a l to t h i s discusses of t h i s work. Chapter 2 Related Work are discussed the Section Section 1.3 gives an o u t l i n e o f the t h e s i s . here historical attempts at defining Fourier texture. mainly as references to l a t e r d i s c u s s i o n s . Section 2.2 introduces the main texture measures used. but work. our motivation with an example o f a p o s s i b l e a p p l i c a t i o n Section 2.1 presents These by presenting the major assumptions made t h i s transform i n our work. We w i l l use Section 2.3 a p p l i c a t i o n s o f these measures that lend credence to assumption demonstrating texture all presents 6) by d i s c r i m i n a t i o n . Also discussed i s previous work on surface s l a n t d e t e c t i o n and depth cues. in Chapter 3 The S o l u t i o n Section important process. 3.1 defines theorem about surface the p r o j e c t i o n " and of use texture of proves proves under an t h i s imaging statistical measures for a theorem i n d i c a t i n g the Section 3.3 undertakes a structural analysis texture's "basic element" and presents an implemented algorithm for detecting surface transform nature o r i e n t a t i o n and l i m i t s of t h i s approach. the the Section 3.2 examines determining of "orthographic to slant. analyse the Section texture's 3.4 makes use of macro-structure. the Hough Again, an implemented algorithm i s presented. Chapter 4 An I n t e r p r e t a t i o n of the Results Section 4.1 summarizes the r e s u l t s of Chapter 3. Section 4.2 then examines a common myth about textures i n l i g h t of these r e s u l t s . Chapter 5 This Conclusions chapter gives a b r i e f summary of what has been accomplished. Several d i r e c t i o n s f o r f u r t h e r study are proposed. 1.5 READING PATHS This t h e s i s w i l l , n a t u r a l l y , be of d i f f e r e n t i n t e r e s t to readers. So, l e t us sketch a few "paths" through the t h e s i s . different 11 D e f i n i t i o n of Texture If the reader i s i n t e r e s t e d i n knowing only what we think texture i s , much of the work we have done may be glossed over. Sections 1.1 But read to get acquainted with texture. 2.1 to get a h i s t o r i c a l perspective. 3.1 to understand the imaging process. 4 and the conclusions to 3.2, 3.3 and 3.4 to get our opinions on texture. 5 the f i r s t p a r t , to get our conclusions. S t a t i s t i c a l Approaches Read 1.1, 2.2, 3.2, 4.1, 4.2, 5. M i c r o - s t r u c t u r a l Approaches 1.1, 2.3, 3.3, 4.1, 4.2, 5. Macro-structural Approaches 1.1, 2.4, The advised 3.4, 4.1, 4.2, reader to at endeavour, may interested least browse 5. in working with texture i n any context i s through the entire I wish the reader f r u i t f u l s t u d i e s . thesis. In this 12 2. RELATED RESEARCH 2.1 THE DEFINITION OF TEXTURE Everyone i s familiar with able t o define i t adequately. people. v i s u a l texture but no one seems to be Texture i s d i f f e r e n t things to d i f f e r e n t C e r t a i n l y , texture depends on one's point o f view, o r l e v e l o f a t t e n t i o n , as was pointed out i n the previous reasonable, however, to define chapter. I t appears what one i s working w i t h , and several stabs have been made at i t . The lack o f successful d e f i n i t i o n s i s due l a r g e l y t o the p r a c t i c e of viewing textured surfaces surface and t o the confusion composed caused the p i c t u r e plane p a r a l l e l to the by considering of micro-structures and macro-structures. i s discussed i n chapter 4. of with texture This l a t t e r problem The former r e s u l t s i n a conceptual the d i s t i n c t i o n between scene and image. gray-tones, a r r a y s ) . however, the question terminology q u i c k l y a r i s e . o f the image Such d e f i n i t i o n s are acceptable only so long as f r o n t o - p a r a l l e l views are maintained. non-zero, blurring That i s , d e f i n i t i o n s have been proposed which describe the a c t u a l texture i n terms (regions, I f the surface slant i s of texture i d e n t i t y and problems i n The image-based d e f i n i t i o n s would say that a n o n - t i l t e d surface and a t i l t e d surface have d i f f e r e n t textures. is no way, There i n such a d e f i n i t i o n , of expressing the notion of the same actual or surface t e x t u r e . would t o be say that Our own d e f i n i t i o n i s scene based, hence we the slanted surface has the same a c t u a l texture as the unslanted surface. apparent texture We would i s present. agree, of course, that a different I t should be r e a l i z e d that a l l o f the f o l l o w i n g researchers have proposed image-based d e f i n i t i o n s . 13 In an e x c e l l e n t review of the r o l e of texture i n object perception, Pickett defines variations" visual textures ( P i c k e t t , 1970). A to be "two-dimensional which i s small relative of more e x p l i c i t d e f i n i t i o n , "texture i s composed of l a r g e numbers of s i m i l a r 'basic elements' or of arrays 'pieces' each to the s i z e of the textured region", i s proposed i n (Rosenfeld, Lee, and Thomas, 1970). H a r a l i c k e t a l f e e l that "texture i s concerned with the s p a t i a l gray tones" Along (statistical) these l i n e s , Zucker has proposed a general model f o r texture This model i s based on a Chomsky-style grammar. proposes an "alphabet" o f micro-structures. arranged (syntax). component) of (Haralick, Shanmugan and D i n s t e i n , 1973). (Zucker, 1976). then distribution on a surface according These micro-structures to a the f i n a l texture. are s e t of placement r u l e s The r e s u l t i s then d i s t o r t e d i n some way to y i e l d Zucker (transformational I t should be noted that the placement r u l e s are chosen to y i e l d p e r i o d i c s t r u c t u r e s . I t i s often f e l t that a s u i t a b l e d e s c r i p t i o n of a which will enable the re-generation texture of that texture. i s one Rosenfeld and L i p k i n have developed a system allowing texture synthesis (Rosenfeld and L i p k i n , 1970). The required texture d e s c r i p t i o n i s a l s o i n the form of (1) the nature o f the micro-structures and (2) the appropriate placement rules. 14 2.2 APPROACHES TO TEXTURE MEASURES Gray-level S t a t i s t i c s Gray-level statistics can be general, i t h order s t a t i s t i c s . p i x e l s or points considered So, 1 order s t classified into 1 s t , 2 & or, i n n The order corresponds to the number o f i n inter-relation. s t a t i s t i c s include g r a y - l e v e l average and variance (Hawkins, 1970) f o r example. depend on the i n d i v i d u a l g r a y - l e v e l values only and not on t h e i r arrangement. Nothing can be deduced statistics. about Note that these micro-structure values size or shape from 1 s t order For example, f i g u r e s f2.2.1 and f2.2.2 below y i e l d the same average and variance values. In f a c t , a l l f i r s t order s t a t i s t i c s are i n v a r i a n t under any p i x e l permutation. 2 n d order p i x e l s or dots. statistics characterize These may be viewed as inter-relations of pairs of "dipole statistics" or the p r o b a b i l i t i e s o f "needles" of f i x e d length and o r i e n t a t i o n thrown on the image having given gray-level conjectured by J u l e s z differences are necessary discrimination. statistics values at their (Julesz, 1973) that 2 n d That i s , a p a i r of textures may order statistical differ and y e t not be d i s c r i m i n a b l e by humans. discriminable exhibited I t has been but not s u f f i c i e n t f o r human v i s u a l texture himself has produced counter-examples t o h i s o r i g i n a l is, tips. textures with identical ( C a e l l i and J u l e s z , 1977). model (and conjecture) by introducing 2 n d in 2 n d order However, J u l e s z conjecture; that order s t a t i s t i c s were J u l e s z modified h i s psychological pseudo-colinearity detectors that 15 Checkerboard Figure f2.2.2 16 come i n t o p l a y only when 2 ^ order s t a t i s t i c s are i d e n t i c a l . modified by considering only those d i p o l e s nc t h i s procedure Schatz connecting endpoints of r e a l or l o c a l " v i r t u a l " l i n e s (Schatz, 1978). An example o f a local virtual line statistics, i s the dotted l i n e i n f i g u r e f.2.2.3. do y i e l d i d e n t i c a l 2 3 order s t a t i s t i c s human discrimination. closer to preprocessed Hence, providing discrimination. values f o r some p a i r s of textures where are d i f f e r e n t . n< a Schatz's Schatz's These textures are not subject to Schatz feels sufficient method that condition assumes that h i s method f o r human the image t o y i e l d " l i n e drawings" or "primal sketches" Of course, Schatz assumes that the o r i g i n a l image i s so comes texture has been (Marr, 1976). preprocessable. This i s not always the case, as with texture elements composed of curved l i n e s o r dots only. 2 3 n< order In these cases, a l l l i n e s are v i r t u a l l i n e s . statistics are computed "gray-tone spatial-dependence" Shanmugan and D i n s t e i n , 1973). displacement or co-occurrence Consider d' =(D ,D ) defined on i t . X by H a r a l i c k with the help of V matrices a digitized (Haralick, image Then the co-occurrence and a matrix Pcj i s defined such that Pcj(i,j) = p r o b a b i l i t y that a point with g r a y - l e v e l j occurs displacement o from a point with g r a y - l e v e l i Haralick from defines these 14 d i f f e r e n t texture s t a t i s t i c s that may be computed matrices interpretations and suggests since possible psycho-physical f o r some o f them (e.g., "coarseness", that the displacements, cj, correspond that at a i s fixed to Julesz's "entropy"). dipoles. Note Note also i n o r i e n t a t i o n , such matrices can be used t o measure t e x t u r a l features i n a given d i r e c t i o n . This i s u s e f u l f o r our work i n detecting surface s l a n t and a l s o f o r detecting d i r e c t i o n a l i t y i n a texture. In f a c t , we will examine "blind" application of this 17 Virtual line f i g u r e f2.2.3 18 technique i n chapter 3.2. More t o the point i s our use o f d i p o l e s i n chapter 3.2 (called "diagonals" i n that chapter). Our d e t e c t i o n o f these d i p o l e s , however, i s implemented by a s t r u c t u r a l a n a l y s i s . This type o f a n a l y s i s i s developed next. Structural Analysis (Tomita detection. clearly e t a l , 1973) have used structural The assumptions made here are that the image i s made outlined A t n order s e t o f these moments (see pgs. 78 to 79 f o r M j j , are chosen as shape d e s c r i p t o r s , p a r t i a l l y f o r t h e i r resistance t o such noise. discrimination here, This process, while Nevertheless, used only f o r texture would be u s e f u l to our task as we could determine how the atomic elements have slant. homogeneous c e r t a i n l e v e l o f noise (input i s v i a a TV camera) i s a l s o assumed and a set of i j definitions), up o f atomic elements (such as c i r c l e s or squares) and that each region t o be detected i s made up o f a elements. a n a l y s i s f o r region we been will deformed by the apparent surface not use them i n t h i s context, but f o r region d e t e c t i o n only (see Chapter 3.3). Hawkins describes the use of l o c a l "matched discrimination (Hawkins, 1970). This filters" i s a s t r u c t u r a l approach i n the sense that s t r u c t u r e s or shapes (such as edges, l i n e s being searched for, and wedges) are but no attempt i s made t o i s o l a t e p o s s i b l e micro- s t r u c t u r e s or t o describe t h e i r shapes. measures f o r texture As Hawkins points are i n s e n s i t i v e t o too many image p r o p e r t i e s . o u t , these In p a r t i c u l a r , they are i n s e n s i t i v e t o changes due t o surface s l a n t since no new edges r e s u l t from t i l t i n g the surface. Schatz's work may a l s o be construed as s t r u c t u r a l . He assumes that 19 a l l r e a l l i n e s i n the image have already been found. lines are constructed "local". between As well, virtual r e a l l i n e terminators with a notion of However, Schatz only looks a t the o v e r a l l s t a t i s t i c s of these l i n e s rather than t h e i r s t r u c t u r a l p r o p e r t i e s . Frequency Domain Consider integers a d i g i t a l image i n matrix form, g ( x , y ) , where x and y are over the domain (0...k). The image's d i s c r e t e Fourier transform i s given by k-1 k-1 F(n,m) = (1/k ) J 1 g(x,y)e-( P ) [( x=0 y=0 x n + The by P(n,m) = |F(n,m)|. The power 2 power 2 spectrum of F i i i s given y )A] m spectrum i s i n v a r i a n t with respect to t r a n s l a t i o n i n the s p a t i a l but not with respect t o r o t a t i o n . Hawkins points out that textures may d i f f e r only i n t h e i r phase r e l a t i o n s h i p s and yet appear (Hawkins 1970), descriptors. sensitivity transformed Then indicating a However, Bajcsy (Bajcsy, 1972,1973) uses the from c a r t e s i a n coordinates direction 0 very different shortcoming of power spectra as texture of power spectra to some advantage. f o r each domain and to polar directional The power spectrum i s coordinates, P(r,#). f o r each frequency r we have the one dimensional functions P ( r ) and P (jrf) r e s p e c t i v e l y . She then defines 0 k P(r) = 25Ptf(r) jz>=0 Q(&) = w/2 ZPr(^) r=l r and where w i s the window s i z e the b a s i s f o r her texture d e s c r i p t o r s i s then the p a i r <P(r),Q(0)>. 20 Bajcsy defines many d e s c r i p t o r s from t h i s p a i r . For t h e i r d e f i n i t i o n and f u r t h e r d e t a i l s of the above see (Bajcsy, 1972,1973). Textural features derived from the Fourier domain have to give poorer results been found than s t a t i s t i c a l features i n some comparative studies (Dyer, Weszka and Rosenfeld, 1975a, 1975b, 1975c). It has been suggested (Rosenfeld,1975) that t h i s may be due to "edge e f f e c t s " of the discrete Fourier transform. Some work has been done using r e f l e c t e d patterns to minimize t h i s problem (Dyer and Rosenfeld, 1975). The Fourier-based directional approach may be features show up s t r o n g l y . useful for our work since However, s t r u c t u r a l information i s disguised by the transform, yet t h i s i s q u i t e important information, as we have seen i n the previous chapter. The Fourier a n a l y s i s presented transform could i n Chapter 3.4. be used in the macro-structural Nevertheless, we found the rho-theta Hough transform i n t u i t i v e l y more transparent f o r t h i s a p p l i c a t i o n . This transform i s developed h i s t o r i c a l l y i n the f o l l o w i n g s e c t i o n . Hough Transforms The problem of detecting surface s l a n t from the perspective p r o j e c t i o n case has been texture (true shape) to be one-dimensional and l i n e - l i k e ; they are arranged regular mesh-like fashion." in tackled by (Kender,1979). Consider the s p e c i a l case where the micro-structures "restricted gradients Examples of such textures appear i n are in a Figure f2.2.4 below. Kender enlisted help from the techniques of a r e l a t e d d i s c i p l i n e , that of l i n e d e t e c t i o n i n images. To see how Kender uses t h i s technique 21 22 to some advantage, i t may be useful to set the stage by quickly f o r d e t e c t i n g l i n e s i n an image was f i r s t proposed reviewing the technique's development. This procedure by (Hough,1962) and i s now commonly referred to Transforms. Basically, as the i t involves transforming use each pattern i n t o a l i n e i n a parameter space, i n Hough's case, intercept space. Hough point i n the into slope- The f i r s t r e a l l y useful development occurred several years l a t e r (Duda and Hart,1972). as of Here, angle-radius (also referred theta-rho or rho-theta) space i s used. to At t h i s stage, a c l o s e r look i s warranted. Duda and Hart decided to use normal parameterization. Referring to Figure f2.2.5 f o r the d e t a i l s of the parameters, we note that a s t r a i g h t l i n e can be expressed as xcos(0) + ysin(O) = rho After (see the Appendix to 2.2 f o r derivation) correlating their digitized image with a differencing operator (a way of d e t e c t i n g i n t e n s i t y changes), Duda and Hart then each map f i g u r e p o i n t ( x ^ y ^ ) to the s i n u s o i d a l curve i n (quantized) t h e t a - rho space: rho = XJCOS(0) + yjSin(G) each c e l l i n the space being augmented by 1 every time i t i s "written" into. Since c o l l i n e a r points i n the image map into l i n e s i n t e r s e c t i n g at a point corresponding to the l i n e they a l l l i e on, accumulation line. (detected by histogramming) p o i n t s of maximal each correspond to a detected Figure f2.2.6 below i s the theta-rho Hough transform of the " c i t y s t r e e t s " of Figure f2.2.4. Rho-theta parameterization of a line Figure f2.2.5 TT_ X Hough transform of "city streets" Figure f2.2.6 25 The next major step was made by (O'Gorman and Clowes,1973). Following a suggestion by A.K. Mackworth and J . F r a n c i s , they decided t o make use o f l o c a l evidence t o determine uniquely the value of ©. In e f f e c t , they considered each p i x e l i n the image to be an "edgel" (having direction and p o s i t i o n accomplished. but no length). Let us see how We can estimate the i n t e n s i t y gradient this i s G=(DX ,DY ) at XV XV each point (x,y) by c o r r e l a t i n g the image with the mask -1/6 0 1 +1/6 -1/6 0 1 +1/6 -1/6 0 1 +1/6 to o b t a i n D X YV and with the mask +1/6 +1/6 +1/6 0 0 0 -1/6 -1/6 -1/6 to o b t a i n DY . XV That i s , f o r every point (x,y): DX XV DY xy +1 +1 = 1 / 6 ( T I(x+l,y+i) - 2 I ( x - l , y + i ) ) i=-l i=-l +1 +1 = 1 / 6 ( 2 I(x+i,y+l) - 2 I ( x + i , y - l ) i=-l i=-l where I(x,y) i s the value o f the image's i n t e n s i t y array a t point (x,y). Now we can approximate (tan(0) = DY y/DX ) for each "edgel" since the X xv ?6 i n t e n s i t y gradient i s g e n e r a l l y perpendicular to the p i c t u r e for each rho and edge. "edgel" we can increment a unique histogram bucket indexed by ©. Having developed the necessary t o o l s , we are f i n a l l y ready to at Render's work with texture. look Kender used the observation that true p a r a l l e l l i n e s i n a perspective image converge to a vanishing point points) to note that such l i n e s would map i n t o points i n the parameter space l y i n g on the sine-curve corresponding point. Sinusoidal curves being rather theta-rho transform i n polar coordinates. parallel (or theta-rho vanishing to detect, Kender plot the The c i t y s t r e e t s example of (Figure l i n e s i n the image now map s t r a i g h t l i n e going through the o r i g i n and the The f i r s t i s to Figure f2.2.4 i s p l o t t e d below i n t h i s space that to difficult proposed two m o d i f i c a t i o n s to the transform. noted So f2.2.7). Kender into points l y i n g on a converging lines map into points on a c i r c l e through the o r i g i n . It should corresponding distance be noted at t h i s stage that the distance between points to p a r a l l e l ( i n the image) l i n e s i s p r e c i s e l y between these lines in the image. This the normal feature w i l l be examined i n Section 3.4 of the next chapter. Kender a l s o noted that i f we describe space a point . i n the i n terms of the rectangular co-ordinates T necessary to compute 6 e x p l i c i t l y . x and T v parameter then i t i s not In f a c t , no trigonometry at a l l is required. Consider an vector" E=(E ,E ). X line segment V "edgel" defined by The edge vector i s a that i t r e f e r s t o . a p o s i t i o n P=(x,y) and an "edge vector perpendicular to the The value of the edge vector's length 27 T y A Polar plot of Hough transform of "city streets" Figure f2.2.7 28 i s l e f t open t o i n t e r p r e t a t i o n conveniently i n Render's paper but may thought o f as the "strength" o f the l i n e . be most That i s , i f the image i s c o r r e l a t e d with the masks o f O'Gorman and Clowes, then the edge vector may be taken t o be E = G = ( D X , D Y ) . XV XV The parametric form of t h i s edgel, T = ( T , T ) , can then be computed t o be: X V T = ((E»P)/|E| )E 2 That i s , T i s i n the d i r e c t i o n o f E, perpendicular t o the l i n e segment, and i s o f length (E»P)/|E| which i s j u s t the length o f P projected the unit vector onto i n the d i r e c t i o n of E and T, namely rho (see Figure f2.2.8). Render's second m o d i f i c a t i o n i s simply t o map every p o i n t , (rho,©), to (K/rho,9) f o r some constant K. but i s now o f length R/rho. So, T i s s t i l l i n the d i r e c t i o n o f E, That i s , T = (K/rho)(E/IEI) = (K/[(E-P)/|E|]) (E/IEI) = (K|E|E)/([(E-P)|E|] T = (R/(E«P))E Converging l i n e s now map i n t o points lying on a straight line, p a r a l l e l l i n e s i n t o points l y i n g on a s t r a i g h t l i n e through the o r i g i n . Derivation of T Figure f2.2.8 30 Render then proves the f o l l o w i n g theorem: "Suppose an image contains the perspective p r o j e c t i o n of a planar surface defined by two or more coplanar sets of p a r a l l e l l i n e segments. Let the o r i g i n of the transform space correspond to the coordinates of the f o c a l point i n the image (that i s , where the camera i s "aimed"). Let R equal the f o c a l distance. Then T = R E / (E-P) transforms edges so that the i n t e r s e c t i o n of l i n e s of accumulation points i n the transform space i s at (p,q), the gradient vector of the surface." And so the surface's s l a n t i s detected. method f a i l s i f the p r o j e c t i o n points are very far d i s t i n q u i s h a b l e from distinguishing away the is since origin. N o t i c e , however, that t h i s orthographic the This or i f the vanishing i n t e r s e c t i o n point w i l l not be method also relies on our between p a r a l l e l l i n e s that converge due to perspective and n o n - p a r a l l e l l i n e s . T h i s , as was pointed out e a r l i e r , i s not always that easy to do. Nevertheless, Render has introduced Hough modifications that make the transform computationally more d e s i r a b l e . Chapter 3 w i l l discuss the uses of the Hough transform f o r orthographic p r o j e c t i o n s . 31 2.3 APPLICATIONS Discrimination The most common a p p l i c a t i o n o f texture homogeneous textured regions. This i s t y p i c a l l y concerned with planar surfaces viewed with the surface normal plane. As i s the d i s c r i m i n a t i o n of perpendicular t o the p i c t u r e In t h i s case the image texture i s the same as the scene texture. was mentioned before, t h i s i d e n t i t y i s the source o f a great deal o f confusion i n defining texture. These are g e n e r a l l y "real-world" a p p l i c a t i o n s such as t e r r a i n c l a s s i f i c a t i o n from s a t e l l i t e images (Dyer, Weszka and Rosenfeld, 1975a,1975b) and m i c r o - b i o l o g i c a l images (Hawkins, 1970). An exception (Tomita, Yachida t o the above and T s u j i , 1973) mentioned under " S t r u c t u r a l A n a l y s i s " . textured cube i s the work on a The input Tomita et i n the preceding picture here could o f several al section be d i f f e r e n t l y textured table-top, f o r example. image i s then segmented i n t o regions on the basis features. of of a The textural An important aspect o f t h i s work i s that segmentation occurs i n stages o r l e v e l s as determined by the "supervisor". For example, the cube image i s f i r s t segmented i n t o the "cube" region and the "table-top" region on the basis o f one feature. segmented into the cube. Note that a t the top l e v e l the cube region. regions The cube region i s then further corresponding to the three v i s i b l e surfaces of i s seen as being one The scene texture i s indeed the same over the whole cube. The image t e x t u r e , however, i s d i f f e r e n t f o r each region representing a face of the cube. I t i s a strength o f t h i s program that i t detects these 32 levels. Immediate d i s c r i m i n a t i o n o f more abstract (and perhaps a r t i f i c i a l ) textures has been studied by J u l e s z Julesz, e t a l , 1973) ( C a e l l i point o f view. Only absolute discrimination the two textures d i f f e r e n t or not?) i s considered by a l l o f these researchers, although r e c e n t l y ( C a e l l i and J u l e s z ,1978) "ease have mentioned o f d i s c r i m i n a t i o n " . No i n t e r p r e t a t i o n (such as apparent texture from true texture) was placed on d i f f e r e n c e s i n apparent In the above cases, d i s c r i m i n a t i o n was performed histogram o f the d i s c r i m i n a t i n g texture texture. by generating a feature, s e t t i n g thresholds from the histogram, and segregating textures as t o how the feature the and 1978) from a psychological point of view and by Schatz (Schatz, 1978) from a computational (are (Julesz r e l a t e d t o the threshold. applied over For example, a l l atomic regions with area greater than the threshold are grouped i n t o one region (Tomita et a l , 1973). We w i l l demonstrate t h i s i n Chapter 3.3. Surface s l a n t Gibson has studied the use o f texture gradient (the change, due t o perspective, i n some textural "space perception" (Gibson, 1950). of features such as coarseness) i n human Gibson has shown t h a t , i n the case perspective images, d i s c o n t i n u i t i e s i n texture gradient give r i s e t o the perception o f edges, such as caused by corners or d i s c o n t i n u i t i e s i n the surface ("occluding edges"), and that the texture gradient could used to determine the orientation Computationally, many problems a r i s e . or shape of a be surface. Among them: i t i s d i f f i c u l t to e s t a b l i s h i f the texture gradient over a region i n an image i s caused by perspective or the curve o f the surface. Gibson a l s o observed that the 33 monocular perception of depth depends on texture gradient t o some degree. We have already mentioned the work by Render i n t h i s f i e l d , and we now note t h a t , he a l s o , e x p l o i t s texture gradient i n perspective by computing the vanishing p o i n t . images This t h e s i s does not e x p l o i t texture gradient, as w i l l be discussed l a t e r . Both o f Gibson's and Render's t h e o r i e s slant i n orthographic images. do not determine surface I t i s the purpose o f t h i s t h e s i s t o present a theory that succeeds i n t h i s respect. Depth cue Computations based on texture gradient have a c t u a l l y been used as a depth cue (Bajcsy and Lieberman, assumption i s made 1976) i n perspective that a l l surfaces are planar. images. The "Real-world" scenes (such as a grassy f i e l d and an ocean view) were considered and images of these were used as input t o the program. Fourier Features derived from the domain were used and r e l a t i v e distances were c o r r e c t l y deduced. I t was conjectured i n this work that absolute distances could be c a l c u l a t e d i f the program contained a camera model with information such as the lens focal length. Some problems were encountered when the planar surface assumption was v i o l a t e d (the grassy f i e l d r o l l e d a b i t ) . This work, may have benefited i f d i s c r i m i n a t i o n o f surface s l a n t had been incorporated i n t o the program. 34 2.4 SUMMARY Texture structures) i s usually on a defined surface. as many basic elements (micro- Each micro-structure may or may not have a s t r u c t u r e associated with i t . As w i l l be f u r t h e r explained 3.1 be viewed as micro-structures placed on a and 3.3, texture surface according to a will macro-structure (placement rules). in Chapter The word " t e x e l " i s used to r e f e r to a projected image of a micro-structure. The shortcomings of t h i s approach w i l l be discussed i n Chapter 4.4. Many texture measures have been developed and they f a l l into three broad c l a s s e s : s t a t i s t i c a l , m i c r o - s t r u c t u r a l and macro-structural. three All c l a s s e s w i l l be used i n the next chapter, but, as we s h a l l see i n Chapter 3 and discuss i n Chapter 4, these class distinctions are somewhat ambiguous. It will remainder determining of be assumed that texture d i s c r i m i n a t i o n i s p o s s i b l e i n the this surface dissertation. slant from r e s t r i c t e d to perspective images. Furthermore, images of work textured concerned with scenes has been The r e s t of t h i s t h e s i s w i l l t h i s work by examining texture i n orthographic p r o j e c t i o n s . extend 35 3. APPROACHES TO COMPUTATIONAL DETERMINATION OF SURFACE SLANT FROM TEXTURE MEASURES 3.1 INTRODUCTION It i s demonstrated i n this chapter that information surface's o r i e n t a t i o n can be extracted from the apparent, surface's orthographic image. This demonstration about a texture o f the i s constructive i n that we w i l l a c t u a l l y s p e c i f y algorithms t o accomplish t h i s task (and i n some cases our computer w i l l accomplish i t ) . With t h i s end i n mind, l e t us now look a t the orthographic p i c t u r e taking process. Let us suppose that we have represented a given object i n terms o f the C a r t e s i a n co-ordinates o f a l l of the points on object, i t s surface. This and the space that i t i s i n w i l l be referred to as the scene. Now l e t us p o s i t i o n a p i c t u r e plane i n such a way that the x- and y-axes of the p i c t u r e plane are p a r a l l e l t o the X- and Y-axes frame o f reference and the p i c t u r e plane o r i g i n l i e s on the Z-axis o f the scene's reference frame. picture scene plane o f the scene's We w i l l say that a p o i n t , (x,y), on the i s an orthographic p r o j e c t i o n o f a point (X,Y,Z), i n the i f and only i f x = kX and y = kY f o r some constrant k. This process i s i l l u s t r a t e d f o r a l i n e i n f i g u r e f3.1.1. Suppose now that our scene c o n s i s t s of a planar surface with and dots on it. A surface i s considered lines t o be " i n f i n i t e " i n a l l d i r e c t i o n s (the extent o f any l i n e s and dots on i t , however, i s f i n i t e ) . I t i s easy t o see that the surface, picture plane, intersects unless i t i s parallel the p i c t u r e plane Without l o s s o f g e n e r a l i t y , we can think o f t h i s being parallel with the along a s t r a i g h t l i n e . intersection line as t o the x-axis ( i f i t i s not, we need simply r o t a t e the Orthographic p r o j e c t i o n of l i n e Figure f3.1.1 37 frame o f reference about the z-axis u n t i l i t i s ) . for simplicity that the surface passes We w i l l otherwise mentioned. assume through the reference frame o r i g i n and that any l i n e on the surface a l s o passes through unless also the o r i g i n These l a s t two assumptions are made simply to allow r e f e r r i n g to absolute co-ordinates, (x,y), rather than being forced t o use r e l a t i v e co-ordinates (delta x, d e l t a y ) . We now want t o t a l k about how the surface i s slanted with respect to the p i c t u r e plane. following terms. To make t h i s task somewhat e a s i e r , we define the We define the amount o f s l a n t , tf, of a surface as the angle between the X-Y plane (or the p i c t u r e gradient vector. plane) I f the frame o f reference i s rotated as we assume i t to be, then & i s the angle between the Y-axis surface which i s normal t o the X-axis. the o r i g i n ) we define 0 and the X-axis. image and the surface's a and that line on the For any l i n e (passing through (a f o r actual) t o be the angle between the l i n e We a l s o define 0 to be the angle between the projected o f the l i n e and the x - a x i s . Note that 0 < 0 a i n general. These concepts are i l l u s t r a t e d i n f i g u r e f3.1.2. I t i s the goal o f t h i s chapter t o recover & from information obtained only from the image (and the assumptions we make about i t ) . In general, f o r a given image and a given surface, the surface w i l l not i n t e r s e c t the p i c t u r e plane a t a l i n e p a r a l l e l t o the x - a x i s , to our assumption. c (which may be 0) from the x-axis o f the p i c t u r e plane. n contrary In f a c t , the i n t e r s e c t i o n l i n e w i l l be a t an angle R e c a l l that a i s the d i r e c t i o n o f the surface's gradient vector, hence the notation a n to i n d i c a t e that the i n t e r s e c t i o n l i n e i s normal t o the d i r e c t i o n o f the gradient. For I t i s a l s o our goal t o recover c from the same the purpose information. o f i l l u s t r a t i o n , however, l e t us s t i c k t o the a n = 0 Surface slant notation Figure f3.1.2 39 assumption. The feature o f t h i s p r o j e c t i o n that i s most u s e f u l t o our work i s the e f f e c t of "foreshortening" of lengths. To see what t h i s means, l e t us prove the f o l l o w i n g theorem. Theorem 3.1.1 Assume that a l l o f the l i n e s on the surface are o f length L and that these l i n e s take on a l l o r i e n t a t i o n s (-ir/2 < © < ir/2). Let the surface be t i l t e d by an angle jzf. Let L be the length o f a projected image o f a l i n e . Then a polar p l o t o f L" versus © i s an e l l i p s e centred on the o r i g i n with a major a x i s a = L and a minor a x i s b = Lcos(jrf). a 1 Proof: R e f e r r i n g t o Figure f3.1.3, i t i s noted that X = OA = Lcos© x = O'A 1 a =L'cos© and that X = x since OA = O'A' so Lcos© = L'cos© (1) a I t i s a l s o observed that Y = BP = CD = OE ODcos^ APcosjzf (OPsin© )cos^ LsinOgCosjrf a y and Y A'P' L'sin© y since Y = BP = A'P' = y so Lsin©cosjzS = L'sin© (2) a Then, d i v i d i n g (2) by (1) we get tan© = tan© cos^ (3) a To see the e l l i p s e i n L , we now want t o express L as a f u n c t i o n o f a, b, and 6. Since a = L and b = Lcos^, we want t o express L' as a f u n c t i o n of L, cos^, and ©. Now 1 1 40 Figure for theorem f3.1.1 Figure f3.1.3 41 L COS © 2 L «2 2 a = cos 0 by (1) 2 L = 2 (trigonometric e q u a l i t y ) (l+tan2e )cos 6 2 a L = 2 b y ( 3 ) (l+tan2e)cos2e COS Jf) 2 L cos j?) 2 2 cos 9cos jzi + s i n 0 2 2 2 then m u l t i p l y i n g by L / L we get 2 2 (L ) (L cos )zJ) 2 2 2 L s i n 6 + (L cos jzi) c o s 2 e 2 2 2 a b 2 2 2 a sin 9 + b cos 0 2 2 2 2 which i s the equation of an e l l i p s e . Q.E.D. It i s now f a i r l y easy to see that any given l i n e i n the scene w i l l be maximally foreshortened i n the d i r e c t i o n of the direction of the d i r e c t i o n normal gradient to it. vector) surface slant (the and not foreshortened at a l l i n a Furthermore, theorem 3.1.1 allows us to c a l c u l a t e the amount of s l a n t , jrf, as: 0 = cos-1(b/a) There i s , nevertheless, from foreshortening. are foreshortened gradient. by a defect i n the method of determining jrf From the theorem j u s t proven, l i n e s i n a the scene f a c t o r cosjzJ i n the d i r e c t i o n of the surface's But due to the invariance of the f u n c t i o n , cos, over the s i g n of i t s argument, i t i s p o s s i b l e to determine only the absolute value of 42 f6 from the foreshortening. That i s , since cos^ = c o s ( - t f ) , d i s t i n g u i s h between the image of a scene and the image of we cannot i t s Necker reversal. With these observations i n hand, l e t us now look at texture. 3.2 STATISTICAL APPROACHES Second order statistics have been used by J u l e s z , H a r a l i c k , and Schatz (see Chapter 2 f o r d e t a i l s ) . the These s t a t i s t i c s are examined in hope t h a t they may be u s e f u l f o r the d e t e c t i o n of surface s l a n t and the r e s u l t s obtained are presented i n t h i s s e c t i o n . Input is in the form of a 64X64 matrix with two p o s s i b l e g r a y - l e v e l s , 0 (blank) and 1 (a mark). 2X2 co-occurrence matrices (see Section 2.2 f o r d e f i n i t i o n s ) are c a l c u l a t e d f o r displacement vectors 6 = (x,y) where 0 < x < 10, 0 < y < 10. Regular dots Consider a surface textured with size) arranged on the v e r t i c e s surface of an dots (with, t h e o r e t i c a l l y , no (invisible) g r i d (which i s a l s o the p i c t u r e plane h o r i z o n t a l ) . A n a l y s i s of the 1 image indicates that pJ(l,l) grid. The = ir/4 about the h o r i z o n t a l a x i s of the i s then t i l t e d back by i s then 'imaged . square second will have order This rotated surface statistics high values for this f o r d's i n the h o r i z o n t a l d i r e c t i o n having lengths equal to m u l t i p l e s of the i n t e r p o i n t distance. vertical High values f o r direction and Pri(l,l) having lengths i n t e r p o i n t d i s t a n c e . For d's of other high will also occur equal directions, to f o r d's cos(jrf) Po^(l,l) in the times the will yield values f o r those lengths of d' that correspond to distances between 43 points having the same direction of cf between them (see Figure The plot of Pcf(l,l) f3.2.1). for cf = k(l,0) where k=l,2,3,... ,10 peaks at cfs corresponding to multiples of the interpoint distance. The plot of Pcf(l,l) for cf = k(0,l) where k i s as above, while somewhat muddled, gave recognizable expected. peaks Thus = cos- at cos(fi) times the distance as was could be determined to be: length (cf) at 1 s t peak of Pc»(l,l) fi = k(l,0) length(d) at 1 s t peak of PcJ(l,l) 6 = k(0,0) 1 Note that i f this technique were to be surface interpoint with unkown slant, used on an image of a we would have to be sure to "pick" the cfs such that they f a l l on adjacent points, otherwise we could not determine the size of the squares of the grid. The problem would be alleviated i f the grid were " f i l l e d in", that i s , i f we had a grid of lines as well as vertices. for In this case we could assume that a polar plot smallest of length (cf) peaks would give a square and we could then f i t our data accordingly. Note that we are actually looking at a grid the dots" as in and that "connecting (Schatz,1977,1978) would not change our result. In fact, the dominant characteristic here seems to be the structure of the grid, rather than the statistics such a grid presents. Circles The surface square grid. here consists of rings arranged on the vertices of a The circles are small enough Again, the surface i s slanted by jz» = nr/4. willing fellow graduate students) that no overlap occurs. My collegues (actually barely and I had no d i f f i c u l t y seeing the surface slant ourselves (human perception), however, an analysis of 2" no 44 Examples of deltas Figure f3.2.1 45 order statistics for the r e s u l t i n g d i g i t i z e d image proved very messy. The s t a t i s t i c s of j u s t a s i n g l e c i r c l e are shown i n Figure f3.2.2 below. I f there were no other c o n t r i b u t o r s to P ^ ( l , l ) when |o^|<d_iam c i r c l e diam c i r c l e is sufficiently large for the plot of and Pd'ci/l) to be recognizable, t h i s method would pick out the "diameter" of the c i r c l e i n any d i r e c t i o n . slant, we Since c i r c l e s are deformed i n t o e l l i p s e s by the could = cos-1(b/a). tilted about are met, is measure major(a) We could a l s o say the major a x i s . i n general. less the than (correctly) the surface set is distance pairs of (e.g. points Corkboard, concrete walkways), a l s o c o n t r i b u t e to P r i ( l , l ) i n the Digitization attributes top, bottom, and sides of the c i r c l e s are flattened) a l s o crept i n deform our implementation experimental plots (see Figure f3.2.4). find that extent objects structural since The v e r i f i e d t h i s a n a l y s i s and c i r c l e diameters d i d not seem to be detectable without p r i o r knowledge of the arrangement. our properties dominate. micro-structures indeed. Perhaps not arrangement, or macro-structure, the and F i r s t o f f , since the minimum i n t e r c i r c l e region of i n t e r e s t (see Figure f3.2.3 below). to that axis diam c i r c l e f o r most textures (and i n p a r t i c u l a r f o r our intercircle (the minor(b) Unfortunately, neither of our c o n d i t i o n s t e s t case) i n v o l v i n g " c i r c l e s " these and surface macro-structure obvious are is highly the structured effect of on the second order s t a t i s t i c s . allowed us to macro-structure say It the is that i s muddying the p l o t of P6(1,1) by introducing the i n t e r c i r c l e distances i n t o the i n t r a c i r c l e part of the p l o t . was p r e c i s e l y the we This makes sense to some (circles) so Again anything at of the regular dot Yet i t texture that a l l about the surface s l a n t f o r that pattern (as dots do not have a u s e f u l m i c r o - s t r u c t u r e ) . In t h i s case at l e a s t , a s t r u c t u r a l a n a l y s i s of some s o r t appears to be necessary. 46 47 Intercircle deltas Figure f3.2.3 Digitization Figure of a circle £2.2A 49 Other Micro-structures C i r c l e s were chosen i n the previous example f o r They are rotationally measurements on them are invariant easily under described Po^(l,l) due to their simplicity. and directional the simple polar equation of a c i r c l e (r = c ) . More complex regular shapes (e.g. squares) are not r o t a t i o n a l l y i n v a r i a n t under P r i ( l , l ) i n that Figure f3.2.5a w i l l y i e l d a lower (0) for P r i ( l , l ) where d' = (d,0) than Figure f3.2.5b. that inter-texel distances I t i s now the case depend not only the macro-structure of the texture but a l s o on the r o t a t i o n of the micro-structures (which, true, value may be construed to be a part of the macro-structure) i t is as shown i n Figure f3.2.6 below. It is clear that second u n i n t e l l i g i b l e i n t h i s case. other regular order statistics quickly become I n t u i t i v e l y , however, squares, c i r c l e s and shapes are i d e a l l y suited f o r d e t e c t i o n of surface s l a n t as c i r c l e s are deformed into e l l i p s e s and squares i n t o parallelograms i n a clearly specified way. Uniform Dots Consider, now, over the plane a surface textured with direction image of observation a. this randomly (e.g., a high-contrast stucco w a l l ) . surface i s again t i l t e d by an angle a dots One would surface, and i s misleading. away from the distributed Suppose that the picture plane in expect the dots to be "compressed" i n the this Suppose is indeed the the digitized case. image, But this I , has a r e s o l u t i o n of N*N and that the dots are now uniformly d i s t r i b u t e d i n the Effect of rotation on co-occurrence matrices Figure f3.2.5 V S v V, v. y -v- -> Effect of rotation on inter-texel distances Figure f3.2.6 52 d i s c r e t e case. the image The average d e n s i t y (# dark p i x e l s / N*N) i s higher I than i n an image of the u n t i l t e d surface. the knowledge of t h i s compression to detect the surface Equivalently, i s there a directional s t a t i s t i c s of the projected image? dependence in But, can we use slant from detectable I? i n the S u p r i s i n g l y , the answer i s "no". Theorem 3.2.1: In an orthographic image of a surface textured by dots positioned randomly and uniformly there i s no d i r e c t i o n a l dependence i n the co-occurence matrices. Proof: Consider aligned a square s e c t i o n of with the scene axes X and Y. the surface of dimensions a x a Suppose the p r o b a b i l i t y density f u n c t i o n (p.d.f) of the dot d i s t r i b u t i o n on the surface i s f(x,y) = g(x)g(y) where g(s) = 1/a f o r 0 < s < a. In the image, the p.d.f of the dot d i s t r i b u t i o n w i l L be f'(x,y) = g(x)h(y) where g(x) i s as above and h(y) = 1/acos^ f o r 0 < y < acostf The p.d.f. F independently dimensions a x 1 can be regarded sampled points acos)Z$. over as a constant, uniform p.d.f. the rectangle i n the image for of I f f' (x,y) i s re-expressed i n polar co-ordinates r,6 then i t i s c l e a r l y a f u n c t i o n of r alone. Hence there can be no d i r e c t i o n a l dependence i n the co-occurence matrices. Q.E.D. As i t seems reasonable to assume that d i r e c t i o n a l i t y i s necessary f o r the d e t e c t i o n of surface s l a n t , i t i s concluded that i t i s not 53 possible to determine the s t a t i s t i c s o f the t e x t u r e . 0, amount o f s l a n t , slant of this surface from second order I t should be pointed out, however, that the can be determined from the image i f the parameters of the p r o b a b i l t y d e n s i t y f u n c t i o n are known. The theorem i n d i c a t e s that a p l o t of P<$(1,1) would such an image. This has been be experimentally v e r i f i e d flat for using the implementation mentioned. Conclusions The r e s u l t s obtained from the implementation i n d i c a t e order statistics on structural appropriate to second ( i n the micro sense) textures q u i c k l y become muddled and u n i n t e l l i g i b l e . seems that This i s not too suprising, as it use s t r u c t u r a l techniques on s t r u c t u r a l textures and s t a t i s t i c a l techniques on " s t a t i s t i c a l " textures. However, we have seen that f o r t r u l y random t e x t u r e , statistics do not help us a t a l l ! seem to apply best to regular dots. a p a t t e r n , or s t r u c t u r e . second Furthermore, second order s t a t i s t i c s But here, the dots are arranged the in Again, s t r u c t u r a l techniques are appropriate, t h i s time f o r a n a l y s i s of the macro-structure of the texture. case order In this micro-structures are simply dots and t h e i r a n a l y s i s need not concern us here. The shortcomings of s t a t i s t i c a l a n a l y s i s s t r o n g l y suggest of structural sections. analysis, and this will be the use examined i n the next two 54 3.3 STRUCTURAL APPROACHES: THE MICRO-STRUCTURE Consider a surface textured by p l a c i n g copies structure given These are the patterns out o f t o construct a texture. We w i l l use the term t e x e l t o r e f e r t o a texture element i n the image. structure Thus, the image o f a copy that has been placed on a surface i s a t e x e l . of a micro- We w i l l assume that the micro-structure i s not a l t e r e d i n any way (other than and micro- over i t . We w i l l use the term micro-structure t o r e f e r t o an a b s t r a c t d e f i n i t i o n o f shape and s i z e . which of a rotation t r a n s l a t i o n ) and we w i l l not concern ourselves with the d e t a i l s o f the macro-structure placed). The (the pattern i n which the micro-structures are purpose of t h i s s e c t i o n , then, i s t o examine the problem of surface s l a n t d e t e c t i o n from t e x e l a n a l y s i s . Consider Figure f3.3.1 below. figure represents a cube I n t u i t i v e l y we would (or c o r n e r ) , each surface o f which has been textured with square micro-structures. the image the cube. squashed into say that the Furthermore, we would partition regions corresponding t o the three v i s i b l e surfaces o f We would a l s o say that the t e x e l s i n any given i n the d i r e c t i o n region are o f the surface's gradient vector. We make these observations even though we do not know, a p r i o r i , that the micros t r u c t u r e i s a square, n e i t h e r do we know i t s s i z e , and we do so i n the presence of a f a i r amount o f noise ( a l l the micro-structures would have mapped i n t o parallelograms i n a n o i s e l e s s image). Any shape-from-texture following algorithms mentioned above. detect system should be attempt just as v e r s a t i l e . The t o embody some of the i n t u i t i v e notions I t should be mentioned, however, the shape o f the true micro-structure. that they do not For example, f o r Figure f3.3.1, they do not recognize the t e x e l s as slanted squares. o ° o ° o ° 0 0 0 ° ^ O o O a o°o a o /7 0 *> * V * o * * * * * o Q * * * * * * 0 a 4 * o 0 "cube" textured with squares Figure f3.3.1 56 The S i n g l e Surface Before we a c t u a l l y t a c k l e an image l i k e Figure f3.3.1, l e t us f i r s t look a t some simpler cases and work our way up. Consider the image o f Figure f3.3.2. The scene represented here i s a s i n g l e surface textured with randomly rotated s t r a i g h t l i n e segments o f a surface has been angle c n tan(jzS) rotated from the X-axis. (slanted) by an angle That i s , i t s gradient length. This about a l i n e a t an vector i s of length and has d i r e c t i o n a. Before s e t t i n g about analysing t h i s image, l e t us set down a few assumptions These given assumptions will be (in addition retained t o our usual ones). f o r the duration o f t h i s s e c t i o n (3.3). -there i s only one micro-structure used. -the surface i s textured by p l a c i n g rotated copies o f the micro-structure t o make a l l o r i e n t a t i o n s e q u a l l y l i k e l y over i t . no assumptions are made as t o where these copies Note that are placed. For example, the placement may be random or o r d e r l y . -the image texels (of the scene) (sufficiently well i s pre-processable to y i e l d a l i s t o f represented, by a list of vertex coordinates, f o r example). -the image has been so pre-processed. One Diagonal For each texel (line segment, i n t h i s case) l e t us measure i t s (Euclidean) length, L, and i t s angle o f o r i e n t a t i o n , 0, from the x-axis (-pi/2 < 0 < p i / 2 ) . list. Let us r e f e r t o t h i s set o f (L,0) p a i r s as the L-0- Since each micro-structure copy i s randomly rotated before being / \ \ / \ \ \ \ / _ / \ I \ 1I Tilted surface textured with line segments Figure f3.3.2 58 placed on the surface, we can now appeal to theorem 3.1.1 the measured data w i l l l i e roughly on an e l l i p s e . to see that The image, of course, i s not a p e r f e c t orthographic p r o j e c t i o n , but i t i s a good approximation to one within a noise factor (caused by d i g i t i z a t i o n ) . therefore, a c t u a l l y represents a noisy e l l i p s e . data A polar taken of Figure f3.3.2 i s shown i n Figure f3.3.3. reduced to f i n d i n g the e l l i p s e f a c t o r s a, b, and c list. 0 of this Our task i s now from the data, L-0- Since we have determined that those l i n e segments making an angle = a with the x-axis are not foreshortened (theorem 3.1.1 n can reasonably estimate a in n plot The data, L-0-list. n to be that 0 corresponding to the largest after L This i s c l e a r l y a guess, the point may be very noisy and therefore i n e r r o r , but i t i s hoped that i t i s accurate enough does, a g a i n ) , we a l l , save us some work). (and it A more noise r e s i s t a n t approach would be to t r e a t a as a parameter i n the least-squares f i t t i n g process. We would, however, l i k e the f u n c t i o n that we are t r y i n g to f i t the to be linear section). use. with respect to i t s parameters (see the appendix to t h i s This i s not the case f o r the f u n c t i o n that we have decided to To make o out a n n a l i n e a r parameter then, i t w i l l be necessary to f a c t o r and then f i n d a s i m i l a r f u n c t i o n which does a l l three parameters, a, b, and Let data us now depend linearly on a . n think of the data, L - 9 - l i s t , as a f u n c t i o n of 6 (each p a i r i s a mapping of some 0 to some L ) . Now assume that the p r o b a b i l i t y d e n s i t y f u n c t i o n of the v a r i a t i o n i n L i s a symmetric f u n c t i o n about mean of 0. to an We can now determine the f a c t o r s a and b by f i t t i n g the data ellipse 1965; pg. section. a with 241-246). a least-squares approximation The d e t a i l s may be found i n the appendix We are now n e a r l y done. we see that (Conte and de Boor, to this Appealing yet again to theorem 3.1.1, 59 -j * * * « •% t * 1 * » IS.000 i i i 4 4 4 4- Polar plot of L - 6 - l i s t taken of Figure f3.3.2 Figure f3.3.3 60 = cos— L (minor-axis/major-axis) where minor-axis = MIN(a,b) and major-axis = MAX(a,b). Also, o n has already been determined. Thus the gradient vector (see Chapter 1) of the surface can be determined t o be: p = -tan^ s i n a n p = +tanjrf s i n a n q = -tanjzJ c o s a n or q = +tanjtf c o s a n This algorithm would be o f l i t t l e i n t e r e s t only micro-structures that we could i f line-segments handle. However, i f our micro- s t r u c t u r e had some c o n s i s t e n t l y i d e n t i f i a b l e l i n e s , then we with these lines micro-structure topologically only. were could work That i s , i f l i n e s o f some given length i n the marked unigue, were the in etc.) a way that (coloured, allows highlighted, determination o f the corresponding length i n any given t e x e l , then we could t r e a t this as One way o f i f i t were a single line-segment ensuring that we have an i d e n t i f i a b l e l i n e structure micro-structure. i s t o require t o have a s u f f i c i e n t l y long diagonal ( s . l . d . ) . that d i s a s u f f i c i e n t l y long diagonal (for the image for a l l other our line micro- We s h a l l say i n question) i f diagonals d j (we w i l l use the term diagonal t o r e f e r t o both true diagonals and edges) i n the micro-structure, length(d) = length(dj) or length (d) * cos(jzS) > length (dj) where i s the angle o f t i l t (with respect t o the p i c t u r e plane) of the surface. The idea here i s t o make sure that we have a diagonal that w i l l not be foreshortened "too much". That i s , we would l i k e i t s image to be i d e n t i f i a b l e by i t s length. or, i f i t i s not, the same identifiability Note that a s . l . d . i s e i t h e r unique length as a l l other s.l.d.s. The o f a s u f f i c i e n t l y long diagonal depends on the angle o f 61 tf. tilt, Hence, identifiable a length s.l.d. is a (u.i.l.) weaker since this concept than a dependence i s not required. Indeed, other usable u . i . l . s such as t o p o l o g i c a l l y unique l i n e s suffer from this restriction. contain Examples o f such (for some images) appear i n Figure f3.3.4 below. that the micro-structures need not be even do not Consider the c l a s s o f micro-structures that have p r e c i s e l y one s u f f i c i e n t l y long diagonal. micro-structures uniquely any l i n e segments convex, polygonal, a t a l l . To Note c l o s e d , nor go any f u r t h e r , i t i s necessary t o f i r s t prove the f o l l o w i n g theorem f o r t e x e l s containing one or more s u f f i c i e n t l y long diagonals. This theorem gives the reason that the diagonal i s detectable. Theorem 3.3.1: The longest diagonal o f a t e x e l corresponds to one s u f f i c i e n t l y long diagonals o f the micro-structure. of the Proof: Without loss o f g e n e r a l i t y , l e t the surface be t i l t e d about the X- a x i s by an angle jzJ (Figure f3.1.1). direction 6 Then any diagonal o f length L and i n the micro-structure w i l l be mapped into a diagonal of length L'2 = L sin ecos (z$ + L cos © 2 2 2 2 2 = L ( s i n 0 c o s ^ + cos 0) 2 Thus L 1 2 2 i s longest when 0 = 0 or © = i r (L'= L) and 0 = ir/2 or © = 3ir/2 (L = Lcosjz)'). 1 i s such that is 2 still LCOSJZJ" longer > than i s shortest when But since a s u f f i c e n t l y long diagonal f o r a l l other L-_, we see that L' a t i t s shortest L-_* at i t s longest. The theorem follows immediately. So, f o r the p a r t i c u l a r case diagonal, we of p r e c i s e l y one sufficiently long know that the longest diagonal of each t e x e l i s the image 62 Examples of micro-structures with exactly one sufficiently long diagonal Figure f3.3.4 63 of the s u f f i c i e n t l y long diagonal of the that we can effectively micro-structure. This means ignore a l l of the points of any t e x e l except those belonging to the longest diagonal, and i n doing so, ignore a l l of the diagonals of the micro-structure except the s u f f i c i e n t l y long one. Since the micro-structure i s randomly rotated before being placed on the surface, so i s the s u f f i c i e n t l y long diagonal. record the diagonal, length, L, and will have a we assumptions of theorem I f we then measure and the d i r e c t i o n , 0, of each t e x e l ' s longest list, L-0-list, satisfying 3.1.1. We can then e x t r a c t a l l of and a the from L-0- n l i s t i n e x a c t l y the way we d i d f o r the s i n g l e line-segment case. To summarize briefly, an algorithm has been developed which e x t r a c t s surface s l a n t information from images of surfaces textured with 1) "Dipoles" or micro-structures c o n s i s t i n g of just a single l i n e - segment 2) "Thick dipoles" or micro-structures containing precisely one s u f f i c i e n t l y long diagonal. Furthermore, we note that 1) i s j u s t a s p e c i a l case of 2). To allow treatment of a more n a t u r a l c l a s s of micro-structures, we now r e l a x our r e s t r i c t i o n on them to include micro-structures containing one or more s u f f i c i e n t l y long d i a g o n a l ( s ) . One or More Diagonals Some examples of such micro-structures are shown i n Figure The situation is now somewhat more d i f f i c u l t . The d i f f i c u l t y a r i s e s p r i m a r i l y because the longest diagonal of a t e x e l may now be of any one f3.3.5. the image of the s u f f i c i e n t l y long diagonals of the micro-structure. 64 Figure f3.3.5 65 This a f f e c t s us i n the f o l l o w i n g way. Theorem 3.3.2: Let and 62 be two of the s u f f i c i e n t l y long diagonals o f the micro-structure. Let the a n g l e between them ( i n the microstructure) be p. I f d i s the longest diagonal o f a t e x e l , then the angle between d and the major a x i s o f the e l l i p s e i s l e s s than u/2. 1 Proof: See Figure Since d j and d2 are d i s t i n c t , p < it*. f3.3.6. l o s s o f g e n e r a l i t y , l e t the surface be t i l t e d about is, the major a x i s o f the e l l i p s e i s the X-axis. 61 and the X-axis be 0 . less than the x - a x i s . That Let the angle between Also without l o s s o f g e n e r a l i t y , a Without let 6 a be or equal t o u/2 ( i f t h i s i s not true f o r d]_, i t w i l l be f o r 62)- Then d must be the image o f d j s i n c e the image o f d j , d ] / , w i l l be at l e a s t as long as the image o f 62, $2'• d2 and the X-axis. Id-.' I = x + y 2 |d 'l 2 2 ^ e t n e angle between 2 + L sin © cos jr> 2 2 a 2 2 a = L c o s 0 2 + L sin 92Cos j?) Hence ^ ' l Note e Then = L cos 0 2 L e t that 2 2 2 2 < Id]/I 2 |dj_'| = |d2'l 2 2 since e a < 62 only when © a = ©2 -- n which case i t can be assumed that d i s the image o f d^ without l o s s o f g e n e r a l i t y . R e f e r r i n g back t o equation (3) of Theorem 3.3.1, we know that tan© = tan© cos^ a So < u/2 < ir/2 tan© < tan(p/2)cosjz>" since © tan© < tan (u/2) since 0 < jz5 < ir/2 © < u/2 a since 0 < ©, p/2 < ff/2 Q.E.D. and d2 are considered t o be l i n e s rather than v e c t o r s . The "angle between them" i s considered t o be the major angle o f t h e i r i n t e r s e c t i o n (unless otherwise noted). 66' Figure for theorem f3.3.2 Figure f3.3.6 67 This i s e a s i l y generalized to more than two diagonals. Note also that u/2 i s not the t i g h t e s t bound, but i t i s our purpose merely to show that such a r e s t r i c t i o n From exists. theorems 3.3.1 and 3.1.1 we know that a l l of the data points i n L - 0 - l i s t s t i l l l i e on an e l l i p s e , but theorem 3.3.2 a l l o f the e l l i p s e w i l l be f a i r l y represented. shows that not In f a c t , there may be no points at a l l at the minor a x i s of the e l l i p s e . Figure f3.3.7 shows an image of a surface textured with squares (which have two s u f f i c i e n t l y long diagonals). list information A polar p l o t of the L-0- f o r t h i s image i s shown i n Figure f3.3.8 i l l u s t r a t i n g the theorem. We w i l l , however, ignore t h i s gap i n that data are a v a i l a b l e to accurately f i t an e l l i p s e to what we enough do have. I t should now be c l e a r why we have decided squares, trigonometric expensive ( e s p e c i a l l y inexpensive approximation, which when using LISP), rather smoothing of data our data to probability a than a computationally by averaging, f o r example. the The to least- noise. of any given point on the e l l i p s e being represented assumption least- A method, on the other hand, a l s o assumes that the to that of any other point. wise use hope i s computationally a b i t squares method makes s t a t i s t i c a l assumptions only about smoothing-by-averaging and make. Theorem 3.3.2 It should i s equal shows us that t h i s i s not a be noted that as the number of s u f f i c i e n t l y long diagonals of the micro-structure increases, the amount of e l l i p s e represented by the L - 0 - l i s t decreases. paradoxical a circle. This leads to the case of the micro-structure with i n f i n i t e l y many diagonals, For t h i s case, the algorithm falls apart completely. The only point i n the L - 0 - l i s t f o r t h i s image i s the point at the end of the ° ° o o- • o o o o oo o o • oo o o ao O o o o <>o o o o ° o O d -d ? D P O°o • a9 0 a ° ° a 0 0 Tilted surface textured with squares Figure f 3 . 3 . 7 69 • * 1 * * * I- * * *. A * * m t t » t * * » •» •» 4 * •# *• »-*—V* • i—*- * •* •» i •» V . . . * *• * * * *• * * * Polar-plot of L-6-list taken of Figure f3.3.7 Figure f3.3.8 : * * 21.021 • 70 major axis in the range (-rf/2 to Tf/2) and yet we can e a s i l y determine the surface s l a n t simply by f i t t i n g an e l l i p s e to any given t e x e l w i l l be an e l l i p s e ) and analysing t h i s f i t i n the same way been doing. The algorithm we have can be made to handle t h i s case simply by doing e x a c t l y that when the L - 0 - l i s t represents only one ellipse. as (which point on the Nevertheless, i t i s unpleasant to have to deal with a s p e c i a l case i n t h i s manner. S i n g l e surface r e s u l t s Pages 71-72 representative and a show two sample synthesized images. runs of the algorithm on Given a l s o are the a c t u a l values of f o r comparison. n More than One Surface In the beginning of surfaces (actually the this section, mentioned i t was hinted that several image regions corresponding to these surfaces) could be segmented on the b a s i s of their apparent texture. i n Chapter 1, such segmentation i s assumed. As the class. L - 0 - l i s t data of any given region corresponding to a surface l i e on an e l l i p s e unique to the surface, we may reasonably suggest this data may be used f o r the region d e t e c t i o n task. shows an image of a cube made up of polar plot of the L-0-list f3.3.10 which can be seen as image, was Nevertheless, to see i f i t i s p o s s i b l e , t h i s problem i s examined f o r t h i s texture Since some data three surfaces for like that Figure f3.3.9 Figure f3.3.2. A t h i s image i s shown i n Figure superimposed ellipses. For i t i s conceivable to detect the e l l i p s e s i n i t s L - 0 - l i s t . this One way to detect these e l l i p s e s i s with a Hough transform (Hough,1962) that * (DISKIN grad) > 30 FORMS READ FROM: grad > * (gradient (image> * * * * * * * * * * * * * • * * O o .o o o o o JNPUl * * o o S U R F" AACCEE n , o o > Input surface ok? * T > This surface i s tilted by an angle phi = ±0.474918 > about a line an angle sigma_n = -.444419 from the X-axis > Therefore, i t s gradient vector is given by > p = -0.221058 or p = 0.221058 > q =0.464222 q = 0.464222 > The actual value of sigma__n = -.523598 > The actual value of phi = ±.523598 72 * * * * * * * * * * * * (gradient (image)) / _ - \ / - N \ \ ..... / x \ \ * * * * * / \ I Input surface > Input surface ok? * > This surface i s t i l t e d by an angle p h i = ±0.767956 > about a l i n e an angle sigma_n = 0.571337 from the X-axis > Therefore, i t s gradient vector i s given by > p = 0.522215 or p = -0.522215 > q = 0.812335 q = -0.812335 > The actual value o f sigma_n = 0.523598 > The actual value of p h i = ±0.785398 — / / \ / —- \ _ \ x / / / I ^ / i / \ r i \ i ^ / / / \! -' N. "cube" textured ''/ 7 / with Figure line f3.3.9 segments IT / 74 * * * *- * *• -» X *- •» S * * -* •• S- * * t * •i 4 * * * * 15.133 -i * Polar of the L-6-list taken of Figure f3.3.9 Figure f3.3.10 75 maps e l l i p s e s i n t o points i n some transform space. look f o r accumulation points in the transform One need then simply space. However, two problems immediately become apparent. The f i r s t i s one of computational complexity. have I f we assume that we no information about the e l l i p s e s , except that they a l l have t h e i r o r i g i n s at the necessarily be co-ordinate origin, three-dimensional then (since the transform there are space three must remaining parameters). The second problem i s much more ellipse fatal and persistent. If the were n o i s e l e s s , t h i s Hough transform technique would work w e l l . As i t i s , we have found, experimentally, that the transform is very s e n s i t i v e to noise, and gives unexpected r e s u l t s . This second problem p e r s i s t s even i f we t r y to e l i m i n a t e the f i r s t . We can do t h i s by noting t h a t , since the same micro-structure i s used over the e n t i r e image, the length of the major a x i s (and equal to the length L value found be the same of the micro-structure's s u f f i c i e n t l y long diagonal) for each e l l i p s e . maximum will We can in the estimate L-0-list. this length to be the Hence, i f the e l l i p s e s are parameterized i n terms of the lengths of the major- and minor-axis the transform space rotation of can now be used. correctly the major-axis, o , a two-dimensional n Let determined us f u r t h e r assume as well. The that a transform has space and somehow been i s now one- dimensional and, i f a l l were w e l l i n the world, i t would now be a simple histogram problem. Nevertheless, i t i s easy to see why the present by looking at the second following analysis. problem is still The transform w i l l 76 c o n s i s t of evaluating the minor-axis length f o r each a . Let us assume n that we only have one e l l i p s e , then l e t us see i f we can detect i t . Consider those points near the ends o f the major a x i s . lengths Note o f a l l o f these w i l l be l e s s than the length o f the major a x i s (as they should be) but due t o the s e l e c t i o n o f the major and that the the noise smaller. i n the points themselves, length some lengths w i l l be much I t can be seen t h a t , f o r these p o i n t s , very the minor-axis w i l l be obtained. axis small values of Note that these are the c o r r e c t values for these p o i n t s ; they do indeed l i e on very e c c e n t r i c e l l i p s e s and not on the e l l i p s e we would l i k e t o detect. Figure f3.3.11 i l l u s t r a t e s t h i s . We could t r y t o c o r r e c t t h i s problem by f i n d i n g a better estimate f o r the major-axis length and by smoothing the data (we w i l l have t o be c a r e f u l that the smoothing algorithm does not t r y t o smooth the e l l i p s e i n t o a c i r c l e as averaging smoothers will). We d i d not have much success with any o f these s o l u t i o n s , however, so we decided that another approach i s c l e a r l y i n order. "We a l l have our moments"anonymous Fortunately, texture d i s c r i m i n a t i o n i s an o l d problem and much work has already been done on i t (see Chapter 2). last chapter, however, most o f the work d i s t i n g u i s h i n g d i f f e r e n t textures on the same fields from grass As was has been surface f i e l d s i n an a e r i a l image). t h i s t h e s i s i s b e t t e r expressed mentioned i n the concerned with (such as wheat The task considered i n as d i s t i n g u i s h i n g d i f f e r e n t surfaces that have the same (actual) texture on them. Before proceeding, l e t us re-emphasize t h a t , although we are using the term "surface", we are a c t u a l l y p r a c t i c i n g region d e t e c t i o n a t this Ellipse detected for noisy points Figure f3.3.11 78 stage of the a n a l y s i s . Since the surface i s part of the scene (and not part of the image) i t w i l l be maintained that a detected surface has not been u n t i l i t s three-dimensional a t t r i b u t e s (such as surface s l a n t ) can be described. Several researchers (Tomita et a l , 1973) (Wang et a l , 1979) have found that the second order moments of i n e r t i a of the t e x e l s form a good feature space f o r surface d e t e c t i o n of t h i s k i n d . We can see why this should be so by considering the case where the micro-structures are a l l circles. Then the t e x e l s w i l l a l l be e l l i p s e s whose major a x i s i s i n the d i r e c t i o n of the l i n e that the surface has whose minor been tilted about and a x i s i s i n the d i r e c t i o n of the surface's gradient vector. In such a case, the minimum angular i n e r t i a of a l l the t e x e l s on a given region w i l l be that taken about the major a x i s . structures circles. each The domain of micro- f o r t h i s s e c t i o n may be thought of as polygons approximating So, rather than g e t t i n g unique points i n the moment space c l a s s of t e x e l s on a region, s l i g h t l y scattered c l u s t e r s i n the space are obtained. (( lrYl) If a ( 2'Y2) ••• x for X texel i s described ( n*yn)) which x are as the a list of points co-ordinates of the v e r t i c e s w i t h i n the t e x e l , then the moments of these v e r t i c e s are given by: n Ixx = d/n) 2 ( i=l I w Yi - y ) 2 m n = (1/n) 2 ( x i - x ) i=l 2 m n I x y = d/n) 2 (*i - % ) (yi - y ) m i=l where ( x , y ) are the co-ordinates of the v e r t i c e s ' centre of mass. m a more m general d e f i n i t i o n see (Wang et al,1979). For In Chapter 2, i n the 79 s e c t i o n on s t r u c t u r a l a n a l y s i s , we referred t o the i j Mij. t order n moments, These are given by n Mij = l / n l ( x - x ) i ( y y ) J k=l k Thus Mu = I m k m xy M 02 = x x M 20 J = lyy So, assume that we these moments have been computed f o r every t e x e l in the image. corresponding histograms The task now i s t o pick out the regions i n the image to the surfaces. o f each eccentricity moment Rather than constructing one-dimensional (Tomita e t al,1973), and d i r e c t i o n o f each t e x e l (Wang e t a l , 1979), l e t us simply view the set o f computed moments as points I x x or computing the i n the three-space, X Iyy X I y , and then look f o r c l u s t e r s i n t h i s space. X Note that, assumptions. clusters (distance i n so doing, we are making a l l o f the usual c l u s t e r i n g One of these i s that the feature space w i l l indeed produce separated by some function) threshold. i s simply In t h i s Euclidean case, the metric distance, and the two works p r e v i o u s l y referenced give us reason t o believe that the feature is space u s e f u l . We are a l s o r e l y i n g h e a v i l y on our previous assumptions and our notion o f texture. For example, composed surfaces o f as many the scene could conceivably be as t e x e l s with one t e x e l t o a surface. This case c l e a r l y c o n t r a d i c t s the d e f i n i t i o n o f texture outlined i n Chapters 1 and 2. And o f course, the assumption i s s t i l l made that only one micro-structure i s used. Note that i f the scene c o n s i s t s o f two d i s t i n c t ( i n space) but i d e n t i c a l l y algorithm w i l l only see one surface. slanted surfaces, the c l u s t e r i n g To ensure that segmentation occurs 80 in a meaningful way, i t w i l l be necessary to go back to the image and v e r i f y that the detected c l u s t e r indeed d e f i n e s a not, further these processing w i l l problems implementation i s not does have within single region. If to take place. The d i s c u s s i o n of the scope not t a c k l e them. of this paper and this The problem does e x i s t , however, and any complete scene a n a l y s i s system w i l l need to apply i t s e l f to i t . ' Keeping i n mind that these assumptions have been made, possible to set i t is now about implementing a c l u s t e r a n a l y s i s algorithm. Any algorithm, such as one of those described i n (Duda and (Tou and Gonzalesz, c l u s t e r s to be algorithm widely known 1974) i s used. large 1974), as would separated. do In here, the Hart, 1973) or since we have found the implementation, a simple the maximin-distance algorithm (Tou and Gonzalesz, This served w e l l f o r purposes of demonstration. For a scene a n a l y s i s system, however, a more dependable graph-theoretic algorithm, such as one of those described in (Zahn, 1971) is recommended. Figure f3.3.1 f3.3.12 showing dimensional the case. shows good An a plot of Iyy versus I separation obtained example of the even x v taken of Figure for this two- algorithm at work i s shown i n Figure f3.3.13. Now that the image i s d i v i d e d up i n t o regions, i t i s necessary o n l y to determine the s l a n t o f each surface. This can be done one surface a t a time s i n c e the techniques f o r handling the s i n g l e already been described. shown on pages 86 to 89. An surface case have example o f the e n t i r e process a t work i s 81 yy 233.$ 00 » *• * * * • ** 4 * % * 4 * * * * » jajL LQJL xy 122.100 -120.000 T w v.s. I w taken o f Figure f3.3.1 Figure f3.3.12 a a a ° ° O O a O a /7 * * **** *& O 0 THIS 0 0 IS 0 4 THE INPUT }HAGE A p p l i c a t i o n of the c l u s t e r i n g algorithm Figure f3.3.13 a o o ° ° o o ° O 0 o o & o o ° a DETECTED SURFACE A p p l i c a t i o n o f the c l u s t e r i n g algorithm Figure f3.3.13 a <?0 # 0 0 O Q o Q 0 DETECTED & SURFACE A p p l i c a t i o n o f the c l u s t e r i n g algorithm Figure f3.3.13 •0- DETECTED SURFACE A p p l i c a t i o n o f the c l u s t e r i n g algorithm Figure f3.3.13 86 * (grad i) * * * * H— * * * * * * * * * * * * * * * * * * > * T T _ + ~ + ~ _ + ++ _+ =- T- _ _ ++ ~ -+ _=- TTT- +-+ _ _-_ _=+ T T +-= +T T=_ T H—+ T ++ +-_ —_T _-_ T+T -_TT_ TT + + _ ++ _ +=_ _T+_T T T4- T++ T+ H—+ ++ + +T++ T -=_+-_TTT+ =+ ++ T + +_TT+= ++++ T+=-T +-H-TT TT += ++ T T += T+ ++ + +T ++ -TTTT ++ T TT =- +T ++ +TT — T- _-_ ++ _~ T_+ ~ +T 4+ T | ++ += +T- ++ T ++- +T4+ +T TT -_- TT +T+ T+ T+ +_T+T T This i s the input image + + + + T This i s the input image ok? 87 * FREE SPACE EXPAND * * * * * * * * * * * +- _ + + + + + + T T=_ ~_ —_ + * T T _~_ _ + H—+ - + = T _ TT Detected surface Detected surface ok? This surface i s tilted by an angle phi= ±0.767009 about a line an angle sigma_n = -3.964055E-3 from the X-axis Therefore, i t s gradient vector i s given by p = 3.820867E-3 or p = -3.820867E-3 q = 0.963873 q = -0.963873 > > > > +-= T + T +-+ ' * * * * * * * * * > * T > > > > > > _ T_+ + +_ ++ _+ =- T- _ _ ~ -+ _=- TTT- +-+ _ _-_ _=+ T T actual value of phi = ±fl/4 » ±0.785398 actual value of sigma n = 0 88 > > > > > > > > +T > + - > IT + + _ > T-t— T++ T+ > -=_+-_TTT+ =+ -_ ++ > +++TT TT += ++ > -TTTT 4+ T _ TT > T- _-_ ++ _ T_+ > += +T- ++ T > -_- TT > T+ ^_ > > Detected surface > > Detected surface ok? * T > This surface i s t i l t e d by an angle phi= ±1.021549 > about a l i n e an angle thetaO = -0.94459 from the X-axis > Therefore, i t s gradient vector i s given by > p = -1.323798 or p = 1.323798 > q = 0.95753 q = -0.95753 > > actual value o f p h i = ±rf/3 » ±1.047197 > > a c t u a l value o f sigma_n = -tan (SQRT(2)) * -0.955316 > -1 89 > > > > > > > > > ++ TT_ > _ T + _ T T > ++ + +T++ T > + +_TT+= ++-H- T+=-T > T T += T+ ++ + +T ++ > _=- +T ++ +TT — > +T 4+ T | ++ > ++- +T++ +T TT > +T+ T+ > +_T+T > T > Detected surface > > Detected surface ok? * T > This surface i s tilted by an angle phi= ±0.923183 > about a line an angle sigma_n = 0.868427 from the X-axis > Therefore, i t s gradient vector i s given by > p = 1.00908 or p = -1.00908 > q = 0.854031 q = -0.854031 > > actual value of phi = ±ir/3 » ±1.047197 > actual value of sigma_n = tan (SQRT(2)) » 0.94459 > -1 90 D e t a i l s of the implementation The process of detecting surface s l a n t from texture i s composed three major steps in t h i s program: load the image, segment the image i n t o regions corresponding information for for each to surfaces, and f i n a l l y surface. the pre-processing of illustrated in of Figure the compute the slant The "load image" module i s responsible input f3.3.14. image. The entire process is The purpose of the supervisor i s two- f o l d : i t must maintain the flow of c o n t r o l and i t must transform data i s f i r s t loaded. This The supervisor then s t r u c t u r e s to allow communication between modules. Flow of control is simple. The image information i s then passed to the region detector. passes one region at a time to the gradient vector c a l c u l a t i o n routines. The real need for the supervisor receives the necessary information. in Figure f3.3.15. i s ensuring that each module The data s t r u c t u r e s used are From the flow of c o n t r o l diagram, we see that the maximin c l u s t e r algorithm, f o r example, requires a l i s t input data. Output However, a l i s t of c l u s t e r e d moments i s of structure is Therefore, the fourth element a "texel" data s t r u c t u r e . of the as no supervisor region. then "moments" This element i s simply c a r r i e d along (but otherwise ignored) by the maximin c l u s t e r The moments i n computing the gradient vectors since they are not used nor even needed f o r t h i s task. data of would c o n s i s t of a l i s t of c l u s t e r s , each c l u s t e r being a l i s t of moments. help shown algorithm. " e x t r a c t s " the t e x e l s from each c l u s t e r to form a / < 1 Supervisor |< /->—/ I I I I I I \ \ < \ image I v I v I Length and | I Direction I I calculation | Compute moments I L-0-list moments list v v I Least-squares I f i t t o an I ellipse Maximin cluster algorithm I | I I I | I I image I I I I Load image I I clusters I I I I | |- ->--/ I I a,b,6 I v I Ellipse I parameters I to gradient I vector v I (p,q) V Flow of Control o f the M i c r o - s t r u c t u r a l A n a l y s i s Algorithm Figure f3.3.14 92 I image I I texel texel . . . texel | I point point . . . point I I I x yI I moment-list I I I moments moments . . . moments I I I Ixx ^yy ^xy t e x e l I I clusters I I I moment-list moment-list . . . moment-list | I L-6-list I I I L-d L-d . . . L-d I I length 6 | Data Structures f o r the M i c r o - s t r u c t u r a l A n a l y s i s Algorithm Figure f3.3.15 93 Conclusions We have seen that surface s l a n t can be computed with analysis o f the t e x e l s i n an image o f the surface. p o s s i b l e under the assumptions planar, that exactly that structural This i s found to be the surfaces one micro-structure a i n the scene are i s used, that the micro- s t r u c t u r e i s randomly rotated before being placed on the surface, that to yield a l i s t of the (orthographic) texels. The t i t l e perhaps the algorithm image o f the s e c t i o n i t would statistical i s " S t r u c t u r a l Approaches", but should be examined a l i t t l e more c l o s e l y to see j u s t why i t should be considered While i s pre-processable and be structural. incorrect (probabilities or t o say that other the technique statistical values is are not c a l c u l a t e d a t any time), i t would be c o r r e c t to point out that i t r e l i e s on s t a t i s t i c a l ^ a s s u m p t i o n s . agree with (Julesz, Schatz 1973) 1 In p a r t i c u l a r , the f i n d i n g s o f t h i s s e c t i o n (Schatz,1977) hypothesis restricted concerning version texture of Julesz' d i s c r i m i n a t i o n . That i s , the data, L - 0 - l i s t , that i s used t o c a l c u l a t e the surface's gradient vector corresponds to the second order s t a t i s t i c s Schatz. or used by J u l e s z and We a l s o r e s t r i c t e d ourselves to those points connected by edges diagonals (lines and v i r t u a l l i n e s (Schatz,1977)). For d e t a i l s o f the work by J u l e s z and by Schatz see Chapter 2. The d i f f e r e n c e between our approach treatment o f the L - 0 - l i s t data F. their approach as a f u n c t i o n , L = F ( 0 ) . i n t e r e s t e d i n how o f t e n a given p o i n t , approaches and (L,0), occurs, as i s our We are not statistical a r e , rather we are i n t e r e s t e d i n the nature o f the f u n c t i o n , I t i s t h i s i n t e r e s t that makes our approach a s t r u c t u r a l one. 94 3.4 STRUCTURAL APPROACHES; THE MACRO-STRUCTURE In the l a s t section an algorithm was developed for detecting surface s l a n t from an image which has been pre-processed to y i e l d a l i s t of t e x e l s , where information. textures each t e x e l had a s t r u c t u r e containing surface s l a n t This pre-processing stage i s a v a l i d examined in the last section, unconnected micro-structures, but i t i s not For example, the square texels in and useful. the the line for the perhaps, for the except, possible Figure d i s c e r n i b l e ( i t would be necessary to compute etc.), assumption for f3.4.1 a l l images. are not easily i n t e r s e c t i o n s of lines, t e x e l s of f i g u r e f3.4.2 do not appear to be very Indeed, the u s e f u l information i n both cases seems macro-structure viewed as being algorithms the texture. segments only. Many successful (Horn, 1971) so the t e x e l d e t e c t i o n assumption now than i t did before. modified Hough transform, f o r In analyzing l i e in In t h i s case, the t e x e l s can be have been proposed ( S h i r a i , 1973) Clowes, 1973) foundation line of to the the sits section, line finding (O'Gorman and on a firmer one technique, a macro-structure will be examined. " G r i d - l i k e " Textures It will be assumed that the image i s of a s i n g l e surface, r e l y i n g on the texture d i s c r i m i n a t i o n work described i n Chapter 2 to do so. micro-structures are r e s t r i c t e d to l i n e segments There may of The a r b i t r a r y length. be several such micro-structures f o r any given image. These micro-structures are placed on the l i n e s of an i n v i s i b l e square g r i d fixed s p a t i a l frequency. of the g r i d . of This frequency i s the same i n both d i r e c t i o n s Both Figures f3.4.1 and f3.4.2 are examples of this kind "complete" g r i d texture Figure f3.4.1 "line-segments" grid texture Figure f3.4.2 "boxes" grid texture Figure f3.4.3 98 of texture. Another example i s shown i n F i g u r e f3.4.3. c l a s s of textures i s very s i m i l a r to that of Chapter 2.2. The (Render, 1979) this discussed case f o r Render's t e x t u r e s . phenomenon o f converging are r e g u i r e d , which i s not Render uses Hough t r a n s f o r m s p a r a l l e l l i n e s i n persepective t h e s i s i s r e s t r i c t e d to orthographic images. Since images t h i s f e a t u r e cannot Nevertheless, domain t e x t u r e s t h a t o t h e r f e a t u r e s can e a s i l y be e x p l o i t e d , as h i n t e d i n Chapter The Hough transforms are so natural p l a n here i s t o examine the image and determine the image of obtained That i s , the nature o f the Of c o u r s e , considered. t h a t the m i c r o - s t r u c t u r e determined by texel. preparation, analysing r e l a t i o n s necessary Note some way that This will be done by texels using the t o do for Then, assuming i s a square, the g r a d i e n t o f the s u r f a c e can the the transformation next few from paragraphs micro-structure will develop be to the so. l e n g t h s o f the s i d e s o f such t e x e l s are r e l a t e d i n t o the normal d i s t a n c e s between the l i n e segments. r e a d i l y measurable i n the Hough t r a n s f o r m o f the and the information The details o f t h i s r e l a t i o n a r e r e q u i r e d because the normal d i s t a n c e s mentioned |LjJ only t h i s p a r t i c u l a r f i g u r e w i l l a c t u a l l y c o n t a i n such t e x e l s ; from a r h o - t h e t a Hough t r a n s f o r m o f the image. In was of the proposed program w i l l be r e q u i r e d t o " h a l l u c i n a t e " images this nature images o f the square m i c r o - s t r u c t u r e s o f F i g u r e f3.4.3. other for be 2.2. the p a r a l l e l o g r a m t e x e l s as if t h e y e x i s t e d . an the t o e x p l o i t the r e l i e d on. of in t e x t u r e examined i n t h i s t h e s i s i s d i f f e r e n t i n t h a t a square g r i d and a f i x e d s p a t i a l frequency this Note t h a t image. 11-21, o f the s i d e s o f a p a r a l l e l o g r a m are g i v e n The by: are lengths, 99 |L]J = Idjl/cosoi |L I = 2 |d l/cosor 2 and 2 where Id^l i s the normal distance between sides o f length | L | 2 |d | i s the normal distance between sides o f length IL^I 2 01 i s the angle between L4 and the normal to L 2 ( i . e . between L4 and dj) 0 2 i s the angle between L and the normal to 2 ( i . e . between L 2 and d ) 2 This i s demonstrated i n Figure f 3 . 4 . 4 . It will be seen that | d j | and i t s d i r e c t i o n , 0 j , can be computed from the Hough transform of the image. The goal i s to use these values to determine the shape o f the t e x e l s and, from t h i s and the knowledge o f the micro-structure shape, to determine the gradient o f the surface. Lj_ i s normal t o d f3.4.5, 2 and L 2 i s normal to dj_. the, d i r e c t i o n s o f L i and L , p i and p 2 So, r e f e r r i n g to Figure 2 r e s p e c t i v e l y , are given by e + tf/2 i f e2 <0 e - ir/2 i f e2 >0 2 Fi = 2 and Q 1 + ir/2 i f Bi < 0 F2 = 01 - ir/2 i f 0i > 0 where 0j i s the d i r e c t i o n o f d j . I t w i l l be seen s h o r t l y that d} and 0j are e a s i l y obtained from the Hough transform. to I t i s , therefore, simple c a l c u l a t e the c a r t e s i a n co-ordinates o f an " i d e a l i z e d " t e x e l , one The relationship between Figure f3.4.4 and d^ 101 7" //•I a Illustration of u^and u Figure f 3 . 4 . 5 2 102 corner of which is at the origin, from the polar co-ordinates, (Li,pi) and (L ,p ). If p 2 The of P are interpreted to be cartesian vectors representing 2 2 columns < p i , we can represent the texel by the matrix the sides of the texel. the square So P will be viewed as the picture or image micro-structure. Now, (Mackworth, knowing the "true shape" of a "surface" can deduce "texel"). the gradient vector (read of of 1974) has shown that, "micro-structure"), one the surface from i t s image (read In this case the true shape is given by: and the apparent shape is given by P (S for square, P for picture). So the applying task of determining Mackworth"s algorithm surface to S slant and P. is accomplished by The details involved in extracting the measures mentioned w i l l now be discussed. The application of theorem 3.4.1 |L]_|, IL2I, p i , and s t i l l necessary to p is required to get the since a texel may not exist. 2 compute d^ and d, 2 the values of However, i t is normal-distance-between- parallel-lines vectors. Note first that i t is a property process that line segments map into line of the orthographic imaging segments and parallel line segments map into parallel line segments. This assures that the domain of discourse is not vacuous. The intention is to extract transform (see Chapter di and d 2 from a rho-theta 2 for details of the transform). Hough So each line 103 segment is first parameterized in terms of rho and 0. In our implementation this step must actually be carried out since the input i s a list of line-segments represented as a l i s t of end points (the data structures used are described later in this section). However, i f the input image i s in the form of an array of pixels, then i t is conceivable that the line detection stage, assumed in this thesis, w i l l be performed with See Chapter 2 for details the aid of a rho-theta Hough transform. of using the Hough transform as a line finder. not be necessary representation accumulation to used reconvert in this points in the data thesis. rho-theta into Input space, In this as case the i t would endpoint list may simply be the this i s precisely the information we want. So, having done this, the broken lines vanish only solid lines and result in the parameterization For example, a polar- plot of the parameterization of Figure f3.4.6 is shown in Figure f3.4.7. Notice that this "underlying" transform Figure is exactly that f3.4.6. Each of the complete set of parallel lines in the image contains identical, unique to the set, values of theta (0). It pointed out that the normal grid distance between lines is now i s simply the difference, delta-rho, in the value, rho, between adjacent points in the transform. This task, then, is simple; group the and, for parameterized by 0 each group, measure delta-rho. Then d^ and 62 are set to the the two delta-rhos and 0j and © 2 are set to the the points transform. corresponding 0s from The angles u^ and U 2 are then set to the complements of © 2 and ©^ respectively. Then 104 • • • D D D n p•aaa n S• a D D ! D D Slanted surface textured with "boxes" grid Figure f3.4.6 105 T 6SI.UE2 P o l a r p l o t of Hough transform Figure f3.4.7 o f Figure f3.4.6 i I 106 oi = Hi - e l and = H2 " C2 e 2 (see theorem 3.4.1 and Figures f3.4.4 and f3.4.5 again) F i n a l l y , L]_ = d]_ / cos c?i L = d 2 / cos 2 a 2 as d i c t a t e d by theorem 3.4.1. described previously. The matrix P is then constructed as Then using a s p e c i a l i z e d v e r s i o n of Mackworth's algorithm (see the appendix to t h i s s e c t i o n ) , the amount of s l a n t , jzJ, and the d i r e c t i o n of the gradient vector, a are c a l c u l a t e d . Results This system has been implemented and tested on several images. We found the r e s u l t s to be somewhat more accurate than the r e s u l t s of the s e c t i o n on m i c r o - s t r u c t u r a l a n a l y s i s . and a n In that s e c t i o n , the angles were obtained to w i t h i n ±0.09 radians. implementation obtained the The macro-structural a n a l y s i s angles tf and a to w i t h i n ±0.01 radians. This d i f f e r e n c e i n accuracy may be a t t r i b u t e d to the s t a t i s t i c a l of the algorithm of that s e c t i o n . No such s t a t i s t i c a l assumptions are made here (the assumption of "enough" t e x e l s i s not made nor are such as cr n guessed at.) nature values Some sample runs are given on the f o l l o w i n g pages. The supervisor entire serves algorithm is illustrated be figure f3.4.8. the same purpose here as i n the l a s t s e c t i o n . n o i s e l e s s image, the values of the 0s would in identical. and delta-rhos for each The For a group Due to noise, however, i t was found necessary to 107 calculate the value of theta for each group's centroicTand the average value of delta-rho. The data-structures used are illustrated in figure f3.4.9. Note that the "image" data structure is the same as except in the last section, that each texel contains only two points, the end-points of each line segment. Two sample runs are shown on pages 110-111. 108 / < cluster 1 Supervisor |<- I / >~/ V I cluster \— — < — \ I I / I I I calculate I I picture I I matrix P I V \ I v V I I I I parameterization I V V e I I I I find | | find I I average I I c e n t r o i d I I delta I I theta I I rho I P I Mackworth's | I Algorithm | + I cluster I I about I I Parameterize I I l i n e segments I -/ I I image I I Load image output I V W,a) Flow of Control f o r the Macro-structural A n a l y s i s Algorithm f i g u r e f3.4.8 I image I I I texel texel . . . texel I I I point point | I Ix yI I parameterization I I I rho-theta rho-theta . . . rho-theta | I I rho e I I cluster-pair I I I parameterization parameterization I IPI I I row row I I Ix yI Data Structures f o r the Macro-structural A n a l y s i s Algorithm Figure f3.4.9 * (supervisor (clusters (parametrize (image> * THERE ARE 1 PLOTS IN THE FILE. * ENTER NUMBER OF PLOT TO BE DISPLAYED. * 1 * * VECR CONTAINS EIGENVECTORS * 0.710198 0.704001 * -0.704002 0.710199 * . * EVR CONTAINS EIGENVALUES * 4.417268 2.195629 * * * > The actual value of phi = ±1.047196 * > The actual value of sigma = -0.785398 * * (supervisor (clusters (parametrize (image> * THERE ARE 1 PLOTS IN THE FILE. * ENTER NUMBER OF PLOT TO BE DISPLAYED. * 1 * * VECR CONTAINS EIGENVECTORS * 0.881348 -0.472472 * 0.472467 0.881346 * EVR CONTAINS EIGENVALUES * 17.906174 14.963252 * * 1 p P 1p P 1 p P 1 p P 1 pP 1 p P > * > P P P P P P p p p. p p p n phi = ±0.581486 sigma = 1.078706 * > The actual value of phi = ±0.523598 * > The actual value of sigma = 0.942477 * L-l P P P P P P P P P P P P 112 4. AN INTERPRETATION OF THE RESULTS 4.1 SUMMARY The previous chapter examined texture from three different points of view: - statistical analysis - micro-structural analysis - macro-structural analysis Section 3.1, the introduction to the chapter, defined "orthographic projection" property and of proved this a theorem projection. illustrating the foreshortening It was also noted that this property is not sufficient to distinguish between Necker reversals of a scene. Statistical approaches to detecting measures were discussed in Section 3.2. of surface slant from texture These measures were in the form 2x2 co-occurence matrices and were applied to images of regular dots and of circles. statistical It was concluded techniques that such a blind application of is not very useful to the problem of detecting surface slant, due to data from complex images that proved d i f f i c u l t to interpret. no A theorem was then proved stating that there is directionality in the co-occurence matrices computed for images of truly random textures. It was concluded from this theorem that co-occurrence matrices can not be used to determine surface slant from such images. Section 3.3 examined the analysis of the texels structures. It 1 was assumed that each texel contained a line (or virtual line) which identifiable as micro-structure. the image of a is given line (or virtual line) in the In the algorithm developed within this section, the 113 presence of a sufficiently long diagonal was required to assure an identifiable line in the texel. The use of the macro-structure of a texture was examined in Section 3.4. Grid-like textures were assumed; they were analysed by determining the shape of the texels as _if they existed. This applying a was accomplished by Hough transformation to the image and retrieving the needed information from the resulting transformed image. Then, assuming the micro-structure to be a square, the gradient of the surface was computed with an algorithm due to Mackworth. 4.2 FALLACIES, OR WHY At first glance, 3.2, 3.3, AND 3.4 ALL START WITH 3 these 3 approaches are quite independent of one another. A closer look reveals marked similarities in the underlying assumptions. The Fallacy of the Statistical-Structural Dichotomy The theorem described texture 3.2.1 as of randomly, uniformly distributed dots considered in (the one non-directionality of having a random micro-structure textures) consisting of can a dot of negligible size and a macro-structure defined as randomly micro-structures of Sections 3.3 and on a surface. In light be distributed 3.4, neither of these structures is useful. Hence, i t is not surprising that statistical techniques f a i l on this image as well. 3.2, Throughout Chapter the use of second order statistics was "blind", that i s , they were applied over the whole image just to "see what could be seen". 114 Admittedly, not much i s seen. But suppose that more judicious use i s made of them, as i t i s in (Schatz, 1978). Schatz (see Chapter 2 for details) considers only the second order statistics taken for end points of lines or "virtual" lines. that i s calculated This i s , effectively, the same information and used in Chapter 3.3. In fact, this thesis maintains that second order statistics are best structures in the image. of as dipole It is true that i t would be hard to extract just what i s needed from Schatz data 1 diagonal" thought since the concept of "longest w i l l get buried in a l l the other length measurements and that Schatz i s interested in the occurrence statistics, whereas our interest is in the length as a function of direction, but these are largely matters of proposed application. So Schatz' statistical work i s , analysis in some sense, micro-structural since statistics are confined to pairs of points connected by structures (lines) and the micro-structural analysis (Chapter in some sense, statistical since the L-0-list 3.3) i s , can be reegarded as statistical measures taken of the texels. The Fallacy of the Micro/Macro-Structure Dichotomy Similarily, the distinction becomes less well between micro- and macro-structure defined as i t i s examined. There was l i t t l e effort involved in distinguishing micro- from macro-structure in Chapter The texels were simply considered to be the "connected" line segments (although we did wave our hands problem arises 3.3. when and allow the connections unconnected texels). The are not so convenient. Figure f4.2.1, for example, may be considered to be dots arranged in a complex Hierarchical texture I Figure f4.2.1 116 macro-structure. However, i t may be more profitable to consider i t as square texels, made up of dots, arranged in a simple namely a square. depends macro-structure, Note that the labelling of macro- and micro- structure on the scale of the image. For example, Figure f4.2.1 may just be a micro-structure of Figure f4.2.2. In fact, this expressed thesis proposes that a macro-structure i s best as a micro-structure, and this is precisely what is done in Chapter 3.4 when the dimensions of a parallelogram texel are found, even though i t may not exist. This thesis also maintains that the labels "micro-structure" and "macro-structure" are misleading and may be forcing the acceptance of an unnatural view of texture. Chapter 2.1 have fallen into Certainly, a l l of the views discussed in this trap. Since there i s no real distinction between micro- and macro- structure, i t is suggested that i t would be best to express a texture as nested structures, a l l of which are expressed as micro-structures. For example, Figure f4.2.2 should be described as "a (square of (squares of (squares of dots)))". then be possible for a program It would (or user) to decide on what level a "texel" should exist. Under this interpretation, then, a l l of the techniques of the chapter are structural. They last appear different at f i r s t because each constructed an a r t i f i c i a l boundary to the level of structural analysis i t would undertake. Now, the claim is not made that i t is impossible to do any sort of non-structural statistical analysis of texture, but i t i s claimed that such an analysis has no place in the domains this thesis i s restricted to. This appears to be due to the nature of the orthographic imaging process and is discussed in the next chapter. 117 o e . 9 4 * O « 9 • o o Hierarchical texture II Figure f4.2.2 O 118 5. Texture has been CONCLUSION shown surface slant in orthographic structural analysis to be a useful cue for the detection of images. techniques to Texture i t , determining relying on the "foreshortening" property process (see theorem 3.1.1). is used of the by applying surface slant by orthographic imaging In a l l cases this has been done without considering texture gradient at a l l . As mentioned in Chapter 2, a l l previous works described have used texture gradient since they assumed a perspective imaging process. Similarily, useful in projection. the purely domain statistical of techniques apparent textures were found not to be under orthographic Let us point out, however, that i f the statistics (notably f i r s t and second order statistics) changed in some determinable way with the distance of the textured object from the viewer, then surface could be determined by a purely statistical analysis. This _is the case for perspective statistics 2). slant images (texture This is not the and Bajcsy uses the change in first-order gradient) in her work, as does Gibson (see Chapter case for orthographic projections since the location of the viewer is indeterminate on the Z-axis (see Chapter 3.1). We have put forth several opinions suggesting a "nested" structural description of texture. It was found that this notion clashes with previous definitions (see Chapter 2) which defined texture in terms of a micro-structure and a macro-structure. definition makes d i f f i c u l t i e s such It was also found that as new texel determination vanish by making them non-problems. One reason for the lack of in the greater progress texture and the lack of acceptance of texture by related concerns in scene analysis is the unavailability of such a definition. It is in the 119 s p i r i t of providing a better basis for texture research, then, that we propose i t . 5.1 DIRECTIONS FOR FURTHER RESEARCH Extensions Immediate extensions of this work would be to relax the various assumptions made throughout the paper. Such extensions might include: Incorporation of "Real-World" Textures This would basically take the form of introducing variation into the s t r i c t l y structural textures mentioned. For example, random, many-sided polygons distributed uniformly over a surface could simulate or plastered-wall type of texture texture. studied cork-board Pebble walls and concrete walks are of the in Chapter 3.3 but with uneven "texels". However, many man-made surfaces, such as tiled floors, woven cloth, and windowed building walls, are textured in the way studied in Chapter with l i t t l e or no changes. 3.4 These, too, should be studied more closely. Non-planar Surfaces This would probably present a very d i f f i c u l t problem for the class of texture examined in Chapter available "locally" in the 3.3 image. since In so little on is Chapter 3.3, we computed the surface slant from texture measures made over the relied information entire surface. We many such measures to accurately f i t an ellipse to the data. Hence, the technique of that chapter would not be applicable to non- 120 planar surfaces. As (Kender, 1979) also points out, such processing would be in the manner of (Woodham, 1977). However, non-planar surfaces should present the are. texture little difficulty i f i s "continuous", as the grid-like textures of Chapter 3.4 This class of textures then, would be a logical starting point for such work. Such textures are often used in line drawings by artists and workers in computer graphics precisely because the surface gradient and curvature are so easily recovered. Perspective Projections This paper has dealt solely with orthographic projections and, while this is a good approximation to many "real" images that one may want to deal with, i t is not a valid assumption for a l l cases. single-camera, fixed-viewpoint images are perspective should be able to deal with these. algorithms they It i s not clear images and we to us how the in this paper could be generalized but we do not doubt that could projections be since the foreshortening have aspect of orthographic i s also a part of perspective projections. Generalization to perspective images is a promising Kender In fact, a l l discovered, extension, for, as Bajcsy and there is much more information present due to the fixed position of the viewer. 121 Formalize the D e f i n i t i o n Our d e f i n i t i o n of texture as "nested" s t r u c t u r e s i s very We feel that formalization. restrictions this definition is important I t would then be necessary to enough explore informal. to the require power and of the d e f i n i t i o n and to apply i t to such tasks as texture d e s c r i p t i o n and generation. A p p l i c a t i o n to the Origami World The origami world was introduced to i l l u s t r a t e our Chapter 1. in However, the a p p l i c a t i o n of our work to t h i s domain i s not as s t r a i g h t forward as we may have difficulty motivations i s due mainly to led the the reader inability of to believe. The texture a n a l y s i s to d i s t i n g u i s h between Necker r e v e r s a l s . We are not saying that i t should, though. look Nevertheless, t h i s does introduce some complications. again at our "cube" example. gradient us Figure f5.1.1 i l l u s t r a t e s the s i x gradient values that could be obtained from such a cube. to determine that the Let configurations for But how are we the labelling of Figure f5.1.1 are given by Figure f5.1.2 a) and not by Figure f5.1.2 b)? The answer i s that we must look again at the l a b e l l i n g and see which of the p o s s i b l e gradient c o n f i g u r a t i o n s are "consistent" (Mackworth, 1973). Note that none of the c o n f i g u r a t i o n s may be c o n s i s t e n t . we have image. determined that the labelling In this case, i s not c o r r e c t f o r the given 122 "cube" labelling and gradients Figure f5.1.1 0 A Two "possible" gradient configurations of Figure f5.1.1 Figure f5.1.2 124 5.2 SYNOPSIS Summing up, then, several algorithms operating on several of textures have been presented. are not actually distinct, It has been decided that these classes but that the distinction i s forced by the currently held definition of texture. have proposed a new classes definition In light of texture of these results, we which avoids this class distinction. Several directions for further study, including an application to a problem which suggested. served as a motivation for this thesis, have been It i s hoped that the reader w i l l think seriously about at least one of these problems, for only by confronting such problems (s)he gain will a real feeling for the problems inherent in determining the nature of a scene from i t s image. 125 6. APPENDICES 6.1 APPENDIX TO 2.2 D e r i v a t i o n of the rho-theta Equation of a_ Line R e f e r r i n g to Figure f6.6.1, we note that a point the N. X = (x,y) i s on l i n e p r e c i s e l y when the v e c t o r , X-N i s perpendicular t o the vector, That i s , when, (X-N)'N = 0 X«N - N'N = 0 X-N = N«N X«N = |N| 2 X'N = r h o 2 (x,y)•(rho*cos©,rho*sin©) = r h o x*rho*cos© + y*rho*sin© = r h o 2 2 xcos© + ysin© = rho Which i s therefore the rho-theta equation of the l i n e . Rho-theta equation of a line Figure f6.1.1 127 6.2 APPENDIX TO 3.3 Least Squares F i t of Data to an Ellipse Theorem 3.1.1 gives us good reason to believe that our data, L-0l i s t , l i e s on ellipse with the equation: F(6;a,b) = r 2 = (a b ) / [ a s i n (0-cr ) + b cos (0-c ) ] 2 2 2 2 2 where a (1) 2 n n is the angle that the major axis of the ellipse makes with the n line, 6 = 0 . Our task here i s to determine a and b. In order to do so, i t w i l l be convenient parameters. to express F(0) in a form that depends linearly on i t s Thus, l e t us not use F(0) = r , but rather F(0) = 1/r . 2 2 Then F(0;a,b) = 1/r = [sin (0-a )] / b + [cos (0-o )] / a 2 2 2 2 n F(0;c ,c ) = ctfi(9) 1 where + c rf (0) 2 c^ = l/b2 2) c = 1/a 2 2 n (2) 2 2 ^ ( 0 ) = sin (0-a ) 2 n tf (0) = cos (0-a ) 2 2 So b. n we w i l l be content to determine c^ and c and, from them, a and 2 To get a least-squares approximation, we wish to minimize the sum of the squares of the errors. That i s , we wish to minimize 128 n = 2 [fi - F(e ;c ,c )] i=l E(c c ) lf 2 i 1 2 2 (Conte and de Boor,1965; pg.241-246) where = l/L^ 2 n = number of elements in L-d-list (Li,6i) is the i element of L-d-list t n It should be pointed out that we have made a insisting on the linearly dependent form. major compromise by Ideally, we would like to minimize n 1 [Li - r ] . 2 1=1 With F(0) = 1/r we are actually minimizing 2 n 2 [l/Li 1=1 - 1/r ] . 2 2 2 This "weights" the small values of Lj and r more than large values, hence the data w i l l f i t the minor-axis part of the ellipse found by this method better than the rest of the ellipse. Nevertheless, we will continue using this method because of i t s ease of applicability. Since E(C},c ) is continuously differentiable with 2 and c , 2 we can detect the minimum at the point where the 1 derivatives vanish. dE(c ,c )/dc 1 2 respect st to partial That is n = T d[fi - F ( 6 c , c ) ] / d c i=l 2 i i 1 2 i n = "2 2 [ f i - F(e c ,c )] dF(6 ;c ,c )/dcj i 1 2 i 1 2 c^ (3) 129 Now = d[(cinJi(ei) + dF(e ;c ,c )/dCj i 1 2 c **2( i)]/dCj e 2 =^j(6i) (4) So s u b s t i t u t i n g (4) i n t o (3) we get n -2 T [fi - F(e c ,c )](zJ (e ) = 0 i=l i 1 2 i i And s u b s t i t u t i n g (2) into t h i s we get n n n c i l ^ j ( 6 i ) ^ i ( 6 i ) + c 2 r f j ( e i ) jtJ (9i) I f i ^ j ( 6 i ) i=l i=l i=l = 2 2 Hence we have a system o f two l i n e a r equations (j=l,2) i n two unknowns (ci,c ). 2 This system i s then solved using Gaussian e l i m i n a t i o n (Conte and de Boor,1965;pg 110-127). 130 6.3 APPENDIX TO 3.4 Orientation of a Surface from True Shape and Projected Shape This is taken nearly verbatim from (Mackworth, 1974). The orthographic imaging process may be given as a matrix transformation by: P= (tilt)(rotation)(scale)F where P is of dimensions 2*(n-l) and contains the co-ordinates of a l l n vertices except the pair at the origin. F is like P but contains the vertices of the true face. 0^ Ik (scale) = [ I 0 k (rotation) = cos(r) sin(r) -sin(r) cos(r) < fcos(o) (tilt) = ; ^sin(a) \ -sin(a) \ fcos(fi) cos (a) J ^0 o\ / cos (a) sin (a) 1^ y-sin(a) cos (a) See Figure f6.3.1 (also from (Mackworth, 1974)). In our case, F represents a square and is given by: 1 F =[ 0 0 1 | which i s the identity matrix So P = (tilt)(rotation)(scale). direction and magnitude of Now from P, we would like to obtain the the gradient vector, a and tan(0) "squashing" effect of the orthographic projection Figure f6.3.1 132 respectively. We f i r s t compute r as follows: (tilt)(rotation)(scale) = P (tilt)(scale)(rotation) =P (tilt)(scale) = P(rotation)_ / j l l 312 \ 321 Since (tilt) and 1 322 (scale) commute and are both symmetric then the right hand side must also be symmetric: 1 hn ^ 21 h 12\ /cos(r) -sin(r) 22/ ysin(r) cos(r) n h That i s , -pjjsinCr) + p cos(r) = p icos(r) + p s i n ( r ) 12 so tan(r) = ( p 1 2 2 22 - P21) / ( P n + P22) Now, from J we compute the eigenvectors and the eigenvalues be Ei = (cos (a), sin (a)) and X i = kcos(jrf) E2 = (-sin (a), cos (a)) and X2 = k (see Figure f6.3.1 again) Hencetf= cos- 1 (V]/.X2) and a = (E]_ (1)/E (2)) . 2 which must 133 Bibliography Bajcsy, R. Computer identification of textured visual scenes. Technical-report AIM-180, Stanford Artificial Intelligence Laboratory, Stanford University, Oct. 1972. Bajcsy, R. Computer IJCAI3(1973),572-579. description of textured Bajcsy, R. and Lieberman, L. Texture gradient as a depth cue. Graphics and Image Processing 5,1 (March 1976),52-67. surfaces. Computer Caelli, T. and Julesz, B. Perceptual analyzers underlying visual texture discrimination: part I. Biological Cybernetics 28 (1978),167-175. Carton, E. J.,Weszka, J . S., and Rosenfeld, A. Some basic texture analysis techniques. Technical-report tr-288, Computer Science, University of Maryland, Jan. 1974. Clowes, M.B. On (1971),79-116. seeing things. Artificial Intelligence 2,1 Conte, S.D. and deBoor, C. Elementary Numerical Analysis: an Algorithmic Approach. McGraw-Hill, New York, . Davis, L.S., Johns, S.A., and Aggarwal, J.K. Texture analysis using generalized co-occurrence matrices. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-1,3 (July 1979), 251-259. Deutsch, E.S. and Belknap, N.J. Texture descriptors using neighborhood information. Computer Graphics and Image Processing 1,2 (Aug. 1972),145-168. Duda, R.O. and Hart, P.E. Use of the Hough transform to detect lines and curves in pictures. CACM 15,1 (Jan. 1972),11-15. Dyer, C. R. and Rosenfeld, A. Fourier texture features- suppression of aperture effects. Technical-report tr-391, Computer Science, University of Maryland, July 1975. Dyer, C.R., Weszka, J.S. and Rosenfeld, A. Experiments in terrain classification on Landsat imagery by texture analysis. Technical-report tr-383, Computer Science, University of Maryland, June 1975a. Dyer, C.R., Weszka, J.S., and Rosenfeld, A. Further experiments in terrain classification by texture analysis. Technical-report tr-417, Computer Science, University of Maryland, Sept. 1975b. Dyer, C.R., Weszka, J.S., and Rosenfeld, A. Detection of 'hazy anomalies' in Landsat imagery by texture analysis. Technical-report tr-429, Computer Science, University of Maryland, Dec. 1975c. 134 Gibson, J.J. The Perception of the Visual World. Boston,Mass., 1950. Houghton Mifflin Co., Haralick, R.M., Shanmugan, K., and Dinstein, I. Textural features for image classification. IEEE Transactions on Systems, Man, and Cybernetics SMC-3,6 (Nov. 1973),610-621. Hawkins, J.K. Textural properties for pattern recognition. and Rosenfeld,A.,Eds.),347-370. In (Lipkin,B. Horn, B.K.P. The Binford-Horn line finder. Memo 285, Al Lab, MIT, July 1971. Hough, P.V.C. Method and means for recognizing U.S. patent 3,069,654, Dec. 18, 1962. complex patterns. Huffman, D.A. Impossible objects as nonsense sentences. In Machine Intelligence 6(1971), Meltzer, B., Michie, D. (Eds),295-323. Julesz, B. Foundations of Cyclopean Perception. Press, Chicago, 1971. University of Chicago Julesz, B., Gilbert, E.N.,Shepp, L.A. and Frisch, H.L. Inability of humans to discriminate between visual textures that agree in second-order statistics-revisited. Perception 2 (1973),391-405. Julesz, B. Experiments in the visual perception of textures. American ,232 (1975),34-43. Scientific Kanade, T. A theory of origami world. Technical-report cmu-cs-78-144, Computer Science, Carnegie-Mellon University, Sept. 20, 1978. Kelly, M.D. Edge detection by computer using planning. In Machine Intelligence 6(1971), Meltzer, B., Michie, D. (Eds),397-410. Kender, J.R. Shape from texture: an aggregation transform that maps a class of textures into surface orientation. IJCAI-79,475-480. Lipkin, B. and pictorics. Rosenfeld, A. (Eds.) Picture Processing Academic Press, New York, 1970. Mackworth, A. K. Interpreting pictures of polyhedral scenes. Intelligence 4,2 (1973),121-137. and Psycho- Artificial Mackworth, A.K. On the interpretation of drawings as three-dimensional scenes. D.Phil, thesis , University of Sussex, 1974. Mackworth, A. K. Model-driven interpretation in systems. Perception 5 (1976),349-370. Nevatia, R., Price, K., and Vilnrotter, F. IJCAI 79,642-644. intelligent vision Describing natural textures. O'Gorman, F. and Clowes, M.B. Finding picture edges through collinearity of feature points. IJCAI3(1973),543-555. 135 Pickett, R.M. Visual analysis of texture in the detection and recognition of objects. In (Lipkin,B. and Rosenfeld,A.,Eds.),289-308. Rosenfeld, A., Lee, Y.H., and Thomas, R.B. texture discrimination. In Rosenfeld,A.,Eds.),381-393. Edge and curve detection (Lipkin,B. and for Rosenfeld, A. Visual texture analysis- an overview. Technical-report tr-406, Computer Science, University of Maryland, Aug. 1975. Rosenfeld, A. and Lipkin, B.S. Rosenfeld,A.,Eds.),309-345. Texture synthesis. In (Lipkin,B. and Schatz, B.R. The computation of immediate texture. PhD thesis Department of A r t i f i c i a l Intelligence, MIT, Aug. 1977. AIM-426, Schatz, B.R. The computation of immediate texture discrimination. Technical-report cmu-cs-78-152, Computer Science Dept., Carnegie-Mellon University, Dec. 1978. Shirai, Y. A context sensitive line finder for recognition of polyhedra. A r t i f i c i a l Intelligence 4,2 (1973),95-119. Tamura, H., Mori, S. and Yamawaki, T. Textural features corresponding to visual perception. IEEE Transactions on Systems, Man, and Cybernetics SMC-8,6 (June 1978),460-473. Tanimoto, S. and Pavlidis, T. A hierarchical data structure for picture processing. Computer Graphics and Image Processing 4^,2 (June 1975),104-119. Tomita, F., Shirai, Y. and Tsuji, S. Descriptions structural analysis. IJCAI 79,884-889. of textures by a Tomita, F., Yachida, M. and Tsuji, S. Detection of homogeneous regions by structural analysis. IJCAI3(1973),364-371. Tou, J.T. and Gonzalesz, R.C. Pattern Addison-Wesley, Reading,Mass., 1974. Recognition Principles. Tsuji, S. and Tomita, F. A structural analyzer for a class of textures. Computer Graphics and Image Processing 2,3/4 (Dec. 1973),216-231. Waltz, D.L. Understanding line drawings of scenes with shadows. Psychology of Computer Vision, Winston, P. (Ed),19-91. In the Wang, S.,Velasco, F.R.D., and Rosenfeld, A. A comparison of some simple methods for extracting texture primitives and their effectiveness in texture discrimination. Technical-note tr-759, Computer Science Centre, Univ. of Md., April 1979. Winston, P.H.(Ed.) The Psychology of Computer Vision. York, 1975. McGraw-Hill, New 136 Woodham, R.J. A cooperative algorithm for determining surface orientation from a single view. IJCAI5(1977),635-641. Yachida, M., Ikeda, M. and Tsuji, S. regions. IJCAI 79,992-994. Boundary detection of textured Zahn, C.T. Graph-theoretic methods for detecting and describing gestalt clusters. IEEE Trans. Computers vol. c-20,no. 1 (1971),68-86. Zucker, S.W., Rosenfeld, A. and Davis, L.S. Picture segmentation by texture discrimination. IEEE Transactions on Computers C24 (Dec. 1975),1228-1233. Zucker, Steven W. Toward a model of texture. Processing 5,2 (June 1976),190-202. Computer Graphics and Image
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Slant from texture : computational methods for recovering...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Slant from texture : computational methods for recovering surface slant from images of textured scenes Breu, Heinz 1980
pdf
Page Metadata
Item Metadata
Title | Slant from texture : computational methods for recovering surface slant from images of textured scenes |
Creator |
Breu, Heinz |
Date Issued | 1980 |
Description | This thesis examines the problem of computationally recovering or determining the slant of a surface from an image of that surface. Images are restricted to those of planar surfaces produced by orthographic projection. This thesis is concerned only with those cues obtainable from the image texture. These cues arise primarily due to the foreshortening property of orthographic projection. Texture measures have typically been partitioned into three classes: statistical approaches, micro-structural approaches, and macro-structural approaches. In this thesis, measures from each of these classes are used to develop algorithms capable of detecting surface orientation. It is concluded that these three classes are not distinct and, indeed, are artificially rendered by the prevailing definition of texture. A new definition involving nested structures is suggested. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-03-24 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051595 |
URI | http://hdl.handle.net/2429/22461 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1980_A6_7 B74.pdf [ 4.94MB ]
- Metadata
- JSON: 831-1.0051595.json
- JSON-LD: 831-1.0051595-ld.json
- RDF/XML (Pretty): 831-1.0051595-rdf.xml
- RDF/JSON: 831-1.0051595-rdf.json
- Turtle: 831-1.0051595-turtle.txt
- N-Triples: 831-1.0051595-rdf-ntriples.txt
- Original Record: 831-1.0051595-source.json
- Full Text
- 831-1.0051595-fulltext.txt
- Citation
- 831-1.0051595.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051595/manifest