La spiegazione fornita nel link (geeksforgeeks.org ) menzionato in un commento di Robert Harvey è corretto. Evita solo la terminologia utilizzata nell'elaborazione delle immagini. Tuttavia, evitare i concetti di elaborazione delle immagini può aiutare alcuni e quindi ostacolarne alcuni, perché non aiuta a rafforzare quei concetti che consentono di identificare nuove situazioni in cui è possibile applicare le stesse tecniche.
Quando una persona che ha familiarità con concetti matematici di base nell'elaborazione del segnale digitale e nell'elaborazione dell'immagine incontra una domanda come questa, la prima cosa che la persona farà mentalmente è verificare se le operazioni soddisfano certe proprietà matematiche - old aka reduction , separabilità di un kernel 2D o elemento di strutturazione in due parti 1D. Quando queste proprietà matematiche sono soddisfatte, si può dire con sicurezza che esiste una soluzione con una particolare complessità temporale.
Vedi erosione dell'immagine e dilatazione dell'immagine .
Se sai come usare OpenCV, la sua implementazione di erosione delle immagini e dilatazione offre alcune funzionalità avanzate come le versioni di "scala di grigi" di queste operazioni, che vengono implementate in termini di minimo e massimo.
Anche con l'erosione e la dilatazione delle immagini, la complessità temporale sarà O(N*N*k) , non O(N*N) , a meno che k sia corretto.
(Nota: potrebbe essere O(N*N*log(k)) a seconda dell'implementazione.) La parte log(k) si applica solo a% relativamente elevato dik nelle decine a centinaia e presuppone un tempo di accesso casuale a memoria uniforme. Funziona scomposizione di un tempo molto lungo 1D kernel [1 1 1 1 1 ... 1] in [1 1 1] , [1 0 0 1 0 0 1] , [1 0 ... 0 1 0 ... 0 1] , e così via. In questo schema, gli zeri negli elementi del kernel devono essere ignorati. Per applicare ognuno di questi kernel speciali, tre letture di memoria sono eseguito per ciascun valore di output.)
La possibilità di ridurre il fattore k*k in k è dovuta alla separabilità dell'operazione in filtro orizzontale e filtro verticale. Ad esempio, un filtro minimo che utilizza un k*k elemento di strutturazione equivale ad applicare due filtri minimi: uno di questi è k*1 e l'altro è 1*k .
Se, tuttavia, l'elemento structuring non è rettangolare, l'elemento structuring non è separabile, quindi la complessità temporale dell'operazione sarà ancora O(N*N*k*k) .
L'attività, come descritto nella domanda originale, può essere scomposta in due parti:
- Trova tutti
k*k subrectangles che non contengano valori zero.
- Per ogni
k*k subrectangles, calcola il valore massimo all'interno.
Dopo, i risultati delle due parti possono essere combinati per dare il risultato finale.
(Una possibile scorciatoia.Se tutti i valori sono noti per essere non negativi, ovvero zero è il valore minimo possibile, allora puoi riformulare la prima attività come: Per ogni sottorettangolo, calcola il valore minimo all'interno. Da questo risultato l'esistenza di un valore zero all'interno del subrectangle può essere facilmente trovata.)