單元4. Segmentation II : Region Growing

1. Region-based segmentation:

如果R表示一張影像的全部範圍，影像切割的目的是將R切割成n個區塊：R1,R2,…,Rn 並滿足下列條件：

Seeded Region growing：

選取一批種子(seed)pixels，以seed為核心進行成長(grow)，判斷seed周圍pixels是否與seed具有相似的特性(灰階值、節理、色彩) ，如果是，則接受該pixel為同一region，再以此新的pixel為核心，繼續偵查周圍尚未被歸類到任一region的pixel，直到影像所有pixels都分類完成。

 

Following Adams and Bischof, we say that the seeds are grouped into n sets, A1; A2; . . .; An. Each step of the algorithm adds a single pixel to one of these sets. To achieve this and maintain a homogeneity criterion, the set T of all as-yet unallocated pixels bordering at least one region is employed

where N(x) is the nearest eight neighbors of the pixel x. If for xT we have that N(x) meets just one of the Ai, then the index i(x) {1; 2; . . .; n} is defined such that .We define d(x) to be a measure of how different x is from the region it adjoins. The simplest definition for d(x) is

where g(x) is the gray-scale intensity value of x. If N(x) meets two or more of the Ai, the value i(x) is taken to be the value of i such that N(x) meets Ai and  d(x) is minimized. A zT is then taken such that

and append z to Ai(z). This completes a single step of the algorithm and the same process is iterated until all pixels have been allocated to a set.

 

The implementation of SRG employs a linked list storing the data of T , which is ordered according to d(x) . Adams and Bischof refer to this as a sequentially sorted list (SSL). The SSL remains ordered throughout the progression of the algorithm, so that by simply processing the first entry at each time step, d(x) is satisfied. Thus, a search cost must be incurred to locate appropriate positions when adding new members to the SSL.

演算法：

Initialization:
根據起始分群標示(labeling)每一個seed所屬region，把每一個seed鄰近點放入SSL(sequentially sorted list)。
Region Growing:
While SSL不是空的 do
     從SSL移除第一個pixel y.
     測試y的鄰近點:
          if 所有y的鄰近點都已標示為相同region的label A then
            標示y為region A；
            更新region A的平均值mean；
            擇出y的鄰近點中不在SSL的pixel，計算該點灰階值與region A的平均灰階值(mean)的差距
               
          else
                標示y為邊界點label。

一個簡化的演算法版本：

// main function

      ......
      /* Initialize region statistics */
      Total = Count = 0;
      for (y = Yseed - 5; y <= Yseed + 5; y++)
         for (x = Xseed - 5; x <= Xseed + 5; x++)
            if ((x >= 0) && (y >= 0) && (x < nc-1) && (y < nr-1))
            {
               Count++;
               Total += ima1.m[y][x];
            }
      /* Perform recursive seeded region growing */
      RegionGrow(ima1, ima2, Xseed, Yseed);
      cout<<"region contain "<<Count<<" points with mean value = "<<Total/Count;
      ......

 

// RegionGrow function

void RegionGrow(uc2D &ima1, uc2D &ima2, int x, int y)
{
   float Diff, Mean;
 
   /* Check to see if point already part of region */
   if (ima2.m[y][x] == 0)
   {
      /* See if point is close enough to add */
      Mean = Total / Count;
      Diff = ima1.m[y][x] - Mean;
      if (Diff < 0) Diff = -Diff;
      if (Diff < Threshold)
      {
         /* Add point to region and consider neighbors */
         Total += ima1.m[y][x];
         Count++;
         ima2.m[y][x] = 1;
         if (x > 0) RegionGrow(x - 1, y);
         if (y > 0) RegionGrow(x, y - 1);
         if (x < Xdim - 2) RegionGrow(x + 1, y);
         if (y < Ydim - 2) RegionGrow(x, y + 1);
      }
   }
}
 
Region Growing示意圖

問題：

l         Seed-dependent : 選擇不同seed將會有不同的影像切割結果；.

l         如果seed剛好位於edge將無法進行影像切割

 

兩篇重要參考文獻：

  1. Rolf Adams, Leanne Bischof, "Seeded region growing", IEEE Trans. on PAMI, Vol. 16, No. 6, June 1994, pp. 641 -647
  2. Andrew Mehnert, Paul Jackway, "An improved seeded region growing algorithm", Pattern Recognition Letters, Vol. 18, 1997, pp. 1065-1071

其它最新參考文獻：

Robert D. Stewart, Iris Fermin, and Manfred Opper . Region growing with pulse-coupled neural networks, IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 13, NO. 6, NOVEMBER 2002