Geometry & Recognition

영상처리에서 한 픽셀의 수정을 위해서 주변 픽셀의 정보를 요구하는 윈도 기반 필터들은 일반적 연산 비용이 큰 편이다. 한 변의 길이가 W인 윈도를 사용할 때  W^2 횟수의 픽셀을 참조해야 하므로 윈도가 클수록 그 비용은 제곱으로 증가한다. 선형 필터 중에는 x-방향과 y-방향 연산으로 각각 분리가 가능한 경우는 연산 비용이 필터의 크기에만 비례하도록 만들 수 있다. median 필터는 이런 분리가 안 되는 비선형 필터 중 하나다. 근사적으로 x-방향으로 median filtering을 하고, 그 결과를 y-방향으로 다시 median filtering을 하는 방법으로 연산을 줄이는 방법을 사용하기도 한다.   

윈도가 움직이면서 윈도 내 모든 픽셀이 다 바뀌는 것이 아니라 움직이는 방향에 수직인 가장자리 픽셀만 바뀐다는 사실을 이용하면 각 픽셀의 윈도에서 median을 찾는 작업을 할 필요가 없다. 예를 들면 scanline 방향(x-방향)으로 윈도를 움직이면서 median filter를 작용할 때, 윈도가 오른쪽으로 1 픽셀 움직이면 윈도의 왼쪽 가장자리의 수직 픽셀들은 새 윈도에서 사라지고, 기존 윈도의 오른쪽 수직 가장자리 앞의 픽셀들이 새로 들어온다. 따라서 각 스캔라인에서 처음 한 번만 윈도의 median을 찾으면 이후에는 윈도가 이동할 때 윈도를 나가는 픽셀과 새로 들어오는 픽셀 (2*W) 개에 대해서 이전 median과 비교만 하면 된다. 이 방법은 비교 횟수가 윈도 크기에 1차적으로 비례하므로 연산 부담을 많이 줄일 수 있다. 이 방법은 사각형 모양의 윈도를 가지는 다른 필터(mean filter, max-filter, min-filter,...)에 대해서도 쉽게 적용할 수 있다.

// boundary region도 처리할 수 있게 수정함; 2021-04-18;
// window size = wx * wy;
// median = argmin(hist[i] >= halfArea)
int RunningMedianFilter(BYTE* image, int w, int h, int wx, int wy, BYTE* out) {
    int hist[256], x;
    int wxhalf = wx >> 1;
    int wyhalf = wy >> 1;
    wx = (wxhalf << 1) + 1;  // size of window = odd number;
    wy = (wyhalf << 1) + 1;
    for (int y = 0, yw = 0; y < h; ++y, yw += w) {
        // calc available area;
        int wystart = max(0, y - wyhalf);
        int wystop  = min(h, y + wyhalf);
        int wysize  = wystop - wystart + 1;
        int wxstart  = 0;
        int wxstop   = wxhalf;
        int halfArea = (wxstop * wysize + 1) >> 1;
        // to avoid *w multiplication in y-step;
        wystart *= w; 
        wystop  *= w;
        // initial histogram of topleft window;
        memset(hist, 0, 256 * sizeof(int));
        for (int iy = wystart; iy <= wystop; iy += w) 
            for (int ix = wxstart; ix <= wxstop; ++ix) hist[image[iy + ix]]++;
        // find initial median;            
        int ltmed = hist[0];       // less_than_median;
        int med = 0;
        while (ltmed < halfArea) ltmed += hist[++med];  
        out[yw + 0] = med;
        // left edge rgn;
        for (x = 1; wxstop < wx; ++x) {
            ++wxstop;
            halfArea = (wxstop * wysize + 1) >> 1;
            for (int iy = wystart; iy <= wystop; iy += w) {
                int v = image[iy + wxstop];     // (x=wxstop) strip enters;
                ++hist[v];
                if (v <= med) ++ltmed;
            }
            while (ltmed >= halfArea) ltmed -= hist[med--];  
            while (ltmed < halfArea)  ltmed += hist[++med];  
            out[yw + x] = med;
        }
        // central rgn;
        for ( ; wxstop < w; ++x) {
            ++wxstop;
            for (int iy = wystart; iy <= wystop; iy += w) {
                int v = image[iy + wxstart];    // (x=wxstart) strip leaves;
                --hist[v];
                if (v <= med) --ltmed;
                v = image[iy + wxstop];         // (x=wxstop) strip enters;
                ++hist[v];
                if (v <= med) ++ltmed;
            }
            ++wxstart;
            while (ltmed >= halfArea) ltmed -= hist[med--];
            while (ltmed < halfArea)  ltmed += hist[++med];
            out[yw + x] = med;
        }
        // right edge rgn;
        for ( ; x <= w; ++x) {
            for (int iy = wystart; iy <= wystop; iy += w) {
                int v = image[iy + wxstart];  // (x=wxstart) strip leaves;
                --hist[v];
                if (v <= med) --ltmed;
            }
            ++wxstart;
            halfArea = ((wxstop - wxstart + 1) * wysize + 1) >> 1;
            while (ltmed >= halfArea) ltmed -= hist[med--];
            while (ltmed < halfArea)  ltmed += hist[++med];
            out[yw + x] = med;
        }
    }
    return 1;
};

wx=wy=7;

아래 그림은 손 모양의 ASM을 이용해서 영상에서 손의 형상을 찾는 과정을 보여준다. 영상의 적당한 지점에 초기 손 모양을 설정하고, 이 설정된 손 모양의 경계에서 수직방향으로 에지를 찾아서 새로운 손 모양을 구성한다. 에지 찾기로 찾은 손 모양은 잘못된 에지 정보로 인해서 손 모양에서 크게 일그러진 형태를 나타낸다(그림에서 초록색 선이 에지 찾기로 찾은 손 모양이다). 이 찾은 결과를 훈련된 손 모양을 이용해서 다시 재구성하면 일그러진 손 모양이 보정이 된다(그림에서 붉은색 선이 재구성한 손 모양이다). 이러한 보정은 다음번 에지 찾기에서 출발점으로 쓰이고, 전체적으로 손 모양이 훈련된 손 모양 이상으로 많이 찌그러지지 않도록 하는 역할을 한다. 
손 모양 찾기의 전체적인 과정은 초기에 손 모양 데이터를 어디에 놓고 얼마만 한 크기로 놓는가에 많이 의존한다. 그리고, 좋지 않은 초기 위치는 찾는 시간을 길게 할 뿐만 아니라, 잘못된 결과를 유도하기도 한다. 이것을 개선하기 위해서 보통은 이미지의 피라미드 구조를 이용해서, 처음 단계에서는 대충 찾고, 점차로 자세히 찾는 과정을 반복한다.
여기서는 손의 이미지를 이진화시켜서 사용했기 때문에 이러한 피라미드 구조는 사용하지 않았다. 이진 영상을 사용하지 않을 때는 훈련용 손영상의 경계에서 수직방향으로의 그레이 값의 프로파일 정보를 훈련시켜서 사용할 수 있다.

* 18개의 훈련용 손 모양을 가지고 얻은 12개의 eigen mode을 씀.
* data 출처:

http://personalpages.manchester.ac.uk/staff/timothy.f.cootes/data/hand_data.html

특정한 eigenface를 평균 얼굴에 적당한 가중치를 주어서 더하면 그 eigenface가 얼굴에 어떤 변화를 주는지를 알아볼 수 있다. 아래의 결과는 가장 큰 eigenvalue를 갖는 6개의 eigenface들에 대해서

-2 * sqrt(eigenvalue) <=  가중치 <= +2 * sqrt(eigenvalue)

사이의 가중치값을 17단계로 변화시키면서 영상의 변화를 본 것이다.

얼굴영상 = 평균 얼굴 + 가중치 * eigenface

일반적인 얼굴영상은 여러 eigenface들의 가중치를 준 조합으로 만들어진다.

아래의 사진을 보면 처음 3개의  eigenface는 영상에서 조명의 변화를 주로 나타내고, 이후의 3개는 얼굴형의 변화를 주로 표현한다. 실제로 eigenface를 사용할 때는 처음 몇 개의 큰 고유치를 갖는 eigenface를 버리고 사용하여서 조명 변화에 따른 영상의 변화를 일정 정도 보상할 수 있다.
Y.Moses, Y.Adini, S.Ullman, "Face Recognition: The Problem of Compensating for changes in Illumination Direction", 1994

영상에 물체의 윤곽을 찾고자 할 때 active snake 알고리즘을 많이 이용한다. 이것은 물체의 윤곽에서 명암의 차이를 이용하여 윤곽선을 탄성이 있는 곡선으로 근사 시키는 방법이다. 그러나 실제의 영상에는 조명의 영향이나 잡음 아니면 다른 물체에의 한 가려짐으로 인해서 윤곽이 명확하게 나타나지 않거나 가려져서 윤곽선을 제대로 찾지 못하거나 심하게 왜곡된 윤곽선을 낳는 결과를 초래한다. 영상에서 윤곽선을 찾는 경우에 특정한 물체(예를 들면 영상에서 얼굴 윤곽, 손 모양, 초음파 사진에서 장기의 모양...)를 대상으로 하는 경우가 많다. 이 경우 대상 물체의 대략의 형태가 알려져 있고, 실제로 사진에 나타나는 형태는 평균적인 형태에서 많이 벗어난 있지 않는다. 이러한 정보를 이용하면 보다 쉽게 물체의 윤곽선을 찾을 수 있다.

먼저 찾고자 하는 물체의 윤곽 정보를 훈련을 시켜 평균 윤곽선과 평균 윤곽선에서 벗어남을 기술하는 독립적인 mode(=eigen mode=eigen shape)를 알아낸다. 이것은 얼굴인식에서 PCA 기법을 이용하여서 평균 얼굴영상에서 변화를 주는 eigen mode인 eigenface를 찾는 기법과 같다. Eigen mode는 평균 윤곽선에서 아주 미세한 변화는 버리고, 큰 것만 취하면 된다. 

이러한 eigen mode를 이용하면 잡음이나 조명 가려짐 등에 의해 잘못 찾은 윤곽선을 보정하여서 원하는 형태를 유지할 수 있다. 즉, 영상처리에 의해서 찾은 윤곽선을 eigen mode로 분해하면 각 eigen mode의 가중치를 구할 수 있는데, 이렇게 구한 가중치를 준 eigen mode를 평균 윤곽선에 더해서 윤곽선을 재구성한다. 이 재구성된 윤곽선은 잡음이나 가려짐 등의 영향으로 인한 미세한 왜곡을 없앨 수 있다. 그리고, 윤곽선 찾기를 반복적인 과정으로 구현할 때 이 재구성된 윤곽에서 출발하여 다음번의 윤곽선 찾기를 시도한다. 그러나 이 방법은 eigen mode가 훈련에 사용한 영상에 많이 의존하므로, 훈련된 윤곽과 많이 다른 윤곽은 제대로 대처하지 못한다.

아래 그림(검정선)은 영상처리에서 찾은 손 윤곽선으로 잡음으로 인해서 왜곡이 많이 되어 있는 모양이다. 빨간 선은 eigen mode를 이용해서 재구성한 윤곽선이다.

* 18개의 훈련용 손 모양을 가지고 얻은 12개의 eigen mode을 씀.
* data 출처: ttp://personalpages.manchester.ac.uk/staff/timothy.f.cootes/data/hand_data.html