Come posso migliorare la perfomace della scansione di immagine di Hilbert?

Question

Questo metodo di scansione delle immagini basato su Hilbert Curve. Assomiglia a Curve (da 1 a 6):

Può essere utilizzato per la scansione di immagini. Quindi, ad esempio, il mio codice per la curva a 3 ordini è:

Hilbert=[C(1,1) C(1,2) C(2,2) C(2,1) C(3,1) C(4,1) C(4,2) C(3,2) C(3,3) C(4,3) C(4,4) C(3,4)... 
     C(2,4) C(2,3) C(1,3) C(1,4) C(1,5) C(2,5) C(2,6) C(1,6) C(1,7) C(1,8) C(2,8) C(2,7)... 
     C(3,7) C(3,8) C(4,8) C(4,7) C(4,6) C(3,6) C(3,5) C(4,5) C(5,5) C(6,5) C(6,6) C(5,6)... 
     C(5,7) C(5,8) C(6,8) C(6,7) C(7,7) C(7,8) C(8,8) C(8,7) C(8,6) C(7,6) C(7,5) C(8,5)... 
     C(8,4) C(8,3) C(7,3) C(7,4) C(6,4) C(5,4) C(5,3) C(6,3) C(6,2) C(5,2) C(5,1) C(6,1)... 
     C(7,1) C(7,2) C(8,2) C(8,1)]; 

E funziona e funziona velocemente. Ho fatto le stesse funzioni per curve a 8 e 9 ordini, ma funziona molto molto lentamente. 9 ordini, forse, non finiranno mai. Almeno, non ho avuto la pazienza di aspettare la fine - dopo 2 ore ho appena spento il programma. Ma la curva di 7 ordini funziona per 15 secondi. Che cosa c'é? Posso fare lo stesso, ma più velocemente? Sì, il programma deve leggere gli elementi dell'array 512 * 512, ma non può essere impossibile renderlo più veloce.

Quindi, di cosa ho esattamente bisogno: ho le coordinate degli elementi dell'array e sono disposti nell'ordine in cui dovrebbero essere letti. Ho bisogno di un tempo accettabile per leggerli e scrivere nel nuovo array. Come farlo?

p.s. L'inglese è ancora difficile per me, se qualcosa non è chiaro - chiedimi, per favore.

Answer 1

Facendo una rapida ricerca online, è possibile trovare a post about Hilbert curves sul blog di Steve Eddins. Qui è la sua applicazione per generare la curva:

function [x,y] = hilbert_curve(order) 
    A = zeros(0,2); 
    B = zeros(0,2); 
    C = zeros(0,2); 
    D = zeros(0,2); 

    north = [ 0 1]; 
    east = [ 1 0]; 
    south = [ 0 -1]; 
    west = [-1 0]; 

    for i=1:order 
     AA = [B ; north ; A ; east ; A ; south ; C]; 
     BB = [A ; east ; B ; north ; B ; west ; D]; 
     CC = [D ; west ; C ; south ; C ; east ; A]; 
     DD = [C ; south ; D ; west ; D ; north ; B]; 

     A = AA; 
     B = BB; 
     C = CC; 
     D = DD; 
    end 

    subs = [0 0; cumsum(A)] + 1; 
    x = subs(:,1); 
    y = subs(:,2); 
end 

xy coordinate restituiti sono numeri interi nella gamma [1,2^order]. Come potete vedere qui sotto, la funzione è sufficientemente veloce:

>> for order=1:10, tic, [x,y] = hilbert_curve(order); toc; end 
Elapsed time is 0.001478 seconds. 
Elapsed time is 0.000603 seconds. 
Elapsed time is 0.000228 seconds. 
Elapsed time is 0.000251 seconds. 
Elapsed time is 0.000361 seconds. 
Elapsed time is 0.000623 seconds. 
Elapsed time is 0.001288 seconds. 
Elapsed time is 0.007269 seconds. 
Elapsed time is 0.029440 seconds. 
Elapsed time is 0.117728 seconds. 

Ora cerchiamo di prova con un'immagine con la curva sovrapposto. Abbiamo ridimensionare l'immagine fino a 128x128 in modo che possiamo vedere il modello senza ottenere sovraffollata, ma si può sicuramente fare 512x512 per il vostro caso:

%// some grayscale square image 
img = imread('cameraman.tif'); 

%// scale it down for better visualization 
N = 128 
assert(N > 0 && mod(N,2)==0); 
img = imresize(img, [N N]); 

%// space-filling Hilbert curve 
order = log2(N) 
[x,y] = hilbert_curve(order); 

%// show image with curve overlayed 
imshow(img, 'InitialMagnification',400) 
h = line(x, y); 

Diamo zoom in un po 'per vedere meglio come la curva copre tutti i pixel:

>> zoom(10) 
>> set(h, 'Marker','.') 

Infine è possibile utilizzare gli indici per indicizzare l'i matrix mago:

>> ind = sub2ind([N N], x, y); 
>> pix = img(ind); %// linear indexing 

dove:

>> whos ind 
    Name   Size    Bytes Class  Attributes 

    ind  16384x1    131072 double