Polygon Decimation

일정한 간격(예를 들면 1)으로 sampling 된 물체의 윤곽정보가 있다고 하자. 이 윤곽정보를 좀 더 적은 데이터를 이용해서 표현하려고 할 때 가장 쉬운 방법 중 하나는 샘플링 간격을 2배로 늘리는 것이다(down sampling). 이는 더 큰 스케일에서 물체를 바라보는 것과 동일한 효과를 준다. 그러나 down sampling에서 일부의 원정보가 사라지게 되므로 이에 대한 보정이 필요하게 된다. Down sampling 된 데이터에서 버려진 중간지점(홀수)의 정보는 선형적으로 예측할 수 있지만 이는 충분하지 못하다. 따라서 down sampling 할 때 버리지는 부분이 지니고 있는 고주파 성분을 저장한 후 이를 down sampling 된 저주파 성분의 보정에 사용해야 할 필요가 생긴다.

그러면 다운 샘플링과정에서 잃어버리는 고주파 성분은 어떻게 알아낼 수 있을까? 이는 다운 샘플링된 데이터로 원 데이터를 구성하려면 보간 방법을 사용하는데, 원 데이터에서 보간 값을 빼주면 근사적으로 예측할 수 있다. 다운 샘플링된 저주파 성분에 예측된 고주파 성분을 일정 부분 추가함으로써 더 정교한 다운샘플링을 할 수 있다. 이는 wavelet 변환에서 lifting-update 과정에 해당한다. 여기서는 이 알고리즘을 복잡한 폴리곤을 단순화시키는 과정에 적용해 본다. 보간 방법으로 Catmull-Rom spline을 이용했다. Douglas-Peucker 알고리즘에서는 변화지 않는 두 개의 고정점이 있지만, 이 방법에서는 모든 점이 변할 수 있다. 알고리즘을 반복 적용하면 매회 1/2로 다운샘플링되므로 어느 단계를 넘어서면 과도하게 단순화되는 단점이 있다. 입력점의 개수가 2의 지수승이 아닌 경우는 마지막 점을 반복해서 넣어주면 된다. 

// at t=1/2 (p0, p1, p2, p3);
CfPt catmull_rom(const CfPt& p0, const CfPt& p1, const CfPt& p2, const CfPt& p3) {
    return ((p1 + p2) * 9 - (p0 + p3)) / 16;
}
// 홀수점에서 고주파 성분을 주변 4개의 짝수점으로 만든 
// catmull-rom 스프라인을 이용해서 예측;
void lift(const std::vector<CfPt>& points,
          std::vector<CfPt>& hf_comp) {
    ASSERT(!(points.size() & 1) &&  points.size() >= 2);
    hf_comp.resize(points.size() / 2);
    for (int i = 1; i < points.size(); i += 2) {
        const int im3 = max(i-3, 0);
        const int im1 = i-1;
        const int ip1 = min(i+1, points.size()-1);
        const int ip3 = min(i+3, points.size()-1);
        // high freq comp = observed - estimated values;
        hf_comp[i/2] = points[i] - catmull_rom(points[im3], points[im1], points[ip1], points[ip3]);
    }
}
// update
// 고주파 성분 예측 에러가 필터링된 저주파 성분(짝수항)을 계산함
// 짝수항(저주파 성분)에 근방에서 구한 고주파 성분 평균의 절반을 더해줌;
void update(const std::vector<CfPt>& points,
            const std::vector<CfPt>& hf_comp,
            std::vector<CfPt>& lf_comp) {
    ASSERT(!(points.size() & 1));
    lf_comp.resize(points.size() / 2);
    for (int i = 0; i < points.size(); i += 2)
        // high[i/2]은 points 기준으로 (i+1)위치임;
        lf_comp[i/2] = points[i] + ((i==0 ? CfPt(0,0): hf_comp[i/2-1]) + hf_comp[i/2]) / 4;
}
std::vector<CfPt> decimate_polygon(const std::vector<CfPt>& points, const int max_pass) {
    const int orig_sz = points.size();
    int two_power = 1; 
    while (two_power < orig_sz) two_power <<= 1;
    // last element padding;
    std::vector<CfPt> input = points;
    const CfPt q_padd = input.back();
    for (int k = input.size(); k < two_power; k++) 
        input.push_back(q_padd);
    // wavelet passes
    std::vector<CfPt> hf_comp;
    std::vector<CfPt> lf_comp;
    // max_pass = max(max_pass-2, 0); // points.size()<= 2^max_pass;
    int pass = 0;
    while (pass++ < max_pass) {
        if (pass > 1) input.swap(lf_comp);
        lift(input, hf_comp);
        update(input, hf_comp, lf_comp);
    }   
    lf_comp.resize(orig_sz>>pass);
    return lf_comp; //decimated polyline;
};

https://kipl.tistory.com/99

Douglas-Peucker Algorithm