Learn Again! 러너게인

지난 Lecture 1에선 선형 시스템에 관한 식을 만들고 이를 Row와 Column picture 두 가지 방법으로 해석해 보았다. 

이번 시간에 배울 내용은 시스템 A의 해를 구하기 위한 방법들을 배울 것이다. 상세한 내용은 아래와 같다. 

1. Elimination(소거법) -Success

                  - Failure

2. Back-substitution (후방 대입법)

3. Elimination matrices (소거 행렬)

4. Matrix multiplication (행렬 곱)

우리는 주어진 어떤 선형 시스템 A에 대한 해(solution)를 구해야 한다. 시스템의 해를 구하는 방법이 바로 소거법(Elimination)이다. 선형 대수를 다루는 모든 소프트웨어는 해를 구할 때 이 Elimination방법을 사용한다. Ex) MATLAB, Mathematica 등등

소거법 성공하면 우리는 그 시스템의 해를 구할 수 있고 대부분의 경우엔 성공한다. 

그렇다면 여기서 이러한 의문이 생길 수 있다. 

실패하는 경우는 언제일까? 또한 이 Elimination은 그 과정에서 어떻게 성공할 행렬과 실패할 행렬을 구분할까? 

우리는 이번 포스팅에서 위 물음에 대한 경우를 살펴볼 것이다. 

소거법을 적용한 이후 우리는 해의 실제 값을 구하기 위해 후방대입법(Back-substitution)을 공부할 것이다. 이건 사실 간단한 연산이다. 

사실 시스템의 해를 구하기 위한 소거법(Elimination)에 대한 아이디어는 위대한 천재 수학자 가우스(Gauss)님께서 아주 자연스럽게 생각해 낸 것이다...(미천한 중생들을 구제해 주신건지 아님 시련을 주신건지 ㅋㅋ)

이러한 소거과정은 행렬형태(Matrix form)로 표현이 되며 이 부분을 유심히 살펴봐야 한다. 즉 소거법 연산이 행렬형태로 이루어 지는데 이때 사용되는 것이 바로 소거행렬(Elimination matrices)이다. 

선형대수는 기본적으로 행렬 연산을 통해 이루어 지며 또한 컴퓨터를 이용해서 연산을 수행해야 하기 때문에 어떤 식으로 소거과정이 행렬 형태로 표현되고 또 행렬 연산이 어떤 형태로 이루어지는지를 잘 살펴봐야 한다. 

1. 소거법(Elimination)

 - Success case

아래의 식은 3개의 방정식과 3개의 미지수로 구성된 시스템 식이다. 

(2)의 행렬 A는 위 시스템식에서 방정식의 계수들만 나열하여 만든 시스템 행렬(System matrix)이다. 해를 구하는 과정은 모두 시스템 행렬 A를 이용하여 이루어진다. 

참고로 행렬 요소들의 index는 식(3)과 같은데, 각 요소의 아래 첨자 숫자에서 첫 번째 숫자는 Row의 index를, 두 번째 숫자는 Column의 index를 의미한다. 즉 $e_{12}$라고 하면 첫 번째 행(Row1), 두 번째 열(Column2)의 요소인 2를 의미한다. 

자 그럼 이제 행렬 A에 대한 해를 구하기 위해 소거를 진행해야 할 텐데.. 어디서 부터 어떻게 소거를 해야할까? 

기본적으로 소거는 왼쪽에서 오른쪽으로, 위에서 아래 방향으로 진행한다. 즉 Row1 -> Row3방향, Col1 -> Col3방향으로 소거가 진행이 된다. 

소거는 기본적으로 다음의 방식을 따른다. 

기준이 되는 식에 적당한 상수를 곱하고, 제거하고자 하는 항이 있는 식에서 이를 빼준다. 

글로는 잘 이해가 안 될 것이다. 우선 식(1)을 살펴보자. 

총 3개의 식 중에 우선 첫 번째식 x+2y+z=2는 항상 소거에서 제외한다. 2번째 식부터 소거 대상이 되는데, 위의 말대로 식을 쓰자면 두 번째 식 3x+8y+z=12에서 첫 번째 식 x+2y+z=2에 어떤 상수를 곱한 다음 빼주는 것이다. 즉,

식(4)의 결과값은 소거하려는 Row, 즉 여기에선 두 번째 Row에 대입한다. 

그럼 여기서 적당한 상수라는 것은 어떤 값일까? 이를 위해선 없애려는 것이 정확히 무엇인지를 파악해야 한다. 여기서 우리의 목적은 두 번째 식 3x+8y+z=12 에서 x항인 3x를 없애는 것이다. 제거하려는 범위가 일단 x로 한정되는 것이다. 그렇다면 그 상수값 alpha는 3이 될 것이다. 

이때 없애고자 하는 텀의 중심축이 되는 원소를 우리는 피벗(Pivot)이라 부른다. 아래 식에서 피벗은 $e_{11}$가 될 것이다. 이 pivot을 기준으로 그 아래에 있는 텀을 없애는 것이다. 

위의 식에서 첫 번째 Row에 3을 곱하고 두 번째 식에서 이를 빼준 값을 두 번째 식에 대입하면 (5)의 오른쪽과 같이 될 것이다. 

다음 단계는 어디를 소거해야할까? pivot을 중심으로 그 아래쪽에 해당하는 모든 텀들을 소거해야 한다. 즉 다음으로 소거해야 할 원소는 $e_{31}$이다. 그러나 $e_{31}$은 이미 0이기 때문에 이 단계는 넘어가도 괜찮다. 그러나 MATLAB등 프로그램에서 실제로 구현될 때는 기준 값과 제거해야할 값을 보고 pivot의 식에 0을 곱한다음 마지막 방정식에서 빼주는 작업이 이루어 진다. 

이제 시스템 행렬 A에선 x에 관한 텀들이 모두 제거되었다. 이제 남은 것은 y와 z축에 대한 텀들이다. 

다음 pivot은 y축 column중에 결정해야 한다. 만약 첫 번째 Row와 두 번째 Column인 $e_{12}$를 pivot으로 잡는다면 애써 없앤 x텀이 되살아날 것이다. 따라서 두 번째 pivot은 $e_{22}$가 되어야 한다. 

자 이제 소거가 모두 완료 되었다. 식(6)의 소거가 완료된 행렬을 우리는 u라고 명한다. 자세히 보면 그 형태가 pivot들을 기준으로 아래쪽에는 원소값이 모두 0인 상삼각행렬(Upper triangular Matrix)이다. 

결국 소거법의 최종 목표는 시스템행렬 A를 u로 만드는 것에 있다. 식(7)은 우리가 찾은 모든 pivot들을 나타내었다. 마지막 원소도 pivot이다. 여기서 한 가지 짚고 넘어가야 할 중요한 점이 있다. 0인 원소는 pivot이 될 수 없다. 위의 경우 모든 pivot원소들이 0이 아니기 때문에 알고리즘의 규칙대로만 수행하면 됐지만 pivot의 값이 0인 경우엔 조금 달라진다. 자세한 사항은 후에 알아보는 시간을 갖도록 하자. 

 - Failure case

이번에는 소거법이 실패하는 경우를 살펴보자. 어떤 경우에 소거가 실패할까? 

일단 pivot이 0인 경우 소거법 적용이 불가능하다. 이유는 첫 번째 pivot의 식에 어떤 상수를 곱해도 x텀은 0이다. 따라서 두 번째 Row의 x원소가 0이 아닌 이상 소거가 불가능하다. 

또 한가지 경우는 x텀을 소거하기위해 상수를 곱하고 뺐는데 y텀까지 소거가 되는 경우가 있다. 

pivot이 0인 경우 소거가 불가능하다..

그렇다면 이러한 경우 절대로 소거법 적용이 불가능할까? 이대로 포기해야만 할까? 

방법은 있다. 바로 0이 아닌 pivot의 방정식과 식을 교환하는 것이다. 아래 식을 살펴보자. 

식(9)의 가운데 행렬에서 두 번째 Row의 pivot이 0이 되었다. 앞서 말했듯 이 경우는 Failure case이다. 하지만 세 번째 Row의 y텀이 0이 아니기 때문에 Row를 교환하여 소거가 가능한 형태로 만들 수 있다. 

결과적으로 pivot이 0이기 때문에 소거가 불가능한 경우 우리는 Row exchange를 통해 소거가 가능하도록 만들 수 있다. 단  다음 방정식의 pivot column의 값이 0이 아닐 경우에만 가능하다. 

다음과 같은 경우도 있다. 시스템 A의 세 번째 Row의 식이 4y-4z=2 일 경우 소거법을 거쳐 최종적으로는 마지막 u 행렬의 z column pivot이 0이 된다. 이 경우 시스템 A는 not-invertible 한 행렬이 된다. 

이상으로 u matrix를 만들기 위한 소거법에서 Failure case를 만들어 보았다. Failure case에는 크게 두 가지가 있다. 

첫 번째는 극복이 가능한 temporary failure이다. 소거 과정에서 pivot이 0인 경우 발생하는데 그 다음 방정식의 pivot 라인의 원소가 0이 아닌 경우 Row exchange를 통하여 해결할 수 있다. 

두 번째는 극복이 불가능한 complete failure이다. pivot=0인 상황에서 그 다음에 교체할 만한 방정식이 존재하지 않는 경우이다. 

2. 후방대입법(Back-substitution)

다음으로 알아볼 것은 후방대입법(Back-substitution)이다. 지금까지 우리는 시스템 Ax=b에서 A만을 이용해 소거법을 적용했다. 그러나 사실 b까지 고려하여 소거법을 적용해야 한다. MATLAB등과 같은 프로그램에서는 소거법을 적용할 때 시스템 행렬 A에 대한 소거를 먼저 수행하고 b는 이후에 따로 분리하여 수행한다. 

자 이제 후방 대입법을 이해하기 위해 b까지 함께 고려한 소거법을 살펴볼 차례이다. 행렬 (2)를 b와 함께 다시 써보자. 

위와 같은 행렬을 우리는 Augmented matrix라 부른다. 부가적인 column인 b를 붙였다는 의미다. 여기서 b는 extra column이다. 

이 상태에서 시스템 A에 대해 소거법을 적용할 때 우리는 양변에 똑같은 작업을 동시에 수행해야 한다. 식(11)에 소거법을 적용한 예를 살펴보자.

시스템 행렬 A에 column b를 붙여 u와 column c를 만들어낼 수 있다. b로부터 소거법을 적용해 만든 column을 우리는 c라고 부른다. 

소거하여 만든 결과식 u와 c를 다시 방정식 ux=c형태로 써보자. (13)과 같이 될 것이다. 

이제 후방대입법(back-substitution)을 적용해서 해를 구해보자. 후방대입법이란 말 그대로 아래쪽 변수, 즉 z텀만 남아있는 세 번째 Row방정식에서부터 해를 풀어나가는 것이다. 이것이 가능한 이유는 우리가 상삼각행렬(Upper triangular)의 형태로 방정식을 만들어서 마지막 방정식은 미지수가 하나이기 때문에 쉽게 답을 알 수 있기 때문이다. 

아래쪽부터 z=-2인 것을 쉽게 알 수 있고, 두 번째 방정식엔 앞서 구한 z=-2를 대입해 y를 구하고 그 다음 첫 번째 식에 앞서 구한 y,z를 대입해 x를 푸는 것이다. 위 시스템의 해는 x=2 y=1, z=-2 가 된다. 

3. 소거행렬과 행렬곱셈(Elimination matrices and Matrix multiplication)

우리는 앞서 소거법 과정을 시스템 행렬A와 column b에 직접 나타냈다. 이번 파트에서는 이 작업을 행렬 형태로 표현할 것이다. 

즉 소거 행렬(Elimination Matrices)을 만들고 이를 시스템 행렬 A에 곱해서 소거법을 적용하는 것이다. 이러한 행렬 곱(Matrix multiplication)의 과정을 이해하면 조금 더 큰 그림을 볼 수 있다. 소거행렬을 만들기 전에 우선 지난 강의에서 배웠던 것을 상기시켜보자. 

우리는 지난 강의에서 Row picture와 Column picture를 배웠다. 여기서 특히 column picture가 중요하다고 강조했고 이는 미지수벡터와 행렬의 column의 선형 결합(Linear combination)이라 배웠다. 이 내용을 기억하며 다음을 보자. 

식(14)는 행렬 A와 벡터 x와의 곱을 나타낸다. 우리가 중고등학교때 배웠던 방식으로 행렬 곱을 볼 수도 있지만, 오른쪽과 같이 행렬의 column들과 벡터 원소간의 선형결합으로 볼 수도 있다. Matrix * column = column임을 기억하라. 

그러나 여기서 강조하고 싶은 것은 Column의 선형결합과 마찬가지로 유사한 Row의 선형결합이다. 지금까지 강의에서의 연산 대부분이 Row 연산이었기 때문에 Row의 선형결합을 이해하는 것은 중요하다. 

행 연산(Row operation)을 살펴보자. 

(※참고: 행렬과 벡터, 행렬과 행렬, 벡터와 벡터 끼리의 연산을 할 때 가운데 이어지는 차원이 반드시 같아야 하며 최종 결과는 양쪽 끝 숫자의 차원의 결과가 나온다. 위 그림 참조)

Row 벡터와 matrix의 곱은 Row의 선형결합으로 생각할 수 있다. Row벡터의 첫 번째 원소는 행렬의 첫 번째 Row와 곱해지고 나머지도 같은 방식으로 연산이 이루어진다. Column의 선형결합을 떠올리며 이 매커니즘을 잘 이해하자. 

- Step1: 

자 이제 소거를 위한 소거행렬을 만들어보자. 소거행렬이란 앞서 했던 소거과정을 행렬의 곱으로써 만들어내는 것이다. 그렇다면 아래 식 왼쪽의 소거행렬(Elimination matrix)에는 어떤 값들이 들어가야할까? 

(※참고: 식(16)의 소거행렬을 E21이라 칭한 이유는 E는 Elementary or Elimination에서 따오고, 21은 A의 Row2, Col1을 0으로 만드는 것이 목적이기 때문)

첫 번째로 소거해야할 Row는 두 번째 Row이다. 즉 $\text{Row2}=\text{Row2}-\alpha \; \text{Row1}$ 이고 $\alpha=3$이다. 이때 첫 번째와 세 번째 Row는 그대로 유지되어야 한다. 

앞서 배웠던 Row의 선형결합을 생각해보자. Matrix1 x Matrix2는 Row의 선형결합으로 표현할 수 있다. 

우선 식(16)의 A의 Row1을 그대로 유지시키려면 E21행렬의 Row1엔 어떤 벡터가 들어가야 할까? 정답은 [1 0 0]이다. 이를 어떻게 생각해낼 수 있을까? 바로 Row의 선형결합을 이용하면 된다. 아래 식을 보자. 

위 그림처럼 Row의 선형결합을 떠올리면 E21의 Row1의 첫 번째 원소는 A의 Row1과 곱해지고 두 번째 원소는 A의 Row2와, 그리고 나머지도 이와 같은 순서로 곱해진다. 따라서 E21의 Row1의 첫 번째 원소만 1로 설정하고 나머지 원소는 0으로 두면 될 것이라는 생각을 할 수 있다. 

그렇다면 A의 Row3을 그대로 유지시키려면 E21의 Row3을 어떻게 설정하면 될까? 바로 [0 0 1]이라고 생각할 수 있을 것이다. 지금까지 설정한 결과는 아래와 같을 것이다. 

자 그럼 E21의 Row2에는 어떤 값이 들어가야할까? 앞서 말했듯 A의 Row1에 3을 곱하고 Row2에서 이를 빼주면 된다. 이때 Row3은 아무런 역할을 하지 않아도 된다. 그렇다면 Row 선형결합으로부터 [-3 1 0]으로 설정하면 해당 연산을 수행할 수 있을 것이다. 최종적인 E21 행렬은 식 (19)와 같이 된다. 

- Step2: 

다음 단계는 A의 Row3의 y축 원소를 소거해야한다. 

식(19)의 결과 행렬에서 Row3, Col2의 원소인 4을 소거해야한다. 어떻게해야할까? 위의 내용을 잘 이해했다면 Row3에서 Row2에 2를 곱한 값을 빼주는 되는 것을 쉽게 알 수 있을 것이다. 즉 Row3 - 2*Row2 이다. 

일단 소거행렬 E를 만들어야 하는데, 아래 첨자 인덱스는 어떤 값이어야할까? 바로 $E_{32}$이다. A'행렬의 Row3과 Row2의 원소를 0으로 만드는 것이 목적이기 때문이다. 

그렇다면 두 번째 단계의 소거행렬인 E행렬은 어떻게 값이 설정되어야할까? 우선 Row1과 Row2는 그대로 유지되어야 한다. 그렇다면 앞서 배운것과 같이 E32행렬의 첫 번째와 두 번째 Row를 각각 [1 0 0], [0 1 0]으로 만들면 될 것이다. 

그럼 마지막 E32의 세 번째 Row는? 

일단 A'의 첫 번째 Row는 아무런 역할을 하지 않기에 0으로, 

두 번째는 2를 곱해서 빼줘야 하기 때문에 -2, 

마지막 세 번째 Row는 1로 설정해주면 된다. 즉 [0 -2 1]이다. 

결과적으로 식은 아래와 같이 될 것이다. 

여기서 한 가지 짚고 넘어가야 할 부분이 있다. E21과 E32등 소거 행렬은 u를 만들기위해 각 단계별로 행렬 A에 작용했다. 

지금까지의 단계를 수식으로 표현하면 아래와 같다. 

최초의 시스템 행렬 A에 E21이 곱해지고, 그 결과에 다시 E32가 왼쪽에 곱해지면 최종적으로 u행렬이 만들어지는 것이다. 참고로 행렬이 identity matrix(단위 행렬)가 아닌 이상 왼쪽에 곱해지는 것과 오른쪽에 곱해지는 것의 결과는 전혀 다르다. 

그렇다면 이를 좀 더 간결하게 표현할 수는 없을까? A의 왼쪽에 곱해지는 E소거행렬들을 하나로 표현할 순 없을까? 

식(21)의 오른쪽처럼 소거행렬들을 먼저 곱하고 이 결과를 A의 왼쪽에 곱해주면 결과는 같아진다. 즉 단계별로 나뉘어진 소거행렬들끼리 먼저 곱하여 하나의 소거행렬을 만들고, 이를 A에 곱해줄 경우 단번에 u행렬이 만들어지는 것이다. 

다시말하면 행렬끼리의 곱셈은 교환법칙(Commutative Law)은 성립하지 않지만, 결합법칙(Associative Law)이 성립하기 때문에 순서가 바뀌지 않는다면 어떻게 묶어서 곱하던 결과가 같다. 

결과적으로 소거행렬을 묶어서 우리는 E라고 표현한다. 

- Another type of matrix: Permutation Matrix

여기서 한 가지 다른 형태의 행렬을 소개할까 한다. 지금 당장에 필요한 것은 아니지만 사실 소거 연산 자체에는 필요한 경우가 있다. 바로 치환행렬(Permutation Matrix)이다. 이 행렬의 역할은 이름이 의미하듯 행렬의 행(row)이나 열(column)을 바꾸는 역할을 한다. 생김새는 Identity Matrix를 뒤집거나 행이나 열을 바꾼 형태이다. 

아래 행렬을 보자. 

식(22)처럼 A의 Row를 서로 바꾸기 위해선 P의 값이 어떻게 설정되어야할까? Row 선형결합을 생각하면 아래와 같이 설정해야한다는 것을 알 수 있다. Row 선형결합 방식으로 실제로 연산을 수행해보자. (※식(17)참조)

위 식은 Row를 교환하는 연산을 수행하는 행렬이다. 그렇다면 Column을 교환하고 싶을 땐 어떤 행렬을 곱해야할까? 

식(22)에서는 P행렬을 A의 왼쪽에 곱하여 Row exchange를 했다. Column exchange를 하기 위해선? P행렬을 A의 오른쪽에 곱해주면 된다. (※식(14)참조)

Column 연산을 수행하려면 행렬을 오른쪽(Right)에 곱하고

Row 연산을 수행하려면 행렬을 왼쪽(Left)에 곱해주면 된다. 

우리는 결론적으로 위의 Row, Column exchange연산을 통해 행렬의 곱은 곱하는 위치가 바뀌면 안된다는 것을 알 수 있다. 즉 행렬의 곱에 있어서 교환법칙(Commutative Law)은 성립하지 않는다는 것을 본 예를 통해 알 수 있었다. 

마치며..

우리는 Lecture 2에서 소거법을 통해 시스템 행렬 A를 상삼각행렬 형태의 u로 만들고 후방대입법을 통해 해를 구하는 법을 배웠다. 또한 행렬곱셈 연산에 대하여 공부하였고 치환행렬과 Row operation, Column operation등을 공부하였다. 

다음 강의에서 배울 내용은 A->u를 만드는 행렬에서 역으로 u->A를 만드는 역행렬에 관한 내용이다. 

이상으로 Lecture 2를 마칩니다.

디지털 영상의 첫 번째 응용 분야중 하나는 신문 산업이었는데, 런던과 뉴욕사이에 해저 케이블(submarine cable)을 통해 처음으로 사진이 전송되었다. 

이렇게 생긴 해저 케이블을 통해 전송.. 예전엔 더 허접했을 것이다

이후 1920년대 초에 Bartlane 케이블 사진 전송 시스템(Bartlane cable picture transmission system)의 등장으로 대서양간 이미지를 전송하는데 일주일이 넘게 걸리던 시간이 3시간 안쪽으로 줄어들었다. 특별히 제작된 프린칭 장치가 전송을 위한 형태로 사진을 부호화(coded)하고 받는 쪽에서 이를 복원하는 방식이었다. 

사실 알고보면 전송 절차가 굉장히 복잡하다.. 오른쪽 사진은 이 방식을 통해 전송된 사진

초기에는 사진의 화질이 좋지 않아 이를 개선시키기 위한 많은 고민들이 있었는데, 이와 관련된 문제들이 프린팅 절차와 사진의 흑백 강도의 정도(intensity levels)에 대한 분포 문제였다. 

위의 사진을 얻기 위해 사용되었던 방법은 수신부 터미널에서 tape에 구멍을 뚫어 만들어지는 사진 복제 기술(photographic reproduction)의 선호로 인해 1921년 말에 더 이상 쓰이지 않게 되었다. 

아래 왼쪽 사진은 photographic reproduction 방식을 사용해서 만들어낸 것이다. 

(왼쪽)5단계의 흑백 강도(5-level of gray intensity)로 만들어진 사진. 위의 사진에 비해 화질 개선이 뚜렷하다. 

(오른쪽) 15단계의 흑백 강도(15-level of gray intensity)로 만들어진 사진. 

초기의 Bartlane 시스템은 이미지를 총 5단계의 gray-level(밝기 값을 총 5 단계로 설정할 수 있음을 의미)로 코딩을 할 수 있었다. 1929년엔 15단계로 증가하였다. 이 기간 동안 Light beam을 통한 film plate의 개발로 복제 절차를 상당히 개선시켰다. 

위에서 언급한 사진들은 디지털 영상 범주에 넣긴 했지만 엄밀히 말하자면 디지털 영상 처리의 결과로 얻어진 결과물들은 아니다. 위의 사진들을 만드는 과정에 컴퓨터는 없었기 때문이다. 그러므로 디지털 영상 처리의 역사는 디지털 컴퓨터의 발명과 직접적으로 연관되어 있다. 

사실 디지털 이미지는 대량의 저장소와 컴퓨팅 파워를 요구하기 때문에 디지털 영상처리 분야에서의 진보는 디지털 컴퓨터의 저장, 디스플레이, 전송 기술의 발전에 굉장히 의존적이다. 따라서 컴퓨터의 발전을 논하지 않고는 디지털 영상처리를 이야기할 수는 없을 것이다. 디지털 컴퓨터의 발전 과정을 간략하게 살펴보자. 

디지털 컴퓨터의 아이디어는 5000년 전에 소아시아에서 발명된 주판으로 거슬러 올라간다. 이후 최근의 지난 두 세기동안 인류는 현재 컴퓨터라 불리는 장치를 발명하였다. 그러나 사실 현대의 디지털 컴퓨터의 근간은 1940년대 폰 노이만의 다음 두 가지 개념이 소개되면서 부터라고 할 수 있다. 

- 데이터와 프로그램을 기억하는 메모리

- Conditional branching (If then Else와 같은 조건부 분기문을 의미)

이 두 가지 아이디어는 컴퓨터의 심장과도 같은 CPU(Central Processing Unit)개발의 기본 토대가 되었다. 폰 노이만을 시작으로 현재까지 컴퓨터의 큰 발전에 기여한 주요 발달과정이 있었으며 순서대로는 다음과 같다. 

디지털 컴퓨터의 이러한 발전과 동시에 디지털 영상처리에 매우 중요한 요소인 대용량 저장 시스템과 디스플레이 시스템의 발명이 있었다. 

의미있는 영상처리를 하기에 성능이 충분한 컴퓨터는 1960년대 초에 등장했다. 오늘날 우리가 이야기하는 디지털 영상처리의 탄생은 이러한 컴퓨터들의 효용과 우주 계획(Space program)의 착수로부터 시작된다. 이 두 가지의 조합은 사람들로 하여금 디지털 영상처리의 잠재력에 관심을 기울이게 하였다. 

우주탐사로켓으로부터 수집된 영상을 개선시키기 위해 컴퓨터 기술을 사용한 것은 1964년 캘리포니아 Pasadena에 있는 제트 추진 연구소(Jet Propulsion Laboratory)에서 시작되었다. Ranger 7으로부터 전송된 달 영상은 카메라가 가진 특성상 여러 형태의 왜곡이 포함되는데, 이를 교정하기 위해 컴퓨터로 영상을 처리하였다. 아래 사진은 1964년 7월31일 9:09 AM에 Ranger 7에 의해 달 착륙 17분전 촬영된 첫 번째 달 영상이다. 사진에 보이는 마커들은 reseau라 불리며 기하보정을 하기 위함이다. 

미국 우주선에 의해 촬영된 첫 번째 이미지 이기도 하다. 매우 역사적이면서 의미 있는 이미지..

위 프로젝트에서 배운 것들은 이후 다른 우주선 영상의 화질 향상 및 복원 기술의 토대가 된다. 

디지털 영상 처리 기술은 우주산업의 응용 뿐만 아니라 이와 동시에 1960~1970년대에 의료 영상, 원격 자원 탐사(Earth resources observation), 항공 등 여러 산업에 적용된다. 1970년대에 발명된 Computerized axial tomography(CAT), 줄여서 Computerized tomography(CT)라 불리는 컴퓨터 단층 촬영법이 의료 영상의 대표적 예이다. 

1960년대부터 현재까지 디지털 영상 처리 분야는 괄목할 만한 성장을 이뤄왔다. 의학과 우주 계획의 응용 외에도 디지털 영상 처리 기술은 굉장히 산업현장, 생물과학 등 다양한 분야에 사용되고 있다. 지리학자들은 항공이나 인공위성 사진으로부터 인구 패턴을 분석하기도 하고, 복구가 불가능한 물건이나 비용이 굉장히 많이 드는 실험 결과에 대한 훼손된 사진들을 복원하거나 화질을 향상시키는 데에 디지털 영상 처리 기술을 사용하기도 한다. 또한 고고학에서도 희귀한 유물의 흐릿한 사진을 복원하는데 영상처리 기술을 사용하기도 한다. 이 외에도 물리학이나 핵의학, 법률, 기상 관측 등 다양한 분야에서 디지털 영상처리 기술이 사용된다. 

지난 시간에 행렬의 Row picture와 Column picture에 대해 알아보고 2x2행렬에 대해 2D 공간에서 plot을 통해 그 내용을 이해 하였다. 

좀 더 깊은 이해를 위해 3x3행렬을 3D 공간에서 표현해보자. 

아래 3개의 방정식과 3개의 미지수를 가지고 있는 식을 가정해보자. 

x,y와 z까지 가지고 있는 3차원의 방정식이다. 

우선은 위 식을 이해하고 그 다음 해를 구해야 한다. 

어떻게 이해할 것인가?

바로 전 시간 공부했던 Row picture가 첫 번째 방법이고, Column picture가 두 번째 방법이다. 특히 Column은 매우 중요하다!

이를 위해 우선 위 식을 행렬 형태(Matrix form)로 만들어 보자. 그리고 위의 두 가지 방법으로 행렬을 이해해본다. 

1. Row picture

3개의 방정식 중 가운데 방정식 

이 공간상에서 어떻게 표현되는지를 살펴보자. 이 식과 같이 x, y의 2차원 일 경우는 공간상에서 직선으로 표현되지만, x, y와 z까지 포함된 선형 3차원 방정식일 경우엔 아래 그림과 같이 공간상에서 평면으로 표현될 것이다. 

즉 방정식 

을 만족시키는 모든 해 [x,y,z]는 저 평면위에 존재하는 것이다. 

진짜로 그런가? 라고 생각할 수 있는 사람들을 위해 실제로 solution값을 그려보도록 하자. 

우변이 -1이 되도록 만들기 위해선 x=1, y=0, z=0 의 값을 대입하면 될 것이다. 이 외에도 아래와 같은 여러 가지의 해를 직관적으로 살펴볼 수 있다. 

x=-1, y=-2, z=-2

x= 0, y=-1, z=-1

x= 0, y= 0, z= 1

...

아래 그림은 위 해들을 실제로 plot한 결과이다. MATLAB의 회전 도구를 통해 돌려보면 실제로 해 값들이 정확히 평면위에 존재하는 것을 볼 수 있다. 

이제 나머지 Row 방정식들도 함께 표현해보자. 결과는 아래와 같다. 

위의 3평면은 딱 한 점에서 만나게 된다. 그것이 바로 이 시스템(Matrix)의 해이다. 

어떤 두 평면이 평행한 평면이 아닌 이상 반드시 어느 한 점에서 만나게 되어 있다. 

시스템의 해 부터 말하자면 해는 (x=0, y=0, z=1)이다. (※ Matlab에서 A\b와 같이 '\' 명령어를 이용하면 해를 구할 수 있음) 

plot3(0,0,1, 'r*') 명령어를 이용해 해를 실제로 그려보면 실제로 모든 평면이 이 점에서 만나는 것을 볼 수 있다. 

결론적으로 어떤 3차원의 시스템에서 하나의 Row picture (하나의 Row 방정식)는 하나의 평면을 형성하고, 이들은 평행한 평면 등 특수한 경우가 아니라면 어느 한 점에서 만난다. 이 만나는 점이 바로 이 시스템의 해(solution)이다. 

아래는 이를 구현한 코드 이다. 

2. Column picture

Row picture는 특히 3차원의 경우 알아보기 어렵다. 이 똑같은 시스템을 이제 Column picture에서는 어떻게 표현되는지 살펴보도록 하자. 

먼저 지난번 포스팅에서 배운것과 같이 위 시스템 (1)을 Column picture의 식으로 나타내면 아래와 같다. 

좌변이 나타내는 것은 3차원 벡터들의 선형결합(Linear Combination)이다. 결국 알아내야 할 것은 좌변에서 어떠한 결합이 우변의 벡터를 만들어내는가 이다. 즉 x,y,z에 어떤 적절한 값을 설정해야 우변의 벡터를 만들어 내는가?를 찾는 문제이다. 

마찬가지로 그림으로 그리면 아래와 같다. 

빨강, 초록, 파랑색 벡터는 각각 x, y, z기준 벡터를 나타내고, 각 column 벡터들은 순서대로 x, y, z에 곱해진 3차원 벡터들이다. 3차원 벡터이기 때문에 화면상으로 감이 잘 오지 않을 수 있지만 Matlab의 그래프 회전도구를 이용해 돌려서 보다보면 감이 올 것이다. 

자 그럼 이제 해를 찾아보자. (3)의 식을 다시 보자. 

가만히 보면 z에 곱해진 벡터가 우변의 벡터와 같은 것을 알 수 있다. 그렇다면 간단히 z의 벡터만 살리면 되겠군! 라고 생각이 들 것이다. x=0, y=0, z=1이면 우변의 벡터와 같아진다. 결국 위 그림에서 청록색 벡터가 해 벡터가 되는 것이다. 

어디서 많이 본 벡터인 것 같은데.. 바로 Row picture에서 힘들게 평면의 교점을 찾아 구한 해라는 것을 알 수 있다. 

Column picture에서는 선형결합으로 표현하여 간단히 해를 구할 수 있었다. 

한 가지 다른 예를 더 해보자. 우변의 항을 [1 1 -3]이라고 가정해서 식을 다시 써보자. 

정답이 바로 보이는가? 아마 단번에 보이진 않을 것이다. 

우변의 해를 만들기 위해선 간단히 x측 벡터[2 -1 0]T와 y측 벡터[-1 2 -3]T를 더하면 된다(T는 transpose를 의미함). 결국 여기선 x와 y측 벡터만 필요하고 z측 벡터는 필요 없기 때문에 답은 x=1, y=1, z=0이 될 것이다. 

그렇다면 여기서 한 가지 생각해 볼 점이 있다. 

식(4)와 같이 이런식으로 모든 경우의 b를 가정해 봤을 때, 예를 들면 b=[-1020, 23301, 32], b=[12322, -33321, 901120], ... 등등 모든 경우의 벡터에 대해서 좌변의 선형 결합으로 우변의 모든 경우의 벡터b를 만들어 낼 수 있는가? 

즉 다시 말하자면, 시스템 A에서 좌변의 선형결합으로 공간상의 모든 벡터(혹은 점)를 만들어낼 수 있는가? 

이 질문은 정말 정말 중요한 질문이다!! 이후에 배울 Rank, Singular matrix, Invertible matrix등을 이해하기 위해선 이 질문에 대한 깊은 고민이 반드시 필요하다.

강의에선 다음과 같은 질문을 칠판에 직접 판서하여 강조한다. 다르게 표현했지만 사실 아래 두 질문은 같은 것을 물어보는 것이다. 

Can I solve Ax=b for every b? 

Do the linear combinations of the columns fill 3-D space?

위 질문에 대한 답은 지금 우리가 다루고 있는 시스템 A를 기준으로 '그렇다' 이다. 

즉 식(2)의 시스템 A의 column picture를 이용해 만든 선형결합 (3)를 활용하면 공간상에 존재하는 모든 b벡터를 만들 수 있는 것이다. 

그렇다는 것은 시스템 A matrix는 non-singular matrix이며 invertible matrix이다. 

시스템 A가 위의 성질로 정의되며 공간상의 모든 벡터 b를 만들 수 있는 것은 바로 A의 column picture의 벡터들이 서로 다른 평면에 존재하기 때문이다. 

이 말이 잘 와닿지 않는 사람들도 있을 것이다. 이런 사람들을 위해 이 부분에 대해 좀 더 자세하게 설명해 보겠다. 

위 그림에서 각 벡터들 v1=[2 -1 0], v2=[-1 2 -3], v3=[0 -1 4]은 3차원 공간상에서 각기 다른 평면에 존재한다. 

그런데 만약 아래와 같이 v3=[1 1 -3]인 경우는 어떻게 될까? 

눈치 채신 분들도 있겠지만 v3=v1+v2이다. 이것이 의미하는 것은 시스템 A에서 어떤 한 column 벡터가 나머지 두 벡터의 선형결합으로 이루어진 경우고 이는 공간상에서 v3는 v1과 v2가 이루는 평면 위에 놓여져 있다는 의미다. 

식 (5)를 실제로 그려보면 아래와 같다. 코드를 실행시키고 그래프 회전 도구를 이용해 돌려보면 아래 오른쪽 그림과 같이 v3가 v1과 v2로 이루어지는 평면위에 존재하는 것을 알 수 있다. 

이 경우 시스템 A는 어떤 선형조합을 해도 노랑 평면을 벗어날 수 없다. (평면의 범위는 그림대로가 아니라 무한대로 생각해야 함)

결국 식(5)의 시스템 A는 2차원으로 그 범위가 한정되며 이 경우를 Rank가 2다 라고 한다. 

Rank는 어떤 시스템에서 선형 독립(Linearly independent)한 Row vector 혹은 Column vector의 개수를 의미하며 자세한 내용은 이후 관련된 포스팅에서 자세하게 다룰 예정이다. 지금은 그냥 이런게 있구나 정도만 알아도 될 것 같다. 

4차원 이상부터는 그림으로 표현하기 어렵지만 4차원, 5차원, ... 9차원 등 더 높은 차원에 대해서도 이 룰은 똑같이 적용된다. 

아래는 Column vector를 구현한 코드이다. 

3. 마치며..

어떤 시스템을 표현하는 Matrix form A가 있고 이 시스템 행렬을 미지수 벡터 x와 곱하여 b라는 결과를 만드는 식이 아래와 같이 존재한다. 

이때 미지수 벡터 x를 시스템 행렬A에 어떠한 방법으로 곱할것인가?를 봤을 때 우리가 지금껏 배운 것 처럼 크게 두 가지 방법이 있다. 바로 Row와 Column방법이다. Row 방법은 다른 말로 내적(Dot product)이며, Column 방법은 선형결합(Linear Combination)이다. 

Row picture는 공간상에서 선(Line) 혹은 평면(Plane)으로 표현되며

Column picture는 공간상에서 벡터(Vector)들의 조합으로 표현된다. 

Strang교수는 두 가지 방법 중 Column 방법을 선호한다고 한다. 

Row picture -> Dot product, Line(2D) or Plane(3D)

Column picture -> Linear Combination, Vectors

지금까지 우리는 어떤 시스템 A를 Row와 Column으로 각각 해석하고 공간상에 표현해 보았다. 

이를 통해 각 방법이 어떤 의미를 가지는지, 공간상에서 어떻게 표현이 되는지, 그리고 실제로 어떻게 구현하는지를 알 수 있었다. 

이상으로 Lecture 1을 마칩니다.