【Python】Canny法実装：whileループからの脱却と高速化の美学

はじめに

画像処理エンジニアや研究者にとって、Canny法(Canny Edge Detector)は避けては通れないアルゴリズムです。
OpenCVのcv.Canny()を呼べば、一瞬で終わる処理ですが、これをスクラッチで実装しようとした瞬間、Python特有の壁にぶつかります。

それは、処理時間です。

特にアルゴリズム後半、エッジを繋ぐ処理で、whileループや再帰関数を使ってしまい、高解像度の画像だと数秒 - 数十秒待たされることもざらにあります。
本記事では、Canny法を題材に、いかにしてPythonのwhileループを排除し、行列計算に落とし込むかというテクニックを解説します。

1. Canny法の「ボトルネック」はどこか？

Canny法は主に以下の4ステップで構成されます。

1. ガウシアンフィルタ(ノイズ除去)
2. Sobelフィルタ(勾配今日かと方向の算出)
3. 非極大値抑制(エッジを細くする)
4. ヒステリシス閾値処理(エッジを繋ぐ)

ステップ1と2は単純な畳み込み演算なので、NumaPyやOpenCVのフィルタ関数で高速に処理できます。問題は、画素ごとの条件分岐が必要に見えるステップ3と、近傍探索が必要なステップ(ヒステリシス)です。

今回は、最も「ループしたくなる」ヒステリシス閾値処理に焦点を当ててループからの脱却を図ります。

2. 従来の実装(Trap)

ヒステリシス閾値処理のロジックは以下の通りです。

• Strong Edge (強エッジ)：閾値(high) 以上の画素。確定でエッジ。
• Weak Edge (微エッジ)：閾値(low ~ high)の画素。強エッジと繋がっている場合のみ、エッジとして残す。

これをナイーブに実装すると、次のコードになりがちです。

遅い実装例

def hysteresis_slow(img, weak, strong):
    h, w = img.shape
    changed = True
    while changed:  
        changed = False
        for i in range(1, h-1):
            for j in range(1, w-1):
                if img[i, j] == weak:
                    # 8近傍にstrongがあるかチェック
                    if check_neighbors(img, i, j) == strong:
                        img[i, j] = strong
                        changed = True
    return img

Pythonのforループの中で、さらにwhileで収束を持つ。これは画像サイズが大きくなると致命的です。計算量は最悪の場合$O(N^2)$に近づき、実行時間は指数関数的に伸びてしまいます。

3.whileループからの脱却(Solution)

この問題を解決するための鍵は「連結成分(Connected Components)」という考え方です。

「弱エッジが強エッジと繋がっていれば採用」という条件は、「強エッジを含む連結成分(かたまり)に属している弱エッジは全て採用」ということになります。

これを実装するためには、ループではなくscipy.ndimage.label(ラベリング処理)を使います。

高速化のアプローチ

1. 勾配画像全体から、閾値処理でstrong_maskとweak_maskを作る。(ここは単なるBool判定)
2. 全ての候補が(Strong + Weak)を一つのバイナリ画像とみなす。
3. そのバイナリ画像に対してラベリング(連結成分分解)を行う。
4. 各ラベル(かたまり)の中に、一つでもstrong ピクセルが含まれているかを判定する。
5. 含まれているラベルの領域だけを残す。

最適化された実装コード

import numpy as np
from scipy.ndimage import label

def hysteresis_vectorized(img, low_threshold, high_threshold):

    h, w = img.shape
    
    # 1. マスクの作成 (Vectorized operation)
    strong_mask = img >= high_threshold
    weak_mask = (img >= low_threshold) & (img < high_threshold)
    
    all_edges = strong_mask | weak_mask
    
    # 2. ラベリング (連結成分の抽出)
    structure = np.ones((3, 3), dtype=int) 
    labels, num_labels = label(all_edges, structure=structure)
    
    # 3. 各ラベル内にStrong Edgeが存在するかチェック
    # ここが肝。Strong Edgeがある場所のラベル番号を取得する
    labels_with_strong = np.unique(labels[strong_mask])
        
    # 4. 有効なラベルを持つピクセルのみを抽出 (Vectorized lookup)
    # np.isin を使うと、「ラベル画像の値がリストに含まれているか」を一発で判定できる
    final_edges = np.isin(labels, labels_with_strong)
    
    return (final_edges.astype(np.uint8) * 255)
    

4. なぜこれで早くなるのか?

計算量の変化

• While ループ版: 変化が伝播するたびに画像全体をスキャンするため。エッジが長い蛇のように伸びている場合、スキャン回数が画像の幅/高さに比例して増えます。
• 連結成分版: ラベリングアルゴリズム(Union - Find等)は、画像のピクセル数に対してほぼ線形($O(N)$)で動作します。

「伝播」を「集合」として捉える
ループを書いている時、私たちは「ピクセルAからBへ移動する」という手続きを考えています。
一方ベクトル化する時は「条件を満たす集合Xと集合Yの交差をとる」という宣言(Declaration)の思考になります。

Pythonで高速化を目指す際には、この手続き型から集合型への思考の転換こそが最大の武器になります。

5. 発展編：非極大値抑制もベクトル化する

記事のメインはヒステリシスでしたが、その前段階である非極大値抑制値も実はforループを使わずに書けます。

画素(x,y)の勾配角度に応じて、比較すべき隣接画素が決まります。これをループ判例するのではなく、画像をずらしたコピーを作って比較します。

例：勾配方向が0度（左右）のピクセルを一括処理するアイデア
左に1つずらした画像と、右に1つずらした画像を用意し、まとめて比較演算を行います。

非極大値抑制のベクトル化

Z = gradient_magnitude
mask_0 = (angle_quantized == 0)

# Z[i, j] >= Z[i, j-1] and Z[i, j] >= Z[i, j+1] を行列で一括判定
nms_result[mask_0] = (Z[mask_0] >= Z_shifted_left[mask_0]) & \
                     (Z[mask_0] >= Z_shifted_right[mask_0])

このように、「近傍画像へのアクセス」を「行列のシフト」に置き換えることで、Pythonのループを完全に排除できます。

まとめ

• Canny法のボトルネック: ヒステリシス処理のwhileループや再帰
• 解決策: 「伝播」処理を「連結成分分析」に置き換える
• ツール: scipy.nidimage.labelやnp.isinを活用する

アルゴリズムの実装において、「定義通りにループで書く」ことから、「行列計算や集合演算に落とし込む」ことへステップアップできた時、Pythonはその真の速度(C言語ライブラリの速度)を発揮します。

ぜひあなたの画像処理パイプラインから、whileループを一掃してみてください!!