手寫漢字的編碼壓縮技術(shù)

1、手寫漢字的編碼壓縮技術(shù)1前言人們常用名人字體制做牌匾、標(biāo)志等以提高企事業(yè)單位的知名度, 因此手寫字體的制作 也就成為裝潢工程的一個(gè)熱點(diǎn). 作者從事的微機(jī)控制切字機(jī)的研究, 旨在把各種名人手跡存 儲(chǔ)到計(jì)算機(jī)中, 由計(jì)算機(jī)自動(dòng)生成步進(jìn)電機(jī)的驅(qū)動(dòng)程序, 驅(qū)動(dòng)切字機(jī), 自動(dòng)完成裝潢漢字的 加工. 這里首先要解決的是手寫漢字的存儲(chǔ)問(wèn)題.把手寫漢字輸入計(jì)算機(jī), 無(wú)論是用數(shù)字?jǐn)z像機(jī)還是用數(shù)字掃描儀, 得到的多為濃淡圖 像, 要存 儲(chǔ)它需要很大的存儲(chǔ)空 間, 即使一 幅 1 024 * 10 24 的 二值漢字圖像, 其長(zhǎng)度就有12 8k 字節(jié)之多. 要把多如浩海的手寫漢字存儲(chǔ)起來(lái), 編碼壓縮技術(shù), 則成了問(wèn)

2、題的關(guān)鍵. 另 外, 由于手寫漢字本身或輸入設(shè)備的分辨率等問(wèn)題, 輸入計(jì)算機(jī)的漢字圖像往往會(huì)存在一些 缺陷, 在存儲(chǔ)之前, 還要解決漢字輪廓的平滑修復(fù)問(wèn)題.手寫漢字存儲(chǔ)系統(tǒng), 包括點(diǎn)陣圖像預(yù)處理、數(shù)據(jù)庫(kù)和數(shù)據(jù)庫(kù)管理三部分. 本文僅就手寫 漢字?jǐn)?shù)據(jù)庫(kù)中采用的 8 近鄰編碼壓縮和手寫漢字的平滑修復(fù)技術(shù)加以論述.2漢字輪廓的編碼與壓縮經(jīng)點(diǎn)陣圖像預(yù)處理得到二值黑白圖像1后要對(duì)手寫漢字進(jìn)行編碼和壓縮.手寫漢字的形狀是由其輪廓決定的. 本文采用 8 近鄰搜索法2 逐一跟蹤手寫漢字輪廓 之每一像素, 生成鏈碼, 再對(duì)鏈碼進(jìn)行壓縮. 所謂 8 近鄰是指圖像上任一像素的與之鄰接的8 個(gè)像素之集合( 圖 1a)

3、, 即: f i- 1, j -1, f i-1, j , f i-1, j +1 , f i, j-1 , f i, j+1 , f i+1, j-1, f i+ 1, j , f i+1 , j+1 ( 1 ) f i- 1, j - 1f i- 1, jf i - 1 , j + 1f i, j - 1f i, jf i , j + 1f i+ 1, j - 1f i+ 1, jf i + 1 , j + 1 圖 1a8 近鄰f i- 1 , jf i , j - 1f i , jf i, j + 1f i+ 1 , j 圖 1b 4 近鄰圖 1c8 近鄰的方向指數(shù)這時(shí), 相鄰的二像素互

4、為 8 近鄰, 稱它們之間是 8 鄰接.由 f ij 至其 8 個(gè)近鄰的方向稱為方向指數(shù), 其值為 0 7 ( 圖1c) . 與之對(duì)應(yīng)的主要還有 4 近鄰( 圖 1b) .如圖 2 所示, 圖像中對(duì)于同灰度值的兩個(gè)像素點(diǎn) a, b,從 a 到 b, 若存在著路徑p 0( = a) , p 1, p 2 , , p n( = b)其中, p 1 p n 全都和 a, b 具有相同的灰 度值, 且 p i 和p i- 1 是 8 鄰接( 或 4 鄰接) 時(shí), 則稱像素點(diǎn) a, b 為 8 連通( 或 4連通) . 對(duì)于圖像上同值像素點(diǎn)的集合, 可以按 8 連通, 也可以按 4 連通分成若干個(gè)連通域

5、. 圖 2中灰度為 1 的成分, 若按 8 連通區(qū)分, 是一個(gè)連通域, 若按 4 連通區(qū)分, 則可分為 a, b, c, d 四個(gè)連通域. 也就是說(shuō), 按 8 近鄰去搜索連通域的邊界, 可以減少輪廓線的數(shù)目. 圖 28 連通域和 4 連通域 圖 38 近鄰內(nèi)外輪廓的跟蹤輪廓跟蹤的方法可用圖 3 加以說(shuō)明. 從圖像區(qū)域左上角開始, 逐行從左至右查找初始跟 蹤點(diǎn). 它滿足條件: 從前未被搜索過(guò); 該像素點(diǎn)的灰度值為 1;其 4 近鄰中至少有一個(gè) 灰度值為 0. 圖 3 中 X 為外輪廓初始跟蹤點(diǎn). 記錄初始跟蹤點(diǎn)的行和列值, 并加上搜索過(guò)的 標(biāo)記( 程序中將其灰度值加 1 ) . 然后, 按圖 4

6、a 所示, 從 1 開始, 按逆時(shí)針?lè)较蛩阉? 首先遇到 的灰度值為 1 的近鄰即為下一輪廓點(diǎn) X 1 . 用 X 指向 X 1 的方向指數(shù)作為編碼, 記錄之, 并將X 1 加上搜索過(guò)的標(biāo)記.圖 4a初始搜索圖 4b反時(shí)針?biāo)阉?再如圖 4b 所 示, 從 1 開始( X 1 指向 X 的方向指數(shù)加 1 的方向) 按逆時(shí)針?biāo)阉? 首 先遇到的灰度值為 1 的近鄰即為下一輪廓 點(diǎn) X 2 . 同樣記錄 X 1 指向 X 2 的方向指數(shù)并 對(duì) X 2 加上搜索過(guò)的標(biāo)記. 如此反復(fù), 直至返 回到初始跟蹤點(diǎn), 一條輪廓線就跟蹤完畢.再?gòu)那耙怀跏?跟蹤點(diǎn) X 開始, 逐行從左到右查找新的初始跟蹤點(diǎn) Y

7、( 圖 2) , 記錄其行和列坐標(biāo). 再用相同的方法跟蹤后面各輪廓 點(diǎn)并依此記錄各方向指數(shù).如此反復(fù), 直至圖像上全部像素點(diǎn)都被搜索過(guò), 則表明已跟蹤完圖像上所有的輪廓.把由一個(gè)個(gè)方向指數(shù)構(gòu)成的序列稱為鏈碼. 一條鏈碼表示一條輪廓線. 在相鄰兩條鏈碼 之間用逗號(hào)隔開, 整幅圖像跟蹤結(jié)束時(shí), 鏈碼最后用字符- 1 結(jié)尾. 這樣, 一幅圖像的數(shù)據(jù) 結(jié)構(gòu)具有以下的形式.始點(diǎn) 行始點(diǎn) 列輪廓 鏈碼,始點(diǎn) 行始點(diǎn) 列輪 廓 鏈 碼,始點(diǎn) 行始點(diǎn) 列輪廓 鏈碼- 1圖 5 給出了手寫漢字“沖”的圖像和經(jīng)過(guò)跟蹤后由輪廓鏈碼復(fù)原的輪廓. 為了節(jié)約存儲(chǔ)空間, 本系統(tǒng)采用 4 種模板對(duì)輪廓鏈碼壓縮 存儲(chǔ)3. 由于

8、鏈碼的值為 0 7, 可用 3 比特表示, 故可用位字段 結(jié)構(gòu)體把 8 個(gè)鏈碼壓縮存入 3 個(gè)字節(jié)中( 圖 6 ) . 但若只使用這一 種模板, 還會(huì)造成一定的浪費(fèi). 設(shè)一條輪廓鏈碼的長(zhǎng)度為 N , 若N m od 8 = 1, 即當(dāng)剩余鏈碼數(shù)為 1 時(shí), 使這一個(gè)鏈碼占用 3 個(gè)字節(jié)顯然是一種浪費(fèi).圖 5漢字的圖像和由 鏈碼復(fù)原的輪廓為此, 系統(tǒng)還建立了另外 3 種模板: 對(duì)于 N mod 8= 12 個(gè) 鏈碼, 分配 1 個(gè)字節(jié), 對(duì)于 N m od 8= 3 5 個(gè)鏈碼, 分配 2 個(gè)字節(jié), 對(duì)于 N mod 8= 6 7 個(gè)鏈碼, 分配 3 個(gè)字節(jié). 這樣就能保證最大限度的利用存儲(chǔ)空間

9、.用鏈碼表示漢字輪廓, 還有如下的優(yōu)點(diǎn):( 1) 高保真性: 鏈碼壓縮是一種無(wú)失真壓縮法, 由鏈碼可以完 全再現(xiàn)手寫漢字的原貌.( 2 ) 平移不變性: 平移漢字時(shí), 鏈碼數(shù)值不變, 只需要把各初始 跟蹤點(diǎn)的坐標(biāo)加上一個(gè)常數(shù)即可.( 3) 縮放不變性: 通過(guò)改變柵格的大小, 即可實(shí)現(xiàn)手寫漢字的放大和縮小.圖 6模板 18鏈碼存入 3 字節(jié) ( 4) 旋轉(zhuǎn)不變性: 由輪廓鏈碼 a1, a2, , aN 求出其差分鏈碼 d 1 , d 2, , d N , 其中, 差分 d i= diff ( ai , ai- 1) 表示后一輪廓點(diǎn)對(duì)于前一輪廓點(diǎn)轉(zhuǎn)過(guò)了幾個(gè) 45°角. 使用差分鏈碼時(shí),

10、由于給出了輪廓上各點(diǎn)的相互關(guān)系, 故欲 使?jié)h字旋轉(zhuǎn) 45 °的倍數(shù)時(shí), 具有旋轉(zhuǎn)不變性.3手寫漢字的修復(fù)與平滑由于手寫漢字的來(lái)源和輸入裝置的精度等原因, 漢字圖像易于出現(xiàn)局部的凹凸現(xiàn) 象, 把這樣的 噪聲叫做標(biāo)本化噪聲4 它可 分為兩種. 一種表現(xiàn)為相鄰二鏈碼之間構(gòu)成 直角( 圖 7) , 對(duì)此, 可修正為直線. 相鄰鏈碼 ai, ai+ 1間若構(gòu)成直角, 即滿足下式:圖 7a 奇數(shù)直角成分 圖 7b 偶數(shù)直角成分 它可以分為鏈碼值為奇數(shù)的直角成分和鏈碼值為偶數(shù)的直角成分, 前者用兩個(gè), 后者用 一個(gè)平滑鏈碼修正. 平滑鏈碼值 p 為p = ( ai+ 1 + 1) mod 8即對(duì)于

11、奇數(shù)直角成分, 令: ai = p ai+ 1 = p對(duì)于偶數(shù)直角成分, 令 ai = pai+ k = ai+ k+ 1 k = 1, 2, 圖 8折線近似法的原理圖 9最小二乘誤差曲線擬合的原理 對(duì)于更大范圍的凹凸缺陷, 可以采用折線近似法或最小二乘誤差曲線擬合的方法進(jìn)行 修正.圖 8 表示出了折線近似法的原理. 假想連接欲修正輪廓上的兩點(diǎn), 找出距離此直線最遠(yuǎn) 的點(diǎn), 若它離假想直線的距離大于給定的允差 , 即以此點(diǎn)將假想直線分割成兩部分, 再找 出距離它們最遠(yuǎn)的點(diǎn). 依此類推, 直到滿足給定的 .圖 9 說(shuō)明了最小二乘誤差曲線擬合的原理. 設(shè)有凹凸缺陷的輪廓上的點(diǎn)的集合為 ( x i ,y i) , i= 1, 2 , , N , 設(shè)平滑曲線為 F( x ) , 設(shè):F( x ) = a0 + a1 x + a2 xN+ + anx問(wèn)題歸結(jié)為求使E = y i - F( x i) 2為最小的 F ( x ) 的系數(shù) a0, a1 , , an 這樣的變分法的問(wèn)題. 設(shè):則 A 可由下式求出:式中: X - 1 為 X 的逆矩陣.A = Y( a) 折線法, ( b ) 最小二乘法 圖 1 0輪廓修 正后的漢字圖 10 是用折線法和最小二乘誤差曲線擬合法對(duì)手寫“沖”字輪廓處理后的結(jié)果 對(duì)于輪廓有凹凸缺陷的手寫漢字, 按需要可以在對(duì)輪廓平 滑修正后重新進(jìn)行編碼