Новый Цепной Код = Chain Code или Crack Code

Современный Код для границ областей начинается с нулевой клетки 0-Клетка (x0,y0) и продолжается в виде цепочки Крэков (элементарных границ) 00=Восток, 01=Юг, 10=Запад, 11=Север. Код соответствует принципу Окаймления и всегда образует замкнутую Цепочку Крэков с начальной и конечной точкой в (x0,y0). Свойство 1: количество Юг-кодов = количеству Север-Кодов Свойство 2: количество Восток-кодов = количеству Запад-Кодов Свойство 3: Периметр области = общему количеству Крэк-Кодов. Правило 1: Стартовая точка всегда первая, высшая точка перехода от Фона к Объекту на Изображении. Правило 2: Стартовый Крэк всегда - Юг, т.е. направление обхода всегда такое, что объект находится слева, а Фон справа.

Пример 1:

0110 Image b = 1110           0100 Start = End = 0-Клетка (1/0) Крэк-Цепь = Юг, Запад, Юг, Восток, Юг, Восток, Север, Восток, Север, Север, Запад, Запад = ЮЗЮВЮВСВССЗЗ Часто используется английские названия south, east, north, west с сокращениями s,e,n,w. Тогда весь Цепной Код заданной области: (1/0)swsesenennww Периметр = Количество Крэков = 12, Площадь = Количество Пикселей = 6

Пример 2:

1000 Image b = 0010           0010 Область 1: (0/0)senw  , Периметр = 4, Площадь = 1 Область 2: (2/1)ssennw, Периметр = 6, Площадь = 2

Этот Цепной Код позволяет расширить себя до 3D-Растра. В этом случае он получить два дополнительных направления backwards = b и forwards = f.
b указывает в позитивном а f в негативном Z-направлении, т.е. b в монитор, а f из монитора. Законы, действующие для 2D-Цепного-Кода действуют соответственно и в 3D. Поэтому данная лекция ограничивается на 2D-Цепном-Коде.

Алгоритмы Цепного Кода

Алгоритмы Цепного Кода - это современная форма кодирования границ областей. Когда мы говорим об "отслеживании Контура", "Трассировке Областей", то обычно имеем в виду Алгоритмы Цепного Кода.

Задача: дано Изображение b[ySize, xSize] со значением 0=Фон и 1=Объект. В Изображении должен быть один и более ненулевых Пикселей, среди которых левый верхний определяется, как Стартовый c0[y0,x0] и у которого левый Кант c1v[y0,x0] определяется, как вертикальный стартовый Крэк в направлении Юг.
Так как стартовое направление - всегда Юг, то Объект всегда находится на левой стороне, а Фон на правой.
Должно быть заранее установлено для Объекта действует правило 4-х соседей или 8-ми соседей.
Нужно найти полный Крэк-Код, описывающий окаймление всех ненулевых областей (объектов).

Алгоритм при соседской 4-ке

Двигаясь по направлению Крэка проверяем следующий Пиксел слева от Крэка.
Если это 0, то поворачиваем налево, готово.
Если это 1, то проверяем Пиксел справа от Крэка.
Если это 0, идем вперед, готово.
Если это 1, идем направо, готово.
В псевдо-коде алгоритм выглядит так:
if ( Pixel слева впереди == Фон ) поворот налево;  
else if ( Pixel справа впереди == Фон ) иду прямо; else поворот направо.

case 'e':			if (b[y-1,x  ] == 0) goto n; else if (b[y  ,x  ] == 0) goto e; else goto s;
case 's':			if (b[y  ,x  ] == 0) goto e; else if (b[y  ,x-1] == 0) goto s; else goto w;
case 'w':			if (b[y  ,x-1] == 0) goto s; else if (b[y-1,x-1] == 0) goto w; else goto n;
case 'n':			if (b[y-1,x-1] == 0) goto w; else if (b[y-1,x  ] == 0) goto n; else goto e;

Алгоритм 4-ки  на C#, если Point start уже определен:

System.Text.StringBuilder cracks = new System.Text.StringBuilder();
cracks.Append( 's' );
Int32 x = start.X;
Int32 y = start.Y + 1;
Char last_crack = 's';
do
{ switch ( last_crack )
  { case 'e': if ( b[y-1,x  ] == 0 ) goto n; if ( b[y  ,x  ] == 0 ) goto e; goto s;
    case 's': if ( b[y  ,x  ] == 0 ) goto e; if ( b[y  ,x-1] == 0 ) goto s; goto w;
    case 'w': if ( b[y  ,x-1] == 0 ) goto s; if ( b[y-1,x-1] == 0 ) goto w; goto n;
    case 'n': if ( b[y-1,x-1] == 0 ) goto w; if ( b[y-1,x  ] == 0 ) goto n; goto e;
  }
  e: last_crack = 'e'; cracks.Append( 'e' ); x++; continue;
  s: last_crack = 's'; cracks.Append( 's' ); y++; continue;
  w: last_crack = 'w'; cracks.Append( 'w' ); x--; continue;
  n: last_crack = 'n'; cracks.Append( 'n' ); y--; continue;
} while ( x != start.X || y != start.Y );

Алгоритм при соседской 8-ке

Двигаясь по направлению Крэка проверяем следующий Пиксел права от Крэка.
Если это 1, то поворачиваем направо, готово.
Если это 0, то проверяем Пиксел слева от Крэка.
Если это 1, идем вперед, готово.
Если это 0, идем налево, готово.
В псевдо-коде алгоритм выглядит так:
if ( Pixel справа впереди == Объект ) поворот направо;  
else if ( Pixel слева впереди == Объект ) иду прямо; else поворот налево.

case 'e':			if (b[y  ,x  ] == 1) goto s; else if (b[y-1,x  ] == 1) goto e; else goto n;
case 's':			if (b[y  ,x-1] == 1) goto w; else if (b[y  ,x  ] == 1) goto s; else goto e;
case 'w':			if (b[y-1,x-1] == 1) goto n; else if (b[y  ,x-1] == 1) goto w; else goto s;
case 'n':			if (b[y-1,x  ] == 1) goto e; else if (b[y-1,x-1] == 1) goto n; else goto w;

Алгоритм 8-ки на C#, если Point start определен:

System.Text.StringBuilder cracks = new System.Text.StringBuilder();
cracks.Append( 's' );
Int32 x = start.X;
Int32 y = start.Y + 1;
Char last_crack = 's';
do
{ switch ( last_crack )
  { case 'e': if ( b[y  ,x  ] == 1 ) goto s; if ( b[y-1,x  ] == 1 ) goto e; goto n;
    case 's': if ( b[y  ,x-1] == 1 ) goto w; if ( b[y  ,x  ] == 1 ) goto s; goto e;
    case 'w': if ( b[y-1,x-1] == 1 ) goto n; if ( b[y  ,x-1] == 1 ) goto w; goto s;
    case 'n': if ( b[y-1,x  ] == 1 ) goto e; if ( b[y-1,x-1] == 1 ) goto n; goto w;
  }
  e: last_crack = 'e'; cracks.Append( 'e' ); x++; continue;
  s: last_crack = 's'; cracks.Append( 's' ); y++; continue;
  w: last_crack = 'w'; cracks.Append( 'w' ); x--; continue;
  n: last_crack = 'n'; cracks.Append( 'n' ); y--; continue;
} while ( x != start.X || y != start.Y );

Алгоритм сформулирован для бинарных Изображений.
Он также работает для градаций серого с Предельным Значением threshold, когда все обращения к Пикселам изменяют следующим образом:
при соседской 4-ке: if (b[...,...] == 0) меняется на: if (b[...,...] <  threshold)
при соседской 8-ке: if (b[...,...] == 1) меняется на: if (b[...,...] >= threshold)
С цветными Изображениями это работает, если определены критерии цвета, которые однозначно отделяют Объект от Фона.

Алгоритм на границе Изображения

Оба алгоритма не работают на границе, так как обращаются к не существующим Пикселам за пределами Изображения..
Допустим xSize == bmp.Width  = количество столбцов.
Допустим ySize == bmp.Height = количество строк.
Тогда:
левая граница: x == 0; правая граница: x == xSize-1
верхняя граница: y == 0; нижняя граница: y == ySize-1

Существует два решения этой проблемы:
1. Стереть по контуру Изображения всю информацию - принудительно сделать Фоном. В этом случае алгоритм никогда не дойдет до края.
2. Следить за текущей позицией и, в случае достижения границы, производит нужные изменения направления без обращения к Пикселам.
Алгоритм для соседской 4-ки с обработкой границ:
switch ( last_crack )
{ case 'e': if (x==xSize || b[y-1,x  ]==0) goto n; if (y==ySize || b[y  ,x  ]==0) goto e; goto s;
  case 's': if (y==ySize || b[y  ,x  ]==0) goto e; if (x==0     || b[y  ,x-1]==0) goto s; goto w;
  case 'w': if (x==0     || b[y  ,x-1]==0) goto s; if (y==0     || b[y-1,x-1]==0) goto w; goto n;
  case 'n': if (y==0     || b[y-1,x-1]==0) goto w; if (x==xSize || b[y-1,x  ]==0) goto n; goto e;
}

Алгоритм для соседской 8-ки с обработкой границ:
switch ( last_crack )
{ case 'e': if (x==xSize) goto n; if (y<ySize && b[y  ,x  ]==1) goto s; if (b[y-1,x  ]==1)
            goto e; goto n;
  case 's': if (y==ySize) goto e; if (x>0     && b[y  ,x-1]==1) goto w; if (b[y  ,x  ]==1)
            goto s; goto e;
  case 'w': if (x==0    ) goto s; if (y>0     && b[y-1,x-1]==1) goto n; if (b[y  ,x-1]==1)
            goto w; goto s;
  case 'n': if (y==0    ) goto w; if (x<xSize && b[y-1,x  ]==1) goto e; if (b[y-1,x-1]==1)
            goto n; goto w;
}

Поиск Стартовой Точки

В неизвестном изображении достаточно просто найти Стартовую Точку для первого Крэк-Кода первой области. Просто сканируя растр, начиная с левого верхнего угла, находится первый Крэк, возникающий на переходе от 0 к 1.

Дано: 
xSize == bmp.Width  = количество колонок.
ySize == bmp.Height = количество строк.

Тогда Стартовая Точка в матрице b размером b[ySize,xSize] находится следующим образом: 

//левая граница Изображения:   x == 0; правая граница Изображения: x == xSize-1 (==bmp.Width -1)
//верхняя граница Изображения: y == 0; нижняя граница Изображения: y == ySize-1 (==bmp.Height-1)
for ( y0 = 0; y0 < ySize; y0++ )
{ if ( b[y0,0]==1 ) { x0 = 0; goto found; } /* if there is a "1" in column 0 */
  for ( x0 = 1; x0 < xSize; x0++ )
    if ( b[y0,x0-1]==0 && b[y0,x0]==1 ) goto found;
}

Сложнее найти следующую Стартовую Точку после того, как несколько областей уже окантованы Цепным Кодом. Если нашелся первый вертикальный Крэк, то необходимо выяснить является ли этот Крэк действительно новым, или он уже участвует в окаймлении другой области.
Соответственно, по ходу окаймления, мы должны отмечать все найденные Южные Крэки, чтобы при дальнейших поисках они были исключены.
Проще всего это сделать, создав матрицу вертикальных Крэков Byte[,] c1v = new Byte[ySize,xSize+1],  занулив все ее значения, и записав все найденные вертикальные Крэки в виде номера j, который будет указывать на принадлежность данного Крэка определенной области. 
Если ожидается более 255 Цепочек Крэков, то переменная j и матрица C1V должны быть определены типом Int16или Int32 вместо типа Byte.

/* Collecting all Chain-Codes ( 4-connectivity, no border pixels allowed ) */
Int32 x0, y0, x, y, i;
Byte[,] c1v = new Byte[ySize,xSize+1];
Byte j = 0; /* Change to type Int32 if j > 255 ! */
Char last_crack; for ( y0 = 0; y0 < ySize; y0++ )
  for ( x0 = 1; x0 < xsize; x0++ )
    if ( b[y0,x0-1]==0 && b[y0,x0]==1 && c1v[y0,x0]==0 )
    { x = x0; y = y0 + 1; i = 1; j++; c1v[y0,x0] = j;
      cracks.Remove( 0, cracks.Length ); cracks.Append( 's' ); last_crack = 's';
      do
      { switch ( last_crack )
        { case 'e': if ( b[y-1,x  ]==0 ) goto n; if ( b[y  ,x  ]==0 ) goto e; goto s;
          case 's': if ( b[y  ,x  ]==0 ) goto e; if ( b[y  ,x-1]==0 ) goto s; goto w;
          case 'w': if ( b[y  ,x-1]==0 ) goto s; if ( b[y-1,x-1]==0 ) goto w; goto n;
          case 'n': if ( b[y-1,x-1]==0 ) goto w; if ( b[y-1,x  ]==0 ) goto n; goto e;
        }
        e: last_crack = 'e'; cracks.Append( 'e' ); x++; continue;
        s: last_crack = 's'; cracks.Append( 's' ); c1v[y,x] = j; y++; continue;
        w: last_crack = 'w'; cracks.Append( 'w' ); x--; continue;
        n: last_crack = 'n'; cracks.Append( 'n' ); y--; c1v[y,x] = j;continue;
      } while ( x != x0 || y != y0 );
    }

Матрица Вертикальных Крэков и Матрица Отметок

Алгоритм поиска Стартовых Точек создает матрицу C1V с пронумерованными границами областей.  Нумерация складывается от 1 до количество областей в порядке нахождения Стартовых Точек этих областей. Область Nr. 1 имеет самую высокую и левую Стартовую Точку, Стартовая Точка области Nr. 2 лежит дальше правее или ниже и т.д. 
Из матрицы вертикальных Крэков C1V можно легко воссоздать Матрицу Отметок C2, которая каждому Пикселу дает присваивает номер области.

Пример:

10001        110022       10002 Image b = 00101  C1V = 003322  C2 = 00302           00101        003322       00302 Область 1: (0/0)senw     Perimeter = 4, Area = 1 Область 2: (4/0)sssennnw Perimeter = 8, Area = 3 Область 3: (2/1)ssennw   Perimeter = 6, Area = 2

Внутреннее и Внешнее Окаймление

Одна область всегда имеет одно внешнее Окаймление, а также может иметь одно или более внутренних Окаймлений (дырок). Внутри этого внутреннего Окаймления могут лежать следующие области, как острова в море, которые также имеют свое Окаймление и так далее.
Алгоритм в приведенном виде устанавливает взаимоотношений Окаймлений и Областей, т.е. он не знает какой код (область) лежит внутри другого кода (области). 
Однако, если последовательно придерживаться правила, что Стартовая Точка всегда в левом верхнем углу левого Пиксела, в верхней строке, а также придерживаться условий, что все Цепные Коды всегда должны начинаться с Южного Крэка, и при обходе Область всегда лежит левее границы, тогда действуют правила:
a) Если последний Крэк в цепочке (указывающий на Стартовую Точку) имеет Западное направление, то этот код относится к внешнему окаймлению;
b) Если последний Крэк в цепочке имеет Восточное направление, то этот код относится к внутреннему окаймлению;

Пример C2-Матрицы с Дырками:

Code 1 содержит последний Крэк в направлении "w" и поэтому является внешним Окаймлением. Codes 2 и 3 имеют последний Крэк в направлении "e" и поэтому являются Дырками. Справа от (2/1) лежат два вертикальных Крэка от 2 и один от 1 (на внешней кранице Изображение). Это значит, что 2 лежит в 1. Справа от (5/2) лежат два вертикальных Крэка от 2 и один от 1. Это значит, что 3 не имеет отношения к 2, но находится в 1.

Периметр, Площадь, Центр Тяжести, описанный четырехугольник

Периметр
Периметр Цепочки Кода - равен количеству его Крэков (единичных неквантуемых отрезков).
Следствия данного определения:
Периметр одного Пиксела равен 4. А радиус одного Пиксела - 1/2.
Периметр растрового круга с радиусом  r равен 8 * r, т.е. идентично периметру описанного квадрата, а не выражению из аналитической геометрии 2*Math.Pi*r.
Одна область всегда имеет один внешний периметр, однако может дополнительно может содержать один или более внутренних периметров = периметры дырок.

Площадь
Площадь Цепочки Кода равна количеству окаймленных ею Пикселей.
Это количество отрицательно, если код содержит внутреннее окаймление (Дырку).
Формула расчета площади соответствует формуле расчета площади полигона:
F = сумма всех i-трапеций (x[i] - x[i+1]) * (y[i] + y[i+1]) / 2.
Если рассмотреть оба конца Крэков, как идущие друг за другом вершины Полигона, то получится:
для Запад-Крэков: x[i] - x[i+1] = 1 und y[i] = y[i+1] = y = Номер строки → F = F + y;
для Восток-Крэков : x[i] - x[i+1] = -1 und y[i] = y[i+1] = y = Номер строки → F = F - y;
для Юг-Крэков : x[i] - x[i+1] = 0 → F = F;
для Север-Крэков: x[i] - x[i+1] = 0 → F = F;
Таким образом, получается простой способ рассчета площадей Цепочек Кодов:
F = сумма всех номеров строк всех Восток-Кэков минус сумма всех номеров срок Запад-Крэков.
Таким образом, площадь Цепочки Кода будет положительной при внешнем Окаймлении и отрицательной при внутреннем Окаймлении. 
Площадь Области равна сумме положительных площадей с внешним Окаймлением плюс отрицательные площади Дырок.
Пример:

Центр Тяжести
Для расчета Центра Тяжести S = (xs,ys) Цепочки Кода - все Пикселы c2[y,x] внутри этой области представляются сжатыми до своих центральных Точек c0[y+0.5,x+0.5] , имеющих единичную массу.
xs = сумма всех x-координат сжатых элементов, деленная на их количество.
ys = сумма всех y-координат сжатых элементов, деленная на их количество.
Количество элементов = количество Пикселей = положительной площади Цепочки Кода. 
При расчете - все элементы Дырок должны быть исключены.

Описанный Четырехугольник

Описанный четырехугольник одной Области - обрамляет внешнее Окаймление (= внешний Крэк-Код) четырьмя прямыми. Эти прямые являются продолжением Крэков с минимальным и максимальным значениями колонок (xmin und xmax) и строк (ymin,ymax). Полностью определяется его верней левой Точкой Pmin=(xmin,ymin) и его правой нижней Точкой Pmax=(xmax,ymax).

Все расчеты в одной процедуре

void crack_calculations( int x0, int y0, Byte[] crack, int no )
{ /* x0, y0 = starting point; crack[0 .. no-1] contains e,s,w,n characters; */
  int x, y, xmin, ymin, xmax, ymax, i = 0, peri = 0; area = 0;
  float sx = 0, sy = 0;
  x = xmin = xmax = x0;
  y = ymin = ymax = y0;
  do
  { if ( i++ > no ) break;
    switch ( cracks[i-1] )
    { case 'e': x++; if (x > xmax) xmax=x; peri++; area += y; sx += y*(x+0.5); sy += y * y/2; break;
      case 's': y++; if (y > ymax) ymax=y; peri++; break;
      case 'w': x--; if (x < xmin) xmin=x; peri++; area -= y; sx -= y*(x+0.5); sy -= y * y/2; break;;
      case 'n': y--; if (y < ymin) ymin=y; peri++;;
    }
  } while ( x != x0 || y != y0 );
  sx /= area; sy /= area;
  /* here is a good place to print perimeter, area, sx, sy, xmin, ymin, xmax, ymax */
}