СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТРУКТУРНЫХ ПРЕДСТАВЛЕНИЙ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ПРИНЦИПА РЕПРЕЗЕНТАЦИОННОЙ МИНИМАЛЬНОЙ ДЛИНЫ ОПИСАНИЯ
ÓÄÊ 004.932.2
ÑÐÀÂÍÈÒÅËÜÍÛÉ ÀÍÀËÈÇ ÑÒÐÓÊÒÓÐÍÛÕ ÏÐÅÄÑÒÀÂËÅÍÈÉ ÈÇÎÁÐÀÆÅÍÈÉ ÍÀ ÎÑÍÎÂÅ ÏÐÈÍÖÈÏÀ ÐÅÏÐÅÇÅÍÒÀÖÈÎÍÍÎÉ ÌÈÍÈÌÀËÜÍÎÉ ÄËÈÍÛ ÎÏÈÑÀÍÈß
© 2008 ã.
À. Ñ. Ïîòàïîâ, êàíä. òåõí. íàóê ÍÏÊ “Ãîñóäàðñòâåííûé îïòè÷åñêèé èíñòèòóò èì. Ñ.È. Âàâèëîâà”, Ñàíêò-Ïåòåðáóðã E-mail: apotapov@mail.wplus.net
Íà îñíîâå ðàíåå ïðåäëîæåííîãî ïðèíöèïà ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ (ÐÌÄÎ), ïðåäíàçíà÷åííîãî äëÿ êîëè÷åñòâåííîé îöåíêè ñòåïåíè èíâàðèàíòíîñòè ïðåäñòàâëåíèé èçîáðàæåíèé, ïðîèçâåäåí ñðàâíèòåëüíûé àíàëèç íåñêîëüêèõ àëãîðèòìîâ ñåãìåíòàöèè, ñòðîÿùèõ êîíòóðíûå îïèñàíèÿ èçîáðàæåíèé, à òàêæå íåñêîëüêèõ àëãîðèòìîâ ïîñòðîåíèÿ ñòðóêòóðíûõ îïèñàíèé èçîáðàæåíèé ñ èñïîëüçîâàíèåì ðàçëè÷íûõ àëôàâèòîâ ñòðóêòóðíûõ ýëåìåíòîâ. Îáîñíîâàíà àäåêâàòíîñòü èñïîëüçîâàíèÿ ïðèíöèïà ÐÌÄÎ ïðè ñðàâíåíèè èíâàðèàíòíîñòè ïðåäñòàâëåíèé èçîáðàæåíèé. Óñòàíîâëåíî, ÷òî îïòèìàëüíûå àëãîðèòìû ñåãìåíòàöèè ðàçëè÷àþòñÿ äëÿ ðàçíûõ âûáîðîê èçîáðàæåíèé (íàïðèìåð, àýðîêîñìè÷åñêèõ èëè ïîëó÷åííûõ âíóòðè ïîìåùåíèé). Íà îñíîâå îáúåêòèâíîãî êðèòåðèÿ âïåðâûå ñòðîãî îáîñíîâàíà öåëåñîîáðàçíîñòü èñïîëüçîâàíèÿ â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ îòðåçêîâ ïðÿìûõ ëèíèé è ñåãìåíòîâ êðèâûõ âòîðîãî ïîðÿäêà è íèçêàÿ ýôôåêòèâíîñòü êðèâûõ áîëåå âûñîêèõ ïîðÿäêîâ.
Êîäû OCIS: 3000.32960.
Ïîñòóïèëà â ðåäàêöèþ 02.06.2008.
Ââåäåíèå
Îäíîé èç íàèáîëåå âàæíûõ õàðàêòåðèñòèê àâòîìàòè÷åñêèõ ìåòîäîâ àíàëèçà èçîáðàæåíèé ÿâëÿåòñÿ ñòåïåíü èõ èíâàðèàíòíîñòè ïî îòíîøåíèþ ê âîçìîæíûì ôàêòîðàì èçìåí÷èâîñòè èçîáðàæåíèé, òàêèì êàê èçìåíåíèå îñâåùåíèÿ, ðàêóðñà ñúåìêè èëè òèïà ñåíñîðà, ñåçîííî-ñóòî÷íîé è ïðî÷åé èçìåí÷èâîñòè îáúåêòîâ ñöåíû [1]. Ñòåïåíü èíâàðèàíòíîñòè îïðåäåëÿåò âåðîÿòíîñòü ïîëó÷åíèÿ êîððåêòíîãî ðåøåíèÿ çàäà÷è è øèðîòó ñôåðû ïðèìåíåíèÿ òîãî èëè èíîãî ìåòîäà.  ïðåäìåòíûõ îáëàñòÿõ ñ âûñîêîé àïðèîðíîé íåîïðåäåëåííîñòüþ äî ñèõ ïîð íå ñóùåñòâóåò ìåòîäîâ àíàëèçà èçîáðàæåíèé, êîòîðûå áû îáëàäàëè çíà÷èòåëüíîé ñòåïåíüþ èíâàðèàíòíîñòè. Áîëåå òîãî, íà íàñòîÿùèé ìîìåíò íå ñóùåñòâóåò ïîäõîäîâ â îáëàñòè àíàëèçà èçîáðàæåíèé, êîòîðûå áû ïîçâîëÿëè íàïðàâëåííî óëó÷øàòü äàííóþ õàðàêòåðèñòèêó ìåòîäîâ àíàëèçà. Ðàçðàáîòêà ïîäîáíîãî ïîäõîäà ÿâëÿåòñÿ âåñüìà àêòóàëüíîé ïðîáëåìîé, ðåøåíèå êîòîðîé ìîæåò èìåòü áîëüøîå ïðàêòè÷åñêîå çíà÷åíèå.
Èç-çà áîëüøîãî ìíîãîîáðàçèÿ çàäà÷ àíàëèçà èçîáðàæåíèé ââåäåíèå îáùåãî êðèòåðèÿ, íà îñíîâå êîòîðîãî ìîæíî áûëî áû îöåíèâàòü èõ ñòåïåíü èíâàðèàíòíîñòè, ÿâëÿåòñÿ ïðîáëåìàòè÷íûì. Îäíàêî ëþáîé ìåòîä àíàëèçà èñïîëüçóåò íåêîòîðîå ïðåäñòàâëåíèå èçîáðàæåíèé, ïîä êîòîðûì îáû÷íî ïîíèìàåòñÿ ôîðìàëüíàÿ ñèñòåìà, ñîäåðæàùàÿ àëãîðèòìû äëÿ ïîëó÷åíèÿ â ÿâíîì âèäå îïèñàíèé îáúåêòîâ çàäàííîãî êëàññà [2]. Èìåííî ñòåïåíü èíâàðèàíòíîñòè ïðèâëåêàåìûõ ïðåäñòàâëåíèé èçîáðàæåíèé
ïðåèìóùåñòâåííî îïðåäåëÿåò ñòåïåíü èíâàðèàíòíîñòè ñîîòâåòñòâóþùèõ ìåòîäîâ àíàëèçà.
Ðàíåå àâòîðîì áûë ïðåäëîæåí ïðèíöèï ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ [3], ïîâûøåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé íà îñíîâå êîòîðîãî ñîîòâåòñòâóåò ïîâûøåíèþ ñòåïåíè èõ èíâàðèàíòíîñòè. Äàííûé ïðèíöèï îáîáùàåò ïðèíöèï ìèíèìàëüíîé äëèíû îïèñàíèÿ [4] è ñîñòîèò èç äâóõ ÷àñòåé:
Ìîäåëüþ, íàèëó÷øèì îáðàçîì îïèñûâàþùåé íåêîòîðîå èçîáðàæåíèå â ðàìêàõ çàäàííîãî ïðåäñòàâëåíèÿ, ÿâëÿåòñÿ ìîäåëü, ìèíèìèçèðóþùàÿ ñóììó äëèíû îïèñàíèÿ ìîäåëè è äëèíû îïèñàíèÿ èçîáðàæåíèÿ â ðàìêàõ ìîäåëè.
Ëó÷øèì ïðåäñòàâëåíèåì äëÿ äàííîé âûáîðêè èçîáðàæåíèé ÿâëÿåòñÿ ïðåäñòàâëåíèå, äëÿ êîòîðîãî ìèíèìèçèðóåòñÿ ñóììà äëèíû ïðåäñòàâëåíèÿ, ñóììû äëèí îïòèìàëüíûõ îïèñàíèé èçîáðàæåíèé â ðàìêàõ ïðåäñòàâëåíèÿ.
Êðèòåðèé ÐÌÄÎ ìîæåò áûòü âû÷èñëåí äëÿ íåêîòîðîãî ïðåäñòàâëåíèÿ ïî âûáîðêå èçîáðàæåíèé âíå çàâèñèìîñòè îò ïîñëåäóþùåé çàäà÷è àíàëèçà. Ýòî ïîçâîëÿåò ñðàâíèâàòü ïðåäñòàâëåíèÿ, èñïîëüçóåìûå â ðàçëè÷íûõ ìåòîäàõ, íå îïèðàÿñü íà êîíå÷íûé ðåçóëüòàò (íàïðèìåð, ðàñïîçíàâàíèÿ, èçìåðåíèÿ, âûÿâëåíèÿ èçìåíåíèé è ò. ä.), íà êîòîðûé òàêæå âëèÿþò ñëåäóþùèå çà ýòàïîì ïîñòðîåíèÿ îïèñàíèÿ èçîáðàæåíèé ýòàïû àíàëèçà.
Ïîñêîëüêó ïðîáëåìà èíâàðèàíòíîñòè íàèáîëåå çàìåòíî ïðîÿâëÿåòñÿ â çàäà÷àõ ñ ñóùåñòâåííîé àïðèîðíîé íåîïðåäåëåííîñòüþ, â íàñòîÿùåé ðàáîòå ïðîèçâîäèòñÿ ñðàâíåíèå ñòðóêòóðíûõ ïðåäñòàâëå-
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
35
íèé, ÿâëÿþùèõñÿ çäåñü íàèáîëåå ïðåäïî÷òèòåëüíûìè [1, 5]. Ðàññìàòðèâàþòñÿ êàê àëãîðèòìû ñåãìåíòàöèè èçîáðàæåíèé, â êîòîðûõ èçîáðàæåíèå ïðåäñòàâëÿåòñÿ êàê ñîâîêóïíîñòü íåçàâèñèìî îïèñûâàåìûõ îáëàñòåé, òàê è àëãîðèòìû ïîñòðîåíèÿ ñòðóêòóðíûõ ýëåìåíòîâ íà îñíîâå êîíòóðîâ. Ïîêàçûâàåòñÿ, ÷òî ðåçóëüòàòû ñðàâíåíèÿ ïðåäñòàâëåíèé íà îñíîâå êðèòåðèÿ ÐÌÄÎ íå òîëüêî ñîãëàñóþòñÿ ñ îïûòîì èññëåäîâàòåëåé, íî òàêæå ïîçâîëÿþò ïîëó÷èòü íîâóþ èíôîðìàöèþ îá ýôôåêòèâíîñòè ðàçëè÷íûõ ïðåäñòàâëåíèé.
Ïðåäñòàâëåíèÿ èçîáðàæåíèé â àëãîðèòìàõ ñåãìåíòàöèè
 äàííîé ðàáîòå ðàññìàòðèâàþòñÿ ñëåäóþùèå
ïðåäñòàâëåíèÿ, ñîñòàâëÿþùèå îñíîâó îäíîãî ñåìåé-
ñòâà àëãîðèòìîâ ñåãìåíòàöèè èçîáðàæåíèé. 1. Ïðåäñòàâëåíèå S0(1), â êîòîðîì èíòåíñèâíîñòè
ïèêñåëîâ ïîëàãàþòñÿ îòñ÷åòàìè ñòàòèñòè÷åñêè íå-
çàâèñèìûõ è îäèíàêîâî ðàñïðåäåëåííûõ ñëó÷àéíûõ
âåëè÷èí. Äëèíà îïèñàíèÿ èçîáðàæåíèÿ f (x, y):G → R â ðàìêàõ ïðåäñòàâëåíèÿ S0(1) ìîæåò áûòü îöåíåíà êàê
LS0 ( f ) = G H ( f ) + Nint log2 Nint,
(1)
ãäå ||G|| – ïëîùàäü îáëàñòè G, âûðàæàåìàÿ â äàííîì ñëó÷àå êàê êîëè÷åñòâî ïèêñåëîâ â èçîáðàæåíèè f, H( f ) – ýíòðîïèÿ çíà÷åíèé èíòåíñèâíîñòåé â ïðåäïîëîæåíèè îá èõ ñòàòèñòè÷åñêîé íåçàâèñèìîñòè, Nint – ÷èñëî ðàçëè÷íûõ óðîâíåé èíòåíñèâíîñòè. Âåëè÷èíà ||G||H( f ) ÿâëÿåòñÿ îöåíêîé ìàòåìàòè÷åñêîãî îæèäàíèÿ äëèíû îïèñàíèÿ èíòåíñèâíîñòåé äëÿ ïèêñåëîâ îáëàñòè G, çàøèôðîâàííûõ ñ ïîìîùüþ êîäà Õàôôìàíà. Äëÿ ðàñøèôðîâêè òàêîãî êîäà òðåáóåòñÿ òàáëèöà ïåðåêîäèðîâêè, êîòîðàÿ äîëæíà ñîäåðæàòüñÿ â îïèñàíèè èçîáðàæåíèé. Åå îáúåì ìîæíî îöåíèòü êàê Nintlog2Nint áèò.
2. Ïðåäñòàâëåíèå S1(1), â êîòîðîì èçîáðàæåíèå ïîëàãàåòñÿ ðàçáèòûì íà ñîâîêóïíîñòü îáëàñòåé G1, …, Gd. B êàæäîé îáëàñòè èíòåíñèâíîñòè ïèêñåëîâ èìåþò ñîáñòâåííîå ðàñïðåäåëåíèå. Ïîìèìî èíòåíñèâíîñòåé ïèêñåëîâ çäåñü òàêæå íåîáõîäèìî îïèñàòü ãðàíèöû îáëàñòåé δGi. Òàêèì îáðàçîì, äëèíà îïèñàíèÿ èçîáðàæåíèÿ â ðàìêàõ äàííîãî ïðåäñòàâëåíèÿ ìîæåò áûòü îöåíåíà êàê
LS1(1) ( f ) =
(2)
∑( )= Gi H ( fi ) + Nintlog2 Nint + δGi log2 Ndir , i
ãäå fi(x, y) = f (x, y)|Gi – ñóæåíèå èçîáðàæåíèÿ f íà îáëàñòü Gi ñ äëèíîé ãðàíèöû ||δGi||, Ndir – ÷èñëî âîçìîæíûõ íàïðàâëåíèé îò òåêóùåé òî÷êè ãðàíèöû íà ñëåäóþùóþ òî÷êó (çäåñü èñïîëüçîâàíî Ndir = 8).
Êðèòåðèé (2) ñëóæèò äëÿ âûáîðà ðàçäåëåíèÿ èçîáðàæåíèÿ íà îáëàñòè (îïèñàíèå àëãîðèòìà ïðåäñòàâëåíî â ðàáîòå [6]).
3. Ïðåäñòàâëåíèå S2(1), â êîòîðîì èçîáðàæåíèå òàêæå ïîëàãàåòñÿ ðàçäåëåííûì íà ñîâîêóïíîñòü îáëàñòåé, íî èç çíà÷åíèé fi(x, y) â êàæäîé îáëàñòè âû÷òåíà ôóíêöèÿ gi(x, y, wi), çàäàâàåìàÿ â âèäå
g(x, y, w) = w0 + w1x + w2 y + w3x2 + w4 xy + w5 y2. (3)
Íåâÿçêè â êàæäîé îáëàñòè ri(x, y) = [fi(x, y) – (x, y, wi)] ïîëàãàþòñÿ ñòàòèñòè÷åñêè íåçàâèñèìûìè è îáëàäàþùèìè ôèêñèðîâàííûì ðàñïðåäåëåíèåì â êàæäîé îáëàñòè. Äëèíà îïèñàíèÿ â ðàìêàõ ïðåäñòàâëåíèÿ S2(1) ìîæåò áûòü çàïèñàíà â âèäå
LS2(1) ( f ) =
(4)
d
∑= ⎣⎡ Gi H (ri ) + Nintlog2 Nint + δGi log2 Ndir + l(wi )⎦⎤ , i =1
ãäå
l(wi
)
=
mi 2
log2
Gi
– îöåíêà äëèíû îïèñàíèÿ ïà-
ðàìåòðîâ ôóíêöèè gi(x, y, wi) â i-îé îáëàñòè ñ ðàç-
ìåðíîñòüþ âåêòîðà ïàðàìåòðîâ mi = 6.
4. Ïðåäñòàâëåíèå S3(1), êîòîðîå àíàëîãè÷íî ïðåä-
ñòàâëåíèþ S2(1), íî â êîòîðîì âìåñòî ôóíêöèé âèäà
(3) èç çíà÷åíèé fi(x, y) â êàæäîé îáëàñòè âû÷èòàåòñÿ
íåêîòîðàÿ ñîâîêóïíîñòü ôóíêöèé Ãàáîða (áîëåå ïîä-
ðîáíî äàííîå ïðåäñòàâëåíèå îïèñàíî â ðàáîòå [7]).
Äëèíà îïèñàíèÿ èçîáðàæåíèÿ â ðàìêàõ ýòîãî ïðåä-
ñòàâëåíèÿ òàêæå îïèñûâàåòñÿ óðàâíåíèåì (4) çà òåì
èñêëþ÷åíèåì, ÷òî â äëèíå îïèñàíèÿ ïàðàìåòðîâ
l(wi
)
=
mi 2
log2
Gi
÷èñëî ïàðàìåòðîâ mi çàâèñèò îò
÷èñëà ôóíêöèé Ãàáîðà, âû÷èòàåìûõ èç çíà÷åíèé
fi(x, y) â îáëàñòè Gi.
Ïðåäñòàâëåíèÿ èçîáðàæåíèé â àëãîðèòìàõ ïîñòðîåíèÿ ñòðóêòóðíûõ ýëåìåíòîâ
Ñòðóêòóðíûå ýëåìåíòû ìîãóò áûòü ïîñòðîåíû íà
îñíîâå êîíòóðîâ, âûäåëåííûõ, êàê ãðàíèöû îáëàñ-
òåé, ïîëó÷åííûõ â ðàìêàõ ðàññìîòðåííûõ âûøå
ïðåäñòàâëåíèé â àëãîðèòìàõ ñåãìåíòàöèè, èëè âû-
äåëåííûõ êàêèì-ëèáî äðóãèì ñïîñîáîì. Ðàññìîò-
ðèì ñëåäóþùèå ïðåäñòàâëåíèÿ äëÿ îïèñàíèÿ åäèíñòâåííîãî êîíòóðà: δG = {(xi, yi)}iN= 1, ãäå N = ||δG|| – îáùåå ÷èñëî òî÷åê íà äàííîì êîíòóðå.  ïðîñòåé-
øåì ïðåäñòàâëåíèè êîíòóðà, êîòîðîå îáîçíà÷èì ÷åðåç S0(2), èñïîëüçóåòñÿ öåïíîå êîäèðîâàíèå, à äëèíà îïèñàíèÿ êîíòóðà ìîæåò áûòü îöåíåíà êàê
LS0(2) (δG) = δG log2 Ndir.
(5)
Îòìåòèì, ÷òî èìåííî ýòî óïðîùåííîå ïðåäñòàâëå-
íèå èñïîëüçîâàëîñü äëÿ îöåíêè äëèíû îïèñàíèÿ
36 “Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
ãðàíèö îáëàñòåé â óðàâíåíèÿõ (2) è (4). Ïðèâëå÷å-
íèå áîëåå òî÷íûõ îöåíîê, ïðèâåäåííûõ íèæå, ïîä-
ðàçóìåâàåò íåîáõîäèìîñòü ïîñòðîåíèÿ ñòðóêòóðíûõ
ýëåìåíòîâ â ïðîöåññå ñåãìåíòàöèè èçîáðàæåíèé
(î ïðîáëåìå ïîñòðîåíèÿ èåðàðõè÷åñêèõ îïèñà-
íèé ñì. [8]).
Îáîçíà÷èì ÷åðåç S1(2) ïðåäñòàâëåíèå, â êîòîðîì êîíòóð îïèñûâàåòñÿ êàê ñîâîêóïíîñòü ñåãìåíòîâ,
äëÿ êàæäîãî èç êîòîðûõ ïðîâîäèòñÿ îòðåçîê ïðÿìîé
ñ ìèíèìàëüíîé ýíòðîïèåé íåâÿçîê (îòêëîíåíèé îò-
ðåçêà îò òî÷åê êîíòóðà). ×åðåç S2(2) îáîçíà÷èì ïðåäñòàâëåíèå, â êîòîðîì ïîìèìî îòðåçêîâ ïðÿìûõ èñ-
ïîëüçóþòñÿ â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ äóãè
îêðóæíîñòåé è êðèâûå âòîðîãî ïîðÿäêà, à ÷åðåç
S3(2) – ïðåäñòàâëåíèå, â êîòîðîì èñïîëüçóþòñÿ òàêæå è êðèâûå òðåòüåãî ïîðÿäêà. Äëÿ âñåõ ýòèõ ïðåä-
ñòàâëåíèé êðèòåðèé ÐÌÄÎ ìîæíî ïðåäñòàâèòü åäè-
íîîáðàçíî.
Ðàññìîòðèì âíà÷àëå îäèí k-é ñåãìåíò. Ïóñòü îí
ñîñòîèò èç N(k) òî÷åê è îïèñûâàåòñÿ êðèâîé ñ mp(k) ïàðàìåòðàìè, äàþùåé íåâÿçêè ri(k), i = 1, …, N(k). Îöåíêà äëèíû îïèñàíèÿ ñåãìåíòà ñîñòîèò èç îöåíîê äëèí
îïèñàíèÿ ìîäåëè (ñòðóêòóðíîãî ýëåìåíòà, êîòîðûé
îáîçíà÷èì ÷åðåç sk) è äàííûõ â ðàìêàõ ìîäåëè (íåâÿçîê, ñ êîòîðûìè ñòðóêòóðíûé ýëåìåíò îïèñûâàåò
ñåãìåíò êîíòóðà). Äëèíà îïèñàíèÿ ñòðóêòóðíîãî ýëå-
ìåíòà ñîñòîèò èç
÷èñëà áèòîâ (êîòîðîå îáîçíà÷åíî ÷åðåç b), íåîá-
õîäèìûõ äëÿ óêàçàíèÿ òèïà ñòðóêòóðíîãî ýëåìåíòà,
äëèíû îïèñàíèÿ ïàðàìåòðîâ ñòðóêòóðíîãî ýëå-
ìåíòà
m(pk ) 2
log2 N (k ).
Èòàê, äëèíà îïèñàíèÿ îäíîãî ñòðóêòóðíîãî ýëå-
ìåíòà
ìîæåò
áûòü
îöåíåíà
êàê
b
+
m(pk ) 2
log2 N (k).
Äëèíà îïèñàíèÿ äàííûõ â ðàìêàõ ìîäåëè ñîîò-
âåòñòâóåò äëèíå îïèñàíèÿ íåâÿçîê ri(k) – çíà÷åíèé îòêëîíåíèÿ ñòðóêòóðíîãî ýëåìåíòà îò òî÷åê êîíòóðà.
Ñ÷èòàÿ íåâÿçêè íåçàâèñèìûìè îòñ÷åòàìè íåêîòîðîé
ñëó÷àéíîé âåëè÷èíû rk, ýòó äëèíó îïèñàíèÿ íåâÿçîê ìîæíî îöåíèòü êàê äëèíó êîäà Õàôôìàíà
∑N (k)H(rk), ãäå H (rk ) = − Pk (r)log2Pk (r) – îöåíêà
ýíòðîïèè íåâÿçîê ïî èõ ãrèñòîãðàììå Pk(r). Ïîìèìî ïåðåäà÷è íåâÿçîê äëÿ äåêîäèðîâàíèÿ íåîáõîäèìà òàáëèöà ïåðåêîäèðîâêè (èëè ãèñòîãðàììà Pk(r)), äëèíó êîòîðîé ìîæíî ãðóáî îöåíèòü êàê nrlog2nr, ãäå nr – êîëè÷åñòâî ðàçëè÷íûõ çíà÷åíèé íåâÿçîê äëÿ äàííîãî ñåãìåíòà.
Äëèíà îïèñàíèÿ îäíîãî ñåãìåíòà ñîñòàâèò
Lk = KS0(3) (sk ) + KSn(2) (δG|sk ) =
=
b
+
m(pk ) 2
log2 N (k)
+
N (k ) H (rk
)
+
nr log2nr.
Òîãäà îáùàÿ öåëåâàÿ ôóíêöèÿ áóäåò çàïèñûâàòüñÿ â ôîðìå
d
∑LSn(2) (δG) = k =1 Lk ,
(6)
ãäå îò íîìåðà ïðåäñòàâëåíèÿ n çàâèñèò âåëè÷èíà b, à òàêæå âûáîð êîíêðåòíîãî ÷èñëà ñåãìåíòîâ d è òèïîâ ñòðóêòóðíûõ ýëåìåíòîâ äëÿ êàæäîãî èç íèõ. Àëãîðèòì ñåãìåíòàöèè êîíòóðîâ, ìèíèìèçèðóþùèé äëèíó îïèñàíèÿ (6), ïðåäñòàâëåí â ðàáîòå [9].
Ñðàâíåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé
Ðàññìîòðèì òðè ïðåäìåòíûå îáëàñòè ñ âûñîêîé àïðèîðíîé íåîïðåäåëåííîñòüþ, êîòîðûå õàðàêòåðèçóþòñÿ âûáîðêàìè èçîáðàæåíèé F1, F2 è F3, ïðåäñòàâëåííûìè íà ðèñ. 1 è ñîäåðæàùèìè àýðîêîñìè÷åñêèå, ðàäèîëîêàöèîííûå èçîáðàæåíèÿ è èçîáðàæåíèÿ, ïîëó÷åííûå âíóòðè ïîìåùåíèé ñîîòâåòñòâåííî. Ñðàâíèì ýôôåêòèâíîñòè ïðèâåäåííûõ âûøå ïðåäñòàâëåíèé íà êàæäîé èç òðåõ ïðåäìåòíûõ îáëàñòåé.
 òàáë. 1 ïðèâåäåíû îòíîøåíèÿ ñðåäíèõ äëèí îïèñàíèÿ èçîáðàæåíèé ðàçíûõ âûáîðîê â ðàìêàõ ïðåäñòàâëåíèé Sn(1), èñïîëüçóåìûõ ïðè ñåãìåíòàöèè, à òàêæå äîëÿ èçîáðàæåíèé âûáîðîê, äëÿ êîòîðûõ ïðîèñõîäèò óìåíüøåíèå äëèíû îïèñàíèÿ ïðè ñìåíå ïðåäñòàâëåíèÿ.
Êàê âèäíî èç òàáë. 1, òîëüêî äëÿ ïåðâîé âûáîðêè (àýðîêîñìè÷åñêèå èçîáðàæåíèÿ) ïðåäñòàâëåíèå S3(1) ïðåâîñõîäèò ïðåäñòàâëåíèå S1(1) íà âñåõ èçîáðàæåíèÿõ, è òîëüêî äëÿ òðåòüåé âûáîðêè (èçîáðàæåíèÿ âíóòðè ïîìåùåíèé) ïðåäñòàâëåíèå S2(1) ïðåâîñõîäèò ïðåäñòàâëåíèå S1(1) íà âñåõ èçîáðàæåíèÿõ.  òî æå âðåìÿ îïèñàíèå èçîáðàæåíèé â âèäå ñîâîêóïíîñòè îáëàñòåé îêàçûâàåòñÿ âñåãäà ýôôåêòèâíåå åãî îïèñàíèÿ áåç òàêîãî ðàçäåëåíèÿ. Ðåçóëüòàò, ïðåäñòàâëåííûé â òàáë. 1, ñîãëàñóåòñÿ ñ ýâðèñòè÷åñêèìè îöåíêàìè ñîäåðæàíèÿ èçîáðàæåíèé, à èìåííî:
Ñöåíû âíóòðè ïîìåùåíèé ñîäåðæàò áîëüøîå ÷èñëî îáëàñòåé ñ ïëàâíûìè ïåðåõîäàìè ÿðêîñòè (ðèñ. 2), êîòîðûå ïðè èñïîëüçîâàíèè ïðåäñòàâëåíèÿ S1(1) ðàçäåëÿþòñÿ íà ìíîæåñòâî îáëàñòåé ïî óðîâíÿì îñâåùåííîñòè.  ðàìêàõ ïðåäñòàâëåíèÿ S2(1) â êà÷åñòâå äîïîëíèòåëüíûõ îáëàñòåé âûäåëÿþòñÿ ëèøü îáëàñòè òåíåé, à íå ïëàâíîãî èçìåíåíèÿ îñâåùåííîñòè.  òî æå âðåìÿ àýðîêîñìè÷åñêèå èçîáðàæåíèÿ ìîãóò òàêæå ñîäåðæàòü ïëàâíûå ïåðåõîäû ÿðêîñòè, îäíàêî äëÿ íèõ ýòî ÿâëÿåòñÿ ìåíåå õàðàêòåðíûì, ÷åì äëÿ èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé.
Èñêóññòâåííûå òåêñòóðû, õàðàêòåðíûå äëÿ èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé, íåäîñòàòî÷íî ýôôåêòèâíî îïèñûâàþòñÿ ôóíêöèÿìè Ãàáî-
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
37
(à)
(á)
(â)
Ðèñ. 1. Ïðèìåðû ôðàãìåíòîâ èçîáðàæåíèé èç âûáîðîê à) àýðîêîñìè÷åñêèõ èçîáðàæåíèé, á) ðàäèîëîêàöèîííûõ èçîáðàæåíèé, â) èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé.
ðà â ðàìêàõ ïðåäñòàâëåíèÿ S3(1), òîãäà êàê äëÿ åñòåñòâåííûõ òåêñòóð, ïðèñóòñòâóþùèõ íà àýðîêîñìè÷åñêèõ èçîáðàæåíèÿõ, äàííîå ïðåäñòàâëåíèå îêàçûâàåòñÿ áîëåå ýôôåêòèâíûì.
Ðàäèîëîêàöèîííûå èçîáðàæåíèÿ, êàê ïðàâèëî, íå ñîäåðæàò íè ïëàâíûõ ïåðåõîäîâ, íè òåêñòóð, õîðîøî îïèñûâàåìûõ ôóíêöèÿìè Ãàáîðà.
Ïðåäñòàâëåíèå èçîáðàæåíèé S1(1), îñíîâàííîå íà ìîäåëÿõ ñåãìåíòàöèè, ïîçâîëÿåò îñóùåñòâëÿòü âûäåëåíèå îäíîðîäíûõ îáëàñòåé íà èçîáðàæåíèè ïîä óïðàâëåíèåì èíôîðìàöèîííîé öåëåâîé ôóíêöèè. Ýòè îáëàñòè ñîîòâåòñòâóþò ãðàíèöàì âèäèìûõ ïîâåðõíîñòåé, îäíàêî èç-çà ñèëüíîãî óïðîùåíèÿ ïðåäñòàâëåíèÿ òàêîå ñîîòâåòñòâèå ìîæåò íàðóøàòüñÿ.
38 “Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
Òàáëèöà 1. Ñðàâíåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé Sn(1)
Îòíîøåíèå äëèí
Âûáîðêà
îïèñàíèÿ
F1 F2 F3
LS1(1) ( f ) LS0(1) ( f )
0,837 0,968 0,713
LS2(1) ( f ) LS1(1) ( f )
0,985 0,999 0,921
LS3(1) ( f ) LS1(1) ( f )
( )P LS1(1) ( f ) < LS0(1) ( f ) ( )P LS2(1) ( f ) < LS1(1) ( f ) ( )P LS3(1) ( f ) < LS1(1) ( f )
0,946 100% 57% 100%
0,988 100%
1% 63%
0,996 100% 100% 28%
Óñëîæíåíèå ïðåäñòàâëåíèÿ ïîçâîëÿåò óëó÷øèòü ðåçóëüòàòû ñåãìåíòàöèè, îäíàêî íå ëþáîå óñëîæíåíèå ïðèâîäèò ê ïîâûøåíèþ êà÷åñòâà ñåãìåíòàöèè, ÷òî íàõîäèò íåïîñðåäñòâåííîå îòðàæåíèå â ñðåäíåé äëèíå îïèñàíèÿ èçîáðàæåíèé âûáðàííîé ïðåäìåòíîé îáëàñòè. Òàêèì îáðàçîì, êðèòåðèé ÐÌÄÎ ìîæåò áûòü èñïîëüçîâàí äëÿ îöåíêè ýôôåêòèâíîñòè ïðåäñòàâëåíèé â çàäà÷å ñåãìåíòàöèè.
Ñðàâíèì ýôôåêòèâíîñòè ïðèâåäåííûõ âûøå ïðåäñòàâëåíèé êîíòóðîâ (ãðàíèö îáëàñòåé) ñ ïîìîùüþ ñòðóêòóðíûõ ýëåìåíòîâ. Â òàáë. 2 ïðèâåäåíû ñðåäíèå äëèíû îïèñàíèé ãðàíèö îáëàñòåé δG â ðàì-
Òàáëèöà 2. Ñðàâíåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé Sn(2)
Îòíîøåíèå äëèí
Âûáîðêà
îïèñàíèÿ
F1 F2 F3
LS1(2) (δG) LS0(2) (δG)
0,809 0,812 0,679
LS2(2) (δG) LS1(2) (δG)
0,831 0,845 0,791
LS3(2) (δG) LS2(2) (δG)
1,007 1,007 1,006
êàõ ïðåäñòàâëåíèé Sn(2) íà ðàçíûõ âûáîðêàõ èçîáðàæåíèé.
Èç òàáë. 2 âèäíî, ÷òî ïðè ââåäåíèè â ïðåäñòàâëåíèå êîíòóðîâ â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ, êàê
ïðÿìûõ ëèíèé, òàê è ñåãìåíòîâ êðèâûõ âòîðîãî ïîðÿäêà ïðîèñõîäèò çàìåòíîå óìåíüøåíèå ñðåäíåé äëèíû îïèñàíèÿ. Ïðè ýòîì ïðåäñòàâëåíèå S1(2) îêàçûâàåòñÿ ýôôåêòèâíåå ïðåäñòàâëåíèÿ S0(2) íà âñåõ èçîáðàæåíèÿõ âûáîðîê, à ïðåäñòàâëåíèå S2(2) ýôôåêòèâíåå ïðåäñòàâëåíèÿ S1(2). Èíûìè ñëîâàìè, â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ îáÿçàòåëüíî äîëæíû èñïîëüçîâàòüñÿ êàê îòðåçêè ïðÿìûõ ëèíèé, òàê è ñåãìåíòû êðèâûõ âòîðîãî ïîðÿäêà. Íàïðîòèâ, ââåäåíèå ñòðóêòóð-
íûõ ýëåìåíòîâ, ñîîòâåòñòâóþùèõ êðèâûì áîëåå âûñîêèõ ñòåïåíåé, íå óëó÷øàåò êðèòåðèé ÐÌÄÎ íè äëÿ îäíîé èç âûáðàííûõ ïðåäìåòíûõ îáëàñòåé.
Îòíîñèòåëüíîå êà÷åñòâî ïðåäñòàâëåíèé S1(2) è S2(2) áëèçêî äëÿ êàæäîé èç âûáîðîê, îäíàêî äëÿ èçîáðà-
(à) (á)
(â)
Ðèñ. 2. Ïðèìåðû ñåãìåíòàöèè ôðàãìåíòîâ èçîáðàæåíèé (à), ïîëó÷åííûõ âíóòðè ïîìåùåíèé, ñ ïîìîùüþ ïðåäñòàâëåíèé S1(1) (á) è S2(1) (â).
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
39
(à) (á)
(â)
Ðèñ. 3. Ñåãìåíòàöèÿ êîíòóðîâ, ïîëó÷åííûõ ñ ïîìîùüþ ôèëüòðàöèè Äåðèøà ïðè íåêîòîðîì óðîâíå ñãëàæèâàíèÿ.
æåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé, äëèíà îïèñàíèÿ êîíòóðîâ â ðàìêàõ ýòèõ ïðåäñòàâëåíèé óìåíüøàåòñÿ ñèëüíåå, òî åñòü êîíòóðû íà èçîáðàæåíèÿõ ýòîãî òèïà îáëàäàþò áîëüøåé ðåãóëÿðíîñòüþ.
Âûâîä î òîì, ÷òî äëÿ ðåàëüíûõ èçîáðàæåíèé èñïîëüçîâàíèå â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ êðèâûõ òðåòüåé è áîëåå âûñîêèõ ñòåïåíåé ÿâëÿåòñÿ íåýôôåêòèâíûì, îòíîñèòñÿ òîëüêî ê àëãîðèòìó ñåãìåíòàöèè èçîáðàæåíèé, èñïîëüçóþùåìó ðàññìîòðåííûå âûøå ïðåäñòàâëåíèÿ. ×òîáû ðàñïðîñòðàíèòü ýòîò âûâîä íà ñòðóêòóðíûå ýëåìåíòû, ñòðîÿùèåñÿ íà îñíîâå êîíòóðîâ, ïîëó÷àåìûõ ñ ïîìîùüþ äðóãèõ àëãîðèòìîâ, áûëè îïðåäåëåíû ñðåäíèå äëèíû îïèñàíèé êîíòóðîâ, âûäåëåííûõ íà èçîáðàæåíèÿõ âûáîðêè F1 ∪ F2 ∪ F3 ñ ïîìîùüþ ôèëüòðà Äåðèøà [10] (ïðèìåð êîíòóðîâ, ïîñòðîåííûõ ñ ïîìîùüþ ýòîãî ìåòîäà, è ðåçóëüòàòû ñåãìåíòàöèè ýòèõ êîíòóðîâ ïðèâåäåíû íà ðèñ. 3). Ïðè ýòîì ïîëó÷åíû ñëåäóþùèå çíà÷åíèÿ:
LS1(2) (δG) LS0(2) (δG) = 0,833,
LS2(2) (δG) LS1(2) (δG) = 0, 798,
LS3(2) (δG) LS2(2) (δG) = 1, 008.
Òàêèì îáðàçîì, îòíîñèòåëüíûå äëèíû îïèñàíèÿ ïîëó÷èëèñü äîñòàòî÷íî áëèçêèìè äëÿ êîíòóðîâ, âûäåëåííûõ ñ ïîìîùüþ ôèëüòðà Äåðèøà è ñ ïîìîùüþ àëãîðèòìà ñåãìåíòàöèè ñ èñïîëüçîâàíèåì îïèñàííûõ âûøå ïðåäñòàâëåíèé. Îäíàêî, êàê îêàçûâàåòñÿ, ïðè ïðèìåíåíèè ôèëüòðà Äåðèøà íåñêîëüêî áîëüøåå ïðåäïî÷òåíèå îòäàåòñÿ êðèâûì âòîðîãî ïîðÿäêà, ÷òî ìîæåò áûòü îáúÿñíåíî îñîáåííîñòÿìè ïðèìåíÿåìîãî â íåì ôèëüòðà, îñóùåñòâëÿþùåãî ñãëàæèâàíèå ïåðåïàäîâ ÿðêîñòè.
Çàêëþ÷åíèå
Ïðåäëîæåííûé ïðèíöèï ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ ïîçâîëèë ïðîèçâåñòè ñðàâíåíèå íåñêîëüêèõ ïðåäñòàâëåíèé èçîáðàæå-
íèé íà âûáîðêàõ èçîáðàæåíèé ñ áîëüøîé àïðèîðíîé íåîïðåäåëåííîñòüþ.  ðåçóëüòàòå ñðàâíåíèÿ îáíàðóæåíî, ÷òî ïðåäñòàâëåíèå, ó÷èòûâàþùåå âîçìîæíîñòü ïëàâíîãî èçìåíåíèÿ ÿðêîñòè ïèêñåëîâ îáëàñòè, áîëåå ýôôåêòèâíî äëÿ èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé.  òî æå âðåìÿ ïðåäñòàâëåíèå, â êîòîðîì ïðèâëåêàþòñÿ ôóíêöèè Ãàáîðà äëÿ îïèñàíèÿ ñîäåðæèìîãî îáëàñòåé, áîëåå ýôôåêòèâíî äëÿ àýðîêîñìè÷åñêèõ èçîáðàæåíèé.
Îáíàðóæåíà òàêæå âûñîêàÿ ýôôåêòèâíîñòü îòðåçêîâ ïðÿìûõ ëèíèé è ñåãìåíòîâ êðèâûõ âòîðîãî ïîðÿäêà â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ, àïïðîêñèìèðóþùèõ êîíòóðû íà èçîáðàæåíèÿõ òðåõ ðàññìîòðåííûõ âûáîðîê. Êðèâûå áîëåå âûñîêèõ ïîðÿäêîâ îêàçûâàþòñÿ ìàëîýôôåêòèâíûìè, òî åñòü íå äîëæíû èñïîëüçîâàòüñÿ ïðè ïîñòðîåíèè èíâàðèàíòíûõ ñòðóêòóðíûõ îïèñàíèé èçîáðàæåíèé.
Òàêèì îáðàçîì, ïðèíöèï ÐÌÄÎ ìîæåò áûòü èñïîëüçîâàí äëÿ îáîñíîâàííîãî âûáîðà ïðåäñòàâëåíèé èçîáðàæåíèé.  ðàáîòå ðàññìîòðåíû íåñêîëüêî ÷àñòíûõ ïðåäñòàâëåíèé, êîòîðûå òðåáóþò äàëüíåéøåãî ñîâåðøåíñòâîâàíèÿ, ÷òî ìîæåò áûòü âûïîëíåíî â ðàìêàõ ïðåäëîæåííîãî ïîäõîäà.
ËÈÒÅÐÀÒÓÐÀ
11. Lutsiv V.R., Malyshev I.A., Pepelka V., Potapov A.S. Target independent algorithms for description and structural matching of aerospace photographs // Proc. SPIE. 2002. V. 4741. P. 351–362.
12. Ìàðð Ä. Çðåíèå. Èíôîðìàöèîííûé ïîäõîä ê èçó÷åíèþ ïðåäñòàâëåíèÿ è îáðàáîòêè çðèòåëüíûõ îáðàçîâ: Ì.: Ðàäèî è ñâÿçü, 1987. 36 ñ.
13. Ïîòàïîâ À.Ñ. Èññëåäîâàíèå ïðåäñòàâëåíèé èçîáðàæåíèé íà îñíîâå ïðèíöèïà ðåïðåçåíòàöèîííîé äëèíû îïèñàíèÿ // Èçâ. âóçîâ. Ïðèáîðîñòðîåíèå. 2008. Ò. 51. ¹ 7. Ñ. 3–7.
14. Vitanyi P.M.B., Li M. Minimum description length induction, Bayesianism, and Kolmogorov complexity // IEEE Transactions on Information Theory. 2000. V. 46. ¹ 2. P. 446–464.
40 “Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
15. Rares A., Reinders M.J.T., Hendriks E.A. Image Interpretation Systems // Technical Report (MCCWS 2.1.1.3.C), MCCWS project, Information and Communication Theory Group. TU Delft. 1999. 32 p.
16. Potapov A.S. Image matching with the use of the minimum description length approach // Proc. SPIE. 2004. V. 5426. P. 164–175.
17. Ïîòàïîâ À.Ñ. Òåîðåòèêî-èíôîðìàöèîííûé ïîäõîä ê ââåäåíèþ îáðàòíûõ ñâÿçåé â ìíîãîóðîâíåâûõ ñèñòåìàõ êîìïüþòåðíîãî çðåíèÿ // Îïòè÷åñêèé æóðíàë. Ò. 74. ¹ 10. 2007. Ñ. 59–65.
18. Ïîòàïîâ À.Ñ., Ãóðîâ È.Ï., Àâåðêèí À.Í. Àíàëèç ìîäåëè êëåòîê çðèòåëüíîé êîðû íà îñíîâå ïðèíöèïà ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ // Èçâ. âóçîâ. Ïðèáîðîñòðîåíèå. 2008. (â ïå÷àòè).
19. Potapov A.S., Gamayunova O.S. Information criterion for constructing the hierarchical structural representations of images // Proc. SPIE. 2005. V. 5807. P. 443–454.
10. Deriche R. Optimal edge detection using recursive filtering // Proc. 1st Int. Conf. Computer Vision. 1987. P. 501–505.
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
41
ÑÐÀÂÍÈÒÅËÜÍÛÉ ÀÍÀËÈÇ ÑÒÐÓÊÒÓÐÍÛÕ ÏÐÅÄÑÒÀÂËÅÍÈÉ ÈÇÎÁÐÀÆÅÍÈÉ ÍÀ ÎÑÍÎÂÅ ÏÐÈÍÖÈÏÀ ÐÅÏÐÅÇÅÍÒÀÖÈÎÍÍÎÉ ÌÈÍÈÌÀËÜÍÎÉ ÄËÈÍÛ ÎÏÈÑÀÍÈß
© 2008 ã.
À. Ñ. Ïîòàïîâ, êàíä. òåõí. íàóê ÍÏÊ “Ãîñóäàðñòâåííûé îïòè÷åñêèé èíñòèòóò èì. Ñ.È. Âàâèëîâà”, Ñàíêò-Ïåòåðáóðã E-mail: apotapov@mail.wplus.net
Íà îñíîâå ðàíåå ïðåäëîæåííîãî ïðèíöèïà ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ (ÐÌÄÎ), ïðåäíàçíà÷åííîãî äëÿ êîëè÷åñòâåííîé îöåíêè ñòåïåíè èíâàðèàíòíîñòè ïðåäñòàâëåíèé èçîáðàæåíèé, ïðîèçâåäåí ñðàâíèòåëüíûé àíàëèç íåñêîëüêèõ àëãîðèòìîâ ñåãìåíòàöèè, ñòðîÿùèõ êîíòóðíûå îïèñàíèÿ èçîáðàæåíèé, à òàêæå íåñêîëüêèõ àëãîðèòìîâ ïîñòðîåíèÿ ñòðóêòóðíûõ îïèñàíèé èçîáðàæåíèé ñ èñïîëüçîâàíèåì ðàçëè÷íûõ àëôàâèòîâ ñòðóêòóðíûõ ýëåìåíòîâ. Îáîñíîâàíà àäåêâàòíîñòü èñïîëüçîâàíèÿ ïðèíöèïà ÐÌÄÎ ïðè ñðàâíåíèè èíâàðèàíòíîñòè ïðåäñòàâëåíèé èçîáðàæåíèé. Óñòàíîâëåíî, ÷òî îïòèìàëüíûå àëãîðèòìû ñåãìåíòàöèè ðàçëè÷àþòñÿ äëÿ ðàçíûõ âûáîðîê èçîáðàæåíèé (íàïðèìåð, àýðîêîñìè÷åñêèõ èëè ïîëó÷åííûõ âíóòðè ïîìåùåíèé). Íà îñíîâå îáúåêòèâíîãî êðèòåðèÿ âïåðâûå ñòðîãî îáîñíîâàíà öåëåñîîáðàçíîñòü èñïîëüçîâàíèÿ â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ îòðåçêîâ ïðÿìûõ ëèíèé è ñåãìåíòîâ êðèâûõ âòîðîãî ïîðÿäêà è íèçêàÿ ýôôåêòèâíîñòü êðèâûõ áîëåå âûñîêèõ ïîðÿäêîâ.
Êîäû OCIS: 3000.32960.
Ïîñòóïèëà â ðåäàêöèþ 02.06.2008.
Ââåäåíèå
Îäíîé èç íàèáîëåå âàæíûõ õàðàêòåðèñòèê àâòîìàòè÷åñêèõ ìåòîäîâ àíàëèçà èçîáðàæåíèé ÿâëÿåòñÿ ñòåïåíü èõ èíâàðèàíòíîñòè ïî îòíîøåíèþ ê âîçìîæíûì ôàêòîðàì èçìåí÷èâîñòè èçîáðàæåíèé, òàêèì êàê èçìåíåíèå îñâåùåíèÿ, ðàêóðñà ñúåìêè èëè òèïà ñåíñîðà, ñåçîííî-ñóòî÷íîé è ïðî÷åé èçìåí÷èâîñòè îáúåêòîâ ñöåíû [1]. Ñòåïåíü èíâàðèàíòíîñòè îïðåäåëÿåò âåðîÿòíîñòü ïîëó÷åíèÿ êîððåêòíîãî ðåøåíèÿ çàäà÷è è øèðîòó ñôåðû ïðèìåíåíèÿ òîãî èëè èíîãî ìåòîäà.  ïðåäìåòíûõ îáëàñòÿõ ñ âûñîêîé àïðèîðíîé íåîïðåäåëåííîñòüþ äî ñèõ ïîð íå ñóùåñòâóåò ìåòîäîâ àíàëèçà èçîáðàæåíèé, êîòîðûå áû îáëàäàëè çíà÷èòåëüíîé ñòåïåíüþ èíâàðèàíòíîñòè. Áîëåå òîãî, íà íàñòîÿùèé ìîìåíò íå ñóùåñòâóåò ïîäõîäîâ â îáëàñòè àíàëèçà èçîáðàæåíèé, êîòîðûå áû ïîçâîëÿëè íàïðàâëåííî óëó÷øàòü äàííóþ õàðàêòåðèñòèêó ìåòîäîâ àíàëèçà. Ðàçðàáîòêà ïîäîáíîãî ïîäõîäà ÿâëÿåòñÿ âåñüìà àêòóàëüíîé ïðîáëåìîé, ðåøåíèå êîòîðîé ìîæåò èìåòü áîëüøîå ïðàêòè÷åñêîå çíà÷åíèå.
Èç-çà áîëüøîãî ìíîãîîáðàçèÿ çàäà÷ àíàëèçà èçîáðàæåíèé ââåäåíèå îáùåãî êðèòåðèÿ, íà îñíîâå êîòîðîãî ìîæíî áûëî áû îöåíèâàòü èõ ñòåïåíü èíâàðèàíòíîñòè, ÿâëÿåòñÿ ïðîáëåìàòè÷íûì. Îäíàêî ëþáîé ìåòîä àíàëèçà èñïîëüçóåò íåêîòîðîå ïðåäñòàâëåíèå èçîáðàæåíèé, ïîä êîòîðûì îáû÷íî ïîíèìàåòñÿ ôîðìàëüíàÿ ñèñòåìà, ñîäåðæàùàÿ àëãîðèòìû äëÿ ïîëó÷åíèÿ â ÿâíîì âèäå îïèñàíèé îáúåêòîâ çàäàííîãî êëàññà [2]. Èìåííî ñòåïåíü èíâàðèàíòíîñòè ïðèâëåêàåìûõ ïðåäñòàâëåíèé èçîáðàæåíèé
ïðåèìóùåñòâåííî îïðåäåëÿåò ñòåïåíü èíâàðèàíòíîñòè ñîîòâåòñòâóþùèõ ìåòîäîâ àíàëèçà.
Ðàíåå àâòîðîì áûë ïðåäëîæåí ïðèíöèï ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ [3], ïîâûøåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé íà îñíîâå êîòîðîãî ñîîòâåòñòâóåò ïîâûøåíèþ ñòåïåíè èõ èíâàðèàíòíîñòè. Äàííûé ïðèíöèï îáîáùàåò ïðèíöèï ìèíèìàëüíîé äëèíû îïèñàíèÿ [4] è ñîñòîèò èç äâóõ ÷àñòåé:
Ìîäåëüþ, íàèëó÷øèì îáðàçîì îïèñûâàþùåé íåêîòîðîå èçîáðàæåíèå â ðàìêàõ çàäàííîãî ïðåäñòàâëåíèÿ, ÿâëÿåòñÿ ìîäåëü, ìèíèìèçèðóþùàÿ ñóììó äëèíû îïèñàíèÿ ìîäåëè è äëèíû îïèñàíèÿ èçîáðàæåíèÿ â ðàìêàõ ìîäåëè.
Ëó÷øèì ïðåäñòàâëåíèåì äëÿ äàííîé âûáîðêè èçîáðàæåíèé ÿâëÿåòñÿ ïðåäñòàâëåíèå, äëÿ êîòîðîãî ìèíèìèçèðóåòñÿ ñóììà äëèíû ïðåäñòàâëåíèÿ, ñóììû äëèí îïòèìàëüíûõ îïèñàíèé èçîáðàæåíèé â ðàìêàõ ïðåäñòàâëåíèÿ.
Êðèòåðèé ÐÌÄÎ ìîæåò áûòü âû÷èñëåí äëÿ íåêîòîðîãî ïðåäñòàâëåíèÿ ïî âûáîðêå èçîáðàæåíèé âíå çàâèñèìîñòè îò ïîñëåäóþùåé çàäà÷è àíàëèçà. Ýòî ïîçâîëÿåò ñðàâíèâàòü ïðåäñòàâëåíèÿ, èñïîëüçóåìûå â ðàçëè÷íûõ ìåòîäàõ, íå îïèðàÿñü íà êîíå÷íûé ðåçóëüòàò (íàïðèìåð, ðàñïîçíàâàíèÿ, èçìåðåíèÿ, âûÿâëåíèÿ èçìåíåíèé è ò. ä.), íà êîòîðûé òàêæå âëèÿþò ñëåäóþùèå çà ýòàïîì ïîñòðîåíèÿ îïèñàíèÿ èçîáðàæåíèé ýòàïû àíàëèçà.
Ïîñêîëüêó ïðîáëåìà èíâàðèàíòíîñòè íàèáîëåå çàìåòíî ïðîÿâëÿåòñÿ â çàäà÷àõ ñ ñóùåñòâåííîé àïðèîðíîé íåîïðåäåëåííîñòüþ, â íàñòîÿùåé ðàáîòå ïðîèçâîäèòñÿ ñðàâíåíèå ñòðóêòóðíûõ ïðåäñòàâëå-
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
35
íèé, ÿâëÿþùèõñÿ çäåñü íàèáîëåå ïðåäïî÷òèòåëüíûìè [1, 5]. Ðàññìàòðèâàþòñÿ êàê àëãîðèòìû ñåãìåíòàöèè èçîáðàæåíèé, â êîòîðûõ èçîáðàæåíèå ïðåäñòàâëÿåòñÿ êàê ñîâîêóïíîñòü íåçàâèñèìî îïèñûâàåìûõ îáëàñòåé, òàê è àëãîðèòìû ïîñòðîåíèÿ ñòðóêòóðíûõ ýëåìåíòîâ íà îñíîâå êîíòóðîâ. Ïîêàçûâàåòñÿ, ÷òî ðåçóëüòàòû ñðàâíåíèÿ ïðåäñòàâëåíèé íà îñíîâå êðèòåðèÿ ÐÌÄÎ íå òîëüêî ñîãëàñóþòñÿ ñ îïûòîì èññëåäîâàòåëåé, íî òàêæå ïîçâîëÿþò ïîëó÷èòü íîâóþ èíôîðìàöèþ îá ýôôåêòèâíîñòè ðàçëè÷íûõ ïðåäñòàâëåíèé.
Ïðåäñòàâëåíèÿ èçîáðàæåíèé â àëãîðèòìàõ ñåãìåíòàöèè
 äàííîé ðàáîòå ðàññìàòðèâàþòñÿ ñëåäóþùèå
ïðåäñòàâëåíèÿ, ñîñòàâëÿþùèå îñíîâó îäíîãî ñåìåé-
ñòâà àëãîðèòìîâ ñåãìåíòàöèè èçîáðàæåíèé. 1. Ïðåäñòàâëåíèå S0(1), â êîòîðîì èíòåíñèâíîñòè
ïèêñåëîâ ïîëàãàþòñÿ îòñ÷åòàìè ñòàòèñòè÷åñêè íå-
çàâèñèìûõ è îäèíàêîâî ðàñïðåäåëåííûõ ñëó÷àéíûõ
âåëè÷èí. Äëèíà îïèñàíèÿ èçîáðàæåíèÿ f (x, y):G → R â ðàìêàõ ïðåäñòàâëåíèÿ S0(1) ìîæåò áûòü îöåíåíà êàê
LS0 ( f ) = G H ( f ) + Nint log2 Nint,
(1)
ãäå ||G|| – ïëîùàäü îáëàñòè G, âûðàæàåìàÿ â äàííîì ñëó÷àå êàê êîëè÷åñòâî ïèêñåëîâ â èçîáðàæåíèè f, H( f ) – ýíòðîïèÿ çíà÷åíèé èíòåíñèâíîñòåé â ïðåäïîëîæåíèè îá èõ ñòàòèñòè÷åñêîé íåçàâèñèìîñòè, Nint – ÷èñëî ðàçëè÷íûõ óðîâíåé èíòåíñèâíîñòè. Âåëè÷èíà ||G||H( f ) ÿâëÿåòñÿ îöåíêîé ìàòåìàòè÷åñêîãî îæèäàíèÿ äëèíû îïèñàíèÿ èíòåíñèâíîñòåé äëÿ ïèêñåëîâ îáëàñòè G, çàøèôðîâàííûõ ñ ïîìîùüþ êîäà Õàôôìàíà. Äëÿ ðàñøèôðîâêè òàêîãî êîäà òðåáóåòñÿ òàáëèöà ïåðåêîäèðîâêè, êîòîðàÿ äîëæíà ñîäåðæàòüñÿ â îïèñàíèè èçîáðàæåíèé. Åå îáúåì ìîæíî îöåíèòü êàê Nintlog2Nint áèò.
2. Ïðåäñòàâëåíèå S1(1), â êîòîðîì èçîáðàæåíèå ïîëàãàåòñÿ ðàçáèòûì íà ñîâîêóïíîñòü îáëàñòåé G1, …, Gd. B êàæäîé îáëàñòè èíòåíñèâíîñòè ïèêñåëîâ èìåþò ñîáñòâåííîå ðàñïðåäåëåíèå. Ïîìèìî èíòåíñèâíîñòåé ïèêñåëîâ çäåñü òàêæå íåîáõîäèìî îïèñàòü ãðàíèöû îáëàñòåé δGi. Òàêèì îáðàçîì, äëèíà îïèñàíèÿ èçîáðàæåíèÿ â ðàìêàõ äàííîãî ïðåäñòàâëåíèÿ ìîæåò áûòü îöåíåíà êàê
LS1(1) ( f ) =
(2)
∑( )= Gi H ( fi ) + Nintlog2 Nint + δGi log2 Ndir , i
ãäå fi(x, y) = f (x, y)|Gi – ñóæåíèå èçîáðàæåíèÿ f íà îáëàñòü Gi ñ äëèíîé ãðàíèöû ||δGi||, Ndir – ÷èñëî âîçìîæíûõ íàïðàâëåíèé îò òåêóùåé òî÷êè ãðàíèöû íà ñëåäóþùóþ òî÷êó (çäåñü èñïîëüçîâàíî Ndir = 8).
Êðèòåðèé (2) ñëóæèò äëÿ âûáîðà ðàçäåëåíèÿ èçîáðàæåíèÿ íà îáëàñòè (îïèñàíèå àëãîðèòìà ïðåäñòàâëåíî â ðàáîòå [6]).
3. Ïðåäñòàâëåíèå S2(1), â êîòîðîì èçîáðàæåíèå òàêæå ïîëàãàåòñÿ ðàçäåëåííûì íà ñîâîêóïíîñòü îáëàñòåé, íî èç çíà÷åíèé fi(x, y) â êàæäîé îáëàñòè âû÷òåíà ôóíêöèÿ gi(x, y, wi), çàäàâàåìàÿ â âèäå
g(x, y, w) = w0 + w1x + w2 y + w3x2 + w4 xy + w5 y2. (3)
Íåâÿçêè â êàæäîé îáëàñòè ri(x, y) = [fi(x, y) – (x, y, wi)] ïîëàãàþòñÿ ñòàòèñòè÷åñêè íåçàâèñèìûìè è îáëàäàþùèìè ôèêñèðîâàííûì ðàñïðåäåëåíèåì â êàæäîé îáëàñòè. Äëèíà îïèñàíèÿ â ðàìêàõ ïðåäñòàâëåíèÿ S2(1) ìîæåò áûòü çàïèñàíà â âèäå
LS2(1) ( f ) =
(4)
d
∑= ⎣⎡ Gi H (ri ) + Nintlog2 Nint + δGi log2 Ndir + l(wi )⎦⎤ , i =1
ãäå
l(wi
)
=
mi 2
log2
Gi
– îöåíêà äëèíû îïèñàíèÿ ïà-
ðàìåòðîâ ôóíêöèè gi(x, y, wi) â i-îé îáëàñòè ñ ðàç-
ìåðíîñòüþ âåêòîðà ïàðàìåòðîâ mi = 6.
4. Ïðåäñòàâëåíèå S3(1), êîòîðîå àíàëîãè÷íî ïðåä-
ñòàâëåíèþ S2(1), íî â êîòîðîì âìåñòî ôóíêöèé âèäà
(3) èç çíà÷åíèé fi(x, y) â êàæäîé îáëàñòè âû÷èòàåòñÿ
íåêîòîðàÿ ñîâîêóïíîñòü ôóíêöèé Ãàáîða (áîëåå ïîä-
ðîáíî äàííîå ïðåäñòàâëåíèå îïèñàíî â ðàáîòå [7]).
Äëèíà îïèñàíèÿ èçîáðàæåíèÿ â ðàìêàõ ýòîãî ïðåä-
ñòàâëåíèÿ òàêæå îïèñûâàåòñÿ óðàâíåíèåì (4) çà òåì
èñêëþ÷åíèåì, ÷òî â äëèíå îïèñàíèÿ ïàðàìåòðîâ
l(wi
)
=
mi 2
log2
Gi
÷èñëî ïàðàìåòðîâ mi çàâèñèò îò
÷èñëà ôóíêöèé Ãàáîðà, âû÷èòàåìûõ èç çíà÷åíèé
fi(x, y) â îáëàñòè Gi.
Ïðåäñòàâëåíèÿ èçîáðàæåíèé â àëãîðèòìàõ ïîñòðîåíèÿ ñòðóêòóðíûõ ýëåìåíòîâ
Ñòðóêòóðíûå ýëåìåíòû ìîãóò áûòü ïîñòðîåíû íà
îñíîâå êîíòóðîâ, âûäåëåííûõ, êàê ãðàíèöû îáëàñ-
òåé, ïîëó÷åííûõ â ðàìêàõ ðàññìîòðåííûõ âûøå
ïðåäñòàâëåíèé â àëãîðèòìàõ ñåãìåíòàöèè, èëè âû-
äåëåííûõ êàêèì-ëèáî äðóãèì ñïîñîáîì. Ðàññìîò-
ðèì ñëåäóþùèå ïðåäñòàâëåíèÿ äëÿ îïèñàíèÿ åäèíñòâåííîãî êîíòóðà: δG = {(xi, yi)}iN= 1, ãäå N = ||δG|| – îáùåå ÷èñëî òî÷åê íà äàííîì êîíòóðå.  ïðîñòåé-
øåì ïðåäñòàâëåíèè êîíòóðà, êîòîðîå îáîçíà÷èì ÷åðåç S0(2), èñïîëüçóåòñÿ öåïíîå êîäèðîâàíèå, à äëèíà îïèñàíèÿ êîíòóðà ìîæåò áûòü îöåíåíà êàê
LS0(2) (δG) = δG log2 Ndir.
(5)
Îòìåòèì, ÷òî èìåííî ýòî óïðîùåííîå ïðåäñòàâëå-
íèå èñïîëüçîâàëîñü äëÿ îöåíêè äëèíû îïèñàíèÿ
36 “Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
ãðàíèö îáëàñòåé â óðàâíåíèÿõ (2) è (4). Ïðèâëå÷å-
íèå áîëåå òî÷íûõ îöåíîê, ïðèâåäåííûõ íèæå, ïîä-
ðàçóìåâàåò íåîáõîäèìîñòü ïîñòðîåíèÿ ñòðóêòóðíûõ
ýëåìåíòîâ â ïðîöåññå ñåãìåíòàöèè èçîáðàæåíèé
(î ïðîáëåìå ïîñòðîåíèÿ èåðàðõè÷åñêèõ îïèñà-
íèé ñì. [8]).
Îáîçíà÷èì ÷åðåç S1(2) ïðåäñòàâëåíèå, â êîòîðîì êîíòóð îïèñûâàåòñÿ êàê ñîâîêóïíîñòü ñåãìåíòîâ,
äëÿ êàæäîãî èç êîòîðûõ ïðîâîäèòñÿ îòðåçîê ïðÿìîé
ñ ìèíèìàëüíîé ýíòðîïèåé íåâÿçîê (îòêëîíåíèé îò-
ðåçêà îò òî÷åê êîíòóðà). ×åðåç S2(2) îáîçíà÷èì ïðåäñòàâëåíèå, â êîòîðîì ïîìèìî îòðåçêîâ ïðÿìûõ èñ-
ïîëüçóþòñÿ â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ äóãè
îêðóæíîñòåé è êðèâûå âòîðîãî ïîðÿäêà, à ÷åðåç
S3(2) – ïðåäñòàâëåíèå, â êîòîðîì èñïîëüçóþòñÿ òàêæå è êðèâûå òðåòüåãî ïîðÿäêà. Äëÿ âñåõ ýòèõ ïðåä-
ñòàâëåíèé êðèòåðèé ÐÌÄÎ ìîæíî ïðåäñòàâèòü åäè-
íîîáðàçíî.
Ðàññìîòðèì âíà÷àëå îäèí k-é ñåãìåíò. Ïóñòü îí
ñîñòîèò èç N(k) òî÷åê è îïèñûâàåòñÿ êðèâîé ñ mp(k) ïàðàìåòðàìè, äàþùåé íåâÿçêè ri(k), i = 1, …, N(k). Îöåíêà äëèíû îïèñàíèÿ ñåãìåíòà ñîñòîèò èç îöåíîê äëèí
îïèñàíèÿ ìîäåëè (ñòðóêòóðíîãî ýëåìåíòà, êîòîðûé
îáîçíà÷èì ÷åðåç sk) è äàííûõ â ðàìêàõ ìîäåëè (íåâÿçîê, ñ êîòîðûìè ñòðóêòóðíûé ýëåìåíò îïèñûâàåò
ñåãìåíò êîíòóðà). Äëèíà îïèñàíèÿ ñòðóêòóðíîãî ýëå-
ìåíòà ñîñòîèò èç
÷èñëà áèòîâ (êîòîðîå îáîçíà÷åíî ÷åðåç b), íåîá-
õîäèìûõ äëÿ óêàçàíèÿ òèïà ñòðóêòóðíîãî ýëåìåíòà,
äëèíû îïèñàíèÿ ïàðàìåòðîâ ñòðóêòóðíîãî ýëå-
ìåíòà
m(pk ) 2
log2 N (k ).
Èòàê, äëèíà îïèñàíèÿ îäíîãî ñòðóêòóðíîãî ýëå-
ìåíòà
ìîæåò
áûòü
îöåíåíà
êàê
b
+
m(pk ) 2
log2 N (k).
Äëèíà îïèñàíèÿ äàííûõ â ðàìêàõ ìîäåëè ñîîò-
âåòñòâóåò äëèíå îïèñàíèÿ íåâÿçîê ri(k) – çíà÷åíèé îòêëîíåíèÿ ñòðóêòóðíîãî ýëåìåíòà îò òî÷åê êîíòóðà.
Ñ÷èòàÿ íåâÿçêè íåçàâèñèìûìè îòñ÷åòàìè íåêîòîðîé
ñëó÷àéíîé âåëè÷èíû rk, ýòó äëèíó îïèñàíèÿ íåâÿçîê ìîæíî îöåíèòü êàê äëèíó êîäà Õàôôìàíà
∑N (k)H(rk), ãäå H (rk ) = − Pk (r)log2Pk (r) – îöåíêà
ýíòðîïèè íåâÿçîê ïî èõ ãrèñòîãðàììå Pk(r). Ïîìèìî ïåðåäà÷è íåâÿçîê äëÿ äåêîäèðîâàíèÿ íåîáõîäèìà òàáëèöà ïåðåêîäèðîâêè (èëè ãèñòîãðàììà Pk(r)), äëèíó êîòîðîé ìîæíî ãðóáî îöåíèòü êàê nrlog2nr, ãäå nr – êîëè÷åñòâî ðàçëè÷íûõ çíà÷åíèé íåâÿçîê äëÿ äàííîãî ñåãìåíòà.
Äëèíà îïèñàíèÿ îäíîãî ñåãìåíòà ñîñòàâèò
Lk = KS0(3) (sk ) + KSn(2) (δG|sk ) =
=
b
+
m(pk ) 2
log2 N (k)
+
N (k ) H (rk
)
+
nr log2nr.
Òîãäà îáùàÿ öåëåâàÿ ôóíêöèÿ áóäåò çàïèñûâàòüñÿ â ôîðìå
d
∑LSn(2) (δG) = k =1 Lk ,
(6)
ãäå îò íîìåðà ïðåäñòàâëåíèÿ n çàâèñèò âåëè÷èíà b, à òàêæå âûáîð êîíêðåòíîãî ÷èñëà ñåãìåíòîâ d è òèïîâ ñòðóêòóðíûõ ýëåìåíòîâ äëÿ êàæäîãî èç íèõ. Àëãîðèòì ñåãìåíòàöèè êîíòóðîâ, ìèíèìèçèðóþùèé äëèíó îïèñàíèÿ (6), ïðåäñòàâëåí â ðàáîòå [9].
Ñðàâíåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé
Ðàññìîòðèì òðè ïðåäìåòíûå îáëàñòè ñ âûñîêîé àïðèîðíîé íåîïðåäåëåííîñòüþ, êîòîðûå õàðàêòåðèçóþòñÿ âûáîðêàìè èçîáðàæåíèé F1, F2 è F3, ïðåäñòàâëåííûìè íà ðèñ. 1 è ñîäåðæàùèìè àýðîêîñìè÷åñêèå, ðàäèîëîêàöèîííûå èçîáðàæåíèÿ è èçîáðàæåíèÿ, ïîëó÷åííûå âíóòðè ïîìåùåíèé ñîîòâåòñòâåííî. Ñðàâíèì ýôôåêòèâíîñòè ïðèâåäåííûõ âûøå ïðåäñòàâëåíèé íà êàæäîé èç òðåõ ïðåäìåòíûõ îáëàñòåé.
 òàáë. 1 ïðèâåäåíû îòíîøåíèÿ ñðåäíèõ äëèí îïèñàíèÿ èçîáðàæåíèé ðàçíûõ âûáîðîê â ðàìêàõ ïðåäñòàâëåíèé Sn(1), èñïîëüçóåìûõ ïðè ñåãìåíòàöèè, à òàêæå äîëÿ èçîáðàæåíèé âûáîðîê, äëÿ êîòîðûõ ïðîèñõîäèò óìåíüøåíèå äëèíû îïèñàíèÿ ïðè ñìåíå ïðåäñòàâëåíèÿ.
Êàê âèäíî èç òàáë. 1, òîëüêî äëÿ ïåðâîé âûáîðêè (àýðîêîñìè÷åñêèå èçîáðàæåíèÿ) ïðåäñòàâëåíèå S3(1) ïðåâîñõîäèò ïðåäñòàâëåíèå S1(1) íà âñåõ èçîáðàæåíèÿõ, è òîëüêî äëÿ òðåòüåé âûáîðêè (èçîáðàæåíèÿ âíóòðè ïîìåùåíèé) ïðåäñòàâëåíèå S2(1) ïðåâîñõîäèò ïðåäñòàâëåíèå S1(1) íà âñåõ èçîáðàæåíèÿõ.  òî æå âðåìÿ îïèñàíèå èçîáðàæåíèé â âèäå ñîâîêóïíîñòè îáëàñòåé îêàçûâàåòñÿ âñåãäà ýôôåêòèâíåå åãî îïèñàíèÿ áåç òàêîãî ðàçäåëåíèÿ. Ðåçóëüòàò, ïðåäñòàâëåííûé â òàáë. 1, ñîãëàñóåòñÿ ñ ýâðèñòè÷åñêèìè îöåíêàìè ñîäåðæàíèÿ èçîáðàæåíèé, à èìåííî:
Ñöåíû âíóòðè ïîìåùåíèé ñîäåðæàò áîëüøîå ÷èñëî îáëàñòåé ñ ïëàâíûìè ïåðåõîäàìè ÿðêîñòè (ðèñ. 2), êîòîðûå ïðè èñïîëüçîâàíèè ïðåäñòàâëåíèÿ S1(1) ðàçäåëÿþòñÿ íà ìíîæåñòâî îáëàñòåé ïî óðîâíÿì îñâåùåííîñòè.  ðàìêàõ ïðåäñòàâëåíèÿ S2(1) â êà÷åñòâå äîïîëíèòåëüíûõ îáëàñòåé âûäåëÿþòñÿ ëèøü îáëàñòè òåíåé, à íå ïëàâíîãî èçìåíåíèÿ îñâåùåííîñòè.  òî æå âðåìÿ àýðîêîñìè÷åñêèå èçîáðàæåíèÿ ìîãóò òàêæå ñîäåðæàòü ïëàâíûå ïåðåõîäû ÿðêîñòè, îäíàêî äëÿ íèõ ýòî ÿâëÿåòñÿ ìåíåå õàðàêòåðíûì, ÷åì äëÿ èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé.
Èñêóññòâåííûå òåêñòóðû, õàðàêòåðíûå äëÿ èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé, íåäîñòàòî÷íî ýôôåêòèâíî îïèñûâàþòñÿ ôóíêöèÿìè Ãàáî-
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
37
(à)
(á)
(â)
Ðèñ. 1. Ïðèìåðû ôðàãìåíòîâ èçîáðàæåíèé èç âûáîðîê à) àýðîêîñìè÷åñêèõ èçîáðàæåíèé, á) ðàäèîëîêàöèîííûõ èçîáðàæåíèé, â) èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé.
ðà â ðàìêàõ ïðåäñòàâëåíèÿ S3(1), òîãäà êàê äëÿ åñòåñòâåííûõ òåêñòóð, ïðèñóòñòâóþùèõ íà àýðîêîñìè÷åñêèõ èçîáðàæåíèÿõ, äàííîå ïðåäñòàâëåíèå îêàçûâàåòñÿ áîëåå ýôôåêòèâíûì.
Ðàäèîëîêàöèîííûå èçîáðàæåíèÿ, êàê ïðàâèëî, íå ñîäåðæàò íè ïëàâíûõ ïåðåõîäîâ, íè òåêñòóð, õîðîøî îïèñûâàåìûõ ôóíêöèÿìè Ãàáîðà.
Ïðåäñòàâëåíèå èçîáðàæåíèé S1(1), îñíîâàííîå íà ìîäåëÿõ ñåãìåíòàöèè, ïîçâîëÿåò îñóùåñòâëÿòü âûäåëåíèå îäíîðîäíûõ îáëàñòåé íà èçîáðàæåíèè ïîä óïðàâëåíèåì èíôîðìàöèîííîé öåëåâîé ôóíêöèè. Ýòè îáëàñòè ñîîòâåòñòâóþò ãðàíèöàì âèäèìûõ ïîâåðõíîñòåé, îäíàêî èç-çà ñèëüíîãî óïðîùåíèÿ ïðåäñòàâëåíèÿ òàêîå ñîîòâåòñòâèå ìîæåò íàðóøàòüñÿ.
38 “Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
Òàáëèöà 1. Ñðàâíåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé Sn(1)
Îòíîøåíèå äëèí
Âûáîðêà
îïèñàíèÿ
F1 F2 F3
LS1(1) ( f ) LS0(1) ( f )
0,837 0,968 0,713
LS2(1) ( f ) LS1(1) ( f )
0,985 0,999 0,921
LS3(1) ( f ) LS1(1) ( f )
( )P LS1(1) ( f ) < LS0(1) ( f ) ( )P LS2(1) ( f ) < LS1(1) ( f ) ( )P LS3(1) ( f ) < LS1(1) ( f )
0,946 100% 57% 100%
0,988 100%
1% 63%
0,996 100% 100% 28%
Óñëîæíåíèå ïðåäñòàâëåíèÿ ïîçâîëÿåò óëó÷øèòü ðåçóëüòàòû ñåãìåíòàöèè, îäíàêî íå ëþáîå óñëîæíåíèå ïðèâîäèò ê ïîâûøåíèþ êà÷åñòâà ñåãìåíòàöèè, ÷òî íàõîäèò íåïîñðåäñòâåííîå îòðàæåíèå â ñðåäíåé äëèíå îïèñàíèÿ èçîáðàæåíèé âûáðàííîé ïðåäìåòíîé îáëàñòè. Òàêèì îáðàçîì, êðèòåðèé ÐÌÄÎ ìîæåò áûòü èñïîëüçîâàí äëÿ îöåíêè ýôôåêòèâíîñòè ïðåäñòàâëåíèé â çàäà÷å ñåãìåíòàöèè.
Ñðàâíèì ýôôåêòèâíîñòè ïðèâåäåííûõ âûøå ïðåäñòàâëåíèé êîíòóðîâ (ãðàíèö îáëàñòåé) ñ ïîìîùüþ ñòðóêòóðíûõ ýëåìåíòîâ. Â òàáë. 2 ïðèâåäåíû ñðåäíèå äëèíû îïèñàíèé ãðàíèö îáëàñòåé δG â ðàì-
Òàáëèöà 2. Ñðàâíåíèå ýôôåêòèâíîñòè ïðåäñòàâëåíèé Sn(2)
Îòíîøåíèå äëèí
Âûáîðêà
îïèñàíèÿ
F1 F2 F3
LS1(2) (δG) LS0(2) (δG)
0,809 0,812 0,679
LS2(2) (δG) LS1(2) (δG)
0,831 0,845 0,791
LS3(2) (δG) LS2(2) (δG)
1,007 1,007 1,006
êàõ ïðåäñòàâëåíèé Sn(2) íà ðàçíûõ âûáîðêàõ èçîáðàæåíèé.
Èç òàáë. 2 âèäíî, ÷òî ïðè ââåäåíèè â ïðåäñòàâëåíèå êîíòóðîâ â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ, êàê
ïðÿìûõ ëèíèé, òàê è ñåãìåíòîâ êðèâûõ âòîðîãî ïîðÿäêà ïðîèñõîäèò çàìåòíîå óìåíüøåíèå ñðåäíåé äëèíû îïèñàíèÿ. Ïðè ýòîì ïðåäñòàâëåíèå S1(2) îêàçûâàåòñÿ ýôôåêòèâíåå ïðåäñòàâëåíèÿ S0(2) íà âñåõ èçîáðàæåíèÿõ âûáîðîê, à ïðåäñòàâëåíèå S2(2) ýôôåêòèâíåå ïðåäñòàâëåíèÿ S1(2). Èíûìè ñëîâàìè, â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ îáÿçàòåëüíî äîëæíû èñïîëüçîâàòüñÿ êàê îòðåçêè ïðÿìûõ ëèíèé, òàê è ñåãìåíòû êðèâûõ âòîðîãî ïîðÿäêà. Íàïðîòèâ, ââåäåíèå ñòðóêòóð-
íûõ ýëåìåíòîâ, ñîîòâåòñòâóþùèõ êðèâûì áîëåå âûñîêèõ ñòåïåíåé, íå óëó÷øàåò êðèòåðèé ÐÌÄÎ íè äëÿ îäíîé èç âûáðàííûõ ïðåäìåòíûõ îáëàñòåé.
Îòíîñèòåëüíîå êà÷åñòâî ïðåäñòàâëåíèé S1(2) è S2(2) áëèçêî äëÿ êàæäîé èç âûáîðîê, îäíàêî äëÿ èçîáðà-
(à) (á)
(â)
Ðèñ. 2. Ïðèìåðû ñåãìåíòàöèè ôðàãìåíòîâ èçîáðàæåíèé (à), ïîëó÷åííûõ âíóòðè ïîìåùåíèé, ñ ïîìîùüþ ïðåäñòàâëåíèé S1(1) (á) è S2(1) (â).
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
39
(à) (á)
(â)
Ðèñ. 3. Ñåãìåíòàöèÿ êîíòóðîâ, ïîëó÷åííûõ ñ ïîìîùüþ ôèëüòðàöèè Äåðèøà ïðè íåêîòîðîì óðîâíå ñãëàæèâàíèÿ.
æåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé, äëèíà îïèñàíèÿ êîíòóðîâ â ðàìêàõ ýòèõ ïðåäñòàâëåíèé óìåíüøàåòñÿ ñèëüíåå, òî åñòü êîíòóðû íà èçîáðàæåíèÿõ ýòîãî òèïà îáëàäàþò áîëüøåé ðåãóëÿðíîñòüþ.
Âûâîä î òîì, ÷òî äëÿ ðåàëüíûõ èçîáðàæåíèé èñïîëüçîâàíèå â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ êðèâûõ òðåòüåé è áîëåå âûñîêèõ ñòåïåíåé ÿâëÿåòñÿ íåýôôåêòèâíûì, îòíîñèòñÿ òîëüêî ê àëãîðèòìó ñåãìåíòàöèè èçîáðàæåíèé, èñïîëüçóþùåìó ðàññìîòðåííûå âûøå ïðåäñòàâëåíèÿ. ×òîáû ðàñïðîñòðàíèòü ýòîò âûâîä íà ñòðóêòóðíûå ýëåìåíòû, ñòðîÿùèåñÿ íà îñíîâå êîíòóðîâ, ïîëó÷àåìûõ ñ ïîìîùüþ äðóãèõ àëãîðèòìîâ, áûëè îïðåäåëåíû ñðåäíèå äëèíû îïèñàíèé êîíòóðîâ, âûäåëåííûõ íà èçîáðàæåíèÿõ âûáîðêè F1 ∪ F2 ∪ F3 ñ ïîìîùüþ ôèëüòðà Äåðèøà [10] (ïðèìåð êîíòóðîâ, ïîñòðîåííûõ ñ ïîìîùüþ ýòîãî ìåòîäà, è ðåçóëüòàòû ñåãìåíòàöèè ýòèõ êîíòóðîâ ïðèâåäåíû íà ðèñ. 3). Ïðè ýòîì ïîëó÷åíû ñëåäóþùèå çíà÷åíèÿ:
LS1(2) (δG) LS0(2) (δG) = 0,833,
LS2(2) (δG) LS1(2) (δG) = 0, 798,
LS3(2) (δG) LS2(2) (δG) = 1, 008.
Òàêèì îáðàçîì, îòíîñèòåëüíûå äëèíû îïèñàíèÿ ïîëó÷èëèñü äîñòàòî÷íî áëèçêèìè äëÿ êîíòóðîâ, âûäåëåííûõ ñ ïîìîùüþ ôèëüòðà Äåðèøà è ñ ïîìîùüþ àëãîðèòìà ñåãìåíòàöèè ñ èñïîëüçîâàíèåì îïèñàííûõ âûøå ïðåäñòàâëåíèé. Îäíàêî, êàê îêàçûâàåòñÿ, ïðè ïðèìåíåíèè ôèëüòðà Äåðèøà íåñêîëüêî áîëüøåå ïðåäïî÷òåíèå îòäàåòñÿ êðèâûì âòîðîãî ïîðÿäêà, ÷òî ìîæåò áûòü îáúÿñíåíî îñîáåííîñòÿìè ïðèìåíÿåìîãî â íåì ôèëüòðà, îñóùåñòâëÿþùåãî ñãëàæèâàíèå ïåðåïàäîâ ÿðêîñòè.
Çàêëþ÷åíèå
Ïðåäëîæåííûé ïðèíöèï ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ ïîçâîëèë ïðîèçâåñòè ñðàâíåíèå íåñêîëüêèõ ïðåäñòàâëåíèé èçîáðàæå-
íèé íà âûáîðêàõ èçîáðàæåíèé ñ áîëüøîé àïðèîðíîé íåîïðåäåëåííîñòüþ.  ðåçóëüòàòå ñðàâíåíèÿ îáíàðóæåíî, ÷òî ïðåäñòàâëåíèå, ó÷èòûâàþùåå âîçìîæíîñòü ïëàâíîãî èçìåíåíèÿ ÿðêîñòè ïèêñåëîâ îáëàñòè, áîëåå ýôôåêòèâíî äëÿ èçîáðàæåíèé, ïîëó÷åííûõ âíóòðè ïîìåùåíèé.  òî æå âðåìÿ ïðåäñòàâëåíèå, â êîòîðîì ïðèâëåêàþòñÿ ôóíêöèè Ãàáîðà äëÿ îïèñàíèÿ ñîäåðæèìîãî îáëàñòåé, áîëåå ýôôåêòèâíî äëÿ àýðîêîñìè÷åñêèõ èçîáðàæåíèé.
Îáíàðóæåíà òàêæå âûñîêàÿ ýôôåêòèâíîñòü îòðåçêîâ ïðÿìûõ ëèíèé è ñåãìåíòîâ êðèâûõ âòîðîãî ïîðÿäêà â êà÷åñòâå ñòðóêòóðíûõ ýëåìåíòîâ, àïïðîêñèìèðóþùèõ êîíòóðû íà èçîáðàæåíèÿõ òðåõ ðàññìîòðåííûõ âûáîðîê. Êðèâûå áîëåå âûñîêèõ ïîðÿäêîâ îêàçûâàþòñÿ ìàëîýôôåêòèâíûìè, òî åñòü íå äîëæíû èñïîëüçîâàòüñÿ ïðè ïîñòðîåíèè èíâàðèàíòíûõ ñòðóêòóðíûõ îïèñàíèé èçîáðàæåíèé.
Òàêèì îáðàçîì, ïðèíöèï ÐÌÄÎ ìîæåò áûòü èñïîëüçîâàí äëÿ îáîñíîâàííîãî âûáîðà ïðåäñòàâëåíèé èçîáðàæåíèé.  ðàáîòå ðàññìîòðåíû íåñêîëüêî ÷àñòíûõ ïðåäñòàâëåíèé, êîòîðûå òðåáóþò äàëüíåéøåãî ñîâåðøåíñòâîâàíèÿ, ÷òî ìîæåò áûòü âûïîëíåíî â ðàìêàõ ïðåäëîæåííîãî ïîäõîäà.
ËÈÒÅÐÀÒÓÐÀ
11. Lutsiv V.R., Malyshev I.A., Pepelka V., Potapov A.S. Target independent algorithms for description and structural matching of aerospace photographs // Proc. SPIE. 2002. V. 4741. P. 351–362.
12. Ìàðð Ä. Çðåíèå. Èíôîðìàöèîííûé ïîäõîä ê èçó÷åíèþ ïðåäñòàâëåíèÿ è îáðàáîòêè çðèòåëüíûõ îáðàçîâ: Ì.: Ðàäèî è ñâÿçü, 1987. 36 ñ.
13. Ïîòàïîâ À.Ñ. Èññëåäîâàíèå ïðåäñòàâëåíèé èçîáðàæåíèé íà îñíîâå ïðèíöèïà ðåïðåçåíòàöèîííîé äëèíû îïèñàíèÿ // Èçâ. âóçîâ. Ïðèáîðîñòðîåíèå. 2008. Ò. 51. ¹ 7. Ñ. 3–7.
14. Vitanyi P.M.B., Li M. Minimum description length induction, Bayesianism, and Kolmogorov complexity // IEEE Transactions on Information Theory. 2000. V. 46. ¹ 2. P. 446–464.
40 “Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
15. Rares A., Reinders M.J.T., Hendriks E.A. Image Interpretation Systems // Technical Report (MCCWS 2.1.1.3.C), MCCWS project, Information and Communication Theory Group. TU Delft. 1999. 32 p.
16. Potapov A.S. Image matching with the use of the minimum description length approach // Proc. SPIE. 2004. V. 5426. P. 164–175.
17. Ïîòàïîâ À.Ñ. Òåîðåòèêî-èíôîðìàöèîííûé ïîäõîä ê ââåäåíèþ îáðàòíûõ ñâÿçåé â ìíîãîóðîâíåâûõ ñèñòåìàõ êîìïüþòåðíîãî çðåíèÿ // Îïòè÷åñêèé æóðíàë. Ò. 74. ¹ 10. 2007. Ñ. 59–65.
18. Ïîòàïîâ À.Ñ., Ãóðîâ È.Ï., Àâåðêèí À.Í. Àíàëèç ìîäåëè êëåòîê çðèòåëüíîé êîðû íà îñíîâå ïðèíöèïà ðåïðåçåíòàöèîííîé ìèíèìàëüíîé äëèíû îïèñàíèÿ // Èçâ. âóçîâ. Ïðèáîðîñòðîåíèå. 2008. (â ïå÷àòè).
19. Potapov A.S., Gamayunova O.S. Information criterion for constructing the hierarchical structural representations of images // Proc. SPIE. 2005. V. 5807. P. 443–454.
10. Deriche R. Optimal edge detection using recursive filtering // Proc. 1st Int. Conf. Computer Vision. 1987. P. 501–505.
“Îïòè÷åñêèé æóðíàë”, òîì 75, ¹ 11, 2008
41