È una cosa su cui stavo lavorando anch'io ma che ho momentaneamente accantonato perché dovrei informarmi meglio; il codice che ho "buttato lì" fa un sampling dei punti derivanti da un sobel applicato sull'immagine (con probabilità maggiore di essere pescati per i punti più intensi), e quindi, partendo da un punto a caso, procede a cercare via via il punto più vicino.
Fa questo andando a cercare, tra i punti rimasti, il punto che minimizza la distanza euclidea con il punto correntemente in esame (sostanzialmente è un selection sort). Non credo si possa usare un algoritmo di ordinamento migliore perché sulla vicinanza tra coppie di punti sul piano (o in generale, in R^n) non si può costruire una relazione d'ordine adeguata.
codice:
// Random choice for the first point
std::swap(sobelPts[rand()%sobelPts.size()], sobelPts[0]);
// Selection sort, since we aren't in a real "strict weak ordering" situation
// (and sobelPts.size() is going to be small anyway)
for(unsigned int i=0; i<sobelPts.size()-1; i++)
{
double minDist=1./0.;
unsigned int swapIdx=i+1;
for(unsigned int j=i+1; j<sobelPts.size(); j++)
{
double dist=sobelPts[i].Distance(sobelPts[j]);
if(dist<minDist)
{
swapIdx=j;
minDist=dist;
}
}
std::swap(sobelPts[i+1], sobelPts[swapIdx]);
}
Quindi riesamina il vettore "ordinato", calcola la media delle distanze tra un punto e l'altro e, se trova un link sensibilmente più grande della media, scarta tutti i punti da lì in poi (in genere significa che da lì in poi ci sono dei punti che non c'entrano, o che, in ogni caso, il link è "sbagliato" e i dati lì non sono più affidabili).
Per ottenere risultati decenti io ripetevo questo procedimento un migliaio di volte, calcolando per ogni tentativo una "fitness" (legata a quanti punti "buoni" del sobel vengono ricalcati dai link) e tenendo alla fine il tentativo con la fitness migliore (è un po' un algoritmo di tipo RANSAC).
In ogni caso, credo che ci siano algoritmi migliori, sto studiando in questo periodo un libro di visione artificiale, se mi imbatto in qualcosa di interessante in proposito ti faccio sapere.
Rispondi quotando
