Come eseguire lo "spostamento delle immagini" più velocemente?

Question

Come eseguire lo "spostamento delle immagini" più velocemente?

#1 da (2 voti)
#2 da (1 voti)
#3 da (0 voti)

0

Ho una matrice in scala di grigi (implementata come semplice array) da mostrare su un display:

line 1: | a | b | c |
line 2: | d | e | f |

a-f sono valori in scala di grigi. Questo modello deve essere spostato di una percentuale variabile a sinistra o a destra.

Quello che faccio attualmente è un approccio semplice:

Ad esempio, sposta il 20% verso sinistra, quindi:

a_new = a * (1 - 0.2) + b * 0.2
b_new = b * (1 - 0.2) + c * 0.2
c_new = c * (1 - 0.2) + 0

e così via. Cioè, ho un ciclo su tutti gli elementi.

Con solo sei elementi non mi interessa, ma in effetti la matrice è molto più grande.

Ovviamente, il fattore (1 - 0.2) può essere riutilizzato, ma mi chiedo se c'è un modo più intelligente di calcolare la matrice risultante (spostata)?

array algorithms

posta mic 09.10.2014 - 10:02

fonte

3 risposte

Leggi altre domande sui tag array algorithms

Quando dovresti creare / distruggere l'oggetto sottostante in una classe che lo avvolge Come posso testare la mia app Android dipendente dalla fotocamera sulla maggior parte dei dispositivi? [duplicare]

score 2 · Answer 1

Se è possibile accedere alla matrice come array 2D (x, y), il problema si generalizza a

new(x, y) = old(x, y) * (1 - 0.2) + old(x + 1, y) * 0.2

per tutti tranne l'ultima colonna. L'ultima colonna è un caso speciale. O usare

new(x, y) = old(x, y) * (1 - 0.2)

solo per quella colonna, oppure tampona il tuo array sorgente con una colonna in più di zero prima e poi non devi più trattare l'ultima colonna come caso speciale.

Questo può essere facilmente implementato usando due loop nidificati. Alcuni linguaggi specializzati (come Matlab) sarebbero in grado di eseguire tutto in un colpo, senza espliciti cicli di loop.

score 1 · Answer 2

Sai dove viene speso il maggior tempo? Ci potrebbero essere tutti i modi per accelerare questo. Non c'è abbastanza codice da sapere con certezza, a meno che tu non stia specificatamente chiedendo solo la matematica.

I computer sono estremamente bravi in matematica, quindi il problema è probabilmente altrove rispetto al calcolo effettivo dei dati. Ad esempio, in un toolkit so se, cambiando ogni pixel in un'immagine uno alla volta, gli ordini di grandezza sono più lenti del calcolare un'intera riga o l'intera immagine in memoria prima di salvare i dati nell'oggetto dell'immagine.

score 0 · Answer 3

L'approccio di base sarebbe; per ogni riga:

Carica l'intera riga in "registro SIMD 1" (MMX, SSE, AVX, Neon, qualsiasi cosa)
Copia in "registro SIMD 2"
Moltiplica "SIMD register 2" per 0.2 (peccato che non sia il 25% ...)
Sottrai "registro SIMD 2" da "registro SIMD 1"
Shift "SIMD register 2" a destra di 1 elemento
Aggiungi "Registro SIMD 2" a "Registro SIMD 1"
Memorizza "registro SIMD 1" nella destinazione

L'approccio di base è "base". In pratica, probabilmente dovrai gestire il caso in cui l'intera riga non rientra in un registro SIMD. Ciò significa principalmente che lo "spostamento a destra" dovrà coinvolgere la memorizzazione dell'elemento più basso (che sarebbe stato spostato all'esterno) e lo spostamento durante il turno successivo come nuovo elemento più alto.

In ogni caso, non dovrebbe essere così difficile finire limitato dalla larghezza di banda della RAM per array / matrici di grandi dimensioni (supponendo che tu stia facendo anche pre-fetch ragionevole e, eventualmente, archivi non temporali).