이번 글에서는 영상인식에 사용되는 대표적인 몇몇 영상 feature들을 비교 정리해 볼까 합니다. 여기서 다룰 영상 feature들은 SIFT, HOG, Haar, Ferns, LBP, MCT 입니다. 주로 HOG, Haar, LBP 등 성격이 다른 여러 영상 feature의 특성을 파악하는데 초점이 맞추어져 있고 invariant local feature와의 비교를 위해 가장 대표적인 SIFT도 포함하였습니다. SURF, BRIEF, ORB 등 기타 invariant local feature들에 대해서는 나중에 별도 글로 다뤄볼 예정입니다.

이 글은 각각의 영상 feature의 세부 구현이나 특징을 열거하기보다는 전체적인 관점에서 각각의 위치와 특성을 파악하는 것이 목적이며 글은 최대한 간결하게 쓰고자 합니다.

1. SIFT(Scale Invariant Feature Transform)

[Lowe04] Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints”, IJCV 2004.

SIFT는 영상에서 코너점 등 식별이 용이한 특징점들을 선택한 후에 각 특징점을 중심으로 한 로컬 패치(local patch)에 대해 아래 그림과 같은 특징 벡터를 추출한 것을 말한다.

<그림 1>

SIFT 특징벡터는 특징점 주변의 영상패치를 4 x 4 블록으로 나누고 각 블록에 속한 픽셀들의 gradient 방향과 크기에 대한 히스토그램을 구한 후 이 히스토그램 bin 값들을 일렬로 쭉 연결한 128차원 벡터이다.

SIFT는 기본적으로 특징점 주변의 로컬한 gradient 분포특성(밝기 변화의 방향 및 밝기 변화의 급격한 정도)을 표현하는 feature이다. SIFT를 포함한 SURF, ORB 등의 local feature들은 대상의 크기변화, 형태변화, 방향(회전)변화에 강인하면서도 구분력이 뛰어난 어찌보면 서로 상충되는 목표를 동시에 만족시키고자 개발된 것들로서 통상적으로 원래 물체의 기하학적 정보는 무시하고 특징점 단위로 혹은 코드북(code book) 단위로 매칭을 수행한다. 이러한 local feature들은 스케일, 회전, 밝기변화에 대한 불변 특징을 위해 어느정도 구분력을 희생하기 때문에 하나의 특징점에 대해 수많은 특징점들이 매칭될 수 있으며 feature 자체의 성능보다는 어떤 매칭 방법을 사용했으냐에 따라서 최종 성능이 크게 좌우될 수 있다.

2. HOG(Histogram of Oriented Gradient)

[Dalal05] N. Dalal and B. Triggs, "Histograms of oriented gradients for human detection," CVPR 2005.

HOG는 대상 영역을 일정 크기의 셀로 분할하고, 각 셀마다 edge 픽셀(gradient magnitude가 일정 값 이상인 픽셀)들의 방향에 대한 히스토그램을 구한 후 이들 히스토그램 bin 값들을 일렬로 연결한 벡터이다. 즉, HOG는 edge의 방향 히스토그램 템플릿으로 볼 수 있다.

<그림 2>

템플릿 매칭(template matching)의 경우에는 원래 영상의 기하학적 정보를 그대로 유지하며 매칭을 할 수 있지만 대상의 형태나 위치가 조금만 바뀌어도 매칭이 잘 안되는 문제가 있다. 반면에 히스토그램 매칭은 대상의 형태가 변해도 매칭을 할 수 있지만 대상의 기하학적 정보를 잃어버리고 단지 분포(구성비) 정보만을 기억하기 때문에 잘못된 대상과도 매칭이 되는 문제가 있다.

HOG는 템플릿 매칭과 히스토그램 매칭의 중간 단계에 있는 매칭 방법으로 볼 수 있으며 블록 단위로는 기하학적 정보를 유지하되, 각 블록 내부에서는 히스토그램을 사용함으로써 로컬한 변화에는 어느정도 강인한 특성을 가지고 있다.

또한 HOG는 edge의 방향정보를 이용하기 때문에 일종의 edge기반 템플릿 매칭 방법으로도 볼 수 있다. Edge는 기본적으로 영상의 밝기 변화, 조명 변화 등에 덜 민감하므로 HOG 또한 유사한 특성을 갖는다고 생각할 수 있다. 또한 HOG는 물체의 실루엣(윤곽선) 정보를 이용하므로 사람, 자동차 등과 같이 내부 패턴이 복잡하지 않으면서도 고유의 독특한 윤곽선 정보를 갖는 물체를 식별하는데 적합한 영상 feature이다.

HOG를 local feature인 SIFT와 비교해 보면 HOG는 일종의 템플릿 매칭이기 때문에 물체가 회전된 경우나 형태변화가 심한 경우에는 검출이 힘들지만 SIFT는 모델의 특징점과 입력 영상의 특징점에 대해 특징점 단위로 매칭이 이루어지기 때문에 물체의 형태변화, 크기변화, 회전 등에 무관하게 매칭이 이루어질 수 있다. 이러한 특성에 비추어 보았을 때, HOG는 물체의 형태변화가 심하지 않고 내부 패턴이 단순하며 물체의 윤곽선으로 물체를 식별할 수 있을 경우에 적합하고 SIFT는 액자 그림과 같이 내부 패턴이 복잡하여 특징점이 풍부한 경우에 적합한 방법이다.

3. Haar feature

[Viola01] P. Viola and M. J. Jones, "Rapid Object Detection using a Boosted Cascade of Simple Features," CVPR 2001.

Haar feature는 기본적으로 영상에서의 영역과 영역의 밝기차를 이용한 feature로서 아래 왼쪽 그림과 같이 다양한 형태의 elementary feature들이 존재하며 이들 elementary feature들을 다수(수백, 수천개) 조합하여(다양한 위치와 크기로) 물체에 대한 특징을 추출하는 방법이다.

<그림 3>

각 elementary feature에 대한 특징값은 feature의 흰색 부분에 해당하는 영상 픽셀들의 밝기합에서 검은색 부분의 밝기 합을 뺀 차로 계산된다. 그리고 feature를 이용한 대상의 식별은 계산된 영역의 밝기차가 feature에 부여된 임계값(threshold)보다 큰지 작은지 여부를 이용한다. 물론 하나의 feature를 사용하는 것이 아니라 다수의 feature를 조합하여 사용하게 되며 예를 들어 사용한 feature가 f1, f2, ..., fn이라면 f1<t1이고 f2<t2이고 f3>t3, ... fn<tn을 만족하면 대상물체이고 만족하지 않으면 배경이라고 판단하는 식이다.

같은 종류의 feature라 할지라도 물체 내에서의 위치 및 크기(scale)에 따라 서로 다른 feature로 간주하기 때문에 거의 무한대에 가까운 feature 조합이 가능하다. 이들 중 의미있는 feature들을 선정하는 것이 중요한데 여기서 의미있는 feature란 인식하고자 하는 대상들에서는 비슷한 값을 나타내면서 대상이 아닌 경우에는 랜덤한 값을 내는 feature들로 볼 수 있다. 예를 들어, 위 그림 3의 오른쪽 그림과 같이 사람의 눈 영역에 대해 feature를 잡으면 눈 영역은 대체로 주변보다 어둡기 때문에 사람 얼굴 검출을 위한 의미있는 feature가 된다. 물론 이러한 의미있는 feature의 선정은 수작업이 아닌 boosting 알고리즘 등과 같이 자동화된 학습 알고리즘을 통해 이루어진다.

이와 같이 Haar feature는 영역간의 밝기차를 이용하기 때문에 Haar feature를 적용하기 위해서는 검출하고자 하는 대상 물체가 이러한 특성에 잘 부합되는지를 따져 보아야 한다. 사람의 얼굴의 경우에는 눈썹, 눈동자, 입술, 머리카락 등이 특징적인 밝기 차를 가지기 때문에 Haar feature를 적용하기에 비교적 적합한 대상으로 볼 수 있다. 또한 체스판의 경우에도 Haar feature를 적용하기 매우 적합한 대상으로 볼 수 있다. 하지만 장기판이나 바둑판의 경우에는 영역에 따른 밝기차가 거의 없기 때문에 일반 벽 등과 구분할 수 없으며 Haar feature를 적용하기 힘든 예로 볼 수 있다.

Haar feature는 기본적으로 물체의 기하학적 정보를 유지하며 영역 단위의 밝기차를 이용하기 때문에 영역 내부에서의 물체의 형태변화 및 약간의 위치변화를 어느정도 커버할 수 있는 특성을 갖는다. 하지만 영상의 contrast 변화, 광원의 방향 변화에 따른 영상 밝기 변화에 영향을 받으며 물체가 회전된 경우에는 검출이 힘들다.

4. Ferns

[Ozuysal10] M. Ozuysal, M. Calonder, V. Lepetit, P. Fua, "Fast Keypoint Recognition using Random Ferns", PAMI 2010.

Ferns는 영상에서 먼저 특징점들을 뽑고 각 특징점을 중심으로 한 로컬 패치(local patch)에 대해 계산된다는 점에서 SIFT와 유사한 점이 있다 (ferns에 대한 상세 내용은 Ferns를 이용한 영상 Object Detection 글 참조).

이후 patch 내에서 임의의 두 점을 잡고 두 점의 픽셀 밝기차가 +인지 -인지를 feature로 사용한다. Haar feature와 비교해 보면 Haar feature가 영역 단위의 밝기차를 이용하는 반면 ferns는 픽셀 단위의 밝기차를 이용하고 또한 값이 아닌 부호만을 사용한다는 점에서 차이가 있다.

<그림 4>

하나의 ferns feature는 patch 내에서의 한쌍의 좌표로 표현되며 하나의 feature에 대한 결과는 0 또는 1의 값을 갖는다. 패치 내에서 여러 개의 feature가 사용될 경우 그 결과는 각 feature의 결과를 이진수로 연결한 값을 사용한다. 예를 들어 위 그림 4의 두번째 경우와 같이 3개의 feature를 사용하면 그 결과값은 000, 001, 010, 011, ..., 111까지 총 8가지 값이 가능하다.

정리해 보면 ferns는 패치(patch) 단위의 매칭을 위한 영상 feature로서, 로컬한 영상 패치의 밝기 패턴을 표현하는 feature이다. 밝기값을 그대로 이용하는 것이 아닌 밝기차의 부호 정보만을 이용하기 때문에 영상의 contrast 변화, 밝기 변화 등에 강인할 것으로 생각된다.

SIFT와 비교해 보면 둘다 로컬한 영상 패치에 대한 feature라는 점에서는 유사하지만 SIFT는 히스토그램이라는 측면이 강하고 ferns는 템플릿이라는 측면이 강하다. 따라서 ferns가 SIFT 보다 구분력은 높지만 패치의 형태가 변하거나 회전된 경우에는 매칭이 힘든 측면이 있다. 이를 보완하기 위해 ferns에서는 대상을 학습시킬 때 패치에 회전, 이그러짐 등의 변형을 가하여 학습 데이터를 확장하여 이용하는 방법을 사용한다.

Ferns와 SIFT는 feature 자체는 다르지만 로컬 패치에 대한 feature라는 점과 패치 단위의 매칭을 이용한다는 점에서 유사하며 응용에 있어서는 상호 대체적으로 사용될 수 있다. 개인적인 경험에 의하면 성능은 fern이  훨씬 뛰어난 편이다(인식 성능은 약간 더 뛰어나며 속도는 훨씬 빠름). 하지만 SIFT는 별도의 학습 과정이 필요 없는 대신에 ferns는 파라미터 설정에 따라서 수십분 이상의 offline 학습 과정이 필요한 단점이 있다.

5. LBP(Local Binary Pattern)

[Ojala96] Ojala, T., Pietikäinen, M. and Harwood, D., A Comparative Study of Texture Measures with Classification Based on Feature Distributions. Pattern Recognition 29(1):51-59, 1996.

[Ahonen06] T. Ahonen, A. Hadid, and M. Pietikinen, "Face description with local binary patterns: Application to face recognition," PAMI 2006.

[Liao07] S. Liao, X. Zhu, Z. Lei, L. Zhang and S. Z. Li, "Learning Multi-scale Block Local Binary Patterns for Face Recognition," ICB 2007.

LBP는 원래 영상의 텍스쳐(texture)를 분류하기 위한 용도로 개발된 feature인데 이후 얼굴인식(face recognition)과 같은 다른 영상인식 응용에도 활용되고 있다.

LBP(Local Binary Pattern)는 영상의 모든 픽셀에 대해 계산되는 값으로서 각 픽셀의 주변 3 x 3 영역의 상대적인 밝기 변화를 2진수로 코딩한 인덱스 값이다 (중앙 픽셀보다 밝으면 1, 어두우면 0으로 코딩한 후 이 값들을 연결한 이진수를 로컬 텍스쳐에 대한 인덱스로 활용)

<그림 5> 출처: [Ahonen06]

이와 같이 각 픽셀들에 대해 계산된 인덱스 값에 대해 히스토그램을 구한 후 이 히스토그램을 해당 영상 영역에 대한 텍스쳐 모델로 활용하는 것이 원래의 LBP 응용이다(잔디밭인지, 숲인지, 땅인지, 벽인지 등 텍스쳐를 분류하는 용도).

이후 LBP를 얼굴인식에 활용한 한 예[Ahonen06]를 보면 얼굴 영역을 일정한 크기의 셀로 분할한 후 각 셀(cell)마다 LBP에 대한 히스토그램을 구하고(해당 셀에 속하는 LBP 인덱스 값들에 대한 히스토그램) 이렇게 구한 히스토그램들을 일렬로 연결한 벡터를 최종 feature로 사용하는 방법 등이 있다 (이 방법은 일종의 텍스쳐 템플릿 매칭 방법으로 볼 수 있는데 셀 단위로는 대상의 기하학적 정보를 유지하되 셀 내에서는 텍스쳐 정보만을 추출하는 형태이다).

<그림 6> 출처: http://www.scholarpedia.org/article/Local_Binary_Patterns

이후 2007년도에는 MB-LBP라는 Mult-scale Block LBP 방법[Liao07]이 발표되었는데, 이 방법은 원래의 LBP가 3x3 픽셀을 이용함으로써 너무 local 특성을 추출하기 때문에 이를 블록으로 확장하여 블록 단위로 LBP를 계산하고자 하는 것으로서 OpenCV에 있는 LBP는 MB-LBP를 기반으로 하고 있다.

<그림 7> 출처: [Liao07]

즉, MB-LBP는 임의의 크기의 영상 영역을 3 x 3 블록으로 분할한 후 각 블록평균에 대해 LBP 인덱스를 계산하는 방법이다. 이와 같이 픽셀 단위가 아닌 블록 단위의 LBP를 사용하면 큰 스케일의 텍스쳐 정보를 추출할 수 있으며 서로 다른 여러 스케일 및 영상 위치에 대해 MB-LBP를 계산하면 하나의 대상에 대해 다양한 feature를 추출할 수 있다는 것이다. 이와 같이 하면 하나의 대상에 대해 무수하(거의 무한대) 많은 LBP feature를 추출할 수 있는데, 이들 중 의미있는(식별력이 높은) LBP feature들을 자동으로 선정하기 위해 AdaBoost와 같은 학습 알고리즘이 적용된다.

LBP 특징에 대해 살펴보면 LBP는 기본적으로 circular texture 정보로서 영상의 밝기 변화에 무관한 영상 feature로 볼 수 있다. 기존의 대부분의 LBP 응용은 검출(detection)이 아닌 인식(recognition) 용이었지만 detection 관점에서 봤을 때 LBP의 활용을 생각해 보면 어느정도 내부 패턴이 존재하는 물체를 검출하는데 적합해 보인다. 기본적인 특성은 Haar feature와 큰 차이가 없으나 다만 Haar보다는 좀더 복잡한(세밀한) 패턴 변화를 표현할 수 있다. 따라서, Haar와 LBP는 서로 대체적으로 사용될 수 있으며 성능상의 큰 차이는 없을 것으로 생각되지만 실제 대상의 내부 패턴 분포가 어떤 feature와 좀더 적합한지 따져보고 선택하는 것이 좋겠다.

참고로, LBP는 1996년 Ojala 논문(Ojala, T., Pietikäinen, M. and Harwood, D., A Comparative Study of Texture Measures with Classification Based on Feature Distributions. Pattern Recognition 29(1):51-59, 1999 )이 최초 originality를 인정받고 있으며 이후 Ojala는 2002년에 기존의 3 x 3 LBP를 임의의 크기의 circular 형태로 계산 가능하도록 확장한 방법을 발표하였다(Ojala, T., Pietikäinen, M. and Mäenpää, T., Multiresolution Gray-scale and Rotation Invariant Texture Classification with Local Binary Patterns. IEEE Trans. Pattern Analysis and Machine Intelligence 24(7): 971-987, 2002).

6. MCT(Modified Census Transform)

[Zabih96] Ramin Zabih and John Woodfill, "Non-parametric Local Transforms for Computing Visual Correspondence," ECCV 1994.

[Froba04] Bernhard Froba and Andreas Ernst, “Face Detection with the Modified Census Transform”, FG 2004.

MCT는 현재 얼굴 검출(Face Detection) 분야에서 가장 대표적인 방법으로서 사용되고 있으며 뛰어난 검출 성능을 보이고 있다.

MCT는 Modified Census Transform의 약자로서 Census Transform(CT)을 약간 수정한 것이다. Census Transform(CT)은 1994년 Zabih와 Woodfill에 의해 제안된 방법으로서 영상에서 한 픽셀에 대한 CT는 그 픽셀 주변영역의 밝기 변화를 중심픽셀보다 밝으면 0, 어두우면 1로 인코딩하고 그 결과를 비트 스트링(bit string)으로 연결한 값이다. 따라서, 만일 주변 영역을 3 x 3 영역으로 잡는다면 어떤 픽셀에 대한 Census Transform(CT) 결과는 앞서 설명한 LBP(Local Binary Pattern)와 동일하다고 봐도 무방하다.

사실 Census Transform(CT)는 LBP(Local Binary Pattern)와 이름만 다를 뿐 내용상으로는 전혀 차이가 없다. 재미있는 사실은 LBP는 1996년 Ojala가 제안하였고[Ojala96] Census Transform(CT)도 같은 해인 1996년 Zabih가 제안하였으니[Zabih96] 똑같은 개념이 같은 년도에 서로 다른 이름으로 발표된 셈이다.

굳이 차이를 찾자면 두 feature가 사용된 컨텍스트(context)의 차이인데 LBP의 경우에는 영상의 텍스쳐(texture)를 표현하기 위한 feature로서 접근한 것으로서 LBP 결과값들에 대한 히스토그램을 영상 영역에 대한 텍스쳐 feature로서 활용하였고, Census Transform(CT)에서는 입력 영상을 주변 밝기 변화에 대한 영향이 제거된 영상으로 변환하기 위한 용도로 사용되었다. 매칭 방법에 있어서도 차이가 있는데, LBP에서는 히스토그램간의 유사도를 측정하였고 Census Transform(CT)에서는 대응되는 픽셀들 사이의 CT 비트 스트링(bit string)의 Hamming distance를 이용하였다.

Census Transform(CT)은 2004년 Froba에 의해 MCT(Modified Census Transform)[Froba04]로 확장되었는데, MCT는 중심 픽셀과의 밝기차를 인코딩하는 대신에 로컬 영역의 평균과의 밝기차를 인코딩함으로써 중심 픽셀에도 0 또는 1의 값을 부여할 수 있도록 한 것이다 (결과적으로 중심 픽셀에 대응하는 비트가 하나 더 늘어난 셈). 이렇게 함으로서 기존의 CT보다는 훤씬 풍부한 local binary pattern을 표현할 수 있도록 한 것이다. 참고로, LBP의 경우에도 동일한 해인 2004년에 평균과의 차를 이용한 형태로 확장된 ILBP(Improved LBP)(H. Jin, Q. Liu, H. Lu and X. Tong, “Face detection using improved LBP under bayesian framework”, International Conference on Image and Graphics 2004)가 독립적으로 발표되었는데 우연치고는 참 대단한 우연이다.

<그림 8>출처: [Froba04]

위 그림은 입력 영상을 MCT로 변환한 예를 보여주는데, 원본 영상들 사이에는 조명에 따른 심각한 차이가 있지만 MCT 결과 영상에서는 이러한 차이가 제거되고 순수한 물체의 패턴 정보만이 남은 것을 볼 수 있다 (MCT 영상은 각 픽셀에서 계산되는 local binary pattern에 대한 이진 비트 스트링을 gray scale로 해석하여 영상화한 것). 이와 같이 MCT로 변환한 영상에 대해 인식 또는 검출 알고리즘을 적용하면 원본 영상에서보다 성능이 나아질 것이라는게 저변에 깔린 기본 아이디어이다.

사실 MCT는 LBP와 동일한 feature이기 때문에 그 응용이나 특성도 모두 동일하다고 보면 된다. 다만 face detection 분야에서 MCT가 활용되는 방식을 좀더 살펴보면 [Froba04]에서는 얼굴내 한 픽셀 위치에 대하여 face 학습 이미지들로부터 계산된 MCT 인덱스들의 히스토그램 H1과 non face 학습 데이터들로부터 계산된 MCT 인덱스들의 히스토그램 H2를 구한 후 입력 영상의 해당 픽셀 위치에서 계산된 MCT 인덱스에 대응하는 bin값이 H1이 큰지, H2가 큰지에 따라서 해당 픽셀이 face 픽셀인지 non face 픽셀인지를 분류한다. 각 픽셀 위치에서 계산된 두 히스토그램간의 overlap(intersection)이 적을수록 구분력이 뛰어나기 때문에 overlap 정도에 따라서 각 픽셀 위치에 대한 가중치(weight)를 다르게 줄 수 있다.

7. 마무리하며..

세부 구현은 조금씩 차이가 있지만 Ferns, Haar, LBP, MCT는 서로 유사한 계열로 모두 영역간의 밝기차를 이용한다. 반면 HOG, SIFT는 기본적으로 edge 정보를 이용한다는 점에서 차이가 있으며 서로 상보적인 관계에 있다고 볼 수 있다. 어떤 문제에는 어떤 feature를 써야한다라고 한마디로 단정지을 수는 없지만 어떤 문제가 주어졌을 때 대상 물체의 특성을 잘 살펴보고 또 여러 후보 feature들의 특성과 잘 비교해 보면 feature를 선택하는데 많은 도움이 되리라 생각한다.

☞ 글의 내용은 주로 저의 주관적인 생각, 판단을 정리한 것이기 때문에 틀린 부분이 있을 수 있음을 참고하시기 바랍니다.

by 다크 프로그래머

영상처리에서의 이진화를 주제로 몇몇 알고있는 내용들을 정리해 봅니다.

영상처리에서 이진화(binarization)는 매우 간단한 연산중의 하나이지만 단순한 만큼 쉽지 않은 문제이기도 합니다.

알다시피 이진화 문제는 two class classification 문제로서 0 아니면 1, 흑 아니면 백, 모 아니면 도(?) 와 같이 대상을 일괄적으로 둘 중 하나의 값으로 분류해 버리는 것입니다.

1. 전역 고정 이진화(Global fixed thresholding)

영상처리에서 이진화는 어떤 주어진 임계값(threshold)보다 밝은 픽셀들은 모두 흰색으로, 그렇지 않은 픽셀들은 모두 검은색으로 바꾸는 것을 지칭한다.

아래 예는 이진화 문제 중 가장 단순한 형태로서 균일한 밝기를 갖는 배경과 물체에 약간의 노이즈를 섞어서 생성한 영상이다.

<그림 1>

그림 1에서 (a)는 원본 영상, (b)는 픽셀들의 밝기값 히스토그램, (c)는 이진화 결과영상이다. 히스토그램에서 볼 수 있듯이 배경영역은 약 100 정도의 밝기값을, 물체는 150 근처의 밝기값 분포를 갖는다. 따라서 임계값(threshold)을 T = 125 정도로 주고 이진화를 했을 때 (c)처럼 가장 좋은 이진화 결과를 기대할 수 있다.

여기서 문제는 임계값 T를 어떻게 자동으로 결정할 것인가이다.

이론적으로 봤을 때 이진화에 따른 분류(classification) 에러를 최소화시켜주는 임계값을 optimal threshold라고 부른다. 즉, 어떤 T값 하나를 고정했을 때 T보다 어두운 물체 픽셀의 비율과 T보다 밝은 배경픽셀의 비율의 합을 최소화해주는 T를 optimal threshold라고 부른다 (물체가 배경보다 밝다고 했을 경우). 하지만 이것은 어디까지는 이론적인 목표, 지향점을 나타낼 뿐 실제 임계값을 구하는 방법을 제시하는 것은 아니다. T가 optimal인지 여부를 알려면 어떤 픽셀이 물체이고 배경인지를 사전에 알고 있어야 하기 때문이다. 하지만 이걸 미리 알고 있었다면 이미 최적의 이진화가 끝난 상태이므로 T를 구할 필요가 없다.

실제 입력 영상의 밝기 분포를 보고 임계값을 찾아주는 가장 실질적인 방법으로는 Otzu's method가 있다 (N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Trans. Syst., Man, Cybern., vol. SMC-9, pp. 62-66, 1979).

Otsu의 이진화 방법은 임계값 T를 기준으로 영상 픽셀들을 두 클래스로 분류했을 때 두 클래스간의 intra-class variance를 최소화하거나 또는 inter-class variance를 최대화하는 T를 찾는 이진화 방법이다.

입력 영상에서 임계값 T보다 어두운 픽셀들의 비율을 α, 밝기 평균을 μ1, 분산을 σ₁², T보다 밝은 픽셀들의 비율을 β, 밝기 평균을 μ2, 분산을 σ₂²라 했을 때 (α+β=1), intra-class 분산과 inter-class 분산은 각각 다음과 같이 계산된다.

intra-class variance = ασ₁²+βσ₂²     --- (1)

inter-class variance = αβ(μ1-μ2)²     --- (2)

식 (1)을 최소화시키는 것은 식 (2)를 최대화시키는 것과 동일하며 둘 중 어느 기준을 사용해도 무방하지만 계산상으로는 식 (2)를 최대화시키는 것이 효율적이다. 즉, Otsu의 이진화 알고리즘은 임계값 T를 0 부터 255까지 단계적으로 변화시키면서 식 (2)를 계산하고 식 (2)가 최대가 되는 T 값을 찾아서 영상을 이진화하는 방법이다.

2. 지역 가변 이진화 I (Locally adaptive thresholding)

문제에 따라서는 아래 예와 같이 하나의 임계값(threshold) 만으로는 어떤 값을 주어도 정확한 이진화가 힘든 경우가 있다.

<그림 2>

그림 2(a)는 흰 종이에 낙서를 한 후에 웹캠으로 촬영한 영상인데 조명 변화 등으로 인해 영상 전체적으로 밝기 변화가 심한 형태로서 그림 2(b) 히스토그램에서 볼 수 있듯이 배경과 물체의 밝기 분포가 서로 상당부분 겹쳐 있는 경우이다. 이 경우에는 어떤 임계값을 사용해도 물체와 배경이 명확하게 구분되지 않는다.

이러한 경우에는 하나의 고정된 threshold 값으로는 이진화가 불가능하며 픽셀 위치마다 서로 다른 threshold를 사용하는 가변 thresholding 기법이 필요하다.

<그림 3>

그림 3은 배경의 밝기 변화를 일차 평면(ax+by+c=0)을 이용하여 근사하여 제거한 결과 이미지를 보여준다(평면근사 방법에 대해서는 최소자승법 이해와 다양한 활용예 (Least Square Method) 글 참조). 배경의 밝기 변화가 제거된 영상은 히스토그램을 그려보면 아래 그림과 같이 배경 영역과 낙서 영역의 밝기값이 잘 분리가 되어서 깨끗한 이진 결과 영상을 얻을 수 있다.

<그림 4>

위의 이진화 과정은 얼핏 global thresholding처럼 보이지만 사실은 원래 입력 영상 관점에서 봤을 때 local adaptive thresholding이 적용된 것이다. 위 과정을 다시 살펴보면 배경의 밝기 변화가 심한 영상에서 먼저 밝기 변화를 제거한 후 밝기 보정된 영상에 대해 global thresholding을 적용한 것이다. 그러나, 이를 원래 영상 관점에서 보면 배경의 밝기를 근사한 평면에 상수값을 더한 것을 threshold 평면으로 볼 수 있고 이 threshold 평면에 대해 직접 이진화를 수행한 것으로 해석할 수 있다.

3. 지역 가변 이진화 II (Locally adaptive thresholding)

사실 위에 설명한 방법은 이진화에 따른 어려움, 특성을 설명하기 위한 하나의 예이고 실용적인 관점에서 간단하면서도 효과적인 방법은 픽셀 주변의 local 영역의 밝기 평균을 임계값으로 사용하는 방법이다 (비전 라이브러리인 OpenCV에 adaptiveThreshold라는 이름의 함수로 제공)

이 방법은 영상 픽셀마다 서로 다른 threshold를 사용하는데, 그 threshold 값은 그 픽셀을 중심으로 한 n x n 주변 영역의 밝기 평균에 일정한 상수를 빼서 결정한다.

주변 영역의 크기를 어떻게 잡느냐와 상수 C를 어떻게 주느냐(+, - 모두 가능)에 따라서 결과가 달라질 수 있으며 문제에 따라서 적절히 값을 조정하면 좋은 이진화 결과를 얻을 수 있다.

아래 그림은 그림 2의 원본 이미지에 local 밝기 평균을 임계값으로 사용하여 이진화한 결과를 보여준다 (n=73, C=10을 사용).

<그림 5>

4. Hysteresis(히스테레시스) thresholding

이진화 문제는 결국 어떤 값이 있을 때 이 값이 A 클래스인지 B 클래스인지 둘 중 하나로 분류하는 것인데 그 경계가 모호한 경우가 많다. 예를 들어 영상에서 어떤 픽셀값이 p1 = 79, p2 = 81이고 임계값(threshold)이 T = 80이라고 하자. 이 경우 p1과 p2는 사실 큰 값의 차이가 없음에도 불구하고 이진화를 하게 되면 전혀 다른 클래스로 분류되게 된다. 이와 같이 경계에 걸친 모호한 값들에 대해서는 하나의 엄격한 기준을 적용하는 것 보다는 이진화 오류를 최소화하기 위해 자신의 값 뿐만 아니라 주변의(공간적 또는 시간적으로) 값을 같이 참조하는 것이 효과적이다.

Hysteresis thresholding은 주변의 분류 결과에 따라서 자신의 분류 결과가 달라질 수 있는 thresholding 기법으로서 Canny edge detector에 사용된 이진화 기법이 가장 대표적인 예이다. Hysteresis(히스테레시스)라는 용어는 위키피디아에는 "Hysteresis is the dependence of a system not only on its current environment but also on its past environment"로 설명되어 있다. 즉, hysteresis는 어떤 시스템의 상태가 자신의 현재 값 뿐만 아니라 과거 또는 주변의 값에 의존하는 현상을 지칭한다.

아래 그림은 edge 검출기 중에서 가장 성능이 좋은 것으로 알려진 Canny edge 검출기를 이용한 edge 검출 예이다(J. Canny, ”A computational approach to edge detection,” IEEE Trans. on PAMI, 8(6):679–698, 1986). 영상에서 에지(edge)를 검출하는 문제도 결국 어떤 픽셀이 edge 픽셀인지 아닌지를 결정하는 이진화 문제로 볼 수 있다.

<그림 6>

Canny edge 검출기에서는 입력 영상에 대해 먼저 Sobel 필터를 적용하여 각 픽셀에 대한 edginess를 계산한 후 다음과 같은 hysteresis thresholding 과정을 거쳐 최종적인 edge 픽셀 여부를 결정한다.

1. high threshold와 low threshold의 두 개의 threshold 값이 존재하며 high threshold 이상의 edginess를 갖는 픽셀들은 무조건 edge 픽셀로 분류한다.
2. low와 high 사이에 있으면서 이미 edge로 분류된 픽셀들과 연결되어(인접해) 있으면 edge 픽셀로 분류한다.
3. 나머지 픽셀들(low threshold 이하이거나 high threshold 이하이면서 edge 픽셀과 연결되어 있지 않은 경우)은 모두 non edge 픽셀로 분류한다.

즉, hysteresis thresholding의 요점은 판단이 확실한 경우(low threshold 이하 또는 high threshold 이상)에는 그대로 이진화를 하되, 그 판단이 불확실한 경우에는 주변 상황을 보고 결정을 하는 것이다.

Hysteresis thresholding 기법은 edge 검출 문제뿐만 아니라 영상 이진화, 피부색 검출 등 모든 이진화 문제에 적용 가능하다. 예를 들어, 영상에서의 피부색 검출의 경우를 보면 먼저 확률이 매우 높은(high threshold) 색들을 피부색으로 분류한 후에 이들을 중심으로 이들과 인접하면서 일정 확률(low threshold) 이상인 픽셀들을 피부색 픽셀로 확장해 나가는 방식이 가능할 것이다.

5. 시간축이 고려된 이진화 문제

마지막으로 시간에 따라 어떤 대상의 분류 상태가 변할 수 있는 경우의 이진화 문제를 살펴보도록 하자.

우리가 어떤 대상에 대해 판단을 할 때 어느 한 순간의 한 값만을 보고 판단을 하는 것은 사실 오류 가능성이 높은 위험한 방법이다. 하지만 방법이 없다보니 어떤 임계값을 미리 정해놓고 관측된 값이 임계값보다 낮으면 A, 높으면 B 이런식으로 판단을 하게 된다. 그런데, 이 대상을 계속 관찰하다 보면 관측된 값이 어떤 때는 임계값보다 높고 또 어떤 때는 임계값보다 낮을 수도 있을 것이다. 이럴 때마다 그 분류가 계속 바뀐다면 결과적으로 매우 불안정한 시스템이 될 것이다.

 이런 경우에 생각할 수 있는 한 방법은 high와 low의 두 개의 임계값을 정해놓고 어떤 대상의 분류가 바뀌는 데에는 보다 엄격한 기준을 적용하는 것이다. 만일 어떤 대상의 관측값이 임계값 이하여서 A 클래스로 분류되었다고 하자. 이후 대상의 관측값이 high threshold 이하인 경우에는 계속 A 클래스로 분류하되, high threshold를 넘어서면 B 클래스로 분류를 바꾼다. 그리고 일단 B가 된 이후에는 관측값이 low threshold보다 낮게 나타난 경우에만 A로 분류를 변경하는 방식이다. 즉, 분류의 경계를 넘나들 때에는 그 방향에 따라서 서로 다른 문턱값을 적용하는 방식이다.

예를 들어보면 처음에 구름이 껴 있는 하늘을 보고 오늘은 그래도 날씨가 좋은 편이다라고 생각했는데 점점 먹구름이 끼는 것이다. 그래도 나는 오늘 날씨가 좋다라는 생각을 바꾸지 않았지만 결국 천둥과 소나기를 접하고 나서야 오늘은 날씨가 나쁘다라고 생각을 바꾼다. 그러다 점점 하늘이 개어서 날씨가 좋아졌지만 쉽사리 마음을 되돌리지 못하고 청명한 하늘과 시원한 솔바람을 맞기 전까지는 여전히 날씨가 나쁘다고 생각하는 식이다.

어찌보면 앞서 설명한 hysteresis 방법과 상당히 유사한 방식으로서 이 기법에 대해서 따로 명칭이 있는지는 잘 모르겠다 (어쩌면 이 기법 또한 hysteresis thresholding 방법중 하나인지도 모른다). 그 응용은 다양한 응용이 가능할 것이며 일례로 열화상 카메라로 감지한 이동체의 움직임을 보고 사람인지 아닌지를 판단하는 문제, 추적하는 대상의 속도나 궤적을 보고 대상을 분류하는 문제 등의 응용이 가능할 것이다.

☞ 예전부터 올리려고 생각했던 글을 이제야 올립니다. 글에서는 주로 영상처리 관점에서 내용을 다루었지만 기본 개념은 영상뿐만 아니라 일반적인 이진화 문제에도 그대로 적용될 수 있습니다. 최적의 해는 문제마다 다를 수 있지만 여러 방법들을 알고 있으면 최적의 해를 찾는데 도움이 되리라 생각합니다.

by 다크 프로그래머

어제 두 해의 경계를 고향집에서 보내고 돌아오는 길에 아내가 앞으로는 가급적 한 해의 마지막 날은 우리집에서 조용히 보냈으면 좋겠다는 얘기를 한다. 맞는 말씀이다. 마무리되지 못한 일, 해외여행, 친구모임, 인사 등에 떠밀리다 보니 어느덧 2014년이다. 매듭도 없고 쉼표도 없이 어제의 2013년이 그대로 오늘 2014년이 된 느낌이다.

사실 쓰고자 하면 며칠 전에, 2013년도에 썼어야 할 글을 이제야 쓴다. 어쩌면 뒤늦은 오늘이 나에게는 실제 지난 한해를 보내는 마지막 날이자 새해를 맞는 첫날인 셈이다.

블로그

지난 한해를 되돌아보면 가장 기억에 남는 것은 뭐니뭐니 해도 이 블로그이다. 

블로그에 올리는 글들은 원래 알고 있던 내용을 정리해서 올리는 경우도 있고 평소 궁금했던 부분 또는 애매한 부분을 새로 공부해서 올리는 경우도 있다. 어느 경우나 자료를 조사하고 생각을 정리하고 글을 가다듬기 위해 많은 시간과 노력이 들어간다. 어떻게 생각하면 힘들수도 있지만 스스로 즐겼기에 재미있게 글을 쓸 수가 있었다. 돌이켜보면 지난 한해동안 다른 어떤 때보다도 많은 공부를 하였고 그만큼 나의 앎과 깨달음의 폭도 깊어진 것 같다.

공부란게 끝이 없어서 항상 배울것은 넘쳐나고 내용은 꼬리에 꼬리를 문다. 많은 내용들이 서로 얽히고 설켜 있으며 그 기저에는 항상 수학이 중요함을 느낀다. 최근 시리즈로 올렸던 선형대수학 관련 글들도 사실은 SIFT, SURF, ORB 등의 local feature들을 전반적으로 정리해 보고자 Harris corner detector부터 다시 공부하던 중 막히는 부분이 있어 시작하게 되었다. 그 전에도 가끔 선형대수학 쪽에서 애매했던 부분들이 있어도 그냥 넘겨왔었는데 최근 Harris 논문을 읽다가 그 임계점을 넘어버린 것이다. 그래서 나의 블로그에는 영상처리와 수학이 항상 혼재된다.

지난 1년동안 블로그 통계를 내 보면 게시글 수는 110개, 댓글 966개, 트랙벡 4개, 방명록 44개, 누적 방문객 수는 20만명, 1일 최대 방문객 기록은 1,422명, 댓글이 가장 많이 달린 글은 '미분 적분 제대로 알자' 117개, '카메라 캘리브레이션' 76개 순이다. 블로그 초기에는 수학 관련 검색어 유입이 대부분이었으나 요즘에는 컴퓨터 비전, 영상처리 관련한 방문도 꽤나 많아져다. 그리고 간간히 '다크프로그래머'라는 검색어로 (하루 3~5건) 방문하는 경우도 있다. 아직 많이 알려지지 않은 블로그이지만 조금씩 자리를 잡아가고 있는 것 같아서 기쁘다.

아쉬움과 다짐

오늘 아침 올 한해 일정을 점검하던 중에 중요한 일을 놓쳐버린 것을 알게 되었다. 어렴풋이 1월달에 있는 것으로 알고 미뤄놓고 있었는데 사실은 12월달에 지나가 버린 것이다. 놓쳐서는 안 되는 것이었는데.. 그동안 블로그로 인해 소홀했던 일들에 치이고 밀려 흘러가다 보니 문득 낯선 곳에 있는 느낌이다. 나의 선택에 후회는 없지만 내가 최소한 어디에 서 있는지는 알면서 살아야겠다.

희망

여기 블로그에 올리는 대부분의 글들은 어떤 주제나 문제에 대해 기존에 있는 내용을 단순히 취합 정리하는 것이 아닌 나의 이해, 나의 해석을 정리한 글이 대부분이다. 스스로 식을 세우고 예제를 만들며 실제 구현 및 실험을 해 보면서 글을 올린다. 스스로 이해되고 정리된 내용에 대해 글을 올리기 때문에 시간은 많이 걸리지만 다른 어디에도 없는 고유한 글이 나온다고 생각한다.

예전에 한 친구가 어떤 일에 대단한 공을 들이는 것을 보면서 뭘 이렇게까지 하느냐 하고 내 물으니 '작은 차이지만 결과를 바꾸는 것은 대부분 1%의 차이다'라는 친구의 대답이 아직도 기억에 남는다. 이왕 쓰는 것 글 하나하나가 최고의 글이 되었으면 하는게 솔직한 바람이다.

올 한해까지는 계속 블로그에 집중하면서 나의 앎과 지식을 가다듬고 정리할 생각이다. 작년, 올해 2년 정도면 어느정도 블로그가 기반이 잡힐 것으로 기대해 보며 이 분야에서 어느정도 인지도를 갖는 블로그가 되기를 희망해 본다. 그래서 보다 많은 이들이 쉽게 접근하고 필요한 지식과 정보를 나눌 수 있는 공간이 되었으면 좋겠다.

블로그에 올리고 싶은 내용은 참 많지만 초창기만큼 마음과 시간의 여유가 잘 허락을 하지 않는다. 아무것도 구속받지 않고 한 1년정도 이것 저것 정리할 수 있는 시간이 있으면 좋겠지만 허황된 꿈이니 좀더 화이팅하고 시간을 잘 분배해서 써야할듯..

☞ 그동안 블로그 방문해 주신 모든 분들께 감사드리며 새해 복 많이 받으시기 바랍니다. ^^

by 다크 프로그래머