signed distance field 算法

柔光的暖阳◎ 2022-09-21 01:42 18阅读 0赞

# 将二值图转化成signed distance field后，可以在双线性插值下实现平滑放大。  定义：  到前景的distance field：各点到最近前景点的距离。  到背景的distance field：各点到最近背景景点的距离。  则： signed distance field = 到背景的distance field - 到前景的distance field。  注：最好严格按上面定义计算signed distance field。看到有的博文中说先提取轮廓点，然后计算各点到最近轮廓点的距离，并且如果此点是前景点就将计算出的距离加+号，如果此点是背景点就将计算出的距离加-号。这样确实也得到一个signed distance field，但显然这样计算出来的signed distance field跟严格按照上面定义计算出来的结果是不一样的。  按标准定义计算出signed distance field后，轮廓阈值应取为0.5，即signed distance field中大于等于0.5的像素复原为前景。  实际存储的时候我是求了一下signed distance field中的最大值max和最小值min，然后通过(signedDis-min)/(max-min)将signedDis映射到\[0,1\]，并且将轮廓阈值0.5映射为(0.5-min)/(max-min)，即得到了一个取值在\[0,1\]间的signed distance field,其轮廓阈值为(0.5-min)/(max-min)。  生成signed distance field的算法，开始我在这个博文（http://blog.csdn.net/tianwaifeimao/article/details/45078661）中找到一个Saito算法，它利用距离平方在x和y上可分开处理的性质提高了计算效率，虽然没有完全达到线性复杂度，但也比暴力算法快得多。算法的正确性很容易看出来，实现出来实测了一下，也没问题。  后来又在网上找到一个称为8ssedt的算法（见：http://www.codersnotes.com/algorithms/signed-distance-fields），博文中给的论文链接打不开，但给出源代码下载，代码很短能看明白，用的是与最短路径的算法相同的思路，针对问题本身的结构做了很巧妙的优化，达到了线性复杂度。（注：前述Saito算法第一步求各点在本行中的最近前景点时也可以利用8ssedt算法的思路进行优化计算）。  8ssedt算法代码如下（转自:http://www.codersnotes.com/algorithms/signed-distance-fields）：  `#include "SDL/sdl.h" #include <math.h> #define WIDTH 256 #define HEIGHT 256 struct Point { int dx, dy; int DistSq() const { return dx*dx + dy*dy; } }; struct Grid { Point grid[HEIGHT][WIDTH]; }; Point inside = { 0, 0 }; Point empty = { 9999, 9999 }; Grid grid1, grid2; Point Get( Grid &g, int x, int y ) { // OPTIMIZATION: you can skip the edge check code if you make your grid // have a 1-pixel gutter. if ( x >= 0 && y >= 0 && x < WIDTH && y < HEIGHT ) return g.grid[y][x]; else return empty; } void Put( Grid &g, int x, int y, const Point &p ) { g.grid[y][x] = p; } void Compare( Grid &g, Point &p, int x, int y, int offsetx, int offsety ) { Point other = Get( g, x+offsetx, y+offsety ); other.dx += offsetx; other.dy += offsety; if (other.DistSq() < p.DistSq()) p = other; } void GenerateSDF( Grid &g ) { // Pass 0 for (int y=0;y<HEIGHT;y++) { for (int x=0;x<WIDTH;x++) { Point p = Get( g, x, y ); Compare( g, p, x, y, -1, 0 ); Compare( g, p, x, y, 0, -1 ); Compare( g, p, x, y, -1, -1 ); Compare( g, p, x, y, 1, -1 ); Put( g, x, y, p ); } for (int x=WIDTH-1;x>=0;x--) { Point p = Get( g, x, y ); Compare( g, p, x, y, 1, 0 ); Put( g, x, y, p ); } } // Pass 1 for (int y=HEIGHT-1;y>=0;y--) { for (int x=WIDTH-1;x>=0;x--) { Point p = Get( g, x, y ); Compare( g, p, x, y, 1, 0 ); Compare( g, p, x, y, 0, 1 ); Compare( g, p, x, y, -1, 1 ); Compare( g, p, x, y, 1, 1 ); Put( g, x, y, p ); } for (int x=0;x<WIDTH;x++) { Point p = Get( g, x, y ); Compare( g, p, x, y, -1, 0 ); Put( g, x, y, p ); } } } int main( int argc, char* args[] ) { if ( SDL_Init( SDL_INIT_VIDEO ) == -1 ) return 1; SDL_Surface *screen = SDL_SetVideoMode( WIDTH, HEIGHT, 32, SDL_SWSURFACE ); if ( !screen ) return 1; // Initialize the grid from the BMP file. SDL_Surface *temp = SDL_LoadBMP( "test.bmp" ); temp = SDL_ConvertSurface( temp, screen->format, SDL_SWSURFACE ); SDL_LockSurface( temp ); for( int y=0;y<HEIGHT;y++ ) { for ( int x=0;x<WIDTH;x++ ) { Uint8 r,g,b; Uint32 *src = ( (Uint32 *)( (Uint8 *)temp->pixels + y*temp->pitch ) ) + x; SDL_GetRGB( *src, temp->format, &r, &g, &b ); // Points inside get marked with a dx/dy of zero. // Points outside get marked with an infinitely large distance. if ( g < 128 ) { Put( grid1, x, y, inside ); Put( grid2, x, y, empty ); } else { Put( grid2, x, y, inside ); Put( grid1, x, y, empty ); } } } SDL_UnlockSurface( temp ); // Generate the SDF. GenerateSDF( grid1 ); GenerateSDF( grid2 ); // Render out the results. SDL_LockSurface( screen ); for( int y=0;y<HEIGHT;y++ ) { for ( int x=0;x<WIDTH;x++ ) { // Calculate the actual distance from the dx/dy int dist1 = (int)( sqrt( (double)Get( grid1, x, y ).DistSq() ) ); int dist2 = (int)( sqrt( (double)Get( grid2, x, y ).DistSq() ) ); int dist = dist1 - dist2; // Clamp and scale it, just for display purposes. int c = dist*3 + 128; if ( c < 0 ) c = 0; if ( c > 255 ) c = 255; Uint32 *dest = ( (Uint32 *)( (Uint8 *)screen->pixels + y*screen->pitch ) ) + x; *dest = SDL_MapRGB( screen->format, c, c, c ); } } SDL_UnlockSurface( screen ); SDL_Flip( screen ); // Wait for a keypress SDL_Event event; while( true ) { if ( SDL_PollEvent( &event ) ) switch( event.type ) { case SDL_QUIT: case SDL_KEYDOWN: return true; } } return 0; }`  [signed distance field 算法][signed distance field]  标签：[des][] [算法][Link 1] [class][] [log][] [com][] [http][] [si][] [代码][Link 2] [it][]  原文：http://www.cnblogs.com/wantnon/p/4947067.html #

[signed distance field]: http://www.bubuko.com/infodetail-1185541.html
[des]: http://www.bubuko.com/so/1/des
[Link 1]: http://www.bubuko.com/so/1/%e7%ae%97%e6%b3%95
[class]: http://www.bubuko.com/so/1/class
[log]: http://www.bubuko.com/so/1/log
[com]: http://www.bubuko.com/so/1/com
[http]: http://www.bubuko.com/so/1/http
[si]: http://www.bubuko.com/so/1/si
[Link 2]: http://www.bubuko.com/so/1/%e4%bb%a3%e7%a0%81
[it]: http://www.bubuko.com/so/1/it