Debian Codegraph @

plugins/core/Standard/qRANSAC_SD/extern/RANSAC_SD/Bitmap.cpp

raw
1 #include "Bitmap.h"
2 #include <iostream>
3 #include <fstream>
4 #include <sstream>
5 #include <iomanip>
6 #include "Grid.h"
7 #include <algorithm>
8 #include <GfxTL/VectorXD.h>
9 #include <MiscLib/Performance.h>
10 using namespace MiscLib;
11 extern MiscLib::performance_t totalTime_components;
12
13 void DilateSquare(const MiscLib::Vector< char > &bitmap,
14 size_t uextent, size_t vextent, bool uwrap, bool vwrap,
15 MiscLib::Vector< char > *dilated)
16 {
17 // first pixel is special
18 (*dilated)[0] = bitmap[0] || bitmap[1] ||
19 bitmap[uextent] || bitmap[uextent + 1];
20 if(vwrap)
21 (*dilated)[0] = (*dilated)[0] ||
22 bitmap[(vextent - 1) * uextent] ||
23 bitmap[(vextent - 1) * uextent + 1];
24 if(uwrap)
25 (*dilated)[0] = (*dilated)[0] || bitmap[uextent - 1]
26 || bitmap[2 * uextent - 1];
27 if(vwrap && uwrap)
28 (*dilated)[0] = (*dilated)[0] ||
29 bitmap[(vextent - 1) * uextent + uextent - 1];
30 // first row is special
31 if(!vwrap)
32 {
33 for(size_t i = 1; i < uextent - 1; ++i)
34 {
35 (*dilated)[i] = bitmap[i - 1] || bitmap[i] || bitmap[i + 1] ||
36 bitmap[uextent + i - 1] || bitmap[uextent + i] ||
37 bitmap[uextent + i + 1];
38 }
39 }
40 else
41 {
42 for(size_t i = 1; i < uextent - 1; ++i)
43 {
44 (*dilated)[i] = bitmap[i - 1] || bitmap[i] || bitmap[i + 1] ||
45 bitmap[uextent + i - 1] || bitmap[uextent + i] ||
46 bitmap[uextent + i + 1] ||
47 bitmap[(vextent - 1) * uextent + i - 1] ||
48 bitmap[(vextent - 1) * uextent + i] ||
49 bitmap[(vextent - 1) * uextent + i + 1];
50 }
51 }
52 // last pixel of first row is special
53 (*dilated)[uextent - 1] = bitmap[uextent - 1] || bitmap[uextent - 2] ||
54 bitmap[2 * uextent - 1] || bitmap[2 * uextent - 2];
55 if(vwrap)
56 (*dilated)[uextent - 1] = (*dilated)[uextent - 1] ||
57 bitmap[vextent * uextent - 1] ||
58 bitmap[vextent * uextent - 2];
59 if(uwrap)
60 (*dilated)[uextent - 1] = (*dilated)[uextent - 1] ||
61 bitmap[uextent] || bitmap[0];
62 if(uwrap && vwrap)
63 (*dilated)[uextent - 1] = (*dilated)[uextent - 1] ||
64 bitmap[(vextent - 1) * uextent];
65 size_t row = 0, prevRow, nextRow = uextent;
66 for(size_t j = 1; j < vextent - 1; ++j)
67 {
68 prevRow = row;
69 row = nextRow;
70 nextRow = row + uextent;
71 // first pixel in row is special
72 (*dilated)[row] = bitmap[prevRow] || bitmap[prevRow + 1] ||
73 bitmap[row] || bitmap[row + 1] || bitmap[nextRow] ||
74 bitmap[nextRow + 1];
75 if(uwrap)
76 (*dilated)[row] = (*dilated)[row] || bitmap[row - 1] ||
77 bitmap[nextRow - 1] || bitmap[nextRow + uextent - 1];
78 for(size_t i = 1; i < uextent - 1; ++i)
79 {
80 (*dilated)[row + i] = bitmap[prevRow + i - 1] ||
81 bitmap[prevRow + i ] || bitmap[prevRow + i + 1] ||
82 bitmap[row + i - 1] || bitmap[row + i] ||
83 bitmap[row + i + 1] || bitmap[nextRow + i - 1] ||
84 bitmap[nextRow + i] || bitmap[nextRow + i + 1];
85 }
86 // last pixel in row is special
87 (*dilated)[row + uextent - 1] = bitmap[prevRow + uextent - 2] ||
88 bitmap[prevRow + uextent - 1] ||
89 bitmap[row + uextent - 2] || bitmap[row + uextent - 1] ||
90 bitmap[nextRow + uextent - 2] || bitmap[nextRow + uextent - 1];
91 if(uwrap)
92 (*dilated)[row + uextent - 1] = (*dilated)[row + uextent - 1] ||
93 bitmap[prevRow] || bitmap[row] || bitmap[nextRow];
94 }
95 // first pixel of last row is special
96 (*dilated)[(vextent - 1) * uextent] = bitmap[(vextent - 1) * uextent] ||
97 bitmap[(vextent - 1) * uextent + 1] ||
98 bitmap[(vextent - 2) * uextent] || bitmap[(vextent - 2) * uextent + 1];
99 if(vwrap)
100 (*dilated)[(vextent - 1) * uextent] =
101 (*dilated)[(vextent - 1) * uextent] || bitmap[0] || bitmap[1];
102 if(uwrap)
103 (*dilated)[(vextent - 1) * uextent] =
104 (*dilated)[(vextent - 1) * uextent] ||
105 bitmap[vextent * uextent - 1] ||
106 bitmap[(vextent - 1) * uextent - 1];
107 if(vwrap && uwrap)
108 (*dilated)[(vextent - 1) * uextent] =
109 (*dilated)[(vextent - 1) * uextent] || bitmap[uextent - 1];
110 // last row is special
111 if(!vwrap)
112 {
113 for(size_t i = 1; i < uextent - 1; ++i)
114 {
115 (*dilated)[(vextent - 1) * uextent + i] =
116 bitmap[(vextent - 1) * uextent + i] ||
117 bitmap[(vextent - 1) * uextent + i - 1] ||
118 bitmap[(vextent - 1) * uextent + i + 1] ||
119 bitmap[(vextent - 2) * uextent + i] ||
120 bitmap[(vextent - 2) * uextent + i - 1] ||
121 bitmap[(vextent - 2) * uextent + i + 1];
122 }
123 }
124 else
125 {
126 for(size_t i = 1; i < uextent - 1; ++i)
127 {
128 (*dilated)[(vextent - 1) * uextent + i] =
129 bitmap[(vextent - 1) * uextent + i] ||
130 bitmap[(vextent - 1) * uextent + i - 1] ||
131 bitmap[(vextent - 1) * uextent + i + 1] ||
132 bitmap[(vextent - 2) * uextent + i] ||
133 bitmap[(vextent - 2) * uextent + i - 1] ||
134 bitmap[(vextent - 2) * uextent + i + 1] ||
135 bitmap[i - 1] || bitmap[i] || bitmap[i + 1];
136 }
137 }
138 // last pixel
139 (*dilated)[bitmap.size() - 1] = bitmap[bitmap.size() - 1] ||
140 bitmap[bitmap.size() - 2] || bitmap[bitmap.size() - uextent - 1] ||
141 bitmap[bitmap.size() - uextent - 2];
142 if(vwrap)
143 (*dilated)[bitmap.size() - 1] = (*dilated)[bitmap.size() - 1] ||
144 bitmap[uextent - 1] || bitmap[uextent - 2];
145 if(uwrap)
146 (*dilated)[bitmap.size() - 1] = (*dilated)[bitmap.size() - 1] ||
147 bitmap[bitmap.size() - uextent] ||
148 bitmap[bitmap.size() - 2 * uextent];
149 if(uwrap && vwrap)
150 (*dilated)[bitmap.size() - 1] = (*dilated)[bitmap.size() - 1] ||
151 bitmap[0];
152 }
153
154 void DilateCross(const MiscLib::Vector< char > &bitmap,
155 size_t uextent, size_t vextent, bool uwrap, bool vwrap,
156 MiscLib::Vector< char > *dilated)
157 {
158 // first pixel is special
159 (*dilated)[0] = bitmap[0] || bitmap[1] ||
160 bitmap[uextent];
161 if(vwrap)
162 (*dilated)[0] = (*dilated)[0] ||
163 bitmap[(vextent - 1) * uextent];
164 if(uwrap)
165 (*dilated)[0] = (*dilated)[0] || bitmap[uextent - 1];
166 // first row is special
167 if(!vwrap)
168 {
169 for(size_t i = 1; i < uextent - 1; ++i)
170 {
171 (*dilated)[i] = bitmap[i - 1] || bitmap[i] || bitmap[i + 1] ||
172 bitmap[uextent + i];
173 }
174 }
175 else
176 {
177 for(size_t i = 1; i < uextent - 1; ++i)
178 {
179 (*dilated)[i] = bitmap[i - 1] || bitmap[i] || bitmap[i + 1] ||
180 bitmap[uextent + i] || bitmap[(vextent - 1) * uextent + i];
181 }
182 }
183 // last pixel of first row is special
184 (*dilated)[uextent - 1] = bitmap[uextent - 1] || bitmap[uextent - 2] ||
185 bitmap[2 * uextent - 1];
186 if(vwrap)
187 (*dilated)[uextent - 1] = (*dilated)[uextent - 1] ||
188 bitmap[vextent * uextent - 1];
189 if(uwrap)
190 (*dilated)[uextent - 1] = (*dilated)[uextent - 1] || bitmap[0];
191 size_t row = 0, prevRow, nextRow = uextent;
192 for(size_t j = 1; j < vextent - 1; ++j)
193 {
194 prevRow = row;
195 row = nextRow;
196 nextRow = row + uextent;
197 // first pixel in row is special
198 (*dilated)[row] = bitmap[prevRow] ||
199 bitmap[row] || bitmap[row + 1] || bitmap[nextRow];
200 if(uwrap)
201 (*dilated)[row] = (*dilated)[row] || bitmap[nextRow - 1];
202 for(size_t i = 1; i < uextent - 1; ++i)
203 {
204 (*dilated)[row + i] = bitmap[prevRow + i ] ||
205 bitmap[row + i - 1] || bitmap[row + i] ||
206 bitmap[row + i + 1] || bitmap[nextRow + i];
207 }
208 // last pixel in row is special
209 (*dilated)[row + uextent - 1] = bitmap[prevRow + uextent - 1] ||
210 bitmap[row + uextent - 2] || bitmap[row + uextent - 1] ||
211 bitmap[nextRow + uextent - 1];
212 if(uwrap)
213 (*dilated)[row + uextent - 1] = (*dilated)[row + uextent - 1] ||
214 bitmap[row];
215 }
216 // first pixel of last row is special
217 (*dilated)[(vextent - 1) * uextent] = bitmap[(vextent - 1) * uextent] ||
218 bitmap[(vextent - 1) * uextent + 1] ||
219 bitmap[(vextent - 2) * uextent];
220 if(vwrap)
221 (*dilated)[(vextent - 1) * uextent] =
222 (*dilated)[(vextent - 1) * uextent] || bitmap[0];
223 if(uwrap)
224 (*dilated)[(vextent - 1) * uextent] =
225 (*dilated)[(vextent - 1) * uextent] ||
226 bitmap[vextent * uextent - 1];
227 // last row is special
228 if(!vwrap)
229 {
230 for(size_t i = 1; i < uextent - 1; ++i)
231 {
232 (*dilated)[(vextent - 1) * uextent + i] =
233 bitmap[(vextent - 1) * uextent + i] ||
234 bitmap[(vextent - 1) * uextent + i - 1] ||
235 bitmap[(vextent - 1) * uextent + i + 1] ||
236 bitmap[(vextent - 2) * uextent + i];
237 }
238 }
239 else
240 {
241 for(size_t i = 1; i < uextent - 1; ++i)
242 {
243 (*dilated)[(vextent - 1) * uextent + i] =
244 bitmap[(vextent - 1) * uextent + i] ||
245 bitmap[(vextent - 1) * uextent + i - 1] ||
246 bitmap[(vextent - 1) * uextent + i + 1] ||
247 bitmap[(vextent - 2) * uextent + i] ||
248 bitmap[i];
249 }
250 }
251 // last pixel
252 (*dilated)[bitmap.size() - 1] = bitmap[bitmap.size() - 1] ||
253 bitmap[bitmap.size() - 2] || bitmap[bitmap.size() - uextent - 1];
254 if(vwrap)
255 (*dilated)[bitmap.size() - 1] = (*dilated)[bitmap.size() - 1] ||
256 bitmap[uextent - 1];
257 if(uwrap)
258 (*dilated)[bitmap.size() - 1] = (*dilated)[bitmap.size() - 1] ||
259 bitmap[bitmap.size() - uextent];
260 }
261
262 void ErodeSquare(const MiscLib::Vector< char > &bitmap,
263 size_t uextent, size_t vextent, bool uwrap, bool vwrap,
264 MiscLib::Vector< char > *eroded)
265 {
266 // first pixel is special
267 (*eroded)[0] = /*bitmap[0] && bitmap[1] &&
268 bitmap[uextent] && bitmap[uextent + 1]*/ false;
269 //if(vwrap)
270 // (*eroded)[0] = (*eroded)[0] &&
271 // bitmap[(vextent - 1) * uextent] &&
272 // bitmap[(vextent - 1) * uextent + 1];
273 //if(uwrap)
274 // (*eroded)[0] = (*eroded)[0] && bitmap[uextent - 1]
275 // && bitmap[2 * uextent - 1];
276 if(vwrap && uwrap)
277 {
278 (*eroded)[0] = bitmap[0]
279 && bitmap[1]
280 && bitmap[uextent]
281 && bitmap[uextent + 1]
282 && bitmap[(vextent - 1) * uextent]
283 && bitmap[(vextent - 1) * uextent + 1]
284 && bitmap[uextent - 1]
285 && bitmap[2 * uextent - 1]
286 && bitmap[(vextent - 1) * uextent + uextent - 1];
287 //(*eroded)[0] = (*eroded)[0] &&
288 // bitmap[(vextent - 1) * uextent + uextent - 1];
289 }
290 // first row is special
291 if(!vwrap)
292 {
293 for(size_t i = 1; i < uextent - 1; ++i)
294 {
295 (*eroded)[i] = /*bitmap[i - 1] && bitmap[i] && bitmap[i + 1] &&
296 bitmap[uextent + i - 1] && bitmap[uextent + i] &&
297 bitmap[uextent + i + 1];*/ false;
298 }
299 }
300 else
301 {
302 for(size_t i = 1; i < uextent - 1; ++i)
303 {
304 (*eroded)[i] = bitmap[i - 1] && bitmap[i] && bitmap[i + 1] &&
305 bitmap[uextent + i - 1] && bitmap[uextent + i] &&
306 bitmap[uextent + i + 1] &&
307 bitmap[(vextent - 1) * uextent + i - 1] &&
308 bitmap[(vextent - 1) * uextent + i] &&
309 bitmap[(vextent - 1) * uextent + i + 1];
310 }
311 }
312 // last pixel of first row is special
313 (*eroded)[uextent - 1] = /*bitmap[uextent - 1] && bitmap[uextent - 2] &&
314 bitmap[2 * uextent - 1] && bitmap[2 * uextent - 2]*/ false;
315 //if(vwrap)
316 // (*eroded)[uextent - 1] = (*eroded)[uextent - 1] &&
317 // bitmap[vextent * uextent - 1] &&
318 // bitmap[vextent * uextent - 2];
319 //if(uwrap)
320 // (*eroded)[uextent - 1] = (*eroded)[uextent - 1] &&
321 // bitmap[uextent] && bitmap[0];
322 if(uwrap && vwrap)
323 {
324 (*eroded)[uextent - 1] = bitmap[uextent - 1]
325 && bitmap[uextent - 2]
326 && bitmap[2 * uextent - 1]
327 && bitmap[2 * uextent - 2]
328 && bitmap[vextent * uextent - 1]
329 && bitmap[vextent * uextent - 2]
330 && bitmap[uextent]
331 && bitmap[0]
332 && bitmap[(vextent - 1) * uextent];
333 }
334 size_t row = 0, prevRow, nextRow = uextent;
335 for(size_t j = 1; j < vextent - 1; ++j)
336 {
337 prevRow = row;
338 row = nextRow;
339 nextRow = row + uextent;
340 // first pixel in row is special
341 (*eroded)[row] = /*bitmap[prevRow] && bitmap[prevRow + 1] &&
342 bitmap[row] && bitmap[row + 1] && bitmap[nextRow] &&
343 bitmap[nextRow + 1]*/ false;
344 if(uwrap)
345 {
346 (*eroded)[row] = bitmap[prevRow]
347 && bitmap[prevRow + 1]
348 && bitmap[row]
349 && bitmap[row + 1]
350 && bitmap[nextRow]
351 && bitmap[nextRow + 1]
352 && bitmap[row - 1]
353 && bitmap[nextRow - 1]
354 && bitmap[nextRow + uextent - 1];
355 }
356 for(size_t i = 1; i < uextent - 1; ++i)
357 {
358 (*eroded)[row + i] = bitmap[prevRow + i - 1] &&
359 bitmap[prevRow + i ] && bitmap[prevRow + i + 1] &&
360 bitmap[row + i - 1] && bitmap[row + i] &&
361 bitmap[row + i + 1] && bitmap[nextRow + i - 1] &&
362 bitmap[nextRow + i] && bitmap[nextRow + i + 1];
363 }
364 // last pixel in row is special
365 (*eroded)[row + uextent - 1] = /*bitmap[prevRow + uextent - 2] &&
366 bitmap[prevRow + uextent - 1] &&
367 bitmap[row + uextent - 2] && bitmap[row + uextent - 1] &&
368 bitmap[nextRow + uextent - 2] && bitmap[nextRow + uextent - 1]*/ false;
369 if(uwrap)
370 {
371 (*eroded)[row + uextent - 1] = bitmap[prevRow + uextent - 2]
372 && bitmap[prevRow + uextent - 1]
373 && bitmap[row + uextent - 2]
374 && bitmap[row + uextent - 1]
375 && bitmap[nextRow + uextent - 2]
376 && bitmap[nextRow + uextent - 1]
377 && bitmap[prevRow]
378 && bitmap[row]
379 && bitmap[nextRow];
380 }
381 }
382 // first pixel of last row is special
383 (*eroded)[(vextent - 1) * uextent] = /*bitmap[(vextent - 1) * uextent] &&
384 bitmap[(vextent - 1) * uextent + 1] &&
385 bitmap[(vextent - 2) * uextent] && bitmap[(vextent - 2) * uextent + 1]*/ false;
386 //if(vwrap)
387 // (*eroded)[(vextent - 1) * uextent] =
388 // (*eroded)[(vextent - 1) * uextent] && bitmap[0] && bitmap[1];
389 //if(uwrap)
390 // (*eroded)[(vextent - 1) * uextent] =
391 // (*eroded)[(vextent - 1) * uextent] &&
392 // bitmap[vextent * uextent - 1] &&
393 // bitmap[(vextent - 1) * uextent - 1];
394 if(vwrap && uwrap)
395 {
396 (*eroded)[(vextent - 1) * uextent] = bitmap[(vextent - 1) * uextent]
397 && bitmap[(vextent - 1) * uextent + 1]
398 && bitmap[(vextent - 2) * uextent]
399 && bitmap[(vextent - 2) * uextent + 1]
400 && bitmap[0]
401 && bitmap[1]
402 && bitmap[vextent * uextent - 1]
403 && bitmap[(vextent - 1) * uextent - 1]
404 && bitmap[uextent - 1];
405 }
406 // last row is special
407 if(!vwrap)
408 {
409 for(size_t i = 1; i < uextent - 1; ++i)
410 {
411 (*eroded)[(vextent - 1) * uextent + i] = false
412 /*bitmap[(vextent - 1) * uextent + i] &&
413 bitmap[(vextent - 1) * uextent + i - 1] &&
414 bitmap[(vextent - 1) * uextent + i + 1] &&
415 bitmap[(vextent - 2) * uextent + i] &&
416 bitmap[(vextent - 2) * uextent + i - 1] &&
417 bitmap[(vextent - 2) * uextent + i + 1]*/;
418 }
419 }
420 else
421 {
422 for(size_t i = 1; i < uextent - 1; ++i)
423 {
424 (*eroded)[(vextent - 1) * uextent + i] =
425 bitmap[(vextent - 1) * uextent + i] &&
426 bitmap[(vextent - 1) * uextent + i - 1] &&
427 bitmap[(vextent - 1) * uextent + i + 1] &&
428 bitmap[(vextent - 2) * uextent + i] &&
429 bitmap[(vextent - 2) * uextent + i - 1] &&
430 bitmap[(vextent - 2) * uextent + i + 1] &&
431 bitmap[i - 1] && bitmap[i] && bitmap[i + 1];
432 }
433 }
434 // last pixel
435 (*eroded)[bitmap.size() - 1] = false/*bitmap[bitmap.size() - 1] &&
436 bitmap[bitmap.size() - 2] && bitmap[bitmap.size() - uextent - 1] &&
437 bitmap[bitmap.size() - uextent - 2]*/;
438 //if(vwrap)
439 // (*eroded)[bitmap.size() - 1] = (*eroded)[bitmap.size() - 1] &&
440 // bitmap[uextent - 1] && bitmap[uextent - 2];
441 //if(uwrap)
442 // (*eroded)[bitmap.size() - 1] = (*eroded)[bitmap.size() - 1] &&
443 // bitmap[bitmap.size() - uextent] &&
444 // bitmap[bitmap.size() - 2 * uextent];
445 if(uwrap && vwrap)
446 {
447 (*eroded)[bitmap.size() - 1] = bitmap[bitmap.size() - 1]
448 && bitmap[bitmap.size() - 2]
449 && bitmap[bitmap.size() - uextent - 1]
450 && bitmap[bitmap.size() - uextent - 2]
451 && bitmap[uextent - 1]
452 && bitmap[uextent - 2]
453 && bitmap[bitmap.size() - uextent]
454 && bitmap[bitmap.size() - 2 * uextent]
455 && bitmap[0];
456 }
457 }
458
459 void ErodeCross(const MiscLib::Vector< char > &bitmap,
460 size_t uextent, size_t vextent, bool uwrap, bool vwrap,
461 MiscLib::Vector< char > *eroded)
462 {
463 // first pixel is special
464 (*eroded)[0] = bitmap[0] && bitmap[1] &&
465 bitmap[uextent];
466 if(vwrap)
467 (*eroded)[0] = (*eroded)[0] &&
468 bitmap[(vextent - 1) * uextent];
469 if(uwrap)
470 (*eroded)[0] = (*eroded)[0] && bitmap[uextent - 1];
471 // first row is special
472 if(!vwrap)
473 {
474 for(size_t i = 1; i < uextent - 1; ++i)
475 {
476 (*eroded)[i] = bitmap[i - 1] && bitmap[i] && bitmap[i + 1] &&
477 bitmap[uextent + i];
478 }
479 }
480 else
481 {
482 for(size_t i = 1; i < uextent - 1; ++i)
483 {
484 (*eroded)[i] = bitmap[i - 1] && bitmap[i] && bitmap[i + 1] &&
485 bitmap[uextent + i] && bitmap[(vextent - 1) * uextent + i];
486 }
487 }
488 // last pixel of first row is special
489 (*eroded)[uextent - 1] = bitmap[uextent - 1] && bitmap[uextent - 2] &&
490 bitmap[2 * uextent - 1];
491 if(vwrap)
492 (*eroded)[uextent - 1] = (*eroded)[uextent - 1] &&
493 bitmap[vextent * uextent - 1];
494 if(uwrap)
495 (*eroded)[uextent - 1] = (*eroded)[uextent - 1] && bitmap[0];
496 size_t row = 0, prevRow, nextRow = uextent;
497 for(size_t j = 1; j < vextent - 1; ++j)
498 {
499 prevRow = row;
500 row = nextRow;
501 nextRow = row + uextent;
502 // first pixel in row is special
503 (*eroded)[row] = bitmap[prevRow] &&
504 bitmap[row] && bitmap[row + 1] && bitmap[nextRow];
505 if(uwrap)
506 (*eroded)[row] = (*eroded)[row] && bitmap[nextRow - 1];
507 for(size_t i = 1; i < uextent - 1; ++i)
508 {
509 (*eroded)[row + i] = bitmap[prevRow + i ] &&
510 bitmap[row + i - 1] && bitmap[row + i] &&
511 bitmap[row + i + 1] && bitmap[nextRow + i];
512 }
513 // last pixel in row is special
514 (*eroded)[row + uextent - 1] = bitmap[prevRow + uextent - 1] &&
515 bitmap[row + uextent - 2] && bitmap[row + uextent - 1] &&
516 bitmap[nextRow + uextent - 1];
517 if(uwrap)
518 (*eroded)[row + uextent - 1] = (*eroded)[row + uextent - 1] &&
519 bitmap[row];
520 }
521 // first pixel of last row is special
522 (*eroded)[(vextent - 1) * uextent] = bitmap[(vextent - 1) * uextent] &&
523 bitmap[(vextent - 1) * uextent + 1] &&
524 bitmap[(vextent - 2) * uextent];
525 if(vwrap)
526 (*eroded)[(vextent - 1) * uextent] =
527 (*eroded)[(vextent - 1) * uextent] && bitmap[0];
528 if(uwrap)
529 (*eroded)[(vextent - 1) * uextent] =
530 (*eroded)[(vextent - 1) * uextent] &&
531 bitmap[vextent * uextent - 1];
532 // last row is special
533 if(!vwrap)
534 {
535 for(size_t i = 1; i < uextent - 1; ++i)
536 {
537 (*eroded)[(vextent - 1) * uextent + i] =
538 bitmap[(vextent - 1) * uextent + i] &&
539 bitmap[(vextent - 1) * uextent + i - 1] &&
540 bitmap[(vextent - 1) * uextent + i + 1] &&
541 bitmap[(vextent - 2) * uextent + i];
542 }
543 }
544 else
545 {
546 for(size_t i = 1; i < uextent - 1; ++i)
547 {
548 (*eroded)[(vextent - 1) * uextent + i] =
549 bitmap[(vextent - 1) * uextent + i] &&
550 bitmap[(vextent - 1) * uextent + i - 1] &&
551 bitmap[(vextent - 1) * uextent + i + 1] &&
552 bitmap[(vextent - 2) * uextent + i] &&
553 bitmap[i];
554 }
555 }
556 // last pixel
557 (*eroded)[bitmap.size() - 1] = bitmap[bitmap.size() - 1] &&
558 bitmap[bitmap.size() - 2] && bitmap[bitmap.size() - uextent - 1];
559 if(vwrap)
560 (*eroded)[bitmap.size() - 1] = (*eroded)[bitmap.size() - 1] &&
561 bitmap[uextent - 1];
562 if(uwrap)
563 (*eroded)[bitmap.size() - 1] = (*eroded)[bitmap.size() - 1] &&
564 bitmap[bitmap.size() - uextent];
565 }
566
567 void PreWrappedComponents(const MiscLib::Vector< char > &bitmap, size_t uextent,
568 size_t vextent, MiscLib::Vector< int > *preWrappedComponentsImg,
569 MiscLib::Vector< int > *relabelComponentsImg,
570 const MiscLib::Vector< std::pair< int, size_t > > &inLabels,
571 MiscLib::Vector< std::pair< int, size_t > > *labels)
572 {
573 MiscLib::Vector< std::pair< int, size_t > > tempLabels(inLabels);
574 tempLabels.reserve(bitmap.size() / 2 + 1); // this is the maximum of possible tempLabels
575 if(!tempLabels.size())
576 tempLabels.push_back(std::make_pair(0, size_t(0)));
577 int curLabel = static_cast<int>(tempLabels.size()) - 1;
578 size_t prevRow, row = 0, nextRow = uextent;
579 for(size_t j = 1; j < vextent - 1; ++j)
580 {
581 prevRow = row;
582 row = nextRow;
583 nextRow = row + uextent;
584 for(size_t i = 1; i < uextent - 1; ++i)
585 {
586 if(!bitmap[row + i])
587 {
588 (*preWrappedComponentsImg)[row + i] = 0;
589 ++tempLabels[0].second;
590 continue;
591 }
592 // get neighborhood
593 int n[8];
594 n[0] = (*preWrappedComponentsImg)[prevRow + i - 1];
595 n[1] = (*preWrappedComponentsImg)[prevRow + i];
596 n[2] = (*preWrappedComponentsImg)[prevRow + i + 1];
597 n[3] = (*preWrappedComponentsImg)[row + i - 1];
598 n[4] = (*preWrappedComponentsImg)[row + i + 1];
599 n[5] = (*preWrappedComponentsImg)[nextRow + i - 1];
600 n[6] = (*preWrappedComponentsImg)[nextRow + i];
601 n[7] = (*preWrappedComponentsImg)[nextRow + i + 1];
602 (*preWrappedComponentsImg)[row + i] = Label(n, 8,
603 &curLabel, &tempLabels);
604 }
605 }
606
607 // reduce the tempLabels
608 for(int i = static_cast<int>(tempLabels.size()) - 1; i > 0; --i)
609 tempLabels[i].first = ReduceLabel(i, tempLabels);
610 MiscLib::Vector< int > condensed(tempLabels.size());
611 labels->clear();
612 labels->reserve(condensed.size());
613 int count = 0;
614 for(size_t i = 0; i < tempLabels.size(); ++i)
615 if(i == (size_t)tempLabels[i].first)
616 {
617 labels->push_back(std::make_pair(count, tempLabels[i].second));
618 condensed[i] = count;
619 ++count;
620 }
621 else
622 (*labels)[condensed[tempLabels[i].first]].second
623 += tempLabels[i].second;
624 // set new component ids
625 for(size_t i = 0; i < preWrappedComponentsImg->size(); ++i)
626 (*preWrappedComponentsImg)[i] =
627 condensed[tempLabels[(*preWrappedComponentsImg)[i]].first];
628 for(size_t i = 0; i < relabelComponentsImg->size(); ++i)
629 (*relabelComponentsImg)[i] =
630 condensed[tempLabels[(*relabelComponentsImg)[i]].first];
631 }
632
633 void Components(const MiscLib::Vector< char > &bitmap,
634 size_t uextent, size_t vextent, bool uwrap, bool vwrap,
635 MiscLib::Vector< int > *componentsImg,
636 MiscLib::Vector< std::pair< int, size_t > > *labels)
637 {
638 componentsImg->resize(uextent * vextent);
639 MiscLib::Vector< std::pair< int, size_t > > tempLabels;
640 tempLabels.reserve(componentsImg->size() / 2 + 1); // this is the maximum of possible tempLabels
641 tempLabels.push_back(std::make_pair(0, size_t(0)));
642 // use an eight neighborhood
643 // first row is special
644 // first pixel is special
645 // wrapping does not make sense in the first row: no pixels have been
646 // assigned components yet
647 int curLabel = 0;
648 if(bitmap[0])
649 {
650 (*componentsImg)[0] = ++curLabel;
651 tempLabels.push_back(std::make_pair(curLabel, size_t(1)));
652 }
653 else
654 {
655 (*componentsImg)[0] = 0;
656 ++tempLabels[0].second;
657 }
658 // handle first row
659 for(size_t i = 1; i < uextent; ++i)
660 {
661 // in the first row only the previous pixel has to be considered
662 if(bitmap[i])
663 {
664 if((*componentsImg)[i - 1])
665 {
666 (*componentsImg)[i] = (*componentsImg)[i - 1];
667 ++tempLabels[(*componentsImg)[i]].second;
668 }
669 else
670 {
671 (*componentsImg)[i] = ++curLabel;
672 tempLabels.push_back(std::make_pair(curLabel, size_t(1)));
673 }
674 }
675 else
676 {
677 (*componentsImg)[i] = 0;
678 ++tempLabels[0].second;
679 }
680 }
681 size_t prevRow, row = 0;
682 size_t jend = vwrap? vextent - 1 : vextent;
683 for(size_t j = 1; j < jend; ++j)
684 {
685 prevRow = row;
686 row = prevRow + uextent;
687 // first pixel in row gets different treatment
688 if(bitmap[row])
689 {
690 if((*componentsImg)[prevRow]) // pixel above in component?
691 {
692 (*componentsImg)[row] = (*componentsImg)[prevRow];
693 ++tempLabels[(*componentsImg)[row]].second;
694 }
695 else
696 {
697 int n[2];
698 n[0] = (*componentsImg)[prevRow + 1];
699 if(uwrap)
700 n[1] = (*componentsImg)[prevRow + uextent - 1];
701 (*componentsImg)[row] = Label(n, uwrap? 2 : 1, &curLabel,
702 &tempLabels);
703 }
704 }
705 else
706 {
707 (*componentsImg)[row] = 0;
708 ++tempLabels[0].second;
709 }
710 for(size_t i = 1; i < uextent - 1; ++i)
711 {
712 if(!bitmap[row + i])
713 {
714 (*componentsImg)[row + i] = 0;
715 ++tempLabels[0].second;
716 continue;
717 }
718 int n[4];
719 n[0] = (*componentsImg)[row + i - 1];
720 n[1] = (*componentsImg)[prevRow + i - 1];
721 n[2] = (*componentsImg)[prevRow + i];
722 n[3] = (*componentsImg)[prevRow + i + 1];
723 (*componentsImg)[row + i] = Label(n, 4, &curLabel, &tempLabels);
724 }
725 // last pixel in the row
726 if(!bitmap[row + uextent - 1])
727 {
728 (*componentsImg)[row + uextent - 1] = 0;
729 ++tempLabels[0].second;
730 continue;
731 }
732 int n[5];
733 n[0] = (*componentsImg)[row + uextent - 2];
734 n[1] = (*componentsImg)[prevRow + uextent - 2];
735 n[2] = (*componentsImg)[prevRow + uextent - 1];
736 if(uwrap)
737 {
738 n[3] = (*componentsImg)[prevRow];
739 n[4] = (*componentsImg)[row];
740 }
741 (*componentsImg)[row + uextent - 1] = Label(n, uwrap? 5 : 3, &curLabel,
742 &tempLabels);
743 }
744 // last row
745 if(vwrap) // in case of vwrapping the last row is computed with almost full
746 // neighborhood
747 {
748 prevRow = (vextent - 2) * uextent;
749 row = (vextent - 1) * uextent;
750 // first pixel
751 if(bitmap[row])
752 {
753 int n[6];
754 n[0] = (*componentsImg)[prevRow];
755 n[1] = (*componentsImg)[prevRow + 1];
756 n[2] = (*componentsImg)[0];
757 n[3] = (*componentsImg)[1];
758 if(uwrap)
759 {
760 n[4] = (*componentsImg)[prevRow + uextent - 1];
761 n[5] = (*componentsImg)[uextent - 1];
762 }
763 (*componentsImg)[row] = Label(n, uwrap? 6 : 4, &curLabel,
764 &tempLabels);
765 }
766 else
767 {
768 (*componentsImg)[row] = 0;
769 ++tempLabels[0].second;
770 }
771 for(size_t i = 1; i < uextent - 1; ++i)
772 {
773 if(!bitmap[row + i])
774 {
775 (*componentsImg)[row + i] = 0;
776 ++tempLabels[0].second;
777 continue;
778 }
779 int n[7];
780 n[0] = (*componentsImg)[row + i - 1];
781 n[1] = (*componentsImg)[prevRow + i - 1];
782 n[2] = (*componentsImg)[prevRow + i];
783 n[3] = (*componentsImg)[prevRow + i + 1];
784 n[4] = (*componentsImg)[i - 1];
785 n[5] = (*componentsImg)[i];
786 n[6] = (*componentsImg)[i + 1];
787 (*componentsImg)[row + i] = Label(n, 7, &curLabel, &tempLabels);
788 }
789 // last pixel
790 if(!bitmap[row + uextent - 1])
791 {
792 (*componentsImg)[row + uextent - 1] = 0;
793 ++tempLabels[0].second;
794 }
795 else
796 {
797 int n[8];
798 n[0] = (*componentsImg)[row + uextent - 2];
799 n[1] = (*componentsImg)[prevRow + uextent - 2];
800 n[2] = (*componentsImg)[prevRow + uextent - 1];
801 n[3] = (*componentsImg)[uextent - 2];
802 n[4] = (*componentsImg)[uextent - 1];
803 if(uwrap)
804 {
805 n[5] = (*componentsImg)[prevRow];
806 n[6] = (*componentsImg)[row];
807 n[7] = (*componentsImg)[0];
808 }
809 (*componentsImg)[row + uextent - 1] = Label(n, uwrap? 8 : 5,
810 &curLabel, &tempLabels);
811 }
812 }
813 // reduce the tempLabels
814 for(int i = static_cast<int>(tempLabels.size()) - 1; i > 0; --i)
815 tempLabels[i].first = ReduceLabel(i, tempLabels);
816 MiscLib::Vector< int > condensed(tempLabels.size());
817 labels->clear();
818 labels->reserve(condensed.size());
819 int count = 0;
820 for(size_t i = 0; i < tempLabels.size(); ++i)
821 if(i == (size_t)tempLabels[i].first)
822 {
823 labels->push_back(std::make_pair(count, tempLabels[i].second));
824 condensed[i] = count;
825 ++count;
826 }
827 else
828 (*labels)[condensed[tempLabels[i].first]].second
829 += tempLabels[i].second;
830 // set new component ids
831 for(size_t i = 0; i < componentsImg->size(); ++i)
832 (*componentsImg)[i] =
833 condensed[tempLabels[(*componentsImg)[i]].first];
834 }
835
836 int Label(int n[], int size, int *curLabel,
837 MiscLib::Vector< std::pair< int, size_t > > *labels)
838 {
839 // check if components are set
840 int count = 0, found;
841 for(int i = 0; i < size; ++i)
842 {
843 if(n[i])
844 {
845 ++count;
846 found = n[i];
847 }
848 }
849 if(!count)
850 {
851 ++(*curLabel);
852 labels->push_back(std::make_pair(*curLabel, size_t(1)));
853 return *curLabel;
854 }
855 else if(count == 1)
856 {
857 ++(*labels)[found].second;
858 return found;
859 }
860 else
861 {
862 ++(*labels)[found].second;
863 // associate the remaining labels
864 for(int i = 0; i < size; ++i)
865 {
866 if(n[i] && n[i] != found)
867 AssociateLabel(n[i], found, labels);
868 }
869 return found;
870 }
871 }
872
873 void AssociateLabel(int a, int b,
874 MiscLib::Vector< std::pair< int, size_t > > *labels)
875 {
876 if(a > b)
877 {
878 AssociateLabel(b, a, labels);
879 return;
880 }
881 if((a == b) || ((*labels)[b].first == a))
882 return;
883 if((*labels)[b].first == b)
884 (*labels)[b].first = a;
885 else
886 {
887 AssociateLabel((*labels)[b].first, a, labels);
888 if((*labels)[b].first > a)
889 (*labels)[b].first = a;
890 }
891 }
892
893 int ReduceLabel(int a,
894 const MiscLib::Vector< std::pair< int, size_t > > &labels)
895 {
896 if(labels[a].first == a)
897 return labels[a].first;
898 return ReduceLabel(labels[a].first, labels);
899 }
900
901 bool IsEdge(const MiscLib::Vector< int > &componentImg, size_t uextent,
902 size_t vextent, int label, bool uwrap, bool vwrap,
903 int startx, int starty, int dirx, int diry,
904 size_t *targetx, size_t *targety)
905 {
906 if(dirx > 0)
907 {
908 if((size_t)startx == uextent)
909 return false;
910 if((size_t)starty == vextent)
911 return false;
912 *targetx = (uwrap && (size_t)startx == uextent - 1)? 0 : startx + 1;
913 *targety = starty;
914 return componentImg[starty * uextent + startx] == label
915 && ((starty > 0 && componentImg[(starty - 1) * uextent + startx] != label)
916 || (!vwrap && starty == 0)
917 || (vwrap && starty == 0 && componentImg[(vextent - 1) * uextent + startx] != label));
918 }
919 if(dirx < 0)
920 {
921 if(!uwrap && startx == 0)
922 return false;
923 *targetx = (startx == 0)? uextent - 1 : startx - 1;
924 *targety = starty;
925 return (!vwrap && (size_t)starty == vextent && componentImg[(starty - 1) * uextent + (*targetx)] == label)
926 || ((size_t)starty != vextent && (componentImg[starty * uextent + (*targetx)] != label
927 && ((starty > 0 && componentImg[(starty - 1) * uextent + (*targetx)] == label)
928 || (vwrap && starty == 0 && componentImg[(vextent - 1) * uextent + (*targetx)] == label))));
929 }
930 if(diry > 0)
931 {
932 if((size_t)starty == vextent)
933 return false;
934 *targetx = startx;
935 *targety = (vwrap && (size_t)starty == vextent - 1)? 0 : starty + 1;
936 return (!uwrap && (size_t)startx == uextent && componentImg[starty * uextent + (startx - 1)] == label)
937 || ((size_t)startx != uextent && (componentImg[starty * uextent + startx] != label
938 && (((size_t)startx > 0 && componentImg[starty * uextent + (startx - 1)] == label)
939 || (uwrap && startx == 0 && componentImg[starty * uextent + (uextent - 1)] == label))));
940 }
941 if(diry < 0)
942 {
943 if(!vwrap && starty == 0)
944 return false;
945 if((size_t)startx == uextent)
946 return false;
947 *targetx = startx;
948 *targety = (starty == 0)? vextent - 1 : starty - 1;
949 return componentImg[(*targety) * uextent + startx] == label
950 && ((startx > 0 && componentImg[(*targety) * uextent + (startx - 1)] != label)
951 || (!uwrap && startx == 0)
952 || (uwrap && startx == 0 && componentImg[(*targety) * uextent + (uextent - 1)] != label));
953 }
954 return false;
955 }
956
957 // finds the loops around a connected component as polygons
958 void ComponentLoops(const MiscLib::Vector< int > &componentImg, size_t uextent,
959 size_t vextent, int label, bool uwrap, bool vwrap,
960 MiscLib::Vector< MiscLib::Vector< GfxTL::VectorXD< 2, size_t > > > *polys)
961 {
962 typedef GfxTL::VectorXD< 2, size_t > Vec2;
963 // find first point of component
964 size_t firsti = 0;
965 int x, y, prevx, prevy;
966 // the corners of our pixels will be the vertices of our polygons
967 // (x, y) is the upper left corner of the pixel y * uextent + x
968 HashGrid< bool, 4 > edges;
969 size_t edgesExtent[] = { uextent + 1, vextent + 1, 3, 3 };
970 edges.Extent(edgesExtent);
971 bool prevPixelWasWhite = true;
972 do
973 {
974 // find the first edge in the polygon
975 // edges are oriented so that the "black" pixels are on the right
976 // black pixels are pixels == label
977 for(; firsti < componentImg.size(); ++firsti)
978 {
979 if(prevPixelWasWhite && componentImg[firsti] == label)
980 {
981 prevPixelWasWhite = false;
982 x = static_cast<int>(firsti % uextent);
983 y = static_cast<int>(firsti / uextent);
984 break;
985 }
986 prevPixelWasWhite = componentImg[firsti] != label;
987 }
988 if(firsti >= componentImg.size()) // unable to find a pixel -> good bye
989 {
990 // if there is a uwrap, then the last row could be an outer loop
991 // this outer loop could be missed of all pixels in the last
992 // row are black
993 // to find that out we spawn another trial at the first
994 // pixel in the last row (if it is black)
995 // if the loop has already been detected, than this
996 // edge should already be in edges
997 if(!uwrap)
998 break;
999 if(componentImg[(vextent - 1) * uextent] == label)
1000 {
1001 x = 0;
1002 y = static_cast<int>(vextent) - 1;
1003 }
1004 }
1005 MiscLib::Vector< Vec2 > poly;
1006 // we initialize the path with an oriented edge
1007 // since the black pixel is on the right the edge goes from
1008 // bottom to top, i.e. from (x, y + 1) to (x, y)
1009 if((x > 0 && (size_t)y < vextent - 1)
1010 || (!uwrap && !vwrap) || (vwrap && !uwrap && y == 0))
1011 {
1012 // on the left of pixel
1013 // check if edge was visited already
1014 unsigned int edgeIndex[] = { static_cast<unsigned>(x), static_cast<unsigned>(y), 1u, 2u };
1015 if(edges.find(edgeIndex))
1016 continue;
1017 prevx = 0;
1018 prevy = 1;
1019 }
1020 else if(uwrap && !vwrap && x == 0 && (size_t)y != vextent - 1)
1021 {
1022 size_t dx, dy;
1023 if(!IsEdge(componentImg, uextent, vextent, label, uwrap, vwrap,
1024 x, y, 1, 0, &dx, &dy))
1025 continue;
1026 // check if edge was visited already
1027 unsigned int edgeIndex[] = { static_cast<unsigned>(x + 1), static_cast<unsigned>(y), 0, 1 };
1028 if(edges.find(edgeIndex))
1029 continue;
1030 // on top of pixel
1031 prevx = -1;
1032 prevy = 0;
1033 ++x;
1034 }
1035 else if(uwrap && !vwrap && x == 0 && (size_t)y == vextent - 1)
1036 {
1037 size_t dx, dy;
1038 if(!IsEdge(componentImg, uextent, vextent, label, uwrap, vwrap,
1039 x + 1, y + 1, -1, 0, &dx, &dy))
1040 continue;
1041 // on bottom of pixel
1042 // check if edge was visited already
1043 unsigned int edgeIndex[] = { static_cast<unsigned>(x + 1), static_cast<unsigned>(y + 1), 0, 1 };
1044 if(edges.find(edgeIndex))
1045 continue;
1046 prevx = -1;
1047 prevy = 0;
1048 ++y;
1049 }
1050 else if(!uwrap && vwrap && (size_t)x == uextent - 1)
1051 {
1052 // on right of pixel
1053 size_t dx, dy;
1054 if(!IsEdge(componentImg, uextent, vextent, label, uwrap, vwrap,
1055 x + 1, y + 1, 0, -1, &dx, &dy))
1056 continue;
1057 // on bottom of pixel
1058 // check if edge was visited already
1059 unsigned int edgeIndex[] = { static_cast<unsigned>(x + 1), static_cast<unsigned>(y + 1), 1, 0 };
1060 if(edges.find(edgeIndex))
1061 continue;
1062 prevx = 0;
1063 prevy = 1;
1064 ++y;
1065 }
1066 else
1067 continue; // we are unable to start a loop at this position
1068 poly.push_back(Vec2(x + prevx, y + prevy));
1069 edges[x][y][prevx + 1][prevy + 1] = true;
1070 do
1071 {
1072 poly.push_back(Vec2(x, y));
1073 // check the four neighbors of (x, y) from left to right
1074 // starting from where we came from
1075 // we take the first edge that we encounter
1076 size_t nextx, nexty;
1077 size_t checkEdge;
1078 for(checkEdge = 0; checkEdge < 3; ++checkEdge)
1079 {
1080 std::swap(prevx, prevy);
1081 prevx *= -1;
1082 if(IsEdge(componentImg, uextent, vextent, label, uwrap, vwrap,
1083 x, y, prevx, prevy, &nextx, &nexty))
1084 break;
1085 }
1086 if(checkEdge > 3)
1087 return;
1088 x = static_cast<int>(nextx);
1089 y = static_cast<int>(nexty);
1090 prevx = -prevx;
1091 prevy = -prevy;
1092 edges[x][y][prevx + 1][prevy + 1] = true;
1093 }
1094 while(poly[0] != Vec2(x, y));
1095 polys->push_back(poly);
1096 }
1097 while(firsti < componentImg.size());
1098 #ifdef _DEBUG
1099 static int fname_int = 0;
1100 std::ostringstream fn;
1101 fn << "ComponentLoopsInput" << fname_int << ".txt";
1102 std::ofstream file;
1103 file.open(fn.str().c_str(), std::ios::out);
1104 for(size_t j = 0; j < vextent; ++j)
1105 {
1106 for(size_t i = 0; i < uextent; ++i)
1107 file /*<< std::setw(3)*/ << componentImg[j * uextent + i]/* << " "*/;
1108 file << std::endl;
1109 }
1110 file.close();
1111 MiscLib::Vector< int > loopsImg((uextent + 1) * (vextent + 1), 0);
1112 std::ostringstream fn2;
1113 fn2 << "ComponentLoopsOutput" << fname_int++ << ".txt";
1114 for(size_t i = 0; i < polys->size(); ++i)
1115 for(size_t j = 0; j < (*polys)[i].size(); ++j)
1116 loopsImg[(*polys)[i][j][1] * (uextent + 1) + (*polys)[i][j][0]] = static_cast<int>(i) + 1;
1117 file.open(fn2.str().c_str(), std::ios::out);
1118 for(size_t j = 0; j < vextent + 1; ++j)
1119 {
1120 for(size_t i = 0; i < uextent + 1; ++i)
1121 file /*<< std::setw(3)*/ << loopsImg[j * (uextent + 1) + i]/* << " "*/;
1122 file << std::endl;
1123 }
1124 file.close();
1125 #endif
1126 }