[發明專利]一種并行快速符號距離函數計算方法

有效

• 申請號: 201710323415.6
• 申請日: 2017-05-09
• 公開（公告）號: CN107330896B
• 公開（公告）日: 2020-07-03
• 發明（設計）人: 江少鋒;艾信友;張聰炫;陳震
• 申請（專利權）人: 南昌航空大學
• 主分類號: G06T7/11
• 分類號: G06T7/11;G06T7/155;G06K9/62;G06K9/34
• 代理公司: 南昌洪達專利事務所 36111
• 代理人: 劉凌峰

1.一種并行快速符號距離函數計算方法，它包括如下步驟：

1)符號計算步驟，采用區域生長法確定區域內部和外部，從而得到距離符號值；

2)Y方向計算步驟，該步驟通過并行方法得到圖像上各點在Y方向上到封閉曲線距離值D_f|x'(y)，對于寬度為W，高度為H的圖像，分配W*H線程，每個線程負責圖像中一個點的符號距離計算；封閉曲線上的點記為源點，對于每個源點以步長1分別向上和向下延伸到圖像邊界，經過的點的D_f|x'(y)即為延伸的步長數，記錄其相應的源點；在進行延伸時，如果經過的點已有源點存在，則其存在多個源點，那么取離它距離最近的源點的距離作為D_f|x'(y)；

3)X方向計算步驟，該步驟通過并行拋物線下界方法得到圖像上各點到封閉曲線最短距離值D_f(x,y)；對于寬度為W，高度為H的圖像，分配W*H線程，每個線程負責圖像中一個點的符號距離計算；計算分兩步，第一步向右計算階段，并行計算每個點對應的拋物線和右邊相鄰點對應拋物線的交點，如果交點在前一個交點左邊，則刪除前一個拋物線，并做刪除標志，刪除掉的拋物線不再參與后續計算，繼續與后面一個點的拋物線求交點，直到沒有拋物線被刪除或者后一個拋物線是被刪除的為止；第二步向左計算階段，并行計算每個點對應的拋物線和左邊相鄰點對應的沒有刪除標志的拋物線的交點，如果交點在后一個交點右邊，則刪除當前拋物線，繼續與前面一個沒有刪除標志的拋物線求交點，直到沒有拋物線被刪除為止。

2.根據權利要求1所述一種并行快速符號距離函數計算方法，其特征在于：對于寬度為W，高度為H的圖像，分配W*H個線程，每個線程負責圖像中一個點的計算；具體計算時采用了并行降維法，即將維圖像的符號距離計算變成兩個1維并行符號距離的計算。

3.根據權利要求1所述的一種并行快速符號距離函數計算方法，其特征在于：所述X方向計算步驟中，每個點并行計算時先向右計算，刪除拋物線下界以上的拋物線，再向左計算刪除拋物線下界以上的拋物線。