基于元胞自动机的增强现实标记识别算法
增强现实系统 中标记识别一直是增强现实系统的瓶颈，占用了系统处理的大部分时间，即使采用规则几何形式的标记，对于实时要求很高的增强现实系统而言，其识别算法的效果和实时性也是不理想的，因此提出了一种利用应用元胞自动机模型，利用给定的演化规则，改进在增强现实系统中标记识别的算法，并在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系统的很多地面，如坐标系变换、光照处理等，这些还有待进一步的研究。