Camera🚧

Camera

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

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

Image Tracking🚧

簡介

圖片的特殊武器: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🚧

簡介

圖片的數學運算: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🚧

簡介

物體分解成點的觀點

   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🚧

Image Alignment

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

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

Image Stitching(Image Mosaicing)(Panorama)

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

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

Scene Modeling🚧

簡介

Scene Reconstruction(Structure From Motion)

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

Scene Compositing(Match Move)

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

Scene Synthesis

生成。家居擺設。

Scene Segmentation

分割。找出模型。

Scene Labeling

標記。鑑定技能。

目前的做法是圖片辨識。

Light Field🚧

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🚧

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

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