以路徑選擇重定尺寸
均勻縮小影像會壓縮所有內容,包括可能希望保留的特徵。內容感知方法可移除一條相連像素路徑,稱為接縫,同時嘗試避開視覺上重要的區域。方法依賴分配給各像素的能量:總能量低是一個數學目標,並不保證移除的內容對觀看者不重要。
定義 10.1.1
(垂直接縫及其能量)
設影像有 行及 列。此處先為每個像素固定一個有限實數 ,其中 、。一條垂直接縫在每行選一列 ,且相鄰兩行滿足 。其能量為 。選出接縫後,在每行分別刪除所選像素並合攏該行空位,所得矩形影像有 行及 列。
能量可使用局部影像差值、用戶提供的保護遮罩,或結合兩者。不同選擇可得到不同接縫。本節假設整張能量表已固定,不假設像素能量能完美表達物件意義,也不假設重定尺寸後能量仍然有效。
動態規劃與證明
定義 10.1.2
(累積接縫成本)
終止於像素 的接縫前綴,是一組列 ,滿足 。令 為 在所有這類前綴上的最小值。至第一行的前綴只有一個像素,故 。
定理 10.1.3
(接縫遞推式)
對 ,
垂直接縫的最小能量是 ;從使它最小的最底行列出發,沿最小前驅回溯,便得到達到此值的接縫。
證明
(按行歸納)
令 。在影像邊緣,此集合只含實際存在的列;不會默默把影像外像素當作零成本。
終止於 的有效前綴,其前一個像素是某個 的 ,移去最後像素後得到終止於 的有效前綴。反過來,任何終止於 ()的有效前綴都可延伸至 。
上界:在終止於最小化 的最小成本前綴後加上 ,得到成本為 的前綴,故 不超過此值。下界:對任何終止於 的前綴,移去最後像素後得到某個 的前綴,其成本至少為 ,所以原前綴成本至少為 。因此等式成立。完整接縫是長度為 的前綴,故最小接縫能量是 。從最小化的最底行列開始,每步取最小前驅,便得到能量恰為 的接縫。
即使能量為負,此證明仍成立,因為每條完整接縫恰有 個像素,而逐行的有向圖沒有循環。
證明透視
為何遞推式只需要最後一個像素
證明用到三個事實。前綴的成本是一個和,所以移去最後像素恰好減去 ,不涉及其他項,兩個界便由此而來。相鄰條件只連結相鄰兩行,所以延伸前綴的方式只取決於它的最後像素,與如何到達無關;這就是最優子結構的一步:到達 的最佳方式包含到達其前驅的最佳方式。最後,能量是固定數值,不隨所選接縫改變。若目標的成本依賴前綴中多於最後像素的部分,或能量隨接縫改變,論證就會失效。負值無妨,因為每個候選都恰有 項。
要讀出接縫,為每項儲存一個達到最小值的前驅;從最底行的最小值列沿指標向上,再把列次序反轉。若候選值並列,任取一個最小值對所述目標都是最優;若實作需要確定輸出,須明確指定並列規則。單行也是有效特例:選該行的最小能量像素,無須前驅步驟。
概念視角算法
接縫是分層圖上的最短路徑
為每個像素建立一個節點,只要 ,就從 向 連一條邊,並讓每個節點帶權重 。再加入連到第一行的源點,以及由第 行連出的匯點,有效接縫就恰是源點到匯點的路徑,接縫能量是路徑上權重之和。此圖沒有循環,所以即使有些權重為負,也可按行次序計算最短路徑,而 就是到節點 的最短路徑距離。
一個誘人的捷徑,是不理會這個圖,逐行獨立選擇最便宜的像素。相鄰條件正好禁止這樣做。
反例模式
逐行選最便宜的像素不是接縫
取 、,第 1 行能量為 ,第 2 行為 。最便宜的像素在第 和第 列,總和為 ,但 ,所以這不是接縫。有效接縫為 ,能量依次為 ,所以最小值是 。即使改用「從最便宜的頂部像素出發,每步走向較便宜鄰點」的修正規則,仍可能失敗:第 1 行為 、第 2 行為 時,它選第 1 列,再走向成本 的鄰點,能量為 ;而 ,由第 2 或第 3 列出發即可達到。局部選擇不能取代遞推式。
表格例題
例題 10.1.4
(四行表格上的累積成本)
對以下固定能量表,逐行計算累積成本:
| 行 | 第 1–4 列的像素能量 | 第 1–4 列的累積成本 |
|---|---|---|
| 1 | 4, 2, 4, 7 | 4, 2, 4, 7 |
| 2 | 6, 1, 5, 4 | 8, 3, 7, 8 |
| 3 | 2, 4, 1, 6 | 5, 7, 4, 13 |
| 4 | 4, 3, 2, 3 | 9, 7, 6, 7 |
例如第 3 行第 1 列只使用第 2 行第 1、2 列,故成本為 。最底行的最小成本是第 3 列的 。回溯得到由上至下列號 ,能量為 。此表證明在這些固定能量下,它在所有有效垂直接縫中最優;一般而言,逐行獨立選擇最小能量像素不會保證相鄰條件。
例題 10.1.5
(兩條最優接縫並列)
取 、,第 1 行能量為 ,第 2 行為 。第一行成本為 。第 2 行第 1 列只有第 1、2 列作前驅,故 ;;。最小值 出現在第 1 和第 3 列,給出兩條最優接縫,列號 與 ,能量均為 。兩者對目標都是最優,所以程式必須按明確規則取捨,例如取列號最小者。兩個邊緣列都不會查閱第 或第 列。
例題 10.1.6
(移除接縫後再重複)
從上面的四行表格移除接縫 。保持其餘能量不變,新的各行為 、、、,共 列。在這張固定表上重複算法,累積成本為 、、、,所以下一條接縫的能量是 。實際上新影像的能量會重新計算,因為被接縫隔開的像素現在已相鄰;上表只是這一步在能量不變時的版本。
效率與目標未包含的因素
命題 10.1.7
(接縫算法的時間與空間)
計算所有成本 需時 。若只需要最小值,兩行成本需 空間;若按直接方法重構,每格保留一個前驅則額外需 空間。輸出接縫本身需 空間。
證明
(數算格子與保留的行)
共有 個格子,每格最多檢查三個前驅,所以需時 。第 行只用到第 行,所以不儲存前驅時只須保留兩行成本。每格一個前驅共 個值,而最後的接縫每行一列。
邊界及並列選擇須一致記錄。
常見錯誤
(把不存在的鄰點當作免費)
取第 1 行能量 、第 2 行 。像素 只在第 1、2 列有前驅,所以 。若給不存在的第 列成本 ,公式會得到 ,比任何經過 的接縫能量都小,因為它們都必須經過第 1 行,那裏的能量至少是 。只有實際存在的列才可進入最小值。
若要移除多條接縫,可以每次移除一條,更新影像和能量表,再重複。初始寬度為 時,在每步寬度至少為二的條件下最多移除 條:移除 條後寬度為 。每次只解決當前固定表的問題;這本身不能證明所得序列對另行定義的多次移除目標全域最優。重新計算局部能量也可能令每次移除後的目標改變。只累計原像素能量的目標沒有明確計入移除接縫後新鄰點之間的不連續。更複雜的目標可以加入這些成本,但其遞推式及假設須另行推導。
低梯度或低指定能量仍可能穿過人臉、文字或有意義的直線邊緣。遮罩、感知準則及人工檢視可減少部分失敗,但不能證明語意一定被保留。交換行與列的角色可處理水平接縫;這是不同的路徑方向,而非原封不動使用同一條垂直接縫。
練習
快速檢查
(若 且能量行為 ,給出一條最小接縫及其能量。遞推式如何避免要求不存在的前驅?)
遞推式用於哪些 值?
解答 · 答案
最小接縫是第 列,能量為 。只有一行時只用到 ,而遞推式只對 使用,所以不會要求任何前驅。對 ,最小值只遍歷實際存在的列。
快速檢查
(給出一個至少三列的兩行能量表,使逐行獨立選擇最便宜像素違反相鄰條件。)
把兩個最便宜的像素放在相距兩列的位置。
解答 · 答案
取第 1 行為 、第 2 行為 。最便宜的像素在第 和第 列,總和為 ,並不是接縫。遞推式給出 、、,所以每條有效接縫的能量至少為 。
快速檢查
(為何重新計算能量並重複單接縫算法,本身不能證明對多接縫目標全域最優?)
比較每次迭代優化的對象,與多接縫目標所累計的對象。
解答 · 答案
每次迭代只對當前固定表最優。移除接縫會改變影像,所以下一張表的能量和鄰接關係都與原來不同,而逐次單接縫最優值之和,並未被證明是任何定義在整個序列上的目標的最優值。全域結論需要另行定義目標並另行證明。
快速檢查
(對各行為 、、 的能量表,計算累積成本並求一條最小垂直接縫。)
先填第 1 行,再用上一行實際存在的列逐格計算。
解答 · 答案
第 1 行成本為 。第 2 行:,,。第 3 行:,,。最小值是第 1 列的 ;回溯得列號 ,能量為 。