樂譜圖像樂符分割技術(shù)

摘 要:提出基于圖段拓撲關(guān)系的譜線刪除方法，以避免譜線過刪除現(xiàn)象;提出雙向游程編碼結(jié)合使用的符干分割方法，克服了現(xiàn)有方法對復雜音符適應性差、分割結(jié)果不完整等缺陷;提出音符先驗知識引導下的符頭切割與檢測算法，以解決粘連符頭的切分問題;提出基于塊狀體分割和特征檢測的符梁分割算法，設(shè)計了適用于樂譜版面的文字和線條提取算法。該方法應用在樂譜識別系統(tǒng)中分割樂符具有良好的性能，尤其對樂譜內(nèi)容復雜、樂符排列密集等情況有較強適應能力。

關(guān)鍵詞:光學樂譜識別; 譜線刪除; 樂符分割; 文字提取; 游程編碼

中圖法分類號: TP391.41

文獻標志碼:A

文章編號:1001-3695(2010)02-0784-04

doi:10.3969/j.issn.1001-3695.2010.02.108

Music symbols segmentation in music score images

LIU Xiao-xiang

(Dept. of Computer Science， Zhuhai College， Jinan University， Zhuhai Guangdong 519070， China)

Abstract: Firstly，proposed a staff lines removal approach based on analyzing topological relationship among run-length segments， as a result， staff lines over-removal could avoid. Secondly，proposed a stems segmentation approach， using both vertical and horizontal run-length coding. It could overcome the weaknesses of current methods such as the fragmentary results and poor adaptability to the complex notes. Thirdly，presented an approach for note heads segmentation， employing the prior know-ledge of music notes to split and separate touched note heads. Lastly，designed a block-based approach for beam segmentation and an applied approach for text and curves extraction. Implemented the approaches in one optical music recognition system. It shows good performance and powerful adaptability， especially for the situation of intensive layout of music symbols， or the case of complicated music score images.Key words:optical music recognition; staff lines removal; music symbols segmentation; text extraction; run-length coding

光學樂譜識別(optical music recognition)技術(shù)是對人類讀譜智能行為的模擬、物化和延伸，實現(xiàn)了傳統(tǒng)紙質(zhì)樂譜向數(shù)字樂譜的高速自動轉(zhuǎn)換，是音樂數(shù)字化的重要課題。樂譜在信息表達上呈現(xiàn)出諸多不利于計算機閱讀的特性:a)版面復雜，樂譜是一個由線條圖形、塊圖形、符號、文字等多種形態(tài)元素(統(tǒng)稱為樂符)混合排列而成的復雜多變的二維數(shù)據(jù)集合;b)多粘連，樂符交錯嵌入在譜線當中，同時樂符間也存在交疊或粘連;c)多態(tài)，樂符中的音符(由符頭、符干、符尾/梁構(gòu)成，描述音樂事件，)是一種具有多態(tài)性的復雜模式對象，同樣的音樂事件可以呈現(xiàn)出多種不同的音符形態(tài)[1]。這些特性決定了樂譜內(nèi)容不存在統(tǒng)一的識別方法，必須采用“因地制宜、分而治之”的策略，預先將不同特征的樂符實行分割，然后選擇適宜的方法識別之[2]。可見，樂符分割技術(shù)為樂譜識別提供基本的待處理單元，是進一步進行音符結(jié)構(gòu)分析、符號/文字識別乃至樂譜理解的重要前提與基礎(chǔ)。

本文從譜線刪除、符干分割、符頭分割、符梁分割、文字/線條圖形提取五個方面對樂譜圖像中的樂符分割技術(shù)進行了研究。主要技術(shù)特色如下:a)提出一種基于圖段拓撲關(guān)系分析的譜線刪除方法。與現(xiàn)有方法相比，該方法在提高刪除單元表達層次的同時，強調(diào)對刪除單元周邊環(huán)境特征的分析和判斷，能夠明顯減少譜線過刪除現(xiàn)象的發(fā)生，保證了樂符在譜線刪除之后的完整性。b)遵循人工讀譜思維的逐步求精原則，設(shè)計了基于垂直游程編碼的粗提取、基于水平游程編碼的精檢測的符干分割算法。該方法能避開符梁、符頭的相交粘連干擾，完整提取符干。c)利用音符先驗知識和已有的譜線、符干結(jié)果對符頭進行切割，解決了粘連符頭的切分問題。d)提出以塊狀體為處理單元的符梁分割方法。相比傳統(tǒng)基于直線識別的符梁檢測方法，該方法能避開粘連符梁的切分難題。e)針對樂譜版面特點，設(shè)計了簡單實用的文字和線條提取算法。

1 譜線刪除

譜線是樂譜的書寫線，用于規(guī)范樂符號的書寫區(qū)域和尺寸。由于樂譜中的絕大多數(shù)符號都嵌入在譜線中，同時譜線本身也提供了重要的信息，譜線的檢測與去除是實現(xiàn)樂符分割的首要關(guān)鍵環(huán)節(jié)。

1.1 譜線檢測與譜線參數(shù)獲取

在刪除譜線之前需要確定每條譜線的位置，水平投影方法是一種直觀、簡便的譜線檢測方法[3]。將樂譜圖像沿水平方向投影生成投影直方圖，直方圖中五條相鄰的峰值線即可確定譜線的位置，如圖1所示。

譜線的線寬與間距決定了樂譜版面的尺寸規(guī)格，是兩個非常重要的參數(shù)，可作為后面眾多分割、識別閾值的設(shè)計依據(jù)和標準。由于譜線具有方向水平、線寬不變、間距均勻和覆蓋廣的特點，可以通過統(tǒng)計不同長度的黑、白游程頻數(shù)的方法來計算此兩項參數(shù)(游程是指二值圖像中一條掃描線上連續(xù)同值的像素集合)。計算步驟如下:

a)對圖像進行垂直方向的游程編碼(描線方向為垂直方向，從左至右逐列掃描);

b)統(tǒng)計出黑(前景)游程隨長度變化的頻率，獲得直方圖，圖中最大峰值對應的游程長度為譜線線寬;

c)統(tǒng)計出白(背景)游程隨長度變化的頻率，獲得直方圖，圖中最大峰值對應的游程長度為譜線間距。

1.2 譜線過刪現(xiàn)象及其解決思路

譜線刪除是一項具有挑戰(zhàn)性的工作，原因是絕大多數(shù)樂符都交錯嵌入在譜線中。刪除時既要達到樂符/譜線分離的目的，又要確保樂符的完整性不遭到破壞，而如何盡可能地避免過刪更是其中的難點。所謂過刪現(xiàn)象，是指在刪除譜線的同時也刪除了原本屬于樂符對象的部分像素，造成樂符被打碎，給后一步的識別工作帶來困難，如圖2所示。

提高刪除單元的表達層次和范圍是克服過刪問題的有效途徑之一。譜線像素在宏觀上具有群體特征，在垂直游程編碼的基礎(chǔ)上可以聚合成具有強線條特征的圖段。研究表明，采用圖段幾何特征來判別譜線的方法能夠明顯減少過刪現(xiàn)象的發(fā)生[4]。然而現(xiàn)有圖段方法僅以圖段自身的幾何特征作為譜線判據(jù)，在不少情形下仍會出現(xiàn)過刪。典型的情形有:樂符中的細線與譜線相切;樂符中的細線與譜線小角度相交。可見，此類方法尚存較大的改進空間。

不失一般性，這里以連音線與譜線相切和相交的圖段實例來分析過刪問題及其解決思路。

圖3左為掃描樂譜圖像(局部)，右為樂譜圖像中連音線與譜線相切、相交處的圖段表示。從右圖可以看到，重疊圖段(樂符一部分，應保留)與譜線圖段(應刪除)在形態(tài)特征上沒有明顯差別，也就是說，單純依據(jù)圖段幾何屬性來區(qū)分兩者是非常困難的。因此，只能從圖段的周邊環(huán)境中尋找區(qū)分依據(jù)。考察圖段與鄰接圖段的連接關(guān)系可以發(fā)現(xiàn)，當譜線與其他對象發(fā)生交叉重疊時，譜線圖段總是交叉處的分支，左右兩段與其他圖段的拓撲關(guān)系是一一鄰接;而重疊圖段總是相當于一個交點域，左右兩段至少有一處與其他圖段的拓撲關(guān)系是一對多鄰接。

由上分析可知，圖段間的拓撲關(guān)系能夠更全面、可靠地區(qū)分譜線與非譜線。依據(jù)該思路，本文提出一種基于圖段拓撲關(guān)系分析的譜線刪除方法。

1.3 基于圖段拓撲關(guān)系分析的譜線刪除方法

為方便算法描述，給出以下定義:

定義1 鄰接游程。如果左右相鄰兩條掃描線上的兩個游程各自存在至少一個像素具有相同的行坐標，那么稱這兩個游程具有鄰接關(guān)系。

定義2 游程鄰接圖。設(shè)G代表游程鄰接圖，它是一個二元組〈V，E〉，即G=〈V，E〉。其中:V為節(jié)點集合，節(jié)點為游程對象;E為邊集合，記錄游程之間的鄰接關(guān)系。

定義3 一一鄰接。如果具有鄰接關(guān)系的兩個游程不再與它們所在的掃描線上的其他游程有鄰接關(guān)系，那么稱這兩個游程具有一一鄰接關(guān)系。

定義4 圖段。由一組相鄰游程組成的集合稱之為圖段，且這些游程滿足以下條件:各游程自左向右連續(xù)排列，左右相鄰游程具有一一鄰接關(guān)系，同時兩端游程與集合以外的游程不具備一一鄰接關(guān)系。

定義5 父子圖段。如果圖段A的最后一個游程與圖段B的第一個游程具有鄰接關(guān)系，則稱A是B的父圖段，B是A的子圖段。

定義6 圖段鄰接圖。設(shè)G代表圖段鄰接圖，是一個二元組〈V，E〉，即G=〈V，E〉。其中:V為節(jié)點集合，節(jié)點為圖段對象;E為邊集合，記錄相鄰圖段之間的父子關(guān)系。

定義7 圖段拓撲類型。如果圖段無父子圖段，該圖段的拓撲類型為孤立型;如果圖段存在父圖段或子圖段，且數(shù)目均小于2，則稱該圖段的拓撲類型為分支型，否則為交點型。

基于圖段拓撲關(guān)系分析的譜線刪除算法如下:

a)沿垂直方向掃描，對圖像進行游程編碼，建立游程鄰接圖。

b)在游程鄰接圖的基礎(chǔ)上，用連通游程生長算法實現(xiàn)游程聚合。這是一個深度優(yōu)先的過程，建立圖段并生成圖段鄰接圖，記錄每一個圖段的拓撲類型。

圖段鄰接圖體現(xiàn)了圖段的拓撲關(guān)系。圖4為X形圖像的圖段游程鄰接圖表示，其中V1、V2、V4、V5為分支型圖段，V3為交點型圖段。

c)當圖段同時符合以下四個條件時，判別為譜線圖段，從圖像中刪除圖段的像素數(shù)據(jù)。 

條件1 線寬約束。圖段平均游程厚度小于一定閾值(2倍譜線線寬)。

條件2 形態(tài)約束。圖段包圍框的厚度小于一定閾值(2.5倍譜線線寬)。

條件3 位置約束。圖段包圍框的水平中心線與譜線位置之差小于一定閾值(1倍譜線線寬)。

條件4 拓撲類型。約束圖段類型不能是定義7中的交點型。

圖5是采用本文方法的實測圖例。其中，(a)為原始樂譜圖像;(b)是采用傳統(tǒng)的圖段分析方法，未考慮拓撲類型約束的譜線刪除結(jié)果;(c)為本文方法加入圖段拓撲類型約束的譜線刪除結(jié)果。可以看到，圖5(b)中矩形框標記出的過刪現(xiàn)象在(c)中已不再出現(xiàn)。

2 符干分割

符干為連接符頭、符梁/尾的垂線，是音符結(jié)構(gòu)的基本骨架。常見的符干檢測方法主要有骨架化、垂直游程分析、水平游程分析和數(shù)學形態(tài)學方法[5]。骨架化方法對噪聲和粘連非常敏感，交點處會形成畸變，因此，當遇到符干連接較多的符頭、符梁時檢測效果欠佳。垂直游程分析方法的原理是選取具有一定長度的黑像素垂直游程作為符干，其優(yōu)點是不受符頭、符梁的相交和粘連干擾，缺點是在處理聲音符時會將符頭簇誤識為符干。水平游程分析方法則是對圖像進行水平游程編碼，刪除長度大于一定閾值的黑像素水平游程，然后進行連通域標志，選取高而窄的連通域作為符干。該方法優(yōu)點是誤識率低，但是符干分割不完整，會丟失與符梁、符頭相交和粘連的那部分線段。數(shù)學形態(tài)學方法通過構(gòu)造垂線結(jié)構(gòu)元素對圖像進行腐蝕操作，從而獲得符干數(shù)據(jù)，其效果與垂直游程分析方法完全相同，并且操作更耗時。

著眼于兩種游程編碼在信息表達上的互補性，本文提出一種垂直、水平游程編碼結(jié)合使用的符干分割算法，能夠有效解決上述方法的局限性。算法描述步驟如下:a)沿垂直方向掃描，對樂譜圖像(如無特殊說明，此后算法中的初始圖像均指譜線去除后的圖像)進行垂直游程編碼，若黑像素游程中長度超過一定閾值(2倍譜線間距)，則標記該游程為候選符干游程;b)沿水平方向掃描，對圖像進行水平游程編碼，檢索出候選符干游程中像素點所在的水平游程，由此獲得像素點左右邊界的輪廓點;c)若候選符干游程輪廓點滿足以下條件，則確定候選符干游程為符干。

條件5 線寬約束。點兩側(cè)的輪廓點之間的距離小于一定閾值(2倍譜線線寬)。

條件6 對稱性約束。輪廓點對相對于候選符干游程的中心線左右對稱。

條件7 一致性約束。同時滿足條件5、6的輪廓點必須連續(xù)且達到一定長度(1.5倍譜線線寬)。

這樣的過程遵循人識圖過程中逐步求精的原則:步驟a)關(guān)注的是符干沿垂直方向的連續(xù)性，相當于人從全局角度粗看垂線的過程，可保證符干抽取結(jié)果的完整性;b)、c)關(guān)注的是符干的左右邊界特征，等同于人從局部角度的細看輪廓的過程，通過分析輪廓細節(jié)確保符干抽取結(jié)果的正確性。

分別采用垂直游程分析方法、水平游程分析方法和本文提出的兩種游程編碼相結(jié)合的方法對譜例進行測試，符干分割結(jié)果如圖6所示。通過對比可看到，圖6(a)中矩形框標記處出現(xiàn)了符頭簇誤識為符干的情況;(b)中的符干丟失了與符頭/符梁重疊的那部分線段，完整性遭到破壞;而(c)中本文方法獲得的符干在完整性和準確性上都得到了保證。

3 符頭分割

符頭用于記錄音符的音高，分為實心與空心符頭兩類。其中空心符頭構(gòu)成的音符結(jié)構(gòu)相對簡單(無符干、符梁)，譜線刪除后自然分離，因此，本章僅討論實心符頭的分割。

判別符頭的策略可分為兩類:a)模板匹配，即根據(jù)符頭的直觀形象設(shè)計模板進行匹配;b)特征檢測，即先分割出潛在的符頭連通域，再根據(jù)連通特征進行篩選[6]。考慮到模板匹配的處理效率瓶頸，本文采用b)類方法。特征檢測方法面臨的主要困難是粘連符頭的切分問題。樂譜圖像中符頭的粘連現(xiàn)象非常普遍，表現(xiàn)形式有上下相鄰粘連(與聲音符中的符頭簇)、左右相鄰粘連和符頭與其他對象(如變音記號)粘連三類，如圖7所示。

筆者認為，合理引入音符特定先驗知識是解決符頭粘連問題的一個有效途徑。音符特定先驗知識指的是音符的記寫規(guī)范(即記譜法)。記譜法中規(guī)定:符頭的尺寸和縱向位置由譜線間距和譜線位置決定;實心符頭不能單獨存在，必須與符干組合，構(gòu)成具有音樂語義的音符對象。可見，譜線、符干信息能夠為粘連符頭提供切分依據(jù)。由于此前已經(jīng)完成了譜線檢測和符干分割工作，可以充分利用已有的結(jié)果完成符頭切分。算法描述如下:

a)沿水平方向掃描，對圖像進行水平游程編碼。刪除長度小于一定閾值(3倍譜線間距)的水平黑像素游程，目的是去除連接符頭與符梁的符干部分，實現(xiàn)符頭與符梁的分離。

b)對圖像進行連通域標志。對于每一個連通域，若寬度大于一定閾值(3倍譜線間距)，且上下任何一條邊緣線接近直線，則刪除該連通域。該步驟的目的是去除具有明顯符梁特征的連通域，避免符梁經(jīng)過下一步的切分后誤識為符頭。

c)以符干為切分線，切分所有連通域，執(zhí)行后橫向粘連的符頭得以分離。

d)以譜線或譜線間線為切分線切分高度大于一定閾值(2倍譜線間距)的連通域，執(zhí)行后縱向粘連的符頭得以分離。

e)通過長、高和面積三個指標檢測切分后的連通域是否具備符頭特征(符頭連通域長約為1.5倍譜線間距、高為1倍譜線間距、像素面積與連通域包圍框面積比約為0.8)。

上述算法可以歸結(jié)為:符頭/符梁分離→刪除符梁→沿符干切分→沿譜線切分→連通域特征檢測。依照此算法可以準確地分割出圖像中的符頭，同時對于符頭三類粘連情況可獲得較理想的分割結(jié)果。

4 符梁分割

符梁是以拍子為單位，分音群連寫的橫線，圖形上表現(xiàn)為具有一定厚度、相互平行的水平或小角度傾斜的直線。現(xiàn)有符梁的判別方法通常采用圖紙識別中的直線檢測算法，如骨架化、基于行鄰圖的直線檢測和卡爾曼濾波器方法等[6]。運用此類方法時，符梁會因與符干相交而被分為多段，搜索和拼接操作需大量的判斷來完成。另外，它們還有一個共同局限，即無法處理多符梁間出現(xiàn)粘連的情況，如圖8所示。

對于符梁相交、粘連問題，筆者的觀點是:不刻意在技術(shù)上尋求相交、粘連直線的越過交點和切分算法，以獲得符梁的直線參數(shù)，而是整體上將可能粘連在一起的多個符梁當做一個合法的符梁。事實上，樂譜中符梁的語義功能僅取決于符梁的個數(shù)，與其長度、方向和位置無關(guān)。也就是說，如果能夠直接獲得符干所依附的符梁個數(shù)，精確計算每個符梁的直線參數(shù)是沒有必要的。基于上述觀點，本文以塊狀圖形為目標提取符梁基元，其過程與實心符頭類似，采用先分割、后特征檢測的方法。算法步驟如下:

a)同分割符頭時的步驟a)，實現(xiàn)符頭與符梁的分離。

b)通過厚度、長度、邊緣線的直線度三個指標檢測圖像中的連通域是否具備符梁特征(連通域厚度不小于2倍譜線厚度、長度不小于譜線間距、符梁上下邊緣線中至少一條接近直線)。

符梁作為塊狀體分割出來后，接下來需要計算符梁的個數(shù)。符梁個數(shù)可通過符干所在的塊狀體厚度除以單個符梁的厚度來計算。由于樂譜不同出版商采用的符梁厚度標準不盡相同，單符梁厚度不能使用固定閾值。為此，本文給出一種單符梁厚度自動閾值技術(shù)，該技術(shù)通過統(tǒng)計垂直游程長度頻數(shù)來實現(xiàn)，可自適應不同出版商的樂譜版式。計算步驟如下:a)對分割出來的符梁塊狀體圖像進行垂直方向的游程編碼;b)統(tǒng)計游程編碼中游程隨長度變化的頻數(shù)，生成頻數(shù)直方圖，選取直方圖中最大峰值對應的游程長度作為單符梁厚度。

考慮到符梁上下粘連的情況，頻數(shù)直方圖中可能會出現(xiàn)多個峰值，此時選取最左邊峰值對應的游程長度(較小值)作為單符梁厚度。

5 文字、線條符號提取

5.1 文字提取

樂譜中的文字用于樂曲的文字描述或輔助說明。它們的分布和形態(tài)具有以下特征:a)出現(xiàn)在譜線區(qū)域間隙的空白處，不與音符發(fā)生交疊;b)總是呈水平排列，無方向變化;c)除樂譜頂部的標題文字較大，其他文字尺寸基本保持一致，無明顯字號變化。針對上述特征，本文采用區(qū)域分割和相鄰檢測法抽取樂譜中的文字。其算法步驟如下:

a)根據(jù)譜線位置對樂譜進行區(qū)域劃分，如圖9所示。將五條譜線邊界包圍而成的矩形區(qū)域記為譜線組區(qū);遠離譜線組和譜線組兩側(cè)的區(qū)域，記為標題區(qū);靠近譜線組和譜線組間的區(qū)域記為文字區(qū)。

b)對圖像進行連通域標志。標題區(qū)內(nèi)的連通域直接放入文字集合;包圍框與譜線組區(qū)有交疊的連通域視為非文字，不作處理;對于包圍框位于文字區(qū)內(nèi)的連通域，執(zhí)行c)。

c)篩選包圍框具有文字尺寸特征的連通域(長度在0.5~5倍譜線間距，高度在1~3倍譜線間距)，加入字符集合。

d)將文字中瑣碎的連通域合并到字符中，解決“i”問題。對于矮小連通域，若其包圍框與文字集合中某包圍框有重疊，或兩個包圍框之間的水平或垂直間隙小于0.3倍譜線間距，則合并包圍框。

e)文字串歸并。如果文字集合中兩個相鄰包圍框垂直方向有重疊，且水平間隙小于0.3倍譜線間距，則合并包圍框。

5.2 線條符號提取

樂譜中線條符號包括延音線、漸強漸弱記號和省略記號線。它們具有非常明顯的幾何特征:角度接近水平、線寬小且尺寸較長。因此，當文字對象刪除后，可直接利用圖像中連通域的幾何特征來進行判別(包圍框?qū)挾炔恍∮?倍譜線間距，包圍框內(nèi)垂直游程的平均長度小于0.5倍譜線間距，包圍框長度與高度的比值大于2)。

6 實驗結(jié)果及討論

以本文研究內(nèi)容開發(fā)的樂譜圖像分割工具已應用于樂譜智能輸入與識別系統(tǒng)——IOMRS。使用該系統(tǒng)對大量譜例進行了測試，測試譜例覆蓋不同類型的多聲部的鋼琴譜和總譜，最終獲得了滿意的結(jié)果。表1為IOMRS在P4 2.4GHz PC，Windows XP上的部分測試結(jié)果，包括8個多聲部譜例詳細數(shù)據(jù)。

測試圖像平均尺寸為1 200×1 600。表中數(shù)量均以分割后連通域的包圍框為單位統(tǒng)計，其中文字數(shù)量為字串包圍框的數(shù)目;線條符號因數(shù)量少，統(tǒng)計略。實測結(jié)果顯示，平均每幅圖像漏分割率小于0.6%，處理時間小于0.5 s，表明本文提出的各類樂符分割方法是準確有效的，執(zhí)行效率也達到實用要求。

需要指出的是，表1顯示每幅圖像符干分割出來的數(shù)量超出實際符干數(shù)15%~30%。其原因在于本文方法會把樂譜小節(jié)線和部分樂符(變音記號)中的垂線也當做符干分離出來，如“#”“b”等中的垂線段。這些偽符干可在后面的音符結(jié)構(gòu)分析階段予以排除(無符頭依附的符干是偽符干)。另外，誤識的偽符干均遠離符頭，它們的存在不影響本文中的符頭切分算法。

圖10是IOMRS分割表1中譜例4的結(jié)果(局部)。其中，(a)為多聲部鋼琴譜樣例，該譜例樂符種類較復雜，排列密集且多粘連;(b)為譜線刪除后的圖像，樂符與譜線得以分離，無明顯譜線過刪現(xiàn)象;(c)~(e)分別為音符基元符干、符頭和符梁分割后的結(jié)果，可為后一步的音符結(jié)構(gòu)分析(音符識別)提供數(shù)據(jù)準備;(f)為文字、線條圖形提取結(jié)果;(g)是從原譜例中刪除譜線、符干、符頭、符梁、文字及線條圖形后得到的結(jié)果，此時圖中的符號屬于簡單模式對象，可在后一步處理中用OCR方法識別之。