ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

射影近似

cv

写真から作る3次元CGから。

中心投影の近似の方法

  • 弱中心投影(weak perspective projection)
  • 疑似中心投影(paraperspective projectionb)
  • 平行投影(orthographic projection)は、弱中心投影の特殊なケース
  • アフィン変換は、これらの線形化射影の一般化したもの

カメラは正規化カメラ(f=1)を用い、対象物の重心の三次元座標を(Xc, Yc, Zc)とする。点の三次元座標を(Xc+ΔX, Yc+ΔY, Zc+ΔZ)とすると、投射式はこのようになる。

\begin{pmatrix} x \\ y \end{pmatrix} =\begin{pmatrix} X_{c}+\Delta X \\ Y_{c}+\Delta Y \end{pmatrix} \frac{1}{Z_{c}+\Delta Z}

これを物体の中心において、テーラー展開をする。

中心投影の零次近似(zero-order approximation)

テーラー展開を零次項までで近似すると、弱中心投影の投射式になる。
\begin{pmatrix} x \\ y \end{pmatrix} =\frac{1}{Z_{C}}\begin{pmatrix} X \\ Y \end{pmatrix}

このときの投影行列はこのようになる。
P_{pp}=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & Z_{C}\end{pmatrix}

Zc = 1としたとき、平行投影になる。

中心投影の一次近似(first-order approximation)

テーラー展開を一次項まで近似すると、疑似中心投影の投射式になる。

\begin{pmatrix} x \\ y \end{pmatrix} =\frac{1}{Z_{C}}\begin{pmatrix} X-\frac{X_{C}}{Z_{C}}Z+X_{C} \\ Y-\frac{X_{C}}{Z_{C}}Z+Y_{C} \end{pmatrix}

このときの投影行列はこのようになる。
P_{pp}=\begin{pmatrix} 1 & 0 & -\frac{X_{X}}{Z_{C}} & X_{C} \\ 0 & 1 & -\frac{Y_{C}}{Z_{C}} & Y_{C} \\ 0 & 0 & 0 & Z_{C}\end{pmatrix}

カメラの正規化

cv

写真から作る3次元CGから。

カメラモデル

カメラモデルを考える時の問題点

  • 光学軸がどこにあるか不明
  • 画像の両座標軸のスケールが異なる可能性がある
  • 実際の画像の両座標軸は必ずしも直角をなさない

座標系(c,x,y)とデジタル画像座標系(o,u,v)を考える。

  • x軸をu軸に平行に設定する。
  • u軸とv軸のなす角度をθとする。
  • 座標系(c,x,y)の単位長をku,kvとする。
  • 座標系(o,u,v)における座標系(c,x,y)の原点を(u0,v0)とする。

座標系(o,u,v)の座標をmp = [u,v]^T, 座標系(c,x,y)の座標をms = [x,y]^Tとしたとき、以下の関係がなりたつ。
m_{p}=Hm_{s}
ここで
H=\begin{pmatrix} k_{u} & -k_{u}\cot \theta & u_{0} \\ 0 & \frac{k_{v}}{\sin \theta } & v_{0} \\ 0 & 0 & 1 \end{pmatrix}
最終的に
P_{new}=HP_{old}=\begin{pmatrix} fk_{u} & -fk_{u}\cot \theta & u_{0} & 0 \\ 0 & \frac{fk_{v}}{\sin \theta } & v_{0} & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}

正規化カメラの概念

  • f = 1 のカメラを正規化カメラと呼ぶ
  • 正規化カメラの画像を正規化画像と呼ぶ
  • 正規化画像の座標を正規化画像座標と呼ぶ
  • fkuとfkvをαu、αvで置き換える。

こうするとPnewは、投射行列Pnを使ってこのように表現できる。
P_{new}=AP_{N}
p_{N}=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}
A=\begin{pmatrix} \alpha _{u} & -\alpha _{u}\cot \theta & u_{0} \\ 0 & \frac{\alpha _{v}}{\sin \theta } & v_{0} \\ 0 & 0 & 1 \end{pmatrix}

行列Aは、カメラの内部の変数によって構成されており、カメラ内部行列(camera intrinsic matrix)と呼ぶ。
ku, kuv, θ, u0, v0をカメラ内部変数と呼ぶ。このように、カメラ内部行列を求めることをキャリブレーションと呼ぶ。

画像のデジタル画像座標が与えられたとき、正規化画像座標は以下の式で求められる。
x=\begin{pmatrix} x \\ y \\ 1 \end{pmatrix} =A^{-1}\begin{pmatrix} u \\ v \\ 1 \end{pmatrix} =A^{-1}m

投射行列

cv

写真から作る3次元CGから。

投射行列

x=f\frac{X}{Z}
y=f\frac{Y}{Z}
この式は、同次座標を用いて以下の行列で表せる。
\begin{pmatrix} x \\ y \\ 1 \end{pmatrix} \simeq \begin{pmatrix} f & 0 & 0 & 0 \\ 0 & f & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} X \\ Y \\ Z \\ 1 \end{pmatrix}

≃はスケールを除いて等しいことを示す。

この時の
P=\begin{pmatrix} f & 0 & 0 & 0 \\ 0 & f & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}
のPを中心投影行列と呼ぶ。
三次元空間上の座標M=(X Y Z 1)^Tと、仮想画像平面上の座標m=(x y 1)^Tの関係は、m = PM で表現できる。

世界座標系とカメラ座標系

世界座標系(world coordnate system)に対して投影行列を適用するには、まず世界座標系をカメラ座標系に変換し、その後に投影行列を適用する。

カメラ座標系を世界座標系に対応させるには、カメラ座標系を回転させ、次に平行移動を行う。
回転は3x3の行列R、平行移動は3x1の行列tで表現できる。Rは以下の性質をもつ。

RR^{T}=R^{T}R=I
$\det (R) = 1
これは、回転の逆行列は逆回転の意味を持っており、回転後に逆回転を行うと元の位置に戻ることを示す。

Rとtを使って、カメラ座標系Mcと、ワールド座標系Mwの関係は以下の式で表現できる。
M_{C}=RM_{w}+t

ここで
D=\begin{pmatrix} R & t \\ 0_{3}^{T} & 1 \end{pmatrix}
であるDを使うと、2つの座標系は以下の式で表現できる。
Mc=DMw
Dは3次元のユークリッド変換を示す。

Dを使うと、新しい投射行列は以下の式で表現できる。
P_{new}=HP_{old}=\begin{pmatrix} fk_{u} & -fk_{u}\cot \theta & u_{0} & 0 \\ 0 & \frac{fk_{v}}{\sin \theta } & v_{0} & 0 \\ 0 & 0 & 1 & 0\end{pmatrix}
fkuとfkvが積の形で残るため、焦点距離の変化と画素サイズの変化が区別できない事を示している。

Computer Vison で使う座標系

cv

ピンボールカメラモデル


測定対象物Mは、焦点面Fのレンズ中心Cを通って、画像平面I上のmに投影される。焦点面Fと画像平面の距離をfとする。
焦点面があるXYZをカメラ座標系と呼ぶ。画像平面上の座標(x,y)と3次元座標系の座標(X,Y)との関係は、以下の関係が成り立つ。

x=f\frac{X}{Z}
y=f\frac{Y}{Z}


図のように画像面を焦点面の前に持ってきても数学的関係は保たれる。

ピンボールカメラモデルと言ったときは、この図がよく使われます。最初の図に比べると、座標軸の正の方向がそろっていて扱いやすくなっています。

写真から作る3次元CG

cv

写真から作る3次元CG

Computer Visionの本は行列式ばかりでてくるような本か、ライブラリの使い方が中心の本しか無く、アルゴリズムが分かるちょうど良い本を探していたらこの本を見つけました。ちょうど良い難易度なので、ゆっくり読んでいきます。

1章から専門用語の対訳をまとめました。

  • pixel coordinate デジタル画像座標
  • normalized coordinate 　正規化画像座標
  • normalized camera 正規化カメラ
  • intrinsic matrix カメラ内部行列
  • intrinsic parameters カメラ内部変数
  • principal point 光軸点
  • extrinsic parameters 外部変数
  • epipolar line(plane) エピポーラ線（平面）
  • fundamental matrix 基礎行列
  • essential matrix 基礎行列
  • projection matrix 投影行列
  • perspective projection 中心投影
  • orthographic projectio 平行投影
  • weak perspective projection 弱中心投影
  • paraperspective projection 疑似中心投影
  • affine projection アフィン投影
  • camera calibration カメラの校正
  • camera self-calibration カメラの自校正

素数夜曲　女王陛下のLISP

book scheme

素数夜曲　女王陛下のLISP読みました。簡単に感想を。

本の内容

　タイトル通り数学とLispの本です。
　この本は大きく前半と後半（付録）に別れています。前半は算数から数学に自然に入って行くような内容が講義形式で話が進みます。整数、最大公約数から入り、無限、有理数、無理数と、数を扱った数学をわかりやすく説明しています。この本の基本スタンスが、「手を動かして自分で法則に気がつく」事を重視しています。数学の楽しみ方を音楽に例えているのははじめて見ました。音楽の楽しみ方が、下手でも良いから演奏することのように、数学に関しても主体的に取り組んでいくことがとても大事というのは共感できます。プログラミングも同じですね。数学の本なのに英語の表記を併記してあるのは助かります。よくわからないところは、検索しもって読んでいくと面白いと思います。時々AAで書かれた検索梟が登場して「○○」で検索しろと教えてくれます。私は無限と濃度の所は特に面白く感じました。自然数と偶数が同じ程度に多くある事を受け入れるためには、無限を受け入れないといけない所に無限の深さを感じました。まあ、無限だからどこまでも深いんですけどね。
　後半はSchemeの文法の説明が最初にあって、Schemeを使って数学のいろんな問題を解いていきます。ただ解くだけではなく、結果を可視化する所が良くできています。実践的なプログラムを作ると言うよりは、プログラミングを通して数学と向き合うところがメインです。SICPにλ計算を加えて内容を数学側に振ったような内容です。非決定性計算、無限ストリームのような概念だけでなく、チャーチ数、Yコンビネータ、クオータニオン、モンテカルロ、乱択アルゴリズムまでいろんな概念をSchemeで実装していきます。

Schemeプログラムの紹介

この本の中から、Schemeのプログラムを一つ紹介します。付録Dに出てくるオイラーの函数です。
オイラーの函数とは、与えられた数n未満の数の中で、nと互いに素(relatively prime)な関係にある数の個数を表します。例えば、n=6の時、n未満の数は1,2,3,4,5となり、6と互いに素な数は1と5なので、φ(6)=2と表せます。本書ではもう少し数学的に突っ込んだ話があるのですが、0から999までのこのオイラーの函数を求めるコードがこれです。本書と若干iotaの動きが違うのと、出力部分は利用しやすいように少し変更しています。

; オイラーの函数
(define (totient n)
  (apply +
         (map (lambda (x)
                (if (= 1 (gcd n x)) 1 0))
              (iota n))))
; 出力部
(map (lambda (x)
       (let ((t (totient x)))
         (format #t "~A,~A~%" x t)))
     (iota 1000))

これをプロットするとこのようになります。

このグラフの規則性と素数の持つ不規則性から、『素数の魅力は、こうした"矛盾の中にある"』と話を締めくくっています。この結果を面白いと思うのであれば、この本はおすすめです。

おすすめの人

　高校３年生なら、ゆっくり読んでいけば十分理解できる内容だと思います。夏休み等まとまった時間があれば是非挑戦して欲しいです。数学ガールが好きな人も楽しめると思います。

2次元変換の階層

cv

Multiple View Geometry in Computer Vision 2.4から。2次元の画像変換における階層構造のまとめ。座標は全て同次座標(homogeneous coordinate)。

Class I Isometries transformations

対象物の移動、再配置。

行列表現

\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} =\begin{pmatrix} \epsilon \cos \theta & -\epsilon \sin \theta & t_{x} \\ \epsilon \sin \theta & \epsilon \cos \theta & t_{y} \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}

ベクトル表現

{\mathbf{x\/}'=H_{E} \mathbf{x\/}=\begin{pmatrix} \mathbf{R\/} & \mathbf{t\/} \\ \mathbf{0\/}^{\mathbf{T\/}} & 1 \end{pmatrix} \mathbf{x\/}

特徴
  • εは±1の値を取る。εが1の時、ユークリッド変換（移動と回転）と同じ。εが-1の時向きが反転する。
  • Rは2x2の回転行列
  • 長さ、角度、面積が不変量
  • 自由度は3

Class II Similarity transformations

Isometries transformations に拡大縮小を追加。

行列表現

\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} =\begin{pmatrix} s \cos \theta & - s \sin \theta & t_{x} \\ s \sin \theta & s \cos \theta & t_{y} \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}

ベクトル表現

\mathbf{x\/}'=H_{S}\mathbf{x\/}=\begin{pmatrix} s \mathbf{R\/} & \mathbf{t\/} \\ \mathbf{0\/}^{\mathbf{T\/}} & 1 \end{pmatrix} \mathbf{x\/}

特徴
  • sはスケーリングの係数
  • 角度と長さの比が不変量
  • 自由度は4

Class III Affine transformations

アフィン変換

行列表現

\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} =\begin{pmatrix} a_{11} & a_{12} & t_{x} \\ a_{21} & a_{22} & t_{y} \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}

ベクトル表現

\mathbf{x\/}'=H_{A}\mathbf{x\/}=\begin{pmatrix} \mathbf{A\/} & \mathbf{t\/} \\ \mathbf{0\/}^{\mathbf{T\/}} & 1 \end{pmatrix} \mathbf{x\/}

特徴
  • Aは2x2の非正則行列
  • 面積の比が不変量。平行な直線は変換後も平行。平行線の一部である直線の長さの比も不変。
  • 自由度は6

Class IV Projective transformations

投影変換

行列表現

\begin{pmatrix} x_{1}' \\ x_{2}' \\ x_{3}' \end{pmatrix} =\begin{pmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \end{pmatrix} \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix}

ベクトル表現

\mathbf{x\/}'=H_{P}\mathbf{x\/}=\begin{pmatrix} \mathbf{R\/} & \mathbf{t\/} \\ \mathbf{v\/}^{\mathbf{T\/}} & v\end{pmatrix}\mathbf{x\/}

特徴
  • ベクトルv=(v1,v2)^T
  • Hpの各係数をスカラー倍(0を除く)しても同じ意味を持つ。
  • 交差比(cross-rate)が不変量
  • 自由度は8 (Hpの係数が9個だが、係数の定数倍は同じ意味をもつので）