지난 포스팅(#디지털 영상 처리를 활용하는 분야의 예시)에서 전자기 스펙트럼(Electromagnetic Spectrum)을 잠깐 다루었다. 이번 포스팅에서 이를 좀 더 자세히 살펴보자.
- 전자기 스펙트럼(Electromagnetic Spectrum):
1666년 아이작 뉴턴(Issaac Newton)은 햇빛이 단순히 흰색 빛이 아니라 연속적인 컬러스펙트럼으로 구성된다는 것을 프리즘을 통과했을 때 보라색부터 빨간색까지 연속적인 컬러 스펙트럼이 만들어지는 현상을 통해 발견하였다. 아래 그림과 같이 이 보라색부터 빨간색까지의 범위를 가시광선이라 하는데, 우리 눈에 보이는 영역을 의미한다. 그림에 보여지는 것과 같이 이 가시광선 영역은 전체 전자기 스펙트럼에서 아주 작은 부분에 해당한다. 우측 끝엔 라디오(Radio)파가 위치해 있고 가시광선 역역에 비해 파장이 수십억배 길다. 반대로 좌측 끝엔 감마선(Gamma Ray)이 있으며 가시광선에 비해 파장이 수백만배 짧다. 아래 그림을 참고하자.
전자기 스펙트럼은 파장(wavelength), 주파수(frequency) 로 표현된다. 이러한 파장과 주파수의 관계는 아래 식과 같이 표현된다. 람다는 파장을, 주파수는 v, c는 광속을 각각 의미한다.
전자기 스펙트럼의 에너지는 주파수에 특정 상수를 곱하여 표현하는데, 아래 식과 같다.
여기서 h는 Plank's 상수이다. Plank's상수는 입자의 에너지와 진동수의 비를 나타낸 상수로써 h=E/f로 정의 된다. 양자역학의 기본 상수 중 하나이다. (출처: 위키백과)
각 요소의 단위는 다음과 같다.
전자기파는 사인파(sinusoidal waves)를 람다(lambda)길이 만큼의 파장으로 전파시키는 것으로 볼 수 있다. 혹은 질량이 없는 입자(particles)들의 흐름(stream)으로써 wave형태의 패턴으로 빛의 속도로 움직이는 것으로 생각할 수도 있다.
람다(lambda)는 사인파의 주기를 뜻하는 것으로 사인파는 똑같은 패턴의 신호가 주기적으로 나타나는 형태이다. 즉 처음 나타난 패턴의 한 점이 다시 나오기까지 걸리는 시간을 의미한다.
각 무질량 입자(massless particles)들은 어느 정도의 에너지 덩어리를 가지고 있는데, 각 덩어리 에너지를 우리는 광자(photon)라 부른다. 에너지에 대한 얘기를 해보자면 에너지는 식(2)에 정의되어 있는데, 에너지는 주파수에 비례함을 식(2)로부터 알 수 있다. 즉 주파수(frequency)가 높을 수록(주파수가 높으면 주기는 짧아짐) 광자가 더 많은 에너지를 갖게 된다. 따라서 라디오파는 가장 낮은 에너지를 가지고, 적외선(infrared), 가시광선(visible), 자외선(ultraviolet), X선(X-ray), 감마선 순으로 높은 에너지를 갖는다. 이를 통해 우리는 왜 감마선이 인체 조직에 위험한지를 알 수 있다. 높은 에너지를 가진 감마선이 인체를 투과하며 조직을 파괴하거나 변형시키는 등 인체에 위험을 초래할 수 있다.
- 가시광선(Visible Ray):
빛은 우리 눈에 감지가 되는 특수한 형태의 전자기 방사(electromagnetic radiation)이다. 우리 눈에 보이는 빛 영역인 가시광선은 위 그림에서 색깔로 처리되어 확대하여 나타나 있다. 가시광선 영역은 파장의 길이가 약 0.43μm(보라색) ~ 0.79μm(빨간색)에 걸쳐 분포해 있다. 에너지가 강한 순서대로(주파수가 높고 파장이 짧은 순서) 나열해보면 보라, 파랑, 초록, 노랑, 오렌지색, 그리고 빨간색의 순으로 분포하며, 색의 변화는 연속적으로 변한다. 무지개 색을 떠올리면 쉽게 연상이 될 것이다.
인간은 눈으로 어떤 물체의 형태와 색깔을 인지할 수 있는데, 이러한 물체의 색깔은 물체가 반사하는 고유의 특성에 따라 인식된다. 쉽게 말해 물체의 표면 특성에 따라 전자기 스펙트럼의 영역에서 반사하는 정도가 다른 것이다. 예를 들어 초록색 공이 있다고 가정했을 때, 이 물체가 초록색으로 보이는 것은 공의 몸체가 500~570 nm 파장 영역의 빛을 주로 반사하는 반면, 다른 파장의 빛에너지는 대부분 흡수하기 때문이다. 위 그림에 보이는 사과가 빨갛게 보이는 까닭도 같은 이유에서다. 모든 파장의 빛을 고르게 반사하는 물체는 흰색으로 보인다.
- 단색광(monochromatic light):
색깔이 없는 빛을 우리는 단색광(monochromatic light)이라 한다. 이러한 단색광이 가지는 유일한 속성은 바로 빛의 밝기 강도(intensity)이다. 단색광은 우리 눈에 검은색에서 점차적으로 회색, 그리고 흰색으로 변하는 것으로 인식되기 때문에 보통 gray level이라는 용어가 이 단색광의 밝기 강도를 나타내기 위해 사용된다. 결국 intensity와 gray level은 같은 의미이다. 이렇게 검은색에서 회색, 그리고 흰색으로 변하는 범위를 우리는 gray scale이라고 하며, 이러한 gray scale을 사용하는 흑백 이미지를 gray scale image라고 부른다.
- 유색광(chromatic light):
유색광은 전자기 스펙트럼에서 대략 0.43μm(보라색) ~ 0.79μm(빨간색) 파장의 영역에서 분포한다. 유색광은 주파수와 함께 다음의 세 가지 요소들로 설명될 수 있다.
복사휘도(Radiance): 광원으로부터 흐르는 에너지의 실제 총량. 보통 와트(W, watts) 단위로 측정됨
발광휘도(Luminance): 관찰자가 감지할 수 있는 광원으로부터 흐르는 에너지의 양. 루멘스(lm, lumens) 단위로 측정됨
명도(Brightness): 인간이 느끼는 주관적인 빛의 밝기. 정확히 측정하기는 어렵다. 컬러 정보의 느낌을 기술하는데에 있어 핵심 요소임
위의 말을 토대로 판단해보자면 복사 휘도와 발광 휘도의 개념이 조금 헷갈릴 것이다. 이와 관련된 예를 들어보자.
어떤 광원으로부터 얼마간의 적외선(infrared)이 방출되었다. 이 광원으로부터 나온 빛은 얼마의 에너지, 즉 복사휘도(Radiance) 에너지를 가지고 있다. 그러나 관찰자는 이를 감지할 수 없었다. 이때의 발광휘도(Luminance)는 거의 제로에 가깝다. 즉 복사휘도와 발광휘도를 나누는 기준은 관찰자(사람)가 감지할 수 있느냐 없느냐에 달려있는 것이다. 정리하자면 복사휘도는 방출한 빛 에너지의 실제 총량을, 발광휘도는 관찰자를 기준으로 관찰자가 감지할 수 있는 빛 에너지의 총량을 나타내는 것이다.
- X선과 감마선(X-rays and Gamma radiation):
가시광선에 이어서 전자기 스펙트럼에서 높은 에너지를 가지는 영역을 살펴보자. 좌측 끝에는 X선(X-rays)과 감마선(gamma radiation)이 위치해 있다. 감마선은 의료, 우주, 원자력환경에서 중요한 역할을 한다. X선도 Hard(High energy)와 Soft(Low energy)의 경우로 나눌 수 있는데, Hard의 경우 산업현장에서, Soft의 경우 의료 분야에서 흉부나 치과 치료를 위한 이미지를 촬영하는데 사용된다.
이 밖에도 전자레인지에 사용되는 마이크로파(Microwaves), TV와 라디오에 사용되는 라디오파(radio wave)등이 있다.
비록 대부분의 이미지들이 전자기파에 의해 방출되는 에너지에 의해 형성된다곤 하지만, 어떤 이미지를 형성하기 위한 방법은 이것이 전부가 아니다. 예를 들면 물체로부터 반사되는 소리로부터 이미지를 형성하는 초음파 이미지(ultrasonic images)가 있다. 또한 전자현미경(electron microscopy)의 전자빔(electron beams)에 의해 형성된 이미지, 그래픽스(graphics)에 의해 합성된 이미지 등도 이러한 예 중 하나 이다.
지난 포스팅의 마지막 부분에 우리는 치환행렬(Permutation matrix)과 전치(Transpose)에 대해 간략히 언급하였다. 이번 포스팅의 서두에선 이에 대해 좀 더 이야기해보고 마무리 짓도록 하자.
1. Permutations
이전 포스팅에서 언급했듯이 치환 행렬(Permutation matrix)은 행 교환(row exchange)을 수행하는 행렬이다. 그렇다면 이러한 치환 행렬은 언제 필요할까? 우리는 지금까지 행렬의 소거를 하는 과정에서 행 교환이 필요없는 경우를 가정하고 소거를 진행하였다. 하지만 항상 완벽한 행렬만 존재할 수는 없기 때문에 반드시 행 교환이 필요할 때가 있다. 바로 pivot이 0인 경우다. 소거 과정에서 pivot이 0이 되는 경우에 행 교환이 필요하며 이때 사용되는 행렬이 바로 치환 행렬이다. 이러한 치환은 한 번이 될 수도, 혹은 여러 번이 필요할 수도 있다. 그때 마다 필요한 치환 행렬을 곱해서 행 교환을 해서 소거를 완료하는 것이다.
A=LU Decomposition을 살펴보자. 우선 A=LU의 형태는 아래와 같을 것이다. 지금까지 가졌던 가정은 A는 행 교환이 필요 없는 완벽한 행렬이라는 것이다. 따라서 P행렬도 필요 없었고, 여기서의 P행렬은 단위행렬이 될 것이다. 행 교환이 필요 없기 때문에 단위 행렬을 곱해서 행을 그대로 둔 채 소거를 해 나간다.
여기서 잠깐 실질적인 이야기를 해보자. 그렇다면 실제로 MATLAB과 같은 프로그램에서 이러한 소거 연산을 어떻게 수행할까? MATLAB에선 소거 연산을 수행할 때 우리가 체크하는 것과 같이 pivot이 0인지를 체크한다. 그런데 MATLAB은 여기서 한 가지 더 체크를 하는 것이 있다. 바로 pivot의 값이 충분히 큰지를 검사한다. 만약 pivot값이 0에 가깝다면 수치적으로(numerically) 좋지 않다. 대수적으론 이러한 과정이 필요하지 않지만, 수치 정확도(numerical accuracy)가 좋지 않아서 계산 결과가 좋지 않을 수 있다. 따라서 0에 가까운 pivot이 있을 경우 MATLAB은 행 교환 연산을 수행한다.
어쨋든 A=LU Decomposition을 할 때 행 교환이 필요한 경우 식이 아래와 같이 된다.
여기서 P는 행 교환 연산을 수행하는 치환행렬이고, 위 식은 어떤 invertible A에도 적용이 된다. 사실 대부분의 경우 행 교환이 필요하지 않는데, 가끔씩 행 교환이 필요한 경우 위와 같이 P행렬을 통해 행 교환 및 소거를 수행한다.
지난 포스팅(lecture 4)에서 언급했듯이 P행렬은 단위행렬에서 각 행을 서로 교환한 조합이다. 이를 다시 한 번 상기시키자면 아래 식과 같다.
단위 행렬도 하나의 치환 행렬에 포함되며 P12는 단위 행렬에서 row1과 row2를 교환한 행렬을 뜻한다. 자세한 사항은 lecture 4의 마지막 부분을 참고하자.
이러한 치환 행렬의 조합은 n!(factorial)만큼 된다. 즉 n=3일 때, 3x2x1=6가지 조합이 나올 수 있는 것이다.
치환 행렬은 편리한 속성이 두 가지 있다.
첫 번째는 모든 P행렬은 invertible하다. 즉 역행렬이 존재한다. (역행렬이 존재하는 단위행렬에서 행만 바꿨으므로 당연히...)
두 번째는 P행렬의 역행렬은 전치(Transpose)행렬과 같다. 즉 아래 식을 만족한다. (이 속성은 굉장히 편리하다)
2. Transpose
전치(Transpose)는 지난 포스팅에서도 잠깐 언급했지만, 좀 더 자세히 살펴보도록 하자. 일단 무작정 전치라는 연산을 한 번 해보자. 아래 행렬을 보자.
왼쪽의 3x2 행렬을 전치 했더니 오른쪽의 2x3형태의 행렬이 됐다. 쉽게 생각하면 행렬의 전치는 뒤집기다. 대각선을 축으로 180도 뒤집었다고 생각하면 된다. 그런데 행렬의 차원을 보니 row의 차원이 column차원으로, column의 차원이 row의 차원으로 변한 것을 볼 수 있다. 즉 row와 column이 바뀐 것으로 생각하면 된다. 이에 대한 정의를 아래와 같이 쓸 수 있다.
i는 row의 인덱스, j는 column의 인덱스인데 전치를 하면 이 두 인덱스가 바뀌게 된다. 즉 식 (6)에서 2를 보면 전치를 하기 전엔 A(2,1)이었지만, 전치를 한 후엔 A(1,2)의 자리로 간 것을 볼 수 있다.
3. 대칭 행렬(Symmetric Matrix)
이번에 알아볼 행렬의 형태는 특별한 형태이면서도 어떻게 보면 최고의 행렬 형태라고도 볼 수 있다. 바로 대칭 행렬(Symmetric Matrix)인데, 이 행렬이 가지고 있는 특성 때문에 다양한 곳에 응용된다.
이름 그대로 이 행렬의 특성은 대칭이라는 것이다. 즉 전치(Transpose)를 해서 행렬을 뒤집어도 원래 행렬과 같은 특성을 가진다. 아래 예를 보자.
식(8)의 행렬 A는 대칭 행렬이다. 일단 대각(diagonal) 원소를 보자. 대각 원소는 diag(3, 2, 4)인데, 이 대각 원소를 기준으로 상삼각(Upper triangular)과 하삼각(Lower Triangular) 부분이 같은 것을 알 수 있다. 따라서 전치를 통해 행렬을 대각 원소를 중심축으로 뒤집어도 그 결과는 같으며 차원 또한 변함이 없다.
그렇다면 우리는 이러한 대칭 행렬을 언제, 어떻게 구할 수 있을 까? 식 (6)의 R행렬을 다시 보자.
위의 R행렬은 대칭 행렬과는 거리가 많이 멀어보인다. R의 전치 행렬도 마찬가지다. 둘 다 직사각형 모양이다. 하지만! 우리는 이렇게 대칭 행렬과는 거리가 아주 멀어 보이는 행렬을 가지고 대칭 행렬을 얻을 수 있다. 바로 저 둘을 곱하면 된다. 실제로 한 번 해보자.
R행렬을 R의 전치 행렬과 곱했더니 우측의 S행렬이 나왔다. S행렬을 보면 대각 원소들을 기준으로 대칭인것을 한 눈에 알 수 있다. 이렇듯 어떤 행렬을 자신의 전치 행렬과 곱한 결과가 대칭 행렬이 나오는 이유는 다음과 같다. 자신과 똑같은 행렬을 단지 뒤집어서 곱했기 때문에 똑같은 원소 끼리의 곱이 반복될 수 밖에 없다. 아래의 연산 순서를 보자.
식 (10)은 식 (9)의 곱셈 과정을 순차적으로 나열한 것이다. 이를 보면 두 번째 연산과 네 번째 연산이 같은 원소끼리의 곱이 반복됨을 알 수 있다. 이렇게 같은 원소끼리 반복되는 연산은 대각 원소를 제외한 모든 원소에서 발생한다. 이러한 연산은 결코 우연이 아니라 필연적으로 일어날 수 밖에 없는 것이다. 결론적으로 아래의 정의를 얻을 수 있다.
어떤 임의의 행렬 A와 그의 전치 행렬(Transpose)을 곱하면 항상 대칭 행렬(Symmetric Matrix)을 얻는다!
위 정의를 수식으로 증명하자면 아래와 같다. 어떤 행렬이 대칭 행렬인지를 알기 위해선, 전치를 해 봤을 때 원래의 행렬과 같으면 우리는 이 행렬이 대칭 행렬인지를 알 수 있다.
전치의 전치는? 당연히 원래의 행렬일 것이다. 결과를 보라. 전치를 하기 전의 행렬과 같은 것을 알 수 있다. 위의 중요한 정의를 잘 기억해두자.
3. 마치며
이번 포스팅에선 치환 행렬(Permutation Matrix)과 전치(Transposes), 그리고 대칭 행렬(Symmetric Matrix)에 대해 알아보았다. 치환 행렬은 어떤 행렬의 왼쪽에 곱해져서 행 교환(row exchange)연산을 수행하고 전치는 row와 column의 index를 바꾸는 연산이다. 쉽게 말해 행렬을 대각선을 기준축으로 180도 회전시키는 것이다. 마지막으로 대칭 행렬에 대해 알아보았고, 대칭 행렬은 대각 원소를 기준으로 상삼각행렬과 하삼각행렬의 원소가 같은 행렬이며 전치 행렬이 원래 자기 자신과 같은 행렬임을 알았다. 또한 임의의 rectangular행렬 A에 대해 A의 전치 행렬에 A를 다시 곱하면 항상 대칭 행렬이 나옴을 알 수 있었다. 다음 포스팅에선 벡터 공간(Vector Spaces)에 대해 공부해 보도록 하자.
이번 포스팅에선 A=LU 분해(LU Decomposition)에 대해 알아보겠다. (LU Factorization이라고도 불린다. 그러나 앞으로 LU Decomposition이라 표현하겠다)
쉽게 말해 어떤 행렬 A가 있을 때, 이를 하삼각 행렬(Lower triangular matrix)과 상삼각 행렬(Upper triangular matrix)의 곱으로 분해하여 나타내는 것을 의미한다. A=LU에서 L과 U는 바로 Lower와 Upper의 처음 이니셜만 따서 표현한 것이다.
LU Decomposition은 가우스 소거(Gauss Elimination)에 의한 Elimination 행렬 형태로 볼 수 있으며, 때때로 치환행렬(permutation matrix, ※Lecture 2 참조)을 포함하기도 한다. 컴퓨터는 square 형태의 선형 방정식을 계산할 때 이 LU Decomposition을 사용하며, 역행렬(Inverse Matrix)을 계산하거나 행렬식(determinant)을 계산할 때 필요한 주요 과정이다.
1. 행렬곱셈의 Inverse
LU Decomposition을 알아보기 전에 먼저 행렬곱셈의 Inverse에 대해 잠깐 살펴보고 가도록 하자. LU Decomposition의 이해를 돕기 위함이다.
어떤 행렬 A가 있고 그의 역행렬을 알고 있을 때, 우리는 이 역행렬을 곱하면 단위행렬이 되는 것을 알고 있다. 이때 역행렬을 A의 왼쪽, 혹은 오른쪽에 곱해도 그 결과는 같다.
그렇다면 아래와 같이 non-singular이고 정방행렬(square matrix)인 A와 B가 있다고 가정하자. 이 두 행렬의 곱셈 AB의 뒤에 역행렬을 곱해 단위 행렬(Identity matrix)을 얻고자 할 때, 우리는 빈 칸에 들어갈 역행렬을 어떻게 곱해야 하는가? 식(1)과 같이 역행렬을 순서대로 곱해야 하는가?
정답은 반대의 순서로 역행렬을 곱해줘야 한다. 즉 B의 역행렬을 먼저 곱해주고 그 다음 A의 역행렬을 곱해줘야 한다. 아래 식 (3)-1을 보자. B와 B의 역행렬이 먼저 곱해져서 단위 행렬이 만들어진다. 이때 단위 행렬은 어디에 곱해도 결과는 변하지 않으므로 무시해도 된다. 결국 A와 A의 역행렬과의 곱이 되고 답은 단위행렬이 만들어진다. 식 (3)-2와 같이 순서가 바뀌어도 결과는 마찬가지다.
결국 단위행렬을 만들기위해 역행렬을 곱해줄 때에는 각 행렬의 역행렬이 본래 자신의 행렬과 붙을 수 있게, 즉 원래 행렬 곱셈의 반대 순서로 역행렬을 곱해주면 된다.
- Transpose:
이번엔 행렬 곱셈에 대한 전치(Transpose)에 대해 알아보자. 이후에 더 자세히 다루겠지만 transpose라는 것은 row의 원소들이 column이 되고, column의 원소들이 row의 원소가 되는 것이다. 쉽게 말해 식(4)와 같이 대각선을 중심축으로 행렬을 180도 돌려서 뒤집는 것이다.
그렇다면 행렬 곱셈에 이러한 transpose를 적용하면 어떻게 될까? 아래와 같이 정방행렬인 A와 A의 역행렬을 곱해서 단위 행렬을 만드는 식이 있을 때, 이 식을 transpose시켰다고 했을 때 결과는 식(5)의 마지막 줄과 같이 행렬 곱셈의 순서가 뒤바뀌게 된다.
우변의 I는 그대로 I가 되고 좌변의 A와 A inverse는 곱하는 순서가 반대로 된다.
또한 식(5)의 마지막 줄에서 A의 역행렬의 transpose는 => A의 transpose의 역행렬로 바꿔 쓸 수 있다. 단 이 규칙은 각각의 단일 행렬에 대해서만 적용된다. 식 (6)을 참고하자.
2. LU Decomposition
- What and why Decomposition?:
Decomposition(Factorization)이라는 것은 말 그대로 분해하는 것을 의미한다. 쉽게 말해 어떤 시스템 혹은 데이터를 표현한 행렬 A를 인수분해 한다는 뜻이다. 우리가 중고등학교때 배우던 그 인수분해처럼 말이다. 위키 사전에는 이 행렬 분해(Matrix Decomposition)의 정의를 다음과 같이 정리하였다.
선형대수에서 Matrix Decomposition은 어떤 행렬(Matrix)을 여러 행렬들의 곱으로 표현하는 것을 의미한다.
그렇다면 이러한 Matrix Decomposition은 왜 하는 것일까? 그 해답은 바로 우리가 중학교때 배웠던 인수분해를 하는 이유와 같은 맥락이다. 우리가 어떤 방정식을 인수분해 하는 이유는 바로 그 방정식의 해를 구하기 위해서다. 혹은 해를 좀 더 쉽게 구하기 위해서, 방정식을 좀 더 알아보기 쉽게 하기 위해서, 특수한 상황에서 문제를 풀기 쉽게 하도록 하기 위해서 등이다.
Matrix Decomposition도 마찬가지이다. (http://www.ece.northwestern.edu/~mya671/files/Matrix_YM_.pdf) 에선 Matrix Decomposition의 목적을 크게 두 가지라고 하였다. 첫 번째는 계산의 편리함(computational convenience), 두 번째는 분석적 용이성(analytic simplicity)을 위함이다. 결국 Matrix Decomposition을 하는 이유는 계산을 좀 더 편리하게 하고 어려운 문제를 쉽게 풀기위해, 시스템 행렬을 단순화시켜 표현하여 분석을 용이하게 하기 위함이다.
행렬 분해는 다양한 방법들이 존재한다. SVD(Singular Value Decomposition), QR Decomposition 등등 다양한 방법들이 존재하며, 각 방법들은 각자 고유의 분해 특성들을 가지며 다양한 문제를 푸는데 사용된다. 여기서 우리는 행렬 분해 방법들 중 가장 기본적인 형태인 LU Decomposition에 대해 알아보자.
- LU Decomposition(Factorization):
어떤 행렬 A가 있고 이 행렬은 역행렬을 가질 수 있는 정방행렬이고, 역행렬을 구하기 위해 소거를 하는 과정에서 Row exchange도 필요 없는 아주 좋은 형태의 행렬이 있다고 가정해보자.
우리는 A에 소거법을 적용해서 최종적으로 U행렬을 만드는 것을 지난 포스팅(Lecture 2)에서 배웠다. 여기서 우리는 A와 U사이의 연결 고리를 알아야 한다. 즉 A가 U와 어떻게 연결이 되는지 말이다. 식으로부터 짐작하신 분들도 있겠지만, 바로 L행렬이 이 연결고리가 된다.
이 연결고리인 L행렬이 어떻게 만들어 지는지 실제 계산을 통해 알아보자.
아래와 같이 2x2크기인 비 특이행렬(non-singular Matrix) A가 있다.
자 이제 A행렬을 소거하여 만들어지는 상삼각행렬(Upper Triangular Matrix)인 U행렬을 만들기 위해 E21행렬을 만들어보자. (E21은 A의 row2, column1의 원소인 8을 제거하기 위한 Elementary or Elimination Matrix라는 의미다)
E21행렬은 어떻게 만드는가? 일단 A에서 pivot은 2이다. 이 pivot의 column에서 바로 아래에 있는 원소 8을 제거해야 하는데 바로 위의 pivot인 2와 딱 4배 차이가 난다. 따라서 row1[2 1]에 4를 곱한다음 row2[8 7]에서 row1을 뺀 결과값을 row2에 대입하면 될 것이다. 즉 아래 식과 같다.
그렇다면 이렇게 되기 위해선 E21행렬의 원소들이 어떻게 배치되어야 할까?
pivot이 있는 A의 row1은 그대로 유지되어야 한다. E21의 row1은 그렇다면 1*[2 1] + 0*[8 7]이므로 [1 0]이 되어야 한다.
E21의 row2는 어떻게 되어야 할까? -4*[2 1] + 1*[8 7] 이므로 [-4 1]이 되어야 할 것이다. 결국 식 (9)와 같이 E21이 만들어 질 것이다.
(※소거와 관련된 내용은 Lecture 2참고)
자 이렇게 만들고 보니 처음에 구하고자 했던 A=LU와는 다른 형태지만 어떤 처리를 하면 뭔가 나올 것만 같다. 눈치 채셨는가?
그렇다. 그것은 바로 좌변과 우변의 왼쪽에 E21의 역행렬을 각각 곱해주면 될 것이다. 즉
결국 소거행렬(Elimination Matrix) E21의 역행렬이 L행렬인 것이다. 이때 L은 하삼각행렬(Lower Triangular Matrix)의 형태를 띄게 된다.
이제 E21역행렬을 구하면 된다. E21의 역행렬은? 바로 -4의 부호만 +로 바꿔주면 된다. 역행렬이라는 것이 곱해서 단위행렬을 만들어야 하기 때문이란 것을 안다면 쉽게 유추할 수 있다. 방금 전 E21을 만들 때와 같이 -4를 소거하여 0으로 만들 방법을 생각하면 쉽게 만들 수 있다.
이렇게 구한 E21의 역행렬은 결국 L이 되고 L과 U를 실제로 곱해보면 A가 나오는 것을 확인할 수 있다. 식 (11)은 A=LU를 나타낸 것이다.
- LDU Decomposition:
어떤 경우에 이 Pivot들만 따로 떼어서 분해해야 하고 싶을 때도 있다. U행렬은 대각선으로 두 개의 pivot인 2와 3을 가지고 있다. 첫 번째 pivot이 2, 두 번째 pivot이 3이다. 만약 이 pivot들만 따로 분리하여 행렬을 만들고 싶을 때 우리는 다음과 같이 할 수 있다.
U행렬에서 각 pivot이 속해있는 row를 해당 pivot으로 나누어준다. 그 결과값을 새로운 U의 각 row에 넣고 pivot들만 대각선으로 나열되어 있는 행렬을 써주면 된다. 즉 아래 그림과 같이 하면 된다.
연산 자체가 간단하기 때문에 따로 부연설명은 하지 않겠다.
이렇게 해서 만들어진 행렬의 조합을 우리는 LDU Decomposition Matrix라 한다. 여기서 D는 Diagonal Matrix의 뜻이며 대각선 방향의 원소만 가지고 있는 대각 행렬을 의미한다. 왼쪽엔 하삼각행렬(Lower Triangular Matrix), 가운데는 Pivot들만 있는 대각행렬(Diagonal Matrix), 우측엔 상삼각행렬(Upper Triangular Matrix)이 위치해있는 형태이다.
- 3x3 case:
이제 3x3크기의 3차원 행렬을 생각해보자. 3x3크기의 행렬 A가 있다고 가정해보자. 이 행렬을 소거하기 위해 먼저 곱해야 할 E행렬은 E21일 것이다. 그 다음으로 E31, E32순으로 곱해서 소거를 해야 한다는 것을 이미 배웠다. 이때 Row exchange는 필요 없는 이상적인 경우로 가정한다. 이를 식으로 나타내면 아래와 같을 것이다.
그 다음 단계는 왼쪽의 E행렬들을 없애서 A=의 꼴로 만들어야 한다. 식 (10)을 참고하여 식 (13)의 왼쪽에 E32, E31, E21순으로 역행렬들을 곱하여 아래와 같은 식으로 만들어준다. 결국 식의 우변은 E21*E31*E32의 역행렬들의 곱이 L이 된다.
우리는 식 (13)에 각 E의 역행렬들을 곱하여 식 (14)의 A=LU형태의 식을 만들었다. 즉 행렬 A와 U간의 연결고리인 L을 만들어 낸 것인데, 사실 (13)의 앞에 곱해진 E도 A와 U의 연결고리라고 볼 수 있다. 결국 U를 만들기위한 방법은 E와 L 두 가지가 있는 셈인데, 결론적으로 보면 이 두 가지 방법중 L이 더 좋은 형태라고 볼 수 있다.
다시말하면
의 형태보다
의 형태가 더 좋은 형태이다.
지금부터 왜 두 번째 형태가 더 나은지 설명하겠다.
위에서 살펴봤던 2x2인 경우에는 E행렬이 단 한개라서 별다른 문제는 없다. 그러나 3x3은 다르다. 다음 A행렬을 보자.
Linear Algebra Lecture 2를 참고하여 A 소거법을 적용해보자. 결과는 아래 식 (16)과 같아진다. 여기서 E31은 단위행렬이 되는데, 이렇게 되면 E31은 곱셈에서 무시해도 무방하다. 참고로 소거법의 특성상 E행렬들은 언제나 하삼각행렬의 형태이다. 이렇게 나오는 이유는 소거 과정에서 pivot의 row는 소거하지 않기 때문에 이와 같은 형태가 나오는 것이다.
어쨋든 E행렬을 살펴보자. E32의 -5, E21의 -2는 E행렬에서 각자의 위치에 그대로 위치해있고 E행렬의 row3, column1의 자리에 10이라는 새로운 숫자가 생겨났다. 이것이 의미하는 것이 무엇일까? (-5와 -2는 소거 과정에서 pivot row에 곱해지는 multiplier임을 기억하자.)
그 다음으로 L을 살펴보자. E21 역행렬의 2, E32 역행렬의 5가 L에서 각자 위치에 그대로 위치해 있고 따로 추가되는 숫자는 없다. 이것이 의미하는것이 무엇일까?
행렬 E를 A에 곱하게 되면 E의 10은 A의 row1에 곱해지게 된다. 즉 10이라는 숫자가 A의 row1에 커다란 영향을 미친다는 것이다. 물론 답은 U가 그대로 나오게 된다. 그러나 그 연산 과정에서 A에 뭔가 큰 영향을 미치게 된다.
반면 L의 경우엔 따로 추가되는 숫자 없이 2와 5가 각자의 자리에 위치한 상태로 L이 계산된다. 즉 10과 같이 뭔가 방해를 하는 숫자를 만들어내지 않는다는 것이다. EA=U와 달리 A=LU는 A를 신경쓰지 않아도 되는 것이다. 결국 A와 U의 연결고리로써 E보다는 L이 좀 더 나은 표현이다.
정리하자면..
A=LU Decomposition에서
만약 행 교환(row exchanges)이 없다면, 소거에 사용되는 multiplier들은 L행렬의 각자 위치에 그대로 들어간다.
- Permutations:
지난 포스팅에서 잠깐 다룬적이 있던 치환행렬(Permutation Matrix)을 다시 살펴보자. 지금까지는 행 교환(row exchanges)이 필요 없는 경우를 가정하고 LU Decomposition을 설명했다. 그러나 행 교환이 필요한 경우가 반드시 생긴다. 이렇게 행 교환이 필요한 경우 사용하는 방법이 치환행렬을 곱해주는 것이다.
3x3 치환행렬을 살펴보자.
비록 아무런 변화가 없긴 하지만 단위행렬도 치환행렬의 한 종류이다. n=3인 정방행렬일 때 치환행렬의 종류는 어떤 것들이 있을까?
먼저 P12를 생각해볼 수 있다. P는 Permutation의 P를 따온 것이고 12는 row1와 row2를 교환한다는 뜻이다.
P13, P23을 어렵지않게 생각할 수 있는데, 이것 말고도 조합이 더 있다. 아래 식 (16)을 보자.
P23에 P13을 곱한 행렬, 그리고 P23에 P12를 곱한 행렬을 생각할 수 있다. 각 치환 행렬을 row로 봤을 때, 각 row가 단위 행렬과 비교해서 몇 번째 줄에 위치했는지를 살펴보면 어느 row로 바뀌는지 쉽게 유추할 수 있다.
이러한 치환 행렬의 조합의 개수는 어떻게 계산할 수 있을까? 바로 n!(factorial)로 계산한다. 즉 n=3일 경우, 3x2x1=6가지의 조합이 나오는 것이다.
치환 행렬은 앞서 말했듯 row를 바꿔주는 역할을 하는 것이다. 그렇다면 다시 원래대로 되돌려 놓으려면 어떻게 해야 할까? 바로 역행렬을 곱해주면 되는데, 사실 원래 행렬과 역행렬은 같다. 왜냐하면 P12가 row1과 row2를 바꾸는 치환 행렬일 때 다시 원래대로 돌려 놓으려면 똑같이 row1과 row2를 바꿔주면 되기 때문에 다시 P12를 곱해주면 된다. 실제 계산해봐도 같은 결과가 나오는데, 이는 치환 행렬 자체가 대각 원소들을 기준으로 좌우가 대칭이기 때문이다. 이런 좌우 대칭인 경우 역행렬은 전치(Transpose)로 구할 수 있다.
또한 P13P23은 P12P23과 역행렬 혹은 전치 관계인 것을 알 수 있다.
우리는 행 교환이 필요한 A=LU Decomposition을 할 때 이러한 치환 행렬을 곱하여 PA=LU와 같은 꼴로 Decomposition을 할 수 있다.
3. MATLAB 활용법
LU Decomposition을 MATLAB을 이용해 간단히 구할 수 있다. 아래는 위의 식 (15)를 MATLAB으로 구현한 코드이다.
위 코드를 실행시키면 아래와 같은 결과가 나온다.
위 결과에서 ans는 앞에서 계산한 L과 U를 곱하여 나온 결과 행렬이다. 원래의 A행렬과 똑같이 나오는 것을 볼 수 있다.
MATLAB에서는 LU Decomposition을 위한 함수를 제공한다. 아래 코드는 MATLAB에서 제공하는 함수를 이용해 LU Decomposition을 수행하는 코드이다.
함수 이름은 lu()이고 괄호안에 Decomposition을 할 함수를 파라미터로 넣으면 된다. 이때 좌변에 대괄호를 이용하여 출력 인수들을 정의해 줘야 한다. 첫 번째 방법은 L과 U만 출력 인수로 정의해준 것이다. 이에 대한 결과는 아래와 같다.
결과를 보면 L의 경우 하삼각행렬 형태가 아닐 것이다. 왜 이렇게 나오는지에 대해서 이해하기 위해선 우선 다음의 정의를 이해해야 한다. 선형 시스템(Linear System)의 표현은 유일하지 않다. 아래 식을 보자.
위의 식에서 첫 번째 식과 두 번째 식은 완전히 똑같은 시스템을 표현하고 있다. 여기서 좌변의 행렬의 행이 바뀌면 우변의 결과 벡터도 똑같은 순서로 행이 교환된다는 것을 기억하자.
위의 개념을 생각했을 때, LU Decomposition은 사실 일반적으로PA=LU와 같이 표현할 수 있다. 여기서 P는 치환 행렬(Permutation Matrix)를 의미한다. MATLAB에서 [L U] = lu(A)와 같이 L과 U만 출력인수로 정할 경우, L은 아래 식과 같이 정의 되어 나오는 것이다.
즉 [L U] = lu(A)로 구한 L은 사실은 P'L인 것이다. 이는 L과 U를 곱했을 때 원래의 A행렬 형태가 나오도록 만들기 위해 치환 행렬을 L에 미리 곱해준 것이라 생각하면 된다. ans는 lu()함수로 구한 L과 U를 곱해서 나온 결과이고 원래의 A와 정확히 일치하는 것을 볼 수 있다.
출력 인수를 [L U P] = lu(A)와 같이 L, U, P 세 개로 정의할 경우, L은 우리가 생각하는 하삼각행렬의 형태, 즉 P의 역행렬이 곱해지지 않은 형태로 L이 계산된다. 아래는 이에 대한 결과이다.
L은 하삼각행렬, U는 상삼각행렬, P는 치환행렬이다. 즉 PA=LU형태로 계산 결과가 나오는 것이다. 이렇게 계산된 결과값을 이용해서 PA와 LU를 실제로 비교해보자. 정확히 같은 값이 나오는 것을 알 수 있다.
그런데 우리가 손으로 계산한 결과들과는 실제로 값이 다르다. 이는 내부 계산과정에서 수치적으로 최적화된 계산 알고리즘을 통해 Decomposition을 하기 때문에 알고리즘마다 값이 약간씩 다르게 나올 수 있다. 어쨋든 결과적으로는 맞게 분해가 된 것이 맞다.
MATLAB에서 제공하는 LU Decomposition함수는 이 외에도 다양한 파라미터들을 설정할 수 있다. 자세한 내용이 궁금하다면 구글에 검색을 해보거나 help명령어, 혹은 MATLAB 스크립트의 lu()함수에 마우스 커서를 놓고 Ctrl+D를 누르면 상세한 도움말을 볼 수 있다.
4. 마치며
이번 포스팅에선 어떤 시스템 행렬 A를 L(Lower Triangular Matrix)과 U(Upper Triangular Matrix)로 분해(Decomposition)하는 방법을 배웠다. 이를 통해 A와 U사이의 관계를 이어주는 L행렬을 정의할 수 있었고 L과 소거 행렬 E와의 관계를 확인할 수 있었다. 또한 Row exchange가 필요한 경우 사용되는 치환행렬(Permutation Matrix)을 공부했고 이에 대한 전치(Transpose)도 공부하였다. 다음 포스팅에선 이 치환 행렬과 전치에 대해 좀 더 알아보도록 하자.
비록 디지털 영상처리라는 학문이 수학과 확률론적 이론을 토대로 만들어 졌지만, 그 근간에는 인간의 직관과 분석력, 그리고 인지 매커니즘이 있다. 그러므로 인간의 시각적 인지 방법을 이해하는 것은 중요하다. 하지만 이 주제는 굉장히 방대하고 복잡하여 모든 부분을 다룰 순 없다. 따라서 이번 포스팅에선 이미지가 어떻게 형성이 되고 이를 인간이 어떻게 인지하는지에 대한 매커니즘을 공부해 보도록하자. 또한 인간의 시각 및 인지력의 물리적 한계를 디지털 영상처리와 관련하여 이해해보도록 하자.
1. 인간 눈의 구조(Structure of Human Eye)
잠시 해부학 공부를 해보자. 아래 그림은 인간의 눈의 단면을 나타낸 것이다. 모양은 구체에 가깝고 평균 지름은 대략 20mm정도이다. 총 3개의 막이 눈을 에워싸고 있는데, 각막(cornea)과 공막(sclera)이 외부를 감싸고, 맥락막(choroid) 그리고 망막(retina)순으로 위치해 있다.
각막은 앞쪽의 표면을 덮는 거칠고 투명한 조직이다. 각막과 이어져 눈의 나머지 전체를 덮고 있는 공막은 불투명한 막이다. 맥락막은 공막 바로 아래에 위치해 있으며, 눈에 영양분을 공급하는 혈관 조직을 가지고 있다. 이 맥락막은 아무리 작은 상처라도 눈에 혈액공급을 원할하게 하지 못하는 염증(inflammation)을 일으켜 눈에 손상을 입힐 수 있다. 맥락막은 두꺼운 색소층을 가지고 있어 관련없는 빛이 눈에 들어오는 것을 줄여주고 눈 안쪽 전체로 후방산란(backscatter)시킨다.
이 막의 앞쪽 끝단에서 맥락막은 모양체(ciliary body)와 홍채(Iris)로 나뉜다. 홍채는 눈으로 들어오는 빛의 양을 늘리거나 줄이는 조절 기능을 한다. 홍채의 개방(동공: pupil) 정도는 대략 지름 2~8mm 범위에서 열리고 닫힌다. 홍채의 앞쪽 부분은 색소층을 가지고 있고 뒤쪽은 검은 색소를 띄고 있다.
렌즈(lens)는 섬유세포(fibrous cell)들이 동심원을 이루어 여러층으로 이루어져 있으며 섬유질에 의해 모양체에 붙어있다. 60~70%의 물, 6% 정도의 지방, 그리고 눈의 다른 조직들에 비해 보다 많은 단백질로 구성되어 있다. 렌즈는 약간 노란색을 띄고 있으며 나이가 들 수록 노란 색소가 증가한다. 극단적인경우 백내장(cataract)에 의한 렌즈 혼탁이 와서 색깔 구분 능력을 떨어트리고 시야를 흐리게 만든다. 렌즈는 가시광선 스펙트럼 영역의 약 8%를 흡수하며 짧은 파장(wavelength)에서 상대적으로 높은 흡수율을 보인다. 적외선과 자외선 모두 렌즈 구조 내의 단백질에 의해 상당량 흡수 되며, 과도할 경우 눈에 손상을 입히게 된다.
눈의 가장 안쪽에 존재하는 막은 망막(retina)으로써 안쪽 벽 전체를 차지하고 있다. 눈의 초점이 적절하게 맞을 경우, 외부 사물의 빛이 망막에 맺혀 이미지를 형성하게 된다. 망막의 표면엔 빛의 수용기(light receptor)가 다수 분포해 있어 패턴화된 시각(pattern vision)을 만들어 낼 수 있다. 눈의 망막에는 추상체(cones)와 간상체(rods)로 알려진 두 가지 종류의 빛 수용체가 있다.
추상체는 대략 600~700만개가 존재하며 주로 와(fovea)로 불리는 망막의 중심부에 위치해 있다. 추상체는 색깔에 굉장히 민감하며 인간은 주로 이 추상체를 이용하여 상세한 부분을 처리할 수 있다. 이는 각 추상체가 고유의 신경 말단에 연결되어 있기 때문이다.
눈의 근육들은 눈의 회전눈의 회전을 제어하며 관심영역의 물체가 와(fovea)에 오도록 한다. cone vision을 명소시(photopic or bright-light vision)라고도 부른다.
간상체(rods)의 수는 추상체에 비해 훨씬 많으며 7,500만개 ~ 1억 5천만개가 망막 표면에 분포해 있다. 간상체의 넓은 분포와 몇 개의 간상체가 하나의 신경 말단에 연결되어 있기 때문에 디테일한 부분의 처리 보다는 전체적인 이미지를 인식하는데 사용된다. 간상체는 색상 인지나 처리에는 관여하지 않고 저 조도에 민감하다. 예를 들어 햇빛에서는 다양한 밝은 색상으로 보였던 물체가 달빛 아래에서는 색깔이 없는 물체로 보이는 현상이 있는데, 이는 오직 저조도에 민감한 간상체만 자극받기 때문이다. 이러한 현상을 암소시(scotopic or dim-light vision)라 한다.
아래 그림은 눈에서 시신경이 출현하는 지역에서 추상체와 간상체들의 밀도를 그래프로 나타낸 것이다.
(cones: 추상체, Rods: 간상체)
그래프를 보면 아예 없는 부분이 있는데 이를 blind spot이라 한다. 이 부분을 제외하곤 수용기들의 분포는 와(fovea)를 중심으로 반지름 방향으로 대칭이다. 수용기 분포는 fovea로부터 각도 단위로(degree)측정되었다. 그래프를 보면 추상체는 망막의 중심부인 와에서 가장 밀도가 높다. 간상체는 중심부로부터 약 20도 까지는 증가하다가 Blind spot을 제외하곤 바깥으로 갈 수록 줄어드는 경향을 보인다.
와(fovea)는 망막에 있는 지름 1.5mm정도의 원형 자국이다. 하지만 앞으로는 이를 정사각형, 혹은 사각형 형태의 센서 배열(sensor array)로 간주하고 설명할 것이다. 그 편이 더 이해하기 쉽고 유용하다. 우리는 앞으로 이 와(fovea)를 1.5mm x 1.5mm 크기의 센서 배열로 생각하자. 추상체의 밀도는 망막의 중심부에서 대략 150,000/mm^2 이다. 이러한 수치를 기반으로 추정해 봤을 때 눈에서 가장 예민한 부분의 추상체의 개수는 약 337,000개 이다.
이러한 원시분해능 측면에서 보면 CCD(Charge-Coupled Device) imaging chip의 센서 개수는 중간 정도의 분해능 성능의 경우 5mm x 5mm 크기에서 이 정도가 된다. 디지털 영상 처리를 위한 이미지 센서등은 결국 인간의 시각 장치의 매커니즘을 분석하여 만들어진 것이다.
2. 눈에서의 이미지 형성(Image Formation in the Eye)
일반적인 카메라의 경우 focal length(렌즈와 Image plane사이의 거리)는 고정되어 있다. 우리가 focusing이라고 부르는 것은 바로 이 Image plane(film 혹은 Digital Camera의 경우 imaging chip)과 렌즈사이의 거리를 맞추는 것이고, 물체와 카메라로부터의 거리에 따라 우리는 이 focus를 맞추어 선명한 물체 영상을 얻는 것이다.
인간의 눈의 경우엔 정 반대이다. 렌즈와 상이 맺히는 영역(imaging region, retina)은 고정되어 있고, focus를 맞추기 위한 작업은 렌즈의 모양을 변형시켜 맞추게 된다. 이때 모양체(ciliary body)에 있는 섬유질(fibers)이 렌즈의 모양을 평평하게 혹은 두껍게 변형시켜 멀거나 가까운 물체를 잘 볼 수 있도록 한다. 아래 그림은 우리 눈에 사물이 어떻게 투영되는지를 아주 간단하게 나타낸 그림이다.
위 그림에서 C는 초점이 모아지는 렌즈의 중심점(optical center of the lens)이고, 이 렌즈의 중심점으로부터 상이 맺히는 망막까지의 거리는 대략 14~17mm정도이다. h는 외부의 이미지가 망막에 형성되었을 때 그 크기를 나타낸 것이다.
다음과 같은 가정을 해보자. 어떤 사람이 100m 떨어져 있는 15m크기의 나무를 바라본다고 가정해보자. 이때 눈의 망막에 맺힌 나무의 크기는 얼마가 될 것인가? 결국 h를 알아내는 문제이다. 우리는 이 문제를 비례식을 이용해서 풀 수 있다. 렌즈 중심점 C를 중심으로 이미지가 맺히는 망막까지의 거리(focal length)를 17mm, 사물까지의 거리를 100m, 사물의 크기를 15m라고 하자. 이를 간단히 비례식으로 나타내면 15:100=h:0.017이다. 0.017은 mm를 m단위로 바꾸어 써준 것이다. 계산해보면 h는 2.55mm가 나오는 것을 알 수 있다.
앞서 언급했듯이 이미지는 가장 먼저 와(fovea)에 맺히게 된다. 인지 과정은 빛 수용체의 상대적 전기 자극에 의해 일어나는데, 복사에너지(radiant energy)를 전기적 임펄스 신호로 과정이 먼저 이루어지고 이러한 전기 신호들은 최종적으로 뇌에 전달되어 그 의미를 해석하게 된다.
3. 밝기 적응과 식별력(Brightness Adaptation and Discrimination)
디지털 이미지는 이산적인 밝기 값들로 표현이 되기 때문에, 서로 다른 밝기 값을 구별해내는 눈의 능력은 영상 처리 결과를 표현하는데에 있어 고려할만한 요소이다. 인간이 적응할 수 있는 밝기 변화는 생각보다 엄청난데, 암소시 한계점(scotopic threshold)에서부터 대략 10의 10승 정도의 밝기 범위를 구분이 가능하다. 다시 말하면 가장 어두운 밝기에서 가장 밝은 단계를 부분할 수 있는 범위가 10의 10승이라는 소리다.
실제 실험에 의해 검증된 인간의 시각 시스템에 의해 인지된 밝기, 일명 주관적 밝기(subjective brightness)는 로그 함수로 나타낼 수 있다. 아래 그림은 이에 대한 결과 그래프이며 빛의 실제 세기에 대해 인간이 인지한 주관적인 밝기의 정도(subjective brightness)를 나타낸 것이다.
그래프에서 암소시(scotopic) 부분을 보면 로그 함수 그래프와 같은 형태를 보이는 것을 알 수 있다. 즉 실제 밝기 변화가 많이 일어났다고 하더라도 인간은 그것을 실제보다 더 작은 변화로 인지한다는 뜻이다. 다음으로 명소시(photopic)부분을 살펴보자. 명소시 부분만 놓고 봤을 때, 범위는 약 10의 6승 정도이다. 암소시에서 명소시로의 전환은 점차적으로 이루어지는데, 범위는 대략 0.001 ~ 0.1 mililambert(log scale로는 -3 ~ -1 mL이다)이고 두 개의 curve가 겹치는 부분이 이 변환 부분이다.
여기서 한 가지 눈여겨 봐야 하는 것은 인간의 시각 시스템은 이렇게 동적으로 변환되는 범위에서 동시에 작동하지 않는다는 것이다. 오히려 전체 감각을 변화시켜 이러한 큰 변환을 달성한다. 즉 어두운 상황에서 암소시 시스템이 작동하다가 점점 밝아져서 명소시 시스템이 겹쳐서 발생하는 상황이 오면 그때는 명소시 시스템이 작동하게 된다. 이를 밝기 적응(brightness adaptation)이라 한다. 또한 어떤 주어진 조건하에서 시각 시스템의 현재의 감각 단계를 밝기 적응 단계(brightness adaptation level)라 한다.
특정 적응 단계에서 밝기 강도가 변하는 것을 구분하는 눈의 능력 또한 중요한 것 중 하나이다. 이에 대한 전형적인 실험이 있다. 다음을 상상해보자. 피험자가 평평하고 똑같은 밝기로 발광하는 어떤 패널을 바라보는 것이다. 이 영역은 피험자의 시야(field of view)를 전부 커버할 정도로 충분히 크고, 재질은 불투명한 유리로 되어있으며 유리의 뒤쪽에서 밝기$I$의 크기로 빛을 변화시켜가며 비춘다. 여기에 기존 밝기 대비 변화량인 $\Delta I$가 짧은 순간동안 패널의 중심부에 원형 형태로 나타난다. 아래 그림은 이 실험에서 패널 부분을 나타낸 것이다.
$\Delta I$가 작으면 피험자들은 밝기 변화를 인지하지 못하고, $\Delta I$가 커질 수록 피험자들은 밝기 변화를 감지하게 된다. 이렇게 변화를 감지하기 위해선 기존의 밝기 값 $I$로 부터의 변화량 $\Delta I$가 충분히 커야하는데, 이를 weber ratio라고 한다. 쉽게 말해 10cm의 막대가 있는데, 10.01cm로 길이가 늘었을 때 막대의 길이가 변화했다는 것을 알아차리기는 매우 어려울 것이다. 그렇다면 원래 길이 대비 얼마만큼 늘어야 길이 변화가 감지되는지를 알아내는 것이 weber ratio의 목적이다.
${\Delta I \over I}$ 값이 작으면 작은 변화량이 요구되고, 반대로 값이 크면 큰 변화량이 요구되는 것이다. 아래 그림은 밝기 값 $I$에 대한 weber ratio의 그래프를 log scale로 그린 것이다. 어두울수록 weber ratio값이 크고 밝아질수록 그 값이 작다. 이 말은 어두울 땐 밝기 변화를 알아차리기 어렵고 밝을 수록 상대적으로 쉽다는 것이다. 그래프가 두 개인 것은 어두울 때는 rods에 의해(암소시), 밝을 때는 cones에 의해(명소시) 밝기 변화를 인지한다는 것이다.
밝기 인지에 대한 약간 다른 얘기를 해보자. 다음의 두 가지 현상은 밝기 인식이 단순히 밝기에 대한 함수가 아님을 증면한다. 첫 번재는 인간의 시각 시스템이 밝기가 다른 경계면 부분에서 undershoot 혹은 overshoot가 일어난다는 것이다. 아래 그림에서 세 번째의 perceived intensity부분에서 보면 이러한 현상이 나타나있다. 경계선 부분의 밝기는 상수이지만 이러한 경계면 부분에서 우리 눈은 이를 좀 더 강력하게 자르는 것을 알 수 있다. 이렇게 외견상으로 잘린 것 같이 보이는 부분을 Mach bands라 한다. 1865년에 Ernst Mach가 처음 정의하였다.
두 번째 현상은 simultaneous contrast라고 불리는 현상인데, 이는 사람이 감지하는 밝기가 단순히 해당 영역의 밝기값으로만 인지되는 것이 아님을 나타낸다. 아래 그림을 보면 모든 사각형의 안쪽 면은 같은 밝기 값을 가지고 있다. 그러나 주변 영역이 어두울수록 안쪽 사각형은 더 밝게 보인다.
이러한 우리 눈의 착시(optical illusion)현상을 나타내는 그림이 몇 가지 더 있는데, 바로 우리 눈이 존재하지 않는 정보를 만들어 내거나 실제와는 다르게 기하학적 정보를 잘못 인지하는 경우다. 아래 그림에서 (a)는 실제 line은 없지만 중심부에 사각형이 있는 것처럼 보인다. (b)도 역시 가운데에 원이 보이는 것 같은 착각을 일으킨다. (c)에 그려진 두 개의 선은 실제로는 같은 길이지만, 양쪽 끝에 그려진 화살표 모양으로 인해 아래쪽 선이 더 길어보인다. (d)의 경우 모두 45도의 평행한 선이지만 주변에 그려진 작은 선들로 인해 다른 각도처럼 보인다.
이러한 착시현상은 인간의 시각 시스템의 특성이며 아직 완벽히 이해된 영역은 아니다. 이처럼 인간의 시각 시스템은 아직까지 일부만 알려져 있으며 아직 더 연구해야 할 부분들이 많이 남아있다.
지난 강의에서 행렬 곱셈(Matrix multiplication)에 대해서 다루었다. 이번 강의에서는 행렬 곱셈과 그 규칙에대해 좀 더 알아보고
역행렬과 Gauss-Jordan이 제안한 소거법을 이용해 역행렬을 구하는 방법에 대해 알아보도록 하자.
1. 행렬 곱셈(Matrix multiplication)
- row*column:
이번 section에선 행렬 곱셈을 총 네 가지 관점에서 살펴볼 것이다. 먼저 살펴볼 것은 row*column의 방법이다.
아래 두 개의 행렬이 어떻게 곱해지는지를 살펴보자. 행렬 A와 B가 있고 곱해진 결과를 C라고 해보자.
C에서 c32, 즉 C에서 row3, column2에 존재하는 원소는 어디로부터 어떻게 만들어지는가?
바로 행렬 A의 row3과 행렬 B의 column 2와의 곱으로부터 만들어진다. 이 곱을 우리는 A의 row3와 B의 column2의 벡터의 내적(dot product)이라고 볼 수 있다. 이 dot product 과정을 다시 써보면 식(2)와 같다.
A의 row3의 첫 번째 원소 a31은 B의 column2의 첫 번째 원소 b12와 곱해진다. 이 값은 두 번째 원소들 a32와 b22의 곱의 값에 더해진다. 이렇게 n개의 각 원소까지 곱하고 더하는 과정을 거쳐 c32값이 계산되어진다. 이를 일반적인 형태로 작성하게 되면 식 (2)의 세 번째 줄과 같아진다.
그렇다면 C의 모양은 어떻게 될까? 만약 A와 B 둘다 정방행렬(square matrix)인 경우 row와 column의 수가 같기 때문에 결과 행렬인 C도 같은 모양을 취하게 된다.
그러나 A가 3x4(row3, column4)인 반면 보다시피 B는 4x3로 모양이 다르다. 그런데 C의 모양은 3x3인 정방행렬이다. 어떻게 이러한 결과가 나온 것일까?
식 (1)을 보자. 곱해지는 두 행렬 중 앞쪽에 위치한 행렬은 m x n이 되어야 하고 그 다음 행렬은 n x p가 되어야 한다. 이때 곱의 결과 모양은? m (rows of A) x p (columns of B) 가 된다. 결국 행렬 C는 A의 m=3, B의 p=4에 의해 3x4로 된 것이다.
또한 어떤 행렬 둘을 곱한다고 했을 때, n의 크기는 반드시 같아야 한다.
지금까지 살펴본 내용은 행렬 곱셈을 하는 가장 일반 적인 방법이다. 고등학교때 배웠던 행렬의 연산은 대부분 이 방식을 배웠을 것이다. 똑같은 연산을 좀 더 다른 관점에서 살펴보도록하자. 전체 row혹은 column-wise의 꼴로 행렬 곱셈을 살펴보는 관점에서 말이다.
AB=C를 다시 한 번 써보자.
- column-wise:
A와 B의 곱을 column의 관점에서 살펴보도록 하자. 행렬 A가 B의 각 column 별로 곱해진다고 생각해 봤을 때, 즉 행렬 A 전체와 B의 각 column 벡터와의 곱으로 생각해 봤을 때 이 곱셈의 결과는 C의 column이 된다. 식 (3)에서 행렬 A와 B의 청록색 column을 곱하면 그 결과는 C의 청록색 column이 되고, 행렬 A와 B의 두 번째 column인 녹색 부분을 곱하면 C의 두 번째 column인 녹색이 되는 것이다. 이를 식으로 나타내면 (4)와 같다. 이것이 위 식을 column별로 보는 것이다.
이것이 말하는 것이 무엇일까? 이는 바로 C의 column들은 A의 column들의 조합이라는 것이다. (개념이 조금 헷갈리시는 분들은 Lecture2의 식(14)를 참조하면 이해가 갈 것이다!) 이는 C의 각 column의 벡터 길이(=m)가 A의 column의 벡터 길이(=m)와 같음을 봐도 알 수 있다.
- row-wise:
이번엔 똑같은 행렬을 row의 조합 관점에서 살펴보자. 식 (5)를 살펴보면 C의 row3는 A의 row3와 행렬 B와의 곱으로 나타내어진다.
이를 마찬가지로 식으로 나타내면 식 (6)과 같다.
column-wise와 비교해보면 column일 때는 행렬 A와 B의 column의 곱으로, row-wise일 때는 A의 row와 B와의 곱으로 C의 column과 row가 각각 정의되었다. row-wise를 다시 정의한다면 C의 row들은 B의 row들의 조합이다.
즉 식(5)의 경우에서 a31*B(row1) + a32*B(row2) + ... 와 같은식으로 B의 모든 row마다 A의 row3의 각 원소들이 계수처럼 곱해져서 C의 row3이 만들어지는 것이다. (역시 개념이 헷갈린다면 Lecture2의 식(17)참조!)
- column*row:
네 번째로 살펴볼 것은 column벡터와 row벡터의 곱셈 형태이다.
맨 처음에 살펴봤던 형태(row*column)와 그 순서가 반대이다. row*column형태에서는 곱셈의 결과가 단 하나의 값(scalar)으로 나왔으며 이는 내적(dot-product)라 하였다. 그렇다면 그 반대는 어떻게 될 것인가? 분명히 row*column의 결과와는 다를 것이다. 다음을 보자.
위에서 예를 들었던 AB=C에서 A의 column은 어떤 모양을 갖는가?바로 m개의 row원소가 1개의 column을 이루는 모양이다.
B의 row는 반대로 p개의 column원소가 1개의 row를 이루는 모양이다.
그렇다면 이들의 곱셈 결과는 어떤 모양이 될 것인가? 결론부터 말하자면 하나의 full size의 큰 행렬이 만들어진다. 아래의 예를 가지고 실제로 계산을 해보자. A는 3x1의 column 벡터이고 B는 1x2의 row벡터이다. 결과는 오른쪽과 같이 만들어지는데, 어떻게 이런 결과가 나오는 것인가?
앞서 배웠던 row-wise와 column-wise를 생각해보면 쉽게 계산할 수 있다.
row-wise인 경우...
a11*B(row1)=[2 12],
a21*B(row2)=[3 18],
a31*B(row3)=[4 24]
와 같이 계산된다.
column-wise인 경우...
A(col1)*b11=[2 3 4]T, (T는 transpose를 의미)
A(col1)*b12=[12 18 24]T
와 같이 계산된다.
네 번째 방법을 다시 정리하자면.. 행렬곱셈 AB는 A의 column * B의 row의 합이다.
좀 더 일반적인 예를 들어보면 두 개의 column과 두 개의 row인 경우를 들 수 있다. 이 경우 A의 col1과 B의 row1, A의 col2와 B의 row2의 합으로 나타낼 수 있다. 두 번째 텀은 0과 곱해지기 때문에 무시하고 결과는 식(8)과 같다.
여기서 한 가지 짚고 넘어가야 할 부분이 있다. 식 (8)을 다시 보자.
위 곱셈의 결과 행렬 C는 굉장히 특별한 행렬이다. 혹시 무엇인가 보이는가? 그 특별한 점은 바로
C의 모든 row는 B의 row를 따라 같은 line 선상에 존재한다.
C의 모든 column은 A의 column를 따라 같은 line 선상에 존재한다.
결국 식(8)의 결과 행렬은 rank가 1인 행렬이다. (rank는 이후 포스팅에서 다룰 예정: linearly independent한 row or column의 수)
위 행렬이 진짜로 같은 라인에 존재하는지 구현해보자. 아래는 MATLAB으로 해당 row 벡터들을 시각화한 결과이다. 세 벡터들이 같은 선상에 존재하기 때문에 앞에서 그려졌던 벡터들은 이후에 그려진 벡터들에의해 가려져 보이지 않음을 알 수 있다.
아래 결과 사진은 column벡터를 그린 것이다. 역시 처음 그려진 벡터가 겹쳐서 보이지 않음을 알 수 있다. 실제로 코드를 돌려서 돌려보며 확인해 보도록하자.
**결국 어떠한 벡터이던간에 column*row인 경우 위와 같은 특별한 행렬이 만들어지게 된다. 이를 잘 기억해 놓자.
아래는 구현 코드이다.
Row 출력 코드
Column 출력 코드
- Block Multiplication:
행렬 곱셈의 형태 중 마지막으로 살펴볼 것은 블록(Block)단위의 행렬 곱셈 방법이다. 예를 들어 20x20크기의 행렬이 있다고 가정했을 때, 이를 10x10 네 개로 분할하여 똑같이 행렬 곱셈을 적용해도 같은 결과가 나온다. 아래 행렬을 보자.
행렬 A는 20x20의 크기를 가지고 있고 이 행렬들을 10x10 크기의 Block으로 나눈다. 이때 각 Block(A1, B1....)을 하나의 원소로 생각하고 행렬 연산을 해주면 기존 행렬 연산과 똑같은 결과가 나오게 된다. 예를 들면 아래와 같은 연산을 참고하면 쉽게 이해할 수 있다.
2. 역행렬(Inverse Matrix)
- Invertible, nonsingular case:
이제 역행렬을 계산하는 법을 살펴보겠다. 우선 정방행렬(square matrices)에 대해 생각해보자. 어떤 정방 행렬 A가 있다고 생각했을 때, 이 행렬의 역행렬이 존재(invertible, nonsingular)한다고 가정하자. (역행렬은 존재할수도, 존재하지 않을 수도 있다)
이때의 관계를 아래와 같이 쓸 수 있다. 행렬 A에 역행렬을 곱해주면 그 결과는 단위행렬(identity matrix)이 된다. 또한 이 역행렬을 오른쪽에 곱해줘도 결과는 같다.
행렬은 곱셈의 순서에 따라 결과가 달라진다는 것은 이미 알고 있을 것이다. 따라서 역행렬을 앞에 곱하는 결과와 뒤에 곱하는 결과는 당연히 달라질 것이라고 생각하는데, 일반적인 행렬(Rectangular Matrix)인 경우에는 이것이 맞다. 하지만 정방행렬(Square Matrix)인 경우에는 식(12)와 같이 앞에 곱하나 뒤에 곱하나 그 결과가 같다. MATLAB에서 inv() 명령어로 확인해보면 바로 알 수 있다.
- no inverse, singular case
이번엔 역행렬이 존재하지 않는 경우를 살펴보자. 이를 다른 말로 특이행렬(singular matrix)라고도 한다. 아래의 행렬 A를 보자. 아래 행렬 A는 역행렬이 존재하지 않는 특이행렬이다. 그렇다면 왜 역행렬이 존재하지 않는 것일까?
우리는 위 행렬 A의 역행렬이 존재하지 않는 다양한 이유를 찾을 수 있다. 어떤 것들이 있을까?
이후 포스팅에서 따로 다루겠지만, 먼저 행렬 A의 행렬식(determinant)은 0이 된다(1/(ad-bc)). 따라서 역행렬이 존재하지 않는다.
이것 보다는 좀 더 좋은 이유가 필요하다. 또 다른 이유는 뭐가 있을까? 행렬 A의 column picture를 살펴보자. 혹시 무엇이 보이는가? 이전 포스팅을 잘 공부한 분이라면 행렬 A의 각 column들이 같은 line상에 위치한다는 것을 알 수 있다. 즉 두 column은 똑같은 방향을 가르키고 있는 것이다.
A의 rank는 1이며 선형 독립(linearly independent)인 차원의 개수가 A의 차원보다 작기때문에 특이행렬이다. 따라서 행렬 A로는 2차원이 아닌 오직 line만 표현이 가능하다. A의 column 1인 [1 2]T벡터에 상수 3을 곱해주면 바로 column 2인 [3 6]T벡터가 나오는 것을 확인하면 알 수 있다. row도 마찬가지다.
이를 확인할 수 있는 또 다른 방법은 각 column을 정규화(normalization)해서 같은지 비교해 보는 것이다. A의 column 벡터들의 2-norm 정규화식 (14)를 실제 계산해서 확인해보기 바란다.
그런데 또 다른 이유가 있다. 이것이 가장 중요한 이유인데, 잘 기억해두도록 하자. 그것은 바로..
**만약 를 만족하는 벡터 x를 찾을 수 있다면, 그 행렬은 역행렬이 존재하지 않는다. (이때 A는 정방행렬, x는 0이 아닌 벡터)**
다시 말하면, 당신이 어떤 정방행렬 A에 대해서 그 행렬에 어떤 0이 아닌 벡터 x를 곱했을 때 우변이 0벡터가 된다면 그 행렬은 역행렬을 만들 수 없다(not invertible, singular case).
식(13)의 행렬 A는 우변을 영벡터로 만들 수 있는 x가 존재하는가? x=[3 -1]T 를 곱하면 우변이 영벡터가 된다.
자 이를 다시 생각해보자.
시스템 A가 어떤 벡터 x를 0으로 보냈다. 이럴 경우, 이렇게 0으로 보낸 x를 다시 원래의 위치로 돌아오게끔 하는 시스템이 존재하는가?를 생각해보자. 선형대수에서의 연산은 선형 결합, 즉 변수에 어떤 계수들을 곱하고 더해서 계산 되는 것인데, 애초에 변수 자체가 0이 되어버렸으면 어떤 계수들을 곱해도 이를 복원시킬 방법이 없는 것이다.
위 시스템 A의 경우 2차원 상의 벡터인 x를 곱할 경우 이를 1차원 상의 공간으로 보내버린다. 게다가 0으로 만들어버리는 경우도 있는 것이다. 이런 상황에서 원래 지점으로 되돌리는 역행렬이 존재한다는 것이 말이 될 것인가? 선형 시스템을 다루는 선형 대수에서는 어불성설(語不成說)이다.
위의 개념을 잘 이해하기를 바란다.
(※ 정방행렬이 아닌 임의의 직사각 행렬(Rectangular Matrix)은 pseudo inverse라는 방법을 이용해 계산해야 한다. 이와 관련해서는 이후 포스팅에서 다룰 예정)
- Gauss-Jordan idea
이제 다시 돌아가서 역행렬이 존재하는 경우를 살펴보자. 행렬 A를 다시 아래와 같이 정의하자.
식 (15)의 행렬 A에 대해 위에서 다룬 역행렬이 존재하지 않는 경우에 대한 방법들을 적용해보자. 행렬식(determinant)은 0이 아니고, 각 column들은 서로 다른 방향을 가리키고 있다. 또한 Ax=0를 만족하는 x를 찾을 수 없다.
자 이제 A가 역행렬을 가질 수 있음을 알았다. 그럼 이제 실제로 어떻게 역행렬을 구할 수 있을까? 행렬 A에 역행렬을 곱하면 그 결과는 단위행렬 I가 되어야한다. 아래 식을 보자.
위 식을 식(13)처럼 두 개의 column-wise 시스템으로 분리해서 생각해보자. A와 첫 번째 column인 [a b]T를 곱하면 I의 첫 번째 column인 [1 0]T이 되어야 한다. 마찬가지로 A*[c d]T = [0 1]T 이다. 이러한 관계를 정리하면 행렬 A와 그 역행렬의 j번째 column을 곱하면 I의 j번째 column이 나온다.
식 (16)을 다시 써보면...
위와 같이 하나의 식을 두 개로 분리해서 생각할 수 있다. (18-1)과 (18-2)를 풀 수 있다면 행렬 A는 역행렬이 존재한다. 이것이 Jordan's idea의 시작이다.
지난 Lecture 2에서 Gauss소거법을 배웠다. 소거법 과정에서 우변의 extra column 벡터를 오른쪽에 붙여서 만든 Augmented Matrix를 기억하는가? 이때 우리는 우변의 extra column 벡터 하나만 붙였다. 하지만 여기에 column을 하나 더 붙여서 아래 형태의 행렬을 만들어보자. 즉 (18-1), (18-2)를 붙여서 한 번에 풀어보자는 것이다.
식 (19-1)를 지난 포스팅에서 배운 Gauss소거법을 활용해 소거해보자. 첫 번째 pivot을 설정하고 아래에 있는 원소들을 소거하기 위한 E 행렬을 만들어 곱해주자. 소거할 원소가 A의 row2, col1이므로 E21이다. row1에 -2를 곱해주고 row2에서 빼주면 소거 되므로 식은 아래와 같다. (Elimination matrix를 만들 땐 row-wise로 생각하면 쉽다)
식 (19-2)의 A의 결과는 상삼각행렬(upper triangular matrix)이 완성되었다. Gauss는 여기서 끝냈다. 하지만 Jordan은 여기서 소거를 더 진행했다. 지금까지 위에서 아래쪽으로 소거를 해 왔다면 이젠 반대로 아래에서 위쪽으로 소거를 진행하는 것이다. 즉 (19-2)에서 두 번째 pivot을 잡았는데 여기서 진행방향을 위쪽으로 잡는 것이다. 이렇게 되면 A의 row1, col2의 원소인 3을 제거한다. 이때 E행렬은 E12가 되며 현재 pivot에 3을 곱하고 row1에서 빼주면된다. 정리하면 아래 식과 같이 된다.
식 (19-3)의 결과를 보면 원래 A가 있던 곳은 단위행렬로, 원래 단위행렬이 있던 곳은 어떤 행렬이 되었다. 이 어떤 행렬은 바로 A의 역행렬이다. 검증을 위해 여기에 A를 곱해보면 단위행렬이 나오는 것을 확인할 수 있다.
어떤 행렬을 소거 하기 위해선 단계별로 제거 행렬(Elimination matrix)을 곱해줘야 한다. 위 예에선 E21과 E12가 그 예인데, 이 둘을 곱해주면 최종적인 E 행렬이 완성된다. 어떤 결과가 나오는지 살펴보자.
E행렬을 원래의 A 행렬에 곱해보자. 어떤 결과가 나오는가?
결국 E행렬은 A의 역행렬이다.
3. 마치며...
이번 포스팅에선 행렬 곱셈(Matrix multiplication)과 역행렬(Inverse matrix)을 계산하는 방법을 배웠다. 행렬 곱셈에선 row*column, column-wise, row-wise, column*row의 네 가지 연산 방법을 살펴보았으며 각각의 특성과 그 의미를 파악하였다.
역행렬에선 역행렬이 존재하는 경우와 존재하지 않는 경우를 살펴보았고 Gauss-Jordan의 소거법을 통해 실제로 역행렬을 계산하는 방법을 배웠다.
