基于元胞自動(dòng)機(jī)的增強(qiáng)現(xiàn)實(shí)標(biāo)記識(shí)別算法

增強(qiáng)現(xiàn)實(shí)系統(tǒng) 中標(biāo)記識(shí)別一直是增強(qiáng)現(xiàn)實(shí)系統(tǒng)的瓶頸，占用了系統(tǒng)處理的大部分時(shí)間，即使采用規(guī)則幾何形式的標(biāo)記，對(duì)于實(shí)時(shí)要求很高的增強(qiáng)現(xiàn)實(shí)系統(tǒng)而言，其識(shí)別算法的效果和實(shí)時(shí)性也是不理想的，因此提出了一種利用應(yīng)用元胞自動(dòng)機(jī)模型，利用給定的演化規(guī)則，改進(jìn)在增強(qiáng)現(xiàn)實(shí)系統(tǒng)中標(biāo)記識(shí)別的算法，并在ARTOOLKIT系統(tǒng)中做了具體實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法的實(shí)時(shí)性和識(shí)別效果均有了很大的提高。

　　0 引? 言

　　增強(qiáng)現(xiàn)實(shí)技術(shù)(augmentedreality，AR)，是隨著虛擬現(xiàn)實(shí)技術(shù)(virtual reality，VR)迅速發(fā)展和實(shí)際應(yīng)用需要而出現(xiàn)的一種將真實(shí)世界信息和虛擬世界信息“無(wú)縫”集成的新技術(shù)。增強(qiáng)現(xiàn)實(shí)系統(tǒng)是使用了增強(qiáng)現(xiàn)實(shí)技術(shù)的應(yīng)用系統(tǒng)。其重要特點(diǎn)的有：用戶(hù)擁有沉浸感，虛擬環(huán)境與實(shí)際環(huán)境融為一體，幾乎感覺(jué)不到真假融合所產(chǎn)生的不和諧；系統(tǒng)具有交互性，用戶(hù)可以通過(guò)交互設(shè)備直接與虛擬物體或虛擬環(huán)境進(jìn)行交互：是在三維空間中增添定位虛擬物體，它的研究涉及系統(tǒng)結(jié)構(gòu)、人機(jī)接口、三維注冊(cè)、頭盔顯示等方面。利用標(biāo)記實(shí)現(xiàn)虛擬物體的精確注冊(cè)已經(jīng)是一種較成熟的技術(shù)了，并在室內(nèi)、室外到移動(dòng)應(yīng)用等環(huán)境都得到了廣范應(yīng)用。其中標(biāo)記識(shí)別一直是增強(qiáng)現(xiàn)實(shí)系統(tǒng)的瓶頸，占用了系統(tǒng)處理的大部分時(shí)間，即使采用規(guī)則幾何形式的標(biāo)記，對(duì)于實(shí)時(shí)要求很高的增強(qiáng)現(xiàn)實(shí)系統(tǒng)而言其識(shí)別算法的結(jié)果和 實(shí)時(shí)性也 是不理想的。

　　元胞自動(dòng)機(jī)(cellular automata，CA)是一時(shí)間和空間都離散的動(dòng)力系統(tǒng)。散布在規(guī)則格網(wǎng)中的每一元胞(Cel1)取有限的離散狀態(tài)，遵循 同樣的作用規(guī)則，依據(jù)確定的局部規(guī)則作同步更新。大量元胞通過(guò)簡(jiǎn)單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演化。不同于一般的動(dòng)力學(xué)模型，元胞自動(dòng)機(jī)不是由嚴(yán)格定義的物理方程或函數(shù)確定，而是用一系列模型構(gòu)造的規(guī)則構(gòu)成。凡是滿(mǎn)足這些規(guī)則的模型都可以算作是元胞自動(dòng)機(jī)模型。因此，元胞自動(dòng)機(jī)是一類(lèi)模型的總稱(chēng)，或者說(shuō)是一個(gè)方法框架。其特點(diǎn)是時(shí)間、空間、狀態(tài)都離散，每個(gè)變量只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的。

　　1 傳統(tǒng)識(shí)別算法

　　視覺(jué)標(biāo)記的識(shí)別過(guò)程包括輸入圖像、輸出圖像標(biāo)記的包圍框和特征點(diǎn)的坐標(biāo)。這個(gè)過(guò)程的設(shè)計(jì)要求是具有較好的精度，滿(mǎn)足實(shí)時(shí)性要求，其中實(shí)時(shí)性要比精度更重要一些。標(biāo)記的識(shí)別中，一般可以利用的信息是標(biāo)記的邊緣信息、幾何信息、色度信息? 。如圖 1所示。首先將圖像轉(zhuǎn)化為二值圖像，然后利用 腐蝕 、邊框提取和 Hough變換等 技術(shù)獲得標(biāo)志包圍，再經(jīng)過(guò)種子填充和幾何限制等手段取得特征點(diǎn)集合。

　　2 采用CA模型的算法

　　CA識(shí)別算法如圖2所示，可見(jiàn)算法的效率高低取決于CA模 的設(shè)計(jì)。本文采用的CA模 犁如下：

　　2．1 元胞空間

　　假設(shè)元胞空間由二維 M*N個(gè)像素構(gòu)成。并假設(shè)是時(shí)間同步的。定義一幅M~N大小的二維圖像

式中：M,N分別表示圖像的高和寬。Aid')表示(? 點(diǎn)的狀態(tài)值(也即灰度值)。對(duì)于k值圖像，(? 在狀態(tài)集取值。含有標(biāo)記的視頻圖像如圖3所示。

　　鄰居模式采用摩爾型。每個(gè)元胞構(gòu)成如下：每個(gè)元胞由4個(gè)分量構(gòu)成：GCell(c,p，e，v)，其中C表示灰度，為簡(jiǎn)單起見(jiàn)，先利用閥值進(jìn)行了二值化，得到 0或 1。要注意在其過(guò)程中消除孤立點(diǎn) ，不然會(huì)影 響識(shí)別效果 。P表示是 否是邊緣點(diǎn)，如 是邊緣點(diǎn)則為 1，否則為 0。e表示是否是邊 ，如是則為 1，否 則為0。v表示是否 為頂點(diǎn) ，如是 則為 1，否 則為 0；i表示是否 為標(biāo)記內(nèi)部特征點(diǎn)，如是則為 1，否則為0。采用二值表示，簡(jiǎn)化了操作。系統(tǒng)初始矩陣如下

　　根據(jù)式(1)，c=(0，1，…， )其中開(kāi)始點(diǎn)為隨機(jī)選擇的。實(shí)驗(yàn)證明，隨機(jī)選擇的效果比固定選擇，如邊界的情況要好一些。算法采用定值型的邊界。保障演化運(yùn)算不超過(guò)矩形空間。

　　2．2 演化規(guī)則

　　(1)先判斷是否是邊緣點(diǎn)。由邊緣定義可知，如果某一點(diǎn)狀態(tài)與其近鄰點(diǎn)中大部分點(diǎn) 的狀態(tài)相異 ，就是梯度變 化明顯，那這個(gè)點(diǎn)就可以認(rèn)為是邊緣點(diǎn)，否則就認(rèn)為是背景點(diǎn)，也就是非邊緣點(diǎn)。基于此理論，按如下規(guī)則來(lái)判斷邊緣點(diǎn)位置。

　　(2)判斷是否是邊? 的點(diǎn)，可 以有兩種判 斷方 法，從 圖 1可知，標(biāo)記是由一個(gè)固定寬度的正方形構(gòu)成的。設(shè)標(biāo)記的寬度為d，黑色標(biāo)記帶的寬度為n，則可用如下的規(guī)則判斷是否是正方形邊上 的點(diǎn)。即必須是邊緣點(diǎn)并且滿(mǎn)足連續(xù) x或 Y方向上n個(gè)都是邊緣點(diǎn)。或者滿(mǎn)足連續(xù) x或 Y方向上 d個(gè)都是同等灰度的。如 式(4)和(5)表示

(3)判斷是否是頂點(diǎn)，如是頂點(diǎn)必須滿(mǎn)足是邊上的點(diǎn)并且滿(mǎn)足連續(xù) x或 Y方向上n個(gè)都是 同等灰度的。如式(6)所示

　　(4)內(nèi)部特征點(diǎn)必須滿(mǎn)足是邊緣點(diǎn)且不是邊點(diǎn)，如下

　　(5)系統(tǒng)結(jié)束條件是非常重要的，不然根據(jù)現(xiàn)在對(duì) CA的研究，是很容易陷入混沌狀態(tài)的 。所以必須設(shè)置結(jié)束條件，根據(jù)應(yīng)用，結(jié)束條件是找到所有頂點(diǎn)并且特征點(diǎn)的數(shù) 目滿(mǎn)足特 征識(shí)別 的要求 。如下所示：

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

　　ARTOOLKIT是一種高效的AR開(kāi)發(fā)平臺(tái)。其標(biāo)記識(shí)別采用傳統(tǒng)方法，作者利用這個(gè)平臺(tái)，改寫(xiě)了標(biāo)記識(shí)別部分的算法，取得了較好的效果。在同一背景和相同PC及相機(jī)的情況下， 比較實(shí)驗(yàn)結(jié)果如表 1、表 2，以及圖4、圖5所示。可見(jiàn)采用 CA模型的系統(tǒng)在識(shí)別效果很好的情況下實(shí)時(shí)性有了很大提高。

　　4 結(jié)束語(yǔ)

　　CA方法由于采用了二值運(yùn)算，并且演化步驟有限，因此算法的效率是很高的，能夠較好的滿(mǎn)足AR系統(tǒng)實(shí)時(shí)處理的要求，可預(yù)留更多的時(shí)間給渲染程序。當(dāng)然，由于 CA在AR中的應(yīng)用才剛剛起步，CA算法應(yīng)該還可以應(yīng)用在AR系統(tǒng)的很多地面，如坐標(biāo)系變換、光照處理等，這些還有待進(jìn)一步的研究。