Математическая постановка задачи

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

Каждой единице изображения в массиве соответствует элемент массива сегментов, значение которого расшифровывается следующим образом:

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

- если значение равно нулю, то это означает, что данному элементу не соответствует ни одна из сегментов линий и, следовательно, соответствующая точка в массиве точек не является каким-либо сегментом линией;

- если значение больше нуля, то оно представляет собой номер сегмента линии, которому соответствует данная точка.

Данные утверждения можно представить в виде формул:

(3.1)

где (x,y) – координаты рассматриваемой точки;

M и N – ширина и высота изображения;

C – массив сегментов, размерность MxN;

n – номер обрабатываемого сегмента.

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

Отдельные сегменты линий

Рис. 3.1

Данный тип сегментов не содержит узлов и для его кодирования достаточно указания одной начальной точки.

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

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

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

Сегмент линии, содержащий начальную и узловую точки

Рис. 3.2

Сегмент, определяемый двумя узловыми точками

Рис. 3.3

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