基于卷積的快速分形圖像編碼

1、基于卷積的快速分形圖像編碼王冬梅1 付萍21（長(zhǎng)春郵電學(xué)院 長(zhǎng)春 130012） 2（吉林工業(yè)大學(xué)信息工程學(xué)院 長(zhǎng)春 130025）摘要 本文提出一種基于卷積的快速分形編碼算法。在求區(qū)分形壓縮仿射變換參數(shù)的過(guò)程中,利用快速卷積來(lái)計(jì)算區(qū)域塊與排列塊之間的互相關(guān),從而實(shí)現(xiàn)了編碼過(guò)程的無(wú)損加速。為了在加速編碼過(guò)程的同時(shí)提高壓縮比,將快速卷積算法與基于四叉樹(shù)分割的鄰域搜索算法相結(jié)合。通過(guò)計(jì)算機(jī)仿真實(shí)驗(yàn),獲得了良好的效果。與經(jīng)典的PIFS方法相比,在信噪比大致相當(dāng)?shù)那疤嵯?編碼速度和壓縮比都得到了顯著提高。關(guān)鍵詞 分形圖像壓縮 四叉樹(shù) 傅氏變換 卷積 互相關(guān)Convolution Based Fast

2、Fractal Image CodingWang Dongmei1 Fu Ping21(Changchun Iustitute of Posts and Telecommunicatiins，Changchun 130012，China)2（Infotmation Engineering Institute，Jilin Untversity of Technology，Changchun 130025）Abstract In this paper, a fast fractal coding algorithm based on convolution theory is presented.

3、 During the procedure of affine transform parameters calculation in fractal compression, fast convolution theory is used to calculate the cross-correlation betw0een domain blocks and range blocks, in this way, the process of encoding is accelerated losslessly. In orded to raise compress ratio while

4、accelerating encoding process, an algorithm combining fast convolution with quadtree partitioning based on neighbor search is adopted. Computer simulation has shown that unded the condition of modedate loss of image quality, this algorithm brings up higher compression ratio and edcoding speed compar

5、ed with that of conventional PIFS method.Key words Fractal image compression Quadtree Fourier transform Convolution Cross-correlation 1 引 言近年來(lái)，分形圖像壓縮編碼技術(shù)因其潛在的高壓縮比而引起了人們的廣泛興趣。它源于Barnsley提出的迭代函數(shù)系統(tǒng)(IFS)理論,實(shí)質(zhì)就是把待壓縮的圖像作為一組不動(dòng)點(diǎn)集T，并尋找一組仿射變換集W1，WN,其不動(dòng)點(diǎn)集與T相近,用保存W1的系數(shù)代替原圖像T。后來(lái),Jacquin提出了基于分割迭代函數(shù)系統(tǒng)(PIFS)的分塊式分形壓

6、縮編碼方法12，這是一種全自動(dòng)的壓縮編碼方案。但是,在這種方法 * 吉林省科學(xué)委員會(huì)發(fā)展基金資助項(xiàng)目。的編碼過(guò)程中，需對(duì)每一排列塊在整幅圖像內(nèi)尋找相互匹配的區(qū)域塊，致使編碼時(shí)間過(guò)長(zhǎng)。本文在經(jīng)典的PIFS方法基礎(chǔ)上，提出了一種基于卷積的快速分形壓縮算法。2 基于卷積的分形壓縮算法原理2.1 互相關(guān)函數(shù)的引入在分形壓縮編碼中，對(duì)每一排列塊尋找最佳匹配區(qū)域塊的過(guò)程，實(shí)際上可以看作是計(jì)算排列塊與各碼書(shū)塊(經(jīng)空間收縮后的區(qū)域塊)的互相關(guān)，以找到一個(gè)與之相關(guān)程度最高，(即最相似)的區(qū)域塊。 同時(shí)，由于區(qū)域塊的搜索步距一般為兩個(gè)象素點(diǎn)，也空一行小五（頁(yè)面設(shè)置，不要設(shè)置頁(yè)眉頁(yè)腳，頁(yè)面設(shè)置上2.8cm，下3.3

7、cm，左右各2cm）空一行小五空一行小五中文標(biāo)題為黑體二號(hào)字不宜超過(guò)20個(gè)字著者署名為楷體十號(hào)字，段前24磅（第一作者單位為宋體小五號(hào) 城市 郵編） （第二作者單位 城市 郵編）摘要 中文摘要不超過(guò)400字為宜。段前為18磅。“摘要”二字為黑體小五號(hào)字。摘要內(nèi)容為宋體小五號(hào)字。每行間距為14磅。關(guān)鍵詞 關(guān)鍵詞 關(guān)鍵詞 關(guān)鍵詞 關(guān)鍵詞 關(guān)鍵詞英文題名不宜超過(guò)10個(gè)實(shí)詞為T(mén)ime New Roman體四號(hào)字加粗，段前18磅作者姓名的漢語(yǔ)拼音為T(mén)ime New Roman五號(hào)字，段前18磅（abcdefghijklmnopqrstuvwxyz英文書(shū)寫(xiě)的作者單位，所在城市，郵編）為T(mén)ime New R

8、oman字體，小五號(hào)斜體Abstract 英文摘要不宜超過(guò)250個(gè)實(shí)詞。段前為12磅。Time New Roman字體五號(hào)字。每行間距為16磅。Key words Time New Roman字體五號(hào)字。每行間距為16磅。1 引 言“引言”段前18磅。黑體小四號(hào)字加粗。正文距引言段前12磅。正文為宋體10號(hào)字，字間距加寬0.5磅，行間距為16磅。論文的必要組成部分按下列排序依次相接：題名、著者、著者單位和所在城市及郵編、摘要、關(guān)鍵詞、英文題名、作者姓名的漢語(yǔ)拼音、英文書(shū)寫(xiě)的著者工作單位、英文摘要、英文關(guān)鍵詞、引言、正文、結(jié)論、參考文獻(xiàn)。論文打印格式 腳注為宋體六號(hào)，字間距加寬0.5磅為何種基金

9、資助項(xiàng)目：中、英文題名、著者、著者單位、摘要、關(guān)鍵詞等用通欄排版。引言、正文、結(jié)論及參考文獻(xiàn)部分一般取雙欄排版，欄間距0.75厘米，每欄23字。應(yīng)減少繁瑣的數(shù)學(xué)推導(dǎo)，正文中過(guò)長(zhǎng)的必要的數(shù)學(xué)公式不易轉(zhuǎn)行時(shí)可排通欄。某些容易混淆的英文與希臘文用鉛筆標(biāo)注。2 一級(jí)標(biāo)題段前、段后各為12磅黑體小四加粗，字間距加寬0.5磅2.1 二級(jí)標(biāo)題黑體5號(hào)字加粗，字間距加寬0.5磅論文章、節(jié)、條的劃分、編號(hào)和排列均應(yīng)采用阿拉伯?dāng)?shù)字分級(jí)編寫(xiě)，即一級(jí)標(biāo)題（章）的編號(hào)為1，2；二級(jí)標(biāo)題（節(jié)）的編號(hào)為1.1，1.22.1，2.2；三級(jí)標(biāo)題（條）的編號(hào)為如此等等。論文中有關(guān)計(jì)量單位的內(nèi)容應(yīng)采用國(guó)家法定計(jì)量單位，執(zhí)行GB31

10、0093等國(guó)家標(biāo)準(zhǔn)。2. 2 頁(yè)面設(shè)置請(qǐng)用A4打印紙排版。上邊距2.8cm,下邊距為3.3 cm，左邊距2cm，右邊距2 cm，頁(yè)眉2.3 cm，頁(yè)腳1.5 cm。2. 3 插圖格式函數(shù)圖的標(biāo)目通常由物理量及其相應(yīng)的符號(hào)和單位組成。物理量的符號(hào)應(yīng)按GB3l00310293規(guī)定的斜體國(guó)際標(biāo)注字符給出，單位應(yīng)按國(guó)標(biāo)規(guī)定用正體書(shū)寫(xiě)。如速度u/km·s1。 圖字：圖表示列請(qǐng)盡量采用電腦制圖，函數(shù)圖尺寸盡量控制在4.5cm×3cm面積。圖字為宋體小五號(hào)字。照片要用黑白照片，反差應(yīng)適當(dāng)大些。插圖必須用繪圖筆畫(huà)在潔白繪圖紙或透明紙上，線條用儀器描繪，黑白對(duì)比度要強(qiáng)，插圖可畫(huà)大些，以便加工

11、。圖字用鉛筆標(biāo)注。論文中的表格應(yīng)精心設(shè)計(jì)，推薦使用三線表。即欄頭取消斜線，表身不出現(xiàn)豎線，盡量刪減分隔線。表序、表題在表格上方居中排。表 題宋體小五號(hào)居中表 題表 序宋體小五號(hào)居中1A表 序2B圖、表應(yīng)有自明性，且隨文出現(xiàn)。圖表以6幅為限。圖、表應(yīng)附上相應(yīng)的圖號(hào)、表號(hào)、圖題、表題。圖中文字、符號(hào)、縱橫坐標(biāo)中的標(biāo)值、標(biāo)值線必須寫(xiě)清，標(biāo)目應(yīng)使用標(biāo)準(zhǔn)的物理量(一般用一個(gè)字母表示)和國(guó)際制單位符號(hào)。文中表格建議使用“三線表”，圖、表的內(nèi)容切忌與文字內(nèi)容重復(fù)圖中。外文一律譯成中文圖字為宋體小五號(hào)字。3 結(jié)論3. 1 論文截止時(shí)間：2006年11月10日，錄取通知日期：2006年11月15日。參考文獻(xiàn)1 “參考文