一种并行快速符号距离函数计算方法

技术领域

本发明涉及一种图像处理领域，具体为一种用于水平集图像分割的快速符号距离函数计算方法。

背景技术

图像分割是图像处理领域中的一个关键技术，主要用于目标识别和理解，在基于图像的人工智能领域中起到非常重要的作用。，同时图像分割也是一经典难题，发展至今仍没有找到一个通用的方法。常用的分割技术有基于阈值的分割方法、基于边界的分割方法、基于区域的分割方法。Osher和Sethian提出的基于水平集的分割方法是一种基于边界的分割方法，由于能够很好地处理拓扑结构发生变化时产生的问题近年来成为图像分割中最大的研究热点。一般在水平集计算的初始化及更新过程中，都需要计算符号距离函数(SDF)。符号距离函数如下定义：

其中d[(x,y),C]表示点(x,y)与闭合曲线C之间的距离。

这一选择的优点是：由于距离函数具有如下基本性质：这意味着u(x,y)的变化率处处都是均匀的，没有太多的坡地，也没有平原。这样将有利于数值计算的稳定性。

由于给定的曲线运动方程只是对于嵌入函数的零水平集成立，而不是对函数的所有水平集成立，所以随着演化的的进行，u逐渐偏离了距离函数的性质，远大于1的某些局部就会出现尖峰或者深谷，远小于1的局部就会出现平坦区。以致计算结果发生误差，如果不加以纠正，这种误差就会逐渐增大，最终导致计算结果严重错误。为了让水平集函数始终保持为符号距离函数，有必要在进行若干次u的更迭后，进行重新初始化。为此符号距离函数在水平集初始化及演化过程中都需要计算。

对于任意闭合曲线，直接计算符号距离函数的计算量较大。特别是对于大幅图像来说，计算量更大。因此，如何快速准确地计算任意闭合曲线地符号距离函数，对于提高水平集方法地效率和稳定性至关重要。

符号距离函数不仅用于水平集分割还大量直接用于计算机视觉中的三维视觉特征提取，模式识别等领域。而计算符号距离函数的计算量较大，时间复杂度为O(N*M)，N为图像点数，M为闭合曲线点数。尤其对于大幅图像，计算量更大。故快速准确地计算符号距离函数对提高水平集方法的效率和稳定性至关重要。

上世纪90年代开始研究人员提出了源点扫描法，快速步进法和降维法。源点扫描法确认与每个网格点同处一条特性线(轮廓线C的法线)上的轮廓线点(源点)，基于源点来计算符号距离，其计算复杂度为O(K*N)，其中K为迭代此处，N为图像点数。快速步进法以封闭曲线为起点，从法线方向进行放射，采用快速匹配法计算符号距离，该方法的计算复杂度为O(NlnM)。降维法将2维或更高维符号距离计算转换为两次1维符号距离计算(见公式(2))，其中D_f|x'(y)为沿Y方向每列1维符号距离计算结果，再沿X方向做一次1维符号距离计算即得到D_f(x,y)。每次1维符号距离计算(式3)可等效为求一系列图像点对应的抛物线组的下边界得到(附图1)，其计算复杂度为O(2N)。虽然理论上在降维法计算中图像的每行和每列的计算是独立的，可以并行计算完成，计算复杂度为O(W+H)，其中W为图像宽度，H为图像高度，但是所采用的抛物线下边界法仍然是串行的。

其中

发明内容

本发明的目的是提供一种快速符号距离函数计算方法，该方法采用并行方法快速生成距离值，该计算方法与传统计算方法相比，具有很高的实时性。符号距离函数计算是水平集图像分割技术中的关键步骤，常规计算方法非常耗时，影响图像分割效率。本发明采用并行计算实现符号距离函数的快速计算，进而大大提高分割速度。

本发明的上述目的通过如下技术方案来实现的：一种并行快速符号距离函数计算方法，它包括如下步骤：它包括如下步骤：

1)符号计算步骤，采用区域生长法确定区域内部和外部，从而得到距离符号值；

2)Y方向计算步骤，该步骤通过并行方法得到图像上各点在Y方向上到封闭曲线距离值D_f|x'(y)；

3)X方向计算步骤，该步骤通过并行抛物线下界方法得到图像上各点到封闭曲线最短距离值D_f(x,y)。

本发明对于宽度为W，高度为H的图像，分配W*H个线程，每个线程负责图像中一个点的计算。具体计算时采用了并行降维法，即将二维图像的符号距离计算变成两个1维并行符号距离的计算。

本发明每个点并行计算时先向右计算，删除抛物线下界以上的抛物线，再向左计算删除抛物线下界以上的抛物线。

与现有技术相比，具有以下有益效果：

(1)本发明所涉及的符号距离是通过并行计算得到的，故计相对于串行计算

方法速度要快很多。

(2)本发明主要解决了抛物线下界法的并行计算问题。常规串行抛物线下界

法寻找抛物线下界时，需要通过各抛物线的交点进行动态排序调整，即当次的

排序结果需用到上次的排序，是一个典型的串行问题。本发明巧妙地将该串行

问题转化成少量并行问题的迭代计算，即每次迭代时，每个点均向前向后进行

抛物线下界计算，最多经过3次迭代计算即能完成所有点的距离计算，即计算

复杂度为O(3)，远远低于O(W+H)。

附图说明

图1为抛物线下界法求符号距离示意图。从图中可以看出抛物线Y1的左边和抛物线Y4的右边构成这组抛物线的下界，抛物线Y2和Y3被删除，而这个下界就是每个点的符号距离，即Y1的左边曲线和Y4的右边曲线就是各点的符号距离值。

图2为并行抛物线下界法流程图。

具体实施方式

实施例一：

一种并行快速符号距离函数计算方法，它包括如下步骤：

1)采用区域生长法得到一个封闭曲线的内部和外部，内部距离符号置负，外部距离符号置正；

2)对于宽度为W，高度为H的图像，分配W*H个线程，每个线程负责图像中一个点的符号距离计算；

3)并行扫描图像中的每列，计算每个点离边界点垂直方向上的最近一维距离D_f|x'(y)。

4)并行扫描图像中的每行，采用并行抛物线下界法计算得到二维D_f(x,y)。

实施例二：

一种并行快速符号距离函数计算方法，它包括如下步骤：

步骤1，从计算机硬盘中读入包含封闭曲线的宽度为W，高度为H的图像，其中封闭曲线的点的像素值为1，其他点的像素值为0。

步骤2，计算符号。采用区域生长法得到一个封闭曲线的内部和外部，内部距离符号置负，外部距离符号置正。

步骤3，计算D_f|x'(y)。分配W*H个线程，每个线程对应图像中的一个点，对于每个封闭曲线上的点(源点)以步长1分别向上和向下延伸到图像边界，经过的点的D_f|x'(y)即为延伸的步长数，记录其相应的源点；在进行延伸时，如果经过的点已有源点存在，则其存在多个源点，那么取离它距离最近的源点的距离作为D_f|x'(y)。

步骤4，计算D_f(x,y)。分配W*H个线程，每个线程对应图像中的一个点。计算分两步，第一步向右计算阶段，并行计算每个点对应的抛物线和右边相邻点对应抛物线的交点，如果交点在前一个交点左边，则删除前一个抛物线，并做删除标志，删除掉的抛物线不再参与后续计算，继续与后面一个点的抛物线求交点，直到没有抛物线被删除或者后一个抛物线是被删除的为止；第二步向左计算阶段，并行计算每个点对应的抛物线和左边相邻点(且没有删除标志)对应抛物线的交点，如果交点在后一个交点右边，则删除当前抛物线，继续与前面一个没有删除标志的抛物线求交点，直到没有抛物线被删除为止。具体计算流程图见附图2。