Debian Codegraph @

imagery/i.segment/outline

raw
1 This is the draft pseudocode for the region growing segmentation algorithm. More information, references, requirements, etc are at the wiki:
2 https://grass.osgeo.org/wiki/GRASS_GSoC_2012_Image_Segmentation
3
4 For anyone interested in background discussion, Rev 51907 includes original comments and discussion between EM, MM, and ML. All comments were combined (and new threads started!) after that revision.
5
6 TODO: Memory management, allow user to input how much RAM can be used. Compare i.watershed and i.cost for two current options, initial recommendations are to follow i.watershed.
7
8 TODO: Are any parts here potentially useful as library functions? Are any of these tasks already done by existing library functions?
9
10 General notes:
11 Avoid use of global variables (makes multithreading easier).
12
13
14 files:
15
16 iseg.h - declare structures and functions
17
18 Structures:
19
20 files: input and output data (segmentation files and/or RAM storage)
21
22 functions: parameters and function pointers
23
24
25 /****************************************************/
26 /******** Parse the input parameters ****************/
27 /****************************************************/
28
29 Using just imagery group right now. Could add an option to allow just one raster as an input (user friendly). Currently no plan for subgroup, it is not often used.
30
31 seeds: All pixels or user defined points (optional, default = all pixels) user defined points will initially be defined with a raster map, could add option to allow vector map later (user friendly).
32
33 constraint (vector linear/polygon) (optional)
34
35 segmentation algorithm (only region growing accepted to start)
36
37 pixel neighbors: for a particular pixel, use 4 neighbors or 8 neighbors? (flag, not set = 4 neighbors)
38
39 Later: memory usage (r.watershed uses -m flag + memory parameter)
40
41
42
43 /* Algorithm parameters */
44
45 similarity threshold
46
47 how quickly the threshold should be reduced
48
49 Minimum number of pixels per segment (optional, default 1)
50
51 Later:
52 weights for shape and compactness
53
54 No plans for implementation:
55 layer weights, color spaces, color transformations: these should be done by the user prior to running i.segment.
56
57
58 /* output parameters */
59 need name for new raster map
60
61 Later:
62 maybe add some glue to allow the user to automatically launch r.to.vect and then the stats module.
63
64
65 /************************************/
66 /******** Input Validation **********/
67 /************************************/
68
69 Exit at first failure:
70
71 confirm input algorithm parameters are in correct range
72
73 Todo: confirm if Rast_get_row() and nulls are handled in a way later processing steps can deal with. (nulls should be skipped)
74
75 Grass library functions already handle basic checks (overwrite, conversion from source data resolution to region resolution, etc)
76
77 End of validation checks
78
79
80 /************************************/
81 /******** Open maps **********/
82 /************************************/
83
84 Open the input and output maps.
85
86 Todo: Currently using the segmentation library. need to implement the -m option to allow possibility to store in RAM.
87
88 input map structure:
89 - each cell is an array, length to match number of maps in the input group
90 - TODO: how to store optional vector boundaries
91 output map structure:
92 - also an array:
93 - segment assignment
94 - candidate flag: has it been check during this iteration loop
95 - assigned flag: has it been assigned to a segment (only if number of seeds < number of pixels)
96
97
98 /*******************************************/
99 /************* preprocessing ? *************/
100 /*******************************************/
101
102 Any preprocessing?
103
104 If complete polygons are given as boundaries:
105 1. run segmentation for each polygon, mask rest of map
106 2. run segmentation with polygons as mask (to segment anything not included in a polygon)
107
108 I think this will apply to vector lines only, initially it was framed as being for polygons or lines.
109
110 /*ML: vector to raster conversion is probably necessary. Pixels crosses by a line (polygon boundary or not) have to become part of a segment boundary.*/
111 /*EM: hmm, OK, something else for discussion: These pixels that are on a vector line, should they eventually be included in one of the adjacent segments? Is "segment boundary" just the edge pixels of the segment, or are the not included in any segment?*/
112 /*ML: Here is where a difference comes into play between lines that are boundary polygons and lines as linear features. In my eyes pixels that are on boundarylines of polygons should be part of the segments that are internal to that boundary. Linear features would have to be treated differently. During discussions with colleagues we did have some difficulties finding actual use cases for linear features. Maybe we can start with only polygon features and if the use case of a linear features comes up try to integrate that then ?*/
113 /*EM: But for polygons covering the entire map, there is a segment on either side of the polygon line. If the line crosses the pixel, what should be done... It looks like this will not be a problem for multi-scalar segmentation, the polygons generated in a high level segmentation will be exactly between pixels. This will only be an issue for polygons generated elsewhere, smoothed, at different resolution, etc.*/
114 /* MM: You can not know where the polygons are coming from, therefore you have consider all cases or, better, come up with a general solution. You will need to clone (substantial) parts of the t.to.vect module if you want to rasterize polygons/boundaries. If you do not rasterize, you will need to check for a boundary/line whenever you evaluate a neighbor. This could be sped up a bit by selecting all boundaries/lines crossing the current 3x3 neighborhood. The spatial selection of vector features is fast, but doing that for every cell/3x3 neighborhood can substantially slow down the module. You will also need to check if the boundary is actually part of an area (not an invalid boundary). Then you will need to check if the focus cell is inside the area, if not, if the neighbor is inside the area. Even though some spatial information gets lost by rasterization, I tend to recommend rasterization. In any case, taking into account boundaries/lines can easily become the bulk of the code, the most complex part of the code, and the most time-consuming component of the module. */
115 /* EM: left the above discussion... unresolved. One thought: instead of storing the output as a raster, maybe it should be first converted to a map, edges representing the neighbor relationship. After we have a map, we could use the vector map to delete edges crossing the borders. This is done once, afterwards we never calculate neighbors, only check for edges. It seems this will be a very large memory structure to start with, but as the segmentation continues it will get smaller.
116
117
118 /*******************************************/
119 /************ Processing ********************/
120 /*******************************************/
121
122 notes:
123 If seeds < number of pixels, candidate pixels must meet the additional requirement of not yet being assigned to a segment.
124
125
126 If we have polygon constraints. Outer for loop to process the image one polygon at a time. (Need to check if all pixels are included in a polygon, otherwise process all those pixels last.)
127
128 /*
129 * Roughly based on SPRING
130 * Bins, et al: Satellite Imagery Segmentation: A Region Growing Approach, 1996
131 * http://marte.dpi.inpe.br/col/sid.inpe.br/deise/1999/02.05.09.30/doc/T205.pdf
132 */
133
134 /* Similarity threshold T(t)... as t increases, threshold for similarity is lower. SPRING used: T(t) = T(0)alphat, where T(0) > 0, t =0,1,2... and alpha <1 */
135 /* MM: T(0) > ) ??? what exactly is t */
136 /* EM: corrected formula, should be >0. t = time. It feels like the opposite of simulated annealing. At earlier iterations in the process, it is difficult to make merges. As time increases, it is easier. To start with, I'm just going to implement a constant threshold, the lowering concept can be addeded later. */
137
138 For t (until no merges are made?)
139
140 Set candidate flag to true/1 for all pixels
141
142 For each pixel that candidate flag is true:
143 function: find segment neighbors (Now we have list of pixels in current focus segment (Ri) and a list of neighbors)
144 Calculate similarity between Ri and neighbors
145 If it exists, Rk is both most similar, and also similarity is < T.
146 function: find segment neighbors of Rk
147 Calculate similarity between Rk and its neighbors
148 IF (Ri is Rk's best neighbor) (so they agree, both are best match for each other)
149 merge Ri and Rk: (probably as function?)
150 update segment values for all pixels in Ri+Rk (mean)
151 set candidate flag to false for all pixels in Ri+Rk
152 select next Ri
153 /* MM: I guess it will be important how to select the next candidate
154 * (see above, FIFO or some kind of sorting) */
155 /* EM: I don't think the order matters: since the algorithm only accepts mutually best neighbors. */
156 Else
157 set candidate flag to false for all pixels in Ri
158 Use Rk as next Ri /* note, this is the eCognition technique. Seems this is a bit faster, we already have segment membership pixels
159 loop
160
161 Were any merges made for this time step?
162
163 next t
164
165 Force a merge of regions that are below minimum size threshold (just merge with most similar neighbor, no comparison with similarity threshold)
166
167 /*****************************************/
168 /******Function: Find Segment Neighbors **/
169 /*****************************************/
170
171 1 1 2 3 4
172 1 9 9 9 5
173 9 9 9 6 5
174 7 7 7 7 9
175
176 If the current segment being checked is 9
177
178 Desired results:
179 If no seeds: (can merge unassigned pixels and other segments)
180 For diagonals:
181 1, 2, 3, 4, 5, 6, 7
182 else
183 1, 2, 3, 4, 5, 7
184
185 else (starting from seeds, so only want single unassigned pixels as neighbors, no merges with other segments allowed)
186 for diagonals:
187 2, 3, 4, 6
188 else
189 2, 3, 6
190
191
192 Method 1: (using "rasters")
193
194 Input could be single pixel or list of pixels.
195 /* MM: what exactly is input? seeds? */
196 /* EM: input here is the current focus pixel. If it is a fresh Row/Column pixel, it will be a single pixel.
197 * If we just had Ri that was not mutually best neighbors with Rk, we'll use the member list of Rk as the new Ri.
198 * So in that case it will be the list of pixels we already know are part of the new Ri.
199
200 Put input in "to be checked" stack
201 Put input in "current segment" list
202 put input in "don't check" list
203 /* MM: you could also determine the status of each pixel on-the-fly when visiting this neighbor */
204 /* EM: I think that could work for the "don't check" list. But they will need to be initialized to zero each time...will that take too long?
205 * It seems we would have to initialize the entire map for each function call? Or keep track of a window size for row/column that was processed?
206 * /
207
208 empty "neighbor" list
209 While "to be checked" stack isn't empty:
210 pop
211 find pixel neighbors
212 with pixel neighbors
213 if in "don't check" list
214 do nothing
215 else
216 put in "don't check" list
217 if candidate pixel
218 if segment ID = current segment ID
219 add to "current segment" list
220 add to "to be checked" stack
221 else
222 add to "neighbor" list
223 next neighbor
224 loop...
225
226 return: neighbor list, pixels in segment list
227 /* MM: what is the purpose of the neighbor list and the segment list? */
228 /* EM: neighbor list: We will calculate the similarity between Ri and each neighbor.
229 * All need to be checked for the smallest similarity value (most similar), so order doesn't matter.
230 * If an Rk is selected, we'll run this routine on it, so will also have a segment membership list for Rk.
231 * If a merge is made, we have a list of pixels to be updated, members of Ri and Rk. (again order doesn't matter.)
232 * It seemed a list would be faster then querying the entire map for what pixels have a specific segment value, since that
233 * query has to look at the entire map.
234 * And it seems with the raster based storage, there was no easy way to store this for the whole time, it would be rechecked each iteration.
235 * ... see below with the map for further comments */
236 neighbor list will be a listing of pixels that are neighbors? Include segment numbers? Only include unique segments?
237 Maybe the most complete return would be a structure array, structure to include the segment ID and a list of points in it? But the list of points would NOT be inclusive - just the points bordering the current segment...
238
239
240 Method 2: (if build a map data structure at start of program)
241 Using current pixel's segment ID's edges, return neighbors
242
243 /* EM: So if we want to remember what pixels are part of each segment in a stable (instead of temporary) method, I think the
244 * map data structure makes more sense. Each element in the map would have: segment ID, processing flags, current values (mean of input data),
245 * current number of pixels, and a list (linked list, sorted array, etc) of pixel members (row,column). Edges would represent neighbor relations.
246 *
247 * My feeling is that this will be very slow to set up, and need more memory for the first iterations (compared to the raster version)
248 * But after the number of segments is reduced and the membership in each segment is higher, processing time will be faster.
249 *
250 * My advisor recommends to implement both methods - to check the speed, and also as a code validation / logic validation / bug testing:
251 * the segmented maps should be the same for both.
252 */
253
254 Existing GRASS functions don't seem to have this "neighbor of an area" concept. Am I missing something, should something be adapted, should I design this as a library function, or just write it as a function for this program?
255
256 r.neighbors:
257 is looking at the neighborhood that is a specified distance from one pixel
258
259 r.watershed
260 looks at the 4 or 8 adjacent neighbors. (can use this as basis for Find Pixel Neighbors function)
261
262 r.buffer
263 My current understanding: needs to know the min/max row and column that the feature is found in, it then scans that entire square, if the pixel is part of the feature, then checks distances around it. Seems looking for min/max for every segment number will be time consuming. Would need data structure to accommodate remembering what pixels are in each segment to use this.
264
265
266 /*****************************************/
267 /******Function: Find pixel Neighbors ****/
268 /*****************************************/
269
270 will use function pointer based on input, to select 4 or 8 neighbors
271
272
273 /*****************************************/
274 /******Function: calculate similarity ****/
275 /*****************************************/
276
277 Initially only Euclidean Distance
278
279 NOTE: this is not a distance function of the coordinates at all!
280
281 sqrt of the sum of squared differences between each of the input raster maps
282
283
284 /****************************************/
285 /************ Output ********************/
286 /****************************************/
287
288 renumber segments to have a sequential (1,2,3...) numbering?
289
290 output raster convert segmentation file or RAM data structure to grass raster using Rast_put_row()
291
292 G_message: total number of segments made.
293
294 /*******************************/
295 /********** tidy up ************/
296 /*******************************/
297
298 free memory, delete temp files
299
300
301 exit - success!
302
303
304
305 ###############################
306 ###############################
307
308 Statistics for the segmentation calculated in a separate module
309
310 Segmentation output = raster
311 statistics module input and output = vector. The user will have to run r.to.vect between the two.
312
313 Name?
314 i.seg.stats
315 i.segment.stats
316 r.stats.seg
317
318 -e Maybe an option for basic vs. extended output statistics
319
320
321 calculate statistics to be saved in data table for the vector map
322
323 one vector map of segments per hierarchy level with a series of attributes (I think this request would be handled by running the module for each hierarchy level? Or do we need to have an attribute for hierarchy level stored with a single vector map?)
324
325 spectral attributes:
326 per spectral band: mean, min, max, skewness
327
328 combination of bands: brightness, indices (i.e. results of multi-band calculations)
329
330 textural attributes: stdev (per-band and/or multi-band), mean difference to neighbor, Haralick texture features cf r.texture
331
332 geometric/morphological attributes: area, perimeter, length/width measures, see also r.li
333 /* MM: perimeter is resolution-dependent, see also the famous Florida coastline problem */
334
335 context attributes: mean difference to all other regions in the same upper hierarchical level, relative localisation within upper hierarchical level, absolute localisation, number of objects in lower level
336
337 depending on segmentation algorithm: raster map indicating for each pixel the probability of belonging to the segment it was put into, i.e. some measure of reliability of results (For region growing - should this be the similarity measure when it was merged? Or similarity measure of the pixel compared to the average?)
338 /*ML: Not sure, but I would think that similarity between pixel and average of region it belongs to might be a good choice. Am not a specialist in statistics, but maybe it is possible to translate this into some form of probability of really "belonging" to that region (cf i.maxlik)*/
339 /* MM: I guess here it is important to not confuse classification with segmentation */