Object-Based Image Analysis PDF

Object-based Image Analysis S LANG / D TIEDE Tutor: M DANESHFAR 5 – Image Segmentation [summary] Content: 1. Brief history 2. Image segmentation in remote sensing 3. Groups of segmentation algorithms 4. Multi-resolution segmentation - role of homogeneity as a key criterio...

Object-based Image Analysis S LANG / D TIEDE Tutor: M DANESHFAR 5 – Image Segmentation [summary] Content: 1. Brief history 2. Image segmentation in remote sensing 3. Groups of segmentation algorithms 4. Multi-resolution segmentation - role of homogeneity as a key criterion 5. Object features – overview 6. Adaptive, parcel-based segmentation ---------------------------------------------------------------------- Two pillars of OBIA:  Segmentation  Classification Brief history of segmentation: 1980s:  First developments of image segmentation (in industrial computer vision)  Robert Haralick & Linda Shapiro (1985), “Image segmentation techniques“ - Has set a benchmark in the development with a first consolidated overview of existing approaches 1990s: 1   Image segmentation became more prominent in Earth observation image analysis – Emerge of commercial and free software for open scientific community.  Most algorithms were developed for single-band, unreferenced, B&W imagery. 2000s:  Development in remote sensing because of the advent of very high resolution (VHR) data. What is Segmentation?  Segments in general: portions of a linear feature e.g. limbs of a chain or a wooden snake  Segments in GIS analysis: portions of linear features e.g. roads or tracks performing 1-dimensional continuous geo-referencing, or even dynamic segmentation (according to address data)  Segments in image segmentation  principle is the same but we move from 1 dimensional to 2(or 3) dimensional geographical space  The entire space (image) will be cut into smaller pieces (2/3 dimensional geographic space) o Fairly same size in pieces o The entire space is considered o No gaps and no overlaps between pieces o Example: Hierarchical system of administrative units (Top-down view, no gap or overlapping regions) Austria:  1 State  9 provinces  127 districts  237 communities Regionalization: Example: Coping with the Euro challenge, it requires a complete political re-organisation of Europe. Completely forget the existing structure; the European Union should become the United Regions of Europe (URE) of 30 regions.  A bottom-up approach! Such regions: Should not be too small in size Relatively homogenous in terms of their internal structure Quite distinct to each other The criterion to build such regions should be objective and transparent 2 Criterion: the natural language spoken by children in primary schools o Merging all neighbouring villages with primary schools with the same dominating natural language. o This process could lead to very small regions (‘language islands’)  so the initial regions should be merged further according to language relationships, which are to be decided by linguists. Use the term ‘Regionalization’ to pay tribute to the fact that we use two aspects from grouping:  Similarity in attribute  Similarity in space. Illustration of this strategy (bottom-up regionalization) in another experiment: Practicing a fire alarm exercise in a school, 500 students class by class enter the gym, and place there according to their sequence of arrival. So… There would be cluster for each class Chance is very high to meet the majority of students at their class cluster, even if some of them move around In the time of going back to their classes, the strict spatial separation into classes gets loosened a bit with some students intermingling with each other But the majority of students would still be around in their initial cluster According to two previous examples:  It is possible to cluster a phenomena in space according to similar properties  It is usual that spatially related things have something in common In image segmentation, following:  First law of geography by Waldo Tobler  Principle of spatial autocorrelation  We can trust in the fact that there will be homogeneous regions belonging to specific classes with a reasonable number of similar pixels. Satellite images: Composed by an array of pixels Specific spectral value for each pixel in each spectral band, depending on the radiometric resolution (value range: 256 in the case of 8 bit, and 2048 in the case of 11 bit) These pixels are similar in a certain spatial surrounding (the same tendency as the neighbouring schools or the classmates have) Our initial criterion is similarity in spectral reflectance 3  Value of a pixel: degree of reflectance in a certain spectral band width, a pseudo-continuous digital coding While there are numerous possible values (namely 256 different ones in an 8-bit coding), still neighbouring pixels tend to have similar values. Image event (token): Consider the simple case of an image of two darker objects lying on a bright table. By laying a spectral profile over this table, covering the two objects, and then looking at the brightness values, we will see that over a certain distance along this profile, the values are changing. Since these events have certain spatial extent, we use the term token or constellation token. To apply the top-down view and dissect the geographical reality in smaller, distinct units, consider a random choice of a portion of an image array: Pixel values are quite similar at neighbouring pixels (spatial autocorrelation)  These pixels can be grouped [Pixel values are not the same, but they tend to range around a certain average value] There are gradual changes in boundaries For example a rural area with larger areas covered by Grassland Forests water bodies such as lakes Hovering over the image, we’ll find numerous neighbouring pixels representing grassland and then, gradually, they change to forest pixels. Object: Combination of certain amount of pixels Segmentation in a form of Regionalization on two aspects:  In feature space (similarity in feature): level of detail  depends on resolution  In real space (similarity in location) The level of detail of the features we can reach depends on the image resolution. Rule of thumb: pixel size needs to be by a factor of 3 to 4 smaller than the objects to be represented. Note:  It is not easy to ultimately judge the quality of the segmentation against the manual drawing  We cannot say segmentation is right or wrong. We may say it seems not to be adequate or appropriate. 4   One common difference is that human delineations are scaled representations, while the segmentation results are not. Different segmentation results can be provided according to: Different strategies and routines Different parametrizations within the routine Using heuristic algorithms, which even the results of the segmentations with the same parametrization may differ Judgment of segmentation results with visual perception depends on: Types of object we are looking at Scale domain we are working in Our specific expert knowledge in this area In matching segmentation results against what human perception would delineate, there may be some problems occurring: Bad performance of the algorithm due to poor parametrization Bad choice of proper algorithm Inherent limitations of segmentation algorithms: (e.g. conceptual boundaries, orchard problem) Lang 2008: In object-based image analysis, the ‘image object’ is the central methodological element and as an object of investigation, it resides somewhere between application-driven plausibility and technology-driven detectability. To this end, we can join image segmentation with knowledge-based classification. Image segmentation decreases the level of detail, reduces image complexity, and makes image content graspable. Segmentation produces image regions and these regions, once they are considered ‘meaningful‘ become image objects; in other words an image object is a ‘peer reviewed‘ image region; refereed by a human expert. A pixel as a technically defined unit can be interpreted in terms of its spectral behavior, in terms of the aggregation of spectral end-members, or in terms of its neighborhoods. A pixel cannot be assigned a valid corresponding real-world object, but an image object can. Overcoming the pixel view and providing image objects that ‘make sense‘ opens a new dimension in rule-based automated image analysis; image objects can be labeled directly using a range of characteristics, including spatial ones, or they can be used for modelling complex classes based on their spatial relationships. Coupled with e.g. a rule-based production system we can make expert knowledge explicit by the use of rules. The practical aim of image segmentation is to find an optimum match between image objects and geographical features. 5 Segmentation algorithms There are hundreds of different segmentation algorithms  Pixel-based or Histogram-based o Thresholding technics  Edge-based o Laplace filter o Sobel-operator  Region-based o Region growing o Split and merge  Non-image related: Do not obey similarity in features, regions defined without any relation to the image content  special case: regular tiles (according to geometric principle) o Chessboard segmentation o Honeycomb segmentation Histogram-based segmentation:  Thresholding techniques  Simplest way to have exhaustive segmentation  Perform segmentation within feature space  pseudo-segmentation  Ignoring the spatial dimension in real space  A form of Unsupervised classification: leading to classes but not to spatially contiguous regions Edge-based Segmentation: Edge: Clear boundary between homogenous areas, detectable by edge-sensitive algorithms (filters)  Finding edges between homogeneous areas (objects and background)  Usually include filtering (e.g. Li Sigma, Sobel) and enhancement prior the edge detection  Combining the detected edges to form a boundary Edge-based segmentation workflow Edge detection o Filtering/smoothing: to decrease noise in image o Enhancement: revealing local changes in intensities o Detection: select edge pixels e.g. by Thresholding o Closing of gaps/deleting artefacts o Combining, extending of lines Linking the edge pixels to form boundaries 6 Region-based segmentation:  Deliver regions  Starts with a set of seed pixels (seed are distributed over image randomly or content-related – Bottom-up or Top-down)  Growing regions by adding neighboring pixels as long as homogeneity criterion applies  Two neighboring regions are unified, if homogeneity applies  Region merging continues until a scale-dependent threshold in size is reached  Techniques: o Region growth o Region merging o Splitting Region-based segmentations:  Watershed  Split and merge  Multi-resolution  Adaptive-parcel based Watershed Segmentation:  Introduced by Haris et al. 1998  Intuitive and transparent  Spectral reference is modelled as height values  Segments are built at gradient magnitudes along similar elevation levels. [The same as water flowing into valleys between watersheds. Region growing stops when neighbouring flooded areas meet each other. (Virtual flooding)]  Higher scale segmentation is achieved by decreasing the number of local minima Problems:  In an initial stage the algorithm leads to over segmentation  To separate adjacent objects it is needed to be actively controlled by markers. It only depends on spectral similarity, so objects may vary significantly in size Split-and-merge algorithm:  Top-down quad-tree principle  Divides an image into n (usually 4) regular sub-regions (e.g. squares)  Dividing will continue until a certain level of homogeneity is reached  Heterogeneous squares are subdivided again  Homogeneous squares merge together 7 Multi-resolution Segmentation  Mimics human eye  Establishing several segmentation levels within one image (segmentation in hierarchical scale domains) – reflecting hierarchical structure of reality  Segmentation levels interlinked  Reproducibility  Universality  Implemented in eCognition software o Local mutual best fitting approach o Utilization of combined homogeneity and shape concept in algorithm o Strictly hierarchical Homogeneity: Literally means, of the same origin; in image analysis, means similarity  Not a complete equality  Similarity in certain properties  Similarity in spectral behavior (digital number) Classification: Grouping single elements according to their properties, no matter where they are located or how they are spatially organized.  Result of a pixel by pixel classification  categorical map  Type of space  Result of segmentation  Region  Always spatially connected (contagious), maximum internal homogeneity, and maximum external heterogeneity Primary objective of segmentation  Dissection of space to parts which are fairly the same size and covering without gaps or overlaps the entire space.  Similarity in properties is just an auxiliary means to do that.  Segmentation employs some basic or rather advanced routines for optimizing the spatial arrangements of regions (controlling the degree of complexity of borderline, or the compactness of the created regions) The common principle: Image dissection in several levels, image scene in multiple scales. Multi-scale segmentation:  Image information is represented in various scales  The interpreter has to decide which level to maintain as relevant and which ones to dismiss 8   It is matter of trial and error Lang (2002) said “How to hit the relevant scale? “  Concept of regionalized hierarchies: according to predominating land-use types, certain hierarchy levels apply. ESP (Estimate Scale Parameter) tool:  Developed by Dragut et al.  Statistical estimation to determine a proper scale of delineation  Taking into account local variance among objects and rate of change in variance between levels  Applied to the entire image Multi-scale image analysis enables a skilled user to draw hierarchical representation of a landscape from a remotely-sensed image. Multi-leveled structural representation of natural habitats reflects the idea that  Natural living are hierarchically structured  So they are near-decomposable Hierarchical structure: o Level +1: higher level o Level 0: Focal level o Level -1: Lower level o Pixel level How to build object hierarchy: Two strategies in terms of geometrical coherence: Scale-adoptive Scale-specific Scale-adoptive segmentation:  To build up a strict hierarchical system  Boundaries of a sub-object fully coincide with boundaries of a super-object  One super-object has exactly ‘n‘ sub-objects  One sub-object belongs to exactly one super-object Scale-specific segmentation:  More close to human delineation  Generalized and truly scaled representation of each level 9   Coincidence of the boundaries is not fully accomplished  There is a spatial congruence of higher and lower level objects Implementation of multi-scale segmentation algorithm in eCognition:  Bottom up region merging technique  Each pixel as a region  Merging a pair of region into one region (each merging has a merging cost)  Merging into bigger objects as long as o homogeneity criteria fulfills o The cost is below ‘least degree of fitting‘ o Least degree of fitting= scale parameter  Establishing segmentation levels on several scales using different scale parameters (e.g. 2nd level based on 1st level: larger scale parameter results in larger objects consisting of the objects of the 1st level) Decision heuristics: For an arbitrary object ‘A’ find an adjacent object ‘B’ for merging  Fitting: fulfillment of homogeneity criteria  Best fitting: when merging produce the best degree of fitting compared to other merging of ‘A’ with other neighbors.  Local mutual best fitting: find the best fitting object B for A, then find the best fitting object C for B, confirm object C is object A, otherwise take B for A and C for B and repeat the process. Find the best fitting pair of objects in the local vicinity of A following the gradient of homogeneity  Global mutually best fitting: merge the pair of objects for which the homogeneity criterion is fulfilled best in the whole image. How to define degree of fitting (in eCognition): Two objects are similar to each other when they are close to each other in feature space  Color homogeneity  Shape homogeneity o Compactness: Relation between boundary length 𝑙 of the object and the square root of the number 𝑛 of the pixels of the object (square root of 𝑛 equals the side of a square with n pixels). (Ideal compactness  objects do not become lengthy) o Smoothness: Relation between boundary length 𝑙 of the object and the perimeter of the bounding box of the object (bounding box: shortest possible boundary length). (Ideal smoothness  boundaries do not become fringed) 𝑙 ℎ𝑐𝑜𝑚𝑝𝑎𝑐𝑡 = √𝑛 𝑙 ℎ𝑠𝑚𝑜𝑜𝑡ℎ = 𝑏 10  𝑙 = 𝑏𝑜𝑢𝑛𝑑𝑎𝑟𝑦 𝑙𝑒𝑛𝑔𝑡ℎ 𝑛 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑝𝑖𝑥𝑒𝑙𝑠 𝑜𝑓 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡 𝑙 = 𝑝𝑒𝑟𝑖𝑚𝑖𝑡𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑏𝑜𝑢𝑛𝑑𝑖𝑛𝑔 𝑏𝑜𝑥 𝑜𝑓 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡 Compactness and Smoothness make up the shape homogeneity and are weighted against each other Color and Shape are weighted against each other Multi-resolution Segmentation parameters (in eCognition): Scale: relative average size Shape: (weighted against color) Compactness: (weighted against smoothness) Domain specific segmentation: ‘Regionalized hierarchies’ can be operationalized by first establishing so-called image domains, such as forest or open land. Within these domains, we can perform specific segmentation, by controlling the parameters independently. This is called ‘Domain specific segmentation’. Object features: Pixels  Characterized by one single feature: the spectral reflectance (The same applies to individual grid cell of a digital elevation model) Objects  Created by regionalization of neighboring similar pixels / aggregated pixel (or grid) values. Characterized by multitude of features (different kinds of descriptive statistics, spatial, neighboring, hierarchical features…) Example: A group of students belonging to the same class has certain characteristics, such as: Average age, the eldest, and the youngest. The same is for every object.  Object feature  Basic descriptive statistics o Mean spectral value 11  o standard deviation o min o max  Spatial (geometrical) features o Form o Perimeter  Textural properties o Layer value texture (mean of sub objects) o Shape texture (direction of sub objects)  Hierarchical features o Number of higher levels o Number of super and sub objects  Class-related features  Relations to classes o neighbouring features o Sub objects o Super objects  Membership to … Parcel-based segmentation:  Often it happens that boundaries are already available, e.g. existing agricultural field boundaries, cadastral maps…(as the example of field boundaries is the most obvious, we may use the term per-parcel or parcel- based segmentation, even for applications where existing boundaries other than parcel borders are used)  In this segmentation, according to internal characteristics, objects are… o Retained o Aggregated o Split apart Why cadastral maps are favorite target geometries for decision makers and planners? Cadastral boundaries are the  Ultimate spatial reference  Precise and legitimate and thereby undisputable But some problems arise from the inconsistency…  Digital cadastral data are most precisely mapped administrative data, if combined with e.g. a 5 meter SPOT scene, the data will be inconsistent resolution-wise  The cadastral data have been captured at scale of 1:500 up to 1:1000, and the SPOT scene serves a scale range of up to 1:50000 or more, the data will be inconsistent scale-wise. Even if we had the highest resolution imagery we still face the challenge that o Not all of the cadastral boundaries have meaning in the image o There are boundaries that are missing 12 Solution: adaptive-parcel based segmentation  A parcel whose internal homogeneity is sufficient remains the same  Neighboring parcels with similar spectral characteristics are merged  A single heterogeneous parcel is split and new boundaries are generated Finally landscape spatially homogeneous objects are generated which can be used for class modelling. Advantages of adaptive-parcel based segmentation approach:  Cost efficiency  High matching degree of the produced geometry  Transferability to similar cases (due to standardized character of the datasets involved) 13