[發明專利]基于壓入與重標記可提前終止的最大流最小割求解算法

在審

• 申請號: 202110421777.5
• 申請日: 2021-04-20
• 公開（公告）號: CN113139976A
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 劉心哲;閆光耀;哈亞軍
• 申請（專利權）人: 上海科技大學
• 主分類號: G06T7/11
• 分類號: G06T7/11
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 徐俊;柏子雵

本發明提供了一種基于壓入與重標記可提前終止的最大流最小割求解算法，用于不需要確切最大流量的應用，其特征在于，由分離條件和穩定條件構成Push?relabel算法的提前終止條件；在Push?relabel算法進行過程中的任意時刻，若集合T中不存在源點s，s∈S，則滿足分離條件；若集合T中不存在任何活躍節點則滿足穩定條件；若分離條件及穩定條件都滿足，則Push?relabel算法終止。本發明提出了一種新穎的提前終止技術，可以大大消除冗余計算，并確保算法在所有情況下都能正確終止。實驗結果表明，使用新的終止條件可以在測試數據中將計算量平均減少到原來的2％。

技術領域

本發明涉及一種基于壓入與重標記算法能夠提前終止的最大流最小割求解算法。

背景技術

Graph cut算法已廣泛用于解決最小切割問題，該問題在計算機視覺任務中很普遍。這些任務將圖像像素映射到圖的節點上，然后為圖的每個節點分配最可能的標簽。基于此，應將圖中的所有節點切成兩個不相交的集合，即集合S及集合T。切應使特定于應用場景的成本函數最小化。最小切割問題通常可以轉換為最大流量問題，因為它更直觀且更易于解決。這些任務廣泛出現在圖像/視頻分割、圖像/視頻拼接、雙目視覺匹配、分類、圖像融合、圖像去霧、骨架化、風格遷移等。

先前的工作表明，圖割可以產生令人印象深刻的結果質量，但是，在實際應用中相對較慢。現有的實現通常不能充分利用應用場景特點來減少冗余計算。例如，在發生最大流量問題的許多應用中，僅需要最大流量的值或最小切，而不需要完整的最大流量。

先前的工作還嘗試優化推入重貼標算法的計算。全局重新標記通過使用全局信息更新高度標簽，減少了集合T中的冗余重新標記操作。相反，間隙重新標記通過更新高度標簽的分布來減少集合S中的多余的推入和重新標記操作。此外，JF-cut提出了一種提前終止技術來去除冗余計算。只要沒有找到增加路徑，它就會終止推入重貼標簽算法。但是，它們的提前終止條件過于激進，因為它不能確保算法在所有情況下都能正確終止。

發明內容

本發明要解決的技術問題是：現有的Push-relabel通常無法充分利用應用場景特點來減少冗余計算，因此不適合具有高分辨率和實時要求的應用程序場景。

為了解決上述技術問題，本發明的一個技術方案是提供了一種基于壓入與重標記可提前終止的最大流最小割求解算法，用于不需要確切最大流量的應用，其特征在于，由分離條件和穩定條件構成Push-relabel算法的提前終止條件，在殘差圖中，設可以達到匯點t的所有節點v構成集合T，其余節點構成集合S；在Push-relabel算法進行過程中的任意時刻，若集合T中不存在源點s，s∈S，則滿足分離條件；若集合T中不存在任何活躍節點則滿足穩定條件；若分離條件及穩定條件都滿足，則Push-relabel算法終止，其中：

將分離條件定義為：殘差圖中不存在從源點到匯點的增廣路徑；

將穩定條件定義為：殘差圖中不存在從任一活躍節點到匯點的增廣路徑。

本發明的另一個技術方案是提供了一種上述的基于壓入與重標記可提前終止的最大流最小割求解算法的應用，其特征在于，用于僅需要最大流量值或最小割斷但不要求最大流量的應用。

本發明設定的分離條件保證了所有節點v構成的集合V已經被分割為兩個不相交的集合S和集合T，也即已經產生了一個(s，t)-cut。本發明設定的穩定條件保證了產生的(s，t)-cut直到算法滿足原始終止條件都不再會發生變化。

本發明提出了一種新穎的提前終止技術，可以大大消除冗余計算，并確保算法在所有情況下都能正確終止。實驗結果表明，使用新的終止條件可以在測試數據中將計算量平均減少到原來的2％。

附圖說明

圖1為多個測試用例的結果；

圖2為通過更多測試數據獲得的統計結果。

具體實施方式