臺灣博碩士論文加值系統

本研究提出OG-string與Visibility-string兩個新的空間知識表示法，用來記錄物件增減頻繁的動態環境中基於觀察者角度而言，所有物件的可見度資訊，其中OG-string保存所有物件的虛擬阻礙集合(VBS, virtual Blocking Set)，便利在推論可見度過程時，可依據保存的VBS推論出物件在觀察者視界中的可見度，而Visibility-string保存所有物件在觀察者視界中的可見狀態(Visible State)及可見區段(Visible Interval)，對於每次物件增減變動後的空間可見度推論，可快速的經由OG-string與Visibility-string提供足夠的空間資訊，以觀察者為基準推論出週遭物件即時的可見度資訊。在這個研究中也提出動態環境可見度推論的演算方案，是以OG-string及Visibility為基礎，並包含了初始化演算、增加演算及刪除演算等三個演算法，用於物件增減頻繁的動態環境中，可協助觀察者對所有物件做可見度推論，如同於一個大型倉儲中，行動載具的路徑規劃也可獲得改善。

In this article, two new spatial knowledge representations called OG-string and Visibility-string are proposed for a dynamic environment seen from the observer’s perspective. The OG-string preserves the objects’ VBSs (Virtual Blocking Set) and can be used to determine visibility of objects. Because of having the same VBS, objects with the same begin-bound in ring-direction are grouped together. As a result the size of OG-string also can be reduced. The Visibility-string contains the objects’ visibility information, and thus can cooperate with OG-string to provide enough spatial information for dynamic visibility inference. We also represent a Dynamic Visibility Inference Scheme consisting of an Initialization, an Addition and a Deletion Algorithm based on the two new representations. The scheme assist with visibility inference for a dynamic environment where objects are added and deleted frequently just like in a warehouse so that a mobile robot’s path planning can be improved.

目錄
第一章 緒論 1
1.1 研究背景 1
1.1.1 空間推論 1
1.1.2 空間知識表示法 1
1.1.3 直角座標系統 2
1.1.4 極座標系統 2
1.1.5 可見度簡介 3
1.2 研究動機 3
1.3 研究成果 4
1.4 論文架構 5
第二章 文獻探討 6
2.1 2D string 6
2.2 2D C-string 7
2.3 2 R-string 10
2.4 2D RS-string 11
2.5 基於PCOS-string的可見度推論 15
2.5.1 可見度(visibility)定義 16
2.5.2 虛擬阻礙集合(VBS, Virtual Blocking Set) 18
2.5.3 基於PCOS-string的可見度推論演算 19
第三章 新空間知識表示法 21
3.1 動態可見度推論要素 21
3.2 Visibility-string 24
3.3 OG-string 26
第四章 動態可見度推論機制 27
4.1 投影區段(projection interval)合併與差集運算 27
4.1.1 區段差集運算 33
4.1.2 區段合併運算 33
4.2 調整區域的偵測 32
4.3 動態環境可見度推論機制 33
4.3.1 初始化演算 33
4.3.2 刪除演算 37
4.3.3 新增演算 38
4.3.4 時間複雜度 39
第五章 結論 41
參考文獻 42



圖目錄
圖1、 觀察者與環境中四個物件的空間關係。 3
圖2、 2D string沿著x軸與y軸取得兩組對空間關係字串。 7
圖3、 兩個物件在單維空間的13種空間關係。 8
圖4、 2D C-string 以MBR將圖像轉換為象徵物件(symbol object)。 9
圖5、 2D C-string 切割機制。 9
圖 6、 2 R-string空間運算元。 10
圖7、 同心圓方向與扇形方向的beginning-point與 ending point 。 11
圖8、 2 R-string對相似影像取用不同的中心物件產生不同的空間關係字串。 12
圖9、 2 R-string對不相似影像產生相同的空間關係字串。 12
圖10、 同心圓方向(ring-direction)的空間推論。 13
圖11、 扇形方向(sector-direction)的空間推論。 14
圖12、 物件B被hlaf-line分割成B''和B''兩個子物件。 14
圖13、 物件基於2D RS-string的空間位置表示。 15
圖14、 PCOS-string範例。 16
圖15、 物件可見度定義。 17
圖16、 物件Ot的虛擬阻礙區塊集合為{(1,5),(7,8),(9,10)}。 18
圖17、 由Huang與Lin提出的可見度演算法。 19
圖18、 一個動態環境中的物件。 24
圖19、 物件O4的可見區段是由多個子區段所構成VI4 = {(1,2), (3,4),(5,6),(78)}。 25
圖20、 Visibility-string與OG-string範例。 25
圖21、 區段的合併運算與差集運算。 30
圖22、 兩區段所有可能重疊的情況以及每種情況下的區段差集運算結果。 31
圖23、 兩區段所有可能重疊或毗連的情況及每種情況下區段合併運算結果。 32
圖24、 調整區域範例。 33



表目錄
表1、 空間知識表示法(Spatial Knowledge Representation)發展史。 2
表2、 2D C-string的Spatial Operators 定義。 8

[1]S.K. Chang, Q.Y. Shi, and C.W. Yan, “Iconic Indexing by 2D-strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(3), pp. 413-428, 1987.
[2]S. K. Chang and Li Y., “Representation of multi-resolution symbolic and binary pictures using 2D-H strings,” Proceedings of IEEE Workshop on Languages for Automata, pp.190-195, Maryland USA, Aug. 1988.
[3]E. Jungert and S. K. Chang, “Representation and retrieval of symbolic pictures using generalized 2D Strings,” Technique Report, University of Pittsburgh, PA 15260, 1988.
[4]S.Y. Lee and F.J. Hsu, “2D C-string: A New Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, 23(10), pp. 1077-1088, 1990.
[5]S. Y. Lee, M. C. Yang, and J. W. Chen, “2D B-String Knowledge Representation and Picture Retrieval for Image Database,” Proceedings of 2nd International Computer Science Conference Data and Knowledge Engineering, pp. 609-615, Hong Kong, Dec. 1992.
[6]G. Petraglia, M. Sebillo, M. Tucci, and G. Tortora, “Towards normalized iconic indexing,” Proceedings of the 1993 IEEE Symposium on Visual Languages, pp. 392-394, Bergen, Norway, 1993.
[7]P.W. Huang and Y.R. Jean, “Using 2D C+-strings as Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, 27(9), pp.1249-1257, 1994.
[8]C.C. Chang and D.C. Lin, “A spatial data representation: an adaptive 2D-H String,” Pattern Recognition Letters, 17(2), pp. 175-185, 1996.
[9]P.W. Huang and Y.R. Jean, “Spatial Reasoning and Similarity Retrieval for Image Database Systems Based on RS-string,” Pattern Recognition, 29(12), pp. 2103-2144, 1996.
[10]Bowon Kim and Kyhyun Um, “2D+ string: A Spatial Metadata to Reason Topological and Directional Relationships,” Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, pp. 112-121, Cleveland USA, Aug. 1999.
[11]F. J. Hsu, S. Y. Lee and, B. S. Lin, “2D C-Tree Spatial Representation for Iconic Image,” Journal of Visual Languages & Computing, 10(2), pp. 147-164, 1999.
[12]Ying-Hong Wang, “Image indexing and similarity retrieval based on spatial relationship model,” Information Sciences, 154(1-2), pp. 39-58, 2003.
[13]Anthony J.T. Lee and H. P. Chiu, “2D Z-string: A new spatial knowledge representation for image databases,” Pattern Recognition Letters, 24(16), pp. 3015-3026, 2003.
[14]P.W. Huang and P.L. Lin, “Visibility Inference Based on Spatial Knowledge Representation from Observer''s Perspective,” International Journal of Intelligent Systems, 12(3), pp. 191-202, 1997.
[15]C.C. Chang, “Spatial Match Retrieval of Symbolic Pictures,” Journal of Information Science and Engineering, vol. 7, pp. 405-422, Dec. 1991.
[16]P.W. Huang and C.H. Lee, “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Trans. Knowledge and Data Engineering, 16(12), Dec. 2004.
[17]P.W. Huang and Y.R. Jean, “Design of Large Intelligent Image Database Systems,” Int’l J. Intelligent Systems, 11, pp. 347-365, 1996.
[18]S.Y. Lee and F.J. Hsu, “Spatial Reasoning and Similarity Retrieval of Images Using 2D C-String Knowledge Representation,” Pattern Recognition, vol. 25(3), pp. 305-318, Mar. 1992.
[19]Y.R. Jean and Hao-Yu Lo, “An Improved Similarity Measure for Image Database Based on 2D C+-string,” Proceedings of 2004 International Computer Symposium, pp. 547-552, Taiwan, 2004.
[20]Y.R. Jean and Jui-Yi Chang, “RS-String-based Spatial Similarity Retrieval Method,” Proceedings of 7th IASTED International Conference on Signal and Image Processing (SIP2005), pp. 483-488, Hawaii, Aug. 2005.
[21]H.C. Lin, L.L. Wang, and S.N. Yang, “Color Image Retrieval Based on Hidden Markov Models,” IEEE Transactions on Image Processing, 6(2), pp. 332-339,Feb. 1997
[22]C.C Chang and C.F Lee “A spatial match retrieval mechanism for symbolic pictures,” Journal of Systems and Software, 44(1), pp. 73-83, Dec. 1998.
[23]Y.I. Chang, H.Y. Ann, and W.H. Yeh, “A unique-ID-based matrix strategy for efficient iconic indexing of symbolic pictures,” Pattern Recognition, 33(8), pp.1263-1276, 2000.
[24]Y.I. Chang, B.Y. Yang, and W.H. Yeh, “A bit-pattern-based matrix strategy for efficient iconic indexing of symbolic pictures,” Pattern Recognition Letters, 24(1-3), pp.537-545, 2003.
[25]張瑞怡，”一個針對影像資料庫的改良式旋轉不變相似擷取法 ─ 基於RS-string”，靜宜大學，碩士論文，民國94年6月。
[26]P. W. Huang and P. L. Lin, “Visibility Inference Based on Spatial Knowledge Representation from Observer''s Perspective,” International Journal of Intelligent Systems, 12(3), pp. 191-202, 1997.