將二值圖轉化成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，即signed distance field中大于等于0的像素復原為前景。

實際存儲的時候我是求了一下signed distance field中的最大值max和最小值min，然后通過(signedDis-min)/(max-min)將signedDis映射到[0,1]，并且將輪廓閾值0映射為(0-min)/(max-min)，即得到了一個取值在[0,1]間的signed distance field,其輪廓閾值為(0-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 256struct 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];elsereturn 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 0for (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 1for (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/dyint 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 keypressSDL_Event event;while( true ){if ( SDL_PollEvent( &event ) ) switch( event.type ){case SDL_QUIT:case SDL_KEYDOWN:return true;}}return 0; }

?

轉載于:https://www.cnblogs.com/wantnon/p/4947067.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的signed distance field 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。