基于定性空间关系的卡通人物的脸部特征提取方法

1.一种基于定性空间关系的卡通人物的脸部特征提取方法，其特征在于，包括以下步骤：
步骤1：读取卡通人物的脸部图像；
步骤2：对边缘的提取、匹配处理以及确定镜像对称轴：
提取该脸部图像中的边缘，并将提取出的边缘对应的多个像素拟合成线段；
从所述的线段中，以线段作为边缘特征元素通过匹配操作识别出具有镜像对称关系的线段，并确定镜像对称轴；
步骤3：将线段聚合成序列，确定各边缘特征元素之间的“里/外”、“上/下”和“对称”定性空间关系，所述的边缘特征元素是指经过聚合的线段序列；
步骤4：基于定性空间关系显著性对边缘特征元素进行筛选；
步骤5：迭代式约束优化：
即基于卡通脸的定性空间关系模型确定每个通过筛选的边缘特征元素在脸部五官中的类属性；
脸部五官包括以下元素：眉毛、眼睛、鼻子、嘴巴和脸轮廓；
卡通脸的定性空间关系模型用于描述脸部五官各元素之间的里/外、上/下和对称关系；将被检测到的脸部五官的元素数目作为附加约束条件进行迭代，实现约束优化；
如果获得约束优化解，则进入下一步骤，否则继续约束优化；
步骤6：获得最优约束优化解：
若约束优化解为多个，则将每个解中标识为脸部五官的特征元素按对应五官的出现概率加权求和，选择该值最大的解作为最优约束优化解，脸部五官的出现概率根据样本卡通图像统计获得；
若约束优化解为一个，则该约束优化解为最优约束优化解；
步骤7：根据最优解中标识为脸部五官的边缘特征元素确定脸部五官的位置和形状，完成卡通人物的脸部特征提取。
2.根据权利要求1所述的基于定性空间关系的卡通人物的脸部特征提取方法，其特征在于，步骤2中：
用canny算子提取脸部图像中的边缘；
将边缘像素拟合成线段的方法是：任选一个尚未拟合过的边缘像素p0，且该像素的八连通邻域内应只有一个边缘像素，寻找其八连通相邻的边缘像素p1，记录二者连线的斜率k1；
寻找与p1相邻的下一个边缘像素p2，计算p1与p2的斜率k2，如果|k2-k1|≤0.6，则认为p0、p1与p2共线；重复这个过程直到第i个相邻边缘像素，其对应的斜率ki与k1之差的绝对值大于
0.6，则完成一条线段的拟合，该线段的两端点为p0和pi-1；
所述的匹配处理的过程为：对于由边缘像素拟合而形成的线段，计算每条线段的长度和斜率，找到与某一条线段呈镜像对称的线段：对任意线段j，计算与其呈完美镜像对称的线段j’的长度和斜率，线段j’是虚拟的线段；如果存在一个实际的线段i，其属性向量与j’的属性向量的欧式距离小于3，则认为线段j与线段i是镜像对称的；
欧式距离 其中v1和v2分别指边缘特征元素i和边缘特征元素j’所
对应的属性向量，v1k和v2k分别指边缘特征元素i和边缘特征元素j’所对应的属性向量中的第k个元素，属性向量中的第k＝1，2个元素分别为长度和斜率；
确定镜像对称轴的方法为：写出每一对呈镜像对称的边缘特征元素所对应的对称轴的直线方程，然后在直线方程的参数空间里进行霍夫变换，最后得到最显著的直线方程参数，其对应的直线即为图像中的镜像对称轴。
3.根据权利要求1所述的基于定性空间关系的卡通人物的脸部特征提取方法，其特征在于，在步骤3中，首先将上一步拟合得到的边缘线段聚合成线段序列，所谓线段序列是指首尾相连接的线段集合；
对任意两个线段序列，根据一个线段序列的端点与另一个线段序列的凸包来计算定性空间关系：
对于线段序列a和b，如果a的所有端点都位于b的凸包之内，则a和b的“里/外”关系为1；
若a的所有端点都位于b的凸包之外，则“里/外”关系为-1；若上述两个条件都不满足，则“里/外”关系为0；
线段序列a和b中若有80％的线段是呈镜像对称的，则认为a和b是呈镜像对称的；即a和b的镜像对称关系为1，否则为0；
若a的所有端点都位于b的凸包之上，则“上/下”关系为1；若a的所有端点都位于b的凸包之下，则“上/下”关系为-1；若上述两个条件都不满足，则“上/下”关系为0。
4.根据权利要求1所述的基于定性空间关系的卡通人物的脸部特征提取方法，其特征在于，步骤4中，
以线段序列为节点，以确定关系为边，所谓确定关系是值非0的定性空间关系；构建三个图，分别对应“里/外”、“上/下”和“镜像对称性”三组定性空间关系；
计算i节点的定性空间关系显著性 其中Wi为节
点i的显著性值，ωio、ωud和ωsm分别为“里/外”、“上/下”和“镜像对称性”的显著性权重；
和 分别为节点i在上述三个图中的度，度是指与该节点相关联的边的条数；
按照所有节点的定性空间关系显著性排序，取定性空间关系显著性排序在前60％的节点进行后续计算，将其它节点删除。
5.根据权利要求1所述的基于定性空间关系的卡通人物的脸部特征提取方法，其特征在于，步骤5中，
卡通脸的定性空间关系模型采用任意两个卡通脸部五官特征之间的定性空间关系的集合来表示，依据经验，“里/外”关系的集合如表1：
表1：
- B E N M F O
B 0 -1 -1 -1 1 0
E -1 0 -1 -1 1 O
N -1 -1 0 -1 1 0
M -1 -1 -1 0 1 0
F -1 -1 -1 -1 0 0
O 0 0 0 0 0 0
“上/下”关系集合如表2：
表2
- B E N M F O
B 0 1 1 1 0 0
E -1 0 1 1 0 0
N -1 -1 0 1 0 0
M -1 -1 -1 0 0 0
F 0 0 0 0 0 0
O 0 0 0 0 0 0
镜像对称性关系如下：
如果线段序列si和sj具有镜像对称性，则它们只可能属于眼睛、眉毛或非脸部特征；若si和sj不具有镜像对称性，则它们不可能属于眼睛或眉毛；如果si具有自镜像对称性，则它只可能属于脸部轮廓、嘴巴或者非脸部特征；若si不具有自镜像对称性则它不可能属于嘴巴或脸部轮廓；
将前述的定性空间关系转化为约束优化条件：
对于任意两个线段序列si和sj，其“里/外”关系的约束优化条件如公式1所示：
其中 是si和sj的“里/外”关系， 和 分别指si和sj的所属五官序号，
是五官 和 在表1中的“里/外”关系，Lo指非脸部特征序号；眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征的序号分别为0，1，2，3，4，5；
其“上/下”关系的约束优化条件如公式2所示：
其中 代表五官 和 在表2中的“上/下”关系， 是si和sj的“上/下”
关系；
其镜像对称性关系转化为约束条件如公式3所示：
其中Lb、Le、Lm、Lf和Lo分别代表眉毛、眼睛、嘴巴、脸部轮廓和非脸部特征的序号；眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征的序号分别为0、1、2、3、4和5；
基于以上约束条件采用约束优化方法滤除不满足约束条件的解空间取值，并在解空间中通过搜索得到所有满足约束条件的解，从而初步确定各线段序列分属于脸部五官中的哪一个。
6.根据权利要求1-5任一项所述的基于定性空间关系的卡通人物的脸部特征提取方法，其特征在于，在步骤5中，在第1轮迭代时，令被检测到的脸部五官数目等于M作为附加约束条件，其中M为定性关系模型中的脸部五官总数，如果通过约束优化找到解，则停止进行后续的约束优化，否则删除该附加约束条件；将脸部五官数目等于M-1作为新的附加约束条件，进行下一轮约束优化；每轮约束优化时附加约束条件中的检测到的脸部五官数目都比上一轮数目小1；如果经过(M-N+1)轮这样的约束优化后还是没有找到解，则约束优化失败，即没有找到任何卡通脸；其中N指在检测到的卡通脸中最少要包含的五官数目。

基于定性空间关系的卡通人物的脸部特征提取方法\n技术领域\n[0001] 本发明涉及一种基于定性空间关系的卡通人物的脸部特征提取方法，属于人工智能和计算机视觉技术领域。\n背景技术\n[0002] 随着动漫和数字娱乐业的蓬勃发展，卡通图像被大量生产出来。仅2012年一年我国就审批备案动画片536部433780分钟，在百度上可被搜索的卡通图片达到77,400,000张。\n“十二五”国家动漫产业发展规划提出：建设国家动漫公共素材库，以完善共享机制并降低企业创作成本。而从海量素材中实现有效的检索和共享，要对海量的卡通图像进行精准检索，需要计算机能够辨识卡通尤其是其脸部特征。因为脸是卡通角色的重要组成部分，通过脸部特征可以推断出角色的表情和身份，进而为用户提供丰富的检索选项。本发明提出了正面卡通脸部的特征提取方法，为实现卡通图像的智能分析和检索奠定基础。\n[0003] 现有的人脸特征提取方法大多基于对五官形状和表观(appearance)的统计建模，其中具有代表性的方法是主动形状模型(ASMs)、主动表观模型(AAMs)和它们的各种改进。\n这类方法要求目标形状和表观可以用线性统计模型表征，即变化不剧烈，否则其统计分布的方差会很大，进而模型对样本的表征精度就会降低。而这个要求通常是很难满足的，因为不同姿态、表情和个体的五官形状和表观可能差异很大。针对该问题可以将整体上难以统计表征的人脸分解为不同表情下的五官，并建立对应的局部ASMs模型。采用基于分而治之的策略，把对形状和表观的统计表征分解到单一表情和姿态层面，进而保证模型的表征精度。但这类方法需为每个卡通角色的形状和表观建立单独的统计模型，若用于处理成千上万的卡通角色，单是样本的采集标记和模型训练的任务量就超出了可控的范围。\n[0004] 除了形状和表观，还可以用脸部特征之间的位置关系来表征人脸。可以用马氏距离来表征人脸特征之间的相对位置关系；还可以用更具结构化的马尔科夫随机场来表征。\n但这些方法都是定量的。定量的方法对于人脸图像和素描是合适的，因为其中的人脸特征分布符合生理学规律，用线性高斯模型就能比较准确的表征。但卡通脸部中的特征分布可能是极端夸张的，在符合人脸大致拓扑结构的前提下可以不受生理学的限制，特征之间的相对距离和角度可以随意变化，因此其定量统计的分布方差大，模型的表征精度低。\n[0005] 因此，有必要设计一种新型的卡通人物的脸部特征提取方法。\n发明内容\n[0006] 本发明所要解决的技术问题是提供一种基于定性空间关系的卡通人物的脸部特征提取方法，该基于定性空间关系的卡通人物的脸部特征提取方法具有提取效率高和准确性性高等优点。\n[0007] 发明的技术解决方案如下：\n[0008] 一种基于定性空间关系的卡通人物的脸部特征提取方法，包括以下步骤：\n[0009] 步骤1：读取卡通人物的脸部图像；\n[0010] 步骤2：对边缘的提取、匹配处理以及确定镜像对称轴：\n[0011] 提取该脸部图像中的边缘，并将提取出的边缘对应的多个像素拟合成线段；\n[0012] 从所述的线段中，以线段作为边缘特征元素通过匹配操作识别出具有镜像对称关系的线段，并确定镜像对称轴；\n[0013] 步骤3：将线段聚合成序列，确定各边缘特征元素之间的“里/外”、“上/下”和“对称”定性空间关系，所述的边缘特征元素是指经过聚合的线段序列；\n[0014] 步骤4：基于定性空间关系显著性对边缘特征元素进行筛选；【选出定性空间关系显著的边缘序列，这些边缘序列位于脸部五官的概率较大】\n[0015] 步骤5：迭代式约束优化：\n[0016] 即基于卡通脸的定性空间关系模型确定每个通过筛选的边缘特征元素在脸部五官中的类属性；【用通俗的话来讲，即确定每一个边缘特征元素分属于脸部五官中的哪一个。】；\n[0017] 脸部五官包括以下元素：眉毛、眼睛、鼻子、嘴巴和脸轮廓；\n[0018] 卡通脸的定性空间关系模型用于描述脸部五官各元素之间的里/外、上/下和对称关系；将被检测到的脸部五官的元素数目作为附加约束条件进行迭代，实现约束优化；\n[0019] 如果获得约束优化解，则进入下一步骤，否则继续约束优化；\n[0020] 步骤6：获得最优约束优化解：\n[0021] 若约束优化解为多个，则将每个解中标识为脸部五官的特征元素按对应五官的出现概率加权求和，选择该值最大的解作为最优约束优化解，脸部五官的出现概率根据样本卡通图像统计获得；\n[0022] 若约束优化解为一个，则该约束优化解为最优约束优化解；\n[0023] 步骤7：根据最优解中标识为脸部五官的边缘特征元素确定脸部五官的位置和形状，完成卡通人物的脸部特征提取。\n[0024] 【根据最优解中标识为脸部五官的边缘特征元素获得脸部五官的位置和形状。比如所有被检测为属于嘴巴的线段序列，其所有端点可组成一个凸包，该凸包所在的位置即为嘴巴的位置，凸包的大小即为嘴巴的大小，凸包的轮廓即为嘴巴的轮廓。】\n[0025] 步骤2中：\n[0026] 用canny算子提取脸部图像中的边缘；\n[0027] 将边缘像素拟合成线段的方法是：任选一个尚未拟合过的边缘像素p0，且该像素的八连通邻域内应只有一个边缘像素，寻找其八连通相邻的边缘像素p1，记录二者连线的斜率k1；寻找与p1相邻的下一个边缘像素p2，计算p1与p2的斜率k2，如果|k2-k1|≤0.6，则认为p0、p1与p2共线；重复这个过程直到第i个相邻边缘像素，其对应的斜率ki与k1之差的绝对值大于0.6，则完成一条线段的拟合，该线段的两端点为p0和pi-1；\n[0028] 所述的匹配处理的过程为：对于由边缘像素拟合而形成的线段，计算每条线段的长度和斜率，找到与某一条线段呈镜像对称的线段：对任意线段j，计算与其呈完美镜像对称的线段j’的长度和斜率，线段j’是虚拟的线段；如果存在一个实际的线段i，其属性向量与j’的属性向量的欧式距离小于3，则认为线段j与线段i是镜像对称的；\n[0029] 欧式距离 其中v1和v2分别指边缘特征元素i和边缘特征元素\nj’所对应的属性向量，v1k和v2k分别指边缘特征元素i和边缘特征元素j’所对应的属性向量中的第k个元素，属性向量中的第k＝1，2个元素分别为长度和斜率；\n[0030] 通用公式为：欧式距离 其中Nv是向量中的元素个数；确定\n镜像对称轴的方法为：写出每一对呈镜像对称的边缘特征元素所对应的对称轴的直线方程，然后在直线方程的参数空间里进行霍夫变换，最后得到最显著的直线方程参数，其对应的直线即为图像中的镜像对称轴。\n[0031] 在步骤3中，首先将上一步拟合得到的边缘线段聚合成线段序列，所谓线段序列是指首尾相连接的线段集合；\n[0032] 对任意两个线段序列，根据一个线段序列的端点与另一个线段序列的凸包来计算定性空间关系：\n[0033] 对于线段序列a和b，如果a的所有端点都位于b的凸包之内，则a和b的“里/外”关系为1；若a的所有端点都位于b的凸包之外，则“里/外”关系为-1；若上述两个条件都不满足，则“里/外”关系为0；\n[0034] 线段序列a和b中若有80％的线段是呈镜像对称的，则认为a和b是呈镜像对称的；\n即a和b的镜像对称关系为1，否则为0；\n[0035] 若a的所有端点都位于b的凸包之上，则“上/下”关系为1；若a的所有端点都位于b的凸包之下，则“上/下”关系为-1；若上述两个条件都不满足，则“上/下”关系为0。\n[0036] 步骤4中，以线段序列为节点，以确定关系为边，所谓确定关系是值非0的定性空间关系；构建三个图，分别对应“里/外”、“上/下”和“镜像对称性”三组定性空间关系；\n[0037] 计算i节点的定性空间关系显著性 其中Wi\n为节点i的显著性值，ωio、ωud和ωsm分别为“里/外”、“上/下”和“镜像对称性”的显著性权重； 和 分别为节点i在上述三个图中的度，度是指与该节点相关联的边的条数；\n[0038] 按照所有节点的定性空间关系显著性排序，取定性空间关系显著性排序在前60％的节点进行后续计算，将其它节点删除。\n[0039] 步骤5中，\n[0040] 卡通脸的定性空间关系模型采用任意两个卡通脸部五官特征之间的定性空[0041] 间关系的集合来表示，依据经验，“里/外”关系的集合如表1：\n[0042] 表1：\n[0043]\n- B E N M F O\nB 0 -1 -1 -1 -1 0\nE -1 0 -1 -1 -1 0\nN -1 -1 0 -1 1 0\nM -1 -1 -1 0 1 0\nF -1 -1 -1 -1 0 0\nO 0 0 0 0 0 0\n[0044] “上/下”关系集合如表2：\n[0045] 表2\n[0046]\n- B E N M F O\nB 0 1 1 1 0 0\nE -1 0 1 1 0 0\nN -1 -1 0 1 0 0\nM -1 -1 -1 0 0 0\nF 0 0 0 0 0 0\nO 0 0 0 0 0 0\n[0047] 镜像对称性关系如下：\n[0048] 如果线段序列si和sj具有镜像对称性，则它们只可能属于眼睛、眉毛或非脸[0049] 部特征；若si和sj不具有镜像对称性，则它们不可能属于眼睛或眉毛。如果[0050] si具有自镜像对称性，则它只可能属于脸部轮廓、嘴巴或者非脸部特征；若[0051] si不具有自镜像对称性则它不可能属于嘴巴或脸部轮廓；\n[0052] 将前述的定性空间关系转化为约束优化条件：\n[0053] 对于任意两个线段序列si和sj，其“里/外”关系的约束优化条件如公式1所示：\n[0054]\n[0055] 其中 是si和sj的“里/外”关系， 和 分别指si和sj的所属五官序号，\n是五官 和 在表1中的“里/外”关系，Lo指非脸部特征序号；眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征的序号分别为0，1，2，3，4，5；\n[0056] 其“上/下”关系的约束优化条件如下式所示：\n[0057]\n[0058] 其中 代表五官 和 在表2中的“上/下”关系， 是si和sj的\n“上/下”关系；\n[0059] 其镜像对称性关系转化为约束条件如下式所示：\n[0060]\n[0061] 其中Lb、Le、Lm、Lf和Lo分别代表眉毛、眼睛、嘴巴、脸部轮廓和非脸部特征的序号。眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征的序号分别为0、1、2、3、4和5；\n[0062] 基于以上约束条件采用约束优化方法滤除不满足约束条件的解空间取值，并在解空间中通过搜索得到所有满足约束条件的解，从而初步确定各线段序列分属于脸部五官中的哪一个。\n[0063] 在步骤5中，在第1轮迭代时，令被检测到的脸部五官数目等于M作为附加约束条件，其中M为定性关系模型中的脸部五官总数，(在本实例中M＝5)，如果通过约束优化找到解，则停止进行后续的约束优化，否则删除该附加约束条件；将脸部五官数目等于M-1作为新的附加约束条件，进行下一轮约束优化；每轮约束优化时附加约束条件中的检测到的脸部五官数目都比上一轮数目小1；如果经过(M-N+1)轮这样的约束优化后还是没有找到解，则约束优化失败，即没有找到任何卡通脸；其中N指在检测到的卡通脸中最少要包含的五官数目(在本实例中N＝3)。\n[0064] 本发明具有以下特点：\n[0065] 1.用任意两个卡通脸部五官特征之间的定性空间关系的集合来表征卡通脸。定性空间关系包括：里/外，上/下和镜像对称性；\n[0066] 2.从图像中提取特征元素，特征元素包括：边缘或局部特征(local features)。根据特征元素的属性找到图像中的镜像对称轴，进而大致确定卡通脸的位置，因为卡通脸大多呈镜像对称性；\n[0067] 3.计算特征元素之间的“里/外”和“上/下”定性空间关系；\n[0068] 4.对特征元素进行筛选，选出定性空间关系显著性高的特征元素进行后续计算；\n[0069] 5.为每个通过筛选的特征元素搜索其所属的脸部五官，使卡通脸的定性空间关系模型得以最大程度的满足。将卡通脸的定性空间关系转化成约束优化条件，用约束优化方法(Constraint Programming)来实现上述搜索。\n[0070] 上述的步骤中，“里/外”和“上/下”两种定性空间关系都具有三个状态，可分别用\n1，0和-1表示。以五官特征A和B的“里/外”关系为例，状态“1”表示五官特征A在B“里”面，状态“-1”表示五官特征A在B“外”面，状态“0”表示A和B不存在稳定的“里/外”关系。图2和图3分别给出了由经验设定的脸部五官特征之间的“里/外”和“上/下”关系表。“镜像对称性”只有存在与否两个状态，由经验给定，如：左眼和右眼，左眉和右眉有镜像对称性；嘴巴和鼻子呈自对称性。\n[0071] 卡通脸的大致位置由图像中的镜像对称轴确定。正面卡通脸的轮廓、眼睛和嘴巴都与脸部中心线呈镜像对称。根据边缘或局部特征等元素的属性，可计算这些元素的镜像对称元素及属性；然后寻找与每个特征元素最匹配的对称特征元素，如果特征元素i的属性向量与其最匹配的对称特征元素j’的属性向量的欧式距离小于阈值H，则认为特征元素i与特征元素j是镜像对称的。每一对呈镜像对称的特征元素都对应一条对称轴，写出这些对称轴的直线方程，然后在直线方程的参数空间里进行霍夫变换，最后得到最显著的直线方程参数，其对应的直线即为图像中的镜像对称轴。与该轴呈镜像对称的特征元素的包围盒代表了卡通脸的大致位置和尺度。\n[0072] 在计算特征元素之间的“里/外”和“上/下”定性空间关系时，先边缘拟合成线段，然后根据一方的端点与另一方的端点凸包来计算定性空间关系；如边缘线段a和b，如果a的所有端点都位于b的凸包之内，则a和b的“里/外”关系为1；若a的所有端点都位于b的凸包之外，则“里/外”关系为-1；若上述两个条件都不满足，则“里/外”关系为0。\n[0073] 特征元素的定性空间关系显著性由该元素与其他元素的确定关系数目来度量，所谓确定关系是值非0的定性空间关系。以特征元素为节点，以确定关系为边，可以构建三个图，分别对应“里/外”、“上/下”和“镜像对称性”三组定性空间关系。根据图中节点的度可以衡量对应特征元素的定性空间关系显著性。节点显著性的取值为该节点在上述三个图中的度的加权平均值。权重可以根据经验设置为1/3，1/3和1/3；也可以通过统计样本图像中的特征元素关系获得。图4给出了一个卡通头像及其对应的特征元素的空间关系显著性图示例。\n[0074] 有益效果：\n[0075] 本发明的基于定性空间关系的卡通人物的脸部特征提取方法，用脸部五官特征之间的定性空间关系来表征卡通脸，从图像中提取边缘或局部特征等元素的定性空间关系，并筛选出定性空间关系显著的元素，通过约束优化方法为这些筛选出图像元素找到所属的五官，进而提取出五官特征的位置和形状。\n[0076] 本发明的方法能够提取正面卡通脸部特征的形状和轮廓，解决现有人脸特征提取方法不能有效处理卡通图像的问题。与现有方法不同，它不需要依赖对形状和表观的统计建模来表征人脸，而是采用五官特征之间的定性空间关系来把握脸部模式，无论卡通脸如何夸张或简化其定性空间关系和拓扑关系是相对稳定的，因此本发明能够有效表征和提取卡通脸部特征。针对500张卡通图像的实验表明，本发明对卡通脸部特征的成功检测率为\n77.3％，而现有方法中最优秀的的STasm和SDM方法的成功检测率分别为43.6％和52.4％，本发明的检测精度明显高于现有方法。图5给出了本发明进行卡通脸部特征检测的结果示例。此外本发明通过定性空间关系显著性筛选，大大减少了需要约束优化的图像元素数目，降低了计算复杂度，提高了计算速度。用未经优化的Python程序设计语言实现了本发明，在没有进行筛选前，500张卡通图像的平均处理速度为11秒；筛选后，平均处理速度降低为6秒。\n附图说明\n[0077] 图1是本发明的流程图。\n[0078] 图2是由经验设定的脸部五官特征之间的“里/外”关系表。图中B代表眉毛(eyeBrow),E代表眼睛(Eyes),N代表鼻子(Nose),M代表嘴巴(Mouth),F代表脸轮廓(Face outline)，O代表非脸部特征(outlier)。图中“里/外”关系的取值可为：1(代表“里”),-1(代表“外”)or 0(代表“无里外关系”)。\n[0079] 图3是由经验设定的脸部五官特征之间的“上/下”关系表。图中B、E、N、M、F和O的意义与图2相同。图中“上/下”关系的取值可为：1(代表“上”),-1(代表“下”)or 0(代表“无上下关系”)。\n[0080] 图4是一个卡通头像及其对应的特征元素的空间关系显著性图。其中有5个子图，左数第1个图为卡通图像，第2个图是从该卡通图像中提取的八个特征元素(分别用数字标识)，第3个图是特征元素之间的“里/外”关系显著性图，第4个图是特征元素之间的“上/下”关系显著性图，第5个图是特征元素之间的“对称”关系显著性图。\n[0081] 图5是本发明进行卡通脸部特征检测的结果示例。其中有7列子图，左数第1列显示了卡通图像；第2列显示了脸部特征提取的总体结果，被提取到的脸部五官用加粗的黑色线条勾勒，非五官特征元素用灰色线条勾勒；从第3列至第7列分别显示了被提取到的眉毛、眼睛、鼻子、嘴巴和脸轮廓，对应的五官特征元素被粗黑线勾勒。\n具体实施方式\n[0082] 以下将结合附图和具体实施例对本发明做进一步详细说明：\n[0083] 实施例1：\n[0084] 具体流程如图1所示，现介绍每一步的实现细节。\n[0085] 卡通脸部特征的定性空间关系模型的说明：\n[0086] 建立卡通脸部特征的定性空间关系模型，即用任意两个卡通脸部五官特征之间的定性空间关系的集合来表征卡通脸。定性空间关系包括：里/外，上/下和镜像对称性。可以根据经验设定这些关系。图2和图3给出了由经验设定的“里/外”和“上/下”关系。镜像对称性也可以由经验设定为：\n[0087] ●一对眉毛呈镜像对称性\n[0088] ●一对眼睛呈镜像对称性\n[0089] ●嘴巴呈自镜像对称性\n[0090] ●脸部轮廓呈自镜像对称性\n[0091] 在第5步会说明如何将上述定性空间关系转化成约束优化的条件。\n[0092] 1.读取卡通人物的脸部图像；\n[0093] 2.从图像中用经典的canny算子提取边缘。将边缘像素拟合成线段，具体做法是：\n任选一个尚未拟合过的边缘像素p0(且该像素的八连通邻域内应只有一个边缘像素，这样的像素可看作是一条线段的端点)；寻找其八连通相邻的边缘像素p1，记录二者连线的斜率k1；寻找与p1相邻的下一个边缘像素p2，计算p1与p2的斜率k2，如果|k2-k1|≤0.6，则认为p0、p1与p2共线；重复这个过程直到第i个相邻边缘像素，其对应的斜率ki与k1之差的绝对值大于0.6，则完成一条线段的拟合，该线段的两端点为p0和pi-1。\n[0094] 完成边缘像素的线段拟合后，可以根据线段的属性【斜率和长度】寻找图像中的与该线段具有镜像对称的其他线段，进而大致确定卡通脸的位置。根据边缘的属性(斜率和长度)，可计算这些元素【元素即线段】的y轴镜像对称元素及属性；然后寻找与每个特征元素【特征元素即线段】最匹配的对称特征元素，如果特征元素i的属性向量与其最匹配的对称特征元素j’的属性向量的欧式距离【对于向量v1和v2而言，其欧式距离\n其中Nv是向量中的元素个数，v1i和v2i指向量v1和v2中的第i个元\n素】小于阈值3，则认为特征元素i与特征元素j是镜像对称的。每一对呈镜像对称的特征元素都对应一条对称轴，写出这些对称轴的直线方程，然后在直线方程的参数空间里进行霍夫变换【霍夫变换在图像处理和模式识别中很常用，其作用是检测不完美的目标，其特点是在参数域中用投票的策略来达成目的。比如这里要检测对称轴，每两个呈镜像对称的线段都能确定一个对称轴，但其中肯定有一些对称轴是逻辑上重叠的而实际中不重叠的。比如左右眼的两条对称线段的对称轴和左右眉毛中两条对称线段的对称轴是逻辑上重叠的，但实际由于光照、边缘提取和拟合的计算误差不可能在数值上完美重合。因此要想知道图像中的对称轴到底在哪里就需要用霍夫变换，将每两个对称线段对应的对称轴变换到直线的参数空间(如：横轴是斜率，纵轴是截距)，每一次这样的变换就相当一次投票。投票结束后，参数空间中某个位置的数值比较大(得到的票数较多)，那么这个位置对应的直线就很可能是对称轴。】，最后得到最显著的直线方程参数，其对应的直线即为图像中的镜像对称轴。与该轴呈镜像对称的特征元素的包围盒代表了卡通脸的大致位置和尺度。【包围盒是个长方形，其顶点位置的计算方法是这样的：每个与对称轴呈镜像对称的线段都有两个端点，所有这些端点构成一个二维点集，该点集的最小x和最小y坐标对应包围盒的一个顶点位置，该点集的最大x和最大y坐标对应包围盒的另一个顶点位置，这两个顶点分别位于该长方形的对角线两端。】\n[0095] 3.计算边缘特征元素之间的“里/外”、“上/下”和“对称”定性空间关系。首先将上一步拟合得到的边缘线段聚合成线段序列，所谓线段序列是指首尾相连接的线段集合。对任意两个线段序列，可以根据一方的端点与另一方的端点凸包来计算定性空间关系；如边缘序列a和b，如果a的所有端点都位于b的凸包之内，则a和b的“里/外”关系为1；若a的所有端点都位于b的凸包之外，则“里/外”关系为-1；若上述两个条件都不满足，则“里/外”关系为0。序列a和b中若有80％的线段是呈镜像对称的，则认为a和b是呈镜像对称的。若a的所有端点都位于b的凸包之上，则“上/下”关系为1；若a的所有端点都位于b的凸包之下，则“上/下”关系为-1；若上述两个条件都不满足，则“上/下”关系为0。\n[0096] 4.对边缘特征元素进行筛选，选出定性空间关系显著性高的特征元素进行后续计算。特征元素的定性空间关系显著性由该元素与其他元素的确定关系数目来度量，所谓确定关系是值非0的定性空间关系。以特征元素为节点，以确定关系为边，可以构建三个图，分别对应“里/外”、“上/下”和“镜像对称性”三组定性空间关系。根据图中节点的度【度是拓扑学中的概念，对于某个节点，其度指与该节点相关联的边的条数】可以衡量对应特征元素的定性空间关系显著性。节点显著性的取值为该节点在上述三个图中的度的加权之和。\n其中Wi为节点i的显著性值，ωio、ωud和ωsm分别为\n“里/外”、“上/下”和“镜像对称性”的显著性权重，权重可以根据经验设置为1/3，1/3和1/3，和 分别为节点i在上述三个图中的度。图4给出了一个卡通头像及其对应的特征\n元素的空间关系显著性图。以其中的节点7为例，其显著性值为2/3+5/3+2/3＝3，因为该节点在第一个图中的度是2，在第二个图中的度是5，在第三个图中的度是2，且三个图的权重都为1/3。按照这种方法可以计算出所有节点的显著性，并将节点按照显著性从高到低排序，排序结果为：7,5,6,1,3,2,4,8，其中非五官节点2、4、8的显著性是最低，取前60％的节点进行后续计算的话，则这些非五官节点都会被筛除掉，这样做既可以减少计算量又不会引入系统误差。\n[0097] 5.为每个通过筛选的边缘特征元素搜索其所属的脸部五官，使卡通脸的定性空间关系模型得以最大程度的满足。将卡通脸的定性空间关系转化成约束优化条件，用约束优化方法(Constraint Programming)来实现上述搜索。\n[0098] 首先将图2中的“里/外”关系转化为约束优化条件。以任意两个线段序列si和sj为例，如果它们分属不同的五官，则它们的“里/外”关系应该与图2中其对应五官的关系一致。\n其对应的约束优化条件如公式1所示：\n[0099]\n[0100] 其中 是si和sj的“里/外”(“In/Out”)关系， 和 分别指si和sj的所属五官序号， 是五官 和 在图2中的“里/外”关系，Lo指非脸部特征(outlier)序\n号。眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征(outlier)的序号分别为0，1，2，3，4，5。公式\n1中四个相乘的因子诠释了图2中的定性关系。比如：若左数第一个因子为0，意味着当把线段序列si和sj分别检测为 和 时，si和sj的“里/外”关系与 和 在图2中的“里/外”关系一致，即特征检测的结果与定性空间关系模型一致，此时后面三个因子取任意值，公式1都成立；若左数第2个因子为0，意味着si和sj被检测为归属于同一个五官，此时其他因子取任意值公式1都成立，这是因为图2中对角线元素都为0，即对同一个五官而言不存在空间关系约束；若第3或第4个因子为0，则意味着si或sj被认定为非脸部特征，此时其他因子取任意值公式1都成立，这是因为非脸部特征不受图2中定性关系的约束。\n[0101] 可以仿照公式1将“上/下”关系转化为约束条件，该约束条件的形式与公式1一致，区别在于新公式中的 被替换成 其中后者代表五官 和 在图3中\n的“上/下”(Up/Down)关系。\n[0102]\n[0103] 其中 是si和sj的“上/下”(“Up/Down”)关系。\n[0104] 将对称性关系转化为约束条件的思路是：如果线段序列si和sj具有镜像对称性，则它们只可能属于眼睛、眉毛或非脸部特征；若si和sj不具有镜像对称性，则它们不可能属于眼睛或眉毛。如果si具有自镜像对称性，则它只可能属于脸部轮廓、嘴巴或者非脸部特征；\n若si不具有自镜像对称性则它不可能属于嘴巴或脸部轮廓。上述思路可以用公式3概括：\n[0105]\n[0106] 其中Lb、Le、Lm、Lf和Lo分别代表眉毛、眼睛、嘴巴、脸部轮廓和非脸部特征的序号。眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征(outlier)的序号分别为0、1、2、3、4和5。\n[0107] 约束优化方法(Constraint Programming)是一类擅长在离散域中求解有约束条件的组合优化问题的方法。这类方法可以运用约束条件，快速滤除不满足条件的解空间取值，并高效地在解空间中通过搜索得到所有满足条件的解。在本实例中，约束优化的目标变量是 i＝1,Λ,Ns，其中Ns是通过筛选的线段序列数目。 的取值域为0、1、2、3、4和5，它们分别代表眉毛，眼睛，鼻子，嘴巴，脸轮廓，非脸部特征(outlier)的序号。\n[0108] 6、将被检测到的脸部五官数目作为附加约束条件，进行迭代式约束优化，这样做的目的是尽量快地找到那些检测到尽量多的脸部五官的解。在第1轮迭代时，令被检测到的脸部五官数目等于M作为附加约束条件(其中M为定性关系模型中的脸部五官总数，在本实例中M＝5)，如果通过约束优化找到解，则停止进行后续的约束优化，否则删除该附加约束条件；将脸部五官数目等于M-1作为新的附加约束条件，进行下一轮约束优化。每轮约束优化时附加约束条件中的检测到的脸部五官数目都比上一轮数目小1。如果经过(M-N+1)轮这样的约束优化后还是没有找到解，则约束优化失败，即没有找到任何卡通脸。其中N指在检测到的卡通脸中最少要包含的五官数目；N越大，约束越强，N的取值可以根据要求设定。在本实例中N＝3。\n[0109] 7、如果通过约束优化找到了多个解，则根据脸部五官出现的概率来选择最优解。\n将每个解中标识为脸部五官的特征元素按对应五官的出现概率加权求和，得到的数值越大则认为该解越符合统计规律，选择该值最大的解作为最优解。五官的出现概率可以根据样本卡通图像统计获得。若约束优化解为一个，则该约束优化解为最优约束优化解；\n[0110] 8、最后，根据最优解中标识为脸部五官的边缘特征元素获得脸部五官的位置和形状。比如所有被检测为属于嘴巴的线段序列，其所有端点可组成一个凸包，该凸包所在的位置即为嘴巴的位置，凸包的大小即为嘴巴的大小，凸包的轮廓即为嘴巴的轮廓。