Кривая Гильберта-Пеано для сканирования изображения произвольного размера
Я написал реализацию кривой заполнения пространства Гильберта-Пеано в Python (от Matlab), чтобы сгладить мое 2D-изображение:
def hilbert_peano(n):
if n<=0:
x=0
y=0
else:
[x0, y0] = hilbert_peano(n-1)
x = (1/2) * np.array([-0.5+y0, -0.5+x0, 0.5+x0, 0.5-y0])
y = (1/2) * np.array([-0.5+x0, 0.5+y0, 0.5+y0, -0.5-y0])
return x,y
Однако классическая кривая Гильберта-Пеано работает только для многомерного массива, форма которого является степенью двойки (например, 256*256 или 512*512 в случае двумерного массива (изображение)).
Кто-нибудь знает, как расширить это на массив произвольного размера?
2 ответа
Наконец, я решил, как предложил Беттердев, поскольку адаптивные кривые не так уж прямолинейны [1], чтобы вычислить большую кривую, а затем избавиться от координат, которые находятся за пределами формы моего изображения:
# compute the needed order
order = np.max(np.ceil([np.log2(M), np.log2(N)]))
# Hilbert curve to scan a 2^order * 2^order image
x, y = hilbert_peano(order)
mat = np.zeros((2**order, 2**order))
# curve as a 2D array
mat[x, y] = np.arange(0, x.size, dtype=np.uint)
# clip the curve to the image shape
mat = mat[:M, :N]
# compute new indices (from 0 to M*N)
I = np.argsort(mat.flat)
x_new, y_new = np.meshgrid(np.arange(0, N, dtype=np.uint), np.arange(0, M, dtype=np.uint))
# apply the new order to the grid
x_new = x_new.flat[I]
y_new = y_new.flat[I]
[1] Чжан Дж., Камата С., Уэсиге Й., "Алгоритм псевдогильбертового сканирования для области произвольного размера прямоугольника"
У меня была такая же проблема, и я написал алгоритм, который генерирует кривую Гильберта для прямоугольников произвольного размера в 2D и 3D. Пример для 55x31: curve55x31
Идея состоит в том, чтобы рекурсивно применить шаблон, подобный Гильберту, но избегать нечетных размеров при уменьшении вдвое размеров области. Если размеры являются степенями двойки, генерируется классическая кривая Гильберта.
def gilbert2d(x, y, ax, ay, bx, by):
"""
Generalized Hilbert ('gilbert') space-filling curve for arbitrary-sized
2D rectangular grids.
"""
w = abs(ax + ay)
h = abs(bx + by)
(dax, day) = (sgn(ax), sgn(ay)) # unit major direction
(dbx, dby) = (sgn(bx), sgn(by)) # unit orthogonal direction
if h == 1:
# trivial row fill
for i in range(0, w):
print x, y
(x, y) = (x + dax, y + day)
return
if w == 1:
# trivial column fill
for i in range(0, h):
print x, y
(x, y) = (x + dbx, y + dby)
return
(ax2, ay2) = (ax/2, ay/2)
(bx2, by2) = (bx/2, by/2)
w2 = abs(ax2 + ay2)
h2 = abs(bx2 + by2)
if 2*w > 3*h:
if (w2 % 2) and (w > 2):
# prefer even steps
(ax2, ay2) = (ax2 + dax, ay2 + day)
# long case: split in two parts only
gilbert2d(x, y, ax2, ay2, bx, by)
gilbert2d(x+ax2, y+ay2, ax-ax2, ay-ay2, bx, by)
else:
if (h2 % 2) and (h > 2):
# prefer even steps
(bx2, by2) = (bx2 + dbx, by2 + dby)
# standard case: one step up, one long horizontal, one step down
gilbert2d(x, y, bx2, by2, ax2, ay2)
gilbert2d(x+bx2, y+by2, ax, ay, bx-bx2, by-by2)
gilbert2d(x+(ax-dax)+(bx2-dbx), y+(ay-day)+(by2-dby),
-bx2, -by2, -(ax-ax2), -(ay-ay2))
def main():
width = int(sys.argv[1])
height = int(sys.argv[2])
if width >= height:
gilbert2d(0, 0, width, 0, 0, height)
else:
gilbert2d(0, 0, 0, height, width, 0)
3D-версия и дополнительная документация доступны по адресу https://github.com/jakubcerveny/gilbert.
Я нашел эту страницу Lutz Tautenhahn:
"Нарисуйте заполненную пробелами кривую произвольного размера" ( http://lutanho.net/pic2html/draw_sfc.html)
Алгоритм не имеет имени, он не ссылается ни на кого другого, и набросок предполагает, что он придумал его сам.
Интересно, возможно ли это для кривой порядка z и как?