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

關(guān)鍵詞：方向關(guān)系模型；方向關(guān)系矩陣

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 17-0000-02

1 引言

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

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

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

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

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

2.2 矩形代數(shù)理論

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

2.3 MBR主方向關(guān)系模型

Theodorids利用MBR建立了基于MBR的主方向關(guān)系模型，使用物體的極小邊界盒之間的關(guān)系來(lái)表示物體之間的方向關(guān)系稱為MBR方向關(guān)系。MBR的主方向關(guān)系模型中的兩個(gè)矩形之間有 36種基本方向關(guān)系，表示為： 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]

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

定理1：設(shè)a和b是兩個(gè)物體的MBR，若它們之間的方向關(guān)系是a B b，其對(duì)應(yīng)的矩形代數(shù)關(guān)系為{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主方向關(guān)系的每一個(gè)原子關(guān)系分別對(duì)應(yīng)著一組矩形代數(shù)關(guān)系。由于區(qū)間原子關(guān)系存在端點(diǎn)重合的情況，如果將這些端點(diǎn)重合的情況合并，就可以得到六組區(qū)間代數(shù)的基本關(guān)系，分別是{p，m}、{o，fi}、{di}、{eq，s，f，d }、{oi， si}和{pi，mi}，利用區(qū)間代數(shù)的基本關(guān)系，我們可以得到基于MBR主方向關(guān)系的36種基本關(guān)系的矩形關(guān)系定義。

定理2：基于MBR的基本方向關(guān)系一一對(duì)應(yīng)于區(qū)間基本關(guān)系的笛卡爾積所形成的矩形關(guān)系。

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

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

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

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

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

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

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

定理4：設(shè)R是一個(gè)基本主方向關(guān)系，那么有：

R= MapY（R）×MapX（R）

而MapY（R）和MapX（R）是基本方向關(guān)系中的一種。

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

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

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

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

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

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

定理5可以通過(guò)群舉法證明，證明過(guò)程略。定理5在求解方向關(guān)系矩陣的反關(guān)系和進(jìn)行一致性場(chǎng)景的查找時(shí)都有重要作用。

4 結(jié)論

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

參考文獻(xiàn)：

[1]楊楠，石偉鉑.基于矩陣的MBR主方向關(guān)系的反關(guān)系[J].燕山大學(xué)學(xué)報(bào)，2007（03）.

[2]石偉鉑.基于MBR的主方向關(guān)系推理[D].燕山大學(xué)，2007.

本文系2010年秦皇島市科學(xué)技術(shù)研究與發(fā)展計(jì)劃項(xiàng)目（編號(hào)：201001A013）研究成果