摘要：
目的 符号距离函数在水平集图像分割,视觉特征提取等图像处理领域有重要应用.随着图像分辨率越来越高,符号距离函数计算效率直接影响图像处理速度,为实现高分辨率图像实时处理,本文在降维法的基础上提出了并行算法,并针对并行计算对降维法进行了改进.方法 降维法将2维距离计算转化为两个1维距离计算,并采用抛物线下界法计算1维距离,是当前最快的一种符号距离计算方法.首先利用行和列计算的独立性,提出了降维法的并行算法.然后再对并行降维法进行改进,提出了抛物线下界法的并行算法.该方法采用多线程分段并行计算抛物线下界,即每个像素点与段内相邻像素点并行进行抛物线求交运算,快速搜索抛物线下界,从而实现了抛物线下界法的分段并行距离函数计算.所有并行算法在CUDA平台上采用GPU通用并行计算方法实现.结果 对不同分辨率及包含不同曲线的9幅图像进行实验测试,在距离计算误差小于1的条件下,并行降维算法对所有测试图像计算时间均小于0.06 s,计算效率比串行方法有了10倍以上的提升,改进并行降维算法对所有测试图像计算时间均小于0.03 s,计算效率比串行方法有了20倍左右的提升.结论 该方法实现了符号距离函数的快速并行计算,其优势在于当图像分辨率较高时仍然能够实现实时处理.%Objective Signed distance functions are the nearest distances between pixels and points on the closed curve in an image,with a negative sign in the curve and a positive sign outside the curve.The signed distance function has important applications in image processing,such as level set-based segmentation,3D visual feature extraction,and pattern recognition in computer vision.The computational complexity of the signed distance function is O (N × M),where N is the number of pixels in an image,and M is the number of points on a closed curve.The high computational complexity of the signed distance function directly affects the computational efficiency of image processing with the increase in image resolution.For real-time processing of an image with high resolution,an improved real-time computing method for the signed distance function based on the dimension reduction method was proposed to improve the computational efficiency.Method Dimension reduction method transforms the 2D signed distance function into two independent 1D signed distance functions for each row (or column) of the image and uses lower parabola envelope-based method for calculating the 1D distance.The lower parabola envelope-based method sequentially computes the lower envelope of the first q parabolas,where the parabolas are ordered according to the horizontal locations of their vertices.The computational complexity of the dimension reduction method is O (2N) and is one of the fastest methods for calculating the signed distance function.This paper first proposes a parallel dimension reduction method according to the computational independence of the signed distance function among the rows (or columns) in an image to reduce the computational time of the dimension reduction method.The parallel dimension reduction method calculates the signed distance functions of the different rows (or columns) in an image simultaneously by allowing each thread to correspond to a row (or column) in the image.Thus,the computational complexity of the proposed parallel dimension reduction method is reduced to O (2 W + 2H),where W and H are the width and height of the image,respectively.Second,this paper proposes an improved parallel dimension reduction method by running the lower parabola envelope-based method in a parallel manner to improve the computational efficiency further.The improved parallel dimension reduction method uses multi-threads in calculating the lower parabola envelope in different segments to perform the dimension reduction method by finding the intersection points between two neighboring parabolas in a segment simultaneously.All parallel processing steps were completed on CUDA platform for general parallel computing on GPU.The first step is calculating the sign by assigning H threads,and each thread should correspond to a row in the image.The second step is calculating the 1D distance by assigning W × H threads.Each thread should correspond to a pixel in the image and should scan from left to right of the image to touch the closed curve and set the scanning distance as the 1D distance of each pixel.The last step is calculating the 2D distance by assigning W × H threads.Each thread should correspond to a pixel in the image and should scan from top to bottom of the image to obtain the final distance using the proposed parallel lower parabola envelope-based method.The entire computational complexity of distance in this method is O (2W + kS),where k is the iterative times,and S is the length of the segment.Result Nine images with different image sizes (256 × 256,1 280 × 1 280,and 2 560 × 2 560) and curve shapes were tested in our experiments.The computational time of three generating methods for signed distance function (the regular serial,the proposed parallel,and the improved parallel dimension reduction methods) was compared with the case in which the maximal error was below 1.The computational time of the parallel method was less than 0.06 s for all testing images and more than 10 times faster than that of the regular serial dimension reduction method.The computational time of the improved parallel method was less than 0.03 s for all testing images and approximately 20 times faster than that of the regular serial dimension reduction method.Conclusion The proposed parallel method for the signed distance function can generate the signed distance in tens of milliseconds.Thus,the proposed parallel method is sufficiently fast for real-time image processing,especially for high-resolution images.
