複数の直線から交点検出を行いたい

Question

前提・実現したいこと

javaで，複数の直線から交点を検出し，より多くの交点が検出された部分を認識させるプログラムを作成したいです．

今行っていること

現在，取り込んだ画像をCanny処理し，Hough変換をすることにより，
直線検出しました．
以下にコードを記します．

public class HoughClass {  
    static{
        System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
    }

    public static void main(String[] args) {

        Mat src = new Mat();//SourceMat
        Mat cdst= new Mat();//CannyDestinationMat
        Mat cdstP= new Mat();//CannyColorDestinationMat
        Mat gray= new Mat();//GrayMat
        Mat canny=new Mat();//CannyEdgeMat
        
        Mat lines= new Mat();//HoughlineMat
        Mat linesP= new Mat();//HoughlinePMat
                
        src = Imgcodecs.imread(path_in);//read image
        
        //Check Input-Image
        if(src.empty()) {
        	System.out.println("Error opening image!");
            System.exit(-1);
        }
        
        //ToGray
        Imgproc.cvtColor(src,gray,Imgproc.COLOR_RGB2GRAY);
        
        // Edge detection
        Imgproc.Canny(gray, canny, 10, 50);

        //Copy edges to the images that will display the results in BGR
        Imgproc.cvtColor(canny, cdst, Imgproc.COLOR_GRAY2BGR);
        cdstP= cdst.clone();
        
        // Standard Hough Line Transform
        Imgproc.HoughLines(canny, lines, 1, Math.PI/360, 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), 1, Imgproc.LINE_AA, 0);
        }
        
        // Probabilistic Line Transform
        Imgproc.HoughLinesP(canny, linesP, 1, Math.PI/360, 50, 60, 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), 1, Imgproc.LINE_AA, 0);  	
        }
    }
}

ここから行いたいこと

複数の直線が検出されましたが，交点検出には至っていません．
調べたところ，２つの直線の交点を求める記事はありましたが，
複数の直線の場合どうすればよいでしょうか？
ご教授願います．

Comments

[fana]

例えばこの画像の例の場合だと，どんな結果（どこ？）を得たいのでしょうか？

[junaa]

下の画像で赤線が３本交わっている部分を検出したいです．

[pepperleaf]

> 赤線が３本交わっている部分
交点リストを作成し、それぞれの距離を求める?
まずは、その辺から、初めては。

[junaa]

近傍の線を消すの難航しています，，，汗
うまくいけば，交点の相関関係を調べていきたいと思います，
ありがとうございます！

Answer 1

処理の目的次第でアプローチが異なりそうですが，
想像するに，画像の赤線のように線が多重に出ていると面倒なんじゃないかなぁ（処理次第で，それが「重み」としてダイレクトに影響しそうなので）と思いますので，
「あの線とこの線とは近いから，この２本の線の交点は考えないものとする」みたいな判断をする必要があるんじゃないかと思います．
（ハフ空間のrの解像度を下げる等の手段で，最初から多重に出ることをある程度抑制するような工夫もできるかもしれません）

…で，複数の線が交わる位置を見つける方法ですが，例えば……

他の方が回答されているような総当たりな方法で，ただし「互いに近い」線のペアは無視するような形で，２本の線の交点を算出した時に【その交点との距離が閾値以内であって，且つ，その交点を計算した２本の線のどちらにも「近くない」線の本数】を数えて，最もこの数が多かった交点を結果とする

ような方法が考えられるのではないかと思います．

Comments

[junaa]

なるほど，とても参考になります．
ということは，交点が密集している箇所を交点を推定するということでしょうか？

[fana]

そういう話になりますね．
前半側は「密集（≒個数）」を考える場合には，n重に出ている線をそのまま個別のn本として単純に扱うとまずいよね，という話です．

[junaa]

なるほど，ありがとうございます．
試行錯誤してみます．

Answer 2

複数の直線の場合どうすればよいでしょうか？

直線の配列で得られると思うので、全ての組み合わせで、それぞれ、交点を求めるしかないと思いますが、、、。

荒っぽく書けば、

for (int x = 0; x < lines.rows(); x++) {

を二重ループにして、

for (int x = 0; x < lines.rows(); x++) {
  for (int x1 = x; x1 < lines.rows(); x1++) {
    // ここで、x と x1の交点を求める (平行線に注意)
  }
}

みたいにして。

Comments

[junaa]

そうですね！やってみます！