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 detection與Shi-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
範本追蹤。給定圖片片段,找到移動軌跡。
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🚧
Scene Modeling🚧
簡介
Scene Reconstruction(Structure From Motion)
重建。拍攝多張相片(影片),源自各種方位。建立模型。
Scene Compositing(Match Move)
合成。拍攝多張相片(影片),源自各種方位。將多餘物品塞入場景,配合相機方位。
Scene Synthesis
生成。家居擺設。
Scene Segmentation
分割。找出模型。
Scene Labeling
標記。鑑定技能。
目前的做法是圖片辨識。
Light Field🚧
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
貼材質。在模型上貼材質。