Разработка и исследование алгоритмов распознавания изображений на основе определения экстремальных признаков замкнутых контуров с помощью сортировки

На правах рукописи    Рюмин Олег Германович Разработка и исследование алгоритмов распознавания изображений на основе определения экстремальных признаков замкнутых контуров с помощью сортировки Специальность: 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Таганрог 2008 Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт». Научный руководитель: доктор технических наук, профессор Ромм Яков Евсеевич Официальные оппоненты: доктор технических наук, профессор Кравченко Павел Павлович кандидат технических наук, старший научный сотрудник Сапрыкин Владимир Абрамович Ведущая организация: ФГНУ НИИ «СПЕЦВУЗАВТОМАТИКА», г. Ростов-на-Дону Защита состоится «     » декабря 2008 г. в           на заседании диссертационного совета Д 212.208.21 Южного федерального университета по адресу: г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406. С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148. Автореферат разослан «     » ноября 2008 г. Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, ГСП -17А, Ростовская область, г. Таганрог, пер. Некрасовский, 44, диссертационный совет Д 212.208.21. Ученый секретарь диссертационного совета Д 212.208.21 доктор технических наук, профессор Н.И. Чернов ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Распознавание, классификация и идентификация плоских изображений – традиционное направление исследований в области теоретической информатики. В частности, актуальным направлением является распознавание печатных и рукописных символов в условиях помех. Минимизация временной сложности и повышение точности схем распознавания и идентификации изображений являются важнейшими требованиями, предъявляемыми к распознающим системам. В то же время обработка изображений сопряжена со значительным объемом вычислений, как правило, в условиях искажения поступающей информации. Широко распространены методы распознавания, основанные на анализе контурных представлений объектов: считается, что форма контуров является наиболее стабильным признаком при яркостных искажениях. Многие задачи распознавания необходимо решать в жестких ограничениях временной сложности, поэтому алгоритмы распознавания должны быть оптимизированы по времени выполнения, временная оптимизация может достигаться за счет распараллеливания. Компьютерная реализация исследуемых алгоритмов, помимо высокого быстродействия, требует практической устойчивости к искажениям и помехам. Ограниченность объемов машинной памяти, выделяемой под пространство эталонов, а также требование минимизации временной сложности делают актуальными разработку и исследование распараллеливаемых алгоритмов распознавания, классификации и идентификации, инвариантных к сдвигу, масштабированию и ротации изображений. Существующие методы сталкиваются с трудностями как при построении схем распознавания, так и при выборе эталонных последовательностей. При этом многие методы характеризуются существенной вычислительной и временной сложностью и либо не адаптированы к параллельным вычислительным системам, либо ориентированы на узкий класс идентифицируемых изображений. В направлении решения существующих проблем целесообразно исследовать применение схем сортировки. Сортировка делает обрабатываемую информацию упорядоченной, на данной основе достигается упрощение алгоритмов распознавания, количество используемых формул и численных методов сокращается. Вследствие этого и по построению сортировки ее применение позволяет снизить рост погрешности: в основе сортировки лежат лишь операции сравнения, сами сортируемые элементы не изменяются. В известных методах распознавания сортировка применяется преимущественно для упорядочения эталонных образов. Методы распознавания с использованием сортировки, как правило, отличаются сугубо технической направленностью, при обработке графической информации сортировка не используется в качестве конструктивной части метода, на ее основе не достигается адаптация к изменениям масштаба и поворота изображений в условиях помех. Цель диссертационной работы состоит в построении метода распознавания и идентификации плоских изображений, ограниченных связным замкнутым контуром, который достигает сравнительного упрощения на основе упорядочения информации при помощи алгоритмов сортировки. Конструируемый метод должен расширить класс детерминированно идентифицируемых изображений в условиях сдвига, ротации и изменения масштаба, достигать устойчивости идентификации за счет итеративности алгоритма и выполнения условий сходимости. Одной из целей исследования является преобразование метода в параллельную форму и выполнение соответственных оценок временной сложности. Для достижения поставленной цели в диссертационной работе решаются следующие задачи: 1. Разработать метод распознавания плоских изображений, инвариантный относительно сдвига, ротации и масштабирования, который позволял бы осуществлять устойчивое построение векторов распознавания изображений с произвольными замкнутыми контурами в условиях растеризации и обладал свойством параллелизма. 2. Синтезировать параллельный алгоритм фильтрации искажений контура, который позволял бы устойчиво идентифицировать изображение в условиях помех с минимизацией временной сложности. 3. Построить структуру данных для базы эталонов и схему идентификации изображения путем последовательного сравнения вектора распознавания с эталонными векторами по норме в условиях искажения контура. 4. Синтезировать алгоритм идентификации отличительных особенностей фрагментов контуров по экстремальным отклонениям от хорд. 5. Выполнить программный эксперимент по распознаванию и идентификации контурно представленных изображений с учетом искажений, сдвига, ротации и масштабирования на растре в аспекте сравнения с известными методами. Методы исследования опираются на теоретические основы информатики, на методы прикладной информатики, на теорию сложности, используются алгоритмы сортировки, цифровой обработки изображений и распознавания образов, применяются современные информационные технологии, структурное и объектное программирование. Достоверность результатов вытекает из математического обоснования конструктивных алгоритмов распознавания и идентификации изображений, подтверждается оценками временной сложности, а также результатами программного моделирования и эксперимента. Научная новизна заключается в следующем: 1. Предложен итерационный метод распознавания плоских изображений, отличающийся формированием экстремальных признаков на основе сортировки, сходимостью для широкого класса изображений, инвариантностью относительно сдвига, ротации и масштабирования, который позволяет осуществлять устойчивое построение векторов распознавания изображений с произвольными замкнутыми контурами в условиях растеризации и обладает параллелизмом. 2. Синтезирован параллельный алгоритм фильтрации искажений контура при радиально-круговой развертке изображения, который отличается от известных фильтров по построению и позволяет на его основе устойчиво идентифицировать изображение при ограниченных искажениях с минимизацией временной сложности: все экстремумы полярного радиуса входного изображения в максимально параллельной форме могут быть идентифицированы и отфильтрованы с временной сложностью. 3. Разработана структура данных для базы эталонов и иерархическая схема однопроходного поиска в подклассе эталонных векторов, которая позволяет идентифицировать изображение путем последовательного сравнения вектора распознавания с эталонными векторами по норме. 4. Представлены схемы изменения размерности векторов распознавания с учетом иерархии эталонов, позволяющие идентифицировать отличительные особенности фрагментов контуров по экстремальным отклонениям от хорд и на этой основе уточнять идентификацию изображения в целом. 5. Выполнен программный эксперимент по распознаванию и идентификации контурно представленных изображений широкого класса с учетом ограниченных искажений, сдвига, ротации и масштабирования, в результате которого выявлено положительное отличие предложенного метода от известных по совокупности компонент сравнения. Основные положения, выносимые на защиту: 1. Предложен распараллеливаемый сходящийся итерационный метод построения векторов распознавания растровых изображений с произвольными замкнутыми контурами, инвариантный относительно их сдвига, ротации и масштабирования. 2. Синтезирован параллельный алгоритм фильтрации искажений контура при радиально-круговой развертке растрового изображения, позволяющий устойчиво идентифицировать изображение при ограниченных искажениях с минимизацией временной сложности. 3. Разработана структура данных для базы эталонов и иерархическая схема однопроходного поиска, позволяющая идентифицировать изображение путем сравнения вектора распознавания с эталонными векторами по норме. 4. Разработаны схемы изменения размерности векторов распознавания с учетом иерархии эталонов, позволяющие идентифицировать отличительные особенности фрагментов контуров по экстремальным отклонениям от хорд и на этой основе уточнять идентификацию изображения в целом. Практическая ценность диссертационного исследования состоит в применимости предложенного метода для решения актуальных задач распознавания плоских изображений, в том числе распознавания печатных и рукопечатных символов в условиях искажений. Компоненты метода применимы для помехоустойчивого анализа формы изображений, выделения ключевых точек контуров и получения их топологических характеристик. Предложенный метод может служить основой для разработки параллельной системы распознавания контурно представленных растровых изображений с высоким быстродействием и практической устойчивостью к ограниченным искажениям контуров. Внедрение и использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» для выявления экстремумов числовых последовательностей при разработке алгоритмического обеспечения параллельной цифровой обработки гидроакустических сигналов и для разработки алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики в преподавании курсов «Информатика», «Теоретические основы информатики», «Информационные технологии в математике», «Теоретические основы нейроинформатики», «Архитектура нейрокомпьютеров», «Практикум решения задач на ЭВМ», что подтверждено соответствующими актами, приведенными в приложении 8 к диссертационной работе. Апробация работы. Основные результаты работы были представлены на I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г.); XI международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2005 г.); международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.); III всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2005 г.); Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» (Таганрог, ТГПИ, 2008 г.); IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2008 г.). Публикации. По материалам работы опубликовано 10 печатных работ общим объемом около 7 печатных листов, в том числе 2 статьи в журналах из перечня рекомендуемых ВАК РФ. Структура и объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы и восьми приложений. Основное содержание работы изложено на 182 страницах, включая список литературы из 172 наименований.

Похожие:

	Разработка и исследование методов распознавания объектов в массивах...		Урок по информатике по теме «Методика обучения сортировке одномерного массива» Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька;...
	Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики		Реферат: Шайдуров А. Г. Исследование и разработка некоторых графических... Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению...
	Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа		Разработка и исследование алгоритмов решения транспортных задач с... Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге
	Разработка алгоритмов поиска и обследования искусственных протяженных... Специальность: 05. 13. 18 – Математическое моделирование, численные методы и комплексы программ		Разработка и исследование методов определения видимости полигонов... Целью диссертации является разработка метода, который бы позволил отрисовывать сцены, геометрическая сложность которых, в настоящее...
	Программа элективного курса для учащихся 11 классов «Обработка изображений... Под «компьютерным художником» можно понимать любого, кто занимается созданием или редактированием изображений с помощью ЭВМ		Аннотация рабочей программы учебной дисциплины Технический рисунок... Знать способы оттенения контуров изображений и геометрических объектов; элементы светотени и светотеневого масштаба; последовательность...
	Методы и алгоритмы выделения контуров изображений в радиотехнических... Рабочая программа составлена на основании рабочего учебного плана по фгос утвержденного ученым советом юргту(нпи) протоколом №4 от...		Программа по формированию навыков безопасного поведения на дорогах... Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
	Реферат на тему «Проблема распознавания речи. Обзор алгоритмов и... Появление графического интерфейса, при котором отпала необходимость в знании человеком каких-либо команд, привела к повсеместному...		Разработка и исследование технологических основ процесса фотонностимулированного... Разработка и исследование технологических основ процесса фотонностимулированного локального анодного окисления наноструктур на основе...
	Программа элективного курса для учащихся 10-11 классов «Компьютерная... Под «компьютерным художником» можно понимать любого, кто занимается созданием или редактированием изображений с помощью ЭВМ		Отчет о научно-исследовательской работе, выполняемой по государственному... «Разработка алгоритмов для биоинформационного анализа комплексных метаболических и молекулярно-генетических сетей»