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

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)

变量mpqqb数组的元素是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/

    10-09 06:23