Görselin Hilbert taramasının perfomace'ını nasıl geliştirebilirim?

Question

Bu görüntü tarama metodu Hilbert Curve'e dayanmaktadır. Eğri (1'den 6'ya kadar) gibi gözükür:

Görüntü taraması için kullanılabilir. Örneğin, 3-sıralı eğri için kodum:

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

Ve hızlı çalışıyor ve çalışıyor. Aynı fonksiyonları 8- ve 9 derecelik eğriler için yaptım, ama çok çok yavaş çalışıyor. Belki 9 sıra, asla bitmeyecek. En azından, beklemek için sabır beklemedim - 2 saat sonra programı kapattım. Ancak 7 sıralı eğri, 15 saniye boyunca çalışır. Sorun ne? Aynı şeyi yapabilir miyim, daha hızlı mı? Evet, programın 512 * 512 dizi elemanlarını okuması gerekiyor ama bunu daha hızlı yapması imkansız.

Yani, tam olarak neye ihtiyacım var - Dizi elemanlarının koordinatlarına sahibim ve okunması gereken sıraya göre düzenlenirler. Okumak ve yeni dizide yazmak için kabul edilebilir bir zamana ihtiyacım var. Nasıl yapılır?

p.s. İngilizce benim için hala zor, eğer bir şey belirsiz ise - bana sorun, lütfen.

Answer 1

Hızlı arama çevrimiçi yapın, Steve Eddins blog sitesinde a post about Hilbert curves bulabilirsiniz.

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 

döndü xy-koordinat aralığında [1,2^order] yılında tam sayılardır: Burada eğri oluşturmak için onun uygulamasıdır. Aşağıda görebileceğiniz gibi, fonksiyon yeterince hızlıdır:

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

Şimdi bunun üstüne eğrisi olan bir görüntüyle test edelim. Biz kalabalık almadan desen görebileceği şekilde 128x128 aşağı Biz görüntüyü yeniden boyutlandırmak, ama kesinlikle dava için 512x512 yapabilirsiniz:

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

en iyi nasıl olduğunu görmek için biraz yakınlaştırmak edelim

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

Son olarak i içine dizin alt simgeler kullanabilirsiniz: eğri tüm pikselleri kaplar Mage matrisi:

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

: ı bir yazım hatası/hata var

>> whos ind 
    Name   Size    Bytes Class  Attributes 

    ind  16384x1    131072 double