Fast Global Image Smoothing Based on Weighted Least Squares
在本篇論文中榨惰，主要將全局光滑問題轉(zhuǎn)換為一個加權(quán)二次能量函數(shù)凉夯，最小化這個能量函數(shù)從而實現(xiàn)圖片光滑的效果李丰，而這個最優(yōu)化問題徐勃，可以轉(zhuǎn)化為一個線性方程組的求解問題辜妓，在求解效率和求解時間上都有明顯的優(yōu)勢苗沧，同時這還是一個全局最優(yōu)的線性系統(tǒng)愉舔。
本次作業(yè)主要對論文的基本算法Separable global smoother for 2D iamge smoothing進(jìn)行了復(fù)現(xiàn)艺配，使用python語言察郁，為了加快計算速度，使用mxnet.ndarray在GPU上進(jìn)行運算妒挎。
1D Fast Global Smoother
對于二維的問題绳锅，我們可以將其分解為1維的情況，所以先求解1維的線性系統(tǒng)酝掩。
對于1D的情況鳞芙，可以定義一個WLS能量函數(shù)如下
$$
J(u) = \sum_{x} ((u_x^h - f_xh)2 + \lambda_t \sum_{i \in N_h(x)} w_{x, i}(gh)(u_xh - u_ih)2)
$$
需要極小化這個能量函數(shù)，相當(dāng)于$\Delta J(u) = 0$，可以等價于求解下面的線性系統(tǒng):
$$
(I_h + \lambda_t A_h) u_h = f_h
$$
使用下面的迭代方法
首先計算向前方向
$$
\tilde{c_x} = c_x / (b_x - \tilde{c_{x-1}} a_x) \
\tilde{f^h_x} = (f_x^h - \tilde{f_{x-1}^h} a_x) / (b_x - \tilde{c_{x-1}} a_x) \
(x = 1, \cdots, W-1)
$$
然后計算向后方向
$$
u_x^h = \tilde{f^h_x} - \tilde{c_x} u_{x+1}^h \quad(x = W - 2, \cdots, 0) \
u_{W-1}^h = \tilde{f_{W-1}^h}
$$
首先計算相似度權(quán)重函數(shù)$w_{p, q}(g)$如下
# 定義計算相似度權(quán)重函數(shù)
def cw_1d(p, q, g, sigma):
'''
計算1d上曲線g上不同位置p和q的相似性原朝，使用sigma作為一個范圍度量
g: ndarray驯嘱，W
p: int
q: int
sigma: float
'''
norm = nd.norm(g[p] - g[q])
return nd.exp(-norm/sigma)
為了避免streaking，每次迭代需要修改$\lambda$的值喳坠，計算公式為
$$
\lambda_t = \frac{2}{3} \frac{4^{T - t}}{4^T -1 }\lambda
$$
計算lambda的代碼如下
# 每次迭代計算lambda
def compute_lamb(t, T, lamb_base):
return 1.5 * 4**(T-t) / (4 ** T - 1) * lamb_base
求解一階全局光滑線性系統(tǒng)
求解1D情況主要使用上圖的(3)和(4)這兩個數(shù)學(xué)公式鞠评，代碼實現(xiàn)如下
# 求解一維的全局光滑線性系統(tǒng)
def compute_1d_fast_global_smoother(lamb, f, g, sigma, ctx):
'''
求解1d fast global smoother，給出lambda, f和g壕鹉，進(jìn)行前向和反向的遞歸求解
'''
w = f.shape[0]
_c = nd.zeros(shape=w-1, ctx=ctx)
_c[0] = -lamb * cw_1d(0, 1, g, sigma) / (1 + lamb * cw_1d(0, 1, g, sigma))
_f = nd.zeros(shape=f.shape, ctx=ctx)
_f[0] = f[0] / (1 + lamb * cw_1d(0, 1, g, sigma))
# 遞歸前向計算
for i in range(1, w-1):
_c[i] = -lamb * cw_1d(i, i + 1, g, sigma) / (
1 + lamb * (cw_1d(i, i - 1, g, sigma) + cw_1d(i, i + 1, g, sigma)) +
lamb * _c[i - 1] * cw_1d(i, i - 1, g, sigma))
_f[i] = (f[i] + _f[i - 1] * lamb * cw_1d(i, i - 1, g, sigma)) / (
1 + lamb * (cw_1d(i, i - 1, g, sigma) + cw_1d(i, i + 1, g, sigma)) +
lamb * _c[i - 1] * cw_1d(i, i - 1, g, sigma))
_f[w-1] = (f[w-1] + _f[w-2] * lamb * cw_1d(w-1, w-2, g, sigma)) / (
1 + lamb * (cw_1d(w-1, w-2, g, sigma)) +
lamb * _c[w-2] * cw_1d(w-1, w-2, g, sigma))
u = nd.zeros(shape=f.shape, ctx=ctx)
u[w - 1] = _f[w - 1]
# 遞歸向后計算
for i in range(w - 2, -1, -1):
u[i] = _f[i] - _c[i] * u[i + 1]
return u.asnumpy()
完成了一維的全局光滑線性系統(tǒng)的求解剃幌，驗證一下其是否有效
首先構(gòu)造一個一維的波動輸入，畫出圖像如下
x1 = np.random.normal(scale=0.2, size=(100))
x2 = np.random.normal(4, 0.2, size=(100))
x = np.concatenate((x1, x2))
plt.plot(np.arange(x.shape[0]), x)
通過一維全局光滑線性系統(tǒng)的求解晾浴，給出參數(shù)$\lambda=900, \sigma=0.07$负乡，得到光滑之后的圖像如下
u = compute_1d_fast_global_smoother(900, nd.array(x, ctx=mx.gpu(0)), nd.array(x, mx.gpu(0)), 0.07, mx.gpu(0))
plt.plot(np.arange(u.shape[0]), u)
可以明顯看出能夠?qū)斎氲囊浑A波動進(jìn)行有效地光滑化，對比于論文里面的其他結(jié)果脊凰，我們認(rèn)為fast global smooth具有計算時間短抖棘，優(yōu)化更好的特點。
2D image separable fast global smooth
對于一張2D的圖片狸涌，問題非常簡單切省，分別在水平和豎直上應(yīng)用1D的solver就能夠求解，只是需要注意帕胆，在計算$w_{p, q}(g)$的時候朝捆，如果是一張RGB的圖片，需要在 channel 維度的向量上計算相似度惶楼。對于這種可分的方法右蹦，雖然很直觀，但是會出現(xiàn)streaking artifact的問題歼捐，為了解決這個問題何陆，在每一次的迭代中，可以修改$\lambda$的值豹储，因為這個值在每次迭代中對稀疏光滑具有顯著的減少贷盲。
下面是可分離全局光滑的代碼實現(xiàn)，只需要不斷在行和列上進(jìn)行計算即可剥扣，同時需要注意巩剖，如果是RGB三通道的圖片，需要在每個通道上分別計算
#可分離的全局圖片光滑
def Separable_global_smoother(f, T, lamb_base, sigma, ctx):
'''
全局圖片光滑算法钠怯，輸入是f和g佳魔，f是2D image, 3 channels
'''
print('origin lamb is {}'.format(lamb_base))
print('sigma is {}'.format(sigma))
H, W, C = f.shape
u = f.copy()
for t in range(1, T+1):
# 計算每一步迭代的lambda_t
lamb_t = compute_lamb(t, T, lamb_base)
# horizontal
for y in range(0, W):
g = u[:, y, :]
for c in range(C):
f_h = u[:, y, c]
u[:, y, c] = compute_1d_fast_global_smoother(lamb_t, f_h, g, sigma, ctx)
# vertical
for x in range(0, H):
g = u[x, :, :]
for c in range(C):
f_v = u[x, :, c]
u[x, :, c] = compute_1d_fast_global_smoother(lamb_t, f_v, g, sigma, ctx)
return u
完成代碼之后，我們讀入一張圖片晦炊，進(jìn)行multi-scale manipulate測試
首先讀入原圖鞠鲜，大小是200x200
origin_img = Image.open('./jay.jpg')
plt.figure(figsize=(5, 5))
plt.title('origin image')
plt.imshow(origin_img)
對小尺度的圖片做fast global smooth
接著將圖片縮小尺度為100 x 100的圖片宁脊，下面是縮小之后的圖片，可以發(fā)現(xiàn)圖片變得更加模糊贤姆，有很多噪點
img_100 = origin_img.resize((100, 100))
plt.figure(figsize=(5, 5))
plt.title('50 x 50 image')
plt.imshow(img_100)
接著我們進(jìn)行一次迭代
lamb_base = 30**2
sigma = 255 * 0.03
ctx = mx.gpu(0)
img = np.array(img_100)
img = nd.array(img, ctx=ctx)
下面是一次迭代的結(jié)果榆苞，可以發(fā)現(xiàn)圖片已經(jīng)變得比較光滑，但是會出現(xiàn)條紋霞捡，具體可以看看下面紅框的部分
T = 1
u1 = Separable_global_smoother(img, T, lamb_base, sigma, ctx)
show_u = u1.astype('uint8').asnumpy()
plt.figure(figsize=(5, 5))
plt.title('1 iteration smooth result')
plt.imshow(show_u)
經(jīng)過第二次迭代坐漏，下面是迭代結(jié)果，關(guān)注于兩張圖片的紅框部分碧信，可以發(fā)現(xiàn)兩次迭代具有比較好的改善效果
T = 2
u2 = Separable_global_smoother(img, T, lamb_base, sigma, ctx)
show_u = u2.astype('uint8').asnumpy()
plt.figure(figsize=(5, 5))
plt.title('2 iteration smooth result')
plt.imshow(show_u)
三面是三次迭代之后的結(jié)果赊琳，可以發(fā)現(xiàn)圖片更加光滑了
T = 3
u3 = Separable_global_smoother(img, T, lamb_base, sigma, ctx)
show_u = u3.astype('uint8').asnumpy()
plt.figure(figsize=(5, 5))
plt.title('3 iteration smooth result')
plt.imshow(show_u)
對原始圖片做 fast global smooth
lamb_base = 30**2
sigma = 255 * 0.03
ctx = mx.gpu(0)
img = np.array(origin_img)
img = nd.array(img, ctx=ctx)
經(jīng)過一次迭代之后的結(jié)果，雖然仍然存在條紋音婶，但是比小尺度的圖片效果好慨畸，這是因為小尺度的圖片有更多的噪聲和不光滑性
T = 1
u1 = Separable_global_smoother(img, T, lamb_base, sigma, ctx)
show_u = u1.astype('uint8').asnumpy()
plt.figure(figsize=(5, 5))
plt.title('1 iteration smooth result')
plt.imshow(show_u)
經(jīng)過第二次迭代之后的結(jié)果
T = 2
u2 = Separable_global_smoother(img, T, lamb_base, sigma, ctx)
show_u = u2.astype('uint8').asnumpy()
plt.figure(figsize=(5, 5))
plt.title('2 iteration smooth result')
plt.imshow(show_u)
下面是三次迭代之后的結(jié)果，可以發(fā)現(xiàn)圖片越來越光滑
T = 3
u3 = Separable_global_smoother(img, T, lamb_base, sigma, ctx)
show_u = u3.astype('uint8').asnumpy()
plt.figure(figsize=(5, 5))
plt.title('3 iteration smooth result')
plt.imshow(show_u)
與Guided Image Filter的對比
fast global image smooth是隱式求解衣式，其將問題轉(zhuǎn)移為一個優(yōu)化問題，然后再轉(zhuǎn)移為一個線性系統(tǒng)的求解檐什，而線性系統(tǒng)的求解有比較成熟的解法碴卧，從而在計算效率和時間上有所提升，同時這還是一個全局最優(yōu)的解法乃正。
反觀guided image filter住册，這篇文章我并沒有非常仔細(xì)地閱讀，通過大概的閱讀瓮具，我發(fā)現(xiàn)其是一種顯示的求解荧飞，通過局部的線性關(guān)系，將guided image的光滑性質(zhì)轉(zhuǎn)移到源圖片上名党，通過最小化源圖片與光滑圖片之間的差異叹阔，將問題轉(zhuǎn)移為一個嶺回歸問題(linear ridge regression)，顯示計算出雙邊濾波的數(shù)值传睹，通過其進(jìn)行光滑化耳幢。因為其模型的構(gòu)建是在局部上進(jìn)行，所以其存在解的局限性欧啤。
總結(jié)
通過本次作業(yè)睛藻，了解到光滑化圖片的一些方法總結(jié)，復(fù)現(xiàn)了第一篇論文的算法邢隧，比較簡單店印，沒有過多的閱讀論文的擴展內(nèi)容。對于guided image filter倒慧，沒有太過仔細(xì)的閱讀按摘，只是大體看了一下論文的核心想法包券，所以理解可能還不到位，有一些誤解院峡。
