本論文介紹了演算法/架構共同設計及由上而下的設計方法並以一個已知演算法的動態適應解交錯器為例子。
解交錯器將電視的交錯訊號轉變為循序訊號，並廣範應用於液晶顯示器 (LCD)、電漿顯示器 (plasma display)、及數位光線處理投影機(DLP projector)，現今的數位電視也支援1080i (i=交錯訊號)。
所提出架構的設計流程基於由上而下且為目標導向的設計方法，這個方法藉由將設計抽象化成多個階層，以簡化設計上的問題。為了最佳化此設計，在設計空間中探索各種設計參數的可能，包含了時脈、記憶體大小、頻寬及管線級數及其它。資料流模型是一個強大的工具，可幫助在設計空間中探索各種設計，階層式的資料流模型可用來粹取設計參數及單位資料量。論文中使用CAL的資料流導向語言能夠快速的模擬高階層的資料流。本架構最高的規格是1920x1080交錯式視訊，每秒顯示60張圖，色彩格式為4:2:2，使用tsmc.18μm製程。其所需時脈為144.9百萬赫茲，為了達到標準解析度的取樣率27百萬赫茲，其操作時脈為162百萬赫茲，其所需閘數約為137千個。

This thesis presents a design flow of algorithm/architecture co-design, top-down design methodology and uses architecture design of deinterlacer from a given algorithm as an example.
Deinterlacing converts interlaced signals to progressive ones, and it is well-applied in LCD displays, plasma displays, and DLP projectors. Nowadays, digital TV (DTV) also supports 1080i (i = interlaced) video sequences.
The proposed architecture design flow is based on the concept of a “top-down” design methodology, which is a target-oriented design method. This method solves the design problem in several levels of abstractions that simplify the design problem. In order to optimize the design, design space exploration helps to explore an optimized solution in the design space including clock rate, memory size, bandwidth, pipeline depth, and so on. The dataflow model is a powerful tool that helps explore various designs in the design space. A hierarchical dataflow model is useful for extracting both the value of the design factors and the data granularity. A dataflow-oriented language called “CAL” has the advantage of modeling the high level dataflow in a short time compared with other existing language.
The highest application is 1920x1080 interlaced video sequences with 60 fps and a color format of 4:2:2 for real time. The design technology is tsmc.18μm. The required clock rate is 144.9 MHz; however, in order to use the multiple clock rate of 27MHz (Standard Definition TV sample rate), the operation clock rate should be 162 MHz, and the gate count with line buffer should be about 137 k.

[1] Digital Video Broadcasting (DVB), deployment-data.xls is available at www.dvb.org/dvb-deployment-data.xls
[2] G. de Haan and E.B.Bellers, “Deinterlacing –an overview,” Proceedings of the IEEE, vol. 86, no. 9, pp.1839-1857 1998.
[3] G.G. Lee, H-Y. Lin, M-J. Wang, R-L., Lai, C.W. Jhuo, & B-H. Chen, "Spatial-temporal content-adaptive deinterlacing algorithm,” IET Image processing, vol. 2, no. 6, pp. 323–336, Dec. 2008.
[4] D.H. Lee, "A new edge-based intra-field interpolation method for deinterlacing using locally adaptive-thresholded binary image," IEEE Trans. Consumer Electronics, vol. 54, no. 1, pp.110-115, Feb. 2008.
[5] S.H. Hong, R.H. Park, S. Yang, and J.Y. Kim, "Edge-preserving spatial deinterlacing for still images using block-based region classification," IEEE Int. Conf. on Consumer Electronics (ICCE), pp. 85-86, 2006.
[6] Q. Huang, W. Gao, D. Zhao, Q. Huang, "An edge-based median filtering algorithm with consideration of motion vector reliability for adaptive video deinterlacing," IEEE Int. Conf. on Multimedia and Expo (ICME), pp. 837-840, Toronto, Ontario, Canada, July 2006.
[7] W. Kim, S. Jin, and J. Jeong, "An efficient intra deinterlacing algorithm with gradient detection and window matching," in Proc. Int. Conf. and Exhibition ACM Multimedia, Augsburg, Germany, Sep. 2007, pp. 747-750.
[8] H.I. Koo, S.H. Lee, and N.I. Cho, "A new EDI-based deinterlacing algorithm," IEEE Trans. Consumer Electronics, vol. 53, no. 4, pp. 1494-1499, November 2007.
[9] S. Jin, W. Kim and J. Jeong, "Fine directional de-interlacing algorithm using modified sobel operation," IEEE Trans. on Consumer Electronics, vol. 54, no. 2, pp. 857-862, May 2008.
[10] M.K. Park, M. Byun, J.H. Park, and M.G. Kang, "Edge-dependent interpolation-based deinterlacing using edge patterns," Journal of Electronic Imaging, vol. 15, no. 4,04303-1－04303-8, Oct. 2006.
[11] T. Koivunen, "Motion detection of an interlaced video signal," IEEE Transa. on Consumer Electronics, vol. 40, no. 3, pp. 753-760, Aug 1994.
[12] G.L. Li and M.J. Chen, "High Performance De-Interlacing Algorithm for Digital Television Displays," Journal of Display Technology, vol. 2, no. 1, pp.85-90, March 2006.
[13] S.F. Lin, Y.L. Chang, and L.G. Chen, "Motion adaptive de-interlacing by horizontal motion detection and enhanced ELA processing," IEEE Int. Symp. on Circuits and Systems (ISCAS), vol. 2, pp. II696-II699,Bangkok, Thailand, 2003.
[14] L. Yu, J. Li, Y. Zhang, and Y. Shen, "Motion adaptive deinterlacing with accurate motion detection and anti-aliasing interpolation filter," IEEE Trans. on Consumer Electronics, vol. 52, no. 2, May 2006.
[15] G.G. Lee, M.J. Wang, H.T. Li, & H-Y. Lin, “A motion-adaptive deinterlacer via hybrid motion detection and edge-pattern recognition,” EURASIP Journal on Image and Video Processing, vol. 2008, Article ID 741290, 10 pages, Mar. 2008.
[16] Y. Shen, D. Zhang, Y. Zhang, and J. Li, "Motion adaptive deinterlacing of video data with texture detection," IEEE Trans. on Consumer Electronics, vol. 52, no. 4, pp. 1403-1408, Nov. 2006.
[17] G. Jeon, M. Anisetti, D. Kim, V. Bellandi, E. Damiani, J. Jeong, "Fuzzy rough sets hybrid scheme for motion and scene complexity adaptive deinterlacing," Image and Vision Computing, vol. 27, no. 4, pp. 425-436, March, 2009.
[18] G. Jeon and J. Jeong, "Designing Takagi-Sugeno fuzzy model-based motion adaptive deinterlacing system," IEEE Trans. on Consumer Electronics, vol. 52, no. 3, p 1013-1020, August 2006.
[19] G. Jeon, R. Falcon, D. Kim, R. Lee, and J. Jeong, "Application of Bayesian belief network in reliable analysis for video deinterlacing," IEEE Trans. on Consumer Electronics, vol. 54, no. 1, pp. 123-139, Feb. 2008.
[20] G. Jeon, H. Choi, D. Kim, J. Lee, and J. Jeong, "A Bayesian network-based deinterlacing scheme," IEEE Int. Conf. on Consumer Electronics (ICCE), Taipei, Taiwan, Oct. 2008.
[21] J. Dong and K. N. Ngan, “An adaptive and parallel scheme for HD video de-interlacing,” IEEE Int. Conf. on Multimedia & Expo (ICME), pp. 1137-1140, Toronto, Canada, July 2006.
[22] G. Seo, H. Choi and C. Lee, "Efficient implementation of neural network deinterlacing," Society of Photographic Instrumentation Engineers (SPIE), vol. 7245,pp.724519-1－724519-1, 2009.
[23] D.H. Woo, I.K. Eom, Y.S. Kim, "Deinterlacing based on modularization by local frequency characteristics," Optical Engineering, vol. 45, no. 2, Feb. 2006.
[24] K. Ouyang, G. Shen, S. Li, and M. Gu, "Advanced Motion Search and Adaption Techniques for Deinterlacing," IEEE Int. Conf. on Multimedia and Expo (ICME), vol. 2005, pp.374-377, Amsterdam, The Netherlands, July 2005.
[25] K. Won, K. Lee and C. Lee, "Effective deinterlacing using selective spatial-temporal interpolation," in Proc. 2nd IEEE Int. Workshop on Soft Computing Applications, pp. 17-20, 2007.
[26] M. NICOLAS and J. ROUSSEL, "Low-cost handling of combing artifacts in motion-compensated deinterlacing ," IEEE Int. Conf. on Consumer Electronics (ICCE), pp.1-2, 10-14 Jan. 2007.
[27] Q. Huang, W. Gao, D. Zhao, H. Sun, "An efficient and robust adaptive deinterlacing technique," IEEE Trans. on Consumer Electronics, vol. 52, no. 3, pp. 888-895, Aug.2006.
[28] R. Li, B. Zeng, and M.L. Liou, "Reliable motion detection/compensation for interlaced sequences and its applications to deinterlacing," IEEE Trans. on Circuits and Systems for Video Technology, vol. 10, no. 1, pp. 23-29, Feb. 2000.
[29] I. Kim, T. Jeong, C. Lee, "Deinterlacing based on motion compensation with variable block sizes," Proceedings of SPIE - The International Society for Optical Engineering, vol. 6312, Applications of Digital Image Processing XXIX, pp.63120B-1－63120B-8, 2006.
[30] T. Jeong, Y. Kim, K. Sohn, C. Lee, "Deinterlacing with selective motion compensation," Optical Engineering, vol. 45, no. 7, pp.077001-1－077001-9 July 2006.
[31] C.C Lin, C.J. Wei, M.H. Sheu, and H.K. Chiang “The VLSI design of Motion Adaptive De-interlacing with Horizontal and Vertical Motions Detection”, IEEE Asia Pacific Conf. on Circuits and Systems, pp. 1587-1590, Dec. 2006.
[32] H.Sun, N. Zheng, C. Ge, D. Wang and P. Ren, “An efficient motion adaptive de-interlacing and Its VLSI architecture design”, IEEE Computer Society Annual Symp. on VLSI, pp. 455-458, April 2008.
[33] C.C. Lin, M.H. Sheu, H.K. Chiang, C. Liaw, and C.T. Tsai, “An efficient video de-interlacing with scene change detection”, IEEE Int. Conf. on Information, Communications and Signal Processing (ICICS), pp.36-40, Dec. 2005.
[34] Y.L. Chang, S.F. Lin, and L.G. Chen, "Extend intelligent edge-based line average with its implementation and test method," IEEE Int. Symp. on Circuits and Systems(ISCAS), pp.Ⅱ-341－Ⅱ-344, Vancouver, Canada, May 2004.
[35] S. Guo, C.H. Lin, and Z. Zhang, "A co-processor architecture for video scan-rate-conversion and spatial/temporal noise reduction," Proceedings of the International Symposium on Consumer Electronics (ISCE), pp. 34-38, 2005.
[36] Y. Yung, Y. Chen, and W. Zhung, "Motion adaptive deinterlacing combining with texture detection and its FPGA implementation," IEEE Int. Workshop on VLSI Design and Video Technology, pp. 405-408, 2005.
[37] H.Y. Lee, J.W. Park, T.M. Bae, S.U. Choi, and Y.H. Ha, "Adaptive scan rate up-conversion system based on human visual characteristics," IEEE Trans. on Consumer Electronics, vol. 46, no. 4, pp. 999-1006, Nov. 2000.
[38] Cheng Peng, Zhengting He, Cager Y., "An efficient motion-adaption de-interlacing technique on VLIW DSP architecture," IEEE Conf. on Advanced Video and Signal Based Surveillance, pp. 644-649, 15-16 Sep. 2005.
[39] C.E. Savin, M.O. Ahmad, Q. Gu, M.N.S. Swamy, "An efficient architecture for signal estimation using minimum mean absolute error rank-order filters with application to intrafield deinterlacing of video signals," Conf. on Electrical and Computer Engineering, vol. 2, pp. 752-755 , Sep. 1995.
[40] G.G.. Lee, M.J. Wang, B.H. Chen, J.F. Chen, P.K. Jao, C.J. Hsiao, and L.F. Wei, “Reconfigurable architecture for deinterlacer based on algorithm/architecture co-design”, Journal of Signal Processing Systems, June 2009.
[41] J. Eker, J.W. Janneck, CAL Language Report, Specification of the CAL actor language version 1.0 – document edition 1, Dec. 2003.
[42] K.K. Parhi, VLSI Digital Signal Processing Systems Design and Implementation, New York, Wiley, Chapter 6 Folding, 1999.
[43] Lee, G. G., Jang, E. S., Mattavelli, M., Tsai, C-J., Lucarz, C., Raulet, M., & Ding, D. (2008). “Text of ISO/IEC FCD 23001-4: Codec Configuration Representation,” ISO/IEC JCT1/SC29/ WG11 MPEG w9772, Archamps, France, Apr. 2008.
[44] Tung, Y-S., Lee, G-G., Jang, E. S., Lee, S., Asai, K., Yamada Y., & Mattavelli, M. (2008). “FCD ISO/IEC 23002-4: Video Tool Library,” ISO/IEC JCT1/SC29/WG11 MPEG w9774, Archamps, France, Apr. 2008.
[45] C.J. Lian, P.C. Tseng, T.C. Chen, Y.W. Chang, L.G.. Chen, "Reconfigurable architecture for video applications,",IEEE Int. SOC Conf. , pp.21-24, Sep. 2007
[46] J. Zheng, W. Gao, D. Wu, D. Xie, "A novel VLSI architecture of motion compensation for multiple standards," IEEE Trans. on Consumer Electronics , vol.54, no.2, pp.687-694, May 2008
[47] Bondalapati, Kiran; Prasanna, Viktor K.,"Reconfigurable computing systems," Proceedings of the IEEE, vol. 90, no. 7, pp. 1201-1217, 2002.
[48] Zain-ul-Abdin, Bertil Svensson, "Evolution in architectures and programming methodologies of coarse-grained reconfigurable computing," Microprocessors and Microsystems, vol. 33, no. 3, pp. 161-178, May 2009.
[49] A.S. Montemayor, F. Fernandez, J. Gutierrez, R. Cabido, and A. Sanchez, "Fuzzy motion detector based on 2D-convolutions for deinterlacing using graphics cards," in 11th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-based Systems (IPMU '06).