---
# System prepended metadata

title: Bag of words

---

# Bag of words

## 影像辨識的挑戰
1. view point variation(視角變化)
2. illumination(光照)
3. occlusion(遮擋)
4. Scale(大小變化)
5. Deformation(型變)
6. Background clutter(背景干擾)
7. Intra-class variation(類內差異)

## 分類 : 統計觀點
### Bayes rule(貝式定理)
- 要事先考慮預設的機率
![](https://i.imgur.com/pTVrOvp.png)

## Bag of Words models
- 看出現的頻率(和空間無關)
- 一開始是拿來計算字在句子或文章裡的出現頻率
- 也可用來看圖片(把圖片切割成一些特徵)
- 對照圖片如果有這個特徵的話就把histogram 加1
- 最高的那個直方圖就是我們推測這張照片的內容
- 缺點: 每一個要分類的內容都必須先建立檔案
- 如過放入新的東西，就無法偵測出東西的內容

### 特徵提取方法 (Feature extraction)
#### Regular Grid(規則網格)
把圖切成幾等分
# 筆記
### sift (用最近鄰居的角度和方向 用相對的關系 AFFINE)CLUSTERING 裡面的論文
# 把特徵用KMEANS 分群(用小)
### KMEANS -> Wij * dist(xi, cj) => cj 是群心
### CMeans => Wij的 M 次方


#### Interest Point Detector
- 圖用特別的點來選取特徵範圍
- 用數學去找出角落和轉折點

#### Random sampling
#### Segmentation based patches(分割成基本Patch)
- patch 多個pixel 組成


### Codewords dictionary formation(碼字字典的形成)
![](https://i.imgur.com/fe50B31.png)
- 用k-means分群

##### 如何選擇Vocabulary大小
- 太大 : 視覺詞不能代表所有補丁
- 太小 : (overfiting)過度擬合、(quantization artifacts)壓縮失真

##### Computational efficiency(計算效率)
- Vocabulary trees (Nister & Stewenius, 2006)

![](https://i.imgur.com/gW2aJla.png)

### 大綱
![](https://i.imgur.com/D8cJShG.png)
![](https://i.imgur.com/0OhgHIl.png)

##### Weighting	the	words(字的權重)
- 和entropy 的概念有點像
- 每一個文章都出現的字, 資料量超小
- TF-ID weighting 用這個來計算它的重量

###### Inverted File(倒置檔、索引檔)
- 為了提高檢索速度而發展出的另一種檔案結構
![](https://i.imgur.com/DLmM0kt.png)

- 範例
![](https://i.imgur.com/nzZqpGO.png)
![](https://i.imgur.com/NJsWPZW.png)
![](https://i.imgur.com/x2ukYfB.png)


# 判別方法(Discriminative method)
[模型](https://taweihuang.hpd.io/2017/03/21/mlbayes/)
## NN(Nearest Neighbor)
## SVM

# 總結方法
## Spatial Pyramid Matching
[例子](https://blog.csdn.net/qq_29573053/article/details/78361335)
- Each level in the pyramid	is 1/4 of the size of previous level.

![](https://i.imgur.com/1p3uIuY.png)

## Naïve Bayes

# 空間信息(spatial info)
## Feature level
## Sudderth, Torralba, Freeman & Willsky, 2005, 2006
## Niebles & Fei-Fei, CVPR 2007
## Discriminative methods – Lazebnik, Schmid & Ponce, 2006

# 缺點
1. 雖然對我們來說很直觀，但沒有此類的訊息
2. 尚未經過廣泛測試
3. 分割和本地化(Segmentation and localization)不明確
4. 沒有空間分布

### SIFT(尺度不變特徵轉換)
- Scale Invariant Feature Transform
- [網頁](https://kknews.cc/zh-tw/tech/kvgxqbp.html)
#### 步驟
1. 尺度空間的極值檢測 搜索所有尺度空間上的圖像，通過高斯微分函數來識別潛在的對尺度和選擇不變的興趣點。
2. 特徵點定位 在每個候選的位置上，通過一個擬合精細模型來確定位置尺度，關鍵點的選取依據他們的穩定程度。
3. 特徵方向賦值 基於圖像局部的梯度方向，分配給每個關鍵點位置一個或多個方向，後續的所有操作都是對於關鍵點的方向、尺度和位置進行變換，從而提供這些特徵的不變性。
4. 特徵點描述 在每個特徵點周圍的鄰域內，在選定的尺度上測量圖像的局部梯度，這些梯度被變換成一種表示，這種表示允許比較大的局部形狀的變形和光照變換。

#### 優點
1. 圖像的局部特徵，對旋轉、尺度縮放、亮度變化保持不變，對視角變化、仿射變換、噪聲也保持一定程度的穩定性。
2. 獨特性好，信息量豐富，適用於海量特徵庫進行快速、準確的匹配。
3. 多量性，即使是很少幾個物體也可以產生大量的SIFT特徵
4. 高速性，經優化的SIFT匹配算法甚至可以達到實時性
5. 擴招性，可以很方便的與其他的特徵向量進行聯合。
