i.segment.html 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231
  1. <h2>DESCRIPTION</h2>
  2. Image segmentation or object recognition is the process of grouping
  3. similar pixels into unique segments, also refered to as objects.
  4. Boundary and region based algorithms are described in the literature,
  5. currently a region growing and merging algorithm is implemented. Each
  6. object found during the segmentation process is given a unique ID and
  7. is a collection of contiguous pixels meeting some criteria. Note the
  8. contrast with image classification where all pixels similar to each
  9. other are assigned to the same class and do not need to be contiguous.
  10. The image segmentation results can be useful on their own, or used as a
  11. preprocessing step for image classification. The segmentation
  12. preprocessing step can reduce noise and speed up the classification.
  13. <h2>NOTES</h2>
  14. <h3>Region Growing and Merging</h3>
  15. This segmentation algorithm sequentially examines all current segments
  16. in the raster map. The similarity between the current segment and each
  17. of its neighbors is calculated according to the given distance
  18. formula. Segments will be merged if they meet a number of criteria,
  19. including:
  20. <ol>
  21. <li>The pair is mutually most similar to each other (the similarity
  22. distance will be smaller than to any other neighbor), and</li>
  23. <li>The similarity must be lower than the input threshold. The
  24. process is repeated until no merges are made during a complete pass.</li>
  25. </ol>
  26. <h3>Similarity and Threshold</h3>
  27. The similarity between segments and unmerged objects is used to
  28. determine which objects are merged. Smaller distance values indicate a
  29. closer match, with a similarity score of zero for identical pixels.
  30. <p>
  31. During normal processing, merges are only allowed when the
  32. similarity between two segments is lower than the given
  33. threshold value. During the final pass, however, if a minimum
  34. segment size of 2 or larger is given with the <b>minsize</b>
  35. parameter, segments with a smaller pixel count will be merged with
  36. their most similar neighbor even if the similarity is greater than
  37. the threshold.
  38. <p>
  39. The <b>threshold</b> must be larger than 0.0 and smaller than 1.0. A threshold
  40. of 0 would allow only identical valued pixels to be merged, while a
  41. threshold of 1 would allow everything to be merged. Initial empirical
  42. tests indicate threshold values of 0.01 to 0.05 are reasonable values
  43. to start. It is recommended to start with a low value, e.g. 0.01, and
  44. then perform hierachical segmentation by using the output of the last
  45. run as <b>seeds</b> for the next run.
  46. <h4>Calculation Formulas</h4>
  47. Both Euclidean and Manhattan distances use the normal definition,
  48. considering each raster in the image group as a dimension.
  49. In future, the distance calculation will also take into account the
  50. shape characteristics of the segments. The normal distances are then
  51. multiplied by the input radiometric weight. Next an additional
  52. contribution is added: <tt>(1-radioweight) * {smoothness * smoothness
  53. weight + compactness * (1-smoothness weight)}</tt>,
  54. where <tt>compactness = Perimeter Length / sqrt( Area )</tt>
  55. and <tt>smoothness = Perimeter Length / Bounding Box</tt>. The
  56. perimeter length is estimated as the number of pixel sides the segment
  57. has.
  58. <h3>Seeds</h3>
  59. The seeds map can be used to provide either seed pixels (random or
  60. selected points from which to start the segmentation process) or
  61. seed segments. If the seeds are the results of a previous segmentation
  62. with lower threshold, hierarchical segmentation can be performed. The
  63. different approaches are automatically detected by the program: any
  64. pixels that have identical seed values and are contiguous will be
  65. assigned a unique segment ID.
  66. <p>
  67. It is expected that the <b>minsize</b> will be set to 1 if a seed
  68. map is used, but the program will allow other values to be used. If
  69. both options are used, the final iteration that ignores the
  70. threshold will also ignore the seed map and force merges for all
  71. pixels (not just segments that have grown/merged from the seeds).
  72. <h3>Maximum number of starting segments</h3>
  73. For the region growing algorithm without starting seeds, each pixel is
  74. sequentially numbered. The current limit with CELL storage is 2
  75. billion starting segment IDs. If the initial map has a larger number
  76. of non-null pixels, there are two workarounds:
  77. <ol>
  78. <li>Use starting seed pixels. (Maximum 2 billion pixels can be
  79. labeled with positive integers.)</li>
  80. <li>Use starting seed segments. (By initial classification or other
  81. methods.)</li>
  82. </ol>
  83. <h3>Boundary Constraints</h3>
  84. Boundary constraints limit the adjacency of pixels and segments.
  85. Each unique value present in the <b>bounds</b> raster are
  86. considered as a MASK. Thus no segments in the final segmentated map
  87. will cross a boundary, even if their spectral data is very similar.
  88. <h3>Minimum Segment Size</h3>
  89. To reduce the salt and pepper affect, a <b>minsize</b> greater
  90. than 1 will add one additional pass to the processing. During the
  91. final pass, the threshold is ignored for any segments smaller then
  92. the set size, thus forcing very small segments to merge with their
  93. most similar neighbor.
  94. <h3>Goodness of Fit</h3>
  95. The <b>goodness</b> of fit for each pixel is calculated as 1 - distance
  96. of the pixel to the object it belongs to. The distance is calculated
  97. with the selected <b>similarity</b> method. A value of 1 means
  98. identical values, perfect fit, and a value of 0 means maximum possible
  99. distance, worst possible fit.
  100. <h2>EXAMPLE</h2>
  101. This example uses the ortho photograph included in the NC Sample
  102. Dataset. Set up an imagery group:
  103. <div class="code"><pre>
  104. i.group group=ortho_group input=ortho_2001_t792_1m@PERMANENT
  105. </pre></div>
  106. <p>Set the region to a smaller test region (resolution taken from
  107. input ortho photograph).
  108. <div class="code"><pre>
  109. g.region -p raster=ortho_2001_t792_1m n=220446 s=220075 e=639151 w=638592
  110. </pre></div>
  111. Try out a low threshold and check the results.
  112. <div class="code"><pre>
  113. i.segment group=ortho_group output=ortho_segs_l1 threshold=0.02
  114. </pre></div>
  115. <center>
  116. <img src="ortho_segs_l1.jpg">
  117. </center>
  118. <p>
  119. From a visual inspection, it seems this results in too many segments.
  120. Increasing the threshold, using the previous results as seeds,
  121. and setting a minimum size of 2:
  122. <div class="code"><pre>
  123. i.segment group=ortho_group output=ortho_segs_l2 threshold=0.05 seeds=ortho_segs_l1 min=2
  124. i.segment group=ortho_group output=ortho_segs_l3 threshold=0.1 seeds=ortho_segs_l2
  125. i.segment group=ortho_group output=ortho_segs_l4 threshold=0.2 seeds=ortho_segs_l3
  126. i.segment group=ortho_group output=ortho_segs_l5 threshold=0.3 seeds=ortho_segs_l4
  127. </pre></div>
  128. <center>
  129. <img src="ortho_segs_l2_l5.jpg">
  130. </center>
  131. <p>
  132. The output <tt>ortho_segs_l4</tt> with <b>threshold</b>=0.2 still has
  133. too many segments, but the output with <b>threshold</b>=0.3 has too few
  134. segments. A threshold value of 0.25 seems to be a good choice. There
  135. is also some noise in the image, lets next force all segments smaller
  136. than 10 pixels to be merged into their most similar neighbor (even if
  137. they are less similar than required by our threshold):
  138. <p>Set the region to match the entire map(s) in the group.
  139. <div class="code"><pre>
  140. g.region -p raster=ortho_2001_t792_1m@PERMANENT
  141. </pre></div>
  142. <p>
  143. Run <em>i.segment</em> on the full map:
  144. <div class="code"><pre>
  145. i.segment group=ortho_group output=ortho_segs_final threshold=0.25 min=10
  146. </pre></div>
  147. <center>
  148. <img src="ortho_segs_final.jpg">
  149. </center>
  150. <p>
  151. Processing the entire ortho image with nearly 10 million pixels took
  152. about 450 times more then for the final run.
  153. <h2>TODO</h2>
  154. <h3>Functionality</h3>
  155. <ul>
  156. <li>Further testing of the shape characteristics (smoothness,
  157. compactness), if it looks good it should be added.
  158. (<b>in progress</b>)</li>
  159. <li>Malahanobis distance for the similarity calculation.</li>
  160. </ul>
  161. <h3>Use of Segmentation Results</h3>
  162. <ul>
  163. <li>Improve the optional output from this module, or better yet, add a
  164. module for <em>i.segment.metrics</em>.</li>
  165. <li>Providing updates to <em><a href="i.maxlik.html">i.maxlik</a></em>
  166. to ensure the segmentation output can be used as input for the
  167. existing classification functionality.</li>
  168. <li>Integration/workflow for <em>r.fuzzy</em> (Addon).</li>
  169. </ul>
  170. <h3>Speed</h3>
  171. <ul>
  172. <li>See create_isegs.c</li>
  173. </ul>
  174. <h2>REFERENCES</h2>
  175. This project was first developed during GSoC 2012. Project documentation,
  176. Image Segmentation references, and other information is at the
  177. <a href="http://grasswiki.osgeo.org/wiki/GRASS_GSoC_2012_Image_Segmentation">project wiki</a>.
  178. <p>
  179. Information about
  180. <a href="http://grasswiki.osgeo.org/wiki/Image_classification">classification in GRASS</a>
  181. is at available on the wiki.
  182. <h2>SEE ALSO</h2>
  183. <em>
  184. <a href="g.gui.iclass.html">g.gui.iclass</a>,
  185. <a href="i.group.html">i.group</a>,
  186. <a href="i.maxlik.html">i.maxlik</a>,
  187. <a href="i.smap.html">i.smap</a>,
  188. <a href="r.kappa.html">r.kappa</a>
  189. </em>
  190. <h2>AUTHORS</h2>
  191. Eric Momsen - North Dakota State University<br>
  192. Markus Metz (GSoC Mentor)
  193. <p>
  194. <i>Last changed: $Date$</i>