基于元胞自動機的增強現實標記識別算法

增強現實系統 中標記識別一直是增強現實系統的瓶頸，占用了系統處理的大部分時間，即使采用規則幾何形式的標記，對于實時要求很高的增強現實系統而言，其識別算法的效果和實時性也是不理想的，因此提出了一種利用應用元胞自動機模型，利用給定的演化規則，改進在增強現實系統中標記識別的算法，并在ARTOOLKIT系統中做了具體實現。實驗結果表明，改進的算法的實時性和識別效果均有了很大的提高。

　　0 引? 言

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

　　元胞自動機(cellular automata，CA)是一時間和空間都離散的動力系統。散布在規則格網中的每一元胞(Cel1)取有限的離散狀態，遵循 同樣的作用規則，依據確定的局部規則作同步更新。大量元胞通過簡單的相互作用而構成動態系統的演化。不同于一般的動力學模型，元胞自動機不是由嚴格定義的物理方程或函數確定，而是用一系列模型構造的規則構成。凡是滿足這些規則的模型都可以算作是元胞自動機模型。因此，元胞自動機是一類模型的總稱，或者說是一個方法框架。其特點是時間、空間、狀態都離散，每個變量只取有限多個狀態，且其狀態改變的規則在時間和空間上都是局部的。

　　1 傳統識別算法

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

　　2 采用CA模型的算法

　　CA識別算法如圖2所示，可見算法的效率高低取決于CA模 的設計。本文采用的CA模 犁如下：

　　2．1 元胞空間

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

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

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

　　根據式(1)，c=(0，1，…， )其中開始點為隨機選擇的。實驗證明，隨機選擇的效果比固定選擇，如邊界的情況要好一些。算法采用定值型的邊界。保障演化運算不超過矩形空間。

　　2．2 演化規則

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

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

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

　　(4)內部特征點必須滿足是邊緣點且不是邊點，如下

　　(5)系統結束條件是非常重要的，不然根據現在對 CA的研究，是很容易陷入混沌狀態的 。所以必須設置結束條件，根據應用，結束條件是找到所有頂點并且特征點的數 目滿足特 征識別 的要求 。如下所示：

　　3 實驗結果

　　ARTOOLKIT是一種高效的AR開發平臺。其標記識別采用傳統方法，作者利用這個平臺，改寫了標記識別部分的算法，取得了較好的效果。在同一背景和相同PC及相機的情況下， 比較實驗結果如表 1、表 2，以及圖4、圖5所示。可見采用 CA模型的系統在識別效果很好的情況下實時性有了很大提高。

　　4 結束語

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