[Physically Based Rendering] 2.1 Monte Carlo: Basics

렌더링에는 적분 문제가 매우 많이 등장한다.

이후 장들에서 보게 되겠지만 카메라의 센서 응답, 참여 매질에서의 빛의 감쇠와 산란, 피부와 같은 재질에서의 산란 등 빛과 관련된 다양한 quantiy들도 적분 방정식으로 표현된다.

 

이러한 적분 방정식들은 일반적으로 해석적인 해를 갖지 않는다. 따라서 우리는 수치적 방법에 의존해야 한다. 사다리꼴 적분이나 가우스 구적법(Gauusian quadrature) 같은 표준적인 수치 적분 기법은 저차원이고 매끄러운 적분을 푸는 데는 효과적이다.

하지만 렌더링에서 흔히 나타나는 고차원적이고 불연속적인 적분에 대해서는 수렴 속도가 좋지 않다.

 

몬테카를로 적분 기법은 이 문제에 대한 하나의 해결책을 제공한다. 몬테카를로 적분은 무작위 샘플링을 사용해 적분값을 평가하며, 그 수렴 속도는 피적분(대상) 함수의 차원에 의존하지 않는다는 특징을 가진다.

 

몬테카를로 적분의 유용한 성질은, 어떤 영역에서의 적분값을 추정하기 위해 필요한 것이 단지 그 영역 안의 임의의 지점에서 피적분 함수를 평가할 수 있는 능력뿐이라는 점이다. 이 성질 덕분에 몬테카를로 적분은 구현하기 쉬울 뿐만 아니라, 매우 다양한 피적분 함수에 적용할 수 있다. 또한 이 방법은 다차원 함수로 자연스럽게 확장된다.

 

무작위성을 신중하게 사용하는 것은 알고리즘 설계 분야에 혁신을 가져왔다. 무작위 알고리즘은 크게 두 가지 부류로 나눌 수 있다. 하나는 Las Vegas 알고리즘, 다른 하나는 Monte Calro 알고리즘이다.

 

Las Vegas 알고리즘은 무작위성을 사용하지만, 최종적으로는 항상 같은 결과를 내는 알고리즘이다. 예를 들어 퀵 정렬에서 피벗 원소를 배열의 임의 위치에서 선택하는 경우가 이에 해당한다.

반면 Monte Calro 알고리즘은 과정 중에 사용된 난수에 따라 서로 다른 결과를 낼 수 있다. 하지만 평균적으로는 올바른 답을 준다. 따라서 같은 입력에 대해 몬테카를로 알고리즘을 여러 번 실행한 뒤 그 결과를 평균내면, 실제 정답에 통계적으로 매우 가까울 가능성이 높은 값을 얻을 수 있다.

 

 

 

2.1 기초

몬테카를로 적분은 무작위화에 기반하므로, 이 장에서는 먼저 이 접근법의 기초가 되는 확률과 통계의 개념을 간단히 복습한다. 이를 통해 기본적인 몬테카를로 알고리즘을 소개하고, 그 오차를 평가하기 위한 수학적 도구들도 함께 다룰 수 있게 된다.

 

2.1.1 배경 지식과 확률 복습

확률 변수 X는 어떤 무작위 과정에 의해 선택되는 값이다. 일반적으로 확률 변수는 대문자로 표기한다. (몇몇 특수한 확률 변수를 나타내는 그리스 문자에는 예외가 있다.) 

 

확률 변수는 항상 어떤 domain(정의역) 으로부터 뽑힌다. 이 정의역은 discrete(이산적) 일 수도 있고, continuous(연속적) 일 수도 있다.

예를 들어 이산적인 경우는 가능한 값들이 고정된 유한한 집합인 경우이고, 연속적인 경우는 실수 집합 R같은 경우이다.

확률 변수 X에 함수 f를 적용하면 새로운 확률 변수 Y=f(X)가 만들어진다.

 

예를 들어 주사위를 한 번 굴린 결과는 사건들의 집합은 아래와 같고 (이산 확률 변수)

각 사간의 확률은 1/6을 가지고, 모든 확률의 합은 반드시 1이다. 

이처럼 가능한 모든 값이 같은 확률을 갖는 확률 변수를 uniform하다고 말한다.

 

이산 확률 변수의 확률을 알려주는 함수 P(X)를 확률 질량 함수, PMF(Probability Mass Function)라고 부른다.

 

두 확률 변수는 하나의 확률이 다른 확률에 영향을 주지 않을 때 독립(Independent)라고 한다.

이 경우 두 확률 변수의 결합 확률(joint probability)는 각각의 확률을 곱한 값으로 주어진다. 

 

 

종속적인(dependent)  확률 변수에서는 하나의 확률이 다른 하나의 확률에 영향을 준다.

검은 공 몇 개와 흰 공 몇 개가 들어 있는 주머니를 생각해 보자. 이 주머니에서 공을 두 개 무작위로 뽑는다면, 두 번째 공이 흰색일 확률은 첫 번째 공의 색에 영향을 받는다. 왜냐하면 첫 번째 선택으로 인해 주머니 안에 남아 있는 특정 색의 공 개수가 달라지기 때문이다.

이때 두 번째 공의 확률은 첫 번째 선택에 조건부로 결정된다(conditioned) 고 말한다. 이 경우 두 공 X 와 Y 를 선택할 결합 확률은 다음과 같다. P(Y|X)는 X의 값이 주어졌을 때 Y의 조건부 확률이다.

 

특히 중요한 확률 변수 중 하나는 표준 균등 확률 변수(canonical uniform random variable)이다.

이를 ξ(xi)로 나타낸다. 이 변수의 domain [0, 1) 안의 모든 값을 독립적으로, 그리고 균등한 확률로 가진다.

 

첫째, 이 분포를 따르는 변수를 소프트웨어에서 생성하기 쉽다. 대부분의 런타임 라이브러리는 이런 값을 생성하는 의사 난수 생성기를 제공한다.

둘째, 표준 균등 확률 변수 ξ 를 이산 확률 변수로 매핑할 수 있다. 예를 들어 다음 조건을 만족하면 ξ 를 선택할 수 있다

 

위 식은 누적 확률 구간에 ξ가 들어가면 선택하겠다는 의미이다.

구간1: 0.0 ~ 0.1

구간2: 0.1 ~ 0.3

구간3: 0.3 ~ 1.0 일 때

확률인 0.33이면 구간3에 속하도록 한다는 의미이다. 

 

조명 처리에서는, 장면 안의 각 광원에서 조명을 샘플링할 확률을 정의하고 싶을 수 있다. 이때 각 광원의 파워 Φi를 전체 광원의 총 파워와 비교하여 다음과 같이 확률을 정할 수 있다. ( pi 값들의 합도 1이다. )

이렇게 각 광원별 확률이 주어지면, ξ 를 사용해서 어떤 광원에서 조명을 샘플링할지 선택할 수 있다.

 

누적 분포 함수(CDF, cumulative distribution function) P(x)는 그 확률 변수의 분포에서 나온 값이 어떤 값 x보다 작거나 같을 확률이다. 

 

주사위 예시로 보면 P(2) = 1/3이다. 

 

연속 확률 변수(Continuous random variables)는 연속적인 영역의 값들을 가질 수 있다. (ex. 실수, 단위구에서의 방향 등)

ξ 외의 연속 확률변수의 예로, 0과 2 사이의 실수 값을 가지는 확률변수를 생각할 수 있다.

이 확률변수는 특정 값 x를 가질 가능성이 2−x라고 가정하자. 즉, 이 확률변수는 1 근처의 값을 가질 때보다 0 근처의 값을 가질 가능성이 두 배 더 높다.

 

확률 밀도 함수  (Probability Density Function)는 이러한 개념을 수식으로 정리한거다. 

PDF는 연속 확률 변수의 분포를 나타내는 밀도 함수이며, 특정 값 주변에 확률이 얼마나 몰려 있는지를 나타낸다. 이산 확률 변수의 PMF에 대응되지만, PDF 값 자체가 확률은 아니고 구간에 대한 적분값이 확률이다.  (PDF p(x)는 확률 변수의 CDF를 미분한 것이다.) 

 

균등 확률 변수의 경우 p(x)는 상수이다. 

PDF는 반드시 0 이상이어야 하며, 정의역 전체에 대해 적분하면 항상 1이 되어야한다. 다만 어떤 한 점 x에서의 PDF값이 반드시 1보다 작아야 하는 것은 아니다.

 

정의역 [a,b]가 주어졌을 때, PDF를 적분하면 확률변수가 그 구간 안에 들어갈 확률을 얻을 수 있다. 

 

 

2.1.2 기대값

함수 f의 기댓값 E|f(x)| 는 정의역 D위의 어떤 값들의 분포 p(x)에 대해, 그 함수의 평균값으로 정의된다.

각 위치 x에서의 함수값 f(x)에, 그 x가 나올 가능성인 p(x)를 곱해서 기댓값을 얻는다는 의미다. 

( f(x) * p(x)는 지점 x가 기댓값에 기여하는 양, 즉 기여도 밀도 )

 

 

예를 들어, 0부터 pi 사이에서 코사인 함수의 기댓값을 구한다고 하자. ( 여기서 p는 균등분포라고 가정한다. )

PDF p(x)는 정의역 전체에서 적분했을 때 1이 되어야 하므로, p(x) = 1/pi 이다.

따라서 아래 처럼 0이 나오고, [0,pi]에서의 cos 평균과 일치한다. 

 

또한 기댓값은 아래와 같은 성질을 가지고 있다.

 

2.1.3 Monte Calro Estimator

이제 임의의 적분값을 근사하는 몬테카를로 추정량(Monte Calro Estimator)을 정의할 수 있다.

1차원 적분을 계산하고 싶다고 하자

구간 [a, b]에서 독립적으로 균등하게 뽑힌 확률변수 Xi들이 주어졌을 때, 몬테카를로 추정량은 다음과 같이 정의된다.

Fn의 수식이 이해가 안되면 보세요.

몬테카를로 추정량은 직접 계산하기 어려운 값을 구하기 위해, 무작위로 뽑은 샘플들을 평균을 내어 근사하는 방법이다.

적분값은 함수 그래프 아래의 면적, 즉 구간 전체에서의 누적된 함수값으로 볼 수 있다.

 

이때 구간 [a, b]에서 함수의 평균적인 높이를 알 수 있다면, 적분값은  구간 길이 x 평균 높이로 생각할 수 있다.

 

결론적으로 아래와 같은 식을 얻을 수 있게된다. 

 

 

이 추정량의 기댓값은 E[Fn]은 실제 적분값과 같다.

 

먼저 확률 변수 Xi에 대응되는 PDF p(x)는 다음과 같아야한다. (균등 확률 변수이기 때문이다.)

앞에서 본 기댓값의 성질을 이용하면 다음과 같이 정리된다.

 

즉, 몬테카를로 추정량의 평균적인 결과는 우리가 구하고 싶은 적분값과 같다.

 

위와 다르게 균등 확률 변수가 아닌 경우도 있을 것이다.

이는 중요한 단계인데, 샘플을 뽑을 PDF를 신중하게 선택하면 오차를 줄일 수 있기 때문이다. 이 기법은 추후 다루겠다.

 

만약 확률 변수 Xi들이 PDF p(x)에서 뽑힌다면, 다음 식을 사용할 수 있다.

이때 제한은 |f(x)| > 0인 모든 x에서 p(x)가 0이 아니어야 한다는 것이다. (만약 f(x)가 큰영역인데, p(x) = 0이라면, 그 영역은 절대 샘플링 되지 않기 때문에 적분값을 제대로 측정할 수가 없다.)

 

 

이제 RandomWalkIntegrator( 무작위로 ray를 쏴서, 최종 색상을 계산하는 시스템)애서 4pi가 왜 등장하는 지 알 수 있다. 

 

우리가 방금 전까지 1차원에서 (b-a)를 사용해서 정규화해주었다. 

3D 공간에서 빛은 사방팔방으로 퍼져나간다. 따라서 적분 범위가 sphere로 바뀐다. 이때 Unit Sphere의 겉넓이가 4pi이다.

 

여기에 p(x) = 1/ 4pi일 것이고, 이를 대입하면 아래의 식을 얻을 수 있을 것이다. 이게 4pi가 등장하는 배경이다.

몬테카를로 방법에서는 적분 함수의 차원과 관계없이 샘플 개수 n을 임의로 선택할 수 있다.

이것은 전통적인 결정론적 구적법에 비해 몬테카를로가 가지는 또 하나의 중요한 장점이다.

전통적인 구적법은 보통 차원이 증가할수록 필요한 샘플 수가 지수적으로 증가한다. 반면 몬테카를로는 차원이 높아져도 같은 방식으로 랜덤 샘플을 뽑아 평균을 내는 구조를 유지할 수 있다.

 

2.1.4 Monte Calro Estimator 오차

몬테카를로 추정량이 올바른 답으로 수렴한다는 것만으로 사용할 가치가 있지는 않다. 얼마나 빠르게 수렴하는지도 중요하다.

 

분산은 함수값이 그 기댓값으로부터 얼마나 벗어나는지를 제곱한 값의 평균이다. 이는 몬테카를로 추정량의 수렴 특성을 나타내는 데 유용하다.

추정량 F의 분산은 다음과 같다. 

(다음과 같은 성질이 있다.)

 

이 성질과 식을 사용하면 분산을 다른 형태로 쓸 수 있다. (전개하면 됨) 

 

몬테 카를로 추정량이 다음과 같을 때, 분산의 성질 때문에 1/n이 1/n^2으로 밖으로 나오게 된다. 

그리고 식을 풀어주면 샘플 개수에 분산은 비례하게 되는데, 

우리가 실제 눈으로보는 오차는 분산이 아니라 표준편차이다. 그렇기 때문에 오차가 줄어드는 속도가 다음과 같다고 할 수 있다.

1차원에서는 일반적인 구적법이 더 빠르게 수렴할 수 있지만, 적분 대상의 차원이 증가하면 그 성능은 지수적으로 나빠진다.

반면 몬테카를로의 수렴률은 차원에 의존하지 않는다. 그래서 고차원 적분에서는 몬테카를로가 사실상 유일하게 실용적인 수치 적분 알고리즘이다.

 

몬테카를로 오차 감소율이 

이라는 특징은 장면을 점진적으로 렌더링하는 과정을 보면 잘 드러난다. 

초반 샘플 수를 늘릴 때에는 비용도 적고 이미지 품질이 빠르게 좋아진다. (오차(노이즈)가 빠르게 감소)

하지만 수십 또는 수백개의 샘플이 이미 사용된 상태에서는 샘플 수를 다시 두 배로 늘리는 데 훨씬 더 오래 걸릴 뿐더러, 오차가 사라지는 데도 많은 시간이 걸린다.  

 

숫자로 예를 들어보면, 오차를 절반으로 줄이기 위해서는 4배 더 많은 샘플링을 해야된다.

만약 n이 1이였다면 1->4로 연산량이 아주 조금 추가된다. 하지만 이미 1024개를 샘플링하고 있을 때는 4096으로 3072이나 증가하게된다. 그래서 효율성 판단이 중요하다.

 

만약 2개의 추정량이 있고, 3ms가 주어졌을 때

두 번째 추정량이 첫 번째 추정량보다 분산이 절반이지만, 하나의 추정 값을 계산하는 비용이 3배가 더 걸릴 때 어떤 것을 선택하는게 좋을까?

 

첫 번째가 좋다.

 

이것을 판단하기 위해서 아래의 식을 사용한다. 

여기서 V[F]는 추정량의 분산이고, T[F]는 그 값을 계산하는 데 걸리는 실행 시간이다.

 

이제 풀어보자 

첫 번쨰 추정량을 F1, 두 번째 추정량을 F2라고 하자.

두 번째 추정량은 분산이 절반이다.

 

V[F1] = 1/2 * V[F2]

하지만 샘플링 비용이 3배더 비싸다

T[F2] = 3 * T[F1]

 

첫 번째 추정량이 샘플 하나를 계산하는 데 1ms가 걸린다고 가정하면, 3ms 동안 첫 번째 추정량은 샘플을 3개 계산할 수 있다.

몬테카를로에서는 샘플 수가 n배 늘어나면 분산은 대략 1/n로 줄어든다.

따라서 첫 번째 추정량을 3번 사용하면 분산은 1/3 V[F1]이 된다.

 

두 번째는 1번의 샘플 밖에 못하기 떄문에 1/2V[F1]이다

 

 

그러므로 첫 번째를 고르는게 효율이 좋다.

 

 

하지만 모든 적분 추정향의 기댓값이 실제 적분값과 같지 않다.

실제 적분값과 기댓값이 다른 추정량을 편향된 추정량(biased estimator)라고 한다.

 

그 차이를 다음과 같이 표현한다.

 

편향된 추정량이라고, 편향되지 않은 추정량보다 더 빠르게 정답에 가까워질 수 있다면 여전히 유용할 수 있다.

 

 

분산과 밀접하게 관련된 개념으로 평균 제곱 오차(MSE, mean squared error)가 있다. MSE는 추정량과 실제 값의 차이를 제곱한 값의 기댓값이다.

분산

편향되지 않은 추정량의 경우, MSE는 분산과 같다. 

 

그렇지 않은 경우는 다음과 같다.

 

 

렌더링 방정식은 너무 복잡해서 수학적으로 완벽한 분산을 계산할 수 없습니다. 그래서 우리는 광선을 n개 쏘고, 그 n개의 결과값들끼리 얼마나 들쭉날쭉한지 계산해서 진짜 분산을 추측해야 합니다. 이를 샘플 분산(Sample Variance)이라고 합니다.

여기서 X_bar는 샘플들의 평균입니다. 즉, 각 샘플값이 평균으로부터 얼마나 떨어져 있는지를 제곱해서 더한 뒤 평균을 낸 값입니다.

이때 n이 아니라 n−1로 나누는 이유는, 표본 평균 X_bar자체가 같은 샘플들로부터 계산된 값이기 때문에 n으로 나누면 실제 분산보다 조금 작게 추정되는 경향이 있습니다.

그래서 n−1로 나누어 값을 약간 키워주는데, 이를 베셀의 보정(Bessel’s correction) 이라고 합니다.

 

다만 표본분산 역시 어디까지나 추정값이라는 점에 주의해야 합니다. 표본 수가 충분하지 않으면 실제 분산을 제대로 반영하지 못할 수 있습니다. 예를 들어 어떤 확률변수가 99.99%의 확률로 값 1을 가지고, 0.01%의 확률로 값 1,000,000을 가진다고 하겠습니다. 이 확률변수에서 무작위 샘플 10개를 뽑았는데 운 좋게 모두 값 1이었다면, 표본분산은 0으로 계산됩니다. 하지만 실제로는 매우 드물게 큰 값이 나오기 때문에, 이 확률변수의 실제 분산은 훨씬 큽니다.

즉, 표본분산은 현재 뽑힌 샘플들이 얼마나 변동되는지를 보여주지만, 샘플에 포함되지 않은 드문 사건까지 항상 잘 반영해 주지는 못합니다.

 

이와 별개로, 만약 적분값에 대한 매우 정확한 기준값을 구할 수 있다면 오차를 다른 방식으로 측정할 수 있습니다. 예를 들어 아주 많은 샘플을 사용해서 실제 적분값에 가까운 값을

 

처럼 얻었다고 하겠습니다. 그러면 각 샘플 결과가 이 기준값으로부터 얼마나 떨어져 있는지를 이용해 평균제곱오차(MSE, Mean Squared Error) 를 추정할 수 있습니다.

여기서 표본분산은 샘플들이 자기 평균 주변에서 얼마나 퍼져 있는지를 보는 값이고, MSE는 샘플들이 정답에 가까운 기준값으로부터 얼마나 떨어져 있는지를 보는 값입니다.

따라서 표본분산은 추정값의 흔들림을 보는 지표이고, MSE는 실제 정답 또는 기준 이미지와 비교했을 때의 오차를 보는 지표라고 정리할 수 있습니다.