一种针对OPTA图像细化算法的快速实现方法

摘要

本发明公布了一种针对OPTA图像细化算法的快速实现方法，属于数字图像处理技术领域。本发明主要包括2个部分：基于OPTA类算法中的删除模板和保留模板构造等价的查找表；基于已构造的查找表实现二值图像的快速细化。本发明的优点在于将OPTA类算法中复杂的模板匹配运算转化为完全等价的快速的查表运算，从而大幅度地提高了OPTA类算法的运算效率。

说明书

技术领域

 本发明属于数字图像处理技术领域，涉及一种针对OPTA图像细化算法的快速实现

方法。为OPTA类算法中消除模板和保留模板构造等价的查找表，基于已构造的查找表实现二值图像的快速细化，从而大幅度地提高了OPTA类算法的运算效率。

背景技术

细化又称为骨架化，即在不影响原图拓扑性的基础上，通过抽取表达原图形状最关键的点，来使得原图中宽度大于一个像素的线条变成单像素的过程，也就是抽取原图骨架的过程。该技术在图像处理中占有重要地位, 是图像分析、信息压缩、特征抽取及模式识别中的常用技术。

目前，已有了大量的图像细化算法被提出，主要可分为串行细化算法^[1,2]和并行细化算法^[3-12]，文献[11]对串行与并行细化算法进行了对比、总结：串行细化算法, 其当前迭代的结果不仅取决于前一次的迭代结果, 而且与当前处理情况有关；而并行细化算法, 其当前迭代则仅仅由前一次的迭代情况决定。由于串行细化算法的处理结果依赖于对像素处理的先后顺序, 因而像素点的消除或保留不可预测；而并行细化算法在对图像进行细化时，由于是利用相同的条件同时检测所有像素点, 其结果具有各向同性, 因此从算法原理上看, 并行方法优于串行方法。

OPTA(One-Pass Thinning Algorithm)细化算法是一种典型的并行图像细化算法，其最早于文献[4]被提出，文献[10]针对其存在细化不全、速度较慢的缺点进行了研究和改进；文献[11]指出文献[10]虽然在细化速度上有所提高，但仍然引入了过多的迭代，影响细化速度，因此文献[11]对文献[10]算法又做了进一步的改进。文献[12]发现文献[11]的改进虽有效地提高了细化速度，但细化质量有所下降，为此在文献[10]的基础上，提出了一种新的图像快速细化算法。该算法不仅有效地保留了文献[10]算法的细化效果，同时较之文献[11]算法细化速度更快。

一个好的细化算法应满足以下的要求^[10]:

(1) 细化图像的连通性必须与原图像保持一致；

(2) 细化图像中的线条宽度应为单像素；

(3) 细化图像中的线条应尽可能是中心线；

(4) 细化后图像应尽可能保持原图的细节特征；

(5) 细化算法的速度应尽可能快。

从以上5点要求中可以发现，前4条准则主要集中在对细化质量的评价，最后一条是对细化速度的要求。因此，对一个细化算法的评价，主要是从细化质量和细化速度两个方面进行。

文献[10,11,12] 都是从改进模板的角度出发来提高该类算法的细化质量和细化速度。

参考文献

[1] C. Arcelli, G. Sanniti di Baja. On the sequential approach to medial line transformation. IEEE Transaction on Systems, Man and Cybernetics, 1978, 8(2): 139~144.

[2] J. Lin, Z. Chen. A Chinese-character thinning algorithm based on global features and contour information. Pattern Recognition, 1995, 28(4): 493~512.

[3] T. Y. Zhang, C. Y. Suen. A fast parallel algorithm for thinning digital patterns. Communications of the ACM, 1984, 27(3): 236~239.

[4] Chin R T, Wan H K, Stover D L, et al. A one-pass thinning algorithm and its parallel 

implementation. Computer Vision Graphics Image Processing (CVGIP), 1987, 40 (1): 30~40.

[5] B. K. Jang, R. T. Chin. One-pass parallel thinning: Analysis, properties, and quantitative evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(11): 1129~1140.

[6] K. Abe, F. Mizutani, C. Wang. Thinning of gray-scale images with combined sequential and parallel conditions for pixel removal. IEEE Transaction on Systems, Man and Cybernetics, 1994, 24(2): 294~299.

[7] L. Lam, C. Y. Suen. An evaluation of parallel thinning algorithm for character recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(9): 914~919.

[8] F.Y.Shih, W.T.Wong. A new safe-point thinning algorithm based on the mid-crack code tracing, IEEE Transaction on Systems, Man and Cybernetics, 1995, 25(2): 370~378.

[9] J. J.Zou, H.Yan, Skeletonization of ribbon-like shapes based on regularity and singularity analyses. IEEE Transaction on Systems, Man and Cybernetics (B), 2001, 31(3): 401~407.

[10] 冯星奎,李林艳,颜祖泉.一种新的指纹图像细化算法.中国图象图形学报, 1999, 4(10): 835~838.

[11] 王家隆,郭成安.一种改进的图像模板细化算法.中国图象图形学报,2004, 3(9): 297~301.

[12]梅园,孙怀江,夏德深. 一种基于改进后模板的图像快速细化算法. 中国图象图形学报, 2006,11(9):1306~1311.。

发明内容

技术问题

本发明目的是针对现有OPTA类算法存在大量复杂的模板匹配运算问题，提出一种将模板匹配运算转换成查表运算的实现方法，以大幅度提高OPTA类算法的运算效率。

技术方案

本发明为实现上述目的，采用如下技术方案：

本发明提出一种针对OPTA图像细化算法的快速实现方法，包括以下步骤：

1）将OPTA类算法中的删除模板和保留模板统一规划为4×4的模板；

2）将每个规划后的删除模板与所有保留模板进行匹配，列出所有同时满足删除模板

和保留模板的情况，并将每种情况表示为一个4×4的组合模板(具体过程详见文献[12])；

    3）将4×4模板中的每个单元格按照从左到右、从上到下的顺序依次标记为                                                、、…、，每个单元格的取值为0或1，则4×4模板可以用一个16位的二进制数表示，取值范围为0～65535之间的所有整数；

4）构造一维数组LUT[65536]，并将数组中所有65536个数的初值值为0；

5）对每个规划后的删除模板，列出所有满足该删除模板的16位二进制数，计算每个二进制数对应的十进制整数，并使得LUT[]=1；

6）对每个组合模板，同步骤5）方法列出所有满足该组合模板的16位二进制数，计算每个二进制数对应的十进制整数，并使得LUT[]=0；

7）对待细化的二值图像中的每个像素点，若该点属于前景点，则将其作为4×4模板中的当前单元格，其周围像素点根据相对位置依次对应其它15个单元格，获取该像素点的16位二进制数并计算对应的十进制整数，如果LUT[]=1，则将该像素点置为背景点，如果LUT[]=0，则该像素点保持不变；

8）重复步骤7），直至整幅图像中所有像素点都被处理完，至此对整幅图像的第一遍细化完成；

9）若上一遍细化过程中，存在前景像素点被置为背景点，则在上一遍细化的结果上再次重复步骤7）、步骤8）进行再次细化，直至一遍细化完成后没有前景像素点被置为背景点，此时整个细化过程结束。

其中，步骤1）所述的删除模板一般为3×3模式，在统一规划为4×4模板时，多出的7个单元格用X代替(X表示该单元格值可以为0或1)，保留模板一般为4×4模式，在统一规划时无需更改。

其中，步骤3）4×4模板中第2行第2列的单元格为当前单元格，即单元格。

其中，步骤5）所述的删除模板的单元格，若其值为X，则在罗列其16位二进制数时，须将其在X=0、X=1时分别列出。

其中，步骤7）中约定前景点即为像素值为1的点，背景点是像素值为0的点。

有益效果

本发明目的是针对现有OPTA类算法存在大量复杂的模板匹配运算问题，提出一种将模板匹配运算转换成查表运算的实现方法。本发明主要包括2个部分：基于OPTA类算法中的删除模板和保留模板构造等价的查找表；基于已构造的查找表实现二值图像的快速细化。相对于OPTA类算法中复杂的模板匹配运算，查表运算可以大幅度地提高OPTA类算法的运算效率，且本发明的优点可以与其它专注于模板改进方法的优点达到完全叠加的效果。

附图说明

图1是文献[10]中的删除模板；

图2是文献[10]中的保留模板；

图3是文献[10]中的删除模板进行统一规划后的4×4模板；

图4是组合模板；

图5是对4×4模板进行标记的示意图。

具体实施方式

下面将结合附图及具体实施例对本发明所述的一种针对OPTA图像细化算法的快速实现方法作进一步地详细描述。

本实施例基于如图1、图2所示的删除模板、保留模板进行详细阐述，具体步骤如下：

步骤1将图1中的删除模板统一规划为4×4的模板，其结果如图3所示，由于图

2中保留模板已满足4×4模式，故无需更改；

步骤2将每个规划后的删除模板与所有保留模板进行匹配，列出所有同时满足删除

模板和保留模板的情况，并将每种情况表示为一个4×4的组合模板，其结果如图4所示；

    步骤3将4×4模板中的每个单元格按照从左到右、从上到下的顺序依次标记为、、…、，如图5所示，每个单元格的取值为0或1，则4×4模板可以用一个16位的二进制数表示，取值范围为0～65535之间的所有整数；

步骤4构造一维数组LUT[65536]，并将数组中所有65536个数的初值值为0；

步骤5对每个规划后的删除模板，列出所有满足该删除模板的16位二进制数，计算每个二进制数对应的十进制整数，并使得LUT[]=1。例如针对图3(a)模板，其16位二进制为000XX1XX111XXXXX，在计算该二进制对应的十进制数时，需要将每个X都分别具体化为0和1，故该模板共计可以表示2⁹=512个16位二进制数，如0000010011100000就是其中一个，其对应的十进制数值为1248，故LUT[1248]=1；

步骤6对每个组合模板，同步骤5）方法列出所有满足该组合模板的16位二进制数，计算每个二进制数对应的十进制整数，并使得LUT[]=0；

步骤7对待细化的二值图像中的每个像素点，若该点属于前景点，即该像素点值为1，则将其作为4×4模板中的当前单元格，其周围像素点根据相对位置依次对应其它15个单元格，获取该像素点的16位二进制数并计算对应的十进制整数，如果LUT[]=1，则将该像素点置为背景点，即将该像素点值置为0，如果LUT[]=0，则该像素点值保持不变；

步骤8重复步骤7），直至整幅图像中所有像素点都被处理完，至此对整幅图像的第一遍细化完成；

步骤9若上一遍细化过程中，存在前景像素点被置为背景点，则在上一遍细化的结果上再次重复步骤7）、步骤8）进行再次细化，直至一遍细化完成后没有前景像素点被置为背景点，此时整个细化过程结束。