一種基于矩陣的MBR方向關系模型

摘要：在空間主方向關系推理的研究中，方向關系模型是其中一項至關重要的課題。介紹了區(qū)間代數(shù)模型、矩形代數(shù)模型和極小邊界盒模型，提出了區(qū)間代數(shù)的矩陣表示方法，并給出了以矩陣表示的區(qū)間代數(shù)和方向關系矩陣之間的轉(zhuǎn)換方法。

關鍵詞：方向關系模型；方向關系矩陣

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9599 （2012） 17-0000-02

1 引言

在空間主方向關系推理的研究中方向關系模型起著至關重要的作用。Allen在1983年提出了區(qū)間代數(shù)理論，他提出區(qū)間代數(shù)中共有13種原子區(qū)間關系，并給出了這13種原子區(qū)間關系的基本運算法則。Balbiani提出了矩形代數(shù)理論。根據(jù)MBR模型，Theodorids建立了基于MBR的主方向關系模型。[1]

本文將方向關系矩陣模型與MBR模型、區(qū)間代數(shù)和矩形代數(shù)模型相結(jié)合，利用這三種模型之間的關系，提出了區(qū)間代數(shù)的矩陣表示形式，并給出了以矩陣表示的區(qū)間代數(shù)和MBR模型之間的轉(zhuǎn)換方法。

2 區(qū)間代數(shù)和矩形代數(shù)和MBR的主方向關系模型

2.1 區(qū)間代數(shù)理論

區(qū)間代數(shù)理論指出，任意兩個有限區(qū)間之間，存在13種關系，稱為區(qū)間代數(shù)的原子關系。如果原子關系的集合用Aint來表示，那么Aint={p，m，o，s，d，f，pi，mi，oi，si，di，fi，eq}。區(qū)間的基本關系是區(qū)間原子關系的^。

2.2 矩形代數(shù)理論

矩形代數(shù)理論是將區(qū)間代數(shù)的一維關系擴展到二維空間而形成的。矩形代數(shù)中矩形框的四邊平行于空間中的x軸和y軸。每一個矩形框向坐標軸的投影都是一個有限區(qū)間，因此矩形代數(shù)關系可以分別向兩個坐標軸投影，將矩形關系分解為坐標軸上的區(qū)間代數(shù)關系。兩個矩形物體的原子關系集合用Arec表示，它們分解到兩個坐標軸上的區(qū)間關系分別有13種，那么矩形代數(shù)的原子關系集合中的關系數(shù)量就有13*13種，即169種。矩形代數(shù)的基本關系就是矩形代數(shù)原子關系的合取，那么矩形代數(shù)基本關系就有2169種。若A和B分別表示矩形代數(shù)關系在x軸和y軸上映射的區(qū)間原子關系，那么這個矩形代數(shù)關系就可以表示為A和B的笛卡爾積，即A×B。

2.3 MBR主方向關系模型

Theodorids利用MBR建立了基于MBR的主方向關系模型，使用物體的極小邊界盒之間的關系來表示物體之間的方向關系稱為MBR方向關系。MBR的主方向關系模型中的兩個矩形之間有 36種基本方向關系，表示為： NW，SW， NW：NE：N，N：NE，SW：SE：S，NW：W，NW：W：N：B， NW：W：N：NE：E：B，N：B，N：NE：E：B，NE：E，NW：SW：W，N：W：B，W，W：B，NW：NE：N：W：E：B：SW：SE：S， NE：SE：E， W：E：B，N：B：NE：S：E：SE，NW：W：SW：N：B：S， B：E， W：SW，W：E：B SE：S：SW：，B：S，NE，B：S：SE：E，N，E：SE，B，SW：S，S：SE，E，NW：N，W：S：B：SW， SE。[2]

矩形關系和基于MBR主方向關系的基本關系之間的關系存在以下定理。

定理1：設a和b是兩個物體的MBR，若它們之間的方向關系是a B b，其對應的矩形代數(shù)關系為{eq，s，f，d }?{eq，s，f，d }，表示為：B??{eq，s，f，d }?{eq，s，f，d }。同樣可以得到以下結(jié)論： SW ? {p，m}×{p，m}。NW ? {p，m}×{pi，mi}。NE ? {pi，mi}×{pi，mi}。SE ? {pi，mi}×{p，m}。S ? {eq，s，f，d }×{p，m}。 W ? {p，m}×{eq，s，f，d }。N ? {eq，s，f，d }×{pi，mi}。E ? {pi，mi}×{eq，s，f，d }。

根據(jù)定理1的結(jié)論，MBR主方向關系的每一個原子關系分別對應著一組矩形代數(shù)關系。由于區(qū)間原子關系存在端點重合的情況，如果將這些端點重合的情況合并，就可以得到六組區(qū)間代數(shù)的基本關系，分別是{p，m}、{o，fi}、{di}、{eq，s，f，d }、{oi， si}和{pi，mi}，利用區(qū)間代數(shù)的基本關系，我們可以得到基于MBR主方向關系的36種基本關系的矩形關系定義。

定理2：基于MBR的基本方向關系一一對應于區(qū)間基本關系的笛卡爾積所形成的矩形關系。

定理3：在基本區(qū)間關系中任取兩組，將這兩組基本區(qū)間關系的冪集（除去空集）做 ×操作，所得到的結(jié)果對應于一個基于MBR的基本方向關系，并且是一一對應的。

上述兩個定理可以利用群舉法得到。

3 矩陣模型和區(qū)間代數(shù)以及矩形模型的關系

根據(jù)MBR的定義，空間區(qū)域a在坐標軸上的投影同MBR在相應坐標軸上的投影是相同的。將參考物體分割為9個區(qū)域，用一個3*3的方向關系矩陣可以清晰的表示這些區(qū)域之間的相鄰關系和兩個物體之間的相交情況，參考物體的9個區(qū)域分別對應方向關系矩陣中的9個元素，如果目標物體和參考物體相交，則用1表示，如果不相交則用0表示。MBR主方向關系的36種基本關系可以用方向關系矩陣來表示。

方向關系矩陣有兩種基本運算：向X軸的投影MapX和向Y軸的投影MapY。R表示一個基本方向關系矩陣，這兩種運算分別表示為MapX（R）和MapY（R）。定義如下：

定義MapX（R）：設基本方向關系矩陣以R來表示，它表示的是一個矩形方向關系。那么MapX（R）為矩陣R最北邊的矩形關系的矩陣，去除全部為0的行后所得到的一維矩陣。

同樣，定義MapY（R）即為矩陣R的最西邊的矩形關系的矩陣表示，去除全部為0的列以后所得到的一維矩陣。

定理4：設R是一個基本主方向關系，那么有：

R= MapY（R）×MapX（R）

而MapY（R）和MapX（R）是基本方向關系中的一種。

六組區(qū)間代數(shù)關系的矩陣表示可以通過對基本MBR主方向關系進行投影運算得到。

劃分后的六組區(qū)間代數(shù)關系的矩陣表示為：{p，m}對應的矩陣表示為 ，{o，fi}對應的矩陣表示為 ，{di}對應的矩陣表示為 ，{eq，s，d，f}對應的矩陣表示為 ，{si，oi}對應的矩陣表示為 ，{pi，mi}對應的矩陣表示為 。

證明：矩陣 對應MBR主方向關系SW，SW對應{p，m}×{p，m}，而MapX （ ）= ，因此關系{p，m}對應的矩陣表示為 。同理可以證明其他區(qū)間關系的矩陣表示形式。

MBR基本主方向關系的矩陣是一個3×1矩陣和一個1×3矩陣做笛卡爾積得到的，而這個3×1矩陣是六組基本區(qū)間代數(shù)關系矩陣做轉(zhuǎn)置得到的，

由此我們可以得到一下結(jié)論：MapY（R）是基本區(qū)間代數(shù)關系矩陣的轉(zhuǎn)置。

定理5：R是一個基本主方向關系矩陣，那么R為MapY（R）何MapX（R）的笛卡爾積，即R= MapY（R）×MapX（R），其中MapX（R）和MapY（R）的轉(zhuǎn)置都是基本區(qū)間關系的矩陣表示。

定理5可以通過群舉法證明，證明過程略。定理5在求解方向關系矩陣的反關系和進行一致性場景的查找時都有重要作用。

4 結(jié)論

在空間方向關系模型領域，區(qū)間代數(shù)模型、矩形代數(shù)模型和MBR主方向關系模型是三種比較重要的方向關系模型，而方向關系矩陣模型則是比較完善的一種新的方向關系模型，我們利用區(qū)間代數(shù)、矩形代數(shù)和MBR三種模型之間的關系，通過方向關系矩陣來表示這三種方向關系模型，給出了MBR和區(qū)間代數(shù)、矩形代數(shù)的方向關系矩陣之間的轉(zhuǎn)換方法，這種方法為進行定性的空間方向關系推理奠定了基礎。

參考文獻：

[1]楊楠，石偉鉑.基于矩陣的MBR主方向關系的反關系[J].燕山大學學報，2007（03）.

[2]石偉鉑.基于MBR的主方向關系推理[D].燕山大學，2007.

本文系2010年秦皇島市科學技術研究與發(fā)展計劃項目（編號：201001A013）研究成果