隨著資訊系統的進步與網際網路的發達，多媒體系統的運用越來越多，影像資料庫又是相當重要的部分，如何從龐大的影像資料搜尋出使用者要的資料儼然成為一個熱門的議題。基於內容的相似影像尋取(Content-Based Image Retrieval，CBIR)是一查詢影像的重要方法。其中利用物件空間關係進行查詢是一常用的方法，然而在過往的研究中都沒有考慮到，影像中當物件之間發生重疊遮蔽時，其物件邊界不能確定的狀況，可能發生物件尋取上不夠完整的情形。因此本論文提出一種新的字串(2D B*-string)，影像中當物件之間發生重疊遮蔽狀況時，能根據此字串中推論出可能之空間關係，進而進行影像推論及其相似性檢索。

When the image data becomes more and more, there are more applications of multimedia systems. Image database plays an important role. Hence, how to retrieve the desired image from the image database efficiently is a popular research topic. Content-Based Image Retrieval (CBIR) is an important approach to image query. Image retrieval based on spatial relationship between objects becomes popular. However, the situation in which objects overlap has not taken into account in previous research. Therefore, we presents a new representation called 2D B*-string in this paper. When objects overlap, the reasoning of relationship between objects can be performed based on the 2D B*-string.

目錄
第一章緒論.............................................................................................................1
1.1研究動機與目的.............................................................................................1
1.2論文架構..........................................................................................................2
第二章相關研究.....................................................................................................3
2.1 2D-string ..........................................................................................................3
2.2 2D B-string .....................................................................................................4
第三章2D B*-string .............................................................................................6
3.1最小可能起始邊界及最大可能結束邊界.....................................................7
3.2 2D B*-string字串產生.................................................................................11
第四章以空間關係為基礎之影像空間關係推論..............................................16
4.1 Type A推論..................................................................................................17
4.2 Type B推論...................................................................................................18
第五章相似性檢索...............................................................................................21
5.1 「 Type A推論」之相似性檢索...............................................................21
5.2 「Type B推論」之相似性檢索...............................................................27
第六章結論...........................................................................................................32
參考文獻.................................................................................................................33
IV
圖目錄
圖1、2-D string之範例.........................................................................................4
圖 2、2D B-string之範例.......................................................................................5
圖 3、原始影像.......................................................................................................6
圖 4、處理過後的表示圖示...................................................................................6
圖 5、原始影像圖3可能存在之空間關係.........................................................7
圖 6、以物件本身的外框為邊界之示意圖..........................................................7
圖 7、沒有和其他物件相連之範例......................................................................8
圖 8、範例一...........................................................................................................9
圖 9、範例一之物件可能重疊覆蓋關係..............................................................9
圖 10、範例一投影至x軸...................................................................................10
圖 11、多物件相連...............................................................................................11
圖 12、範例二.......................................................................................................12
圖 13、實際範例圖...............................................................................................13
圖 14、一維度的13種空間關係........................................................................17
圖 15、x軸上兩物件間以序值推理空間關係的決策樹...................................18
圖 16、相似性檢索的範例...................................................................................23
圖 17、相似性檢索的範例相似關聯圖..............................................................27
V
表目錄
表1、兩物件相連時其可能的空間關係............................................................15
表 2、空間關係類型(Category) ...........................................................................26
表 3、相似性檢索範例中圖像f1及圖像f2的Type A相似性度量................27
表 4、物件對在兩影像的可能的空間關係........................................................28
表 5、相似性檢索範例中圖像f1及圖像f2的Type B的可能空間關係........31

[1]
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 , pp.413-42, May, 1987.
[2]
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.
[3]
Hsu, F. J., and Lee, S. Y., "Spatial Reasoning and Similarity Retrieval of Image Using 2D C-String Knowledge Representation," Pattern Recognition, Vol. 25, no. 3, pp. 305-318, March 1992.
[4]
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.
[5]
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.
[6]
Huang, P. W. and Jean, Y. R., "Using 2D C+ String as Spatial Knowledge Representation for Image Database Systems," Pattern Recognition, Vol. 27, No. 9, pp.1249-1257, 1994.
[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,pp.1486 - 1496, Dec. 2004.
[8]
Lee, Suh-Yin, Yang, Ming-Chwen, and Chen, Ju-Wei. "Signature file as a spatial filter for iconic image database," Journal of Visual Languages & Computing 3.4 , pp.373-397, 1992.
[9]
Smeulders, A.W.M., Worring, M., Santini, S., Gupta, A., and Jain, R.. "Content-Based Image Retrieval at the End of the Early Years," IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 22, No. 11, pp.1349-1380, 2000.
[10]
Smith, J.R., and Chang, S.F., "Visual SEEK: A Full Automated Content-Based Image Query System," Proc. Fourth ACM Int’l Multimedia Conf., pp.87-98, 1996.
[11]
Tamura, H., and Yokoya, N., "Image Database Systems: A Survey. Pattern Recognition," Vol. 17, No. 1, pp.29-43, 1984.