Given Two Intersecting Lines Find Solution Calculator
You don't want to get the intersections of the parallel lines; only the intersections of the vertical lines with those of the horizontal lines. Also, since you have vertical lines, calculating the slope will likely result in exploding or inf slopes, so you shouldn't use the y = mx+b equations. You need to do two things:
- Segment your lines into two classes based on their angle.
- Calculate the intersections of each line in one class to the lines in the other classes.
With HoughLines, you already have the result as rho, theta so you can easily segment into two classes of angle with theta. You can use for e.g. cv2.kmeans() with theta as your data you want to split.
Then, to calculate the intersections, you can use the formula for calculating intersections given two points from each line. You are already calculating two points from each line: (x1, y1), (x2, y2) so you can simply just store those and use them. Edit: Actually, as seen below in my code, there's a formula you can use for calculating the intersections of lines with the rho, theta form that HoughLines gives.
I have answered a similar question before with some python code that you can check out; note this was using HoughLinesP which gives you only line segments.
Code example
You didn't provide your original image so I can't use that. Instead I'll use the standard sudoku image used by OpenCV on their Hough transform and thresholding tutorials:
First, we'll just read this image and binarize it using adaptive thresholding like what's used in this OpenCV tutorial:
import cv2 import numpy as np img = cv2.imread('sudoku.jpg') gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) blur = cv2.medianBlur(gray, 5) adapt_type = cv2.ADAPTIVE_THRESH_GAUSSIAN_C thresh_type = cv2.THRESH_BINARY_INV bin_img = cv2.adaptiveThreshold(blur, 255, adapt_type, thresh_type, 11, 2) 
Then we'll find the Hough lines with cv2.HoughLines():
rho, theta, thresh = 2, np.pi/180, 400 lines = cv2.HoughLines(bin_img, rho, theta, thresh) 
Now, if we want to find the intersections, really we want to find the intersections only of the perpendicular lines. We don't want the intersections of mostly parallel lines. So we need to segment our lines. In this particular example you could easily just check whether the line is horizontal or vertical based on a simple test; the vertical lines will have a theta of around 0 or around 180; the horizontal lines will have a theta of around 90. However, if you want to segment them based on an arbitrary number of angles, automatically, without you defining those angles, I think the best idea is to use cv2.kmeans().
There is one tricky thing to get right. HoughLines returns lines in rho, theta form (Hesse normal form), and the theta returned is between 0 and 180 degrees, and lines around 180 and 0 degrees are similar (they are both close to horizontal lines), so we need some way to get this periodicity in kmeans.
If we plot the angle on the unit circle, but multiply the angle by two, then the angles originally around 180 degrees will become close to 360 degrees and thus will have x, y values on the unit circle near the same for angles at 0. So we can get some nice "closeness" here by plotting 2*angle with the coordinates on the unit circle. Then we can run cv2.kmeans() on those points, and segment automatically with however many pieces we want.
So let's build a function to do the segmentation:
from collections import defaultdict def segment_by_angle_kmeans(lines, k=2, **kwargs): """Groups lines based on angle with k-means. Uses k-means on the coordinates of the angle on the unit circle to segment `k` angles inside `lines`. """ # Define criteria = (type, max_iter, epsilon) default_criteria_type = cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER criteria = kwargs.get('criteria', (default_criteria_type, 10, 1.0)) flags = kwargs.get('flags', cv2.KMEANS_RANDOM_CENTERS) attempts = kwargs.get('attempts', 10) # returns angles in [0, pi] in radians angles = np.array([line[0][1] for line in lines]) # multiply the angles by two and find coordinates of that angle pts = np.array([[np.cos(2*angle), np.sin(2*angle)] for angle in angles], dtype=np.float32) # run kmeans on the coords labels, centers = cv2.kmeans(pts, k, None, criteria, attempts, flags)[1:] labels = labels.reshape(-1) # transpose to row vec # segment lines based on their kmeans label segmented = defaultdict(list) for i, line in enumerate(lines): segmented[labels[i]].append(line) segmented = list(segmented.values()) return segmented Now to use it, we can simply call:
segmented = segment_by_angle_kmeans(lines) What's nice is here we can specify an arbitrary number of groups by specifying the optional argument k (by default, k = 2 so I didn't specify it here).
If we plot the lines from each group with a different color:
And now all that's left is to find the intersections of each line in the first group with the intersection of each line in the second group. Since the lines are in Hesse normal form, there's a nice linear algebra formula for calculating the intersection of lines from this form. See here. Let's create two functions here; one that finds the intersection of just two lines, and one function that loops through all the lines in the groups and uses that simpler function for two lines:
def intersection(line1, line2): """Finds the intersection of two lines given in Hesse normal form. Returns closest integer pixel locations. See https://stackoverflow.com/a/383527/5087436 """ rho1, theta1 = line1[0] rho2, theta2 = line2[0] A = np.array([ [np.cos(theta1), np.sin(theta1)], [np.cos(theta2), np.sin(theta2)] ]) b = np.array([[rho1], [rho2]]) x0, y0 = np.linalg.solve(A, b) x0, y0 = int(np.round(x0)), int(np.round(y0)) return [[x0, y0]] def segmented_intersections(lines): """Finds the intersections between groups of lines.""" intersections = [] for i, group in enumerate(lines[:-1]): for next_group in lines[i+1:]: for line1 in group: for line2 in next_group: intersections.append(intersection(line1, line2)) return intersections Then to use it, it's simply:
intersections = segmented_intersections(segmented) And plotting all the intersections, we get:
As mentioned above, this code can segment lines into more than two groups of angles as well. Here's it running on a hand drawn triangle, and calculating the intersection points of the detected lines with k=3:
Given Two Intersecting Lines Find Solution Calculator
Source: https://stackoverflow.com/questions/46565975/find-intersection-point-of-two-lines-drawn-using-houghlines-opencv