Este grupo redactor ha estado por horas investigando para dar solución a tus preguntas, te ofrecemos la soluciones por eso esperamos que te resulte de gran apoyo.
Solución:
No desea obtener las intersecciones de las líneas paralelas; sólo las intersecciones de las líneas verticales con las de las horizontales. Además, dado que tiene líneas verticales, el cálculo de la pendiente probablemente resultará en pendientes explosivas o inf, por lo que no debe usar el y = mx+b ecuaciones. Debes hacer dos cosas:
- Segmenta tus líneas en dos clases según su ángulo.
- Calcule las intersecciones de cada línea en una clase con las líneas en las otras clases.
Con HoughLines, ya tienes el resultado como rho, theta para que pueda segmentar fácilmente en dos clases de ángulos con theta. Puede utilizar, por ejemplo, cv2.kmeans() con theta como sus datos que desea dividir.
Luego, para calcular las intersecciones, puede usar la fórmula para calcular las intersecciones dados dos puntos de cada línea. Ya está calculando dos puntos de cada línea: (x1, y1), (x2, y2) para que pueda simplemente almacenarlos y usarlos. Editar: En realidad, como se ve a continuación en mi código, hay una fórmula que puede usar para calcular las intersecciones de líneas con el rho, theta formar eso HoughLines da.
He respondido una pregunta similar antes con un código de Python que puede consultar; tenga en cuenta que esto estaba usando HoughLinesP que le da solo segmentos de línea.
Ejemplo de código
No proporcionaste tu imagen original, así que no puedo usarla. En su lugar, usaré la imagen de sudoku estándar utilizada por OpenCV en sus tutoriales de transformación y umbral de Hough:
Primero, solo leeremos esta imagen y la binarizaremos usando umbrales adaptativos como lo que se usa en este tutorial de OpenCV:
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)
Entonces encontraremos las líneas de Hough con cv2.HoughLines():
rho, theta, thresh = 2, np.pi/180, 400
lines = cv2.HoughLines(bin_img, rho, theta, thresh)
Ahora, si queremos encontrar las intersecciones, realmente queremos encontrar las intersecciones solo de las líneas perpendiculares. No queremos las intersecciones de líneas en su mayoría paralelas. Entonces necesitamos segmentar nuestras líneas. En este ejemplo en particular, podría verificar fácilmente si la línea es horizontal o vertical basándose en una prueba simple; las líneas verticales tendrán un theta de alrededor de 0 o alrededor de 180; las líneas horizontales tendrán un theta de alrededor de 90. Sin embargo, si desea segmentarlos en función de un número arbitrario de ángulos, automáticamente, sin que defina esos ángulos, creo que la mejor idea es usar cv2.kmeans().
Hay una cosa difícil de hacer bien. HoughLines devuelve líneas en rho, theta forma (forma normal de Hesse), y la theta devuelto está entre 0 y 180 grados, y las líneas alrededor de 180 y 0 grados son similares (ambas están cerca de las líneas horizontales), por lo que necesitamos alguna forma de obtener esta periodicidad en kmeans.
Si trazamos el ángulo en el círculo unitario, pero multiplicamos el ángulo por dos, entonces los ángulos originalmente alrededor de 180 grados se acercarán a 360 grados y, por lo tanto, tendrán x, y valores en el círculo unitario cerca de los mismos para ángulos en 0. Así que podemos obtener una buena “cercanía” aquí trazando 2*angle con las coordenadas en el círculo unitario. Entonces podemos correr cv2.kmeans() en esos puntos, y segmentar automáticamente con cuantas piezas queramos.
Así que construyamos una función para hacer la segmentación:
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 zip(range(len(lines)), lines):
segmented[labels[i]].append(line)
segmented = list(segmented.values())
return segmented
Ahora para usarlo, simplemente podemos llamar:
segmented = segment_by_angle_kmeans(lines)
Lo bueno es que aquí podemos especificar un número arbitrario de grupos especificando el argumento opcional k (por defecto, k = 2 así que no lo especifiqué aquí).
Si trazamos las líneas de cada grupo con un color diferente:
Y ahora todo lo que queda es encontrar las intersecciones de cada línea en el primer grupo con la intersección de cada línea en el segundo grupo. Dado que las líneas están en la forma normal de Hesse, hay una buena fórmula de álgebra lineal para calcular la intersección de líneas a partir de esta forma. Mira aquí. Creemos dos funciones aquí; uno que encuentra la intersección de solo dos líneas, y una función que recorre todas las líneas en los grupos y usa esa función más simple para dos líneas:
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
Entonces, para usarlo, es simplemente:
intersections = segmented_intersections(segmented)
Y trazando todas las intersecciones, obtenemos:
Como se mencionó anteriormente, este código también puede segmentar líneas en más de dos grupos de ángulos. Aquí está ejecutándose en un triángulo dibujado a mano y calculando los puntos de intersección de las líneas detectadas con k=3:
Si ya tiene el segmento de línea, simplemente sustitúyalo en una ecuación de línea …
x = x1 + u * (x2-x1)
y = y1 + u * (y2-y1)
u se puede encontrar utilizando cualquiera de los siguientes …
u = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1))
u = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1))
En primer lugar, debe refinar la salida de la transformada de Hough (normalmente lo hago mediante agrupación de k-medias en función de algunos criterios, por ejemplo, pendiente y / o centroides de segmentos). En su problema, por ejemplo, parece que la pendiente de todas las líneas suele estar en las proximidades de 0, 180, 90 grados, por lo que puede agrupar sobre esta base.
A continuación, hay dos formas diferentes de obtener los puntos de intersección (que técnicamente son los mismos):
- Las ecuaciones en la respuesta de Bhupen.
- Usando una biblioteca de geometría como Shapely o SymPy. El beneficio de hacer esto con una biblioteca de geometría es que tiene acceso a una variedad de herramientas que podría necesitar más adelante en el desarrollo (intersección, interpolación, casco convexo, etc., etc.)
PS Shapely es un envoltorio de una poderosa biblioteca de geometría C ++, pero SymPy es Python puro. Es posible que desee considerar esto en caso de que su aplicación sea crítica en el tiempo.
Finalizando este artículo puedes encontrar las interpretaciones de otros usuarios, tú aún tienes la libertad de mostrar el tuyo si dominas el tema.