本篇論文主要在解決計算複雜度高的視訊解碼後處理器與視訊編碼的移動估計。為了降低其計算複雜度，本論文提出以DCT為基礎之後處理器與移動估計演算法。
首先，針對視訊後處理器，本論文提出適應性後處理器演算法，利用DCT係數將區塊分類以消除圖框效應。所提出的方法分別可應用於intra與inter壓縮模式中，所需的計算複雜度比在時域上更小。為了保留影像邊緣的資訊，提出以DCT為基礎之邊緣偵測機制伴隨著一維方向性濾波器可保留影像邊緣並消除圖框效應。從模擬的結果可看出此以DCT係數為基礎之圖框分類可將區塊精確的分類為平滑、邊緣與非平滑區塊，有助於後處理器消除圖框效應並保留影像邊緣的資訊。
其次，在移動估計上，本篇論文提出了以DCT為基礎之適應性臨界決策演算法，有效的使用在視訊一位元影像轉換上，並應用於編碼端之一位元移動估計上。一位元移動估計之硬體計算複雜度遠比全搜演算法要小。由實驗結果可看出所提出之一位元移動估計演算法在低移動影像序列上之效能很接近於用於八位元解析度影像之全搜演算法。經與其他單層一位元移動估計法比較，本適應性演算法的PSNR效能較佳，對複雜影像之相容性也較高，此外，所提出之低複雜度演算法可適用於VLSI硬體實現上。

In this dissertation, two most computationally demanded problems in the postprocessor in video decoders and the motion estimation in video encoders are undertaken. To reduce their computations, the DCT-based intra/inter block postprocessing and DCT-based thresholding binary motion estimation are studied.
To solve the first problem, an adaptive postprocessor figured with DCT-based block classification to effectively remove the so-called blocky effect from compressed video sequences is proposed. The proposed DCT-based detection algorithms for both intra and interfames require much lower computation complexity than the spatial-domain approaches. In order to preserve the edge information, the adaptive postprocessor is also designed with a DCT-based edge detection mechanism such that a 1-D median filter can be adaptively adjusted to match with the edge orientation. Simulation results show that the proposed DCT-based detection algorithms accurately classifies smooth, edge, or non-smooth blocks to help the adaptive postprocessor to effectively remove the blocky effect and sharply preserve the edge information.
For the seoncd probelm, an adaptive DCT-based thresholding algorithm, which can achieve an effectively binarization of video image for binary motion estimation in the video encoder, is provided. The binary motion estimation through the full search mechanism requires extremely low hardware complexity. Experimental results show that the proposed adaptive binary motion estimation attains close performance to the 8-bit resolution motion estimation for low motion sequences with full search strategy. Compared to the well-known single-layer binary motion estimation, the proposed adaptive algorithm shows better PSNR performance and more robustness to complex images. However, the proposed algorithm is with less computation complexity suitable for VLSI implementation.

[1] W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard. New York: Van Nostrand, 1993.
[2] J. L. Mitchell, W. B. Pennebaker, C. E. Fogg, and D. J. LeGall, MPEG Video: Compression Standard. London, U.K.: Chapman & Hall, 1996.
[3] D. Le Gall. “MPEG: A video compression standard for multimedia applications,” Commun. of the ACM, vol. 34, pp. 46-58, Apr. 1991.
[4] ISO/IEC JTC1/SC29/WG11, “ISO/IEC CD 13818: Information technology,” MPEG-2 Committee Draft, Dec. 1993.
[5] CCITT Study Group XV, TD35, “Draft review of recommendation H.261 video codec for audiovisual services at p ×64 kbits/s,” Image Communication, pp.221-239, Aug. 1990.
[6] ITU-T Recommendation H.263, “Video coding for low bitrate communication”, Draft, July 1995.
[7] S. Thomas, “The MPEG-4 video standard verification model,” IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 19-31, Feb. 1997.
[8] C. G. Zhou, L. Khon, D. Rice, I. Kabir, A. Jabbi, X. P. Hu, “MPEG video decoding with the UltraSPARC visual instruction set,” Digest of papers COMPCON Spring95, pp. 470-475, IEEE, Mar. 1995.
[9] V. Bhaskaran, K. Konstantinides, Image and video compression standards: algorithms and architectures, Kluwer Academic Publishers, Boston/Dordrecht/London, 1995.
[10] K. Guttage, R. J. Gove, J. R. van Aken, “A signal-chip multiprocessor for multimedia: the MVP,” IEEE Computer Graphics and Applications, vol.12, pp. 53-64, Nov. 1992.
[11] B. Kappor, “An analysis of memory bandwidth requirement for the h.263 video codec,” SPIE 3309 Visual Communications and Image Processing, San Jose, Jan. 1998, pp. 525-534.
[12] P. Kuhn, Algorithms, Complexity Analysis and VLSI Architectures for MPEG-4 Motion Estimation, Boston, MA: Kluwer Academic, 1999.
[13] Y. P. Lee, L. G. Chen, H. M. Jong, D. L. Huang, and K. N. Jeng, "Video coding architecture for multimedia applications," In Proc. 5th VLSI Design/CAD Symp., 1994, pp. 107-112.
[14] H. Fujiwara, M. L. Liou, and M. T. Sun, "An all-ASIC implementation of a low bit-rate video codec," IEEE Trans. Circuits Syst. Video Technol., vol. 2, pp. 123-134, June, 1992.
[15] E. Feig and S. Winograd, "Fast algorithm for the discrete cosine transform," IEEE Trans. Signal Processing, vol. 40, pp. 2174-2193, Sept. 1992.
[16] M. Liou, "Overview of the p×64 kbits/s video coding standard," Commun., ACM, vol. 34, pp. 59-63, Apr. 1991.
[17] G. K. Wallance, "The JPEG still picture compression standard," Commun. ACM, vol. 34, pp. 30-34, Apr. 1991.
[18] R. Hopkins, "Digital terrestrial HDTV for North America: The Grand Alliance HDTV system," IEEE, Trans. Consumer Electron., vol. 40, pp. 185-198, Aug. 1994.
[19] M. Yuen and H. R. Wu, “A survey of hybrid MC/DPCM/DCT video coding distortions,” Signal Processing (Special Issue on Image Quality Assessment), vol. 70, pp. 247–278, Nov. 1998.
[20] P. Farrelle and A. Jain, “Recursive block-coding—a new approach to transform coding,” IEEE Trans. Commun., vol. COM-34, pp. 161–179, Feb. 1986.
[21] D. Pearson and M. Whybray, “Transform coding of images using interleaved blocks,” Proc. Inst. Elect. Eng., vol. 131, pp. 466–472, Aug. 1984.
[22] B. Hinman, J. Bernstein, and D. Staelin, “Short-space Fourier transform image processing,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, San Diego, CA, Mar. 1984, pp. 481–484.
[23] H. S. Malva, and D. H. Staelin, “The LOT: Transform coding without blocking effects,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-37, pp. 553–339, Apr. 1982.
[24] Y. Zhang, R. Pickholtz, and M. Loew, “A new approach to reduce the blocking effect of transform coding,” IEEE Trans. Commun., vol. 41, pp. 299–302, Feb. 1993.
[25] H. Reeve and J. Lim, “Reduction of blocking effects in image coding,” Opt. Eng., vol. 23, pp. 34–37, 1984.
[26] B. Ramamurthi and A. Gersho, “Nonlinear space-variant postprocessing of block coded images,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-34, pp. 1258–1267, Oct. 1986.
[27] R. L. Stevenson, “Reduction of coding artifacts in transform image coding,” in Proc. IEEE Int. Conf. Acoustics, speech, and Signal Processing, vol. 5, Minneapolis, MN, Mar. 1993, pp. 401–404.
[28] T. Jarske, P. Haavisto, and I. Defe, "Post-filtering methods for reducing blocking effects from coded images," IEEE Trans. Consumer Electron., vol. 40, pp. 521-526, 1994.
[29] T. S. Liu and N. Jayant, "Adaptive postprocessing algorithms for low bit rate video signals," In Proc. IEEE Int. Conf. Conf. Acoustics, Speech, Signal Processing, 1994, pp. V-401-403.
[30] C. J. Kuo and R. J. Hsieh, "Postprocessor design for block coded images," In Proc. HD-Media Technology and Applications Workshop, Taipei, Taiwan, 1993, pp. S9.1-9.7.
[31] B. Jeon, J. Jeong, and J. M. Jo, "Blocking artifacts reduction in image coding based on minimum block boundary discontinuity," In Proc. SPIE Visual Communication and Image Processing, vol. 2501, pp. 198-209, May 1995.
[32] Y. Yang, N. P. Galatsanos, and A. K. Kataggelos, "Regularized recon-struction to block artifact of block discrete cosine transform compressed imaged," IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp. 421-432, Dec. 1993.
[33] A. Zakhor, “Iterative procedures for reduction of blocking effects transform image coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 2, pp. 91–95, Mar. 1992.
[34] H. Paek, R.-C. Kim, and S.-U. Lee, “On the POCS-based postprocessing technique to reduce the blocking artifacts in transform coded images,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 358–367, June 1998.
[35] C. N. Tien and H. M. Hang, "Transform domain postprocessing of DCT-coded images," Proc. SPIE Visual Communication and Image Processing, vol. 2094, Nov. 1993, pp. 1627-1638.
[36] A. V. Oppenhenim and R. W. Schafer, Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice Hall, 1989.
[37] S. C. Hsia, J. F. Yang and B. D. Liu, "Efficient postprocessor for blocky effect removal based on transform characteristics", IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 924-929, Dec. 1997.
[38] Y. L. Lee, H. C. Kim and H. W. Park, "Blocking Effect Reduction of JPEG Images by Signal Adaptive Filtering," IEEE Trans. Image Processing, vol. 7, pp. 229-234, Feb. 1998.
[39] A. N. Netravali and J. O. Limb, “Picture coding: A review,” in Proc. IEEE, vol. 68, pp. 366–406, Mar. 1980.
[40] A. K. Jain, “Image data compression: A review,” in Proc. IEEE, vol. 69, pp. 349–389, Mar. 1981.
[41] H. G. Musmann, P. Pirsch, and H. J. Grallert, “Advances in picture coding,” in Proc. IEEE, vol. PROC-73, pp. 523–548, Apr. 1985.
[42] F. Dufaux and F. Moscheni, “Motion estimation techniques for digital TV: A review and a new contribution,” in Proc. IEEE, vol. 83, pp. 858–876, June 1995.
[43] M. Bierling, “Displacement estimation by hierarchical block matching,” in Proc. SPIE, vol. 1001, pp. 942–951, 1988.
[44] H. Gharavi and M. Mills, “Blockmatching motion estimation algorithms—new results,” IEEE Trans. Circuits Syst., vol. 37, pp. 649–651, May 1990.
[45] M. Ghanbari, “The cross-search algorithm for motion estimation,” IEEE Trans. Commun., vol. 38, pp. 950–953, July 1990.
[46] L. G. Chen, W. T. Chen, Y. S. Jehng, and T. D. Chiueh, “An efficient parallel motion estimation algorithm for digital image processing,” IEEE Trans. Circuits Syst. Video Technol., vol. 1, pp. 378–385, Dec. 1991.
[47] Y. L. Chan and W. C. Siu, “New adaptive pixel decimation for block motion vector estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 113–118, Feb. 1996.
[48] H. M. Jong, L. G. Chen, and T. D. Chiueh, “Accuracy improvement and cost reduction of 3-step search block matching algorithm for video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 88–90, Feb. 1994.
[49] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438–442, Aug. 1994.
[50] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 313–317, June 1996.
[51] Y. L. Chan and W. C. Siu, “On block motion estimation using a novel search strategy for an improved adaptive pixel decimation,” J. Vis. Commun. Image Represent., vol. 9, no. 2, pp. 139–154, June 1998.
[52] L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 419–421, Aug. 1996.
[53] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 369–377, Aug. 1998.
[54] K. H.-K. Chow and M. L. Liou, “Genetic motion search algorithm for video compression,” IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp. 440–445, Dec. 1993.
[55] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion-compensated interframe coding for video conferencing,” in Proc. Nat. Telecommunications Conf., Nov./Dec. 1981, pp. G 5.3.1–G 5.3.5.
[56] J. R. Jain and A. K. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Trans. Commun., vol. 29, pp. 1799–1808, Dec. 1981.
[57] R. Srinivasan and K. R. Rao, “Predictive coding based on efficient motion estimation,” IEEE Trans. Commun., vol. 33, pp. 888–896, Aug. 1985.
[58] G. Cote, M. Gallant, F. Kossentini, “Efficient motion vector estimation and coding for H.263-based very low bit rate video compression,” ITU-T SG 16, Q15-A-45, June 1997.
[59] B. Liu and A. Zaccarin, “New fast algorithms for the estimation of block motion vector,” IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp. 148–157, Apr. 1993.
[60] J. S. Kim and R. H. Park, “A fast feature-based block matching algorithm using integral projections,” IEEE J. Select. Areas Commun., vol. 10, pp. 968–971, June 1992.
[61] B. Natarajan, V. Bhaskaran, and K. Konstantinides, “Low-complexity block-based motion estimation via one-bit transforms”, IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 702-706, Aug. 1997.
[62] T. M. Le, M. Snelgrove, and S. Panchanatan, “Fast motion estimation using feature extraction and XOR operations”, SPIE 3311 MHA Multimedia Hardware Architecture, San Jose, CA, 1998, pp. 108-118.
[63] S. Zhong, F. Chin, Y. S. Cheung, and D. Kwan “Hierarchical motion estimation based on visual pattern for video coding”, in Proc. ICASSP-96, May 1996, pp. 2323-2326.
[64] X. Song, Y. Q. Zhang, and T. Chiang, “Hierarchical motion estimation using binary pyramids with 3-scale tilings,” SPIE 3309 VCIP Visual Communications and Image Processing, San Jose, CA, 1998, pp. 80-87.
[65] X. Song, T. Chiang, X. Lee, and Y.-Q. Zhang, “New fast binary pyramid motion estimation for MPEG2 and HDTV encoding,” IEEE Trans. Circuits Syst. Video Technol., vol. 10, pp. 1015–1028, Oct. 2000.
[66] J. H. Luo, C. N. Wang, and T. Chiang, “A novel all-binary motion estimation (ABME) with optimized hardware architectures,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp. 700-712, Aug. 2002.
[67] J. Feng, K. T. Lo, H. Mehrpour, and A. E. Karbowiak, “Adaptive block matching motion estimation algorithm using bit-plan matching,” in Proc. Int. Conf. Image Processing, Oct. 1995, pp. 496-499.
[68] J. H. Lee and J. B. Ra, “Efficient motion estimation using edge-based binary block-matching and Refinement based on motion vector correlation”, in Proc. Int. Conf. Image Processing, Oct. 7-10, 2001, pp. 957-960.
[69] I. Pitas, Digital Image Processing Algorithms, Englewood Cliffs, NJ: Prentice-Hall, 1993.
[70] Y. F. Hsu, Y. C. Chen, "A new adaptive separable median filter for removing blocking effects", IEEE Trans Consumer Electron., vol. 39, pp. 510-513, Aug. 1993.
[71] M. J. Chen, L. G. Chen, T. D. Chiueh, "One-dimensional full search motion estimation algorithm for video coding," IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp. 504-509, Oct. 1994.
[72] S. Acharya and B. Smith, “Compressed domain transcoding of MPEG,” in Proc. Int. Conf. Multimedia Computing and Systems (ICMCS), Austin, TX, June 28-July 1 1998, pp. 295-304.
[73] S. F. Chang and D. G. Messerschmitt, “A new approach to decoding and compositing motion-compensated DCT based images,” in Proc. IEEE Int. Conf. Acoust., Speech and Signal Processing, Apr. 1993, pp. 421–424.
[74] P. A. A. Assuncao and M. Ghanbari, “A frequency-domain video transcoder for dynamic bit-rate reduction of MPEG-2 bit streams,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 953–967, Dec.1998.
[75] --, “Manipulation and compositing of MC-DCT compressed video,” IEEE J. Select. Areas Commun., vol. 13, pp. 1–11, Jan. 1995.
[76] H. Sun, W. Kwok, and J. W. Zdepski, “Architectures for MPEG compressed bitstream scaling,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 191–199, Apr. 1996.
[77] A. Jain, Fundamentals of Digital Image Processing, Eaglewood Cliffs, NJ: Prentice-Hall, 1989.
[78] C. B. Wu, B. D. Liu, J. F. Yang, “Adaptive postprocessors with DCT-based block classifications”, IEEE Trans. Circuits Syst. Video Technol., vol. 13, May 2003.
[79] C. B. Wu, B. D. Liu, J. F. Yang,“Adaptive postprocessors with DCT-based block classifications,”in Proc. 2001 IEEE Int. Symp. Circuit Syst., Sydney, Australia, May 6-9, 2001, pp. V 271-274.
[80] J. R. B. de Marca, “An LSF quantizer for the North-American half-rate speech coder,” IEEE Trans. Vehicular Technol., vol. 43, pp. 413-419, Aug. 1994.
[81] K. Hwang, Computer Arithmetic: Principles, Architecture, and Design, Now York : Wiley, 1979