mser

static void extractMSER_8UC1_Pass( int* ioptr,  

             int* imgptr,  

             int*** heap_cur,  

             LinkedPoint* ptsptr,  

             MSERGrowHistory* histptr,  

             MSERConnectedComp* comptr,  

             int step,  

             int stepmask,  

             int stepgap,  

             MSERParams params,  

             int color,  

             CvSeq* contours,  

             CvMemStorage* storage )  

{  

   //设置第一个组块的灰度值为256，该灰度值是真实图像中不存在的灰度值，以区分真实图像的组块，从而判断程序是否结束  

   comptr->grey_level = 256;  

   //步骤2和步骤3  

   //指向第二个组块  

   comptr++;  

   //设置第二个组块为输入图像第一个像素（左上角）的灰度值  

   comptr->grey_level = (*imgptr)&0xff;  

   //初始化该组块  

   initMSERComp( comptr );  

   //在最高位标注该像素为已被访问过，即该值小于0  

   *imgptr |= 0x80000000;  

   //得到该像素所对应的堆，即指向它所对应的灰度值  

   heap_cur += (*imgptr)&0xff;  

   //定义方向，即偏移量，因为是4邻域，所以该数组分别对应右、下、左、上  

   int dir[] = { 1, step, -1, -step };  

#ifdef __INTRIN_ENABLED__  

   unsigned long heapbit[] = { 0, 0, 0, 0, 0, 0, 0, 0 };  

   unsigned long* bit_cur = heapbit+(((*imgptr)&0x700)>>8);  

#endif  

   //死循环，退出该死循环的条件有两个：一是到达组块的栈底；二是边界像素堆中没有任何值。达到栈底也就意味着堆中没有值，在此函数中两者是一致的。  

   for ( ; ; )  

   {  

       // take tour of all the 4 directions  

       //步骤4  

       //在4邻域内进行搜索  

       while ( ((*imgptr)&0x70000) < 0x40000 )  

       {  

           // get the neighbor  

           /* ((*imgptr)&0x70000)>>16得到第16位至第18位数据，该数据对应的4邻域的方向，再通过dir数组得到4邻域的偏移量，因此imgptr_nbr为当前像素4邻域中某一个方向上邻域的地址指针 */  

           int* imgptr_nbr = imgptr+dir[((*imgptr)&0x70000)>>16];  

           //检查邻域像素是否被访问过，如果被访问过，则会在第一位置1，因此该值会小于0，否则第一位为0，该值大于0  

           if ( *imgptr_nbr >= 0 ) // if the neighbor is not visited yet  

           {  

               //标注该像素已被访问过，即把第一位置1  

               *imgptr_nbr |= 0x80000000; // mark it as visited  

               //比较当前像素与邻域像素灰度值  

               if ( ((*imgptr_nbr)&0xff) < ((*imgptr)&0xff) )  

               {  

                   //如果邻域值小于当前值，把当前值放入堆中  

                   // when the value of neighbor smaller than current  

                   // push current to boundary heap and make the neighbor to be the current one  

                   // create an empty comp  

                   //堆中该像素灰度值的数量加1，即对该灰度值像素个数计数  

                   (*heap_cur)++;  

                   //把当前值的地址放入堆中  

                   **heap_cur = imgptr;  

                   //重新标注当前值的方向位，以备下一次访问该值时搜索下一个邻域  

                   *imgptr += 0x10000;  

                   //定位邻域值所对应的堆的位置  

                   //当前heap_cur所指向的灰度值为while循环搜索中的最小灰度值，即水溢过的最低点  

                   heap_cur += ((*imgptr_nbr)&0xff)-((*imgptr)&0xff);  

#ifdef __INTRIN_ENABLED__  

                   _bitset( bit_cur, (*imgptr)&0x1f );  

                   bit_cur += (((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8;  

#endif  

                   imgptr = imgptr_nbr;    //邻域值换为当前值  

                   //步骤3  

                   comptr++;    //创建一个组块  

                   initMSERComp( comptr );    //初始化该组块  

                   comptr->grey_level = (*imgptr)&0xff;    //为该组块的灰度值赋值  

                   //当某个邻域值小于当前值，则不对当前值再做任何操作，继续下次循环，在下次循环中，处理的则是该邻域值，即再次执行步骤4  

                   continue;  

               } else {  

                   //如果邻域值大于当前值，把邻域值放入堆中  

                   // otherwise, push the neighbor to boundary heap  

                   //找到该邻域值在堆中的灰度值位置，并对其计数，即对该灰度值像素个数计数  

                   heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)]++;  

                   //把该邻域像素地址放入堆中  

                   *heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)] = imgptr_nbr;  

#ifdef __INTRIN_ENABLED__  

                   _bitset( bit_cur+((((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8), (*imgptr_nbr)&0x1f );  

#endif  

               }  

           }  

           *imgptr += 0x10000;    //重新标注当前值的领域方向  

       }  

       //imsk表示结束while循环后所得到的最后像素地址与图像首地址的相对距离  

       int imsk = (int)(imgptr-ioptr);  

       //得到结束while循环后的最后像素的坐标位置  

       //从这里可以看出图像的宽采样2^N的好处，即imsk>>stepgap  

       ptsptr->pt = cvPoint( imsk&stepmask, imsk>>stepgap );  

       // get the current location  

       //步骤5  

       //对栈顶的组块的像素个数累加，即计算组块的面积大小，并链接组块内的像素点  

       //结束while循环后，栈顶组块的灰度值就是该次循环后得到的最小灰度值，也就是该组块为极低点，就相当于水已经流到了最低的位置  

       accumulateMSERComp( comptr, ptsptr );  

       //指向下一个像素点链表位置  

       ptsptr++;  

       // get the next pixel from boundary heap  

       //步骤6  

       /*结束while循环后，如果**heap_cur有值的话，heap_cur指向的应该是while循环中得到的灰度值最小值，也就是在组块的边界像素中，有与组块相同的灰度值，因此要把该值作为当前值继续while循环，也就是相当于组块面积的扩展*/  

       if ( **heap_cur )    //有值  

       {  

           imgptr = **heap_cur;    //把该像素点作为当前值  

           (*heap_cur)--;    //像素的个数要相应的减1  

#ifdef __INTRIN_ENABLED__  

           if ( !**heap_cur )  

               _bitreset( bit_cur, (*imgptr)&0x1f );  

#endif  

       //步骤7  

       //已经找到了最小灰度值的组块，并且边界像素堆中的灰度值都比组块的灰度值大，则这时需要组块，即计算最大稳定极值区域  

       } else {  

#ifdef __INTRIN_ENABLED__  

           bool found_pixel = 0;  

           unsigned long pixel_val;  

           for ( int i = ((*imgptr)&0x700)>>8; i < 8; i++ )  

           {  

               if ( _BitScanForward( &pixel_val, *bit_cur ) )  

               {  

                   found_pixel = 1;  

                   pixel_val += i<<5;  

                   heap_cur += pixel_val-((*imgptr)&0xff);  

                   break;  

               }  

               bit_cur++;  

           }  

           if ( found_pixel )  

#else  

           heap_cur++;    //指向高一级的灰度值  

           unsigned long pixel_val = 0;  

           //在边界像素堆中，找到边界像素中的最小灰度值  

           for ( unsigned long i = ((*imgptr)&0xff)+1; i < 256; i++ )  

           {  

               if ( **heap_cur )  

               {  

                   pixel_val = i;    //灰度值  

                   break;  

               }  

               //定位在堆中所对应的灰度值，与pixel_val是相等的  

               heap_cur++;  

           }  

           if ( pixel_val )    //如果找到了像素值  

#endif  

           {  

               imgptr = **heap_cur;    //从堆中提取出该像素  

               (*heap_cur)--;    //对应的像素个数减1  

#ifdef __INTRIN_ENABLED__  

               if ( !**heap_cur )  

                   _bitreset( bit_cur, pixel_val&0x1f );  

#endif  

               //进入处理栈子模块  

               if ( pixel_val < comptr[-1].grey_level )  

               //如果从堆中提取出的最小灰度值小于距栈顶第二个组块的灰度值，则说明栈顶组块和第二个组块之间仍然有没有处理过的组块，因此在计算完MSER值后还要继续返回步骤4搜索该组块  

               {  

                   // check the stablity and push a new history, increase the grey level  

                   //利用公式2计算栈顶组块的q(i)值  

                   if ( MSERStableCheck( comptr, params ) )    //是MSER  

                   {  

                       //得到组块内的像素点  

                       CvContour* contour = MSERToContour( comptr, storage );  

                       contour->color = color;    //标注是MSER-还是MSER+  

                       //把组块像素点放入序列中  

                       cvSeqPush( contours, &contour );  

                   }  

                   MSERNewHistory( comptr, histptr );  

                   //改变栈顶组块的灰度值，这样就可以和上一层的组块进行合并  

                   comptr[0].grey_level = pixel_val;  

                   histptr++;  

               } else {  

                   //从堆中提取出的最小灰度值大于等于距栈顶第二个组块的灰度值  

                   // keep merging top two comp in stack until the grey level >= pixel_val  

                   //死循环，用于处理灰度值相同并且相连的组块之间的合并  

                   for ( ; ; )  

                   {  

                       //指向距栈顶第二个组块  

                       comptr--;  

                       //合并前两个组块，并把合并后的组块作为栈顶组块  

                       MSERMergeComp( comptr+1, comptr, comptr, histptr );  

                       histptr++;  

                       /*如果pixel_val = comptr[0].grey_level，说明在边界上还有属于该组块的像素；如果pixel_val < comptr[0].grey_level，说明还有比栈顶组块灰度值更小的组块没有搜索到。这两种情况都需要回到步骤4中继续搜索组块*/  

                       if ( pixel_val <= comptr[0].grey_level )  

                           break;  

                       //合并栈内前两个组块，直到pixel_val < comptr[-1].grey_level为止  

                       if ( pixel_val < comptr[-1].grey_level )  

                       {  

                           // check the stablity here otherwise it wouldn‘t be an ER  

                           if ( MSERStableCheck( comptr, params ) )  

                           {  

                               CvContour* contour = MSERToContour( comptr, storage );  

                               contour->color = color;  

                               cvSeqPush( contours, &contour );  

                           }  

                           MSERNewHistory( comptr, histptr );  

                           comptr[0].grey_level = pixel_val;  

                           histptr++;  

                           break;  

                       }  

                   }  

               }  

           } else  

               //边界像素堆中没有任何像素，则退出死循环，该函数返回。  

               break;  

       }  

   }  

}