基于改進(jìn)K均值聚類算法的摩斯報(bào)抄報(bào)研究*

梁 充

（杭州電子科技大學(xué)，浙江 杭州 310018）

0 引言

摩斯（Morse）報(bào)是短波無(wú)線通信的主要應(yīng)用之一，也是通信的重要手段之一。摩斯報(bào)的優(yōu)點(diǎn)是編碼方式簡(jiǎn)單、抗噪性強(qiáng)且易于實(shí)現(xiàn)。盡管隨著通信技術(shù)的飛速發(fā)展摩斯報(bào)的應(yīng)用受到了極大影響，但不管是某些民用通信領(lǐng)域還是軍事通信領(lǐng)域仍然應(yīng)用著摩斯報(bào)，如無(wú)線電廣播、航空公告、海上通信以及戰(zhàn)備演習(xí)等[1]。

摩斯報(bào)發(fā)送的是摩斯碼。摩斯碼由2種碼和3種間隔組成。2種碼分別為點(diǎn)（dot）與劃（dash）；3種間隔分別為碼間隔、字符間隔以及字間隔.點(diǎn)的時(shí)長(zhǎng)為基本單位，劃的時(shí)長(zhǎng)為點(diǎn)的3倍，碼間隔與點(diǎn)相同時(shí)長(zhǎng)，碼間隔、字符間隔以及字間隔的時(shí)長(zhǎng)比例為1:3:7[2-5]。點(diǎn)與劃的不同排列組合代表了不同的字符，而每個(gè)字符中點(diǎn)與劃的間隔為碼間隔，字符之間的間隔為字符間隔，字符組合為單詞，單詞之間的間隔為字間隔。

然而，在實(shí)際發(fā)報(bào)時(shí)存在大量人工發(fā)報(bào)和人工值守抄報(bào)的情況，使得人工摩斯碼的參數(shù)并不能完全精確為1:3:1:3:7，只能相對(duì)接近碼文標(biāo)準(zhǔn)，且穩(wěn)定性較差。對(duì)于不同的發(fā)報(bào)人，點(diǎn)的時(shí)長(zhǎng)也不盡相同，導(dǎo)致譯碼難度大幅上升。在人工抄報(bào)方面，由于人的反應(yīng)能力有限，隨著時(shí)間的持續(xù)以及報(bào)文數(shù)量、信息量的增加，報(bào)務(wù)員需要對(duì)接收到的摩斯碼進(jìn)行高效快速的抄報(bào)，往往導(dǎo)致正確率大大下降。此外，長(zhǎng)時(shí)間、強(qiáng)噪聲環(huán)境下的監(jiān)聽抄報(bào)對(duì)報(bào)務(wù)員也會(huì)產(chǎn)生身體健康影響[6-8]。近年來(lái)，一些文獻(xiàn)使用了機(jī)器學(xué)習(xí)中的聚類方法進(jìn)行對(duì)摩斯碼的自動(dòng)抄報(bào)，如K均值聚類算法（K-means）、模糊C均值聚類算法（Fuzzy C-Means，F(xiàn)CM）等。盡管在信噪比較低的情況下它也得到了不錯(cuò)的效果，但耗時(shí)較長(zhǎng)。受此啟發(fā)，本文基于K均值聚類算法的原理，根據(jù)摩斯碼的特性改進(jìn)算法，并將其應(yīng)用于摩斯報(bào)的自動(dòng)抄報(bào)。實(shí)驗(yàn)表明，在相同環(huán)境下，該改進(jìn)算法的抄報(bào)效率同比于原算法的抄報(bào)效率有了較大提升，且能保持原算法的高抄報(bào)準(zhǔn)確率。

1 信號(hào)預(yù)處理

1.1 時(shí)頻分析

摩斯信號(hào)在時(shí)域與頻域中均有重要的特性，因此目前常用時(shí)頻聯(lián)合域分析（Joint Time-Frequency Analysis），即時(shí)頻分析作為處理摩斯信號(hào)的方法。時(shí)頻分析方法能夠提供摩斯信號(hào)在不同時(shí)間與頻率下的能量密度信息，有利于下文針對(duì)摩斯信號(hào)進(jìn)行的降噪處理。短時(shí)傅里葉變換（Short Time Fourier Transform，STFT）是時(shí)頻分析中較為常用的一種方法[9]。本文利用式（1）和式（2）對(duì)摩斯信號(hào)進(jìn)行短時(shí)傅里葉變換得到時(shí)頻矩陣Pn(ω)，式中x(m)為采集到的連續(xù)摩斯信號(hào)，n為時(shí)間，ω為頻率。將其進(jìn)行灰度映射可得到時(shí)頻圖，如圖1所示。

圖1 摩斯信號(hào)時(shí)頻圖

由圖1可見，摩斯信號(hào)的時(shí)頻特征為矩形亮條。矩形亮條在時(shí)間軸上的長(zhǎng)度就是碼的長(zhǎng)度，其中亮條按照1:3的長(zhǎng)度比例對(duì)應(yīng)摩斯碼中的點(diǎn)與劃，每段亮條之間的間隔也根據(jù)1:3:7的長(zhǎng)度比例分別對(duì)應(yīng)摩斯碼中的碼間隔、字符間隔以及字間隔。圖1中的摩斯碼為“......-...-..--- -----.-.....”，對(duì)應(yīng)的報(bào)文為“HELLO MORSE”。

1.2 灰度變換

在實(shí)際情況下，摩斯信號(hào)中會(huì)夾雜著大量噪聲。仿真下的高斯白噪聲反映在時(shí)頻灰度圖中表現(xiàn)為大小、形狀、灰度均各異的亮斑，不利于提取有用信號(hào)。對(duì)此，本文采用灰度指數(shù)變換的方法將摩斯信號(hào)時(shí)頻灰度圖中的高灰度級(jí)（即有用信號(hào)部分）進(jìn)行擴(kuò)展，同時(shí)將低灰度級(jí)（即噪聲信號(hào)部分）進(jìn)行壓縮，從而更好地分離有用信號(hào)與噪聲信號(hào)，計(jì)算公式為：

式中，f(x,y)為原圖像的灰度分布，a、b、c用于控制灰度值擴(kuò)展與壓縮的范圍與程度。

1.3 閾值分割

在處理摩斯信號(hào)時(shí)頻圖到分析時(shí)頻圖并譯碼的過程中，圖像分割是關(guān)鍵步驟。常用的圖像分割方法有許多種，如種子填充、邊緣分割、區(qū)域分割以及閾值分割等。對(duì)于摩斯信號(hào)時(shí)頻圖，信號(hào)與噪聲混雜在一起。本文采用最大類間方差法得到自適應(yīng)分割閾值，并對(duì)圖像進(jìn)行閾值分割，將信號(hào)部分與背景噪聲分開得到信號(hào)的二值圖。

2 摩斯碼譯碼

2.1 參數(shù)提取

已知點(diǎn)、劃、碼間隔、字符間隔、字間隔的長(zhǎng)度比例為1:3:1:3:7，通過提取分析矩形亮條以及間隔在時(shí)間軸上的相對(duì)長(zhǎng)度，即可判斷某個(gè)矩形亮條是點(diǎn)還是劃、間隔是什么類型的間隔，再以字符間隔或字間隔將矩形亮條正確分組，每組即為一個(gè)字符，然后對(duì)照摩斯電碼表進(jìn)行譯碼。參數(shù)提取與歸一化的目的就是將摩斯碼的二值圖信息轉(zhuǎn)化為碼和間隔的相對(duì)長(zhǎng)度信息。將二值圖用由0、1組成的矩陣表示，計(jì)算得到每一段0與1的長(zhǎng)度，再將所得的所有長(zhǎng)度分別除以其中的最大值，通過歸一化得到它們的相對(duì)長(zhǎng)度，得到0、1的相對(duì)長(zhǎng)度分布圖，如圖2所示。由圖2可以發(fā)現(xiàn)，五類碼有其各自的聚集特性。為了區(qū)分它們，本文采用聚類算法。聚類算法是機(jī)器學(xué)習(xí)中的一種非監(jiān)督學(xué)習(xí)算法，特點(diǎn)就是沒有任何的先驗(yàn)假設(shè)，在處理數(shù)值型數(shù)據(jù)集時(shí)具有很好的表現(xiàn)，且非常適用于處理像摩斯碼長(zhǎng)度參數(shù)這樣能夠被明顯區(qū)分為不同區(qū)域且辨識(shí)度較高的數(shù)據(jù)集。

圖2 五類碼的分布情況

2.2 改進(jìn)聚類算法

K均值聚類（K-means Clustering Algorithm）是一種較為常見的分類式聚類算法，用于將原始數(shù)據(jù)集中的樣本分類到多個(gè)聚類中心[10]。K均值算法由以下過程迭代式地進(jìn)行計(jì)算：

（1）設(shè)定K個(gè)聚類中心點(diǎn)；

（2）將這K個(gè)點(diǎn)隨機(jī)放置，完成初始化；

（3）分別計(jì)算原始數(shù)據(jù)集中每個(gè)樣本點(diǎn)到每個(gè)聚類中心點(diǎn)的歐氏距離，將樣本點(diǎn)歸類至距離最近的聚類中心點(diǎn)所在的類，且在一輪運(yùn)算后，原始數(shù)據(jù)集被分為K類；

（4）根據(jù)K個(gè)類中所包含的樣本點(diǎn)，重新計(jì)算每一類中樣本點(diǎn)的均值中心，作為新的聚類中心點(diǎn)；

（5）再次更新樣本點(diǎn)的歸類結(jié)果，根據(jù)新的聚類中心點(diǎn)重新計(jì)算樣本點(diǎn)距離并劃分出K個(gè)類；

（6）重復(fù)步驟4和步驟5，直至所有樣本點(diǎn)所屬的聚類中心不再發(fā)生變化或滿足一定的迭代次數(shù)。

以上就是K均值算法的全過程，通過迭代來(lái)更新聚類中心點(diǎn)與其樣本區(qū)域，直至無(wú)法更新[11]。初始化時(shí)，聚類中心的位置非常重要。在K均值算法中，因?yàn)椴煌某跏嘉恢每赡軙?huì)導(dǎo)致不同的結(jié)果，所以一般要求聚類中心盡量分散開。但是，對(duì)于分析聚類摩斯碼的碼長(zhǎng)這一特定情況，本文在初始化時(shí)對(duì)聚類中心的位置做了理論運(yùn)算。根據(jù)摩斯碼的點(diǎn)、劃、碼間隔、字符間隔、字間隔碼長(zhǎng)比例為1:3:1:3:7，可得在理想情況下五類碼的碼長(zhǎng)歸一化分布應(yīng)為：點(diǎn)（1，0.143）、劃（1，0.429）、碼間隔（0，0.143）、字符間隔（0，0.429）、字間隔（0，1）。以此對(duì)應(yīng)初始化時(shí)5個(gè)聚類中心的位置，可以大大降低聚類算法的迭代次數(shù)，并且避免隨機(jī)到不同初始化聚類中心而導(dǎo)致聚類結(jié)果不同的情況。由此，本文提出了一種基于改進(jìn)K均值聚類算法的摩斯碼譯碼方法。

（1）將摩斯碼二值圖所轉(zhuǎn)化的矩陣中0、1的時(shí)間長(zhǎng)度進(jìn)行歸一化；

（2）設(shè)K為5，將5個(gè)聚類中心初始化為（1，0.143）、（1，0.429）、（0，0.143）、（0，0.429）、（0，1）；

（3）用K均值聚類算法進(jìn)行迭代；

（4）將5個(gè)聚類下的5類樣本點(diǎn)分別對(duì)應(yīng)點(diǎn)、劃、碼間隔、字符間隔以及字間隔，得到摩斯碼并查表譯碼。

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

仿真環(huán)境為高斯白噪聲AWGN信道，實(shí)驗(yàn)步驟如下。

（1）將載有“HELLO MORSE”信息的摩斯信號(hào)音頻文件導(dǎo)入仿真軟件MATLAB R2017b，添加0 dB的高斯白噪聲，以短時(shí)傅里葉變換STFT作出時(shí)頻圖。

（2）將摩斯信號(hào)時(shí)頻圖進(jìn)行灰度映射，使其變?yōu)榛叶葓D，如圖3所示。后對(duì)其進(jìn)行灰度指數(shù)變換處理，得到圖4。通過對(duì)比圖3、圖4，結(jié)合圖5，可以明顯看出，經(jīng)過灰度指數(shù)變換后，灰度圖的對(duì)比度增大明顯，灰度分布更加分散，降低了閾值分割的難度。下面通過最大類間方差法獲得自適應(yīng)分割閾值，再以此閾值對(duì)圖像作分割處理得到圖6。

圖3 灰度映射后的摩斯信號(hào)時(shí)頻圖

圖4 灰度指數(shù)變換后的時(shí)頻圖

圖5 參數(shù)為0.06時(shí)的圖像灰度分布

圖6 閾值分割后的圖像

將分割后的二值圖作參數(shù)提取并歸一化作出分布圖，如圖7所示。閾值分割有時(shí)并不能完美地將噪聲與信號(hào)分離，在分割后得到的圖像中仍然會(huì)存在一些毛刺。對(duì)于二值圖的參數(shù)矩陣中所有包含信號(hào)的行，只需要提取其中的一行參數(shù)，即可進(jìn)行點(diǎn)、劃以及間隔的識(shí)別。因此，本文在參數(shù)提取時(shí)，只要求挑選與其他行相比相似度最高的行，從而避免提取到帶有毛刺的部分。

圖7 歸一化后的0、1參數(shù)分布

分別以K均值聚類算法和本文中改進(jìn)的K均值聚類算法處理分布圖，過程中計(jì)時(shí)，處理后對(duì)照摩斯碼表翻譯報(bào)文，結(jié)果如圖8和圖9所示。

圖8 聚類結(jié)果

圖9 輸出識(shí)別結(jié)果與對(duì)應(yīng)碼文

改變信噪比，對(duì)比在不同信噪比下算法的性能與準(zhǔn)確率。對(duì)于一段碼文長(zhǎng)度為100、內(nèi)容信息隨機(jī)的摩斯碼，在其他相同環(huán)境下添加信噪比范圍為-10～5 dB的高斯白噪聲，用本文算法進(jìn)行抄報(bào)識(shí)別。為了更加準(zhǔn)確地統(tǒng)計(jì)算法的準(zhǔn)確率，以點(diǎn)劃與間隔的結(jié)果進(jìn)行對(duì)比，免去將摩斯碼譯碼過程中可能造成的誤差，實(shí)驗(yàn)結(jié)果如圖10所示。從圖10可以看出，當(dāng)信噪比大于-5 dB時(shí)，算法的準(zhǔn)確率較高，能達(dá)到95%以上，而在信噪比為-9 dB時(shí)仍能達(dá)到85%的準(zhǔn)確率。

生成多個(gè)不同長(zhǎng)度的隨機(jī)摩斯信號(hào)，在0 dB的高斯白噪聲環(huán)境中重復(fù)步驟1～步驟4，比較兩種算法所需要的時(shí)間，實(shí)驗(yàn)結(jié)果如圖11所示。由于兩種算法耗時(shí)都非常短，為了便于比較，將時(shí)間參數(shù)乘以10 000。從圖11可以看出，隨著長(zhǎng)度的增加，兩種算法的耗時(shí)都有所增加，但是改進(jìn)算法不僅耗時(shí)更短，而且增長(zhǎng)率更高。

圖10 不同信噪比下的算法準(zhǔn)確率情況

圖11 兩種算法的耗時(shí)對(duì)比

4 結(jié)語(yǔ)

根據(jù)現(xiàn)有的摩斯碼抄報(bào)方法，結(jié)合摩斯碼本身的一些特性，本文提出了一種基于改進(jìn)K均值聚類算法的摩斯碼抄報(bào)方法，更加適用于摩斯碼的抄報(bào)。該方法先采用時(shí)頻分析將摩斯信號(hào)的分析轉(zhuǎn)化為時(shí)頻圖像的分析，后經(jīng)過灰度映射、灰度指數(shù)變換以及閾值分割等方法進(jìn)行去噪處理。對(duì)于去噪效果不甚完美的部分，在參數(shù)提取中將其舍去，從而保證得到的參數(shù)最為準(zhǔn)確。參數(shù)提取后進(jìn)行歸一化，作出分布圖，并對(duì)其采用改進(jìn)的K均值聚類方法識(shí)別標(biāo)記出摩斯碼中的3種碼和3種間隔，后對(duì)照摩斯碼表最終得到抄報(bào)結(jié)果。本文方法簡(jiǎn)單，且采用非監(jiān)督學(xué)習(xí)算法，無(wú)需先驗(yàn)信息。在仿真實(shí)驗(yàn)中，通過統(tǒng)計(jì)不同信噪比下的算法準(zhǔn)確率和對(duì)兩種算法的耗時(shí)統(tǒng)計(jì)，驗(yàn)證了本文方法較高的準(zhǔn)確性和高效性。如何在摩斯碼譯碼過程中再一步提高效率，是下一步的研究?jī)?nèi)容。