LSD-VP消失点検出

【概要】LSD（Line Segment Detector）は画像から線分を検出するアルゴリズムである。Hough変換より計算効率が高く、パラメータ調整不要という特徴を持つ。消失点は3次元空間の平行線が2次元画像上で収束する点である。処理は以下の手順で行われる。まず、LSDで画像から線分を検出する。次に、検出された線分の延長線の交点を計算する。そして、DBSCANで近接する交点をクラスタリングし、最後に各クラスタの中心を消失点として推定する。

目次

1. 概要

LSD（Line Segment Detector）は、画像から線分を検出するアルゴリズムである。

技術名：LSD（Line Segment Detector）
出典：von Gioi, R. G., Jakubowicz, J., Morel, J. M., & Randall, G. (2012). LSD: A Line Segment Detector. Image Processing On Line, 2, 35-55. https://doi.org/10.5201/ipol.2012.gjmr-lsd

この技術は、画像の勾配情報を直接利用して線分を検出するため、Hough変換のような投票処理が不要で計算効率が高い。画像の局所的な勾配方向の一貫性を利用するため、閾値などのパラメータ調整が不要である。建築物の透視図法解析や道路認識に活用できる。

本教材では、カメラ映像から線分を検出し、DBSCANで消失点を推定する。消失点は、3次元空間で平行な線が2次元画像上で収束する点であり、カメラの視点と被写体の幾何学的関係を表す。処理は、(1)LSDで画像から線分を検出、(2)検出された線分の延長線の交点を計算、(3)DBSCANで近接する交点をクラスタリング、(4)各クラスタの中心を消失点として推定する、という4段階で行う。

DBSCANは密度ベースクラスタリング手法で、ノイズに対する耐性があり、クラスタ数を事前に指定する必要がない。消失点検出では交点の数や分布が予測困難なため、DBSCANが適している。

2. Python開発環境，ライブラリ類

ここでは、最低限の事前準備について説明する。機械学習や深層学習を行う場合は、NVIDIA CUDA、Visual Studio、Cursorなどを追加でインストールすると便利である。これらについては別ページ https://www.kkaneko.jp/cc/dev/aiassist.htmlで詳しく解説しているので、必要に応じて参照してください。

Python 3.12 のインストール

インストール済みの場合は実行不要。

管理者権限でコマンドプロンプトを起動（手順：Windowsキーまたはスタートメニュー > cmd と入力 > 右クリック > 「管理者として実行」）し、以下を実行する。管理者権限は、wingetの--scope machineオプションでシステム全体にソフトウェアをインストールするために必要である。

REM Python をシステム領域にインストール
winget install --scope machine --id Python.Python.3.12 -e --silent
REM Python のパス設定
set "PYTHON_PATH=C:\Program Files\Python312"
set "PYTHON_SCRIPTS_PATH=C:\Program Files\Python312\Scripts"
echo "%PATH%" | find /i "%PYTHON_PATH%" >nul
if errorlevel 1 setx PATH "%PATH%;%PYTHON_PATH%" /M >nul
echo "%PATH%" | find /i "%PYTHON_SCRIPTS_PATH%" >nul
if errorlevel 1 setx PATH "%PATH%;%PYTHON_SCRIPTS_PATH%" /M >nul

【関連する外部ページ】

Python の公式ページ: https://www.python.org/

AI エディタ Windsurf のインストール

Pythonプログラムの編集・実行には、AI エディタの利用を推奨する。ここでは，Windsurfのインストールを説明する。

管理者権限でコマンドプロンプトを起動（手順：Windowsキーまたはスタートメニュー > cmd と入力 > 右クリック > 「管理者として実行」）し、以下を実行して、Windsurfをシステム全体にインストールする。管理者権限は、wingetの--scope machineオプションでシステム全体にソフトウェアをインストールするために必要となる。

winget install --scope machine Codeium.Windsurf -e --silent

【関連する外部ページ】

Windsurf の公式ページ: https://windsurf.com/

必要なライブラリのインストール

コマンドプロンプトを管理者として実行（手順：Windowsキー > cmd と入力 > 右クリック > 「管理者として実行」）し、以下を実行する。


pip install opencv-python opencv-contrib-python numpy hdbscan

3. LSD-VP消失点検出プログラム

概要

このプログラムは、動画像から線分を検出し、クラスタリング手法を用いて消失点を推定する。透視図法による空間認識を模倣し、建築物や道路などの人工環境における構造を理解する。

主要技術

参考文献


# LSD-VP消失点検出プログラム
#   特徴技術名: LSD (Line Segment Detector)
#   出典: Rafael Grompone von Gioi, Jérémie Jakubowicz, Jean-Michel Morel, and Gregory Randall, "LSD: a Line Segment Detector," Image Processing On Line, 2 (2012), pp. 35–55. https://doi.org/10.5201/ipol.2012.gjmr-lsd
#   特徴機能: パラメータ調整不要での自動線分検出 - 任意のデジタル画像に対してパラメータチューニングなしで動作し、線形時間でサブピクセル精度の線分検出を実現する機能。Helmholtz原理に基づいた誤検出制御により、平均して1画像につき1つの誤検出に制限。
#   学習済みモデル: 使用していない
#   方式設計:
#     関連利用技術:
#       - HDBSCAN: 階層密度ベースクラスタリング（Campello et al., 2013）- 異なる密度のクラスタを検出可能で、線分交点から消失点を自動検出
#       - OpenCV: コンピュータビジョンライブラリ - 画像処理とカメラ入力処理
#       - NumPy: 数値計算ライブラリ - 行列演算と幾何計算
#       - hdbscan: HDBSCANクラスタリング実装パッケージ
#     入力と出力:
#       - 入力: 動画（ユーザは「0:動画ファイル，1:カメラ，2:サンプル動画」のメニューで選択．0:動画ファイルの場合はtkinterでファイル選択．1の場合はOpenCVでカメラが開く．2の場合はhttps://github.com/opencv/opencv/blob/master/samples/data/vtest.aviを使用）
#       - 出力: 処理結果が画像化できる場合にはOpenCV画面でリアルタイムに表示．OpenCV画面内に処理結果をテキストで表示．さらに，１秒間隔で，print()で処理結果を表示．プログラム終了時にprint()で表示した処理結果をresult.txtファイルに保存し，「result.txtに保存」したことをprint()で表示．プログラム開始時に，プログラムの概要，ユーザが行う必要がある操作（もしあれば）をprint()で表示．
#     処理手順:
#       1. LSDアルゴリズムによる線分検出
#       2. 線分の交点計算
#       3. HDBSCANクラスタリングによる消失点推定
#       4. 結果の可視化
#     前処理: グレースケール変換による勾配計算最適化
#     後処理: 短い線分除去による精度向上
#     追加処理: 平行線分除去（角度差閾値による判定）- 消失点推定精度向上
#     調整を必要とする設定値:
#       - HDBSCAN_MIN_CLUSTER_SIZE（最小クラスタサイズ）: 消失点検出精度を左右する重要パラメータ
#   将来方策: HDBSCAN_MIN_CLUSTER_SIZEを画像解像度と検出された線分数に基づいて動的に調整する機能の実装。具体的には、画像面積と線分数の比率から最適なクラスタサイズを自動計算する
#   その他の重要事項: 建築物や道路の透視図法解析に特化
#   前準備: pip install opencv-python opencv-contrib-python numpy hdbscan

import cv2
import numpy as np
from hdbscan import HDBSCAN
import tkinter as tk
from tkinter import filedialog
import urllib.request
import os
import time

# 定数定義
HDBSCAN_MIN_CLUSTER_SIZE = 15  # 最小クラスタサイズ
HDBSCAN_MIN_SAMPLES = 5  # 最小サンプル数
INTERSECTION_THRESHOLD = 1e-10  # 平行判定閾値
VP_RADIUS = 15  # 消失点表示半径（ピクセル）
MIN_LINE_LENGTH = 50  # 最小線分長（ピクセル）
ANGLE_THRESHOLD = 0.2  # 角度差閾値（ラジアン）
RANDOM_SEED = 42  # 乱数シード

# 表示・記録設定
LOG_INTERVAL = 1.0  # ログ出力間隔（秒）
RESULT_FILENAME = 'result.txt'  # 結果保存ファイル名

# サンプル動画URL
SAMPLE_VIDEO_URL = 'https://github.com/opencv/opencv/raw/master/samples/data/vtest.avi'
SAMPLE_VIDEO_FILENAME = 'vtest.avi'

# 乱数シード設定
np.random.seed(RANDOM_SEED)

# プログラム開始時の説明
print("=== LSD-VP消失点検出プログラム ===")
print("概要: LSD (Line Segment Detector) アルゴリズムを使用して画像から線分を検出し、")
print("      HDBSCANクラスタリングにより消失点を自動検出します。")
print("      建築物や道路などの透視図法解析に適しています。")
print("\n操作方法:")
print("- 'q'キー: プログラム終了")
print("- 検出結果は画面にリアルタイム表示されます")
print("- 1秒ごとに検出結果がコンソールに表示されます")
print("- 終了時に全結果がresult.txtに保存されます\n")

print("入力選択:")
print("0: 動画ファイル")
print("1: カメラ")
print("2: サンプル動画")

choice = input("選択: ")
temp_file = None

if choice == '0':
    root = tk.Tk()
    root.withdraw()
    path = filedialog.askopenfilename()
    if not path:
        exit()
    cap = cv2.VideoCapture(path)
elif choice == '1':
    cap = cv2.VideoCapture(0, cv2.CAP_DSHOW)
    cap.set(cv2.CAP_PROP_BUFFERSIZE, 1)
elif choice == '2':
    # サンプル動画ダウンロード
    try:
        print("サンプル動画をダウンロード中...")
        urllib.request.urlretrieve(SAMPLE_VIDEO_URL, SAMPLE_VIDEO_FILENAME)
        temp_file = SAMPLE_VIDEO_FILENAME
        cap = cv2.VideoCapture(SAMPLE_VIDEO_FILENAME)
        print("ダウンロード完了")
    except Exception as e:
        print(f"動画のダウンロードに失敗しました: {SAMPLE_VIDEO_URL}")
        print(f"エラー: {e}")
        exit()
else:
    print("無効な選択です")
    exit()

# LSD検出器の初期化
lsd = cv2.createLineSegmentDetector(0)

print("\n処理を開始します...")
print("検出結果の見方:")
print("- VP(Vanishing Point): 複数の線分が収束する点")
print("- 赤・緑・青の円で消失点を表示")
print("- 建築物では通常1-3個の消失点が検出されます\n")

# 結果記録用
results_log = []
last_print_time = time.time()
start_time = time.time()
last_result_str = ""  # 最後の結果を保持

# メイン処理
try:
    while True:
        cap.grab()
        ret, frame = cap.retrieve()
        if not ret:
            break

        # グレースケール変換と線分検出
        gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
        lines = lsd.detect(gray)[0]

        vanishing_points = []

        if lines is not None and len(lines) >= 2:
            # 短い線分を除外
            filtered_lines = []
            for line in lines:
                x1, y1, x2, y2 = line[0]
                length = np.sqrt((x2 - x1)**2 + (y2 - y1)**2)
                if length >= MIN_LINE_LENGTH:
                    filtered_lines.append(line)

            if len(filtered_lines) >= 2:
                # 線分の交点を計算
                h, w = frame.shape[:2]
                intersections = []

                for i in range(len(filtered_lines)):
                    for j in range(i + 1, len(filtered_lines)):
                        x1, y1, x2, y2 = filtered_lines[i][0]
                        x3, y3, x4, y4 = filtered_lines[j][0]

                        # 線分の方向ベクトル
                        v1 = np.array([x2 - x1, y2 - y1])
                        v2 = np.array([x4 - x3, y4 - y3])

                        # 角度差を計算（平行に近い線分を除外）
                        angle1 = np.arctan2(v1[1], v1[0])
                        angle2 = np.arctan2(v2[1], v2[0])
                        angle_diff = abs(angle1 - angle2)
                        if angle_diff > np.pi:
                            angle_diff = 2 * np.pi - angle_diff

                        if angle_diff < ANGLE_THRESHOLD:
                            continue

                        # 行列式で交点計算
                        denom = v1[0] * v2[1] - v1[1] * v2[0]
                        if abs(denom) < INTERSECTION_THRESHOLD:
                            continue

                        # 交点のパラメータ計算
                        dx = x3 - x1
                        dy = y3 - y1
                        t = (dx * v2[1] - dy * v2[0]) / denom

                        # 交点座標
                        x = x1 + t * v1[0]
                        y = y1 + t * v1[1]

                        # 画像周辺の交点を保持（延長線上の交点も含む）
                        if -w <= x <= 2*w and -h <= y <= 2*h:
                            intersections.append((x, y))

                if len(intersections) >= HDBSCAN_MIN_CLUSTER_SIZE:
                    # HDBSCANで交点をクラスタリング
                    points = np.array(intersections)
                    clustering = HDBSCAN(min_cluster_size=HDBSCAN_MIN_CLUSTER_SIZE,
                                       min_samples=HDBSCAN_MIN_SAMPLES).fit(points)

                    # 各クラスタの中心を消失点とする
                    for label in set(clustering.labels_):
                        if label == -1:  # ノイズは除外
                            continue
                        cluster_points = points[clustering.labels_ == label]
                        vp = np.mean(cluster_points, axis=0)
                        vanishing_points.append(vp)

        # 結果文字列の生成
        current_time = time.time()
        elapsed_time = current_time - start_time
        line_count = len(lines) if lines is not None else 0
        last_result_str = f"[{elapsed_time:.1f}秒] 検出された消失点数: {len(vanishing_points)}個, 線分数: {line_count}"

        if vanishing_points:
            last_result_str += " 座標:"
            for i, vp in enumerate(vanishing_points[:3]):
                last_result_str += f" VP{i+1}({vp[0]:.0f},{vp[1]:.0f})"

        # 1秒間隔での結果出力
        if current_time - last_print_time >= LOG_INTERVAL:
            print(last_result_str)
            results_log.append(last_result_str)
            last_print_time = current_time

        # 結果画像の作成
        result = frame.copy()

        # 検出された線分を描画
        if lines is not None:
            for line in lines:
                x1, y1, x2, y2 = map(int, line[0])
                cv2.line(result, (x1, y1), (x2, y2), (0, 255, 0), 1)

        # 消失点を描画（画面内外問わず表示）
        colors = [(255, 0, 0), (0, 255, 0), (0, 0, 255)]
        for i, vp in enumerate(vanishing_points):
            x, y = int(vp[0]), int(vp[1])
            # 画面内の消失点を表示
            if 0 <= x < frame.shape[1] and 0 <= y < frame.shape[0]:
                color = colors[i % len(colors)]
                cv2.circle(result, (x, y), VP_RADIUS, color, -1)
                cv2.putText(result, f'VP{i+1}', (x+20, y+5),
                           cv2.FONT_HERSHEY_SIMPLEX, 0.7, (255, 255, 255), 2)
            else:
                # 画面外の場合は画面端に矢印を表示
                cx = np.clip(x, 50, frame.shape[1]-50)
                cy = np.clip(y, 50, frame.shape[0]-50)
                color = colors[i % len(colors)]

                # 矢印の方向を計算
                dx = x - cx
                dy = y - cy
                norm = np.sqrt(dx**2 + dy**2)
                if norm > 0:
                    dx = dx / norm * 30
                    dy = dy / norm * 30
                    cv2.arrowedLine(result, (int(cx), int(cy)),
                                   (int(cx + dx), int(cy + dy)), color, 3)
                    cv2.putText(result, f'VP{i+1}', (int(cx-20), int(cy-10)),
                               cv2.FONT_HERSHEY_SIMPLEX, 0.7, color, 2)

        # 情報テキスト表示
        cv2.putText(result, f"lines: {line_count}, VPs: {len(vanishing_points)}", (10, 30),
                   cv2.FONT_HERSHEY_SIMPLEX, 0.7, (255, 255, 255), 2)

        cv2.imshow('LSD-VP Detection', result)

        if cv2.waitKey(1) & 0xFF == ord('q'):
            break

finally:
    # 最後の結果を記録（1秒間隔に満たない場合でも記録）
    if last_result_str and (not results_log or results_log[-1] != last_result_str):
        results_log.append(last_result_str)

    # 結果をファイルに保存
    if results_log:
        with open(RESULT_FILENAME, 'w', encoding='utf-8') as f:
            f.write("LSD-VP消失点検出プログラム 実行結果\n")
            f.write("=" * 50 + "\n")
            for log in results_log:
                f.write(log + "\n")
        print(f"\n{RESULT_FILENAME}に保存しました")

    # 後処理
    cap.release()
    cv2.destroyAllWindows()
    if temp_file and os.path.exists(temp_file):
        os.remove(temp_file)

    print("プログラムを終了します")

4. 使用方法

  1. プログラムを実行
  2. Webカメラを選んだ場合は，カメラを建築物、廊下、道路などに向ける
  3. 画面に緑色の線分と、赤・緑・青の円（消失点）が表示される
  4. 画面外の消失点は矢印で方向が示される
  5. 'q'キーを押すとプログラムが終了する

5. 実験・探求のアイデア

パラメータ調整による検出精度の変化

主要パラメータの役割：DBSCAN_EPSはクラスタの密度を決定し、MIN_LINE_LENGTHはノイズとなる短い線分を除外し、ANGLE_THRESHOLDは平行に近い線分の交点を除外する。

環境での消失点検出実験

アルゴリズムの比較実験

応用実験