一种基于稀疏表示和判决分析的数码球识别方法

摘要

本发明公开了一种基于稀疏表示和判决分析的数码球识别方法，包括：把数码球集合中的每一个数码球，放置在单色背景下，利用单摄像头连续采集单幅或多幅图像，自动定位每幅图像中的数码球并提取视觉特征，并对所有的特征建立稀疏表达，形成训练样本特征集合；把待识别的一个或多个数码球放置在同样的场景中，采集单幅或多幅图像，对每幅图像中的所有数码球自动定位并提取子图像和提取子图像的视觉特征，并利用训练样本特征集合建立该子图像的稀疏表达；采用判决分析方法进行识别，其中对于多幅图像的情况，采用联合后验判决，提高识别精度。本发明充分利用稀疏表达和判决分析，应用于单色背景下的单球或多球识别，识别效果好。

说明书

技术领域

本发明属于图像稀疏表示和概率计算领域，具体是涉及一种基于稀疏表示和判决分析的数码球识别方法。

背景技术

传统的字符识别都是在平面上操作的，但如果把这些平面操作的方法用于曲面，就会出现很多问题。但是我们生活中的很多东西并不仅仅是平面上的识别，对于曲面甚至不规则图形上的识别是个很有意义又很实用的方法。数码球是一种在它表面上印有唯一数字的球，因此我们需要一种新的方法来识别球面上的数字信息。我们先实现静止图片的识别，然后对高速运动的数码球进行连续拍摄，再进行识别，这是个很有挑战性也很有工业价值的问题。

由于是球面上操作的，所以先要检测到圆，然后定位数字，接着把数字信息表示出来，最主要的还是识别这个数字信息。然而，因为数码球存在着三维旋转，不同视角等问题，所以导致了不同的观测结果。此外，通过单个相机，我们只能得到数码球的部分信息，不能得到完整的球面信息用于识别。最后，当图片中存在多个数码球的时候，我们如何准确定位和去除那些错误定位的圆很重要。所以我们提出了用稀疏表达和多次概率分布的测量来实现球面数字的识别。

近年来，稀疏表达在机器学习和模式识别中应用的越来越多了。尤其对于处理高维数据，稀疏的方法很有效。基于稀疏表达这个技术，每个样本都可以表达为训练数据的稀疏线性组合。当这个优化表示足够稀疏时，基于凸优化的算法能够有效用于解决该问题。比较有名的稀疏表达方法有lasso，弹性网(elastic net)和非负方法(nonnegative garrote)。该发明中，就是用这三种方法来表达数码球的信息用于分类的。

在表示了数码球的信息后，接着就是分类了。一直以来，分类都是机器学习中的重点，分类的方法也是多种多样的。在机器学习提出来之前，主要的分类方法是相关。随着机器学习的广泛兴起，有越来越多的分类方法了，如PCA(Shlens Jonathon，A Tutorial on Principal Component Analysis.Systems Neurobiology Laboratory，Salk Insitute for Biological Studies，2009)，Fisher判决(Fisher，Ronald A.，The use of multiple measurements intaxonomic problems.Annals Eugen.，1936.)，线性判别分析(LDA)(R.Duda，P.Hart，and D.Stork，Pattern classification，2rd ed.Wiley-Interscience，2000)。本发明利用多次测量和概率方法来进行分类，通过单次甚至多次的后验判决方法达到不错的数码球识别率。

发明内容

本发明提供了一种基于稀疏表示和判决分析的数码球识别方法，该方法识别能力强，识别效果好。

一种基于稀疏表示和判决分析的数码球识别方法，包括：

(1)把数码球集合中的每一个数码球单独放置在单色背景下，利用单摄像头连续采集单幅或多幅图像，自动定位每幅图像中的数码球并提取视觉特征，并对所有的视觉特征建立稀疏表达，形成训练样本特征集合；

(2)把待识别的一个或多个数码球放置在同样的场景中，采集单幅或多幅图像，对每幅图像中的所有数码球自动定位并提取子图像；对单幅或者多幅图像中对应同一数码球的子图像提取视觉特征，并利用训练样本特征集合建立该子图像的稀疏表达；

(3)采用判决分析方法进行识别，得到测试图像所属的类别，其中对于多幅图像的情况，采用联合后验判决的方法实现。

所述的步骤(1)中形成训练样本特征集合的方法为在单色背景下用单摄像头连续采集单幅或多幅图像，每幅图中只有一个数码球，形成训练样本集合，定位图像中的球并提取视觉特征，建立训练样本集合的稀疏表达：把数码球集合中的每一个数码球，单独放置在单色背景(如黑色)下，利用单摄像头连续采集单幅或多幅图像作为训练样本集合，每次获得的图像都是单视角的，具体步骤如下：

(a)对采集的图像做预处理，使用Canny算子进行边缘检测，得到二值化图像，接着给出圆的大致半径，使用霍夫变换或外接圆构造匹配的方法定位每幅图中的数码球位置；

(b)在每幅数码球图片上找到感兴趣的信息区域，检测并提取该兴趣区域(黄同同，数码球的快速检测与识别。浙江大学计算机学院：计算机软件与理论，2010)，最后对该兴趣区域进行坐标轴变换，用极坐标形式进行特征提取和表示，其流程如下：检测出数码球图片上的椭圆，然后将椭圆移到中心，旋转和重投影这椭圆，对椭圆进行二值化，从二值化图像转换得到极坐标图像；

(c)最后将来自第i类的n_i幅训练图片构成矩阵其中a_i，j，j＝1，2，...n_i是由每幅图像构成的列向量，每个元素都标准化为单位的l²范数，所有K个类的训练图片组合成一个训练样本矩阵A＝[A₁，A₂，...，A_K]，即为训练样本特征集合。

所述的步骤(2)中对每幅图像中的所有数码球自动定位并提取子图像的过程为：

(a)对输入的测试图像A进行预处理，使用Canny算子进行边缘检测，得到二值化图像；

(b)把二值化后的图像中的所有点都保存下来，以所有的非零点为中心，球的半径为半径，把该区域内的所有点都加1，再标准化该边缘直方图；

(c)遍历标准化边缘直方图中所有的点，估计出所有圆的中心并保存下来；

(d)以每个圆心信息为中心，以球的半径为半径，提取出测试图片所有的感兴趣区域并以图片方式保存下来，输出得到所有感兴趣区域的子图像A＝{A₁，A₂，...A_n}，即测试图像的子图像。

多球检测的实施算法如下：

输入：单幅测试图像A

输出：所有感兴趣区域子图像A＝{A₁，A₂，...A_n}

步骤1：对输入的测试图像进行预处理，使用Canny算子进行边缘检测，得到二值化图像；

步骤2：计算二值化图像的边缘直方图，即以所有的非零点为中心，球的半径为半径，把该区域内的所有点都加1，再标准化该边缘直方图；

步骤3：遍历图中所有的点，取那些一定区域内(大于某个设定的阈值)最大值的点为圆心并保存下来；

步骤4：以每个圆心信息为中心，以球的半径为半径，提取出测试图片所有的感兴趣区域并以图片方式保存下来。

所述的对识别单幅或者多幅图像中对应同一数码球的子图像提取视觉特征的过程为：取出测试图片中的一个感兴趣区域子图像，把该兴趣区域堆成一个列向量用所有训练样本特征集合得到y的近似稀疏表达，即：

其中，β是稀疏系数向量。理想情况下，β中除了与y所属的类i相关的系数不为零外，其它所有系数都为零。但是，通常是β的大部分非零值都集中在第i类上，小部分非零值分散在其它类上。现在的问题是如何来求得β，从而获得y的近似表达。我们可以用下面三种方法来实现：

第一种方法是用lasso算法(R.Tibshirani，Regression Shrinkage and Selection via the Lasso.Journal of the Royal Statistical Society，Series B，1996.)求得稀疏系数向量β，即：

$\arg \underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+\lambda {\left|\right|\beta \left|\right|}_1$

其中，||·||₁是l¹范数，λ||β||₁是l¹惩罚项。

第二种方法是用弹性网算法(H.Zou and T.Hastie，Regularization and variable selection via the Elastic Net.Journal of the Royal Statistical Society，Series B，2005.)求得稀疏系数向量β，即：

$\underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+{\lambda }_1{\left|\right|\beta \left|\right|}_1+{\lambda }_2{\left|\right|\beta \left|\right|}_2^2$

其中，||·||₂表示为一个向量的l²范数，并且弹性网可以用LARS(B.Efron，T.Hastie，I.Johnstone and R.Tibshirani，Least angle regression.Annals of Statistics，2004.)方法解决。

第三种方法是用非负方法(nonnegative garrote)(L.Breiman，Better subset regression using the nonnegative garrote.Technometrics，1995.)求稀疏系数向量β，即：

$\underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+\lambda {\left|\right|\beta \left|\right|}_1,s.t.{\beta }_i>0$对于i＝1，...，n。

非负方法可以用经典的数值方法有效求得，这些经典的数值方法包括最小角回归(LARS)和pathwise coordinate(J.Friedman，T.Hastie，H.Hofling and R.Tibshirani，Pathwise coordinate optimization.Annals OfApplied Statistics，2007.)方法。

得到测试图片y的稀疏表达β后，接下来就是判断y属于哪个类。这个提取的特征在不同的类之间应该尽可能的不同。根据前面的稀疏表达，已经知道系数向量β的大部分非零值主要集中于测试样本所属的类，即其中，γ_i是与第i类相关的系数向量。为了估计测试样本所属的类，我们定义了下面的后验估计(posterior estimate)：

$p(y\in C_i|\beta )=\frac{\underset{j=1}{\overset{n_i}{\Sigma }}{\gamma }_{\mathrm{ij}}}{\underset{k=1}{\overset{n}{\Sigma }}{\beta }_k}$

这里的γ_ij是第i类在第j次计算得到的系数向量。

接着，我们选择概率值最大的类作为测试图片y所属的类别，即：

$\underset{i}{\max }p(y\in C_i|\beta ).$

对于单幅图像，我们可以采用后验估计的识别方法进行识别。对于多幅图像的识别，为了提高精度，我们可以采取联合后验判决的方法实现。计算m次系数向量判断y属于第C_i类的多次后验概率，联合后验判决的计算公式如下：

$p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)=\frac{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n_i}{\Sigma }}{\gamma }_{\left(\mathrm{ij}\right)l}}{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n}{\Sigma }}{\beta }_{\mathrm{jl}}}$

γ_ij是第i类在第j次计算得到的系数向量，γ_(ij)l是向量γ_ij的第l个元素、然后，我们选择概率值最大的类作为测试图片y所属的类别，即：

$\underset{i}{\max }p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)$

下面的算法给出了图像的稀疏表达和判决分析过程：

输入：k个类的训练样本构成的矩阵由测试图片构成的列向量

输出：y所属的类标签m。

步骤1：用lasso求解问题：

$\arg \underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+\lambda {\left|\right|\beta \left|\right|}_1;$

或：用弹性网(elastic net)求解问题：

$\underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+{\lambda }_1{\left|\right|\beta \left|\right|}_1+{\lambda }_2{\left|\right|\beta \left|\right|}_2^2;$

或：用非负的方法(nonnegative garrote)求解问题：

$\underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+\lambda {\left|\right|\beta \left|\right|}_1,s.t.{\beta }_i>0$对于i＝1，...，n

步骤2：计算单次的后验估计：

$p(y\in C_i|\beta )=\frac{\underset{j=1}{\overset{n_i}{\Sigma }}{\gamma }_{\mathrm{ij}}}{\underset{k=1}{\overset{n}{\Sigma }}{\beta }_k}$

或：多次的后验估计：

$p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)=\frac{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n_i}{\Sigma }}{\gamma }_{\left(\mathrm{ij}\right)l}}{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n}{\Sigma }}{\beta }_{\mathrm{jl}}}$

步骤3：输出测试样本y所属的类标签m。

$\underset{i}{\max }p(y\in C_i|\beta )$或$\underset{i}{\max }p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)$

附图说明

图1是实施例中数码球特征提取的步骤；

图2是实施例中多球识别的测试图片；

图3是实施例中基于稀疏表示的数码球识别方法识别示意图；

图4为本发明基于稀疏表示的数码球识别方法的识别流程示意图。

具体实施方式

如图4所示，一种基于稀疏表示和判决分析的数码球识别方法，包括：

(1)把数码球集合中的每一个数码球单独放置在单色背景下，用单摄像头连续采集单幅或多幅图像，如图1所示，每幅图中只有一个数码球，形成训练样本集合，定位图像中的球并提取视觉特征，建立训练样本集合的稀疏表达：

把数码球集合中的每一个数码球，单独放置在黑色背景下，利用单摄像头连续采集单幅或多幅图像作为训练样本集合，每次获得的图像都是单视角的；对采集的图像做预处理，使用Canny算子进行边缘检测，得到二值化图像，接着给出圆的大致半径，使用霍夫变换或外接圆构造匹配的方法定位每幅图中的数码球位置；在每幅训练图片上找到感兴趣的信息区域(黄同同，数码球的快速检测与识别。浙江大学计算机学院：计算机软件与理论，2010)，检测并提取该区域，最后对该兴趣区域进行坐标轴变换，用极坐标形式进行特征提取和表示，其流程如图1：即检测出图片上的椭圆，然后将椭圆移到中心，旋转和重投影这椭圆，对椭圆进行二值化，从二值化图像转换得到极坐标图像；然后将来自第i类的n_i幅训练图片构成矩阵其中a_i，j，j＝1，2，...n_i是由每幅图像构成的列向量，每个元素都标准化为单位的l²范数，因此，所有K个类的训练图片组合成一个训练样本矩阵

(2)将测试的多个数码球放在相同的单色背景下，采集测试图像，并对每幅图像中的所有数码球自动定位和提取子图像：把要检测的一个或多个数码球放在如上的单色背景下，采集单幅或多幅测试图像，如图2；对测试图片进行预处理，使用Canny算子进行边缘检测，得到二值化图像；把二值化后的图像中的所有点都保存下来，然后计算其边缘直方图并标准化；遍历直方图中的所有点，估计出所有圆的中心并存下来；提取保存下来的圆心信息，以每个圆心信息为中心，以球的半径为半径，提取出测试图片中的所有感兴趣区域并以图片方式保存下来。

多球检测的实施算法如下：

输入：单幅测试图像A

输出：所有感兴趣区域子图像A＝{A₁，A₂，...A_n}

步骤1：对输入的测试图像进行预处理，使用Canny算子进行边缘检测，得到二值化图像；

步骤2：计算二值化图像的边缘直方图，即以所有的非零点为中心，球的半径为半径，把该区域内的所有点都加1，再标准化该边缘直方图；

步骤3：遍历图中所有的点，取那些一定区域内(大于某个设定的阈值)最大值的点为圆心并保存下来；

步骤4：以每个圆心信息为中心，以球的半径为半径，提取出测试图片所有的感兴趣区域并以图片方式保存下来。

(3)对识别的单幅或者多幅图像中对应同一数码球的子图像提取视觉特征的过程为：取出测试图片中的一个感兴趣区域子图像，把该兴趣区域堆成一个列向量用所有训练样本特征集合得到y的近似稀疏表达，即：

其中，β是稀疏系数向量。理想情况下，β中除了与y所属的类i相关的系数不为零外，其它所有系数都为零。但是，通常是β的大部分非零值都集中在第i类上，小部分非零值分散在其它类上。现在的问题是如何来求得β，从而获得y的近似表达。我们可以用下面lasso算法来实现：

用lasso(R.Tibshirani，Regression Shrinkage and Selection via the Lasso.Journal of the Royal Statistical Society，Series B，1996.)算法求得稀疏系数向量β，即：

$\arg \underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+\lambda {\left|\right|\beta \left|\right|}_1$

其中，||·||₁是l¹范数，λ||β||₁是l¹惩罚项。

(4)得到测试图片y的稀疏表达β后，接下来就是判断y属于哪个类。这个提取的特征在不同的类之间应该尽可能的不同。根据前面的稀疏表达，已经知道系数向量β的大部分非零值主要集中于测试样本所属的类，即其中，γ_i是与第i类相关的系数向量。为了估计测试样本所属的类，对于多幅图像进行识别，我们采取联合后验判决的方法实现。计算m次系数向量判断y属于第C_i类的多次后验概率，如下计算：

$p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)=\frac{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n_i}{\Sigma }}{\gamma }_{\left(\mathrm{ij}\right)l}}{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n}{\Sigma }}{\beta }_{\mathrm{jl}}}$

γ_ij是第i类在第j次计算得到的系数向量，γ_(ij)l是向量γij的第l个元素、然后，我们选择概率值最大的类作为测试图片y所属的类别，即：

$\underset{i}{\max }p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)$

下面的算法给出了图像的稀疏表达和判决分析过程，如图3所示：

输入：k个类的训练样本构成的矩阵由测试图片构成的列向量

输出：y所属的类标签m。

步骤1：用lasso求解问题：

$\arg \underset{\beta }{\min }\frac{1}{2}{\left|\right|y-\mathrm{A\beta }\left|\right|}_2^2+\lambda {\left|\right|\beta \left|\right|}_1;$

步骤2：计算多次的后验估计：

$p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)=\frac{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n_i}{\Sigma }}{\gamma }_{\left(\mathrm{ij}\right)l}}{\underset{j=1}{\overset{m}{\Sigma }}\underset{l=1}{\overset{n}{\Sigma }}{\beta }_{\mathrm{jl}}}$

步骤3：输出测试样本y所属的类标签m。

$\underset{i}{\max }p(y\in C_i|{\beta }_1,{\beta }_2,...,{\beta }_m)$