Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The automatic recognition of individual trees in aerial images of forests based on a synthetic tree crown… Pollock, Richard 1996

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

Item Metadata

Download

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

Full Text

T H E A U T O M A T I C R E C O G N I T I O N OF INDIVIDUAL T R E E S IN A E R I A L I M A G E S O F F O R E S T S B A S E D O N A S Y N T H E T I C T R E E C R O W N I M A G E M O D E L B y Richard James Pollock B . L . A . University of Toronto M . C.omp. Sci. Concordia University A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F D O C T O R O F P H I L O S O P H Y in T H E F A C U L T Y O F G R A D U A T E S T U D I E S C O M P U T E R S C I E N C E We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A June 1996 © Richard James Pollock, 1996 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of C-(?P\?tAT£P. *>UZNCE-The University of British Columbia Vancouver, Canada Date #fc J t M l E , WQb i I i DE-6 (2/88) Abstract T h e thesis of this work is that individual tree crowns can be automatically recognized in monoc-ular high spatial resolution optical images of scenes containing boreal or cool temperate forests in a leaved state. T h e thesis was advanced by developing and testing an automatic tree crown recognition procedure that is based on a model of the image formation process at the scale of an individual tree. This model provides a means of applying specific scene and image formation knowledge to the recognition task. T h e procedure associates instances of a three-dimensional shape description with locations in a scene image such that the descriptions estimate the visible scene extent of tree crowns that existed at the corresponding scene locations when the image was acquired. This provides an estimate of the average horizontal diameter of the vertical projection of individual recognized tree crowns, and a basis for species classification. This work makes a contribution to the overall effort to increase the level of automation in forest type mapping. Thi s work also introduces and demonstrates the use of a pre-defined image model to support the manual acquisition of a sample of unmodelled tree crown image properties, and the use of constraints related to the spatial relationships among multiple neighbouring candidate recognition instances to resolve image interpretation conflicts. T h e procedure was tested with a scene of mixed uneven-aged forests in which the trees represent a wide variety of species, size, and growing conditions. T h e results were assessed on the basis of ground reference data and compared to those produced by human interpreters. T h e scene represented a greater level of difficulty than that which has been addressed by previous attempts at automating the tree crown recognition task. T h e test results show that the procedure was able to largely accommodate the variation represented by the test scene, but that human interpreters were better able to accommodate irregularities in tree crown form and irradiance that were caused by tight vertical and horizontal spacing of the crowns. ii Table of Contents Abstract ii List of Tables v i i List of Figures ix Acknowledgement xi 1 Introduction 1 2 Background 5 2.1 Forest T y p e Mapping 5 2.2 A Framework for Automation in Forest T y p e Mapping 9 2.3 Factors that Motivate the Proposed Framework 10 2.3.1 Resolving Individual Tree Crowns in Aerial Images . . . 11 2.3.2 T h e Necessity of Individual Tree Crown Recognition 11 2.3.3 Comparison of S A R Sensing and Optical Sensing 12 2.3.4 T h e Advantage of Multispectral Optical Sensing 13 2.3.5 Laser Ranging for Tree Height and its Synergy with Individual Tree Crown Recognition 14 2.3.6 Advances in Georeferencing Images Acquired from Aircraft 15 3 T h e Recognition Task 17 3.1 Object Recognition 17 3.2 Goa l of Individual Tree Crown Recognition . 18 3.3 Token-based Individual Tree Crown Recognition 19 iii 3.4 Recognition with an Example-based Comprehensive Image Model 22 3.5 T h e Adopted Processing Strategy: Recognition based on a Synthetic Compre-hensive Image Model 25 4 Synthetic Tree C r o w n Image M o d e l 29 4.1 Geometric Aspects 31 4.1.1 Crown Envelope Shape . 31 4.1.2 Sensing Geometry 32 4.2 Radiometric Aspects 36 4.2.1 Scene Irradiance 36 4.2.2 Scene Irradiance and Tree Crown Interaction 38 4.2.3 Sensor Irradiance 44 4.3 Model Instantiation 47 4.4 Notation 50 4.5 Extent Similarity 52 4.6 Pattern Correlation 53 5 Procedures 54 5.1 Mode l Instance Organization and Generation 55 5.1.1 Evaluation of Inputs to Mode l Instance Set Generation 56 5.1.2 Comput ing an Approximately Min imal Dominating Set 61 5.2 Representation of Recognition Instances 61 5.3 Matching Image Locations and Mode l Instances 63 5.4 Evaluation of Correct Recognition Probability 70 5.4.1 Nearest-neighbours Interpolation 71 5.4.2 Feature Definitions 73 5.5 Resolution of Interpretation Conflicts , . . . 76 iv 5.5.1 Definition of a Processing Region State and the Associated Objective Function Value 80 5.5.2 Initial Optimization Experiments 82 5.5.3 Optimization by Similated Annealing 83 5.5.4 Summary 88 6 Experiment 91 6.1 D a t a 92 6.1.1 Image D a t a 93 6.1.2 Reference D a t a 96 6.2 Manual Recognition Experiment 97 6.3 Evaluation of Inputs to Model Instance Set Generation 98 6.3.1 Definition of Constraints on the Locally Variable Parameters 99 6.3.2 Pattern Correlation Sensitivity Tests 102 6.3.3 Evaluation of b{ and rji 109 6.3.4 Evaluation of paiff, SSE, and 5 5 M H O 6.3.5 Definition of Recognition Regions 112 6.3.6 Summary 115 6.4 Tuning the Initial Matching Procedure 117 6.5 Training Set and Feature Selection 119 6.6 Tuning the Conflict Resolution Procedure 123 6.7 Results 125 6.7.1 Recognition Results 126 6.7.2 Crown Diameter Estimation Results 144 6.7.3 Summary 151 7 Conclusion 154 7.1 Further Research 155 v Bibliography 158 A Sample Plot Display Triplets 163 B Index to T e r m and A c r o n y m Definition Page Numbers 170 vi List of Tables 6.1 Flight parameters 92 6.2 Flightline extrema coordinates and sun positions 92 6.3 M E I S II channel descriptions 93 6.4 Standard deviations of INS orientation angles 95 6.5 Crown envelope shape intervals 99 6.6 Crown envelope size and shape intervals 100 6.7 Test parameter values that are independent of horizontal radius 103 6.8 Test parameter values that are dependent on horizontal radius 103 6.9 Pattern correlation for high and low test parameter value instances of the per-meable volume model 105 6.10 Pattern correlation for high and low test parameter value instances of the opaque surface model 105 6.11 Summaries of the pattern correlation values for pairs of different permeable vol-ume model instances for different sets of tree crown property parameters 106 6.12 Summaries of the pattern correlation values for all pairs of different opaque surface model instances 107 6.13 Pattern correlation values for model instances generated with extreme values for (0s ,&) - 107 6.14 Correlation coefficients for pairs of permeable volume model and opaque surface model instances 108 6.15 Sequence of 6-values and associated ^-values . . . 109 6.16 Sample tree crown image correlation coefficients I l l 6.17 Extent similarity of model instances generated for different column offsets . . . . 114 vii 6.18 Ranges, means, and, standard deviations for interval-valued reference tree at-tributes 125 6.19 Proportions of sample tree sets with specified values for ordinal- and nominal-valued reference attributes 126 6.20 Running times for different components of the recognition procedure 128 6.21 Liberal enumeration of the omission and commission errors in the automatic recognition results . . . . 132 6.22 Conservative enumeration of the omission and commission errors in the auto-matic recognition results 133 6.23 Automatical ly recognized proportions of sample tree subsets associated with specified properties 142 6.24 Number of conservatively assessed automatic recognition commission errors as-sociated with each model instance horizontal radius parameter value 144 6.25 Full resolution horizontal crown diameter intervals 145 6.26 Half resolution horizontal crown diameter intervals 145 6.27 Error matrix for the full-resolution horizontal crown diameter classification based on manual crown image region delineation 147 6.28 Error matrix for the full-resolution automatic horizontal crown diameter classi-fication 148 6.29 Error matrix for the half-resolution horizontal crown diameter classification based on manual crown image region delineation 148 6.30 Error matrix for the half-resolution automatic horizontal crown diameter classi-fication 148 6.31 Error matrix assessments 149 6.32 Standardized variable values for differences of T a u coefficients 150 viii List of Figures 1.1 Tree crown recognition scenario 2 1.2 Subimages and individual tree crown recognition results for 1 hectare subscenes . 3 3.3 Processing strategy 27 4.4 Crown envelope examples 32 4.5 M E I S II subimages that show tree crown relief displacement 34 4.6 Vertical perspective projection and orthographic projection 34 4.7 Light-scattering element area density distribution examples 43 4.8 Volume array orientation 45 4.9 Tree crown image model instance and point feature locations 50 5.10 Procedure to generate a model instance set 57 5.11 Algorithm to compute a sequence of G E R horizontal radius values 59 5.12 Algori thm to find an approximately minimal dominating set of a graph 62 5.13 Procedure to match image locations and model instances (version 1) 65 5.14 Procedure to match image locations and model instances (version 2) 66 5.15 Procedure to match image locations and model instances (version 3) 68 5.16 Procedure to perform non-maximum suppression 69 5.17 Schematic examples of conflict resolution based on non-maximum suppression . . 78 5.18 Processing windows and margins for interpretation conflict resolution 79 5.19 Simulated annealing algorithm 85 5.20 Procedure to update the objective function data to reflect a recognition instance replacement. . 89 5.21 Alteration of a coverage count map during a recognition instance replacement . . 90 ix 6.22 Pixel value frequency histograms for the M E I S II image channels 94 6.23 Tree crown model instances generated with intermediate test parameter values . 109 6.24 Sample tree crown subimage display triplets 113 6.25 Test subimage mosaic and maps 118 6.26 Image regions from which the training set was selected 120 6.27 Initial recognition instances for a training set region . . 121 6.28 F ina l recognition instances corresponding to different objective function compo-nent weights 124 6.29 Channel 8 subimage and recognition results for 1 hectare subscenes that contain sample plots 3, 7, and 21 127 6.30 Schematic examples of relationships between actual and interpreted tree crown image regions 130 6.31 Plot boundary, reference, and results displays for sample plot 21 134 6.32 Plot boundary, reference, and results displays for sample plot 7 134 6.33 Sample plot 7 results computed with different overlap penalty weights 135 6.34 Plot boundary, reference, and results displays for sample plot 4 136 6.35 Recognized sample trees in sample plot 4 in the liberal assessment 137 6.36 Plot boundary, reference, and results displays for sample plot 12 138 6.37 Plot boundary, reference, and results displays for sample plot 22 139 6.38 Plot boundary, reference, and results displays for sample plot 1 141 A.39 Plot boundary, reference and results displays for sample plots 1 to 4 164 A.40 Plot boundary, reference and results displays for sample plots 5 to 8 165 A.41 Plot boundary, reference and results displays for sample plots 9 to 12 166 A.42 Plot boundary, reference and results displays for sample plots 13 to 16 167 A.43 Plot boundary, reference and results displays for sample plots 17 to 20 168 A.44 Plot boundary, reference and results displays for sample plots 21 to 24 169 x Acknowledgement I acknowledge the guidance provided by the members of my supervisory committee: Drs . D o n Leckie, J i m Little, Dav id Lowe, and Bob Woodham. Bob Woodham was my primary source of scholarly advice and encouragement. I consider myself extremely fortunate to have had B o b as my Research Supervisor. Don Leckie, Project Leader at the Petawawa National Forestry Institute ( P N F I ) , provided access to the M E I S II images, reference data, and associated docu-mentation that were used in this research. Don was a source of many valuable suggestions, and he shared with me his detailed knowledge of forest type mapping procedures and his ideas for their improvement. David Lowe provided an implementation of the V S M learning procedure and of the nearest neighbours interpolation procedure that I adapted to this research. J i m Li t -tle's contagious bouyancy helped me maintain the sense of self-confidence that is so necessary in research. I thank my University Examiners Drs . A l a n Mackworth and Peter M u r t h a , and External Examiner D r . John Miller of York University for their generous contribution of time and insight to my oral examination. I also thank my soon-to-be boss D r . Jan Mulder of the Alberta Research Counci l for his patient tolerance of several changes to my completion date. M a r c i a Wilson produced the line drawings for many of the figures. Steve Joyce and E d Cloney, both formerly at P N F I , answered questions about the experimental image and reference data. A r t Pope answered questions on the use of the Vista software, which I used extensively in my research (Art and David Lowe are the principal developers of Vista). T h e Laboratory for Computational Intelligence (LCI) is an immensely supportive place in which to work. L C I L a b Manager D a n Razzell does a magnificent job of keeping the compu-tational resources up and running smoothly. T h e work, ideas, tenacity, and advice of other students in the L C I , particularly Jeffrey Beis, Jiping L u , D a n McReynolds , Jane Mull igan, A r t Pope, and Michael Sahota were constantly inspiring. I give special thanks to L C I Secretary Valerie M c R a e for being a good friend. Financial support for this research was provided by the Natural Sciences and Engineering Research Counci l of Canada in the form of a postgraduate scholarship to the author and research grants to R. J . Woodham, and by the Institute for Robotics and Intelligent Systems, one of the Canadian Networks of Centres of Excellence. Ultimately, I could not have done this without the companionship, understanding, and love of my wife M a r c i a . xi Chapter 1 Introduction T h e thesis of this work is that individual tree crowns can be automatically recognized in high spatial resolution optical images of scenes containing boreal or cool temperate forests in a leaved state. T h e images are assumed to be monocular and vertical 1 , and acquired under clear sky conditions. We categorize electro-optical sensor images that are produced with a scene element 2 dimension no greater than one metre as having high spatial resolution (this is explained in Section 2.3.1). In the case of stratified forests, the scope of the thesis is limited to the crowns of emergent trees and dominant or codominant trees belonging to the upper continuous stratum. A secondary assertion included in the thesis is that constraining the recognition task on the basis of knowledge of the sensing system, the sensing situation, and the physical characteristics of trees can be the basis of an effective strategy. This work is intended to contribute to the increased automation of forest type mapping procedures. T h e thesis was advanced by developing and testing an automatic tree crown recognition procedure that is based on a model of the image formation process at the scale of an individual tree. T h e procedure associates instances of a three-dimensional shape description with locations in a scene image such that the descriptions estimate the visible scene extent of tree crowns that existed at the corresponding scene locations when the image was acquired (Figure 1.1). T h e procedure was tested on multispectral aerial digital images of scenes within the re-search forest of the Petawawa National Forestry Institute (PNFI) near Chalk River, Ontario, Acquired with a nominally vertical optical axis 2 region of flat and level terain spanned by the sensor instantaneous field of view 1 Chapter 1. Introduction 2 shape description — Figure 1.1: Tree crown recognition scenario. Canada . These scenes contain mixed forest and represent many different stand types, including mixed hardwood and softwood stands, and a wide range of individual tree size. T h e images were acquired with the second generation of the multi-detector electro-optical imaging scanner (MEIS II), a pushbroom scanner (McCol l , Neville, and T i l l 1983) and they have a 36 cm ground projected pixel dimension. Figure 1.2 displays some of the test image data, scene variation, and results that were produced by the recognition procedure. T h e test results were evaluated on the basis of reference data that were collected by P N F I personnel on the ground within the imaged scenes, and were compared to individual tree recog-nition results that were produced by human interpreters from the same image data. T h e remainder of this dissertation is organized as follows: Chapter 2 provides relevant background information on forest type mapping and describes and motivates a framework for automation in forest type mapping that incorporates the individual tree crown recognition task. „ shape description image projection recognized tree crown Figure 1.2: Subimages from the test image data and automatic individual tree crown recognition results for 1 hectare subscenes. The subimages were extracted from the visible green wavelength channel of the test image data. The image projection of the shape description boundary for each of the recognized crowns is superimposed in white on the subimages in the right column. The boundary of a 20-by-20 metre ground sample plot is superimposed in white on all of the subimages. Chapter 1. Introduction 4 Chapter 3 discusses the individual tree crown recognition task in detail, and motivates and describes a new automation strategy for achieving the goals of the task. Chapters 4 and 5 respectively describe a tree crown image model and procedures based on the model that implement the proposed automation strategy. Chapter 6 describes the experiment that was performed in order to test the proposed au-tomation strategy and presents an evaluation of the results. Chapter 7 summarizes the dissertation, discusses what the experimental results reveal about the validity of the thesis, and suggests further related research directions. Chapter 2 Background T h e work that is described in this dissertation is intended to contribute to the automation of forest type mapping procedures, particularly those that are carried out in Canada . These pro-cedures and the motivation for increased automation are outlined in Section 2.1. A framework for automation that incorporates the individual tree crown recognition task, which is the focus of this work, is described in Section 2.2, and technical factors that motivate and support this particular framework are described in Section 2.3. 2.1 Forest Type Mapping A forest type map stratifies an area of forested land in order to enhance the efficiency of ground sampling for forest inventory. A stratum is composed of forest stands of a particular type. Normally, the purpose of a forest inventory is to provide an estimate the spatial distribution of wood volume (Gillis and Leckie 1993; Gillis and Edwards 1988). Forest inventories have also been adapted to estimate the spatial distribution of wildlife habitats, and there is increasing pressure to make new inventories even more suited to this purpose (O'Brien and Chojnacky 1992; Schroer 1992). In Canada , forest type mapping normally requires the evaluation of species composition, density, tree height, tree age class, and site class attributes (Gillis and Leckie 1993). Regardless of the exact definition of these attributes and the classification systems associated with them, both of which vary among provinces, the manual interpretation of medium scale vertical aerial 5 Chapter 2. Background 6 photographs in stereo is the standard method of evaluating the first three (Ahern and Leckie 1987). Site class (an indication of the potential forest productivity of the site) and tree age class are estimated from the values of the other attributes, contextual information, and existing records. T h e photo-interpretation procedure produces a set of stand boundaries and, for each stand, a set of stand attribute values. A stand attribute value is the average of a sample of local values for that attribute within the stand. T h e local attribute values may pertain to individual trees (e.g., height) or to clusters of trees (e.g., species composition, density). Stand boundary delineation does not involve the explicit measurement of local attribute values, but instead relies on visual estimates of regions where attribute values appear relatively homogeneous and distinct from those of adjacent regions. Even when based on considerable experience, these estimates may vary significantly from one interpreter to another (Biging, Congalton, and M u r p h y 1991). Limits on the minimum allowable stand area (which may vary according to stand type) and continuity with earlier-defined boundaries for adjacent land areas are also observed (Brickell 1992). Local attributes are evaluated on a sample basis with the stand boundaries using simple tools such as a parallax bar (for measuring height), wedge or dot type crown diameter scales, crown closure example cards (for estimating the fraction of ground area that coincides with vertical tree crown projections) and reference stereograms (which provide examples of species identification, species composition estimation, and stand delineation) (Hershey and Befort 1995; Howard 1991). T h e local attributes are normally evaluated only for the emergent trees and the dominant and codominant trees of the upper continuous canopy stratum, since these are the trees that are visible in aerial images. These are also the trees that are most significant with respect to merchantable wood volume. Understory vegetation is significant with respect to wildlife habitat and stand development but is not generally visible in aerial images. Interpreters who are highly experienced, familiar with photographs of the given scale, and familiar with the type of forest that is pictured often estimate the values of the local attributes Chapter 2. Background 7 or even the stand attributes by eye (pers. comm. D r . Donald Leckie 1 ) . T h e photo-interpretation results are usually incorporated into a computerized geographic information system (GIS). T h e usual procedure for doing so consists of manually transcribing the stand boundaries onto a base map, manually digitizing the stand boundaries from the base map, and manually entering stand attribute values into a database management system that is a part of the GIS. Each of these steps is subject to quality control. Thi s procedure is typically even more expensive than the photo-interpretation (Leckie 1994). A n estimate of the amount of wood volume per unit land area in each stand can be de-rived from an estimate of stand tree density (numbers of stems per hectare) combined with observations that are related to individual tree wood volume. Counting trees on medium scale aerial photographs or high spatial resolution digital images is a tedious and slow manual task. Therefore, tree density is usually estimated by combining an estimate of crown closure with an estimate of average crown area within the same land region (Howard 1991, pp. 305, 306). O n a species-by-species basis, the average horizontal diameter or area of the vertical pro-jection of individual crowns onto a horizontal surface (referred to in the rest of this dissertation as crown diameter and crown area, respectively) can be a useful predictor of individual tree wood volume when combined with height and supported by ground plot sampling (Howard 1991, pp. 300, 301, 310, 311). Crown area or diameter may also be useful in estimating the amount of non-timber biomass, which is important in wildlife habitat inventories (Warbington and Levitan 1992), as well as in estimating fire hazard, site productivity, and industrially useful non-stem biomass (Schreuder, Gregoire, and Wood 1993). Accuracy standards for local attribute evaluation from aerial images are not well established or documented. Thi s reflects normal practice in Canadian forest type mapping, which is to directly assess the accuracy of the stand attribute evaluation (Gillis and Leckie 1993). This may involve aerial overflights or ground plot surveys within the stands. T h e placement of boundaries on the photos may also be checked for obvious inconsistencies. T h e photo-interpreter may elect, 1 Project Leader, Petawawa National Forestry Instiute, Forestry Canada Chapter 2. Background 8 or may be required, to perform a certain number of site visits during the interpretation process in order to calibrate the interpretation or resolve ambiguities. Precision standards for stand attributes values are readily available since they correspond to the associated class intervals. These class intervals are normally described in the legends of the completed forest type maps, and they dictate the coarsest allowable precision for the evaluation of local attributes. In Canadian forest type mapping, tree height classes are based on intervals ranging in width from 1 m (calibrated with field surveys) to 10 m, and crown coverage classes are based on in-tervals ranging in width from 10% to 30% (Gillis and Leckie 1993). Crown diameter and stem density do not appear in the legends of Provincial forest type maps, but may be involved in the wood volume density estimates that appear on some maps. In British Columbia , species compo-sition for young stands is based on the number of stems per hectare for different species. Howard states that, for North American forests, crown diameter manually evaluated from 1:8,000 to 1:20,000 scale photographs can often be reliably assigned to classes that represent 0.5 m to 1.5 m wide diameter intervals (Howard 1991, p. 299). There is a continual need for up-to-date forest type maps. Each year in Canada , approx-imately 27 million hectares of land are mapped in Provincial forest management inventory programs (Leckie 1993) in order to continually re-map a total of 344 million hectares on a 10 to 20 year cycle (Gillis and Leckie 1993). A t the same time, inventory managers are hav-ing difficulty finding competent photo-interpreters to replace the ones that are retiring (Leckie 1993). Evidently, few forestry programme graduates are attracted to forest type mapping work (pers. comm. D r . Peter M u r t h a 2 ) . This , together with the general attraction of cost reduction, motivates the development of automation in the forest type mapping process. 2 Professor, Faculty of Forestry, University of Britsh Columbia Chapter 2. Background 9 2.2 A Framework for Automation in Forest Type Mapping T h e work that is described in this dissertation is intended to contribute to the development of a system for automatically extracting information relevant to forest type mapping from digital optical images that are vertical, monoscopic, and have high spatial resolution. T h e envisaged image interpretation approach is based on the automatic recognition of indi-vidual tree crowns that are visible in the image data, which is the focus of the current work. T h e recognition results would include estimates of the image region, diameter, and scene location of individual crowns. Species classification would be based on features derived from individual crown image re-gions, but may also be constrained by general knowledge of the tree species expected in the scene and their commonly occurring associations. Knowledge of species site preferences might also be used in the species classification procedure should data on site conditions within the scene be available. Laser range data acquired concurrently with the image data would be registered to the image data and analyzed in combination with the recognition results in order to obtain a sample of individual tree height estimates (this is discussed further in Section 2.3.5). T h e most direct application of the information provided by the proposed image interpreta-tion approach would be the evaluation of attributes for predefined stand regions. This infor-mation would represent a denser sample of local attribute values than is typically obtained in the manual photo-interpretation process. A more advanced application would be the automatic definition of stand regions through the grouping of neighbouring trees such that the variance of the properties of individual trees and tree clusters would be within pre-defined limits within each stand region. T h e proposed image interpretation approach would produce basic information that could be stored as an intermediate product and adapted to a variety of forest type classification systems. This is an important issue because of the increasing demands on the versatility Chapter 2. Background 10 of forest management inventories. In contrast, mapping procedures based on manual photo-interpretation do not produce an application-independent intermediate product. 2.3 Factors that Motivate the Proposed Framework T h e following are technical factors that motivate the proposed framework for automation in the forest type mapping process (each factor is discussed in further detail in the indicated section): • Airborne electro-optical sensors can produce images in which individual tree crowns can be resolved (Section 2.3.1). • Individual crown recognition is required for general forest type mapping from optical images (Section 2.3.2). • D a t a from airborne or satellite-borne synthetic aperture radar (SAR) sensors are not a complete substitute for high spatial resolution optical image data in forest type mapping (Section 2.3.3). • W i t h respect to tree species identification, the high spectral resolution of image data from modern electro-optical sensors offsets their low spatial resolution relative to that of medium scale aerial photographs (Section 2.3.4). • Co-registered laser range data and monoscopic vertical aerial image data provide an ef-fective means of measuring tree heights that could be further automated through the automatic recognition of individual tree crowns in the image data (Section 2.3.5). • Inertial navigation system (INS) and global positioning system (GPS) technology has made it possible to georeference images acquired from aircraft, including line scanner images, on the basis of few if any ground control points (Section 2.3.6). Chapter 2. Background 11 2.3.1 Resolving Individual Tree Crowns in Aerial Images Leckie used a series of M E I S II images acquired in a visible red wavelength region and at dif-ferent altitudes over the P N F I research forest to illustrate the relationship between the ground projected pixel dimension ( G P P D ) and the ability to manually resolve individual tree crowns in the image (Leckie 1993). A t a G P P D of 0.75, 1.5, and 3.0 m most individual crowns are respec-tively clearly resolved, inconsistently resolved, and consistently not resolved (presumably the flight conditions were such that the scene elements were practically square). T h e corresponding scene element dimensions are 0.56, 1.12, and 2.25 m, because the M E I S II along-scanline scene element dimension is 75 % of the along-scanline G P P D due to resampling of the detector array output as part of a registration procedure that removes optical system distortions and prevents aliasing (McCol l , Neville, and T i l l 1983). This suggests that automated individual tree crown recognition may be possible in electro-optical sensor images of boreal and cool temperate forests with a scene element dimension no greater than approximately 1.0 m. For convenience, we cat-egorize such images as having high spatial resolution. Digital images with comparable spatial resolution may also be obtained by digitizing 1:10,000 to 1:20,000 scale (medium scale) aerial photographs or the analogue signal from a video camera. In contrast, image data acquired with a scene element that is large enough to encompass multiple trees (for example, image data from currently operating civilian satellite sensors) is categorized as having low spatial resolution in this dissertation. 2.3.2 The Necessity of Individual Tree Crown Recognition Experiments in the analysis of low spatial resolution optical image data strongly suggest that individual tree crown recognition is necessary for extracting information from optical sensor images at the level of detail required for compiling type maps of all but the simplest forests. A t low spatial resolutions, radiance from multiple trees and their surroundings contributes to a single pixel value. Therefore the information on tree species composition, size, and density that is required for forest type mapping is not directly accessible from low spatial resolution Chapter 2. Background 12 image data. T h e possibility of inverting models of scene element reflectance in order to extract information on the sub-element components contributing to the radiance has been a subject of considerable research. L i and Strahler had reasonable success in computing the average size and spacing of trees corresponding to individual pixels of simulated S P O T H R V image data (20 m G P P D ) (Li and Strahler 1985). T h e scene contained single storey stands of one or two conif-erous species on a uniform contrasting background (species composition was not computed), a conical crown form was assumed, and models of the density, height distribution, and radiomet-ric properties of the trees and the background provided computational constraints. However, it is not clear that techniques such as this can be extended to deriving species composition, tree density, and tree size information for scenes as complex as a typical cool temperate mixed or uneven-aged forest (Ahern and Leckie 1987; Leckie 1990a). 2.3.3 Comparison of SAR Sensing and Optical Sensing Airborne and satellite-borne S A R sensors are providing an increasingly available alternative to optical sensing, and the haze and cloud penetrating capability of S A R sensing is attractive in forestry applications. T h e recently deployed Canadian R A D A R S A T satellite carries a C -band H H polarized S A R sensor. However, experiments with image data from both airborne and satellite-borne S A R sensors indicate that R A D A R S A T data will not provide a significant improvement over satellite-borne optical sensors in detailed species composition mapping, and that the significant role in forestry of R A D A R S A T data will instead be in mapping logged or burned areas (Ahern, Leckie, and Werle 1993). T h e spatial resolution of S A R data is more constrained than that of electro-optical data since it depends on both the radar pulse bandwidth and the azimuth beam width (Fitch 1988). Operational airborne S A R sensors produce data with G P P D s on the order of several metres. In an experiment involving medium spatial resolution image data from airborne S A R and electro-optical sensors, Leckie found that the S A R data were better for distinguishing different softwood species stands than the electro-optical data, but that the electro-optical data was better for Chapter 2. Background 13 distinguishing hardwood and softwood stands, and open and forested areas (Leckie 1990b). T h e S A R data were acquired in different combinations of sending and receiving polarization in both the X and C bands with G P P D s of 3 .0m (range) and 4 .0m (azimuth). T h e electro-optical data were acquired in visible and near-infrared bands with a G P P D of 4 .1m, and both data sets were resampled to the same 10 m grid before analysis. These results indicate that although airborne S A R image data can be a useful complement to medium spatial resolution electro-optical image data in forestry applications, it cannot replace medium or high spatial resolution electro-optical image data. T h e degree to which airborne S A R image data can complement high spatial resolution electro-optical image data in tree species discrimination is still unknown. 2.3.4 The Advantage of Multispectral Optical Sensing High spatial resolution images from operational electro-optical sensors generally have a sig-nificantly coarser spatial resolution, with respect to manual forest cover interpretation, than do aerial photographs at a scale of 1:15,000 or larger (Leckie 1990a). This means that crown margin shape and crown texture are less useful as features for species classification when in-terpreting the digital images than when interpreting photographs. However, in experiments reported in Leckie (1993) manual tree species identification from colour composite displays of multi-channel high spatial resolution M E I S II image data was more accurate than manual species identification from 1:9,000 scale colour infrared photographs of the same scene. T h e higher spectral resolution of the digital images relative to that of the photographs appeared to more than compensate for their lower spatial resolution. Experiments in the automatic supervised classification of various tree species that are based on multi-channel pixel values from manually delineated tree crown regions in high spatial resolu-tion digital images have produced results in which 50 % to 90 % of the test trees were correctly classified, depending on species (Gougeon 1995; Gougeon 1993; Hughes, Evans, and Burns 1986; Thomasson, Bennet, Jackson, and Mailander 1994). This accuracy range may overlap those obtained through operational manual photo-interpretation procedures: in an experiment Chapter 2. Background 14 involving experienced photo-interpreters and 1:12,000 scale aerial photographs, between 68% and 88 % of a sample of coniferous stands in Northern California were correctly classified for species (Biging, Congalton, and M u r p h y 1991). T h e automatic classification experiments did not involve texture or shape features, but image values were selected from portions of tree crown image regions that were estimated to correspond to directly irradiated crown surfaces. 2.3.5 Laser Ranging for Tree Height and its Synergy with Individual Tree Crown Recognition Tree height can only rarely be directly evaluated from monoscopic optical images. Furthermore, it is doubtful that tree height can be reliably evaluated automatically from stereo high spatial resolution images. Monoscopic tree height estimation requires measurement of the length of the shadows cast on level open ground by the trees. Such shadows exist only in very open stands or at the edge of clearings. Stereo tree height estimation requires the discrimination of both the base and apex of the tree, and usually very few trees in the scene have a base that is visible in an aerial image. Airborne laser profiling and "light detecting and ranging" ( L I D A R ) systems provide an al-ternative means of estimating individual tree height or average stand height to a useful degree of accuracy. These systems generate vertical range data along a narrow ground trace by measuring the time of travel of reflected laser pulses. A laser profiling system records the distance to parts of tree crowns, and to the ground where there are gaps in the canopy. In order to transform the profile data into tree height data, the samples that correspond to ground reflections must be recognized and a ground profile must be derived from them. This may be difficult to do where the forest canopy is dense and the topography is varied. A L I D A R system records the amplitude of each received pulse as a function of time. T h e part of an amplitude record that corresponds to tree crown reflections can usually be distinguished from the part that corresponds to the ground reflection. A system implemented by Aldred and Bonner was able to automatically measure average stand height to ± 4 . 1 m at a 95 % confidence Chapter 2. Background 15 level or, equivalently, with a 2.1 m root-mean-square (rms) error, from L I D A R data acquired at a height of approximately 400 m above ground-level (Aldred and Bonner 1985) (this height was chosen for compatibility with the limit of another instrument and does not represent an upper operational height limit for the L I D A R instrument). Thi s result was considered to be at least as good as the results obtained from parallax difference measurements made with medium scale aerial photographs. Scanning L I D A R systems can be used to acquire range data samples over two dimensions, but the accuracy with which tree height can be estimated using the off-nadir samples has not been determined. T h e range data that closely correspond to the centres of the vertical projections of tree crowns must be identified in order to obtain a sample of individual tree heights (Jacobs, Evans, and Ritchie 1993). In some sensing systems, it is possible to synchronize the acquisition of range data and image data, and to automatically determine the image coordinates of the range data samples. Co-registered range data and high spatial resolution digital image data in which individual trees have been recognized would be complementary in that the localization results could be used to determine which range samples are useful for tree height estimation. 2.3.6 Advances in Georeferencing Images Acquired from Aircraft Image interpretation results must be referenced to a standard geographic coordinate system (georeferenced) in order for them to be useful in any type of mapping application. This means that the image coordinate frame must be georeferenced. Geometric distortion in the images that is caused by platform instability greatly complicates this task. High spatial resolution optical image data for civilian use are currently only acquired from aircraft, and the various types of line scanner sensors provide the best spectral resolution. Because undesired aircraft motion can occur between each scan when acquiring line scanner images, the geometric distortions that occur in such images are more complex than those that occur in film and digital frame camera images. However, good progress is being made in the development of techniques for georeferencing line scanner images from aircraft on the basis of few if any ground control points Chapter 2. Background 16 ( G C P s ) . Gibson achieved rms errors of sub-pixel and single-pixel sizes, respectively, for horizontal and vertical positions when correcting and georeferencing M E I S II images with a 0.5 m G P P D (Gibson 1994). Thi s experiment involved a fore-, aft-, and nadir-view image acquired for each of five approximately parallel flightlines, and three additional flightlines oriented approximately orthogonal to the first five. A n INS mounted on the sensor was used to track sensor velocity, orientation, and (relatively inaccurately) position. A total of five G C P s and 3375 conjugate points were manually located in the images (Gibson states that this number of conjugate points is unnecessarily high). T h e correction and georeferencing was performed with a least-squares bundle adjustment. ' Cosandier and his colleagues achieved average rms errors of single pixel size for horizon-tal positions in correcting and georeferencing 7.5 m G P P D images acquired with the compact airborne spectrographic imager (CASI) (Cosandier, Ivanco, and M a h 1992). No G C P s or con-jugate points were used. A vertical gyroscope integrated with the C A S I provided roll and pitch data and a pair of G P S receivers (one in the aircraft and one at a ground station) provided position and heading data. Chapter 3 The Recognition Task Section 3.1 defines precisely what is meant by the term "object recognition" in this dissertation. This definition provides a basis for the statement of the overall goal of the individual tree crown recognition task, which is given in Section 3.2. Strategies that have been developed for achieving related goals are discussed in Sections 3.3 and 3.4. T h e alternative strategy for achieving the stated goal that was adopted in this work is described and motivated in Section 3.5. 3 . 1 Object Recognition We consider the process of object recognition from a monoscopic optical image to have two components: detection and localization. Detection is the process of deciding whether or not a particular region of the image depicts the existence of a particular object (or instance of a particular type of object) in the scene at the time that the image was acquired. Localization can be further divided into image-space and scene-space components. Image-space localization is the process of defining the set of two-dimensional image-space coordinates to which the visible spatial extent of the detected object, or specified visible parts of the detected object, was projected. Scene-space localization is the process of defining the set of three-dimensional scene-space coordinates that coincided with the detected object, or specified parts of the detected object, at the time that the image was acquired. 17 Chapter 3. The Recognition Task 18 Image-space localization has two broad purposes: to support further analysis and inter-pretation of the image, and to support scene-space localization. T h e extraction of further information about the type, three-dimensional shape, or condition of the object, and the recog-nition of further objects that are composed of the already recognized objects are examples of image analysis or interpretation tasks that may be supported by image-space localization. Scene-space localization can be formulated as two tasks: determine the coordinates of the points-of-interest on or within the object with respect to an object-centred coordinate frame, and determine the position and orientation of the object-centred coordinate frame with re-spect to the scene coordinate frame. T h e image-space localization results are necessary but not sufficient to perform these tasks because the back-projection of an arbitrary point in the image-space into the scene-space is not unique. T h e further constraints that are required to perform these tasks can sometimes be derived from some combination of external measurement, (e.g., measurement of the position and orientation of the sensor within the scene with a radar altimeter and an inertial navigation system), image analysis (e.g., estimating surface shape from shading patterns in the image), and reference to a pre-defined geometric model of the detected object (which may have been used in the detection process). T h e techniques that are applied will depend on the assumptions that can be made about the scene and the image formation process, the external measurements that can be made, and the required precision and accuracy of the localization results. 3.2 Goal of Individual Tree Crown Recognition A procedure that performs individual tree crown recognition from monoscopic optical images and that fits within the framework described in Section 2.2 must perform image-space lo-calization that supports further processing for species identification, and perform scene-space localization that provides an estimate of the crown diameter of the detected trees. Limitations on the applicability of the procedure with respect to terrain properties, forest stand properties (including tree size and density), and the location of tree crown images within the overall image Chapter 3. The Recognition Task 19 extent should be minimized. A s discussed in Section 2.1 there are no established accuracy standards for individual tree crown detection or diameter estimation that can be used to measure the success of an automated procedure. Human performance is a meaningful alternative standard since manual evaluation of local attribute values is the current basis for stand attribute evaluation (see Section 2.1). 3 . 3 Token-based Individual Tree Crown Recognition Procedures to automatically recognize individual tree crowns in aerial images on the basis of the detection of image tokens that were manually observed to be associated with, or incorporated within, examples of tree crown images have been implemented by Gougeon (Gougeon 1995; Gougeon 1994) and Pinz (Pinz 1991). These two procedures emphasize image-space localization for the purpose of counting tree crowns and for providing a basis for species identification; crown diameter estimation is not explicitly addressed. They involve different image tokens, but they have common limitations: both procedures rely on the general assumption of a high level of image contrast between a tree crown image and the immediately surrounding region, which implies certain scene irradiance and tree crowding conditions. They are also limited in the range of tree size that can be accommodated. These limitations will be discussed in greater detail after the procedures and the results that have been produced by them are outlined. Pinz's procedure is based on the assumptions that the tree crown image regions have near-circular boundaries and that they generally have higher pixel values than the surrounding image regions. T h e procedure smooths the image with a lowpass filter of a size that is related to the expected size range of the tree crown image regions, and locates local maxima in the smoothed image. Each local maximum is considered to be the centre of a tree crown image region. T h e average of the smoothed image pixel values in concentric circles of increasing radius (starting and ending at user-specified radii) centred at each local maxima is computed. For a given local maximum, the first circle whose average is a user-specified fraction of the smoothed image value at the local maximum is selected as the boundary of the crown image region. T h e image tokens Chapter 3. The Recognition Task 20 in this procedure are local maxima, and circular image trajectories across which the average image pixel value gradient is high. Pinz's procedure was tested on portions of large and medium scale aerial photographs that were digitized to have G P P D s of 0.40 m and 0.80 m. T h e scenes portrayed in the test subimages contained well-spaced coniferous trees. T h e shadows that were cast by the trees when the images were acquired were long enough to cause the between-crown image regions to be much darker than the images of the directly irradiated portions of the crown images. Also, the subimages exhibit no noticeable height displacement so the tree crown image regions have a generally near-circular shape. Some results are illustrated in (Pinz 1991), but their accuracy is not assessed. M a n y tree crown image regions of widely varying sizes appear to be correctly delineated. However, the results also contain many cases where the same image region is interpreted both as a single large crown and as multiple small crowns. Gougeon's procedure is based on the assumption that image regions corresponding to in-dividual tree crowns are separated by narrow interstices of relatively low image pixel values. T h e procedure smooths the image with a 3-by-3 averaging filter, finds local minima within a 3-by-3 neighbourhood, joins minima that occupy the same 5-by-5 neighbourhood, and applies a hierarchically organized system of heuristically defined procedures to join sets of linked minima into possible crown outlines. T h e image tokens in this procedure are sequences of local minima that define closed boundaries of image regions. T h e permissible spatial relationships between adjacent minima in a boundary sequence were derived from inspection of example crown images and were manually encoded into the procedure. Gougeon's procedure was tested on a near infrared wavelength channel of a M E I S II subim-age of a scene that contained several tree plantation compartments. T h e subimage has a G P P D of 0.31 m and individual tree images do not exhibit noticeable height displacement. T h e solar zenith angle at the time of image acquisition was 6 7 ° . A subset of the compartments contained well-spaced trees with crown diameters that varied over a small range. T h e spacing of the trees combined with the high solar zenith angle caused the image regions between the images of Chapter 3. The Recognition Task 21 the directly irradiated portions of the tree crowns to be dark and well-defined. T h e procedure localized 84% of all the images of actual tree crowns in these compartments, and the number of delineated crown images was slightly closer to the actual number of trees than a manual tree count that was performed with the same image data. Most of the errors occurred where tree crowns were unusually close to each other and the divisions between crown images were relatively indistinct. In such cases, the images of multiple (usually two) crowns were recognized as a single crown image. One compartment in the scene contained a row of trees that had grown such that in the image most of them appear to be in physical contact with an adjacent tree. T h e procedure localized 35% of all the images of actual tree crowns in this compartment. Images of relatively large tree crowns in another compartment were separated into multiple regions. These tree crown images were correctly delineated when the procedure was run on the image data that had been resampled to a 0.70 m G P P D . T h e demonstrated scope and effectiveness of the procedures described above point out the following sources of difficulty in the individual tree crown recognition task: • T h e boundary of the image of an individual tree crown may be weakly defined, or even only implicit, for much of its length. This may be the case when the tree crown is in physical contact with other crowns, or is viewed against a background with which it has a low degree of image contrast. Such a background may consist of understory trees or shrubs, or even other trees of the same canopy layer in parts of the image where there is a large amount of height displacement. Wide crown spacing combined with short crown shadows may prevent the understory or ground from appearing much darker than tree crowns in vertical images. Acquisition of image data when the solar zenith angle is large can result in dark between-crown image regions. However, a large solar zenith angle may cause tree crowns to cast shadows on each other in places where trees are crowded, and this would add variation the appearance of the tree crown images. • T h e size of visible tree crowns can vary widely over a small area of land in uneven-aged and mixed stands. A recognition procedure that is effective only when the size of a crown Chapter 3. The Recognition Task 22 image is within certain fixed limits must be applied to resampled versions of the image in order to accommodate relatively large crown image size variation (e.g., Gougeon's procedure). Alternatively, the procedure can be designed to search a single version of the image for crown images of size that varies continuously within a wide range (e.g., Pinz's procedure). In either case, conflicting interpretations of the same image region (i.e., one large crown image versus multiple small crown images) may arise. 3.4 Recognition with an Example-based Comprehensive Image Model A n alternative to the token-based approach to object recognition is based on searching for a match between image regions and a model of the full spatial extent of the object image (a comprehensive image model). This approach may be effective when there are no reliable tokens for the object images. However, tokens provide a model of an object image that is relatively selective and therefore may also be less sensitive to unimportant object image variation. Traditional template matching (Pratt 1991, § 20.1) is a simple version of recognition with a comprehensive image model. A measure of the strength of the match between a reference image array, or template, and the input image array is computed at different relative offsets of the two arrays. Image-space object location is derived from the relative offset, and the object is considered to be detected at an input image location where the match-strength is locally maximum and above a specified threshold. T h e n coincident pixel values of the two arrays at a given relative offset may be treated as corresponding elements of two n-dimensional coordinate vectors, and the match-strength defined such that it is inversely-related to the value of a between-point distance measure (e.g., Euclidean distance). Components of a comprehensive image model may be based on representative examples of object images (example-based), or on knowledge of the physical properties of the object of interest, the sensing system, and the sensing situation (synthesized). T h e example-based Chapter 3. The Recognition Task 23 approach to defining a comprehensive image model is attractive because its implementation is potentially much simpler than the implementation of the synthetic approach: the need for a detailed understanding of the process through which the objects of interest in the three-dimensional world become two-dimensional images, and for the parameters of this process, is avoided. In a particular task domain, the size of an adequately representative set of examples would be directly related to the degree of variation in the spatial extent of the object images (which is related to variations in the shape, size, and orientation of the object in scene-space and to variations in local imaging geometry) as well as to the degree of pattern variation within the object image extent (e.g., two tree crown images may occupy almost the same spatial extent within two uniformly-dimensioned image arrays, but may represent considerable pattern variation because the imaged tree crowns may vary in three-dimensional shape and foliage density). If this variation is naturally large and little control can be imposed on it then the manual effort that is required to collect a representative set of examples may be impractical. Turk and Pentland's work in detecting human faces in monochromatic images (Turk and Pentland 1991) provides an example of the purely example-based approach to the definition of a comprehensive image model that illustrates the points raised above. A sample of m face images was acquired in which each image array has the same row and column dimensions and each face image occupies approximately the same region within its array. T h e concatenated rows of each image array were considered as the coordinate vector for a single point in an n-dimensional space. Principal components analysis was used to compute the orthonormal unit vectors in the n-dimensional space that coincide with the first m — 1 principal axes of the set of m sample points. Turk and Pentland called these vectors eigenfaces. T h e eigenfaces associated with the principal axes along which most of the sample point variance occurs were retained as a compact representation of the m face images. These eigenfaces represent considerable variation in full-frontal face images that all occupy approximately the same region within the image arrays and are all superimposed on a relatively featureless background. A n image submitted for interpretation was 'centred' by subtracting the mean of the m sample images from it, and Chapter 3. The Recognition Task 24 a face was considered to be detected if the squared Euclidean distance between the centered image (as a vector) and its projection onto the space spanned by the eigenfaces was smaller than a specified threshold. In a preprocessing step, the m sample images were partitioned into subsets each of which contained images of the same individual with varying facial expression and obtained under different lighting conditions. T h e components of the projection of the centred version of each of the sample images onto the space spanned by the eigenfaces (i.e., its principal components) were computed and stored in a vector. T h e average principal component vector for each sample image subset was then computed. A submitted image that was interpreted as a face was further indentifed as portraying a particular individual by computing the Euclidean distance between the principal component vector of the submitted image and the average principal component vector for each sample image subset. T h e assigned identity was associated with the smallest distance. Turk and Pentland's eigenface technique is attractive in a 'mug-shot' face-detection task domain because the object image spatial extent variation is controlled and the technique auto-matically derives a representation of most of the pattern variation within an object image sample that is much more compact than the sample itself. A n adaptation of this technique to individ-ual tree crown recognition in the case of limited crown variation is described in M u r g u (1996). In the more general individual tree crown recognition task domain involving uneven-aged or mixed-species forest stands, the spatial extent variation is relatively uncontrolled. A rectan-gular image window of certain dimensions may closely approximate the spatial extent of some individual tree crown images within the overall image array, but in other locations it may en-compass the images of multiple relatively small tree crowns or only part of the image of a single relatively large tree crown. Also, height displacement variation may cause the spatial extent of images of uniformly sized and shaped tree crowns to vary in some high spatial resolution aerial images. This means that multiple instances of a eigenface-type image model would be required in this task domain, and a representative tree crown image sample would have to be Chapter 3. The Recognition Task 25 manually collected for each of the different window sizes. T h e precision of the image-space localization of tree crown images would be limited to that which is provided by a bounding rectangle. Experiments in the species classification of tree crown image regions have involved a greater image space localization precision than this (cf. Section 2.3.4), and some have even found that classification is significantly improved when it is based on pixel values from only the directly irradiated portion of the crown surface. A modification of the eigenface technique to allow non-rectangular windows is possible, but a large amount of manual effort would be required to estimate the boundary position of each sample tree crown image. 3.5 The Adopted Processing Strategy: Recognition based on a Synthetic Comprehensive Image Model T h e processing strategy that was adopted in this work is based on the use of a synthetic com-prehensive image model. Thi s image model facilitates a manual training set selection procedure in which unmodelled tree crown image properties are sampled, and the recognition procedure uses the image model that has been extended with example-based knowledge derived from the training set. In contrast to the existing token-based individual tree crown recognition proce-dures reviewed in Section 3.3, the adopted strategy does not rely on the existence of explicit tree crown image region boundaries or a large amount of contrast between the tree crown image region and the surrounding image region. In contrast to procedures that are based on purely example-based comprehensive image models (see Section 3.4) the adopted strategy permits readily acquired knowledge of the sensing system, the sensing situation, and physical properties of individual tree crowns in the scene (the image formation knowledge) to be used to constrain the task of collecting example-based data on tree crown images, and to constrain the recognition task. Image formation knowledge is directly encoded as value intervals for the parameters of the synthetic component of the image model. T h e involvement of image formation knowledge in the recognition procedure is also intended to make the procedure less reliant on specific scene Chapter 3. The Recognition Task 26 and sensing conditions than other tree crown recognition procedures. We consider that the definition of a synthetic tree crown image model is generally practical only for a single image channel and only up to, but not including, the application of a uniform gain and offset (this is discussed further in Chapter 4). Further constraints that are related to absolute apparent radiance in one or more wavelength regions and to the gains and offsets that were applied independently to one or more image channels are derived from the training set. T h e synthetic component of the image model includes a parameterized three-dimensional description of general crown envelope size and shape. T h e objective of the recognition procedure is to associate instances of the image model with locations in the image such that the crown envelope descriptions provide approximations of the visible scene extent of tree crowns that existed at the corresponding scene locations when the image was acquired. Each such associa-tion of a model instance and an image location is called a recognition instance. T h e projection of the spatial extents of the estimated crown envelopes onto the image provides image-space localization of tree crown image extent. Crown diameter estimates are derived from the model instance parameter values. T h e overall strategy is to compute a set of initial recognition instances that satisfy inex-pensively applied constraints derived from the image formation knowledge, but that may also contain a large proportion of false instances, and then to filter the recognition instances in fur-ther processing steps that involve constraints that are applied at greater expense per recognition instance. T h e strategy is described in further detail below and illustrated in Figure 3.3. T h e training set selection procedure and the recognition procedure are preceded by the same step. In this initial step the image extent and the parameter space of the synthetic component of the image model are searched for locations where a measure of the strength of the match between the synthetic model instance and the local pattern of image values is at a local maximum and is no lower than a liberally-specified threshold. These matches constitute the initial recognition instances. T h e search region of the model parameter space is defined by the user-specified model parameter value intervals. In the training set selection procedure, Chapter 3. The Recognition Task 27 interpretat ion confl ict reso lu t ion filter (use of recogni t ion resul ts) Figure 3.3: Processing strategy (ellipses label data, boxes label operations). Chapter 3. The Recognition Task 28 image regions that correspond to a sample of the full range of crown and stand types in the overall scene are manually defined. Examples of correct and incorrect recognition instances are then manually selected from the initial recognition instances within these image regions, and features involving the image values within the corresponding tree crown image regions are evaluated for these examples. T h e user is not required to manually delineate or window individual tree crown image regions. T h e example-based component of the image model is applied in the second step of the recognition procedure. For each of the initial recognition instances, the features are evaluated and the probability that the instance is correct (the correct recognition probability) is estimated on the basis of the distribution of the elements of training set in the feature space. Initial recognition instances with a correct recognition probability value under 0.5 are rejected. T h e results of the second step of the recognition procedure (the intermediate recognition instances) are expected to sometimes contain conflicting interpretations of the same image re-gion (i.e., one large crown image versus multiple small crown images), since each intermediate recognition instance is established independently of any other. T h e goal of the third and final step of the recognition procedure is to resolve conflicts due to physically implausible spatial relationships among the intermediate recognition instances while retaining a good overall inter-pretation of parts of the image that portray forest cover. T h e physical constraint that within forest stands the volume of the crown envelope intersections is generally less than the remain-ing crown envelope volume is applied in this step. This is possible because each recognition instance is associated with a crown envelope boundary defined in both the scene-space and the image-space. A synthetic comprehensive tree crown image model and procedures that implement the adopted strategy are described in Chapters 4 and 5, respectively. Chapter 4 Synthetic Tree Crown Image M ode l T h e main simplifying assumptions incorporated into the synthetic tree crown image model (referred to simply as the 'image model' in the remainder of this chapter) are the following: 1. a tree crown is rotationally symmetric about a vertical axis in both overall shape and composition 2. the sensor produces single-channel image values that are linearly related to sensor irradi-ance 3. the images are acquired under clear sky conditions. Assumption (1) arises from the observation that tree crowns tend to be compact objects with a large degree of rotational symmetry about a vertical axis. Assumption (2) is reasonable because modern electro-optical sensors such as the M E I S II are capable of producing images in which the pixel values for a scene object have a highly linear relationship to the object's apparent radiance pattern at the sensor. Furthermore, the variation in the length and composition of the atmospheric path between a point on a single tree crown and an airborne sensor at typical flying heights is, as a fraction of the average, minute over the visible extent of the tree crown. Therefore, when sensing narrow wavelength band intervals that are well within the capability of many electro-optical sensors (< 0.15/mi), it is reasonable to assume that the atmospheric effect at the sensor on the actual radiance of a single tree crown is equivalent to the application of a uniform gain (due to the atmospheric path absorption and 29 Chapter 4. Synthetic Tree Crown Image Model 30 scattering) and a uniform offset (due to the atmospheric path radiance) (Horvath, Braithwaite, and Polcyn 1970). Assumption (3) is reasonable because it corresponds to a restriction that normally applies to the acquisition of aerial photographs for forest type mapping. Electro-optical sensors designed for remote sensing typically generate multiple image chan-nels that correspond to sensor irradiance within different wavelength intervals or bands, and the multispectral radiometric properties of individual elements of trees (individual leaves, bark, and cones) are well-studied, as are the integrated radiometric properties of collections of tree crowns (see Guyot et al. (1989) for a survey). This motivates the inclusion of interband radiance relationships in the image model. However, different gains and offsets are normally applied to each image channel to optimize the use of the image value representation and this causes the relationship of the apparent radiance in the different sensing bands to be lost. In principle, this information can be recovered from knowledge of the sensing system, but the atmospheric effect on the relationship of the actual radiance in the different bands may also be significant. In consideration of the above, the image model is intended to be valid for a single image channel, and only up to, but not including, the application of a uniform gain and offset. T h e procedure that uses the model (described in Chapter 5) includes a step in which examples of correct and incorrect recognition results that are based entirely on the model are manually selected. T h e uses of these examples include the derivation of constraints that are related to interchannel image value relationships. T h e model components that are concerned with overall tree crown shape and the geometric characteristics of the sensing system are discussed in Section 4.1, and those that are concerned with the scene irradiance, its interaction with a tree crown, and the resulting sensor irradiance are discussed in Section 4.2. T h e evaluation of a model instance is described in Section 4.3. Notation pertaining to the use of model instances in the training and recognition procedures and ways in which differences between model instances may be measured are described in Sections 4.4 to 4.6. Chapter 4. Synthetic Tree Crown Image Model 31 4.1 Geometric Aspects 4.1.1 Crown Envelope Shape T h e crown of a non-suppressed tree can be divided at approximately the widest horizontal cross-section into an upper "sun crown" and a lower "shade crown" (Hakkila 1989). Only sun crowns are modelled since in aerial images of forest stands the sun crown is the only visible part of a tree, unless the view direction is off-nadir and the tree is open-grown, in a low-density stand, or at the edge of a clearing. We define a tree crown Cartesian coordinate frame {C} by the unit vectors {x c, y c , zc} such that the system is right-handed, z c points vertically upwards, and x c is directed towards true north (azimuth = 0 ° ) . T h e botanist Henry Horn proposed the following equation as a general model for the two-dimensional vertical profile of a crown envelope (Horn 1971, p. 106), defined here in the first quadrant of the j/2-plane of {C}: zn yn , , — + f - = l 4.1 a" bn K ' This is actually the equation for a generalized ellipse, due to Piet Hein (Gardiner 1965). In Equation 4.1, a and b are positive numbers that represent the intersection of the curve with the z- and y-axes, respectively, and n is positive and non-zero. W h e n n — 1 the curve is a straight line. A s n decreases past 1 to 0 the curve becomes increasingly upwards concave, and approaches the z- and y-axes. A s n increases from 1 the curve becomes increasingly downwards concave, and approaches the lines z — a, y = b. W h e n n = 2 the curve is part of an ellipse. To obtain the full crown profile, the curve is reflected in the z-axis. Horn proposed the use of one set of parameters to model the sun crown profile, and another to model the shade crown profile, with the same value for the horizontal radius, b, in both sets. We extend Horn's idea into three dimensions and model a crown envelope with a generalized ellipsoid of revolution ( G E R ) : zn (x2 + y2)2 — + - — T = 1- (4.2) Chapter 4. Synthetic Tree Crown Image Model 32 T h e modelled crown volume is bound by this surface and the zy-plane of {C}. Th i s model can be made to closely fit general graphical descriptions of crown form, such as those presented in (Hosie 1969). Figure 4.4 illustrates several crown envelopes defined by Equation 4.2. n = 1.5, a/b =10 n = 1.0, a/b = 6 n = 1.5, a/b = 4.5 n = 2.0, a/b = 2 n = 2.0, a/b = 1 Figure 4.4: Crown envelope examples. 4.1.2 Sensing Geometry We define a sensor Cartesian coordinate frame {5} by the unit vectors {x s ,y s , z s} such that the system is right-handed, x s points in fore direction of the platform and y s points in the port direction. T h e orientation of {5} relative to {C} is represented by the rotation matrix R , and the position of the origin of {5} with respect to {C} is represented by the translation vector t. Both R and t are a function of time. T h e projection vector p is the vector joining the apex of a tree crown and the origin of {5}, so p — t — h z c where h is the zc coordinate of the crown apex. T h e projection of a particular tree crown onto the image plane is modelled with a scaled orthographic projection of the tree crown in the direction of p onto a plane perpendicular to p. T h e scale of the image is computed as f/H, where H is distance between the optical centre and the scene along the optical axis (this is the flying altitude above the scene when the optical axis is vertical and the ground is flat and level). This projection simplifies the sensor irradiance model (this-will be made clear in Section 4.2.3), and it approximates the perspective projection geometry of both cameras and pushbroom scanners that have an optical centre located at the origin of {S}, an optical axis aligned with z s , and an image plane parallel to the xsys-p\ane and Chapter 4. Synthetic Tree Crown Image Model 33 intersecting the zs axis at / . T h e quality of the approximation is related to the angle between p and z s , as will be described later in this section. Relief displacement is the distance between the images of two separate points in the scene that lie on the same vertical axis. In a vertical perspective projection of a scene, a given scene object with a non-zero vertical dimension will exhibit increasing relief displacement with increasing distance from the intersection of the optical axis and the image plane (the optical axis image point). Relief displacement also increases with an increase in the ratio of object height to flying height. In the large to medium scale vertical aerial photographs commonly used in forest type mapping, radial relief displacement has a significant effect on the appearance of individual tree crowns. In aerial image acquisition with a pushbroom scanner the scanline is parallel to the detector array axis and the flightline is parallel to the flight velocity. We assume that the detector array axis is parallel to y s , and we consider the scanline and flightline to map to the along-row and along-column dimensions of the image, respectively (in this discussion, we assume that the image has not been subjected to a geometric transformation, including any transformation intended to compensate for platform instability). A pushbroom scanner image is a perspective projection of the scene only in the along-row dimension. W h e n the platform velocity is constant and perpendicular to the scanline, the image is a scaled orthographic projection of the scene in the along-column dimension. Therefore, a pushbroom scanner image that has been acquired with a vertical optical axis exhibits relief displacement only in the along-row dimension. Figure 4.5 shows that along-row relief displacement has a noticeable effect on the appearance of individual tree crowns in the M E I S II image data that were used in the experiment (the sensing situation and the image data are described in Chapter 6). Figure 4.6a represents the vertical perspective projection of a vertical scene object. In this figure / and O are, respectively, the lens focal length and optical center, A and A' are, respectively, the top and bottom of a vertical object, a and a' are, respectively, the projections of A and A' onto a horizontal image plane, h and H are, respectively, the height of the object Chapter 4. Synthetic Tree Crown Image Model 34 Figure 4.5: M E I S II subimages that show tree crown relief displacement. T h e subimages were extracted from a visible green wavelength channel, each subimage has 125 rows and columns, and the rows are aligned with the page width dimension. T h e middle subimage intersects the middle column of the flightline image, and the left and right subimages are parts of the flightline image near the opposite ends of the image rows. Because of relief displacement, the trees in the left and right subimages appear to "tilt" respectively to the left and right, and the dark between-tree gaps are less visible in these subimages than in the middle subimage. and the height of the lens optical centre, and r and R are, respectively, the distance between a' and the image plane nadir and A and the ground nadir. T h e relief displacement d is the distance between a and a'. image level h - d - H 4* i . - \ h sin 6„ .•1 _ H GROUND LEVEL GROUND LEVEL (a) (b) Figure 4.6: Vertical perspective projection (a) and orthographic projection (b). B y similar triangles, r(H — h) = Rf and H(r - d) — Rf. Equating the left hand sides of these two equations gives us the well-known formula for relief displacement in vertical aerial photographs: d = rh Chapter 4. Synthetic Tree Crown Image Model 35 Alternatively, d = Shj where S is the scale factor f/H. Let 8 be the angle between the line A'O and the optical axis. T h e n , d - Sh tan 8. In a scaled orthographic projection of a vertical object where 80 is the angle between the view axis to the object and the vertical axis (Figure 4.6b) the image distance between the top and bottom of the object, d0, is given by dQ = Sh sin 8Q Therefore, when 8 is small, the projection of the object onto the sensor's image plane may be closely approximated by a scaled orthographic projection where 8Q = 8 (and d0/d = cos#). For M E I S II along-scanline relief displacement the maximum value of 8 is 1 9 . 5 7 ° (McCol l , Neville, and T i l l 1983) and at this angle dQ/d = 0.94. T h e approximation may be improved by scaling the object projection in the direction of the relief displacement by a factor of l / co s# . T h e previous discussion assumes that the optical axis is vertical and that the scene terrain is flat and level. T h e relationship between a scaled local orthographic projection of a scene object and its perspective projection will not be as described above if these conditions are not met. In aerial image acquisition with a pushbroom scanner, a deviation of the optical axis from the vertical will cause a variation of the along-scanline dimension of the scene elements, a deviation due to aircraft pitch will result in a relief displacement component orthogonal to the scanline, and a flight velocity component that is not orthogonal to the scanline will skew the image. Chapter 4. Synthetic Tree Crown Image Model 36 4.2 Radiometric Aspects 4.2.1 Scene Irradiance In the simplest scenario for natural scene irradiance, an irradiated scene object is on flat and level terrain, light reflected from the adjacent terrain and the object contributes insignificantly to the sky radiance, and the sky is cloud-free and clear (i.e., with little haze). Under these conditions the total irradiance of a horizontal surface (Etot) is the the sum of the irradiance due to direct sunlight (the direct irradiance, E<nT), and of the irradiance due to the scattering of direct sunlight by the atmosphere (the diffuse irradiance, Edit). Although the atmosphere also emits radiation, this is negligible when sensing radiation with a wavelength/shorter than about 3 fj.m (Silva 1978). One component of the image model is a model of the scene irradiance under the conditions described above. T h e parameters of this model are the components of the unit vector s that points from the origin of {C} towards the centre of the sun' and the diffuse fraction of the total horizontal irradiance K — Edi{/Etot- T h e components of s are derived from the value for the angle 8S between s and z c (the solar zenith angle), and the clockwise (as seen from above) angle <^>s between the projection of s on the <ccyc-plane and xc (the solar azimuth). T h e output of the scene irradiance model is a set of collimated beams. Each beam has a direction and a perpendicular irradiance value that is normalized with respect to -Etot- One of the beams represents the direct irradiance. T h e direction of this beam is (0s,<ps) and its normalized perpendicular irradiance value is (1 - K)/ cos9s. T h e remaining beams represent the diffuse irradiance. T h e method of discretizing the distribution of the diffuse atmospheric radiation is taken from Woodham and Gray (1987). T h e sky hemisphere is discretized into 109 approximately circular, equal-area patches by mapping a 109-tile uniform hexagonal tessellation of the xcyc-plane that is centred at the origin of {C} onto the hemisphere with the azimuthal equal-area projection. Each diffuse irradiance beam is associated with one patch. T h e direction of diffuse Chapter 4. Synthetic Tree Crown Image Model 37 irradiance beam i is the direction (9{,fa) to the centre of the corresponding patch. Let Ldif{0i,fa,0s,fa) be the incident power per unit area per unit solid angle from an in-finitesimal patch of the sky hemisphere centred along direction (#;, fa), when the sun is in posi-tion (0S, fa). Various models have been developed to provide estimates of LdHfa, 0S, fa)/Ed\{, (denoted by N(0{,fa,0s,fa)) for shortwave radiation from clear skies (see Siala et. al. (1990) for a survey). A n y such model can be used to evaluate the normalized perpendicular irradiance value, P(0{,fa), associated with diffuse irradiance beam i. We have not found an existing model of the hemispherical distribution of sky radiation that is wavelength-specific, or existing calibration data that makes a model wavelength-specific. However, the relative hemispherical distribution of clear sky radiation follows the same general pattern across the visible wavelength range: greatest in a circumsolar region, least in the quadrant opposite the sun, and increasing towards the horizon. Furthermore, clear sky radiation at wavelengths longer than the visible red and shorter than 0.3 fim is negligible since (1) 46 % of the total energy from solar irradiance above the earth's atmosphere falls between 0.40 fim and 0.76 ^ m , (2) Rayleigh scatter, which causes the great majority of clear sky diffuse radiation, is inversely proportional to the fourth power of wavelength, and (3) ozone absorption causes a cutoff in solar irradiation of the earth's surface at 0.3 ^im (Fraser, G a u t , Reifenstein, and Sievering 1975). If Up is the solid angle subtended at the origin by each sky hemisphere patch, then we have P(0t,fa)=ojpKN(0i,fa) (4.3) (0S and fa are omitted from the notation for clarity). If we assume that the patches exactly cover the hemisphere, then 109 E<M = w p Ld\{(0j, fa) cos0j (4.4) 3 = 1 Since Ld\{{0j, fa) = Ed\{N(0j,<j)j), we have 109 Edi{ = ujpEdi{ N(°j, ti) c o s °j ( 4-5) 3 = 1 Chapter 4. Synthetic Tree Crown Image Model 38 and T h e substitution of the right hand size of Equation 4.6 into Equation 4.3 yields F(Vi,<pi) - —. (4.7) £ j = i N(9j,<l>j) cos6j T h e effect of opaque obstacles on scene irradiance can be considered by setting N to zero for those beams that are intercepted by those obstacles (obstacles would also have an effect on the value of K). T h e three-component continuous distribution ( T C C D ) model (Hooper, Brunger, and C h a n 1987) is used to estimate N(6i,<f>i,8s,(j)s) and Equation 4.7 is used to evaluate P(6i,<f>i). Rela-tive to other models, the T C C D model is easy to use, accurate, and has been calibrated (for shortwave radiation) at a location close to P N F I . 4.2.2 Scene Irradiance and Tree Crown Interaction T h e interaction of scene irradiance with a tree crown depends on both the shape and the physical composition of the crown. T h e simplest composition model is based on the assumption of an opaque surface. Thi s assumption may be reasonable for young fairly open growing needle-leaved trees belonging to species with characteristically dense foliage (Albers, Strahler, L i , Liang, and Clarke 1990), or for broad-leaved trees with leaves that are concentrated near the crown envelope and are oriented to form a fairly continuous surface. However, an opaque surface assumption is difficult to justify in general, and in particular for mature trees and trees growing under competition. In the context of manual air-photo interpretation, Sayn-Wittgenstein describes variation between different crowns in the amount of photographic contrast between the part of a crown that is directly irradiated by the sun and the part that is not, and credits this variation mainly to differences in foliage density; he even suggests using this effect as a cue for distinguishing species with characteristically different foliage densities (for example, separating jack pine from spruce or balsam fir) (Sayn-Wittgenstein 1978). Chapter 4. Synthetic Tree Crown Image Model 39 These considerations have led to the development and examination of two models of the interaction of scene irradiance with a tree crown: an opaque surface model and a more complex permeable volume model. In both models, the crown volume is approximated by a subset of a three-dimensional volume array that consists of the array cells with centres inside a crown envelope defined by a generalized ellipsoid of revolution and and the £ c y c - p l a n e (the crown cells). A volume array cell has uniform side dimensions. T h e position and orientation of the volume array depends on the relative position and orientation of {5} and {C}. Thi s will be discussed further in Section 4.2.3. A surface cell is a crown cell that is 6-connected to a non-crown cell, and whose centre is closer to the generalized ellipsoid of revolution part of the envelope than to the x c j / c -plane. A surface cell is associated with a surface point, which is the point on the surface of the crown envelope that is closest to the centre of the surface cell. For each surface cell, the components of the outward unit normal vector at the corresponding surface point are determined. In the opaque surface model, the contribution of an incident collimated beam of light to the radiance leaving a surface cell in a particular view direction is a function of the angle between the beam direction and the surface cell normal vector (the incident angle) and of the angle between the view direction and the normal vector (the exitant angle). T h e Minnaert reflectance function (Woodham and G r a y 1987) is used: LT = pEo(-k + l ) cos*(0 c o s * - 1 ^ ) . (4.8) 27T In this equation E0 is the perpendicular irradiance of a collimated beam of light with incident angle i, Lr is the observed radiance at exitant angle e, p is assigned a value in (0,1] that can be used to account for absorption, and k is assigned a value related to the intrinsic properties of the surface. Equation 4.8 is a physically plausible model of the reflectance of an opaque surface for 0 < k < 1. This can be argued by considering the signs of the partial derivatives of Lr with respect to i and e and by reasoning that (1) with increasing i a given beam of light illuminates a larger surface area, so one should not observe an increase in brightness though a given aperture, and (2) with increasing e one sees more surface area through a given aperture, so should not Chapter 4. Synthetic Tree Crown Image Model 40 observe a decrease in brightness. Both i and e are restricted to [0, | ) . If i is outside this interval then the beam does not irradiate the surface point, and if e is outside this interval then the surface point is invisible. Under the Minnaert reflectance function, Lr/(E0cos(i)) is unchanged when the values of i and e are interchanged. Thi s is a basic physical constraint for opaque surfaces called the Helmholtz reciprocity condition (Minnaert 1941). T h e reflectance of many natural diffusely reflecting opaque surfaces can be accurately mod-elled with the Minnaert reflectance function. Values of k in the neighbourhood of 0.7 have been associated with loose porous surfaces, while values approaching 1 are characteristic of more compact surfaces (Young and Collins 1971). W h e n k = 1 Equation 4.8 becomes the expression for the Lambertian reflectance function. In the opaque surface model implementation, the same user-specified value of k applies to all surface cells and p is arbitrarily set to 1 for all surface cells. T h e simulated radiance of a surface cell in the opaque surface model is the sum of the contributions of all of the beams that comprise the simulated scene irradiance. In the permeable volume model a tree crown is considered to be a volume of light-scattering elements. These elements are assumed to be randomly oriented and positioned, small relative to the size of the cells, and to have uniform size, shape, and radiometric characteristics. Wi th in a crown cell there is a uniform density of light-scattering elements. Each crown cell is assigned a projected one-sided light-scattering element area density D according to a specified distribution (this is discussed in detail below). T h e value of D for a particular cell is assumed to be constant over all projection directions. A light ray that is incident to a cell is either intercepted by a light-scattering element or passes through unintercepted. T h e assumption of small randomly oriented and positioned light-scattering elements leads to the use of Bouguer's law to compute the probability G that ray r will pass unintercepted through a cell when the path length of r through the cell is s (the gap probability): G = e x p ( - £ ) s ) . Chapter 4. Synthetic Tree Crown Image Model 41 A beam of light impinging on a cell from direction (0, 4>) with normalized perpendicular irradiance P is represented by a pencil of regularly spaced parallel rays directed along (0,(f>). Each ray is the central axis of a portion of the beam. Each portion has the same cross-sectional area A. T h e normalized radiant flux Q from the portion of the beam represented by ray r that is intercepted by the cell is evaluated according to Q = AP(1 - exp(-Ds)). T h e constant A is arbitrarily set to 1 in the model implementation. T h e normalized perpendic-ular irradiance P' of the portion of the beam represented by r upon leaving the cell is evaluated according to P' = P exp(-Ds). Some of the non-intercepted light that reaches a crown cell may first pass through other crown cells. If a particular ray has to travel through cells 1 , . . . , n with density values Di,...,Dn and individual cell path lengths si,...,sn, and the normalized perpendicular irradiance associ-ated with the ray before entering cell 1 is P, then the normalized irradiance P' that is associated with the ray on leaving cell n is evaluated according to n P' = Pexp(-J2DiSi). T h e total simulated normalized radiant flux intercepted by a cell is computed as the sum of the contributions from all the beams that comprise the simulated scene irradiance, with each beam ray passing through the centre of the cell. T h e permeable volume model is limited to single-scattering, in other words re-radiated flux from one cell that is intercepted and scattered by other cells is ignored. T h e unabsorbed intercepted flux for a cell (the flux that is transmitted and reflected by the light-scattering elements in the cell) is assumed to leave the cell as isotropically distributed flux originating from the centre of the cell. Therefore, the radiant intensity (power per unit solid angle) leaving a cell in the direction towards the viewer is directly proportional to the unabsorbed intercepted flux for the cell. Chapter 4. Synthetic Tree Crown Image Model 42 We assume that the significant light-scattering elements in a fully leaved tree crown are the leaves. A s the size of a tree crown increases, the distribution of foliage within the crown generally becomes less uniform because the light that reaches an inner region of the crown falls below the compensation point of the leaves, which die and are not replaced (Jack and Long 1992). In response to this, the value of D for a crown cell is a function of the distance x from the centre of the cell to the closest point on the surface of the crown envelope, as defined by D(x) = alX^{l-x)a\ (4.9) This function can provide a wide range of distributions, from nearly uniform to sharply peaked, depending on the values of a i , a2, and a 3 . In Wang et al. (1990) a close fit to the measured radial horizontal and vertical leaf area density distributions for 26 Radiata pine trees with this function is demonstrated. T h e values of ai, a2, and are derived from (1) the depth beyond which the projected one-sided light-scattering element area density is zero ( X e n d ) , (2) the depth of the maximum density ( X m a x ) , (3) the maximum density ( - D m a x) , and (4) the average density ( Z ) a v g ) . W i t h a2 and G&3 greater than zero, D(x) in Equation 4.9 has a single maximum. Let bi and b2 be, respectively, the value of this maximum and the corresponding value of x. Let 63 to denote the value of the second derivative of D(x) at b2. It is possible to show that „ _ -hb22{l-b2) a2 -- 6 3 6 2 ( 1 - b2)2 a3 = 7 61 61 6 ^ ( 1 - 6 2 K T h e interval [0, Xend] is scaled to [0,1], so that b2 = XmAX/Xend. Also, 61 = Dmax. T h e value of 63 corresponding to D a v g is estimated with a root-finding procedure, which is possible because for fixed positive values of 61 and 62 the area under the curve defined by Equation 4.9 strictly decreases with an increase in the magnitude of 63. Figure 4.7 illustrates some distributions produced by Equation 4.9. Chapter 4. Synthetic Tree Crown Image Model 43 Xend = 1.00, Xmax = 0.10, Dmax = 1.00, Davg = 0.33 Xend = 1.00, Xmax = 0.33, Dmax = 1.00, Davg = 0.33 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 Xend = 1.00, Xmax = 0.33, Dmax = 1.00, Davg = 0.66 Xend = 1.00, Xmax = 0.33, Dmax = 1.00, Davg = 0.99 0.8 0.6 0.2 0 0.2 0.4 0.6 0.8 1 0.2 0.4 0.6 0.8 1 Figure 4.7: Light-scattering element area density distribution examples (X: horizontal axis, D : vertical axis) Chapter 4. Synthetic Tree Crown Image Model 44 Individual leaves generally have greater reflectance and transmittance in the near-infrared wavelength region (over 40 % for both) than in the visible region (under 20 % for both) (Gaus-man, Al len, Wiegand, Escobar, and Rodriguez 1971; Will iams 1991). Thi s suggests that both the opaque surface model and the permeable volume model should be more appropriate for visible wavelength sensing than for near-infrared wavelength sensing. 4.2.3 Sensor Irradiance A sensor is modelled such that its optical centre is at the origin of {S}, its view axis coincides with the z s-axis, and its image plane is parallel to the x s y s -p lane and intersects the 2 s-axis at the sensor focal length / . A n image plane array is defined such that the along-column axis is parallel to the a;s-axis and the along-row axis is parallel to y s-axis. T h e image plane array elements are square with side dimension p. T h e offset of the optical axis image point from the nearest array element centre depends on the sensor that is being modelled. T h e M E I S II has 1024 image plane array row elements, so the optical axis image point lies on the boundary between column 511 and column 512, where the first column has index 0. A pushbroom sensor such as the M E I S II acquires an image one row at a time and is therefore more accurately described as having an 'image line' rather than an 'image plane.' However, we assume that the sensor moves in the x s direction at a constant speed such that the spacing of the rows is the same as the spacing of the elements along the rows. Thi s permits the definition of an image plane array with an indefinite number of rows. T h e axes of the three-dimensional volume array that contains the crown cells are labelled a, b, and c. T h e cell dimension is pH/f, where H is the vertical distance between the origin of {5} and the ground. Thi s is the dimension of the projection of an image plane array element onto flat and level ground when the x s y s -p lane is horizontal. T h e orientation of the volume array when p is oriented such that the axis through p intersects the point (xs = dx, ys = dy, andzs — f) on the image plane is defined by the following sequence: 1. Orient the volume array such that the a, b, and c-axes are parallel to x s , y s , and z s , Chapter 4. Synthetic Tree Crown Image Model 45 respectively, and define a rotation axis that intersects the origin of {5}, is in the xsys-plane, and is perpendicular to the line joining (0, 0, / ) and (dx, dy, f) (see Figure 4.8a). 2. Rotate the volume array about the rotation axis until the c-axis is parallel to p (see Figure 4.8b). A s (d..d...n 7 . Jd x , d y , f ) rotation axis section of the volume array rotation axis rotated section of the volume array (a) Figure 4.8: Volume array orientation (see text for explanation). Additionally, the volume array is positioned such that in step (1) the a- and o-axis cell intervals coincide with intervals of the projection of the image plane array onto a plane that is perpendicular to the z s-axis and intersects the z s-axis at —H (this is the ground plane when the xsys-plane is horizontal and the ground is flat and level). A n arbitrary 'slice' of the volume array (defined by a constant c-coordinate) between the scene and {5} represents a sensor detector array. A detector array element corresponds to the image plane array element that projects to the detector array's exposit ion at step (1). T h e mapping between the detector array elements and the image plane array elements is not changed by the rotation in step (2). Thi s causes Chapter 4. Synthetic Tree Crown Image Model 46 the relationship of sensor irradiance to the modelled image of a tree crown to be based on the scaled local orthographic projection described in Section 4.1.2. For a pushbroom sensor, the dx component of the offset is always zero. In the opaque surface model, the exitant angle for a surface cell is the angle between the cell's normal vector and p. T h e magnitude of the simulated irradiance of the corresponding detector element is set to the magnitude of the simulated surface cell radiance. Let Q be the total intercepted flux for a crown cell in the permeable volume model and let a be the associated absorptance (the fraction of the intercepted flux that is absorbed by the light-scattering elements in the cell). If there are n crown cells between this cell and the detector element array with density values D \ , . . . , Dn and each with a side dimension c, then the contribution of the cell to the irradiance of the corresponding detector element is evaluated according to n V = (1 - a ) Q e x p ( - c ^ A ) -i=l In the current model implementation, a is the same for all cells, so the factor (1 — a) is arbitrarily set to 1. In the permeable volume model, a background is represented by a two-dimensional array of volume cells occupying an a6-plane of the volume array. T h e background is positioned such that all of the crown volume cells are between it and the detector element array. Background radiance is simulated by assigning an intercepted flux value to background cells and including these cells in the computation of the sensor irradiance in the same manner as the crown cells. Only the background cells that have the same (a, b) coordinate of at least one crown cell are given an intercepted flux value, and the value is the same for all such cells. T h e intercepted flux value is a specified multiple B of the average of the detector irradiance values for the crown with no background radiance. Only the detectors that have the same (a, b) coordinate of at least one crown cell are involved in the computation of the background intercepted flux value (the irradiance value is undefined for the other detectors). Chapter 4. Synthetic Tree Crown Image Model 47 4.3 Model Instantiation A pixel value in an image model instance is obtained by applying a gain and an offset to the magnitude of the simulated irradiance of the corresponding detector element. T h e gain and offset are uniform over the image and are evaluated so that the pixel values in a single model instance span the full value range of the specified pixel value representation. A n unsigned byte pixel value representation was used in the main experiment. T h e elements of the rotation matrix R that represents the orientation of {5} with respect to {C} (see Section 4.1.2) may be derived from many different specifications. One convenient approach that we have implemented is to use a roll angle (7), a pitch angle (/?), and a flightline azimuth (fa). A n orientation that is specified with these angles is equivalent to the result of first aligning the axes of {S} with the corresponding axes of of {C} and then applying the following sequence of rotations to {S}: (1) about x c by 7, (2) about y c by (3, and (3) about z c by —fa (azimuth is a negative rotation angle in a right-handed coordinate frame). T h e orientation of the projection vector p is a function of the image offset of the crown apex from the optical axis image point and of the sensor orientation. Pushbroom scanner image skew (due to aircraft yaw) is not modelled. T h e parameters of the complete model are summarized as follows: (1) sensing geometry: (1.1) / : lens focal length (metres) (1.2) p: image plane array element dimension (metres) (1.3) H: vertical height above ground level (metres) (1.4) 7: roll angle (degrees) (1.5) (3: pitch angle (degrees) (1.6) fa: flightline azimuth (degrees) (1.7) dT: image row offset of the crown apex from the optical axis image point (pixels) Chapter 4. Synthetic Tree Crown Image Model 48 (1.8) dc: image column offset of the crown apex from the optical axis image point (pixels) (2) scene irradiance 1 (2.1) 9S: solar zenith angle (degrees) (2.2) (f>s: solar azimuth (degrees) (2.3) K: diffuse fraction of the total horizontal irradiance (dimensionless) (3) tree crown shape and size: (3.1) a: generalized ellipsoid of revolution ( G E R ) vertical radius (metres) (3.2) b: G E R horizontal radius (metres) (3.3) n: G E R exponent (dimensionless) (4a) Minnaert reflectance function k (opaque surface model only) (dimensionless) (4b) projected one-sided light-scattering element area density distribution (permeable volume model only): (4.1) Xen<i: depth beyond which the density is zero (metres) (4.2) Xmax: depth of maximum density (metres) (4.3) Dmax: maximum density (metres 2 /metres 3 ) (4.4) D a v g : average density (metres 2 /metres 3 ) (5) B: factor for computing the simulated background radiant intensity (permeable volume model only) (dimensionless) Values for / and p are derived from the sensor specifications, and are fixed. Values for H, 7, f3, and a must be obtained during image acquisition. Ideally, these are constant over a single image. Values for 8S and 4>s are readily calculated from the time and location; these values 'This list excludes calibration data for the adopted model of the hemispherical distribution of difuse sky radiation. Chapter 4. Synthetic Tree Crown Image Model 49 vary continuously during a mission but the significance of the variation depends on the length and geographic extent of the mission. T h e value of K for a scene depends on the wavelength, relative optical path length, atmospheric conditions, and reflectance properties of the terrain (Iqbal 1983) and may be readily measured during image acquisition. Measurements of the value of K under various conditions are also available from the literature (e.g., Oliver et al. (1975) and McDowel l (1974)). Knowledge of the scene and of the tree species expected to exist in the scene is required to evaluate the parameters related to tree crown shape, size, and composition. This is discussed further in Chapter 6. A n instance of the image model is contained within a rectangular array of pixels. T h e origin pixel of a model instance array, as well as any scene image array, has coordinates (0, 0). T h e following ancillary data is associated with the model instance array: 1. the values of the model instance parameters 2. the array coordinates of the pixel to which the crown apex projects (the apex location) 3. the array coordinates of the pixels that comprise the synthetic tree crown image (the extent locations) 4. the array coordinates of the pixel within which the centroid of the crown image extent locations lies (the extent centroid location) 5. the array coordinates of the pixels that indicate the visible extent of the directly irradiated portion of the surface of the crown model instance (the direct irradiation locations). T h e crown apex and the extent centroid are point features. Figure 4.9 illustrates an example of an image model instance and the associated point features locations. T h e apex location is to the left of the extent centroid location in the illustrated model instance because the projection vector is not vertical. T h e direct irradiation locations in a model instance array correspond to visible directly irradiated surface cells. If the angle between the surface cell normal vector and the vector Chapter 4. Synthetic Tree Crown Image Model 50 (a) (b) (c) (d) Figure 4.9: Tree crown image model instance (a), superimposed apex and extent centroid locations (b), extent locations (c), and direct irradiation locations (d). pointing in the direction (9S, </>s) from the origin of {C} is less than | then the corresponding surface cell is classified as directly irradiated. 4.4 Notation T h e following notation will be used in the remainder of this dissertation: • M , : image model instance i , consisting of an image array and the ancillary data listed in Section 4.3 • If. the image array for M,- ; the array has Ri rows and C,- columns • C»,j): the (row, column) coordinates of the apex location for Mi • (rc,i, cc,i)'- the (row, column) coordinates of the extent centroid location for M,-• a list of the (row, column) coordinates ( r x , c i) , ( r 2 , c 2 ) , . . . , (r/., c/.) of distinguished pixel locations in the locations are listed in ascending order primarily on the value of r and secondarily on the value of c so that rj+i > rj and c J + i > Cj if r J + i = r-j • £ e , t ' : list of the le<{ extent locations in I{ • Cd,i- list of the ld,i direct irradiation locations in Ii Chapter 4. Synthetic Tree Crown Image Model 51 • e'^: vector of dimension / e , i evaluated such that = Ii(rj,Cj) where (rj,Cj) is item j o f £ e , i -• d^: vector of dimension / d , i evaluated such that d^' = I{(rj,Cj) where (rj,Cj) is item j of £d,t'-T h e model instance index (i in the above list) is omitted where it is clearly implied by the context of discussion. A model instance may be positioned with respect to a scene image array by specifying the scene image (row, column) array location that coincides with the location of a designated point feature (called the registration feature) in the model instance. T h e row and column axes of the model instance are assumed to always be aligned with, respectively, the row and column axes of the scene image array. Let (x, y) denote a scene image array (row, column) location and reg denote a registration feature (reg = a when the registration feature is the apex and reg = c when the registration feature is the extent centroid). T h e vectors of image values from scene image array S that coincide with the extent locations and the direct irradiation locations of M ; when this model instance is registered to (x,y) by reg are denoted by s ^ { i ) ' r e 3 ' x ^ and s ( d W ' r e ^ ) , respectively (items may be omitted from the superscripts where they are clearly implied by the context of the discussion). Vector s ^ ' r e 9 ' x ' y ^ has / e , i elements and vector s(d(>)*<re9< x'V) has ld,i elements. T h e elements of these vectors are evaluated according to Sj = S(x + rj — rregti, y -\- Cj — cregt{) where (rj,Cj) is item j of £ e , i , and (d('',reg,x,t/) C( j_ i \ — j(x -\- rj — rregt{, y -\- Cj — cregti) where (rj, Cj) is item j of £d,i-Subsequent discussions will also refer to normalized vectors that have an element mean value of zero and unit length. If v is a d-dimensional vector, then the normalized version, denoted v, Chapter 4. Synthetic Tree Crown Image Model 52 is computed according to 1 d t=i and v — u 1 | | v - / i l | | 4.5 Extent Similarity Consider a set of model instance image arrays M = { M i , . . . , Mn} in which all the elements have the same row and column dimensions and the same location for a designated point feature. T h e corresponding model instances are aligned on the designated point feature, which is referred to as the alignment registration feature (or simply as the registration feature when the context is clear). Let £ n be the list of / n locations that occur in all of £ e , i > • • ->A:,raj and let Cu be the list of /u locations that occur in at least one of £ e , i i • • - ,£e,n- T h e extent similarity TJM for M is the ratio / n / A j -Extent similarity is a value in [0,1]; the value is 1 if and only if for all aligned image arrays each extent location is an extent location in. all of the others, and is 0 if and only if no extent location in one of the aligned image arrays is an extent location in any other. T w o model instances, 6 and c, exhibit an extent difference if and only if their extent similarity il{b,c} i s l e s s than 1. T w o model instances that are generated with different values for one or more of the parameters that define shape, size, and sensing geometry may exhibit an extent difference. If the sensing geometry parameter values for the different parameter sets are such that the x s y s -p lane is horizontal and the projection vector is vertical, then two model instances that are generated from different values for a, n, or fa will not exhibit an extent difference. Also, model instance extents vary in discrete steps, so a parameter value change can be too small to cause an extent difference. Chapter 4. Synthetic Tree Crown Image Model 53 4.6 Pattern Correlation Consider model instances a and b with an extent similarity of 1 and with image value vectors e( a' and e^b\ T h e correlation coefficient for corresponding elements of e^a) and is the pattern correlation for the model instances. T h e correlation coefficient is a dimensionless value that ranges between —1 and 1 and measures the degree to which two variables are linearly related (Hogg and Craig 1978, § 2.3). Perfect negative and positive linear relationships are represented by correlation coefficients of —1 and 1, respectively. T h e normalized vector is the pattern for model instance i. T h e pattern correlation for the two model instances a and 6, denoted paib, is the inner product of the corresponding patterns: paib = e^T e<>). (4.10) Pattern correlation is undefined for two model instances that exhibit an extent difference. T w o model instances exhibit a pattern difference if and only if their pattern correlation is less than 1. T w o model instances that are generated from different composition models (opaque surface or permeable volume), or with different values for one or more of the parameters that define the scene irradiance and the light-scattering element area density (permeable volume model only), k (opaque surface model only), or B (permeable volume model only) may exhibit a pattern difference. If the sensing geometry parameter values for the different parameter sets are such that the x s y s -plane is horizontal and the projection vector is vertical, then two model instances that are generated from different values for a, n, or fa will not exhibit an extent difference and may exhibit a pattern difference. T h e model instance image values vary in discrete steps, so a parameter value change can be too small to cause a pattern difference. Chapter 5 Procedures Let M{ be an instance of the synthetic tree crown image model 1 , reg be a specified registration feature (i.e., the crown apex or the extent centroid), S be a scene image array that represents a single specified channel of the scene image data, and (x,y) be a location in S. T h e correlation coefficient PAf i,S,r«^,, = e W T s ( « ( i ) ™ * » ) is used as a measure of the strength of the match between Mi and the scene image in the shared initial matching step of the training and recognition procedures when M,- is positioned at (x, y) (the notation used here is described in Section 4.4). This is appropriate because the model is intended to be valid only up to, but not including, the application of a uniform gain and offset to the scene image, and variations in uniform gain and offset do not affect PMi,s,reg,x,y Components of the subscript for p will be omitted where they are clearly understood from context or are irrelevant to the discussion. T h e initial matching step consists of searching the scene image spatial extent and the model parameter space for locations where p is at a local maximum and above a liberally-specified threshold. T h e search region of the model parameter space is defined by the user-specified parameter value intervals. T h e amount of computation involved in the generation of a model instance has motivated the use of precomputed model instances in the initial matching proce-dure. T h e organization and generation of these model instances is described in Section 5.1. 'The synthetic tree crown image model wil be refered to simply as the 'model' in the remainder of this chapter wher  the context excludes example-based model components from the discussion. 54 Chapter 5. Procedures 55 T h e representation of the recognition instances that are produced by the initial matching procedure and filtered by the remaining procedures is described in Section 5.2. T h e procedures for the initial matching step, the evaluation of correct recognition probability, and the resolution of interpretation conflicts are respectively described in Sections 5.3, 5.4, and 5.5. 5.1 Model Instance Organization and Generation T h e scene image extent is partitioned into p recognition regions R E C R E G i , . . . , R E C R E G p within which the sensing geometry, scene irradiance, and constraints on the various tree prop-erties that correspond to the model parameters are considered to be practically constant. T h e recognition region R E C R E G ; is associated with the model instance set M I S E T ; . Each model instance in M I S E T ; incorporates the values for the'sensing geometry and scene irradiance parameters that are associated with R E C R E G i , and only model instances from M I S E T ; are involved in the final tree crown recognition instances within R E C R E G p . T h e model instance set M I S E T ; is partitioned into uniform-extent subsets: M I S E T ; = U E S S E T i , i U • • • U U E S S E T i i ? i . T h e uniform-extent subset U E S S E T t J - consists of r 8 ) j model instances: U E S S E T . - J = { M , - , M i < j t r i J . T h e elements of a uniform-extent subset are such that when they are aligned on a specified registration feature (i.e., the crown apex or the extent centroid) the subset has an extent similarity of 1 (see Section 4.5 for the definition of extent similarity). T h e different uniform-extent subsets represent the modelled tree crown spatial extent vari-ation within the image-space: any two elements drawn from different uniform-extent subsets exhibit an extent difference when they are aligned on the specified registration feature (see Chapter 5. Procedures 56 Section 4.5 for a definition of extent difference). T h e different model instances within the same uniform-extent subset represent the modelled pattern variation associated with a fixed image-space tree crown spatial extent: any two elements of the same uniform-extent subset exhibit a pattern difference (see Section 4.6 for the definition of pattern difference). T h e procedure that we use to generate a model instance set is described in Figure 5.10. T h e procedure generates random samples of model instances that respect the specified constraints on the parameter values, and constructs the model instance set from relatively small subsets of the sample sets. T h e model instance set is representative of the sample sets in the sense that all elements of the sample sets are similar to one or more elements of model instance set with respect to extent and pattern, where the required degree of similarity is expressed by the values of rji,...,r]s and pdiff- T h e evaluation of the inputs to the procedure is discussed in Section 5.1.1, and an algorithm that accomplishes steps (3.2) and (3.4.4) of the procedure is described in Section 5.1.2. 5.1.1 Evaluation of Inputs to Model Instance Set Generation T h e evaluation of the inputs to the model instance set generation procedure involves a certain amount of experimentation and adaptation to the scene. Therefore, details of the process are best described with an example, one of which is provided in Section 6.3. In this section we provide an outline of the process. T h e basic steps, which are discussed in further detail in the remainder of this section, are the following: 1. Define constraints on the locally variable parameters for the overall scene. 2. Evaluate b\,..., bs, and T/I, . . . , ns. 3. Evaluate pdiff> 5 5 E and 5 5 M -4. Determine a partitioning of the scene image extent into initial recognition regions. 5. If warranted by the scene knowledge, specialize the constraints on the locally variable pa-rameters to different parts of the scene and subdivide the recognition regions accordingly. Chapter 5. Procedures 57 Input: • fixed values for the sensing geometry and scene irradiance parameters for R E C R E G ; • constraints on the values for the locally variable parameters R E C R E G ; • a set of discrete values for b (the G E R horizontal radius) that respect the specified constraints and are denoted b\,...,bs, and corresponding extent similarity values • SSE, • «55M, /Miff Output: M I S E T ; (2) Let MISETj - = 0 and j = 1 (3) For g = l , . . . , s : (3.1) Generate a set E containing a random sample of SSE model instance extents within the constraints that have been defined for ( & s , | , n ) (a is the G E R vertical radius and n is the G E R exponent). (3.2) F i n d an approximately minimal subset E ' of E such that for any element e of E there is an element e' of E ' such that f]{e,e'} > Vg-(3.3) Let t = | E ' | and denote the elements of E ' by e[,..., e't. Partition the elements of E into t disjoint subsets E i , . . . , E 4 such that for h = 1 , . . . , t, e'h £ and T / E ^ = 1. (3.4) Forfc = l , . . . , t : (3.4.1) Let u = | E / j | and denote the elements of E ^ by e i , . . .,eu. (3.4.2) Let M = 0. (3.4.3) For k = l,...,u: (3.4.3.1) Generate a set Mfc containing a random sample of \SSM/U] model in-stances within the constraints that have been defined for the locally-variable parameter values, and with the additional constraint that the value for (6, | , n) is that of e .^ (3.4.3.2) Let M = M U M f c . (3.4.4) F i n d an approximately minimal subset M ' of M such that for any element M of M there is an element M' of M ' for which PM,M' — Pdiff-(3.4.5) Let UESSET,- , , - = M ' , M I S E T ; = M I S E T j U U E S S E T . j , and j = j + 1. Figure 5.10: Procedure to generate a model instance set. Chapter 5. Procedures 58 With in a particular recognition region, the model parameters related to sensing geometry and scene irradiance are considered to be fixed. T h e remaining parameters are locally variable since they are related to tree crown shape, size, and composition, and to background radiant intensity (cf. Section 4.3). T h e evaluation of the constraints that can be placed on the locally variable parameters will require knowledge of the scene and of the morphology of the tree species that are expected to occur in the scene. In Canada, information on expected species and stand types can be derived from knowledge of the one or more forest regions and sections (as described in Rowe (1972)) in which the scene is located. Useful published information on tree morphology for individual species is also available. Since p is a function of the pixels comprising the extent of a model instance and the coincid-ing image region, we convert the desired precision for estimates of the radius of large crowns, cr, into a required minimum extent similarity of two model instances with b = 6; and b — 0 ; + i . We make the assumption that the sensing geometry is such that most of the applicable model instances will have circular or near-circular extents, and evaluate to the extent similarity of two concentric circular regions with radii 6 m a x and 6 m a x — a: We then use 77adj to generate b\, b2,..., bs according to the algorithm described in Figure 5.11. This algorithm was designed in recognition of the fact that for small i, b{+i — bi, where 6,-+i = bf/Vadj, may be too small relative to the G P P D to be useful. Therefore, the algorithm accepts a minimum o-value increment ( A o ) m , n . We intend that a model instance for which b = b{ will match images of tree crowns with radii approximately in the range [&,• — xi, 6; + x2], where max* (5.11) Xi = y i ( A 6 ) j , ( A 6 ) i = bi - bi-x x2 = y2 ( A 6 ) 2 , ( A 6 ) 2 = bi+1 - b{ Chapter 5. Procedures 59 Input: 6 m i n , 6 m a x , 7/ a dj, ( A 6 ) m i n Output: 61, &2, • • • (1) Let i = 1, bi = bmin. (2) If bi > 6 m a x then halt and return 61,, • ,i>i-i-(3) Let bi+1 = y/bJ/Tjadj. (4) If bi+l - b i < (Ab) (4.1) Let 6,-+i = b{+ (Ab)min. (5) Let i = i + 1 (6) G o t o (2). Figure 5.11: Algori thm to compute a sequence of G E R horizontal radius values. and y i , y2 are evaluated so that x\ and x2 respectively define the extent difference midpoint for [bi-i,bi\ and [o; ,o t + i ]: ( 6 t - y i ( A 6 ) ! ) 2 bU ( 6 , - ( A 6 ) ! ) 2 6? " (bl-y1(Ab)iy bt - ( y i ( A 6 ) i )2 (68 + y 2 ( A 6 ) 2 ) 2 (6 t + y 2 ( A 6 ) 2 ) 2 (6i + y 2 ( A 6 ) 2 ) 2 6 2 + 1 We then evaluate 77; according to (6 t + ( A 6 ) 2 ) 2 2/i 2/2 = bi-y/b!-bi(Abh (Ab,) -bj + ^b? + bi(Ab)2 (Ab2) Vi = \ (bi+x2)* 6? b2 Q . - * i ) 2 -6? + if t = 1 if i = s /2 otherwise We evaluate pdin to an estimate of the value of p in cases where the pattern difference between a model instance and an image region is only due to unmodelled variation, or "noise." This is done by selecting a sample of tree crown images that have an exceptionally regular appearance (e.g., relatively little within-crown image texture, and a relatively smooth image boundary), and, for each element of the sample, computing p with each element of a large sample Chapter 5. Procedures 60 of model instances. T h e model instances are positioned by registering the model instance apex feature to the manually estimated apex locations in the tree crown images. T h e model instances are generated within the specified constraints on the locally-variable parameter values and with values for the sensing geometry and scene irradiance that are applicable to the tree crown image. T h e estimate for p^iff is set to a value that is no less than the maximum value of p obtained for each of the tree crown images. T h e values 5 5 E and 5 5 M determine the size of the sample sets E and computed in steps (3.1) and (3.4.3.1) of the procedure to generate a model instance set (Figure 5.10). Experimen-tally determined minimum values for 5 5 E and 5 5 M at which the sizes of the E ' and M ' subsets are maximum for the specified values of rji,..., rjs and p^\ff are used. T h e initial recognition regions are intended to comprise a partitioning of the spatial extent of the image such that the sensing geometry and the scene irradiation can be regarded as practically constant over each region. T h e sensing geometry and scene irradiation parameter values that are associated with an initial recognition region are estimates of the averages for those values over the region. We define the recognition regions experimentally, using sensitivity tests to help judge whether or not the deviation of the sensing geometry and scene irradiance parameter values from the average values over the recognition regions represent model instance extent or pattern dissimilarities that exceed the limits expressed by 771,..., r)s and Pdiff-A specialization of the constraints on the locally variable parameters to different parts of the scene, and a refinement of the recognition regions through subdivision, might be derived from further local knowledge of the terrain and of pre-existing stand types as recorded in old surveys. In many cases where knowledge of the scene is broad (at the level of knowing the forest region and section) and the overall spatial extent of the scene data is limited to the area covered by a single aerial image acquisition mission we can expect that there will be little grounds for varying the constraints over the scene. Chapter 5. Procedures 61 5.1.2 Computing an Approximately Minimal Dominating Set Steps (3.2) and (3.4.4) of the procedure to generate a model instance set both map to the problem of finding a minimal dominating set of a graph. A dominating set of a graph G that consists of the set of vertices V and the set of edges A is a subset V ' of V such that any vertex of G that is not in V ' is connected to one or more elements of V by a path of length 1. In the case of step (3.2) there is a one-to-one correspondence between elements of E and elements of V (et- V{), there is an edge joining u; and Vj if and only if n^eitejy > ^ i fr , and finding an approximately minimal E ' is equivalent to finding an approximately minimal V . In the case of step (3.4.4) there is a one-to-one correspondence between elements of M and elements of V (Mi <-> V{), there is an edge joining u,- and Vj if and only if PMi,Mj - Pdiflh and finding an approximately minimal M ' is equivalent to finding an approximately minimal V . T h e procedure to generate a model instance set involves the objectives of finding approxi-mately minimal subsets E ' and M ' because the problem of finding a minimal dominating set of a graph is known to be NP-complete. T h e minimal dominating set problem is approximable within a factor of 1 + ln | V | by means of a specialization of the greedy approximation algorithm for the minimal set covering problem described in Johnson (1974). This algorithm to find an approximately minimal dominating set of a graph is described in Figure 5.12, and is imple-mentable in time 0(n2) (or in time O ( n l o g n ) if step (2) is performed separately, as part of the process of constructing (V , A ) out of E or M ) . This algorithm gives reasonable results in practice (cf. Section 6.3.6). 5.2 Representation of Recognition Instances T h e location of a recognition instance in a scene image array is the scene image (row, column) array location that coincides with the specified registration feature of the model instance in-volved in the recognition instance. A t most, one element of a uniform-extent subset can be involved in a recognition instance Chapter 5. Procedures 62 Input: ( V , A ) Output: V : Vu,- £ V , 3VJ £ V ' such that (i>;, Uj) £ A and | V ' | is within a factor of 1 + In | V | of the minimum (1) Let V = 0, U N C O V = V , n = | V | . (2) For i = 1, . . . , n : (2.1) Let SET[z] = {v{}. (2.1.1) For j = l , . . . , n : (2.1.1.1) If («,-, U J ) 6 A and w^- ^ SET[t] then let S E T [ « ] = SET[t] U {VJ}. (3) If U N C O V = 0 then halt and return V : (4) Choose j, 1 < j < n, such that | S E T [ j ] | is maximized. (5) Let V = V U {VJ}, U N C O V = U N C O V - S E T [ j ] . (6) For i = l , . . . , n : (6.1) Let SET[z] = SET[t] - SET[j'] . (7) G o to (3). Figure 5.12: Algorithm to find an approximately minimal dominating set of a graph (adapted from the algorithm to compute an approximately minimal set cover in Johnson (1974)). Chapter 5. Procedures 63 at a particular location. One identifier map is defined for each uniform-extent subset. T h e identifier maps and the uniform-extent subsets together represent the recognition instances at any stage of the recognition procedure. T h e identifier map for a particular uniform-extent subset is only required to cover the associated recognition region. Since different recognition regions may have different numbers of associated uniform-extent subsets, they may also have different numbers of identifier maps. In order to simplify the following discussions, we will assume that recognition regions are rectangular and that the diagonally opposite corner elements of the maps coincide with scene image locations ( x m i n , y m i n ) and ( a ; m a x , y m a x ) , where a ; m a x ^ 2-min and y m ax ^ ymin' Let U E S S E T = {M\,.. .,Mr} be a uniform-extent subset, ID be the associated identifier map, S be the scene image array, and (x,y) be a location within 5 that maps to a location within ID (in this discussion, components are omitted from subscripts for clarity). If some Mi € U E S S E T is involved in a recognition instance at (x, y) then ID (x — xmm, y — ymin) = i', otherwise, ID (x - xmm, y - y m i n ) = null. 5.3 Matching Image Locations and Model Instances T h e objective of the procedure for matching image locations and model instances is to pro-duce for each recognition region R E C R E G ; , i = 1, . . . ,p , a set of identifier maps I D S E T , — {IDj'4 , . . . , ID J ) ? t } such that I D ; j represents initial recognition instances that involve model instances from U E S S E T ^ - . A n outline of the procedure that was used in the main experiment is presented in Figure 5.15. This procedure will be explained as a refinement of those outlined in Figures 5.13 and 5.14. Figure 5.13 illustrates the basic approach. For each uniform-extent subset and each image location within the recognition region find a model instance that has the maximum correlation coefficient with the coincident image region when positioned at the image location. If that correlation coefficient is no less than a specified threshold /?thr> then evaluate the coinciding Chapter 5. Procedures 64 location of the identifier map for the uniform-extent subset to the identifier id of the selected model instance; otherwise, evaluate it to null. T h e threshold p t h r is liberally specified (false recognition instances are eliminated in later processing steps) and confirmed through experi-mentation. T h e correlation coefficients associated with the selected model instances identified in ID,-,!, • • • i IDi,9i a r e retained in parallel maps R H O i , . . . , R H O g i . Locations in the R H O - m a p s that do not have locally maximum values are evaluated to null in the corresponding ID-maps. For a given R H O - m a p , the neighbourhood within which local maxima are searched for is de-fined by the extent of the associated uniform-extent subset. T h e procedure that implements this non-maximum suppression operation is outlined in Figure 5.16. T h e basic procedure that is illustrated in Figure 5.13 is essentially an exhaustive search through the image-space and the uniform-extent subsets. We decided to investigate the possi-bility of reducing the amount of computation involved in the matching procedure by exploiting the fact that a local maximum in a correlation surface tends to be the peak of a 'hill' whose spatial extent is related to that associated with the the uniform-extent subset (model extents that are relatively large in a particular direction tend to produce hills that relatively wide in that direction ) (c/. Section 6.4). T h e second version of the procedure, which is outlined in Figure 5.14, implements a refinement to support this investigation. Thi s procedure has parameters dfrac and p s t h n in addition to those of the basic procedure. T h e image-space is searched for matches using two resolution levels. A t the first resolution level, the x and y dimen-sions are searched in increments of dx and dy, respectively, where dx — m&x(dfrac X dimx, 1) and dy — max(dfrac X dimy, 1), and dimx and dimy are, respectively, the overall x- and y-dimensions of the extent associated with the current uniform-extent subset. If in this search a location (x0,y0) is found such that an element of the current uniform-extent subset has a correlation coefficient with the coincident image region that is no less than p s t h r , then each location of a neighbourhood of (x0,y0) is tested (this represents the second resolution level). T h e neighbourhood is defined by x0 — dx/2 < x < x0 + dx/2 and y0 — dy/2 < y < y0 + dy/2. A n experimentally confirmed value is specified for p s thr -Chapter 5. Procedures 65 Input: • S: single channel scene image • M I S E T ; : model instance set such that M I S E T ; = U E S S E T , - , i U • • - U U E S S E T , - , , , . and \JESSETij = {Mitjtl,...MiJ,riJ} • (zmin, y m i n ) and ( x m a x , y m a x ) : S coordinates of diagonally opposite corners of R E C R E G , , where xmax ^ ^min and y m a x ^ ymin • Pthi-: correlation coefficient minimum threshold Output : I D S E T ; : identifier map set such that I D S E T , = {ID,- ,! , . . . , I D j , 9 J Note: the registration feature used in computing correlation coefficients in this procedure is the same one that was used in computing the extent similarity values when M I S E T , - was generated (steps (3.2) and (3.3) in Figure 5.10). (1) For j = (1.1) Allocate ID;,., and R H O j . (1.2) For x = x m j n , . . . , xmax and y = ym\ni • • • •> ymax : (1.2.1) F i n d id such that for k - 1 , . . . , r,-,j pMiih,d,s,x,y > PM,i]ik,s,x,y (1.2.2) If pMiijiid,s,x,y > Pthr then let ID,-j(a; - x m i n , y - ymin) = id and R H O ^ z - z m i n , y - ymin) = pMiJiid,s,x,y; otherwise, let lDij(x - xmin, y - y m i n ) = null and R H O j ( x - xmin, y - ymin) = null. (1.3) Perform non-maximum suppression on R H O j and alter I D , j accordingly. Figure 5.13: Procedure to match image locations and model instances (version 1). Chapter 5. Procedures 66 Input: • 5 , M I S E T , ' , (<Emin> ymin)> (^maxi J/max)> Pthr • dfrac: extent dimension fraction • Psthr-: correlation coefficient minimum threshold for initiating full-resolution search Output : I D S E T ; : identifier map set such that I D S E T ; = { ID; , i , . . . , I D ; , g J (1) For j = 1, . . . ,%: (1.1) Allocate I D t j and R H O j , and initialize ID;,., and R H O j to null at all locations. (1.2) Evaluate dimx and dimy respectively to the overall x-dimension and y-dimension of the U E S S E T i j extent. (1.3) Let dx = m&x(dfrac X dimx, 1) and dy = m&x(dfrac X dimy, 1). (1.4) Let x — xm\n. (1.5) While x < x m a x : (1.5.1) Let y = ymin. (1.5.2) While y < y m a x : (1.5.2.1) F i n d id such that for k - 1 , . . . , r.-j PMiijM,s,x,y > PMiiJik,s,x,y (1.5.2.2) If PM, j ,d,s,x,y > Psthr then perform full-resolution match search for x = x - dx/2,..., x + dx/2 and y — y- dy/2,..'., y + dy/2 (see block (1.2) of Figure 5.13) (1.5.2.3) Let y = y + dy. (1.5.3) Let x = x + dx. (1.6) Perform non-maximum suppression On R H O j and alter I D ; j accordingly. Figure 5.14: Procedure to match image locations and model instances (version 2). Chapter 5. Procedures 67 A further refinement that was investigated was to search the uniform-extent subsets at two levels of resolution. Thi s refinement is incorporated into the final version of the procedure, which is outlined in Figure 5.15. T h e uniform-extent subsets are grouped such that the members of each group represent extents that are approximately similar, within a specified tolerance. T h e groups are not necessarily disjoint sets, and one member of each group is the representative for that group (the definition of the groups will be described later). For each group, matching is first performed with the representative uniform-extent subset (the two-resolution search of the image-space, as described in Figure 5.14, is used). Tests for matches are performed with other members of the group only at those locations where a match was obtained using the representative. A t each location where a match was obtained with an element of at least one member of the group only one match (one that is associated with the maximum corresponding correlation obtained over the group) is retained. Let Ei = {£?,-,!,..., Eitqi} be the set of extents represented by { U E S S E T , - , i , • • •, UESSET,- , , , . } . A n approximately minimal subset E( of E ; is computed such that for any element e of E , there is an element e' of E' t - such that rje>ei > rjgTOUp, where i]STOUp is user specified (but generally greater than the value of ?7adj that was involved in generating the model instance set (c/. Section 5.1.1)). T h e algorithm to find an approximately minimal dominating set of a graph (Figure 5.12) is applied to this task, in the same manner as it is to generate a model instance set (step (3.2) in Figure 5.10). T h e group representatives are those uniform-extent subsets whose extents are in E ' , and the other members of a given group are those uniform-extents subsets with an extent similarity with the representative that is greater than or equal to Tjsroup. T h e registration feature that is used to compute correlation coefficients in the matching procedure and to compute the uniform-extent subset groups and representatives is assumed to be the same registration feature that in used in steps (3.2) and (3.3) of the procedure to model to generate a model instance set (Figure 5.10). Chapter 5. Procedures 68 Input: • S, M I S E T ; , (a: m i n , 7/ m in) , (Zmax ,2 /max), Pthr, Psthr, d / V a C • ny: number of U E S S E T groups • rep: rep[m] is the representative of U E S S E T group m • size: size[m] is the number of members of U E S S E T group m • member: member[m,n] is member n of U E S S E T group m Output: I D S E T ; : identifier map set such that I D S E T ; = { I D t ) 1 , . . . , I D , - i g J (1) F o r i = 1, (1.1) Allocate I D ; j and R H O j , and initialize ID t ) j and R H O j to null at all locations. (2) For m — 1 , . . . , ng: (2.1) Let j = rep[m]. (2.2) Evaluate ID; : j using variable resolution search (see steps (1.2) to (1.4) and block (1.5) in Figure 5.15). (2.3) For n = 1 , . . . , size[m]: (2.3.1) Let k - member[m, n]. (2.3.2) If k 7^ j then check for match with U E S S E T ; ^ at those locations where I D ; j is non-null, and for each such location (x,y) let R H O , , / ^ — xmax,y — y m a x ) — PMiikiid,S,x,y (2.4) For X = X m j n , . . . , Xmax a-nd y = J/min> • • • j Umax-(2.4.1) Search for id such that for k £ {memberfm, 1 ] , . . . , member[m, size[m]]} IDi,,-d(a: - x m a x , V - 2/max) 7^ null and REOid(x - xmAX, y - y m a x ) > RHOfc(x - x m a x , y - y m a x ) . (2.4.2) If id found then for n = 1, . . .,size[m]: (2.4.2.1) Let k = memberfm, n]. (2.4.2.2) If k ^ id then let I D ^ a : - x m a x , y - y m a x ) = null. (3) For j = 1 , . . . , qi perform non-maximum suppression on R H O j and alter I D ; j accordingly. Figure 5.15: Procedure to match image locations and model instances (version 3). Chapter 5. Procedures 69 Input: • U E S S E T : uniform-extent subset • ID: identifier map associated with U E S S E T • R H O : p map associated with U E S S E T • dimx, dimy: x and y dimensions, respectively, of the input maps Output: ID (altered) (1) Allocate dimx-by-dimy map P R O P and initialize to null at all locations. (2) For x = 1 , . . . , dimx — 1 and y = 1 , . . . , dimy — 1: (2.1) If ID(x ,y) ^ null then: (2.1.1) Register the extent of U E S S E T to P R O P ( x , y ) using the centroid as the registration feature. (2.1.2) For all x',y' such that (x',y') is a location in P R O P that coincides with a location in the registered extent: (2.1.2.1) If P R O P ( a ; / , y ' ) = null or P R O P ( x ' , y ' ) < R H O ( z , y ) then let P R O P ( x ' , y ' ) = R H O ( x , y ) . (3) For a: = l , . . . , dimx — 1 and y = 1 , . . . , dimy — 1: (3.1) If ID(z , y) ^ null and R H O ( x , y) < P R O P ( x , y) then let ID(z , y) = null. Figure 5.16: Procedure to perform non-maximum suppression. Chapter 5. Procedures 70 5.4 Evaluation of Correct Recognition Probability T h e probability that an initial recognition instance (or simply 'recognition instance' in the remainder of this section) is correct is evaluated on the basis of features that involve the scene image region that coincides with the extent locations or the direct irradiation locations (c/. Section 4.3) of the matching model instance. Let there be d features. T h e feature values for any recognition instance are formatted into a c?-dimensional feature vector x. Correct and incorrect recognition represent two classes, to which we assign the indices 1 and 2, respectively. T h e correct recognition probability that is computed for x, Px(class 1) (or, equivalently, 1.0—Px(class 2)), is used to classify the associated recognition instance as correct (when Px(class 1) > 0.5) or incorrect (when P x (c lass 1) < 0.5). T h e incorrect recognition instances are then rejected, and the surviving instances (the intermediate recognition instances) are passed on to the conflict resolution filter, along with the associated correct recognition probability values. Samples of correct and incorrect recognition instances with respectively ei and e 2 elements are manually selected from the initial recognition instances. A n estimated probability of correct recognition is assigned to each element of each sample set. T h e feature vector for the jth element of the ith sample (j £ {1 , . . . , e;} and i £ {1,2}) is x( l J ) . T h e estimated probability that x ^ ) represents class k is s;j,A:- Note that s t - j ; 2 = 1-0 — T h e two sample sets may be considered to comprise a single training set of e i + e 2 exemplars. In this context the feature vectors are written with a single index. T h e estimated probability that x ^ represents class j is s ; j . A nearest-neighbours interpolation procedure is used with the exemplars to estimate the probability that an input feature vector x represents correct recognition. Thi s type of procedure was selected because it does not require prior knowledge of the manner in which members of the two classes are distributed in the feature space, and it readily supports the incremental expansion of the set of exemplars. T h e nearest-neighbours interpolation procedure that we use is described in Section 5.4.1. Chapter 5. Procedures 71 T h e selection and definition of features is discussed in Section 5.4.2. 5.4.1 Nearest-neighbours Interpolation T h e performance of nearest-neighbours interpolation with a training set of finite size is sensitive to the weights assigned to the different features in the definition of the metric for the distance between an input vector and elements of the training set (the similarity metric). If features with relatively low class-discriminating power are assigned the same or higher weights as those with relatively high class-discriminating power, then a larger training set is required to obtain the same classification accuracy as is obtained when the low class-discriminating power features are assigned appropriate (relatively low) weights. A larger training set implies a greater data collection burden, greater memory requirements, and more computation in the classification. T h e use of a fixed interpolation kernel in nearest-neighbours interpolation may result in the averaging of too few class probabilities to permit a good estimate of the local Bayes probability in parts of the feature space where the exemplars are sparsely distributed, and poor sensitivity to variations in the distribution in parts of the feature space where the exemplars are densely distributed. These problems are avoided through the use of a variable interpolation kernel that has a width that adapts to the density of exemplars in the feature space in the locality of the input vector. Such adaptation might be achieved by relating the kernel width to the kth nearest-neighbour or to the average distance to the k nearest-neighbours. Lowe's variable-kernel similarity metric ( V S M ) learning procedure (Lowe 1995) uses cross-validation optimization (based on the conjugate gradient optimization technique) to evaluate (1) the similarity metric weights and (2) a constant that relates the average distance to k nearest-neighbours to the width of a variable Gaussian interpolation kernel. T h e objective of cross-validation optimization is to minimize the error resulting when the class probabilities associated with each exemplar are predicted on the basis of the remaining exemplars. T h e V S M learning procedure and the associated nearest-neighbours interpolation procedure was used in Chapter 5. Procedures 72 this work 2 T h e nearest-neighbours interpolation procedure that is associated with V S M learning (Lowe 1995) has the following basis. Let N be the number of nearest neighbours that are included in the interpolation, and n; be a weight that is associated with the z t h nearest-neighbour. A class probability for input vector x is computed according to P x ( c l a s s i ) = % ^ . T h e exemplar weight n t is determined by a Gaussian kernel centred at x and is a function of the distance m; of the neighbour from x: ni = e x p ( - m 2 / 2 ( 7 2 ) . T h e similarity metric is a weighted Euclidean distance metric: d k=i Optimal values for the feature weights wi,..., wj, are computed by the V S M learning procedure. T h e width of the Gaussian kernel is function of a, which is evaluated to a multiple r of the average distance to the M nearest neighbours: M M is evaluated to some fraction of JV. A value for r that is optimal with respect to the overall density of the exemplars within the feature space is computed by the V S M learning procedure. In our 2-class application involving e\ + e2 exemplars, the error E that is minimized by the V S M learning procedure is computed according to: e i + e 2 2 E = E E ( ^ - P x C ) ( c l a s s j ) ) 2 t'=i j=i 2The implementation of the VSM learning procedure and of the nearest neighbours interpolation procedure (which includes an implementation of k-d tree construction and search procedures) that was used in this work was provided by Dr. David Lowe, Department of Computer Science, University of Britsh Columbia. Chapter 5. Procedures 73 where Px(<) (class j) is the predicted probability that the ith exemplar is in class j, based on that exemplar's nearest neighbours among all the other exemplars. T h e N nearest neighbours of an input vector are found using an implementation of the A;-d tree algorithm (Friedman, Bentley, and Finkel 1977). A A;-d tree is essentially a multidi-mensional binary search tree. In this application, the number of search dimensions is equal to the number of features (d). Let T be the number of exemplars in the training set. Fried-man et. al. (1977) show that construction of the k-d tree requires time proportional to dTlogT, and argue that the search for the N nearest neighbours of an input vector has expected time proportional to l o g T . Sproull (1991) presents the results of experiments for different values of k and T , and for both uniformly distributed and clustered vectors. T h e search time was limited to being nearly proportional to l o g T and was nearly independent of N only for small d relative to T (e.g., d < 4 and T > 100), and performance was better for clustered data than for uniformly distributed data. T h e A;-d tree implementation provided reasonable performance in the main experiment (Section 6.7). 5.4.2 Feature Definitions T h e set of features that is used in the nearest-neighbours interpolation is selected from a set of hypothetically useful features on the basis of feedback from the V S M learning procedure. This process is illustrated in Section 6.5. T h e features that we hypothesize are useful in distinguishing correct and incorrect recogni-tion instances fall into the following two classes: • those that are based on the average value of the scene image pixels that coincide with the direct irradiation locations of the matching model instance (the average direct irradiation pixel value), for one or more scene image channels • those that are based on the straight-line least squares regression of scene image pixel values on the values of the coincident matching model instance pixels (the regression of the scene image on the model instance), for one or more scene image channels Chapter 5. Procedures 74 We denote the average direct irradiation pixel value for channel a by Da. T h e reflectance spectra of healthy green leaves (needle and broad) are characterized by local maxima in the visible green and near-infrared (nir) wavelength regions and local minima in the visible blue and visible red wavelength regions (Guyot, Guyon , and Riom 1989). This property allows the directly irradiated portion of healthy leaf-bearing trees to be manually distinguished from most other objects in colour-infrared photographs and colour-composite displays of multispectral digital images, on the basis of colour. Therefore, we hypothesize that Dbluo g^reem A-ed, Aiir, and ratios Dmax-imai/.Dminima> where 'maxima' and 'minima' denote wavelength regions centred respectively on green leaf reflectance maxima and minima, include useful features. T h e regression of the scene image on the model instance incorporates the model instance and scene image pixel values as respectively the independent (X) and dependent (Y a ) variables in the regression, and the values of a coincident pair of pixels as one data point (X; , Y 0 i,-) (the a component in the Y-subscript designates the scene image channel). This corresponds to the view that the model instance is an idealization of the image of a real crown up to, but not including, the application of a uniform gain and offset, and that the departures from the ideal due to such things as shape irregularities and gaps in the foliage comprise a form of noise (the possibility that these factors may provide useful information in the separate problem of species identification is acknowledged). Let n be the number of pixels in the model instance extent. A straight-line least squares regression produces values bafi and ba>i such that T h e channel a coefficient of determination R\ is the ratio of the channel a regression sum Y — 1 a,i — K,0 + ba,lXi and such that the channel a residual sum of squares n is minimized. of squares (SSTeg<a) to the channel a total sum of squares corrected for the mean (SStot,a)'-tot,a Chapter 5. Procedures 75 where n "^Sto^ a = ^ y(^ a,t — ^ a)> i=l n i=l and 1 n = — E ^ M " t=l is restricted to [0,1] and can be interpreted as the fraction of the total sum of squares cor-rected for the mean that is explained by the regression line; it is also the square of the channel a correlation coefficient for the recognition instance. Inspection of high spatial resolution vertical images of forests reveals that the amount of texture in a tree crown image can vary noticeably with species and crown size. R2 should be sensitive to such variation, and we hypothesize that this would limit the usefulness of these values as features for distinguishing instances of the correct recognition of all sorts of tree crowns from instances of incorrect recognition. T h e channel a pure error sum of squares (55err,a) is the variation in the dependent variable that cannot be explained by the regression line (i.e., the variation caused by multiple different values of Ya at the same value of X). A n upper bound on the value of R2 ( i ? m a x a ) can be defined using 5 5 e r r , a as follows: j-,2 (iSiStot.a ~ SSerr<a) '5'-'tot,a If the increase in crown image texture is associated with an increase in SSerr>a, then R2/Rma.*,a (which is restricted to [0,1]) should be less sensitive to species and crown size variation than T h e pure error sum of squares can be estimated on the basis of repeat runs (i.e., repeated measurements of Ya for the same value of X). When there is an insufficient number of true repeat runs to support a reliable estimate of SSerTja, we can use a division of the X-va lue interval into a number of sub-intervals as the basis of an approximation of repeat runs (Draper and Smith 1981, pp. 35-42). Let m be the number of X - a x i s intervals, n; be the number of Chapter 5. Procedures 76 data points in the i interval, and Ya,t',j be the Y a -value of the j data point in the i interval. T h e n , and the estimated value for 5 5 e r r is m rti i=l3=1 When m = 1, the estimate is based on true repeat runs. W h e n n,- = 0, Y 0 i j is undefined and the i t h interval cannot be involved in the estimate. Let X m j n and XmSiX be, respectively, the minimum and maximum values of X{, i = 1 , . . . , n. A measure of the degree of contrast within the channel a scene image region for a recognition instance is Ca = (ba,0 + fra.l^max) — (^ a,0 + a^.l^ rnin) — — a^,l-^ min-We hypothesize that this feature may be useful in distinguishing correct recognition instances from incorrect recognition instances that correspond to image regions that have a crown-like colour, but have shading that is too subtle to be crown-like (e.g., part of a grassy field with local topographic shading variation that causes it to become a involved in an initial recognition instance). A n alternate measure of contrast that does not involve the regression of the scene image on the model instance is Ca = Da — Ia, where Ia is the channel a average non-direct irradiation pixel value. In summary, the hypothetically useful features are the following: £ > a , i)maxima/-Dminima> R2^ ^ a / ^ m a x , o i Ca, and C'a. 5.5 Resolution of Interpretation Conflicts We define the extent of a recognition instance to be the image extent of the positioned matching model instance. T h e initially implemented conflict resolution filter eliminated a recognition Chapter 5. Procedures 77 instance if the centroid location of its extent was within that of a different recognition instance with a greater correct recognition probability value (e.g., Figure 5.17a). Thi s procedure was implemented as a version of the non-maximum suppression procedure outlined in Figure 5.13, with the modifications that it uses the correct recognition probability value associated with a recognition instance rather than the correlation coefficient value, and it operates over all of the indentifier maps. Wi th in the context of the main experiment, this procedure produced reasonable results in some locations, but often failed. T h e following were the most commonly occurring failures: • A conflict in which one or more recognition instances with relatively small extents and high correct recognition probabilities coincided with a single recognition instance with a relatively large extent and low correct recognition probability would not be resolved if the centroid of the large extent happened to fall outside of all the small extents (e.g., F i g -ure 5.17b). • A recognition instance would be eliminated because its extent centroid was within the much smaller extent of a recognition instance with a slightly higher correct recognition probability. In such cases, the recognition instance with the larger extent was often the one that should have been retained. Thi s failure often occurred because small-extent and large-extent model instances would respectively match the tip and the entirety of a conical tree crown (e.g., Figure 5.17c). These failures suggested the need for a broader notion of spatial interaction between recogni-tion instances than whether the extent centroid for one recognition instance is inside or outside of the extent of a different recognition instance, and the need to link the quality of a recognition to more than just the correct recognition probability. This led to the idea of defining the conflict resolution filter to be an optimization procedure that is applied to the intermediate recognition instances on a window-by-window basis. T h e windows are the rectangular cells of a uniform user-specified grid that is superimposed onto the image extent, and they are intended to be large enough to contain several of the largest Chapter 5. Procedures 78 (a) (b) (c) Figure 5.17: Schematic examples of conflict resolution based on non-maximum suppression. T h e dark and light boundaries represent the extents of recognition instances with, respectively, relatively high and low correct recognition probability values. Parts (a) and (c) illustrate the elimination of a recognition instance with a relatively large extent and low recognition probability value. Part (b) represents a small perturbation of the situation represented in Part (a) in which none of the recognition instances are eliminated. tree crown images. Each window is also assigned a surrounding margin of a user-specified width that overlaps the adjacent windows (Figure 5.18). T h e optimization procedure is applied to each window and its surrounding margin (the processing region), but the results are retained only for the windows. Each processing region represents an instance of the optimization problem. T h e optimization is extended into the margins in order to reduce discontinuities in the results at window boundary locations. T h e optimization procedure selects a subset of the intermediate recognition instances that are located within each processing region such that a certain objective function is maximized. Then , the results for each window are integrated into the final set of recognition instances by running them though the initially implemented conflict resolution filter that is described at the beginning of this section. This procedure attempts to remove conflicts that remain along the window boundaries. Although the procedure does not do this perfectly (examples of some failures are discussed and illustrated in Section 6.7.3), the results were found to be noticeably better when the procedure was applied than when it was not. Chapter 5. Procedures 79 ^—window boundary grid j — margin boundary margin ^ WINUUW Figure 5.18: Processing windows and margins for interpretation conflict resolution. T h e objective function F is a weighted combination of three components: F = Wifi + W2f2 + w3f3 where the weights (wi, W2, and w3) are user-specified and the components ( / i , / 2 , and / 3 ) are related to the following aspects of the currently selected set of intermediate recognition instances: fx: the fraction of the processing region that does not coincide with the intersection locations of multiple positioned matching model instances $i: the average correct recognition probability value fy: the fraction of the processing region that coincides with locations within positioned match-ing model instances T h e fi component is intended to control the degree of image-space overlap between posi-tioned matching model instances and is related to the fact that within forest stands the crown Chapter 5. Procedures 80 envelope intersection volume is generally less than the remaining crown envelope volume. T h e relationship is admittedly indirect since the intersections of the image-space projections of tree crowns in the scene do not exactly correspond to the intersections of the tree crown volumes in scene-space. Thi s is particularly so in parts of the image where there is considerable height displacement and occlusion of some tree crown images by others. T h e J2 component is intended to reflect an overall preference for the recognition instances with higher correct recognition probability values, as evaluated by the correct recognition prob-ability filter (cj. Section 5.4). T h e fa component counterbalances the other two components: clearly, the rejection of all of the recognition instances would maximize fy, and the retention of the one recognition instance with the highest correct recognition probability value would maximize f2-5.5.1 Definition of a Processing Region State and the Associated Objective Function Value Let there be m locations, (x\, y i ) , . . . , (xm, ym), within the processing region at which the matching model instances for one or more recognition instances are positioned. We call these the non-null locations. A recognition instance selection that may be made at non-null location (xi,y{) is S%i,Vi ^ { ^ l i . J K )  rxi,yi,\i • • • i  rxi,yi,ni) where {rXi>yiti,..., rXityi<nj} is the full set of nj intermediate recognition instances positioned at (xi,yi), and 0^^ .^ denotes the selection of none of those recognition instances (the null selection). A valid jth state for a processing region during the optimization procedure is a set that represents one recognition instance selection at each of the non-null locations: s j = {sxi,yi,j> • • • i  sxm,ym,j} where sXitVitj is the selection at non-null location (x{,yi) that is associated with the state j. Chapter 5. Procedures 81 T h e values of the objective function and its components for state j are denoted respectively Fj, and / i j , / 2 J , and f3j. T h e expressions for the components of the objective functions involve the following quantities: Nji the total number of non-null selections in S j P(sxi,yi): the correct recognition probability associated with sXiiVi (p{sx„yi) = 0 if 8XitVi = <Dx„y,) Pmax'' max(p (fxi,yi,j) '• rXi,yi,j £ Ufc=l{rxk,yk,l> • • • i rxk,yk,nk}) Pmin : m m ( P ( r i , - , i / i , j ) : rxi,yi,j £ U/s=l { , 11 • • • > rxk,yk,nk }) C J : the number of singly or multiply covered (or, simply, covered) locations in state j, which are the processing region locations that coincide with a location in at least one positioned matching model instance in state j • - > '• cmji the number of multiply covered locations in state j, which are the processing region locations that coincide with a location within the intersection of two or more positioned matching model instances in state j c u b: an upper bound on the number of covered locations in any state, defined by the number of covered locations when all of the recognition instances at all of the non-null locations are selected (this does not represent a valid state since in this case multiple selections may be made at a single non-null location) T h e objective function components for state j are evaluated according to: / '•max Cm; h j = — ' cub (pf/Nj) - p m i n Pmax — Pmin Chapter 5. Procedures 82 T h e value for each component is restricted to [0,1] for any processing region. This helps ensure the applicability of the same set of weights to different processing regions. T h e maximization of F for a particular processing region is an instance of a combinatorial optimization problem. T h e number of possible states grows exponentially with the number of non-null locations. 5.5.2 Initial Optimization Experiments We initially implemented a backtracking procedure to perform the optimization, but found that within the the context of the main experiment, even small processing regions (e.g., 25-by-25 pixels) are almost always associated with too many states to allow the procedure to terminate in a reasonable amount of time (the procedure performs an exhaustive search of the states). Processing regions that are small enough to allow a reasonable execution time (e.g., 10-by-10 pixels) often cannot contain the spatial interactions between multiple large tree crown images, and lead to a significantly increased incidence of window-boundary discontinuities in the results. In the backtracking procedure, each non-null location in a processing region corresponds to a different level in a state-space tree, and the different nodes at a level correspond to the different possible recognition instance selections at the corresponding location. A bounding function was added to the procedure in an attempt to improve the execution time. T h e bounding function is based on the assumptions that at all levels of the tree under the level of the current node there is a recognition instance selection with a recognition probability of 1.0, and that these selections together raise the coverage to cUD without raising the multiple coverage. T h e bounding function returns the value of the objective function under these assumptions. If the bounding function value is less than that of the current largest objective function value then the descendants of the current node are not visited. T h e addition of this bounding function did not shorten the running time of the procedure to a reasonable level. Chapter 5. Procedures 83 A greedy algorithm was also implemented. T h e procedure starts by selecting a recognition instance with the globally maximum correct recognition probability. It then searches for the remaining non-null location and selection selection that produces the maximum increase in the objective function value, and stops when an increase is no longer possible. Wi th in the context of the main experiment the procedure consistently terminated with an obviously poor result. T h e procedure quickly became caught in locations of the state space with locally maximum objective function values. 5.5.3 Optimization by Similated Annealing T h e optimization procedure that was used to produce the results reported in Section 6.7 is based on simulated annealing. T h e following definitions are fundamental to the discussion of our application of this technique: S: the set of all states in a problem instance (a problem instance corresponds to a processing region) s: the state score function, which assigns a real number to a state; if e (s t) < e (SJ) then s,- is considered to be closer to optimum than S j p: the move set; a relation over S (p C S X S) that represents the pairs of elements of S that are connected by a permissable atomic state modification, or move. pk: the pairs of elements of S that are connected by a sequence of k moves (p = p1). (S,p): the state-space a: the acceptance function, which assigns a real number in (0,1] to a pair of scores and a control parameter value; a (e (s,-),e (SJ ) ,£ ) is the probability of accepting a move from state s; to state S j under control parameter value t (3: the selection function, which assigns a real number in [0,1] to a pair of states; j3 (s,-, S j ) is the probability of randomly selecting a move that, if accepted, would cause a transition Chapter 5. Procedures 84 from state st- to state Sj This notation and terminology is taken from Otten and van Ginneken (1989), which is also the main background reference on simulated annealing that was used in this work. In discussions of simulated annealing it is customary to consider the problem to be one of minimization, in other words to find a state s; € S such that V S j eS[e(si) <e (s,)]. Therefore, in our application we equate e (st) and — F,-. A basic simulated annealing algorithm is outlined in Figure 5.19. T h e overall form of the algorithm is an inner loop (block (3.2)) nested within an outer loop (block (3)), with the number of iterations of the inner loop determined in the outer loop. Also, the inner loop contains an implementation of an acceptance function (line (3.2.2)) that involves a pseudo-randomly generated real number from the interval [0,1) (denoted random). T h e control parameter t for the acceptance function is evaluated in the outer loop. T h e probability that Sj will be the next accepted state given that s; is the current state (i.e., the probability of the transition from st- to Sj) is r (s;,Sj,£), where r(si,Sj,t) = a(e (st-),e (SJ), t) (5 (s;, Sj). It is convenient to think of all the transition probabilities for a given value of t as elements of a |S|-by-|S| transition matrix T(t), where T ( i ) t j = r ( s ; , S j , i ) . Clearly, the entries of T(t) are non-negative and the row sums are equal to unity; therefore, T(t) is a Markov matrix, and the sequence of current states generated by the inner loop is a Markov chain. Th i s sequence has the property that the next accepted state does not depend on the states that have preceded the current state. For a given value of t, the transition matrix does not change and that part of the sequence of current states is called a homogeneous Markov chain. T h e conditional probability that Scurr = Sj given that n steps earlier in the same homogeneous Markov chain s c u r r = s; is denoted by rn (s,-,Sj,£). Chapter 5. Procedures 85 Input: (S,/x): the state-space Output : s o p t : the estimated optimum state (1) Initialize K and t. (2) Let stop = F A L S E . (3) While stop ± T R U E : (3.1) Let i = 1. (3.2) While i < K: (3.2.1) A p p l y a random move to s c u r r to get s n e w and let £ n e w = £ ( s n e w ) -(3.2.2) If random < exp( ( e c u r r — £new) A) then: (3.2.2.1) Let sCUrr ~ s n e w and 6 c u r r — £new (3.2.3) Let i = i + 1. (3.3) Update K, and t. (3.4) If the stop criteria are met then let stop = T R U E . (4) Let s0pt — s c u r r . Figure 5.19: Simulated annealing algorithm. Chapter 5. Procedures 8 6 Let the move set have the properties of space connectivity (i.e., any state can be reached from any other state by a sequence of moves) and reflexivity: OO U pk = S x S A:=l and Vsj- G S [(s,-, s,-) G p] Also, let j3 have the following properties: V ( s i , s i ) <E p \fi{si,Sj) / 0] and V(&i,*j))tn\P(si,&j) = 0]. Then for the homogenous Markov chain there exists a probability density function of states S, called the equilibrium density of the chain such that S (sj,t) = lim Tn (si,Sj,t) k—f oo and where the 5 does not depend on s,-. This is the chain limit theorem, which is proved in Chapter 3 of Otten and van Ginneken ( 1 9 8 9 ) . Let us add symmetry to the conditions on p and j3: Vs; G S , V S J G S [(s,-,Sj) G p ->• (sj,s t) G p] and Ys; G S , V S J G . S [/? (s^ S J ) = j3 ( S J , s t)], and let us adopt the acceptance function encoded in Figure 5 . 1 9 : a(e (si),e(sj),t) = m i n { l , e x p ( ( e (s,-) -e(sj))/t)}. T h e n , for a sufficiently high value of t, the equilibrium probability is practically the same for all states, and for a sufficiently low value of t the equilibrium probability is practically zero for all Chapter 5. Procedures 87 states that do not have the globally minimum score (Otten and van Ginneken 1989, Chapter 3). We call a homogeneous Markov chain that satisfies above-specified requirements on fi, a , and (3 an annealing chain. For annealing chains, fewer steps are required to get close to equilibrium (i.e., reach quasi-equilibrium) with a relatively large value of t than with a relatively low value of t. Also, after quasi-equilibrium is obtained for one value of t, relatively few steps are required to re-establish quasi-equilibrium in a new chain for a slightly different value of t whose starting state is the old chain's ending state. T h e central idea of the annealing algorithm, then, is to quickly establish quasi-equilibrium for a high value of t and then re-establish quasi-equilibrium for decreasing values of t until the stopping criteria are met, which should occur when there is little or no decrease in the average score for successive chains. T h e procedures described in Otten and van Ginneken (1989) for initializing t and K (the number of steps to run the current annealing chain through), computing successive values of t and K, and determining when to stop were implemented in our application of simulated annealing. These procedures involve statistics compiled during the inner loop executions that are required to reach quasi-equilibrium for each value of t, and their implementation has been omitted from Figure 5.19. For our application, we define a move as the selection of a single non-null location, followed by a recognition instance replacement at that location. A recognition instance replacement at a particular location is the removal of the previously selected recognition instance followed by the addition of a newly selected recognition instance at that location. In a random move, the location and new recognition instance selections are random. Clearly, the move set has the properties of space connectivity, reflexivity, and symmetry that are required for simulated annealing (space connectivity is satisfied because any final state can be reached from an initial state by transitioning to the state of all null selections, and then making the non-null selections required to establish the final state). T h e required conditions on (5 are trivially satisfied. T h e evaluation of -Fj+i to accompany the transition from Sj to Sj+i requires the evaluation of iVj+i, C j + i , craj+i, and pf+1- This procedure is outlined in Figure 5.20. T h e procedure is Chapter 5. Procedures 88 supported by a coverage count map for the processing region, which is denoted by C O V C N T , and the functions A c r , A c m r , A c a , A c m a . Each location in a coverage count map is evaluated to the number of different positioned matching model instances that contain a coinciding location in the current state. T h e alteration of a coverage count map during a recognition instance replacement is illustrated in Figure 5.21. T h e function A c r returns the reduction in the number of covered locations in the processing region (a number that is less than or equal to zero) when the specified recognition instance is removed from the specified location. T h e function A c a returns the increase in the number of covered locations in the processing region (a number that is greater than or equal to zero) when the specified recognition instance is added to the specified location. T h e functions A c m r and A c m a are similar to A c r and A c a , except that they respectively return the reduction or increase in the number of multiply covered locations. Each of these functions also updates the coverage count map. Note that an implementation of any of these functions needs to scan and modify the coverage count map only within the extents of the removed or added recognition instances. 5.5.4 Summary Interpretation conflict resolution was formulated as a window-based combinatorial optimization problem that involves the spatial interaction between recognition instances as well as the correct recognition probability values. A backtracking optimization procedure that performs an exhaustive search of the states for a processing region (a window plus its surrounding margin) typically required an unreasonable amount of computation for windows that were large enough to contain the spatial interaction between multiple images or large tree crowns. T h e addition of a bounding function to the procedure did not decrease the required amount of computation to a reasonable level. A greedy optimization procedure usually became caught at local objective function maxima within the state-space. A n optimization procedure that is based on simulated annealing had reasonable Chapter 5. Procedures 89 Input: C O V C N T , (x;,y;) sXhyij, sXitViij+1, Nj, pf, CJ, crrij Output: Nj+U pj+ 1 ' cj+i> cmj+i (1) If 8 „ j , w j 7^  0*,,y, then let ctmp = CJ + A c r ( C O V C N T , (xi, y t ) , sXiiyij), and c m t m p = cmj + A c m r ( C O V C N T , (zt-, y t ) , s r j ) 3 / j j ) ; otherwise, let Ptmp = ) Ctmp = Cj, and c m t m p = crrij. (2) If s ;^,</i>j+i 7^  ®xi,yi then let Wj+i = A W + 1, PJ+1 = Ptmp + P(Sx„yt,j + l), Cj+i = ctmp + A c a ( C O V C N T , (xi, yi),sXiiyitj+1), and c m j + i = c m t m p + A c r a a ( C O V C N T , (a;,-, y t ) , s^^.j+i); otherwise, let Aj+l = A^ tmp, = Ptmp' CJ+I = c t m p , and c m J + i = c m t r n p . Figure 5.20: Procedure to update the objective function data to reflect the replacement of sxi,yi,j+i at location (x;,y;). Chapter 5. Procedures 90 Figure 5.21: Alteration of a coverage count map during a recognition instance replacement: (a) states of the coverage count map, and (b) initial and final coverage classes. execution times for adequately large processing regions, and was used to produce the results that are reported in Section 6.7. Chapter 6 Experiment This chapter is organized as follows: Section 6.1 describes the experimental image data and the reference data. Section 6.2 describes the manual tree crown recognition experiment, the results of which were compared to the automatic tree crown recognition results. Section 6.3 describes the evaluation of the inputs to the model instance set generation pro-cedure. Section 6.4 describes the evaluation of the adjustable parameters of the initial matching pro-cedure: pthr, Psthr, dfrac, and ^group-Section 6.5 describes the selection of the training set and the features that were used in estimating the probability of correct recognition. Section 6.6 describes the evaluation of the adjustable parameters to the conflict resolution procedure. Section 6.7 presents an assessment and analysis of the automatic tree crown recognition and diameter estimation results. 91 Chapter 6. Experiment 92 6.1 Data T h e experimental image data were acquired from an aircraft with the M E I S II in two flightlines over the P N F I research forest near Chalk River, Ontario, C a n a d a ( 4 6 ° 0 0 ' N ; 7 7 ° 2 5 ' W ) on the morning of 16 August 1988. T h e scene terrain has low relief. Basic flight parameters from the flight report are listed in Table 6.1. F L I G H T L I N E A L T I T U D E A Z I M U T H G R . S P E E D T I M E ( G M T ) (metres agl) (degrees) (metres/sec) Start E n d Sturgeon 518 321 82.8 13:58:33 14:01:59 Headquarters 518 277 79.7 14:11:52 14:13:46 Table 6.1: Flight parameters for the M E I S II data acquired over the P N F I research forest on 16 August 1988. T h e geographic coordinates of the flightline extrema were estimated by locating them on 1:25,000 scale National Topographic Series map sheets. T h e sun positions corresponding to the flightline location and time extrema were calculated using the method described in Chapter 1 of Iqbal (1983). T h e solar declination value for 16 August 1988 o f + 1 3 ° 4 4 ' 2 0 . 8 " listed in Section C of The Astronomical Almanac for the Year 1988 was used in the calculation. These results are listed in Table 6.2. L O C A T I O N L A T I T U D E L O N G I T U D E S U N A Z I M U T H S U N Z E N I T H Z (degrees) (degrees) Sturgeon Start 4 5 ° 5 6 ' 5 2 " N 7 7 ° 2 0 ' 4 6 " W 111.93 52.03 Sturgeon E n d 4 6 ° 0 0 ' 5 5 " N 7 7 ° 2 5 ' 2 0 " W 112.71 51.55 Headquarters Start 4 5 ° 5 9 ' 3 4 " N 7 7 ° 2 2 ' 4 5 " W 115.08 49.94 Headquarters E n d 4 5 ° 5 9 ' 5 9 " N 7 7 ° 2 7 ' 3 5 " W 115.90 49.42 Table 6.2: Estimated coordinates of flightline extrema and the calculated sun position at those locations at the time of imaging. Meteorological data collected at P N F I near the time of image acquisition and obtained from the Canadian Atmospheric Environment Service indicate a ground level visibility of 24.1 km, no cloud cover, and a ground level windspeed between 13 and 11 k m / h r . Iqbal (1983, p. 119) lists horizontal ground level visibility values of 340, 28, and 11 km and indicative of "clean", Chapter 6. Experiment 93 "clear", and "turbid" atmospheres, respectively. 6.1.1 Image Data Table 6.3 lists the wavelength bands in which the experimental image data channels were sensed. Pixel values for each channel are represented by 8 bits. M E I S II C E N T R E W A V E L E N G T H S I G N I F I C A N C E C H A N N E L W A V E L E N G T H (pm) R A N G E (/zm) 7 0.4489 0.4336-0.4642 chloropyhll abs. peak 8 0.5484 0.5325-0.5643 chlorophyll refl. peak 4 0.6402 0.6217-0.6587 chlorophyll abs. peak 2 0.6751 0.6553-0.6949 leaf refl. slope peak 3 0.8734 0.8461-0.9007 leaf refl. peak 6 1.0175 0.9628-1.0722 leaf refl. peak Table 6.3: Channel descriptions for the M E I S II data acquired over the P N F I research forest on 16 August 1988. Channel 6 was not made available to this experiment because its quality was considered to be too low for it to be usable. Visual inspection of the displayed data shows that channels 3 and 8, which respectively correspond to near-infrared and visible green wavelength bands, have noticeably better contrast and less noise than the other channels. Channel 8 exhibits greater contrast within individual tree crown image regions than channel 3, which is to be expected since individual leaves generally have higher transmittance in the near-infrared wavelength region, as pointed out in Section 4.2.2. Pixel value frequency histograms were compiled for each of the image data channels (Fig-ure 6.22)'. T h e histogram for each channel represents the same 24 320-by-320 pixel image regions. Each image region is centred on a different ground sample plot (cf. Section 6.1.2). These sample plots are distributed throughout both flightlines (cf. Section 6.7). T h e frequency histograms show that the sampled pixel values in all channels are concen-trated in the lower half of the [0, 255] range. T h e peaks at pixel value 255 are evidence that there were bright objects in the scene that saturated the sensor. In all of the bands tree crowns are generally not the brightest objects (some areas of exposed soil and pavement were brighter), Chapter 6. Experiment 94 CHANNEL 2 - range: [0..255], mean: 26.9, a.d.: 25.7 CHANNEL 3 - range [0..2S5J, mean: 55.8, s.d.: 27.8 pixel value pixel value 100 150 pixel value CHANNEL 7 35000 range: (0..255], mean: 54.8, s.d.: 22.4 Figure 6.22: Pixel value frequency histograms for the M E I S II image channels. Each histogram is computed for the same 24 320-by-320 pixel image regions. Each image region is centered on a different ground sample plot. Chapter 6. Experiment 95 so the tree crowns are effectively imaged with 7 bits of precision. T h e nominal along-scanline pixel ground dimension is 0.364 m for both flightlines. This estimate is based on the nominal flight altitude above ground level (Table 6.1) and the M E I S II focal length and output pixel image-plane dimension (McCol l , Neville, and T i l l 1983). T h e nominal along-flightline pixel ground dimension is 0.414 m and 0.398 m for the Sturgeon and Headquarters flightlines, respectively. These estimates are based on the data used to estimate the along-scanline dimension, the nominal flightline ground speed (Table 6.1), and a detector array scan rate of 200 Hz for both flightlines. T h e image data were acquired without real-time aircraft roll correction (a M E I S II system option), and no geometric post-processing was applied to them. T h e orientation angles of an inertial navigation system (INS) that was mounted in the aircraft were sampled during image acquisition. T h e INS was not attached to, or precisely aligned with, the sensor head, so the measured orientation angles were not necessarily those of the sensor coordinate frame. However, the INS was only about 2 m away from the sensor head, so relative orientation variation due to airframe flex was negligible. Table 6.4 lists the INS orientation angle standard deviations for portions of the full-flightline images that encompass the sample plots (the sample plots are discussed in Section 6.1.2). Reliable data on groundspeed and height variation are not available. F L I G H T L I N E # S A M P L E S R O L L cr P I T C H a A Z I M U T H a Sturgeon 8883 0.407 0.359 0.200 Headquarters 6285 0.416 0.393 0.399 Table 6.4: Standard deviations (in degrees) of INS orientation angles for flightline intervals that encompass the sample plots. Under the assumption that the x s y s -p lane was horizontal at the mean roll and pitch angle for the INS, then the maximum angle between the optical and vertical axes for the Sturgeon and Headquarters flighlines was respectively 1 . 7 1 7 ° and 0 . 9 2 5 ° . T h e image data were processed at P N F I in order to remove dropped scanlines (image rows correspond to scanlines), and remove some column striping. Also, an additive along-row pixel value adjustment was applied in order to reduce a gradation in average column image intensity. Chapter 6. Experiment 96 This gradation was caused by along-scanline local view direction variation combined with flight directions that were not oriented exactly along the solar azimuth. Image regions corresponding to red pine stands were delineated, and for each region the mean pixel value in each band and the image location of the centroid was computed. T h e adjustment for each band was based on a quadratic least squares regression of region mean pixel value on region centroid scanline position. T h e adjustment was less than 10 pixel value increments for all bands. Although not required for this research, the adjustment was considered to be beneficial to manual image interpretation involved in other research that used these data. T h e image data pre-processing procedures are described in further detail in Cloney et. al. (1994). 6.1.2 Reference Data During the periods of M a y to October 1989 and M a y to August 1990 various attributes of a sample of 587 overstory trees that were distributed among twenty-four 20-by-20 metre square sample plots in the scene were evaluated in the field by P N F I personnel. These attributes are (1) species, (2) stem diameter at breast height (dbh), (3) horizontal crown diameter, (4) tree height, (5) dominance, (6) crowding, and (7) species context. T h e dbh was measured to the nearest 0.1 cm. T h e horizontal crown diameter was evaluated as the average of the maximum north-south and east-west horizontal crown dimensions and recorded to the nearest 0.1 m. Tree height was evaluated to the nearest 0.1 m. Dominance was evaluated as dominant (crown clearly higher than those of neighbouring trees) or co-dominant (crown in overstory but not clearly higher than those of neighbouring trees). Crowding was evaluated as low (tree fairly open growing and not competing with neighbours), medium (tree in light competition with neighbours), or high (tree in contact with neighbours on all sides). Species context (a measure of the species mixture of the overstory canopy in the neighbourhood of the sample tree) was evaluated as either purely softwood, a mixture of softwood and hardwood with softwood predominant (softwood/hardwood), a mixture of softwood and hardwood with hardwood predominant (hardwood/softwood), or purely hardwood. Chapter 6. Experiment 97 P N F I personnel manually estimated the crown apex image location for 548 of the sample trees (these locations were confirmed through field visits with hardcopies of the image data) the image extents of the crowns of 539 of the sample trees, and the image location of each corner of each sample plot. T w o of the apex locations correspond to multiple sample trees (4 each). A l l the other apex locations have a one-to-one correspondence with sample trees. In a display of the image data, understory trees can be manually detected through gaps in the upper canopy stratum within each sample plot. P N F I personnel estimated the crown apex image location for these visible understory trees, and for trees having a stem location outside of any plot and a crown extent intersecting a plot boundary (border trees). Th i s produced a total of 203 additional crown apex image locations. Attributes were not evaluated for any of the visible understory trees or border trees. T h e reference data collection procedure is described in further detail in Cloney et. al. (1994). A reference display was created for each of 24 sample plots by overlaying in white the estimated apex locations of the sample trees, visible understory trees, and border trees, and the estimated sample tree crown boundaries onto a 100-by-100 pixel channel 8 subimage centered on the sample plot. T h e reference displays were used in assessing the accuracy of the results produced by the recognition procedure (the accuracy assessment procedure is described in detail in Section 6.7). 6.2 Manual Recognition Experiment A n assessment of the accuracy of manual recognition for 15 of the sample plots was performed at P N F I . This includes, for each sample plot, the average number of omission errors and the average number of commission errors over 5 different interpreters who worked independently of one another. These data for 14 sample plots are tabulated in Section 6.7.1, where they are compared to automatic recognition results. T h e source of the manual recognition results and the following outline of the experimental procedure is Cloney and Leckie (1995). Chapter 6. Experiment 98 Four of the interpreters had extensive experience in forest inventory photo-interpretation and the remaining interpreter was a forestry student with little photo-interpretation experience. Each interpreter used the same workstation display of the same three-channel colour composite of sample plot subimages drawn from the experimental image data (linearly scaled versions of channels 3, 7, and 4 assigned to the red, green, and blue display coordinates, respectively). T h e colour composite was designed to also support an experiment in manual species discrimi-nation. T h e workstation supported continuous zooming and roaming of the display. A l l of the interpreters were given the same orientation resentation in which they were introduced to the display equipment and shown some examples of correct crown recognition. T h e interpreters were required to record the pixel location of the estimated centroid of each identified tree crown's image extent. T h e sample plot subimages were partitioned into three subsets and a different pixel size was used in displaying each subset. T h e subimages for six of the plots were displayed with the original pixel dimension. T h e subimages for two of the plots were displayed with pixels having half the side-dimension of the original, and the subimages for the remaining seven plots were displayed with pixels having twice the side-dimension of the original (in all cases cubic-convolution resampling was used). T h e pixel size variation was considered to have a minor effect on the manual recognition results. Border trees and visible understory trees (c/. Section 6.1.2), as well as visible ground vege-tation were masked-out in the sample plot subimage, and the interpreters were told to ignore the masked-out areas. 6 . 3 Evaluation of Inputs to Model Instance Set Generation This section describes the application of the procedure outlined in Section 5.1.1 to the experi-mental scene and image data. T h e results are summarized in Section 6.3.6. Chapter 6. Experiment 99 6.3.1 Definition of Constraints on the Locally Variable Parameters T h e scene is part of the Middle Ottawa Forest Section of the Great Lakes-St. Lawrence For-est Region (Rowe 1972, pp. 100). In this Forest Section, upland forests are usually com-posed of sugar maple (Acer saccharum Marsh. ) , American beech (Fagus grandifolia E h r h . ) , yellow birch (Betula alleghaniensis Britton), red maple (Acer Rubrum L . ) , eastern hemlock [Tsuga canadensis (L.) Carr . ] , eastern white pine (Pinus strobus L . ) , and red pine (Pinus resinosa A i t . ) . Forests on dry ridges and sand flats.are usually composed of eastern hemlock, eastern white pine, and jack pine (Pinus banksiana Lamb. ) . Varying amounts of white spruce [Picea glauca (Moench) Voss], balsam fir [Abies balsamea (L.) Mil l . ] , trembling aspen (Polpu-lus tremuloides Michx. ) , white birch (Betula papyrifera Marsh . ) , red oak (Quercus rubra L . ) , and basswood (Tilia americana L.) are present throughout both of these general forest types. Swamp forests are common, and they are usually composed of eastern white cedar (Thuja occidentalis L . ) , eastern larch [Larix laricina (Du Roi) K . K o c h ] , black spruce [Picea mari-ana (Mill.) B.S.P. ] , black ash (Fraxinus nigra Marsh. ) , red maple and white elm (Ulmus amer-icana L . ) . Descriptions of crown form in Hosie (1969) and Sayn-Wittgenstein (1978) for these tree species were compared to plots of a generalized ellipsoids that were computed from different parameter values in order to obtain the following constraints on tree crown size and shape shape for the overall scene. Table 6.5 lists the identified constraints on ( | , n ) , which defines the crown envelope shape. Table 6.6 lists the identified constraints on (6, | , n), which defines the crown envelope size and shape. id a b n 1 8.0 - 10.0 1.0 - 1.5 2 4.0 - 6.0 1.0 - 1.5 3 2.0 - 4.0 1.5 - 2.0 4 1.0 - 2.0 2.0 - 2.5 Table 6.5: Crown envelope shape intervals. Chapter 6. Experiment 100 6 (metres) shape id 1.0 - 2.0 2.0 - 4.0 4.0 - 6.5 1 . 2 . 3 2 . 3 . 4 4 Table 6.6: Crown envelope size and shape intervals. A n overall horizontal radius range of 1.0 m to 6.5 m was obtained by manually inspecting the image data. T h e shape with id = 1 (c/. Table 6.5) is restricted to black spruce which has an exceptionally narrow (b < 2 m) elongated crown. T h e largest crowns (b > 4 m) belong to species for which the sun crown is characteristically parabolic or slightly flat-topped (eastern white pine, eastern hemlock, red pine, yellow birch, and sugar maple). T h e following are the constraints that were identified for the remaining locally variable parameters: • Xend: 0.7 X min(6, 3.0 m) < Xend < 1.0 X min(6,3.0m) • ^max: 0.2 X X e n d < m^ax < 0.5 X Xend • J D a v g : 0.5 m - 1 < A w g < 3.0 m - 1 • A W (1-5 X A v g ) < Anax < (4.5 X A v g ) • k: 0.75 < k < 1.00 • B: 0.20 < B < 0.50 (full parameter descriptions are given in Section 4.3). T h e choice of the constraints on the permeable-volume model parameters related to tree crown composition was guided by the following information: • Average projected one-sided leaf area density values of 1 . 5 m 2 / m 3 (for a Norway spruce) and 1.86 m 2 / m 3 (for an unspecified coniferous species) are quoted in Oker-Blom and Kellomaki (1982) and Kuuluvainen and Pukkala (1989), respectively. Chapter 6. Experiment 101 • In Koppel and O j a (1984) the average one-sided (not projected) leaf area density for an entire Norway spruce crown is given as 5.6 m 2 / m 3 , the maximum depth of the live foliage is given as 2.5 m, the density value for the portion of the crown above the height where the non-foliated inner region disappeared is given as 1 7 m 2 / m 3 , or 3.0 times the whole crown average, and the average for the sun crown is given as 8 m 2 / m 3 , or 1.4 times the whole crown average. • In Wang et al. (1990) it is reported that the maximum leaf area density for a sample of radiata pine trees was up to 4 times greater than the average for the entire crown, and that the peak of the average (over the vertical crown extent) horizontal radial leaf area density distribution tended to occur between one-third and one-half of the crown radius in from the crown surface. T h e constraint for B was based on a sample of ratios of canopy gap image region pixel values to tree crown image region average pixel values (in the M E I S II, the gain for each channel is selected by the operator, but the only offset is a real time subtraction of dark current values from detector outputs). T h e pixels were manually selected from the channel 8 (green wavelength band) image and were restricted to locations near the middle image column. Pixels near the edge of tree crown image regions where foliage gaps are evident were avoided. A constraint for the k parameter of the opaque surface model cannot be derived from measurements of physical tree crown characteristics. For values of k that are less than 1 and incident angles greater than zero, the value of the Minnaert reflectance function (Equation 4.8) increases without bound as the exitant angle increases from 0 and approaches | . When the projection vector is vertical and the x s y s -plane is horizontal, this causes brightening at and near the edge of the direct irradiation extent of opaque surface model instances for values of n greater than 1. For k less than 0.75 the appearance of the edge brightening effect is clearly unrealistic in model instances that are generated with the other parameters evaluated to the test values. Therefore, 0.75 was selected as the low limit for k. Chapter 6. Experiment 102 6.3.2 Pattern Correlation Sensitivity Tests T h e pattern correlation for pairs of different tree crown image model instances was computed in a series of tests in order to support the following investigations: 1. quantify the sensitivity of model instance pattern to full-scene variation and measurement error in 8S, fa, fa, and K, and of variation in the locally variable parameters within the specified constraints 2. compare the pattern variation that is possible with the permeable volume model to that which is possible with the opaque surface model within the specified parameter constraints For all tests, certain sensing geometry parameters were evaluated as follows: / = 0.02461 m, p = 1.729 x 10~ 5 m, H = 518 m, 7 = 0 . 0 ° , f3 = 0 . 0 ° , fa = 2 7 7 ° , dr = 0, and dc = 0. T h e specified values for 7, /3, dr, and dc imply a horizontal a: sy s-plane and a vertical pro-jection vector. Consequently, two model instances that were generated from these values and from the same value for b had the same extent and apex location, which permitted the compu-tation of their pattern difference. Also, a horizontal x s y s -p lane and a vertical projection vector permitted the effect of a change in the value of fa to be simulated with a change in the value of fa. T h e specified values for H and fa were taken from the Headquarters flightline flight pa-rameters (see Table 6.1). T h e values for / and p are those that are specified for the M E I S II (McCol l , Neville, and T i l l 1983). Tables 6.7 and 6.8 list parameter values on which the tests were based. For convenience, the pair (a, n) is treated as a single locally variable parameter in the tests. A range of natural variation or natural variation and measurement error, depending on the parameter, is defined by the low and high values. T h e parameter descriptions and value units are given in Section 4.3. T h e intermediate test values for 8S and fa are averages of the Headquarters flightline extrema values for those parameters (see Table 6.2). T h e difference between the 8S extrema values is 0 . 5 2 ° , and we assume that the precision of the calculation of 8S from the specified image Chapter 6. Experiment 103 test param. low intermediate high 48.42 49.68 50.94 113.07 115.49 117.91 K 0.00 0.10 0.40 -Davg 0.50 1.75 3.00 m^ax 1.50 x jD a v g 3.00 X Davg 4.50 X .DaVg 0.20 x Xend 0.35 x Xend 0.50 X Xend B 0.20 0.35 0.50 k 0.75 0.88 1.00 Table 6.7: Test parameter values that are independent of horizontal radius. low intermediate high 6 = 1.00 23 extent pixels) (a,n) (1.00,2.00) (4.50,1.50) (10.00,1.50) e^nd 0.70 0.85 ' 1.00 b = 3.00 (220 extent pixels) (o,n) (3.00,2.00) (12.00,2.00) (18.00,1.00) -^ end 2.00 2.50 3.00 b = 6.50 (1020 extent pixels) (o,n) (6.50,2.00) (9.75,2.00) (13.00,2.00) e^nd 2.00 2.50 3.00 Table 6.8: Test parameter values that are dependent on horizontal radius. Chapter 6. Experiment 104 acquisition times is within ± 1 . 0 0 ° of the actual values. These considerations lead to high and low values for 9S of 4 9 . 6 8 ° ± 1 . 2 6 ° . T h e difference between the fa extrema values is 0 . 8 2 ° , and we assume that the precision of the calculation of fa from the specified times is within ± 1 . 0 0 ° of the actual values. Furthermore, we estimate that practically all (99%) of the variation in fa to be within ± 2 . 5 4 X 0 . 3 9 9 ° « ± 1 . 0 1 ° of 2 7 7 ° on the basis of the standard deviation for fa, which is listed in Table 6.4. These considerations lead to high and low values for fa of 115.49 ± 2 . 4 2 ° . These ranges for 6S and fa are greater than those that are estimated for the Sturgeon flightline by similar reasoning. T h e choice of the test values for K was guided by the following information: • on a clear day in August 1973 near Nunn Colorado with a 5 0 ° solar zenith angle, Oliver at al. (1975) measured K to be 0.125 in a wavelength band centred at 0.51 firn, • Fraser et al. (1975) state that shortwave noontime clear sky values for K may reach 0.40, depending on location and season. For each test value for b and each test parameter other than b, a model instance pair was generated that represented the high and low values for that parameter and the intermediate values for the other parameters. T h e pattern correlation for the permeable volume model instance pairs and the opaque surface model instance pairs are listed in Tables 6.9 and 6.10, respectively. These tables also rank the pattern correlation values from lowest to highest. Table 6.9 shows that for b = 3.00 and b = 6.50, the pattern differences caused by the variation in 0 S, fa, and K were less than those caused by the variation in any one of the locally variable permeable volume model parameters other than B. For b = 1.00, the Xend-variation as well as the B-variation caused less pattern difference than the error variation in 6S, fa, and K. Table 6.10 shows that for all values of b, the pattern differences caused by the variation in 9S, fa, and and K were less than those caused by the variation in any one of the locally variable opaque surface model parameters. For each test value for b, the pattern correlation was computed for all pairs of different model instances representing all combinations of high and low test values for more than one locally Chapter 6. Experiment 105 test par am. b = 1.00 b = 3.00 b = 6.50 P rank P rank rank 1.000 8 1.000 9 0.999 9 0.994 4 0.994 6 0.995 6 K 0.995 5 0.997 8 0.997 8 (a,n) 0.920 2 0.925 4 0.973 4 a^vg 0.826 1 0.916 3 0.949 3 m^ax 0.995 5 0.859 2 0.906 2 e^nd 0.998 7 0.970 5 0.980 5 0.957 3 0.743 1 0.829 1 B 0.996 6 0.996 7 0.996 7 Table 6.9: Pattern correlation for high and low parameter value instances of the permeable volume model, ranked from lowest to highest with the ranks associated with locally-variable parameters in bold print (non-test parameters for each model instance pair were assigned the respective intermediate values). test param. b = 1.00 b = 3.00 b = 6.50 P rank P rank P rank es 1.000 5 1.000 5 0.999 4 <f>s 0.995 3 0.995 3 0.996 3 K 0.999 4 0.999 , 4 0.999 4 (a,n) 0.918 1 0.918 1 0.972 2 k 0.979 2 0.952 2 0.961 1 Table 6.10: Pattern correlation for high and low parameter value instances of the opaque surface model ranked from lowest to highest with ranks associated with locally-variable parameters in bold print (non-test parameters for each model instance pair were assigned the respective intermediate values). Chapter 6. Experiment 106 variable parameter. For the permeable volume model, sets of 2 to 6 locally variable parameters were involved in the test, with each set consisting of the locally variable parameters associated with the lowest pattern correlation values in Table 6.9 (the opaque surface model has only two locally variable parameters if (a,n) is treated as a single parameter). Summaries of the results for the permeable volume model and the opaque surface model are listed in Tables 6.11 and 6.12, respectively. p b= 1.00 6 = 3.00 b = 6.50 lowest 2 (4 instances, 6 pairs) min 0.476 0.614 0.749 max 0.943 0.998 0.998 avg 0.777 0.807 0.875 lowest 3 (8 instances, 28 pairs) min 0.350 0.523 0.690 max 0.969 0.997 0.998 avg 0.784 0.814 0.881 lowest 4 (16 instances, 120 pairs) min 0.340 0.315 0.611 max 0.994 0.997 . 0.998 avg 0.795 0.761 0.872 lowest 5 (32 instances, 496 pairs) min 0.330 0.243 0.550 max 1.000 1.000 1.000 avg 0.801 0.766 0.874 all 6 (64 instances, 2016 pairs) min 0.223 0.231 0.514 max 1.000 1.000 1.000 avg 0.793 0.768 0.874 Table 6.11: Summaries of the pattern correlation values for all pairs of different permeable volume model instances drawn from the set of instances representing all combinations of high and low test values for the 2 to 6 locally-variable parameters associated with the lowest pattern correlation values in Table 6.9 (non-test parameters for each model instance pair were assigned the respective intermediate values). T h e comparison of Tables 6.11 and 6.12 with Tables 6.9 and 6.10, respectively, shows that for both versions of the tree crown image model, covariation of the values of two or more locally variable parameters can cause larger pattern differences among model instances than variation Chapter 6. Experiment 107 p b= 1.00 b = 3.00 b = 6.50 min 0.894 0.878 0.921 max 0.987 0.996 0.972 avg 0.931 0.921 0.957 Table 6.12: Summaries of the pattern correlation values for all 12 pairs of different opaque surface model instances drawn from the set of 4 instances representing all possible combinations of high and low test values for (a, n) and k (non-test parameters for each model instance pair were assigned the respective intermediate values). in the value of any single parameter. For each test value for b and both versions of the tree crown image model, pattern correlation values were computed for model instances generated with the extreme test values for (9s,fa) and the intermediate test values for the other parameters (Table 6.13). b 1.00 3.00 6.50 perm. P 0.988 0.988 0.990 opaq. P 0.989 0.990 0.991 Table 6.13: Pattern correlation values for permeable volume model (perm, p) and opaque surface model (opaq. p) instances generated with extreme test values for (9s,fa): (48.42,113.07) and (50.94,117.91). Parameters other than #s, <f>s, and b,were assigned the respective intermediate test values. Table 6.13 shows that the pattern differences caused by natural variation and estimated measurement error in 9S, fa, and fa over the full Headquarters scene were less than those caused by variation in the values of most of the individual locally variable parameters (cf. Tables 6.9 and 6.10) and covariation of two or more locally variable parameters (cf. Tables 6.11 and 6.12). Table 6.14 lists pattern correlation values for model instance pairs consisting of a permeable volume model instance and an opaque surface model instance. T h e pattern correlation values in Table 6.14 are grouped according to the values of D a v g , D m a x , X m a x , and k that the model instances were generated from. Opaque surface model instances generated from either the high or low test value for k have a relatively high pattern correlation (consistently greater than 0.9) with permeable volume model instances that represent a high density of scattering elements close to the surface of the crown envelope, which are generated from high test values for D a v g Chapter 6. Experiment 108 and Z ) m a x and the low test value for X m a x . However, permeable volume model instances that represent a low density of scattering elements far from the surface of the crown envelope, which are generated from low test values for D a v g and D m a x and the high test value for Xmax, have a relatively low pattern correlation (consistently less than 0.9) with opaque surface model instances generated with either the low or high test value for k. These results show that when the values of locally variable parameters are restricted to the specified constraints, the patterns that are produced with the opaque surface model are nearly subsumed by the patterns that are produced by the permeable volume model. (a,n) b= 1.00 b = 3.00 b = 6.50 high D a V g , high D m a x , low X m a x ; high k low 0.957 0.952 0.950 inter. 0.951 0.927 0.941 high 0.933 0.936 0.938 high D a v g high D m a x low Xmax; low k low 0.967 0.983 0.985 inter. 0.947 0.976 0.987 high 0.933 0.956 0.988 low D a v g , low D m a x , high Xmax; high k low 0.525 0.741 0.902 inter. 0.542 0.818 0.894 high 0.508 0.767 0.867 low D a v g , low D m a x , high Xmax: low k low 0.368 0.607 0.847 inter. 0.433 0.785 0.876 high 0.584 0.607 0.884 Table 6.14: Correlation coefficients for pairs of permeable volume model and opaque surface model instances with the same extents (parameter values not given in the table are intermedi-ate) . Figure 6.23 illustrates the basic differences between the two versions of the tree crown image model, and helps to explain the test results in Table 6.14. In the permeable volume model instance the non-directly irradiated portion of the extent is brighter because of penetration of light through the crown, and the modelled radiance near the edge of the extent falls off because of a decrease in light scattering element area density. Permeable volume model instances can Chapter 6. Experiment 109 be generated so that they are more like opaque surface model instances by increasing the scattering element area density and concentrating it closer to the surface of the crown envelope. This reduces the light penetration through the crown and the crown edge reflectance fall-off. However, the opaque surface model cannot model any amount of light penetration through the crown or crown edge reflectance fall-off. (a) (b) (c) Figure 6.23: Tree crown model instances generated with intermediate test parameter values: (a) opaque surface version, (b) permeable volume version (c) direct irradiation locations. 6.3.3 E v a l u a t i o n o f 62 a n d T?. T h e desired precision for estimates of the radius of the largest crowns was evaluated to 0.75 m, and 7/acjj was evaluated to 0.78 according to Equation 5.11. T h e minimum 6-value increment was evaluated to 1.5 pixels, or 1.5 X 0.364 m = 1.09 m and, using the algorithm described in Figure 5.11, the sequence of b-values and associated 77-values listed in Table 6.15 was computed. i 1 2 3 4 5 6 7 8 9 10 bi (metres) 1.00 1.55 2.09 2.64 3.18 3.73 4.28 4.84 5.48 6.21 m 0.65 0.74 0.79 0.83 0.85 0.87 0.88 0.88 0.88 0.88 Table 6.15: Sequence of 6-values and associated 77-values computed from 77acH = 0.78, ( A 6 ) m i n = 1.5 x 0.364, 6 m i n = 1.00, and bmax = 6.50. Chapter 6. Experiment 110 6.3.4 Evaluation of paiff} 55E , and 5 5 M A set of 11 subimages centred on tree crown images with exceptionally regular appearance and representing a variety of sizes and column offsets was manually selected from the Headquarters flightline channel 8 image. Channel 8 (the visible green wavelength channel) was selected because it is one of the two channels that exhibits the least visible noise and greatest contrast, and the other such channel (channel 3, the near-infrared wavelength channel) exhibits less contrast within crown image regions than does channel 8. T h e tree crown apex location within each subimage and the crown radius was manually estimated. T h e procedure described in Figure 5.10 was used to generate a model instance set (a set of uniform-extent subsets) for each of the column offset-based recognition regions containing the sample tree crown images. Only the permeable volume version of the crown image model was used. In the generation of each model instance set, input parameters of the procedure were evaluated as follows: • Pdiff =1-0 • dT = 0 and dc to the value corresponding to middle column of the column offset-based recognition region (cf. Section 6.3.5) • b{ and r/; to values from Table 6.15 that bracket the estimated crown radius for the sample tree images within the recognition region • /, p, H, 7, /3, and fa to the fixed test values specified in Section 6.3.2 • 0S, fa, and K to the intermediate test values specified in Section 6.3.2 • the constraints on locally variable parameters to the overall scene values specified in Section 6.3.1 For each model instance set, the procedure was run with different values for 55E (in incre-ments of 10) and 5 5 M = 1 in order to estimate the minimum value at which the subsets E ' of E (cf. step (3.2) of Figure 5.10) are of maximum size for the given inputs. Thi s produced an Chapter 6. Experiment 111 estimate of 5 5 E = 60. T h e procedure was then run with 5 5 g = 60 and different values of 5 5 M (in increments of 10) in order to estimate the minimum value at which the subsets M ' of M (cf. step (3.4.4) of Figure 5.10) are of maximum size for the given inputs (for pdiff = 1-0 this is the point where M begins to contain non-random duplicate model instances). This produced an estimate of 5 5 M = 150. Mode l instance sets that were generated with 5 5 E = 60 and 5 5 M = 150 were used to derive a working value for /Miff- For each sample tree crown image, the uniform-extent subset that best coincided with the tree crown image extent (with the crown apex as the registration feature), was manually selected and the correlation coefficient for the tree crown image and each of the 150 elements of the uniform extent subset was computed. Table 6.16 lists the minimum and maximum correlation coefficient obtained for each sample tree crown image (pm\n and p m a x , respectively), the value of dc that was used to generate the corresponding model instance set, and the locally variable parameter values of the model instance for which pma.x was obtained. sample b (metres) dc (pixels) Pmin Pmax 1 1.55 -410.5 0.906 0.949 2 1.55 135.5 0.865 0.926 3 3.73 9.5 0.779 0.918 4 3.18 -198.5 0.776 0.910 5 3.73 10.5 0.677 0.891 6 3.18 142.5 0.643 0.864 7 1.55 38.5 0.717 0.859 8 6.21 33.5 0.745 0.858 9 2.64 219.5 0.545 0.853 10 2.09 -444.5 0.571 0.814 11 1.55 -391.5 0.581 0.751 Table 6.16: Sample tree crown image correlation coefficients. Values of p m m and p m a x that were similarly obtained for the channel 3 sample crown images were generally lower than those listed in table 6.16. T h e values of the locally variable parameters (other than b) for the model instances for which P = Pmax varied widely with respect to the specified constraints (a/b: 1.32 to 8.64, n: 1.03 to 2.15, Xend: 1.18 to 2.45 m, Xmax/Xend: 0.28 to 0.49, L > a v g : 0.52 to 2.62 m - 1 , £ > m a x / D a v g : 1.61 Chapter 6. Experiment 112 to 4.41, B: 0.27 to 0.48). This is evidence that the constraints are not excessively loose relative to the natural variation of tree crown images. Based on the values of p m a x in Table 6.16, the working value for pdiff was evaluated to 0.95. B y generating the model instance sets with different values of 5 5 M (in increments of 10), the minimum value of 5 5 M at which the subsets M ' of M are of maximum size was estimated as 60 for pdiff = 0.95. A display triplet showing the sample tree crown subimage, the subimage with the boundary and apex location of the highest-p model instance superimposed in white, and the subimage with the pattern of the highest-p model instance superimposed at the same location was produced for each sample tree crown subimage (Figure 6.24). T h e y-intercept and slope of the straight-line least squares regression of tree crown image pixel values on coincident model instance pixel values were computed and used to transform the model instance patterns before the superimposition (the slope was applied as a gain and the y-intercept as an offset). T h e display triplets provide a visual impression of how well the extent and pattern of real tree crown images can be matched by instances of the permeable volume tree crown image model. 6.3.5 Definition of Recognition Regions A s illustrated in Section 4.1.2, a major geometric effect in the experimental M E I S II image data is along-row relief displacement (the angle between the projection vector and the optical axis can be as high as 2 0 ° ) . This indicates that the recognition regions should be at least partially based on image column offset (dc) intervals. T h e maximum d c -interval width that produces regions within which the along-row tree crown relief displacement can be considered as practically constant was estimated to be 51 pixels. Thi s interval width divides the 1024 column M E I S II image into 20 adjacent along-column image 'strips.' Three different crown envelopes were defined with b — 1.00, 3.73, and 6.21, and with values for f and n that produced the most vertically elongated shapes possible within the parameter constraints. For a specified whole number s of along-column strips (all of uniform width except for possibly the first and Chapter 6. Experiment 113 Figure 6.24: Sample tree crown subimage display triplets. Channel 8 subimage (left), subimage with boundary and apex location of highest-p model instance (middle), and subimage with model instance pattern (right). Chapter 6. Experiment 114 last when 1024/s is not a whole number) a model instance was computed for each of the three crown envelope definitions and for dc evaluated to the column coordinate of the start and middle of each strip (dT was evaluated to 0.0 for each instance). T h e extent similarity values of model instances with the same crown envelope definition, adjacent c?c-values, and aligned on the apex location were computed. T h e value of s was incremented from 10 until all of the computed extent similarity values were no less than the corresponding revalues listed in Table 6.15. T h e extent similarity values for s = 20 are listed in Table 6.17. dc (pixels) 1 2 (1.00,10,1.5) (3.73,4,2.0) (6.21,2,2.5) 0.0 25.5 1.00 0.88 1.00 25.5 51.0 0.75 0.89 0.93 51.0 76.5 0.75 0.88 1.00 76.5 102.0 0.77 0.89 0.94 102.0 127.5 0.77 0.89 1.00 127.5 153.0 0.94 0.90 0.93 153.0 178.5 0.78 0.89 0.94 178.5 204.0 0.81 0.87 1.00 204.0 229.5 0.96 0.91 0.93 229.5 255.0 0.84 0.90 0.99 255.0 280.5 0.84 0.92 0.94 280.5 306.0 ' 0.84 0.92 0.99 306.0 331.5 0.94 0.93 0.94 331.5 357.0 0.84 0.92 0.99 357.0 382.5 0.88 0.97 0.94 382.5 408.0 0.96 0.94 0.99 408.0 433.5 0.89 0.89 0.94 433.5 459.0 0.86 0.96 0.99 459.0 484.5 0.94 0.94 0.99 484.5 512.0 0.86 0.90 0.94 Table 6.17: Extent similarity of model instances generated for different column offsets (51 pixel dc increment). T h e apex was used as the registration feature in computing these extent similarity values. T h e apex was also used as the registration feature in model instance generation and in the recognition procedures; the decision to do so was based on the assumption that the form and irradiation of the part of the tree crown that is near the apex is least likely to be influenced by Chapter 6. Experiment 115 neighbouring tree crowns. Therefore, matches obtained for different model instances and same tree crown image would be compared to each other in the recognition procedure on the basis of the most ideal part of the tree crown. T h e pattern correlation values of model instance pairs representing extreme values of 6S, <f>s, and (f>{ (cf. Table 6.13) are considerably larger than the sample tree crown image correlation coefficients (cf. Table 6.16). Therefore, we do not regard refinement of the column offset-based recognition regions defined in Section 6.3.5 on the basis of variation in 9S, <f>a, and <f>{ to be warranted. If the d c-value associated with a column offset-based recognition region is that of the along-row midpoint of the region, then 51-column wide regions (i.e., 20 strips) represent an along-row deviation in the angle between the projection vector and the optical axis of 0 . 9 9 ° to 1 . 0 3 ° . These deviations are over twice the standard deviations of the roll (7) and pitch (/?) INS orientation angles listed in Table 6.4. Therefore, we do not regard refinement of the column offset-based recognition regions on the basis of variation in 7 and /? to be warranted. Knowledge of the scene that is more specific than knowledge of its Forest Region and Section has not been obtained. Therefore, we do not have grounds for specializing the constraints on the locally variable parameters to different parts of the scene and for subdividing the recognition regions on this basis. 6.3.6 Summary Twenty model instance sets were generated for each of the Sturgeon and Headquarters flightlines (one model instance for each 51-column wide recognition region in each flightline). Only the permeable volume model was used. T h e apex was used in computing the extent similarity values in the model instance set generation procedure (steps (3.2) and (3.3) in Figure 5.10). T h e value of dc used to generate a model instance set was that of the along-row midpoint of the corresponding recognition region, and dr was evaluated to 0 in each case. T h e other inputs to the model instance set generation procedure were evaluated as follows: Chapter 6. Experiment 116 • the constraints on locally variable parameters to the overall scene values specified in Section 6.3.1 • / = 0.02461 m,p= 1.729 x 1 0 - 5 m, H = 518 m, 7 = 0 . 0 ° , f3 = 0 . 0 ° , (the fixed test values specified in Section 6.3.2) • Sturgeon: (9s,<f>s) = ( 5 1 . 7 9 ° , 1 1 2 . 3 2 ° ) , Headquarters: (9s,<f>s) = ( 4 9 . 6 8 ° , 1 1 5 . 4 4 9 ° ) (the averages of the extrema values for the corresponding flightline as listed in Table 6.2) • K = 0.10 (the intermediate test value specified in Section 6.3.2) • Sturgeon: (j>{ — 3 2 1 ° , Headquarters: <f>{ = 2 7 7 ° (the flightline azimuth values listed in Table 6.2) • bi and 77; to the values specified in Table 6.15. • Pdiff = 0.95, SSE = 60, 5 5 M — 60 (the values specified in Section 6.3.4) T h e value assigned to K is relatively uncertain. However, a wide variation in the K-value produced relatively small pattern differences in the pattern correlation sensitivity tests (cf. Table 6.9), so we do not regard this uncertainty as being of much consequence. T h e number of uniform-extent subsets in a model instance set decreases with the associated column offset. For example, the number of uniform extent subsets in the model instance sets associated with dc = 484.5 pixels (a large offset from middle image column) and dc = 25.5 pixels (a small column offset) are respectively 43 and 11. This occurs because as the column offset decreases the amount of modelled relief displacement also decreases and, consequently, variation in the a and n parameters has an decreased effect on the image extent of the model instances. Conversely, the average number of model instances in the uniform-extent subsets of a model instance set increases slightly with a decrease in the associated column offset. For example, the average number of model instances in the uniform-extent subsets of model instance sets associated with dc = 484.5 pixels and dc — 25.5 pixels are respectively 2.7 and 3.6. Thi s occurs because as the associated column offset and number of uniform-extent subsets for a model Chapter 6. Experiment 117 instance set decreases, a larger variation in a and n is represented by each uniform-extent subset. 6.4 Tuning the Initial Matching Procedure T h e tuning of the initial matching procedure consists of adjusting the value of the procedure parameters ptrir (the correlation coefficient minimum threshold), psthr (the correlation coefficient minimum threshold for initiating the full-resolution search of the image-space), and dfrac (the extent dimension fraction), and the value of ngroup (the extent similarity value used to define the uniform-extent subset groups). In order to support the tuning task, six 51-by-280 subimages that represent a variety of stand types were selected from the the Headquarters flightline channel 8 image recognition regions with the associated d c-values —229.5, 25.5, and 280.5. Figure 6.25a is a mosaic of the test subimages. T h e initial matching procedure was run on the test subimages with different values for (Pthr, Psthn dfrac, r)gTOUp) (although r / g r o u p is not strictly an adjustable parameter of the matching procedure we group it with those parameters for convenience). T h e crown apex was used as the registration feature since it was also used in the model instance set generation (cf. Section 6.3.6). Figure 6.25b is a correlation coefficient map in which a non-zero value at location (x,y) is the maximum correlation coefficient for that location in the test subimage mosaic over all tested uniform-extent subsets, for (pthr, Psthn dfrac, rfgroup) = (0.00,0.00,0.00,1.00). T h e map was created by linearly scaling the correlation coefficient interval [0,1.0] to the image pixel value interval [0,255]. Thi s set of parameter values implies an exhaustive search through the image-space and uniform-extent subsets (i.e., the basic matching procedure outlined in Figure 5.13). T h e pthr parameter was evaluated to 0.00 because a negative value would permit matches to be defined for inverse linear relationships between model instance pixel values and coincident image pixel values, and such matches would clearly be invalid. A visual comparison of Figure 6.25a and Figure 6.25b shows that tree crown images generally Chapter 6. Experiment 118 Figure 6.25: Test subimage mosaic and maps: (a) test subimage mosaic, (b) overall maxi-mum correlation coefficient map for (/>thn Psthn dfrac, r / g r o u p ) = (0.00,0.00,0.00,1.00), (c) over-all maximum correlation coefficient map for (/>thn Psthn dfrac, nSTOup) = (0.00,0.50,0.25,0.75), (d) map of locations where map c pixel values are greater than zero, and (e) map b masked by map d. Chapter 6. Experiment 119 coincide with local maxima in the correlation coefficient surface, and that the spatial extent of a hill in the surface is generally related to the spatial extent of the coincident tree crown image. Figure 6.25c is the map of maximum correlation coefficients for (pthn Psthn dfrac, T]gTOUp) = (0.00,0.50,0.25,0.75). In this case, the 32, 11, and 28 uniform extent subsets associated with dc — -229.5, 25.5, and 280.5 were put into 15, 8, and 15 groups, respectively. A l l of the local maxima in Figure 6.25b appear to be present in Figure 6.25c. This was confirmed by generating a map of all non-zero pixels in Figure 6.25c (the white pixels in Figure 6.25d) and using this map to mask Figure 6.25b. T h e result (Figure 6.25e) shows that the unmasked regions generally have relatively low pixel values in Figure 6.25b. T h e adjustable parameter values that were used to generate Figure 6.25c were estimated to be those that minimized the amount of computation involved in the matching procedure while resulting in the retention of all of the local maxima that appear in Figure 6.25b. Thi s estimate was arrived at by generating and inspecting maximum correlation coefficient maps that were generated from a set of value combinations for />sthr, dfrac, and r / g r o u p . 6.5 Training Set and Feature Selection T h e training set was selected from the image regions illustrated in Figure 6.26. These regions represent a wide range of tree species, tree size, and column offset, as well as some non-forested areas that contain incorrect initial recognition instances. Each training region was defined within a single recognition region and none of them intersect a ground sample plot image region. Figure 6.27 illustrates the initial recognition instances for one of the training regions il-lustrated in Figure 6.26. T h e channel 8 subimage is pictured with the boundaries and apex locations of the matching model instances overlaid in white. For each training region, the initial recognition instances were selected which were considered with a high degree of confidence by the author to be either correct or incorrect. Over all training regions, 725 correct recognition instances and 1503 incorrect recognition instances were selected. Chapter 6. Experiment 120 Figure 6.26: Image regions from which the training set was selected. Each region is 51-by-51 pixels in size, and was defined within a single recognition region. T h e displayed subimages are from channel 8. Chapter 6. Experiment 121 Figure 6.27: Initial recognition instances for a training set region. T h e region is from the dc = 76.5 pixels recognition region. T h e recognition instances for all 13 uniform-extent subsets are pictured. Chapter 6. Experiment 122 725 incorrect recognition instances were randomly selected from the initial set of 1503 in-correct recognition instances. Thi s was done because the training regions were not randomly selected from the scene (for example, four of the training regions were deliberately selected to contain unforested areas), and so the relative numbers of correct and incorrect recognition errors do not necessarily reflect the relative a priori probabilities of correct and incorrect recognition. 50 recognition instances were randomly selected from each of the sets of 725 correct and incorrect recognition instances; a test set was made from these 100 recognition instances and the training set was made from the remaining 2 X 675 = 1350 recognition instances. T h e probability of correct recognition for the correct and incorrect recognition training exemplars was evaluated respectively to 1.0 and 0.0. T h e V S M learning procedure was initially run with the following 9 features: R2ch&, Cchs, Cch3, Dch7, Dchs, Dch4, Dch3, Dch3/Dch4, and Dchs/Dcm (see Section 5.4.2 for the feature definitions). T h e feature that was assigned the smallest weight by the V S M learning procedure was removed and the procedure was then re-run. T h e removal of a feature and re-running of the V S M procedure was repeated as long as the cross-validation error did not increase and the classification accuracy for the test set did not decrease. T h e final features were the following: R2ch8i Cch8, Cch3, and Dch3/Dch4, with the respective weights 9.24, 0.21, 0.18, and 2.77. T h e final optimized value r was 0.73. T h e initial and final values for the cross-validation error E were respectively 454.52 and 344.42. T h e fractions of correct and incorrect recognition test exemplars that were initially correctly classified were respectively 0.74 and 0.78 (0.76 overall). After the optimization, the fractions were respectively 0.90 and 0.88 (0.89 Overall). T h e cross-validation error and the test set classification accuracy were both essentially unchanged when R2ch& was replaced by R^hs/Rma.x,ch8 ( a n -^-axis interval width of 5 was used to compute # m a x c / j 8 ) , and worsened when Cchs and Cch3 were replaced by C'ch8 and C'ch3; therefore, the final features listed in the previous paragraph and the associated weights and r-value were used in the evaluation of the correct recognition probability. T h e V S M learning procedure was run with the final features and a training set consisting of Chapter 6. Experiment 123 the 675 correct recognition exemplars and 1453 incorrect recognition exemplars. A final cross-validation error of 464.92 was obtained, and the fractions of correct and incorrect recognition test exemplars that were correctly classified were respectively 0.82 and 0.96 (0.89 overall). These results are no better than those obtained with the original training set and were produced with a larger training set; therefore, the original training set was used in the evaluation of the correct recognition probability. In each run of the V S M learning procedure, all of the feature weights were initialized to 1.00, r was initialized to 0.80, the number of nearest neighbours involved in the interpolation was 10, and the number of nearest neighbours used to compute the kernel width was 3. 6 . 6 Tuning the Conflict Resolution Procedure T h e tuning of the conflict resolution procedure consists of defining a window grid and margin dimension, and adjusting the objective function component weights (cf. Section 5.5). A grid that defines 51-by-51 pixel windows was chosen because those windows are large enough to contain several of the largest tree crowns, and the along-column window boundaries can be made to coincide with the recognition region boundaries. T h e training set image regions pictured in Figure 6.26 each coincide with one window. T h e margin dimension was initially evaluated to 25 pixels. T h e objective function compo-nent weights were adjusted by computing final recognition results for several subimages, using a range of values (in increments of 5) for each of the weights. T h e sub-images were selected to represent wide canopy type and column-offset variation. O f the values that were tested, (wi, ^ 2 , W3) = (10,5,1) produced the best results over all subimages (according to visual in-spection); therefore, this weight triplet was used in the main experiment. T h e results were then recomputed with decreasing values for the margin width (5 pixel increments were used). A margin width of 20 pixels was found to be the smallest at which no reduction in the quality of the results was evident; therefore this margin width was selected for the main experiment. Figure 6.28 presents some examples of final recognition instances that were computed with Chapter 6. Experiment 124 different objective function component weights, including the selected final weights. T h e weight triplets (wi, W2, W3) = (10,1,1), (1,10,1), and (1,1,10) were chosen to respectively emphasize minimization of overlap among interpreted crown extents, maximization of the average correct recognition probability value, and maximization of the area of the processing region covered by interpreted crown extents. T h e intended emphasis for each of these weight triplets is evident in the corresponding results. (10,1,1) (1,10,1) (1,1,10) (10,5,1) Figure 6.28: F ina l recognition instances corresponding to different objective function compo-nent weights. Results are shown for the training set region pictured in Figure 6.27. Each example is labelled with the corresponding value for (wi, W2, w3). T h e weights are associated with components of the objective function as follows: w\ - minimization of overlap among in-terpreted crown extents, W2 - maximization of the average correct recognition probability value, W3 - maximization of the area of the processing region covered by interpreted crown extents. Chapter 6. Experiment 125 6 . 7 Results A n assessment of the automatic recognition results for 14 sample plots is presented in Sec-tion 6.7.1. These sample plots will be referred to as the test sample plots and the sample trees in them will be referred to as the test sample trees. T h e test sample plots were selected from the 15 sample plots for which manual recognition results are available (the manual recognition experiment is described in Section 6.2). Sample plot 3, which was included in the manual recog-nition experiment, was omitted from the test set because it contains the two reference locations that are associated with multiple trees (cf. Section 6.1.2), and it is not clear how these cases were accommodated in the enumeration of the manual recognition errors. A n assessment of the automatic crown diameter estimates for the automatically recognized test sample trees is presented is Section 6.7.2. T h e analysis of each set of results includes significance tests of various hypotheses about a population of trees that is randomly sampled by the test sample trees (the test population). T h e population corresponding to the full set of sample plots or to any subset of them has not been formally defined. However, the sample plots were selected on the basis of photo-interpretation and local knowledge so that they would, represent as wide a range of non-plantation stand types as possible, given the resources that were available for field work and the geographic coverage of the image data (Cloney, Leckie, and Gillis 1994). A s shown in Tables 6.18 and 6.19, the values for the different reference tree attributes, which are defined in Section 6.1.2, are distributed over the 340 test sample trees much as they are over all 548 sample trees. Therefore, we assume that the test population encompasses a substantial portion of the tree attribute-value combinations that are represented by the scene. dbh cm) height (m) crown diameter (m) min max M a min max a min max V- a all 8.2 59.0 23.4 9.7 6.5 33.3 17.8 4.2 1.0 10.2 3.6 1.7 test 8.9 59.0 23.8 9.7 6.5 33.3 18.5 4.2 1.1 10.2 3.5 1.7 Table 6.18: Ranges, means, and, standard deviations for interval-valued reference attributes for all 540 sample trees and for the 340 test sample trees. Chapter 6. Experiment 126 dominance crowding species species context dom. co-dom. low med. high soft. hard. soft. s . /h . h./s. hard. all 0.58 0.42 0.41 0.46 0.13 0.73 0.27 0.62 0.12 0.10 0.16 test 0.58 0.42 0.36 0.49 0.14 0.74 0.26 0.64 0.12 0.08 0.16 Table 6.19: Proportions of all 540 sample trees and of the 340 test sample trees with speci-fied values for ordinal- and nominal-valued reference attributes. Except for species, all values for each attribute are represented. "Softwood" (soft.) and "hardwood" (hard.) respectively represent 9 and 10 different species. T h e results assessments and analyses are summarized in Section 6.7.3. 6.7.1 Recognition Results Figure 6.29 provides an overview of the recognition results. T h e figure was created from three 275-by-275 pixel channel 8 subimages, each of which corresponds to a 1 hectare subscene that contains a single sample plot. T h e displays on the left show the subimages with the sample plot boundary overlaid in white. T h e displays on the right show the subimages with the sample plot boundary and the boundaries and apex locations of model instances overlaid in white. Each overlaid model instance boundary illustrates the computed recognition of one tree crown and the estimate of its image region. Inspection of the figure reveals that tree crowns were successfully recognized over a wide range of crown size and crown image texture, even in cases where the crown boundary is weakly defined or only implicit for much of its length. Some errors are also evident (examples of errors are discussed and illustrated later in this section). T h e erroneous recognition of tree crowns within unforested parts of the subscenes is largely avoided. Table 6.20 lists S U N S P A R C s t a t i o n 2 running times for different components of the recog-nition procedure as applied to the subimages pictured in Figure 6.29 (the times are actually for the minimum number of 51-by-51 pixel windows that cover the subimage extent, so in each case results were computed for an image extent that was slightly larger than the pictured subimage). T h e matching component, which produces the initial recognition instances, was run with three different sets of parameter values (A, B , and C ) . T h e times for these three runs show Chapter 6. Experiment 127 Figure 6.29: Channel 8 subimage and recognition results for 1 hectare subscenes that contain sample plots 3 (top), 7, and 21 (bottom). T h e column offsets of the plot centroids from the optical axis image point are respectively —8, —254, and 122 pixels. Chapter 6. Experiment 128 subimage matching matching matching correct conflict total A B C rec. prob. resolution plot 3 25:13 18:0.1 6:47 4:03 16:28 27:18 plot 7 43:11 29:14 ' 10:27 6:32 26:30 43:30 plot 21 27:05 20:35 5:42 4:53 24:08 34:43 average 31:50 22:37 7:39 5:09 22:22 35:10 Table 6.20: Running times for different components of the recognition procedure as applied to the subimages pictured in Figure 6.29. T h e tabulated quantities are the elapsed (real) times in minutes and seconds on a S U N S P A R C s t a t i o n 2. T h e matching procedure was run with the following values for ( p t h r , p s t h r , dfrac, r ? g r o u p ) : A : (0.00, 0.00,0.00,1.00), B : (0.00, 0.00,0.00,0.75), and C : (0.00,0.50,0.25,0.75). T h e other components were run with the initial recognition instances generated with parameter tuple C . T h e conflict resolution component includes the integration of the results for the separate processing regions. that a substantial savings in computation was obtained through a two-resolution search of the uniform-extent subsets as compared to a single-resolution search (i.e., T / g r o u p = 0.75 vs. ^group = 1-00) and through a two-resolution search of the image space as compared to a single-resolution search (i.e., /> s t n r = 0.50 and dfrac = 0.25 vs. psthr = 0.00 and dfrac = 0.00). Parameter value set C was used to compute the recognition results that are discussed in this section and were used to obtain the running times of the other procedure components (the choice of this parameter value set is discussed in Section 6.4). In general, the interpretation conflict resolution filter required more time than the sum of the times required for the version-C matching component and the correct recognition probability filter. T h e matching component required more time for the plot 7 subimage than for either of the two other subimages because of the relatively large absolute column offset for the plot 7 subimage. A relatively large column offset means that model instance sets with relatively large numbers of uniform-extent subsets are involved in the matching procedure (tree crown shape becomes a more significant variable as the absolute column offset increases). T h e interpretation conflict resolution component required more time for the plots 7 and 21 subimages than for the plot 3 subimage because the numbers of intermediate recognition instances were larger for the plots 7 and 21 subimages. In the case of plot 7, this was so because of a larger number of uniform extent subsets involved in the matching, and in the case of plot 21 this was so because Chapter 6. Experiment 129 of the smaller size of the tree crowns and, consequently, the greater number of intermediate recognition instances in the processing windows. For each of the 24 sample plots, a display showing the sample plot boundary and the recognition results (a results display), and a display of the sample plot boundary alone (a plot boundary display) were produced from copies of the same 100-by-100 pixel channel 8 subimage that was used to produce the reference display. T h e plot boundary displays are useful because they show the subimages with a minimum of annotation clutter. T h e plot boundary, reference, and results displays were assembled info triplets. A display triplet for each of the sample plots is presented in Appendix A (selected display triplets are reproduced later in this section). T h e automatic recognition results for a sample plot were assessed by manually comparing the reference and results displays for that sample plot. A binary subimage in which only the ref-erence apex locations are indicated was referred to in cases where the overlaid boundaries in the reference display were too cluttered to allow the coincident crown images to be clearly distin-guished. In general, the tree crown image associated with a reference crown boundary or apex location could be identified within the channel 8 subimage. A false-colour composite display of channel 3, 4, and 8 subimages was also referred to in order to confirm the identification. T h e manual recognition results for each test sample plot consist of a set of image locations, each of which corresponds to the interpreted location of a single tree crown. T h e interpreters were not required to delineate the crown image region. Omission errors were counted only in cases in which no interpreted tree crown locations were specified within the known image region of a single sample tree crown. A case in which multiple interpreted tree crown locations were specified within the known image region of a single sample tree crown never produced an omission error, and all but one of the locations were counted as commission errors. In contrast to the manual recognition results, the automatic recognition results include esti-mates of crown image regions. In cases where multiple interpreted crown image regions coincide with a single sample tree crown image region, it is reasonable to consider the possibility that none of the interpreted image regions describe the sample tree crown image region reasonably Chapter 6. Experiment i:JO well. Therefore, the automatic recognition results were assessed twice, according to two different sets of rules. T h e first assessment of the automatic recognition results, called the liberal assessment (Ta-ble 6.21), was intended to produce error counts that can be compared to those for the manual recognition results. In this assessment, an omission error was counted in all cases where an in-terpreted crown image region is not mostly included within a sample tree crown image region. In all cases where a sample tree crown image region intersects most of the area of n > 1 in-terpreted crown image regions, n — 1 commission errors were assessed. In a liberal assessment, example (a) of Figure 6.30 would produce zero omission errors and zero commission errors, example (b) would produce zero omission errors and two commission errors, example (c) would produce one omission error and one commission error, example (d) would produce zero omission errors and one commission error, and example (e) would produce three omission errors and one commission error. T h e actual tree crown would be counted as recognized only in examples (a), (b), and (d). actual crown image region a) interpreted crown image region Figure 6.30: Schematic examples of relationships between actual and interpreted crown image image regions. Chapter 6. Experiment 131 In the second assessment of the automatic recognition results, called the conservative as-sessment (Table 6.22), a model instance boundary that does not delineate a sample tree crown image region was counted as an omission error. A model instance boundary that coincides with an image region that is not clearly identified by the reference data as the image of a single tree crown was counted as a commission error. Some judgement was exercised in deciding whether or not a model instance boundary adequately delineates with a tree crown image region (the ex-act coincidence of model instance boundaries and reference boundaries was not insisted upon). In a conservative assessment, example (a) of Figure 6.30 would produce one omission error and one commission error, example (b) would produce one omission error and three commission errors, example (c) would produce one omission error and one commission error, example (d) would produce zero omission errors and one commission error, and example (e) would produce three omission errors and one commission error T h e actual tree crown would be counted as recognized only in example (d). T h e liberal and conservative assessments would be the same only for examples (c), (d), and (e). Table 6.21 shows that the numbers of commission errors in the manual and the liberally assessed automatic recognition results are close (respectively 10% and 11% of the total number of sample trees). However, the number of liberally assessed automatic recognition omission errors is 2.8 times the number of manual recognition omission errors. Comparison of Tables 6.21 and 6.22 shows that the numbers of conservatively assessed errors are only slightly greater than the numbers of liberally assessed errors. T h e automatic recognition results for six of the test sample plots are discussed below. Results that are among the best and the worst over all of the the test plots are included. T h e discussions explain the cause of various errors that occur in the automatic recognition results, and include descriptions of error enumeration under both assessment procedures. T h e display triplets for these sample plots are reproduced below, with additional annotation, to support the discussions. T h e automatic recognition results for sample plots 21 and 7, which are discussed next, are Chapter 6. Experiment 132 plot man. int. sample manual auto. manual auto. pixel d im. trees om. errs om. errs comm. errs comm. errs 1 original 15 0.6 4 5.8 4 2 original 14 0.6 3 2.6 3 4 original 20 2.8 14 4.0 11 5 double 10 0.0 1 3.0 2 6 double 27 7.2 13 0.4 2 7 double 6 0.0 0 0.4 1 8 double 16 . 1.2 3 2.2 2 12 half 47 3.6 24 3.6 1 15 half 30 2.6 12 6.0 2 19 original 46 2.6 16 2.4 1 20 original 24 2.4 9 1.2 0 21 double 27 3.0 3 0.6 1 22 double 30 9.0 12 1.8 6 23 double 28 10.4 17 0.6 2 total 340 46.0 . 131 34.6 38 total/340 0.14 0.38 0.10 0.11 Table 6.21: Liberal enumeration of the omission and commission errors in the automatic recog-nition results, accompanied by the enumeration of omission and commission errors in the man-ual recognition results (average values over 5 different interpreters) and the display pixel di-mension used in the manual interpretation of each sample plot (extracted from Cloney and Leckie (1995)). Chapter 6. Experiment 133 plot flight- abs. col. sample omission commssion line offset trees errors errors 1 Head 378 15 6 6 2 Head 414 14 4 4 4 Head 446 20 18 15 5 Head 37 10 1 2 6 Head 80 27 13 2 7 Head 254 6 1 2 8 Head 165 16 4 3 12 Head 96 47 24 1 15 Head 12 30 13 3 19 Stur 21 46 16 1 20 Stur 17 24 9 0 21 Stur 122 27 3 1 22 Stur 131 30 13 7 23 Stur 21 28 17 2 total 340 142 49 total/340 0.42 0.14 Table 6.22: Conservative enumeration of omission and commission errors in the automatic recognition results. T h e sample flightline that each sample plot belongs to and the absolute column offset from the optical axis image point of each sample plot centroid are also indicated. relatively good. T h e 3 unrecognized crowns in sample plot 21 (Figure 6.31) all have relatively dark and low-contrast images (the images of these crowns are labelled in the reference display of Figure 6.31). A n omission error was counted for each of these crowns in both assessments. T h e heights of the unrecognized sample trees ranged from 11.4 to 11.6 m and they are all co-dominant, while the average height of the other sample trees in the plot was 17.7 m. This suggests that surrounding tree crowns were intercepting direct solar irradiance that otherwise would have reached the unrecognized crowns. T h e unrecognized crowns are larger than they appear to be in the image. For example, the unrecognized black spruce crown (labelled bs in the reference display) had a diameter of 2.4 m, which is close to the average diameter for the recognized crowns (2.6 m), but its image has an exceptionally small reference region consisting of only four pixels. T h e red pine whose crown image is labelled rp' on the reference display of Figure 6.32 was counted as unrecognized in the conservative assessment for plot 7, but was counted as Chapter 6. Experiment 134 * m ft^P^^. ,-.:; 7« V i i v l l w i BIB Figure 6.31: Plot boundary (left), reference (middle), and results (right) displays for sample plot 21. T h e images of the unrecognized sample tree crowns are labelled according to species in the reference display (bf: balsam fir, bs: black spruce, wb: white birch). recognized in the liberal assessment. T h e two model instance boundaries that are labelled err in the results display each produced a commission error in the conservative assessment, but in the liberal assessment they collectively produced only 1 commission error. Figure 6.32: Plot boundary (left), reference (middle), and results (right) displays for sample plot 7. T h e sample tree crown images are labelled with their species in the reference display (la: largetooth aspen, rp: red pine). Commission errors in the conservative assessment are labelled err in the results display. The image column offset for the centroid of sample plot 7 is moderate (-254 pixels), and the resulting height displacement appears to have caused the rp' crown to partially occlude the adjacent crown whose image is labelled rp", thereby blocking the view of any between-crown Chapter 6. Experiment 135 gap and explaining why the division between the two crown images is unclear (the rp' and rp" trees were respectively 27.4 and 28.2 m high, so neither tree was overtopping the other). T h e r p ' and rp" crowns had diameters of 6 .7m and 5 .8m, respectively, and the model instance that matches the rp" crown image has a horizontal radius parameter of 3.18 m, or an associated horizontal diameter value of 6.36 m. Therefore, recognition of the rp' crown should involve a model instance with approximately the same image extent as the one that matches the rp" crown image. However, the extents of the two positioned model instances would overlap considerably, and this is discouraged in the conflict resolution procedure (Section 5.5). Instead, two relatively small model instances were selected to match irregularities within the rp' crown image (these irregularities suggest a foliage gap or foliage clumping). T h e combined extent of these model instances covers a large part of the rp' crown image while producing little overlap of interpreted crown image regions. Figure 6.33 shows the effect of changing the w\-va\ue from 10 (the value used to generate the results shown in Figure 6.32) to 5. T h e greater tolerance for overlap of interpreted crown extents (due to the smaller Wi-value) in the new results allows approximately the same amount of the combined image extent of the rp' and rp" crowns to be accounted for by two interpreted crown extents as is accounted for by three interpreted crown extents in the original results. Figure 6.33: Sample plot 7 results computed with different overlap penalty weights. T h e display of the original results from Figure 6.32 is reproduced on the left. These results were computed with a Wi-value of 10 (cf. Section 6.6). T h e display on the right shows the results computed with the same parameters as the original results, except for an upva lue of 5. Chapter 6. Experiment 136 T h e automatic recognition results for sample plots 4, 12, and 22, which are discussed next, are relatively poor. T h e automatic recognition results for sample plot 4 (Figure 6.34) have considerably greater numbers of both omission errors and commission errors, in either assessment, than the manual recognition results. T h e model instance boundaries that coincide with the 2 sample trees that are counted as recognized in the conservative assessment are labelled rec in the results display of Figure 6.34. T h e 6 sample trees that were counted as recognized in the liberal assessment are labelled rec in the reference display of Figure 6.35. Figure 6.34: Plot boundary (left), reference (middle), and results (right) displays for sample plot 4. T h e matches labelled rec in the results display indicate the only instances of successful tree crown recognition in the conservative assessment. T h e sample tree crown images are labelled with their species in the reference display (la: largetooth aspen, ta: trembling aspen, rm: red maple, wb: white birch). T h e labels for the relatively dark and low-contrast tree crown images that are discussed in the text include the sample tree identifiers 015, 025, 026, and 027. T h e automatic recognition procedure failed to establish model instance matches for most of the sample tree crown images in sample plot 4 because their spatial extents are too irregular or, in some cases, they are too dark and low-contrast. This resulted in a large number of omission errors in both assessments, relative to the number of manual recognition omission errors. T h e irregular crown image extents are explained by the tendency for large hardwood trees under competition to develop irregular crown form, and by the partial occlusion of tree crowns by other tree crowns. A l l 20 of the sample trees were hardwoods, many of them were large Chapter 6. Experiment 137 Figure 6.35: Recognized sample trees in sample plot 4 in the liberal assessment are labelled rec in the reference display. (11 of them had a crown diameter greater than or equal to 5 m), they were all subjected to either medium crowding (14 trees) or high crowding (6 trees), and the offset of the sample plot centroid from the optical axis image point is large (446 pixels). Four of the unrecognized sample tree crowns have images that are generally darker and lower in contrast than the positive training example images (these sample crown images are indicated in the reference display of Figure 6.34 with labels that include sample tree identifiers). For each of the images labelled 025, 026, and 027 one or more reasonable candidate model instance matches were initially established by the matching procedure but these were later eliminated by the correct recognition probability filter. T h e image labelled 015 was not even initially assigned a match. T h e heights of the corresponding sample trees ranged from 14.8 m to 17.9 m and they are all co-dominant, while the mean height for the other sample trees in the plot was 19.2 m and 44% of these were dominant. This suggests that the primary cause of the dark and low-contrast quality of their crown images was their relatively low height and, consequently, the interception by surrounding crowns of direct solar irradiance that otherwise would have reached them. T h e matches that resulted in instances of recognition success in only the liberal assessment are matches between small model instances and within-crown image features of relatively large sample crowns. Such matches also produced most of the commission errors. Note that the feature labelled ? in the reference display of Figure 6.34 does not coincide Chapter 6. Experiment 138 with a sample or understory tree according to the reference data, yet the appearance of this feature is at least as crown-like as the four sample tree crown images discussed above. This feature has been automatically recognized as a tree crown, which resulted in a commission error in both assessments (the coincident model instance boundary is labelled ? in the results display). Under both assessments, the automatic recognition results for sample plot 12 (Figure 6.36) have a considerably greater number of omission errors than the manual recognition results, but fewer commission errors. T h e white spruce crown images that are labelled ws in the reference display of Figure 6.36 were collectively recognized as part of a single relatively large crown. This produced 5 omission errors and 1 commission error in both assessments (the model instance boundary associated with the commission error is labelled err in the results display). These errors are explained by two factors. First the labelled crown images collectively create a pattern that resembles the image of the directly irradiated portion of a single large crown. Second, a dark image region is juxtaposed with the cluster of labelled crown images approximately along the image projection of the direct solar irradiance direction. In this context, the dark image region resembles the image of the non-directly irradiated portion of a large crown. Figure 6.36: Plot boundary (left), reference (middle), and results (right) displays for sample plot 12. T h e images of the unrecognized white spruce crowns that are discussed in the text are labelled ws in the reference display and the associated commission error is labelled err in the results display. T h e sample plot 12 results suggest that the probability of automatically recognizing a crown Chapter 6. Experiment 138 with a sample or understory tree according to the reference data, yet the appearance of this feature is at least as crown-like as the four sample tree crown images discussed above. This feature has been automatically recognized as a tree crown, which resulted in a commission error in both assessments (the coincident model instance boundary is labelled ? in the results display). Under both assessments, the automatic recognition results for sample plot 12 (Figure 6.36) have a considerably greater number of omission errors than the manual recognition results, but fewer commission errors. T h e white spruce crown images that are labelled ws in the reference display of Figure 6.36 were collectively recognized as part of a single relatively large crown. This produced 5 omission errors and 1 commission error in both assessments (the model instance boundary associated with the commission error is labelled err in the results display). These errors are explained by two factors. First the labelled crown images collectively create a pattern that resembles the image of the directly irradiated portion of a single large crown. Second, a dark image region is juxtaposed with the cluster of labelled crown images approximately along the image projection of the direct solar irradiance direction. In this context, the dark image region resembles the image of the non-directly irradiated portion of a large crown. Figure 6.36: Plot boundary (left), reference (middle), and results (right) displays for sample plot 12. T h e images of the unrecognized white spruce crowns that are discussed in the text are labelled ws in the reference display and the associated commission error is labelled err in the results display. T h e sample plot 12 results suggest that the probability of automatically recognizing a crown Chapter 6. Experiment 139 is related to the size of the crown and the level of crowding that the tree was subjected to. A l l of the sample trees in sample plot 12 were subjected to either medium or high crowding, but 62% of the sample trees with unrecognized crowns were subjected to high crowding compared to 22% of the sample trees with recognized crowns. Also, the recognized and unrecognized crowns had an average diameter of 3.7 m and 2.5 m respectively. T h e automatic recognition results for sample plot 22 (Figure 6.37) include the recognition of a single large white birch crown as multiple relatively small crowns. This example produced 5 commission errors and 1 omission error in the conservative assessment, and 4 commission errors and no omission errors in the liberal assessment (the white birch crown is labelled wb in the reference display of Figure 6.37, and the associated commission errors in the conser-vative assessment are labelled errl in the results display). In large- and medium-scale aerial photographs, white birch crowns tend to have a clumped appearance. This is due to the di-vision of the main stem into several large ascending branches, each bearing its own clump of foliage (Sayn-Wittgenstein 1978, p. 69). T h e labelled white birch crown image is consistent with this description, so each of the associated commission errors probably coincides with a single within-crown foliage clump. at • Jf { M i l » ' ™ S ^ H H H E I iiiiii-^iy t Figure 6.37: Plot boundary (left), reference (middle), and results (right) displays for sample plot 22. T h e unrecognized white birch crown image that is discussed in the text is labelled wb in the reference display, and the associated commission errors in the conservative assessment are labelled errl in the results display. T h e unrecognized black spruce and eastern larch crown images that are discussed in the text are respectively labelled 6s and el in the reference display, and the associated commission error is labelled err2 in the results display. Chapter 6. Experiment 140 Figure 6.37 reveals a second example of the recognition of a cluster of crown images as part of a single relatively large crown. This example produced 5 omission errors and 1 commission error in both assessments. T h e model instance boundary associated with the commission error is labelled err2 in the results display. Three of the crown images are of black spruce crowns (labelled bs in the reference display) and two are of eastern larch crowns (labelled el in the reference display). A s is case with the example in sample plot 12 (Figure 6.36), a dark image region is juxtaposed with a bright image region that coincides with multiple poorly separated crown images, and both image regions are juxtaposed approximately along the image projection of the direct solar irradiance direction (the direct solar irradiance direction projects to different axes in the images of sample plots 12 and 22 because these images are from different flight lines). T h e tree that corresponds to the dark black spruce crown image labelled bs' in the reference display of Figure 6.37 was 18.0 m high, while the of trees corresponding to the bright eastern larch crown images (labelled el) were 20.8 m and 21.8 m high. These eastern larch trees were positioned with respect to the bs' crown such that they probably intercepted direct solar ir-radiance that otherwise would have reached the 6s' crown. This would explain the relatively dark and low-contrast appearance of the bs' crown image. Despite the fact that it was shorter than the eastern larch trees, the 6s' tree was classified as dominant, possibly because it was 4 m higher than the immediately adjacent tree whose crown image is labelled 6s. In some cases, automatically interpreted crown regions that were computed for different processing windows overlap each other excessively. T h e results for sample plot 1 contain exam-ples of this. T h e boundaries of the processing windows for the image of this plot are overlaid in white onto the results display of Figure 6.38. A n interpreted crown region is associated with the processing window that contains the apex location of the matching model instance. T h e interpreted crown regions labelled a, 6, and c in the results display respectively overlap the crown regions labelled a', 6', and c' T h e a-a' and the c-c' examples each produced one commission error in both assessments (two of the a extents are outside of the sample plot and Chapter 6. Experiment 141 were therefore not counted as commission errors). Figure 6.38: Plot boundary (left), reference (middle), and results (right) displays for sample plot 1. T h e processing window boundaries are overlaid onto the results display. Three examples of excessive overlap between automatically interpreted crown extents for different processing windows are labelled in the results display (a vs. a', b vs. b', and c vs. c'). T h e processing step that integrates the results for different processing windows eliminates an interpreted crown region if its centroid is within a second interpreted crown extent associated with a greater correct recognition probability value (cf. Section 5.5). T h e a-regions were not eliminated because their match probability values (0.825, 0.878, and 0.840), are greater than that of the a-region (0.668). T h e c-region is a similar case: its match probability value (0.760) is greater than that of the c-region (0.691). T h e 6-region has a lower match probability than the b -region (0.619 vs. 0.812), but it was not eliminated because its centroid lies outside of the b -region. In the preceding discussions, examples were presented in which automatic crown recognition omission errors could be explained by their relationship to column offset, crowding, crown diameter, relative tree height or dominance, and, in the case of large crowns, species class (hardwood or softwood). In the following discussion, we investigate the significance of these factors with respect to the probability of automatic crown recognition over the test population. Pairs of opposing properties that are related to the factors that we wish to investigate were defined and associated with subsets of the set of 340 sample trees. Each subset contains Chapter 6. Experiment 142 exactly those sample trees with the associated property. T h e two subsets corresponding to any property pair are disjoint, but their union does not necessarily contain all of the sample trees. T h e proportion of each subset that consists of sample trees with automatically recognized crowns (in the conservative assessment) was calculated. T h e properties, subset sizes, and recognized proportions are listed in Table 6.23. T h e crown diameter threshold (3.5 m) is the mean crown diameter over all 340 sample trees. Each row of this table represents a pair of opposing properties, and the property under the heading "property 1" is associated with the greater recognized proportion. property 1 property 2 "1 «2 Pi Pi Z s.l. for acc. Hi 0.05 0.01 abs. col. off. < 50 and abs. col. off. > 250 and 78 42 0.462 0.333 1.367 med. or high, crowding med. or high crowding abs. col. off. < 100 and abs. col. off. > 250 and 145 42 0.469 0.333 1.564 med. or high, crowding med. or high crowding abs. col. off. < 250 and abs. col. off. > 250 and 175 42 0.480 0.333 1.719 V med. or high, crowding med. or high crowding low crowding med. crowding 123 168 0.813 0.470 4.683 V V med. crowding high crowding 168 49 0.470 0.388 0.645 dominant co-dominant 197 143 0.675 0.455 4.061 V V diameter > 3.5 m diameter < 3.5 m 134 206 0.634 0.549 1.553 soft. sp. and hard. sp. and 172 34 0.552 0.529 0.246 diameter < 3.5 m diameter < 3.5 m soft. sp. and hard. sp. and •81 53 0.765 0.434 3.890 V diameter > 3.5 m diameter > 3.5 m Table 6.23: Automatical ly recognized proportions of sample tree subsets associated with speci-fied properties. T h e subsets associated with property 1 and property 2 are of size n i and n2 and have recognized proportions P i and P2. Z is the value of the standardized variable for P \ - P2. T h e hypothesis Hi that the automatically recognized population proportion associated with property 1 is greater than that associated with property 2 can be accepted at the 0.05 and 0.01 significance levels where indicated with a y/. For each pair of properties, we define the H0 to be the hypothesis of equal automatically recognized test population proportions and Hi to be the hypothesis that the automatically recognized test population proportion associated with property 1 is greater than that associated with property 2. T h e results of a test that was performed to decide between HQ and Hi for each pair of properties are listed in Table 6.23. T h e standardized variable Z used in the test Chapter 6. Experiment 143 was calculated according to where a P l _ p 2 = , / p ( l - P ) ( - + - ) . T h e assumed uniform test population proportion P was evaluated to the weighted mean of the sample subset proportions: = n i P i + n 2 P 2 n i + n 2 / Z i was accepted in a one-tailed test at the 0.05 and 0.01 significance levels for Z > 1.645 and Z > 2.33 respectively. This test relies on the assumption that the sample trees with a specified property represent a random sample of the test population trees with that property, in which case n,Pj- has a binomial distribution and the density function of Z is very nearly standard normal for large values of nt- (n^ > 30) (Hogg and Craig 1978, § 5.4). T h e results of the significance tests provide strong evidence that Ho can be rejected for crowding variation between low and medium levels, and for dominance variation. There is also strong eyidence that Ho can be rejected for species class variation when consideration is limited to trees with average or greater than average crown diameter, but not when consideration is limited to trees with smaller than average crown diameter. There is little evidence that Ho can be rejected for absolute column offset variation (even when consideration is limited to trees under medium or high crowding), for crowding variation between medium and high levels, or for crown diameter class variation (diameter greater than or equal to average vs. diameter less than average). Table 6.24 shows that 69% of the automatic recognition commission errors are associated with model instances that have the 1.00 m horizontal radius value. O f these 34 commission errors, 31 coincide with parts of images of relatively large crowns, as do 5 of the 6 commission errors associated with the 1.55 m horizontal radius value. T h e single commission error associated with the 6.21 m horizontal radius value occurs in the plot 15 results where it coincides with a Chapter 6. Experiment 144 dense cluster of irregular hardwood crowns. Only 3 of the commission errors occurred because the results integration step was ineffective (2 in sample plot 2 and 1 in sample plot 8). model instance 1.00 1.55 2.09 2.64 3.18 3.75 4.28 4.84 5.48 6.21 hor. radius (m) number of 34 6 0 2 3 3 0 0 0 1 , commissions Table 6.24: Number of conservatively assessed automatic recognition commission errors associ-ated with each model instance horizontal radius parameter value. 6.7.2 Crown Diameter Estimation Results T h e horizontal diameter value associated with the matching model instance for an automati-cally recognized tree crown provides an automatic diameter estimate for that tree crown (the horizontal diameter value associated with a model instance is simply twice the horizontal ra-dius parameter value that was used in computing the model instance). Thi s section presents an assessment and analysis of the accuracy of the automatic crown diameter estimates for each of the 198 tree crowns that were considered to be automatically recognized in the conservative recognition accuracy assessment. For 197 of these tree crowns, a crown diameter estimate was also derived from the manually-delineated reference crown image region by computing the average of the overall pixel-unit dimension of the region along four different axes (along-column, along-row, and both diagonals) and multiplying the results by a G P P D of 0.364 m. This provided a set of manual diameter estimates for those tree crowns whose accuracy could be compared to that of the automatic diameter estimates. One of the automatically recognized tree crowns had only a reference apex location and no reference image region, and was therefore excluded from the manual classification. T h e automatic and manual diameter estimates were used to assign the recognized crowns to diameter classes. T w o different sets of crown diameter class intervals, were considered. T h e endpoints of the "full-resolution" intervals were placed halfway between the full set of ordered Chapter 6. Experiment 145 horizontal diameter values for the model instance set (see Table 6.25). Except for the first and last intervals, which are open-ended, the widths of these intervals range from 1.0 to 1.4 m. index 1 2 3 4 5 6 7 8 9 10 d> 2.6 3.6 4.7 5.8 6.9 8.0 9.1 10.3 11.7 d< 2.6 3.6 4.7 5.8 6.9 8.0 9.1 10.3 11.7 Table 6.25: Full resolution horizontal crown diameter (d) intervals (metres). T h e endpoints of the "half-resolution" intervals were placed halfway between every second model instance set horizontal diameter value (see Table 6.26). Except for the first and last intervals, which are open-ended, the widths of these intervals range from 2.2 to 2.3 m. index 1 2 3 4 5 d> 3.6 5.8 8.0 10.3 d< 3.6 5.8 8.0 10.3 Table 6.26: Half resolution horizontal crown diameter (d) intervals (metres). Errors in the classifications derived from the manual and automatic diameter estimates (the test classifications) were assessed on the basis of classifications derived from the crown diameter measurements that were made on the ground (the reference classifications). T h e correct and erroneous components of each of the test classifications are enumerated in an error matrix. T h e error matrices for the full-resolution estimates are presented in Tables 6.27 and 6.28, and those for the half-resolution estimates are presented in Tables 6.29 and 6.30. In each error matrix, a crown assigned to class a by the test classification and assigned to class b by the reference classification is counted in the matrix cell at row a and column 6. T h e following quantities are involved in the accuracy assessment, several of which are in-cluded in Tables 6.27 to 6.30: N: total' number of sample trees (both recognized and unrecognized) in the 14 test plots (N = 340) m : the number of classes (m = 10 for the full-resolution classifications and m = 5 for the half-resolution classifications) Chapter 6. Experiment 146 N{i number of sample trees (both recognized and unrecognized) in the 14 test plots that are assigned to class i by the reference classification Pi'. (Ni/N) an estimate of the a priori probability of assigning a sample tree to class i by chance n: total number of sample trees involved in the accuracy assessment (n = 198 for the automatic classification and n = 197 for the manual classification) na: number of sample trees counted in row i and column i of the error matrix (i.e., the number of sample trees correctly assigned to class i by the test classification) ni+: sum of entries in row i of the error matrix, which is the number of sample trees assigned to class i by the test classification sum of entries in column i of the error matrix, which is the number of sample trees assigned to class i by the reference classification P+i'. (n+i/n) components of the marginal distribution of the reference classification Ui'. (nn/rii+) user's accuracy for class i (Story and Congalton 1986), which is an estimate of the probability that a tree assigned to class i by the test classification actually belongs class i Pi' (nu/n+i) producer's accuracy for class i (Story and Congalton 1986), which is an estimate of the probability that a tree actually in class i is assigned to class i by the test classification Xi'. (nPi) an estimate of the number of sample trees that would be assigned to class i by chance Inspection of the error matrices reveals a tendency for each test classification to underesti-mate crown diameter. Thi s has caused the class 1 producer's accuracy to be considerably larger than the class 1 user's accuracy, in each error matrix, since the crown diameter for a tree that is actually in class 1 cannot be underestimated, while underestimation of the crown diameter for a tree that is actually in one of the other classes may cause it to be assigned to class 1 by the test classification. Chapter 6. Experiment 147 A tendency to underestimate crown diameter has also been noted in the manual interpreta-tion of medium scale aerial photographs (Howard 1991, p. 299). Thi s occurs because many thin branches that help define the maximum extent of a crown and are considered in field measure-ments are not resolved in the photographs, or are hidden because they penetrate into adjacent crowns. These may also be significant factors in the manual and automatic diameter classi-fications presented here since the spatial resolution of the experimental image data is clearly not high enough to reveal individual branches. T h e examination of the recognition results for sample plot 21 in Section 6.7.1 suggests that the degree to which the tree crown was shaded by other tree crowns when the image data were acquired may also be a significant factor. 1 2 3 4 5 6 7 8 9 10 n,+ Ui 1 53 37 10 1 101 0.52 2 5 16 15 3 1 40 0.40 3 1 4 10 6 1 22 0.45 4 1 3 7 1 1 13 0.54 5 1 3 1 5 0.60 6 1 4 3 8 0.38 7 1 1 3 5 0.60 8 1 1 0.00 9 1 1 0.00 10 1 1 0.00 "+. 59 58 38 20 9 6 6 1 0 0 197 P. 0.90 0.28 0.26 0.35 0.33 0.50 0.50 0.00 — — X'i 63.158 60.834 31.284 22.596 8.116 5.220 4.058 1.734 o.ooo o.boo Table 6.27: Error matrix for the full-resolution horizontal crown diameter classification based on manual crown image region delineation. A crown estimated to be in class a and known to be in class b is counted in the cell at row a and column b. A quantity that is often used to measure the overall accuracy of a test classification is the overall agreement P0 = £3£Li nalni which is the correctly classified fraction of the total number of samples (Story and Congalton 1986). T h e value of Pa associated with each error matrix is listed in Table 6.31. In both the manual and automatic cases, the overall agreement value for the half-resolution classification is 1.6 times that of the full-resolution classification. For random samples of trees, nPa has a binomial distribution; therefore, the standard devi-ation of PQ can be estimated according to ' c(Pa) = ^ - P 0 ( l - P 0 ) . Chapter 6. Experiment 148 1 2 3 4 5 6 7 8 9 10 "•+ Hi 1 43 28 8 3 82 0.52 2 16 27 19 3 2 0 1 68 0.40 3 3 7 3 2 15 0.47 4 1 3 5 3 1 13 0.38 5 1 3 2 2 1 9 0.22 6 3 2 1 4 10 0.10 7 8 0 1 1.00 9 0 — 10 0 — 59 59 38 20 9 6 6 1 0 0 198 Pi 0.73 0.46 0.18 0.25 0.22 0.17 0.00 1.00 — — X, 63.479 61.142 31.442 22.711 8.158 5.247 4.079 1.742 0.000 0.000 Table 6.28: E r r o r matrix for full-resolution automatic horizontal crown diameter classification. A crown estimated to be in class a and known to be in class b is counted in the cell at row a and column b. 1 2 3 4 5 ni+ Ui 1 111 29 1 • 141 0.79 2 6 26 3 • 35 0.74 3 2 10 1 13 0.77 4 1 1 4 6 0.67 5 9 2 2 0.00 n+i 117 58 15 7 0 197 Pi 0.95 0.45 0.67 0.57 — xi 123.992 53.879 13.317 5.792 0.000 Table 6.29: E r r o r matrix for the half-resolution horizontal crown diameter classification based on manual crown image region delineation. A crown estimated to be in class a and known to be in class b is counted in the cell at row a and column b. 1 2 3 4 5 ni+ Ui 1 114 33 2 1 150 0.76 2 4 18 6 28 0.64 3 7 7 5 19 0.37 4 • 1 1 1.00 5 0 — n+i 118 58 15 7 0 198 Pi 0.97 0.31 0.47 0.14 — xi 124.621 54.153 13.385 5.821 0.000 Table 6.30: E r r o r matrix for the half-resolution automatic horizontal crown diameter classifi-cation. A crown estimated to be in class a and known to be in class b is counted in the cell at row a and column b. Chapter 6. Experiment 149 error matrix Po P0 99% conf. int. T a(T) T 99% conf. int. man. full-res. auto, full-res. 0.233 0.233 0.482 0.434 0.0356 0.0352 (0.390,0.574) (0.343,0.525) 0.325 0.262 0.0464 0.0459 (0.205,0.445) (0.144,0.380) man. half-res. auto, half-res. 0.461 0.461 0.766 0.707 0.0302 0.0323 (0.689,0.844) (0.624,0.790) 0.566 0.456 0.0560 0.0600 (0.421,0.710) (0.304,0.614) Table 6.31: Error matrix assessments. For large n, the 99% confidence interval for P0 can be estimated as Pa ± 2 . 5 8 cr(P0). T h e values of (j(P0) and the associated 99% confidence interval for each error matrix is listed in Table 6.31. T h e confidence intervals show that the hypothesis that the test population overall agreement value is greater than zero can be accepted at the 0.005 significance level for every error matrix. Overall agreement does not take into account the chance agreement between a reference and test classification, and may therefore give a misleading impression of high classification accuracy. T h e T a u coefficient (T) is an alternative measure of classification accuracy that does consider chance agreement. It is calculated according to 1-Pr where Pr = YliLi P+iPils measure of random agreement (Klecka 1980; M a and Redmond 1995). T h e T a u coefficient can be interpreted as an adjustment of overall agreement by the number of classes and the a priori probability of correct classification: if Pi = 1 /m then the upper limit of T as m increases is Pa. Table 6.31 includes the value of T for each error matrix, and the estimates for the standard deviation of T , which are calculated according to ( M a and Redmond 1995). Although the values for T are generally lower than the corresponding values for P0, the associated confidence intervals show that the hypothesis of a test population value of zero for T can be rejected at the 0.005 significance level for every error matrix. There-fore, we can reject the hypothesis that the classification results only represent chance agreement. In both the manual and automatic cases, the T a u coefficient for the half-resolution classifi-cation is 1.7 times that of the full-resolution classification. Chapter 6. Experiment 150 Let T\ and T2 be T a u coefficients associated with test classifications 1 and 2, respectively, define HQ to be the hypothesis of equal test population Tau coefficients for the two classifications, and define H\ to be the hypothesis of a larger test population T a u coefficient for classification 1. A test was performed to decide between HQ and Hi for the pairs of test classifications listed in Table 6.32. T h e standardized variable Z that was used in the test was calculated according to Tx-T2 test classifications Z s.l. for acc. Hi 0.05 0.01 1. man. full-res. 2. auto, full-res. 0.965 1. man. half-res. 2. auto, half-res. 1.340 1. man. half-res. 2. man. full-res. 3.314 V V 1. auto, half-res. 2. auto, full-res. 2.568 V Table 6.32: Standardized variable values for differences of Tau coefficients for various pairs of crown diameter classifications. T h e hypothesis Hi that the population T a u coefficient for classification 1 is greater than that of classification 2 can be accepted at the 0.05 and 0.01 significance levels where indicated with a yf. T h e values of Z for different pairs of test classifications are listed in Table 6.32. Hi was accepted in a one-tailed test at the 0.05 and 0.01 significance levels for Z > 1.645 and Z > 2.33, respectively. T h e results of the significance tests do not support the rejection of the hypothesis that manual and automatic crown diameter classifications are equally accurate over the test popu-lation; however, they do support the rejection of the hypothesis that tree crowns are no more accurately assigned to approximately 2.0 m wide diameter classes than to approximately 1.0 m wide diameter classes under either classification method. Chapter 6. Experiment 151 6.7.3 S u m m a r y T h e errors in automatic recognition results were mostly omission errors. Automatic recognition errors were evidently caused by non-ideal crown irradiation, irregular crown form (especially for some hardwood trees), partial occlusion of tree crowns due to height displacement, faulty interpretation of tight clusters of tree crowns as relatively large tree crowns, and faulty integra-tion of the results for adjacent processing windows. T h e errors in the automatic and manual image-based crown diameter estimates were comparable. Both sets of estimates tended to be low relative to ground measurements, probably because of the intersection of tree crowns and the failure to resolve branches at the outer crown extent which are visible from the ground. A more detailed summary of the results assessments and analyses follows: Recognition results: • T h e automatic recognition results were assessed twice, according to two different sets of rules. T h e liberal assessment, which de-emphasizes correct image-space localization, was intended to produce error counts that can be compared to the manual recognition results. T h e conservative assessment placed more emphasis on correct image-space localization. • T h e numbers of commission errors in the manual and the liberally assessed automatic recognition results are close: respectively 10% and 11% of the 340 sample trees. However, the number of liberally assessed automatic recognition omission errors (38%) is 2.8 times the number of manual recognition omission errors (14%) (cf. Table 6.21). T h e numbers of conservatively assessed errors are only slightly greater than the numbers of liberally assessed errors (cf. Table 6.22). • Inspection of the results for select test sample plots revealed evidence of the following: - some tree crowns were not recognized because direct solar irradiation that would otherwise have reached them was intercepted by neighbouring trees. — some recognition errors occurred because of the requirement for a large amount Chapter 6. Experiment 152 of overlap in the interpreted crown boundaries in cases where height displacement caused tree crowns to partially occlude each other — some large hardwood trees were unrecognized because they had an irregular crown form that was caused by growing under competition, and some because they had an basic crown architecture that does not correspond well to the simplifying assumptions of the tree crown image model — tight clusters of tree crowns were sometimes recognized as the directly irradiated portion of a single relatively large tree crown when the cluster image was juxtaposed with a dark image region along the image projection of the direct solar irradiation direction — some errors were produced by faulty integration of the results for adjacent processing windows • Most commission errors were due to the recognition of portions of tree crown images as separate relatively small tree crowns. • Pairs of opposing properties that correspond to pairs of disjoint test population subsets were defined, and for each pair the null hypothesis that equal proportions of those subsets would be automatically recognized (#0) was tested using the test sample tree recognition results (cf. Table 6.23). • T h e results of the significance tests provide strong evidence that Ho can be rejected for crowding variation between low and medium levels, and for dominance variation. There is also strong evidence that Ho can be rejected for species class variation (softwood vs. hardwood) when consideration is limited to trees with average or greater than average crown diameter, but not when consideration is limited to trees with smaller than average crown diameter. • T h e results of the significance test provide little or no evidence that Ho can be rejected for absolute column offset variation (even when consideration is limited to trees under Chapter 6. Experiment 153 medium or high crowding), for crowding variation between medium and high levels, or for crown diameter class variation (diameter greater than or equal to average vs. diameter less than average). Crown diameter estimation results: • Automat ic and manual image-based crown diameter estimates were compared to field measurements of crown diameter on the basis of two different sets of crown diameter classes: the full-resolution set (with 1.0 to 1.4 m wide class intervals) and the half-resolution set (with 2.2 to 2.3 m wide class intervals) (see Tables 6.27, 6.28, 6.29, and 6.30 for the error matrices). • Both the automatic and manual image-derived crown diameter estimates tended to be low for both sets of classes. • T h e overall agreement of the automatic image-based crown diameter classification with the field measurement-based crown diameter classification is 0.434 for the full-resolution classes and 0.707 for the half-resolution classes. • For each error matrix, the T a u coefficient permits the rejection of the hypothesis that the image-based crown diameter classification results only represent chance agreement, and do not permit the rejection of the hypothesis that the automatic and manual crown diameter image-based classifications are equally accurate. Chapter 7 Conclusion This dissertation discusses the design, implementation, and testing of a strategy for recognizing individual tree crowns in high spatial resolution aerial images of forests. Thi s work makes a contribution to the overall effort to increase the level of automation in forest type mapping. T h e strategy is based on the use of readily available scene and image formation knowledge to constrain the recognition task, which makes it unique within the problem domain. T h e knowledge is used to instantiate a tree crown image model, and the model instances are used to generate a set of initial recognition instances from which a training set of positive and negative exemplars is manually extracted. A recognition probability filter applies the training set to the selection of a subset of the initial recognition instances, which is then passed through a conflict resolution filter. T h e idea of using a pre-defined image model to support manual training is novel within the overall context of automated visual object recognition. Another novel idea that is incorporated into the strategy is the use of constraints on the spatial relationships among multiple neighbouring candidate recognition instances to resolve interpretation conflicts. T h e strategy was implemented and tested with a scene of mixed uneven-aged forests in which the trees represent a wide variety of species, size, and growing conditions. T h e test results were assessed and analyzed in detail and compared to human performance in the same task. T h e scene represented a level of difficulty that is significantly above the level that has been addressed by previous attempts at automating the tree crown recognition task. Also, the detail of the results assessment and analysis is greater than that of previous related work. Thi s work demonstrated that the implementation was largely able to accommodate the 1 5 4 Chapter 7. Conclusion 155 variation represented by the test scene. Recognition was successful in many cases where the tree crown image regions are not clearly delimited by a contrasting background region. Clear tree crown image region boundaries are relied on by previously implemented tree crown recog-nition strategies. However, this work also demonstrated that the recognition results that were produced by the implementation are less accurate than manually generated recognition results. T h e commission error levels in the automatically and manually generated recognition re-sults for 340 sample trees were practically the same (respectively 11% and 10%); however, the omission error level of the automatically generated results (38%) was almost three times that of the manually generated results (14%). Irregularities in tree crown form and irradiance that were caused by tight vertical and horizontal spacing of the crowns were the most significant sources of error in the automatic recognition results. Human interpreters were better able to accommodate these irregularities than the implementation was able to. T h e automatic and manual crown diameter estimation results for the automatically recog-nized trees do not differ significantly. Crown diameter estimation was significantly better for approximately 2.2 m wide diameter class intervals than for approximately 1.2 m wide diameter class intervals (the overall agreement values for the automatically generated results for these classifications and the field-collected reference data are respectively 0.71 and 0.43). Crown di-ameter was usually underestimated, probably because the full crown extents are usually not visible in the experimental image data. 7.1 Further Research T h e operational utility and relative merits of different automatic tree crown recognition strate-gies, including the one described in this dissertation, is still undefined primarily because oper-ational standards for the accuracy of individual tree crown recognition do not exist. Since the primary application of forest type mapping is to the estimation of mechantable timber volume in forest stands, further research should place a high priority on defining the level of tree crown recognition accuracy that adequately supports this task. Chapter 7. Conclusion 156 T h e conversion of scene and image formation knowledge into tree crown model instance sets, the definition of recognition regions, and the tuning of the components of the recognition procedure require considerable user input and experimentation. Further systemization of these tasks and possibly the development of support tools would significantly increase the operational potential of the tree crown recognition strategy. T h e training set that was used by the correct recognition probability filter in the main experiment consists of initial recognition instances that a human interpreter considers, with a high degree of confidence, to be either correct or incorrect. Further experiments should investigate the benefit of including in the training set initial recognition instances with less clearly visible evidence of correctness or incorrectness. Evidence of image contrast between tree crowns and background should be investigated as a cue for crown detection that may in some cases offset the effects of irregular crown form and irradiance. Such evidence may be incorporated as a feature that is used to estimate the correct recognition probability. T h e feature value could be computed as a function of the image values near the boundary of the initial recognition instance extent. T h e correct recognition results that are generated by the implementation provide a good basis for tree species classification. T h e image-space localization for a recognized tree crown includes the separation of the image regions for the directly irradiated and non-directly irra-diated portions of the visible crown surface. Thi s separation has been found to be important in experiments in automatic species identification from manually delimited tree crown image regions. It should be possible to investigate supervised tree species classification by extending the existing training set collection and nearest-neighbours interpolation procedures. T h e current implementation of the interpretation conflict resolution filter seeks to maxi-mize a function of the correct recognition probability values and spatial relationships for the intermediate recognition instances within uniform sized image windows. However, a window that is large enough to contain the image of a cluster of several large tree crowns may define an extremely large search space in parts of the image that predominately contain images of Chapter 7. Conclusion 157 relatively small tree crowns. This means that exact combinatorial optimization techniques such as backtracking are not generally practical for instances of the optimization problem. A n im-plementation of the filter that is based on variable sized windows may make such techniques practical and may possibly be more efficient than the current filter. A fundamental problem that must be addressed in following this approach is the development of a method for determining the best window size for a particular part of the image. In the main experiment, the component weights of the conflict resolution objective function were fixed over all processing regions. However, the experimental results suggest that match extent overlap should be penalized less in image regions where there is a large amount of relief displacement (and therefore partial occlusion of tree crowns by other tree crowns) than in regions where there is little or no relief displacement. T h e benefit of varying the component weights (in particular, the weight that controls the the match extent overlap) with image location should be investigated. A method of measuring the degree of confidence with which a final recognition instance can be regarded as correct should be developed. Such a confidence measure would be used to flag the recognition instances that should be manually verified. T h e correct recognition probability value for a final recognition instance might be one component of such a confidence measure. However, the level of initial ambiguity that is associated with the final recognition instance and was resolved by the conflict resolution filter might also be considered. Thi s would implement the notion that a greater level of initial ambiguity implies less confidence in the results. T h e level of initial ambiguity might be defined as a function of the correct recognition probability values and the image extents of the rejected intermediate recognition instances that conflict with final recognition instance: a rejected recognition instance with a relatively low correct recognition result or with an image extent that is relatively close to that of the final recognition instance would make a relatively small contribution to the level of initial ambiguity. T h e effectiveness of the confidence measure would be evaluated according to its effectiveness as a predictor of recognition errors. Bibliography A h e m , F . J . and D . G . Leckie (1987). Digital remote sensing for forestry: Requirements and capabilities, today and tomorrow. Geocarto International 2(3), 43-52. Ahern , F . J . , D . G . Leckie, and D . Werle (1993). Applications of R A D A R S A T S A R data in forested environments. IEEE Transactions on Geoscience and Remote Sensing 19(A), 330-337. Albers, B . J . , A . H . Strahler, X . L i , S. Liang, and K . C . Clarke (1990). Radiometric measure-ments of gap probability in conifer tree canopies. Remote Sensing of Environment 34 (3), 179-192. Aldred , A . H . and G . M . Bonner (1985). Applications of airborne lasers to forest surveys. Information Report PI-X-51, Petawawa National Forestry Institute, Chalk River, Ontario. Biging, G . S., R . G . Congalton, and E . C . M u r p h y (1991). A comparison of photointer-pretation and ground measurements of forest structure. In Technical Papers of the 1991 ACSM-ASPRS Annual Convention, pp. 6-15. Brickell, J . E . (1992). Delineation of map units for vegetation management. In H . G . L u n d , E . Landis, and T . Atterbury (eds.), Proceedings of Stand Inventory Technologies '92, Bethesda, Mary land , pp. 74-82. American Society for Photogrammetry and Remote Sens-ing. Cloney, E . and D . G . Leckie (1995). Analysis of M E I S interpreted tree count, sixth draft of an unpublished report prepared at the Petawawa National Forestry Institute, P . O . Box 2000, Chalk River, Ontario, K0J-1J0 . Cloney, E . E . , D . G . Leckie, and M . Gillis (1994). The PNFI Data Set (second ed.). P . O . Box 2000, Chalk River, Ontario, K0J-1J0: Petawawa National Forestry Institute. Cosandier, D . , T . Ivanco, and S. M a h (1992). T h e geocorrection and integration of the global positioning system with the compact airborne spectrographic imager. In J . K . Hornsby, D . J . K i n g , and N . A . Prout (eds.), Fifteenth Canadian Symposium on Remote Sensing, Toronto, Ontario, pp. 385-390. Draper, N . R. and H . Smith (1981). Applied Regression Analysis (second ed.). New York, New York: John Wiley &; Sons, Inc. F i t ch , J . P. (1988). Synthetic Aperture Radar. New York, New York: Springer-Verlag. Fraser, R . S., N . E . G a u t , E . C . Reifenstein, and H . Sievering (1975). Interaction mechanisms — within the atmosphere. In Manual of Remote Sensing, Chapter 5, pp. 181-233. Falls Church , Virginia: American Society of Photogrammetry. Friedman, J . H . , J . L . Bentley, and R. A . Finkel (1977). A n algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software 3(3), 209-226. 158 BIBLIOGRAPHY 159 Gardiner, M . (1965). T h e "superellipse": a curve that lies between the ellipse and the rect-angle. Scientific American 213(3), 222-232. Gausman, H . W . , W . A . Allen, C . L . Wiegand, D . E : Escobar, and R. R. Rodriguez (1971). Leaf light reflectance, transmittance, absorptance, and optical and geometrical parameters for eleven plant genera with different leaf mesophyll arrangements. In Proceedings of the Seventh International Symposium on Remote Sensing of Environment, A n n A r b o r , Michigan, pp. 1599-1625. Gibson, J . R . (1994). Photogrammetric calibration of a digital electro-optical stereo imaging system. Geomatica 4^(2), 95-109. Gillis, M . D . and J . A . Edwards (1988). Volume compilation procedures in forest management inventories. Information Report PI-X-79, Petawawa National Forestry Institute, Chalk River, Ontario. Gillis, M . D . and D . G . Leckie (1993). Forest inventory mapping procedures across Canada . Information Report PI-X-114, Petawawa National Forestry Institute, Chalk River, O n -tario. Gougeon, F . A . (1993). Individual tree identification from high resolution M E I S images. In D . G . Leckie and M . D . Gillis (eds.), Proceedings of the International Forum on Airborne Multispectral Scanning for Forestry and Mapping (with Emphasis on MEIS), Chalk River, Ontario, pp. 117-128. Forestry Canada . Gougeon, F . A . (1994). A valley following approach to the automatic delineation of individual tree crowns in high spatial resolution M E I S images, unpublished draft. Gougeon, F . A . (1995). Comparison of multispectral classification schemes for tree crowns individually delineated on high spatial resolution M E I S images. Canadian Journal of Remote Sensing 21(1), 1-9. Guyot , G . , D . G u y o n , and J . Riom (1989). Factors affecting the spectral response of forest canopies. Geocarto International 3, 3-18. Hakkila, P. (1989). Utilization of Residual Forest Biomass. Berlin: Springer-Verlag. Hershey, R . R . and W . A . Befort (1995). Aerial photo guide to new england forest cover types. General Technical Report NE-195, U S D A Forest Service, Radnor, Pennsylvania. Hogg, R . V . and A . T . Cra ig (1978). Introduction to Mathematical Statistics (fourth ed.). New York: Macmil lan Publishing C o . , Inc. Hooper, F . C , A . P. Brunger, and C . S. C h a n (1987). A clear sky model of diffuse sky radiance. Transactions of the ASME Journal of Solar Energy Engineering 109(1), 9-14. Horn , H . S. (1971). The Adaptive Geometry of Trees. Princeton, New Jersey: Princeton University Press. Horvath, R . , J . G . Braithwaite, and F . C . Polcyn (1970). Effects of atmospheric path on airborne multispectral sensors. Remote Sensing of Environment 1, 203-215. Hosie, R . C . (1969). Native Trees of Canada (seventh ed.). Canadian Forestry Service, De-partment of the Environment. .. . BIBLIOGRAPHY 160 Howard, J . A . (1991). Remote Sensing of Forest Resources. London, England: Chapman & Hal l . Hughes, J . S., D . L . Evans, and P. Y . Burns (1986). Identification of two southern pine species in high-resolution aerial M S S data. Photogrammetric Engineering and Remote Sensing 52(8), 1175-1180. Iqbal, M . (1983). An Introduction to Solar Radiation. D o n Mills , Ontario: Academic Press Canada . Jack, S. B . and J . N . Long (1992). Forest production and the organization of foliage within crowns and canopies. Forest Ecology and Management ^#(3-4), 233-245. Jacobs, D . M . , D . L . Evans, and J . C . Ritchie (1993). Laser profiler and aerial video data for forest assessments. In ASPRS Technical Papers in Remote Sensing: Proceedings of the 1993 ACSM/ASPRS Annual Convention and Exposition, New Orleans, L A , pp. 135-142. Johnson, D . S. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9(3), 256-278. Klecka, W . R. (1980). Discriminant Analysis. Beverly Hills, California: S A G E Publication, Inc. Koppel , A . and T . O j a (1984). Regime of diffuse solar radiation in an individual Norway spruce (Picea abies (L.) Karst.) crown. Photosynthetica 18(A), 529-535. Kuuluvainen, T . and T . Pukkala (1989). Simulation of within-tree and between-tree shading of direct radiation in a forest canopy: Effect of crown shape and sun elevation. Ecological Modelling 49(1-2), 89-100. Leckie, D . G . (1990a). Advances in remote sensing technologies for forest surveys and man-agement. Canadian Journal of Forest Research 20(A), 464-483. Leckie, D . G . (1990b). Synergism of synthetic aperture radar and visible/infrared data for for-est type discrimination. Photogrammetric Engineering and Remote Sensing 56(9), 1237-1246. Leckie, D . G . (1993). Application of airborne multispectral scanning to forest inventory map-ping. In D . G . Leckie and M . D . Gillis (eds.), Proceedings of the International Forum on Airborne Multispectral Scanning for Forestry and Mapping (with Emphasis on MEIS), Chalk River, Ontario, pp. 86-93. Forestry Canada . Leckie, D . G . (1994). Possible airborne sensor, processing and interpretation systems for major forestry applications. In Proceedings of the First International Airborne Remote Sensing Conference and Exhibition, Strasbourg, France, pp. 11:159-169. L i , X . and A . H . Strahler (1985). Geometric-optical modeling of a conifer forest canopy. IEEE Transactions on Geoscience and Remote Sensing 23(5), 705-720. Lowe, D . G . (1995). Similarity metric for a variable-kernel classifier. Neural Computation 7, 72-85. M a , Z . and R. L . Redmond (1995). T a u coefficients for accuracy assessment of classification of remote sensing data. Photogrammetric Engineering and Remote Sensing 61(A), 435-439. BIBLIOGRAPHY 161 M c C o l l , W . D . , R . A . Neville, and S. M . T i l l (1983). Multidetector electro-optical imaging scanner, M I E S II. In Proceedings of the Eighth Canadian Symposium on Remote Sensing, pp. 71-77. McDowel l , D . Q . (1974). Spectral distribution of skylight energy for two haze conditions. Photogrammetric Engineering 40(5), 569-571. Minnaert , M . (1941). T h e reciprocity principle in lunar photometry. Astrophysics Journal 93, 403-410. M u r g u , D . (1996). Individual tree detection and localization in aerial imagery. Master's thesis, Department of Computer Science, University of British Columbia . O'Brien , R . and D . C . Chojnacky (1992). T h e potential for describing structural elements of bird habitat with forest inventory data. In H . G . L u n d , E . Landis, and T . Atterbury (eds.), Proceedings of Stand Inventory Technologies '92, Bethesda, M a r y l a n d , pp. 204-212. American Society for Photogrammetry and Remote Sensing. Oker-Blom, P. and S. Kellomaki (1982). Theoretical computations on the role of crown shape in the absorption of light by forest trees. Mathematical Biosciences 59(2), 291-311. Oliver, R . E . , J . K . Berry, and J . A . Smith (1975). A portable instrument for measuring apparent directional reflectance. Optical Engineering 14(3), 244-247. Otten, R . H . J . M . and L . P. P. P. van Ginneken (1989). The Annealing Algorithm. Boston, Massachussets: Kluwer Academic Publishers. Pinz, A . J . (1991). A computer vision system for the recognition of trees in aerial pho-tographs. In J . C . Ti l ton (ed.), Multisource Data Integration in Remote Sensing, pp. 111-124. Greenbelt, Mary land: National Aeronautics and Space Administrat ion. Pratt , W . K . (1991). Digital Image Processing (second ed.). New York, New York: John Wiley & Sons, Inc. Rowe, J . S. (1972). Forest Regions of Canada. Ottawa, Ontario: Department of the Environ-ment, Canadian Forestry Service. Publication No. 1300. Sayn-Wittgenstein, L . (1978). Recognition of tree species on aerial photographs. Information Report F M R - X - 1 1 8 , Forest Management Institute, Ottawa, Ontario. Schreuder, H . T . , T . G . Gregoire, and G . B . B . Wood (1993). Sampling Methods for Multire-source Forest Inventory. New York, New York: John Wiley &; Sons, Inc. Schroer, G . L . (1992). Methods for sampling wildlife habitats. In H . G . L u n d , E . Landis, and T . Atterbury (eds.), Proceedings of Stand Inventory Technologies '92, Bethesda, M a r y -land, pp. 204-212. American Society for Photogrammetry and Remote Sensing. Siala, F . M . F . , M . A . Rosen, and F . C . Hooper (1990). Models for the directional distri-bution of the diffuse sky radiance. Transactions of the ASME Journal of Solar Energy Engineering 112(2), 102-112. Silva, L . F . (1978). Radiation and instrumentation in remote sensing. In P. H . Swain and S. M . Davis (eds.), Remote Sensing: The Quantitative Approach, Chapter 2, pp. 21-135. New York, New York': M c G r a w - H i l l Book Company. BIBLIOGRAPHY 162 Sproull, R . F . (1991). Refinements to nearest-neighbor searching in fc-dimensional trees. Al-gorithmica 6(4), 579-589. Story, M . and R. G . Congalton (1986). Accuracy assessment: A user's perspective. Pho-togrammetric Engineering and Remote Sensing 52(3), 397-399. Thomasson, J . A . , C . W . Bennet, B . D . Jackson, and M . P. Mailander (1994). Differentiating bottomland tree species with multispectral videography. Photogrammetric Engineering and Remote Sensing 60(1), 55-59. Turk , M . and A . Pentland (1991). Eigenfaces for recognition. Journal of Cognitive Neuro-science 3(1), 71-86. Wang, Y . P., P. G . Jarvis, and M . L . Benson (1990). Two-dimensional needle-area density distribution within the crowns of pinus radiata. Forest Ecology and Management 32(2-4), . 217-237. Warbington, R . and J . Levitan (1992). How to estimate canopy cover using maximum crown w i d t h / D B H relationships. In H . G . L u n d , E . Landis, and T . Atterbury (eds.), Proceedings of Stand Inventory Technologies '92, Bethesda, M a r y l a n d , pp. 319-328. American Society for Photogrammetry and Remote Sensing. Wil l iams, D . L . (1991). A comparison of spectral reflectance properties at the needle, branch, and canopy level for selected conifer species. Remote Sensing of Environment 35(2 & 3), 79-93. Woodham, R. J . and M . H . Gray (1987). A n analytic method for radiometric correction of satellite multispectral scanner data. IEEE Transactions on Geoscience and Remote Sensing 25(3), 258-271. Young, A . T . and S. A . Collins (1971). Photometric properties of the Mariner cameras and selected regions on Mars . Journal of Geophysical Research 76(2), 432-437. Appendix A Sample Plot Display Triplets 163 Appendix A. Sample Plot Display Triplets 166 Figure A.41: Plot boundary, reference and results displays subimages for sample plots 9 (top) to 12 (bottom). Appendix A. Sample Plot Display Triplets 167 Figure A.42: Plot boundary, reference and results displays subimages for sample plots 13 (top) to 16 (bottom). Appendix A. Sample Plot Display Triplets 168 HI pig; ^ ^ ^ ^ §§1* Figure A.43: Plot boundary, reference and results displays for sample plots 17 (top) to 20 (bottom). Appendix A. Sample Plot Display Triplets 169 Appendix B Index to Term and Acronym Definition Page Numbers 170 Appendix B. Index to Term and Acronym Definition Page Numbers 171 acceptance function, 83 locally variable parameter, 58 alignment registration feature, 52 manual diameter estimate, 144 annealing chain, 87 Markov chain, 84 apex location, 49 Markov matrix, 84 automatic diameter estimate, 144 M E I S II, 2 border tree, 97 Minnaert reflectance function, 39 C A S I , 16 model instance set, 55 chain limit theorem, 86 move set, 83 comprehensive image model, 22 multiply covered location, 81 conservative assessment, 131 normalized vector, 51 control parameter, 83 null selection, 80 correct recognition probability, 28 opaque surface model, 39 coverage count map, 88 optical axis image point, 33 covered location, 81 overall agreement, 147 crown cell, 39 pattern correlation, 53 detection, 17 pattern difference, 53 diffuse irradiance, 36 pattern, 53 direct irradiation pixel, 73 permeable volume model, 40 direct irradiance, 36 pitch angle, 47 direct irradiation locations, 49 plot boundary display, 129 dominating set, 61 point features, 49 eigenface, 23 principal component, 24 equilibrium density, 86 processing region, 78 error matrix, 145 producer's accuracy, 146 exemplar, 70 projection vector, 32 exitant angle, 39 quasi-equilibrium, 87 extent centroid location, 49 recognition instance selection, 80 extent difference, 52 recognition instance, 26 extent location, 49 recognition region, 55 extent similarity, 52 reference classification, 145 flightline azimuth, 47 reference display, 97 flightline, 33 reflexivity, 86 forest type map, 5 registration feature, 51 gap probability, 40 repeat runs, 75 G C P , 16 results display, 129 generalized ellipse, 31 roll angle, 47 generalized ellipsoid of revolution, 31 S A R , 10 G E R , 31 scanline, 33 GIS, 7 scene element, 1 G P P D , 11 score function, 83 G P S , 10 selection function, 83 Helmholtz reciprocity condition, 40 similarity metric, 71 identifier map, 63 simulated annealing, 83 incident angle, 39 singly covered location, 81 INS, 10 solar azimuth, 36 Lambertian reflectance function, 40 solar zenith angle, 36 liberal assessment, 130 space connectivity, 86 L I D A R , 14 state-space, 83 localization, 17 surface cell, 39 Appendix B. Index to Term and Acronym Definition Page Numbers surface point, 39 symmetry, 86 template matching, 22 test classification, 145 test population, 125 test sample plot, 125 test sample tree, 125 total irradiance, 36 training set, 70 transition matrix, 84 uniform-extent subset, 55 user's accuracy, 146 visible understory tree, 97 volume array, 39 

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051597/manifest

Comment

Related Items