Algoritmo per distribuzione puntiforme 2D distesa

Question

In un array di pixel 2D, ho bisogno di un algoritmo efficiente che selezionerà il p% di pixel che sono i più sparsi.

Questo può essere fatto in modo adattivo selezionando i punti, quindi regolando ripetutamente le posizioni dei punti che sono troppo vicini tra loro. Ma questo non è efficiente dal momento che richiederebbe molte iterazioni e calcoli a distanza.

Non deve essere perfetto, basta evitare i cluster di punti per quanto è possibile farlo in modo efficiente.

Answer 1

ne dite di questo:

1. Scopri la somma delle distanze da ogni punto di ogni altro punto. Quindi il punto A ha una distanza di somma di dist (A, B) + dist (A, C) + dist (A, D) + ...
2. Ordina queste distanze sommate.
3. Rimuovere i punti che hanno le somme di distanza più piccole fino a raggiungere la percentuale desiderata.

Questo può essere abbastanza preciso, ma in caso contrario, si può sempre sostituire il punto 3 con:

"Rimuovi il punto che ha la somma più piccola, e se è necessario rimuovere più punti per raggiungere la desiderata percentuale, quindi tornare al passaggio 1. "

Attendere. Ora mi sto chiedendo. Stai cercando di trovare i punti che sono più distanti da un dato insieme di punti ... o provando, da un determinato array, a trovare i punti che sarebbero i più sparsi? Questo è completamente diverso ... e ancora molto difficile.

Answer 2

Come calcolare un valore di "densità" per ciascun pixel all'inizio, in base alla sua vicinanza a tutti gli altri pixel. Quindi, rimuovi ripetutamente il pixel più "denso" finché non rimani sotto il p% rimanente nell'elenco.

Avresti bisogno di fare il calcolo della distanza per determinare la densità tra ogni dato due punti al massimo due volte. La prima volta sarebbe quando costruirai la lista originale - ogni pixel avrebbe bisogno di essere confrontato tra loro. Il secondo sarebbe quando rimuovete un pixel dall'elenco - dovreste calcolare quello rimosso contro ciascuno rimasto nell'elenco. Questo è per tenere conto dei valori di densità che cambiano man mano che ciascun pixel viene rimosso - ad esempio, 2 pixel direttamente uno accanto all'altro avranno un valore molto alto, ma una volta rimosso, il rimanente potrebbe avere un valore molto basso.

Un rapido pseudocodice (si noti che in questo esempio, le aree ad alta densità hanno un numero basso)

For I = 0 to MaxPixel 
    For J = I to MaxPixel 
     PixelDensity[I], PixelDensity[J] += DistanceBetween(Pixels[I], Pixels[J]) 

While PixelDensity.Count > TargetCount 
    RemovePixel = IndexOfSmallest(PixelDensity) 
    ForEach I in PixelDensity 
     PixelDensity[I] -= DistanceBetween(Pixels[I], Pixels[RemovePixel]) 
    PixelDensity.Remove(RemovePixel) 

Se la memoria è meno di una preoccupazione di tempo di calcolo, è possibile anche memorizzare la distanza tra due punti qualsiasi in un semplice array 2d. Inoltre, invece di una semplice distanza, potrebbe essere utile rendere il calcolo della distanza esponenziale - ciò eviterebbe qualcosa come avere due punti quasi uno sopra l'altro, ma molto lontano da tutto il resto, e avere entrambi passare attraverso.

Answer 3

Un approccio iterativo per lo scavo di un ruscelletto potrebbe essere semplice da visualizzare.

1. Per ogni cella, trovare i due punti più vicini e registrare il prodotto di queste due distanze.
2. Quelle celle con i prodotti più alti sono quelle collegate ai punti più lontani.

Answer 4

Si desidera una distribuzione Poisson Disk, ma è complicato. Fare una ricerca mostra molti articoli accademici su come farlo in modo efficiente: http://people.csail.mit.edu/thouis/JonesPoissonPreprint.pdf

Answer 5

Ooh! Cosa ne pensi di questo!

(In un modo molto mano-Mossi, dal momento che non so se tua matrice è quadrata o qualsiasi altra cosa ... darò per scontato che è.)

Diciamo che avete un array di 1000x1000 che si desidera mettere 47 punti in (sto selezionando 47 in modo che sia un numero insolito che non si adatta "bene").

Si prende il ceil (sqrt (47)) ... che fornirà un valore (7). Quindi creiamo un quadrato 7x7, lo riempiamo con 47 pixel (alcuni sono vuoti) e immaginiamo di posizionarlo nell'angolo dell'array.

Ora, traduci ciascuno di questi pixel in una nuova posizione, in base a dove si trovano nella piccola (7x7) matrice per l'array grande (1000x1000). Una semplice equazione dovrebbe fare questo per te ... per la coordinata X, ad esempio:

xBigArrayIndex = xSmallArrayIndex * 1000/7; 

Allora i vostri pixel sarà super sparsi! Ed è bello e veloce.

L'unico lato negativo è che funziona perfettamente solo quando il quadrato è idealmente distanziato per cominciare ... se lo riempi in modo ingenuo (iniziando in alto a sinistra, passando attraverso, ecc.) Finirai con spread leggermente inferiore all'ideale ... dato che i pixel tradotti non raggiungeranno abbastanza in basso a destra il grande array. Ma forse questo è abbastanza buono? E se no, forse è un sottoinsieme più piccolo del problema che è più facile da affrontare?

Answer 6

È possibile utilizzare l'algoritmo convesso, ed escludere punti che questo algoritmo calcola e ripeterlo finché raggiungere i vostri p criteri%, o

eseguire convesse passi algoritmo scafo, verificare la presenza di punti inclusi in scafo e all'interno di esso per soddisfare i criteri 100% - p%

alcune demo di convesso sono qui http://www.cs.unc.edu/~snoeyink/demos/

e qui hai qualche info in più http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

Answer 7

Grazie a tutti per le risposte!

La soluzione migliore sembra utilizzare "blocchi predefiniti": n x n matrici con celle già selezionate e che coprono l'array di pixel con queste.

Ad esempio, una matrice 4 x 4 con una copertura del 12,5% sarebbe: copertura

0 0 1 0 
0 0 0 0 
1 0 0 0 
0 0 0 0 

Con 6,3%:

0 0 0 0 
0 1 0 0 
0 0 0 0 
0 0 0 0 

Per ottenere una copertura% tra questi, solo alternano tra questi blocchi in base ad un conteggio corrente della copertura percentuale effettiva complessiva finora. Per coprire una larghezza che non è un multiplo di 4, usa alcuni blocchi 3 x 3. Per coprire un'area più ampia in modo più efficiente, usa solo blocchi più grandi.

Questo copre l'intero array in modo efficiente senza calcoli di distanza o aritmetica in virgola mobile.

Answer 8

La selezione "più estesa" di pixel è l'insieme la cui triangolazione Delaunay è costituita da triangoli equilateri. L'insieme di punti che conduce a questa triangolazione si ottiene dividendo l'array di pixel in un insieme di riquadri, dove ogni casella è sqrt (3) più lunga di quanto sia larga. Ogni riquadro contribuisce con 5 pixel al set finale di pixel (uno ad ogni angolo, più un nodo centrale al centro della scatola). Il trucco è scoprire quante righe e colonne di caselle ti daranno questo rapporto 1: sqrt (3). Senza passare attraverso la derivazione, ecco come si ottiene che:

std::vector<PixelIndices> PickPixels(int width, int height, float percent) 
{ 
    int total_pixels = width*height; 
    int desired_pixel_count = (int)total_pixels*percent; 

    // split the region up into "boxes" with 4 corner nodes and a center node. 
    // each box is sqrt(3) times taller than it is wide. 

    // calculate how many columns of boxes 
    float a = 1.155*height/(float)width; 
    float b = .577*height/(float)width + 1; 
    float c = 1 - desired_pixel_count; 
    int num_columns = (int)((-b + sqrt(b*b -4*a*c))/(2*a)); 

    // Now calculate how many rows 
    int num_rows = .577*height*num_columns/(float)width; 

    // total number of pixels 
    int actual_pixel_count = 2*num_rows*num_columns + num_rows + num_columns + 1; 

    std::cout << " Total pixels: " << total_pixels << std::endl; 
    std::cout << "  Percent: " << percent << std::endl; 
    std::cout << "Desired pixels: " << desired_pixel_count << std::endl; 
    std::cout << " Actual pixels: " << actual_pixel_count << std::endl; 
    std::cout << " Number Rows: " << num_rows << std::endl; 
    std::cout << "Number Columns: " << num_columns << std::endl; 

    // Pre-allocate space for the pixels 
    std::vector<PixelIndices> results; 
    results.reserve(actual_pixel_count); 

    // Now get the pixels, my integer math is probably wrong here, didn't test 
    // (didn't even finish, ran out of time) 
    for (int row = 0; row <= num_rows; row++) 
    { 
    int row_index = row*height/num_rows; 

    // Top of box 
    for (int col = 0; col <= num_columns; col++) 
    { 
     int col_index = col*width/num_columns; 
     results.push_back(PixelIndices(row_index, col_index)); 
    } 

    // Middle of box 
    if (row != num_columns) 
    { 
     for (int col = 0; col < num_columns; col++) 
     { 
     // I'll leave it to you to get this, I gotta go! 
     } 
    } 
    } 

    return results; 
} 

Invece di usare la divisione intera per trovare gli indici, si potrebbe accelerare l'operazione trovando la distanza tra ciascun punto in una riga/colonna e solo l'aggiunta da l'offset.

Answer 9

Si potrebbe provare piastrelle Wang:
http://en.wikipedia.org/wiki/Wang_tile
(Vedi le pagine non legate alla carta di Cohen, e la carta di Kopf Sono un nuovo utente in modo da non possono inserire tutti i link.).

Questi legano insieme l'idea delle tessere prefabbricate, così come il requisito uniformemente distribuito di solito risolto con i modelli di Poisson-disk. Le tessere Wang possono evitare effetti di periodicità che sono quasi sicuramente un problema con l'uso più diretto di tessere prefabbricate.

Answer 10

Abbastanza vecchio, ma merita uno scavo, perché le risposte hanno perso un metodo importante e si sono concentrate su soluzioni ottimali a cui non sei interessato. Tuttavia, il metodo che suggerisco potrebbe non essere adatto alle tue esigenze.

È possibile utilizzare quasi random sequences, progettati per tali problemi. I più diffusi sono Sobol sequences, per cui è possibile trovare pacchetti in scatola praticamente per qualsiasi lingua. Sono incredibilmente veloci: solo l'aritmetica bit a bit.

Probabilmente produrranno alcuni cluster, ma ciò può essere evitato selezionando in anticipo il "seme" da utilizzare per le dimensioni xey, e verificando ad occhio nudo.

Dipende da cosa si vuole fare con i punti: se "visual spread out" è importante, questo potrebbe non essere ciò che si desidera. Se vuoi punti che "riempiono l'aereo" quasi in modo uniforme, fanno perfettamente il lavoro. Sono particolarmente utili per fare una media di qualcosa su un'immagine velocemente, poiché richiede meno punti rispetto alla generazione casuale "normale". Sperimenta con diverse dimensioni e vedi.

Vedere anche this link per esempi di esperimenti e immagini.