Riconoscere una matrice in un gruppo di punti

Ho un'immagine che elaborerò con il mio programma per ottenere un elenco di coordinate.Riconoscere una matrice in un gruppo di punti

Rappresentata nell'immagine c'è una matrice. In un test ideale otterrei solo i sedici punti centrali di ogni quadrato della matrice. Ma nei test reali prendo più punti di rumore.

Desidero utilizzare un algoritmo per estrapolare dall'elenco delle coordinate, il gruppo formato da 16 coordinate che rappresentano al meglio una matrice.

La matrice può avere qualsiasi rapporto di aspetto (compreso tra un intervallo) e può risultare leggermente ruotato. Ma è sempre una matrice 4x4. La matrice non è sempre presente nell'immagine, ma non è un problema, ho bisogno solo della migliore corrispondenza. Naturalmente il punto fondato sono sempre più di 16 (o i saltare)

Esempio di punti fondate:

enter image description here

Esempi di risultati desiderata:

enter image description here

Se qualcuno mi può suggerire un modo preferito per farlo sarebbe grandioso.

Sto pensando alla distanza euclidea tra i punti.

For each point in the list: 
    1. calculate the euclidean distance (D) with the others 
    2. filter that points that D * 3 > image.widht (or height) 
    3. see if it have at least 2 point at the same (more or less) distance, 
     if not skip 
    4. if yes put the point in a list and for each same-distance founded points: go to 2nd step.

alla fine se ho 16 punti nell'elenco, questa potrebbe essere una matrice.

Qualche suggerimento migliore?

Grazie

fonte

2013-05-24 Univers3

Vuoi una forma con un reticolo periodico? Peridocity su X-line o linea Y o entrambi? Che dire della simetricità angolare? Vuoi forme di diamanti anche tu? –

Una forma di diamante non è mai rappresentata. Penso che la rotazione massima (a partire da un quadrato perfetto) possa essere di 45 ° (e -45 °). Sì, la forma ha un reticolo periodico (X e Y) ma quando estrapolo i punti dall'immagine, i punti estrapolati differiscono leggermente. – Univers3

Un quadrato ruotato di 45 ° non sarebbe un diamante? – mbeckish

Questo è l'algoritmo che viene in mente:

for each pair of points (p1, p2): 
    let d be the distance vector (x and y) between them 
    if d.x > (image.width-p1.x)/3 or d.y > (image.height-p1.y)/3: 
     continue 
    let d_t be d turned 90 degrees (d.y, -d.x) 
    for i from 0 to 3: 
     for j from 0 to 3: 
      if there is no point at p1 + i*d + j*d_t: 
       continue outer loop 
    if you get here, you have a 4*4 grid

Per tagliare il tempo di esecuzione a metà (in media), si può solo prendere in considerazione le P2 di che sono alla destra di p1.

fonte

2013-05-24 15:05:49

Con una piccola soglia percentuale sulla distanza iniziale, l'algoritmo può essere tollerante all'errore nel trovare i punti della matrice, modificando l'IF con: 'se la distanza del punto più vicino a p1 + i * d + j * d_t differiscono più del 4% con d' – Univers3

Sì, se i dati sono rumorosi o a valori fluttuanti farlo. Anche il mio algo assume che la matrice sarà quadrata, quindi sii consapevole di ciò. –

seconda della quantità di potenza di elaborazione che si desidera utilizzare, e assumendo un "po 'di rotazione" significa molto poco, si potrebbe provare la seguente: 1) prendendo solo le coordinate X dei punti, cercare gruppi di dimensioni 4.

2) Per ciascun gruppo, cercare di vedere per ogni gruppo a sinistra con distanza d, se ce ne sono altri due con distanze 2 * d e 3 * d.

3) Se sì, confrontare le coordinate y per ciascuno di questi cluster per vedere se sono approssimativamente uguali.

A seconda dei dati, è possibile ottenere prestazioni migliori eseguendo il passaggio tre prima del passaggio 2 e utilizzandolo per ridurre le opzioni considerate.

fonte

2013-05-24 14:47:45

Riconoscere una matrice in un gruppo di punti

risposta

Problemi correlati