如何写一个简单的手写识别算法？
可以精準(zhǔn)快速的識(shí)別出自定義的簡(jiǎn)單圖形。
類(lèi)似于下面這種？
Magic Touch - A Free Game by Nitrome
Magic Touch: Wizard for Hire on the App Store on iTunes
吐槽第一名答案， @Vinjn張靜 回答的 $1 gesture recognizer 是比較好的解法。
灑家也有一個(gè)類(lèi)似的算法，借鑒了原始手寫(xiě)ocr的思路來(lái)實(shí)現(xiàn)的。其實(shí)是寫(xiě)在 $1 gesture recognizer 之前的，但沒(méi)有 $1 gesture recognizer 歸納得好，作者jacob還是我偶像。
Realtime Gesture recognition
把所有的筆畫(huà)定義了個(gè)8個(gè)方向，然后將B的筆畫(huà)可以分解成一個(gè)字符串。然后當(dāng)人在觸摸屏上畫(huà)出一個(gè)符號(hào)時(shí)，也將它分解成8個(gè)方向的字符串，最后比較兩個(gè)字符串的距離就能判斷出和不同符號(hào)的近似度。
<img src="http://pic1.zhimg.com/5c8f99d6dfe803d783e215e131cb9f10_b.jpg" data-rawwidth="527" data-rawheight="167" class="origin_image zh-lightbox-thumb" width="527" data-original="http://pic1.zhimg.com/5c8f99d6dfe803d783e215e131cb9f10_r.jpg">
實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單，第一步去噪，因?yàn)椴煌|摸屏的采樣頻率不同。
<img src="http://pic3.zhimg.com/cd33fdcf5a5f58b1c15ad0ffbf44300a_b.jpg" data-rawwidth="376" data-rawheight="188" class="content_image" width="376">
第二步把去噪后的數(shù)據(jù)轉(zhuǎn)換成方向序列，把之前得到的點(diǎn)換成方向序列，并把方向序列歸納到之前定義的8個(gè)方向中去。
<img src="http://pic3.zhimg.com/cd33fdcf5a5f58b1c15ad0ffbf44300a_b.jpg" data-rawwidth="376" data-rawheight="188" class="content_image" width="376">
第三步把連續(xù)一致的方向合并。
<img src="http://pic4.zhimg.com/dd4e09658bfd902a0b72c943687b260b_b.jpg" data-rawwidth="263" data-rawheight="156" class="content_image" width="263">
第四步把小片段的移動(dòng)略去，最后就能得出其實(shí)是畫(huà)了一個(gè)凹的形狀。
<img src="http://pic4.zhimg.com/e8f5c7238045c508d42c0341bf860483_b.jpg" data-rawwidth="470" data-rawheight="170" class="origin_image zh-lightbox-thumb" width="470" data-original="http://pic4.zhimg.com/e8f5c7238045c508d42c0341bf860483_r.jpg">
這個(gè)算法的厲害之處是可以實(shí)時(shí)識(shí)別，畫(huà)到一半也能判斷出來(lái)。
Realtime Gesture recognition 源代碼和demo都在上面了。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
吐槽時(shí)間。。。。
剛寫(xiě)完論文累死了，來(lái)吐槽。。。。
原來(lái)大家都覺(jué)得第一名不靠譜，怎么木有人把我頂上去！我眼紅著那300多票呢！
我來(lái)告訴你為什么第一名不靠譜，
首先ocr拿來(lái)做gesture recognition是不對(duì)滴！
ocr是一個(gè)比gesture recognition更難的問(wèn)題，因?yàn)閛cr得到的是一張圖片，所有點(diǎn)并沒(méi)有時(shí)間戳，而手勢(shì)識(shí)別時(shí)，每一下移動(dòng)是有時(shí)間戳的，所以是知道“怎么畫(huà)出來(lái)”這個(gè)額外信息的。
其次ocr不是這么解釋的。
ocr問(wèn)題的重點(diǎn)是怎么選擇特征，比如知名的uci 數(shù)據(jù)集就有以下這些特征量:
我不懂deep learning，別和我講什么ocropus....
最后貝葉斯講得也不好。
感覺(jué)挑小朋友刺也挺不要臉的，其實(shí)我就是眼紅那300多票。。。
不請(qǐng)自來(lái)，終于有個(gè)能答的了。
用貝葉斯分類(lèi)器做，四五十行Matlab代碼足以搞定。
先占座，容我緩緩道來(lái)，保準(zhǔn)看完大家都會(huì)做模式識(shí)別。
------------------------------
以手寫(xiě)阿拉伯?dāng)?shù)字識(shí)別為例，我們需要設(shè)計(jì)一個(gè)系統(tǒng)，其輸入為一個(gè)M*N像素的圖片，輸出為的0~9的數(shù)字。對(duì)于M*N像素的圖片輸入，可將其視為一個(gè)M*N的矩陣，矩陣的每個(gè)元素代表其對(duì)應(yīng)像素位置上的的灰度值。
我們需要大量的手寫(xiě)樣本來(lái)訓(xùn)練分類(lèi)器，樣本越多越好，自己采集樣本當(dāng)然很累啦，網(wǎng)上有現(xiàn)成的數(shù)據(jù)庫(kù) MNIST Database sam roweis : data
把數(shù)據(jù)庫(kù)中的一部分畫(huà)出來(lái)，大概是這樣子的：
<img src="http://pic1.zhimg.com/6bdccf8a6dc0f8998adf24c430579fc4_b.jpg" data-rawwidth="913" data-rawheight="334" class="origin_image zh-lightbox-thumb" width="913" data-original="http://pic1.zhimg.com/6bdccf8a6dc0f8998adf24c430579fc4_r.jpg">--
先講正態(tài)分布。
單個(gè)變量x的正態(tài)分布，眾所周知，大概是這樣的
<img src="http://pic4.zhimg.com/79f621189519523b42b93951f6bbd393_b.jpg" data-rawwidth="422" data-rawheight="300" class="origin_image zh-lightbox-thumb" width="422" data-original="http://pic4.zhimg.com/79f621189519523b42b93951f6bbd393_r.jpg">
函數(shù)式也很簡(jiǎn)單<img src="http://pic4.zhimg.com/104bbf353af8487e0055d807d8c42e07_b.jpg" data-rawwidth="232" data-rawheight="58" class="content_image" width="232">兩個(gè)變量&lt;x,y&gt;的聯(lián)合分布，大概是這樣子的兩個(gè)變量<x,y>的聯(lián)合分布，大概是這樣子的
<img src="http://pic4.zhimg.com/59e76b87eba74967fc0589219a479b1f_b.jpg" data-rawwidth="300" data-rawheight="227" class="content_image" width="300">
那么對(duì)于k個(gè)變量的輸入，，
應(yīng)該是什么樣子呢~
我也不知道，但是有公式描述它：
<img src="http://pic2.zhimg.com/071cccf42ac95f91441636904b7a6835_b.jpg" data-rawwidth="569" data-rawheight="58" class="origin_image zh-lightbox-thumb" width="569" data-original="http://pic2.zhimg.com/071cccf42ac95f91441636904b7a6835_r.jpg">跟單變量函數(shù)式是不是很像啊~~跟單變量函數(shù)式是不是很像啊~~
其中，u 是 x 的期望值：
<img src="http://pic1.zhimg.com/6f4119728be998032ce9557a35486770_b.jpg" data-rawwidth="291" data-rawheight="32" class="content_image" width="291"> 是 x 的協(xié)方差矩陣，大小為 k*k：
<img src="http://pic4.zhimg.com/b0856458cd49232aea2467b2b4f85823_b.jpg" data-rawwidth="758" data-rawheight="197" class="origin_image zh-lightbox-thumb" width="758" data-original="http://pic4.zhimg.com/b0856458cd49232aea2467b2b4f85823_r.jpg">
嗯，這就是對(duì)k維隨機(jī)變量的正態(tài)分布的描述，簡(jiǎn)單吧。
------------------------------
再講貝葉斯分類(lèi)。
看一維的例子。
假設(shè)有兩種魚(yú)A,B，各自的長(zhǎng)度都呈正態(tài)分布，但期望方差不同，如下圖，藍(lán)色為B的長(zhǎng)度的正態(tài)分布，紅色為A的長(zhǎng)度的正態(tài)分布。
<img src="http://pic4.zhimg.com/818851373fbacf832cd8539d812cf7f7_b.jpg" data-rawwidth="561" data-rawheight="420" class="origin_image zh-lightbox-thumb" width="561" data-original="http://pic4.zhimg.com/818851373fbacf832cd8539d812cf7f7_r.jpg">
問(wèn)題來(lái)了，是我逮到一條魚(yú)，告訴你量出來(lái)長(zhǎng)度為25，別的你都不知道，讓你猜猜到底這魚(yú)是A還是B，你會(huì)怎么答啊？
答A么，錯(cuò)啦！！
這是A，B的長(zhǎng)度的正態(tài)分布，又不是A，B的概率分布！！！
假如逮上來(lái)1000100條魚(yú)，其中100條是A，剩下的1000000條是B；你答A就二了么！
那該怎么答哇~
把各自的正態(tài)分布乘以其概率，再畫(huà)畫(huà)看~
<img src="http://pic2.zhimg.com/c1c5adf8bff164333a5ce14a63a2d089_b.jpg" data-rawwidth="561" data-rawheight="420" class="origin_image zh-lightbox-thumb" width="561" data-original="http://pic2.zhimg.com/c1c5adf8bff164333a5ce14a63a2d089_r.jpg">我去，x=25的地方B比A不知道高到哪里去了！！！所以你們不要見(jiàn)的風(fēng)是的雨啊，懂了沒(méi)有！！！我去，x=25的地方B比A不知道高到哪里去了！！！所以你們不要見(jiàn)的風(fēng)是的雨啊，懂了沒(méi)有！！！
原理是什么呢？貝葉斯老爺子告訴我們這個(gè)定理：
就是說(shuō)啊：要是你知道某種魚(yú)的長(zhǎng)度x的正態(tài)分布，也知道這種魚(yú)在魚(yú)群中的概率，是所有魚(yú)的長(zhǎng)度分布。逮上來(lái)一條魚(yú)的長(zhǎng)度為25，套這個(gè)公式就知道這條魚(yú)是的概率是多少了不是~
剛那個(gè)問(wèn)題不就好答了么，肯定要比較和 的大小啊，哪個(gè)大選哪個(gè)啊~~
這是一維的問(wèn)題，x的緯度高了的話，套用上面的正態(tài)分布的高緯度公式啊，一樣算得出來(lái)
so easy~~
------------------------------
正式步入主題。
我們剛說(shuō)了，對(duì)于M*N的矩陣輸入，直接把它轉(zhuǎn)化成一個(gè)有M*N個(gè)元素的數(shù)組，這個(gè)數(shù)組就是前面的x啦，即，對(duì)于x中的每一個(gè)元素，我們都視之為呈正態(tài)分布。
我們有很多不同手寫(xiě)數(shù)字的樣本噠~算出這些樣本對(duì)應(yīng)的參數(shù)，比如對(duì)于數(shù)字 3：
1. 算出其在樣本庫(kù)中的出現(xiàn)的概率
2. 算出數(shù)字3對(duì)應(yīng)的所有樣本矩陣轉(zhuǎn)換成的向量x的正態(tài)分布:
3. 根據(jù)貝葉斯公式算出 ，這里忽略掉 因?yàn)樗鼘?duì)于所有數(shù)字都一樣，而且我們只是要比較 的大小而已啊~
這不就把貝葉斯分類(lèi)器設(shè)計(jì)好了么，剩下的就簡(jiǎn)單啦~
比如我們現(xiàn)在有一張圖片，轉(zhuǎn)化成矩陣再轉(zhuǎn)化成向量x, 然后你就開(kāi)始算啊，
算一直到的大小，最后比較誰(shuí)大就認(rèn)為這個(gè)圖片上畫(huà)的是誰(shuí)~
------------------------------
Matlab代碼和數(shù)據(jù)庫(kù)附上，大家有興趣可以下了試試看：
Bayes.m_免費(fèi)高速下載
識(shí)別正確率高達(dá)95.3%啊有木有！！！
手寫(xiě)數(shù)字都能識(shí)別了，三角形什么的識(shí)別起來(lái)不是太簡(jiǎn)單啦~就是要大量的樣本而已嘛。
------------------------------
感謝大家的熱情，如果有興趣自學(xué)模式識(shí)別的話 @歐陽(yáng)塵曦@黃升球 ，推薦大家這本書(shū)：
Pattern Classification (豆瓣)
網(wǎng)上中英文pdf都有，大家自己找啦。有人問(wèn)到需要的數(shù)學(xué)基礎(chǔ)，其實(shí)本科的基礎(chǔ)數(shù)學(xué)就足夠用了，遇到不懂的去網(wǎng)上搜，再不行就找人問(wèn)。
------------------------------
關(guān)于不同分類(lèi)器選擇的問(wèn)題，樓下匿名用戶(hù)已經(jīng)講的很好啦，我再補(bǔ)充幾點(diǎn) @用心閣 ：
貝葉斯分類(lèi)器的好處是，簡(jiǎn)單易懂，無(wú)迭代，運(yùn)行速度快，準(zhǔn)確率尚可，但是在某些情況下會(huì)表現(xiàn)不好，而且需要大量樣本來(lái)估算其正態(tài)分布參數(shù)。
KNN分類(lèi)器的原理也很簡(jiǎn)單，比貝葉斯更容易懂，實(shí)現(xiàn)簡(jiǎn)單，需要樣本數(shù)少，但是其迭代次數(shù)多，運(yùn)行速度比貝葉斯要慢個(gè)幾十甚至上百倍，而且根據(jù)k的取值，運(yùn)行結(jié)果準(zhǔn)確率不是很穩(wěn)定。
支持向量機(jī)，前幾年非常火的，需要較好的數(shù)學(xué)基礎(chǔ)才能理解實(shí)現(xiàn)，準(zhǔn)確率較前兩者都好，速度跟貝葉斯在一個(gè)級(jí)別，也不需要迭代，缺點(diǎn)在于，對(duì)于兩個(gè)以上的類(lèi)別，你需要設(shè)計(jì)不止一個(gè)支持向量機(jī)來(lái)分類(lèi)，而且，你需要針對(duì)特定的情況設(shè)置特定的kernal，以達(dá)到滿意的效果。
最近比較火的是神經(jīng)網(wǎng)絡(luò)啦，準(zhǔn)確率超高，表現(xiàn)驚人；但是訓(xùn)練需要迭代，運(yùn)行時(shí)間很長(zhǎng)，大規(guī)模的神經(jīng)網(wǎng)絡(luò)一般的PC運(yùn)行起來(lái)很吃力的。
------------------------------
關(guān)于樣本多少的問(wèn)題 @波紋，你可以這么理解，假如告訴你，某種魚(yú)的長(zhǎng)度呈正態(tài)分布，但是其長(zhǎng)度的方差和均值都未知，那你需要逮幾條魚(yú)出來(lái)量，才敢有把握估算這種魚(yú)長(zhǎng)度的正態(tài)分布呢？當(dāng)然是越多越好啦，具體的證明，你可以搜下：最大似然估計(jì)。我們采集樣本，就是為了估算這種魚(yú)的長(zhǎng)度的正態(tài)分布的參數(shù)。
------------------------------
@chivalry
1. 貝葉斯是假定各個(gè)特征間是獨(dú)立的，代碼中看到用到了協(xié)方差，是不是只要保留協(xié)方差矩陣的對(duì)角線的值？
答：可以看我前面講的多為正態(tài)分布。需要計(jì)算樣本的協(xié)方差矩陣，才能估算樣本的正態(tài)分布。樣本的各個(gè)特征之間是否獨(dú)立，不影響我們對(duì)樣本的正態(tài)分布的估算。
2. 沒(méi)看到乘以先驗(yàn)概率的地方？
答：在樣本中，各個(gè)數(shù)字出現(xiàn)的概率是一樣的（現(xiàn)實(shí)中大多也是如此），要比較后驗(yàn)概率的大小，乘不乘都一樣，你看我就把p(x)給省去了。事實(shí)上，我比較后驗(yàn)概率時(shí)的計(jì)算更加簡(jiǎn)化了：
對(duì)后驗(yàn)概率取對(duì)數(shù)，稱(chēng)之為discriminant function:
<img src="http://pic3.zhimg.com/886a018eabb82c3f930da6bae6bf8ace_b.jpg" data-rawwidth="297" data-rawheight="44" class="content_image" width="297">
<img src="http://pic1.zhimg.com/c4e80d23fa41f64cb70c953f29d18fc8_b.jpg" data-rawwidth="591" data-rawheight="55" class="origin_image zh-lightbox-thumb" width="591" data-original="http://pic1.zhimg.com/c4e80d23fa41f64cb70c953f29d18fc8_r.jpg">
省去對(duì)各個(gè)數(shù)字一樣的項(xiàng)和影響小的項(xiàng)，最后只剩下
<img src="http://pic2.zhimg.com/1ddbfd5cba2ad14c47d5254abff06901_b.jpg" data-rawwidth="298" data-rawheight="54" class="content_image" width="298">甚至連二分之一也不乘了。甚至連二分之一也不乘了。
------------------------------
@黃升球 對(duì)于高像素的圖片，即高緯度的輸入，一般需要做降維處理提取特征向量，PCA和LDA是比較基礎(chǔ)的，也能提高分類(lèi)器的準(zhǔn)確率，這部分確實(shí)需要一點(diǎn)數(shù)學(xué)才好理解。
總結(jié)
以上是生活随笔為你收集整理的如何写一个简单的手写识别算法？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： java学习--装饰器设计模式
- 下一篇： 用计算机弹大白菜鸡毛菜,抖音大白菜、鸡毛