查找圖像中的不同部分

Question

假設您獲得了vector<vector<bool>>（方形區域），其中1對應於「填充」框。有沒有方法可以在O（n）時間內找到整個區域？例如，該載體將具有兩個完整區域：

0 0 1 1 1 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 
0 0 1 0 1 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 

Answer 1

這稱爲8連接region growing。這是圖像處理中的標準技術，您可以選擇種子像素並「增長」。這可以用BFS在線性時間內完成在像素數：

• 保持與邊緣隊列，把那裏的初始種子
• 從隊列中取出一個元素調用它當前點並添加到您的「區域」列表
• 推到隊列中的當前點是一個鄰居，從來沒有推到隊列中，你已經被推到了隊列
• 結束時隊列爲空的點。

區域列表包含一個區域，將其設置爲零。找到另一顆種子並再次運行，直到找不到種子。