9.7. ПРЕОБРАЗОВАНИЕ ДВУХУРОВНЕВЫХ ИЗОБРАЖЕНИЙ В ШТРИХОВЫЕ
Процедура прореживания в чистом виде не дает полного решения задачи преобразования изображений класса 2 в изображение класса 3. Остовы, получаемые с помощью алгоритмов 9.1 и 9.3, представляют собой все еще двухуровневые изображения, хотя и содержащие очень немного зачерненных пикселов. Такое изображение эквивалентно графу, вершинами которого служат зачерненные пикселы, а ребра связывают пикселы с их соседями. Этот граф можно следующим образом преобразовать в некоторый другой граф, не содержащий вершины второго порядка.
Обход графа двухуровневого изображения, содержащего его остов производится с помощью алгоритма 6.2 или аналогичного ему. Помимо стека 5 предусматривается буферная память Т, в которую заносятся координаты всех пикселов, соответствующих вершинам второго порядка. Если порядок некоторой вершины отличается от двух, координаты соответствующей точки выводятся и проверяется наличие точек в буферной памяти. Если какие-либо точки в ней обнаруживаются, выводится их описание, а также координаты точки, соответствующей последней просмотренной вершины, порядок которой отличается от двух. Мы проиллюстрируем порядок выполнения этого процесса на примере.
На рис. 9.8 представлен остов изображения, приведенного на рис. 9.6. Для обхода соответствующего графа необходимо в каждой связной компоненте задать некоторую исходную вершину. Такие вершины можно найти в процессе просмотра двухуровневого изображения, содержащего остовные пикселы, осуществляемого сверху вниз слева направо. В общем случае эти вершины имеют второй порядок, что, в частности, имеет место и для обеих компонент изображения рис. 9.8. В процессе обхода графа информация может не выводиться до тех пор, пока не будет обнаружена некоторая вершина, порядок которой отличается от двух. Если такую вершину обнаружить не удается, то соответствующий граф представляет собой просто некоторую цепь и при выводе можно ограничиться этой информацией. Допустим, что в данном примере для первой связной компоненты в качестве начальной точки выбрана вершина d, а для второй — вершина а. В процессе обхода, начатого в вершине d, обнаруживается, что С является следующей вершиной порядка, отличного от двух. В таком случае выводится пара вершин d и С, а также описание расположенных между ними пикселов, хранящееся в буферной памяти Т. Для представления этого описания существуют различные способы.
Юдин из них предусматривает выдачу маршрута, образованного этими пикселами и представленного в цепном коде. В данном случае это описание имеет вид 536545242545342342332912; показатели степени обозначают повторение символов. Другой способ предусматривает выдачу описаний прямых и дуг окружностей. В данном случае такое описание будет включать радиус и центр некоторой дуги окружности с концевыми точками 
и 3 и прямую, соединяющую точку 3 с точкой С.
Рис. 9.8. Представление остова в виде некоторого графа вершины второго порядка обозначены символом 
или числом, вершины первого порядка — строчными и вершины третьего порядка — прописными буквами
Для получения подобного описания приходится обращаться к методам вычерчивания кривой по точкам и, в частности, к методам кусочной аппроксимации, рассмотренным в гл. 12. В этом случае пиксел 2 выбирается с помощью алгоритма типа алгоритма 12.1.
Осмотр верхнего контура начинается с пиксела С, в котором он и заканчивается Соответствующее описание, представленное кривыми, включает радиус и центр дуги, соединяющей точки С и 2, и прямую проведенную между ними.
При обработке второй компоненты первое описание будет содержать пару пикселов а и В и соединяющее их ребро, представленное прямой. В процессе продвижения осмотра от точки В пер вой выделенной точкой является Е, а затем — точка 
Для продолжения обхода необходимо извлечь какую-либо вершину из стека 
в данном случае таковой является правый нижний сосед вершины Е. Далее следует ребро, соединяющее вершины Е и 
и т. д. Результаты такого обхода сведены в табл. 9.1.
Таблица 9.1 (см. скан) Описание изображения, приведенного на рис. 9.8
Последователь ность появления ребер определяется порядком осмотра окрестности каждого пиксела. В данном случае просмотр велся в порядке возрастания номеров направлений, обозначенных на рис. 7.4. В описание ребер введена также информация, характеризующая их ориентацию. Для ее получения можно воспользоваться методами построения кривых по точкам, излагаемыми в следующих трех главах.
Мы не приводим в явном виде алгоритм построения указанных описаний, поскольку обход графа может осуществляться различными способами, выбор одного из которых определяется характером решаемой задачи.
