此表达式的算法是什么意思?
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);
它通过合并以下内容来创建像素的邻域:
例如,关于
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/