728x90

주어진 이미지(destination image)의 일부분($\Omega$)을 다른 이미지(source image: $g(x, y)$)로 자연스럽게 대체하는 seamless blending의 한 기법인 Possion Image Editing을 살펴보자. 수학적으로는 destination image의 한 영역 $\Omega$에서 source image를 보간(interpolation)하는 함수 $f(x,y)$를 찾는 작업이다. $f$는 보간 영역의 경계($\partial\Omega$)에서는 destination image와 같은 컬러 값($f^{*}$)을 가져야 한다.

그럼 보간의 기준은 무엇이 되어야 하는가? blending이 잘되기 위해서는 보간 영역에서는 source image와 같은 형상으로 보여야 한다. 이미지에서 형상의 인식은 컬러값 자체가 아니라 컬러의 변화인 gradient에 의해서 결정이 된다. 따라서 보간 함수는 source image의 gradient를 최대한 유지하도록 선택되어야 한다. 이제 seamless blending을 주는 보간 함수를 찾는 문제는 source image가 blending 영역의 경계에서는 destination 이미지의 color값을 가지면서 영역 내부에서는 source image의 gradient 값을 최대한 유지하는 함수를 찾는 변분 문제로 귀결된다: source image의 gradient를 $\mathbf{v}(x, y)=\nabla g= (\partial g/\partial x, \partial g / \partial y)$라 하면,

$$ \underset{f}{\text{argmin}} \iint_{\Omega}  | \nabla f - \mathbf{v}|^2 dxdy, \quad\text {with} \quad f = f^*~\text {on}~\partial \Omega.$$ 

위 식을 $f$에 대해서 variation을 취하면$$\iint 2(\nabla \delta f)\cdot(\nabla f - \mathbf{v}) dxdy = - 2 \iint \delta f ( \nabla^2 f - \nabla \cdot \mathbf{v}) dxdy + 2 \iint  \nabla \cdot \left[ \delta f (\nabla f - \mathbf{v})\right] dxdy    $$을 얻을 수 있는데 마지막 항은 total derivative이므로 기여가 없다. 따라서 보간함수 $f$는 다음 방정식을 만족해야 한다:

$$ \nabla^2 f = \nabla \cdot \mathbf{v}, \quad \text {or} \quad \frac {\partial^2 f}{\partial x^2} + \frac {\partial ^2 f}{\partial y^2 } = \frac {\partial v_x }{\partial x}+ \frac {\partial v_y}{\partial y}.$$

보간함수를 찾는 과정은 domain $\Omega$에서 Dirichlet boundary condition $f=f^* ~\text {on} ~\partial\Omega$이 부여된 Poisson 방정식의 해를 찾는 것과 같다는 것을 알려준다.

$\nabla \cdot\mathbf{v}= \nabla^2 g$이므로 Poisson 방정식의 해를 $f(x,y)= g(x,y) + h(x,y)$로 쓰면 풀어야 할 문제는 다음의 Laplace 방정식으로 해를 구하는 문제로 바뀐다.

$$ \nabla^2 h = 0, \quad ~~ h|_{\partial\Omega} = (f^* - g)|_{\partial\Omega}$$

 

** 1차원 예: $f^*(x)=1-\frac{x}{\pi}$, $g(x)=\frac{1}{2} \cos (4x)$ 인 경우, $f(x)=g(x) + h(x)$로 쓰면, $h(x)$는 $h(x=0) = f^*(0) - g(0) = 0.5$, $h(\pi)=f^*(\pi)-g(\pi) = -\frac{1}{2}$의 경계조건을 만족하는 $d^2h/dx^2 = 0$의 해로 주어지는데, $h(x)=\frac{1}{2}- \frac{x}{\pi}$임을 쉽게 알 수 있다. 따라서 $f(x)= \frac{1}{2}-\frac{x}{\pi} +\frac{1}{2} \cos(4x)$로 쓰인다:

출처: Poisson Image Editing J. Matías Di Martino, Gabriele Facciolo, Enric Meinhardt-Llopis

 

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

Poisson Image Editing  (0) 2021.08.03
Sampling Theorem  (0) 2021.05.12
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
Posted by helloktk

댓글을 달아 주세요

728x90

오토바이를 타고 코너를 돌 때 안쪽으로 약간 기울이면 넘어지지 않고 안전하게 돌 수 있다는 사실은 라이더라면 누구나 경험으로 알고 있을 것이다.

1. 왜 기울여야 하는가?

2. 속력 $v$로 반지름 $R$인 코너를 돌 때 얼마나 기울여야 할까?

3. 도로면의 마찰계수는 얼마나 되어야 할까?

https://www.youtube.com/watch?v=ZpV2Bg-WX0w&t=244s

Posted by helloktk

댓글을 달아 주세요

턱을 오르는 공?

Physics 2021. 5. 23. 21:41
728x90

볼링공(반지름: $R$, 회전관성: $\frac{2}{5} mR^2$)이 굴러가다가 턱에 부딪치는 경우를 보자. 충돌이 비탄성적이라면 공은 턱(높이: $h$)을 기준으로 회전해서 턱 위로 올라갈 수 있다. 물론 부딪치기 직전 속도가 너무 작으면 오를 수 없고, 너무 크면 위로 튄다. 어떤 조건일 때 튀지 않고 턱 위로 올라갈 수 있을까?

1. 충돌 전후로 턱에 대한 각운동량이 보존되므로 충돌 직후 각속도 $\omega$는 충돌 전 속도($v$)를 알면 구할 수 있다.

$$ \omega=\frac{7}{2}\left(  1 - \frac{5h}{7R}\right) \frac{v}{R}.$$

2. 역학적 에너지 보존을 이용하면 공이 턱에 완전히 올라서기 위해서는 충돌 직후 각속도 $\omega$가  일정한 크기 이상이어야 한다:

$$ \omega  \ge \sqrt{\frac{10gh}{7R^2}}.$$

3. 충돌 후에는 공의 질량중심은 턱에 대해서 회전을 한다. 이때 구심력 역학을 하는 힘은 턱이 주는 수직항력($F_N$)과 이 수직항력 방향의 중력 성분($mg \cos \theta$)의 차이이다. 너무 빨리 회전하면 공이 턱에 붙어서 돌지 못하고 튕길 수 있다. 튀지 않고 회전하려면 어떤 조건이 들어오는가? 충돌 직후의 운동방정식이

$$mg \cos \theta -F_N = mR \omega^2$$

이므로 공이 튀지 않고, 즉 턱과 접촉을 유지하면서($F_N \ge 0$)  올라가기 위해서는 턱의 높이가 

$$ \frac{h}{R} \ge \frac{7}{17} \approx 0.41$$

을 만족해야 한다.

Posted by helloktk

댓글을 달아 주세요

728x90

comb 함수: 일정한  간격($T$)으로 주어진 message를 샘플링하는 함수.

$$\text{comb}_T(t) := \sum_{n=-\infty}^{\infty} \delta (t- nT)$$

주기가 $T$인 함수다: 

$$ \text{comb}_T(t) = \text{comb}_T(t+T)$$

따라서 Fouries series 전개가 가능하다.

$$\text{comb}_T(t) = \sum_{n=-\infty}^{ \infty}   c_n e^{i 2\pi n t /T}$$

계수 $c_n$은?

\begin{align} c_n :=&\frac{1}{T} \int_{-T/2}^{T/2} \text{comb}_T(t) e^{-i 2\pi n t /T}dt \\ =&  \frac{1}{T}\int_{-T/2}^{T/2} \delta (t) e^{ -i 2\pi n t/T} dt  \\ =&\frac{1}{T} e^{-i 2\pi n (0) /T } = \frac{1}{T}.\end{align}

따라서, $\text{comb}_T(t)$의 Fourier series 전개는 

$$\text{comb}_T(t) = \frac{1}{T} \sum_{n = -\infty}^{\infty} e^{i2\pi  n t/T}.$$

frequency domain에서 delta 함수의 역 Fourier transform은 정의에 의해서

$$ {\cal F}^{-1} [\delta (f-f_0)] = \int \delta (f-f_0) e^{i 2\pi t f }df = e^{i 2\pi t f_0}$$

그럼 $\text{comb}_T(t)$의 Fourier transform은 어떻게 표현되는가?

\begin{align} {\cal F}[\text{comb}_T(t)]=& \frac{1}{T} \sum {\cal F}[ e^{i2\pi n t/T}] \\  =& \frac{1}{T} \sum {\cal F}[ {\cal F}^{-1} [ \delta (f - n/T)]] \\ =& \frac{1}{T} \sum_{n = -\infty}^{\infty} \delta(f - n/T).\end{align} $\text{comb}$ 함수의 Fourier 변환은 frequency domain에서 $\text{comb}$ 함수이고 (up to constant factor),  time domain에서 주기가 $T$일 때 frequency domain에서는 $ 1/T$의 주기를 가진다.

주어진 message $m(t)$에서 일정한 간격 $T$로 샘플링된 message $m_s(t)$는 $\text{comb}$ 함수를 이용하면

$$m_s (t) : = m(t) \text{comb}_T(t) = \sum m(nT) \delta (t- nT)$$

로 표현된다.

양변에 Fourier transform을 적용하면,

\begin{align} M_s(f) = {\cal F} [m_s ] =& {\cal F}[m(t) \text{comb}_T(t)]= {\cal F}[m] * {\cal F}[\text{comb}_T]  \\  =& \frac{1}{T} \sum \int \delta(f' - n /T) M(f- f') df' \\ =& \frac{1}{T} \sum_{n=- \infty}^{\infty}  M(f - n/T) . \end{align}

따라서 message의 spectrum이 band-limited이고, $\text{band-width} \le \frac{1}{2} f_s = \frac{1}{2T}$인 조건을 만족하면 샘플링된 데이터를 이용해서 원 신호를 복원할 수 있다.

이 경우에 low-pass filter 

$$ H(f/f_s) := T \cdot \text{rect}(f/f_s)=\left\{ \begin{array}{ll} T ,& |f/f_s| < 1/2 \\ 0 , & |f/f_s| >1/2,\end{array}\right. $$

을 sampled massage의 Fourier transform에 곱해주면, 원 message의 Fourier transform을 얻는다:

$$ M(f) = H(f) M_s(f).$$

그런데 $M_s(f)$는 frequency domain에서 주기가 $f_s = 1/T$인 주기함수이므로 Fourier series로 표현할 수 있다:($\text{comb}_T$ 함수와 같은 방식으로 하면 계수를 쉽게 찾을 수 있다: Poisson summation formula)

$$M_s(f) = \frac{1}{T}\sum M(f- n f_s ) = \sum_{-\infty}^\infty   m(nT) e^{-i 2\pi nf T}$$

따라서, 

\begin{align} M(f) = & H(f/f_s)   M_s(f) \\ =& H(f/f_s)  \sum  m(nT) e^{-i 2\pi nfT} \\ =& \sum m(nT) \Big(\text{rect}(f/f_s )T  e^{-i 2\pi nTf} \Big) \\=& \sum m(nT) {\cal F} \left[  \text{sinc}  \left( \pi  \frac{t-nT}{T} \right) \right]\end{align}

이므로 양변에 역 Fourier transform을 하면 sampled 된 message $\{m(nT)|n\in Z\}$를 이용해서 원 message를 복원할 수 있는 식을 얻을 수 있다(Whittaker-Shannon interpolation):

$$m(t) = \sum_{n=-\infty}^{\infty}  m(nT) \,\, \text{sinc}\left(  \pi \frac{t-nT}{T} \right) .$$

 

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

Poisson Image Editing  (0) 2021.08.03
Sampling Theorem  (0) 2021.05.12
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
Posted by helloktk

댓글을 달아 주세요

728x90

Lanczos kernel:  a sinc function windowed by the central lobe of a second, longer, sinc function(wikipedia)

$$K(x) = \left\{ \begin{array}{ll}   \text{sinc}(\pi x) \text{sinc}\Big( \frac{\pi x}{a}\Big), & |x| < a \\ 0 ,& |x| \ge a\end{array} \right. = \text{sinc}(\pi x) \text{sinc}\Big( \frac{\pi x}{a}\Big)\text{Box}(|x|<a) $$

$$H(\omega)=\frac{1}{2\pi^2\sqrt{2\pi}}\Big( -(2\pi-3\omega)Si(2\pi-3\omega)+(4\pi -3\omega)Si(4\pi-3\omega)\\+(2\pi +3\omega)Si(2\pi+3\omega)+(4\pi+3\omega)Si(4\pi+3\omega)\Big)$$

// windowed sinc(x); window=sinc(x/3);
static double Lanczos3(double x){
    if (x < 0) x = -x; // symmetric;
    x *= PI;
    if (x < 0.01)    return 1. + (- 5./ 27. + 
        (14. / 1215. - 17. * x * x / 45927.) * x * x) * x * x; 
    else if (x < 3.) return 3. * sin(x) * sin(x / 3.) / x / x;
    else     	     return 0;
};
// interpolation in the horizonal direction: single channel or gray image;
double Lanczos3_line(BYTE *src_line, int srcWidth, int x, double xscale) {
    double halfWidth;
    if (xscale > 1.) halfWidth = 3.;
    else             halfWidth = 3. / xscale;

    double centerx = double(x) / xscale - 0.5;  //center loc of filter in the src_line;
    int left  = (int)floor(centerx - halfWidth);
    int right = (int)ceil(centerx + halfWidth);
    if (xscale > 1) xscale = 1;
    double s = 0;
    double weightSum = 0;
    for (int ix = left; ix <= right; ix++) {   
        double weight = Lanczos3((centerx - ix) * xscale);
        int xx = ix;         // for ix<0 || ix>=srcWidth: repeat boundary pixels
        CLAMP(xx, 0, srcWidth - 1);
        s += weight * src_line[xx];
        weightSum += weight;
    }
    return s / weightSum; 
}

 

bicubic downsample(1/2): alias 발생

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

Poisson Image Editing  (0) 2021.08.03
Sampling Theorem  (0) 2021.05.12
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
Posted by helloktk

댓글을 달아 주세요