cs131 lecture 11 Image Resizing-Seam Carving

Posted on 2021-04-10 Edited on 2023-09-01 In course Views:

如何保留重要的資訊又縮減尺寸，其中定義甚麼是重要，甚麼是不重要的影像資訊

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矩陣後，從最下方開始尋找最小向上路徑

搜尋方式是先選出下方最小起始點，向上沿著上方周圍三個鄰居來選擇最小數值，直到矩陣上方列

結果

一隻胖鳥經過Scaling瘦身成功，Retarget才能呈現他的身材!

Extensions

Imporve the running time

在流程中，我們只需更新被濾除掉的seam carving像素點集合周圍的energy funciton，而不必更新整張影像的energy function

Retargeting in Both Dimensions

在流程中，如果都需要調整寬高，那應該先調整哪個方向

或著是透過一個方法同時調整寬高

同時重新調整寬高的思路，同時考慮到x,y方向的seam cost

並將他合成一個選擇公式：

$c,r$ 是行與列，考慮到x,y方向的seam cost，個別移除水平與垂直方向的結果
找出最小化的seam

Multi-Size Image Representation

上述流程是在知道輸入調整尺寸的情況下做演算

那假如在不確定輸入尺寸的情況下(ex:顯示的尺寸可能有各種不同的組合)

要如何做到即時resizing的轉換

那就先把整張影像上x,y索引的seam 的計算完排序並存起來，當今天要縮剪k個長度，就刪去前k個seam

Object Removal

設定mask來保護/移除指定的區塊

Limitations

seam carving的侷限性，低能量區域

低能量區域的移除造成影像細節的幾何變化
低能量區域在某些情形下也可能是重要資訊，ex:人臉

改善方法：
使用自訂義限制，ex:人臉因為低能量區域被移除造成人臉扭曲，那就用人臉檢測保護臉部區塊+seam carving

Improvement: forward energy

seam carving導致平均能量不停上升，並且會有鋸齒狀的邊緣

改變移除策略：不移除最小能量的seam，而是移除插入能量最小的seam

$C_L$是計算移除$𝑝_{𝑖,𝑗}$後左右,上下的能量,以此類推
得到每個移除接縫後的能量總和，用來評估哪個方向的像素被移除可以得到較小的能量

小能量代表移除後得到平滑影像，大能量代表出現梯度變化大(扭曲、鋸齒狀)的結果

比較forward & backward結果

更多差異圖

Reference

Improved seam carving with forward energy

cs131 lecture 11 Image Resizing-Image Retargeting Overview

Posted on 2021-04-07 Edited on 2023-09-01 In course Views:

影像調整大小在生活上隨處可見，如在不同的螢幕解析度下就必須對輸入的影像進行變化

但改變的同時常常造成比較重要的影像位置失去原先的樣貌特性

該節就開始探討在Resize的同時又可以保持重要的影像訊息

Content-aware Retargeting

上圖可以看到紅區域處是重要的資訊，若直接改變影像尺寸會造成人物的變形

若僅延展在影像中間處的雪地與天空區塊，就可以保留重要資訊

問題定義

輸入影像尺寸$n \times m$與新的尺寸$n’ \times m’$

輸出影像$n’ \times m’$並保有與原影像一樣好的影像細節

但所謂好的影像縮放結果沒辦法用量化的方式來定義

我們也不知道甚麼叫做重要的影像資訊，也許每個人對重要的影像區塊看法都不同

影像重要性(顯著性) 量測

定義一個function來找出影像”重要”的地方

重要指的可以是人眼經常會去特別關注的地方

cs131 lecture 10 Clustering- mean-shift clustering

Posted on 2021-04-05 Edited on 2023-09-01 In course Views:

論文名稱：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

cs131 lecture 10 Clustering-K-means clustering

Posted on 2021-03-28 Edited on 2023-09-01 In course , paper reading Views:

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

Efficient Graph-Based Image Segmentation

Posted on 2021-03-25 Edited on 2023-09-01 In paper reading Views:

在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

結果圖：

除了上述的流程與演算法外，由於目前提到的演算方法只考慮到空間位置，及鄰近像素來建構圖的連接關係，假使色彩相同但距離有些許差異，也不會合併成相同區域。為了考慮更大範圍的鄰近空間，又不能考慮到過大的範圍，否則搜索範圍所消耗的時間會過大，論文作者使用一個歐式距離的範圍來取代前面提到的四相連\八相連，擴大搜索範圍。