計算機視覺的幾個經典算法
1. 最小二乘法（尋找線性回歸函數(shù)）
在了解最小二乘法之前，我們有必要先說說線性回歸，所謂線性回歸我們最常見的例子y=2x這個一元線性回歸方程中，斜率2就是回歸系數(shù)，它表示的是x變動時，y與之對應的關系，而線性回歸就是表示一些離散的點在總體上是最逼近某一條直線的
這跟最小二乘法有啥關系呢？其實最小二乘法（Least Square Method）是尋找線性回歸函數(shù)的一個方法，它是通過最小化誤差的平方和來求得的，那我們?yōu)槭裁词褂脷埐钇椒胶湍兀恳驗樗臄M合程度更高，也就是擬合函數(shù)與待求解函數(shù)的y之間的相似性更高
利用最小二乘法可以簡便得求得未知的數(shù)據(jù)，并使得這些求得的數(shù)據(jù)與實際數(shù)據(jù)之間誤差的平方和為最小
2. RANSAC（模型已知，參數(shù)未知）
RANSAC，即隨機采樣一致性，它不是一種方法或算法，它是一種思想，一個求解已知模型的參數(shù)的框架，它不限定某一特定的問題，可以是計算機視覺的問題，也可以是統(tǒng)計數(shù)學，甚至可以是經濟學領域的模型參數(shù)的估計問題
它是一種迭代的方法，用來在一組包含離散的被觀測數(shù)據(jù)中估算出數(shù)學模型的參數(shù)，它也是一種非確定性算法，它會產生一個在一定概率下合理的結果，其允許使用更多次的迭代來使其概率增加
RANSAC的基本假設是 “內群”數(shù)據(jù)可以通過幾組模型參數(shù)來敘述其數(shù)據(jù)分布，而“離群”數(shù)據(jù)則是不適合模型化的數(shù)據(jù)。 數(shù)據(jù)會受噪聲影響,噪聲指的是離群，例如從極端的噪聲或錯誤解釋有關數(shù)據(jù)的測量或不正確的假設
RANSAC假定，給定一組（通常很小的）內群，存在一個程序，這個程序可以估算最佳解釋或最適用于這一數(shù)據(jù)模型的參數(shù)
2.1 RANSAC 與 最小二乘法的區(qū)別
從上述的內容我們可以得知其實這兩個東西都是用來做擬合的，但是他們之間又有什么關系、有什么區(qū)別、應用場景有什么不同呢？
在實際開發(fā)或生產實踐中，數(shù)據(jù)都會有一定的偏差，當我們已知兩個變量之間的關系是線性回歸函數(shù)，Y=aX+b，如果我們想知道具體的a和b的值，理論上說我們只需要兩個點就能滿足需求，但是由于誤差的存在，我們任意選取的兩個點所求出的a和b可能都不相同，我們最想要的就是最后的理論模型與測試值的誤差最小
- 最小二乘法：通過計算最小均方差關于a和b的偏導數(shù)為0時的值，在很多情況下最小二乘法就是線性回歸的代名詞，但是它只適用于誤差較小的情況
- RANSAC：在模型已確定且最大迭代次數(shù)允許的情況下，RANSAC總是可以找到最優(yōu)解（對于包含80%誤差的數(shù)據(jù)集，RANSAC的效果遠遠好過最小二乘法）
綜上所述我們可以片面地認為最小二乘法適用于誤差小的情況，RANSAC使用與誤差稍大且最大迭代次數(shù)允許的情況，在圖像處理的實際開發(fā)中，由于一張圖片的像素個數(shù)龐大，采用最小二乘法運算量巨大且計算速度很慢
2.2 RANSAC算法的步驟
RANSAC算法的輸入數(shù)據(jù)：是一組觀測數(shù)據(jù)，并且由于RANSAC的獨特性，通常這些觀測數(shù)據(jù)中會有較大的噪點和無效點，除了觀測數(shù)據(jù)，RANSAC還需要一個已知的模型（理解為一個函數(shù)），還有一些可信的參數(shù)也很重要
在RANSAC算法的實現(xiàn)過程中，我們可以大致分為6個步驟：
- 在輸入數(shù)據(jù)中隨機選擇幾個點設置為內群，也就是除噪點和無效點之外的有效點
- 計算合適內群的模型，作為輸入數(shù)據(jù)傳入RANSAC算法中
- 把其他的剛才沒有選中的點傳入建立的模型中，計算是否為內群
- 把內群數(shù)量記錄下來，并重復以上的步驟
- 在每一次計算內群數(shù)量過程中選出內群數(shù)量最多的那一個，內群數(shù)量最多的那一次建立的模型就是我們需要的結果
在執(zhí)行RANSAC算法的過程中，對于不同的數(shù)學模型，在計算參數(shù)模型時的方法也必定不同，故RANSAC不是為了找到計算模型參數(shù)，而是提供這樣的一個思路
RANSAC最大的缺陷在于要求數(shù)學模型已知
在算法執(zhí)行的過程中我們應該關注兩個問題：1.開始時應該選擇多少個點為內群；2.最大迭代次數(shù)是多少
2.3 RANSAC的參數(shù)確定
假設我們在第一步選取的點是內群的概率為w，而選取的個數(shù)為n，w^n是所選擇的n個點都是內群的機率, 1-w^n 是所選擇的n個點至少有一個不是內群的機率, (1 ? wn)k 是表示重復 k 次都沒有全部的n個點都是內群的機率, 假設算法跑 k 次以后成功的機率是p，我們可以得到p的計算公式：p = 1 ? (1 ? w^n)k
再通過上述公式得到k的計算公式：K=log(1-P)/log(1-w^n)
通過這兩個函數(shù)我們可以得知，如果我們希望建立的模型是最優(yōu)解的幾率高一點，當w確定時，k越大p就越大。當w不變時，n越大所需要的k就越大，然而通常來講w是位置的，所以我們會把n選小一點
2.4 RANSAC的應用
RANSAC最典型的應用場景是全景拼接，它的實現(xiàn)過程大致分為4個步驟
- 針對某個場景拍攝多張圖像，這些圖像一般成序列
- 通過特征匹配（SIFT）計算下一張圖片與上一張圖片之間的變換結構
- 圖像映射，將下一張圖片疊加到上一張圖片的坐標系中
- 將變換后的圖像融合起來就得到了最后的全景圖
2.5 RANSAC算法的優(yōu)缺點
優(yōu)點：其優(yōu)點就是其功能咯，那就是可以找出最優(yōu)的計算模型
缺點：由于其受限頗多，缺點也非常明顯
- 它計算參數(shù)的迭代次數(shù)沒有上限；如果設置迭代次數(shù)的上限，得到的結果可能不是最優(yōu)的結果，甚至可能得到錯誤的結果
- RANSAC只有一定的概率得到可信的模型，概率與迭代次數(shù)成正比
- 它要求設置跟問題相關的閥值
- RANSAC只能從特定的數(shù)據(jù)集中估計出一個模型，如果存在兩個（或多個）模型，RANSAC不能找到別的模型
- 要求數(shù)學模型已知
3. 哈希算法
Hash算法與RANSAC和最小二乘法沒有關系，它是另一種算法，在我們計算機視覺領域它常用來做圖像相似度比較，相似圖像搜索的哈希算法有三種：均值哈希算法（aHash）、差值哈希算法（dHash）和感知哈希算法（pHash）
說到哈希算法就必須要說說散列函數(shù)了，它是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字”指紋”的方法，它把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來，該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個叫做散列值的指紋，散列值常用一個短的隨機字母和數(shù)字組成的字符串來表示
通過哈希算法得到的任意長度的二進制值映射為較短的固定長度的二進制值，即哈希值。此外，哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表示形式，如果通過哈希一段明文得到哈希值，哪怕只更改該段明文中的任意一個字母，隨后得到的哈希值都將不同，哈希算法是一個函數(shù)，能夠把幾乎所有的數(shù)字文件都轉換成一串由數(shù)字和字母構成的看似亂碼的字符串
哈希函數(shù)作為一種加密函數(shù)，它有兩個最重要的特點：
- 不可逆性，輸入信息得出輸出的那個看似亂碼的字符串（哈希值）非常容易，但是從輸出的字符串反推出輸入的結果卻是卻非常非常難
- 輸出值唯一性和不可預測性，只要輸入的信息有一點點區(qū)別，那么根據(jù)哈希算法得出來的輸出值也相差甚遠
漢明距離
漢明距離是用來比較兩個哈希值的接近程度的量，它代表的是兩個數(shù)字對應二進制不同的位置的數(shù)目
3.1 均值哈希算法與差值哈希算法
均值哈希算法的過程分為6步：
- 縮放：圖片縮放為8*8，保留結構，除去細節(jié)
- 灰度化：轉換為灰度圖
- 求平均值：計算灰度圖所有像素的平均值
- 比較：像素值大于平均值記作1，相反記作0，總共64位
- 生成hash：將上述步驟生成的1和0按順序組合起來既是圖片的指紋（hash）
- 對比指紋：將兩幅圖的指紋對比，計算漢明距離，即兩個64位的hash值有多少位是不一樣的，不相同位數(shù)越少，圖片越相似
差值哈希算法與均值哈希算法前期和后期的處理基本相同，只是在比較hash時有不同，差值哈希算法分為6步：
- 縮放：圖片縮放為8*9，保留結構，除去細節(jié)
- 灰度化：轉換為灰度圖
- 比較：像素值大于后一個像素值記作1，相反記作0。本行不與下一行對比，每行9個像素，八個差值，有8行，總共64位
#均值哈希算法
def aHash(img):
#縮放為8*8
img=cv2.resize(img,(8,8),interpolation=cv2.INTER_CUBIC)
#轉換為灰度圖
gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
#s為像素和初值為0，hash_str為hash值初值為''
s=0
hash_str=''
#遍歷累加求像素和
for i in range(8):
for j in range(8):
s=s+gray[i,j]
#求平均灰度
avg=s/64
#灰度大于平均值為1相反為0生成圖片的hash值
for i in range(8):
for j in range(8):
if gray[i,j]>avg:
hash_str=hash_str+'1'
else:
hash_str=hash_str+'0'
return hash_str
#差值感知算法
def dHash(img):
#縮放8*9
img=cv2.resize(img,(9,8),interpolation=cv2.INTER_CUBIC)
#轉換灰度圖
gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
hash_str=''
#每行前一個像素大于后一個像素為1，相反為0，生成哈希
for i in range(8):
for j in range(8):
if gray[i,j]>gray[i,j+1]:
hash_str=hash_str+'1'
else:
hash_str=hash_str+'0'
return hash_str
3.2 離散余弦變換DCT與感知哈希算法
我們在上面說有3中哈希算法，但是只說了兩種，第三種感知哈希算法關系到一個新的東西DCT，也就是離散余弦變換
均值哈希算法過于嚴格，不夠精確，更適合搜索縮略圖，為了獲得更精確的結果可以選擇感知哈希算法，它采用的是DCT（離散余弦變換）來降低頻率的方法，感知哈希算法分為8步：
- 縮小圖片：32 * 32是一個較好的大小，這樣方便DCT計算
- 轉化為灰度圖：把縮放后的圖片轉化為灰度圖。
- 計算DCT:DCT把圖片分離成分率的集合
- 縮小DCT：DCT計算后的矩陣是32 * 32，保留左上角的8 * 8，這些代表圖片的最低頻率
- 計算平均值：計算縮小DCT后的所有像素點的平均值
- 進一步減小DCT：大于平均值記錄為1，反之記錄為0.
- 得到信息指紋：組合64個信息位，順序隨意保持一致性
- 最后比對兩張圖片的指紋，獲得漢明距離即可
離散余弦變換(Discrete Cosine Transform)，主要用于將數(shù)據(jù)或圖像的壓縮，能夠將空域的信號轉換到頻域上，具有良好的去相關性的性能，DCT變換本身是無損的，同時，由于DCT變換是對稱的，所以，我們可以在量化編碼后利用DCT反變換，在接收端恢復原始的圖像信息，DCT變換在當前的圖像分析以及壓縮領域有著極為廣大的用途，我們常見的JPEG靜態(tài)圖像編碼以及MJPEG、MPEG動態(tài)編碼等標準中都使用了DCT變換
這個東西我也沒太懂，只能先為大家提供一點理論的東西了，以后有機會接觸到會細說
4. 圖像聚類算法K-Means
4.1 分類與聚類
分類
分類其實是從特定的數(shù)據(jù)中挖掘模式，作出判斷的過程，分類學習的主要過程可以分為3步：
- 訓練數(shù)據(jù)集存在一個類標記號，判斷它是正向數(shù)據(jù)集還是負向數(shù)據(jù)集
- 然后需要對數(shù)據(jù)集進行學習訓練，并構建一個訓練的模型
- 通過該模型對預測數(shù)據(jù)集進行預測，并計算其結果的性能
聚類
從廣義上說，聚類就是將數(shù)據(jù)集中在某些方面相似的數(shù)據(jù)成員放在一起，一個聚類就是一些數(shù)據(jù)實例的集合，其中處于相同聚類中的數(shù)據(jù)元素彼此相似，但是處于不同聚類中的元素彼此不同
由于在聚類中那些表示數(shù)據(jù)類別的分類或分組信息是沒有的，即這些數(shù)據(jù)是沒有標簽的，所以聚類通常被歸為無監(jiān)督學習（Unsupervised Learning），從這個角度來看，分類就類似于監(jiān)督學習
聚類的目的也是把數(shù)據(jù)分類，但是事先是不知道如何去分的，完全是算法自己來判斷各條數(shù)據(jù)之間的相似性，相似的就放在一起。在聚類的結論出來之前，完全不知道每一類有什么特點，一定要根據(jù)聚類的結果通過人的經驗來分析，看看聚成的這一類大概有什么特點
總之，聚類主要是"物以類聚"，通過相似性把相似元素聚集在一起，它沒有標簽；而分類通過標簽來訓練得到一個模型，對新數(shù)據(jù)集進行預測的過程，其數(shù)據(jù)存在標簽
4.2 K-Means聚類
K-Means聚類是最常用的聚類算法，最初起源于信號處理，其目標是將數(shù)據(jù)點劃分為K個類簇，該算法的最大優(yōu)點是簡單、便于理解，運算速度較快，缺點是要在聚類前指定聚集的類簇數(shù)，該算法的最大優(yōu)點是簡單、便于理解，運算速度較快，缺點是要在聚類前指定聚集的類簇數(shù)
K-Means聚類算法的分析流程
第一步：確定K值，即將數(shù)據(jù)集分為K個類簇或小組
第二步：從數(shù)據(jù)集中隨機選擇K個數(shù)據(jù)點作為質心（Centroid）或數(shù)據(jù)中心
第三步：分別計算每個點到每個質心之間的距離，并將每個點劃分到最近質心的小組
第四步：當每個質心都聚集了一些點后，重新定義算法選出新的質心（對于每個簇，計算其均值，即得到新的k個質心點）
第五步：迭代執(zhí)行3、4步，知道迭代終止或滿足迭代結束條件（聚類結果不再變化）
import cv2
import numpy as np
import matplotlib.pyplot as plt
#讀取原始圖像
img = cv2.imread('lenna.png')
print (img.shape)
#圖像二維像素轉換為一維
data = img.reshape((-1,3))
data = np.float32(data)
#停止條件 (type,max_iter,epsilon)
criteria = (cv2.TERM_CRITERIA_EPS +
cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
#設置標簽
flags = cv2.KMEANS_RANDOM_CENTERS
#K-Means聚類 聚集成2類
compactness, labels2, centers2 = cv2.kmeans(data, 2, None, criteria, 10, flags)
#K-Means聚類 聚集成4類
compactness, labels4, centers4 = cv2.kmeans(data, 4, None, criteria, 10, flags)
#K-Means聚類 聚集成8類
compactness, labels8, centers8 = cv2.kmeans(data, 8, None, criteria, 10, flags)
#K-Means聚類 聚集成16類
compactness, labels16, centers16 = cv2.kmeans(data, 16, None, criteria, 10, flags)
#K-Means聚類 聚集成64類
compactness, labels64, centers64 = cv2.kmeans(data, 64, None, criteria, 10, flags)
#圖像轉換回uint8二維類型
centers2 = np.uint8(centers2)
res = centers2[labels2.flatten()]
dst2 = res.reshape((img.shape))
centers4 = np.uint8(centers4)
res = centers4[labels4.flatten()]
dst4 = res.reshape((img.shape))
centers8 = np.uint8(centers8)
res = centers8[labels8.flatten()]
dst8 = res.reshape((img.shape))
centers16 = np.uint8(centers16)
res = centers16[labels16.flatten()]
dst16 = res.reshape((img.shape))
centers64 = np.uint8(centers64)
res = centers64[labels64.flatten()]
dst64 = res.reshape((img.shape))
#圖像轉換為RGB顯示
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
dst2 = cv2.cvtColor(dst2, cv2.COLOR_BGR2RGB)
dst4 = cv2.cvtColor(dst4, cv2.COLOR_BGR2RGB)
dst8 = cv2.cvtColor(dst8, cv2.COLOR_BGR2RGB)
dst16 = cv2.cvtColor(dst16, cv2.COLOR_BGR2RGB)
dst64 = cv2.cvtColor(dst64, cv2.COLOR_BGR2RGB)
#用來正常顯示中文標簽
plt.rcParams['font.sans-serif']=['SimHei']
#顯示圖像
titles = [u'原始圖像', u'聚類圖像 K=2', u'聚類圖像 K=4',
u'聚類圖像 K=8', u'聚類圖像 K=16', u'聚類圖像 K=64']
images = [img, dst2, dst4, dst8, dst16, dst64]
for i in range(6):
plt.subplot(2,3,i+1), plt.imshow(images[i], 'gray'),
plt.title(titles[i])
plt.xticks([]),plt.yticks([])
plt.show()
K-Means聚類與圖像處理
在圖像處理中國，通過K-Means聚類算法可以實現(xiàn)圖像分割、圖像聚類和圖像識別等操作，我們通過算法可以將這些像素點聚類成K個類簇，然后使用每個簇內的質心點來替換簇內所有的像素點，這樣就能實現(xiàn)在不改變分辨率的情況下量化壓縮圖像顏色，實現(xiàn)圖像顏色層級分割
K-Means聚類在圖像處理的應用中，優(yōu)點非常的明顯，雖然效果不如我們神經網絡那一塊兒的方法，但是在一般情況下也是夠用，而且簡單迅速，對應處理大數(shù)據(jù)集算法效率很高，而當結果簇是密集的時候其效果也是非常理想的
其缺點一個是剛才說過的必須指定類簇數(shù)K，另一個是對噪聲和孤立點數(shù)據(jù)敏感，在一般的問題處理時這些缺陷都可以用其他的方法來彌補文章來源：http://www.zghlxwxcb.cn/news/detail-477634.html
版權聲明：以上學習內容及配圖來自或參考自——八斗人工智能 王小天
如果文章對您有所幫助，記得一鍵三連支持一下哦~文章來源地址http://www.zghlxwxcb.cn/news/detail-477634.html
到了這里，關于計算機視覺的幾個經典算法 —— 最小二乘法 + RANSAC + 哈希算法（附DCT） + 圖像聚類算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
