---
# System prepended metadata

title: 課程｜電腦視覺
tags: [課程]

---

# 電腦視覺

## Ch2 Thresholding and Segmentation
- Thresholding
    - 把亮度 0-255 的灰階照片，用 Threshold (e.g. T = 128) 轉換成黑白照片
    - Histogram：$h(m)=\#\{(r,c)|I(r,c)=m\}$：亮度為 $m$ 的 pixel 有 $h(m)$ 個
    - $P(I)=\frac{h(I)}{R\times C}$
    - 好的 Threshold 可以把 input image 恰好分成物體與背景
        - 方法：Minimizing Within-Group Variance
            - $\sigma^2=q_1(t)\sigma_1^2(t)+q_2(t)\sigma_2^2(t)$
            - 分別為 $value\le 和 \gt~t$ 的機率與變異數
        - 方法：Minimize Kullback Information Distance
- Connected Components Labeling
    - 4-connected / 8-connected
    - Rosenfeld 證明 binary 的 image 中，若 $C$ 是 component of 1， $D$ 是 component of 0 且是 $C$ 的鄰居，如果一個用 4-connected 另一個用 8-connected，則 $C$ 和 $D$ 必定一個包含另一個
    - 四種演算法：
        - An Iterative Algorithm
            ```clike=
            把每個 pixel 設成 unique ID;
            while(not change){
                從左上到右下，A[i][j] = min(A[i][j],A[i+-1][j],A[i][j+-1]);
                從右下到左上，A[i][j] = min(A[i][j],A[i+-1][j],A[i][j+-1]);
            }
            ```
        - The Classical Algorithm (Transitive Closure)
            ```clike=
            id = 0
            從左上到右下，如果該 pixel 有值
                如果有鄰居 ： A[i][j] = min(A[i-1][j],A[i][j-1]);
                如果沒鄰居 ： A[i][j] = id ++
            過程中紀錄 equivalence class ( 直接用 disjoint set )
            掃過整張圖，把 equivalence class 設成同樣 ID
            ```
        - A Space-Efficient Two-Pass Algorithm That Uses a Local Equivalence Table
            ```clike=
            id = 0
            從上到下：
                建一個 local equivalence table
                從左到右：
                    如果該 pixel 有值
                        如果沒鄰居 ： A[i][j] = id ++
                        如果有鄰居 ： A[i][j] = min(A[i-1][j],A[i][j-1])，並把 ID 不同的鄰居，加入 equivalence table
                從左到右：
                    如果該 pixel 有值
                        設成把該 pixel 設成同一 equivalence 的 ID
            過程中紀錄 equivalence class ( 直接用 disjoint set )
            從下到上：
                做相同的事情
            ```
        - An Efficient Run-Length Implementation of the Local Table Method
            ```clike=
            while( P<PLAST && Q<QLAST ){
                if(EndP<StartQ)    P = P+1
                if(EndQ<StartP)    Q = Q+1
                if(overlap)        //do something
            }
            ```
- Signature Segmentation and Analysis
    - 根據投影在不同線上，觀測是甚麼圖形
    - ![](https://i.imgur.com/cWiC4Kv.png)
## Ch3 Region Analysis
- Region properties 
    - 面積算法、質心算法、矩算法
    - 根據 region intensity histogram 來判斷對比度
        - 對比度越強，長條圖分布越平均
    - 邊界：
        - $P4=\{(r,c)\in R|N_8(r,c)-R\ne\phi\}$：八個鄰居有一個點在外
        - $P8=\{(r,c)\in R|N_4(r,c)-R\ne\phi\}$：四個鄰居有一個點在外
        - ![](https://i.imgur.com/Vjgl52p.png)
            - 注意邊界是指在 $P4$ 或 $P8$ 上走出一個 cycle(path)，(**怎麼找邊界長度**)
            - 相鄰點是垂直或水平長度計為 $1$，若是斜角則計為 $\sqrt{2}$
    - 中心到邊界距離：
        - 平均距離：$\mu_R$
        - 距離變異數：$\sigma^2_R$
        - Haralick property：
            - 越接近圓形，$\frac{\mu_R}{\sigma_R}$ 越大
            - 相似的形狀，$\frac{\mu_R}{\sigma_R}$ 會相似
            - 旋轉和縮放不會影響 $\frac{\mu_R}{\sigma_R}$
    - 亮度：
        - 平均亮度：$\mu$
        - 亮度變異數：$\sigma^2$
        - $\mu_{rg}=\frac{1}{A}\sum\limits_{(r,c)\in R}(r-\bar{r})(I(r,c)-\mu)$
        - $\mu_{cg}=\frac{1}{A}\sum\limits_{(r,c)\in R}(c-\bar{c})(I(r,c)-\mu)$
    - Gray-Level Co-occurrence Matrix 灰度共生矩陣
        - 共可分成 0 度、 45 度、 90 度、 135 度，四個矩陣 $P_H,~P_{SD},~P_V,~P_{LD}$
        - 假設原圖的亮度是 0~10，則每個矩陣為 10*10
        - 矩陣的每個元素，代表原圖中對應(兩亮度)再對應角度，共出現幾次
        - ![](https://i.imgur.com/sKZtLb3.png)  ![](https://i.imgur.com/Mf13JnL.png)
        - **可以用來判斷紋理**
            - Texture Second Moment：$M=\sum\limits_{g_1,g_2}P^2(g_1,g_2)$
            - Texture Entropy：$E=-\sum\limits_{g_1,g_2}P(g_1,g_2)logP(g_1,g_2)$
            - Texture Contrast：$C=\sum\limits_{g_1,g_2}|g_1-g_2|P(g_1,g_2)$
            - Texture Homogeneity：$H=\sum\limits_{g_1,g_2}\frac{P(g_1,g_2)}{k+|g_1-g_2|}$ 其中 $k$ 是某個小常數
    - 極限點 Extremal point
        - 八個極限點：上左、上右、下左、下右、左上、左下、右上、右下
        - 不同的圖形中，可能某些點會重疊再一起
        - 對面的兩點可以決定一條對角線，可以算其長度及角度
        - 兩點的距離：
            - 中心的距離：$\sqrt{(r_1-r_2)^2+(c_1-c_2)^2}$
            - 最遠距離：$\sqrt{(r_1-r_2)^2+(c_1-c_2)^2}$+1.12
- Signature segmentation properties
    - 投影：在哪一條線上的點有幾個 ? 
        - 水平：$P_H(r)=\#\{c|(r,c)\in R\}$
        - 垂直：$P_V(c)=\#\{r|(r,c)\in R\}$
        - 主對角線：$P_D(d)=\#\{(r,c)\in R|r+c=d\}$
        - 次對角線：$P_E(e)=\#\{(r,c)\in R|r-c=e\}$
    - 公式：
        - $\bar{r}=\frac{1}{A}\sum\limits_rrP_H(r)$
        - $\bar{c}=\frac{1}{A}\sum\limits_ccP_V(c)$
        - $\bar{d}=\frac{1}{A}\sum\limits_ddP_D(d)$
        - $\bar{e}=\frac{1}{A}\sum\limits_eeP_E(e)$
- 旋轉性質：
    - $\begin{equation}   {\left[ \begin{array}{ccc}
cos\theta & sin\theta \\
-sin\theta & cos\theta 
\end{array} \right ]} \times{\left[ \begin{array}{ccc}
x\\
y
\end{array} \right ]} = {\left[ \begin{array}{ccc}
x_{rot}\\
y_{rot}
\end{array} \right ]}\end{equation}$
## Ch4 Statical Pattern Recognition
- 基於統計及自己定義的 feature, error 來做分類問題，包含了：
    - Feature selection and extraction 
    - Decision rule
    - Estimating decision rule error
- 決定決定法則
    - **當觀測到一文件測量類別 $d$ 時，判定為類別 $a$，希望和真正的類別 $t$ 越接近越好**
        - 每一個文件包含三種 attribute
            - t : 真正的類別
            - a : 演算法判定的類別
            - d : 測量類別
        - 舉例而言，我們給定兩張表
            - 文件分布表：![](https://i.imgur.com/BgBRllQ.png) 經濟收益表：![](https://i.imgur.com/sYblCls.png)
            - 根據這兩張表，決定某一種對應關係 $f:(d_1,d_2,d_3)\rightarrow(a_1,a_2,a_3)$
    - 一些性質：
        - 經濟收益矩陣 Economic Gain Matrix
            - 把每一個 $(t,a)=(真正, 判定)$，量化成分數
            - Identity gain matrix： 判定正確得到 1 分，錯誤則得到 0 分
        - 期望分數 (Expected Profit) ： $\sum\sum e(t,a)P(t,a)$
            - $P(t,a)=\sum_dP(t,a,d)$
        - False alarm：實際上沒發生，卻假警報響起判斷成有發生
        - Mis detection：實際上有發生，卻被判斷錯誤成沒發生
        - 公正賽局假設：$P(a|d)=P(a|t,d)$
            - 當決定要把文件判定成哪一種類別 $a$ 時，只需考慮他的測量類別 $d$，而跟該文件的真正類別 $t$ 無關
        - 計算上，我們會先決定某一種對應關係 $f:d\rightarrow a$，根據此對應關係算出決策情形分布 $P(t,a)$。
            - 接著可以算出期望分數，或是最大錯誤率，來決定該對應關係的好壞
    - **貝式決定法則：找一個期望收益最大的 $f$**
        - **知道事前文件機率 $p(c_1)$ 和 $p(c_2)$ 時適用**
        - 寫成式子即為 $\forall g,~E[e;f]\ge E[e;g]$
        - 文件分布表：![](https://i.imgur.com/BgBRllQ.png) 經濟收益表：![](https://i.imgur.com/sYblCls.png)
        - $f:(d_1,d_2,d_3)\rightarrow(c_2,c_1,c_1)$ ： 期望收益為 $.2+.18+.3=.68$
        - $g:(d_1,d_2,d_3)\rightarrow(c_1,c_2,c_1)$ ： 期望收益為 $.12+.16+.3=.58$
    - **最大化最小值決定法則：找一個期望收益最小值最大化的 $f$**
        - **不知事前文件機率 $p(c_1)$ 和 $p(c_2)$ 時適用**
        - 當文件是某一個真實類別 $t_i$ 時，都有一個文件期望收益，我們希望最小值最大
        - 文件分布表：![](https://i.imgur.com/e3AgHWu.png) 經濟收益表：![](https://i.imgur.com/sYblCls.png)
        - $f:(d_1,d_2,d_3)\rightarrow(c_2,c_1,c_1)$
            - $c_1$ 的文件期望收益為 $.3+.5=.8$
            - $c_2$ 的文件期望收益為 $.5$
        - $g:(d_1,d_2,d_3)\rightarrow(c_1,c_2,c_1)$
            - $c_1$ 的文件期望收益為 $.2+.5=.7$
            - $c_2$ 的文件期望收益為 $.4$
        - 我們會做兩張圖來分析
            - ![](https://i.imgur.com/dVAkFTv.png) ![](https://i.imgur.com/HNBBhFe.png)
- **Decision Error**
    - Miss Detection $\alpha_k$：答成別類錯誤的比例
    - False Alarm $\beta_k$：誤答成該類的比例
    - ![](https://i.imgur.com/wNJyAd7.png)
    - 選擇錯誤率最小的 $f$ 也是一種決定法則
- 其他決策方法：
    - Nearest Neighbor Rule
    - Binary Decision Tree Classifier
    - Neural Network
## Ch5 Mathematical Morphology
- [數學形態學](https://zh.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E5%BD%A2%E6%80%81%E5%AD%A6)
    - 圖案 ←→ 點座標的集合
    - Operation：腐蝕和膨脹、開運算和閉運算
- 二元圖形
    - Dilation
        - $A\oplus B=\{c~|~c=a+b\text{ for some }a\in A,~b\in B\}$
        - 對點做擴張：$A_t=\{c~|~c=a+t\text{ for some }a\in A\}$
    - Erosion
        - $A\ominus B=\{x~|~x+b\in A,~\forall b\in B\}$
        - $A\ominus B=\{x~|~B_x\subseteq A\}$
        - $A$ 的哪個位置，可以擺入 $B$
        - Minkowski subtraction : $\cap A_{b\in B}$
    - Hit and Miss
        - $A\otimes(J,K)=(A\ominus J)\cap(A^C\ominus K)$ ，其中滿足 $J\cap K\ne\phi$
        - e.x. 找到所有的右上角邊界
            - ![](https://i.imgur.com/s1tJ80E.png)
    - Opening 
        - $A\circ K=(A\ominus K)\oplus K$
        - 找出 $A$ 中可以放入 $K$ 的位置，並保留
    - Closing 
        - $A\bullet K=(A\oplus K)\ominus K$
        - 找出 $A$ 中不可放入 $K$ 的位置，其他部分保留
    - 其他性質
        - $A^C=\{x~|~x\notin A\}$
        - $\check{B}=\{x~|~x=-b\text{ for some }b\in B\}$
        - Theorem 5.1: Erosion Dilation Duality
            - $(A\ominus B)^C=A^C\oplus\check{B}$
            - $(A\oplus B)^C=A^C\ominus\check{B}$
            - 只要實作 erosion 或是 dilation 其中一種，另一種 operation 就可以透過補圖來達到
            - Duality ： 一個 operator 的結果，恰好是另一個 operator 在補圖上的結果，再取補圖
        - Genus g(I) ： 連通元件數量減去洞數量，可以表示成 Erosion 式子
            - 必須先決定背景和前景哪一個是 4/8-connected
            - ![](https://i.imgur.com/tIKU2ne.png)
        - Conditional Dilation
            - ![](https://i.imgur.com/9GpMV91.png)
            - $J\oplus |_I D$ 
                - 上圖中 $D$ 是一個上下左右中，五個 pixel 的 mask
                - 一直重複把圖片對 $D$ 做 dilation 在交集 $I$ ，直到照片不再改變
- 灰階圖形
    - 每個 $a\in A$ 及 $b\in B$ 都可以表示成 $(x,~y,~亮度)$
        - 二元：只考慮座標，來決定 $A~\text{op}~B$
        - 灰階：除了座標，$A~\text{op}~B$ 是所有滿足的點之中，亮度最大或是最小的
    - Dilation $A\oplus B=\{c~|~c=a+b\text{ for some }a\in A,~b\in B\}$，滿足的點中，亮度最大的
    - Erosion $A\ominus B=\{x~|~x+b\in A,~\forall b\in B\}$，滿足的點中，亮度最小的
    - Opening $A\circ K=(A\ominus K)\oplus K$
    - Closing $A\bullet K=(A\oplus K)\ominus K$
- Morphological Skeleton 形態骨架
    - 給定圖形：![](https://i.imgur.com/UTzwMQH.png)
    - 形態骨架：![](https://i.imgur.com/zJ5P65f.png)
    - 形態骨架的每個點，擴張該點所存值的次數，即可以得到原圖
    - 得到型態骨架的方法：
        - $A-A\circ K$ ：![](https://i.imgur.com/3MBy5AF.png)
        - $A\ominus K-(A\ominus K)\circ K$ ：![](https://i.imgur.com/ix9KDCy.png)
        - $A\ominus^2 K-(A\ominus^2 K)\circ K$ ：![](https://i.imgur.com/2UaOf2x.png)
        - 仔細想想蠻合理的 XD
## Ch6 Neighborhood Operators
- 目標：將原圖中的每一個位置，判斷其鄰居是否有某種 pattern， 決定新圖的長相。
    - $N(r,c)$ 表示 $(r,c)$ 的鄰居集合，通常只討論 4-connected / 8 connected
    - Recursive Operator：新圖的結果，跟操作順序 (從上到下，從左到右) 有關
    - Linear Operator：新圖的結果，為原圖上鄰居的線性組合 (係數可能和絕對位置有關)
    - Shift Invarient Operator：新圖的結果，跟絕對位置完全無關
    - $g(r,c)=\Phi[r,c,f(r',c')|(r',c')\in N(r,c)]$
    - ![](https://i.imgur.com/huSkTCE.png)
- Region Growing Operator
    - ![](https://i.imgur.com/0S8QLFU.png)
- Nearest Neighbor Sets and Influence Zones
    - Recursive 的使用 region growing operation，直到整個圖的背景都被 label
- Region Shrinking Operator
    - ![](https://i.imgur.com/BJB8WfU.png)
- Euclidean-distance
    - ![](https://i.imgur.com/FsVJYeI.png)
    - 用 4-connected 會高估距離，而用 8-connected 會低估距離，因此實務上會一層用 4-connected，一層用 8-connected ，當作兩點距離的量測
- Mark Interior/Border Pixel Operator
    - ![](https://i.imgur.com/Hsl5sEq.png)
- Connectivity Number Operator
    - Yokoi Connectivity Number，以 4-connectivity 為例：
        - 先計算四個角落，屬於 $q、r、s$ 哪一類
        - ![](https://i.imgur.com/xuLujUg.png)
        - 該位置的 Yokoi Connectivity Number 由以下公式決定
        - ![](https://i.imgur.com/6jtviNm.png)
    - Rutovitz Connectivity Number
        - 另一種定義方式，比較複雜因此不提
    - ![](https://i.imgur.com/VIc9Rr5.png)
- Connected Shrink Operator
    - Recursive 的由上至下由左至右，刪除 Yokoi Connectivity Number 為 1 的點
        - Yokoi Connectivity Number 為 1 的點，保證刪除後仍為 connected
    - ![](https://i.imgur.com/PuSLcRv.png)
- Pair Relationship Operator
    - 將 boarder 中有和 interior 相鄰的位置標成 $p$，其他位置標成 $q$
    - ![](https://i.imgur.com/PSOgg4T.png)
- Thinning Operator
    - Recursive
    - 為了避免 Connected Shrink 直接操作會造成圖形不對稱，我們每一輪先把圖形的邊界標記成目標，每一輪只刪除最外圍的點
    - 1.用 Mark Interior/Border Pixel Operator 標記邊界
    - 2.用 Pair Relationship Operator 標記目標
    - 3.用 Connected Shrink Operator 由上至下由左至右，刪除目標當中 Yokoi Connectivity Number 為 1 的點
    - 4.重複 1、2、3 步驟直到圖形不再變化
    - ![](https://i.imgur.com/x0NYyKy.png)
- Distance Transformation Operator
    - ![](https://i.imgur.com/sAXoDVI.png)
    - 方法一：每個迴圈決定一個數字
        - 如果迴圈 $i$ 時，將 $i-1$ 旁邊尚未標記的 pixel 標記成 $i$
    - 方法二：把背景設成 0
        - 從上到下，從左到右：每個 pixel 設定成左邊和上面較小值 +1
        - 從下到上，從右到左：每個 pixel 設定成右邊和下面較小值 +1
- Radius of Fusion
    - 每個 connected componet 向外至少擴張多少 pixel 後，會有某些連在一起
    - 該半徑等價於，最小的 $n$ 使得擴張 $n$ 次、收縮 $n+1$ 次後，新圖包含了原圖的某些背景點
- Number Of Shortest Paths
    - ![](https://i.imgur.com/JS7jGNa.png)
    - 把原圖中的點設成 1，每個迴圈中，如果舊的圖該位置四周有數字，則新圖設定該位置成那些數字總和
- Non-Minima-Maxima Operator
    - 標註圖中每個點和周圍的關係，是 flat，minimum，maximum，transition 哪一種
    - ![](https://i.imgur.com/z3C5cui.png)
- Relative Extrema Operator
    - 標註圖中每個點，只往遞增的方向走，最大可以走到的數字為何
    - ![](https://i.imgur.com/0ysGVf8.png)
    - 1.從上到下，從左到右：每個 pixel 和左邊和上面比較，如果可以傳遞則傳遞
    - 2.從下到上，從右到左：每個 pixel 和右邊和下面比較，如果可以傳遞則傳遞
    - 重複 1、2 步驟直到圖形不再變化
- Reachability Operator
    - 標記圖中每個點，只往遞增的方向走，最大可以走到的數字相同的標為同一區域，並把邊界挑出來
    - ![](https://i.imgur.com/7a618zJ.png)
- Convolution and Correlation
    - Linear，Shift-Invariant
    - Correlation : $(f\otimes w)(r,c)=\sum f(r+r',c+c')w(r',c')$
    - Convolution : $(f * w)(r,c)=\sum f(r-r',c-c')w(r',c')$
- Separability
    - ![](https://i.imgur.com/St2sg5N.png)
    - 透過把 mask 拆成兩個 sub mask 相乘，可以有效降低計算量
    - 原圖 1000\*1000，Mask 10\*10，新圖 990\*990
    - 原方法：
        - 新圖的每個 pixel 需要 10\*10 個乘法的計算量
        - 總時間需要 990\*990\*10\*10
    - 拆解方法：
        - 先把原圖用 1\*10 submask 運算成 1000\*990 圖
            - 每個 pixel 需要 1\*10 個乘法的計算量
            - 總時間需要 1000\*990\*1\*10
        - 再把 1000\*990 圖用 10\*1 submask 運算成新圖
            - 每個 pixel 需要 10\*1 個乘法的計算量
            - 總時間需要 990\*990\*10\*1
    - 算一個點不會比較快，但算整張圖比較快
## Ch7 Conditioning And Labeling
- 用一些例子介紹 conditioning 及 labeling
    - Conditioning : Noise cleaning、Sharpening
    - Labeling : Edge detection、Line detection
- Noise cleaning
    - 使用 3\*3 的 box filter 或是 5\*5 的 box filter
        - 一般都設定成相同的權重，可以猜成 row 和 column 以降低計算量
        - 在做 convolution 時可以作一些優化
        - Separable : 等價於先和 1\*3 做 convolution，再和 3\*1 做 convolution
        - Nonlinear 的 filter：$w(r,c)=e^{-\frac{1}{2}\frac{r^2+c^2}{\sigma^2}}$
        - 其他：
            - ![](https://i.imgur.com/xI5Sn3A.png) ![](https://i.imgur.com/PpRzbYD.png) ![](https://i.imgur.com/9pibAoZ.png)
    - 移除 Outlier or Peak Noise 
        - ![](https://i.imgur.com/qqCYzBL.png)
            - 2.算出鄰居的平均及標準差，看距離幾個標準差
            - 3.用 平均 和 $y$，去某種加權平均
            - 5.這個方法沒有設定 threshold
                - ![](https://i.imgur.com/jXREkEv.png)
                - ![](https://i.imgur.com/RYRoanR.png)
                - 中心的 mask 佔 1/2
                - 剩下的每個點先算 $g(r,c)=\frac{1}{max\{2,~|f(r,c)-y|~\}}$
                - 每個點的 mask 平分 1/2
        - ![](https://i.imgur.com/g0dpLfq.png)
            - 7.算出鄰居的平均及四分位距 $Q=Q_3-Q_1$，看距離幾個四分位距
            - 8.去除最大和最小的 k 個後取平均
            - 9.最亮加上最暗的去除以二
            - 10.算出鄰居的平均及標準差，只取出兩倍標準差內的來取平均
                - ![](https://i.imgur.com/EBKVW3L.png)
        - Hysteresis Smoothing
            - 如果上升階段遇到小小的下降，則 smooth 他，反之亦然
        - Selected-Neighborhood Averaging
            - 有 9 種區域鄰居，挑標準差最小的來取平均
    - SNR (signal to noise ratio)
        - 訊號雜訊比
        - ![](https://i.imgur.com/cpC7dkZ.png)
- Sharpening
    - 方法一：
        - ![](https://i.imgur.com/VBXY5id.png)
    - 方法二：
        - ![](https://i.imgur.com/OXtdLNM.png)
        - 看看 f(r,c) 比較靠近最大值或是最小值，就將其設定成那個值
- Edge detection
    - **Gradient Edge Detectors**
        - Roberts operators：
            - ![](https://i.imgur.com/83e7bbD.png) ![](https://i.imgur.com/xi89Evw.png)
        - Prewitt edge detector：
            - ![](https://i.imgur.com/GBhnuOg.png)
        - Sobel edge detector：
            - ![](https://i.imgur.com/lOpCstB.png)
        - Frei and Chen edge detector：
            - ![](https://i.imgur.com/JWnSNnI.png)
        - Kirsch edge detector：
            - ![](https://i.imgur.com/rtt0rXs.png)
        - Robinson edge detector：
            - ![](https://i.imgur.com/Lunuwf4.png)
        - Nevatia and Babu： 5\*5，六個方向
        - 前四個要取 L2 Norm，後三個要取 max(abs())，取完後看是否有超過一 threshold。
    - **Zero-Crossing Edge Detectors**
        - 先對原圖取二次微分，可以用和底下兩個 mask 做 convolution 來近似
            - ![](https://i.imgur.com/VrcWwvf.png)
        - 找出二次微分等於零的點，一階微分的極值，即為原圖亮度劇烈變化的位置
            - 因為直接找是沒有意義的，因此用以下兩種找法
                - 自己比 t 大而且鄰居有點比 -t 小
                - 自己比 -t 小而且鄰居有點比 t 大
            - 滿足兩性值的其中一個，表示二次微分穿過零點
            - 設定 threshold 是避免太容易把 noise 當作 edge
- Line detection
    - ![](https://i.imgur.com/aFY8yle.png)
## Ch8 The Facet Model
- 找出相對極大值
    - 該點一階微分為零，二階微分為負
    - 可以用[最小平方法](https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E4%BA%8C%E4%B9%98%E6%B3%95)求出
    - 如果給定三點 $f(n-1)、f(n)、f(n+1)$，要用二次曲線 $cm^2+bm+a$ 來近似，則可解微分等於零得到以下結果
        - $a=f(n)$
        - $b=\frac{f(n+1)-f(n-1)}{2}$
        - $c=\frac{f(n+1)+f(n-1)-2f(n)}{2}$
- Sloped Facet Parameter and Error Estimation
    - 假設原圖由 $𝑔(𝑟,𝑐)=𝛼𝑟+𝛽𝑐+𝛾+𝜂(𝑟,𝑐)$ 產生，先由  $\hat{\alpha}r+\hat{\beta}c+\gamma$ 來近似原圖
        - $𝜂(𝑟,𝑐)$ 平均為 0 ，標準差為 $\sigma^2$
    - 最小平方法誤差為 $\sum\limits_{r\in R}\sum\limits_{c\in C}[\hat{a}𝑟+\hat{𝛽}𝑐+\hat{𝛾}-g(r,c)]^2$ ，找出誤差最小 $\hat{𝛼}$ 、 $\hat{𝛽}$ 、 $\hat{𝛾}$
        - 在 ![](https://i.imgur.com/JI5klfP.png) 座標底下， $\sum r = \sum c = 0$
        - $\hat{\alpha}=\frac{\sum\sum rg(r,c)}{\sum\sum r^2}$
        - $\hat{\beta}=\frac{\sum\sum cg(r,c)}{\sum\sum c^2}$
        - $\hat{\gamma}=\frac{\sum\sum g(r,c)}{\sum\sum 1}$
    - 代入 $𝑔(𝑟,𝑐)=𝛼𝑟+𝛽𝑐+𝛾+𝜂(𝑟,𝑐)$
        - $\hat{\alpha}=\frac{\sum\sum r[𝛼𝑟+𝛽𝑐+𝛾+𝜂(𝑟,𝑐)]}{\sum\sum r^2}=\alpha+\frac{\sum\sum r𝜂(r,c)}{\sum\sum r^2}$ ，平均數為 $\alpha$，變異數為 $\frac{\sigma^2}{\sum\sum r^2}$
        - $\hat{\beta}=\frac{\sum\sum c[𝛼𝑟+𝛽𝑐+𝛾+𝜂(𝑟,𝑐)]}{\sum\sum c^2}=\beta+\frac{\sum\sum c𝜂(𝑟,𝑐)}{\sum\sum c^2}$ ，平均數為 $\beta$，變異數為 $\frac{\sigma^2}{\sum\sum c^2}$
        - $\hat{\gamma}=\frac{\sum\sum 𝛼𝑟+𝛽𝑐+𝛾+𝜂(𝑟,𝑐)}{\sum\sum 1}=\gamma+\frac{\sum\sum 𝜂(𝑟,𝑐)}{\sum\sum 1}$ ，平均數為 $\gamma$，變異數為 $\frac{\sigma^2}{\sum\sum 1}$
    - 最小平方法的誤差 $\epsilon=\sum\limits_{r\in R}\sum\limits_{c\in C}[\hat{𝛼}𝑟+\hat{𝛽}𝑐+\hat{𝛾}-(𝛼𝑟+𝛽𝑐+𝛾+𝜂(𝑟,𝑐))]^2$
        - $=\sum\limits_{r\in R}\sum\limits_{c\in C}~[~𝜂^2(𝑟,𝑐)-(\hat{𝛼}-𝛼)^2𝑟^2-(\hat{𝛽}-𝛽)^2𝑐^2-(\hat{𝛾}-𝛾)^2~]~$
    - 可以推論出 $\frac{\epsilon^2}{\sigma^2}$ 的自由度為 $\sum\limits_{r\in R}\sum\limits_{c\in C} 1-3$，故 $Y=\frac{\epsilon^2}{\sigma^2}\sim \chi_{\#N-3}^2$
        - $\sum\sum\frac{𝜂^2(𝑟,𝑐)}{\sigma^2}$ 是一個自由度為 $\sum\sum 1$ 的卡方分布
        - $\sum\sum\frac{(\hat{𝛼}-𝛼)^2𝑟^2}{\sigma^2}$ 是一個自由度為 $1$ 的卡方分布
        - $\sum\sum\frac{(\hat{𝛽}-𝛽)^2𝑐^2}{\sigma^2}$ 是一個自由度為 $1$ 的卡方分布
        - $\sum\sum\frac{(\hat{𝛾}-𝛾)^2}{\sigma^2}$ 是一個自由度為 $1$ 的卡方分布
- **卡方檢定**
    - 若 $k$ 個隨機變數 $Z_1,...,Z_k$，為彼此獨立的標準常態分佈 $\sim N(0,1)$
    - 則這些隨機變數的平方和 $Y=Z_1^2+...+Z_k^2$，稱為 **"自由度為 k 的卡方分布"**，即 $Y\sim \chi_k^2$
- **T 分布**
    - 給定 $Z\sim N(0,1)$ 以及 $Y\sim \chi_n^2$
    - 則 $T=\frac{Z}{\sqrt{\frac{Y}{n}}}$ 是自由度為 $n$ 的 t-distribution，即 $T\sim t_n$
- Facet-Based Peak Noise Removal
    - 先用周圍預估中間，如果中間真正值和預估值差異太大則為 noise 需要 remove
    - $g(0,0)-\hat{\gamma}~~\sim~~N(0,\sigma^2(1+\frac{1}{\#N}))$
    - $Z=\frac{g(0,0)-\hat{\gamma}}{\sigma\sqrt{1+\frac{1}{\#N}}}~~\sim~~N(0,1)$
    - $Y=\frac{\epsilon^2}{\sigma^2}\sim \chi_{\#N-3}^2$
    - 則 $t=\frac{Z}{\sqrt{\frac{Y}{\#N-3}}}=\frac{(g(0,0)-\hat{\gamma})\sqrt{\#N-3}}{\sqrt{1+\frac{1}{\#N}}\epsilon}$ 是自由度為 $\#N-3$ 的 t-distribution
    - 可以查 t-distribution 的表來決定是否為 noise 的機率
- Iterated Facet Model
    - 物體是由一系列慢慢改變斜率的小平面所構成
- Gradient-Based Facet Edge Detection
    - 可以用小平面的斜率當作 gradient，來判斷 edge 為 gradient 大於某 threshold 的標準
    - ![](https://i.imgur.com/HiaaxbN.png)![](https://i.imgur.com/xwEXP5C.png)
    - 可以查卡方分布得到是否為 edge 的機率
- Bayesian Approach to Gradient Edge Detection
    - 𝑃(𝑒𝑑𝑔𝑒│𝐺)>𝑃(𝑛𝑜𝑛𝑒𝑑𝑔𝑒|𝐺)
    - 𝑃(𝐺│𝑒𝑑𝑔𝑒)𝑃(𝑒𝑑𝑔𝑒)>𝑃(𝐺│𝑛𝑜𝑛𝑒𝑑𝑔𝑒)𝑃(𝑛𝑜𝑛𝑒𝑑𝑔𝑒)
- Discrete Orthogonal Polynomials
    - $1$
    - $x$
    - $2x^2-1$
    - $4x^3-3x$
    - $8x^4-8x^2-1$
- Directional Derivative Edge Finder 
    - An edge pixel
        - $f_α^{′′′}(ρ)<0$
        - $f_α^{′′}(ρ)=0$
        - $f_α^{′}(ρ)≠0$
- Corner Detection
    - ![](https://i.imgur.com/F1Dj2Jq.png)
- Topographic Primal Sketch
    - Peak : 梯度等於零，兩個方向凹口向下
    - Pit : 梯度等於零，兩個方向凹口向上
    - Ridge : 
        - 梯度不等於零，一個方向凹口向下且斜率為零
        - 梯度等於零，一個方向凹口向下，另一個方向凹口轉折處
    - Ravine :
        - 梯度不等於零，一個方向凹口向上且斜率為零
        - 梯度等於零，一個方向凹口向上，另一個方向凹口轉折處
    - Saddle : 梯度等於零，一個方向凹口向上，另一個方向凹口向下
    - Flat : 梯度等於零，兩個方向凹口都是轉折處
    - Hillside : 梯度不為零的其他 case
## Ch9 Texture
- Texture Analysis Issues
    - 1.Pattern recognition：做分類問題
    - 2.Generative model：做描述
    - 3.Texture segmentation：區分一圖上的不同部分
- “Texel” v.s. “Texture Primitive”
    - Texel : 組成 texture 的基本元素，可以重複排列出整個圖
    - Texture Primitive : 有相似特性的 connected pixel set
    - 一個影像的 texture 大致可以用三項來描述：
        - primitives 種類
        - primitives 個數
        - primitives 空間分布
- Statistical Approaches
    - Gray Level Co-Occurrence Matrix
        - 描述某兩個亮度出現在相對位置的數量有幾個
        - 算完後還可計算 Gray level difference probability
            - 亮度相差 $d$ 的 pair 有多少個，來區分不同性質的 texture
    - Strong Texture Measures and Generalized Co-occurrence
        - 1.建立 texture primitive
            - Connected components
            - Ascending\descending components
            - Saddle components
        - 2.分析不同 primitive 之間的關係
    - Autocorrelation function
        - 大的 primitive 可能表示材質比較 coarse
        - Coarse texture → function drops off slowly
        - Fine texture → function drops off rapidly
- Model Based Technique
    - Auto-regression
    - Markov random fields
    - Random Mosaic models
## Ch10 Segmentation
- 後面其實都不太重要
## Ch11 Arc Extraction
- 前面其實也不太重要

## 其他
- [課程網頁](http://cv2.csie.ntu.edu.tw/CV/index.html#intro)
- [期中考試筆記](https://hackmd.io/bXMlc5gCSJigmkzuI2UJOg)
- [期末考試筆記](https://hackmd.io/CbfqvoNaS7e7U9WgEinEoQ)
