視訊訊號經常使用交錯(interlace)的方式來傳送或儲存，交錯式的訊號一開始是為了解決電視經由廣播傳送時頻寬不足的問題以及為了增加時間上的顯示頻率而設計的，這種設計在每一張畫面中只抽取一半的掃描線來代表此張畫面，於是原本每秒30張的畫面率(frame rate)變成了每秒60張的場畫面率(field rate)，在50年前NTSC或者PAL規格設計的當時，所有的電視都是採用與電視訊號能搭配的交錯式掃描的方式來顯示視訊，交錯掃描訊號可說是一種良好的設計。隨著科技的進步，在電腦及液晶電視逐漸普及的現在，大部分的顯示器已經改由漸近式(Progressive)掃描的方式來呈現視訊，原本60張的場畫面在漸近式的顯示器上會被當成30張的畫面來顯示，但是每一張畫面中卻存在著兩張不同時間點所拍攝的場畫面，若是沒有考慮到時間差的問題而直接顯示出來的話，就會看到非常明顯的鋸齒狀雜訊，所以去交錯雜號在目前的漸近式顯示器上變成了必需要處理的問題之一。
去交錯雜訊的演算法若是依效果差到佳來排列的話可以分為：空間上去交錯、時間與空間上適應性的去交錯以及使用動作補償去交錯這三種。這三種各自有自己的特色，目前的顯示器最常用到的為前兩種做法，因為它們的成本較低也比較好設計；第三種做法在許多文獻中皆有提到，但它不被顯示器採用的原因是動作向量的計算量太大且不一定能夠找到夠準確的動作向量。本論文為了使動作補償去交錯由理論變為可行的作法，針對計算量及動作向量的準確度做了深入的研究，提出了二種不同的快速動作估計的方法，利用找到的擬真動作向量(True motion vector)補償出去交錯後的視訊畫面。
本論文提出的第一種快速動作向量搜尋法能夠快速地產生視訊編碼器使用的動作向量，不只產生出的動作向量比一般的快速演算法更趨近真實的動作向量，誤差值(distortion)也更趨近於完全搜尋法，它能被應用在固定方塊或變異方塊大小的編碼器中；而提出的第二種動作向量搜尋是專門針對視訊去交錯或畫面率增加的主題而設定的，它的目的是找出能與物件真實的移動相匹配的動作向量，物體的形狀通常不是規則的形狀，所以動作向量對應的方塊必需是變異大小的以貼近物體的外形變化，動作搜尋能成功的前提是必需確保同一移動物體皆有一致方向的動作向量，如此一來，選擇最佳的動作向量的條件不再是單憑方塊對應的誤差值為最小來決定。由本文實驗的結果可看出產出的動作向量極趨近真實的物件移動。
一般而言，在一張畫面中並不是所有的區域都可以找到相對應的動作向量，所以動作補償式的去交錯演算法必須搭配空間上的內插法來插補動作補償不佳的區域。本論文提出數個能成功偵測出動作補償不佳區域的方法，因此不易產生因動作補償不準而畫面品質不佳的區域。本論文亦提出一個空間上的內插法，它改良了傳統上以像素點為單位找尋內插方向的作法，改用方塊對應的方式來找尋最佳內插角度，藉由上列的各種作法，本論文提出了一套完整的去交錯雜訊演算法，期許能對顯示器技術有所貢獻。

Interlaced video signals are widely used nowadays. Originally, the interlaced scanning method was designed to decrease the bandwidth when transmitting videos and increase the frame rate when displaying videos. It only transmits odd scan-lines in one frame and even scan-lines in the next frame. Under such rule, the original 30 frames per second signal become 60 fields per second by using the same bandwidth. When NTSC and PAL were designed 50 years ago, all the televisions used the interlaced scanning process, so interlaced signal and interlaced scanning television were good industrial designs. But as the time goes by, new techniques are proposed. The computer monitor and LCD television are widely used now, and they all use the progressive scanning method. On these progressive scanning devices, 60 fields per second will be displayed as 30 frames per second in spite of two fields of one frame are captured in different time interval. Serious saw effect will be seen on the interlaced frame and will make the audiences feel uncomfortable. As a result, the de-interlacing algorithm is essential for progressive display devices.
De-interlacing algorithm can be categorized into three groups: spatial de-interlacing, spatial/temporal adaptive de-interlacing and motion compensated de-interlacing. The performances of them are from low to high in the previous mentioned order. Although they have their individual characteristics, the television producers often use the first two methods since their costs are lower than the third one and the logic designs are also much easier than the third one. The third method is widely used in many literatures and shows high quality de-interlaced video. The reasons why motion compensated de-interlacing is not used in television industry are: the huge computation in motion vector generation and the low accuracy of found motion vectors. Two fast motion estimation algorithms are proposed in this Dissertation to speed up the motion estimation time and improve the motion vector accuracy. The found true motion vectors are used to motion compensate de-interlaced video frames.
Our first fast motion estimation algorithm can generate video-encoder-used motion vectors fast while the generated vectors are not only closer to real motion vector but also with lower distortion value than that generated by other algorithms. It can be used in fix block size or variable block sizes video encoders. Our second motion estimation algorithm is designed for applications such as de-interlacing and frame rate up-conversion. It only focuses on the accuracy of motion vectors without regarding the distortion value. For our true motion estimation algorithm, it must confirm that the caught motion vectors inside one object are in the same real motion trajectory. Since the shape of an object is often irregular, the true motion estimation is designed as variable block sizes to fit the shape of objects. The experimental result can manifest that the found motion vectors are very close to the real object moving trajectory.
Generally speaking, not all regions in one frame have their corresponding motion vectors. For this reason, spatial de-interlacing must be included in motion compensated de-interlacing system to fix the bad-compensated regions. Several detection methods are proposed in this dissertation to detect these bad-compensated regions and to force these regions to be interpolated by spatial interpolation. The more precise detection methods will generate the higher quality de-interlaced frame. Furthermore, for spatial de-interlacing, the traditional pixel-based interpolation is not adopted. The pixel based directional search is replaced by block based directional search. As a result, it successfully improves the accuracy of edge direction detection. Some bad pixel refinement methods are also designed to improve the overall visual quality.
All the mentioned methods are discussed in this dissertation. We hope the dissertation can contribute to the production of progressive display devices especially the production of high quality televisions.

[1] I. Ahmad, W. Zheng, J. Luo and M. Liou, " A fast adaptive motion estimation algorithm," IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no.3, pp. 420–438, Mar 2006.
[2] X. Q. Banh and Y. P. Tan, “Adaptive dual-Cross search algorithm for block-matching motion estimation,” IEEE Transactions on Consumer Electronics, vol. 50, no. 2, pp. 766–775, May 2004.
[3] E. B. Bellers, R.J. Schutten, M. Kruetzmann, H. van der Heijden , and Haiyan He, “Directional and motion-compensated de-interlacing”, Digest of Technical papers, ICCE ’06, Jan. 2006.
[4] M. Biswas, S. Kumar, and T. Q. Nguyen, “Performance analysis of motion-compensated de-Interlacing systems”, IEEE Transactions on Image Processing, vol. 15, no. 9, Sept. 2006.
[5] G. Bjontegaard, “Calculation of average PSNR differences between RD-curves,” Doc. #VCEG-M33, the 13th meeting: Austin, Texas, USA, Apr. 2001.
[6] R. Braspenning, and G. de Haan, “True-motion estimation using feature correspondence,” SPIE, Proceedings of VCIP, pp. 396–407, Jan. 2004, vol. 8, no. 1, pp. 85–91, Feb. 1998.
[7] P. Brox, L. Woestenberg, and G. de Haan, “Local picture-repetition mode detection for video de-interlacing”, IEEE Transactions on Consumer Electronics, vol. 53, no. 4, Nov. 2007.
[8] S. Byun, J. Byun, and G. Kim, “A recursive approach for de-interlacing using improved ELA and motion compensation based on bi-directional BMA,” 2004 International Conference on Image Processing, vol. 3, pp. 1679–1682, Oct. 2004.
[9] R. Castagno, P. Haavisto, and G. Ramponi, “A method for motion adaptive frame rate up-conversion,” IEEE Transactions on Circuits and System Video Technologies, vol. 6, pp. 436–446, Oct. 1996.
[10] C. Cafforio, F. Rocca, and S. Tubaro, “Motion compensated image interpolation,” IEEE Transactions on Communication, vol. 38, pp. 215–222, 1990.
[11] F. J. Chang, S. C. Tai, “A motion and edge adaptive de-interlacing algorithm,” National Cheng Kung University, Tainan, Taiwan, R.O.C. Thesis for Master of Science Degree, June 2003.
[12] Y. L. Chang, S. F. Lin, C. Y. Chen, L. G. Chen, “Video de-interlacing by adaptive 4-field global/local motion compensated approach” IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 12, pp.1569–1582, Dec. 2005.
[13] G. B. Chen, “A fast motion estimation algorithm for mobile communications,” Journal of Zhejiang University SCIENCE, pp. 13–18, July 2006.
[14] M. J. Chen, C. H. Huang, and C. T. Hsu, “Efficient de-interlacing technique by inter-field information,” IEEE Transactions on Consumer Electronics, vol. 50, no. 4, pp.1202–1208, Nov. 2004.
[15] M. J. Chen, and K. C. Hou, “Fast variable block-size motion estimation by merging refined motion vector for H.264,” IEICE Transactions on Communication, vol. E89-B, no. 10, Oct. 2006.
[16] T. Tao Chen, “Adaptive temporal interpolation using bidirectional motion estimation and compensation,” in Proceedings of 2002 International Conference on Image Processing, vol. 2, pp. 313–316, Sept. 2002.
[17] Z. Chen, P. Zhou and Y. He, “Fast integer pixel and fractional pixel motion estimation for JVT,” ITU-T, Doc. #JVT-F017, 2002.
[18] Z. Chen, P. Zhou and Y. He, “Fast motion estimation for JVT,” ITU-T, Doc. #JVT-G016, 2003.
[19] Y. Cheng, Z. Wang, K. Dai, and J. Guo, “A fast motion estimation algorithm based on diamond and triangle search patterns,” Lecture notes in computer science, Iberian conference on pattern recognition and image analysis 2005, pp. 419–426, 2005.
[20] C. H. Cheung and L. M. Po, “Novel cross-diamond-hexagonal search algorithms for fast block motion estimation,” IEEE Transactions on Multimedia, vol. 7, no. 1, pp. 16–22, Feb. 2005.
[21] B. D. Choi, Jo. W. Han, C. S. Kim and S. J. Ko, “Motion-compensated frame interpolation using bilateral motion estimation and adaptive overlapped block motion compensation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 4, Apr. 2007.
[22] W. I. Choi, B. Jeon, and J. Jeong, “Fast motion estimation with modified diamond search for variable motion block sizes,” in Proc. ICIP 2003, vol. 2, pp. 371–374, Sept. 2003.
[23] T. S. Chong, O. C. Au, W. S. Chau, T. W. Chan, “A content adaptive de-interlacing algorithm,” IEEE International Symposium on Circuits and Systems, vol. 5, pp.4923–4926, May 2005.
[24] T. Doyle, “Interlaced to sequential conversion of EDTV applications,” in Proc. 2nd Int. Workshop Signal Processing of HDTV, pp. 412–430, Feb. 1998.
[25] F. Dufaux and F. Moscheni, “Motion estimation techniques for digital TV: a review and a new contribution”, in Proceeding of the IEEE, vol. 83, pp. 858–876, June 1995.
[26] S. Fujiwara and A. Taguchi, “Motion-compensated frame rate up-conversion based on block matching algorithm with multi-size blocks”, Proceedings of 2005 International Symposium on Intelligent Signal Processing and Communication Systems, 2005. ISPACS 2005.
[27] J. Gu, X. Gao, and H. Ishimura, “Adaptive de-interlacing algorithm based on motion compensation”, Proceedings. ICSP '04. 2004 7th International Conference on Signal Processing, vol. 1, pp.800–803, Sept. 2004.
[28] T. Ha, S. Lee, and J. Kim, “Motion compensated frame interpolation by new block-based motion estimation algorithm”, IEEE Transactions on Consumer Electronics, vol. 50, no. 2, pp.752–759, May 2004.
[29] G. de Haan, P. W. A. C. Biezen, H. Huijgen, and O. A. Ojo, “True-motion estimation with 3-D recursive search block matching,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 3, no. 5, pp.368–379, Oct. 1993.
[30] G. de Haan and P. W. A. C. Biezen,, “An efficient true-motion estimator using candidate vectors from a parametric motion model,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 1, pp.85–91, Feb. 1998.
[31] G. de Haan, “IC for motion-compensated de-interlacing, noise reduction, and picture-rate conversion,” IEEE Transactions on Consumer Electronics, vol. 45, no. 3, pp. 617–624, Aug. 1999.
[32] K. Hilman, H. W. Park and Y. Kim, “Using motion-compensated frame-rate conversion for the correction of 3 : 2 pull down artifacts in video sequences,” IEEE Transactions on circuits and systems for video technology, vol. 10, no. 6, Sept.2000.
[33] P. Ishwar and P. Moulin, “On spatial adaptation of motion-field smoothness in video coding,” IEEE Transaction on Circuits Systems for Video Technology, vol. 10, no. 6, pp. 980–989, Sept. 2000.
[34] B. W. Jeon, G. I. Lee, S. H. Lee and R. H. Park, “Coarse-to-fine frame interpolation for frame rate up-conversion using pyramid structure,” IEEE Transactions on Consumer Electronics, vol. 49, no. 3, pp. 499–508, Aug. 2003.
[35] T. Jeong, Y. Kim, K. Sohn, and C. Lee, “Deinterlacing with selective motion compensation,” Optical Engineering, vol. 45, no. 7, pp. 077001-1–077001-9, July 2006.
[36] X. Jing and L. P. Chau, “An efficient three-step search algorithm for block motion estimation,” IEEE Transactions on. Multimedia, vol. 6, pp. 435–438, Jun. 2004.
[37] Y. Y. Jung, S. Yang, and P. Yu, “An effective de-interlacing technique using two types of motion information” IEEE Transactions on Consumer Electronics, vol. 49, no. 3, pp.493 – 498, Aug. 2003.
[38] W. Kim, S. Jin, and J. Jeong, “Novel intra deinterlacing algorithm using content adaptive interpolation”, IEEE Transaction on Consumer Electronics, vol 53, no 3, Aug. 2007.
[39] Y. H. Kim, J. W. Yoo, S. W. Lee, J. Shin, J. Paik and H. K. Jung, “Adaptive mode decision for H.264 encoder,” Electronics Letters, vol. 40, no. 19, Sept. 2004.
[40] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proc. Nat. Telecommun. Conf., New Orleans, LA, pp. G5.3.1–G5.3.5., Nov. 29–Dec. 3 1981,
[41] C. J. Kuo, C. Liao, and C. C. Lin, “Adaptive interpolation technique for scanning rate conversion,” IEEE Transactions on Circuits and System Video Technology, vol. 6, no. 3, pp. 317–321, Jun. 1996.
[42] T. Y. Kuo and C. C. J. Kuo, “Motion-compensated interpolation for low-bit-rate video quality enhancement,” in Proc. SPIE Visual Communications and Image Processing, vol. 3460, pp. 277–288, July 1998.
[43] O. Kwon, K. Sohn, and C. Lee, “Deinterlacing using directional interpolation and motion compensation,” IEEE Transactions on Consumer Electronics, vol. 49, no. 1, pp.198–203, February 2003.
[44] C.W. Lam, L. M. Po and C. H. Cheung, “A novel kite-cross-diamond search algorithm for fast block matching motion estimation,” Proceeding of IEEE International Symposium on Circuits and Systems, Vancouver, Canada, May 2004.
[45] C. W. Lam, L. M. Po and C. H. Cheung, “A novel kite-cross-diamond search algorithm for fast video coding and videoconferencing applications,” Proceeding of IEEE International Conference on Acoustics, Speech, and Signal Processing, Montreal, Quebec, Canada, May 2004.
[46] S. H. Lee, Y. C. Shin, S. Yang, H. H. Moon, and R. H. Park, “Adaptive motion-compensated interpolation for frame rate up-conversion,” IEEE Transactions on Consumer Electronics, vol. 48, no. 3, pp. 444–450, Aug. 2002.
[47] G. L. Li and M. J. Chen, “High performance de-interlacing algorithm for digital television displays,” IEEE Journal of Display Technology, vol. 2, no. 1 pp. 85–90, Mar. 2006.
[48] M. Li and T. Nguyen, “A de-interlacing algorithm using markov random field model”, IEEE Transactions on Image Processing, vol. 16, no. 11, Nov. 2007.
[49] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, pp. 438–442, Aug. 1994.
[50] Y. Liang, I. Ahmad, J. Luo, and Y. Sun, “Fast motion estimation using hierarchical motion intensity structure,” in Proc. ICME 2004, Taiwan, pp. 699–702, June 2004.
[51] C. C. Lin, M. H. Sheu, H. K. Chiang, C. Y. Liaw, and J. F. Lin, “Motion adaptive de-interlacing with local scene changes detection,” ICICIC ’07, Sept. 2007.
[52] C. C. Lin, M. H. Sheu, H. K. Chiang, and C. J. Wei, “The VLSI design of motion adaptive de-interlacing with horizontal and vertical motions detection,” APCCAS 2006, Dec. 2006.
[53] S. F. Lin, Y. L. Chang, and L. G. Chen, “Motion adaptive interpolation with horizontal motion detection for deinterlacing.” IEEE Transactions on Consumer Electronics, vol. 49, no. 4, pp.1256–1265, November 2003.
[54] S. Mallat, “Super-resolution bandlet upconversion for HDTV,” White paper from Let It Wave company. Available at http://www.letitwave.com/rubriques/7%20 TECHNOLOGY/ WhitePaper_LIW.pdf
[55] M. J.W. Mertens and G. de Haan, “Motion vector field improvement for picture rate conversion with reduced halo” Proc. of the SPIE/IST VCIP, San Jose, CA, pp. 352–362, January 2001.
[56] O. A. Ojo and G. de Haan, “Robust motion compensated video upconversion,” IEEE Transactions on Consumer Electronics, vol. 43, no. 4, pp. 1045–1056, Nov. 1997.
[57] E. P. Ong, H. Wang, and P. Xue, “Video coding based on true motion estimation,” 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2003 Proceeding, vol. 3, no. 6-10, pp. 409–12, April 2003.
[58] K. Ouyang, G. Shen, S. Li, and M. Gu, “Advanced motion search and adaptation techniques for deinterlacing,” IEEE International Conference on Multimedia & Expo (ICME), July 2005.
[59] A. Pelagotti, and G. de Haan, “A new algorithm for high quality video format conversion”, in Proc. of Image Processing, vol. 2, pp. 375–378, Oct. 2001.
[60] J. Y. Pyun, J. S. Lee, J. W. Jeong, J. H. Jeong, and S. J. Ko, “Robust error concealment for visual communications in burst-packet-loss networks,” IEEE Transactions on Consumer Electronics, vol. 49, no. 4, pp. 1013 – 1019, Nov. 2003.
[61] H. So, J. Kim, W.-K. Cho and Y.-S Kim, “Fast motion estimation using modified diamond search patterns,” Electronics Letters, vol. 41, no. 2, Jan. 2005.
[62] J. E. Santos Conde, A. Teuner, and B. J. Hosticka , “Hierarchical locally adaptive multigrid motion estimation for surveillance applications,” 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '99 Proceedings, vol. 6, pp. 3365 – 3368, March 1999.
[63] L. Song and G. Wei, “Complexity reduction of adaptive interpolation filter,” JVT-D016. doc, 6th meeting: Awaji Island, Japan, July 2002.
[64] K. Sugiyama and H. Nakamura, “A method of de-interlacing with motion compensated interpolation,” IEEE Transactions on Consumer Electronics, vol. 45, no, 3, pp. 611–616, Aug. 1999.
[65] J. W. Suh and Y. S. Ho, “Error concealment technique based on optical flow,” Electronics Letters, vol. 38, no. 18, pp. 1020 – 1021, Aug. 2002.
[66] G. Sullivan, “Recommended simulation common conditions for H.26L coding efficiency experiments on low resolution progressive scan source material,” Doc. #VCEG-N81, the 14th meeting: Santa Barbara, CA, USA. Sep. 2001.
[67] S. C. Tai, Y. R. Chen, and S. J. Li, “Low complexity variable-size block –matching motion estimation for adaptive motion compensation block size in H.264.” in Proc. IEEE Asia-Pacific Conference on Circuits and Systems, pp. 613-616, 2004.
[68] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, pp. 369–377, Aug. 1998.
[69] R. Thoma and M. Bierling, “Motion compensating interpolation considering covered and uncovered background,” Signal Processing: Image Communication, vol. 1, no. 2, pp. 191-212, Oct. 1989.
[70] D. Van de Ville, W. Philips, and I. Lemahieu, “Motion compensated de-interlacing for both real time video and still images,” 2000 International Conference on Image Processing, vol. 2, 10-13, pp. 680–683, Sept. 2000.
[71] D. Wang and D. Lauzon, “Hybrid algorithm for estimating true motion fields,” Optical Engineering, vol. 39, no. 11, pp. 2876–2881, Nov. 2000.
[72] D. Wang, A.Vincent, and P. Blanchfield, “Hybrid de-interlacing algorithm based on motion vector reliability”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 8, pp. 1019–1025, Aug. 2005.
[73] J. Wang, D. Wang, and W. Zhang, “Temporal compensated motion estimation with simple block-based prediction”, IEEE Transactions on Broadcasting, vol. 49, no. 3, pp. 241–248, Sept. 2003.
[74] S. Yang, Y. Y. Jung, Y. H. Lee, and R. H. Park, “Motion compensation assisted motion adaptive interlaced-to-progressive conversion,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, no. 9, pp. 1138–1140, Sept. 2004.
[75] H. Yoo and J. Jeong, “Direction-oriented interpolation and its application to de-interlacing,” IEEE Transactions on Consumer Electronics, vol. 48, no. 4, pp. 954–962, Nov. 2002.
[76] C. S. Yu and S. C. Tai, "Adaptive double-layered initial search pattern for fast motion estimation," IEEE Transactions on Multimedia, vol. 8, no. 6, pp. 1109–1116, Dec. 2006,
[77] L. Yu, J. Li, Y. Zhang and Y. Shen, “Motion adaptive deinterlacing with accurate motion detection and anti-aliasing interpolation filter”, IEEE Transactions on Consumer Electronics, vol. 52, no. 2, May 2006.
[78] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, pp. 349–355, May 2002.
[79] C. Zhu, X. Lin, L. P. Chau, and L. M. Po, “Enhanced hexagonal search for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 14, no. 10, pp. 1210-1214, Oct. 2004.
[80] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block matching motion estimation,” IEEE Transactions on Image Processing, vol. 9, pp. 287–290, Feb. 2000.
[81] http://broadcastengineering.com/ar/broadcasting_understanding_interlace/
[82] Joint Video Team Reference Software, Version 9.5 (JM9.5), http://iphome.hhi.de/suehring/tml/download/
[83] Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, “Draft ITU-T recommendation and final draft international standard of joint video specification (ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC),” ITU-T, Doc. #JVT-G050r1, Mar. 2003.