【正文】 味著更小的空間相關(guān)性 變換的尺寸 2*2 4*4 8*8 16*16 32*32 64*64 子塊尺寸 位 /象素 快速算法 ?直接進(jìn)行 計(jì)算：每個(gè)系數(shù)需要 64 次乘法、 63 次加法，8 8 將需要 1024 次乘法， 896 次加法。 ? 變換固有的缺點(diǎn)： ?塊效應(yīng)：變換編碼是一種塊結(jié)構(gòu)編碼方法，易出現(xiàn)塊與塊之間的不連續(xù)性。 變換系數(shù)的游程編碼 ?更有效的傳輸非零變換系數(shù)位置的方法：“之”字型掃描和游程 幅度二維熵編碼。 ?傳送的系數(shù)位置隨圖像內(nèi)容而變化，具有一定的自適應(yīng)性。 ?經(jīng)逆量化和逆 恢復(fù)圖象。 ? 系數(shù)能量集中在低頻系數(shù)（特別是直流系數(shù)），需要進(jìn)行細(xì)量化（量化步長 /臺(tái)階?。?，而高頻系數(shù)能量很少，可以對(duì)高頻系數(shù)粗量化。 14 ( , )3 V k l??????? ? ????????解：二維是可分離的 ， 可先對(duì)各行進(jìn)行一維的行變換 ， 得到系數(shù)矩陣如下： 再進(jìn)行列變換 ， 最終的系數(shù)矩陣為： 的矩陣算法 ( , )f i j ( , )F u v( , )G i v垂直方向8 1 DCT水平方向8 1 DCT舉例 ?在變換域中，低頻系數(shù)的能量遠(yuǎn)大于高頻系數(shù)的能量，變換系數(shù)的相關(guān)性將大大去除。 的矩陣算法 ? 一維離散余弦變換： V C U?正變換： TU C V?反變換： ? 二維離散余弦變換： TV C UC?正變換： 反變換： TU C V C?C 為離散余弦變換矩陣 ， 為 C 的轉(zhuǎn)置矩陣 的矩陣算法 ? 變換矩陣 C ： 當(dāng) 2 時(shí) ， 變換矩陣 C為： 當(dāng) 4 時(shí) ， 變換矩陣 C 為： 1 1 12 2 23 ( 2 1 )2 c o s c o s c o s2 2 2( 1 ) 3 ( 1 ) ( 1 )( 2 1 )c o s c o s c o s2 2 2 NNNA N N NNN N N NN N N? ? ?? ? ??????????? ? ? ???11223c o s c o s44A???????????1 1 1 12 2 2 23 5 7c o s c o s c o s c o s1 8 8 8 82 2 6 10 14c o s c o s c o s c o s8 8 8 83 9 15 21c o s c o s c o s c o s8 8 8 8A? ? ? ?? ? ? ?? ? ? ????????????的矩陣算法 77001 ( 2 1 ) ( 2 1 )( , ) ( ) ( ) ( , ) c os c os4 16 16iji u j vF u v C u C v f i j ?????? ??? ??????77001 ( 2 1 ) ( 2 1 )( , ) ( ) ( ) ( , ) c os c os4 16 16uvi u j vF i j C u C v f u v??? ??? 變換使用下式計(jì)算 ? 逆變換使用下式計(jì)算 ( ) , ( ) = 1/ 2C u C v( ) , ( ) 1u C v ?當(dāng) 0； 其他 其中， 的矩陣算法舉例 已知： 139 144 149 153144 151 153 156( , )150 155 160 163159 161 162 160u m n?????????用矩陣算法求其。 （ 3）具有較強(qiáng)的抗干擾能力，傳輸過程中的誤碼對(duì)圖像質(zhì)量的影響遠(yuǎn)小于預(yù)測編碼。它常被認(rèn)為是對(duì)語音和圖像信號(hào)進(jìn)行變換的最佳方法 ,成為 、 等國際上公用的圖像壓縮編碼標(biāo)準(zhǔn)的重要環(huán)節(jié)。 為解決這一問題：在變換的基礎(chǔ)上提出了以下變換： 哈特萊變換（） 離散哈特萊變換 () 離散余弦變換 （） 離散余弦變換 （） 這些變換都與變換緊密相連，且變換的運(yùn)算均在實(shí)數(shù)域進(jìn)行。 變換的局限和算法上的不足： （ 1）變換是在整體上將信號(hào)分解為不同的頻率分量，而缺乏局域性信息。原因：非平穩(wěn)信號(hào)的頻率是隨時(shí)間變化的，所以不再簡單地用變換做分析工具。對(duì)于 0tT的信號(hào)，我們?nèi)粝Ｍ佬盘?hào)的能量分布，須對(duì)信號(hào)做傅里葉變換，即研究其頻率特性。 變換的特征－降維 ?忽略特征值較小的那些特征向量，從而減少 u 的維數(shù)。 中心化后圖象向量 變換的特征－去相關(guān) ?去相關(guān) —— 最佳的變換編碼 變換系數(shù) {v(k), 0,1,…1} 是不相關(guān)的，而且具有零均值，即： [ ( )] 0vm E v k??*1[( )( ) ]0()0Tv v vTukNR E v m v mRkl????? ? ?? ? ?????? ? ? ? ???????證明： * * ***[ ] { ( )} { }0T T Tv u uTTuum E v E u m E u mmm? ? ? ? ? ? ? ?? ? ? ? ?協(xié)方差矩陣 變換的特征－去相關(guān) ?經(jīng)過 變換后，所得的變換系數(shù) v 是一個(gè)平均向量為零的向量集，其坐標(biāo)原點(diǎn)移到中心位置。 ? 依賴信號(hào)統(tǒng)計(jì)特性，但很難實(shí)時(shí)計(jì)算視頻的統(tǒng)計(jì)特性； ? 基函數(shù)不是固定的，是隨圖像內(nèi)容改變的； ? 對(duì)圖象塊是不可分離； ?變換矩陣不能分解為稀疏矩陣。 變換編碼的選擇原則 ?變換編碼的種類 ?變換 ?離散傅立葉變換 ?離散正弦變換 ?離散余弦變換 ?哈達(dá)瑪變換 ? 變換 ? 變換 ? 變換 ?小波變換 ?去相關(guān)，能量集中（例如，、） ?計(jì)算復(fù)雜度低 232。 ? ?? ?若 ， 則證 明 ：22122* * *012 2*0NT T TkNTnV A U V UV v k V V U A A UU U u n U??????? ? ? ?? ? ? ???? ? ? ?若 ：則 ：1 1 1 1220 0 0 0,TN N N Nm n k lV A UAu m n v k l? ? ? ?? ? ? ???? ? ? ?? 1 ? 2 酉變換特性－能量集中與變換系數(shù)方差 ?酉變換：能量轉(zhuǎn)到少數(shù)系數(shù)上，總能量不變 ? 變換前后平均能量相等： μu、 分別表示 U 矢量的均值和協(xié)方差 [ ] [ ] [ ]VUE V E A U A E U A???? ? ? ?****[( )( ) ]( [( )( ) ])TV V VTTUUTUR E V VA E U U AA R A????? ? ?? ? ??? 矩陣對(duì)角線元素給出變換系數(shù)方差 : ? ? ? ?2*, ,Tv v ukk kkk R A R A? ???? ??? ? ? ? 直 流 分 量1122* * *00NN T T Tv v v u u uknk A A n? ? ? ? ? ?????? ? ? ???? ? ? ? ? ? 平 均 能 量2 * 2Tv u u uk Tr A R A Tr R n????? ? ? ???? ? ? ?112200nkE u n E v k? ? ? ??? ? ? ?? ? ? ?最后得： 矩陣的跡 ， 矩陣對(duì)角線上元素的總和 。由于基函數(shù)是正交的，則這個(gè)信號(hào)對(duì)應(yīng)于其它的基函數(shù)將產(chǎn)生較少的系數(shù)。 ? 例如 1024，直接傅里葉變換需要大約 106 次操作，快速傅里葉變換只需要 104 次操作。 TV A UA?N N 正交變換矩陣 N N變換系數(shù) ?反變換 ?重要的實(shí)際意義：用 2 個(gè) N N 矩陣乘法代替了 1 個(gè) 1 N2 矢量和 N2 N2 矩陣的乘法，實(shí)現(xiàn)變換。 ?正交矩陣是酉矩陣，但酉矩陣不需要是正交矩陣。變換編碼 四川大學(xué) 計(jì)算機(jī)學(xué)院 陳 虎 ? ?原理 ?為達(dá)到目的可以通過不同的路徑 —— 殊途同歸 ? 例如：數(shù)學(xué)計(jì)算機(jī)中，經(jīng)常利用某些數(shù)學(xué)函數(shù)略加轉(zhuǎn)換可以找出一條計(jì)算的捷徑。 ?因此 ,合成可能性往往落在陰影區(qū)內(nèi) 0 X1 X2 ?變換去除相關(guān)性示例 ?如果對(duì)數(shù)據(jù)進(jìn)行正交變換，從幾何上相當(dāng)于坐標(biāo)系旋轉(zhuǎn) 45o,變成 x1’、x2’坐標(biāo)系，則在新坐標(biāo)系下，任憑 x1’在較大的范圍變化，而 x2’始終只在相當(dāng)小的范圍內(nèi)變化，因此通過這樣的變化就能得到一組去除大部分，甚至是全部統(tǒng)計(jì)相關(guān)性的另一種輸出樣本 0 X1 X2 X1’ X2’ ?變換編碼過程 變換 量化 譯碼器 逆變換 編碼器 發(fā)送端 接收端 G A A’ G’ U’ 輸入 U 輸出 U為變換矩陣， ’:變換系數(shù) U’的逆變換矩陣 酉（）變換概念 ?線性變換 v = ，系數(shù)矩陣 A 稱為此變換的基矩陣 ?如果 A 是一個(gè)酉矩陣，則： 1*TAA? ?且 **TTA A A A I??其中， * 表示對(duì) A 的每個(gè)元素取共軛復(fù)數(shù)， T 表示轉(zhuǎn)置 ?如果 A 是酉矩陣，且所有元素都是實(shí)數(shù)，則它是一個(gè)正交矩陣，且滿足 1 T? ?且 TTA A A A I??上式表明：當(dāng) 時(shí)，內(nèi)積為 1；否則內(nèi)積為 0，所以， A的各行是一組正交向量 ?任何兩個(gè)酉變換之間的差別在于基函數(shù)（即 A 的行向量）的選擇。 () 是離散正交變換基函數(shù) ? ? ? ? ? ?1100, , , 0 , 1NNklmnv k l u m n a m n k l N????? ? ? ? ????正變換 ( ) 矩陣表示： V AU?N N輸入信號(hào)塊 ， 向量排列 N2 N2 變換矩陣 N N變換系數(shù) ?線性： v() 描述為“基函數(shù) ( )”的線性組合 ? ? ? ? ? ?1100, , * , 0 , 1NNklklu m n v k l a m n m n N????? ? ? ? ???可分離的正交變換 ?酉變換 ? ? ? ? ? ?1100, , , 0 , 1NNklmnv k l u m n a m n k l N????? ? ? ????基函數(shù)分解表示為： ? ? ? ? ? ? ? ? ? ?, , ,kl k la m n a m b n a k m b l n????