반복함수계

컴퓨터 그래픽스 계산물리 마지막 수정: 2026-08-10 04:38:09

1. 개요[편집]

반복함수계 Iterated Function System (IFS)
구성	완비 거리공간 위의 축약 사상 유한 개
작용소	허친슨 작용소 W(A) = ∪ w_i(A)
존재·유일성	바나흐 고정점 정리 (하우스도르프 거리)
역문제	콜라주 정리 (Barnsley, 1985)
렌더링	결정론적 반복 vs 카오스 게임
대표 예	시에르핀스키 삼각형(3맵), 반슬리 고사리(4맵)

반복함수계(Iterated Function System, IFS)는 완비 거리공간 위의 축약 사상 유한 개의 모음 $\{w_1, \dots, w_N\}$ 이며, 그 자체로 하나의 프랙탈 집합을 유일하게 결정한다. 규칙 몇 줄이 무한한 디테일을 낳는다는 프랙탈의 표어를, IFS는 “축약 사상의 계수 몇 개가 집합 하나를 결정한다”는 정리로 못 박는다.

핵심은 관점의 전환이다. 프랙탈을 점의 집합으로 보지 말고, 집합들의 공간 위에서 정의된 한 사상의 고정점으로 보라는 것. 그러면 존재성과 유일성이 바나흐 고정점 정리 한 줄로 끝나고, “어떻게 그리는가”도 “고정점을 어떻게 반복으로 찾는가”라는 익숙한 수치해석 문제가 된다.

차원의 정의, 자기유사성 일반론, 상자 세기 실측 같은 프랙탈 공통 주제는 프랙탈 문서에 있다. 여기서는 IFS 자체의 이론과 계산을 다룬다.

2. 허친슨 작용소와 고정점[편집]

무대는 $\mathbb{R}^n$ 의 공집합 아닌 콤팩트 부분집합 전체의 모임 $\mathcal{H}(\mathbb{R}^n)$ 이다. 여기에 하우스도르프 거리를 준다.

h(A,B) = \max\left\{\, \sup_{a \in A}\inf_{b \in B}|a-b|,\ \ \sup_{b \in B}\inf_{a \in A}|a-b| \,\right\}

말로 풀면 “ $A$ 의 모든 점이 $B$ 에서 $\epsilon$ 이내에 있고 그 반대도 성립하는 최소 $\epsilon$ “이다. 결정적인 사실은 원 공간이 완비이면 $(\mathcal{H}, h)$ 도 완비 거리공간이라는 것이다. 즉 집합을 점처럼 취급해도 되는 무대가 마련된다.

각 $w_i$ 가 립시츠 상수 $s_i < 1$ 의 축약이라 하고, 허친슨 작용소를 정의한다(Hutchinson, 1981).

W(A) \;=\; \bigcup_{i=1}^{N} w_i(A)

이 $W$ 는 $(\mathcal{H}, h)$ 위에서 축약이고, 그 축약 상수는

h\big(W(A), W(B)\big) \;\le\; s\,h(A,B), \qquad s = \max_i s_i < 1

이다(각 조각의 하우스도르프 거리가 합집합에서 최댓값으로 물려받는다는 성질에서 곧장 나온다). 완비공간 위의 축약이므로 바나흐 고정점 정리가 적용되어

유일한 콤팩트 집합 $A^\ast$ 가 존재해 $W(A^\ast) = A^\ast$ 이고, 임의의 초기 콤팩트 집합 $B$ 에 대해 $h\big(W^{\,k}(B),\, A^\ast\big) \le s^{\,k}\, h(B, A^\ast) \to 0$ .

이 $A^\ast$ 를 IFS의 끌개(attractor)라 부른다. 유일성이 강조점이다. 시에르핀스키 삼각형을 그릴 때 정삼각형에서 출발하든 원에서 출발하든 낙서에서 출발하든 같은 극한에 도달한다는 뜻이고, 수렴 속도가 $s^k$ 로 기하급수적이라는 것도 공짜로 따라온다.

자기유사성도 여기서 재정의된다. $A^\ast = \bigcup_i w_i(A^\ast)$ 자체가 “전체가 자기 자신의 축소 복사본들의 합집합”이라는 진술이다. 프랙탈이 자기유사하게 보이는 것이 아니라, 자기유사성을 방정식으로 쓴 것이 곧 IFS다.

3. 차원 — 모란 방정식과 그 한계[편집]

$w_i$ 가 전부 닮음변환(similarity)이고 비율이 $r_i$ 이며, 조각들이 겹침이 심하지 않다는 열린 집합 조건(open set condition)을 만족하면 끌개의 하우스도르프 차원 $D$ 는 모란 방정식의 유일한 해다.

\sum_{i=1}^{N} r_i^{\,D} = 1

모든 비율이 같은 $r$ 이면 익숙한 $D = \ln N / \ln(1/r)$ 로 줄어든다. 시에르핀스키 삼각형은 $N=3,\ r=1/2$ 이므로 $\ln 3/\ln 2 \approx 1.585$ 다. 이 표는 프랙탈 문서에 정리되어 있다.

주의할 것은 이 공식이 닮음일 때만 성립한다는 점이다. 아래 반슬리 고사리처럼 회전·전단이 섞인 일반 아핀 사상은 방향에 따라 축소율이 달라서 모란 방정식이 적용되지 않는다. 자기아핀 집합의 차원 이론은 훨씬 어렵고(팔코너의 아핀 차원 공식은 거의 모든 계수에 대해서만 성립한다), 실무에서는 그냥 상자 세기로 재는 쪽이 빠르다.

4. 카오스 게임 — 왜 확률로 그리는가[편집]

끌개를 화면에 띄우는 방법은 두 가지고, 성격이 완전히 다르다.¹

결정론적 반복. $B_0$ 에서 시작해 $B_{k+1} = W(B_k)$ 를 직접 계산한다. 정의에 충실하고 수렴 보장이 명시적( $s^k$ )이라는 장점이 있지만, 집합을 그대로 들고 다녀야 한다. 폴리곤 목록으로 표현하면 도형 개수가 매 단계 $N$ 배로 늘어 $N^k$ 가 되고, 픽셀 버퍼로 표현하면 매 단계 전체 화면을 $N$ 번 훑어야 한다. 정확한 기하가 필요한 경우(SVG 출력, 얕은 깊이)에 쓴다.

카오스 게임. 아무 점 $x_0$ 에서 출발해, 매 단계 사상 하나를 확률 $p_i > 0$ 으로 뽑아 적용한다.

x_{k+1} = w_{i_k}(x_k), \qquad \Pr[i_k = i] = p_i

그리고 점을 찍는다. 메모리는 점 하나면 되고, 한 점 찍는 비용은 아핀 변환 한 번이다. 초반 수십 점은 아직 끌개에 안착하지 못했으므로 버린다(축약 때문에 $x_k$ 의 끌개까지 거리가 $s^k$ 로 줄어든다 — 20회면 이미 부동소수점 정밀도 안이다).

여기서 자주 나오는 오해를 정리하자. 확률 $p_i$ 는 끌개의 모양을 바꾸지 않는다. 모든 $p_i$ 가 양수이기만 하면 궤도가 조밀하게 놓이는 집합은 언제나 같은 $A^\ast$ 다. $p_i$ 가 결정하는 것은 그 위에 얹히는 측도이며, 이는

\mu = \sum_{i=1}^{N} p_i \,\big(\mu \circ w_i^{-1}\big)

를 만족하는 유일한 불변 측도다. 엘튼의 에르고딕 정리(1987)는 카오스 게임 궤도의 시간 평균이 이 $\mu$ 에 대한 공간 평균으로 거의 확실히 수렴함을 보장한다. 즉 카오스 게임은 몬테카를로이고, 화면에 보이는 점의 밀도가 $\mu$ 다.

그래서 실무 규칙이 나온다. $p_i$ 를 잘못 고르면 집합은 맞는데 어떤 가지가 하얗게 비어 렌더가 오래 걸린다. 아핀 사상 $w_i(\mathbf{x}) = A_i\mathbf{x} + \mathbf{b}_i$ 에 대해

p_i \;\propto\; |\det A_i|

로 잡는 것이 표준이다. 면적을 많이 차지하는 조각에 그만큼 점을 더 보내 밀도를 고르게 만드는 것. $\det A_i = 0$ 인 퇴화 사상은 이 규칙으로는 확률 0이 되어버리므로 작은 하한(예: 0.01)을 따로 준다.

5. 반슬리 고사리 — 아핀 4개[편집]

IFS의 홍보 대사. 마이클 반슬리가 제시한 고사리는 아핀 사상 4개, 즉 실수 24개(각 사상당 $a,b,c,d,e,f$ )로 잎맥까지 완성된다.²

w_i \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} a_i & b_i \\ c_i & d_i \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} e_i \\ f_i \end{pmatrix}

$i$	$a$	$b$	$c$	$d$	$f$	$p$	역할
1	0	0	0	0.16	0	0.01	줄기
2	0.85	0.04	−0.04	0.85	1.60	0.85	전체를 축소·회전해 위로
3	0.20	−0.26	0.23	0.22	1.60	0.07	왼쪽 잎
4	−0.15	0.28	0.26	0.24	0.44	0.07	오른쪽 잎

읽는 법이 재미있다. $w_2$ 는 행렬이 거의 회전-축소( $\sqrt{0.85^2+0.04^2} = 0.851$ )라 고사리 전체를 조금 줄여 위로 밀어 올린다 — 그래서 고사리는 자기 자신을 무한히 쌓아 올린 모양이다. $w_1$ 은 행렬식이 0이라 평면을 선분으로 뭉갠다. 축약 사상이긴 하다(립시츠 상수 $0.16$ ). 가역이 아니어도 축약이기만 하면 IFS 이론은 그대로 성립한다.

전체 축약 상수는 $s = 0.851$ 이고, 이 값이 다음 절의 콜라주 정리에서 증폭 인자로 되돌아온다.

6. 콜라주 정리 — 역문제와 프랙탈 압축[편집]

지금까지는 IFS를 주고 집합을 얻는 순방향이었다. 실용적으로 진짜 궁금한 것은 반대다. 목표 이미지 $L$ 이 주어졌을 때, 그것을 끌개로 갖는 IFS를 어떻게 찾는가? 반슬리의 콜라주 정리(1985)가 답을 준다.

축약 상수 $s$ 인 IFS에 대해 $h\big(L,\ W(L)\big) \le \epsilon$ 이면, 그 IFS의 끌개 $A^\ast$ 는 $h(L, A^\ast) \le \dfrac{\epsilon}{1-s}$ 를 만족한다.

증명은 삼각부등식과 축약성으로 세 줄이다. 그런데 함의가 크다. 끌개를 계산할 필요 없이, 목표 도형을 자기 자신의 축소 복사본 몇 개로 얼마나 잘 덮었는지( $\epsilon$ )만 보면 답의 품질이 보장된다는 뜻이다. 그래서 IFS 설계는 “고사리 사진 위에 반투명한 축소 고사리들을 콜라주처럼 겹쳐 맞추는” 작업이 된다. 실제로 초기 IFS 편집기가 그런 GUI였다.

주의할 함정 두 개. 첫째, 분모의 $1-s$ 다. 축약이 약할수록( $s \to 1$ ) 같은 콜라주 오차가 훨씬 큰 최종 오차로 증폭된다. 고사리의 $s=0.851$ 이면 증폭이 약 6.7배다. 둘째, 이 부등식은 상계일 뿐이라 실제 결과가 훨씬 좋을 수도 있고, 상계가 무의미하게 클 수도 있다.

이 아이디어를 이미지 압축으로 끌고 간 것이 프랙탈 압축이다. 이미지 전체가 자기유사한 경우는 거의 없으므로, 이미지를 작은 치역 블록으로 나누고 각 블록마다 더 큰 정의역 블록 중 (축소·회전·명암 변환 후) 가장 닮은 것을 찾아 그 대응만 저장한다(분할 IFS, Jacquin 1992). 특징이 독특하다.

부호화는 느리고 복호화는 빠르다. 부호화는 블록 짝짓기 탐색이라 무겁고, 복호화는 아무 이미지에서 시작해 사상을 반복하면 끝난다.
해상도 독립. 저장된 것은 픽셀이 아니라 사상이므로, 복호할 때 격자를 더 촘촘히 잡으면 없던 디테일이 “생긴다”. 진짜 정보는 아니지만 확대 시 블록 노이즈 대신 그럴듯한 질감이 나온다.
결국 상용 경쟁에서는 웨이블릿 변환 기반 방식(JPEG 2000 계열)에 밀렸다. 부호화 시간과 특허 문제가 컸다.³

7. 변종과 쓰임새[편집]

응축 IFS(IFS with condensation). 축약 사상들에 고정된 집합 $C$ 를 합집합으로 더한다: $W(A) = C \cup \bigcup_i w_i(A)$ . 나무 줄기처럼 반복되지 않는 부분을 넣을 때 쓴다.
재귀 IFS / 그래프 지향 IFS. 어떤 사상 뒤에 어떤 사상이 올 수 있는지를 유한 오토마타로 제약한다. 단일 IFS보다 훨씬 다양한 집합을 만들며, 마르코프 사슬로 카오스 게임을 돌린다.
L-시스템과의 관계. L-시스템은 문자열 재작성으로 식물을 생성한다. 표현력이 겹치는 부분이 크지만, IFS는 “합집합의 고정점”, L-시스템은 “문법의 유도”라는 점에서 성격이 다르다. 가지 길이가 단계마다 달라지는 성장 규칙은 L-시스템 쪽이 자연스럽다.
컴퓨터 그래픽스에서. 절차적 식생, 결정 구조, 배경 텍스처. 데이터가 계수 몇십 개뿐이라 대역폭이 사실상 0이고, 필요할 때 GPU에서 점을 뿌려 만든다. 점 스플랫이라 폴리곤 파이프라인과 궁합이 좋지는 않아서, 요즘은 IFS로 뽑은 점군을 메시화하거나 거리 함수로 바꿔 레이마칭하는 쪽이 흔하다.
플레임 프랙탈류 렌더링. 아핀 사상 뒤에 비선형 “변주” 함수를 붙이고 로그 밀도로 톤 매핑하는 확장. 카오스 게임의 밀도가 곧 그림이라는 점을 정면으로 활용한 사례다.

8. 구현 시 주의[편집]

축약을 확인하라. 아핀 사상의 립시츠 상수는 $A_i$ 의 최대 특이값 $\sigma_{\max}(A_i)$ 다. 행렬식이 1보다 작다고 축약인 것이 아니다 — 한 방향으로 늘이고 다른 방향으로 심하게 줄이는 행렬은 $|\det| < 1$ 이면서 $\sigma_{\max} > 1$ 일 수 있고, 그러면 궤도가 발산한다. 카오스 게임이 화면 밖으로 날아가면 여기부터 의심한다.
난수의 품질. 사상 선택에 나쁜 난수 생성기를 쓰면 특정 조합이 안 나와서 끌개에 구멍이 생긴다. 저품질 LCG의 하위 비트를 그대로 인덱스로 쓰는 것이 전형적인 사고 패턴이다.
과도 구간을 버려라. 초기 20~50점은 끌개 위에 없다. 특히 시작점을 끌개에서 멀리 잡았다면 더 버려야 한다.
점 밀도와 알파 누적. 점을 그냥 찍으면 밀도가 높은 곳이 포화되어 정보가 사라진다. 히스토그램 버퍼에 누적한 뒤 $\log$ 톤 매핑을 거는 것이 표준이다.

9. 관련 문서[편집]

결정론적 반복이 확률적 반복보다 “정확할 것 같다”는 직관은 반쯤만 맞다. 둘 다 같은 고정점으로 가지만 오차의 성격이 다르다 — 결정론은 하우스도르프 거리가 $s^k$ 로 줄고, 카오스 게임은 몬테카를로라 $1/\sqrt{n}$ 로 채워진다. 화면 채우기가 목적이라면 후자가 압도적으로 싸고, 기하를 뽑아야 한다면 전자밖에 답이 없다. ↩
반슬리는 이 이론으로 회사(Iterated Systems)를 차렸고, 고사리 하나로 “이미지가 실수 24개”라는 슬로건을 만들었다. 물론 임의의 사진이 실수 24개가 되지는 않는다. 자연 이미지의 자기유사성은 고사리만큼 친절하지 않기 때문이다. ↩
1990년대에 프랙탈 압축은 “무한 확대 가능한 이미지”라는 홍보 문구를 달고 등장했고, 마이크로소프트 엔카르타의 이미지 일부가 실제로 이 방식이었다. 무한 확대는 정보가 늘어난다는 뜻이 아니라 없는 디테일을 그럴듯하게 지어낸다는 뜻이었다는 점에서, 요즘의 초해상도 신경망과 비슷한 종류의 마케팅이었다. ↩