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.