如何對龐大的多媒體資料進行尋取是一重要的研究議題。本研究是以影像相似度為基礎，將影像相似度延伸應用至影片相似尋取，利用影像在空間關係上的相似度，進行影片相似度之計算。本研究之目的是針對一參考影片，查詢參考影片中與查詢影片最為相似之片段。我們從參考影片中，隨機挑選多張影像組成一段影片，並計算此段影片與查詢影片的相似度，但隨機組合之結果數量龐大，對其一一計算相似度不是有效率之方法，所以，本研究加入基因演算法，利用其尋求近似最佳解之能力進行影片相似尋取。

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.