水平集中符号距离函数并行降维计算  

Parallel computing of signed distance function in level set based on dimension reduction

作　　者：江少锋[1] 杨素华[2] 陈震[1] 张聪炫[1] 周旭欣[1] 

机构地区：[1]南昌航空大学测试与光电工程学院,南昌330063 [2]南昌航空大学信息工程学院,南昌330063

出　　处：《中国图象图形学报》2018年第2期174-181,共8页Journal of Image and Graphics

基　　金：国家自然科学基金项目(61162023);航空科学基金资助项目(2016ZC56005);江西省重点研发计划一般项目(20171BBG70052;20161BBE50080)~~

摘　　要：目的符号距离函数在水平集图像分割,视觉特征提取等图像处理领域有重要应用。随着图像分辨率越来越高,符号距离函数计算效率直接影响图像处理速度,为实现高分辨率图像实时处理,本文在降维法的基础上提出了并行算法,并针对并行计算对降维法进行了改进。方法降维法将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 low-er 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 computatio

关 键 词：符号距离函数 并行计算 降维法 抛物线下界法 水平集 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]