How can I improve the image performance of a Hilbert image?

Question

This image scanning method is based on the Hilbert curve. The curve looks (from 1 to 6):

It can be used to scan images. So for example, my code for a 3rd order curve:

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

And it works and works fast. I performed the same functions for curves of the 8th and 9th order, but it works very, very slowly. Probably the 9th order will never end. At least I did not have the patience to wait for the end - after 2 hours I just turned off the program. But a 7th order curve lasts 15 seconds. What's the matter? Can I do the same, but faster? Yes, the program should read 512 * 512 elements of the array, but this cannot be impossible.

So, what I need - I have the coordinates of the elements of the array, and they are located in the order in which to read. I need for an acceptable amount of time to read them and write in a new array. How to do it?

ps English is still difficult for me, if something is unclear - ask me, please.

Answer 1

By performing a quick search on the Internet, you can find a post about Hilbert curves on Steve Eddins' blog. Here is its implementation for generating a curve:

 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 

The returned xy coordinates are integers in the range [1,2^order] . As you can see below, the function is fast enough:

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

Now test it with an image with a superimposed curve. We reduce the image size to 128x128 so that we can see the template without overflow, but you can do 512x512 for your case:

 %// 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, [NN]); %// 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 in a bit to better see how the curve spans all pixels:

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

Finally, you can use indexes to index into the image matrix:

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

Where:

 >> whos ind Name Size Bytes Class Attributes ind 16384x1 131072 double