動機
一小張石面照片包含局部紋理資訊:相鄰強度模式、重複邊緣和特定色彩組合。若想把它延伸,直接重複整張照片會暴露長方形週期。另一做法是重新安排較小區塊,同時要求重疊部分相容。這是很具體的數據驅動合成:局部候選來自量得的樣例,而非石頭的解析方程。
「數據驅動」並不取消模型選擇。我們仍要定區塊大小、色彩表示、相似度、輸出約束及搜尋程序。重疊吻合的區塊,可能在應延續水平結構的位置放一條垂直裂紋。反過來,要求每塊完全等於來源樣例,也可能因鄰塊互相衝突而不可能。有用的模型應顯示取捨,而不是用一幅漂亮結果遮蓋它們。
以下刻意建立有限模型,使算法有精確終止證明,也可以手算完整執行。它不是完整現代紋理合成器,更不是所有影像類別的統計模型。其教學價值在於分清最近鄰選擇、重疊提議的協調,以及目標值下降與影像可信之間的距離。
定義
定義 1.27.1
(含觀測值的有限樣例能量)
為清楚起見,用固定有限網格的灰階輸出 ,每值屬有限非空字母表 。位置 的提取器 選出 個像素。有限字典 來自指定樣例區塊,字典值未必窮盡輸出字母表。彩色版本以向量代純量,且須明定色彩距離。
標籤 指定該位置選哪個字典區塊。已觀察位置集合為 ,值為 ,取 ;另可把集合 內像素硬性固定為字母表中的指定值。定義
這是優化目標,不自動是概率或校準知覺分數。它要求輸出區塊接近字典成員,並讓已觀察像素抵抗變化。硬性固定與有限懲罰不同:即使改動固定像素能減少區塊誤差,也不允許改。
定義 1.27.2
(消去標籤後的能量)
消去標籤,得到
對當前影像,每個區塊各選最近鄰;重疊像素再把這些決定耦合。獨立複製的候選不一定相容,整體目標也沒有因此變成凸函數。
定義 1.27.3
(係數與提議總和)
固定標籤後, 是像素 出現於各區塊的次數,若 再加 ; 是所有字典區塊在該位置的提議值總和,若有觀察再加 。這些係數逐項計算目標中的每次出現。假設單一提取器內沒有重複同一像素,不同區塊共享像素則正是模型核心。
定理 / 命題
定理 1.27.4
(精確座標更新是最近區塊與最近平均值決策)
固定 ,最小化一個標籤等於搜尋 的最近字典區塊。固定標籤和其他像素後,非固定像素若 ,應選最接近 的字母表值;若 ,其值不影響目標。結論針對此平方誤差模型,遇平手不宣稱唯一。
定理 1.27.5
(有限模型的嚴格座標下降必會停止)
按固定次序反覆訪問每個標籤及非固定像素。只有精確最小化能嚴格降低目標時才更新;平手保留當前值。則狀態只會改變有限次。一整輪沒有變化時,當前狀態是逐座標極小值,但未必是全域極小值,終止也不證明知覺品質。
此終止論證必須使用有限字母表。若強度連續,目標下降且有下界,可以讓能量值收斂,卻未必有限步停止。近似最近鄰搜尋也不自動保留精確逐座標最小性。仍可在驗證下降後接受提議,但停止時能宣稱的性質需要相應減弱。
證明思路
證明
(標籤與像素的精確更新)
一個標籤只出現在 ,所以更新就是有限最近鄰搜尋。把涉及像素 的項收集起來,忽略與它無關的常數; 時為
因此最佳允許值最接近加權提議平均。這是協調多個提議,不是說平均值本身屬某個字典區塊。硬性固定像素無論係數如何,都排除在更新之外。
證明
(嚴格改變只有有限多次)
可行影像與標籤狀態至多 個。每次改動嚴格下降,故不能重訪狀態,總改動次數至多為狀態數減一。這個界可以極大,只是正確性論證,不是高效最壞情況保證。一整輪不變時,每個座標都在同一固定狀態下受檢查,因此沒有單座標嚴格改善。
證明透視
平手保留現值為何重要?
不同狀態可以有相同能量。若求解器不斷在同樣好的標籤間切換,有限狀態本身不能排除循環。平手不動,才使真正改動都有嚴格進度量。浮點程式還要交代比較規則;容差會改變「無改善」的意思,不能預設等同精確逐座標最小。
固定標籤後,不同輸出像素的目標可分離,因此同時按最近平均規則更新全圖,也精確最小化影像這一組座標。但聯合問題仍非凸,因標籤一變,提議亦變。初始圖、硬約束與字典可導致不同終點。隨機初始化能探索替代結果;隨機種子能記錄執行,卻不能保證選到最佳結果。
例題詳解
例題 1.27.6
(完整追蹤一次有限合成)
三個輸出像素,字母表 ,區塊 、,字典 、。固定 、,沒有觀察懲罰。由 、標籤 開始,能量 。第一塊到兩樣例的平方距離均為四,保留標籤一;第二塊改選標籤二,能量降至四。中間像素收到零與二的提議,平均一,所以改成一,能量降至二。下一輪第一塊到首樣例成本一、另一樣例五;第二塊相反,所以標籤保持 。像素平均仍是一,整輪不變,終點為 、能量二。
例題 1.27.7
(觀察數據怎樣改變提議平均)
兩個區塊在某自由像素提議零、二;觀察 ,懲罰 。故 、,無限制平均是 。在字母表 ,一與二平手,能量均為四,而零的能量十二。若當前值是一,嚴格更新規則保留它。更大觀察懲罰可偏向二,卻仍不等於把像素硬性固定。
例題 1.27.8
(逐座標極小值可以錯過最佳狀態)
只有一個輸出像素 ,字典是單像素零及二,觀察 、。狀態 能量 ;只改標籤變 ,只改像素變四,所以是逐座標極小值。但同時改成 ,能量為零。即使精確更新且完全沒有數值誤差,有限算法仍可能在次佳狀態停止。
第一例也顯示重疊合成實際做了甚麼:最終兩個輸出區塊是 、,均不等於字典成員。共享像素協調導致折衷。若更重視完整保存來源紋理元素,可以改為在複製區域間選邊界;但那是另一個帶自身約束的優化問題,並不是本目標隱含的功能。
概念視角結構
樣例是有限詞彙,重疊則是組合約束
字典列出模型能提議哪些局部模式;重疊項決定鄰近提議能否一致共享像素。有效局部區塊詞彙不等於牆壁、人臉或物件的全域描述。增大區塊加入長距離資訊,也增加搜尋成本與直接複製風險。區塊尺度決定哪些結構受直接約束,哪些只期待由局部相容湧現,或根本不出現。
窮舉標籤一輪,在 位置各比較 個 維候選,約需 次純量運算。收集提議和約需 ,直接搜尋字母表約需 。這些是每輪成本,並不保證輪數是小常數。記憶體還要存字典與標籤場。狀態有限不是實際枚舉全部狀態的好理由。
常見錯誤
反例模式
零局部誤差不保證想要的場景
若字典只有常數零與常數一區塊,沒有數據項禁止時,全零輸出的區塊能量為零。即使目標是磚牆,該數值也沒說明磚塊幾何,因字典與約束根本未編碼它。要修正結論,須先論證目標代表所需結構,再做適當評估;只最小化方便計算的數,不能建立真實感。
常見錯誤
(把合成補全當作實測數據)
沒有統計模型,不應把最近鄰距離當概率。從樣例複製的區塊,也不等於破損照片缺失部分的觀察真相。樣例恢復是在假設下提供合理填補,同一已知像素可容許多種完成。清晰結果仍可能加入無根據細節;用途需要時,應記錄樣例來源並分清量得與合成區域。
常見錯誤
(原始區塊距離不具平移不變性)
區塊距離還取決於尺度及對齊。一像素平移,可以讓同一重複邊緣在原始歐氏(Euclidean)座標中相距很遠。旋轉、照明正規化或特徵距離會改搜尋,但每項不變性亦會丟掉某些區別。新增彈性應回應實際模型需要,不應只為降低殘差而把不同模式視作相同。
總結
樣例目標把最近局部提議、重疊及觀察約束結合。標籤更新選字典鄰居,影像更新協調像素提議。有限字母表及嚴格平手規則保證有限步到達逐座標極小值,沒有全域最佳或知覺真實感保證。完整小例使執行可核查,也顯示相鄰區塊不相容時的折衷。
練習
快速檢查
(在完整合成例中枚舉四組標籤,對自由 最小化,驗證聯合最佳能量,並指出其他標籤為何較差。)
解答 · 答案
標籤 的能量 ,在零得四; 為 ,在二得四; 為 ,在一得二; 為 ,在一得十。因此這個例子的終點碰巧是全域最佳,但不能推廣,另例已展示反例。
快速檢查
(兩個區塊提議一與三,觀察提議零,。在字母表 求全部最小像素值及能量。)
解答 · 答案
、,平均一,是唯一字母表最小值。能量 。配方為 ,同時驗證最小值與唯一性。
快速檢查
(一像素字母表 、字典零與二、、。精確判定何時 是嚴格更新規則下的逐座標極小值,並與全域最佳比較。)
解答 · 答案
當前能量 ,只改標籤必加四;只改像素得四,因此恰在 有嚴格改善。 時是逐座標極小值,等於一時平手保留。聯合狀態 總有零能量。因此 對所有正 能量為正,而當它確是逐座標極小值,即 ,便是全域次佳。
快速檢查
(五個自由像素各有四值,三個區塊標籤各有兩選擇。給嚴格狀態改動次數上界,並解釋等能量改標籤與近似最近鄰停止為何需要不同保證。)
解答 · 答案
狀態數 ,故嚴格改動至多 8191 次。這個寬鬆界算改動,不算座標測試。等能量改動可以重訪狀態而循環;近似搜尋可能漏掉更佳標籤,所以無改動一輪只能證明已測提議沒有改善,除非另驗精確最近鄰最優性。