Come trovare i massimi locali nelle matrici?

Question

Come trovare i massimi locali nelle matrici?

#1 da (2 voti)
#2 da (1 voti)

1

Ho bisogno di sviluppare un algoritmo per trovare tutti i massimi locali in una matrice bidimensionale : come cercare i massimi locali nel modo più efficiente? Esistono algoritmi a riguardo?

Inoltre, l'algoritmo dovrebbe essere in grado di gestire anche i picchi "piatti", cioè dovrebbe trovare le coordinate centrali di ciascun picco. Ecco un esempio con un array unidimensionale: alcuni elementi consecutivi hanno lo stesso valore di picco, quindi l'algoritmo dovrebbe restituire la posizione centrale.

                       |       flat peak       |
                       |-----------------------|
array = [...  0.8  0.9  1.0  1.0  1.0  1.0  1.0  0.9  0.8  ...]
                                   |
                            desired result

Come gestire il problema dei picchi piani in un array bidimensionale? Nei picchi piatti, gli elementi vicini sono uguali tra loro e formano un unico massimo locale, quindi mi piacerebbe ottenere le coordinate centrali di questo quartiere.

language-agnostic c++ performance algorithms

posta enzom83 13.04.2013 - 12:41

fonte

2 risposte

Leggi altre domande sui tag language-agnostic c++ performance algorithms

Comprensione dei sistemi di gestione dei pacchetti Come possiamo evitare di dover costruire ancora un altro sistema CRM da zero [chiuso]

score 2 · Answer 1

Se vuoi raggruppare i vicini con valori uguali, puoi utilizzare un set disgiunto (noto anche come unione -trovare) la struttura dei dati per classificare in modo efficiente insiemi di vicini equivalenti.

Tuttavia, se i valori della matrice sono a virgola mobile (come nel tuo esempio), dovresti notare che confrontare il punto variabile i dati per l'uguaglianza esatta è quasi sempre la cosa sbagliata da fare.

Infine, trovare le "coordinate centrali" di un "picco piatto" può essere più complicato in una matrice bidimensionale che in una 1-dimensionale. Ad esempio, il centro geometrico di massa di un "picco piatto" a forma di C potrebbe non essere vicino a nessuno dei suoi membri effettivi. Ora, potrebbe essere quello che vuoi per una particolare applicazione, oppure no.

score 1 · Answer 2

Determinare se un punto è un massimo locale è semplice, basta interrogare il suo 4-vicinato (o forse il quartiere di Moore se sei preoccupato per i punti di sella). Restituisce vero se il valore è > = valore di ciascun vicino.

Il tuo commento "risultato desiderato" mette una leggera ruga su questo. È possibile scegliere di popolare una nuova matrice dst dalla matrice src. È possibile appianare i valori con sfocatura gaussiana o facendo scorrere una finestra sui dati per una media mobile. Oppure considera l'identificazione delle linee di contorno con ConRec o Marching Squares. Aggiungere un po 'di rumore potrebbe lasciarti con un problema molto più semplice.

Se vuoi veramente operare su valori non modificati, avrai bisogno di più di un passaggio. Riempi la matrice dst con zero. Riempi uno in posizioni corrispondenti ai massimi locali nella tua matrice src. Imposta colore = 2. Ora esplora l'intera matrice dst dall'alto, cercando quelli. Non appena ne trovi uno, riempilo con il colore, incrementa il colore, quindi continua la scansione. Alla fine puoi vedere tutti i massimi locali, ognuno con un colore distinto. Trova la posizione media (x, y) di tutti i valori di colore 2 e così via per ciascun colore.

Puoi farlo con un singolo bit per valore di origine. Al primo passaggio, impostare valori di dst booleano in modo che corrispondano ai massimi locali nella matrice src. Nella seconda passata, scansiona i bit impostati, riempie gli allagamenti, li cancella e calcola la media (x, y) durante il riempimento dell'inondazione.