臺灣博碩士論文加值系統

非失真影像編碼在許多場合皆有其應用之需求性；例如醫學影像編碼、遠端感測，以及影像壓縮等。在進行非失真影像編碼過程中，如何有效地移除統計累贅至今仍是訊號源編碼研究領域的一個主要挑戰課題。因此已有許多關於非失真影像編碼的方法被提出。其中有部分的研究係使用可還原小波轉換。然而由各項文獻中可以發現，使用轉換編碼所得到的結果往往卻不若以空間域之預測編碼結合環境建模（predictive coding with context modeling in spatial domain）所得到之結果來的好。

在本篇論文中，我們將針對近年來非失真影像編碼之概況做一簡介。此外我們亦將提出一基於線性預測之架構並以最小平方法進行此預測器係數之修正。由於使用最小平方法進行預測器係數之修正具有所謂邊界導向之特性（edge-directed characteristic），因此對於位處影像邊界附近像素之預測具有非常良好的效果。然而若將整張圖像皆以最小平方法進行預測器係數之修正勢將導致極高之複雜度，因此我們提出當編碼過程遭遇影像之邊界時才以最小平方法進行預測器係數之修正；如此運算複雜度將可大幅地降低。為了能夠於編碼過程中事先偵測影像邊界之存在與否，我們提出了一個非常簡易、有效而且僅使用已掃瞄/編碼像素（causal pixels）的邊界偵測法。如此一來我們的系統便可以預知影像邊界存在與否，並在遭遇邊界時，事先以最小平方法進行預測器係數之修正以防範較大預測誤差之發生。在我們所提出的方法中僅使用到已掃瞄/編碼像素來進行預測編碼；因此並無需傳送額外之資訊。經由實驗證明，我們所提出的方法能夠有效地在預測結果與運算複雜度之間取得良好的平衡點。此外我們也透過大量的實驗並針對當前非失真影像壓縮領域最先進的預測器（predictor）與編碼器（coder）進行比較來證明所提出方法之可用性。

除上述所提出具邊界前瞻（edge-look-ahead）能力之非失真預測編碼架構外，我們發現較大的預測誤差通常好發於影像中具有邊界之處。因此，我們在本篇論文中提出一創新概念，亦即利用控制工程的技術來改進影像中位於邊界附近像素之預測結果。之所以有這樣的想法是因為我們瞭解控制系統的目的本就是希望系統的輸出能夠準確地遵循所輸入之控制命令；因此在目的上與預測編碼是一致的。此外影像中的邊界（亦即像素的急速變化）亦可視為控制系統中的步階命令（step command）。基於前述的觀察使我們產生了嘗試以控制方法來改進預測編碼效能的想法。為了實現這樣想法，我們也以Takagi以及Sugeno兩位學者所提出之模糊類神經網路實做了一適應性預測編碼架構。此外我們也將控制領域中經常被使用的Proportional Controller（P型控制器）實現於此一模糊類神經網路中以強化影像中位於邊界像素之預測結果。我們發現這樣的作法對於預測編碼的效能改善確實是有所幫助的；雖然目前的改進效果並不是那麼地顯著，但是這樣的概念的確為非失真影像預測編碼領域開啟了一個全然不同的問題思考以及解決方式。

Lossless image coding is required by many applications, such as medical imaging, remote sensing, and image archiving. It has remained a major challenge to source coding community for the difficulty of removing statistical redundancy effectively and efficiently. Therefore, many approaches have been proposed for lossless compression of images. Among proposed approaches, some of which are based on reversible transform coding, like integer wavelet transformation. However, we find in literatures that the results obtained by using transform coding are typically inferior to that of obtained by predictively encoded techniques with context modeling in spatial domain.

In this dissertation, an introduction on recent advances in lossless image coding will be given. Moreover, we will propose an approach based on linear predictive coding with least-squares (LS) optimization for the adaptation of predictor coefficients. The LS-based adaptive predictor, for its edge-directed characteristic, has been shown to be useful for the prediction of pixels around boundaries. Instead of performing LS adaptation in a pixel-by-pixel manner, we adapt the predictor coefficients only when an edge is detected so that the computational complexity can be significantly reduced. For this, we propose a simple yet effective edge detector using only causal pixels. This way, the proposed system can look ahead to determine if the coding pixel is around an edge and initiate the LS adaptation in advance to prevent the occurrence of a large prediction error. Furthermore, only causal pixels are used for estimating the coding pixels in the proposed encoder; no additional side information needs to be transmitted. As we will see later in the experiments, a very good trade-off between prediction results and the computational complexity can be obtained with the proposed approach. Besides, extensive experiments as well as comparisons to existing state-of-the-art predictors and coders will be given to demonstrate the usefulness of the proposed approach.

In addition to the proposed edge-look-ahead approach, we find a large prediction error can usually take place for pixels around boundaries. Therefore, we also propose in this dissertation a novel concept of using control technologies to improve prediction result for pixels around boundaries. This idea comes from the fact that the purpose of a control system is to follow the input command as precisely as possible, which has the same objective with predictive coding. Moreover, an edge or a boundary can be regarded as a step command in control system. The above observations lead to the idea of solving this problem using control technologies. To realize this idea, we also implement an adaptive predictor using Takagi-Sugeno fuzzy neural network (TS-FNN). Moreover, the widely used proportional controller in control theory is applied implicitly in the consequent part of the network as a compensator to enhance the prediction result around edges. The effectiveness of the proposed novel approach, though not very conspicuous at present, can be further improved if a more sophisticated compensator is applied, and what's more, we have brought up an idea of solving this problem in a quite different aspect for lossless compression of images.

Abstract (in Chinese) i
Abstract (in English) iii
Acknowledgement (in Chinese) v

1 Introduction 1
1.1 Advances in Lossless Image Coding 2
1.2 The Proposed approach 6
1.3 Outline of the Dissertation 7

2 Least-squares Based Adaptive Predictor with Edge-look-ahead 8
2.1 An Overview of the Proposed System 9
2.2 Edge-directed Characteristic of LS adaptation 13
2.3 Proposed Edge Detector 16
2.4 Least-squares Based Adaptive Prediction 18
2.5 Prediction Error Refinement 21
2.6 Concluding Remarks 23

3 Entropy Coding of Prediction Errors 25
3.1 Conditional Entropy Coding 26
3.2 Further Manipulations on the Refined Errors 28
3.2.1 Error Sign Flipping 28
3.2.2 Error Remapping 28
3.2.3 Histogram Tail Truncation 29
3.3 Concluding Remarks 31

4 Experiments 32
4.1 The Edge Detector 33
4.1.1 Comparison with ``Sobel” Operator 35
4.1.2 Texture context for Edge Detection 37
4.2 Error compensation 42
4.3 Order of predictor 48
4.4 Effectiveness of the Edge-look-ahead mechanism 49
4.5 Comparisons to existing predictors 51
4.6 LS adaptation 54
4.7 Further insight on the proposed edge-look-ahead mechanism 55
4.8 Comparisons to existing state-of-the-art coders 58
4.9 Computational complexity 60
4.10 Concluding Remarks 62

5 Enhancing the Predictive Coding Efficiency with Control Technologies 64
5.1 Introduction 66
5.2 Proposed TS-FNN based coding system 70
5.2.1 The TS-FNN based adaptive predictor 71
5.2.2 Network Adaptation process 76
5.3 Entropy Coding of Prediction Errors 84
5.4 Experiments 86
5.4.1 The network parameters 86
5.4.2 The training area for network adaptation 88
5.4.3 The ``P-controller” based compensation mechanism 89
5.4.4 Comparisons to existing predictors 92
5.4.5 The error compensation mechanism 94
5.4.6 Comparisons to existing state-of-the-art coders 95
5.4.7 Computational complexity of the proposed approach 98
5.5 Concluding Remarks 100
6 Conclusion 101

Bibliography 103
Appendix 109
A Pseudo Code of the Proposed Edge-look-ahead Approach 110
B Matlab Code for Sobel operator 113
C Pseudo Code of the P-Controller Compensation Approach 115

Vita 121
Publication List 124

[1] Khalid Sayood, Introduction to Data Compression, Morgan-Kaufmann, 2nd Edition, pp. 139-163, 2000.
[2] K. R. Rao and J. J. Hwang, Techniques & Standards For Image, Video & Audio Coding, Prentice-Hall, pp. 31-42, 1996.
[3] B. Carpentieri, M. J. Weinberger, and G. Seroussi, ``Lossless compression of continuous-tone images,” Proc. IEEE, Vol. 88, No. 11, pp. 1797-1809, Nov. 2000.
[4] N. Memon and X. Wu, ``Recent developments in context-based predictive techniques for lossless image compression,” Comput. J., Vol. 40,No. 2/3, pp. 127-136, 1997.
[5] Xiaolin Wu, ``An algorithmic study on lossless image compression,” Proc. Data Compression Conf., Snowbird, UT, USA, pp. 150-159, 31 March 3 April 1996.
[6] X. Wu and T. Qiu, ``Wavelet Coding of Volumetric Medical Images for High Throughput and Operability,” IEEE Trans. Medical Imaging, Vol.24, No. 6, pp. 719-727, Jun. 2005.101
[7] A. T. Deever and S. S. Hemami, ``Lossless Image Compression With Projection-Based and Adaptive Reversible Integer Wavelet Transforms,” IEEE Trans. Image Process., Vol. 12, No. 5, pp. 489-499, May 2003.
[8] M. Grangetto, E. Magli, M. Martina, and G. Olmo, ``Optimization and Implementation of the Integer Wavelet Transform for Image Coding,” IEEE Trans. Image Process., Vol. 11, No. 6, pp. 596-604, Jun. 2002.
[9] N. V. Boulgouris, D. Tzovaras, and M. G. Strintzis, ‘Lossless image compression based on optimal prediction, adaptive lifting, and conditional arithmetic coding,” IEEE Trans. Image Process., Vol. 10, No. 1,pp. 1-14, Jan. 2001.
[10] J. Reichel, G. Menegaz, M. J. Nadenau, and M. Kunt, ``Integer Wavelet Transform for Embedded Lossy to Lossless Image Compression,” IEEE Trans. Image Process., Vol. 10, No. 3, pp. 383-392, Mar. 2001.
[11] N. Memon, X. Kong, and J. Cinkler, ``Context-based lossless and near lossless compression of EEG signals,” IEEE Trans. Information Technology in Biomedicine, Vol. 3, pp. 231-238, Sept. 1999.
[12] K. H. Yang and A. F. Faryar, ``A contex-based predictive coder for lossless and near-lossless compression of video,” in Proc. IEEE Int. Conf. Image Process., Vol. 1, pp. 144-147, Sept. 10-13, 2000.
[13] X. Y. Lin, L.-K. Shark, M. R. Varley, and B. J. Matuszewski, ``A hybrid lossless compression scheme using region-based predictive coding and integer wavelet transform,” in Proc. IEEE Int. Conf. Image Process., Vol. 3, pp. 486-489, Oct. 7-10, 2001.
[14] X.Wu and N.Memon, ``Context-based, adaptive, lossless image coding,” IEEE Trans. Communications, Vol. 45, No. 4, pp. 437-444, April 1997.102
[15] M. J. Weinberger, G. Seroussi, and G. Sapiro, ``The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS,” IEEE Trans. Image Process., Vol. 9, No. 8, pp. 1309-1324, Aug. 2000.
[Online].Available: http://www.hpl.hp.com/loco/locodownold.htm
[16] G. Motta, J. A. Storer, and B. Carpentieri, ``Lossless image coding via adaptive linear prediction and classification,” Proc. IEEE, Vol. 88,No. 11, pp. 1790-1796, Nov. 2000.
[17] I, Avcibas, N. Memon, B. Sankur, and K. Sayood, ‘A Successively Refinable Lossless Image-Coding Algorithm,” IEEE Trans. Communications, Vol. 53, No. 3, pp. 445-452, Mar. 2005
[18] M. K. Das, C. C. Li, and S. R. Burgett, ``A new multiresolution predictive scheme for lossless compression of medical images,” Proc. IEEE Int. Symp. Computer-Based Medical Systems, pp. 34-39, June 13-16, 1993.
[19] X. Wu, ``Lossless compression of continuous-tone images via context selection, quantization, and modeling,” IEEE Trans. Image Process., Vol. 6, No. 5, pp. 656-664, May 1997.
[20] B. Meyer and P. E. Tischer, ``TMW-a new method for lossless image compression,” in Proc. Int. Picture Coding Symp., Berlin, Germany, Oct. 1997.
[21] B. Aiazzi, L. Alparone, and S. Baronti, ``Fuzzy logic-based matching pursuits for lossless predictive coding of still images,” IEEE Trans. Fuzzy Systems, Vol. 10, No. 4, pp. 473-483, Aug. 2002.103
[22] R. D. Dony, and S. Haykin, ``Neural network approaches to image compression, ”Proc. IEEE, Vol. 83, No. 2, pp. 288-303, Feb. 1995.
[23] L.-J. Kau, Y.-P. Lin and C.-T. Lin, ``Lossless image coding using adaptive, switching algorithm with automatic fuzzy context modeling,” IEE Proc. Vision, Image and Signal Processing, Vol. 153, No. 5, pp. 684-694, Oct. 2006.
[24] C. N. Manikopoulos, ``Neural network approach to DPCM system design for image coding,” Proc. IEE Communications, Speech and Vision, Vol.139, No. 5, pp. 501-507, 1992.
[25] N. Kuroki, T. Nomura, M. Tomita and K. Hirano, ``Lossless image compression by two-dimensional linear prediction with variable coefficients,” IEICE Trans. Fundamentals, Vol. E75-A, No. 7, pp. 882-889, July 1992.
[26] X. Li and M. T. Orchard, ``Edge-directed prediction for lossless compression of natural images,” IEEE Trans. Image Process., Vol. 10, No. 6,pp. 813-817, June 2001.
[27] L.-J. Kau and Y.-P. Lin, ``Adaptive lossless image coding using least squares optimization with edge-look-ahead,” IEEE Trans. Circuits and Systems II, Vol. 52, No. 11, pp. 751-755, Nov. 2005.
[28] L.-J. Kau and Y.-P. Lin, ``Least Squares-Based Switching Structure for Lossless Image Coding,” IEEE Trans. Circuits and Systems I, Vol. 54, No. 7, pp. 1529-1541, July 2007.
[29] H. Ye, G. Deng and J. C. Devlin, ``A weighted least squares method for adaptive prediction in lossless image compression,” in Proc. Picture Coding Symp., pp. 489-493, Saint-Malo, France, 2003.104
[30] B. Meyer and P. E. Tischer, ``Glicbawls - grey level image compression by adaptive weighted least squares,” in Proc. Data Compression Conf., pp. 503, Snowbird, Utah, USA 2001.
[31] H. Ye, G. Deng, and J. C. Devlin, ‘Adaptive linear prediction for lossless coding of greyscale images,” in Proc. IEEE Image Process., Vol. 1,pp. 128-131, Sep. 2000.
[32] E. D. Sontag, ``Feedback stabilization using two-hidden-layer nets,” IEEE Trans. Neural Networks, Vol. 3, No. 6, pp. 981-990, Nov. 1992.
[33] Chin-Teng Lin and C. S. George Lee, A Neural-Fuzzy Synergism to Intelligent Systems, Prentice Hall, pp. 235-250, 1996.
[34] I. H. Witten, R. M. Neal, and J. G. Cleary, ``Arithmetic coding for data compression,” Communications of the ACM, Vol. 30, No. 6, pp. 520-540, June 1987.
[35] S. J. Leon, Linear Algebra with Applications, New Jersey, Prentice Hall,2002, pp. 482-488.
[36] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C, Cambridge University Press, 2002, pp. 96-98.
[Online]. Available: http://www.library.cornell.edu/nr/cbookcpdf.html
[37] M. Sugeno and G. T. Kang, ``Structure identification of fuzzy model,” Fuzzy Sets and Systems, Vol. 28, pp. 15-33, 1988.
[38] T. Takagi and M. Sugeno, ``Fuzzy identification of systems and its applications to modeling and control,” IEEE Trans. Syst. Man. Cyber., Vol. 15, pp. 116-132, 1985.105
[39] K. Tanaka and Hua O. Wang, Fuzzy Control Systems Design and Analysis: A Linear Matrix Inequality Approach, John Wiley & Sons, Inc.2001.
[40] C. F. Juang and C. T. Lin, ``An online self-constructing neural fuzzy inference network and its applications,” IEEE Trans. Fuzzy Systems, Vol. 6, pp. 12-32, 1998.
[41] Y. C. Chen and C. C. Teng, ``A model reference control structure using a fuzzy neural network,” Fuzzy Sets and Systems, Vol. 73, pp. 291-312,1995.
[42] C. H. Lee and C. C. Teng, ``Identification and control of dynamic systems using recurrent fuzzy neural networks,” IEEE Trans. Fuzzy Systems, Vol. 8, No. 4, pp. 349-366, 2000.
[43] C. H. Lee and C. C. Teng, ``Fine tuning of membership functions for fuzzy neural systems,” Asian Journal of Control, Vol. 3, No. 3, pp. 18-25, 2001.
[44] C. H. Lee and M. H. Chiu, ``Adaptive Nonlinear Control Using TSK Type Recurrent Fuzzy Neural Network System,” Lecture Notes in Computer Science, Vol. 4491, pp. 38-44, 2007.
[45] C. H. Lee, W. Y. Lai, and Y. C. Lin, ``A TSK-type fuzzy neural network systems for dynamic systems identification,” in Proc. 42nd IEEE Int. Conf. Decision and Control, pp. 4002-4007, Hawaii, U.S.A, 2004.