UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Using image hierarchies to interpret LANDSAT data Catanzariti, Ezio 1977

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1977_A6_7 C39.pdf [ 5.68MB ]
Metadata
JSON: 831-1.0051788.json
JSON-LD: 831-1.0051788-ld.json
RDF/XML (Pretty): 831-1.0051788-rdf.xml
RDF/JSON: 831-1.0051788-rdf.json
Turtle: 831-1.0051788-turtle.txt
N-Triples: 831-1.0051788-rdf-ntriples.txt
Original Record: 831-1.0051788-source.json
Full Text
831-1.0051788-fulltext.txt
Citation
831-1.0051788.ris

Full Text

i USING IMAGE HIERARCHIES TO INTERPRET LANDSAT DATA by E z i o C a t a n z a r i t i Laucea In P h y s i c s , U n i v e r s i t y of N a p o l i , N a p o l i , I t a l y 1971 A THESIS SUBMITTED. IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF COMPUTER SCIENCE He a c c e p t t h i s t h e s i s as c o n f a r m i n q to t h e r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA September, 1977 {cj Ezio C a t a n z a r i t i , 1977 In presenting th is thes is in p a r t i a l fu l f i lment of the requirements for an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary shal l make it f ree ly ava i l ab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho la r ly purposes may be granted by the Head of my Department or by his representat ives . It is understood that copying or pub l ica t ion of th is thes is for f inanc ia l gain sha l l not be allowed without my wri t ten permission. Department o The Univers i ty of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date Q*Jc i. I f 7 7 i i A b s t r a c t Most automatic LANDSAT image i n t e r p r e t a t i o n systems have used t r a d i t i o n a l P a t t e r n R e c o g n i t i o n technigues. U s u a l l y each p i x e l i s c l a s s i f i e d i n t o one o f a number of c a t e g o r i e s by examining i t s s p e c t r a l s i g n a t u r e , without regard t o i t s s p a t i a l context. A survey o f such t e c h n i g u e s and Of c o m p u t a t i o n a l v i s i o n technigues from A r t i f i c i a l I n t e l l i g e n c e l e a d s t o the design of a new system that allows the s p a t i a l s t r u c t u r e of the image to c o n t r o l the i n t e r p r e t a t i o n . T h i s c l a s s i f i e r uses a pyramidal, h i e r a r c h i c a l s t r u c t u r e o f images. A number of experiments with the implementation on LANDSAT images of f o r e s t cover show t h a t one can achieve improvements over a c o n v e n t i o n a l c l a s s i f i e r i n both accuracy (number of p i x e l s c o r r e c t l y i n t e r p r e t e d ) and r e a d a b i l i t y (number of r e g i o n s i n the i n t e r p r e t e d image) without s a c r i f i c i n g e f f i c i e n c y . i i i T a ble o f Contents 1. PATTERN RECOGNITION AND LANDS AT IMAGERY 1.1 P a t t e r n Recognition and A r t i f i c i a l I n t e l l i g e n c e i n the LANDSAT Domain....... ,. 1 1.2 Pattern Recognition and LANDSAT Image P r o c e s s i n g : P o i n t by P o i n t C l a s s i f i c a t i o n . . . . . . . .......5 1.3 The Use o f S p a t i a l Information i n LANDSAT Image A n a l y s i s . . . . . . . ....... 19 2. SOME APPROACHES TO SCENE ANALYSIS 2.1 H i e r a r c h i c a l S t r u c t u r e s . . .......26 2.2 Region Merging....... . , 34 2.3 I n t e r p r e t a t i o n D i r e c t e d Segmentation of LANDSAT Images....... .......37 3. USING PYRAMID STRUCTURES IN THE AUTOMATIC INTERPRETATION OF LANDSAT IMAGES ............. ....... 40 4. EXPERIMENTS WITH THE PYRAMIDAL STRUCTURE 4.1 R e s u l t s . . . . . . . . 56 4.2 C o n c l u s i o n s . . . . . . . 76 BIBLIOGRAPHY...... ....... 80 L i s t of T a b l e s 0. Performance of the maximum l i k e l i h o o d c l a s s i f i e r . . . ...56 1. Performance of the s t r a i g h t pyramidal s t r u c t u r e u s i n g f o u r l e v e l s with varying K i . . . . . ....... 60 2. R e s u l t s f o r cases I and I I I of Table 1 a f t e r clean-up with C=2 ........61 3. T o t a l number of p i x e l s c l a s s i f i e d f o r the cases i n Tab l e 1 compared with the p o i n t by p o i n t c l a s s i f i c a t i o n . . . . . . .......62 H. Performance of the s t r a i g h t pyramidal s t r u c t u r e using three l e v e l s with v a r y i n g K i . .......62 5. R e s u l t s f o r cases I and I I o f T a b l e 4 a f t e r the clean-up with C=2...... ...62 6. Performance of the s t r a i g h t pyramidal s t r u c t u r e u s i n g two l e v e l s with varying Ki ...... 63 7. Resu l t s f o r case I of Table 6 a f t e r the clean-up with C=<l....... .......63 8. Number of u n c l a s s i f i a b l e p i x e l s at each l e v e l u s i n g the computed values f o r the d i s p e r s i o n t h r e s h o l d s i n the t e s t f o r homogeneity....... ........ 65 9. Performance of the pyramidal s t r u c t u r e using the t e s t f o r homogeneity with Ta=10, Tb=20, Tc=20... 64 10. Results f o r some o f the cases of Table 9 a f t e r the clean-up with C=2...... .66 11. Performance of the pyramidal s t r u c t u r e using the t e s t f o r V homogeneity with Ta=5, Tb=10, Tc=10.... ......,67 12. Number o f u n c l a s s i f i a b l e p i x e l s at each l e v e l u s i n g Ta=5, Tb=10, Tc=10 at a l l l e v e l s . . . .... 68 13. Results using f o u r l e v e l s o f the pyramid with d i f f e r e n t values f o r the T i at each l e v e l . . . . . .68 14. Some r e s u l t s u s i n g region merging and s p l i t t i n g techniques i n s i d e the pyramidal s t r u c t u r e . . . . . ......69 15. Performance of the re g i o n merging and s p l i t t i n g techniques...... .......71 i v i L i s t of Fi g u r e s and I l l u s t r a t i o n s 1.1 A LANDSAT p i c t u r e . . . . . . .......4 1.2 An Earth Resources Information Tree (from Landgrebe, D. A. Remote Sensing Technology - a Look t o the Future, Symposium on Machine P r o c e s s i n g o f Remotely Sensed Data, Purdue U n i v e r s i t y 1976)..... ......61 1.3 The o r g a n i z a t i o n of a C l a s s i f i c a t i o n System.... ....7 1.4 The e l e c t r o m a g n e t i c spectrum i n the v i s i b l e r e g i o n . . . ...9 1.5 T y p i c a l r e f l e c t a n c e s p e c t r a f o r v e g e t a t i o n , sandy s o i l , c l a y s o i l and water, with LANDSAT HSS bands shown (from Image A n a l y s i s System Handbook, MacDonald, D e t t w i l e r and A s s o c i a t e s L t d . , Canada 1977) .....10 1.6 P i x e l by p i x e l p l o t o f i n t e n s i t y i n band 6 versus i n t e n s i t y i n band 4 (from Image A n a l y s i s System Handbook, MacDonald, D e t t w i l e r and A s s o c i a t e s L t d . , Canada 1977)..... 11 1.7 E l l i p s e s of C o n c e n t r a t i o n f o r o l d growth, new growth, recent l o g g i n g and water (from S t a r r , D. W. Automatic I n t e r p r e t a t i o n of Landsat Images using Context S e n s i t i v e Region Merging, M.Sc. T h e s i s , U.B.C. 1976)..... .......12 1.8 A D e c i s i o n Tree scheme f o r c l a s s i f i c a t i o n (from Fu, K. S. Pattern Recognition in Remote Sensing of the E a r t h ' s Resources, IEEE Trans. on Geoscience E l e c t r o n i c s , V o l . GE. No.1 1976) ....... 18 1.9 A H i e r a r c h i c a l graph model o f a LANDSAT scene (from Fu, K. S. P a t t e r n R e c o g n i t i o n i n Remote Sensing of the Earth's Resources, IEEE Trans. on Geoscience E l e c t r o n i c s , V o l . GE. No. 1 1976)...... ..'.....'24 3.1 The ground t r u t h map..... ...42 3.2 An i n f o r m a t i o n t r e e f o r the scene.... .....43 3.3 L e v e l 1 of the pyramid ......45 3.4 L e v e l 2 of the pyramid..... ...... 47 3.5 L e v e l 3 of the pyramid..... ...... 47' 4.1 Point by point c l a s s i f i c a t i o n 58 v i i 4.2 The c l a s s e s of i n t e r e s t t r a c e d i n the d i g i t i z e d ground t r u t h data . . .......59 4.3 Example of c l a s s i f i c a t i o n u s i n g f o u r l e v e l s of the pyramid {case I I I of Table 2 ) . . . . . . 73 4.4 Example of c l a s s i f i c a t i o n u s ing the r e g i o n merging and s p l i t t i n g techniques i n s i d e t h e pyramidal s t r u c t u r e (case V of Tab l e 14).... , ......74 4.5 Example of c l a s s i f i c a t i o n u s i n g the r e g i o n merging and s p l i t t i n g techniques (case I I of Table 15)...... ......74 v i i i Acknowledgeaen t I wish to express g r a t e f u l acknowledgement t o Dr. Alan Mackworth f o r h i s understanding and encouragement as my t h e s i s a d v i s o r . I p a r t i c u l a r l y a p p r e c i a t e d h i s guidance i n b r i n g i n g my t h e o r e t i c a l background to experimental and p r a c t i c a l e x p r e s s i o n . I wish a l s o to warmly thank B i l l Deacon f o r h i s f r i e n d l y , u n s e l f i s h help i n my t h e s i s work, and Dr. John Baker who helped me a d j u s t to the academic and s o c i a l environment a t U.B.C. on my a r r i v a l i n Canada. CHAPTER 1 P a t t e r n R e c o g n i t i o n and LANDSAT Imagery. 1.1 Pat t e r n R e c o g n i t i o n and A r t i f i c i a l I n t e l l i g e n c e i n the LANDSAT domain The boundary between the P a t t e r n R e c o g n i t i o n (P.R.) approach and the A r t i f i c i a l I n t e l l i g e n c e (A.l.) approach to a p a r t i c u l a r domain such as scene a n a l y s i s , i s o f t e n f u z z y and d i f f i c u l t t o t r a c e . In each f i e l d use i s made of the other f i e l d ' s t echniques. I t i s d i f f i c u l t t o d e f i n i t e l y a l l o c a t e the work of some computer s c i e n t i s t s to one or the other f i e l d (see f o r example [351 o r [ 3 6 1 ) . The work of an A.I. s p e c i a l i s t l i k e Yakimovsky [41] i s g r e a t l y i n f l u e n c e d by some well e s t a b l i s h e d P.R. techniques, and , i n g e n e r a l : [ i t ]...should be p o i n t e d out t h a t i n A.I. systems f o r t a s k s such as scene a n a l y s i s , some use of P.R., methodologies i s almost unavoidable. Such systems need t o segment images i n t o p a r t s , j u s t as i n s y n t a c t i c P a t t e r n R e c o g n i t i o n ; t o measure ge o m e t r i c a l and t e x t u r a l p r o p e r t i e s of the p a r t s , and t o i d e n t i f y or c l a s s i f y the p a r t s on the b a s i s of these p r o p e r t i e s , j u s t as i n s t a t i s t i c a l P a t t e r n R e c o g n i t i o n . Advances i n segmentation, f e a t u r e e x t r a c t i o n , and c l a s s i f i c a t i o n techniques are being made by both s c h o o l s , they have more i n common than i s sometimes r e a l i z e d . . . (Rosenfeld i n [1]) On the other hand i n the P.R. community there i s an awakening i n t e r e s t i n A.I., as w e l l as i n other f i e l d s of computer s c i e n c e , as P.R. r e s e a r c h e r s seek t o overcome the l a c k of f o r m a l i z a t i o n and theory t h a t make P.R. techniques and programs appear t o be merely a "bag of t r i c k s " , j u s t i f i e d by t h e i r 2 experimental r e s u l t s [ 4 ] , The s i t u a t i o n i s more d e f i n i t e f o r the young f i e l d of LANDSAT image p r o c e s s i n g . For some h i s t o r i c a l reasons, s p e c i a l i s t s i n t h i s f i e l d are mainly concerned with P.R. techn i q u e s , and the A.I. scene a n a l y s i s community i s not yet conscious enough of the f a c t t h a t a LANDSAT p i c t u r e i s as much a scene as the more f a m i l i a r indoor and outdoor p i c t u r e s . In terms of p i c t u r e p r o c e s s i n g t h i s means that LANDSAT image i n t e r p r e t a t i o n systems perform c o n t e x t - f r e e p i x e l c l a s s i f i c a t i o n r a t h e r than e x p l o i t i n g the s p a t i a l / s p e c t r a l / t e m p o r a l s t r u c t u r e of the image. I t i s worthwile t o make c l e a r i n what e x a c t l y the above d i f f e r e n c e l i e s . A l l LANDSAT data i n t e r p r e t a t i o n t e c h n i g u e s are based on the f a c t t h a t i n f o r m a t i o n i s conveyed t o the sensor through the s p e c t r a l , s p a t i a l and temporal v a r i a t i o n s of r e g i o n s of the e l e c t r o m a g n e t i c f i e l d . For example [6] a v e r t i c a l view of an a g r i c u l t u r a l scene can be i d e n t i f i e d by the uniform r e c t a n g u l a r areas d e f i n e d by the a g r i c u l t u r a l f i e l d s { s p a t i a l v a r i a t i o n s ) or by the c o l o r of the l i g h t emanating from the scene ( s p e c t r a l v a r i a t i o n s ) or by the manner i n which the scene changes over the course o f the l o c a l growing season (temporal v a r i a t i o n s ) or by a combination of a l l three of these. The most h e a v i l y used p r o c e s s i n g systems f o r LANDSAT data make use mostly of m u l t i s p e c t r a l - m u l t i t e m p o r a l c l a s s i f i c a t i o n technigues - to a great extent they n e g l e c t the s p a t i a l v a r i a t i o n s . But f u t u r e 3 LANDSAT programs a n t i c i p a t e enormous advancements i n the q u a l i t y of the s p a t i a l i n f o r m a t i o n ; LANDSAT C s p a t i a l r e s o l u t i o n w i l l be twice the r e s o l u t i o n of the present LANDSATS. In the words of an a u t h o r i t y on Heraote Sensing: i f a n a l y s i s i s to be done by p r i m a r i l y image-oriented techniques, s p a t i a l r e s o l u t i o n becomes a prime c o n s i d e r a t i o n , f o r i n t h i s case, i t i s the major i n f o r m a t i o n bearing a t t r i b u t e of the data. However, i f the a n a l y s i s i s t o be done on a m u l t i s p e c t r a l b a s i s , the s p a t i a l r e s o l u t i o n ... determines what i n f o r m a t i o n a l c l a s s e s can be u t i l i z e d with r e s p e c t t o the data s e t . , . . Thus g r e a t e r r e s o l u t i o n cannot be expected, with present m u l t i s p e c t r a l a n a l y s i s techniques, t o g r e a t l y impact c l a s s i f i c a t i o n accuracy f o r a given s e t of c l a s s e s . . . [ 6 1 But g r e a t e r r e s o l u t i o n w i l l p rovide, of course, much more d e t a i l about the s p a t i a l s t r u c t u r e of the scene. Programs t h a t can make use of such i n f o r m a t i o n , u s i n g A.I. scene a n a l y s i s t e c h n i g u e s , can take advantage of these advances and h o p e f u l l y c o n t r i b u t e t o improving c l a s s i f i c a t i o n accuracy. G73 C N48 - 3 e ' U l 23 -13 N N48-32 'U123-J3 M S S - - D SUN EL30 A2140 194-3369-P-2-A-P-1L CCRS E-1383-18363-? NOT PRECISION PROCESSED POSITION ERROR 1 0 . 0 0 K M IMAGE DATA CREATED 15AUG73 1 7 1 - i 5 6 7 i F i g u r e 1.1. A LANDSAT p i c t u r e 5 1.2 P a t t e r n •Recognition - and LANDSAT Image P r o c e s s i n g : P o i n t by Point C l a s s i f i c a t i o n The word as seen from the s a t e l l i t e i s very d i f f e r e n t from everyday scenes ( F i g . 1 . 1 ) ; the complexity of a LANDSAT scene i s suggested by what i s c a l l e d an " i n f o r m a t i o n t r e e " (Fig.1.2) The o b j e c t i v e of a c l a s s i f i c a t i o n system i s t o produce a p a r t i t i o n o f the image i n a c e r t a i n number of c a t e g o r i e s ( p a f t e r n c l a s s e s ) depending on the purpose of the study and of course the accuracy o b t a i n a b l e decreases as one goes down the i n f o r m a t i o n t r e e . The o r g a n i z a t i o n of a c l a s s i f i c a t i o n system i s s c h e m a t i c a l l y shown i n Fig.1.3, where the i n p u t s X1, X2, Xn c o n s i s t of such measurements as adeguately c h a r a c t e r i z e the v a r i a t i o n s of the scene ( i n terms of the s p e c t r a l , s p a t i a l and temporal v a r i a t i o n s ) . U s u a l l y , as mentioned above, o n l y the s p e c t r a l and temporal v a r i a t i o n s are gathered from the data f o r a LANDSAT scene c l a s s i f i c a t i o n . A raultispectral scanner responds to l i g h t i n s e l e c t e d wavelength bands. The LANDSAT's scanner responds t o l i g h t i n the 0.5-0.6 (band 4) , 0.6-0.7 (band 5), 0.7-0.8 (band 6 ) , and 0.8-1.1 (band 7) micron wavelength bands ( F i g . 1.4). Each p o i n t i n a LANDSAT image, t h e r e f o r e , i s c h a r a c t e r i z e d by f o u r c o l o r components (the p o i n t ' s f e a t u r e v e c t o r ) . Objects t h a t are d i f f e r e n t t o the human eye c o n s t i t u t e h o p e f u l l y d i f f e r e n t p a t t e r n c l a s s e s i n the image, that i s , have d i f f e r e n t s p e c t r a l responses. Fig.1.5 i s an example o f s p e c t r a l response curve as EAKTH S u r f a c e F e a t u r e s S u r f a c e U a t e r • Exposed E a r t h Veget2c i . cn i i i Der.* I t y Tors* Shadows L i q u i d Snow Zee Water i : i G e o l o g i c S o i l s F e a t u r e s R e s i d e n t i a l I n d u s t r i s l C r o p l a n d F o r e s t B'jBhlar.d G r a s s l a n d S p e c i e s C rop C rop L ' a e ^ C o n d i c i o n Secies C r c p - C o n d i t i o n D e ^ d u o u e C o n i f e r o u s K i x e d K o i s t u r a D i s e a s e I n s e c t V a r i e t y . Y i e l d C r a i n Hay P a s t u r e O t n e r D i s e a s e F e a s i b i l i t y :M'«;I H o i c ' t u r * S t r e s s Dcn-ige 3 a t * . £ d S t r e s s Figure 1„2 An E a r t h Resources Information Tree SCENE Figure 1.3 The o r g a n i z a t i o n o f a C l a s s i f i c a t i o n System 8 a f u n c t i o n of the wavelength. In t h i s example the c a t e g o r i e s shown form s p e c t r a l l y d i s t i n c t groups, as a p l o t of the values of the r e f l e c t a n c e f o r band 4. versus the values of the r e f l e c t a n c e f o r band 6 shows ( F i g . 1.6). LANDSAT image c l a s s i f i e r s g e n e r a l l y make use of s u p e r v i s e d or unsupervised Pattern R e c o g n i t i o n t e c h n i q u e s . When r e p r e s e n t a t i v e s e t s (ground-truth data) from each p a t t e r n c l a s s under c o n s i d e r a t i o n are a v a i l a b l e , then a s u p e r v i s e d technique i s a p p l i c a b l e . I n t h i s approach the system i s presented with a s e t of samples drawn from the c l a s s e s of i n t e r e s t ( t r a i n i n g set) and i s "taught" how to r e c o g n i z e them, when very l i t t l e i s known about the number of s p e c t r a l l y d i s t i n c t c l a s s e s , then the system has to " l e a r n " the c l a s s e s of i n t e r e s t from the given data (unsupervised c l a s s i f i c a t i o n or c l u s t e r i n g ) . In t h i s case the data samples are c l u s t e r e d together a c c o r d i n g to a c e r t a i n s i m i l a r i t y measure, i . e . , a r u l e f o r a s s i g n i n g the data to t h e domain of a p a r t i c u l a r c l u s t e r c e n t r e . These c l u s t e r s may then be c o r r e l a t e d with the c l a s s e s of i n t e r e s t by using ground-truth data. The c l u s t e r c e n t e r s are h e u r i s t i c a l l y chosen [ 3 ] , A s i m i l a r i t y measure can be E u c l i d e a n d i s t a n c e , or any other d i s t a n c e , of the data from the c l u s t e r c e n t e r s (minimum distan.ce c l a s s i f i e r ) . F i g . 1.6 i l l u s t r a t e s t h i s technique with an example. In t h i s case t h e r e are f o u r p a t t e r n c l a s s e s , i . e . , v e g e t a t i o n , sandy s o i l , c l a y s o i l , and water; the p i x e l whose f e a t u r e v e c t o r i s Vj i s assigned t o the c l u s t e r with Upper l i m i t g lass transmission ERTS-1 MSS U l t r a V i o l e t V i s i b l e Near In f r a r e d Thermal emission peak of the earth Thermal Infrared (microns) .4 ..5 .7 .9 1.5 2.0 3,0 4.0 5.0 6.0 9.0 12.0 15.0 20.0 25.0 .Figure l6k The electromagnetic spectrum i n the visible region,, 10 ~ ~ VEGETATION i HIGH REFLECTANCE SOIL (e.g. sandy s o i l ) -LOW REFLECTANCE SOIL (e.g. c l a y s o i l ) WATER 7b" 4-.'8 .9 urn Band 4 Band 5 Band 6 Band 17 h- A fc- 4 i> (t-• ~ • WAVELENGTH IN MICROMETRES F i g u r e 1.5 T y p i c a l r e f l e c t a n c e s p e c t r a f o r v e g e t a t i o n , sandy s o i l , c l a y s o i l and wa t e r , wittt LANDSAT MSS bands shown. ; 1 . 1 J~ 4 VEGETATION INTENSITY - BAND 4 ARBITRARY UNITS F i g u r e 1.6 P i x e l by p i x e l p l o t of i n t e n s i t y i n band 6 versus i n t e n s i t y i n band k„ 12 S 5n Figure-1.7 E l l i p s e s o f C o n c e n t r a t i o n f o r o l d growth,, new g r o w t h , r e c e n t l o g g i n g and water„ 13 f e a t u r e vector Sv. I t should perhaps be mentioned t h a t simple approaches l i k e t h i s , very common i n P.R., do not always give good r e s u l t s when a p p l i e d to the the LANDSAT domain, f o r they assume t h a t the p a t t e r n c l a s s e s a r e l i n e a r l y s e p a r a b l e . I n the r e a l LANDSAT world the s i t u a t i o n i s much d i f f e r e n t from the one represented s c h e m a t i c a l l y i n Fig.1.6. In F i g . 1 . 7 the extent o f the s t a t i s t i c a l o v e r l a p i n a standard s i t u a t i o n i s represented. 17-3. The scene i s a f o r e s t e d area and the c l a s s e s of i n t e r e s t are f o u r : three stages o f f o r e s t growth and areas of water. The f i g u r e shows the tendency of the p a t t e r n c l a s s e s to be grouped i n e l l i p s o i d a l c l u s t e r s c e ntered around t h e i r means ( i n f i g u r e shown f o r the two bands 6 and 7). I t i s c l e a r t h a t i f the purpose were to d i s c r i m i n a t e between water and l a n d , then a simple minimum d i s t a n c e c l a s s i f i e r would c o r r e c t l y s e p a r a t e the p i x e l s belonging to one c l a s s (water) from the p i x e l s belonging to the other one (non water). For any other purpose t h i s approach c l e a r l y would not succeed. What i s u s u a l l y done i n non-supervised c l a s s i f i c a t i o n i s , once the c l u s t e r s are determined by some s i m i l a r i t y measure, s t a t i s t i c s are c a l c u l a t e d from them. C l a s s i f i c a t i o n of an unknown p i x e l can be done, i n both the unsupervised and s u p e r v i s e d approaches, using s t a t i s t i c a l d e c i s i o n theory. So f a r , the most powerful s u p e r v i s e d technique f o r LANDSAT data c l a s s i f i c a t i o n , and the most g e n e r a l l y used, i s provided by 14 s t a t i s t i c a l d e c i s i o n theory. T h i s approach takes i n t o account the s t a t i s t i c a l p r o p e r t i e s of p a t t e r n c l a s s e s i n order t o a r r i v e at a c l a s s i f i c a t i o n scheme. In t h i s model the data samples are represented as p o i n t s i n a n-dimensional space. Each c o o r d i n a t e i n such a space r e p r e s e n t s a (measurable) property of the data sample. I t i s an u n d e r l y i n g assumption of t h i s theory t h a t each c l a s s has a s s o c i a t e d with i t a m u l t i v a r i a t e p r o b a b i l i t y d i s t r i b u t i o n i n n-space. The o b j e c t i v e o f the c l a s s i f i c a t i o n procedure i s then t o a r r i v e a t an assignment of every p o i n t to the c l a s s e s i n the way t h a t best f u l f i l l s a c e r t a i n d e c i s i o n c r i t e r i o n . When the form o f the d i s t r i b u t i o n i s known then the parameters of the d i s t r i b u t i o n must be c a l c u l a t e d from the ground-truth data (parametric approach). Because of some n i c e p r o p e r t i e s of g e n e r a l i t y and computational s i m p l i c i t y o f the normal (Gaussian) d i s t r i b u t i o n , a c l a s s i f i c a t i o n procedure g e n e r a l l y "assumes" a normal d i s t r i b u t i o n i n n-space f o r the pat t e r n c l a s s e s . Since a normal d i s t r i b u t i o n i s completely s p e c i f i e d by i t s mean v e c t o r and c o v a r i a n c e matrix, i n t h i s case the parameters t h a t must be lear n e d are the means and the elements of the c o v a r i a n c e matrix f o r each c l a s s , as c a l c u l a t e d from the t r a i n i n g s e t . When the form of the d i s t r i b u t i o n i s not known, then s e v e r a l technigues can be used t o g i v e e s t i m a t e s of d i s t r i b u t i o n s from the t r a i n i n g s e t , f o l l o w i n g implementation 15 c o n s i d e r a t i o n s and i n t u i t i o n (fion-£arametric approach), and t e s t s can be conducted t o t e s t t h e i r v a l i d i t y ; f o r example the performance o f the c l a s s i f i e r can be measured by d i r e c t experimentation with the t r a i n i n g s e t . Once the p r o b a b i l i t y of membership f o r each c l a s s i s computed f o r a p i x e l i n the s c e n e 1 , the p i x e l can be assigned t o a c l a s s a c c o r d i n g to a c r i t e r i o n that minimizes the p r o b a b i l i t y o f m i s c l a s s i f i c a t i o n {Bav.es c r i t e r i o n ) . U s u a l l y the Bayes c r i t e r i o n i s taken i n the form of the maximum-likelihood c r i t e r i o n : a p i x e l i s assign e d to the c l a s s that g i v e s to i t the highest p r o b a b i l i t y of membership (£oint by. po i n t c l a s s i f i c a t i o n ) . For a complete treatment of the d e c i s i o n t h e o r e t i c approach to P.R. see I 5 ]. Most of the other c l a s s i f i c a t i o n technigues do not s u b s t a n t i a l l y d i v e r g e from t h i s approach. An i n t e r e s t i n g v a r i a t i o n o f the c o n v e n t i o n a l maximum l i k e l i h o o d c l a s s i f i e r i n v o l v e s the use of a " d e c i s i o n t r e e " ^Following [ 8 ] we d e f i n e : = q<P K(y)/P(y) (Bayes* formula) the a - p o s t e r i o r i p r o b a b i l i t y o f c l a s s k, i . e . The p r o b a b i l i t y t h a t a given point y i s a c t u a l l y a member of c l a s s k where: Pk(y) i s the n - v a r i a t e normal p r o b a b i l i t y d e n s i t y f o r c l a s s k ( i t i s a j o i n t 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 o f n random v a r i a b l e s : the n p r o p e r t i e s of c l a s s k) qK i s the a p r i o r i p r o b a b i l i t y t h a t a p o i n t w i l l be chosen from c l a s s k and p(y) = 2 qKpJy) i s 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 a l l p o s s i b l e p o i n t s . 16 [ 1 0 ] . A d e c i s i o n t r e e i s shown i n Fig.1.8. At the f i r s t stage a l l c l a s s e s are put i n t o i groups using only N1 f e a t u r e s . The same procedure i s then repeated a t the second stage f o r each of the i groups. The process continues u n t i l each o f the o r i g i n a l c l a s s e s can be s e p a r a t e l y i d e n t i f i e d . For example i n a scene p a r t l y covered by clouds the p i x e l s obscured by c l o u d s are r e - c l a s s i f i e d once more, i n one or s e v e r a l s t e p s , using a p i c t u r e from another date with no c l o u d s at t h i s p o i n t i n the scene. The o v e r a l l performance of t h i s c l a s s i f i e r i s shown to be b e t t e r than that of the c o n v e n t i o n a l s i n g l e stage c l a s s i f i e r because d i f f e r e n t f e a t u r e subsets can be s e l e c t e d at d i f f e r e n t stages. In f 1 1 ] a m o d i f i c a t i o n of a d e c i s i o n t r e e , a l i n e a r binary d e c i s i o n t r e e c l a s s i f i e r i s proposed t h a t i s more a c c u r a t e and much f a s t e r than the maximum l i k e l i h o o d c l a s s i f i e r t h a t uses the same number of f e a t u r e s . In general the success of any p a r t i c u l a r c l a s s i f i e r i s s e n s i t i v e t o so many v a r i a b l e s t h a t i s u s e l e s s t o give f i g u r e s f o r performance. But, t o g i v e a rough i d e a , f o r example i n f 1 2 ] experiments are performed to t e s t the c l a s s i f i c a t i o n accuracy of the IMAGE 100, a d i s p l a y system made by G.E. with a b u i l t i n i n t e r a c t i v e s u p e r v i s e d non parametric c l a s s i f i e r f o r LANDSAT p i c t u r e s , the most widely used c l a s s i f i c a t i o n system i n Canada. The experiment g i v e s r e s u l t s of c l a s s i f i c a t i o n s f o r an a g r i c u l t u r a l region {BQ% a c c u r a c y ) , a mixed vegetation-urban 17 area (88%), and a major urban c e n t r e (70%) . In an experiment performed at LARS [ 9 ] the c l a s s i f i c a t i o n performance on a set of LANDSAT data i s compared with a data s e t c o l l e c t e d by an a i r b o r n e m u l t i s p e c t r a l scanner system with more wavelength bands over a wider r e g i o n of the spectrum. The i n t e r e s t i n g r e s u l t i s t h a t the o v e r a l l performance f o r the two data s e t s was n e a r l y i d e n t i c a l . C l a s s i f i c a t i o n performance of any approach depends l a r g e l y on the degree of s p e c t r a l s e p a r a b i l i t y of the c l a s s e s of i n t e r e s t and on the amount of t r a i n i n g data used, but i f the c l a s s e s of i n t e r e s t are s p e c t r a l l y s i m i l a r (as measured by the sensor) then one cannot d i s c r i m i n a t e among them r e g a r d l e s s of the amount of t r a i n i n g data used. D i f f e r e n t sources of i n f o r m a t i o n , b e s i d e s the s p e c t r a l data, must be i d e n t i f i e d and used. N F E A T U R F S F i g u r e 1.8 A D e c i s i o n Tree scheme f o r c l a s s i f i c a t i o n 19 1*3 The use of s p a t i a l i n f o r m a t i o n i n LANDSAT image a n a l y s i s Some technigues have been proposed and implemented that c h a r a c t e r i z e the i n f o r m a t i o n present i n the s p a t i a l r e l a t i o n s h i p s i n the data of a s a t e l l i t e p i c t u r e , so that t h i s i n f o r m a t i o n can be e x t r a c t e d by machine p r o c e s s i n g and u t i l i z e d i n c o n j u n c t i o n with the m u l t i s p e c t r a l i n f o r m a t i o n . The f o l l o w i n g i s a comprehensive review of these technigues as a p p l i e d t o LANDSAT imagery. In [13] a two-step c l a s s i f i c a t i o n procedure i s presented. In the f i r s t s tep the whole scene i s r e c u r s i v e l y p a r t i t i o n e d i n r e c t a n g u l a r b l o c k s such t h a t each block i s l i k e l y to c o n t a i n p i x e l s from a s i n g l e c l a s s , and each c l a s s of i n t e r e s t i s approximated by a union of b l o c k s . In the second s t e p the blocks are c l a s s i f i e d u s i n g s u p e r v i s e d and unsupervised c l a s s i f i c a t i o n that makes use of a s t a t i s t i c a l d i s t a n c e measure between p a r t i t i o n blocks and subimages of known c l a s s i f i c a t i o n . The performance of t h i s technique on two s a t e l l i t e images i s compared with t h a t o f a point by point c l a s s i f i e r : a comparable accuracy i s obtained with l e s s storage r e q u i r e d at expense of much l a r g e r computation time. In [ 1 4 ] and [15] a s i m i l a r method i s repor t e d t h a t p a r t i t i o n s the image in blocks o f s t a t i s t i c a l l y s i m i l a r p i x e l s before c l a s s i f y i n g them. I n i t i a l l y the whole scene i s d i v i d e d i n t o groups of f o u r p i x e l s ; each group becomes a c e l l provided i t s a t i s f i e s a given c r i t e r i o n o f homogeneity. The 20 s t a t i s t i c a l l y s i m i l a r c e l l s a r e t h e n merged i n t o b l o c k s . Each "homogeneous" b l o c k o f p i x e l s i s t h e n c o n s i d e r e d a s t a t i s t i c a l sample, and a sample c l a s s i f i e r , r a t h e r then a p o i n t by p o i n t c l a s s i f i e r , i s used t o c l a s s i f y each sample. O b v i o u s l y t e c h n i g u e s l i k e t h i s reduce t h e number o f c l a s s i f i c a t i o n s needed t o c l a s s i f y the whole image. The above t e c h n i g u e s , as w e l l as most o f the f o l l o w i n g , have i n common t h e f a c t t h a t c l a s s i f i c a t i o n of a p i x e l i n the scene i s a r e s u l t of t h e s p e c t r a l p r o p e r t i e s o f i t s nei g h b o u r s as w e l l as i t s own. Some a u t h o r s e s p e c i a l l y t h o s e i n t e r e s t e d i n t e r r a i n c l a s s i f i c a t i o n c h a r a c t e r i z e s p a t i a l i n f o r m a t i o n as t e x t u r e . F o u r i e r a n a l y s i s t e c h n i g u e s , f o r example, a re used t o e x t r a c t t e x t u r a l i n f o r m a t i o n ; t h i s method r e l a t e s t e x t u r e t o s p a t i a l f r e g u e n c y . The d i s c r e t e f a s t F o u r i e r t r a n s f o r m i s t a k e n and sampled f o r b l o c k s o f d a t a s t a r t i n g from the upper l e f t hand c o r n e r o f t h e a r e a o f i n t e r e s t . The r e s u l t i n g s p a t i a l f r e g u e n c y v e c t o r i s a s s i g n e d as a f e a t u r e t o the p i x e l i n the middl e of the b l o c k . These f e a t u r e s can the n be i n p u t as a d d i t i o n a l f e a t u r e s i n a p o i n t by p o i n t c l a s s i f i e r . T h i s method i s used f o r example a t LARS [ 9 ] ; f o r a thorough d e s c r i p t i o n o f t h i s t e c h n i g u e see [ 1 6 ] . I n [ 1 7 ] a pr o c e d u r e i s g i v e n t o compute t h e t e x t u r a l f e a t u r e s of b l o c k s o f image d a t a . T h i s t i m e t e x t u r e i s c h a r a c t e r i z e d by the s p a t i a l d i s t r i b u t i o n of i t s grey t o n e s . A 21 set of grey-tone spatial-dependence p r o b a b i l i t y - d i s t r i b u t i o n matrices f o r a given image block i s computed ( s c h e m a t i c a l l y , matrices whose elements r e p r e s e n t j o i n t p r o b a b i l i t y d e n s i t i e s of p a i r s of grey l e v e l s i n the t e x t u r e ) . One matrix i s c a l c u l a t e d f o r every angular r e l a t i o n s h i p ( i . e . , 0°, 45°, etc.) and di s t a n c e ( i . e . , 1, 2, etc.) between neig h b o r i n g p a i r s of p i x e l s or groups of p i x e l s ( r e s o l u t i o n c e l l s ) on the image. , A c e r t a i n number of t e x t u r a l f e a t u r e s i s e x t r a c t e d from each of these matrices and assigned to the c e n t r a l p i x e l of the b l o c k . . These f e a t u r e s are used as a d d i t i o n a l i n p u t i n a point by point c l a s s i f i c a t i o n of a LANDSAT p i c t u r e . The r e p o r t e d o v e r a l l accuracy of the c l a s s i f i c a t i o n i s 83% (using 64x64 b l o c k s and both s p e c t r a l and t e x t u r a l f e a t u r e s on seven t e r r a i n c l a s s e s ) versus the 74-7795 achieved using only s p e c t r a l f e a t u r e s . In [18] a procedure i s described f o r r e c l a s s i f y i n g each p i x e l by u s i n g the s p a t i a l i n f o r m a t i o n c o n t a i n e d i n the surrounding three-by-three r e g i o n . The method c o n s i s t s of comparing two s p a t i a l and one s p e c t r a l f u n c t i o n s , c a l c u l a t e d i n the t h r e e - b y - t h r e e r e g i o n , s e g u e n t i a l l y a g a i n s t three t h r e s h o l d s T1, T2, and T3. For a given p i x e l , i f the number of p i x e l s i n the r e g i o n belonging to the same c l a s s i s g r e a t e r than T1 or the most freguent c l a s s i n the r e g i o n occurs a t l e a s t T2 times or the E u c l i d e a n d i s t a n c e i n s p e c t r a l space between the mean of the c l a s s o f the c e n t r a l p i x e l and the mean of the most freguent c l a s s i n the r e g i o n i s greater than T3 then no change i s made; 22 otherwise, the c l a s s number of the c e n t r a l p i x e l i s s e t t o the most frequent c l a s s number i n the r e g i o n . An analogous s i m p l e r p o s t p r o c e s s i n g procedure i s proposed i n [191, which searches f o r connected s e t s i n a binary c l a s s i f i c a t i o n map of a LANDSAT image (a mapping of mixed softwood-hardwood timber s t a n d s ) . The areas of the connected s e t s are evaluated. I f they are s m a l l e r then a p r e s p e c i f i e d t h r e s h o l d , they are e l i m i n a t e d by changing t h e i r l a b e l to the other type. Some authors propose technigues t h a t are s u i t a b l e f o r d e t e c t i n g c l a s s e s of o b j e c t s whose p a r t i c u l a r shape or s i z e makes them hard to d i s t i n g u i s h from the "noise 1' of the s p e c t r a l c h a r a c t e r i s t i c s ( b r i d g e s , freeways, g e o l o g i c a l f e a t u r e s , e t c . ) . . In [20] l o c a l l i n e d e t e c t i o n procedures are a p p l i e d to LANDSAT imagery c o n t a i n i n g l i n e a r f e a t u r e s such as roads, r i v e r s and g e o l o g i c a l lineaments. These l i n e d e t e c t o r s are l o c a l i n t h a t they make a d e c i s i o n about the presence of a l i n e at a p o i n t by examining p i x e l s i n a region i n the immediate neighborhood of the p o i n t . B a s i c a l l y what they do i s t o compare i n some way, f o r a c e r t a i n d i r e c t i o n , the i n t e n s i t i e s of the p o i n t s i n the r e g i o n along t h a t d i r e c t i o n with the i n t e n s i t i e s of the neighbouring p o i n t s along the same d i r e c t i o n . Most of the l i n e a r f e a t u r e s i n the t e r r a i n of a LANDSAT image are picked up by t h i s program. However, the weakness of algo r i t h m s l i k e the above c o n s i s t s i n the f a c t t h at though on 23 one hand they do make use of s p a t i a l i n f o r m a t i o n , on the other hand a) the context used i s very l o c a l , i . e . , there i s no way to j o i n two 'broken' ends of a l i n e , and b) they l o s e the power of the s t a t i s t i c a l use of the s p e c t r a l i n f o r m a t i o n . S t i l l , they can be very u s e f u l i n some p a r t i c u l a r a p p l i c a t i o n i n which an output c o n s i s t i n g of M i n e s ' i s d e s i r e d . The l i n e d e t e c t o r produces l i n e o r i e n t a t i o n values as w e l l as l i n e i n t e n s i t i e s values. In [ 2 1 ] a r e l a x a t i o n method i s d e s c r i b e d t o reduce the noise generated by the l o c a l l i n e d e t e c t i o n o p e r a t i o n . The n o i s e a r i s e s because p i x e l s not l y i n g on l i n e s may appear l o c a l l y l i n e - l i k e , and v i c e v e r s a . The procedure i t e r a t i v e l y r e i n f o r c e s the r e s u l t of the l i n e d e t e c t o r . I t s t a r t s from a p o i n t P and goes along the d i r e c t i o n given by the l i n e o r i e n t a t i o n value examining some neighboring p o i n t s , i . e . , the p o i n t s seen by P. These p o i n t s are weighted ac c o r d i n g t o t h e i r o r i e n t a t i o n values r e l a t i v e to P: i f the sum i s a l a r g e p o s i t i v e number the i n t e n s i t y o f P i s s u b s t a n t i a l l y i n c r e a s e d (the point P i s rewarded); i f i t i s a l a r g e negative number the i n t e n s i t y o f P i s s u b s t a n t i a l l y decreased (the point P i s punished), and s i m i l a r l y f o r intermediate v a l u e s . An analogous i t e r a t i v e procedure i s d e s c r i b e d i n the same paper which uses i n f o r m a t i o n about the l i n e o r i e n t a t i o n at a p o i n t ' s neighbors t o a d j u s t the l i n e o r i e n t a t i o n a t the point so as to improve the alignement. In { 2 2 ] the s t r u c t u r a l or s y n t a c t i c approach to P a t t e r n 24 R e c o g n i t i o n i s proposed f o r d e s c r i b i n g the s p a t i a l r e l a t i o n s h i p s i n a LANDSAT scene, A t r e e graph model can c o n t a i n t h e s p a t i a l d i s t r i b u t i o n s o f a l l c l a s s e s i n t h e e n t i r e scene,. F o r example, t h e scene under a n a l y s i s , a s a t e l l i t e photograph of Mari o n County, I n d i a n a p o l i s , i s p a r t l y o b s c u r e d by t h e c l o u d s ; t h e c l o u d f r e e p a r t of t h e scene c o n s i s t s of an urban and a r u r a l a r e a , and t h e urban a r e a c o n s i s t s o f t h e downtown a r e a s u r r o u n d e d by th-~! i n n e r c i t y a r ea w i t h nearby suburban a r e a and a system of highways {Fig.1.3) « , F i g u r e 1 . 9 . A t r e e graph model of a LANDSAT scene (from f 22 ]) The s p a t i a l r e l a t i o n s h i p s among c l a s s e s a r e g i v e n as l i n g u i s t i c s r u l e s and a r e s p e c i f i e d i n terra's o f a web grammar [23] , The 25 r e c o g n i t i o n of p a t t e r n s ( s e n t e n c e s ) , e.g., cloud-shadow p a i r s and highways, i s performed by a p a r s i n g a l g o r i t h m u s i n g the given s y n t a c t i c r u l e s . In [24] b a s i c a l l y the same idea i s present, but a t r e e grammar [25] i s i n t r o d u c e d t o d e s c r i b e a subscene and a t r e e automaton to r e c o g n i z e i t . A very i n t e r e s t i n g method i s a l s o i n t r o d u c e d to " i n f e r " the s y n t a c t i c r u l e s when the s t r u c t u r e of a p a r t i c u l a r c l a s s under c o n s i d e r a t i o n i s not known. What i s i n t e r e s t i n g i n t h i s approach i s i t s use of d e c i s i o n theory only as a f i r s t s t e p i n the r e c o g n i t i o n process. In [ 2 7 ] a s i m i l a r approach i s used i n t h a t a s t r u c t u r a l world model i s used (but i t i s not f o r m a l i z e d i n the same way). A c l a s s i f i c a t i o n a l g o r i t h m o f a LANDSAT scene i s d e s c r i b e d f o r the r e c o g n i t i o n of b r i d g e s , i s l a n d s , r i v e r s and l a k e s . The al g o r i t h m works l i k e a s e q u e n t i a l f i l t e r . I t f i r s t l o o k s f o r the " e a s i e s t " o b j e c t to f i n d , i n t h i s case the water, and uses the assigned meaning, together with l o c a l p r o p e r t i e s of the unknown regions and s p a t i a l r e l a t i o n s h i p s with the i n t e r p r e t e d r e g i o n s , to ease the d e t e c t i o n o f the second e a s i e s t o b j e c t , and so on. T h i s a l g o r i t h m i s r e p o r t e d to have found a l l b r i d g e s i n the scene. In [28] the same scheme i s s u c c e s s f u l l y implemented f o r the r e c o g n i t i o n of the roads i n a s a t e l l i t e image. Again i t can be s a i d t h a t i n a domain with d i f f e r e n t semantics (types of f o r e s t s , f o r example) t h i s approach u o u l d not probably be so e f f e c t i v e . 26 CHAPTER 2 Some Approaches t o Scene A n a l y s i s 2.1. H i e r a r c h i c a l S t r u c t u r e s Image understanding by computer i n v o l v e s two main problems, segmentation and i n t e r p r e t a t i o n 1391. Before the o b j e c t s i n the p i c t u r e can be r e c o g n i z e d and d e s c r i b e d ( i n t e r p r e t a t i o n ) they must be e x p l i c i t i l y l o c a t e d . Many d i f f e r e n t types of subsets of the p i c t u r e can be " o b j e c t s " , depending on the type of d e s c r i p t i o n t h a t i s r e g u i r e d . In the segmentation phase of the p i c t u r e r e c o g n i t i o n process the given image i s p a r t i t i o n e d i n a c e r t a i n number of subsets, each one being l i k e l y t o be an o b j e c t or a p a r t of an o b j e c t i n the p i c t u r e . The standard p i c t u r e segmentation approach to P a t t e r n R e c o g n i t i o n r e q u i r e s , as a minimum, to a t l e a s t "look a t " every p i x e l i n the p i c t u r e . T h i s approach i s i n e h e r e n t l y w a s t f u l because a l l t h i s d e t a i l i s not needed everywhere i n the p i c t u r e f o r most purposes [ 3 5 ] . Some recent work t r i e s to a v o i d t h i s kind of waste. In [29] K e l l y d e s c r i b e s an approach based on the i d e a of s e l e c t i v e a t t e n t i o n : i . e . , on the f a c t t h a t when l o o k i n g at a scene we can focus our a t t e n t i o n on the r e l e v a n t p a r t s of i t i f we already have an i d e a about what these r e l e v a n t p a r t s are. He c o n s i d e r s an image of a human f a c e and e x t r a c t s a s m a l l e r p i c t u r e from i t , with the i n t e n s i t y at every poin t equal 27 to the average i n t e n s i t y over an area 8x8 p i x e l s of the o r i g i n a l . The idea i s t h a t t h i s reduced p i c t u r e e x h i b i t s only the gross f e a t u r e s ( l a r g e edges) of the f a c e whithout the surrounding n o i s e of the f i n e f e a t u r e s . These f e a t u r e s are detected (by an edge f i n d i n g algorithm) and used to r e f i n e the segmentation of the o r i g i n a l p i c t u r e , i . e . , to f i n d a l l the edges in the p i c t u r e . T h i s i d e a of working on a compressed v e r s i o n of the o r i g i n a l p i c t u r e data i s used by S h i r a i [30] t o speed-up the contour f i n d i n g process i n the i n i t i a l stage of a l i n e f i n d i n g procedure i n a block world scene. He i n i t i a l l y assumes the whole scene i s composed o f two r e g i o n s , t h e background and the b l o c k s , and uses an e i g h t - f o l d r e d u c t i o n of the p i c t u r e to t r a c e out the boundary between these two r e g i o n s . The program scans a l l the p i x e l s i n the compressed p i c t u r e t o f i n d p o i n t s l i k e l y to be contour p o i n t s and uses t h i s i n f o r m a t i o n t o l o c a t e the a c t u a l p o i n t s on the o r i g i n a l higher r e s o l u t i o n p i c t u r e . Once the contour l i n e s are t r a c e d , t h e program keeps s e a r c h i n g f o r the other l i n e s i n the scene i n a h i e r a r c h i c a l f a s h i o n , a t each st e p using the previous r e s u l t s t o make assumptions about the next. What i s n i c e about t h i s s t r a t e g y i s t h a t i t a l l o w s him to make guesses about the presence of l i n e s i n s p e c i f i c areas, e.g., an extension of one or more l i n e s or a connection between two broken l i n e s . T h i s technigue overcomes the weakness noted i n [20] (sec.1.3). I t would be i n t e r e s t i n g to t e s t the 28 e f f e c t i v e n e s s of the above approach i n the much more complex LANDSAT domain. S e v e r a l authors extended K e l l y ' s i d e a on p l a n n i n g . , D i f f e r e n t k i n d s of h i e r a r c h i c a l s t r u c t u r e s have been developed capable of handling p i c t u r e processing at d i f f e r e n t l e v e l s . , Again, the ' p e r c e p t u a l l y ' motivated reason f o r such s t r u c t u r e s l i e s i n the f a c t t h a t ...the enormous amount o f complex f u n c t i o n s computed by p e r c e p t u a l systems are best decomposed i n t o s u c c e s s i v e l y s i m p l e r s e t s o f f u n c t i o n s , and a l l a p p l i e d i n a p a r a l l e l s e r i a l flow of processes ...[31] In [32] Uhr d e s c r i b e s h i s r e c o g n i t i o n cone model of p e r c e p t i o n . T h i s i s a p a r a l l e l - s e r i a l system of l a y e r s of t r a n s f o r m a t i o n s . A l a y e r c o n s i s t s of an array of c e l l s , each c o n t a i n i n g i n f o r m a t i o n i n p u t to i t , and a set of transforms., Each c e l l sees one l o c a l r e g i o n of the image so t h a t the e n t i r e image i s covered. An image i s i n p u t to the cone's r e t i n a where the s e t of transforms performs l o c a l t r a n s f o r m a t i o n s on i t . A l l outputs from here are merged i n t o the next l a y e r : i . e . , s u c c e s s i v e l a y e r s of the cone c o n t a i n a r r a y s of c e l l s t h a t 'see* the output of the l a y e r d i r e c t l y below. The a r r a y s decrease i n s i z e as they go up i n t h e cone u n t i l e v e n t u a l l y the cone completely c o l l a p s e s i n t o a l a y e r with a s i n g l e c e l l . T h i s s t r u c t u r e i s s t i l l at an e a r l y stage of development and not too much can be s a i d about implementation (experimental) 29 r e s u l t s . K l i n g e r [33] d e s c r i b e s a r e g u l a r decomposition procedure t h a t d e l e t e s l a r g e non i n f o r m a t i v e areas of a p i c t u r e but keeps s e a r c h i n g f o r i n f o r m a t i o n i n t h e most i n f o r m a t i v e {complex) areas. The data s t r u c t u r e c o n s i s t s of a t r e e of guadrants of the o r i g i n a l p i c t u r e , whose nodes have e i t h e r f o u r or zero successors. I n i t i a l l y the e n t i r e d i g i t i z e d p i c t u r e i s a quadrant. When the a l g o r i t h m looks a t a quadrant i t can decide t h a t 'no i n f o r m a t i o n ' i s c o n t a i n e d i n i t , i n which case the area i n the quadrant i s e l i m i n a t e d from the data s t r u c t u r e without l o s s of i n f o r m a t i o n . I f , however, i t f i n d s 'a l a r g e amount of i n f o r m a t i o n * then a l l p i x e l s i n the quadrant are saved i n the data s t r u c t u r e of the reduced p i c t u r e . I f t h e r e i s not enough i n f o r m a t i o n present t o make a d e c i s i o n about the quadrant, the a l g o r i t h m s u b d i v i d e s t h e quadrant i n t o f o u r subquadrants and r e c u r s i v e l y processes them i n the same way. The depth of t h e decomposition t r e e then v a r i e s a c r o s s the image depending on the amount of i n f o r m a t i o n present i n each pa r t of the scene. The bound on the search i s of course e s t a b l i s h e d by the quadrant's s i z e becoming egual t o the p i x e l s i z e . Storage savings can be achieved by using r e g u l a r decompositions, but the amount o f s a v i n g depends on the amount of redundancy i n the image: i n a l i n k e d implementation, p o s s i b l y 30 more storage i s used by the l i n k s and upper l e v e l s of the t r e e than i s saved by the e l i m i n a t i o n of redundancy i n the d e s c r i p t i o n of uniform areas [ 3 4 ] . The running time depends on the complexity of the image. T h i s procedure i s shown to be most s u i t a b l e f o r a p p l i c a t i o n s i n v o l v i n g sparse p i c t u r e i n f o r m a t i o n [ 3 3 ] , f o r example when one wants to i s o l a t e o b j e c t s from a background. A h i e r a r c h i c a l segmentation scheme i s used by Mackworth [38] to o b t a i n the i n i t i a l r e g i o n segmentation i n a l i n e drawing a p p l i c a t i o n (a s k e t c h map) . The a l g o r i t h m r e c u r s i v e l y p a r t i t i o n s the image i n empty guadrants, each guadrant being sub d i v i d e d only i f i t i s not empty. An analogous scheme i s used f o r l i n e segmentation. Another approach to h i e r a r c h i c a l p i c t u r e p r e p r o c e s s i n g i s d e s c r i b e d by Tanimoto and more than the previous ones can be seen as a development o f K e l l y ' s i d e a . The data s t r u c t u r e i s f o r m a l l y d e s c r i b e d i n [ 3 5 ] . The p i c t u r e i s s t o r e d i n a seguence of matrices where every matrix i s a d i g i t i z a t i o n of the p i c t u r e at lower r e s o l u t i o n than the previous matrix i n the seguence. The whole s t r u c t u r e can be seen as a pyramid o f matrices with the matrix a t l e v e l K obtained from the matrix i n l e v e l K-1 by averaging b l o c k s of four c e l l s . T h i s r e q u i r e s t h a t the p i c t u r e under c o n s i d e r a t i o n be an NxM matrix of gray l e v e l s with N=N'x2*- and M=M'x2L where N* and M* are i n t e g e r s and L i s the number of " l e v e l s " [ 3 5 ] . 31 The lower l e v e l of the pyramid i s the p i c t u r e at highest r e s o l u t i o n ; i f N=M=2«-, then the top of the pyramid i s a p i x e l whose gray value i s the average over the whole p i c t u r e . Tanimoto shows t h a t t h i s method of pr o c e s s i n g p i c t u r e s can be very h e l p f u l i n speeding up the o p e r a t i o n of edge d e t e c t i o n i n the p i c t u r e . T h i s data s t r u c t u r e i s used by Levine [361 f o r the low l e v e l p r o c e s s i n g stage (segmentation) of a three stage image understanding system [ 3 7 ] . The image t o be i n t e r p r e t e d i s a 128x12 8 d i g i t i z e d p i c t u r e of an outdoor scene. The f e a t u r e space has fou r dimensions: the i n t e n s i t y , hue, and s a t u r a t i o n , which are c a l c u l a t e d from the green, r e d , and blue components, and a l o c a l t e x t u r e as c a l c u l a t e d i n [ 1 7 ] . The p i c t u r e pyramid i s c r e a t e d by s u c c e s s i v e l y averaging groups of f o u r p i x e l s . On the way down t h i s pyramid, a c l u s t e r i n g a l g o r i t h m i s used t o a s s i g n segment (region) l a b e l s to the p i x e l s . F i r s t another pyramid, an edge pyramid, i s c r e a t e d i n order t o d r i v e the c l u s t e r i n g a l g o r i t h m . Each four p i x e l c l u s t e r at any l e v e l i n t h e edge pyramid becomes one p i x e l at the next higher l e v e l by mean of a l o g i c a l 08 o p e r a t i o n . The e f f e c t o f t h i s o p e r a t i o n i s to t h i c k e n the edges at each s u c c e s s i v e l e v e l i n the edge pyramid. The segmentation process s t a r t s at a l e v e l high enough t h a t almost a l l the p i x e l s are l a b e l l e d as edges i n the corresponding l e v e l o f the edge pyramid. The c l u s t e r i n g a l g o r i t h m i s c a l l e d 32 to l a b e l the p i x e l s t h a t are not already l a b e l l e d as edges, then every p i x e l i s expanded i n a four p i x e l c l u s t e r to go down to the next l e v e l . The p i x e l s i n these c l u s t e r s r e t a i n the l a b e l a lready assigned t o them except when they have a neighbour of d i f f e r e n t l a b e l , i n which case both points i n the p a i r are p o t e n t i a l edge p o i n t s and so are l i b e r a t e d f o r re-examination by the c l u s t e r i n g a l g o r i t h m . at every s u c c e s s i v e lower l e v e l of the p i c t u r e pyramid the c l u s t e r i n g a l g o r i t h m w i l l a s s i g n a segment l a b e l t o every p i x e l t h a t i s e i t h e r a p o t e n t i a l edge or i s l a b e l l e d as edge i n the corresponding l e v e l of the edge pyramid. Levine p o i n t s out that the main purpose a t t h i s stage i s to reduce the number of u n i t s next p r o c e s s i n g stages w i l l have to work with. At t h i s stage no use of context i s made. The image i s segmented i n t o uniform r e g i o n s i n a context independent f a s h i o n , t h r e s h o l d i n g each p i x e l i n d i p e n d e n t l y . More i n f o r m a t i o n about the ' r e a l world' represented i n the p i c t u r e w i l l be used i n the next ( i n t e r m e d i a t e and high) stages of the r e c o g n i t i o n system [ 3 7 ] . . This o b s e r v a t i o n leads to one o f the s t i l l obscure p o i n t s about these h i e r a r c h i c a l data s t r u c t u r e s . In f a c t i t i s not yet c l e a r e x a c t l y what p r o c e s s i n g can be performed i n a cone (or a decomposition t r e e or a pyramid), and what p r o c e s s i n g must be performed by some higher l e v e l stage. The c o n v e n t i o n a l approach to machine v i s i o n sees the 33 i n t e r p r e t a t i o n phase of t h e whole r e c o g n i t i o n process as s e q u e n t i a l l y f o l l o w i n g the segmentation phase, but as has r e c e n t l y been shown by Mackworth [ 3 9 ] segmentation needs semantic i n f o r m a t i o n ( i n t e r p r e t a t i o n ) to be performed s e n s i b l y . Segmentation i s i n t e r p r e t a t i o n and v i c e v e r s a : to be meaningful segmentation needs to be d r i v e n i n some way by i n v o k i n g a r e a l world model, but such a model can't be e l a b o r a t e d without having f i r s t i n t e r p r e t e d the p i c t u r e i n some way [ 3 9 ] . F o l l o w i n g t h i s paradigm the whole v i s i o n process becomes an a l t e r n a t i o n of segmentation and i n t e r p r e t a t i o n . I t seems to me t h a t any segmentation obtained e x p l o i t i n g K e l l y ' s idea of planning as developed in the pyramidal approach, i s p a r t l y i n the l i n e o f t h i s paradigm. In f a c t , even i f the segmentation at every l e v e l i s made i n a c o n t e x t f r e e way, the same segmentation g i v e s a context to (and d r i v e s ) the segmentation at the l e v e l below. T h i s i s an i n s i g h t I attempt t o e x p l o i t i n t h i s t h e s i s . 34 2.2 Region Merging A completely d i f f e r e n t approach to p i c t u r e segmentation, £§2i2S merging, was f i r s t taken by B r i c e and Fennema [ 4 0 ] . They re c o g n i z e that a segmentation i n r e g i o n s using a simple equivalence r e l a t i o n induced by the s i m i l a r i t y of the gray s c a l e i s g e n e r a l l y i n s u f f i c i e n t t o reach a simple i n t e r p r e t a t i o n w i t h i n the problem domain. Therefore they s t a r t with "atomic r e g i o n s " (regions of constant gray value) and use more g l o b a l i n f o r m a t i o n to merge them i n l a r g e r coherent r e g i o n s . In p a r t i c u l a r the p r o p e r t i e s of the r e g i o n s along t h e i r boundaries are c o n s i d e r e d : two r e g i o n s which do not d i f f e r too s t r o n g l y along t h e i r common boundary are j o i n e d together i n one r e g i o n . Here, the s t r e n g t h of an elementary boundary segment i s defined as the absolute value of the d i f f e r e n c e i n gray s c a l e of the two p i x e l s on the r i g h t and on the l e f t of t h i s segment. The r e g i o n merging a l g o r i t h m i s a two step procedure. I n the f i r s t s t e p , two r e g i o n s , Ri and R j , a r e j o i n e d i f W/PH > Q1, where Pfl=min(Pi,Pj), P i i s the perimeter of R i , P j i s the perimeter of R j , w i s the l e n g t h of the weak part of the boundary I between the two r e g i o n s , i . e . , the number of elementary boundary segments having a s t r e n g t h l e s s than a p r e d e f i n e d minimum, and Q1 i s a t h r e s h o l d (phagocyte t h r e s h o l d ) . According to t h i s c r i t e r i o n , then, the two r e g i o n s are merged i f the r e s u l t i n g boundary of t h e i r union does not grow too f a s t . In the second s t e p t h i s c r i t e r i o n i s somewhat r e l a x e d : two 35 regions are merged i f W/I > Q2, where Q2 i s a t h r e s h o l d (weakness t h r e s h o l d ) . T h e r e f o r e , i n t h i s step the two r e g i o n s are merged i f the weak part of the boundary between them i s at l e a s t a c e r t a i n percentage of the whole boundary. B r i c e and Fennema do not use general knowledge about the scene domain. They a s s i g n an i n t e r p r e t a t i o n to the r e g i o n at the end of the segmentation process. Yakimovsky [ 4 1 ] uses the previous i d e a s as a s t a r t i n g p o i n t . His work goes beyond t h e i r s i n the f a c t t h a t he p r o v i d e s d i r e c t i n c o r p o r a t i o n of s p e c i f i c problem i n f o r m a t i o n i n the segmentation process. His world model i s a p r o b a b i l i s t i c one. Background i n f o r m a t i o n on the scene under study i s c o l l e c t e d by the system from t r a i n i n g examples. I n i t i a l l y a c o n s e r v a t i v e segmentation i n atomic r e g i o n s i s obtained t a k i n g sample p o i n t s i n the image and growing a region around them a c c o r d i n g with a t h r e s h o l d c r i t e r i o n on the p i x e l f e a t u r e v e c t o r s . Following t h i s , a non-semantic r e g i o n grower i s used to i t e r a t i v e l y merge r e g i o n s on the b a s i s of a B r i c e and Fenema type c r i t e r i o n : on each i t e r a t i o n the p a i r of r e g i o n s whose common boundary i s the weakest i n the c u r r e n t image p a r t i t i o n i s merged i n t o one r e g i o n . In t h i s stage the " s t r e n g t h " of a boundary i s c a l c u l a t e d as the average d i f f e r e n c e between the values of p r o p e r t i e s of the p a i r s o f p o i n t s along the boundary. 36 F i n a l l y a t h i r d step i s c a r r i e d out i n which the world model i s used t o d r i v e the r e g i o n grower a l g o r i t h m . F i r s t , a d d i t i o n a l p r o p e r t i e s ( l i k e shape) of the r e g i o n s and boundaries of the r e s u l t i n g p a r t i t i o n are assigned to the a l t e r n a t i v e i n t e r p r e t a t i o n s of the r e g i o n s . The boundary s t r e n g t h f o r each boundary i s now d e f i n e d as the p r o b a b i l i t y of t h a t boundary being r e a l , a boundary between two d i f f e r e n t o b j e c t s i n the world model. Again a weakest-boundary-first c r i t e r i o n i s used to merge the two r e g i o n s . The program performs s u c c e s s f u l l y i n two d i f f e r e n t scene domains: an outdoor scene and a r a d i o g r a p h i c image. 37 2.3 I n t e r p r e t a t i o n D i r e c t e d Segmentation of LANDSAT Images The s e m a n t i c s - d r i v e n region growing a l g o r i t h m d e s c r i b e d by Yakimovsky i s along the l i n e s of the paradigm d i s c u s s e d at the end of sec.2 . 1 (the i s l a n d - d r i v e n theory o f p e r c e p t i o n o u t l i n e d i n [ 39]) . Other s u c c e s s f u l experiments with t h i s paradigm are de s c r i b e d i n [42] (domain: indoor scenes) , and i n [ 3 8 j (domain: sketch maps) . In [ 4 3 ] a program i s d e s c r i b e d t h a t i n t e r p r e t s a LANDSAT image with the aim o f v e r i f y i n g the f e a s i b i l i t y of t h i s approach on t h i s domain. The image under study d e p i c t s f o r e s t s and l a k e s , the aim i s to c l a s s i f y r e g i o n s o f o l d growth, second growth, recent l o g g i n g and water. The scene (Fig.1.1) i s a good example of a standard LANDSAT p i c t u r e and most of the p r e v i o u s l y d e s c r i b e d procedures wich use context i n i n t e r p r e t i n g s a t e l l i t e p i c t u r e s ( f o r example Bajcsy and Tavakoly [27]) would hardly be a p p l i c a b l e to i t . A s u p e r v i s e d parametric approach i s taken to perform a f i r s t p a r t i a l c o n s e r v a t i v e i n i t i a l segmentation of the whole scene. The c l a s s e s of i n t e r e s t are assumed to be d i s t r i b u t e d a c c ording to a m u l t i v a r i a t e normal d i s t r i b u t i o n and a maximum l i k e l i h o o d c r i t e r i o n (see sec. 1.2) i s used t o a s s i g n every p i x e l to a c l a s s . The number of c l a s s e s i s augmented i n the f o l l o w i n g way: i f 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 (p.d.f.) of the p i x e l 38 f o r any of the f o u r b a s i c c l a s s e s ( c a l l e d strong c l a s s e s ) i s below a given t h r e s h o l d , then the p i x e l i s assigned to an "ambiguous" c l a s s which depends on the f i r s t and second g r e a t e s t values of the p i x e l ' s p.d.f. . The value f o r the t h r e s h o l d i n f l u e n c e s both the number of r e g i o n s i n the i n i t i a l segmentation and the o v e r a l l c o r r e c t n e s s of the c l a s s i f i c a t i o n f o r the s t r o n g c l a s s e s . ft s m a l l t h r e s h o l d g i v e s many p i x e l s assigned to the s t r o n g c l a s s e s but the o v e r a l l c o r r e c t n e s s f o r them i s low (with a value of z e r o f o r the t h r e s h o l d the whole p i c t u r e i s c l a s s i f i e d i n the b a s i c f o u r c l a s s e s ) . A l a r g e t h r e s h o l d gives a b e t t e r o v e r a l l c o r r e c t n e s s f o r the b a s i c c l a s s e s but very few p i x e l s are c l a s s i f i e d as strong and the t o t a l number of r e g i o n s becomes very l a r g e . F o l l o w i n g t h i s a three-pass r e g i o n merging a l g o r i t h m i s c a l l e d t o grow r e g i o n s a c c o r d i n g to semantic c r i t e r i a . The idea i s t h a t r e g i o n s c l a s s i f i e d as strong keep t h e i r l a b e l and i n f l u e n c e the c l a s s i f i c a t i o n of adjacent ambiguous r e g i o n s . A l i s t o f t h e ambiguous r e g i o n s i s kept: the program i t e r a t i v e l y scans the l i s t . For every ambiguous r e g i o n , a l l the adjacent s t r o n g r e g i o n s are examined. The one t h a t "has the weakest boundary" i s merged with i t and g i v e s i t s l a b e l t o the r e s u l t i n g r e g i o n . The f i r s t and second passes of the a l g o r i t h m use measurements on the boundary to c a l c u l a t e the "phagocyte" and "weakness" t h r e s h o l d s of B r i c e and Fennema which h e u r i s t i c s are 39 s e q u e n t i a l l y augmented i n the f o l l o w i n g way: In the f i r s t pass, to have an adjacent strong r e g i o n as c a n d i d a t e f o r merging, the highest value of the p r o b a b i l i t y d e n s i t y of the ambiguous r e g i o n under c o n s i d e r a t i o n , as c a l c u l a t e d from the average r e f l e c t a n c e values f o r the whole area, must g i v e the same c l a s s as the strong r e g i o n . And the same must be t r u e f o r the r e g i o n t h a t would r e s u l t from the union of the two., Among a l l the strong r e g i o n s t h a t are candidates f o r merging the one chosen w i l l be the one that minimizes a kind of d i s p e r s i o n f o r the average val u e s o f the r e f l e c t a n c e as c a l c u l a t e d f o r the p a i r o f r e g i o n s (ambiguous r e g i o n - s t r o n g r e g i o n ) . F i n a l l y the two regions w i l l be merged i f they have enough border i n common (phagocyte h e u r i s t i c ) . S i m i l a r though l e s s r e s t r i c t i v e c r i t e r i a are used i n the second pass. The t h i r d pass simply gets r i d of the remaining ambiguous r e g i o n s a s s i g n i n g them to the c l a s s t h a t g i v e s the b i g g e s t d e n s i t y p r o b a b i l i t y value. For a thorough d e s c r i p t i o n of the program see [ 7 ] . T h i s program improves the o v e r a l l c l a s s i f i c a t i o n accuracy from 71% obtained with a p o i n t by p o i n t c l a s s i f i c a t i o n ( i n i t i a l t h r e s h o l d equal zero) to 79%, reducing the number of r e g i o n s t o h a l f of the number o b t a i n e d with the p o i n t by point c l a s s i f i c a t i o n . 40 CHAPTER 3 Using Pyramid S t r u c t u r e s i n the Automatic I n t e r p r e t a t i o n of LANDSAT Images The two methods of segmenting a p i c t u r e d e s c r i b e d i n the p r e v i o u s c h a p t e r , i . e . , the h i e r a r c h i c a l s t r u c t u r e s of Uhr, K l i n g e r , Hackworth, Tanimoto and Levine, and the r e g i o n merging of B r i c e S Fennema and Yakimovsky are u s u a l l y seen as two b a s i c a l l y d i f f e r e n t methodologies i n approaching the scene a n a l y s i s problem. The d i f f e r e n c e i s seen i n the f a c t that while i n a h i e r a r c h i c a l s t r u c t u r e t h e p i c t u r e i s processed i n a top-down way,i.e., through moving from coarse to f i n e r e s o l u t i o n or through p a r t i t i o n i n g the p i c t u r e i n t o s m a l l e r and s m a l l e r r e g i o n s , i n the r e g i o n merging approach the a n a l y s i s s t a r t s at the p i x e l l e v e l , and b u i l d s up a g l o b a l p i c t u r e d e s c r i p t i o n by growing r e g i o n s . Despite the obvious d i f f e r e n c e i n point o f view, a n a l y t i c vs s y n t h e t i c , the two methods should not be compared as they have been used i n d i f f e r e n t stages of the scene a n a l y s i s process. In f a c t , except f o r Ohr's r e c o g n i t i o n cones t h a t are s t i l l i n an e a r l y stage of development, h i e r a r c h i c a l s t r u c t u r e s have been used mainly i n the p r e p r o c e s s i n g stage of machine v i s i o n systems, i . e . , t o speed up the edge f i n d i n g o p e r a t i o n s or to get an i n i t i a l c o n s e r v a t i v e segmentation i n atomic r e g i o n s , see f o r 41 example l e v i n e [ 3 7 ] and Mackworth [ 3 8 ] . I t was noted i n sec.2.1 t h a t one point that i s not yet c l e a r about the top down approach i s what p r o c e s s i n g can be performed i n s i d e an h i e r a r c h i c a l s t r u c t u r e and what processing must be performed by a higher l e v e l p rocessor. Region merging, i n s t e a d , has proved to be a very powerful technigue i n performing the e n t i r e r e c o g n i t i o n process because i t allows i n t r o d u c t i o n of semantics a t s e v e r a l l e v e l s of complexity ( p i x e l s , atomic r e g i o n s , r e g i o n s , r e l a t i o n s among re g i o n s , e t c . ) . The p r o j e c t h e r e i n d e s c r i b e d i s concerned mainly with the use of a h i e r a r c h i c a l data s t r u c t u r e , i . e . , a pyramid, as a t o o l f o r c l a s s i f y i n g a LANDSAT scene. The i n t e n t i o n was to design a scheme that could allow most of the c l a s s i f i c a t i o n procedure to be performed i n s i d e the pyramid. Much context can be used while going down the s t r u c t u r e (from lower to higher r e s o l u t i o n ) and i n p a r t i c u l a r one can t r y r e g i o n merging at every l e v e l i n an attempt to improve the r e s u l t i n g segmentation. Moreover, semantics can be used to c o n t r o l the b u i l d i n g o f the pyramid (from higher to lower r e s o l u t i o n ) . The p i c t u r e used i n t h i s study i s the same 1 as the one used i n [ 7 ] . T h i s i s because the same ground t r u t h map of a f o r e s t e d area of Vancouver I s l a n d ( F i g . 3 . 1 ) , provided by Murtha *This i s ERTS frame No 1385-18365, Aug. 15 1973 III n « i # r f j ! 1 i ' i ! i i M M •;^:?J:;:;;:: : ;:V:J ^ rii m u IM5 i! n V i m t t m "^•^"nrii i ui i#-^>£y k.^-> W r y — A -\ l irx/x. :.:.rr:^^ r~:r""^  — ^ ^ - " - v , . . ^ . v > x ~ — — ^ / > X \ X X X A•//? x r ^ - X ' - ' ^ i iiiiii^Biiiia v WX-k:///f ^*\Y/y/A'V////^y&//^\^/W /*'\Y///Jyky>r :^-: :'r^ • • •>'.• /..-i Z V/ • ,M//////\;,y///7):\:Y//yA??'%\\///f?\>>>t-{-\-: 1 ( v:-:vs::-::-^ ;::-:> A y , VrXXXx; \;j (.„ -X^vXXX ^ s ^ X x - ^ - , \ X r ^ V \ X X \ • v V - . 4 ^ v A \ y - H ! -^vo ft.,.Uw^vi,/>i,~^ -xxx OLD GROWTH ov e r mature mature SECOND GROWTH o l d r e c e n t RECENT LOGGING canopy c o v e r 7 5 - 1 0 0 $ canopy c o v e r 50--7^ % canopy cover 1-^9 % 1973 c u t t i n g 197^ c u t t i n g l a k e s roads a g r i c u l t u r e towns tr«8 m S E S B ; LJ F i g u r e 3 , 1 The ground t r u t h map ( t h e a r e a of i n t e r e s t i s e n c l o s e d i n the s q u a r e ) . F i g u r e 3*2 An information Tree for the scene 0 44 [ 4 4 ] , i s used. T h i s map a l l o w s the p o s s i b i l i t y of attempting s e v e r a l l e v e l s of i n t e r p r e t a t i o n . In Fig.3.2 a p o s s i b l e i n f o r m a t i o n t r e e f o r t h i s scene i s p i c t u r e d 2 . In t h i s case f o u r c l a s s e s , v i z . , o l d growth, second growth, rec e n t l o g g i n g and water, were sought, because the same maximum l i k e l i h o o d c l a s s i f i e r implemented by S t a r r [ 7 ] and the method de s c r i b e d i n [ 4 3 ] and reported i n sec.2.3 were used. The scene i s s t o r e d as a 64x64 ar r a y . T h i s i s l e v e l 1 i n the data s t r u c t u r e . The pyramid i s obtained by s u c c e s s i v e l y averaging groups of f o u r p i x e l s , i . e . , the f e a t u r e v e c t o r f o r the r e s u l t i n g p i x e l w i l l have as components the average of the r e s p e c t i v e components f o r the f o u r p i x e l s , wich components c o n s i s t of the values of the r e f l e c t a n c e f o r band 5, band 6 and band 7. Fig.3.3 i s an image of the area under study at the highest r e s o l u t i o n o b tained o v e r p r i n t i n g the d i g i t a l data f o r band 6. The d i f f e r e n t c l a s s e s can be seen as d i f f e r e n t patches i n the image, f o r example the l a k e s i n the scene are c l e a r l y v i s i b l e s i n c e the v a l u e s of the r e f l e c t a n c e are very low f o r water. Fig.3.4 and Fig.3.5 are o v e r p r i n t e d images at the next two l e v e l s of r e s o l u t i o n . Among other t h i n g s these p i c t u r e s suggest one of the l i m i t s to u s e f u l averaging. The hypothesis i s that p i x e l s i n the 2 F o r a s u c c e s s f u l human-interpreter experiment on these l e v e l s of c l a s s i f i c a t i o n using multitemporal data and a c o l o r - a d d i t i v e viewer see [ 4 4 ] . 8 9 A 9 a A N 9 © $ ® A « e f t © © ® S 8 ® © ® © f t f t A A AM8ft A-K998 6© ft ft©8 9© ©8 ©©$«®®$$f i® 9 © ©© ®©© H H ft 9 ft A 0 6 6 M S H 6 ft ft A M 6 6) © © © © © «iB 8 ft ft i\ ft ft M A H 6 © ii 9 ffi 8 8 © © © 9 © © © k © © 3. © © © © © © © § 8 9 © 9 9 e e I'i e e .© © M e 9 M 99 9 © © © 0 © © 0 f ID a 9 3 e w ft A A A M 9 © © © © e © ©©©8©©®®s#©©©©©©©e8©® © © © 9 9 99 9 M 99 9 9 9 © © ff) 9 © ® 0) © © Si S € © ® A « A X A X 8 © » 0 9®*® © © 1?) 8 ffl 89 98! 9 9 © 9 © © 9 8 © $ © © $ ft ft 9 8 d © 8 M M 8 9 9 (189© * © 9 9 © 9 © © S E§ $ «) A A A X A A ft 9 ti 9 © © 9 ® 8 9 M 9 © © © 9 8 ffi 9 © 9 © © 9 © © S 0 «>' 9 9© 6 6 © 6 9 8 8 9 HA A 9 © © 8 ©9 © © 9 © g § 0 © © A M A A ft9 99 89 9© 9 9• © © © 9 ©© ©9 8 9 99 ©9 © © 9 © ©© © ee9e©Si$eM0©Me6©©8eee8©©a2a'3SAMKHA9oeea?«?i88©©B9©8©©®e©®©e6a©i8®®® © 9 © m © © ® E© © 9 9 9 8 © 9 © © 9 9 999Z 3 Ii & ® S Si ft A A M 8 9 H © © S 9 © ©9) 8 © © 9 9© © 9 9 8 © 0 9 © © @ § © © ffia®©©s®©e®f>©©Me'e©e©©©8©®es®igiaisg©M86en8©ise®©©9ffl©s.f®©88©eee®®®as& ©®©e«)®©e®©g®fse©©©©®®©©®9©«SMa3g©©®M8©9«©®®©^©e©©©®©©©@«©9®@©e©@ 0aee«<©$ffl9«©@©!ee©©©(«as®s@f i©9ea®9«@©©e6§ : B8@®«9@9ees9«©©9@s©©©®©a© © 9 © 9 9 © 9 ©9 98 © * © © © © 9 $ 9 © © £ $ Ii # a ® 9 A A 8 ffi © © M Ft § © © © 6 © © S © 6 © © ©8 89 © tl 9 8 © © © © © 0 9 ©9©9«98«©©9e©©©©©©®®f f l©©^|.@S5e©©MKK©9M«8£®B®©©f®©©9KM9AKeNMe©®»e6« ®®9899©e©e©©e©e©»9@©©99©©©©©eM-®S98M8!i8©99©9©©S®©8®eH©8©©®©@©©M8Q ®8A > Ai - iA i iAAAe©M©©'©gs[ i#6©e©©©©8e®©®i®9A«p ie©®©§a©©©9e9©©®©*©®©$sg©ia XZZZa©®H©®©«®©BEiae©8©©ffiS©©88M©e®B©9©©9©©©@©®©©89©®ffl©SI2SSI©S9Mft S XZXX8©©©©®B©©©Sffl©A89©©©§©®§@ee©©©©©©®©©©©©©9©©©©©©©S©©©SS©aiAffi88® x x x M A 8 a © 8 M e o 9 z M e A «®©©©®©©©®e©©©©6©©®©©©® @ ® © © ® © i & $ ® © $ $ © © © $ © © $ © $ $ x A A M A A M f i e e a s z x A faeeM®e8©©©©©©8©©9ee©©©88©©©©©©©a»©©9®©©©©®ffl®©e©®eM AA899H9©©e8Ae©ee©eMXAM©©e©©®®s)e9e©©8©©©©©ee©e®©ee#©©e©©©§se©8A6« ©@89©tii ,!A8AAHH9©©©©A8X8e©eA.AA«8©ae©©©®©©©®©©©©©©©©g!©©©©e©©©©©©©©© 8 9 i'i 6 ri ii 8 ii ii 9 9 M A 8 © © 9 8 9 © M 8 9 © 8 H 8 8 i i l i© A © 9 9 © © © © © © 9 § ^ 9 © © 8 9 © © Ii 8 ft © fi@©©@HKM H ©f^©8©©©©69MM68©©9©8©8©999©99MA A99®®©8®©9©® ©9©©©©ftAXti©©©©© AXA A A A 0 # © 9 » © © © © © © 9 © © © e e © © a © e e ® « © © e e « 9 6 © A M ® 9 ©©©•©©© ©989XMAA©»#®©©©aAe8f j A ffi©©e©©©©©©e©©©9©©©e©§©Q@©©©©®©©©9©aAeM©e®@@©AXM©©©®©®e®©#©e©9e9M s©©«©©®«9©«©ee9©©®©©©©®©©®®®©®©©ff i9e®©.8e9MZA 'M©©#©©©©e«©©®©®©©ee-@ 8SSf!«g£aSS©8e«e©©@®©®@©©©@©©®©M6©®@S9«9ZAe©®©©©©S-©© A+Z®©®9®®@8©e #©9©§©e£aB©@a -©M©Ba©®©$®©©#®«M«©®©i©a©©M©e©©®®©©©®©©©eM=—=©s©s@© e®©©fe©8£SS©£3©©®©3£©©§&Sl©©©©®©©©99©©©9©6$gf f le©©©©©©@©©8© — 9 © # © @ © © $ S® ©S © © © © 3 S © ® m © © 9 i © § © © © © 0 © © X A 9 © 9 9 Q © ii 9 © © © ® © © © © 9 ft • = -®©©©fc©®©@®BgSf®S©©$f $9M99AAH©©@©®eH8a 1 X A AZ Ai iZX99@9©©©«©©©9&~-© © @ ® © © i S g l l I S $ @ © © © © 9 8 © @ 7 t i f M © © A A A A A A } XXA X X X Z A A A 9 8 © 9 9 ©©©8©©©@Z+-= S@©©s©3 SS3CE©©e®©©©©@©©©MAAXA HXXXAAXZX XX A©Mti©A99AA©©®©©9©®©S-§©S90 ®^©©*l®fi-aS#©©©©f§088A®®©H Aft90A AXft8A X A KA89H8998«KA©©@9[1X H9Z MH©®©@ f © © S # i i a i S© e 9 © f ) e© X 9 A M 8 9 9 1 A e 9 A X A A 8 © A ^ A © 9 M 9 8 9 A 8 9 : i A 9 ® © 8 © 8 8 © Z X X M f t 9 l 3 @ ®©©®©s®©f©®©ss©D®AAee88AXXAAMAe©969ea6e©©©eriAe©eeA« &enx AXKMeeft©-© ©©©©©©©$©©©©©$©©8AZAAM9f t i ' ]AXA6©©©866© © M 8 8 8 8 8 9 6 9@99AM M 9 9 A A ft M 9 ft © ft i'i A ©«®^©©©©©e©9H«©A A A A f t A 6 9 S M A X M©©@©f i©89©©9999969© 9 © 9 AAX6AHA99M©AZHft @© XX AXKM8MM A A M 8 © 8 8 8 A 8 © 8 © © © 8 M 9 9 © 8 9 9 9 © A K©© 8 9 ©8 A A A A©8©©98@8© © 9© ©&©© © A tl A A A iii-18 M MA H £1M8 [•! ©89©©@9899A M118©©©MA B M9©9© MX = M H+ f i6 .©99H6AH S ©3©©®$© A 9 X X 9 8 8 6 8 AM8iie©8©@M8©@98 A H 8 8 AMZ ©8M9 N AM8 AM AX AM AM 8 8 9 MX X A© ©®®8@®Z A A8KQ©ir89M© K M 6 9 © © © 9 M 8 © © A X 9 ii M i i A A A 8 8 A 9 c\ X 9 9 A A AX A 8 © X X Afi A W © 9 E 0 S £ M X ti A A 9 9 9 K6© ©© © 9 6 M © ii 6 ii © 9 © 6 © 9 ii M A M 6 M 9 H MHZ+A 8 M ©M?'i A Si ft i1 H MAX© ft ii M « ft 8 8 ft e 6 Z X a 9 6 88© 6 e © 8 © © A f t H 6 A 6 6 9 A ) 8©9M8a9©9K9f tAKAf t6 f tA?1©©©99f t6MM M 8 M 8 Q 9 Q 8 9 €15 A M 9 8 © 9 8 8 8 ) €©©©©6e®®©68©999©8@9f te69X AM A A A A 8 9 M 8 S © ® 8 e 8 H 9 © © © © ft 9 9 8 © ft A M ft 6 9 9 ft 9 g 6 9 8 8 X 8 9 8 8 © © ©96 9© 8 9 © © © ii ft ii 9 M ft ft A ft A ii ii 9 ft 8 6 i'i © © © © © 9 M 9 © © 9 ft 9 ft 9 e © e 8 f i S 9 6 © © 9 6 © A 9 9 e 9 A 9 © e © © 9 © 9 6 © 9 © 6 9 8 9 H 8 A A 9 8 A 8 f t M M A 9 H89© © § § © © © © A M © 8 8 98f tAAAA9©9f t9©8ft I ' i9A6©M©©9M999©A©98AAAM9A AM MM A8HAftMMA©9©©98©8©9 8 8 A © 8 X A ft A A 9 8 © 96©A H i i 8 8 6 © © 9 9 © 9 ft 8 M ft ft 9 © ii M ft X ft M A ti A 9 ft ft M A ft ft ft ft A ft 9 © 8 8 ft 8 H Z M 9 © © A ft X A A A P! 9 © 6 © 9 © ft MM © 9 © © 9 8 G © © 9 © 9 9 9 9 © 9 A M ii 9 © 8 A A A A 9 9 9 A ft K ft A A A 6 9 9 8 8 9 X A ft A @ A 8 6 9 f t 8 8 © © 9 f t 9 9 A©6e ! i 8 © § 8 9 9 9 M £ 9 M 6 M r i X 9 9 9 © © K © ) A A 8 8 9 A Aft X A X A © A © ©© A X 9 A A 8 ft 6 ft ii Li © ft © © 6 8 9 - 9 8 9 6 9 6 ft 6 © ii 9 © 9 9 9 ii A M ft ft ti ft M 9 ii 9 9 6 i i ft ft ti 8 M ii A9 ft A A ii H 9 9 9 9 © MA ft 9 9 9M69 - o e 8 © © © 9 n 9 6 © 8 9 8 9 e 9 6 8 e f i 0 t M 9 A © [ i © 9 9 9 9 8 © 8 8 6 M 6 8 I i89K f t AM 99 i v !©B999i '19- » 6M A Kii@9©©©8 A © 6 0 i i 8 8 8 6 6 9 M 9 £ ) 8 A A 8 8 A M6M6 M6886969-A A 6 AMM6AMM AM A AM9 A6— ©8ft ft ft 6 6 3 9 ft ©6X ft 8 8 9 8 8 9 8 8 8 9 © © ft M ft ft 8 ft M 689 M 8 M M •© ft 8 © 8 9 6 8 M ft M ii M ii ft M A 8 M8MM9 = » ©$ © © © © ft ft A Z A -9 ft 9 9 ii 9 9 © © © © 9 A A. A A ft A Aft 9 9 9 8 ii 6 6 A 9 © © © A 6 6 9 9 9 9 9 9 ft A ft M 9 A 9 ft ft ft) © © § © * © © ft A 9 © 6 91 \999 © © © © © © A M ft 9 A 6 A8 ft 8 6 ft Z A ti K 9 M © © 6 9 8 8 8 8 9 8 8 8 8 9 A ft 8 8 9 6 ft ft ft 9©8>»©»®»8e9 M ft 6 ii i'i ft 9 © © ffl © © A 6 © 9 8 ii 9 6 9 9 96 9ft - ft A 6 9 &l 8 6 8 ft 6 ii 9 ft fj9 8 9 ft ft 9 9 © ft ft 6 8 © ® S © & © © © 9 © © 8 A A A M 8 <B 9 ® © 8 © A © S © © ® ® ©666© © © 9 A A 6 8 9 6 0 9 9 6 9 9 © ©©989© A M 9 M H 6 9 © © 8 1 © © © © © © BJ © «9 A 8 8 ffi © © (9 ® ® © © 6 9 © © © 6 9 A 9 ft © « © © © 6 6 6 9 96 © 9 ft 9 © © © 9) 9 § © © 9 8 © 9 ft © 9 © 9 © © © <fm ( $ © — - m ii © ®®®®»6 6© © ft © 8 A A A 8 A M 8 9 © m © ft 9 © 9 © © © ©9 8© •« © 6 © © « « 9 9 9 9© 9 I? © © 8 * « © S > ~ © © 8 9 ffi © © © © © © ® © 9 ii X M 9 © 9 6 9 © © 9 ©8 © © 6 © © © © © © © © 8 9 © © © 6 6 © 6 9 A © ii ,© 46 middle o f r e g i o n s get averaged with p i x e l s belonging to the same c l a s s , while p i x e l s on the boundaries get mixed t o g e t h e r with p i x e l s belonging t o d i f f e r e n t c l a s s e s . As the averaging operator keeps being a p p l i e d the boundaries get l a r g e r w h ile the patches i n d i c a t i n g c e n t r a l areas of r e g i o n s get s m a l l e r . In s t a t i s t i c a l terms t h i s f a c t can be s p e c i f i e d by s a y i n g t h a t areas composed of p i x e l s that have egu a l p r o b a b i l i t i e s of belonging to two or more c l a s s e s get l a r g e r by the averaging process, while c l u s t e r s of p i x e l s t h a t have a high p r o b a b i l i t y of belonging to a s i n g l e c l a s s get s m a l l e r . T h e o r e t i c a l l y one can b u i l d the pyramid u n t i l e v e n t u a l l y g e t t i n g to the highest l e v e l , which c o n s i s t s of one p i x e l with a value f o r the f e a t u r e v e c t o r egual t o the average f o r the whole image. But as one goes up i n the pyramid the gross f e a t u r e s ( c e n t r a l areas) of the s m a l l r e g i o n s s t a r t d i s a p p e a r i n g u n t i l the n o i s e of the boundaries e v e n t u a l l y c o v e r s the whole image., The optimal l e v e l a t which t o stop the computation o f the pyramid can be e v a l u a t e d by having an estimate of the average s i z e s of the c l a s s e s under study i n the d i g i t i z e d ground t r u t h map. In t h i s case the s m a l l l a k e s i n the scene (average s i z e 15 p i x e l s ) suggest a l i m i t of, at most, l e v e l 4 (2*=16) to the averaging o p e r a t i o n s . In f a c t , as can be seen from Fig.3.5, at the t h i r d l e v e l the areas o f water begin t o disappear from the reduced image. A l a b e l l i n g procedure i s s t a r t e d with the a p p l i c a t i o n of © ® © © i © x X © CD CD CCS © © 63 © © © © >> ffi CD CD CD © © © © © CD C© CD © © & CD cm CD © © © CD © © © @ CS CCD CD CD CD © ® © © Ct) © 3 Cu) 3 3: 3 3 CD CD CD © <n> © © CD CD CD 3 CD 3 CCD c s CD 3 CD CD CD SS X 3 p> 3 CD CD CD © © CD CD CD CD CD © CD © CD CD 3 CD 3 CD (D £3* CD CD 3 3 3 CD CD CCD CD (2- <tr. 3 CD CD CD CD CD CD CD CD CD CD CD CD CD Ct- CD te- 3 CD s 3 3 CD 3 3 CD CD CD 3 CD CD > ! » 3 3 SP* 3 Ct) B CO © cr CD 3 i-s 3 3 3 J » 3 3 , Ct -CD CD CD CD CD CD CD 3 3 CD 3 CD CD CO) CD CD CD ffi CD © © CD CD CD CD CD CD 3 CD © CD © © 3 3 3 £3; ;*» 3 C t 3 3 CD 5 » 3 X 3 3 3 CD > © ® it) © © «S sr. cw CD X © 3 © 3 CD 3 CD 3 © I t © IC CD CD CD © S=* CD 3 3 3 3 3 3 CD CD 3> 3 3 3 5 * X 3 CD 5> 3 f B CD CS CS CD © CD CD CD CC6 S» 3 CD 3 CD 3 CD cD CD 3 CCD © CD CD cr?) CD 3 CD > CD i i» (SI 3 > X 3 © 3 . CD CD > ' 3 3 CD ® CD © CD * © 3 CD CD 3 3 5=< 3 > CD © © © CD 3 CD (tt) CD CD CD CD © CD CD CD CD CLD © CD 3 ^ 3 CD 3 > CD > CD 3 3 CD CD CD <S5 © © © eg BSi P» o a EX! © ® CO © CD CCD CD CCD © CD X 3 CD CD 2* 3 5> X CD 5 » 5 » N 3 X s a> CD 2 * 3 CD 3 3 CD CD CD •© © © © CD © X © S» CCD CCD C» © CNl e* «s> ® s e* «© © ® <&> sea CCD <2> ftb "SB CD © © e© © @ © © CD © X © 3 © 5=» © 3 © CD ® ffi ® © G5 © © (& CD 6£> i » ? & ' © @ (16 <0fe © & « . © CD © © a.' © © © •«•> CD ® © & © ® © © © © © © CD CS> 3 © © 3 © 3 © CD © © 3 ^ ? 3 © © © © ffi © © 85 © CD © CD CD 3 CO CD CD CD a> CD CD a X ES> le> X S=» CO CD ® CD 3 3 © CD © © CD CD © 3 CD 3 © © CD CD Cft CD CD © © CD © © CD © ffi © © Si? 8 » © © © @ © © 3 © CD * CD © S3 © © © © Jp< © © © © <© « © CD c* &> © © © © ® © ffi © © €B «gj © © SB © © © s& © CO) ffl CD ® cb 3 © 3 © CD © Ct © © © © SB © e © © © «B © es> s ® ® © CD © 3 © CD 3 © © <S* © et © <® © *£> • @ © © CD © CD © 3 C-S CD © CD © ® © CD © © CD CD © © C-& © S ) ©a? © © e* & ® © © © » a> © <£> CD ffi © © ??> © CD & © CD © © © © O 6B CT) f?> s?i © « ts) sa CD i S S J » 6 3 © CD CD CD CD CD © © © © CD ffi © CCt © CB © CD «fi © © © CD es © ® * © ffi © © © © CD CD © a> © © © © © © © 3 CD 3 CD CD 3 CD CD 3 CD CD CD 3 CD © CD CD & 3 CD CD © CD 3 © © ® © © © & © ® © © © & & CCD eg ® t s CD 3 3 5 » fc» 3 > > t » 3 CD O CD © CD © © CD © © 0 ) © © © CD CD © CD © © © © © © © © © ® & © © © © © ® © ffi m © * © © &> © F i g u r e 3 . if L e v e l 2 of the pyramid 3 D2 3 © CD CD © © CD CD (X) CD 3 S3 3 3 CD CD CD ® C£ © a a Ct <£> © CD CD © CD 3 CD CD 3 3 CD CD © & 3 3 CD 3 CD © CD CD P=" CD CD 3 3 et> 3 CD ;x» CD 3 3 2 CD e » © CD CD e c 3 3 CD 3 © CD 3 CD 3 CD 3 © CD © > 3 © CD r s cb CD 3 © © CD 3 CD 3 CD CD CD 3 CD CD 3 CD 3 ® © CD X CD © CD CD ® © C D C D ( p ® © C f i «0 © 3 © © © © tfi> ® © C t ) © ® « > C D < D e e c? cc a;- (E ffi ® © © C D © ® ® © ® © © C D ® ® © C D © © ! ^ © 3 © ® © t f ) © < & 3 3 3 © © © © C D © ( t ! ) © © S ® @ t B © © S 3 © ® © © © © © s > © c e ® © © © © CD © f f i <® © © © ® + ® © ^ ? B C f i © i 9 N C D C D © © ® © ® F i g u r e 3 . 5 L e v e l 3 of this pyramid 48 the maximum l i k e l i h o o d c l a s s i f i e r to the compressed p i c t u r e at the h i g h e s t l e v e l of t h e pyramid permitted by the scene under a n a l y s i s . A p i x e l t h a t g i v e s a 'high enough' value f o r 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 f o r one of the f o u r c l a s s e s of i n t e r e s t i s l a b e l l e d as s t r o n g , otherwise i t i s l a b e l l e d as ambiguous. (here "high enough* means that the computed value of the p.d.f. f o r one c l a s s must be higher than a given percentage of the sum of the p.d.f. f o r the f o u r c l a s s e s , see r 71 f o r more d e t a i l s ) The segmentation proceeds down the pyramid from t h i s l e v e l to the lowest. The s t r o n g p i x e l s are the s t a r t i n g p o i n t s f o r the r e g i o n growing process. They are simply expanded i n groups of f o u r p i x e l s , which keep the l a b e l a l r e a d y assigned to the parent, while ambiguous p i x e l s sent to the next lower l e v e l w i l l be re-examined. As pointed out above, because of the pyramid s t r u c t u r e , the segmentation at t h i s l e v e l already c o n s t i t u t e s a plan f o r the segmentation at the lowest l e v e l ; i n f a c t , c l u s t e r s of s t r o n g p i x e l s at t h i s l e v e l w i l l l i k e l y be the l a r g e s t and most uniform areas of the a c t u a l p i c t u r e . At any l e v e l the maximum l i k e l i h o o d c l a s s i f i e r i s c a l l e d to r e c l a s s i f y only the p i x e l s t h a t at the p r e v i o u s l e v e l c o u l d not be l a b e l l e d as s t r o n g . S i n c e there i s a compression f a c t o r of f o u r between two s u c c e s s i v e l e v e l s of the pyramid, every time a p i x e l can be l a b e l l e d as s t r o n g at l e v e l L, t h e r e w i l l be a 49 saving i n the c l a s s i f i c a t i o n o f p i x e l s by a f a c t o r of 4<«--i) over the point by p o i n t c l a s s i f i e r . Of course the t o t a l s a v i n g s are not as l a r g e as t h i s , because, on the other hand, a p i x e l t h a t i s marked ambiguous at l e v e l L i m p l i e s a t l e a s t four c a l l s to the c l a s s i f i c a t i o n a l g o r i t h m at l e v e l L - 1 . A p p l i c a t i o n of the averaging operator can be seen as making use of con t e x t i n the l a b e l l i n g process.. I f among the f o u r p i x e l s to be averaged t h e r e i s one whose f e a t u r e v e c t o r * s value would l i e i n some h i g h l y o v e r l a p p i n g area of 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 s {the areas t h a t are the i n t e r s e c t i o n of two or more e l l i p s e s of c o n c e n t r a t i o n i n Fig. 1 . 6 ) , the averaging o p e r a t i o n can make the value f o r the f e a t u r e v e c t o r o f the r e s u l t i n g averaged p i x e l f a l l i n a unambiguous area o f the n-space. The opposite can be s a i d i f the c l u s t e r of f o u r p i x e l s belong to a boundary area; i n t h i s case t h e averaging o p e r a t i o n makes the r e s u l t i n g p i x e l value more d e f i n i t l y ambiguous, i n s t a t i s t i c a l terms, than i t s predecessors. T h i s model of the s i t u a t i o n proved t o be a p p r o p r i a t e f o r areas where t h e r e were no changes i n the r e f l e c t a n c e values or where the changes happened smoothly. But when the t r a n s i t i o n from one region to another one was very abrupt, i.e.,when neighboring p i x e l s gave a high p r o b a b i l i t y of memebership to d i f f e r e n t c l a s s e s , then the averaging o p e r a t i o n sometimes gave a r e s u l t i n g f e a t u r e v e c t o r whose p.d.f, value l i e s i n an unambiguous, but i n c o r r e c t , area of the n-space. For example 50 p i x e l s r e s u l t i n g from the boundary between water ( c l a s s U) and f o r e s t ( c l a s s e s 1 or 2) were o f t e n c l a s s i f i e d as r e c e n t l o g g i n g {class 3) i n some higher l e v e l of the pyramid. T h i s phenomenon can a f f e c t to some extent the c l a s s i f i c a t i o n accuracy. To overcome t h i s d i f f i c u l t y a t e s t f o r homocfeneity. i s devised to be performed on each f o u r p i x e l c l u s t e r before the averaging operator i s a p p l i e d as one goes from one l e v e l t o the next higher l e v e l . For each band used, the v a l u e s of the d i s p e r s i o n f o r the f o u r p i x e l s are c a l c u l a t e d and t e s t e d a g a i n s t a t h r e s h o l d . I f the d i s p e r s i o n i s con s i d e r e d too l a r g e , i . e . , i f i t i s l a r g e r than the t h r e s h o l d f o r any of the three bands, the f e a t u r e v e c t o r of the r e s u l t i n g p i x e l at the s u c c e s s i v e higher l e v e l i s assumed to be zero, t h a t i s , the p i x e l i s u n c l a s s i f i a b l e a t t h a t l e v e l . In a l l subseguent t r a n s i t i o n s from one l e v e l to the next higher l e v e l any four p i x e l c l u s t e r c o n t a i n i n g a ze r o - v a l u e d p i x e l w i l l again y i e l d a zero-valued p i x e l . The t e s t i s purposely rough so to be i n e x p e n s i v e . I t s purpose i s to detect abrupt changes along the boundaries. When such changes are detected, holes are cr e a t e d t h a t get propagated upwards i n the pyramid. The t e s t a c t s as a b a r r i e r to the expanding wavefront of the boundary r e g i o n s . The c l a s s i f i c a t i o n of these areas i s delayed by the l a b e l l i n g a l g o r i t h m u n t i l , on the way down, a s a f e unambiguous l e v e l i s a g a i n reached. Optimal g l o b a l values f o r the d i s p e r s i o n t h r e s h o l d s are 51 a u t o m a t i c a l l y computed by the c l a s s i f i e r (see the next s e c t i o n ) . These values can a l s o be i n p u t i n t e r a c t i v e l y i n case one wants values t h a t more s p e c i f i c a l l y f i t a p a r t i c u l a r s i t u a t i o n . For example sometimes erroneous c l a s s i f i c a t i o n o ccurs more f r e q u e n t l y a t the s p a t i a l boundary between two s p e c i f i c c l a s s e s . In t h i s case one may want to look only a t the boundaries where the problem a r i s e s to determine l o c a l l y o p t i m a l v a l u e s f o r the t h r e s h o l d s . I n g e n e r a l more c o n s e r v a t i v e v a l u e s reduce the p r o b a b i l i t y of m i s c l a s s i f i c a t i o n but i n c r e a s e the number of u n c l a s s i f i a b l e p i x e l s a t the higher l e v e l s t h e r e f o r e i n c r e a s i n g the t o t a l number of c l a s s i f i c a t i o n s . The t e s t f o r homogeneity a l s o a c t s to s t a b i l i z e the s m a l l r e g i o n s i n the image. In f a c t the process o f the s m a l l areas becoming s m a l l e r and e v e n t u a l l y d i s a p p e a r i n g , i s d e t e c t e d as the t h r e s h o l d v e c t o r beeing exceeded by t h e d i f f e r e n c e between the f e a t u r e v e c t o r of the s m a l l homogeneous nucleus and the f e a t u r e v e c t o r of the surrounding environment. using t h i s t e chnigue i t i s p o s s i b l e t o experiment with l e v e l s higher than the t h i r d one i n the pyramid. The c l a s s i f i e r so f a r d e s c r i b e d , with the simple use of context i m p l i e d i n the pyramidal s t r u c t u r e , and with the help of the more e x p l i c i t but s t i l l very l o c a l c o n t e x t used i n the t e s t f o r homogeneity, g i v e s some improvement over the p o i n t by point c l a s s i f i e r both i n c l a s s i f i c a t i o n accuracy and i n r e a d a b i l i t y , i . e . , i t g i v e s a s m a l l e r f i n a l number o f r e g i o n s . T h i s 52 improvement i s obtained without any i n c r e a s e i n p r o c e s s i n g time because the overhead used f o r b u i l d i n g and m a i n t a i n i n g the pyramid i s balanced by the s m a l l e r number o f c a l l s to the maximum l i k e l i h o o d c l a s s i f i e r . As mentioned at the beginning of t h i s s e c t i o n the main g o a l sought with t h i s c l a s s i f i e r i s t o have a s t r u c t u r e t h a t allows the user to experiment i n making use of n o n - t r i v i a l semantics from the very beginning of the segmentation process. The way t h i s i d e a i s here pursued i s by i n t e r a c t i v e l y developing r e g i o n merging of i n c r e a s i n g complexity at every l e v e l i n the pyramid on the way down the pyramid i n the c l a s s i f i c a t i o n process., Again the p e c u l i a r c h a r a c t e r i s t i c s of the pyramidal s t r u c t u r e g i v e both the moti v a t i o n and the j u s t i f i c a t i o n f o r des i g n i n g some r e g i o n merging and s p l i t t i n g technigues. I n f a c t as already noted a p i x e l at any upper l e v e l r e p r e s e n t s a (square) r e g i o n i n the o r i g i n a l image. The hypothesis one can d e r i v e from t h i s o b s e r v a t i o n i s t h a t i t might not make too much sense t o f u r t h e r c o n s i d e r , i n a compressed p i c t u r e , l o c a l or g l o b a l p r o p e r t i e s of c l u s t e r s of p i x e l s to perform any kind of r e g i o n growing, but r a t h e r i n f o r m a t i o n on the l o c a l environment of s i n g l e p i x e l s c o u l d be used to r e f i n e the segmentation a t t h a t l e v e l . , The strong m o t i v a t i o n f o r doing t h i s i s , a g a i n , the e f f i c i e n c y / c o r r e c t n e s s / r e a d a b i l i t y t r a d e o f f . The f o l l o w i n g technique i s a p p l i e d . The immediate neighborhood of each p i x e l i n the image i s scanned. A p i x e l 53 already l a b e l l e d as strong t h a t does not have a high enough number of neighbors belonging t o i t s own c l a s s i s c o n s i d e r e d as p o s s i b l y a f f e c t e d by m i s c l a s s i f i c a t i o n and t h e r e f o r e i s sent to the next lower l e v e l t o be c l a s s i f i e d again (a s p l i t i s made). On the other hand, a p i x e l whose p.d.f. f o r any c l a s s i s not high enough t o l e t i t be c l a s s i f i e d as s t r o n g , but wich has a high number of s t r o n g neighbors a l l belonging to the same c l a s s , has i t s c l a s s i f i c a t i o n i n f l u e n c e d by t h e i r s and i s t h e r e f o r e merged i n t o t h a t c l a s s . , The procedure i s s e q u e n t i a l l y a p p l i e d t o the whole image at the given l e v e l s t a r t i n g from the upper l e f t hand corner and i s t h e r e f o r e order dependent. I t could p o s s i b l y be a p p l i e d more than once t o the same l e v e l , although t h i s has not been t r i e d . The number of s t r o n g neighbors necessary t o make an ambiguous p i x e l s t r o n g and the number necessary f o r a strong p i x e l t o remain s t r o n g are suggested by the l e v e l of the pyramid. Optimal v a l u e s f o r these numbers a r e e x p e r i m e n t a l l y determined f o r each l e v e l and are i n t e r a c t i v e l y i n p u t i n case the o p t i o n f o r doing r e g i o n merging i s chosen at t h a t l e v e l . The output from the c l a s s i f i e r can be e i t h e r taken as i t i s or i t can be f u r t h e r processed by higher l e v e l r e g i o n merging technigues. In the f i r s t case every remaining u n l a b e l l e d p i x e l a t the highest r e s o l u t i o n l e v e l i s assigned t o the c l a s s t h a t g i v e s the l a r g e s t value f o r the p.d.f.. In t h i s case another l o c a l region 54 merging clean-u£ procedure has been devised to read the f i n a l segmented image from the " s a l t and pepper" n o i s e t y p i c a l , f o r example, of the poin t by p o i n t c l a s s i f i e r s (see f o r example Kan [ 1 9 ] ) . T h i s i s the n o i s e i n t r o d u c e d i n the segmented image' by s m a l l and i s o l a t e d r e g i o n s . In the case of the pyramidal c l a s s i f i e r t h i s e f f e c t , which i s otherwise almost completely e l i m i n a t e d as a s i d e e f f e c t of the pyramidal s t r u c t u r e , i s p a r t l y r e i n t r o d u c e d by the a p p l i c a t i o n of the t e s t f o r homogeneity t h a t d e l a y s the c l a s s i f i c a t i o n of many p i x e l s u n t i l the lowest l e v e l . The procedure i s as f o l l o w s . Again the immediate neighborhood of every p i x e l i s examined., I f the number of neighbors i n the most fr e g u e n t c l a s s t h a t surrounds i t i s over a c e r t a i n t h r e s h o l d , the p i x e l i s merged i n t o t h i s c l a s s . T h i s simple procedure has proved e f f e c t i v e i n improving the r e a d a b i l i t y of the p i c t u r e without n e g a t i v e l y a f f e c t i n g but r a t h e r improving the o v e r a l l c o r r e c t n e s s of the c l a s s i f i c a t i o n {see next s e c t i o n ) . In case one wants t o f u r t h e r r e f i n e the i n t e r p r e t a t i o n of the p i c t u r e no change to the l a b e l l i n g procedure i s r e q u i r e d . The output i n t h i s case i s a p a r t i t i o n o f the p i c t u r e i n t o s t r o n g r e g i o n s , i . e . , the ones l a b e l l e d as one of the four c l a s s e s of i n t e r e s t , and ambiguous r e g i o n s , i . e . , those c o n s t i t u t e d by p i x e l s which do not give high enough p.d.f. values f o r any c l a s s . At the lowest l e v e l s of the pyramid. 55 r e g i o n merging technigues u s i n g more g l o b a l semantics can be a p p l i e d . Some experiments with an e x i s t i n g r e gion merging program are r e p o r t e d i n next chapter. 56 CHAPTER 4 Experiments with the Pxramidal S t r u c t u r e 4.1 R e s u l t s The pyramidal c l a s s i f i e r i s w r i t t e n i n ALGOL W and has been implemented on an IBM 370/168. The p o i n t by p o i n t maximum l i k e l i h o o d c l a s s i f i c a t i o n o f the whole area under study takes about 8 seconds of e x e c u t i o n time with 220 re g i o n s l e f t i n the f i n a l segmented image ( F i g . 4 . 1 ) . T h i s number has to be compared with the a c t u a l number of r e g i o n s i n the area of i n t e r e s t . In Fig.4.2 t h i s number, 36, i s shown as t r a c e d i n the d i g i t i z e d ground-truth map. The s t a b i l i t y o f the maximum l i k e l i h o o d c l a s s i f i e r has been v e r i f i e d with d i f f e r e n t s e t s of t r a i n i n g data randomly chosen by the program. The c o r r e c t n e s s of the point by point c l a s s i f i c a t i o n v a r i e s from 73 t o 75%; as expected, i t improves with an i n c r e a s e i n t h e s i z e of t r a i n i n g s e t . The experiments with the pyramidal s t r u c t u r e have to be compared with the f i g u r e s given i n Table 0. TABLE 0 c o r r e c t n e s s % No. o f r e g i o n s CPO-time (sees) p.by p. 74.80 220 7.90 Performance of the maximum l i k e l i h o o d c l a s s i f i e r 57 r The pyramid occupies b*w* 2^ bytes i n the computer's c-o s t o r e (where n b " i s the number of bands used, "w" i s the number of bytes o f main storage r e g u i r e d t o s t o r e one p i x e l , and 2 i s the s i d e o f the highest r e s o l u t i o n p i c t u r e i n p i x e l s ) , and i t takes about 2-3 seconds to be c r e a t e d , depending on the number of l e v e l s . At any l e v e l i n the pyramid the d e c i s i o n t o l a b e l a p i x e l as s t r o n g , or to send i t t o the next lower l e v e l to be c l a s s i f i e d i s made a c c o r d i n g with the r u l e : pmax>Ki*(p1*p2*p3*p4)/100, where pmax i s the maximum value f o r the p.d.f. f o r the four c l a s s e s and K i i s a t h r e s h o l d which i s ex p e r i m e n t a l l y chosen by the user a t l e v e l i . In g e n e r a l the values chosen f o r K are l a r g e r i n the upper l e v e l s o f the pyramid. In order to have a c l a s s i f i c a t i o n i n the f o u r c l a s s e s of i n t e r e s t the t h r e s h o l d a t the lowest l e v e l , K1, must be zero. The r e g i o n merging clean-up procedure alone takes from 3 to 5 seconds of exe c u t i o n time. The d e s i r a b i l i t y of paying t h i s c o s t i s a matter of how important r e a d a b i l i t y i s i n the f i n a l p i c t u r e . Tables w i l l be given i n c l u d i n g t h i s a d d i t i o n a l c o s t , t h a t show t h a t along with the improvement i n r e a d a b i l i t y there i s always a f u r t h e r improvement i n the o v e r a l l c o r r e c t n e s s . In what f o l l o w s C i s the t h r e s h o l d of the clean-up procedure, that i s , the minimum number of s i m i l a r neighbors a p i x e l must have to be merged with them. 58 LL] second growth Q o l d growth ; J2] r e c e n t l o g g i n g ffl w a t e r F i g u r e *K 1 P o i n t by p o i n t c l a s s i f i c a t i o n . 59 [TJ second growth o l d growth [/] r e c e n t l o g g i n g jig water F i g u r e i f . 2 The c l a s s e s o f i n t e r e s t t r a c e d i n the d i g i t i z e d ground t r u t h d a t a . 60 D i f f e r e n t s e t s o f experiments were performed. The f i r s t experiments were intended t o t e s t the performance of the c l a s s i f i e r using the s t r a i g h t pyramidal s t r u c t u r e . Up to fo u r l e v e l s are used. Table 1 shows some r e s u l t s using a l l the four l e v e l s . Table 2 gives the same f i g u r e s a f t e r the clean-up procedure. As i s c l e a r from these r e s u l t s , the more c o n s e r v a t i v e (lower) the values f o r the t h r e s h o l d s a r e , the worse i s the c o r r e c t n e s s of t h e c l a s s i f i c a t i o n , but l e s s time i s r e g u i r e d t o perform i t and fewer r e g i o n s remain i n the f i n a l segmentation. In the f i r s t experiment (case I) the c o r r e c t n e s s obtained i s about 3% l e s s the one o b t a i n e d with the p o i n t by point c l a s s i f i c a t i o n but the number of r e g i o n s i s h a l f of the number l e f t by the point by point c l a s s i f i e r . T h i s number becomes a g u a r t e r of the l a t t e r a f t e r the a p p l i c a t i o n of the clean-up procedure. TABLE 1 K4 K3 K2 c o r r e c t n e s s % No. of re g i o n s CPU-time I 90 90 90 72.20 121 9.95 I I 85 80 75 71.50 73 8.80 I I I 80 75 75 70.80 61 8.48 IV 0 0 0 64.00 8 7.70 Performance of the s t r a i g h t pyramidal s t r u c t u r e using f o u r l e v e l s with v a r y i n g K i , 61 TABLE 2 K4 K3 K2 c o r r e c t n e s s % No. of r e g i o n s Tot-time I 90 90 90 73. 50 60 14. 25 I I I 80 75 75 71.30 37 13. 88 Re s u l t s f o r cases I and I I I of Tab l e 1 a f t e r clean-up with C=2 The t h i r d of the cases shown, case I I I , i s perhaps the most i n t e r e s t i n g r e s u l t . In f a c t , even i f the c o r r e c t n e s s f u r t h e r drops, i t s t i l l remains a c c e p t a b l e , while the number of r e g i o n s i n the f i n a l output, 61, i s s i g n i f i c a n t l y low, and becomes the same as the number of r e g i o n s i n the a c t u a l p i c t u r e data a t the e x i t of the clean-up procedure ( F i g . 4. 3) . The c o r r e c t n e s s though drops to an unacceptable l e v e l i n the l a s t case (case I V ) . Remember t h a t i n t h i s case a l l the p i x e l s are c l a s s i f i e d only once, at the f o u r t h (top) l e v e l of the pyramid. In a l l cases of the Tab l e 1 the e x e c u t i o n time i s s l i g h t l y g r e a t e r then, or comparable with, the time taken by the point by point c l a s s i f i e r . As expected, t h i s time get s h o r t e r going down i n the t a b l e . , In f a c t , as p o i n t e d out elsewhere, the l a r g e r the values used f o r the t h r e s h o l d s , the fewer p i x e l s l a b e l l e d as strong at any l e v e l , that i s , more p i x e l s have to be c l a s s i f i e d at the next lower l e v e l . To g i v e an i d e a , the f o l l o w i n g t a b l e shows the t o t a l number of p i x e l s c l a s s i f i e d i n each of the previous cases. 62 TABLE 3 No. c l a s s i f i e d p o i n t by p o i n t 4 096 case I 2256 case I I 9 96 case I I I 872 case IV 64 T o t a l number of p i x e l s c l a s s i f i e d f o r the cases i n Table 1 compared with the p o i n t by point c l a s s i f i c a t i o n T able 4 shows some r e s u l t s obtained using three l e v e l s of the pyramid. Table 5 giv e s one f i g u r e a f t e r the clean-up. TABLE 4 K3 K2 c o r r e c t n e s s % No. of r e g i o n s CPO-time I 90 85 74.70 141 9.55 I I 85 80 74.20 122 9.15 I I I 80 75 74.00 99 8.85 IV 0 0 71 29 7.70 Performance of the s t r a i g h t pyramidal s t r u c t u r e using t h r e e l e v e l s with v a r y i n g K i . TABLE 5 K3 K2 c o r r e c t n e s s % No. of r e g i o n s Tot-time I 90 85 76.15 77 13.50 I I 85 80 75.50 6 8 13.45 Res u l t s f o r I and I I of Table 4 a f t e r the clean-up with C=2 63 The c o r r e c t n e s s of the c l a s s i f i c a t i o n improves s i g n i f i c a n t l y : as a matter of f a c t , as already p o i n t e d out ( c f . sec. 3), 3 l e v e l s are more a p p r o p r i a t e than 4 l e v e l s f o r the p a r t i c u l a r scene under study. T a b l e 4 i l l u s t r a t e s a l s o how t h i s improvement i s obtained at the expense of r e a d a b i l i t y . In f a c t , the lower the l e v e l the c l a s s i f i c a t i o n process s t a r t s a t , the more d i f f i c u l t i s to cover the n o i s e of the s m a l l c l u s t e r s of ambiguous p i x e l s . TABLE 6 K2 c o r r e c t n e s s % No. of r e g i o n s CPU-time I 80 75.40 149 8.80 I I 0 75.7 0 71 7.50 Performance of the s t r a i g h t pyramidal s t r u c t u r e using two l e v e l s with v a r y i n g K i TABLE 7 K2 c o r r e c t n e s s % No. of r e g i o n s Tot-time I 80 77.66 28 12.85 R e s u l t s f o r case I of Table 6 a f t e r the clean-up with C=4 Table 6 and Table 7 show some r e s u l t s u s i n g 2 l e v e l s of the pyramid. T h i s time even the s t r a i g h t c l a s s i f i c a t i o n a t l e v e l 2 64 (case II) g i v e s an improvement i n c l a s s i f i c a t i o n accuracy over the p o i n t by point c l a s s i f i e r . I t should be emphasized that i n the r e s u l t s h i t h e r t o presented, the exe c u t i o n time i s r e l a t i v e l y independent by the number of l e v e l s used. T h i s i s because the i n c r e a s e d number of p i x e l s t o be c l a s s i f i e d when u s i n g l e s s l e v e l s i s balanced by the s m a l l e r overhead r e q u i r e d by the b u i l d i n g of the pyramid. The next s e t of experiments were intended to t e s t the performance of the c l a s s i f i e r i n c l u d i n g the t e s t f o r homogeneity i n the c r e a t i o n of the pyramid. The program computes the three t h r e s h o l d s f o r band 5, 6, and 7 i n the f o l l o w i n g way. F i r s t , a l i s t of a l l the p a i r s of boundary p o i n t s i s obtained by t r a c i n g the r e g i o n s i n the d i g i t i z e d ground t r u t h map. The program then goes through t h i s l i s t and f o r every p a i r of boundary p o i n t s i t c a l c u l a t e s , f o r every band, the d i f f e r e n c e i n t h e i r r e f l e c t a n c e values. The average value of a l l the numbers so obtained i s computed f o r a l l the p a i r s of p o s s i b l e boundary c l a s s e s ( s i x i n t h i s case, i . e . , 1-2, 1-3, 1-4, 2-3, 2-4, and 3-4), and the average of these values i s again taken. ; The three numbers so obtained, one f o r each band, are the t h r e s h o l d s used i n the t e s t f o r homogeneity. Bemember t h a t the three v a l u e s o f the d i s p e r s i o n o f each four p i x e l c l u s t e r are t e s t e d a g a i n s t these numbers before c a r r y i n g out the averaging process up to the pyramid. I f the t e s t i s negative f o r t h a t c l u s t e r , t h a t i s , i f any of the values o f the d i s p e r s i o n i s g r e a t e r than the 65 corresponding t h r e s h o l d , the r e s u l t i n g p i x e l i s l a b e l l e d as u n c l a s s i f i a b l e at the next higher l e v e l . In t h i s case the computed values of the d i s p e r s i o n t h r e s h o l d s were about 10, 20, and 20. Using these values almost a l l the s m a l l r e g i o n s i n the scene are saved at the upper l e v e l s of the pyramid, without s i g n i f i c a n t l y i n c r e a s i n g the work of the maximum l i k e l i h o o d c l a s s i f i e r . ,. These r e s u l t s are r e l a t i v e l y i n s e n s i t i v e t o the p a r t i c u l a r values used f o r the t h r e s h o l d s . To g i v e an i d e a , t a b l e 8 g i v e s the l i s t o f the p i x e l s l a b e l l e d as u n c l a s s i f i a b l e at each l e v e l using the t e s t a t a l l l e v e l s . TABLE 8 L e v e l No. No. u n c l a s s . p i x e l s T o t . No. p i x e l s 5 15 16 4 35 64 3 53 256 2 45 1024 Number o f u n c l a s s i f i a b l e p i x e l s at each l e v e l u sing the computed values f o r the t h r e s h o l d s i n the t e s t f o r homogeneity., In the f o l l o w i n g , the t h r e s h o l d s used i n the t e s t f o r homogeneity w i l l be i n d i c a t e d by "Ta", "Tb", and " T c M . Table 9 shows some r e s u l t s using the above valu e s as t h r e s h o l d s i n the t e s t f o r homogeneity. Up to a maximum of four l e v e l s are used. T h i s i s because using the t e s t a t a l l l e v e l s , only one p i x e l 66 remains at the f i f t h l e v e l that i s not l a b e l l e d u n c l a s s i f i a b l e . TABLE 9 K4 K3 K2 c o r r e c t n e s s % No. o f r e g i o n s CP0-time I 0 0 0 70.00 40 8.30 I I 90 85 80 75.00 125 9.20 I I I - 85 80 75.80 9.20 IV - 80 76.20 153 9.00 V - 0 76.60 73 7.90 Performance homogeneity of the pyramidal s t r u c t u r e with Ta=10, Tb=20, Tc=20 using the t e s t f o r Table 10 gi v e s some f i g u r e s a f t e r the clean-up procedure. KU K3 K2 c o r r e c t n e s s % No. of regions I I 90 85 80 77. 10 71 I I I - 85 80 77.50 75 IV — 80 78.00 79 Resul t s f o r some of the cases of Table 9 a f t e r the clean-up with C=2 Case I and I I i n the pre v i o u s two t a b l e s are obtained u s i n g f o u r l e v e l s of the pyramid, case I I I using three l e v e l s , and cases IV 67 and V using two l e v e l s . These r e s u l t s have t o be compared with the analogous r e s u l t s given i n t h e p r e v i o u s t a b l e s . In g e n e r a l the t e s t improves the c l a s s i f i c a t i o n performance but, as a s i d e e f f e c t , i n t r o d u c e s some salt-and-pepper n o i s e i n the f i n a l segmented image. I n t h i s case, as Table 10 shows, the clean-up procedure becames p a r t i c u l a r l y e f f e c t i v e . The r e s u l t s g i v e n i n Table 11 show what happens i f the values f o r the t h r e s h o l d s i n the t e s t are chosen more c o n s e r v a t i v e l y , e.g., Ta=5, Tb=10, Tc=10. TABLE 11 K4 K3 K2 c o r r e c t n e s s % No. of r e g i o n s CPU-time I 0 0 0 75. 10 124 8. 40 I I - 0 0 75.50 - 9. 15 I I I — — 0 76.00 132 8. 55 Performance of the pyramidal s t r u c t u r e using the t e s t f o r homogeneity with Ta=5, Tb=10, Tc=10 T h i s time even the s t r a i g h t c l a s s i f i c a t i o n i n the fo u r main c l a s s e s at the f o u r t h l e v e l {case I) performs b e t t e r than the point by p o i n t c l a s s i f i e r . In g e n e r a l , a f u r t h e r improvement i n c l a s s i f i c a t i o n accuracy b r i n g s with i t i n c r e a s e d n o i s e ( l a r g e r number of regions) i n the f i n a l output. The p r i c e p a i d , as expressed by the i n c r e a s e d number o f c l a s s i f i c a t i o n s i s , again, not too high, as the e x e c u t i o n time shows and as Tab l e 12 68 i l l u s t r a t e s . TABLE 12 Le v e l No. No. un c l a s s . p i x e l s Tot. No. p i x e l s 5 15 16 4 58 3 157 256 2 274 1024 Number o f p i x e l s l a b e l l e d as u n c l a s s i f i a b l e at each l e v e l s u s i ng Ta=5, Tb=10, and Tc=10 a t a l l l e v e l s . As a r u l e , i f a good balance between c l a s s i f i c a t i o n accuracy and r e a d a b i l i t y i s sought, one should delay the a p p l i c a t i o n o f the t e s t as long as p o s s i b l e according to the s i z e of the s m a l l e r regions i n the scene under study (see chapter 3). In T a b l e 13 some examples are given. TABLE 13 K4 K3 K2 c o r r e c t n e s s % No. of reg. CPU-time No. c l a s s i f i e d I 90 80 0 75.10 51 8.28 605 I I 90 90 0 76.4 0 61 8.5 3 9 34 Results using f o u r l e v e l s o f the pyramid with d i f f e r e n t v a l u e s f o r the T i at each l e v e l . Both cases i n Table 13 use fo u r l e v e l s of the pyramid. Case I 69 has been o b t a i n e d u s i n g the t e s t with Ta~10, Tb=20, and Tc=20 a t the f i r s t and second l e v e l , and Ta=5, Tb= 10 , and Tc=10 at the t h i r d l e v e l . Case I I has been obtained u s i n g the t e s t with Ta=10, Tb=20, Tc=20 at the second l e v e l , and Ta=5, Tb=10 and Tc=10 at the t h i r d l e v e l . In the next s e t of experiments the performance of the l o c a l r e g i o n merging and s p l i t t i n g procedures d e s c r i b e d i n the previous chapter was t e s t e d at a l l l e v e l s i n t h e pyramid. Table 14 giv e s some r e s u l t s . In what f o l l o w s "Sa" i s the number of strong p i x e l s needed f o r an ambiguous p i x e l t o become s t r o n g , and "Ss" i s the number o f s t r o n g neighbours a s t r o n g p i x e l needs to remain strong (see chapter 3 ) . TABLE 14 c o r r e c t n e s s Ho. o f r e g i o n s CPO-time II I - 1 76.30 100 9.30 I I I - 2 78.60 60 14.40 IV 78.40 81 14.40 V 78.30 81 15.30 VI 78.10 89 14.57 Some r e s u l t s using r e g i o n merging and s p l i t t i n g technigues i n s i d e the pyramidal s t r u c t u r e . Case I I I - 1 and IXI-2 i n Tab l e 14 must be compared with case I I I i n Table 9, and case IV must be compared with case IV i n Table 70 9. Case VI cor responds t o two l e v e l s with Ta=5, Tb=1Q, Tc=10, and Sa=5, Ss=2, C=2, K2=80. Case V corresponds t o three l e v e l s with Ta=5, Tb=10, Tc=10, Sa=5, Ss=2 a t a l l l e v e l s , and C=2, K3=85, K2=80 ( F i g . ft. ft). Case I I I - 1 has been obtained as case I I I i n Table 9 without a p p l y i n g the clean-up procedures at the h i g h e s t r e s o l u t i o n l e v e l and s e t t i n g Sa=ft and Ss=0 at a l l l e v e l s . Remember th a t Sa i s ; the number of s i m i l a r s t r o n g neighbours necessary to make an ambiguous p i x e l s t r o n g , and Ss i s the number necessary f o r a stro n g p i x e l t o remain s t r o n g . In the case I I I - 1 of Table 1ft t h e r e f o r e , s i n c e Ss=0, th e r e are only ambiguous p i x e l s t h a t are merged i n str o n g r e g i o n s , the t o t a l number o f c l a s s i f i c a t i o n s , so to say the exe c u t i o n time, r e s u l t i n g reduced. This case shows t h a t , t o a c e r t a i n e x t e n t , the c o s t o f these procedures can be absorbed by the s m a l l e r number o f c l a s s i f i c a t i o n s r e g u i r e d , on the average, t o the maximum l i k e l i h o o d c l a s s i f i e r f o r the i n c r e a s e d number o f ambiguous p i x e l s t h a t become s t r o n g . Of course t h i s i s l e s s and l e s s t r u e { i . e . , the r e g i o n merging technigues become more expensive) as Sa and Ss become l a r g e r . The most n o t i c e a b l e c o n c l u s i o n t h a t can be i n f e r r e d from most of the above r e s u l t s i s t h a t some of the semantics used by these procedures i s alre a d y i m p l i e d i n the use of the pyramidal s t r u c t u r e . In f a c t , i n both c a s e s the values of the r e f l e c t a n c e on c l u s t e r s o f p i x e l s are used t o d r i v e the c l a s s i f i c a t i o n process, even i f t h i s i s done i n a d i f f e r e n t f a s h i o n . The 71 r e s u l t s obtained by experimenting with the r e g i o n merging procedures o u t s i d e o f the pyramidal s t r u c t u r e seem to support the previous c o n c l u s i o n s . T a b l e 15 shows some r e s u l t s obtained a p p l y i n g the r e g i o n merging and s p l i t t i n g t echniques t o the highest r e s o l u t i o n p i c t u r e {Fig. 4.5). TABLE 15 K1 Sa Ss C No.class. T o t . c l a s s . I 90 3 3 4 5296 4096 I I 90 5 2 4 62 22 4096 Performance of the r e g i o n merging c o r r e c t . % No.reg. CPU-time 79.10 - 19.80 79.40 31 20.60 and s p l i t t i n g technigues A good improvement i s o b t a i n e d i n both c o r r e c t n e s s and r e a d a b i l i t y at the expense o f e x e c u t i o n time. The f i n a l experiment with t h e pyramidal s t r u c t u r e was to use i t together with a higher l e v e l r e g i o n merger, t o see i f i t c o u l d s i g n i f i c a n t l y enhance the performance of the region merger. T h i s could be done i n two ways. E i t h e r by performing r e g i o n merging a t a l l l e v e l s i n the pyramid or g i v i n g the output from the pyramidal s t r u c t u r e as a i n p u t to the r e g i o n merging program. S t a r r ' s r e gion merger [ 7 ] was chosen and modified to work with the data s t r u c t u r e here d e s c r i b e d , however i n i t i a l experiments with the r e g i o n merger alone working on the h i g h e s t r e s o l u t i o n p i c t u r e produced r e s u l t s t h a t were not as good as 72 those of the pyramid alone. Thus the idea of using an e x i s t i n g r e g i o n merger was dropped. [~]second growth • old growth J2Jrecent logging water Figure 4.3 . Example of c l a s s i f i c a t i o n using four l e v e l s of the pyramid (case III of Table 2 . ?4 [~j second growth • o l d growth £/] r e c e n t l o g g i n g . [Xj w a t e r Figxire 4.4 Example of c l a s s i f i c a t i o n u s i n g the r e g i o n merging and s p l i t t i n g t e c h n i q u e s i n s i d e the p y r a m i d a l s t r u c t u r e ( c a s e V o f T a b l e 14 . 75 fjj second growth Q o l d growth 0 r e c e n t l o g g i n g fj) w a t e r F i g u r e 4*5 Example of c l a s s i f i c a t i o n u s i n g t h e r e g i o n m e r g i n g and s p l i t t i n g t e c h n i q u e s . 76 4.2 Conelusions The e f f i c i e n c y and f e a s i b i l i t y of a pyramidal s t r u c t u r e have been e x t e n s i v e l y t e s t e d on a t y p i c a l LANDSAT image. In e v a l u a t i n g the r e s u l t s presented i n t h i s chapter few main p o i n t s have to be taken i n c o n s i d e r a t i o n . Often the t a b l e s show s m a l l d i f f e r e n c e s i n e x e c u t i o n time, or, i n other words, i n the t o t a l number of p i x e l s c l a s s i f i e d . The scene under study was 64x64 p i x e l s i n s i z e , while a f u l l s i z e p i c t u r e i s at l e a s t 2048x2048 p i x e l s 1 . The d i f f e r e n c e s of few seconds of CPU time i n v o l v e d i n the experiments h e r e i n d e s c r i b e d may become s e v e r a l hours when one or more f u l l s i z e p i c t u r e s have to be c l a s s i f i e d . To have an idea of the order of magnitude i n v o l v e d , c o n s i d e r t h a t ...[Using the IMAGE 100} a s k i l l e d o p erator and a n a l y s t can c l a s s i f y a LANDSAT frame i n approximately 8 hours, as compared with approximately 30 hours on the LARSYS system which has higher o p e r a t i n g c o s t ...[45] (The IMAGE 100 i s the most powerful and e f f i c i e n t commercially a v a i l a b l e c l a s s i f i c a t i o n system which i n c o r p o r a t e s a hardwired p a r a l l e l e p i p e d c l a s s i f i e r t o permit the most r a p i d c l a s s i f i c a t i o n o f d i g i t a l image data, while LARSYS i s a very w e l l known c l a s s i f i c a t i o n system developed at Purdue U n i v e r s i t y ) . An important part o f the execution time of the whole A LANDSAT MSS image c o n t a i n s about 2*10® b i t s , each p i x e l being represented by 6 b i t s . 77 c l a s s i f i c a t i o n procedure i n the pyramid s t r u c t u r e c o n s i s t s on the time necessary t o b u i l d the pyramid (from two to three seconds i n the 64x64 p i x e l image). T h i s time c o u l d be s i g n i f i c a n t l y reduced by making use of s p e c i a l purpose p a r a l l e l hardware i n the pyramid r e p r e s e n t a t i o n . Computer systems connecting p a r a l l e l hardwired a r r a y s of processors to a s e r i a l computer system have been developed over the past few years, some o f these d e v i c e s being a l r e a d y a t the experimental and marketing stage. "A v a r i e t y o f c o n f i g u r a t i o n s of networks of [ l a r g e ] a r r a y s of p r o c e s s o r s are now p o s s i b l e - i f we knew what to do with them and how to program them" [ 3 1 ] (emphasis mine)., A software system which makes use o f l a r g e numbers of r e g u l a r i t e r a t i v e p a r a l l e l - s e r i a l o p e r a t i o n s , as i s the case o f the pyramidal c l a s s i f i e r , can take enormous advantages of a p a r a l l e l - s e r i a l hardware a r c h i t e c t u r e and open t o t a l l y new p e r s p e c t i v e s t o LANDSAT data c l a s s i f i c a t i o n . F i g u r e s given i n [ 3 1 ] , i f a p p l i e d to the pyramid c l a s s i f i e r , show t h a t p a r a l l e l a r r a y s of processors would speed-up the whole s t r u c t u r e by a f a c t o r e of LN (where L i s the number o f l e v e l s , and N i s the number of p i x e l s i n the h i g h e s t r e s o l u t i o n p i c t u r e ) , and the savings would apply not only t o the pyramid b u i l d i n g o p e r a t i o n (the averaging operation) but a l s o to the pyramid expanding o p e r a t i o n , to the r e g i o n merging and s p l i t t i n g o p e r a t i o n s , and so on. I t i s beyond the scope o f t h i s t h e s i s t o analyse deeply the above f i g u r e s . However, t h i s p o s s i b i l i t y must be explored 78 i n a f i e l d as the LANDSAT data computer a n a l y s i s f o r which "the prime d i f f i c u l t y i s the high c o s t " [ 4 5 ] , with regard to the main problem r a i s e d i n t h i s t h e s i s , the c o r r e c t n e s s / r e a d a b i l i t y / e f f i c i e n c y t r a d e o f f , attempts to balance these d i f f e r e n t f a c t o r s can be seen as attempts to balance d i f f e r e n t , o f t e n c o n t r a s t i n g , p o i n t s of view. From the A.I. p o i n t o f view, as l o n g as there i s enough memory to c o n t a i n a l l the i n f o r m a t i o n needed by the program, and as long as the execution time i s kept t o a reasonable l e v e l {less than 24 h o u r s , s a y ) , e f f i c i e n c y i s not the main concern. Rather the main concern i s the performance of the program i n the given domain. The A.I. r e s e a r c h e r seeks a procedure t h a t can c o r r e c t l y r e c o g n i z e the given scene and, h o p e f u l l y , be g e n e r a l enough t o be used on other scenes a l s o . From the Remote Sensing p o i n t of view, on the other hand, computational e f f i c i e n c y i s t h e f i r s t reguirement f o r a c l a s s i f i c a t i o n program t h a t w i l l probably be used i n a commercial r e a l - t i m e system. Many f u t u r e a p p l i c a t i o n s f o r s a t e l l i t e imagery f o r e s e e a world i n which t h i s t o o l w i l l be used as e x t e n s i v e l y as the t e l e s c o p e and r a d a r . The images have to be i n t e r p r e t e d i n l a r g e numbers at the same r a t e as they are being produced. E n t i r e s e s s i o n s of the Remote Sensing conferences are devoted to t h i s theme. At other times, f o r example when producing f o r e s t i n v e n t o r y maps, r e a d a b i l i t y becomes a prime f a c t o r , f o r the c l a s s i f i e d map 79 even i f c o r r e c t l y c l a s s i f i e d can be not too meaningful to the user. The computer c l a s s i f i c a t i o n maps produced from d i f f e r e n t r e sources i n v e n t o r i e s and a g r i c u l t u r a l a p p l i c a t i o n s o f t e n are obscured by the salt-and-pepper appearance: ...These maps are u n d e s i r a b l e to users who would l i k e t o c l e a n them up f o r more usable, smoother resource maps..., [19] The pyramidal c l a s s i f i e r here d e s c r i b e d can g u i c k l y c l a s s i f y a scene g i v i n g a c l e a n r e a d a b l e output with a c o r r e c t n e s s comparable t o or markedly b e t t e r than the c o r r e c t n e s s o f the p o i n t by poin t c l a s s i f i e r . But a l s o any of the p r e v i o u s l y d e s c r i b e d p o i n t s of view can be s t r e s s e d by simply changing some parameters i n the s t r u c t u r e . One might e i t h e r have a f a s t rough glance at the scene; one might e f f i c i e n t l y c l a s s i f y the image to meet commercial reguirements t o a g r e a t e r extent than a p o i n t by poin t c l a s s i f i e r does, or one might use the output from the pyramid as a f i r s t , f a s t stage of a more i n t e l l i g e n t i n t e r p r e t a t i o n system. 80 BIBLIOGRAPHY I. Rosenfeld, A., Feldman, J . , Kanal, L., Winston, P. A r t i f i c i a l I n t e l l i g e n c e and P a t t e r n R e c o g n i t i o n , F i f t h I n t e r n a t i o n a l J o i n t Conference on A r t i f i c i a l I n t e l l i g e n c e . M.I.T. Cambridge,Mass., August 1977 2- Remote Sensing Data Systems, Image A n a l y s i s System Handbook, MacDonald, D e t t w i l e r and A s s o c i a t e s L t d . , Canada 1977 3. Anderberg, M. a. C l u s t e r A n a l y s i s f o r A p p l i c a t i o n s * Hew York, Academic P r e s s , 1973 ~ 4. Simon, J. C. Recent Progress t o Formal Approach of P a t t e r n R e c o g n i t i o n and Scene A n a l y s i s , P a t t e r n R e c o q n i t i o n . Vol.7, September 1975 (pp. 117-124) 5. N i l s s o n , N. J . Learning Machines. McGraw-Hill Book Comp. 1965 6. Landgrebe, D. A. Remote Sensing Technology - a Look to the Future, Symposium on Machine P r o c e s s i n g of Remotely Sensed Data. Purdue U n i v e r s i t y , West L a f a y e t t e , Indiana 1976 7. S t a r r , D. W. Automatic I n t e r p r f t a t i o n of LANDSAT Images Hsinjg Context S e n s i t i v e Region MergJLng, B.Sc. T h e s i s , U n i v e r s i t y of B r i t i s h Columbia, B.C. 1976 8. Cooper, P. 8. S t a t i s t i c a l D e c i s i o n Theory, i n Automatic I n t e r p r e t a t i o n and C l a s s i f i c a t i o n -of Images, G r a s s e l l i ( e d i t o r ) , Academic Press 1969 9. Landgrebe, D. A. { p r i n c i p a l i n v e s t i g a t o r ) . NASA C o n t r a c t NAS9-1416, F i n a l Report , Laboratory f o r A p p l i c a t i o n s of Remote Sensing, Purdue U n i v e r s i t y , l e s t L a f a y e t t e , Indiana 1975 10. Hauska, H. and Swain, P. H., The D e c i s i o n Tree C l a s s i f i e r : Design and P o t e n t i a l , Symposium on Machine Pro c e s s i n g of Remotely Sensed Data. Purdue U n i v e r s i t y , Best L a f a y e t t e , Indiana 1975 I I . You, K. C. An Approach to the Design of a L i n e a r Binary Tree C l a s s i f i e r , Symposium on Machine P r o c e s s i n g of Remotely Sensed Data, Purdue U n i v e s r s i t y , i e s t L a f a y e t t e , Indiana 1976 12. Economy, R., Goodenough, D., Ryerson, R., Towles, S. C l a s s i f i c a t i o n Accuracy of the IMAGE 100, Second Canadian Symposium on Remote Sensing, Guelph, O n t a r i o 1974 ~ 81 13. Robertson, T. V. E x t r a c t i o n and C l a s s i f i c a t i o n of Objects i n M u l t i s p e c t r a l Images, Machine P r o c e s s i n g of Bemotely 5ensed Data, Conf., P r o c , Purdue U n i v e r s i t y , West L a f a y e t t e , Indiana 1973 14. K e t t i g , R. L. and Landgrebe, D. ft. C l a s s i f i c a t i o n of M u l t i s p e c t r a l Image Data by E x t r a c t i o n and C l a s s i f i c a t i o n of Homogeneous O b j e c t s , Symposium on Machine Processing o f Bemotely-Sensed Data, Purdue U n i v e r s i t y , West L a f a y e t t e , Indiana 1975 15. Wiersma, D A. and Landgrebe, D A. The Use of S p a t i a l C h a r a c t e r i s t i c s f o r the improvement of M u l t i s p e c t r a l C l a s s i f i c a t i o n o f Remotely Sensed Data, Symposium on Machine Proc e s s i n g o f Remotely Sensed Data, Purdue U n i v e r s i t y , West" L a f a y e t t e , Indiana 1976 16; Anuta, P. E. S p a t i a l R e g i s t r a t i o n of M u l t i s p e c t r a l and Multitemporal Imagery using Fast F o u r i e r Transform Technigues, IEEE T r a n s a c t i o n s on Geoscience E l e c t r o n i c s , V o l GE-8, No.4, Oct. 1970 17. H a r a l i c k , R. M., Shanmugam, K., and D i n s t e i n , I. T e x t u r a l Features f o r Image C l a s s i f i c a t i o n , IEEE Trans. on Systems, Man ana C y b e r n e t i c s , V o l . SMC-3, pp. 610-621, 1973 ~ 18. Goldberg, M., Goodenough, D., and S h l i e n , S. C l a s s i f i c a t i o n Methods and E r r o r E s t i m a t i o n f o r M u l t i s p e c t r a l Scanner Data, T h i r d Canadian Symposium on Remote Sensing. Edmonton, A l b e r t a 1975 19. Kan, E. P. A new Computer Approach to Map Mixed F o r e s t Features and Postprocess M u l t i s p e c t r a l Data, F a l l Convention of the American S o c i e t y of Photogrammetry -, S e a t t l e , Washington, Sept. 1976 20. Vanderbrug, G. , I. Lin e D e t e c t i o n i n S a t e l l i t e Imagery, Symposium on Machine P r o c e s s i n g of Remotely Sensed Data, Purdue U n i v e r s i t y , West L a f a y e t t e , Indiana 1975 21. Vanderbrug, G. J . Experiments i n I t e r a t i v e Enhancement of Li n e a r F e a t u r e s , Symposium on Machine P r o c e s s i n g o f Remotely Sensed Data, Purdue U n i v e r s i t y , l e s t L a f a y e t t e , Indiana 1976 22. Brayer, J . M. and Fu, K. S. A p p l i c a t i o n of a WEB Grammar Model t o an Earth Resources S a t e l l i t e P i c t u r e , The T h i r d I i i - J o i n t Conference on P a t t e r n R e c o g n i t i o n , Coronado, C a l i f o r n i a , Nov. 1976 23. Rosenfeld, A and Milgram, D. L. WEB Automata and Web Grammars, Machine I n t e l l i g e n c e 7, Edinburg, U n i v e r s i t y p r e s s . 82 1972 24. Fu, K. S. and L i , R. Y. Tree System Approach f o r Landsat Data I n t e r p r e t a t i o n , Sy_mj)osiuni on Machine P r o c e s s i n g of Remotely Sensed Data, Purdue U n i v e r s i t y , West L a f a y e t t e , Indiana 1976 25. Fu, K. S. and Bhargava, B, K. Tree Systems f o r S y n t a c t i c P a t t e r n R e c o g n i t i o n , IEEE T r a n s a c t i o n s on Computers. V o l . C-22, December 1973 26. Fu, K. S. P a t t e r n R e c o g n i t i o n i n Remote Sensing of the Earth's Resources, IEEE T r a n s a c t i o n s on Geoscience E l e c t r o n i c s , V o l . GE, No.1, January~1976~ 27. Bajcsy, R and Tavakoly, M. A Computer R e c o g n i t i o n of B r i d g e s , I s l a n d s , R i v e r s and Lakes from S a t e l l i t e P i c t u r e s , Machine P r o c e s s i n g of Remotely Sensed Data, Conf. P r o c , Purdue U n i v e r s i t y , West L a f a y e t t e , Indiana 1973 28. Bajcsy, R and Tavakoly, M. Computer R e c o g n i t i o n of Roads from S a t e l l i t e P i c t u r e s , Second I n t . J o i n t Conference on Pattern R e c o g n i t i o n , pp. 190-194, Aug.1974 29. K e l l y , M. D. Edge D e t e c t i o n i n P i c t u r e s by Computer using P l a n n i n g , Machine I n t e l l i g e n c e 6, pp.397-349, 1971 30. S h i r a i , Y. A. A Context S e n s i t i v e L i n e Finder f o r R e c o g n i t i o n of Polyhedra, A r t i f i c i a l I n t e l l i g e n c e 4, 2, pp.95-119, 1973 31. Uhr, L. " R e c o g n i t i o n Cones" and some t e s t r e s u l t s ; the imminent a r r i v a l of W e l l - S t r u c t u r e d P a r a l l e l - S e r i a l Computers; P o s i t i o n s and P o s i t i o n s on P o s i t i o n s , Advanced Papers f o r the Workshop on Computer V i s i o n Systems, Univ. of Massachussetts June 1977 32. Uhr, L. "Layered" R e c o g n i t i o n Cone Networks that Preprocess, C l a s s i f y and D e s c r i b e , IEEE Trans. Computers, 21 pp.758-768, 1972 33. K l i n g e r , A. and Dyer, C. R. Experiments on P i c t u r e R e p r e s e n t a t i o n s Using Regular Decomposition, Computer Graphics and Image Proc e s s i n g 5, No.1, pp. 68-105, Mar. 1976 34. Tanimoto, S. The Roles o f Regular H i e r a r c h i c a l Image and P r o c e s s i n g S t r u c t u r e s i n Machine V i s i o n , Proceed, o f the Workshop on Machine V i s i o n Systems, New York, Academic P r e s s , (to~appear) 1978 83 35., Tanimoto, S. L. and P a v l i d i s , T. A H i e r a c h i c a l Data S t r u c t u r e f o r P i c t u r e P r o c e s s i n g , Computer Gra p h i c s and Image Pr o c e s s i n g 4, No. 2, pp. 104-119, June 1975 36. l e v i n e , M. D. and Leemet, J . A method f o r Non-purposive P i c t u r e Segmentation, T h i r d I n t . J o i n t Conference on Pattern R e cognition, Coronado, C a l i f o r n i a Nov. 1976 37. Levi n e , M. D. A Knowledge-based Computer V i s i o n System, Myanced Papers f o r the Workshop on Computer V i s i o n Systems, Oniv. o f Massachussetts June 1977 38. Mackworth, A. K. On Reading Sketch Maps, F i f t h I n t . J o i n t Conference on A r t i f i c i a l I n t e l l i g e n c e . M.I.T., Cambridge, Mass., Aug., 1977 39. Mackworth, A. K. V i s i o n Research S t r a t e g y : Black Magic, Metaphors, Mechanisms, Miniworlds and Maps, Advanced Papers f o r the Workshop on Computer V i s i o n Systems, Univ. of Massachusetts June 1977 40. B r i c e , C. R., and Fennema, C. L. Scene A n a l y s i s using Regions, A r t i f i c i a l I n t e l l i g e n c e 1, pp.205-226, 1970 41. Yakimovsky, Y. Scene A n a l y s i s using a Semantic Base f o r Region Growing, S t a n f o r d A.I. Lab. Memo AIM-209, S t a n f o r d Univ., 1973 42. Tenenbaum, M. and Barrow, H. Experiments i n I n t e r p r e t a t i o n Guided Segmentation, P a t t e r n R e c o g n i t i o n and A r t i f i c i a l I n t e l l i g e n c e , Conf. Proceed., June 1976 43. S t a r r , D. and Mackworth, A. K. I n t e r p r e t a t i o n - d i r e c t e d Segmentation of ERTS Images, ACM/Pacific Regiona1 Symposium-( p r o c ) , 1976 44., Murtha, P. A. and Watson, E. K. Mapping o f F o r e s t C l e a r - c u t t i n g , South Vancouver I s l a n d , from LANDSAT Imagery, T h i r d Canadian Symposium on Remote Sensing, Edmonton, A l b e r t a 1975 45. Strome, W. M., Remote Sensing the Future, T h i r d Canadian Symposium on Remote Sensing, Edmonton, A l b e r t a 1975 T=0.77 DR=0 $3.74, $3.83T $SIG 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051788/manifest

Comment

Related Items