평면 위에 점집합이 주어지고 이들을 잘 기술하는 직선의 방정식을 구해야 할 경우가 많이 발생한다. 이미지의 에지 정보를 이용해 선분을 찾는 경우에 hough transform과 같은 알고리즘을 이용하는 할 수도 있지만 수치해석적으로 직접 fitting을 할 수도 있다. 점집합의 데이터를 취합하는 과정은 항상 노이즈에 노출이 되므로 직선 위의 점뿐만 아니라 직선에서 (많이) 벗어난 outlier들이 많이 들어온다. 따라서 line-fitting은 이러한 outlier에 대해서 매우 robust 해야 한다. 데이터 fitting의 경우에 초기에 대략적인 fitting에서 초기 파라미터를 세팅하고, 이것을 이용하여서 점차로 정밀하게 세팅을 해나가는 반복적인 방법을 많이 이용한다. 입력 데이터가 $\{(x_i, y_i)| i=0,..., N-1\}$로 주어지는 경우에 많이 이용하는 최소자승법에서는 각 $x_i$에서 직선상의 $y$ 값과 주어진 $y_i$의 차이(residual)의 제곱을 최소로 하는 직선의 기울기와 $y$ 절편을 찾는다. 그러나 데이터가 $y$축에 평행하게 분포하는 경우를 다루지 못하게 되며, 데이터 점에서 직선까지 거리를 비교하는 것이 아니라 $y$값의 차이만 비교하므로 outlier의 영향을 매우 심하게 받는다.

이러한 문제를 제거 또는 완화하기 위해서는 PCA(principal axis analysis)를 이용할 수 있다. 점들이 선분을 구성하는 경우, 선분 방향으로는 점 위치의 편차가 크지만 수직 방향으로는 편차가 상대적으로 작다. 따라서 평면에서 점 분포에 대한 공분산 행렬 $\Sigma$의 고윳값과 고유 벡터를 구하면, 큰 고윳값을 갖는 고유 벡터 방향이 선분의 방향이 될 것이다. 잘 피팅이 이루어지려면 두 고윳값의 차이가 커야 한다. 또한 outlier에 robust 한 피팅이 되기 위해서는 각 점에 가중치를 부여해서 공분산 행렬에 기여하는 가중치를 다르게 하는 알고리즘을 구성해야 한다. 처음 방향을 설정할 때는 모든 점에 동일한 가중치를 부여하여 선분의 방향을 구한 후 다음번 계산에서는 직선에서 먼 점이 공분산 행렬에 기여하는 weight를 줄여 주는 식으로 하면 된다. weight는 점과 직선과의 거리에 의존하나 그 형태는 항상 정해진 것이 아니다.

 

// 점에서 직선까지 거리;
double DistanceToLine(CPoint P, double line[4]) {
    // 중심에서 P까지 변위;
	double dx = P.x - line[2], dy = P.y - line[3]; 
    // 직선의 법선으로 정사영 길이 = 직선까지 거리;
    return fabs(-line[1] * dx + line[0] * dy);
}
// PCA-방법에 의한 line-fitting;
double LineFit_PCA(std::vector<CPoint>& P, std::vector<double>& weight, double line[4]) {
    int res = 1;
    // 초기화 시 weight[i] = 1.;
    double sx = 0, sy = 0, sxx = 0, syy = 0, sxy = 0, sw = 0;
    for (int i = P.size(); i-->0;) {
         int x = P[i].x, y = P[i].y;
         double w = weight[i]; 
         sx += w * x; sy += w * y;
         sxx += w * x * x; syy += w * y * y;
         sxy += w * x * y; 
         sw  += w; 
    }
    // variances;
    double vxx = (sxx - sx * sx / sw) / sw;
    double vxy = (sxy - sx * sy / sw) / sw;
    double vyy = (syy - sy * sy / sw) / sw;
    // principal axis의 기울기;
    double theta = atan2(2 * vxy, vxx - vyy) / 2;
    line[0] = cos(theta); line[1] = sin(theta);
    // center of mass (xc, yc);
    line[2] = sx / sw; line[3] = sy / sw;
    // line-eq:: sin(theta) * (x - xc) = cos(theta) * (y - yc);
    // calculate weights w.r.t the new line;
    std::vector<double> dist(P.size());
    double scale = 0;
    for (int i = P.size(); i-->0;) {
        double d = dist[i] = DistanceToLine(P[i], line);
        if (d > scale) scale = d;
    }
    if (scale == 0) scale = 1;
    for (int i = dist.size(); i-->0; ) {
        double d = dist[i] / scale;
        weight[i] = 1 / (1 + d * d / 2);
    }
    return fitError(P, line);
};
void test_main(std::vector<CPoint>& pts, double line_params[4]) {
    // initial weights = all equal weights;
    std::vector<double> weight(pts.size(), 1); 
    while (1) {
       double err = LineFit_PCA(pts, weight, line_params) ;
       //(1) check goodness of line-fitting; if good enough, break loop;
       //(2) re-calculate weight, normalization not required.
     }
};

아래 그림은 weight를 구하는 함수로 $weight= 1 /\sqrt{1+dist\times dist}$를 이용하고, fitting 과정을 반복하여 얻은 결과다. 상당히 많은 outlier가 있음에도 영향을 덜 받는다. 파란 점이 outlier이고, 빨간 직선은 outlier가 없는 경우 fitting 결과고, 파란 선은 outlier까지 포함한 fitting 결과다.

##: 네이버 블로그에서 이전;

 
 
 
728x90

'Image Recognition > Fundamental' 카테고리의 다른 글

Fast Float Sqrt  (0) 2020.12.27
2차원 Gaussian 분포 생성  (0) 2020.12.10
Histogram Equalization  (0) 2020.11.12
Least Squares Fitting of Circles  (0) 2020.11.11
Integer Sqrt  (0) 2020.11.11
Posted by helloktk
,

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

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

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

 

728x90

'Image Recognition' 카테고리의 다른 글

Color Counting  (0) 2010.01.18
Isometric Transformation  (0) 2010.01.11
Eigenface (2)  (0) 2009.12.28
Active Shape Model (ASM)  (2) 2009.12.25
Similarity Transformation  (1) 2009.12.14
Posted by helloktk
,

Eigenface (2)

Image Recognition 2009. 12. 28. 23:55

특정한 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


 

 
 
 
 



728x90

'Image Recognition' 카테고리의 다른 글

Isometric Transformation  (0) 2010.01.11
Active Shape Model (3)  (0) 2009.12.30
Active Shape Model (ASM)  (2) 2009.12.25
Similarity Transformation  (1) 2009.12.14
Eigenface  (0) 2009.12.12
Posted by helloktk
,

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

먼저 찾고자 하는 물체의 윤곽 정보를 훈련을 시켜 평균 윤곽선과 평균 윤곽선에서 벗어남을 기술하는 독립적인 mode(=eigen mode=eigen shape)를 알아낸다. 이것은 얼굴인식에서 PCA 기법을 이용하여서 평균 얼굴영상에서 변화를 주는 eigen modeeigenface를 찾는 기법과 같다. 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

 

 

728x90

'Image Recognition' 카테고리의 다른 글

Active Shape Model (3)  (0) 2009.12.30
Eigenface (2)  (0) 2009.12.28
Similarity Transformation  (1) 2009.12.14
Eigenface  (0) 2009.12.12
Retinex 알고리즘 관련 자료  (1) 2009.04.29
Posted by helloktk
,

Eigenface

Image Recognition 2009. 12. 12. 20:03

평균 얼굴:
- 173개의 얼굴 영상(130x150)을 가지고 만든 것이다.
- 얼굴 영상 출처: http://www.cs.colostate.edu/evalfacerec/data.html(두 눈의 위치 정보가 있어서 편리하다)
- 얼굴 영상은 두 눈의 위치가 영상에서 일정한 위치에 있도록 기하학적인 변환(similarity transform)을 수행했다.


Eigenfaces:
- 173개의 영상에서 평균 얼굴을 뺀 후에 Covariance Matrix을 만들었으므로 실제로 eigenvector는 173-1=172차원 hyperplane를 형성. 130x150차원 공간의 subspace)
- 각각의 eigenface는 1로 정규화된 벡터(영상)이나, 이미지로 보이기 위해서 임의로 스케일링한 것이다. 따라서 각각의 eigenface이 밝기는 상대적인 값이다.
- 영상은 eigenvalue의 크기 순서대로 69개만 나열한 것이다( 큰 것--> 작은 것. dimensional reduction)


얼굴의 재구성
원본 얼굴($\bf x$):

69개의 eigenface로 재구성된 얼굴: 상관계수=0.9897;

 


훼손된 얼굴(원본):

eigenface을 이용해서 재구성한 얼굴(69개의 eigenface을 이용) : 상관계수=0.8788;

eigenface를 10개에서 69개로 순차적으로 늘리면서 재구성한 결과(animating gif):


Nonface의 재구성:
원본(원숭이)

재구성된 원숭이 얼굴(69개의 eigenface이용)
- 원본과의 상관계수를 구하여서 얼굴인지 아닌지를 판별할 수 있다.: 상관계수=0.7887;

728x90

'Image Recognition' 카테고리의 다른 글

Active Shape Model (ASM)  (2) 2009.12.25
Similarity Transformation  (1) 2009.12.14
Retinex 알고리즘 관련 자료  (1) 2009.04.29
Spline Based Snake  (0) 2008.08.15
Anisotropic Diffusion Filter  (0) 2008.08.11
Posted by helloktk
,