系統識別號 | U0002-1601201514380800 |
---|---|
DOI | 10.6846/TKU.2015.00432 |
論文名稱(中文) | 根據基因演算法產生之空間關係圖之影片尋取 |
論文名稱(英文) | Similarity Retrieval of Videos Based on the Spatial Relation Diagram Generated by the Genetic Algorithm |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊管理學系碩士班 |
系所名稱(英文) | Department of Information Management |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 103 |
學期 | 1 |
出版年 | 104 |
研究生(中文) | 卓建安 |
研究生(英文) | Chien-An Cho |
學號 | 601630063 |
學位類別 | 碩士 |
語言別 | 英文 |
第二語言別 | |
口試日期 | 2014-12-20 |
論文頁數 | 53頁 |
口試委員 |
指導教授
-
梁恩輝(094110@mail.tku.edu.tw)
委員 - 謝禎冏(cchsieh@ttu.edu.tw) 委員 - 張昭憲(jschang@mail.im.tku.edu.tw) 委員 - 梁恩輝(094110@mail.tku.edu.tw) |
關鍵字(中) |
基於內容的檢索 空間關係 空間關係圖 R-Tree 基因演算法 STR演算法 |
關鍵字(英) |
Content-based retrieval Spatial relation Spatial Relation Diagram R-Tree Genetic algorithms STR algorithm |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在過去影片檢索的相關論文中,使用建置於空間關係圖(Spatial Relation Diagram)上的R-tree作為影片尋取的索引結構。而影片之間的相似度則可以用影片中存在的各個物件對,在影片中所發生過的空間關係進行測量。 而在本研究中,我們修改了空間關係在空間關係圖中的位置,產生出修改後的空間關係圖,被命名為改良關係圖(Modified Relation Diagram),將R-tree建置於新的圖上,則可以為影片產生出更好的索引結構,影片尋取的效率也就可以提升。因此,本研究中我們提出了一個使用基因演算法的方法,來為每個物件對產生出接近最佳的索引結構。 |
英文摘要 |
An R-tree for each object pair built on a spatial relation diagram of these two objects has been used for retrieving similar videos. The similarity between videos is measured based on the spatial relations between objects. Non-similar data can be filtered at early stages of the process of query using the R-tree. However, a better R-tree can be obtained by modifying the spatial relation diagram such that the efficiency of the process of query can be improved. Hence, we propose to use the genetic algorithm to build a near-optimal R-tree structure for each object pair for similarity retrieval of videos. |
第三語言摘要 | |
論文目次 |
Contents Contents III List of Figures IV List of Tables VII 1 Introduction 1 2 Related Works 2 2.1 Similarity Retrieval of Videos 2 2.2 R-Tree 5 2.3 Search in R-tree 6 2.4 STR Algorithm 7 2.5 Genetic Algorithm 8 2.6 Genetic Algorithm 10 3 Similarity retrieval based on the Modified Relation Diagram 14 3.1 Relation Number 15 3.2 Construction of the Modified Relation Diagram using Genetic Algorithm 16 3.2.1 Initial Population 16 3.2.2 Fitness Function 17 3.2.3 Selection Function 18 3.2.4 Crossover 18 3.2.5 Mutation 19 4 Experiment 21 5 Conclusion 26 6 Reference 27 Appendix 1 The SR of each object pair in the first 12 shots represented in the SRD 30 Appendix 2 The SR of each object pair in the first 12 shots represented in the MRD 42 List of Figures FIGURE 1. 13 TYPES OF SPATIAL RELATIONSHIPS BETWEEN TWO INTERVALS IN ONE DIMENSIONAL SPACE 4 FIGURE 2. A MAP AND THE WINDOW QUERY Q 6 FIGURE 3. AN R-TREE STRUCTURE 7 FIGURE 4. AN EXAMPLE DATA SET 8 FIGURE 5. STR ALGORITHM PACKING RESULT 8 FIGURE 6. SPATIAL RELATION DIAGRAM 10 FIGURE 7. AN EXAMPLE SEQUENCE RECTANGLE 12 FIGURE 8. AN EXAMPLE R-TREE OF SEQUENCE RECTANGLES AND QUERY Q 13 FIGURE 9.A SEQUENCE RECTANGLE BETWEEN O 1AND O2. 14 FIGURE 10. A SEQUENCE RECTANGLE GENERATED FROM THE MODIFIED DIAGRAM 15 FIGURE 11.169 SPATIAL RELATIONS AND 169 RELATION NUMBERS 16 FIGURE 12. AN EXAMPLE CHROMOSOME FOR POSITIONS OF SPATIAL RELATIONS 17 FIGURE 13. THE SEQUENCE RECTANGLES OF OBJECT (O 1, O 2) ON EXAMPLE MRD 18 FIGURE 14. SELECT CROSSOVER POINTS AND MATCHING SECTION 19 FIGURE 15. AN EXAMPLE RESULT OF CROSSOVER 19 FIGURE 16. BEFORE MUTATION 20 FIGURE 17. AFTER MUTATION 20 FIGURE 18. FOUR OBJECTS OF AIR HOCKEY GAME 21 FIGURE 19. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND B IN SHOTS 1 – 6 (SRD) 30 FIGURE 20. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND B IN SHOTS 7 – 12 (SRD) 31 FIGURE 21. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND C IN SHOTS 1 – 6 (SRD) 32 FIGURE 22. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND C IN SHOTS 7 – 12 (SRD) 33 FIGURE 23. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND D IN SHOTS 1 – 6 (SRD) 34 FIGURE 24. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND D IN SHOTS 7 – 12 (SRD) 35 FIGURE 25. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND C IN SHOTS 1 – 6 (SRD) 36 FIGURE 26. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND C IN SHOTS 7 – 12 (SRD) 37 FIGURE 27. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND D IN SHOTS 1 – 6 (SRD) 38 FIGURE 28. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND D IN SHOTS 7 – 12 (SRD) 39 FIGURE 29. THE SEQUENCE RECTANGLES OF OBJECT PAIR C AND D IN SHOTS 1 – 6 (SRD) 40 FIGURE 30. THE SEQUENCE RECTANGLES OF OBJECT PAIR C AND D IN SHOTS 7 – 12 (SRD) 41 FIGURE 31. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND B IN SHOTS 1 – 6 (MRD) 42 FIGURE 32. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND B IN SHOTS 7 – 12 (MRD) 43 FIGURE 33. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND C IN SHOTS 1 – 6 (MRD) 44 FIGURE 34. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND C IN SHOTS 7 – 12 (MRD) 45 FIGURE 35. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND D IN SHOTS 1 – 6 (MRD) 46 FIGURE 36. THE SEQUENCE RECTANGLES OF OBJECT PAIR A AND D IN SHOTS 7 – 12 (MRD) 47 FIGURE 37. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND C IN SHOTS 1 – 6 (MRD) 48 FIGURE 38. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND C IN SHOTS 7 – 12 (MRD) 49 FIGURE 39. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND D IN SHOTS 1 – 6 (MRD) 50 FIGURE 40. THE SEQUENCE RECTANGLES OF OBJECT PAIR B AND D IN SHOTS 7 – 12 (MRD) 51 FIGURE 41. THE SEQUENCE RECTANGLES OF OBJECT PAIR C AND D IN SHOTS 1 – 6 (MRD) 52 FIGURE 42. THE SEQUENCE RECTANGLES OF OBJECT PAIR C AND D IN SHOTS 7 – 12 (MRD) 53 List of Tables TABLE 1. THE DEFINITION OF SPATIAL OPERATORS IN 2D C-STRING 4 TABLE 2. SPATIAL RELATION BETWEEN OBJECTS IN VIDEO SHOT E 11 TABLE 3. SPATIAL RELATIONS OF OBJECT PAIR (O 1, O 2) IN VIDEO DATABASE 18 TABLE 4. THE INFORMATION AT LEVEL 0 OF R-TREES ON SPATIAL RELATION DIAGRAM 23 TABLE 5. THE INFORMATION AT LEVEL 0 OF R-TREES ON THE MODIFIED RELATION DIAGRAMS 23 TABLE 6. THE INFORMATION AT LEVEL 1 OF R-TREES ON SPATIAL RELATION DIAGRAM 23 TABLE 7. THE INFORMATION AT LEVEL 1 OF R-TREES ON THE MODIFIED RELATION DIAGRAMS 24 TABLE 8. THE INFORMATION AT LEVEL 2 OF R-TREES ON SPATIAL RELATION DIAGRAM 24 TABLE 9. THE INFORMATION AT LEVEL 2 OF R-TREES ON THE MODIFIED RELATION DIAGRAMS 24 TABLE 10. THE RATIOS OF THREE PARAMETERS OF RETRIEVAL PERFORMANCE AT LEVEL 0. 24 TABLE 11. THE RATIOS OF THREE PARAMETERS OF RETRIEVAL PERFORMANCE AT LEVEL 1. 25 TABLE 12. THE RATIOS OF THREE PARAMETERS OF RETRIEVAL PERFORMANCE AT LEVEL 2. 25 |
參考文獻 |
[1]K.Sze, K. Lam, G. Qiu, "A New Key Frame Representation for Video Segment Retrieval", IEEE Transactions on Circuits and Systems for Video Technology, vol. 15,no. 9, pp. 1148 - 1155, 2005. [2]T. Xiang, S. Cong, “Activity Based Surveillance Video content Modeling”, Pattern Recognition, vol. 41, no. 7, pp. 2309 – 2326, 2008. [3]P. Yu, “Weighted Similarity Retrieval of Video Database”, ICIC Express Letters, vol. 4, no. 5, pp. 2009-2013, 2005. [4]C. C. Lo, S. J. Wang, L. W. Huang, “Video Retrieval using Successive Modular Operations on Temporal Similarity”, Computer Standards & Interfaces, vol. 26, no. 4, pp. 317–328, 2004. [5]A. Hanjalic, “Adaptive Extraction of Highlights from A Sport Video Based on Excitement Modeling”, IEEE Transactions on Multimedia, vol. 7,no. 6, pp. 1114 – 1122, 2005. [6]Z. Rasheed, Y Sheikh, M. Shah, “On the Use of Computable Features for Film Classification”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 1, pp. 52 – 64, 2005. [7]H. T. Shen, J. Shao, Z. Huang, X. Zhou, “Effective and Efficient Query Processing for Video Subsequence Identification”, IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 3, pp. 321 – 334, 2008. [8]B. Han, X. Gao, H. Ji, “A Shot Boundary Detection Method for News Video Based on Rough-Fuzzy Sets”, International Journal of Information Technology, vol. 11, no. 7, pp. 101–111, 2005. [9]S. K. Chang, Q. Y. Shi, C. W. Yan, “Iconic Indexing by 2-D string”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 9, no. 3, pp. 413-428, 1987. [10]E. Jungert, “Extended Symbolic Projection Used in A Knowledge Structure for Spatial Reasoning”, The 4th BPRA Conference on Pattern Recognition, Springer-Verlag, pp. 343-351, 1988. [11]S. K. Chang, E. Jungert, Y. Li, “Representation and Retrieval of Symbolic Pictures using Generalized 2D string”, Visual Communications and Image Processing IV, Philadelphia, pp. 1360 - 1372, 1989. [12]S. Y. Lee, F. J. Hsu, “2D C-string: A New Spatial Knowledge Representation for Image Database Systems”, Pattern Recognition, vol. 23,no. 10, pp. 1077 – 1087, 1990. [13]P. W. Hang, Y. R. Jean, “Using 2D C+-string as Spatial Knowledge Representation for Image Database Systems”, Pattern Recognition, vol. 27, no. 9, pp. 1249–1257, 1994. [14]A. J. T. Lee, H. P. Chiu, “2D Z-string: A New Spatial Knowledge Representation for Image Database”, Pattern Recognition Letters, vol. 24, no. 16, pp. 3015–3026, 2003. [15]M. Flicker, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, P. Yanker, “Query by Image and Video Content: The QBIC System”, IEEE Computer, vol. 28, no. 9, pp. 23 – 32, 1995. [16]M. Yeung, B. Yeo, B. Liu, “Extracting Story Units from Long Programs for Video Browsing and Navigation”, Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems, Hiroshima, pp. 296 – 305, 1996. [17]K. Shearer, S. Venkatesh, D. Kieronska, “Spatial Indexing for Video Database”, Journal of Visual Communication and Image Representation, vol. 7, no. 4, pp. 325–335, 1996. [18]F. J. Hsu, S. Y. Lee, B. S. Lin, “Video Data Indexing by 2D C- trees”, Journal of Visual Languages & Computing, vol. 9, no. 4, pp. 375–397, 1998. [19]Y. K. Chan, C. C. Chang, “Spatial Similarity Retrieval in Video Database”, Journal of Visual Communication and Image Representation, vol. 12, no. 2, pp. 107–122, 2001. [20]C. C. Liu, A. L. P. Chen, “3D-list: A Data Structure for Efficient Video Query Processing”, IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 1, pp. 106-122, 2002. [21]A. J. T. Lee, H. P. Chiu, P. Yu, “3D C-string: A new Spatio-temporal Knowledge Structure for Video Database Systems”, Pattern Recognition, vol. 35, pp. 2521-2537, 2002. [22]A. J. T. Lee, H. P. Chiu, P. Yu, “Similarity Retrieval of Video by using 3D C-string Knowledge Representation”, Journal of Visual Communication and Image Representation, vol. 16, no. 6, pp. 749–773, 2005. [23]A. J. T. Lee, H. P. Chiu, P. Yu, R. W. Hong, “3D Z-string: A New Knowledge Structure to Represent Spatio-temporal Relations Between Objects in A Video”, Pattern Recognition Letters, vol. 26, no. 16, pp. 2500–2508, 2005. [24]S. Y. Lee, M. K. Shan, W. P. Yang, “Similarity Retrieval of Iconic Image Database”, Pattern Recognition, vol. 22, no. 6, pp. 675–682, 1989. [25]E. H. Liang, M. F. Tung. “A Spatial Indexing Structure for Video Retrieval”, Master’s thesis, Tamkang University, 2007. [26]A. Guttman, “R-Tree: A Dynamic Index Structure for Spatial Searching”, ACM SIGMOD International Conference on Management of Data, New York, pp. 47-57, 1984. [27]S. T. Leuteneggert, M. A. Lopezt, J. Edgington, “STR: A Simple and Efficient algorithm for R-tree Packing”, Proc. of the 14th Int. conf. on Data Engineering, Birmingham, pp.497-506, 1997. [28]Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, Y. Theodoridis “R-trees: Theory and Applications”, Springer, ISBN: 9781852339777, 2006. [29]T. Brinkhoff, H. P. Kriegel, B. Seeger, “Efficient Processing of Spatial Joins Using R-trees”, Proceedings of the ACM SIGMOD international conference on management of data, New York, pp. 237-246, 1993. [30]S. N. Sivanandam, S. N. Deepa, “Introduction to Genetic Algorithms”, Springer Science& Business Media, ISBN: 9783540731900, 2007. [31]D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, ISBN: 0201157675, 1998. [32]A. Kumar, R. M. Pathak, M. C. Gupta, “Genetic Algorithm Based Approach for Designing Computer Network Topology”, Proceedings of the ACM conference on Computer science, New York, pp.358-365, 1993. [33]N. V. Patel ,I. K. Sethi, “Video Shot Detection and Characterization for Video Databases”, Pattern Recognition, vol.30, no. 4, pp.583–592, 1997. [34]D. W. Gavrila, “R-Tree Index Optimization”, Tech. Report CS- TR-3292, Univ. of Maryland, College Park, 1994. [35]N. Beckmann, H. P. Kriegel, R. Schneider, B. Seeger, “The R*-Tree: An Efficient and Robust Access Method for Point and Rectangles”, ACM SIGMOD international conference on Management of data, vol.19, no. 2, pp. 322 - 331, 1990. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信