圖形寶石四。使用Neigborhood地圖進行二值圖像細化

Question

這個表達式的算法是什麼意思？

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

算法「二值圖像細化使用鄰域地圖」一書中「圖形寶石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; 
    } 
    } 

Answer 1

（參見commented source code）

變量m，p，q和qb陣列的元素是表示一個像素的3×3像素「附近」的9比特數。

假設你的圖像看起來像這樣（每個字母代表一個像素，其是「接通」或「斷開」（1或0，黑色或白色）：

---x--- 

| 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個像素的分組mak因爲每個八進制數字代表三個比特，所以八進制數是一個不錯的選擇。

將鄰域表達爲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_@@@。

該算法的要點是評估每個像素的鄰域以確定是否關閉該像素（刪除它）。這條線做了評價：先於該行是爲了建立鄰里p

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

一切。代碼的寫法是每個像素值每次只讀一次。

qb數組存儲上一個掃描行中每個像素的鄰域。請注意0​​的元素只有8位寬。這意味着鄰域的左上角像素被省略。這不是問題，因爲任何時候使用qb，它都會上移一排。

因此，要回答你的問題什麼這行做：

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

它通過合併創建了一個像素附近的以下內容：

• 以前的像素在同一行附近，向左移動
• 像素鄰域的右列一排較高，向上移動
• 圖像的（x + 1，y + 1）像素，將i n要在「西南」一角

例如，關於j附近的計算公式爲：

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

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

Answer 2

它看起來像一個位操作。你不明白單個操作，或者你不明白爲什麼操作正在完成（如果後面的，鏈接到算法的描述是必不可少的，BTW）？

在該行Operators：

• <<向右移位運算符（移動p的比特以根據RH參數更顯著位置）在該上下文中
• &按位和
• |的按位或

這裏回顧一個有用的事情是，啓動智慧的整數文字h'0'表示爲八進制，這意味着您可以直接從屏幕表示中讀取二進制數字（無論如何，稍加練習）。這裏的常數是（666）_8 =（110110110）_2和（0110）_8 =（001001000）_2。