復現《Region Filling and Object Removal by Exemplar-Based Image Inpainting》
論文內容
這篇論文是圖片補全傳統演算法中的經典之作，主要的思路還是使用被扣圖片剩餘部分的冗餘資訊對孔洞進行填充。作者提出了一種確定區域填充順序的方法，使得原有圖片的結構資訊得以更好的傳播。論文的主要流程如下所示：
- 查詢孔洞的邊緣，計算邊緣畫素點的填充優先順序
- 挑選出優先順序最高的點，根據畫素點得到畫素塊
- 在剩餘部分查詢和畫素塊最相似的畫素塊
- 用最佳畫素塊填充對應的部分填充對應的孔洞部分，檢視填好了沒有，沒有跳到1
可以看到流程主要又兩個方面：1 計算邊緣畫素點的優先順序；2 查詢最佳匹配塊。下面來介紹一下這兩個部分是怎麼做的。
優先順序的計算
在介紹之前先放一張論文中的圖片方便之後的解釋：
優先順序的計算由下面的公式給出：
$$ P(p)=C(p)D(p) $$
其中$C(p)$為畫素點的信譽度（confidence），計算公式如下：
$$ C(p)=\frac{\sum_{q\in\Psi_p\cap(I-\Phi)C(q)}}{|\Psi_p|} $$
這個公式表明演算法會優先填充周圍資訊比較豐富的畫素點，因為這些點填充起來較為容易，填充得到的也更加的可靠，這樣從周圍最可靠的部分開始填充逐步向內推進使得整體的填充結果可靠。在開始的時候也就表現為優先考慮填充那個尖銳的突出部分。
另一個部分在論文中叫做data term（原諒我不知道應該怎麼翻譯 
Line"/> ），計算公式如下：
$$ D(p)=\frac{|\bigtriangledown I_{\frac{1}{p}}\bullet n_p|}{\alpha} $$
其中$\alpha$是歸一化因子，如果是灰度影象的話就為255。這個公式又表示什麼含義呢？通過這個公式我們可以發現演算法會優先挑選哪些在原有圖片結構附近的畫素進行填充，這樣的話圖片原有的結構就可以更好的向著孔洞中延伸了。為什麼要這樣子呢？這是基於我們生活的關於圖片一個常識，一般來說在圖片較小的一片區域內它的主要結構是近似於直線的。
查詢最佳匹配
這個部分就比較簡單了，比較圖片相似度的演算法有很多作者挑選了一個最近簡單最小平方和演算法，然後全圖暴力搜尋最佳匹配。
實現中遇到的問題
在開始介紹之前首先放上一個自己實現的GitHub的地址： ofollow,noindex" target="_blank">論文實現GitHub地址
開始不清楚邊界上的法線和文中的 isophote 應該如何計算，之後發現邊界上的發現不就是mask在邊界上的梯度嗎 ，而 isophote 不就是梯度旋轉90度嘛。最後實現完成之後發現如下圖的這樣簡單的圖片填充得到的效果都慘不忍睹。
結果：
下面這些黑塊是什麼鬼。。。然後就看是什麼原有啦，最後發現是查詢最佳匹配的這個部分有問題，因為查詢最佳匹配的時候是隻看孔洞外面那個部分和剩餘圖片的匹配程度的。所以在圓形下面部分的圖片塊開始查詢的時候會發現下原圖中央邊界部分的下面匹配的很好（雖然之後在全灰的部分也匹配的很好，但是在相同情況下先匹配的排到了前面），然後災難就發生了。之後忘裡面走回發現在全黑的部分匹配的最好，這就是下面這塊黑東東出現的原因了。那麼應該咋搞類。
在另外一個作者的參考實現中他加入了一個尤拉距離度，在相同情況下優先考慮比較近的圖片塊。這樣做的原因可能是覺得圖片的變化是漸進的，相近的圖片塊比較像吧。最後得到的結果如下所示：
看起來還是不錯的。
從結構傳播的這個角度來看，第一個結果為什麼讓人感到維和呢？因為它在填充的時候得到的最佳匹配的圖片塊的結構和原有的結構之間差距太大了，變化太劇烈了。這樣我可以給它加上一個用於評估圖片塊和原有部分的結構相似度的部分應該得到更好的結果，改進後的公式如下所示：
$$ diff=SQDIFF-|cos(\theta)|+||p|-|q|| $$
其中$p$為原有部分的最大梯度，$q$為匹配圖片塊中的最大梯度，$|cos(\theta)|$用於評估兩個結構在方向上的相似性，而後面的這部分則是用於評估在變化劇烈程度上的相似性。最後得到的結果如下所示：
可以看到效果還是不錯的。當然也可以嘗試一下把這兩種方法結合起來一下。之後我把跑了一下其他圖片和有的圖片的確效果還不錯，有的就和論文有一些距離了 。這些結果都可以在原始圖片和結果都可以在GitHub中找到（ 填充結果 ），當然你也可以自己跑一遍。一些是一些實驗結果：
和論文進行比較可以看到還有一些差距的。
總結
自動圖片補全就像是人類看到圖片腦補一樣的，人類在腦補的時候會根據已有的常識（也就以前看過的類似圖片）以及圖片中的語義資訊進行腦補，而這種方法還是隻能使用較為有限的資訊。同時在低頻的時候補全效果較好，高頻補全得到的效果較差。還有就是演算法的效率較差，運算時間比較長。另外大家在自己製作mask的時候，可以考慮一下使用微軟的paint 3D真的非常好用，先用神奇選擇把要扣的東西扣出來（它有個自動補全背景可以和自己演算法補全的結果比較一下），然後把扣下來的東西在Z軸上拉開，背景填充成黑色，扣下來的填充成白色儲存成2D圖片，一個mask就製作好了。
本 作品 由 尹傲雄 採用知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協議進行許可。