Seam Carving

一種很強的圖像縮放算法

0簡介

我們在排版的時候可能會遇到一些尷尬的情況。一張圖片原本是豎著的，而你希望把它當作一張寬屏圖片，于是你只好對它進行拉伸。

撫子的形狀瞬間變得不可描述起來。有沒有什么辦法，能不改變前景撫子的形象，只是拉伸背景的天空呢?也許你會想到萬能的神經網絡。但早在神經網絡火遍大江南北之前，就有一種方法流行于世間：Seam Carving。它可以做到這樣：

完美符合我們的要求!那么這個仿佛魔法一樣的Seam Carving是如何工作的呢?

01什么是圖像

我們這里將所談論到的圖像限定為二維的像素圖象，而不是矢量圖象或者三維的體素組成的“圖像”之類的東西。對于一幅圖像，它的每個像素擁有一個整數坐標，同時擁有一個顏色，后者以 RGB 的形式表現。

當人看到圖像的時候，主要是通過識別圖像當中的邊緣來分辨圖像中的物體的，這提示我們邊緣的信息對于尋找圖像中的主要物體有著重要的作用。如果我們在圖像縮放的時候能夠盡量不影響到這些像素，那么就有可能做到在保證圖像中主要物體的比例不變的情況下拉伸背景。就像這樣

由此我們可以得出結論：通過依次刪除圖像中若干條自上而下和自左而右的像素通路，就可以達到“縮放”的目的。就自上而下的像素通路來說，這樣的通路寬度為 1，從圖像的第一行連接到圖像的最后一行，在每一行中只占據一個像素，相鄰行的像素的水平坐標相差在 -1 到 1 之間。刪除這樣的自上而下的像素保證了圖像的寬度減一的同時不會出現寬度不同的行;自左而右的像素通路也是同理。

圖中的紅線分別是一條垂直通路和水平通路。如何找到這樣的像素通路，穿過盡可能少的重要物體?為此，我們引入了一個概念：“能量”。

02能量，又是能量

能量在這里起到的作用是表征像素的重要程度。先從圖像的基本元素的能量——像素的能量說起。對于單個像素，我們可以定義其能量形式為：

其中，字母I表示像素灰度值，第一個偏導項就表示了色彩在這個像素變化的劇烈程度。如果我們將 RGB 顏色的像素的顏色看作一個三維向量，那么其能量形式也會是一個三維向量，這對于算法的后續實現是不利的。在實現中，我們可以用灰度標量代替 RGB 三維向量參與運算，因為人眼對灰度的敏感度遠高于色彩。公式看起來不太直觀，來看一個例子：

與人物有關的部分，細節比較多，對應的顏色變化也更明顯，能量也就越高。相比之下，背景部分比如天空的顏色變化不太明顯，能量普遍比較低。對應到上圖中，可能找到的垂直能量通路就是左側的天空，刪除之后并不會影響魚和人物的部分。

對于任意的一條自上而下的像素通路，該通路的能量就是該通路中所有像素的能量的和。

03利用能量進行分割

前文說到，像素的能量表征了像素的重要程度，那么像素通路的能量就表征了像素通路中所有像素的總體重要程度，也就表征了該通路穿過的重要物體的多寡，也就表征了刪除這條像素通路對圖像中重要物體的影響程度的大小。刪除一條能量最小的像素通路對圖像中重要物體的影響是最小的。

對于這樣一張圖像，如果對其進行縮放，我們希望保留不同顏色間的分界線，使其形狀和比例盡可能地不改變。即這幾條分界線的重要性應該盡可能地高。根據我們關于能量的定義，分界線附近的像素的能量顯著地高于色塊中的像素。如果要被刪去的像素通路主要通過色塊區域，那么分界線的形狀就可以得到保留了。

那么現在的問題就變成了如何尋找一條能量最小的像素通路，這里以自上而下的像素通路說明尋找這樣的像素通路的方式。這就轉換為了一個經典的動態規劃問題，形式化的轉移方程如下：

我們記 dpi 為從圖像的第一行到第 i 行的第 j 個像素的通路中能量最小的通路的能量 e 以及該像素在該通路上的前驅 p。第 i 行的第 j 個像素的能量為 e(i,j)。那么

這個公式可能還是有點太過抽象了。由于通路一定是連通的，也就是某一個像素只可能與三個像素位于同一條通路內，分別是它的左上、正上和右上。

如果我們分別知道它左上、正上和右上的三個像素所在的通路的最低能量，只需要選出能量最低的一條并加上自己的能量，就構成了當前像素的最短能量通路。換言之，這其實是一種歸納法：

·第一行每個像素的累積能量是自己的能量值

·除此之外每一行每個像素的累計能量是上一行的三個相鄰像素中最低的累積能量加上自己的能量值

·最后一行的累計能量最低的就代表了一條能量最短的通路

當然，這里還有一個小小的擴展：現在有一個希望縮減的圖像，其寬高分別需要縮減 dw 和 dh 個像素。這就意味著這張圖象需要刪去 dw 和 dh 條能量最小的自上而下的通路和自左而右的通路。我們可以選擇先刪除自左而右的通路，再刪除自上而下的通路，反之亦可。但是為了追求刪除通路的總能量和最小——這樣全部刪除掉的像素對重要物體的影響最小，我們還可以優化這個刪除順序。

這個問題也可以用動態規劃的方法解決。不妨記 dq[i] [j] 為原圖像在水平縮減 i 個像素長度、垂直縮減 j 個像素長度的過程中所有刪去的像素通路的能量值和的最小值，由于寬高分別為 x 和 y 的圖像在這種縮放方式下只有可能通過 寬高為 (x+1,y) 或 (x,y+1) 的圖像縮減而來，所以有

有了上面的經驗，讀者能否自己理解這個轉移方程的含義呢?

最后再來看一個利用Seam Carving方法處理的例子：

很多細節得到了保留，比起直接拉伸來說要好太多了。

04結語

本文介紹的這種Seam Carving方法由Avidan等人發明，并發表在2007年的Siggraph中，目前已經有非常廣泛的應用，在Photoshop等軟件中都可以找到它的身影。比起目前主流的神經網絡方法來說，它要簡單的多，并且有很大的改良余地，最終效果也不遑多讓。有興趣的同學也可以進一步的研究或者和我討論。