Fawkes API Fawkes Development Version
zauberstab.cpp
1
2/***************************************************************************
3 * zauberstab.cpp - Implementation of class "Zauberstab"
4 * which offers methods for finding
5 * maximal, color-contiguous region
6 * around a seed pixel
7 *
8 * Created: Mon Jul 02 2005
9 * Copyright 2005 Martin Heracles <Martin.Heracles@rwth-aachen.de>
10 * 2005-2008 Tim Niemueller [www.niemueller.de]
11 *
12 ****************************************************************************/
13
14/* This program is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version. A runtime exception applies to
18 * this software (see LICENSE.GPL_WRE file mentioned below for details).
19 *
20 * This program is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU Library General Public License for more details.
24 *
25 * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
26 */
27
28#include <core/macros.h>
29#include <fvutils/color/yuv.h>
30#include <fvutils/color/zauberstab.h>
31
32#include <cstdlib>
33#include <iostream>
34
35using namespace std;
36using namespace fawkes;
37
38namespace firevision {
39
40/** @class Zauberstab <fvutils/color/zauberstab.h>
41 * Zaubertab selection utility.
42 */
43
44/** Constructor. */
46{
47 topSliceY = 0;
48 slices = new vector<ZSlice *>();
49 slices->clear();
50}
51
52/** Constructor. */
54{
55 for (std::vector<ZSlice *>::iterator it = slices->begin(); it != slices->end(); ++it) {
56 delete (*it);
57 }
58
59 delete slices;
60}
61
62/** Clears all slices.
63 */
64void
66{
67 for (std::vector<ZSlice *>::iterator it = slices->begin(); it != slices->end(); ++it) {
68 delete (*it);
69 }
70
71 slices->clear();
72}
73
74/** @class Zauberstab <fvutils/color/zauberstab.h>
75 * Zaubertab selection utility.
76 */
77
78/** Constructor. */
80{
81 // create empty region
82 region = new ZRegion();
83
84 buffer = NULL;
85 width = 0;
86 height = 0;
87
88 /* by default, "Zauberstab" does not allow
89 any deviation from seed color */
90 this->threshold = 0;
91}
92
93/** Destructor. */
95{
96 delete (region);
97}
98
99/** Set threshold.
100 * @param t new threshold
101 */
102void
104{
105 this->threshold = t;
106}
107
108/** Get threshold.
109 * @return threshold
110 */
111unsigned int
113{
114 return this->threshold;
115}
116
117/** Set buffer to work on.
118 * @param b buffer
119 * @param w width of image
120 * @param h height of buffer
121 */
122void
123Zauberstab::setBuffer(unsigned char *b, unsigned int w, unsigned int h)
124{
125 this->buffer = b;
126 this->width = w;
127 this->height = h;
128}
129
130/** Check if region is empty.
131 * @return true if empty
132 */
133bool
135{
136 return (region->slices->size() == 0);
137}
138
139/** Delete all regions. */
140void
142{
143 region->clear();
144}
145
146/** Delete region.
147 * @param seedX seed x
148 * @param seedY seed y
149 */
150void
151Zauberstab::deleteRegion(unsigned int seedX, unsigned int seedY)
152{
153 // STEP 1:
154 // find the region
155 ZRegion *region2 = privFindRegion(seedX, seedY);
156
157 // STEP 2:
158 // now delete the newly found region2 from the original region
159 deleteRegion(region2);
160
161 delete region2;
162}
163
164/** Delete region.
165 * @param region2 region to delete
166 */
167void
169{
170 ZSlice *nSlice; //A slice to be deleted
171 ZSlice *oSlice; //A slice currently in the region
172
173 // delete each slice of region 2 from region
174 while (region2->slices->size()) {
175 /* check if current slice from region 2 is at
176 at a height different from all slices at region */
177 nSlice = region2->slices->back();
178 region2->slices->pop_back();
179 int heightOfSlice = nSlice->y;
180
181 unsigned int i = 0;
182 unsigned int size = region->slices->size();
183
184 while (i < size) //for all existing slices (but not the newly added)
185 {
186 oSlice = region->slices->at(i);
187 if (oSlice->y == heightOfSlice) //same height check for overlapping
188 {
189 if ((oSlice->leftX >= nSlice->leftX) && (oSlice->leftX < nSlice->rightX)) {
190 //The slice to delete starts before the slice to be deleted
191 if (oSlice->rightX > nSlice->rightX) //A part of the region remains
192 {
193 oSlice->leftX = nSlice->rightX;
194 } else //The whole slice dissapears
195 {
196 region->slices->erase(region->slices->begin() + i);
197 size--;
198 delete oSlice;
199
200 //The index now points to the next element in the region->slices vector
201 continue;
202 }
203 }
204
205 if ((nSlice->leftX >= oSlice->leftX) && (nSlice->leftX < oSlice->rightX)) {
206 //The slice to be deleted starts before the part that should be deleted
207 if (oSlice->rightX <= nSlice->rightX) { //just truncate the old slices
208 oSlice->rightX = nSlice->leftX;
209 } else //split the old spice
210 {
211 ZSlice *newPart = new ZSlice;
212 newPart->rightX = oSlice->rightX;
213 newPart->leftX = nSlice->rightX;
214 newPart->y = heightOfSlice;
215
216 oSlice->rightX = nSlice->leftX;
217 region->slices->push_back(newPart);
218 }
219 }
220 }
221
222 i++;
223 }
224 }
225}
226
227/** A private region finder
228 * @param seedX seed x
229 * @param seedY seed y
230 * @return a ZRegion pointer (has to be deleted by the caller)
231 */
232ZRegion *
233Zauberstab::privFindRegion(unsigned int seedX, unsigned int seedY)
234{
235 unsigned char py __unused;
236 unsigned char pu = 0;
237 unsigned char pv = 0;
238
239 // STEP 1:
240 // first of all find the region around (seedX, seedY)
241 // (this is analogously to method "findRegion")
242 // (could be done more elegantly without the following redundant code)
243
244 // create empty region
245 ZRegion *region2 = new ZRegion();
246
247 /* find seed pixel's v-value
248 (consider seed pixel's neighborhood
249 and take average v-value) */
250 unsigned int uSeed = 0;
251 unsigned int vSeed = 0;
252 unsigned int cnt = 0;
253
254 for (int x = seedX - 2; x <= (int)seedX + 2; ++x) {
255 if (x < 0)
256 continue;
257 if ((unsigned int)x >= width)
258 continue;
259 for (int y = seedY - 2; y <= (int)seedY + 2; ++y) {
260 if (y < 0)
261 continue;
262 if ((unsigned int)y >= height)
263 continue;
264 YUV422_PLANAR_YUV(buffer, width, height, x, y, py, pu, pv);
265 uSeed += pu;
266 vSeed += pv;
267 ++cnt;
268 }
269 }
270
271 if (cnt) {
272 uSeed = uSeed / cnt;
273 vSeed = vSeed / cnt;
274 }
275 /* initial slice
276 thru seed pixel (seedX, seedY) */
277 ZSlice *tmp = NULL;
278 tmp = findSlice(seedX, seedY, vSeed, uSeed);
279 region2->slices->push_back(tmp);
280
281 /* NOTE: The following search works fine for
282 objects that are convex (such as ball, goal, ...).
283 For non-convex objects it may miss parts
284 (e.g. for a U-shaped object it can only find right or left half). */
285
286 // search downwards for more slices
287 tmp = region2->slices->front();
288 int tmpY = ((int)seedY >= (int)(height - 1)) ? height - 1 : seedY + 1;
289 // new "seed" pixel has x-coordinate in the middle of initial slice
290 int tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
291
292 YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
293 while (isSimilarUV(pu, uSeed, pv, vSeed)) {
294 tmp = findSlice(tmpX, tmpY, vSeed, uSeed);
295 region2->slices->push_back(tmp);
296 // new "seed" pixel has x-coordinate in the middle of previous slice
297 tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
298 tmpY++;
299 if (tmpY >= (int)this->height) {
300 break;
301 } else {
302 YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
303 }
304 }
305
306 /* search upwards for more slices
307 (start search from initial slice again) */
308 tmp = region2->slices->front();
309 tmpY = (seedY == 0) ? 0 : seedY - 1;
310 // new "seed" pixel has x-coordinate in the middle of initial slice
311 tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
312
313 YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
314 while (isSimilarUV(pu, uSeed, pv, vSeed)) {
315 tmp = findSlice(tmpX, tmpY, vSeed, uSeed);
316 region2->slices->push_back(tmp);
317 // new "seed" pixel has x-coordinate in the middle of previous slice
318 tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
319 tmpY--;
320 if (tmpY < 0) {
321 break;
322 } else {
323 YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
324 }
325 }
326
327 region2->topSliceY = tmpY + 1;
328
329 for (std::vector<ZSlice *>::iterator it = region2->slices->begin(); it != region2->slices->end();
330 ++it) {
331 cout << "start x: " << ((*it)->leftX) << " end x: " << ((*it)->rightX) << " y: " << ((*it)->y)
332 << endl;
333 }
334 cout << endl;
335 return region2;
336}
337
338/** Find region.
339 * @param seedX seed x
340 * @param seedY seed y
341 */
342void
343Zauberstab::findRegion(unsigned int seedX, unsigned int seedY)
344{
345 if (buffer == NULL)
346 return;
347 if (width == 0)
348 return;
349 if (height == 0)
350 return;
351
352 delete region;
353 region = privFindRegion(seedX, seedY);
354}
355
356/** Add region.
357 * @param seedX seed x
358 * @param seedY seed y
359 */
360void
361Zauberstab::addRegion(unsigned int seedX, unsigned int seedY)
362{
363 // STEP 1:
364 // find the region
365 ZRegion *region2 = privFindRegion(seedX, seedY);
366
367 // STEP 2:
368 // now merge the newly found region2 with the original region
369 addRegion(region2);
370
371 delete region2;
372}
373
374/** Find specific slice.
375 * @param x x
376 * @param y y
377 * @param vSeed v seed
378 * @return slice
379 */
380ZSlice *
381Zauberstab::findSlice(unsigned int x, unsigned int y, unsigned int vSeed, int uSeed)
382{
383 // slice with single pixel (x, y)
384 ZSlice *slice = new ZSlice;
385 slice->y = y;
386 slice->leftX = x;
387 slice->rightX = x;
388
389 unsigned char py __unused;
390 unsigned char pu = 0;
391 unsigned char pv = 0;
392 int tmpX = x + 1;
393
394 if ((unsigned int)tmpX < width) {
395 YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
396
397 // search to the right
398 while (uSeed >= 0 ? isSimilarUV(pu, uSeed, pv, vSeed) : isSimilarV(pv, vSeed)) {
399 (slice->rightX)++;
400 tmpX++;
401 if (tmpX >= (int)this->width) {
402 break;
403 } else {
404 YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
405 }
406 };
407 }
408
409 // search to the left
410 tmpX = x - 1;
411 if (tmpX >= 0) {
412 YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
413 while (uSeed >= 0 ? isSimilarUV(pu, uSeed, pv, vSeed) : isSimilarV(pv, vSeed)) {
414 (slice->leftX)--;
415 tmpX--;
416 if (tmpX < 0) {
417 break;
418 } else {
419 YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
420 }
421 };
422 }
423 /*
424 cout << "Zauberstab: Slice found." << endl;
425 cout << " (left : " << slice->leftX << endl
426 << " right: " << slice->rightX << endl
427 << " at y = " << slice->y << ")" << endl;
428 */
429 return slice;
430}
431
432/** Add region.
433 * @param region2 region to add
434 */
435void
437{
438 ZSlice *nSlice; //A slice to be added
439 ZSlice *oSlice; //A slice currently in the region
440
441 // add each slice from region 2 to region
442 while (region2->slices->size()) {
443 /* check if current slice from region 2 is at
444 at a height different from all slices at region */
445 nSlice = region2->slices->back();
446 region2->slices->pop_back();
447 int heightOfSlice = nSlice->y;
448
449 unsigned int i = 0;
450
451 while (i < region->slices->size()) //for all existing slices
452 {
453 oSlice = region->slices->at(i);
454 if (oSlice->y == heightOfSlice) //same height check for overlapping
455 {
456 if (((oSlice->leftX >= nSlice->leftX) && (oSlice->leftX <= nSlice->rightX))
457 || ((nSlice->leftX >= oSlice->leftX) && (nSlice->leftX <= oSlice->rightX))) {
458 //They are overlapping so grow the new slice
459 nSlice->leftX = min(nSlice->leftX, oSlice->leftX);
460 nSlice->rightX = max(nSlice->rightX, oSlice->rightX);
461
462 //and delete the old one
463 region->slices->erase(region->slices->begin() + i);
464 delete oSlice;
465
466 //The iterator i now points to the next element in the region->slices vector
467 continue;
468 }
469 }
470
471 ++i;
472 }
473
474 //By now all overlapping slices have been removed
475 region->slices->push_back(nSlice);
476 }
477}
478
479/** True if two V values are similar.
480 * @param v1 V value 1
481 * @param v2 V value 2
482 * @return true if V values are similar (depends on threshold)
483 */
484bool
485Zauberstab::isSimilarV(unsigned int v1, unsigned int v2)
486{
487 return ((unsigned int)abs((int)v1 - (int)v2) > this->threshold) ? false : true;
488}
489
490/** True if two U values are similar.
491 * @param u1 U value 1
492 * @param u2 U value 2
493 * @return true if U values are similar (depends on threshold)
494 */
495bool
496Zauberstab::isSimilarU(unsigned int u1, unsigned int u2)
497{
498 return ((unsigned int)abs((int)u1 - (int)u2) > this->threshold) ? false : true;
499}
500
501/** True if two u and V values are similar.
502 * @param u1 U value 1
503 * @param u2 U value 2
504 * @param v1 V value 1
505 * @param v2 V value 2
506 * @return true if V values are similar (depends on threshold)
507 */
508bool
509Zauberstab::isSimilarUV(unsigned int u1, unsigned int u2, unsigned int v1, unsigned int v2)
510{
511 return isSimilarU(u1, u2) && isSimilarV(v1, v2);
512}
513
514/** Get region.
515 * @return region
516 */
517ZRegion *
519{
520 return region;
521}
522
523/** Get selection.
524 * @return selection as a vector of rectangles.
525 */
526vector<rectangle_t>
528{
529 vector<rectangle_t> rv;
530 rv.clear();
531
532 std::vector<ZSlice *>::iterator it;
533 for (it = region->slices->begin(); it != region->slices->end(); it++) {
534 rectangle_t rect;
535 rect.start.x = (*it)->leftX;
536 rect.start.y = (*it)->y;
537 rect.extent.w = (*it)->rightX - (*it)->leftX;
538 rect.extent.h = 1;
539 rv.push_back(rect);
540 }
541
542 return rv;
543}
544
545} // end namespace firevision
a region is a stack of slices, together with the y-position of the slice at the top
Definition: zauberstab.h:56
std::vector< ZSlice * > * slices
slices
Definition: zauberstab.h:58
void clear()
Clears all slices.
Definition: zauberstab.cpp:65
ZRegion()
Constructor.
Definition: zauberstab.cpp:45
virtual ~ZRegion()
Constructor.
Definition: zauberstab.cpp:53
int topSliceY
top slice Y
Definition: zauberstab.h:59
ZRegion * getRegion() const
Get region.
Definition: zauberstab.cpp:518
void findRegion(unsigned int seedX, unsigned int seedY)
Find region.
Definition: zauberstab.cpp:343
void setThreshold(unsigned int t)
Set threshold.
Definition: zauberstab.cpp:103
std::vector< fawkes::rectangle_t > getSelection()
Get selection.
Definition: zauberstab.cpp:527
void deleteRegion()
Delete all regions.
Definition: zauberstab.cpp:141
void addRegion(unsigned int seedX, unsigned int seedY)
Add region.
Definition: zauberstab.cpp:361
unsigned int getThreshold()
Get threshold.
Definition: zauberstab.cpp:112
~Zauberstab()
Destructor.
Definition: zauberstab.cpp:94
Zauberstab()
Constructor.
Definition: zauberstab.cpp:79
void setBuffer(unsigned char *b, unsigned int w, unsigned int h)
Set buffer to work on.
Definition: zauberstab.cpp:123
bool isEmptyRegion()
Check if region is empty.
Definition: zauberstab.cpp:134
Fawkes library namespace.
unsigned int w
width
Definition: types.h:112
unsigned int h
height
Definition: types.h:113
Rectangle (unsigned integers)
Definition: types.h:118
upoint_t start
start point
Definition: types.h:119
extent_2d_t extent
extent
Definition: types.h:120
unsigned int x
x coordinate
Definition: types.h:36
unsigned int y
y coordinate
Definition: types.h:37
a "slice" is a row of consecutive pixels (horizontal)
Definition: zauberstab.h:40
int y
Y value.
Definition: zauberstab.h:43
int rightX
right X
Definition: zauberstab.h:42
int leftX
left X
Definition: zauberstab.h:41