參考 題型範例 - 全國高級中等學校技藝競賽平台 工業類
題目：求二個簽名字元的相似度
問題描述
有一簽名字元為 BMP 的二元圖形(如圖 1)，從 BMP 圖檔截出內容的部分(如圖 2)，其中下圖 1 與下圖 2 上下方向相反，下圖中的每一個點以二元值表示之，0 表示黑及 1 表示白。我們可使用二個手寫的簽名字元的 BMP 圖形來做比對，比對時使用投影法及運算程序以求出它們的相似度。例如，求出的值為 0.52824，則二個簽名字元的相似度為 52.82%。


圖 1 簽名字元


圖 2 BMP 的二元圖形
圖 3 「工」字元

水平投影


圖 4 「工」字元水平投影


圖 5 「工」字元垂直投影

投影的原理：
今有一「工」字元(圖 3)，做水平投影，於 y 軸累積黑點點數(圖 4)；做垂直投影，於 x 軸累積黑點點數(圖 5)。

運算的程序：
求二個圖形的相似度時，在此使用投影法及相關運算程序如下：
  1. 對二個圖形的 x 軸及 y 軸分別做投影，x 軸及 y 軸各有 32 個元素。
  2. 對二個圖形的 x 軸及 y 軸的每一個元素都做投影時，即是將其具有「0」(黑)的值做累加，即為其投影值，如圖 4 及圖 5 所示。
  3. 將二個比對的圖形，其在相同座標的投影值相除可得該座標的相似度，x 軸及 y 軸均是。
  4. 對 x 軸而言，x 軸各座標的相似度值加總，再除以座標元素的數目 32，即為二個圖形 x 軸的相似度；對 y 軸亦然。
  5. 將 x 軸的相似度與 y 軸的相似度相乘，即為二個圖形的相似度。
提示：
  1. 為避免相除時分母為 0，x 軸及 y 軸的每一個元素的投影初始值都預設為 1。
  2. 在相同座標的二個投影值相除的相似度最大為 1 (100%)。 
執行程式：
例 1 ：使用二個字元比較



    

    
輸入：檔案「南 1.txt」及「南 2.txt」
執行結果：列印如圖 6。




例 2 ：使用二個字元比較



    

    

    
輸入：檔案「南 1.txt」及「南 3.txt」

    
執行結果：步驟 4，求平均相似度：垂直投影：0.842，水平投影：0.863
步驟 5，2 字元相似度：0.72676




例 3 ：使用二個字元比較



    

    

    
輸入：檔案「南 2.txt」及「南 3.txt」

    
執行結果：步驟 4，求平均相似度：垂直投影：0.729，水平投影：0.710
步驟 5，2 字元相似度：0.51764




例 4 ：使用二個字元比較



    

    
輸入：檔案「三 1.txt」及「三 2.txt」
執行結果：列印如圖 7。




例 5 ：使用二個字元比較



    

    

    
輸入：檔案「川 1.txt」及「川 2.txt」

    
執行結果：步驟 4，求平均相似度：垂直投影：0.838，水平投影：0.909
步驟 5，2 字元相似度：0.76198





圖 6  (南 1.txt)  (南 2.txt) 比對相似度的過程 



圖 7  (三 1.txt)  (三 2.txt) 比對相似度的過程