基于改進K均值聚類算法的摩斯報抄報研究*

梁 充

（杭州電子科技大學，浙江 杭州 310018）

0 引言

摩斯（Morse）報是短波無線通信的主要應用之一，也是通信的重要手段之一。摩斯報的優點是編碼方式簡單、抗噪性強且易于實現。盡管隨著通信技術的飛速發展摩斯報的應用受到了極大影響，但不管是某些民用通信領域還是軍事通信領域仍然應用著摩斯報，如無線電廣播、航空公告、海上通信以及戰備演習等[1]。

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

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

1 信號預處理

1.1 時頻分析

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

圖1 摩斯信號時頻圖

由圖1可見，摩斯信號的時頻特征為矩形亮條。矩形亮條在時間軸上的長度就是碼的長度，其中亮條按照1:3的長度比例對應摩斯碼中的點與劃，每段亮條之間的間隔也根據1:3:7的長度比例分別對應摩斯碼中的碼間隔、字符間隔以及字間隔。圖1中的摩斯碼為“......-...-..--- -----.-.....”，對應的報文為“HELLO MORSE”。

1.2 灰度變換

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

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

1.3 閾值分割

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

2 摩斯碼譯碼

2.1 參數提取

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

圖2 五類碼的分布情況

2.2 改進聚類算法

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

（1）設定K個聚類中心點；

（2）將這K個點隨機放置，完成初始化；

（3）分別計算原始數據集中每個樣本點到每個聚類中心點的歐氏距離，將樣本點歸類至距離最近的聚類中心點所在的類，且在一輪運算后，原始數據集被分為K類；

（4）根據K個類中所包含的樣本點，重新計算每一類中樣本點的均值中心，作為新的聚類中心點；

（5）再次更新樣本點的歸類結果，根據新的聚類中心點重新計算樣本點距離并劃分出K個類；

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

以上就是K均值算法的全過程，通過迭代來更新聚類中心點與其樣本區域，直至無法更新[11]。初始化時，聚類中心的位置非常重要。在K均值算法中，因為不同的初始位置可能會導致不同的結果，所以一般要求聚類中心盡量分散開。但是，對于分析聚類摩斯碼的碼長這一特定情況，本文在初始化時對聚類中心的位置做了理論運算。根據摩斯碼的點、劃、碼間隔、字符間隔、字間隔碼長比例為1:3:1:3:7，可得在理想情況下五類碼的碼長歸一化分布應為：點（1，0.143）、劃（1，0.429）、碼間隔（0，0.143）、字符間隔（0，0.429）、字間隔（0，1）。以此對應初始化時5個聚類中心的位置，可以大大降低聚類算法的迭代次數，并且避免隨機到不同初始化聚類中心而導致聚類結果不同的情況。由此，本文提出了一種基于改進K均值聚類算法的摩斯碼譯碼方法。

（1）將摩斯碼二值圖所轉化的矩陣中0、1的時間長度進行歸一化；

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

（3）用K均值聚類算法進行迭代；

（4）將5個聚類下的5類樣本點分別對應點、劃、碼間隔、字符間隔以及字間隔，得到摩斯碼并查表譯碼。

3 仿真實驗與結果分析

仿真環境為高斯白噪聲AWGN信道，實驗步驟如下。

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

（2）將摩斯信號時頻圖進行灰度映射，使其變為灰度圖，如圖3所示。后對其進行灰度指數變換處理，得到圖4。通過對比圖3、圖4，結合圖5，可以明顯看出，經過灰度指數變換后，灰度圖的對比度增大明顯，灰度分布更加分散，降低了閾值分割的難度。下面通過最大類間方差法獲得自適應分割閾值，再以此閾值對圖像作分割處理得到圖6。

圖3 灰度映射后的摩斯信號時頻圖

圖4 灰度指數變換后的時頻圖

圖5 參數為0.06時的圖像灰度分布

圖6 閾值分割后的圖像

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

圖7 歸一化后的0、1參數分布

分別以K均值聚類算法和本文中改進的K均值聚類算法處理分布圖，過程中計時，處理后對照摩斯碼表翻譯報文，結果如圖8和圖9所示。

圖8 聚類結果

圖9 輸出識別結果與對應碼文

改變信噪比，對比在不同信噪比下算法的性能與準確率。對于一段碼文長度為100、內容信息隨機的摩斯碼，在其他相同環境下添加信噪比范圍為-10～5 dB的高斯白噪聲，用本文算法進行抄報識別。為了更加準確地統計算法的準確率，以點劃與間隔的結果進行對比，免去將摩斯碼譯碼過程中可能造成的誤差，實驗結果如圖10所示。從圖10可以看出，當信噪比大于-5 dB時，算法的準確率較高，能達到95%以上，而在信噪比為-9 dB時仍能達到85%的準確率。

生成多個不同長度的隨機摩斯信號，在0 dB的高斯白噪聲環境中重復步驟1～步驟4，比較兩種算法所需要的時間，實驗結果如圖11所示。由于兩種算法耗時都非常短，為了便于比較，將時間參數乘以10 000。從圖11可以看出，隨著長度的增加，兩種算法的耗時都有所增加，但是改進算法不僅耗時更短，而且增長率更高。

圖10 不同信噪比下的算法準確率情況

圖11 兩種算法的耗時對比

4 結語

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