c++ - 图形 gem IV。使用邻域图对二值图像进行细化

Question

这个表达式的算法是什么意思？

p = ((p<<1)&0666) | ((q<<3)&0110) | (Image->scanLine(y+1)[x+1] != 0);

《Graphics Gems IV》一书中的算法“Binary Image Thinning Using Neigborhood Maps”:

    static int  masks[] = {0200, 0002, 0040, 0010};

 uchar delete_[512] = 
 {
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,1,0,0,1,1,  0,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,1,1,1,0,1,1,  0,0,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,1,1,0,0,1,1, 
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  0,0,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,  0,0,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,0,0,0,0,0,0,  1,1,1,1,0,0,1,1,
  0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,
  1,0,1,1,1,0,1,1,  1,1,1,1,1,1,1,1
 };

  int xsize, ysize; 
  int x, y; 
 int i;  
 int count = 1; 
 int p, q;  
 uchar *qb;
 int m;


 xsize = Image->width();
 ysize = Image->height();
 qb = (uchar*) malloc (xsize*sizeof(uchar));
 qb[xsize-1] = 0;

    while(count) 
 { 
  count = 0;
  for (i = 0; i < 4; ++i) 
  {
   m = masks[i];
   p = Image->scanLine(0)[0] != 0;

   for (x = 0; x < xsize-1; ++x)
    qb[x] = p = ((p<<1)&0006) | (Image->scanLine(0)[x+1] != 0);

   // Scan image for pixel deletion candidates.
   for (y = 0; y < ysize-1; ++y) 
   {
    q = qb[0];
    p = ((q<<3)&0110) | (Image->scanLine(y+1)[0] != 0);

    for (x = 0; x < xsize-1; ++x) 
    { 
     q = qb[x];
     p = ((p<<1)&0666) | ((q<<3)&0110) | (Image->scanLine(y+1)[x+1] != 0);
     qb[x] = p;
     if  ((p&m)==0 && delete_[p])
     {
      count++;
      Image->scanLine(y)[x] = 0; 
     } 
    }

Answer 1

(见 commented source code )

变量 m 、 p 、 q 和 qb 数组的元素是 9 位数字，表示像素的 3x3 像素“邻域”。

假设您的图像看起来像这样(每个字母代表一个像素，它是“开”或“关”(1 或 0，黑色或白色):

    ---x---
    0123456
| 0 abcdefg
| 1 hijklmn
y 2 opqrstu
| 3 vwxyz{|

(x,y) 位置 (2,1) 处的像素是 j 。该像素的邻域是

bcd
ijk  // 3x3 grid centered on j
pqr

由于每个像素都有一个二进制值，邻域可以用 9 位表示。上面的邻域可以线性写出，用二进制表示为 bcd_ijk_pqr 。连续 3 个像素的分组使八进制成为一个不错的选择，因为每个八进制数字代表三个位。

一旦您有一个表示为 9 位值的邻域，您就可以对其进行位操作。诸如 ((p << 1) & 0666) 之类的操作采用邻域，将所有位向左移动一个位置，并清除最右边的位列。例如，移位将 bcd_ijk_pqr 更改为 cdi_jkp_qr@(其中 @ 表示“空”位，默认为 0)。然后掩码将其更改为 cd@_jk@_qr@ 。以3x3的网格形式表示:

cd@
jk@
qr@

本质上，整个网格都向左移动了。

类似地，诸如 ((q << 3) & 0110) 之类的操作会将所有位移动三个位置(将行向上移动)并清除前两列位。所以 bcd_ijk_pqr 变成 ijk_pqr_@@@ 然后在屏蔽之后，变成 @@k_@@r_@@@ 。

该算法的要点是评估每个像素的邻域，以确定是否关闭该像素(删除它)。此行进行评估:

if  ((p&m)==0 && delete_[p])

该行之前的所有内容都是为了在 p 中设置邻域。代码的编写使得每个像素值在每次通过时都被准确读取一次。

qb 数组存储前一个扫描线中每个像素的邻域。请注意，qb 的元素只有 8 位宽。这意味着省略了邻域的左上角像素。这不是问题，因为任何时候使用 qb，它都会向上移动一行。

所以回答你关于这条线做什么的问题:

p = ((p<<1)&0666) | ((q<<3)&0110) | (Image->scanLine(y+1)[x+1] != 0);

它通过合并以下内容创建像素的邻域:

• 同一条线上前一个像素的邻域，左移
• 右列相邻像素高一排，上移
• 图像的(x+1,y+1)像素，放在“西南”角

例如，关于j的邻域计算为:

p = bc@_ij@_pq@ | @@d_@@k_@@@ | r

    bc@ | @@d | @@@   bcd
p = ij@ | @@k | @@@ = ijk
    pq@ | @@@ | @@r   pqr