Àëãîðèòì ñòåãîàíàëèçà íà îñíîâå ìåòîäà àíàëèçà èåðàðõèé Ñ.Â. Áåëèì Ä.Ý. Âèëüõîâñêèé sbelim@mail.ru vilkhovskiy@gmail.com Îìñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò èì. Ô.Ì. Äîñòîåâñêîãî, Îìñê, Ðîññèÿ Àííîòàöèÿ  ñòàòüå ïðåäëîæåí ìåòîä âûÿâëåíèÿ ñòåãàíîãðàôè÷åñêèõ âñòàâîê, ôîðìèðóåìûõ ñ ïîìîùüþ ïîäìåíû íàèìåíåå çíà÷àùåãî áèòà (LSB). Îáíàðóæåíèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ðàçáèåíèÿ èçîáðàæåíèÿ íà ñëîè è àíàëèçà îêðóæåíèÿ êàæäîãî áèòà ìëàäøåãî ñëîÿ. Àíà- ëèçèðóþòñÿ òàêæå áèòû ðàñïîëîæåííûå íàä èññëåäóåìûì áèòîì â äâóõ âûøåëåæàùèõ ñëîÿõ. Äëÿ ïðèíÿòèÿ ðåøåíèÿ î ïîäìåíå êîíêðåòíîãî áèòà èñïîëüçóåòñÿ ìåòîä àíàëèçà èåðàðõèé. Âåñîâûå êîýôôèöèåíòû â ðàìêàõ ìåòîäà àíàëèçà èåðàðõèé ôîðìèðóþòñÿ íà îñíîâå çíà÷åíèé ñàìèõ áèòîâ. Ïðîâåäåí êîìïüþòåðíûé ýêñïå- ðèìåíò ñ âñòðàèâàíèåì ñîîáùåíèÿ â îãðàíè÷åííóþ ïðÿìîóãîëüíóþ îáëàñòü èçîáðàæåíèÿ. Ïîêàçàíà âûñîêàÿ ýôôåêòèâíîñòü ïðåäëî- æåííîãî ìåòîäà. Ââåäåíèå Ñàìûì ïðîñòûì è ñàìûì ðàñïðîñòðàíåííûì ìåòîäîì âñòðàèâàíèÿ ñòåãàíîãðàôè÷åñêèõ âñòàâîê ÿâëÿåòñÿ ïîäìåíà íàèìåíåå çíà÷àùèõ áèò (LSB-çàìåùåíèå) [1]. Îñíîâíàÿ èäåÿ ìåòîäà ñîñòîèò â çàìåíå îò îäíîãî äî ÷åòûðåõ ìëàäøèõ áèò â áàéòàõ öâåòîâîãî ïðåäñòàâëåíèÿ ïèêñåëåé èçîáðàæåíèÿ. Íàèìåíåå çàìåòíîé ÿâëÿåòñÿ çàìåíà â ñèíåé ñîñòàâëÿþùåé öâåòà, ÷òî ñâÿçàíî ñ îñîáåííîñòÿìè ñâåòîâîñïðèÿòèÿ ÷åëîâå÷åñêî- ãî ãëàçà. Ýòîò ìåòîä èñïîëüçóåòñÿ êàê ñàìîñòîÿòåëüíî, òàê è â êà÷åñòâå ñîñòàâíîé ÷àñòè áîëåå ñëîæíûõ ìåòîäîâ. Íå ñìîòðÿ íà ïðîñòîòó àëãîðèòìà ôîðìèðîâàíèÿ ñòåãàíîãðàôè÷åñêîé âñòàâêè, çàäà÷à åå îáíàðó- æåíèÿ áåç äîïîëíèòåëüíîé èíôîðìàöèè ÿâëÿåòñÿ äîñòàòî÷íî ñëîæíîé. Íà ñåãîäíÿøíèé äåíü íå ñóùåñòâó- åò ìåòîäîâ, êîòîðûå ñ ïîëíîé äîñòîâåðíîñòüþ ìîãóò îïðåäåëèòü íàëè÷èå è ðàçìåðû ñòåãàíîãðàôè÷åñêîé âñòàâêè â ïðîèçâîëüíîì êîíòåéíåðå. Áîëüøèíñòâî ìåòîäîâ íîñÿò ñòàòèñòè÷åñêèé õàðàêòåð è îñíîâûâà- þòñÿ íà ïðåäïîëîæåíèè îá èçìåíåíèè ñòàòèñòè÷åñêèõ ñâîéñòâ áèòîâ èçîáðàæåíèÿ ïðè ïîìåùåíèè â íåãî âñòðîåííîé èíôîðìàöèè. Èçâåñòíûå íà ñåãîäíÿøíèé äåíü ìåòîäû ýôôåêòèâíû ïðè çàïîëíåíèè ñòåãîêîí- òåéíåðà íå ìåíåå ÷åì íà 50% [2].  ðàáîòå [3] îáíàðóæåíèå ñòåãàíîãðàôè÷åñêèõ âñòàâîê îñóùåñòâëÿåòñÿ èç ïðåäïîëîæåíèÿ îá èçìåíåíèè êîððåëÿöèé ìåæäó ñîñåäíèìè ïèêñåëÿìè. Ìåòîä, ïðåäëîæåííûé àâòîðàìè, ñîñòîèò â òîì, ÷òî ðàññìàòðèâàþòñÿ áëèæàéøèå ñîñåäè êàæäîãî ïèêñåëÿ. Èç àíàëèçà îêðóæàþùèõ ïèêñå- ëåé äåëàåòñÿ ïðîãíîç î çíà÷åíèè öåíòðàëüíîãî ïèêñåëÿ è ñðàâíèâàåòñÿ ñ åãî òåêóùèì çíà÷åíèåì.  ðàáîòå [4] ïðåäëîæåí àëãîðèòì îáíàðóæåíèÿ ñòåãàíîâñòàâîê ñ èñïîëüçîâàíèåì øàáëîíîâ äëÿ ñîñåäíèõ ïèêñåëåé. Ïîñòðîåíèå øàáëîíîâ òàêæå îñíîâûâàåòñÿ íà ïðåäïîëîæåíèè î ñèëüíîé êîððåëÿöèè ìåæäó ïèêñåëÿìè èñõîäíîãî èçîáðàæåíèÿ. Êîððåëÿöèè ìåæäó ïèêñåëÿìè òàêæå èñïîëüçîâàíû â ñòàòüå [5] äëÿ ïîñòðîåíèÿ 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 ñòàòèñòè÷åñêîãî ìåòîäà îáíàðóæåíèÿ ñòåãàíîãðàôè÷åñêèõ âñòàâîê. Àíàëîãè÷íûé ñòàòèñòè÷åñêèé ìåòîä îñíîâàííûé íà âåëè÷èíå êîððåëÿöèè ìåæäó ñîñåäíèìè ïèêñåëÿìè ïðåäëîæåí â ðàáîòå [6].  ðàáîòå [8] ïðèâîäèòñÿ îáîáùåííûé ìåòîä îïðåäåëåíèÿ äëèíû ñòåãàíîãðàôè÷åñêîé âñòàâêè íà îñíîâå îáúåäèíåíèÿ íåñêîëüêèõ äåòåêòîðîâ. Èñïîëüçîâàíèå àâòîðåãðåññèâíîé ìîäåëè äëÿ îáíàðóæåíèÿ ñêðûòûõ ñîîáùåíèé, à òàêæå îöåíêà èõ îòíîñèòåëüíîé äëèíû ïðåäëîæåíî â [7]. Òàêèì îáðàçîì, íà ñåãîäíÿøíèé äåíü îñíîâíûìè çàäà÷àìè ñòåãîàíàëèçà ñòàâèòüñÿ ïðèíöèïèàëüíîå îáíàðóæåíèå íàëè÷èÿ ñêðûòîé âñòàâêè è, ïî âîçìîæíî- ñòè, îïðåäåëåíèå åå äëèíû. Öåëüþ äàííîé ñòàòüè ñòàâèòüñÿ ðàçðàáîòêà àëãîðèòìà äëÿ ïðèíÿòèÿ ðåøåíèÿ, ÿâëÿåòñÿ ëè òîò èëè èíîé áèò ïîäìåíåííûì. Òî åñòü íå ïðîñòî îïðåäåëåíèÿ íàëè÷èÿ ñòåãàíîãðàôè÷åñêîé âñòàâêè, à, ïî âîçìîæíîñòè, åå îïðåäåëåíèå. 1 Ïîñòàíîâêà çàäà÷è Áóäåì àíàëèçèðîâàòü èçîáðàæåíèÿ, â êîòîðûõ ìîæåò áûòü âñòðîåíà èíôîðìàöèÿ â âèäå ñòåãàíîãðàôè- ÷åñêèõ âñòàâîê â ìëàäøèé áèò ñèíåé êîìïîíåíòû. Ïðè ýòîì áóäåì èñõîäèòü èç äâóõ ïðåäïîëîæåíèé. Âî- ïåðâûõ, áóäåì ñ÷èòàòü, ÷òî äîñòîâåðíî íåèçâåñòíî åñòü ëè ñòåãàíîãðàôè÷åñêàÿ âñòàâêà èëè íåò. Âî-âòîðûõ, çàðàíåå íåèçâåñòíî íè êîëè÷åñòâî âñòðîåííûõ áèòîâ, íè èõ ãåîìåòðè÷åñêîå ïîëîæåíèå íà èçîáðàæåíèè. Çàäà÷åé ñòàâèòüñÿ îïðåäåëåíèå íàëè÷èÿ ñòåãàíîãðàôè÷åñêîé âñòàâêè è îïðåäåëåíèå ìàêñèìàëüíîãî êîëè- ÷åñòâà ïèêñåëåé, â êîòîðûõ ïîäìåíåí ìëàäøèé áèò ñèíåé êîìïîíåíòû. Âòîðîå ïðåäïîëîæåíèå ñóùåñòâåííî îñëîæíÿåò çàäà÷ó, òàê êàê âîçìîæíà ñèòóàöèÿ, ïðè êîòîðîé çàìåíåíû âñå ìëàäøèå ïèêñåëè ñèíåé êîì- ïîíåíòû.  ýòîì ñëó÷àå àíàëèç íóëåâîãî ñëîÿ èçîáðàæåíèÿ íå ïðèíåñåò íèêàêîé èíôîðìàöèè. Ïðè ýòîì çàðàíåå íåèçâåñòíî ïîçâîëèò ëè àíàëèç íóëåâîãî ñëîÿ ñäåëàòü êàêèå-ëèáî âûâîäû.  ñâÿçè ñ ýòèì íåîáõî- äèì àíàëèç áîëåå âûñîêèõ ñëîåâ. Áóäåì îïèðàòüñÿ íà ïðåäïîëîæåíèå î òîì, ÷òî îñíîâíûå çàêîíîìåðíîñòè èçîáðàæåíèÿ ïëàâíî ìåíÿþòñÿ îò îäíîãî ñëîÿ ê äðóãîìó. Ïîýòîìó çàêîíîìåðíîñòè, âûÿâëåííûå â îäíîì ñëîå äîëæíû ñ âûñîêîé âåðîÿòíîñòüþ ïîâòîðÿòüñÿ â áëèçëåæàùèõ ñëîÿõ. Áóäåì èñêàòü ïèêñåëè, â êîòîðûõ ïðîèçâåäåíà ïîäìåíà íóëåâîãî áèòà îòäåëüíî àíàëèçèðóÿ íóëåâîé ñëîé è áëèæàéøèå ê íåìó òðè ñëîÿ.  äàëüíåéøåì ïîñòðîèì ñõåìó ñðàâíåíèÿ ðåçóëüòàòîâ ýòèõ äâóõ àëãîðèòìîâ è ïðèíÿòèÿ îáùåãî ðåøåíèÿ. Ïóñòü k -ûé ñëîé ñèíåé êîìïîíåíòû èñõîäíîãî èçîáðàæåíèÿ çàäàíà â âèäå áèíàðíîé ìàòðèöû öâåòîâ Bij k , à êîîðäèíàòû âñòðàèâàåìîé èíôîðìàöèè çàäàþòñÿ â âèäå ìàòðèöû Rij . Ïðè ýòîì Rij = 1 , åñëè ïðîèñõîäèò ïîäìåíà ìëàäøåãî áèòà ñèíåé êîìïîíåíòû ñîîòâåòñòâóþùåãî ïèêñåëÿ è Rij = 0 , åñëè ïîäìåíû íå ïðîèñõîäèò.  ðåçóëüòàòå âñòðàèâàíèÿ ñòåãàíîãðàôè÷åñêîé âñòàâêè âìåñòî íóëåâîãî ñëîÿ Bij 0 ñôîðìèðóåòñÿ ìàòðèöà A0ij . Çàäà÷à ñâîäèòñÿ ê ìàêñèìàëüíî òî÷íîìó âîññòàíîâëåíèþ ìàòðèöû Rij èç àíàëèçà ìàòðèö A0ij , Bij 1 , Bij 2 , Bij 3 . 2 Ïðèìåíåíèå ìåòîäà àíàëèçà èåðàðõèé äëÿ âûÿâëåíèÿ ïîäìåíåííûõ áèòîâ Ïðèìåíèì ìåòîä àíàëèçà èåðàðõèé [8] äëÿ ïðèíÿòèÿ ðåøåíèÿ î ïîäìåíå áèòà. Äëÿ ýòîãî íåîáõîäèìî ñôîð- ìóëèðîâàòü àëüòåðíàòèâíûå ðåøåíèÿ, èç êîòîðûõ îñóùåñòâëÿåòñÿ âûáîð, à òàêæå êðèòåðèè äëÿ àíàëèçà àëüòåðíàòèâ. Êàê óæå áûëî ñêàçàíî â ïîñòàíîâêå çàäà÷è íåîáõîäèìî âûÿâèòü ïèêñåëû, â êîòîðûõ ïðîèçî- øëà ïîäìåíà ìëàäøåãî áèòà. Ïîýòîìó âîçìîæíî òîëüêî îäíî èç äâóõ ðåøåíèé, îáîçíà÷àåìûõ â äàëüíåéøåì ëèáî , åñëè â äàííîì ïèêñåëå îñóùåñòâëåíà ïîäìåíà ìëàäøåãî áèòà, ëèáî , åñëè ïèêñåëü íå èçìåíÿëñÿ. Ñíà÷àëà ïîñòðîèì ñèñòåìó âûÿâëåíèÿ ïîäìåíû áèòîâ íà îñíîâå àíàëèçà íóëåâîãî ñëîÿ. Äëÿ ýòîãî îñóùå- ñòâèì ïîñëåäîâàòåëüíûé ïðîõîä ïî âñåì áèòàì íóëåâîãî ñëîÿ è îñóùåñòâèì àíàëèç áëèæàéøèõ ñîñåäåé êàæäîãî èç íèõ. Âûäåëèì òðè êðèòåðèÿ: K1 - ñîñåäíèå ïî ñòîðîíàì áèòû èìåþò òî æå çíà÷åíèå, ÷òî è àíàëèçèðóåìûé èëè îòëè÷íîå îò íåãî. K2 - ñîñåäíèå ïî óãëàì áèòû èìåþò òî æå çíà÷åíèå, ÷òî è àíàëèçèðóåìûé èëè îòëè÷íîå îò íåãî. K3 - îòêëîíåíèå çíà÷åíèÿ áèòà îò ñðåäíåãî çíà÷åíèÿ îêðóæàþùèõ âîñüìè áèòîâ. Ïåðâûå äâà êðèòåðèÿ ïîçâîëÿþò âûÿâëÿòü ïðîòÿæåííûå îáëàñòè èçîáðàæåíèÿ îäíîãî öâåòà. Òðå- òèé êðèòåðèé íåîáõîäèì äëÿ âûÿâëåíèÿ îáëàñòåé ñ ãðàäèåíòíîé çàëèâêîé. Òàêèì îáðàçîì, ïîëó÷àåì äâóõóðîâíåâîå èåðàðõè÷åñêîå äåðåâî àëüòåðíàòèâ, èçîáðàæåííîå íà ðèñóíêå 1. Äëÿ ïðèìåíåíèÿ ìåòîäà àíàëèçà èåðàðõèé íåîáõîäèìî îïðåäåëèòü îòíîñèòåëüíûå âåñà êðèòåðèåâ ri (i = 1, 2, 3), à òàêæå âåñà ðåøåíèé â ðàìêàõ îäíîãî êðèòåðèÿ pi è qi (i = 1, 2, 3). Áóäåì ñ÷èòàòü, ÷òî êðèòåðèé K1 âàæíåå êðèòåðèÿ K2 â n ðàç, à êðèòåðèé K2 âàæíåå êðèòåðèÿ K3 â k ðàç. Òàêæå áóäåì ïðåäïîëàãàòü íàëè÷èå òðàíçèòèâíîñòè, òî åñòü êðèòåðèé K1 âàæíåå êðèòåðèÿ K3 â nk ðàç. Òîãäà ñîãëàñîâàííàÿ ìàòðèöà ïàðíûõ ñðàâíåíèé áóäåò èìåòü âèä: Èç äàííîé ìàòðèöû ñòàíäàðòíûìè ñïîñîáàìè [8] ìîãóò áûòü ïîëó÷åíû âåñîâûå êîýôôèöèåíòû: r1 = nk/(nk + k + 1), r2 = k/(nk + k + 1), r3 = 1/(nk + k + 1) Ðèñ. 1: Èåðàðõèÿ êðèòåðèåâ äëÿ îïðåäåëåíèÿ ïîäìåíû áèòà èç àíàëèçà íóëåâîãî ñëîÿ. K1 K2 K3 K1 1 n kn K2 1/n 1 k K3 1/(kn) 1/k 1 Ïðè êëàññè÷åñêîì èñïîëüçîâàíèè ìåòîäà àíàëèçà èåðàðõèé ïàðíûå ñðàâíåíèÿ îïðåäåëÿþòñÿ íà îñíîâå ýêñïåðòíûõ îöåíîê.  íàøåì ïîäõîäå âìåñòî ýêñïåðòíûõ îöåíîê áóäåì èñïîëüçîâàòü íåêîòîðûå îáúåêòèâ- íûå ïîêàçàòåëè, îïðåäåëÿåìûå ÷èñëåííî.  ÷àñòíîñòè, îãðàíè÷åíèÿ íà çíà÷åíèÿ n è k ìû â äàëüíåéøåì îïðåäåëèì èç ðàññìîòðåíèÿ òðèâèàëüíûõ ïðèìåðîâ. Íàèáîëåå ïîäõîäÿùèå çíà÷åíèÿ ýòèõ ïàðàìåòðîâ íàé- äåíî èç êîìïüþòåðíîãî ýêñïåðèìåíòà. Ïåðåéäåì ê îïðåäåëåíèþ âåñîâûõ êîýôôèöèåíòîâ â ðàìêàõ êàæäî- ãî èç êðèòåðèåâ. Íà÷íåì ðàññìîòðåíèå ñ K1 . Ïóñòü èç ÷åòûðåõ áèòîâ, ñîïðèêàñàþùèõñÿ ñ èññëåäóåìûì x èìåþò òîò æå çíà÷åíèå, òîãäà ðåøåíèå N áîëåå âåñîìî ïî ñðàâíåíèþ ñ Y (òî åñòü èññëåäóåìûé áèò íå ïîäìåíåí) â x/(4 − x) ðàç. Çàïèñûâàÿ ìàòðèöó ïàðíûõ ñðàâíåíèé è ïðîèçâîäÿ íåîáõîäèìûå ïðåîáðàçîâà- íèÿ ïîëó÷àåì çíà÷åíèÿ êîýôôèöèåíòîâ â p1 = (4 − x)/4, q1 = x/4. Àíàëîãè÷íî äëÿ êðèòåðèÿ K2 . Ïóñòü èç ÷åòûðåõ áèòîâ, ñîïðèêàñàþùèõñÿ ñ äàííûì, òîëüêî ïî âåðøèíàì, èìåþò òî æå çíà÷åíèå. Òîãäà âåñî- âûå êîýôôèöèåíòû ïðèìóò çíà÷åíèÿ p2 = (4 − y)/4, q2 = y/4. Äëÿ âû÷èñëåíèÿ âåñîâûõ êîýôôèöèåíòîâ ïî êðèòåðèþ K3 ïðåäïîëîæèì, ÷òî çíà÷åíèå àíàëèçèðóåìîãî áèòà c, à ñðåäíåå çíà÷åíèå îêðóæàþùèõ åãî áèòîâ c0 . Äëÿ íàõîæäåíèÿ âåñîâûõ êîýôôèöèåíòîâ ïðèìåíèì ñëåäóþùèå ðàññóæäåíèÿ. Ïóñòü ðåøåíèå N áîëåå âåñîìî, ÷åì Y â a ðàç, ãäå âåëè÷èíà a çàâèñèò îò àáñîëþòíîãî çíà÷åíèÿ îòêëîíåíèÿ çíà÷åíèÿ áèòà c îò ñðåäíåãî çíà÷åíèÿ îêðóæàþùèõ áèòîâ c0 (dc = |c − c0 |). Òîãäà âåñîâûå êîýôôèöèåíòû áóäóò èìåòü âèä: p3 = 1/(a + 1),q3 = a/(a + 1) Ðàññìîòðèì ïðåäåëüíûå ñëó÷àè.  ñëó÷àå ðàâåíñòâà çíà÷åíèÿ èññëåäóåìîãî áèòà ñðåäíåìó çíà÷åíèþ îêðóæàþùèõ áèòîâ (dc = 0) áóäåì ñ÷èòàòü, ÷òî îí íå ïîäìåíåí, êîýôôèöèåíòû ïðè ýòîì áóäóò èìåòü çíà÷åíèå p3 = 0, p3 = 0. Åñëè áèò ìàêñèìàëüíî îòëè÷àåòñÿ îò îêðóæàþùèõ (dc = 1), òî áóäåì ñ÷èòàòü åãî îäíîçíà÷íî ïîäìåíåííûì, òî åñòü p3 = 1, q3 = 0. Ñëåäîâàòåëüíî, ïðè dc = 0 äîëæíî áûòü a → ∞. Ïðè çíà÷åíèè dc = 1 äîëæíî âûïîëíÿòüñÿ a = 0. Ýòèì óñëîâèÿì óäîâëåòâîðÿåò âûðàæåíèå: a = 1/dc − 1. Îòêóäà ñëåäóþò çíà÷åíèÿ äëÿ âåñîâûõ êîýôôèöèåíòîâ: p3 = dc, q3 = 1 − dc. Äëÿ îêîí÷àòåëüíîãî ïðèíÿòèÿ ðåøåíèÿ íåîáõîäèìî âû÷èñëèòü âåëè÷èíû: P (Y ) = r1 p1 + r2 p2 + r3 p3 , P (N ) = r1 q1 + r2 q2 + r3 q3 Åñëè P (Y ) > P (N ), òî ïðèíèìàåòñÿ ðåøåíèå R = Y , òî åñòü áèò ÿâëÿåòñÿ ïîäìåíåííûì, â ïðîòèâíîì ñëó÷àå, ïðè P (Y ) ≤ P (N ), ïðèíèìàåòñÿ ðåøåíèå R = N , òî åñòü áèò íå ÿâëÿåòñÿ ïîäìåíåííûì. Ðàñøèðèì ïðåäëîæåííûé ìåòîä íà àíàëèç áèòà íà îñíîâå ñðàâíåíèÿ ñ òðåìÿ âûøåëåæàùèìè ñëîÿìè. Áóäåì â êàæäîì ñëîå ðàññìàòðèâàòü áèò, ëåæàùèé íàä äàííûì, è âîñåìü åãî áëèæàéøèõ ñîñåäåé.  äàëüíåéøåì ýòîò íàáîð áèòîâ áóäåì íàçûâàòü îêíîì â ñîîòâåòñòâóþùåì ñëîå. Ââåäåì êðèòåðèè ïðèíÿòèÿ ðåøåíèé íà îñíîâå àíàëèçà k -ãî ñëîÿ (k = 1, 2, 3): K1 k - ñîñåäíèå ïî ñòîðîíàì áèòû â îêíå 1-ãî ñëîÿ èìåþò òî æå çíà÷åíèå, ÷òî è àíàëèçèðóåìûé áèò íóëåâîãî ñëîÿ èëè îòëè÷íîå îò íåãî. K2 k - ñîñåäíèå ïî óãëàì áèòû â îêíå 2-ãî ñëîÿ èìåþò òî æå çíà÷åíèå, ÷òî è àíàëèçèðóåìûé áèò íóëåâîãî ñëîÿ èëè îòëè÷íîå îò íåãî. K3 k - îòêëîíåíèå çíà÷åíèÿ áèòà â íóëåâîì ñëîå îò ñðåäíåãî çíà÷åíèÿ áèòîâ îêíà â 3-îì ñëîå. Òðåõóðîâ- íåâîå èåðàðõè÷åñêîå äåðåâî àëüòåðíàòèâ, èçîáðàæåíî íà ðèñóíêå 2. Îêîí÷àòåëüíîå ðåøåíèå îáîçíà÷èì R1 . Áóäåì ñ÷èòàòü, ÷òî ðåçóëüòàòû àíàëèçà ïåðâîãî ñëîÿ âàæíåå ðåçóëüòàòîâ âòîðîãî â äâà ðàçà, è âòîðîé ñëîé âàæíåå òðåòüåãî òàêæå â äâà ðàçà. Îòñþäà ïîëó÷àåì çíà÷åíèÿ âåñîâûõ êîýôôèöèåíòîâ: t1 = 4/7, Ðèñ. 2: Èåðàðõèÿ êðèòåðèåâ äëÿ îïðåäåëåíèÿ ïîäìåíû áèòà èç àíàëèçà âûøåëåæàùèõ ñëîåâ t2 = 2/7, t3 = 1/7.  ðàìêàõ îäíîãî ñëîÿ òðóäíî âûäåëèòü êàêîé-òî èç êðèòåðèåâ, ïîýòîìó ïîëîæèì, ÷òî âñå îíè ðàâíî- çíà÷íû: s1 = s2 = s3 = 1/3. Äëÿ âåñîâûõ êîýôôèöèåíòîâ äëÿ äâóõ ðåøåíèé â ðàìêàõ îäíîãî êðèòåðèÿ ïðèìåíèì ïîäõîä àíàëîãè÷- íûé èñïîëüçîâàííîìó ïðè àíàëèçå íóëåâîãî ñëîÿ. Äëÿ ïåðâîãî êðèòåðèÿ: p1 k = (4 − xk )/4, q1 k = (xk )/4, ãäå xk - êîëè÷åñòâî ñîñåäåé ïî áîêàì, èìåþùèõ òî æå çíà÷åíèå â îêíå -ñëîÿ. Äëÿ âòîðîãî êðèòåðèÿ: p2 k = (4 − y k )/4, q2 k = y k /4, ãäå y k - êîëè÷åñòâî ñîñåäåé ïî äèàãîíàëè, èìåþùèõ òî æå çíà÷åíèå â îêíå -ñëîÿ. Âåñîâûå êîýôôèöèåíòû òðåòüåãî êðèòåðèÿ: p3 k = dck , q3 k = 1 − dck , ãäå dck - îòëè÷èå çíà÷åíèÿ áèòà îò ñðåäíåãî çíà÷åíèÿ áèòîâ îêíà â k -ì ñëîå. Äëÿ ïðèíÿòèÿ ðåøåíèÿ íåîáõîäèìî âû÷èñëèòü âåëè÷èíû: P1 (Y ) = t1 (s1 p1 1 + s2 p2 1 + s3 p3 1 ) + t2 (s1 p1 2 + s2 p2 2 +s3 p3 2 )+t3 (s1 p1 3 +s2 p2 3 +s3 p3 3 ), P1 (N ) = t1 (s1 q1 1 +s2 q2 1 +s3 q3 1 )+t2 (s1 q1 2 +s2 q2 2 +s3 q3 2 )+t3 (s1 q1 3 + s2 q2 3 + s3 q3 3 ) Åñëè P1 (Y ) > P1 (N ), òî ïðèíèìàåòñÿ ðåøåíèå R1 = Y , òî åñòü áèò ÿâëÿåòñÿ ïîäìåíåííûì, â ïðîòèâíîì ñëó÷àå, ïðè P1 (Y ) ≤ P1 (N ), ïðèíèìàåòñÿ ðåøåíèå R1 = N , òî åñòü áèò íå ÿâëÿåòñÿ ïîäìåíåííûì. 3 Àëãîðèòì âûÿâëåíèÿ ïîäìåíåííûõ ïèêñåëåé Çàïèøåì ôîðìàëüíî àëãîðèòì, ðåàëèçóþùèé ïðåäëîæåííûé ìåòîä. Îñóùåñòâëÿåì ïîñëåäîâàòåëüíûé ïðî- õîä ïî âñåì ïèêñåëÿì èçîáðàæåíèÿ. Äëÿ êàæäîãî ïèêñåëÿ âûïîëíÿåì ïîñëåäîâàòåëüíîñòü øàãîâ: Øàã 1. Âûäåëÿåì îêíà ðàçìåðîì 3 × 3 â íóëåâîì, ïåðâîì, âòîðîì è òðåòüåì ñëîÿõ. Øàã 2. Âû÷èñëÿåì âåëè÷èíû P (Y ), P (N ), P1 (Y ), P2 (N ). Øàã 3. Åñëè âûïîëíÿåòñÿ õîòÿ áû îäíî èç äâóõ ðàâåíñòâ R = Y èëè R1 = Y , òî áèò ñ÷èòàåòñÿ ïîä- ìåíåííûì. Çàíîñèì â ñîîòâåòñòâóþùèé ýëåìåíò ìàòðèöû Ri j åäèíè÷íîå çíà÷åíèå, â ïðîòèâíîì ñëó÷àå íóëåâîå. Íà âûõîäå àëãîðèòìà áóäåò ïîëó÷åíà ìàòðèöà ïîäìåíåííûõ ïèêñåëåé Rij . Òàê êàê â àëãîðèòìå îñó- ùåñòâëÿåòñÿ îäèí ïðîõîä ïî âñåì ïèêñåëÿì è äëÿ êàæäîãî ïèêñåëÿ âûïîëíÿåòñÿ ôèêñèðîâàííîå êîëè÷å- ñòâî øàãîâ, òî òðóäîåìêîñòü àëãîðèòìà áóäåò ëèíåéíîé. Òàêæå ñëåäóåò îòìåòèòü ëîêàëèçàöèþ äàííûõ, íåîáõîäèìûõ äëÿ ïðèíÿòèÿ ðåøåíèÿ, â ìàëîé îáëàñòè âîêðóã èññëåäóåìîãî ïèêñåëÿ, ÷òî ïîçâîëÿåò ëåãêî ïðîèçâîäèòü ðàñïàðàëëåëèâàíèå àëãîðèòìà ïðîñòûì ðàçáèåíèåì èçîáðàæåíèÿ íà îáëàñòè. 4 Êîìïüþòåðíûé ýêñïåðèìåíò è ðåçóëüòàòû Äëÿ èññëåäîâàíèÿ ýôôåêòèâíîñòè ïðåäëîæåííîãî ìåòîäà áûë ïðîâåäåí êîìïüþòåðíûé ýêñïåðèìåíò ïî âûÿâëåíèþ âñòðîåííîé èíôîðìàöèè. Èññëåäîâàíèÿ ïðîâîäèëèñü íà òðåõ òèïàõ èçîáðàæåíèé: ãðàäèåíòíîé çàëèâêå, èñêóññòâåííîì èçîáðàæåíèè ãåîìåòðè÷åñêèõ ôèãóð è øèðîêî èñïîëüçóåìîì èçîáðàæåíèè "Lena". Âñå èçîáðàæåíèÿ èìåëè ðàçìåð 256×256 ïèêñåëåé, ãëóáèíà öâåòà ñîñòàâëÿëà 256 öâåòîâ. Âñòðàèâàëñÿ òåêñò íà ðóññêîì ÿçûêå â âèäå ïîáèòîâîé ïîñëåäîâàòåëüíîñòè â ïðÿìîóãîëüíóþ îáëàñòü ðàñïîëîæåííóþ ñëó÷àé- íûì îáðàçîì â öåíòðå èçîáðàæåíèÿ. Ïîìåíÿëîñü 9% èñõîäíîãî íóëåâîãî ñëîÿ. Íà ðèñóíêå 3 ïðåäñòàâëåíû ðåçóëüòàòû ýêñïåðèìåíòà ñ ãðàäèåíòíîé çàëèâêîé. Êàê õîðîøî âèäíî èç ñðàâíåíèÿ ðèñóíêîâ 3á è 3ã ÿâíî âèäåí ïðÿìîóãîëüíèê, â êîòîðûé ïðîèçâîäèëîñü âñòðàèâàíèå. Àíàëîãè÷íûå ðåçóëüòàòû äëÿ èñêóññòâåííîãî èçîáðàæåíèÿ ñ ãåîìåòðè÷åñêèìè ôèãóðàìè ïðè- âåäåíî íà ðèñóíêå 4 è äëÿ ôîòîãðàôè÷åñêîãî èçîáðàæåíèÿ íà ðèñóíêå 5. Íà îáîèõ ðèñóíêàõ ÿâíî âèäíà îáëàñòü, â êîòîðóþ âñòðàèâàëîñü ñêðûâàåìîå ñîîáùåíèå. (a) (b) (c) (d) Ðèñ. 3: Ðåçóëüòàò ðàáîòû àëãîðèòìà ïî âûÿâëåíèþ ïîäìåíåííûõ ïèêñåëåé íà ãðàäèåíòíîé çàëèâêå: a) èñõîäíîå èçîáðàæåíèå, b) ìàòðèöà äëÿ èñõîäíîãî èçîáðàæåíèÿ, c) èçîáðàæåíèå ñ âñòðîåííûì ñîîáùåíèåì, d) ìàòðèöà äëÿ èçîáðàæåíèÿ ñî ñòåãàíîâñòàâêîé. 5 Îáñóæäåíèå ðåçóëüòàòîâ è âûâîäû Òàêèì îáðàçîì, ïðåäëîæåííûé â äàííîé ñòàòüå àëãîðèòì ïîçâîëÿåò íå òîëüêî âûÿâëÿòü íàëè÷èå ñòåãà- íîãðàôè÷åñêîé âñòàâêè â èçîáðàæåíèÿ, íî è ñ äîñòàòî÷íî âûñîêîé òî÷íîñòüþ îïðåäåëÿòü åå ìåñòîíàõîæ- äåíèå è îáúåì.  îòëè÷èå îò ðàñïðîñòðàíåííûõ íà äàííûé ìîìåíò àëãîðèòìîâ â ïðåäëîæåííîì ìåòîäå íå èñïîëüçóåòñÿ ñòàòèñòè÷åñêèé ïîäõîä. Ñëåäóåò îòìåòèòü, ÷òî èññëåäîâàííûå â ðàìêàõ êîìïüþòåðíîãî ýêñïåðèìåíòà èçîáðàæåíèÿ ñî ñòåãàíîãðàôè÷åñêîé âñòàâêîé ëåãêî ïðîõîäÿò òåñò Õè-êâàäðàò, êîòîðûé íå îáíàðóæèâàåò â íèõ âñòðîåííûõ ñîîáùåíèé. Äàííûé ìåòîä òðåáóåò äîïîëíèòåëüíûõ èññëåäîâàíèé, äëÿ ðàçðàáîòêè àëãîðèòìîâ àíàëèçà ïîëó÷åííîé ìàòðèöû. Ñïèñîê ëèòåðàòóðû [1] E. Adelson. Digital Signal Encoding and Decoding Apparatus. U.S. Patent. 1990, N. 4,939,515. [2] A. Westfeld,A. Ptzmann. Attacks on Steganographic Systems. Breaking the Steganographic Utilities EzStego, Jsteg, Steganos and S-Tools and Some Lessons Learned. Lecture Notes in Computer Science, 1768:6175, 2000. [3] J. Zhang,F. Xiong. Steganalysis for LSB Matching Based on the Dependences Between Neighboring Pixels. Journal of multimedia, V.7,N.5:380385, 2012. [4] D. Lerch-Hostalot,D. Meg?as. LSB Matching Steganalysis Based on Patterns of Pixel Dierences and Random Embedding. Computers and Security, V.32:192206, 2013. [5] Zh. Xia,X. Wang,X. Sun,B. Wang Steganalysis of least signicant bit matching using multi-order dierences. Security and Communication Networks, V.7,N.8:12831291, 2014. (a) (b) Ðèñ. 4: Ðåçóëüòàò ðàáîòû àëãîðèòìà ïî âûÿâëåíèþ ñòåãàíîãðàôè÷åñêîé âñòàâêè íà èñêóññòâåííîì èçîáðà- æåíèè ñ ãåîìåòðè÷åñêèìè ôèãóðàìè: a) èçîáðàæåíèå ñ âñòðîåííûì ñîîáùåíèåì, b) ìàòðèöà äëÿ èçîáðà- æåíèÿ ñî ñòåãàíîâñòàâêîé. (a) (b) Ðèñ. 5: Ðåçóëüòàò ðàáîòû àëãîðèòìà ïî âûÿâëåíèþ ñòåãàíîãðàôè÷åñêîé âñòàâêè íà ôîòîãðàôè÷åñêîì èçîá- ðàæåíèè: a) èçîáðàæåíèå ñ âñòðîåííûì ñîîáùåíèåì, b) ìàòðèöà äëÿ èçîáðàæåíèÿ ñî ñòåãàíîâñòàâêîé.. [6] Q. Guan,J. Dong,T. Tan An eective image steganalysis method based on neighborhood information of pixels. 18th IEEE International Conference on Image Processing, 27772780, 2011. [7] D. Andrew,A. Ker. General Framework for Structural Steganalysis of LSB Replacement. M. Barni et al. (Eds.), LNCS.3727:296311, 2005. [8] S. Bhattacharyya,G. Sanya. Steganalysis of LSB Image Steganography using Multiple Regression and Auto Regressive (AR) Model. Int. J. Comp. Tech. Appl, V.2(4):10691077, 2011. [9] T. Saaty,G. Sanya. Relative Measurement and its Generalization in Decision Making: Why Pairwise Comparisons are Central in Mathematics for the Measurement of Intangible Factors - The Analytic Hierarchy/Network Process. Review of the Royal Spanish Academy of Sciences, Series A, Mathematics, V.102 (2):251318, 2008. Steganalysis Algorithm Based on Hierarchy Analysis Method Sergey V. Belim, Danil E. Vilkhovskiy This article presents a new method of image analysis with steganographic inserts based on hierarchy analysis method. Images with applied algorithm of replacing the least signicant bit (LSB) are investigated. Detection is performed by dividing the image into layers and making an analysis of zero-layer of adjacent bits for every bit. First-layer and second-layer are analyzed too. Hierarchies analysis method is used for making decision if current bit is changed. Weighting coecients as part of the analytic hierarchy process are formed on the values of bits. Then a matrix of corrupted pixels is generated. Visualization of matrix with corrupted pixels allows to determine size, location and presence of the embedded message. Computer experiment was performed. Message was embedded in a bounded rectangular area of the image. This method demonstrated eciency even at low lling container, less than 10. Widespread statistical methods are unable to detect this steganographic insert. The location and size of the embedded message can be determined with an error which is not exceeding to ve pixels.