Разработка и исследование методов распознавания объектов в массивах оцифрованных данных на основе адаптивного порога и схем сортировки
Скачать 433.45 Kb.
|
На правах рукописи  Заярный Виктор Вильевич РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РАСПОЗНАВАНИЯ ОБЪЕКТОВ В МАССИВАХ ОЦИФРОВАННЫХ ДАННЫХ НА ОСНОВЕ АДАПТИВНОГО ПОРОГА И СХЕМ СОРТИРОВКИ Специальность: 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТдиссертации на соискание ученой степени кандидата технических наук Таганрог 2009 Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт».
Защита состоится « 3 » июля 2009 г. в 14.20 на заседании диссертационного совета Д 212.208.21 в Технологическом институте Южного федерального университета по адресу: ауд. Д-406, пер. Некрасовский, 44, г. Таганрог, Ростовская область, ГСП-17 А, 347928. С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148. Автореферат разослан « » 2009 г.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Одной из важнейших задач, возникающих в связи с созданием современных информационных систем, является автоматизация процесса распознавания образов. Предмет распознавания образов объединяет ряд научных дисциплин. Их связывает поиск решения общей задачи выделения элементов, принадлежащих конкретному классу, среди множества размытых элементов, относящихся к нескольким классам. Под классом образов понимается некоторая категория, определяемая рядом свойств, общим для всех ее элементов. На практике возникает необходимость распознавать объекты из разнообразных наборов данных (гидроакустические и радиолокационные сигналы, тепловизионные картины, оцифрованные изображения), что влечет целесообразность разработки и применения таких методов, с помощью которых можно выделить объекты произвольно определяемого, однако допустимого для исследуемого класса типа. В частности, целесообразна разработка алгоритмов, которые могут работать одновременно с оцифрованными сигналами и с их изображениями. Например, в медицинской диагностике актуальна задача выделения объектов на изображениях, полученных с помощью оцифрованных ультразвуковых сигналов. Широко распространены методы распознавания, основанные на анализе контурных представлений объектов: считается, что форма контуров является наиболее стабильным признаком при яркостных искажениях. Отсюда востребованы алгоритмы выделения контуров. Многие системы распознавания работают с априори выделенными объектами. В процессе применения таких систем необходимо решать задачу предварительного выделения объектов из окружающего информационного шума. Хорошо известны алгоритмы выделения объектов из бинарных изображений или из изображений, имеющих границу. При выделении объектов из набора не бинарных данных различного типа необходимо определять принадлежность данных текущему объекту. Требуемое определение можно выполнить на основе алгоритмов сортировки. Целесообразность сортировки обусловлена упорядоченностью обрабатываемых данных, исключением накопления вычислительной погрешности, – в основе сортировки лежат лишь операции сравнения, сортируемые элементы при этом не изменяются. Алгоритмы сортировки представляют актуальный объект исследования в различных направлениях информатики и вычислительной техники, с другой стороны актуально распознавание объектов среди оцифрованных данных и изображений текста низкого качества. В диссертации объединяются оба эти направления. Целью диссертационной работы является разработка и исследование компьютерных алгоритмов выделения объектов из набора данных различных типов на основе определения функции сравнения, отношения порядка элементов множества данных, их последующей сортировки и идентификации экстремумов в смысле сконструированного отношения. Выделение объектов на этой основе должно выполняться без предварительной фильтрации входной информации, в случае применения фильтрации работа конструируемых алгоритмов не должна ухудшаться. В случае бинарных данных требуется предложить альтернативный частный алгоритм, более эффективный, чем алгоритмы общей конструкции. Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
Методы исследования опираются на теоретические основы информатики, на методы прикладной информатики, на теорию сложности, используются алгоритмы сортировки, применяются современные информационные технологии, структурное и объектное программирование. Достоверность результатов вытекает из математического обоснования конструктивных алгоритмов выделения образов из исходных данных, подтверждается оценками временной сложности, а также результатами компьютерного моделирования и эксперимента. Научная новизна заключается в следующем:
Основные положения, выносимые на защиту:
Практическая ценность диссертационного исследования состоит в применимости предложенного метода для решения актуальных задач выделения объектов из различного вида данных, в том числе выделения символов из изображений низкого качества. Компоненты метода применимы для помехоустойчивого выделения объектов. Предложенный метод построчной заливки может служить основой для разработки параллельной системы выделения объектов из данных с высоким быстродействием. При условии построения соответствующей функции принадлежности в качестве объекта может рассматриваться контур изображения. Внедрение и использование результатов работы. Полученные в работе результаты использованы: в ОАО «Таганрогский завод «Прибой» результаты приняты к использованию для создания расширенной библиотеки программ идентификации сигналов гидроакустической локации; результаты использованы в хоздоговорной НИР № 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 данных выполняется за log2N этапов, без дополнительных сравнений для нахождения размера шага. При этом на каждом отдельном этапе шаг фиксирован, начиная с 1, затем удваивается при переходе к следующему этапу (рис. 1).
Временная сложность последовательной реализации такой сортировки имеет оценку T=O(N log2N). В главе дан алгоритм этой сортировки, в приложении представлена реализация в последовательном варианте. Выполнен синтез параллельных алгоритмов сортировок слиянием. Параллельно сортируются на  процессорах части последовательности, затем сливаются в выходную последовательность с оценкой временной сложности: .Предложена разновидность распараллелеливания сортировок на основе слияния с оценкой времени T(p)  , .В последовательном варианте одна из таких сортировок применяется для модификации алгоритма заливки с затравкой: модифицируется выбор затравок для заливки объекта с целью его выделения. Далее, с применением сортировки, в главе разрабатываются методы выделения объектов из массивов оцифрованных данных на основе заливки с затравкой и функции, определяющей принадлежность текущего элемента выделяемому объекту. Модификация подвергаются известные алгоритмы заливки с затравкой для изображений. Для использования алгоритмов заливки производится бинаризация изображений. Как правило, для заливки области изображения задаются: заливаемая (перекрашиваемая) область, код пикселя, которым будет выполняться заливка, начальная точка области, начиная с которой выполняется заливка. В отличии от этого для предложенного выделения объектов потребуется найти решение следующих проблем алгоритмического характера. 1) Сохранить сведения о каждом выделенном объекте, чтобы далее можно было обрабатывать их по отдельности. 2) Сохранять исходные данные без изменения при работе алгоритма заливки с затравкой. 3) Произвести выбор затравки для очередного объекта в условиях неопределенности информации об объекте. 4) Определить алгоритм принадлежности текущего элемента объекту (построить функцию принадлежности). 5) Определить те элементы, которые не могут быть затравкой. На рассматриваемом множестве данных всегда определено отношение порядка (), поэтому определены локально и глобально наибольшее, а также наименьшее значения, которые, с оговоркой относительно математической нестрогости, будут называться локальными и глобальными экстремумами, соответственно, максимумами и минимумами. Для решения проблемы пункта 1 строится связный список адресов точек объекта. При заливке какого-либо элемента его адрес заносится в соответствующий список. Для решения проблемы пункта 2 определяется множество (поверхность) признаков, такое, что каждому элементу сопоставляется свой набор признаков, соответственных его координатам (битовые признаки упакованы в формат одного байта, составляющего элемент набора). При этом в качестве признаков используются: необработанный элемент, затравка, объект, поглощенный элемент, контур. Под поглощенным понимается элемент, который не может быть затравкой или элементом нового объекта. При обработке данных изменениям подвергаются только признаки, сами данные не меняются. Идентифицирующие характеристики объектов определяются с использованием поверхности признаков для проверки принадлежности текущего элемента объекту. При решении проблем пункта 3 выбор затравки в общем случае зависит от вида задачи и вида используемых в ней данных. В большинстве случаев в качестве затравки можно выбрать локальный максимум. Для нахождения локального максимума определяется функция сравнения, зависящая от входных данных, которая обозначается fcmp(dann). Аргумент dann может быть как единственным текущим данным, так и множеством данных в некоторой его окрестности. Имея функцию сравнения, можно отсортировать данные по невозрастанию и найти локальные экстремумы. Первый элемент отсортированного массива – глобальный максимум, он же – первый из локальных максимумов, используемый в качестве первой затравки. Выбор других затравок тесно связан с пунктом 5 и будет рассмотрен ниже. Для работы алгоритма заливки с затравкой в соответствии с пунктом 4 определяется функция принадлежности текущего элемента выделяемому объекту fpr(dann). В качестве затравки взят локальный максимум local_max выделяемого объекта, функция принадлежности использует значение этого локального максимума. Вычисляется порог как доля локального максимума porog = D(local_max). Текущие данные, превышающие этот порог и примыкающие к ранее выделенным данным, принадлежат выделяемому объекту. Считается, что текущее данное принадлежит выделяемому объекту, если fcmp(dann) fcmp(porog). Функция принадлежности fpr(dann), помимо этой проверки, может дополнительно выделять внешний контур объекта. Под этим понимаются данные, примыкающие к ранее выделенным элементам объектов, но не удовлетворяющие пороговому соотношению. Составляется связный список координат этих элементов. Используя поверхность признаков, можно исключить повторяющиеся элементы из этого списка. В соответствии с пунктом 5, выделив очередной объект, требуется выбрать затравку для следующего объекта.
На рис. 2 представлен пример выделения объектов по значению порога. Порог изображен как доля (часть) текущего локального максимума. Здесь ордината f(x1) – максимум (объект 1), x2 – нижняя граница объекта 1, x3 – верхняя граница объекта 1, f(x4) – первый минимум, f(x5) – второй минимум, f(x6) – локальный максимум (объект 2), x7 – нижняя граница объекта 2, x8 – верхняя граница объекта 2, f(x9) – третий минимум. Объектом считается множество точек, прилегающих к затравке, и не меньших порога. Здесь затравки – это локальные максимумы (f(x1) и f(x6)), порог – ордината максимума объекта, умноженная на пороговый коэффициент (Р1 = f(x1)*K; Р2 =f(x6)*K). Значение коэффициента K зависит от вида задачи. Бинаризация данных происходит совместно с заливкой, поскольку значение порогов вычисляется по мере выделения каждого из объектов. Значение f(x2) больше значения локального максимума f(x6), но его следует пропустить. Чтобы не взять точку x2 в качестве затравки, необходимо отметить точки, не принадлежащие никаким объектам (поглощенные точки). На рис. 2 эти поглощенные точки принадлежат интервалам (x4, x2), (x3, x5) для объекта 1, (x5, x7), (x8, x9) – для объекта 2. Для идентификации поглощенных точек необходимо написать программную функцию их определения, используя в качестве затравок точки контура объекта. Такая подпрограмма-функция именуется функцией поглощения. В отсортированном массиве с помощью признаков и с учетом отметки поглощенных элементов выбирается первый необработанный элемент. Этот элемент и будет очередным локальным максимумом и искомой затравкой. Таким образом, для выделения каждого объекта необходимо следующее. 1. Выбирается точка локального максимума в качестве затравки и выделяется объект путем заливки с помощью функции выделения, на поверхности признаков отмечаются точки объекта. Задача решается с помощью следующей подпрограммы (Delphi): function FP_InObj( X, Y :LongInt):LongInt;//Проверяем точку на принадлежность к объекту (Возвращает 0, если точка принадлежит объекту, иначе 1) var Out1 : LongInt; begin Out1 := 1;// до проверки - точка не принадлежит объекту if ArPr[Y+1,X+1] = Pr_0 then begin FP_InObj := Out1; exit; end; if ArPr[Y+1,X+1] = Pr_NeProver then ArPr[Y+1,X+1] := Pogl_Zatrav; if (ArDann[Y+1,X+1] >= Form1.Porog) and // для Max (ArPr[Y+1,X+1] <> Pr_XMax) and (ArPr[Y+1,X+1] <> POGLOSHEN)then Out1 := 0 // точка принадлежит объекту Else //точка не принадлежит объекту, но примыкает к нему (контур) Begin // запоминаем затравку поглощения new(pPogl1); // новая точка контура объекта pPogl1^.pNext := PogAll.points; pPogl1^.x := X; pPogl1^.y := Y; PogAll.points := pPogl1; inc(PogAll.NNpoints); end; FP_InObj := Out1; end; 2. В том случае, когда по условиям задачи априори заданы радиусы окрестностей локализации объектов, локализованная окрестность объекта на поверхности признаков отмечается как поглощенная (эти элементы не могут быть взяты в качестве затравок). 3. Перебором точек контура объекта или точек границ локализованной окрестности как затравок, с использованием функции поглощения, при помощи заливки выделяются и отмечаются на поверхности признаков поглощенные точки. Отличительная особенность способа – совмещение во времени перевода данных в бинарную форму с выделением из них объектов. Если в качестве данных рассматривать значения функции двух переменных, а в качестве объектов минимумы, максимумы или корни, то на основе изложенной схемы локализуются (идентифицируются) все локальные экстремумы и нули. В общем случае осуществлен перенос определения локальных числовых экстремумов на произвольное множество, в котором задано отношение порядка, и при помощи сортировки элементов по заданному отношению локализуются аналоги экстремумов в смысле данного отношения. На этой основе построено выделение объектов, что составляют часть распознавания образов на основе сортировки. Далее в главе предложена конструкция алгоритма линейной заливки, которая используется в том случае, если функция принадлежности едина для всех объектов. В отличие от разметки связных областей путем последовательного сканирования, предлагаемый алгоритм обрабатывает все объекты текущей строки и сливает получаемые объекты в процессе работы, не требуя постобработки. Производится заливка одновременно всех объектов в текущей строке. Для такой заливки выделяются отрезки текущей строки, принадлежащие объектам, затем они связываются с ранее выделенными объектами путем нахождения объектов предыдущей строки, соприкасающихся с отрезками объектов текущей строки. Данные обрабатываются построчно, исключено повторное обращение к каждому отдельному элементу данных. Алгоритм может быть преобразован для работы с несколькими процессорами. Ниже более формально описывается последовательный алгоритм. В модуле, вызывающем выделение объектов, необходимо определить функцию, FInObject, проверяющую, принадлежит ли точка объекту. Эта функция зависит от задачи. Например: // --- Функция проверяет, принадлежит ли точка объекту ---- Function FInObject (var StrFlObj:TStrPix; X: LongInt ) : Boolean; begin //Pr_XOblMax =16; - X область Max Extremum FInObject := (StrFlObj[X] > 2)and (StrFlObj[X] < 128); end; Здесь StrFlObj – строка данных, X – индекс строки. В модуле, реализующем рассматриваемый алгоритм, создаются следующие три подпрограммы: создание объекта CreateObjInList, добавление данных к объекту AddCoordObj, слияние объектов Slil2Obj. Каждый объект выделяется в виде связного списка адресов данных. Вводятся два массива индексов объектов размером в длину строки: массив MOld номеров объектов предыдущей строки и массив MNew номеров объектов текущей строки.
Рассмотрим алгоритм на примере диаграммы (рис. 3), где строка 1 – массив MOld с номерами объектов, строка 2 является текущей. Штрихом отмечены данные, определенные функцией принадлежности как принадлежащие объектам. Подмножество последовательных данных обозначается Lin (начальная точка, конечная точка). При обработке Lin (1, 2) вызывается процедура CreateObjInList, поскольку Lin (1, 2) не имеет в предыдущей строке соседних объектов. CreateObjInList создает новый объект 4, заносит в него точки из Lin (1, 2) и заносит номер объекта в массив MNew. При обработке Lin (4, 4) вызывается процедура AddCoordObj, поскольку Lin (4, 4) имеет в предыдущей строке один соседний объект с номером 1, AddCoordObj добавляет к объекту 1 точки Lin (4, 4) и заполняет массив MNew. При обработке Lin (6, 8) вызывается процедура Slil2Obj, поскольку Lin (6, 8) имеет в предыдущей строке несколько соседних объектов. Процедура Slil2Obj сливает объект 3 с объектом 2, очищает объект 3, заменяет в MOld и MNew номер объекта 3 на 2, добавляет к объекту 2 точки из Lin (6, 8) и заполняет массив MNew. При переходе к следующей строке массив MNew копируется в MOld, затем очищается. После обработки всего массива данных из списка объектов удаляются пустые объекты. Предложенный алгоритм быстрее алгоритма заливки с затравкой за счет однократного обращения к каждому элементу данных и допускает распараллеливание. Целесообразно его применение для обработки данных с использованием адаптивного порога. В приложении к главе 1 дана полная программная реализация изложенного алгоритма для 8-битных оцифрованных сигналов, там же приведена программа для работы с изображениями на основе изложенного алгоритма. Приведение данных к виду, удобному для обработки алгоритмом линейной заливки, может выполняться с помощью построения адаптивного порога (модификация алгоритма адаптивной бинаризации для изображений). То же можно выполнить путем обработки входных данных фильтром нижних частот, фильтром «размытие» и т. п. В обоих рассмотренных в главе алгоритмах используется представление выделенных объектов в виде списка адресов отрезков строк, принадлежащих объекту. Это позволяет легко объединять объекты при слиянии без дополнительной перезаписи. При необходимости можно восстановить объект, либо преобразовать к виду, требуемому для дальнейшей программной обработки. При линейной заливке данные обрабатываются по взаимно независимым строкам, возможна параллельная обработка, в рамках которой необходим контроль за объединением построчно выделенных объектов. При обработке достаточен доступ к одной строке данных, допустимо хранение данных на внешнем носителе с последовательным доступом, можно обрабатывать данные по мере поступления с датчиков. Алгоритм линейной заливки может применяться для выделения объектов в бинарных изображениях (буквы, рисунки, отпечатки пальцев), для обработки тепловизионных отображений (выделение областей одинаковой температуры, областей превышающих или не достигающих определенного порога), а также в тех случаях, когда данные с помощью дополнительной обработки (сравнение с адаптивным порогом) приведены к бинарному виду. С помощью адаптивных порогов оба предложенных алгоритма применимы для выделения объектов с различными характеристиками, включая изображения плохого качества, гидроакустические данные и др. Во второй главе излагается применение охарактеризованных алгоритмов главы 1 для решения задачи распознавания объектов по оцифрованным сигналам гидроакустической локации. Выделение объектов реализовано в два этапа: первый – строится поверхность признаков объектов, точки которых заданы координатами X, Y; второй этап – на этой поверхности выделяются объекты с помощъю линейной заливки. Выделенным объектам на поверхности признаков соответствуют амплитуды их элементов. Вслед за тем вычисляются характеристики выделенных объектов. Характеристики образцов объектов принимаются в качестве эталонов. На данной основе формируется список допустимых границ характеристик для целевых объектов. Выделенные объекты, характеристики которых попадают в допустимые границы, считаются распознанными целевыми объектами.
Конкретно, с учетом специфики объектов гидроакустики, разработаны специальные алгоритмы выделения объектов и вычисления их характеристик. Пример такого алгоритма представляет | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | Разработка и исследование алгоритмов распознавания изображений на... | | Доклад ронжина Андрея Леонидовича по диссертационной работе «Разработка... «Разработка адаптивного метода робастного понимания слитной речи на основе интегральной обработки данных», представленной на соискание... |
| Разработка и исследование моделей поведения динамических объектов... Специальность: 05. 13. 18 – Математическое моделирование, численные методы и комплексы программ | | Разработка и исследование методов определения видимости полигонов... Целью диссертации является разработка метода, который бы позволил отрисовывать сцены, геометрическая сложность которых, в настоящее... |
| Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики | | Разработка и исследование распределенной подсистемы конструкторского... Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге |
| Программа bde administrator 28 Обязательной является разработка вопросов системного анализа объектов проектирования, оптимизации и выбора наилучших вариантов решений,... | | Тема: «Системы распознавания текста» Цели урока Цели урока: дать учащимся представление об orc – программах распознавания текста, познакомиться с возможностями данных программ |
| Разработка методов и аппаратурных средств лазерно-информационной... | | Разработка методов и средств анализа и диагностирования объектов... |
| Отчет о научно-исследовательской работе «Разработка методов и средств... «Разработка методов и средств информационной поддержки образовательных процессов с применением перспективных технологий передачи... | | Урока информатики по теме «Табличные базы данных». (Открытый урок.) Данный урок «База данных. Системы управления базами данных» является первым уроком по теме «Технологии хранения, поиска и сортировки... |
| Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа | | Рефераты №3 (2012 г.) Разработка, исследование и реализация методов совершенствования теплообменных аппаратов турбоустановок |
| Проекта Разработка моделей социальных явлений с помощью методов интеллектуального анализа данных | | Исследование методов информационной защиты баз данных в социально-экономической сфере Казанский национальный исследовательский технический университет им. А. Н. Туполева |
