Algorytm Zhao & Koch

Pora na przedstawienie algorytmu ukrywania danych, który będzie odporny na kompresję JPEG. Zdecydowałem się na algorytm przedstawiony przez Jian Zhao i Eckhard Koch’a w 1996 roku. Jest on już trochę leciwy, ale posiada dobre wyniki odporności na kompresję.

Algorytm operuje w przestrzeni częstotliwościowej obrazu, więc nie zmieniamy poszczególnych pikseli. Do przejścia w przestrzeń częstotliwościową wykorzystywana jest transformata kosinusowa.

DCT

Dyskretna transformata kosinusowa (ang. discrete cosine transform) jest jedną z najpopularniejszych blokowych transformacji danych. DCT przekształca skończony ciąg N liczb f(0), f(1),…,f(N-1), w ciąg liczb rzeczywistych F(0), F(1),…,F(N-1) zgodnie z następującymi zależnościami:

Definiuję się również odwrotną transformatę kosinusową

Podczas kompresji danych używana jest dwuwymiarowa transformata kosinusowa zadana wzorem:

oraz przy dekompresja odwrotna:

Odwrotna dwuwymiarowa transformata kosinusowa

W algorytmie zaproponowanym przez Jian Zhao i Eckhard Koch’a również zostały zastosowane elementy algorytmu kompresji JPEG. Autorzy zauważyli, że skwantyzowane współczynniki DCT mają umiarkowany poziom wariancji w środkowym zakresie częstotliwości. Niewielkie zmiany w tych współczynnikach, nie powinny być zauważalne dla oka ludzkiego. Dlatego do wstawienia znaku wodnego należy wybrać trzy współczynniki ze środkowego zakresu. Po spełnieniu odpowiednich zależności pomiędzy tymi elementami będzie możliwość umieszczenia wiadomości w obrazie.

Relacje pomiędzy trzema współczynnikami tworzą 9 kombinacji (wzorów), które zostały podzielone na trzy grupy: dwie do zakodowania „1” lub „0” oraz jednej nieprawidłowej. Jeśli potrzebne są zbyt duże modyfikacje, aby zakodować bit (w taki sposób zmienić współczynniki, by pasowały do poprawnego wzoru) wtedy blok jest nieprawidłowy. W takim przypadku trzy współczynniki należy zmodyfikować do niepoprawnego wzoru, aby blok został pominięty przy odczytywaniu wiadomości. Kryterium wyboru prawidłowego bloku jest parametr MD(ang. maximum difference), czyli maksymalna różnica pomiędzy dwoma wybranymi elementami.

W powyższym obrazie znajdują się możliwe pozycje współczynników transformaty kosinusowej dla bloku 8×8. Zostały one statystycznie wybrane przez autorów algorytmu. Tak jak to zostało wspomniane wcześniej, do zakodowania wiadomości należy użyć trzech współczynników. Możliwe kombinacje tych trzech elementów znajdują się w tabeli poniżej.

Nr wzoru	(k1,l1)	(k2,l2)	(k3,l3)
1	2(0,2)	9(1,1)	10(1,2)
2	9(1,1)	2(0,2)	10(1,2)
3	3(0,3)	10(1,2)	11(1,3)
4	10(1,2)	3(0,3)	11(1,3)
5	9(1,1)	2(0,2)	10(1,2)
6	2(0,2)	9(1,1)	10(1,2)
7	9(1,1)	16(2,0)	2(0,2)
8	16(2,0)	9(1,1)	2(0,2)
9	2(0,2)	9(1,1)	16(2,0)
10	9(1,1)	2(0,2)	16(2,0)
11	10(1,2)	17(2,1)	3(0,3)
12	17(2,1)	10(1,2)	3(0,3)
13	10(1,2)	3(0,3)	17(2,1)
14	3(0,3)	10(1,2)	17(2,1)
15	9(1,1)	16(2,0)	17(2,1)
16	16(2,0)	9(1,1)	17(2,1)
17	10(1,2)	17(2,1)	18(2,2)
18	17(2,1)	10(1,2)	18(2,2)

Natomiast poniżej zostały przedstawione możliwe wzory trzech wybranych współczynników.

	(k1,l1)	(k2,l2)	(k3,l3)
Wzór do zakodowanie „1”	H	M	L
	M	H	L
	H	H	L
Wzór do zakodowanie „0”	M	L	H
	L	M	H
	L	L	H
Nieprawidłowy wzór	H	L	M
	L	H	M
	M	M	M

Do dostosowania widoczności i odporności znaku, służą dwa parametry: MD oraz d. Parametr MD został omówiony wyżej. Natomiast parametr d definiowany jest, jako moc wstawienia wiadomości do obrazu. W rzeczywistości, jest to odległość pomiędzy dwoma wybranymi współczynnikami transformaty. Jego domyślna wartość to 1. Im wyższy parametr d, tym wstawiony znak będzie odporniejszy na modyfikacje, jednak należy się liczyć z większą widocznością i podatnością na ataki.

W poniższych algorytmach przyjąłem następujące oznaczenie:

Yq(k, l)– skwantyzowane współczynniki transformaty bloku

Sprawdzenie możliwości zapisu

wybierz pozycję współczynników (k1,l1),(k2,l2),(k3,l3)
Yq(k1,l1)=dct(k1,l1), Yq(k2,l2)=dct(k2,l2), Yq(k3,l3)=dct(k3,l3)
If bit=1
   if MIN(|Yq(k1,l1)|,|Yq(k2,l2)|)+MD<|Yq(k3,l3)| then
      zmodyfikuj blok do niepoprawnego wzoru
      wstaw zmodyfikowane współczynniki do bloku 
   else
      blok jest prawidłowy
   end if
else
   if MAX(|Yq(k1,l1)|,|Yq(k2,l2)|)>|Yq(k3,l3)|+MD then
      zmodyfikuj blok do niepoprawnego wzoru
      wstaw zmodyfikowane współczynniki do bloku 
   else
      blok jest prawidłowy
   end if
end if

Sprawdzanie możliwości odczytu

wybierz pozycję współczynników (k1,l1),(k2,l2),(k3,l3)
Yq(k1,l1)=dct(k1,l1), Yq(k2,l2)=dct(k2,l2), Yq(k3,l3)=dct(k3,l3)
Sprawdz czy Yq(k1,l1),Yq(k2,l2),Yq(k3,l3) są poprawnym wzorem

Wstawianie znaku

wybierz pozycję współczynników (k1,l1),(k2,l2),(k3,l3)
Yq(k1,l1)=dct(k1,l1), Yq(k2,l2)=dct(k2,l2), Yq(k3,l3)=dct(k3,l3)
if m=1 then
   zmodyfikuj Yq(k1,l1),Yq(k2,l2),Yq(k2,l2) aby spełniały zależności:
   Yq(k1,l1)>Yq(k3,l3)+d
   Yq(k2,l2)>Yq(k3,l3)+d
else
   zmodyfikuj Yq(k1,l1),Yq(k2,l2),Yq(k2,l2) aby spełniały zależności:
   Yq(k1,l1)+d<Yq(k3,l3)
   Yq(k2,l2)+d<Yq(k3,l3)
end if
wstaw zmodyfikowane współczynniki do bloku

Odczytywanie znaku

wybierz pozycję współczynników (k1,l1),(k2,l2),(k3,l3)
Yq(k1,l1)=dct(k1,l1), Yq(k2,l2)=dct(k2,l2), Yq(k3,l3)=dct(k3,l3)
If Yq(k1,l1)>Yq(k3,l3)+d and Yq(k2,l2)>Yq(k3,l3)+d then
   m=1
else if Yq(k1,l1)+d<Yq(k3,l3) and Yq(k2,l2)+d<Yq(k3,l3) then
   m=0
end if

Do pracy!

Koniec tej teorii 🙂 czas zabierać się za implementację! Pisania kodu trochę będzie, ale to dobrze bo od ponad tygodnia nic w StegoCore nie dodawałem. Poznałem na czym opiera się kompresja JPEG i jak można ją wykorzystać do ukrycia danych. Algorytm Zhao & Koch nie wydaje się trudny i z samego pseudokodu można odnieść wrażenie że powinien działać. Wszystko jednak wyjdzie w testach, ale jestem dobrej myśli 🙂

Paweł Skaruz