Chamfer Match

주어진 영상에 특정 물체가 포함되어 있는지를 확인하려면, 먼저 그 물체의 템플릿을 준비한 뒤 이를 영상 위에 겹쳐 놓고 픽셀 단위로 이동시키면서 각 위치에서의 일치 정도를 계산하면 된다. 일반적으로는 템플릿과 영상 사이의 상관계수를 이용하여 일치 여부를 판단한다.

대상 영상이 이진 영상인 경우에는 distance map을 이용하면 매칭 문제를 더욱 효율적으로 해결할 수 있다. 에지 영상으로부터 생성한 distance map은 영상의 각 픽셀에서 가장 가까운 에지까지의 거리를 저장하고 있다. 따라서 매칭하려는 템플릿의 이진 영상을 distance map 위에서 픽셀 단위로 이동시키면서, 템플릿의 각 픽셀 위치에서 distance map이 제공하는 거리값을 모두 합하면 된다. 이 거리의 총합이 가장 작은 위치가 템플릿과 가장 잘 일치하는 위치가 된다.

이와 같은 매칭 기법을 Chamfer Matching이라고 한다. Chamfer Matching은 모델과 대상 영상 사이에 회전이나 크기 변화가 없을 때 우수한 성능을 보인다. 크기 변화가 있는 경우에는 여러 스케일에서 탐색하는 스케일 공간(scale space) 기법을 적용할 수 있다. 또한 모델의 형태가 변형될 가능성이 있는 경우에는 변형된 여러 모델을 미리 준비한 뒤 각각에 대해 매칭을 수행해야 한다.

Chamfer Matching은 distance map만 한 번 계산해 두면 이후의 매칭 과정은 단순한 거리값의 합을 계산하는 것만으로 이루어지므로 계산 비용이 매우 낮다는 장점이 있다. 또한 distance map의 거리값을 일정한 최대값으로 제한하면 일부 outlier의 영향을 줄일 수 있어 보다 robust한 매칭 결과를 얻을 수 있다.

* procedure:

1. 입력영상의 에지영상을 구함.
2. 입력영상의 에지영상의 distance map을 구함.
3. 매칭과정을 실행.

int GetAddressTable(BYTE *subImg, int w, int h, int stride/*=원본이미지 폭*/, int addr[]);

//계산을 보다 빠르게 하기 위해서 subimg에서 template 위치를(distimg에 놓인 경우) 미리 계산함.
int GetAddressTable(BYTE *subImg, int w, int h, int stride/*=원본이미지 폭*/, int addr[]) {
    for(int y=0, k=0; y<h; y++) {
        for(int x=0; x<w; x++){
            if(subImg[y*w+x])
                addr[k++]= y*stride + x ; //template가 dist이미지에서움직일 때 픽셀위치(상대적);
        }
    }
    return (k);    //# of template pixels<= w*h;
}

Matching code;
void ChamferMatch(float* distImg, int w1, int h1,   //distance-map;
                  BYTE* subImg, int w2, int h2,     //template-map;
                  float *match/*[w1 * h1]*/) {      //match_score-map(filled with FLT_MAX)
    int umax = w1 - w2;
    int vmax = h1 - h2;
    int uc = w2 / 2;      //center_x of template-map;
    int vc = h2 / 2;      //center_y of template-map;
    int *addr = new int [w2 * h2]; //max;
    int n = GetAddressTable(subImg, w2, h2, w1, addr) ;
    for (int v = 0; v <= vmax; v += 2){           //to speed-up;
        for (int u = 0; u <= umax; u += 2){       //to speed-up;
            double score=0;
#if (0)
            for (int v1 = v, v2 = 0; v1 < h1 && v2 < h2; v1++, v2++){
                int i1 = v1 * w1;
                int i2 = v2 * w2;
                for (int u1 = u, u2 = 0; u1 < w1 && u2 < w2; u1++, u2++) {
                    if (subImg[i2 + u2])
                        score += distImg[i1 + u1]; // truncate [0, th_dist];
                }
            }           
#else 
            int offset = v * w1 + u; //start address;
            int i = n;
            while(i--) score += distImg[addr[i] + offset];
#endif
            //at the center of subimg;
            match[(uc + u) + (vc + v) * w1] = score; 
        }   
    }   
    delete[] addr ;
};

입력영상의 에지영상(모델이미지를 포함, 에지를 1픽셀로 조절하지 않았음)

 

모델영상:

 distance map에서 찾은 위치에 template를 오버랩함;