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

• Заярный, Виктор Вильевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Заярный, Виктор Вильевич

Введение.

Глава 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 г.; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики результаты используются в преподавании курсов «Основы информатики», «Теоретические основы информатики», «Программирование», «Информационные технологии в математике», «Специальные разделы информатики».Внедрение результатов работы подтверждено соответствующими актами.

Список литературы диссертационного исследования кандидат технических наук Заярный, Виктор Вильевич, 2009 год

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. Харинов М.В., Ямов А.С. «Инвариантное представление изображений на основе псевдотроичной системы счисления» Россия, Санкт-Петербург, СПИИРАН, [e-mail]://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;