常見的影像修復技術，主要的瓶頸在於邊緣的修復。為了解決修補
法在確定影像邊緣上的難題，還有修補時，提升正確性，本文提出一利
用浮水印技術用於影像破壞區域之偵測與修補。
我們將原圖之重要邊緣抽出，視為強健型浮水印，再嵌入於原圖做
一階小波之後的1 LL 位置中，以作為修補比對之參考。本技術亦嵌入一易
碎型浮水印，修復系統可藉由抽取易碎型浮水印，自動偵測待測影像之
破壞區域，同時利用抽取出之強健型浮水印(重要邊緣)，依照其重要邊
緣紋理，進行階層式修補，包含區塊修補法及結構擴展法。但是同時嵌
入兩個浮水印，又要提升嵌入之後的影像PSNR 值，是很困難的。所以
我們利用小波轉換與VQ 結合，來減少需要嵌入的資料量。由實驗結果
可證實，嵌入浮水印之後，測試影像仍然不易察覺的優點，受破壞之後，
本技術可自動偵測破壞區域，並成功修補之。

In image completion and inpainting technique,the key issue is edge
restoration. In order to resolve the image inpainting problem in the object
edge and to enhance the accuracy of the original image during repairing, we
presents a multi-purpose watermarking technique to repair image
automatically. We use the edge of the original image as the robust watermark
and embed it into the lower frequency band as the reference for repairing
defected area. We also embedde a fragile watermark into image. By
extracting the fragile watermarking, the repair system can detect the defected
area automatically.
Meanwhile, we utilize the extracted robust watermarking, followed by
the texture of object edge, to repair the image block and edge of image. It is
difficult to insert two watermarks and to achieve high Peak Signal to Noise
Ratio, so we use the Discrete Wavelet Transform and Vector Quantization
techniques to minimize the embedded data. According to the experimental
results, the embedded watermark is invisible in the test image. When the test
image was attacked, this technology can detect the large defected area or
complicated defected area and repair it automatically.

目錄
第一章 緒論................................................................................................1
1.1 研究背景與動機.............................................................................1
1.2 研究目的.........................................................................................2
1.3 論文架構.........................................................................................3
第二章 相關技術之基礎介紹....................................................................4
2.1 小波轉換.........................................................................................4
2.1.1 小波理論分析......................................................................4
2.1.2 離散小波轉換......................................................................7
2.2 向量量化編碼法(Vector Quantization) ..........................................9
2.2.1 LBG演算法.........................................................................11
2.3 Canny edge 邊緣偵測...................................................................13
2.4 影像修補法...................................................................................16
2.4.1 結構擴展法........................................................................16
2.4.2 區塊修補法........................................................................18
2.5 數位浮水印相關技術...................................................................19
2.5.1 數位影像驗證技術............................................................19
2.5.2 數位浮水印技術基本原理................................................22
2.5.3 相關浮水印技術................................................................25
第三章 本系統浮水印之產生與嵌入......................................................26
3.1 修補專用強健型浮水印產生.......................................................27
3.1.1 編碼簿之產生....................................................................27
3.1.2 修補專用強健型浮水印之產生.........................................29
3.2 修補專用強健型浮水印嵌入.......................................................34
3.3 偵測破壞區域專用易碎型浮水印嵌入........................................37
第四章 影像破壞區域之偵測與修補......................................................40
4.1 偵測破壞區域專用易碎型浮水印抽取.........................................41
4.2 修補專用強健型浮水印抽取.......................................................44
4.3 改良式修補演算法.......................................................................46
4.3.1 破壞區域標定....................................................................47
4.3.2 破壞區域之周圍邊緣資訊前處理.....................................48
4.3.3 改良式修補演算法............................................................50
第五章 系統評估與討論..........................................................................52
5.1 嵌入浮水印...................................................................................53
5.1.1 嵌入修補專用強健型浮水印.............................................53
5.1.2 嵌入偵測破壞區域專用易碎型浮水印.............................57
5.1.3 VQ壓縮...............................................................................63
5.2 偵測破壞區域...............................................................................65
5.3 修補討論.......................................................................................67
5.3.1 本系統修補步驟................................................................67
5.3.2 強邊緣斜率討論................................................................71
5.3.3 VQ 對修補之影像...............................................................76
5.3.4 Canny edge 對修補之影響..................................................78
第六章 結論與未來研究方向....................................................................82
6.1 結論...............................................................................................82
6.2 未來研究方向...............................................................................83
參考文獻......................................................................................................85
圖目錄
圖2.1 雙頻帶分析濾波器.............................................................................5
圖2.2 小波係數之階層關係.........................................................................6
圖2.3 二階小波轉換示意圖.........................................................................6
圖2.4 小波合成............................................................................................7
圖2.5 向量量化編碼示意圖.......................................................................10
圖2.6 向量量化解碼示意圖.......................................................................10
圖2.7 像素的邊緣梯度...............................................................................14
圖2.8 Pepper................................................................................................15
圖2.9 Canny 邊緣偵測.................................................................................15
圖2.10 不同閥值的Canny 邊緣偵測.........................................................15
圖2.11 連接遭受破壞區域Ω 的曲線.........................................................16
圖2.12 修補示意圖....................................................................................16
圖2.13 曲線i c (yellow)與曲線
c (red) , dist為最短距離示意圖....................17
圖2.14 區塊修補法(1) ...............................................................................18
圖2.15 區塊修補法(2) ...............................................................................18
圖2.16 典型浮水印嵌入法流程圖.............................................................24
圖2.17 私密浮水印萃取流程圖.................................................................24
圖2.18 公開浮水印萃取流程圖.................................................................24
圖3.1 浮水印之產生與嵌入流程圖...........................................................26
圖3.2 修補專用強健型浮水印嵌入流程圖...............................................27
圖3.3 訓練編碼簿流程圖...........................................................................28
圖3.4 測試影像Fence................................................................................31
圖3.5 測試影像做2 階小波完成圖............................................................32
圖3.6 取2 LL 區域做Canny edge 完成圖.....................................................32
圖3.7 使用VQ 壓縮之後，還原邊緣資訊圖..............................................32
圖3.8 修補專用強健型浮水印嵌入法流程圖...........................................34
圖3.9 偵測破壞區域專用易碎型浮水印...................................................37
圖3.10 8 8 × pixels 之子區塊示意圖............................................................38
圖3.11 易碎型浮水印嵌入位置.................................................................39
圖4.1 影像破壞區域之偵測修補流程圖...................................................40
圖4.2 抽取偵測破壞區域專用易碎型浮水印流程圖...............................41
圖4.3 易碎型浮水印抽取法流程圖...........................................................42
圖4.4 修補專用強健型浮水印抽取流程圖...............................................44
圖4.5 改良式影像修補流程圖...................................................................46
圖4.6 (a)受破壞之浮水印 (b)偵測破壞區域專用易碎型浮水印 (c) 對
應影像受破壞區域........................................................................47
圖4.7 (a)測試影像的邊緣資訊圖 (b)VQ 壓縮之後解壓縮還原回來的邊
緣資訊圖........................................................................................48
圖4.8 Lena 解壓縮還原破壞區域的邊緣資訊圖........................................49
圖4.9 (a)Fence 解壓縮還原破壞區域的邊緣資訊圖 (b)使用Sun[1]的方法
修補破壞區域的邊緣圖..................................................................49
圖4.10 使用Laplacian 遮罩抽取之強邊緣資訊........................................50
圖4.11 使用改良式修補法修補邊緣完成圖.............................................51
圖5.1 Lena...................................................................................................52
圖5.2 Fence..................................................................................................52
圖5.3 Jet.......................................................................................................52
圖5.4 Lilies..................................................................................................52
圖5.5 (a)Lena 嵌入強健型浮水印 (b)嵌入的強健型浮水印.....................53
圖5.6 (a)Fence 嵌入強健型浮水印 (b)嵌入的強健型浮水印..................54
圖5.7 (a)Jet 嵌入強健型浮水印 (b)嵌入的強健型浮水印.......................54
圖5.8 (a)Fence 嵌入強健型浮水印 (b)嵌入的強健型浮水印..................55
圖5.9 (a)Lena (b)Fence (c)Jet (d)Lilies 嵌入強健型浮水印......................56
圖5.10 認證用浮水印 TKU.......................................................................58
圖5.11 (a)Lena (b)Fence (c)Jet (d)Lilies 部分嵌入易碎型浮水印............58
圖5.12 (a)Lena (b)Fence (c)Jet (d)Lilies 完全嵌入強健型與易碎型浮水印
........................................................................................................60
圖5.13 (a) 浮水印嵌入位置7 示意圖 (b) 影像Jet 嵌入位置7 (c) 浮水印
嵌入位置5 示意圖 (d) 影像Jet 嵌入位置5 (e) 浮水印嵌入位置
14 示意圖 (f) 影像Jet 嵌入位置...................................................62
圖5.14 (a)Lilies 邊緣資訊 (b)Lilies 使用VQ 壓縮 (c)Lena 邊緣資訊
(d)Lena 使用VQ 壓縮 (e)Jet 邊緣資訊 (f)Jet 使用VQ 壓縮
(g)Fence 邊緣資訊 (h)Fence 使用VQ壓縮...................................65
圖5.15 (a)Fence 破壞區域 (b)破壞區域偵測.............................................66
圖5.16 (a)Lena 破壞區域 (b)破壞區域偵測..............................................66
圖5.17 (a)遭受破壞之測試影像 (b)抽取出修補專用強健型浮水印 (c)對
未遭受破壞區域做強邊緣處理 (d)將邊緣資訊貼回破壞區域...68
圖5.18 Lena 破壞區域貼回邊緣資訊.........................................................69
圖5.19 邊緣資訊作線性迴歸，取平滑.......................................................70
圖5.20 使用結構擴展法修補邊緣.............................................................70
圖5.21 修補完成........................................................................................71
圖5.22 剩餘區域做Canny edge，破壞區域貼上邊緣資訊........................72
圖5.23 破壞區域貼上邊緣資訊.................................................................72
圖5.24 使用結構擴展法修補邊緣.............................................................73
圖5.25 剩餘區域做梯度運算.....................................................................74
圖5.26 破壞區域貼回邊緣資訊(不做細線化處理)...................................75
圖5.27 使用結構擴展法修補.....................................................................75
圖5.28 修補完成........................................................................................76
圖5.29 (a)使用VQ 壓縮之邊緣資訊回填破壞區域 (b)利用改良式修補法
將(a)修補完成 (c)不使用VQ 壓縮之邊緣資訊 (d)不使用VQ 壓
縮之邊緣影像回填破壞區域 (e) 利用改良式修補法將(c)修補完
成....................................................................................................77
圖5.30 (a)測試影像Lena (b)對測試影像作Canny edge，閥值為1.5 (c) 對
測試影像做Canny edge，閥值為0.5..............................................79
圖5.31 (a)閥值1.5 之邊緣資訊填回破壞區域 (b) 閥值0.5 之邊緣資訊填
回破壞區域 (c) 閥值1.5 之修補完成影像 (d) 閥值0.5 之修補完
成影像............................................................................................80
圖5.32 (a)Jet 破壞區域 (b)Jet 修補完成 (c)Lilies 破壞區域 (d)Lilies 修補
完成................................................................................................81

表目錄
表5.1 部份嵌入強健型浮水印之後與原圖影像比較PSNR 值..................55
表5.2 完全嵌入強健型浮水印之後與原圖影像比較PSNR 值..................57
表5.3 部分嵌入強健型與易碎型浮水印之後，與原圖影像比較PSNR
值......................................................................................................59
表5.4 部分嵌入強健型與易碎型浮水印之後，與原圖影像比較PSNR
值......................................................................................................60
表5.5 嵌入易碎型浮水印位置不同，與原圖相比較PSNR 值....................63

參考文獻
[1] Jian Sun, Lu Yuan, Jiaya Jia, Heung-Yeung Shum,“Image Completion
with Structure Propagation,” ACM Transactions on Graphics ,
SIGGRAPH 2005.
[2] Andrei Rares, Marcel J.T. Reinders, and Jan Biemond, “Edge-Based
Image Restoration” IEEE Transactions on Image Processing, VOL.
14, NO. 10, 2005, PP.1454-1468.
[3] R. M. Gray, “Vector Quantization,” IEEE Transactions on Acoustics,
Speech, andSignal Processing, Vol. 1, April 1984, pp. 4-29.
[4] Y. Linde, A. Buzo, and R. M. Gray, “An Algorithm for Vector
QuantizerDesign,” IEEE Transactions on Communications, Jan. 1980,
Vol. 28, pp. 84-95.
[5] John F. Canny. “A computational approach to edge detection,” IEEE
Transactions on Pattern Analysis and Machine Intelligence,
8(6):679-698, 1986
[6] A. Criminisi*,P.Perez and K. Toyama,”Region Filling and Object
Removal by Exemplar-Based Image Inpainting,” IEEE Transactions
on Image Processing, vol. 13, NO. 9, Sep 2004.
[7] I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon, ”Secure spread
spectrum watermarking for multimedia,” IEEE Trans. Image Processing,
vol. 6, Dec. 1997, pp. 1673-1687.
[8] C.S. Lu, S. K. Huang, C. J. Sze, and H. Y. M. Liao, ”Cocktail
watermarking for digital image protection,” IEEE Trans. Multimedia,
vol. 2, Dec. 2000, pp. 209-224.
[9] C. T. Hsu and J. L. Wu, ”Multiresolution watermarking for digital
image, ” IEEE Trans. Circuits Syst. Ⅱ, vol. 45, Aug. 1998, pp. 206-216.
[10] C. T. Hsu and J. L. Wu, ”Hidden digital watermarks in images,” IEEE
Trans. Image Processing, vol. 8, Jan. 1999, pp. 55-68.
[11] C. S. Lu and H. Y. M. Liao, ”Multipurpose watermarking for image
authentication and protection,” IEEE Trans. Image Processing, vol. 10,
Oct. 2001, pp. 1579-1592.
[12] Y. J. Zhagn, T. Chen, and J. Li, ”Embedding watermarks into both DC
and AC components of DCT,” in Proc. SPIE Security and Watermarking
of Multimedia Contents Ⅲ, Jan. 2001, pp. 424-435.
[13] S. Stankovic, I. Djurovic, and I. Pitas, ”Watermarking in the
space/spatial-frequency domain using two-dimensional Radon-Wigner
distribution,” IEEE Trans. Image Processing, vol. 10, Apr. 2001, pp.
650-658.
[14] W.N. Lie, G. S. Lin, C. L. Wo, and T. C. Wang, ”Robust image
watermarking on the DCT domain,” in Proc. IEEE Int. Symp. Circuits
and Systems, vol. 1, May 2000, pp.228-231.
[15] Rafael C. Gonzalez, Richard E. Woods and Steven L. Eddins 著,
繆紹剛 譯, “數位影像處理-運用MATLAB,” 東華書局,2005
[16] Alasdair McAndrew 著,徐曉珮 譯,”數位影像處理,” 高立圖書有限
公司,2005