algorithm - 基于字典的关键字检测

Question

我想从可能存在 OCR 错误的扫描文档中识别关键字。根据每个字符的关键字列表和置信度值及其扫描文档的替代项，我如何开发一种算法来可靠地识别关键字？

对于 OCR，我使用 Tesseract，它为每个字符及其最佳备选方案提供置信度值。所以对于每个单词，我都有一个这样的列表:

 Word=order
 [0] o (93%) [alts: 0 (90%), c (83%), e (82%)]
 [1] r (96%)
 [2] d (96%)
 [3] e (90%) [alts: a (75%)]
 [4] r (95%) 

另一个包含 OCR 错误的示例:

 Word=PaYmeHI (Payment would be correct)
 [0] P (81%) [alts: p (78%), D (68%)]
 [1] a (76%) [alts: 3 (73%), e (63%), ö (61%)]
 [2] Y (87%) [alts: V (86%)]
 [3] m (83%) 
 [4] E (71%) [alts: € (79%), 9 (72%), % (67%), e (65%), B (64%), G (64%)]
 [5] H (76%) [alts: n (83%), D (74%), N (70%), ü (69%)]
 [6] I (75%) [alts: t (69%), { (67%), 1 (65%), i (61%)]

如您所见，tesseract 并不总是选择百分比最高的结果 (4, 5)。

从浏览结果可以看出，大多数值高于 90% 的字符都是正确的。然而，糟糕的结果不一定包含替代列表中的正确字符(参见 [2]，它应该是小写的 y 。

目前，我正在使用 Levenshtein 距离和字符串长度获取候选列表。此外，我排除了关键字 lev2 > 3 .这只是硬编码，因为我仍在寻找确定阈值的好方法。

      int lev = getLevenshteinDistance(keyword, s);
      int lev2 = getLevenshteinDistance(keyword.toLower(), s.toLower());
      int len = Math.abs(keyword.length - s.length); 
      int x = lev + lev2 + len;

我按 x 对关键字列表进行排序, 以获得最有可能的结果。

所以首先，我正在寻找一种方法来根据 OCR 结果和字符串长度确定一个好的阈值。较短的字符串需要的阈值比较大的字符串低，并且 OCR 结果也可靠。以上面的例子为例:对于词序lev2 <= 1 , 就足够了，而对于 payment至少lev2 <= 3应计算。

其次，我如何确定剩下的候选词之一是否真的匹配这个词？万一lev == 0当所有字符的置信度值为 >= 90 时这很明显。但考虑到糟糕的 OCR 结果，我可以开发什么算法来同时包含替代 OCR 选择？

Answer 1

我一直在为我的一个项目考虑类似的事情；我还没有得到任何好的答案，但这里有一些想法:

我想我们要回答的问题是:

此文档(OCR 结果)是否包含术语“订单”？

想法一

OCR 文档包含带有一些“分数”的术语 ...

因此在您的示例中，文档包含:

• 排序得分 = sum(93,96,96,90,95)/5 = 94
• 0rder with score = sum(90,96,96,90,95)/5 = 93
• crder 得分 = sum(83,96,96,90,95)/5 = 92
• 顺序为 score = sum(82,96,96,90,95)/5 = 91
• ordar with score = sum(93,96,96,75,95)/5 = 91
• 0rdar with score = sum(90,96,96,75,95)/5 = 90
• crdar 得分 = sum(83,96,96,75,95)/5 = 89
• erdar 得分 = sum(82,96,96,75,95)/5 = 88

现在我们有了每个候选人的分数，我们可以得到文档的分数，给定一些查询(现在使用 levenshtein 距离......)

给定关键字“order”的文档得分是平均值

• (3-min(lev(order, order),3)*0.33) * 94,
• (3-min(lev(0rder, order),3)*0.33) * 93,
• (3-min(lev(crder, order),3)*0.33) * 92,
• ...,
• ...

如果此分数高于某个阈值，则文档被视为匹配“订单”

想法 2

我们可以使用一些语言模型来改进 OCR 结果

按如下方式计算每个术语的分数:

term        | ocr_score   |ngram score            |combined score
------------+-------------+-----------------------+---------------
order   | 94          |score(ord, rde, der)   |ocr*ngram
0rder   | 93          |score(0rd, rde, der)   |ocr*ngram
crder   | 92          |score(crd, rde, der)   |ocr*ngram
erder   | 91          |score(erd, rde, der)   |...
ordar   | 91          |score(ord, rda, der)   |...
0rdar   | 90          |score(0rd, rda, der)   |...
crdar   | 89          |score(crd, rda, der)   |...
erdar   | 88          |score(erd, rda, der)   |...

其中 score(ord) = 'ord' 的三元组概率

例如，Google Books 给出了任何三元组的三元组概率(参见: http://books.google.com/ngrams/chart?content=ord&corpus=0&smoothing=3&year_start=1970&year_end=2000 )

我们还可以计算一元组、二元组、四元组……；然后我们可以根据单词本身的“unigram”概率计算分数；单词的二元组等等......;那么我们也可以应用一些纯解析的语言模型

现在每个“候选术语”都有更多分数，我们将它们与每个分数的一些权重结合起来，以获得该术语的综合分数

想法 3

好的，所以上面的内容导致了术语/分数的爆炸式增长……这是计算密集型的；所以我们使用一些魔法根据想法 1 和 2 为每个术语构建概率 DFA。文档现在包含概率 DFA 而不是术语。 Lucene 的家伙已经做了一些工作来构建 Levenshtein DFA 并允许检查 DFA1 和 DFA2 是否快速匹配......