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 
35 using namespace std;
36 using namespace fawkes;
37 
38 namespace firevision {
39 
40 /** @class Zauberstab <fvutils/color/zauberstab.h>
41  * Zaubertab selection utility.
42  */
43 
44 /** Constructor. */
45 ZRegion::ZRegion()
46 {
47  topSliceY = 0;
48  slices = new vector<ZSlice *>();
49  slices->clear();
50 }
51 
52 /** Constructor. */
53 ZRegion::~ZRegion()
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  */
64 void
65 ZRegion::clear()
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. */
79 Zauberstab::Zauberstab()
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. */
94 Zauberstab::~Zauberstab()
95 {
96  delete (region);
97 }
98 
99 /** Set threshold.
100  * @param t new threshold
101  */
102 void
103 Zauberstab::setThreshold(unsigned int t)
104 {
105  this->threshold = t;
106 }
107 
108 /** Get threshold.
109  * @return threshold
110  */
111 unsigned int
112 Zauberstab::getThreshold()
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  */
122 void
123 Zauberstab::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  */
133 bool
134 Zauberstab::isEmptyRegion()
135 {
136  return (region->slices->size() == 0);
137 }
138 
139 /** Delete all regions. */
140 void
141 Zauberstab::deleteRegion()
142 {
143  region->clear();
144 }
145 
146 /** Delete region.
147  * @param seedX seed x
148  * @param seedY seed y
149  */
150 void
151 Zauberstab::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  */
167 void
168 Zauberstab::deleteRegion(ZRegion *region2)
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  */
232 ZRegion *
233 Zauberstab::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  */
342 void
343 Zauberstab::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  */
360 void
361 Zauberstab::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  */
380 ZSlice *
381 Zauberstab::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  */
435 void
436 Zauberstab::addRegion(ZRegion *region2)
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  */
484 bool
485 Zauberstab::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  */
495 bool
496 Zauberstab::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  */
508 bool
509 Zauberstab::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  */
518 Zauberstab::getRegion() const
519 {
520  return region;
521 }
522 
523 /** Get selection.
524  * @return selection as a vector of rectangles.
525  */
526 vector<rectangle_t>
527 Zauberstab::getSelection()
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
firevision::ZRegion::slices
std::vector< ZSlice * > * slices
slices
Definition: zauberstab.h:66
firevision::ZSlice::leftX
int leftX
left X
Definition: zauberstab.h:58
fawkes::extent_2d_t::h
unsigned int h
height
Definition: types.h:112
fawkes::rectangle_t::start
upoint_t start
start point
Definition: types.h:118
firevision::ZSlice::y
int y
Y value.
Definition: zauberstab.h:60
fawkes::extent_2d_t::w
unsigned int w
width
Definition: types.h:111
firevision::ZRegion
a region is a stack of slices, together with the y-position of the slice at the top
Definition: zauberstab.h:63
fawkes
firevision::ZRegion::topSliceY
int topSliceY
top slice Y
Definition: zauberstab.h:67
fawkes::upoint_t::y
unsigned int y
y coordinate
Definition: types.h:36
fawkes::rectangle_t::extent
extent_2d_t extent
extent
Definition: types.h:119
fawkes::rectangle_t
Rectangle (unsigned integers)
Definition: types.h:116
firevision::ZSlice::rightX
int rightX
right X
Definition: zauberstab.h:59
fawkes::upoint_t::x
unsigned int x
x coordinate
Definition: types.h:35
firevision::ZSlice
a "slice" is a row of consecutive pixels (horizontal)
Definition: zauberstab.h:47