Accurate Image Up-sampling and Down-sampling in Pyramid-based Algorithm

在許多的pyramid-based或multi-scale演算法中，常應用到down-sampling與up-sampling的概念；如Gaussian Pyramid及Laplacian Pyramid。本篇討論在實作上的細節，點出其困難點和解決方法。

1. Scale ratio

在down-sampling影像時，我們常定義down-sampling scale ratio為0.5倍；但也不限制可是任意實數。與之相對的up-sampling scale ratio則是2倍。設計成2-power次方目的是方便軟體實作，當然也有ratio \(\sqrt{2}\)的變形版本。

2. Down-sampling

在down-sampling方面，第一個遇到的問題就是影像大小的決定；若影像大小乘上scale ratio後非整數，是否要四捨五入? 亦或是無條件進位；答案是無條件進位，否則會損失掉一整行的資訊。

常做的步驟是先 low-pass filter (通常是Gaussian kernel) 後跳偶數點取出(0, 2, 4, 6, 8, …)。若沒有先行 low-pass filter則會有較嚴重的 aliasing。而 low-pass filter 的 kernel 設計將與對應 upsampling 的複雜度有關。

3. Up-sampling

與 downsampling 使用的 low-pass filter 相應， upsampling 也要使用相同的 low-pass filter 的權重內插。

1. Initial 2 large images \(I_{large1}, I_{large2}\) with zeros.
   • Put the corresponded value from small image to \(I_{large1}\). That is, all downsamping-skipped pixels will keep zeros. (figure. 1)
   • Put value 1 to \(I_{large2}\), the same position as \(I_{large1}\). (figure. 2)
2. Smooth large images with same low-pass filter.
3. Do pixel-wised division. \(\frac{I_{large1}(x,y)}{I_{large2}(x,y)}\)

 % interpolate, convolve with 2D separable filter
 R = zeros(r,c,k);
 R(1+reven:2:r, 1+ceven:2:c, :) = I;
 R = imfilter(R,filter);
 
 % reweight, brute force weights from 1s in valid image positions
 Z = zeros(r,c,k);
 Z(1+reven:2:r, 1+ceven:2:c, :) = 1;
 Z = imfilter(Z,filter);
 R = R./Z;

4. Advanced  Down-sampling and Up-sampling

這邊 upsampling 時要將兩張 smooth 後的影像 (分別是跳點大圖與跳點填 1 的影像)做點除的動作很麻煩。若是一個經過設計的 low-pass filter，則跳點填 1 的影像經過 low-pass filter 後會是一個常數或 1。意思是我們就可以用一個簡單的乘法甚至是無須點對點相除了。

\[G_{down}=\frac{1}{256}\begin{bmatrix}1&4&6&4&1\\4&16&24&16&4\\6&24&36&24&6\\4&16&24&16&4\\1&4&6&4&1\end{bmatrix}\]

\[G_{up}=\frac{1}{64}\begin{bmatrix}1&4&6&4&1\\4&16&24&16&4\\6&24&36&24&6\\4&16&24&16&4\\1&4&6&4&1\end{bmatrix}\]

如上面兩個 low-pass filter，downsampling 時使用\(G_{down}\)，而 upsampling 時則是將跳點大圖與 \(G_{up}\) filtering後即是內插的結果，無須點對點相除掉權重。因為將跳點 1 的影像跑 \(G_{up}\) kernel的結果是全為 1 的常數影像。

Downsampling流程

1. \(I_{g}=I{\otimes}{G_{down}}\)
2. \(I_{small}=I_{g}\) sample even pixels.

Upsampling流程

1. \(I_{u}=0\)
2. put vaild pixel from \(I_{small}\)  to \(I_{u}\)
3. \(I_{large}=I_{u}{\otimes}{G_{up}}\)

當然我們也可以有3×3的版本

\[G_{down}=\frac{1}{16}\begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}\]

\[G_{up}=\frac{1}{4}\begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}\]