728x90

$m$개의 control point $\{\mathbf{Q}_i\}$가 주어지면  $p$차의 B-Spline curve는 basis 함수를 $N_{i, p}(t)$을 써서

$$ \mathbf{B}(t) = \sum_{i=0}^{m-1} N_{i, p}(t) \mathbf{Q}_i $$

로 표현할 수 있다. 이를 이용해서 일정한 순서로 샘플링된 평면상의 $N$개의 입력점 $\{ \mathbf{P}_i \}$을 찾아보자. B-spline 곡선을 이용하면 이 문제는 control 점을 찾는 문제가 된다. 곡선이 입력점을 잘 표현하기 위해서는 곡선과 입력점과의 차이를 최소로 하는 control 점을 찾아야 한다:

$$    \mathbf{ Q}^* = \text{argmin}(L), \quad\quad L:= \sum_{k = 0}^{N-1} | \mathbf{B}(t_k) - \mathbf{P}_k|^2 $$

여기서 $\{ t_k| k=0,1,...,N-1\}$는 입력점이 얻어지는 sample time으로 $0= t_0\le t_1\le...\le t_{N-1}= 1$로 rescale 할 수 있다. 

행렬을 이용해서 식을 좀 더 간결하게 표현할 수 있다. 

$$L = \sum_{k = 0}^{N-1} | \mathbf{B}(t_k) - \mathbf{P}_k|^2 = \sum_{k = 0}^{N-1} \left| \sum_{i=0}^{m-1} N_{i, p}(t_k) \mathbf{Q}_i -  \mathbf{P}_k \right|^2 = \sum_{k = 0}^{N-1} \left| \sum_{i=0}^{m-1} A_{ki} \mathbf{Q}_i - \mathbf{P}_k \right|^2, \\ \quad A_{ki} = N_{i, p}(t_k) $$

로 쓸 수 있으므로, $\hat {Q}= (\mathbf{Q}_0, \mathbf{Q}_1,..., \mathbf{Q}_{m-1})^t$, $\hat {P} = (\mathbf{P}_0, \mathbf{P}_1,..., \mathbf{P}_{N-1})^t$인 벡터, 그리고 $ \hat {A} = (A_{ki})$인 행렬로 보면

$$ L= \left| \hat{A} \cdot \hat {Q} - \hat {P} \right|^2 =  (\hat{Q}^t \cdot \hat {A}^t -\hat{P}^t ) \cdot (\hat{A}\cdot \hat{Q} - \hat{P}).$$

위 식의 값을 최소로 하는 최소자승해는 $\hat {Q}^t$에 대한 미분 값이 0인 벡터를 찾으면 된다; $$ \frac {\partial L}{\partial \hat {Q}^t } = \hat {A}^t \cdot \hat {A} \cdot \hat {Q} - \hat {A}^{t} \cdot \hat {P} = 0.$$ 이 행렬 방정식의 해는

$$ \hat {Q}^* = ( \hat {A} ^t \cdot \hat {A})^{-1} \cdot ( \hat {A}^t \cdot \hat {P})$$ 로 표현된다. $\hat {A} ^t \cdot \hat {A}$가 (banded) real symmetric ($m\times m$) 행렬이므로 Cholesky decomposion을 사용하면 쉽게 해를 구할 수 있다. $\hat{A}$가 banded matrix 형태를 가지는 이유는 basis가 local support에서만 0이 아닌 값을 취하기 때문이다. 

open b-spline(cubic)

int BSplineFit_LS(std::vector<CPoint>& data,
                  int degree,             // cubic(3); 
                  int nc,                 // num of control points;
                  double X[], double Y[]) // estimated control points;
{
    // open b-spline;
    std::vector<double> knot((nc - 1) + degree + 2);
    for (int i = 0; i <= nc + degree; i++) knot[i] = i;
    
    int ndata = data.size();
    std::vector<double> t(ndata);                // parameter;
    double scale = (knot[nc] - knot[degree]) / (ndata - 1);
    for (int i = 0; i < ndata; i++) 
        t[i] = knot[degree] + scale * i;

    std::vector<double> A(ndata * nc);
    for (int i = 0; i < ndata; i++)
        for (int j = 0; j < nc; j++)
            A[i * nc + j] = Basis(j, degree, &knot[0], t[i]); //A(i,j)=N_j(t_i)

    // S = A^t * A; real-symmetric matrix;
    std::vector<double> Sx(nc * nc);
    std::vector<double> Sy(nc * nc);
    for (int i = 0; i < nc; i++) {
        for (int j = 0; j < nc; j++) {
            double s = 0;
            for (int k = 0; k < ndata; k++)
                s += A[k * nc + i] * A[k * nc + j];
            Sx[i * nc + j] = s;
        }
    }
    //copy;
    for (int i = 0; i < nc * nc; i++) Sy[i] = Sx[i];
    // X = A^t * P.x;  Y = A^t * P.y
    for (int i = 0; i < nc; i++) {
        double sx = 0, sy = 0;
        for (int k = 0; k < ndata; k++) {
            sx += A[k * nc + i] * data[k].x;
            sy += A[k * nc + i] * data[k].y;
        };
        X[i] = sx; Y[i] = sy;
    };
    // solve real symmetric linear system; S * x = X, S * y = Y;
    // solvps(S, X) destories the inputs;
    // ccmath-2.2.1 version;
    int res1 = solvps(&Sx[0], X, nc);
    int res2 = solvps(&Sy[0], Y, nc);
    return res1 == 0 && res2 == 0;
};

**네이버 블로그 이전;

'Computational Geometry' 카테고리의 다른 글

Data Fitting with B-Spline Curves  (0) 2021.04.30
Closest Pair of Points  (0) 2021.04.27
DDA Algorithm  (0) 2021.04.25
B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Posted by helloktk

댓글을 달아 주세요

728x90

Brute-force : O(n^2),

Optimal: O(n log(n))

참고: people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf

참고: arxiv.org/pdf/1911.01973.pdf

//  points should be sorted in order of increasing x-component.
//
#define DIST2(p, q) ((p).x-(q).x)*((p).x-(q).x) + ((p).y-(q).y)*((p).y-(q).y)
// 수정: index range -> [idx1, idx2]; ClosestPair(points, 0, points.size()-1, closest);
int ClosestPair(CPoint points[], int idx1, int idx2, int closest[2]) {
    if (idx2 - idx1 >= 3) {
        int lpair[2], rpair[2], min_dist2;
        int idx12 = idx1 + (idx2 - idx1) / 2;                    // half index;
        int dist1 = ClosestPair(points, idx1, idx12, lpair);     // left side;
        int dist2 = ClosestPair(points, idx12 + 1, idx2, rpair); // right side;
        if (dist1 < dist2) {
            closest[0] = lpair[0]; closest[1] = lpair[1];
            min_dist2 = dist1;
        } else {
            closest[0] = rpair[0]; closest[1] = rpair[1];
            min_dist2 = dist2;
        }
        // find points which lies near center strip(2d-strip);
        // Note our distance is the squar of actual distance;
        int width = int(sqrt(double(min_dist2))+0.5);
        int ll = idx1;
        while (points[ll].x < (points[idx12].x - width - 1)) ll++;
        int rr = idx2;
        while (points[rr].x > (points[idx12 + 1].x + width + 1)) rr--;
        for (int i = ll; i < rr; i++) {
            for (int j = i + 1; j <= rr; j++) {
                int dist2 = DIST2(points[i], points[j]);
                if (min_dist2 > dist2) {
                    min_dist2 = dist2;
                    closest[0] = i; closest[1] = j;
                }
            }
        }
        return min_dist2;
    } 
    else if (idx2 == idx1 + 2) {
        return ClosestPair3(points, idx1, closest);
    }
    else if (idx2 == idx1 + 1) {
        closest[0] = idx1; closest[1] = idx2;
        return DIST2(points[idx1], points[idx2]);
    }
    else return INT_MAX;
};

'Computational Geometry' 카테고리의 다른 글

Data Fitting with B-Spline Curves  (0) 2021.04.30
Closest Pair of Points  (0) 2021.04.27
DDA Algorithm  (0) 2021.04.25
B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Posted by helloktk

댓글을 달아 주세요

728x90

Fixed-point version: 선분 길이가 4096 픽셀 정도까지는 1-pixel 이내의 오차로 그려진다.

void DDALine(CPoint A, CPoint B) {
    const int mulfac = 4096; // 2^12 = 4096;
    int dx = B.x - A.x;
    int dy = B.y - A.y;
    int adx = dx < 0 ? -dx : dx;
    int ady = dy < 0 ? -dy : dy;
    int steps = adx < ady ? ady : adx;
    if (steps == 0) SetPixel(A.x, A.y); //single point;
    else {
        int curX = A.x * mulfac;      
        int curY = A.y * mulfac;
        dx = (dx * mulfac) / steps;
        dy = (dy * mulfac) / steps;
        while (steps-- >= 0) {
            SetPixel(curX / mulfac, curY / mulfac);
            curX += dx;
            curY += dy;
        }
    }
}

'Computational Geometry' 카테고리의 다른 글

Data Fitting with B-Spline Curves  (0) 2021.04.30
Closest Pair of Points  (0) 2021.04.27
DDA Algorithm  (0) 2021.04.25
B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Posted by helloktk

댓글을 달아 주세요

B-Spline

Computational Geometry 2021. 4. 25. 09:43
728x90

$$ \mathbf{C}(u) = \sum_{i=0}^{n} N_{i,p} (u) \mathbf{P}_i$$

where $N_{i, p}(u)$'s are B-spline basis functions of degree $p$, $n+1$ control points $\{\mathbf{P}_i\}$, and a knot vector $\mathbf{U}=(u_0, u_1, ..., u_m)$. Note, $m=n + p + 1$.

B-spline의 basis 함수 $N_{i, p}(t)$는 유한한 구간에서만 0이 아닌 값을 갖는(local support) 함수로 다음과 같은  recursion relation을 가진다:

\begin{align} N_{i,0}(t) &= \left\{ \begin{matrix} 1 & \mathrm{if} \quad u_i \leq x \lt u_{i+1} \\ 0 & \mathrm{otherwise} \end{matrix} \right. \quad \quad (0 \le i \le n+p), \\ N_{i,p}(t) &= \frac{t - u_i}{u_{i+p} - u_i} N_{i,p-1}(t) + \frac{u_{i+p+1} - t}{u_{i+p+1} - u_{i+1}} N_{i+1,p-1}(t).\end{align}

$N_{i,p}(t)$의 local support는 $[u_i, u_{i+p+1}]$로 주어진다.

일반적으로 knot vector가 특별한 구조를 가지지 않으면 B-spline곡선은 Bezier 곡선의 경우와 달리 처음과 끝 control 점을 통과하지 않는다(open B-spline). 처음과 끝점을 통과하도록 만들기 위해서는 knot 벡터의 시작 $(p+1)$개 성분이 같은 값을 갖고, 마지막 $(p+1)$개 성분도 같은 값을 갖도록 조정하면 된다(clamped B-spline):

$$clamped: u[0]=u[1]=...=u[p],...,u[n+1]=...=u[n+p]=u[n+p+1]$$

knot는 균일할 필요는 없지만, 균일한 경우는 보통

$$ u_i = \left\{ \begin{array} {rcl} 0 & , & 0 \le i \le p, \\ \frac{i-p}{n+1-p}&, & p+1\le i \le n \\ 1&,& n+1\le i \le n+p+1\end{array}\right.$$

로 선택한다. 

ref: ae.sharif.edu/~aerocad/curve%20modelling-B_Spline.pdf

clamped(black), open(blue)

// Note, p = degree;
void BSpline(int p, std::vector<CPoint>& control, int resolution, CDC *pDC) {
    int n = control.size() - 1;  ASSERT(n > 0);
    std::vector<double> u(n + p + 2);                // knot vector;
    calculateKnots(&u[0], n, p);                     // uniform knot;
    double delta = (u[n + p + 1] - u[0]) / (resolution - 1);  // parameter increment;
    CPoint Q;
    for (double t = u[0] ; t <= u[n+p+1]; t += delta) {
        calculatePoint(&u[0], n, p, t, &control[0], &Q);
        if (i == 0) pDC->MoveTo(Q);
        pDC->LineTo(Q);
    }
    pDC->LineTo(control[n]);
}
// de Boor Cox's algorithm;
double Blend(int i, int p, double *u, double t) {  
    if (p == 0) { // termination condition of recursion;
        if ((u[i] <= t) && (t < u[i+1]))        return 1;
        else                                    return 0;
    }
    else {
        double coef1, coef2;
        if (u[i+p] == u[i]) {
            if (t == u[i])  coef1 = 1;
            else            coef1 = 0;
        } 
        else                coef1 = (t - u[i]) / (u[i+p] - u[i]); 
        
        if (u[i+p+1] == u[i+1]) {
           if (t == u[i+1]) coef2 = 1;
           else             coef2 = 0;
        } 
        else                coef2 = (u[i+p+1] - t) / (u[i+p+1] - u[i+1]);
        return coef1 * Blend(i, p-1, u, t) + coef2 * Blend(i+1, p-1, u, t);
    }
}
// clamped b-spline knot vector; uniform example;
// u[0]=u[1]= ... =u[p],.....,u=[n+p-2]=u[n+p-1]=u[n+p]=u[n+p+1]
void calculateKnots(double *u, int n, int p) {
    int j = 0; 
    while (j <= p)     u[j++] = 0;                 // multiplicity = p+1;
    while (j <= n)     u[j++] = j - p;             // m = n+p+1;
    while (j <= n+p+1) u[j++] = n - p + 1;         // multiplicity = p+1;
}
void calculatePoint(double *u, int n, int p, double t, CPoint *control, CPoint *output) {
    double x = 0, y = 0;
    for (int i = 0; i <= n; i++) {
        double b = Blend(i, p, u, t);
        x += control[i].x * b;
        y += control[i].y * b;
    }
    output->x = int(x + 0.5);
    output->y = int(y + 0.5);
}

'Computational Geometry' 카테고리의 다른 글

Closest Pair of Points  (0) 2021.04.27
DDA Algorithm  (0) 2021.04.25
B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Convexity in Bezier Curve  (0) 2021.04.22
Posted by helloktk

댓글을 달아 주세요

728x90

// test flatness of a bezier curve with control points {p1, c1, c2, p2};
bool FlatBezier(const double eps, 
                const CfPt& p1, const CfPt& c1, const CfPt& c2, const CfPt& p2) {
    CfPt U = c1 - (p1 * 2 + p2) / 3;
    CfPt V = c2 - (p1 + p2 * 2) / 3;
    double normU = hypot(U.x, U.y);
    double normV = hypot(V.x, V.y);
    return (3. * max(normU, normV) / 4.) <= eps;
}
// subdivision stage; De Casteljau's algorithm
void GetBezierPoints(const double eps, 
                     const CfPt &p1, const CfPt &c1, const CfPt &c2, const CfPt &p2,
                     std::vector<CfPt>& smoothed) {
    if (!FlatBezier(eps, p1, c1, c2, p2)) {
        // Subdivide the curve at t = 0.5
        // left;
        CfPt mid_segm = (p1  + c1 * 3 + c2 * 3 + p2) / 8.0;
        CfPt new_c1   = (p1 + c1) / 2.0;
        CfPt new_c2   = (p1 + c1 * 2 + c2) / 4.0;
        GetBezierPoints(eps, p1, new_c1, new_c2, mid_segm, smoothed);
        // right;
        new_c1  = (c1 + c2 * 2 + p2) / 4.0;
        new_c2  = (c2 + p2) / 2.0;
        GetBezierPoints(eps, mid_segm, new_c1, new_c2, p2, smoothed);
    } 
    else smoothed.push_back(p2); // flat enough;
        
}
// linear interpolation between a and b;
CfPt lerp(const double t, const CfPt &a, const CfPt &b) {
    return a * (1 - t) + b * t;
}
void SmoothPathWithBezier(std::vector<CfPt>& points, std::vector<CfPt>& smoothed) {
    int N = points.size();
    if (N < 3) return ; 
    smoothed.clear();
    CfPt cntl[4];
    CfPt *pts = &points[0];   // iterator;
    smoothed.push_back(pts[0]);    
    for (int i = 2; i < N; i++, pts++) {
        if (i == 2) {
            cntl[0] = pts[0];
            cntl[1] = lerp(2./ 3, pts[0], pts[1]);
        } else {
            //0번 control-pts= (0-1)의 중간점;
            //1번 control-pts= (0-1)의 5:1 내분점; 
            cntl[0] = lerp(1./ 2, pts[0], pts[1]);
            cntl[1] = lerp(5./ 6, pts[0], pts[1]);
        }
        if (i == N - 1) {
            //1:2 내분점;
            cntl[2] = lerp(1./ 3, pts[1], pts[2]);
            cntl[3] = pts[2];
        } else {
            //2번 control-pts;(1-2)의 1:5 내분점;
            //3번 control-pts;(1-2)의 중간점;
            cntl[2] = lerp(1./ 6, pts[1], pts[2]);
            cntl[3] = lerp(1./ 2, pts[1], pts[2]);
        }
        //입력 중에 처음 두개가 같거나, 나중 두개가 같으면 마지막이 control pt;
        if ((pts[0] == pts[1]) || (pts[1] == pts[2])) 
            smoothed.push_back(cntl[3]);
        else {
            double tolerance = 1.; // 1-pixel;
            GetBezierPoints(tolerance, cntl[0], cntl[1], cntl[2], cntl[3], smoothed);
        }
    }
}

'Computational Geometry' 카테고리의 다른 글

DDA Algorithm  (0) 2021.04.25
B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Convexity in Bezier Curve  (0) 2021.04.22
De Casteljau's Algorithm  (0) 2021.04.22
Posted by helloktk

댓글을 달아 주세요

728x90

cubic Bezier 곡선은 네 개의 컨트롤 점($\mathbf {P}_0, 주어진다:

$$\mathbf {B}(t) = (1-t)^3 \mathbf {P}_0 + 3(1-t)^2 t \mathbf {P}_1 + 3 (1-t) t^2 + t^3 \mathbf {P}_3.$$

만약 곡선이 충분히 평탄하다면 굳이 삼차 다항식을 계수로 가지는 Bezier 곡선으로 표현할 필요가 없이$\mathbf {P}_0$와 잇는 직선으로 근사하는 것이 여러모로 유리할 것이다. 그러면 Bezier 곡선의 평탄성을 어떻게 예측할 것인가? 이는 cubic Bezier 곡선과 시작점과 끝점을 연결하는 직선 $\mathbf {L}(t)= (1-t) \mathbf {P}_0 + t \mathbf {P}_3$과의 차이를 비교하므로 판단할 수 있다.

 

직선도 cubic Bezier 곡선 표현으로 할 수 있다. 시작점이 $\mathbf {P}_0$이고 끝점이 $\mathbf {P}_3$일 때 이 둘 사이를 3 등분하는 두 내분점 $(2\mathbf {P}_0 + \mathbf{P}_3)/3$, $( \mathbf {P}_0 + 2\mathbf {P}_3)/3$을 control point에 포함시키면,

$$\mathbf {L}(t)= (1-t)^3  \mathbf {P}_0 + (1-t)^2 t (2 \mathbf {P}_0 +\mathbf {P}_3)+ (1-t) t^2  (\mathbf {P}_0 + 2 \mathbf {P}_3)+ t^3 \mathbf {P}_3$$

처럼 쓸 수 있다. Bezier 곡선과 직선의 차이를 구하면

\begin{align} \Delta (t) &= |\mathbf {B}(t) - \mathbf {L}(t)| \\   &= |(1-t)^2 t (3\mathbf {P}_1 -2 \mathbf {P}_0 -\mathbf{P}_3) + (1-t) t^2(3 \mathbf {P}_2 - \mathbf {P}_0 - 2 \mathbf {P}_3)| \\ &= 3 (1-t) t |(1-t) \mathbf {U} + t \mathbf {V}|, \\ \\ &\quad \mathbf {U}=\mathbf {P}_1 - \frac{1}{3}(2 \mathbf {P}_0 + \mathbf {P}_3),   \quad \mathbf {V}=\mathbf {P}_2 - \frac{1}{3} (\mathbf {P}_0 + 2 \mathbf {P}_3)  \end{align}

그런데 

$$ \text {max} \{3(1 - t) t \} = \frac {3}{4}, \quad 0\le t \le 1, \\ \text {max}\{ |(1-t) \mathbf {U} + t \mathbf {V}| \} =\text {max}\{ |\mathbf{U}| , |\mathbf {V}|\} $$

이므로 아래와 같은 벗어난 거리의 상한 값을 얻을 수 있다:

$$ \Delta (t) \le \frac {3}{4} \text{max} \{ |\mathbf {U} | , |\mathbf {V}| \}$$

이 상한값이 주어진 임계값보다 작으면 3차 Bezier 곡선은 두 끝점을 잇는 직선으로 근사할 수 있다. 좀 더 기하학적으로 표현하면

$$|\mathbf{U}| = \mathbf{P}_1\text{에서 왼쪽 3등분 내분점까지 거리}$$

$$|\mathbf {V}|= \mathbf {P}_2 \text{에서 오른쪽 3등분 내분점까지 거리}$$

이므로,

$$ \Delta(t) \le \frac {3}{4}\times( \text{control point와 3등분 내분점 간의 거리의 최댓값}).$$

'Computational Geometry' 카테고리의 다른 글

B-Spline  (0) 2021.04.25
Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Convexity in Bezier Curve  (0) 2021.04.22
De Casteljau's Algorithm  (0) 2021.04.22
Bezier Curve Arc Length  (0) 2021.04.21
Posted by helloktk

댓글을 달아 주세요

728x90

Bezier 곡선은 control point $\{ \mathbf {P}_i\}$의 선형 결합으로 주어진다:

$$\mathbf {B}(t) = \sum_{i=0}^{n} B_{i, n} (t) \mathbf {P}_i , \quad B_{i, n}(t)=\left(\begin {array}{c} n \\ i \end {array} \right) t^i (1-t)^{n-1}.$$

Bernstein 다항식이 선형 결합의 가중치를 역할을 하는데 0과 1 사이의 양의 실수 값을 가진다. 그리고 이들 가중치의 합은 1이다:

$$ 0\le  B_{i, n}(t) \le 1, \quad i=0,1,2,... n ,    \quad    0\le t\le 1 \\\sum_{i=0}^{n}  B_{i, n}(t) = 1$$

따라서 Bezier 곡선은 control points로 만든 convex region에 있음을 알 수 있다. Bezier 곡선의 convexity 특성은 여러 가지 좋은 특성을 준다.  몇 가지만 나열하면, 첫째가 Bezier 곡선은 항상 컨트롤 포인트의 convex hull 내에 놓이게 되므로 곡선의 제어 가능성을 보장한다. 둘째, 교차 여부를 쉽게 확인할 수 있다. 셋째는 culling을 가능하게 한다.

'Computational Geometry' 카테고리의 다른 글

Bezier Curve Smoothing  (0) 2021.04.23
Flatness of Cubic Bezier Curve  (0) 2021.04.23
Convexity in Bezier Curve  (0) 2021.04.22
De Casteljau's Algorithm  (0) 2021.04.22
Bezier Curve Arc Length  (0) 2021.04.21
Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Posted by helloktk

댓글을 달아 주세요

728x90

n 차 Bezier 곡선은 두 개의 (n - 1) 차 Bezier 곡선의 선형보간으로 표현할 수 있다. Bezier 곡선은 Bernstein 다항식을 이용해서도 표현할 수도 있지만, 높은 찻수의 곡선일 때는 De Casteljau's Algorithm을 이용하는 것이 수치적으로 보다 안정적인 결과를 준다.

// De Casteljau's algorithm; recursive version;
double Bezier(double t, double n, double Q[]){
   if (n == 1) return Q[0];
   else return (1 - t) * Bezier(t, n - 1, &Q[0]) + t * Bezier(t, n - 1, &Q[1]);
}
// De Casteljau's algorithm; non-recursive. calling of Bezier() modifies Q's;
double Bezier(double t, double n, double Q[]){
    for (int k = 1; k < n; k++)
        for (int j = 0; j < (n - k); j++)
            Q[j] = (1 - t) * Q[j] + t * Q[j + 1];
    return Q[0];
}
void BezierCurve(std::vector<CfPt> &cntls,
                 int npts, std::vector<CfPt> &curves) {
    int n = cntls.size();
    std::vector<double> xp(n);
    std::vector<double> yp(n);
    for (int k = 0; k < n; k++) {
        xp[k] = cntls[k].x;
        yp[k] = cntls[k].y;
    }
    curves.resize(npts);    
    for (int i = 0; i < npts; ++i) {
        double t = double(i) / (npts - 1);
        curves[i].x = Bezier(t, n, &xp[0]);
        curves[i].y = Bezier(t, n, &yp[0]);
    }
}

'Computational Geometry' 카테고리의 다른 글

Flatness of Cubic Bezier Curve  (0) 2021.04.23
Convexity in Bezier Curve  (0) 2021.04.22
De Casteljau's Algorithm  (0) 2021.04.22
Bezier Curve Arc Length  (0) 2021.04.21
Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Posted by helloktk

댓글을 달아 주세요

728x90

곡선의 길이를 구하고자 하면 곡선을 따라 속력을 적분하면 된다. 곡선을 기술하는 벡터가 $\mathbf {B}(t) = [B_x(t), B_y(t)]$ 로 주어지면 곡선의 길이는

$$\text {Arc Length}(t_1, t_2) =\int_{t_1}^{t_2} | \mathbf {B}'(t)|dt=\int_{t_1}^{t_2} \sqrt{(B'_x(t))^2 + (B'_y(t))^2} dt.$$

그러나 일반적으로 이 적분은 닫힌 형태로 주어지지 않으므로 Gauss-Legendre quadrature와 같은 수치 적분에 의존해서 그 값을 계산하여야 한다.
Bezier curve의 경우는 기하학적인 방법을 이용하여서 좀 더 간편하게 그 길이를 구할 수 있다. Bezier curve의 길이에 대한 간단한 근사는 현의 길이($|\mathbf{Q}_3- \mathbf {Q}_0|$)로 근사하는 것이다. 그러나 현의 길이는 lower bound만을 준다. 다음으로 고려할 근사는  control 점 사이 거리의 합이다. 이것은 실제 길이의 upper bound를 준다. 따라서 근사적인 길이는 이 두 거리의 평균으로 잡으면 될 것이다:

$$ \text{Arc Length}\sim \frac{ \text {현의 길이} + \text {control point 사이 거리 합}}{2}.$$

그러나 이 근사가 유효하기 위해서는 현의 길이와 control point 간의 거리의 합

$$|\mathbf{Q}_3- \mathbf {Q}_2|+ |\mathbf {Q}_2- \mathbf {Q}_1| +|\mathbf {Q}_1- \mathbf {Q}_0|$$

의 차이가 충분히 작아야 한다. 만약에 이 두 길이의 차이기 정해진 임계값보다도 크면 Bezier curve를 둘로 분할해서 좌우 두 Bezier curve에 대해서 동일한 검사를 한다. 충분히 평탄한 경우는 위의 평균값으로 근사하고 그렇지 못한 경우는 충분히 평탄해질 때까지 분할하는 과정을 반복한다. 아래 코드는 3차 Bezier curve의 길이를 이 알고리즘을 이용해서 구하는 과정을 구현한 것이다.

#define DistL2(A, B) sqrt(((A).x-(B).x)*((A).x-(B).x) + ((A).y-(B).y)*((A).y-(B).y))
static void BezierSubDiv(CfPt Q[4], CfPt leftQ[4], CfPt rightQ[4]) {
    CfPt T[4][4];                      /* Triangle Matrix */
    for (int j = 0; j < 4; ++j) T[0][j] = Q[j];
    // de Casteljau divides and conquers at t = 0.5;
    for (int i = 1; i < 4; ++i)
        for (int j = 0 ; j <= 3 - i; ++j)
            T[i][j] = (T[i - 1][j] + T[i - 1][j + 1]) / 2;
            
    // left subdiv control points;
    for (int j = 0; j < 4; ++j) leftQ[j]  = T[j][0];
    // right subdiv control points;
    for (int j = 0; j < 4; ++j) rightQ[j] = T[3 - j][j];
}                                        
void BezierLength(CfPt Q[4], double tol, double *length) {
    CfPt leftQ[4], rightQ[4];                
    double controlLen = 0;  
    for (int i = 0; i < 3; ++i) controlLen += DistL2(Q[i], Q[i + 1]);
    double cordLen = DistL2(Q[0], Q[3]);
    // test flatness;
    if (fabs(controlLen - cordLen) > tol) {
        BezierSubDiv(Q, leftQ, rightQ);              /* divide */
        BezierLength(leftQ, tol, length);            /* left side */
        BezierLength(rightQ, tol, length);           /* right side */
        return;
    }
    *length = *length + (cordLen + controlLen) / 2 ;
    return ;
}

De Casteljau's algorithm

int main() {
    double k[4] = {0.5522847498, //touch at t = 0.5;
                   0.551915023,  //min-deviation;
                   0.551778477,  //match area;
                   0.551777131   //match length;
                   };
    for (int i = 0; i < 4; i++)
        printf("bezier length = %.8f\n", BezierLengthCircle(k[i]));
    printf("exact length  = %.8f\n", 2.0 * atan(1.));
    return 0;
}
double BezierLengthCircle(double k) {
    CfPt Q[4] = {{0, 1.}, {k, 1.}, {1., k}, {1., 0.}};
    double len = 0;
    double tol = 1.e-20;//
    BezierLength(Q, tol, &len);
    return len;
};

 

'Computational Geometry' 카테고리의 다른 글

Convexity in Bezier Curve  (0) 2021.04.22
De Casteljau's Algorithm  (0) 2021.04.22
Bezier Curve Arc Length  (0) 2021.04.21
Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Bresenham's Line Algorithm  (0) 2021.04.07
Posted by helloktk

댓글을 달아 주세요

728x90

Bezier 곡선을 이용한 원의 근사처럼 타원을 근사해보도록 하자. 원점을 중심으로 하고 장축 반지름이 $a$, 단축 반지름이 $b$인 타원을 1사분에서 3차 Bezier curve을 이용해서 근사하려면 4개의 control point가 필요하다. 원의 경우처럼, 끝점에서 접선의 기울기를 같게 하는 조건을 부여하면 control point는 

$$\mathbf {P_0} = (0, b), \quad \mathbf {P}_1 = (ka, b), \quad \mathbf {P}_2 =( a, kb),\quad \mathbf {P}_3 = (a, 0)$$

로 잡을 수 있다. 따라서

$$\mathbf {B}(t) = (1-t^3) \mathbf {P}_0 + 3t(1-t)^2 \mathbf {P}_1 + 3t^2 (1-t) \mathbf {P}_2 + t^3 \mathbf {P}_3 = \left(\begin {array}{c} a x(t) \\ b y(t) \end {array}\right) $$

$$ x(t) = 3k (1-t)^2 t + 3 (1-t) t^2 + t^3 \\ y(t) = 3k t^2 (1-t) + 3t(1-t)^2 + (1-t)^3 $$

$t=1/2$일 때 $(a/\sqrt {2}, b/\sqrt {2})$을 통과하는 조건을 부여하면, 원과 마찬가지로

$$ k = \frac {4}{3}(\sqrt {2}-1)= 0.5522847498...$$

을 얻는다. Mahalanobis measure를 기준으로 거리를 측정하면  타원의 경우도 벗어남 에러가

$$ \Delta (t) = \sqrt { \frac {B_x^2(t)}{a^2} + \frac {B_y^2(t)}{b^2} }  -1 =\sqrt {x^2(t)+y^2(t)}-1$$

원의 경우와 같음을 쉽게 알 수 있다.

회전된 타원; 

2사분면: $(x, y) \rightarrow (-x, y)$

3사분면: $(x, y) \rightarrow (-x, -y)$

4사분면: $(x, y) \rightarrow (x, -y)$

void BezierEllipse(CDC *pDC, CPoint center, double a, double b) {
    const double k = 0.5522847498;
    CPen red(PS_SOLID, 3, RGB(0xFF, 0, 0));
    CPen *pOld = pDC->SelectObject(&red);
    CPoint P[4];  //control pts;
    P[0] = CPoint(center.x,                    int(center.y - b + 0.5));
    P[1] = CPoint(int(center.x + k * a + 0.5), int(center.y - b + 0.5));
    P[2] = CPoint(int(center.x + a + 0.5),     int(center.y - k * b + 0.5));
    P[3] = CPoint(int(center.x + a + 0.5),     center.y);
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
}
void BezierEllipse(CDC *pDC, CPoint center, double a, double b, double ang) {
    const double k = 0.5522847498;
    const double cosang = cos(ang);
    const double sinang = sin(ang);
    CPoint P[4];
    double x[4], y[4], xt[4], yt[4];
    //1사분면: 
    x[0] = 0,     y[0] = b;
    x[1] = k * a, y[1] = b;
    x[2] = a,     y[2] = k * b;
    x[3] = a,     y[3] = 0;
    CPen red(PS_SOLID, 3, RGB(0xFF, 0, 0));
    CPen *pOld = pDC->SelectObject(&red);    
    for (int i = 0; i < 4; i++) {
        xt[i] = x[i] * cosang - y[i] * sinang;
        yt[i] = x[i] * sinang + y[i] * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
    //4사분면;(x, -y);
    CPen blue(PS_SOLID, 3, RGB(0, 0, 0xFF));
    pOld = pDC->SelectObject(&blue);
    for (int i = 0; i < 4; i++) {
        xt[i] = x[i] * cosang - (-y[i]) * sinang;
        yt[i] = x[i] * sinang + (-y[i]) * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
    //3-사분면;(-x,-y)
    CPen green(PS_SOLID, 3, RGB(0, 0xFF, 0));
    pOld = pDC->SelectObject(&green);
    for (int i = 0; i < 4; i++) {
        xt[i] = (-x[i]) * cosang - (-y[i]) * sinang;
        yt[i] = (-x[i]) * sinang + (-y[i]) * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
    //2사분면;(-x,y);    
    CPen magenta(PS_SOLID, 3, RGB(0xFF, 0, 0xFF));
    pOld = pDC->SelectObject(&magenta);
    for (int i = 0; i < 4; i++) {
        xt[i] = (-x[i]) * cosang - y[i] * sinang;
        yt[i] = (-x[i]) * sinang + y[i] * cosang;
        P[i] = CPoint(int(center.x + xt[i] + 0.5), int(center.y - yt[i] + 0.5));
    }
    pDC->PolyBezier(P, 4);
    pDC->SelectObject(pOld);
}

'Computational Geometry' 카테고리의 다른 글

De Casteljau's Algorithm  (0) 2021.04.22
Bezier Curve Arc Length  (0) 2021.04.21
Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Bresenham's Line Algorithm  (0) 2021.04.07
Rotating Calipers  (3) 2021.03.31
Posted by helloktk

댓글을 달아 주세요

728x90

한 개의 Bezier 곡선을 이용해서 원을 표현할 수 없음은 잘 알려진 사실이다. 그럼 Bezier 곡선을 이용해서 얼마나 원(호)을 잘 근사할 수 있을까? 3차 Bezier 곡선을 이용해서 원점에 중심을 둔 반지름 1인 원의 1 사분면 원호를 근사해보도록 하자. 3차 Bezier 곡선은 4개의 control point $\{ \mathbf {P}_i | i=0,1,2, 3\}$이 주어진 경우

$$ \mathbf {B}(t) = (1-t^3) \mathbf {P}_0 + 3t(1-t)^2 \mathbf {P}_1 + 3t^2 (1-t) \mathbf {P}_2 + t^3 \mathbf {P}_3$$

으로 표현된다. 원호 근사에 필요한 control point는 다음 조건을 부여하면 얻을 수 있다. (1) $t=0,1$일 때 원 위에 있어야 하므로

$$\mathbf {B}(t=0) = (0,1) \quad \rightarrow \quad \mathbf {P_0} = (0,1)$$

$$\mathbf {B}(t=1) = (1,0) \quad \rightarrow \quad \mathbf {P_3} = (1,0)$$

그리고 또 그 두 지점에서 접선의 기울기가 원의 기울기와 같아야 하므로

$$ {\mathbf {B}'}(t=0) \propto (1,0)\quad \text {and}\quad {\mathbf {B}'}(t=1)\propto (0,-1)$$

에서

$$ \mathbf {P}_1 = (k, 1), \quad \mathbf {P}_2 = (1, k)$$

처럼 잡을 수 있다. (2) Bezier 곡선의 중간지점이  원 위에 있도록 조건을 부여하면

$$ \mathbf {B}(t=1/2) = (1/\sqrt {2}, 1/\sqrt {2})$$

을 얻고, 이를 이용하면

$$k= \frac {4}{3} (\sqrt {2}-1) = 0.5522847498...$$

을 얻는다.

그럼 원에서 얼마나 벗어날까? 원 중심에서 거리를 차이를 구해보면 Bezier 곡선이 항상 원의 바깥으로 치우쳐 있음을 알 수 있다:

$$\Delta(t) = ||\mathbf {B}(t)||-1\ge 0$$ 

최대로 벗어나는 정도는 $t=(3\pm \sqrt{3})/6$일 때 $\Delta_\text {max}=\frac{1}{3}\sqrt{ \frac{71}{6}-2\sqrt{2}}-1=0.00027253...$이므로 대부분의 경우 크게 벗어남이 없는 원의 근사를 준다.

(2-2) $t=1/2$에서 Bezier 곡선이 원을 통과하는 조건 대신 원에서 벗어남을 최소로 하는 조건을 부여하면 더 좋은 근사를 얻을 수 있다:

$$k=\text{argmin}|\Delta|_\text{max}$$

이 경우  Bezier 곡선은 원의 바깥에 놓이지 않고 교차하게 된다. $t=1/2$에서 최솟값, $t=\frac{1}{2}\left(1\pm \frac{\sqrt{3k^2+20k -12}}{2-3k}\right) $일 때 최댓값을 가지는데, 두 값의 절대값이 같게 되려면(closed form이 없다)

$$ k = 0.551915023...$$

을 선택해야 하고, 이 때 벗어남의 최대값은 $|\Delta|_\text{max} =  0.00019607...$이므로 더 좋은 근사가 된다.

 

(2-3) 또 다른 제한조건은 없을까? Bezier 곡선이 만드는 면적이 사분원의 면적을 표현하도록 제한을 가하는 경우:

$$\frac{\pi}{4} = \int_{0}^{1} \frac{1}{2}\left( B_y B'_x - B_x B'_y\right) dt \\ = \int_0^1  \left(-\frac{3}{2} \left(3 k^2 (t-1)^2 t^2+k \left(-2 t^4+4 t^3-6 t^2+4 t-1\right)+2 (t-1) t\right) \right)dt \\= \frac{1}{2}+\frac{3k}{5}-\frac{3k^2}{20}$$ 에서 

$$ k = 2 - \sqrt{ \frac{22 - 5 \pi }{3}} =0.551778477...$$

이다. 이 경우 면적은 같으나 벗어남 오차는 $t=1/2$일 때

$$|\Delta |_\text{max} = \frac{1}{8} \sqrt{332-40 \sqrt{66-15 \pi }-30 \pi }-1= 0.00026849...$$

로 주어지는데, 중심을 지나는 경우보다는 벗어남이 작지만 최소는 아니다.

(2-4) Bezier 곡선의 길이가 원주가 되는 제한조건을 걸 수도 있다:

$$\frac{\pi}{2}  = \int_0^1\sqrt{ (B'_x)^2 + (B'_y)^2}dt.$$

그런데 우측 적분이 closed form으로 주어지지 않는다. 때문에 $k$ 값을 구하기 위해서 전적으로 numerical method에 의존해야되는데,  그 결과만 쓰면

$$k=0.551777131...$$

'Computational Geometry' 카테고리의 다른 글

Bezier Curve Arc Length  (0) 2021.04.21
Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Bresenham's Line Algorithm  (0) 2021.04.07
Rotating Calipers  (3) 2021.03.31
Convex Hull Peeling  (0) 2021.03.29
Posted by helloktk

댓글을 달아 주세요

728x90

화면이나 그림에서 직선을 그리려면 직선의 방정식을 만족하는 모든 픽셀들을 찾으면 된다. 하지만 픽셀의 위치는 연속적인 값이 아니라  이산적이므로 그림에 그려진 직선을 구성하는 픽셀은 그 직선을 표현을 하는 식이 주는 값에 가장 가까운 정수를 찾아서 그린 것이다. 직선을 그리기 위해서 실수 연산을 한 후 정수로 반올림하는 과정이 들어가게 된다. 

Bresenham 알고리즘은 평면 위의 두 점 $(x_0, y_0), (x_1, y_1)$을 연결하는 직선을 정수 연산만을 사용하여 그릴 수 있음을 보여준다. 직선의 방정식은 $y = mx +b$의 형태로 표현이 되고, 두 점이 주어지는 경우 기울기는 $m = \frac {y_1 - y_0}{x_1 - x_0} = \frac {\Delta y}{\Delta x}$, $y-$절편은 $b =y_0 - m  x_0$로 얻을 수 있다. 직선의 기울기가 1보다 크면 $x$와 $x+1$에서 변할 때 종속변수 $y$값의 차이가 커지므로 선이 연속적으로 그려지지 않게 보인다.  이 경우 $y$를 독립변수로 사용하면 되고, 기울기가 음수면 시작과 끝을 바꾸면 된다. 따라서 기울기가 $0\le m \le 1$인 경우만 살펴보면 충분하다. 

이제, $(x_k, y_k)$ 위치에서 직선의 픽셀이 정해진 경우,  $x_{k+1}= x_k + 1$에서 직선식의 값 $y =m (x_k + 1) + b$는 어떤 정수 값으로 대체되어야 하는가? 기울기가 1보다 작으므로 $y$는 구간 $[y_k, y_k +1]$에서 값을 취한다. 즉,  오른쪽 옆이나 오른쪽 위 픽셀에 점을 찍어야 한다. 수식으로는 구간의 아래($d_{lower}$)와 위쪽($d_{upper}$)과의 차이를 비교하여 작은 쪽으로 결정하면 된다:

$$ d_{lower} = y - y_k = m(x_k + 1) +b - y_k$$

$$ d_{upper} = (y_k + 1) - y = y_k + 1 - m (x_k + 1) -b$$

이 과정을 실수연산 없이 판별하는 방법을 알아내자. $d_{lower}$와 $d_{upper}$의 차이는 

$$ d_{lower} - d_{upper} = 2m (x_k + 1) - 2 y_k + 2b -1$$

로 표현되고, 나눗셈을 하지 않기 위해서 $\Delta x$을 곱한 값을 discriminator로 사용하자:

$$p_k = \Delta x(d_{lower} - d_{upper} )= 2 \Delta y (x_k + 1) - 2 \Delta x y_k  + \Delta x (2b-1)$$

의 꼴로 표현되므로 직선의 정보($\Delta x, \Delta y$)와 현재 점을 찍은 픽셀($x_k, y_k$)을 알면 다음번에 점을 찍을 픽셀을 정수 연산만 가지고 판별할 수 있는 장점이 있다. $k+1$일 때 판별식이

$$ p_{k+1} = 2 \Delta y (x_k + 1)  - 2 \Delta x y_{k+1}  + \Delta x (2b-1)$$

이므로 다음과 같은 recursion relation을 만족한다:

$$p_{k+1} = p_k + 2\Delta y - 2\Delta x  (y_{k+1} - y_k) \\ p_0 = 2\Delta y - \Delta x$$

이를 이용하면 시작 픽셀 $(x_0, y_0)$에서 $p_0 = 2\Delta y - \Delta x$을 계산하여 0보다 작지 않으면 $(x_k + 1, y_k+1)$ 픽셀에 점을 찍고,  그다음 점 찍을 픽셀은  $p_{k+1} = p_k + 2\Delta y - 2\Delta x$을 이용해서 판별한다. $p_0 < 0$ 이면 ($x_k +1, y_k$) 픽셀에 점을 찍고,  그다음 점을 찍을 픽셀은 $p_{k+1}= p_k + 2\Delta y$을 계산하여 판별한다.

void BresenhamLine(int x1, int y1, int x2, int y2, DWORD color) {
    int dx = x2 - x1 ;
    int incx = 1;
    if (dx < 0) {
        dx = -dx;
        incx = -1;
    }
    int dy = y2 - y1;
    int incy = 1;
    if (dy < 0) {
        dy = -dy;
        incy = -1;
    }
    setPixel(x1, y1,color);
    if (dx > dy) {
        int p = (dy << 1) - dx;
        while (x1 != x2) {
            if (p >= 0) {
                y1 += incy;
                p -= (dx << 1);
            }
            x1 += incx;
            p += (dy << 1);
            setPixel(x1, y1, color);
        }
    } else {
        int p = (dx << 1) - dy;
        while (y1 != y2) {
            if (p >= 0) {
                x1 += incx;
                p -= (dy << 1);
            }
            y1 += incy;
            p += (dx << 1);
            setPixel(x1, y1, color);
        }
    }
};

'Computational Geometry' 카테고리의 다른 글

Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Bresenham's Line Algorithm  (0) 2021.04.07
Rotating Calipers  (3) 2021.03.31
Convex Hull Peeling  (0) 2021.03.29
Graham Scan  (0) 2021.03.28
Posted by helloktk

댓글을 달아 주세요

728x90

/*
** 두 점 A, B가 주어졌을 때 벡터 (B-A)가 x-축과 이루는 각을 [0,8)사이로 보내는  
** 간단한 연산의 단조증가함수를 만들어 실제의 각을 대신하도록 한다. 
** 실제 각을 다른 계산에 넣어 사용하지 않고 비교만 할 때 매우 유용하다.
** (0,  1,  2,   3,   4,   5,   6,   7,   8)은 각각 실제 각도
** (0, 45, 90, 135, 180, 225, 270, 315, 360)에 해당한다.
*/
double FowlerAngle(CPoint A, CPoint B) {
    return FowlerAngle(B.x - A.x, B.y - A.y);
}
double FowlerAngle(double dx, double dy) {
    double adx = dx < 0 ? -dx: dx;
    double ady = dy < 0 ? -dy: dy;
    int code = (adx < ady) ? 1: 0;
    if (dx < 0)  code += 2;
    if (dy < 0)  code += 4;
    switch (code) {
    case 0: if (dx == 0) return 0;   /*     dx = dy = 0     */
            else return ady / adx;   /*   0 <= angle <=  45 */
    case 1: return 2 - adx / ady;    /*  45 <  angle <=  90 */
    case 2: return 4 - ady / adx;    /* 135 <= angle <= 180 */
    case 3: return 2 + adx / ady;    /*  90 <  angle <  135 */
    case 4: return 8 - ady / adx;    /* 315 <= angle <  360 */
    case 5: return 6 + adx / ady;    /* 270 <= angle <  315 */
    case 6: return 4 + ady / adx;    /* 180 <  angle <= 225 */
    case 7: return 6 - adx / ady;    /* 225 <  angle <  270 */
    }
};

 

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

Lanczos Resampling  (0) 2021.05.08
Interpolation Kernels  (0) 2021.05.05
Fowler Angle  (0) 2021.04.05
Brute-Force Euclidean Distance Transform  (0) 2021.03.14
Poisson Noise  (0) 2021.03.06
Grassfire Algorithm  (0) 2021.03.05
Posted by helloktk

댓글을 달아 주세요