Университет информатики и радиоэлектроники” удк 007.001.362: 681.3

Учреждение образования “БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ” УДК 007.001.362: 681.327.12.001.362 ВЕРШОК Денис Александрович [email protected] АЛГОРИТМИЧЕСКИЕ СРЕДСТВА ОБРАБОТКИ И АНАЛИЗА ИЗОБРАЖЕНИЙ НА ОСНОВЕ ПРЕОБРАЗОВАНИЯ ХАФА Специальность 05.13.15 – Вычислительные машины и системы АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Минск – 2002 Работа выполнена в Государственном научном учреждении "Институт технической кибернетики Национальной академии наук Беларуси" Научный руководитель – доктор технических наук, профессор Садыхов Рауф Хосровович (БГУИР, каф. ЭВМ) Официальные оппоненты:

доктор технических наук, профессор Петровский А.А.

(БГУИР, каф. ЭВС) кандидат физико-математических наук, доцент Краснопрошин В.В.

(БГУ, каф. Математического обеспечения АСУ) Оппонирующая организация – Научно-производственное республиканское унитарное предприятие Агат-Систем" Защита состоится 31 октября 2002 года в 14 часов на заседании совета по защите диссертаций Д 02.15.04 при Учреждении образования "Белорусский государственный университет информатики и радиоэлектроники" по адресу: 220027, г.Минск, П.Бровки, 6, а.232-1 корп., тел. С диссертацией можно ознакомиться в библиотеке Учреждения образования "Белорусский государственный университет информатики и радиоэлектроники".

Автореферат разослан “_” сентября 2002 г.

Ученый секретарь совета по защите диссертаций кандидат технических наук, доцент Б.В. Никульшин ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы диссертации. Во многих системах обработки изображений необходимо решать задачи поиска или идентификации объектов заданной формы: прямых, окружностей, эллипсов и т.п. Преобразование Хафа, введенное в 1962г. стало эффективным средством решения таких задач.

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

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

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

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

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

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

Связь работы с крупными научными программами, темами. Работа выполнена в лаборатории идентификации систем Института технической кибернетики НАН Беларуси в сотрудничестве с кафедрой ЭВМ Белорусского Государственного Университета Информатики и Радиоэлектроники в рамках следующих научно-исследовательских работ и программ: Проект Фонда фундаментальных исследований Республики Беларусь №T96-098 от 1 марта 1997г. “Разработка теоретических основ анализа и синтеза изображений на базе спектральных дескрипторов для создания систем компьютерного видения”.

(1997-1999);

Проект Фонда фундаментальных исследований Республики Беларусь №T97M-079 от 1 марта 1998г “Разработка методов и алгоритмов обработки и анализа изображений на основе моментов и моментных функций для создания систем идентификации образов" (1998-2000);

Научно исследовательская работа ГБЦ № 96-3087 "Разработать методы и алгоритмы идентификации изображений для создания систем реального времени" (1997 1998);

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

регистрации 19961906 (1996-2000);

Государственная программа фундаментальных исследований "Исследование проблем моделирования интеллектуальных процессов", тема "Волна 15" – "Разработка структурных моделей клеточных автоматов для задач синтаксического распознавания образов", номер гос. регистрации 199961901 (1996-2000);

Государственная программа "Информатика", тема "Разработать систему цифровой обработки изображений образцов элементов и узлов электронных изделий" (1998-2000);

Научно-исследовательская работа, поддержанная фондом INTAS “Intelligent neural system for autonomous control of a mobile robot”, INTAS-BELARUS № 97 2028. (1999-2000) Цель и задачи исследования. Целью работы является разработка эффективных алгоритмов выделения геометрических примитивов на основе преобразования Хафа, применительно к созданию систем обработки изображений в области робототехники, систем распознавания рукописных символов, а также для решения задач обратного перепроектирования.

Поставленная цель определяет следующие основные задачи:

1. Исследовать свойства дискретного преобразования Хафа на предмет правильного выбора параметров дискретизации при построении алгоритмов на его основе для решения различных прикладных задач.

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

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

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

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

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

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

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

1. Разработан алгоритм выделения информативных признаков проекционного типа на основе преобразования Хафа для распознавания рукописных символов. Алгоритм позволяет выделять инвариантные к масштабу и повороту признаки и обойтись при этом без дополнительных преобразований для удовлетворения последних требованиям компактности и линейной разделимости.

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

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

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

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

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

В рамках создания системы обработки видеоинформации от монокулярного источника научные результаты получены в ходе выполнения проекта INTAS BELARUS №97-2028 "Intelligent neural system for autonomous control of a mobile robot". Предложенные принципы навигации мобильного робота в незнакомой обстановке с использованием видеоданных востребованы для решения практических задач, например, таких как, функционирование робота на производстве, в агрессивной обстановке при химической или радиоактивной опасности, при ликвидации последствий аварий и стихийных бедствий и т.д.

Алгоритм сегментации полутоновых изображений интегрирован в систему цифровой обработки изображений слоев интегральных микросхем, которая внедрена на УП "Белмикроситемы" ПО "Интегралл". Перспективы внедрения подобных системы существуют на таких предприятиях как ПО "Горизонт", ПО "Витязь", УП КБТЭМ-ОМО.

Основные положения диссертации, выносимые на защиту.

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

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

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

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

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

6. Система Цифровой Обработки Изображений Слоев ИМС, предназначенная для автоматизации этапа восстановления топологии интегральной схемы при решении задачи обратного перепроектирования.

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

Апробация результатов диссертации. Результаты диссертационной работы докладывались и обсуждались на: The Second international Conference "New Information Technologies in Education" (NITE'96, Minsk, Belarus, 1996);

Научно-технической конференции посвященной 30-летию Брестского политехнического института, (Брест, Беларусь, 1996);

The Fourth International Conference “Pattern Recognition and Information Processing” (PRIP'97, Minsk, Belarus, 1997);

Первой международной конференции “Цифровая обработка информации и управление в чрезвычайных (экстремальных) ситуациях” (ЦОИУЧС’98, Минск, Беларусь, 1998);

Международной научно-технической конференции “Новые информационные технологии в науке и производстве” (Минск, Беларусь, 1998);

Десятой научно-технической конференции “Новые технологии в машиностроении и вычислительной технике”, (Брест, Беларусь, 1998);

3rd Eurel Workshop and Masterclass "European Advanced Robotics Systems Development" (Robotics2000, Salford, UK);

Второй международной конференции “Цифровая обработка информации и управление в чрезвычайных (экстремальных) ситуациях” (ЦОИУЧС’2000, Минск, Беларусь, 2000);

The Sixth International Conference “Pattern Recognition and Information Processing” (PRIP'2001, Minsk, Belarus, 2001);

The International Workshop on Intelligent Data Acquisition And Advanced Computing Systems: Technology and Applications (IDAACS'2001, Foros, Ukraine, 2001);

The Second International Conference on Neural Networks and Artificial Intelligence (ICNNAI'2001, Minsk, Belarus, 2001).

Опубликованность результатов. По основным положениям и результатам выполненных исследований опубликовано 19 печатных работ. Из них 4 статьи опубликовано в научных сборниках, 15 в материалах научных конференций, печатная работа опубликована в тезисах научных конференций. Общее число печатных страниц – 115.

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

ОСНОВНОЕ СОДЕРЖАНИЕ В первой главе рассмотрены методы и алгоритмы выделения на изображениях прямых линий и прямолинейных сегментов, отмечены особенности функционирования этих алгоритмов, их достоинства и недостатки, выявлено, что при обработке зашумленных изображений наиболее эффективными являются алгоритмы на основе преобразования Хафа.

Рассмотрены две формы преобразования Хафа для выделения прямых, определяемые уравнением представления прямой: (k, b) и (, ) – преобразования. Отмечены достоинства, недостатки и ограничения каждой из двух дискретных реализаций преобразования. Для обеих форм приведены рекомендации по выбору параметров дискретизации. Показано, что для (k, b) – преобразования необходимо выполнение следующих условий: b y и b, а для (, ) – x и k, где М – количество (M 1)x max x дискретных значений переменной х. В соответствии с приведенными рекомендациями предложены алгоритмы вычисления обеих форм преобразования Хафа.

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

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

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

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

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

С помощью преобразования Хафа в алгоритме формируются признаки в виде проекционных профилей символа (рис.1).

Рис. 1. Пример проекционных профилей символа Для получения таких профилей используется – преобразование Хафа.

При этом размерность пространства признаков при размере исходного изображения NN точек будет KN 2, где K – количество проекционных профилей. В результате применения преобразования, изображение цифры из исходного XY пространства переводится в R пространство параметров. Если, вычисляя преобразование Хафа параметр зафиксировать, то в результате формируется одномерное пространство, которое представляет собой проекцию (профиль) исходного изображения на ось R, под углом проецирования Q = + / 2 относительно оси X. Проекционный профиль в этом пространстве описывается проекционной функцией g ( r ). Алгоритм построен так, что вначале вычисляется проекция для угла проецирования Q = + / 2, где = 0, которая после некоторой обработки, поступает на вход классификатора.

Последний на основании двух критериев делает вывод, либо об отнесении изображения к одному из классов, либо об уточнении сведений об изображении. Во втором случае вычисляется проекция под углом Q = + / 2, где = /2 и т. д. Принцип выбора угла для формирования последовательности вычисляемых проекций показан на рис.2.

9/16 /2 7/ 5/ (13) (2) (12) 3/ (7) (6) 11/16 (14) 5/16 (11) /4 (3) 3/4 (4) 3/16 (10) 13/16 (15) /8 (5) 7/8 (8) /16 (9) 15/16 (16) 0 (1) Рис. 2. Последовательность выбора угла для вычисления проекций Проекции поступают на классификатор после дополнительной обработки, которая необходима для придания признакам свойств инвариантности к масштабу. Для этого значения функции g подвергаются нормализации, которая выполняется в соответствии с g( r ) g norm ( r ) =, r = 0K R 1, (1) max g ( ) где g ( r ) – значение проекционной функции в точке r ;

g norm ( r ) – нормализованное значение проекционной функции в точке r ;

max g ( ) – абсолютное максимальное значение проекционной функции.

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

На основе модифицированного преобразования Хафа разработан алгоритм выделения информативных признаков в виде прямолинейных сегментов для распознавания рукописных символов. Суть алгоритма состоит в аппроксимации геометрической формы символа прямолинейными отрезками. Для поиска отрезков используется - преобразование Хафа, в которое внесены следующие модификации: 1) При формировании массива-накопителя используется весовое аккумулятивное значение AV, вместо единичного.

Значение AV выбирается в соответствии с предложенными правилами, большее значение AV выбирается для тех точек, которые с большей вероятностью принадлежат прямым линиям. 2) Использование правила для выбора параметра. Для квантования, предусмотрено восемь направлений прямолинейного сегмента, однако не имеет смысла в каждой черной точке изображения вычислять преобразование для всех восьми направлений. В соответствии с результатами локального анализа изображения определяются наиболее вероятные направления, в которых расположен прямолинейный сегмент. Эта модификация позволяет снизить вычислительную сложность преобразования Хафа, а также решает проблему выделения ложных сегментов.

После применения модифицированного преобразования Хафа для выделения прямых, цифра представляется набором признаков в виде прямолинейных сегментов. Каждый из признаков определяется тремя элементами: – позицией, – ориентацией и длиной – значением из соответствующей ячейки (, ) накапливающего массива g.

Для придания признакам инвариантных свойств по отношению к преобразованию масштабирования достаточно использовать нормализованные значения величин и g (, ) – это norm и g norm (, ) соответственно:

g ( i, i ) g norm ( i, i ) =, max g (, ) (2) i i _ norm = ;

max где max g (, ) – максимальное значение в массиве g, max – максимальное значение параметра среди выделенных прямых.

Для учета поворота исходного изображения необходимо вычислять циклическую свертку результатов преобразования Хафа, что является трудоемкой вычислительной задачей. Предложено использовать относительные значения параметра, определяющего ориентацию признака. В качестве такого параметра выбран угол между соседними прямолинейными сегментами. Для его нахождения выделенные признаки сначала упорядочиваются по возрастанию параметра, а затем находится – угол между соседними признаками: i = i i 1 ;

i = 1K N, 0 = 0. Инвариантность к сдвигу в поле изображения должна предусматриваться в системе распознавания, использующей разработанный алгоритм, на стадии предварительной обработки.

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

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

Направления задаются углами наклона нормали относительно оси OX. Для их определения в окрестности каждой точки проводится локальный анализ изображения. Результатами этого этапа являются тангенсы угла наклона возможных направлений нормали (относительно оси OX) в данной точке (x,y) исходного изображения. Эти результаты поступают на второй этап, который представляет собой двумерное преобразование Хафа, где используются следующие уравнения отображения:

b = tan a + ( y x tan ), (3) y b a= x +, tan tan где (a,b) – координаты центра окружности;

tan – тангенс угла наклона нормали к дуге окружности в точке (x,y).

Их можно получить из уравнения окружности, опираясь на утверждение, что все векторы нормали, проведенные к дуге окружности, пересекаются в центре этой окружности. На выходе второго этапа формируется двумерный накапливающий массив g (b, a ), максимумы в котором определяют центры искомых окружностей. Таким образом, каждый выделенный информативный признак в форме окружности определяется координатами центра окружности (b,a) и длиной дуги окружности (значение в соответствующей ячейке g (b, a ) накапливающего массива). При использовании комбинированных признаков, как прямолинейных сегментов, так и окружностей, необходимо унифицировать их описания. Поэтому перечисленная выше тройка элементов при описании i ого информативного признака в виде окружности заменяется на другую: i, i, g ( i, i), где i – расстояние от начала координат до центра окружности, i – угол наклона вектора, опущенного из центра окружности в начало координат, g ( i, i) – длина дуги окружности (значение в соответствующей ячейке накапливающего массива).

Для придания признакам инвариантных свойств к масштабу, как и в случае прямолинейных сегментов, для окружностей достаточно использовать нормализованные значения параметров и g (, ) – norm и g norm (, ) соответственно. Для достижения инвариантности признаков к повороту исходного изображения на углы кратные шагу дискретизации ориентирующего параметра используются его относительные значения. Инвариантность к сдвигу в поле изображения должна предусматриваться в системе распознавания, использующей разработанный алгоритм, на стадии предварительной обработки.

В третьей главе разработан алгоритм сегментации полутоновых изображений. Алгоритм комбинирует в себе два подхода к решению задачи сегментации и поэтому, состоит из двух основных частей. Вначале в алгоритме решается задача выделения на изображении границ и аппроксимации их прямолинейными сегментами, а затем на основе полученной информации – покрытия изображения набором областей. Критерием разделения на области выступает их цветовая характеристика, а для аппроксимации границ используется преобразование Хафа, что позволяет избавиться от недостатков присущих гранично-ориентированным методам, проводить аппроксимацию с заданной степенью точности, обрабатывать сильнозашумленные и искаженные изображения. На выходе алгоритма формируется векторное представление изображения в виде набора областей. Разработанный алгоритм адаптирован для выделения металлических проводников на изображениях слоев цифровых интегральных микросхем (ИМС) и их технологических шаблонах (рис 3).

а б Рис. 3. Исходные изображения а) слоя ИМС;

б) шаблона ИМС В алгоритме последовательно выполняются следующие этапы обработки:

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

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

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

На этапе выделения максимумов в алгоритме применялись: 1) поиск абсолютного максимального значения, превышающего пороговое в некоторой локальной окрестности;

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

Определение "точек-кандидатов" на излом. На этом этапе находятся точки пересечения всех прямых в пространстве исходного изображения.

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

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

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

Задачей объединения элементарных областей является получение нескольких, как можно больших по площади областей из набора разрозненных элементарных областей. Эти большие области в конечном итоге и определяют объекты на изображении. Например, области i и i+1, имеющие общие ребра, объединяются в одну, если для них выполняется следующее соотношение:

Coli Coli +1 T, (4) где T – пороговое значение;

Coli – цвет i-ой элементарной области.

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

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

В заключении третьей главы приведены результаты экспериментов по обработке алгоритмом изображений слоев ИМС. Оценка качества работы алгоритма проводилась на основании заключения эксперта. При обработке изображений шаблонов слоев ИМС процент успешно обработанных изображений достиг 95 %, при обработке изображений слоев ИМС – 90%.

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

Рассмотрена концепция построения программной оболочки экспериментальной системы распознавания и обработки изображения. Главная ее цель – обеспечение повторного использования программных средств от разных разработчиков алгоритмов. В соответствии с требованиями программной оболочки проводилась разработка систем, описанных в четвертой главе.

Разработана система распознавания рукописных арабских цифр. В рамках системы проведено комплексное экспериментальное тестирование предложенных алгоритмов выделения информативных признаков на основе преобразования Хафа. Структура системы с использованием алгоритма выделения проекционных признаков представлена на рис. 4.

Вх. изображение да Преобразование Хафа для утоньшение сдвиг классификатор нормализация получения i-ого информативного признака нет Предварительная обработка i:=i+ Рис. 4. Структура системы распознавания рукописных символов с использованием алгоритма выделения проекционных признаков Достоверность распознавания для всех алгоритмов в составе системы составила не ниже 98%. Получены экспериментальные подтверждения увеличения быстродействия указанных алгоритмов по сравнению с алгоритмами на основе классического преобразования Хафа.

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

Система включает три этапа обработки, на которых используются оригинальные алгоритмы, в том числе основанные на преобразовании Хафа, позволяющие достигать заданной точности и функционировать системе в реальном масштабе времени (рис. 5). Эксперименты системы с мобильным роботом Вальтер подтвердили возможность его успешной навигации при Система обработки видеоинформации Выделение Выделение Отслеживание Выделение границ на прямолинейных сегментов прямых на основе сегментов на основе список сегментов преобразо- основе обратного преобразо (для каждого вания преобразования вания Хафа сегмента Уолша Хафа координаты центра, ориентация, длина, Изобр. t-t расстояние от Изобр. t центра до робота) данные от ультразву ковых Нейронная датчиков сеть для Управляющая формиро карта расстояний, система на робот вания карты полученная от основе расстояний позиционных Данные от от позици- нейронных датчиков сканера в сетей онных инфра- датчиков красном диапазоне Данные от тактильных датчиков Управляющие сигналы на электроприводы робота:

1) движение вперед/назад со скоростью V, 2) остановка, 3) поворот влево/вправо на угол скорости не более 15 мм/сек.

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

Разработка этой системы является одной из первых попыток автоматизации данного этапа работы инженера-тополога. Система состоит из трех программных модулей (подсистем): подсистемы склейки кадров изображения, подсистемы предварительной обработки кадров, подсистемы сегментации и векторного описания объекта, которые могут работать как независимые процессы. В основе подсистемы сегментации и векторного описания объекта используется алгоритм сегментации полутоновых изображений на основе преобразования Хафа, предложенный в третьей главе диссертационной работы.

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

В приложении 1 диссертационной работы приведен фрагмент из базы рукописных арабских цифр, на которой проводилось тестирование разработанных алгоритмов выделения информативных признаков. В приложении 2 показаны изображения слоев интегральных микросхем и их шаблонов. В приложении 3 представлены внутрисистемные форматы файлов, используемые в системе цифровой обработки слоев ИМС. В приложении приведено описание пунктов меню в программных модулях системы цифровой обработки изображений слоев ИМС. В приложении 5 представлены акты о внедрении результатов диссертационной работы.

ЗАКЛЮЧЕНИЕ Главный результат диссертационной работы состоит в разработке алгоритмов обработки и анализа изображений на основе преобразования Хафа и предложенных модификаций этого преобразования. Данные алгоритмы интегрированы в системы обработки и анализа изображений различного назначения. Испытания этих систем подтвердили эффективность разработанных алгоритмов.

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

Исследованы две дискретные формы этого преобразования для выделения прямых: (k, b ) и (, ) – преобразования. Для обеих форм приведены рекомендации по выбору параметров дискретизации, и в соответствии с этими рекомендациями предложены алгоритмы вычисления обеих форм ПХ [3]. Выполнен обзор существующих разновидностей преобразования Хафа, отмечены их достоинства и недостатки, определены возможные пути оптимизации алгоритмов вычисления ПХ, в результате, обоснована необходимость разработки новых алгоритмов на основе модификаций преобразования Хафа для решения различных задач обработки и анализа изображений.

2. Разработан алгоритм выделения информативных признаков проекционного типа на основе преобразования Хафа для распознавания рукописных символов [1]. Признаки инвариантны к масштабу, а инвариантность к сдвигу и повороту предусматривается в системе распознавания на этапах предварительной обработки и классификации. Алгоритм позволяет обойтись без дополнительных преобразований для удовлетворения признаков требованиям компактности и линейной разделимости.

3. На основе модифицированного преобразования Хафа разработаны алгоритмы выделения информативных признаков в виде прямолинейных сегментов [5-6] и комбинированных признаков в форме прямолинейных сегментов и окружностей [2],[7] для распознавания рукописных символов.

Признаки инварианты к масштабированию, повороту образа на углы кратные шагу дискретизации параметра, задающего их ориентацию, а инвариантность к сдвигу предусматривается на этапе предварительной обработки. Предложенные модификации по выбору параметра, введения аккумулятивного значения AV и применения уравнений отображения (3), при вычислении ПХ, позволяют увеличить быстродействие и повысить точность распознавания по сравнению с алгоритмами на основе стандартного преобразования Хафа. Кроме того, снижаются требования к памяти из-за отказа от использования трехмерного массива-аккумулятора при выделении окружностей.

4. Разработан алгоритм сегментации для обработки полутоновых изображений слоев цифровых интегральных микросхем [10],[14],[17-19], основанный на оригинальном подходе, находящемся на стыке гранично-ориентированных и областно-ориентированных методов сегментации, что позволяет обрабатывать сильнозашумленные и искаженные полутоновые изображения.

Алгоритм интегрирован в систему Цифровой Обработки Изображений Слоев ИМС [4],[14][16], которая предназначенная для автоматизации этапа восстановления топологии интегральной схемы при решении задачи обратного перепроектирования. Разработка этой системы является одной из первых попыток автоматизации данного этапа работы инженера-тополога.

5. Рассмотрена концепция построения программной оболочки экспериментальной системы распознавания и обработки изображений. В рамках этой концепции разработана система распознавания рукописных арабских цифр [1-2],[5],[7] и проведено комплексное экспериментальное тестирование предложенных алгоритмов выделения информативных признаков. В результате: достоверность распознавания для всех алгоритмов составила не ниже 98%, также получены экспериментальные подтверждения увеличения быстродействия указанных алгоритмов по сравнению с алгоритмами на основе классического преобразования Хафа.

6. Разработана система обработки видеоинформации от монокулярного источника для решения задачи управления мобильным роботом в незнакомой обстановке [11-13],[15] структурированного пространства.

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в сборниках и журналах 1. Садыхов Р.Х., Вершок Д.А. Алгоритм выделения информативных признаков на основе преобразования Радона в системе распознавания рукописных символов // Известия НАН Беларуси. Cер. физ.-тех. наук.– 1998.– No.3.– С. 103-107.

2. Вершок Д.А., Садыхов Р.Х. Алгоритм выделения инвариантных информативных признаков для распознавания рукописных символов, основанный на преобразовании Хафа // Идентификация образов: Сб. науч.

тр.– Минск: Ин-т техн. кибернетики НАН Беларуси.– 1999.– С. 7-15.

3. Вершок Д.А., Садыхов Р.Х. Особенности дискретного преобразования Хоуга // Идентификация образов: Сб. науч. тр. – Минск: Ин-т техн. кибернетики НАН Беларуси.– 2001.– С. 63-71.

4. Система цифровой обработки изображений слоев интегральных микросхем / Вершок Д.А., Дудкин А.А., Калюта А.Г. и др. // Идентификация образов: Сб.

науч. тр.– Минск: Ин-т техн. кибернетики НАН Беларуси.– 2001.– С. 71-87.

Доклады на международных и республиканских конференциях 5. Sadykhov R.H, Vershok D.A. Modified algorithm of Hough transform in a system of handwritten numerals recognition // Proc. of The Second Int. Conf. "New Information Technologies in Education" (NITE'96), Minsk, Belarus, 12-14 Nov.

1996. / State econ. university.– Minsk, 1996.– P. 363- 6. Садыхов Р.Х., Вершок Д.А. Алгоритмы выделения контуров бинарного изображения на основе модифицированного преобразования Хафа // Материалы науч.-техн. конф., посвященной 30-летию института / Брестский политехн. ин-т.– Брест, 1996.– 2ч.– С. 108-109.

7. Sadykhov R.H., Vershok D.A. Algorithm of invariant features extraction based on modified Hough transform // Proc. of fourth int. conf. "Pattern Recognition and Information Processing" (PRIP'97), Minsk, Belarus, 20-22 May 1997 / Belarussian state university.– Minsk, 1997.– Vol.2.– P. 69-75.

8. Вершок Д.А. Алгоритм выделения эллиптических объектов основанный на преобразовании Хафа и использовании геометрических свойств объектов // Новые технологии в машиностроении и вычислительной технике: Труды X науч.-техн. конф., Брест, 1998 / Брестский политехн. ин-т.– Брест, 1998.– 2ч.– C. 92-96.

9. Вершок Д.А., Садыхов Р.Х. Алгоритм выделения эллипсов на основе преобразования Хафа // Цифровая обработка информации и управление в чрезвычайных (экстремальных) ситуациях (ЦОИУЧС-98): Труды 1-ой межд.

конф., Минск, Беларусь, 22-25 сент. 1998 г. / Ин-т техн. кибернетики НАН Беларуси.– Минск, 1998.– Т. 3.– С. 56-59.

10.Вершок Д.А., Садыхов Р.Х. Алгоритм обработки полутоновых изображений на основе преобразования Хафа // Новые информационные технологии в науке и производстве: Материалы межд. науч.-техн. конф., Минск, Беларусь, 25-27 нояб. 1998г / Бел. гос. универ. информатики и радиоэлектроники.– Минск, 1998.– С. 251-254.

11.The system of video-data processing for the autonomous control of mobile robots.

Vershok D., Sadykhov R., Schilling K. e.a. // Proc. of 3rd Eurel Workshop and Masterclass "European Advanced Robotics Systems development", Salford, U.K, 12-14 April 2000 / University of Salford.– Manchester, 2000.– Vol.2.– P. 287 291.

12.Vershok D., Selikhanovich A., Sadykhov R. The system of visual information processing for the control of mobile robot // Цифровая обработка информации и управление в чрезвычайных ситуациях: Труды 2-ой межд. конф., Минск, Беларусь, 2000г. / Ин-т техн. кибернетики НАН Беларуси.– Минск, 2000.– Т. 2.– С. 82-88.

13.Vershok D., Nikolaychuk D. Visual information using for the mobile robot control // Цифровая обработка информации и управление в чрезвычайных ситуациях: Труды 2-ой межд. конф., Минск, Беларусь, 2000г. / Ин-т техн.

кибернетики НАН Беларуси.– Минск, 2000.– Т. 1.– С. 75-81.

14.Вершок Д.А., Дудкин А.А., Садыхов Р.Х. Система обработки изображений для выделения объектов заданного цвета // Цифровая обработка информации и управление в чрезвычайных ситуациях: Труды 2-ой межд. конф., Минск, Беларусь, 2000г. / Ин-т техн. кибернетики НАН Беларуси.– Минск, 2000.– Т. 2.– С. 149-153.

15.Vershok D.A. Approach to monocular vision application for mobile robot control // Proc. of sixth int. conf. "Pattern Recognition and Information Processing" (PRIP'2001), Minsk, Belarus, 15-17 May 2001 / Inst. of engin. cybernetics.– Minsk, 2001.– Vol.2.– P. 130-135.

16.Computer-aided system for LSI circuit video image processing. Doudkin A.A., Selichanovich A.M., Vatkin D.A, Vershok D.A. // Proc. of sixth int. conf. "Pattern Recognition and Information Processing" (PRIP'2001), Minsk, Belarus, 15- May 2001 / Inst. of engin. cybernetics.– Minsk, 2001.– Vol.2.– P. 105-109.

17.Contour detection algorithms of layout objects on chip images. Doudkin A.A., Sadykhov R.Kh., Selikhanovich A.M., Vershok D.A. Proc. of sixth int. conf.

"Pattern Recognition and Information Processing" (PRIP'2001), Minsk, Belarus, 15-17 May 2001 / Inst. of engin. cybernetics.– Minsk, 2001.– Vol.2.– P. 77-81.

18.Contour extraction algorithm for LSI circuit video image processing.

Doudkin A.A., Sadykhov R.Kh., Selikhanovich A.M., Vershok D.A. // Proc. of the Int. Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS'2001), Foros, Ukraine, 1-4 July 2001 / Inst. of Comput. Informat. Tehnologies.– Ternopil, 2001.– P. 69-72.

19.Vershok D.A. The algorithm of segmentation of grayscale images // Proc. of the 2nd int. conf. on neural networks and artificial intelligence (ICNNAI'2001), Minsk, Belarus|, 2-5 oct. 2001г. / Belarussian. st. university of informatics and radioelectronics.– Minsk, 2001.– P. 143-146.