【Python】RANSACアルゴリズムによる直線検出【OpenCV】

本記事はアフィリエイト広告(PR)を含みます

RANSACアルゴリズムは、外れ値を多く含むデータからモデルに適合する点を抽出して最適なモデルを推定する手法です。
画像処理では直線や楕円検出に用いられます。

例えば左のような画像から直線検出したい場合、そのまま直線を当てはめると外れ値に引っ張られて右の画像のようになってしまいます。

これに対してRANSACアルゴリズムを使うとこのように同じ直線上に分布する点が最も多い位置に直線を当てはめることができます。

今回はRANSACアルゴリズムを使って直線検出を行う手順について解説します。

1. RANSACアルゴリズムの流れ
2. RANSACによる直線検出をPythonで実装
3. 動作確認
4. まとめ
5. 参考サイト
6. 関連書籍

1. RANSACアルゴリズムの流れ

RANSACアルゴリズムは以下のような流れで行います。
ここではシンプルに7点の中から外れ値を除外して直線を描いてみます。

1.1. ランダムに点を選択

まず、7点の中から重複しない2点をランダムに選択します。直線は最低2点から求められるため、直線検出では2点を選びます。

1.2. 選択した点から仮のモデルを求める

今回は直線検出なので、選択した2点を通る直線を求め、この直線を仮のモデルとします。
直線は次の一般式で表せます。

ax + by + c = 0

1.3. 残りの点と仮のモデルとの距離を求める

選択しなかった各点について、仮の直線までの垂直距離を計算します。
垂直距離は次の式で表せます。

d = \frac{|ax_0 + by_0 + c|}{\sqrt{a^2 + b^2}}

1.4. 距離が閾値以内(インライア)なら記録

仮の直線までの距離があらかじめ設定した閾値以内の点をインライアとして記録します。
閾値を超えた点はアウトライアとして扱います。

1.5. 最もインライア数が多いモデルを採用

1.1～1.4をランダムに選ぶ点を変えながら指定回数繰り返します。
その中で最もインライア数の多かったモデルを採用します。

2. RANSACによる直線検出をPythonで実装

冒頭で示した画像を例にRANSACを使って実際に直線検出してみましょう。
今回はRANSACの処理内容を確認するため、ライブラリのRANSAC機能は使用せず、2点のランダム選択やインライア判定を実装します。

2.1. テスト用画像を作成

まずはテスト用の画像を作成します。

基準となる直線を $y=x$ とし、その周辺にインライア、離れた位置にアウトライアを生成します。

for _ in range(NUM_POINTS):
    # y=x上の基準点
    x = np.random.randint(0, WIDTH)
    y = x

    if np.random.rand() < INLIER_RATIO:
        # 70%：y=xから上下20px以内
        offset = np.random.randint(
            -THRESHOLD,
            THRESHOLD + 1
        )
    else:
        # 30%：下側へ150～400pxずらす
        offset = np.random.randint(
            150,
            401
        )

点群の生成時に70%の確率で、直線 $y=x$ から上下20ピクセル以内に配置します。
これらがRANSACで検出したいインライアです。
残りの30%は、基準となる直線から大きく離れた位置に配置し、アウトライアとします。

2.2. ランダムに2点を選択

直線は2点から求められるため、点群の中から重複しない2点をランダムに選択します。

indices = np.random.choice(
    num_points,
    2,
    replace=False
)

2.3. 2点を通る仮の直線を求める

1.2で示した直線の一般式

ax+by+c=0

の各係数は、2点を $(x_1,y_1)$ 、 $(x_2,y_2)$ とすると次のようになります。

\begin{gathered} a=y_1-y_2 \\ b=x_2 – x_1 \\ c=x_1y_2-x_2y_1 \end{gathered}

a = y1 - y2
b = x2 - x1
c = x1 * y2 - x2 * y1

2.4. 全点と仮の直線との距離を計算

点 $(x_0,y_0)$ と直線との距離は次の式で求めます。

d= \frac{|ax_0+by_0+c|} {\sqrt{a^2+b^2}}

NumPyを使って、すべての点との距離をまとめて計算しています。

distances = np.abs(
    a * points[:, 0]
    + b * points[:, 1]
    + c
) / np.sqrt(a * a + b * b)

2.5. インライアを判定

仮の直線との距離が20ピクセル以内の点を、インライアとして判定します。
inlier_maskには各点がインライアかどうかを示す真偽値が格納されます。

inlier_mask = distances <= distance_threshold
inlier_count = np.count_nonzero(inlier_mask)

例えば次のような配列になります。

[True, True, False, True, False]

2.6. 最もインライア数が多いモデルを保存

ランダムに作成した仮モデルの中で、最もインライア数が多い直線を保存します。
この処理を1000回繰り返し、最も多くの点から支持された直線を採用します。

if inlier_count > best_inlier_count:
    best_inlier_count = inlier_count
    best_line = line
    best_inlier_mask = inlier_mask

ここまでが前半で説明したRANSACの処理に対応します。

2.7. インライア全体から最終的な直線を求める

RANSACで作成した直線は、ランダムに選ばれた2点だけを通る直線です。
そのため、検出したインライア全体をcv2.fitLine()に渡し、最終的な直線を再計算します。

vx, vy, x0, y0 = cv2.fitLine(
    fit_points,
    cv2.DIST_L2,
    0,
    0.01,
    0.01
)

2.8. コード全体

import cv2
import numpy as np

# 画像サイズ
WIDTH = 1000
HEIGHT = 1000

# 点の生成回数
NUM_POINTS = 300

# 点群生成時のインライア率
INLIER_RATIO = 0.7

# 点群生成時のずれ
THRESHOLD = 20

# RANSACの設定
RANSAC_ITERATIONS = 1000
RANSAC_DISTANCE_THRESHOLD = 20

# 生成した点を保存
points = []

np.random.seed(42)

# 黒画像
img = np.zeros((HEIGHT, WIDTH, 3), dtype=np.uint8)

# ----------------------------------
# 点群を生成
# ----------------------------------
for _ in range(NUM_POINTS):

    # y=x上の基準点
    x = np.random.randint(0, WIDTH)
    y = x

    if np.random.rand() < INLIER_RATIO:
        # 70%：y=xから上下20px以内
        offset = np.random.randint(
            -THRESHOLD,
            THRESHOLD + 1
        )
    else:
        # 30%：下側へ150～400pxずらす
        offset = np.random.randint(
            150,
            401
        )

    y += offset

    # 画像内に入った点だけ採用
    if 0 <= x < WIDTH and 0 <= y < HEIGHT:
        points.append([x, y])

# NumPy配列に変換
points = np.array(points, dtype=np.float64)

# ----------------------------------
# RANSACによる直線検出
# ----------------------------------
def ransac_line(
    points,
    iterations=1000,
    distance_threshold=20
):
    best_line = None
    best_inlier_mask = None
    best_inlier_count = 0

    num_points = len(points)

    if num_points < 2:
        raise ValueError("直線検出には2点以上必要です。")

    if iterations <= 0:
        raise ValueError("iterationsは1以上にしてください。")

    if distance_threshold < 0:
        raise ValueError(
            "distance_thresholdは0以上にしてください。"
        )

    for _ in range(iterations):

        indices = np.random.choice(
            num_points,
            2,
            replace=False
        )

        p1 = points[indices[0]]
        p2 = points[indices[1]]

        if np.linalg.norm(p2 - p1) < 1e-8:
            continue

        x1, y1 = p1
        x2, y2 = p2

        a = y1 - y2
        b = x2 - x1
        c = x1 * y2 - x2 * y1

        line = np.array(
            [a, b, c],
            dtype=np.float64
        )

        distances = np.abs(
            a * points[:, 0]
            + b * points[:, 1]
            + c
        ) / np.sqrt(a * a + b * b)

        inlier_mask = (
            distances <= distance_threshold
        )

        inlier_count = np.count_nonzero(
            inlier_mask
        )

        if inlier_count > best_inlier_count:
            best_inlier_count = inlier_count
            best_line = line
            best_inlier_mask = inlier_mask

    if best_line is None:
        raise RuntimeError(
            "直線モデルを検出できませんでした。"
        )

    return best_line, best_inlier_mask


best_line, inlier_mask = ransac_line(
    points,
    iterations=RANSAC_ITERATIONS,
    distance_threshold=RANSAC_DISTANCE_THRESHOLD
)

inlier_points = points[inlier_mask]
outlier_points = points[~inlier_mask]

print(f"全点数: {len(points)}")
print(f"インライア数: {len(inlier_points)}")
print(f"アウトライア数: {len(outlier_points)}")

# ----------------------------------
# インライア全体で直線を再計算
# ----------------------------------
# RANSACで選ばれた2点だけの直線ではなく、
# インライア全体を使って最終的な直線を求める。
fit_points = inlier_points.astype(
    np.float32
).reshape(-1, 1, 2)

vx, vy, x0, y0 = cv2.fitLine(
    fit_points,
    cv2.DIST_L2,
    0,
    0.01,
    0.01
)

vx = float(vx[0])
vy = float(vy[0])
x0 = float(x0[0])
y0 = float(y0[0])

# y = slope * x + intercept に変換
if abs(vx) < 1e-8:
    raise ValueError("垂直な直線が検出されました。")

slope = vy / vx
intercept = y0 - slope * x0

print(
    f"検出された直線: "
    f"y = {slope:.4f}x + {intercept:.4f}"
)

# ----------------------------------
# 点群を描画
# ----------------------------------

# アウトライア：赤
for x, y in outlier_points:
    cv2.circle(
        img,
        (int(round(x)), int(round(y))),
        3,
        (0, 0, 255),
        -1,
        cv2.LINE_AA
    )

# インライア：黄色
for x, y in inlier_points:
    cv2.circle(
        img,
        (int(round(x)), int(round(y))),
        3,
        (0, 255, 255),
        -1,
        cv2.LINE_AA
    )

# ----------------------------------
# 検出した直線を描画
# ----------------------------------
x1 = 0
y1 = int(round(slope * x1 + intercept))

x2 = WIDTH - 1
y2 = int(round(slope * x2 + intercept))

# 画像範囲内で直線を切り取る
success, pt1, pt2 = cv2.clipLine(
    (0, 0, WIDTH, HEIGHT),
    (x1, y1),
    (x2, y2)
)

if success:
    cv2.line(
        img,
        pt1,
        pt2,
        (255, 255, 0),
        2,
        cv2.LINE_AA
    )

# ----------------------------------
# 表示・保存
# ----------------------------------
cv2.imshow("RANSAC Line Detection", img)
cv2.imwrite("ransac_result.png", img)

cv2.waitKey(0)
cv2.destroyAllWindows()