隨著多媒體擷取技術之進步，多媒體資料已和我們的生活更加緊密結合，尤以視訊影片為盛。如何準確且有效率地擷取使用者所感興趣的影片，是影片搜尋之主要目的。由於影片內容比單張影像包含更豐富的時間與空間上之資訊，目前許多研究除了取出影片的低階特徵值外，也考慮存在於鏡頭片段序列之隱含意義，試著找出關聯性以相互結合，希望將低階特徵值轉換為高階意涵來進行更準確的影片擷取。然而，許多方法不斷致力於追求更高準確度之同時，卻往往忽略了效率的考量，導致雖然提昇準確率，卻反而降低執行效能，因此，為求快速尋找相似影片，利用分群、量化或註解影片等方式來改善索引架構是最通用之方法。在本研究中，我們發展一種快速樣式索引技術，利用編碼原則，讓鏡頭片段以低維度的群組定義來取代高維度之低階特徵值，藉以降低計算複雜度，同時考慮存在於影片中的連續關聯性，搭配滑動視窗來產生關鍵影格樣式，以提昇搜尋準確率，並透過獨特設計之快速樣式索引樹，可快速地找到相似影片。實驗結果顯示，我們所提出之方法的確能準確且有效地進行影片搜尋，而準確率與執行效能的表現上，也優於其他兩個用來作比較之方法。

With the progress of multimedia capturing technique, the multimedia data is more and more tightly bound up with our life, especially for video data. How to access the user-interested videos efficiently and effectively is a hot topic for content-based video retrieval. Because a video is with richer spatial and temporal information than an image, lots of recent works attempt to make an excellent video exploration by using not only visual features but also the implicit semantics hidden in a sequence of video events. These works always put the concentration on how to enhance the accuracy but ignore another important issue: efficiency. In other words, up to the present, the conventional content-based video retrieval methods have not overcome the efficiency problem that high accuracy mostly brings out the great time cost. For this reason, we propose a fast-pattern-index technique to support content-based video retrieval in this paper. In our method, the high dimensionality of low-level features is first reduced to improve the retrieval performance by clustering operation. Then we make use of the temporal continuity between shots to find the valuable patterns within a sliding window and to construct the FPI-tree. Through traversing the proposed FPI-tree, the videos that are related to user’s intention can be found rapidly. Experimental evaluations reveal that our approach outperforms other two contemporary approaches in terms of accuracy and efficiency.

[1]D. A. Adjeroh, M. C. Lee, and I. King. A Distance Measure for Video Sequences Similarity Matching. Proceedings of the IEEE Conference on Multimedia Computing and Systems, pp.72-79, Austin, Texas, August 1998.
[2]R. Agrawal, T. Imielinski, and A. Swami. Mining Association Rules between Sets of Items in Large Databases. Proceedings of the 1993 ACM SIGMOD international conference on Management of data, pp. 207-216, Washington, DC, USA, May 1993.
[3]R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. Proceedings of the 20th International Conference on Very Large Data Bases, pp. 487-499, Santiago de Chile, Chile, September 1994.
[4]H. Aoki, S. Shimotsuji, and O. Hori. A Shot classification Method of Selecting Effective Key-Frames for Video Browsing. Proceedings of the 4th ACM international conference on Multimedia, pp. 1-10, Boston, Massachusetts, USA, November 1996.
[5]F. Arman, R. Depommier, A. Hsu, and M. Y. Chiu. Content-based Browsing of Video Sequences. Proceedings of the 2nd ACM International Conference on Multimedia, pp. 97-103, San Francisco, USA, October 1994.
[6]L. Chen and T. S. Chua. A Match and Tiling Approach to Content-based Video Retrieval. Proceedings of IEEE International Conference on Multimedia and Expo, pp. 301-304, Tokyo, Japan, August 2001.
[7]W. G. Cheng and D. Xu. Content-based video retrieval using the shot cluster tree. Proceedings of the 2nd IEEE International Conference on Machine Learning and Cybernetics, pp. 2901-2906, Xi’an, China, November 2003.
[8]S. C. Cheung and A. Zakhor. Fast similarity search and clustering of video sequences on the world-wide-web. IEEE Transaction on Multimedia, Vol. 7, No. 3, pp. 524–537, June 2005.
[9]N. Dimitrova, H. J. Zhang, B. Shahraray, I. Sezan, T. Huang, and A. Zakhor. Applications of video-content analysis and retrieval. IEEE Transactions on Multimedia, Vol. 9, pp. 42-55, July-September 2002.
[10]G. Gaughan, A.F. Smeaton, C. Gurrin, H. Lee, and K. Mc Donald. Design, Implementation and Testing of an Interactive Video Retrieval System, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, pp. 23-30, Berkeley, CA, USA, November 2003.
[11]J. A. Hartigan and M. A. Wong. A K-Means Clustering Algorithm, Applied Statistics, Vol. 28, pp. 100-108, 1979.
[12]Y. H. Ho, C. W. Lin, J. F. Chen, and Mark H. Y. Liao. Fast coarse-to-fine video retrieval using shot-level statistics. IEEE Transactions on Circuits and Systems for Video Technology, Vol. 16, No. 5, May 2006.
[13]A.K. Jain, A. Vailaya, and X. Wei. Query by Video Clip. ACM Multimedia Systems : Special Issue on Video Libraries, Vol. 7, No. 5, pp. 369-384, Secaucus, NJ, USA, September 1999.
[14]S. H. Kim and R.-H. Park. An Efficient Algorithm for Video Sequence Matching Using the Modified Hausdroff Distance and the Directed Divergence. IEEE Transactions on Circuits System Video Technology, Vol. 12, No. 7, pp. 592-596, July 2002.
[15]Y. T. Kim and T. S. Chua. Retrieval of News Video using Video Sequence Matching. Proceedings of the 11th International Multimedia Modelling Conference, Vol. 00, pp. 68-75, Washington, DC, USA, January 2005
[16]X. Liu, Y. Zhuang, and Y. Pan. A New Approach to Retrieve Video by Example Video Clip. Proceedings of the 7th ACM international conference on Multimedia, pp. 41-44, Orlando, Florida, USA, November 1999.
[17]S. Lu, Michael R. Lyu, and I. King. Semantic Video Summarization Using Mutual Reinforcement Principle and Shot Arrangement Patterns. Proceedings of 11th International Multimedia Modeling Conference, pp. 60-67, Melbourne, Australia, January 2005.
[18]Milind R. Naphade, C. Y. Lin, John R. Smith, Belle Tseng, and S. Basu. Learning to Annotate Video Database. Proceedings of SPIE Conference on Storage and Retrieval for Media Databases, pp. 20-25, San Jose, CA, January 2002.
[19]Y. Peng and C. W. Ngo. Clip-based Similarity Measure for Hierarchical Video Retrieval. Proceedings of the 6th ACM SIGMM International Workshop on Multimedia Information Retrieval, pp. 53-60, New York, NY, USA, October 2004.
[20]Y. Peng and C. W. Ngo. Clip-Based Similarity Measure for Query-Dependent Clip Retrieval and Video Summarization. IEEE Transactions on Circuits and Systems for Video Technology, Vol. 16, No. 5, pp. 612-627, May 2006.
[21]Dulce B. Ponceleon, S. Srinivasan, A. Amir, D. Petkovic, and D. Diklic. Key to Effective Video Retrieval:Effective Cataloging and Browsing. Proceedings of the 6th ACM International Conference on Multimedia, pp. 99-107, Bristol, UK, September 1998.
[22]M. Rautiainen, T. Ojala, and T. Seppänen. Analysing the performance of visual, concept and text features in content-based video retrieval. Proceedings of the 6th ACM SIGMM International Workshop on Multimedia Information Retrieval, pp. 197-204, New York, NY, USA, October 2004.
[23]Y. Rui, T. S. Huang, S. Mehrotra. Exploring video structure beyond the shots. Proceedings of the ICMCS'98 IEEE Conference on Multimedia Computing and Systems, pp. 237-240, Austin, TX, USA, June 1998.
[24]S. Santini and R. Jain. Similarity Measures. IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 21, No. 9, pp. 871-883, Sepember 1999.
[25]M. K. Shan and S. Y. Lee. Content-based Video Retrieval based on Similarity of Frame Sequence. Proceedings of the IEEE Conference on Multimedia Computing and Systems, pp.90-97, Austin, Texas, USA, August 1998.
[26]S. W. Smoliar and H. Zhang. Content-Based Video Indexing and Retrieval. IEEE Transactions on Multimedia, Vol. 1, No. 2, pp. 62-72, June 1994.
[27]R. Srikant and R. Agrawal. Mining Generalized Association Rules. Proceedings of the 21th International Conference on Very Large Data Bases, pp. 420-431, Zurich, Switzerland, September 1995.
[28]P. Virga and P. Duygulu. Systematic Evaluation of Machine Translation Methods for Image and Video Annotation. Proceedings of the 4th International Conference on Image and Video Retrieval, pp. 487-496, Singapore, July 2005.
[29]Y. Wu, Y. Zhuang, and Y. Pan. Content-Based Video Similarity Model. Proceedings
of the 8th ACM International Multimedia Conference on Multimedia, pp. 465–467, Los Angeles, CA, USA, 2000.
[30]J. Yuan, L. Y. Duan, Q. Tian, and C. Xu. Fast and robust short video clip search using an index structure. Proceedings of the 6th ACM SIGMM international Workshop on Multimedia Information Retrieval, pp. 61-68 ,New York, NY, USA, October 2004.
[31]D. Zhong, H. J. Zhang, and S. F. Chang. Clustering Methods for Video Browsing and Annotation. Proceedings of SPIE Conference on Storage and Retrieval for Image and Video Databases, pp. 76-87, San Jose, CA, February 1996.
[32]X. Zhu, A. K. Elmagarmid, X. Xue, L. Wu, and A. C. Catlin. InsightVideo： Toward Hierarchical Video Content Organization for Efficient Browsing, Summarization and Retrieval. IEEE Transactions on Multimedia, Vol. 7, No. 4, pp. 648-665, August 2005.