數位影像修復與多重浮水印技術

Digital Image Recovery and Multiple-Watermarking Techniques

曾易聰(Yi-Chong Zeng)

指導教授 ： 貝蘇章

國立臺灣大學/電機資訊學院/電信工程學研究所/博士(2006年)

https://doi.org/10.6342/NTU.2006.00424

摘要

本論文的研究主題在於整合數位影像處理方法與浮水印技術，並且將該些方法應用在數位影像與影片中。研究主題包含三大部分：（一）影像修復、色彩化和增強之研究；（二）多重浮水印技術之研究；（三）影像修復與多重浮水印技術整合之研究。所有章節的摘要分別描述如下：

第一章　影像修復
「空隙紋理合成」(lacuna texture synthesis)的功用在於針對古老的中國畫作和數位影像進行虛擬修復之研究。該方法是利用紋理貼片技術，並且使用馬可夫隨機場模組。首先，我們移除不想要的圖案，例如：污點、裂縫和人工添加物，然後在圖案移除後所留下的空白區域內填補適當的紋理。該演算法除了保持影像內物件的外型完整性，並且可以防止邊界的不連續性。

第二章　可視性浮水印移除
在本章中，提出一種移除可視性浮水印的影像修復演算法。本演算法利用「獨立成分分析」(independent component analysis, ICA)，將原始影像從浮水印影像和參考影像中分離出來。在本研究中，我們進行現有的三種常用的「獨立成分分析」方法與五種不同的可視性浮水印埋藏技術的實驗。從結果中將展示無論是哪種「獨立成分分析」以及埋藏技術都可成功地移除可視性浮水印。此外，我們也取得公共網路上的浮水印影像，並成功地移除影像上的浮水印。

第三章　影像色彩化
以往，畫家使用黑色的墨水來呈現中國水墨畫中多樣的景色與物件，包括：山景、水景、動物、植物…等等。在本章中，將介紹一種有效的影像色彩化方法，將原有中國水墨畫予以填入色彩。該方法不但比傳統的方法需要更少的運算時間，同時可以在水墨畫中保有柔和的漸層色調，包含：水流、煙霧、雲朵、瀑布、陰影…等等。

第四章　影像增強
我們將在本章中介紹「加權式直方統計圖分離法」(weighted histogram separation, WHS)，並且利用其強化高動態範圍影像(high dynamic range image)的色調。該方法的特性介於連續性平均量化轉換和直方統計圖等化兩種技術之間。此外，提出的方法亦可應用在影像的局部增強，我們稱之為「適應性加權式直方統計圖分離法」(adaptive weighted histogram separation, AWHS)。

第五章　空間領域多重浮水印演算法
我們在資訊安全上的研究目標是發展一種多重浮水印的埋藏與擷取演算法，稱之為「空間領域多重浮水印演算法」(spatial domain multiple-watermarking algorithm)。該演算法屬於一種量化索引調變技術(quantization index modulation)，其可以將二重浮水印或是三重浮水印埋入原始影像當中。此外，從擷取出來的浮水印不但可以用來偵測影像中被竄改的區域，同時也可以用來進行攻擊的分類與辨識之研究。

第六章　雙領域二重浮水印演算法
「雙領域二重浮水印演算法」(dual domain bi-watermarking algorithm)主要是在離散餘弦轉換領域上運作，將二重浮水印埋入原始影像內，是空間領域的二重浮水印演算法的一種延伸技術。然而，該方法卻可以在空間領域和離散餘弦轉換領域上，從影像中擷取出二重浮水印。同樣地，從二重浮水印中分解出來的兩個浮水印，對於不同的影像壓縮率展現出不同的能力，另外該兩個浮水印對於總體性攻擊和區域性攻擊也會反應出不同的強健性。

第七章　2.5領域三重浮水印演算法
在本章中，我們將介紹整合雙領域二重浮水印演算法和視覺密碼學所衍生出來的新技術，稱之為「2.5領域三重浮水印演算法」(2.5 domain tri-watermarking algorithm)。這個演算法是在離散餘弦轉換空間中運作，將三重浮水印埋藏在影片中，但是三重浮水印卻可以在空間領域和離散餘弦轉換領域的影片中擷取出來。從三重浮水印中分解出來的三個浮水印，對於各類的攻擊也會呈現出不同的強健性。計算該三個浮水印的位元錯誤率，我們甚至可以分辨影片是受到空間領域的攻擊或是時間領域上的攻擊。

第八章　影像修復與浮水印演算法的整合
本章的重點是整合影像修復與浮水印技術。我們利用空間領域二重浮水印演算法，將縮小版原始影像的半色調影像當作浮水印埋藏在原始影像中。然後從浮水印影像中擷取出來的二重浮水印，經由線性規劃法(linear programming)與二次規劃法(quadratic programming)的反向半色調處理(inverse halftoning)，我們可以獲得相似的灰階影像。此外，二重浮水印不止可以偵測影像中被竄改的區域，同時也可以將該區域修復成近似原始影像的狀態。

第九章 線性規劃法的研究與應用
在1736年，偉大的數學家歐拉發表一篇論文解決柯尼斯堡鎮七座橋樑的問題，並且把該問題轉換成圖論模式加以探討。這就是著名的歐拉路徑(Euler circuit)問題。在本章中，我們則是使用混合整數型態的線性規劃法(mix-integer linear programming)來解決非歐拉路徑的問題，把非歐拉路徑轉換成歐拉路徑。再者，二元整數規劃法(binary integer programming)則是用來決定圖樣中各個邊界的方向性。實驗結果中將展示演算法在多種領域上的應用，包括：路徑規劃、連續性線條畫作和實體產品的製作。

第十章　結論與未來展望
最後，我們將總結上述章節中提出的各種方法，並且討論可能的改良方式與應用領域。

關鍵字

影像修復 ； 影像色彩化 ； 影像增強 ； 浮水印技術 ； 線性規劃法

並列摘要

The research topic of this paper is to integrate the digital image processing schemes and the watermarking techniques, and those methods will apply on the digital images and digital videos. The research topic includes three parts: (1) image recovery, colorization and enhancement, (2) multiple-watermarking techniques, and (3) the integration of image recovery and multiple-watermarking techniques. The abstracts of all chapters are described below:

Chapter 1 – Image Recovery
The lacuna texture synthesis is proposed for the virtual restoration of ancient Chinese paintings and digital images. Lacuna texture synthesis is a patching method, which uses the Markov Random Field (MRF) model. We eliminate the undesirable patterns, such as stains, crevices, and artifacts, and the algorithm fills the lacuna regions with the appropriate textures. The proposed scheme not only maintains a complete shape, but also prevents the edge disconnection in the final results.

Chapter 2 – Visible Watermark Removal
In this chapter, an image recovery algorithm for removing visible watermarks is presented. Independent component analysis (ICA) is utilized to separate source images from watermarked and reference images. Three independent component analysis approaches and five different visible watermarking methods are examined in our study. The experimental results will show that visible watermarks are successfully removed, and that the proposed algorithm is independent of both the adopted ICA approach and the visible watermarking method. Moreover, several watermarked images sourced from various websites are removed the watermarks successively.

Chapter 3 – Image Colorization
In the past, the artists adopted the black ink to represent various sights and objects in Chinese ink-and-wash, such as, mountain scenery, waterscape, animals, plants, etc. This chapter will introduce an effective method to colorize the Chinese ink-and-wash paintings. The proposed method not only takes fewer computing time than the conventional method, but it also can preserve the soft-gradual tone in the ink-and-wash paintings, such as, water-flowing, smog, cloud, waterfall, and shadow etc.

Chapter 4 – Image Enhancement
We will introduce the weighted histogram separation (WHS) in this chapter, which is presented to enhance the high dynamic range images. The property of weighted histogram separation situates between the successive mean quantization transform and the histogram equalization. Additionally, the proposed method is further applied to the local enhancement, which is termed as the adaptive weighted histogram separation (AWHS).

Chapter 5 – Spatial Domain Multiple-watermarking Algorithm
The objective of our study in information security is to develop a multiple watermarks embedding and extraction algorithm, which is called as spatial domain multiple-watermarking algorithm. This algorithm is one kind of quantization index modulation, it can impose bi-watermark or tri-watermark on the host image. Furthermore, the extracted watermarks not only are exploited to detect the tampered areas, but it is also used for attack classification and attack identification.

Chapter 6 – Dual Domain Bi-watermarking Algorithm
A dual domain bi-watermarking algorithm embeds bi-watermark into the host image in discrete-cosine-transform domain (DCT), and it is the extension of the spatial domain bi-watermarking algorithm. However, the bi-watermark can be extracted from both spatial domain and DCT domain. By the same token, two separated watermarks from the extracted bi-watermark have different capability for various compression rates, and they also reveal the different robustness against the global and the regional attacks.

Chapter 7 – 2.5 Domain Tri-watermarking Algorithm
In this chapter, we will introduce an integration of dual domain bi-watermarking algorithm and visual cryptography, which is named as 2.5 domain tri-watermarking algorithm (2.5D-TW). This algorithm implements tri-watermark embedding in discrete-cosine-transform domain (DCT) for video protection, but the tri-watermark can be extracted from both spatial domain and DCT domain. Three separated watermarks from the extracted tri-watermark reveal the different robustness against various attacks. According to the bit error rates of those three watermarks, the algorithm even identifies whether the attack is occurred in spatial domain or in temporal domain for video.

Chapter 8 – Integration of Image Recovery and Watermarking Algorithm
The key of this chapter is to integrate the image recovery scheme and the watermarking technique. The spatial domain bi-watermarking algorithm is used to add the halftone of downscaled host image into the host image. After extracting the bi-watermark from the covered image, the bi-watermark is restored to the gray-scale image using the proposed inverse halftoning, which utilizes the linear programming and quadratic programming. Furthermore, the bi-watermark is not only exploited to detect the tampered areas without prior data, but it also can be applied to recover the tampered areas in the tampered image.

Chapter 9 – Linear Programming and Its Applications
In 1736, the great mathematician Leonhard Euler published a paper to solve the problem of seven bridges of Königsberg, and he translated it into the graph theory problem. This study is the well-known Euler circuit problem. Here, we solve non-Euler circuit problem using mix-integer linear programming, which transforms the non-Euler circuit to the Euler one. In addition, the binary integer programming is exploited to determine the edge direction. The experimental results will show that the proposed scheme can be applied to the route planning, the continuous line drawing and the real-object production.

Chapter 10 – Conclusions and Future Works
Consequently, we will summarize the previous researches and describe the possible improvement and applications in the future works.

並列關鍵字

image recovery ； image colorization ； image enhancement ； watermarking technique ； linear programming

參考文獻

[1] William K. Pratt, Digital Image Processing, 3rd Ed., John Wiley & Sons Inc., New York, 2001.

[2] A. Efros, and T. K. Leung, “Texture synthesis by non-parametric sampling,” IEEE Int’l. Conf. on Computer Vision, vol. 2, pp.1033-1038, Sept. 1999.

[3] L.-Y. Wei, and M. Levoy, “Fast texture synthesis using tree-structured vector quantization,” In Proc. of SIGGRAPH, pp.479-488, July 2000.

[4] D. J. Heeger, and J. R. Bergen, “Pyramid-based Texture Analysis/Synthesis,” In Proc. of SIGGRAPH, pp.229-238, Aug. 1995.

[5] J. S. De Bonet, “Multiresolution sampling procedure for analysis and synthesis of Texture Images,” In Proc. of SIGGRAPH, pp.361-368, Aug. 1997.