基于OBB包围盒的图形检测算法

张 敏，郑 哲，林君强

(1.福建信息职业技术学院建筑工程系，福建 福州 350003;2.福建省地质测绘院，福建 福州 350011)

众多学者在基础地理信息数据领域中对图形检测的方法进行了大量研究，车秋锋对4D产品的检测进行综合性功能设计[1]，蔡建德、何鑫星等人设计图形精度检查系统[2-3]，伍素贞等人基于AutoCAD和RTK进行数学精度检测[4]。这些图形检测方法中更多关注的是数学信息，而忽略对象的图形特征和属性问题，必须人工逐一查看图形的绘制方法、图形的表达、图形的属性是否正确。这种人工检测的方式能够保证检测的准确性，但是检测效率较低。包围盒是一种求解离散点集最优包围空间的算法，较多地用于图形的碰撞检测中，利用体积略大而几何特性简单的包围盒近似地描述相对复杂的虚拟对象，以剔除大量不可能产生碰撞的物体对象[5-7]。因此本文基于包围盒的思路，在图形对象特性的基础上探索一种既能保证检测的准确性又能保证检测效率的图形快速检索算法。

1 图形对象的特殊性

在基础地理信息领域，图形对象主要划分为8大类，依据地物的大小或长宽是否跟随比例尺的变化而变化的特征，本文将图形检索的对象类别划分为：不依比例尺对象、半依比例尺对象、依比例尺对象。每一个图形对象都由多个图形要素组合而成，不依比例尺图形对象内部封装成点状，一般以块的形式存在；半依比例尺图形对象内部封装成线状；依比例尺图形对象内部封装成面状。从数据类别来看，所有类别的图形对象的特征一般包含几何特征和属性特征，几何特征侧重从数学方面进行描述，属性特征侧重用文字表述型数据进行描述，除了几何特征和属性特征以外，还应该要关注图形对象本身存在的特殊的图形特征。因此在进行图形检测时按照不同对象类别进行检测，每个图形对象遍历其图形要素组成，而在检测过程中同时注意不同类别图形对象的特殊性(表1)，主要集中在图形对象的旋转性、指向性、封闭性，其中部分不依比例尺图形对象具有旋转特征；半依比例尺图形对象中的复合图形不同的绘制顺序具有不同的指向性；依比例尺图形对象是首尾相连的线，在图形检测时应考虑图形对象的封闭性。

表1 图形对象的特殊性

2 图形检测的方法

2.1 图形检测包围盒

传统的图形检测是采用统一的网格划分或者定义固定大小的盒子进行算法实现，这种算法实现简单、可操作性强，但没有考虑图形对象的完整性，极易造成图形对象的分割或不完整，并且因无法评估图形对象的大小，网格尺寸和盒子大小一般设计较大，图形检测的搜索范围也就较大。为了保证图形对象的完整性和检测效率，需要定义一个合适大小的物体来包裹图形对象。包围盒的基本思想就是利用某种形状简单的几何体来紧密包裹对象物体[8-14]。几何体常常是球体或长方体，因此本文借鉴包围盒的思路来探究图形检测的方法，由于基础地理信息领域的研究对象是二维平面图形，本文采用圆形、矩形包围盒(图1)，其中矩形包围盒分为轴对齐包围盒(axially aligned bounding box,AABB)[15-16]和有向包围盒((oriented bounding box, OBB)[17-21]。

图1 包围盒类别

从图1中可以看出，圆形包围盒和AABB包围盒有较大的空间缝隙，造成空间冗余，为了有效地利用内存空间，并考虑到对象的图形特征，本文确定基于OBB包围盒进行图形检测。

2.2 OBB包围盒理论

Ci,j=Cov(xi,yj)=E[(xi-ui)(yi-uj)]i,j=1,2,…,n

(1)

(2)

之后将坐标点投影到方向向量上，找到x、y分量在每个方向上的最大值和最小值，记为vkmin、vkmax，k=0,1，由式(3)可得包围盒的中心，由式(4)可得包围盒半长。

(3)

(4)

以上方法得到的是图形对象的最小OBB包围盒，由于检测图形和被检测图形之间允许存在一定的误差，本文设置误差参数为m(单位：m)，将生成的最小OBB包围盒沿着轴方向向外扩展m距离，进而得到图形检测的包围盒范围(图2)，图2中虚线为生成的最小包围盒范围，实线为扩展m距离后的包围盒范围，扩展后的范围即为图形检测的搜索范围。

图2 扩展m距离后的包围盒范围

2.3 图形检测方法

2.3.1 同名点匹配检测

同名点匹配即基于相同的坐标和属性进行匹配。以房屋为例(图3)，按照2.2讲述的方法建立图形检测范围，由于在建立图形检测范围时已经提取了图形对象的坐标序列(x1,y1),(x2,y2),...,(x8,y8)和属性信息，则进入被检测图幅时将鼠标指针逐点定位到相应的坐标位置上，在范围内搜索离原坐标点最近、属性一致的图形对象。该方法适合所有图形对象的检测，尤其是常规的图形对象。

图3 房屋

依比例尺图形对象检测时须提取Closed值，值为1代表图形封闭，值为0代表图形不封闭。

不依比例尺图形对象的基点位置有中心和非中心的区别。在进行图形检测时鼠标指针直接定位到该对象的基点位置(对于基点在中心的则直接定位到包围盒中心)，搜索距离基点最近、属性一致、angle值(旋转角，误差允许范围假设为5°)一致的图形对象，angle值根据包围盒的2个主方向得到。

2.3.2 以绘点顺序为准的检测

主要针对半依比例尺图形对象中的复合图形，该类复合图形对象通过绘点顺序和坐标判断图形的绘制方向和开角方向。以围墙为例，如图4(a)所示，在图形检测范围内首先按照顺序提取架构线坐标(x1,y1),(x2,y2)，依据绘点顺序和坐标判定绘制方向，此时计算围墙边线的坐标和架构线坐标的差值，大于0则围墙边线沿着方向生成在架构线的左边，小于0则围墙边线沿着方向生成在架构线的右边，这种规则我们称之为“左+右-”，以此来判定此类图形对象的指向性。

对于开角方向验证，图4(b)为无开角短线的悬空通廊，按照绘点顺序，1—2点连线为对象边线，开角在2—3点间，不同绘点顺序，开角方向不同，上图表示指向南北为通行方向，下图表示指向东西为通行方向；图4(c)为无开角短线的台阶类，开角在起-闭点间，开角方向与绘点顺序无关，只与起、闭点的位置有关；图4(d)为有开角短线的复合图形对象比如人行桥，按照绘点顺序，1—2点连线为对象边线，开角在2—3点间，开角指向含义与悬空通廊相同，但开角短线方向略有不同，左图为正确开角的人行桥，右图为错误开角的人行桥，正确开角的绘点顺序应是按照顺时针方向进行。因此在此类图形对象检测时，读取每个对象的绘点顺序、坐标确定对象边线、开角方向、开角短线方向。

图4 不同绘点顺序生成的图形

3 图形检测算法

3.1 图形检测算法实现

1)所有的检测对象按照对象类别创建对象列表Objcetlist[j]和属性列表Attributelist[j]，其中j=0表示是不依比例尺对象列表，j=1表示是半依比例尺对象列表，j=2表示是依比例尺对象列表。每个检测对象均按照绘点顺序号提取坐标序列(xi,yi)。以下以某一个检测对象为例进行说明。

4)协方差矩阵对角化，由CP=λP求解C的特征值λ以及对应特征值λ的特征向量P，满足PCPT=λ，λ为对角矩阵。取最大特征值对应的特征向量作为OBB包围盒的方向，该特征向量就是OBB包围盒的坐标轴，假设为M。

7)进入被检图幅开始检测，首先定位到该检测对象的图形检测范围内进行检索，判断哪些图形对象落在包围盒内，落在包围盒内的图形对象均将被检索并分别创建检测列表Checklist[j]，保存其坐标集合；根据提取的图形对象属性信息Attributelist[j]确定进一步可能的图形对象集合Object_Checklist[j]。之后根据检测对象的坐标序列按照同名点匹配的方法逐点进行坐标匹配，此时离检测对象坐标点最近、属性一致的图形将被检索到。特别地，j=0的，搜索距离基点最近、属性一致、angle在符合范围内的图形对象；j=1的，根据绘点顺序和坐标判断图形的生成方向或开角方向；j=2的，提取closed是否为1。

3.2 算法改进

3.1小节中通过检测对象的属性信息来确定被检测的图形对象是否符合检测条件，但图形对象存在多语义问题，如图5所示，以台阶为例，该图形对象在实际中既可以表示台阶，也可以表示室外楼梯，若有边亦可表示成有边台阶；对于不规则的台阶，图形对象可表示成台阶、室外楼梯或不规则楼梯，此时同一对象有不同的表示方法，也就有了不同的属性信息，造成图形对象的多语义问题。显然按照检测图形对象的属性信息进行图形检测，必然造成匹配结果不完整，可能丢失部分图形对象。因此对上述图形检测算法进行改进，事先创建属性匹配文件，在进入被检图幅时，预先读取属性匹配文件，在进行图形检索时遍历该文件，以便更为完善地进行图形检测。属性匹配文件格式如下：

图5 图形对象的多语义

143301=143400,143302,143410

……

end

4 实验结果

实验环境：Microsoft Windows 7 操作系统，Intel(R) Core(TM)i5-3230 CPU @2.60 GHz处理器，NVIDIA GeForce 610 M显卡，4.00 GB内存，1 366×768屏幕分辨率。

实验情况：在检索图幅中确定10个检索的图形对象对100个图幅进行检索，因篇幅有限，图6中仅列出其中一个图形对象的检索情况，为了图形显示更直观在±m误差位置各生成一条控制边界，实线是+m误差的控制线，虚线是-m误差的控制线。从检索情况来看，情形1检索出的图形对象在[-m,+m]控制范围内，情形2检索出的图形对象其中一个角点超出+m的范围，情形3检索出的图形对象超出+m的范围，情形4检索出的图形对象超出-m的范围。

图6 图形检索情况

4.1 检测时间分析

应用Matlab对算法的执行效率进行测试，System函数直接调用程序执行，利用tic、toc组合函数计算每一次程序循环执行的时间，统计每一幅图的检测时间绘制时间离散点图。图7(a)的时间离散点图中平均每一幅图的检测时间为9.746 s，图7(b)的残差图中可看出基本上时间残差控制在[-5 s,+5 s]，但是存在几个异常点，其主要原因在于图形检测时未匹配到相关图形对象，导致程序在遍历属性匹配文件，直到遍历结束为止，但每一幅图的检测时间基本控制在20 s以内[22]。

图7 时间点图

4.2 检测结果的准确性分析

采用人工检测的方式，在排除人为因素(如人为错误采集检测图形对象的标准点、检测点数据等)的前提下，人工检测能保证100%的准确率；而基于动态包围盒的图形检测算法进行图形检测的准确率如图8所示，基本上图形检测的准确率能达到70%以上，最高达到100%，也存在部分图形检测准确率较低，最低为20%，其原因在于图形存在多语义问题，容易造成计算机误判，因此应事先编辑属性匹配文件，若编码文件较为全面、完善，可确保检测结果的准确性。

图8 图形检测的准确率统计

5 结论

从实验结果来看，使用基于动态包围盒的图形检索算法进行图形检测能大大提高图形检测的效率，但是初始使用该算法，由于图形属性匹配文件考虑不足，图形检测结果的准确性尚不如人意，对于计算机误判的图形需要人工进行纠错，因此初始使用建议“算法+人工”的方式既保证了图形检测的效率又保证了图形检测的准确性，不过随着图形属性匹配文件的不断完善，该算法的图形检测结果会越来越可靠。同时图形有比例尺之分，但是该算法却不受比例尺的限制，只要标准图幅和受检图幅比例尺一致即可完成图形检测。