패턴 인식 (8) 특징 추출
 패턴인식, 오일석 지음/교보문고 |
8. 특징 추출
특징은 크게 두 가지 기준에 대해 우수해야 한다. 첫 번째는 분별력(discriminatory power)이다. 좋은 특징은 서로 다른 부류를 잘 분별해 주어야 하는 것이다. 두 번째는 차원(dimensionality)이다. 특징 벡터의 차원이 낮을수록 계산 효율이 좋고 차원의 저주에서 멀어진다.
특징은 패턴 원천(pattern source)이 처한 외부 환경에 맞추어 설계해야 한다. 이 사실에 따라 야기되는 현상 중의 하나는 특징 설계 과정이 매우 다양하다는 것이다. 어떤 경우에는 측정기로 얻은 값 자체를 특별한 처리 없이 특징 벡터 x로 사용할 수 있으나, 어떤 경우에는 전처리를 한 후에 그것으로부터 특징 벡터를 추출해 사용하여야 한다. 또한 추출된 특징 벡터 중 분별력이 좋은 특징만 선택하여 새로운 특징 벡터 x를 만들기도 한다.
특징에 관하여 용어 혼란이 있을 수 있어 명확히 하고자 한다. 특징을 만드는 전체 과정을 특징 생성(feature generation)이라 하고, 특징 생성을 위해 필요한 작업을 특징 추출(feature extraction)과 특징 선택(feature selection)으로 구분지어 부르기로 한다.
8.1 특징 생성의 틀
8.1.1 실제 세계의 다양성
패턴 인식 과정은 실제 세계에 존재하는 패턴을 적절한 센서를 사용하여 컴퓨터에 입력하고, 이 패턴은 응용에 맞는 적절한 표현으로 컴퓨터에 저장된다. 이 표현은 적절한 처리 과정을 거쳐 특징 벡터라는 수학적인 표현으로 바뀐다. 이러한 처리 과정을 추상화(abstraction)라 부를 수 있다.
수학을 이용하여 통일된 틀에서 원하는 작업을 하려면, 결국 응용에 적합한 처리 과정을 밟아 분별력 높고 차원이 낮은 특징 벡터 x를 생성하여야 한다. 외부 세계에 존재하는 패턴으로 특징 벡터를 만드는 전체 과정을 특징 생성이라 부른다.
8.1.2 특징 추출과 특징 선택
가장 먼저 벌어지는 작업은 센서(sensor)를 사용하여 실세계에 존재하는 패턴을 디지털 신호로 바꾸어 메모리에 저장하는 것이다. 신호(signal)은 여러 형태를 갖는데 보통 벡터 s로 표현한다. 센서로 입력된 신호는 잡음 제거, 분할, 정규화와 같은 전처리가 필요할 수도 있다. 대표적인 신호의 종류는 아래와 같다.
- 영상(image) : 이진, 명암, 컬러 영상이 될 수 있으며 일정한 크기의 영상으로 크기 정규화(size normalization)할 필요도 있다. 명암, 컬러 영상을 이진 영상으로 바꾸어야 할 경우도 있다. 영상에서 특징을 추출하여 1차원 벡터로 바꾸어야 할 경우도 있다.
- 시간성 신호(temporal signal) : 시간 개념이 있으므로 그에 맞게 특징을 추출해야 한다.
- 측정 벡터(measurement vector) : 신호 자체가 벡터 형태이므로 특징 벡터와 크게 다르지 않다.
신호 s가 메모리에 저장되고 나면, 필요한 작업은 크게 두가지 이다.
- 특징 추출 : 신호 s로부터 특징 벡터 x를 만드는 과정이다. 신호의 형태와 으용ㅇ 분야에 따라 아주 다양한 특징 추출 알고리즘이 존재한다. $ x_{\text{org}} = e(s) $
- 특징 선택 : 원래의 특징 벡터에서 쓸모가 적은 특징을 제거하고 새로운 특징 벡터를 선택한다. 이 과정에서 특징 벡터의 크기가 줄어든다. $x = s(x_{\text{org}}) $
8.2 영역에서 특징 추출
패턴이 영역(region)으로 표현되는 상황이 있다. 영역 R은 이진 배열(비트맵)로 표현할 수 있다. 조봍 영상의 좌표계는 왼쪽 위를 원점으로 한다. 또는 집합의 형태로 표현하거나 체인 코드 표현도 가능하다.
8.2.1 모양에 관련한 특징
영역에서 여러 가지 유용한 특징을 추출할 수 있다. 모멘트(moments)라는 개념을 아래와 같이 정의할 수 있다.
$$m_{pq} = \sum_{(x,y) \in R} x^p y^q$$
p와 q를 바꾸어 가며 여러 특징을 추출할 수 있다.
영역의 면적(area)과 중점(centroid)를 각각 아래와 같이 계산할 수 있다.
$$a = m_{00}$$
$$(\bar{x}, \bar{y}) = ( m_{10} / a , m_{01} / a )$$
여기서 영역의 면적은 면적은 영역 R이 다른 위치로 이동하여도 값이 변하지 안흔다. 이러한 성질을 이동 불변(translation invariant)라 한다.
또한 중점은 영역의 크기가 변하더라도 변하지 않는다. 이런 경우에는 크기 불변(scale invariant)이다.
영역은 또한, 회전 불변(rotation invariant)이다.
다음은 중심 모멘트(central moments)를 나타낸 것이다.
$$\bar{m}_{pq} = \sum_{(x, y) \in R} (x- \bar{x})^p (y - \bar{y})^q$$
중심 모멘트를 이용하여 점들이 얼마나 넓게 퍼져 있는지를 나타내는 행, 열, 혼합 분산을 계산할 수 있다.
$$v_{rr} = \bar{m}_{20} / a$$
$$v_{cc} = \bar{m}_{02} / a$$
$$v_{rc} = \bar{m}_{11} / a$$
체인코드를 사용할 경우, 영역의 둘레는 다음과 같이 구할 수 있다.
$$p = n_{even} + n_{odd} \sqrt{2}$$
- $n_{even}$ : 짝수(상하좌우)를 나타내는 체인의 수
- $n_{odd}$ : 홀수(대각선)를 나타내는 체인의 수
영역의 둘레와 면적을 이용하여 둥근 정도(roundness)를 다음과 같이 정의할 수 있다.
$$r = \frac{4 \pi a}{p^2}$$
원일 때 r=1로 가장 큰 값을 갖고, 영역이 길죽해질수록 r은 0에 가깝게 된다. 정사각형은 $\pi/4$이다.
8.2.2 투영과 프로파일 특징
영역을 가로 방향과 세로 방향으로 투영(projection)하여 특징을 추출할 수 있다.
- $ h_i $ : 행 i에 있는 1의 개수
- $ v_j $ : 열 j에 있는 1의 개수
프로파일(profile) 특징은 바깥에서 영역을 바라보며 그 값을 측정한다. 바라보는 방향은 상하좌우 네 가지가 될 수 잇다.
프로파일 $t_j, r_i, b_j, l_i $ : 상,하,좌,우 방향에서 영역을 바라보았을 때 처음 1까지의 거리
8.3 변환을 이용한 특징
여기서는 다른 형태의 신호인 파형(waveform)을 다룬다. 파형은 어느 용옹에서 획득했느냐에 따라 지진파, 기계 진동파, 수중파, 음파, 재정 자립도 추이 곡선, 주식 곡선, 성적 곡선 등이 될 수 있으며, 이들은 아날로그 일 수도, 디지털일 수도 있다.
신호는 기저 함수(basis function)의 선형 결합(linear combination)으로 표현할 수 있다. 예를 들면 아래와 같다.
$$s_1(x) = 0.5 g_1(x) + 1.5 g_2(x)$$
여기서 0.5와 1.5를 기저함수의 계수라고 하며 이 두 계수에 따라 신호의 차이가 뚜렷이 드러난다. 즉 이들 계수를 특징으로 삼을 수 있다.
실제로는 외부 세계에서 관찰한 신호가 입력으로 들어오므로 기저 함수의 계수를 미리 알 수 없다.
8.3.1 퓨리에 변환
입력 신호 s는 n개의 값으로 구성되며, $ s = (s(0), s(1), \dots, s(n-1)^T) $ 으로 표기한다고 할 때, i는 시간 또는 위치를 나타내는 매개변수이다. 이 때 디지털 신호를 위한 퓨리에 변환을 위한 식은 아래와 같다.
$$f(u) = \frac{1}{\sqrt{n}}\sum_{i=1}^{n-1} s(i) \exp(-j \frac{2 \pi u i}{n}), u=0, \dots, n-1)$$
여기서 j는 복소수(complex number)에 나타나는 $\sqrt{-1} $이다.
이를 이산 퓨리에 변환(discrete Fourier transform)이라 부른다. 퓨리에 변환은 $s(i)$를 $f(u)$로 바꾸어 주는데, i는 시간을 나타내고 u는 주파수를 나타낸다. $f(u)$는 u번째 기저 함수의 계수이다. 따라서 퓨리에 변환은 시간 공간(time space)를 주파수 공간(frequency space)로 변화내 준다고 말할 수 있다.
$f(u)$는 실수부$real(f(u))$와 허수부$imag(f(u))$로 구성된다. 이 때, $ p(u) = \sqrt{ real(f(u))^2 + imag(f(u))^2}, u=0, \dots, n-1 $을 파워 스펙트럼(power spectrum)이라고 부른다. 이 값 또한 특징으로 사용될 수 있으며 퓨리에 특징이라고 부른다.
파워 스펙트럼의 경우, u가 커질 수록 그 값을 급속이 하작이진다. 특히 큰 u에 대해서는 0에 매우 가까워 무시해도 문제가 되지 않으므로, 파워 스펙트럼 앞부분에 있는 d개의 특징만을 주로 사용한다.
이미지에서는 퓨리에 변환을 2차원으로 확장하여 사용한다.
8.3.2 퓨리에 기술자
2차원 퓨리에 변환은 이미지에 적용할 수 있으나, 앞에서 설명한 영역에 대해서는 적절하지 않다. 이러한 경우 다른 방법이 있다. 영역의 경계 지점을 $\alpha(i) = x_i + jy_i$와 같은 형식으로 복소수로 표현한다. 그 다음 복소수로 표현된 n개의 점을 이용하여 퓨리에 변환을 얻을 수 있다. 이렇게 얻은 계수를 퓨리에 기술자(Fourier discriptor)라고 한다. 퓨리에 기술자는 시작점을 어디로 하든지 같은 값을 얻는다는 성질이 있다.
8.4 시계열 신호에서의 특징 추출
시계열(time series)로 주어지는 신호도 있다. 이러한 신호는 동적(dynamic)인 성질을 가지므로 정적(static)인 영상과는 다른 방식의 특징 추출 알고리즘이 필요하다. 시계열 신호에서는 주로 퓨리에 변환을 이용하여 단위 시간당 물결(wave)이 몇번 발생하는지를 나타내는 주파수(frequency)와 물결의 높이를 나타내는 진폭(amplitude)로 나타낸다.
시계열에서는 특징을 추출하기 위해 보통 신호를 프레임(frame)단위로 나눈다. 한 프레임이 가지는 점이 개수를 k라고 하자. 경계가 되는 지점에 임의성이 발생할 수 있으므로 어느정도 겹침을 허용하는 것이 일반적이다.
나눠진 프레임에 각각에서 특징 벡터를 추출하면 된다. 결국 하나의 특징 벡터를 얻는 것이 아니라 특징 벡터의 열을 얻게 된다. 즉, 각 프레임에서 퓨리에 변환을 한 뒤 d개의 파워스페트럼을 선택하여 특징으로 사용한다.
퓨리에 특징보다 분별력이 우수한 캡스트럼(cepstrum) 특징도 있다.
8.5 주성분 분석
앞에서 살펴본 방법들은 신호 s를 특징 벡터 x로 변환하는 과정이 주어진 훈련 집합과 무관하다. 하지만 훈련 집합을 이용하여 매개 변수를 추정하고 그것을 이용하여 특징 추출을 하는 방법도 있다. 바로 주성분 분석(principal component analysis, PCA)이다.
8.5.1 동기
PCA는 Karhunen-Loeve (KL) 변환 또는 Hotelling 변환이라고도 부른다. PCA는 훈련 집합을 이용하여 특징 추출이 사용할 변환 행렬 U를 추정한다. 훈련 집합을 $ X = \{ s_1, s_2, \dots, s_N \} $이라고 표현하면, 특징 추출 함수 $ e(s; U) $는 다음과 같이 쓸 수 있다.
$$x = e(s; U) = Us$$
신호 s와 특징 벡터 x가 각각 D와 d차원이라면 U 는 d * D 행렬이다.
PCA는 신호 s를 보다 낮은 차원의 특징 벡터 x로 변환하는 것이 목적으로 d는 D보다 작다. 차원이 줄어들면 당연히 정보 손실이 일어난다. 따라서 PCA는 정보 손실을 최소화하며 D차원을 d차원으로 변환한다.
PCA는 차원 축소를 신호 공간에 정의된 어떤 축으로의 투영으로 표현한다. 축은 D차원 단위 벡터 u로 표현할 수 있다. u 축으로의 투영 변환은 $ \hat{x} = u^ s $로 계산되는데, $ \hat{x} $는 투영 후의 점이다. d개의 각 투영된 점을 모으면 특징 벡터 x가 완성된다.
PCA는 샘플들이 공간에 얼마나 퍼져있는 정도를 변환된 공간에서 얼마나 잘 유지하느냐를 척도로 삼는다. 즉 샘플들의 분산을 이용하는 것이다. PCA는 변환된 샘플들의 분산을 최대화하는 축을 찾는 최적화 문제로 생각할 수 있다.
8.5.2 알고리즘과 응용
위의 최적화 문제는 다음의 분산을 최대화 하는 u를 찾는 문제로 다시 쓸 수 있다.
$$\hat{\sigma}^2 = \frac{1}{N} \sum_{i=1}^N (\hat{x}_i - \bar{\hat{x}})^2 = \frac{1}{N} \sum_{i=1}^N (u^s_i - u^T \bar{s})^2$$
u는 단위벡터이기 때문에 $ u^T u = 1 $이라는 조건을 만들 수 있다. 이 조건을 이용하여 조건부 최적화 문제로 변환한 뒤 라그랑제 승수를 이용하여 다음을 최대화 하는 문제로 변환한다.
$$L(u) = \frac{1}{N} \sum_{i=1}^N (u^T s_i - u^T \bar{s})^2 + \lambda (1- u^T u)$$
$L(u)$를 u로 미분하고, 식을 정리하면 $ 2 \Sigma u - 2\lambda u$로 정리된다. 여기서 $\Sigma $는 공분산 행렬이다. $L(u) $를 최대화하는 u는 $\frac{\partial L(u)}{\partial u} = 0 $을 만족하여야 하므로, 다음과 같이 정리된다.
$$\Sigma u = \lambda u$$
이것은 곧, u는 공분산 행렬의 고유 벡터(eigenvector)이고 $ \lambda $는 고유 값(eigenvalue)임을 알 수 있다. 즉 샘플의 공분산 행렬의 고유벡터를 계산하면 그것이 바로 최대 분산을 갖는 u가 되는 것이다.
공분산 행렬은 D * D 크기를 가지므로 이 행렬의 고유 벡터는 D개가 존재한다. 고유 벡터의 성질에 따라 이들은 모두 수직(orthogonal)하다. 또한 고유 벡터에 해당하는 고유 값이 클수록 중요도가 크므로, 고유 값에 대하여 정렬을 하고 상위 d개의 고유 벡터를 선정하면 된다. 이를 주성분(principal component)라고 한다. 이들 주성분을 이용하여 변환 행렬을 구성할 수 있다.
$$U = (u_1 u_2 \dots, u_d)^T$$
최종적으로 PCA로 구한 변환 행렬 U를 이용하여 신호 s를 특징 벡터 x로 변환할 수 잇다.
$$x = Us$$
만일 d = D로 고유 벡터를 하나도 버리지 않고 사용한다면 $ s = U^{-1} x $를 이용하여 정보 손실 없이 원래의 s를 변환할 수 있다.
이렇게 생성한 특징을 이용하여 분류기를 훈련시키면 된다.
PCA는 주로 얼굴인식에 사용된다. 또, 이미 다른 알고리즘으로 추출한 특징 벡터의 차원 축소에 사용되기도 한다. 그외 데이터 압축, 시각화(visualization)에 사용되기도 한다.
8.6 Fisher의 선형 분별
Fisher의 선형 분별(linear discriminant, LD)라는 분류기 설계 방법이 있다. 기본 원리가 PCA와 비슷하기 때문에 여기서 소개한다.
PCA는 부류의 구분 없이 원래 특징 벡터가 가진 정보의 손시릉ㄹ 최소화하는 변환 행렬을 찾지만 LDA는 서로 다른 부류가 가장 잘 분별될 수 있는 변환 행렬을 찾는다.
분별의 정도를 수치화 하기 위해 다음의 두가지를 사용한다. 하나는 부류간 퍼짐(between-class scatter)이다.
$$|\bar{m_1} - \bar{m_2}| = |w^T m_1 - w^T m_2| = |w^T(m_1 - m_2) |$$
나머지 하나는 부류내 퍼짐(within-class scatter)이다.
$$\bar{s}^2_i = \sum_{y \in w_i} (y - \bar{m}_i)^2$$
여기에서 샘플은 x, 투영 축은 w로 표시한다. $\bar{m}_i $는, i부류의 평균을 나타낸다.
이제 이를 최적화 문제로 변환하여 목적함수를 정의한다.
$$j(w) = \frac{\text{between-class scatter}}{\text{within-class scatter}} = \frac{|\bar{m}_1 - \bar{m}_2|}{\bar{s}_1^2 + \bar{s}_2^2}$$
수식을 유도하면 이 목적 함수를 미분하여 0을 만드는 w를 구할 수 있다.
이렇게 푸는 방법을 Fisher의 선형 분별(linear discriminant)라 부른다.
8.7 실용적 관점
특징 추출은 패턴 인식 전체 과정 중에서 외부 환경에 가장 많은 영향을 받는다. 따라서 휴리스틱한 경험과 실험에 따른 시행착오가 가장 많이 필요한 단계이다.
8.7.1 특징 결합
현재 구해진 특징이 성능이 좋지 않다면 다음을 고려할 수 있다.
- 특징을 버리고 다른 특징을 설계
- 특징에 새로운 특징을 추가(특징 결합, feature combination)
8.7.2 특징 전처리
-
거리 개념이 없는 특징의 변환 : 거리 개념이 없는 특징은 편의상 정수를 부여하여 표현한다. 이 특징이 [1, n]의 정수를 갖는다면 이 특징을 n개의 특징 $x_{i1}, x_{i2}, \dots $으로 확장하여 거리 개념을 만들 수 있다. 새로운 특징은 이진 값을 가지며, k번째 특징만 1을 갖고 나머지는 0을 가게된다. 따라서 특징이 다른 두 샘플간의 거리는 $\sqrt{2}$가 된다.
-
특징 값의 정규화 : 어떤 특징은 값이 범위가 크고 어떤 특징은 작은 경우 정규화를 이용할 수 있다. 간단한 정규화로 선형 변환을 이용한 동적 범위 정규화(dynamic range normalization)을 주로 이용한다. 또는 각 특징의 표준 편차를 이용한 방법을 이용할 수 있다.
-
손실 특징의 보충 : 샘플이 어떤 특징 값이 지정되지 않은 경우가 있다. 이런 경우 손실 특징을 갖게 된다. 훈련 집합이 큰 경우에는 이런 샘플을 배제하면 되나, 그렇지 않은 경우 다른 샘플의 평균 값으로 채워넣는 방법을 사용하기도 한다.