動機
運動估計與分割都從圖像證據推斷隱藏量,卻需要不同算法。光滑運動模型可能導出正定線性系統,二元區域模型則可能導出網絡最小割。把兩者都稱為能量最小化,不代表可交換它們的保證:前者用二次譜分析,後者用非負容量及流量守恆。
本節把兩種方法推導到可核對的程度。光流顯示貌似物理的方程如何留下不可辨認方向;圖割顯示受限制的非凸二元搜尋也能有精確全局證書。每個構造也給出一個反例,提醒不可隨意推廣。
亮度不變、運動光滑、固定區域亮度及有理容量都是下文明確使用的假設。它們是建模選擇,不是對所有圖像的宣稱。
定義
定義 7.1.1
(光流約束)
若可微圖像序列 沿運動點 保持亮度,速度為 ,鏈式法則給出光流約束
每點只有一條方程,卻有兩個速度分量。小窗若假定共同速度,可用行向量 及右端 做加權最小二乘,權重 。未正則化解唯一需要加權梯度生成平面。
定義 7.1.2
(正則化稠密光流能量)
稠密場把水平及垂直分量分組堆成 。 逐像素作梯度與速度內積, 收集時間導數, 分別計算兩分量的空間差分。正則化能量為
幅值懲罰保證唯一性,亦引入偏差,不能稱作量度到的運動資訊。令 ,完整梯度算法為 。
定義 7.1.3
(二元分割能量及其割網絡)
設 ,固定非負一元代價 及非負鄰邊權重 。二元能量為
網絡有源點 、匯點 及每像素一節點,標記零代表源側。弧 容量為 , 容量為 ;每鄰對加雙向、各容量 的弧。割容量只計由源側指向匯側的弧。
此步最優化期間,用來計算一元代價的區域亮度固定不變。
定理 / 命題
定理 7.1.4
(有限光流求解的收斂)
對稱正定,唯一極小解為 。若 ,則任意初值的梯度迭代收斂,且
這是固定線性化亮度模型的保證,不是原非線性變形的全局結論。
第二個結果不再依靠譜控制,而是在剛才定義的網絡上給出組合證書。
定理 7.1.5
(精確二元割與有限最大流證書)
上述網絡每個二元標記的割容量正好等於 ,每個割亦決定一個標記。有理容量先同乘公分母變成整數,再沿剩餘源匯路徑增廣,必有限停止。停止時的剩餘可達集合給最小割,容量等於可行流值,故其標記是固定二元能量的全局極小解。
這限制在非負、偏好相同標記的鄰邊作用。任意多標記或運動能量未必能如此表示;固定區域亮度的全局割,也不等於同時把亮度與標記全局最優化。
零容量弧是合法情形,剩餘搜尋只沿嚴格正容量前進;保留此區別,才能正確處理平手與已飽和的邊。
證明思路
證明
(正定性與譜收縮)
對非零 ,,微分即得唯一解。從更新式減去其法方程,誤差滿足 。譜定理在正交特徵基中給出全部因子 ,步長條件使其都嚴格落在 內;取最大絕對值便得到幾何收斂。若刪除幅值項,且 ,唯一性改需 ;光滑性本身不能保證。
證明
(割容量、流量下界與有限停止)
標記零的節點在源側,只付指向匯的 ;標記一只付源指向它的 。鄰對同側付零,異側恰有一條弧跨割,付 。逐項相加便得能量等式。
可行流不超容量,且各非端點守恆。對任意源側節點集合求和,流值等於離開集合的淨流,不超過外向割容量,這就是下界證書。從零流開始,在正剩餘容量中搜尋源匯路徑,例如用廣度優先搜尋,再沿路徑增加最小剩餘容量。正向剩餘弧用未用容量,反向弧容許取消已有流。增廣保持容量與守恆;整數情形每次至少增加一,而總流有源外向總容量上界,因此有限停止。有理容量可先縮放;這個簡單論證不聲稱對輸入位數有良好複雜度。
停止時取由源經正剩餘弧可達的節點為源側。所有原來離開此集的弧已飽和,所有進入此集的弧流量為零,否則其反向剩餘弧會擴大可達集。因此淨外向流等於割容量。任意流不超任意割的界,便同時證明兩者最優。這解釋為何須同時給流與割,而非只憑標記外觀判斷。
證明透視
割證書在哪裏使用每個假設
證明分為三部分,各用不同假設。能量等式只用標記約定:標記零在源側,才使 承載 。流量下界用非負性:零流可行,是因為每個容量至少為零;「流值不超割容量」這一步捨去內向跨割流,是因為它非負。有限停止用整數性:每次增廣至少加一,而流值有界,計數論證便能收結;對任意實數容量,這個計數給不出界。
唯一不顯然的一步是停止時割的選法。證明不搜尋全部割,而直接取剩餘可達集 。關於 的兩個事實把不等式變成等式:離開 的弧已飽和,否則正向剩餘弧會離開 ;進入 的弧沒有流,否則反向剩餘弧會離開 。一個流與一個割相等之後,普遍下界同時使該流最大、該割最小,而能量等式把最小性轉移到標記上。負容量在第一步就破壞論證,所以下文真正重要的條件是保證 的次模性。
相比之下,運動部分的證明較短:正定性給出唯一性,步長條件給出每個特徵方向的收縮。
例題詳解
例題 7.1.6
(平滑不能辨認均勻切向運動)
取 ,亮度式只有 ,不含 。即使加入空間平滑,任意常數垂直速度的差分都是零,仍然不可分辨。單像素若取 ,最小化 得 。先驗帶來唯一性,同時水平分量也有偏差;垂直零值不能報告成量度證明物體沒有垂直運動。
例題 7.1.7
(匹配流量的明確二像素割)
兩像素亮度零與二,區域亮度零與二,用平方誤差得到代價對 、,鄰權重為一。四個標記 的能量依次為四、一、九、四。源至第一點容量四,第二點至匯容量四,像素間雙向容量一,另兩條端點弧為零。沿源、第一、第二、匯送一單位流;把兩像素分側的割容量也是一。匹配流與割證明 全局最優,不必靠窮舉。
例題 7.1.8
(不對稱次模鄰對的表示)
若 ,令 、、。則 ,逐一代入可核對。線性項加到一元代價;若一元項為負,從該像素兩種代價都減去較小者,並記錄移出的常數,就得到非負容量而不改變最優標記。
一般只要 ,便可解四條純量式得 、、。次模條件恰好保證邊容量非負。先累加所有一元項和常數再建圖;忘記常數即使未改標記,也會使流值與原能量的證書比較失真。
進階配準可取仿射變形 ,參數順序為 。殘差 的 Jacobian 行為
導數在變形點計算。加權行向量須生成六維參數空間,才有唯一未正則化增量。只選三個不共線位置不足以保證強度配準:每條亮度殘差只提供一個純量,梯度方向也重要。每次增量後重新變形、計導數,並檢查原殘差;線搜尋可拒絕增加能量的步。粗到細可改善起點,卻不消除重複紋理與遮擋歧義。
概念視角結構
固定證據與改變未知量的分別
割是在固定一元數據下最優化標記,之後重估區域均值就改變了代價、產生新問題。交替精確割與非空區域的精確均值,使聯合平方誤差能量不增加;若區域為空,保留之前的亮度值。這種不增序列仍不保證全局最優。同樣地,精確解線性化配準並不等於全局解原來的非線性變形。
常見錯誤
反例模式
排斥鄰對不能直接用非負割邊
若 、,公式要求 。負容量不符合最大流證明,不能直接放進此網絡。這只說明指定標記約定下的吸引式構造失效,不是所有改寫都不可能。單一鄰對可反轉一個變量的標記來轉換作用,但多個相互耦合鄰對未必能用一致重標同時修補。
光流量度表觀亮度運動,反射與照明變動可令它不同於表面物理運動。光滑懲罰也可能把誤差傳過真實運動邊界。
常見錯誤
(交換端點弧的約定)
標記零在源側時, 必須承載 。若改用 建 ,實際最小化的是每對一元代價互換後的能量。在二像素例中,互換後第一像素的端點容量為 ,第二像素為 ;最小割容量為一並給出 ,而它的真實能量是九,是四個標記中最差的。
常見錯誤
(迭代上限不是最優證書)
增廣程序只有確認不存在正剩餘路徑才有停止證書。任意迭代上限後,當前流值仍是有效下界,已找到的最佳標記是上界;誠實的報告是兩者的差距。只有差距為零才證明該標記最優。
總結
亮度不變導出局部與稠密光流,可辨認性須與正則化分開。正定有限二次模型有可證收斂的梯度算法。二元吸引式分割有精確割表示及最大流證書;次模條件保證本構造的邊權非負。非線性變形、變動區域均值、排斥作用及取樣誤差仍須各自處理。
練習
練習 7.1.9
(小窗方程為 、,求未正則化最小二乘速度與結構張量。為何不同於重複第一條兩次?)
基礎
解答(2)
- 1
解兩條獨立方程
兩行為 與 ,故 、,解為 。結構張量是 之和,即 。
- 2
與重複約束比較
兩方向各有獨立約束。重複水平式只得 ,垂直分量仍任意;樣本增加不一定增加秩。
練習 7.1.10
( 特徵值為一、四,求合法常數步長區間,計算步長 的收縮因子,並說明步長 時的情況。)
基礎
解答(3)
- 1
代入步長條件
,故條件為 。
依據: 定理要求 。
- 2
計算 的模態因子
因子為 與 ,所以範數收縮因子為 。
- 3
檢查端點
第二因子為 ,該方向的非零誤差只反號而不衰減。定理中上端點必須嚴格排除。
練習 7.1.11
(鄰對值為 ,求非負邊權與一元係數,並驗證全部四個值。)
核心
解答(2)
- 1
計算係數
,,。
- 2
核對四個標記
故 ,依序給零、三、一、二。常數為零,這例中所有邊及一元容量均非負。
練習 7.1.12
(證明對任意可行流與任意割,割容量減流值非負。若某標記能量為五而某可行流值為四,可證明甚麼,還不知道甚麼?)
核心
解答(3)
- 1
寫出跨割的流值
流值等於外向跨割流減內向跨割流。
依據: 對源側節點把守恆式求和。
- 2
逐項估計
關鍵一步
外向流不超外向容量,內向流非負,故流值不超割容量。
- 3
解讀數值
最優能量位於四與五之間,候選標記距最優至多一能量單位。兩值相等才證明精確最優;目前不相等,不能決定哪個中間值可達。