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

• Агаджанян Альберт Грантович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Агаджанян Альберт Грантович

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ

ВВЕДЕНИЕ

1 ТОНОВАЯ АППРОКСИМАЦИЯ ИЗОБРАЖЕНИЙ КАК АКТУАЛЬНЫЙ ИНСТРУМЕНТ ОБРАБОТКИ ЦИФРОВОЙ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ

1.1 Цифровые изображения

1.1.1. Формы графического представления ЦИ

1.1.2. Общая характеристика и свойства моделей цветовоспроизведения ЦИ

1.1.3. Влияние размерности палитры РЦИ на качество изображения

1.1.4. Монохромные изображения как частный случай цветных РЦИ

1.2 Монохромные растровые цифровые изображения

1.2.1 Виды и способы монохромного представления ЦИ

1.2.2 Структура и характеристики тоновых палитр монохромных РЦИ

1.2.3 Влияние размерности тоновой палитры на качество монохромных РЦИ

1.3 Области применения и задачи обработки монохромных РЦИ

1.3.1 Общая характеристика задачи и виды обработки ЦИ

1.3.2 Сжатие монохромных ЦИ

1.3.3 Обработка монохромных ЦИ при распознавании образов

1.3.4 Тоновая аппроксимация ММИ как универсальная технология преобразования РЦИ

1.4 Современные методы ТА монохромных мультитоновых изображений и их классификация

1.4.1 Дуальность подхода к реализации ТА монохромных РЦИ

1.4.2 Пред-кластерные методы ТА. Методы сечения

1.4.3 Пред-кластерные методы ТА. Группирующие методы

1.4.4 Пост-кластерные методы ТА

1.5 Сравнительное экспериментальное исследование популярных методов ТА

1.6 Постановка задачи диссертационного исследования

1.6.1 Построение и исследование математической модели ТА ММИ

1.6.2 Разработка и исследование методов поисковой оптимизации ММИ

1.6.3 Разработка и исследование программного обеспечения оптимальной ТА ММИ

2 ПРОЦЕСС ТОНОВОЙ АППРОКСИМАЦИИ РАСТРОВЫХ МОНОХРОМНЫХ МУЛЬТИТОНОВЫХ ИЗОБРАЖЕНИЙ КАК ОБЪЕКТ ОПТИМИЗАЦИИ

2.1. Математические модели растровых монохромных мультитоновых изображений

2.1.1. Координатно-пиксельная ММ растрового изображения

2.1.2. Математическая модель палитры растрового монохромного мультитонового ЦИ58

2.1.3. Объединенная координатно-пиксельно-тоновая ММ растрового монохромного мультитонового изображения

2.1.4. Математические модели частотно-яркостных свойств растрового монохромного мультитонового ЦИ

2.1.5. Использование ММ исходных ММИ для построения аппроксимирующих палитр

2.2. Технология тоновой аппроксимации ММИ

2.2.1. Особенности процесса тоновой аппроксимации ММИ

2.2.2. Основные структурные характеристики аппроксимирующей палитры

2.2.3. Структурирование ИП под задачу тоновой аппроксимации

2.2.4. Влияние структуры АП на качество тоновой аппроксимации ММИ

2.2.5. Фундаментальные свойства формирования УП

2.2.6. Конечный этап тоновой аппроксимации ММИ

2.3. Количественная критериальная оценка качества тоновой аппроксимации ММИ

2.3.1. Математические модели оценки качества тоновой аппроксимации ММИ

2.3.2. Предметно ориентированные ММ оценки качества тоновой аппроксимации ММИ

2.3.3. Выбор адекватного задаче тоновой аппроксимации ММИ критерия оценки ее качества

2.3.4. Дополнительное исследование адекватности критериев оценки качества ТА

2.4. Выводы по второй главе

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

2.4.2. Необходимость разработки специализированного поисково-оптимизационного алгоритма ТА

3. МОДИФИЦИРОВАННЫЙ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКИЙ МЕТОД СУБОПТИМАЛЬНОЙ ТОНОВОЙ АППРОКСИМАЦИИ РАСТРОВЫХ МОНОХРОМНЫХ ИЗОБРАЖЕНИЙ

3.1. Анализ проблемы оптимизации ТА растровых изображений и перспективных методов ее решения

3.1.1. Аппроксимированное мультитоновое монохромное изображение как объект оптимизации

3.1.2. Процедура тоновой аппроксимации как объект оптимизации

3.1.3. Проблема размерности решения задачи оптимизации процесса аппроксимации АММИ

3.1.4. Выбор парадигмы, метода и алгоритма поисковой оптимизации тоновой аппроксимации

3.2. Исследование возможностей субоптимальной аппроксимации ММИ вариантами классического ЭГА

3.2.1. Анализ фундаментальных положений ЭГА

3.2.2. Исследование классического ЭГА в среде многоэкстремальной задачи

3.2.3. Параметрические исследования на тестовой функции Растригина поисковой результативности ЭГА

3.2.4. Параметрическая субоптимизация поисковой результативности ЭГА на тестовой

ФР

3.2.5. Итоги и необходимость интеграции ТА ММИ в эволюционно-генетическое пространство

3.3. Исследование возможностей использования АП в качестве хромосомы ЭГА для ТА ММИ

3.3.1. Концептуальный анализ вариантов построения хромосомы ЭГА для ТА

3.3.2. Пример применения двухромосомной тоновой ГХС для аппроксимации ММИ

3.3.3. Структурные варианты ГХС на основе варьируемых АП-хромосомы и ОГ-хромосомы

122

3.4. Модифицированная на основе двухромосомной ГХС модель ЭГА тоновой субоптимизации АММИ

3.4.1. Стартовый этап модифицированного ЭГА

3.4.2. Особенности использования генетических операторов и других механизмов ЭГА при оптимизации ТА

3.4.3. Проблемы параметрической настройки модернизированного ЭГА в задаче ТА

3.5. Повышение результативности оптимизации ТА ММИ параметрической настройкой вероятностных факторов ЭГА

3.5.1. Применение 2-уровнего ПФЭ для выявления зоны субоптимальных значений ВФ

3.5.2. Поиск субоптимальных вероятностных показателей кроссинговера и мутации ЭГА для

ТА

3.5.3. Достоверность результатов оптимизации ТА модернизированным ЭГА

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

4. ГИБРИДНЫЙ АЛГОРИТМА БИОПТИМАЛЬНОЙ ТОНОВОЙ АППРОКСИМАЦИИ МОНОХРОМНЫХ РАСТРОВЫХ ИЗОБРАЖЕНИЙ

4.1. Алгоритм оценки экстремальности аппроксимирующей палитры

4.1.1. Постановка задачи разработки алгоритма гарантированной оценки структуры АП на предмет экстремальности

4.1.2. Парадигма оценки вектора АП на экстремальность

4.1.3. Экспериментальная проверка технологических свойств алгоритма СЕО при ТА и их анализ

4.1.4. Перспективы использования алгоритма СЕО для повышения результативности ТА ММИ

4.2. Разработка быстродействующего гибридного алгоритма экстремальной тоновой аппроксимации ММИ

4.2.1. Алгоритм циклического поиска экстремальной АП с пошаговым использованием СЕО

4.2.2. Гибридный алгоритм субоптимальной тоновой аппроксимации ММИ на основе алгоритмов ЭГА и ПБЭ

4.2.3. Поиск зоны субоптимальных настроечных параметров этапа ЭГА гибридного алгоритма оптимизации ТА ММИ

4.2.4. Повышение эффективности гибридного алгоритма тоновой аппроксимации на основе реализации параллельно-поисковой модели ЭГА

4.2.5. Проектирование адаптивной модели оптимизации тоновой аппроксимации ММИ

4.2.6. Основные результаты параграфа 4.2 и задача дальнейшего исследования

4

4.3. Сравнительное исследование эффективности разработанного гибридного алгоритма дуальной

оптимизации ТА ММИ

4.3.1. Задачи и способы выполнения сравнительного исследования алгоритмов ТА ММИ

4.3.2. Ресурсно-временная оптимизация вычисления критерия оптимизации ТА

4.3.3. Планирование эксперимента по исследованию результативности ГАО

4.3.4. Экспериментальное исследование эффективности ГАО в сравнении с популярными методами ТА

4.4. Оценка основных результатов сравнительного исследования ГАО с популярными и стандартными методами ТА

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЕ А

А.1. Популярные модели цветовоспроизведения ЦИ

ПРИЛОЖЕНИЕ А

А.2. Сравнительное исследование эффективности стандартных методов ТА ММИ

А.2.1. Постановка задачи сравнительного исследования методов ТА монохромных РЦИ

А.2.2. Критериальная основа сравнения стандартных методов ТА ММИ

А.2.3. Задачи и способы экспериментального сравнительного исследования методов ТА ММИ

А.2.4. Экспериментальное сравнение стандартных методов ТА ММИ

A.2.5. Достоверность экспериментальных данных и заключительные выводы

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ Б

B.3. Сравнительный анализ квадратичного и модульного критериев оценки качества применительно к пред-кластерным АТА

В.3.1. Анализ причин искажения качества тоновой аппроксимации

В.3.2. Сравнительный анализ алгоритмов ВС и МС на основе квадратичного и модульного критериев оценки качества

ПРИЛОЖЕНИЕ С

C.1. Исследование возможностей существующих подходов к задачам поисковой дискретной оптимизации

С.1.1. Основные различия в подходах к решению поисковых задач дискретной оптимизации

С.1.2. Перспективные эвристические подходы к субоптимизации тоновой аппроксимации ММИ

ПРИЛОЖЕНИЕ С

С.2. Основы и принципы эволюционно-генетического подхода к оптимизации технических задач

С.2.1. Возникновение и развитие эволюционного подхода

C.2.2. Общая структура и составляющие алгоритма ЭГА

C.2.3. Основные механизмы алгоритма ЭГА

C.2.4. Базовая схема и виды эволюционно-генетического алгоритма

C.2.5. Особенности применения эволюционно-генетического принципа в задачах ТА

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ С

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ D

ПРИЛОЖЕНИЕ E

ПРИЛОЖЕНИЕ F.1 (СВИДЕТЕЛЬСТВО ЭВМ)

ПРИЛОЖЕНИЕ F.2 (ПАТЕНТ)

ПРИЛОЖЕНИЕ F.3 (ЗАСЛУШИВАНИЕ ДИССЕРТАЦИИ)

ПРИЛОЖЕНИЕ F.4 (ЗАСЛУШИВАНИЕ ДИССЕРТАЦИИ)

ПРИЛОЖЕНИЕ F.5 (АКТ О ВНЕДРЕНИИ)

ПРИЛОЖЕНИЕ F.6 (АКТ О ВНЕДРЕНИИ)

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ

АММИ - аппроксимированное мультитоновое монохромное изображение

АП - аппроксимирующая палитра

ВС - взвешенное сечение

ВФ - вероятностные факторы

ВЦИ - векторное цифровое изображение

ГА - генетический алгоритм

ГАО - гибридный алгоритм оптимизации

ГХС - генно-хромосомная структура

ИП - исходная палитра

ИЧДЯ - исходная частотная диаграмма яркости КПИ - количество поисковых итераций КПТ - координатно-пиксельно-тоновая КС - к-средних

КТЧ - координатно-тоново-частотная

КФ - количественные факторы

ММ - математическая модель

ММИ - мультитоновое монохромное изображение

МС - медианное сечение

МЭГА - модифицированный эволюционно-генетический алгоритм ОГ - опорные границы

ОММИ - оригинальное мультитоновое монохромное изображение

ПБЭ - поиск ближайшего экстремума

ПС - программное средство

ПФЭ - полный факторный эксперимент

РЦИ - растровое цифровое изображение

СЕО - сканирование единичной окрестности

СКО - среднее квадратическое отклонение

СМО - среднее модульное отклонение

СП - стандартная палитра

СТЗ - система технического зрения

ТА - тоновая аппроксимация

УП - унитоновое покрытие

ФР - функция Растригина

ЦИ - цифровое изображение

ЧДЯ - частотная диаграмма яркости

ЭГА - эволюционно-генетический алгоритм

ЭЧДЯ - поэлементная частотная диаграмма яркости

Введение диссертации (часть автореферата) на тему «Метод и алгоритмы гибридной оптимизации тоновой аппроксимации растровых монохромных изображений»

ВВЕДЕНИЕ

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

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

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

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

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

Степень разработанности темы исследований. Рассматриваемая задача возникла в 80-е годы, когда основная необходимость ТА была вызвана аппаратными ограничениями цифровых устройств. Тогда P. Heckbert предложил детерминированный алгоритм т.н. медианного сечения, который стал популярен в связи с простотой реализации и высокой скоростью вычисления. На этой основе были предложены различные модификации, составившие класс методов «сечения» (работы S. Wan, M. Orchard, C. Bouman, R. Balasubramaian и др.). В задаче ТА широко используется метод кластеризации «k-средних» (S. Lloyd), или «итерации Вороного». В последнее время появилось множество исследований, посвященных усовершенствованию данного подхода (работы E. Celebi, Yu-Chen Hu, М.В. Харинова и др.).

Также широко распространенно использование в задаче ТА популярного метода кластеризации «k-средних» (S. Lloyd), также известного как «итерации Вороного». В настоящее время существуют множество исследований, посвященных усовершенствованию данного подхода (работы E. Celebi, Yu-Chen Hu, М.В. Харинова и т.д.).

Существуют гибридные методы ТА, использующие генетический алгоритма Голдберга и метод k-средних (P. Scheunders, B. Freisleben, A. Schrader). Но они работают с цветными изображениями и аппроксимирующими палитрами высокой размерности, а направлены исключительно на сжатие информации, игнорируя сегментирующие возможности ТА. Можно отметить и метод нейроквант (A. Dekker), основанный на нейронной сети и обеспечивающий высокое качество ТА цветных ЦИ, но с существенными вычислительными затратами.

Среди российских исследований выделяются работы М.В. Харинова, посвященные разоработке метода Kh-средних базирующегося на алгоритме k-средних, причем применительно к ММИ. Нужно отметить работы А.А. Большакова, которые посвящены обработке ЦИ 2D и 3D форматов, где используется ТА ММИ, в том числе для распознавания препятствий. У А.А. Большакова есть также работы про обработку массивов сигналов эвристическими алгоритмами оптимизации, используемыми в задачах ТА ММИ.

Работы по оптимизации ТА начаты в ДГТУ Р.А. Нейдорфом и А.А. Скляренко. Они исследовали ТА применительно к ММИ для упрощения их дальнейшей обработки информационными технологиями и техническими средствами. На их основе в настоящем исследовании продолжено развитие идей и методов оптимизации ТА ММИ.

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

Предметами исследования являются математические модели информационных структур, участвующих в ТА (исходного и аппроксимированного ЦИ, их тоновых палитр и частотных диаграмм), а также

этапы процесса ТА, методы и алгоритмы их реализации.

11

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

Исследования показали, что для достижения этой цели необходимо решение следующих научных и практических задач: 1) системно исследовать сущности и закономерности осуществления основных этапов процедуры ТА ММИ для выявления и определения потенциальных возможностей использования наиболее эффективных подходов к решению поставленных задач; 2) разработать адекватные задаче критерии оценки качества тоновой аппроксимации ММИ; 3) обоснованно выбрать наиболее результативные методы оптимизации, которые позволят на основе разработанных критериев достигнуть основной цели диссертационного исследования; 4) разработать метод и алгоритм реализации оптимизирующей ТА ММИ на основе разработанных критериев; 5) разработать программное средство реализации оптимизирующей ТА ММИ, обеспечивающее, как исследовательские, так и технические аспекты решаемых задач.

Основные положения, выносимые на защиту, и их научная новизна:

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

обеспечили результативное решение всех задач, поставленных в диссертационном исследовании.

2. Генно-хромосомная структура (ГХС) для задачи оптимизации ТА, которая отличается от традиционного представления оптимизируемых информационных образов рассматриваемых как хромосомы неотличимые от особей, тем что разделены понятия хромосом - аппроксимирующих палитр, генами которых являются тона исходной палитры, а аллели задаются подмножествами унитонового покрытия (УП), формируемыми на основе срединных значений между соседними аппроксимирующими тонами. В этом случае роль каждой особи в процессе ТА выполняет матрица - модель соответствующей ММИ, на которую исключено прямое воздействие алгоритма МЭГА. Данная структура прошла испытание и реализована в программе ЭВМ «Субоптимальная аппроксимация монохромных мультитоновых изображений эволюционно генетическим алгоритмом» №2017611901 от 10.02.2017.

3. Использующий эту новую ГХС, и модифицированный под задачу субоптимизации ТА ММИ эволюционно-генетический алгоритм (МЭГА), отличающийся от известных методов решения подобных задач тремя основными отличиями: 1) тем, что первичная популяция формируется на основе срединных значений диапазонов между тонами стартовой АП (хромосомы), полученных делением тонового диапазона интегральной диаграммы яркости на размер АП; 2) тем, что границы унитонового покрытия исходной палитры смещаются в средину диапазона между тонами-генами в процессе их варьирования; а также 3) тем, что на каждом шаге поиска генерируются популяции, которые реализуют эволюционный поиск с различными вероятностными настройками, и для продолжения поиска выбирается лучший результат. Это дало увеличение быстродействия поиска субоптимума на ~40%. Результативность МЭГА подтверждена использованием его для поиска экстремальной области в «Способе тоновой аппроксимации палитры монохромного полутонового изображения», защищенном патентом №2691082 от 10.06.2019.

4. Метод сканирования единичной окрестности (СЕО) АП с целью оценки её экстремальности для аппроксимации ММИ, и основанный на нем метод поиска ближайшего экстремума (ПБЭ) в задаче оптимизации ТА ММИ не имеющие аналогов и использованные основные инструменты «Способа тоновой аппроксимации палитры монохромного полутонового изображения», новизна которого подтверждается патентом №2691082 от 10.06.2019.

5. Гибридный алгоритм оптимизации (ГАО) ТА ММИ, отличающийся от известных методов решения этой задачи тем, что использует комбинированный поиск двумя описанными выше вынесенными на защиту алгоритмами: 1) МЭГА, быстро отыскивающим вероятную область оптимума, и 2) ПБЭ, быстро находящим экстремум в этой области. Это позволяет, согласно экспериментальным данным, в среднем обеспечивать улучшение качества ТА ММИ не менее, чем ~2 3% и до -15016% в зависимости от координатной и яркостной структуры ММИ и сравниваемого алгоритма (модификации к-средних, алгоритм медианного сечения), причем с вероятностью такого улучшения не менее ~93%. Кроме того, ГАО обеспечивает эффект консенсуса качества и скорости аппроксимации, получивший в работе название биоптимальности ТА ММИ. Он реализует «Способ тоновой аппроксимации палитры монохромного полутонового изображения», чья новизна подтверждена патентом №2691082 от 10.06.2019.

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

Теоретическая и практическая значимость. Теоретическим результатом исследования следует считать разработанный метод тоновой аппроксимации ММИ, обеспечивающий близкое к оптимальному по качеству аппроксимирующее преобразование при близких к минимальным временных затратах. Иными словами, предложенный метод позволяет достигнуть результативного, близкого к оптимальному соотношения между точностными и временными критериями при реализации ТА ММИ. Его значимость подтверждается патентом №2691082 от 10.06.2019 «Способ тоновой аппроксимации палитры монохромного полутонового изображения».

Кроме того, в работе получены отдельные теоретические результаты частного порядка: 1) обоснована адекватность и предпочтительность оценки качества для ТА критерия наименьшего модуля отклонения; 2) установлена перспективность аппроксимационной обработки уменьшенного варианта оригинального изображения ввиду малого изменения ЧДЯ и, соответственно, зоны экстремальных структур АП; 3) аналитически и экспериментально обоснована эффективность алгоритма взвешенного сечения (ВС) для получения стартовых подмножеств УП; 4) обоснована необходимость четкого разделения понятий хромосомы и особи в эволюционно-генетическом подходе.

Практическая полезность диссертации подтверждается как указанным патентом, так и созданным и защищенным Свидетельством о регистрации программы для ЭВМ «Субоптимальная аппроксимация монохромных мультитоновых изображений эволюционно генетическим алгоритмом» №2017611901 от 10.02.2017. Кроме того, созданное ПС использовано как ядро для WEB-версии, размещенной по адресу http://imageapproximation.net/, позволяющего решать задачи ТА ММИ широкому кругу пользователей.

Достоверность результатов исследования. Адекватность и достоверность

полученных результатов подтверждают публикации результатов в зарубежных и

российских изданиях, имеющих высокий статус (включены в список ВАК), а также

участие как в зарубежных, так и в российских конференциях. Соответственно,

результаты исследований проходили большое количество рецензирований и, как

правило, получали высокую оценку. Другим подтверждением достоверности

15

являются патент №2691082 и свидетельство о регистрации программы для ЭВМ №2017611901, которые были получены по результатам диссертационной работы.

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

Реализация и внедрение результатов работы. Диссертационное исследование выполнялось по госбюджетной НИОКТР кафедры ПОВТиАС "Разработка метода быстродействующей субоптимизации тоновой аппроксимации мультитоновых монохромных изображений для информационно-управляющих систем объектов беспилотной навигации" по направлению «Системный анализ, управление и обработка информации». Созданный метод оптимизации процедуры тоновой аппроксимации ММИ был реализован в WEB-формате и внедрен как для научно-исследовательского, так и для массового пользования. Также на базе результатов диссертационного исследования был разработан учебно-методический курс «Обработка цифровых изображений» для студентов, внедренный на факультете «Информатика и Вычислительная техника» по направлению «Программное обеспечение вычислительной техники и автоматизированных систем».

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

диссертационной работы докладывались и обсуждались на следующих

конференциях: 10th International Conference on Advanced Computational Engineering

and Experimenting ACE-X 2016 (Croatia, Split, 3-6 July 2016); Proceedings of IEEE

East-West Design & Test Symposium EWDTS 2016 (Armenia, Yerevan, 14-17 Oct.

2016); XII Всероссийская научно-практическая конференция «Перспективные

системы и задачи управления» (Россия, Домбай, 3-7 Апреля, 2017); XXX

Международная научная конференция «Математические методы в технике и

технологиях» ММТТ-30 (Россия, Санкт-Петербург, 29 мая - 2 июня 2017);

Proceedings of IEEE East-West Design & Test Symposium EWDTS 2017 (Serbia, Novi

Sad, 29 Sept. - 2 Oct. 2017); The Eleventh International Conference on Advanced

Engineering Computing and Applications in Sciences ADVCOMP 2017 (Spain,

16

Barcelona, 12-16 Nov. 2017); XXXI Международная научная конференция «Математические методы в технике и технологиях» ММТТ-31 (Россия, Санкт-Петербург, 10 - 14 сентября 2018); Международная научная конференция «Математические методы в технике и технологиях» ММТТ-32 (Россия, Санкт-Петербург, 3-7 июня 2019).

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

Публикации. Результаты диссертационной работы опубликованы в 23 работах, из которых 8 имеют ВАК уровень (5 - опубликованы в российских изданиях, 3 - зарубежных). При этом 4 статьи индексированы в наукометрической базе Scopus и 2 в Web of Science. Из общей доли статей - 8 являются самостоятельными, из них 2 входят в перечень ВАК. В работах выполненных в соавторстве доля вклада составляет от 30 до 80%.

Объем работы. Диссертация содержит введение, 4 главы, заключение, библиографический список из 125 наименований и 23 приложения. Основная часть диссертации изложена на 185 страницах, содержащих 41 иллюстрацию, 9 таблиц и 63 формулы, а приложения занимают 127 страниц.

Соответствие паспорту специальности. Работа выполнена в соответствии с паспортом специальности ВАК при Минобрнауки РФ (технические науки, специальность 05.13.01 - Системный анализ, управление и обработка информации. Ее тематика соответствует пункту 3 - «Разработка критериев и моделей описания и оценки эффективности решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; пункту 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; пункту 5 - «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации»; пункту 12 - «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации.

1 ТОНОВАЯ АППРОКСИМАЦИЯ ИЗОБРАЖЕНИЙ КАК АКТУАЛЬНЫЙ ИНСТРУМЕНТ ОБРАБОТКИ ЦИФРОВОЙ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ

1.1 Цифровые изображения

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

о форма графического представления;

о модель цветовоспроизведения.

1.1.1. Формы графического представления ЦИ

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

Графическое представление РЦИ

В растровой графике построение РЦИ обеспечивается посредством множества точек, именуемых пикселями, различного цвета [1, 2]. Форма пикселей определяется выводящим устройством, но, как правило, пиксель является прямоугольным, либо квадратным [1, 2]. Такой простой графический подход позволяет легко воспроизводить и обрабатывать трудоемкие сцены с высокой степенью загруженности различными объектами. Также попиксельный подход позволяет точно передавать широкую цветовую гамму [1, 2].

При увеличении масштаба РЦИ можно рассмотреть его пиксельную структуру (см. рис. 1.1). На рисунке 1.1 для наглядности отображена сетка,

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

В связи с однозначной

простотой использования РЦИ при

воспроизведении сложных и

нагруженных графических сцен,

этот формат является

общепринятым как в устройствах

ввода/вывода, так и в задачах

^ 1 1 т-т -рчт щ обработки ЦИ. Более того, формат

Рис. 1.1. Пример масштабирования РЦИ ^ ^ > т ^

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

К основным свойствам РЦИ относятся размер изображения, т.е. количество пикселей по ширине и высоте, размерность палитры («глубина цвета или тона») и модель цветовоспроизведения.

Во многих источниках, например, [1, 2], к свойствам РЦИ также относят

разрешение, но это не совсем корректно, т.к. относится не к цифровой структуре

передачи изображения, а, фактически, к уже упомянутому масштабированию. Под

разрешением понимается количество пикселей на единицу площади [1, 2], иначе

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

пикселей повышает визуальное качество РЦИ, поскольку увеличивается четкость

восприятия изображения из-за трудности, а в некоторых случаях и невозможности

19

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

Графическое представление ВЦИ

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

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

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

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

^^^^^^ ^^^^ Однако, описанное преимущество

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

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

Роль цветности в воспроизведении ЦИ

Как указано в преамбуле параграфа 1.1, наряду с формой представления ЦИ, определяемой технологией его формирования и структурой представления изображения на экране, важной характеристикой ЦИ, определяющей его свойства, является используемая палитра [1, 2]. Согласно сложившейся терминологии [1, 2], палитрой называется упорядоченная совокупность воспроизводящих изображение цветовых тонов. При этом могут использоваться тона как одного, так и различных цветов. По этому принципу ЦИ подразделяются на полихромные и монохромные. Под полихромными ЦИ понимаются изображения, чьи палитры оперируют

Список литературы диссертационного исследования кандидат наук Агаджанян Альберт Грантович, 2020 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Абашин, В.Г. Основы растровой графики: учебное пособие для вузов. / В.Г. Абашин - Орел: ОрелГТУ, 2009. - 100 с.

2. Васильев, В.Е. Компьютерная графика: Учеб. пособие. / В.Е. Васильев, А.В. Морозов // - СПб.: СЗТУ, 2005. - 101 с.

3. Pytlarz J., Pieri E., Atkins R. Objectively Evaluating High Dynamic Range and Wide Color Gamut Color Differences // SMPTE Motion Imaging Journal, 2017. - Vol. 126. Pp. 27-32.

4. Jayashree A.R. RGB to HIS color space conversion via MACT algorithm // International Conference on Communication and Signal Processing. - 2013. - Pp. 561565.

5. Недзьведь, О.В. Оптика глаза. Основы биофизики зрения: учеб.-метод. пособие / О. В. Недзьведь, В. Г. Лещенко // - Минск : БГМУ, 2008. - 35 c.

6. Shapiro L., Stockman G. Computer Vision // - Prentice Hall PTR. - 2001. - 609 p.

7. Kanan C., Cottrell G. Color-to-Grayscale: Does the Method Matter in Image Recognition? // PLoS One. - 2012. - Vol. 7. URL: https://doi.org/10.1371/journal.pone.0029740 (дата обращения: 21.07.2018).

8. Левашов В. Лекции по истории фотографии. Тримедия Контент. - М: 2014. - 680 с.

9. Ежова, К.В. Моделирование и обработка изображений. Учеб. пособие. / К.В. Ежова - СПб: НИУ ИТМО, 2011. - 93 с.

10. Тропченко А.Ю. Методы вторичной обработки изображений и распознавания объектов. Учебное пособие. - СПб: СПбГУ ИТМО, 2012. - 234с.

11. Pratt W. Intoduction to Digital Image Processing // - CRC:Press. - 2013. - 756 p.

12. Визильтер Ю.В., Желтов С.Ю., Князь В.А., Ходарев А.Н., Моржин А.В. Обработка и анализ цифровых изображений с примерами на LabVIEW IMAQ Vision // - ДМК Пресс. - 2008. - 464 с.

13. Sangwine S., Horne R. The Colour Image Processing Handbook // - SpringerVerlag Berlin, Heidekberg. - 1998. - 425 p.

14. Brun L., Tremeau A. Digital Color Imaging Handbook // The Electrical Engineering and Applied Signal Processing Series. - NYC: CRC Press. - 2003. - 764 p.

15. Emre C. Improving the Performance of K-Means for Color Quantization // Image and Vision Computing. - 2011. - Vol. 29. - Pp. 260-271.

16. Burger W., Burge M. Color Quantization // Digital Image Processing. Texts in Computer Science. - London: Springer. - 2016. - Pp. 329-339.

17. Yue X.D., Miao D.Q., Cao L.B., Wu Q., Y.F. Chen An efficient color quantization based on generic roughness measure // Pattern Recognition. - 2014. - Vol. 47. - Pp. 1777-1789.

18. Hu Y.-C., Chen W.-L., LO C.-C., Chuang J.-C. Improved vector quantization scheme for grayscale image compression // Opto-Electronics Review. - 2012. - Vol. 20. - Pp. 187-193.

19. Ramirez E., Jimenez O., Perez A., Pogrebnyak O. Grayscale Image Segmentation Based on Associative Memories // Computations in Systems. - 2011. - Vol. 15. - Pp. 149-162.

20. Харинов М.В. Обобщение трех подходов к оптимальной сегментации цифрового изображения // Труды СПИИРАН. - 2013. - Вып. 25. - С. 294-316.

21. Kharinov M. Reclassification formula that provides to surpass K-means method // Computer Vision and Pattern Recognition. - 2012. - URL: https://arxiv.org/ftp/arxiv/papers/1209/1209.6204.pdf (дата обращения: 02.07.2018).

22. Деревянкина А.А. Автоматизация исследования изображений методом s-аппроксимации // Математически13е методы в технике и технологиях (ММТТ) - сб. тр. XXIII Междунар. науч. конф.: в 12 т. Т. 6. Секции 6,7/ под общ. ред. В .С. Балакирева.- Саратов: СГТУ. 2010. - С. 37-43.

23. Bruni V., Ramella G. and Vitulano D. Automatic Perceptual Color Quantization of Dermoscopic Images // In Proceedings of the 10th International Conference on Computer Vision Theory and Applications. - 2015. - Pp. 323-330.

24. Hu Z., Su Q., Xia X. Multiobjective Image Color Quantization Algorithm Based on Self-Adaptive Hybrid Differential Evolution // Computational Intelligence and Neuroscience. - 2016. - Pp. 1-12.

25. Nugroho A.K. Image Quantization in Psoriasis Using K-Mean Clustering //

Transformasi Teknologi untuk Mendukung Ketahanan Nasional. - 2018. - Vol. 4. Pp. 183-189.

188

26. Bing S., Zhixiong Z., Pengbo W. The Influence of Sar Image Quantization Method on Detection Precision // IGARSS 2018 - 2018 IEEE International Geoscience and Remote Sensing Symposium. - 2018. - Pp. 33-36.

27. Paulson C., Wilson J. Lewis T. Synthetic aperture radar quantized grayscale reference automatic target recognition algorithm // Algorithms for Synthetic Aperture Radar Imagery XXV. - 2018. - DOI: 10.1117/12.2318551.

28. Bakht A., Sami R., Fakhre A. Automated differential blood count using image quantization // Journal ofMedical Sciences (Peshawar). - 2017. - Vol. 25. - No. 4. - Pp. 457-462.

29. Nolan A., Goley S. Analytic performance model for grayscale quantization in the presence of additive noise // Proceedings of SPIE - The International Society for Optical Engineering. - 2011. - DOI: https://doi.org/10.1117/12.884131.

30. Neydorf R.A., Aghajanyan A.G., Vucinic D. Monochrome Multitone Image Approximation on Lowered Dimension Palette with Sub-optimization Method based on Genetic Algorithm // Springer, Improved Performance of Materials. - Springer International Publishing. - 2018. - Pp. 144-154.

31. Neydorf R.A., Aghajanyan A.G., Vucinic D. Monochrome multitone image approximation with low-dimensional palette // IEEE East-West Design & Test Symposium (EWDTS). - 2016. - Pp. 1-4.

32. Нейдорф Р.А., Агаджанян А.Г. Исследование аспектов возможного применения субоптимальной тоновой аппроксимации изображений в задачах технического зрения средств автономной навигации // Известия ЮФУ, Технические науки. Таганрог: Изд-во ТТИ ЮФУ. - №1-2 (186-187). - 2017. - С.133-145.

33. Нейдорф Р.А., Агаджанян А.Г., Нейдорф А.Р. Оптимизация результатов аппроксимации растровых изображений и оценка их экстремальности // Математические Методы в Технике и Технологиях. Саратов: СГТУ и. Ю.А. Гагарина. - 2017. - Том 1. - С. 19-26.

34. Neydorf R.A., Aghajanyan A.G., Vucinic D. A high-speed hybrid algorithm of monochrome multitone images approximation // IEEE East-West Design & Test Symposium (EWDTS). - 2017. - Pp. 1-4.

35. Neydorf R.A., Aghajanyan A.G., Vucinic D. Improved Bi-optimal Hybrid Approximation Algorithm for Monochrome Multitone Image Processing // ADVCOMP 2017, The Eleventh International Conference on Advanced Engineering Computing and Applications in Sciences. IARIA. - 2017. - Pp. 20-25.

36. Paul Heckbert Color image quantization for frame buffer display // SIGGRAPH '82 Proceedings of the 9th annual conference on Computer graphics and interactive techniques. - Boston, Massachusetts, USA: ACM. - 1982. - Pp. 297-307.

37. Kobayashi H., Iwahashi M., Kiya H. Weighted median cut quantization and its applications // 2012 International Symposium on Intelligent Signal Processing and Communications Systems. - 2012. - Pp. 509-514.

38. Sae-Tang W., Sugiyama M. Non-separable weighted median-cut quantization for images with sparse color histogram // 2012 International Symposium on Intelligent Signal Processing and Communications Systems. - 2012. - Pp. 473-478.

39. Bouman, C., Orchard M. Color quantization of images // IEEE Trans. Signal Processing. - 1991. Vol. - 39(12). - Pp. 2677-2690,

40. Balasubramaian R., Bouman C. A. and Allebach, J. Sequential scalar quantization of color images // J. Electronic Imaging. - 1994. - Vol. 3(1). - Pp. 45-59.

41. Wan S., Wong S. and Prusinkiewicz P. An algorithm for multidimensional data clustering // - ACM Trans. Mathematical Software. - 1988. - Vol. 14(2). - Pp. 153-162.

42. Fletcher, P., A SIMD parallel colour quantization algorithm // Comput. Graphics. - 1991. - Vol. 15(3). Pp. 365-373.

43. Gervautz M. and Purgathofer, W. A simple method for color quantization: octree quantization // in N. Magnenat-Thalmann and D. Thalmann, Eds., New Trends in Computer Graphics. - Springer-Verlag, New York. - 1988. - Pp. 219-231.

44. Llyod, S. P., Least squares quantization // IEEE Trans. - 1982. Pp. 129-137.

45. Scheunders P. A Genetic C-Means Clustering Algorithm Applied To Color Image Quantization. Pattern Recognition. - 1997. - Vol. 30. - Pp. 859-866.

46. Goldberg David. Genetic Algorithms in Search, Optimization and Machine Learning // - Addison-Wesley Professional. - 1989. - 372 p.

47. Freisleben B., Schrader A. Color Quantization With A Hybrid Genetic Algorithm // Sixth International Conference on Image Processing and Its Applications. -1997. - Pp. 86-90.

48. Dekker A. Kohonen neural networks for optimal colour quantization // Network Computation in Neural Systems. - 2009. - Vol. 5. - Pp. 351-367.

49. Гантмахер Ф. Р. Теория матриц. - 5-е изд. - М.: ФизМатЛит, 2004.- 560 с.

50. Черушева, Т. В. Алгебра матриц: учеб. пособие / Т. В. Черушева, О.Б. Васюнина - 2-е изд., перераб. и доп. - Пенза: Изд-во ПГУ, 2010. - 61 с.

51. Banerjee S. Mathematical Modeling: Models, Analysis and Applications // -Chapman and Hall/CRC. - 2014. - 276 p.

52. Heilio M., Lahivaara T. Mathematical Modelling // - Springer International Publishing. - 2016. - 242 p.

53. Cunningham D. Set Theory: A First Course // - Cambridge University Press, 1 ed. - 2016. - 262 p.

54. Halmos P.R. Naive Set Theory // - Springer-Verlag New York. - 1974. - Pp. 104. - DOI: 10.1007/978-1-4757-1645-0.

55. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. - М.: МЦНМО, 2012. - 112 c.

56. Сабурова, Н.Ю. Множества, отношения, функции: учеб. пособие / Н.Ю. Сабурова. - Архангельск: Арханг. гос. тех. ун-т, 2008. - С. 80.

57. Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. - 2-е изд., испр. - М.: Физматлит, 2001. - С. 320.

58. Коржов Е.Н. Математическое моделирование: учебное пособие. -Воронеж: ИПЦ ВГУ, 2012. - 74 с.

59. Скляренко А.А. Методы решения задачи попиксельной S-аппроксимации мультитоновых изображений и их оптимизация: диссертация кандидата технических наук. Донской государственный технический университет, 2012.

60. Hassan M., Bhagveti C. Evaluation of image quality assessment metrics: color quantization noise // International Journal of Applied Information Systems (IJAIS). -2015. - Vol. 9. - DOI: 10.5120/ijais15-451367

191

61. Агаджанян А.Г. Задачи и методы тоновой аппроксимации растровых монохромных мультитоновых изображений [Электронный ресурс] // Инженерный вестник Дона. - 2018. - №23. - URL: http: //ivdon.ru/ru/magazine/archive/n3y2018/5169

62. Вентцель Е.С. Исследование операций: задачи, принципы, методология // - М: Наука. - 1980. - C. 208.

63. Boyd S., Vandenberghe L. Convex Optimization // - Cambridge University Press. - 2004. - 730 p.

64. Гребенникова И.В. Методы оптимизации: учебное пособие / И.В. Гребенникова. - Екатеринбург: УрФУ, 2017. - 148 с.

65. Костин В.Н., А.Н. Калинин. Методы оптимизации в примерах и задачах: учебное пособие. - Оренбург: ОГУ, 2008. - 153с.

66. Mitchell, M. An Introduction to Genetic Algorithms // Massachusetts Institute of Technology. - USA: Fifth printing 2011 (reissue). - 2011. - 162 p.

67. Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик // - 2-е изд., испр. и доп. М.: ФИЗМАТЛИТ, 2006. - С. 320.

68. Luke, S. Essentials of Metaheuristics [Электронный ресурс] / S. Luke - Lulu, 2013. - URL: https://cs.gmu.edu/~sean/book/metaheuristics/Essentials.pdf.

69. Курейчик, В.М. Генетические алгоритмы и их применение / В.М. Курейчик - Таганрог: ТРГУ, 2002. - С. 244.

70. Pohlheim H. Evolutionary Algorithms: Overview, Methods and Operators // GEATbx Introduction. - 2006. - 79 p.

71. Du K.-L., Swamy M.N.S. Search and Optimization by Metaheuristics. Techniques and Algorithms Inspired by Nature // - Springer, 2016. - 437 p.

72. Лопатин А. С. Метод отжига // Стохастическая оптимизация в информатике : межвуз. Сб. СПб. : Изд-во СпбГУ, 2005. Вып. 1. С. 133-149.

73. Marco Dorigo and Thomas St ' utzle. Ant colony optimization // - A Bradford Book, First Printing edition. - 2004. - 319 p.

74. M. James. Ant colony optimization.Test Run // In: The Microsoft Journal for Developers, MSDN Magazine. - 2012. - Pp.70-74.

75. Rechenberg, I. Evolutionsstrategie — Optimierung technischer Systeme nach Prinzipien der biologischen Evolution // - Ingo Rechenberg - Stuttgart: Frommann-Holzboog-Verlag, 1973. - C. 170.

76. Fogel, L.J. Biotechnology: Concepts and Applications // L.J. Fogel - N.J.: Prentice-Hall, 1963. - 514 p.

77. Holland, J.H. Adaptation in natural and artificial systems // J.H. Holland -Michigan: University of Michigan Press, Ann Arbor, 1975. - 232 p.

78. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

79. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского. -М.: Горячая линия -Телеком, 2006. - 452 c.

80. Четвериков, С.С. О некоторых моментах эволюционного процесса с точки зрения современной генетики / С.С. Четвериков - Классики современной генетики. - М.: Наука, 1968. - С. 52.

81. Гродницкий, Д.Л. Две теории биологической эволюции / Д.Л. Гродницкий // - Саратов: Изд-во «Научная книга», 2002. - С. 160.

82. Карузина И.П. Учебное пособие по основам генетики / Издание второе, стереотипное - Москва: Медицина, 1980 - с.224

83. Инге-Вечтомов, С.Г. Генетика с основами селекции / С.Г. Инге-Вечтомов - СПб.: Изд-во Н-Л, 2010. - С. 720.

84. Rastrigin, L.A. Systems of Extreme Control / L.A. Rastrigin - M.: Nauka, 1974. - P. 316.

85. Агаджанян, А.Г. Исследование эффективности эволюционного подхода при решении задач континуальной оптимизации / А.Г. Агаджанян, Р.А. Нейдорф // Omega Science, 2015. - №63. - C. 9-11.

86. Мясников, А.С. Островной генетический алгоритм с динамическим распределением вероятностей выбора генетических операторов [электронный ресурс] / А.С. Мясников - ФГБОУ ВПО «МГТУ им. Н.Э. Баумана», 2010. Режим доступа: http://engineering-science.ru/doc/ 136503.html, свободный.

193

87. Агаджанян, А.Г. Параметрическая настройка эволюционно-генетического алгоритма на решение задач континуальной оптимизации / Агаджанян А.Г., Нейдорф Р.А. // Проблемы управления, обработки и передачи информации (УОПИ-2015): сб. тр. IV Междунар. науч. конф.: в 2 т. Саратов: Издательский дом «Райт-Экспо», 2015. - Т. 1. - С. 191-196.

88. Агаджанян А.Г. Экспериментальное исследование эффективности применения классического эволюционно-генетического алгоритма в континуальных задачах на примере исследования функции Растригина // Юбилейная конференция студентов и молодых ученых, посвященная 85-летию ДГТУ [Электронный ресурс]: сборник докладов научно-технической конференции (Ростов-на-Дону, 12-13 мая 2015 г.) — Ростов н/Д:ДГТУ, 2015. - С. 2016-2021.

89. Агаджанян А.Г. Влияние степени агрессивности мутационной стратегии на поисковую эффективность эволюционно-генетического алгоритма при решении континуальных задач / Агаджанян А.Г. // Системный анализ, управление и обработка информации: сб. тр. VI Междунар. науч. конф.: — Ростов н/Д: ДГТУ, 2015. - С. 146-149.

90. Агаджанян, А.Г. Оптимизация аппроксимации монохромных мультитоновых изображений эволюционно-генетическим алгоритмом / А.Г. Агаджанян, Р.А. Нейдорф // Omega Science, 2016. - №108. - С. 11-17.

91. Eshelman, L.J. The CHC adaptive search algorithm: how to safe search when engaging in non traditional genetic recombination // In Foundations of Genetic Algorithms. - 1991. - Pp. 265-283.

92. Collet P., Jean-Philippe R. Stochastic Optimization Algorithms / Handbook of Research on Nature Inspired Computing for Economics and Management Hershey. -2006. - 19 p.

93. Агаджанян А.Г. Анализ влияния вероятностных параметров настройки эволюционно-генетического алгоритма на результативность оптимизационной аппроксимации изображений // Техника и технологии: курс на инновации: сборник материалов международной научно-практической конференции - Иркутск: «Научное партнерство Апекс», 2017. - C. 49-57.

194

94. Нейдорф Р.А. Филиппов А.В., Ягубов З.Х. Перестановочный алгоритм биэкстремального решения однородной распределительной задачи. (статья). Вестник Дон. гос. техн. ун-та. - 2011. - Т. 11. С. 655-666.

95. Гурьянова К.Н. Математический анализ [учеб. пособие] / К. Н. Гурьянова, У. А. Алексеева, В. В. Бояршинов // М-во образования и науки Рос. Федерации, Урал. федер. ун-т. — Екатеринбург : Изд-во Урал. ун-та, 2014. - 330 с.

96. Predoi M. Mathematical analysis: Differential calculus // Editura Universitaria. - 2005. - 273 p.

97. William F. Trench. Introduction to Real Analysis // Faculty Authored and Edited Books. - 2013. - 587 p.

98. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. - М.: Наука, 1976. - 280 с.

99. Реброва И.А. Планирование эксперимента: учебное пособие. - Омск: СибАДИ, 2010. - 105 с.

100. Нейдорф Р.А., Агаджанян А.Г. Дуальная оптимизация тоновой аппроксимации монохромных изображений параллельным эволюционно-генетическим поиском // Труды СПИИРАН. 2018. Вып. 60. C. 156-188.

101. С. Е. Столяр, А. А. Владыкин. Информатика: Представление данных и алгоритмы. — СПб.: Невский Диалект; М.: БИНОМ. - 2007. - 382 с.

102. Токарев В. А., Хлуденев А. В. Оценка эффективности алгоритмов цифровой обработки сигналов при конвейерной реализации [Электронный ресурс] // Огарев-online. - 2015. - №20. - Режим доступа: http: //j ournal .mrsu.ru/arts/ocenka-effektivnosti-algoritmov-cifrovoj-obrabotki-signalov-pri-konvejernoj-realizacii

103. Pan X., Zhang T. Comparison and Analysis of Algorithms for the 0/1 Knapsack Problem // Journal of Physics Conference Series. - 2018. - Vol. 1069. - URL: http://iopscience.iop.org/article/10.1088/1742-6596/1069/1/012024/pdf

104. University of Southern California [электронный ресурс]: Signal and Image Processing Institute, Collection of testing images. - Электрон. дан. - Режим доступа: http://sipi.usc.edu/database/database.php (дата обращения: 04.08.2018).

105. University of Cambridge [электронный ресурс]: Cambridge University Computer Laboratory, Database of faces. - Электрон. дан. - Режим доступа: https://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html (дата обращения: 04.08.2018).

106. Нейдорф Р. А., Агаджанян А.Г. Сравнительное исследование гибридного алгоритма оптимальной тоновой аппроксимации монохромных изображений // Наукоемкие технологии в космических исследованиях Земли. 2018. Т. 10. № 5. С. 64-74.

107. Агаджанян А.Г. Оптимальная тоновая аппроксимация монохромных изображений двухэтапным гибридным алгоритмом // Математические методы в технике и технологиях: сб. тр. Междунар. науч. конф.: в 12 т. Т. 8 / под общ. Ред. А. А. Большакова. - СПб.: Изд-во Политехн. Ун-та, 2018. С. 73-77. /

108. Агаджанян А. Г. Быстродействующий алгоритм оптимизации тоновой аппроксимации монохромных растровых изображений // Прикаспийский журнал: управление и высокие технологии. — 2018. — №2. — Стр. 95-103.

109. Шорохова, И.С. Статистические методы анализа: [учеб. пособие] / И. С. Шорохова, Н. В. Кисляк, О. С. Мариев; М-во образования и науки Рос. Федерации, Урал. федер. ун-т. — Екатеринбург: Изд-во Урал. ун-та, 2015. — 300 с.

110. Макконнелл С. Совершенный код. Мастер-класс / Пер. с англ. — М.: Издательство «Русская редакция», 2010. — 896 стр.

111. Bass L., Clements P., Kazman R. Software architecture in practice (3rd ed.) // SEI series in software engineering. 2012. 662 p.

112. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. П75 Приемы объектно-ориентированного проектирования. Паттерны проектирования. — СПб: Питер, 2001. — 368 с.:

113. Petricek T., Skeet J. Real-World functional programming with examples in F# and C#. 2009. 560 p.

114. Гудов, А.М. Технология разработки программного обеспечения [Электронный ресурс]: электронный учебно-методический комплекс / А. М. Гудов, С. Ю. Завозкин, С. Н. Трофимов; Федеральное агентство по образованию, ГОУ

196

ВПО "Кемеровский гос. ун-т", Каф. ЮНЕСКО по новым информационным технологиям. - Кемерово: Кемеровский гос. ун-т, 2009. - Режим доступа: http://unesco.kemsu.ru/study work/method/po/UMK/Dop mat/Pdf/trpo learning book. pdf (дата обращения: 11.01.2019).

115. Jacobson I., Ng P.-W., McMahon P., Spence I., Lidman S. The essence of software engineering: Applying the SEMAT Kernel // - Addison-Wesley Professional. -2013. - 352 p.

116. Якунин, Ю.Ю. Технологии разработки программного обеспечения. Версия 1.0 [Электронный ресурс]: электрон. учеб. пособие / Ю. Ю. Якунин. -Электрон. дан. (3 Мб). - Красноярск ИПК СФУ, 2008. - (Технологии разработки программного обеспечения: УМКД № 183-2007 / рук. творч. Коллектива Ю. Ю. Якунин). - 1 электрон. опт. диск (DVD). - Систем. требования: Intel Pentium (или аналогичный процессор других производителей) 1 ГГц; 512 Мб оперативной памяти; 3 Мб свободного дискового пространства; привод DVD; операционная система Microsoft Windows 2000 SP 4 / XP SP 2 / Vista (32 бит); Adobe Reader 7.0 (или аналогичный продукт для чтения файлов формата pdf).

117. Фримен Э., Робсон Э., Сьерра К., Бейтс Б. Head First. Паттерны проектирования. Обновленное юбилейное издание. - СПб.: Питер, 2018. - 656 с.

118. Duffy J., Slutter H. Concurrent programming on Windows // - Published by Addison-Wesley Professional. - 2008. - 958 p.

119. Рихтер Дж. CLR via C#. Программирование на платформе Microsoft .NET Framework 4.5 на языке C#. 4-е изд. — СПб.: Питер, 2013. — 896 с.: ил. — (Серия «Мастер-класс»).

120. Скит Д. С# для профессионалов: тонкости программирования, 3-е изд. : Пер. с англ. — М.: ООО "И.Д. Вильямс", 2014. - 608 с.

121. Троелсен Э. Язык программирования C# 5.0 и платформа .NET 4.5, б-е изд.: Пер. с англ. - М.: ООО "И.Д. Вильямс", 2013. - 1312 с.

122. Brat De Smet. C# 5.0 Unleashed // - Indianapolis (US): Person Education, -2013. - 1700 p.

123. Microsoft developer network (MSDN) [электронный ресурс]: Full information of .NET's library. - Режим доступа: https://docs.microsoft.com/ru-ru/dotnet/csharp/

124. Albahari J., Albahari B. C# 6.0 in a Nutshell, 6th edition // - Reilly Media, 2015. - 1133 p.

125. Mark J. Price. C# 7.1 and .NET Core 2.0 - Modern Cross-Platform Development - Thrid Edition // - Packt Publishing, 2017. - 800 p.

ПРИЛОЖЕНИЕ А.1

A.1. Популярные модели цветовоспроизведения ЦИ

Модель цветовоспроизведения RGB

Модель RGB (аббревиатура: Red - красный, Green - зеленый, Blue - синий) имеет самое широкое распространение и используется большинством технических устройств. Воспроизведение цвета в данной модели заключается в смешении трех цветов, которые и формируют название самой модели ^м. рис. 1.3). Этот подход фактически повторяет принцип восприятия цвета сетчаткой человеческого глаза, который имеет три типа так называемых «колбочек», разделяющихся на красный, зеленый и синий [5]. Таким образом, с позиции биофизики зрения данная модель наиболее соответствует естественному цветовоспроизведению.

В стандартном цифровом виде значения R, G и B представляются в целочисленной форме от 0 до 255, где 0 наименьшая интенсивность цвета, а 255 -наибольшая. Также возможен вариант представления от 0 до 1 для каждого цветового канала, но для простоты, как правило, используется именно

целочисленная градация. На рисунке 1.4 проиллюстрирован переход от красного к зеленому цвету с указанием координатного значения цвета согласно модели RGB в формате (R, G, B).

Рис. 1.3. Цветовая модель RGB

Рис. 1.4. Визуальное и численное представление цвета Модель цветовоспроизведения CMYK Название CMYK, как и в случае с RGB, состоит из первых букв

используемых цветовых каналов (С - сине-зелёный, M - пурпурный, Y - желтый и

199

K - черный). Если модель RGB предполагает сложение световых лучей, то модель CMYK является субтрактивной, т.е. для получения определенного цвета исключаются (поглощаются) все остальные. Субтрактивная схема рассчитана на использование в типографии.

Основные цветовые каналы были подобраны с целью достижения максимального диапазона различных цветов при субтрактивной схеме. В модели CMYK показатели канала измеряются в процентах используемой краски. Классический вариант предполагает оперирование в цифровом виде градацией от 0 до 100. Необходимо отметить, что весь спектр цветов получается путем смешивания основных трех каналов. Черный же канал был добавлен учитывая специфику данной модели, поскольку при максимально (100%) пропорциональном смешивании основных трех цветов модели CMYK невозможно получить реально черный цвет (скорее темно-коричневый) [2]. Также имеют место быть проблемы с деформацией бумаги при получении черных оттенков в связи с задействованием большой массы краски всех трех цветов [2].

Модель цветовоспроизведения HSB

Аббревиатура HSB расшифровывается как H - цветовой тон, S -насыщенность и B - яркость. В классической форме модель HSB предполагает диапазон цветового тона в пределах от 0 до 360 градусов (цилиндрическое представление), а насыщенность и яркость от 0 до 100. Тем не менее могут применяться и другие цифровые кодировки, но в любом случаи необходимо осуществлять перевод в модель RGB или CMYK, что является недостатком модели HSB [2]. Данная модель концептуально отличается от предыдущих и считается наиболее интуитивно понятной человеку, что обеспечило модели HSB распространенность в графических редакторах.

Интуитивная простота заключается в том, что пользователь последовательно выбирает три компоненты - желаемый цвет, его насыщенность и яркость, тогда как модель RGB и CYMK представляют собой большое координатное пространство, которое затруднительна в восприятии по сравнению с рассматриваемой моделью.

ПРИЛОЖЕНИЕ А.2

А.2. Сравнительное исследование эффективности стандартных методов ТА ММИ

А.2.1. Постановка задачи сравнительного исследования методов ТА монохромных РЦИ

Для выполнения экспериментального исследования необходимо:

1. проработка или выбор уже существующих критериальных показателей для оценки уровня эффективности тестируемых методов ТА ММИ;

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

3. выполнение плана экспериментального исследования и проведения соответствующего анализа итоговых результатов;

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

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

А.2.2. Критериальная основа сравнения стандартных методов ТА ММИ

Эффективность алгоритмов ТА изображения необходимо оценивать, как минимум, по двум критериям: качеству аппроксимации (предметному) и времени ее выполнения (ресурсному).

Для предметной оценки качества ТА необходим объективный числовой критерий, оценивающий отклонение аппроксимирующих тонов от исходных. Наиболее естественной оценкой является суммарная или усреднённая (на один пиксель) ошибка тонового воспроизведения исходного ИММ его аппроксимированным вариантом. Как правило, для такой оценки используется

среднеквадратичное отклонение между одинаковыми пикселями исходного и аппроксимированного изображения [13, 14].

В упрощенном цифровом виде любое РЦИ можно представить, как матрицу, т.е. координатно двумерное множество следующего вида:

Рп,т = (РыЛ (А.1)

где I - номер строки, у - номер столбца, п, т - их размеры, а к для аппроксимируемого ММИ - индекс яркостного тона пикселя р в векторе тонов, образующих его палитру. Этот индекс определен двумерной пространственной структурой изображения, т.е. индексами I и у. Таким образом, математическая модель ММИ является трехмерной, причем третья координата факторного пространства модели является не пространственной, и имеет размерность яркости тона, как физической величины.2

Используя ММ вида (1.1) квадратичное отклонение кр тонов координатно идентичных элементов матрицы аппроксимированного и исходного изображений можно выразить следующей формулой:

ТТр = ^^(Шц-Ш,)2 (А-2)

где а индекс аппроксимированного, а о - преобразуемого тона.

Для ресурсной оценки работы алгоритма ТА необходимо измерять время, затрачиваемое на его выполнение, которое зависит от количества и структуры реализуемых операций над входными данными. Как правило, время алгоритма работы Т имеет некоторую зависимость f от входных данных:

Т(Ы, Ба, с) = Ба, С), (А.3)

где N - общее количество пикселей изображения, б а - размер АП, б° - размер ИП, а С - некоторое множество настроечных величин обрабатывающего алгоритма, которое может быть пустым.

Аналитически установить характер этой зависимости зачастую затруднительно, в связи с объективно существующей сложностью аналитической

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

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

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

А.2.3. Задачи и способы экспериментального сравнительного исследования методов ТА ММИ

В предыдущих параграфах было показано, что основным эталоном для оценки эффективности алгоритмов ТА целесообразно использовать метод к-средних, поскольку этот алгоритм является популярным инструментом решения этой задачи [15]. Кроме того, часто используются пред-кластерный алгоритм медианного сечения (МС) ввиду простоты его реализации [10]. Поэтому в качестве сравнительной базы исследования ТА ММИ выбраны именно эти алгоритмы.

Основной проблемой метода к-средних, как было отмечено в параграфе 1.6, является определение стартовой позиции поиска (исходных центроидов). Поэтому

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

о использование АП, полученной алгоритмом медианного сечения (МС), в качестве стартовой точки для метода к-средних (МСК);

о генерация 500 случайных АП, но в рамках границ аппроксимирующих тонов, определенных МС, и их последовательная обработка методом к-средних (КС500);

о генерация 5000 случайных АП, но в рамках границ аппроксимирующих тонов, определенных МС, и их последовательная обработка методом к-средних (КС5000);

Второй задачей организации эксперимента является формирование репрезентативной выборки изображений для обработки выбранными для сравнения методами, которая обеспечит оценку влияния на эффективность аппроксимации различных объективных факторов, связанных, в основном, с характером ММИ, координатной и тоновой его структурой и т.п. Количественное значение выборки является одним из факторов статистической мощности (чем выше мощность, тем достовернее результат) проводимого эксперимента. К способам определения адекватного размера выборки можно, например, отнести сопоставление с проведенными раннее исследованиями других научных групп в области решаемой задачи. Так, в исследовании [19] в эксперименте обрабатывалась выборка из 7 изображений, в [18] из 6 изображений, а в [21] и вовсе из одного. Исходя из размеров выборок в исследованиях [18, 19, 21] принято решение проведения сравнительного анализа на основе 30 разнородных ММИ, отобранных случайным образом. Данная размерность адекватна для первичных исследований и, при этом, имеет большую статистическую мощность, нежели в работах [18, 19, 21]. На рисунке 1.16 приведены частотные диаграммы яркости трех изображений из отобранной выборки, которые демонстрируют существенно различное яркостное распределение.

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

204

1.16), а также по размеру (от 600x340 до 1920x1280 пикселей). Все отобранные изображения подверглись ТА выбранными выше методами, с переводом их из исходной стандартной палитры (256 оттенков серого цвета) в аппроксимирующую

3C00

2С00

1C0Q

О 8000

еооо

4000 2000 о

О 50 100 150 200 250

Рис. 1.16. Частотные диаграммы трех ММИ из исследуемой выборки

На первом этапе сравнительного анализа предполагается выявление наименее эффективного алгоритма по среднему показателю качества ТА (А.2) среди установленной выборки. Второй этап подразумевает сравнение всех остальных тестируемых алгоритмов относительно наихудшего, определенного на первом этапе, по следующим показателям: средний процент улучшения качества ТА (т.е. процент минимизации критерия (А.2)), максимальный/минимальный

процент улучшения качества, статистическая вероятность улучшения и затрачиваемое на обработку время.

А.2.4. Экспериментальное сравнение стандартных методов ТА ММИ

Результаты экспериментального исследования с описанными выше параметрами представлены в таблице 1.1. В первом столбце таблицы указаны порядковые номера исследуемых ММИ, во втором столбце «Размер ММИ» указано общее количество пикселей изображения. В последующих столбцах представлены оценки качества ТА ММИ, вычисленные по критерию (А.2), при обработке указанным алгоритмом.

В ячейках, выделенных светло-серым цветом, приведены номера ММИ, которые соответствуют диаграммам яркости, продемонстрированным выше: ММИ №20 (рис. 1.16а), №14 (рис. 1.16Ь), №3 (рис. 1.16с). Наилучше качество ТА, т.е. наименьшее отклонение (А.2), по каждому изображению показано в ячейках, выделенных темно-серым цветом со светлыми цифрами (см. табл. 1.1).

Таблица 1.1. Оценка (А.2) ТА исследуемых методов

№ Размер ММИ МС МСК КС500 КС5000

1 806300 7700,75 7569,00 7594,15 7558,06

2 1920000 8754,11 8517,27 8607,72 8257,52

3 910800 8617,39 8491,23 8487,35 8464,47

4 2457600 13585,36 13376,10 13470,20 13052,12

5 375200 5412,25 4969,44 4967,31 4963,06

6 325500 4536,37 4381,53 4374,31 4354,24

7 523626 6578,47 6559,95 6541,94 6531,69

8 1067008 8557,59 7295,70 7295,70 7288,73

9 252000 4085,91 3945,28 3933,27 3928,83

10 960000 8348,87 7726,43 7726,43 7726,43

11 412300 5279,73 5016,64 5007,76 4995,87

12 204000 3397,71 3312,11 3302,17 3301,66

13 786432 7577,80 7247,60 7227,03 7220,09

14 274181 4640,72 3831,43 3794,27 3792,14

15 1500000 10829,44 10753,78 10599,46 10667,48

16 1204132 8579,50 7176,81 7323,44 6818,18

17 1704000 11961,55 11731,92 11713,18 11716,98

№ Размер ММИ МС МСК КС500 КС5000

18 1705600 11181,86 10444,89 10391,27 10403,11

19 1710400 10851,67 9390,00 9348,36 9323,18

20 3025269 12590,44 12590,44 11896,90 11831,47

21 1221360 9084,78 8855,53 8903,34 8305,31

22 960000 8671,82 8552,67 8425,42 8442,05

23 958800 8916,30 8916,30 8935,06 8916,04

24 2073600 12760,86 12469,09 12469,09 12279,30

25 427200 5925,94 5909,60 5865,27 5747,87

26 1446486 6834,58 6456,13 6007,24 5971,42

27 518400 6061,60 6043,98 6122,06 5999,13

28 614400 6852,52 6606,50 6597,41 6591,35

29 691560 7509,32 7132,72 7121,84 7096,00

30 160000 2719,30 2418,78 2375,91 2361,79

Экспериментальные данные в таблице 1.1 показывают, что метод МС в среднем уступает остальным методам по качеству ТА, что было вполне ожидаемо в связи пред-кластерным принципом обработки. Поэтому эффективность остальных алгоритмов оценивается относительно результатов МС. Процент улучшения качества рассчитывался по следующей формуле:

AQ = (MC~X} *100, (А.4)

где MC - оценка качества ТА методом МС согласно (А.2), а X - оценка сравниваемого с МС метода. Результаты сравнительного исследования продемонстрированы в таблице 1.2.

В среднем предложенные вариации метода ^-средних позволили улучшить результат по сравнению с МС от 5,3% до 7,08%. При этом максимальное улучшение составило 25,8% (для КС5000), а минимальное -0,9% (для КС500), т.е. результат оказался хуже, чем МС (см. табл. 1.2). Однако, следует отметить, что все тестируемые модификации метода ^-средних не менее, чем в 98% (статистическая вероятность) случаев превзошли результат алгоритма МС.

Также отметим, что минимальное улучшение для модификации МСК составило 0%, поскольку этот метод, начинающийся с результата алгоритма МС, не может оказаться хуже своей стартовой точки поиска.

Таблица 1.2. Результаты сравнительного анализа

МСК КС500 КС5000

Среднее улучшение в сравнении с МС 5,39% 5,97% 7,08%

Минимальное улучшение 0% -0,9% 0%

Максимальное улучшение 21,1% 22,3% 25,8%

Вероятность улучшения 98% 98% 100%

Время обработки (мс.) 0,0308 61,3 528,5

Несомненно, максимальное улучшение результата МС при обработке алгоритмом КС500 и КС5000 вызывает интерес и требует дополнительного анализа. Поскольку алгоритм МС базируется на равномерном сечении применительно к ММИ, то, как отмечалось ранее в параграфе 1.3, данный алгоритм оказывается неэффективным при существенно неравномерной частотной диаграмме яркости изображения. Рассмотрим данный эффект на примере изображения №26 (см. табл. 1.1).

На рисунке 1.17 проиллюстрирована уменьшенная копия изображения №26 (в связи с невозможностью демонстрации полного размера в формате А4), а также частотная диаграмма яркости оригинальной версии и аппроксимированной (алгоритмом МС и КС5000). Алгоритм МС, основанный на равномерном сечении, выделяет тон АП на покрытие яркостной зоны, мало использующейся в отображении исходного изображения (см. рис. 1.1 7Ь, выделено красным кругом). Это позволяет корректно отразить лишь некоторые мелкие детали изображения. Но в условиях сильно разряженной палитры (в 256/8 = 32 раза) важно использовать тона АП таким образом, чтобы минимизировать потери изображения в целом. Согласно выбранному критерию оценки (А.2) наибольший приоритет имеют яркостные зоны, чьи тона больше всего используются при отображении ММИ, а значит имеют высокую значимость для воспроизведения изображения. Однако принцип работы метода МС позволил выделить для области наиболее кучной

дислокации исходных тонов лишь два тона аппроксимирующей палитры, а на вторую по значимости зону их дислокации - лишь один (см. рис. 1.17а/Ь).

Структура же АП, полученная алгоритмом КС5000, позволила ссущественно минимизировать потери в сравнении с алгоритмом МС, что объясняется корректным распределением тонов АП на наиболее значимые яркостные зоны изображения (см. рис. 1.17с, выделено зелеными кругами). Алгоритм позволил найти АП, выделяющую на зону с наибольшим количеством тонов три аппроксимирующих тона (в МС лишь два), причем один из них практически совпал с пиком исходной диаграммы (см. рис. 1.17Ь/с). Также видно, что объекты днища истребителя отображаются в основном темными тонами, что наблюдается на частотной диаграмме яркости исходного изображения в участке от 0 до 50 (см. рис. 1.17а). Алгоритм КС5000 определил АП, выделяющую на участок диаграммы от 0 до 50 два тона (в МС лишь один). На низкочастотный средний участок шкалы КС5000 выделил три тона вместо четырех в МС, а на участок минимальной яркости - вообще ни одного (см. рис. 1.17с).

Как было отмечено выше, другим важным критерием оценки алгоритмов ТА является время обработки. Алгоритм ^-средних при модели МСК выполняет один поисковый цикл, что в среднем на исследованной выборке изображений требовало ~30 микросекунд, тогда как обработка большого количества различных АП серьезно повысило вычислительное время относительно МСК (см. табл. 1.2), но обеспечило увеличение качества ТА.

100 150 200 250

Рис. 1.17. Изображение №26 и частотная диаграмма яркости оригинальной версии (а), а также аппроксимированной алгоритмами МС (Ь) и КС5000 (с)

Возможность применения того или иного варианта алгоритма зависит от степени чувствительности области применения к вычислительному времени. При

высокой чувствительности, как правило, точность результата является второстепенным, что делает приемлемым использование алгоритма МС или МСК. Но важно отметить, что и ~61 миллисекунда (КС500), и даже ~528 миллисекунд (КС5000) являются достаточно адекватным затрачиваемым ресурсом для многих областей, в том числе и ряда задач технического зрения.

А.2.5. Достоверность экспериментальных данных и заключительные выводы

Несмотря на то, что статистическая мощность исследования проведенного в пункте А.1.4 выше, чем во многих исследованиях, посвященных рассматриваемой предметной задаче [18, 19, 21], было принято решение увеличить выборку тестируемых ММИ до 100, что позволит оценить степень достоверности полученных результатов. Использованные ранее 30 изображений включены в новую выборку. Результаты сравнительного эксперимента представлены в таблице 1.3, где в скобках указаны данные, полученные при выборке из 30 ММИ.

Таблица 1.3. Результаты сравнительного анализа выборкой из 100 ММИ

МСК КС500 КС5000

Среднее улучшение в сравнении с МС 7,1% 7,6% 8,4%

(5,3%) (5,9%) (7%)

Минимальное улучшение 0% -1,8% 0%

(0%) (-0,9%) (0%)

Максимальное улучшение 61,9% 62,6% 62,6%

(21,1%) (22,3%) (25,8%)

Вероятность улучшения 95% 92% 100%

(98%) (98%) (100%)

Время обработки (мс.) 0,0306 75 512,3

(0,0308) (61,3) (528,5)

Среднее улучшение результата МС при выборке из 100 изображений для МСК составило 7,1%, что на 1,8% больше, чем результат на меньшей выборке. Модификация КС5000 по этому показателю улучшилась на 1,4% и составила 8,4% (см. табл. 1.3).

Как отмечалось ранее, для исследования отбирались различающиеся по всем основным параметрам ММИ, что обуславливает полученные статистические погрешности. Например, этот фактор прослеживается в диапазоне между минимальным и максимальным улучшением, т.е. по некоторым изображениям улучшение близко к нулю, а по другим может достигать более 60% (см. табл. 1.3). Кроме того, КС5000 и КС500, как описано в пункте А.1.3, базируются на случайном характере генерирования стартовых точек поиска, что привело к определенным изменениям исследуемых критериев. Таким образом, результаты, полученные в ходе сравнительного исследования, в целом можно считать достоверными.

ПРИЛОЖЕНИЕ Б.1

С целью проверки правомерности вывода о том, что стратегия использования срединных значений (2.23) и (2.24), позволят определить такие подмножества УП (2.26) и (2.27), которые обеспечат минимум критерия оптимизации (2.34) (поскольку совершается замена аппроксимирующего тона на наиболее близкий исходный), было решено провести экспериментальное исследование.

Эксперимент предполагает генерацию случайным образом двух аппроксимирующих тонов для некоторого ММИ, после чего по принципу срединных значений осуществляется формирование подмножеств УП (2.28) и создается АММИ, которая проходит оценку согласно (2.34). Далее срединная граница подвергается сдвигу на +- 1 единицу и +- 2 единицы. При этом после каждого сдвига формируется АММИ, соответствующая этим подмножествам УП, которая подвергается оценке по (2.34).

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

Для данного исследования было выбрано стандартное для экспериментальных тестов ММИ размерностью 512 на 512. Выбранное изображение, а также ее ЧДЯ и вспомогательные характеристики продемонстрированы на рисунке рис. Б.1.1.

Далее по описанному ранее плану было сгенерировано несколько АП в диапазоне от 0 до 187 (минимальное и максимальное значение для выбранного ММИ (см. рис. Б.1.1)), состоящих из двух тонов. Для этих двух тонов определялись подмножества УП по принципу срединного значений, после чего выполнялись запланированные сдвиги с соответствующей оценкой.

Количество пикселей: 262144 Чэстотно-яркостная диаграмма

Минимальны* тон: 0 2500

Максиматъньй тон: 187 опт

2000

«отчество тонов: 187 Средняя яркость: 91.16962814 1500

1000

500

00 51 102 153 204 255

Рис. Б. 1.1. Характеристики обрабатываемой ММИ Результаты проведенного исследования представлены в таблице Б.1.1, которая состоит из 6 подтаблиц (выделенных толстой внешней линией), где представлены результаты каждой из 6 сгенерированных АП. В подтаблицах демонстрируется оценка (2.34) для срединного значения границ между двумя аппроксимирующими тонами, а также оценки при выполнении соответствующих сдвигов. Для упрощения отслеживания изменения оценки (2.34), в подтаблицах показаны отклонения оценки при выполнении сдвига от оценки при использовании границ на основе срединных значений (если результат отклонения положительный, то значит, что при сдвиге оценка ухудшилась, т.е. суммарное отклонение возросло).

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

Таблица Б.1.1 - Результаты исследования корректности границ УП

АП = (5; 72) Граница Оценка Откл. АП = (151; 159) Граница Оценка Откл.

Срединное: 38,5 9097556 Срединное: 155 15819137

-1 37,5 9099092 1536 -1 154 15819137 0

1+ 39,5 9099059 1503 1+ 156 15821383 2246

-2 36,5 9103772 6216 -2 153 15821815 2678

2+ 40,5 9103580 6024 2+ 157 15825555 6418

АП = (29; 108) Граница Оценка Откл. АП = (20; 138) Оценка Откл.

Срединное: 68,5 5413890 Срединное: 79 6922303

-1 67,5 5415600 1710 -1 78 6922303 0

1+ 69,5 5415635 1745 1+ 80 6926357 4054

-2 66,5 5420808 6918 -2 77 6926035 3732

2+ 70,5 5420684 6794 2+ 81 6934173 11870

АП = (38; 173) Граница Оценка Откл. АП = (104; 135) Граница Оценка Откл.

Срединное: 105,5 9273710 Срединное: 119,5 7396066

-1 104,5 9275743 2033 -1 118,5 7398533 2467

1+ 106,5 9275768 2058 1+ 120,5 7398654 2588

-2 103,5 9281617 7907 -2 117,5 7406183 10117

2+ 107,5 9281987 8277 2+ 121,5 7406316 10250

Необходимо отметить, что для АП (151 ;159), а также АП (20;138) при сдвиге -1 было получено нулевое отклонение. Это связано с двойственной ситуацией, возникающей при случае, когда срединное значение является целочисленным (см. пункт 2.2.4). В этом случае оба аппроксимирующих тона могут заменить исходный тон (он же срединный) с одинаковым отклонением. В ходе исследований было приято инженерное решение, которое при возникновении данной ситуации предполагает замену «спорного» тона в темную сторону (меньшую). Таким образом, при осуществлении сдвига -1, этот тон переходит под покрытие светлого (большего) аппроксимирующего тона, соответственно, отклонение остается неизменным.

Эффект увеличения отклонения (2.34) при выполнении сдвига срединного значения продемонстрирован на графиках, где по оси абсцисс отмечен сдвиг, а по оси ординат возникающие при этом отклонение (см. рис. Б.1.2).

Рис. Б.1.2 Изменение отклонения оценки (2.34) при сдвиге срединного значения

ПРИЛОЖЕНИЕ Б.2

Таблица Б.2.1 - Результаты сравнения критериев по частному показателю

близости к смещению средней яркости ММИ

№ Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8

1 806300 110,00 68,23 109,51 68,74 0,51 7,35 9,17

2 1920000 140,90 43,95 141,59 42,98 -0,98 5,39 8,80

3 910800 104,81 66,25 103,70 65,14 -1,10 8,24 10,13

4 2457600 151,07 52,25 151,53 50,63 -1,62 7,37 9,58

5 375200 79,37 44,55 77,07 42,20 -2,35 7,50 11,20

6 325500 121,48 49,75 121,50 49,56 -0,19 6,58 8,23

7 523626 111,73 56,12 110,31 54,76 -1,36 8,25 10,43

8 1067008 59,05 46,08 57,15 44,97 -1,11 7,10 11,32

9 252000 112,42 53,86 111,57 53,22 -0,64 6,75 8,53

10 960000 77,09 49,28 75,03 47,82 -1,46 7,74 11,66

11 412300 104,35 57,23 102,46 56,67 -0,56 7,70 10,84

12 204000 125,04 69,99 124,70 69,94 -0,05 6,24 8,48

13 786432 92,38 55,24 91,60 54,53 -0,70 7,27 9,59

14 274181 94,53 31,70 93,77 29,38 -2,32 6,13 9,62

15 1500000 130,63 53,32 130,10 52,91 -0,41 7,18 8,66

16 1204132 162,18 20,17 162,64 18,19 -1,98 4,92 9,92

17 1704000 101,36 63,55 100,45 63,96 0,41 7,41 9,83

18 1705600 74,45 39,09 71,29 35,45 -3,64 7,96 14,88

19 1710400 89,12 41,92 88,14 40,82 -1,11 6,03 8,37

20 3025269 110,11 58,71 109,59 59,28 0,57 5,70 7,97

21 1221360 148,66 50,14 149,39 50,47 0,33 6,66 9,52

22 960000 117,52 47,37 116,18 46,18 -1,19 7,63 9,91

23 958800 116,50 59,10 116,15 58,64 -0,46 7,77 9,29

24 2073600 110,20 50,03 108,11 47,16 -2,87 8,06 11,06

25 427200 123,72 52,65 123,08 51,41 -1,24 7,27 9,40

26 1446486 161,31 50,35 160,79 51,91 1,56 4,40 9,40

27 518400 117,18 56,63 116,51 56,41 -0,22 7,28 8,89

28 614400 92,18 50,28 90,54 48,86 -1,42 7,57 10,43

29 691560 97,02 43,43 94,94 40,51 -2,92 7,92 11,74

30 160000 127,89 34,92 127,00 34,43 -0,49 5,05 6,27

В таблице Б.2.1 использованы следующие обозначения:

о Х1 - общее количество пикселей изображения;

о Х2 - средняя яркость ОММИ;

о Х3 - значение (2.36) для ОММИ;

о Х4 - средняя яркость АММИ;

о Х5 - значение (2.36) для АММИ;

о Х6 - отклонение между Х3 и Х5;

о Х7 - оценка АММИ модульным критерием (2.34о);

о Х8 - оценка АММИ квадратичным критерием (2.33);

ПРИЛОЖЕНИЕ Б.3

В.3. Сравнительный анализ квадратичного и модульного критериев оценки качества применительно к пред-кластерным АТА

В.3.1. Анализ причин искажения качества тоновой аппроксимации

Описанный в параграфе 2.2 алгоритм ВС позволит участкам ЧДЯ, содержащим большое количество тонов, получить меньший диапазон покрытия одним аппроксимирующим тоном, а участкам с малым количеством тонов -больший диапазон, поскольку их потенциальная значимость меньше. Рассмотрим пример 8-тоновых АП структур, полученных алгоритмами МС и ВС (см. рис. Б.3.1).

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

Очевидно, что описанный фактор может существенно повлиять на оценку тоновой аппроксимации ММИ при использовании критерия (2.33). При рассмотрении рисунка Б.3.1 видно, что алгоритм ВС на хвостовом участке яркого диапазона (от ~140 до 255) выделяет только один тон, а алгоритм МС выделяет на участок с наибольшим количеством пикселей (т.е. передающим основную часть ММИ) вдвое меньше тонов, чем ВС. Таким образом, эти зоны при критерии (2.33) могут потенциально исказить визуальный результат оценки тоновой аппроксимации, а при критерии (2.34) - существенно исказить передачу мелких деталей изображения.

Рис. Б.3.1. Частотная диаграмма яркости оригинального изображения и двух аппроксимированных на основе алгоритмов МС и ВС

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

В.3.2. Сравнительный анализ алгоритмов ВС и МС на основе квадратичного и модульного критериев оценки качества

Для исследования данных методов обработана выборка из 30 существенно различающихся ММИ. Аппроксимирующие палитры, полученные алгоритмами МС и ВС, для каждого ММИ оценены с помощью критериев (2.33) и (2.34). Результаты аппроксимации ММИ из выборки алгоритмами МС и ВС сопоставлялись их прямым сравнением в относительной форме по формуле:

мс-вс

г =--100

вс

(Б.3.1)

где МС - результат оценки качества АММИ, полученного алгоритмом МС, ВС -результат оценки качества АММИ, полученного алгоритмом ВС.

Согласно формуле (Б.3.1), не отрицательное значение результат х будет указывать на преимущество ВС по сравнению с МС. Количественными оценками преимущества являются:

о среднее по выборке относительное улучшение оценки; о процентная доля улучшения результата МС алгоритмом ВС; о максимальное и минимальное значения оценок; о статистическая вероятность преимущества ВС перед МС. Результаты (Б.3.1) по всем изображениям (в отсортированном порядке) проиллюстрированы на соответствующих графиках (см. рис. Б.3.2, Б.3.3), где по оси абсцисс указаны порядковые номера ММИ, а по оси ординат значение результат 2 (Б.3.1).

На представленных графиках (см. рис. Б.3.2, Б.3.3) отчетливо видно, что в зависимости от использованного критерия оценка качества ТА, результативность алгоритма ВС и МС оценивается существенно разным образом. Так, при квадратичной оценке согласно формуле (Б.3.1), алгоритм ВС имеет преимущество над МС только в двух ММИ (№30 и №15, см. рис. Б.3.3). В связи с этим целесообразно рассмотреть показатели сравнительного анализа более подробно.

Рис. Б.3.2. Оценка (Б.3.1) при критерии (2.34)

Рис. Б.3.3. Сравнительная оценка (Б.3.1) при критерии (2.33)

Обработанные результаты сравнительного эксперимента представлены в таблице Б.3.1. В среднем критерий СМО демонстрирует перевес на 2,8% в сторону алгоритма ВС по качеству ТА по всем 30 ММИ (см. табл. Б.3.1). При этом если рассматривать только улучшение, т.е. положительное значение (Б.3.1), то среднее превосходство составляет 8,39%, тогда как среднее значение проигрыша равняется -3,54%, т.е. ~2,3 раза меньше. Однако, как было отмечено и на графике (см. рис. Б.3.3), при использовании критерия СКО получается совершенно иной результат, причем с существенным превосходством алгоритма МС, а именно -13,6% при использовании формулы (Б.3.1).

Таблица Б.3.1 - Результаты экспериментального сравнения

Количественные показатели эффективности ТА\Критерий Критерий СКО Критерий СМО

В среднем ВС превосходит МС на... -13,6% 2,8%

Максимальное превосходство ВС 8,3% 36,9%

Минимальное превосходство ВС -42,4 -9,5%

Вероятность улучшения результата МС алгоритмом ВС 6,6% 53,3%

Весомым показателем в настоящем эксперименте является статистическая

вероятность улучшения результата МС алгоритмом ВС (см. табл. Б.3.1, строка 5).

Так, согласно оценке СКО статистическая вероятность улучшения результата МС

алгоритмом ВС составила всего 6,6%, тогда как согласно критерию СМО

221

статистическая вероятность этого события составляет уже 53,3% (в 16 из 30 ММИ). Этот факт, как и ранее отмеченные (см. пункты 2.3.3, 2.4.1), указывает, что критерий СМО, вероятно, позволяет получить более адекватные оценки ТА ММИ, учитывая описанный механизм работы алгоритма ВС (см. пункты 2.2.3, 2.4.1).

ПРИЛОЖЕНИЕ С.1

С.1. Исследование возможностей существующих подходов к задачам поисковой дискретной оптимизации

С.1.1. Основные различия в подходах к решению поисковых задач дискретной оптимизации

Основные принципы организации поиска

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

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

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

Детерминированный принцип поиска

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

Подобный подход не имеет вероятностных составляющих, а текущее направление поиска определяется только исходя из заданных входных данных или промежуточных результатов (также детерминированных) [63-65]. Главным преимуществом детерминированных алгоритмов является прогнозируемость поискового процесса и гарантированная точность решения [63-65]. Но такого рода алгоритмы имеют также существенные недостатки: не универсальность (ориентированность на определенные, изначально постулируемые свойства объекта) и, как правило, большие вычислительные затраты [63-65].

Наиболее популярным детерминированным алгоритмом субоптимизации ТА является метод ^-средних [13, 14], который анализировался в п. 1.4.3, в том числе экспериментально в п. 1.5.3. Будучи детерминированным, этот алгоритм обладает основными недостатками данного подхода [63-65]. Необходимо отметить, что существуют множество популярных классических алгоритмов детерминированной оптимизации, такие как: градиентный спуск и его различные модификации, симплекс метод, метод золотого сечения и т.д. [63-65]. Однако, еще на этапе возникновения ТА, большинство из них были признаны малоэффективными решениями в рассматриваемой задаче [13, 14], прежде всего, в связи с большой размерностью задачи ТА, делающей их громоздкими и ресурсно бесперспективными.

Однако, несмотря на отмеченные очевидные недостатки, которые не

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

поставленной задачи (см. пар. 1.8), от детерминированного подхода не следует

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

этот подход гарантирует, при соответствующих условиях, возможность

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

прямой перебор, метод ветвей и границ и ряд других, также плохо согласующихся