c++ - 图形 gem IV。使用邻域映射的二值图像细化

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

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

一本书“Graphics Gems IV”中的算法“使用近邻图进行二值图像细化”:

    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;
     }
    }

最佳答案

(请参阅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

关于c++ - 图形 gem IV。使用邻域映射的二值图像细化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2262984/