00001
00002 /***************************************************************************
00003  *  zauberstab.cpp - Implementation of class "Zauberstab"
00004  *                   which offers methods for finding 
00005  *                   maximal, color-contiguous region
00006  *                   around a seed pixel
00007  *
00008  *  Created: Mon Jul 02 2005
00009  *  Copyright  2005       Martin Heracles  <Martin.Heracles@rwth-aachen.de>
00010  *             2005-2008  Tim Niemueller   [www.niemueller.de]
00011  *
00012  ****************************************************************************/
00013
00014 /*  This program is free software; you can redistribute it and/or modify
00015  *  it under the terms of the GNU General Public License as published by
00016  *  the Free Software Foundation; either version 2 of the License, or
00017  *  (at your option) any later version. A runtime exception applies to
00018  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00019  *
00020  *  This program is distributed in the hope that it will be useful,
00021  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00022  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00023  *  GNU Library General Public License for more details.
00024  *
00025  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00026  */
00027
00028 #include <fvutils/color/zauberstab.h>
00029 #include <fvutils/color/yuv.h>
00030 #include <core/macros.h>
00031
00032 #include <cstdlib>
00033 #include <iostream>
00034
00035 using namespace std;
00036 using namespace fawkes;
00037 
00038 /** @class Zauberstab <fvutils/color/zauberstab.h>
00039  * Zaubertab selection utility.
00040  */
00041 
00042 /** Constructor. */
00043 ZRegion::ZRegion()
00044 {
00045   topSliceY = 0;
00046   slices = new vector<ZSlice*>();
00047   slices->clear();
00048 }
00049 
00050 /** Constructor. */
00051 ZRegion::~ZRegion()
00052 {
00053         for (std::vector<ZSlice*>::iterator it = slices->begin(); it != slices->end(); ++it)
00054         {
00055                 delete (*it);
00056         }
00057
00058         delete slices;
00059 }
00060 
00061 /** Clears all slices.
00062  */
00063 void
00064 ZRegion::clear()
00065 {
00066         for (std::vector<ZSlice*>::iterator it = slices->begin(); it != slices->end(); ++it)
00067         {
00068                 delete (*it);
00069         }
00070
00071         slices->clear();
00072 }
00073 
00074 /** @class Zauberstab <fvutils/color/zauberstab.h>
00075  * Zaubertab selection utility.
00076  */
00077 
00078 /** Constructor. */
00079 Zauberstab::Zauberstab() {
00080   // create empty region
00081   region = new ZRegion();
00082
00083   buffer = NULL;
00084   width = 0;
00085   height = 0;
00086
00087   /* by default, "Zauberstab" does not allow
00088      any deviation from seed color */
00089   this->threshold = 0 ;
00090 }
00091
00092 
00093 /** Destructor. */
00094 Zauberstab::~Zauberstab() {
00095   delete(region);
00096 }
00097
00098 
00099 /** Set threshold.
00100  * @param t new threshold
00101  */
00102 void
00103 Zauberstab::setThreshold(unsigned int t) {
00104   this->threshold = t;
00105 }
00106
00107 
00108 /** Get threshold.
00109  * @return threshold
00110  */
00111 unsigned int
00112 Zauberstab::getThreshold() {
00113   return this->threshold;
00114 }
00115
00116 
00117 /** Set buffer to work on.
00118  * @param b buffer
00119  * @param w width of image
00120  * @param h height of buffer
00121  */
00122 void
00123 Zauberstab::setBuffer(unsigned char *b,
00124                       unsigned int w,
00125                       unsigned int h) {
00126   this->buffer = b;
00127   this->width = w;
00128   this->height = h;
00129 }
00130
00131 
00132 /** Check if region is empty.
00133  * @return true if empty
00134  */
00135 bool
00136 Zauberstab::isEmptyRegion() {
00137   return (region->slices->size() == 0);
00138 }
00139
00140 
00141 /** Delete all regions. */
00142 void
00143 Zauberstab::deleteRegion() {
00144   region->clear();
00145 }
00146 
00147 /** Delete region.
00148  * @param seedX seed x
00149  * @param seedY seed y
00150  */
00151 void
00152 Zauberstab::deleteRegion(unsigned int seedX, unsigned int seedY)
00153 {
00154   // STEP 1:
00155   // find the region
00156   ZRegion* region2 = privFindRegion (seedX, seedY);
00157
00158   // STEP 2:
00159   // now delete the newly found region2 from the original region
00160   deleteRegion(region2);
00161
00162   delete region2;
00163 }
00164
00165 
00166 /** Delete region.
00167  * @param region2 region to delete
00168  */
00169 void
00170 Zauberstab::deleteRegion(ZRegion *region2)
00171 {
00172   ZSlice* nSlice; //A slice to be deleted
00173   ZSlice* oSlice; //A slice currently in the region
00174
00175         // delete each slice of region 2 from region
00176         while (region2->slices->size())
00177         {
00178                 /* check if current slice from region 2 is at
00179                          at a height different from all slices at region */
00180     nSlice = region2->slices->back();
00181     region2->slices->pop_back();
00182                 int heightOfSlice = nSlice->y;
00183
00184                 unsigned int i = 0;
00185                 unsigned int size = region->slices->size();
00186
00187                 while(i < size) //for all existing slices (but not the newly added)
00188                 {
00189                         oSlice = region->slices->at(i);
00190                         if (oSlice->y == heightOfSlice) //same height check for overlapping
00191                         {
00192                                 if ((oSlice->leftX >= nSlice->leftX)
00193                                                 && (oSlice->leftX < nSlice->rightX))
00194                                 {
00195                                         //The slice to delete starts before the slice to be deleted
00196                                         if (oSlice->rightX > nSlice->rightX) //A part of the region remains
00197                                         {
00198                                                 oSlice->leftX = nSlice->rightX;
00199                                         }
00200                                         else //The whole slice dissapears
00201                                         {
00202                                                 region->slices->erase(region->slices->begin() + i);
00203                                                 size--;
00204                                                 delete oSlice;
00205
00206                                                 //The index now points to the next element in the region->slices vector
00207                                                 continue;
00208                                         }
00209                                 }
00210
00211                                 if ((nSlice->leftX >= oSlice->leftX)
00212                                                 && (nSlice->leftX < oSlice->rightX))
00213                                 {
00214                                         //The slice to be deleted starts before the part that should be deleted
00215                                         if (oSlice->rightX <= nSlice->rightX)
00216                                         {//just truncate the old slices
00217                                                 oSlice->rightX = nSlice->leftX;
00218                                         }
00219                                         else //split the old spice
00220                                         {
00221                                                 ZSlice* newPart = new ZSlice;
00222                                                 newPart->rightX = oSlice->rightX;
00223                                                 newPart->leftX = nSlice->rightX;
00224                                                 newPart->y = heightOfSlice;
00225
00226                                                 oSlice->rightX = nSlice->leftX;
00227                                                 region->slices->push_back(newPart);
00228                                         }
00229                                 }
00230                         }
00231
00232                         i++;
00233                 }
00234         }
00235 }
00236 
00237 /** A private region finder
00238  * @param seedX seed x
00239  * @param seedY seed y
00240  * @return a ZRegion pointer (has to be deleted by the caller)
00241  */
00242 ZRegion*
00243 Zauberstab::privFindRegion (unsigned int seedX, unsigned int seedY)
00244 {
00245   unsigned char py __unused;
00246   unsigned char pu = 0;
00247   unsigned char pv = 0;
00248
00249   // STEP 1:
00250   // first of all find the region around (seedX, seedY)
00251   // (this is analogously to method "findRegion")
00252   // (could be done more elegantly without the following redundant code)
00253
00254   // create empty region
00255   ZRegion *region2 = new ZRegion();
00256
00257   /* find seed pixel's v-value
00258      (consider seed pixel's neighborhood
00259       and take average v-value) */
00260   unsigned int uSeed = 0;
00261   unsigned int vSeed = 0;
00262   unsigned int cnt = 0;
00263
00264   for (int x = seedX - 2; x <= (int)seedX + 2; ++x) {
00265     if (x < 0) continue;
00266     if ((unsigned int )x >= width) continue;
00267     for (int y = seedY - 2; y <= (int)seedY + 2; ++y) {
00268       if (y < 0) continue;
00269       if ((unsigned int)y >= height) continue;
00270       YUV422_PLANAR_YUV(buffer, width, height, x, y, py, pu, pv);
00271       uSeed += pu;
00272       vSeed += pv;
00273       ++cnt;
00274     }
00275   }
00276
00277         if (cnt)
00278         {
00279                 uSeed = uSeed / cnt;
00280                 vSeed = vSeed / cnt;
00281         }
00282   /* initial slice 
00283      thru seed pixel (seedX, seedY) */
00284   ZSlice *tmp = NULL;
00285   tmp = findSlice(seedX, seedY, vSeed, uSeed);
00286   region2->slices->push_back(tmp);
00287
00288   /* NOTE: The following search works fine for
00289      objects that are convex (such as ball, goal, ...).
00290      For non-convex objects it may miss parts
00291      (e.g. for a U-shaped object it can only find right or left half). */
00292
00293   // search downwards for more slices
00294   tmp = region2->slices->front();
00295   int tmpY = ((int)seedY >= (int)(height - 1)) ? height -1 : seedY + 1;
00296   // new "seed" pixel has x-coordinate in the middle of initial slice
00297   int tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
00298
00299   YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
00300   while (isSimilarUV(pu, uSeed, pv, vSeed)) {
00301     tmp = findSlice(tmpX, tmpY, vSeed, uSeed);
00302     region2->slices->push_back(tmp);
00303     // new "seed" pixel has x-coordinate in the middle of previous slice
00304     tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
00305     tmpY++;
00306     if (tmpY >= (int)this->height) {
00307       break;
00308     } else {
00309       YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
00310     }
00311   }
00312
00313   /* search upwards for more slices
00314      (start search from initial slice again) */
00315   tmp = region2->slices->front();
00316   tmpY = (seedY == 0) ? 0 : seedY - 1;
00317   // new "seed" pixel has x-coordinate in the middle of initial slice
00318   tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
00319
00320   YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
00321   while (isSimilarUV(pu, uSeed, pv, vSeed)) {
00322     tmp = findSlice(tmpX, tmpY, vSeed, uSeed);
00323     region2->slices->push_back(tmp);
00324     // new "seed" pixel has x-coordinate in the middle of previous slice
00325     tmpX = int(float(tmp->leftX + tmp->rightX) / 2.0);
00326     tmpY--;
00327     if (tmpY < 0) {
00328       break;
00329     } else {
00330       YUV422_PLANAR_YUV(buffer, width, height, tmpX, tmpY, py, pu, pv);
00331     }
00332   }
00333
00334   region2->topSliceY = tmpY + 1;
00335
00336         for (std::vector<ZSlice*>::iterator it = region2->slices->begin(); it != region2->slices->end(); ++it)
00337         {
00338                 cout << "start x: " << ((*it)->leftX) << " end x: " << ((*it)->rightX) << " y: " << ((*it)->y) << endl;
00339         }
00340         cout << endl;
00341   return region2;
00342 }
00343 
00344 /** Find region.
00345  * @param seedX seed x
00346  * @param seedY seed y
00347  */
00348 void
00349 Zauberstab::findRegion(unsigned int seedX, unsigned int seedY) {
00350   if (buffer == NULL) return;
00351   if (width == 0) return;
00352   if (height == 0) return;
00353
00354   delete region;
00355   region = privFindRegion(seedX, seedY);
00356 }
00357
00358 
00359 /** Add region.
00360  * @param seedX seed x
00361  * @param seedY seed y
00362  */
00363 void
00364 Zauberstab::addRegion(unsigned int seedX, unsigned int seedY)
00365 {
00366   // STEP 1:
00367   // find the region
00368   ZRegion* region2 = privFindRegion (seedX, seedY);
00369
00370   // STEP 2:
00371   // now merge the newly found region2 with the original region
00372   addRegion(region2);
00373
00374   delete region2;
00375 }
00376
00377 
00378 /** Find specific slice.
00379  * @param x x
00380  * @param y y
00381  * @param vSeed v seed
00382  * @return slice
00383  */
00384 ZSlice*
00385 Zauberstab::findSlice(unsigned int x, unsigned int y,
00386                       unsigned int vSeed, int uSeed)
00387 {
00388   // slice with single pixel (x, y)
00389   ZSlice *slice = new ZSlice;
00390   slice->y = y;
00391   slice->leftX = x;
00392   slice->rightX = x;
00393
00394   unsigned char py __unused;
00395   unsigned char pu=0;
00396   unsigned char pv=0;
00397   int tmpX = x + 1;
00398
00399   if ((unsigned int)tmpX < width)
00400   {
00401     YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
00402
00403     // search to the right
00404                 while (uSeed >= 0 ? isSimilarUV(pu, uSeed, pv, vSeed) : isSimilarV(pv, vSeed)) {
00405       (slice->rightX)++;
00406       tmpX++;
00407       if (tmpX >= (int)this->width) {
00408         break;
00409       } else {
00410         YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
00411       }
00412     };
00413   }
00414
00415   // search to the left
00416   tmpX = x - 1;
00417   if (tmpX >= 0)
00418   {
00419     YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
00420     while (uSeed >= 0 ? isSimilarUV(pu, uSeed, pv, vSeed) : isSimilarV(pv, vSeed)) {
00421       (slice->leftX)--;
00422       tmpX--;
00423       if (tmpX < 0) {
00424         break;
00425       } else {
00426         YUV422_PLANAR_YUV(buffer, width, height, tmpX, y, py, pu, pv);
00427       }
00428     };
00429   }
00430   /*
00431   cout << "Zauberstab: Slice found." << endl;
00432   cout << "            (left : " << slice->leftX << endl
00433        << "             right: " << slice->rightX << endl
00434        << "             at y = " << slice->y << ")" << endl;
00435   */
00436   return slice;
00437 }
00438
00439 
00440 /** Add region.
00441  * @param region2 region to add
00442  */
00443 void
00444 Zauberstab::addRegion(ZRegion *region2)
00445 {
00446   ZSlice* nSlice; //A slice to be added
00447   ZSlice* oSlice; //A slice currently in the region
00448
00449   // add each slice from region 2 to region
00450   while (region2->slices->size())
00451   {
00452     /* check if current slice from region 2 is at
00453        at a height different from all slices at region */
00454     nSlice = region2->slices->back();
00455     region2->slices->pop_back();
00456     int heightOfSlice = nSlice->y;
00457
00458                 unsigned int i = 0;
00459
00460                 while(i < region->slices->size()) //for all existing slices
00461                 {
00462                         oSlice = region->slices->at(i);
00463                         if (oSlice->y == heightOfSlice) //same height check for overlapping
00464                         {
00465                                 if (((oSlice->leftX >= nSlice->leftX)
00466                                      && (oSlice->leftX <= nSlice->rightX))
00467                                     || ((nSlice->leftX >= oSlice->leftX)
00468                                         && (nSlice->leftX <= oSlice->rightX)))
00469                                 {
00470                                         //They are overlapping so grow the new slice
00471                                         nSlice->leftX  = min(nSlice->leftX,  oSlice->leftX);
00472                                         nSlice->rightX = max(nSlice->rightX, oSlice->rightX);
00473
00474                                         //and delete the old one
00475                                         region->slices->erase(region->slices->begin() + i);
00476                                         delete oSlice;
00477
00478                                         //The iterator i now points to the next element in the region->slices vector
00479                                         continue;
00480                                 }
00481                         }
00482
00483                         ++i;
00484                 }
00485
00486                 //By now all overlapping slices have been removed
00487                 region->slices->push_back(nSlice);
00488   }
00489 }
00490
00491 
00492 /** True if two V values are similar.
00493  * @param v1 V value 1
00494  * @param v2 V value 2
00495  * @return true if V values are similar (depends on threshold)
00496  */
00497 bool
00498 Zauberstab::isSimilarV(unsigned int v1,
00499                        unsigned int v2) {
00500   return ( (unsigned int)abs((int)v1 - (int)v2) > this->threshold ) ? false : true;
00501 }
00502
00503 
00504 /** True if two U values are similar.
00505  * @param u1 U value 1
00506  * @param u2 U value 2
00507  * @return true if U values are similar (depends on threshold)
00508  */
00509 bool
00510 Zauberstab::isSimilarU(unsigned int u1,
00511                        unsigned int u2) {
00512   return ( (unsigned int)abs((int)u1 - (int)u2) > this->threshold ) ? false : true;
00513 }
00514
00515 
00516 /** True if two u and V values are similar.
00517  * @param u1 U value 1
00518  * @param u2 U value 2
00519  * @param v1 V value 1
00520  * @param v2 V value 2
00521  * @return true if V values are similar (depends on threshold)
00522  */
00523 bool
00524 Zauberstab::isSimilarUV(unsigned int u1, unsigned int u2,
00525                        unsigned int v1, unsigned int v2)
00526 {
00527   return isSimilarU(u1, u2) && isSimilarV(v1, v2);
00528 }
00529
00530 
00531 /** Get region.
00532  * @return region
00533  */
00534 ZRegion *
00535 Zauberstab::getRegion() const
00536 {
00537   return region;
00538 }
00539
00540 
00541 /** Get selection.
00542  * @return selection as a vector of rectangles.
00543  */
00544 vector< rectangle_t >
00545 Zauberstab::getSelection()
00546 {
00547
00548   vector< rectangle_t > rv;
00549   rv.clear();
00550
00551   std::vector< ZSlice *>::iterator it;
00552   for (it = region->slices->begin(); it != region->slices->end(); it++) {
00553     rectangle_t rect;
00554     rect.start.x = (*it)->leftX;
00555     rect.start.y = (*it)->y;
00556     rect.extent.w = (*it)->rightX - (*it)->leftX;
00557     rect.extent.h = 1;
00558     rv.push_back( rect );
00559   }
00560
00561   return rv;
00562 }