浏览全部资源
扫码关注微信
收稿：2017-07-18，
修回：2017-10-27，
纸质出版：2018-02-16
移动端阅览
目的
2
符号距离函数在水平集图像分割，视觉特征提取等图像处理领域有重要应用。随着图像分辨率越来越高，符号距离函数计算效率直接影响图像处理速度，为实现高分辨率图像实时处理，本文在降维法的基础上提出了并行算法，并针对并行计算对降维法进行了改进。
方法
2
降维法将2维距离计算转化为两个1维距离计算，并采用抛物线下界法计算1维距离，是当前最快的一种符号距离计算方法。首先利用行和列计算的独立性，提出了降维法的并行算法。然后再对并行降维法进行改进，提出了抛物线下界法的并行算法。该方法采用多线程分段并行计算抛物线下界，即每个像素点与段内相邻像素点并行进行抛物线求交运算，快速搜索抛物线下界，从而实现了抛物线下界法的分段并行距离函数计算。所有并行算法在CUDA平台上采用GPU通用并行计算方法实现。
结果
2
对不同分辨率及包含不同曲线的9幅图像进行实验测试，在距离计算误差小于1的条件下，并行降维算法对所有测试图像计算时间均小于0.06 s，计算效率比串行方法有了10倍以上的提升，改进并行降维算法对所有测试图像计算时间均小于0.03 s，计算效率比串行方法有了20倍左右的提升。
结论
2
该方法实现了符号距离函数的快速并行计算，其优势在于当图像分辨率较高时仍然能够实现实时处理。
Objective
2
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
2
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(2
N
) 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
+2
H
)
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(2
W
+
kS
)
where
k
is the iterative times
and
S
is the length of the segment.
Result
2
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
2
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.
Sethian J A. Level Set Methods and Fast Marching Methods:Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science[M]. London:Cambridge University Press, 1999.
Osher S, Sethian J A. Fronts propagating with curvature-dependent speed:algorithms based on Hamilton-Jacobi formulation[J]. Journal of Computational Physics, 1988, 79(1):12-49.[DOI:10.1016/0021-9991(88)90002-2]
Sharma O, Agarwal N. Signed distance based 3D surface reconstruction from unorganized planar cross-sections[J]. Computers&Graphics, 2016, 62:67-76.[DOI:10.1016/j.cag.2016.12.002]
Guo D, Li C Q, Wu L, et al. Improved marching tetrahedra algorithm based on hierarchical signed distance field and multi-scale depth map fusion for 3D reconstruction[J]. Journal of Visual Communication and Image Representation, 2017, 48:491-501.[DOI:10.1016/j.jvcir.2016.12.016]
Fabbri R, Costa L D F, Torelli J C, et al. 2D Euclidean distance transform algorithms:a comparative survey[J]. ACM Computing Surveys, 2008, 40(1):#2.[DOI:10.1145/1322432.1322434]
Tsai Y H R. Rapid and accurate computation of the distance function using grids[J]. Journal of Computational Physics, 2002, 178(1):175-195.[DOI:10.1006/jcph.2002.7028]
Li J, Yang X, Shi P F. A fast level set approach to image segmentation based on mumford-shah model[J]. Chinese Journal of Computers, 2002, 25(11):1175-1183.
李俊, 杨新, 施鹏飞.基于Mumford-Shah模型的快速水平集图像分割方法[J].计算机学报, 2002, 25(11):1175-1183. [DOI:10.3321/j.issn:0254-4164.2002.11.008]
Dong J W, Yang H Y, Zhang B. Fast generation of signed distance function in level set method[J]. Computer Engineering and Application, 2009, 45(34):180-182.
董吉文, 杨海英, 张冰.水平集方法中符号距离函数的快速生成[J].计算机工程与应用, 2009, 45(34):180-182. [DOI:10.3778/j.issn.1002-8331.2009.34.056]
Sethian J A. A fast marching level set method for monotonically advancing fronts[J]. Proceedings of the National Academy of Sciences of the United States of America, 1996, 93(4):1591-1595.[DOI:10.1073/pnas.93.4.1591]
Felzenszwalb P F, Huttenlocher D P. Distance transforms of sampled functions[J]. Theory of Computing, 2012, 8(19):415-428.[DOI:10.4086/toc.2012.v008a019]
Mishchenko Y. A fast algorithm for computation of discrete Euclidean distance transform in three or more dimensions on vector processing architectures[J]. Signal, Image and Video Processing, 2015, 9(1):19-27.[DOI:10.1007/s11760-012-0419-9]
Zhang B, Su Y L, Zhang S L. Method for generating the signed distance function based on curve marching[J]. Journal of Northwest University:Natural Science Edition, 2007, 37(5):697-700.
张博, 苏永利, 张书玲.基于曲线推进的符号距离函数生成方法[J].西北大学学报:自然科学版, 2007, 37(5):697-700. [DOI:10.16152/j.cnki.xdxbzr.2007.05.033]
Zhang B, Su Y L. A fast method for signed distance function generation[J]. Computer Applications and Software, 2008, 25(6):102-103, 112.
张博, 苏永利.一种快速的符号距离函数的生成方法[J].计算机应用与软件, 2008, 25(6):102-103, 112. [DOI:10.3969/j.issn.1000-386X.2008.06.041]
Feng C L, Zhao D Z, Huang M. Image segmentation using CUDA accelerated non-local means denoising and bias correction embedded fuzzy c-means (BCEFCM)[J]. Signal Processing, 2016, 122:164-189.[DOI:10.1016/j.sigpro.2015.12.007]
Fluck O, Vetter C, Wein W, et al. A survey of medical image registration on graphics hardware[J]. Computer Methods and Programs in Biomedicine, 2011, 104(3):e45-e57.[DOI:10.1016/j.cmpb.2010.10.009]
相关作者
相关机构
京公网安备11010802024621
