Debian Codegraph @

imagery/i.segment/i.segment.html

raw
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)