Wie kann ich die Leistung des Hilbert-Scan des Bildes verbessern?

Question

Diese Methode des Bildscannens basiert auf der Hilbert-Kurve. Die Kurve sieht wie folgt aus (von 1 bis 6):

Sie kann für den Bildscan verwendet werden. So zum Beispiel, mein Code für 3-Order-Kurve ist:

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)]; 

Und es funktioniert und arbeitet schnell. Ich habe die gleichen Funktionen für Kurven der 8- und 9-Ordnung gemacht, aber es funktioniert sehr sehr langsam. 9-order wird vielleicht niemals enden. Zumindest hatte ich nicht die Geduld, auf das Ende zu warten - nach zwei Stunden habe ich einfach das Programm abgeschaltet. Aber die Kurve 7-order läuft für 15 Sekunden. Was ist los? Kann ich dasselbe tun, aber schneller? Ja, das Programm muss 512 * 512 Array-Elemente lesen, aber es kann nicht unmöglich sein, es schneller zu machen.

Also, was genau ich brauche - ich habe die Koordinaten der Array-Elemente, und sie sind in der Reihenfolge angeordnet, in der gelesen werden soll. Ich brauche für eine akzeptable Zeit, um sie zu lesen und in das neue Array zu schreiben. Wie es geht?

p.s. Englisch ist immer noch schwer für mich, wenn etwas unklar ist - frag mich bitte.

Answer 1

Machen Sie eine schnelle Suche online, finden Sie a post about Hilbert curves auf Steve Eddins Blog. Hier ist seine Umsetzung die Kurve zu generieren:

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 

Die zurück xy-Koordinaten sind ganze Zahlen im Bereich [1,2^order]. Wie Sie sehen können, ist die Funktion ausreichend schnell:

>> 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. 

es sich jetzt lassen Sie testen, mit einem Bild mit der überlagerten Kurve. Wir skalieren das Bild nach unten zu 128x128, so dass wir das Muster ohne immer überfüllt sehen, aber Sie können auf jeden Fall tun 512x512 für Ihren Fall:

%// 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); 

Lassen Sie uns ein bisschen heran besser zu sehen, wie die Kurve umfasst alle Pixel:

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

Schließlich können Sie die Indizes zum indizieren in die ich benutze Magier Matrix:

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

wo:

>> whos ind 
    Name   Size    Bytes Class  Attributes 

    ind  16384x1    131072 double