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


  查詢圖書館館藏目錄
系統識別號 U0002-2306201113560300
中文論文名稱 一個根據空間關係進行影片尋取之基因演算法
英文論文名稱 A Genetic Algorithm for Video Retrieval based on Spatial Relations
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 99
學期 2
出版年 100
研究生中文姓名 張貴棠
研究生英文姓名 Kuei-Tang Chang
學號 698630026
學位類別 碩士
語文別 中文
口試日期 2011-05-28
論文頁數 77頁
口試委員 指導教授-梁恩輝
委員-魏世杰
委員-萬書言
委員-吳瑞堯
中文關鍵字 影片尋取  相似尋取  基因演算法  影像相似度 
英文關鍵字 Video Retrieval  Similarity Retrieval  Genetic Algorithm  Image Similarity 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 如何對龐大的多媒體資料進行尋取是一重要的研究議題。本研究是以影像相似度為基礎,將影像相似度延伸應用至影片相似尋取,利用影像在空間關係上的相似度,進行影片相似度之計算。本研究之目的是針對一參考影片,查詢參考影片中與查詢影片最為相似之片段。我們從參考影片中,隨機挑選多張影像組成一段影片,並計算此段影片與查詢影片的相似度,但隨機組合之結果數量龐大,對其一一計算相似度不是有效率之方法,所以,本研究加入基因演算法,利用其尋求近似最佳解之能力進行影片相似尋取。
英文摘要 How to retrieve multimedia information is an important issue. Based on image similarity, our research extends to similarity retrieval for video. We measure video similarity according to spatial relation in images. Given a reference video, our objective is to retrieve the video segment in the reference video the most similar to query video. We select frames randomly from the reference video to compose them as a video segment and measure the similarity between it and the query video. But, the amount of random selection is very huge. It is not efficient to measure video similarity for each selection. Therefore, we propose the genetic algorithm to retrieve the video segment which is the most similar to query video in this paper.
論文目次 目錄
第一章 緒論 1
1.1 研究動機與目的 1
1.2 論文架構 4
第二章 相關研究 5
2.1 空間關係表示法 5
2.1.1 2D String 5
2.1.2 2D B-String 6
2.2 影像相似計算演算法 8
2.3 基因演算法 13
2.3.1 何謂基因演算法 13
2.3.2 基因演算法的基本架構 14
2.3.3 基因演算法主要運算過程 14
第三章 影片相似尋取 17
3.1 去除重覆字串 17
3.2 以基因演算法進行影片相似尋取 18
3.2.1 初始族群 18
3.2.2 適應函式 21
3.2.3 選擇函式 25
3.2.4 交配方式 26
3.2.5 突變方式 27
3.2.6 影片相似尋取之範例 28
第四章 實驗與分析 36
4.1 實驗資料 36
4.2 系統介面 38
4.3 影片查詢 43
4.4 實驗結果 44
第五章 結論 54
參考文獻 55


圖目錄
圖 1 2D STRING範例圖形 6
圖 2 2D B-STRING範例圖形 7
圖 3 查詢影像與資料庫影像之範例 8
圖 4 影像A和B在X軸上之2D B-STRING 11
圖 5 去除重覆字串示意圖 18
圖 6 初始族群 20
圖 7 對應關係示意圖1 21
圖 8 對應關係示意圖2 22
圖 9 對應關係示意圖3 22
圖 10 對應關係示意圖4 22
圖 11 交配範例 27
圖 12 突變範例 28
圖 13 範例之查詢影片 29
圖 14 影片相似尋取之流程圖 30
圖 15 交叉個數 32
圖 16 範例之查詢結果 35
圖 17 框選物件示意圖 37
圖 18 系統查詢介面1 38
圖 19 系統查詢介面2 39
圖 20 系統查詢介面3 40
圖 21 系統查詢介面4 41
圖 22 參數設定介面 42
圖 23 查詢結果輸出介面 42
圖 24 影片查詢範例之查詢影片 44
圖 25 查詢影片1 45
圖 26 查詢影片2 46
圖 27 查詢影片3 47
圖 28 查詢影片4 48
圖 29 查詢影片5 49


表目錄
表 1 符號表 23
表 2 演化過程 34
表 3 相似PLAY數量表 51
表 4 實驗結果 53


附錄目錄
附錄 1 影片查詢範例之查詢結果 57
附錄 2 與查詢影片1相似之查詢結果1 59
附錄 3 與查詢影片1相似之查詢結果2 60
附錄 4 與查詢影片1相似之查詢結果3 61
附錄 5 與查詢影片2相似之查詢結果1 62
附錄 6 與查詢影片2相似之查詢結果2 63
附錄 7 與查詢影片2相似之查詢結果3 64
附錄 8 與查詢影片3相似之查詢結果1 65
附錄 9 與查詢影片3相似之查詢結果2 66
附錄 10 與查詢影片3相似之查詢結果3 68
附錄 11 與查詢影片4相似之查詢結果1 70
附錄 12 與查詢影片4相似之查詢結果2 71
附錄 13 與查詢影片4相似之查詢結果3 72
附錄 14 與查詢影片5相似之查詢結果1 73
附錄 15 與查詢影片5相似之查詢結果2 73
附錄 16 與查詢影片5相似之查詢結果3 76
參考文獻 中文部份
[1] 黃悌維,《影像資料庫中一個相似尋取之方法》,未出版之碩士論文,淡江大學資訊管理學系,2002。
英文部份
[2] Arndt, T., and Chang, S. K., “Image Sequence Compression by Iconic Indexing,” IEEE Workshop on Visual Languages, pp. 177-182, Oct. 1989.
[3] Chang, S. K., Shi, Q. Y., and Yan, C. W., “Iconic indexing by 2D-strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 9, no. 3, pp. 413-428, May. 1987.
[4] Deb, S., Video Data Management and Information Retrieval, Idea Group Inc., 2005.
[5] Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., and Gorkani, M., “Query by Image and Video Content: The QBIC System,” Computer, vol. 28, no. 9, pp. 23-32, Sep. 1995.
[6] Hsu, F. J., and Lee, S. Y., “Spatial Reasoning and Similarity Retrieval of Images Using 2D C-String Knowledge Representation,” Pattern Recognition, vol. 25, no. 3, pp. 305-318, Mar. 1992.
[7] Huang, P. W., and Lee, C. H., “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 12, pp. 1486, Dec. 2004.
[8] Lee, S. Y., Yang, M. C., and Chen, J. W., “2D B-string: a spatial knowledge representation for image database systems,” in Proceedings of Second International Computer Science Conference (ICSC'92), Hong Kong, pp. 609-615, 1992.
[9] Liu, C. C., and Chen, A. L. P., “3D-List: A Data Structure for Efficient Video Query Processing,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 1, Jan. 2002.
[10] Shearer, K., Bunke, H., and Venkatesh, S., “Video Indexing and Similarity Retrieval by Largest Common Subgraph Detection using Decision Trees,” Pattern Recognition, vol. 34, no. 5, pp. 1075-1091, May. 2001.
[11] Shearer, K., Kieronska, D., and Venkatesh, S., “Resequencing Video Using Spatial Indexing,” Journal of Visual Languages and Computing, vol. 8, no. 2, pp. 193-214, Apr. 1997.
[12] Shearer, K., Venkatesh, S., and Kieronska, D., “Spatial Indexing for Video Databases,” Journal of Visual Communication and Image Representation, vol. 7, no. 4, pp. 325-335, Dec. 1996.
[13] Smith, J. R., and Chang, S. F., “VisualSEEK: A Full Automated Content-Based Image Query System,” in Proceeding MULTIMEDIA '96 Proceedings of the fourth ACM international conference on Multimedia, New York, 1996.
[14] Yu, P., Hwang, C., and Kuo, N., “Similarity Retrieval of Video Database Based on 3D Z-string,” International Symposium on Electronic Commerce and Security, pp. 56-59, 2009.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2016-06-24公開。
  • 不同意授權瀏覽/列印電子全文服務。


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