Region Growing Segmentation

From AWF-Wiki
(Difference between revisions)
Jump to: navigation, search
(→‎QGIS Individual Tree Crown Segmentation Method)
Line 1: Line 1:
−
== QGIS Individual Tree Crown Segmentation Method ==
+
=Region Growing Segementation with Saga's Seeded Region Growing Tool=
−
Different QGIS geoalgorithms are implemented in order to segment a greyscale single-band Canopy Height Model (CHM) raster using a Region Growing approach. These are the steps you need to follow to use the Image Segmentation Model. The following procedure is explained using QGIS version 2.12.2.
+
−
# Download the [[:File:model_segmentation.zip|*.model file]] (extract .zip after download).
+
−
# Open QGIS and go to the Processing Toolbox; if the Toolbox is not opened go to {{mitem|text= Processing → Toolbox}} to activate it. Once the Toolbox is opened go to {{mitem|text= Models → Tools → Add model from file}} and load the previously downloaded model.
+
−
# The model should appear in the Models tab. Double click on it to execute.
+
−
# A window showing the different inputs and outputs should appear, just as if you were using any other geoalgorithm.
+
−
# You will need to provide the model with the [[:File:CHM.tif|CHM (download here)]] and a [[:File:Corrected_Bound.zip|polygon shapefile  (download here)]] containing the boundary of the plot that you want to segment.
+
−
# The main output is called ''Segments_noGaps'', you can disable the rest since they are only used when creating the Model to check if every step is working properly.
+
−
# If any error window from Python pops up close it and the model will continue running properly. This error windows should not imply any error on the results of the model.
+
  
−
== Model Description ==
+
The following tutorial explains how to delineate tree crowns, using SAGA's Seeded Region Growing Tool. The product, a polygon shapefile, can then be used in an object based classification, f.ex. in order to classify different tree species.
−
To access the Model script right click on it and select Edit model. Here are the steps followed in the model in order to obtain the final segmentation.
+
−
# Starting from the CHM, SAGA’s {{button|text=Seed generation}} geoalgorithm is performed three times changing the ''Bandwith'' parameter each time. A big bandwidth value will be used for extracting big crowns, the lowest value has been used to extract the seeds belonging to small crowns and the intermediate value for the places where there should be no crowns (gaps). These values can be changed for optimizing the model to the current CHM.
+
  
−
::Note: The {{button|text=Seed generation}} parameters can be modified according to the type of forest under study. The example here described has been adjusted to a broad-leaved forest with a high tree crown cover.
 
  
−
# The seeds in point shapfile format generated for the gaps have to be filtered using the QGIS geoalgorithm {{button|text=Extract by attribute}}, applying a height threshold in order to keep just the seeds related to those places without tree crowns, e.g. those with a height value lower than 5 meters.
+
 
−
# To avoid over-segmentation, a buffer around the seeds obtained for the large crowns has to be carried out using the QGIS geoalgorithm {{button|text=Fixed distance buffer}}. Afterwards, this buffer will be used to filter the points from the small crowns seeds, keeping only those points outside of the buffer. For this purpose, QGIS geoalgorithm {{button|text=Difference}} was used.
+
 
−
# SAGA’s geoalgorithm {{button|text=Merge layer}} is used for merging all the final seed shapefiles.
+
=Material you need to complete the tutorial=
−
# Merged seeds are rasterized using GDAL’s function {{button|text=Rasterize (vector to raster)}}. The resolution of the output raster has to match the CHM’s resolution. In this case, the resolution is set to 0.25x0.25.
+
 
−
# The CHM and the rasterized seeds have to be clipped by the extent of the plot’s boundary (*.shp) using {{button|text=Clip raster by mask layer}} from GDAL.
+
'''Data'''
−
# SAGA’s {{button|text=Simple region growing}} is performed using the previous clipped raster files as inputs. All the parameters are set as default, except for the “Threshold – Similarity” which is set at 0.0001 in order to cover the entire plot with the regions.
+
 
−
# Parallel to this step, a mask for the gaps is created for later on clipping the gaps out of the segments.  
+
A multispectral image of the forest canopy
−
#* Using the {{button|text=Raster calculator}} from GDAL with the CHM as input (“Input layer A”). The condition set is “A<5” so that the calculator returns a raster where, if the condition is true a value of 1 is assigned, and if not, a 0.
+
 
−
#* Afterwards, the generated raster is polygonized and the mask is generated by extracting the polygons with a value of 0 in the attribute table by using QGIS geoalgorithm {{button|text=Extract by attribute}}.
+
A canopy height model [[Canopy_Height_Model_based_on_Airborne_Laserscanning_using_LAStools#Create_a_CHM_directly_from_height-normalized_points:_lasthin_and_las2dem|CHM]]
−
# Finally, the segments generated in the simple region growing are clipped with the gaps mask using {{button|text=Clip raster by mask layer}} from GDAL. This raster is clipped again with the boundary of the plot for being able to run {{button|text=Hoover metrics}}, from Orfeo Toolbox, if necessary.
+
 
 +
'''Software'''
 +
 
 +
QGIS 2.18.11
 +
 
 +
SAGA 2.3.2
 +
 
 +
 
 +
 
 +
=Split multiband image into several raster images=
 +
 
 +
SAGA's Region Growing Algorithm works only with single band images. Therefor, we have to split our multiband image into its individual bands following [[Split_stack|these instructions]].
 +
 
 +
 
 +
 
 +
=Seed points=
 +
 
 +
 
 +
The first step here is to extract  the position of the tree tops, which are going to be the starting point for the region growing algorithm. You find a description of how to derive the seed points from a CHM [[Individual_Tree_Detection_(ITC)|here]] .
 +
Now have a look at how the seeds align with your multiband image
 +
 
 +
 
 +
[[File:Unfiltered_seed_points.PNG]]
 +
 
 +
 
 +
In this picture you see, that the points align well with the tree tops. However, there are many points that represent small trees (in the lower left corner) which you might not be so interested in. In order to correct that, we are going to filter the points by their height in the seed shapefile and save the shapefile with the selected seeds only as a new shapefile.
 +
If the seed points do not fit the image well, it might be due to the fact that you are using an orthophoto and not a true orthophoto. If you are working only with a smaller dataset you can help it by using the {{button|text=Georeferencer}} in the {{button|text=Raster menu}} by rubberheeting your orthophoto to make it fit. You'll find the instructions for doing so [[Georeferencing_of_UAV photos|here]].
 +
 
 +
 
 +
This looks much better:
 +
 
 +
 
 +
[[File:Filtered_seed_points.PNG]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
=Seed point rasterization=
 +
 
 +
 
 +
In order to use the seed points in the region growing algorithm in SAGA, we have to convert the vector file to a raster file using the {{button|text=Rasterize}} module from the GDAL Conversions in QGIS. It is critical that we create a raster file that only contains the seed points and no-data. So every pixel outside the seed points has to be no-data. It is also critical that our rasterized vector image has the '''exact same''' CRS (Coordinate reference system), extend and pixel size as the single band images.
 +
 
 +
* In the {{button|text=Processing Toolbox}}, type 'rasterize' and select the {{button|text=Rasterize}} tool ind the SAGA geoalgorithms submenu
 +
* Select the seed point shapefile as input
 +
* Select {{button|text=ID}} as {{button|text=Attribute}} and the other parameters according to the screenshot below
 +
* Select the extend of one of the band splits as extend by clicking {{button|text=select canvas/ layers extend}} in the {{button|text=Output extend}} line
 +
* Copy the '''exact''' cellsize from either the metadata of one of your split images and set output raster size to {{button|text= Output resolution in map units per pixel}}
 +
* Save to a local file
 +
 
 +
 
 +
 
 +
[[File:Rasterize.PNG]]
 +
 
 +
 
 +
 
 +
The result should look like this:
 +
 
 +
 
 +
 
 +
[[File:Universe2.PNG]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Now verify that the newly created seed point raster aligns 100% with one of the band split rasters by checking the metadata or {{button|text=Save raster layer as..}} mask  and by zooming into the seed pixels. Also check with the Info button[[File:Info.PNG]], if any pixel which is not a seed point, is no-data.  
 +
 
 +
 
 +
[[File:Saveas.PNG]]
 +
 
 +
 
 +
Your raster should align like this:
 +
 
 +
 
 +
[[File:Seedpixel.PNG]]
 +
 
 +
=Superimpose Vector=
 +
 
 +
It happens regularly that, although following the previous steps meticulously, that the extend and pixel size of the rasterized vector file does not match the splitted band images 100 %. In this case we have to use the OTB  {{button|text=Superimpose Vector}} tool that you can find in the {{button|text=Processing Toolbox}}.
 +
 
 +
* Open the  {{button|text=Superimpose Vector}} tool in the {{button|text=Processing Toolbox}}.
 +
* Select one of the split band images as {{button|text=Reference input}}
 +
* Select the rasterized seed point shapefile as {{button|text=The image to reproject}}
 +
* Fill in the other parameters as shown here:
 +
 
 +
[[File:Superimpose.PNG]]
 +
 
 +
 
 +
Next, go to the {{button|text=Properties}} of the newly created layer in the {{button|text= Layers Panel}}
 +
 
 +
* Check the extend of the layer in the {{button|text=Metadata}} tab.
 +
* Go to {{button|text=Styles}}, load max/min values and set the {{button|text=Color Gradient}} to {{button|text=White to black}}
 +
 
 +
The result should look very much the same as the first rasterized vector, but the extend and pixel size are now 100 % the same as in
 +
 
 +
the split band images.
 +
 
 +
 
 +
=Region Growing in SAGA=
 +
 
 +
Now we finally made it to the fun part of the whole exercise, which is creating the segments around the tops of the trees i.e. the seed points. Therefor we open SAGA GIS.
 +
 
 +
* When prompted, select an empty Startup Project
 +
 
 +
[[File:SAGA1.PNG|300px|]]
 +
 
 +
 
 +
* Click the [[File:SAGA2.PNG]] button
 +
 
 +
* Change [[File:SAGA3.PNG|150px|]] to {{button|text=All files}}
 +
 
 +
 
 +
* Open all split band images and the superimposed seed raster '''one after another'''
 +
* The layer panel on the left should now look like this:
 +
 
 +
 
 +
[[File:SAGA4.PNG]]
 +
 
 +
 
 +
* In the line below {{button|text=Grids}} you see the extend of your raster files. If you happen to see two different of those lines, your raster images do not match 100 %. You can fix that again with the {{button|text=Superimpose sensor}} Tool in the OTB library in {{button|text=QGIS}}
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
=Seeded Region Growing Algorithm=
 +
 
 +
 
 +
* Go to the {{button|text=Geoprocessing}} menu and select {{button|text=Find and Run tool}}
 +
 
 +
* Write ' region growing' and select [[File:SAGA6.PNG]]
 +
 
 +
 
 +
 
 +
* Select the one grid on offer
 +
* Select your seed point raster as {{button|text=Seeds}}
 +
 
 +
* Select your splitted band images as {{button|text=Features}}
 +
* Select {{button|text=create}} in {{button|text=Segments}}, {{button|text=Similarity}} and {{button|text=Tables<<Seeds}}
 +
* Select {{button|text=Normalize}}
 +
* Select {{button|text=4 (von Neumann}}
 +
* Select {{button|text= feature space and position}}
 +
* Insert the values shown in the picture and click {{button|text=Okay}} twice. We will talk about the input values later on...
 +
 
 +
[[File:Region_growing_mask.PNG]]
 +
 
 +
 
 +
After a short while, SAGA will have finished the calculation and  you'll notice two new layers in the layer panel. Double-click on {{button|text= Segments}} and you hopefully see the first fruit of all the effort that you put into this exercise:
 +
 
 +
 
 +
[[File:Region_growing_segments.PNG]]
 +
 
 +
 
 +
 
 +
=Vectorising the raster data=
 +
 
 +
In the next step we are going to create polygons in a shapefile which we can then open in {{button|text=QGIS}}...
 +
* In the {{button|text=Find and Run tool}} search, enter 'vectorising grid' and select [[File:Vectorising_Saga.PNG|150px|]]
 +
 
 +
 
 +
* Fill in the mask as follows and double-click {{button|text= Okay}} :
 +
 
 +
[[File:Vectorising_Saga2.PNG]]
 +
 
 +
 
 +
* Right click on the newly created {{button|text=Segments}} file under {{button|text=Shapes}} in the Layer panel
 +
* Select {{button|text=Save as}} and save the file as ESRI shapefile
 +
 
 +
 
 +
 
 +
=Opening the polygon file in QGIS=
 +
 
 +
Now you can open the shapefile in QGIS and adjust the look of the segments in the {{button|text= Styles}} tab in the properties of the layer:
 +
 
 +
[[File:Segments2.PNG]]
 +
 
 +
 
 +
=The math part=
 +
 
 +
As you see in the last image, the segments fit the crowns quite well, but there is room for improvement. You can start to fine-tune the segmentation by changing the different parameters in the segmentation tool: '''Variance in Feature Space, Variance in Position Space, (Similarity Treshold), Method and Neighbourhood'''. You can also try to '''include or exclude certain data'''.
 +
 
 +
You can do that by trial and error, however, it helps to understand the math that lies behind these algorithms.
 +
 
 +
What the algorithm in the Seeded Region Growing module does, is that it starts with the seed point, goes to the adjacent pixels and joines them together if they are similar enough. 'Enough' in this case is determined by the similarity-condition which is expressed in the following formula:
 +
 
 +
[[File:Formula_(1).PNG]]
 +
 
 +
 
 +
The meaning of the parameters are easy to understand: ''''f'''' is a value (f.ex. a spectral value or a height value) ''''r'''' is a location. The indices designate which value it is, the one from the seed point or from the pixel that is being investigated (should it be joined to the segment of the seed or not).
 +
''''t'''' indicates vector transposition and '''σ<sub>1</sub>''' and '''σ<sub>2</sub>''' are variances in colour and position space. The latter normalize the value differences between seed point and pixel.
 +
'''α''' is the similarity criterion. It not need to be normalized and is set arbitrarily at 0.15.
 +
 
 +
'''σ<sub>1</sub>''' and '''σ<sub>2</sub>''' control how far the values (feature space / position space) are allowed to be. For a maximum distance of 40 % of the peak intensity and three color bands, the formula for '''σ<sub>1</sub>''' is:
 +
 
 +
[[File:Formula_(2).PNG]]
 +
 
 +
 
 +
'''σ<sub>2</sub>''' determines the maximum spatial distance '''δ''' which is set to the radius of the largest crown (for spherical crowns):
 +
 
 +
[[File:Formula_(2).PNG]]
 +
 
 +
 
 +
 
 +
(BECHTEL 2008<ref name="bechtel">Bechtel, B. (2008)."Segmentation for Object Extraction of Trees using MATLAB and SAGA." SAGA–Seconds Out, Hamburger Beiträge Zur Physischen Geographie Und Landschaftsökologie. Univ. Hamburg, Inst. für Geographie (2008): 1-12..</ref>)
 +
 
 +
 
 +
 
 +
The algorithm in the Seeded Region Growing module is based on the work of ERIKSON (2003<ref name="Erikson2003">Erikson, M. (2003). Segmentation of individual tree crowns in colour aerial photographs using region growing supported by fuzzy rules. Canadian Journal of Forest Research, 33(8), 1557-1563.</ref>, 2004<ref name="Erikson2004">Erikson, M. (2004). Segmentation and classification of individual tree crowns (Vol. 320).</ref>, ERIKSON & OLOFSSON 2005<ref name="Eriolof2005">Erikson, M., & Olofsson, K. 2005). Comparison of three individual tree crown detection methods. Machine Vision and Applications, 16(4), 258-265.</ref>)
 +
 
 +
=References=
 +
<references/>

Revision as of 15:06, 10 April 2018

Contents

Region Growing Segementation with Saga's Seeded Region Growing Tool

The following tutorial explains how to delineate tree crowns, using SAGA's Seeded Region Growing Tool. The product, a polygon shapefile, can then be used in an object based classification, f.ex. in order to classify different tree species.



Material you need to complete the tutorial

Data

A multispectral image of the forest canopy

A canopy height model CHM

Software

QGIS 2.18.11

SAGA 2.3.2


Split multiband image into several raster images

SAGA's Region Growing Algorithm works only with single band images. Therefor, we have to split our multiband image into its individual bands following these instructions.


Seed points

The first step here is to extract the position of the tree tops, which are going to be the starting point for the region growing algorithm. You find a description of how to derive the seed points from a CHM here . Now have a look at how the seeds align with your multiband image


Unfiltered seed points.PNG


In this picture you see, that the points align well with the tree tops. However, there are many points that represent small trees (in the lower left corner) which you might not be so interested in. In order to correct that, we are going to filter the points by their height in the seed shapefile and save the shapefile with the selected seeds only as a new shapefile. If the seed points do not fit the image well, it might be due to the fact that you are using an orthophoto and not a true orthophoto. If you are working only with a smaller dataset you can help it by using the Georeferencer in the Raster menu by rubberheeting your orthophoto to make it fit. You'll find the instructions for doing so here.


This looks much better:


Filtered seed points.PNG



Seed point rasterization

In order to use the seed points in the region growing algorithm in SAGA, we have to convert the vector file to a raster file using the Rasterize module from the GDAL Conversions in QGIS. It is critical that we create a raster file that only contains the seed points and no-data. So every pixel outside the seed points has to be no-data. It is also critical that our rasterized vector image has the exact same CRS (Coordinate reference system), extend and pixel size as the single band images.

  • In the Processing Toolbox, type 'rasterize' and select the Rasterize tool ind the SAGA geoalgorithms submenu
  • Select the seed point shapefile as input
  • Select ID as Attribute and the other parameters according to the screenshot below
  • Select the extend of one of the band splits as extend by clicking select canvas/ layers extend in the Output extend line
  • Copy the exact cellsize from either the metadata of one of your split images and set output raster size to Output resolution in map units per pixel
  • Save to a local file


Rasterize.PNG


The result should look like this:


Universe2.PNG




Now verify that the newly created seed point raster aligns 100% with one of the band split rasters by checking the metadata or Save raster layer as.. mask and by zooming into the seed pixels. Also check with the Info buttonInfo.PNG, if any pixel which is not a seed point, is no-data.


Saveas.PNG


Your raster should align like this:


Seedpixel.PNG

Superimpose Vector

It happens regularly that, although following the previous steps meticulously, that the extend and pixel size of the rasterized vector file does not match the splitted band images 100 %. In this case we have to use the OTB Superimpose Vector tool that you can find in the Processing Toolbox.

  • Open the Superimpose Vector tool in the Processing Toolbox.
  • Select one of the split band images as Reference input
  • Select the rasterized seed point shapefile as The image to reproject
  • Fill in the other parameters as shown here:

Superimpose.PNG


Next, go to the Properties of the newly created layer in the Layers Panel

  • Check the extend of the layer in the Metadata tab.
  • Go to Styles, load max/min values and set the Color Gradient to White to black

The result should look very much the same as the first rasterized vector, but the extend and pixel size are now 100 % the same as in

the split band images.


Region Growing in SAGA

Now we finally made it to the fun part of the whole exercise, which is creating the segments around the tops of the trees i.e. the seed points. Therefor we open SAGA GIS.

  • When prompted, select an empty Startup Project

SAGA1.PNG


  • Click the SAGA2.PNG button
  • Change SAGA3.PNG to All files


  • Open all split band images and the superimposed seed raster one after another
  • The layer panel on the left should now look like this:


SAGA4.PNG


  • In the line below Grids you see the extend of your raster files. If you happen to see two different of those lines, your raster images do not match 100 %. You can fix that again with the Superimpose sensor Tool in the OTB library in QGIS




Seeded Region Growing Algorithm

  • Go to the Geoprocessing menu and select Find and Run tool
  • Write ' region growing' and select SAGA6.PNG


  • Select the one grid on offer
  • Select your seed point raster as Seeds
  • Select your splitted band images as Features
  • Select create in Segments, Similarity and Tables<<Seeds
  • Select Normalize
  • Select 4 (von Neumann
  • Select feature space and position
  • Insert the values shown in the picture and click Okay twice. We will talk about the input values later on...

Region growing mask.PNG


After a short while, SAGA will have finished the calculation and you'll notice two new layers in the layer panel. Double-click on Segments and you hopefully see the first fruit of all the effort that you put into this exercise:


Region growing segments.PNG


Vectorising the raster data

In the next step we are going to create polygons in a shapefile which we can then open in QGIS...

  • In the Find and Run tool search, enter 'vectorising grid' and select Vectorising Saga.PNG


  • Fill in the mask as follows and double-click Okay :

Vectorising Saga2.PNG


  • Right click on the newly created Segments file under Shapes in the Layer panel
  • Select Save as and save the file as ESRI shapefile


Opening the polygon file in QGIS

Now you can open the shapefile in QGIS and adjust the look of the segments in the Styles tab in the properties of the layer:

Segments2.PNG


The math part

As you see in the last image, the segments fit the crowns quite well, but there is room for improvement. You can start to fine-tune the segmentation by changing the different parameters in the segmentation tool: Variance in Feature Space, Variance in Position Space, (Similarity Treshold), Method and Neighbourhood. You can also try to include or exclude certain data.

You can do that by trial and error, however, it helps to understand the math that lies behind these algorithms.

What the algorithm in the Seeded Region Growing module does, is that it starts with the seed point, goes to the adjacent pixels and joines them together if they are similar enough. 'Enough' in this case is determined by the similarity-condition which is expressed in the following formula:

Formula (1).PNG


The meaning of the parameters are easy to understand: 'f' is a value (f.ex. a spectral value or a height value) 'r' is a location. The indices designate which value it is, the one from the seed point or from the pixel that is being investigated (should it be joined to the segment of the seed or not). 't' indicates vector transposition and σ1 and σ2 are variances in colour and position space. The latter normalize the value differences between seed point and pixel. α is the similarity criterion. It not need to be normalized and is set arbitrarily at 0.15.

σ1 and σ2 control how far the values (feature space / position space) are allowed to be. For a maximum distance of 40 % of the peak intensity and three color bands, the formula for σ1 is:

Formula (2).PNG


σ2 determines the maximum spatial distance δ which is set to the radius of the largest crown (for spherical crowns):

Formula (2).PNG


(BECHTEL 2008[1])


The algorithm in the Seeded Region Growing module is based on the work of ERIKSON (2003[2], 2004[3], ERIKSON & OLOFSSON 2005[4])

References

  1. ↑ Bechtel, B. (2008)."Segmentation for Object Extraction of Trees using MATLAB and SAGA." SAGA–Seconds Out, Hamburger Beiträge Zur Physischen Geographie Und Landschaftsökologie. Univ. Hamburg, Inst. für Geographie (2008): 1-12..
  2. ↑ Erikson, M. (2003). Segmentation of individual tree crowns in colour aerial photographs using region growing supported by fuzzy rules. Canadian Journal of Forest Research, 33(8), 1557-1563.
  3. ↑ Erikson, M. (2004). Segmentation and classification of individual tree crowns (Vol. 320).
  4. ↑ Erikson, M., & Olofsson, K. 2005). Comparison of three individual tree crown detection methods. Machine Vision and Applications, 16(4), 258-265.
Retrieved from "http://wiki.awf.forst.uni-goettingen.de/wiki/index.php?title=Region_Growing_Segmentation&oldid=14275"
Personal tools
Namespaces

Variants
Actions
Navigation
Development
Toolbox
Print/export