視訊資料庫之知識結構與相似度查詢

Knowledge Structure and Similarity Retrieval in Video Databases

余平(Ping Yu)

指導教授 ： 李瑞庭

國立臺灣大學/管理學院/資訊管理學研究所/博士(2006年)

https://doi.org/10.6342/NTU.2006.02129

摘要

近年來，因傳統資料庫無法適當的處理視訊資料，使得如何有效的管理視訊資料庫成為熱門的研究課題。在視訊資料庫系統中，用來區別視訊最重要的方法之一，是利用視訊中的物件及物件間的空間與時間關係，而如何利用這些特性，將視訊儲存在視訊資料庫中，成為重要的視訊資料庫設計議題。
在本論文中，我們首先提出一個新的視訊知識結構3D C-string，可用來表示視訊中物件的空間與時間關係，且能持續追蹤各個物件的移動速度及大小的改變。然後，我們提出3DC相似度查詢演算法，藉由提供多種視訊的相似度型態，此查詢演算法具有在不同標準下區別視訊的能力。接著，我們提出另一個新的視訊知識結構3D Z-string，因不用將物件切割為子物件，使得此方法在儲存需求及執行時間上均較3D C-string更為簡潔且有效率。最後，我們提出3DZ相似度查詢演算法，因可找出部份相似的物件集合，且提供藉由回饋更新查詢結果的機制，使得此視訊查詢方法更具彈性，且更能符合使用者的需求。最後，我們進行一連串的實驗。實驗的結果顯示，本論文所提的方法，比以往的方法更具有效性及有用性。此外，我們也製作一個視訊資料庫雛型系統來實證本論文所提的各種方法。

關鍵字

視訊資料庫 ； 空間與時間關係推導 ； 3D C-string ； 3D Z-string ； 相似度查詢

並列摘要

In recent years, how to efficiently process and manage video databases has attracted more and more attention because traditional database systems are not suitable for processing those data. In video database systems, one of the most important methods for discriminating the videos is to use the perception of spatio-temporal relations between objects in the desired videos. Therefore, how videos are stored in a database becomes an important design issue of a video database system
In this dissertation, we first propose a new knowledge structure called 3D C-string. The 3D C-string can represent the spatio-temporal relations between objects in a video and keep track of the motions and size changes of the objects. Secondly, we propose the 3DC similarity retrieval algorithm. By providing various types of similarity between videos, our proposed approach has discriminating power about different criteria. Thirdly, we propose a new knowledge structure called 3D Z-string. Since there is no cutting between the objects in the video, the 3D Z-string approach is more compact and efficient than the 3D C-string approach in terms of storage requirement and execution time. Finally, we proposed the 3DZ similarity retrieval algorithm. Since the approach can find the partly matched object sets and provide the refined mechanism to meet users’ requirement from the feedbacks. The approach provides a more flexible way to retrieve similar videos. To show the efficiency and effectiveness of our proposed approaches, we perform a series of experiments to compare our proposed approaches with the previously proposed approaches. The experimental results show that our proposed approaches outperform the previously proposed approaches. We also develop a prototype video database management system that supports the methods presented in this dissertation.

並列關鍵字

Video databases ； Spatio-temporal inference ； 3D C-string ； 3D Z-string ； Similarity retrieval

參考文獻

[53] Overview of the MPEG-4 Standard, ISO/IEC JTC1/SC29/WG11, Mar 2001.

[1] Adali, S., Candan, K.S., Chen, S., Erol, K., Subrahmanian, V., “The advanced video information system: data structures and query processing,” Multimedia Systems, vol.4, pp. 172-186, 1996.

[2] Aghbari, Z., Kaneko, K., and Makinouchi, A., “Content-trajectory approach for searching video databases,” IEEE Trans. on Multimedia, vol. 5, no. 4, pp. 516-531, Dec. 2003.

[6] Caspi, Y. and Irani, M., “Spatio-temporal alignment of sequences,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 24, no. 11, pp. 1409-1424, 2002.

[10] Chang, S.K., Shi, Q.Y., and Yan, C.W., “Iconic indexing by 2D strings,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 9, no. 3, pp. 413-429, May 1987.