Контур цифровой формы с серийным кодированием

Пиксель является граничным пикселем, если он заполнен, но примыкает к пикселю, который не заполнен. Учитывая RLE-кодирование заполненных пикселей для каждой строки, мы можем работать с тремя соседними строками, чтобы вычислить RLE-версию граничных пикселей, а затем декодировать ее.

По сути, у нас есть алгоритм развертки. С тремя рядами, как

   ***********   ****
************************
  ****        ******

получаем очки события (^) от РЛЭ:

   ***********   ****
************************
  ****        ******
^ ^^  ^       ^  ^  ^^  ^

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

   ***********   ****
BBB***BBBBBBBBBBB***BBBB
  ****        ******

Затем для интервалов, которые заполнены, но не известны как границы, проверьте, есть ли место слева от левой конечной точки и есть ли место справа от правой конечной точки. Если да (соответственно), то это границы.

Примечание. В этом ответе предполагается, что "без контура" означает "в окружении 4 соседей", поэтому результат будет немного отличаться от вашего примера (1 зеленый пиксель вместо синего).

Все пиксели контура — это пиксели, в которых установлены не все 4 «соседних пикселя» (левый, правый, верхний и нижний пикселя).

При декодировании RLC сверху вниз можно получить контурные пиксели с помощью следующего алгоритма псевдокода:

 For the first line
   All decoded pixels are outline pixels
 For the subsequent lines
   Leftmost and rightmost pixels of each RLC run are outline pixels
   All other pixels are outline pixels if:
     The pixel above isn't set (case A)
     The pixel below isn't set (case B)

Варианты A и B означают, что вам придется смотреть на пиксели выше/ниже текущего пикселя, поэтому алгоритм на самом деле должен быть своего рода конвейером/просмотром вперед на одну строку, потому что случай B не сможет быть обнаружен до следующей строки. был расшифрован.

РЕДАКТИРОВАТЬ: чтобы впоследствии отсортировать пиксели по часовой стрелке, вы можете использовать тот факт, что ваш контур представляет собой диагонально соединенную линию шириной в один пиксель. Выбрав один из пикселей в самой верхней строке, вы получите два возможных следующих пикселя, следующие за тем, который находится справа, ниже или справа и ниже текущего пикселя. После этого просто следуйте за соседними пикселями, которые вы еще не посещали, пока не останется соседнего пикселя. Пример:

  /----- First pixel you pick, A and B are neighbour candidates, A is the "correct" one
  v
  xAxxx           
 B     x        
 x    x      xxx
 x     xxxxxx   x
  xx           x
    xxxxxxxxxxx

  s0123             Result after following the neighbours (s = start, e = end),
 e     4            numbers from 0-9 show order of traversal
 1    5      234
 0     678901   5
  98           6
    76543210987

Подсказка:

Как сказано в других ответах, испускание списка пикселей контура может быть реализовано как процесс развертки, во время которого проверяются окрестности 3x3 конечных точек запуска.

Эта процедура будет испускать пиксели в зашифрованном виде, как последовательность прямых и обратных дуг, которые необходимо сохранить и переупорядочить.

Альтернатива может быть основана на идее реализации стандартного алгоритма окрестности Мура, преимущество которого заключается в перечислении контурных пикселей в желаемом порядке.

Для этой процедуры требуется знать конфигурацию 8-окрестностей вокруг текущего пикселя, и идея состоит в том, чтобы обновлять эту окрестность при каждом переходе к другому пикселю: мы сохраняем индексы для серии, содержащей текущий пиксель, и для двух противоположных серий в строках. над и под.

При каждом переходе к другому пикселю нам нужно обновлять эти три индекса, что будет включать короткие последовательные поиски в списке отсортированных прогонов. Это можно рассматривать как механизм псевдослучайного доступа к пикселям, принимая во внимание, что последовательные доступы строго локальны и могут быть как бы кэшированы.

Обновление:

В представлении с кодированием длины серии, которое я использую, кодируются только черные серии, как тройки (X, Y, L). Прогоны сортируются по строкам сверху вниз, а затем слева направо подряд.

Для удобства можно перейти на схему «линейной адресации», как если бы все строки изображения были добавлены друг за другом, а каждый пиксель обозначен одним числом Z = X + Y.Nx (где Nx — ширина изображения).

Итак, у нас есть список черных серий, а белые неявно находятся между двумя последовательными черными.

Во время обработки мы всегда можем помнить индекс прогона, который начинается непосредственно перед текущим пикселем или на нем (R[I].Z <= Z < R[I+1].Z). Мы можем определить цвет пикселя, проверив, находимся ли мы внутри ряда или между ним и следующим (Z < R[I].Z + R[I].L).

Если мы переместимся на одну позицию влево, Z уменьшится на 1, и нам, возможно, придется выбрать предыдущий прогон (I--).

Если мы переместимся на одну позицию вверх, Z уменьшится на Nx, и нам, возможно, придется вернуться на несколько прогонов (с I-- до R[I].Z <= Z снова).

На картинке показан текущий пиксель и его 4-соседки, а также «зоны влияния» черных трасс. Мы можем обрабатывать все восемь направлений смещения одинаково.

Как мы видим, каждый ход занимает количество операций, в худшем случае равное количеству прогонов подряд, которое считается малой величиной. Используя эту концепцию, мы можем перемещаться по RLC-представлению по произвольному пути с разумными затратами, не реконструируя всю растровую карту.

Поскольку алгоритм окрестности Мура требует времени, линейного по длине контура, реализация, основанная на этой линейной адресации прогонов, также потребует линейного времени (для ограниченного числа прогонов в строке).