高效的8連接洪水填充

我一直在使用保羅赫克伯特出色的種子填充算法（可用here和書Graphic Gems (1990)）。高效的8連接洪水填充

由於該算法可能會出現卷積。它設計精良，速度很快！不幸的是，它只適用於4連通的空間。

我正在尋找8連通空間（沿對角線泄漏）的設計良好，快速的算法。有任何想法嗎？

遞歸訪問或反覆拋出每個單元格到堆棧不會被認爲是精心設計的這個問題的目的。以僞代碼提供的算法是最受讚賞的（Heckbert's有代碼和僞代碼）。

謝謝！

Heckbert的算法，這裏複製的完整性：

/* 
* A Seed Fill Algorithm 
* by Paul Heckbert 
* from "Graphics Gems", Academic Press, 1990 
* 
* user provides pixelread() and pixelwrite() routines 
*/ 

/* 
* fill.c : simple seed fill program 
* Calls pixelread() to read pixels, pixelwrite() to write pixels. 
* 
* Paul Heckbert 13 Sept 1982, 28 Jan 1987 
*/ 

typedef struct {  /* window: a discrete 2-D rectangle */ 
    int x0, y0;   /* xmin and ymin */ 
    int x1, y1;   /* xmax and ymax (inclusive) */ 
} Window; 

typedef int Pixel;  /* 1-channel frame buffer assumed */ 

Pixel pixelread(); 

typedef struct {short y, xl, xr, dy;} Segment; 
/* 
* Filled horizontal segment of scanline y for xl<=x<=xr. 
* Parent segment was on line y-dy. dy=1 or -1 
*/ 

#define MAX 10000  /* max depth of stack */ 

#define PUSH(Y, XL, XR, DY) /* push new segment on stack */ \ 
    if (sp<stack+MAX && Y+(DY)>=win->y0 && Y+(DY)<=win->y1) \ 
    {sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;} 

#define POP(Y, XL, XR, DY) /* pop segment off stack */ \ 
    {sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;} 

/* 
* fill: set the pixel at (x,y) and all of its 4-connected neighbors 
* with the same pixel value to the new pixel value nv. 
* A 4-connected neighbor is a pixel above, below, left, or right of a pixel. 
*/ 

fill(x, y, win, nv) 
int x, y; /* seed point */ 
Window *win; /* screen window */ 
Pixel nv; /* new pixel value */ 
{ 
    int l, x1, x2, dy; 
    Pixel ov; /* old pixel value */ 
    Segment stack[MAX], *sp = stack; /* stack of filled segments */ 

    ov = pixelread(x, y);  /* read pv at seed point */ 
    if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1) return; 
    PUSH(y, x, x, 1);   /* needed in some cases */ 
    PUSH(y+1, x, x, -1);  /* seed segment (popped 1st) */ 

    while (sp>stack) { 
    /* pop segment off stack and fill a neighboring scan line */ 
    POP(y, x1, x2, dy); 
    /* 
    * segment of scan line y-dy for x1<=x<=x2 was previously filled, 
    * now explore adjacent pixels in scan line y 
    */ 
    for (x=x1; x>=win->x0 && pixelread(x, y)==ov; x--) 
     pixelwrite(x, y, nv); 
    if (x>=x1) goto skip; 
    l = x+1; 
    if (l<x1) PUSH(y, l, x1-1, -dy);  /* leak on left? */ 
    x = x1+1; 
    do { 
     for (; x<=win->x1 && pixelread(x, y)==ov; x++) 
     pixelwrite(x, y, nv); 
     PUSH(y, l, x-1, dy); 
     if (x>x2+1) PUSH(y, x2+1, x-1, -dy); /* leak on right? */ 
skip:  for (x++; x<=x2 && pixelread(x, y)!=ov; x++); 
     l = x; 
    } while (x<=x2); 
    } 
}

來源

2012-03-07 Richard

也許你應該投入一點努力自己開始。設計和實施上述計劃可能需要花費100個小時。延長我可能需要花費幾個小時。展示下。 – wildplasser 2012-03-07 21:19:14

這是值得的事情，看看是否已經發明和完善了@wildplasser。我很欣賞你希望每個人都能始終重新發明。但是，我們都會住在山洞裏，或者使用Windows。如果沒有生成合適的算法，我一定會生成它。如果有，那麼利用現有的更好。 – Richard 2012-03-07 21:24:31

如果你依賴別人的珠子和鏡子，你就住在籠子裏。先試着製作你自己的作品，否則你永遠不會離開那個籠子。 – wildplasser 2012-03-07 21:38:12

檢查cvFloodFill()從OpenCV框架。該標誌參數似乎是用來設置這個值：

void cvFloodFill(CvArr* image, 
       CvPoint seed_point, 
       CvScalar new_val, 
       CvScalar lo_diff=cvScalarAll(0), 
       CvScalar up_diff=cvScalarAll(0), 
       CvConnectedComp* comp=NULL, 
       int flags=4, 
       CvArr* mask=NULL)

來源

2012-03-07 21:19:59 karlphillip

高效的8連接洪水填充

回答

相關問題