1.什么是OCR？

OCR（optical character recognition）是將圖片進(jìn)行掃描，提取其中的文字的技術(shù)。如今，不少業(yè)務(wù)領(lǐng)域都用到了OCR技術(shù)。比如某些快遞軟件支持識別包含地址信息的圖片，解析出用戶地址。

2.游戲業(yè)務(wù)引入OCR的背景

在用戶發(fā)布游戲商品時，我們希望用戶將參數(shù)填得越全越好，這樣有助于搜索、個性化推薦、統(tǒng)計數(shù)據(jù)。但是，以王者榮耀為例，目前王者榮耀有400+皮膚，將所有擁有的皮膚填寫一遍非常麻煩，所以我們希望通過用戶上傳圖片或商品封面，提取其中的參數(shù)信息，填入商品信息中，以達(dá)到補(bǔ)全參數(shù)、減少用戶操作的目的。

3.問題

目前騰訊、百度、58等公司都提供了OCR識別API，轉(zhuǎn)轉(zhuǎn)也有自研的OCR能力，對一張用戶上傳的圖片進(jìn)行OCR識別可以得到一個文本集合。

["曙李逍遙","伽羅太華","李信一念神度","虞婭云寬雀翎","公孫離析雪靈祝","椅右京楓霜盡","孫尚香音你閃耀","娜可露露前塵鏡","百里守約碎云","馬可波羅深海之息"]

結(jié)合OCR識別結(jié)果我們可以發(fā)現(xiàn)一些問題

• 圖中有10個皮膚，但是用戶只擁有5個皮膚，灰色的皮膚是未擁有的，我們不希望將用戶未擁有的皮膚也識別出來。
• 對復(fù)雜文字支持不是很好，比如把“李信一念神魔”識別為了“李信一念神度”，把“橘右京楓霜盡”識別為了“椅右京楓霜盡”，所以在進(jìn)行參數(shù)匹配時，我們希望有一定容錯性。

由此產(chǎn)生了兩個要解決的問題

• 只識別擁有的皮膚
• 匹配時有一定容錯

4.如何只識別擁有的皮膚

通過觀察用戶上傳的圖片我們可以發(fā)現(xiàn)：

• 圖片可以分為10個皮膚區(qū)域以及背景區(qū)域，我們只關(guān)注皮膚區(qū)域，所以需要先想辦法將皮膚區(qū)域與背景區(qū)域分離。
• 劃分完皮膚區(qū)域后，我們可以對10個區(qū)域依次進(jìn)行判斷，區(qū)分出這到底是一個未擁有的皮膚區(qū)域還是已擁有的皮膚區(qū)域。

4.1.劃分皮膚區(qū)域

如何將皮膚區(qū)域和背景區(qū)域分離呢？通過觀察我們能看到：

• 背景區(qū)域的顏色比較單調(diào)，大部分大都是藍(lán)色、灰色以及右側(cè)的一些白色絲帶。
• 皮膚區(qū)域色彩會豐富一些，有各種炫酷的色彩和藝術(shù)字。

所以是否能嘗試使用色彩數(shù)來區(qū)分皮膚區(qū)域和背景區(qū)域呢？

對用戶上傳圖片的色彩數(shù)量進(jìn)行統(tǒng)計，得到以下趨勢：

上圖為從橫向開始遍歷，使用Set對縱向所有像素的顏色進(jìn)行去重，得到的顏色數(shù)量變化趨勢。可以看出，五個較為明顯的凸起即對應(yīng)了圖上的5列皮膚。

上圖為從縱向開始遍歷，使用Set對橫向所有像素的顏色進(jìn)行去重，得到的顏色數(shù)量變化趨勢?？梢钥闯?，兩個較為明顯的凸起即對應(yīng)了圖上的2行皮膚。

因此，如果某個點(diǎn)附近顏色數(shù)量發(fā)生劇烈變化就可以認(rèn)為這是一個邊界點(diǎn)，相鄰兩個邊界點(diǎn)相連可以組成線段，橫向的線段和縱向的線段相連可以組成矩形。按照這個思路對圖片進(jìn)行劃分后效果如下。

這樣就初步實(shí)現(xiàn)了將皮膚區(qū)域和背景區(qū)域分離

4.2保留擁有的皮膚

對于已擁有的皮膚和未擁有的皮膚，他們的顏色數(shù)量都很豐富，繼續(xù)用顏色數(shù)量區(qū)分的效果不是很理想，那如何進(jìn)行區(qū)分呢？

• 已擁有的皮膚區(qū)域：整體比較鮮艷，所以飽和度高、亮度高的像素占比更高
• 未擁有的皮膚區(qū)域：整體比較暗淡，所以飽和度高、亮度高的像素占比低

所以，我們可以在劃分矩形后，首先對矩形的長寬比進(jìn)行初次過濾，然后提取矩形中像素的顏色，計算亮度和飽和度大于閾值的像素占比，保留占比高的矩形

 private double colorScore(BufferedImage img, Rectangle rect,
                             double brightnessThreshold, double saturationThreshold) {
       int total = 0;
       Set<Integer> set = new HashSet<>();
       for (int i = (int) rect.getX(); i < (int) (rect.getX() + rect.getWidth()); i++) {
           // 垂直方向截取中間部分，因?yàn)樯线吅拖逻呉话阌胁噬奈淖?，影響判?br>           for (int j = (int) (rect.getY() + rect.getHeight() / 4);
                j < (int) (rect.getY() + rect.getHeight() * 3 / 4); j++) {
               // 獲取RGB
               int color = img.getRGB(i, j);
               int r = (color >> 16) & 0xff;
               int g = (color >> 8) & 0xff;
               int b = color & 0xff;
               // 計算飽和度
               double max = Math.max(r, Math.max(g, b));
               double min = Math.min(r, Math.min(g, b));
               double saturation = 1 - min / max;
               // 計算亮度
               double brightness = 0.3 * r + 0.6 * g + 0.1 * b;
               // 統(tǒng)計大于閾值的像素
               if (brightness > brightnessThreshold
                       && saturation > saturationThreshold) {
                   set.add(color);
              }
               total++;
          }
      }
       if (total == 0) {
           return 0;
      }
       // 統(tǒng)計大于閾值像素在所有像素的占比
       return set.size() / (double) total;
  }

在對閾值進(jìn)行一些調(diào)優(yōu)后，最終保留結(jié)果如下。

這樣，在進(jìn)行OCR識別時，就不會把未擁有的皮膚也識別出來了。

5.解決匹配時的容錯

要將“李信一念神度”匹配為“李信一念神魔”這個參數(shù)，基本思路是計算兩個文本的重復(fù)度，如果高于一個閾值即可認(rèn)定是相同的文本，目前文本相似度計算有兩種大致方向：

• 基于NLP

提取兩個文本的特征向量，計算向量空間兩個向量夾角的余弦相似度。

• 基于串匹配

將字符串進(jìn)行分割，統(tǒng)計子串是否相同。

為了方便我們采用了第二種方法，在串匹配算法中我們選擇了Rabin-Karp算法，其具體思路是使用滑動窗口得出文本的哈希集合，對兩個哈希集合進(jìn)行比對，計算出相似度。

例如：我們使用窗口大小為2，每次滑動1對“李信一念神魔”和“李信一念神度”進(jìn)行分割，可以得到：

[ "李信" , "信一" , "一念" , "念神" , "神魔" ]

[ "李信" , "信一" , "一念" , "念神" , "神度" ]

而對窗口中元素計算哈希的操作我們可以交給String類的hashCode()方法，所以兩個文本計算相似度方法大致如下：

public static void main(String[] args) {
       // 模擬滑動窗口分割后的結(jié)果
       List<String> list1 = Arrays.asList(new String[]{"李信", "信一", "一念", "念神", "神魔"});
       List<String> list2 = Arrays.asList(new String[]{"李信", "信一", "一念", "念神", "神度"});

       // 向HashSet中添加元素時會計算元素的hash
       Set<String> baseSet = new HashSet<>(list2);

       float count = 0;
       for (String word : list1) {
           // contains方法也是通過hash判斷的
           if (baseSet.contains(word)) {
               count += 1;
          }
      }
       // 輸出0.8
       System.out.println(count / list1.size());
  }

在上述過程中，向HashSet中增加元素，以及使用contains方法判斷HashSet中是否包含元素時，都是基于String類自帶的hashCode()方法進(jìn)行的：

public int hashCode() {
       int h = hash;
       if (h == 0 && value.length > 0) {
           char val[] = value;

           for (int i = 0; i < value.length; i++) {
               h = 31 * h + val[i];
          }
           hash = h;
      }
       return h;
  }

由于我們的文本量比較小，對于這種哈希計算方式，是完全滿足我們的需求的。

而Rabin-Karp算法認(rèn)為，在文本量非常大的情況下，先分割窗口然后每次對窗口中的元素單獨(dú)計算哈希效率是低下的，可以通過改良計算方式，使下一個窗口的哈希與

• 上一個窗口的哈希
• 離開窗口的元素
• 進(jìn)入窗口的元素

產(chǎn)生關(guān)聯(lián)，加快運(yùn)算速度，所以給出了一種更快分割窗口并且計算哈希的方式：

/**
    * 計算文本的哈希集合
    *
    * @param str       文本
    * @param windowLen 滑動窗口大小
    * @param moveLen   每次滑動長度
    * @return 文本的哈希集合
    */
   public static List<Long> hashCode(String str, int windowLen, int moveLen) {
       List<Long> hashList = new ArrayList<>();

       int temp = 1;
       for (int i = 0; i < windowLen; i++) {
           temp = (temp * BASE_NUM) % MOD_NUM;
      }

       long curHash = 0;
       for (int i = 0; i < str.length(); i++) {
           // 加上進(jìn)入窗口元素的哈希
           curHash = (curHash * BASE_NUM + str.codePointAt(i)) % MOD_NUM;
           if (i > windowLen - 1) {
               // 減去離開窗口元素的哈希
               curHash -= (str.codePointAt(i - windowLen)) * temp % MOD_NUM;
          }
           if (curHash < 0) {
               curHash += MOD_NUM;
          }
           if ((i + 1) % moveLen == 0 || (i + 1) == str.length()) {
               hashList.add(curHash);
          }
      }
       return hashList;
  }

如果一個業(yè)務(wù)場景需要匹配的文本量非常大，可以嘗試選用這種方式。

最終，我們的匹配流程大致如下，在系統(tǒng)啟動時，會拉取我們的參數(shù)庫，使用上面的方式對每個參數(shù)進(jìn)行預(yù)處理，得到它們的哈希集合，存到本地，當(dāng)一個OCR識別結(jié)果產(chǎn)生時，計算它的哈希集合，與本地進(jìn)行匹配，如果發(fā)現(xiàn)相似度大于閾值，即認(rèn)為匹配成功。

這樣，我們就保證了一定的容錯性。

6.效果

當(dāng)我們解決了：只識別擁有的皮膚、匹配時有一定容錯，這兩個問題后就可以線上部署了。

目前OCR只應(yīng)用在王者榮耀、和平精英兩款游戲，上線后每日可為我們的商品補(bǔ)充上千參數(shù)。后續(xù)會逐步擴(kuò)展到其他游戲品類。

作者簡介：

常睿，轉(zhuǎn)轉(zhuǎn)訂單業(yè)務(wù)Java研發(fā)工程師。