一种基于计算几何的高效、快速的地铁裂缝主干提取算法及系统

摘要

本发明属于轨道交通技术领域，特别涉及一种基于计算几何的高效、快速的地铁裂缝主干提取算法及系统，机器识别连通的裂缝的算法流程，首先定义一个空的待访问队列Cn，以及一个空的存储空间Cxy；裂缝区域凸多边形的构造，根据上一步运算得到的所有裂缝像素点的横纵坐标，经过运算，可以得到由裂缝像素点集所构成的一个凸多边形；采用矩形框标识裂缝主干，由以上所述两个步骤可以得到凸多边形，得到凸多边形的基础上，识别裂缝的主干区域，并使用匹配的矩形框把相应区域标识出来；本发明的益处在于：此裂缝主干提取算法及系统结合了自动检测及人工检测的优势，人工工作量大大降低，而且精度得到保证，是一个较好的裂缝主干提取算法及系统。

说明书

技术领域

本发明属于轨道交通技术领域，特别涉及一种基于计算几何的高效、快速的地铁裂缝主干提取算法及系统。 

背景技术

近年来，随着城市建设的快速发展、城市规模的不断扩大以及城市人口的急剧膨胀，许多城市都出现了不同程度的交通拥堵问题。为了有效缓解城市公共交通问题.大家纷纷把目光转向发展城市轨道交通。我国北京、广州、南京、深圳、重庆等城市已有多条地铁线路投入营运，成都、青岛、沈阳等城市的地铁也正在建设中。 

城市轨道交通的特点是运行速度快、行车密度高、客流量大、环境封闭，因而对运营安全要求极高，需要安全可靠的基础设施系统作为保障。然而在地铁隧道运营管理及养护过程中，却发现由于运行车辆的动力冲击、地质变形以及临近施工等因素的影响，地铁隧道存在不同程度的裂缝，为地铁安全运营埋下了隐患，引起了业内人士普遍的关注。因此，能够随时高效、快速地查找地铁隧道表面裂缝的主干区域是确保城市轨道交通安全运行的必要措施。 

现阶段，国内对地铁隧道表面裂缝的检测提取主要是依靠人工，即采用以人工静态检查为主、动态检测车检查为辅的方式。然后这种以人工为主的检测方式必须在夜晚地铁线路无运营任务时进行，并且具有检测速度慢、工作效率低、占用线路时间长、人工成本高以及失误率高等不足，因此，这种主要依靠人工的方法已经不符合现代城市轨道交通发展的需求。 

因此，地铁隧道裂缝检测的发展趋势是裂缝的自动检测。目前裂缝自动检测技术主要有两种：1、基于形变数据的固定式检测方法；2、利用光学成像和图像处理技术的移动式自动检测方法。前者通过在地铁隧道内安装传感器来检测隧道形变数据，利用各种检测算法评估隧道的破损情况。该方法存在以下不足：传感器安装复杂、工程量大，成本高，传感器无法覆盖所有地铁隧道表面。 第二种方法检测灵活、移动性好、覆盖所有区间，并且随着机器视觉和图像处理技术的不断发展，检测的准确性和效率不断提高，已经成为主要的发展方向。 

然而，我国在地铁裂缝移动式自动检测方面的研究还比较薄弱，尚处在起步阶段。这几年，对裂缝的自动检测技术研究主要集中在公路路面以及工业探测上，比如钢板裂缝识别，在这些方面的确取得了一定成果，提出了一些有效的裂缝图像处理算法。而对于隧道等城市轨道交通基础设施的裂缝自动检测尚无报道。国外，日本和韩国在隧道表面裂缝自动检测领域的研究处于领先位置，日本的隧道裂缝光学检测系统甚至已经在工程中有了一些实际应用。 

移动式检测设备以线阵相机拍摄的图像的形式对地铁隧道全貌进行记录，通过图像处理技术识别隧道图像中的裂缝，通过适当方法将裂缝标识出来，进而采取适度措施来保障轨道交通安全。但是，由于地铁隧道内环境复杂，隧道裂缝形状千奇百怪，主裂缝与细小裂缝互相交叉，一条主裂缝往往会延伸出多条细小裂缝，等等。这种情况下，通过传统的图像处理方式无法恰当地标识出主干裂缝存在的区域，提取出的区域存在误差，并不能很好的表示裂缝的主干。 

本算法的核心部分是从遍历互相连通的裂缝像素点集开始，到采用矩形框把裂缝的主干区域标识出来结束。 

在本算法核心部分运算之前，我们先使用前人经常使用的图像处理技术初步对裂缝图像进行处理，该部分具体步骤包括：裂缝图像预处理、分块二值化、细化和去除噪声干扰四部分。裂缝图像预处理包括图像剪切、对比度调整、亮度调节等等。分块二值化是把8bit灰度图像的像素点根据事先设置的阈值转换为1bit的黑白像素点。细化是对裂缝宽度进行预处理。去除噪声干扰是尽可能地去除地铁隧道中众多污点对裂缝判断的影响。 

发明内容

为了克服现有技术对裂缝主干区域提取不准确的缺点，本发明通过借鉴计算几何的相关知识，识别连通的分叉交织裂缝，进一步通过本算法准确提取该分叉交织区域的裂缝主干部分，以确保对裂缝识别的准确性，以及为事后补救裂缝施工时提供更为重要与详细的信息。 

在传统的地铁隧道裂缝检测系统中，如果存在小裂缝与大裂缝混合在一起，或者大裂缝衍生出多条小裂缝的情况，那么传统算法就会把包含这些大大小小 的裂缝的整个区域标识出来，或者把这些裂缝识别成分离的多条裂缝。因而，无论采用上述哪种标识方法，都不能很好地标识出裂缝的主干区域。 

为了解决以上问题，我们提出了这种基于计算几何的高效、快速的地铁裂缝主干提取算法。具体方案如下：一种基于计算几何的高效、快速的地铁裂缝主干提取算法，其特征在于包含如下步骤： 

步骤1）机器识别连通的裂缝的算法流程，首先定义一个空的待访问队列C_n，以及一个空的存储空间C_xy； 

步骤2）裂缝区域凸多边形的构造，根据上一步运算得到的所有裂缝像素点的横纵坐标，经过运算，可以得到由裂缝像素点集所构成的一个凸多边形。 

步骤3）采用矩形框标识裂缝主干，由以上所述两个步骤可以得到凸多边形，得到凸多边形的基础上，识别裂缝的主干区域，并使用匹配的矩形框把相应区域标识出来。 

步骤1）还进一步包括： 

步骤1.1）取一个黑色像素点C_b1作为裂缝识别的一个起点，同时把C_b1加入到待访问队列C_n中，把C_b1坐标存入C_xy中； 

步骤1.2）将C_b1标记为已探测的裂缝像素点，然后搜索与C_b1相邻的其所有黑色像素点，把其中未被访问的黑色像素点C_b2，C_b3，...，C_bn依次放在待访问队列C_n的尾部，并把各自坐标把存入C_xy中； 

步骤1.3）用队列C_n的下一个首元素C_b2替换C_b1，并从队列C_n中去掉首元素C_b1。重复以上过程，直到队列C_n空为止； 

所述步骤2）还包括： 

步骤2.1）设裂缝像素点集中_y坐标最小的点为C₁，把C₁同裂缝像素点集中其他各点用线段连接，并计算这些线段与水平线的夹角。然后按照夹角大小及到C₁的距离进行词典式分类，得到一序列C₁，C₂，...，C_n，依次连接这些点，便得到一个多边形。C₁点是凸多边形边界的起点，C₂与C_n也必然是凸多边形的顶点。C_n+1=C₁； 

步骤2.2）删去C₃，C₄，...，C_n-1中不是凸多边形的点。 

步骤3.3）顺序输出凸多边形顶点。 

所述步骤3）还进一步包括： 

步骤3.1）找到最优的凸多边形对角线对应的两个顶点，具体方法步骤如下： 

步骤3.1.1）设该凸多边形的顶点中y坐标最小的点为C₁，从C₁开始按照凸多边形逆时针顺序可以得到凸多边形的各个顶点序列C₁，C₂，...，C_n； 

步骤3.1.2）依次计算所有裂缝点到每条对角线线段的距离之和，输出距离之和最小时对应的对角线的两个顶点； 

步骤3.1.3）输出最优的凸多边形对角线对应的两个顶点，即第二步中最终得到的minsum对应的顶点C_i和C_j； 

步骤3.2）计算最优的矩形框宽度并使用矩形框标识裂缝主干的相关算法。 

步骤3.2.1）依次计算除C_i和C_j以外的所有裂缝点C₁，C₂，...，C_n到对角线线段C_iC_j的距离s₁，s₂，...，s_n，其中，C_iC_j是由前面模块得到的最优的凸多边形对角线的两个端点，距离的计算方法参考步骤3.1.2）中的算法； 

步骤3.2.2）将步骤3.2.1）计算得到的距离s₁，s₂，...，s_n按照由小到大的顺序排列，取序列中第[0.5×n]个位置对应的s值，该s值即为最优的矩形框宽度值； 

步骤3.2.3）以C_i和C_j两点为一对对边的中点，以s为该对边的长度，画出一个矩形框，该矩形框标识的区域即为裂缝的主干区域。 

一种基于计算几何的高效、快速的地铁裂缝主干提取系统，其特征在于包括： 

机器识别连通的裂缝的算法流程模块，定义一个空的待访问队列C_n，以及一个空的存储空间C_xy； 

裂缝区域凸多边形的构造模块，根据上一个运算得到的所有裂缝像素点的横纵坐标，经过本模块算法，可以得到由裂缝像素点集所构成的一个凸多边形。 

采用矩形框标识裂缝主干模块，由以上所述两个模块可以得到凸多边形，得到凸多边形的基础上，识别裂缝的主干区域，并使用匹配的矩形框把相应区域标识出来。 

机器识别连通的裂缝的算法流程模块还包括： 

取一个黑色像素点C_b1作为裂缝识别的一个起点，同时把C_b1加入到待访问队列C_n中，把C_b1坐标存入C_xy中； 

将C_b1标记为已探测的裂缝像素点，然后搜索与C_b1相邻的其所有黑色像素点，把其中未被访问的黑色像素点C_b2，C_b3，...，C_bn依次放在待访问队列C_n的尾部，并把各自坐标把存入C_xy中； 

用队列C_n的下一个首元素C_b2替换C_b1，并从队列C_n中去掉首元素C_b1。重复以上过程，直到队列C_n空为止； 

裂缝区域凸多边形的构造模块还包括： 

设裂缝像素点集中y坐标最小的点为C₁，把C₁同裂缝像素点集中其他各点用线段连接，并计算这些线段与水平线的夹角。然后按照夹角大小及到C₁的距离进行词典式分类，得到一序列C₁，C₂，...，C_n，依次连接这些点，便得到一个多边形。C₁点是凸多边形边界的起点，C₂与C_n也必然是凸多边形的顶点。C_n+1=C₁； 

删去C₃，C₄，...，C_n-1中不是凸多边形的点。 

顺序输出凸多边形顶点。 

采用矩形框标识裂缝主干模块还包括： 

找到最优的凸多边形对角线对应的两个顶点： 

设该凸多边形的顶点中y坐标最小的点为C₁，从C₁开始按照凸多边形逆时针顺序可以得到凸多边形的各个顶点序列C₁，C₂，...，C_n； 

依次计算所有裂缝点到每条对角线线段的距离之和，输出距离之和最小时对应的对角线的两个顶点； 

输出最优的凸多边形对角线对应的两个顶点，即最终得到的minsum对应的顶点C_i和C_j； 

计算最优的矩形框宽度并使用矩形框标识裂缝主干的相关算法。 

依次计算除C_i和C_j以外的所有裂缝点C₁，C₂，...，C_n到对角线线段C_iC_j的距离s₁，s₂，...，s_n，其中，C_iC_j是由前面模块得到的最优的凸多边形对角线的两个端点； 

将上面计算得到的距离s₁，s₂，...，s_n按照由小到大的顺序排列，取序列中第[0.5×n]个位置对应的s值，该s值即为最优的矩形框宽度值； 

以C_i和C_j两点为一对对边的中点，以s为该对边的长度，画出一个矩形框，该矩形框标识的区域即为裂缝的主干区域。 

本发明的益处在于：此裂缝主干提取算法及系统结合了自动检测及人工检测的优势，人工工作量大大降低，而且精度得到保证，是一个较好的裂缝主干提取算法及系统。 

附图说明

图1为本发明算法框架流程图； 

图2为本发明系统结构示意图； 

图3为机器识别连通裂缝的算法结果示意图； 

图4为裂缝像素点构成的凸多边形； 

图5为查找最优凸多边形的对角线及其端点； 

图6为查找最优凸多边形的对角线及其端点； 

图7为使用矩形框标识裂缝主干； 

图8为使用矩形框标识裂缝主干； 

图9为使用矩形框标识裂缝主干。 

具体实施方式

当结合附图考虑时，通过参照下面的详细描述，能够更完整更好地理解本发明以及容易得知其中许多伴随的优点，但此处所说明的附图用来提供对本发明的进一步理解，构成本发明的一部分。 

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。 

实施例：如图1至图8所示，我们提出的核心算法流程具体分为三个模块：机器识别连通的裂缝的算法流程、裂缝区域凸多边形构造的算法流程和采用矩形框标识裂缝主干的算法流程。 

首先，详细介绍第一个模块——机器识别连通的裂缝的算法流程。我们首先定义一个空的待访问队列C_n，以及一个空的存储空间C_xy。第一步：取一个黑色像素点C_b1作为裂缝识别的一个起点，同时把C_b1加入到待访问队列C_n中，把C_b1坐标存入C_xy中。第二步：将C_b1标记为已探测的裂缝像素点，然后搜索与C_b1相邻的其所有黑色像素点，把其中未被访问的黑色像素点C_b2，C_b3，...，C_bn依次放在待访问队列C_n的尾部，并把各自坐标把存入C_xy中。第三步：用队列C_n的下一个首元素C_b2替换C_b1，并从队列C_n中去掉首元素C_b1。重复以 上过程，直到队列C_n空为止。如图2所示，即为按照上述算法得到的一个裂缝区域，该裂缝上的所有点的坐标都全部存放在了C_xy中。 

该部分的算法伪代码如下： 

这里调用了四个函数：CheckCrack()的初始值为0，被访问过的像素点Visited(i)置为1；AddCrack(C_ki，C_n)是将C_ki放于队列C_n之尾；DelCrackHead(C_n)是从队列C_n取第一个顶点，并将其从C_n中删除；AddCrackXY(C_ki，C_n)将C_ki的XY坐标放于C_xy之尾。 

第二个算法模块——裂缝区域凸多边形的构造。在本模块中，我们根据上一步运算得到的所有裂缝像素点的横纵坐标，经过本模块算法，可以得到由裂缝像素点集所构成的一个凸多边形。 

本模块的算法步骤如下： 

第一步：设裂缝像素点集中y坐标最小的点为C₁，把C₁同裂缝像素点集中其他各点用线段连接，并计算这些线段与水平线的夹角。然后按照夹角大小及到C₁的距离进行词典式分类，得到一序列C₁，C₂，...，C_n，依次连接这些点， 便得到一个多边形。C₁点是凸多边形边界的起点，C₂与C_n也必然是凸多边形的顶点。C_n+1=C₁。 

第二步：删去C₃，C₄，...，C_n-1中不是凸多边形的点，方法如下： 

第三步：顺序输出凸多边形顶点。 

根据上述步骤，可以得到如图3所示的示意图： 

第三个算法模块——采用矩形框标识裂缝主干。由以上所述两个模块可以得到上图所示的凸多边形。本算法模块在得到凸多边形的基础上，可以识别裂缝的主干区域，并使用恰当的矩形框把相应区域标识出来。 

本模块又主要过程包括两部分：找到最优的凸多边形对角线，计算最优的矩形框宽度并使用矩形框标识裂缝主干。下面详细介绍一下这三部分的算法。 

第一部分，找到最优的凸多边形对角线对应的两个顶点。方法步骤如下： 

第一步：设该凸多边形的顶点中y坐标最小的点为C₁，从C₁开始按照凸多边形逆时针顺序可以得到凸多边形的各个顶点序列C₁，C₂，...，C_n。 

第二步：依次计算所有裂缝点到每条对角线线段的距离之和。输出距离之和最小时对应的对角线的两个顶点，方法如下： 

第三步：输出最优的凸多边形对角线对应的两个顶点，即第二步中最终得到的minsum对应的顶点C_i和C_j。 

根据上述步骤，得到如图4所示的示意图： 

接下来，介绍该模块的第二部分计算最优的矩形框宽度并使用矩形框标识裂缝主干的相关算法。方法步骤如下： 

第一步：依次计算除C_i和C_j以外的所有裂缝点C₁，C₂，...，C_n到对角线线段C_iC_j的距离s₁，s₂，...，s_n。其中，C_iC_j是由前面模块得到的最优的凸多边形对角线的两个端点。距离的计算方法参考第三模块的第一部分第二步中的算法。 

第二步：将上面计算得到的距离s₁，s₂，...，s_n按照由小到大的顺序排列，取序列中第[0.5×n]个位置对应的s值，该s值即为最优的矩形框宽度值。 

第三步：以C_i和C_j两点为一对对边的中点，以s为该对边的长度，画出一个矩形框，该矩形框标识的区域即为裂缝的主干区域。示意图如图5所示： 

综上，此裂缝主干提取算法结合了自动检测及人工检测的优势，人工工作量大大降低，而且精度得到保证，是一个较好的裂缝主干提取算法。 

在实际应用过程中，该算法要综合图像处理、计算几何处理及人工活动之上，主要包括如下三个阶段：裂缝图像数据采集阶段、裂缝图像数据处理阶段和裂缝主干提取阶段，本算法主要应用在裂缝图像数据处理及裂缝主干提取阶段。 

裂缝图像数据采集阶段主要完成数据采集任务，即通过车载检测设备搭载图像采集设备，如CCD相机，按照一定速度扫描整个隧道，得到整个隧道的扫描图像，将所有图像数据存入数据库，以供下一步图像处理使用。 

在裂缝图像数据采集阶段完成之后，要对裂缝图像数据进行处理，这个阶段要用到图像处理的相关算法和本专利提出的相关算法。图像处理的相关算法包括：裂缝图像预处理、分块二值化、细化和去除噪声干扰四部分。而后，使用我们提出的专利算法中的机器识别连通的裂缝算法模块，得到连通的裂缝区域。 

在进行完裂缝图像数据处理阶段后，我们运行最核心的裂缝主干提取的算法。该阶段主要使用裂缝区域凸多边形构造的算法模块和使用矩形框标识裂缝主干的算法模块。按照裂缝主干提取的算法流程图，在得到连通裂缝区域之后，把该连通裂缝的所有像素点信息输入到裂缝区域凸多边形构造算法中，最终得到由该连通裂缝组成的最优凸多边形。而后，将该凸多边形的信息连同裂缝像 素点信息一起，输入到使用矩形框标识裂缝主干的算法中，最终正确、恰当地提取出地铁裂缝的主干。 

该算法以车载式检测设备（如CCD相机等）获取地铁隧道图像信息和图像处理技术为基础，以图像作为裂缝主干提取的信息源，所有对裂缝主干做出的处理标识都要基于已有的图像信息；图像获取技术为采用线阵CCD相机，在车辆移动时逐行扫描地铁隧道表面，而后将各行图像进行拼接，最终合成一幅完整的隧道表面图。特别注意的是，过程中应该保证相机采集数据速度与车速一致，以防产生图像变形、与实际裂缝不符等问题，对于裂缝特征的提取主要通过图像处理技术，通过该项技术，对裂缝进行识别、定位并且要对每条裂缝的宽度信息进行记录。 

该算法基于采集到的图像信息得到连通的裂缝区域，对裂缝区域的进一步处理，主要表现在两个方面： 

基于计算几何的相关技术，构造出裂缝区域的特征凸多边形； 

根据特征凸多边形，使用该算法，得到最优的凸多边形对角线及其端点； 

图像信息来自最新的图像采集结果。 

使用该算法，根据事先约定的阈值，进行裂缝主干的提取，并使用矩形框进行标识，阈值是事先约定好的，例如专利说明书中的0.5，是经过多次试验得到的最优经验值。 

以上就是该专利算法应用过程中具体的实施步骤，按照此步骤就能保证实时提取标识所有裂缝的主干，以评估地铁隧道危险程度，确保地铁轨道交通的运行安全。 

以上对本发明所提供的一种基于计算几何的高效、快速的地铁裂缝主干提取算法及系统进行了详细介绍，以上参照附图对本申请的示例性的实施方案进行了描述。本领域技术人员应该理解，上述实施方案仅仅是为了说明的目的而所举的示例，而不是用来进行限制，凡在本申请的教导和权利要求保护范围下所作的任何修改、等同替换等，均应包含在本申请要求保护的范围内。