Pythonで2次元行列内の0で埋められた長方形をすべて検出する方法

はじめに

本記事では、0と1のみで構成される2次元のバイナリ行列が与えられたとき、0で埋められたすべての長方形の開始座標と終了座標を見つけるアルゴリズムをPythonで実装する方法を解説します。

前提条件として、各長方形は互いに分離しており、接触しないものとします。ただし、配列（行列）の境界には接していても構いません。また、要素が1つだけの長方形も存在しえます。

問題の例

たとえば、以下のような入力行列を考えてみましょう。

この場合、出力は次のようになります。各リストは [開始行, 開始列, 終了行, 終了列] の形式で長方形の位置を表しています。

[[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

アルゴリズムの考え方

この問題は、走査済みのセルを別の値（ここでは5）でマークしながら、左上から順に長方形を拡張していくことで解けます。手順は以下の通りです。

1. 補助関数 find_rect() を定義します。引数は i, j, a, output, index です。
2. x := 行数、y := 列数 を取得します。
3. flag_col := 0、flag_row := 0 でフラグを初期化します。
4. m を i から x までループします。
   • a[m][j] が 1 なら flag_row := 1 として break します。
   • a[m][j] が 5 の場合は何もしません（既に処理済み）。
   • n を j から y までループします。
     • a[m][n] が 1 なら flag_col := 1 として break します。
     • それ以外の場合、a[m][n] := 5 として訪問済みマークを付けます。
   • flag_row が 1 なら output[index] の末尾に m-1 を追加し、そうでなければ m を追加します。
   • flag_col が 1 なら output[index] の末尾に n-1 を追加し、そうでなければ n を追加します。
5. メイン関数では以下を実行します。
   • n := 行列のサイズ
   • op := 新しい空のリスト（結果格納用）、idx := -1
   • i を 0 から n まで、j を 0 から列数まで二重ループし、a[i][j] が 0 の場合は [i, j] を op に追加し、idx をインクリメントして find_rect(i, j, a, op, idx) を呼び出します。
6. 最後に op を表示します。

実装コード

以下に実際のPython実装を示します。

def find_rect(i,j,a,output,index):
    x = len(a)
    y = len(a[0])
    flag_col = 0
    flag_row = 0
    for m in range(i,x):
        if a[m][j] == 1:
            flag_row = 1
            break
        if a[m][j] == 5:
            pass
        for n in range(j, y):
            if a[m][n] == 1:
                flag_col = 1
                break
            a[m][n] = 5
    if flag_row == 1:
        output[index].append( m-1)
    else:
        output[index].append(m)
    if flag_col == 1:
        output[index].append(n-1)
    else:
        output[index].append(n)

def get_coord(a):
    n = len(a)
    op = []
    idx = -1
    for i in range(0,n):
        for j in range(0, len(a[0])):
            if a[i][j] == 0:
                op.append([i, j])
                idx = idx + 1
                find_rect(i, j, a, op, idx)
    print (op)

tests = [[1, 0, 1, 1, 1, 0, 1],
         [1, 1, 0, 1, 1, 1, 1],
         [1, 1, 1, 0, 0, 1, 1],
         [1, 0, 1, 1, 0, 0, 1],
         [1, 0, 1, 1, 0, 1, 1],
         [1, 0, 1, 0, 0, 0, 0],
         [1, 1, 1, 0, 0, 0, 1],
         [1, 0, 1, 1, 1, 0, 1]]
get_coord(tests)

入力

[[1, 0, 1, 1, 1, 0, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1]]

出力

[[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

まとめ

このアルゴリズムは、未訪問の0セルを起点として右方向・下方向へ長方形を伸ばし、境界に達したか1にぶつかったかで終端座標を決定します。訪問済みセルを5で上書きすることで同じ長方形を二重にカウントすることを防いでおり、計算量は行列のサイズに対してほぼ線形時間 O(行数 × 列数) で動作します。画像処理やパターン認識など、領域検出が必要な場面で応用できる基本的かつ有用なテクニックです。