Содержание к диссертации
Введение
ГЛАВА 1. Обоснование общей схемы идентификации моделей воспроизведения цветных изображений 12
1.1 Модели воспроизведения цветных изображений 12
1.2 Формулировка задачи идентификации 23
1.3 Качественный анализ метода идентификации, конкретизация задач исследования 32
Выводы и результаты 38
ГЛАВА 2. Согласованная идентификация линейных моделей цветовоспроизведения 39
2.1 Алгоритмы согласованной идентификации
линейных моделей цветовоспроизведения 39
2.2 Сравнение точности согласованных и МНК-оценок 42
2.3 Построение оценок на основе мультифрактальных характеристик 49
2.4 Генетический алгоритм получения промежуточных оценок 55
2.5 Согласованная идентификация на основе мобильного генетического алгоритма 64
2.6 Сравнение согласованной идентификации с робастными оценками 70
Выводы и результаты 73
ГЛАВА 3. Согласованная идентификация нелинейных моделей цветовоспроизведения 75
3.1 Постановка задачи и общая схема согласованной
идентификации нелинейных моделей 75
3.2 Согласованная идентификация моделей цветовоспроизведения по критерию минимума цветового контраста 83
3.3 Согласованное оценивание моделей неинвариантных к сдвигу в цветовом пространстве 87
3.4 Реализация алгоритмов согласованной идентификации нелинейных моделей 94
Выводы и результаты 98
ГЛАВА 4. Параллельные алгоритмы согласованной идентификации 99
4.1 Параллельные алгоритмы согласованной идентификации с фиксированной размерностью подсистем 99
4.2 Последовательность перебора подсистем с сохранением нормы Хемминга 106
4.3 Параллельный генетический алгоритм
согласованной идентификации 107
Выводы и результаты 112
ГЛАВА 5. Экспериментальное исследование точности воспроизведения цветных изображений 113
5.1 Системы управления цветом 113
5.2 Сравнительный анализ методов идентификации
моделей цветовоспроизведения 117
5.3 Анализ точности идентификации
моделей неинвариантных к сдвигу 121
Выводы и результаты 125
Заключение 127
Список использованных источников
- Формулировка задачи идентификации
- Сравнение точности согласованных и МНК-оценок
- Согласованная идентификация моделей цветовоспроизведения по критерию минимума цветового контраста
- Последовательность перебора подсистем с сохранением нормы Хемминга
Введение к работе
Актуальность
Задача воспроизведения цветных изображений является одной из сложнейших в обшей проблеме компьютерной обработки изображений. Особую актуальность тга задач1» приобрела в связи с развитием технологий и систем многокрасочной печати. К сожалению, математические модели таких систем, полностью удовлетворяющие по качестзу, отсутствуют Связано это со сложностью и недостаточной изученностью физики протіесса цветовоспроизведения (R.D. Hersch, F. Collaud, F. Crete, P. Emmel, 2004). Известные модели, как пргчило, обладают сложной нелинейной структурой и являются неизопланатичными.
В промышленных системах используется табличное описание процесса цветовоспроизведения на основе измерений спектров большого количества цветовых мишегей по калибровочным шкалам. Калибровка цветопередачи на основе шкал требует больших материальных и временных затрат. Для нестандартного набора базовых цветов така^ процедура оказывается чрезвычайно трудной (Stollnitz E.J., Ostromoukhov V., Salesin D., Ь' Щ
Обычно указанные трудности преодолеваются путем моделировглия систем цветовоспроизведения, в ходе которого подбираются наиболее подходящие модели ЦБсгососпроизве-дения Подбор этих моделей чрезвычайно трудоемкая задача требующая больших затрат времени и вычислительных ресурсов. Для определения параметров модели решаете задача идентификации по измеренным спектрам цветовых мишеней. Большой чклад в развитие теории идентификации внесли отечественные (Жданов А.И, Перельман И.Ч Потчк Б.Т, Пытьев Ю.П., Сергеев В. В., Теряев Е.Д., Фурсов В.А., Цьшкин ЯЗ., Шамриков Б.М, Юсупов P.M.) и зарубежные (Калман Р.Е., Гроп Д., Эйкхофф П., Льюнг Л, Ли Р, Сейдж Э.П., Мелса Дж.) ученые.
При решении задачи идентификации моделей цветовоспроизведения имеет место значительная априорная неопределенность. Основные источники неопределенности стедую-шие: недостаточная точность математической модели реальной системы (Wyszecki G. Stiles W.S., 1982); случайные ошибки в измерениях спектров красочных смесей; н^равноточность описания системы в различных спектральных диапазонах (Berns, 1995); малое число доступных наблюдений. Вследствие этого вероятностные модели ошибок оказываются ненадежными, либо вовсе отсутствуют.
Если априорные вероятностные модели ошибок измерений не известны для решения задачи определения параметров обычно используют метод наименьших квадратов (МНК). Обоснование МНК и развитие статистической теории оценивания в значительной мере было выполнено А.Н. Колмогоровым, Г. Крамером, Ю.В. Линником в 40-60 годах прошлого века. Была показана оптимальность МНК-оценок в случае, когда ошибки измерений имеют нормальное распределение (Крамер Г., 1975) Однако МНК-оценки весьма чувствительны к нарушениям условий их оптимальности.
В то же время, требование устойчивости к нарушениям исходных предположений является одним из важнейших с практической точки зрения. Устойчивые методы оценивания, не приводящие к большим ошибкам при нарушениях условий оптимальности, в математической статистике получили название робастных. Целый класс оценок, устойчивых к нарушениям априорных предположений о распределении погрешностей, был предложен Д. Хьюбе-ром (1964). Б.Т. Поляк, ЯЗ. Цыпкин (1976) построили робастные оценки для линейной регрессии. К робастным оценкам также относится широко используемый метод наименьших модулей (МНМ), который был детально исследован в работах (Fletcher R., Grant J.A., Heblen H.D. 1971) и (В.И. Мудров и В. Л. Кушко, 1976,
^- НАЦИОМАЛЫМЯ * БИБЛИОТЕКА 1
09 щі*юУЗ*
Несмотря на значительные успехи в развитии методов робастного оценивания, они не могут в полной мере удовлетворить потребностям практики. Во-первых, для построения алгоритмов идентификации в рамках этой теории используются априорные предположения либо в виде стандартной статистической гипотезы (Р. Калман), либо о классах распределений, которые обычно неизвестны. Во-вторых, обеспечение устойчивости оценок к возмущениям исходных данных, к сожалению, приводит к некоторой потере полезной информации.
Резкой критике методы оценивания, основанные на использовании стандартной априорной статистической гипотезы, подверг Р. Калман (Kalman R.E., 1985). Там же была высказана идея улучшения метода наименьших квадратов путем поиска подсистемы наиболее свободной от шума. Похожие идеи идентификации, основанные на иных предположениях, приводились в работах (Allen D.M. 1971) и (В.Н. Вапник, 1984). Однако, возможно в связи с отсутствием на тот момент необходимых вычислительных мощностей, оба этих подхода остались на уровне теоретических идей.
В последнее время появилось несколько новых подходов идентификации моделей сложных систем: подход В.Н. Вапника основанный на минимизации эмпирического функционала среднего риска (В.Н. Вапник, 1984); методика идентификации на основе непараметрических коллективов решающих правил, предлагаемая в работах А.Г. Ивахненко (1971) и В.А. Лапко (2002); подход к оцениванию на основе рандомизированных алгоритмов (Б.Т. Поляк и О.Н. Граничин, 2003). Похожая методика на основе адаптивных алгоритмов случайного поиска использовалась в начале восьми десять'х в работах Л.А. Растригина (1981).
Тем не менее, задача построения алгоритмов идентификации моделей в условиях значительной априорной неопределенности для задач определения параметров моделей цветовоспроизведения остается актуальной. В данном случае основная проблема заключается в том, что приходится выполнять оценивание параметров по малому числу наблюдений. При малом числе наблюдений основное условие предельных теорем теории вероятностей (существование большого числа случайных явлений) не выполняется. Поэтому основанная на них теория статистического оценивания и рассматриваемые в рамках этой теории методы построения оценок оказываются недостаточно обоснованными. При малом числе наблюдений, даже если вероятностные характеристики ошибок измерений известны, построенные на их основе статистические выводы будут ненадежны.
Таким образом, актуальна задача разработки методов и алгоритмов идентификации моделей цветовоспроизведения по малому числу наблюдений в условиях значительной априорной неопределенности. Основная направленность настоящей работы состоит в построении процедур высокоточной идентификации моделей цветовоспроизведения на основе критериев, не требующих задания априорных вероятностных моделей.
Развиваемые методы и алгоритмы опираются на идею Р. Калмана поиска подсистемы, наиболее свободной от шума. Эта задача в настоящей работе решается путем поиска подсистем, для которых оценки параметров, вычисленные с использованием различных входящих в них наборов данных, оказываются наиболее согласованными между собой. Соответствующие процедуры отбора данных мы будем называть согласованным оцениванием (Фурсов В. А., 2001) или согласованной идентификацией.
При отсутствии априорных вероятностных моделей, позволяющих осуществить такой отбор по априорным данным, задача должна решаться с использованием алгоритмов переборного типа. Эти алгоритмы обладают высокой вычислительной сложностью. Поэтому для практического применения согласованной идентификации чрезвычайно актуальна также задача разработки методов и алгоритмов, позволяющих получать согласованные оценки за приемлемое время.
В настоящей работе для решения этой задачи используются методы стсхаггріческого поиска, в частности, используется парадигма генетических алгоритмов (Goldberg D Е., КогЪ A., Deb К., 1989). Эффективность данных алгоритмов, основоположником которых считается Holland J. Н. (1975), показана в ряде работ (Mitchell М., 1999), (Saman К., 1W», СЯрушки-на Н.Г., 2003). В настоящей работе эта идея используется для пострснчя длгор^тмої- согласованной идентификации моделей, используемых в системах воспроиззеденич і'вєїньгх изображений. При этом ставится задача получения высокоточных оценок за npHW^Koe время к условиях априорной неопределенности.
Цель и задачи исследований. Целью работы является повьчиекче точности нтспроиз-ведения цветных изображений и сокращение числа измерений по шкалам цветового охвата путем применения специально разрабатываемых для этого методов и алгоритмов идентификации моделей цветовоспроизведения.
В соответствии с поставленной целью в рамках диссертационной работы решіются следующие задачи.
-
Разработка и исследование методов идентификации линейных моделей цветовоспроизведения на основе стохастического поиска, обеспечивающих повышение точности оценок.
-
Разработка и исследование метода и итерационного алгоритма повышения rcwt л,ти согласованной идентификации моделей цветовоспроизведения на Пскове анализа мутьтк-фрактального спектра множества оценок.
-
Исследование комбинированных генетических алгоритмов -епасозанной идеяги-фикации нелинейных моделей цветовоспроизведения, обеспечизающих потученяе зьгоко-точных оценок за приемлемое время.
-
Разработка и исследование алгоритмов идентификации моделей гьс-овоспроизведй-ния с неопределенностью в структуре модели.
-
Разработка алгоритмов идентификации моделей цветовоспроизведения ,:с ограниченным наборам образцов спектров с использованием характеристики цветового контраста.
-
Разработка и оценка эффективности параллельных алгоритмов согласованной идентификации.
Научная новизна работы. В диссертации получены следующие новые научные результаты.
1. Разработаны методы стохастического поиска наиболее согласованного подмножества оценок в задаче идентификации линейной модели цветовоспроизведения с использованием мобильного генетического алгоритма
2 Предложен новый критерий согласованной идентификации, основанный на анализе мультифрактального спектра множества оценок.
-
Разработан поэтапный оптимизационный алгоритм идентификации нелинейной модели цветовоспроизведения на основе стохастического поиска наиболее свободной от шума подсистемы.
-
Предложена новая схема идентификации нелинейных моделей с разбиением пространства параметров модели цветовоспроизведения на изопланатичные области по критерию согласованности.
-
Разработан алгоритм согласованной идентификации параметров моделей цветовоспроизведения по критерию минимума цветового контраста.
Реализация результатов работы. Результаты диссертационной работы внедрены в технологический процесс обработки цветных изображений в издательском доме «Агни» (г. Самара), а также используется в учебном процессе Самарского государственного аэро-
космического университета им. СП. Королева и в научных исследованиях Института систем обработки изображений РАН.
Основные результаты получены в рамках научно-исследовательских работ по гранту РФФИ «Разработка теории идентификации моделей цветообразования, развитие и исследование методов и алгоритмов обработки цветных изображений», проект №03-01-00109, 2002-2004, руководитель д.т.н., профессор Фурсов В.А.
По теме диссертации опубликованы 13 работ, работы [11,12] выполнены автором лично, остальные написаны в соавторстве.
Апробация работы. Основные результаты были доложены на следующих конференциях: 6-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» Великий Новгород, 2002 г.; 2-й Всероссийской конференции «Высокопроизводительные вычисления и технологии», Ижевск, Удмурдский Государственный Университет, 2003; 11-й Всероссийской конференции «Математические методы распознавания образов» ММРО-11, Москва, 2003; 4* European Congress on Computational Methods ч, in Applied Sciences and Engineering, Jyvaskyla, Finland, 24-28, July, 2004; 7-й Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-2004), Санкт-Петербург, 2004 г.; 2-й Всероссийской конференции «Математическое моделирование 2005», Самара 2-6 июня 2005 г.; 2* ISPE Concurrent Engineering: Research and Application, 2005, Dallas /Fort Worth, USA, 25-29 July 2005.
Основные положения диссертации, выносимые на защиту:
-
Метод согласованной идентификации линейных моделей цветовоспроизведения на основе стохастического поиска, обеспечивающий повышение точности оценок.
-
Критерий качества оценок и итерационный алгоритм повышения точности согласованной идентификации на основе анализа мультифрактального спектра множества оценок.
-
Двухэтапный генетический алгоритм согласованной идентификации нелинейных моделей, обеспечивающий получение высокоточных оценок за приемлемое время.
-
Общая схема и алгоритм идентификации моделей цветовоспроизведения с неопределенностью в структуре модели с разбиением пространства параметров на изопланатичные области.
-
Алгоритм согласованной идентификации модели цветовоспроизведения по критерию минимума цветового контраста.
-
Параллельная реализация алгоритмов согласованной идентификации и полученные теоретические и экспериментальные оценки ускорения.
Структура и объем работы
Диссертация состоит из введения, пяти глав, заключения, списка литературы. Общий объем работы составляет 136 страниц, 29 рисунков, 9 таблиц. Библиографический список насчитывает 96 наименований.
Формулировка задачи идентификации
Система цветовоспроизведения должна обеспечить точность цветопередачи, которая определяется величиной цветового контраста между цветом оригинала ъш и полученным ъ1аЬ в результате печати цветом:
Точность цветопередачи зависит от качества профиля устройства, который представляет собой таблицу соответствий координат внутреннего цветового пространства устройства и аппаратно-независимого пространства Lab. Объем такой таблицы достаточно велик. Для построения профилей печатных устройств, обычно требуется печать шкал цветового охвата объемом в 800-1200 цветовых мишеней для каждого вариаігга бумаги и каждого набора базовых красок. Пример сокращенной шкалы приведен на рисунке 1.10.
Для каждого образца в шкале известны его координаты в цветовом пространстве устройства - zDDS. Посредством спектрофотометра замеряется спектр образца, и вычисляются его координаты в пространстве Lab - ъш . Таким образом, формируется профиль устройства цветовоспроизведения в виде таблицы соответствий вида: (1.18) z1 - 7Х -iab ... ... ... Z DDS - 7 ... ... ... 7К ADDS - 7К
Для точки z DDS, не принадлежащей таблице (1.18) выполняется интерполяция по ближайшим соседним точкам таблицы: 2Lab Г/VZ DDS 2 DDS — 2 DDs)
В качестве Fj, как правило, используется линейная или сплайн-интерполяция [46], [72]. С целью повышения точности таблица строится на основе некоторой модели [93]: L = nzDDS,ck), (1.19) где с - Nx\-вектор параметров. В таком случае для расчета координат ъыь произвольной точки zDDS выполняется интерполяция вектора параметров С= rI(ZDDS C ,...,С ), затем рассчитывается вектор цветовых координат =- ( 5,с). (1.20)
Использование соотношения (1.20) основано на выборе некоторой модели и определении вектора параметров модели с в каждой точке цветового пространства из таблицы (1.18). Каждой такой точке соответствует цветовая мишень из шкалы цветового охвата.
Объем таблицы (1.18) достаточно велик, каждой строке соответствует измерение напечатанного образца, поэтому построение такой таблицы является достаточно дорогостоящим процессом. При изменении параметров печатного устройства (раскалибровке, замене базовых красок или бумаги) печать шкал должна быть проведена заново.
Рекалибровка печатающих устройств должна выполняться регулярно. Дополнительные трудности возникают в том случае, если в печатном устройстве кроме набора базовых красок используется несколько дополнительных. Построение профиля по шкале для нескольких сотен красок практически невозможно. Таким образом, актуальна задача построения профиля устройства цветовоспроизведения по сокращенным шкалам цветового охвата. Эта задача может быть решена путем идентификации модели цветовоспроизведения по небольшому числу цветовых мишеней.
Согласно (1.4)-( 1.6), спектр красочный смеси однозначно определяет координаты ъыь. С учетом приведенных выше формальных моделей (1.10)-(1.16), соотношение (1.19) можно представить в общем виде: y F\X,zDDSic), (1.21) где у — спектр смеси красок, X - матрица, столбцами которой являются спектры различных элементов автотипии, zDDS - координаты цвета в цветовом пространстве устройства, с - Мх\ вектор параметров. Вектор zDDS определяет управляющие параметры процесса, матрица X - описательные параметры, доступные для непосредственного измерения, вектор параметров с подлежит идентификации в каждой точке таблицы (1.18). Компоненты вектора zDDS меняются от точки к точке изображения, столбцы матрицы X остаются постоянными в некоторой области. Для случая трех красок, представленного на рисунке 1.8, эта матрица содержит 8 измерений спектров, а не 450 измерений как табличный профиль, описывающий трехкрасочную систему!
В частном случае, когда процесс описывается линейной моделью, столбцы матрицы X определяются спектрами базовых красок, и модель (1.21) принимает вид: У = Хс, (1.22) где у, с, Хтеже, что и в (1.21).
При использовании моделей общего вида (1.21) и/или (1.22) в системе цветовоспроизведения координаты цвета известны и поступают в систему в качестве входных управляющих параметров. Значения управляющих параметров меняются от точки к точке изображения.
Кроме управляющих параметров присутствуют параметры устройства воспроизведения, характеризующие спектры базовых цветов устройства, спектр печатной основы, алгоритм растрирования. Эти параметры характеризуют спектры и относительные площади растровых элементов, образующих точку. Они определяют то, как будет сформирована точка на оттиске (см. рисунок 1.8).
Как указывалось выше, из-за неизбежных условий печати (замены красителей, бумаги, изменения механических параметров печатного устройства и др.) требуется периодическая настройка указанных (постоянных) параметров устройства - рекалибровка. Для этого предлагается осуществлять эпизодическую идентификацию (определение параметров с) моделей цветовоспроизведения по наблюдениям спектров красочной смеси у и входным спектрам X небольшого числа цветовых мишеней. Предлагаемая схема системы воспроизведения цветных изображений, включающая подсистему идентификации моделей, приведена на рисунке 1.11.
Сравнение точности согласованных и МНК-оценок
В настоящем разделе проводится сравнение точности согласованной идентификации с другими методами построения оценок. Алгоритмы уточнения оценок параметров регрессии, базирующиеся на принципах, схожих с согласованным оцениванием, предлагались и ранее. Например, в работе Аллена [49] описывается следующая методика. Из системы (1.30) вычеркивается некоторая строка и строятся все возможные регрессионные модели с различным количеством независимых переменных (столбцов матрицы X). Для каждой модели рассчитывается расхождение между предсказываемым значением отклика модели с полным набором строк и с исключенной строкой. Такие расчеты проводятся для каждой строки. В конечном счете отбирается модель, имеющая наименьшее среднее значение предсказываемого расхождения. В монографии [13], в которой алгоритм Аллена описан на русском языке, это метод характеризуется как дающий массу детальной информации об устойчивости различных регрессионных моделей, построенных на основе одного и того же набора экспериментальных данных. Основным недостатком метода называлось то, что он требует огромного объема вычислений.
Другой подход, названный селекцией обучающей выборки описан в работе Вапника [3]. Он заключается в исключении из обучающей выборки нескольких элементов для того, чтобы с помощью оставшегося множества найти функцию, доставляющую меньшую гарантированную величину среднему риску. Никакого дальнейшего исследования или развития предлагаемая идея в работе не получила. Возможно, это связано с тем, что, как и для работы Алена, вычислительные мощности того времени не позволяли провести детальное экспериментальное исследование метода и развить его. В методе Вапника решение о принятии промежуточной оценки за окончательную производится на основании поведения функционала заданного не в пространстве оценок, а в пространстве отклика модели. Принципиальное отличие метода согласованного оценивания заключается в том, что решение о выборе подсистемы, на которой вычисляется оценка, принимается на основе критерия, вычисленного с использованием промежуточных оценок. В третьей главе будет рассмотрен близкий к схеме селекции Вапника метод, использующий в качестве критерия взаимной близости цветовой контраст, задаваемый в пространстве отклика модели процесса цветов оспрооизведения.
Развиваемый в данной работе подход, основанный на построении согласованных оценок получил развитие за счет возможности применения высокопроизводительных вычислительных средств в процессе исследования. Созданные на основе данного подхода параллельные и распределенные алгоритмы обладают способностью за счет значительного повышения вычислительной сложности достигать более точных оценок в условиях априорной неопределенности [59], [24 ], [25 ].
Определяющим фактором в рамках принципа согласованного оценивания является вид функции взаимной близости множеств промежуточных оценок. Критерий взаимной близости должен быть чувствителен к случайным ошибкам в измерениях. Он должен выбираться с учетом структуры модели, соответствующей конкретному классу прикладных задач.
Можно предложить множество различных вариантов - от простых, таких как вариация или диаметр множества 0 , до специфичных, например таких, как цветовой контраст между спектрами красочных смесей, который будет рассмотрен в следующей главе,
В настоящем разделе рассматриваются результаты сравнения согласованных оценок полученных перебором всех матриц подсистем верхнего уровня (2.5) с использованием рассмотренного выше критерия парной близости (1.43).
Исследования показывают, что критерий (1.43) позволяет определять подсистемы верхнего уровня, соответствующие оценкам с ошибкой меньшей, чем ошибка исходной МНК-оценки. Для сравнительной оценки точности предлагаемых методов, использовался следующий показатель, вычисляемый как выходная ошибка модели [46]: $ = у -ХЙ, (2.12) где у" =Хс-значение незапгумленного отклика системы, на практике никогда не известное. При проведении тестовых экспериментов системы генерируются следующим образом: сначала случайно задаются X, с и , потом рассчитывается величина у = Хс и к ней добавляется шум: у = у + %. С использованием вектора у и X проводится идентификация, ошибка которой определяется согласно (2.12)
Согласованная идентификация моделей цветовоспроизведения по критерию минимума цветового контраста
В примере из предыдущего раздела была продемонстрирована эффективность применения согласованного оценивания для идентификации модели процесса цветовоспроизведения. Критерием качества (3.4) служила величина цветового контраста между измеренным и рассчитанным цветами. В настоящем разделе рассмотрим применение данной величины для построения критерия взаимной близости (3.10).
Рассмотрим подробнее функционал качества модели из соотношения (3.4): Ф(ЯХ,с),у) = Ф(у,у)) y,yeYw, (3.18) где у = СРР...,.Р#) и y = (yt — yN) элементы Л -мерного пространства Yw, представляют собой измеренный и рассчитанный отклик системы (3.1). Критерий качества модели формулируется исходя из специфических требований к модели, и может иметь произвольный вид, однако обычно представляет собой норму некоторого пространства. Исходя из этого предположения, можно записать следующие соотношения для функционала (3.18): Ф(У,У) = Ч-4 Ч.ЧеРв. (3-19) где Р0 - D-мерное пространство с нормой -]. Элементы этого пространства получаются согласно отображению: ЪР -Ъ- О- О-20)
Использование различных преобразований (3.20) и различных норм (3.19) приводит к получению различных критериев качества (3.18) и, соответственно, различных задач минимизации (3.4). В частности, если (3.20) представляет собой тождественное преобразование, а норма (3.19) - евклидову норму L2, то получим критерий качества из соотношения (3.5): ф(у.у) = у-уг=Е№-л)2- 3-21 м Если преобразование (3.20) тождественное, а в (3.19) используется норма ія, то функционал (3.18) примет вид: Ф(У»У) = maxly, - yt\. (3.22) М.ЛГ Соотношение (3.4) в свою очередь примет вид: с = arg minOiiaxl.y, (с) - ,-(). (3.23) Если для вычисления оценки (3.4) используется функционал качества отличный от (3.21), то этот же функционал качества может быть использован при вычислении значения критерия взаимной близости оценок (3.10). В этом случае критерий парной взаимной близости (1-43) имеет вид: = S.lk(nX,6i))- (F(X,ef)), (3.24)
В частном случае (3.23) из (3.24) получим следующий критерий взаимной близости для нормы ж: W[Bt] = тму,,Дс,)-у,,(с,). (3.25)
В случае, когда пространства PD и \N не совпадают и отображение pYP не является тождественным, (3.24) принимает наиболее общий вид. Такая ситуация возникает, если качество модели оценивается в специфичном пространстве, определяемом исходя из потребностей конкретной прикладной задачи.
Рассмотрим применение критерия взаимной близости (3.24) для задачи идентификации системы цветвоспроизведения. В качестве пространства VD мы будем использовать равноконтрастное цветовое пространство Lab, а в качестве нормы — величину цветового контраста между двумя цветами (1.6). Связанные с этой величиной понятия теории цвета приведены в разделе 1.1.
Качество модели цветовоспроизведения определяется величиной цветового контраста между измеренным и рассчитанным по модели цветами. Эту величшгу, определяемую согласно (1.12), предлагается использовать в качестве критерия взаимной близости.
Для каждой оценки из множества 0 можно рассчитать согласно модели (3.3) спектр красочной смеси. Соотношения (1.4), (1.5) определяют отображение (3.20) из пространства спектров (пространства отклика модели) в пространство Lab, в котором качество модели определяется как норма L2 задаваемая соотношением (1.12). Соотношения (1.4), (1.5) можно формально записать в виде:
Эффективность применения такого критерия для нелинейных моделей процесса цветовосроизведсния показана в работе [21]. Применение данного критерия в совокупности с генетическим алгоритмом получения согласованных оценок позволяет снизить ошибку до 0.453ЛЕ по сравнению с ошибкой 0.945ДЕ, приведенной в таблице 3.1. Более подробно данные экспериментов, подтверждающие эффективность предлагаемого критерия приведены в пятой главе. Действительно, в отличие от критериев взаимной близости, использованных ранее, критерий (3.27) обеспечивает близость цветов, соответствующих различным промежуточным оценкам.
Наглядно можно видеть разницу между критериями на рисунке 3.3. На каждом из рисунков СКО между реальным и рассчитанным спектрами одинаково. Цветовой контраст на первом рисунке составляет 0.93ДЕ, это означает, что прогнозируемый цвет неотличим от реального. На втором рисунке цветовой контраст — 2.16 ДЕ, что соответствует различным с точки зрения человеческого восприятия цветам.
Последовательность перебора подсистем с сохранением нормы Хемминга
На принципиальном уровне генетические алгоритмы допускают параллельную реализацию достаточно очевидным способом за счет присущего им внутреннего параллелизма. Однако тонкостям такой реализации посвящено большое количество работ [53], [92].
Стоит сразу отметить, что сравнение ускорения последовательного и параллельного генетичесішх алгоритмов не совсем корректно. Так как генетический алгоритм является стохастическим, то нельзя сказать, что, сравнивая последовательную и параллельную реализацию, мы сравниваем две реализации одного и того же алгоритма, мы можем лишь гарантировать, что эти две реализации дают в среднем одинаковые результаты [53].
Различают два основных способа параллельной реализации генетического алгоритма на многопроцессорных системах с раздельной памятью - кластерах. Это так называемая схема «ведущий-ведомый» и распределенная схема [53].
Наиболее простой способ реализации генетического алгоритма — это схема распараллеливания «ведущий-ведомый». При таком способе корневой процесс контролирует межпроцессные пересылки, сортировку и рекомбинации. Корневой процесс рассылает остальным процессам наборы хромосом для расчета функции приспособленности. Этот способ наиболее прост для программирования. Самый существенный недостаток данного метода в очень высокой нагрузке на коммуникации между процессами. Расходы на коммуникации линейно возрастают с числом процессоров, а время между моментами синхронизации ограничено размером популяции. Согласно [53] общее время вычислений при параллельном расчете на одно поколение составляет: TP= f- + pin \)Tc, (4.4) где 7} — время на вычисление приспособленности одной хромосомы, Тс - среднее время коммуникаций на один процесс, п количество процессоров, р - параметр, характеризующий конкретный способ параллельной реализации, типичное значение данного параметра для схемы ведущий-ведомый порядка единицы.
Соотношение (4.6) постоянно для конкретного типа задачи, число процессоров п , дающее максимум (4.5) можно найти, дифференцируя (4.4) по л и приравнивая производную к нулю: IN Т Iі pop1 г -=Г%- (4-7
Если число процессоров больше nupt, то отношение (4.5) будет приблизительно постоянным. Определяющими параметрами для схемы ведущий-ведомый являются размер популяции и отношение f/C [53],
Для задачи согласованного оценивания iVpo/I»1000, отношение f/L составляет порядка 30 для линейной задачи. Тогда, согласно (4.7) ускорение должно происходить пока число процессоров не превысит 150.
Однако специфика задачи согласованного оценивания предполагает дополнительные операции кроме сортировки по всей популяции, такие как расчет плотности (2.27) и уточнение оценок согласно мультифрактальному критерию (2.32), эти операции занимают достаточно значительное время пропорциональное размеру популяции, согласно экспериментальным оценкам: Т ЙСЗГ,. (4.8)
Все эти вычисления должны вестись корневым процессом после получения данных популяции от остальных процессов. Это дополнительное время войдет в качестве отдельного слагаемого в (4.4) и, так как остальные слагаемые положительны, можно с учетом (4.8) записать следующее неравенство: N.,Tf Тр =_LX+Р(п-щ+T„ о.гт, п
Таким образом, более чем троекратного ускорения схема «ведущий-ведомый» для задачи согласованного оценивания не дает.
Более значительное ускорение предполагает использование схемы распределенного генетического алгоритма, так называемой распределенной («островной») схемы. При таком подходе на каждом процессоре генерируется собственная популяция и проводится изолированный эволюционный цикл в течение некоторого количества эпох на каждом процессе.
Эффективность генетического алгоритма для решения конкретной задачи во многом зависит от так называемого баланса исследования и использования [47]. Размеры исследуемой области генетического алгоритма тем больше, чем выше случайная составляющая поиска, которая определяется величиной параметра мутации. Предельным случай полностью стохастического ГА является метод Монте-Карло. Использование означает процесс направленной сходимости к некоторому экстремуму. За эффективность использования в ГА отвечают операторы скрещивания и отбора. Фактически, ГА представляет собой некоторый метод поиска нулевого порядка (отдаленный аналог метода Хука-Дживса в бинарном пространстве [33]) со стохастической составляющей. Баланс исследования и использования как раз определяет соотношение между стохастической и детерменированной оптимизацией в ГА.
Согласно теореме, приводимой в [92] можно провести следующую оценку ускорения при распределенной схеме распараллеливания: 5 = + 0(1- )- / , (4.9) л — л, где 1-Я в терминах генетических алгоритмов означает вероятность найти решение задачи за одну итерацию, s - некоторый параметр ускорения, зависящий от характеристик конкретного алгоритма, в том числе от вероятностных параметров инициализации популяции. Для задачи согласованного оценивания, как и для большинства задач, (1-Л.) »0, следовательно, Л-»1 и оценка ускорения (4.9) выполняется. С учетом сказанного запуск независимых ГА в каждом процессе фактически увеличивает область исследования алгоритма. Увеличить прирост скорости удается, уменьшая значение дисперсии мутации и/или изменив алгоритм селекции родителей со случайного на пропорциональный. Также хороший результат показало применение методики элитного отбора.
