힐베르트 곡선

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

힐베르트 곡선은 1891년 다비트 힐베르트가 제시한 연속 함수로, 0과 1 사이의 수를 0과 1 사이의 정사각형으로 매핑하는 공간 채움 곡선이다. 힐베르트 곡선은 일련의 연속 함수들의 균등 극한으로 정의되며, 1차, 2차, 3차 힐베르트 다각형을 통해 생성 과정을 설명할 수 있다. 이 곡선은 균등 연속 함수이며 전사 함수이지만 단사 함수는 아니고 모든 점에서 미분 불가능하다. 힐베르트 곡선은 1차원과 2차원 공간 사이의 매핑을 제공하여 지역성을 잘 보존하기 때문에 컴퓨터 과학, 특히 이미지 처리, 데이터베이스, 컴퓨터 그래픽스, 로봇 공학 등 다양한 분야에서 활용된다. 또한, 힐베르트 곡선은 린덴마이어 시스템으로 표현할 수 있으며, 3D 프린팅 분야에서도 사용된다.

더 읽어볼만한 페이지

프랙탈 곡선 - 바이어슈트라스 함수
바이어슈트라스 함수는 특정 조건의 상수 $a$ 와 $b$ 를 사용하여 $f(x)= \sum_{n=0}^\infin a^n\cos (b^n\pi x)$ 와 같은 무한 급수 형태로 정의되며 모든 점에서 연속이지만 어느 곳에서도 미분 불가능한 자기 유사성을 지닌 최초로 연구된 프랙탈 중 하나이다.
프랙탈 곡선 - 페아노 곡선
페아노 곡선은 단위 정사각형을 점진적으로 더 작은 정사각형으로 나누고 중심점을 연결하는 과정을 무한히 반복하여 얻어지는 곡선으로, 린덴마이어 시스템으로 구성하거나 힐베르트 곡선처럼 변형될 수 있다.
다비트 힐베르트 - 힐베르트 공간
힐베르트 공간은 내적 공간이면서 내적으로부터 유도된 거리 함수에 대해 완비 거리 공간을 이루는 공간으로, 다양한 함수 공간의 예시를 가지며 푸리에 해석, 양자역학 등 여러 분야에 응용된다.
다비트 힐베르트 - 힐베르트 기저 정리
힐베르트 기저 정리는 가환환 R이 뇌터 환일 때 R을 계수로 하는 다항식환 R[x_1,...,x_n] 역시 뇌터 환임을 명시하는 정리이며, 대수기하학에서 대수적 집합을 유한 개의 다항식의 공통근으로 해석할 수 있게 한다.

힐베르트 곡선

2. 정의

힐베르트 곡선은 연속 함수열의 균등 극한으로 정의되며, 4진법 전개를 이용하여 명시적으로 표현할 수도 있다.^[19] 힐베르트 곡선은 다음과 같은 연속 함수들의 열의 균등 극한이다.

1차, 2차, 3차 힐베르트 다각형을 통해 귀납적으로 정의되며, 이 함수열은 균등 수렴한다.

2. 1. 힐베르트 곡선의 정의

'''힐베르트 곡선'''(Hilbert curve|힐베르트 커브^영어)은 다음과 같은 연속 함수들의 열

h_n\colon[0,1]\to[0,1]\times[0,1]

(

n\in\mathbb Z^+

)의 균등 극한이다.

(1차 힐베르트 다각형) 구간 $[0,1]$ 을 4등분하고, 정사각형 $[0,1]\times[0,1]$ 을 4개의 부분 정사각형으로 등분한다. 분할된 4개의 구간과 4개의 정사각형을 대응시킨다. (이웃하는 구간은 이웃하는 정사각형과 대응한다.) 이제 이웃하는 두 구간에 대응하는 두 정사각형의 중심을 이어붙인다.
(2차 힐베르트 다각형) 다시 각 구간과 그에 대응하는 정사각형을 4등분한 뒤, 16개의 구간과 16개의 정사각형을 대응시킨다. (각 구간의 부분 구간은 그 구간에 대응하는 정사각형의 한 부분 정사각형에 대응하며, 이웃하는 구간은 이웃하는 정사각형과 대응한다.) 15쌍의 이웃하는 구간에 대응하는 15쌍의 정사각형의 중심을 이어붙인다.
(3차 힐베르트 다각형) 16개의 구간과 16개의 정사각형을 각각 64개의 부분 구간과 64개의 부분 정사각형으로 등분하여 같은 과정을 반복한다. 이러한 과정은 1차 힐베르트 다각형과 ‘닮은’ 부분 곡선을 2차 힐베르트 다각형과 닮은 모양으로 대체하는 것으로 요약할 수 있다.

(h_n)_{n\in\mathbb Z^+}

이

h

로 균등 수렴함은 다음과 같이 보일 수 있다. 축소 구간 정리에 따라, 임의의

t\in[0,1]

에 대하여,

(h_n(t))_{n\in\mathbb Z^+}

는 어떤 점

h(t)\in[0,1]\times[0,1]

로 수렴한다.

h(t)

와

h_n(t)

는

n

번 분할로 얻어진 변의 길이가

1/2^n

인 같은 작은 정사각형에 속하며, 따라서 이들 사이의 거리는 작은 정사각형의 대각선을 넘지 않는다. 즉, 다음이 성립한다.

:

|h(t)-h_n(t)|\le\sqrt 2/2^n\qquad(\forall t\in[0,1],n\in\mathbb Z^+)

따라서

(h_n)_{n\in\mathbb Z^+}

은

h

로 균등 수렴한다.

2. 2. 명시적 표현

구간 Interval (mathematics)|구간^영어 [0, 1] 속의 수를 4진법으로 나타내고, 정사각형 [0, 1]×[0, 1] 속 점을 복소수로 여겼을 때, '''힐베르트 곡선'''은 다음과 같이 명시적으로 나타낼 수 있다.^[19]

:

h\colon[0,1]\to[0,1]\times[0,1]

:

\begin{align}h(t)&=\sum_{j=1}^\infty(-1)^{e_{3j}}2^{-j}\sgn(t_j)(t_j-1+(-1)^{d_j}i)\exp(i\pi d_j/2)\\&=\sum_{j=1}^\infty(-1)^{e_{0j}}2^{-j}\sgn(t_j)((1-d_j)t_j-1+(1-d_jt_j)i)\end{align}

여기서

$t=0.t_1t_2t_3\cdots_{(4)}$ 는 $t$ 의 4진법 전개이다.
$e_{kj}=|\{r\in\{1,2,\dots,j-1\}\colon t_r=k\}|\in\mathbb Z/2\mathbb Z=\{0,1\}$
$d_j=e_{0j}+e_{3j}\in\mathbb Z/2\mathbb Z=\{0,1\}$
$\sgn$ 은 부호 함수이다.
$\exp$ 는 지수 함수이다.
$i$ 는 허수 단위이다.

3. 성질

힐베르트 곡선은 균등 연속 함수이자 전사 함수이지만, 단사 함수가 아니고 모든 곳에서 미분 불가능하다.^[19]

3. 1. 연속성

균등 연속 함수이다.^[19]

3. 2. 전사성

힐베르트 곡선은 전사 함수이다.^[19] 즉, 2차원 공간의 모든 점을 채운다.

3. 3. 미분 불가능성

힐베르트 곡선은 모든 곳에서 미분 불가능하다. 특히, 립시츠 연속 함수가 아니다.^[19]

4. 역사

다비트 힐베르트가 1891년 논문에서 제시하였다.^[20] 이는 처음 제시된 공간 채움 곡선은 아니지만, 그가 논문에 실은 그림은 공간 채움 곡선의 생성 과정을 설명하는 최초의 그림이다.^[19]

4. 1. 힐베르트의 발견

다비트 힐베르트가 1891년 논문에서 제시하였다.^[20] 이는 처음 제시된 공간 채움 곡선은 아니지만(최초의 공간 채움 곡선은 주세페 페아노가 제시하였다), 그가 논문에 실은 그림은 공간 채움 곡선의 생성 과정을 설명하는 최초의 그림이다(#정의에서의 그림과 유사하다).^[19]

5. 응용

힐베르트 곡선은 1차원과 2차원 공간 사이의 매핑을 제공하며, 지역성을 상당히 잘 보존하는 특성이 있다.^[4] 이는 1차원 공간에서 서로 가까운 두 데이터 점이 곡선을 따라 배치된 후에도 서로 가깝게 유지된다는 것을 의미한다. 이러한 특성 덕분에 힐베르트 곡선은 컴퓨터 과학, 이미지 처리, 데이터베이스, 컴퓨터 그래픽스, 로봇 공학, 3D 프린팅 등 다양한 분야에서 응용된다.

5. 1. 컴퓨터 과학

힐베르트 곡선과 그 이산적인 근사값은 1차원과 2차원 공간 사이의 매핑을 제공하여 지역성을 상당히 잘 보존하기 때문에 유용하다.^[4] 1차원 공간에서 서로 가까운 두 데이터 점은 접힌 후에도 서로 가깝게 유지된다.

이러한 지역성 때문에 힐베르트 곡선은 컴퓨터 과학에서 널리 사용되며, 모바일 로봇으로 지역을 탐색하기 위한 알고리즘 설계에도 활용되었다.^[6]^[7]

곡선을 따라 임의의 점의 선형 거리는 스킬링의 방법 등 표준 수학적 기법을 사용하여 n차원 좌표로 변환하거나, 그 반대로도 변환할 수 있다.^[12]^[13]

데이터 공간이 사각형을 형성하지 않는 경우에도 힐베르트 곡선을 효율적으로 구현할 수 있으며,^[14] 힐베르트 곡선을 고차원으로 일반화하는 여러 방법도 존재한다.^[15]^[16]

5. 1. 1. 이미지 처리

힐베르트 곡선은 Riemersma 디더링과 같은 이미지 처리 알고리즘에 사용된다.^[8] 1차원과 2차원 공간 사이의 매핑을 제공하여 지역성을 상당히 잘 보존하기 때문에 이러한 용도로 유용하다.^[4]

Riemersma 디더링에서 grayscale 사진은 각 픽셀에서 남은 양을 힐베르트 곡선을 따라 다음 픽셀에 추가하여 임계값을 사용해 디더링된 흑백 이미지로 변환될 수 있다. 힐베르트 곡선은 픽셀의 각 행에서 단순히 왼쪽에서 오른쪽으로 순서가 정해진 경우 눈에 보이는 방해 패턴을 만들지 않기 때문에 사용된다.^[8]

5. 1. 2. 데이터베이스

힐베르트 곡선은 Z-order보다 더 나은 지역성 보존 동작을 보이기 때문에 다차원 데이터베이스에서 Z-order 대신 사용될 것을 제안되었다.^[9] 예를 들어, 힐베르트 곡선은 R-tree 인덱스를 압축하고 가속화하는 데 사용되었다(Hilbert R-tree 참조).^[9] 또한 힐베르트 곡선은 데이터 웨어하우스를 압축하는 데 도움을 주기도 했다.^[10]^[11]

5. 1. 3. 컴퓨터 그래픽스

힐베르트 곡선은 1차원과 2차원 공간 사이의 매핑을 제공하여 지역성을 잘 보존하기 때문에 컴퓨터 그래픽스 분야에서 유용하게 활용된다.^[4] 이러한 지역성 속성은 컴퓨터 과학에서 널리 사용된다.

예를 들어, 컴퓨터가 사용하는 IP 주소 범위는 힐베르트 곡선을 사용하여 그림으로 매핑될 수 있다. 이미지를 생성하는 코드는 각 픽셀의 색상을 찾기 위해 2D에서 1D로 매핑하며, 힐베르트 곡선은 근처 IP 주소를 그림에서 서로 가깝게 유지하기 때문에 사용되기도 한다.^[5]

Riemersma 디더링 알고리즘에서, grayscale 사진은 힐베르트 곡선을 따라 각 픽셀에서 남은 양을 다음 픽셀에 추가하여 임계값을 사용해 디더링된 흑백 이미지로 변환될 수 있다.^[8]

블렌더 및 시네마 4D와 같은 일반적인 프로그램은 힐베르트 곡선을 사용하여 객체를 추적하고 장면을 렌더링한다.

5. 2. 로봇 공학

힐베르트 곡선은 그 지역성 속성 때문에 모바일 로봇을 이용한 지역 탐색 알고리즘 설계에 사용된다.^[6]^[7]

5. 3. 3D 프린팅

3D 프린터의 공구 경로로 3D 모델을 변환하는 데 사용되는 슬라이서 소프트웨어는 힐베르트 곡선을 내부 채움 패턴 옵션으로 제공한다.^[17]

6. 표현

힐베르트 곡선은 L-시스템 등 다양한 방법으로 표현될 수 있다.^[17]

6. 1. 린덴마이어 시스템

힐베르트 곡선은 L-시스템으로 표현할 수 있다.

'''알파벳''': A, B
'''상수''': F, +, −
'''공리''': A
'''생산 규칙''':
* A → +BF−AFA−FB+
* B → −AF+BFB+FA−

여기서 "F"는 "앞으로 그리기"를 의미하고, "+"는 "왼쪽으로 90° 회전", "-"는 "오른쪽으로 90° 회전"을 의미하며(터틀 그래픽스), "A"와 "B"는 그리는 동안 무시된다.

6. 2. 기타 구현

《그래픽 젬스 II》에서는 힐베르트 곡선의 일관성을 논하며 구현을 제공한다.^[17]

힐베르트 곡선은 이미지를 렌더링하거나 비디오를 렌더링하는 데 일반적으로 사용된다. 블렌더 및 시네마 4D와 같은 일반적인 프로그램은 힐베르트 곡선을 사용하여 객체를 추적하고 장면을 렌더링한다.

3D 모델을 3D 프린터의 공구 경로로 변환하는 데 사용되는 슬라이서 소프트웨어는 일반적으로 힐베르트 곡선을 내부 채움 패턴 옵션으로 제공한다.

참조

_[1] 논문 Über die stetige Abbildung einer Linie auf ein Flächenstück. http://www.digizeits[...] Mathematische Annalen 1891
_[2] 논문 Sur une courbe, qui remplit toute une aire plane. http://www.digizeits[...] Mathematische Annalen 1890
_[3] 웹사이트 Chapitre 1: fractales http://pascale.et.vi[...] Pascale Bourges 2019-02-09
_[4] 논문 Analysis of the clustering properties of the Hilbert space-filling curve
_[5] 웹사이트 Mapping the whole internet with Hilbert curves https://blog.benjojo[...] 2021-01-02
_[6] 간행물 Exhaustive geographic search with mobile robots along space-filling curves http://link.springer[...] Springer Berlin Heidelberg 1998
_[7] 학술회의 Fractal trajectories for online non-uniform aerial coverage
_[8] 저널 A Balanced Dithering Technique https://www.drdobbs.[...] Dr. Dobb's 1998-12-01
_[9] 논문 Hilbert R-tree: An improved R-tree using fractals Morgan Kaufmann Publishers Inc.
_[10] 서적 Data Warehousing and Knowledge Discovery
_[11] 저널 Reordering Columns for Smaller Indexes
_[12] 웹사이트 Programming The Hilbert Curve by John Skilling https://pubs.aip.org[...]
_[13] 웹사이트 Grant Tebbin: Calculating Hilbert Curve Coordinates https://www.grant-tr[...]
_[14] 저널 Compact Hilbert indices: Space-filling curves for domains with unequal side lengths
_[15] 저널 On multidimensional curves with Hilbert property
_[16] 논문 Four-dimensional Hilbert curves for R-trees
_[17] 문서 Space-Filling Curves and a Measure of Coherence Graphics Gems II
_[18] 논문 Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 1891
_[19] 서적
_[20] 저널 https://archive.org/[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com