algorithm - 优化的 OCR 黑白像素算法

Question

我正在为有限的字符集编写一个简单的 OCR 解决方案。也就是说，我知道字母表中所有 26 个字母的确切样子。我正在使用 C# 并且能够轻松确定给定的像素应该被视为黑色还是白色。

我正在为每个字符生成一个黑色/白色像素矩阵。例如，字母 I(大写 i)可能如下所示:

01110
00100
00100
00100
01110

注意:我在本文后面使用的所有点都假设左上角的像素是 (0, 0)，右下角的像素是 (4, 4)。 1代表黑色像素，0代表白色像素。

我会在 C# 中创建一个相应的矩阵，如下所示:

CreateLetter("I", new List<List<bool>>() {
  new List<bool>() { false, true,  true, true,  false },
  new List<bool>() { false, false, true, false, false },
  new List<bool>() { false, false, true, false, false },
  new List<bool>() { false, false, true, false, false },
  new List<bool>() { false, true,  true, true,  false }
});

我知道我可以通过使用多维数组来优化这部分，但现在让我们忽略它，这是为了说明目的。每个字母的尺寸完全相同，10px x 11px(10px x 11px 是我真实程序中字符的实际尺寸。我在这篇文章中将其简化为 5px x 5px，因为使用 0 来“绘制”字母要容易得多和 1 在较小的图像上)。

现在，当我给它一个 10px x 11px 的图像部分以使用 OCR 进行分析时，它需要在每个像素 (10 * 11 = 110) 上的每个字母 (26) 上运行，这意味着 2,860 (26 * 110)每个字符的迭代(在最坏的情况下)。

我认为这可以通过定义每个角色的独特特征来优化。因此，例如，让我们假设字符集仅包含 5 个不同的字母:I、A、O、B 和 L。它们可能如下所示:

01110  00100  00100  01100  01000
00100  01010  01010  01010  01000
00100  01110  01010  01100  01000
00100  01010  01010  01010  01000
01110  01010  00100  01100  01110

在分析了每个字符的独特特征后，我可以显着减少测试字符所需的测试次数。例如，对于“I”字符，我可以将它的独特特征定义为在坐标 (3, 0) 中有一个黑色像素，因为没有其他字符将该像素作为黑色。因此，我没有测试 110 像素以匹配“I”字符，而是将其缩减为 1 像素测试。

这就是所有这些角色的样子:

var LetterI = new OcrLetter() {
  Name = "I",
  BlackPixels = new List<Point>() { new Point (3, 0) }
}
var LetterA = new OcrLetter() {
  Name = "A",
  WhitePixels = new List<Point>() { new Point(2, 4) }
}
var LetterO = new OcrLetter() {
  Name = "O",
  BlackPixels = new List<Point>() { new Point(3, 2) },
  WhitePixels = new List<Point>() { new Point(2, 2) }
}
var LetterB = new OcrLetter() {
  Name = "B",
  BlackPixels = new List<Point>() { new Point(3, 1) },
  WhitePixels = new List<Point>() { new Point(3, 2) }
}
var LetterL = new OcrLetter() {
  Name = "L",
  BlackPixels = new List<Point>() { new Point(1, 1), new Point(3, 4) },
  WhitePixels = new List<Point>() { new Point(2, 2) }
}

这对于 5 个字符手动执行具有挑战性，并且添加的字母数量越多，难度就越大。您还希望确保您拥有最少一组字母的独特特征，因为您希望尽可能对其进行优化。

我想创建一个算法来识别所有字母的独特特征，并生成与上述类似的代码。然后我会使用这个优化的黑/白矩阵来识别字符。

我如何获取填充了所有黑色/白色像素的 26 个字母(例如 CreateLetter 代码块)，并将它们转换为一组优化的定义字母的独特特征(例如新的 OcrLetter() 代码块)？我如何保证它是最有效的独特特征定义集(例如，不是将 6 个点定义为独特特征，而是有一种方法可以用 1 或 2 个点来做到这一点，如我的字母“I”例如能够)。

我提出的另一种解决方案是使用哈希表，它将从 2,860 次迭代减少到 110 次迭代，减少了 26 次。这是它的工作方式:

我会用类似于以下的数据填充它:

Letters["01110 00100 00100 00100 01110"] = "I";
Letters["00100 01010 01110 01010 01010"] = "A";
Letters["00100 01010 01010 01010 00100"] = "O";
Letters["01100 01010 01100 01010 01100"] = "B";

现在，当我到达要处理的图像中的某个位置时，我将其转换为一个字符串，例如:“01110 00100 00100 00100 01110”，然后只需在哈希表中找到它。这个解决方案看起来很简单，然而，这仍然需要 110 次迭代才能为每个字母生成这个字符串。

在大 O 表示法中，算法是相同的，因为 O(110N) = O(2860N) = O(N) 在页面上处理 N 个字母。然而，它仍然以 26 的常数因子进行了改进，这是一个显着的改进(例如，它需要 1 分钟而不是 26 分钟)。

更新:迄今为止提供的大多数解决方案都没有解决识别角色独特特征的问题，而是提供了替代解决方案。我仍在寻找这个解决方案，据我所知，这是实现最快 OCR 处理的唯一方法。

我只是想出了一个部分解决方案:

对于每个像素，在网格中，将具有它的字母存储为黑色像素。

使用这些字母:

  I      A      O      B      L
01110  00100  00100  01100  01000
00100  01010  01010  01010  01000
00100  01110  01010  01100  01000
00100  01010  01010  01010  01000
01110  01010  00100  01100  01110

你会有这样的事情:

CreatePixel(new Point(0, 0), new List<Char>() {                         });
CreatePixel(new Point(1, 0), new List<Char>() { 'I',           'B', 'L' });
CreatePixel(new Point(2, 0), new List<Char>() { 'I', 'A', 'O', 'B'      });
CreatePixel(new Point(3, 0), new List<Char>() { 'I'                     });
CreatePixel(new Point(4, 0), new List<Char>() {                         });
CreatePixel(new Point(0, 1), new List<Char>() {                         });
CreatePixel(new Point(1, 1), new List<Char>() {      'A',      'B', 'L' });
CreatePixel(new Point(2, 1), new List<Char>() { 'I'                     });
CreatePixel(new Point(3, 1), new List<Char>() {      'A', 'O', 'B'      });
// ...
CreatePixel(new Point(2, 2), new List<Char>() { 'I', 'A',      'B'      });
CreatePixel(new Point(3, 2), new List<Char>() {      'A', 'O'           });
// ...
CreatePixel(new Point(2, 4), new List<Char>() { 'I',      'O', 'B', 'L' });
CreatePixel(new Point(3, 4), new List<Char>() { 'I', 'A',           'L' });
CreatePixel(new Point(4, 4), new List<Char>() {                         });

现在对于每个字母，为了找到独特的特征，您需要查看它属于哪个桶，以及桶中其他字符的数量。所以让我们以“我”为例。我们访问它所属的所有桶 (1,0; 2,0; 3,0; ...; 3,4) 并看到其他字符最少的桶是 (3,0)。事实上，它只有1个字符，意味着在这种情况下它必须是一个“我”，我们发现了我们独特的特性。

您也可以对白色像素执行相同操作。请注意，bucket (2,0) 包含除“L”之外的所有字母，这意味着它可以用作白色像素测试。同样，(2,4) 不包含“A”。

可以立即丢弃包含所有字母或不包含任何字母的桶，因为这些像素无法帮助定义独特的特征(例如 1,1；4,0；0,1；4,4)。

当您没有对字母进行 1 像素测试时，它会变得更加棘手，例如在“O”和“B”的情况下。让我们来看看'O'的测试......

它包含在以下存储桶中:

// Bucket   Count   Letters
// 2,0      4       I, A, O, B
// 3,1      3          A, O, B
// 3,2      2          A, O
// 2,4      4       I,    O, B, L

此外，我们还有一些可以提供帮助的白色像素测试:(我只列出了最多缺少 2 个的测试)。缺失计数计算为 (5 - Bucket.Count)。

// Bucket   Missing Count   Missing Letters
// 1,0      2                  A, O
// 1,1      2               I,    O
// 2,2      2                     O,    L
// 3,4      2                     O, B

所以现在我们可以取最短的黑色像素桶 (3,2) 并看到当我们测试 (3,2) 时，我们知道它是“A”或“O”。所以我们需要一种简单的方法来区分“A”和“O”。我们可以寻找包含“O”但不包含“A”的黑色像素桶(例如 2,4)或包含“O”但不包含“A”的白色像素桶(例如 1,1)。这些中的任何一个都可以与 (3,2) 像素结合使用，以仅通过 2 次测试来唯一标识字母“O”。

当有 5 个字符时，这似乎是一个简单的算法，但是当有 26 个字母和更多像素重叠时，我该怎么做？例如，假设在 (3,2) 像素测试之后，它发现了 10 个不同的包含该像素的字符(这是所有桶中最少的)。现在我需要找到与其他 9 个字符的差异，而不是仅与其他 1 个字符的差异。我将如何实现尽可能少检查的目标，并确保我没有运行无关的测试？

Answer 1

我没有答案，但这里是您最终解决方案的一些界限:

如果您想直接“使用 X 像素作为键”，那么您至少需要 ceiling(log2(number of characters))像素。您将无法用更少的位来消除字母的歧义。在您的情况下，尝试找到 5 个像素等效于找到将字母拆分为独立分区的 5 个像素。恐怕没那么容易。

您也可以使用白痴(呵呵)suggestion并根据您正在扫描的语言的字母频率构建一棵树，类似于 Huffman coding .这将比每个字母 5 位占用更多的空间，但假设 power-law distribution 可能会更小字母用法。我会采用这种方法，因为它允许您搜索每个节点的特定分区，而不是搜索一组分区。