DPCM (ang. Differential Pulse-Code Modulation) – metoda kompresji stratnej przeznaczona głównie dla sygnałów dźwiękowych. Normalny algorytm wykorzystuje predykcję kolejnych wartości sygnałów i koduje jedynie różnice pomiędzy wartością szacowaną a rzeczywistą. My zajmiemy się jego uproszczonymi wersjami, kodującymi zmiany pomiędzy kolejnymi wartościami, zamiast samych wartości. Zmiany te zwykle są mniej dynamiczne niż same wartości sygnału. Schemat kodowania został zaprezentowany na poniższym schemacie.

Na początku wyjaśnijmy oznaczenia:

• X - sygnał wejściowy,
• Y' - różnica do zakodowania,
• Y - zakodowana wartość,
• E - estymanta/wartość, jaka zostanie odkodowana.

DPCM bez predykcji

Jeżeli potrzebujecie jakieś wcześniejsze wartości początkowe (np. krok -1) zakładamy, że będą one równe \(0\) W każdym kroku algorytmu (dopóki mamy nowe próbki sygnału) będziemy odejmować od bieżącej wartości X wartość estymowaną E, otrzymując w ten sposób wstępną wartość różnicy Y'. Następnie na wartości Y' dokonujemy kwantyzacji (na przykład do wartości 8-bitowej), otrzymując naszą zakodowaną różnicę Y. Następnie dodajemy ją do naszej wartości estymowanej E w celu jej odświeżenia.

Dekompresja odbywa się w podobny sposób. Tu również zakładamy, że X'[0]==Y[0]. Następnie dla każdej kolejnej zakodowanej różnicy dodajemy wartość naszego odtworzonego sygnału z poprzedniego kroku. Należy jednak pamiętać, że nasz sygnał nie jest już zapisany na pierwotnym rozmiarze danych, nie tym po kwantyzacji!!!

Przedstawmy teraz kilka przypadków:

Zakładamy, że chcemy zakodować ciąg \(X=[15,16,20,14,5,10,15,13,11,7,10,11,20,1,23]\). Załóżmy, że zmienna ta będzie zapisana w typie int8 i będziemy stosować dla niej kwantyzacji do konkretniej ilości bitów (7 i 6), przy użyciu naszej standardowej funkcji do kwantyzacji. Poniżej dwa przykłady jak wartości jakie generuje zasza fukcja.:

• Wartości oryginalne: \(X=[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\)
• Wartości po kwantyzacji do 7 bitów: \(X_7=[-9, -9, -7, -7, -5, -5, -3, -3, -1, -1, 0, 0, 2, 2, 4, 4, 6, 6, 8, 8, 10]\)
• Wartości po kwantyzacji do 6 bitów: \(X_6=[-10, -10, -6, -6, -6, -6, -2, -2, -2, -2, 1, 1, 1, 1, 5, 5, 5, 5, 9, 9, 9]\)

W pierwszym przypadku wykorzystamy funkcję do 7-bitów. Zacznijmy od dwóch pierwszych wartości. Kodujemy wartość \(15\), ponieważ w kroku zerowym nasze \(e=0\) nasza różnica będzie wynosić \(Y'=15\). Po kwantyzacji otrzymamy \(Y=K_7(15)=14\), za pomocą tego odświeżymy naszą estymowaną wartość na wyjściu: \(e=X'=Y+e=16+0=16\). Przejdźmy do kodowania kolejnej wartości \(16\). Zaczynamy od wyliczenia różnicy \(Y'=16-14=2\), czyli po kwantyzacji również będziemy mieć \(Y=K_7(2)=2\). Teraz odświeżamy naszą wartość estymowaną \(e=2+16=16\). Reszta kroków została przedstawiona w tabeli.

Po całym kodowaniu dostajemy na wyjściu zakodowany łańcuch \(Y=[ 14 , 2, 4, -5, -9 , 4 , 4 , -1 ,-1 , -5 , 2 , 2 , 8, -17, 20]\). Teraz zabieramy się dekodowanie tego łańcucha. Zaczynamy od wartości \(14\), ponieważ nie było kroku -1-go zakładamy, że poprzednia wartość \(X'\) miała wartość \(0\), więc \(X'\) w tym kroku będzie wynosić \(X'=14+0=14\). Kolejna wartość to \(2\), więc nowa wartość to \(X'=2+14=16\). Kontynuacja obliczeń w tabeli.

Na wyjściu otrzymaliśmy, więc wektor \(X'=[14, 16, 20, 15, 6, 10, 14, 13, 12, 7, 9, 11, 19, 2, 22]\), który jest zbliżony wartościami do \(X=[15,16,20,14,5,10,15,13,11,7,10,11,20,1,23]\).

DPCM z predykcją

Trochę bardziej zaawansowana wersja DPCM zawiera predykcję, czyli wnioskowanie nie tylko na podstawie różnicy i poprzedniego elementu, ale również kilku poprzednich. Istnieją różnego rodzaju mniej lub bardziej zaawansowane predykatory. Najprostszy, jaki będziemy wykorzystywać to średnia ostatnich \(n\) elementów. Czyli zamiast odejmować ostatni estymant będziemy odejmować średnią np. 3 ostatnich sedymentów.

Ogólnie algorytm dla wyliczenia pojedynczego przejścia składa się z kilku kroków:

• Pobieramy wartość do zakodowania \(X_i\)
• Wyliczamy naszą wartość do zakodowania, czyli odejmujemy oczekiwaną wartość z poprzedniego kroku \(E_{i-1}\), więc wykonujemy równanie \(Y_{i}'=X_i-E_{i-1}\)
• Dokonujemy kwantyzacji, czyli dostajemy na wyjście naszej kompresji, czyli \(Y\)
• Wyliczamy wartość, jaką otrzymamy na wyjściu naszego dekodera \(X_i'=Y_i+E_{i-1}\)
• Dokonujemy predykcji na podstawie naszych danych, czyli ostatnich \(n\) wartości \(X_i'\), - przykładowo licząc z nich średnią albo stosując algorytm predykcji liniowej.

Teraz przejdźmy do przykładów. Zaczniemy od naszego przypadku \(X=[15,16,20,14,5,10,15,13,11,7,10,11,20,1,23]\) i predyktorem średnią z 3 elementów, a wartości będziemy poddawać kwantyzacji do7-bitów. Poniżej przykład bez rzutowania wartości estymowanej na liczbę całkowitą. Dalej również ten sam przykład, ale z zaokrągleniem.

Inne metody predykcji

1. Średnia geometryczna (scipy.stats.mstats.gmean) - może wymagać obudowania własną funkcją
2. Średnia harmoniczna (scipy.stats.mstats.hmean) - może wymagać obudowania własną funkcją
3. Mediana
4. Predykcja liniowa \[\begin{aligned} p=1\qquad:&\qquad\hat{x}(n)=1x(n-1)\\ p=2\qquad:&\qquad\hat{x}(n)=2x(n-1)-1x(n-2)\\ p=3\qquad:&\qquad\hat{x}(n)=3x(n-1)-3x(n-2)+1x(n-3)\\ p=4\qquad:&\qquad\hat{x}(n)=4x(n-1)-6x(n-2)+4x(n-3)-1x(n-4)\\ \end{aligned}\]
5. Regresja liniowa

Przykładowy kod

1. DPCM bez predykcji

   def DPCM_compress(x,bit):
       y=np.zeros(x.shape)
       e=0
       for i in range(0,x.shape[0]):
           y[i]=kwant(x[i]-e,bit)
           e+=y[i]
       return y

2. DPCM z predykcją

   def DPCM_compress(x,bit,predictor,n): 
       y=np.zeros(x.shape)
       xp=np.zeros(x.shape)
       e=0
       for i in range(0,x.shape[0]):
           y[i]=kwant(x[i]-e,bit)
           xp[i]=y[i]+e
           idx=(np.arange(i-n,i,1,dtype=int)+1)
           idx=np.delete(idx,idx<0)
           e=predictor(xp[idx])
       return y

3. Predyktor bez predykcji:

   def no_pred(X):
       return X[-1]

Jak testować?

Jeżeli chodzi o testowanie to błędy najłatwiej zaobserwować na fragmencie sinusa:

x=np.linspace(-1,1,1000)
y=0.9*np.sin(np.pi*x*4)