=Paper=
{{Paper
|id=Vol-1732/paper2
|storemode=property
|title=
Алгоритм поиска
импульсного шума на
изображении
(Algorithm of an Impulse Noise Detection on an Image)
|pdfUrl=https://ceur-ws.org/Vol-1732/paper2.pdf
|volume=Vol-1732
|authors=Sergey Belim,Stanislav Larionov
}}
==
Алгоритм поиска
импульсного шума на
изображении
(Algorithm of an Impulse Noise Detection on an Image)
==
https://ceur-ws.org/Vol-1732/paper2.pdf
Àëãîðèòì ïîèñêà èìïóëüñíîãî øóìà íà èçîáðàæåíèè
Ñ.Â. Áåëèì Ñ.Á. Ëàðèîíîâ
belimsv@omsu.ru me@stas-larionov.ru
Îìñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò èì. Ô.Ì. Äîñòîåâñêîãî, Îìñê, Ðîññèÿ
Àííîòàöèÿ
 ñòàòüå ïðåäëîæåí àëãîðèòì âûÿâëåíèÿ èìïóëüñíîãî øóìà. Èçîá-
ðàæåíèå ïðåäñòàâëÿåòñÿ â âèäå ãðàôà. Íà ãðàôå èùóòñÿ ñîîáùå-
ñòâà. Ñîîáùåñòâà, ñîñòîÿùèå èç îäíîãî ïèêñåëÿ ñ÷èòàþòñÿ ïîâðå-
æäåííûìè. Ïðîâåäåí êîìïüþòåðíûé ýêñïåðèìåíò. Àëãîðèòì ïîêà-
çàë âûñîêóþ ýôôåêòèâíîñòü.
Ââåäåíèå
Ïîèñê íà èçîáðàæåíèèè ïèêñåëåé, ïîâðåæäåííûõ èìïóëüñíûì øóìîì, ìîæíî îòíåñòè ê çàäà÷àì îáó÷åíèÿ
áåç ó÷èòåëÿ. Îñíîâíîé ïîäõîä, èñïîëüçóåìûé â ïîäàâëÿþùåì êîëè÷åñòâå àëãîðèòìîâ, ñîñòîèò â àíàëèçå
ñêîëüçÿùåãî îêíà [1, 2]. Ïîä ñêîëüçÿùèì îêíîì ïîíèìàåòñÿ íåêîòîðàÿ ëîêàëüíàÿ îáëàñòü èçîáðàæåíèÿ ïî-
ñëåäîâàòåëüíî ïðîõîäÿùàÿ âñå ïèêñåëè. Èç ñðàâíåíèÿ õàðàêòåðèñòèê öåíòðàëüíîãî ïèêñåëÿ îêíà ñ îñòàëü-
íûìè ïèêñåëÿìè îêíà äåëàåòñÿ âûâîä î åãî ïîâðåæäåíèè. Îòëè÷èå ìåòîäîâ äåòåêòèðîâàíèÿ ïîâðåæäåííûõ
ïèêñåëåé äðóã îò äðóãà ñîñòîèò â âûáîðå ðàçìåðîâ ñêîëüçÿùåãî îêíà è àëãîðèòìà ïðèíÿòèÿ ðåøåíèÿ î
ïîâðåæäåíèè ïèêñåëÿ [3, 4, 5]. Òàêèå àëãîðèòìû ðàáîòàþò äîñòàòî÷íî áûñòðî, òàê êàê èìåþò ëèíåéíóþ
òðóäîåìêîñòü ïî êîëè÷åñòâó ïèêñåëåé èçîáðàæåíèÿ. Îäíàêî ýôôåêòèâíîñòü ïîèñêà ïîâðåæäåííûõ ïèê-
ñåëåé ñóùåñòâåííî çàâèñèò îò ïîëüçîâàòåëüñêèõ íàñòðîåê. Íàïðèìåð, àëãîðèòì SD-ROM [1], ëåæàùèé â
îñíîâå áîëüøîãî êîëè÷åñòâà äðóãèõ àëãîðèòìîâ, ñîäåðæèò ÷åòûðå ïàðàìåòðà, âûáèðàåìûõ ïîëüçîâàòåëåì.
Âàðüèðîâàíèå äàííûõ ïàðàìåòðîâ ìîæåò ìåíÿòü ýôôåêòèâíîñòü ïîèñêà ïîâðåæäåííûõ ïèêñåëåé îò 62%
äî 96%. Ïðè ýòîì îñòàåòñÿ âûñîêèì ïðîöåíò ëîæíûõ ñðàáàòûâàíèé.
Óëó÷øåíèå ðåçóëüòàòîâ óäàåòñÿ äîáèòñÿ íà îñíîâå àëãîðèòìîâ, àíàëèçèðóþùèõ íå òîëüêî íåáîëüøóþ
ëîêàëüíóþ îáëàñòü, íî è âñå èçîáðàæåíèå â öåëîì.  êà÷åñòâå òàêèõ ìîæíî îòìåòèòü àëãîðèòìû íà îñíîâå
àññîöèàòèâíûõ ïðàâèë [6, 7], ìåòîäàõ ïîääåðæêè ïðèíÿòèÿ ðåøåíèé [8], à òàêæå îñíîâàííûå íà ìåòîäàõ
ñåãìåíòàöèè èçîáðàæåíèé [9, 10]. Âî âñåõ ïåðå÷èñëåííûõ àëãîðèòìàõ îäèí èëè äâà íàñòðàèâàåìûõ ïà-
ðàìåòðà è äîñòàòî÷íî âûñîêàÿ ýôôåêòèâíîñòü îáíàðóæåíèÿ ïîâðåæäåííûõ ïèêñåëåé. Ïðè ýòîì óäàåòñÿ
ñóùåñòâåííî ñíèçèòü ïðîöåíò ëîæíûõ ñðàáàòûâàíèé. Ñëåäóåò îòìåòèòü, ÷òî ïåðå÷èñëåííûå àëãîðèòìû
îáëàäàþò íå ëèíåéíîé, à êâàäðàòè÷íîé òðóäîåìêîñòüþ.
Öåëüþ äàííîé ñòàòüè ÿâëÿåòñÿ ðàçðàáîòêà àëãîðèòìà âûäåëåíèÿ ïîâðåæäåííûõ ïèêñåëåé íà îñíîâå
ãðàôîâîãî ïðåäñòàâëåíèÿ èçîáðàæåíèÿ ñ ïîñëåäóþùåé åãî êëàñòåðèçàöèåé.
Èç ìåòîäîâ íà ñåãìåíòàöèè èçîáðàæåíèé ìîæíî îòìåòèòü ïðåäñòàâëåíèå èçîáðàæåíèÿ íà îñíîâå âçâå-
øåííîãî ãðàôà ñ ïîñëåäóþùèì âûäåëåíèåì ñîîáùåñòâ (community) íà äàííîì ãðàôå [11, 12, 13]. Âûäåëåíèå
ñîîáùåñòâ â áîëüøèíñòâå ñëó÷àåâ ðåàëèçóåòñÿ íà îñíîâå âûðàùèâàíèÿ îáëàñòåé íà èñõîäíîì èçîáðàæåíèè.
Äàííûé ïîäõîä èìåååò êâàäðàòè÷íóþ òðóäîåìêîñòü. Ïîâðåæäåííûå ïèêñåëè âûäåëÿþòñÿ êàê ñåãìåíòû, ñî-
ñòîÿùèå èç îäíîé òî÷êè.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: Sergey V. Belim, Nadezda F. Bogachenko (eds.): Proceedings of the Workshop on Data Analysis and Modelling (DAM 2016),
Omsk, Russia, October 2016, published at http://ceur-ws.org
1 Ïîñòàíîâêà çàäà÷è è àëãîðèòì ðåøåíèÿ
Èìïóëüñíîãîû øóì íà èçîáðàæåíèÿõ ïðîÿâëÿåòñÿ êàê îòäåëüíûå ñëó÷àéíî ðàñïîëîæåííûå ïèêñåëè ñëó-
÷àéíîãî öâåòà. Ïðè ýòîì èíôîðìàöèÿ î ïðåæíåì çíà÷åíèè ïèêñåëÿ ñòàíîâèòñÿ óòåðÿííîé. Îáîçíà÷èì
îòíîøåíèå êîëè÷åñòâà èçìåíåííûõ ïèêñåëåé ê îáùåìó êîëè÷åñòâó ïèêñåëåé èçîáðàæåíèÿ ÷åðåç p è áóäåì
íàçûâàòü ïðîöåíòîì çàøóìëåíèÿ.
Íà âõîäå àëãîðèòìà èìååì èçîáðàæåíèå ðàçìåðîì N ×M ïèêñåëåé, íà êîòîðîì ïðèñóòñòâóåò èìïóëüñíûé
øóì.
Ïîëîæåíèå ïèêñåëÿ íà èçîáðàæåíèè ìîæåò áûòü çàäàíî äâóìÿ êîîðäèíàòàìè (x, y), ãäå x ïðèíèìàåò
öåëûå çíà÷åíèÿ íà îòðåçêå [0, N − 1], y ïðèíèìàåò öåëûå çíà÷åíèÿ íà îòðåçêå [0, M − 1]. Äëÿ öâåòíûõ
èçîáðàæåíèé êàæäîìó ïèêñåëþ ñ êîîðäèíàòàìè (x, y) ñîîòâåòñòâóåò òðè öâåòîâûå ñîñòàâëÿþùèå: r(x, y)
êðàñíûé öâåò, g(x, y) çåëåíûé öâåò, b(x, y) ñèíèé öâåò.
Ïðåäñòàâèì èçîáðàæåíèå â âèäå íåîðèåíòèðîâàííîãî âçâåøåííîãî ãðàôà G. Âåðøèíàìè ãðàôà áóäóò
ñëóæèòü ïèêñåëè èçîîáðàæåíèÿ. Ðåáðàìè ñîåäèíèì òîëüêî âåðøèíû, ñîîòâåòñòâóþùèå áëèæàéøèì ñîñåä-
íèì ïèêñåëÿì íà èçîáðàæåíèè. Âåñ ðåáðà áóäåò îïðåäåëÿòüñÿ îòëè÷èåì öâåòîâûõ ñîñòàâëÿþùèõ êîíöîâ
ðåáðà. Êàê ïîêàçàíî â ñòàòüå [14] íàèëó÷øèå ðåçóëüòàòû ìîãóò áûòü ïîëó÷åíû ïðè èñïîëüçîâàíèè ýêñ-
ïîíåíöèàëüíîé ôóíêöèè. Âåñ ðåáðà, ñîåäèíÿþùåãî âåðøèíû vi = (xi , yi ) è vj = (xj , yj ), îïðåäåëèì â
ñëåäóþùåì âèäå:
1
q
d(vi , vj ) = exp(− (ri − rj )2 + (gi − gj )2 + (bi − bj )2 ).
h
Çäåñü ri = r(vi , vj ), gi = g(vi , vj ), bi = b(vi , vj ). Ïàðàìåòð h îïðåäåëÿåò çíà÷åíèå ðàçíîñòè öâåòîâûõ ñîñòàâ-
ëÿþùèõ, äåòåêòèðóåìîå êàê ïåðåõîä ê ñîñåäíåìó ñåãìåíòó. Äàííûé ïàðàìåòð îïðåäåëÿåòñÿ ïîëüçîâàòåëåì
è ÿâëÿåòñÿ îáùèì äëÿ âñåãî èçîáðàæåíèÿ.
Âûäåëåíèå èñïîð÷åííûõ ïèêñåëåé áóäåì îñóùåñòâëÿòü íà îñíîâå àëãîðèòìà ñåãìåíòàöèè èçîáðàæåíèÿ.
Ïðè ñåãìåíòàöèè âñå ïèêñåëè ðàçáèâàþòñÿ íà ãðóïïû ñõîæèõ ýëåìåíòîâ.  êà÷åñòâå ìåðû ñõîæåñòè âû-
áèðàåòñÿ ¾öâåòîâîå ðàññòîÿíèå¿ ìåæäó ïèêñåëÿìè d(vi , vj ). Â ðåçóëüòàòå ñåãìåíòàöèè çàøóìëåííîãî èçîá-
ðàæåíèÿ íåêîòîðûå ñåãìåíòû áóäóò ñîñòîÿòü èç îäíîé òî÷êè. Ñ âûñîêîé âåðîÿòíîñòüþ â êà÷åñòâå îä-
íîïèêñåëüíûõ ñåãìåíòîâ áóäóò âûäåëåíû èìïóëüñíûå øóìû. Îäíàêî ñòîèò îòìåòèòü, ÷òî áîëüøèíñòâî
ôîòîãðàôè÷åñêèõ èçîáðàæåíèé ñîäåðæèò ýëåìåíòû, êîòîðûå â îòñóòñòâèå øóìîâ òàêæå îïðåäåëÿþòñÿ,
êàê îäíîïèêñåëüíûå êëàñòåðû. Íàëè÷èå òàêèõ ýëåìåíòîâ áóäåò ïðèâîäèòü ê ëîæíûì ñðàáàòûâàíèÿì.
Ïðè ïðåäñòàâëåíèè èçîáðàæåíèÿ â âèäå ãðàôà ñåãìåíòàöèÿ ýêâèâàëåíòíà êëàñòåðèçàöèè ãðàôà G. Ãðàô
G ðàçáèâàåòñÿ íà ïîäãðàôû, ðàññòîÿíèÿ ìåæäó âåðøèíàìè êîòîðûõ çíà÷èòåëüíî ìåíüøå, ÷åì ñ îñòàëüíû-
ìè âåðøèíàìè. Òàêèå ïîäãðàôû îáðàçóþò ñîîáùåñòâà (community). Äëÿ êîëè÷åñòâåííîé îöåíêè ðàçáèåíèÿ
ãðàôà íà ñîîáùåñòâà èñïîëüçóåòñÿ ôóíêöèÿ ìîäóëüíîñòè Íüþìàíà [15, 16].
Äëÿ âû÷èñëåíèÿ ôóíêöèè ìîäóëüíîñòè íåîáõîäèìî äëÿ ãðàôà G çàäàòü ìàòðèöó âåñîâ E . Äèàãîíàëüíûå
ýëåìåíòû ìàòðèöû âåñîâ Eii ïîêàçûâàþò âåñ i-îé âåðøèí. Íà íà÷àëüíîì ýòàïå âåñ âñåõ âåðøèí íóëåâîé.
Íåäèàãîíàëüíûå ýëåìåíòû Eij (i 6= j ) èìåþò âåñ, ðàâíûé öâåòîâîìó ðàññòîÿíèþ ìåæäó ïèêñåëÿìè, ñî-
îòâåòñòâóþùèì âåðøèíàì vi è vj . Ìàòðèöà E áóäåò ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, òàê
êàê ó ðåáåð íåò îðèåíòàöèè. Äëÿ âû÷èñëåíèÿ ôóíêöèè ìîäóëüíîñòè ââåäåì ïðèâåäåííóþ ìàòðèöó âåñîâ
e = E/m, ãäå
M
X N
m= Eij .
i,j=1
 ïðèâåäåííîé ìàòðèöå âåñîâ ýëåìåíò eij ïîêàçûâàåò äîëþ âåñà çàäàííîãî ðåáðà â îáùåì âåñå ãðàôà. Â
äàëüíåéøåì áóäåì ðàññìàòðèâàòü òîëüêî ïðèâåäåííûé âèä ìàòðèöû âåñîâ. Î÷åâèäíî, ÷òî
M
X N
eij = 1.
i,j=1
Âåëè÷èíà ìîäóëüíîñòè îïðåäåëÿåòñÿ âûðàæåíèåì [15, 16]:
K
X K
X
Q(G) = eij − ai bi .
i=1 i=1
PK
ãäå K êîëè÷åñòâî âåðøèí ãðàôà, ai ïðèâåäåííàÿ èñõîäÿùàÿ ñòåïåíü âåðøèíû vi (ai = j=1,j6=i eij ),
PK
bi ïðèâåäåííàÿ âõîäÿùàÿ ñòåïåíü âåðøèíû vi (bi = j=1,j6=i eji ). Òàê êàê ãðàô G íåîðèåíòèðîâàííûé,
âõîäÿùàÿ è èñõîäÿùàÿ ñòåïåíü äëÿ âñåõ âåðøèí îäèíàêîâû (ai = bi ; i = 1, ..., K ). Ôóíêöèÿ ìîäóëüíîñòè
ïðèíèìàåò âèä:
K
X K
X
Q(G) = eij − a2i .
i=1 i=1
Äëÿ âûÿâëåíèÿ ñîîáùåñòâ íà ãðàôå áóäåì èñïîëüçîâàòü ïðîöåäóðó îáðàçîâàíèÿ ñòÿæåê. Ïîä ñòÿæêîé
ïîíèìàåòñÿ ïðåîáðàçîâàíèå, ïðè êîòîðîì íåêîòîðûé ïîäãðàô H ãðàôà G çàìåíÿåòñÿ îäíîé âåðøèíîé vH .
Åñëè êàêàÿ-òî èç âåðøèí ïîäãðàôà H áûëà ñâÿçàíà ðåáðîì ñ âåðøèíîé v èç ïîäãðàôà G\H , òî âåðøèíà vH
òàêæå áóäåò ñâÿçàíà ðåáðîì òîãî æå âåñà ñ âåðøèíîé v . Âåñ íîâîé âåðøèíû áóäåò ðàâåí ñóììå âåñîâ ðåáåð
è âåðøèí, âõîäÿùèõ â ïîäãðàô H . Íîâûé ãðàô îáîçíà÷èì GH . Ïîäãðàô H áóäåì ñ÷èòàòü ñîîáùåñòâîì,
åñëè Q(GH ) > Q(G). Ñëåäóåò îòìåòèòü, ÷òî ïðè îáðàçîâàíèè ñòÿæêè óìåíüøàåòñÿ ÷èñëî âåðøèí ãðàôà
K . Íàøåé çàäà÷åé ñòîèò ïîèñê âåðøèí ãðàôà, íå âõîäÿùèõ íè â îäíî áîëåå êðóïíîå ñîîáùåñòâî.
Áóäåì íàõîäèòü ñîîáùåñòâà ìåòîäîì âûðàùèâàíèÿ îáëàñòåé.
1. Âûáèðàåì ïðîèçâîëüíûé ïèêñåëü èçîáðàæåíèÿ v , íå âõîäÿùèé íè â îäíî ñîîáùåñòâî.
2. Äëÿ âûáðàííîãî ïèêñåëÿ v ïîî÷åðåäíî ðàññìàòðèâàåì áëèæàéøèå ñîñåäíèå ïèêñåëè v (i) (i = 1, ..., 8) è
ïûòàåìñÿ îáúåäèíèòü èõ â ñîîáùåñòâî. Ïðè êàæäîì îáúåäèíåíèè âû÷èñëÿåì èçìåíåíèå ôóíêöèè ìîäóëü-
íîñòè ∆Qi (i = 1, ..., 8).
3. Åñëè îáúåäèíåíèå äàííîé âåðøèíû â ñîîáùåñòâî ñ äðóãèìè ïèêñåëÿìè íå âûãîäíî (∆Qi < 0, i =
1, ..., 8), òî ñîîòâåòñòâóþùèé ïèêñåëü îòíîñèì ê ïîâðåæäåííûì. Èíà÷å ñòðîèì ñîîáùåñòâî
Íà âûõîäå àëãîðèòìà ïîëó÷èì ñïèñîê ïèêñåëåé, îáðàçóþùèõ ñîîáùåñòâà èç îäíîãî ýëåìåíòà. Ñ áîëüøîé
âåðîÿòíîñòüþ äàííûå ïèêñåëè ÿâëÿþòñÿ èñêîìûìè.
Èçìåíåíèå ôóíêöèè ìîäóëüíîñòè ìîæåò áûòü âû÷èñëÿíî äîñòàòî÷íî áûñòðî íà îñíîâå òåêóùèõ õàðàê-
òåðèñòèê ãðàôà. Ïðè îáúåäèíåíèè âåðøèí vi è vj èçìåíåíèå ìîäóëüíîñòè áóäåò ðàâíî:
∆Q = 2(eij − ai aj ).
Î÷åâèäíî, ÷òî ïðåäëîæåííûé àëãîðèòì èìååò êâàäðàòè÷íóþ òðóäîåìêîñòü îò ÷èñëà ïèêñåëåé.
2 Êîìïüþòåðíûé ýêñïåðèìåíò
 êîìïüþòåðíîì ýêñïåðèìåíòå îáðàáàòûâàëèñü è èñêóññòâåííûå èçîáðàæåíèÿ è ôîòîãðàôè÷åñêèå ôàéëû
ðàçìåðîì N = 512, M = 512 ïèêñåëåé. Êîîðäèíàòû è öâåò pN M òî÷åê, ìîäåëèðóþùèõ èìïóëüñíûé
øóì ãåíåðèðîâàëèñü ñ ïîìîùüþ ëèíåéíîãî êîíãðóýíòíîãî ãåíåðàòîðà ñ ðàâíîìåðíûì ðàñïðåäåëåíèåì.
Ýêñïåðèìåíòû ïðîâîäèëèñü ñ óðîâåíåì øóìà îò 0% äî 70%. Äëÿ êàæäîãî íàáîðà ïàðàìåòðîâ è êàæäîãî
èçîáðàæåíèÿ ïðîâîäèëîñü ïî 100 íåçàâèñèìûõ ýêñïåðèìåíòîâ.
 êàæäîì ýêñïåðèìåíòå ãåíåðèðîâàëèñü pN M êîîðäèíàò è öâåòîâ ïèêñåëåé. Ïîñëå ýòîãî îñóùåñòâëÿëîñü
âûÿâëåíèå ïîâðåæäåííûõ ïèêñåëåé. Ðåçóëüòàòû ñðàâíèâàëèñü ñî ñãåíåðèðîâàííûìè äàííûìè. Äëÿ îöåíêè
êà÷åñòâà ðàáîòû àëãîðèòìà èñïîëüçîâàëèñü äâå âåëè÷èíû. Ýôôåêòèâíîñòü ðàáîòû àëãîðèòìà:
N0
ef f = ,
pN M
ãäå N0 êîëè÷åñòâî âåðíî èäåíòèôèöèðîâàííûõ èñïîð÷åííûõ ïèêñåëåé. Óðîâåíü ëîæíûõ ñðàáàòûâàíèé:
Ne
err = ,
N
ãäå Ne êîëè÷åñòâî îøèáî÷íî èäåíòèôèöèðîâàííûõ èñïîð÷åííûõ ïèêñåëåé, N îáùåå êîëè÷åñòâî ïèêñå-
ëåé îïðåäåëåííîå àëãîðèòìîì, êàê èñïîð÷åííûå.
Äëÿ èçîáðàæåíèÿ, ïðåäñòàâëÿþùåãî ñîáîé îáëàñòü ðàâíîìåðíîé çàëèâêè îäíèì öâåòîì ýôôåêòèâíîñòü
ðàáîòû àëãîðèòìà ïðè p = 10% ñîñòàâëÿåò ef f = 99.98% ïðè ïðîöåíòå ëîæíûõ ñðàáàòûâàíèé err = 0.11%.
Ýôôåêòèâíîñòü íèæå ñòà ïðîöåíòîâ, òàê êàê ïðè ñëó÷àéíîì âûáîðå öâåòà èñïîð÷åííîãî ïèêñåëÿ íåíóëåâàÿ
âåðîÿòíîñòü ñîâïàäåíèÿ åãî ñ öâåòîì çàëèâêè. Ýôôåêòèâíîñòü ðàáîòû àëãîðèòìà îñòàåòñÿ âûñîêîé âïëîòü
äî áîëüøèõ çíà÷åíèé óðîâíÿ øóìà. Òàê ïðè p = 70% ýôôåêòèâíîñòü ðàâíà ef f = 99.97% ïðè ïðîöåíòå
ëîæíûõ ñðàáàòûâàíèé err = 6.20%. Ðîñò ïðîöåíòà ëîæíûõ ñðàáàòûâàíèé ñâÿçàí ñ òåì, ÷òî ïðè âûñîêîì
óðîâíå øóìà èñïîð÷åííûå ïèêñåëè äîñòàòî÷íî ÷àñòî îêàçûâàþòñÿ áëèæàéøèìè ñîñåäÿìè.
Àíàëîãè÷íûå ýêñïåðèìåíòû äëÿ èñêóññòâåííûõ èçîáðàæåíèé ïðàâèëüíûõ ãåîìåòðè÷åñêèõ ôèãóð ñ ÷åò-
êèìè ãðàíèöàìè è ïðèñóòñòâèåì îáëàñòåé ãðàäèåíòíîé çàëèâêè ïðè ñ óðîâíåì øóìà îò p = 10% äî p = 70%
ïîêàçàëè ýôôåêòèâíîñòü îò ef f = 99.97% äî ef f = 99.95%. Ïðîöåíò ëîæíûõ ñðàáàòûâàíèé, ïðè ýòîì, òàê-
æå ñíèæàëñÿ îò err = 7.81% äî err = 4.15%. Îñíîâíîé âêëàä â âåëè÷èíó ïðîöåíòà ëîæíûõ ñðàáàòûâàíèé
âíîñèëè ÷åòêèå ãðàíèöû, ðàçäåëÿþùèå îáëàñòè èçîáðàæåíèÿ.
Ýêñïåðèìåíòû íà ôîòîãðàôè÷åñêèõ èçîáðàæåíèÿõ ïîêàçàëè, ÷òî ýôôåêòèâíîñòü âûÿâëåíèÿ ïîâðåæäåí-
íûõ ïèêñåëåé îñòàåòñÿ äîñòàòî÷íî âûñîêîé è ìåäëåííî óáûâàåò ñ ðîñòîì óðîâíÿ øóìà. Äàæå äëÿ ïðîöåí-
òà çàøóìëåíèÿ p = 50% ýôôåêòèâíîñòü ef f = 83.85%. Çíà÷åíèå ïðîöåíòà ëîæíûõ ñðàáàòûâàíèé òàêæå
óáûâàåò, ÷òî ñâÿçàíî ñ åãî îòíîñèòåëüíûì õàðàêòåðîì. Ïî àáñîëþòíîé âåëè÷èíå êîëè÷åñòâî îøèáî÷íî
îïðåäåëåííûõ ïèêñåëåé îñòàåòñÿ ïðàêòè÷åñêè íà îäíîì óðîâíå.
3 Àíàëèç ðåçóëüòàòîâ è âûâîäû
Ïðåäëîæåííûé ìåòîä âûÿâëåíèÿ ïèêñåëåé, ïîâðåæäåííûõ èìïóëüñíûì øóìîì, îáëàäàåò äîñòàòî÷íî âû-
ñîêîé ýôôåêòèâíîñòüþ äàæå äëÿ ñèëüíî çàøóìëåííûõ èçîáðàæåíèé. Ïðè÷åì êîëè÷åñòâî ïèêñåëåé, îøè-
áî÷íî îòíåñåííûõ ê ïîâðåæäåííûì, ðàñòåò î÷åíü ìåäëåííî ñ óâåëè÷åíèåì çàøóìëåíèÿ, ÷òî ïðèâîäèò ê
óìåíüøåíèþ óðîâíÿ ëîæíûõ ñðàáàòûâàíèé. Ïðîâåäåì ñðàâíåíèå ñ ðåçóëüòàòàìè äðóãèõ ðàáîò. Íàèáîëåå
ðàñïðîñòðàíåííûé àëãîðèòì SD-ROM ïîçâîëÿåò îáíàðóæèâàòü èñïîð÷åííûå ïèêñåëè â ñðåäíåì ñ ýôôåê-
òèâíîñòüþ 71% è óðîâíå ëîæíûõ ñðàáàòûâàíèÿ 5% ïðè èíòåíñèâíîñòè øóìà 10% [1]. Ýòîò æå ìåòîä ìîæåò
äåìîíñòðèðîâàòü ýôôåêòèâíîñòü äî 96% ïðè óðîâíå çàøóìëåíèÿ 30%, íî íà øóìàõ òèïà ¾ñîëü è ïåðåö¿.
Ñëåäóåò îòìåòèòü, ÷òî çàäà÷à àíàëèçà èçîáðàæåíèé ñ øóìîì ¾ñîëü è ïåðåö¿ ÿâëÿåòñÿ áîëåå ïðîñòîé, òàê
êàê â íèõ èíòåíñèâíîñòü öâåòà èñïîð÷åííûõ ïèêñåëåé èìååò ëèáî ìàêñèìàëüíîå, ëèáî ìèíèìàëüíîå çíà÷å-
íèå. Ïðè÷åì äîñòèæåíèå ìàêñèìàëüíîé ýôôåêòèâíîñòè âîçìîæíî ëèøü ïðè îïðåäåëåííîì íàáîðå ÷åòûðåõ
ïàðàìåòðîâ, ïîäáèðàåìûõ âðó÷íóþ. Ïðè óâåëè÷åíèè óðîâíÿ øóìà óðîâåíü ëîæíûõ ñðàáàòûâàíèé â àë-
ãîðèòìå SD-ROM ðàñòåò î÷åíü áûñòðî è óæå ïðè èíòåíñèâíîñòè øóìà 30% äîñòèãàåò 73%. Àíàëîãè÷íûå
àëãîðèòìû, îñíîâàííûå íà àíàëèçå ëîêàëüíîãî îêðóæåíèÿ êàæäîãî ïèêñåëÿ, äåìîíñòðèðóþò áëèçêèå ðå-
çóëüòàòû. Òàê ìåòîä, èñïîëüçóþùèé ïîñòðîåíèå àññîöèàòèâíûõ ïðàâèë äëÿ íàáîðîâ ñîñåäíèõ ïèêñåëåé,
ïðè èíòåíñèâíîñòè øóìà 30%, ïîêàçûâàåò ýôôåêòèâíîñòü 77% è óðîâåíü ëîæíûõ ñðàáàòûâàíèé 35% [6, 7].
Àëãîðèòì, îñíîâàííûé íà ìåòîäå àíàëèçà èåðàðõèé ïîçâîëÿåò îáíàðóæèâàòü èìïóëüñíûé øóì ñ ýôôåê-
òèâíîñòüþ 85% è ëîæíûìè ñðàáàòûâàíèÿìè 55% [8]. Ñóùåñòâåííûì íåäîñòàòêîì äàííûõ ìåòîäîâ ÿâëÿåòñÿ
àíàëèç äîñòàòî÷íî íåáîëüøîé îáëàñòè èçîáðàæåíèÿ âîêðóã êàæäîãî ïèêñåëÿ, êîòîðûé íå ïîçâîëÿåò âûÿâ-
ëÿòü è àíàëèçèðîâàòü ïðîòÿæåííûå îáëàñòè íà èçîáðàæåíèè. ×àñòè÷íî äàííûé íåäîñòàòîê áûë óñòðàíåí
â ìåòîäå âûÿâëåíèÿ èìïóëüñíîãî øóìà, îñíîâàííîì íà êëàñòåðèçàöèè èçîáðàæåíèé [9, 10], äëÿ êîòîðî-
ãî ýôôåêòèâíîñòü îáíàðóæåíèÿ èñïîð÷åííûõ ïèêñåëåé 82%, à óðîâåíü ëîæíûõ ñðàáàòûâàíèé 23% ïðè
çàøóìëåíèè íà 10%. Ïðè óâåëè÷åíèè ïðîöåíòà èñïîð÷åííûõ ïèêñåëåé ýôôåêòèâíîñòü ïàäàåò è ïðè 30%
çàøóìëåíèÿ ñîñòàâëÿåò 68%, à óðîâåíü ëîæíûõ ñðàáàòûâàíèé 11%.
Òàêèì îáðàçîì, ïðåäëîæåííûé â äàííîé ñòàòüå àëãîðèòì ïîçâîëÿåò ïîëó÷àòü çàìåòíûé âûèãðûø êàê
â ýôôåêòèâíîñòè îáíàðóæåíèÿ èñïîð÷åííûõ ïèêñåëåé, òàê è â óðîâíå ëîæíûõ ñðàáàòûâàíèé ïðè çíà÷è-
òåëüíîì çàøóìëåíèè èçîáðàæåíèÿ, âûøå 30%.
Ñïèñîê ëèòåðàòóðû
[1] Abreu E., Lightstone M., Mitra S.K., Arakawa S.K. A new e cient approach for the removal of impulse noise
from highly corrupted images. IEEE Transactions on Image Processing, IEEE Transactions on. 5:10121025,
1996.
[2] Garnett R., Huegerich T., Chui C., He W. A Universal Noise Removal Algorithm with an Impulse Detector.
IEEE Trans Image Proccess. 14(11):17471754, 2005.
[3] Sorokin S.V., Shherbakov M.A. Realizacija SD-ROM l'tra na osnove koncepcii nechetkoj logiki. (The SD-
ROM lter implementation based on the fuzzy logic concept.) Izvestija vysshih uchebnyh zavedenij. Povolzhskij
region. 3:5665, 2007.
[4] Krasovskij G.Ja., Uss M.L. Fil'tracija izobrazhenij, iskazhennyh impul'snymi pomehami tochechnogo i
strochnogo tipa, na osnove sistem iterirovanyh funkcij. (Filtration of broken by string and dotted impulse
images based on system of itereated functions.) Radioelektronni i kompjuterni sistemi. 2:4755, 2003.
[5] Chan R., Ho C., Nikolova M. Salt-and-pepper noise removal by median-type noise detectors and detail-
preserving regularization. IEEE Trans. Image Proc. 14(10):14791485, 2005.
[6] Belim S.V., Majorov-Zil'bernagel' A.O. Algoritm poiska povrezhdennyh pikselej i udalenija impul'snogo
shuma na izobrazhenijah s ispol'zovaniem metoda associativnyh pravil. (The algorithm of broken pixel
detection and impulse noize removal based on associative rules.) Nauka i obrazovanie: jelektronnoe nauchno-
tehnicheskoe izdanie. 12, 2014, URL: http://technomag.bmstu.ru/doc/744983.html
[7] Belim S.V., Majorov-Zil'bernagel' A.O. Vosstanovlenie izobrazhenij so staticheskimi propuskami na osnove
metoda associativnyh pravil. (Recovering of images with static gaps based on the method of associative rules.)
Vestnik komp'juternyh i informacionnyh tehnologij. 12:1823, 2014.
[8] Belim S.V., Seliverstov S.A. Ispol'zovanie metoda analiza ierarxij dlya vyyavleniya impul'snogo shuma v
gra cheskix ob"ektax. (Using of hierarchy analysis method for impulse noize recognizing in graphical objects.)
Informacionnye texnologii. 4:251258, 2015.
[9] Belim S.V., Kutlunin P.E. Vyyavlenie povrezhdennyx pikselej na izobrazhenii s pomoshh'yu algoritma
klasterizacii (Broken pixels detection in images based on the clusterization algorithm.) Vestnik komp'yuternyx
i informacionnyx texnologij. 3:310, 2016.
[10] Belim S.V., Kutlunin P.E. Boundary extraction in images using a clustering algorithm. Computer optics.
39(1):119124, 2015.
[11] Pourian P., Karthikeyan S., Manjunath B.S. Weakly supervised graph based semantic segmentation by
learning communities of image-parts. The IEEE International Con-ference on Computer Vision (ICCV).
13591367, 2015.
[12] Nair R.S., Vineetha K.V. Modularity Based Color Image Segmentation. IJIREEICE. 3(1):109113, 2016.
[13] Mourchid Y., Hassouni M.E., Cherif H.A. New Image Segmentation Approach using Community
Detection Algo-rithms. International Journal of Computer Information Systems and Industrial Management
Applications. 8:195204, 2016.
[14] Browet A., Absil P.-A., Van Dooren P. Community Detection for Hierarchical Image Segmentation. IWCIA.
LNCS 6636:358371, 2011.
[15] Newman M. E. Analysis of weighted networks. Physical Review E. 70(5):056131, 2004.
[16] Clauset A., Newman M. E. J., Moore C. Finding community structure in very large networks. Physical
Review E. 70(6):066111, 2004.
Algorithm of an Impulse Noise Detection on an Image
Sergey V. Belim, Stanislav B. Larionov
In article the algorithm of of an impulse noise detection is suggested. The image is presented as a graph.
On the graph communities are looked for. Communities from one point are read by the defective pixels. The
computer experiment is made. The algorithm shows high eectiveness.