如何提高图像的希尔伯特扫描性能？

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.

现在让我们用覆盖了曲线的图像来测试它。我们将图像的大小调整为 128x128，这样我们就可以看到图案而不会过于拥挤，但是您绝对可以根据自己的情况将图像调整为 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','.')

终于可以使用下标对图像矩阵进行索引了：

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

其中：

>> whos ind
  Name          Size             Bytes  Class     Attributes

  ind       16384x1             131072  double

如何提高图像的希尔伯特扫描性能？

How can I improve perfomace of Hilbert scan of image?

performance

matlab

fractals

hilbert-curve

image-scanner