Camera(Under Construction!)

Camera

將3D物體轉換成2D圖片的機制。

程式碼資料集。知名函式庫如jsfeat

Image Tracking(Under Construction!)

簡介

圖片的特殊武器:Blob

針對人類視覺系統的特性,擷取圖片引人注目的地方。

Laplacian of Gaussians (LoG):圖片套用各種寬度(變異數)的LoG filter。針對一種寬度,找到區域極大值,推定為圖片重點,重點的半徑範圍是LoG filter的變異數。

difference of Gaussians (DoG):LoG的高速近似算法。改為套用各種寬度的DoG filter。換句話說,圖片縮放成各種尺寸,套用同樣寬度的DoG filter。換句話說,Gaussian pyramid,從中選擇尺寸足夠大的圖片來縮小(因為放大會失真),以得到各種尺寸的圖片;寬度最接近的兩兩圖片,直接相減。【尚待確認:直接相減】

圖片的特殊武器:橢圓形Blob

引人注目的地方,莫名其妙是圓形。由於尺寸、形狀皆不夠精準,所以調整成橢圓形。不過還是很莫名其妙。

automatic scale selection:調整blob尺寸。一、找到一個blob之後,微調blob尺寸。二、計算blob裡面(或者周圍)所有像素的梯度的長度的平均數。三、平均數依照blob尺寸排列,形成一串數列。四、區域極大值所在之處,表示梯度變化最大,推定為正確尺寸。當區域極大值不只一個,推定blob不存在。

高速近似算法:一、各種寬度的blob,改成各種尺寸的圖片(實務:邊長屢乘0.7倍)。二、微調blob尺寸,改為尺寸相鄰的兩張圖片的一次內插(實務:微調範圍是該圖的0.7至1.4倍,自行設定間距)。三、統計blob內部的梯度平均數,改為擷取blob中心的DoG值。四、簡單一句話歸納:長、寬、縮放尺寸,在三維空間中求得DoG區域最小值。

affine shape adaptation:調整blob形狀。取得blob內的像素,求得二次動差矩陣總和,實施特徵分解,得到橢圓形,設為新blob。重複上述動作,直至blob形狀不變。

另類觀點:取得blob內的像素。一個像素的X梯度、Y梯度,視作一個二維點座標;所有像素的X梯度、Y梯度,視作一群二維點座標。計算principal component analysis(不必預先減去平均數),得到橢圓形。

Ix(x,y) = I(x,y) - I(x-1,y) = x gradient at (x,y)
Iy(x,y) = I(x,y) - I(x,y-1) = y gradient at (x,y)

P = [ Ix(x,y) Ix(x,y+1) Ix(x,y+2) ... Ix(x+1,y) Ix(x+1,y+1) ... ]
    [ Iy(x,y) Iy(x,y+1) Iy(x,y+2) ... Iy(x+1,y) Iy(x+1,y+1) ... ]

PᵀP = [ ∑IxIx ∑IyIx ] = ∑C(x,y) 
      [ ∑IxIy ∑IyIy ]

C(x,y) = [ IxIx IyIx ] = second monent matrix = structure tensor
         [ IxIy IyIy ]

Image Feature Detection

特徵偵測。找到圖片所含有的特殊結構、邊邊角角。

Hessian keypoint detection:偵測頂點、端點、臨界點。一、求每個像素的det(Hessian matrix)。二、由於綜合了X梯度與Y梯度,因此數值偏高者,多半為頂點、端點、臨界點。

I(x,y) = R/G/B pixel value at (x,y)
Ix(x,y) = I(x,y) - I(x-1,y) = x gradient at (x,y)
Iy(x,y) = I(x,y) - I(x,y-1) = y gradient at (x,y)
Ixy(x,y) = Ix(x,y) - Ix(x,y-1)
         = [I(x,y) - I(x-1,y)] - [I(x,y-1) - I(x-1,y-1)]
         = y gradient of x gradient at (x,y)

     ∂I          ∂²I    
Ix = ――   Ixy = ―――――   H = [ Ixx Iyx ]   det(H) = Ixx Iyy - Ixy Iyx
     ∂x         ∂x ∂y       [ Ixy Iyy ]          = Ixx Iyy - (Ixy)²

Harris corner detectionShi-Tomasi corner detection:偵測角。一、擷取一塊區域,求梯度。二、套用窗函數Gaussian window,專注於區域中心附近的梯度。三、求得二次動差矩陣總和,實施特徵分解,以兩個特徵值的絕對值大小,判斷該區域是否有角。兩值都足夠大,就表示梯度們有兩個主要方向,就表示有兩條較直的邊緣,就表示有角。四、高速算法是改用det和trace來判斷。五、原理類似於principal component analysis。

Marr–Hildreth edge detection:偵測邊緣。LoG filter或者DoG filter,過零處(正負變化之處)當作邊緣。

Canny edge detection:偵測邊緣。一、平滑兼去噪:Gaussian filter。二、求邊緣:求得梯度長度、梯度方向。三、找到最明顯的邊緣:若梯度長度為區域極大值,則保留,否則設為零。區域極大值是依照梯度方向取得前後兩個像素,僅三個像素比較梯度長度。四、清除不明顯的邊緣:設定門檻,梯度長度太短者設為零。五、銜接邊緣。

Hough line transform:偵測直線,甚至偵測線段。一、求邊緣:求得梯度長度,設定門檻。二、針對一個像素(x,y),窮舉穿過此像素的直線們,求得原點在直線上的投影點,再換成極座標表示法(r,θ),一條直線對應一個點,直線們對應一條曲線r = xcosθ + ysinθ。一個像素得到一條曲線。三、圖片每個像素皆換成曲線。曲線們的交點,即是穿過大量像素的直線!四、建立細膩方格紙(離散化),曲線穿過方格,則投票加一,得票多的方格當作交點。五、轉換過程是三步驟:對偶、轉成極座標、投票。

Hough cycle transform:偵測圓。窮舉各種半徑。針對一個像素(x,y),窮舉穿過此像素的所有圓;圓穿過像素,則投票加一,得票多的像素就是圓心。

line segment detection:偵測線段。

Image Feature Detection再進化

例如corner,只有位移不變、旋轉不變。現在還要縮放不變。方法是把corner補強為橢圓形blob。

Harris affine region detector:圖片縮放成各種尺寸,每張圖都找corner。每一個corner,以自己為中心,嘗試找橢圓形blob。

Hessian affine region detector:找corner改為找keypoint,其餘相同。

maximally stable extremal regions

Kadir–Brady saliency detector

Image Feature Description

特徵描述。將圖片獨特之處寫成數值,以供辨識比對。

histograms of oriented gradients (HOG):一個像素進行投票,梯度長度是持票數,梯度角度(無視正反方向,僅0°到180°)決定投票箱編號。180°等分成9個箱子。一個像素投票給最鄰近的兩個箱子,與箱子中心的距離(角度差)作為投票比例。

圖片分解成大量16×16區域,交疊一半。一個區域256個像素實施投票,得到9個數字,RGB分開就是9×3個數字。一個區域的數字,依序串成一串,當作特徵描述。

scale-invariant feature transform (SIFT):一個像素進行投票,梯度長度是持票數,梯度角度決定投票箱編號。360°等分成8個箱子。一個像素投票給一個箱子。

實施Harris affine region detector,得到大量區域。針對一個區域,切成4×4宮格,一個宮格所有像素實施投票,得到8個數字,所有宮格就是4×4×8=128個數字,RGB分開就是128×3個數字。一個區域的數字,依序串成一串,當作特徵描述。

speeded up robust features (SURF):SIFT的高速算法。

BRIEF – Binary Robust Independent Elementary Features
BRISK – Binary Robust Invariant Scalable Keypoints
ORB   – Oriented FAST and Rotated BRIEF
FREAK – Fast Retina Keypoint
KAZE  – 
AKAZE – Accelerated-KAZE

Image Feature Matching

特徵匹配。兩張圖片,找到引人注目的地方,找到對應。

KNN Match
Radius Match
Flann Based Matcher
RANSAC

Video Tracking(Under Construction!)

簡介

圖片的數學運算:Alignment

物體不斷移動,物體於每張圖片的位置、形狀都略有差異。我們可以透過前面章節的feature detection、feature description,擷取物體的大致範圍,但是如何精準得到物體移動軌跡呢?

像素們一齊移動,欲求軌跡。像素們一齊實施函數變換,欲求函數。此問題即是Alignment,每個點(像素)另外附帶數值(像素值);點的位置要盡量對齊,點的數值也要盡量相同。

Kanade–Lucas–Tomasi algorithm:一、假設只有translation。二、令兩張圖的平方誤差最小。三、泰勒展開,以零階與一階導數,近似原式。四、實施gradient descent或者Euler extrapolation。

圖片的特殊武器:Optical Flow

Kanade–Lucas–Tomasi algorithm的高速近似算法。一、增加了時間維度。二、假設像素們位移之後完全相符,原式與零階導數完全相等。兩者相消後,得到「泰勒展開一階導數等於零」的結論,得到一道簡潔的一次方程式。

一個像素構成一道一次方程式,所有像素構成一個一次方程組(矩陣恰是二次動差矩陣總和)。求解,即得位移量。

然而,正常情況下,像素們位移之後不可能完全相符。前述假設,邏輯錯誤,最後得到歪解。憑感覺瞎搞,但是算得快。

「泰勒展開一階導數等於零」,整個式子除以時間,就得到像素速度與亮度的關係式。計算學家取了一個文雅的名稱叫做「光流」。以光流的觀點,重新解釋整件事:

假定像素亮度不變、位置會變;欲求像素的移動速度,移動速度表示成向量。三個維度:長、寬、時間。像素位置改變,泰勒展開取到一階導數,原式與零階導數相消:梯度在「像素的移動距離向量」上的點積(投影)等於零。整個式子除以一單位時間:梯度在「像素的移動速度向量」上的點積(投影)等於零。此投影量,理想狀態是零,但是通常不是零。我們希望投影量越小越好。

Lucas–Kanade algorithm:「投影量」越小越好。一、因為是歪解,所以只好用遞推法趨近正解。二、遞推法,以當前移動速度來移動像素,再求得新的移動速度,直到收斂。三、縮放法,Gaussian pyramid,從最小的圖片(最大的範圍)開始實施,逐步縮小範圍。四、translation可以推廣成affine transform。請參考這篇講義

Horn–Schunck algorithm:「投影量」與「速度向量的長度」越小越好。scalarization。

EpicFlow:「投影量」與「速度向量的長度」與「邊緣匹配的差異」越小越好。scalarization。

Image Template Tracking

範本追蹤。給定圖片片段,找到移動軌跡。

Lucas–Kanade algorithm

Image Feature Tracking

特徵追蹤。給定圖片特徵,找到移動軌跡。

Kanade–Lucas–Tomasi algorithm

Video Object Tracking(Video Object Matching)

物體追蹤。指定圖片當中物體,找到移動軌跡。

進階應用有複數物體追蹤群眾計數

dense tracking:warping + template matching + template tracking。

sparse tracking:feature detection + feature matching + feature tracking。

online optimization:以histogram或SIFT的相似程度作為函數,實施mean shift或particle filter。

neural network:

Video Magnification

放大。以高幀率高解析度的攝影機進行拍攝,觀察物體極短時間、極小範圍的微小變化。應用範圍很廣

Camera Tracking(Under Construction!)

簡介

物體分解成點的觀點

   camera calibration
1. 一臺相機不動,給定很多的物體的表面座標,拍一張相片,算相機的位置、焦距、方向。

   ( 上古時代 )

   cemera calibration
2. 一臺相機不動,給定平坦物體的表面座標,物體移動,各拍一張相片,算上述東東。

   ( http://research.microsoft.com/en-us/um/people/zhang/Calib/  十幾年前)

   camera tracking
3. 一臺相機一直動,想做是多臺相機,各拍一張相片,算每個相機的位置、焦距、方向。

   ( voodoo / 新版的 blender 有這功能 )

   structure from motion
4. 承上,找到所有物體的3d座標

   point cloud to mesh
5. 承上,物體3d座標重新拼成MESH。

   match move
6. 一臺相機一直動,把東西塞進去場景裡面。

   augmented reality
7. 承上,塞進去的東西可以跟場景互動,例如碰撞偵測。

相機的數學知識:Perspective Projection

一臺相機。拍攝景物,得到相片。

3D world coordinates ↦ 2D image coordinates: P = K[R|t]
1. intrinsics matrix [R|t]: camera position and orientation
   (rigid transfomation, orthonormal matrix)
2. extrinsics matrix K: focal length, principal point, skew, aspect ratio
   (upper triangular matrix)

相機的數學知識:Epipolar Geometry

兩臺相機。拍攝兩張相片,源自兩種方位。兩張相片的對應點、對應線。主題曲

epipolar plane: triangle (eye o1, eye o2, scene x)
epipolar point: intersection e of line (eye o1, eye o2) and image
Ee1 = 0, e2ᵀE = 0
epipolar line:  point x in image1 ↦ line l in image2
Ex1 = l2, Eᵀx2 = l1
essential matrix:   xᵀEx = 0                  (world coordinate)
fundamental matrix: xᵀFx = (K⁻¹x)ᵀE(K⁻¹x) = 0 (image coordinate)
8-point algorithm: solve F. SVD with rank(F) = 2.
Nistér's 5pt Algorithm: solve polynomial of degree 10.
Lui–Drummond Iterative 5pt Algorithm: https://www.reddit.com/r/computervision/comments/cr8jgw/

使用image feature matching擷取圖片特徵。

相機的數學知識:Trifocal Tensor

三臺相機。三點定位。楊戩。

Camera Calibration(Camera Resection)

校準。拍攝多張相片,源自各種方位。求出相機參數,例如焦距、曲率。另外求出相機相對於物體的位置,例如位移、旋轉。

Image Registration

配準。拍攝多張相片,源自各種方位。找到每張相片的對應特徵,將特徵座標整合到世界座標系,得到點雲。

Camera Tracking(Bundle Adjustment)

追蹤。拍攝多張相片,源自各種方位。求出每張相片的相機方位,將相機方位整合到世界座標系。

bundle adjustment: solve projected points and camera positions
                   (point cloud registration with camera position)
algorithm: Nonlinear Least Squares
           Gauss–Newton Algorithm / Levenberg–Marquardt Algorithm

Photo Stitching(Under Construction!)

Image Alignment

對齊。拍攝多張相片,源自各種方位。相片實施三維幾何變換,整合到世界座標系。

進階應用有矯正變形圖片GPS

Image Stitching(Image Mosaicing)(Panorama)

縫合。拍攝多張相片,源自各種方位。銜接成一張寬廣相片,稱作環景照。經典範例是谷歌街景這裡有作品實作

每張相片因為光線角度導致色彩差異、因為廣角鏡頭導致景物扭曲。需要校正亮度、曲線扳直、填補像素、裁切圖片。

Scene Modeling(Under Construction!)

簡介

Scene Reconstruction(Structure From Motion)

重建。拍攝多張相片(影片),源自各種方位。建立模型。

Scene Compositing(Match Move)

合成。拍攝多張相片(影片),源自各種方位。將多餘物品塞入場景,配合相機方位。

Scene Synthesis

生成。家居擺設。

Scene Segmentation

分割。找出模型。

Scene Labeling

標記。鑑定技能。

目前的做法是圖片辨識。

Light Field(Under Construction)

Light Field

光場。三維空間的每個地點、每種方向,各有一個光線顏色值。空氣所在之處通常是透明、不存在數值。

Light Field Camera

光場相機。有如方格馬賽克的玻璃窗,每一格都可以看到全景,但是視角略有不同。

設置大量底片,底片位置略有差異。同時拍攝大量相片,之後可以重新對焦,得到各種焦距的相片。

http://stanford.edu/class/ee367/class9.pdf

Light Field Transport

http://www.cs.columbia.edu/CAVE/projects/lightfield_transfer/

Image-Based Modeling(Under Construction!)

Intrinsic Image

真相。去除光線影響,還原物體的真實顏色。

Image-based Modeling

拍攝相片,建立模型。可以想成是3D Graphics的反運算。

平面變立體、2D變3D。根據像素顏色,推論模型形狀。像素值,是素材與光線的綜合結果。去除素材影響,則得光線。再從光線強度,推估光線入射角,得到表面法向量。

這件事聽起來很蠢。想要建立模型,直接使用偵測模型的器材即可,何必使用相機?原因是幾乎人人隨身攜帶智慧型手機,那上面裝著計算機和相機;但是不是人人都有深度感測儀。

Shape From Shading:拍攝一張相片。
Photometric Stereo:拍攝多張相片,相機固定方位,光源源自各種方位。
View Synthesis:拍攝多張相片,相機源自各種方位。
http://www.statfe.com/projects/csc5280_project3/index.html

Image-based Lighting

打光。拍攝多張相片,源自各種方位。偵測光源與光強,然後重新打光。

拍攝金屬球:相機對準金屬球中心,拍攝金屬球的半面。根據相片的金屬球的半面的表面亮度,運用光線入射角等於折射角的原理,推測半個環境的光源與光強。調整相機方位(例如水平周轉一圈),以各種方位拍攝,得到整個環境的光源與光強。

拍攝平面鏡:相機拍攝平坦的反光物體,以各種方位拍攝(例如直線平移),推測光源與光強。

拍攝場景:建立模型,運用Graphics領域的光線追蹤演算法,推測光源與光強。

Image-based Rendering

渲染。拍攝多張相片,源自各種方位。繪製模型。

Image-based Texturing

貼材質。在模型上貼材質。