高強(qiáng)　余軍　亢治虎

摘要：簡(jiǎn)譜數(shù)字識(shí)別是光學(xué)樂(lè)譜識(shí)別中的一個(gè)重要分支，傳統(tǒng)的識(shí)別方法是模板匹配，該方法計(jì)算量大，且對(duì)模板的依賴性很強(qiáng)，導(dǎo)致其魯棒性較弱，對(duì)圖像的噪聲和位移敏感?？紤]到簡(jiǎn)譜數(shù)字識(shí)別規(guī)模較小，通過(guò)分析數(shù)字對(duì)噪聲較為穩(wěn)定的幾何特征，提出一種改進(jìn)的投影特征匹配法對(duì)簡(jiǎn)譜數(shù)字進(jìn)行快速識(shí)別匹配。理論分析和實(shí)驗(yàn)結(jié)果表明，改進(jìn)的投影特征匹配法與傳統(tǒng)的模板匹配法相比，識(shí)別精度和速度有所提高，魯棒性也更強(qiáng)。

關(guān)鍵詞：投影；數(shù)字識(shí)別；模板匹配；歐氏距離

DOIDOI：10.11907/rjdk.151538

中圖分類號(hào)：TP317.4

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：16727800（2015）006017604

作者簡(jiǎn)介作者簡(jiǎn)介：高強(qiáng)（1989-），男，湖北黃岡人，武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)閳D像處理與模式識(shí)別；余軍（1992-），男，湖北天門人，武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)槟Ｊ阶R(shí)別與智能系統(tǒng)；亢治虎（1988-），男，湖北襄陽(yáng)人，武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

0 引言

光學(xué)文字識(shí)別[1]（Optical Character Recogniton，OCR）是模式識(shí)別學(xué)科的一個(gè)傳統(tǒng)研究領(lǐng)域。在音樂(lè)界，相對(duì)應(yīng)于光學(xué)文字識(shí)別，有一個(gè)重要分支——光學(xué)樂(lè)譜識(shí)別[2]（Optical Music Recognition，OMR）。有了OMR技術(shù)，只需將紙質(zhì)教材上的樂(lè)譜作一個(gè)清晰的掃描，由計(jì)算機(jī)進(jìn)行演奏或者生成格式化的樂(lè)譜文件（MusicXML文件等），這無(wú)疑大大簡(jiǎn)化了錄入樂(lè)譜的步驟，大幅提高了樂(lè)譜錄入效率。

最為經(jīng)典的OMR技術(shù)莫過(guò)于模板匹配法。該方法的基本思想是通過(guò)為每個(gè)待識(shí)別字符定義一個(gè)典型的標(biāo)準(zhǔn)模板，然后采用直方圖法[3]、輪廓矩[4，5]、歐氏距離[6]、曼哈頓距離[7]等度量方法比較待識(shí)別的樣本與標(biāo)準(zhǔn)模板，根據(jù)度量方法得出的相似度來(lái)決定樣本與模板是否屬于同一類別[8]。

由于標(biāo)準(zhǔn)模板的存在，常規(guī)模板匹配方法識(shí)別與數(shù)字模板數(shù)字字體一致時(shí)的識(shí)別率很高，但是它對(duì)噪聲敏感，并且對(duì)數(shù)字的不同字體也不具有適應(yīng)性，魯棒性不強(qiáng)[9]——當(dāng)數(shù)字的字體字形變化、識(shí)別圖片的分辨率較低或噪點(diǎn)較多時(shí)，該方法的識(shí)別率下降。另外，由于常規(guī)模板匹配直接涉及到兩個(gè)圖像矩陣級(jí)別的運(yùn)算，其計(jì)算量通常較大，時(shí)間開(kāi)銷較多[10]。

考慮到簡(jiǎn)譜中的數(shù)字識(shí)別規(guī)模較小，只有0～7八個(gè)數(shù)字，可通過(guò)分析簡(jiǎn)譜數(shù)字對(duì)噪聲較為穩(wěn)定的幾何特征和水平或垂直投影特征，避開(kāi)常規(guī)模板匹配法在魯棒性上的劣勢(shì)，應(yīng)用一種改進(jìn)的投影特征匹配法對(duì)簡(jiǎn)譜數(shù)字進(jìn)行快速識(shí)別匹配，并給出具體的算法流程，分析了算法的時(shí)間復(fù)雜度。理論分析和實(shí)驗(yàn)結(jié)果表明，改進(jìn)的投影特征匹配法與傳統(tǒng)的模板匹配法相比，識(shí)別精度和速度有所提高，魯棒性也更強(qiáng)。

1 算法原理

1.1 預(yù)處理

相機(jī)獲取的信息多為32位真彩色信息，但樂(lè)譜只有黑白兩色，人眼分辨樂(lè)譜不需要其它任何顏色信息。因此，在開(kāi)始數(shù)字識(shí)別之前，可先采用加權(quán)平均值法轉(zhuǎn)換三通道彩色樂(lè)譜到單通道灰度圖，將彩色圖像轉(zhuǎn)換為8位灰度圖，將圖像的RGB三維信息轉(zhuǎn)換為一維，可大幅度減小計(jì)算量，公式如下[11]：

上式中，紅綠藍(lán)三通道的權(quán)值是根據(jù)人眼對(duì)顏色的敏感度測(cè)定的，所以，運(yùn)用式（1）可以得到較為理想的灰度圖像。

為進(jìn)一步減少計(jì)算量，還需要做二值化處理。將樂(lè)譜背景置為黑色（值為0），音符置為白色（值為255），在方便人眼觀察的同時(shí)，可以為后續(xù)的圖像處理技術(shù)帶來(lái)操作上的便利。

1.2 投影特征匹配

由于待識(shí)別的目標(biāo)結(jié)果只有0～7八種數(shù)字，采用水平投影法和垂直投影法[12]將圖像從二維矩陣降維到一維向量以進(jìn)行快速匹配。

設(shè)圖像寬度和高度分別為w和h，現(xiàn)對(duì)其做水平投影，得到后的向量除以255w，所得到的向量下標(biāo)對(duì)應(yīng)圖片坐標(biāo)系中的縱坐標(biāo)，而指定下標(biāo)的值對(duì)應(yīng)某一像素水平方向所有非零（白色）像素占該圖片寬度的百分比。同理再對(duì)其做垂直投影，得到后的向量除以255h，則所得到的向量下標(biāo)對(duì)應(yīng)圖片坐標(biāo)系中的橫坐標(biāo)，而指定下標(biāo)的值對(duì)應(yīng)某一像素垂直方向所有非零（白色）像素占該圖片高度的百分比。其它數(shù)字依此類推，所有數(shù)字的水平、垂直投影向量如圖1所示。

觀察8個(gè)數(shù)字及其水平、垂直投影向量的特征，這一步需要選取相對(duì)比較穩(wěn)定，即能夠直接從圖像上體現(xiàn)出的不怎么受噪聲影響、魯棒性較強(qiáng)的特征來(lái)區(qū)分它們。可利用大部分圖像中都存在的接近于100%的峰值區(qū)間，它們的水平位置特征比較具有唯一性。具體區(qū)分方法如下：

（1）8個(gè)數(shù)字中，只有2和4的水平投影接近于100%的峰值區(qū)間存在于向量后半段（反映到圖2中2的灰色部分），但2的垂直投影不存在接近于100%的峰值區(qū)間（反映到圖2中不存在豎直基本全部貫穿圖像的白色連通域），而4的垂直投影存在接近于100%的峰值區(qū)間且位置同樣在向量后半段（反映到圖2中4的灰色部分）。

（2）剩下的6個(gè)數(shù)字中，只有1、5、7的水平投影的接近于100%的峰值區(qū)間存在于向量前1/3段（反映到圖3中的水平灰色矩形）。其中，1的垂直投影存在接近于100%的峰值區(qū)間且位置在向量后2/3段（反映到圖3中1的豎直灰色矩形，該特征在6個(gè)數(shù)字中具有唯一性，可直接篩選出），5和7的垂直投影都不存在接近于100%的峰值區(qū)間（反映到圖3中，5和7的圖像不存在豎直基本全部貫穿圖像的白色連通域），但5的垂直投影的局部峰值存在于向量的前1/3段和后1/3段，而7的垂直投影的局部峰值只存在于向量的中部附近（反映到圖3中5和7的豎直灰色部分）。

（3）剩下3、6、0三個(gè)數(shù)字，可以通過(guò)比較其垂直投影在前半段的峰值與后半段的峰值差來(lái)篩選出3——一般對(duì)于0和6，前后峰值差超過(guò)10%，而3的前后峰值差則會(huì)小于10%（反映在圖4中3圖像的灰色部分）。最后可利用6的水平投影在前半段存在的跳變（反映在圖4中6圖像的灰色部分）區(qū)分出6和0。

進(jìn)一步總結(jié)，上述3步也即是說(shuō)，僅需要提取水平和垂直向量的峰值區(qū)間的位置作為特征，即可區(qū)分出0～7八個(gè)數(shù)字。

算法1 投影特征匹配算法

輸入：二值化后的矩形圖片矩陣I。

輸出：該符號(hào)的類型type（0～7為數(shù)字，-1為識(shí)別錯(cuò)誤）。

Step 1： 初始化type=-1，計(jì)算I的寬度w與高度h。

1.3 時(shí)間復(fù)雜度

設(shè)圖像的寬和高分別為w與h，則Step 2中求水平投影與垂直投影向量并對(duì)其縮放各只需要遍歷一遍圖像，時(shí)間頻度為T（w，h）=2wh；Step 3中，只需各自遍歷一遍水平和垂直投影向量即可計(jì)算出最大值橫縱坐標(biāo)、平均值以及前后半段的峰值，時(shí)間頻度T（w，h）=w+h；Step 4～Step 10中，只用到了基本乘除運(yùn)算和比較操作，時(shí)間頻度為T（w，h）=C（常數(shù)）；Step 11中，還需再遍歷一遍水平投影向量，時(shí)間頻度為T（w，h）=h。

綜上所述，該算法的總時(shí)間頻度為T（w，h）=2wh+w+2h+C，時(shí)間復(fù)雜度為O（wh）。

2 實(shí)驗(yàn)結(jié)果與分析

為了比較傳統(tǒng)模版匹配方法與投影特征匹配方法在識(shí)別精度、識(shí)別速度與識(shí)別魯棒性上的區(qū)別，本文對(duì)《天空之城》和《鈴兒響叮當(dāng)》兩首樂(lè)曲的簡(jiǎn)譜進(jìn)行識(shí)別測(cè)試。兩種方法采用相同算法預(yù)處理和提取簡(jiǎn)譜中的數(shù)字，只在匹配階段，傳統(tǒng)模板匹配采用歐氏距離作為度量方法，而投影特征匹配采用本文方法，其識(shí)別結(jié)果如表1、表2所示。

從以上識(shí)別結(jié)果可以看出，在識(shí)別精度方面，2種方法都可取得較為理想的識(shí)別準(zhǔn)確率，但投影特征匹配法的精度要略高一些；在識(shí)別速度方面，投影特征匹配法雖然增加了提取特征的過(guò)程，但由于信息量減少，還是縮短了10%左右的識(shí)別時(shí)間；在識(shí)別魯棒性方面，歐氏距離法受模板的影響明顯較大，例如表2中識(shí)別2和表1中識(shí)別6時(shí)，由于圖片所用簡(jiǎn)譜數(shù)字與模板稍有變化（數(shù)字的平移或字體的變換），帶來(lái)識(shí)別精度的下降，而投影特征匹配法則由于比較的是數(shù)字的幾何特征，而它反映了不同數(shù)字之間的根本區(qū)別，相對(duì)于數(shù)字整體而言，抗噪性大大增強(qiáng)。

3 結(jié)語(yǔ)

通過(guò)分析簡(jiǎn)譜數(shù)字的幾何特征，提出了投影特征匹配法，即一種將圖像從二維矩陣降維到一維向量的快速匹配方法。在給出具體的算法思想之后，計(jì)算了算法的時(shí)間復(fù)雜度，并用不同的實(shí)驗(yàn)結(jié)果證實(shí)了算法的識(shí)別精度、識(shí)別速度和魯棒性都要優(yōu)于傳統(tǒng)的歐氏距離模板匹配法。而對(duì)于如何將數(shù)字識(shí)別擴(kuò)展到字符甚至漢字的快速識(shí)別、如何進(jìn)一步提高識(shí)別精度等，相關(guān)工作有待進(jìn)一步展開(kāi)。

參考文獻(xiàn)：

[1] 姚超，盧朝陽(yáng)，李靜，等.用于手寫文字識(shí)別的MQDF替代參數(shù)選擇方法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（12）：6569.

[2] 何歡.光學(xué)樂(lè)譜識(shí)別技術(shù)研究[D].北京：北方工業(yè)大學(xué)，2011.

[3] 李小偉. 基于FPGA的灰度圖像模板匹配并行處理研究[D].武漢：華中科技大學(xué)，2013.

[4] 王慧.基于模板匹配的手寫體字符識(shí)別算法研究[D].北京：北京交通大學(xué)，2012.

[5] 孔金生，張小鳳，王璇.基于輪廓特征的模板匹配方法及其應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2008（22）：201203.

[6] 黃琛.基于Hausdorff距離模板匹配的行人檢測(cè)算法研究與應(yīng)用[D].北京：清華大學(xué)，2006.

[7] CHING Y SUEN，JINNA TAN.Analysis of errors of handwritten digits made by a multitude of classifiers[J].Pattern Recognition Letters archive， 2005.

[8] G LOULOUDIS， B GATOS，I PRATIKAKIS，et al.Text line detection in handwritten documents[J].Pattern Recognition archive，2008，41（12）：758772.

[9] 唐琎，李青.一種快速的模板匹配算法[J].計(jì)算機(jī)應(yīng)用，2010（6）：15591561，1564.

[10] 邵平，楊路明，黃海濱，等.基于積分圖像的快速模板匹配[J].計(jì)算機(jī)科學(xué)，2006（12）：225229.

[11] ALEX ZELINSKY.Learning OpenCV computer vision with the OpenCV library[J].IEEE robotics and automation magazine，2009，16（3）：100110.

[12] 哈勤和，張暢，王澤兵，等.圖象的快速一維投影模板匹配[J].計(jì)算機(jī)工程與應(yīng)用，1998（1）：3839，50.

責(zé)任編輯（責(zé)任編輯：黃 健）

英文摘要Abstract：Numbered musical notation recognition is an important branch of optical music recognition， the traditional method is the template matching， but its amount of calculation is very large， and very dependent on the templates， resulting that its weaker， sensitive to image noise and displacement. Considering the small scale of notation numeral recognition， analyzing the digital noise more stable geometry， the paper put forward an improved projection characteristics matching method for quickly identifying notation numbers. Theoretical analysis and experimental results indicate that comparing with traditional method of template matching， the projection characteristics template matching method is faster， more accurate and robust.

英文關(guān)鍵詞Key Words： Projection；Number Identification；Template Matching；Euclidean Distance