автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Воспроизведение цветных изображений на основе согласованной идентификации

на правах

НИКОНОРОВ Артем Владимирович

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

Специальность: 05.13.17 Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Самара 2005

Работа выполнена в Самарском государственном аэрокосмическом университете имени академика С.П.Королева и Институте систем обработки изображений РАН

Научный руководитель: доктор технических наук, профессор

В. А. Фурсов

Официальные оппоненты: доктор технических наук, профессор

М.А. Кораблин

кандидат технических наук, доцент В.В. Мясников

Ведущая организация: Самарский государственный технический

университет

Защита состоится 2 декабря 2005 г. в 12 часов на заседании диссертационного совета Д 212.215.07 в Самарском государственном аэрокосмическом университете имени академика С.П.Королева, по адресу: 443086, г. Самара, Московское шоссе, д. 34.

С диссертацией можно ознакомиться в библиотеке Самарского государственного аэрокосмического университета имени академика С.П.Королева.

Автореферат разослан 1 ноября 2005 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

И.В.Белоконов

jM

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность

Задача воспроизведения цветных изображений является одной из сложнейших в общей проблеме компьютерной обработки изображений. Особую актуальность тга зада1!-» приобрела в связи с развитием технологий и систем многокрасочной печати. К сожалению, математические модели таких систем, полностью удовлетворяющие по качестзу, отсутствуют Связано это со сложностью и недостаточной изученностью физики процесса цсловоспроизве-дения (R.D. Hersch, F. Collaud, F. СгёЙ, P. Emmel, 2004). Известные модели, как пргчило, обладают сложной нелинейной структурой и являются неизопланатичными.

В промышленных системах используется табличное описание процесса цветовоспроизведения на основе измерений спектров большого количества цветовых мишегей по калибровочным шкалам. Калибровка цветопередачи на основе шкал требует больших материальных и временных затрат. Для нестандартного набора базовых цветов такал проце дура оказывается чрезвычайно трудной (Stollnitz E.J., Ostromoukhov V., Salesin D., Ь' Щ

Обычно указанные трудности преодолеваются путем моделировглия систе м цветовоспроизведения, в ходе которого подбираются наиболее подходящие модели ЦБс-ососпроизве-дения Подбор этих моделей чрезвычайно трудоемкая задача требующая большие затрат времени и вычислительных ресурсов. Для определения параметров модели решаете задача идентификации по измеренным спектрам цветовых мишеней. Большой чклад в развитие теории идентификации внесли отечественные (Жданов А.И, Перельман И. И Почта Б.Т, Пытьев Ю.П., Сергеев В. В., Теряев Е.Д., Фурсов В.А., Цыпкин ЯЗ., Шамриков Б.М, Юсупов P.M.) и зарубежные (Калман P.E., Гроп Д., Эйкхофф П., Льюнг Л, Ли Р, Сейдж Э.П., Мелса Дж.) ученые.

При решении задачи идентификации моделей цветовоспроизведения имеет место значительная априорная неопределенность. Основные источники неопределенности стедуто-щие: недостаточная точность математической модели реальной системы (Wyszecki G. Stiles W.S., 1982); случайные ошибки в измерениях спектров красочных смесей; н'равноточностъ описания системы в различных спектральных диапазонах (Berns, 1995); малое число доступных наблюдений. Вследствие этого вероятностные модели ошибок оказываются ненадежными, либо вовсе отсутствуют.

Если априорные вероятностные модели ошибок измерений не известны для решения задачи определения параметров обычно используют метод наименьших квадратов (МНК). Обоснование МНК и развитие статистической теории оценивания в значительной мере было вьполнено А.Н. Колмогоровым, Г. Крамером, Ю.В. Линником в 40-60 годах прошлого века. Была показана оптимальность МНК-оценок в случае, когда ошибки измерений имеют нормальное распределение (Крамер Г., 1975) Однако МНК-оценки весьма чувствительны к нарушениям условий их оптимальности.

В то же время, требование устойчивости к нарушениям исходных предположений является одним из важнейших с практической точки зрения. Устойчивые методы оценивания, не приводящие к большим ошибкам при нарушениях условий оптимальности, в математической статистике получили название робастных. Целый класс оценок, устойчивых к нарушениям априорных предположений о распределении погрешностей, был предложен Д. Хьюбе-ром (1964). Б.Т. Поляк, ЯЗ. Цыпкин (1976) построили робастные оценки для линейной регрессии. К робастным оценкам также относится широко используемый метод наименьших модулей (МНМ), который был детально исследован в работах (Fletcher R., Grant J. A., Heblen H.D. 1971) и (В.И. Мудров и В. Л. Кушко, 197

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

Резкой критике методы оценивания, основанные на использовании стандартной априорной статистической гипотезы, подверг Р. Калман (Kaiman R.E., 1985). Там же была высказана идея улучшения метода наименьших квадратов путем поиска подсистемы наиболее свободной от шума. Похожие идеи идентификации, основанные на иных предположениях, приводились в работах (Allen D.M. 1971) и (В.Н. Вапник, 1984). Однако, возможно в связи с отсутствием на тот момент необходимых вычислительных мощностей, оба этих подхода остались на уровне теоретических идей.

В последнее время появилось несколько новых подходов идентификации моделей сложных систем: подход В.Н. Вапника основанный на минимизации эмпирического функционала среднего риска (В.Н. Вапник, 1984); методика идентификации на основе непараметрических коллективов решающих правил, предлагаемая в работах А.Г. Ивахненко (1971) и В.А. Лапко (2002); подход к оцениванию на основе рандомизированных алгоритмов (Б.Т. Поляк и О.Н. Граничин, 2003). Похожая методика на основе адаптивных алгоритмов случайного поиска использовалась в начале восьмидесятых в работах JI.A, Растригина (1981).

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

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

Развиваемые методы и алгоритмы опираются на идею Р. Калмана поиска подсистемы, наиболее свободной от шума. Эта задача в настоящей работе решается путем поиска подсистем, для которых оценки параметров, вычисленные с использованием различных входящих в них наборов данных, оказываются наиболее согласованными между собой. Соответствующие процедуры отбора данных мы будем называть согласованным оцениванием (Фурсов В.А., 2001) или согласованной идентификацией.

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

В настоящей работе для решения этой задачи используются методы cvxa." iичгского поиска, в частности, используется парадигма генетических алгоритмов (Goldberg D Е., Korb A., Deb К., 1989). Эффективность данных алгоритмов, основоположником которых считается Holland J. Н. (1975), показана в ряде работ (Mitchell М., 1999), (Saman К., 1 СЯрушки-на Н.Г., 2003). В настоящей работе эта идея используется для построения длгор* tmoi- согласованной идентификации моделей, используемых в системах воспроизвеценич пвегных изображений. При этом ставится задача получения высокоточных оценок за прием"7»«* время в условиях априорной неопределенности.

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

В соответствии с поставленной целью в рамках диссертационной работа: реш потея следующие задачи.

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

2. Разработка и исследование метода и итерационного алгоритма повышения гоч! .кти согласованной идентификации моделей цветовоспроизведения на основе анализа мутьтн-фрактального спектра множества оценок.

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

4. Разработка и исследование алгоритмов идентификации моделей гье-'-овопфоизведг-ния с неопределенностью в структуре модели.

5. Разработка алгоритмов идентификации моделей цветовоспроизведения ,:<• ограниченным наборам образцов спектров с использованием характеристики цветового контраста.

6. Разработка и оценка эффективности параллельных алгоритмов согласованной идентификации.

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

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

2 Предложен новый критерий согласованной идентификации, основанный на анализе мультифрактального спектра множества оценок.

3. Разработан поэтапный оптимизационный алгоритм идентификации нелинейной модели цветовоспроизведения на основе стохастического поиска наиболее свободной от шума подсистемы.

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

5. Разработан алгоритм согласованной идентификации параметров моделей цветовоспроизведения по критерию минимума цветового контраста.

Реализация результатов работы. Результаты диссертационной работы внедрены в технологический процесс обработки цветных изображений в издательском доме «Агни» (г. Самара), а также используется в учебном процессе Самарского государственного аэро-

космического университета им. С.П. Королева и в научных исследованиях Института систем обработки изображений РАН.

Основные результаты получены в рамках научно-исследовательских работ по гранту РФФИ «Разработка теории идентификации моделей цветообразования, развитие и исследование методов и алгоритмов обработки цветных изображений», проект №03-01-00109, 20022004, руководитель д.т.н., профессор Фурсов В.А.

По теме диссертации опубликованы 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 г.; 2th ISPE Concurrent Engineering: Research and Application, 2005, Dallas /Foit Worth, USA, 25-29 July 2005.

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

1. Метод согласованной идентификации линейных моделей цветовоспроизведения на основе стохастического поиска, обеспечивающий повышение точности оценок.

2. Критерий качества оценок и итерационный алгоритм повышения точности согласованной идентификации на основе анализа мультифрактального спектра множества оценок.

3. Двухэтапный генетический алгоритм согласованной идентификации нелинейных моделей, обеспечивающий получение высокоточных оценок за приемлемое время.

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

5. Алгоритм согласованной идентификации модели цветовоспроизведения по критерию минимума цветового контраста.

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

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения, списка литературы. Общий объем работы составляет 136 страниц, 29 рисунков, 9 таблиц. Библиографический список насчитывает 96 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

фикации. Намечен общий подход к решению задачи на основе согласованной идентификации. Сформулированы основные задачи исследований.

Цвет - субъективная характеристика излучения. Он зависит от множества факторов, в частности, от спектрального состава излучения и от личных психофизических особенностей наблюдателя. Под спектром здесь понимается последовательность измерений коэффициентов отражения в диапазоне длин волн видимого света (380 - 700 нм). Этот диапазон разбивается на интервалы с шагом ДЛ=10 нм. Таким образом, спектр представляет собой вектор 1 х32.

Согласно ГОСТ 13088-67 цвет определяют как векторную величину трех измерений, выражающую свойство, общее всем спектральным составам излучений, визуально неразличимым в колориметрических условиях наблюдения. Трехкомпонентную Величину, описывающую цвет, принято представлять точкой в пространстве, называемом цветовым пространством.

Наиболее сложным с точки зрения построения модели является процесс воспроизведения изображений на печатном устройстве. На рис. 1 показано, как образуется цвет точки печатного оттиска из цветов различных растровых элементов в случае трехкрасочной печати. Как видно из рисунка, в точке оттиска присутствуют 8 участков различного цвета: три цвета соответствующих базовым краскам под номерами 1,2 и 3; три цвета смесей двух красок - 12, 23, 13; смесь трех красок - 123 и бумага - 0. Каждый из этих участков характеризуется своим спектром и своей площадью. Площади элементов определяются координатами в цветовом пространстве устройства- zDDS.

Стандартом аппаратно-независимого цветового пространства считается пространство Lab. Переход от спектров к пространству Lab выполняется согласно следующим соотношениям:

¿ = 116/(У/Уж)-16,

а = 5Щ(/(Х/Хк)-ЯГ/Г„)}, (1)

6 = 200[/(r/rj-/(Z/Zí,)],

•Л

где У = к J[ S(¿)y(Á)R(Á)dÁ, Z = k^S(A)z(Á)R(Á)dA,

Рис. 1 - Растровые элементы, Xn= 96 4; yN= Ю0, ZN = 82.5, к = ——-,

образующие точку оттиска | S(Á)y(Á)dÁ

(цифрами указаны зоны с f v ,>0.008856,

различными спектрами, f(t)=i '

образованные наложением красок) [7.7867<+16/116, V ¿<0.008856.

/?(Л) - спектр образца, S{X) - спектральный состав излучения от источника освещения, х(А), у(Я), г(Л) - известные функции чувствительности человеческого зрения, Л -интервал длин волн, от 380 до 700нм.

Качество цветопередачи определяется как расстояние в пространстве Lab между требуемым и полученным цветами:

ДЕ'=|г^-гЦ, (2)

где — векторы измеренного и требуемого цвета в цветовом пространстве Lab.

Точной модели процесса формирования цвета красочной смеси до сих пор не получено (Mourad, 2003). Поэтому на практике обычно используется описание процесса цветовоспроизведения в виде таблицы соответствий: t!dds -> г'ш, / = 1,2..., называемой профилем устройства. При использовании локально-линейной модели процесса для построения таких таблиц необходимо проводить большое количество измерений спектров по так называемым шкалам цветового охвата. Например, для четырехкрасочной печати требуется около 1000 измерений.

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

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

y = /"(X,c(Zoos))+$, (3)

где у - ЛМ-вектор измеренного спектра смеси красок, X - N*M- матрица, столбцами которой являются спектры различных растровых элементов, c(zDDS) - М* 1 • вектор параметров модели, компоненты которого зависят от площади участков (рис. 1), соответствующих растровым элементам различных цветов, AM-вектор ошибок (модели, измерений и др.). Предполагается, что вектор ошибок % ограничен: ^ = Const.

Задача идентификации заключается в определении вектора c(zDDS) (далее для простоты обозначаемого с) параметров модели (3) устройства по измеренным спектрам, составляющим матрицу X и вектор у. Точность идентификации модели цветовоспроизведения определяется величиной цветового контраста между измеренным и рассчитанным спектрами (2) (вычисляется на этапе верификации алгоритмов). В качестве критерия точности цветовоспроизведения используется среднеквадратичное отклонение (СКО) между измеренным и рассчитанным спектрами.

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

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

1. Матрица X и вектор у фиксированы, т.е. известны в результате измерений на одной реализации.

2. Соответствующая соотношению (3) формальная модель, достаточно точно описывающая процесс цветовоспроизведения при £=0, существует, но не известна.

3. Статистические характеристики вектора ошибок \ не известны, но предполагается, что система (2) содержит некоторую подсистему из L (М < L <N) уравнений более свободных от шума, по которым А/xl-вектор с может быть определен с требуемой точностью.

Приведем описание общей схемы согласованной идентификации на примере частного случая - линейной модели:

У = Хс+§, (4)

где у и X - имеют тот же смысл и те же размерности, что и в (3).

Из системы (4) сформируем множество так называемых подсистем кижнегс уроння с помощью весовых матриц диагонального вида - Gt = diag(gtg „), AM,2,. . Z хлс."-' < этих матриц могут бьггь только нулями и единицами. Ненулевые элементы ладсиот-я для различных сочетаний из Sk индексов, так что rankQk=St для всех к. В резучь.ат'; получаем множество подсистем вида:

у4=ХЛ+^,*=1,2,... (5)

где

yk=Gky,Xk=GkX,%k=Gky,

dim (R(Xt)) = rankGk = £ gtJ = |gt l = Sk,

i-1

где R(Xt) - пространство столбцов матрицы Xk, a gk - N* l-вектор: Gt - Eg.

Если размерность подсистем нижнего уровня фиксирована, т.е Sk -- S, то число подсистем нижнего уровня равное^ (S<N). Вычисляя для каждой из пострлеаных таким образом подсистем МНК-оценку

ct=[XrGtX]-'XrGiy, (б)

получаем множество S всех возможных оценок на подсистемах нижле! j уровня размерности S:

H = {ct=[XrGtXrxrGiy | VGj: fc| = S}f |S| = C£.. (7)

Аналогичным образом (из нулей и единиц) строится множеств*) лиаггнальных Vx,\r весовых матриц Н,:

Н, = diag(h, t, hIN), rank Нi = P (S<P<N) с использованием которых формируются так называемые подсистемы верхнего уровня. у;=Х,с, + 4„ (8)

где

Х,=Н,Х, у(=Н;у,|,=Н,у,/ = й^ = С;. Ясно, что каждой такой подсистеме будет соответствовать свое подмножество подсистем нижнего уровня и, соответственно, подмножество промежуточных сценой

в, = {с, б S | VA: gTkb, = ||gj = S}_ |в,| = С?, V/ = (9)

где h; - ЛМ-вектор: н, = Eh,.

Для характеристики множеств 0, вводится критерий взаимной близости■

Щ&,) = Щси.....си), c,t е0,, k = lj,! = lj. (10)

Множество в, с минимальным значением W{®,) обозначим в и будем называть наиболее согласованным множеством оценок. Задача заключается в отыскании этого множества и построении на нем точечной оценки. Нахождение наиболее согласованного множества по существу сводится к отысканию индекса I:

В работе исследовался критерий парной взаимной близости:

^ЬЖ-и (И)

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

3 ■= й' = й, Const} показано, что: где:

^(е,)=(к-1)±1тк;% (12)

Ы /=1 м=1 V /

= 211У-1М2К |-Кл|«»Г»г£

l-l,L-J'MX

(13)

Здесь |§,||2 - квадрат нормы вектора ошибок измерений на 1-й подсистеме нижнего уровня, а сов^,^,) - косинус угла между этим вектором и собственным вектором (столбцом матрицы Т, спектрального разложения = Т^Л,!"^), соответствующим собственному значению .

Из (12), (13) видно, что вклад слагаемых IV, (0,) и Шг (0,) зависит от собственных значений матриц подсистем нижнего уровня и ориентации векторов ошибок измерений и этих подсистем. В частности, если ошибки случайные и независимые, основной вклад вносит составляющая Щ (0,). Эта сумма тем меньше, чем меньше нормы векторов ошибок измерений. Следовательно, есть все основания ожидать, что подсистема верхнего уровня, для которой функция взаимной близости минимальна, наиболее свободна от шума.

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

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

Основные современные системы построения цветовых профилей используют локально -линейные модели систем печатных устройств на основе табличного представления. Эти модели достаточно хорошо описывают процесс воспроизведения цвета в ограниченной области цветового пространства. Для линейной модели (4) проведено экспериментальное исследование связи критерия взаимной парной близости с точностью оценок. На рис. 2 приведены графики значений ошибки оценивания

fL-Ъ'-Ч

и величины критерия Щ0,) для различных подсистем верхнего уровня фиксированной размерности. Графики подтверждают качественные выводы, базирующиеся на соотношениях (12), (13).

Проведено также экспериментальное сравнение точности согласованных оценок с МНК-оценками. Для этого использовался показатель, вычисляемый как отношение ошибок оценивания по этим методам:

-й ш -

где с ^ и - МНК-оценка и ошибка, соответствующая этой оценке, а сСЕ и %СЕ - оценка и ошибка согласованного оценивания (conforming estimation).

Эксперимент проводился для разных размерностей подсистем верхнего уровня. Соответствующие графики приведены на рис. 3.

Из графиков видно, что точность согласованных оценок всегда выше точности МНК-оценок, но она существенным образом зависит от размерности подсистем верхнего уровня. Характер этой зависимости (рис. 3) показывает, что если априорная информация о размерности подсистемы, наиболее свободной от шума, отсутствует, неправильный выбор этой размерности может привести к существенному снижению точности согласованной идентификации. Заметам, что в соответствии с (12), (13) точность согласованной идентификации по критерию парной близости также зависит от размерности подсистем верхнего уровня.

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

В качестве характеристики, описывающей распределение множества оценок в пространстве параметров, используется обобщенная фрактальная размерность Ds (Федер Е., 1991). Значения размерности, соответствующие большим отрицательным значениям q подчеркивают области, в которых точки множества расположены наиболее плотно, тогда как большим отрицательным значениям q соответствует размерность наиболее редко посещаемых областей (Harte D., 2001). Предложен следующий формальный критерий фрактального уточнения

А = - 5|+| Д, - ö|) • (Z)_ -£>„), (15)

где D — значение обобщенной фрактальной размерности, усредненное по нескольким подсистемам. Минимальное значение данного критерия определяет наименее зашумленные подсистемы.

Рис. 2 - Значения ошибки оценивания Ц (сплошная линия) и критерия парной близости № (разрывная линия)

Рис. 3 - Зависимости относительной ошибки г) (1) и значения критерия парной близости IV (2) от размерности подсистемы Р.

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

Подсистемы нижнего и верхнего уровня однозначно определяются матрицами G, и Н„ которые можно представить как Gk = Egt и 11, - Eh,. соответственно. С учетом этого процедуру формирования подсистем верхнего и нижнего уровня можно реализовать посредством перебора бинарных векторов длины N. Эти векторы определяют также и особи в популяции генетического алгоритма отбора наиболее согласованной подсистемы. Если размерность подсистемы нижнего уровня фиксирована, то особь соответствует некоторой подсистеме верхнего уровня, в качестве приспособленности которой выступает непосредственно значение взаимной близости оценок на подсистеме.

Для подсистем нижнего уровня переменной размерности, каждая особь представляет собой одну подсистему нижнего уровня, а вся популяция в целом - множество промежуточных оценок. В качестве приспособленности особи используется отклонение оценки соответствующей особи от с - среднего значения оценки для всей популяции: /(gt) = fct(gt)-c|.

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

После останова алгоритма уточнение оценок для всей популяции так же выполняется на основе мультифрактального критерия (15).

Метод согласованной идентификации при фиксированной размерности подсистемы в работе реализован с использованием парадигмы мобильного генетического алгоритма (Goldberg D.E., Korb A., Deb К., 1989). Применение мобильных генетических алгоритмов позволяет дополнительно снизить вычислительную сложность согласованной идентификации.

В работе проведено также сравнение согласованной идентификации с широко используемым робастным методом оценивания - методом наименьших модулей (МНМ).

В эксперименте использовалось 800 реализаций линейных систем размерности 15x4, матрица входов которых задается как случайная выборка из нормального распределения #(50,100). Вектор ошибок задавался как смесь нормального шума и аномальных ошибок с вероятностью р, имеющих равномерное распределение на интервале [50,100]. На рис. 5 приведен график, показывающий, что средняя ошибка, отнесенная к ошибке МНК-оценки, для метода согласованного оценивания с мультифрактальным уточнением меньше, чем подсчитанная таким же образом относительная ошибка для метода наименьших модулей.

в 7 « 9 юр

Рис. 4 - Зависимости относительной ошибки Т}(1) и значения фрактального критерия А (2) от размерности подсистемы Р

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

Рассматривается нелинейная модель системы цветовоспроизведения (3):

y = F(X,c) + ^. (16)

Задача оценивания векторного параметра с модели формулируется как задача минимизации функционала качества Ф, в частности, строится множество промежуточных оценок &,:

в, = {c(Jt | с,, = argnun®(f (Х„,с), yv)}, (17)

где

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

0 = aiginmJF(0,), (18)

I-U

на котором затем ищется искомая оценка.

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

1. Метод Бройдена-Флетчера-Шано (БФШ) (C G. Broyden, R. Fletcher, D.F. Shanno, 1970). Если функционал качества принимает вид СКО, то минимизация проводится методом Левенберга-Марквардта (JIM) (К. Levenberg, 1944), (D. Marquardt, 1963).

2. Генетический алгоритм (ГА). Исследовавшиеся варианты алгоритмов сведены в таблицу 1.

Таблица 1 Методы идентификации нелинейных моделей.

Метод построения'

оценок на подсистеме нижнего уровня множества промежуточных оценок искомой точечной оценки

1 - - БФШ

2 - ГА

3 БФШ Полный перебор Усреднение промежуточных оценок

4 ГА Полный перебор Усреднение промежуточных оценок

5 БФШ ГА Усреднение промежуточных оценок

6 ГА ГА Усреднение промежуточных оценок

Варианты построения оценок 1 и 2 - без отбора наиболее согласованной подсистемы, т.е. традиционная идентификация по всей выборке. Варианты 3-6 ппостроены на основе принципа согласованности.

Результаты сравнения точности различных алгоритмов идентификации нелинейной модели системы цветовоспроизведения приведены на рисунке 6. Варианты 5 и 6 обеспечивают достаточно высокую точность при приемлемых вычислительных затратах.

0Таз од о£ 57

Рис 5 - Зависимости относительных ошибок оценивания МНМ (1) и согласованной идентификации (2) от вероятности аномальных ошибок

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

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

В работе показано также, что этот подход может быть обобщен на случай произвольного критерия качества, задаваемого в виде нормы некоторого пространства:

Ф(У,У) = ||Р-Р||> Р'РеРо>

где Р0 D-мерное пространство с нормой Щ. Элементы этого пространства получаются согласно отображению: q>w \ \N -> PD ■

В третьем разделе рассмотрена идентификация процессов, которые отличаются не только параметрами, но и структурой в разных областях цветового пространства ZDDS. Для идентификации таких неинвариантных к сдвигу в цветовом пространстве моделей предложен метод разбиения фазового пространства системы на области с локально - постоянной структурой модели (16).

Критерий качества разбиения на области определяется как значение взаимной близости оценок построенных по точкам внутри области. В данном случае область выступает в качестве подсистемы верхнего уровня, а каждая точка области - в качестве подсистемы нижнего уровня. Формирование различных разбиений фазового пространства на области выполняется при помощи различных бинарных и ./-арных модификаций генетических алгоритмов.

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

Предложен алгоритм последова- Таблица 2. Формирование двоичного представления тельного перебора бинарных векторов с сохранением нормы Хемминга, позволяющий минимизировать число итераций перебора. Пример последовательности перебора векторов длины 6 с нормой Хэмминга 3 приведен в таблице 2.

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

и,-О

12 14 3«

■ Оотибгз ндеетмфикшии (т^) а Выч сложность (О)

Рис. 6 — Сравнение различных методов идентификации нелинейных моделей

переопределенных систем

I ь. I ь, г ь, I ь,

0 000111 5 010101 10 100011 15 101100

1 001011 6 010110 11 100101 16 110001

2 001101 7 011001 12 100110 17 110010

3 001110 8 011010 13 101001 18 110100

4 010011 9 011100 14 101010 19 111000

Экспериментально установленное сверхлинейное ускорение параллельной реализации согласуется с теоретической оценкой (Andre, Koza, 1998) S= >яУ-', где 1-Я в терминах генетических алгоритмов означает вероятность нахождения решения задачи за одну итерацию, s - некоторый параметр ускорения, п - число процессоров, S - значение ускорения, полученное усреднением по большому числу запусков алгоритма.

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

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

Показано, что применение согласованной идентификации позволяет добиться повышения качества воспроизведения цвета вдвое по сравнению с известными методами основанными на идентификации моделей цветовоспроизведения, предложенными в работах (Berns S.R. 1996), (Hersch R. D., Collaud F., Crété F., Emmel P., 2005). Использование разработанных методов и алгоритмов в сквозной информационной технологии воспроизведения цветных изображений позволило сократить число измерений по шкале цветового охвата при калибровке офсетной печатной машины Heidelberg Speed Master 74 в 15 раз.

Основные результаты диссертации:

1. Разработан метод согласованной идентификации линейных моделей цветовоспроизведения на основе стохастического поиска, обеспечивающий повышение точности оценок в условиях априорной неопределенности. Проведен качественный анализ точности получаемых оценок и экспериментальное исследование. Приводится статистика, подтверждающая более высокую точность предлагаемых алгоритмов идентификации по сравнению МНК и МНМ оценками параметров линейных моделей.

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

3. Разработан двухэтапный генетический алгоритм согласованной идентификации нелинейных моделей, обеспечивающий получение высокоточных оценок за приемлемое время.

4. Предложен метод идентификации систем цветовоспроизведения, неинвариантных к сдвигу, посредством разбиения цветового пространства на изопланэтичные области. В частности показано, что для задачи воспроизведения с тестовой шкалой в 800 образцов идентификация может быть проведена по 20 опорным точкам. При этом себестоимость процесса калибровки может бьггь снижена в 15 раз с сохранением требуемого качества

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

6. Разработаны параллельные алгоритмы построения согласованных оценок на основе полного перебора подсистем и на основе методов стохастического поиска. Получены теоретические и экспериментальные оценки ускорения.

реализации согласованной идентификации на основе генетического алгоритма

\¡2.\&oS

2006-4 19068

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

Основные результаты опубликованы в следующих работах:

1. Никоноров A.B., Попов С.Б. Сравнительный анализ моделей цветсюбразования при офсетной многокрасочной печати // сб. Компьютерная оптика 23, Самара-Москва, 2002,

2. Никоноров A.B., Попов С.Б., Фурсов В.А. Идентификация моделей цветовоспроизведения // Труды 6-й международной конференции «Распознавание образов и анализ изображений, новые информационные технологии», Великий Новгород, 2002, с. 431-436.

3. Никоноров A.B., Попов С.Б., Фурсов В.А. Применение принципа согласованности оценок в задаче идентификации моделей цветовоспроизведения // Известия Самарского научного центра РАН т.1 №7,2002, с. 159-165.

4. Fursov V., Nikonorov A., Popov S. Identifying Color Reproduction Models. Pattern Recognition and Image Analysis, Vol. 13, No. 2, 2003, pp. 315-318.

5. Никоноров A.B., Попов С.Б., Фурсов В.А. Принцип согласованного оценивания в задаче идентификации. Алгоритмы параллельной реализации // Тезисы 2-й всероссийской конференции «Высокопроизводительные вычисления и технологии», Ижевск: Удмурдский Государственный Университет, 2003, с. 234-237.

6. Никоноров A.B., Попов С.Б., Фурсов В.А. Вычислительные аспекты идентификации моделей цветовоспроизведения // сб. Компьютерная оптика 25, Самара-Москва, 2003, с. 79-

7. Никоноров А.В, Попов С.Б., Фурсов В.А. Идентификация нелинейных моделей цветовоспроизведения // Материалы 11-й всероссийской конференции «Математические методы распознавания образов», Москва, 2003, с. 381-384.

8. Fursov V., Nikonorov A. Constructing the conforming estimates of non linear parameters. 4* European Congress on Computational Methods in Applied Sciences and Engineering, 24-28, July, 2004, Jyvaskyla, Finland, p. 404.

9. Fursov V., Nikonorov A. Conformity estimation in color lookuptables preprocessing problem. Proceedings of the 17th International Conference on Pattern Recognition (ICPR), Vol. I, p. 213-

10. Никоноров A.B. Идентификация моделей с отбором данных по критерию обобщенной фрактальной размерности И Известия Самарского научного центра РАН 2004, т. 6, № 1, с.

11. Никоноров А.В., Фурсов В.А. Согласованная идентификация в условиях априорной неопределенности // Труды 2-й Всероссийской конференции «Математическое моделирование и краевые задачи», Самара, 2005, с. 251-256.

12.Nikonorov А. V., Iterative improvement of estimations using multifractal spectra. Proc. of the conf. Concurrent Engineering Resesarch and Application, Dallas, USA July 2005, pp. 407-411.

13. V. A. Fursov and A. Nikonorov, The Problem of Preprocessing in the Conformity Estimation in Color Lookup Tables, Pattern Recognition and Image Analysis, Vol. 15, No. 3, 2005, pp. 1-4.

c.79-83.

83.

216.

230-237.

Подписано в печать 31.10.05 Формат 60 х 841/16 Бумага офсетная Усл. печ. л. 1,0 Тираж 100 экз. Заказ_

ВВЕДЕНИЕ

ГЛАВА 1. ОБОСНОВАНИЕ ОБЩЕЙ СХЕМЫ ИДЕНТИФИКАЦИИ

МОДЕЛЕЙ ВОСПРОИЗВЕДЕНИЯ ЦВЕТНЫХ ИЗОБРАЖЕНИЙ

1.1 Модели воспроизведения цветных изображений

1.2 Формулировка задачи идентификации

1.3 Качественный анализ метода идентификации, конкретизация задач исследования

Выводы и результаты

ГЛАВА 2. СОГЛАСОВАННАЯ ИДЕНТИФИКАЦИЯ ЛИНЕЙНЫХ

МОДЕЛЕЙ ЦВЕТОВОСПРОИЗВЕДЕНИЯ

2.1 Алгоритмы согласованной идентификации линейных моделей цветовоспроизведения

2.2 Сравнение точности согласованных и МНК-оценок

2.3 Построение оценок на основе мультифрактальных характеристик

2.4 Генетический алгоритм получения промежуточных оценок

2.5 Согласованная идентификация на основе мобильного генетического алгоритма

2.6 Сравнение согласованной идентификации с робастными оценками 70 Выводы и результаты

ГЛАВА 3. СОГЛАСОВАННАЯ ИДЕНТИФИКАЦИЯ НЕЛИНЕЙНЫХ

МОДЕЛЕЙ ЦВЕТОВОСПРОИЗВЕДЕНИЯ

3.1 Постановка задачи и общая схема согласованной идентификации нелинейных моделей

3.2 Согласованная идентификация моделей цветовоспроизведения по критерию минимума цветового контраста

3.3 Согласованное оценивание моделей неинвариантных к сдвигу в цветовом пространстве

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

Выводы и результаты

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

4.1 Параллельные алгоритмы согласованной идентификации с фиксированной размерностью подсистем

4.2 Последовательность перебора подсистем с сохранением нормы Хемминга

4.3 Параллельный генетический алгоритм согласованной идентификации

Выводы и результаты

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

ТОЧНОСТИ ВОСПРОИЗВЕДЕНИЯ ЦВЕТНЫХ ИЗОБРАЖЕНИЙ

5.1 Системы управления цветом

5.2 Сравнительный анализ методов идентификации моделей цветовоспроизведения

5.3 Анализ точности идентификации моделей неинвариантных к сдвигу

Выводы и результаты

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

В промышленных системах используется табличное описание процесса цветовоспроизведения на основе измерений спектров большого количества цветовых мишеней по калибровочным шкалам. Калибровка цветопередачи на основе шкал требует больших материальных и временных затрат. Для нестандартного набора базовых цветов такая процедура оказывается чрезвычайно трудной [71], [93].

Обычно указанные трудности преодолеваются путем моделирования систем цветовоспроизведения, в ходе которого подбираются наиболее подходящие модели цветовоспроизведения. Подбор этих моделей чрезвычайно трудоемкая задача требующая больших затрат времени и вычислительных ресурсов. Для определения параметров модели решается задача идентификации по измеренным спектрам цветовых мишеней. Большой вклад в развитие теории идентификации внесли отечественные (Жданов А.И., Перельман И.И., Поляк Б.Т., Пытьев Ю.П., Сергеев В. В., Теряев Е.Д., Цыпкин Я.З., Шамриков Б.М, Юсупов P.M.) и зарубежные (Калман P.E., Гроп Д., Эйкхофф П., Льюнг Л., Ли Р., Сейдж Э.П., Мелса Дж.) ученые.

При решении задачи идентификации моделей цветовоспроизведения имеет место значительная априорная неопределенность. Основные источники неопределенности следующие: недостаточная точность математической модели реальной системы [95]; случайные ошибки в измерениях спектров красочных смесей; неравноточность описания системы в различных спектральных диапазонах [50]; малое число доступных наблюдений. Вследствие этого вероятностные модели ошибок оказываются ненадежными либо вовсе отсутствуют.

Если априорные вероятностные модели ошибок измерений не известны, опираясь на восходящее к Гауссу мнение, для решения задачи определения параметров используют метод наименьших квадратов (МНК). Обоснование МНК и развитие статистической теории оценивания в значительной мере было выполнено А.Н. Колмогоровым [15], Г. Крамером [16], Ю.В. Линником [19] в 40-60 годах прошлого века. Была показана оптимальность МНК-оценок в случае, когда ошибки измерений имеют нормальное распределение [16]. Однако МНК-оценки весьма чувствительны к нарушениям условий их оптимальности.

В то же время, требование устойчивости к нарушениям исходных предположений является одним из важнейших с практической точки зрения. Устойчивые методы оценивания, не приводящие к большим ошибкам при нарушениях условий оптимальности, в математической статистике получили название робастных [35]. Целый класс оценок, устойчивых к нарушениям априорных предположений о распределении погрешностей, был предложен Д. Хьюбером [75]. Б.Т. Поляк [9], Я.З. Цыпкин [44] построили робастные оценки для линейной регрессии. К робастным оценкам также относится широко используемый метод наименьших модулей (МНМ), который был детально исследован Флетчером, В.И. Мудровым и В. Л. Кушко в работах [58] и [21].

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

Резкой критике методы оценивания, основанные на использовании стандартной априорной статистической гипотезы, подверг Р. Калман [78]. Там же была высказана идея улучшения метода наименьших квадратов путем поиска подсистемы наиболее свободной от шума. Похожие идеи идентификации, основанные на иных предположениях, приводились в работах Д.М. Аллена [49] и В.Н. Вапника [3]. Однако, возможно в связи с отсутствием на тот момент необходимых вычислительных мощностей, оба этих подхода остались на уровне теоретических идей.

В последнее время появилось несколько новых подходов идентификации моделей сложных систем: подход В.Н. Вапника основанный на минимизации эмпирического функционала среднего риска [3]; методика идентификации на основе непараметрических коллективов решающих правил, предлагаемая в работах (А.Г. Ивахненко [14] и В.А. Лапко [19]; Б.Т. Поляк и О.Н. Граничин [9] разрабатывают подход к оцениванию на основе рандомизированных алгоритмов. Похожая методика на основе адаптивных алгоритмов случайного поиска использовалась в начале восьмидесятых в работах Л.А. Растригина [32].

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

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

Развиваемые методы и алгоритмы опираются на идею Р. Калмана поиска подсистемы, наиболее свободной от шума. Эта задача в настоящей работе решается путем поиска подсистем, для которых оценки параметров, вычисленные с использованием различных входящих в них наборов данных, оказываются наиболее согласованными между собой. Соответствующие процедуры мы будем называть, следуя работе В.А. Фурсова [42], согласованным оцениванием или согласованной идентификацией.

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

В настоящей работе для решения этой задачи используются методы стохастического поиска, в частности, используется парадигма генетических алгоритмов [67] (Goldberg D.E.). Эффективность данных алгоритмов, основоположником которых считается [74] (Holland J. Н.), показана в ряде работ [84], [90], [47]. В настоящей работе эта идея используется для построения алгоритмов согласованной идентификации моделей, используемых в системах воспроизведения цветных изображений. При этом ставится задача получения высокоточных оценок за приемлемое время в условиях априорной неопределенности.

Цель и задачи исследований

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

В соответствии с поставленной целью в рамках диссертационной работы решаются следующие задачи.

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

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

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

4. Разработка и исследование алгоритмов идентификации моделей цветовоспроизведения с неопределенностью в структуре модели.

5. Разработка алгоритмов и информационной технологии идентификации моделей цветовоспроизведения по ограниченным наборам образцов спектров с использованием характеристики цветового контраста.

6. Разработка и оценка эффективности параллельных алгоритмов согласованной идентификации.

Научная новизна работы

В диссертации получены следующие новые научные результаты.

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

2. Предложен новый критерий согласованной идентификации, основанный на анализе мультифрактального спектра множества оценок.

3. Разработан поэтапный оптимизационный алгоритм идентификации нелинейной модели цветовоспроизведения на основе стохастического поиска наиболее свободной от шума подсистемы.

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

5. Разработан алгоритм согласованной идентификации параметров моделей цветовоспроизведения по критерию минимума цветового контраста.

Апробация работы

Основные результаты были доложены на следующих конференциях.

1. б-й Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-2002), Новгород, 2002 г.

2. 2-й Всероссийской конференции «Высокопроизводительные вычисления и технологии». Ижевск, Удмурдский Государственный Университет, 2003.

3. 11-й Всероссийской конференции «Математические методы распознавания образов» ММРО-11, Москва, 2003.

4. 4th European Congress on Computational Methods in Applied Sciences and Engineering, Jyvaskyla, Finland, 24-28, July, 2004.

5. 7-й Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-2004), Санкт-Петербург, 2004 г.

6. 2-й Всероссийской конференции «Математическое моделирование 2005», Самара 2-6 июня 2005 года.

7. 12th ISPE Concurrent Engineering: Research and Application, 2005, Dallas /Fort Worth, USA, 25-29 July 2005.

Основные положения диссертации, выносимые на защиту

1. Метод согласованной идентификации линейных моделей цветовоспроизведения на основе стохастического поиска, обеспечивающий повышение точности оценок.

2. Критерий качества оценок и итерационный алгоритм повышения точности согласованной идентификации на основе анализа мультифрактального спектра множества оценок.

3. Двухэтапный генетический алгоритм согласованной идентификации нелинейных моделей, обеспечивающий получение высокоточных оценок за приемлемое время.

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

5. Алгоритм согласованной идентификации модели цветовоспроизведения по критерию минимума цветового контраста.

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

Благодарности

Диссертационная работа была выполнена при поддержке Министерства образования РФ, Администрации Самарской области, Американского фонда гражданских исследований и развития (С1ШР), РФФИ (гранты № 03-01-00109, 04-0790149, 04-07-96500).

Выводы и результаты

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

Показано, что применение согласованной идентификации позволяет добиться повышения качества воспроизведения цвета вдвое по сравнению с известными методами, основанными на идентификации моделей цветовоспроизведения, предложенными в работах [50] и [92]. Использование разработанных методов и алгоритмов в сквозной информационной технологии воспроизведения цветных изображений позволило сократить число измерений по шкале цветового охвата при калибровке офсетной печатной машины Heidelberg Speed Master 74 в 15 раз.

ЗАКЛЮЧЕНИЕ

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

В рамках диссертационной работы получены следующие результаты.

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

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

3. Было показано, что основные результаты, полученные для согласованной идентификации линейных моделей, остаются в силе и для нелинейных моделей. Разработан двухэтапный генетический алгоритм согласованной идентификации нелинейных моделей, обеспечивающий получение высокоточных оценок за приемлемое время.

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

5. Разработан алгоритм согласованной идентификации модели цветововспроизведения по критерию минимума цветового контраста.

6. Разработана параллельная реализация алгоритмов согласованной идентификации, получены теоретические и экспериментальные оценки ускорения.

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

1. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно генетических алгоритмов // Мужвуз. Сборник -ВГТУ, Воронеж, 1994. - 127 с.

2. Божонкин C.B., Паршин Д.А. Фракталы и мультифракталы. Ижевск. НИЦ «Регулярная и хаотическая динамика», 2001, 128 с.

3. Вапник В.Н., Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979

4. Вентцель Е.С., Теория вероятностей, М.: Физматгиз, 1958,464с.

5. Воеводин В.В., Кузнецов Ю.А., Матрицы и вычисления, М.: Наука, 1984, 320 с.

6. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1967, 575с.

7. Гильбо Е.П., Челпанов И.Б., Обработка сигналов на основе упорядоченного выбора, М.: Советское радио, 1975, 344 с.

8. Гмурман В.Е., Теория вероятностей и математическая статистика. Учеб. пособие для вузов. Изд. 7е стер. М.: Высш. Шк., 2000. - 479 с.

9. Граничин О.Н., Поляк Б.Т., Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003, 191 с.

10. Ю.Демиденко Е.З., Линейная и нелинейная регрессии, М.: Финансы и статистика, 1981,302 с.

11. Демидович Б.П., Марон И.А. Основы вычислительной математики — М.: Наука 1979, 664 с.

12. Джадц Д., Вышецки Г. Цвет в науке и технике. М.: Мир, 1978. - 580 с.

13. Дрейпер Н., Смит Г. Прикладной регрессионный анализ, т.2 М.: Финансы и статистика, 1987, 351с.

14. Ивахненко А.Г., Непараметрический комбинированный алгоритм МГУА на операторах поиска аналогов // Автоматика, 1990, №5, с. 14-27.

15. Колмогоров А.Н., К обоснованию метода наименьших квадратов, // Успехи математических наук, 1, в.1, 1946, 57-70.

16. Крамер Г., Математические методы статистики, М.: Мир, 1975, 648 с.

17. Крянев A.B., Лукин Г.В. Математические методы обработки неопределенных данных. М.: Физматлит, 2003, 216с.

18. Лапко В.А., Непараметрические коллективы решающих правил, Новосибирск, «Наука», 2002, 167 с.

19. Линник Ю.В., Метод наименьших квадратов и основы теории обработки наблюдений, Л.: Физматгиз, 1962, 352 с.

20. Маркус М., Минк X., Обзор по теории матриц и матричных неравенств. М.: Эдиториал, УРСС, 2004, стереотипное издание по 1972 году, 232с.

21. Мудров В.И., Кушко В. Л., Методы обработки измерений. М., Сов. Радио, 1976.

22. Никоноров А.В, Попов С.Б., Фурсов В.А. Идентификация нелинейных моделей цветовоспроизведения // Материалы 11-й всероссийской конференции «Математические методы распознавания образов», Москва, 2003, с. 381-384.

23. Никоноров A.B., Попов С.Б., Фурсов В.А. Применение принципа согласованности оценок в задаче идентификации моделей цветовоспроизведения // Известия Самарского научного центра РАН т.1 №7, 2002, с. 159-165.

24. Никоноров A.B., Попов С.Б., Фурсов В.А. Идентификация моделей цветовоспроизведения // Труды 6-й международной конференции «Распознавание образов и анализ изображений, новые информационные технологии», Великий Новгород, 2002, с. 431-436.

25. Никоноров A.B., Попов С.Б. Сравнительный анализ моделей цветообразования при офсетной многокрасочной печати. // сб. Компьютерная оптика 23, 2003. С.79-83.

26. Никоноров A.B., Фурсов В.А. Согласованная идентификация в условиях априорной неопределенности // Труды 2-й Всероссийской конференции «Математическое моделирование и краевые задачи», Самара, 2005, с. 251-256.

27. Попов С.А. Построение математических моделей коррекции цвета компьютерных изображений. НовГУ им. Ярослава Мудрого. Великий Новгород, 2002 214 с.

28. Пугачев B.C., Теория вероятностей и математическая статистика. М., Физматгиз, 2003.

29. Растригин JI.A. Адаптация сложных систем. Рига: Зинатне, 1981, 357с.

30. Реклейтис Г., Рейвиндран, Рэгсдел К., Оптимизация в технике, Т 1, М.: Мир, 1986, 349с.

31. Селиванов Ю.П., Основы моделирования и оптимального программирования автотипного процесса, М.: Книга, 1978, 238 с.

32. Смоляк С.А., Титаренко Б.П., Устойчивые методы оценивания. М.Ж Статистика, 1980.

33. Теряев Е.Д., Шамриков Б.М. Цифровые системы и поэтапное адаптивное управление. М.: Наука, 1999, 330с.

34. Федер Е., Фракталы, М.: Мир, 1991.

35. Федерер Г., Геометрическая теория меры. М.: Наука, 1987, 760 с.

36. Форсайт Дж., Молер К., Численное решение систем линейных алгебраических уравнений, М.: Мир, 1969, 168 с.

37. ФурсовВ.А. Проблемы вычисления оценок по малому числу наблюдений. //Лекция в трудах молодежной школы "Математическое моделирование 2001", Самара, 13-16 июня 2001. С. 56-63.

38. Фурсов В.А. Идентификация моделей систем формирования изображений по малому числу наблюдений. Самара: ИПО СГАУ, 1998, 128 с.

39. Фурсов В.А. Построение оценок по нестатистическим критериям // Труды международной конференции "ТВП 2001", Самара, 2001, с.141-144.

40. Хьюбер Д., Робастность в статистике. М.: Мир, 1984

41. Цыпкин Я.З. Основы информационной теории идентификации. М.: Наука, 1983.

42. Шашлов Б. А. Цвет и цветовоспроизведение. М.: Мир книги, 1995. 316 с.

43. Эйкхофф П., Основы идентификации систем управления, М.: Мир, 1975, 683 с.

44. Ярушкина Н.Г., Основы теории нечетких и гибридных систем, М.: Финансы и статистика, 2003г.

45. Amidror I. Scattered data interpolation methods for electronic imaging systems: a survey. J. Electronic Imaging. № 11 (2). April 2002.

46. Allen D.M. The prediction sum of squares as a criterion for selecting predictor variables. -University of Kentucky, Technical report, 1971

47. Berns S.R. The Spectral Modeling of Large-Format Ink-Jet Printers. Technical report // Barselona: RIT Munsell Color Science Laboratory, 1996 57 c.

48. Bjorck A. Least Squares Methods. Elsevier Science Publishers B.V. (North Holland). 1990.

49. Brent R.P. Algorithms for minimization without derivatives. Englewood Cliffs, N. J.: Prenctice-Hall. 1973.

50. Cantu-Paz E., Efficient and accurate parallel genetic algorithms. Kluwer Academic Publisher. Second Printing, 2001. 167 p.

51. CIE. Recommendations on uniform color spaces color-difference equations, psychometric color terms, 1978. Supplement Publication 2 to CIE Publ. 15 (E-1.3.1) 1978.

52. Demichel M.E., Procédé, Vol. 26, 17-21, 1924.

53. Demuth H., Beale M., Neural Network Toolbox For Use with MATLAB Natick, The MathWorks, Inc., 1997. 700 p.

54. Emmel P., Hersch R.D., A Model for Colour Prediction of Halftoned Samples Incorporating Light Scattering and Ink Spreading. Poceedings of the IS&T/SID 7th

55. Color Imaging Conference: Color Science, Systems and Applications, November 1619, 1999, Scottsdale, Arizona, USA, pp. 173-181.

56. Fletcher R., Grant J.A., Heblen H.D., The calculation of linear least Lp approximations. Computer Journal, 1971, v. 14, №3.

57. Fletcher R., Practical Methods of Optimization, John Wiley and Sons., 1980.

58. Fursov V., Conformity Principle in Problems of Identification , International Conference Melborne, Australia and St.Petersburg, Russia., pages 463-470. SpringerVerlag, 2003.

59. Fursov V., Nikonorov A. Conformity estimation in color lookuptables preprocessing problem. Proceedings of the 17th International Conference on Pattern Recognition (ICPR), Vol. I, p. 213-216.

60. Fursov V., Nikonorov A. Constructing the conforming estimates of non linearfhparameters. 4 European Congress on Computational Methods in Applied Sciences and Engineering, 24-28, July, 2004, Jyvaskyla, Finland.

61. Fursov V., Nikonorov A., Popov S., Identifying Color Reproduction Models. Pattern Recognition and Image Analysis, Vol. 13, No. 2,2003, pp. 315-318.

62. Nikonorov A. V., Iterative improvement of estimations using multifractal spectra. Proc. of the conf. Concurrent Engineering Resesarch and Application, Dallas, USA July 2005, pp. 407-411.

63. V. A. Fursov and A. Nikonorov, The Problem of Preprocessing in the Conformity Estimation in Color Lookup Tables, Pattern Recognition and Image Analysis, Vol. 15, No. 3,2005, pp. 1-4.

64. Goldberg D. E., Korb A., and Deb K. Messy genetic algorithms: Motivation, analysis, and first results., Complex Systems 3: 493-530 p. 1989.

65. Goldberg D. E., Deb, K. Kargupta H., Harik G. Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In S. Forrest, ed., Proceedingsof the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann. 1993.

66. Harte D., Multifractals: theory and applications. Chapman & Hall/CRC Press, Boca Raton, Florida, 2001 247p.

67. Haupt R.L., Haupt S.E., Practical genetic algorithms. John Wiley & Sons, Inc., Hoboken, New Jersey. Second edition, 2004, 261 p.

68. Hersch R. D., Collaud F., Crete F., Emmel P. Spectral prediction and dot surface estimation models for halftone prints. IS&T/SPIE Electronic Imaging Symposium, Conf. Imaging IX: Processing, Hardcopy and Applications, Jan. 04, SPIE Vol. 5293, 356-369p.

69. Hersch R. D., Collaud F., Crete F., Emmel P., Spectral prediction and dot surface estimation models for halftone prints, IS&T/SPIE Electronic Imaging Symposium, Conf. Imaging IX: Processing, Hardcopy and Applications, Jan. 04, SPIE Vol. 5293, 356-369.

70. Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press. (Second edition: MIT Press, 1992.).

71. Huber P.J. Robust estimation of location parameters. Advances of Mathematical Sciences, 1964, v. 35, №1.

72. Hung P.C. Colorimetric calibration in electronic imaging devices using a look-up table model and interpolations. J. Electronic Imaging, vol. 2, pp. 53-61, Jan. 1993.

73. Industrial colour-difference evaluation, CIE 116-1995 Technical Report, Iternational Commission on Illumination.

74. Kalman R., Noised systems identification. Advances of Mathematical sciences, v. 40, issue 4(244), 1985.

75. Lammens J.M. A Computational Model of Color Perception and Color Naming Диссертация иа соискание докторской степени / University of New-York, Graduated School, 1994 256 c.

76. Lawson C.L., Hanson R.J., Solving Least Squares Problems. Prentice Hall, Inc., Englenood Cliffs, N.J., 1974.

77. Lee S., Wolberg G., Shin S. Y., Scattered data interpolation with multilevel B-splines, IEEE transactions on visualization and computer graphics, vol. 3, no. 3, july-september 1997, pp.228-244.

78. MacAdam D. Projective transformation of I.C.I, color specifications, J. Opt. Soc. Am., 27, 294, 1937.

79. Marquardt D. W. Generalised inverses, ridge regression, biased linear and nonlinear estimation, Technometrics, 1970, v. 12, № 3.

80. Mitchell M., An Introduction to Genetic Algorithms. The MIT Press, London, 1999, 161 p.

81. Mourad S. Color predicting model for electrophotographic prints on common office paper. PhD thesis № 2708 (2003), Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland, 2003, 128p.

82. H. E. J. Neugebauer, Die theoretischen grundlagen des mahrfarbenbuchdrucks, Zeitschrift fur Wissenshaftliche Photographie Photophysik und Photochemie 36:4, 73-89 (1937).

83. Nikonorov A. V., Iterative improvement of estimations using multifractal spectra. Proc. of the conf. Concurrent Engineering Resesarch and Application, Dallas, USA July 2005

84. Roberts. A.~J. Estimate generalised fractal dimensions of a set of points. Technical report, http://www.sci.usq.edu.au/staff/aroberts/fdim.sh, 1994

85. R. W. G., Measuring Color. Fountain Press, 3rd. edition, 1998.

86. Saman K., Input Space Segmentation with a Genetic Algorithm for Generation of Rule Based Classifier Systems. In Chambers L., Practical handbook of genetic algorithms : new frontiers, vol. 2. CRC Press, Boca Raton, Florida, 1995. 421 p.

87. Seber G.A. Linear regression analysis. John Wiley and Sons. New-York. London.

88. Vose, M. D. and Wright, A. H. Form invariance and implicit parallelism. Evolutionaiy Computation, 9(3), 2001, 355-370.

89. Wyszecki G., Stiles W. S. Color Science. John Wiley & Sons, Inc.,2nd. edition, 1982.

90. Yule J. A. C., W. J. Nielsen, The penetration of light into paper and its effect on halftone reproduction, Proc. 1951 of Technical Assoc. Graphics Arts, pp. 65-76, 1951.