複製區塊後,為何還須決定邊界
一幅織布照片包含許多小範圍的線條排列,要逐像素重建並不容易。直接複製一個方形區塊,可以保留方塊內的排列;困難卻轉移到邊界:下一個區塊的線條可能出現在不同高度,亮度也可能不同。即使兩個區塊各自合理,矩形接合仍會暴露它們的不一致。
重疊區讓我們選擇何處由原有影像轉用新區塊。把重疊像素全部平均,可能產生兩道模糊的邊緣;沿選定接縫保留兩側的其中一個提案,則有不同效果。本節把接縫選擇寫成精確的有限模型,並分清三件事:選區塊、為已選區塊選接縫,以及評估完成影像。它們是不同問題。
先前的有限範例模型透過更新共用像素來協調衝突的區塊提案。這裏改用明確的二元歸屬遮罩,逐點在兩個提案中選一個來複製。以下教學構造連角落規則也完整指定;其數學保證只關於此構造,不會自動證明某張照片的合成結果自然。
區塊位置與重疊誤差
定義 1.26.1
(區塊字典、重疊寬度與步長)
由範例影像取得非空有限字典 ,每個區塊為 ,每像素含 個實數色彩通道。字典不暗中包含旋轉、縮放或色彩調整;如需要這些變換,必須另行指定變換後的區塊及允許規則。選整數重疊寬度 ,令步長 。
若區塊有 行、 列,且行數與列數均為正整數,左上位置取 ,其中 、。最後影像高度為 ,寬度為 。每行由左至右,完成一行後移到下一行。若想得到較小尺寸,可以裁剪完成的矩形;以下有限分析針對裁剪前的矩形。
定義 1.26.2
(重疊條帶與已覆蓋集合)
除第一個位置外,以 表示局部座標中已被覆蓋的輸出值。覆蓋集合 是左條帶、上條帶,或兩者並集:
首行的後續位置只有 ;首列的後續位置只有 ;內部位置兩者都有。此結論依賴上述沒有缺塊的規則掃描次序。內部角落同屬兩個條帶,但仍只是一組像素:
定義 1.26.3
(逐點差異與正規化重疊誤差)
對候選 ,定義逐點差異與正規化重疊誤差
範數把通道差的平方相加。除以 後是每像素向量的平均平方誤差,沒有再除以通道數。同一位置的所有候選使用相同重疊集合,因此正規化不改變排名;與其他誤差合併時,這個尺度卻很重要。第一個位置的 為空,直接定義 ,不要除以零。
確定性合成可在 最小的候選中選字典編號最小者。若希望增加變化,也可在滿足 的候選中抽選,其中 須先指定,並記錄隨機種子。當 且 時,相對容差只容許精確零誤差匹配。隨機選擇讓不同運行有變化,卻沒有因此建立自然紋理的概率模型。
穿過左重疊區的接縫
定義 1.26.4
(可行接縫與接縫代價)
先假設只有左條帶被覆蓋。接縫是一列列索引 ,滿足
每行恰有一個接縫位置,每下降一行最多橫移一列,第一列不能繞回第 列。除非明確限制,頂端與底端均可自由選擇。固定候選後,接縫代價為
本節的貼入慣例是: 時保留舊值, 時複製 。所以接縫位置本身屬於舊影像。把接縫位置分給新區塊也是一種可能慣例,但會改變若干貼入像素,必須交代。
常見錯誤
(接縫代價不是整個重疊誤差,也不是可見的跳躍)
這個代價比較的是相同座標上兩個提案的差異。它既不是整個重疊區的差異總和,也不完全等於完成影像中相鄰像素的跳躍。若想優化平滑度或梯度,應另立目標。離散接縫模型的用處,正是提供一個能精確求解及檢視的代理量。
定理 1.26.5
(在指定路徑類別內求精確最小接縫)
對固定的 有限非負誤差陣列,令 ,並對 定義
則 是從首行走到 的可行路徑最小代價。完整接縫最小代價為 。在每個狀態保存一個達到最小值的前驅,再從最小底部狀態回溯,便得到最優接縫。平手時可選最小列索引以便重現。
證明
(動態規劃遞推式給出精確最優值)
首行每一列只對應一條單點前綴,所以初始化正確。假設第 行的結論成立。任何走到 的路徑必從列出的某個前驅列 而來;其前綴代價至少為 ,因此總代價至少為遞推式右側。反過來,選一個達到最小值的前驅。由歸納假設,確實存在一條到達它的最優前綴;加上 仍可行,且達到右側的值。下界可取到,故歸納得到所有狀態的結論。完整路徑必在某個底部列結束,取底部最小值便得全路徑最優值,保存的前驅構造出達標路徑。此論證使用有限狀態及每步向下一行的性質,沒有依賴尚未決定的未來選擇。
證明透視
為何終點足以代表前綴狀態
兩條在同一行、同一列結束的前綴,擁有完全相同的後續選擇。以較便宜的前綴替換較貴者,不會封鎖日後的移動;這是遞推成立的關鍵。如果另規定整條路徑最多可斜走若干次,只有終點便會遺失必要資訊:狀態還須記錄已斜走的次數。遞推式只能證明其狀態實際保留的限制下之最優性。
若頂端必在 ,把其他首行列初始化為 ;若底端必在 ,只在 上取最後最小值。禁用位置也賦予無限代價。最後值有限便證明存在可行路徑;若為無限,則沒有允許路徑。使用擴充實數慣例:有限 滿足 ,而 。此時歸納敘述為:有限狀態有達標路徑,無限狀態則不可達;允許且有限的前綴可以延伸,沒有允許有限前驅的狀態則無法到達。這些是邊界條件,不是隨意引入網格外前驅值的理由。當 時,只有唯一接縫。
命題 1.26.6
(接縫遞推式的時間代價)
共有 個狀態,每個至多三個前驅。計算全部數值需要 時間;直接回溯使用 前驅儲存。若只求代價,可用兩行、即 記憶體,但重建路徑仍須保存決定,或另行指定重算方法。
證明
(統計狀態與轉移)
每個狀態只計算一次,取至多三個已存數值的最小值,並記錄一個前驅索引。第 行只依賴第 行,所以只保留兩行數值便只需 記憶體。
上條帶可用轉置後的相同論證:以 表示每列的一個行索引,滿足 、,在 時保留舊像素。
完整二維條帶算例
例題 1.26.7
(從兩個區塊提案算到實際貼入陣列)
取 、,原有左重疊區十二個位置全為零。灰階候選為
其左重疊誤差與累積代價陣列分別為
例如 ,不可使用不存在的第四列前驅。底部唯一最小值三在第二列。回溯得到 ,代價為 。保留舊值的遮罩與最後區塊範圍為
遮罩一代表舊值,零代表新值;未覆蓋的第四列必須取自 。原重疊平方誤差和為 ,故 ,接縫代價則為三。兩個數字分別在不同像素集合上求和,不應把它們報成影像品質改善的百分比。這只是刻意縮小的算術例子,並不是織布合成效果的證據。
反例模式
逐步選最便宜像素,代價可比最優值大任意多
考慮誤差陣列
先選首行最小值,再逐行選可達位置中即時誤差最小者,會在第一列起步,第二行仍留在第一列。第三行無法一步到第三列,故至少須付 。若平手選最小列,第四行再付 ,總數為 。但 可行且只花一。它確是最優:零代價路徑必須依次使用第一、第一、第三、第三列,違反移動限制;其餘正數項均至少為一。把每個 換成任意 ,貪心代價仍至少為 ,最優值卻保持一。修正方式是在每列保留最好的累積前綴,不是只保留眼前最便宜的移動。
內部角落與完整掃描構造
內部位置若只選垂直接縫,便未處理上重疊區;只選水平接縫也未處理左重疊區。我們採用一個簡單且明確的合併規則:針對同一個凍結的舊影像 及候選 ,在完整左條帶求垂直接縫 ,在完整上條帶求水平接縫 。不要貼完一個條帶後才計算另一個。把兩者舊值側的並集保留下來:
其他位置全部複製 。因 、,此規則不會索取 以外不存在的舊像素。又因每個位置只有一個二元決定,角落不會重複寫入或含糊平均。
例題 1.26.8
(寬度為一的內部角落)
取 、。兩條接縫都是唯一的,,所以
舊影像提供首行及首列, 提供餘下 方塊。重疊共有五個像素,而非六個。
常見錯誤
(兩條條帶最優接縫並不構成最優的角落切割)
並集規則完整指定了貼入,但分別的接縫定理沒有證明合併邊界在 L 形重疊區上最小化某個共同能量。兩條獨立路徑可能互相影響,或令對方部分邊界不再顯露。若要全域優化該區域的二元遮罩,須先定義遮罩能量及邊界條件,再為該問題證明算法。不可把這個較強結論暗中加到兩個條帶結果上。
現在有限拼接程序已可逐步執行:
- 固定字典、、色彩表示、選擇規則,以及所用隨機種子。第一塊按已聲明的起始規則選擇;不採隨機時取最小字典編號。
- 在其後每個掃描位置凍結 上的現有輸出,並集像素只計一次,算各候選的 並選一塊。
- 在已覆蓋條帶上求垂直及/或水平最小接縫。只有一條帶時使用其舊值側;兩者都有時用並集規則。
- 遮罩一的位置取舊值,其餘位置取候選值,完成整個區塊範圍後前往下一個預定位置。
按貼入次數歸納可知,所有向 索取的值都已存在:它們都在覆蓋條帶內;新露出的位置則全部由 填滿。有限的 次訪問後,矩形完整填好。這是終止與像素歸屬論證,並非能量下降定理。後來的區塊可以覆寫先前區塊的一部分;我們沒有證明每次貼入都降低某個固定全域目標,也沒有搜尋所有可能拼接影像。
窮舉字典時,每個位置的重疊評分需 ,兩條接縫合計需 ,複製需 。取得源區塊、計算特徵及加速搜尋是另外的工作。
常見錯誤
(整體重疊最匹配不等於接縫最佳)
整個重疊誤差最小的候選,不一定具有最便宜的最佳接縫:評分與切割的目標不同。應按下一步實際使用的量來排序,或說明為何這個代理量已足夠。
紋理轉移:讓第二幅影像引導選擇
純合成希望取得另一幅像源紋理的樣本;紋理轉移還希望目標影像引導不同紋理出現的位置。暗的目標區域可以要求暗的源材料,亮區則要求亮的材料。這不會恢復目標物件的真實材質或三維形狀,只是限制選定的影像表示。
在輸出矩形上指定目標對應場 ,並給每個候選一個相容的區塊對應場 。它們可以是灰階強度、預先計算的低頻色彩場,或明確選定的特徵。必須交代維數、單位與預處理;若各區塊獨立重縮放,可能正好移除了目標想控制的亮度資訊。
定義 1.26.9
(對應代價與合併轉移代價)
對固定非空集合 及區塊位置 ,使用
一般可取整個區塊作 ;也可以取明確記錄、具有有效目標資訊的子集。兩個誤差須有相容尺度,或另有明確權重慣例。 只表示數值係數相同,不會自動表示感知影響相等。
選擇 最小者,再完全按前面的規則求接縫及貼入。第一塊的 ,在 時由對應項決定; 時全部平手,按起始規則選取。第一塊沒有接縫。至此得到完整的單次掃描轉移程序。接縫本身仍最小化重疊差異,而非對應誤差。另外, 評的是候選提案;保留舊像素可能令完成後的區塊範圍不能達到該分數。因此,完成影像與目標的符合程度仍須另外量度。
例題 1.26.10
(目標可改變選中的二維區塊)
取 、,內部重疊的三個舊值全為零,候選為
把較小字典編號分給 。其平均重疊誤差為 、。這個小例子只在新露出像素使用灰階對應:,該點目標值為三。因此 、,合併代價為 、。當且僅當 時 勝出; 時 勝出;相等時用編號規則。若 ,兩者分數為五及 ,故選 。寬一的接縫無選擇,保留首行及首列,得到 。唯一新露出位置的目標誤差是一。本例指定了實際區塊、目標、評分、接縫及貼入結果,沒有從一個像素推斷整體結構獲得保留。
有限模型留下哪些實際評估問題
接縫代價很低,仍可能在複製區塊較深處出現磚邊接錯行。大區塊保留較多內部結構,卻只有較少獨立排列機會;小區塊較自由,但未必容納一個完整圖案。增加重疊使選擇更受限,也增加搜尋工作。這些取捨不會給出一個通用最佳尺寸。
色彩平方誤差受曝光、對齊及色彩座標影響。亮度正規化可能修復照明差異,亦可能破壞刻意指定的目標亮度關係。模糊後的對應場可以保留大範圍明暗,卻丟失細輪廓。一個對應純量不會編碼語義身分、可見性或幾何;即使目標特徵精確一致,紋理也可能不合適。
實際評估應交代範例與目標、區塊和重疊尺寸、隨機種子,展示全圖及接縫、長結構的局部放大,並比較相同設定下的多次運行。要隔離切割決策,可固定區塊提案,比較矩形貼入與接縫貼入;要隔離目標項,可固定字典,比較只用重疊與加入轉移分數。應用已聲明的特徵提取器,在完成影像上量度對應誤差,包括保留的像素,並說明指標沒有量度甚麼。這些是建議的評估控制,不是本節已完成的實驗。上述數值結果都沒有證明自然影像的品質。
習題
快速檢查
(設 、。求步長、兩行三列區塊的影像尺寸,以及內部位置的重疊大小。解釋為何須扣除角落。)
解答 · 答案
步長為 ,高為 ,寬為 。每個條帶有十像素,分別相加卻把 角落計了兩次。因此並集有 像素。若直接相加兩條帶分數,便會額外加重角落權重,除非本來就明確想這樣做。
快速檢查
(對 、、各行依次為 、、 的左條帶誤差陣列,計算全部動態規劃值及一條自由端點最優接縫。再把頂端限制在第一列、底端限制在第二列,重做計算。)
解答 · 答案
自由端點的累積陣列為 。底部第一列以一達到最小值;回溯得到 ,代價 。限制頂端後,首行是 ,第二行 ,第三行 。底端再限制於第二列,得到代價五及路徑 。自由端點的一不可用於受限問題,邊界限制確實改變了問題。
快速檢查
(解釋按整個重疊誤差選區塊,為何不同於按最小接縫誤差選區塊。用三行兩列左條帶誤差(、)驗證: 的每一行都是 , 的每一行都是 。)
解答 · 答案
的重疊誤差和為 ,但第一列直線接縫代價零; 的誤差和為六,任何完整接縫均花三。取平均只把兩個總數同除以六,因此平均重疊排名仍選 ;最小接縫排名則選 。在 區塊內取全零舊重疊,左兩列候選值等於各誤差的平方根,便可實現這些條帶陣列;第三列任意。任一排名都沒有交代重疊外的區塊內容。
快速檢查
(對橫移加入非負懲罰 。推導遞推式並解釋所需狀態。在主要四行算例中,證明 時, 比原本最優的 更便宜。只比較這兩條路徑足以證明常列路徑全域最優嗎?)
解答 · 答案
初始化不變,遞推為 。當前終點仍決定所有允許的下一步及轉移代價,所以前綴替換證明仍成立。 時,折線差異三,加三次橫移,總代價十二;第二列直線為 。只比較兩條路徑不能證明全域最優。實際遞推四行為 、、、,所以常列路徑確實達到全域最小值十,但不是唯一最優。另一條最優路徑為 :差異七加一次橫移懲罰三,亦得十。第二行第二列的第一、第二列前驅平手,所以最小列前驅規則會回溯出後一條路徑。
快速檢查
(在轉移算例中,把較小編號分給 。求 、、 時的選擇及貼入結果。解釋為何使用全部四個目標像素是另一模型。)
解答 · 答案
時只看重疊,選 ;唯一複製的內部值為零,所以結果全零。 時對應項選 ,得 。 時分數同為 ,以較小編號選 。在全部四個像素上定義對應誤差,須另外提供四個目標值,且把其中三個由舊影像保留的像素納入評分,一般會改變分數及分界。不能由題目僅提供的一個目標值杜撰其餘數值。