각 전경 픽셀에 대해서 모든 배경 픽셀까지 거리를 구한 다음 최솟값을 할당하면 된다. 픽셀 수가 n = w * h 개면 time complexity는 O(n^2)이다 (이미지 폭이나 높이의 4승이므로 연산량이 상당하다.) linear time Euclidean distance transform은 kipl.tistory.com/268.

ListPlot3D[ Reverse@ImageData[pic], PlotRange -> Full]

mathematica를 이용한 3D plot

int brute_force_edt(double *img, int w, int h) {
    int n = w * h;
    std::vector<int> list(n);
    int fg_cnt = 0;
    int bg_ptr = n - 1;               //배경 픽셀 위치는 끝에서 역으로 채움;
    //전경과 배경 픽셀 위치를 분리;
    for (int i = 0; i < n; ++i)
        if (img[i])                  // foreground;
            list[fg_cnt++] = i;
        else                         // background;
            list[bg_ptr--] = i;

    for (int i = 0; i < fg_cnt; ++i) {     // 전경 픽셀;
        int xi = list[i] % w, yi = list[i] / w;
        double d2min = DBL_MAX;
        for (int j = n; j-- > fg_cnt; ) { // 배경 픽셀까지 거리를 계산해서 최소값을 할당;
                                          // 배경이 list에 역순으로 저장됨으로 역방향 서치;
            int xj = list[j] % w, yj = list[j] / w;
            double dx  = xi - xj, dy = yi - yj;  //
            double dst = dx * dx + dy * dy;
            if (dst == 1) { 
            	d2min = 1; break;
            }
            if (d2min > dst) d2min = dst;
        }
        img[list[i]] = d2min;
    }
    return fg_cnt;
}
 
 
 
728x90

'Image Recognition > Fundamental' 카테고리의 다른 글

Interpolation Kernels  (0) 2021.05.05
Fowler Angle  (0) 2021.04.05
Poisson Noise  (0) 2021.03.06
Grassfire Algorithm  (0) 2021.03.05
Image Sharpness  (0) 2021.02.25
Posted by helloktk
,