0 引言

在计算机视觉研究中,物体的定位及检测一直是重要的课题之一,它涉及多个学科并被运用到多种领域,诸如车牌检测^[1]、人脸双瞳定位^[2]、图像检索^[3]、人工智能^[4]、工业零件识别等。对于图像中目标的定位技术国内外研究中有许多相关的研究工作,常用的定位图像最小外接矩形的方法为旋转法或雷厄姆法,为了提高原有方法的准确度,Suesse等^[5]提出了一种新方法是基于区域低阶矩的特征找到最佳外接矩形;杨四海等^[6]构造了图像目标多边形的凸壳;卢蓉等^[7]采取离散格林法与顶点链码相结合的方式求取目标图像的最小外接矩形。在形态分析领域内的大部分工作都被包含在Bookstein等的研究成果中^[8-9],但他们只关心区域轮廓上的离散点集的拟合技术;李响等^[10]利用Zernike矩的模在空间上具有旋转不变性实现对物体的定位,但其幅角却会相差一个角度;张法全等^[11]利用重心原理使用区域的边界点代替所有内部点并结合最小二乘法确定目标物体的最小外接矩形的LSF(Linear Spectral Frequency)算法,效率较高但较适用于封闭图像，且仍存在对于寻找最小外接矩形面积不够小的问题;基于投影计算能量值找到主方向并对得到的初始矩形进行优化找到最小外接矩形的PRT(Projection Rotation Translation)算法^[12],较适用于带有镂空的物体图像,虽然利用投影结果较精确，但运算速度较慢^[13]。

在检测珠宝的最小外接矩形的过程中,提取珠宝图像中目标的主轴方向是关键所在。主成分分析(Principal Component Analysis,PCA)法是在统计目标特征基础上的多维正交的线性变换,在针对图像等离散型目标中一般称PCA为Hotelling变换,对高维数据降维应用广泛^[14]。二维主成分分析(Two-Dimensional PCA,2DPCA)法是在PCA的工作之上作出的改进，常用于对人脸的识别和目标的分类,但由于2DPCA在进行数据降维和分类的存储过程中需存储的系数较多,且在训练样本较小时,2DPCA运算时间会更多一点^[15],普适性不强。分块PCA等算法的鲁棒性在一定程度上并不如PCA^[16],而本文只需计算出目标的主轴方向,因此本文以主成分分析为基础提出一种检测珠宝的新方法:不规则珠宝的主轴方向应为目标图像的主分量方向,使用其主分量为基础作线性变换^[17],就能够去掉随机向量中各个元素间的相关性,然后对找到的主轴方向进行优化,最后确定目标的最小外接矩形完成对珠宝的自动定位及检测。

1 不规则珠宝的定位检测

利用几何形状进行目标定位技术的一般思路为:根据珠宝的形状特征,构造出一个几何模型,并设定一个相应的能量度来判断几何模型的姿态是否与珠宝相匹配,从而利用几何模型描述出珠宝尺寸信息。目标的外接矩形指的是能够完全包含目标图像上所有的点、线,且各边均与目标相切的矩形。一个珠宝的外接矩形能够有无穷多个,其中面积最小的称为最小外接矩形。由定义可知：目标的最小外接矩形是唯一的,其在一定程度上刻画了该目标的某些几何特征,由于本文以测量珠宝长宽尺寸值为前提,通过计算不规则目标的最小外接矩形可以从全局的角度描述目标图像的形状特征完成目标的定位,比计算珠宝的凸集更能达到所需珠宝属性,即获得珠宝的唯一长宽值,为后续的测量工作奠定基础,因此本文以最小外接矩形作为描述珠宝属性的模型。在现有的针对珠宝图像进行目标检测的算法中,文献^[12]提出了一种以投影为基础通过计算图像中每一个点的最大能量值以确定珠宝图像中目标的主轴方向,然后再通过姿态优化找到最佳矩形,最后通过平移进行尺寸优化找到珠宝的最小外接矩形的算法。但由于该方法在投影找主轴的过程中所用时间较长,增加了算法的复杂度,因此本文提出一种主成分析的珠宝自动定位及检测方法，用于对珠宝图像中目标的定位。

1.1 获取珠宝图像的质心

当背景色较复杂,需对珠宝图像采取阈值分割,然后再对珠宝图像进行边缘检测；当图像背景与珠宝颜色相近时,可使用梯度值腐蚀法,在边缘处检测每个点周围的四个点分别与这个点的颜色变化值,变化值绝对值小于一定阈值的归为同一集合,最终将待定位的目标从背景中提取出来。为更高效地验证本文算法的可行性,降低珠宝图像中定位目标的难度,本文将珠宝置于色彩单一的背景上拍摄,其中二值珠宝图像的面积由式(1)给出:

$A=\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{B\left[ i,j \right]}}$

(1)

对于二值图像B[i,j],珠宝的中心坐标与质心相同,因此使用式(2)~(3)求珠宝图像的中心位置(约定y轴向上):

$\bar{x}\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{B[i,j]=}}\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{jB[i,j]}}$

(2)

$\bar{y}\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{B[i,j]=}}-\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{iB[i,j]}}$

(3)

其中x和y是珠宝图像相对于左上角图像的中心坐标,具体为:

$\bar{x}=\frac{1}{A}\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{jB[i,j]}}$

(4)

$\bar{y}=-\frac{1}{A}\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{m-1}{iB[i,j]}}$

(5)

由于约定y轴向上,因此式(3)和式(5)的等号右边加了负号。

1.2 提取珠宝的主轴

求物体主轴方向的方法有很多,而对于不规则珠宝主轴的提取,为了找到更准确的方向,本文利用主成分分析法来提取其主方向。PCA常用于对数据的降维及压缩上,简而言之其作用就是既要突出主元的重要性,同时将主特征和次特征强烈地区分开。PCA的基本原理为如图 1所示,即将原坐标系使用y=kx+b表示的直线将其改写成(x,kx+b)的坐标形式,此时u₁的方向上包含了大部分的数据信息,故利用u₁方向的长轴代替原先的长轴和短轴描述数据,这样就能将二维数据降低为一维表示,图中辅助图形椭圆的长短轴差距越大,就越能够利用长轴表示大部分的信息。

由于Hotelling变换阵的基矢量与目标图像的去相关程度和相似程度有着密切的联系,目标图像的统计性质由自协方差矩阵、均值等表征。主成分分析的求解过程其实就是求协方差的特征向量和特征值然后再作数据转换,令x⁽ⁱ⁾为一个m×n的随机向量,x_j⁽ⁱ⁾为第i个向量的第j个特征,σ_j为x_j⁽ⁱ⁾的第j个特征的标准差。根据最大方差理论解释其过程如下:

设投影后的每一个样本点的每一维的特征均值全为0,故方差为:

$\begin{align} & \frac{1}{m}\sum\limits_{i=1}^{m}{({{\mathbf{x}}^{{{\mathbf{(i)}}^{\text{T}}}}}\mathbf{u}}{{)}^{2}}=\frac{1}{\text{m}}\sum\limits_{i=1}^{m}{{{\mathbf{u}}^{\text{T}}}{{\mathbf{x}}^{\mathbf{(i)}}}}{{\mathbf{x}}^{{{\mathbf{(i)}}^{\text{T}}}}}\mathbf{u} \\ & ={{\mathbf{u}}^{\text{T}}}(\frac{1}{\text{m}}\sum\limits_{i=1}^{m}{{{\mathbf{x}}^{\mathbf{(i)}}}}{{\mathbf{x}}^{{{\mathbf{(i)}}^{\text{T}}}}})\mathbf{u} \\ \end{align}$

(6)

用λ表示$\frac{1}{m}\sum\limits_{i=1}^{m}{({{\mathbf{x}}^{{{\mathbf{(i)}}^{\text{T}}}}}\mathbf{u}}{{)}^{2}}$,用R表示$\frac{1}{\text{m}}\sum\limits_{i=1}^{m}{{{\mathbf{x}}^{\mathbf{(i)}}}}{{\mathbf{x}}^{{{\mathbf{(i)}}^{\text{T}}}}}$即协方差,将式(6)写为:

$\lambda ={{\mathbf{u}}^{\text{T}}}R\mathbf{u}$

(7)

由于u为单位向量,式(7)可简化为uλ=uu^TRu=Ru,因此:

$R\mathbf{u}=\lambda \mathbf{u}$

(8)

其中：λ即为协方差R的特征值；u就是特征向量。主方向即为特征值λ对应的最大特征向量，找到的主轴即为如图 1中μ₁的方向。利用主成分分析法求协方差前的步骤为:

第1步 令特征向量$\mathbf{\mu }=\frac{1}{m}\sum\limits_{i=1}^{\text{m}}{{{\mathbf{x}}^{^{\mathbf{(i)}}}}}$;

第2步 将每一个随机向量x⁽ⁱ⁾替换为x⁽ⁱ⁾-μ;

第3步 令x_j⁽ⁱ⁾的第j个特征的方差${{\sigma }_{j}}^{2}=\frac{1}{m}\sum\limits_{i}{{{(\mathbf{x}_{\mathbf{j}}^{^{\mathbf{(i)}}})}^{2}}}$

第4步 将每一个x_j⁽ⁱ⁾替换为x⁽ⁱ⁾_j-μ。

因此,对珠宝图像利用主成分分析提取主轴的算法流程概括为:

步骤1 求目标的均值如式(9)所示:

$\left[ \begin{matrix} {\bar{x}} \\ {\bar{y}} \\ \end{matrix} \right]=E\left[ \begin{matrix} x \\ y \\ \end{matrix} \right]$

(9)

其协方差矩阵Z如式(10)所示:

$\mathbf{Z}=E\left\{ \left[ \begin{matrix} x-\bar{x} \\ y-\bar{y} \\ \end{matrix} \right] \right.\left. \left[ \begin{matrix} x-\bar{x} & y-\bar{y} \\ \end{matrix} \right] \right\}$

(10)

步骤2 由式(11)获得协方差矩阵Z的特征值λ₁及λ₂:

$\left| \left[ \begin{matrix} E\{{{(x-\bar{x})}^{2}}\}-\lambda & E\{(x-\bar{x})(y-\bar{y})\} \\ E\{(x-\bar{x})(y-\bar{y})\} & E\{{{(y-\bar{y})}^{2}}\}-\lambda \\ \end{matrix} \right] \right|=0$

(11)

步骤3 将特征值λ₁和λ₂代入$\mathbf{Z}{{\bar{\varphi }}_{\text{i}}}=\lambda {{\bar{\varphi }}_{\text{i}}}$中,并求出与特征值所对应的两个相互垂直的特征向量φ₁及φ₂,则φ₁和φ₂的方向即为珠宝的主轴方向和与主轴垂直的短轴方向,此时可以得到珠宝的初始矩形。

1.3 提取珠宝最小外接矩形 1.3.1 优化主轴方向

由于利用主成分分析法与图像样本点分布有关而造成算法存在一定的误差，因此需对提取到的主轴方向进行优化处理,使得得到的主轴方向更为理想。根据主成分分析找到的初始矩形,并不一定正好外接于珠宝,因此需对主轴方向进行姿态优化,对于旋转优化的区间只需在小范围的角度操作,旋转方向的判断依据为:首次旋转优化时,若此时珠宝矩形所包含的目标面积变大就按照此刻的方向继续优化;若旋转后矩形包含的图像面积变小,那么就以反向开始旋转优化。优化的具体过程步骤如下:

1) 提取初始矩形中心Q(x₀,y₀)平移置原点O,变换矩阵为K_s1;

2) 令图像绕点O顺时针旋转θ角,并变换此时矩阵为K_r;

3) 将旋转中心于坐标原点平移到原位置Q(x₀,y₀)且变换矩阵为K_s2。

故目标绕任意点Q(x₀,y₀)的优化过程,即为将每一像素点的齐次坐标的行向量的右乘变换矩阵:

$\begin{align} & \left[ \begin{matrix} {{x}^{'}} \\ {{y}^{'}} \\ 1 \\ \end{matrix} \right]={{K}_{s1}}\cdot {{K}_{r}}\cdot {{K}_{s2}}\cdot \left[ \begin{matrix} x \\ y \\ 1 \\ \end{matrix} \right]= \\ & \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ {{x}_{0}} & {{y}_{0}} & 1 \\ \end{matrix} \right]\cdot \left[ \begin{matrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \\ \end{matrix} \right]\cdot \\ & \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -{{x}_{0}} & -{{y}_{0}} & 1 \\ \end{matrix} \right]\cdot \left[ \begin{matrix} x \\ y \\ 1 \\ \end{matrix} \right]= \\ & \left[ \begin{matrix} \left( x-{{x}_{0}} \right)\cos \theta +\left( y-{{y}_{0}} \right)\sin \theta +{{x}_{0}} \\ -\left( x-{{x}_{0}} \right)\sin \theta +\left( y-{{y}_{0}} \right)\cos \theta +{{y}_{0}} \\ 1 \\ \end{matrix} \right] \\ \end{align}$

(12)

即:

$\left\{ \begin{matrix} {x}'=(x-{{x}_{0}})\cos \theta +(y-{{y}_{0}})\sin \theta +{{x}_{0}} \\ {y}'=(x-{{x}_{0}})\sin \theta +(y-{{y}_{0}})\cos \theta +{{y}_{0}} \\ \end{matrix} \right.$

(13)

图 2为按照θ=1°的旋转间隔以逆时针旋转对不规则图形提取到的主轴优化的过程图,在此过程中对于主轴的每一次优化都计算出以当前主轴为方向的矩形面积。可以看出,一共旋转了5次,其中矩形ABCD为以目标中心O旋转第4次后所得到的最优矩形,这是由于在第5次旋转后所得到的矩形面积有所增加即停止了优化,并提取出第4次优化后的矩形主轴和短轴,如图 2中的直线L和直线H为下一步找到最小外接矩形作准备。

如图 3所示,在第5次循环结束后所得到的矩形面积要大于第4次的结果,总运算次数由39次减少为5次,降低了运算复杂度,使算法更为高效。

1.3.2 获取最小外接矩形

在找到优化后的珠宝主轴方向后并无法直接得到目标的外接矩形,为此需将边缘检测后的目标图像按已找到的主轴L和短轴H的方向,计算最高最远和最低最远的边缘点,最后得出外接矩形的四个顶点完成对珠宝轮廓的描述。

令(x_g^p,y_g^p),g=1,2,…,n,是目标图像的m个边界点,将主轴表达式设为:

$\text{(y}-\bar{y})-\tan \theta (x-\bar{x})=0$

(14)

其中θ为优化后的主轴与水平线的夹角,设f(x,y)=(y)-tan θ(x),f(x_g^p,y_g^p)>0,点(x_g^p,y_g^p)分类为较高位置的边缘点;如果f(x_g^p,y_g^p)＜0,点(x_g^p,y_g^p)分类为较低位置的边缘点。判断已分好类的边缘点,找出珠宝图像上距离主轴最高最远和最低最远的两个交点;类似地,定义(y)+cot θ(x)=0求出图像上距离短轴最高最远和最低最远的两个交点。

在获得最远边界点后,就能够得到珠宝最小外接矩形的四个顶点:设点(x₁^p,y₁^p)和点(x₂^p,y₂^p)为珠宝上距离主轴最高最远和最低最远的两个交点;点(x₃^p,y₃^p)和点(x₄^p,y₄^p)为珠宝上距离短轴最高最远和最低最远的两个交点,则不规则珠宝的最小外接矩形的四个顶点可用如式(15)来计算：

$\left\{ \begin{align} & {{A}_{x}}=\frac{x_{1}^{p}\tan \theta +x_{3}^{p}\cot \theta +y_{3}^{p}-y_{1}^{p}}{\tan \theta +\cot \theta }, \\ & {{A}_{y}}=\frac{y_{1}^{p}\cot \theta +y_{3}^{p}\tan \theta +x_{3}^{p}-x_{1}^{p}}{\tan \theta +\cot \theta } \\ & {{B}_{x}}=\frac{x_{1}^{p}\tan \theta +x_{4}^{p}\cot \theta +y_{4}^{p}-y_{1}^{p}}{\tan \theta +\cot \theta }, \\ & {{B}_{y}}=\frac{y_{1}^{p}\cot \theta +y_{4}^{p}\tan \theta +x_{4}^{p}-x_{1}^{p}}{\tan \theta +\cot \theta } \\ & {{C}_{x}}=\frac{x_{2}^{p}\tan \theta +x_{3}^{p}\cot \theta +y_{3}^{p}-y_{2}^{p}}{\tan \theta +\cot \theta }, \\ & {{C}_{y}}=\frac{y_{2}^{p}\cot \theta +y_{3}^{p}\tan \theta +x_{3}^{p}-x_{2}^{p}}{\tan \theta +\cot \theta } \\ & {{D}_{x}}=\frac{x_{2}^{p}\tan \theta +x_{4}^{p}\cot \theta +y_{4}^{p}-y_{2}^{p}}{\tan \theta +\cot \theta }, \\ & {{D}_{y}}=\frac{y_{2}^{p}\cot \theta +y_{4}^{p}\tan \theta +x_{4}^{p}-x_{2}^{p}}{\tan \theta +\cot \theta } \\ \end{align} \right.$

(15)

2 实验结果及分析

将本文算法作用于真实珠宝图像,并与LSF算法^[11]和PRT算法^[12]作对比以体现本文的优势。其中,PRT算法的思想为:利用投影原理对全图像扫描,找出图像中能量值最大的点的方向,然后再通过旋转和平移得到的图像的最小外接矩形达到对图像位姿定位的目的;LSF算法的思想是:对利用重心原理并结合最小二乘法找到图像的最小外接矩形达到检测目的。

2.1 实验图像

由于不规则珠宝的轮廓形状复杂,并不具有规律的几何特征,无法直接获取其理想的最小外接矩形,因此需利用多人描绘珠宝的最小外接矩形求得平均值作为最佳值的方式来比较不同方法的误差。在实验400多枚珠宝后随机抽取了一些不规则珠宝进行检测,图 4即为使用不同算法于Matlab下得到的实验图。

2.2 实验配置

从实验图上并不能直观地比较出各个算法得到的外接矩形为最小,因此本文引入以下几个误差概念,进一步使用数据来比较各个算法的优劣。其中,相对误差为每个算法得到的最小外接矩形的面积与理想矩形面积差的比值,是个百分比,体现算法的相对差距;矩形度差较能体现出珠宝图像面积对于算法获得的矩形的填充度的百分比,从侧面反映出算法的准确程度;长宽比差为各个算法提取的目标图像主轴与短轴的比与理想值作比较所得到的误差,体现各算法获取的矩形拉伸度;主轴用时为各个算法提取珠宝主轴的时间(单位:s)。

设相对误差为:

$\eta =\frac{\left| {{S}_{\text{算法}}}-{{S}_{\text{理想}}} \right|}{{{S}_{\text{理想}}}}$

(16)

矩形度差为:

$T=\left| \frac{A}{{{S}_{\text{算法}}}}-\frac{A}{{{S}_{\text{理想}}}} \right|$

(17)

长宽比差为:

$V=\left| \frac{{{L}_{\text{算法}}}}{{{W}_{\text{算法}}}}-\frac{{{L}_{\text{理想}}}}{{{W}_{\text{理想}}}} \right|$

(18)

其中:A表示珠宝图像的区域面积;S_理想表示多人刻画计算平均值作为最佳值的外接矩形面积;L_理想表示最佳理想外接矩形长轴长;W_理想表示最佳理想外接矩形短轴长;S_算法表示算法获取的珠宝最小外接矩形面积; L_算法表示算法计算的目标最小外接矩形长轴长;W_算法表示算法计算的目标最小外接矩形短轴长。

2.3 实验结果及分析

图 5是不同算法下对于珠宝轮廓检测得到的最小外接矩形的相对误差曲线。能够看出本文算法获取的最小外接矩形的面积明显小于其他两种算法,说明本文算法的精确度更高。

图 6是不同算法计算主轴所用时间,可以看出基于投影的PRT算法找主轴时所用时间较多,而本文算法与LSF算法更为高效。

从图 5~6可看出，本文算法不仅得到的结果更为精确,且所用的时间短,算法更为高效。

表 1给出了采取不同算法检测不规则珠宝所得到的误差值,由于引用的主成分分析提取主轴方向,因此与珠宝图像点分布和物体轮廓的形状有关,可以看出本文算法对于细长型、对称性较强的珠宝形状能够获得更好的结果。从表 1中本文与PRT算法和LSF算法的各项误差的平均值对比,能够更加直观地从本文的相对误差(0.4%),矩形度差(0.8%)和长宽比差(4.5%)体现出本文算法较其他算法更加准确,从本文主轴提取时间约为LSF算法的50%,约为PRT算法的30%,本文算法大大节省了运算时间。

3 结语

主成分分析在最小均方差的理论下是最优变换,其在消除模式特征间的相关性、突出差异性方面均可达到最佳效果。本文将主成分分析用于对珠宝的自动定位及检测,以提取珠宝图像的形状特征,降低计算复杂度；且在定位检测珠宝位姿时,仅利用优化后的主轴线方向推导出珠宝最小外接矩形的四个顶点，减少了运算步骤，使得算法既准确又高效,能够精准快速地检测出珠宝的位姿。由于主成分分析产生的误差与图像样本点和对称性有关,因此本文算法更适用于细长型、对称性较强的珠宝。实验结果表明本文算法简单精确，具有强鲁棒性。