风雨

蓦然回首 却在灯火阑珊处
posts - 3, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

置顶随笔

这个博客是http://hi.baidu.com/zhanggmcn的补充,主要存放一些代码相关的内容。

posted @ 2010-05-04 10:11 zgm 阅读(53) | 评论 (0)编辑 收藏

2010年5月11日

 一、人脸表情识别技术目前主要的应用领域包括人机交互、安全、机器人制造、医疗、通信和汽车领域等

 二、1971年,心理学家EkmanFriesen的研究最早提出人类有六种主要情感,每种情感以唯一的表情来反映人的一种独特的心理活动。这六种情感被称为基本情感,由愤怒(anger)、高兴(happiness)、悲伤 (sadness)、惊讶(surprise)、厌恶(disgust)和恐惧(fear)组成

 人脸面部表情运动的描述方法---人脸运动编码系统FACS (Facial Action Coding System),根据面部肌肉的类型和运动特征定义了基本形变单元AUAction Unit),人脸面部的各种表情最终能分解对应到各个AU上来,分析表情特征信息,就是分析面部AU的变化情况

 FACS有两个主要弱点1.运动单元是纯粹的局部化的空间模板;2.没有时间描述信息,只是一个启发式信息

三、人脸表情识别的过程和方法

1、表情库的建立:目前,研究中比较常用的表情库主要有:美国CMU机器人研究所和心理学系共同建立的Cohn-Kanade AU-Coded Facial Expression Image Database(简称CKACFEID)人脸表情数据库;日本ATR建立的日本女性表情数据库(JAFFE),它是研究亚洲人表情的重要测试库

2、表情识别:

(1)图像获取:通过摄像头等图像捕捉工具获取静态图像或动态图像序列。  

(2)图像预处理:图像的大小和灰度的归一化,头部姿态的矫正,图像分割等。

è目的:改善图像质量,消除噪声,统一图像灰度值及尺寸,为后序特征提取和分类识别打好基础

主要工作è人脸表情识别子区域的分割以及表情图像的归一化处理(尺度归一和灰度归一) 

(3)特征提取:将点阵转化成更高级别图像表述如形状、运动、颜色、纹理、空间结构等, 在尽可能保证稳定性和识别率的前提下,对庞大的图像数据进行降维处理

è特征提取的主要方法有:提取几何特征、统计特征、频率域特征和运动特征等

1采用几何特征进行特征提取主要是对人脸表情的显著特征,如眼睛、眉毛、嘴巴等的位置变化进行定位、测量,确定其大小、距离、形状及相互比例等特征,进行表情识别

优点:减少了输入数据量

缺点:丢失了一些重要的识别和分类信息,结果的精确性不高 

2)基于整体统计特征的方法主要强调尽可能多的保留原始人脸表情图像中的信息,并允许分类器发现表情图像中相关特征,通过对整幅人脸表情图像进行变换,获取特征进行识别。

主要方法:PCAICA(独立主元分析)

PCAè一个正交维数空间来说明数据变化的主要方向 优点:具有较好的可重建性 缺点:可分性较差

ICAè可以获取数据的独立成份,具有很好的可分性

基于图像整体统计特征的提取方法缺点:外来因素的干扰(光照、角度、复杂背景等)将导致识别率下降

3)基于频率域特征提取: 是将图像从空间域转换到频率域提取其特征(较低层次的特征)

 主要方法:Gabor小波变换

 小波变换能够通过定义不同的核频率、带宽和方向对图像进行多分辨率分析,能有效提取不同方向不同细节程度的图像特征并相对稳定,但作为低层次的特征,不易直接用于匹配和识别,常与ANN SVM 分类器结合使用,提高表情识别的准确率。 

4)基于运动特征的提取:提取动态图像序列的运动特征(今后研究的重点)

 主要方法:光流法

 光流是指亮度模式引起的表观运动,是景物中可见点的三维速度矢量在成像平面上的投影,它表示景物表面上的点在图像中位置的瞬时变化,同时光流场携带了有关运动和结构的丰富信息

 光流模型是处理运动图像的有效方法,其基本思想是将运动图像函数f (x, y,t)作为基本函数,根据图像强度守恒原理建立光流约束方程,通过求解约束方程,计算运动参数

 优点:反映了表情变化的实质,受光照不均性影响较小

 缺点:计算量大 

(4)分类判别:包括设计和分类决策

在表情识别的分类器设计和选择阶段,主要有以下方法:用线性分类器、神经网络分类器、支持向量机、隐马尔可夫模型等分类识别方法

1)   线性分类器:假设不同类别的模式空间线性可分,引起可分的主要原因是不同表情之间的差异。

2) 神经网络分类器:人工神经网络(Artificial Neural Network,ANN)是一种模拟人脑神经元细胞的网络结构,它是由大量简单的基本元件神经元,相互连接成的自适应非线性动态系统。将人脸特征的坐标位置和其相应的灰度值作为神经网络的输入,ANN可以提供很难想象的复杂的类间分界面。

   神经网络分类器主要有:多层感知器、BP网、RBF

  缺点:需要大量的训练样本和训练时间,不能满足实时处理要求

3) 支持向量机(SVM)分类算法:泛化能力很强解决小样本、非线性及高维模式识别问题方面表新的研究热点

基本思想:对于非线性可分样本,首先通过非线性变换输入空间变换到一个高维空间,然后在这个新空间中求取最优线性分界面。这种非线性变换通过定义适当的内积函数实现,常用的三种内积函数为:多项式内积函数、径向基内积函数Sigmoid内积函数

4) 隐马尔可夫模型(Hidden Markov Models, HMM):特点:统计模型、健壮的数学结构,适用于动态过程时间序列建模,具有强大的模式分类能力,理论上可处理任意长度的时序,应用范围非常广泛。

优点:运用HMM方法能够比较精确的描绘表情的变化本质和动态性能

5) 其他方法:

基于人脸物理模型的识别方法,将人脸图像建模为可变形的3D网格表面,把空间和灰度放在一个3D空间中同时考虑。

基于模型图像编码的方法是使用遗传算法来编码、识别与合成各种不同的表情

四、研究展望

1)鲁棒性有待提高:

外界因素(主要是头部偏转光线变化的干扰)

采用多摄像头技术、色彩补偿技术予以解决,有一定效果,但并不理想

2)表情识别计算量有待降低è确保实时性的要求

3)加强多信息技术的融合

     面部表情不是唯一的情感表现方式,综合语音语调、脉搏、体温等多方面信息来更准确地推测人的内心情感,将是表情识别技术需要考虑的问题

posted @ 2010-05-11 10:57 zgm 阅读(819) | 评论 (2)编辑 收藏

2010年5月4日


Computing n choose k mod p

Postby joshi13 » Tue Apr 14, 2009 4:49 am

Hi all.

How can we apply the modular multiplicative inverse when calculating

(n choose k) mod p, where 'p' is a prime number.

If you could suggest some related problems, it would be very helpful.

Thanks in advance.


Re: Computing n choose k mod p

Postby mf » Tue Apr 14, 2009 10:56 am

You could use Lucas's theorem.


Re: Computing n choose k mod p

Postby maxdiver » Tue Apr 14, 2009 12:03 pm

There is another, more "mechanical", but more general, approach. It can be applied to any formula containing factorials over some modulo.

C_n^k = n! / (k! (n-k)!)
Let's learn how to compute n! mod p, but factorial without factors p and so on:
n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2) * ... * (2p-1) * _2_ * (2p+1) * (2p+2) * ... * n.
We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on).
I name this 'strange factorial'.

If n is not very large, we can calculate this simply, then GOTO END_SCARY_MATHS :)
If p is not large, then GOTO BEGIN_SCARY_MATHS:
Else - skip the rest of the post :)

BEGIN_SCARY_MATHS:
After taking each factor mod p, we get:
n!* mod p = 1 * 2 * ... * (p-1) * 1 * 2 * ... * (p-1) * 2 * 1 * 2 * ... * n.
So 'strange factorial' is really several blocks of construction:
1 * 2 * 3 * ... * (p-1) * i
where i is a 1-indexed index of block taken again without factors p ('strange index' :) ).
The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
The result in each block is multiplication 1 * 2 * ... * (p-1), which is common to all blocks, and multiplication of all 'strange indices' i from 1 to floor(n/p).
But multiplication of all 'strange indices' is really a 'strange factorial' again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.

So... After so much brainfucking maths I must give a code :)
Code: Select all
int factmod (int n, int p) {
   long long res = 1;
   while (n > 1) {
      long long cur = 1;
      for (int i=2; i<p; ++i)
         cur = (cur * i) % p;
      res = (res * powmod (cur, n/p, p)) % p;
      for (int i=2; i<=n%p; ++i)
         res = (res * i) % p;
      n /= p;
   }
   return int (res % p);
}

Asymptotic... There are log_p n iterations of while, inside it there O(p) multiplications, and calculation of power, that can be done in O(log n). So asymptotic is O ((log_p n) (p + log n)).
Unfortunately I didn't check the code on any online judge, but the idea (which was explained by Andrew Stankevich) is surely right.
END_SCARY_MATHS:

So, we can now compute this 'strange factorial' modulo p. Because p is prime, and we've excluded all multiples of p, then the result would be different from zero. This means we can compute inverse for them, and compute C_n^k = n!* / (k!* (n-k)!*) (mod p).
But, of course, before all this, we should check, if p was in the same power in the nominator and denominator of the fraction. If it was indeed in the same power, then we can divide by it, and we get exactly these 'strange factorials'. If the power of p in nominator was greater, then the result will obviously be 0. The last case, when power in denominator is greater than in nominator, is obviously incorrect (the fraction won't be integer).

P.S. How to compute power of prime p in n! ? Easy formula: n/p + n/(p^2) + n/(p^3) + ...


(转载:http://acm.uva.es/board/viewtopic.php?f=22&t=42690&sid=25bd8f7f17abec626f2ee065fec3703b

posted @ 2010-05-04 10:07 zgm 阅读(227) | 评论 (0)编辑 收藏