Geometry & Recognition

Contrast Limited Adaptive Histogram Equalization (CLAHE). CLAHE는 영상의 평탄화 (histogram equalization) 과정에서 contrast가 과도하게 증폭이 되는 것을 방지하도록 설계된 adaptive algorithm의 일종이다. CLAHE algorithm은 전체 영상 영역을 바로 적용하지 않고 tile이라 불리는 작은 영역으로 영상을 분할하여 tile 별로 적용한다. 그리고 인접하는 tile 간에 bilinear 보간을 사용함으로써 tile 경계에서 급격한 변화가 생기는 것을 방지한다. gray 영상에 CLAHE 알고리즘을 적용하면 영상의 contrast을 개선해 준다. 그리고 컬러 영상에도 적용을 할 수 있는데, 보통 luminance 채널에만 적용한 결과(HSV로 변환 후 V에 대해서만 적용)가 RGB 각 채널별로 적용하는 것보다 좋은 결과를 준다.

아래는 RGB 영상의 각 채널에 CLAHE 알고리즘을 적용한 결과이다.

rgn: 히스토그램을 구하는 이미지 상의 영역;

tile: adaptive HE가 적용되는 영역

첫 행/열 tile의 폭/높이 = rgn 폭/높이의 절반

마지막 tile 크기 = 이미지의 나머지 폭/높이 

cliplimit = 각 영역의 히스토그램 슬롯당 들어가는 최대 픽셀 수

/* "Graphics Gems IV" 의 code를 수정함;
** 2023-01-13 updated: 이미지 사이즈가 rgn 사이즈의 정수배가 되지 않을 때 문제 해결;*/
int CLAHE ( BYTE* image, int width, int height,
            BYTE gMin/*0*/, BYTE gMax/*255*/, int rgn_nx/*16*/, int rgn_ny/*16*/,
            int bins/*256*/, double fcliplimit )
{
    std::vector<int> map_array(rgn_nx * rgn_ny * bins);
    int rgn_xsz		= width / rgn_nx;
    int rgn_ysz		= height / rgn_ny; 
    int rgn_area	= rgn_xsz * rgn_ysz;
    int clipLimit	= int( fcliplimit * ( rgn_xsz * rgn_ysz ) / bins );
    clipLimit = ( clipLimit < 1 ) ? 1 : clipLimit;
    //  
    /* calculate greylevel mappings for each contextual region */
    for (int iy = 0; iy < rgn_ny; iy++) {
        for (int ix = 0; ix < rgn_nx; ix++) {
            int *hist = &map_array[bins * ( iy * rgn_nx + ix )];
            int start = (iy * rgn_ysz) * width + ix * rgn_xsz;
            RgnHistogram (&image[start], width, rgn_xsz, rgn_ysz, hist, bins);
            ClipHistogram ( hist, bins, clipLimit );
            //convert hist to cuimulative histogram normalized to [gMin=0, gMax=255]
            MapHistogram ( hist, gMin, gMax, bins, rgn_area );
        }
    }

    /* bilinearInterp greylevel mappings to get CLAHE image */
    /* 첫열/행에 해당하는 타일은 rgn의 절반 크기만 처리하므로 ix(iy)는 0~rgn_nx(rgn_ny)까지임*/
    int szx, szy, ixl, ixr, iyt, iyb;
    BYTE *first_tile = &image[0]; // 같은 iy를 갖는 첫 타일의 주소;
    for (int iy = 0; iy <= rgn_ny; iy++ ) {
        if ( iy == 0 ) {				
            // 첫 타일은 절반만;
            szy = rgn_ysz / 2; iyt = iyb = 0;
        } else if ( iy == rgn_ny ) {
            // 마지막 타일은 나머지 전부;
            szy = height - ((rgn_ny-1)*rgn_ysz + rgn_ysz/2);
            iyt = rgn_ny - 1; iyb = iyt;
        } else {
            szy = rgn_ysz; iyt = iy - 1; iyb = iyt + 1;
        }
        BYTE *ptile = &first_tile[0]; //각 타일의 시작 주소;
        for (int ix = 0; ix <= rgn_nx; ix++ ) {
            if ( ix == 0 ) {	
                //첫 타일은 절반만;
                szx = rgn_xsz / 2; ixl = ixr = 0;
            } else if ( ix == rgn_nx ) {		
                //마지막 타일은 나머지 전부;
                szx = width - ((rgn_nx-1)*rgn_xsz + rgn_xsz/2);
                ixl = rgn_nx - 1; ixr = ixl;
            } else {
                szx = rgn_xsz; ixl = ix - 1; ixr = ixl + 1;
            }
            // cumulative histogram data;
            int *LU = &map_array[bins * ( iyt * rgn_nx + ixl )];
            int *RU = &map_array[bins * ( iyt * rgn_nx + ixr )];
            int *LB = &map_array[bins * ( iyb * rgn_nx + ixl )];
            int *RB = &map_array[bins * ( iyb * rgn_nx + ixr )];
            BilinearInterp (ptile, width, LU, RU, LB, RB, szx, szy );
            ptile += szx;			  
        }
        first_tile += szy * width;
    }
    return 0;						 
}

void ClipHistogram ( int* hist, int gLevels, int clipLimit ) {
    int excess = 0;
    for (int i = 0; i < gLevels; i++ ) { /* calculate total number of excess pixels */
        int diff =  hist[i] - clipLimit;
        if ( diff > 0 ) excess += diff;	 /* excess in current bin */
    };

    /* clip histogram and redistribute excess pixels in each bin */
    int incr = excess / gLevels;		/* average binincrement */
    int upper =  clipLimit - incr;		/* bins larger than upper set to cliplimit */
    for (int i = 0; i < gLevels; i++ ) {
        if ( hist[i] > clipLimit ) hist[i] = clipLimit; /* clip bin */
        else {
            if ( hist[i] > upper ) {			/* high bin count */
                excess -= hist[i] - upper;
                hist[i] = clipLimit;
            } else {							/* low bin count */
                excess -= incr;
                hist[i] += incr;
            }
        }
    }

    while ( excess ) { /* redistribute remaining excess  */
        int start = 0;
        while ( excess && start < gLevels) {
            int step = gLevels / excess;
            if ( step < 1 ) step = 1;		 /* step size at least 1 */
            for (int i = start; i < gLevels && excess; i += step) 
                if (hist[i] < clipLimit) { 
                    hist[i]++; excess--;
                }
            start++;
        }
    }
}
void BilinearInterp ( BYTE * image, int stride, 
                    int* LU, int* RU, int* LB,  int* RB,
                    int rgn_xsz, int rgn_ysz ) {
    int area = rgn_xsz * rgn_ysz; /* Normalization factor */
    for (int y = 0, yrev = rgn_ysz; y < rgn_ysz; y++, yrev--) {
        BYTE *line = &image[y * stride];
        for (int x = 0, xrev = rgn_xsz; x < rgn_xsz; x++, xrev-- ) {
            int v = line[x]; /* get histogram bin value */
            v = (yrev * ( xrev * LU[v] + x * RU[v] ) + y * ( xrev * LB[v] + x * RB[v] ) ) / area;
            line[x] = v > 255 ? 0xFF: v < 0 ? 0x00: v;
        }
        //image += stride - rgn_xsz;  // goto the beginning of rgn's next-line;
    }
}
void RgnHistogram ( BYTE* image, int stride, int rgn_xsz, int rgn_ysz, 
                        int* hist, int gLevels) {
    // image is pointing the beginnign of a given region;
    for (int i = 0; i < gLevels; i++ ) hist[i] = 0;
    for (int y = 0; y < rgn_ysz; y++ ) {
        BYTE *line = &image[y * stride];
        for (int x = 0; x < rgn_xsz; x++)
            hist[line[x]]++;
    }
}
// transform hist[] to a normalized cumulative histogram;
void MapHistogram ( int* hist, BYTE gMin, BYTE gMax, int gLevels, int rgn_area ){
    double scale = double( gMax - gMin ) / rgn_area;
    int iMin = int(gMin);
    for (int i = 0, sum = 0; i < gLevels; i++ ) {
        sum += hist[i];
        int a = int(iMin + sum * scale );
        hist[i] = a > gMax ? gMax: a < gMin ? gMin: a;
    }
}

n이 양수일 때 n 과 n-1은 짝홀/홀짝의 짝이므로 2의 파워가 아니면 이진수로 표현할 때 한 곳에서 비트 차이가 난다. 따라서 AND연산을 하면 0이 아니다.  그런데 n이 2의 파워이면 최상위 비트만 1이고, n-1은 n의 최상위 비트를 제외한 하위비트 모두가 1로 구성되므로 AND 연산을 하면 0이다.

예:   n=6 = 110,  6-1=101 -->  6 & 5 = 100;

       n=8 = 1000, 8-1=0111 --> 8 & 7=0000

// n이 양수이고, n-1과 겹치는 비트가 없으면 된다;
bool IsPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

n>1 일 떄 2로 나누기를 계속할 때 1을 제외한 홀수가 나오면 안됨; 

bool IsPowerOf2(int n) {
    if (n == 1) return true;
    if (n == 0 || n & 1) return false;
    return IsPowerOf2(n >> 1);
} // n == 0;

x보다 크기 않은 2^i을 구한 후 x와 같은가 체크;

bool IsPowerof2(int x){
    int i = 0;
    while ((1 << i) < x) i++;
    if (x == (1 << i)) return true;
    return false;
}

2의 파워이면 log_2(n) = 자연수 이므로 ceil과 floor가 같다.

bool IsPowerOf2(int n) {
   if (n == 0) return false;
   return (ceil(log2(n)) == floor(log2(n)));
}

주어진 자연수보다 작지 않은 최소의 2^n;

int NextPowerOf2(int n) { //32-bit;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;    
} // NextPowerOf2(5) -> 8; NextPowerOf2(8) -> 8;

// labeling using depth-first search; non-recursive version;
int GetConnectedComponents(BYTE *image, int w, int h, int *table) {
    int label = 0;    // starting label = 1;
    std::vector<int> stack(w * h);
    // initialize the table;
    for (int k = npixs; k-- > 0;) 
        table[k] = image[k] ? -1: 0;  // Foreground = -1; Background = 0;

    for (int pos = w * h; pos-- > 0;) {
        if (table[pos] == -1) { // Foreground;
            ++label;            // assign next label;
            int top = -1;       // stack initialization;
            stack[++top] = pos;
            while (top >= 0) {
                int adj = stack[top--];
                int xx = adj % w;
                int yy = adj / w;
                if (table[adj] == -1) {// Foreground;
                    table[adj] = label;
                    // check 4-way connectivity;
                    if (xx + 1 < w) stack[++top] = adj + 1; //RIGHT;
                    if (yy + 1 < h) stack[++top] = adj + w; //BOTTOM;
                    if (yy > 0)     stack[++top] = adj - w; //TOP;
                    if (xx > 0)     stack[++top] = adj - 1; //LEFT;
                }
            }
        }
    }
    return label;    // total # of CCs;
};

빠른 속도의 비행기와 반대방향으로 나는 새가 정면충돌을 한다. 새는 비행기의 앞에 부딪힌 후 비행기와 같이 움직이게 된다(대부분은 중간에 떨어진다). 충돌에 의해서 새의 속도가 반대방향으로 바뀌었으므로 충돌 과정에서 새의 속도가 0인 순간이 있었을 것이다(속도는 시간의 연속함수이고, 방향이 변하면 성분의 부호가 변했음을 의미한다. 따라서 중간에 0이 되는 순간이 있어야 한다). 새의 속도가 0이라는 의미는 비행기도 그 순간 속도가 0이란 의미이므로(비행기가 새를 가르고 지나지 않았으므로) 새가 순간적이나마 비행기를 멈추었음을 의미할 것이다. 정말로 새가 자신보다도 엄청나게 더 무겁고 빠르게 움직이는 비행기를 순간적으로 정지시켰을까?

공기 저항이 없을 때 물체를 $v_0$ 속력으로 위로 던지면 최고점에 올라가는데 걸리는 시간과 다시 내려오는데 걸리는 시간은 동일하게 $t_{ff} = v_0/g$로 주어진다. 공기 저항이 있는 경우는 어떻게 될지 구체적으로 계산해보자.

반지름이 $R$인 공 모양의 물체가 속력의 제곱에 비례하는 공기 저항(끌림힘) $D= \frac{1}{2} C\rho_{air} A v^2 \approx  0.2 \rho_{air} \pi R^2 v^2$을 받을 때, 올라가는 동안 운동 방정식은 (물체가 받는 공기의 부력도 고려해야 하지만 여기서는 무시한다. 부력은 $g$을 약간 줄이는 효과를 만든다)

$$  m \frac{dv}{dt} = -mg -\ 0.2   \rho_{air} \pi R^2  v^2, $$

$$ \rightarrow  \quad \frac{dv}{dt} = -g (1 + \gamma^2 v^2) , \quad\quad  \gamma^2 =  0.2 \frac{\pi R^2 \rho_{air} }{mg} .$$

$\gamma$는 내려오는 과정에서 terminal speed의 역수를 의미한다. 시간에 대해 적분을 해서 속도를 구하면,

$$ v(t) = \frac{1}{\gamma} \tan \Big( -\gamma gt + \arctan(\gamma v_0) \Big)$$

최고점에 도달하는데 걸리는 시간은 $v(t_{up})=0$ 에서

$$ t_{up} = \frac{1}{\gamma g} \arctan(\gamma v_0) = \frac{v_0}{g} \Big(1 - \frac{(\gamma v_0)^2}{3}+....\Big) $$

로 주어지므로 공기저항이 없을 때보다 더 짧다. 최고점의 높이는

$$ h_{max} = \int_0^{t_{up}} v(t) dt = \frac{1}{\gamma^2 g} \ln \sqrt{ 1 + (\gamma v_0)^2 } =\frac{v_0^2}{2g} \Big( 1- \frac{(\gamma v_0)^2}{2 }+...\Big)$$

로 주어지므로 역시 공기 저항이 없을 때보다 낮다.

다시 내려오는 과정에서 중력과 끌림힘이 반대방향이므로 운동 방정식은

$$ \frac{dv}{dt}= -g (1 -\gamma^2 v^2)$$

로 주어지고, 이를 적분하면 (출발 시간을 $t=0$으로)

$$ v(t) = -\frac{1}{\gamma} \tanh (\gamma g t)$$

이를 다시 적분하면 낙하시간에 따른 높이를 얻을 수 있다: $h(0)=h_{max}$

$$ h(t) = \frac{1}{\gamma^2 g} \ln \frac{ \sqrt{ 1+ (\gamma v_0)^2 } }{ \cosh( \gamma gt)}$$

따라서 바닥에 떨어지는데 걸리는 시간 $t_{dn}$은: $ h(t_{dn}) = 0$

$$t_{dn} = \frac{1}{\gamma g}\text{arccosh}\sqrt{1+(\gamma v_0)^2} =\frac{1}{\gamma g} \ln \left(\gamma v_0 + \sqrt{1+ (\gamma v_0)^2 } \right) = \frac{v_0}{g}\Big( 1  -  \frac{ (\gamma v_0)^2 }{6}+...\Big)$$

두 시간을 비교해보면 위로 던져진 물체가 최고점에 올라가는데 걸리는 시간보다 다시 내려오는데 걸리는 시간이 더 길다는 것을 볼 수 있다:

$$ {t_{dn} - t_{up}} \approx  \frac{(\gamma v_0)^2}{6} t_{ff}$$

$v_0 =10\text{m/s}$로 ($\rightarrow t_{ff} = 1.02\text{s}$, $v_{terminal} \approx 36.6\text{m/s}$) 야구공을 공중으로 던지는 경우를 예로 들면, 차이는 대략 0.013초 정도로 계산된다. 던지는 속력이 종단속력에 가깝거나 더 크면 근사식을 사용할 수 없고 정확한 계산식을 이용해야 한다.

$v_0 = 40\text{m/s}$, $1/\gamma=36.6 \text{m/s}$ 일 때,