面向大象程式設計
很多時候大家覺得動态規劃算法沒什麼實際作用。一方面是因為 LeetCode 上很多題目是簡化版，隻是讓你求一個「最大值」，而不是真正去求最優解。另一方面可能是因為真的沒有接觸過實際場景中的動态規劃算法。
那麼，今天就給大家看一篇文章，講述動态規劃算法在圖檔進行中的一個實際應用 —— 接縫裁剪（seam carving）。這篇文章的作者是 Avik Das，原文是英文文章，我将其翻譯為了中文。
什麼是所謂「接縫裁剪」呢？一句話概括，就是對圖檔進行橫向或縱向的壓縮，且壓縮後的結果很自然。看一段視訊來直覺感受一下吧：
這篇文章我認為寫的非常好，使用實際的案例幫大家了解動态規劃算法，有詳細的例子和圖解。同時，這篇文章對動态規劃的求解過程也講解得非常清晰，完全按照我所講的「動态規劃解題四步驟」來求解。文章中也詳細講解了「back 數組」的技巧，可以仔細體會。
以下是文章内容。
- 原文作者：Avik Das[1]
- 原文位址：Real-world dynamic programming: seam carving[2]
- 譯者：nettee
我們一直認為動态規劃（dynamic programming）是一個在學校裡學習的技術，并且隻是用來通過軟體公司的面試。實際上，這是因為大多數的開發者不會經常處理需要用到動态規劃的問題。本質上，動态規劃可以高效求解那些可以分解為高度重複子問題的問題，是以在很多場景下是很有用的。
在這篇文章中，我将會仔細分析動态規劃的一個有趣的實際應用：接縫裁剪（seam carving）。Avidan 和 Shamir 的這篇文章 Seam Carving for Content-Aware Image Resizing[3] 中詳細讨論了這個問題以及提出的技術（搜尋文章的标題可以免費擷取）。
環境敏感的圖檔大小調整
為了用動态規劃解決實際問題，我們需要将問題模組化為可以應用動态規劃的形式。本節介紹了這個問題的必要的準備工作。
論文的原作者介紹了一種在智能考慮圖檔内容的情況下改變圖檔的寬度或高度的方法，叫做環境敏感的圖檔大小調整（content-aware image resizing）。後面會介紹論文的細節，但這裡先做一個概述。假設你想調整下面這個沖浪者圖檔的大小。
一個沖浪者在平靜的海面中間清晰可見的俯視圖，右邊是身後洶湧的海浪。圖檔來自 Pixabay 上的
Kiril Dobrev
[4]。
論文中詳細讨論了，有多種方法可以減少圖檔的寬度。我們最先想到的是裁剪和縮放，以及它們相關的缺點。删除圖檔中部的幾列像素也是一種方法，但你也可以想象得到，這樣會在圖檔中留下一條可見的分割線，左右的内容無法對齊。而且即使是這些方法全用上了，也隻能删掉這麼點圖檔：
嘗試通過裁掉圖檔的左側和中間部分來減少圖檔寬度。裁掉中間會在圖檔中留下一條可見的分割線。
Avidan 和 Shamir 在他們的論文中展示的是一個叫做接縫裁剪的技術。它首先會識别出圖檔中不太有意義的“低能量”區域，然後找到穿過圖檔的能量最低的“接縫”。對于減少圖檔寬度的情況，接縫裁剪會找到一個豎向的、從圖檔頂部延伸到底部、下一行最多向左或向右移動一個像素的接縫。
在沖浪者的圖檔中，能量最低的接縫穿過圖檔中部水面最平靜的位置。這和我們的直覺相符。
沖浪者圖檔中發現的最低能量接縫。接縫通過一條五個像素寬的紅線來可視化，實際上接縫隻有一個像素寬。
通過識别出能量最低的接縫并删除它，我們可以把圖檔的寬度減少一個像素。不斷重複這個過程可以充分減少圖檔的寬度。
寬度減少了 1024 像素後的沖浪者圖檔。
這個算法删除了圖檔中間的靜止水面，以及圖檔左側的水面，這仍然符合我們的直覺。和直接剪裁圖檔不同的是，左側水面的質地得以保留，也沒有突兀的過渡。圖檔的中間确實有一些不是很完美的過渡，但大部分的結果看起來很自然。
定義圖檔的能量
這個算法的關鍵在于找到能量最低的接縫。要做到這一點，我們首先定義圖檔中每個像素的能量，然後應用動态規劃算法來尋找穿過圖檔的能量最低的路徑。下一節中會詳細讨論這個算法。讓我們先看看如何為圖檔中的像素定義能量。
論文中讨論了一些不同的能量函數，以及它們在調整圖檔大小時的效果。簡單起見，我們使用一個簡單的能量函數，表達圖檔中的顔色在每個像素周圍的變化強烈程度。為了完整起見，我會将能量函數介紹得詳細一點，以備你想自己實作它，但這部分的計算僅僅是為後續動态規劃作準備。
左半邊表示，當相鄰像素的顔色非常不同時這個像素的能量大。右半邊表示，當相鄰像素的顔色比較相似時像素的能量小。
為了計算單個像素的能量，我們檢查這個像素左右的像素。我們計算逐個分量之間的平方距離，也就是分别計算紅色、綠色、藍色分量之間的平方距離，然後相加。我們對中心像素上下的像素進行同樣的計算。最終，我們将水準和垂直距離相加。
唯一的特殊情況是當像素位于邊緣，例如左側邊緣時，它的左邊沒有像素。對于這種情況，我們隻需比較将其和右邊的像素比較。對于上邊緣、右邊緣、下邊緣的像素，會進行類似的調整。
當周圍像素的顔色非常不同時，能量函數較大；而當顔色相似時，能量函數較小。
沖浪者圖檔中每個像素的能量，用白色顯示高能量像素、黑色顯示低能量像素來可視化。不出所料，中間的沖浪者和右側的湍流的能量最高。
這個能量函數在沖浪者圖檔上效果很好。然而，能量函數的值域很廣，當對能量進行可視化時，圖檔中的大部分像素看起來能量為零。實際上，這些區域的能量隻是相對于能量最高的區域比較低，但并不是零。為了讓能量函數更容易可視化，我放大了沖浪者，并調亮了該區域。
使用動态規劃搜尋低能量接縫
為每個像素計算出了能量之後，我們現在可以搜尋從圖檔頂部延伸到底部的低能量接縫了。同樣的分析方法也适用于從左側延伸至右側的水準接縫，可以讓我們減少原始圖檔的高度。不過，我們現在隻關注垂直的接縫。
我們先定義最低能量接縫的概念：
- 接縫是像素的序列，其中每行有且僅有一個像素。要求對于連續的兩行，
- 最低能量接縫是指接縫中所有像素的能量總和最小的一條接縫。
注意，最低能量接縫不一定會經過圖檔中的最低能量像素。是讓接縫的能量總和最小，而不是讓單個像素的能量最小。
貪心的方法行不通。過早選擇了低能量像素後，我們陷入了圖檔的高能量區域，如圖中紅色路徑所示。
從上圖中可以看到，“從最頂行開始，依次選擇下一行中的最低能量像素”的貪心方法是行不通的。在選擇了能量為 2 的像素之後，我們被迫走入了圖檔中的一個高能量區域。而如果我們在中間一行選擇一個能量相對高一點的像素，我們還有可能進入左下的低能量區域。
将問題分解為子問題
上述的貪心方法的問題在于，當決定如何延伸接縫時，我們沒有考慮到未來的接縫剩餘部分。我們無法預知未來，但我們可以記錄下目前所有已知的資訊，進而可以觀察過去。
讓我們反過來進行選擇。我們不再從多個像素中選擇一個來延伸單個接縫，而是從多個接縫中選擇一個來連接配接單個像素。 我們要做的是，對于每個像素，在上一行可以連接配接的像素中進行選擇。如果上一行中的每個像素都編碼了到那個像素為止的路徑，我們本質上就觀察了那個像素之前的所有曆史。
對每個像素，我們檢視上一行中的三個像素。本質的問題是，我們應當延伸哪個接縫？
這表明了可以對圖檔中的每個像素劃分子問題。因為子問題需要記錄到那個像素的最優路徑，比較好的方法是将每個像素的子問題定義為以那個像素結尾的最低能量接縫的能量。
和貪心的方法不同，上述方法本質上嘗試了圖檔中的所有路徑。隻不過，當嘗試所有可能的路徑時，在一遍又一遍地解決相同的子問題，讓動态規劃成為這個方法的一個完美的選擇。
定義遞歸關系
與往常一樣，我們現在需要将上述的思路形式化為一個遞歸關系。子問題是關于原圖檔中的每一個像素的，是以遞歸關系的輸入可以簡單的是那個像素的
和
我們定義函數
表示從圖檔頂部開始、到像素
結束的最低能量的垂直接縫。使用字母
首先，我們定義基本情況（base case）。在圖檔的最頂行，所有以這些像素結尾的接縫都隻有一個像素長，因為再往上沒有其他像素了。是以，以這些像素結尾的最低能量接縫就是這些像素的能量：
對于其他的所有像素，我們需要檢視上一行的像素。由于接縫需要是相連的，我們的候選隻有左上方、上方、右上方三個最近的像素。我們要選取以這些像素結尾的接縫中能量最低的那個，然後加上目前像素的能量：
我們需要考慮所檢視的像素位于圖檔的左邊緣或右邊緣時的邊界情況。對于左、右邊緣處的像素，我們分别忽略
或者
。
最終，我們需要取得豎向延伸了整個圖檔的最低能量接縫的能量。這意味着檢視圖檔的最底行，選擇以這些像素中的一個結尾的最低能量接縫。設圖檔寬
個像素，高
有了這個定義，我們就得到了一個遞歸關系，包括我們所需的所有性質：
- 遞歸關系的輸入為整數。
- 我們所需的最終結果易于從遞歸關系中提取。
- 這個關系隻依賴于自身。
檢查子問題的 DAG（有向無環圖）
由于每個子問題
子問題放置在二維網格中，就像在原圖檔中的排列一樣。
如遞歸關系的基本情況（base case）所示，最頂行的子問題對應于圖檔的最頂行，可以簡單地用單個像素的能量值初始化。
子問題的第一行不依賴于任何其他子問題。注意最頂行的單元沒有出來的箭頭。
從第二行開始，依賴關系開始出現。首先，在第二行的最左單元，我們遇到了一個邊界情況。由于左側沒有其他單元，标記為
左邊緣處的子問題隻依賴于上方的兩個子問題。
再看第二行的第二個單元，标記為
左右邊緣之間的子問題依賴于上方的三個子問題。
第二行的最後，右邊緣處表示了第二個邊界情況。因為右側沒有其他單元，這個單元隻依賴于上方和左上最近的單元。
右邊緣處的子問題隻依賴于上方的兩個子問題。
最後，對所有後續行重複這個過程。
因為依賴于包含了太多的箭頭，這裡的動畫逐個顯示了每個子問題的依賴。
由于完整的依賴圖箭頭數量極多，令人生畏，逐個地觀察每個子問題能讓我們建立直覺的依賴模式。
自底向上的實作
從上述分析中，我們可以得到子問題的順序：
- 從圖檔的頂部到底部。
- 對于每一行，可以以任意順序。自然的順序是從左至右。
因為每一行隻依賴于前一行，是以我們隻需要維護兩行的資料：前一行和目前行。實際上，如果從左至右計算，我們實際上可以丢棄前一行使用過的一些元素。不過，這會讓算法更複雜，因為我們需要弄清楚前一行的哪部分可以丢棄，以及如何丢棄。
在下面的 Python 代碼中，輸入是行的清單，其中每行是數字的清單，表示這一行中每個像素的能量。輸入命名為
pixel_energies
，而
pixel_energies[y][x]
表示位于坐标
首先計算最頂行的接縫的能量，隻需拷貝最頂行的單個像素的能量：
previous_seam_energies_row = list(pixel_energies[0]) 接着，循環周遊輸入的其餘行，計算每行的接縫能量。最棘手的部分是确定引用前一行中的哪些元素，因為左邊緣像素的左側和右邊緣像素的右側是沒有像素的。
在每次循環中，會為目前行建立一個新的接縫能量的清單。每次循環結束時，将前一行的資料替換為目前行的資料，供下一輪循環使用。這樣我們就丢棄了前一行。
# 在循環中跳過第一行
for y in range(1, len(pixel_energies)):
pixel_energies_row = pixel_energies[y]
seam_energies_row = []
for x, pixel_energy in enumerate(pixel_energies_row):
# 判斷要在前一行中周遊的 x 值的範圍。這個範圍取決于目前像素是在圖檔
# 的中間還是邊緣。
x_left = max(x - 1, 0)
x_right = min(x + 1, len(pixel_energies_row) - 1)
x_range = range(x_left, x_right + 1)
min_seam_energy = pixel_energy + \
min(previous_seam_energies_row[x_i] for x_i in x_range)
seam_energies_row.append(min_seam_energy)
previous_seam_energies_row = seam_energies_row 最終，
previous_seam_energies_row
包含了最底行的接縫能量。取出這個清單中的最小值，這就是答案！
min(seam_energy for seam_energy in previous_seam_energies_row) 你可以測試這個實作：把它包裝在一個函數中，然後建立一個二維數組作為輸入調用這個函數。下面的輸入資料會讓貪心算法失敗，但同時也有明顯可見的最低能量接縫：
ENERGIES = [
[9, 9, 0, 9, 9],
[9, 1, 9, 8, 9],
[9, 9, 9, 9, 0],
[9, 9, 9, 0, 9],
]
print(min_seam_energy(ENERGIES)) 時間和空間複雜度
對于原圖檔中的每一個像素，都有一個對應的子問題。每個子問題最多有 3 個依賴，是以解決每個子問題的工作量是常數。最後，我們需要再周遊最後一行一遍。那麼，如果圖檔寬
像素，高
像素，時間複雜度是
。
在任意時刻，我們持有兩個清單，分别存儲前一行和目前行。前一行的清單共有
個元素，而目前行的清單不斷增長，最多有
個元素。那麼，空間複雜度是
，也就是
。
注意到，如果我們真的從前一行的資料中丢棄一部分元素，我們可以在目前行的清單增長的同時縮減前一行的清單。不過，空間複雜度仍舊是
。取決于圖檔的寬度，常量系數可能會有一點影響，但通常不會有什麼大的影響。
用後向指針尋找最低能量接縫
現在我們找到了最低能量垂直接縫的能量，那麼如何利用這個資訊呢？事實上我們并不關心接縫的能量，而是接縫本身！問題是，從接縫的最後一個像素，我們無法回溯到接縫的其餘部分。
這是我在文章前面的内容中跳過的部分，但很多動态規劃的問題也有相似的考慮。例如，如果你還記得盜賊問題（打家劫舍）[5]，我們可以知道盜竊的數值并提取出最大值，但我們不知道哪些房子産出了那個總和的值。
表示後向指針
解決方法是通用的：存儲後向指針。在接縫裁剪的問題中，我們不僅需要每個像素處的接縫能量值，還想要知道前一行的哪個像素得到了這個能量。通過存儲這個資訊，我們可以沿着這些指針一路到達圖檔的頂部，得到組成了最低能量接縫的像素。
首先，我們建立一個類來存儲一個像素的能量和後向指針。能量值會用來計算子問題。因為後向指針隻是記錄了前一行的哪個像素産生了目前的能量，我們可以隻用
class SeamEnergyWithBackPointer():
def __init__(self, energy, x_coordinate_in_previous_row=None):
self.energy = energy
self.x_coordinate_in_previous_row = \
x_coordinate_in_previous_row 每個子問題将會是這個類的一個執行個體，而不再隻是一個數字。
存儲後向指針
在最後，我們需要回溯整個圖檔的高度，沿着後向指針重建最低能量的接縫。不幸的是，這意味着我們需要存儲圖檔中所有的像素，而不僅是前一行。
為了實作這一點，我們将保留所有子問題的全部結果，即使可以丢棄前面行的接縫能量數值。我們可以用像輸入的數組一樣的二維數組來存儲這些結果。
讓我們從第一行開始，這一行隻包含單個像素的能量。由于沒有前一行，所有的後向指針都是
None
。但是為了一緻性，我們還是會存儲
SeamEnergyWithBackPointer
的執行個體：
seam_energies = []
# 拷貝最頂行的像素能量來初始化最頂行的接縫能量。最頂行沒有後向指針。
seam_energies.append([
SeamEnergyWithBackPointer(pixel_energy)
for pixel_energy in pixel_energies[0]
]) 主循環的工作方式幾乎和先前的實作相同，除了以下幾點差別：
- 前一行的資料包含的是
SeamEnergyWithBackPointer
- 當為目前像素存儲資料時，我們需要建立一個新的
SeamEnergyWithBackPointer
- 在每一行計算結束後，不會丢棄前一行的資料，而是簡單地将目前行的資料追加到
seam_energies
# 在循環中跳過第一行
for y in range(1, len(pixel_energies)):
pixel_energies_row = pixel_energies[y]
seam_energies_row = []
for x, pixel_energy in enumerate(pixel_energies_row):
# 判斷要在前一行中周遊的 x 值的範圍。這個範圍取決于目前像素是在圖檔
# 的中間還是邊緣。
x_left = max(x - 1, 0)
x_right = min(x + 1, len(pixel_energies_row) - 1)
x_range = range(x_left, x_right + 1)
min_parent_x = min(
x_range,
key=lambda x_i: seam_energies[y - 1][x_i].energy
)
min_seam_energy = SeamEnergyWithBackPointer(
pixel_energy + seam_energies[y - 1][min_parent_x].energy,
min_parent_x
)
seam_energies_row.append(min_seam_energy)
seam_energies.append(seam_energies_row) 沿着後向指針前進
當全部的子問題表格都填滿後，我們就可以重建最低能量的接縫。首先找到最底行對應于最低能量接縫的 x 坐标：
# 找到最底行接縫能量最低的 x 坐标
min_seam_end_x = min(
range(len(seam_energies[-1])),
key=lambda x: seam_energies[-1][x].energy
) 然後，從圖檔的底部走向頂部，
坐标從
len(seam_energies) - 1
降到
0
。在每輪循環中，将目前的
坐标對添加到表示接縫的清單中，然後将
的值設為目前行的
SeamEnergyWithBackPointer
對象所指向的位置。
# 沿着後向指針前進，得到一個構成最低能量接縫的坐标清單
seam = []
seam_point_x = min_seam_end_x
for y in range(len(seam_energies) - 1, -1, -1):
seam.append((seam_point_x, y))
seam_point_x = \
seam_energies[y][seam_point_x].x_coordinate_in_previous_row
seam.reverse() 這樣就自底向上地建構出了接縫，将清單反轉就得到了自頂向下的接縫坐标。
時間與空間複雜度
時間複雜度和之前相似，因為我們仍然需要将每個像素處理一次。在最後還需要從最後一行中找出最低的接縫能量，然後向上走一個圖檔的高度來重建接縫。那麼，對于
的圖檔，時間複雜度是
。
至于空間複雜度，我們仍然為每個子問題存儲常量級的資料，但是現在我們不再丢棄任何資料。那麼，我們使用了
删除低能量的接縫
找到了最低能量的垂直接縫後，我們可以簡單地将原圖檔中的像素複制到新圖檔中。新圖檔中的每一行都是原圖檔中對應行除去最低能量接縫的像素後的剩餘像素。因為我們在每一行都删去了一個像素，那麼我們可以從一個
的圖檔得到
我們可以重複這個過程，在新圖檔上重新計算能量函數，然後找到新圖檔上的最低能量接縫。你可能很想在原圖檔上找到不止一個低能量的接縫，然後一次性把它們都删除。但問題是兩個接縫可能相關交叉，在中間共享同一個像素。在第一個接縫删掉之後，第二個接縫就會由于缺少了一個像素而不再有效。
上述視訊展示了應用于沖浪者圖檔上的接縫删除過程（視訊連結在此[6]——譯者注）。我是通過擷取每次疊代的圖檔，然後在上面添加最低能量接縫的可視化線條來制作的這個視訊。
另一個例子
已經有很多深入的講解了，那讓我們以一些漂亮的照片結束吧！請看下面的在拱門國家公園的岩層的照片：
拱門國家公園中間的一個有孔的岩層。圖檔來自 Flickr 上的
Mike Goad
[7]。
這個圖檔的能量函數：
拱門圖檔中每個像素的能量，用白色顯示高能量像素、黑色顯示低能量像素來可視化。注意岩層孔洞邊緣旁的高能量。
這産生了下面的最低能量接縫。注意到這個接縫穿過了右側的岩石，正好從岩石頂部被照亮與天空顔色一緻的部分進入。或許我們需要選擇一個更好的能量函數！
拱門圖檔中的最低能量接縫。接縫通過一條五個像素寬的紅線來可視化，實際上接縫隻有一個像素寬。
最終，調整拱門圖檔的大小之後：
寬度減少了 1024 像素後的拱門圖檔。
這個結果肯定不太完美，原圖檔中的很多邊緣在調整大小後的圖檔中都有些變形。一種可能的改進是實作另一個論文中讨論的能量函數。
動态規劃雖然常常隻在教學中遇到，但它還是解決實際的複雜問題的有用技術。在本文中，我們讨論了動态規劃的一個應用：使用接縫裁剪實作環境敏感的圖檔大小調整。
我們應用了相同的原理，将問題分解為子問題，分析子問題之間的依賴關系，然後以時間、空間複雜度最小的順序求解。另外，我們還探索了通過後向指針，除了計算最小的數值，還能找到産生這個數值的特定選擇。然後将這部分内容應用到實際的問題上，對問題進行預處理和後處理，讓動态規劃算法真正有用。
參考資料
[1]
Avik Das: https://avikdas.com/
[2]
Real-world dynamic programming: seam carving: https://avikdas.com/2019/05/14/real-world-dynamic-programming-seam-carving.html
[3]
Seam Carving for Content-Aware Image Resizing: https://dl.acm.org/citation.cfm?id=1276390
[4]
Kiril Dobrev: https://pixabay.com/users/kirildobrev-12266114/
[5]
盜賊問題（打家劫舍）: https://medium.com/future-vision/a-graphical-introduction-to-dynamic-programming-2e981fa7ca2?source=friends_link&sk=37cd14642cf1a83eb0bb33d231442837#25bc
[6]
原視訊連結: https://youtu.be/B9HPREBePI4
[7]
Mike Goad: https://www.flickr.com/photos/exit78/
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下