vcs.maemo.org Git - opencv/blob - src/cvaux/vs/enteringblobdetection.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   5 //  By downloading, copying, installing or using the software you agree to this license.
   6 //  If you do not agree to this license, do not download, install,
   7 //  copy or use the software.
   8 //
   9 //
  10 //                        Intel License Agreement
  11 //
  12 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  13 // Third party copyrights are property of their respective owners.
  14 //
  15 // Redistribution and use in source and binary forms, with or without modification,
  16 // are permitted provided that the following conditions are met:
  17 //
  18 //   * Redistribution's of source code must retain the above copyright notice,
  19 //     this list of conditions and the following disclaimer.
  20 //
  21 //   * Redistribution's in binary form must reproduce the above copyright notice,
  22 //     this list of conditions and the following disclaimer in the documentation
  23 //     and/or other materials provided with the distribution.
  24 //
  25 //   * The name of Intel Corporation may not be used to endorse or promote products
  26 //     derived from this software without specific prior written permission.
  27 //
  28 // This software is provided by the copyright holders and contributors "as is" and
  29 // any express or implied warranties, including, but not limited to, the implied
  30 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  31 // In no event shall the Intel Corporation or contributors be liable for any direct,
  32 // indirect, incidental, special, exemplary, or consequential damages
  33 // (including, but not limited to, procurement of substitute goods or services;
  34 // loss of use, data, or profits; or business interruption) however caused
  35 // and on any theory of liability, whether in contract, strict liability,
  36 // or tort (including negligence or otherwise) arising in any way out of
  37 // the use of this software, even if advised of the possibility of such damage.
  38 //
  39 //M*/
  40
  41 /*
  42 This file implements the virtual interface defined as "CvBlobDetector".
  43 This implementation based on a simple algorithm:
  44 A new blob is detected when several successive frames contains connected components
  45 which have uniform motion not at an unreasonably high speed.
  46 Separation from border and already tracked blobs are also considered.
  47
  48 For an entrypoint into the literature see:
  49
  50      Appearance Models for Occlusion Handling
  51      Andrew Senior &t al, 8p 2001
  52      http://www.research.ibm.com/peoplevision/PETS2001.pdf
  53
  54 */
  55
  56 //#define USE_OBJECT_DETECTOR
  57
  58 #include "_cvaux.h"
  59
  60 static int CompareContour(const void* a, const void* b, void* )
  61 {
  62     float           dx,dy;
  63     float           h,w,ht,wt;
  64     CvPoint2D32f    pa,pb;
  65     CvRect          ra,rb;
  66     CvSeq*          pCA = *(CvSeq**)a;
  67     CvSeq*          pCB = *(CvSeq**)b;
  68     ra = ((CvContour*)pCA)->rect;
  69     rb = ((CvContour*)pCB)->rect;
  70     pa.x = ra.x + ra.width*0.5f;
  71     pa.y = ra.y + ra.height*0.5f;
  72     pb.x = rb.x + rb.width*0.5f;
  73     pb.y = rb.y + rb.height*0.5f;
  74     w = (ra.width+rb.width)*0.5f;
  75     h = (ra.height+rb.height)*0.5f;
  76
  77     dx = (float)(fabs(pa.x - pb.x)-w);
  78     dy = (float)(fabs(pa.y - pb.y)-h);
  79
  80     //wt = MAX(ra.width,rb.width)*0.1f;
  81     wt = 0;
  82     ht = MAX(ra.height,rb.height)*0.3f;
  83     return (dx < wt && dy < ht);
  84 }
  85
  86 void cvFindBlobsByCCClasters(IplImage* pFG, CvBlobSeq* pBlobs, CvMemStorage* storage)
  87 {   /* Create contours: */
  88     IplImage*       pIB = NULL;
  89     CvSeq*          cnt = NULL;
  90     CvSeq*          cnt_list = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvSeq*), storage );
  91     CvSeq*          clasters = NULL;
  92     int             claster_cur, claster_num;
  93
  94     pIB = cvCloneImage(pFG);
  95     cvThreshold(pIB,pIB,128,255,CV_THRESH_BINARY);
  96     cvFindContours(pIB,storage, &cnt, sizeof(CvContour), CV_RETR_EXTERNAL);
  97     cvReleaseImage(&pIB);
  98
  99     /* Create cnt_list.      */
 100     /* Process each contour: */
 101     for(; cnt; cnt=cnt->h_next)
 102     {
 103         cvSeqPush( cnt_list, &cnt);
 104     }
 105
 106     claster_num = cvSeqPartition( cnt_list, storage, &clasters, CompareContour, NULL );
 107
 108     for(claster_cur=0; claster_cur<claster_num; ++claster_cur)
 109     {
 110         int         cnt_cur;
 111         CvBlob      NewBlob;
 112         double      M00,X,Y,XX,YY; /* image moments */
 113         CvMoments   m;
 114         CvRect      rect_res = cvRect(-1,-1,-1,-1);
 115         CvMat       mat;
 116
 117         for(cnt_cur=0; cnt_cur<clasters->total; ++cnt_cur)
 118         {
 119             CvRect  rect;
 120             CvSeq*  cnt;
 121             int k = *(int*)cvGetSeqElem( clasters, cnt_cur );
 122             if(k!=claster_cur) continue;
 123             cnt = *(CvSeq**)cvGetSeqElem( cnt_list, cnt_cur );
 124             rect = ((CvContour*)cnt)->rect;
 125
 126             if(rect_res.height<0)
 127             {
 128                 rect_res = rect;
 129             }
 130             else
 131             {   /* Unite rects: */
 132                 int x0,x1,y0,y1;
 133                 x0 = MIN(rect_res.x,rect.x);
 134                 y0 = MIN(rect_res.y,rect.y);
 135                 x1 = MAX(rect_res.x+rect_res.width,rect.x+rect.width);
 136                 y1 = MAX(rect_res.y+rect_res.height,rect.y+rect.height);
 137                 rect_res.x = x0;
 138                 rect_res.y = y0;
 139                 rect_res.width = x1-x0;
 140                 rect_res.height = y1-y0;
 141             }
 142         }
 143
 144         if(rect_res.height < 1 || rect_res.width < 1)
 145         {
 146             X = 0;
 147             Y = 0;
 148             XX = 0;
 149             YY = 0;
 150         }
 151         else
 152         {
 153             cvMoments( cvGetSubRect(pFG,&mat,rect_res), &m, 0 );
 154             M00 = cvGetSpatialMoment( &m, 0, 0 );
 155             if(M00 <= 0 ) continue;
 156             X = cvGetSpatialMoment( &m, 1, 0 )/M00;
 157             Y = cvGetSpatialMoment( &m, 0, 1 )/M00;
 158             XX = (cvGetSpatialMoment( &m, 2, 0 )/M00) - X*X;
 159             YY = (cvGetSpatialMoment( &m, 0, 2 )/M00) - Y*Y;
 160         }
 161         NewBlob = cvBlob(rect_res.x+(float)X,rect_res.y+(float)Y,(float)(4*sqrt(XX)),(float)(4*sqrt(YY)));
 162         pBlobs->AddBlob(&NewBlob);
 163
 164     }   /* Next cluster. */
 165
 166     #if 0
 167     {   // Debug info:
 168         IplImage* pI = cvCreateImage(cvSize(pFG->width,pFG->height),IPL_DEPTH_8U,3);
 169         cvZero(pI);
 170         for(claster_cur=0; claster_cur<claster_num; ++claster_cur)
 171         {
 172             int         cnt_cur;
 173             CvScalar    color = CV_RGB(rand()%256,rand()%256,rand()%256);
 174
 175             for(cnt_cur=0; cnt_cur<clasters->total; ++cnt_cur)
 176             {
 177                 CvSeq*  cnt;
 178                 int k = *(int*)cvGetSeqElem( clasters, cnt_cur );
 179                 if(k!=claster_cur) continue;
 180                 cnt = *(CvSeq**)cvGetSeqElem( cnt_list, cnt_cur );
 181                 cvDrawContours( pI, cnt, color, color, 0, 1, 8);
 182             }
 183
 184             CvBlob* pB = pBlobs->GetBlob(claster_cur);
 185             int x = cvRound(CV_BLOB_RX(pB)), y = cvRound(CV_BLOB_RY(pB));
 186             cvEllipse( pI,
 187                 cvPointFrom32f(CV_BLOB_CENTER(pB)),
 188                 cvSize(MAX(1,x), MAX(1,y)),
 189                 0, 0, 360,
 190                 color, 1 );
 191         }
 192
 193         cvNamedWindow( "Clusters", 0);
 194         cvShowImage( "Clusters",pI );
 195
 196         cvReleaseImage(&pI);
 197
 198     }   /* Debug info. */
 199     #endif
 200
 201 }   /* cvFindBlobsByCCClasters */
 202
 203 /* Simple blob detector.  */
 204 /* Number of successive frame to analyse: */
 205 #define EBD_FRAME_NUM   5
 206 class CvBlobDetectorSimple:public CvBlobDetector
 207 {
 208 public:
 209     CvBlobDetectorSimple();
 210    ~CvBlobDetectorSimple();
 211     int DetectNewBlob(IplImage* pImg, IplImage* pFGMask, CvBlobSeq* pNewBlobList, CvBlobSeq* pOldBlobList);
 212     void Release(){delete this;};
 213
 214 protected:
 215     IplImage*       m_pMaskBlobNew;
 216     IplImage*       m_pMaskBlobExist;
 217     /* Lists of connected components detected on previous frames: */
 218     CvBlobSeq*      m_pBlobLists[EBD_FRAME_NUM];
 219 };
 220
 221 /* Blob detector creator (sole interface function for this file) */
 222 CvBlobDetector* cvCreateBlobDetectorSimple(){return new CvBlobDetectorSimple;};
 223
 224 /* Constructor of BlobDetector: */
 225 CvBlobDetectorSimple::CvBlobDetectorSimple()
 226 {
 227     int i = 0;
 228     m_pMaskBlobNew = NULL;
 229     m_pMaskBlobExist = NULL;
 230     for(i=0;i<EBD_FRAME_NUM;++i)m_pBlobLists[i] = NULL;
 231
 232     SetModuleName("Simple");
 233 }
 234
 235 /* Destructor of BlobDetector: */
 236 CvBlobDetectorSimple::~CvBlobDetectorSimple()
 237 {
 238     int i;
 239     if(m_pMaskBlobExist) cvReleaseImage(&m_pMaskBlobExist);
 240     if(m_pMaskBlobNew) cvReleaseImage(&m_pMaskBlobNew);
 241     for(i=0; i<EBD_FRAME_NUM; ++i) delete m_pBlobLists[i];
 242 }   /* cvReleaseBlobDetector */
 243
 244 /* cvDetectNewBlobs
 245  * return 1 and fill blob pNewBlob by blob parameters
 246  * if new blob is detected:
 247  */
 248 int CvBlobDetectorSimple::DetectNewBlob(IplImage* /*pImg*/, IplImage* pFGMask, CvBlobSeq* pNewBlobList, CvBlobSeq* pOldBlobList)
 249 {
 250     int         result = 0;
 251     CvSize      S = cvSize(pFGMask->width,pFGMask->height);
 252     if(m_pMaskBlobNew == NULL ) m_pMaskBlobNew = cvCreateImage(S,IPL_DEPTH_8U,1);
 253     if(m_pMaskBlobExist == NULL ) m_pMaskBlobExist = cvCreateImage(S,IPL_DEPTH_8U,1);
 254
 255     /* Shift blob list: */
 256     {
 257         int     i;
 258         if(m_pBlobLists[0]) delete m_pBlobLists[0];
 259         for(i=1;i<EBD_FRAME_NUM;++i)m_pBlobLists[i-1]=m_pBlobLists[i];
 260         m_pBlobLists[EBD_FRAME_NUM-1] = new CvBlobSeq;
 261     }   /* Shift blob list. */
 262
 263     /* Create exist blob mask: */
 264     cvCopy(pFGMask, m_pMaskBlobNew);
 265
 266     /* Create contours and add new blobs to blob list: */
 267     {   /* Create blobs: */
 268         CvBlobSeq       Blobs;
 269         CvMemStorage*   storage = cvCreateMemStorage();
 270
 271 #if 1
 272         {   /* Glue contours: */
 273             cvFindBlobsByCCClasters(m_pMaskBlobNew, &Blobs, storage );
 274         }   /* Glue contours. */
 275 #else
 276         {   /**/
 277             IplImage*       pIB = cvCloneImage(m_pMaskBlobNew);
 278             CvSeq*          cnts = NULL;
 279             CvSeq*          cnt = NULL;
 280             cvThreshold(pIB,pIB,128,255,CV_THRESH_BINARY);
 281             cvFindContours(pIB,storage, &cnts, sizeof(CvContour), CV_RETR_EXTERNAL);
 282
 283             /* Process each contour: */
 284             for(cnt = cnts; cnt; cnt=cnt->h_next)
 285             {
 286                 CvBlob  NewBlob;
 287
 288                 /* Image moments: */
 289                 double      M00,X,Y,XX,YY;
 290                 CvMoments   m;
 291                 CvRect      r = ((CvContour*)cnt)->rect;
 292                 CvMat       mat;
 293
 294                 if(r.height < S.height*0.02 || r.width < S.width*0.02) continue;
 295
 296                 cvMoments( cvGetSubRect(m_pMaskBlobNew,&mat,r), &m, 0 );
 297                 M00 = cvGetSpatialMoment( &m, 0, 0 );
 298
 299                 if(M00 <= 0 ) continue;
 300
 301                 X  = cvGetSpatialMoment( &m, 1, 0 )/M00;
 302                 Y  = cvGetSpatialMoment( &m, 0, 1 )/M00;
 303
 304                 XX = (cvGetSpatialMoment( &m, 2, 0 )/M00) - X*X;
 305                 YY = (cvGetSpatialMoment( &m, 0, 2 )/M00) - Y*Y;
 306
 307                 NewBlob = cvBlob(r.x+(float)X,r.y+(float)Y,(float)(4*sqrt(XX)),(float)(4*sqrt(YY)));
 308
 309                 Blobs.AddBlob(&NewBlob);
 310
 311             }   /* Next contour. */
 312
 313             cvReleaseImage(&pIB);
 314
 315         }   /* One contour - one blob. */
 316 #endif
 317
 318         {   /* Delete small and intersected blobs: */
 319             int i;
 320             for(i=Blobs.GetBlobNum(); i>0; i--)
 321             {
 322                 CvBlob* pB = Blobs.GetBlob(i-1);
 323
 324                 if(pB->h < S.height*0.02 || pB->w < S.width*0.02)
 325                 {
 326                     Blobs.DelBlob(i-1);
 327                     continue;
 328                 }
 329                 if(pOldBlobList)
 330                 {
 331                     int j;
 332                     for(j=pOldBlobList->GetBlobNum(); j>0; j--)
 333                     {
 334                         CvBlob* pBOld = pOldBlobList->GetBlob(j-1);
 335                         if((fabs(pBOld->x-pB->x) < (CV_BLOB_RX(pBOld)+CV_BLOB_RX(pB))) &&
 336                            (fabs(pBOld->y-pB->y) < (CV_BLOB_RY(pBOld)+CV_BLOB_RY(pB))))
 337                         {   /* Intersection is present, so delete blob from list: */
 338                             Blobs.DelBlob(i-1);
 339                             break;
 340                         }
 341                     }   /* Check next old blob. */
 342                 }   /*  if pOldBlobList */
 343             }   /* Check next blob. */
 344         }   /*  Delete small and intersected blobs. */
 345
 346         {   /* Bubble-sort blobs by size: */
 347             int N = Blobs.GetBlobNum();
 348             int i,j;
 349             for(i=1; i<N; ++i)
 350             {
 351                 for(j=i; j>0; --j)
 352                 {
 353                     CvBlob  temp;
 354                     float   AreaP, AreaN;
 355                     CvBlob* pP = Blobs.GetBlob(j-1);
 356                     CvBlob* pN = Blobs.GetBlob(j);
 357                     AreaP = CV_BLOB_WX(pP)*CV_BLOB_WY(pP);
 358                     AreaN = CV_BLOB_WX(pN)*CV_BLOB_WY(pN);
 359                     if(AreaN < AreaP)break;
 360                     temp = pN[0];
 361                     pN[0] = pP[0];
 362                     pP[0] = temp;
 363                 }
 364             }
 365
 366             /* Copy only first 10 blobs: */
 367             for(i=0; i<MIN(N,10); ++i)
 368             {
 369                 m_pBlobLists[EBD_FRAME_NUM-1]->AddBlob(Blobs.GetBlob(i));
 370             }
 371
 372         }   /* Sort blobs by size. */
 373
 374         cvReleaseMemStorage(&storage);
 375
 376     }   /* Create blobs. */
 377
 378     /* Analyze blob list to find best blob trajectory: */
 379     {
 380         int     Count = 0;
 381         int     pBLIndex[EBD_FRAME_NUM];
 382         int     pBL_BEST[EBD_FRAME_NUM];
 383         int     i;
 384         int     finish = 0;
 385         double  BestError = -1;
 386         int     Good = 1;
 387
 388         for(i=0; i<EBD_FRAME_NUM; ++i)
 389         {
 390             pBLIndex[i] = 0;
 391             pBL_BEST[i] = 0;
 392         }
 393
 394         /* Check configuration exist: */
 395         for(i=0; Good && (i<EBD_FRAME_NUM); ++i)
 396             if(m_pBlobLists[i] == NULL || m_pBlobLists[i]->GetBlobNum() == 0)
 397                 Good = 0;
 398
 399         if(Good)
 400         do{ /* For each configuration: */
 401             CvBlob* pBL[EBD_FRAME_NUM];
 402             int     Good = 1;
 403             double  Error = 0;
 404             CvBlob* pBNew = m_pBlobLists[EBD_FRAME_NUM-1]->GetBlob(pBLIndex[EBD_FRAME_NUM-1]);
 405
 406             for(i=0; i<EBD_FRAME_NUM; ++i)  pBL[i] = m_pBlobLists[i]->GetBlob(pBLIndex[i]);
 407
 408             Count++;
 409
 410             /* Check intersection last blob with existed: */
 411             if(Good && pOldBlobList)
 412             {   /* Check intersection last blob with existed: */
 413                 int     k;
 414                 for(k=pOldBlobList->GetBlobNum(); k>0; --k)
 415                 {
 416                     CvBlob* pBOld = pOldBlobList->GetBlob(k-1);
 417                     if((fabs(pBOld->x-pBNew->x) < (CV_BLOB_RX(pBOld)+CV_BLOB_RX(pBNew))) &&
 418                        (fabs(pBOld->y-pBNew->y) < (CV_BLOB_RY(pBOld)+CV_BLOB_RY(pBNew))))
 419                         Good = 0;
 420                 }
 421             }   /* Check intersection last blob with existed. */
 422
 423             /* Check distance to image border: */
 424             if(Good)
 425             {   /* Check distance to image border: */
 426                 CvBlob*  pB = pBNew;
 427                 float    dx = MIN(pB->x,S.width-pB->x)/CV_BLOB_RX(pB);
 428                 float    dy = MIN(pB->y,S.height-pB->y)/CV_BLOB_RY(pB);
 429
 430                 if(dx < 1.1 || dy < 1.1) Good = 0;
 431             }   /* Check distance to image border. */
 432
 433             /* Check uniform motion: */
 434             if(Good)
 435             {
 436                 int     N = EBD_FRAME_NUM;
 437                 float   sum[2] = {0,0};
 438                 float   jsum[2] = {0,0};
 439                 float   a[2],b[2]; /* estimated parameters of moving x(t) = a*t+b*/
 440
 441                 int j;
 442                 for(j=0; j<N; ++j)
 443                 {
 444                     float   x = pBL[j]->x;
 445                     float   y = pBL[j]->y;
 446                     sum[0] += x;
 447                     jsum[0] += j*x;
 448                     sum[1] += y;
 449                     jsum[1] += j*y;
 450                 }
 451
 452                 a[0] = 6*((1-N)*sum[0]+2*jsum[0])/(N*(N*N-1));
 453                 b[0] = -2*((1-2*N)*sum[0]+3*jsum[0])/(N*(N+1));
 454                 a[1] = 6*((1-N)*sum[1]+2*jsum[1])/(N*(N*N-1));
 455                 b[1] = -2*((1-2*N)*sum[1]+3*jsum[1])/(N*(N+1));
 456
 457                 for(j=0; j<N; ++j)
 458                 {
 459                     Error +=
 460                         pow(a[0]*j+b[0]-pBL[j]->x,2)+
 461                         pow(a[1]*j+b[1]-pBL[j]->y,2);
 462                 }
 463
 464                 Error = sqrt(Error/N);
 465
 466                 if( Error > S.width*0.01 ||
 467                     fabs(a[0])>S.width*0.1 ||
 468                     fabs(a[1])>S.height*0.1)
 469                     Good = 0;
 470
 471             }   /* Check configuration. */
 472
 473
 474             /* New best trajectory: */
 475             if(Good && (BestError == -1 || BestError > Error))
 476             {
 477                 for(i=0; i<EBD_FRAME_NUM; ++i)
 478                 {
 479                     pBL_BEST[i] = pBLIndex[i];
 480                 }
 481                 BestError = Error;
 482             }   /* New best trajectory. */
 483
 484             /* Set next configuration: */
 485             for(i=0; i<EBD_FRAME_NUM; ++i)
 486             {
 487                 pBLIndex[i]++;
 488                 if(pBLIndex[i] != m_pBlobLists[i]->GetBlobNum()) break;
 489                 pBLIndex[i]=0;
 490             }   /* Next time shift. */
 491
 492             if(i==EBD_FRAME_NUM)finish=1;
 493
 494         } while(!finish);       /* Check next time configuration of connected components. */
 495
 496         #if 0
 497         {/**/
 498             printf("BlobDetector configurations = %d [",Count);
 499             int i;
 500             for(i=0; i<EBD_FRAME_NUM; ++i)
 501             {
 502                 printf("%d,",m_pBlobLists[i]?m_pBlobLists[i]->GetBlobNum():0);
 503             }
 504             printf("]\n");
 505
 506         }
 507         #endif
 508
 509         if(BestError != -1)
 510         {   /* Write new blob to output and delete from blob list: */
 511             CvBlob* pNewBlob = m_pBlobLists[EBD_FRAME_NUM-1]->GetBlob(pBL_BEST[EBD_FRAME_NUM-1]);
 512             pNewBlobList->AddBlob(pNewBlob);
 513
 514             for(i=0; i<EBD_FRAME_NUM; ++i)
 515             {   /* Remove blob from each list: */
 516                 m_pBlobLists[i]->DelBlob(pBL_BEST[i]);
 517             }   /* Remove blob from each list. */
 518
 519             result = 1;
 520
 521         }   /* Write new blob to output and delete from blob list. */
 522     }   /*  Analyze blob list to find best blob trajectory. */
 523
 524     return result;
 525
 526 }   /* cvDetectNewBlob */
 527
 528
 529
 530
 531 /* Simple blob detector2.  */
 532 /* Number of successive frames to analyse: */
 533 #define SEQ_SIZE_MAX    30
 534 #define SEQ_NUM         1000
 535 typedef struct
 536 {
 537     int     size;
 538     CvBlob* pBlobs[SEQ_SIZE_MAX];
 539 } DefSeq;
 540
 541 class CvBlobDetectorCC:public CvBlobDetector
 542 {
 543 public:
 544     CvBlobDetectorCC();
 545    ~CvBlobDetectorCC();
 546     int DetectNewBlob(IplImage* pImg, IplImage* pFGMask, CvBlobSeq* pNewBlobList, CvBlobSeq* pOldBlobList);
 547     void Release(){delete this;};
 548
 549     virtual void ParamUpdate()
 550     {
 551         if(SEQ_SIZE<1)SEQ_SIZE=1;
 552         if(SEQ_SIZE>SEQ_SIZE_MAX)SEQ_SIZE=SEQ_SIZE_MAX;
 553
 554 #ifdef USE_OBJECT_DETECTOR
 555         if( m_param_split_detector_file_name )
 556         {
 557             m_split_detector = new CvObjectDetector();
 558             if( !m_split_detector->Load( m_param_split_detector_file_name ) )
 559             {
 560                 delete m_split_detector;
 561                 m_split_detector = 0;
 562             }
 563             else
 564             {
 565                 m_min_window_size = m_split_detector->GetMinWindowSize();
 566                 m_max_border = m_split_detector->GetMaxBorderSize();
 567             }
 568         }
 569 #endif
 570     }
 571
 572 private:
 573     /* Lists of connected components detected on previous frames: */
 574     CvBlobSeq*      m_pBlobLists[SEQ_SIZE_MAX];
 575     DefSeq          m_TrackSeq[SEQ_NUM];
 576     int             m_TrackNum;
 577     float           m_HMin;
 578     float           m_WMin;
 579     float           m_MinDistToBorder;
 580     int             m_Clastering;
 581     int             SEQ_SIZE;
 582
 583     /* If not 0 then the detector is loaded from the specified file
 584      * and it is applied for splitting blobs which actually correspond
 585      * to groups of objects:
 586      */
 587     char*           m_param_split_detector_file_name;
 588     float           m_param_roi_scale;
 589     int             m_param_only_roi;
 590
 591     CvObjectDetector* m_split_detector;
 592     CvSize          m_min_window_size;
 593     int             m_max_border;
 594
 595     CvBlobSeq       m_detected_blob_seq;
 596     CvSeq*          m_roi_seq;
 597
 598     CvBlobSeq       m_debug_blob_seq;
 599 };
 600
 601 /* Blob detector creator (sole interface function for this file): */
 602 CvBlobDetector* cvCreateBlobDetectorCC(){return new CvBlobDetectorCC;}
 603
 604 /* Constructor for BlobDetector: */
 605 CvBlobDetectorCC::CvBlobDetectorCC() :
 606     m_split_detector(0),
 607     m_detected_blob_seq(sizeof(CvDetectedBlob)),
 608     m_roi_seq(0),
 609     m_debug_blob_seq(sizeof(CvDetectedBlob))
 610 {
 611     /*CvDrawShape shapes[] =
 612     {
 613         { CvDrawShape::RECT,    {{255,255,255}} },
 614         { CvDrawShape::RECT,    {{0,0,255}} },
 615         { CvDrawShape::ELLIPSE, {{0,255,0}} }
 616     };
 617     int num_shapes = sizeof(shapes) / sizeof(shapes[0]);*/
 618
 619     int i = 0;
 620     SEQ_SIZE = 10;
 621     AddParam("Latency",&SEQ_SIZE);
 622     for(i=0;i<SEQ_SIZE_MAX;++i)m_pBlobLists[i] = NULL;
 623     for(i=0;i<SEQ_NUM;++i)m_TrackSeq[i].size = 0;
 624     m_TrackNum = 0;
 625
 626     m_HMin = 0.02f;
 627     m_WMin = 0.01f;
 628     AddParam("HMin",&m_HMin);
 629     AddParam("WMin",&m_WMin);
 630     m_MinDistToBorder = 1.1f;
 631     AddParam("MinDistToBorder",&m_MinDistToBorder);
 632     CommentParam("MinDistToBorder","Minimal allowed distance from blob center to image border in blob sizes");
 633
 634     m_Clastering=1;
 635     AddParam("Clastering",&m_Clastering);
 636     CommentParam("Clastering","Minimal allowed distance from blob center to image border in blob sizes");
 637
 638     m_param_split_detector_file_name = 0;
 639 #ifdef USE_OBJECT_DETECTOR
 640     AddParam("Detector", &m_param_split_detector_file_name);
 641     CommentParam("Detector", "Detector file name");
 642 #endif
 643
 644     m_param_roi_scale = 1.5F;
 645     AddParam("ROIScale", &m_param_roi_scale);
 646     CommentParam("ROIScale", "Determines the size of search window around a blob");
 647
 648     m_param_only_roi = 1;
 649     AddParam("OnlyROI", &m_param_only_roi);
 650     CommentParam("OnlyROI", "Shows the whole debug image (0) or only ROIs where the detector was applied (1)");
 651
 652     m_min_window_size = cvSize(0,0);
 653     m_max_border = 0;
 654     m_roi_seq = cvCreateSeq( 0, sizeof(*m_roi_seq), sizeof(CvRect), cvCreateMemStorage() );
 655
 656     SetModuleName("CC");
 657 }
 658
 659 /* Destructor for BlobDetector: */
 660 CvBlobDetectorCC::~CvBlobDetectorCC()
 661 {
 662     int i;
 663     for(i=0; i<SEQ_SIZE_MAX; ++i)
 664     {
 665         if(m_pBlobLists[i])
 666             delete m_pBlobLists[i];
 667     }
 668
 669     if( m_roi_seq )
 670     {
 671         cvReleaseMemStorage( &m_roi_seq->storage );
 672         m_roi_seq = 0;
 673     }
 674     //cvDestroyWindow( "EnteringBlobDetectionDebug" );
 675 }   /* cvReleaseBlobDetector */
 676
 677
 678 /* cvDetectNewBlobs
 679  * Return 1 and fill blob pNewBlob  with
 680  * blob parameters if new blob is detected:
 681  */
 682 int CvBlobDetectorCC::DetectNewBlob(IplImage* /*pImg*/, IplImage* pFGMask, CvBlobSeq* pNewBlobList, CvBlobSeq* pOldBlobList)
 683 {
 684     int         result = 0;
 685     CvSize      S = cvSize(pFGMask->width,pFGMask->height);
 686
 687     /* Shift blob list: */
 688     {
 689         int     i;
 690         if(m_pBlobLists[SEQ_SIZE-1]) delete m_pBlobLists[SEQ_SIZE-1];
 691
 692         for(i=SEQ_SIZE-1; i>0; --i)  m_pBlobLists[i] = m_pBlobLists[i-1];
 693
 694         m_pBlobLists[0] = new CvBlobSeq;
 695
 696     }   /* Shift blob list. */
 697
 698     /* Create contours and add new blobs to blob list: */
 699     {   /* Create blobs: */
 700         CvBlobSeq       Blobs;
 701         CvMemStorage*   storage = cvCreateMemStorage();
 702
 703         if(m_Clastering)
 704         {   /* Glue contours: */
 705             cvFindBlobsByCCClasters(pFGMask, &Blobs, storage );
 706         }   /* Glue contours. */
 707         else
 708         { /**/
 709             IplImage*       pIB = cvCloneImage(pFGMask);
 710             CvSeq*          cnts = NULL;
 711             CvSeq*          cnt = NULL;
 712             cvThreshold(pIB,pIB,128,255,CV_THRESH_BINARY);
 713             cvFindContours(pIB,storage, &cnts, sizeof(CvContour), CV_RETR_EXTERNAL);
 714
 715             /* Process each contour: */
 716             for(cnt = cnts; cnt; cnt=cnt->h_next)
 717             {
 718                 CvBlob  NewBlob;
 719                 /* Image moments: */
 720                 double      M00,X,Y,XX,YY;
 721                 CvMoments   m;
 722                 CvRect      r = ((CvContour*)cnt)->rect;
 723                 CvMat       mat;
 724                 if(r.height < S.height*m_HMin || r.width < S.width*m_WMin) continue;
 725                 cvMoments( cvGetSubRect(pFGMask,&mat,r), &m, 0 );
 726                 M00 = cvGetSpatialMoment( &m, 0, 0 );
 727                 if(M00 <= 0 ) continue;
 728                 X = cvGetSpatialMoment( &m, 1, 0 )/M00;
 729                 Y = cvGetSpatialMoment( &m, 0, 1 )/M00;
 730                 XX = (cvGetSpatialMoment( &m, 2, 0 )/M00) - X*X;
 731                 YY = (cvGetSpatialMoment( &m, 0, 2 )/M00) - Y*Y;
 732                 NewBlob = cvBlob(r.x+(float)X,r.y+(float)Y,(float)(4*sqrt(XX)),(float)(4*sqrt(YY)));
 733                 Blobs.AddBlob(&NewBlob);
 734
 735             }   /* Next contour. */
 736
 737             cvReleaseImage(&pIB);
 738
 739         }   /* One contour - one blob. */
 740
 741         {   /* Delete small and intersected blobs: */
 742             int i;
 743             for(i=Blobs.GetBlobNum(); i>0; i--)
 744             {
 745                 CvBlob* pB = Blobs.GetBlob(i-1);
 746
 747                 if(pB->h < S.height*m_HMin || pB->w < S.width*m_WMin)
 748                 {
 749                     Blobs.DelBlob(i-1);
 750                     continue;
 751                 }
 752
 753                 if(pOldBlobList)
 754                 {
 755                     int j;
 756                     for(j=pOldBlobList->GetBlobNum(); j>0; j--)
 757                     {
 758                         CvBlob* pBOld = pOldBlobList->GetBlob(j-1);
 759                         if((fabs(pBOld->x-pB->x) < (CV_BLOB_RX(pBOld)+CV_BLOB_RX(pB))) &&
 760                            (fabs(pBOld->y-pB->y) < (CV_BLOB_RY(pBOld)+CV_BLOB_RY(pB))))
 761                         {   /* Intersection detected, delete blob from list: */
 762                             Blobs.DelBlob(i-1);
 763                             break;
 764                         }
 765                     }   /* Check next old blob. */
 766                 }   /*  if pOldBlobList. */
 767             }   /*  Check next blob. */
 768         }   /*  Delete small and intersected blobs. */
 769
 770         {   /* Bubble-sort blobs by size: */
 771             int N = Blobs.GetBlobNum();
 772             int i,j;
 773             for(i=1; i<N; ++i)
 774             {
 775                 for(j=i; j>0; --j)
 776                 {
 777                     CvBlob  temp;
 778                     float   AreaP, AreaN;
 779                     CvBlob* pP = Blobs.GetBlob(j-1);
 780                     CvBlob* pN = Blobs.GetBlob(j);
 781                     AreaP = CV_BLOB_WX(pP)*CV_BLOB_WY(pP);
 782                     AreaN = CV_BLOB_WX(pN)*CV_BLOB_WY(pN);
 783                     if(AreaN < AreaP)break;
 784                     temp = pN[0];
 785                     pN[0] = pP[0];
 786                     pP[0] = temp;
 787                 }
 788             }
 789
 790             /* Copy only first 10 blobs: */
 791             for(i=0; i<MIN(N,10); ++i)
 792             {
 793                 m_pBlobLists[0]->AddBlob(Blobs.GetBlob(i));
 794             }
 795
 796         }   /* Sort blobs by size. */
 797
 798         cvReleaseMemStorage(&storage);
 799
 800     }   /* Create blobs. */
 801
 802     {   /* Shift each track: */
 803         int j;
 804         for(j=0; j<m_TrackNum; ++j)
 805         {
 806             int     i;
 807             DefSeq* pTrack = m_TrackSeq+j;
 808
 809             for(i=SEQ_SIZE-1; i>0; --i)
 810                 pTrack->pBlobs[i] = pTrack->pBlobs[i-1];
 811
 812             pTrack->pBlobs[0] = NULL;
 813             if(pTrack->size == SEQ_SIZE)pTrack->size--;
 814         }
 815     }   /* Shift each track. */
 816
 817     /* Analyze blob list to find best blob trajectory: */
 818     {
 819         double      BestError = -1;
 820         int         BestTrack = -1;;
 821         CvBlobSeq*  pNewBlobs = m_pBlobLists[0];
 822         int         i;
 823         int         NewTrackNum = 0;
 824         for(i=pNewBlobs->GetBlobNum(); i>0; --i)
 825         {
 826             CvBlob* pBNew = pNewBlobs->GetBlob(i-1);
 827             int     j;
 828             int     AsignedTrack = 0;
 829             for(j=0; j<m_TrackNum; ++j)
 830             {
 831                 double  dx,dy;
 832                 DefSeq* pTrack = m_TrackSeq+j;
 833                 CvBlob* pLastBlob = pTrack->size>0?pTrack->pBlobs[1]:NULL;
 834                 if(pLastBlob == NULL) continue;
 835                 dx = fabs(CV_BLOB_X(pLastBlob)-CV_BLOB_X(pBNew));
 836                 dy = fabs(CV_BLOB_Y(pLastBlob)-CV_BLOB_Y(pBNew));
 837                 if(dx > 2*CV_BLOB_WX(pLastBlob) || dy > 2*CV_BLOB_WY(pLastBlob)) continue;
 838                 AsignedTrack++;
 839
 840                 if(pTrack->pBlobs[0]==NULL)
 841                 {   /* Fill existed track: */
 842                     pTrack->pBlobs[0] = pBNew;
 843                     pTrack->size++;
 844                 }
 845                 else if((m_TrackNum+NewTrackNum)<SEQ_NUM)
 846                 {   /* Duplicate existed track: */
 847                     m_TrackSeq[m_TrackNum+NewTrackNum] = pTrack[0];
 848                     m_TrackSeq[m_TrackNum+NewTrackNum].pBlobs[0] = pBNew;
 849                     NewTrackNum++;
 850                 }
 851             }   /* Next track. */
 852
 853             if(AsignedTrack==0 && (m_TrackNum+NewTrackNum)<SEQ_NUM )
 854             {   /* Initialize new track: */
 855                 m_TrackSeq[m_TrackNum+NewTrackNum].size = 1;
 856                 m_TrackSeq[m_TrackNum+NewTrackNum].pBlobs[0] = pBNew;
 857                 NewTrackNum++;
 858             }
 859         }   /* Next new blob. */
 860
 861         m_TrackNum += NewTrackNum;
 862
 863         /* Check each track: */
 864         for(i=0; i<m_TrackNum; ++i)
 865         {
 866             int     Good = 1;
 867             DefSeq* pTrack = m_TrackSeq+i;
 868             CvBlob* pBNew = pTrack->pBlobs[0];
 869             if(pTrack->size != SEQ_SIZE) continue;
 870             if(pBNew == NULL ) continue;
 871
 872             /* Check intersection last blob with existed: */
 873             if(Good && pOldBlobList)
 874             {
 875                 int k;
 876                 for(k=pOldBlobList->GetBlobNum(); k>0; --k)
 877                 {
 878                     CvBlob* pBOld = pOldBlobList->GetBlob(k-1);
 879                     if((fabs(pBOld->x-pBNew->x) < (CV_BLOB_RX(pBOld)+CV_BLOB_RX(pBNew))) &&
 880                        (fabs(pBOld->y-pBNew->y) < (CV_BLOB_RY(pBOld)+CV_BLOB_RY(pBNew))))
 881                         Good = 0;
 882                 }
 883             }   /* Check intersection last blob with existed. */
 884
 885             /* Check distance to image border: */
 886             if(Good)
 887             {   /* Check distance to image border: */
 888                 float    dx = MIN(pBNew->x,S.width-pBNew->x)/CV_BLOB_RX(pBNew);
 889                 float    dy = MIN(pBNew->y,S.height-pBNew->y)/CV_BLOB_RY(pBNew);
 890                 if(dx < m_MinDistToBorder || dy < m_MinDistToBorder) Good = 0;
 891             }   /* Check distance to image border. */
 892
 893             /* Check uniform motion: */
 894             if(Good)
 895             {   /* Check uniform motion: */
 896                 double      Error = 0;
 897                 int         N = pTrack->size;
 898                 CvBlob**    pBL = pTrack->pBlobs;
 899                 float       sum[2] = {0,0};
 900                 float       jsum[2] = {0,0};
 901                 float       a[2],b[2]; /* estimated parameters of moving x(t) = a*t+b*/
 902                 int         j;
 903
 904                 for(j=0; j<N; ++j)
 905                 {
 906                     float   x = pBL[j]->x;
 907                     float   y = pBL[j]->y;
 908                     sum[0] += x;
 909                     jsum[0] += j*x;
 910                     sum[1] += y;
 911                     jsum[1] += j*y;
 912                 }
 913
 914                 a[0] = 6*((1-N)*sum[0]+2*jsum[0])/(N*(N*N-1));
 915                 b[0] = -2*((1-2*N)*sum[0]+3*jsum[0])/(N*(N+1));
 916                 a[1] = 6*((1-N)*sum[1]+2*jsum[1])/(N*(N*N-1));
 917                 b[1] = -2*((1-2*N)*sum[1]+3*jsum[1])/(N*(N+1));
 918
 919                 for(j=0; j<N; ++j)
 920                 {
 921                     Error +=
 922                         pow(a[0]*j+b[0]-pBL[j]->x,2)+
 923                         pow(a[1]*j+b[1]-pBL[j]->y,2);
 924                 }
 925
 926                 Error = sqrt(Error/N);
 927
 928                 if( Error > S.width*0.01 ||
 929                     fabs(a[0])>S.width*0.1 ||
 930                     fabs(a[1])>S.height*0.1)
 931                     Good = 0;
 932
 933                 /* New best trajectory: */
 934                 if(Good && (BestError == -1 || BestError > Error))
 935                 {   /* New best trajectory: */
 936                     BestTrack = i;
 937                     BestError = Error;
 938                 }   /* New best trajectory. */
 939             }   /*  Check uniform motion. */
 940         }   /*  Next track. */
 941
 942         #if 0
 943         {   /**/
 944             printf("BlobDetector configurations = %d [",m_TrackNum);
 945             int i;
 946             for(i=0; i<SEQ_SIZE; ++i)
 947             {
 948                 printf("%d,",m_pBlobLists[i]?m_pBlobLists[i]->GetBlobNum():0);
 949             }
 950             printf("]\n");
 951         }
 952         #endif
 953
 954         if(BestTrack >= 0)
 955         {   /* Put new blob to output and delete from blob list: */
 956             assert(m_TrackSeq[BestTrack].size == SEQ_SIZE);
 957             assert(m_TrackSeq[BestTrack].pBlobs[0]);
 958             pNewBlobList->AddBlob(m_TrackSeq[BestTrack].pBlobs[0]);
 959             m_TrackSeq[BestTrack].pBlobs[0] = NULL;
 960             m_TrackSeq[BestTrack].size--;
 961             result = 1;
 962         }   /* Put new blob to output and mark in blob list to delete. */
 963     }   /*  Analyze blod list to find best blob trajectory. */
 964
 965     {   /* Delete bad tracks: */
 966         int i;
 967         for(i=m_TrackNum-1; i>=0; --i)
 968         {   /* Delete bad tracks: */
 969             if(m_TrackSeq[i].pBlobs[0]) continue;
 970             if(m_TrackNum>0)
 971                 m_TrackSeq[i] = m_TrackSeq[--m_TrackNum];
 972         }   /* Delete bad tracks: */
 973     }
 974
 975 #ifdef USE_OBJECT_DETECTOR
 976     if( m_split_detector && pNewBlobList->GetBlobNum() > 0 )
 977     {
 978         int num_new_blobs = pNewBlobList->GetBlobNum();
 979         int i = 0;
 980
 981         if( m_roi_seq ) cvClearSeq( m_roi_seq );
 982         m_debug_blob_seq.Clear();
 983         for( i = 0; i < num_new_blobs; ++i )
 984         {
 985             CvBlob* b = pNewBlobList->GetBlob(i);
 986             CvMat roi_stub;
 987             CvMat* roi_mat = 0;
 988             CvMat* scaled_roi_mat = 0;
 989
 990             CvDetectedBlob d_b = cvDetectedBlob( CV_BLOB_X(b), CV_BLOB_Y(b), CV_BLOB_WX(b), CV_BLOB_WY(b), 0 );
 991             m_debug_blob_seq.AddBlob(&d_b);
 992
 993             float scale = m_param_roi_scale * m_min_window_size.height / CV_BLOB_WY(b);
 994
 995             float b_width =   MAX(CV_BLOB_WX(b), m_min_window_size.width / scale)
 996                             + (m_param_roi_scale - 1.0F) * (m_min_window_size.width / scale)
 997                             + 2.0F * m_max_border / scale;
 998             float b_height = CV_BLOB_WY(b) * m_param_roi_scale + 2.0F * m_max_border / scale;
 999
1000             CvRect roi = cvRectIntersection( cvRect( cvFloor(CV_BLOB_X(b) - 0.5F*b_width),
1001                                                      cvFloor(CV_BLOB_Y(b) - 0.5F*b_height),
1002                                                      cvCeil(b_width), cvCeil(b_height) ),
1003                                              cvRect( 0, 0, pImg->width, pImg->height ) );
1004             if( roi.width <= 0 || roi.height <= 0 )
1005                 continue;
1006
1007             if( m_roi_seq ) cvSeqPush( m_roi_seq, &roi );
1008
1009             roi_mat = cvGetSubRect( pImg, &roi_stub, roi );
1010             scaled_roi_mat = cvCreateMat( cvCeil(scale*roi.height), cvCeil(scale*roi.width), CV_8UC3 );
1011             cvResize( roi_mat, scaled_roi_mat );
1012
1013             m_detected_blob_seq.Clear();
1014             m_split_detector->Detect( scaled_roi_mat, &m_detected_blob_seq );
1015             cvReleaseMat( &scaled_roi_mat );
1016
1017             for( int k = 0; k < m_detected_blob_seq.GetBlobNum(); ++k )
1018             {
1019                 CvDetectedBlob* b = (CvDetectedBlob*) m_detected_blob_seq.GetBlob(k);
1020
1021                 /* scale and shift each detected blob back to the original image coordinates */
1022                 CV_BLOB_X(b) = CV_BLOB_X(b) / scale + roi.x;
1023                 CV_BLOB_Y(b) = CV_BLOB_Y(b) / scale + roi.y;
1024                 CV_BLOB_WX(b) /= scale;
1025                 CV_BLOB_WY(b) /= scale;
1026
1027                 CvDetectedBlob d_b = cvDetectedBlob( CV_BLOB_X(b), CV_BLOB_Y(b), CV_BLOB_WX(b), CV_BLOB_WY(b), 1,
1028                         b->response );
1029                 m_debug_blob_seq.AddBlob(&d_b);
1030             }
1031
1032             if( m_detected_blob_seq.GetBlobNum() > 1 )
1033             {
1034                 /*
1035                  * Split blob.
1036                  * The original blob is replaced by the first detected blob,
1037                  * remaining detected blobs are added to the end of the sequence:
1038                  */
1039                 CvBlob* first_b = m_detected_blob_seq.GetBlob(0);
1040                 CV_BLOB_X(b)  = CV_BLOB_X(first_b);  CV_BLOB_Y(b)  = CV_BLOB_Y(first_b);
1041                 CV_BLOB_WX(b) = CV_BLOB_WX(first_b); CV_BLOB_WY(b) = CV_BLOB_WY(first_b);
1042
1043                 for( int j = 1; j < m_detected_blob_seq.GetBlobNum(); ++j )
1044                 {
1045                     CvBlob* detected_b = m_detected_blob_seq.GetBlob(j);
1046                     pNewBlobList->AddBlob(detected_b);
1047                 }
1048             }
1049         }   /* For each new blob. */
1050
1051         for( i = 0; i < pNewBlobList->GetBlobNum(); ++i )
1052         {
1053             CvBlob* b = pNewBlobList->GetBlob(i);
1054             CvDetectedBlob d_b = cvDetectedBlob( CV_BLOB_X(b), CV_BLOB_Y(b), CV_BLOB_WX(b), CV_BLOB_WY(b), 2 );
1055             m_debug_blob_seq.AddBlob(&d_b);
1056         }
1057     }   // if( m_split_detector )
1058 #endif
1059
1060     return result;
1061
1062 }   /* cvDetectNewBlob */
1063
1064