Разработка и исследование методов распознавания объектов в массивах оцифрованных данных на основе адаптивного порога и схем сортировки

• Автор: Заярный, Виктор Вильевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Таганрог
• Количество страниц: 497 с. : ил.

Введение
Глава 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. Выводы
Заключение
Литература
Приложения
Приложение 1.1. Программа линейной заливки
Приложение 1.2. Программа заливки с затравкой
Приложение 1.3 Программа для обработки изображений с
использованием приведенных в приложениях 1.1, 1.2, 1.4 модулей
Приложение 1.3.1. Файл проект Delphi
Приложение 1.3.2. Основная форма
Приложение 1.3.3. Форма контроля результатов обработки
Приложение 1.3.4. Программа для работы с адаптивным порогом
Приложение 1.4. Программа сортировки слиянием

Приложение 2.1 Программа для обработки гидроакустической информации с использованием приведенного в приложении 1.4 модуля
Приложение 2.1.1. Файл проект Бе1рЫ
Приложение 2.1.2. Основная форма
Приложение 2.1.3. Модуль иОаззБойРгосебигез
Приложение 2.1.4. Модуль иОаззосаНгабоп
Приложение 2.1.5. Модуль иС1азз_Ра11ебе
Приложение 2.1.6. Модуль иС1азз_МеШо(1Рагатз
Приложение 2.1.7. Модуль иС1аз8_11ап§еОЬ]ес18Ргосес1иге8
Приложение 2.1.8. Модуль иС1а8Б ЗогЮеРгосебигез
Приложение 2.1.9. Модуль иСIаэз_Турез_Апс1_ОЬ) еЩя Ргосебигеэ
Приложение 2.1.10. Модуль ипк1_Оа!а
Приложение 2.1.11. Модуль ип_1Ша1аОи1
Приложение 2.1.12. Модуль 11пк1_ба12
Приложение 2.1.13. Константы
Приложение 2.1.14. Типы процедур
Приложение 2.2. Параметры объектов
Приложение 2.3. Характеристики объекта, изображенного на рис
(Хорошо идентифицируемый сигнал)
Приложение 2.4. Список параметров одного из ложных объектов ...480 Приложение 2.5. Параметры для выделения заиленных объектов ил 050826 01.ini
Приложение 2.6. Параметры для выделения дна Dno04.ini
Приложение 3. Акты об использовании результатов диссертационной работы
машины), можно сортировать исходную неупорядоченную
последовательность, разбитую на отрезки по числу процессоров, по сложным составным ключам. Тогда каждое сравнение будет занимать больше времени, но не будет межпроцессорного обмена на этом этапе сортировки. После получения сортированных отрезков данных их слияние можно выполнять попарно, пока не получится полностью отсортированная последовательность данных.
В настоящее время широко распространены многоядерные процессоры и многопроцессорные компьютеры с общим доступом к памяти. В [56, 57] приведена оценка времени работы слияния, которую можно использовать для таких компьютеров. Ниже, в п. 1.1.1 приведен способ распараллеливания сортировок на основе слияния, а в пп. 1.1.2-1.1.3 приведены выдержки из [56, 57] с оценками временной сложности на этот случай.
1.1.1. Параллельная сортировка с видоизменением слияния для постоянного количества процессоров
При получении каждой сливаемой последовательности с помощью одного процессора алгоритм упрощается, однако временная оценка увеличивается. Допустим, мы имеем. N неупорядоченных, данных и р процессоров, причем N » р. Мы можем разделить эти данные на р равных групп в порядке расположения. Получим отрезки длиной N/p данных в каждом. Используя р процессоров, все эти отрезки данных можно сортировать параллельно за время, пропорциональное (N/p)-log2(N/p). Здесь логарифм по основанию 2 определяется тем, что процессор на шаге выполняет бинарное сравнение.
Слияние полученных отсортированных отрезков данных по схеме сдваивания займет logÿ? этапов, на i-м из которых будет задействовано р/2' процессоров (i = 1.. Iog2 р ). На каждом из этапов слияния затраты времени; будут пропорциональны (N/ р)х2‘ и на последнем этапе пропорциональны N.
В итоге всех этапов верхняя оценка числа последовательных шагов составит
l°Xl Р Р
J(N/p)x 2' = (N / р)х YP-' = 2loRiP*'-)xN/p<2pxN/p=2N.
/=1
С учетом предварительно проделанной сортировки приходим к окончательной оценке временной сложности:
Т(р) = {N/pxlog2(N/p) + 2N)i
Тем самым изложена некоторая разновидность параллельной сортировки на