| 1 |
<h2>DESCRIPTION</h2> |
| 2 |
|
| 3 |
<em>i.segment</em> identifies segments (objects) from |
| 4 |
imagery data. |
| 5 |
<p> |
| 6 |
Image segmentation or object recognition is the process of grouping |
| 7 |
similar pixels into unique segments, also referred to as objects. |
| 8 |
Boundary and region based algorithms are described in the literature, |
| 9 |
currently a region growing and merging algorithm is implemented. Each |
| 10 |
object found during the segmentation process is given a unique ID and |
| 11 |
is a collection of contiguous pixels meeting some criteria. Note the |
| 12 |
contrast with image classification where all pixels similar to each |
| 13 |
other are assigned to the same class and do not need to be contiguous. |
| 14 |
The image segmentation results can be useful on their own, or used as a |
| 15 |
preprocessing step for image classification. The segmentation |
| 16 |
preprocessing step can reduce noise and speed up the classification. |
| 17 |
|
| 18 |
<h2>NOTES</h2> |
| 19 |
|
| 20 |
<h3>Region Growing and Merging</h3> |
| 21 |
|
| 22 |
This segmentation algorithm sequentially examines all current segments |
| 23 |
in the raster map. The similarity between the current segment and each |
| 24 |
of its neighbors is calculated according to the given distance |
| 25 |
formula. Segments will be merged if they meet a number of criteria, |
| 26 |
including: |
| 27 |
|
| 28 |
<ol> |
| 29 |
<li>The pair is mutually most similar to each other (the similarity |
| 30 |
distance will be smaller than to any other neighbor), and</li> |
| 31 |
<li>The similarity must be lower than the input threshold. The |
| 32 |
process is repeated until no merges are made during a complete pass.</li> |
| 33 |
</ol> |
| 34 |
|
| 35 |
<h4>Similarity and Threshold</h4> |
| 36 |
The similarity between segments and unmerged objects is used to |
| 37 |
determine which objects are merged. Smaller distance values indicate a |
| 38 |
closer match, with a similarity score of zero for identical pixels. |
| 39 |
<p> |
| 40 |
During normal processing, merges are only allowed when the |
| 41 |
similarity between two segments is lower than the given |
| 42 |
threshold value. During the final pass, however, if a minimum |
| 43 |
segment size of 2 or larger is given with the <b>minsize</b> |
| 44 |
parameter, segments with a smaller pixel count will be merged with |
| 45 |
their most similar neighbor even if the similarity is greater than |
| 46 |
the threshold. |
| 47 |
<p> |
| 48 |
The <b>threshold</b> must be larger than 0.0 and smaller than 1.0. A threshold |
| 49 |
of 0 would allow only identical valued pixels to be merged, while a |
| 50 |
threshold of 1 would allow everything to be merged. The threshold is scaled to |
| 51 |
the data range of the entire input data, not the current computational region. |
| 52 |
This allows the application of the same threshold to different computational |
| 53 |
regions when working on the same dataset, ensuring that this threshold has the |
| 54 |
same meaning in all subregions. |
| 55 |
|
| 56 |
<p> |
| 57 |
Initial empirical |
| 58 |
tests indicate threshold values of 0.01 to 0.05 are reasonable values |
| 59 |
to start. It is recommended to start with a low value, e.g. 0.01, and |
| 60 |
then perform hierarchical segmentation by using the output of the last |
| 61 |
run as <b>seeds</b> for the next run. |
| 62 |
|
| 63 |
<h4>Calculation Formulas</h4> |
| 64 |
Both Euclidean and Manhattan distances use the normal definition, |
| 65 |
considering each raster in the image group as a dimension. |
| 66 |
|
| 67 |
In future, the distance calculation will also take into account the |
| 68 |
shape characteristics of the segments. The normal distances are then |
| 69 |
multiplied by the input radiometric weight. Next an additional |
| 70 |
contribution is added: <code>(1-radioweight) * {smoothness * smoothness |
| 71 |
weight + compactness * (1-smoothness weight)}</code>, |
| 72 |
where <code>compactness = Perimeter Length / sqrt( Area )</code> |
| 73 |
and <code>smoothness = Perimeter Length / Bounding Box</code>. The |
| 74 |
perimeter length is estimated as the number of pixel sides the segment |
| 75 |
has. |
| 76 |
|
| 77 |
<h4>Seeds</h4> |
| 78 |
The seeds map can be used to provide either seed pixels (random or |
| 79 |
selected points from which to start the segmentation process) or |
| 80 |
seed segments. If the seeds are the results of a previous segmentation |
| 81 |
with lower threshold, hierarchical segmentation can be performed. The |
| 82 |
different approaches are automatically detected by the program: any |
| 83 |
pixels that have identical seed values and are contiguous will be |
| 84 |
assigned a unique segment ID. |
| 85 |
|
| 86 |
<h4>Maximum number of segments</h4> |
| 87 |
|
| 88 |
The current limit with CELL storage used for segment IDs is 2 |
| 89 |
billion starting segment IDs. Segment IDs are assigned whenever a yet |
| 90 |
unprocessed pixel is merged with another segment. Integer overflow can |
| 91 |
happen for computational regions with more than 2 billion cells and |
| 92 |
very low threshold values, resulting in many segments. If integer |
| 93 |
overflow occurs during region growing, starting segments can be used |
| 94 |
(created by initial classification or other methods). |
| 95 |
|
| 96 |
<h4>Goodness of Fit</h4> |
| 97 |
The <b>goodness</b> of fit for each pixel is calculated as 1 - distance |
| 98 |
of the pixel to the object it belongs to. The distance is calculated |
| 99 |
with the selected <b>similarity</b> method. A value of 1 means |
| 100 |
identical values, perfect fit, and a value of 0 means maximum possible |
| 101 |
distance, worst possible fit. |
| 102 |
|
| 103 |
<h3>Mean shift</h3> |
| 104 |
Mean shift image segmentation consists of 2 steps: anisotrophic |
| 105 |
filtering and 2. clustering. For anisotrophic filtering new cell values |
| 106 |
are calculated from all pixels not farther than <b>radius</b> pixels away |
| 107 |
from the current pixel and with a spectral difference not larger than |
| 108 |
<b>hr</b>. That means that pixels that are too different from the current |
| 109 |
pixel are not considered in the calculation of new pixel values. |
| 110 |
<b>radius</b> and <b>hr</b> are the spatial and spectral (range) bandwidths |
| 111 |
for anisotrophic filtering. Cell values are iteratively recalculated |
| 112 |
(shifted to the segment's mean) until the maximum number of iterations |
| 113 |
is reached or until the largest shift is smaller than <b>threshold</b>. |
| 114 |
|
| 115 |
<p> |
| 116 |
If input bands have been reprojected, they should not be reprojected |
| 117 |
with bilinear resampling because that method causes smooth transitions |
| 118 |
between objects. More appropriate methods are bicubic or lanczos |
| 119 |
resampling. |
| 120 |
|
| 121 |
<h3>Boundary Constraints</h3> |
| 122 |
Boundary constraints limit the adjacency of pixels and segments. |
| 123 |
Each unique value present in the <b>bounds</b> raster are |
| 124 |
considered as a mask. Thus, no segments in the final segmented map |
| 125 |
will cross a boundary, even if their spectral data is very similar. |
| 126 |
|
| 127 |
<h3>Minimum Segment Size</h3> |
| 128 |
To reduce the salt and pepper effect, a <b>minsize</b> greater |
| 129 |
than 1 will add one additional pass to the processing. During the |
| 130 |
final pass, the threshold is ignored for any segments smaller then |
| 131 |
the set size, thus forcing very small segments to merge with their |
| 132 |
most similar neighbor. A minimum segment size larger than 1 is |
| 133 |
recommended when using adaptive bandwidth selected with the <b>-a</b> |
| 134 |
flag. |
| 135 |
|
| 136 |
<h2>EXAMPLES</h2> |
| 137 |
|
| 138 |
<h3>Segmentation of RGB orthophoto</h3> |
| 139 |
|
| 140 |
This example uses the ortho photograph included in the NC Sample |
| 141 |
Dataset. Set up an imagery group: |
| 142 |
<div class="code"><pre> |
| 143 |
i.group group=ortho_group input=ortho_2001_t792_1m@PERMANENT |
| 144 |
</pre></div> |
| 145 |
|
| 146 |
<p>Set the region to a smaller test region (resolution taken from |
| 147 |
input ortho photograph). |
| 148 |
|
| 149 |
<div class="code"><pre> |
| 150 |
g.region -p raster=ortho_2001_t792_1m n=220446 s=220075 e=639151 w=638592 |
| 151 |
</pre></div> |
| 152 |
|
| 153 |
Try out a low threshold and check the results. |
| 154 |
<div class="code"><pre> |
| 155 |
i.segment group=ortho_group output=ortho_segs_l1 threshold=0.02 |
| 156 |
</pre></div> |
| 157 |
|
| 158 |
<center> |
| 159 |
<img src="i_segment_ortho_segs_l1.jpg"> |
| 160 |
</center> |
| 161 |
|
| 162 |
<p> |
| 163 |
From a visual inspection, it seems this results in too many segments. |
| 164 |
Increasing the threshold, using the previous results as seeds, |
| 165 |
and setting a minimum size of 2: |
| 166 |
<div class="code"><pre> |
| 167 |
i.segment group=ortho_group output=ortho_segs_l2 threshold=0.05 seeds=ortho_segs_l1 min=2 |
| 168 |
|
| 169 |
i.segment group=ortho_group output=ortho_segs_l3 threshold=0.1 seeds=ortho_segs_l2 |
| 170 |
|
| 171 |
i.segment group=ortho_group output=ortho_segs_l4 threshold=0.2 seeds=ortho_segs_l3 |
| 172 |
|
| 173 |
i.segment group=ortho_group output=ortho_segs_l5 threshold=0.3 seeds=ortho_segs_l4 |
| 174 |
</pre></div> |
| 175 |
|
| 176 |
<center> |
| 177 |
<img src="i_segment_ortho_segs_l2_l5.jpg"> |
| 178 |
</center> |
| 179 |
|
| 180 |
<p> |
| 181 |
The output <code>ortho_segs_l4</code> with <b>threshold</b>=0.2 still has |
| 182 |
too many segments, but the output with <b>threshold</b>=0.3 has too few |
| 183 |
segments. A threshold value of 0.25 seems to be a good choice. There |
| 184 |
is also some noise in the image, lets next force all segments smaller |
| 185 |
than 10 pixels to be merged into their most similar neighbor (even if |
| 186 |
they are less similar than required by our threshold): |
| 187 |
|
| 188 |
<p>Set the region to match the entire map(s) in the group. |
| 189 |
<div class="code"><pre> |
| 190 |
g.region -p raster=ortho_2001_t792_1m@PERMANENT |
| 191 |
</pre></div> |
| 192 |
|
| 193 |
<p> |
| 194 |
Run <em>i.segment</em> on the full map: |
| 195 |
|
| 196 |
<div class="code"><pre> |
| 197 |
i.segment group=ortho_group output=ortho_segs_final threshold=0.25 min=10 |
| 198 |
</pre></div> |
| 199 |
|
| 200 |
<center> |
| 201 |
<img src="i_segment_ortho_segs_final.jpg"> |
| 202 |
</center> |
| 203 |
|
| 204 |
<p> |
| 205 |
Processing the entire ortho image with nearly 10 million pixels took |
| 206 |
about 450 times more then for the final run. |
| 207 |
|
| 208 |
<h3>Segmentation of panchromatic channel</h3> |
| 209 |
|
| 210 |
This example uses the panchromatic channel of the Landsat7 scene included |
| 211 |
in the North Carolina sample dataset: |
| 212 |
|
| 213 |
<div class="code"><pre> |
| 214 |
# create group with single channel |
| 215 |
i.group group=singleband input=lsat7_2002_80 |
| 216 |
|
| 217 |
# set computational region to Landsat7 PAN band |
| 218 |
g.region raster=lsat7_2002_80 -p |
| 219 |
|
| 220 |
# perform segmentation with minsize=5 |
| 221 |
i.segment group=singleband threshold=0.05 minsize=5 \ |
| 222 |
output=lsat7_2002_80_segmented_min5 goodness=lsat7_2002_80_goodness_min5 |
| 223 |
|
| 224 |
# perform segmentation with minsize=100 |
| 225 |
i.segment group=singleband threshold=0.05 minsize=100 |
| 226 |
output=lsat7_2002_80_segmented_min100 goodness=lsat7_2002_80_goodness_min100 |
| 227 |
</pre></div> |
| 228 |
|
| 229 |
<p> |
| 230 |
<center> |
| 231 |
<img src="i_segment_lsat7_pan.png"><br> |
| 232 |
Original panchromatic channel of the Landsat7 scene |
| 233 |
</center> |
| 234 |
|
| 235 |
<p> |
| 236 |
<center> |
| 237 |
<img src="i_segment_lsat7_seg_min5.png"><br> |
| 238 |
Segmented panchromatic channel, minsize=5 |
| 239 |
</center> |
| 240 |
<p> |
| 241 |
<center> |
| 242 |
<img src="i_segment_lsat7_seg_min100.png"><br> |
| 243 |
Segmented panchromatic channel, minsize=100 |
| 244 |
</center> |
| 245 |
|
| 246 |
<h2>TODO</h2> |
| 247 |
|
| 248 |
<h3>Functionality</h3> |
| 249 |
<ul> |
| 250 |
<li>Further testing of the shape characteristics (smoothness, |
| 251 |
compactness), if it looks good it should be added. |
| 252 |
(<b>in progress</b>)</li> |
| 253 |
<li>Malahanobis distance for the similarity calculation.</li> |
| 254 |
</ul> |
| 255 |
<h3>Use of Segmentation Results</h3> |
| 256 |
<ul> |
| 257 |
<li>Providing updates to <em><a href="i.maxlik.html">i.maxlik</a></em> |
| 258 |
to ensure the segmentation output can be used as input for the |
| 259 |
existing classification functionality.</li> |
| 260 |
<li>Integration/workflow for <em>r.fuzzy</em> (Addon).</li> |
| 261 |
</ul> |
| 262 |
|
| 263 |
<h3>Speed</h3> |
| 264 |
<ul> |
| 265 |
<li>See create_isegs.c</li> |
| 266 |
</ul> |
| 267 |
|
| 268 |
<h2>REFERENCES</h2> |
| 269 |
|
| 270 |
This project was first developed during GSoC 2012. Project documentation, |
| 271 |
Image Segmentation references, and other information is at the |
| 272 |
<a href="https://grasswiki.osgeo.org/wiki/GRASS_GSoC_2012_Image_Segmentation">project wiki</a>. |
| 273 |
<p> |
| 274 |
Information about |
| 275 |
<a href="https://grasswiki.osgeo.org/wiki/Image_classification">classification in GRASS</a> |
| 276 |
is at available on the wiki. |
| 277 |
|
| 278 |
<h2>SEE ALSO</h2> |
| 279 |
|
| 280 |
<em> |
| 281 |
<a href="https://grass.osgeo.org/grass8/manuals/addons/i.segment.stats.html">i.segment.stats</a> (addon), |
| 282 |
<a href="https://grass.osgeo.org/grass8/manuals/addons/i.segment.uspo.html">i.segment.uspo</a> (addon), |
| 283 |
<a href="https://grass.osgeo.org/grass8/manuals/addons/i.segment.hierarchical.html">i.segment.hierarchical</a> (addon) |
| 284 |
<a href="g.gui.iclass.html">g.gui.iclass</a>, |
| 285 |
<a href="i.group.html">i.group</a>, |
| 286 |
<a href="i.maxlik.html">i.maxlik</a>, |
| 287 |
<a href="i.smap.html">i.smap</a>, |
| 288 |
<a href="r.kappa.html">r.kappa</a> |
| 289 |
</em> |
| 290 |
|
| 291 |
<h2>AUTHORS</h2> |
| 292 |
|
| 293 |
Eric Momsen - North Dakota State University<br> |
| 294 |
Markus Metz (GSoC Mentor) |