Branch-and-price Algorithm for Rolling Batch Scheduling Problem in Continuous-casting and Rolling Processes with Hybrid Production Mode
-
摘要: 研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标，建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解，提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题，采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界，最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法，执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题，提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题，在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间，加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验，结果显示所提出改进策略能够突破求解能力的限制，使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.Abstract: This paper studies a new type of rolling batch scheduling problem arising in continuous casting and rolling processes which are linked by the hybrid production mode of direct hot charge rolling (DHCR), hot charge rolling (HCR) and cold charge rolling (CCR). The problem is formulated as an integer programming model with the objective of minimizing heat energy loss due to cooling (Waiting) of HCR slabs (Hot ingots) and productivity loss caused by changeover of rolling shelves. Since the commercial optimization software is difficult to obtain an optimal solution or even a feasible solution of the model within a limited CPU time, the model is decomposed into a master problem and a set of subproblems using the Dantzig-Wolfe decomposition. The master problem and subproblems are iteratively solved through column generation algorithm to obtain a tighter lower bound of the original problem. Finally, the column generation algorithm acting as a bounding mechanism is embedded into the branch-and-bound framework to form a branch-and-price algorithm which performs the branch search process to obtain an integer optimal solution. Furthermore, key factors affecting the performance of the algorithm are analyzed and corresponding improvement strategies are proposed. For the master problem, a solution strategy of hybriding column generation and Lagrangian relaxation is proposed to restrain the tailing-off effect of column generation. For the pricing subproblem, a dominance rule and label lower bound calculation based method is proposed to eliminate non-promising state space early in the dynamic programming algorithm such that the solution procedure is speeded up. Numerical experiments are carried out on actual production data provided by a steel company and random instances extended from actual production data. The results show that the proposed improvement strategies can break through the limitation of the solving ability and enable the branch-and-price algorithm to solve industrial scale problem optimality within an acceptable CPU time.
-
人脸作为重要的视觉信息在人与人交互中传递大量信息.很多系统已经能够准确的识别人脸的年龄、表情和性别等信息[1-5], 人脸的人种、民族在人类学和计算视觉具有重要的实用价值.随着日益频繁的国际和地区往来, 在安保、公共安全、犯罪识别、海关签证、边境口岸都具有广泛的应用价值[6-8].同时, 相关研究会促进各种人脸分析识别系统对于不同人种和民族的技术公平性, 使得系统具有更好的适用性, 避免出现一些系统只适于部分族群而产生的技术"歧视"[8].如何利用计算机技术深入分析和挖掘人脸的群体特征及其规律, 对推进和深化人脸识别技术和人类学研究也同样具有重要意义.
人种是指人类学用肤色、头发、身体结构等差异加以区分的人群.民族是指在特定地理区域和遗传因素形成的具有特定文化和语言的人群共同体.人脸的这些群体特征是人脸视觉认知中先于年龄、性别和表情识别的最重要的人脸信息之一.神经科学研究表明, 人脸的人种特征是人脸最先识别的特征.如图 1所示, 在80 ~ 120 ms首先识别人脸的人种属性, 接下来在150 ms识别人脸年龄和性别等特征进行认知[9].体质人类学也对人脸的人种和民族特征进行了大量研究, 采集大量不同人种和民族数据通过人体测量学对人脸几何特征进行统计分析[10-11].体质人类学对人脸长度、角度等进行测量构建相应的指标体系, 这些指标体系支撑了体质人类学的发展.随着机器视觉和人脸分析技术不断发展, 进一步完善体质人类学对提高民族特征指标体系具有有效性, 通过结合数据构建科学的指标体系对体质人类学研究具有重要科学意义. Bledsoe[12]最早利用面部几何特征之间的距离和比率, 分析了白种人的面部特征; Kanade[13]对眼角、嘴巴和下巴等面部特征之间几何关系, 在一个自建的20个白种人数据库上进行了分析; Brunelli等[14]通过47个样本的白人数据库, 研究了人脸部件几何结构(例如鼻子长度、嘴巴宽度和下巴形状等)之间的匹配关系, 研究表明, 通过人脸的几何特征可以有效地判别和分析人脸的民族特征.此外, 人脸的族群特征由于相互融合, 同一人脸可以包含多个人种或民族的特征, 这也给人脸的族群特征分析带来了一定的困难.同一人种的不同民族人脸面部特征研究与不同人种的面部特征研究不同, 不同人种人脸肤色和体貌特征之间差异较大, 同一人种包含多个民族, 同一民族人脸差异要小于人种之间的差异[15]. 1991年Lindsay等发现对同人种面孔的记忆力比对不同人种的要好[16], 这主要由于日常接触同族人群较多, 因此人们对本民族人脸认知要快于异族人群.但目前机器视觉领域中, 人脸民族特征相关研究主要集中于不同人种的人脸特征差异研究, 而对于同人种内的不同民族研究较少.中国属于亚裔黄种人, 人口占全世界20 %, 是一个统一的多民族国家, 由于受地域、生活方式和遗传等因素的影响形成了56个民族, 并分布于我国横跨的5个时区之中[17], 如何更好地利用计算机技术科学揭示和研究中国不同民族面部具有重要的科学意义.
流形学习(Manifold learning)可从高维采样的数据空间中恢复低维的流形结构, 找到高维空间中的低维流形, 并求出相关映射.流形分析不仅可以实现高维数据降维, 还可以可视化分析数据本质和内在规律[18]. 2010年Seung和Lee在Science发表的"认知的流形模式"探讨了人类视觉感知机制, 证实了人类视觉神经系统可以捕获这种非线性流形结构的能力, 提出视觉感知的流形假说[19].当识别人脸图像由于光照变化, 表情、年龄、姿态和视觉方向产生变化, 人类视觉的高维空间中会产生一个由光照、表情、年龄和姿态等变量控制的低维流形; 但对于人脸民族特征是否在不同个体存在由族群特征控制的低维流形还有待进行研究. 2015年文献[20]指出, 人脸族群或民族特征的流形相关工作还未展开.而对于中国不同民族的人脸特征, 本文作者[21-24]早期建立了中国多民族人脸数据库, 并利用人脸图像特征对部分民族的人脸特征进行了前期研究, 研究表明中国的不同民族面部特征间也存在多样性.人脸民族特征的流形结构研究需要建立多民族数据库.本文将通过构建多民族人脸数据对中国人脸面部民族特征的内在规律进行研究, 对比体质人类学人脸面部特征的测量指标, 进而研究人脸民族特征.
1. 相关工作
流形学习分析人脸数据在高维空间中的低维流形是人脸识别和分析研究的热点之一.流形学习对数据进行结构学习, 产生可靠的嵌入投影, 将数据投射到低维的子空间表示, 去除冗余信息, 找到更为紧凑的本质特征表示方法.传统的流形线性子空间算法有主成分分析(Principal component analysis, PCA)[25]、线性判别分析(Linear discriminant analysis, LDA)[26]、独立成分分析(Independent component correlation algorithm, ICA)[27]、二维主成分分析(Two-dimensional principal component analysis, 2DPCA)[28]、二维线性判别分析(Two-dimensional linear discriminant analysis, 2DLDA)[29]等. Tenenbaum等提出两种流形学习算法, 局部线性嵌入(Locally linear embedding, LLE)和等距映射(Isometric feature mapping, Isomap)[30], 针对LLE方法矩阵分解的不稳定和对噪声敏感等缺点, 拉普拉斯特征映射(Laplacian eigenmaps, LE)[31]理论于2003年被Belkin团队提出, 该方法是在谱分析理论的基础上发展起来的.由于LLE和LE等非线性降维方法没有显式地给出映射关系, 只能得到训练样本的低维嵌入, 难以获得新样本点的低维投影, 于是He等给出了局部保持投影(Locality preserving projection, LPP)[32-33]的概念, 它是LE的线性化推广.因为LLE和LE具有一样的不足, He团队又针对LLE进行改进, 这才有了近邻保持嵌入(Neighborhood preserving embedding, NPE)[34].詹德川等[35]在Isomap的基础上引入了集成学习方法, 利用坐标相关性来度量可视化效果.何力等[36]提出了从放大因子和延伸方向两个角度出发来讨论维数约简过程中样本点改变前与新形成的对应关系.曾宪华等[37] 2007年提出了基于人脑增殖学习原理的动态增殖流行学习算法. Chen等[38]在LPP的基础上进行二维推广, 提出一种二维局部保持投影(Two-dimensional neighborhood preserving embedding, 2DLPP)算法, 直接在二维矩阵上从行方向执行维数约简操作. 2011年, 张大明等[39]把NPE拓展到二维, 即二维近邻保持嵌入(Two-dimensional neighborhood preserving embedding, 2DNPE)算法, 解决了NPE可能遭遇奇异值的问题.
流形学习不仅可作为人脸识别的特征分析方法, 还被用于人脸年龄和表情的语义分布结构内在规律研究[40-43], 在人脸的年龄流形研究中, Guo等在2008年对人脸年龄流形结构进行研究[43], 实验表明不同年龄呈现流形结构, 如图 2(a)所示, 在0 ~ 45岁人脸呈现均匀的流形分布, 60岁以上样本流形结构分布较为混杂; 在人脸的面部表情流形研究中, 文献[42]在Frey人脸表情库[44]上执行Isomap, 中性表情、高兴的正表情和不高兴的负表情依次在个体流形呈现如图 2(b)的低维空间结构不同个体的人脸表情图像会形成不同的表情流形.续爽等在图嵌入的框架下分析人脸表情子空间, 将分散于高维图像空间中的6个个体表情流形都统一到低维子空间内的一个流形上, 如图 2(c)所示, 证实了来自不同个体的表情数据按表情的语义流形分布[45].
图 2 人脸年龄和表情属性的流形语义分布Fig. 2 Semantic distribution of age and facial expression attributes中国人类学学者已经通过人体测量学对我国不同民族进行了面部特征研究, 进而分析各民族及族群的起源、进化和融合过程[46-47].随着数据采集设备不断发展, 以人脸的二维和三维形状分析为基础的形态测量学或人体测量学[48]及几何形态测量学[49]应运而生, 一些难以量化的非线性测量指标, 例如不规则形状的角度、曲度、面积都可以通过相关采集设备进行计算获得相应数据.利用人脸特征点定位可以准确获得人脸各种几何特征数据, 基于人脸图像和三维模型的人脸几何形态测量学成为分析人脸的重要途径之一[50].本文构建了中国分布不同区域的三个民族的人脸数据集, 在此基础上, 结合人类学研究文献对广西壮族、吉林朝鲜族和新疆维吾尔族体质的面部特征研究总结出20个常用人脸面部几何特征, 如图 3所示.通过这20个人脸几何特征分析不同民族的低维流形空间结构.这20个人脸几何特征包括面宽$(x_{1})$、下颌宽$(x_{2})$、形态面高$(x_{3})$、额头高$(x_{4})$、容貌面高$(x_{5})$、鼻宽$(x_{6})$、嘴宽$(x_{7})$、两眼外宽$(x_{8})$、眼裂宽$(x_{9})$、鼻高$(x_{10})$、两眼内宽$(x_{11})$、下脸高$(x_{12})$、眉周长$(x_{13})$、眼周长$(x_{14})$、鼻周长$(x_{15})$、嘴周长$ (x_{16})$眉面积$(x_{17})$、眼面积$(x_{18})$、鼻面积$(x_{19})$、嘴面积$(x_{20})$.
人脸特征数据集表示为${\{ x_{1}, x_{2}, \cdots, x_{n}\}}$, 每一张人脸图像的几何特征数据可以表示为${ x_{i}\in {\bf R}^{D}}$, D代表每个图像的特征数量.假设${\{ x_{1}, x_{2}, \cdots, x_{n}\}}$实际是一种$d$维的流形结构$M$嵌入到${{\bf R}^{D}}$空间中, 其中${(d\ll D)}$, 那么, 就有可能找到一组新的低维数据${\{ y_{1}, y_{2}, \cdots, y_{n}\}}$来表示这组人脸几何特征数据集, 其中${y_{i} \in {\bf R}^{D}}$.如图 4所示, 其中深色代表朝鲜族, 中浅色代表维吾尔族, 浅色代表壮族.本文将人脸数据库中的3个民族按性别分为2组, 图 4(a)为男性组, 图 4(b)为女性组, 分散于Laplacian[51]和LPP[52]流形结构.
图 4 壮族(浅色)、维吾尔族(中浅色)、朝鲜族(深色)男女流形结构Fig. 4 Male and female manifold structure of three ethnies (Zhuang, Uygur, Korean)如图 4所示, 在体质人类学指标体系下, 3个民族数据集Laplacian拉普拉斯和LPP流形空间数据分布混杂在一起, 不同民族数据样本没有形成各自民族语义的子流形结构.主要由于体质人类学测量指标在主要人脸的器官及各个器官相对位置定义的几何特征维度较低, 没有有效刻画民族的人脸几何特征, 这些指标特征没有能够描述不同民族群体人脸特征差异性.因此未形成相应的民族语义子流形.课题组前期在人类学指标体系下对我国几个少数民族进行研究, 利用AFS概念语义化在人类学指标体系下抽取人脸语义特征进行分析研究, 也发现体质人类学指标对于民族属性识别率较低.因此本文主要探索以下两个问题: 1)中国各民族人脸特征是否存在按民族语义分布的子流形结构. 2)人脸中的哪些几何特征能够刻画人脸的民族属性.
本文将利用中国3个民族人脸数据特征研究不同民族语义流形结构.
2. 多民族人脸数据集
本文为研究中国各民族的人脸特征, 根据区域分布选取3个民族建立数据集.如表 1所示, 中国百万以上人口的民族及其地理位置, 选取位于东北、西北和南部的3个民族进行分析, 主要由于位于较远不同地域的民族区分度较大, 同一区域内的民族可能会由于人口流动造成数据区分度较小.
民族 人口数量 人口比例(%) 地理位置 壮族 16 926 381 1.27 广西 维吾尔族 10 069 346 0.76 新疆 朝鲜族 1 830 929 0.14 吉林 本文采集了我国分布较远的3个民族, 位于广西的壮族、新疆的维吾尔族和吉林的朝鲜族作为数据集[54]. 3个民族的地理分布如图 5所示.
每个民族采集100人, 其中男、女各50人, 从高校各民族本科生采集, 采集对象年龄集中于18 ~ 22岁, 可以降低年龄因素对民族特征的影响.
为了准确采集中国多民族人脸数据库.实验室采用如图 5所示的篮箱系统和多机位相机对人脸进行采集.图 6为采集的3个民族人脸数据部分样本[54].本文公开采集的具有民族标记和人脸特征点的数据集为其他领域相关研究提供数据1.
1http://zs.dlnu.edu.cn/minzu300face.rar
3. 人脸特征点定位及相似度计算
人脸几何形态特征作为体质人类学分析民族特征的测量体系, 主要研究基础是基于颅面的测量.其他指标, 例如肤色纹理和颜色等易于受外界环境变化影响.此外, 基于图像的人脸民族几何特征与人体测量学既有联系又有区别.人类学建立于对于颅面几何特征精确测量, 而基于图像的人脸的特征点之间的像素点距离进行计算, 不是实测的几何特征, 需要进行归一化, 而角度和比例特征不随人脸图像大小变化影响, 具有较好稳定性.要测量长度、角度或者比例特征依赖于对人脸重要特征点的精确定位算法.
本文采用Stasm算法对人脸进行标注[55].主要由于Stasm标注特征点相对较少, 这样生成的其他几何特征相对规模较小.如图 7所示, 共77个特征点以及特征点标定的位置.
4. 人脸高维几何特征筛选
人脸包含高维的几何特征.人脸特征维度图示如图 8所示.一张480像素× 640像素的人脸包含像素特征30.72万个, 但由77个特征点会生成2 926个长度特征、21万余个角度特征、410万个比例特征和组成.比例特征远远高于人脸的像素特征.
设人脸特征点集合为$F={\left[l_{1}, l_{2}, \cdots, l_{n}\right]^{ \rm{T}}}$, $N$ = $77, $其中长度特征为${d(l_{i}, l_{j})={\|l_{i} - l_{j}\|}^{2}}$, 角度特征为
$ \begin{align} {\beta}_{i}={{\arccos}}\frac{d({{l}}_{{i}}, {{l}}_{{j}})^{2}+d({{l}}_{{i}}, {{l}}_{{q}})^{2}-d({{l}}_{{j}}, {{l}}_{{q}})^{2}} {2\times d({{l}}_{{i}}, {{ l}}_{{j}})\times d({{l}}_{{i}}, {{l}}_{{j}})} \end{align} $
(1) 比例指数为
$ \begin{align} r=\frac{d({l}_{i}, {l}_{j})}{d({l}_{a}, {l}_{b})} \end{align} $
(2) 其中, ${\forall {l}_{i}, {l}_{j}, {l}_{a}, {l}_{b}\in\{ { l}_{1}, { l}_{2}, \cdots, {l}_{n}\}}$.
由于人脸结构基本上为左右对称, 因此几何特征存在大量冗余特征.本文采用LE和LLE流形算法, 对未筛选冗余特征的2 926维的长度数据集进行流形分析, 如图 9所示.
从图 9可以看出, 直接采用人脸全部长度特征进行流形分析, 不同民族样本流形分布混杂在一起, 没有形成各自民族的子流形结构, 主要由于人脸的相对左右对称存在大量冗余特征, 因此需要从高维的特征中筛选掉冗余特征.考虑到特征之间的相关性和冗余性, 本文利用基于空间搜索的最大相关最小冗余(Minimal redundancy maximal relevance, mRMR)算法[56-57]对几何特征进行筛选. mRMR算法使用互信息衡量特征的相关性与冗余度, 并使用信息差和信息熵两个代价函数寻找特征子集, 其基本思想是基于互信息的最大统计依赖准则来获得较好的特征. mRMR算法中最大相关和最小冗余定义为
$ \max\{{D}({F}, {c}), {D}\}=\frac{1}{|{F}|}\sum\limits_{{x}_{i}\in{S}}{I}({ f}_{r}, {c}) $
(3) $ \max\{{R}({F}), {R}\}=\frac{1}{|{F}|^{2}}\sum\limits_{{f}_{r}, {f}_{0}\in{ F}}{I}({f}_{r}, {f}_{0}) $
(4) 其中, $F$为人脸几何特征, $c$为样本民族属性类别, ${{I}({f}_{r}, { c})}$表示特征${{f}_{r}}$与类别$c$之间的互信息, ${{I}({f}_{r}, { f}_{0})}$表示特征${{f}_{r}}$与特征${{f}_{0}}$之间的相互信息.
给定两个随机变量${x}$和${y}$, 设它们的概率密度分别为${p(x)}$, ${p(y)}$和${p(x, y)}$, 则它们之间的互信息定义为
$ \begin{align} {{I}{({x}, {y})}}=\iint p(x, y) {\rm log}\frac{{p}{({x}, {y})}}{{p}{({x})}{p}{({y})}}{\rm d}x{\rm d}y \end{align} $
(5) mRMR算法利用下式作为评价函数进行特征子集的选择.
$ \begin{align} \begin{cases} \max\phi _{1}\left ( D, R \right ), &\phi _{1}=D-R\\ \max\phi _{2}\left ( D, R \right ), &\phi _{2}= \dfrac{D}{R} \end{cases} \end{align} $
(6) 由于人脸几何特征数据维度较高, 传统数据库只适用于特征维度较低的数据集.本文采用mongoDB数据库, 将维度较高的角度与比例特征数据进行存储.实验中, 为了提高算法效率将219 450个角度特征切分22个独立数据集分别利用mRMR进行筛选, 每个数据集包含角度特征9 975个; 将4 279 275个比例特征分为455个独立的数据集, 每个数据集包含比例特征9 405个, 如表 2所示筛选的几何特征.
表 2 筛选的几何特征Table 2 The selected geometric features长度几何特征 角度几何特征 比例几何特征 特征维度 2 926 219 450 4 279 275 筛选后特征维度 195 250 500 长度特征在mRMR特征权重值$score\geq 0$条件下, 筛选出195个距离特征; 在角度数据集分割为22个独立的子数据集, 从每个子数据集特征权重$score$ $>$ $0.23$的特征, 共筛选出1 535个角度特征, 合并1 535个角度特征形成新数据集继续进行筛选, mRMR权重$score\geq 0$条件下, 筛选出250个角度特征; 在455个的比例子数据集, 本文利用mRMR分别对每个子数据集根据权重$score\geq 0.23$的标准共筛选出7 124个比例特征, 再利用筛选出的7 124个比例特征形成新数据集继续进行计算, 最终在权重$score\geq 0$条件下, 筛选出500个比例特征.
根据图 10中的多民族人脸流行分析流程, 本文从mRMR对人脸特征筛选特征中构建3个民族人脸长度数据集、角度数据集和比例数据集, 进而利用流形分析方法对不同数据集的样本空间结构进行可视化, 并验证在该特征指标下是否不同民族人脸在空间中存在民族语义的子流形结构, 进而用分类器验证筛选后特征的有效性.
5. 不同几何特征下的人脸流形分析
本节对长度、角度及比例特征类别下的5个不同特征集合的数据集进行流形分析, 观察和研究不同特征指标体系下的人脸民族的样本空间流形结构.
5.1 多民族人脸长度特征流形分析
人脸几何长度一直是体质人类学分析民族和族群的重要指标, 77个特征点包含2 926个长度特征. 图 4的实验数据表明, 在体质人类学的人脸几何测量指标中, 不同族群样本集中在低维空间子流形结构.由于其中含有冗余的长度特征, 因此本文利用mRMR筛选出195个特征长度, 构建包含3个民族人脸数据样本的数据集.
从2 926个特征中筛选出来的195个几何长度特征, 按权重进行排序.本文将每个长度的特征权重根据Score分为5部分: [0.15, 0.452), [0.10, 0.15), [0.05, 0.10), [0.01, 0.05), (0, 0.05), 将前4个不同权重范围的长度特征区域在表 3进行显示, 并与人类学的指标进行对比, 其中字体加粗的鼻宽、鼻高、唇厚、口裂宽存在于筛选出的195个长度特征之中.
表 3 mRMR筛选的4个权重范围的长度特征Table 3 The selected distance-based features by mRMR权重 权重区域特点 1 眼裂宽度、眉眼距离、眉与鼻翼距离、鼻翼长度特征 2 眉毛各长度特征、额头宽度、鼻翼与眼内角距离、下唇厚度 3 更为精细的鼻部和嘴部几何长度特征 4 嘴部与眉尖距离, 嘴部与下颚距离, 眉与耳朵距离 人类学常用指标体系 头长、头宽、面宽、鼻宽、鼻高、唇厚、口裂宽、内眼角宽、外眼角间距、内眼角间距、颧间宽、下颌长度、下颌角间距 为了更为直观分析影响这些通过mRMR筛选的人脸几何长度的语义特征, 本文将4个权重范围特征在人脸进行可视化.一类权重用19个距离特征点表示, 二类权重用37个距离特征点表示, 三类权重用63个距离特征点表示, 四类权重用65个距离特征点表示, 如图 11所示.通过4个不同权重区间的长度可以观察到, 如图 11(a)和图 11(b)所示, 眉毛、眼睛和鼻子组成的T形区域的长度特征与人脸的民族特征语义相关性较强.特征描述从T形区域延伸到嘴部区域.主要表现在上唇和下唇的长宽相关性较强, 这与人类学常用指标一致.
从图 11和表 3可以看出, 1)筛选出的权重较高, 人脸长度特征与人体测量学对民族研究指标略有不同.其中人体测量学只有4个指标与mRMR算法得到的长度指标相同, 其余指标没有包含在195个筛选特征集合中; 2)与民族相关的人脸特征主要集中于眉眼区域和鼻翼区域, 以及眉、眼睛和鼻部三者之间的距离长度; 3)脸型与民族特征相关性较差, 除脸型周围的特征点集合中除脸部标记耳部特征点被作为与眉部被选取外, 表明脸型的颧骨周围特征点及长度都没有被选取; 4)鼻头部的精细长度与民族特征相关性较强, 在权重3的范围内, 鼻部区域的各种长度特征被更为精细的刻画, 而这鼻头部的各种几何特征度量一致被研究忽视; 5)除传统人类学的鼻宽和额高, 在权重4的范围内, 嘴部区域与民族特征相关性较强, 主要表现在上唇和下唇的长宽相关性较强, 这与人类学常用指标一致.
通过mRMR从2 926个特征筛选195个长度特征, 本文对筛选后的数据集进行流形学习.如图 12所示, 采用LE拉普拉斯和LLE对数据进行流形分布可视化.其中深色代表朝鲜族, 中浅色代表维吾尔族, 浅色代表壮族, 都能在空间内形成与民族语义相关的子流形结构分布.
图 12 筛选长度特征数据集的流形结构Fig. 12 The illustration of ethnic manifold structure based on selected features按民族语义分布的子流形结构表明, 3个民族人脸数据集样本在长度筛选后的特征指标中能够形成各自相对独立的子流形分布结构.也验证了筛选后长度特征的有效性, 这些特征长度可以一定程度刻画不同民族的差异性.
5.2 多民族人脸角度特征流形分析
人脸角度特征点也是人脸几何特征之一.例如内外眼角角度表示眼睛的形状, 耳际点与下颚角度可以一定程度表示人脸长度比例等.人脸的角度特征不仅可以表示人脸单个部件器官内部的角度, 还可以表达人脸不同器官部件之间关系.在人脸77个特征点共包含219 450个角度特征.采用mRMR筛选多民族人脸数据集的角度间的相关性和冗余性, 并构建特征数据集进行流形分析.本文利用筛选后的角度特征通过角点和特征区域对4个权重角度的角点及其相关点集进行描述, 如表 4所示, 并对其中特征区域进行说明.
表 4 mRMR筛选的4个权重范围的角度特征Table 4 The selected angle features by mRMR权重 角点 权重区域特点 1 眉尖点 眉毛与内眼角点和鼻根部形成的角度关系 2 鼻根点, 眉尖点, 形成鼻翼与鼻眼角度关系热区, 耳位置点 通过角度度量眉眼距离关系 3 眉、眼角点 眼裂角度, 眉眼之间角度关系, 鼻翼角度关系 4 眉和嘴部 更为精细的眼鼻嘴之间定位关系 为进一步刻画不同权重角度特征, 找出能区分人脸民族属性的角度特征, 本文对不同权重角度特征进行可视化, 如图 13所示.从这些角度特征中选取出250个权重较高的角度特征, 每个角度特征可用上述距离特征(边)之间的夹角表示, 并根据权重大小分为4个不同权重范围的角度特征.三角着色的"热区"是该区域角度都是权重较高的角度特征.
图 13和表 4表明, 权重较高与民族特征相关的人脸角度特征主要是眉、眼、鼻三者之间的布局关系, 人脸局部角度特征集中于眼睛开裂角度和鼻翼角度.分析结论与人脸的长度特征计算出的民族特征显著区域基本一致.
本文采用传统的PCA和LDA对角度进行流形分析. PCA是1986年Jolliffe提出的线性降维技术.线性判别式分析LDA, 也叫做Fisher线性判别. FLD由Belhumeur于1996年引入人工智能领域, 其基本思想是将高维的样本投影到最佳鉴别矢量空间, 从而可以达到抽取分类信息、压缩特征空间维数的效果.
采用PCA和LDA对多民族人脸角度分析结果如图 14所示, 角度的3个主分量张成到3维空间进行显示. 3个民族的人脸数据在筛选后的民族语义描述下分布清晰, 各个民族人脸角度主分量形成了按民族语义的流形结构.其中也可以发现不同民族之间也存在模糊性的样本, 这也表明人脸的民族属性具有一定的模糊隶属关系.
5.3 多民族人脸几何指数特征(比例特征)分析
人类学采用指数特征对人脸进行描述.人体测量中的指数是两种测量绝对值之间的百分比关系.由于指数反映的是人体形态上的某种比例关系, 与绝对值特征相比, 能够较好排除因个体差异带来的比较误差, 因此, 在人类学群体间的比较研究中具有更为重要的意义.不同民族的各种人脸指数特征同各种绝对测量一样, 也存在着相当大的变异范围.人类学家根据指数的变异范围, 将指数区分为若干等级进行研究比较[58-59].
体质人类学关于人脸研究定义了18个比例指数特征, 其中15个在正面人脸, 其他3个在颅侧面.正面15个指数特征如表 5所示.
表 5 体质人类学定义的15个正脸指数Table 5 The 15 Physical anthropological definition of 15 frontal face index序号 指数特征名称 1 头宽高指数 2 额顶宽指数 3 头面宽指数 4 形态面指数 5 形态上面指数 6 容貌面指数 7 颧下颌宽度指数 8 颧额宽指数 9 容貌上面指数 10 额面指数 11 容貌上面高 12 头面高指数 13 鼻指数 14 鼻宽深指数 15 唇指数 本文首先利用这15个体质人类学定义的指数比例特征构建数据集, 验证这些指标能否表达不同民族的人脸差异, 因此通过Laplacian和Isomap对数据进行流形分析, 流形分布如图 15所示.
图 15 壮族(浅色)、维吾尔族(中浅色)、朝鲜族(深色)男女流形结构Fig. 15 The male and female manifold structure of the Zhuang (light), Uygur (middle light) and Korean (dark)图 15表明, 体质人类学比例指数的流形分布按各民族语义形成了一定程度子流形结构, 例如女性的Laplacian流形分布中的深色朝鲜族和浅色的壮族形成了较为完整的流形结构, 而男性的维吾尔和壮族较难区分.在Isomap流形结构中, 男性和女性的流形分布形成了类簇, 但是深色朝鲜族与中浅色维吾尔族数据混杂在一起, 没有形成明显边界的类簇.需要指出, 人体测量学定义了15个正脸指数特征, 而一张包含77个特征点的人脸共包括4 279 275个指数特征.
本文采用mRMR对人脸比例特征进行权重分析, 从427万多个比例特征中找出能够区分民族属性的比例特征.因为数据维度较高, 将数据高维指数特征按维度分为455个独立的子数据集, 利用mRMR对每个子数据集根据$score\geq 0.23$的标准共筛选出7 124个比例特征, 再利用筛选出的7 124个比例特征形成新数据集合并进行计算, 最终在权重$score\geq 0$条件下, 筛选出500个比例特征.
如图 16所示, 根据权重大小将部分权重较高的比例特征分为4个不同权重范围的比例特征刻画在人脸上.每个图的同一颜色代表一对长度组成的比例指数特征.
从图 16可以看出, 眼裂宽度、眉眼距离、鼻翼长度、鼻翼与眼内角距离以及鼻翼与眉毛距离等在每类权重特征中都出现, 额宽、眼睛到嘴部距离出现频率也较高, 说明这些特征对区分民族有重要作用.为提供详细的人脸指数特征说明, 本文给出了权重较高的15个指数特征, 如表 6所示.
表 6 不同权重的比例特征Table 6 The index features with different weight序号 权重区域特点 权重值 (眼裂高度) / (眉眼距离) 0.329 1 (眼裂高度) / (鼻翼与眉毛距离) 0.362 (鼻翼与眉毛距离)/ (嘴部与眉尖) 0.312 (鼻翼与眼内角点距离) / (额头高度) 0.35 (眼裂高度) / (鼻翼与眉毛距离) 0.302 2 (鼻翼长度) / (眉眼距离) 0.302 (眉眼距离) / (眉毛与鼻翼距离) 0.301 (鼻翼长度) / (眉毛与嘴部距离) 0.302 (眼裂高度) / (鼻翼与眉毛距离) 0.30 3 (鼻翼与眼内角点距离) / (额头高度) 0.294 (鼻翼距离) / (嘴巴与眼外角点距离) 0.297 (眉间距) / (鼻翼与眼内角距离) 0.297 (眼裂高度) / (鼻翼与眼内角点距离) 0.274 4 (眉毛与上唇距离) / (眉毛与下唇距离) 0.283 (鼻翼长度) / (眼睛与下颌距离) 0.281 本文利用筛选的500个指数特征构建数据集进行流形分析.采用PCA、LDA、LE和LPP方法比例进行维数约减流形分析, 如图 17所示.可视的三维流形空间中3个民族的人脸比例数据分布清晰, 各个民族的比例特征同样可以形成各自的聚类簇.采用拉普拉斯和LPP方法对数据进行流形分布可视化后, 呈现了与民族语义相关的子流形结构分布, 其中深色代表朝鲜族, 中浅色代表维吾尔族, 浅色代表壮族.
5.4 多民族人脸几何混合特征流形分析
人脸包含长度、角度、指数(比例)特征, 这些特征都可以形成各自对民族几何特征语义描述.为探究三类特征中哪一类特征更重要, 本文将三类特征混合形成数据集进行分析.
将250个长度特征、500个角度特征和500个人脸比例特征进行混合, 利用mRMR筛选了51个$score$ $>$ $0$的特征.其中长度、角度和比例特征的占比分别为0 %, 14.6 %, 85.4 %.总结了区分民族特征的重要指标51个, 如表 7所示.给出了类型(角度或指数比例)、权重值及其详细的人脸特征点计算公式.
表 7 长度、角度筛选出的51个人脸几何特征Table 7 The selected 51 geometric features from distance-based and angular attributesID 类型 详细 权重 ID 类型 详细 权重 1 I (49, 57)/(22, 7) 0.669 27 I (39, 43)/(7, 22) 0.299 2 I (35, 47)/(23, 51) 0.362 28 I (49, 69)/(34, 72) 0.296 3 I (37, 51)/(16, 24) 0.35 29 I (22, 73)/(21, 64) 0.298 4 I (39, 43)/(22, 36) 0.329 30 I (49, 52)/(15, 7) 0.296 5 I (50, 71)/(33, 60) 0.33 31 I (35, 47)/(28, 51) 0.298 6 I (49, 52)/(5, 17) 0.312 32 I (25, 50)/(21, 27) 0.292 7 I (22, 76)/(21, 54) 0.312 33 I (37, 51)/(14, 19) 0.294 8 I (51, 59)/(22, 45) 0.302 34 A ∠(21, 55, 26) 0.289 9 I (31, 35)/(37, 51) 0.305 35 I (39, 43)/(28, 51) 0.287 10 A ∠(51, 59, 27) 0.311 36 I (49, 52)/(22, 38) 0.289 11 I (39, 43)/(20, 58) 0.302 37 I (49, 76)/(35, 72) 0.289 12 I (37, 59)/(14, 22) 0.302 38 I (50, 52)/(22, 60) 0.286 13 I (17, 36)/(23, 50) 0.302 39 I (35, 47)/(23, 50) 0.287 14 I ∠(31, 22, 33) 0.297 40 I (49, 52)/(7, 35) 0.287 15 I (49, 52)/(60, 74) 0.304 41 I (22, 53)/(21, 50) 0.284 16 I (50, 55)/(17, 55) 0.301 42 I (50, 70)/(33, 60) 0.285 17 I (18, 21)/(33, 49) 0.302 43 A ∠(17, 49, 21) 0.285 18 I (35, 60)/(21, 54) 0.305 44 I (37, 51)/(16, 24) 0.285 19 I (39, 43)/(23, 51) 0.303 45 I (37, 51)/(16, 24) 0.282 20 I (37, 51)/(18, 25) 0.301 46 A ∠(51, 25, 59) 0.283 21 I (22, 73)/(21, 76) 0.347 47 A ∠(35, 29, 49) 0.284 22 I (49, 52)/(24, 66) 0.303 48 I (49, 57)/(22, 43) 0.282 23 I (49, 57)/(14, 22) 0.302 49 I (39, 43)/(19, 49) 0.282 24 I (50, 57)/(29, 61) 0.296 50 A ∠(21, 49, 25) 0.281 25 A ∠(21, 36, 22) 0.299 51 I (31, 35)/(24, 51) 0.279 26 A ∠(22, 60, 50) 0.298 注: I代表长度, A代表角度 从表 7可以看出, 1)人脸长度特征对于民族特征影响较小, 这与我们的认知相符.例如, 各民族未成年的人脸与成年人脸虽然长度特征相差较大, 但人可以很快识别其族群, 可见人脸的长度特征对于人脸的民族特征影响较小; 2)指数(比例)特征占比远大于角度特征, 数量比为5.8倍.本文对表 7中的角度和比例特征中的顶点和边按频度进行统计, 并标记其在人脸的区域位置, 得到如表 8所示边和点的支持度.
表 8 混合指标中的特征边与点的频繁项集Table 8 The frequent itemsets of the characteristic edge and point in the mixed attributesID 边 支持度 说明 ID 点 支持度 部位 1 39 ~ 43 6 眼裂 1 22 16 眉 2 49 ~ 52 6 鼻翼长度 2 49 16 鼻 3 37 ~ 51 4 鼻眼距离 3 51 14 鼻 4 35 ~ 47 3 眼裂 4 21 11 眉 5 49 ~ 57 3 鼻翼宽度 5 50 10 鼻 6 22 ~ 73 2 眉嘴距离 6 35 9 眼 7 31 ~ 35 2 眼裂 7 37 7 眼 8 14 ~ 22 2 额头高度1 8 43 7 眼 9 16 ~ 24 2 额头高度2 9 52 7 鼻 10 21 ~ 54 2 眉鼻距离1 10 39 6 眼 11 23 ~ 50 2 眉鼻距离2 11 24 5 眉 12 23 ~ 51 2 眉鼻距离3 12 57 4 鼻 13 23 4 眉 14 31 3 眼 15 46 3 眼 16 14 3 额头 17 16 3 额头 18 73 2 嘴 19 54 2 鼻 从表 8可以看出, 最为频繁出现的是眼裂和鼻翼相关信息, 如图 18所示.其中鼻部和眼部特征点占比64 %, 加上眉部占比超过85 %.说明在中国三个民族数据样本中, 区分度较大区位为鼻部和眼部信息, 这些部位反映了更多的民族特征信息.
由于混合特征中比例特征占比较高, 本文得出如图 19所示的混合特征下的流形结构, 可见其分布与指数特征数据集基本一致, 但更为清晰.这个研究表明人脸比例属性是描述人脸民族特征的重要指标, 长度和角度对于人脸民族的特征语义表述权重较小, 但融入一些比例无法描述的角度特征可以让人脸民族刻画的更为准确.
5.5 实验分析
采用分类器对筛选的数据集进行分析, 主要利用不同分类器通过对人脸的族群判别的各种分类指标来验证筛选出的不同人脸几何特征的有效性.将采集到的维吾尔族、壮族和朝鲜族的人脸图像, 经过图像预处理、特征点定位、几何特征计算、特征选择等步骤, 最终建立传统20个长度特征(A数据集), 筛选的195个几何长度特征(B数据集)、250个几何角度特征(C数据集)、250个比例指数特征(D数据集)和有三种特征筛选出的51个混合特征数据集(E数据集)共5个数据集, 将每个测试结果按性别指标较好的前两项粗体标注.其中交叉验证为10折, 取各指标在交叉验证中的平均值.未验证性别对民族特征的有效性, 每个数据集按性别拆分为两个数据集, 采用不同的模式分类方法对其进行分类与预测, 进而验证特征的有效性.类别为3个民族标记, 维吾尔族、壮族和朝鲜族.
实验硬件环境: Intel(R) Core(TM) i7-4770 CPU, 8GB内存; 软件环境:操作系统Win7;实验工具: Weka version 3.6[60].
为便于比较各模型的性能, 定义TP Rate、FP Rate、查准率(Precision)、查全率(Recall)、F-Measure、AUC (Area under curve)等[61]指标汇总信息.对于多分类问题, 计算指标值时, 假设${Y}$ = $\{{y}_{1}, {y}_{2}, \cdots, { y}_{n}\}$是数据集的类标号集合, 首先需将多分类问题分解成$k$个二分类问题, 为每一个类${ y}_{1}$ $\in$ ${y}$创建二类分类器, 其中所有属于${{ y}_{i}}$的样本都被看作正类, 而其他样本被看作负类. TP代表被分类模型正确预测的正样本数, FN代表分类模型错误预测为负类的正样本数, FP代表被分类模型错误预测为正类的负样本数, TN代表被分类模型正确预测的负样本数.分类器的分类效果越好, 它所对应的TP值就越高, FP越低.
$ \begin{align} TP_{\rm Rate}= \frac{TP}{TP+FN} \end{align} $
(7) 式(7)表示正确分类正样本的比例.
$ \begin{align} FP_{\rm Rate}=\frac{FP}{FP+TN} \end{align} $
(8) 式(8)代表错误分类负样本的比例.
$ \begin{align} Recall=\frac{TP}{TP+FN} \end{align} $
(9) 式(9)代表被判定为正确分类的正类样本数占所有被正类的样本数的比例.
$ \begin{align} Precision=\frac{TP}{TP+FP} \end{align} $
(10) 式(10)代表被正确分类的正类样本数占所有被判定为正类的样本数的比例.
AUC被定义为ROC曲线下的面积, 也可以认为是ROC曲线下面积占单位面积的比例, AUC的取值范围在0.5 ~ 1之间. AUC更大的分类器效果更好. F-Measure又称为F-Score, 是一种统计量, 常用于评价模型的好坏.
$ \begin{align} {F}{\rm -}{Measure}=\frac{2\times Precision\times Recall}{Precision+Recall} \end{align} $
(11) 分类正确率为
$ \begin{align} Accuracy=\frac{TP+TN}{TP+FN+FP+TN} \end{align} $
(12) 首先采用J48分类算法进行实验[62], 设置剪枝的阈值0.25, 实验结果如表 9所示, 混合特征数据集分类器指标高于其他数据集; 其次不同民族男性和女性的角度特征数据集分类效果高于比例特征数据, 长度特征数据集指标较差.
表 9 J48交叉验证学习后结果指标Table 9 J48 cross validation results after feature learningDataSet Sex TP Rate FP Rate Precision Recall F-Measure AUC A M 0.753 0.123 0.753 0.753 0.753 0.814 B M 0.833 0.083 0.834 0.833 0.833 0.879 C M 0.92 0.04 0.921 0.921 0.921 0.935 D M 0.90 0.05 0.902 0.9 0.90 0.935 E M 0.96 0.02 0.96 0.96 0.96 0.975 A F 0.727 0.137 0.725 0.727 0.724 0.775 B F 0.773 0.113 0.776 0.773 0.773 0.863 C F 0.813 0.093 0.814 0.813 0.812 0.853 D F 0.767 0.117 0.765 0.767 0.764 0.844 E F 0.813 0.093 0.818 0.813 0.814 0.888 决策树J48提供的规则集可以更好理解人脸的民族特征语义描述.本文从不同数据集J48决策树中抽取其识别率最高的决策树, 如图 20所示.
图 20 不同指标下的民族判别决策树Fig. 20 Ethnic classification decision trees with different indicators从不同类型特征的决策树可以得到:长度数据集决策树为4层9条规则, 角度数据集为3层5条规则, 指数比例数据集有3层4条规则.可见角度数据集和比例数据集的决策树信息表达较优, 层数均为3.从规则条数看, 比例数据规则条数最为精简, 而且比例指数数据集仅依靠4条分类规则就可以得到高于其他特征数据集的交叉验证的平均准确率.可见人脸的比例特征数据可以更好地对人脸特征进行描述.
本文利用Naive Bayes进行分类实验[63], 如表 10所示, 其中Naive Bayes采用K2搜索算法, 估计方法采用Simple estimator, 男女混合特征数据集指标结果最好, 男性比例特征数据集分类指标相对较好, 女性角度数据集分类指标优于比例特征数据集结果.
表 10 Naive Bayes实验结果Table 10 Naive Bayes experimental resultsDataSet Sex TP Rate FP Rate Precision Recall F-Measure AUC A M 0.82 0.09 0.821 0.82 0.82 0.927 B M 0.90 0.05 0.903 0.90 0.901 0.96 C M 0.96 0.02 0.96 0.96 0.96 0.993 D M 0.967 0.017 0.968 0.967 0.967 0.992 E M 0.973 0.013 0.974 0.973 0.973 0.999 A F 0.773 0.113 0.779 0.773 0.772 0.882 B F 0.753 0.123 0.755 0.753 0.750 0.902 C F 0.893 0.053 0.894 0.893 0.893 0.947 D F 0.887 0.057 0.889 0.887 0.887 0.956 E F 0.92 0.04 0.921 0.92 0.92 0.979 表 11为Naive Bayes算法分类实验[64]结果, 混合指标数据集各个指标在不同性别均最好, 男性比例特征数据集分类指标与角度数据集分类指标基本相当, 女性数据集比例特征数据集分类指标高于角度数据集.
表 11 Bayes network实验结果Table 11 Bayes network experimental resultsDataSet Sex TP Rate FP Rate Precision Recall F-Measure AUC A M 0.793 0.103 0.793 0.793 0.793 0.923 B M 0.893 0.053 0.897 0.893 0.894 0.962 C M 0.967 0.017 0.967 0.967 0.967 0.995 D M 0.967 0.017 0.967 0.967 0.967 0.992 E M 0.967 0.017 0.967 0.987 0.987 1.0 A F 0.733 0.133 0.735 0.733 0.734 0.883 B F 0.767 0.117 0.766 0.767 0.766 0.898 C F 0.887 0.057 0.888 0.887 0.887 0.951 D F 0.900 0.05 0.901 0.9 0.9 0.964 E F 0.913 0.043 0.914 0.913 0.913 0.983 表 12为RBFNetwork分类实验结果[65], 其中随机种子数为1、最低标准偏差为0.1, 混合指标数据集各个指标在不同性别均最好, 男性比例特征数据集分类指标相对较好, 女性角度数据集在5项指标除AUC外其他指标好于比例特征数据集.
表 12 RBF network实验结果Table 12 RBF network experimental resultsDataSet Sex TP Rate FP Rate Precision Recall F-Measure AUC A M 0.773 0.113 0.775 0.773 0.773 0.871 B M 0.913 0.043 0.915 0.913 0.914 0.947 C M 0.967 0.017 0.967 0.967 0.967 0.978 D M 0.973 0.013 0.974 0.973 0.973 0.976 E M 0.993 0.003 0.993 0.993 0.993 0.994 A F 0.753 0.123 0.753 0.753 0.753 0.866 B F 0.807 0.097 0.805 0.807 0.805 0.904 C F 0.900 0.050 0.900 0.900 0.900 0.937 D F 0.893 0.053 0.893 0.893 0.893 0.943 E F 0.907 0.047 0.909 0.907 0.907 0.94 表 13和表 14是SVM的两种不同实现算法分类结果. 表 13采用Weka的LibSVM类库分类实验[66], 其中分类类型C-SVC, 核函数类型${{\rm e}^{-r\left | u-v \right |^{2}}}, $核函数中的${degree} = 3$, 核函数中的${{coef}_{0}} = 0$, ${cachesize}$ = 40 MB.不同男性的混合特征数据集与比例数据集分类指标基本相同, 女性混合特征要优于比例特征数据集.
表 13 SVM中LibSVM实验结果Table 13 SVM in LibSVM experimental resultsDataSet Sex TP Rate FP Rate Precision Recall F-Measure AUC A M 0.773 0.113 0.775 0.773 0.772 0.83 B M 0.82 0.09 0.823 0.82 0.823 0.865 C M 0.86 0.07 0.858 0.86 0.857 0.895 D M 0.933 0.033 0.934 0.933 0.933 0.95 E M 0.953 0.023 0.953 0.953 0.953 0.965 A F 0.733 0.133 0.752 0.733 0.734 0.8 B F 0.720 0.14 0.758 0.72 0.713 0.79 C F 0.667 0.167 0.715 0.667 0.608 0.75 D F 0.860 0.07 0.862 0.86 0.859 0.895 E F 0.92 0.04 0.922 0.92 0.92 0.94 表 14 SVM中SMO实验结果Table 14 SVM in SMO experimental resultsDataSet Sex TP Rate FP Rate Precision Recall F-Measure AUC A M 0.893 0.053 0.895 0.893 0.893 0.944 B M 0.967 0.017 0.967 0.967 0.967 0.982 C M 0.967 0.017 0.967 0.967 0.967 0.983 D M 0.973 0.013 0.974 0.973 0.973 0.985 E M 0.973 0.013 0.973 0.973 0.973 0.985 A F 0.867 0.067 0.868 0.867 0.867 0.922 B F 0.907 0.047 0.907 0.907 0.907 0.947 C F 0.907 0.047 0.907 0.907 0.907 0.943 D F 0.933 0.033 0.934 0.933 0.934 0.965 E F 0.953 0.023 0.954 0.953 0.953 0.97 同时本文还采用了Weka中的独立的SMO (Sequential minimal optimization)[67]算法进行分类实验, SMO算法是一种用于解决SVM训练过程中所产生优化问题的算法.在SMO算法中, 核函数为多项式函数.
从表 14可以看出男性的混合特征数据集和比例特征数据集分类指标相同, 女性混合特征数据集略微优于比例特征数据集.
为观察不同数据集对特征数量的影响, 本文将特征属性按mRMR计算的权重$score$进行排序, 依次递增特征数量, 分析不同算法与特征个数的变化曲线, 如图 21所示.
图 21 不同类型特征增量下的准确率变化曲线Fig. 21 The recongnition rates comparison based on different types of features从图 21可以看出, 比例特征数据集的增量特征准确率变化曲线较为平缓.各个分类算法比例特征数据集抖动相对长度和角度变化较小.这也说明, 人脸几何特征中的比例特征能够更好帮助区分人脸的族群特征.
本文对比不同算法在不同数据集的交叉验证的平均准确率及方差, 如表 15所示.混合特征数据其平均准确率高于其他数据集, 方差也在较小范围波动.表明混合特征可以更加准确有效地作为人脸民族特征分析的指标.
表 15 SVM中SMO实验结果Table 15 SVM in SMO experimental results性别 J48 Naive Bayes BayesNet M(20长度特征) 80.00±1.83 89.33±1.04 79.30±1.62 M(195长度特征) 83.33±2.21 90.00±1.06 89.33±0.69 M(250角度特征) 92.00±1.05 96.00±0.55 96.70±0.85 M(400角度特征) 90.00±1.11 96.70±0.47 96.70±0.28 M(51混合特征) 96.00±0.55 97.33±0.21 98.67±0.53 F(20长度特征) 72.67±2.31 77.33±1.44 73.33±1.94 F(195长度特征) 77.33±1.51 75.33±1.21 76.67±1.20 F(250角度特征) 81.33±2.78 89.33±0.95 88.67±0.47 F(400角度特征) 76.67±2.51 88.67±0.55 90.00±0.38 F(51混合特征) 81.33±2.10 92.00±0.35 91.33±0.32 M(20长度特征) 77.33±2.17 89.33±1.65 77.33±1.03 M(195长度特征) 91.33±0.95 96.67±0.54 82.00±0.99 M(250角度特征) 96.70±0.85 96.70±0.56 86.00±0.32 M(400角度特征) 97.30±0.35 97.30±0.61 93.30±0.52 M(51混合特征) 99.33±1.25 97.33±0.49 95.33±0.49 F(20长度特征) 75.33±2.87 86.67±1.19 73.33±1.67 F(195长度特征) 80.67±1.14 90.67±1.29 72.00±1.43 F(250角度特征) 90.00±1.10 90.67±0.88 66.67±1.08 F(400角度特征) 89.33±0.85 93.33±1.30 86.00±0.73 F(51混合特征) 90.67±0.94 95.33±0.76 92.00±0.89 6. 结论
本文利用流形学习分析研究中国三个民族人脸几何特征, 分析分布规律和结构.首先从体质人类学采用的测量指标入手, 验证了传统经验构建的低维几何描述难以形成按不同民族语义特征描述的子流形结构.为了进一步研究人脸几何特征是否存在按民族语义分布的子流形结构, 本文扩充了人脸几何特征维度, 并利用mRMR算法对人脸中的冗余几何特征进行筛选, 在降维后的长度、角度和比例特征中分析不同民族人脸特征的流形结构, 实验结果表明, 民族人脸数据在子空间内可按民族语义形成流形结构, 且采用该指标体系可以有效地对不同民族人脸进行分类和识别.
本文的主要工作包括: 1)通过实验验证了人脸特征具有按民族语义分布的流形结构; 2)提出了一种筛选和分析不同民族人脸几何特征差异的算法框架; 3)提出了一套丰富和补充体质人类学指标的人脸民族几何特征测量指标集合.
本文研究得到以下人脸民族特征的数据结论: 1)人脸的比例特征相比于长度和角度是较为重要的人脸民族特征描述指标; 2)嘴部和脸型对于人脸民族特征影响较小; 3)眼部、鼻部和眉部区域对于人脸民族特征影响较大, 占85 %权重; 4)鼻翼和眉眼距是最为重要的人脸民族语义指标.
此外, 本文提出的多民族人脸特征分析和筛选及流形分析方法可以对其他不同民族人脸特征研究进行推广.人脸民族特征分析和体质人类学者可以根据这种方法来深入分析不同民族之间的差异特征, 并可以扩充数据集, 研究不同民族样本数据集下人脸几何特征的流形结构分布.
-
表 1 分支-定价算法与CPLEX求解小规模算例的计算结果比较
Table 1 Comparison of computational results obtained by branch-and-price and CPLEX for small scale instances
问题规模 分支-定价 CPLEX 轧批数 时间槽数 LMP OPT GAP (%) CPU (s) LIP UB GAP (%) CPU (s) 20 5 2 479.77 2 483.8 0.16 0.11 2278.50 2 483.8 9.01 1.17 25 6 2 991.97 3 011.7 0.66 0.17 2782.05 3 011.7 8.25 2.76 30 7 3 693.91 3 726.4 0.88 0.43 3501.45 3 726.4 6.42 216.72 35 8 4 026.08 4 047.0 0.52 0.79 3842.80 4 047.0 5.31 501.53 40 10 4 622.63 4 634.8 0.26 1.18 4473.60 4 779.6 6.84 3 600.00 
下载: 导出CSV
表 2 分支-定价算法求解中规模算例的计算结果
Table 2 Computational results of branch-and-price for solving medium scale instances
问题规模 GAP (%) Nodes CPU (s) 轧批数 时间槽数 平均 最大 平均 最大 平均 最大 50 12 1.49 2.91 21 57 2.12 7.15 50 15 1.06 1.50 13 33 1.19 5.73 50 18 0.77 1.02 10 23 0.89 3.25 50 20 1.22 3.27 11 25 0.25 0.98 60 12 0.74 2.47 26 45 12.02 81.53 60 15 1.26 3.24 27 59 8.03 46.81 60 18 1.10 2.65 21 40 4.68 22.55 60 20 1.12 3.81 19 48 3.51 10.06 80 12 1.00 2.57 24 80 196.55 497.12 80 15 0.86 1.91 31 58 119.58 254.81 80 18 1.30 2.74 18 37 40.23 150.28 80 20 0.71 1.72 11 29 10.61 76.11 100 12 0.46 1.86 66 113 233.75 714.88 100 15 0.66 2.50 24 67 185.42 325.91 100 18 0.81 3.13 40 79 100.21 255.13 100 20 1.01 3.05 22 62 51.14 190.11
下载: 导出CSV
表 3 主问题和子问题改进策略的性能分析
Table 3 Performance analysis of improvement strategies for master problem and subproblem
问题规模 M1 (s) M2 (s) M3 (s) M4 (s) 轧批数 时间槽数 平均 最大 平均 最大 平均 最大 平均 最大 50 12 4.69 17.12 3.7 14.29 2.33 7.94 2.12 7.15 50 15 3.65 12.85 2.98 10.93 1.25 7.16 1.19 5.73 50 18 2.04 8.64 1.77 7.57 1.01 4.05 0.89 3.25 50 20 0.87 2.84 0.67 2.03 0.29 1.22 0.25 0.98 60 12 48.25 191.13 36.77 149.03 14.84 100.93 12.02 81.53 60 15 29.45 114.49 24.14 85.5 10.12 60.32 8.03 46.81 60 18 12.47 64.05 10.36 56.81 5.82 28.13 4.68 22.55 60 20 10.82 36.24 8.7 32.5 4.33 11.71 3.51 10.06 80 12 1 086.38 - 969.15 - 217.68 641.45 196.55 497.12 80 15 690 2 063.25 503.93 1 733.78 124.16 315.08 119.58 254.81 80 18 322.21 1 067.64 257.22 938.52 42.79 175.27 40.23 150.28 80 20 86.17 737.05 62.47 610.48 12.48 90.52 10.61 76.11 100 12 3 400.82 - 2 444.17 - 265.16 801.17 233.75 714.88 100 15 2 619.11 - 2 006.37 - 207.73 380.22 185.42 325.91 100 18 1 514.30 - 1 227.72 - 111.29 319.95 100.21 255.13 100 20 702.27 2 960.12 525.75 2 452.29 62.02 223.47 51.14 190.11 注:表中"-"表示算法在2小时内未完成分支搜索过程.
下载: 导出CSV
表 4 分支-定价算法与手工计划的结果比较
Table 4 Comparison results between branch-and-price and the manual planning method
问题规模 目标值 能耗费用 机架切换时间 轧批数 时间槽数 手工排产 分支-定价 手工排产 分支-定价 手工排产 分支-定价 51 12 1.0915 1.0000 1.0886 1.0000 1.3074 1.0000 56 12 1.0864 1.0000 1.0842 1.0000 1.2239 1.0000 55 13 1.0944 1.0000 1.0941 1.0000 1.1181 1.0000 56 13 1.0756 1.0000 1.0744 1.0000 1.1601 1.0000 58 14 1.0947 1.0000 1.0949 1.0000 1.0836 1.0000 平均 1.0885 1.0000 1.0872 1.0000 1.1786 1.0000
下载: 导出CSV
-
[1] Lopez L, Carter M W, Gendreau M. The hot strip mill production scheduling problem:a tabu search approach. European Journal of Operational Research, 1998, 106 (2-3):317-335 doi: 10.1016/S0377-2217(97)00277-4 [2] 吕志民, 徐金梧.一种适用于热送热装生产计划优化的方法.北京科技大学学报, 2002, 24 (6):675-678 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200206023.htmLv Zhi-Min, Xu Jin-Wu. Optimization method for hot charge rolling manufacture plan. Journal of University of Science and Technology Beijing, 2002, 24 (6):675-678 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200206023.htm [3] Cowling P. A flexible decision support system for steel hot rolling mill scheduling. Computers and Industrial Engineering, 2003, 45(2):307-321 doi: 10.1016/S0360-8352(03)00038-X [4] Zhao J, Wang W, Liu Q L, Wang Z G, Shi P. A two-stage scheduling method for hot rolling and its application. Control Engineering Practice, 2009, 17 (6):629-641 doi: 10.1016/j.conengprac.2008.10.014 [5] Pan C C, Yang G K. A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation. Computers and Industrial Engineering, 2009, 56 (1):165-178 doi: 10.1016/j.cie.2008.05.001 [6] Lee H S, Murthy S S, Haider S W, Morse D V. Primary production scheduling at steelmaking industries. IBM Journal of Research and Development, 1996, 40 (2):231-252 doi: 10.1147/rd.402.0231 [7] Cowling P, Rezi W. Integration of continuous caster and hot strip mill planning for steel production. Journal of Scheduling, 2000, 3 (4):185-208 doi: 10.1002/(ISSN)1099-1425 [8] Tang L X, Liu J Y, Rong A Y, Yang Z H. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operational Research, 2001, 133 (1):1-20 doi: 10.1016/S0377-2217(00)00240-X [9] 吕志民, 牟文恒, 许剑桦, 唐荻, 徐金梧.两流方式下薄板坯连铸连轧生产组织方法及仿真.北京科技大学学报, 2005, 27 (3):356-359 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200503025.htmLv Zhi-Min, Mu Wen-Heng, Xu Jian-Hua, Tang Di, Xu Jin-Wu. Production organization method and simulation of dual-line thin slab continuous casting and hot rolling. Journal of University of Science and Technology Beijing, 2005, 27 (3):356-359 http://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200503025.htm [10] 于港, 田乃媛, 徐安军, 贺东风.炼钢——热轧生产计划的优化与协调.冶金能源, 2009, 28 (4):6-9 http://www.cnki.com.cn/Article/CJFDTOTAL-YJLY200904003.htmYu Gang, Tian Nai-Yuan, Xu An-Jun, He Dong-Feng. Optimization and coordination of steelmaking-hot rolling production plan. Energy for Metallurgical Industry, 2009, 28 (4):6-9 http://www.cnki.com.cn/Article/CJFDTOTAL-YJLY200904003.htm [11] 汪恭书, 唐立新.连铸——轧制生产中带有批决策的排序问题的建模与优化方法.自动化学报, 2012, 38 (10):1713-1720 http://www.aas.net.cn/CN/abstract/abstract17727.shtmlWang Gong-Shu, Tang Li-Xin. Modelling and optimization methods for the sequencing problem with batching decision in the continuous-casting and rolling production. Acta Automatica Sinica, 2012, 38 (10):1713-1720 http://www.aas.net.cn/CN/abstract/abstract17727.shtml [12] Chen Z L, Powell W B. Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics, 2003, 50 (7):823-840 doi: 10.1002/(ISSN)1520-6750 [13] Tang L X, Wang G S, Liu J Y. A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry. Computers and Operations Research, 2007, 34 (10):3001-3015 doi: 10.1016/j.cor.2005.11.010 [14] Dantzig G B, Wolfe P. Decomposition principle for linear programs. Operations Research, 1960, 8 (1):101-111 doi: 10.1287/opre.8.1.101 [15] Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem. Operations Research, 1961, 9 (6):849-859 doi: 10.1287/opre.9.6.849 [16] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 1992, 40 (2):342-354 doi: 10.1287/opre.40.2.342 [17] Moukrim A, Quilliot A, Toussaint H. An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration. European Journal of Operational Research, 2015, 244 (2):360-368 doi: 10.1016/j.ejor.2014.12.037 [18] Restrepo M I, Gendron B, Rousseau L M. Branch-and-price for personalized multiactivity tour scheduling. INFORMS Journal on Computing, 2016, 28 (2):334-350 doi: 10.1287/ijoc.2015.0683 [19] Fragkos I, Degraeve Z, De Reyck B. A horizon decomposition approach for the capacitated lot-sizing problem with setup times. INFORMS Journal on Computing, 2016, 28 (3):465-482 doi: 10.1287/ijoc.2016.0691 [20] Tang L X, Wang G S, Chen Z L. Integrated charge batching and casting width selection at baosteel. Operations Research, 2014, 62 (4):772-787 doi: 10.1287/opre.2014.1278 [21] Battarra M, Erdoǧan G, Vigo D. Exact algorithms for the clustered vehicle routing problem. Operations Research, 2014, 62 (1):58-71 doi: 10.1287/opre.2013.1227 [22] Baldacci R, Mingozzi A, Roberti R, Wolfler Calvo R. An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 2013, 61 (2):298-314 doi: 10.1287/opre.1120.1153 [23] Fleszar K. An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem. INFORMS Journal on Computing, 2016, 28 (4):703-720 doi: 10.1287/ijoc.2016.0708 [24] Gschwind T, Irnich S. Dual inequalities for stabilized column generation revisited. INFORMS Journal on Computing, 2016, 28 (1):175-194 doi: 10.1287/ijoc.2015.0670 [25] Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 2000, 48 (1):111-128 doi: 10.1287/opre.48.1.111.12453 期刊类型引用(5)
1. 何星辰，郭勇，李奇龙，高唱. 基于深度学习的抗年龄干扰人脸识别. 自动化学报. 2022(03): 877-886 . 
本站查看2. 于晓童，任甫. 几何形态测量法在人类颅面形态研究中的应用. 沈阳医学院学报. 2021(01): 1-4 . 百度学术3. 张克博. 审美位移与现代化重构——动画影片《姜子牙》角色设计的几点思考. 大观. 2021(03): 3-4 . 百度学术4. 山笑珂，张炳林. 利用改进深度信念网络的人脸表情识别. 计算机工程与设计. 2021(07): 2052-2060 . 百度学术5. 杜宇浩，阎高伟，李荣，王芳. 基于局部线性嵌入的测地线流式核多工况软测量建模方法. 化工学报. 2020(03): 1278-1287 . 百度学术其他类型引用(9)
-
下载:
计量
- 文章访问数: 2361
- HTML全文浏览量: 243
- PDF下载量: 1006
- 被引次数: 14
