摘要訊息 : 借助佇列對圖像像素進行分割.

0. 前言

在資料結構中, 線型的結構使用得比較多的是向量. 除了向量之外, 用得最多的也許就是堆疊和佇列. 今天來說一下堆疊的兩個應用.

本文在 2022 年 5 月 17 日進行一次更新和修正. 修正之後本文已經歸檔, 不再享受更新.

1. 像素分隔

大家對於像素畫應該都不陌生, 它是一個 $m$ 行 $n$ 列的像素矩陣. 在二值圖像中, 每一個像素或為黑色或為白色. 也就是說, 在 C++ 中, 我們可以使用布林型別來表示每一個像素. 0 表示黑色, 1 (255) 表示白色. 值為 1 的像素是圖像的背景, 值為 0 的像素是圖像上的一個點, 稱為圖元像素. 兩個相鄰的圖元像素屬於同一個圖元的像素. 像素分割的目的就是通過識別同一個圖元的像素, 給圖元像素做標記, 分割出若干個區域.

我們可以使用迷宮老鼠中尋找最短路徑的思想來完成. 首先一行一行地掃描圖像, 當遇到一個沒有做標記的像素的時候, 做好標記並且將其放入佇列中. 每次從佇列中取出一個像素, 再檢查是否存在與其相鄰的圖元像素, 做好相同的標記並放入佇列中. 不斷重複這個步驟直到佇列中不存在元素為止, 這樣就得到了一個區域. 然後繼續進行掃描, 找出一個新的區域, 直到整個圖像的所有區域都被找到為止. 每次找到一個區域之後, 都要對標記進行更新, 每個區域都應該有一個獨一無二的標記 :

#include <queue>

template <size_t Row, size_t Column>
void split(int (&arr)[Row][Column]) {
    using position_type = pair<int, int>;
    std::queue<position_type> q;
    auto region {2};
    for(auto row {0}; row < Row; ++row) {
        for(auto col {0}; col < Column; ++col) {
            if(arr[row][col] == 1) {
                arr[row][col] = region++;
                q.push({row, col});
                while(not q.empty()) {
                    auto pos {q.front()};
                    /* 上 */
                    --pos.first;
                    if(pos.first >= 0 and arr[pos.first][pos.second] == 1) {
                        arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
                        q.push(pos);
                    }
                    /* 下 */
                    ++++pos.first;
                    if(pos.first < Row and arr[pos.first][pos.second] == 1) {
                        arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
                        q.push(pos);
                    }
                    /* 左 */
                    --pos.first;
                    --pos.second;
                    if(pos.second >= 0 and arr[pos.first][pos.second] == 1) {
                        arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
                        q.push(pos);
                    }
                    /* 右 */
                    ++++pos.second;
                    if(pos.second < Column and arr[pos.first][pos.second] == 1) {
                        arr[pos.first][pos.second] = arr[q.front().first][q.front().second];
                        q.push(pos);
                    }
                    q.pop();
                }
            }
        }
    }
}

在 split 函式中, 我們接受一個 int 型別的二維陣列的參考. 由於使用 bool 型別的陣列會導致標記無法唯一, 因此我們改用 int 型別的陣列.

最後, 我們來分析函式 split 的複雜度. 首先分析空間複雜度, 一種比較極端的情況是圖像中所有的像素值都為 1. 因此, 佇列在某一個時刻會擁有絕大部分的像素位置. 但是由於每次處理完一個像素就會從佇列中移除, 因此其使用的空間不可能超過 $O(mn)$. 其中, $m$ 為陣列行數, $n$ 為陣列的列數. 再加上一些輔助性的變數所用的空間, 整個程式的空間複雜度為 $O(mn)$.

然後分析這個函式的時間複雜度. 我們要掃描圖像的每一個像素, 此處的時間複雜度下限為 $\Omega(mn)$. 但是對於每一幅圖像來說, 至多就掃描 $m$ 行 $n$ 列, 不可能有更多的像素, 所以時間複雜度也有上限 $O(mn)$. 處理佇列中的像素所需要的時間為 $O(mn)$, 因為佇列中不可能同時擁有全部像素. 因此, 這個函式總的時間複雜度為 $\Theta(mn)$. 其中, $m$ 為陣列行數, $n$ 為陣列的列數.