基于公式库的公式识别方法及装置

摘要

本发明提供一种基于公式库的公式识别方法及装置，该公式识别方法包括：基于公式库，构建公式库中每个公式的部件；进而构建部件集；为所述部件集中的每个部件设置编码形成部件编码集，提取所述部件编码集中每个编码对应的部件特征，进而构建与所述部件编码集相对应的部件特征集；对待识别公式图像进行处理，获得部件子图；对部件子图提取部件特征，通过将单个部件子图的部件特征和部件特征集进行比对，获得单个部件子图的多候选识别结果，进而获得所述待识别公式图像的公式识别结果。

说明书

技术领域

本发明涉及一种公式识别方法及装置，特别涉及一种基于公式库的公式识别方法 及装置，可以用于例如在线教育领域。

背景技术

随着在线教育技术的发展，提供简捷快速的答疑解惑服务成为该技术发展的一项 重要业务，目前主流的市场应用为拍照题目搜索，即基于对题目拍照后形成的图像中的文 字、公式的识别结果进行搜索。在当前的教学科目中，数学是中小学的重要课程，公式是数 学题目中最主要的一种表达形式，因此，公式识别是决定题目搜索性能的一项最主要的核 心技术。

传统的公式识别技术主要应用于对图像或手写体公式的解析识别，该公式识别方 法的主要原理是先从图像中分割出单个字符，再对单个字符进行识别，最后对字符与字符 之间的结构关系进行分析，最终完成对公式的识别理解。因此，这种传统的公式识别技术受 图像质量和手写体书写习惯的影响较大，而且，需要对构成公式的各个字符之间进行结构 分析，识别过程较为繁琐，识别时间较长，识别效率也低，无法很好地应用到拍照题目搜索。

发明内容

拍照题目搜索的前提是必须有一个数量庞大、不断更新的题目、答案和解析数据 库，因此，相当于在拍照题目搜索情况下进行的公式识别预先建立了一个特定的公式库。本 发明提供了一种基于上述特定的公式库的公式识别方法及装置，该公式识别方法基于特定 的公式库来构建每个公式的部件，建立公式库的部件集，将公式作为部件集中的部件按照 先后顺序进行水平方向组合而成。

根据本发明的一方面，本发明实施例提供一种基于公式库的公式识别方法，所述 公式识别方法包括：

构建公式库中每个公式的部件；其中，所述部件包括第一等级符号和子公式，所述第一 等级符号为所述每个公式的起始符号和与该起始符号在结构关系上为水平关系的同等级 符号，所述子公式为以第一等级符号为基准衍生的所有等级低于所述第一等级符号的次等 级符号和所述第一等级符号组成的公式；

根据构建的所述每个公式的部件，建立公式库的部件集；

为所述部件集中的每个部件设置编码形成部件编码集，提取所述部件编码集中每个编 码对应的部件特征，进而构建与所述部件编码集相对应的部件特征集；

获取待识别公式图像的部件子图，其中，每个所述部件子图包含一个部件；

获取所述待识别公式图像中每个所述部件子图的部件特征，将每个所述部件子图的部 件特征与所述部件特征集进行比对，获得每个所述部件子图的多候选识别结果，进而获得 所述待识别公式图像的公式识别结果。

所述起始符号为公式最左侧等级最高且基准符号为符号本身的符号，所述基准符 号为公式中每个符号的结构基准。

所述构建公式库中每个公式的部件包括：

获取公式库中每个公式的所有第一等级符号t₀,t₁,t₂,……t_n；其中，以所述起始符号 t₀为基准符号逐一递进式获取与所述起始符号结构关系为水平关系的右侧符号，将所述起 始符号与所述右侧符号作为第一等级符号t₀,t₁,t₂,……t_n;

分别以每个公式的所述第一等级符号t₀,t₁,t₂,……t_n为基准符号获取次等级符号，将 无次等级符号的第一等级符号作为部件，将存在次等级符号的第一等级符号与该第一等级 符号的次等级符号组成的子公式作为部件。

所述为所述部件集中的每个部件设置编码形成部件编码集，包括：对所述部件集 中的部件进行去重操作，为去重后的所述部件集中的每个部件设置编码形成部件编码集。

所述部件特征包括部件纹理特征和边缘特征。

所述获取待识别公式图像的部件子图，包括：

对所述待识别公式图像进行水平方向投影切分，获得所述待识别公式图像的一级子图 序列；

获取所述一级子图序列中相邻一级子图的相邻边界的平均距离作为第一参考值，获取 所述一级子图序列中所有一级子图宽度的平均值作为第二参考值；

对所述一级子图序列中的各个一级子图进行连通域分割，分割成功后获得所述待识别 公式图像的二级子图序列，并根据所述二级子图序列中的相邻二级子图之间的空间位置关 系进行合并获得所述待识别公式图像的三级子图序列；

对所述三级子图序列中的每个三级子图和进行连通域分割后未获成功的一级子图分 别进行单字符识别，结合所述第一参考值和第二参考值，确定部件子图。

所述对所述三级子图序列每个三级子图进行单字符识别，确定部件子图包括：

对所述三级子图序列中的每个三级子图分别进行单字符识别获得所述每个三级子图 的识别结果及相应的识别可信度；

根据所述单字符识别判断所述识别结果中存在的第一等级符号的类型及相应的识别 可信度并根据该判断结果确定部件子图。

所述根据所述单字符识别判断所述识别结果中存在的第一等级符号的类型及相 应的识别可信度并根据该判断结果确定部件子图包括：

若所述三级子图序列中存在识别结果为分式且识别可信度高于第一预设值的三级子 图，且所述三级子图的宽度接近所述三级子图对应的一级子图的宽度，所述三级子图的宽 度大于所述第一参考值和第二参考值，则将所述三级子图对应的一级子图作为分式类型的 部件子图；

若所述三级子图序列中存在识别结果为根式且识别可信度高于所述第一预设值的三 级子图，且所述三级子图的高度接近所述三级子图对应的一级子图的高度，所述三级子图 的高度大于所述第一参考值和第二参考值，则将所述三级子图对应的一级子图作为根式类 型的部件子图。

所述对所述进行连通域分割后未获成功的一级子图进行单字符识别，确定部件子 图包括：

对所述进行连通域分割后未获成功的一级子图进行单字符识别后的识别结果及识别 可信度进行判断，若该识别结果为公式符号且识别可信度高于所述第一预设值，且所述一 级子图与水平方向的相邻一级子图的距离接近所述第一参考值，则将所述一级子图作为公 式符号类型的部件子图。

该方法还包括，根据对所述三级子图序列中每个三级子图和进行连通域分割后未 获成功的一级子图进行单字符识别后无法确定部件子图时，将所有不能确定为部件子图的 三级子图和一级子图重新标记为新的子图序列，通过动态规划获得所述重新标记的新的子 图序列的最优组合子图序列，将所述最优组合子图序列中的每个子图作为部件子图。

所述获取所述待识别公式图像中每个所述部件子图的部件特征，将每个所述部件 子图的部件特征与所述部件特征集进行比对，获得每个所述部件子图的多候选识别结果包 括：

对所述待识别公式图像中的每个部件子图进行归一化处理；

提取进行归一化处理后的每个所述部件子图的纹理特征和边缘特征，形成每个所述部 件子图的部件特征；

将单个部件子图的部件特征与所述部件特征集中的部件特征进行比对，获得所述单个 部件子图的部件特征与所述部件特征集中各特征之间的相似度；

将所述相似度从大到小进行排序，选取前M个相似度对应的M个部件特征，并将所述M个 部件特征对应的部件编码作为所述单个部件子图的多候选识别结果。

所述获得所述待识别公式图像的公式识别结果包括：

若所述待识别公式图像只包括一个部件子图，在所述多候选识别结果中选取相似度最 大的部件特征对应的部件编码作为公式识别结果；

若所述待识别公式图像包括多个部件子图，将所述待识别公式图像的每个部件子图的 多候选识别结果作为基本单位，采用动态规划的方法，结合概率统计语言模型对每个候选 的公式识别结果进行评分、排序，将得分最高的部件特征对应的部件编码作为公式识别结 果。

所述公式识别装置包括：

构建部件模块，其用于构建所述公式库中每个公式的部件，其中，所述部件包括第一等 级符号和子公式，所述第一等级符号为所述每个公式的起始符号和与该起始符号在结构关 系上为水平关系的同等级符号，所述子公式为以第一等级符号为基准衍生的所有等级低于 所述第一等级符号的次等级符号和所述第一等级符号组成的公式；

建立部件集模块，其根据构建的所述每个公式的部件，建立公式的部件集；

构建部件编码集和部件特征集模块，其用于对所述部件集中的每个部件设置编码形成 部件编码集，提取所述部件编码集中每个编码对应的部件的特征，进而构建与所述部件编 码集相对应的部件特征集；

获取部件子图模块，其用于对待识别公式图像进行处理，获得所述待识别公式图像的 部件子图，其中，每个所述部件子图包含一个部件；

公式识别模块，其用于获取所述待识别公式图像中每个所述部件子图的部件特征，将 每个所述部件子图的部件特征与所述部件特征集进行比对，获得每个所述部件子图的较优 识别结果，进而获得所述待识别公式图像的公式识别结果。

与传统的公式识别方法相比，本发明所述识别方法以预先建立的公式库为基础， 该识别方法可以充分利用公式库来校准和优化识别结果，同时，该识别方法将复杂类型的 子公式转换成一个新的字符，一个公式就被当成一个或者多个复杂类型子公式和单个传统 字符的水平方向组合。通过本发明所述的公式识别方法及装置，不需要进行字符之间的结 构分析，简化了公式识别的步骤，节省公式识别的时间，提高了公式识别的准确率。

以下结合本发明的附图及优选实施方式对本发明的技术方案做进一步详细地描 述，本发明的有益效果将进一步明确。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本发明的一部分，但其 说明仅用于解释本发明，并不构成对本发明的不当限定。

图1是根据本发明一优选实施例的公式识别方法的流程图；

图2是根据本发明一优选实施例的获取待识别公式图像的部件子图的流程图。

图3是根据本发明一优选实施例的公式识别装置的框图。

具体实施方式

下面将结合本发明的具体实施例及相应的附图对本发明技术方案进行清楚、完整 地描述。显然，所描述的实施例仅是本发明一部分优选实施例，而不是全部的实施例。基于 本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他 实施例，都属于本发明保护的范围。

此处首先定义本发明涉及的公式中的起始符号、基准符号、第一等级符号、次等级 符号及子公式等的含义。公式是由传统的字符集中的字符组成的，公式中的每个公式字符 都有一个基准符号，该基准符号是每个公式字符的结构基准。

公式中每个公式字符与其对应的基准符号之间的结构关系包括水平关系、分式上 下标关系、根号根指数关系、根号根号内关系、矩阵关系、上下角标关系等。其中水平关系是 只考虑水平右侧关系，即若存在两个水平关系的符号，则认为左侧的符号为右侧符号的基 准符号。如果公式字符与基准符号之间的结构关系为水平关系，则认为公式字符与基准符 号为同一等级的符号，而对于其它结构关系，可以认为该公式字符比基准符号的等级低一 级，即定义为次等级符号。

每一个公式都有且仅有一个起始符号，起始符号是公式最左侧的等级最高的符 号，起始符号的基准符号就是其本身。公式中所有与起始符号结构关系为水平关系的符号 为第一等级符号。某个公式字符的基准符号和结构关系共同决定该字符在公式中的唯一顺 序和结构特征。以某第一等级符号为基准衍生出的所有低于其等级的次等级符号与某第一 等级符号组成的公式，称为以某第一等级符号为基准符号的子公式。

例如，公式“”中公式字符“a”、“b”、“c”的基准符号分别为“根式（）”、 “a”、“b”，结构关系分别为根号根号内关系、水平关系、水平关系。最左侧的等级最高的符号 为根式，因此起始符号为根式。

再如，对于公式Ⅰ“”。首先找到起始符号，起始符号是最左侧的等 级最高的符号，在该公式I中最左侧是一个分式结构的复杂类型公式，因此其最高等级的符 号为“分式—”，因此“分式—”也就是该公式的起始符号。紧接着分式的水平右侧符号为 “+”，"+"的水平右侧符号为“a”，“a”的水平右侧符号为“+”，“+”的水平右侧符号为“分 式—”，所以，上述“分式—”、“+”、“a”、“+”、“分式—”为公式I的第一等级符号。并且，该公式 Ⅰ包含两个子公式“”和“”，其中子公式“”是由第一个“分式—”为基 准符号衍生出的子公式，“”是由第二个“分式—”为基准符号衍生出的子公式。

再分析公式Ⅰ中的两个子公式“”和“”的结构关系。在子公式“ ”中，以“基准符号-结构关系-公式字符”的方式来描述该子公式中各个公式字符 之间的结构关系，具体如下：分式-分式上标-b，b-水平-+，+-水平-根式，根式-根式根号 内-b，b-右上角标-2，b-水平-4，4-水平-a，分式-分式下标-2，2-水平-a。例如上文中“分式- 分式上标-b”的含义为基准符号为“分式”，公式字符为“b”，两者之间关系为“分式上标”，其 余表示方法与此同理。公式“”与前述公式同理。本发明下文对部件的定义基于上述对公 式中字符的定义。

下面结合图1说明根据本发明的一优选实施例的公式识别方法的具体步骤。

图1是根据本发明的一优选实施例的公式识别方法的流程图。如图1所示，根据本 发明的优选实施例的公式识别方法的具体步骤如下。

步骤S1：构建公式库中每个公式的部件。

每个公式的部件包括第一等级符号和子公式。第一等级符号为每个公式的起始符 号和与该起始符号在结构关系上为水平关系的同等级符号。子公式为以第一等级符号为基 准衍生的所有等级低于该第一等级符号的次等级符号和该第一等级符号组成的公式。

步骤S2：根据构建的所述每个公式的部件，建立公式库的部件集。

对公式库中的每个公式通过步骤S1所述的方法，构建每个公式的部件，从而建立 公式库的部件集。

步骤S3：为部件集中的每个部件设置编码形成部件编码集，提取所述部件编码集 中每个编码对应的部件特征，进而构建与所述部件编码集相对应的部件特征集。

该步骤中，对部件集中的部件进行去重操作，为去重后的部件集中的每个部件设 置编码形成部件编码集。部件特征包括部件纹理特征和边缘特征。提取部件编码集中每个 编码对应的纹理特征和边缘特征后构建与部件编码集相对应的部件特征集。

步骤S4：获取待识别公式图像的部件子图，其中，每个所述部件子图包含一个部 件。

该步骤中，需要对待识别公式图像进行水平方向投影切分，获得所述待识别公式 图像的一级子图序列。获取所述一级子图序列中相邻一级子图的相邻边界的平均距离作为 第一参考值，获取所述一级子图序列中所有一级子图宽度的平均值作为第二参考值。对所 述一级子图序列进行连通域分割，分割成功后获得所述待识别公式图像的二级子图序列， 并根据所述二级子图序列中的相邻二级子图之间的空间位置关系进行合并获得所述待识 别公式图像的三级子图序列。对所述三级子图序列和进行连通域分割后未获成功的一级子 图序列分别进行单字符识别，结合所述第一参考值和第二参考值，确定部件子图。

步骤S5：获取每个部件子图的部件特征，通过与部件特征集比对，实现公式识别。

该步骤中，获取所述待识别公式图像中每个所述部件子图的部件特征，将每个所 述部件子图的部件特征与所述部件特征集进行比对，获得每个所述部件子图的多候选识别 结果，进而获得所述待识别公式图像的公式识别结果。

以下详述上述步骤的实现方法。

对于步骤S1：构建公式库中每个公式的部件。首先，获取公式库中的每个公式的第 一等级符号。该过程中首先要获取公式的起始符号t₀，起始符号t₀的获取规则为，获取公式 最左侧等级最高且基准符号为符号本身的符号。然后，以起始符号t₀为基准符号，获取与其 结构关系为水平关系的右侧符号t₁，以此类推，分别获取以t_n-1为基准符号，结构关系为水 平关系的右侧符号t_n，从而，完成对公式中所有第一等级符号t₀,t₁,t₂,……t_n的采集。

获取第一等级的符号后，分别以每个公式的第一等级符号t₀,t₁,t₂,……t_n为基准 符号获取次等级符号。

若公式中以某一第一等级符号为基准，没有次等级符号，则定义该第一等级符号 即为部件；若以某一第一等级符号为基准，存在次等级符号，则以某一第一等级符号和其次 等级符号组成的公式为子公式，该子公式为部件。至此，完成对公式库中每个公式的部件采 集。

以前述的公式Ⅰ“”为示例。首先获取起始符号“—（分号）”（）， 然后以起始符号为基准符号，获取与其结构关系为水平关系的右侧符号“+”（），依次类 推，获取以“+”（）为基准符号，结构关系为水平关系的右侧符号“—（分号）”（），从而， 获取该公式中所有的第一等级符号“—（分号）”（）、“+”（）、“a”（）、“+”（）和“— （分号）”（）。最后，分别以和为基准符号，获取所有次等级符号，从而，得到和 的子公式“”和“”，即，整个公式可以拆分出“”、“”两个子 公式和“+”（）、“a”（）、“+”（）三个第一等级符号，作为该公式的五个部件。对于公式 库中的其它公式，通过上述步骤构建每个公式的部件。

对于步骤S3中设置部件编码集。首先，对部件集中的所有部件做去重操作；然后， 将部件集中的所有部件设置编码，使得部件与编码一一对应，从而形成部件编码集。例如， 将公式Ⅰ“”中的五个部件首先做去重操作，去掉一个重复的“+”，从而得 到“”、“+”、“a”、和“”四个部件，然后，对这四个部件分别编码为0、1、2、3，则编 码为0的部件即为“”，编码为1的部件即为“+”，编码为2的部件为“a”，编码为3的 部件为“”。这样，公式Ⅰ就转换为01213的编码形式。

接着，对部件编码集中每个部件进行部件特征提取，获得每个部件对应的部件纹 理特征和边缘特征，构成与部件编码集相对应的部件特征集，将其用于在稍后描述的识别 过程中，以识别图像中的公式。

对于部件纹理特征的提取，一幅图像的纹理是在图像计算中经过量化的图像特 征。图像纹理描述图像或其中小块区域的空间颜色分布和光强分布。本实施例采用如下步 骤提取纹理特征。

①首先将图像划分为16×16的小区域（cell），对每个cell的一个像素，将其环形 邻域内的8个邻点进行顺时针或逆时针的比较，如果中心像素值比该邻点大，则将邻点赋值 为1，否则赋值为0，这样每个点都会获得一个8位二进制数（通常转换为十进制数）。

②然后计算每个cell的直方图，即每个数字（假定是十进制数）出现的频率（即，对 每一个像素点是否比邻域内点大的一个二进制序列进行统计），然后对该直方图进行归一 化处理。

③最后将得到的每个cell的统计直方图进行连接，从而得到整幅图的纹理特征。

对于部件边缘特征的提取。本实施例采用canny边缘检测算法提取部件边缘特征。 具体过程为：对原始图像进行高斯平滑去噪；求梯度值；梯度幅度值判定；初步确定图像边 缘点；精确定位边缘位置；最后输出一二值化图像。进行边缘检测的目的是为了找到图像中 亮度变化剧烈的像素点构成的集合，该集合所表现出来的往往是轮廓。理想情况下，对所给 图像应用边缘检测器可以得到一系列连续的曲线，用于表示该图像中的边界。因此通过边 缘检测所得到的结果能够大大减少图像数据量，过滤掉不需要的信息，留下图像的重要结 构，从而大大简化了处理。

步骤S4，参考图2，获取待识别公式图像的部件子图包括如下方法：

步骤S401：对待识别公式图像进行水平方向投影切分。

对待识别的公式图像进行水平方向投影切分，首先对待识别的公式图像进行二值 化处理，然后统计每一列非零像素值的个数并用数组Col[w]存储，最后对数组Col[w]进行 遍历，其中数组Col[w]的零值与非零值的交界处即为切分点。

通过上述切分点的确定，获得了该公式图像的一级子图序列{s₀，s₁，s₂，……s_n}, 由于该水平方向投影切分的结果受切分精度、图像清晰度等因素的影响，导致该一级子图 序列中的每个子图s_i存在三种可能性：①s_i是某一个部件的完整图；②s_i是某一个部件的 一部分;③s_i是两个或者多个部件组合成的。

由于存在不是期望获得的部件子图的可能性②和③的s_i，因此需要进行步骤S402 进一步处理，以获得期望的部件子图。

此外，对获取的一级子图序列{s₀，s₁，s₂，……s_n}进行计算。计算相邻的一级子图s_n-1的 右边界与一级子图s_n的左边界的距离d_n（d_n﹥0），对计算得到的d_n进行平均值计算，获得d_n的 平均值，将定义为第一参考值。

然后，获取一级子图序列中的所有一级子图s₀，s₁，s₃，……s_n的宽度分别为d_w0，d_w1， d_w2，……d_wn，计算所有一级子图的宽度的平均值，使得，将定义为第二参 考值。

步骤S402：对所述一级子图序列进行连通域分割。

对一级子图序列中的每一个子图进行连通域分割，使 每一个一级子图被分割为m个二级子图序列。由于通过连通域 分割而得到的二级子图比较零碎，因此，需要根据二级子图之间的空间位置关系进行合并 处理。具体合并过程如下：

首先，计算二级子图序列中每一个二级子图（0≤j≤m） 的矩形框Rect（）。

然后，对计算得到的m个矩形框进行遍历，若任意两个矩形框之间同时存在水平和 垂直方向的重叠，则将这两个二级子图进行合并，作为一个新的三级子图。

重复上述过程，直到没有二级子图能够进行合并为止，最终得到k（k≤m）个连通域 分割三级子图序列。

步骤S403：对三级子图序列中的每个三级子图和连通域分割未获成功的一级子图 进行单字符识别。

对连通域分割成功的三级子图序列中的每个三级子 图和进行连通域分割后未获成功的一级子图进行单字符识别，然后获取每个三级子图和每个进行连通域分割后未获成功的一级子图的识别结果及其对应的识别可信度。

具体地，对所述三级子图序列中的每个三级子图分别进行单字符识别获得所述每 个三级子图的识别结果及相应的识别可信度；根据单字符识别判断所述识别结果中存在的 第一等级符号的类型及相应的识别可信度并结合第一参考值和第二参考值确定部件子图。 通过上述方式，可以确定以下两种类型的部件子图：

①若该三级子图序列中存在识别结果为分式且识别可信度高于第一预设值的三级子 图，三级子图的宽度接近其对应的一级子图的宽度，且三级子图的宽度大于 第一参考值和第二参考值，即，的宽度与高度比值很大，则认为所述一级子图为分式类型的部件子图，不需要做进一步的处理。即，特别的，第一预设值为80%-100%之间 的任一数值。

②若该三级子图序列中存在识别结果为根式且识别可信度高于所述第一预设值 的三级子图，三级子图的高度接近与其对应的一级子图的高度，且三级子图的 高度大于第一参考值和第二参考值，的宽度与高度比值很小，则认为所述一级子 图为根式类型的部件子图，不需要做进一步的处理。

对连通域分割后未获成功的一级子图进行单字符识别，根据识别结果及其对应的 识别可信度，并结合第一参考值确定部件子图，具体为：

针对进行连通域分割后未获成功的一级子图进行单字符识别，若识别结果为公式 符号且识别可信度高于所述第一预设值，同时该一级子图与水平方向的相邻一级子图的 距离接近第一参考值，则认为所述一级子图为公式符号类型的部件子图，不需要做进一 步的处理。

其中，参照图2，对三级子图序列中的每个三级子图和连通域分割未获成功的一级 子图进行单字符识别，并确定部件子图，在时序上不分先后。即，可以先对三级子图序列中 的每个三级子图进行单字符识别确定分式和根式类型的部件子图，也可以先对连通域分割 未获成功的一级子图进行单字符识别确定公式符号类型的部件子图；还可以同时进行。

步骤S404：对不能确定为部件子图的三级子图和一级子图进行动态规划。

根据对所述三级子图序列中每个三级子图和进行连通域分割后未获成功的一级 子图进行单字符识别后无法确定部件子图时，将所有不能确定为部件子图的三级子图和一 级子图作为基本单位，进行动态规划，具体步骤如下。

将所有上述不能确定为部件子图的子图按照在待识别图像中的位置进行从左到 右，从上到下的排序，重新标记为新的子图序列。动态规划采用通 过局部最优解推算全局最优解的方法，得到新的子图序列的最优 组合。具体过程如下：计算子图序列中第0到第k个子图的最优组合情况，则分别计算第0到 第i个子图的最优组合和第i个子图到第k个子图的最优组合，其中i的范围为[1,k-1]。而第 0到第i的子图的最优组合则为第0到第j个子图的最优组合和第j到第i个子图的最优组合， 其中j的范围为[1,i-1],以此类推，由局部最优解推算出全局最优解。

在最优解的求解过程中，评定规则为：通过几何得分和识别可信度得分的加权，获 得最终得分，即score=n₁*Gem+n₂*Reg（score为最终得分，Gem为几何得分，Reg为识别可信 度得分，n₁、n₂分别表示几何得分和识别可信度得分的权值），此处得分越高表示结果越好， 因此最后选取得分最高的结果作为最优解。例如，若要求解和两个子图合并的情况， score表示i与i-1组合的最终得分。通过将、两个子图进行合并，将合并后的子图进 行部件识别，其中，所述部件识别是参照单字符识别方法，以新的部件集为识别对象的一种 统计模式的识别方法。

部件识别具体方法为：将合并后的子图进行非线性放缩，即曲线拟合归一化，提取 子图的纹理特征和边缘特征，形成子图的部件特征，并与部件特征集进行比对，最终获取识 别结果Code和识别可信度得分Reg。提取将上述两个子图进行合并之后的空间位置特征，与 编码为Code的部件的空间位置特征进行匹配，得到相似度得分Gem。根据获得的Gem和Reg 值，即可计算该组合的最终得分。

通过上述过程求解出新的子图序列的得分最高的组合， 该得分最高的组合即为最优组合子图序列，最优组合子图序列中每个子图即为部件子图。

通过上述步骤S401至步骤S404，完成对待识别公式图像的所有部件子图的采集， 且每个所述部件子图包含一个部件。

对于步骤S5：获取每个部件子图的部件特征，通过与部件特征集比对，实现公式识 别。

首先，对通过步骤S4获得的每个部件子图S_i进行非线性放缩，即曲线拟合归一化 处理,归一化到统一的大小。

然后，对每个部件子图S_i进行纹理特征和边缘特征提取，形成部件子图S_i的部件特 征。基于提取的部件子图S_i的部件特征与步骤S3中提取的部件特征集的比对结果，进行部 件识别。具体地，计算单个部件子图S_i的部件特征与部件特征集中各特征之间的相似度。例 如，可以计算部件特征集与单个子图S_i的特征之间的欧式距离，以欧式距离的倒数作为相 似度度量。将相似度度量按照从大到小的顺序排序，选取前M个相似度度量值对应的M个部 件特征集中的部件特征，将这M个部件特征集中的部件特征对应的部件编码作为所述单个 部件子图的多候选识别结果。

获得单个部件子图的多候选识别结果后，根据该多候选识别结果，最终获得公式 识别结果，具体方法如下：

当待识别公式图像中只包括一个部件时，则在该多候选识别结果中选取相似度最大的 部件特征对应的部件编码作为公式识别结果。

当待识别公式图像中包含多个部件时，将待识别公式图像的每个部件子图的多候 选识别结果作为基本单位，采用动态规划的方法，结合特定的语言模型，对每个候选的公式 识别结果进行评分、排序，该评分规则依据事先统计的语言概率模型，最后选择依据该模型 得分最高的结果作为公式识别结果。下面具体描述本发明所应用的语言概率模型。

上述语言模型是通过语料库来对某些部件同时出现的概率进行统计，首先要计算 部件β₀的识别候选α₀与部件β₁的识别候选α₁同时出现在语料库中的语言概率P(gá)；P(gá) 的计算需要统计部件β₀的识别候选α₀与部件β₁的识别候选α₁同时出现在语料库中次数f(g á)，并统计语料库中所有公式出现的总次数S(GΩ)，这样就有P(gá)＝f(gá)/S(GΩ)。例如， 待识别公式图像经过处理后得到部件子图ImageA和部件子图ImageB，分别将这两个部件子 图的特征与部件特征集进行对比，根据相似度的较大的结果，得到部件子图ImageA的多候 选识别结果CA₁，CA₂……CA_n，同理，得到部件子图ImageB的多候选识别结果CB₁，CB₂，…… CB_m，其中，n，m为多候选的个数。此时，分别取两个部件子图的最优识别结果的组合作为公 式的识别结果通常不是该公式的最优结果，因此，需要进一步采用动态规划的方法，结合上 述语言模型对两个部件子图的多候选识别结果进行分别组合，查找语言模型中对应的组合 概率值，依据该概率值进行打分，最终，结合单个部件的识别得分和多个部件子图的语言模 型得分确定公式的最优识别结果。通常，将上述两种得分进行加权获得加权得分。选择加权 得分最高的结果作为公式识别结果。

下面结合图2说明根据本发明的一优选实施例的公式识别装置的具体构造。

本发明的公式识别装置包括构建部件模块、建立部件集模块、构建部件编码集和 部件特征集的模块、获取部件子图模块、以及公式识别模块。下面具体对每个部件进行说 明。

构建部件模块，利用构建部件模块获取所述公式库中每个公式的部件，首先获取 公式的起始符号，然后获取以起始符号为基准符号，结构关系为水平关系的符号， 以此类推，分别获取以为基准符号，结构关系为水平关系的符号，从而完成对第一 等级符号的获取；接下来分别获取以为基准 的次等级符号。若公式中以某一第一等级符号为基准，不存在次等级符号，则定义该第一等 级符号即为部件；否则，若存在次等级符号，则获取以第一等级符号为基准所衍生出的子公 式，并将子公式作为部件。通过以上的步骤，完成对公式库中每个公式的部件采集。

建立部件集模块，其根据构建的所述每个公式的部件，建立公式的部件集。

构成部件编码集和部件特征集模块，其用于对所述部件集中的每个部件进行去重 操作，并将去重后的部件集中每个部件设置编码形成部件编码集，提取所述部件编码集中 每个编码对应的部件的特征，进而构建与所述部件编码集相对应的部件特征集。

获取部件子图模块，该模块具体包括水平方向投影切分模块,、连通域分割模块、 单字符识别模块、以及动态规划模块，用于分别对待识别公式图像进行水平方向投影切分、 连通域分割、单字符识别和动态规划，最终获得所述待识别公式图像的部件子图，其中，每 个所述部件子图包含一个部件。

其中，水平方向投影切分模块，其用于对待识别的公式图像进行水平方向投影切 分。

首先对待识别的公式图像进行二值化处理，然后统计每一列非零像素值的个数并 用数组Col[w]存储，最后对数组Col[w]进行遍历，其中数组Col[w]的零值与非零值的交界 处即为切分点。

通过上述切分点的确定，获得了该公式图像的一级子图序列,由于该水平方向投影切分的结果受切分精度、图像清晰度等因素的影响，导致该一级子图 序列中的每个子图存在三种可能性：①是某一个部件的完整图；②是某一个部件的 一部分;③是两个或者多个部件组合成的。

由于存在不是期望获得的部件子图的可能性②和③的，因此需要连通域分割模 块进一步处理，以获得期望的部件子图。

此外，对获取的一级子图序列进行计算。计算相邻的一 级子图的右边界与一级子图的左边界的距离（），对计算得到的进行 平均值计算，获得的平均值，将定义为第一参考值。

然后，获取一级子图序列中的所有一级子图的宽度分别 为，计算所有一级子图的宽度的平均值，使得，将定义为第二参考值。

连通域分割模块，其用于对一级子图序列中的每一个子 图进行连通域分割，使每一个一级子图被分割为m个二级子图序列 。由于通过连通域分割而得到的二级子图比较零碎，因此，需要根 据二级子图之间的空间位置关系进行合并处理。具体合并过程如下：

首先，计算二级子图序列中每一个二级子图（0≤j≤m）的 矩形框Rect（）；

然后，对计算得到的m个矩形框进行遍历，若任意两个矩形框之间同时存在水平和垂直 方向的重叠，则将这两个二级子图进行合并，作为一个新的三级子图。

重复上述过程，直到没有二级子图能够进行合并为止，最终得到k（k≤m）个连通域 分割三级子图序列。

单字符识别模块，其用于对三级子图序列中的每个三级子图和连通域分割未获成 功的一级子图进行单字符识别。

对连通域分割成功的三级子图序列中的每个三级子 图和进行连通域分割后未获成功的一级子图进行单字符识别，然后获取每个三级子图和每个进行连通域分割后未获成功的一级子图的识别结果及其对应的识别可信度。

具体地，对所述三级子图序列中的每个三级子图分别进行单字符识别获得所述每 个三级子图的识别结果及相应的识别可信度；根据单字符识别判断所述识别结果中存在的 第一等级符号的类型及相应的识别可信度并结合第一参考值和第二参考值确定部件子图。 通过上述方式，可以确定以下两种类型的部件子图：

①若该三级子图序列中存在识别结果为分式且识别可信度高于第一预设值的三级子 图，三级子图的宽度接近其对应的一级子图的宽度，且三级子图的宽度大于 第一参考值和第二参考值，即，的宽度与高度比值很大，则认为所述一级子图为 分式类型的部件子图，不需要做进一步的处理。即，特别的，第一预设值为80%-100%之间的 任一数值。

②若该三级子图序列中存在识别结果为根式且识别可信度高于所述第一预设值 的三级子图，三级子图的高度接近与其对应的一级子图的高度，且三级子图的 高度大于第一参考值和第二参考值，的宽度与高度比值很小，则认为所述一级子 图为根式类型的部件子图，不需要做进一步的处理。

对连通域分割后未获成功的一级子图进行单字符识别，根据识别结果及其对应的 识别可信度，并结合第一参考值确定部件子图，具体为：

针对进行连通域分割后未获成功的一级子图进行单字符识别，若识别结果为公式 符号且识别可信度高于所述第一预设值，同时该一级子图与水平方向的相邻一级子图的 距离接近第一参考值，则认为所述一级子图为公式符号类型的部件子图，不需要做进一 步的处理。

动态规划模块，其用于对不能确定为部件子图的三级子图和一级子图进行动态规 划。

根据对所述三级子图序列中每个三级子图和进行连通域分割后未获成功的一级 子图进行单字符识别后无法确定部件子图时，将所有不能确定为部件子图的三级子图和一 级子图作为基本单位，进行动态规划，具体步骤如下。

将所有上述不能确定为部件子图的子图按照在待识别图像中的位置进行从左到 右，从上到下的排序，重新标记为新的子图序列。动态规划采用通 过局部最优解推算全局最优解的方法，得到新的子图序列的最优 组合。具体过程如下：计算子图序列中第0到第k个子图的最优组合情况，则分别计算第0到 第i个子图的最优组合和第i个子图到第k个子图的最优组合，其中i的范围为[1,k-1]。而第 0到第i的子图的最优组合则为第0到第j个子图的最优组合和第j到第i个子图的最优组合， 其中j的范围为[1,i-1],以此类推，由局部最优解推算出全局最优解。

在最优解的求解过程中，评定规则为：通过几何得分和识别可信度得分的加权，获 得最终得分，即score=n₁*Gem+n₂*Reg（score为最终得分，Gem为几何得分，Reg为识别可信 度得分，n₁、n₂分别表示几何得分和识别可信度得分的权值），此处得分越高表示结果越好， 因此最后选取得分最高的结果作为最优解。例如，若要求解和两个子图合并的情况， score表示i与i-1组合的最终得分。通过将、两个子图进行合并，将合并后的子图进 行部件识别，其中，所述部件识别是参照单字符识别方法，以新的部件集为识别对象的一种 统计模式的识别方法。

部件识别具体方法为：将合并后的子图进行非线性放缩，即曲线拟合归一化，提取 子图的纹理特征和边缘特征，形成子图的部件特征，并与部件特征集进行比对，最终获取识 别结果Code和识别可信度得分Reg。提取将上述两个子图进行合并之后的空间位置特征，与 编码为Code的部件的空间位置特征进行匹配，得到相似度得分Gem。根据获得的Gem和Reg 值，即可计算该组合的最终得分。

通过上述过程求解出新的子图序列的得分最高的组合， 该得分最高的组合即为最优组合子图序列，最优组合子图序列中每个子图即为部件子图。

通过上述模块处理，完成对待识别公式图像的所有部件子图的采集，且每个所述 部件子图包含一个部件。

公式识别模块，利用公式识别模块对每个子图S_i进行纹理特征和边缘特征提取， 形成每个子图的部件特征。利用构成部件编码集和部件特征集模块，提取单个部件子图的 部件特征，并计算单个子图S_i的部件特征与部件特征集中各特征之间的相似度。将相似度 度量按照从大到小的顺序排序，选取前M个相似度对应的M个部件特征，并将所述M个部件特 征对应的部件编码作为所述单个部件子图的多候选识别结果。

若所述待识别公式图像只包括一个部件子图，在所述多候选识别结果中选取相似 度最大的部件特征对应的部件编码作为公式识别结果；

若所述待识别公式图像包括多个部件子图，将所述待识别公式图像的每个部件子图的 多候选识别结果作为基本单位，采用动态规划的方法，结合概率统计语言模型对每个候选 的公式识别结果进行评分、排序，将得分最高的部件特征对应的部件编码作为公式识别结 果。

以上对本发明提出的一种基于公式库的公式识别方法和装置进行了描述。与传统 的公式识别方法相比，本发明所述识别方法类似于文本行识别。以预先建立的公式库为基 础，该识别方法可以充分利用公式库来校准和优化识别结果，同时，该识别方法将复杂类型 的子公式转换成一个新的字符，一个公式就被当成一个或者多个复杂类型子公式和单个传 统字符的水平方向组合。通过本发明所述的公式识别方法及装置，不需要进行字符之间的 结构分析，简化了公式识别的步骤，节省公式识别的时间，提高了公式识别的准确率。

以上所述仅为本申请的实施例而已，并不用于限制本发明，对于本领域的技术人 员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、 等同替换、改进等，均应包含在本发明的权利要求范围之内。