最近在做RDOQ算法優化和硬體系統結構設計,建立其時序模型,估算算法的硬體複雜度。在做這部分工作的同時,部落客學習了圖像的二維變換與離散餘弦變換(DCT),總結如下:
1. 圖像的二維離散變換
與一維的有限長離散非周期信号存在傅裡葉變換(DFT)一樣,圖像作為一個二維離散信号同樣存在着二維離散變換(注意這裡是介紹一個通用的概念,二維離散變換,包括了DFT、DCT等多種變換在内的一種通式寫法),其通式可以表達為
1.1 二維變換的可分性與對稱性
如果一個二維變換核同時具備可分性與對稱性,此時允許用兩個一維變換來計算二維變換,即首先沿着輸入的行(列)進行一維變換,接着用第一步得到的結果再對列(行)進行一維變換。當變換對的正反變換都滿足這個條件時,且 f(x,y)f(x,y) 是大小為 M×MM×M 的方形圖像時,式(2.6-30)和式(2.6-31)可表示為矩陣形式
T=AFAT
其中 FF 矩陣是包含元素 f(x,y)f(x,y) 的 的M×M的M×M 矩陣,AA 矩陣是有元素 ai,j=r1(i,j)ai,j=r1(i,j) 的 M×MM×M 矩陣,TT 是 M×MM×M 變換的結果,其值為 T(u,v),u,v=0,1,…,M−1T(u,v),u,v=0,1,…,M−1,其中的 AA 矩陣并不是所說的基函數或者基圖像,而由r(x,y,u,v)r(x,y,u,v) 構成的圖像才是基圖像。具體什麼事基函數,如何獲得基圖像将在下面說明。
1.2 為什麼二維變換可以用矩陣表示
首先回顧一下什麼樣的圖像可以使用 T=AFATT=AFAT 來進行表示,要求二維變換核同時具備可分性與對稱性且圖像是正方形的圖。當滿足上述條件式,一個二維變換可以用兩個一維變換計算,即首先變換圖像的每一列再變換圖像的每一行。對每一列進行變換就是用矩陣乘以圖像的每一列,有線性代數知識可知 :XF=X[f1,f2,f3,…,fn],其中的F是圖像矩陣,而 f1,…fnf1,…fn 是圖像矩陣中的每一列。
1.3 二維離散餘弦變換
正變換
反變換
由上可知當 M=NM=N的時候,DCT變換可以表示為矩陣相乘的形式,其中T=AFATT=AFAT 的 AA 的形式為
注意矩陣中有一個元素寫錯了,第3行第1列的元素應該是 cos(2π/2N)cos(2π/2N) 。在上述利用矩陣進行DCT變換的過程中,關于矩陣的維數是需要說明的,根據定義可以知道,被變換的圖像必須是一個正方形的圖像,也就是說圖像矩陣必須是一個方陣。根據最開始關于二維離散變換的定義我們可以知道,被變換的圖像是一個 M×NM×N 矩陣,但是這裡使用一個方陣主要是因為這樣的圖像在計算的時候才會産生 T=AFATT=AFAT ,否則 FF 前後矩陣的維數不相同,計算出的變換矩陣當然也不同,這時的計算就變成了 T=AFBTT=AFBT 的形式了。是以為了分解友善都會假設圖像是正方形的,如果圖像不是正方形的,會在圖像上取一個個正方形塊,分塊計算(實際上常常在圖像上取 8 × 8 的子圖象進行計算,因為這樣的計算量不是很大。這時矩陣 F 和 A 都是方陣。
2. DCT餘弦變換的相關代碼
2.1 編寫DCT餘弦變化矩陣 A 的代碼
clc;clear all;close all;
N = 8; % 這個是一個可以修改的參數,與原始的正方形圖像的尺寸相同。
I = rand(N) % 被變換的矩陣,這裡是一個随機生成的、元素分布在0到1的N*N的方陣
for i = 0:N-1
for j = 0:N-1
if i == 0
a = sqrt(1/N);
else
a = sqrt(2/N);
end
A(i+1,j+1) = a*cos((j+0.5)*pi*i/N)
end
end
D = A*I*A' % DCT變換
D1 = dct2(I) % matlab DCT函數進行DCT變換
D2 = A'*D*A % DCT逆變換
2.2 用矩陣相乘代替上述的 for 循環
無論是在MATLAB中,還是在puthon中使用numpy都有一個共同的特點,使用向量相乘或者矩陣相乘可以加快計算速度,是以下面的代碼是在 2.1 代碼的基礎上,用矩陣相乘來代替 for 循環的一種形式。如果想了解這種方法的具體原理,可以參考部落格《從 DTFT 的角度用矩陣相乘代替 for 循環進行計算》
clc;clear all;close all;
N = 4; % 這個是一個可以修改的參數,與原始的正方形圖像的尺寸相同。
I = rand(N) % 被變換的矩陣,這裡是一個随機生成的、元素分布在0到1的N*N的方陣
A = sqrt(2 / N)*cos((0:N-1)'*((0:N-1)+0.5)*pi/N);
A(1,:) = A(1,:) / sqrt(2)
D = A*I*A' % DCT變換
D1 = dct2(I) % matlab DCT函數進行DCT變換
D2 = A'*D*A % DCT逆變換
上面通過10行進行的計算在這裡通過三行的矩陣相乘就可以代替了,代碼精簡了,而且會提高運算速度。
2.3 DCT 餘弦變換的MATLAB指令
D = dct2(I) % matlab DCT函數對I進行DCT變換
D = dctmtx(N) % 如果矩陣A是N×N方陣,則A的DCT變換可用D×A×D’來計算,注意其中的N是維數,不是矩陣