코딩 더 매트릭스 - 6장 기저 (1)

필립 클라인의 저서 코딩 더 매트릭스 6장 기저

1. 좌표 표현을 선형결합, 행렬-벡터 곱셈으로 표현해 봅니다.
2. 좌표 표현을 이미지 손실 압축에 적용해 봅니다.
3. 생성자 집합을 찾기 위한 알고리즘 Grow와 Shrink를 살펴봅니다.
4. 최소 스패닝 트리를 이해하고 Grow와 Shrink 알고리즘으로 최소 스패닝 트리를 찾아 봅니다.
5. Superfluous-Vector 정리를 이해합니다.
6. 일차종속과 일차독립을 이해합니다.
7. 기저와 기저변경을 이해합니다.
8. 카메라 좌표계를 이해하고 공간상의 점을 이미지 평면 상에 매핑하는 원근감을 이해합니다.

좌표 표현

2차원 평면에서 좌표 $(1,2)$를 다음과 같이 선형결합, 행렬-벡터 곱셈으로 나타낼 수 있습니다.

좌표축이 $a_1, ..., a_n$이라 할때 열벡터 $a_1, ..., a_n$들로 구성된 행렬을 $A = \begin{bmatrix}a_1 & ... & a_n\end{bmatrix}$와 같이 쓸 수 있습니다.

$Au = v$라 할때 $u$는 $a_1, ..., a_n$에 대한 $v$의 좌표 표현입니다. $u$는 행렬방정식 $Au = v$의 해이기도 합니다. 벡터공간 $V$가 $Span\text{ }\{a_1, ..., a_n\}$일때 $A$의 열들은 벡터공간 $V$의 생성자들이고 $v \in V$입니다. 따라서 방정식 $Au = v$는 적어도 하나의 해를 가집니다.

이미지 손실압축

100 X 200 의 이미지를 압축하고자 합니다. 다음과 같은 방법들을 고려해볼 수 있습니다.

1. 벡터를 k-스파스 벡터로 100개의 엔트리를 가진 이미지의 한 벡터에 대해 가장 큰 k개 엔트리를 제외한 나머지 벡터를 0으로 만들어 스파스한 벡터를 저장하는 방법입니다. $e.g. [200,30,75,50] -> [200,0,75,0]$
2. 이미지 벡터를 좌표 표현 생성자 벡터 $a \in \Bbb{R}^{100}$ 을 최소 갯수로 찾아 생성자 벡터들과 좌표 표현을 저장합니다. 이때 모든 이미지 벡터들을 생성자벡터와 좌표 표현의 선형결합으로 표현할 수 있어야 합니다. 만약 최소로 필요한 생성자 벡터가 50개라면 좌표 표현은 50 X 200개만 있어도 됩니다. 하지만 생성자 벡터의 최소 개수가 크면 효율이 없습니다.

3. 앞의 두 전략의 조합

   • 먼저 최소 갯수의 생성자 $\{ a_1, ..., a_n : a_i \in \Bbb{R}^{100}\}$와 각각의 이미지 벡터에 대한 좌표 표현 $u$를 찾습니다.
   • $u \in \Bbb{R}^n$를 스파스한 벡터 $\tilde{u}$로 대체하고 $\tilde{u}$를 저장합니다.
   • 압축된 이미지를 복원시 $\tilde{u}$와 $a_1, ..., a_n$의 선형결합을 계산합니다.

생성자 집합을 찾기 위한 두 개의 Greedy 알고리즘

이미지 손실압축에서 최소로 필요한 생성자 $a_1, ..., a_n$는 어떻게 찾을 수 있을까요? 두 개의 Greedy 알고리즘을 살펴 보겠습니다. 다음에 오는 코드들은 의사코드 입니다.

def Grow(V):
	B = 0
	repeat while possible
		find a vector v in V that is not in Span B, and put it in B

def Shrink(V):
	B = some finite set of vectors that spans V
	repeat while possible
		find a vector v in V such that Span {B - v} = V, and remove v from V

Grow 알고리즘은 벡터공간 $V$의 생성자 집합 $B$를 찾을때까지 추가를 반복합니다. 만약 더이상 추가할 생성자 벡터가 없다면 알고리즘을 종료합니다. Shrink 알고리즘은 생성자 집합 $B$에서 더이상 제거할 벡터가 없을때 까지 제거를 반복합니다. 물론 두 알고리즘 모두 집합 $B$는 반드시 $V$를 생성해야 합니다.

최소 스패닝 트리 (Minimum Spanning Tree)

포켓몬스터의 배경이었던 관동지방 전체 도시에 전력을 공급한다고 생각해보겠습니다.

위의 그래프에서 노드는 도시, 엣지는 도시 사이에 설치가능한 전력 공급망, 엣지의 가중치는 설치 비용을 뜻합니다. 만약 노드들 사이의 경로가 2개 이상이라면 이 그래프는 사이클을 포함한다고 합니다. 예를 들어 무지개시티와 보라시티를 잇는 경로는 2개 이상이므로 사이클을 포함합니다.

스패닝 트리는 사이클을 포함하지 않고 최소 경로만 선택한 그래프를 뜻합니다. Spanning 이라는 단어에서 유추할 수 있듯 최소로 선택한 엣지들 만으로 모든 노드들을 연결할 수 있습니다. 아래 그래프들은 스패닝 트리입니다.

한편 그래프의 왼편과 오른편은 노드들을 공유하고 있지 않으므로 (서로 분리돼있음) 그래프는 두 개의 서브그래프로 이루어져 있다고 말할 수 있습니다.

최소 스패닝 트리는 가중치의 합이 최소인 스패닝 트리입니다. Grow 알고리즘과 Shrink 알고리즘으로 최소 스패닝 트리를 직접 찾아보겠습니다. 우선 엣지들을 다음과 같이 표로 정리해 볼 수 있습니다.

표의 행은 두 노드를 연결하는 엣지의 GF2 상의 벡터로 만들 수 있습니다. 예를 들면 회색시티와 달맞이산을 연결한 엣지는 $[1,1,0,0,0,0,0]$ 입니다. 각각의 엣지들을 GF2 상의 벡터로 표현했을때

위의 벡터들을 모두 계수 1에 대해 선형결합하면 무지개시티에서 보라시티를 잇는 엣지를 만들 수 있습니다. 따라서 어떤 벡터가 다른 벡터들의 생성에 속하는지 쉽게 알아낼 수 있습니다. 이를 활용해 Grow 알고리즘으로 그래프의 최소 스패닝 트리를 찾아보겠습니다.

from GF2 import one
from vec import Vec
from vecutil import zero_vec

Gray = '회색시티'
Moon = '달맞이산'
Green = '태초마을'
Blue = '블루시티'
Rainbow = '무지개시티'
Brown = '갈색시티'
Purple = '보라시티'

D = {Gray, Moon, Green, Blue, Rainbow, Brown, Purple}

graph = {
    (Gray, Moon): { 'vec': Vec(D, {Gray: one, Moon: one}), 'cost': 7 },
    (Gray, Green): { 'vec': Vec(D, {Gray: one, Green: one}), 'cost': 2 },
    (Moon, Green): { 'vec': Vec(D, {Moon: one, Green: one}), 'cost': 9 },
    (Blue, Rainbow): { 'vec': Vec(D, {Blue: one, Rainbow: one}), 'cost': 5 },
    (Blue, Brown): { 'vec': Vec(D, {Blue: one, Brown: one}), 'cost': 3 },
    (Rainbow, Brown): { 'vec': Vec(D, {Rainbow: one, Brown: one}), 'cost': 4 },
    (Rainbow, Purple): { 'vec': Vec(D, {Rainbow: one, Purple: one}), 'cost': 8 },
    (Brown, Purple): { 'vec': Vec(D, {Brown: one, Purple: one}), 'cost': 6 },
}

def recursion(v, target, B):
    if v == target:
        return True
    for i, l in enumerate(B):
        if recursion(v + l, target, B[i+1:]):
            return True

def grow():
    B = []
    res = []
    initial_vec = zero_vec(D)
    keys = sorted(graph.keys(), key=lambda x: graph[x]['cost'])

    for k in keys:
        if not recursion(initial_vec, graph[k]['vec'], B):
            B.append(graph[k]['vec'])
            res.append(k)
    return res

res = grow()
for r in res:
    print(r)

>>>
('회색시티', '태초마을')
('블루시티', '갈색시티')
('무지개시티', '갈색시티')
('갈색시티', '보라시티')
('회색시티', '달맞이산')

프로시저 grow는 생성자 집합 B를 찾을 때까지 벡터공간 graph의 모든 벡터에 대해 반복합니다. 이때 반복순서는 벡터들의 가중치의 오름차순입니다. 각 벡터에 대해 재귀적으로 벡터가 집합 B의 생성에 속하는지 판단합니다. 생성에 속하지 않는다면 B에 추가합니다.

다음은 Shrink 알고리즘을 이용해 최소 스패닝 트리를 찾는 코드입니다.

def shrink():
    B = [ item['vec'] for k, item in graph.items() ]
    res = list(graph.keys())
    initial_vec = zero_vec(D)
    keys = sorted(graph.keys(), key=lambda x: graph[x]['cost'], reverse=True)

    for k in keys:
        if recursion(initial_vec, graph[k]['vec'], [ v for v in B if v != graph[k]['vec'] ]):
            B.remove(graph[k]['vec'])
            res.remove(k)
    return res

res = shrink()
for r in res:
    print(r)

>>>
('회색시티', '달맞이산')
('회색시티', '태초마을')
('블루시티', '갈색시티')
('무지개시티', '갈색시티')
('갈색시티', '보라시티')

프로시저 shrink는 생성자 집합 B를 찾을 때까지 벡터공간 graph의 모든 벡터에 대해 반복합니다. 이때 반복순서는 벡터들의 가중치의 내림차순입니다. 각 벡터에 대해 재귀적으로 벡터가 집합 B의 생성에 속하는지 판단합니다. 생성에 속한다면 B에서 제거합니다.

Grow와 Shrink 모두 다음 그래프를 최소 스패닝 트리로 찾아냅니다.

Superfluous-Vector 정리

임의의 집합 $S$와 임의의 벡터 $v \in S$에 대해 만약 $v$가 $S$내의 다른 벡터들의 선형결합으로 표현될 수 있다면 $Span\text{ }(S - \{v\}) = Span\text{ }S$입니다. 이를 증명해보겠습니다.

$S = \{v_1, v_2, ..., v_n\}$이라 하고 $v_n$을 다른 벡터들의 선형결합으로 표현될 수 있다고 하겠습니다.

$Span\text{ }S$내의 모든 벡터 $v$는 다음과 같이 표현할 수 있습니다.

$v_n$에 관한 식을 위 식에 대입하면

따라서 $Span\text{ }S$내의 임의의 벡터는 $Span\text{ }(S - \{v_n\})$내에서도 존재합니다.

일차종속, 일차독립

$a_1v_1 + ... + a_n v_n = 0$ 식을 벡터 $[v_1, ..., v_n]$들의 자명하지 않은 결합으로 표현할 수 있다면(계수 $a_1, ..., a_n$ 중 적어도 하나가 0이 아니라면) 벡터들은 일차종속입니다. $a_1v_1 + ... + a_n v_n = 0$ 식에서 $a_n v_n$을 우변으로 넘기면 $a_n v_n = -(a_1 v_1 + ... + a_{n-1} v_{n-1})$ 이므로 $a_n v_n$는 다른 벡터들의 선형결합으로 표현할 수 있습니다.

$a_1v_1 + ... + a_n v_n = 0$이 오직 자명한 결합으로 표현할 수 있다면(계수 $a_1, ..., a_n$ 이 모두 0이라면) 일차독립입니다.

일차독립 집합의 부분집합은 일차독립입니다. 이 명제는 만약 부분집합이 일차종속이면 모집합이 일차종속이라는 명제의 대우입니다. 이것이 참이라는 것은 쉽게 알 수 있습니다. 집합 $S$, $T$가 있을때 $S \in T$이고 $S = \{s_1, s_2, ..., s_n\}$, $T = \{s_1, s_2, ..., s_n, t_1, ..., t_m\}$라 하겠습니다. $S$가 일차종속이라면 $a_1s_1 + ... + a_n s_n = 0$을 만족하는 계수 $a_1, ..., a_n$ 중 적어도 하나는 0이 아닙니다. 따라서 $a_1s_1 + ... + a_n s_n + 0t_1 + ... + 0t_n = 0$ 식이 성립하고 이는 집합 $T$가 일차종속이라는 것을 의미합니다.

기저

벡터공간 $V$에 대해 $V$의 생성자들로 구성된 일차독립 집합을 기저라 합니다. 따라서 $V$의 벡터들의 집합 $B$가 다음 두 성질을 만족하면 $B$는 $V$의 기저입니다.

• $Span\text{ }B = V$
• $B$는 일차독립

예를 들어 벡터공간 $\Bbb{R}^3$에 대한 기저 중 하나는 $[1,0,0], [0,1,0], [0,0,1]$입니다. 모든 벡터 $[x,y,z] \in \Bbb{R}^3$ 는 $x[1,0,0] + y[0,1,0] + z[0,0,1]$ 로 표현 가능하므로 $[1,0,0], [0,1,0], [0,0,1]$ 는 $\Bbb{R}^3$ 를 생성합니다. 세 백터 중 어느 것도 나머지 두 벡터의 선형결합으로 표현불가능하므로 일차독립입니다. 따라서 $[1,0,0], [0,1,0], [0,0,1]$ 는 $\Bbb{R}^3$의 기저입니다.

$[1,1,1], [1,1,0], [0,1,1]$ 역시 $\Bbb{R}^3$의 기저입니다. 이미 알고있는 기저 $[1,0,0], [0,1,0], [0,0,1]$이 $[1,1,1], [1,1,0], [0,1,1]$의 생성에 있으면 $[1,1,1], [1,1,0], [0,1,1]$는 $\Bbb{R}^3$을 생성합니다.

$[1,1,1], [1,1,0], [0,1,1]$은 세 백터 중 어느 것도 나머지 두 벡터의 선형결합으로 표현불가능 하다면 일차독립입니다. $[1,1,1] = \alpha [1,1,0] + \beta [0,1,1]$ 에서 첫번째 엔트리가 1이려면 $\alpha$가 1이어야 합니다. 그리고 세번째 엔트리가 1이려면 $\beta$가 1이어야 합니다. 하지만 $\alpha$, $\beta$가 모두 1일때 두번째 엔트리가 2가 되므로 $[1,1,1]$은 $[1,1,0], [0,1,1]$의 선형결합으로 표현할 수 없습니다. 나머지 두개의 벡터들에 대해서도 선형결합으로 표현 불가능합니다. 따라서 세 백터는 일차독립이고 $\Bbb{R}^3$의 기저입니다.

벡터공간 $V$의 임의의 벡터 $v$에 대해 $V$의 기저 벡터들에 의한 표현은 오직 하나만 존재합니다. 두 개가 존재한다고 가정하고 이를 증명해보겠습니다. 기저 벡터가 $a_1, ..., a_n$일때

로 두 개의 표현이 존재합니다. 위 식은 다음과 같이 정리할 수 있습니다.

$a_1, ..., a_n$은 기저이므로 계수 $\alpha_1 - \beta_1, ..., \alpha_n - \beta_n$은 모두 0입니다. 따라서 $\alpha_i = \beta_i$이고 $v$의 기저에 대한 표현은 오직 하나만 존재합니다.

기저변경

하나의 기저에 대한 어떤 벡터의 좌표 표현을 또 다른 기저에 대한 동일한 벡터의 좌표 표현으로 바꿀 수 있습니다. 이를 기저변경이라 합니다. 필드 $F$상의 벡터공간 $V$에 대해 $a_1, ..., a_n$이 기저를 형성한다고 할 때 다음과 같이 함수 $f: F^n \to V$를 정의하겠습니다.

즉 함수 $f$는 어떤 벡터의 $a_1, ..., a_n$에 대한 표현을 벡터 그 자체로 매핑합니다. 어떤 벡터의 기저에 대한 표현은 오직 하나이므로 $f$는 전단사 함수이고 가역적입니다. 함수 $f$에 대응하는 행렬 $A$가 있다면 $f(u) = Au = v$는 가역적이므로 매핑된 벡터 $v$를 이용해 좌표 표현 $u = A^{-1}v$ 를 구할 수 있습니다.

벡터 공간 $V$에 대해 $a_1, ..., a_n$이 하나의 기저를 형성하고 $b_1, ..., b_m$이 다른 기저를 형성할때 함수 $f: F^n \to V$와 $g: F^m \to V$를 다음과 같이 정의하겠습니다.

$V$의 벡터 $v$에 대해 $v = f(x) = g(y)$ 는 벡터 $v$를 서로 다른 기저와 좌표 표현으로 표현할 수 있음을 뜻합니다. 함수의 가역성을 이용해 합성함수 $g^{-1} \circ f$ 를 정의해보겠습니다. 함수의 정의역은 $F^n$이고 공역은 $F^m$입니다. 이는 기저 $a_1, ..., a_n$에 대한 좌표 표현 $x$를 기저 $b_1, ..., b_n$에 대한 좌표 표현으로 변경할 수 있음을 뜻합니다. ( $F^n \to V \to F^m$ )

$f(x) = g(y)$를 $a_1, ..., a_n$을 열벡터로 갖는 행렬 $A$와 $b_1, ..., b_m$을 열벡터로 갖는 행렬 $B$, 좌표 표현 $x$, $y$를 이용해 $Ax = By$로 바꿔 쓸 수 있습니다. $B$는 역행렬이 존재하므로 $B^{-1}Ax = y$가 성립합니다. 따라서 $a_1, ..., a_n$ 기저에 대한 좌표 표현 $x$에 행렬 $B^{-1}A$ 를 곱함으로써 $b_1, ..., b_m$ 에 대한 좌표 표현 $y$를 얻을 수 있습니다. 이때 행렬 $B^{-1}A$는 기저변경 행렬입니다.

원근감 렌더링

3차원 공간상의 물체를 카메라로 찍으려 합니다. 아래는 물체에 반사된 빛이 카메라의 이미지 센서 어레이를 통과하는 모습을 단순화한 그림입니다.

이미지 센서 어레이의 왼쪽 위 모서리를 (0,0)이라 하면 다람쥐의 코에서 반사된 빛은 (1,2)를 통과합니다.

공간의 한 점 $p$를 이미지 센서 어레이 평면에 대응하는 점 $q$로 매핑하는 함수가 필요합니다. 간단하게 이런 함수를 표현할 수 있는 특별히 편리한 기저가 있습니다. 이것을 카메라 좌표계라고 합니다.

원점은 카메라의 중심이고 기저벡터 $a_1$은 왼쪽 위 모서리에서 오른쪽 모서리로 수평방향으로 향하는 벡터입니다. $a_2$는 왼쪽 위 모서리에서 왼쪽 아래 모서리로 수직방향으로 향하는 벡터입니다. $a_3$는 원점에서 왼쪽 위 모서리로 향하는 벡터입니다. 이제 공간의 점 $p$와 대응하는 점 $q$를 다음 그림에서 살펴보겠습니다.

물체의 옆면에서 바라본 위 그림에서 기저벡터 $a_1$은 우리가 바라보는 방향의 벡터이므로 보이지 않습니다. 다람쥐의 코 $p$를 카메라 좌표계 기저들로 선형결합 하면 $p = x_1a_1 + x_2a_2 + x3a_3$입니다. 이에 대응하는 점 $q$는 삼각형의 닮음비를 이용하면 $q = \frac{x_1}{x_3}a_1 + \frac{x_2}{x_3}a_2 + \frac{x_3}{x_3}a_3$ 입니다.

간단히 아래 그림의 정육면체를 카메라 좌표계를 이용해 그려보겠습니다.

from vecutil import list2vec

L = [
    [0,0,0],
    [1,0,0],
    [0,1,0],
    [1,1,0],
    [0,0,1],
    [1,0,1],
    [0,1,1],
    [1,1,1]
]
corners = [ list2vec(v) for v in L ]

corners는 모서리들을 카메라 좌표계에 대한 좌표 표현으로 저장합니다.

# 볼록결합으로 모든 좌표의 점들을 벡터화
def line_segment(pt1, pt2, samples=100):
    return [ (i / samples) * pt1 + (1 - i / samples) * pt2 for i in range(samples + 1) ]

line_segments = [
    line_segment(corners[i], corners[j]) for i, j in
    [ (0,1), (2,3), (0,2), (1,3), (4,5), (6,7), (4,6), (5,7), (0,4), (1,5), (2,6), (3,7) ]
]
pts = sum(line_segments, [])

프로시저 line_segment는 두 모서리를 인수로 받아 두 모서리 사이의 점 100개를 반환합니다.

# 카메라 중심을 원점으로 두기위해 평행이동
shifted_pts = [ v + list2vec([ 1,1,8 ]) for v in pts ]

# 기저
cb = [
    list2vec([ 1 / 100, 0, 0 ]),
    list2vec([ 0, 1 / 100, 0 ]),
    list2vec([ 0, 0, 1 ])
]

# 좌표 표현 찾기
def vec2rep(cb, v):
    return list2vec([ v[i] / cb[i][i] for i in v.D ])

# 이미지 평면으로 투영
def scale_down(x):
    return list2vec([ x[0] / x[2], x[1] / x[2], 1 ])

reps = [ vec2rep(cb, v) for v in shifted_pts ]
in_camera_plane = [ scale_down(u) for u in reps ]

카메라 좌표상 카메라 중심을 원점으로 두기 위해 모든 점들을 $[1, 1, 8]$만큼 평행이동 합니다. 카메라 좌표의 기저는 $[\frac{1}{100},0,0], [0,\frac{1}{100},0], [0,0,1]$입니다. 프로시저 vec2rep는 점들을 기저에 대한 좌표 표현으로 변환해줍니다. scale_down은 공간의 점을 대응하는 이미지 센서 어레이로 매핑합니다.

def pixel(v):
    return (v[0], v[1])

pixels = [ pixel(u) for u in in_camera_plane ]
plot(pixels, 30, 1)