淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1601201514380800
中文論文名稱 根據基因演算法產生之空間關係圖之影片尋取
英文論文名稱 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頁
口試委員 指導教授-梁恩輝
委員-謝禎冏
委員-張昭憲
委員-梁恩輝
中文關鍵字 基於內容的檢索  空間關係  空間關係圖  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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2015-01-19公開。
  • 同意授權瀏覽/列印電子全文服務,於2018-01-19起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信