面向OSD 語言檢測對照表的匹配定位算法*

滕 斌 ，林珊 玲 ，林志賢 ，郭太良

(1.福州大學 物理與信息工程學院，福建 福州 350116；2.中國福建光電信息科學與技術創新實驗室，福建 福州 350116；3.福州大學 先進制造學院，福建 泉州 362200)

0 引言

OSD(On Screen Display)是人機交互的通道[1]。在生產中為避免OSD 菜單出現文字錯誤，利用人工根據標準表格進行OSD 菜單的文字檢測工作，然而人工檢測存在成本高、誤檢率高等問題，故實現檢測的自動化顯得至關重要。

自動化檢測主要包括兩大部分：(1)正確識別OSD 上的文字并輸出；(2)將識別結果與對照表對比確定最終檢測結果。根據OSD的實際使用需求，對照表存在行數多、單行文字少以及多次重復的特點。本文結合Excel 表的編碼方式，分析研究了BM[2](Boyer-Moore)、AC[3](Aho-Corasick)算法，提出了一種應用于OSD 自動化檢測系統的面向Excel 表的匹配定位算法。

1 OSD 語言自動化檢測系統

OSD 語言檢測系統是一個容錯率極低的系統，實際運行過程中主要通過兩方面來達到要求，一是系統通過多次檢測的方法來降低識別正確率不足帶來的影響；二是通過設計優化的對照表匹配定位算法來提高定位的準確性，進一步降低檢測系統的誤檢、漏檢情況。OSD 語言自動化檢測系統識別部分主要通過攝像頭采集OSD圖像信息，對采集的圖像結果進行二值、降噪等必要的預處理，然后利用分割算法將圖像中有效的文字部分進行分割，最后對分割好的文字經行識別操作并輸出識別結果[4]。

結合多種品牌顯示器和多層級的設置界面不難發現，OSD 菜單具有單項文字少、層級多、項目總數多以及同一單項名在不同界面多次出現等特點。常見顯示器OSD 圖像如圖1 所示。圖2 是圖1的實測識別結果，結果按行排列展開。用于確定最終檢測結果的對照表同樣也是按行展開，每行單元格對應OSD中的單項菜單的內容。圖3 即圖1 所示的OSD 界面的對照表信息，其中74 項的亮度為64 項亮度設置展開后的二級菜單的第一個菜單項，此處9 行表格就出現了1 項重復內容，因此如何在重復率高的對照表中找到識別內容的準確位置就顯得尤為重要。

圖1 OSD 圖像

圖2 識別結果

圖3 標準對照表

2 經典的模式匹配算法

2.1 模式匹配

模式匹配[5]是數據結構中字符串的一種基本運算。例如：給定某字符串T 長度為n，則存在T=T0T1T2T3…Tn-1，有一子串P 長度為m，則存在P=P0P1P2P3…Pm-1。在給定字符串T中匹配字串P，若存在TiTi+1Ti+2Ti+3…Ti+m=P0P1P2P3…Pm-1則模式匹配成功，反之失敗。

模式匹配按同時匹配子串的個數，可以分為單模式匹配和多模式匹配，其中常見的KMP[6](Knuth-Morris-Pratt)、BM 是單模式匹配算法，AC、WM[7](Wu-Manber)是多模式匹配算法，以下主要介紹BM、AC 算法。

2.2 BM 算法

BM 算法是一種非常高效的字符串搜索算法[8]，其核心是兩大規則，即壞字符規則和好后綴規則，通過這兩大規則來決定匹配過程中向右跳躍的距離[9-10]。

BM 算法的基本流程如下：給定一個字符串長度為n，子串P 長度為m，首先將字符串T 和子串P 左對齊，然后從右向左進行比較，如圖4 所示。

圖4 BM 算法匹配方法

利用壞字符規則和好后綴規則來計算字串向右移動的距離[11]，如圖5 所示，從右往左看，已匹配的cab 字符為好后綴，未配的e 字符為壞字符。

圖5 壞字符和好后綴

壞字符規則存在兩種情況：(1)如果字符x 在模式P中未出現，那么從x 開始的m 個文本顯然不可能與P匹配成功，直接全部跳過該區域即可；(2)如果x 在模式P中出現，則以該字符進行對齊。圖4 所示的匹配過程中c 字符為壞字符，且在子串P中出現，故符合壞字符規則的第二種情況，其移位效果如圖6 所示。

圖6 壞字符規則移位

好后綴規則也存在兩種情況：(1)如果在P中位置t處已匹配部分P′在P中的某位置t′也出現，且位置t′的前一個字符與位置t的前一個字符不相同，則將P 右移使t′對應t 方才所在的位置；(2)如果在P中任何位置已匹配部分P′都沒有再出現，則找到與P′的后綴P″相同的P的最長前綴x，向右移動P 使x 對應方才P″后綴所在的位置。圖5 所示的匹配過程中cab 字符為好后綴即P′，且在字串P 再沒有出現，ab 字符為P′的后綴P″相同的P的最長前綴x，所以符合好后綴規則的第二種情況，向右移動P 使ab 對于方才P″后綴ab 所在位置，其移位效果如圖7 所示。

圖7 好后綴規則移位

2.3 AC 算法

AC 自動機[12]即AC 算法。它與普通單模式字符串匹配的不同點在于同時與所有子串進行匹配[13]，其核心是狀態轉移函數和失效函數。

圖8 是一個使用多模式串he、she、hers、his 創建的自動機。初始狀態都為0，讀取第一個字符串he，0 狀態受到第一個字符h的刺激改變為1 狀態，受到e的刺激改變為2 狀態，此時第一個字符串讀取完畢，將末尾字符的2 狀態標記為output 輸出狀態。然后依此讀取下一個多模式串，其中讀取hers 時，刺激h 已經存在，不需要創建新狀態，直接到達狀態1 即可，只有在當前狀態下，受到的刺激是新刺激時，才會創建新狀態。然后依次為所有字符串創建自動機路徑[14]。圖中實線即為狀態轉移函數。

圖8 AC 算法

AC 算法的匹配過程如下：假設存在主串ushers，將其放到自動機中運行，首先，第一個字符u，0 狀態不存在u的刺激，返回自身狀態，s、h、e的刺激全部存在，狀態依次經過3、4、5的轉變，5 為output 狀態，即she 字符串匹配成功。當再下一個刺激r 出現，由于當前狀態不存在刺激r 出現失配情況，這時就需要用到失效函數。應該轉移到的狀態點為：從這個狀態節點向上直到樹根節點（狀態0）所經歷的輸入字符，與從產生失效狀態的那個狀態節點向上所經歷的輸入字符串完全相同。而且這個狀態節點是所有具備這些條件的節點中深度最大的那個節點。不存在滿足條件的狀態節點，則失效函數為0[15]。因此上述情況此時應從狀態5 轉變為狀態2 繼續執行。

3 本文算法

3.1 算法思想

針對以上分析可知，無論BM 算法還是AC 算法都是實現字符串的精準匹配，OSD 語言檢測對照表的匹配定位算法需要在無法完全匹配的情況下實現準確定位。因此本文提出了一種面向OSD 語言檢測對照表的匹配定位算法。

本文算法使用分類匹配和概率定位的方法來實現精準定位的需求。本文算法的流程圖如圖9 所示。

圖9 算法流程圖

3.1.1 分類匹配

分類匹配的存在是為了減少匹配次數。在真正執行匹配操作前先對照表內容和識別內容進行預處理，將表格內容從上至下每3 行單元格分為一組，計算3 行內容的字數之和N 作為分類的一級標簽，中間行單元格的字數M 作為分類的二級標簽；同樣地對識別的結果也進行三行一組的分配，計算3 行總字數m 和中間行字數n。至此，分類操作執行完畢。

匹配流程圖如圖10 所示。匹配過程如下：根據每組識別結果的m 和n 值在表格分類項中查找出m=M 且n=N的組，通常有多個符合條件的組，找出這些待匹配組后，每組進行逐行逐字匹配操作。每組每行匹配一次，上下行的匹配結果用于計算定位概率，中間行的匹配結果用于最終檢測結果的認定。匹配過程由上往下進行，匹配第一步是進行字數的匹配，出現字數不等情況時，直接跳過該組進行下一組的匹配。組內行之間的匹配過程是一對一跳轉的逐字匹配，出現字符不匹配就跳轉到下一字或單詞的匹配進程中。

圖10 匹配流程圖

3.1.2 概率定位

檢測的最終結果是否值得信賴，重點在于是否可以在對照表中找到識別結果的準確位置。為了提高定位的準確性，引入概率定位的方法,概率定位是本算法最為重要的方法。利用上下行匹配正確字數和上下行總字數的商來確定定位概率，取待匹配組中定位概率最大值所在組的中間行位置為最終定位位置，輸出位置值和定位概率值，即：

OSD 語言檢測系統的最終輸出即：

3.2 算法實例

以中文OSD 菜單為例，考慮如下的對照表內容：第一行起，圖像/亮度/對比度/色調/清晰度/高級設置/亮度/清晰度/色調/對比度/圖像/高級設置，共12 行，識別輸出為青晰度/色調/對比度。

不考慮漢字的轉碼過程，直接使用漢字演示算法執行過程。實際過程是漢字轉成4 字符后執行操作。首先對對照表內容和輸出內容進行分類，其中對照表內容分為3 大組以M-N的形式記錄，分別是7-2、7-3、7-3、7-3；8-2、8-2；9-3、9-4、9-2、9-2，識別輸出以m-n形式記錄，即8-2。查找m=M 且n=N，共兩組待匹配組，每組經行逐行匹配。

第一組，與對比度/色度/清晰度進行匹配，上下行成功匹配2 字共6 個字，定位概率為33.3%，中間行匹配成功結果為正確。

第二組，與清晰度/色調/對比度進行匹配，上下行成功匹配5 字共6 個字，定位概率為83.3%，中間行匹配成功結果為正確。

第二組定位概率大于第一組，選擇第二組的匹配結果，最終檢測結果輸出為：9 行83.3%色調正確。

4 測試結果與分析

為了更好地對本文算法進行效果驗證，隨機編輯了2～5 字的中文詞語或短語各25 個，合計100 個不同單項，并將這100 個單項重復出現5 次，共獲得500 項菜單內容，將500 項隨機排列生成最終的對照表。測試環境是Windows 10 64 位操作系統，使用配置為AMD R5-3500U 2.1 GHz CPU、8 GB 內存的筆記本電腦，采用C 語言編程。

預處理過程，將對照表分成了10 大組28 小組。表1所示是分組的基本情況。

表1 分組基本情況

根據對照表的內容，特意模擬了如下幾種識別情況并結合傳統匹配方法來檢驗算法效果：

第1種：OSD內容正確識別結果正確，測試結果如圖11、圖12 所示，本文算法準確定位出了所在行和檢測結果，而傳統方法只能簡單查找出對照表中有5 個匹配項。

圖11 本文算法測試結果

圖12 傳統方法測試結果

第2種：OSD 內容正確但識別結果有誤，分為3種情況：(1)上下行識別有誤；(2)中間行識別有誤；(3)三行識別均有誤。測試結果如圖13～圖16 所示，其中傳統方法的情況一結果和圖12 所示結果類似，這里不再展示。

圖13 本文算法情況1

圖14 本文算法情況2

圖15 本文算法情況3

圖16 傳統方法情況2、3

第3種：OSD 內容錯誤但識別正確，本文算法檢測效果如圖17 所示，傳統查找方法結果如圖18 所示。測試結果不難發現，即使在內容有誤或識別有誤的情況下，本文算法仍舊可以進行定位并且輸出識別和判斷結果，而傳統方法只能在OSD 和識別都無誤的情況下找出相同的項，出現任一錯誤時就無法查找匹配。

圖17 本文算法

圖18 傳統方法

根據以上3種情況的多次測試結果表明，本文方法對比傳統的查找方法可以規避在出現不完全匹配情況時無法匹配定位的問題，同時引入的概率定位方法可以高效地在多重復項中找到目標項，日常的使用則可以兼顧定位準確性和識別確定性。

5 結論

本文通過對OSD 語言檢測系統的需求分析，結合BM算法和AC 算法提出了一種面向OSD 語言檢測對照表的匹配定位算法。實驗表明，該算法通過分類匹配和概率定位提高了匹配速度，解決了無法定位的問題。結合OSD 菜單的發展和文字識別的發展現狀，算法還可以進一步改進，使其更加適應系統需求。