Заярный Виктор Вильевич разработка и исследование

Вид материала

Исследование

Содержание Общая характеристика работы Целью диссертационной работы Методы исследования Достоверность результатов Научная новизна Основные положения, выносимые на защиту Практическая ценность Внедрение и использование результатов работы. Апробация работы. Структура и объем работы. Содержание работы N данных выполняется за log В приложении Основной результат диссертационной работы Работа содержит следующие научные результаты Практическая ценность Основные публикации по теме работы

Подобный материал:

• Н. Я. Засядкович московский инженерно-физический институт (государственный университет), 24.19kb.
• Тематика курсовых работ Разработка программы маркетингового исследования. Разработка, 27.44kb.
• Разработка программы маркетингового исследования. Разработка спецификации на маркетинговое, 27.82kb.
• Левачков Василий Васильевич исследование, 142.51kb.
• Иванов Петр Алексеевич ввт-406 тудент группа т исследование, 71.44kb.
• Удк 504. 056: 574 разработка и исследование методов технического мониторинга химически, 331.8kb.
• Исследование закономерностей и разработка технологии окатывания медьсодержащих материалов, 378.14kb.
• Подпись, дата курсовой проект по дисциплине "Электротехника и электроника" Вариант, 209.55kb.
• Удк 621. 311 Разработка и исследование эффективности алгоритма централизованной системы, 54.48kb.
• Направление 2 Разработка, исследование и совершенствование методов расчета конструкций, 1050.14kb.

На правах рукописи   




Заярный Виктор Вильевич


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


Специальность:

05.13.17 – Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук


Таганрог 2009

Работа выполнена в ГОУВПО

«Таганрогский государственный педагогический институт».

Научный руководитель:	доктор технических наук, профессор Ромм Яков Евсеевич
Официальные оппоненты:	доктор технических наук, профессор Турулин Игорь Ильич
	кандидат технических наук, старший научный сотрудник Хади Роман Ахмедович
Ведущая организация:	Ростовский государственный университет путей сообщения (РГУПС)

Защита состоится « 3 » июля 2009 г. в 14.20 на заседании диссертационного совета Д 212.208.21 в Технологическом институте Южного федерального университета по адресу: ауд. Д-406, пер. Некрасовский, 44, г. Таганрог, Ростовская область, ГСП-17 А, 347928.


С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу:

344000, Ростов-на-Дону, ул. Пушкинская, 148.


Автореферат разослан « » 2009 г.

Ученый секретарь диссертационного совета Д 212.208.21 доктор технических наук, профессор

Чернов Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Одной из важнейших за­дач, возникающих в связи с созданием современных информа­ционных систем, является автоматизация процесса распознава­ния образов. Предмет распознавания образов объединяет ряд научных дисциплин. Их связывает поиск решения общей задачи выде­ления элементов, принадлежащих конкретному классу, среди мно­жества размытых элементов, относящихся к нескольким клас­сам. Под классом образов понимается некоторая категория, опре­деляемая рядом свойств, общим для всех ее элементов. На практике возникает необходимость распознавать объекты из разнообразных наборов данных (гидроакустические и радиолокационные сигналы, тепловизионные картины, оцифрованные изображения), что влечет целесообразность разработки и применения таких методов, с помощью которых можно выделить объекты произвольно определяемого, однако допустимого для исследуемого класса типа. В частности, целесообразна разработка алгоритмов, которые могут работать одновременно с оцифрованными сигналами и с их изображениями. Например, в медицинской диагностике актуальна задача выделения объектов на изображениях, полученных с помощью оцифрованных ультразвуковых сигналов. Широко распространены методы распознавания, основанные на анализе контурных представлений объектов: считается, что форма контуров является наиболее стабильным признаком при яркостных искажениях. Отсюда востребованы алгоритмы выделения контуров. Многие системы распознавания работают с априори выделенными объектами. В процессе применения таких систем необходимо решать задачу предварительного выделения объектов из окружающего информационного шума. Хорошо известны алгоритмы выделения объектов из бинарных изображений или из изображений, имеющих границу. При выделении объектов из набора не бинарных данных различного типа необходимо определять принадлежность данных текущему объекту. Требуемое определение можно выполнить на основе алгоритмов сортировки. Целесообразность сортировки обусловлена упорядоченностью обрабатываемых данных, исключением накопления вычислительной погрешности, – в основе сортировки лежат лишь операции сравнения, сортируемые элементы при этом не изменяются. Алгоритмы сортировки представляют актуальный объект исследования в различных направлениях информатики и вычислительной техники, с другой стороны актуально распознавание объектов среди оцифрованных данных и изображений текста низкого качества. В диссертации объединяются оба эти направления.

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

1. Найти видоизменение алгоритма заливки с затравкой на основе выбора затравок и определения принадлежности элемента объекту, идентификации границ объекта, – без изменения исходных данных, которое бы обеспечивало широту диапазона обработки, включающую оцифрованные гидроакустические сигналы и растровые изображения.
   
2. На основе общей функции принадлежности разработать однопроходный алгоритм построчной линейной заливки, обладающий качествами параллелизма, одновременности обработки всех объектов в темпе поступления строк, разрешением конфликтов в процессе заливки.
   
3. Разработать метод выделения объектов из оцифрованных данных гидроакустической локации на основе определения с помощью сортировки координат локальных максимумов, их линейной заливки для выделения объектов, позволяющий достоверно различать истинные и ложные объекты в условиях помех.
   
4. Обобщить применение алгоритма построчной линейной заливки на основе выделения данных, превышающих адаптивный порог, для одновременного выделения контуров всех объектов на изображениях.
   
5. Разработать модификации алгоритмов обработки данных применительно к локализации корней функций двух действительных переменных с построением наглядного отображения процесса и результата работы алгоритмов.
   
6. Выполнить программную реализацию алгоритмов обработки данных гидроакустической локации, выделения объектов на изображениях, локализации корней функций двух действительных переменных, оценить временную сложность и представить их сравнение с известными методами.
   

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

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

Научная новизна заключается в следующем:

1. Предложена модификация алгоритма заливки с затравкой на основе выбора затравок и определения принадлежности элемента объекту и идентификации границ объекта без изменения исходных данных. Модификация отличается от аналогов по построению, позволяет совмещать во времени перевод изображения в бинарную форму с выделением из него объектов.
   
2. Разработан алгоритм построчной линейной заливки при наличии общей функции принадлежности, отличающийся от известного алгоритма разметки связных областей параллелизмом и тем, что обработка объектов ведется по мере поступления строк, причем конфликты разрешаются посредством слияния объектов в процессе заливки. Алгоритм является однопроходным, позволяет вести обработку с высокой скоростью без дополнительной переразметки объектов.
   
3. Предложен метод выделения объектов из массива оцифрованных сигналов гидроакустической локации, который отличается построением признаков на основе определения локальных экстремумов с помощью сортировки и их линейной заливкой для выделения объектов. Метод позволяет с высокой степенью достоверности различать истинные и ложные объекты в условиях помех без применения известных схем фильтрации.
   
4. Показана возможность обобщенного применения алгоритма построчной линейной заливки для различного вида данных, превышающих адаптивный порог или сравнимых с его значением в окрестности текущего данного. В частности, возможно выделение контуров одновременно всех объектов на изображениях. От известных алгоритмов заливки бинарных изображений предложенное обобщение отличается построчным доступом к данным с выделением всех объектов строки, расширенными возможностями функции принадлежности и ускорением обработки изображения.
   
5. Разработаны модификации предложенных алгоритмов обработки данных для локализации корней функций двух действительных переменных, отличающиеся от известных по построению, наглядностью отображения процесса и результата работы алгоритмов.
   

Основные положения, выносимые на защиту:

1. Предложена модификация алгоритма заливки с затравкой на основе определения принадлежности элемента объекту и идентификации границ объекта без изменения исходных данных, отличающаяся общностью вида обрабатываемых данных в диапазоне от оцифрованных гидроакустических сигналов до растровых изображений.
   
2. Разработан однопроходный алгоритм построчной линейной заливки при наличии общей функции принадлежности, отличающийся параллелизмом, обработкой всех объектов по мере поступления строк, разрешением конфликтов путем слияния объектов в процессе заливки.
   
3. Предложен метод выделения объектов из массива оцифрованных сигналов гидроакустической локации, отличающийся построением признаков на основе координат локальных максимумов, определяемых с помощью сортировки и их линейной заливкой для выделения объектов, и позволяющий с высокой достоверностью различать истинные и ложные объекты в условиях помех без применения известных схем фильтрации цифровой обработки сигналов.
   
4. Показана возможность обобщенного применения алгоритма построчной линейной заливки для различного вида данных путем выделения значений данных, превышающих адаптивный порог, а также для одновременного выделения контуров всех объектов на изображениях.
   
5. Разработаны модификации предложенных алгоритмов обработки данных для локализации корней функций двух действительных переменных, отличающиеся построением и наглядностью отображения процесса, а также результатов работы алгоритмов.
   
6. Выполнена программная реализация алгоритмов обработки данных гидроакустической локации, алгоритмов выделения объектов на изображениях, локализации корней функций двух действительных переменных, даны оценки временной сложности предложенных алгоритмов в аспекте сравнения с известными методами.
   

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

Внедрение и использование результатов работы.

Полученные в работе результаты использованы: в ОАО «Таганрогский завод «Прибой» результаты приняты к использованию для создания расширенной библиотеки программ идентификации сигналов гидроакустической локации; результаты использованы в хоздоговорной НИР № 1 «Разработка методов и программного обеспечения для распознавания, классификации и идентификации малоразмерных зашумленных объектов», проводившейся на кафедре информатики ТГПИ с ОКБ «РИТМ» ТРТУ и завершенной в 2005 г.; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики результаты используются в преподавании курсов «Основы информатики», «Теоретические основы информатики», «Программирование», «Информационные технологии в математике», «Специальные разделы информатики».Внедрение результатов работы подтверждено соответствующими актами.

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

IV Всероссийская научно-техническая конференция «Современные методы и средства обработки пространственно-временных сигналов» (Пенза, 26 – 29 мая, 2006 г.).

Международная научно-техническая конференции «ММА-2006» "Математические модели и алгоритмы для имитациифизических процессов".

(Таганрог, 11 – 14 сентября, 2006 г.).

IX Международная научно-практическая конференция «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, 2-5 октября 2006 г.).

The Fourth International Conference Theoretical and Applied Aspects of Program Systems Development (TAAPSD’2007). (Ukraine, Berdyansk 4-9 September 2007).

IX Всероссийский симпозиум по прикладной и промышленной математике. Региональный макросимпозиум «Насущные задачи прикладной математики в Ставрополье» (Кисловодск, 1 – 8 мая 2008 г.).

Публикации. По материалам диссертационной работы опубликовано 12 печатных работ общим объёмом 14 печатных листов, в том числе две статьи в журнале из списка допущенных ВАК РФ.

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


СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Исходный список 6 2 4 7 1 3 8 5 Слияние в пары –––––– –––––– –––––– –––––– После 1-го этапа 2 6 4 7 1 3 5 8 Слияние пар в четверки –––––––––––– –––––––––––– После 2-го этапа 2 4 6 7 1 3 5 8 Слияние четверок в восьмерки –––––––––––––––––––––– После 3-го этапа 1 2 3 4 5 6 7 8 Рис. 1. Схема сортировки слиянием с возрастающим шагом

Временная сложность последовательной реализации такой сортировки имеет оценку T=O(N log₂N). В главе дан алгоритм этой сортировки, в приложении представлена реализация в последовательном варианте. Выполнен синтез параллельных алгоритмов сортировок слиянием. Параллельно сортируются на процессорах части последовательности, затем сливаются в выходную последовательность с оценкой временной сложности:

.

Предложена разновидность распараллелеливания сортировок на основе слияния с оценкой времени T(p) , .

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

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

Для использования алгоритмов заливки производится бинаризация изображений. Как правило, для заливки области изображения задаются:

заливаемая (перекрашиваемая) область,

код пикселя, которым будет выполняться заливка,

начальная точка области, начиная с которой выполняется заливка.

В отличии от этого для предложенного выделения объектов потребуется найти решение следующих проблем алгоритмического характера.

1) Сохранить сведения о каждом выделенном объекте, чтобы далее можно было обрабатывать их по отдельности.

2) Сохранять исходные данные без изменения при работе алгоритма заливки с затравкой.

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

4) Определить алгоритм принадлежности текущего элемента объекту (построить функцию принадлежности).

5) Определить те элементы, которые не могут быть затравкой.

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

Для решения проблемы