대수적 재구성법

수치해석 계산물리 마지막 수정: 2026-09-01 04:51:17

1. 개요[편집]

대수적 재구성법 Algebraic Reconstruction Technique (ART)
문제	$A\mathbf{x}=\mathbf{b}$ — 투영행렬 · 화소값 · 측정 투영
원형	Kaczmarz (1937) 행 사영법
CT 이름	Gordon–Bender–Herman (1970) — 첫 EMI 스캐너와 같은 해
갱신	$\mathbf{x}\leftarrow \mathbf{x} + \lambda\,\frac{b_i-\mathbf{a}_i^{\mathsf T}\mathbf{x}}{\lVert\mathbf{a}_i\rVert^2}\,\mathbf{a}_i$
변형	SIRT(전체 동시) · SART(뷰 단위) · OS-EM(부분집합)
급소	반복 횟수가 곧 정칙화 — 준수렴(semi-convergence)

역변환 공식을 유도하지 못하겠으면, 그냥 연립방정식으로 놓고 풀면 된다. 미지수가 백만 개인 것만 빼면 아주 좋은 생각이다.

대수적 재구성법(ART)은 단층촬영 재구성을 거대한 선형계 $A\mathbf{x}=\mathbf{b}$ 로 놓고, 방정식 한 줄씩 차례로 만족시키는 사영을 반복해 푸는 반복법이다. 라돈 변환의 역변환 공식을 이산화하는 여과역투영(FBP)과 달리, 연속 공식이 존재하는지 자체를 신경 쓰지 않는다.

A\mathbf{x} = \mathbf{b},\qquad A_{ij} = (\text{$i$번 광선이 $j$번 화소를 지나는 길이})

$\mathbf{x}$ 는 화소(복셀)값 벡터, $\mathbf{b}$ 는 검출기가 잰 투영값이다. 512×512 영상에 800뷰×512채널이면 $A$ 는 대략 $4\times10^5 \times 2.6\times10^5$ 이고, 다행히 한 광선은 화소를 $O(\sqrt{n})$ 개만 지나므로 극도로 희소행렬이다. 불행히도 크기가 커서 저장하지 않고 필요할 때마다 광선 추적으로 즉석 계산하는 것이 표준이다.

이 정식화의 진짜 매력은 계수행렬이 아니라 무엇을 담을 수 있는가에 있다. 콘빔·나선형·비정형 궤적, 검출기 결함으로 빠진 행, 각도가 60도밖에 안 되는 제한각, 화소마다 다른 감쇠 모형, 심지어 비음수 제약과 전변분 벌점까지 전부 같은 틀 안에 들어간다. FBP는 이 중 어느 것도 받아들이지 못한다.

2. 카츠마시의 두 줄[편집]

방법의 뿌리는 폴란드 수학자 스테판 카츠마시가 1937년에 발표한 행 사영법이다. CT는커녕 컴퓨터도 없던 시절이다.

방정식 $\mathbf{a}_i^{\mathsf T}\mathbf{x} = b_i$ 하나는 $\mathbb{R}^n$ 의 초평면 $H_i$ 를 정의한다. 현재 추정값을 그 초평면 위로 직교 사영하는 것이 갱신 한 스텝이다.

\mathbf{x}^{k+1} \;=\; \mathbf{x}^{k} \;+\; \lambda\,\frac{b_i - \mathbf{a}_i^{\mathsf T}\mathbf{x}^{k}}{\lVert \mathbf{a}_i \rVert^{2}}\,\mathbf{a}_i, \qquad i = (k \bmod m) + 1

$\lambda = 1$ 이면 정확히 초평면 위에 내려앉고, $0<\lambda<1$ 이면 덜 가고(완화), $1<\lambda<2$ 이면 지나쳐 간다(과완화). 행을 순환하며 이 사영을 계속하는 것이 전부다. 물리적으로는 “이 광선이 잰 총합이 안 맞네? 그 광선이 지난 화소들에 오차를 골고루 나눠 뿌리자” 이고, 실제로 초기 CT 논문들은 이 방식을 그렇게 설명했다.

수렴 성질은 계가 무모순인지에 달려 있다.

무모순계( $\mathbf{b}$ 가 $A$ 의 치역 안에 있음). $0<\lambda<2$ 에서 해집합의 한 점으로 수렴하며, 그 점은 $\mathbf{x}^0$ 에 가장 가까운 해다. $\mathbf{x}^0 = \mathbf{0}$ 이면 최소 노름 해로 간다. 즉 초기값이 곧 사전 정보다.
모순계(잡음이 있는 실제 데이터는 전부 여기). 수렴하지 않고 극한 순환(limit cycle)을 돈다. 만족시킬 수 없는 방정식들 사이를 영원히 왕복하는 것이고, 그 결과가 영상에 소금-후추 잡음으로 나타난다. $\lambda$ 를 반복마다 줄이면 순환의 반경이 줄어 가중 최소제곱 해 근처로 수렴한다.

여담이지만 이 방법은 볼록집합 사영법(POCS)의 특수 경우다. 초평면은 볼록집합이고, 비음수 조건 $x_j \ge 0$ 도 볼록집합이므로 사영을 하나 더 끼워 넣는 것만으로 제약을 강제할 수 있다. 재구성 코드에서 매 스윕 끝에 음수를 0으로 자르는 그 한 줄이 실은 이론적으로 정당한 연산이다.

3. 행 순서가 수렴을 지배한다[편집]

카츠마시 반복의 수렴 속도는 연속으로 고른 두 초평면이 이루는 각도에 좌우된다. 거의 평행한 두 초평면 사이를 왕복하면 지그재그로 기어가고, 직교하는 두 초평면이면 두 스텝에 끝난다.

CT에서 이건 추상적 이야기가 아니다. 사이노그램을 저장된 순서대로 훑으면 인접한 광선은 거의 나란하고, 따라서 $\mathbf{a}_i$ 들이 거의 평행해 수렴이 참담하게 느려진다. 그래서 실전 ART는 행 순서를 반드시 흩는다.

무작위 순서. 가장 단순하고 대개 충분하다.
허먼-마이어 다단 순서. 뷰 인덱스를 비트 반전에 가까운 규칙으로 재배열해, 연속으로 고르는 뷰가 각도상 최대한 멀어지게 만든다. 결정적이라 재현성이 있다는 것이 장점.
무작위화 카츠마시(스트로머-베르신, 2009). 행 $i$ 를 $\lVert\mathbf{a}_i\rVert^2/\lVert A\rVert_F^2$ 에 비례하는 확률로 뽑으면 기댓값 수렴률에 대한 선형 수렴 보장이 나온다.

\mathbb{E}\bigl\lVert \mathbf{x}^{k}-\mathbf{x}^{\star}\bigr\rVert^{2} \;\le\; \Bigl(1-\kappa^{-2}\Bigr)^{k}\,\bigl\lVert \mathbf{x}^{0}-\mathbf{x}^{\star}\bigr\rVert^{2}, \qquad \kappa = \lVert A\rVert_F\,\lVert A^{+}\rVert_2

70년 된 휴리스틱에 “확률적으로 행을 뽑는다”는 한 줄을 얹자 조건수로 표현되는 깔끔한 수렴률이 나온 셈이고, 이 결과가 무작위 수치선형대수라는 분야를 크게 자극했다. 참고로 이 갱신식은 잔차 제곱합에 대한 확률적 경사하강법의 한 스텝과 형태가 같다 — 딥러닝의 SGD를 아는 사람이라면 처음 보는 식이 아니다.¹

카츠마르츠 갱신 x ← x + λ(b_i − a_iᵀx)a_i/‖a_i‖² 를 56×56 팬텀의 평행빔 투영에 광선 하나씩 적용한다. 투영 각도가 12개면 잔차는 계속 줄어드는데 정답 대비 RMSE 는 10에폭에서 0.1509 에 멈추고, 60개면 같은 10에폭에 0.0557 까지 내려간다. 2 % 잡음 아래에서 λ 를 1.0 으로 올리면 최소 RMSE 가 ep34 에서 ep3 으로 앞당겨지고 그 뒤 60에폭까지 계속 나빠진다.

4. SIRT · SART · 그 사이[편집]

ART의 “한 번에 한 행”은 수렴은 빠르지만 순차적이라 병렬화가 어렵고 잡음에 거칠다. 그래서 갱신 단위를 키운 변형들이 나왔다.

방법	갱신 단위	스윕당 수렴	잡음	병렬성
ART	광선 1개(행 1개)	빠름	거칠다(소금-후추)	나쁨
SART	한 뷰(각도 1개)	중간	중간	좋음
SIRT	전체 행 동시	느림	매끄럽다	매우 좋음

SIRT(길버트, 1972). 모든 행의 보정량을 계산해 한꺼번에 평균해서 반영한다. 사실상 $\lVert A\mathbf{x}-\mathbf{b}\rVert^2$ 에 대한 가중 란트베버 반복 내지 경사하강이며, 모순계에서도 최소제곱 해로 얌전히 수렴한다(극한 순환이 없다). 대신 스윕당 진척이 ART보다 훨씬 적어 수십~수백 회가 필요하다.
SART(앤더슨과 칵, 1984). 뷰 단위로 갱신하는 절충안. 여기에 광선 길이 가중과 쌍선형 보간 기반 투영 모형을 함께 제안해, ART의 소금-후추 잡음을 상당 부분 없앴다. GPU 시대의 실질적 표준에 가깝다.
OS-EM(허드슨과 라킨, 1994). 계보가 조금 다르다. PET·SPECT는 광자 계수가 푸아송이라 최소제곱이 아니라 우도를 최대화해야 하고, 그 표준이 기댓값 최대화 알고리즘 기반 MLEM이다. OS-EM은 여기에 ART의 부분집합 아이디어를 얹어, 뷰를 여러 부분집합으로 나눠 부분집합마다 EM 갱신을 한다. 부분집합 수만큼 가속되는 것이 경험적으로 확인돼 임상 PET 재구성을 사실상 통일했다. 다만 엄밀한 수렴 보장은 잃었다.

정리하면 축은 하나다. 갱신을 잘게 쪼갤수록 스윕당 진척이 빠르지만 잡음과 이론적 안정성을 잃는다. GPU가 흔해진 뒤로는 순차 ART보다 병렬 친화적인 SIRT/SART/OS 계열이 실무를 차지했다 — 알고리즘의 우열이 아니라 하드웨어가 저울을 기울인 사례다.

5. 반복 횟수가 곧 정칙화 — 준수렴[편집]

반복법에는 FBP에 없는 성질이 하나 있다. 오차가 줄다가 다시 늘어난다.

이유는 특이값 분해로 보면 명확하다. 란트베버형 반복은 큰 특이값에 대응하는 성분부터 먼저 복원하고, 작은 특이값 성분은 천천히 채운다. 그런데 잡음은 작은 특이값 방향에서 폭발적으로 증폭되므로, 반복을 계속하면 신호를 다 복원한 뒤부터는 잡음만 열심히 복원한다. 그래서 참값과의 오차가 U자를 그린다. 이 현상을 준수렴(semi-convergence)이라 부른다.

결론은 다소 킹받는다. 일찍 멈추는 것 자체가 정칙화다. 반복 횟수 $k$ 는 티호노프 정규화의 $\alpha$ 나 FBP의 램프 필터 창과 정확히 같은 역할을 하는 파라미터이며, 세 가지가 모두 “해상도와 잡음의 교환비를 어디에 놓을 것인가”라는 한 문제의 다른 얼굴이다. 멈출 시점을 고르는 표준 처방은 역문제의 것을 그대로 쓴다 — 잔차가 잡음 수준에 도달하면 멈추는 모순 원리, L-곡선의 꺾이는 점, 교차검증.

$\lambda$ 도 같은 저울에 있다. 크면 빨리 가지만 잡음도 빨리 들어오고, 작으면 느린 대신 매끄럽다. 실무에서는 $\lambda \approx 0.05\sim0.3$ 에서 시작해 반복마다 줄이는 것이 흔하다.

6. FBP와 언제 갈리는가[편집]

투영이 충분히 촘촘하고 각도가 $[0,\pi)$ 를 다 덮으면 FBP가 압도적이다. 명시적 공식이라 한 번의 필터링과 한 번의 역투영이면 끝나고, 선형이므로 잡음 전파를 손으로 계산할 수 있으며, 결과가 재현 가능하다. 데이터가 온전할 때 반복법을 쓰는 것은 낭비다.

반복법이 이기는 자리는 전부 “데이터가 온전하지 않다”로 요약된다.

각도 부족(sparse-view). 저선량을 위해 뷰를 1/4로 줄이면 FBP는 방사형 줄무늬 아티팩트로 무너진다. 반복법은 부족한 정보를 사전 정보로 메울 수 있다.
제한각(limited angle). 전자 토모그래피의 ±60° 같은 경우. 푸리에 평면에 빠진 쐐기가 생겨 FBP 공식 자체의 전제가 깨진다. 반복법이라고 없는 정보를 만들지는 못하지만, 비음수성·희소성·형상 사전 정보를 강제할 수 있다.
결측·잘림. 죽은 검출기 채널, 금속 임플란트로 포화된 광선, 관심 영역만 스캔한 잘린 투영. 반복법에서는 그냥 그 행을 빼면 된다. FBP에서는 사이노그램을 보간해 메우는 수밖에 없고 그 자국이 영상에 남는다.
비표준 기하. 콘빔, 나선형, 토모신테시스, 자유 궤적 C-암. 해석적 공식을 새로 유도하는 대신 $A$ 만 바꾸면 된다.
정칙화 결합. 전변분 잡음제거의 TV 항을 사전항으로 얹는 것이 sparse-view CT의 국룰이 됐고, 뼈처럼 조각별 상수에 가까운 영상에 특히 잘 듣는다. “왜 뷰를 절반으로 줄여도 되는가”에 대한 이론적 정당화는 압축센싱이 제공한다.

비용은 정직하게 비싸다. 한 스윕이 순투영 + 역투영 한 번씩이므로 대략 FBP 한 번의 두 배이고, 여기에 반복 횟수 10~100을 곱한다. 2010년 전후 임상 스캐너가 반복 재구성으로 넘어갈 수 있었던 것은 알고리즘이 좋아져서라기보다 GPU가 그 계산량을 감당하게 됐기 때문이다.²

7. CT 바깥에서[편집]

같은 정식화는 “선적분을 잰다”는 구조가 있는 곳이면 어디서나 재활용된다.

전자 토모그래피. 시료 홀더 때문에 제한각이 강제되고 전자선 손상 때문에 뷰를 늘릴 수 없다 — 반복법이 선택이 아니라 필수인 대표적 영역.
지진 토모그래피. 지진파 주시(travel time)를 선적분으로 놓고 속도 구조를 역산한다. 광선이 지구 내부를 균일하게 훑지 못하고 지진계도 대륙에만 몰려 있어, 데이터가 지독하게 불완전하다. 이 분야가 SIRT/LSQR을 오래 써 온 이유다.
탄성파·초음파·전기 임피던스. 순연산자가 비선형이면 반복마다 선형화해서 같은 틀을 쓴다.
범용 선형계. ART를 CT에서 떼어 내면 그냥 “거대 희소 과결정계의 행 단위 해법”이다. 크리로프 부분공간법이 행렬 전체와의 곱을 요구하는 것과 달리, 카츠마시는 한 번에 행 하나만 만지면 되므로 $A$ 를 메모리에 올릴 수 없을 때의 선택지가 된다.

한 줄 요약. ART는 재구성을 “공식을 유도하는 문제”에서 “제약을 만족시키는 문제”로 바꿔 놓았다. 느리다는 대가를 치르는 대신, 데이터에 구멍이 났을 때 무엇을 대신 넣을지 사람이 정할 수 있게 됐다.³

8. 관련 문서[편집]

Strohmer, T. & Vershynin, R. (2009). “A Randomized Kaczmarz Algorithm with Exponential Convergence”, J. Fourier Anal. Appl. 여기 나오는 $\kappa = \lVert A\rVert_F\lVert A^{+}\rVert_2$ 는 흔히 쓰는 $\lVert A\rVert_2\lVert A^{+}\rVert_2$ 보다 크다(최대 $\sqrt{n}$ 배). 즉 이 보장은 깔끔하되 낙관적이지는 않으며, 실제 CT 행렬에서 이 상수는 상당히 나쁘다. 그럼에도 이 논문이 중요한 이유는 속도가 아니라 70년 만에 처음으로 수렴률에 상수가 붙었다는 데 있다. ↩
초창기 상용 반복 재구성은 마케팅 이름만 요란하고 실제로는 FBP 결과를 초기값으로 삼아 몇 번만 도는 하이브리드였다. 이유는 순수하게 시간이다 — 흉부 CT 한 건을 5분씩 재구성하는 스캐너는 병원에서 팔리지 않는다. “완전 반복(fully iterative)“이라는 문구가 카탈로그에 등장한 시점이 곧 GPU가 충분해진 시점이다. ↩
그리고 이 자유가 곧 위험이다. 사전 정보를 세게 넣을수록 영상은 예뻐지지만, 없는 구조를 만들어 내거나 있는 병변을 매끄럽게 지워 버릴 수 있다. TV 정칙화를 과하게 먹인 CT 영상이 유난히 “만화 같아” 보이는 것은 조각별 상수 사전이 그렇게 시켰기 때문이다. 진단 영상에서 데이터 일관성 항을 절대 빼지 않는 관행은 이 공포에서 나왔다. ↩