画像のヒルベルトスキャンのパーフォマンスを改善するにはどうすればよいですか？

Question

ヒルベルト曲線に基づくこの画像スキャン方法。曲線は次のようになります（1から6の順）：

イメージスキャンに使用できます。例えば、私の3次曲線のコードは、

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

です。私は8次曲線と9次曲線で同じ機能を果たしましたが、非常に遅いです。おそらく、9オーダーは決して終わらないでしょう。少なくとも、私は終わりを待つ忍耐を持っていませんでした - 2時間後に私はプログラムをオフにしました。しかし、7次曲線は15秒間実行されます。どうしたの？私は同じ、しかし速くすることができますか？はい、プログラムは512 * 512の配列要素を読み込む必要がありますが、それを高速化することは不可能ではありません。

これで、正確に何が必要なのですか？私は配列要素の座標を持っていて、読み込むべき順序で配列されています。私はそれらを読んで新しいアレイに書き込むために、受け入れ可能な時間が必要です。どうやってするの？

p.s.何か不明な点があれば、英語はまだ難しいです。お願いします。

Answer 1

オンラインですばやく検索すると、Steve Eddinsのブログでa post about Hilbert curvesが見つかります。

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座標が範囲[1,2^order]の整数です。ここでは曲線を生成するために彼の実装です。以下に見られるように、関数は十分に速いです：

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

ここでは、カーブがオーバーレイされたイメージでテストしてみましょう。我々は過密取得せずにパターンを見ることができるので、128×128までの画像をリサイズしていますが、間違いなくあなたのケースのための512x512の操作を行うことができます。

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

のより良い方法を確認するビットにズームしてみましょう曲線は、すべてのピクセルをカバー：

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

最後に、あなたが私へのインデックスに添字を使用することができますMAGEマトリックス：

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

：私はあなたがタイプミス/バグを持っていると思う

>> whos ind 
    Name   Size    Bytes Class  Attributes 

    ind  16384x1    131072 double