[譯]使用 Python 實現接縫裁剪演算法

09-10

來自專欄掘金翻譯計劃4 人贊了文章

原文地址：Implementing Seam Carving with Python
原文作者：Karthik Karanth
譯文出自：掘金翻譯計劃
本文永久鏈接：https://github.com/xitu/gold-miner/blob/master/TODO1/implementing-seam-carving-with-python.md
譯者：caoyi0905
校對者：yqian1991

使用 Python 實現接縫裁剪演算法

接縫裁剪是一種新型的裁剪圖像的方式，它不會丟失圖像中的重要內容。這通常被稱之為「內容感知」裁剪或圖像重定向。你可以從這張照片中感受一下這個演算法：

照片由 Unsplash 用戶 Pietro De Grandi 提供

變成下面這張：

正如你所看到的，圖像中的非常重要內容 —— 船隻，都保留下來了。該演算法去除了一些岩層和水（讓船看起來更靠近）。核心演算法可以參考 Shai Avidan 和 Ariel Shamir 的原始論文 Seam Carving for Content-Aware Image Resizing。在這篇文章中，我將展示如何在 Python 中基本實現該演算法。

概要

該演算法的工作原理如下：

為每個像素分派一個能量值（energy）
找到能量最低的像素的 8 聯通區域
刪除該區域內所有的像素
重複 1-3，直到刪除所需要保留的行/列數

接下來，假設我們只是嘗試裁剪圖像的寬度，即刪除列。對於刪除行來說也是類似的，至於原因最後會說明。

以下是 Python 代碼需要引入的包：

import sysimport numpy as npfrom imageio import imread, imwritefrom scipy.ndimage.filters import convolve# tqdm 並不是必需的，但它可以向我們展示一個漂亮的進度條from tqdm import trange

能量圖

第一步是計算每個像素的能量值，論文中定義了許多不同的可以使用的能量函數。我們來使用最基礎的那個：

這意味著什麼呢？I 代表圖像，所以這個式子告訴我們，對於圖像中的每個像素和每個通道，我們執行以下幾個步驟：

找到 x 軸的偏導數
找到 y 軸的偏導數
將他們的絕對值求和

這就是該像素的能量值。那麼問題就來了，「你怎麼計算圖像的導數？」，維基百科上的 Image derivations（圖像導數）給我們展示了許多不同的計算圖像導數的方法。我們將使用 Sobel 濾波器。這是一個在圖像上的每個通道上的計算的convolutional kernel（卷積核）。以下是圖像的兩個不同方向的過濾器：

直觀地說，我們可以認為第一個濾波器是將每個像素替換為它上邊的值和下邊的值之差。第二個過濾器將每個像素替換為它右邊的值和左邊的值之差。這種濾波器捕捉到的是每個像素相鄰所構成的 3x3 區域中像素的總體趨勢。事實上，這種方法與邊緣檢測演算法也有關係。計算能量圖的方式非常簡單：

def calc_energy(img): filter_du = np.array([ [1.0, 2.0, 1.0], [0.0, 0.0, 0.0], [-1.0, -2.0, -1.0], ]) # 將一個 2D 的濾波器轉為 3D 的濾波器，為每個通道設置相同的濾波器：R，G，B filter_du = np.stack([filter_du] * 3, axis=2) filter_dv = np.array([ [1.0, 0.0, -1.0], [2.0, 0.0, -2.0], [1.0, 0.0, -1.0], ]) # 將一個 2D 的濾波器轉為 3D 的濾波器，為每個通道設置相同的濾波器：R，G，B filter_dv = np.stack([filter_dv] * 3, axis=2) img = img.astype(float32) convolved = np.absolute(convolve(img, filter_du)) + np.absolute(convolve(img, filter_dv)) # 我們將紅綠色藍三通道中的能量相加 energy_map = convolved.sum(axis=2) return energy_map

可視化能量圖後，我們可以看到：

顯然，像天空和水的靜止部分這樣變化最小的區域，具有非常低的能量（暗的部分）。當我們運行接縫裁剪演算法的時候，被移除的線條一般都與圖像的這些部分緊密相關，同時試圖保留高能量部分（亮的部分）。

找到最小能量的接縫（seam）

我們下一個目標就是找到一條從圖像頂部到圖像底部的能量最小的路徑。這條線必須是 8 聯通的：這意味著線中的每個像素都可以他通過邊或叫角碰到線中的下一個像素。舉個例子，這就是下圖中的紅色線條：

所以我們怎麼找到這條線呢？事實證明，這個問題可以很好地使用動態規劃來解決！

讓我們創建一個名為 M 的 2D 數組來存儲每個像素的最小能量值。如果您不熟悉動態規劃，這簡單來說就是，從圖像頂部到該點的所有可能接縫（seam）中的最小能量即為 M[i,j]。因此，M 的最後一行中就將包含從圖像頂部到底部的最小能量。我們需要從此回溯以查找此接縫中存在的像素，所以我們將保留這些值，存儲在名為backtrack 的 2D 數組中。

def minimum_seam(img): r, c, _ = img.shape energy_map = calc_energy(img) M = energy_map.copy() backtrack = np.zeros_like(M, dtype=np.int) for i in range(1, r): for j in range(0, c): # 處理圖像的左邊緣，防止索引到 -1 if j == 0: idx = np.argmin(M[i - 1, j:j + 2]) backtrack[i, j] = idx + j min_energy = M[i - 1, idx + j] else: idx = np.argmin(M[i - 1, j - 1:j + 2]) backtrack[i, j] = idx + j - 1 min_energy = M[i - 1, idx + j - 1] M[i, j] += min_energy return M, backtrack

刪除最小能量的接縫中的像素

然後我們就可以刪除有著最低能量的接縫中的像素，返回新的圖片：

def carve_column(img): r, c, _ = img.shape M, backtrack = minimum_seam(img) # 創建一個（r，c）矩陣，所有值都為 True # 我們將刪除圖像中矩陣里所有為 False 的對應的像素 mask = np.ones((r, c), dtype=np.bool) # 找到 M 最後一行中最小元素的那一列的索引 j = np.argmin(M[-1]) for i in reversed(range(r)): # 標記這個像素之後需要刪除 mask[i, j] = False j = backtrack[i, j] # 因為圖像是三通道的，我們將 mask 轉為 3D 的 mask = np.stack([mask] * 3, axis=2) # 刪除 mask 中所有為 False 的位置所對應的像素，並將 # 他們重新調整為新圖像的尺寸 img = img[mask].reshape((r, c - 1, 3)) return img

對每列重複操作

所有的基礎工作都已做完了！現在，我們只要一次次地運行 carve_column 函數，直到我們刪除到了所需的列數。我們再創建一個 crop_c 函數，圖像和縮放因子作為輸入。如果圖像的尺寸為（300,600），並且我們想要將其減小到（150,600），scale_c 設置為 0.5 即可。

def crop_c(img, scale_c): r, c, _ = img.shape new_c = int(scale_c * c) for i in trange(c - new_c): # 如果你不想用 tqdm，這裡將 trange 改為 range img = carve_column(img) return img

將它們合在一起

我們可以添加一個 main 函數，讓代碼可以通過命令行調用：

def main(): scale = float(sys.argv[1]) in_filename = sys.argv[2] out_filename = sys.argv[3] img = imread(in_filename) out = crop_c(img, scale) imwrite(out_filename, out)if __name__ == __main__: main()

然後運行這段代碼：

python carver.py 0.5 image.jpg cropped.jpg

cropped.jpg 現在應該顯示以下這樣的圖像:

![]https://karthikkaranth.me/img/pietro_carved.jpg)

行應該怎麼處理呢？

然後，我們可以開始研究怎麼修改我們的循環來換個方向處理數據。或者...只需旋轉圖像就可以運行 crop_c！

def crop_r(img, scale_r): img = np.rot90(img, 1, (0, 1)) img = crop_c(img, scale_r) img = np.rot90(img, 3, (0, 1)) return img

將這段代碼添加到 main 函數中，現在我們也可以裁剪行！

def main(): if len(sys.argv) != 5: print(usage: carver.py <r/c> <scale> <image_in> <image_out>, file=sys.stderr) sys.exit(1) which_axis = sys.argv[1] scale = float(sys.argv[2]) in_filename = sys.argv[3] out_filename = sys.argv[4] img = imread(in_filename) if which_axis == r: out = crop_r(img, scale) elif which_axis == c: out = crop_c(img, scale) else: print(usage: carver.py <r/c> <scale> <image_in> <image_out>, file=sys.stderr) sys.exit(1) imwrite(out_filename, out)

運行代碼：

python carver.py r 0.5 image2.jpg cropped.jpg

然後我們就可以把這張圖：

Photo by Brent Cox on Unsplash

變成這樣：

總結

我希望你是愉快而又收穫地讀到這裡的。我很享受實現這篇論文的過程，並打算構建一個這個演算法更快的版本。比如說，使用相同的計算過的圖像接縫去除多個接縫。在我的實驗中，這可以使演算法更快，每次迭代可以幾乎線性地移除接縫，但質量明顯下降。另一個優化是計算 GPU 上的能量圖，在這裡探討的。

這是完整的程序：

#!/usr/bin/env python"""Usage: python carver.py <r/c> <scale> <image_in> <image_out>Copyright 2018 Karthik Karanth, MIT License"""import sysfrom tqdm import trangeimport numpy as npfrom imageio import imread, imwritefrom scipy.ndimage.filters import convolvedef calc_energy(img): filter_du = np.array([ [1.0, 2.0, 1.0], [0.0, 0.0, 0.0], [-1.0, -2.0, -1.0], ]) # 將一個 2D 的濾波器轉為 3D 的濾波器，為每個通道設置相同的濾波器：R，G，B filter_du = np.stack([filter_du] * 3, axis=2) filter_dv = np.array([ [1.0, 0.0, -1.0], [2.0, 0.0, -2.0], [1.0, 0.0, -1.0], ]) # 將一個 2D 的濾波器轉為 3D 的濾波器，為每個通道設置相同的濾波器：R，G，B filter_dv = np.stack([filter_dv] * 3, axis=2) img = img.astype(float32) convolved = np.absolute(convolve(img, filter_du)) + np.absolute(convolve(img, filter_dv)) # 我們將紅綠色藍三通道中的能量相加 energy_map = convolved.sum(axis=2) return energy_mapdef crop_c(img, scale_c): r, c, _ = img.shape new_c = int(scale_c * c) for i in trange(c - new_c): img = carve_column(img) return imgdef crop_r(img, scale_r): img = np.rot90(img, 1, (0, 1)) img = crop_c(img, scale_r) img = np.rot90(img, 3, (0, 1)) return imgdef carve_column(img): r, c, _ = img.shape M, backtrack = minimum_seam(img) mask = np.ones((r, c), dtype=np.bool) j = np.argmin(M[-1]) for i in reversed(range(r)): mask[i, j] = False j = backtrack[i, j] mask = np.stack([mask] * 3, axis=2) img = img[mask].reshape((r, c - 1, 3)) return imgdef minimum_seam(img): r, c, _ = img.shape energy_map = calc_energy(img) M = energy_map.copy() backtrack = np.zeros_like(M, dtype=np.int) for i in range(1, r): for j in range(0, c): # 處理圖像的左邊緣，防止索引到 -1 if j == 0: idx = np.argmin(M[i-1, j:j + 2]) backtrack[i, j] = idx + j min_energy = M[i-1, idx + j] else: idx = np.argmin(M[i - 1, j - 1:j + 2]) backtrack[i, j] = idx + j - 1 min_energy = M[i - 1, idx + j - 1] M[i, j] += min_energy return M, backtrackdef main(): if len(sys.argv) != 5: print(usage: carver.py <r/c> <scale> <image_in> <image_out>, file=sys.stderr) sys.exit(1) which_axis = sys.argv[1] scale = float(sys.argv[2]) in_filename = sys.argv[3] out_filename = sys.argv[4] img = imread(in_filename) if which_axis == r: out = crop_r(img, scale) elif which_axis == c: out = crop_c(img, scale) else: print(usage: carver.py <r/c> <scale> <image_in> <image_out>, file=sys.stderr) sys.exit(1) imwrite(out_filename, out)if __name__ == __main__: main()

修改於（2018 年 5 月 5 日）： 正如一個熱心的 reddit 用戶所說，通過使用 numba 來加速計算繁重的功能，可以很容易的得到幾十倍的性能提升。要想體驗 numba，只要在函數 carve_column 和 minimum_seam 之前加上 @numba.jit。就像下面這樣：

@numba.jitdef carve_column(img):@numba.jitdef minimum_seam(img):

如果發現譯文存在錯誤或其他需要改進的地方，歡迎到掘金翻譯計劃對譯文進行修改並 PR，也可獲得相應獎勵積分。文章開頭的 本文永久鏈接 即為本文在 GitHub 上的 MarkDown 鏈接。

掘金翻譯計劃是一個翻譯優質互聯網技術文章的社區，文章來源為掘金上的英文分享文章。內容覆蓋 Android、iOS、前端、後端、區塊鏈、產品、設計、人工智慧等領域，想要查看更多優質譯文請持續關注掘金翻譯計劃、官方微博、知乎專欄。