Geometry & Recognition

동일한 물체나 풍경이라도 촬영에 사용된 센서의 종류나 조명 조건 때문에 사진이 더 어둡거나 반대로 더 밝게 표현될 수 있다. 이런 경우 사진을 잘 찍힌 사진과 비교하여 보정하려면 어떤 기준을 가지고 작업을 해야 할까? 동일한 내용의 영상이라면 단순히 히스토그램을 늘리거나 줄이는 과정을 (histogram stretching) 사용할 수 있다. 그러나 같은 물체나 풍경을 담지 않은 기준 영상의 히스토그램과 같은 내용의 히스토그램을 되도록 사진을 조작하고 싶으면 histogram stretching으로는 안된다. 

입력 영상의 주어진 픽셀 값이 기준 영상의 어떤 픽셀 값에 해당하게 변환을 해야 하는가를 결정해야 한다. 변환 $f$는 두 영상의 픽셀 값의 확률분포를 보존하도록 만들어진다. 입력 영상의 히스토그램 구간 $(i-1, i]$이 기준 영상의 히스토그램 구간 $(f(i-1), f(i)]$으로 변환될 때 각각 구간에서 픽셀이 나타날 확률이 동일해야 한다. 영상에서 픽셀 값은 이산적이므로 확률보다는 확률의 누적합을 이용하는 것이 더 편리하다. 입력 영상의 히스토그램 구간 $[0, i]$에서 픽셀이 나타날 누적 확률과 같은 누적 확률을 주는 기준 영상의 히스토그램 구간이 $[0, k=f(i)]$일 때 

$$i(영상)\rightarrow k = f(i) (기준영상)$$

으로 변환하면 된다. 이 과정은 히스토그램 stretching에도 그대로 적용이 된다. 누적 히스토그램(cumulative histogram)은 주어진 픽셀 값까지 확률 합을 쉽게 구할 수 있게 하는 일종의 lookup table이다. cumulative histogram의 $i$-번째 값은 픽셀 값이 $0$부터 $i$까지 히스토그램의 누적합이기 때문이다. 따라서 히스토그램 매칭(histogram matching, histogram specification)은 같은 cumulative histogram의 값을 갖는 픽셀 값 사이의 변환을 의미한다. 두  영상의 픽셀 수가 같지 않은 경우에는 cumulative histogram를 쓸 수 없다. 이 경우에는 전체 픽셀 수로 정규화시킨 cumulative distribution function(cdf)을 사용하면 된다.

히스토그램 평탄화(histogram equalization)는 각 그레이 값이 나타날 확률이 균일한 기준 영상을 (즉, 1차 cumulative histogram이 직선인 영상) 사용한 히스토그램 매칭에 해당한다. 따라서 기준 영상이 필요하지 않는다. 

//map을 lookup table로 이용해서 영상을 변환할 수 있다.
void matchHistogram(int srcHist[256], int refHist[256], int map[256]) {
    double cumSrc[256], cumRef[256];
    cumSrc[0] = srcHist[0];
    cumRef[0] = refHist[0];
    for (int i = 1; i < 256; i++) {
        cumSrc[i] = cumSrc[i - 1] + srcHist[i];
        cumRef[i] = cumRef[i - 1] + refHist[i];
    }
    // normalize ==> make CDF; 두 비교 영상이 같은 크기가 아닐 수 있으므로 필요하다;
    for (int i = 0; i < 256; i++) {
        cumSrc[i] /= cumSrc[255];
        cumRef[i] /= cumRef[255];
    }
    // 두 비교영상의 cumulant histogram이 가장 가까운(같은) 픽셀끼리 변환한다;
    for (int i = 0; i < 256; i++) {
        int k = 255;  
        while (cumRef[k] > cumSrc[i]) k--;
        // nearest interpolation; 2022.02.11
        if ((cumSrc[i] - cumRef[k]) < (cumRef[k + 1] - cumSrc[i])) map[i] = k;
        else map[i] = k + 1;
    }
};

실제 사용은 grey 이미지인 경우:

int histogramSpec(BYTE *src, int ws, int hs, BYTE *ref, int wr, int hr, BYTE *out) {
    int srcHist[256] = {0}, refHist[256] = {0}, map[256];
    makeHistogram(src, ws, hs, srcHist);
    makeHistogram(ref, wr, hr, refHist);
    matchHistogram(srcHist, refHist, map);
    for (int k = ws * hs; k-- > 0;)
        out[k] = map[src[k]];
    return 1;
}

Tarjan의 Union-Find algorithm을 이용해서 (이진) 이미지의 Connected Component Labeling을 구현한 코드이다. 이미지의 배경은 검정(0)으로 하고 전경은 0이 아닌 값이면 된다. 처음 각 전경에 해당하는 픽셀은 모두 root node로 만든다: parent 정보는 배열 label에 저장되고, root node에 대해서는 label[pos] = pos). 4방향 연결을 기준으로 하면 왼쪽(LEFT)이나 위쪽(TOP)의 픽셀과 연결이 되어 있으면 parent가 더 작은 root 번호를 갖도록 합병한다(UNION).  8-방향 연결인 경우에는 위-왼쪽(TOPLEFT), 위-오른쪽(TOPRIGHT)도 합병한다. 전체 픽셀에 대해서 조사가 끝나면 배열 label에는 각 픽셀의 root 번호가 저장된다. 자신의 위치 값이 label의 값과 같은 경우는 root 노드로 새로운 blob의 시작을 나타낸다.  label 배열에 기록된 root 번호는 합병과정에서 중간 번호가 빠질 수 있을 수 있다. 순차적 레이블링이 필요한 경우에는 배열 label을 다시 스캔해서 번호가 순차적으로 할당되도록 만든다. 

보통의 connected component labeling 알고리즘이 이미지를 두 번 스캔을 해야 하는데 반해 이 알고리즘은 한 번의 스캔만 필요하다. 물론 순차적인 레이블링을 원하면 parent table을 다시 조사해야 한다.

#define CCL_LEFT         (-1)
#define CCL_TOP          (-w)
#define CCL_TOPLEFT      (-1 - w)
#define CCL_TOPRIGHT     (1 - w)

#define CCL_BG            (-1)
// 두 노드 (a,b)를 합병함; find(and compress)와 union을 동시에;
#define UNION(a, b, label) {                    \
    int r0 = (a), r1 = (b), p;                  \
    while ((p = label[r0]) != r0) { r0 = p; }   \
    label[(a)] = p;                             \
    while ((p = label[r1]) != r1) { r1 = p; }   \
    label[(b)] = p;                             \
    if (r0 > r1)  label[r0] = r1;               \
    else          label[r1] = r0;               \
}                  
static int FindRoot(int node, int* parent) {
    if (node != parent[node]) parent[node] = FindRoot(parent[node], parent);
    return parent[node];
}
static void Union(int node1, int node2, int *parent) {
    int root1 = FindRoot(node1, parent);
    int root2 = FindRoot(node2, parent);
    if (root1 > root2) parent[root1] = root2;
    else parent[root2] = root1;
}
int ConnectedComponentLabel(BYTE *image, int w, int h, int label[]) {
    BYTE *q = &image[0] ;
    for (int y = 0, pos = 0; y < h; y++) {
        for (int x = 0; x < w; x++, pos++) {
            if (*q++) {                     // Foreground;
                label[pos] = pos;           // 초기 root = 현위치             
                if ((y > 0) && q[CCL_TOP]) 
                    UNION(pos, pos + CCL_TOP, label);         
                if ((x > 0) && q[CCL_LEFT]) 
                    UNION(pos, pos + CCL_LEFT, label);
#if defined (_EIGHTCONN_)
                if ((x + 1 < w) && (y > 0) && q[CCL_TOPRIGHT]) 
                    UNION(pos, pos + CCL_TOPRIGHT, label);
                if ((x > 0) && (y > 0) && q[CCL_TOPLEFT]) 
                    UNION(pos, pos + CCL_TOPLEFT, label);
#endif // _EIGHTCONN_
            } else 
                label[pos] = CCL_BG;        // BACKGROUND;
        }
    }
    // 합병과정에서 빈 레이블이 생길 수 있으므로 순차적 레이블을 같도록 정리(선택 사항);
    // label = -1은 배경임;
    int curlab = 0;                                // 0-부터 시작;
    for (int pos = 0 ; pos < w * h; pos++) {
        int r = label[pos];
        if (r == CCL_BG)   continue;               // background;
        else if (r == pos) label[pos] = curlab++;  // root: assign a new label;
        else               label[pos] = label[r];  // assign renewed parent's label.
    }  
    return (curlab);                               //배경 제외;
};

blog.naver.com/helloktk/ 에서 옮겼고, 출력 부분을 바꿈;

<CCL을 이용하여 DataMatrix-code를 검출하는 과정>

<20000 성분의 체스보드에 대한 4-방향 연결 테스트;>

출력은 정수형으로 바꾸어야 한다.  8-방향 연결로 하면 1개 성분만 나온다.