Geometry & Recognition

이미지에서 물체를 인식할 때 물체의 윤곽 정보는 매우 중요한 역할을 한다. 이 윤곽 정보는 보통의 경우 에지를 검출한 후 적절한 영상처리를 거쳐서 단일 픽셀의 선으로 표현된다. 그러나 이렇게 만든 윤곽선은 불필요하게 많은 점으로 구성이 되어 있는 경우가 많으므로, 실제 결과를 사용할 때 적당한 길이의 직선으로 연결된 폴리 라인(polyline)으로 근사를 하여 사용한다. 이 경우 윤곽선의 연접한 점들을 어디까지 직선으로 판단할 것인가에 대한 문제가 생긴다. 

이에 대한 한 가지 접근법은 먼저 윤곽선의 처음과 끝점을 잇는 선분을 만들고 사이의 점들이 이 선분에서 벗어난 정도를 조사한다. 최대로 벗어난 윤곽선의 점이 폴리 라인의 새 꼭짓점이 되고 그 꼭짓점을 기준으로 이전 선분을 두 개로 분할한다. 다시 분할된 두 선분에 대해서 같은 작업을 시행하여 더 이상 작은 선분으로의 분할이 없을 때까지 반복하는 것이다. 이 방법은 잘 알려진 Douglas-Peucker 알고리즘이다. 

두 번째 방법은 윤곽선의 처음 점에서 시작하는 직선의 끝점의 위치를 윤곽선을 따라 순차적으로 옮겨가면 선분을 만들고, 사이의 점들이 이 선분에서 너무 멀리 떨어지지 않는가를 체크한다. 선분에서 너무 벗어난 점이 있으면, 바로 직전의 윤곽선 점을 꼭짓점으로 분류한 후 이 꼭짓점에서 시작하는 선분을 앞에서와 같은 방식으로 만들어서 다음 꼭짓점 후보를 찾는다. DP 알고리즘이 분할에 기반한 것이라면, 이 방법은 점들의 합병(merging)에 기반한 알고리즘이다. 두 알고리즘 모두 재귀적으로 구현할 수 있다. 아래 그림은 DP-알고리즘(Green Line)과 merge-알고리즘 (Blue Line)을 동시에 비교한 것이다.

거리-tolerance를 10씩 증가시키면(점점 단순해진다) 두 알고리즘을 적용하여 본 결과:

// mark는 새로운 꼭지점의 후보를 기록한다(1=꼭짓점, 0=아님)
// mark[0] = mark[end_idx] = 1;
// end = size(v) - 1: not changing;
void mergeSimplication(double tolerance, int start, int end, std::vector<CfPt>& v, 
                       std::vector<int>& mark) 
{
    if (end <= start + 1) return ; //at least 3 ;
    int k = start + 2;
    for (;k <= end; k++) {
        double dist_max = 0;
        for (int i = start+1 ; i < k; i++) {
            // distance to a segment(v[start], v[k]) from v[i];
            double dist = distance2Segment(v[start], v[k], v[i]);
            if (dist_max < dist) dist_max = dist;
        }
        if (dist_max > tolerance) break; 
    } 
    // 정상적으로 끝나면 k==end + 1;
    if (k <= end) {
        //k 에서 tolerance을 넘었으므로 새로운 vertex은 k-1;
        mark[k-1] = 1; // new_vertex;
        mergeSimplication(tolerance, k-1, end, v, mark);
    }
    return;
};

// distance2Segment()는 한 점에서 선분까지 거리를 구하는 함수;
// distantance tolerance 이내에 근접한 이웃점들은 미리 제외시킨 후 알고리즘을 적용한다.

두 점 $A$와 $B$가 만드는 선분 $\overline{AB}$가 있고, 한 점 $P$에서 이 선분까지 거리를 구하려고 할 때 단순히 $\overline{AB}$를 통과하는 직선과 점 $P$의 거리를 구해서 쓰면 안 된다. 그림처럼 $P$가 $P'$의 위치에 있는 경우에 $\overline{AB}$를 통과하는 직선과의 거리가 더 짧지만, 선분과의 거리는 $P'$와 $A$와 거리로 주어진다. 마찬가지로 $P$가 $P''$에 있을 때는 점 $B$와 거리가 최단거리다. 정리하면,
1. 선분 $\overline{AP}$와 $\overline{AB}$의 사이각이 $90^\circ$를 넘는 경우는 $A$까지 거리;
$$\cos (\text{사이각}) = \frac{(P.x - A.x)*(B.x - A.x) + (P.y - A.y)*(B.y - A.y)}{\overline{AP}\text{ 길이} * \overline{AB}\text{ 길이}} < 0 .$$
2. 선분 $\overline{AP}$의 $\overline{AB}$로의 정사영 길이가 $\overline{AB}$의 길이보다 클 때는 $B$까지 거리:
$$\text{정사영 길이} = \frac{(P.x - A.x)*(B.x - A.x) + (P.y - A.y)*(B.y - A.y)}{ \overline{AB}\text{ 길이}} > \overline{AB}\text{ 길이} .$$
3. 직선 $\overline{AB}$와의 거리 = $\overline{AP}$의 수선으로 정사영 길이:
$$\text{수선으로 정사영} = \frac{-(P.x - A.x)*(B.y - A.y) + (P.y - A.y)*(B.x - A.x)}{\overline{AB}\text{ 길이}} .$$

struct CfPt {
    double x, y;
    double DistanceTo(CfPt P) {
        return hypot(P.x - x, P.y - y);
    }
};
//선분과의 거리;
double SegmentDistance(CfPt A, CfPt B, CfPt P) {
    double lineLen = A.DistanceTo(B);
    if (lineLen == 0) return A.DistanceTo(P);  //A == B;
    // lineLen != 0 case
    double prj = ((P.x - A.x )*(B.x - A.x) + (P.y - A.y) * (B.y - A.y)) / lineLen;
    if (prj < 0) return A.DistanceTo(P);
    else if (prj > lineLen) return B.DistanceTo(P);
    else 
        //return normal_projection
        return fabs((-1)*(P.x - A.x)*(B.y - A.y) + (P.y - A.y)*(B.x - A.x)) / lineLen;
};

타원도 기본적으로 원 그리기와 동일한 알고리즘을 이용하여 그릴 수 있다. 하지만 원과 달리 좀 더 고려할 부분이 있다. 전체 영역을 $45^\circ$씩 8개 영역으로 나눈 후 한 영역에서만 계산하고 나머지는 대칭성을 이용하는 방법을 타원에는 바로 적용이 어렵다. 원에서 $45^\circ$ 기준선은 접선의 기울기가 $\frac{dy}{dx} = -1$인 점과 원점을 잇는 선분인데 타원에서는 이 관계가 성립하지 않는다. 타원 방정식 $\frac{x^2 }{ a^2} +\frac{ y^2}{b^2} = 1$ 에서 접선의 기울기가 $-1$인 지점은

$$x = \frac{a^2 }{ \sqrt {a^2  + b^2 }} , \quad y = \frac{ b^2 }{ \sqrt {a^2  + b^2 }}$$

로 주어진다. 이 지점까지는 $x$를 독립변수로 잡아야 하고, 나머지 $y = 0$까지는(1 사분면에서) $y$를 독립변수로 잡아야 한다. 나머지 분면은 대칭성을 이용하면 바로 그릴 수 있다.

픽셀 $(x_k , y_k)$에  점이 찍히면 다음은 어느 픽셀에 점을 찍어야 할까? $0\ge \text{기울기}\ge-1$이므로 오른쪽 옆이나 또는 오른쪽 아래 픽셀이 될 것이다. 이를 판별하는 식을 만들기 위해서 다음 식을 고려하자(나눗셈을 피하기 위해서 타원식에 $a^2b^2$을 곱했다): 

$$F(x, y) = b^2 x^2 + a^2 y^2 - a^2 b^2$$

$(x_k, y_k )$가 타원 위의 점이면 $F=0$을 만족한다. 다음 점이 찍힐 후보 위치가 $(x_k+1, y_k)$ 또는 $(x_k+1, y_k-1)$이므로 중간 위치(Midpoint)에서 $F$의 부호를 기준으로 판별하도록 하자:

$$d_k = F(x_k+1, y_k-1/2) \\ d_k < 0  \quad \text {이면} \quad (x_k+1, y_k),\\   d_k > 0\quad \text {이면} \quad (x_k+1, y_k-1)$$

이후에 판별식의 업데이트는 

$$d_k <0~인 ~경우:\quad           d_{k+1} = F(x_k+2, y_k-1/2) = d_{k} + b^2 ( 2 x_{k+1} +1)$$

$$d_k \ge 0 ~인 ~경우: \quad  d_{k+1} = F(x_k + 2, y_k -3/2) = d_{k} + b^2 (2x_{k+1} + 1)- 2a^2  y_{k+1}$$

로 주어진다. 시작 픽셀에서 판별식의 값은

$$ x_0 = 0, y_0 = b \quad \Rightarrow\quad d_0 = F(1, b-1/2) = (4 b^2 + a^2 (1 - 4 b)) / 4$$

다음 문제는 $x$가 독립변수로써 얼마나 사용되고, 어느 지점에서 $y$가 독립변수가 되어야 하는가를 알아내는 것이다. 기울기 $dy /dx$ 가 0에서 -1 사이인 지점까지 $x$가 독립변수이므로, 우선 타원식을 미분하면

$$2b^2 x + 2a^2 y \frac{dy}{dx} = 0 \\ \Rightarrow b^2 x = -a^2 y \frac{dy}{dx} = a^2 y \left| \frac{dy}{dx}\right|  \le a^2 y, \quad -1 \le \frac{dy}{dx} \le 0 \\ \therefore  \quad b^2 x \le a^2 y$$

이 조건이 만족하는 동안 $x$를 독립변수로 사용하여 그리기를 한다.

$y$가 독립변수인 구간으로 넘어가자. 이 경우는 $x_0=a, ~y_0=0$에서 출발하면 위 영역에서 $x_k$와 $y_k$의 역할을 바꾼 방식이 된다. $(x_k, y_k)$에 점이 찍히면 다음 후보는 $(x_k, y_k+1)$ 또는 $(x_k-1, y_k+1)$이다. 중간점이 $(x_k-1/2, y_k+1)$이므로 판별식은

$$ d_k = F(x_k -1/2, y_k +1)$$

로 주어진다. 이 판별식의 업데이트는 

$$d_k <0~인 ~경우:\quad           d_{k+1} = F(x_k - 1/2, y_k+2) = d_{k} + a^2 ( 2 y_{k+1} +1)$$

$$d_k \ge 0 ~인 ~경우: \quad  d_{k+1} = F(x_k  -3 / 2, y_k +2) = d_{k} +a^2 (2x_{k+1} + 1)  - 2 b^2  x_{k+1}$$

로 주어진다. 그리고 시작 픽셀에서 판별식의 값은

$$ x_0 = a, y_0 = 0 \quad \Rightarrow\quad d_0 = F(a-1/2,0) = (4 a^2 + b^2 (1 - 4 a)) / 4$$

이다. 전체적인 코드는

// setPixel(CDC *pDC, int x, int y)에 (x, y), (-x, y), (x,-y), (-x,-y)를 
// 동시에 그리도록 구현이 되어야 한다. 그리고 중심이 원점이 아닌 경우에는 
// 평행이동 시키면 된다:
    int x = 0, y = b ;
    int aa = a * a ;
    int bb = b * b ;
    int d = (4 * bb + aa * (1 - 4 * b)) / 4 ;

    setPixel (pDC, x, y) ;     
    while ( bb * x < aa * y) {
        ++x ;
        if (d < 0) d +=  bb * (2 * x + 1);    // (x+1, y) 선택;
        else {                                // (x+1, y-1) 선택;
            --y ;
            d += bb * (2 * x + 1) - 2 * aa * y ;
        }
        setPixel(pDC, x, y);

    };
    //y-독립변수 구간;
    x = a, y = 0;
    d = (4 * aa + bb * (1 - 4 * a)) / 4;
    setPixel(pDC, x, y) ;
    while (bb * x > aa * y) {
        ++y ;
        if (d < 0) d += aa * (2 * y + 1);
        else {
            --x ;
            d += - 2 * bb * x + aa * (2 * y + 1);   
        }
        setPixel(pDC, x, y);
    }

물론 실수 연산을 하면, 아래의 코드로 타원을 그릴 수 있다. 접선의 기울기의 크기 $|dy/dx| = 1$ 인 점을 기준으로 하여 그 값이 1 보다 작은 지점에서는 $x$를 독립변수로, 큰 지점에서는 $y$를 독립변수로 잡으면,

          x-구간    ===>  b^2 * x < a^2 * y;
          y-구간    ===>  b^2 * x > a^2 * y;

이므로, 아래처럼 쓸 수가 있다:

    int aa = a * a, bb = b * b;
    x = 0; y = b;
    while (bb * x <= aa * y) {
        y = (int)((double) b / a * sqrt(aa - x * x) + 0.5);
        setPixel(pDC, x, y);
        ++x;
    }
    y = 0;
    while (bb * x > aa * y) {
        x = (int)((double) a / b * sqrt(bb - y * y) + 0.5);
        setPixel(pDC, x, y) ;
        ++y;
    }

last update: 2021.04.08;