FindBlobs.icpp

   1 /***********************************************************************
   2 FindBlobs - Helper function to extract all eight-connected blobs of
   3 pixels from a frame that match an arbitrary property.
   4 Copyright (c) 2010-2013 Oliver Kreylos
   5
   6 This file is part of the Augmented Reality Sandbox (SARndbox).
   7
   8 The Augmented Reality Sandbox is free software; you can redistribute it
   9 and/or modify it under the terms of the GNU General Public License as
  10 published by the Free Software Foundation; either version 2 of the
  11 License, or (at your option) any later version.
  12
  13 The Augmented Reality Sandbox is distributed in the hope that it will be
  14 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License along
  19 with the Augmented Reality Sandbox; if not, write to the Free Software
  20 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  21 ***********************************************************************/
  22
  23 #define FINDBLOBS_IMPLEMENTATION
  24
  25 #include "FindBlobs.h"
  26
  27 namespace {
  28
  29 template <class PixelParam>
  30 struct LineBlob // Helper structure to assemble blobs one line at a time
  31         {
  32         /* Embedded classes: */
  33         public:
  34         typedef PixelParam Pixel; // Underlying pixel type
  35
  36         /* Elements: */
  37         public:
  38         unsigned int x1,x2;
  39         unsigned int y;
  40         unsigned int parent,rank;
  41         unsigned int min[2],max[2];
  42         double sumX,sumY,sumW;
  43         BlobProperty<Pixel> blobProperty;
  44
  45         /* Methods: */
  46         void merge(const LineBlob& other)
  47                 {
  48                 for(int i=0;i<2;++i)
  49                         {
  50                         if(min[i]>other.min[i])
  51                                 min[i]=other.min[i];
  52                         if(max[i]<other.max[i])
  53                                 max[i]=other.max[i];
  54                         }
  55                 sumX+=other.sumX;
  56                 sumY+=other.sumY;
  57                 sumW+=other.sumW;
  58                 blobProperty.merge(other.blobProperty);
  59                 }
  60         };
  61
  62 }
  63
  64 template <class PixelParam,class PixelPropertyParam>
  65 inline
  66 std::vector<Blob<PixelParam> >
  67 findBlobs(const unsigned int size[2],
  68         const PixelParam* frame,
  69         const PixelPropertyParam& property)
  70         {
  71         /* Create a list of line blobs: */
  72         std::vector<LineBlob<PixelParam> > lineBlobs;
  73         unsigned int numLineBlobs=0; // Number of line blobs in the current list
  74         unsigned int lastLineStart=0; // Index of first line blob for the previous pixel row
  75         unsigned int lastLineEnd=0; // Index one after last line blob for the previous pixel row
  76
  77         /* Process all pixel rows: */
  78         const PixelParam* frameRowPtr=frame;
  79         for(unsigned int y=0;y<size[1];++y,frameRowPtr+=size[0])
  80                 {
  81                 /* Find all line blobs on the current line: */
  82                 unsigned int x=0;
  83                 const PixelParam* framePtr=frameRowPtr;
  84                 while(x<size[0])
  85                         {
  86                         /* Skip non-property pixels: */
  87                         while(x<size[0]&&!property(x,y,*framePtr))
  88                                 {
  89                                 ++x;
  90                                 ++framePtr;
  91                                 }
  92                         if(x>=size[0])
  93                                 break;
  94
  95                         /* Collect a new line blob: */
  96                         LineBlob<PixelParam> lb;
  97                         lb.x1=x;
  98                         lb.blobProperty.addPixel(x,y,*framePtr);
  99                         ++x;
 100                         ++framePtr;
 101                         while(x<size[0]&&property(x,y,*framePtr))
 102                                 {
 103                                 lb.blobProperty.addPixel(x,y,*framePtr);
 104                                 ++x;
 105                                 ++framePtr;
 106                                 }
 107                         lb.x2=x;
 108                         lb.y=y;
 109                         lb.parent=numLineBlobs;
 110                         lb.rank=0;
 111                         lb.min[0]=lb.x1;
 112                         lb.min[1]=y;
 113                         lb.max[0]=lb.x2;
 114                         lb.max[1]=y+1;
 115                         lb.sumW=double(lb.x2-lb.x1);
 116                         lb.sumX=double(lb.x1+lb.x2-1)*lb.sumW*0.5;
 117                         lb.sumY=double(y)*lb.sumW;
 118                         lineBlobs.push_back(lb);
 119                         ++numLineBlobs;
 120
 121                         /* Finish the line blob: */
 122                         ++x;
 123                         ++framePtr;
 124
 125                         /* Merge the new line blob with any line blobs it touches from the previous line: */
 126                         for(unsigned int i=lastLineStart;i<lastLineEnd;++i)
 127                                 {
 128                                 if(lineBlobs[i].x1<=lb.x2&&lineBlobs[i].x2>=lb.x1) // Check detects eight-connected blobs
 129                                         {
 130                                         /* Merge the two blobs: */
 131                                         unsigned int root1=i;
 132                                         while(root1!=lineBlobs[root1].parent)
 133                                                 root1=lineBlobs[root1].parent;
 134                                         unsigned int root2=numLineBlobs-1;
 135                                         while(root2!=lineBlobs[root2].parent)
 136                                                 root2=lineBlobs[root2].parent;
 137                                         if(root1!=root2)
 138                                                 {
 139                                                 if(lineBlobs[root1].rank>lineBlobs[root2].rank)
 140                                                         {
 141                                                         lineBlobs[root2].parent=root1;
 142                                                         lineBlobs[root1].merge(lineBlobs[root2]);
 143                                                         }
 144                                                 else
 145                                                         {
 146                                                         lineBlobs[root1].parent=root2;
 147                                                         if(lineBlobs[root1].rank==lineBlobs[root2].rank)
 148                                                                 ++lineBlobs[root2].rank;
 149                                                         lineBlobs[root2].merge(lineBlobs[root1]);
 150                                                         }
 151                                                 }
 152                                         }
 153                                 }
 154                         }
 155
 156                 /* Go to the next line: */
 157                 lastLineStart=lastLineEnd;
 158                 lastLineEnd=numLineBlobs;
 159                 }
 160
 161         /* Convert all line blobs that are their own parents into "real" blobs: */
 162         std::vector<Blob<PixelParam> > result;
 163         for(unsigned int i=0;i<numLineBlobs;++i)
 164                 {
 165                 /* Check if the line blob is a root and not just a single pixel: */
 166                 if(lineBlobs[i].parent==i&&lineBlobs[i].sumW>0.0)
 167                         {
 168                         Blob<PixelParam> b;
 169                         b.x=(lineBlobs[i].sumX+lineBlobs[i].sumW*0.5)/lineBlobs[i].sumW;
 170                         b.y=(lineBlobs[i].sumY+lineBlobs[i].sumW*0.5)/lineBlobs[i].sumW;
 171                         for(int j=0;j<2;++j)
 172                                 {
 173                                 b.min[j]=lineBlobs[i].min[j];
 174                                 b.max[j]=lineBlobs[i].max[j];
 175                                 }
 176                         b.blobProperty=lineBlobs[i].blobProperty;
 177                         result.push_back(b);
 178                         }
 179                 }
 180
 181         return result;
 182         }