Trova il picco di ciascuna isola nella matrice sparsa

Una volta ho dovuto risolvere esattamente lo stesso problema, come parte del software di elaborazione delle immagini commerciali. Alla fine ho optato per un'implementazione della linea di scansione, perché legge la matrice solo una volta.

Fondamentalmente, si considera una singola riga della matrice e si tiene traccia di tutti gli "eventi" su questa linea di scansione. Gli eventi sono bordi sinistro e destro delle isole. Si noti che la stessa isola potrebbe avere più lati sinistro e destro sulla stessa linea di scansione. Si noti inoltre che ciò che sembra essere 2 isole separate sulla linea di scansione, potrebbe rivelarsi la stessa isola in seguito.

Inoltre, tieni un registro di ogni isola conosciuta con il suo valore più alto.

Inizi con la riga superiore, inizializza gli eventi. E poi scendi una riga alla volta, rivelando ogni volta un'altra riga della matrice e aggiornando gli eventi. Accanto all'aggiornamento della posizione degli eventi esistenti, è necessario considerare anche le seguenti modifiche alla topologia:

1. Inizio (in alto) del nuovo terreno: un nuovo record dell'isola e nuovi bordi sinistro e destro sono inseriti nella linea di scansione.
2. Fine (in basso) di un pezzo di terra: un evento sinistro e destro vengono rimossi dalla linea di scansione.
3. Parte superiore di un lago / mare: un'isola che si divide in 2 penisola separate della stessa isola (2 nuovi eventi)
4. Fondo di un lago / mare: due penisole si fondono in una sola. Se non appartengono già agli stessi record dell'isola, questi due record dell'isola devono essere uniti.

Se capisco correttamente, sembrerebbe che lo stai facendo nel modo più efficiente. Fammi provare a riepilogare il tuo algoritmo:

Main:
For each pixel in image:
  If pixel is non-zero:
    Call flood subroutine with pixel.
  End
End

Flood subroutine:
Acquire all neighboring pixels of passed pixel of the same height.
Peak = true
For each pixel 
  If pixel has neighboring pixel with higher height
    Peak = false
    Call flood subroutine with pixel with higher height
  End
End
If Not Peak
  For each pixel
    Set pixel height to 0
  End
Else
  Add peak to list
End

Ciò significa che, sebbene tecnicamente si passino tutti i pixel dell'immagine per eseguire questa subroutine di flooding, se molti pixel condividono la stessa altezza, in seguito si raggiungeranno molti 0 pixel di altezza che sono stati impostati dalla subroutine .

Probabilmente potresti anche ottimizzarlo un po 'per selezionare tutti i pixel della stessa altezza e determinare se ci sono pixel vicini con altezza più alta nello stesso algoritmo per evitare di dover eseguire quel controllo in seguito.

L'unico problema con questo algoritmo è che potrebbe essere piuttosto pesante in memoria, poiché utilizza la ricorsione per mantenere i pixel con lo stesso colore. Probabilmente potresti migliorare un po 'selezionando i pixel adiacenti con altezza più alta, impostando i pixel attualmente selezionati su 0 se trovati, quindi liberando le risorse prima di chiamare la subroutine flood per ogni pixel con altezza più elevata.

Spero che questo aiuti.

Se comprendo correttamente il tuo algoritmo attuale, è:

loop through all n values in your matrix looking for non 0 ones in O(n)
for each of island, flood fill over the m non zero elements and set them to 0 in O(m)

dato che la matrice è sparsa e n > > m allora questo algoritmo sarà O (n) complessità.

Possiamo ottenere una maggiore complessità utilizzando una struttura dati che non memorizza gli 0. per esempio se hai aggiunto i tuoi dati non 0 a un dizionario con la chiave che è l'indice dei dati (i, j) allora possiamo ancora ottenere tutti i dati in O (1) e fare affidamento su una chiave non presente che significa che il valore è 0.

we can then for each non zero element we haven't looked at yet, run the flood fill 
and remove every key we look at from the dictionary in a complexity of O(m).

Ora la tua domanda non richiede una soluzione di complessità algoritmica più bassa ma una più veloce, questo nuovo algoritmo ti aiuterà?

Bene, dipende:

• Se la tua matrice è sufficientemente grande e sparsa, questo dovrebbe sovraperformare la tua attuale implementazione. Per una matrice più piccola, l'algoritmo originale potrebbe essere più veloce in quanto potrebbe avere fattori costanti più piccoli.
• Puoi persino modificare le tue strutture dati? (la risposta qui sembra essere no)

Sembra una variazione della colorazione del blob. (Google è tuo amico!)

Stai per creare un elenco di BLOB, inizialmente vuoto. Cerca un valore diverso da zero. Quando ne trovi uno, fai connettività a 4 vie per trovare i pixel blob e chiama il "colore" il valore più alto. Quando esaurisci i pixel a 4 vie, riavvia la scansione per trovare un nuovo blob.

Credo che questo sia un esempio di set di disgiunti in cui
Isola : imposta
Picco: Grande numero dell'insieme (o "Genitore dell'insieme")

Vorrei andare con "Disjoint Sets Forest" dove ogni set mantiene un puntatore al "picco" dell'isola.

link

Fai un tentativo. Buona fortuna.