我正在为有限的字符集编写一个简单的 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 }
});
我知道我可以通过使用多维数组来优化这部分，但现在让我们忽略它，这是为了说明目的。每个字母的尺寸完全相同，10 像素 x 11 像素（10 像素 x 11 像素是我真实程序中字符的实际尺寸。我在这篇文章中将其简化为 5 像素 x 5 像素，因为使用 0 更容易“绘制”字母和 1 在较小的图像上）。
现在，当我给它一个 10 像素 x 11 像素的图像部分以使用 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)。事实上，它只有一个字符，这意味着在这种情况下它必须是一个“我”，我们发现了我们的独特之处。
您也可以对白色的像素执行相同的操作。请注意，桶 (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 个其他字符。我将如何实现获得尽可能少的检查的目标，并确保我没有运行无关的测试？