优化的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乘11px(10px乘11px是我真实节目中一个角色的实际尺寸.我在这个帖子中将其简化为5px乘5px,因为使用0更容易"绘制"字母和1在一个较小的图像上).

现在当我给它一个10px乘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)中具有黑色像素,因为没有其他字符将该像素视为黑色.因此,我没有在"I"字符上测试110像素匹配,而是将其缩小为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个点来做,就像我的字母"我"一样例子是能够).

---

我提出的替代解决方案是使用哈希表,它将从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表示法中,算法是相同的,因为对于在页面上处理的N个字母,O(110N)= O(2860N)= O(N).然而,它仍然以26的恒定因子得到改善,这是一个显着的改进(例如,而不是需要26分钟,需要1分钟).

---

更新:到目前为止提供的大多数解决方案都没有解决识别角色的独特特征的问题,而是提供替代解决方案.我仍然在寻找这个解决方案,据我所知,这是实现最快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 个像素。恐怕没那么容易。

您还可以使用 Moron（呵呵）的建议，根据您正在扫描的语言的字母频率构建一棵树，类似于霍夫曼编码。这将比每个字母 5 位占用更多的空间，但假设字母使用呈幂律分布，则可能会更小。我会采用这种方法，因为它允许您搜索每个节点的特定分区，而不是搜索一组分区。