Построение контура

Соседние к данному пикселы можно разделить на н-соседей – имеют общую сторону и к-соседей – касаются углом. Соответственно и контур может быть как к-контуром (8-ми связным), в него входят пикселы области имеющие по крайней мере одного н-соседа, расположенного вне данной области. Так и н-контуром (4-х связным), в него входят пикселы области имеющие любого соседа (н или к), расположенного вне данной области.

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

3
	P

Для данной фигуры (начиная с пиксела с 2-ой штриховкой) это будет (0,0,0,7,5,5,4,4,4,2,2,1). Это потребует 12*3=48 бит.

Если применять дифференциальные коды, то можно немного сократить размеры памяти для хранения контура. Дифференциальные - это не само направление, а его отличие от предыдущего (начальное направление можно взять постоянным, например, 0-ое). Это тоже 8 кодов 0,+1,-1,+2,-2,+3,-3,+4). За счет того, что обычно направление сохраняется или изменяется несильно, то имеет смысл использовать коды с переменной длиной 0 – 0, +1 – 100, -1 – 101,+2 – 1100,-2 – 1101,+3 – 1110,-3 – 11110,+4 – 11111.

Построение скелета (остова) области

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

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

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

Для правильной обработки таких случаев следует проверять еще две комбинации пикселов.