Image Matting: Knockout method

Image Matting은 영상에서 전경(foreground)과 배경(background)이 혼합되어 있는 픽셀을 분리하여, 각 픽셀의 전경 색상과 투명도(alpha)를 추정하는 기술이다. 특히 머리카락, 털, 연기, 반투명 물체와 같이 단순한 이진 분할(segmentation)만으로는 정확하게 추출하기 어려운 물체를 자연스럽게 분리하는 데 사용된다. Matting에서는 각 픽셀의 색상이

\[I=\alpha F+(1-\alpha)B\]

로 표현된다고 가정한다. \(I\)는 입력 영상의 픽셀 값, \(F\)는 전경의 색상, \(B\)는 배경의 색상, \(\alpha\)는 전경의 불투명도(alpha)이다. 하나의 입력 영상만으로는 \(F\), \(B\), \(\alpha\)를 동시에 구해야 하므로 미지수가 방정식보다 많아 해를 직접 구할 수 없다. 따라서 추가적인 정보나 가정이 필요하다.

Knockout Method는 이러한 문제를 해결하기 위해 사용자가 입력한 trimap을 이용하는 대표적인 interactive image matting 기법이다. Trimap은 영상을 전경, 배경, 그리고 전경과 배경이 혼합되어 있는 미지 영역의 세 영역으로 구분한 영상이다. 전경과 배경 영역에서는 이미 물체의 소속이 결정되어 있으므로 alpha 값은 각각 1과 0으로 고정된다.

Knockout Method에서는 미지 영역의 각 픽셀에 대해 주변의 전경 영역과 배경 영역에서 후보 픽셀을 선택하여 전경 색상 \(F\)와 배경 색상 \(B\)를 추정한다. 그런 다음  matting 방정식을 이용하여 alpha 값을 계산한다. 일반적으로 여러 후보의 전경·배경 조합을 시험한 후, 입력 영상과 가장 잘 일치하는 조합을 선택하여 최종적인 전경 색상과 alpha 값을 결정한다.

이 방법은 머리카락이나 털처럼 복잡한 경계에서도 비교적 자연스러운 alpha 값을 얻을 수 있으며, 사용자의 간단한 trimap만으로 동작한다는 장점이 있다. 그러나 결과의 품질은 trimap의 정확도와 전경·배경 색상의 추정에 크게 의존한다. 또한 미지 영역이 넓거나 전경과 배경의 색상이 매우 유사한 경우에는 정확한 alpha 값을 추정하기 어렵다. 이러한 한계에도 불구하고 Knockout Method는 사용자 입력을 이용한 image matting의 기본 개념을 제시한 대표적인 방법으로, 이후 Bayesian Matting, Closed-form Matting, KNN Matting 등 다양한 matting 알고리즘의 발전에 중요한 기반이 되었다.

Ref: https://grail.cs.washington.edu/projects/digital-matting/image-matting/  

세번째 이미지 = alpha 값이 적용된 전경(Gandalf)

// knockout method;
// trimap을 만들 때 전경/배경/중간 영역(경계) 구분;
#define BACKGROUND 0    // 배경 마스크 색상;
#define FOREGROUND 255  // 전경 마스크 색상;
#define UNKNOWN    128  // 경계 영역의 생상;
#define EDGEMARK   3    // 전경과 배경의 경계선을 표시하는 색상
// 주어진 픽셀에서 경계점까지 떨어진 거리(제곱)에 따라 경계점을 
// 정렬하기 위해 필요함;
struct PtDist {
    int x, y, d;
    PtDist() {}
    PtDist(int x, int y): x(x), y(y), d(0) {}
};
struct RGBTRIO {
    double rgb[3];  // b-g-r
};
static 
bool compare(const PtDist& a, const PtDist& b) {
    // 거리 제곱의 ascending order로 정렬;
    return a.d < b.d;
}
// 최소거리의 DISTANCE_THRESHOLD배 이내에 있는 경계 픽셀만을 이용해서 
// alpha값을 추정한다:
#define DISTANCE_THRESHOLD  (5.0)
static
RGBTRIO estimateColor(int x0, int y0, CRaster& raster, 
                   std::vector<PtDist>& pts) {
    for (int i = pts.size(); i-->0;) {
        int x = pts[i].x - x0; 
        int y = pts[i].y - y0;
        pts[i].d = x * x + y * y; 
    }
    std::sort(pts.begin(), pts.end(), compare);
    const double minDist = sqrt(double(pts[0].d));
    ASSERT(minDist > 0);
    const double maxDist = DISTANCE_THRESHOLD * minDist;
    const double inv_diff = 1.0/ (maxDist - minDist);
    double wsum = 0, rsum = 0, gsum = 0, bsum = 0, d;
    for (int i = 0; i < pts.size(); i++) { // sorted data;
        if ((d = sqrt(double(pts[i].d))) < maxDist) {
            double w = (maxDist - d) * inv_diff;
            DWORD q = raster.GetPixel0(pts[i].x, pts[i].y);
            bsum += w * ((q      ) & 0xFF); // blue;
            gsum += w * ((q >>  8) & 0xFF); // green;
            rsum += w * ((q >> 16) & 0xFF); // red;
            wsum += w;
        }
        else break;
    }
    if (wsum == 0) wsum = 1;
    RGBTRIO Q;
    Q.rgb[0] = (bsum / wsum);
    Q.rgb[1] = (gsum / wsum);
    Q.rgb[2] = (rsum / wsum);
    return Q;
}
#define AddVec(A,B,C)	{C[0]=A[0]+B[0];C[1]=A[1]+B[1];C[2]=A[2]+B[2];}
#define SubVec(A,B,C)	{C[0]=A[0]-B[0];C[1]=A[1]-B[1];C[2]=A[2]-B[2];}
#define NormSq(A)       (A[0]*A[0]+A[1]*A[1]+A[2]*A[2])
#define DotProd(A,B)	(A[0]*B[0]+A[1]*B[1]+A[2]*B[2])
#define ScaleVec(A,s)   {A[0]*=s;A[1]*=s;A[2]*=s;}
static
double estimateAlpha(double F[3], double B[3], double C[3]) {
    double N[3], V[3], Bp[3];
    SubVec(F, B, N);						//N=F-B;
    double nn = NormSq(N);					//nn=N.N;
    if (nn == 0) return 1;	
    SubVec(C, B, V);						//V=C-B;
    double proj = DotProd (N, V) / nn;		//proj=(V.N)/(N.N);
    ScaleVec(N, proj);						//N=N(V.N)/(N.N);
    SubVec(C, N, Bp);						//Bp=C-N(V.N)/(N.N);
    //
    SubVec(F, Bp, N);						//N=F-Bp;
    nn = NormSq(N);							//nn=N.N;
    if (nn == 0) return 1;
    SubVec(C, Bp, V);						//V=C-Bp;
    proj = DotProd(N, V) / nn;				//proj=(N.V)/(N.N);

    return proj < 0 ? 0: proj > 1 ? 1: proj;
}
void FindMatt(CRaster& raster, CRaster& trimap, CRaster& alphaMap) {
    ASSERT((trimap.GetBPP()==8) && (raster.GetBPP()==24));
    const CSize sz = raster.GetSize();
    alphaMap.SetDimensions(sz, 32);// Bitmap with alpha-channel;
    std::vector<PtDist> ptFore = binaryTracing(trimap, FOREGROUND);
    std::vector<PtDist> ptBack = binaryTracing(trimap, BACKGROUND);
    
    double C[3];
    for (int y = 0; y < sz.cy; y++) {
        BYTE *p = (BYTE *)trimap.GetLinePtr(y);
        BYTE *q = (BYTE *)raster.GetLinePtr(y);
        BYTE *r = (BYTE *)alphaMap.GetLinePtr(y);
        for (int x = 0; x < sz.cx; x++) {
            if (UNKNOWN == *p) {// unknown pixel(0=background,255=foreground);
                RGBTRIO Qf = estimateColor(x, y, raster, ptFore);
                RGBTRIO Qb = estimateColor(x, y, raster, ptBack);
                C[0] = q[0]; C[1] = q[1]; C[2] = q[2];
                double alpha = estimateAlpha(Qf.rgb, Qb.rgb, C);
                // if ( alpha >= 0.5)
                r[0] = (int)max(0, min(255, Qf.rgb[0]));
                r[1] = (int)max(0, min(255, Qf.rgb[1]));
                r[2] = (int)max(0, min(255, Qf.rgb[2]));
                r[3] = int(alpha * 255);       //[0:1]->[0:255]
            } else if (FOREGROUND == *p) {
                r[0] = q[0];
                r[1] = q[1];
                r[2] = q[2];
                r[3] = 0xFF;
            }
            p++; q += 3; r += 4;
        }
    }
}