ビジュアルコンピューティングⅠB／図形処理B　期末試験（予想問題）

参照：内部パラメータ・画角 $\theta=2\tan^{-1}\frac{w_x/2}{f}$（B第1回 p.18, p.32）、外部パラメータと透視投影行列 $P=K[R\,|\,t]$（B第1回 p.34–36）、基本行列 $E=[t]_\times R$（B第3回 p.40）、エピポール（B第3回 p.15–18）、回転四元数（B第7回 p.6）、RGBD復元（B第4回 p.6）。

前提の整理（全小問で使用）

カメラ0：$Z_0$ 軸は $Z_w$ 軸と同一直線・同一向き、$Y_0=Y_w$、右手系より $X_0=X_w$。よってカメラ0座標系は世界座標系を $C_0=(0,0,-a)$ に平行移動しただけで、$\;\boldsymbol{M}_0=\boldsymbol{M}_w+(0,0,a)^T$。すなわち $R_0=I,\ \boldsymbol{t}_0=(0,0,a)^T$。

カメラ1：$Z_1$ 軸は $C_1=(-a,0,0)$ から世界原点へ向かうので、世界座標での方向は $Z_1=(1,0,0)$。$Y_1=Y_w=(0,1,0)$、右手系より $X_1=Y_1\times Z_1=(0,0,-1)$。各軸を列に並べた回転部は $$R=\begin{pmatrix}0&0&1\\0&1&0\\-1&0&0\end{pmatrix}$$ これは $Y_w$ 軸まわり $+90^\circ$ の回転 $R_y(90^\circ)$ である。

(1)

水平画角 $90^\circ$、画像幅 800 画素より $\;f=\dfrac{800/2}{\tan 45^\circ}=400\;$[画素]。主点は $(c_u,c_v)=(400,300)$。両カメラは同一仕様なので $$K_0=K_1=\begin{pmatrix}400&0&400\\0&400&300\\0&0&1\end{pmatrix}$$

(2)

カメラ1座標をカメラ0座標へ移す変換は $\boldsymbol{M}_0=R\boldsymbol{M}_1+\boldsymbol{t}$。並進はカメラ0座標での $C_1$ の位置 $\boldsymbol{t}=C_1-C_0=(-a,0,a)^T$。同次座標系で $$\begin{pmatrix}X_0\\Y_0\\Z_0\\1\end{pmatrix}=\begin{pmatrix}0&0&1&-a\\0&1&0&0\\-1&0&0&a\\0&0&0&1\end{pmatrix}\begin{pmatrix}X_1\\Y_1\\Z_1\\1\end{pmatrix}$$ 検算：$\boldsymbol{M}_1=\boldsymbol{0}\Rightarrow\boldsymbol{M}_0=(-a,0,a)^T=C_1$、$\boldsymbol{M}_1=(0,0,a)^T\Rightarrow\boldsymbol{M}_0=(0,0,0)^T=$世界原点。いずれも正しい。

(3)

$\boldsymbol{M}_0=R\boldsymbol{M}_1+\boldsymbol{t}$ に対し基本行列は $E=[\boldsymbol{t}]_\times R$。$\boldsymbol{t}=(-a,0,a)^T$ より $$[\boldsymbol{t}]_\times=\begin{pmatrix}0&-a&0\\a&0&a\\0&-a&0\end{pmatrix},\qquad E=[\boldsymbol{t}]_\times R=a\begin{pmatrix}0&-1&0\\-1&0&1\\0&-1&0\end{pmatrix}$$ スケール不定なので $E\propto\begin{pmatrix}0&-1&0\\-1&0&1\\0&-1&0\end{pmatrix}$。正規化画像座標 $\hat{\boldsymbol{x}}_0,\hat{\boldsymbol{x}}_1$ に対し $\hat{\boldsymbol{x}}_0^{\,T}E\,\hat{\boldsymbol{x}}_1=0$ を満たす。

(4)

世界→カメラ0は $R_0=I,\ \boldsymbol{t}_0=(0,0,a)^T$。よって $$s\begin{pmatrix}u_0\\v_0\\1\end{pmatrix}=P_0\begin{pmatrix}X_w\\Y_w\\Z_w\\1\end{pmatrix},\quad P_0=K[I\,|\,\boldsymbol{t}_0]=\begin{pmatrix}400&0&400&400a\\0&400&300&300a\\0&0&1&a\end{pmatrix}$$

(5)

世界→カメラ1は $R_1=R^{T}$、$\boldsymbol{t}_1=R^{T}\{(0,0,a)^T-\boldsymbol{t}\}=R^{T}(a,0,0)^T=(0,0,a)^T$（世界原点はカメラ1から見ても距離 $a$ の正面）。よって $$P_1=K[R^{T}\,|\,\boldsymbol{t}_1]=\begin{pmatrix}400&0&-400&400a\\300&400&0&300a\\1&0&0&a\end{pmatrix}$$ 検算：世界原点 $\to(400,300)$、$C_0=(0,0,-a)\to(800,300)$（＝(7)のエピポール）。正しい。

(6)

視点は $C_1=(-a,0,0)$、視線（$Z_1$ 軸）は世界原点方向、水平画角 $90^\circ$。右手座標系として記述すると

#declare A = 1;   // a の値
camera{
    location <-A, 0, 0>
    look_at  <0, 0, 0>
    angle    90
}

(7)

エピポールは相手カメラの投影中心を自カメラの画像に投影した点である。

カメラ0のエピポール：$C_1$ のカメラ0座標は $\boldsymbol{t}=(-a,0,a)^T$ なので $$u_0=400\cdot\frac{-a}{a}+400=0,\quad v_0=400\cdot\frac{0}{a}+300=300$$ $\boldsymbol{e}_0=(0,\ 300)$（画像左端上にある）。

カメラ1のエピポール：$C_0$ のカメラ1座標は $R^{T}(\boldsymbol{0}-\boldsymbol{t})=(a,0,a)^T$ なので $$u_1=400\cdot\frac{a}{a}+400=800,\quad v_1=300$$ $\boldsymbol{e}_1=(800,\ 300)$（画像右端上にある）。ともに $a$ によらない。

(8)

回転は $R=R_y(90^\circ)$、軸は $Y_w=(0,1,0)$、角 $\theta=90^\circ$。回転四元数は $$q=\Bigl(\cos\tfrac{\theta}{2};\ 0,\ \sin\tfrac{\theta}{2},\ 0\Bigr)=\Bigl(\tfrac{\sqrt2}{2};\ 0,\ \tfrac{\sqrt2}{2},\ 0\Bigr)$$ 一致の確認：$q=(w;0,y,0)$ が表す回転行列は一般に $$\begin{pmatrix}1-2y^2&0&2wy\\0&1&0\\-2wy&0&1-2y^2\end{pmatrix}$$ $w=y=\tfrac{\sqrt2}{2}$ を代入すると $1-2y^2=0,\ 2wy=1$ となり $\begin{pmatrix}0&0&1\\0&1&0\\-1&0&0\end{pmatrix}=R$ に一致する。

(9)

手順①：デプス値からカメラ1座標を求める。 $$Z_1=d,\quad X_1=\frac{d}{400}(u_1^d-400),\quad Y_1=\frac{d}{400}(v_1^d-300)$$ 手順②：(2)の逆変換 $\boldsymbol{M}_w=R\{\boldsymbol{M}_1-(0,0,a)^T\}$ で世界座標へ戻す。$R$ は $(X_1,Y_1,Z_1)\mapsto(Z_1,\,Y_1,\,-X_1)$ を与えるので $$X_w=d-a,\qquad Y_w=\frac{d}{400}(v_1^d-300),\qquad Z_w=-\frac{d}{400}(u_1^d-400)=\frac{d}{400}(400-u_1^d)$$

(10)

この点のカメラ0座標は $(X_w,\,Y_w,\,Z_w+a)$。透視投影して $$u_0=\frac{400\,X_w}{Z_w+a}+400,\qquad v_0=\frac{400\,Y_w}{Z_w+a}+300,\qquad Z_w+a=\frac{d}{400}(400-u_1^d)+a$$ に(9)の値を代入すればよい。

参照：距離画像→点群（B第4回 p.6）、ICP（B第4回 p.24）、符号付き距離場（B第4回 p.29, p.30）、Marching Cubes（B第4回 p.34）。

①　3次元点群（点群）

②　ICP（Iterative Closest Point、反復最近接点）

③　最近接点（最も距離の近い点）

④　符号付き距離場（SDF：Signed Distance Field）

⑤　物体表面までの符号付き距離

⑥　マーチングキューブス（Marching Cubes）

参照：点群の位置合わせ・ICP・point-to-point / point-to-plane（B第4回 p.22, p.24, p.25）。

(1)

入力は位置合わせを行う2つの3次元点群（基準となるターゲット点群と、それに合わせるソース点群）。出力は、ソース点群をターゲット点群に最もよく重ね合わせる剛体変換（回転行列 $R$ と並進ベクトル $\boldsymbol{t}$）。目的は、同一物体を異なる方向からセンシングして得た複数の点群を共通座標系へ整列させることである。

(2)

まずソース点群の各点に対し、ターゲット点群の中で最近接点を対応点として探索する。次にその対応点組の距離の総和が最小となる回転 $R$ と並進 $\boldsymbol{t}$ を最小二乗法で推定し、ソース点群を変換する。最近接点の探索と変換の推定を反復し、変換量の変化が十分小さくなった（対応点が十分一致した）ところで収束とみなして終了する。

(3)

point-to-point は、対応点間のユークリッド距離 $\lVert\boldsymbol{p}_i^A-(R\boldsymbol{p}_i^B+\boldsymbol{t})\rVert^2$ の総和を最小化する。point-to-plane は、対応点からターゲット面（対応点における接平面）への距離、すなわち法線方向成分の二乗和を最小化する。後者は平面的な領域での滑りを許すため、平坦な部分が多い形状で収束が速く安定しやすい。

参照：3次ベジエ曲線の定義とバーンスタイン基底関数（B第2回 p.20）、対称性を用いた自己交差の解法（過去問F1型）。

3次ベジエ曲線は $P(t)=\sum_{i=0}^{3}B_i^3(t)P_i$、$B_0^3=(1-t)^3,\ B_1^3=3t(1-t)^2,\ B_2^3=3t^2(1-t),\ B_3^3=t^3\ (0\le t\le1)$。制御点を代入して成分ごとに展開すると $$x(t)=22t^3-33t^2+15t-2,\qquad y(t)=12t-12t^2$$

(1)

配置が対称で $x(1-t)=-x(t)$、$y(1-t)=y(t)$ が成り立つ。よって $t_1$ と $t_2=1-t_1\ (t_1\ne t_2)$ は同じ $y$ をもち、さらに同一点を通る（自己交差する）ためには $x(t_1)=-x(t_1)$、すなわち $x=0$ が必要。 $$x(t)=22t^3-33t^2+15t-2=(2t-1)(11t^2-11t+2)=0$$ より $t=\dfrac12,\ \dfrac{11\pm\sqrt{33}}{22}$。このうち互いに $t_2=1-t_1$ の関係にある対 $$t=\frac{11-\sqrt{33}}{22}\ \ \text{および}\ \ t=\frac{11+\sqrt{33}}{22}$$ が自己交差を与える（$t=\tfrac12$ は単独で $x=0$ を横切るだけ）。このとき $11t^2-11t+2=0$ すなわち $t-t^2=\dfrac{2}{11}$ なので $$x=0,\qquad y=12(t-t^2)=12\cdot\frac{2}{11}=\frac{24}{11}$$ よって自己交差する点の座標は $\left(0,\ \dfrac{24}{11}\right)$。

(2)

$y(t)=12t-12t^2$ より $\dfrac{dy}{dt}=12-24t=0\Rightarrow t=\dfrac12$（区間内、上に凸なので最大）。このとき $x(\tfrac12)=0$、$y(\tfrac12)=12\cdot\tfrac12-12\cdot\tfrac14=3$。よって座標は $(0,\ 3)$。

参照：オイラーの公式 $v-e+f=2$・オイラー操作（B第5回 p.46）、貼り合わせ操作での増分の数え方（B第6回 p.5）、CSG木・和演算 union（B第5回 p.17, p.24）。

(1)

立方体は頂点 $v=8$、辺 $e=12$、面 $f=6$ である。 $$v-e+f=8-12+6=2$$ となり、オイラーの公式を満たす。

(2)

立方体の1つの正方形面に、その面を底面とする四角錐を貼り合わせると、貼り合わせ面（底面の正方形）1枚が立体内部に消え、側面の三角形が4枚できるので面は $\Delta f=-1+4=+3$。四角錐の頂点（apex）1個が増えて $\Delta v=+1$。この頂点と底面の4頂点を結ぶ辺が4本増えて $\Delta e=+4$。よって $$\Delta v-\Delta e+\Delta f=1-4+3=0$$ となって $v-e+f$ の値は変化しない。したがってこの操作は位相を保つオイラー操作である。

(3)

6面すべてに(2)の操作を施すと $$v=8+6\times1=14,\quad e=12+6\times4=36,\quad f=6+6\times3=24$$ $$v-e+f=14-36+24=2$$ となり、この星型の立方体もオイラーの公式を満たす。

(4)

立方体の1辺の長さを $L$ とする。立方体と、各面に底面を一致させて貼り合わせた6個の四角錐（いずれも底面が1辺 $L$ の正方形）の和演算で得られる。

和 (union)
├─ 立方体（1辺 L）
├─ 四角錐 P1（面1 に貼り合わせ）
├─ 四角錐 P2（面2 に貼り合わせ）
│    …
└─ 四角錐 P6（面6 に貼り合わせ）

#include "colors.inc"

camera{
    location <30, 20, -100>
    look_at  <30, 20, 0>
    angle    90
}

light_source{<30, 20, -100> color White*2}

triangle{
    <0, 0, 1>, <0, 60, 3>, <90, 0, 4>
    pigment{color Green}
}

参照：plane の構文と平面・物体の前後関係（B第7回 p.31）、colors.inc の色（A第5回 p.25）、画像外枠＝距離×tan(半画角)・アスペクト比 4:3（A第5回 p.21）、頂点 z 値の線形補間による前後判定。

(1)

法線 $\langle0,0,1\rangle$、原点からの距離 2 の無限平面を追加する。

plane{
    <0, 0, 1>, 2
    pigment{color Red}
}

(2)

三角形の頂点の $z$ 値は $(0,0)$ で 1、$(0,60)$ で 3、$(90,0)$ で 4 なので、三角形上の $z$ 値は $$z=1+\frac{x}{30}+\frac{y}{30}$$ と線形補間される。$z=2$ との交線は $x+y=30$ であり、辺 $(0,0)$–$(0,60)$ とは点 $(0,30,2)$ で、辺 $(0,0)$–$(90,0)$ とは点 $(30,0,2)$ で交わる（辺 $(0,60)$–$(90,0)$ とはセグメント内で交わらない）。カメラは $z=-100$ から $+z$ 方向を見るので $z$ が小さいほど手前である。したがって三角形のうち $z<2$（$x+y<30$）の部分、すなわち頂点 $(0,0,1)$ を含む小三角形だけが赤い平面より手前にあって緑色に見え、$z>2$ の残り（頂点 $(0,60,3)$・$(90,0,4)$ 側の四角形）は赤い平面の背後に隠れる。無限平面は画像全面を覆う。画角90度・距離100より画像外枠は水平半幅 $100\tan45^\circ=100$、アスペクト比 4:3 より垂直半幅 75 で、$x\in(-70,130),\ y\in(-55,95)$。三角形は全体が枠内に収まる。

見取り図：

参照：背面消去（面法線と視線ベクトルの内積）とその限界（B第7回 p.17–19）、隠面消去法の分類（B第7回 p.21）。

背面消去は、面法線 $\boldsymbol{n}$ と視点方向のベクトルの内積が負となる面（視点から見て裏を向く背面）を、面ごとに独立に除外する処理である。これは面が視点に対して表か裏かだけを判定するもので、面どうしの遮蔽関係は考慮しない。したがって一般には、表を向いた面（正面）であっても、それより手前にある別の正面の面に遮られて見えない部分が残りうる。背面消去はこの面間の遮蔽を解消できないため、隠面消去は完成しない。「隠面消去された面は背面消去でも除かれる」は成り立つが、その逆は成り立たない。

ただし、対象が単一の凸多面体（凸立体）である場合は、視点から見える面はすべて正面であり、正面の面が他の面に遮られることがない。したがってこの場合に限り、背面消去だけで隠面消去が完成する。一般の非凸立体や複数物体では、Zバッファ法などの画像空間アルゴリズムによる面間の前後比較が別途必要になる。