Графика Gems IV.Разбавление двоичных изображений с помощью карт соседства

Question

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

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

Алгоритм "Разбавление двоичных изображений с использованием карт соседства" в книге "Графика 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

(см. закомментированный исходный код )

Переменные 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@. Выражается в виде сетки 3х3:

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

Answer 2

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

Операторы в этой строке:

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

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