ハフ直線変換

目次

• 目的
• 理論
• Hough Line Transform
  • どのように動作するか?
  • 標準的および確率的ハフ直線変換
  • このプログラムは何をするか?
• コード
• Explanation
  • 画像を読み込む:
  • Cannyディテクタを使って画像のエッジを検出する:
  • 標準的ハフ直線変換:
  • 確率的ハフ直線変換
  • 元の画像と検出された直線を表示する:
  • ユーザがプログラムを終了するまで待つ
• 結果

前のチュートリアル: Cannyエッジ検出器
次のチュートリアル: ハフ円変換

原著者	Ana Huamán
互換性	OpenCV >= 3.0

目的

このチュートリアルでは、以下の方法を学ぶ:

• OpenCVの関数 HoughLines() と HoughLinesP() を使って画像中の直線を検出する。

理論

覚え書き

以下の説明は、BradskiとKaehlerによる書籍 Learning OpenCV に基づくものである。

ハフ直線変換

1. ハフ変換による直線検出は、直線を検出するために用いられる変換である。
2. この変換を適用するには、まず前処理としてエッジ検出を行うことが望ましい。

どのように動作するか?

1. As you know, a line in the image space can be expressed with two variables. For example:
   1. 直交座標系において: 引数: \((m,b)\)。
   2. 極座標系において: 引数: \((r,\theta)\)

ハフ変換では、直線を極座標系で表現する。したがって、直線の方程式は次のように書ける:

\[y = \left ( -\dfrac{\cos \theta}{\sin \theta} \right ) x + \left ( \dfrac{r}{\sin \theta} \right )\]

項を整理すると: \(r = x \cos \theta + y \sin \theta\)

1. 一般に、各点 \((x_{0}, y_{0})\) について、その点を通る直線の集合を次のように定義できる:

   \[r_{\theta} = x_{0} \cdot \cos \theta + y_{0} \cdot \sin \theta\]

   これは、各組 \((r_{\theta},\theta)\) が \((x_{0}, y_{0})\) を通る各直線を表すことを意味する。

2. ある \((x_{0}, y_{0})\) についてそこを通る直線の集合をプロットすると、正弦曲線が得られる。たとえば \(x_{0} = 8\)、\(y_{0} = 6\) の場合、次のようなプロット（\(\theta\) - \(r\) 平面上）が得られる:

ここでは \(r > 0\) かつ \(0< \theta < 2 \pi\) を満たす点のみを考える。

1. 画像中のすべての点に対して上記と同じ操作を行うことができる。2つの異なる点の曲線が \(\theta\) - \(r\) 平面上で交差する場合、その両点は同じ直線上にあることを意味する。たとえば、上記の例に続けて、さらに2つの点 \(x_{1} = 4\)、\(y_{1} = 9\) と \(x_{2} = 12\)、\(y_{2} = 3\) のプロットを描くと、次のようになる:

3つのプロットは1つの点 \((0.925, 9.6)\) で交差する。これらの座標は、\((x_{0}, y_{0})\)、\((x_{1}, y_{1})\)、\((x_{2}, y_{2})\) が乗る直線の引数（ \(\theta, r\)）である。

1. 上記のすべては何を意味するのか？ それは一般に、曲線間の交点の数を求めることによって直線を検出できることを意味する。交差する曲線が多いほど、その交点で表される直線がより多くの点を持つことを意味する。一般に、直線を検出するために必要な交点の最小数のしきい値を定義できる。
2. これがハフ変換による直線検出の動作である。画像中の各点の曲線間の交点を追跡する。交点の数があるしきい値を超えた場合、その交点の引数 \((\theta, r_{\theta})\) を持つ直線として宣言する。

標準的および確率的ハフ直線変換

OpenCVは3種類のハフ変換による直線検出を実装している:

a. 標準ハフ変換

• これは前節で説明したものとほぼ同じである。結果として組 \((\theta, r_{\theta})\) のベクトルを返す。
• OpenCVでは関数 HoughLines() で実装されている。

b. 確率的ハフ変換による直線検出

• ハフ変換による直線検出のより効率的な実装。検出された直線の端点 \((x_{0}, y_{0}, x_{1}, y_{1})\) を出力として返す。
• OpenCVでは関数 HoughLinesP() で実装されている。

c. 重み付きハフ変換

• 標準ハフ変換における2値の0または1の値の代わりに、エッジ強度を用いる。
• OpenCVでは関数 HoughLines() に use_edgeval=true を指定して実装されている。
• samples/cpp/tutorial_code/ImgTrans/HoughLines_Demo.cpp の例を参照。

このプログラムは何をするか?

• 画像を読み込む
• 標準ハフ変換 (Standard Hough Line Transform) と 確率的ハフ変換 (Probabilistic Line Transform) を適用する。
• 元画像と検出された線を3つのウィンドウに表示する。

コード

C++

解説するサンプルコードはこちらからダウンロードできる。少し凝ったバージョン(標準的ハフと確率的ハフの両方を、しきい値を変更するトラックバー付きで表示する)はこちらにある。

 
#include "opencv2/imgcodecs.hpp"
#include "opencv2/highgui.hpp"
#include "opencv2/imgproc.hpp"
 
using namespace cv;
using namespace std;
 
int main(int argc, char** argv)
{
 // Declare the output variables
 Mat dst, cdst, cdstP;
 
 const char* default_file = "sudoku.png";
 const char* filename = argc >=2 ? argv[1] : default_file;
 
 // Loads an image
 Mat src = imread( samples::findFile( filename ), IMREAD_GRAYSCALE );
 
 // Check if image is loaded fine
 if(src.empty()){
        printf(" Error opening image\n");
        printf(" Program Arguments: [image_name -- default %s] \n", default_file);
 return -1;
    }
 
 // Edge detection
    Canny(src, dst, 50, 200, 3);
 
 // Copy edges to the images that will display the results in BGR
    cvtColor(dst, cdst, COLOR_GRAY2BGR);
    cdstP = cdst.clone();
 
 // Standard Hough Line Transform
    vector<Vec2f> lines; // will hold the results of the detection
    HoughLines(dst, lines, 1, CV_PI/180, 150, 0, 0 ); // runs the actual detection
 // Draw the lines
 for( size_t i = 0; i < lines.size(); i++ )
    {
 float rho = lines[i][0], theta = lines[i][1];
 Point pt1, pt2;
 double a = cos(theta), b = sin(theta);
 double x0 = a*rho, y0 = b*rho;
        pt1.x = cvRound(x0 + 1000*(-b));
        pt1.y = cvRound(y0 + 1000*(a));
        pt2.x = cvRound(x0 - 1000*(-b));
        pt2.y = cvRound(y0 - 1000*(a));
        line( cdst, pt1, pt2, Scalar(0,0,255), 3, LINE_AA);
    }
 
 // Probabilistic Line Transform
    vector<Vec4i> linesP; // will hold the results of the detection
    HoughLinesP(dst, linesP, 1, CV_PI/180, 50, 50, 10 ); // runs the actual detection
 // Draw the lines
 for( size_t i = 0; i < linesP.size(); i++ )
    {
 Vec4i l = linesP[i];
        line( cdstP, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
    }
 
 // Show results
    imshow("Source", src);
    imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst);
    imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP);
 
 // Wait and Exit
    waitKey();
 return 0;
}

Java

解説するサンプルコードはこちらからダウンロードできる。

 
import org.opencv.core.*;
import org.opencv.core.Point;
import org.opencv.highgui.HighGui;
import org.opencv.imgcodecs.Imgcodecs;
import org.opencv.imgproc.Imgproc;
 
class HoughLinesRun {
 
 public void run(String[] args) {
 // Declare the output variables
        Mat dst = new Mat(), cdst = new Mat(), cdstP;
 
        String default_file = "../../../../data/sudoku.png";
        String filename = ((args.length > 0) ? args[0] : default_file);
 
 // Load an image
        Mat src = Imgcodecs.imread(filename, Imgcodecs.IMREAD_GRAYSCALE);
 
 // Check if image is loaded fine
 if( src.empty() ) {
            System.out.println("Error opening image!");
            System.out.println("Program Arguments: [image_name -- default "
                    + default_file +"] \n");
            System.exit(-1);
        }
 
 // Edge detection
        Imgproc.Canny(src, dst, 50, 200, 3, false);
 
 // Copy edges to the images that will display the results in BGR
        Imgproc.cvtColor(dst, cdst, Imgproc.COLOR_GRAY2BGR);
        cdstP = cdst.clone();
 
 // Standard Hough Line Transform
        Mat lines = new Mat(); // will hold the results of the detection
        Imgproc.HoughLines(dst, lines, 1, Math.PI/180, 150); // runs the actual detection
 // Draw the lines
 for (int x = 0; x < lines.rows(); x++) {
 double rho = lines.get(x, 0)[0],
                    theta = lines.get(x, 0)[1];
 
 double a = Math.cos(theta), b = Math.sin(theta);
 double x0 = a*rho, y0 = b*rho;
            Point pt1 = new Point(Math.round(x0 + 1000*(-b)), Math.round(y0 + 1000*(a)));
            Point pt2 = new Point(Math.round(x0 - 1000*(-b)), Math.round(y0 - 1000*(a)));
            Imgproc.line(cdst, pt1, pt2, new Scalar(0, 0, 255), 3, Imgproc.LINE_AA, 0);
        }
 
 // Probabilistic Line Transform
        Mat linesP = new Mat(); // will hold the results of the detection
        Imgproc.HoughLinesP(dst, linesP, 1, Math.PI/180, 50, 50, 10); // runs the actual detection
 // Draw the lines
 for (int x = 0; x < linesP.rows(); x++) {
 double[] l = linesP.get(x, 0);
            Imgproc.line(cdstP, new Point(l[0], l[1]), new Point(l[2], l[3]), new Scalar(0, 0, 255), 3, Imgproc.LINE_AA, 0);
        }
 
 // Show results
        HighGui.imshow("Source", src);
        HighGui.imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst);
        HighGui.imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP);
 
 // Wait and Exit
        HighGui.waitKey();
        System.exit(0);
    }
}
 
public class HoughLines {
 public static void main(String[] args) {
 // Load the native library.
        System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
 new HoughLinesRun().run(args);
    }
}

Python

解説するサンプルコードはこちらからダウンロードできる。

"""
@file hough_lines.py
@brief This program demonstrates line finding with the Hough transform
"""
import sys
import math
import cv2 as cv
import numpy as np
 
 
def main(argv):
 
    default_file = 'sudoku.png'
    filename = argv[0] if len(argv) > 0 else default_file
 
 # Loads an image
    src = cv.imread(cv.samples.findFile(filename), cv.IMREAD_GRAYSCALE)
 
 # Check if image is loaded fine
 if src is None:
 print ('Error opening image!')
 print ('Usage: hough_lines.py [image_name -- default ' + default_file + '] \n')
 return -1
 
 
 
    dst = cv.Canny(src, 50, 200, None, 3)
 
 
 # Copy edges to the images that will display the results in BGR
    cdst = cv.cvtColor(dst, cv.COLOR_GRAY2BGR)
    cdstP = np.copy(cdst)
 
 
    lines = cv.HoughLines(dst, 1, np.pi / 180, 150, None, 0, 0)
 
 if lines is not None:
 for i in range(0, len(lines)):
            rho = lines[i][0][0]
            theta = lines[i][0][1]
            a = math.cos(theta)
            b = math.sin(theta)
            x0 = a * rho
            y0 = b * rho
            pt1 = (int(x0 + 1000*(-b)), int(y0 + 1000*(a)))
            pt2 = (int(x0 - 1000*(-b)), int(y0 - 1000*(a)))
 
 cv.line(cdst, pt1, pt2, (0,0,255), 3, cv.LINE_AA)
 
 
 
    linesP = cv.HoughLinesP(dst, 1, np.pi / 180, 50, None, 50, 10)
 
 if linesP is not None:
 for i in range(0, len(linesP)):
            l = linesP[i][0]
 cv.line(cdstP, (l[0], l[1]), (l[2], l[3]), (0,0,255), 3, cv.LINE_AA)
 
 cv.imshow("Source", src)
 cv.imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst)
 cv.imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP)
 
 cv.waitKey()
 return 0
 
 
if __name__ == "__main__":
 main(sys.argv[1:])

解説

画像を読み込む:

C++

 const char* default_file = "sudoku.png";
 const char* filename = argc >=2 ? argv[1] : default_file;
 
 // Loads an image
 Mat src = imread( samples::findFile( filename ), IMREAD_GRAYSCALE );
 
 // Check if image is loaded fine
 if(src.empty()){
        printf(" Error opening image\n");
        printf(" Program Arguments: [image_name -- default %s] \n", default_file);
 return -1;
    }

Java

 String default_file = "../../../../data/sudoku.png";
 String filename = ((args.length > 0) ? args[0] : default_file);
 
 // Load an image
        Mat src = Imgcodecs.imread(filename, Imgcodecs.IMREAD_GRAYSCALE);
 
 // Check if image is loaded fine
 if( src.empty() ) {
            System.out.println("Error opening image!");
            System.out.println("Program Arguments: [image_name -- default "
                    + default_file +"] \n");
            System.exit(-1);
        }

Python

    default_file = 'sudoku.png'
    filename = argv[0] if len(argv) > 0 else default_file
 
 # Loads an image
    src = cv.imread(cv.samples.findFile(filename), cv.IMREAD_GRAYSCALE)
 
 # Check if image is loaded fine
 if src is None:
 print ('Error opening image!')
 print ('Usage: hough_lines.py [image_name -- default ' + default_file + '] \n')
 return -1

Cannyディテクタを使って画像のエッジを検出する:

C++

 // Edge detection
 Canny(src, dst, 50, 200, 3);

Java

 // Edge detection
        Imgproc.Canny(src, dst, 50, 200, 3, false);

Python

    dst = cv.Canny(src, 50, 200, None, 3)

ここでハフ変換を適用する。この目的で利用できる2つのOpenCV関数の使い方を説明する。

標準的ハフ直線変換:

まず、変換を適用する:

C++

 // Standard Hough Line Transform
    vector<Vec2f> lines; // will hold the results of the detection
 HoughLines(dst, lines, 1, CV_PI/180, 150, 0, 0 ); // runs the actual detection

Java

 // Standard Hough Line Transform
        Mat lines = new Mat(); // will hold the results of the detection
        Imgproc.HoughLines(dst, lines, 1, Math.PI/180, 150); // runs the actual detection

Python

    lines = cv.HoughLines(dst, 1, np.pi / 180, 150, None, 0, 0)

• with the following arguments:
  • dst: エッジディテクタの出力。グレースケール画像である必要がある（ただし実際には二値画像である）
  • lines: 検出された線の引数 \((r,\theta)\) を格納するベクトル
  • rho : 引数 \(r\) の分解能（ピクセル単位）。ここでは 1 ピクセルを使う。
  • theta: 引数 \(\theta\) の分解能（ラジアン単位）。ここでは 1 度 (CV_PI/180) を使う
  • threshold: 線を「*検出*」するための交点数の最小値
  • srn と stn: デフォルトでは0に設定される引数。詳細はOpenCVリファレンスを参照。

そして線を描画して結果を表示する。

C++

 // Draw the lines
 for( size_t i = 0; i < lines.size(); i++ )
    {
 float rho = lines[i][0], theta = lines[i][1];
 Point pt1, pt2;
 double a = cos(theta), b = sin(theta);
 double x0 = a*rho, y0 = b*rho;
        pt1.x = cvRound(x0 + 1000*(-b));
        pt1.y = cvRound(y0 + 1000*(a));
        pt2.x = cvRound(x0 - 1000*(-b));
        pt2.y = cvRound(y0 - 1000*(a));
 line( cdst, pt1, pt2, Scalar(0,0,255), 3, LINE_AA);
    }

Java

 // Draw the lines
 for (int x = 0; x < lines.rows(); x++) {
 double rho = lines.get(x, 0)[0],
                    theta = lines.get(x, 0)[1];
 
 double a = Math.cos(theta), b = Math.sin(theta);
 double x0 = a*rho, y0 = b*rho;
 Point pt1 = new Point(Math.round(x0 + 1000*(-b)), Math.round(y0 + 1000*(a)));
 Point pt2 = new Point(Math.round(x0 - 1000*(-b)), Math.round(y0 - 1000*(a)));
            Imgproc.line(cdst, pt1, pt2, new Scalar(0, 0, 255), 3, Imgproc.LINE_AA, 0);
        }

Python

 if lines is not None:
 for i in range(0, len(lines)):
            rho = lines[i][0][0]
            theta = lines[i][0][1]
            a = math.cos(theta)
            b = math.sin(theta)
            x0 = a * rho
            y0 = b * rho
            pt1 = (int(x0 + 1000*(-b)), int(y0 + 1000*(a)))
            pt2 = (int(x0 - 1000*(-b)), int(y0 - 1000*(a)))
 
 cv.line(cdst, pt1, pt2, (0,0,255), 3, cv.LINE_AA)

確率的ハフ直線変換

まず、変換を適用する:

C++

 // Probabilistic Line Transform
    vector<Vec4i> linesP; // will hold the results of the detection
 HoughLinesP(dst, linesP, 1, CV_PI/180, 50, 50, 10 ); // runs the actual detection

Java

 // Probabilistic Line Transform
        Mat linesP = new Mat(); // will hold the results of the detection
        Imgproc.HoughLinesP(dst, linesP, 1, Math.PI/180, 50, 50, 10); // runs the actual detection

Python

    linesP = cv.HoughLinesP(dst, 1, np.pi / 180, 50, None, 50, 10)

• with the arguments:
  • dst: エッジディテクタの出力。グレースケール画像である必要がある（ただし実際には二値画像である）
  • lines: 検出された線の引数 \((x_{start}, y_{start}, x_{end}, y_{end})\) を格納するベクトル
  • rho : 引数 \(r\) の分解能（ピクセル単位）。ここでは 1 ピクセルを使う。
  • theta: 引数 \(\theta\) の分解能（ラジアン単位）。ここでは 1 度 (CV_PI/180) を使う
  • threshold: 線を「*検出*」するための交点数の最小値
  • minLineLength: 1本の線を構成できる点数の最小値。この点数未満の線は無視される。
  • maxLineGap: 同一の線とみなすための2点間のギャップの最大値。

そして線を描画して結果を表示する。

C++

 // Draw the lines
 for( size_t i = 0; i < linesP.size(); i++ )
    {
 Vec4i l = linesP[i];
 line( cdstP, Point(l[0], l[1]), Point(l[2], l[3]), Scalar(0,0,255), 3, LINE_AA);
    }

Java

 // Draw the lines
 for (int x = 0; x < linesP.rows(); x++) {
 double[] l = linesP.get(x, 0);
            Imgproc.line(cdstP, new Point(l[0], l[1]), new Point(l[2], l[3]), new Scalar(0, 0, 255), 3, Imgproc.LINE_AA, 0);
        }

Python

 if linesP is not None:
 for i in range(0, len(linesP)):
            l = linesP[i][0]
 cv.line(cdstP, (l[0], l[1]), (l[2], l[3]), (0,0,255), 3, cv.LINE_AA)

元の画像と検出された直線を表示する:

C++

 // Show results
 imshow("Source", src);
 imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst);
 imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP);

Java

 // Show results
        HighGui.imshow("Source", src);
        HighGui.imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst);
        HighGui.imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP);

Python

 cv.imshow("Source", src)
 cv.imshow("Detected Lines (in red) - Standard Hough Line Transform", cdst)
 cv.imshow("Detected Lines (in red) - Probabilistic Line Transform", cdstP)

ユーザがプログラムを終了するまで待つ

C++

 // Wait and Exit
 waitKey();
 return 0;

Java

 // Wait and Exit
        HighGui.waitKey();
        System.exit(0);

Python

 cv.waitKey()
 return 0

結果

覚え書き

以下の結果は、Codeセクションで述べたもう少し凝ったバージョンを使って得られたものである。上記と同じ処理を実装しており、しきい値用のトラックバーを追加しているだけである。

数独の画像のような入力画像を使う。標準的ハフ直線変換を使うと次の結果が得られる:

確率的ハフ変換を使うと:

threshold を変更すると、検出される線の数が変化することがわかる。その理由は明白である。しきい値を高く設定すると、検出される線は少なくなる（線が検出されたと判定するためにより多くの点が必要になるため）。