Blog

如何保留重要的資訊又縮減尺寸，其中定義甚麼是重要，甚麼是不重要的影像資訊 Basie Idea 不重要的資訊代表影像梯度變化小的地方，定義一個energy function/ 使用梯度來作為energy function的原因： 邊界代表紋理資訊 人眼對edge比較敏感，平滑處就可以被視為不重要資訊 概念很簡單 左圖對整張影像濾除低能量pixel 中間對每行方向濾除最低能量pixel 右圖對每列方向濾除最低能量pixel，看起來結果較好一點，但仍看得出來階梯處有扭曲的感覺 Seam Carving 接縫裁剪(Seam Carving)，是一個可以針對圖像內容做正確縮放的算法。概念上，算法會找出一系列的接縫（seam）（接縫是在圖像中最不重要的一連串像素），接著利用接縫對圖像做縮放。如果是要縮小圖像，則移除這些接縫，若是放大，則在這些接縫的位置上，插入一些像素。接縫裁剪可以人工定義一些不會被修改的像素區域，也可以從圖像中移除整個物體。by wiki 流程 輸入要變化的影像與尺寸 計算energy function 從energy function計算seam cost $M$ 選出裁切方向最小的seam carving 濾除足夠多的行列直到與輸入尺寸相同 計算Seam cost的部分，主要使用動態規劃的方法來實作，因為每次計算seam cost時必須計算與鄰居周圍的相關資訊 重新定義參數： $E$是前面提到的energy function，$E(i,j)是在影像上對應i,j的座標點能量值$ $M$是seam cost，用來評估將該點作為seam carving時依據，$M$的計算公式： $M(i,j) = E(i,j) + min(M(i-1, j-1), M(i-1,j), M(i-1, j+1))$ 可以從公式看到，seam cost所代表的意義就是由該點所對應的energy function，加上鄰近上方像素的最小點，就可以當作今天要把該點去除或展開時的一個成本，成本高低代表該點是重要資訊的指標 Dynamic Programming 由於seam cost公式是計算矩陣$M$，其中又參考到自身周圍計算過的數值，因此需要用到動態規劃(Dynamic Programming, DP) $M(i,j) = E(i,j) + min(M(i-1, j-1), M(i-1,j), M(i-1, j+1))$ Searching for Minimum 得到seam cost矩陣後，從最下方開始尋找最小向上路徑 ...

影像調整大小在生活上隨處可見，如在不同的螢幕解析度下就必須對輸入的影像進行變化 但改變的同時常常造成比較重要的影像位置失去原先的樣貌特性 該節就開始探討在Resize的同時又可以保持重要的影像訊息 Content-aware Retargeting 上圖可以看到紅區域處是重要的資訊，若直接改變影像尺寸會造成人物的變形 若僅延展在影像中間處的雪地與天空區塊，就可以保留重要資訊 問題定義 輸入影像尺寸$n \times m$與新的尺寸$n’ \times m'$ 輸出影像$n’ \times m’$並保有與原影像一樣好的影像細節 但所謂好的影像縮放結果沒辦法用量化的方式來定義 我們也不知道甚麼叫做重要的影像資訊，也許每個人對重要的影像區塊看法都不同 影像重要性(顯著性) 量測 定義一個function來找出影像"重要"的地方 重要指的可以是人眼經常會去特別關注的地方 相關論文與應用 Setlur, Vidya, et al. “Automatic image retargeting.” Proceedings of the 4th international conference on Mobile and ubiquitous multimedia. 2005. Gal, Ran, Olga Sorkine, and Daniel Cohen-Or. “Feature-Aware Texturing.” Rendering Techniques 2006.17th (2006): 2.

論文名稱：Mean Shift, Mode Seeking, and Clustering 流程： 隨機初始化起點與視窗$h$ 計算中心重心 移動搜索視窗到重心位置 重複步驟2~3直到收斂 重心計算公式： 其中$x是輸入的資料集,x={x_1,x_2…x_k},x_i是第i個資料$ $S_h是視窗半徑為h$的區域 mean shift 演算法範例： 圖(1)~(3)計算重心並移動，移動幅度(1)>(2)>(3)，圖(4)收斂 特性 Unsupervised learning 跟k-means不同的是，不用先假設資料有幾群 調整一個視窗大小參數，並且具有物理意義，視窗大小代表中心的搜索範圍，但視窗範圍會影響到輸出結果 對outliers具有穩健性 資料維度越高，運算越巨大 參考 ML - Clustering Mean Shift Algorithm

k means clustering 流程 隨機初始化群心$c_1,…,c_K$與迭代次數$t$ 計算隸屬矩陣$\delta^t$，得到新的分群結果 由分群結果更新群心 增加迭代次數$t$，重複步驟2~4，直到到達設定停止條件(到達迭代次數上限或群心不在大幅變動) 參數定義： $t$：迭代次數 $K$：群數 $N$：輸入的資料數量 $x_j$：輸入的第$j$筆資料 $c^t_i$：第$t$次第$k$群的群心 $\delta^t$：第$t$次的隸屬矩陣，定義第$j$個資料對應第$c$個群心的距離，矩陣大小為K*N 流程： k means clustering特性 不同的初始化群心位置會有不同結果 對球形的數據有較好的fit結果 * 需要決定參數k 選擇參數k的方法 不同的群數使得結果不同，決定群數變成非常重要的問題 以分群的角度來看，分群的目的為，群內的變異性越小越好，群跟群之間的變異性越大越好 翻成白話來說就是：同一群內的資料越聚集越好，群跟群之間的資料離越遠越好 這裡介紹一個常用來自動選擇群數k的方法：Elbow method Elbow Method Elbow method的核心思想是，運用前面所說分群的特性來定義一個objective function來找到輸入資料對應最好的分群結果，通常使用群內樣本的距離和來量測 如下圖所示，選擇的k值隨著群數分越多，數值越小，但可以發現前期變化很大，到後面逐漸變小 而群數設定為2時的轉折最大，像是手肘彎曲的地方，這時elbow method就選擇該輸入的資料分為2群最適合 k-means 優缺點 Unsupervised learning 原理簡單好實現 可擴展至大型的數據集，適應不同的dataset 保證收斂 可以預先初始化群心中心 需先設定參數k(使用elbow method可以解決這問題) 輸入資料需標準化到同一尺度空間 初始化群中心影響分群結果 群心容易被異常資料(outliers)影響，造成群心偏移 容易陷入局部最佳解 參考 k-Means Advantages and Disadvantages

在stanford中的cs131課程提到的Graph-based segmentation，剛好介紹到這篇論文，就來研讀一下。 論文網址：Felzenszwalb, Pedro F., and Daniel P. Huttenlocher. “Efficient graph-based image segmentation.” International journal of computer vision 59.2 (2004): 167-181. 本篇論文是基於圖的(Graph-Based)影像分割演算法，提出一個有效率的影像分割方式，並且影像分群的的結果是有意義的。 主要動機 過往的某些方法並沒有考慮到漸變的影像，使得分割結果不符合預期 問題描述 影像 $G$ 是由像素集合V與無向邊 $E$ 連接一組點對$(v_i, v_j)$，並且具有權重 $w(v_i, v_j)$，權重是由兩像素點之間的差異來產生 S是在影像G分割出來的一個區塊，並以 $G’=(V,E’)$ 表示， 其中$ E’\in E$ 斷定為分割公式定義 斷定兩區域$C_1,C2$是否存在邊界分割，是基於量測兩個區域$C_1,C2$之間的相異性，以及評估區塊內部各自元素的相異性程度 $Dif(C_1, C_2)是兩區域之間的差異，差異是指將組件C_1中的節點v_i連接到C_2中的節點v_j的最小權重邊$ $Int(C)$是計算同一區域內兩兩像素點之間的最大權重 $MInt(C_1, C_2)$是個別區域內的內部差異 $\tau(C)是一個閾值，由設定參數k來控制最後產生的群集大小$ 演算法流程 計算每個像素8相連或4相連的不相似度 將edge E按照不相似度non-decreasing排序edge權重得到$o_1,o_2,…,o_m$ 開始分割動作，初始分割區域為$S^0$, 其中每個像素點$v_i$是獨立的一個區域 重複步驟並定義$q=1,…m$ $S^q$的初始區域是由$S^{q-1}$組成, 定義$v_i, v_j$ 是一組前q小的edge權重對應的點對$o_q = (v_i, v_j) $ 檢查點對合成條件是否符合, 合成條件參考$D(C1, C2)$, 符合則合併, 否則維持分割結果S並繼續執行到結束 測試結果 使用的測試資料是COIL database， 對不同的影像大小使用不同的參數k ...

影像分割目的 把屬於同一群的像素集合在一起 將想要做進一步分析的物件與背景分割出來，概念跟框選 ROI 相似，但是更精細的 ROI，把非物件的不相干雜訊濾除 視覺上分群的範例 依照格式塔原則進行分類，以 Gestalt 為名的完形心理學，概念#是人類對於任何視覺圖像的認知，是一種經過知覺系統組織後的形態與輪廓，而並非所有各自獨立部份的集合。 其中格式塔原則的一些特點： Similarity 相似性 Symmetry 對稱性 Common Fate 共同命運，同群在影像中表現出相同的移動方向性、趨勢 Proximity 相近性，物體距離相近時視為一群 clustering method 分群的概念是把一組資料依照距離或相似程度分成不同的群集 分群法是一種非監督式分群方法 相似度比對 常見的相似度比對方法有： Euclidean distance Cosine similarity 歐式距離： 餘弦相似性，概念是比對兩向量的夾角角度： 分群演算法理想特性 可擴縮性（Scalability） 可以處理不同的資料型態 簡單的參數調整與設定 可說明性，呈現的結果是可解釋的 約束性，演算法可由使用者預先設定的限制下動作 Agglomerative clustering 將每個資料點都視為一獨立的群 找出最相近的群集點對 將點對合併成一群 重複上述步驟直到合併結束 定義群集之間的相似性 點到點之間的平均距離 最小點距離 最大點距離 優缺點 好實現且應用廣泛 集群具有自適應形狀 提供階層式的集群 不需預設群數 可能會出現不均勻的群集結果 還是需要定義群集相似度閾值 時間複雜度 $O(n^3)$ 可能陷入局部最佳解 參考 視覺法則 – 格式塔原則

另一種描述影像特徵的方法，HoG(Histogram of Oriented Gradients)，方向梯度直方圖 特徵描述子 HoG 簡介 局部的物件外觀與形狀經常由局部亮度梯度或邊緣方向顯現出來，因此透過局部梯度資訊建立一個梯度角度直方圖的特徵 HoG 流程 把影像切分成多個小區塊(稱為 cells)，cells 的形狀可以是矩形或圓形，每個 cell 累加梯度方向的局部直方圖 把 cell 合成多個格子成為一個 block，對 block 內的亮度區域進行正規化 結果： 與 SIFT1 不同的地方 HoG 通常用來描述更大的影像區域，SIFT 用關鍵點來進行匹配 SIFT 是對整體梯度進行正規化，HoG 是使用周圍的 cell 區塊 參考 一文講解方向梯度直方圖（hog） A Gentle Introduction Into The Histogram Of Oriented Gradients

我們在上一回找到了角點，但如何利用關鍵點的周圍資訊，來讓彼此匹配，也許可以把角點周圍的像素區塊取出來匹配，但如果遇到兩張影像角度不同時如何匹配? SIFT descriptor(SIFT=Scale-Invariant Feature Transform) 建構一個旋轉不變性描述子 從 DoG 得到一個帶有尺度不變性的關鍵點 從關鍵點周圍資訊找出特徵角度(不直接旋轉個別影像區塊進行匹配，因為很慢) SIFT 流程 使用影像梯度計算關鍵點周圍的角度直方圖，並把角度切成八等分 把關鍵點周圍梯度值每 4x4 為一群，個別計算旋轉過的梯度方向直方圖 梯度的貢獻程度取決於距離，如果它在兩個直方圖位置的中間，它給兩個直方圖一半的貢獻 梯度直方圖的方向分為 8 份與每個區塊為 4x4 是由作者選出最佳的參數結果 8 方向的直方圖，4x4 個直方圖陣列，會有 8x4x4=128 個向量 SIFT 描述子是一個長度為 128 的向量，並有帶有旋轉不變性與尺度不變性 可以比較影像 A 與影像 B 的各自的向量來尋找配對的關鍵點 很大的影像梯度通常來自 3D 照明效果(如：眩光)，將 128 維向量最大數值限制在 0.2 內，計算完後再進行正規化(乘上 256) SIFT 測試結果 在隨機改變影像尺度、角度，再加上一定的 noise 的 dataset 下的特徵比對結果 在隨機改變影像尺度、角度、仿射變換並加入 2%的 noise 的 dataset，對 30000 個特徵進行最鄰近點搜尋的結果，測試穩定性 對測試資料進行 30 度的仿射變換與 2%的 noise 後提取特徵點，計算單點最鄰近搜尋的準確率 SIFT 結論 SIFT 是一個具有尺度不變性、旋轉不變性，並具有獨特性的關鍵點提取方法 有效率的計算速度，可以在一般的 PC 上做到接近即時處理的效果 論文中也展示使用關鍵點加上最鄰近搜尋來進行物件檢測 參考 David G. Lowe,“Distinctive Image Features from Scale-Invariant Keypoints”," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110 wiki-尺度不變特徵轉換

問題 Harris corner 沒有尺度不變性 在不同尺度下所呈現的角點響應函數都不同，Image 1 的最小圓圈範圍是跟 Image 2 最大圓圈範圍才會有相同的角點結果 解決方法 希望能設計一個 scale invariant detection function 可以讓每張影像都找得到一個穩定的尖峰，才能在多尺度搜尋時找到相同的結果 Scale Invariant Detection 使用 Laplacian 與 Difference of Gaussians kernel 來對影像進行不同尺度的縮放 Laplacian kernel $L = \sigma^2(G_{xx}(x,y,\sigma)+G_{yy}(x,y,\sigma))$ 其中 G 是高斯函數 $G(x,y,\sigma)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2+y^2}{2\sigma^2}}$ Difference of Gaussians(DoG) $DoG = G(x,y,k{\sigma}) - G(x,y,{\sigma}) $ 對影像逐漸加深模糊度，越模糊所保留的細節越少 高斯差所得到的影像細節隨著$\sigma$越大細節越粗糙 Scale Invariant Detections Harris-Laplacian:結合 Laplacian kernel 的 harris corner，並取出局部最大值作為結果 SIFT:使用 DoG 並對每個點取 3x3x3 鄰居 26 個點(不包含自己)，找出高斯差最小的數值

使用特徵點來尋找物件、定位、全景拼接 使用 Local Invariant Features 動機 全局特徵有它的限制性 增強對遮擋、角度變化的魯棒性 常見的方法 找到多個獨特的關鍵點 定義一個 window 大小把 key points 的的周圍資訊取出來 提取周圍資訊並做正規化 計算正規化區域的局部描述子，例如使用區域色彩資訊 匹配局部描述子 好的 Local Features 特性 區塊特徵萃取要有重複性與準確性 特徵是局部的獨特，對變形與雜亂背景有魯棒性 要能萃取夠多的特徵進行比對 計算方法越快越好 Harris Corner 設計準則：可以很簡單的用一個小視窗當作視野範圍辨認出角點 如果在角點，往任意方向移動這個小視窗應該會有很大的亮度變化 Formulation 移動小視窗的中心座標點$[x,y]到[x+u,y+v]$來計算移動後的亮度變化 量測單點亮度變化公式： $ I(x+u,y+v) - I(x,y) $ 計算整個小視窗內的亮度變化公式： $\sum_{xy}w(x,y)[I(x+u,y+v)-I(x,y)]^2 $ 其中 window function 可以使用加權函數、高斯函數 利用泰勒展開式對$I(x+u,y+v)$ 其中一階近似為 將一階近似帶入 harris corner 公式 最終 其中 M 是一個 2x2 的矩陣用來計算影像導數 M 是對稱矩陣，求其特徵值 可以把矩陣 M 想像成是一個橢圓型，其中它的軸長是$\lambda_1 , \lambda_2$，方向由 R 定義 可以看到$\lambda_1 , \lambda_2$ 與影像的關係，而我們只關心 corner 的地方，試著將 corner 位置的值透過一個公式過濾出來 ...