Skip to content

Trovare il punto di intersezione di due linee tracciate con houghlines opencv

Non dimenticare che nella scienza un problema di solito ha più di una soluzione, quindi ti mostreremo la soluzione più ottimale ed efficiente.

Soluzione:

Non si vogliono ottenere le intersezioni delle linee parallele, ma solo le intersezioni delle linee verticali con quelle orizzontali. Inoltre, dal momento che si hanno linee verticali, il calcolo della pendenza probabilmente risulterà in pendenze esplosive o inf, quindi non si dovrebbe usare il metodo y = mx+b . È necessario fare due cose:

  1. Segmentare le linee in due classi in base al loro angolo.
  2. Calcolare le intersezioni di ogni linea di una classe con le linee delle altre classi.

Con HoughLinessi ha già il risultato come rho, theta quindi si può facilmente segmentare in due classi di angoli con theta. Si può usare per es. cv2.kmeans() con theta come dati da dividere.

Quindi, per calcolare le intersezioni, si può utilizzare la formula per il calcolo delle intersezioni date due punti di ciascuna linea. Si stanno già calcolando due punti per ogni linea: (x1, y1), (x2, y2) quindi è sufficiente memorizzarli e utilizzarli. Modifica: In realtà, come si vede di seguito nel mio codice, c'è una formula che si può usare per calcolare le intersezioni delle linee con il valore rho, theta che HoughLines dà.

Ho già risposto a una domanda simile in passato con del codice python che potete consultare; notate che questo utilizzava HoughLinesP che fornisce solo segmenti di linea.


Esempio di codice

Non avete fornito la vostra immagine originale, quindi non posso usarla. Utilizzerò invece l'immagine standard del sudoku usata da OpenCV nei suoi tutorial sulla trasformazione di Hough e sulla soglia:

Immagine di Sudoku

Per prima cosa, leggeremo questa immagine e la binarizzeremo usando la sogliatura adattiva come quella usata in questo tutorial di 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)

Immagine sudoku binarizzata

Poi troveremo le linee di Hough con cv2.HoughLines():

rho, theta, thresh = 2, np.pi/180, 400
lines = cv2.HoughLines(bin_img, rho, theta, thresh)

Immagine di Sudoku con linee Hough

Ora, se vogliamo trovare le intersezioni, in realtà vogliamo trovare le intersezioni solo delle linee perpendicolari. Non vogliamo le intersezioni di linee per lo più parallele. Dobbiamo quindi segmentare le nostre rette. In questo particolare esempio si può facilmente verificare se la linea è orizzontale o verticale in base a un semplice test; le linee verticali avranno un valore theta di circa 0 o circa 180; le linee orizzontali avranno un valore theta di circa 90. Tuttavia, se si desidera segmentarle in base a un numero arbitrario di angoli, automaticamente, senza che sia l'utente a definirli, credo che l'idea migliore sia quella di usare cv2.kmeans().

C'è una cosa difficile da capire. HoughLines restituisce le linee in rho, theta (forma normale di Hesse) e l'opzione theta restituita è compresa tra 0 e 180 gradi, e le linee intorno a 180 e 0 gradi sono simili (sono entrambe vicine alle linee orizzontali), quindi abbiamo bisogno di un modo per ottenere questa periodicità in kmeans.

Se tracciamo l'angolo sul cerchio unitario, ma moltiplichiamo l'angolo per due, allora gli angoli originariamente intorno ai 180 gradi diventeranno vicini ai 360 gradi e quindi avranno x, y sulla circonferenza unitaria vicino agli stessi valori per gli angoli a 0. Quindi possiamo ottenere una certa "vicinanza" qui tracciando 2*angle con le coordinate sul cerchio unitario. Poi possiamo eseguire cv2.kmeans() su questi punti e segmentare automaticamente con il numero di pezzi che vogliamo.

Costruiamo quindi una funzione per eseguire la segmentazione:

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

Ora per utilizzarla, possiamo semplicemente chiamare:

segmented = segment_by_angle_kmeans(lines)

La cosa bella è che possiamo specificare un numero arbitrario di gruppi specificando l'argomento opzionale k (per impostazione predefinita, k = 2 quindi non l'ho specificato qui).

Se tracciamo le linee di ciascun gruppo con un colore diverso:

Linee segmentate

Ora non resta che trovare le intersezioni di ogni linea del primo gruppo con l'intersezione di ogni linea del secondo gruppo. Poiché le rette sono in forma normale di Hesse, esiste una bella formula di algebra lineare per calcolare l'intersezione delle rette in questa forma. Vedere qui. Creiamo due funzionie; una che trova l'intersezione di due sole rette, e una funzione che esegue un loop su tutte le rette dei gruppi e utilizza la funzione più semplice per due rette:

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

Poi per usarla, è sufficiente:

intersections = segmented_intersections(segmented)

E tracciando tutte le intersezioni, otteniamo:

Incroci


Come già detto, questo codice può anche segmentare le linee in più di due gruppi di angoli. Eccolo in esecuzione su un triangolo disegnato a mano e che calcola i punti di intersezione delle linee rilevate con k=3:

Incroci del triangolo

Se si dispone già dei segmenti di retta, è sufficiente sostituirli in un'equazione di retta...

x = x1 + u * (x2-x1)
y = y1 + u * (y2-y1)

u può essere trovato utilizzando uno dei seguenti metodi...

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))

Prima di tutto, è necessario affinare l'output della trasformata di Hough (di solito lo faccio con il clustering k-means basato su alcuni criteri, ad esempio la pendenza e/o i centroidi dei segmenti). Nel vostro problema, ad esempio, sembra che la pendenza di tutte le linee sia di solito vicina a 0, 180, 90 gradi, quindi è possibile eseguire il clustering su questa base.

Esistono poi due modi diversi per ottenere i punti di intersezione (che tecnicamente sono la stessa cosa):

  1. Le equazioni nella risposta di Bhupen.
  2. Utilizzando una libreria di geometria come Shapely o SymPy. Il vantaggio di farlo con una libreria geometrica è che si ha accesso a una serie di strumenti che potrebbero servire in seguito nello sviluppo (intersezione, interpolazione, scafo convesso, ecc. ecc.).

P.S. Shapely è un wrapper attorno a una potente libreria geometrica in C++, ma SymPy è puro Python. Si potrebbe prendere in considerazione questo aspetto nel caso in cui la propria applicazione sia critica dal punto di vista del tempo.

Ricordati di consigliare questo post se hai raggiunto il successo.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.