Растровое изображение изображение как двумерный массив данных. Пару слов о распознавании образов Цифровое распознавание геометрических фигур на изображении

Постановка задачи определяется целью и возможностями ее реализации.

Цель. Разработать программу классификации деталей прямоугольной формы на качественные и бракованные.

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

Моделирование с применением компьютера подразумевает переход от реального объекта (мира) к кодированному описанию его свойств при помощи данных и операций над ними. Такой переход, как правило, выполняется в несколько этапов:

Абстракция – выбор наиболее существенных признаков объекта с точки зрения поставленной задачи.

Необходимо провести исследования, которые позволяют от объекта моделирования перейти к субъекту моделирования отбросив все лишнее в соответствии с целью в поставленной задаче

Чем отличается прямоугольник от других четырёхугольников?

• Равенство противоположных сторон.
• Параллельность противоположных сторон.
• Равенство диагоналей.
• Все углы прямые.

Какой минимум признаков нужен для однозначного решения задачи?

• Равенство 2-х противоположных сторон + равенство диагоналей.
• Параллельность 2-х противоположных сторон + равенство диагоналей.
• Три угла прямые.

Итак, благодаря абстракции мы получили словесную информационную модель. Но, она еще пока непонятна для компьютера. Он понимает математическую модель, представленную в виде алгоритма и реализованную программно .

Методика реализации задачи .

Чертёж качественной детали (прямоугольника) или бракованной детали (четырехугольника) выполняется из отрезков (команда LINE) в графической системе AutoCAD и экспортируется в . Программа kntrs.lsp () считывает из DXF-файла данные об отрезках (координаты вершин) и записывает их в текстовый файл vrtks.txt в круговом порядке обхода вершин.

Текстовый файл vrtks.txt можно создать вручную, снимая координаты вершин непосредственно с чертежа.

Разработанная программа rct.lsp должна считывать данные из файла vrtks.txt, анализировать их и выводить в файл result.txt запись о соответствии детали требованиям (прямоугольник или нет).

Формализация признаков

Равенство длин отрезков (сторон или диагоналей): Длина каждого отрезка определяется как гипотенуза прямоугольного прямоугольника (по теореме Пифагора) через разницу координат отрезков:

(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))

Параллельность прямых: K2= K1 , где К – угловой коэффициент прямой К=(Y2-Y1)/(X2-X1)

Как формализовать понятие «Прямой угол»? В рамках поставленной задачи наличие «Прямого угла» можно определить по признаку перпендикулярности отрезков: K2= -1/K1 , где К – угловой коэффициент прямой. К=(Y-Y0)/(X-X0) .

Отображение модели в компьютере

Любая информация в конечном итоге отображается в компьютере с помощью двоичных чисел (кодов) во внутримашинную модель. Ранее кодирование осуществлялось программистом. Сейчас основная часть программ создаётся на алгоритмических языках.

Когда мы смотрим на двумерное изображение какой-либо трехмерной сцены (на картине, фотографии, экране монитора), нам кажется, что там непосредственно присутствуют все те предметы, которые мы могли бы увидеть, если бы непосредственно наблюдали ту же сцену в жизни. Между тем, все, что нам на самом деле дано в двумерном изображении, это видимое поле , представляющее собой лишь некоторуюфункцию распределения яркости илицвета на двумерной плоскости:f (x , y ) , гдеx иy – декартовы координаты, описывающие плоскость изображения.

Более того, если приблизиться вплотную к экрану компьютерного монитора, можно увидеть, что изображение на экране на самом деле не гладкое и непрерывное, а представляет собой дискретную «мозаику», состоящую из отдельных цветных прямоугольников, расположенных в виде регулярной прямоугольной матрицы. Это и есть цифровое изображение. С математической точки зрения цифровое изображение представляет собой двумерную матрицуIm размера (DimXDimY), гдеx– целое число от 0 доDimX– 1, описывающее номер элемента в строке матрицы,y– целое число от 0 доDimY– 1, описывающее номер строки матрицы, в которой расположен данный элемент. При этом сам элемент цифрового изображения (ячейка прямоугольной матрицы) носит названиепиксель (pixel,pictureelement). В простейшем случае каждый пиксельIm имеет скалярное целочисленное значение, пропорциональное значению функции распределения яркостиf (x , y ) в данной точке плоскости.

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

@Рис. 1.1.1 Цифровое изображение как двумерная матрица интенсивностей

Начиная изучать машинное зрение, необходимо четко представлять себе, что в компьютере в качестве цифрового изображения хранится только и исключительно двумерный массив чисел того или иного формата. Любые другие данные, которые мы хотели бы из изображения извлечь (фигуры, линии, объекты, размеры, содержание изображенного текста и т.д. и т.п.) – могут быть получены лишь в результате применения ряда процедур обработки и анализа изображения, которые мы должны либо сами запрограммировать, либо использовать готовые процедуры, имеющиеся в известных пакетах программ для анализа изображений. При этом для решения простых задач компьютерного зрения готовые средства наверняка найдутся в стандартных библиотеках процедур обработки изображений, для решения задач посложнее необходимо будет скомбинировать те или иные готовые процедуры, а для многих вполне «обыденных» задач, которые «биологическое» зрение человека, казалось бы, решает легко и играючи, компьютерное машинное зрение до сих пор решений не имеет и все еще продолжает их искать. Ведь используя свое естественное зрение, человек легко ориентируется в любой обстановке, узнает предметы, выбирает путь, управляет автомобилем и многое, многое другое. Почему же компьютер, получающий изображение от видеокамеры, всего этого не может? Может быть, дело в строении человеческого глаза?

На самом деле человеческий глаз, как и видеокамера, всего лишь формирует «видимое поле», аналогичное цифровому изображению. При этом оптическая система, состоящая из зрачка и хрусталика, проецирует двумерное изображение на сетчатку глаза, где фоточувствительные клетки («палочки» и «колбочки») преобразуют полученное изображение в нервные импульсы. И только после этого сложный механизм обработки полученной информации, функционирующий в соответствующем отделе нашего мозга, интерпретирует эти импульсы как понятное нам изображение видимой сцены. Таким образом, и у человека функцию «видения» выполняет не один только глаз, но система «глаз + мозг» («сенсор + компьютер»). Именно встроенные в мозг алгоритмы обработки информации позволяют человеку понимать то, что он видит. Роль этих встроенных алгоритмов можно пояснить на следующем примере.

Когда в середине XXвека хирурги-офтальмологи научились делать операции на хрусталике глаза, у многих слепых от рождения людей появилась техническая возможность прозреть. То есть после такой операции у человека, доселе слепого (свет просто не проходил через хрусталик), изображение на сетчатке начинало формироваться и соответствующие сигналы начинали поступать в мозг совершенно так же, как это происходит у здоровых людей. К сожалению, в данном случае «увидеть свет» не означало «начать видеть». Как показала дальнейшая история, большинство «технически прозревших» взрослых пациентов так никогда и не смогли достичь в области зрения более существенных результатов, чем распознавание простых геометрических фигур – и даже это требовало от них серьезных сознательных усилий. Узнавание же людей по лицам и ориентирование в пространстве так и остались для них непосильными задачами. Дело в том, что те встроенные механизмы «автоматического» зрительного анализа, которые развиваются у людей в раннем детстве, у этих пациентов не были своевременно развиты, и они оказались в положении компьютера, имеющего устройство для ввода изображения, но не имеющего необходимого программного обеспечения для его анализа.

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

@Рис. 1.1.2. Цифровое изображение как псевдо-трехмерный рельеф

Теперь представьте себе, что вы должны, не глядя на изображение, ощупать соответствующий ему «рельеф» и постараться определить, что именно этот «рельеф» изображает – дом, собаку или человеческий глаз? Как показывают эксперименты, средний человек не в состоянии справиться с подобной задачей. Даже распознавание простейших геометрических фигур в подобном «рельефном» представлении будет связано со значительными усилиями и потребует сознательной выработки специального навыка, стратегии и алгоритмов ощупывания. Такова, несмотря на кажущуюся простоту объекта «цифровое изображение», истинная сложность задач компьютерного и машинного зрения.

УДК 004932:621.396

Т.М. ВЛАСОВА, В.Г. КАЛМЫКОВ

АЛГОРИТМ И ПРОГРАММА РАСПОЗНАВАНИЯ КОНТУРОВ ИЗОБРАЖЕНИЙ КАК ПОСЛЕДОВАТЕЛЬНОСТИ ОТРЕЗКОВ ЦИФРОВЫХ ПРЯМЫХ

Abstract: In the given work the algorithm of the recognition of the digital direct line segment in contours of the binary images and the software implementation of the algorithm is considered. Utilization of this algorithm to process the images will result to more natural and economical description in comparison with known ways of the description of the images. The considered algorithm and the software implementation can be used also for the description of contours when processing the half-tone and colour images.

Key words: image, contour, digital straight segments, algorithm, program.

Анотація: У даній роботі наводиться алгоритм розпізнавання відрізків цифрових прямих у контурах бінарних зображень, а також програмна реалізація алгоритму. Використання цього алгоритму для оброблення зображень призведе до того, що опис зображень буде більш натуральним та економним порівняно з відомими засобами кодування зображень. Запропоновані алгоритм і програмна реалізація можуть застосовуватись для кодування контурів при обробленні напівтонових та кольорових зображень. Ключові слова: зображення, контур, відрізки цифрових прямих, алгоритм, програма.

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

1. Введение

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

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

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

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

В настоящей работе рассматривается распознавание контура бинарного изображения как последовательности отрезков цифровых прямых без потери информации.

2. Контур как последовательность отрезков цифровых прямых

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

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

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

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

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

пикселы являются двумерными элементами этого клеточного комплекса. Помимо пикселов, имеются крэки и точки. Крэки - это

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

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

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

клеточного комплекса дает много преимуществ. В частности, граница области становится тонкой кривой с нулевой площадью.

На рис. 1 приведены пример исходного контура объекта, образованного дугой кривой и отрезком прямой, а также его цифровой эквивалент как последовательность крэков. Пронумерованы точки, принадлежащие крэкам разных направлений. Как и в работах , под Ь -элементом будем понимать связную последовательность крэков одного и того же направления, выходящую из некоторой точки и заканчивающуюся крэком того же или перпендикулярного направления. На рис. 1 приведено одно из возможных разбиений контура на Ь -элементы, которые образованы крэками между точками: (0-2), (2-4), (4-6), (6-8), (8-9), (9-11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25), (25-27), (27-0). Каждый Ь -элемент характеризуется такими параметрами: направлением относительно начальной его точки g (принято g =0 - для направления вверх, 1 - вправо, 2 - вниз, 3 - влево); l - количеством крэков направления g (! = 1,2,...); направлением последнего крэка q относительно направления g предыдущих крэков (q = -1 - последний крэк направлен влево относительно направления g, +1 - вправо, 0 - совпадает с направлением g). Количество крэков l условно будем называть "длиной" Ь -элемента Для Ь -элемента (0-2) g =0, !=3, q =+1. Для Ь -элемента (27-0) g =3, =1, q =0.

Метод выделения отрезков цифровых прямых в контуре использует следующее свойство последовательности Ь -элементов, образующих отрезок. Такая последовательность включает Ь -элементы с одинаковыми значениями g, q; их длины принимают значения!, +1. Причем

чередование Ь -элементов длин!, +1 определяется цепной дробью, получаемой при делении целых чисел п = Ах = |х1 - х2| и т = Ау = |у1 - у2\, где (х1зу1), (х2,у2) - координаты начальной

и конечной точек отрезка: или

Положим для определенности, что п > т. Как следует из формулы (1), l - целая часть от деления п на т - соответствует в отрезке цифровой прямой количеству из l подряд идущих крэков одного направления. Вместе с примыкающим перпендикулярным крэком они образуют Ь -элемент длины!. к1 подряд идущих Ь -элементов длины l и один Ь -элемент длины!+1 (или к1 подряд идущих Ь -элементов длины +1 и один Ь -элемент длины!) образуют К1 -элемент "длины" к1 (по аналогии с "длиной" Ь -элемента). Ь -элемент, отличающийся по длине на 1 от подряд идущих Ь -элементов, будем называть измененным Ь -элементом данного К1 -элемента. Аналогично, к2 подряд идущих К1 -элементов “длины” к1 и один К1-элемент “длины” к1 +1 (или к2 подряд идущих К1 -элементов "длины" к1 +1 и один К1 -элемент “длины” к1) образуют К2-элемент “длины” к1. И так

к + к 2 + к з +... + кг

далее до исчерпания членов цепной дроби. К1 -элемент (вообще К-1 -элемент), отличающийся по длине на 1 от подряд идущих К1 -элементов (Кг-1 -элемент), будем называть измененным К1 -элементом (Кг-1 -элементом) данного К2 -элемента (Кг -элемента). Таким образом, каждому

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

В контуре на рис. 1 могут быть выделены следующие отрезки цифровых прямых: 0-3, 3-9, 910, 10-17, 17-0.

3. Выделение отрезков цифровой прямой в контуре

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

Метод выделения отрезков цифровой прямой состоит в последовательном выполнении следующих действий.

1. Выделение последовательности Ь -элементов в последовательности крэков. Это действие соответствует определению целой части! цепной дроби (1).

2. Выделение последовательности Кг -элементов при г = 1 в последовательности Ь -элементов, причем один из Ь -элементов каждого К1 -элемента должен содержать на 1 крэк больше или меньше других. Это действие соответствует определению к1 -го элемента цепной дроби (1). После его выполнения значение г должно быть увеличено на 1.

3. Выделение последовательности Кг -элементов в последовательности Кг-1 -элементов,

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

4. Пункт 3 повторяется до тех пор, пока из идущих подряд Кг -элементов еще возможно

образовать Км -элемент.

5. Определяют граничные точки между двумя соседними Ь -элементами, которые не входят в один и тот же Кг -элемент. Эти точки являются конечными точками отрезков цифровых прямых, образующих контур.

Рассмотрим алгоритм выделения отрезков прямых в последовательности Ь -элементов

Пусть [Ь5 (/5,gs,qs)}; 5 = 0.1,...,£ - последовательность Ь-элементов, образующих контур; х5,у5- координаты начала э-го Ь-элемента; [ху,у у}; у = ; г = 0,1,...,!; ! < £ - множество

точек излома контура. Точки излома определяют конечные точки отрезков прямых, которые образуют контур. Найти точки излома - значит, определить отрезки прямой, образующие контур.

Каждый рассматриваемый отрезок характеризуется Кг -элементом, а также цепной

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

1. Начальные условия.

Заданы последовательности [Ь5 (/5, gs, qs)} и {х5,у5} .

Необходимо найти координаты точек излома |х;.,у,}.

к0р:= 0, к1р:= 0, к2р:= 0,..., кр:= 0 - рабочие значения элементов цепной дроби.

Примем в качестве начальной точки первого отрезка точку 5 =0; і =0; і =0.

2. Принимают первый Ь -элемент в последовательности началом первого отрезка прямой. Начальная его точка х5,у. Длина /=/0 является также значением первого элемента цепной дроби.

5:=5+1; к1р:=к1р+1.

3. Выполняют проверку для следующего Ь -элемента, образуют ли они вместе с предыдущими К0-элемент.

3.1. Если ((д3 == д3-1) && (д3 == 73-1)&& (4 == /3-1)), то продолжение Кг -элемента к0р:= к0р +1; 5:= 5 + 1; и продолжение отрезка прямой. Переход к п.3.

3.2. Если ((д3 ф д3-1) || (д3 ф 73-1)11 (|/э - /є-1!>1)), то конец отрезка прямой. Переход к п.5.

3.3. Если ((&== 9з+1) && (%== 7з+1)&& ((/з+1== /з+1)1! (/з - 1 == /3+1))), то завершение К0 -элемента; Ї = Ї+1.

4. Проверка продолжения/завершения К(-элемента.

4.1. Если (к == 0), то к ^= к^; кр:= 0; к^1р:= к1+ 1р+1; 5:=5 +1; начало Км -элемента.

Переход к п.3.

4.2. Если ((к іФ 0)&&(к == к^)), то к^1р:= к^1р+1; 5:= 5+1; продолжение Кі+1 -элемента. Переход к п.3.

4.3. Если ((к (Ф 0)&&((к+1== к1р)11(к1-1 == к^))), то Ї := +1; конец Км -элемента.

Переход к п.4.

4.4. Если ((^ф0)&&(|к - к1р|>1)), то конец отрезка прямой переход к п.5.

5. Конец отрезка.

X] = Хз; у = Уз; к1р:= 0, к2р:= 0,., кір:= 0; к:= 0, к2:= 0,., к:= 0.

Если (s < S), то s:= s +1; переход к п. 2.

Иначе - конец последовательности L -элементов. Конец работы алгоритма.

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

4. Программа выделения отрезков цифровой прямой

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

определить невозможно, поскольку переменная t заранее не ограничена. Ограничить величину t

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

Предложенный алгоритм реализован в виде программы LINESEGM, которая входит в состав лабораторного программного комплекса по обработке изображений в среде Visual C++.

В качестве исходной информации программа LINESEGM использует последовательности L -элементов, построенные для каждого из контуров обрабатываемого изображения.

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

Как видно из алгоритма, операции построения Kt -элементов из Kt-l -элементов

одинаковы для всех значений t. Отметим, что начальное значение t =0 и в процессе работы алгоритма увеличивается каждый раз на 1. Специальный класс CKForLn включает методы, соответствующие операциям алгоритма. В процессе работы программы, реализующей алгоритм при каждом увеличении t на 1, создается новый объект, содержащий функции, выполняющие операции алгоритма для каждого значения t.

Учитывая, что на нулевом уровне К0 -элементы образуются не из К -элементов, а из L -

элементов, для реализации алгоритма на нулевом уровне создана специальная модификация класса CKForLn - класс Cmini.

Принцип работы программы заключается в том, что для каждого значения t в программе реализуется объект класса CKForLn t-того уровня, содержащий функции, определяющие параметры Kt -элемента. Исходными параметрами Kt -элемента являются параметры уже

завершенного Kt-l -элемента, параметры которого были определены объектом класса CKForLn t-1

Ого уровня.

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

Реализация объектов в динамическом массиве по мере увеличения t позволяет не накладывать ограничений на размеры изображения. Ограничения на размер изображения определяются только ресурсами используемого компьютера.

При описании работы программы будет использовано понятие завершенного Kt -

элемента. Каждый завершенный Kt -элемент содержит kt Kt-l -элементов и один измененный Kt-l -элемент, который содержит kt-l ±1 Kt-2 -элементов, в отличие от незавершенного Kt -элемента, который не содержит незавершенного Kt -элемента.

Класс CKForLn включает следующие методы.

1. Метод DK(), (define K-element) - определить К -элемент.

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

2. Метод VK§, (verify K-element) - проверить идентичность рассматриваемого К -элемента с К-элементом того же уровня, определенным предварительно функцией метода DK() .

3. Метод DEO, (define the end of K-element) - определить завершение К -элемента, то есть при определении Kt -элемента найти его измененный Kt-1 -элемент. Функция метода DE() уровня t-1 вызывается функцией метода DK() уровня t.

4. Метод VE(),(verify the end of К -element) - проверить идентичность завершения рассматриваемого К -элемента измененным К -элементом, определенным предварительно функцией метода DE().

Класс Cmini включает такие же методы, отличающиеся от методов класса CKForLn тем, что методы класса Cmini работают с L -элементами и определяют или проверяют К0 -элементы.

Методы класса Cmini

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

Функция метода DK() класса Cmini сравнивает параметры каждого следующего L -элемента с параметрами начального L -элемента до тех пор, пока они совпадают. В случае несовпадения параметров функция DK() проверяет, завершен ли К0 -элемент и заканчивает

работу. Завершенным считается К0 -элемент, заканчивающийся измененным L -элементом, таким, длина которого отличается от других L -элементов К0 -элемента на 1 (операция 3.1 для начала отрезка - t = 0).

Функция метода VK() проверяет, совпадают ли параметры следующих k0 L -элементов с параметрами L -элементов К0 -элемента, предварительно определенного функцией метода DK()

того же уровня. В случае совпадения параметров текущего К0 -элемента с предварительно

определенным функция VK() формирует признак продолжения отрезка и завершает работу (операция 3.1 для продолжения отрезка - t > 0).

В противном случае функция VK() формирует признак завершения отрезка и завершает

Функция метода DE() сравнивает параметры текущего Kci-элемента с параметрами К0 -элемента, предварительно определенного функцией DK(), чтобы определить, является ли текущий К0 -элемент измененным. При равенстве других параметров количество L -элементов к0

измененного К0 -элемента сравнительно с К0 -элементом, предварительно определенным

функцией DK(), должно отличаться на 1 (операция 3.2, 3.3 для определения завершения

начального К0 -элемента отрезка - t = 0). Результат - параметры измененного К0 -элемента

используются в методе VE() класса Cmini.

Функция метода VE() сравнивает параметры текущего К0 -элемента с параметрами предварительно определенного функцией DE() измененного К0 -элемента, чтобы определить,

совпадают ли они (операция 3.2, 3.3 для продолжения отрезка - t > 0). Результат - признак совпадения или несовпадения - используется в методе VК() класса CKForLn.

Методы класса CKForLn

Методы используют в качестве исходных данных параметры К-элементов, построенные для низшего уровня. То есть, для определения параметров Kt -элемента используются параметры

уже построенных Kt-l -элементов.

Функция метода DK() уровня t класса CKForLn при определении параметров ^-элемента вызывает функцию VK() уровня t-1 класса CKForLn, которая проверяет, следует ли за уже определенным Kt-l -элементом Kt-l -элемент с такими же параметрами. Если да, вызов функции VK() повторяется. При этом происходит подсчет количества повторений, то есть определяется параметр kt .

В противном случае функция DK() уровня t вызывает функцию DE() уровня t-1 для определения измененного Kt-l -элемента и заканчивает работу. По окончании работы функция DK() уровня t класса CKForLn определяет параметры и формирует признаки завершенного или незавершенного Kt -элемента (операция 4.1, 4.2 при текущем максимальном значении t).

Функция метода VK() уровня t класса CKForLn проверяет, совпадают ли параметры следующих kt Kt -элементов с параметрами Kt -элемента, предварительно определенного

функцией метода DK() того же уровня. В случае совпадения параметров текущего Kt -элемента с

предварительно определенным функцией DK() Kt -элементом того же уровня, функция VK()

формирует признак продолжения отрезка и завершает работу.

В противном случае функция VK() формирует признак завершения отрезка и завершает работу (операция 4.1,4.2 при текущем значении t, меньшем максимального).

Kt -элементФункция метода DE0уровня t класса CKForLn при определении параметров Kt -элемента сравнивает параметры текущего Kt -элемента с параметрами Kt -элемента, предварительно определенного функцией DK(), чтобы определить, является ли текущий Kt -элемент измененным. При равенстве других параметров их значения kt-1 должны отличаться на 1. В случае выполнения этого условия функция DE() формирует признак измененного Kt -элемента и

завершает работу (операция 4.3, 4.4 при текущем максимальном значении t).

Функция метода VE() уровня t класса CKForLn сравнивает параметры текущего Kt -элемента с параметрами предварительно выделенного функцией DE() измененного Kt -элемента, чтобы определить, совпадают ли значения их параметров.

В случае совпадения значений параметров текущего Kt -элемента с предварительно

определенным функцией DK() того же уровня, функция VK() формирует признак совпадения значений параметров и завершает работу (операция 4.3,4.4 при текущем значении t, меньшем максимального).

Временная диаграмма (рис. 2) иллюстрирует работу программы LINESEGM на примере распознавания отрезка прямой. В нижней части рисунка изображена часть цифровой линии, состоящая из L -элементов одних и тех же основного и вспомогательного направлений и различных длин.

На шаге 0 создан объект класса Стіпі, который определяет параметры К0 -элемента.

На шаге 10 завершено определение параметров К0-элемента и создается объект 1 класса СКРогЬп, который использует функции ранее созданного объекта для определения параметров К1-элемента. На шаге 19 завершено определение параметров К1 -элемента и создается объект 2 класса СКРогЬп, который использует функции ранее созданных объектов для определения параметров К2 -элемента. На шаге 49 завершено определение параметров К2 -элемента и создается объект 3 класса СКРогЬп, который использует функции ранее созданных объектов для определения параметров К3-элемента. На шаге 79 выполняется

условие завершения отрезка. Подробно работа программы описана в приложении.

На участке 0-6 два Ь -элемента образуют незавершенный К0 -элемент. Очевидно, что Ь -

элемент 3-6 длины 3 завершает отрезок прямой, так как Ь -элемент 6-7 длины 1 не может быть его продолжением. Таким образом, Ь -элемент 6-7 является началом отрезка цифровой прямой.

На рис. 3 представлен пример работы программы. Контур бинарного изображения фигурной стрелки разделен квадратиками на отрезки прямых. Результат работы программы -последовательность отрезков прямых - был использован для выделения дуг цифровых кривых . Большие квадратики показывают границы дуг цифровых кривых.

Работа программы проверена на значительном количестве (более 2000) примеров и используется при исследовании структурного анализа полутоновых изображений.

5. Работа программы распознавания отрезков прямых

Рассмотрим работу программы иЫЕБЕСМ на примере рис. 4. В нижней части рисунка изображена часть цифровой линии, состоящая из Ь -элементов одних и тех же основного и вспомогательного направлений и различных длин. На участке 0-6 два Ь -элемента образуют незавершенный К0-

Рис. 3. Пример работы программы структурного анализа контура - сегментация контура отрезками цифровых прямых

элемент. Очевидно, что Ь -элемент 3-6 длины 3 завершает отрезок прямой, так как Ь -элемент 6-7 длины 1 не может быть его продолжением. Таким образом, Ь -элемент 6-7 является началом отрезка цифровой прямой.

Работу программы по определению очередного отрезка прямой начинает функция ОК() нулевого уровня, которая определяет завершенный К0 -элемент 6-10, состоящий из Ь -элементов

длин 1,1,2; к0=2. Этот К0 -элемент является начальным для К1-элемента. Программа образовывает объект первого уровня и передает управление функции ОК() этого объекта. Функция ОК() уровня 1 вызывает функцию VKQ уровня 0. Функция VKQ сравнивает параметры Ь -элементов К0-элемента 6-10 с последующими Ь-элементами и подтверждает наличие К0 -элемента 10-14,

идентичного К0 -элементу 6-10. Продолжая работу, функция VKQ обнаруживает, что следующие Ь -элементы не образуют такого же К0 -элемента, завершает работу и передает управление функции ОК() уровня 1. Функция ОК() уровня 1 вызывает функцию ОЕ() уровня 0. Эта последняя, начиная с Ь -элемента 6-7, определяет наличие измененного К0 -элемента 14-19, состоящего из Ь -элементов длин 1,1,1,2; к0=3, завершает работу и передает управление функции ОК() уровня 1. Эта функция определяет наличие завершенного К1-элемента 6-19, состоящего из двух К0 -

элементов 1,1,2, (к1=2) и одного измененного 1,1,1,2 (к0=3). Программа образовывает объект второго уровня и передает управление функции ОК() этого объекта. Функция ОК() уровня 2 вызывает функцию VKQ уровня 1, которая, в свою очередь, вызывает функцию VKQ уровня 0. Функция VKQ сравнивает параметры Ь -элементов К0 -элемента 6-10 с последующими Ь -

элементами и подтверждает наличие К0 -элементов 19-23, 23-27, идентичных К0-элементу 6-10, то есть столько же, сколько таких К0 -элементов содержится в К1-элементе 6-19. Далее функция VKQ уровня 0 возвращает управление с признаком продолжения отрезка функции VKQ уровня 1. Функция VKQ вызывает функцию VE0 уровня 0, которая определяет наличие измененного К0 -

элемента 27-32, идентичного К0 -элементу 14-19. Таким образом, определен К1-элемент 19-32,

идентичный К1-элементу 6-19. Далее функция VKQ уровня 1 не определяет очередной К1-элемент, идентичный К1-элементу 6-19, из-за того, что функция VE0 уровня 0 не определяет измененный К1-элемент, идентичный К1-элементу 6-19, начиная с Ь -элемента 40-41, и возвращает управление функции ОК() уровня 2. Функция ОК() уровня 2 вызывает функцию ОЕ() уровня 1, которая определяет наличие измененного К1-элемента 32-49, состоящего из К0 -элементов 32-36, 36-40,

40-44, 44-49. Далее определяется К2-элемент 6-49, образуется объект уровня 3, определяется измененный К2-элемент 49-79. Эти два К2-элемента образуют К3-элемент 6-79. Этим построение отрезка завершается, поскольку следующие Ь -элементы 79-81 и 81-83 не образуют К0 -элемент,

идентичный К0 -элементу 6-10, и функция VKQ уровня 0 не формирует признак продолжения

отрезка. В последовательности Ь -элементов выделен отрезок цифровой прямой 6-79. Программа начинает определение следующего отрезка, начиная с Ь -элемента 80-82.

б. Выводы

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

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

3. На основе предложенного алгоритма и его программной реализации получено теоретическое решение и проведены эксперименты по распознаванию дуг цифровых кривых и сегментации контура бинарных изображений на отрезке цифровых прямых и дуги цифровых кривых.

СПИСОК ЛИТЕРАТУРЫ

1. Kovalevsky V.A. Applications of Digital Straight Segments to Economical Image Encoding, In Proceedings of the 7th International Workshop, DGCI"97, Montpellier. - France, 1997. - December 3-5. - P. 51-62.

2. Калмыков В.Г. Структурный метод описания и распознавания отрезков цифровых прямых в контурах бинарных изображений // Штучний інтелект. - 2002. - № 4. - C. 450-457.

3. Калмыков В.Г., Вишневский В.В. Анализ контуров объектов в бинарных изображениях // Математические машины и системы. - 1997. - № 2. - С. 68 - 71.

4. Калмиков В.Г. Дуга цифрової кривої - визначення і застосування // Оброблення сигналів і зображень та розпізнавання образів. Праці сьомої Всеукраїнської міжнародної конференції. - Київ. - 2004. - 11 - 15 жовтень.