張慧的博客

 一、歐氏距離

二維的公式

　　ρ = sqrt( (x1-x2)^2+(y1-y2)^2 )

三維的公式

　　ρ = sqrt( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 )

n維空間的公式

　　n維歐氏空間是一個點集,它的每個點 X 可以表示為 (x[1]，x[2]，…，x[n]) ，其中 x[i](i = 1，2，…，n) 是實數，稱為 X 的第i個坐標，兩個點 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)是聚類算法的一種，聚類分析是根據在數據中發現的描述對象及其關系的信息，將數據對象分組。其目標是，組內的對象相互之間是相似的，而不同組中的對象是不同的。組內的相似性越大，組間差別越大，聚類就越好。

舉個例子，在二維平面上有幾百個點，在笛卡兒坐標系中有(x,y)坐標，把它們點到紙上，問題是如何把它們分成不同組，每個組里點彼此之前都比較相近，而離其它組的成員又比較遠。下面介紹的k均值就能干這種事。

基本k均值

基本k均值思想很簡單，首先，選擇k個初始質心，其中k是用戶指定的參數，即所期望的簇的個數。每個點被指派到最近的質心，而指派到一個質心的點集為一個簇。然后根據指派到簇的點，更新每個簇的質心。重復指派和更新步驟，直到簇不發生變化，或等價的，直到質心不發生變化。

三、特征提取

1、第一步，參照網上曾經有人的做法:

為簡單起見，我們使用了最簡單的圖像特征——黑色像素在圖像中的分布來進行訓練和測試。首先，我們把圖像規范化為 32*32 像素的圖片，然后按 2*2 分切成 16*16 共 256 個子區域，然后統計這 4 個像素中黑色像素的個數，組成 256 維的特征矢量，如下是數字 2 的一個特征矢量：
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
相應地，因為我們只需要識別 0~9 共 10 個數字，所以創建一個 10 維的矢量作為結果，數字相應的維置為 1 值，其它值為 0。數字 2 的結果如下：0 0 1 0 0 0 0 0 0 0

核心代碼為:

Vb.net代碼  

1. For m_i As Integer = 1 To 16  
2.      myinitwidth = myendwidth  
3.      myendwidth += jiange  
4.      For myi As Integer = myinitwidth To myendwidth  
5.          For myj As Integer = myinitheight To myendheight  
6.              mycolor = myybcominfo.mybitmap.GetPixel(myi, myj)  
7.              If mycolor.B = 0 And mycolor.R = 255 And mycolor.G = 0 Then  
8.                  While (Not Monitor.TryEnter(mymonitorobj))  
9.                      Thread.Sleep(1)  
10.                  End While  
11.                  myjgtz(mycount) += 1  
12.                  Monitor.Exit(mymonitorobj)  
13.                  Thread.Sleep(1)  
14.              End If  
15.          Next  
16.      Next  
17.      mycount += 1  
18.      myendwidth += 1  
19.  Next  

2、在第一步的特征基礎上進一步加工，加上位置信息，以位置做為權重，調整第一步的特征矢量，核心代碼為:

Vb.net代碼  

1. For mi As Integer = 0 To 15  
2.     If myjgtz(mi) > 0 Then  
3.         pictz(myii, myjj, m_j) += mi * myjgtz(mi)  
4.     End If  
5.     myjgtz(mi) = 0  
6. Next  

3、第三步計算每個數字的K均值，核心代碼為:

Vb.net代碼  

1. '計算K均值  
2.        Dim mmsum As Double = 0  
3.        For myii As Integer = 0 To 9  
4.            mystr &= vbCrLf & myii & "的樣本均值是：" & vbCrLf  
5.            For myk As Integer = 0 To 15  
6.                mmsum = 0  
7.                For myjj As Integer = 0 To 9  
8.                    mmsum += pictz(myii, myjj, myk)  
9.                    ProgressBar1.Value = count  
10.                    count += 1  
11.                Next  
12.                mmsum /= 10  
13.                ktz(myii, myk) = mmsum  
14.                mystr &= ktz(myii, myk) & ","  
15.            Next  
16.            mystr &= vbCrLf  
17.        Next  

最后，進行待識別數字的特征值，然后進行歐氏距離對比

Vb.net代碼  

1. Dim jqtz(16) As Integer  
2.                 '歐氏距離   
3.         Dim mys(10) As Integer  
4.         Dim temp As Integer = 1000000000  
5.         Dim jgnum As Integer = -1  
6.         For m_iii As Integer = 0 To 9  
7.             mys(m_iii) = 0  
8.             For m_jjj As Integer = 0 To 15  
9.                 mys(m_iii) += Pow(ktz(m_iii, m_jjj) - jqtz(m_jjj), 2)  
10.             Next  
11.             If mys(m_iii) < temp Then  
12.                 temp = mys(m_iii)  
13.                 jgnum = m_iii  
14.             End If  
15.         Next  
16.         jg.Text = ""  
17.         For m_iii = 0 To 9  
18.             jg.Text &= m_iii & ":" & mys(m_iii) & vbCrLf  
19.         Next  
20.         jg.Text &= "結果是：" & jgnum  

實驗表明，算法有一定的識別率，進一步提高需要改進算法，對于仿宋的識別率最高，達90%，黑體、楷體等識別率也可以，手寫數字，只要書寫較規范，然后寫的位置適當，在方框較中間，識別率較高