Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

graphSegmentation_Filter.cpp

Go to the documentation of this file.
00001 /* ---------------------------------------------------------------------------
00002     Phission :
00003         Realtime Vision Processing System
00004 
00005     Copyright (C) 2003-2006 Philip D.S. Thoren (pthoren@cs.uml.edu)
00006     University of Massachusetts at Lowell,
00007     Laboratory for Artificial Intelligence and Robotics
00008 
00009     This file is part of Phission.
00010 
00011     Phission is free software; you can redistribute it and/or modify
00012     it under the terms of the GNU Lesser General Public License as published by
00013     the Free Software Foundation; either version 2 of the License, or
00014     (at your option) any later version.
00015 
00016     Phission is distributed in the hope that it will be useful,
00017     but WITHOUT ANY WARRANTY; without even the implied warranty of
00018     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019     GNU Lesser General Public License for more details.
00020 
00021     You should have received a copy of the GNU Lesser General Public License
00022     along with Phission; if not, write to the Free Software
00023     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00024 
00025  ---------------------------------------------------------------------------*/
00026 #ifdef HAVE_CONFIG_H
00027     #include <phissionconfig.h>
00028 #endif
00029 
00030 #include <phission.h>
00031 #include <graphSegmentation_Filter.h>
00032 
00033 #define phGRAPH_USE_RANDOM_COLORS() 0
00034 
00035 /* ---------------------------------------------------------------------------
00036  * Code in this file from "Efficient Graph Based Segmentation" source code
00037  *
00038  *  graphSegmentation_Filter::SegmentImage
00039  *  graphSegmentation_Filter::SegmentGraph
00040  *  graphSegmentation_Filter::ProcessGraph
00041  *  
00042  *  dist_rgb
00043  *
00044  *  class phUniverse
00045  *
00046  *  bool operator<(const ph_edge &a, const ph_edge &b) 
00047  *
00048  * 05/27/2007
00049  *  Code was edited by Philip Thoren (pthoren@cs.uml.edu)
00050  *  
00051  *  Formatted to my own crazy standards and optimized it for uint8_t images.
00052  *
00053  * ---------------------------------------------------------------------------
00054  * 
00055  * Copyright (C) 2006 Pedro Felzenszwalb
00056  * 
00057  * This program is free software; you can redistribute it and/or modify
00058  * it under the terms of the GNU General Public License as published by
00059  * the Free Software Foundation; either version 2 of the License, or
00060  * (at your option) any later version.
00061  * 
00062  * This program is distributed in the hope that it will be useful,
00063  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00064  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00065  * GNU General Public License for more details.
00066  * 
00067  * You should have received a copy of the GNU General Public License
00068  * along with this program; if not, write to the Free Software
00069  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
00070  */
00071 /* ------------------------------------------------------------------------ */
00072 phUniverse::phUniverse( uint32_t elements ) 
00073 {
00074     phFUNCTION("phUniverse::phUniverse")
00075     uint32_t i = 0;
00076     
00077     this->m_elts        = NULL;
00078     this->m_elts_size   = 0;
00079 
00080     phDALLOC(this->m_elts,
00081              this->m_elts_size,
00082              elements,
00083              ph_uni_elt);
00084     for (i = 0; i < elements; i++) 
00085     {
00086         this->m_elts[i].rank = 0;
00087         this->m_elts[i].size = 1;
00088         this->m_elts[i].p = i;
00089     }
00090     
00091     this->m_elt_count   = elements;
00092     this->m_num         = elements;
00093 
00094 error:
00095     return;
00096 }
00097 
00098 /* ------------------------------------------------------------------------ */
00099 phUniverse::~phUniverse() 
00100 {
00101     phFree(this->m_elts);
00102     this->m_elts_size   = 0;
00103     this->m_elt_count   = 0;
00104     this->m_num         = 0;
00105 }
00106 
00107 /* ------------------------------------------------------------------------ */
00108 void phUniverse::resize( uint32_t elements )
00109 {
00110     phFUNCTION("phUniverse::resize")
00111     if (elements > 0)
00112     {
00113         uint32_t i = 0;
00114 
00115         phDALLOC(this->m_elts,
00116                 this->m_elts_size,
00117                 elements,
00118                 ph_uni_elt);
00119         for (i = 0; i < elements; i++) 
00120         {
00121             this->m_elts[i].rank = 0;
00122             this->m_elts[i].size = 1;
00123             this->m_elts[i].p = i;
00124         }
00125 
00126         this->m_elt_count   = elements;
00127         this->m_num         = elements;
00128     }
00129     
00130     return;
00131 error:
00132     this->m_num         = 0;
00133     this->m_elt_count   = 0;
00134     this->m_elts_size   = 0;
00135 }
00136 
00137 /* ------------------------------------------------------------------------ */
00138 int phUniverse::find(int x) 
00139 {
00140     int y = x;
00141     
00142     while (y != this->m_elts[y].p)
00143     {
00144         y = this->m_elts[y].p;
00145     }
00146     
00147     this->m_elts[x].p = y;
00148     
00149     return y;
00150 }
00151 
00152 /* ------------------------------------------------------------------------ */
00153 int phUniverse::size(int x) const 
00154 { 
00155     return this->m_elts[x].size; 
00156 }
00157 
00158 /* ------------------------------------------------------------------------ */
00159 uint32_t phUniverse::num_sets() const 
00160 { 
00161     return this->m_num; 
00162 }
00163 
00164 /* ------------------------------------------------------------------------ */
00165 void phUniverse::join(int x, int y) 
00166 {
00167     ph_uni_elt *elts = this->m_elts;
00168     
00169     if (elts[x].rank > elts[y].rank) 
00170     {
00171         elts[y].p = x;
00172         elts[x].size += elts[y].size;
00173     }
00174     else 
00175     {
00176         elts[x].p = y;
00177         elts[y].size += elts[x].size;
00178         if (elts[x].rank == elts[y].rank)
00179             elts[y].rank++;
00180     }
00181     if (this->m_num == 1)
00182         this->m_num = 0;
00183     else
00184         this->m_num--;
00185 }
00186 
00187 /* ---------------------------------------------------------------------- */
00188 typedef float (*phDistFunctionType)( const uint8_t *ptr1,
00189                                      const uint8_t *ptr2 );
00190 
00191 /* ---------------------------------------------------------------------- */
00192 float dist_grey8(const uint8_t *ptr1,
00193                  const uint8_t *ptr2 )
00194 {
00195     return ((float)ptr1[0]-(float)ptr2[0]);
00196 }
00197 
00198 /* ---------------------------------------------------------------------- */
00199 float dist_hsv24(const uint8_t *ptr1,
00200                  const uint8_t *ptr2 )
00201 {
00202     float hd = ((float)ptr1[0]-(float)ptr2[0]);
00203     float sd = ((float)ptr1[1]-(float)ptr2[1]);
00204     float vd = ((float)ptr1[2]-(float)ptr2[2]);
00205     return sqrt((hd*hd*hd)+sd+vd);
00206 }
00207 
00208 /* ---------------------------------------------------------------------- */
00209 float dist_rgb24(const uint8_t *ptr1,
00210                  const uint8_t *ptr2 )
00211 {
00212     float rd = ((float)ptr1[0]-(float)ptr2[0]);
00213     float gd = ((float)ptr1[1]-(float)ptr2[1]);
00214     float bd = ((float)ptr1[2]-(float)ptr2[2]);
00215     return sqrt((rd*rd)+(gd*gd)+(bd*bd));
00216 }
00217 
00218 /* ---------------------------------------------------------------------- */
00219 graphSegmentation_Filter::graphSegmentation_Filter( uint32_t    min_size,
00220                                                     uint32_t    threshold,
00221                                                     int         color_blobs ):
00222     phFilter("graphSegmentation_Filter")
00223 
00224 {
00225     //phImageValidFormatMask;
00226     this->m_format = phImageRGB24 | phImageHSV24 | phImageGREY8;
00227 
00228     this->m_num_edges   = 0;
00229     
00230     this->m_edges       = NULL;
00231     this->m_edges_size  = 0;
00232     
00233     this->m_output      = NULL;
00234     this->m_output_size = 0;
00235 
00236     this->m_thresholds      = NULL;
00237     this->m_thresholds_size = 0;
00238 
00239     this->m_universe    = new phUniverse(0);
00240 
00241     this->m_min_size    = min_size;
00242     this->m_thresh      = threshold;
00243     this->m_color_blobs = color_blobs;
00244 }
00245 
00246 /* ---------------------------------------------------------------------- */
00247 graphSegmentation_Filter::~graphSegmentation_Filter()
00248 {
00249     phFree(this->m_edges);
00250     this->m_edges_size = 0;
00251     phFree(this->m_output);
00252     this->m_output_size = 0;
00253     phFree(this->m_thresholds);
00254     this->m_thresholds_size = 0;
00255     phDelete(this->m_universe);
00256 }
00257 
00258 /* ------------------------------------------------------------------------ */
00259 phFilter *graphSegmentation_Filter::cloneFilter()
00260 {
00261     phFUNCTION("graphSegmentation_Filter::cloneFilter")
00262     int locked = 0;
00263     graphSegmentation_Filter *graphSegmentation = new graphSegmentation_Filter();
00264     
00265     phTHIS_LOOSE_LOCK(locked);
00266     
00267     /* graphSegmentation->set(this->m_value); */
00268 
00269     phTHIS_LOOSE_UNLOCK(locked);
00270 
00271     return (phFilter *)graphSegmentation;
00272 }
00273 
00274 /* ---------------------------------------------------------------------- */
00275 int graphSegmentation_Filter::set( uint32_t   min_size,
00276                                    uint32_t   threshold,
00277                                    int        color_blobs )
00278 {
00279     phFUNCTION("graphSegmentation_Filter::set")
00280     int locked = 0;
00281     phTHIS_LOOSE_LOCK(locked);
00282     
00283     this->m_min_size    = min_size;
00284     this->m_thresh      = threshold;
00285     this->m_color_blobs = color_blobs;
00286 
00287     phTHIS_LOOSE_UNLOCK(locked);
00288     
00289     return phSUCCESS;
00290 }
00291 
00292 /* ---------------------------------------------------------------------- */
00293 int graphSegmentation_Filter::setMinSize( uint32_t min_size )
00294 {
00295     phFUNCTION("graphSegmentation_Filter::set")
00296     int locked = 0;
00297     phTHIS_LOOSE_LOCK(locked);
00298     
00299     this->m_min_size = min_size;
00300 
00301     phTHIS_LOOSE_UNLOCK(locked);
00302     
00303     return phSUCCESS;
00304 }
00305 
00306 /* ---------------------------------------------------------------------- */
00307 int graphSegmentation_Filter::setThreshold( uint32_t threshold )
00308 {
00309     phFUNCTION("graphSegmentation_Filter::set")
00310     int locked = 0;
00311     phTHIS_LOOSE_LOCK(locked);
00312     
00313     this->m_thresh = threshold;
00314 
00315     phTHIS_LOOSE_UNLOCK(locked);
00316     
00317     return phSUCCESS;
00318 }
00319 
00320 /* ---------------------------------------------------------------------- */
00321 int graphSegmentation_Filter::setColorBlobs( int color_blobs )
00322 {
00323     phFUNCTION("graphSegmentation_Filter::set")
00324     int locked = 0;
00325     phTHIS_LOOSE_LOCK(locked);
00326     
00327     this->m_color_blobs = color_blobs;
00328 
00329     phTHIS_LOOSE_UNLOCK(locked);
00330     
00331     return phSUCCESS;
00332 }
00333 /* ---------------------------------------------------------------------- */
00334 uint32_t graphSegmentation_Filter::getMinSize()
00335 {
00336     phFUNCTION("graphSegmentation_Filter::set")
00337     int locked = 0;
00338     uint32_t min_size = 0;
00339 
00340     phTHIS_LOOSE_LOCK(locked);
00341     
00342     min_size = this->m_min_size;
00343 
00344     phTHIS_LOOSE_UNLOCK(locked);
00345     
00346     return min_size;
00347 
00348 }
00349 
00350 /* ---------------------------------------------------------------------- */
00351 uint32_t graphSegmentation_Filter::getThreshold()
00352 {
00353     phFUNCTION("graphSegmentation_Filter::set")
00354     int locked = 0;
00355     uint32_t threshold = 0;
00356 
00357     phTHIS_LOOSE_LOCK(locked);
00358 
00359     threshold = this->m_thresh;
00360 
00361     phTHIS_LOOSE_UNLOCK(locked);
00362     
00363     return threshold;
00364 
00365 }
00366  
00367 /* ---------------------------------------------------------------------- */
00368 int graphSegmentation_Filter::getColorBlobs()
00369 {
00370     phFUNCTION("graphSegmentation_Filter::set")
00371     int locked = 0;
00372     int color_blobs = 0;
00373 
00374     phTHIS_LOOSE_LOCK(locked);
00375 
00376     color_blobs = this->m_color_blobs;
00377 
00378     phTHIS_LOOSE_UNLOCK(locked);
00379     
00380     return color_blobs;
00381 }
00382  
00383 /* ---------------------------------------------------------------------- */
00384 /* This algorithm was adapted from the "Efficient Graph Based Segmentation"
00385  * source code at:
00386  *                   http://people.cs.uchicago.edu/~pff/segment/
00387  *
00388  * It has been changed to work with a uint8_t buffer and use pointer arithmetic
00389  * to try and speed up the algorithm.
00390  *
00391  */
00392 void graphSegmentation_Filter::SegmentImage( )
00393 {
00394     ph_edge    *cur_edge = NULL;
00395     uint32_t num_edges= 0;
00396 
00397     phDistFunctionType distpixels = NULL;
00398     
00399           uint8_t *ptr= this->Image;
00400     const uint32_t w  = this->width;
00401     const uint32_t h  = this->height;
00402     const uint32_t d  = this->depth;
00403 
00404     register uint32_t x  = 0;
00405     register uint32_t y  = 0;
00406     
00407     uint8_t *ptr_cur        = (uint8_t *)ptr;
00408     uint8_t *ptr_right      = NULL;
00409     uint8_t *ptr_down       = NULL;
00410     uint8_t *ptr_down_right = NULL;
00411     uint8_t *ptr_up_right   = NULL;
00412 
00413     switch (format)
00414     {
00415         case phImageRGB24:
00416             distpixels = dist_rgb24;
00417         break;
00418         case phImageHSV24:
00419             distpixels = dist_hsv24;
00420         break;
00421         case phImageGREY8:
00422             distpixels = dist_grey8;
00423         break;
00424     }
00425     
00426     this->m_num_edges   = 0;
00427     cur_edge            = this->m_edges;
00428 
00429     for (y = 0; y < h; y++)
00430     {
00431         ptr_right = &(ptr_cur[d]);
00432         if (y < (h-1))
00433         {
00434             ptr_down        = &(ptr_cur[w*d]);
00435             ptr_down_right  = &(ptr_cur[(w+1)*d]);
00436         }
00437         if (y > 0)
00438         {
00439             ptr_up_right = &(ptr[((((y-1) * w)+1) * d)]);
00440         }
00441         for (x = 0; x < w; x++, ptr_cur += d)
00442         {
00443             /* right */
00444             if (x < w-1)
00445             {
00446                 cur_edge->a = y * w + x;
00447                 cur_edge->b = y * w + (x+1);
00448                 cur_edge->w = (distpixels)(ptr_cur, ptr_right);
00449                 
00450                 cur_edge++;
00451                 num_edges++;
00452                 ptr_right += d;
00453             }
00454 
00455             /* down */
00456             if (y < h-1)
00457             {
00458                 cur_edge->a = y * w + x;
00459                 cur_edge->b = (y+1) * w + x;
00460                 cur_edge->w = (distpixels)(ptr_cur, ptr_down);
00461                 
00462                 cur_edge++;
00463                 num_edges++;
00464                 ptr_down += d;
00465             }
00466 
00467             if ((x < w-1) && (y < h-1))
00468             {
00469                 cur_edge->a = y * w + x;
00470                 cur_edge->b = (y+1) * w + (x+1);
00471                 cur_edge->w = (distpixels)(ptr_cur, ptr_down_right);
00472 
00473                 cur_edge++;
00474                 num_edges++;
00475                 ptr_down_right += d;
00476             }
00477 
00478             if ((x < w-1) && (y > 0))
00479             {
00480                 cur_edge->a = y * w + x;
00481                 cur_edge->b = (y-1) * w + (x+1);
00482                 cur_edge->w = (distpixels)(ptr_cur, ptr_up_right);
00483 
00484                 cur_edge++;
00485                 num_edges++;
00486                 ptr_up_right += d;
00487             }
00488         }
00489     }
00490 
00491     this->m_num_edges   = num_edges;
00492 }
00493 
00494 /* ---------------------------------------------------------------------- */
00495 bool operator<(const ph_edge &a, const ph_edge &b) 
00496 {
00497     return a.w < b.w;
00498 }
00499 
00500 #define ph_GRAPHTHRESHOLD(size, c) (c/size)
00501 
00502 /* ---------------------------------------------------------------------- */
00503 int graphSegmentation_Filter::SegmentGraph()
00504 { 
00505     phFUNCTION("graphSegmentation_Filter::SegmentGraph")
00506 
00507     uint32_t    num_vertices= (this->width * this->height);
00508     float       c           = this->m_thresh;
00509     uint32_t    i           = 0;
00510     
00511     /* sort edges by weight */
00512     std::sort(this->m_edges, this->m_edges + this->m_num_edges);
00513     
00514     /* make a disjoint-set forest */
00515     this->m_universe->resize(num_vertices);
00516 
00517     /* init / alloc thresholds */
00518     phDALLOC(this->m_thresholds,
00519              this->m_thresholds_size,
00520              num_vertices,
00521              float);
00522     
00523     for (i = 0; i < num_vertices; i++)
00524         this->m_thresholds[i] = ph_GRAPHTHRESHOLD(1,c);
00525 
00526     /* for each ph_edge, in non-decreasing weight order... */
00527     for (i = 0; i < this->m_num_edges; i++) 
00528     {
00529         ph_edge *pedge = &(this->m_edges[i]);
00530 
00531         /* components connected by this ph_edge */
00532         int a = this->m_universe->find(pedge->a);
00533         int b = this->m_universe->find(pedge->b);
00534         if (a != b) 
00535         {
00536             if ((pedge->w <= this->m_thresholds[a]) && 
00537                 (pedge->w <= this->m_thresholds[b])) 
00538             {
00539                 this->m_universe->join(a, b);
00540                 a = this->m_universe->find(a);
00541                 this->m_thresholds[a] = pedge->w + 
00542                                ph_GRAPHTHRESHOLD(this->m_universe->size(a), c);
00543             }
00544         }
00545     }
00546 
00547     return phSUCCESS;
00548 error:
00549     return phFAIL;
00550 }
00551 
00552 /* ---------------------------------------------------------------------- */
00553 /* 
00554  * This is the code that actually segments the graph from the output 
00555  * generated in the graphSegmentation_Filter::SegmentImage method.
00556  *
00557  * This is also take from the original segment_image function from the
00558  * "Efficient Graph Based Segmentation" source code.
00559  *
00560  */
00561 void graphSegmentation_Filter::ProcessGraph( )
00562 {
00563     register uint32_t       i           = 0;
00564     register int            comp        = 0;
00565     register unsigned int   x;
00566     register unsigned int   y;
00567     uint8_t                *pixel       = NULL;
00568     uint8_t                *outptr      = this->m_output;
00569     uint32_t                lim         = this->width * this->height;
00570     uint32_t                w           = this->width;
00571     uint32_t                h           = this->height;
00572     uint32_t                d           = this->depth;
00573 
00574     phUniverse             *u           = this->m_universe;
00575 
00576     // post process small components
00577     for (i = 0; i < this->m_num_edges; i++)
00578     {
00579         int a = u->find(m_edges[i].a);
00580         int b = u->find(m_edges[i].b);
00581         if ((a != b) && 
00582             ((u->size(a) < this->m_min_size) || 
00583              (u->size(b) < this->m_min_size)))
00584         {
00585             u->join(a, b);
00586         }
00587     }
00588     
00589     #if phGRAPH_USE_RANDOM_COLORS()
00590     uint8_t *colors = new uint8_t[w*h*d];
00591     uint8_t *col_ptr = colors;
00592     for (y = 0; y < lim; y++ )
00593     {
00594         for (x = 0; x < d; x++ )
00595         {
00596             colors[x+y] = (uint8_t)random();
00597         }
00598     }
00599     #endif
00600 
00601     /* Edited from the original code that colors the blobs in that this 
00602      * colors the image for an RGB image represented by a uint8_t buffer */
00603     if (this->m_color_blobs)
00604     {
00605         for (y=0; y < h; y++ )
00606         {
00607             for (x = 0; x < w; x++, outptr += d )
00608             {
00609                 comp = u->find(y * w + x);
00610                 pixel = &(this->Image[((comp)) * d]);
00611                 phMemcpy(outptr,pixel,d);
00612                 
00613                 #if phGRAPH_USE_RANDOM_COLORS()
00614                 comp = u->find(y * w + x);
00615                 phMemcpy(outptr,&(colors[comp*d]),d);
00616                 #endif
00617             }
00618         }
00619     }
00620 
00621     #if phGRAPH_USE_RANDOM_COLORS()
00622     delete [] colors;
00623     #endif
00624 }
00625 
00626 /* ---------------------------------------------------------------------- */
00627 int graphSegmentation_Filter::filter()
00628 {
00629     phFUNCTION("graphSegmentation_Filter::filter")
00630    
00631     /* defined before being called:
00632      *  width, height, depth, format, Image
00633      */
00634     
00635     /* Begin Filter */
00636     phDALLOC(this->m_output,this->m_output_size,
00637              this->width*this->height*this->depth,
00638              uint8_t);
00639 
00640     phDALLOC(this->m_edges,this->m_edges_size,
00641              this->width*this->height*4,
00642              ph_edge)
00643 
00644     /* segment the image : populates this->m_edges */
00645     this->SegmentImage( );
00646     /* segment : Populates this->m_universe */
00647     this->SegmentGraph();
00648     /* process the graph : colors the image */
00649     this->ProcessGraph( );
00650 
00651     this->m_workspaceImage->setImage( this->width,
00652                                       this->height,
00653                                       this->format,
00654                                       0,
00655                                       this->m_output );
00656     
00657     /* End Filter */
00658     
00659     /* make sure to free up any space here, not including Image */
00660     
00661     return phSUCCESS;
00662     
00663 error:
00664     /* make sure to free up any space here, not including Image */
00665     
00666     return phFAIL;
00667     
00668 }
00669 
00670 




Copyright (C) 2002 - 2007 Philip D.S. Thoren ( pthoren@users.sourceforge.net )
University Of Massachusetts at Lowell
Robotics Lab
SourceForge.net Logo

Generated on Sat Jun 16 02:44:09 2007 for phission by  doxygen 1.4.4