Android OpenCV (32) : Hough line detection

This is the third day of my participation in Gwen Challenge

Hough transform uses the duality between points and lines to map the discrete pixels on straight lines in image space to curves in Hough space through parametric equations, and map the intersection points of multiple curves in Hough space as parameters of linear equations to lines in image space. Given the parametric equation of the line, hough transform can be used to detect the line in the image.

Hough line detection

Duality of points and lines

Points in image space correspond to lines in Hough space
Lines in image space correspond to points in Hough space
Lines that are co-pointed, the corresponding points in Hough space are on a line
Collinear points, corresponding lines in Hough space intersect at one point

Parametric equation of polar coordinates

For a straight line in the plane, in Cartesian coordinates, the usual slightly inclined, two point two ways. In the Hough transform, however, a different notation is considered: (r, theta) is used to represent a line. Where r is the distance of the line from the origin, and theta is the Angle between the vertical line and the X-axis of the line. As shown below:

According to hough transform principle, all lines passing through a certain point in the image space are sinusoidal when they are represented in polar coordinates. Two points on a straight line in the image space and two sinusoids mapped in the parameter space intersect at one point.

Through the transformation process, the line detection in the image is transformed into the problem of finding the maximum number of positive curves passed by a certain point in the parameter space. Since the curves in the parameter space are continuous, but the pixels in the image are discrete in practice, we need to discretize the coordinate axes of the parameter space and use the discrete squares to represent each sine curve. Firstly, the grid that meets the conditions is found, and then all the points in the image space corresponding to the grid are found, which together form the straight line in the original image.

It can be seen that hough transform algorithm is mainly divided into four steps to detect the straight lines in the image

Discretize the coordinate axes of the parameter space, e.g., theta=0,10,20… , r = 0.1, 0.2, 0.3…
Each non-zero pixel in the image is mapped to obtain the square that passes through the parameter space.
The number of occurrences of each grid in the parameter space is counted, and the grid whose frequency is greater than a certain threshold value is selected as the grid representing the straight line.
The parameters of the square representing the line in the parameter space are taken as the parameters of the line in the image.

Hoff detection has strong anti-jamming capability, the image of the damaged part of the straight line, noise and other coexistence of non linear structure is not sensitive, tolerant of characteristics of boundary description of the gap, and the advantages of less affected by image noise, but the time complexity and space complexity of hough transform is very high, and the accuracy is conditioned by discrete interval parameters. When the discrete interval is large, the detection accuracy will be reduced, while when the discrete interval is small, the accuracy will be improved, but the calculation burden will be increased, resulting in the long side of calculation time

API

public static void HoughLines(Mat image, Mat lines, double rho, double theta, int threshold, double srn, double stn, double min_theta)
Copy the code

Parameter 1: image: the original image of the line to be detected, which must be a single channel image of CV_8U.
Parameter 2: Lines, the output of lines detected by Hough transform. Each line is represented by two or three parameters. The first represents the distance of the line from the origin of the coordinates, the second represents the Angle between the vertical line of the line and the X-axis from the origin of the coordinates, and the third represents the value of the accumulator.
$((\rho, \theta)) or ((\rho, \theta, \textrm{votes}))$
Parameter 3: RHO, range resolution, in pixels, the unit length of distance discretization
Parameter 4: Theta, Angle resolution, in radians, unit Angle during the Angle discretization.
Parameter 5: threshold, the threshold of the accumulator, that is, if the cumulative number of times passed by each grid after discretization in the parameter space is greater than this threshold, it will be identified as a straight line, otherwise it will not be identified as a straight line.
Parameter 6: SRN. For the multi-scale Hough transform algorithm, this parameter represents the divisor of the range resolution. The rough accumulator range resolution is the third parameter rHO, and the accurate accumulator resolution is RHO/SRN. This parameter must be non-negative, and the default parameter is 0.
Parameter 7: STN. For the multi-scale Hough transform algorithm, this parameter represents the divisor of angular resolution. The rough accumulator range resolution is the fourth parameter, rHO, and the accurate accumulator resolution is RHO/STN. This parameter must be non-negative, and the default parameter is 0. When this argument and the sixth argument SRN are both 0, the function represents the standard Hough transform.
Parameter 8: min_theta, which detects the minimum Angle of a line. Default is 0.
Nine parameters: max_theta, Angle the detection line, the default parameters for CV_PI, is the default value of OpenCV 4 concrete is 3.1415926535897932384626433832795.

When extracting a line using standard Hough transform and multi-scale HoughLins(), the length of a line or line segment in the image cannot be accurately known, but only the existence of a line in the image and the polar coordinate analytic expression of the line can be obtained. If you need to accurately locate line segments in an image, the HoughLins() function will not suffice. However, the asymptotic probabilistic HoughLinesP() transformation function provided by OpenCV 4 can obtain the coordinates of the two endpoints of the line or segment that meet the conditions in the image, and then determine the position of the line or segment.

public static void HoughLinesP(Mat image, Mat lines, double rho, double theta, int threshold, double minLineLength, double maxLineGap) 
Copy the code

Parameter 1: image: the original image of the line to be detected, which must be a single channel image of CV_8U.
Parameter 2: lines, output line segment. Each line is represented by four elements. As follows, two endpoints of each line segment are represented
$(x_1, y_1, x_2, y_2)$
Parameter 3: RHO, range resolution, in pixels, the unit length of distance discretization
Parameter 4: Theta, Angle resolution, in radians, unit Angle during the Angle discretization.
Parameter 5: threshold, the threshold of the accumulator, that is, if the cumulative number of times passed by each grid after discretization in the parameter space is greater than this threshold, it will be identified as a straight line, otherwise it will not be identified as a straight line. The larger the cumulative number, the longer the resulting line is likely to be.
Parameter 6: minLineLength: indicates the minimum line segment length that can be detected. Set this parameter based on site requirements.
Parameter 7: maxLineGap, which represents the maximum interval pixel between line segments. Assume that 5 means that two adjacent line segments with less than 5 pixels can be connected.

operation

package cn.onlyloveyd.demo.ui

import android.os.Bundle
import androidx.appcompat.app.AppCompatActivity
import androidx.databinding.DataBindingUtil
import cn.onlyloveyd.demo.R
import cn.onlyloveyd.demo.databinding.ActivityHoughLineBinding
import cn.onlyloveyd.demo.ext.showMat
import org.opencv.android.Utils
import org.opencv.core.Mat
import org.opencv.core.Point
import org.opencv.core.Scalar
import org.opencv.imgproc.Imgproc
import kotlin.math.cos
import kotlin.math.roundToInt
import kotlin.math.sin

/** * hof * author: yidong * 2020/7/18 */
class HoughLineDetectActivity : AppCompatActivity() {

    private lateinit var mBinding: ActivityHoughLineBinding
    private lateinit var mGray: Mat
    private lateinit var mEdge: Mat
    override fun onCreate(savedInstanceState: Bundle?). {
        super.onCreate(savedInstanceState)
        mBinding = DataBindingUtil.setContentView(this, R.layout.activity_hough_line)
        mBinding.presenter = this
        mGray = Mat()
        mEdge = Mat()
        val bgr = Utils.loadResource(this, R.drawable.book)
        Imgproc.cvtColor(bgr, mGray, Imgproc.COLOR_BGR2GRAY)
        mBinding.ivLena.showMat(mGray)
        Imgproc.Canny(mGray, mEdge, 80.0.150.0.3.false)}override fun onDestroy(a) {
        mGray.release()
        mEdge.release()
        super.onDestroy()
    }

    fun doHoughLineDetect(a) {
        title = "HoughLine"
        val lines = Mat()
        Imgproc.HoughLines(mEdge, lines, 1.0, Math.PI / 180.0.150)
        val out = Mat.zeros(mGray.size(), mGray.type())
        val data = FloatArray(2)
        for (i in 0 until lines.rows()) {
            lines.get(i, 0.data)
            val rho = data[0] // The line is the distance from the origin of the coordinates
            val theta = data[1] // The Angle between the line perpendicular to the origin and the X-axis
            val a = cos(theta.toDouble())  // The cosine of the Angle
            val b = sin(theta.toDouble())  // The sine of the Angle
            val x0 = a * rho  // The point where a line intersects a perpendicular through the origin of the coordinates
            val y0 = b * rho
            val pt1 = Point()
            val pt2 = Point()
            pt1.x = (x0 + 1000 * (-b)).roundToInt().toDouble()
            pt1.y = (y0 + 1000 * (a)).roundToInt().toDouble()
            pt2.x = (x0 - 1000 * (-b)).roundToInt().toDouble()
            pt2.y = (y0 - 1000 * (a)).roundToInt().toDouble()
            Imgproc.line(out, pt1, pt2, Scalar(255.0.255.0.255.0), 2, Imgproc.LINE_AA, 0)
        }
        mBinding.ivResult.showMat(out)
        out.release()
        lines.release()
    }

    fun doHoughLinePDetect(a) {
        title = "HoughLineP"
        val lines = Mat()
        Imgproc.HoughLinesP(mEdge, lines, 1.0, Math.PI / 180.0.100.50.0.10.0)
        val out = Mat.zeros(mGray.size(), mGray.type())
        for (i in 0 until lines.rows()) {
            val data = IntArray(4)
            lines.get(i, 0.data)
            val pt1 = Point(data[0].toDouble(), data[1].toDouble())
            val pt2 = Point(data[2].toDouble(), data[3].toDouble())
            Imgproc.line(out, pt1, pt2, Scalar(255.0.255.0.255.0), 2, Imgproc.LINE_AA, 0)
        }
        mBinding.ivResult.showMat(out)
        out.release()
        lines.release()
    }
}
Copy the code

The effect

The source code

Github.com/onlyloveyd/…

Android OpenCV (32) : Hough line detection

Hough line detection

Duality of points and lines

Parametric equation of polar coordinates

API

operation

The effect

The source code

Related Posts

Android mainstream tripartite library source analysis (four, in-depth understanding of GreenDao source code)

15-ViewModel

React Native Android development environment setup in 4 steps