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

• Автор: Ромм, Леонард Яковлевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Таганрог
• Количество страниц: 225 с. : ил.

ОГЛАВЛЕНИЕ

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

1.1. Определение и свойства матрицы сравнений

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

1.3. Модификация сортировок слиянием и подсчетом на основе

много путево го слияния

1.3.1. Временная сложность /^-слияния

1.3.2. Слияние двух одномерных массивов как частный случай от-слияния

1.3.3. Параллельная сортировка т-путевым слиянием на основе матриц сравнения

1.3.4. Временная сложность параллельной сортировки т-слиянием на основе матриц сравнения
1.3.5. Параллельная сортировка подсчетом на основе матриц сравнения
1.3.6. Временная сложность параллельной модификации сортировки подсчетом
1.4. Идентификация экстремальных элементов числовой последовательности на основе сортировки
1.5. Сравнение идентификации экстремумов на основе сортировки
с существующими методами
1.6. Формирование признаковых характеристик плоских изображений
на основе сортировки
1.6.1. Предварительные примеры идентификации элементарных геометрических фигур с помощью подстановок
1.7. Выводы

Глава 2. Метод распознавания и целочисленной идентификации плоских контурных изображений на основе экстремальных признаков контура
2.1. Формирование признаков плоских контурных изображений, инвариантных относительно сдвига, поворота и изменения масштаба
2.1.1. Схема считывания декартовых координат точек контура
2.1.2. Алгоритм преобразования исходных декартовых координат
в полярные
2.1.3. Идентификация и использование глобально экстремальных элементов для определения признаковых характеристик контура
плоских изображений
2.1.4. Принцип формирования целочисленных компонентов векторных идентификаторов
2.2. Формирование вспомогательного и идентифицирующего векторов
2.3. Устойчивость идентифицирующего вектора в условиях сдвига, поворота, графических искажений и изменения масштаба изображения
2.3.1. Устойчивость идентифицирующего вектора относительно поворота изображения
2.3.2. Устойчивость идентифицирующего вектора к искажениям
и разрывам контура фигуры
2.3.3. Подход к сохранению устойчивости идентифицирующего вектора относительно изменения масштаба
2.4. Использование локально экстремальных координат для составления дополнительных характеристик различных участков контура без повторного проведения сортировки
2.5. Частные случаи схемы идентификации
2.6. Выводы
Глава 3. Распознавание множества внутриконтурных точек плоских изображений и фильтрация исходных координат на основе локально
экстремальных признаков
3.1. Метод программной реализации инвариантности поворота и сдвига

относительно начального положения обрабатываемого изображения
3.1.1. Метод сквозного считывания
3.2. Распознавание и идентификация внутриконтурной части изображения
3.2.1. Об использовании индексов локально экстремальных координат для получения дополнительных признаковых характеристик изображения
3.2.2. Построение идентифицирующего вектора без фильтрации последовательности исходных координат
3.2.3. Целочисленная идентификация рукописных символов на основе сортировки и подстановки индексов
3.2.4. Предварительные выводы об устойчивости идентифицирующего вектора к искажениям множества внутриконтурных точек фигуры
3.3. Фильтрация исходной последовательности координат на основе локализации экстремальных элементов при помощи сортировки
3.3.1. Примеры идентификации множества внутриконтурных точек фигур
с учетом фильтрации координат
3.3.2. Об устойчивости идентифицирующего вектора, учитывающего фильтрацию координат, к искажениям фигуры и идентификации классов изображений
3.3.3. О достижимости предельной устойчивости целочисленной идентификации изображений при вариации радиуса локализации экстремумов входной и отфильтрованной последовательности подмножества внутренних точек
3.4. Полная оценка временной сложности параллельной идентификации фигуры
3.5. Применение метода целочисленной идентификации для автоматизации построения базы данных идентифицирующих векторов
и натуральных идентификаторов
3.6. Применение параллельной целочисленной идентификации для поиска изображений

любое т -слияние выполняется с помощью (1.18), (1.19), поэтому достаточно вычислять только те МС(у), которые расположены выше и справа от главной матричной диагонали (ДЛГ-матр), состоящей из матрицы с незаполненными (нулевыми) элементами.
В результате все т -сливаемые отрезки располагаются в один горизонтальный ряд над входом в таблицы, идентифицированные как МСП7) (см. пример 1.3). Чтобы выполнить вставку произвольно выбранного из этого ряда элемента аг), достаточно без учета окаймления подсчитать суммарное число "плюсов" и "нулей" в 1-м столбце всех МС(,г)(г = 1, 2,...) над ДЛГ-матр и сложить это число с суммарным числом "минусов" в строке всех МС(/7) ( у = 1,2,...) справа от ДЛГ-матр, также подсчитываемым без учета окаймления, затем к полученной сумме следует добавить собственный номер элемента а(р в МС(1г равный і. Полученная сумма составит номер элемента аг) в m-слитом отрезке. Этот алгоритм проиллюстрирован на примере 1.3. Этот же алгоритм ниже используется в программной реализации т -слияния [45], в данной работе - при условии т-п.
1.3.1. Временная сложность т -слияния
Пусть все элементы всех требуемых МС*,у) из (1-Ю) при і < j вычисляются синхронно и взаимно независимо (параллельно). Для одной МС*у) это потребует п2 процессорных элементов (ПЭ). Общее количество ПЭ, обозна-

чаемое Snm, вычисляется умножением п2 на число МС , расположен-

ных выше ДЛГ-матр:
snn,=^(m2 -т)хп2. (1.20)
Длительность вычисления рассматриваемых элементов М.С0/) есть
Тяя"*, (1.21)