隨著影片資料量越來越龐大，如何在大量的資料中，進行影片尋取，儼然成為一個重要的議題。而基於內容的影片相似尋取(Content-based Video Retrieval)是一種處理影片資料較合適的解決方法之一。
本論文中，我們基於影片中物件的空間關係，利用基因演算法來進行影片尋取。針對物件間的空間變化關係定義了六種空間事件，並將其以字串表示，稱為空間事件字串。參考影片與查詢影片皆可產生出其影片之空間事件字串序列。接著，基於空間事件字串序列利用基因演算法與適應函數中的四種指標，查詢出參考影片中與查詢影片最為相似之影片片段。最後，實驗結果顯示本方法可成功地將與查詢影片相似之多組皆找尋出來。

When the video data becomes more and more, how to perform video retrieval in the large amount data is an important issue. Content-based video retrieval is one of the appropriate solutions for retrieving video data.
In this thesis, a Genetic Algorithm is used for video retrieval based on the change of the spatial relationship between objects in the video.Six spatial events are defined for the change of spatial relationship between objects and represented as spatial event strings.A spatial event string sequence (SESS) is constructed for the reference video.A SESS is also constructed for the query video.Then, Searching for the video segment in the reference video similar to the query video based on their spatial event string sequences is performed using a Genetic Algorithm with four indicators for its fitness function. Finally, experiments are performed and the results show that multiple similar video segments to the query video can be located successfully.

目錄
第一章	緒論	1
1.1　研究動機與目的	1
1.2　論文架構	4
第二章	相關研究	5
2.1　2D String	5
2.2　基因演算法	7
2.2.1	何謂基因演算法	7
2.2.2	基本架構	8
2.2.3	主要運算過程	9
2.3　影片尋取方法	10
2.3.1	全序列比對(Full-sequence Matching)	11
2.3.2	段比對(Segment Matching)	11
2.3.3	子序列比對(Subsequence Matching)	11
第三章	空間事件字串及影片相似尋取	14
3.1　六種空間事件	14
3.2  SES之相異度	27
3.3　影片尋取	29
3.3.1	初始族群	30
3.3.2	適應函式	34
3.3.3	選擇函式	38
3.3.4	交配方式	39
3.3.5	突變方式	42
3.3.6	影片相似尋取之範例	43
第四章	實驗與分析	64
4.1　實驗資料	64
4.2　影片查詢	65
4.2.1	第一組範例	66
4.2.2 	第二組範例	71
4.2.3	第三組範例	76
4.3　實驗分析	84
第五章	結論	86
參考文獻	87
圖目錄
圖 一、2D String範例及其表示法	7
圖 二、三種影片尋取之架構	13
圖 三、影片範例	21
圖 四、原始影片與影片SES序列關係對照圖	30
圖 五、初始族群	32
圖 六、對應字串組與候選片段之關係圖	33
圖 七、對應關係示意圖1	34
圖 八、對應關係示意圖2	35
圖 九、對應關係示意圖3	35
圖 十、對應關係示意圖4	36
圖 十一、交配範例	41
圖 十二、突變範例	42
圖 十三、影片相似尋取流程圖	44
圖 十四、範例之候選片段	46
圖 十五、範例之交叉個數	47
圖 十六、範例一之查詢結果(續)	53
圖 十七、範例二之查詢影片	55
圖 十八、範例二之查詢結果	58
圖 十九、範例三之查詢影片	59
圖 二十、範例三之查詢結果(續)	63
圖 二十一、標示物件示意圖	65
圖 二十二、第一組範例查詢影片	67
圖 二十三、第一組範例查詢結果(a)	69
圖 二十四、第一組範例查詢結果(b)	70
圖 二十五、第二組範例查詢影片	72
圖 二十六、第二組範例查詢結果(a)	74
圖 二十七、第二組範例查詢結果(b)	75
圖 二十八、第二組範例查詢結果(c)	75
圖 二十九、第三組範例查詢結果(a)	78
圖 三十、第三組範例查詢結果(b)	79
圖 三十一、第三組範例查詢結果(c)	82
表目錄
表 一、空間事件表	17
表 二、各空間事件其序值大小關係變化	20
表 三、範例影片其序值變化	22
表 四、符號表	36
表 五、SEQSES相似度	46
表 六、範例一演化過程	51
表 七、範例一之四組最佳近似解	54
表 八、範例二演化過程	56
表 九、範例二之四組最佳近似解	57
表 十、範例三演化過程	60
表 十一、範例三之四組最佳近似解	61
表 十二、第一組範例之四組最佳近似解	68
表 十三、第二組範例之四組最佳近似解	73
表 十四、第三組範例之四組最佳近似解	77
表 十五、兩影片尋取方法之實驗結果	85

[1]	Arndt, T., and Chang, S.K., “Image Sequence Compression by Iconic Indexing,” 1989 IEEE Workshop on Visual Languages, The Institute of Electrical and Electronic Engineers, IEEE Computer Society, Silverspring, MD, pp. 177-182, Oct. 1989.
[2]	Chang, S.K., Shi, Q.Y., and Yan, C.W., ”Iconic indexing by 2D-strings,” IEEE Trans. On Pattern Analysis and Matching Intelligence,PAMI-9,May,1987,pp.413-428.
[3]	Deb, S., “Video Data Management and Information Retrieval,” Idea Group Inc. 2005.
[4]	Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Streele, D., and Yanker, P., “Query by Image and Video Content: The QBIC System,” Computer, vol. 28, no. 9, pp. 23-32, Sept. 1995.
[5]	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, March 1992.
[6]	Hsu, F.J., Lee, S.Y., and Lin, B.S., “Video data indexing by 2D C-trees,” Journal of Visual Languages and Computing, vol. 9, pp. 375-397, 1998.
[7]	Huang, P.W., and Lee, C.H., “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Trans. on Knowledge and Data Engineering, vol. 16, no. 12, 2004.
[8]	John H. Holland, “Adaptation In Natural and Artificial Systems,” The University of Michigan Press, 1975.
[9]	Lee, S.Y., Yang, M.C., and Chen, J. W.,”2D B-string: a spatial knowledge representation for image database systems,” Proc.ICSC’92 Second Int. Computer Sci. Conf.,1992,pp.609-615.
[10]	Liu, C. C., and Chen, A.L.P., “3D-List: A Data Structure for Efficient Video Query Processing,” IEEE Trans. on Knowledge and Data Engineering, vol. 14, no. 1, 2002.
[11]	Shearer, K.R., Kieronska, D., and Venkatesh, S., “Resequencing Video Using Spatial Indexing,” J. Visual Languages Comput., vol. 8, pp. 193-214, 1997.
[12]	Shearer, K.R., Venkatesh, S., and Kieronska, D., “Spatial Indexing for Video Databases,” J. Visual Commun. Image Representation, vol. 7, pp. 325-335, 1996.
[13]	Smith, J.R., and Chang, S.F., “VisualSEEK: A Full Automated Content-Based Image Query System,” Proc. Fourth ACM Int’l Multimedia Conf., pp. 87-98, 1996.
[14]	YU, Jun-qing., HE, Yun-feng., SUN, Kai., Wang, Zhi-fang., WU, Xiang-mei., “ Semantic Analysis and Retrieval of Sports Video“ IEEE Computer Society 2006.
[15]	Back, T, Hammel, U, and Schwefel, HP, “Evolutionary Computation: Comments on the History and Current State,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, April 1997, pp.3-17.