SSE图像算法优化系列二十五:二值图像的Euclidean distance map(EDM)特征图计算及其优化。
Euclidean distance map(EDM)这个概念可能听过的人也很少,其主要是用在二值图像中,作为一个很有效的中间处理手段存在。一般的处理都是将灰度图处理成二值图或者一个二值图处理成另外一个二值图,而EDM算法确是由一幅二值图生成一幅灰度图。其核心定义如下:
The definition is simple enough: each point in the foreground is assigned a brightness value equal to its straight line (hence “Euclidean”) distance from the nearest point in the background.
或者用一句更简洁的话说就是:The value of each pixel is the distance to the nearest background pixel (for background pixels, the EDM is 0)。
EDM由很多用处,比如由于像素都是分布在矩形格上,造成一些形态学上的操作存在一些方向偏移,以及在距离计算上的一些偏差都可以使用EDM技术克服,使用EDM来实现的腐蚀、膨胀或者开和闭操作相比普通的逐像素(模板操作)的结果来的更加各向同性化,如下图所示(很明显,基于EDM处理的图结果更加光滑,没有任何的方向性,而传统的逐像素的算法则有点棱角分明):
图一: 使用普通的逐像素的处理(从做至右依次是:二值原图、闭操作、开操作,找到的边界)
图二: 使用基于EDM的处理(从做至右依次是:二值原图、闭操作、开操作,找到的边界)
直接从图像的前景点搜索和其最接近的背景点的距离是一个极其低效和耗时的操作。一些研究者通过只取几个方向距离也实现了一些不同的EDM效果,比如只有45或者90度的角度的距离,但是这些距离的效果和传统的一些处理方法同样存在这没有足够的各向同性的性质,因此,也不具有很大的意义,如下图所示:
为了快速的实现EDM值的计算,不少作者提出了一些快速算法,其中比较经典的是Danielsson在1980提出的算法,其通过两次遍历图像给出了和原始计算一样的效果,具体步骤如下所示:
1. Assign the brightness value of 0 to each pixel in the background and a large positive value (greater than the maximum feature width) to each pixel in a feature.
2. Proceeding from left to right and top to bottom, assign each pixel within a feature a brightness value one greater than the smallest value of any of its neighbors.
3. Repeat step 2, proceeding from right to left and bottom to top.
在相关的资料中寻找参考的代码,可以找到如下一些资料:
The EDM algorithm is similar to the 8SSEDT in F. Leymarie, M. D. Levine, in: CVGIP Image Understanding, vol. 55 (1992), pp 84-94
public static int ONE = 100; // 这个值和一个像素的距离对应 public static int SQRT2 = 141; // 这个值和Sqr(2)个像素的距离对应 public static int SQRT5 = 224; // 这个值和Sqr(5)个像素的距离对应 public static void CalaEuclideanDistanceMap(FastBitmap Bmp) { int X, Y, Index, Value,Max; int Width, Height, Xmax, Ymax ; byte* Pointer; Width = Bmp.Width; Height = Bmp.Height; Xmax = Width - 2; Ymax = Height - 2; // 1. Assign the brightness value of 0 to each pixel in the background and a large positive // value (greater than the maximum feature width) to each pixel in a feature. int[] ImageData = new int[Width * Height]; for (Y = 0, Index = 0; Y < Height; Y++) { Pointer = Bmp.Pointer + Y * Bmp.Stride; for (X = 0; X < Width; X++, Index++) ImageData[Index] = Pointer[X]<<16; } // 2. Proceeding from left to right and top to bottom, assign each pixel within a feature a // brightness value one greater than the smallest value of any of its neighbors. for (Y = 0,Index=0; Y < Height; Y++) { Pointer = Bmp.Pointer + Y * Bmp.Stride; for (X = 0; X < Width; X++,Index++) { if (Pointer[X] > 0) { if ((X <=