作者|Samarendra Chandan Bindu Dash
編譯|Flin
來源|analyticsvidhya
介紹
在本文中，我們將深入研究一種有趣的演算法，稱為“接縫雕刻”，調整影像的大小而不裁剪或扭曲其內容似乎是不可能完成的任務，我們將逐步構建，從頭開始實作接縫雕刻演算法，同時查看其背后的一些有趣的數學原理，
微積分方面的知識將有助于后續學習，但不是必需的，我們開始吧，
（本文的靈感來自麻省理工學院的格蘭特·桑德森的演講，）
問題
讓我們看一下這張圖片，
薩爾瓦多·達利（Salvador Dali）完成的這幅畫被命名為“記憶的永恒”，我們對繪畫的內容更感興趣，而不是其藝術價值，我們要通過減小圖片的寬度來調整圖片的大小，我們可以想到的兩個有效程序是裁剪圖片或壓縮寬度，
但是，正如我們所看到的，裁剪會洗掉許多物件，擠壓又會扭曲圖片，我們希望兩者兼有，即在不裁剪任何物件或不扭曲物件的情況下減小寬度，
我們可以看到，除了物件之外，圖片中還有很多空白，我們要在此處完成的任務是以某種方式洗掉物件之間的空白區域，以便保留影像中有趣的部分，同時丟棄不必要的空間，
這確實是一個棘手的問題，很容易迷失，因此，將問題分解為更小，更易于管理的部分始終是一個好主意，我們可以將這個問題分為兩個部分，
-
識別圖片中有趣的部分（即物件），
-
標識可以去除而不會扭曲圖片的像素路徑，
識別物件
在繼續之前，我們需要將圖片轉換為灰度影像，這將對我們稍后進行的操作很有幫助，這是一個將RGB像素轉換為灰度值的簡單公式
def rgbToGrey(arr):
greyVal = np.dot(arr[...,:3], [0.2989, 0.5870, 0.1140])
return np.round(greyVal).astype(np.int32)
為了識別物件，我們可以制定策略，如果我們能以某種方式識別圖片中的所有邊緣呢？然后，我們可以要求接縫雕刻演算法采用不通過邊緣的像素路徑，因此，通過擴展，不會碰觸任何由邊緣封閉的區域，
但是，我們如何識別邊緣呢？我們可以看到的一個觀察結果是，每當兩個相鄰像素之間的顏色發生急劇變化時，最有可能就是物體的邊緣，我們可以將這種立即的顏色變化合理化，作為從該像素開始的新物件的開始，
我們必須解決的下一個問題是如何識別像素值的急劇變化，現在，讓我們考慮一個簡單的情況，即一行像素，假設我們將此值陣串列示為x，
我們可以取像素x [i + 1]，x [i]之間的差，它會顯示當前像素從右側變化了多少，或者我們也可以取x [i]和x [i-1]之差，這將在左側產生變化，為了表示總變化，我們可能要取兩者的平均值，得出
熟悉微積分的任何人都可以快速地將此運算式識別為導數的定義，我們需要計算x值的急劇變化，因此我們正在計算它的導數，如果我們定義一個過濾器[ -0.5,0,0.5 ]，然后用陣列[x[i-1]，x[i]，x[i+1]乘以它的元素，然后取它的和，它就會得到x[i]的導數，
由于我們的圖片是2D的，因此我們需要2D過濾器，我不會詳細介紹，但是我們過濾器的2D版本看起來像這樣，
當我們的過濾器計算沿x軸的每個像素的導數時，它將給出垂直邊緣，同樣，如果我們沿y軸計算導數，則將具有水平邊緣，過濾器如下，（與轉置時用于x軸的過濾器相同，）
這些過濾器也稱為Sobel過濾器，
所以，我們有兩個過濾器，需要在圖片中傳播，對于每個像素，用（3X3）子矩陣對其進行逐元素乘法，然后取其和，這種運算被稱為卷積，
卷積：
數學上，卷積運算就是這樣，
看看我們如何對兩個函式進行逐點乘法，然后對其進行積分，從數值上講，這將與我們之前所做的相對應，即過濾器和影像的逐元素相乘，然后對其求和，
注意，對于k函式，它如何寫為k（t-τ），因為卷積運算需要翻轉其中一個信號，你可以直觀地將其想象成這樣：兩列火車在一條直線的水平軌道上相互朝著一個不可避免的碰撞（不必擔心，因為它們是疊加的，火車不會發生任何事情），因此，火車頭將彼此面對，現在，假設你正在從左到右掃描軌道，然后，對于左列火車，你將從尾部向頭部掃描，
同樣，計算機需要從右下角（2,2）角到左上角（0,0）而不是從左上角到右下角讀取過濾器，因此，實際的Sobel過濾器如下所示，
在進行卷積運算之前，我們先進行180度旋轉，
我們可以繼續撰寫一個簡單的實作來進行卷積運算，像這樣：
def naiveConvolve(img,ker):
res = np.zeros(img.shape)
r,c = img.shape
rK,cK = ker.shape
halfHeight,halfWidth = rK//2,cK//2
ker = np.rot90(ker,2)
img = np.pad(img,((1,1),(1,1)),mode='constant')
for i in range(1,r+1):
for j in range(1,c+1):
res[i-1,j-1] = np.sum(np.multiply(ker,img[i-halfHeight:i+halfHeight+1,j-halfWidth:j+halfWidth+1]))
return res
這將很好地作業，但是將花費大量時間來執行，因為它將進行近9 * r * c的乘法和加法運算以得出結果，但是我們可以聰明地使用數學中的更多概念來大大減少時間復雜度，
快速卷積：
卷積具有有趣的性質，時域中的卷積對應于頻域上的乘法，即
，其中F（w）表示頻域中的函式，
我們知道傅立葉變換將時域的信號轉換成其頻域，因此，我們可以做的是計算影像和濾波器的傅立葉變換，將它們相乘，然后進行傅立葉逆變換以獲得卷積結果，
為此我們可以使用NumPy庫，
def fastConvolve(img,ker):
imgF = np.fft.rfft2(img)
kerF = np.fft.rfft2(ker,img.shape)
return np.fft.irfft2(imgF*kerF)
（注意：在某些情況下，得出來的值可能與樸素方法稍有不同，因為fastConvolve函式會計算圓形卷積，但是實際上，我們可以輕松地使用快速卷積，而不必擔心這些較小的值差異，）
酷！現在，我們有了一種有效的方法來計算水平邊緣和垂直邊緣，即x和y分量，因此，使用
def getEdge(greyImg):
sX = np.array([[0.25,0.5,0.25],
[0,0,0],
[-0.25,-0.5,-0.25]])
sY = np.array([[0.25,0,-0.25],
[0.5,0,-0.5],
[0.25,0,-0.25]])
#edgeH = naiveConvolve(greyImg,sX)
#edgeV = naiveConvolve(greyImg,sY)
edgeH = fastConvolve(greyImg,sX)
edgeV = fastConvolve(greyImg,sY)
return np.sqrt(np.square(edgeH) + np.square(edgeV))
識別像素路徑：
對于連續路徑，我們可以定義一個規則，即每個像素僅連接到它下面的3個最近的像素，這將使像素從上到下具有連續的路徑，因此，我們的子問題成為基本的尋路問題，我們必須將成本降到最低，
由于邊緣具有更高的幅度，如果我們繼續以最低的成本移除像素路徑，它將避免出現邊緣，
讓我們定義一個函式“ cost”，該函式獲取一個像素并計算從那里到圖片結尾的最小成本像素路徑，我們有以下觀察，
- 在最底行（即i = r-1）
- 對于任何中間像素，
代碼：
def findCostArr(edgeImg):
r,c = edgeImg.shape
cost = np.zeros(edgeImg.shape)
cost[r-1,:] = edgeImg[r-1,:]
for i in range(r-2,-1,-1):
for j in range(c):
c1,c2 = max(j-1,0),min(c,j+2)
cost[i][j] = edgeImg[i][j] + cost[i+1,c1:c2].min()
return cost
繪圖：
我們可以在圖中看到三角形，它們表示不回傳的點，也就是說，如果你到達那個像素，就沒有一條路徑不通過邊緣到達底部，而這正是我們試圖避免的，
從成本矩陣中尋找像素路徑可以很容易地用貪婪演算法完成，在最上面一行找到最小成本像素，然后向下移動，在所有連接到它的像素中選擇成本最低的像素，
def findSeam(cost):
r,c = cost.shape
path = []
j = cost[0].argmin()
path.append(j)
for i in range(r-1):
c1,c2 = max(j-1,0),min(c,j+2)
j = max(j-1,0)+cost[i+1,c1:c2].argmin()
path.append(j)
return path
為了洗掉路徑定義的接縫，我們只需要遍歷每一行并洗掉路徑陣列提到的列，
def removeSeam(img,path):
r,c,_ = img.shape
newImg = np.zeros((r,c,3))
for i,j in enumerate(path):
newImg[i,0:j,:] = img[i,0:j,:]
newImg[i,j:c-1,:] = img[i,j+1:c,:]
return newImg[:,:-1,:].astype(np.int32)
在這里，我已經預先計算了100個接縫雕刻操作，
我們可以看到畫中的物體是如何彼此接近的，我們已經成功地使用接縫切割演算法縮小了影像的大小，而不會對物體造成任何變形，我已經附上了完整代碼鏈接，感興趣的讀者可以在這里看看，
- https://github.com/Samarendra109/Seam-Carving.git
總的來說，接縫雕刻是一個有趣的演算法，它有一些警告，因為如果提供的影像有太多的細節或太多的邊緣，它將失敗，
使用該演算法對不同的圖片進行修改以查看最終結果總是很有趣的，如果你有任何疑問或建議，請給我留言，
感謝你的閱讀！
原文鏈接：https://www.analyticsvidhya.com/blog/2020/09/seam-carving-algorithm-a-seemingly-impossible-way-to-resize-an-image/
歡迎關注磐創AI博客站：
http://panchuang.net/
sklearn機器學習中文官方檔案：
http://sklearn123.com/
歡迎關注磐創博客資源匯總站：
http://docs.panchuang.net/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/208644.html
標籤：其他