Графика Самоцветы IV. Разбиение бинарных изображений с использованием карт небрежности

Question

Что означает алгоритм этого выражения?

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

Алгоритм "Binary Разбавление Image Использование Neigborhood карты" в книге "Графика 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; 
    } 
    } 

Answer 1

(см commented source code)

Переменные m, p, q, и элементы qb массива являются 9-битные числа, которые представляют собой 3x3-пиксельного "окрестности" пикселя.

Пусть ваше изображение выглядит следующим образом (каждая буква представляет собой пиксель, который является либо «на» или «выключено» (1 или 0, черный или белый):

---x--- 

| 0 abcdefg 
| 1 hijklmn 
y 2 opqrstu 
| 3 vwxyz{| 

Пиксель в точке (х, у) местоположения (2,1) является j. окрестности этого пикселя

bcd 
ijk // 3x3 grid centered on j 
pqr 

Поскольку каждый пиксель имеет двоичное значение, соседство может быть представлена ​​в 9 бит. окрестности выше, могут быть выписаны линейно, выраженный в двоичном виде как bcd_ijk_pqr. Группировка 3 пикселей в строке mak es восьмым хорошим выбором, поскольку каждая восьмеричная цифра представляет три бита.

Как только у вас есть окрестность, выраженная в 9-битовом значении, вы можете выполнять манипуляции с битами. Операция, такая как ((p << 1) & 0666), берет окрестности, сдвигает все биты влево на одну позицию и очищает самый правый столбец бит. Например, сдвиг изменяет bcd_ijk_pqr на cdi_jkp_qr@ (где @ представляет бит 'null', по умолчанию 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) пиксель изображения, поместите i Nto на «юго-западе» углом

Например, окрестность j рассчитываются как:

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

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

Answer 2

Похоже поразрядным манипуляции. Разве вы не понимаете отдельные операции, или вы не понимаете, почему совершает манипуляцию (если позже ссылка на описание алгоритма необходима, BTW)?

Operators в этой строке:

• << оператор сдвига вправо (переместить биты р на более значимые позиции в соответствии с аргументом RH)
• & в этом контексте побитовое и
• | в побитовое или

Полезная вещь, напомню здесь, что целочисленные литералы, которые начинают остроумие h '0' выражены в октал, что означает, что вы можете читать двоичные цифры прямо из экранного представления (ну, с небольшой практикой, во всяком случае). Константы здесь: (666) _8 = (110110110) _2 и (0110) _8 = (001001000) _2.