前言：

         文字识别的关键之所在就是单个文字的切割，切割的准确度极大的影响了文字识别的正确率。本文基于传统横纵投影的思想对文字进行切割，使用java与python实现了本算法。

 

基本思路：

         1、横向扫描，切出每一行

         2、对每一行进行纵向扫描，得出每一个字

 

经过对原始图像的相关处理，得出如下二值图（仅有黑白色）。这里的‘相关处理’是很复杂的，涉及图像学相关知识，我是通过opencv进行处理的。本文主要对切割算法进行讨论，图片处理部分望读者自行了解。



（待切割图）

横向扫描

         横向扫描就是依次从左往右统计，得出这一行黑色点的数量。比如上图尺寸为1200*430，经过横向扫描就可以得到430个数值，这个数值表示在1200个点中黑色点的数量。我们把这430个数直观的展示出来，可以得到下图：



（横向切割统计图，x：行数   y：黑色点数）

在上图中，y轴数值不为0的区域就是文字存在的地方，为0的区域就是每行之间相隔的距离。我们通过如下规则就可以找出每一行文字的起始点和终止点，以定位该行文字区域：1、如果前一个数为0，则记录第一个不为0的坐标；2、如果前一个数不为0，则记录第一个为0的坐标。形象的说就是从出现第一个非空白行（开始有字）到出现第一个空白行（没有字）这段区域就是文字存在的区域。



（横向切割说明图）

纵向扫描

         纵向扫描与横向扫描同理。针对横向扫描切割出的区域，进行纵向扫描，得出每一个字。

我们对横向扫描得出的第一行进行纵向扫描，可以得到1200个数值，如下图：



（横向切割统计图，x：行数   y：黑色点数  省略了部分区域）

再运用横向扫描的思维，对纵向扫描的数据进行切割，就可以得出单个文字了。

 

切割结果



（切割结果）

         可以看到切割结果有些不理想，会存在很多连在一起的字。

结果分析

         算法对于数字切割十分理想，但是对于汉字会存在切割失败的现象。分析发现部分汉字两两之间没有空白区域，是连在一起的，所以纵向扫描算法就无法准确切割。如下图所示：



所以直接使用投影进行切割，这种方法是不可行的。我们需要对该算法进行优化，以便得出更为准确的结果。优化算法敬请期待下篇（文字切割算法-投影切割优化）。

项目源码：我的github（https://github.com/printlin/tmOcr/tree/master）

前言

        在上文（文字切割算法-基于投影的切割）中发现切割结果并不是很理想，所以在本文提出优化算法对结果进行进一步处理。本算法的解决思路很简单，即针对已暴露出的问题进行解决，对于未暴露的问题就无能为力了。所以算法的鲁棒性并不是很好，但是简单易实现。

发现问题

         对基于投影的切割结果进行观察，可以将问题总结为三类。

整体连接



         多个文字连接在一起

左右结构分开



         左右结构的文字被切割成两个字

左右结构分开后连接



         左右结构的文字分开后，又与前后相邻文字相连

 

解决问题

整体连接

         由于汉字是方块字，可以认为每个字的长宽比例都是差不多的，基本都是1:1（金龙鱼调和…呸）。对于整体连接在一起的文字，可以先计算整体的长宽比。如果比例是接近于整数的（±0.2），则认为这是整体连接在一起的多个字。再计算每个字的平均长度进行切割，就可以得到一个比较不错的结果。



       如上图，这是四个字连在一起的。长宽比：104/27≈3.85，3.85>4-0.2所以我们认为它是4个字。则平均宽度：104/4=26，按照26*27的宽长进行切割，就可以得出结果。（这里的长宽比是：宽度/长度）



 

左右结构分开

         由于左右结构分开后，两张图片的长宽比与数字符号的长宽比相似。所以我们无法判断到底是偏旁还是符号，这样就无法进行连接。这个问题将在以后提出识别算法对图片进行识别后解决。



如上图，由于无法识别图片内容，所以无法判断到底是“7”与“阝”连接，还是“阝”与“艮”连接。

左右结构分开后连接

         采用整体连接的解决思路，先计算长宽比，如果发现长宽比不是在整数附近的（>±0.2），则认为这是左右结构分开后连接的。因为这种情况都是两张图，所以在发现第一张是分开后连接的，则将这张图先以1:1进行切割，再将剩下的部分记录。如果这张图相邻的下一张也被判断为是分开后连接的，则将上一张图剩下的部分与这张图的开头相连接，再进行1:1切割。这样就可以得到一个不错的结果。



         如上图，先对第一张进行1:1切割，即按照27*27的大小从开头逐步向后切割，记录最后剩下的部分“丬”。再判断下一张图，发现也是分开后连接的，则按照27*27的大小从末尾逐步向前切割，得到剩下的部分。最后将这两个剩下的部分进行连接，得到一个完整的“北”。

（当然这里要求在投影切割时记录图片两两之间的距离，这样才能还原被切割后的图片）

切割结果如下：



 

结果

        在采用上述优化算法后，发现切割结果有了显著的成效。但是还是会存在一些不足，这些问题会在以后提出识别算法后进行优化。文字切割出来后，我们可以通过图片相似度比对算法对图片特征进行提取，以进行识别。



项目源码：我的github（https://github.com/printlin/tmOcr）

转自：https://www.cnblogs.com/skyfsm/p/8029668.html

要做文字识别，第一步要考虑的就是怎么将每一个字符从图片中切割下来，然后才可以送入我们设计好的模型进行字符识别。现在就以下面这张图片为例，说一说最一般的字符切割的步骤是哪些。



当然，我们实际上要识别的图片很可能没上面那张图片如此整洁，很可能是倾斜的，或者是带噪声的，又或者这张图片是用手机拍下来下来的，变得歪歪扭扭，所以需要进行图片预处理，把文本位置矫正，把噪声去除，然后才可以进行进一步的字符分割和文字识别。这些预处理的方法在我的前面几篇博客都有提到了，大家可以参考参考：
透视矫正
水平矫正

在预处理工作做好之后，我们就可以开始切割字符了。最普通的切割算法可以总结为以下几个步骤：

对图片进行水平投影，找到每一行的上界限和下界限，进行行切割
	
对切割出来的每一行，进行垂直投影，找到每一个字符的左右边界，进行单个字符的切割
一看只有两个步骤，好像不太难，马上编程实现看看效果。

首先是行切割。这里提到了水平投影的概念，估计有的读者没听过这个名词，我来解释一下吧。水平投影，就是对一张图片的每一行元素进行统计（就是往水平方向统计），然后我们根据这个统计结果画出统计结果图，进而确定每一行的起始点和结束点。下面提到的垂直投影也是类似的，只是它的投影方向是往下的，即统计每一列的元素个数。

根据上面的解释，我们可以写出一个用于水平投影和垂直投影的函数。

#define V_PROJECT 1  //垂直投影（vertical）
#define H_PROJECT 2  //水平投影（horizational）

typedef struct
{
    int begin;
    int end;

}char_range_t;



//获取文本的投影以用于分割字符(垂直，水平),默认图片是白底黑色
int GetTextProjection(Mat &src, vector<int>& pos, int mode)
{
    if (mode == V_PROJECT)
    {
        for (int i = 0; i < src.rows; i++)
        {
            uchar* p = src.ptr<uchar>(i);
            for (int j = 0; j < src.cols; j++)
            {
                if (p[j] == 0)  //是黑色像素
                {
                    pos[j]++;
                }
            }
        }
    }
    else if (mode == H_PROJECT)
    {
        for (int i = 0; i < src.cols; i++)
        {

            for (int j = 0; j < src.rows; j++)
            {
                if (src.at<uchar>(j, i) == 0)
                {
                    pos[j]++;
                }
            }
        }
    }

    return 0;
}

上面代码提到的vector pos就是用于存储垂直投影和水平投影的位置的，我们可以根据它来确定行的位置。我们先把水平投影画出来。

下面是画出水平（垂直）投影图的代码实现。

void draw_projection(vector<int>& pos, int mode)
{
    vector<int>::iterator max = std::max_element(std::begin(pos), std::end(pos)); //求最大值
    if (mode == H_PROJECT)
    {
        int height = pos.size();
        int width = *max;
        Mat project = Mat::zeros(height, width, CV_8UC1);
        for (int i = 0; i < project.rows; i++)
        {
            for (int j = 0; j < pos[i]; j++)
            {
                project.at<uchar>(i, j) = 255;
            }
        }
        imshow("horizational projection", project);

    }
    else if (mode == V_PROJECT)
    {
        int height = *max;
        int width = pos.size();
        Mat project = Mat::zeros(height, width, CV_8UC1);
        for (int i = 0; i < project.cols; i++)
        {
            for (int j = project.rows - 1; j >= project.rows - pos[i]; j--)
            {
                //std::cout << "j:" << j << "i:" << i << std::endl;
                project.at<uchar>(j, i) = 255;
            }
        }
        imshow("vertical projection", project);
    }

    waitKey();
}

水平投影图：



通过上面的水平投影图，我们很容易就能确定每一行文字的位置，确定的思路如下：我们可以以每个小山峰的起始结束点作为我们文本行的起始结束点，当然我们要对这些山峰做些约束，比如这些山峰的跨度不能太小。这样子我们就得到每一个文本行的位置，接着我们就根据这些位置将每个文本行切割下来用于接下来的单个字符的切割。

//获取每个分割字符的范围，min_thresh：波峰的最小幅度，min_range：两个波峰的最小间隔
int GetPeekRange(vector<int> &vertical_pos, vector<char_range_t> &peek_range, int min_thresh = 2, int min_range = 10)
{
    int begin = 0;
    int end = 0;
    for (int i = 0; i < vertical_pos.size(); i++)
    {
        if (vertical_pos[i] > min_thresh && begin == 0)
        {
            begin = i;
        }
        else if (vertical_pos[i] > min_thresh && begin != 0)
        {
            continue;
        }
        else if (vertical_pos[i] < min_thresh && begin != 0)
        {
            end = i;
            if (end - begin >= min_range)
            {
                char_range_t tmp;
                tmp.begin = begin;
                tmp.end = end;
                peek_range.push_back(tmp);
                begin = 0;
                end = 0;
            }

        }
        else if (vertical_pos[i] < min_thresh || begin == 0)
        {
            continue;
        }
        else
        {
            //printf("raise error!\n");
        }
    }

    return 0;
}

切割每一行，然后我们得到了一行文本，我们继续对这行文本进行垂直投影。



紧接着我们根据垂直投影求出来每个字符的边界值进行单个字符切割。方法与垂直投影的方法一样，只不过，因为字符排列得比较紧密，仅通过投影确定字符得到的结果往往不够准确的。不过先不管了，先切下来看看。



从上图看出，切割效果不太好，那多切割几行再看看。





效果确实不咋滴，那换成英文文档来测试这个切割算法。

比如切割这个英语文本图片



切割效果还是很不错的：





那为什么英语的切割效果很好，但中文效果一般呢？

分析其原因，这其实跟中文的字体复杂度有关的，中文的字符的笔画和形态都比英文的多，更重要的是英文字母都是绝大部分都是联通体，切割起来很简单，但是汉字多存在左右结构和上下结构，很容易造成过度切割，即把一个左右偏旁的汉字切成了两份，比如上面的“则”字。

针对行字符分割，左右偏旁的字难以分割的情况，我觉得可以做以下处理：

先用通用的分割方法切割字符，得到一堆候选的切割字符集合。
	
统计字符集合的大多数字符的尺寸，作为标准尺寸。
	
根据标准尺寸选出标准的字符，切割保存。并对切割保存好的字符原位置涂成白色
	
对剩下下来的图片进行腐蚀，让字体粘连。
	
用1中算法再次分割，得到完整字体集合。
因为以上的思路可能只适应于纯汉字文本，所以就不贴代码了。

最后贴几张分割字符的图吧，感觉分割效果不太让人满意，主要是汉字的分割确实很有难度，左右偏旁的字经常分割错误。

英文的切割还是比较简单的，毕竟英文字母基本都是联通体，而且没有像汉字那样的左右结构。



对于字体间隔比较宽的汉字文档，总的看来分割任务基本完成，但是左右结构的汉字依然难以正确分割。

 



最后看一下一些字体较小，字体间隔较窄的情况。这类情况确实分割效果大打折扣，因为每个字体粘连过于接近，字体的波谷很难确定下来，进而造成切割字符失败。



总结

汉字字符切割，看似简单，做起来其实很难做得很好，我也对此查阅了很多论文，发现其实很多论文也谈到了，汉字确实很那做到一个高正确率的分割，直至现在还没有一统江湖的解决方案。汉字切割的失败，就会直接导致了后面OCR识别的失败，这也是当前很多一些很厉害的OCR公司都没法把汉字做到100%识别的一个原因吧。所以这个问题就必须得到很好的解决。现在解决汉字切割失败（过切割，一个字被拆成两个）的较好方法是，在OCR识别中再把它修正。比如“刺”字被分为两部分了，那么我们就直接将这两个“字”送去识别，结果当然是得到一个置信度很低的一个反馈，那么我们就将这两个部分往他们身边最近的、而且没被成功识别的部分进行合并，再将这个合并后的字送进OCR识别，这样子我们就可以通过识别反馈来完成汉字的正确分割和识别了。既然一些基于图像处理的方法基本很难把汉字分割的效果做得很好，那深度学习呢？我先去试试，效果好的话再分享给大家。

转载来自两篇文章：拍照怎么搜题？（上）和拍照怎么搜题？（下）

 

注：这里讨论分析的仅仅是简单的思路部分，针对特定场景。自然场景下的文本区域检查、切割、识别与这里讨论的内容有一定差别。

################################   上半部分  ########################################

前一段时间几个拍照搜题的软件挺流行（比如：小猿搜题、作业帮、学霸君等），手机拍张照片，就能把考题的答案搜出来，完全不用去百度手敲。这可乐坏了莘莘学子们，不过不知道父母是什么感受。


出于程序员那种职业的好奇心，同时也去评估一下做这个事情的难度和成本，老王用了两周的时间做了一个简单的研究并写了一个demo程序，这里分享给大家（注：由于研究时间不长，如有不正确的地方请专家们指正~）

拍照搜题的技术点主要由图像识别和内容搜索组成，将拍照图像中的文字或者图形识别出来，再交给检索系统，对已有的题目进行快速的搜索，找出最相似的题目。由于之前对搜索技术有过一定的了解（毕竟在狼厂干过几年，耳濡目染^_^），所以这次主要聚焦到图像文本的识别上。同时，只是调研性质，所以为了降低难度，我这次只做了英语的识别。

 

 

先给大家看看最后的效果。以下是随便用手机拍的一段英文文章：

 

 



 

最后识别出来以后，没有做任何的单词校正工作，效果如下：

=======================================

Three months after [he government stopped issulng (&%) or renewing permits for In[ernet cafes because of security (%#) concerns, some cafe owners are having flnanclal (ff%%) concerns of their own.

=======================================


后来，我的同事tt和yx可怜我，帮我做了两个相关的单词匹配算法，对单词做校正，使得一些识别的不准的单词得到校正，比如：issulng -> issuing。


好了，开始正题吧~

 


==== 处理流程 ====



整个过程大体分为两个阶段：

1、图像的处理。就是将我们拍的照片进行清理（有点类似于洗衣服），然后对图像中的字符进行切分，为字符的识别做准备。大概分成几个过程，分别是：

a、灰度处理：将彩色图片变成灰度图

b、二值化：将灰度图变成黑白图

c、去噪：消除黑白图上的噪点，让图看起来更干净

d、旋转：对图片进行顺时针和逆时针旋转，找到一个最佳水平位置

e、水平切割：对调整好水平位置的图片进行一行一行的切割

f、垂直切割：对一行一行的图片进行一列一列的切割，产出单个的字符。


2、图像的识别。就是将上面的一个个单独字符的图片进行判别，看他到底是哪个字符。


你是不是感觉有点晕了呢？不错，是我我也晕了，哈哈哈~

还记得我们的理念嘛？把复杂的问题，简单的讲清楚！

来吧，老王不会干巴巴的讲那些无聊的理论，看看实际怎么处理的吧。


==== 图像的处理 ====

 

第一步，我们拍照得到原图。

 



 

肉眼看，你觉得这个图是不是黑白的？
回答“是”的同学，我负责任的告诉你，你的眼睛欺骗了你。可以用图像处理软件看看每一个像素，他们其实是彩色！！！
彩色有什么问题么？对于人眼来说，当然没有。不过对于我们的程序来说，就是有问题的。他不知道哪个颜色是有效信息。所以，我们接下来的工作，就是对信息进行降维，将RGB（红绿蓝）的256*256*256种色值降维到2种，即：白+黑。这样，我们的程序就能很轻松的判断信息的有效性了。
好了，要实现白+黑，还得分两步走：先灰，再黑白。

那么，老王要问问题了：

问：什么是黑色？
答：R = 0, G = 0, B = 0，也就是css中的#000000

问：什么是白色？
答：R = 255, G = 255, B = 255，也即#ffffff

问：什么是灰色？
答：诶……

老王也不知道明确的定义，但是老王知道是：R = G = B。也就是红绿蓝的色值相等的颜色。比如，我们经常在css中设置的值：#e0e0e0 #9c9c9c等等。

第二步，就是把上面拍的原始图变成灰度图。



仔细跟上面的图片对比一下，有什么不一样嘛？考验像素眼的时候到了！如果眼睛还是看不出来，我做一张对比图给大家看看：



 

看出区别来了嘛？如果还没看出来，请用图像处理软件查看图上下部分的每一个像素。


那么，彩色图是怎么变到灰度图的呢？

我们知道，每一个像素的颜色值可以由RGB三原色来表示，比如：红色=RGB(255, 0, 0)，黄色=RGB(255, 255, 0)。如果我们将每个像素的设置成一样的，他就变成灰色了，比如：Color-Pixel(x, y) = RGB(r, g, b) => RGB(t, t, t)，其中 t = r * k + g * p + b * q 并且k + p + q = 1，这样的话，就可以把彩色变成灰白了。


这里k、p、q的取值有很多很多种，一般说取0.11、0.59、0.3 或者 1/3、1/3、1/3。至于为什么，我就没有去深究了~

我的算法里，取的是1/3、1/3、1/3。


好了，有了灰色图，我们怎么把他变黑白呢？（装B的说法：二值化）

算法有很多很多很多很多……

第三步，灰度图的二值化。

我下载了一个软件，上面列举了n种二值化的方法



 

每一种方法都有优缺点，没有一种完美的解决方案。我自己做了灰度平均值、百分比阈值和双峰波谷最小值等几个算法，根据我的实验效果，最后选择了双峰波谷最小值法。

这种算法是怎么样工作的呢？等我慢慢道来。
我们之前已经得到了灰度图，他的RGB值：t=r=g=b。这样我们就可以将RGB(r,g,b)值合并，用一个t表示。最终简化成用1个Byte(8bits)来表示每一个像素的值，每个像素的值就会落在[0, 255]这样一个闭区间上，如果我们用16进制表示，就是[00, ff]这样一个区间。如果用放大镜放大一个10*4个像素的图片，就会像这样：

00 00 00 00 00 00 00 00 00 00
ee 00 ee dd 4f 29 30 00 00 00
ff 10 32 ee 40 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00

好了，我们看看，值为0的个数C(0)=29个, C(ee)=3, C(dd)=1, C(4f)=1, C(29)=1, C(30)=1, C(32)=1……
于是乎，如果我们统计完我们实验那张图片的0~255每个值的个数，会得到怎么样的一个结果呢？

 



用上述的方法，我把之前处理的那个灰度图片的灰度值放到二维平面上，x轴表示0~255种色值，y轴表示每个色值的个数。仔细看，是否很容易看出有两个波峰。这两个波峰，就是这张灰度图片上最重要的两个色值：前景色+背景色。

一般来讲，在文本照片的case里，我们会认为背景色的数值会比前景色多很多，所以较高的波峰，我们就认为是背景色，而低的那个呢，我们认为是前景色。在非文本的很多情况下，有可能出现多个波峰，这个时候，前景色有可能是多个色调，这种case就先不在这里讨论了。

好啦，有这样一个数值投影，我们只要能找出前景色和背景色，就很好识别哪些是文字，哪些是背景了，对吧。从而，我们只要把前景标志为1，背景标志为0。我们就可以把一张w*h像素的彩色图变成一个w*h的位图。我们再在这张位图上做算法，就轻松太多了。接下来的工作，就是怎么样用算法来找到前景色和背景色。

我们肉眼很容易看出，在x=18和x=135两个点附近是两个波峰，那里对应的就是我们的前景和背景。不过，对于我们的程序来讲，还不是那么容易。我们需要再用算法来处理一下，让程序能很容易的辨认出来。

我们用程序怎么判断一个点是波峰呢？就是他旁边的两个点值比他小，对不对。那旁边的两个点比他小，他就一定是波峰嘛？很明显不是。比如我们上面的统计图，很多毛刺的点，他们不是波峰，但是比周围的点要大。那有没有一种比较好的算法能快速的找到波峰呢？

其中有一种简单粗暴但有效的方法，就是迭代平滑：每个点a[i] = (a[i-1] + a[i] + a[i+1]) / 3（当然，首尾两个点单独处理），如此反复，至到找到只有两个点（如果多个连续点值相同，则看成是一个点）比旁边的点要大，或者最多执行K次（比如100次）。

我们来想想这个逻辑，我们不断用旁边点的值来修正一个点，那经过多次以后，这个点的值就会趋近于周围两个点。如果是一个突兀点，比如是一个高点，多次平均以后，一定和周围两个点的值相当，极限情况就是这几个点相等，对吧。



这就是我们迭代平滑以后的点，看起来是不是如丝般顺滑啊，哈哈哈。
当然，如果迭代K次以后，也找不到这样两个点的话，我们就只能做个兼容方案：先找到最高点，然后再找距离这个点左右各p个点以外的次高点。我们就认为这两个点是前景和背景。当然，这个并不能证明他们就是，只是觉得他们最可能是。这个就没有绝对的好，只能做技术上的折中。这个时候就是做实验调参数了。

好了，有了波峰以后，我们总要给前背景做个区分，也就是，从那个点分开，把贴近背景的点认为都是背景，把贴近前景的点，认为都是前景。这个时候，我们就选择了两个波峰中间的波谷。（也有算法选择他们之间的平均值）。具体到这个case，我们很容易就选择到了62号点附近。



 

这样，小于62的点，都是前景色，其余的都是背景色。换句话说，也就是灰度图像上，gray=r=g=b中值小于62的，都是前景色，我们把他们标识为1，认为是黑色。其余的都是0，认为是白色。看看效果吧：



怎么样，是不是感觉一下就清爽了呢？

这样，我们就把一张彩色图，变成了黑白图。

现在，我们的灰度像素图，就变成了类似这样的效果：


0 0 0 0 0 0 0 0 0 0

1 0 1 1 1 1 1 0 0 0

1 0 1 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0


完全就是我们熟悉的二进制的位图，专业俗称bitmap。哈哈哈哈~


好了，二值化做完了，接下来，我们需要做的，就是对黑白图片上的一些干扰点进行优化，去掉这些干扰点（俗称：噪点）。这个过程也叫去噪。

第四步，去噪点。

我们为什么要去掉噪点呢？我们把之前二值化以后的图具备放大：



大家可以看红色剪头所指，有很多零星的黑点。就像美女脸上出现了小黑癍，非常影响我们对美的追求一样，会极大干扰到我们程序对于图片的切割和识别。于是乎，我们要尽我们一切可能，把这些黑斑，去掉！！


常用的去噪方法很多很多。

最简单的，即是大家在学算法数据结构中学到的DFS或者BFS（深度和广度搜索）。我们对w*h的位图先搜索所有联通的区域（值为1的，我们看起来是黑色的，连接起来的区域）。所有联通区域算一个平均的像素值，如果某些联通区域的像素值远远低于这个平均值，我们就认为是噪点。然后用0代替他。


还有一些高级的算法，比如高斯去噪、椒盐去噪等，用的是每个点上下左右8个点的平均值或者是求和以后的对比值来替代这个点，多次迭代来去噪。详细的算法可以看看相关论文，也不是特别复杂。鉴于篇幅就只提到这里。


去噪如果做的太厉害，就容易误伤，把正常点当噪点去掉了（所谓的腐蚀），所以要注意取得一个平衡。


我的算法里，上述方法都做了实验，最后选择了bfs去噪的方法。大家看看效果如下：



上面那些噪点基本上都被清理掉了。就像美女涂了美白的护肤品一样，爽~


好了，对于图像本身的清洗处理，我们基本上做的差不多了。

接下来，我们就要开始准备开始对图像进行切割了。洗好的鸭子，终于要上菜板了~

第五步，旋转调平。

对于用户而言，拍照的时候不可能绝对的水平，所以，我们需要通过程序将图像做旋转处理，来找一个认为最可能水平的位置，这样切出来的图，才有可能是最好的一个效果。


那我们怎么样评估一个旋转的角度是一个好的效果呢？


我们假定调整了一个角度alpha，如果把所有点向左投影，如果该行都是0，则计数加一。这样，我们统计累加以后，找到调整角度以后，计数最大的那个角度。直白的说，就是，调整角度alpha，如果使得空行越宽越明显，这样的调整就是好的。


但是，由于旋转操作是在做坐标变换，是一个O(n^2)的算法，所以开销很大，我们的调整最好是在一个小范围内做调整，比如：-5°~ +5°之间，按0.1°为最小单位做调整。这样只需要100次，我们就可以找到一个相对比较满意的值。


具体旋转的算法，可以自己用坐标变换来实现，也可以用各个语言提供的库函数来做。我偷懒，用了java的系统库函数，嘿嘿~


看看我们调整以后的效果：



我们放一个对比图，因为调整角度比较小，所有要仔细看哦~



好了，图像调整的水平了，我们就可以对图像进行切割了。所以接下来，我们就先水平切割图像，然后再对每一行进行垂直切割。最终产出一个个字符。

第六步，水平切割。

大家如果有写过日记的话，就很清楚的感觉到，写日记的时候，日记本的每一行都有一条水平线，用来保证我们写的字的水平，对吧~ 现在我们就是要沿着每一条水平线，把我们的文字用剪刀剪成一行一行的。这就是水平切割。


还是老规矩，好不好，先看疗效：



这是我的程序，对二值化、去噪和旋转调平以后的图像做的水平切割的效果。没一行的上边缘画了一条实线，下边缘画了一条虚线。在程序上，就是对应行号被标记为一个水平区块的开始和结束。


那具体是怎么实现的呢？来吧，老王带你继续往下走。


首先，我们先在重复一下我们现在已经有的一个数据结构，是一张类似以下效果的w*h的位图：


0 0 0 0 0 0 0 0 0 0

1 0 1 1 1 1 1 0 0 0

1 0 1 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0


接下来，我们将我们处理完的黑白图片的位图往y轴上投影，将所有值进行累加，这样就能得到一个在y轴上的曲线（或直方图）。



大家应该感觉到了吧，没一行值大的地方，就是前景色多的地方，值小的地方，就基本都是背景色。好了，这样就好办了。我们按照之前的方案，先做平滑，然后找波谷，从波谷切分。



以上就是平滑以后的效果，是不是看着就爽很多了~ ^_^


然后我们就按之前的办法，从波谷切分，这样就得到一块一块的（鉴于篇幅，我就不再画图了哈~）。虽然有了这一块一块的，但是这一块块的东西还含有大部分的背景，我们需要将他们进行压缩。直到每一块的上边缘线和下边缘线紧贴我们的文本。


怎么搞？其实也很简单。我们将每一块的投影值求一个平均，如果某一个点的值远远低于这个平均值，则认为他是背景。这里就用一个参数来调整。我这里取值如下：

final double THRESHOLD = 0.5;

final double avg = Math.min((total / lastTroughIds.length) * THRESHOLD, 10);


只要投影值小于这个avg的，我们就把他当做背景。这样，我们就将每一块的背景行去掉了。


这样是不是就结束了？ No No No……


有一种case是这样的：i jump

可以看到，i j特别多的这种，有可能上面那个点被单独分隔成一行了，对不对。我们需要对前后比较小的区块进行合并，然后让他们形成一个整体。


做完这一些工作以后，基本上行就被划开了（实际上还有很多细节工作要做，这里就不赘述了。如果有兴趣，我以后可以开源我的代码~）


水平切开了以后，我们对于图像的处理就完成90%了，最后就是垂直切分，把他们切成一个个单独的字符块。

第七步，垂直切割。

紧接上面，我们将得到的水平的切割行，进行垂直的切割处理。先看效果：



那垂直切割和水平切割有什么不一样嘛？有一点不一样：同一行的两个字符往往挨的比较紧，有些时候会出现垂直方向上的重叠（比如：有些字体的Tj就会出现重叠），投影以后也不好切割，从而造成切割的时候出错。就是这一点，使得我们的垂直切割比水平切割更难。


因此我在处理的时候，做了一些特殊的工作。老王先计算一下，这一行的所有字符大体的平均宽度，按道理，这一行的字符都该差不多宽（也有个别例外，但是按照2-8定律，我们处理好大多数的情况，有利于我们简化问题的复杂度）。这样，如果粘连的话，我们按照平均宽度的一个范围，就大体上可以将他们在某一个薄弱的地方切割开。


那这些特殊的工作是怎么做的呢？别急，待老王慢慢道来。


首先，我们可以看到绝大多数情况，字符还是基本独立的。所以先把能连接的点，先连接起来，形成独立的字符区块。如果即使有粘连，也没关系，我们留到后面来处理。要求位图连通区块，有很多算法，我们这里就再次用到bfs（这些经典的算法真是屡试不爽），将图的连通。比如：



这个图用bfs就可以跑出两个大的连通区块，左边r部分和右边e的部分。


是不是做完这一步就好了呢？当然不是。有一些字符还要做上下连通区域的合并。比如：



大家可以看到类似i、j这种字符，他们是分成上下两个部分的，如果我们要识别他们，肯定是不能将他们拆分开的。而bfs算法又没办法将他们连通起来，怎么办呢？

我们将bfs产生出来的所有区块往x轴上投影，如果出现上下重叠覆盖较多的情况，我们就将他们做合并形成一个新的合并后的区块，认为他们就是连通的。


有了这样一个个的区块，我们就很好处理了。接着，我们把这些区块算取他们的平均宽度。如果有些区块宽度特别宽，比如超出平均宽度2-3倍，我们认为有可能是两个或者多个字符粘连在一起（比如有些字体的rm这两个单词就很容易拍照出来形成粘连），就可以在最薄弱的地方将他们切开，形成两个或多个独立的区块；而有一些连续的区块，每一个的宽度都特别小（只有平均宽度的几分之一），并且他们的间隔也特别小（平均间隔的几分之一），我们就认为有可能他们原先是一个字符，但是在去噪的过程中被分开了（比如经常看到h、n这样的字符，中间的那一块特别薄，在拍的不是很清楚的情况下，去噪的时候被去掉了），我们就把这些区块合并成一个区块。


切分&合并完以后，我们一个个独立的区块，就是我们想要的一个个待识别的字符图案了。前面做了这么多的工作，就是为了得到他们。


怎么样，老王说的还清楚嘛？

接下来的工作，就是对这些一个个独立的图案区块做识别。



################################   下半部分  ########################################

 

 

====图像的识别 ====



我们已经拿到一个个的字符的图案了，现在要做的，就是如何把这些图案转化成计算机可认知的二进制编码。因为这次只涉及到英文和标点，所以实际要做的，就是将图案转化为asc码。

 



识别的方法有非常多，接下来我给大家介绍一下我用的几种方法。为了使得识别率提升，一般还会有其他更好或者更有效的方法，如果这里没讲述到，请大家谅解~



对于每一个待识别的字符图案，都有他自己的特征（比如：i长的很瘦，O长的很圆，T横竖都有等等），识别的时候，就可以借助他们的特征，从而抽丝剥茧的把他们认出来。


问：那具体怎么做呢？


答：我们将多种字体的所有英文和标点生成标准图案，再将待识别的图案和他们进行比对，看这些待匹配的图案和哪个标准图案最像，那就能找出最有可能的asc码。 


那就开始吧！

 

步骤一：生成模板图案


我们用多种常见字体，将所有英文和标点生成标准图案。这里简称模板图案。为什么要多种字体呢？因为对于同一个字符，在不同字体下，可能长的完全不一样，比如同样是gal，不同字体效果如下：



拿到这些标准模板图案以后，我们就有了如下图的这些位图：


但是有了这些位图还不够，我们还要做一些其他工作，来保证后面的匹配工作能正常进行。接下来我们就看看还要做什么工作。



步骤二：归一化 +记录meta信息


我们将模板图案先去掉上下左右空白的背景，让前景图案顶格。接着再统一宽高，将图案压缩或拉伸为p*q大小的图案（比如都压缩或者拉伸到50像素*50像素），这样我们才能很好比对。说白了，就是大家都用统一的标准，否则你穿XL号的衣服，我穿S号的，我们的衣服就根本没有可比性。


好了，有了统一的比对标准，是不是一切就都好了呢？


大家一看这种问题，基本就可以条件反射的判定：回答是否定的（就跟读书那会儿做判断题一样^_^）。那问题出在哪儿呢？


有些图案做了归一化以后，就失真了，比如逗号[,]和引号[’]，去掉周围的白边，最后就都长成如下图像了：





还有一些字符就会长的很像了，比如大写的Z和小写的z，归一化以后，就变成如下这样了，人看都恼火，让计算机怎么来判断，对吧。


所以，除了归一化，我们还要记录图案本身的信息，比如原始的长宽，原始的位图等等，这些信息在匹配的时候，可以提供额外的信息，来帮助算法判断有效性。


好了，做完上面两步，我们就得到了标准图案的归一化位图和meta信息。同时，我们对上一篇文章中做完垂直切割的待匹配图案也做归一化和meta信息记录的工作。有了这两样东西，我们就可以开展下面的匹配工作了。


步骤三：模板图案和待匹配图案的匹配


接下来，就用我们的匹配算法，对待匹配的图案和标准图案进行匹配了。图像的识别算法有很多很多，根据不同的应用场景，会有很多不同的选择，包括直接匹配的，也有通过数据挖掘来识别。每一种方法没有绝对的好坏，只有看是否更适合。


我曾经看过一篇文章，是讲验证码识别的。验证码为了防止机器识别，会对字符进行旋转、扭曲、干扰等处理。为了识别这些变态的字符，那篇文章列举了多达10几种的识别算法，当时看得我不断的惊叹：我擦……。如果以后有时间，我尝试看看能不能把那篇文章找出来分享给大家。


我们这里因为只涉及到英文和标点，所以用了以下几种方法:


1、字符像素匹配


2、投影区块匹配


3、九宫格匹配


4、重心匹配


5、宽高比匹配


每一个匹配算法都有自身的优缺点（稍后会讲到），因此他们都能得出一个谁跟谁最像，待匹配图案是谁的可能性最大的判断。虽然这个判断绝大多数情况下是对的，但是也有bad case的情况。所以，我们要综合来看所有的判断，将每一个算法的匹配值进行加权求和，得出最后的一个相似度的值，这个相似度有可能就是最终的一个结果。不过这个结果可能也是有错误的（bad case），所以如果继续往后做的时候，我们要不断去给我们的评价判断系统以反馈，丰富我们识别的样本，同时对识别算法和加权参数进行修正（这个会比较花时间，我这次就没做了^_^）


通过上面的算法，我们就将待匹配的图案和每一个标准图案进行算法比对的相似度值求出来，做个排序，取相似度最大的那个，基本就得到我们最终想要的那个。


后来出于好奇，我专门问了作业帮的朋友，想看看他们怎么做的。大体方法类似，同时他们还用了其他的一些手段，比如：卷积神经网络(CNN)等。后面有时间了，我再专门去研究研究。


好了，大体上的步骤，老王是不是都讲清楚了呢？接下来，就是具体讲讲这几个匹配算法，做完这几个算法，我们的识别工作就基本告一段落。来吧，跟着老王一起往下看。

方法一：字符像素匹配


这是最直观也最容易想到的方法。我们将待匹配图案和标准的每一个图案进行一个像素一个像素的比对，如果位图都是0或者都是1，则计数加一，最终得到计数数值k。用k除以像素个数w * h就得到了一个相似值 d = k / (w * h)。如果d越大，则相似度越高（为了描述起来容易些，后面我都用一些简单的位图来做示意）：


模板图案：


待匹配图案：



我们的模板图案和待匹配图案都被归一化到10*10的尺寸，他们有99个点是重合的，有一个点不重合：(0,0)那个点。这样的话，他们的相似度就是d = 99 / 100 = 99%。


理想情况下，如果所有点都匹配的话，他们的就会有100点重合，那d = 100 / 100 = 100%。另外一个极端，就是一个点都不重合，那么d = 0 / 100 = 0%，对吧。所以，我们这个算法的值域就是[0,1]。对于99%的相似度，我们认为已经很高了，所以他俩匹配的可能性就非常高。

 

如此这样，我们将待匹配的图案和模板图案一一计算，得到d1 d2 ... dn这样一个结果序列，降序排列的第一个，就是这个算法认为最有可能的图案。


这个算法直观，实现简单，不过这个算法有一个问题：就是待匹配图案如果稍微有一些偏差或者干扰，对算法本身的影响就会非常大。比如，我们在图像处理的时候，某一行里多了一个干扰点，就有可能造成这一行的匹配度下降。如下图：



我们在图像处理的时候，最后一行多了一个噪点，然后做图像归一化以后，整个图像的最右边就往左边挤占了一个像素，这样和模板图案进行算法对比的时候，匹配值就变成了90，整个匹配度就变成d = 90 / 100 = 90%。


因此，这个算法对图像准确度要求很高，抗干扰能力弱。不过，在图像处理比较好的绝大多数情况下，他的匹配度还是不错的。

方法二：投影区块匹配


上一种方法就是对图像的信息太过敏感，稍微一点干扰就会造成影响。所以，我们有一个新的方法，将信息做汇聚，然后再比较信息的相似性。


我们将图像在x轴上做投影，累加位图为1的值。然后再将x轴等分成n份（比如n=5），分别将这等分的n份里所有的值累加，得到k1 k2 ... kn，然后将标准图案和待匹配图案的这n个k值进行求差。差值越小，则相似度越高。同理，在y轴也做同样的投影和求差值。


我们还是对这个10 * 10的位图进行分析，将这个位图分别往x、y轴上投影。将位图中为1的累加，因此得到在x轴上的10个数字和y轴上的10个数字，如下：



模板图案：


待匹配图案1：



待匹配图案2：



然后我们把x轴和y轴上的数字，分别分成连续的5组（每两个一组），组内的数字累加:


模板图案：


x轴：(8 8) (66) (6 6) (6 6) (8 8) -> 16 12 12 12 16


y轴：(10 10) (22) (10 10) (2 2) (10 10) -> 20 4 20 4 20


我们将上面的值命名为：


x0[1] x0[2] ... x0[5] = 16 12 12 12 16


y0[1] y0[2] ... y0[5] = 20 4 20 4 20


待匹配图案1：


x轴：(7 8) (66) (6 6) (6 6) (8 8) -> 15 12 12 12 16


y轴：(9 10) (22) (10 10) (2 2) (10 10) -> 19 4 20 4 20


我们将上面的值命名为：


x1[1] x1[2] ... x1[5] = 15 12 12 12 16


y1[1] y1[2] ... y1[5] = 19 4 20 4 20


待匹配图案2：


x轴：(7 8) (66) (6 6) (6 8) (8 1) -> 15 12 12 14 9


y轴：(8 9) (22) (9 9) (2 2) (9 10) -> 17 4 18 4 19


x2[1] x2[2] ... x2[5] = 15 12 12 14 9


y2[1] y2[2] ... y2[5] = 17 4 18 4 19


然后，我们将对应的值做以下操作：


待匹配图案1和标准图案对比：


a、dx1 =∑((x1[i] - x0[i]) / 20) ^ 2 = 0.0025


b、dy1 =∑((y1[i] - y0[i]) / 20) ^ 2 = 0.0025


c、d1  = 1 - (dx1 + dy1) / 2 = 99.75%


（其中i=1到5, 20是每一组点的个数）


待匹配图案2和标准图案对比：


a、dx2 =∑((x2[i] - x0[i]) / 20) ^ 2 = 0.1325


b、dy2 =∑((y2[i] - y0[i]) / 20) ^ 2 = 0.035


c、d2  = 1 - (dx2 + dy2) / 2 = 91.6%


从绝对差值来看，这种方案要比前一种对于图像的敏感度要小，特别是如果每组的个数更多的时候，这种敏感度就越弱。


这个算法主要是在做图像有效信息分布的比对，信息相对要粗放一些，抗干扰度要好一些。不过但是带来的问题，就是信息是统计信息，比较粗，有些图案比对会不准确，比如：a和o等

方法三：九宫格匹配


我们将图案划分成3*3的格子，然后在每个格子里统计位图值为1的个数，得到k1 k2 ... k9一共9个值。然后再将标准图案和待匹配图案对k值求差，差值越小，则相似度越高。


这个算法类似上一种，不同的是，他将x轴和y轴的信息做了汇聚。鉴于计算方法类似，我们这里就不再赘述。

方法四：重心匹配


还记得我们之前说的一个case吗？逗号[,]和引号[’]其实除了位置不一样以外，其实长的非常像。我最先做匹配的时候，匹配出来的结果就是要么都是逗号，要么都是引号。类似的还有横线[-]和下划线[_]等。那我们要做的，其实就可以计算位图中1值的重心在x方向和y方向的分布，一比对就可以轻松的判别了。比如逗号的重心在y轴上的分布是更下面一些，而引号则是更上面一些。


具体重心的计算方式有很多，最简单的就是：


x轴：将每个1点的x坐标分别相加，然后除以1点的个数，再除以宽度做归一化；


y轴：将每个1点的y坐标分别相加，然后除以1点的个数，再除以高度做归一化。

 

 

for (int x = 0; x < width; x++)
{
	for (int y = 0; y < height; y++)
	{
		if (data[x][y] == 1)
		{
		yValue += y;
		count++;
		}
	}
}
double
avg = count > 0 ? yValue / count : 0;
avg = avg / height;

方法五：宽高比匹配


为什么要做这样一个匹配呢？我们先看一个case：


1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1


请问，这个10*10的图案，是什么字符？


这可能是一个句号[.]，也可能是一个竖线[|]，还有可能是某些字体的逗号[,]。因为在做归一化的时候，都变成了一个全是1的图案。而逗号和句号的重心有可能还差不多。这个时候，我们就可以用原始信息中的宽高比来做比对。比如，句号[.]的宽高比接近1:1，竖线[|]的宽高比可能是1:20，逗号[,]的宽高比可能是1:2等等。有了这个判断，就可以将相似的这些图案区分开来了。


通过以上几种算法，我们就会拿到每个算法计算出来的每个待识别图案和标准图案的相似值。对于每个待识别图案，我们将每个算法的相似值做一个加权合并，就得到了最终的相似度值，从而来确定这个待识别的图案和哪个标准图案最相似，找出最有可能的asc码值。


好了，最后我们再来看看文章开始的时候，给大家展示的效果：


最后识别出来以后，没有做任何的单词校正工作：


===================================

Three months after [he government stopped issulng (&%) or renewing permits for In[ernet cafes because of security (%#) concerns, some cafe owners are having flnanclal

 (ff%%) concerns of their own.

===================================

大家肉眼看，识别率还是不错的。不过有一些字符比如(I、l、i)、(t、[)等这些字符组内的图案特别容易识别错误。为了解决这些问题，可以加入单词的校正算法。常用的LCS（最长公共子序列）或者BKTree等等。因为需要做全字典匹配，所以，BKTree的效率会更好一些。（这些基础算法就暂时不在这里细讲，有兴趣的同学可以查阅baidu）

 

 

 

 

 

有了纠错算法，基本能很好的将图案识别出来。

 

====总结 ====

以上只是一个基本的拍照识图的算法，除了上述说的这些方法，其实在实际应用中，还会对数据做反馈训练。比如有些字符会引发错误，我们会将这些图案反馈给系统，下次遇到类似的图案的时候，系统就会匹配到更精准的信息。同时，对于参数的调整，也可以引入反馈和修正。


而如果要加入中文的话，整个难度和复杂度还会提升不少，使用的方法可能都还有不一样。鉴于这次调研的时间，老王同志就没有再做深入的研究了。再等一段时间，老王可能会把这个做的更深入细致。这次就先到这里吧~ ^o^