貝蘇章臺灣大學：電信工程學研究所張家漢Chang, JahanJahanChang2007-11-272018-07-052007-11-272018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/58915中文摘要 隨著數位相機與網際網路的普及, 每天都有大量的彩色影像產生並且在個各地方傳遞◦ 然而現在卻沒有什麼工具可以直接來對這些彩色影像來做處理◦ 唯一的做法只有先將一張彩色影像分解成三張灰階的影像, 然後使用傳統處理灰階影像的一些方法, 如傅立葉轉換, convolution, correlation與 特徵值分解…等等, 來分別獨立地處理與分析這三張灰階影像◦ 直到近年來有些研究人員提出使用超複數來表示色影像後, 才有新的分法出現◦ 藉由超複數代數, 我們可以對多度空間的信號, 定義超複數的傅立葉轉換, convolution and correlation…等等運算, 並且發展出這些運算的快速演算法◦ 因此我們可以利用超複數代數與其運算來直接分析處理彩色影像而不需要將彩色影像分解成三張分開的灰階影像◦ 對彩色影像, 我們可以使用四維的超複數來表示彩色影像◦ 有兩種可能的超複數可以供我們選擇來做彩色影像處理◦ 他們是四元數(不可交換性代數)和退化四元數(可交換性代數) ◦ 四元數比退化四元數先被提出來並且具有清楚的幾何意義◦ 不過四元數的乘法不具有交換性◦ 因為這個性質, 四元數的傅立葉轉換, convolution, correlation 以及四元數矩陣的特徵值分解…等等運算的複雜度變得非常大◦ 另一方面 雖然退化四元數較晚被提出來並且大部分的工程師都對他不熟悉, 但是因為他的乘法具有交換性所以退化四元數的傅立葉轉換, convolution, correlation 以及四元數矩陣的特徵值分解…等等運算的複雜度比四元數的簡單釵h◦ 此外, 幾乎所有四元數所能做到的彩色影像的應用, 如: 彩色影像的傅立葉轉換, 邊界偵測, 特定顏色的邊界偵測, 以及彩色物件比對…等等, 退化四元數也都能夠做得到◦ 因此, 我們認為使用退化四元數來表示彩色影像以及來做彩色影像處理會比用四元數來的好以及有效率◦ 在這篇論文中, 我們將會推導出四元數與退化四元數的傅立葉轉換, convolution, correlation 以及四元數與退化四元數矩陣的特徵值分解…等等運算的快速演算法, 然後比較兩者之間的表現優劣◦ 藉由這些工具, 我們可以直接來分析彩色影像而不需要將其分解三張灰階影像◦ 藉由超複數的傅立葉轉換, 我們可以去分析彩色影像在頻譜上的分佈情形; 藉由超複數的convolution, correlation , 我們可以去比較兩張彩色影像之間的相關性, 並可以做彩色物件比對; 藉由特徵值分解, 我們可以對彩色影像作壓縮, 對比增強, 減弱, 以及在彩色影像中加入彩色的數位浮水印◦ 從這份論文中的實驗結果, 我們可以發現使用四元數或是退化四元數來表示彩色影像可以做出釵h新的彩色影像的應用◦ 我們相信四元數與退化四元數對彩色影像的處理是非常有幫助的◦Abstract As the digital camera and the internet getting more and more common and popular, many color images are largely produced and transmitted everyday and everywhere. However, there does not exist tools to directly analyze the color image. The only way to perform color image processing is to decompose the color image into three channel gray images and analyze the three gray images separately and independently by the conventional gray image processing methods, such as Fourier transform, convolution, correlation and singular value decomposition, etc, until some researchers use the Hypercomplex numbers to represent the color image. By means of the Hypercomplex algebra, we can define the Hypercomplex Fourier transform, convolution and correlation, etc, for multi-dimensional signal processing and develop the efficient implementation algorithms for these operations. Therefore, we can use the Hypercomplex algebra and operations to directly process the color image without decomposing the color image into three channel gray images. For color image processing, we can use the 4-dimensional Hypercomplex numbers to represent the color image. There are two possible Hypercomplex numbers, quaternions (non-commutative algebra) and reduced biquaternions (commutative algebra), can be used for color image processing. Quaternions are proposed earlier than reduced biquaternions and have clear geometric meaning. However, quaternions are not commutative. Due to this property, the complexity of the quaternion Fourier transform, convolution, correlation and singular value decomposion of a quaternion matrix are very complicated. On the other hand, although the reduced biquaternions are proposed later and are not familiar to the most engineers, the reduced biquaternions are commutative algebra. Therefore, the complexity of the reduced biquaternion Fourier transform, convolution, correlation and the singular value decomposition of a reduced biquaternion matrix are much simpler than the ones of quaternions. Besides, almost all the color image applications by using quaternions, such as Fourier transform of a color image, color image edge detection, color sensitive edge detection, color image correlation and color template matching etc, can be performed by using reduced biquaternions. Consequently, we think using reduced biquaternions to represent the color image is better using quaternions. In this thesis, we will develop the efficient implementation algorithms of the quaternion and redcued biquaternion Fourier transform, convolution and correlation, and the efficient algorithms of the eigenvalue decomposition and singular value decomposition of a quaternion matrix or a reduced biquaternion matrix. Then we will compare the performance of the quaternions and reduced biquaternoins. By means of these tools, we can directly analyze the color image without decomposing the color image into three channel image. By the Hyercomplex Fourier transform, we can analyze the property of a color image in frequency domain. By the Hypercomplex convolution and correlation, we can analyze the relations between two color images and perform the color template matching. By the singular value decomposition, we can perform the color image compression, enhancement, smoothing, and color image watermarking. From the experimental results, we can find that using the Hypercomplex numbers, quaternions or reduced biquaternions, to represent the color image will produce many new color image applications. We believe that quaternions and reduced biquaternions are useflul for color image processing.Contents Part 1： Introduction Chapter 1 Introduction ……………………………………………. 1-1 Chapter 2 Introduction of Hypercomplex numbers ……………... 2-1 2.1 Introduction ………………………………………………… 2-1 2.2 Generalized Complex Numbers …………………………… 2-2 2.2.1 Dual Numbers ………………………………………. 2-3 2.2.2 Double Numbers ……………………………………. 2-4 2.3 Doubling Procedure ………………………………………... 2-6 2.4 Hypercomplex Numbers …………………………………… 2-7 2.5 Conclusion ………………………………………………….. 2-10 Part 2： Non-Commutative Hypercomplex -- Quaternions Chapter 3 Quaternion Algebra ……………………………………. 3-1 3.1 Introdcution…………………………………………………. 3-1 3.2 The Quaternion Algebra …………………………………... 3-1 3.2.1 Definition of quaternions from the doubling procedure… …………………………………………………………… 3-4 3.3 The Geometric Meaning of Quaternions …………….…… 3-5 3.3.1 Quaternions and vector algebra …………………… 3-5 3.3.2 The polar form of quaternions …………………….. 3-7 3.3.3 Three Dimensional Rotation by quaternions ……… 3-10 3.3.4 Composition of rotations by means of quaternions 3-14 3.4 Conclusion …………………………………………………. 3-15 Chapter 4 Quaternion Fourier Transform ……………………….. 4-1 4.1 Introduction ………………………………………………… 4-1 4.2 Quaternion Fourier Transform ……………………………. 4-2 4.3 Efficient Implementation of Quaternion Fourier Transform …………………………………………………………………4-5 4.3.1 Implementation of QFT of type 1 ………………….. 4-5 4.3.2 Implementation of QFT of type 2 and 3 …………… 4-8 4.4 Quaternion Convolution …………………………………… 4-10 4.4.1 One-side and Two-side Quaternion Convolution and their implementation ……………………………….. 4-10 4.4.2 Spectrum-Product Quaternion Convolution and its implementation ……………………………………… 4-17 4.5 Quaternion Correlation ……………………………………. 4-23 4.6 Conclusion ………………………………………………….. 4-25 4.7 Appendix ……………………………………………………. 4-26 Chapter 5 Quaternion Matrix …………………………………….. 5-1 5.1 Introduction ………………………………………………… 5-1 5.2 Eigenvalues and Eigenvectors of a Quaternion Matrix …. 5-2 5.3 Singular Value Decomposition of a Quaternion Matrix …. 5-6 5.4 The Quaternion Matrix and the Quaternion Polynomial .. 5-9 5.4.1 The nth Roots of a Quaternion …………………….. 5-9 5.4.2 The Zeros of a Quaternion Polynomial ……………. 5-10 5.5 Conclusion ………………………………………………….. 5-12 Chapter 6 Applications of Quaternions for Digital Signal and Color Image Processing ……………………………………………. 6-1 6.1 Introduction ………………………………………………… 6-1 6.2 Quaternion Linear Time-Invariant System Analysis ……. 6-2 6.2.1 Using QFT for quaternion linear time-invariant system analysis ……………………………………………… 6-2 6.2.2 Simplifying the QLTI system analysis and quaternion filter design …………………………………………. 6-6 6.3 Color Image Edge Detection ………………………………. 6-8 6.4 Color Sensitive Edge Detection ……………………………. 6-15 6.5 Color Pattern Recognition …………………………………. 6-19 6.6 Singular Value Decomposition of a Color Image …………. 6-32 6.7 Color Image Watermarking ……………………………….. 6-37 6.7.1 Gray Image Watermarking Based on Conventional SVD ………………………………………………………... 6-38 6.7.2 Color Image Watermarking Based on Quaternion SVD ………………………………………………………… 6-40 6.7.3 Twin-Watermarking Based on Quaternion SVD …. 6-42 6.7.4 Experiments of color image watermarking and twin- watermarking ……………………………………….. 6-44 6.8 3D Rotation …………………………………………………. 6-51 6.8.1 3D Rotation Matrix …………………………………. 6-51 6.8.2 Eular Angles …………………………………………. 6-52 6.8.3 Qauternions …………………………………………. 6-53 6.9 Conclusion …………………………………………………... 6-56 6.10 Appendix …………………………………………………... 6-57 Part 3：Commutative Hypercomplex -- Reduced Biquaternions Chapter 7 Reduced Biquaternion Algebra ……………………….. 7-1 7.1 Introduction ………………………………………………… 7-1 7.2 The Reduced Biquaternion Algebra ………………………. 7-2 7.2.1 e1 - e2 form of Reduced Biquaternions …………….. 7-3 7.2.2 Matrix representation of a Reduced Biquaternion .. 7-4 7.2.3 Norm and Conjugation of Reduced Biquaternions .. 7-6 7.3 Polar form of Reduced Biquaternions …………………….. 7-8 7.3.1 The polar form of Reduced Biquaternions ………... 7-8 7.3.2 Properties of the polar form of Reduced Biquaternions ……………………………………………………….. 7-11 7.3.3 Relations among the e1-e2 form, matrix representation and polar form ……………………………………… 7-13 7.3.4 Simplified polar form – Color Image representation 7-14 7.4 Conclusion …………………………………………………... 7-17 Chapter 8 Reduced Biquaternion Fourier Transform, Convolution and Correlation ………………………………………... 8-1 8.1 Introduction ………………………………………………… 8-1 8.2 Discrete Reduced Biquaternion Fourier Transform ……... 8-2 8.3 Efficient Implementation of the Discrete Reduced Biquaternion Fourier Transform …………………………. 8-3 8.3.1 Implementation of the DRQFT of type 2 …………. 8-3 8.3.1 Implementation of the DRQFT of type 1 …………. 8-3 8.4 Reduced Biquaternion Convolution ……………………… 8-5 8.5 Reduced Biquaternion Correlation ………………………. 8-7 8.6 Conclusion …………………………………………………. 8-8 Chapter 9 Reduced Biquaternion Matrix ………………………… 9-1 9.1 Introduction ………………………………………………… 9-1 9.2 The Reduced Biquaternion Matrix ……………………….. 9-2 9.3 Eigenvalues and Eigenvectors of a Reduced Biquaternion Matrix ………………………………………………………… 9-3 9.4 Singular Value Decomposition of a Reduced Biquaternion Matrix ………………………………………………………… 9-9 9.5 The Reduced Biquaternion Matrix and Polynomial ……... 9-11 9.5.1 The nth Roots of a Quaternion ……………………. 9-11 9.5.2 The Zeros of a Quaternion Polynomial …………… 9-16 9.6 Conclusion ………….………………………………………. 9-20 Chapter 10 Applications of Reduced Biquaternions for Digital Signal and Color Image Processing ………………………………… 10-1 10.1 Introduction ……………………………………………….. 10-1 10.2 Symmetric Multi-channel System Analysis ……………... 10-2 10.3 Color Template Matching ………………………………… 10-5 10.4 Sensitive Color Image Edge Detection …………………. 10-19 10.4.1 Color Sensitive Edge Detection for One Selected Color ………………………………………………………10-19 10.4.2 Color Sensitive Edge Detection between Two Selected Colors …………………………………………….. 10-23 10.5 Singular Value Decomposition of a Color Image ………. 10-27 10.6 Conclusion ………………………………………………... 10-31 Part 4： Conclusion and Reference Chapter 11 Conclusion and Future Work ………………………… 11-1 Reference4374284 bytesapplication/pdfen-US數位影像處理傅立葉轉換超複數數位信號處理四元數退化四元數hypercomplexFourier transform, digital signal and image processingular value decompositionquaternionreduced biquaternionthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58915/1/ntu-93-F88942016-1.pdf