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

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

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

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

 

Специальные требования к техническому обеспечению

Требования к техническому обеспечению для решения задачи «Кодирование сегментов» полностью совпадают с требованиями к комплексу технических средств, предъявленными при разработке подсистемы «Линейная сегментация» (см. п. 1.3.1).

Реализация задачи возможна при наличии набора следующих технических средств:

- персональный компьютер IBM PC с процессором не ниже Pentium I;

-  клавиатура;

-  монитор;

-  жесткий диск с объемом свободного пространства не менее 50 МБ;

-  оперативная память объемом не менее 128 МБ.

Работа программы возможна только на ЭВМ, которые поддерживают 32-разрядные операционные системы семейства Windows, такие как Windows 95, Windows NT или выше. Как указано выше, работа может вестись на ЭВМ с процессором не ниже Intel Pentium. Но желательно использовать ЭВМ с процессором не ниже класса Intel Pentium II, который работает более эффективно.

Описание алгоритма «Обработка и кодирование сегментов»

 

Назначение и характеристика

Алгоритм «Обработка и кодирование сегментов» предназначен для поиска выделенных сегментов линий, их идентификации, поиска узловых точек, формирования кодов, содержащих координаты данных сегментов для последующей обработки их в подсистеме цепного кодирования или использования в других подсистемах. Для работы алгоритма необходимо наличие информации об узлах и сегментах изображения, полученных в результате работы алгоритмов «Поиск узлов» и «Поиск сегментов», описание которых приведено в пунктах 2.2 и 3.2 соответственно.

 

Используемая информация

При работе данного алгоритма используется следующая информация:

- значения массива точек исходного графического изображения;

- значения массива сегментов, содержащего описания принадлежности точки тому или иному сегменту;

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

 

Результаты решения

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

 

Алгоритм решения

 

Алгоритм решения составлен с учетом математического описания, приведенного в пункте 4.1.4. Алгоритм представляется в текстовом виде следующим образом:

1. Начало;

2. Инициализация массивов и переменных;

3. Если поиск узлов выполнен, то переход к п.5, иначе к п.4;

4. AnalyzeNode, переход к п.3;

5. Если поиск сегментов выполнен, то переход к п.7, иначе к п.6;

6. AnalyzeSeg, переход к п.5;

7. i=0; j=0; lnum=0; lineno=0;

8. Если j>=N, то переход к п.15;

9. Если i>=M, то переход к п.14;

10. Если (apix[i][j]=1)и(apix1[i][j]<0)и((NeigCount(i,j)=1)или(NeigCount(i,j)=2)), то переход к п.11, иначе к п.13;

11. lnum=lnum+1; lineno=lineno+1;

12. GetLineVect(i,j,lineno);

13. i=i+1; переход к п.9;

14. i=0; j=j+1; переход к п.8;

15. Конец.

 

Требования к контрольному примеру

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

- отдельно расположенные сегменты, начало, и конец которых являются обычными точками - такие сегменты представляют собой отдельные линии;

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

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

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