Реферат : Морфологический анализ цветных (спектрозональных) изображений (работа 1) 


Полнотекстовый поиск по базе:

Главная >> Реферат >> Математика


Морфологический анализ цветных (спектрозональных) изображений (работа 1)




Ìîðôîëîãè÷åñêèé àíàëèç öâåòíûõ (ñïåêòðîçîíàëüíûõ) èçîáðàæåíèé.

Ïûòüåâ Þ.Ï.

Ìîñêîâñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò, Ìîñêâà, Ðîññèÿ

1. Ââåäåíèå

Õîðîøî èçâåñòíî, ÷òî изображения îäíîé è òîé æå ñöåíû, ïîëó÷åííûå ïðè ðàçëè÷íûõ óñëîâèÿõ îñâåùåíèÿ è(èëè) èçìåíåííûõ1 îïòè÷åñêèõ ñâîéñòâàõ îáúåêòîâ ìîãóò îòëè÷àòüñÿ ðàäèêàëüíî. Ýòî îáñòîÿòåëüñòâî ïîðîæäàåò çíà÷èòåëüíûå òðóäíîñòè â ïðèêëàäíûõ çàäà÷àõ àíàëèçà è èíòåðïðåòàöèè èçîáðàæåíèé ðåàëüíûõ ñöåí, â êîòîðûõ ðåøåíèå äîëæíî íå çàâèñåòü îò óñëîâèé ðåãèñòðàöèè èçîáðàæåíèé. Ðå÷ü èäåò, íàïðèìåð, î çàäà÷àõ âûäåëåíèÿ íåèçâåñòíîãî îáúåêòà íà ôîíå èçâåñòíîé ìåñòíîñòè, èçâåñòíîãî îáúåêòà íà ïðîèçâîëüíîì ôîíå ïðè íåêîíòðîëèðóåìûõ óñëîâèÿõ îñâåùåíèÿ, î çàäà÷å ñîâìåùåíèÿ èçîáðàæåííèé îäíîé è òîé æå ñöåíû, ïîëó÷åííûõ â ðàçëè÷íûõ ñïåêòðàëüíûõ äèàïàçîíàõ è ò.ä.

Ìåòîäû ìîðôîëîãè÷åñêîãî àíàëèçà, ðàçðàáîòàííûå áîëåå äåñÿòè ëåò òîìó íàçàä, [1-5], äëÿ ðåøåíèÿ ïåðå÷èñëåííûõ çàäà÷, áûëè â îñíîâíîì îðèåíòèðîâàíû äëÿ ïðèìåíåíèÿ ê ÷åðíî-áåëûì èçîáðàæåíèÿì2 è îêàçàëèñü äîñòàòî÷íî ýôôåêòèâíûìè, [5-11].

Ìåæäó òåì, ïî ìåíüøåé ìåðå äâà îáñòîÿòåëüñòâà óêàçûâàþò íà öåëåñîîáðàçíîñòü ðàçðàáîòêè ìîðôîëîãè÷åñêèõ ìåòîäîâ àíàëèçà öâåòíûõ èçîáðàæåíèé. Âî-ïåðâûõ, â çàäà÷å îáíàðóæåíèÿ è âûäåëåíèÿ îáúåêòà ïîñëåäíèé, êàê ïðàâèëî, ïðåæäå âñåãî öâåòîì îòëè÷àåòñÿ îò ôîíà. Âî-âòîðûõ, îïèñàíèå ôîðìû èçîáðàæåíèÿ â òåðìèíàõ öâåòà ïîçâîëèò ïðàêòè÷åñêè óñòðàíèòü ýôôåêò òåíåé è âëèÿíèå íåîïðåäåëåííîñòè â ïðîñòðàíñòâåííîì ðàñïðåäåëåíèè èíòåíñèâíîñòè ñïåêòðàëüíî îäíîðîäíîãî îñâåùåíèÿ.

2. Öâåò è ÿðêîñòü ñïåêòîçîíàëüíîãî èçîáðàæåíèÿ.

Ðàññìîòðèì íåêîòîðûå àñïåêòû òåîðèè öâåòà òàê íàçûâàåìûõ ìíîãîñïåêòðàëüíûõ (ñïåêòðîçîíàëüíûõ, [13]) èçîáðàæåíèé, àíàëîãè÷íîé êëàññè÷åñêîé êîëîðèìåòðèè [12]. Áóäåì ñ÷èòàòü çàäàííûìè n äåòåêòîðîâ èçëó÷åíèÿ ñî ñïåêòðàëüíûìè ÷óâñòâèòåëüíîñòÿìè j=1,2,...,n, ãäå Î(0,) - äëèíà âîëíû èçëó÷åíèÿ. Èõ âûõîäíûå ñèãíàëû, îòâå÷àþùèå ïîòîêó èçëó÷åíèÿ ñî ñïåêòðàëüíîé ïëîòíîñòüþ e()³0, (0,), äàëåå íàçûâàåìîé èçëó÷åíèåì, îáðàçóþò âåêòîð , w= . Îïðåäåëèì ñóììàðíóþ ñïåêòðàëüíóþ ÷óâñòâèòåëüíîñòü äåòåêòîðîâ , (0,), è ñîîòâåòñòâóþùèé ñóììàðíûé ñèãíàë íàçîâåì ÿðêîñòüþ èçëó÷åíèÿ e. Âåêòîð íàçîâåì öâåòîì èçëó÷åíèÿ e. Åñëè öâåò e è ñàìî èçëó÷åíèå íàçîâåì ÷åðíûì. Ïîñêîëüêó ðàâåíñòâà è ýêâèâàëåíòíû, ðàâåíñòâî èìååò ñìûñë è äëÿ ÷åðíîãî öâåòà, ïðè÷åì â ýòîì ñëó÷àå - ïðîèçâîëüíûé âåêòîð, ÿðêîñòü îòîðîãî ðàâíà åäèíèöå. Èçëó÷åíèå eíàçîâåì áåëûì è åãî öâåò îáîçíà÷èì åñëè îòâå÷àþùèå åìó âûõîäíûå ñèãíàëû âñåõ äåòåêòîðîâ îäèíàêîâû:

.

Âåêòîðû , è , , óäîáíî ñ÷èòàòü ýëåìåíòàìè n-ìåðíîãî ëèíåéíîãî ïðîñòðàíñòâà . Âåêòîðû fe, ñîîòâåòñòâóþùèå ðàçëè÷íûì èçëó÷åíèÿì e, ñîäåðæàòñÿ â êîíóñå . Êîíöû âåêòîðîâ ñîäåðæàòñÿ â ìíîæåñòâå , ãäå Ï - ãèïåðïëîñêîñòü .

Äàëåå ïðåäïîëàãàåòñÿ, ÷òî âñÿêîå èçëó÷åíèå , ãäå E - âûïóêëûé êîíóñ èçëó÷åíèé, ñîäåðæàùèé âìåñòå ñ ëþáûìè èçëó÷åíèÿìè âñå èõ âûïóêëûå êîìáèíàöèè (ñìåñè) Ïîýòîìó âåêòîðû â îáðàçóþò âûïóêëûé êîíóñ , à âåêòîðû .

Åñëè òî è èõ àääèòèâíàÿ ñìåñü . Äëÿ íåå

. (1)

Îòñþäà ñëåäóåò

Ëåììà 1. ßðêîñòü fe è öâåò e ëþáîé àääèòèâíîé ñìåñè e èçëó÷åíèé e1(),...,em(), m=1,2,... îïðåäåëÿþòñÿ ÿðêîñòÿìè è öâåòàìè ñëàãàåìûõ.

Ïîä÷åðêíåì, ÷òî ðàâåíñòâî , îçíà÷àþùåå ôàêò ñîâïàäåíèÿ ÿðêîñòè è öâåòà èçëó÷åíèé e è , êàê ïðàâèëî, ñîäåðæèò ñðàâíèòåëüíî íåáîëüøóþ èíôîðìàöèþ îá èõ îòíîñèòåëüíîì ñïåêòðàëüíîì ñîñòàâå. Îäíàêî çàìåíà e íà â ëþáîé àääèòèâíîé ñìåñè èçëó÷åíèé íå èçìåíèò íè öâåòà, íè ÿðêîñòè ïîñëåäíåé.

Äàëåå ïðåäïîëàãàåòñÿ, ÷òî âåêòîð w òàêîâ, ÷òî â E ìîæíî óêàçàòü áàçîâûå èçëó÷åíèÿ , äëÿ êîòîðûõ âåêòîðû , j=1,...,n, ëèíåéíî íåçàâèñèìû. Ïîñêîëüêó öâåò òàêèõ èçëó÷åíèé íåïðåìåííî îòëè÷åí îò ÷åðíîãî, èõ ÿðêîñòè áóäåì ñ÷èòàòü åäèíè÷íûìè, , j=1,...,n.  òàêîì ñëó÷àå èçëó÷åíèå õàðàêòåðèçóåòñÿ ëèøü öâåòîì , j=1,...,n.

Äëÿ âñÿêîãî èçëó÷åíèÿ e ìîæíî çàïèñàòü ðàçëîæåíèå

, (1*)

â êîòîðîì - êîîðäèíàòû â áàçèñå ,

èëè, â âèäå âûõîäíûõ ñèãíàëîâ äåòåêòîðîâ èçëó÷åíèÿ, - , ãäå , , - âûõîäíîé ñèãíàë i-ãî äåòåêòîðà, îòâå÷àþùèé j-îìó èçëó÷åíèþ j(), i, j=1,...,n. Ìàòðèöà - ñòîõàñòè÷åñêàÿ, ïîñêîëüêó åå ìàòðè÷íûå ýëåìåíòû êàê ÿðêîñòè áàçîâûõ èçëó÷åíèé íåîòðèöàòåëüíû è , j=1,...,n. Ïðè ýòîì ÿðêîñòü è âåêòîð öâåòà , , j=1,...,n, (êîíåö êîòîðîãî ëåæèò â Ï) îïðåäåëÿþòñÿ êîîðäèíàòàìè j è öâåòàìè èçëó÷åíèé , j=1,...,n, è íå çàâèñÿò íåïîñðåäñòâåííî îò ñïåêòðàëüíîãî ñîñòàâà èçëó÷åíèÿ e.

 ðÿäå ñëó÷àåâ áåëîå èçëó÷åíèå åñòåñòâåííî îïðåäåëÿòü èñõîäÿ èç áàçîâûõ èçëó÷åíèé, à íå èç âûõîäíûõ ñèãíàëîâ äåòåêòîðîâ, ñ÷èòàÿ áåëûì âñÿêîå èçëó÷åíèå, êîòîðîìó â (1*) îòâå÷àþò ðàâíûå êîîðäèíàòû: .

Çàìåòèì, ÷òî ñëàãàåìûå â (1*), ó êîòîðûõ j<0,3 ôèçè÷åñêè èíòåðïðåòèðóþòñÿ êàê ñîîòâåòñòâóþùèå èçëó÷åíèÿì, "ïîìåùåííûì" â ëåâóþ ÷àñòü ðàâåíñòâà (1*) ñ êîýôôèöèåíòàìè -j>0: .  òàêîé ôîðìå ðàâåíñòâî (1*) ïðåäñòàâëÿåò “áàëàíñ èçëó÷åíèé”.

Îïðåäåëèì â ñêàëÿðíîå ïðîèçâåäåíèå è âåêòîðû , áèîðòîãîíàëüíî ñîïðÿæåííûå ñ : , i,j=1,...,n.

Ëåììà 2.  ðàçëîæåíèè (1*) , j=1,...,n, . ßðêîñòü , ãäå , ïðè÷åì âåêòîð îðòîãîíàëåí ãèïåðïëîñêîñòè Ï, òàê êàê , i,j=1,...,n.

×òî êàñàåòñÿ ñêàëÿðíîãî ïðîèâåäåíèÿ , òî åãî åñòåñòâåííî îïðåäåëÿòü òàê, ÷òîáû âûõîäíûå ñèãíàëû äåòåêòîðîâ áûëè êîîðäèíàòàìè fe â íåêîòîðîì îðòîíîðìèðîâàííîì áàçèñå . Â ýòîì áàçèñå êîíóñ . Çàìåòèì, ÷òî äëÿ ëþáûõ âåêòîðîâ è, òåì áîëåå, äëÿ , 4.

Ïóñòü Õ - ïîëå çðåíèÿ, íàïðèìåð, îãðàíè÷åííàÿ îáëàñòü íà ïëîñêîñòè R2, èëè íà ñåòêå , ñïåêòðàëüíàÿ ÷óâñòâèòåëüíîñòü j-ãî äåòåêòîðà èçëó÷åíèÿ, ðàñïîëîæåííîãî â òî÷êå ; - èçëó÷åíèå, ïîïàäàþùåå â òî÷êó . Èçîáðàæåíèåì íàçîâåì âåêòîðíîçíà÷íóþ ôóíêöèþ

(2**)

Òî÷íåå, ïóñòü Õ - ïîëå çðåíèÿ, (Õ, Ñ, ) - èçìåðèìîå ïðîñòðàíñòâî Õ ñ ìåðîé C - -àëãåáðà ïîäìíîæåñòâ X. Öâåòíîå (ñïåêòðîçîíàëüíîå) èçîáðàæåíèå îïðåäåëèì ðàâåíñòâîì

, (2)

â êîòîðîì ïî÷òè äëÿ âñåõ , , - -èçìåðèìûå ôóíêöèè íà ïîëå çðåíèÿ X, òàêèå, ÷òî

.

Öâåòíûå èçîáðàæåíèÿ îáðàçóþò ïîäêëàññ ôóíêöèé ëåáåãîâñêîãî êëàññà ôóíêöèé . Êëàññ öâåòíûõ èçîáðàæåíèé îáîçíà÷èì LE,n.

Âïðî÷åì, äëÿ óïðîùåíèÿ òåðìèíîëîãèè äàëåå ëþáîé ýëåìåíò íàçûâàåòñÿ öâåòíûì èçîáðàæåíèåì, à óñëîâèå

(2*)

óñëîâèåì ôèçè÷íîñòè èçîáðàæåíèé f().

Åñëè f - öâåòíîå èçîáðàæåíèå (2), òî , êàê íåòðóäíî ïðîâåðèòü, - ÷åðíî-áåëîå èçîáðàæåíèå [2], ò.å. , . Èçîáðàæåíèå , íàçîâåì ÷åðíî-áåëûì âàðèàíòîì öâåòíîãî èçîáðàæåíèÿ f, à öâåòíîå èçîáðàæåíèå , f(x)¹0, xX - öâåòîì èçîáðàæåíèÿ f.  òî÷êàõ ìíîæåñòâà Â={xX: f(x)=0} ÷åðíîãî öâåòà (x), xÂ, - ïðîèçâîëüíûå âåêòîðû èç , óäîâëåòâîðÿþùèå óñëîâèþ: ÿðêîñòü (x)=1. ×åðíî-áåëûì âàðèàíòîì öâåòíîãî èçîáðàæåíèÿ f áóäåì òàêæå íàçûâàòü öâåòíîå èçîáðàæåíèå b(), èìåþùåå â êàæäîé òî÷êå Õ òó æå ÿðêîñòü, ÷òî è f, b(x)=f(x), xX, è áåëûé öâåò, (x)=b(x)/b(x)=, xX.

3. Форма цветного изображения.

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

Нередко изменение распределения интенсивности освещения сопровождается значительным изменением и его спектрального состава, но - пространственно однородным, одним и тем же в пределах всей изображаемой сцены. Поскольку между спектром излучения e и цветом нет взаимно однозначного соответствия, модель сопутствующего преобразования изображения f(x) в терминах преобразования его цвета (). Для этого определим отображение A(): , ставящее в соответствие каждому вектору цвета подмножество поля зрения в точках которого изображение , имеет постоянный цвет .

Пусть при рассматриваемом изменении освещения и, соответственно, ; предлагаемая модель преобразования изображения состоит в том, что цвет преобразованного изображения должен быть также постоянным на каждом множестве A(), хотя, вообще говоря, - другим, отличным от . Характекрным в данном случае является тот факт, что равенство влечет . Если - самое детальное изображение сцены, то, вообще говоря, на различных множествах A() и A() цвет изображения может оказаться одинаковым5.

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

Для определения понятия формы цветного изображения f() на удобно ввести частичный порядок , т.е. бинарное отношение, удовлетворяющее условиям: 1) , 2) , , то , ; отношение должно быть согласованным с определением цветного изображения (с условием физичности), а именно, , если . Отношение интерпретируется аналогично тому, как это принято в черно-белой морфологии[2], а именно, означает, что изображения fиg сравнимы по форме, причем форма g не сложнее, чем форма f. Если и , то f и g назовем совпадающими по форме (изоморфными), f ~ g. Например, если f и g - изображения одной и той же сцены, то g, грубо говоря, характеризует форму изображенных объектов не точнее (подробнее, детальнее), чем f, если .

В рассматриваемом выше примере преобразования изображений если между множествами A(), и A(), существует взаимно-однозначное соответствие, т.е., если существует функция , такая, что A(())= A(), , причем , если . В этом случае равенства и эквивалентны, и изоморфны и одинаково детально характеризуют сцену, хотя и в разных цветах.

Если же не взаимно однозначно, то A()=U A() è . В этом случае равенство влечет (но не эквивалентно) , передает, вообще говоря, не все детали сцены, представленные в .

Пусть, скажем, g - черно-белый вариант f, т.е. g(x)=f(x) и g(x)/g(x)=, xX. Если преобразование - следствие изменившихся условий регистрации изображения, то, естественно, . Аналогично, если fgизображения одной и той же сцены, но в gвследствие неисправности выходные сигналы некоторых датчиков равны нулю, то . Пусть F - некоторая полугруппа преобразований , тогда для любого преобразования FF , поскольку, если некоторые детали формы объекта не отражены в изображении f, то они, тем более, не будут отражены в g.

Формой изображения f назовем множество изображений , форма которых не сложнее, чем форма f`, и их пределов в (черта символизирует замыкание в ). Формой изображения fв широком смысле назовем минимальное линейное подпространство , содержащее . Если считать, что для любого изображения , то это будет означать, что отношение непрерывно относительно сходимости в в том смысле, что .

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

4. Форма кусочно-постоянного (мозаичного) цветного изображения.

Во многих практически важных задачах форма объекта на изображении может быть охарактеризована специальной структурой излучения, достигающего поле зрения X в виде здесь - индикаторные функции непересекающихся подмножеств Аi, i=1,…...,N, положительной меры поля зрения Х, на каждом из которых функции , , j=1,...,n, i=1,...,N, непрерывны. Поскольку согласно лемме 2

, (3)

то цветное изображение fe, такого объекта характеризует его форму непрерывным распределением яркости и цвета на каждом подмножестве Ai, i=1,...,N. Для изображения , где , также характерно напрерывное распределение яркости и цвета на каждом Ai, если , - непрерывные функции.

Если, в частности, цвет и яркость постоянны на Ai, i=1,...,N, то это верно и для всякого изображения , если не зависит явно от . Для такого изображения примем следующее представление:

, (4)

его черно-белый вариант

(4*)

на каждом Ai имеет постоянную яркость , и цвет изображения (4)

(4**)

не меняется на Ai и равен , i=1,...,N.

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

. (4***)

v(a), очевидно, содержится в nN мерном линейном подпространстве

, (4****)

которое назовем формой a() в широком смысле.

Форму в широком смысле любого изображения a(), у которого не обязательно различны яркости и цвета на различных подмножествах Ai ,i=1,...,N, определим как линейное подпространство , íàòÿíóòîå íå âåêòîð-ôóíêöèè Fa(),FF, где F - класс преобразований , îïðåäåëåííûõ êàê ïðåîáðàçîâàíèÿ âåêòîðîâ a(x)Fa(x) во всех точках xX; здесь F - любое преобразование . Òîò ôàêò, ÷òî F îçíà÷àåò êàê ïðåîáðàçîâàíèå , òàê è ïðåîáðàçîâàíèå , íå äîëæåí âûçûâàòü íåäîðàçóìåíèÿ.

Изображения из конуса(4***) имеют форму, которая не сложнее, чем форма a() (4), поскольку некоторые из них могут иметь одно и то же значение яркости или(и) цвета на различных множествах Аi, i=1,…………..,N. Также множества оказываются, по существу, объединенными в одно, что и приводит к упрощению формы изображения, поскольку оно отражает меньше деталей формы изображенного объекта, чем изображение (4). Это замечание касается и L(a()), если речь идет о форме в широком смысле.

Ëåììà 3. Ïóñòü {Ài} - èçìåðèìîå ðàçáèåíèå X: .

Изображение (3) имеет на каждом подмножестве Ai :

постоянную яркость и цвет , если и только если выполняется равенство (4);

постоянный цвет , если и только если в (3) ;

постоянную яркость fi , i=1,...,N, если и только если в (3) не зависит от , i=1,…...,N.

Доказательство . На множестве Ai яркость и цвет изображения (3) равны соответственно6

, , i=1,.…..,N.

Если выполнено равенство (4), то и от не зависят. Наоборот, если и , то и , т.е. выполняется (4).

Если , то цвет не зависит от . Наоборот, пусть не зависит от . В силу линейной независимости координаты (i)(x) не зависят от , т.е. и, следовательно, где - яркость на A i и . Последнее утверждение очевидно

Цвет изображения определяется как электродинамическими свойствами поверхности изображенного объекта, так и спектральным составом облучающего электромагнитного излучения в том диапазоне, который используется для регистрации изображения. Речь идет о спектральном составе излучения, покидающего поверхность объекта и содержащего как рассеянное так и собственное излучения объекта. Поскольку спектральный состав падающего излучения, как правило, пространственно однороден, можно считать, что цвет изображения несет информацию о свойствах поверхности объекта, о ее форме, а яркость в значительной степени зависит и от условий “освещения”. Поэтому на практике в задачах морфологического анализа цветных изображений сцен важное значение имеет понятие формы изображения, имеющего постоянный цвет и произвольное распределение яркости в пределах заданных подмножеств Ai , i=1,...,N, поля зрения X.

Итак, пусть в согласии с леммой 3

, (5)

где, - индикаторная функция Ai, , функция gi задает распределение яркости

(6)

в пределах Ai при постоянном цвете

, i=1,...,N, (7)

причем для изображения (5) цвета (i), i=1,.…..,N, считаются попарно различными, а функции g(i), i=1,.…..,N, - удовлетворяющими условиям i=1,.…..,N.

Нетрудно заметить, что в выражениях (5),(6) и (7) без потери общности можно принять условие нормировки , позволяющее упростить выражения (6) и (7) для распределений яркости и цвета. С учетом нормировки распределение яркости на Ai задается функцией а цвет на Ai равен

(7*)

Форму изображения (5) определим как класс всех изображений

(8)

,

êàæäîå èç êîòîðûõ, êàê è èçîáðàæåíèå (5), èìååò ïîñòîÿííûé öâåò â ïðåäåëàõ êàæäîãî Ai, i=1,...,N. Ôîðìà òàêèõ èçîáðàæåíèé íå ñëîæíåå, ÷åì ôîðìà f() (5), ïîñêîëüêó â èçîáðàæåíèè íà íåêîòîðûõ ðàçëè÷íûõ ïîäìíîæåñòâàõ Ai, i=1,...,N, ìîãóò ñîâïàäàòü çíà÷åíèÿ öâåòà, êîòîðûå íåïðåìåíðíî ðàçëè÷íû â èçîáðàæåíèè f() (5). Ñîâïàäåíèå öâåòà íà ðàçëè÷íûõ ïîäìíîæåñòâàõ Ai, i=1,...,N âåäåò ê óïðîùåíèþ ôîðìû èçîáðàæåíèÿ ïî ñðàâíåíèþ ñ ôîðìîé f() (5). Âñå èçîáðàæåíèÿ , èìåþùèå ðàçëè÷íûé öâåò íà ðàçëè÷íûõ Ai, i=1,...,N, ñ÷èòàþòñÿ èçîìîðôíûìè fè ìåæäó ñîáîé), ôîðìà îñòàëüíûõ íå ñëîæíåå, ÷åì ôîðìà f. Åñëè , òî, î÷åâèäíî, .

Åñëè â (8) ÿðêîñòü , òî öâåò íà Ai ñ÷èòàåòñÿ ïðîèçâîëüíûì (ïîñòîÿííûì), åñëè æå â òî÷êàõ íåêîòîðîãî ïîäìíîæåñòâà , òî öâåò íà Ai ñ÷èòàåòñÿ ðàâíûì öâåòó íà , i=1,...,N.

Цвет изображения (8) может не совпадать с цветом (5). Если же по условию задачи все изображения , форма которых не сложнее, чем форма , должны иметь на Ai, i=1,...,N, тот же цвет, что и у то следует потребовать, чтобы , в то время, как яркости îñòàþòñÿ ïðîèçâîëüíûìè (åñëè , òî öâåò íà Ai îïðåäåëÿåòñÿ ðàâíûì öâåòó f íà Ai, i=1,...,N).

Нетрудно определить форму любого, не обязательно мозаичного, изображения fв том случае, когда допустимы произвольные изменения яркости при неизменном цвете (x) в каждой точке . Множество, содержащее все такие изображения

(9)

назовем формой в широком смысле изображения , у которого f(x)0, -почти для всех , [ср. 2]. является линейным подпространством , содержащем любую форму

, (10)

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

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

5. Çàäà÷è àïïðîêñèìàöèè öâåòíûõ èçîáðàæåíèé. Форма как оператор наилучшего приближения.

Ðàññìîòðèì âíà÷àëå çàäà÷è ïðèáëèæåíèÿ êóñî÷íî-ïîñòîÿííûìè (ìîçàè÷íûìè) èçîáðàæåíèÿìè. Ðåøåíèå ýòèõ çàäà÷ ïîçâîëèò ïîñòðîèòü ôîðìó èçîáðàæåíèÿ â òîì ñëó÷àå, êîãäà ñ÷èòàåòñÿ, ÷òî äëÿ ëþáîãî ïðåîáðàçîâàíèÿ , äåéñòâóþùåãî íà èçîáðàæåíèå êàê íà âåêòîð â êàæäîé òî÷êå è îñòàâëÿþùåãî ýëåìåíòîì , ò.å. èçîáðàæåíèåì. Ôîðìà â øèðîêîì ñìûñëå îïðåäåëÿåòñÿ êàê îïåðàòîð íàèëó÷øåãî ïðèáëèæåíèÿ èçîáðàæåíèÿ èçîáðàæåíèÿìè

ãäå - êëàññ ïðåîáðàçîâàíèé , òàêîé, ÷òî . Èíà÷å ìîæíî ñ÷èòàòü, ÷òî

(10*)

à - îïåðàòîð íàèëó÷øåãî ïðèáëèæåíèÿ ýëåìåíòàìè ìíîæåñòâà , ôîðìà êîòîðûõ íå ñëîæíåå, ÷åì ôîðìà . Õàðàêòåðèñòè÷åñêèì äëÿ ÿâëÿåòñÿ òîò ôàêò, ÷òî, åñëè f(x)=f(y), òî äëÿ ëþáîãî .

5.1. Приближение цветного изображения изображениями, цвет и яркость которых постоянны на подмножествах разбиения поля зрения X.

Задано разбиение , òðåáóåòñÿ îïðåäåëèòü ÿðêîñòü è öâåò íàèëó÷øåãî ïðèáëèæåíèÿ íà êàæäîì . Ðàññìîòðèì çàäà÷ó íàèëó÷øåãî ïðèáëèæåíèÿ â öâåòíîãî èçîáðàæåíèÿ f() (2) èçîáðàæåíèÿìè (4), â êîòîðûõ ñ÷èòàåòñÿ çàäàííûì ðàçáèåíèå ïîëÿ çðåíèÿ X è òðåáóåòñÿ îïðåäåëèòü èç óñëîâèÿ

(11)

Òåîðåìà 1. Ïóñòü . Òîãäà ðåøåíèå çàäà÷è (11) èìååò âèä

, i=1,...,N, j=1,...,n, (12)

è èñêîìîå èçîáðàæåíèå (4) çàäàåòñÿ ðàâåíñòâîì

. (13)

Îïåðàòîð ÿâëÿåòñÿ îðòîãîíàëüíûì ïðîåêòîðîì íà ëèíåéíîå ïîäïðîñòðàíñòâî (4****) èçîáðàæåíèé (4), ÿðêîñòè è öâåòа êîòîðûõ íå èçìåíÿþòñÿ â ïðåäåëàõ êàæäîãî Ai , i=1,...,N.

×åðíî-áåëûé âàðèàíò (4*) öâåòíîãî èçîáðàæåíèÿ (4) ÿâëÿåòñÿ íàèëó÷øåé â àïïðîêñèìàöèåé ÷åðíî-áåëîãî âàðèàíòà öâåòíîãî èçîáðàæåíèÿ f, åñëè öâåòíîå èçîáðàæåíèå (4) ÿâëÿåòñÿ íàèëó÷øåé â àïïðîêñèìàöèåé öâåòíîãî èçîáðàæåíèÿ f. Оператор , является ортогональным проектором на линейное подпространство черно-белых изображений, яркость которых постоянна в пределах каждого .

 òî÷êàõ ìíîæåñòâà öâåò (4**) íàèëó÷øåé àïïðîêñèìàöèè (4) öâåòíîãî èçîáðàæåíèÿ f (2) ÿâëÿåòñÿ öâåòîì àääèòèâíîé ñìåñè ñîñòàâëÿþùèõ f èçëó÷åíèé, êîòîðûå ïîïàäàþò íà .

Äîêàçàòåëüñòâî. Ðàâåíñòâà (12) - óñëîâèÿ ìèíèìóìà ïîëîæèòåëüíî îïðåäåëåííîé êâàäðàòè÷íîé ôîðìû (11), Ï - îðòîãîíàëüíûé ïðîåêòîð, ïîñêîëüêó â çàäà÷å (11) íàèëó÷øàÿ àïïðîêñèìàöèÿ - îðòîãîíàëüíàÿ ïðîåêöèÿ f íà . Âòîðîå óòâåðæäåíèå ñëåäóåò èç ðàâåíñòâà

, âûòåêàþùåãî èç (13). Последнеå óòâåðæäåíèå ñëåäóåò èç ðàâåíñòâ

,i=1,...,N âûòåêàþùèõ èç (12) è ðàâåíñòâà (1), â êîòîðîì èíäåêñ k ñëåäóåò çàìåíèòü íà xX.

Çàìå÷àíèå 1. Äëÿ ëþáîãî èçìåðèìîãî ðàçáèåíèÿ îðòîãîíàëüíûå ïðîåêòîðû è îïðåäåëÿþò ñîîòâåòñòâåííî ôîðìó â øèðîêîì ñìûñëå öâåòíîãî èçîáðàæåíèя (4), öâåò è ÿðêîñòü êîòîðîãî, ïîñòîÿííûå â ïðåäåëàõ êàæäîãî , ðàçëè÷íû äëÿ ðàçëè÷íûõ , èáî , è ôîðìó â øèðîêîì ñìûñëå ÷åðíî-áåëого èçîáðàæåíèя, ÿðêîñòü êîòîðого ïîñòîÿííà íà êàæäîì è ðàçëè÷íà äëÿ ðàçíûõ ,[2].

Åñëè ó÷åñòü, óñëîâèå ôèçè÷íîñòè (2*), òî ôîðìîé öâåòíîãî èçîáðàæåíèÿ ñëåäóåò ñ÷èòàòü ïðîåêòîð íà âûïóêëûé замкнутый êîíóñ (4***)

Аналогично формой черно-белого изображения следует считать проектор на выпуклый замкнутый конус изображений (4*), таких, что [2]. Дело в том, что оператор определяет форму изображения (4), а именно

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

Аналогично для черно-белого изображения a()

,7 [2]. И проектор можно отождествить с формой изображения (4*), как это сделано в работах [2,3].

Примечания.

Формы в широком смысле не определяются связью задач наилучшего приближения элементами è , êîòîðàÿ èçâåñòíà êàê òðàíçèòèâíîñòü ïðîåöèðîâàíèÿ. Èìåííî, åñëè îïåðàòîð íàèëó÷øåãî â ïðèáëèæåíèÿ çëåìåíòàìè âûïóêëîãî çàìêíóòîãî (â è â ) êîíóñà , òî . Èíà÷å ãîâîðÿ, äëÿ îïðåäåëåíèÿ íàèëó÷øåãî â ïðèáëèæåíèÿ ýëåìåíòàìè ìîæíî âíà÷àëå íàéòè îðòîãîíàëüíóþ ïðîåêöèþ èçîáðàæåíèÿ íà , à çàòåì ñïðîåöèðîâàòü â íà . Ïðè ýòîì êîíå÷íîìåðíûé ïðîåêòîð äëÿ êàæäîãî êîíêðåòíîãî êîíóñà ìîæåò áûòü ðåàëèçîâàí ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, à äëÿ ìíîãèõ çàäà÷ ìîðôîëîãè÷åñêîãî àíàëèçà èçîáðàæåíèé äîñòàòî÷íûì îêàçûâàåòñÿ èñïîëüçîâàíèå ëèøü ïðîåêòîðà Ï .

Форма в широком смысле (4***) èçîáðàæåíèÿ (4) ïîëíîñòüþ îïðåäåëÿåòñÿ èçìåðèìûì ðàçëîæåíèåì , ïîñëåäíåå, â ñâîþ î÷åðåäü îïðåäåëÿåòñÿ èçîáðàæåíèåì

,

åñëè âåêòîðû ïîïàðíî ðàçëè÷íû. Åñëè ïðè ýòîì , òî ôîðìà â øèðîêîì ñìûñëå ìîæåò áûòü îïðåäåëåíà è êàê îïåðàòîð Ï îðòîãîíàëüíîãî ïðîåöèðîâàíèÿ íà , îïðåäåëåííûé ðàâåíñòâîì (13).

Ïîñìîòðèì, êàêèì îáðàçîì âîñïîëüçîâàòüñÿ ýòèìè ôàêòàìè ïðè ïîñòðîåíèè ôîðìû â øèðîêîì ñìûñëå êàê îïåðàòîðà îðòîãîíàëüíîãî ïðîåöèðîâàíèÿ íà ëèíåéíîå ïîäïðîñòðàíñòâî (10*) äëÿ ïðîèçâîëüíîãî èçîáðàæåíèÿ . Ïóñòü - ìíîæåñòâî çíà÷åíèé è - èçìåðèìîå ðàçáèåíèå X , ïîðîæäåííîå , â êîòîðîì - ïîäìíîæåñòâî X , â ïðåäåëàõ êîòîðîãî èçîáðàæåíèå èìååò ïîñòîÿííûå ÿðêîñòü è öâåò, îïðåäåëÿåìûå âåêòîðîì , åñëè .

Îäíàêî äëÿ íàéäåííîãî ðàçáèåíèÿ óñëîâèå , âîîáùå ãîâîðÿ, íåâûïîëíèìî è, ñëåäîâàòåëüíî, òåîðåìà 1 íå ïîçâîëÿåò ïîñòðîèòü îðòîãîíàëüíûé ïðîåêòîð Ï íà . Ïîêàæåì, ÷òî Ï ìîæíî ïîëó÷èòü êàê ïðåäåë ïîñëåäîâàòåëüíîñòè êîíå÷íîìåðíûõ îðòîãîíàëüíûõ ïðîåêòîðîâ. Çàìåòèì âíà÷àëå, ÷òî ëþáîå èçîáðàæåíèå ìîæíî ïðåäñòàâèòü â âèäå ïðåäåëà (â ) äîëæíûì îáðàçîì îðãàíèçîâàííîé ïîñëåäîâàòåëüíîñòè ìîçàè÷íûõ èçîáðàæåíèé

(*)

ãäå - èíäèêàòîð ìíîæåñòâà , ïðèíàäëåæàùåãî èçìåðèìîìó ðàçáèåíèþ

 (*) ìîæíî, íàïðèìåð, èñïîëüçîâàòü òàê íàçûâàåìóþ èñ÷åðïûâàþùóþ ïîñëåäîâàòåëüíîñòü ðàçáèåíèé [], óäîâëåòâîðÿþùóþ ñëåäóþùèì óñëîâèÿì

- - C - èçìåðèìî, ;

- N+1-oe ðàçáèåíèå ÿâëÿåòñÿ ïðîäîëæåíèåì N-ãî, ò.å. äëÿ ëþáîãî , íàéäåòñÿ i=i(j), , òàêîå, ÷òî ;

- ìèíèìàëüíàÿ -àëãåáðà, ñîäåðæàùàÿ âñå , ñîâïàäàåò ñ C.

Ëåììà (*). Ïóñòü - èñ÷åðïûâàþùàÿ ïîñëåäîâàòåëü-íîñòü ðàçáèåíèé X è - òî ìíîæåñòâî èç , êîòîðîå ñîäåðæèò . Òîãäà äëÿ ëþáîé C-èçìåðèìîé ôóíêöèè

è -ïî÷òè äëÿ âñåõ [ ]. 

Âîñïîëüçóåìñÿ ýòèì ðåçóëüòàòîì äëÿ ïîñòðîåíèÿ ôîðìû â øèðîêîì ñìûñëå Ï ïðîèçâîëüíîãî èçîáðàæåíèÿ . Ïóñòü - ìèíèìàëüíàÿ -àëãåáðà, îòíîñèòåëüíî êîòîðîé èçìåðèìî , ò.å. ïóñòü , ãäå - ïðîîáðàç áîðåëåâñêîãî ìíîæåñòâà , B - -àëãåáðà áîðåëåâñêèõ ìíîæåñòâ . Çàìåíèì â óñëîâèÿõ, îïðåäåëÿþùèõ èñ÷åðïûâàþùóþ ïîñëåäîâàòåëüíîñòü ðàçáèåíèé, C íà è âûáåðåì ýòó, çàâèñÿùóþ îò , èñ÷åðïûâàþùóþ ïîñëåäîâàòåëüíîñòü ( - èçìåðèìûõ) ðàçáèåíèé â ëåììå (*).

Òåîðåìà (*). Ïóñòü , - èñ÷åðïûâàþùàÿ ïîñëåäîâàòåëüíîñòü ðàçáèåíèé X, ïðè÷åì - ìèíèìàëüíàÿ -àëãåáðà, ñîäåðæàùàÿ âñå è Ï(N) - îðòîãîíàëüíûé ïðîåêòîð , îïðåäåëåííûé ðàâåíñòâîì ,

Òîãäà

1) äëÿ ëþáîãî -èçìåðèìîãî èçîáðàæåíèÿ è ïî÷òè äëÿ âñåõ , ,

2) äëÿ ëþáîãî èçîáðàæåíèÿ ïðè ), ãäå Ï - îðòîãîíàëüíûé ïðîåêòîð íà .

Äîêàçàòåëüñòâî. Ïåðâîå óòâåðæäåíèå íåïîñðåäñòâåííî ñëåäóåò èç ëåììû (*) è îïðåäåëåíèÿ . Äëÿ äîêàçàòåëüñòâà âòîðîãî óòâåðæäåíèÿ çàìåòèì, ÷òî, òàê êàê A(N+1) - ïðîäîëæåíèå ðàçáèåíèÿ A(N), N=1,2,..., òî ïîñëåäîâàòåëüíîñòü ïðîåêòîðîâ Ï(N), N=1,2,..., ìîíîòîííî íåóáûâàåò: è ïîòîìó ñõîäèòñÿ (ïîòî÷å÷íî) ê íåêîòîðîìó îðòîãîíàëüíîìó ïðîåêòîðó Ï. Òàê êàê - ìíîæåñòâî âñåõ -èçìåðèìûõ èçîáðàæåíèé è èõ ïðåäåëîâ (â ), à â ñèëó ëåììû (*) äëÿ ëþáîãî -èçìåðèìîãî èçîáðàæåíèÿ

, òî äëÿ ëþáîãî èçîáðàæåíèÿ è äëÿ ëþáîãî , èáî -èçìåðèìî, N=1,2,... 

Âîïðîñ î òîì, êàêèì îáðàçîì ìîæåò áûòü ïîñòðîåíà èñ÷åðïûâàþùàÿ ïîñëåäîâàòåëüíîñòü ðàçáèåíèé, îáñóæäàåòñÿ â ñëåäóþùåì ïóíêòå.

Çàäàíû âåêòîðû f1,...,fq, òðåáóåòñÿ îïðåäåëèòü ðàçáèåíèå , íà ìíîæåñòâàõ êîòîðîãî íàèëó÷øåå ïðèáëèæåíèå ïðèíèìàåò ñîîòâåòñòâåííî çíà÷åííèÿ f1,...,fq. Ðàññìîòðèì çàäà÷ó ïðèáëèæåíèÿ öâåòíîãî èçîáðàæåíèÿ f, â êîòîðîé çàäàíî íå ðàçáèåíèå ïîëÿ çðåíèÿ X, à âåêòîðû â , è òðåáóåòñÿ ïîñòðîèòü èçìåðèìîå ðàçáèåíèå ïîëÿ çðåíèÿ, òàêîå, ÷òî öâåòíîå èçîáðàæåíèå - íàèëó÷øàÿ â àïïðîêñèìàöèÿ f. Òàê êàê

, (14*)

òî â Ai ñëåäóåò îòíåñòè ëèøü òå òî÷êè , äëÿ êîòîðûõ , =1,2,...,q, èëè, ÷òî òî æå ñàìîå, =1,2,...,q. Òå òî÷êè, êîòîðûå ñîãëàñíî ýòîìó ïðèíöèïó ìîãóò áûòü îòíåñåíû ê íåñêîëüêèì ìíîæåñòâàì, äîëæíû áûòü îòíåñåíû ê îäíîìó èç íèõ ïî ïðîèçâîëó. Ó÷èòûâàÿ ýòî, óñëîâèìñÿ ñ÷èòàòü, ÷òî çàïèñü

, (14)

îçíà÷àåò, ÷òî ìíîæåñòâà (14) íå ïåðåñåêàþòñÿ è .

×òîáû ñôîðìóëèðîâàòü ýòîò ðåçóëüòàò â òåðìèíàõ ìîðôîëîãè÷åñêîãî àíàëèçà, ðàññìîòðèì ðàçáèåíèå , â êîòîðîì

(15)

è çâåçäî÷êà óêàçûâàåò íà äîãîâîðåííîñòü, ïðèíÿòóþ â (14). Îïðåäåëèì îïåðàòîð F, äåéñòâóþùèé èç â ïî ôîðìóëå , , i=1,...,q. Î÷åâèäíî, F âñåãäà ìîæíî ñîãëàñîâàòü ñ (14) òàê, ÷òîáû âêëþ÷åíèÿ è , i=1,...,q, ìîæíî áûëî ñ÷èòàòü ýêâèâàëåíòíûìè. 8

Òåîðåìà 2. Ïóñòü - çàäàííûå âåêòîðû Rn. Ðåøåíèå çàäà÷è

íàèëó÷øåãî â ïðèáëèæåíèÿ èçîáðàæåíèÿ f èçîáðàæåíèÿìè èìååò âèä , ãäå - èíäèêàòîðíàÿ ôóíêöèÿ ìíîæåñòâà . Ìíîæåñòâî îïðåäåëåíî ðàâåíñòâîì (15). Íåëèíåéíûé îïåðàòîð , êàê âñÿêèé îïåðàòîð íàèëó÷øåãî ïðèáëèæåíèÿ óäîâëåòâîðÿåò óñëîâèþ F2=F, ò.å. ÿâëÿåòñÿ ïðåêòîðîì.

Çàìå÷àíèå 2. Åñëè äàííûå çàäà÷è äîñòóïíû ëèøü â ÷åðíî-áåëîì âàðèàíòå, òî åñòü çàäàíû ÷èñëà , i=1,...,q, êîòîðûå ìîæíî ñ÷èòàòü óïîðÿäî÷åííûìè ñîãëàñíî óñëîâèþ , òî, êàê ïîêàçàíî â [3], èñêîìîå ðàçáèåíèå X ñîñòîèò èç ìíîæåñòâ

ãäå , è èìååò ìàëî îáùåãî ñ ðàçáèåíèåì (14).

Çàìå÷àíèå 3. Âûáåðåì âåêòîðû fi, i=1,..,q åäèíè÷íîé äëèíû: , i=1,...,q. Òîãäà

. (16)

Ìíîæåñòâà (16) ÿâëÿþòñÿ êîíóñàìè â Rn , îãðàíè÷åííûìè ãèïåðïëîñêîñòÿìè, ïðîõîäÿùèìè ÷åðåç íà÷àëî êîîðäèíàò. Îòñþäà ñëåäóåò, ÷òî ñîîòâåòñòâóþùåå ïðèáëèæåíèå èçîáðàæåíèÿ f èíâàðèàíòíî îòíîñèòåëüíî ïðîèçâîëüíîãî ïðåîáðàçîâàíèÿ ïîñëåäíåãî, íå èçìåíÿþùåãî åãî öâåò (íàïðèìåð ), â ÷àñòíîñòè, îòíîñèòåëüíî îáðàçîâàíèÿ òåíåé íà f.

Çàìå÷àíèå 4. Äëÿ ëþáîãî çàäàííîãî íàáîðà ïîïàðíî ðàçëè÷íûõ âåêòîðîâ îïåðàòîð F, ïðèâåäåííûé â òåîðåìå 2, îïðåäåëÿåò ôîðìó èçîáðàæåíèÿ, ïðèíèìàþùåãî çíà÷åíèÿ ñîîòâåòñòâåííî íà èçìåðèìûõ ìíîæåñòâàõ (ëþáîãî) ðàçáèåíèÿ X. Âñÿêîå òàêîå èçîáðàæåíèå ÿâëÿåòñÿ íåïîäâèæíîé (â ) òî÷êîé F: , åñëè , âñå îíè èçîìîðôíû ìåæäó ñîáîé. Åñëè íåêîòîðûå ìíîæåñòâà èç - ïóñòûå, èëè íóëåâîé ìåðû, ñîîòâåòñòâóþùèå èçîáðàæåíèÿ èìåþò áîëåå ïðîñòóþ ôîðìó.

Èíà÷å ãîâîðÿ, â äàííîì ñëó÷àå ôîðìîé èçîáðàæåíèÿ ÿâëÿåòñÿ ìíîæåñòâî âñåõ èçîáðàæåíèé, ïðèíèìàþùèõ çàäàííûå çíà÷åíèÿ íà ìíîæåñòâàõ ïîëîæèòåëüíîé ìåðû ëþáîãî ðàçáèåíèÿ X, è èõ ïðåäåëîâ â .

Теоремы 1 и 2 позволяют записать необходимые и достаточные условия наилучшего приближения изображения f() изображениями , в котором требуется определить как векторы , так и множества так, чтобы

.

Следствие 1.

Пусть Di ,i=1,...,N, - подмножества Rn (15), П - ортогональный проектор (13), , где . Тогда необходимые и достаточные условия суть следующие: , где , .

Следующая рекуррентная процедура, полезная для уточнения приближений, получаемых в теоремах 1,2, в некоторых случаях позволяет решать названную задачу. Пусть - èñõîäíûå âåêòîðû â çàäà÷å (14*), - ñîîòâåòñòâóþùåå îïòèìàëüíîå ðàçáèåíèå (14), F(1)- îïåðàòîð íàèëó÷øåãî ïðèáëèæåíèÿ è - íåâÿçêà. Âîñïîëüçîâàâøèñü òåîðåìîé 1, îïðåäåëèì äëÿ íàéäåííîãî ðàçáèåíèÿ îïòèìàëüíûå âåêòîðû . Ñîãëàñíî âûðàæåíèþ (13) , è ñîîòâåòñòâóþùèé îïåðàòîð íàèëó÷øåãî ïðèáëèæåíèÿ Ï(1) (13) îáåñïå÷èò íå ìåíåå òî÷íîå ïðèáëèæåíèå f(), ÷åì F(1): . Âûáåðåì òåïåðü â òåîðåìå 2 , îïðåäåëèì ñîîòâåòñòâóþùåå îïòèìàëüíîå ðàçáèåíèå è ïîñòðîèì îïåðàòîð íàèëó÷øåãî ïðèáëèæåíèÿ F(2). Òîãäà . Íà ñëåäóþùåì øàãå ïî ðàçáèåíèþ ñòðîèì è îïåðàòîð Ï(3) è ò.ä.

 çàêëþ÷åíèå ýòîãî ïóíêòà âåðíåìñÿ ê âîïðîñó î ïîñòðîåíèè èñ÷åðïûâàþùåãî -èçìåðèìîãî ðàçáèåíèÿ X, îòâå÷àþùåãî çàäàííîé ôóíêöèè . Âûáåðåì ïðîèçâîëüíî ïîïàðíî ðàçëè÷íûå âåêòîðû èç f(X) è ïîñòðîèì ïî ôîðìóëå (15) ðàçáèåíèå Rn . Äëÿ êàæäîãî q=1,2,... îáðàçóåì ðàçáèåíèå E(N(q)), ìíîæåñòâà , j=1,...,N(q), êîòîðîãî îáðàçîâàíû âñåìè ïîïàðíî ðàçëè÷íûìè ïåðåñå÷åíèÿìè ìíîæåñòâ èç . Ïîñëåäîâàòåëüíîñòü ñîîòâåòñòâóþùèõ ðàçáèåíèé X , i=1,...,N(q), q=1,2... -èçìåðèìû è ÿâëÿåòñÿ ïðîäîëæåíèåì

5.2. Приближение изображениями, цвет которых постоянен на подмножествах разбиения поля зрения X.

Çàäàíî ðàçáèåíèå , òðåáóåòñÿ îïðåäåëèòü öâåò è ðàñïðåäåëåíèå ÿðêîñòåé íàèëó÷øåãî ïðèáëèæåíèÿ íà êàæäîì Ai,i=1,...,N.

Äëÿ ïðàêòèêè, êàê óæå áûëî îòìå÷åíî, áîëüøîé èíòåðåñ ïðåäñòàâëÿåò êëàññ èçîáðàæåíèé (5), öâåò êîòîðûõ íå èçìåíÿåòñÿ â ïðåäåëàõ íåêîòîðûõ ïîäìíîæåñòâ ïîëÿ çðåíèÿ, è çàäà÷è àïïðîêñèìàöèè ïðîèçâîëüíûõ èçîáðàæåíèé èçîáðàæåíèÿìè òàêîãî êëàññà.

Çàïèøåì èçîáðàæåíèå (5) â âèäå

(17)

ãäå .

Ïóñòü A1,...,AN - çàäàííîå ðàçáèåíèå X, - èíäèêàòîðíàÿ ôóíêöèÿ Ai, i=1,...,N. Ðàññìîòðèì çàäà÷ó íàèëó÷øåãî â ïðèáëèæåíèÿ èçîáðàæåíèÿ èçîáðàæåíèÿìè (17), íå òðåáóÿ, ÷òîáû

(18)

Ðå÷ü èäåò î çàäà÷å àïïðîêñèìàöèè ïðîèçâîëüíîãî èçîáðàæåíèÿ èçîáðàæåíèÿìè, ó êîòîðûõ ÿðêîñòü ìîæåò áûòü ïðîèçâîëüíîé ôóíêöèåé èç , â òî âðåìÿ, êàê öâåò äîëæåí ñîõðàíÿòü ïîñòîÿííîå çíà÷åíèå íà êàæäîì èç çàäàííûõ ïîäìíîæåñòâ A1,...,AN ïîëÿ çðåíèÿ X, (ñì. Ëåììó 3).

Òàê êàê

òî ìèíèìóì S (19) ïî äîñòèãàåòñÿ ïðè

, (20)

è ðàâåí

(21)

Çàäà÷à (18) òåì ñàìûì ñâåäåíà ê çàäà÷å

. (22)

 ñâÿçè ñ ïîñëåäíåé ðàññìîòðèì ñàìîñîïðÿæåííûé íåîòðèöàòåëüíî îïðåäåëåííûé îïåðàòîð

. (23)

Ìàêñèìóì (íåîòðèöàòåëüíîé) êâàäðàòè÷íîé ôîðìû íà ñôåðå â Rn, êàê èçâåñòíî, (ñì.,íàïðèìåð, [11]) äîñòèãàåòñÿ íà ñîáñòâåííîì âåêòîðå yi îïåðàòîðà Ôi, îòâå÷àþùåì ìàêñèìàëüíîìó ñîáñòâåííîìó çíà÷åíèþ >0,

,

è ðàâåí , ò.å. . Ñëåäîâàòåëüíî, ìàêñèìóì â (22) ðàâåí è äîñòèãàåòñÿ, íàïðèìåð, ïðè

Òåîðåìà 3. Ïóñòü A1,...,AN -çàäàííîå èçìåðèìîå ðàçáèåíèå X, ïðè÷åì9 (Ai)>0, i=1,...,N. Ðåøåíèåì çàäà÷è (18) íàèëó÷øåãî ïðèáëèæåíèÿ èçîáðàæåíèÿ èçîáðàæåíèÿìè g() (17) ÿâëÿåòñÿ èçîáðàæåíèå

(24)

Îïåðàòîðû ,i=1,...,N, è - íåëèíåéíûå (çàâèñÿùèå îò f() ) ïðîåêòîðû: Ïi ïðîåöèðóåò â Rn âåêòîðû íà ëèíåéíîå ïîäïðîñòðàíñòâî , íàòÿíóòîå íà ñîáñòâåííûé âåêòîð îïåðàòîðà Ôi (23), îòâå÷àþùèé íàèáîëüøåìó ñîáñòâåííîìó çíà÷åíèþ i,

; (25)

Ï ïðîåöèðóåò â èçîáðàæåíèå íà ìèíèìàëüíîå ëèíåéíîå ïîäïðîñòðàíñòâî , ñîäåðæàùåå âñå èçîáðàæåíèÿ

Íåâÿçêà íàèëó÷øåãî ïðèáëèæåíèÿ

(19*).

Äîêàçàòåëüñòâî. Ðàâåíòñòâî (24) è âûðàæåíèå äëÿ Ïi ñëåäóåò èç (17),(20) è ðåøåíèÿ çàäà÷è íà ñîáñòâåííûå çíà÷åíèÿ äëÿ îïåðàòîðà Ôi (23). Ïîñêîëüêó Ôi ñàìîñîïðÿæåííûé íåîòðèöàòåëüíî îïðåäåëåííûé îïåðàòîð, òî çàäà÷à íà ñîáñòâåííûå çíà÷åíèÿ (23) ðàçðåøèìà, âñå ñîáñòâåííûå çíà÷åíèÿ Ôi íåîòðèöàòåëüíû è ñðåäè íèõ i - наибольшее.

Для доказательства свойств операторов Ïi, i=1,...,N, è Ï ââåäåì îáîçíà÷åíèÿ, óêàçûâàþùèå íà çàâèñèìîñòü îò f():

(26*)

Ýòè ðàâåíñòâà, ïîêàçûâàþùèå, ÷òî ðåçóëüòàò äâóêðàòíîãî äåéñòâèÿ îïåðàòîðîâ Ïi, i=1,...,N, è Ï (26) íå îòëè÷àåòñÿ îò ðåçóëüòàòàòà îäíîêðàòíîãî èõ äåéñòâèÿ, ïîçâîëÿò ñ÷èòàòü îïåðàòîðû (26) ïðîåêòîðàìè.

Ïóñòü fi - cñîáñòâåííûé âåêòîð Ôi , îòâå÷àþùèé ìàêñèìàëüíîìó ñîáñòâåííîìó çíà÷åíèþ i. Чтобы определить ñëåäóåò ðåøèòü çàäà÷ó íà ñîáñòâåííûå çíà÷åíèÿ äëÿ îïåðàòîðà :

.

Ïîñêîëüêó rank =1, èìååò åäèíñòâåííîå ïîëîæèòåëüíîå ñîáñòâåííîå çíà÷åíèå, êîòîðîå, êàê íåòðóäíî ïðîâåðèòü, ðàâíî i, è åìó ñîîòâåòñòâóåò åäèíñòâåííûé ñîáñòâåííûé âåêòîð fi. Ïîýòîìó

.

Îòñþäà, â ñâîþ î÷åðåäü, ñëåäóåò ðàâåíñòâî (26*) äëÿ

Ëåììà 4. Äëÿ ëþáîãî èçîáðàæåíèÿ ðåøåíèå (24) çàäà÷è (18) íàèëó÷øåãî ïðèáëèæåíèÿ åäèíñòâåííî è ÿâëÿåòñÿ ýëåìåíòîì .

Äîêàçàòåëüñòâî. Äîñòàòî÷íî äîêàçàòü, ÷òî åäèíñòâåííûé (ñ òî÷íîñòüþ äî ïîëîæèòåëüíîãî ìíîæèòåëÿ) ñîáñòâåííûé âåêòîð fi îïåðàòîðà (23), îòâå÷àþùèé ìàêñèìàëüíîìó ñîáñòâåííîìó çíà÷åíèþ i, можно выбрать так, чтобы , ïîñêîëüêó â òàêîì ñëó÷àå áóäóò âûïîëíåíû èìïëèêàöèè:

,

ñîñòàâëÿþùèå ñîäåðæàíèå ëåììû. Äåéñòâèòåëüíî, åñëè òî ñîãëàñíî (23) , ïîñêîëüêó âêëþ÷åíèå îçíà÷àåò, ÷òî ; îòñþäà è èç (25) ïîëó÷èì, ÷òî ,i=1,...,N, à ïîýòîìó è â (24) .

Óáåäèìñÿ â íåîòðèöàòåëüíîñòè .  îðòîíîðìèðîâàííîì áàçèñå e1,...,en, â êîòîðîì , âûõîäíîé ñèãíàë i-ãî äåòåêòîðà â òî÷êå (ñì. çàìå÷àíèå 1) çàäà÷à íà ñîáñòâåííûå çíà÷åíèÿ (23*) èìååò âèä , p=1,...,n,

ãäå , .

Òàê êàê ìàòðèöà ñèììåòðè÷åñêàÿ è íåîòðèöàòåëüíî îïðåäåëåííàÿ ( ) îíà èìååò n íåîòðèöàòåëüíûõ ñîáñòâåííûõ çíà÷åíèé , êîòîðûì ñîîòâåòñòâóþò n îðòîíîðìèðîâàííûõ ñîáñòâåííûõ âåêòîðîâ , à ïîñêîëüêó ìàòðè÷íûå ýëåìåíòû , òî ñîãëàñíî òåîðåìå Ôðîáåíóñà-Ïåððîíà ìàêñèìàëüíîå ñîáñòâåííîå çíà÷åíèå - àëãåáðàè÷åñêè ïðîñòîå (íåêðàòíîå), à ñîîòâåòñòâóþùèé ñîáñòâåííûé âåêòîð ìîæíî âûáèðàòü íåîòðèöàòåëüíûì:

. Ñëåäîâàòåëüíî, âåêòîð fi îïðåäåëåí ñ òî÷íîñòüþ äî ïîëîæèòåëüíîãî ìíîæèòåëÿ , . 

Çàìå÷àíèå 4.

Åñëè , ò.å. åñëè àïïðîêñèìèðóåìîå èçîáðàæåíèå íà ìíîæåñòâàõ òîãî æå ðàçáèåíèÿ èìååò ïîñòîÿííûé öâåò, òî â òåîðåìå 3 , .

Наоборот, если , то

, т.е. определяется выражением (17), в котором .

Итак, пусть в изображении g() (17) все векторы f1,.…..,fN попарно не коллинеарны, тюею цвета всех подмножеств A1,...,AN попарно различны. Тогда форма в широком смысле изображения (17) есть множество решений уравнения

, , (27)

где , fi - собственный вектор оператора Фi: , отвечающий максимальному собственному значению i, i=1,...,N . В данном случае , если и только если выполнено равенство (27).

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

Çàäàíû âåêòîðû öâåòà 1,..., q, òðåáóåòñÿ îïðåäåëèòü ðàçáèåíèå A1,..., Aq, íà ìíîæåñòâàõ êîòîðîãî íàèëó÷øåå ïðèáëèæåíèå èìååò ñîîòâåòñòâåííî öâåòà 1,..., q è îïòèìàëüíûå ðàñïðåäåëåíèÿ ÿðêîñòåé 10.

Речь идет о следующей задаче наилучшего в ïðèáëèæåíèÿ èçîáðàæåíèÿ

. (28)

Ðàññìîòðèì âíà÷àëå çàäà÷ó (28) íå òðåáóÿ, ÷òîáû . Òàê êàê äëÿ ëþáîãî èçìåðèìîãî

, (29)

è äîñòèãàåòñÿ íà

, (30)

òî, êàê íåòðóäíî óáåäèòüñÿ,

, (31)

ãäå çâåçäî÷êà * îçíà÷àåò òî æå ñàìîå, ÷òî è â ðàâåíñòâå (14): òî÷êè xX, â êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî ìîãóò áûòü ïðîèçâîëüíî îòíåñåíû ê îäíîìó èç ìíîæåñòâ Ai èëè Aj.

Ïóñòü - ðàçáèåíèå , â êîòîðîì

(32)

à F: Rn Rn îïåðàòîð, îïðåäåëåííûé óñëîâèåì

(33)

Òîãäà ðåøåíèå çàäà÷è (28) ìîæíî ïðåäñòàâèòü â âèäå

, (34)

ãäå - èíäèêàòîðíàÿ ôóíêöèÿ ìíîæåñòâà Ai (31), i=1,...,q è F -îïåðàòîð, äåéñòâóþùèé â ïî ôîðìóëå (34) (ñì. ñíîñêó 4 íà ñòð. 13).

Íåòðóäíî óáåäèòüñÿ, ÷òî çàäà÷à íà ìèíèìóì (29) ñ óñëîâèåì ôèçè÷íîñòè

(35)

èìååò ðåøåíèå

(36)

Ñîîòâåòñòâåííî ðåøåíèå çàäà÷è (28) ñ óñëîâèåì ôèçè÷íîñòè èìååò âèä

, (37)

ãäå - èíäèêàòîðíàÿ ôóíêöèÿ ìíîæåñòâà

, (38)

 ðÿäå ñëó÷àåâ äëÿ ïîñòðîåíèÿ (34) ïîëåçíî îïðåäåëèòü îïåðàòîð F+: Rn Rn, äåéñòâóþùèé ñîãëàñíî ôîðìóëå

(39)

ãäå

, òàê ÷òî ,i=1,...q. (40)

Ïîäûòîæèì ñêàçàííîå.

Òåîðåìà 4. Ðåøåíèå çàäà÷è (28) íàèëó÷øåãî â ïðèáëèæåíèÿ èçîáðàæåíèÿ èçîáðàæåíèÿìè íà èñêîìûõ ìíîæåñòâàõ A1,...,Aq ðàçáèåíèÿ X çàäàííûå öâåòàìè 1,..., q ñîîòâåòñòâåííî, äàåòñÿ ðàâåíñòâîì (34), èñêîìîå ðàçáèåíèå A1,...,Aq îïðåäåëåíî â (31). Òðåáîâàíèå ôèçè÷íîñòè íàèëó÷øåãî ïðèáëèæåíèÿ ïðèâîäèò ê ðåøåíèþ (37) è îïðåäåëÿåò èñêîìîå ðàçáèåíèå ôîðìóëàìè (38). Ðåøåíèå (34) èíâàðèàíòíî îòíîñèòåëüíî ëþáîãî, à (37) - îòíîñèòåëüíî ëþáîãî, ñîõðàíÿþùåãî ôèçè÷íîñòü, ïðåîáðàçîâàíèÿ, íåèçìåíÿþùåãî åãî öâåò.

Ôîðìîé â øèðîêîì ñìûñëå èçîáðàæåíèÿ, èìåþùåãî çàäàííûé íàáîð öâåòîâ 1,..., q íà íåêîòîðûõ ìíîæåñòâàõ ïîëîæèòåëüíîé ìåðû A1,...,Aq ðàçáèåíèå ïîëÿ çðåíèÿ ìîæíî íàçâàòü îïåðàòîð (34), ôîðìîé òàêîãî èçîáðàæåíèÿ ÿâëÿåòñÿ îïåðàòîð F+ (37). Âñÿêîå òàêîå èçîáðàæåíèå g(), óäîâëåòâîðÿþùåå óñëîâèÿì ôèçè÷íîñòè (íåîòðèöàòåëüíîñòè ÿðêîñòåé), óäîâëåòâîðÿåò óðàâíåíèþ F+g()=g(), òå èç íèõ, ó êîòîðûõ (Ai)>0, i=1,...,q, èçîìîðôíû, îñòàëüíûå èìåþò áîëåå ïðîñòóþ ôîðìó.

 çàêëþ÷åíèå ýòîãî ðàçäåëà âåðíåìñÿ ê ïîíÿòèþ ôîðìû èçîáðàæåíèÿ, çàäàííîãî ñ òî÷íîñòüþ äî ïðîèçâîëüíîãî, óäîâëåòâîðÿþùåãî óñëîâèÿì ôèçè÷íîñòè, ïðåîáðàçîâàíèÿ ÿðêîñòè. Ðå÷ü èäåò î ôîðìå èçîáðàæåíèÿ , çàäàííîãî ðàñïðåäåëåíèåì öâåòà , ïðè ïðîèçâîëüíîì (ôèçè÷íîì) ðàñïðåäåëåíèè ÿðêîñòè, íàïðèìåð, . Äëÿ îïðåäåëåíèÿ ôîðìû ðàññìîòðèì çàäà÷ó íàèëó÷øåãî â ïðèáëèæåíèÿ èçîáðàæåíèÿ òàêèìè èçîáðàæåíèÿìè

, (41)

Òåîðåìà 5. Ðåøåíèå çàäà÷è (41) äàåòñÿ ðàâåíñòâîì

, (42)

â êîòîðîì , ãäå . Íåâÿçêà ïðèáëèæåíèÿ

, (43)

( !) 

Îïðåäåëåíèå. Ôîðìîé èçîáðàæåíèÿ, çàäàííîãî ðàñïðåäåëåíèåì öâåòà , íàçîâåì âûïóêëûé, çàìêíóòûé êîíóñ èçîáðàæåíèé

èëè - ïðîåêòîð íà .

Âñÿêîå èçîáðàæåíèå g(), ðàñïðåäåëåíèå öâåòà êîòîðîãî åñòü () è òîëüêî òàêîå èçîáðàæåíèå ñîäåðæèòñÿ â è ÿâëÿåòñÿ íåïîäâèæíîé òî÷êîé îïåðàòîðà

: g() = g(). (#)

Ïîñêîëüêó íà ñàìîì äåëå äåòàëè ñöåíû, ïåðåäàâàåìûå ðàñïðåäåëåíèåì öâåòà (), íå ïðåäñòàâëåíû íà èçîáðàæåíèè f() = f()() â òîé îáëàñòè ïîëÿ çðåíèÿ, â êîòîðîé ÿðêîñòü f(x)=0, xX, áóäåì ñ÷èòàòü, ÷òî - ôîðìà ëþáîãî èçîáðàæåíèÿ f(x) = f(x)(x), f(x)>0, xX(mod), âñå òàêèå èçîáðàæåíèÿ èçîìîðôíû, à ôîðìà âñÿêîãî èçîáðàæåíèÿ g(), óäîâëåòâîðÿþùåãî óðàâíåíèþ (#), íå ñëîæíåå, ÷åì ôîðìà f().

Çàìå÷àíèå 5. Ïóñòü 1,..., N - èñõîäíûé íàáîð öâåòîâ, , A1,...,AN - ñîîòâåòñòâóþùåå îïòèìàëüíîå ðàçáèåíèå X, íàéäåííîå â òåîðåèå 4 è

, (34*)

- íàèëó÷øåå ïðèáëèæåíèå f(). Òîãäà â ðàâåíñòâå (24)

, (24*)

åñëè A1,...,AN - èñõîäíîå ðàçáèåíèå X â òåîðåìå 3. Íàîáîðîò, åñëè A1,...,AN - çàäàííîå â òåîðåìå 3 ðàçáèåíèå X è f1,...,fN - ñîáñòâåííûå âåêòîðû îïåðàòîðîâ Ô1,...,ÔN (23) ñîîòâåòñòâåííî, îòâå÷àþùèå ìàêñèìàëüíûì ñîáñòâåííûì çíà÷åíèÿì, òî f1,...,fN è áóäåò âûïîëíåíî ðàâåíñòâî (24), åñëè â (34*) îïðåäåëèòü i êàê öâåò fi â (24), i=1,...,N.

Ïðîâåðêà ýòîãî çàìå÷àíèÿ íå ïðåäñòàâëÿåò çàòðóäíåíèé.

В. Случай, когда допускаются небольшие изменения цвета в пределах каждого Ai, i=1,...,N.

Ðàçóìååòñÿ, óñëîâèå ïîñòîÿíñòâà öâåòà íà ìíîæåñòâàõ Ai, i=1,...,N, íà ïðàêòèêå ìîæåò âûïîëíÿòüñÿ ëèøü ñ îïðåäåëåííîé òî÷íîñòüþ. Ïîñëåäíþþ ìîæíî ïîâûñèòü êàê ïóòåì ïåðåõîäà ê áîëåå ìåëêîìó ðàçáèåíèþ , òàê è äîïóñтив íåêîòîðûå èçìåíåíèÿ öâåòà â ïðåäåëàõ êàæäîãî Ai, i=1,...,N, íàïðèìåð, âûáðàâ âìåñòî (17) êëàññ èçîáðàæåíèé

(17*)

â êîòîðîì â (3).

Ïîñêîëüêó â çàäà÷å íàèëó÷øåãî ïðèáëèæåíèÿ f() èçîáðàæåíèÿìè ýòîãî êëàññà ïðåäñòîèò íàéòè , âåêòîðû ïðè ëþáîì i=1,...,N, ìîæíî ñ÷èòàòü îðòîãîíàëüíûìè, îïðåäåëèâ

, (*)

èç óñëîâèÿ ìèíèìóìà íåâÿçêè ïî . Ïîñëå ýòîãî äëÿ êàæäîãî i=1,...,N âåêòîðû äîëæíû áûòü îïðåäåëåíû èç óñëîâèÿ

(**)

ïðè äîïîëíèòåëüíîì óñëîâèè îðòîãîíàëüíîñòè

. Ðåøåíèå ýòîé çàäà÷è äàåòñÿ â ñëåäóþùåé ëåììå

Ëåììà 5. Ïóñòü îðòîãîíàëüíûå ñîáñòâåííûå âåêòîðû îïåðàòîðà Ôi (23), óïîðÿäî÷åííûå ïî óáûâàíèþ ñîáñòâåííûõ çíà÷åíèé:

.

Òîãäà ðåøåíèå çàäà÷è (**) äàåòñÿ ðàâåíñòâàìè .

Äîêàçàòåëüñòâî. Çàìåòèì, ÷òî, ïîñêîëüêó Ôi - ñàìîñîïðÿæåííûé íåîòðèöàòåëüíî îïðåäåëåííûé îïåðàòîð, åãî ñîáñòâåííûå çíà÷åíèÿ íåîòðèöàòåëüíû, à åãî ñîáñòâåííûå âåêòîðû âñåãäà ìîæíî âûáðàòü òàê, ÷òîáû îíè îáðàçîâàëè îðòîãîíàëüíûé áàçèñ â Rn. Ïóñòü Pi - îðòîãîíàëüíî ïðîåöèðóåò â Rn íà ëèíåéíóþ îáîëî÷êó ñîáñòâåííûõ âåêòîðîâ è

[Pi Ôi Pi] - ñóæåíèå îïåðàòîðà Pi Ôi Pi íà . Òîãäà ëåâàÿ ÷àñòü (*) ðàâíà ñëåäó оператора [Pi Ôi Pi]

, ãäå - j-îå ñîáñòâåííîå çíà÷åíèå îïåðàòîðà (ñì., íàïðèìåð, [10]). Ïóñòü . Òîãäà ñîãëàñíî òåîðåìå Ïóàíêàðå, [10], , îòêóäà ñëåäóåò óòâåðæäàåìîå â ëåììå. ■

Âîñïîëüçîâàâøèñü âûðàæåíèÿìè (*) è ëåììîé 5, íàéäåì, ÷òî â ðàññìàòðèâàåìîì ñëó÷àå èìååò ìåñòî óòâåðæäåíèå, àíàëîãè÷íîå òåîðåìå 3.

Òåîðåìà 3*. Íàèëó÷øåå ïðèáëèæåíèå ëþáîãî èçîáðàæåíèÿ f() èçîáðàæåíèÿìè (17*) èìååò âèä

,

Ãäå : îðòîãîíàëüíûé ïðîåêòîð íà ëèíåéíóþ îáîëî÷êó , ñîáñòâåííûõ âåêòîðîâ çàäà÷è

.

Íåâÿçêà íàèëó÷øåãî ïðèáëèæåíèÿ ðàâíà

.

Ðàññìîòðèì òåïåðü çàäà÷ó íàèëó÷øåãî ïðèáëèæåíèÿ èçîáðàæåíèÿ f èçîáðàæåíèÿìè (17), â êîòîðûõ çàäàíû è ôèêñèðîâàíû âåêòîðû , è íàäëåæèò îïðåäåëèòü èçìåðèìîå ðàçáèåíèå è ôóíêöèè , êàê ðåøåíèå çàäà÷è

(30)

Ïðè ëþáîì ðàçáèåíèè ìèíèìóì â (30) ïî äîñòèãàåòñÿ ïðè , îïðåäåëÿåìûõ ðàâåíñòâîì (20).  ñâîþ î÷åðåäü, î÷åâèäíî, ÷òî

(31)

ãäå òî÷êè , â êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî ìîãóò áûòü ïðîèçâîëüíî âêëþ÷åíû â îäíî èç ìíîæåñòâ : ëèáî â , ëèáî â . Ýòî ñîãëàøåíèå îòìå÷åíî çâåçäî÷êîé â (31).

Òàêèì îáðàçîì äîêàçàíà

Òåîðåìà 6. Ïóñòü çàäàííûå âåêòîðû Rn. Ðåøåíèåì çàäà÷è (30) ÿâëÿåòñÿ èçîáðàæåíèå

,

ãäå îðòîãîíàëüíûé ïðîåêòîð îïðåäåëåí ðàâåíñòâîì (25), à - èíäèêàòîðíàÿ ôóíêöèÿ ìíîæåñòâà (31), i=1,...,N. Íåâÿçêà íàèëó÷øåãî ïðèáëèæåíèÿ ðàâíà

. 

Çàìå÷àíèå 5. Òàê êàê ïðè

,

òî óñëîâèÿ (31), îïðåäåëÿþùèå ðàçáèåíèå , ìîæíî çàïèñàòü â âèäå

, (32)

ïîêàçûâàþùåì, ÷òî ìíîæåñòâî â (32) èíâàðèàíòíî îòíîñèòåëüíî ëþáîãî ïðåîáðàçîâàíèÿ èçîáðàæåíèÿ , íå èçìåíÿþùåãî åãî öâåò.

Теоремы 3 и 6 позволяют сформулировать необходимые и достаточные условия наилучшего приближения изображения f() изображениями (17), при котором должны быть найдены и i0 , i=1,...,N, такие, что

.

Теорема 7. Для заданного изображения f() определим множества равенствами (32), оператор П - равенством (24), - равенствами (25). Тогда ,

определено равенством (32), в котором - собственный вектор оператора Фi (23), отвечающий наибольшему собственному значению, причем в (23) , наконец, будет дано равенством (20), в котором , где - собственный вектор оператора , отвечающий наибольшему собственному значению ; наконец,

.

Замечание 6. Следующая итерационная процедура полезна при отыскании : Для изображения f() зададим и по теореме 5 найдем и , затем по теореме 3, используя найдем и . После этого вновь воспользуемся теоремой 3 и по найдем и и т.д. Построенная таким образом последовательность изображений очевидно обладает тем свойством, что числовая последовательность , k=1,2,.….. монотонно не возрастает и, следовательно, сходится. К сожалению ничего определенного нельзя сказать о сходимости последовательности .

Формы (10) и (9) удобно задавать операторами Пf и П*f соответственно.

Теорема 7. Форма в широком смысле изображения определяется ортогональным проектором П*f :

,

при этом и .

Доказательство. Так как для , то получаем первое утверждение. Для доказательства второго утверждения рассмотрим выпуклую задачу на минимум , решение которой определяется условиями (см., например, [11]) . Отсюда следует, что и тем самым доказано и второе утверждение

Замечание. Так как , где fi(x) - выходной сигнал i-го детектора в точке , причем fi(x)0 ,i=1,...,n, и, следовательно цвет реальных изображений непременно имеет неотрицательные , то для реальных изображений , условия и , эквивалентны. Если же для некоторого , то условие не влечет . Заметим также, что для изображений g(), удовлетворяющих условию , всегда .

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

(40)

В котором

. Если ИК составляющей солнечного излучения можно пренебречь по сравнению с собственным излучением объектов, то представляет интерес задача приближения изображениями f() , в которых f1() - любая неотрицательная функция из , 1() - фиксированное векторное поле цвета, f2() - термояркость, 2() - термоцвет в точке . Форма П*f видимой компоненты f() (40) определяется как оператор наилучшего приближения в задаче

, в данном случае

, причем П*f действует фактически только на "видимую компоненту" g(), обращая "невидимую, ИК, компоненту" g() в ноль.

Форма ИК компоненты f() может быть определена лишь тогда, когда известно множество возможных преобразований 2() f2().

Некоторые применения.

Задачи идентификации сцен.

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

1). Задачи идентификации при произвольно меняющейся интенсивности освещения.

Можно ли считать f() è g() изображениями одной и той же сцены, возможно, отличающимя лишь распределениями яркости, например, наличием теней?

 ïðîñòåéøåì ñëó÷àå äëÿ èäåíòèôèêàöèè äîñòàòî÷íî âîñïîëüçîâàòüñÿ òåîðåìîé 5, à èìåííî, f() è g() ìîæíî ñ÷èòàòü èçîáðàæåíèÿìè îäíîé è òîé æå ñöåíû, åñëè ñóùåñòâóåò ðàñïðåäåëåíèå öâåòà , äëÿ êîòîðîãî v(()) ñîäåðæèò f() è g(). Åñëè , è , òî, î÷åâèäíî, ñóùåñòâóåò , ïðè êîòîðîì f(x)v(()), g(x)v(()), à èìåííî, , , åñëè , , åñëè , è, íàêîíåö, - ïðîèçâîëüíî, åñëè .

Íà ïðàêòèêå óäîáíåå èñïîëüçîâàòü äðóãîé ïîäõîä, ïîçâîëÿþùèé îäíîâðåìåííî ðåøàòü çàäà÷è ñîâìåùåíèÿ èçîáðàæåíèé è âûäåëåíèÿ îáúåêòîâ. Ìîæíî ëè, íàïðèìåð, ñ÷èòàòü g() èçîáðàæåíèåì ñöåíû, ïðåäñòàâëåííîé èçîáðàæåíèåì f()? Îòâåò ñëåäóåò ñ÷èòàòü óòâåðäèòåëüíûì, åñëè

.

Çäåñü () - ðàñïðåäåëåíèå öâåòà íà èçîáðàæåíèè f(), ñèìâîë ~0 îçíà÷àåò, ÷òî çíà÷åíèå (g()) ìîæíî îáúÿñíèòü íàëè÷èåì øóìà, êàêèõ-ëèáî äðóãèõ ïîãðåøíîñòåé, èëè, íàêîíåö, - íàëè÷èåì èëè, íàîáîðîò, îòñóòñòâèåì îáúåêòîâ îáúÿñíÿþùèì íåñîâïàäåíèå g() è f() ñ òî÷íîñòüþ äî ïðåîáðàçîâàíèÿ ðàñïðåäåëåíèÿ ÿðêîñòåé. Òàêèå îáúåêòû, èçìåíèâøèå ðàñïðåäåëåíèå öâåòà g() ïî ñðàâíåíèþ ñ ðàñïðåäåëåíèåì öâåòà f(), ïðåäñòàâëåíû â .

2).Èäåíòèôèêàöèÿ ïðè ïðîèçâîëüíîì èçìåíåíèè ðàñïðåäåëåíèÿ èíòåíñèâíîñòè è ïðîñòðàíñòâåííî îäíîðîäíîì èçìåíåíèè ñïåêòðàëüíîãî ñîñòàâà îñâåùåíèÿ.

Ìîæíî ëè ñ÷èòàòü èçîáðàæåíèåì ñöåíû, ïðåäñòàâëåííîé íà èçîáðàæåíèè f(), èçîáðàæåíèå, ïîëó÷åííîå ïðè èçìåíèâøèõñÿ óñëîâèÿõ ðåãèñòðàöèè, íàïðèìåð, ïåðåìåùåíèåì èëè èçìåíåíèåì òåíåé è èçìåíåíèåì ñïåêòðàëüíîãî ñîñòàâà îñâåùåíèÿ?

Ïóñòü Ï - ôîðìà â øèðîêîì ñìûñëå èçîáðàæåíèÿ f(), îïðåäåëåííàÿ â òåîðåìå @, Ï* - ôîðìà f(). Òîãäà îòâåò íà ïîñòàâëåííûé âîïðîñ ìîæíî ñ÷èòàòü óòâåðäèòåëüíûì, åñëè . Åñëè èçìåíåíèå g() îáóñëîâëåíî íå òîëüêî èçìåíèâøèìèñÿ óñëîâèÿìè ðåãèñòðàöèè, íî òàêæå ïîÿâëåíèåì è (èëè) èñ÷åçíîâåíèåì íåêîòîðûõ îáúåêòîâ, òî èçìåíåíèÿ, îáóñëîâëåííûå ýòèì ïîñëåäíèì îáñòîÿòåëüñòâîì áóäóò ïðåäñòàâëåíû íà .

3). Çàäà÷è ñîâìåùåíèÿ èçîáðàæåíèé è ïîèñêà ôðàãìåíòà.

Ïóñòü f() - çàäàííîå èçîáðàæåíèå, AX - ïîäìíîæåñòâî ïîëÿ çðåíèÿ, A() - åãî èíäèêàòîð, A()f() -íàçîâåì ôðàãìåíòîì èçîáðàæåíèÿ f() íà ïîäìíîæåñòâå A, ïðåäñòàâëÿþùåì âûäåëåííûé ôðàãìåíò ñöåíû, èçîáðàæåííîé íà f(). Ïóñòü g() - èçîáðàæåíèå òîé æå ñöåíû, ïîëó÷åííîå ïðè äðóãèõ óñëîâèÿõ, â ÷àñòíîñòè, íàïðèìåð, ñäâèíóòîå, ïîâåðíóòîå, ò.å. ãåîìåòðè÷åñêè èñêàæåííîå ïî ñðàâíåíèþ ñ f(). Çàäà÷à ñîñòîèò â òîì, ÷òîáû óêàçàòü íà g() ôðàãìåíò èçîáðàæåíèÿ, ïðåäñòàâëÿþùèé íà f() ôðàãìåíò ñöåíû è ñîâìåñòèòü åãî ñ A()f().

Îãðàíè÷èìñÿ ñëó÷àåì, êîãäà óïîìÿíóòûå ãåîìåòðè÷åñêèå èñêàæåíèÿ ìîæíî ìîäåëèðîâàòü ãðóïïîé ïðåîáðàçîâàíèé R2->R2, ïðåîáðàçîâàíèå èçîáðàæåíèÿ íàçîâåì ñäâèãîì g() íà h. Çäåñü

Q(h): Rn->Rn, hH, - ãðóïïà îïåðàòîðîâ. Âåêòîðíûé ñäâèã íà hH äàñò

.

 çàäà÷å âûäåëåíèÿ è ñîâìåùåíèÿ ôðàãìåíòà ðàññìîòðèì ôðàãìåíò ñäâèíóòîãî íà h èçîáðàæåíèÿ g() â “îêíå” A:

(100)

ïðè÷åì, ïîñêîëüêó ãäå òî â (100) - îãðàíè÷åíèå íà ñäâèã “îêíà” À, êîòîðîå äîëæíî îñòàâàòüñÿ â ïðåäåëàõ ïîëÿ çðåíèÿ X.

Åñëè êðîìå öâåòà g() ìîæåò îòëè÷àòüñÿ îò f(), ñêàæåì, ïðîèçâîëüíûì ïðåîáðàçîâàíèåì ðàñïðåäåëåíèÿ ÿðêîñòè ïðè íåèçìåííîì ðàñïðåäåëåíèè öâåòà è - ôîðìà ôðàãìåíòà f(), òî çàäà÷à âûäåëåíèÿ è ñîâìåùåíèÿ ôðàãìåíòà ñâîäèòñÿ ê ñëåäóþùåé çàäà÷å íà ìèíèìóì

.(101)

Ïðè ýòîì ñ÷èòàåòñÿ, ÷òî ôðàãìåíò èçîáðàæåíèÿ g(), ñîîòâåòñòâóþùèé ôðàãìåíòó A()f(), áóäåò ïîìåùåí â “îêíî”.À ïóòåì ñîîòâåòñòâóþùåãî ñäâèãà h=h*, ñîâïàäàåò ñ A()f() ñ òî÷íîñòüþ äî íåêîòîðîãî ïðåîáðàçîâàíèÿ ðàñïðåäåëåíèÿ ÿðêîñòè íà íåì. Ýòî îçíà÷àåò, ÷òî

.

ò.å. â (101) ïðè h=h* äîñòèãàåòñÿ ìèíèìóì.

4).  ðÿäå ñëó÷àåâ âîçíèêàåò ñëåäóþùàÿ çàäà÷à àíàëèçà ñïåêòðîçîíàëüíûõ èçîáðàæåíèé: âûäåëèòü îáúåêòû êîòîðûå “âèäíû”, ñêàæåì, â ïåðâîì êàíàëå è “íå âèäíû” â îñòàëüíûõ.

Ðàññìîòðèì äâà èçîáðàæåíèÿ è . Îïðåäåëèì ôîðìó â øèðîêîì ñìûñëå êàê ìíîæåñòâî âñåõ ëèíåéíûõ ïðåîáðàçîâàíèé : (A - ëèíåéíûé îïåðàòîð R2->R2, íå çàâèñÿùèé îò xX). Äëÿ îïðåäåëåíèÿ ïðîåêòîðà íà ðàññìîòðèì çàäà÷ó íà ìèíèìóì

. [*]

Ïóñòü , , òîãäà çàäà÷à íà ìèíèìóì [*] ýêâèâàëåíòíà ñëåäóþùåé: tr A*AS - 2trAB ~ . Åå ðåøåíèå (çíàêîì - îáîçíà÷åíî ïñåâäîîáðàùåíèå).

=

=

Ðèñ.1.

fe - âåêòîð âûõîäíûõ ñèãíàëîâ äåòåêòîðîâ, îòâå÷àþùèé èçëó÷åíèþ e(), e - åãî öâåò; 1,2,3, - âåêòîðû (öâåòà) áàçîâûõ èçëó÷åíèé, - áåëûé öâåò, êîíåö âåêòîðà íàõîäèòñÿ íà ïåðåñå÷åíèè áèññåêòðèñ.

Ëèòåðàòóðà.

[1] Ïûòüåâ Þ.Ï. Ìîðôîëîãè÷åñêèå ïîíÿòèÿ â çàäà÷àõ àíàëèçà èçîáðàæåíèé, - Äîêë. ÀÍ ÑÑÑÐ, 1975, ò. 224, ¹6, ññ. 1283-1286.

[2] Ïûòüåâ Þ.Ï. Ìîðôîëîãè÷åñêèé àíàëèç èçîáðàæåíèé, - Äîêë. ÀÍ ÑÑÑÐ, 1983, ò. 296, ¹5, ññ. 1061-1064.

[3] Ïûòüåâ Þ.Ï. Çàäà÷è ìîðôîëîãè÷åñêîãî àíàëèçà èçîáðàæåíèé, - Ìàòåìàòè÷åñêèå ìåòîäû èññëåäîâàíèÿ ïðèðîäíûõ ðåñóðñîâ çåìëè èç êîñìîñà, ðåä. Çîëîòóõèí Â.Ã., Íàóêà, Ìîñêâà, 1984, ññ. õõõõ-õõõõõ.

[4] Ïûòüåâ Þ.Ï., ×óëè÷êîâ À.È. ÝÂÌ àíàëèçèðóåò ôîðìó èçîáðàæåíèÿ, - Çíàíèå,ñåð. Ìàòåìàòèêà, Êèáåðíåíòèêà, Ìîñêâà, 1988, 47 ñòð.

[5] Yu.P.Pyt’ev. Morphological Image Analysis, Patt. Recogn. and Image Analysis, 1993, v.3, #1, pp.19-28.

[6] Àíòîíþê Â.À., Ïûòüåâ Þ.Ï. Ñïåöïðîöåññîðû ðåàëüíîãî âðåìåíè äëÿ ìîðôîëîãè÷åñêîãî àíàëèçà ðåàëüíûõ ñöåí. Îáðàáîòêà èçîáðàæåíèé è äèñòàíöèîííîå èññëåäîâàíèÿ, -Íîâîñèáèðñê, 1981, ññ. 87-89.

[7] Àíòîíþê Â.À., Ïûòüåâ Þ.Ï., Ðàó Ý.È. Àâòîìàòèçàöèÿ âèçóàëüíîãî êîíòðîëÿ èçäåëèé ìèêðîýëåêòðîíèêè,Ðàäèîòåõíèêà è ýëåêòðîíèêà, 1985, ò. ÕÕÕ,¹12, ññ. 2456-2458.

[8] Åðìîëàåâ À.Ã., Ïûòüåâ Þ.Ï. Àïðèîðíûå îöåíêè ïîëåçíîãî ñèãíàëà äëÿ ìîðôîëîãè÷åñêèõ ðåøàþùèõ àëãëðèòìîâ, - Àâòîìàòèçàöèÿ, 1984, ¹5, ññ. 118-120.

[9] Ïûòüåâ Þ.Ï, Çàäîðîæíûé Ñ.Ñ., Ëóêüÿíîâ À.Å. Îá àâòîìàòèçàöèè ñðàâíèòåëüíîãî ìîðôîëîãè÷åñêîãî àíàëèçà ýëåêòðîííîìèêðîñêîïè÷åñêèõ èçîáðàæåíèé, - Èçâ. ÀÍ ÑÑÑÐ, ñåð. ôèçè÷åñêàÿ, 1977, ò. 41, ¹11, ññ. õõõõ-õõõõ.

[10] A.A. Stepanov, S.Yu. Zheltov, Yu.V. Visilter. Shape analysis using Pyt'ev morphological paradigm and its using in machine vision. Proc. SPIE - Th. Intern. Soc. For Optical Engineering Videometrics III, 1994, v. 2350, pp. 163-167.

[11] Ïûòüåâ Þ.Ï.. Ìàòåìàòè÷åñêèå ìåòîäû èíòåðïðåòàöèè ýêñïåðèìåíòà, Âûñøàÿ øêîëà, 351 ñòð., 1989.

[12] Майзель С.О. Ратхер Е.С. Цветовые расчеты и измерения. М:Л:Госэнергоиздат 1941, (Труды всесоюзного электротехнического института, вып.56).

[13] P. Kronberg. Fernerkundung der Erde Ferdinand Enke. Verlag Stuthgart 1985.

1 Íàïðèìåð, â ñâÿçè ñ èçìåíåíèåì âðåìåíè ñóòîê, ïîãîäû, âðåìåíè ãîäà è ò.ï.

2 Ôðàãìåíò ìîðôîëîãè÷åñêîãî àíàëèçà öâåòíûõ èçîáðàæåíèé ñîäåðæèòñÿ â ðàáîòå[3].

3 âåêòîð fe áóäåò èìåòü îòðèöàòåëüíûå êîîðäèíàòû, åñëè îí íå ïðèíàäëåæèò âûïóêëîìó êîíóñó

4÷åðòà ñèìâîëèçèðóåò çàìûêàíèå, - âûïóêëûé çàìêíóòûé êîíóñ â Rn.

5 Если - более детальное изображение , то некоторые A() могут ращепитьсяна несколько подмножеств A(), на каждом из которых цвет постоянный, но различный на разных подмножествах A(). Однако, поскольку форма обычно строится исходя из данного изображения f(), v(f()) не может содержать изображения, которые более детально характеризуют изображенную сцену.

6 Äëÿ ïðîñòîòû ÿðêîñòü èçîáðàæåíèÿ ñ÷èòàåòñÿ ïîëîæèòåëüíîé â êàæäîé òî÷êå ïîëÿ çðåíèÿ Õ.

7 - êëàññ íåîòðèöàòåëüíûõ ôóíêöèé ïðèíàäëåæàùèõ .

8Îäíà è òà æå áóêâà F èñïîëüçîâàíà êàê äëÿ îïåðàòîðà , òàê è äëÿ îïåðàòîðà . Ýòà âîëüíîñòü íå äîëæíà âûçûâàòü íåäîðàçóìåíèÿ è ÷àñòî èñïîëüçóåòñÿ â ðàáîòå.

9Åñëè (As)=0, òî â çàäà÷å íàèëó÷øåãî ïðèáëèæåíèÿ (18) öâåò è ðàñïðåäåëåíèå ÿðêîñòè íà As ìîæíî ñ÷èòàòü ïðîèçâîëüíûìè, ïîñêîëüêó èõ çíà÷åíèÿ íå âëèÿþò íà âåëè÷èíó íåâÿçêè s.

10Âåêòîðû 1,..., q âûáèðàþòñÿ, íàïðèìåð, ñîîáðàçíî öâåòàì îáúåêòîâ, ïðåäñòàâëÿþùèõ èíòåðåñ.

1


Похожие работы: