CN101493887A - 基于半监督学习和哈希索引的眉毛图像分割方法 - Google Patents

Abstract

本发明公开了一种基于半监督学习和哈希索引的眉毛图像分割技术，依次包括以下步骤：接受用户的原始眉毛图像，将眉毛图像划分成大小相等的小像素块，并通过计算机在眉毛区域内外分别选定一些像素块赋予不同的标号；将每个像素块均表示成向量的形式，并通过局部敏感的哈希方法计算出这些像素块之间的相似度，得到归一化的相似距离矩阵；利用基于图的半监督学习技术为没有标号的像素块打上标号，并从中提取出标号为眉毛的像素块，完成眉毛的提取工作。本发明因为利用局部敏感的哈希方法求解基于图的半监督学习技术中的相似距离矩阵，大大地提高了运用半监督技术进行图像分割的速度。

Description

基于半监督学习和哈希索引的眉毛图像分割方法

技术领域

本发明涉及一种基于半监督学习技术和局部敏感的哈希索引方法相结合的从原始眉毛图像中提取出纯眉毛图像的方法，属于电子信息技术领域。

背景技术

在现代社会中，随着计算机网络技术的高速发展和全球范围内电子商务的迅速兴起，信息安全显示出前所未有的重要性，而生物特征识别作为信息安全的一个重要方面开始越来越受到人们的重视。目前人们研究和使用的生物特征识别技术主要有：人脸识别、虹膜识别、指纹识别、手形识别、掌纹识别、人耳识别、签名识别、声音识别、步态识别、等等。眉毛作为人脸上的一个重要特征，具有作为识别特征的普遍性、唯一性、稳定性和可采集性。事实上，与人脸图像相比，眉毛图像不仅具有轮廓鲜明、结构简单和容易选取的优点，而且受光照和表情的影响较小，具有更好的稳定性和抗干扰性；与虹膜图像相比，眉毛图像则又具有易于采集和使用方便的优点。此外，人类的眉毛具有多种多样的形状，无固定结构，具有很好的身份特异性，因此能够被有效地应用于身份鉴别。

应用眉毛进行识别，一个重要的步骤就是眉毛图像的分割。图像分割历来是图像分析和模式识别的首要问题，也是图像处理的经典难题之一，它是图像分析和模式识别系统的重要组成部分，并决定图像的最终分析质量和模式识别的判别结果。目前，虽然有众多的自动分割图像的方法，包括：阈值法，聚类法，边缘检测等，但这些方法的分割结果却经常不是人们所期望的。与这些自动的分割方法相比，半自动的图像分隔技术更为实用，因此也受到了更多的关注。半自动或者交互的图像分割指通过借助人的帮助完成图像分割，代表性的工作包括：图切，随机漫步搜索，Lazy Snapping等。本质上，这些工作都可以纳入半监督学习分类的框架里面。

半监督学习技术是介于有监督学习和无监督学习之间的一种学习技术，其中给定的数据只有部分标注了类别。比如，χ＝{x₁，…，x_l，x_l+1，…，x_n}是一个给定的点集，χ中前l个点都有类别标号{y₁，...，y_l}，其中y_i∈t＝{1，...，c}(i＝1，...，l)，其余点没有标号，半监督学习的目标就是以某种最优准则来标注χ中没有标号的点。到目前为止，半监督学习技术有以下几种主要的实现方法：产生式模型(generative model)，自训练(self-training)，联合训练(Co-training)，图方法(graph based methods)等。本发明的目的在于提供一种基于图的半监督学习技术的眉毛图像分割技术。一般地，眉毛图像的分割由于受到头发、光照、姿势及表情的影响比之普通的图像分割更为困难。自动分割的方法几乎不可能正确的提取出眉毛图像，其他的眉毛图像分割方法比如：主成分分析和模板匹配，虽然能基本定位，但是也都不能准确标定眉毛的边界。

发明内容

本发明的目的是提供一种基于半监督学习技术和局部敏感的哈希方法，相结合的眉毛图像分割方法。

本发明是采用以下技术手段实现的：

本发明依次包括以下步骤：

步骤1；接受用户的原始眉毛图像，并将眉毛图像划分成大小相等的小像素块s×s，s的值可根据速度和精度要求选择s＝2，3，4，...，10.

步骤2；通过计算机从原始眉毛图像中选定一些眉毛点和非眉毛点，所有的像素块按照所包含的眉毛点与非眉毛点的多少给予相应的标号：如果眉毛点数大于非眉毛点数则该像素块的标号为1，反之为0；如果像素块中不包含任何选定的眉毛点和非眉毛点，则该像素块没有标号；

步骤3；所有的像素块均用向量表示，比如可以用五维向量(r，g，b，x，y)表示，其中r，g，b表示该像素块的RGB值的平均值，x，y表示该像素块的中心相对于左上角的坐标值。记所有的像素块对应的向量组成的集合为X，有标号的向量子集为L。通过局部敏感的哈希方法计算像素块之间的相似度，生成相似距离矩阵W，并归一化该相似距离矩阵为S，具体步骤如下：

步骤3.1；令d为像素块的维数，R为分割阈值(欧式距离小于R的像素块将于较大的概率散列到哈希表中的同一位置)，1-δ为希望成功做到距离小于R的像素块散列到哈希表中的同一位置的概率，w为哈希表的分割尺度，比如0≤h₁≤4，0≤h₂≤4，则认为h₁，h₂具有相同的哈希值；

步骤3.2；估算参数k和l，使得查询时间最少；

步骤3.2.1；通过计算机，从X中分别任意选出固定数目的向量，组成新的集合X_t和X_q；

步骤3.2.2；选定k为某固定常数，比如k＝16，l取为logδ/log(1-p₁ ^k)上取整，其中 $p_1={\∫}_0^w(1/w)(1/\mathrm{\π})e^{-t^2/2R^2}(1-t/R)\mathrm{dt};$

步骤3.2.3；通过计算机生成l个k维复合向量c_i＝(c_il，c_i2，...，c_ik)(1≤i≤l)，其中c_ij(1≤i≤l，1≤j≤k)为d维向量，且c_ijz(1≤i≤l，1≤j≤k，1≤z≤d)均为取自标准正态分布的实数；记这l个k维复合向量组成的集合为C；再通过计算机生成l个实数b_i(1≤i≤l)，其中b_i(1≤i≤l)均取自均匀分布U(0，w)；

步骤3.2.4；对X_t中的每一个向量x_t令：

p_ij＝(C_ij·x_t+b_i)/w(1≤i≤l，1≤j≤k)

其中·表示向量的点积；令向量p_i＝(p_i1，p_i2，...，p_ik)(1≤i≤l)，则x_t的l个哈希键值可表示为

其中表示上取整函数，a_u(1≤u≤k)取自均匀分布U(0，hashsize)，hashsize为哈希表H的长度，一般取为X_t的向量个数；哈希表H由每个哈希值到对应哈希桶的索引构成，而每个哈希桶则由X_t中具有相同哈希值的向量构成；

步骤3.2.5；按照x_t的l个哈希键值，依次将x_t装入H中该哈希键值对应的哈希桶中；

步骤3.2.6；对X_q中的每一个向量x_q：执行步骤3.2.4计算x_q的l个哈希键值，并用U_q表示所需要的时间；根据x_q的l个哈希键值，查找哈希表H中对应的哈希桶B_q，用T_q表示所有B_q的向量个数之和，用V_q表示总的查找时间；令u_q＝U_q/kl，令v_q＝V_q/l；计算所有B_q的每个向量和x_q之间的欧氏距离，所花费的时间记为G_q；令g_q＝G_q/T_q；

步骤3.2.7；令 $u=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{U}_q\right)/n,$ $v=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{v}_q\right)/n,$ $g=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{g}_q\right)/n,$ 其中n为集合X_q中的向量个数；

步骤3.2.8；利用u、v和g的值，估算新的k值，满足条件：

$k=\underset{1\≤k\≤100}{\arg \min }\left\{\underset{x_q\∈X_q}{\mathrm{\Σ}}(u\×k\×l+v\×l+g\×\mathrm{collision})\right\},$

其中l为logδ/log(1-p₁ ^k)的上取整值， $\mathrm{collison}=\underset{x_t\∈X_t}{\mathrm{\Σ}}{\∫}_0^w(1/w)(1/\mathrm{\π})e^{-x^2/2{\mathrm{dist}}^2}(1-x/\mathrm{dist})\mathrm{dx}$ (dist为x_t与x_q之间的欧氏距离)；

步骤3.2.9；根据新的k值，计算新的l为logδ/log(1-p₁ ^k)的上取整值；

步骤3.3；令X_t为X，执行步骤3.2.3至步骤3.2.5重新生成哈希表H；

步骤3.4；遍历整个哈希表H，对于X中任意两个向量x_i与x_j，若具有相同的哈希键值，则定义x_i与x_j之间的相似度为：

w_ij＝exp(-‖x_i-x_j‖²/2σ²)

其中σ为常数，否则定义t_i与t_j之间的相似度为0，由此得到相似距离矩阵W；

步骤3.5；归一化相似距离矩阵W，令

其中D为斜对角矩阵，且 $\begin{array}{c}S=D^{-\frac{1}{2}}W{D}^{-\frac{1}{2}}\\ D_{\mathrm{ii}}=\underset{j}{\mathrm{\Σ}}{w}_{\mathrm{ij}}\end{array};$

步骤4，依据步骤3得到的归一化相似矩阵S，采用基于图的半监督学习技术进行迭代计算，为没有标号的像素块打上标号，具体步骤如下：

步骤4.1；构造初始状态矩阵Y_n×2，其中n为X所含向量的总数，包括有标号的和无标号的向量，若x_i∈L为已标号向量中的眉毛块，则Y_i1＝1，Y_i2＝0；若x_i∈L是已标号向量中的非眉毛块，则Y_i2＝1，Y_i1＝0；否则，Y_i1＝Y_i2＝0；

步骤4.2；迭代计算F(t+1)＝αSF(t)+(1-α)Y直到收敛，其中F(0)＝Y，α是个介于0到1之间的常数；

步骤4.3；假设F^*为迭代的结果，则无标号向量x_i的标号取决于F_i ^*中最大的分量。即：若F_i1 ^*＞F_i2 ^*，则该向量对应的像素块属于眉毛区域，令像素块的标号为1；否则，该向量对应的像素块属于非眉毛区域，令该像素块的标号为0。

步骤5；根据迭代的结果，从原始眉毛图像中提取出与原始标号为1的像素块相连通且迭代结果为眉毛的像素块，完成眉毛的提取工作；

步骤5.1；令集合A为空集；任意取出一个眉毛像素块对应的向量o∈L，将o加入集合A，并将o的标号改为2；

步骤5.2；从集合A中任意取出向量a，令A＝A-{a}；以a对应的像素块为起点，在八个领域中查找标号为1的所有像素块加入集合A，并将这些像素块的标号改为2；

步骤5.3；执行步骤5.2直到集合A为空；

步骤5.4；把标号为2的像素块连成眉毛区域，并通过计算机把眉毛区域放到一个能够包含它的最小矩形中生成一幅256色的纯眉毛图像，眉毛区域外部和最小矩形之间的部分统一取为眉毛区域外部颜色的均值。

本发明的基本原理在于认为某个像素块是否属于眉毛区域可以通过它的近邻们判断，利用迭代的方法，把每个像素块的标号信息(是否属于眉毛区域)扩展到它的近邻直至达到一个全局稳态。

本发明与现有技术相比，具有以下明显的优势和有益效果：

本发明由于利用了先验信息，分割效果要比自动分割的方法具有更好的效果，此外因为采用了局部敏感的哈希方法计算基于图的半监督方法中的相似距离矩阵，所以具有比较快的分割速度。

实施例的实验效果明显，说明本发明可以在实际应用中进行眉毛图像的分割。在一个具体的实验中，选择5个人的40张原始眉毛图像进行实验，本发明都能正确的将眉毛从原始图像中的背景中切割出来。这么好的分割效果，是在室内一般自然光照条件下取得的，且对图像的成像质量并没有非常高的要求。所以，可以认为本发明具有非常高的实用价值。事实上，与自动分割图像的方法相比，因为头发，眼睫毛与眉毛同属毛发，自动分割的方法几乎不可能把眉毛从背景中完全正确的分离出来。其他的人机交互的图像分割方法中与本发明比较相似的包括微软的Lazy Snapping以及Fei Wang等人在CVPR’06上提出的应用LNP(Linear Neighborhood Propagation)进行图像分割的方法。这两个方法与本发明都是通过在原始图像中画上一些线或点标注清楚背景和前景来完成图像分割。与Lazy Snapping相比，应用Lazy Snapping进行眉毛图像分割，需要对眼睫毛，头发等与眉毛颜色相近的地方进行特别的标注，而本发明并不需要；此外，因为眉毛区域的边缘比较细微，复杂，Lazy Snapping在某些边界的标定上没有本发明准确。与LNP相比，LNP运行比较缓慢，而本发明因为采用了局部敏感的哈希方法求取相似距离矩阵，在运算速度上有大幅度的提高。

本发明在许多领域中具有重要的应用价值。比如，在眉毛识别中，可以利用本发明进行前期预处理提取出纯眉毛图像，建立眉毛数据库；又比如，可以作为某些图像处理软件的插件，只需要简单的在原图像上画上几笔，就能把需要的对象从背景中提取出来。

附图说明

图1为本发明流程示意图；

图2为原始眉毛图像的示意图；

图3为在原始眉毛图像上进行标注的示意图；

图4为纯眉毛图像的示意图；

图5为原始眉毛图像的效果图；

图6为在原始眉毛图像上进行标注的效果图；

图7为纯眉毛图像的效果图。

具体实施方式

根据图1配置本发明的实施例。本发明在实施时需要数码相机或数码摄像机之类的数字图像采集设备和具有一般图像处理能力的普通台式微机。具体实方案为：

步骤1；采用图像采集卡CG300、CP240松下摄像机和75mm高精度日本进口镜头组装成数字图像采集设备，微机选为DELL GX620型计算机；在一般的光照条件下采集原始眉毛图像，并将原始眉毛图像装入计算机中；通过计算机把图像处理成RGB彩色图像，并将眉毛图像划分成大小相等的一些小像素块，小像素块的大小为7×7；

步骤2；在计算机的显示器上显示出原始眉毛图像，如图2所示，并在图像上通过鼠标注上一些眉毛区域中的点和一些非眉毛区域中的点，图3是一个对图像中的点进行标注的例子，其中外围的黑线(彩色图像中的红线)表示非眉毛区域，眉毛中的白线(彩色图像中的绿线)表示眉毛区域；所有的像素块按照所包含的眉毛点与非眉毛点的多少给予相应的标号：如果眉毛点数大于非眉毛点数则该像素块的标号为1，反之为0；如果像素块中不包含任何选定的眉毛点和非眉毛点，则该像素块没有标号。

步骤3；所有的像素块均用五维向量(r，g，b，x，y)表示，其中r，g，b表示该像素块的RGB值的平均值，x，y表示该像素块的中心相对于左上角的坐标值；记所有的像素块对应的五维向量组成的集合为X，有标号的向量组成集合L；下面通过局部敏感的哈希方法计算像素块之间的相似度，生成相似距离矩阵W，并归一化该相似距离矩阵为S，具体步骤如下：

步骤3.1；令d＝5，w＝4，δ＝0.3，R＝20；

步骤3.2；估算参数k和l；

步骤3.2.1；通过计算机，从X中任意选出1000和100个向量，分别组成新的集合X_t和X_q；

步骤3.2.2；取定k＝16，l为logδ/log(1-p₁ ^k)的上取整值，其中

$p_1={\∫}_0^w(1/w)(1/\mathrm{\π})e^{-t^2/2R^2}(1-t/R)\mathrm{dt};$

步骤3.2.3；通过计算机生成l个k维复合向量c_i＝(c_i1，c_i2，...，c_ik)(1≤i≤l)，其中c_ij(1≤i≤l，1≤j≤k)为d维向量，且c_ijz(1≤i≤l，1≤j≤k，1≤z≤d)均为取自标准正态分布的实数；记这l个k维复合向量组成的集合为C；通过计算机生成l个实数b_i(1≤i≤l)，b_i(1≤i≤l)均取自均匀分布U(0，w)；

步骤3.2.4；对X_t中的每一个向量x_t令：

p_ij＝(C_ij·x_t+b_i)/w(1≤i≤l，1≤j≤k)

其中·表示向量的点积；令向量p_i＝(p_i1，p_i2，...，p_ik)(1≤i≤l)，则x_t的l个哈希键值可表示为

其中

表示上取整函数，a_u(1≤u≤k)取自均匀分布U(0，hashsize)，hashsize为哈希表H的长度，一般取为X_t的向量个数；哈希表H由每个哈希值到对应哈希桶的索引构成，而每个哈希桶则由X_t中具有相同哈希值的向量构成；

步骤3.2.5；按照x_t的l个哈希键值，依次将x_t装入H中该哈希键值对应的哈希桶中；

步骤3.2.6；对X_q中的每一个向量x_q：执行步骤3.2.4计算x_q的l个哈希键值，并用U_q表示所需要的时间；根据x_q的l个哈希键值，查找哈希表H中对应的哈希桶B_q，用T_q表示所有B_q的向量个数之和，用V_q表示总的查找时间；令u_q＝U_q/kl，令v_q＝V_q/l；计算所有B_q的每个向量和x_q之间的欧氏距离，所花费的时间记为G_q；令g_q＝G_q/T_q；

步骤3.2.7；令 $u=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{U}_q\right)/n,$ $v=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{v}_q\right)/n,$ $g=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{g}_q\right)/n,$ 其中n为集合X_q中的向量个数；

步骤3.2.8；利用u、v和g的值，估算新的k值，满足条件：

$k=\underset{1\≤k\≤100}{\arg \min }\left\{\underset{x_q\∈X_q}{\mathrm{\Σ}}(u\×k\×l+v\×l+g\×\mathrm{collision})\right\},$

其中l为logδ/log(1-p₁ ^k)的上取整值， $\mathrm{collison}=\underset{x_t\∈X_t}{\mathrm{\Σ}}{\∫}_0^w(1/w)(1/\mathrm{\π})e^{-x^2/2{\mathrm{dist}}^2}(1-x/\mathrm{dist})\mathrm{dx}$ (dist为x_t与x_q之间的欧氏距离)；

步骤3.2.9；根据新的k值，计算新的l为logδ/log(1-p₁ ^k)的上取整值；

步骤3.3；令X_t为X，执行步骤(3.2.3)至步骤(3.2.5)重新生成哈希表H；

步骤3.4；对于X中任意两个向量x_i与x_j，若具有相同的哈希键值，则定义x_i与x_j之间的相似度为：

w_ij＝exp(-||x_i-x_j||²/2σ²)

其中σ＝100为常数，否则定义t_i与t_j之间的相似度为0，由此得到相似距离矩阵W。归一化相似距离矩阵W，

步骤3.5；令

$S=D^{-\frac{1}{2}}W{D}^{-\frac{1}{2}}$

其中D为斜对角矩阵，且 $D_{\mathrm{ii}}=\underset{j}{\mathrm{\Σ}}{w}_{\mathrm{ij}};$

步骤4；依据步骤3得到的归一化相似矩阵S，采用基于图的半监督学习技术进行迭代计算，为没有标号的像素块打上标号，具体步骤如下：

步骤4.1；构造基于图的半监督学习技术中的初始状态矩阵Y_n×2，其中n为X所含向量的总数，包括有标号的和无标号的向量；若x_i∈L为已标号向量中的眉毛块，则Y_i1＝1，Y_i2＝0；若x_i∈L是已标号向量中的非眉毛块，则Y_i2＝1，Y_i1＝0；否则，Y_i1＝Y_i2＝0；

步骤4.2；迭代计算F(t+1)＝αSF(t)+(1-α)Y直到收敛，其中F(0)＝Y，α＝0.9；

步骤4.3；假设F^*为迭代的结果，则无标号向量x_i的标号取决于F_i ^*中最大的分量。即：若F_i1 ^*＞F_i2 ^*，则该向量对应的像素块属于眉毛区域，令像素块的标号为1；否则，该向量对应的像素块属于非眉毛区域，令该像素块的标号为0；

步骤5；根据迭代的结果，从原始眉毛图像中提取出与原始标号为1的像素块相连通且迭代结果为眉毛的像素块，完成眉毛的提取工作：

步骤5.1；令集合A为空集；任意取出一个眉毛像素块对应的向量o∈L，将o加入集合A，并将o的标号改为2；

步骤5.2；从集合A中任意取出向量a，令A＝A-{a}；以a对应的像素块为起点，在八个领域中查找标号为1的所有像素块加入集合A，并将这些像素块的标号改为2；

步骤5.3；执行步骤5.2直到集合A为空；

步骤5.4；把标号为2的像素块连成眉毛区域，并通过计算机把眉毛区域放到一个能够包含它的最小矩形中生成一幅256色的纯眉毛图像，眉毛区域外部和最小矩形之间的部分统一取为眉毛区域外部颜色的均值。

最后应说明的是：以上实施例仅用以说明本发明而并非限制本发明所描述的技术方案；因此，尽管本说明书参照上述的各个实施例对本发明已进行了详细的说明，但是，本领域的普通技术人员应当理解，仍然可以对本发明进行修改或等同替换；而一切不脱离发明的精神和范围的技术方案及其改进，其均应涵盖在本发明的权利要求范围当中。

Claims (5)

1、一种基于半监督学习和哈希索引的眉毛提取方法，其特征在于，依次包括以下步骤：

步骤1；接受用户的原始眉毛图像，并将眉毛图像划分成大小相等的小像素块s×s，s的值可根据速度和精度要求选择s＝2，3，4，...，10.

步骤2；通过计算机从原始眉毛图像中选定眉毛点和非眉毛点，所有的像素块按照所包含的眉毛点与非眉毛点的多少给予相应的标号：如果眉毛点数大于非眉毛点数则该像素块的标号为1，反之为0；如果像素块中不包含任何选定的眉毛点和非眉毛点，则该像素块没有标号；

步骤3；所有的像素块均用向量表示，比如可以用五维向量(r，g，b，x，y)表示，其中r，g，b表示该像素块的RGB对应分量的平均值，x，y表示该像素块的中心相对于左上角的坐标值；记所有像素块对应的向量组成的集合为X，其中有标号的子集为L；通过局部敏感的哈希方法计算像素块之间的相似度，生成相似距离矩阵W，并归一化该相似距离矩阵为S。

2、根据权利要求1所述的基于半监督学习和哈希索引的眉毛提取方法，其特征在于：所述的步骤3包括：

步骤3.1；令d为像素块的维数，R为分割阈值(欧式距离小于R的像素块将于较大的概率散列到哈希表中的同一位置)，1-δ为希望成功做到距离小于R的像素块散列到哈希表中的同一位置的概率，w为哈希表的分割尺度，比如0≤h₁≤4，0≤h₂≤4，则认为h₁，h₂具有相同的哈希值；

步骤3.2；估算参数k和l，使哈希表的查询时间最少。

3、根据权利要求2所述的基于半监督学习和哈希索引的眉毛提取方法，其特征在于：所述的步骤3.2包括：

步骤3.2.1；通过计算机，从X中分别任意选出固定数目的向量，组成新的集合X_t和X_q；

步骤3.2.2；选定k为某固定常数，比如k＝16，l为logδ/log(1-p₁ ^k)的上取整值，其中 $p_1={\∫}_0^w(1/w)(1/\mathrm{\π})e^{{-t}^2/{2R}^2}(1-t/R)\mathrm{dt};$

步骤3.2.3；通过计算机生成l个k维复合向量c_i＝(c_i1，c_i2，...，c_ik)(1≤i≤l)，其中c_ij(1≤i≤l，1≤j≤k)为d维向量，且c_ijz(1≤i≤l，1≤j≤k，1≤z≤d)均为取自标准正态分布的实数；记这l个k维复合向量组成的集合为C；通过计算机生成l个实数b_i(1≤i≤l)，b_i(1≤i≤l)均取自均匀分布U(0，w)；

步骤3.2.4；对X_t中的每一个向量x_t令：

p_ij＝(C_ij·x_t+b_i)/w(1≤i≤l，1≤j≤k)

其中·表示向量的点积；令向量p_i＝(p_i1，p_i2，...，p_ik)(1≤i≤l)，则x_t的l个哈希键值可表示为

其中“”表示上取整函数，a_u(1≤u≤k)取自均匀分布U(0，hashsize)，hashsize为哈希表H的长度，一般取为X_t的向量个数；哈希表H由每个哈希值到对应哈希桶的索引构成，而每个哈希桶则由X_t中具有相同哈希值的向量构成；

步骤3.2.5；按照x_t的l个哈希键值，依次将x_t装入H中该哈希键值对应的哈希桶中；

步骤3.2.6；对X_q中的每一个向量x_q：执行步骤3.2.4计算x_q的l个哈希键值，并用U_q表示所需要的时间；根据x_q的l个哈希键值，查找哈希表H中对应的哈希桶B_q，用T_q表示所有B_q的向量个数之和，用V_q表示总的查找时间；令u_q＝U_q/kl，令v_q＝V_q/l；计算所有B_q的每个向量和x_q之间的欧氏距离，所花费的时间记为G_q；令g_q＝G_q/T_q；

步骤3.2.7；令 $u=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{U}_q\right)/n,$ $v=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{v}_q\right)/n,$ $g=\left(\underset{x_q\∈X_q}{\mathrm{\Σ}}{g}_q\right)/n,$ 其中n为集合X_q中的向量个数；

步骤3.2.8；利用u、v和g的值，估算新的k值，满足条件：

$k=\underset{1\≤k\≤100}{\arg \min }\left\{\underset{x_q\∈X_q}{\mathrm{\Σ}}(u\×k\×l+v\×l+g\×\mathrm{collision})\right\},$

其中l为logδ/log(1-p₁ ^k)的上取整值， $\mathrm{collison}=\underset{x_t\∈X_t}{\mathrm{\Σ}}{\∫}_0^w(1/w)(1/\mathrm{\π})e^{-x^2/2{\mathrm{dist}}^2}(1-x/\mathrm{dist})\mathrm{dx}$ (dist为x_t与x_q之间的欧氏距离)；

步骤3.2.9；根据新的k值，计算新的l为logδ/log(1-p₁ ^k)的上取整值；

步骤3.3；令X_t为X，执行步骤3.2.3至步骤3.2.5重新生成哈希表H；

步骤3.4；遍历整个哈希表H，对于X中任意两个向量x_i与x_j，若具有相同的哈希键值，则定义x_i与x_j之间的相似度为：

w_ij＝exp(-‖x_i-x_j‖²/2σ²)

其中σ为常数，否则定义t_i与t_j之间的相似度为0，由此得到相似距离矩阵W；

步骤3.5；归一化相似距离矩阵W，令

$\text{S=}{\text{D}}^{-\frac{1}{2}}{\mathrm{WD}}^{-\frac{1}{2}}$

其中D为斜对角矩阵，且 $D_{\mathrm{ii}}=\underset{j}{\mathrm{\Σ}}{w}_{\mathrm{ij}};$

4、根据权利要求1所述的基于半监督学习和哈希索引的眉毛提取方法，其特征在于：所述得到的归一化相似矩阵S，采用基于图的半监督学习技术进行迭代计算，为没有标号的像素块打上标号，具体步骤如下：

步骤4.1；构造初始状态矩阵Y_n×2，其中n为X所含向量的总数，包括有标号的和无标号的向量，若x_i∈L为已标号向量中的眉毛块，则Y_i1＝1，Y_i2＝0；若x_i∈L是已标号向量中的非眉毛块，则Y_i2＝1，Y_i1＝0；否则，Y_i1＝Y_i2＝0；

步骤4.2；迭代计算F(t+1)＝αSF(t)+(1-α)Y直到收敛，其中F(0)＝Y，α是个介于0到1之间的常数；

步骤4.3；假设F^*为迭代的结果，则无标号向量x_i的标号取决于F_i ^*中最大的分量。即：若F_i1 ^*＞F_i2 ^*，则该向量对应的像素块属于眉毛区域，令像素块的标号为1；否则，该向量对应的像素块属于非眉毛区域，令该像素块的标号为0。

步骤5；根据迭代的结果，从原始眉毛图像中提取出与原始标号为1的像素块相连通且迭代结果为眉毛的像素块，完成眉毛的提取工作；

5、根据权利要求1所述的基于半监督学习和哈希索引的眉毛提取方法，其特征在于：所述步骤5包括：

步骤5.1；令集合A为空集；任意取出一个眉毛像素块对应的向量o∈L，将o加入集合A，并将o的标号改为2；

步骤5.2；从集合A中任意取出向量a，令A＝A-{a}；以a对应的像素块为起点，在八个领域中查找标号为1的所有像素块加入集合A，并将这些像素块的标号改为2；

步骤5.3；执行步骤5.2直到集合A为空；

步骤5.4；把标号为2的像素块连成眉毛区域，并通过计算机把眉毛区域放到一个能够包含它的最小矩形中生成一幅256色的纯眉毛图像，眉毛区域外部和最小矩形之间的部分统一取为眉毛区域外部颜色的均值。

Images