一、歐氏距離
二維的公式
ρ = sqrt( (x1-x2)^2+(y1-y2)^2 )
三維的公式
ρ = sqrt( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 )
n維空間的公式
n維歐氏空間是一個(gè)點(diǎn)集,它的每個(gè)點(diǎn) X 可以表示為 (x[1]，x[2]，…，x[n]) ，其中 x[i](i = 1，2，…，n) 是實(shí)數(shù)，稱為 X 的第i個(gè)坐標(biāo)，兩個(gè)點(diǎn) A = (a[1]，a[2]，…，a[n]) 和 B = (b[1]，b[2]，…，b[n]) 之間的距離 ρ(A，B) 定義為下面的公式。
ρ(A，B) =sqrt [ ∑( a[i] - b[i] )^2 ] (i = 1，2，…，n)
二、K均值算法
k均值(k-means)是聚類算法的一種，聚類分析是根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對(duì)象及其關(guān)系的信息，將數(shù)據(jù)對(duì)象分組。其目標(biāo)是，組內(nèi)的對(duì)象相互之間是相似的，而不同組中的對(duì)象是不同的。組內(nèi)的相似性越大，組間差別越大，聚類就越好。
舉個(gè)例子，在二維平面上有幾百個(gè)點(diǎn)，在笛卡兒坐標(biāo)系中有(x,y)坐標(biāo)，把它們點(diǎn)到紙上，問(wèn)題是如何把它們分成不同組，每個(gè)組里點(diǎn)彼此之前都比較相近，而離其它組的成員又比較遠(yuǎn)。下面介紹的k均值就能干這種事。
基本k均值
基本k均值思想很簡(jiǎn)單，首先，選擇k個(gè)初始質(zhì)心，其中k是用戶指定的參數(shù)，即所期望的簇的個(gè)數(shù)。每個(gè)點(diǎn)被指派到最近的質(zhì)心，而指派到一個(gè)質(zhì)心的點(diǎn)集為一個(gè)簇。然后根據(jù)指派到簇的點(diǎn)，更新每個(gè)簇的質(zhì)心。重復(fù)指派和更新步驟，直到簇不發(fā)生變化，或等價(jià)的，直到質(zhì)心不發(fā)生變化。
三、特征提取
1、第一步，參照網(wǎng)上曾經(jīng)有人的做法:
為簡(jiǎn)單起見(jiàn)，我們使用了最簡(jiǎn)單的圖像特征——黑色像素在圖像中的分布來(lái)進(jìn)行訓(xùn)練和測(cè)試。首先，我們把圖像規(guī)范化為 32*32 像素的圖片，然后按 2*2 分切成 16*16 共 256 個(gè)子區(qū)域，然后統(tǒng)計(jì)這 4 個(gè)像素中黑色像素的個(gè)數(shù)，組成 256 維的特征矢量，如下是數(shù)字 2 的一個(gè)特征矢量：
0 0 4 4 4 2 0 0 0 0 0 0 0 0 2 4 0 0 4 4 4 2 0 0 0 0 0 0 0 0 2 4 2 2 4 4 2 1 0 0 0 0 0 0 1 2 3 4 4 4 4 4 0 0 0 0 0 0 0 0 2 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 2 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 2 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 2 4 4 4 4 4 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 4 4 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 2 4 4 4 2 2 2 2 4 3 2 2 2 2 2 0 2 4 4 4 0 0 0 0 4 2 0 0 0 0 0 0 2 4 4 4 0 0 0 0 4 2 0 0 0 0 0 0 2 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 2 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 2 4 4 4
相應(yīng)地，因?yàn)槲覀冎恍枰R(shí)別 0~9 共 10 個(gè)數(shù)字，所以創(chuàng)建一個(gè) 10 維的矢量作為結(jié)果，數(shù)字相應(yīng)的維置為 1 值，其它值為 0。數(shù)字 2 的結(jié)果如下：0 0 1 0 0 0 0 0 0 0
核心代碼為:
- For m_i As Integer = 1 To 16
- myinitwidth = myendwidth
- myendwidth += jiange
- For myi As Integer = myinitwidth To myendwidth
- For myj As Integer = myinitheight To myendheight
- mycolor = myybcominfo.mybitmap.GetPixel(myi, myj)
- If mycolor.B = 0 And mycolor.R = 255 And mycolor.G = 0 Then
- While (Not Monitor.TryEnter(mymonitorobj))
- Thread.Sleep(1)
- End While
- myjgtz(mycount) += 1
- Monitor.Exit(mymonitorobj)
- Thread.Sleep(1)
- End If
- Next
- Next
- mycount += 1
- myendwidth += 1
- Next
2、在第一步的特征基礎(chǔ)上進(jìn)一步加工，加上位置信息，以位置做為權(quán)重，調(diào)整第一步的特征矢量，核心代碼為:
- For mi As Integer = 0 To 15
- If myjgtz(mi) > 0 Then
- pictz(myii, myjj, m_j) += mi * myjgtz(mi)
- End If
- myjgtz(mi) = 0
- Next
3、第三步計(jì)算每個(gè)數(shù)字的K均值，核心代碼為:
- '計(jì)算K均值
- Dim mmsum As Double = 0
- For myii As Integer = 0 To 9
- mystr &= vbCrLf & myii & "的樣本均值是：" & vbCrLf
- For myk As Integer = 0 To 15
- mmsum = 0
- For myjj As Integer = 0 To 9
- mmsum += pictz(myii, myjj, myk)
- ProgressBar1.Value = count
- count += 1
- Next
- mmsum /= 10
- ktz(myii, myk) = mmsum
- mystr &= ktz(myii, myk) & ","
- Next
- mystr &= vbCrLf
- Next
最后，進(jìn)行待識(shí)別數(shù)字的特征值，然后進(jìn)行歐氏距離對(duì)比
- Dim jqtz(16) As Integer
- '歐氏距離
- Dim mys(10) As Integer
- Dim temp As Integer = 1000000000
- Dim jgnum As Integer = -1
- For m_iii As Integer = 0 To 9
- mys(m_iii) = 0
- For m_jjj As Integer = 0 To 15
- mys(m_iii) += Pow(ktz(m_iii, m_jjj) - jqtz(m_jjj), 2)
- Next
- If mys(m_iii) < temp Then
- temp = mys(m_iii)
- jgnum = m_iii
- End If
- Next
- jg.Text = ""
- For m_iii = 0 To 9
- jg.Text &= m_iii & ":" & mys(m_iii) & vbCrLf
- Next
- jg.Text &= "結(jié)果是：" & jgnum
實(shí)驗(yàn)表明，算法有一定的識(shí)別率，進(jìn)一步提高需要改進(jìn)算法，對(duì)于仿宋的識(shí)別率最高，達(dá)90%，黑體、楷體等識(shí)別率也可以，手寫數(shù)字，只要書寫較規(guī)范，然后寫的位置適當(dāng)，在方框較中間，識(shí)別率較高
