# **影像處理**

## 測邊

* 概念：灰階的突然改變
>**常用方法：**

**1.拉普拉斯算子：**
概念：峰值二次微分通過零點來側邊，
在Laplace算子裡，只要上下 左右 這兩組滿足一正一負和兩值差大於T的條件（避免左右差分值太小），就可以確定（x,y)的位置上存在一個邊點。
**2.Sobel側邊算子：**（-1，-2，-1）
概念跟Laplace差不多，分為偵測X軸kernel、偵測Y軸kernel。
**3.prewitt算子 ：**（-1，-1，-1）
跟Sobel類似，只是kernel裡的數字不同而已，但也是分為偵測水平紋理、垂直紋理kernel

> **結合側邊、去雜訊的算子**

**1.Marr-Hildreth算子：**
概念：影像中某一個像素的灰階值受距離較遠像素灰階值的影響是較小的
計算出來的值有點像墨西哥帽的kernel
**2.canny：**（測出來的邊點很少）
概念：首先利用高斯去除過多的細紋，然後在每個像素上計算其梯度方向和梯度量，假如在這個方向上，該像素的梯度量大於二個鄰居的量則該像素為邊點。（若方向為水平則是看垂直的兩個鄰居的量「即法向量」）

>** 基底投影法**

使用9個向量基底來對影像做投影，最後再取內積最大值，則代表此圖有類似於對應基地所測得的邊點，缺點是有些基底定義沒有很明確。

## 門檻值決定與區域分割
* 概念：二值化
>**統計式方法：**

**1.蠻力法**
方法：畫圖出來看波峰波古。
缺點：假設沒有明顯波古就烙賽了
統計式門檻值決定法：
**2.Otsu方法**：算兩區域between變異數max和兩區域裡的變異數相加min，來決定門檻值。
◦ 消息理論為基礎的門檻決定法：
kapur方法：算兩區域的平均消息量熵，把兩個值相加取最大值，熵越大代表兩區域分佈越平均，其算法觀念跟Otsu的最小變異數和觀念本質上相同。
◦ 動差守恆式的門檻決定法：
K階有2k個變數待解（其實不知道在幹嘛）

>區域分割

**1.分水嶺法**
方法：每一個像素檢查其8個方位的鄰居，找出一鄰居且其灰階值比原像素差最多者，則用一個箭頭表示方向，若跟8個鄰居比為最小者，則為局部最小值，沒箭頭指向的線為分水嶺所在。

## 直線與道路偵測
* 概念:首先先由測邊方法測出邊點，再由下面的方法來測得直線
>**常用方法：**

**1.蠻力法：**
方法：用側得的邊點集，來決定有幾條可能的直線（兩點一直線），接著計算每條可能的直線與邊點集裡每個邊點的距離，只要小於門檻值T1，則投一票，若總投票數超過門檻值T2，則為一條真正直線。
時間複雜度：O(m^3) 「m為邊點數」。
缺點：運算太慢。
**2.霍式轉換法：**
概念：用側得的邊點集，轉成參數空間（r,角度），假設兩點共線，那他們帶入式子6.3.1在選定的角度下，值（法距）會相同。
方法：使用二維陣列來完成參數空間的資料維護，把180度切成n等份當作橫軸，把相鄰兩個法距r差值設為1來當作縱軸，接著把邊點對應橫軸角度依依帶入6.3.1式算出法距r，而相等的法距r會落入同個位置（通常稱為投票箱），每個投票箱會紀錄哪些邊點落入其中，最後投票箱裡的邊點數若超過門檻值，則為真正的直線。
複雜度：O(mn) 「m為邊點數，n為角度分割數」。
缺點：很花記憶體（累積陣列），以及需檢查全部邊點。
**3.隨機式方法：**
概念：抽樣出隨機3個點來做直線偵測
方法：隨機抽出3個邊點，用2個邊點決定一條直線，且用另一個邊點來算與直線的距離，然後在這些組合中（假設3個點就有3個組合）挑一個最小距離值（邊點與直線距離）當作候選線，另外在處理時要排除叢聚的現象，接著決定好候選線後就跟上面方法一樣，計算所有邊點與候選線的距離小於門檻值T1的有幾個（C)，假設C大於門檻值T2，則候選線為真正直線。
複雜度：探討決定候選線的失敗次數對時間效益的影響，以下是用到的機率密度概念。
連續型隨機變數的機率密度函（Probability density function)：
是一個描述這個隨機變數的輸出值，在某個確定的取值點附近的可能性的函數。圖中，橫軸為隨機變數的取值，縱軸為機率密度函數的值，而隨機變數的取值落在某個區域內的機率為機率密度函數在這個區域上的積分。當機率密度函數存在的時候，累積分布函數是機率密度函數的積分。
總之課本只是要說隨機式方法比較強== ，因為他可以不用算那麼多邊點也不會很耗記憶體。
**4.偵測拋物線**
◦ Kluge：只是使用隨機式演算法來算拋物線而已，會拿拋物線的3個參數來決定拋物線（？不太確定）

## 影像資料庫檢索
>**常用方法：**

**1.色彩檢索法：**(RGB拆開）
方法：把要比對的image分別轉成R,G,B 3個直方圖跟database裡的image 3個直方圖比對，算差異量，差異量越小代表越相似。
方法：八分樹（Octree)（RGB合在一起）
每個pixel轉成二進位，並用八分樹來表示，
從pixel裡的RGB各自取最左邊的位元，當作八分樹第一個counter,然後接下去收集，最後再把輸入影像的八分樹跟database的八分樹做比較，counter差異量越小（counter 的差異量可取絕對值）代表兩圖像越接近，通常越上層的節點，我們會給予較高的加權，因為它代表主要顏色
**2.邊紋檢索法：**
概念：利用邊點圖所求得的5個特徵來做檢索，特徵分別如下：
特徵1:注水時間
從編號1的邊點開始掃描，每經過一個邊點注水時間多1，入水處不一樣所得到的注水時間也可能會不一樣。
特徵2:分岔數
分岔點（起始點也算一個分岔）。
特徵3:迴圈數
迴圈。
特徵4:水流量
水流經過的邊點數。
特徵5:最小長方形寬高
得到一個最小的長方形將邊點圖框住。

## 圓與橢圓偵測
**1.測圓**
步驟：
1. 利用第4章的側邊方法，得到邊點集
2. 在邊點集中隨機選擇4個點
3. 找出4個邊點所構成的所有圓
4. 決定候選圓
方法：取d4與C（123）最小值且小於閥值Td 作為後選圓）
5. 決定真正的圓
方法：檢查所有的邊點跟C(123)候選圓是否小於Td，若是小於則C+=1，最後若是C>Tg則為真正圓，其中閥值Tg=2pi*r(123)Tr。（Tr通常為0.8，表示數位圓上的邊點需佔圓周的80%）

可調式搜尋範圍法（在第四步驟有另外一個方法可以減少計算量）
概念：使用一個邊長為2*（r(ijk)+變數）的正方形將候選圓匡住，然後只用在正方形裡的邊點來做第四步。

## 2.測橢圓
步驟：
1. 利用第4章的側邊方法，得到邊點集
2. 在邊點集中隨機選擇4個點
3. 橢心的決定：
方法：找出2個邊點所計算出來通過橢心的直線，4個邊點會算出3個橢心，接下來求3個點的質心，3個點分別與質心算距離，小於門檻值的淘汰。
4. 決定候選橢圓
方法：首先會先決定d,e,f是否有滿足橢圓條件，滿足後再來判斷取出的4個邊點中，各個邊點與候選橢圓的距離是否有小於門檻值，以上條件都滿足為候選橢圓。
5. 決定真正的橢圓
方法：檢查所有的邊點跟候選圓是否小於Td，若是小於則C+=1，最後若是C>Tg則為真正圓，其中閥值Tg=（外接長方形周長）+（內街菱形周長的一半）*Tr。（Tr通常為0.8，表示數位橢圓上的邊點需佔橢圓周的80%）

### 應用:視訊場景的變化偵測
方法：Hausdorff(利用圓、橢圓、直線來偵測場景變化）
先測得第一張影像中的直線、圓與橢圓之所在，並記錄圖形上的交點所在，接下來側下一張圖形上的交點所在，然後計算Hausdorff量度，假如連續兩張影像，他的Hausdorff大於門檻值，代表第二張影像內的交點有大位移，於是我們認定有場景變化，簡單來說此方法的圖形看法就是看橫軸哪個點大於門檻值，他跟他的下一張圖就有場景變化。
方法：PME
PME=平均移動向量值*決定性移動方向的百分比。
柱狀圖看法為波峰處為場景切換之處。