Пару слов о распознавании образов. Растровое изображение изображение как двумерный массив данных Пример цифрового распознавания треугольника
Когда мы смотрим на двумерное изображение какой-либо трехмерной сцены (на картине, фотографии, экране монитора), нам кажется, что там непосредственно присутствуют все те предметы, которые мы могли бы увидеть, если бы непосредственно наблюдали ту же сцену в жизни. Между тем, все, что нам на самом деле дано в двумерном изображении, это видимое поле , представляющее собой лишь некоторуюфункцию распределения яркости илицвета на двумерной плоскости:f (x , y ) , гдеx иy – декартовы координаты, описывающие плоскость изображения.
Более того, если приблизиться вплотную к экрану компьютерного монитора, можно увидеть, что изображение на экране на самом деле не гладкое и непрерывное, а представляет собой дискретную «мозаику», состоящую из отдельных цветных прямоугольников, расположенных в виде регулярной прямоугольной матрицы. Это и есть цифровое изображение. С математической точки зрения цифровое изображение представляет собой двумерную матрицуIm размера (DimXDimY), гдеx– целое число от 0 доDimX– 1, описывающее номер элемента в строке матрицы,y– целое число от 0 доDimY– 1, описывающее номер строки матрицы, в которой расположен данный элемент. При этом сам элемент цифрового изображения (ячейка прямоугольной матрицы) носит названиепиксель (pixel,pictureelement). В простейшем случае каждый пиксельIm имеет скалярное целочисленное значение, пропорциональное значению функции распределения яркостиf (x , y ) в данной точке плоскости.
На рис. 1.1.1 слева показано изображение женского лица, представленное как изображение, а справа показан увеличенный фрагмент изображения того же лица (правый глаз), где для каждого элемента изображения указано соответствующее числовое значение пикселя. Светлым элементам изображения соответствуют бо льшие значения матрицы, темным – меньшие значения. Никакой другой информации цифровое изображение не содержит.
@Рис. 1.1.1 Цифровое изображение как двумерная матрица интенсивностей
Начиная изучать машинное зрение, необходимо четко представлять себе, что в компьютере в качестве цифрового изображения хранится только и исключительно двумерный массив чисел того или иного формата. Любые другие данные, которые мы хотели бы из изображения извлечь (фигуры, линии, объекты, размеры, содержание изображенного текста и т.д. и т.п.) – могут быть получены лишь в результате применения ряда процедур обработки и анализа изображения, которые мы должны либо сами запрограммировать, либо использовать готовые процедуры, имеющиеся в известных пакетах программ для анализа изображений. При этом для решения простых задач компьютерного зрения готовые средства наверняка найдутся в стандартных библиотеках процедур обработки изображений, для решения задач посложнее необходимо будет скомбинировать те или иные готовые процедуры, а для многих вполне «обыденных» задач, которые «биологическое» зрение человека, казалось бы, решает легко и играючи, компьютерное машинное зрение до сих пор решений не имеет и все еще продолжает их искать. Ведь используя свое естественное зрение, человек легко ориентируется в любой обстановке, узнает предметы, выбирает путь, управляет автомобилем и многое, многое другое. Почему же компьютер, получающий изображение от видеокамеры, всего этого не может? Может быть, дело в строении человеческого глаза?
На самом деле человеческий глаз, как и видеокамера, всего лишь формирует «видимое поле», аналогичное цифровому изображению. При этом оптическая система, состоящая из зрачка и хрусталика, проецирует двумерное изображение на сетчатку глаза, где фоточувствительные клетки («палочки» и «колбочки») преобразуют полученное изображение в нервные импульсы. И только после этого сложный механизм обработки полученной информации, функционирующий в соответствующем отделе нашего мозга, интерпретирует эти импульсы как понятное нам изображение видимой сцены. Таким образом, и у человека функцию «видения» выполняет не один только глаз, но система «глаз + мозг» («сенсор + компьютер»). Именно встроенные в мозг алгоритмы обработки информации позволяют человеку понимать то, что он видит. Роль этих встроенных алгоритмов можно пояснить на следующем примере.
Когда в середине XXвека хирурги-офтальмологи научились делать операции на хрусталике глаза, у многих слепых от рождения людей появилась техническая возможность прозреть. То есть после такой операции у человека, доселе слепого (свет просто не проходил через хрусталик), изображение на сетчатке начинало формироваться и соответствующие сигналы начинали поступать в мозг совершенно так же, как это происходит у здоровых людей. К сожалению, в данном случае «увидеть свет» не означало «начать видеть». Как показала дальнейшая история, большинство «технически прозревших» взрослых пациентов так никогда и не смогли достичь в области зрения более существенных результатов, чем распознавание простых геометрических фигур – и даже это требовало от них серьезных сознательных усилий. Узнавание же людей по лицам и ориентирование в пространстве так и остались для них непосильными задачами. Дело в том, что те встроенные механизмы «автоматического» зрительного анализа, которые развиваются у людей в раннем детстве, у этих пациентов не были своевременно развиты, и они оказались в положении компьютера, имеющего устройство для ввода изображения, но не имеющего необходимого программного обеспечения для его анализа.
Для того чтобы окончательно убедиться в сложности стоящей перед нами задачи анализа изображения, представляющего собой двумерный массив числовых данных, попробуем поставить себя на место компьютерной программы, имеющей дело с абстрактными числами. Для этого мысленно изменим модальность восприятия изображения – переведем его из визуальной области в тактильную. Представим двумерный массив значений интенсивности как шахматную доску, размер которой равен размеру изображения (DimXDimY), а в центр каждой клетки воткнут столбик, высота которого пропорциональна значению соответствующего пикселя изображения. Иными словами, рассмотрим двумерное изображение как некую условную трехмерную поверхность. На рис. 1.1.2 слева фрагмент женского лица показан как изображение, а справа изображен как псевдотрехмерный рельеф.
@Рис. 1.1.2. Цифровое изображение как псевдо-трехмерный рельеф
Теперь представьте себе, что вы должны, не глядя на изображение, ощупать соответствующий ему «рельеф» и постараться определить, что именно этот «рельеф» изображает – дом, собаку или человеческий глаз? Как показывают эксперименты, средний человек не в состоянии справиться с подобной задачей. Даже распознавание простейших геометрических фигур в подобном «рельефном» представлении будет связано со значительными усилиями и потребует сознательной выработки специального навыка, стратегии и алгоритмов ощупывания. Такова, несмотря на кажущуюся простоту объекта «цифровое изображение», истинная сложность задач компьютерного и машинного зрения.
Давно хотел написать общую статью, содержащую в себе самые основы Image Recognition, некий гайд по базовым методам, рассказывающий, когда их применять, какие задачи они решают, что возможно сделать вечером на коленке, а о чём лучше и не думать, не имея команды человек в 20.
Какие-то статьи по Optical Recognition я пишу давненько, так что пару раз в месяц мне пишут различные люди с вопросами по этой тематике. Иногда создаётся ощущение, что живёшь с ними в разных мирах. С одной стороны понимаешь, что человек скорее всего профессионал в смежной теме, но в методах оптического распознавания знает очень мало. И самое обидное, что он пытается применить метод из близрасположенной области знаний, который логичен, но в Image Recognition полностью не работает, но не понимает этого и сильно обижается, если ему начать рассказывать что-нибудь с самых основ. А учитывая, что рассказывать с основ - много времени, которого часто нет, становится всё ещё печальнее.
Эта статья задумана для того, чтобы человек, который никогда не занимался методами распознавания изображений, смог в течении 10-15 минут создать у себя в голове некую базовую картину мира, соответствующую тематике, и понять в какую сторону ему копать. Многие методы, которые тут описаны, применимы к радиолокации и аудио-обработке.
Начну с пары принципов, которые мы всегда начинаем рассказывать потенциальному заказчику, или человеку, который хочет начать заниматься Optical Recognition:
- При решении задачи всегда идти от простейшего. Гораздо проще повесить на персону метку оранжевого цвета, чем следить за человеком, выделяя его каскадами. Гораздо проще взять камеру с большим разрешением, чем разрабатывать сверхразрешающий алгоритм.
- Строгая постановка задачи в методах оптического распознавания на порядки важнее, чем в задачах системного программирования: одно лишнее слово в ТЗ может добавить 50% работы.
- В задачах распознавания нет универсальных решений. Нельзя сделать алгоритм, который будет просто «распознавать любую надпись». Табличка на улице и лист текста - это принципиально разные объекты. Наверное, можно сделать общий алгоритм(вот хороший пример от гугла), но это будет требовать огромного труда большой команды и состоять из десятков различных подпрограмм.
- OpenCV - это библия, в которой есть множество методов, и с помощью которой можно решить 50% от объёма почти любой задачи, но OpenCV - это лишь малая часть того, что в реальности можно сделать. В одном исследовании в выводах было написано: «Задача не решается методами OpenCV, следовательно, она неразрешима». Старайтесь избегать такого, не лениться и трезво оценивать текущую задачу каждый раз с нуля, не используя OpenCV-шаблоны.
Список приведённых тут методов не полон. Предлагаю в комментариях добавлять критические методы, которые я не написал и приписывать каждому по 2-3 сопроводительных слова.
Часть 1. Фильтрация
В эту группу я поместил методы, которые позволяют выделить на изображениях интересующие области, без их анализа. Большая часть этих методов применяет какое-то единое преобразование ко всем точкам изображения. На уровне фильтрации анализ изображения не производится, но точки, которые проходят фильтрацию, можно рассматривать как области с особыми характеристиками.Бинаризация по порогу, выбор области гистограммы
Самое просто преобразование - это бинаризация изображения по порогу. Для RGB изображения и изображения в градациях серого порогом является значение цвета. Встречаются идеальные задачи, в которых такого преобразования достаточно. Предположим, нужно автоматически выделить предметы на белом листе бумаги:
Выбор порога, по которому происходит бинаризация, во многом определяет процесс самой бинаризации. В данном случае, изображение было бинаризовано по среднему цвету. Обычно бинаризация осуществляется с помощью алгоритма, который адаптивно выбирает порог. Таким алгоритмом может быть выбор матожидания или моды . А можно выбрать наибольший пик гистограммы.
Бинаризация может дать очень интересные результаты при работе с гистограммами, в том числе в ситуации, если мы рассматриваем изображение не в RGB, а в HSV . Например, сегментировать интересующие цвета. На этом принципе можно построить как детектор метки так и детектор кожи человека.
Классическая фильтрация: Фурье, ФНЧ, ФВЧ
Классические методы фильтрации из радиолокации и обработки сигналов можно с успехом применять во множестве задач Pattern Recognition. Традиционным методом в радиолокации, который почти не используется в изображениях в чистом виде, является преобразование Фурье (конкретнее - БПФ). Одно из немногих исключение, при которых используется одномерное преобразование Фурье, - компрессия изображений . Для анализа изображений одномерного преобразования обычно не хватает, нужно использовать куда более ресурсоёмкое двумерное преобразование .
Мало кто его в действительности рассчитывает, обычно, куда быстрее и проще использовать свёртку интересующей области с уже готовым фильтром, заточенным на высокие (ФВЧ) или низкие(ФНЧ) частоты. Такой метод, конечно, не позволяет сделать анализ спектра, но в конкретной задаче видеообработки обычно нужен не анализ, а результат.
Самые простые примеры фильтров, реализующих подчёркивание низких частот (фильтр Гаусса) и высоких частот (Фильтр Габора).
Для каждой точки изображения выбирается окно и перемножается с фильтром того же размера. Результатом такой свёртки является новое значение точки. При реализации ФНЧ и ФВЧ получаются изображения такого типа:
Вейвлеты
Но что если использовать для свёртки с сигналом некую произвольную характеристическую функцию? Тогда это будет называться "Вейвлет-преобразование ". Это определение вейвлетов не является корректным, но традиционно сложилось, что во многих командах вейвлет-анализом называется поиск произвольного паттерна на изображении при помощи свёртки с моделью этого паттерна. Существует набор классических функций, используемых в вейвлет-анализе. К ним относятся вейвлет Хаара , вейвлет Морле , вейвлет мексиканская шляпа , и.т.д. Примитивы Хаара, про которые было несколько моих прошлых статей ( , ), относятся к таким функциям для двумерного пространства.
Выше приведено 4 примера классических вейвлетов. 3х-мерный вейвлет Хаара, 2х-мерные вейвлет Мейера, вейвлет Мексиканская Шляпа, вейвлет Добеши. Хорошим примером использования расширеной трактовки вейвлетов является задачка поиска блика в глазу, для которой вейвлетом является сам блик:
Классические вейвлеты обычно используются для сжатия изображений , или для их классификации (будет описано ниже).
Корреляция
После такой вольной трактовки вейвлетов с моей стороны стоит упомянуть собственно корреляцию, лежащую в их основе. При фильтрации изображений это незаменимый инструмент. Классическое применение - корреляция видеопотока для нахождения сдвигов или оптических потоков. Простейший детектор сдвига - тоже в каком-то смысле разностный коррелятор. Там где изображения не коррелируют - было движение.
Фильтрации функций
Интересным классом фильтров является фильтрация функций. Это чисто математические фильтры, которые позволяют обнаружить простую математическую функцию на изображении (прямую, параболу, круг). Строится аккумулирующее изображение, в котором для каждой точки исходного изображения отрисовывается множество функций, её порождающих. Наиболее классическим преобразованием является преобразование Хафа для прямых. В этом преобразовании для каждой точки (x;y) отрисовывается множество точек (a;b) прямой y=ax+b, для которых верно равенство. Получаются красивые картинки:
(первый плюсег тому, кто первый найдёт подвох в картинке и таком определении и объяснит его, второй плюсег тому, кто первый скажет что тут изображено)
Преобразование Хафа позволяет находить любые параметризуемые функции. Например окружности . Есть модифицированное преобразование, которое позволяет искать любые фигуры . Это преобразование ужасно любят математики. Но вот при обработке изображений, оно, к сожалению, работает далеко не всегда. Очень медленная скорость работы, очень высокая чувствительность к качеству бинаризации. Даже в идеальных ситуациях я предпочитал обходиться другими методами.
Аналогом преобразования Хафа для прямых является преобразование Радона . Оно вычисляется через БПФ, что даёт выигрыш производительности в ситуации, когда точек очень много. К тому же его возможно применять к не бинаризованному изображению.
Фильтрации контуров
Отдельный класс фильтров - фильтрация границ и контуров . Контуры очень полезны, когда мы хотим перейти от работы с изображением к работе с объектами на этом изображении. Когда объект достаточно сложный, но хорошо выделяемый, то зачастую единственным способом работы с ним является выделение его контуров. Существует целый ряд алгоритмов, решающих задачу фильтрации контуров:Чаще всего используется именно Кэнни, который хорошо работает и реализация которого есть в OpenCV (Собель там тоже есть, но он хуже ищёт контуры).
Прочие фильтры
Сверху приведены фильтры, модификации которых помогают решить 80-90% задач. Но кроме них есть более редкие фильтры, используемые в локальных задачах. Таких фильтров десятки, я не буду приводить их все. Интересными являются итерационные фильтры (например активная модель внешнего вида), а так же риджлет и курвлет преобразования, являющиеся сплавом классической вейвлет фильтрации и анализом в поле радон-преобразования. Бимлет-преобразование красиво работает на границе вейвлет преобразования и логического анализа, позволяя выделить контуры:
Но эти преобразования весьма специфичны и заточены под редкие задачи.
Часть 2. Логическая обработка результатов фильтрации
Фильтрация даёт набор пригодных для обработки данных. Но зачастую нельзя просто взять и использовать эти данные без их обработки. В этом разделе будет несколько классических методов, позволяющих перейти от изображения к свойствам объектов, или к самим объектам.Морфология
Переходом от фильтрации к логике, на мой взгляд, являются методы математической морфологии ( , , ). По сути, это простейшие операции наращивания и эрозии бинарных изображений. Эти методы позволяют убрать шумы из бинарного изображения, увеличив или уменьшив имеющиеся элементы. На базе математической морфологии существуют алгоритмы оконтуривания, но обычно пользуются какими-то гибридными алгоритмами или алгоритмами в связке.
Контурный анализ
В разделе по фильтрации уже упоминались алгоритмы получения границ. Полученные границы достаточно просто преобразуются в контуры. Для алгоритма Кэнни это происходит автоматически, для остальных алгоритмов требуется дополнительная бинаризация. Получить контур для бинарного алгоритма можно например алгоритмом жука .Контур является уникальной характеристикой объекта. Часто это позволяет идентифицировать объект по контуру. Существует мощный математический аппарат, позволяющий это сделать. Аппарат называется контурным анализом ( , ).
Если честно, то у меня ни разу ни получилось применить контурный анализ в реальных задачах. Уж слишком идеальные условия требуются. То граница не найдётся, то шумов слишком много. Но, если нужно что-то распознавать в идеальных условиях - то контурный анализ замечательный вариант. Очень быстро работает, красивая математика и понятная логика.
Особые точки
Особые точки это уникальные характеристики объекта, которые позволяют сопоставлять объект сам с собой или с похожими классами объектов. Существует несколько десятков способов позволяющих выделить такие точки. Некоторые способы выделяют особые точки в соседних кадрах, некоторые через большой промежуток времени и при смене освещения, некоторые позволяют найти особые точки, которые остаются таковыми даже при поворотах объекта. Начнём с методов, позволяющих найти особые точки, которые не такие стабильные, зато быстро рассчитываются, а потом пойдём по возрастанию сложности:Первый класс. Особые точки, являющиеся стабильными на протяжении секунд. Такие точки служат для того, чтобы вести объект между соседними кадрами видео, или для сведения изображения с соседних камер. К таким точкам можно отнести локальные максимумы изображения, углы на изображении (лучший из детекторов, пожалуй, детектор Хариса), точки в которых достигается максимумы дисперсии, определённые градиенты и.т.д.
Второй класс. Особые точки, являющиеся стабильными при смене освещения и небольших движениях объекта. Такие точки служат в первую очередь для обучения и последующей классификации типов объектов. Например, классификатор пешехода или классификатор лица - это продукт системы, построенной именно на таких точках. Некоторые из ранее упомянутых вейвлетов могут являются базой для таких точек. Например, примитивы Хаара, поиск бликов, поиск прочих специфических функций. К таким точкам относятся точки, найденные методом гистограмм направленных градиентов (HOG).
Третий класс. Стабильные точки. Мне известно лишь про два метода, которые дают полную стабильность и про их модификации. Это SURF и SIFT . Они позволяют находить особые точки даже при повороте изображения. Расчёт таких точек осуществляется дольше по сравнению с остальными методами, но достаточно ограниченное время. К сожалению эти методы запатентованы. Хотя, в России патентовать алгоритмы низя, так что для внутреннего рынка пользуйтесь.
Часть 3. Обучение
ретья часть рассказа будет посвящена методам, которые не работают непосредственно с изображением, но которые позволяют принимать решения. В основном это различные методы машинного обучения и принятия решений. Недавно Яндыкс выложил на Хабр курс по этой тематике, там очень хорошая подборка. Вот оно есть в текстовой версии. Для серьёзного занятия тематикой настоятельно рекомендую посмотреть именно их. Тут я попробую обозначить несколько основных методов используемых именно в распознавании образов.В 80% ситуаций суть обучения в задаче распознавания в следующем:
Имеется тестовая выборка, на которой есть несколько классов объектов. Пусть это будет наличие/отсутствие человека на фотографии. Для каждого изображения есть набор признаков, которые были выделены каким-нибудь признаком, будь то Хаар, HOG, SURF или какой-нибудь вейвлет. Алгоритм обучения должен построить такую модель, по которой он сумеет проанализировать новое изображение и принять решение, какой из объектов имеется на изображении.
Как это делается? Каждое из тестовых изображений - это точка в пространстве признаков. Её координаты это вес каждого из признаков на изображении. Пусть нашими признаками будут: «Наличие глаз», «Наличие носа», «Наличие двух рук», «Наличие ушей», и.т.д… Все эти признаки мы выделим существующими у нас детекторами, которые обучены на части тела, похожие на людские. Для человека в таком пространстве будет корректной точка . Для обезьяны точка для лошади . Классификатор обучается по выборке примеров. Но не на всех фотографиях выделились руки, на других нет глаз, а на третьей у обезьяны из-за ошибки классификатора появился человеческий нос. Обучаемый классификатор человека автоматически разбивает пространство признаков таким образом, чтобы сказать: если первый признак лежит в диапазоне 0.5
Существует очень много классификаторов. Каждый из них лучше работает в какой-то своей задачке. Задача подбора классификатора к конкретной задаче это во многом искусство. Вот немножко красивых картинок на тему.
Простой случай, одномерное разделение
Разберём на примере самый простой случай классификации, когда пространство признака одномерное, а нам нужно разделить 2 класса. Ситуация встречается чаще, чем может представиться: например, когда нужно отличить два сигнала, или сравнить паттерн с образцом. Пусть у нас есть обучающая выборка. При этом получается изображение, где по оси X будет мера похожести, а по оси Y -количество событий с такой мерой. Когда искомый объект похож на себя - получается левая гауссиана. Когда не похож - правая. Значение X=0.4 разделяет выборки так, что ошибочное решение минимизирует вероятность принятия любого неправильного решения. Именно поиском такого разделителя и является задача классификации.
Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график - это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate ».
) АдаБуста - один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.
SVM ( , , , ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.
Ещё есть нейронные сети и регрессия. Но чтобы кратко их классифицировать и показать, чем они отличаются, нужна статья куда больше, чем эта.
________________________________________________
Надеюсь, у меня получилось сделать беглый обзор используемых методов без погружения в математику и описание. Может, кому-то это поможет. Хотя, конечно, статья неполна и нет ни слова ни о работе со стереоизображениями, ни о МНК с фильтром Калмана, ни об адаптивном байесовом подходе.
Если статья понравится, то попробую сделать вторую часть с подборкой примеров того, как решаются существующие задачки ImageRecognition.
И напоследок
Что почитать?1) Когда-то мне очень понравилась книга «Цифровая обработка изображений» Б. Яне, которая написана просто и понятно, но в то же время приведена почти вся математика. Хороша для того, чтобы ознакомиться с существующими методами.
2) Классикой жанра является Р Гонсалес, Р. Вудс " Цифровая обработка изображений ". Почему-то она мне далась сложнее, чем первая. Сильно меньше математики, зато больше методов и картинок.
3) «Обработка и анализ изображений в задачах машинного зрения» - написана на базе курса, читаемого на одной из кафедр ФизТеха. Очень много методов и их подробного описания. Но на мой взгляд в книге есть два больших минуса: книга сильно ориентирована на пакет софта, который к ней прилагается, в книге слишком часто описание простого метода превращается в математические дебри, из которых сложно вынести структурную схему метода. Зато авторы сделали удобный сайт, где представлено почти всё содержание - wiki.technicalvision.ru
4) Почему-то мне кажется, что хорошая книжка, которая структурирует и увязывает картину мира, возникающую при занятии Image Recognition и Machine Learning - это «Об интеллекте» Джеффа Хокинса. Прямых методов там нет, но есть много мыслей на подумать, откуда прямые методы обработки изображений происходят. Когда вчитываешься, понимаешь, что методы работы человеческого мозга ты уже видел, но в задачах обработки видео.
УДК 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 жовтень.
Постановка задачи определяется целью и возможностями ее реализации.
Цель. Разработать программу классификации деталей прямоугольной формы на качественные и бракованные.
Возможности для реализации задачи определяются возможностями компьютера. Компьютер способен обрабатывать числовую информацию в алгоритмической последовательности. Чтобы реализовать возможности компьютера необходимо смоделировать решаемую задачу.
Моделирование с применением компьютера подразумевает переход от реального объекта (мира) к кодированному описанию его свойств при помощи данных и операций над ними. Такой переход, как правило, выполняется в несколько этапов:
Абстракция – выбор наиболее существенных признаков объекта с точки зрения поставленной задачи.
Необходимо провести исследования, которые позволяют от объекта моделирования перейти к субъекту моделирования отбросив все лишнее в соответствии с целью в поставленной задаче
Чем отличается прямоугольник от других четырёхугольников?
- Равенство противоположных сторон.
- Параллельность противоположных сторон.
- Равенство диагоналей.
- Все углы прямые.
Какой минимум признаков нужен для однозначного решения задачи?
- Равенство 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) .
Отображение модели в компьютере
Любая информация в конечном итоге отображается в компьютере с помощью двоичных чисел (кодов) во внутримашинную модель. Ранее кодирование осуществлялось программистом. Сейчас основная часть программ создаётся на алгоритмических языках.
