王丁杰　周昌樂

摘要： 現(xiàn)有的物體識(shí)別方法大都是有監(jiān)督學(xué)習(xí)，而且主要處理的是2D圖像數(shù)據(jù)， 由于這類數(shù)據(jù)給出的背景信息和物體信息少于2.5D場(chǎng)景中的信息，傳統(tǒng)有監(jiān)督的學(xué)習(xí)方法對(duì)于非特定物體的識(shí)別效果還是不盡如人意，更別說基于無監(jiān)督學(xué)習(xí)的識(shí)別系統(tǒng)了。隨著Kinect設(shè)別的出現(xiàn)，獲取場(chǎng)景的2.5D信息變得很容易。設(shè)計(jì)了一個(gè)全新的基于無監(jiān)督物體識(shí)別系統(tǒng)。首先用平面擬合和空間聚合把物體從場(chǎng)景中分離以后。 然后用幾何基元擬合分割技術(shù)把物體分割為不同部件，在此基礎(chǔ)上構(gòu)建物體的圖模型， 最后把圖模型嵌入為向量空間上的點(diǎn)集合，使用擴(kuò)展陸地移動(dòng)距離算法計(jì)算物體間的相似度。從實(shí)驗(yàn)結(jié)果來看效果不錯(cuò)。

關(guān)鍵詞： 2.5D； 物體識(shí)別； kinect； 無監(jiān)督； 幾何基元擬合； 擴(kuò)展陸地移動(dòng)距離

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）09-2219-04

物體識(shí)別一直是機(jī)器人學(xué)科，計(jì)算機(jī)視覺和人機(jī)交互領(lǐng)域里的一個(gè)基礎(chǔ)性工作。物體識(shí)別按表示方式主要可以分成兩大類：基于部件模型的物體識(shí)別[3-4] 和基于外觀的物體識(shí)別 [5-6] 。從2007年開始，基于部件模型的物體識(shí)別技術(shù)日趨主流。

盡管基于部件模型的物體識(shí)別系統(tǒng)取得了很大的成功，但是絕大多數(shù)部件模型都有兩個(gè)前提： 一是的模型結(jié)構(gòu)特征是事先指定的；二是訓(xùn)練樣本中需要對(duì)物體的位置做出標(biāo)記，并且告知物體的類型。雖然這種有監(jiān)督的學(xué)習(xí)方式也是人類認(rèn)知世界的一個(gè)過程，但是人類同樣也可通過無監(jiān)督學(xué)習(xí)的方式來認(rèn)知這個(gè)世界。

隨著2010年Kinect出現(xiàn)，獲取場(chǎng)景的深度信息成為可能，物體和場(chǎng)景的分離變得更加容易。新技術(shù)的出現(xiàn)，給物體識(shí)別技術(shù)帶來新的方法和視角。我們?cè)O(shè)計(jì)的物體識(shí)別系統(tǒng)就基于場(chǎng)景的2.5D信息。

我們?cè)O(shè)計(jì)了一個(gè)全新的無監(jiān)督，增量式物體識(shí)別框架，利用場(chǎng)景中的點(diǎn)云信息來識(shí)別物體。它可被用于機(jī)器人中，用于探索未知的環(huán)境，模仿人類認(rèn)識(shí)現(xiàn)實(shí)環(huán)境。

我們把場(chǎng)景中物體分為支撐體和被支撐體，比如桌面和桌面上的物體。主要步驟包括以下幾個(gè)：

1）物體提取。首先我們用RANSAC提取場(chǎng)景平面，刪除場(chǎng)景平面中的支持平面，再用空間歐式距離聚類的方法，分割中出被支撐物體。

2）對(duì)每個(gè)被支撐物體用基于基元（ 三維球體，圓柱體，平面）的多層次分割方法建立物體模型。

3）利用前面的分割結(jié)果構(gòu)建物體的圖模型 [2] 。

4）用度量多維標(biāo)度法把該圖模型轉(zhuǎn)化到二維向量空間中，獲取每個(gè)物體的向量模型。

5）用擴(kuò)展陸地移動(dòng)距離算法估計(jì)物體的向量模型間的距離，以此作為物體間的相識(shí)度。

1 物體提取

我們可以利用深度信息來把物體分成支撐體如桌面和掛著很多畫的墻壁， 被支撐體比如桌面上得物體和墻上的畫。

我們用Kinect攝像頭獲取數(shù)據(jù)，并通過OpenNI接口得到數(shù)據(jù)的點(diǎn)云信息。然后用隨機(jī)樣本一致性算法從場(chǎng)景中提取所有的平面，對(duì)任意平面，用空洞的數(shù)量（因被支撐物和平面的分離產(chǎn)生）來判定該平面是否是支撐面。

在支撐物被抽取后，會(huì)造成被支撐物在空間上的分離。這時(shí)我們可以用基于空間歐式距離的聚類方法，把和支撐面連接的每個(gè)物體提取出來，為進(jìn)一步的處理做準(zhǔn)備。圖2中綠色部分為支撐平面，紅色部分為提取到的在空間上分離的物體。

2 物體模型構(gòu)建

2.1 物體分割

基于部件的物體結(jié)構(gòu)分解和人類看待物體的方式有很多共同之處。我們采用的分割方法基于Marco的層次幾何基元擬合分割，分別用了三種基元：平面，球體，圓柱體。我們通過設(shè)置最終的分割部件的數(shù)目[β]來控制分割結(jié)果。

2.2 圖模型構(gòu)建

對(duì)于任意的物體[x]，我們先用一個(gè)無向圖來描述一個(gè)物體。[x]首先被逐層的分割成不同的部件。然后用[2]中的圖結(jié)構(gòu)來記錄模型的拓?fù)浣Y(jié)構(gòu)和幾何特征。圖中的邊表示部件間的父子關(guān)系或則兄弟關(guān)系。和節(jié)點(diǎn)相關(guān)的屬性包括：該點(diǎn)和父節(jié)點(diǎn)的相對(duì)距離和方向，該節(jié)點(diǎn)的幾何形狀信息如外形類別，大小比例等。

由EMD的距離公式可知，權(quán)重接近的點(diǎn)之間如果相對(duì)距離越小，計(jì)算出來的EMD距離就越小。由于擴(kuò)展EMD只對(duì)點(diǎn)集進(jìn)行整體的移動(dòng)，不會(huì)改變點(diǎn)集內(nèi)部的相對(duì)位置。為了保證來自不同點(diǎn)集的權(quán)重相似的點(diǎn)盡可能的對(duì)齊， 要求圖模型到點(diǎn)集的嵌入過程要產(chǎn)生穩(wěn)定的相對(duì)位置。否則EMD計(jì)算出來的距離不能穩(wěn)定和真實(shí)的反映物體間的相似度。考慮如下兩個(gè)圖結(jié)構(gòu)：

當(dāng)它們被轉(zhuǎn)化到向量空間后，一個(gè)好的對(duì)齊會(huì)是[R-r，A-a，B-b，C-c，D-d]。如果我們?cè)O(shè)置上述圖中的邊權(quán)重為常數(shù)1 ，那么在上述圖在映射到向量空間后，可能有錯(cuò)位對(duì)齊。證明：假設(shè)圖模型（b），映射到向量空間中的點(diǎn)集[V]，點(diǎn)集的數(shù)量[|V|=n+1]， 對(duì)于特定點(diǎn)集中的某個(gè)點(diǎn)[x]，它的相對(duì)距離向量[dx=（dxy1，...，dxyn）] 中的每個(gè)元素表示該點(diǎn)到集合[V]上其它點(diǎn)[yi]的距離，其中[1≤i≤n]。 如果存在某個(gè)點(diǎn)[z]，它的相對(duì)距離向量為[dz=（dzy1，...，dzyn）]，且[dxyk=dzuk，（1≤k≤n）]。那么[dx=dz]，意味著這兩個(gè)點(diǎn)在向量空間中的位置是可交換的，這是由圖嵌入（見4.1）過程決定的。所以對(duì)齊的時(shí)候就可能出現(xiàn)[B-c，C-b]。因?yàn)閇c]和[b]在向量空間中的相對(duì)距離向量相同。而這顯然不是最佳的對(duì)齊方式。為了保證點(diǎn)集內(nèi)部點(diǎn)間相對(duì)位置的更加穩(wěn)定，對(duì)于圖模型中的任意父節(jié)點(diǎn)[p]，我們讓父子邊（部件的層次分割）的權(quán)重由1開始隨子節(jié)點(diǎn)重量（其屬性和基點(diǎn)屬性的距離）的遞增方向遞增，增量為1。兄弟邊（部件間的相鄰關(guān)系）的權(quán)重為常量1。此外我們保證兄弟節(jié)點(diǎn)的重量不同。這樣避免了同一個(gè)圖中存在兩個(gè)不同節(jié)點(diǎn)在嵌入到向量空間時(shí)由于位置可交換導(dǎo)致內(nèi)部結(jié)構(gòu)不穩(wěn)定，從而可能發(fā)生錯(cuò)位對(duì)齊。

3 圖嵌入和匹配

3.1 圖嵌入到向量空間

圖嵌入是一種圖匹配的有效手段。它能把圖信息轉(zhuǎn)化成向量空間上的點(diǎn)集合，其中每個(gè)點(diǎn)對(duì)應(yīng)于圖中的一個(gè)節(jié)點(diǎn)，點(diǎn)之間的歐式距離對(duì)應(yīng)于圖中相應(yīng)圖節(jié)點(diǎn)間的距離，這里我們用最短路徑表示圖節(jié)點(diǎn)間的距離。考慮一個(gè)物體的圖模型[G]有節(jié)點(diǎn)集[{vij|i≤j≤n}]， 那么它的差異矩陣為[{Dij=short_path（vi，vj）|1≤i，j≤n}]。我們用Johnsom算法來計(jì)算節(jié)點(diǎn)對(duì)間的最短距離，其時(shí)間復(fù)雜度為[O（2VlogV+VE）]。接著我們用度量多維標(biāo)度法來把圖嵌入到一個(gè)二維的向量空間中。對(duì)于任意兩個(gè)圖節(jié)點(diǎn)[vi]和[vj]間的最短路徑[dij]， 其在向量空間中的對(duì)應(yīng)節(jié)點(diǎn)間的歐式距離為[f（δij）]，度量多維標(biāo)度法保證[Fs]最小。

3.2 點(diǎn)集匹配

當(dāng)圖被嵌入到一個(gè)向量空間以后，圖匹配問題就轉(zhuǎn)化為向量空間中點(diǎn)集合的匹配問題。

陸地移動(dòng)距離（EMD） 源于運(yùn)輸問題，在圖像處理中被廣泛的用于解決這類帶有權(quán)重的點(diǎn)集合間的匹配問題。 兩個(gè)點(diǎn)集間的移動(dòng)距離越小，表示它們之間越相似。假設(shè)[P={（p1，wp1），...，（pm，wpm）}]為供應(yīng)者，接收者[Q={（q1，wq1），...，（qn，wqn）}]，其中[m>n]。[pi]和[qi]表示點(diǎn)在向量空間中的坐標(biāo)，[wpi]和[wqi]表示點(diǎn)的重量，這里我們用該點(diǎn)特征向量和基點(diǎn)向量的距離來表示，我們用根節(jié)點(diǎn)對(duì)應(yīng)的特征向量最為基點(diǎn)向量。[D=[dij]]為距離矩陣，[dij]表示[pi]到[qj]的距離。我們要找出流[F=[fij]]，使運(yùn)輸總代價(jià)[EMD（P，Q）]最小。這里[fij]表示[pi]到[qj]的流量。

距離公式為：

1）表示只能由供應(yīng)者流向消費(fèi)者。2）表示[pi]的流出量不能超過該點(diǎn)的重量。3）[qj]的接受量不能超過其容量限制。4）總的流量為兩堆土中的最小值。

前面描述的EMD要求兩個(gè)向量集合在空間上對(duì)齊。為了解決這個(gè)問題Cohen 和Guibas [11] 擴(kuò)展了EMD算法，動(dòng)態(tài)的在匹配的過程中對(duì)點(diǎn)集進(jìn)行整體移動(dòng)調(diào)整，從而找出最佳的匹配結(jié)果，我們稱此為擴(kuò)展EMD算法。Cohen和Guibas用迭代的方式計(jì)算陸地移動(dòng)距離的最小值。首先從一個(gè)最初的位置開始，擴(kuò)展EMD計(jì)算最優(yōu)的流向[Fk]，在此流向的前提下計(jì)算一個(gè)更優(yōu)化的空間坐標(biāo)轉(zhuǎn)化矩陣[Gk]，應(yīng)用此轉(zhuǎn)化于其中一個(gè)點(diǎn)集，使其整體發(fā)生移動(dòng)或旋轉(zhuǎn)，進(jìn)而使EMD距離減小。在[Gk]的前提下，計(jì)算出最優(yōu)的[Fk+1]，如此迭代，直到EMD值達(dá)到穩(wěn)定值。圖5是玩具獅子和老虎在向量空間中的擴(kuò)展EMD匹配結(jié)果，我們可以看到兩個(gè)點(diǎn)集在空間位置上有比較好的對(duì)齊結(jié)果，在此基礎(chǔ)上計(jì)算出來的陸地移動(dòng)距離能更好的體現(xiàn)兩個(gè)點(diǎn)集間的距離，即圖像間的相似度。

5 實(shí)驗(yàn)結(jié)果

我們采集了每個(gè)物體20個(gè)視角的2.5D照片。設(shè)置分割結(jié)果部件參數(shù)[β=6]?？紤]兩個(gè)物體A和B間的距離，對(duì)于A的任何一個(gè)視角的2.5D照片，計(jì)算出它與B的所有視角照片間的距離，其中最小的那個(gè)為A到B的單視角最小距離。A和B所有視角最小距離的和，以灰度度量的形式表示為圖6灰度表中的格子。圖6中任意一個(gè)格子對(duì)應(yīng)于物體間的所有視角最小距離和?；叶仍缴畹母褡颖硎緦?duì)應(yīng)的兩個(gè)物體越相似，白色的相反。為了了解物體視角對(duì)識(shí)別的影響，我們選擇獅子奧特曼和獅子分別在在[0?，30?，60?]度視角下的2.5D照片，來比較它們間相似度。由圖7可看出，同類物體間視角差別越小，相似度越高。非同類物體間的視角差別對(duì)識(shí)別的影響比較不穩(wěn)定，這可能是因?yàn)閺腒inect獲取的數(shù)據(jù)有誤差，不能準(zhǔn)確反映物體的幾何模型數(shù)據(jù)。

6 結(jié)論

當(dāng)今2D圖像識(shí)別技術(shù)的識(shí)別率不高的很大一個(gè)原因是2D圖片無法提供足夠的背景和前景的信息。我們借助從Kinect獲取的2.5D信息，設(shè)計(jì)了一個(gè)全新的無監(jiān)督圖像識(shí)別系統(tǒng)，該系統(tǒng)利用深度信息提取場(chǎng)景中的前景物體，然后再計(jì)算物體間的相似度。這樣避免了背景信息對(duì)前景物體識(shí)別的干擾，有效的提高了識(shí)別率。該系統(tǒng)的缺點(diǎn)是假設(shè)所有的物體在空間上是分離的，這樣如果有兩個(gè)物體是相挨的，那么會(huì)被當(dāng)做一個(gè)物體處理。從理論上說，無論是我們采用的圖模型還是擴(kuò)展EMD都有部分匹配的特性，對(duì)于物體的縮放，旋轉(zhuǎn)也有一定的魯棒性。如果部分匹配能取得好的效果，那么可以在一定程度上解決前面所述的不足。我們將在接下來的工作中探索Kinect的數(shù)據(jù)誤差對(duì)魯棒性和部分匹配的影響。

參考文獻(xiàn)：

[1] Shokoufandeh A， Dickinson S， J?nsson C， et al. On the representation and matching of qualitative shape at multiple scales[J]. Computer Vision—ECCV 2002， 2002： 6-14.

[2] Dickinson S J， Pentland A P， Rosenfeld A. From volumes to views： An approach to 3-D object recognition[J]. CVGIP： Image Understanding， 1992， 55（2）： 130-154.

[3] Felzenszwalb P F， Girshick R B， McAllester D， et al. Object detection with discriminatively trained part-based models[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2010， 32（9）： 1627-1645.

[4] Leonardis A， Bischof H. Dealing with occlusions in the eigenspace approach[C]//Computer Vision and Pattern Recognition， 1996. Proceedings CVPR'96， 1996 IEEE Computer Society Conference on. IEEE， 1996： 453-458.

[5] Turk M， Pentland A. Eigenfaces for recognition[J]. Journal of cognitive neuroscience， 1991， 3（1）： 71-86.

[6] Attene M， Falcidieno B， Spagnuolo M. Hierarchical mesh segmentation based on fitting primitives[J]. The Visual Computer， 2006， 22（3）： 181-193.

[7] Demirci M F， Shokoufandeh A， Keselman Y， et al. Object recognition as many-to-many feature matching[J]. International Journal of Computer Vision， 2006， 69（2）： 203-222.

[8] Cox M， Cox T.Multidimensional Scaling[M].Chapman and Hall， London，1994.

[9] Rubner Y， Tomasi C， Guibas L J. A metric for distributions with applications to image databases[C]//Computer Vision， 1998. Sixth International Conference on. IEEE， 1998： 59-66.

[10] Rubner Y， Tomasi C， Guibas L J. The earth mover's distance as a metric for image retrieval[J]. International Journal of Computer Vision， 2000， 40（2）： 99-121.

[11] Cohen S， Guibasm L. The earth mover's distance under transformation sets[C]//Computer Vision， 1999. The Proceedings of the Seventh IEEE International Conference on. IEEE， 1999， 2： 1076-1083.

[12] Fischler M A， Bolles R C. Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM， 1981， 24（6）： 381-395.