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

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

З^р^—

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

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

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

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

АВТОРЕФЕРАТ

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

13 щз'а ^

Таганрог 2009

003472813

Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт».

Научный руководитель: доктор технических наук,

профессор Ромм Яков Евсеевич

Официальные оппоненты: доктор технических наук,

профессор Турулин Игорь Ильич

кандидат технических наук, старший научный сотрудник Хади Роман Ахмедович

Ведущая организация:

Ростовский государственный университет путей сообщения (РГУПС)

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

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «19 » 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 данных выполняется за log2N этапов, без дополнительных сравнений для нахождения размера шага. При этом на каждом отдельном этапе шаг фиксирован, начиная с 1, затем удваивается при переходе к следующему этапу (рис. 1).

Исходный список 6 12 4 17 1 13 8 |5

Слияние в пары

После 1-го этапа 2 16 4 17 1 13 5 18

Слияние пар в четверки

После 2-го этапа 2 | 4 | 6 | 7 1 13 Is |8

Слияние четверок в восьмерки

После 3-го этапа 1 12 |3 14 | 5 |6 | 7 |8

Рис. 1. Схема сортировки слиянием с возрастающим шагом

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

Т (p)¿{N/pxlog¡(N/p) + 2N)x .

Предложена разновидность распараллелеливания сортировок на основе слияния с

Nloe N los2 N оценкой времени Т(р) <-—— + —^—, р = const.

Р 2

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

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

подвергаются известные алгоритмы заливки с затравкой для изображений.

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

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

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

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

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

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

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

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

При решении проблем пункта 3 выбор затравки в общем случае зависит от вида задачи и вида используемых в ней данных. В большинстве случаев в качестве затравки можно выбрать локальный максимум. Для нахождения локального максимума определяется функция сравнения, зависящая от входных данных, которая обозначается fcmp(dann). Аргумент dann может быть как единственным текущим данным, так и множеством данных в некоторой его окрестности. Имея функцию сравнения, можно отсортировать данные по невозрастанию и найти локальные экстремумы. Первый элемент отсортированного массива - глобальный максимум, он же - первый из локальных максимумов, используемый в качестве первой затравки. Выбор других затравок тесно связан с пунктом 5 и будет рассмотрен ниже. Для работы алгоритма заливки с затравкой в соответствии с пунктом 4 определяется функция принадлежности текущего элемента выделяемому объекту Jpr(dann). В качестве затравки взят локальный максимум local max выделяемого объекта, функция принадлежности использует значение этого локального максимума. Вычисляется порог как доля локального максимума porog = D(local_max). Текущие данные, превышающие этот порог и примыкающие к ранее выделенным данным, принадлежат выделяемому объекту. Считается, что текущее данное принадлежит выделяемому объекту, если fcmp(dann) ä fcmpfporog). Функция принадлежности Jpr(dann), помимо этой проверки, может дополнительно выделять внешний контур объекта. Под этим понимаются данные, примыкающие к ранее выделенным элементам объектов, но не удовлетворяющие пороговому соотношению. Составляется связный список координат этих элементов. Используя поверхность признаков, можно исключить повторяющиеся элементы из этого списка. В соответствии с пунктом 5, выделив очередной объект, требуется выбрать затравку для

следующего объекта.

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

Здесь ордината fixi) - максимум (объект 1), Х2~ нижняя граница объекта 1, Xj -верхняя граница объекта 1, J[xt) - первый минимум, J[xs) - второй минимум,,/(%) - локальный максимум (объект 2), xi - нижняя граница объекта 2, xg- верхняя граница объекта 2, flxg) - третий минимум.

Объектом считается множество точек, прилегающих к затравке, и не меньших порога. Здесь затравки - это локальные максимумы (j[xi) и J[xè)\ порог - ордината максимума объекта, умноженная на пороговый коэффициент (Pi =J[xi)*K; Р2 =/[Хб)*К}. Значение коэффициента /Г зависит от вида задачи.

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

Значение больше значения локального максимума/^), но его следует пропустить. Чтобы не взять точку х2 в качестве затравки, необходимо отметить точки, не принадлежащие никаким объектам (поглощенные точки). На рис. 2 эти поглощенные точки принадлежат интервалам (х*, xj), fo, xi) для объекта 1, (х5, Х7), (xs, х9~) - для объекта 2.

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

Такая подпрограмма-функция именуется функцией поглощения.

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

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

1. Выбирается точка локального максимума в качестве затравки и выделяется объект путем заливки с помощью функции выделения, на поверхности признаков отмечаются точки объекта. Задача решается с помощью следующей подпрограммы (Delphi):

function FP_InObj( X, Y :LongInt):LongInt;//Проверяем точку на принадлежность к объекту (Возвращает 0, если точка принадлежит объекту, иначе 1) var Outl : Longlnt; begin .

Outl := 1;// до проверки - точка не принадлежит объекту if ArPr[Y+l,X+l] - Pr_0 then begin FP_InObj := Outl; exit; end; if ArPr(Y+l,X+l ] = Pr_NeProver then

ArPr[Y+l,X+l) := Pogl_Zatrav; if (ArDann[Y+l,X+l] >= Forml.Porog) and // для Max

(ArPr:Y+l,X+l] <> Pr_XMax) and (ArPr[Y+l,X+l] о POGLOSHEN)then Outl ;<= 0 / / точка принадлежит объекту Else //точка не принадлежит объекту, но примыкает к нему (контур) Begin // запоминаем затравку поглощения new(pPogll); // новая точка контура объекта pPogll".pNext PogAll.points; pPogll'.x X; рРод11Л.у У;

PogAll.points :=• pPogll; inc(PogAll.NNpoints); end;

FP_InObj Outl ; end;

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

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

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

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

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

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

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

Алгоритм может быть преобразован для работы с несколькими процессорами.

Ниже более формально описывается последовательный алгоритм.

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

// — Функция проверяет, принадлежит ли точка объекту----

Function FInObject (var StrFlObj:TStrPix; X: Longlnt ) : Boolean; begin //Pr_XOblMax =16; - X область Max Extremum

FInObject := (StrFlObjtX] > 2)and (StrFlObj[X] < 128); end;

Здесь StrFlObj - строка данных, X - индекс строки.

В модуле, реализующем рассматриваемый алгоритм, создаются следующие три подпрограммы: создание объекта CreateObjlnList, добавление данных к объекту AddCoordObj, слияние объектов Slil20bj. Каждый объект выделяется в виде связного списка адресов данных. Вводятся два массива индексов объектов размером в длину строки: массив MOld номеров объектов предыдущей строки и массив MNew номеров объектов текущей строки.

Рассмотрим алгоритм на примере диаграммы (рис. 3), где строка 1 - массив МОИ с номерами объектов, строка 2 является текущей. Штрихом отмечены данные, определенные функцией принадлежности как принадлежащие объектам. Подмножество последовательных данных обозначается Lin (начальная точка, конечная точка). При обработке Lin (1,2) вызывается процедура CreateObjlnList, поскольку Lin (1,2) не имеет в предыдущей строке соседних объектов. CreateObjlnList создает новый объект 4, заносит в него точки из Lin (1,2) и заносит номер объекта в массив MNew. При обработке Lin (4,4) вызывается процедура AddCoordObj, поскольку Lin (4,4) имеет в предыдущей строке один соседний объект с номером 1, AddCoordObj добавляет к объекту 1 точки Lin (4,4) и заполняет массив MNew. При обработке Lin (6, 8) вызывается процедура Slil20bj, поскольку Lin (6,8) имеет в предыдущей строке несколько соседних объектов. Процедура Slil20bj сливает объект 3 с объектом 2, очищает объект 3, заменяет в MOld и MNew номер объекта 3 на 2, добавляет к объекту 2 точки из Lin (6, 8) и заполняет массив MNew. При переходе к следующей строке массив MNew копируется в MOld, затем очищается. После обработки всего массива данных из списка объектов удаляются пустые объекты.

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

В приложении к главе 1 дана полная программная реализация изложенного алгоритма для 8-битных оцифрованных сигналов, там же приведена программа для работы с изображениями на основе изложенного алгоритма.

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

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

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

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

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

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

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

Выделенные объекты, характеристики которых попадают в допустимые границы,

считаются распознанными целевыми объектами.

4 4 Г) и 0 0 (1 0 9 3 0 0 0 0

4 о л п 0 п 0 п (1 п п

0 д 0 4 4 (1 0 0 4 о 11 (1 п (1 п

0 а Д 4 4 0 п 4 0 п 0 0 Г) 0 0 п п 0 п 4 п п

0 4 <1 4 п 4 0 <\ Л с Л п а а 0 4 0 с 4 4 0

4 { П 4 .1 0 п п п 0 п 4 * Г) 4 4 п 4

П 0 197 Г) п 4 п 0 0 11 п 4

4 () 0 14- 0 «? 4 4 п 4 4 п о р 4

4 п 0 9 4 0 0 0

и п П 147 ш 4 о 4 п 0 4

.4- 0 _0_ л. с, 4 ш * ш «п 14-4П -4- -1 4 0 4 0. _0 0 0_

т т4 — 7Г 7 0 "Т п ¥ т "о" "о" 0 п" т

1Й? 4 о 0 п 0 п л о 4 п (1 п 0 п П 0 п 4 п п п

эМ п о 4 0 п П п п (1 п п

0 п 4 (1 4 1) 4 4 4 4 1 0 0

36 0 11 0 п 4 П 4 4 11 п 0

1 п 0 9 с Р п 0 0 0 0 п Р 1 П 0 0 0 9 (1

р а 0 а п Г, л п п п п 0 0 0 1 а 0 0 п (1 г 11 п

0 0 п п п о п 0 п л п 0 п п 1 л 0 0 0 и 0 п п

3 л п п 0 и п п п п п 0 п 0 1 п 0 п 0 п п п и

0 0 п 0 0 0 о п 0 (1 0 0 0 п 0 о п 0 4 а п п 0

0 0 0 0 п 4 0 11 п 0 0 0 0 п п 0 п п п

0 (1 п п 0 п 4 г р с 0 о 0 0

4 п л п П (1 п 0 0 п 0 0 п 4

0 .1 0 д 0

"; в*"?!

Гор. •ЯП т 00* № 105 ч* щ •ЙР «ж« -жн 35. 1 1 Щ ! пе Й ем Щ

7 3 7 5 п 7 3 3 1 5 ? 3 . 4 1 л | 3 0

1П 3 5 ? 5 0 5 7 к 4 2 0 0 ь 0 л 3 п

11 3 п п 1 Я 7 7 0 л 4 п 0 п 4 л п

ч 3 г, 3 1 (1 3 3 6 0 л 0 3 0 2 I 0 0 2 2 п Г)

з ■ ч 1 о П 1 а Ч 1) п

в 1 ; 2 7 3 4 ч 3 ? 1 Г) 1 0 0 ? (1 1 4 ? 3 0

ч 7 3 ч Я 7 7 3 ? 0 1 0 2 3 п 2 3 з 0

р 7 к к 11 10 11 Я 10 ь г> 1 п 0 4 1 л 1 3 л 4 1

0 7 7 ч 11 10 14 13 12 11 7 3 } 1 5 ? 1 0 1 1 0 К 1

Г) к 1 я п 18 17 13 15 6 5 э Б 1 0 0 0 0 3 1

2 7 10 я д

к 10 1? 11 18 1$ И 7 / 0 0

7 11 4 Й 4 7 Я 14 15 14 8 7 1 4

в 1? 1 я 10 11 7 5 II п 0 2 6 Г. п

я 0 п 1 1 19 В г. я п п 4 1 8 0

7 1 3 1 3 3 4 3 4 1 7 л 11 0

5 1 4 3 1 0 0 ? 4 1 Ь 0 6 0 0 1

3 7 (1 я 1 3 0 1 4 0 ? 1 3 ? л 1 1 1

1 5 0 3 0 1 п 2 5 1 4 7 0 2 5 С 1 3 0 1

п 3 0 п п 0 ? 3 0 0 2 0

п 3 п д 9 0 1 ? 2 В Ч 1 1 1 0 1 1 1

0 3 ¡1 0 0 1 о 0 ? 1 7 1? 3 0 4 р л п ? 0

1 ? д 0 (1 1 1 4 0 К 17 5 0 2 ¡1 а 5 л Г)

? 1 г. ? п 3 6 1 4 Я ^ ? л

? п ? п ? К ? ? 7 л 1 л 1 ? '

п ? 0 п 1 п п 1 г> 1 ? 7 7 (1 4 л ? 1 П 1 л 0

лТг ' {

Рис. А. Пример поверхности признаков с выделенными объектами

Рис. 5. Пример амплитуд выделенных объектов

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

Алгоритм 1.

1. Определяются локальные экстремумы (максимумы) гидроакустических сигналов.

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

3. Определяются характеристики объектов для сравнения с эталонными значениями.

3.1. Размеры объекта в посылках Ногг8)ге и Уа^ге, где Ног^ге - размер объекта по оси ОХ, УеЛ^ге - размер объекта по оси О К;

3.2. Отношение размера области объекта по горизонтали к размеру по вертикали НоггУег1Яа(га,

НоггУепКаПо = ЯогеЯге/Кег/Зке;

3.3. ОЬ^ЕпуЯаПо - отношение суммы амплитуд области объекта к сумме амплитуд его окружения в прилегающей контурной полосе малого размера («объект/окружение»)

Л

ОЫЕМок^АтрЮкг^

)

где I - индекс точки объекта, ^ Лтр1ш - сумма амплитуд к-го объекта, ^ АтрЮкг-

' 1 сумма амплитуд окружения к-го объекта;

3.4. Гладкость (равномерность) поверхности объекта, характеризуемая отношением Рк, равным разности суммы максимумов и суммы минимумов на к-м объекте, деленным на сумму максимумов, -

-г-,

где ^ тахЛ - сумма амплитуд выделенных максимумов А-го объекта, ^Г - сумма / / амплитуд выделенных минимумов к-го объекта, (чем ближе к нулю рк, тем более гладко отражает звук поверхность к-го объекта).

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

Помимо характеристик, представленных для примера в п. 3, вычисляется полный набор из нескольких десятков (в зависимости от типа целевых объектов) характеристик, В полном виде набор представлен в рассматриваемой главе и в диссертационном приложении к этой главе.

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

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

Нтл= Я'*~Я-*"' , н — м

max i mini

где Hllc - i-я характеристика к-го объекта, Нт1к - приведенная к единому масштабу /-я характеристика ¿-го объекта, #„,„,- нижняя граница /-Й характеристики объекта, Hmmi-верхняя граница i-й характеристики объекта.

Интегральная характеристика:

Gt=£Hml,

i

где G, - квадрат расстояния до центра характеристик для к-го объекта.

При необходимости можно ввести веса учитываемых характеристик, однако в данной работе все характеристики имели одинаковый вес.

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

а б в

Рис. 6. Пример обработки файла входных сигналов а - необработанный сигнал; б - выделенные объекты; в - целевой объект

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

Полный список характеристик, а также программная реализация изложенного метода, выполненная в Delphi, без сокращений (около 220 стр.), даны в приложении к главе 2. На рис. 6 иллюстрируется отображение последовательных этапов выделения и идентификации целевого объекта, выполненных с помощью методов данной главы.

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

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

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

Рис. 7. Фрагмент изображения текста плохого качества

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

Пример изображения текста низкого качества с градиентным изменением яркости

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

Для иллюстрации возможностей обоих предложенных алгоритмов это изображение обрабатывается модифицированным алгоритмом заливки с затравкой с использованием конкретной функции принадлежности, приведенной выше при изложении содержания главы 1. Это же изображение обрабатывается линейной заливкой с использованием адаптивного порога. Полученные объекты в обоих случаях переводятся в графический формат. Исходное изображение и оба восстановленных изображения поступают на вход программы FineReader 6.0. Сравнение результатов показывает преимущество использования предварительного выделения объектов разработанными методами. На рис. 8 результат обработки изображения, представленного на рис. 7, непосредственно по программе FineReader 6.0 - без предварительного выделения объектов предложенными методами.

up позволяет выполнять \,-копирование или создание образа жесткого диска. Easy CD/DVD Recor-, *ит для записи компакт-дисков. CO-ROM Emulator помогает запускать программы (преимущественно игры), ленящиеся скопировать все необходимые файлы на жесткий диск и вынуждающие постояннп при) ин.пп.ныи СО в дисководе. Разумеется, все эти утилиты работают под управлением Windows, которую можно установить за дополни н.чп. ную плату, как и прение программные иные опции

В придачу вам полагаюп новая сумка для транспортировки и' мышка цвета «стеле* (матовая темно-серая).

гаться с новым GMA900. Особенно озадачило о к

тем более что в комплект

входит г o-VideoHaRCA. а внутри стоит большая дик .щеомоста (возмо-бы не 1

на, хватило бы места для ИЛИ ХОТЯ

<абыть обо I

для тех.

__крышкой

Рис. 8. Распознавание исходного изображения программой FineReader 6.0

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

{¡»up позволяет выполнять розеромос ¡¿копировании или создании образа У^жосйого диска; Easy CO/DVD Rocor-dor служит для записи компакт>дис-Кг.'ков) CO-ROM Emulator помогает запу- «-"■'V-Г*-.' -"«i-i". ■ Ш екать программы (преимущественно йбы'разъет.доя joto"последующей ШЖЕсли забыть обо всех недочетах/« «хноутбук^будет.-интересен для тех,? ¡Рктоне-.боится'делать^модерниза-/ ft циюйпод «одной с общей.'; крышкой ■ ¡¿спрятаны все компоненты v- от про-? J&ueccopa до батареики CMOS-памяД; .up позволяет выполнять резервное .. . копирование или создание образа ■ жесткого диска, Easy CD/DVD Recor-. ' der служит для записи компакт-дисков, CD-ROM Emulator помогает запу-екать,программы, (преимущественно ;. игды),у ленящиеся скопировать.: все

' бы;, разъема для. его последующей" ■Лустановки).■i'.'■:jp~Ф■ .люутбук^ .':KTOi:Hö ;боцтся, делать.людерниза;: у ЦИЮ! ■"■=. ПОД-. ОДНОЙ. .;0бщейi: крышкой' ^спратанЬгвсегШ^^ .:|дессорад0батграйкиСМОЗ-памя-

Рис. 9. Обработка изображения методом заливки с затравкой до удаления шумов Рис. 10. Обработка изображения методом линейной запивки с учетом адаптивного порога до удаления шумов

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

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

После дополнительного удаления помех на основе соответственной им малой разницы между минимальной и максимальной амплитудой восстановленное изображение подается на распознавание на вход программы FineReader 6.0. Результат распознавания представлен на рис. 9.

Up позволяет выполнять резервное копирование или создание образа жесткого диска. Easy CD/DVD Recorder служит для записи компакт-дисков, CO-ROM Emulator помогает запускать программы (преимущественно игры), ленящиеся скопировать все необходимые файлы на хесткий диск и вынуждающие постоянно держать оригинальный СО в дисководе. Разумеется, все зга утилиты работают под управлением Windows, которую можно установить за дополнительную плату, как и П[ючие программные и аппаратные опции.

В придачу вам полагаются нейлоновая сумка для транспортировки и попноразморная оптическая мышка цвета «стеле» (матовая темно-серая).

гаться с новым GMA900. Особенно озадачило отсутствие интерфейса S-Video, тем более что в комплект входит перех дниксбЛЛйеонаПСА, а внутри стоит большая дискретная плата ведеомоста (возможно, если бы не такое раст чительство пространства, хватило бы места для беспроводного адаптера или хотя бы разъема для его последующей установки).

Если забыть обо всех недочетах, ноутбук будет интересен для тех, кто не боится делать модернизацию: под одной общей крышкой спрятаны все компоненты*- от про-цессора

до батарейки CMOS-памя-_

Рис. 11. Распознавание изображения, обработанного по методу модифицированной заливки с затравкой программой FineReader 6.0.

Очевидно, восстановленное изображение значительно улучшено.

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

В главе даны, помимо того, примеры обработки изображения с качеством, более низким, чем на рис. 7, - после трехкратного пропуска через фильтр «размытие». При попытке распознавания такого изображения с помощью программы FineReader 6.0 изображение автоматически переворачивается, результат не имеет ничего общего с исходным текстом. Обработка по методу модифицированной заливки с затравкой для такого изображения также дала неудовлетворительный результат. В то же время применение модифицированного алгоритма линейной заливки с использованием адаптивного порога привело к распознаванию с некоторым количеством ошибок, однако существенно лучшим, чем распознавание необработанного изображения.

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

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

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

Функция принадлежности для внутренних контуров объектов записывается в виде: // Внутренний контур

Function FKont9InObj (var StrFlObj:TArPix; Y, X: LongI:it ) : Longlnt;

var fOut: Longlnt;

begin

fOut -1;

if (StrFlObj [Y,X]-\I >= 0 then

begin // окружение объекта //внутри

if ((StrFlObj[4-1,X-l}-1) < 0)or ИStrFlObj < 0)or

((StrFlObj[Y-1,X+1J-1) < 0)or((StrFlObj[Y ,X-1]-1) < 0)or ((StrFlObj[Y ,X+ll-1) < 0!or((StrFlObj(Y+1,X-1]-1) < 0)or ((StrFlObj(Y+1,X]-1) < 0)or((StrFlObj[Y+1,X+1]-1) < 0) then

fOut StrFlObj[Y,X]~1; end;

FKont8InObj := fOut; end;

Результат выделения контуров внутри изображенного на рис. 7 объекта после его троекратного размытия приводится на рис. 12.

ПОЗВОЯЯОТГ • шшолнт^. рмсрш'ооо:;

-■кошроозимо ,'ипм ешдшшо; "образо; »сепсого дтека» Бвду CD/OW Rocor-'j ;'oer..записей ктлюот°дие->;; З'ко®. СО°ШМ &iulai6ir пммшг залу»)

;;йфы), т лемвщиоея.' ё«ого<|Юва?ь'.- ос©1

; бы • рз'змгш; для" ота;:. псдоеду&щой .^гаис^

Бспи забш&!обо всо« йодочого«»"^ : йру»бук; б^ОТ^ИМТС^

.спрятаны псо ;-!

ц№мраУ'до.:батареПш 'jpMOS-na.MRvi

Рис. 12. Пример выделения внутренних контуров без выделения объектов

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

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

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

01234567390123456789012345678901234567890123456789012345678901234567090123456789

веевевэеаэееэеаевазвееаевэаввеаайеееЕавеввэевееееевеаваеавэаеаэвваевееэееееееейе

-~q4ertvuiopnasdlghjlcl; ' zxcvbrro, ./0®ЕНТП110Р( > ASOTGHJKl,: "ZXCVBNHo

вввеавеевееевеееэвваавввайавваевеедваеввевавввевваевеееаеадеввеееаеввввеввеаевеа евзееаеавеаэвааввеввэавеевавйееаввевввевваееееееавеавйавававвввевайваайааевееваэ

Рис. 13. Фрагмент тестового изображения. Ниже строки повторяются (всего 58 строк).

Для алгоритма линейной запивки при сравнении не требовалось никакой модификации. В табл. 1 приведено сравнение времени работы предложенных алгоритмов с алгоритмом заливки с затравкой, встроенным в систему Delphi (FloodFill).

Таблица 1

Время обработки данных с помощью модификации алгоритмов заливки с затравкой, ли-

нейной заливки и заливки с затравкой Delphi 7 FloodFill)

Рисунок для заливки - линейная заливка для 4-связных объектов линейная заливка для 8-связных объектов | модифицированный алгоритм заливки с затравкой для 4-связных объектов модифицированный алгоритм заливки с затравкой для 8-связных объектов заливка с затравкой Delphi 7 (FloodFill)

Компьютер - AMD Athlonflm) 64X2 Dual 4200+, 2.00 Гб ОЗУ

рис. 13 (701x960) 35996 объектов за 31 мс. 4734 объектов за 47 мс. 35996 объектов за 63 мс. 4734 объектов за 63 мс. 453 мс.

рис. 13 негатив (701x960) 4589 объектов за 94 мс. 25 объектов за 63 мс. 4589 объектов за 234 мс. 25 объектов за 250 мс. 547 мс.

рис. (гл. 3) (800x1170) 6404 объектов за 78 мс. 6300 объектов за 78 мс. 6404 объектов за 109 мс. 6300 объектов за 109 мс. 109 мс.

рис. (гл. 3) негатив (800x1170) 3161 объектов за 93 мс. 3161 объектов за 93 мс. 3161 объектов за 281 мс. 3135 объектов за 313 мс. 578 мс.

рис. 9 без помех (486x1361) 974 объектов за 16 мс. 950 объектов за 31 мс. 974 объектов за 47 мс. 950 объектов за 62 мс. 31 мс.

рис. 12 (486x1361) 9493 объектов за 15 мс. 7860 объектов за 31 мс. 9493 объектов за 47 мс. 7860 объектов за 62 мс. 141 мс.

Компьютер - Intel(R) Pentium(R)D CPU 3.4 GHz 1.00 ГБ ОЗУ

рис. 13. (701x960) 35996 объектов за 31 мс. 4734 объектов за 46 мс. 35996 объектов за 47 мс. 4734 объектов за 63 мс. 578 мс.

рис. 13 негатив (701x960) 4589 объектов за 94 мс. 25 объектов за 63 мс. 4589 объектов за 156 мс. 25 объектов за 157 мс. 390 мс.

рис. (гл. 3) (800x1170) 6404 объектов за 46 мс. 6300 объектов за 62 мс. 6404 объектов за 78 мс. 6300 объектов за 78 мс. 172 мс.

рис. (гл. 3) негатив (800x1170) 3161 объектов за 78 мс. 3135 объектов за 79 мс. 3161 объектов за 187 мс. 3135 объектов за 188 мс. 375 мс.

рис. 9 без помех (486x1361) 974 объектов за 16 мс. 950 объектов за 16 мс. 974 объектов за 47 мс. 950 объектов за 47 мс. 31 мс.

рис. 12 (486x1361) 9493 объектов за 31 мс. 7860 объектов за 32 мс. 9493 объектов за 32 мс. 7860 объектов за 47 мс. 156 мс.

Из табл. 1 видно, что линейная заливка меньше зависит от числа и вида выделяемых объектов по сравнению с алгоритмами заливки с затравкой. Линейная заливка во всех случаях оказалась быстрее известного алгоритма заливки с затравкой.

Для объектов простого вида программа Delphi FloodFill работает быстрее, чем предложенный модифицированный алгоритм заливки с затравкой.

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

В заключении обобщаются основные результаты диссертационной работы, харак-

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

В приложении приводится программная реализация предложенных алгоритмов обработки изображений (около 4,5 п.л.), модуль сортировки слиянием (1 п.л.), программа для обработки гидроакустической информации (около 9 п.л.), а также значения эталонных характеристик и параметров гидроакустических объектов. Общий объем приложения к диссертационной работе - 338 стр.

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

Работа содержит следующие научные результаты

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

1. Ромм Я.Е., Заярный В.В. О погрешности параллельных вычислений и ее структурном ограничении. I / Таганрог: ТРТИ, 1987. 26 с. Деп. в ВИНИТИ 26.05.87, № 3779-В87. (Лично автора - 0,75 п.л.).

2. Ромм Я.Е., Заярный В.В. О погрешности параллельных вычислений и ее структурном ограничении. II / Таганрог: ТРТИ, 1987. 12 с. Деп. в ВИНИТИ 26.05.87, № 3781-В87. (Лично автора - 0,3 п.л.).

3. Ромм Я.Е., Заярный В.В. О погрешности параллельных вычислений и ее структурном ограничении. III / Таганрог: ТРТИ, 1987. 18 с. Деп. в ВИНИТИ 26.05.87, № 3780-В87. (Лично автора - 0,4 п.л.).

4. Ромм Я.Е., А.И. Дордопуло, В.В. Заярный. Программная локализация нулей многочленов с приложением к идентификации объектов по данным гидроакустической локации / Научное издание; Таганрог: Изд-во Таганрог, гос. пед. Института. - 2005. - 217 с. (Лично автора - 3 п.л.).

5. Ромм Я.Е., Заярный В.В. Идентификация объектов по данным гидроакустической локации на основе сортировки / В кн.: Сборник статей IV Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов». - Пенза: НОУ «Приволжский Дом знаний».- 2006. - С. 94 - 96 (26 - 29 мая 2006 г. Пенза). (Лично автора - 0,07 пл.).

6. Ромм Я.Е., Заярный В.В. Программная идентификация объектов при обработке гидроакустических сигналов / В кн.: Материалы Международной научно-технической конференции «ММА-2006»"Математические модели и алгоритмы для имитациифизиче-ских процессов". Т 1. Физико-математические и физико-технические модели и алгоритмы для имитациифизических процессов (11-14 сентября, 2006 г. Таганрог, Россия). -С. 326 - 328. (Лично автора - 0,07 п.л.).

7. Ромм Я.Е., Заярный В.В. Компьютерная идентификация малоразмерных объектов при обработке гидроакустических сигналов / В кн.: Научные труды IX Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики»; книга «Информатика», Москва 2006, МГУПИ. - С. 98 - 104 (2-5 октября 2006 г. Москва). (Лично автора - 0,3 п.л.).

8. Заярный В.В., Боженюк A.B. Предварительная обработка сигналов для распознавания образов // Известия ТРТУ 2007. - №1. - С. 227 - 229. (Лично автора - 0,1 п.л.).

9. Ромм Я.Е., Заярный В.В. Компьютерная идентификация объектов при обработке сигналов с приложением к данным гидроакустической локации и обработке изображений / Таганрог: ТРТИ, 2007. 29 с. Деп. в ВИНИТИ 20.07.07 № 751-В2007. (Лично автора-0,7 п.л.).

10. Ромм Я.Е., Заярный В.В. Компьютерная обработка сигналов и идентификация объектов / В кн.: The Fourth International Conference Theoretical and Applied Aspects of Program Systems Development (TAAPSD'2007). - ABSTRACTS (Ukraine, Berdyansk 4-9 September 2007). - pp. 87-92. (Лично автора - 0,4 п.л.).

11. Ромм Я.Е., Заярный В.В. Компьютерная обработка сигналов гидроакустической локации и идентификация объектов растровых изображений // Системы управления и информационые технологии, 2007, №4.2(30). - С. 290-295. (Лично автора - 0,3 п.л.).

12. Ромм Я.Е., Заярный В.В. Выделение объектов в двумерном массиве оцифрованных сигналов // Обозрение прикладной и промышленной математики. - Т. 15. - Вып.З. - С. 473 - 474. (Лично автора - 0,05 п.л.).

Все включенные в диссертацию результаты получены лично соискателем.

Соискатель О* .------Заярный В.В.

Подписано к печати 2 7 Собьем 1,1 уч.-юд.л.

Тип.ТТИ ЮФУ Заказ № 2С2л\лр.1СС экз.

Введение.

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

1.1. Синтез параллельных сортировок с применением схем слияния и оценки их временной сложности.

1.1.1. Параллельная сортировка с видоизменением слияния для постоянного количества процессоров.

1.1.2. Параллельная сортировка с постоянным количеством процессоров.

1.1.3. Последовательное слияние по матрицам сравнений.

1.2. Использование алгоритма заливки с затравкой для выделения объектов из набора данных.

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

1.4. Построчный линейный алгоритм выделения объектов на основе связности объектов соседних строк.

1.5. Примеры работы алгоритма линейной заливки для различных топологий связности данных.

1.5.1. Пример алгоритма линейной заливки для 4-связных данных

1.5.2. Пример алгоритма линейной заливки для 8-связных данных

1.5.3. Пример алгоритма линейной заливки для 6-связных данных

1.6. Модификация алгоритма 1.2 для параллельной обработки данных

1.7. Построение адаптивного порога для обработки данных.

1.8. Назначение, область и применения выделения объектов модифицированными алгоритмами заливки с затравкой и линейной заливки.

1.9. Выводы.

Глава 2. Распознавание объектов по оцифрованным сигналам гидроакустической локации.

2.1. Постановка задачи.:.

2.2. Схема обнаружения, распознавания, классификации и идентификации объектов на основе сортировки и локализации экстремумов.

2.3. Алгоритм автоматического программного распознавания малоразмерных объектов по данным гидроакустической локации.

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

2.4.1. Выделение заиленных объектов.

2.4.2. Выделение объектов больших размеров.

2.5. Выводы.

Глава 3. Выделение объектов на оцифрованных изображениях.

3.1. Постановка задачи.

3.2. Особенности выделения объектов из оцифрованных изображений низкого качества.

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

3.4. Пример обработки нечеткого (размытого) изображения низкого качества методом линейной заливки при наложении адаптивного порога с учетом временной сложности.

3.5. Сравнительные оценки временной сложности обработки изображений с помощью предложенных модификаций метода заливки с затравкой и линейной заливки.

3.6. Примененние линейной заливки для нахождения корней функции двух переменных.

3.7. Выводы.

Актуальность проблемы. В настоящее время обработка информации занимает существенную часть научно-технических исследований во всех сферах деятельности. Актуальна потребность в развитии и совершенствовании информационных систем, информация — ключевой элемент процесса принятия решений [78], количество разнохарактерной и сложной информации растет. Одной из важнейших задач при создании современных информационных систем является автоматизация процесса распознавания образов. Акты распознавания разделяют на два основных типа [78]: распознавание конкретных объектов и распознавание абстрактных объектов. В диссертации исследуется распознавание первого типа. К пространственным образам относят символы, отпечатки пальцев, синоптические карты, гидроакустическую информацию, физические объекты и рисунки. В разряд временных образов входят речь, переменные сигналы, электрокардиограммы, характеристики цели и временные ряды. В задачах распознавания образов можно выделить два основных направления: изучение способностей к распознаванию, которыми обладают человеческие существа и другие живые организмы, и развитие теории, а также методов, предназначенных для решения отдельных задач распознавания образов в определенных прикладных областях. Первое направление связано с такими дисциплинами, как психология, физиология и биология, второе же имеет дело в первую очередь с техникой, компьютерами и информатикой. Во всех случаях необходимо предварительно выделить образы из окружающего информационного шума. Предмет распознавания образов объединяет ряд научных дисциплин; их связывает поиск решения общей задачи — выделить элементы, принадлежащие конкретному классу, среди множества размытых элементов, относящихся к нескольким классам. Под классом образов понимается некоторая категория, определяемая рядом свойств, общим для всех ее элементов. Но предварительно необходимо получить это множество размытых элементов, выделить его из всего набора исходных данных. Образ — это описание любого элемента как представителя соответствующего класса образов. В случае, когда множество образов разделяется на непересекающиеся классы, желательно использовать для отнесения этих образов к соответствующим классам какое-либо автоматическое устройство. Такая классификация образов может выполняться операторами, возможно, с применением компьютеров. Некоторые задачи распознавания оператор не в состоянии решить самостоятельно.

Примером служит выделение из множества морских сигналов и шумов тона подводной лодки посредством анализа гидроакустических сигналов. [22, 34, 75].

При необходимости для распознавания применяются алгоритмы цифровой обработки сигналов (ЦОС).

Алгоритмы ЦОС. ЦОС широко применяется в различных областях науки и техники, включая биомедицину, акустику, гидролокацию, звуковую локацию, радиолокацию, сейсмологию, связь системы передачи данных, ядерную технику и др. Обрабатываются одномерные и многомерные сигналы, необходимые, например, для анализа сейсмических данных при разведке нефти, при измерениях силы землетрясений и контроле ядерных взрывов [44, 46]. В основном используются цифровая фильтрация и спектральный анализ, которые могут выполняться дискретно на специализированных или универсальных машинах, а также непрерывно с помощью аналоговых вычислительных машин. В процессах фильтрации нижних частот или полосовой фильтрации, при дифференциации, интерполяции и сглаживании, отдают предпочтение описанию сигналов в частотной области. К цифровым фильтрам относятся фильтры с конечной- импульсной характеристикой (КИХ) и фильтры с бесконечной импульсной характеристикой. (БИХ). КИХ-фильтром — называют фильтр, у которого импульсная характеристика представляет собой конечный дискретный сигнал (N -точечный дискретный сигнал). БИХ-фильтром - называют фильтр, у которого импульсная характеристика может принимать отличные от нуля значения на бесконечном множестве. В случае, когда представляемая последовательность имеет конечную длительность, т.е. имеет только конечное число ненулевых значений, используется ДПФ (дискретное преобразование Фурье). ДПФ есть преобразование Фурье последовательности конечной длины, являющееся само по себе также последовательностью, а не непрерывной функцией, которое соответствует равноудаленным по частоте выборкам преобразования Фурье-сигнала. Спектральный анализ можно проводить путем вычисления спектров с помощью ДПФ или с применением статистических методов. На практике при спектральном анализе, как правило, используются БПФ (быстрое преобразование Фурье) и основанная на нем методика вычисления быстрой свертки. Существует несколько алгоритмов ЦОС;, для которых необходимы одни и те же основные операции: свертка, корреляция, фильтрация, преобразования и модуляция.

Для двух заданных последовательностей конечной длины jc(/t) и h{k) с длиной iV, и N2 соответственно линейная свертка равна у(п) = h(n) <S> = Jh(k)x(n= £h(k)x(n-к), n = 0,1,., (M-1),

4 = -® 4=0 где M = Nx + N2 - 1. Для двух заданных последовательностей и у(к) длины N с нулевыми средними значениями оценка их взаимной корреляции равна рг„(и) =-/7ч . , п = 0, ±1, ±2,., где rrv(«) - оценка взаимной ковариант [гх№Л°)-/V ности, определяемая как гху(п) =

Т7 «=0,1,2,. N

4 = 0 Л' + n-l

У х{к-п)у(к), п= 0,-1,-2, N

1,(0)-^ ZWt)]1.

•<* 4=0 N 4=0

Оценка автокорреляции рхх{п) последовательности длины N с нулевым \ Гхх{П) / \ средним значением задается как р (п)=—^-г, п = 0, ±1, ±2,., где гхх\п) г, ДО) дгд:'

J N-n-l оценка автоковариантности, - гхх{п) = — ^х(/с)х(/с + «), п =0,1, 2,.

N 4 = 0

Уравнение для фильтрации с конечной импульсной характеристикой имеет

ЛГ-л-1 вид: у{п) - ^h(k)x(n-k), где и у(к) - соответственно вход и выход фильтра, а

4=0 h(k), к = 0, 1,., N-1 - коэффициенты фильтра.

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

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

Анализ непрерывных (аналоговых) линейных стационарных систем в случае нулевых начальных условий при частотном подходе выполняется в последовательности [50]: с помощью прямого преобразования Фурье определяют спектр X('j со) входного сигнал x(t); умножением спектра X(j<s>) на комплексный коэффициент передачи системы H(jcо) находят спектр выходного сигнала y(t ):Y( j а>)- F{ y(t)} = X( j to )H( jco); с помощью обратного преобразования Фурье функции Y(ja>) вычисляют реакцию y(t) системы на воздействие x(t) .

Сравнение спектров непрерывных x(t) и дискретных х[п] сигналов позволяет выявить их общие свойства и различия. Общим является то, что периодические сигналы описываются рядами Фурье, а непериодические - преобразованиями Фурье. Спектры периодических сигналов - дискретные линейчатые, расстояние между спектральными линиями определяется частотой повторения сигнала. Спектральная плотность непериодического аналогового сигнала x(t) представляет собой непрерывную функцию частоты со, а спектр дискретного сигнала х[п] - периодическую функцию частоты со с периодом, равным частоте дискретизации т„=27с/д=2те/7\

Анализ дискретных линейных стационарных систем в случае нулевых начальных условий при частотном подходе выполняется в последовательности [50]: с помощью прямого ДПФ определяют спектр Х(к) входного сигнала х[п], (n = 0,N-\); умножением всех компонент спектра Х(к) на комплексный коэффициент передачи системы для соответствующих частот находят спектр выходного сигнала у[п]: Y(k) = X(k)H 2я Л J

NT , k = 0,N-l)\ с помощью обратного ДПФ функции Y(k) вычисляют реакцию у[п] системы на воздействие х[п].

С созданием специализированных и параллельных компьютеров увеличивается эффективность использования математических преобразований. К числу главных среди них принадлежат преобразования Фурье, Уолша и Хаара. Областями применения этих преобразований являются системы управления и связи. Находят применение специализированные непрерывно работающие устройства, к числу которых относятся, например, сверхбыстродействующие фурье-процессоры на поверхностных акустических волнах. Существует множество применяемых для данных целей преобразований. Преобразование Винограда-Фурье [1,4,9] и алгоритм первоначального множителя [1,9] представляют собой оригинальные, но сложные методы повышения скорости вычисления БПФ. Дискретное косинус-преобразование целесообразно для сжатия данных. В рамках преобразования Уолша сигнал раскладывается на прямоугольные импульсы, а не на синусоиды, и преобразование вычисляется быстрее, чем БПФ. Преобразование Адамара, построенное с помощью перестановки последовательности Уолша, вычисляется еще более быстро. Преобразование Хаара полезно для определения краевых элементов при обработке изображений [10].

1. Дискретное косинус-преобразование по сути представляет собой действи

N-1 klun N к =0, 1, ., N-1. тельную часть ДПФ: Хс(к)= Re [х (fc)]= хп cos п = 0

2. Дискретное преобразование Уолша [32] основано на наборе гармонических прямоугольных импульсов, которые называются функциями Уолша WAL{n,t) (/ — время, п - порядок). Четные функции WAL(2k, t) записываются как CAb(k, t), а нечетные функции WAl(2k+\,t) записываются как SAL(2k+\,t), где к=\, 2,N/2-l. Любую функцию /(/) можно разложить по набору функций

N/2-1 N/2-1

Уолша: f(t)=a0lVAL(0, ()+ J] J] [a, SAL (/,/) + b, CAL(j, /)], где а, и bj - коэффициенты ряда. *

3. Преобразование Адамара (Уолша-Адамара) - это преобразование Уолша, но с другим порядком функции Уолша и, следовательно, строк матрицы преобразования. Получающаяся при такой перестановке матрица Адамара содержит под-массивы матриц второго порядка. Например, матрицу Адамара порядка 8x8 можно записать через матрицы 2# =

1 1" "-1 -Г и - 2Н =

1 -1 -1 1

Любую матрицу Адамара порядка 2N можно рекурсивно получить из гН как N тт N тт ' 2N тт И И lNH -ЫН

4. Вейвлетное преобразование предоставляет средства для анализа нестационарных сигналов [86]. Вейвлетное преобразование применяется также для фильтрации сигналов, устранения шумов, определения местонахождения сингулярностей и их распределения. В вейвлетном преобразовании в качестве весовых коэффициентов значений сигнала выступают вейвлетные функции. Все вейвлетные функции получаются из основной (материнской, базовой) вейвлетной функции. Например, морлетовская, или модифицированная гауссова материнская вейвлетная функция вейвлет Морле) [86] е~'1/2, Фурье-образ которой -Я(ш)=л/2^<Г((0~Шо)1/2.

Остальные (дочерние) функции получаются путем такого изменения масштаба материнской, чтобы образовалось семейство функций. Каждую дочернюю функцию можно записать как -^^{(/-т^а}, где а - переменный коэффициент масштабиро

Ыа вания, т — константа переноса.

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

В литературе по распознаванию образов, включающей учебные пособия [27, 39, 53], статьи [29, 77], другие издания [42, 43, 47, 78, 83], фактически не сообщается, по каким алгоритмам выделены объекты из наборов данных. В некоторых задачах, например, при распознавании спама, объекты заведомо выделены. Однако обычно мы имеем набор входных данных, в котором объекты необходимо сначала выделить, а только потом распознать. Многие сообщения, относящиеся к выделению объектов [5, 12, 37, 76] носят декларативный характер и не содержат конкретных алгоритмов. В публикациях, описывающих работу со стандартными пакетами программ [70], алгоритмы также не приводятся. В отдельных работах, относящихся к конкретным задачам, помимо распознавания образов, описаны и методы выделения объектов. Об этом говорится, например, в материалах по обработке изображений [40, 51, 85], в статьях [26, 48, 52, 81, 87], в трудах Сойфера [72 - 74], в некоторых публикациях об обработке геологической информации [28], а также контуров изображений [36]. Известные методы преобразования полутоновых изображений в бинарные приводятся в [8]. Методы выделения объектов кратко приведены в [18]. В [73] даны процедуры обработки изображений, заключающиеся в их препарировании: изображение преобразуется к виду, который, возможно, далек от естественного, но удобен для визуальной интерпретации или компьютерного анализа. Многие операции препарирования осуществимы при помощи специальных поэлементных преобразований. Частным случаем препарирования является пороговая обработка [18, 73]. Перечислим некоторые другие используемые преобразования.

Очевидным обобщением пороговой обработки является преобразование ярко-стного среза (рис. 1а). Оно позволяет выделить определенный интервал диапазона яркостей входного изображения. Перемещая «рабочий» интервал по шкале и меняя его ширину, можно произвести визуальный анализ отдельных изображенных объектов, различающихся по яркости. Детали, не попадающие в указанный интервал, то есть относящиеся к «фону», будут подавлены. На рис. 1G приведен вариант ярко-стного среза с сохранением фона. В данном случае изображение в цел ом, сохраняется, но на нем «высвечиваются» участки, попавшие в заданный интервал яркостей. Если этот интервал примыкает к границе шкалы яркости, то получаем преобразование так называемой неполной пороговой обработки (рис. Г). а & в г д е ж з и

Рис. 1. Преобразования яркостного среза Контрастное масштабирование в своем простейшем варианте совпадает по смыслу с линейным контрастированием: «рабочий» интервал яркостей растягивается на весь диапазон допустимых значений (рис. Г). В других случаях контрастное масштабирование может быть связано с обращением функции яркости, то есть получением «негатива» (рис. 1д), представлением «рабочего» интервала яркостей на однородном фоне: черном (рис. Iе), белом (рис. 1Ж) или сером (рис. I3) и т. д.

Пилообразное контрастное преобразование иллюстрирует рис. Iй. Как показывает практика, если изображение состоит из нескольких крупных областей с медленно меняющимися (по плоскости) значениями яркости, то такое преобразование почти не разрушает целостности его восприятия и в то же время резко увеличивает контрастность плохо различимых мелких деталей. Более подробно пилообразное преобразование рассмотрено в [19, 49]. Преобразование используется для выделения характерных признаков, кодирования изображений, представления постепенного изменения яркости вдоль строки изображения. Его особенности: среди базисных векторов имеется вектор с одинаковыми компонентами; наклонный базисный вектор монотонно убывает от максимального до минимального значения скачками постоянной величины; матрица преобразования обладает секвентным свойством; существует быстрый алгоритм преобразования; обеспечивается высокая степень концентрации энергии изображения. Исходная для рассматриваемого преобразования матрица второго порядка:

2 2

1 1 1 -1 Матрица преобразования четвёртого порядка [19,49]:

S4=R ал

Ьл а.

1 0

-а4 К

0 -1

К «4

X ! О

2 I

--Iо где R может принимать значения или -Д= а4 и Ъ4 — действительные коэффицил/2 л/4 енты, которые следует выбирать так, чтобы матрица S4 была ортогональной, а величина скачков при изменении второго наклонного базисного вектора - постоянной. Из условия постоянства величины скачка можно найти [19,49], что а4 = 2Ъ4. Из условия ортогональности S4S\ -1, следует, что Ъ4 . Таким образом,

1 1 1 1 з/л/5 \/45 -l/V5 -З/л/5

1-1-1 1

-з/л/5 з/л/5 —l/л/5

Матрица 54 является ортонормальной. Кроме того, она обладает секвентным свойством: число изменений знака возрастает с увеличением номера строки от 0 до 3. Матрица пилообразного преобразования при N = 8 имеет вид:

5°~л/2

1 0 0 0 1 0 0 0"

8 bs 0 0 -«8 0 0

0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1

0 1 0 0 0 -1 0 0

-Л «8 0 0 Ь* «8 0 0

0 0 1 0 0 0 -1 0

0 0 0 1 0 0 0 -1 s4о'

Как и при построении матрицы S4, коэффициенты подбираются так, чтобы наклонный базисный вектор убывал равномерными скачками, все строки матрицы являлись ортонормальными векторами, матрица обладала секвентным свойством.

Путем обобщения получается рекуррентная формула, связывающая матрицы пилообразного преобразования iV-ro и (Л72)-го порядка: где 1К - единичная матрица К-го порядка. Постоянные aN и bN можно найти из п = 1,2,. По определению пилообразное преобразование записывается как d(n) = s(n)-x(n), где dt(n) = [Z)(o)Z)(l).£)(A^ -1)] - вектор коэффициентов пилообразного преобразования; JSfr(A^) = [x(o)Ar(l).Jir(A^-l)] - вектор входной последовательности, a S(n) - пилообразная матрица размером (NxN).

В отличие от известных подходов излагаемая работа посвящена выделению объектов из всей совокупности данных, при этом она строится не на цифровой обработке, а на применении алгоритмов сортировки, линейной заливки и заливки с затравкой. С целью выделения объектов, прежде всего, следует рассмотреть вопрос, чем конкретное входное данное (текущее данное), принадлежащее какому-либо объекту, отличается от данных, не принадлежащих этому объекту. В некоторых задачах для определения принадлежности текущего данного к объекту необходимо сравнивать текущее данное с соседними, где соседство — мера близости — определяется с помощью метрики [38]. Алгоритм идентификации принадлежности текущего данного к объекту зависит от вида (типа) данных. Такой алгоритм должен быть реализован в виде функции принадлежности рассматриваемого данного объекту и в дальнейшем именуется просто функцией принадлежности. Функция принадлежности индивидуальна для каждой задачи, но для многих задач можно использовать типовые процедуры выделения объектов. При обработке исходных данных необходимо принять во внимание, что шумовые значения амплитуд сигналов могут быть отфильтрованы не только методами ЦОС, но и альтернативными рекуррентных соотношений: а2 = 1, bN методами. В частности, вариациями радиуса окрестности локального экстремума могут быть поглощены амплитуды шума. Именно такой путь был выбран в диссертациях [31, 79, 80]. В излагаемой диссертационной работе предпринята попытка выделения объектов также на альтернативной основе — по экстремальным признакам амплитуд входных сигналов. Такая основа предпочтительна тем, что в ее границах входные сигналы не искажаются вычислительной обработкой.

В качестве нетривиальных задач выделения объектов можно интерпретировать некоторые задачи вычислительной математики. Например, если в качестве входных данных рассматривать дискретизированные значения функций, то можно применить методы выделения объектов для локализации экстремумов и нулей этих функций. Известные методы вычисления нулей полиномов и функций [2 Г, 71] направлены на уменьшение количества вычислительных операций, они хорошо разработаны для функций одной переменной; Функция двух переменных сводится к функции J(r0+at) = (p(f) [31]. Однако не все функции, можно обрабатывать этими методами. С развитием мощностей компьютеров можно использовать метод общего поиска — вычислить все значения функции в заданном интервале с заданным шагом (шаг в окрестностях подозрительных точек можно уточнять по мере необходимости) и найти экстремумы и корни функции за приемлемое время. Метод можно применить для произвольной функции одной и двух переменных [23, 54, 55], см. также [62 - 69]. Если рассматривать дискретизированные значения функции как набор данных, то экстремумы и корни этой функции можно считать объектами, подлежащими выделению. Отличие данных объектов от прочих очевидно - экстремумы различимы путем непосредственного сравнения с соседними значениями данных, а в корне значение функции равно нулю.

Подобное соединение задач распознавания и задач численной оптимизации исследовано в [31]. Соединение задач распознавания со спецификой вычисления особенностей функции (например, вычетов) и нулей с учетом кратности проработано в [79]. Синтетическое соединение алгоритмов распознавания и поиска представлено в [20].

Таким образом, задача распознаваниями, в частности, выделения «объектов оказывается тесно связанной с задачами построения конструктивных вычислительных и поисковых алгоритмов.

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

I. Сортировка [25, 35] является одной из основных процедур нечисловой обработки данных, которая широко используется в задачах, связанных с информационно-поисковыми системами, системами распределения ресурсов и др. Сортировка применяется, чтобы обеспечить эффективную обработку (например, поиск) в больших наборах данных; представить массивы данных в форме, удобной для анализа; группировать элементы по некоторому признаку; строить гистограммы распределения данных и др. Часто важно иметь одни и те же данные, отсортированные по различным ключам. Поскольку данные обычно являются записями, которые значительно длиннее ключей, при сортировке используют массивы индексов, позволяющие обращаться к исходным данным в нужном порядке.

Следующий пример иллюстрирует смысл применения сортировки. Пусть A[l. N] — массив данных. Mind i - один из m массивов индексов MInd l .MInd m для упорядочения массива данных А в различном отношении. Пусть размер индексных массивов совпадает с размером массива данных А. Для неотсортированного массива значения массива индексов Mind Л [i] = i, а порядок обращения к данным с помощью индексного массива- A[Mindl[i]].

Если массив данных упорядочен в некотором отношении, (например, по возрастанию) с помощью массива индексов Mind2, то Mind2 содержит индексы в таком порядке, что A[Mind2[i]] <= A[Mind2[i+l]] для любого i от 1 до N-1.

С помощью массива Mind3 массив данных может быть упорядочен по убыванию. С помощью массива Mind4 массив может быть упорядочен по какому-либо другому ключу из исходного массива А. Таким образом, с помощью массивов индексов мы можем иметь в различном порядке отсортированные исходные данные, причем сами исходные данные не подвергаются никаким перестановкам.

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

Во всех внешних сортировках используются внутренние сортировки.

Классификация основных методов сортировки представлена на рис. 2.

Рис. 2. Классификация основных методов сортировки

Временная сложность последовательных алгоритмов будет измеряться количеством последовательных шагов их выполнения. В частности, временная сложность последовательной сортировки измеряется числом выполняемых сравнений и перестановок данных [25, 35]. Заметим, что в излагаемой работе вместо перестановок данных будут использоваться перестановки индексов в индексных массивах и следует учитывать, что хотя порядок оценки времени сортировок сохранится, по сравнению с приведенными в [25, 35] оценками время сравнения данных увеличится, а время перестановок уменьшится. Для параллельных алгоритмов временная сложность будет оцениваться на модели неветвящихся параллельных программ без учета обмена. В частности, временная сложность параллельной сортировки будет оцениваться количеством последовательных сравнений с использованием обозначения T(R) = кхЬт, где хЬт- время бинарного сравнения, к - количество последовательных сравнений, R, - число используемых процессорных элементов. Приближенно временная сложность представляется в обозначениях T{r)=o{ / ), где o(f) - класс функций, растущих не быстрее / [35], точнее, 0(f)/f< с= const V /.

Важным качеством сортировок является наличие в них устойчивости - сохранения порядка записей с одинаковыми ключами [25, 35]. К числу устойчивых относятся, например, сортировка вставками (однако, если место вставки определяется с помощью бинарного поиска, эта сортировка может быть неустойчивой). К числу неустойчивых сортировок относятся корневая, пирамидальная, быстрая. В* [61] предложены параллельные модификации известных сортировок, при которых они приобретают устойчивость. Ниже приводятся наиболее типичные примеры сортаровок [25, 35].

Сначала упомянем о простых алгоритмах сортировки с квадратичной оценой времени выполнения. Это сортировка вставками (включением) [25, 35], пузырьковая сортировка (обменом)[25, 35], сортировка выбором (выбираем минимум из оставшихся) [25, 35]. Все эти сортировки имеют временную сложность-T(\) = 0(N2), где 0(f)- класс функций, растущих не быстрее и устойчивы.

Несколько более быстрая сортировка Шелла [25, 35] (T(l) = 0(N13)) представляет собой многопроходную сортировку, при которой сперва делают перестановки на большое расстояние, а потом шаг перестановок уменьшают. Это можно интерпретировать как разбиение исходного списка на подсписки, каждый из которых сортируется отдельно (сортировкой вставками), причем на каждом проходе число подсписков уменьшается, а их длина растет. Сортировка Шелла неустойчива. Пример сортировки методом Шелла:

Группы D=4

ГбГ1 | 87 1 1 154 1 | 170 1 1 275 [ [ 503 [ | 612 1 [ 765 Рис. 3. Пример сортировки методом Шелла Пирамидальная сортировка (T(\) = 0(Nlog2 N)) строит бинарное дерево, значение каждого узла в котором превышает значение потомков.

1 12 I 10 I 11 I 5 I 9 I S ) 6 Н I 2 1 7 I 3 I 4 i I 2 3 4 5 6 7 8 9 10 11 12

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

T(\) = 0(Nlog2N)) берет два уже отсортированных списка и создает, сливая их, новый отсортированный список. Различные реализации сортировки слиянием могут быть устойчивыми и неустойчивыми. При сортировке подсчетом (T(\) = 0(N2)) определяются номера мест элементов множества, расстановка по которым дает сортированное множество. Сортировка подсчетом устойчива. Быстрая сортировка (сортировка Хоара, в наихудшем случае T(\) = 0(N2), в среднем случае T(\) = 0(Nlog2N)) представляет собой рекурсивный алгоритм, который выбирает в списке осевой элемент, а затем разбивает список на две части, состоящие из элементов соответственно меньших или больших выбранного. Сортировка Хоара называется быстрой, поскольку в среднем случае требуется (N/3)ln(2)log2(N) [25] перестановок данных, что меньше, чем число сравнений.

Исходный список 6 2 4 7 1 3 8 5

Ось в ячейке 6 5 2 4 1 3 6 8 7

Ось в ячейке 5 3 2 4 1 5 6 8 7

Ось в ячейке 3 1 2 З1 4 5 6 8' 7

Ось в ячейке 1 1 2 3 4 5 6 8 7

Ось в ячейке 8 1 2 3 4 5 . 6 7 8=

Рис. 5. Пример быстрой сортировки.

Обычно размер данных значительно больше размера ключей, что и вызывает ускорение сортировки. Но в случае перестановки индексов это преимущество теряется. Сортировка Хоара неустойчива. Параллельная сортировка Хоара рассмотрена в [60]. Этот вариант устойчив и устанавливает взаимно-однозначное соответствие входных и выходных индексов. Преобразование сортировки Хоара в форму параллельного алгоритма в лучшем случае достигает временной сложности t(R)=0(log2n) при R = 0{n). В общем случае оценка временной сложности данной сортировки t{R) = 0(log2n) достигается с использованием R = (n +1)2/4 процессоров. Другие современные методы последовательных сортировок обсуждаются в [3, 7, 14, 17]. Касаясь отдельно аспекта параллелизма сортировок, отметим, что среди известных схем выделяются параллельная сортировка Бэтчера [35] (t{n) = 0(log\ n)); сортировка на линейных сетях [41] (t(n)= o(n))', четно-нечетная сортировка перестановками [41] (t(n/2) = 0(n)); асинхронная конвейерная сортировка альтернативными вставками [88]. В дальнейшем в работе будет использоваться сортировка слиянием, которая в параллельном варианте [56, 57, 58] характеризуется сложностью ( t(n2 / 4) = 0(log2n)). Принцип построения паралдельных схем сортировки можно пояснить на схеме известной сортировки деревом (рис. 6). Каждый из текущих минимальных элементов можно найти на < п/2 процессорах за время 0(log2w). После п просеиваний найденных минимумов, получаем отсортированный массив.

Современное состояние проблем параллельных сортировок освящено в [6, 11, 15, 16, 82], приводятся схемы с временной сложностью T(N) = 0(log2 N). п элементов

L'og2«J

Рис. 6. Пример распараллеливания этапа сортировки деревом Кроме того, существует несколько вариантов сортировок на.основе слияния. Сортировка .слиянием разрабатывалась как внешняя сортировка для файлов с последовательным доступом [25, 35]. При использовании сортировки слиянием в качестве внутренней сортировки образовалось множество вариантов, как неустойчивых, так и устойчивых сортировок. В качестве устойчивых вариантов сортировки слиянием рассмотрим естественную сортировку слиянием и сортировку слиянием с фиксированным шагом. Для этого введем следующие термины. Этапом сортировки назовем однократный проход по всем данным с соответствующиви сравнениями и перестановками индексов (или данных). Шагом1 сортировки назовем расстояние, с которого начинают сливаться индексы* (или данные). Естественная сортировка слиянием использует то обстоятельство, что в исходной последовательности некоторые данные частично упорядочены. На рис. 7 упорядоченные отрезки данных помечены штриховкой. В процессе каждого этапа слияния находим размер шага слияния. Это требует дополнительных сравнений. В худшем, случае сортировка N данных займет log2^ этапов, а в лучшем случае один этап.

Исходный' список 6 2 4 7 , 1 3' 8 5 ш^ш^////////////////^^^

После 1-го этапа 2 4 6 7 1 3 5 8

После 2-го этапа 1 2 3 4 5 6 7 8

Рис. 7. Пример естественной сортировка слиянием

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

Исходный список 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

Рис. 8. Пример сортировки слиянием с фиксированным на каждом этапе шагом

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

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

Разновидности > изображений. Существующие устройства ввода, такие как сканеры, фото и видеокамеры, а также устройства вывода, такие как мониторы и принтеры, обусловливают форму представления визуальной информации в виде изображений [45]; в памяти компьютера обычно используется представление изображения в виде матрицы пикселей /(mvm2), 0</и, <Мх-\, 0 <тг <М2-1 (растровое изображение) [74]. В зависимости от вида элементов матрицы различают следующие разновидности изображений: полноцветные, палитровые, полутоновые, бинарные. Элементы полноцветных изображений непосредственно хранят всю информацию о цветовых составляющих, использование таких изображений требует больших вычислительных затрат. В палитровых изображениях значение пикселей является ссылкой на ячейку карты цветов (палитру) - двумерный массив, в столбцах которого расположены интенсивности цветовых составляющих каждого цвета. Полутоновое изображение состоит из элементов, которые могут принимать одно из значений интенсивности какого-либо базового цвета. Это один из наиболее распространенных типов изображений, который применяется при исследованиях различного рода (широко используется глубина цвета 8 бит на пиксель). Диапазон значений элементов бинарного (монохромного) изображения ограничен только двумя значениями; 0 (фоновые точки) или 1 (точки интереса). Природа происхождения таких изображений разнообразна, часто бинарные изображения получаются в результате порогового разделения полутоновых изображений с фиксированным или адаптивным порогом (известные методы преобразования полутоновых изображений в бинарные приводятся в [8]). Количество информации при этом значительно сокращается, поэтому бинарные изображения просты в обработке, хранении и пересылке. Для использования алгоритмов заливки производят [18] бинеаризацию изображений. Рассмотрим обычную заливку с затравкой для изображений. Алгоритмы широко известны и приводятся, например, в [24]. Как правило, для заливки области изображеня задаются:

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

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

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

По способу задания заливаемые области делятся на 2 типа:

• гранично-определенные, задаваемые своей (замкнутой) границей, нарисованной определенным кодом пикселей.

• внутренне-определенные, нарисованные одним определенным кодом пикселей.

По способам доступа к соседним пикселям области делятся на два типа:

Область Граница Алгоритм заливки

1. 4-связная 8-связная 4-и 8-связный

2. 8-связная 4-связная 8- и 4-связный а) 4-х б) 8-ми связные, внутренне-определенные области

О - пикселы области, ® - пикселы границы

Рис. 9. Область заливки и граница Алгоритмы заливки с затравкой области.

Заливка выполняется следующим образом:

• определяется, является ли пиксель граничным или уже закрашенным,

• если нет, то пиксель перекрашивается, затем проверяются и, если нужно, перекрашиваются 4 соседних пикселя.

Алгоритм, известный под названием простого алгоритма заливки с затравкой, состоит в следующем. Алгоритм 1.

1. Поместить координаты затравки в стек;

2. Если стек пуст, перейти к п. 8;

3. Извлечь координаты пикселя из стека;

4. Перекрасить пиксель;

5. Для всех четырех соседних пикселей проверить является ли он граничным или уже перекрашен;

6. Если нет, то занести его координаты в стек;

7. Перейти к п. 2;

8. Выход. а) Порядок перебора соседних пикселей б) Порядок заливки области

Рис. 10. Заливка 4-связной области итеративным алгоритмом

Помимо простого алгоритма заливки с затравкой, широко применяется построчный алгоритм заливки с затравкой. Используется пространственная когерентность:

• пиксели в строке меняются только на границах;

• при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксель.

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

1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.

2. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксель. Пусть это Хлев и Хправ, соответственно.

3. Анализируется строка ниже закрашиваемой в пределах от

Х;|ев до Хправ и в ней находятся крайние правые пиксели всех незакрашенных фрагментов. Их координаты заносятся в стек.

То же самое проделывается для строки выше закрашиваемой.

Алгоритм, реализующий данную разновидность заливки с затравкой, известен под названием построчного алгоритма и состоит в следующем.

Алгоритм 2.

1. Занести координаты заправочного пикселя в стек;

2. Если стек пуст, перейти к п. 10;

3. Взять координаты затравки из стека;

4. Перекрасить пиксель;

5. Закрасить строку вправо и влево от затравки пока не встретится уже закрашенный или граничный пиксель;

6. Запомнить координаты крайних закрашенных пикселей Хлев и Х[фав;

7. В диапазоне от Хлев до Х„рав в выше и нижележащей строке отыскиваются крайние правые пиксели в еще незакрашенных сегментах;

8. Координаты отысканных пикселей запоминаются в стеке как затравки;

9. Перейти к п. 2;

10. Выход.

В исходных данных обычно содержится более одного объекта. Поэтому при нахождении объектов следует учитывать разметку компонент [30].

Разметка компонент. Будем считать две точки изображения связанными, если существует путь между ними, вдоль которого характеристическая функция постоянна. Так, на рис. 11 точка А связана с точкой В, но не связана с точкой С. Связная компонента бинарного изображения есть максимальное множество связанных точек, т. е. множество, состоящее из всех тех точек, между любыми двумя из которых существует связывающий их путь.

Рис. 11. Изображение, состоящее из нескольких областей, для каждой из которых необходимо проводить расчет положения и ориентации.

Элементы изображения необходимо пометить таким образом, чтобы принадлежащие одной области были отличимы от остальных Для этого нам необходимо решить, какие точки принадлежат одной и той же области. На рис. 11 точка А считается связанной с точкой В, поскольку мы можем найти непрерывную кривую, целиком лежащую в затененной области и соединяющую указанные точки. Ясно, что точка А не связана с точкой С, так как в этом случае подобной кривой найти нельзя. Для разметки объектов на дискретном бинарном изображении можно использовать алгоритм заливки с затравкой. Вначале выбираем произвольную точку - затравку. Один из способов разметки объектов на дискретном бинарном изображении состоит в выборе произвольной точки - затравки, в которой Ьи= 1, и приписывании метки этой точке и ее соседям. На следующем шаге помечаются, соседи этих соседей (кроме уже помеченных) и т. д. По завершении этой рекурсивной процедуры одна компонента будет полностью помечена, и процесс можно будет продолжить, выбрав новую начальную точку — затравку. Чтобы ее отыскать, достаточно каким-либо систематическим образом перемещаться по изображению до тех пор, пока не встретится первая еще непомеченная точка, в которой b,j= 1. Когда на этом этапе не останется ни одного такого элемента, все объекты изображения окажутся размеченными. «Фон» также можно разбить на связные компоненты, поскольку объекты могут иметь отверстия. Их можно пометить с помощью той же процедуры, но при этом необходимо обращать внимание не на единицы, а на нули.

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

Связность. В [30] рассматрривается смысл термина сосед. Если мы имеем дело с квадратным растром, то, по-видимому, соседями следует считать четыре элемента изображения, касающиеся сторон данного элемента. Для угловых элементов существуют две возможности: четырехсвязность - соседями считаются только элементы, примыкающие к сторонам; восьмисвязность - элементы, касающиеся в углах, также считаются соседями. Указанные возможности приведены на следующих диаграммах:

Рис. 12. Соседние элементы для 4- и 8-связных областей Оказывается, ни одна из этих схем не является полностью удовлетворительной. В этом можно убедиться, если вспомнить, что фон также можно разбить на несколько связных компонент. Здесь нам хотелось бы применить наши интуитивные представления о связности областей на непрерывном бинарном изображении. Так, например, простая замкнутая кривая должна разделять изображение на две связные области (рис. 13). Это так называемая теорема Жордана о кривой.

Теперь рассмотрим' простое изображение, содержащее четыре элемента со значением "единица", которые примыкают к центральному элементу со значением "нуль": это — крест с выброшенным центром. Если принять соглашение о четырехсвязности, то на изображении окажутся четыре различные компоненты (О/, 02, Оз, и 04).

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

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

4- ч У /1ч

4 *

0 1 0

1 0' 1

0' 1 0

В/ о, В, ff| в2

В, 04 В,

В о в о в О в О в данному по сторонам, а также два из лах: четырех элементов, касающихся в угили ——

Для обеспечения симметричности'отношения связности два угловых элемента должны находиться на одной и той же диагонали: если элемент А — сосед элемента Д то элемент В должен быть соседом элемента/1. В'дальнейшем мы будем пользоваться первым из двух возможных вариантов, приведенных выше, считая соседями элементы в направлениях N, Е, SE, S, W и NW. С помощью шестисвязности как объект, так и фон можно трактовать единообразно без каких-либо дальнейших неувязок. Для изображений на квадратном.растре мы примем именно такое соглашение. На гексагональном растре рассуждения-проще. Все шесть элементов растра, касающиеся данного центрального элемента, являются соседями, так что неопределенности не возникает. Наши предыдущие действия можно рассматривать как простой перекос квадратной решетки и превращение ее в гексагональную. Чтобы в этом убедиться, зафиксируем произвольный элемент и сдвинем ряд, находящийся над ним^ на половину ширины элемента вправо, а ряд, находящийся под ним, — на ту же величину влево:

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

Как говорилось выше, задача выделения объектов из набора сигналов, или из набора любых других данных имеет много общего с выделением объектов из изображений. В дальнейшем будем пользоваться следующими терминами: для изображений - изображение и пиксель. Для данных аналог термина «изображение» -весь набор данных, весь набор сигналов или просто набор данных, набор сигналов. Аналог пикселя для данных - точка данных, ил и данное, точка сигнала или сигнал. Поскольку данные могут быть различного типа, включая их задание в виде структур, желательно вынести проверку принадлежности данного объекту из алгоритма заливки. Это достигается введением функции принадлежности. Кроме того, имея функцию принадлежности можно легко изменять условия проверки, анализировать при проверке не только текущее данное, но, если надо, и соседние данные. В процессе выделения объектов необходимо произвести бинеаризацию сигналов. Поскольку, как правило, и выделяемые объекты и фон могут иметь разную амплитуду в одном наборе данных, пороговая фильтрация с общим порогом для всего набора данных в таких случаях неприменима, независимо от способа выбора порога (с помощью анализа симметричного пика гистограммы, с помощью алгоритма k-средних и др. [18]). Однако для некоторых задач допустима пороговая фильтрация с общим порогом. Пороговая фильтрация допустима при создании порога, индивидуального для каждого выделяемого объекта. Порог может функцией от амплитуды выделяемого объекта. Но при этом требуется узнать амплитуду объекта, который еще не выделен. Можно для этой цели ■ отсортировать данные по убыванию и выделять объекты в порядке максимальных значений. При этом надо пропускать ранее выделенные данные и обеспечить поглощение немаксимальных данных, прилегающих к выделенным объектам. Таким образом, происходит совмещение во времени перевода данных в бинарную форму с выделением из него объектов. Выделение можно производить как по координатам, так и по площади. При выделении по координатам получаем набор признаков1 объектов. Чтобы выделить объекты, необходимо объединить соответствующие признаки. Эта задача практически полностью совпадает с заливкой бинарного изображения. Для решения этой задачи предложен метод построчной линейной заливки. Основа - работа со строками, а не с объектами. Кроме того, допустима адаптивная бинаризация [18] при работе с данными, в дальнейшем называемая работой с адаптивным порогом. Адаптивный порог может быть построен путем размытия данных, причем практически для данных любого вида. Данные относятся к выделяемым объектам, если превышают адаптивный порог на некоторое заданное значение. Выбор превышения зависит от задачи. В качестве данных можно рассматривать значения функции двух переменных. В этом случае можно находить минимумы и максимумы такой функции, пользуясь методом заливки с затравкой, а также линии сечения функции плоскостью. Если это нулевая плоскость (Х=0, Y=0), то линии сечения будут корнями функции. Для этого можно использовать метод построчной линейной заливки.

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

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

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

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

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

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

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

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

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

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

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

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

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 страницах, включая 28 таблиц, 67 рисунков и список литературы из 94 наименований. Диссертация включает приложение из 11 разделов общим объемом 341 стр.

3.7. Выводы

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

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

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

4. Даны видоизменения алгоритмов главы 1 для одновременного выделения контуров всех объектов на изображениях плохого качества.

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

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

Заключение

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

Работа содержит следующие научные результаты

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

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

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

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

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

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

Научная новизна диссертационной работы заключается в следующем.

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

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

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

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

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

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

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

1. Barlow J.S. and Remond A. Eye movement artifact nulling in EEGs by multichannel on-line EOG subtrractio. // Electroencephalography and Clinical Neurophysiology, 1981. -52.-P. 418-423.

2. Baudet G., Stevenson D. Optimal sorting algorithms for parallel computers // IEEE Transactions of computers. January 1978. -v.c. 27, № 1. - P. 84 - 87.

3. Biedl Th., Chan Т., Demaine E.D., Fleischer R., Golin M., King J.A., Munro J. I. Fun-Sort'-or the chaos of unordered binary search. Discrete Applied Mathematics, Volume 144, Issue 3 , 15 December 2004. - P. 231-236.

4. Bierman GJ. Measurement updating using the U-D factorization. Automatica, 1976. 12.-P. 375-382.

5. FineReader 9.0: новая версия системы распознавания документов и PDF-файлов, http://w4a.ru/blog/2007/10/02/finereader 9 0 novaya versiya sistemi raspoznavan/

6. Gasarch W., Golub E., Kruskal C. Constant time parallel sorting: an empirical view. -Journal of Computer and System Sciences, Volume 67, Issue 1 , August 2003, P. 63-91.

7. Gerbessiotis A.V., Siniolakis C. J. Probabilistic integer sorting. Information Processing Letters, Volume 90, Issue 4, 31 May 2004. - P. 187-193.

8. Gonzalez R.C., Woods R.E. Digital image processing. MA.: Addison-Wesley, 1992.-716 p.

9. Ifeachor E.C. A Practical Guide for MATLAB and С Language Implementations of DSP Algorithms. Harlow: Person Education, 2001.

10. Nardelli E., Proietti G. Efficient unbalanced merge-sort. Information Sciences, Volume 176, Issue 10 ,22 May 2006. - P. 1321-1337.

11. Oracle.UkrSat.com Магазин - RCO - Инструментарий разработчика, ora-cle.ukrsat.com/storeadditional. php?grp=23&globalgroup=l 7

12. Richard Beigel and John Gill. Sorting n objects with a k-Sorter // IEEE Transactions of computers. May 1990. -v. 39, № 1. - P. 714 - 716.

13. Sanguthevar Rajasekaran, Sandeep Sen. A generalization of the 0-1 principle for sorting. Information Processing Letters, Volume 94, Issue 1,15 April 2005. - P. 43-47.

14. Seiferas J. Networks for sorting multitonic sequences. Journal of Parallel and Distributed Computing ,Volume 65, Issue 12 , December 2005. P. 1601-1606.

15. Taniar D., Rahayu J.W. Parallel database sorting. Information Sciences , Volume 146, Issues 1-4 , October 2002! - P. 171-219.

16. Ахмед Н., Pao К.Р. Ортогональные преобразования при обработке цифровых сигналов: / Под ред. И.Б. Фоменко. М.: Связь, 1980. - 248 с.

17. Березин И.С., Жидков Н.П. Методы вычислений. Т. 2. - М.: Государственное издательство физико-математической литературы, 1962. - 640 с.

18. Боббер Р. Гидроакустические измерения. М.: Мир;.1974. 364 с.

19. Буланов С.Г., Заика И.В., Катрич С.А., Ромм Я.Е. Моделирование критериев устойчивости и определение экстремальных значений решений дифференциальных уравнений на основе разностных схем при помощи, сортировки / ТГПИ Таганрог. -2004. С. 156.

20. Вельтмандер^ П.В. «Основные алгоритмы компьютерной графики» Книга 2. http://ermak.cs.nstu.ru/ke; rivs/home.htm#top •

21. Губерман Ш.А. Неформальный анализ данных в геологии и геофизике. Выделение объектов (системный подход) М.: Недра, 1987. http://wvvw.integro.ru/system/ots/guberman/guberman.htm

22. Дадашев Тахмасиб «Поиск видеоданных в сети» Журнал «Компьютерра» №12 от 30 марта 1998 года.

23. Журавель И.М. «Краткий курс теории обработки изображений», http://matlab.cxponenta.ru/imageprocess/book2/index.php

24. Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука. Гл. ред. физ.-мат. лит, 1989. - 496 с.-ISBN 5-02-014094-5.

25. Заярный В.В., Боженюк А.В. Предварительная обработка сигналов для распознавания* образов. / Известия ТРТУ 2007г. №1. С.227. Издательство ТРТУ ГСП 17А Таганрог, 28 Некрасовский, 44.

26. Клюкин И. И. «Удивительный мир звука.»-Л.Судостроение, 1978.-168 с.

27. Конкурс Русских ИнновацийПатентование способа аппаратно-независимогопредставления видеоинформации для стеганографии и автоматического распознавания изображений.Ыт, http://wvvw.inno.ru/proiect/14017/

28. Кузин Л.Т. Основы кибернетики: в 2-х т. Т.2. М.: Энергия, 1979. - 584 с.

29. Курс лекций по дисциплине «Системы искусственного интеллекта» Лекция 11 :Системы машинного зрения.Ы;т1, http://www.mari.ru/mmlab/home/AI/11/index.html

30. Оппенгейм А.В., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. / Под ред. С.Я. Шаца. М.: Связь, 1979. - 416 с.

31. Павлидис Т. Алгоритмы машинной графики и обработки изображений: Пер. с англ. М.: Радио и связь, 1986. - 394 с.

32. Применение цифровой обработки сигналов // Под ред. Э. Оппенгейма. М.: Мир, 1980. - 398 с.47. «Программное o6ecne4eHHe.html», http.7/www.zenit-npk.ru/frames/med9.html

33. Путятин Е.П. докт.техн.наук «Нормализация и распознавание изображе-ний.Мт», http://sumschool.sumdu.edu.ua/is-02/rus/lectures/pytyatin/pytyatin.htm

34. Прэт У. Цифровая обработка изображений, в двух книгах. Книга 1: Пер. с англ./Под ред. Д.С. Лебедева. М.:Мир, 1982.-311 с.

35. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. I // Кибернетика и системный анализ. 2001. - № 4. - С. 142 - 159.

36. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. II // Кибернетика и системный анализ. 2001. - № 5. - С. 81 - 101.

37. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. 1994. - № 5. - С. 3 - 23.

38. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. 1995. - № 4. - С. 13 - 37.

39. Ромм Я.Е. Параллельная сортировка слиянием. Приложение к вычислению нулей, экстремумов функций и распознаванию образов. Таганрог: Изд-во ТГПИ, 1998. - 190 с.

40. Ромм Я.Е., А.И. Дордопуло, В.В. Заярный. Программная локализация нулей многочленов с приложением к идентификации объектов по данным гидроакустической локации. / Научное издание; Таганрог: Изд во Таганрог, гос. пед. Института. -2005.-217 с.

41. Ромм Я.Е., Виноградский В.В. Преобразование сортировок в форму устойчивых схем со свойствами прямой и обратной адресности / ТГПИ. Таганрог, 2003. -43 с. Деп. в ВИНИТИ 8. 12. 2003, № 2130-В2003.

42. РоммЯ.Е., Гуревич М.Ю., Белоконова С.С., Соловьёва И.А. Вычисление нулей и полюсов функций на основе устойчивой адресной сортировки с приложением к поиску и распознаванию. / Проблемы программирования. 2004. - №2-3. - С. 462472.

43. Ромм Я.Е., Заика И.В. Метод нахождения экстремумов решений дифференциальных уравнений на основе адресной сортировки. ТГПИ.- Таганрог, 2003.- Деп. в ВИНИТИ 12.15.2003 № 908-В2003

44. Ромм Я.Е., Заика И.В. Схема поиска экстремумов и нулей решения системы дифференциальных уравнений на основе сортировки / ТГПИ. Таганрог, 2004. - 49 с. Деп. В ВИНИТИ 28. 05. 2004, № 897-В2004.

45. Ромм Я.Е., Заика И.В. Схема поиска экстремумов и нулей функций на основе адресной сортировки / ТГПИ. Таганрог, 2005. - 50 с. Деп в ВИНИТИ 01. 03. 2005, № 289 - В2005.

46. Ромм Я.Е., Заика И.В., Соловьева И.А. Метод программной оптимизации в приложении к математическим моделям экономики. / «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». Т.2. -Таганрог. 2005. - С. 17 - 26.

47. Ромм Я.Е., Тюшнякова И.А, Заика И.В. Идентификация экстремумов функций на основе сортировки с приложением к вычислительным схемам алгебры, анализаи распознаванию изображений // Проблемы программирования. Киев,2006.№2-3.-С. 708-717.

48. Рудаков П.И., Сафонов-В.И. «Обработка сигналов и изображений. MATLAB 5.x». М.: ДИАЛОГ-МИФИ, 2000. - 416 с.

49. Самарский А.А. Введение в численные методы. М.: Наука, 1987. -288с.~

50. Сойфер В.А. Компьютерная обработка изображений. Часть 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ (СОЙФЕР В.А. , 1996), МАТЕМАТИКА http://www.pereplet.ru/obrazovanie/stsoros/49.html

51. Сойфер В.А. Компьютерная обработка изображений. Часть 2. Методы и алгоритмы (СОЙФЕР В .А., 1996), МАТЕМАТИКА.

52. Сойфер В.А. Методы компьютерной обработки изображений. Под ред. Сойфе-ра В.А. 2-е изд. испр. М: ФИЗМАТЛИТ, 2003'. - 784с. ISBN 5-9221-0270-2/

53. СУТЯГИН И. «Гидроакустический комплекс атомных подводных лодок типа «ЛОС-АНДЖЕЛЕС» ВМС США», http://commi.narod.ru/txt/1995/0802.htm76. «Технологии. оптического распознавания документов», http://www.eos.com.ua/eos/reshenija/orc.htm

54. Травин Андрей. «WolfPromotion Технологии* оптического распознавания текстов», http://travin.msk.ru/arc/OCR.html

55. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. - 321 с.

56. Харинов М.В., Ямов А.С. «Инвариантное представление изображений на основе псевдотроичной системы счисления» Россия, Санкт-Петербург, СПИИРАН, alexandr@mail.iias.spb.suhttp://www.inftech.webservis.ru/it/conference/isanditc/2000/section4/rus/arrusl2.html

57. Цейтлин Г.Е. Распараллеливание алгоритмов сортировки // Кибернетика 1989. - № 6. - С. 67-74.

58. Цепковский Ю.А. Построение оптической обратной связи для управления рукой робота с использованием виде http://paep2007.abacus.ua/default.aspx?id=paepshowdoc&doc= 10918

59. Цифровая обработка сигналов Лекция 3 http://graphics.cs.msu.ru/courses/cg02b/lectures/lection3/lect03 02.ppt

60. Цифровая обработка сигналов. Сайт проф. Давыдова А.В. Тема 18. Распознавание объектов изображений http://prodav.exponenta.ru/dsp/doc/dspl8.doc

61. Цифровая обработка сигналов: практический подход // Э. Айфичер, Б. Джер-вис. 2-е изд. - М.: Вильяме, 2004. - 989 с.87. «Что такое семантическая сегментация?», http://vvww.patchmaker.net/ssl/

62. Яценко Е.А., Мохница А.С. Инструментальные средства конструирования синтаксически правильных параллельных алгоритмов и программ. // Проблемы программирования. 2004. - №2-3. - С. 444 - 450.

63. Ромм Я.Е., Заярный В.В. Компьютерная идентификация объектов при обработке сигналов с приложением к данным гидроакустической локации и обработке изображений // ДЕП. в ВИНИТИ 20.07.07 № 751-В2007.

64. Ромм Я.Е., Заярный В.В. Компьютерная обработка сигналов гидроакустической локации и идентификация объектов растровых изображений // Системы управления и информационые технологии, 2007, №4.2(30). С. 290 - 295.

65. Ромм Я.Е., Заярный В.В. Выделение объектов в двумерном массиве оцифрованных сигналов // Обозрение прикладной и промышленной математики. Т. 15. -Вып.З. - С. 473 - 474.

66. Function CreateObjlnList( var ListObjAll :TList; Str, iVl, iV21.nglnt):Longlnt;1. VarpObgAll : pTpObj; pis : pTpPix;//TpObjStr; Num, i : Longlnt; // i, MaxA, MinA, SumA : Longlnt; Begin

67. Учет рамки dec(Str); dec(iVl); dec(iV2);

68. Num := ListObjAll.Count; // номер созданного Объекта

69. TFInObj = Function ( var Arln : TArPix; ix, iy: Longlnt):1.nglnt; //----------------------const1. NoObj = -1; // не объектvar CurrentBasePath, CurrentAppPath, CurrentlNI, DefaultlNI : String;

70. TmpXAMin, TmpXAMax, TmpYAMin, TmpYAMax: Longlnt; //Координаты промежут. Координат значения функции принадлежности

71. TmpAMin, TmpAMax: Longlnt; //Амплитуды промежут. значения функции принадлежности1. DataFileName : String;--- Функция сравнения ------

72. Function FmCmp( il, ±2: Longlnt; var Arln : Array of Byte): Longint;

73. Function FmMinCmp( il, ±2: Longlnt; var Arln : Array of Byte): j^ongint ;---- Создаие Объекта в списке (возвр. номер Объекта)

74. Find80bject для 8-связных procedure Fmd80b.ect( var ListObjAll :TList; var Arrln:TArPix; FInObject:TFInObj) ;implementation uses SysUtils, Windows;procedure ListPack(Lst:TList);

75. List.Pack в среднем работает очень медленно // Собираем все NIL в конце, затем Pack -быстрее Varil, i2, NN : Longlnt; beginil := 0; i2 := 0;