CWYAlpha

Just another WordPress.com site

Archive for 五月 2012

Thought this was cool: 查找最小的k个元素

leave a comment »

给定一个数组和一个k,输出最小的k个数字。

这个问题有多重解法,譬如:
1、sort, top K,时间复杂度O(nlogn)
2、小顶堆排序,pop+调整k次,时间复杂度O(n+klogn)。
3、选择排序,每次选min,swap到头部时间复杂度O(nk)。

这里写下选择排序这个。

#include <stdio.h>

void select_min(int* arr, int n, int k)
{
	int i, j, tmp;
	int min,minP;
	for(i=0; i<k; i++)	
	{
		min = arr[i];
		minP = i;
		for(j=i+1; j<n; j++)
		{
			if(arr[j]<arr[minP])	
			{
				minP = j;
				min = arr[j];
			}
		}
		if(minP!=i)
		{
			tmp = arr[minP];
			arr[minP] = arr[i];
			arr[i] = tmp;
		}
	}
	// Print min k
	for(i=0;i<k;i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, -1};
	int k = 3;
	select_min(arr, sizeof(arr)/sizeof(int), 3);
	return 0;
}

from 四号程序员四号程序员: http://www.coder4.com/archives/3248

Advertisements

Written by cwyalpha

五月 31, 2012 at 4:09 下午

发表在 Uncategorized

Thought this was cool: 微笑识别

leave a comment »

论文:Exploring Temporal Patterns in Classifying Frustrated and Delighted Smiles

Is there a difference between while people smile under frustration as opposed to being genuinely delighted? How do the classifiers perform on recognizing mental states such as frustration and delighted when acted, as well as when elicited? What can we infer from the results about data collected through natural means as opposed to asking people to act? How do humans perform in correctly labeling smiles elicited under frustrated and genuinely delighted? Can we develop automated systems to distinguish between frustrated smiles and delighted smiles that perform better or as good as their human counterpart? This paper attempts to answer all these questions through a series of studies.

Publications:

M. E. Hoque, D. J. McDuff, R. W Picard, Exploring Temporal Patterns towards Classifying Frustrated and Delighted SmilesIEEE Transactions on Affective Computing, 2011. [under review]

M. E. Hoque, R. W. Picard, Acted vs. natural frustration and delight: Many people smile in natural frustration9th IEEE International Conference on Automatic Face and Gesture Recognition (FG’11), Santa Barbara, CA, USA, March 2011. (PDF: 1693 KB)

Press:

Specs that see right through you, by Sally Adee, NewScientist, July 5, 2011.

新闻来自:36kr

计算机面部识别技术虽然在近年并未获得突破性成果,但MIT的研究者还是在这方面取得一些不错成绩,他们最新开发的技术甚至能够判断微笑背后的真实情感。

研究人员最初让实验者表现出高兴与沮丧的表情,并使用两个摄像头记录图像。然后再让计算机算法与普通人同时对记录的表情进行情绪判断,两者都能基本判别。再让本来就快乐的人与本来遭受了挫折的人都露出微笑表情时,人类通过笑容判别情绪的准确率过半,而MIT的计算机算法的差别准确率却能超过90%。

研究人员希望该技术能更好地帮助那些理解人类表情有困难的人。同时,它在商业方面也有着较大潜力,因为他们认为:“顾客对你微笑,表达的不一定就是满意,笑容背后的含义很重要。”

最热文章

from 丕子: http://www.zhizhihu.com/html/y2012/3805.html

Written by cwyalpha

五月 31, 2012 at 4:09 下午

发表在 Uncategorized

Thought this was cool: 浅谈网页搜索排序中的投票模型

leave a comment »

     前些天读了一本《选举的困境》,其中有一章,从美国的选举制度说起,介绍美国选举制度的不足,然后针对其不足,提出种种改善,然而每种改善都有其各自的问题,其中的变化很有趣。

    先说美国选举制度,美国的总统选举是一种“赢者通吃”的方式,每个州根据其人口多少,有几十或几百的“州票”,州里的人对总统候选人进行选举,在某个州获得票最多的那个候选人,获得这个州所有的“州票”,然后统计所有候选人的“州票”多少,获得最多“州票”的候选人获胜。

    这样制度的问题是显然的,比如如果只有两个州,A州5个人,而B州4个人,州票也分别是5和4,如果某候选人X在A州以3:2获胜,另一个候选人Y在B州以4:0获胜,这样显然候选人Y在全国范围内获得了6张票,而候选人X只有在A州的3张票,但是由于“赢者通吃”,X获得了A周的全部5张“州票”,Y只获得了B周的4张“州票”,在全国只有1/3民众支持的X居然获得了选举的胜利。

    这样的情况在2000年美国总统选举中就出现过,小布什的州票领先于戈尔,然而在全国民众中统计支持戈尔的人数却是大于小布什的,当然戈尔输给小布什还有另一个原因,这里按下不表。

    如果放在算法领域,可以看出这里的问题在于,为了统计结果R(最适合的总统人选),找到了一个特征A(每个民众的投票),而决定结果R的,却不是特征A,而是由特征A推导出来的特征B(州票),在特征A向特征B的推导过程中,信息丢失了(每个洲的支持百分比不一样)。

    “赢者通吃”这种制度的具体历史原因先不说,有兴趣的朋友可以去看原著。解决这种问题的最直接方案就是从“赢者通吃”变成直选,也就是一人一票,直接统计票数,然而这样也会遇到一系列问题。

    在谈那一系列问题之前,先把要解决的问题抽象一下:

    有n个候选人,每个选民对这n个候选人投票,最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人。

方案1:一票制,每人一票,选出自己最喜欢的候选人,对结果进行统计,得票最多的那个人当选。

    这样做的问题是会导致作者定义的一种“鹬蚌困局”,举例说,如果有ABC三个候选人,其中BC政见比较类似,支持B的人也比较支持C,反之亦然,在全民中,喜欢BC的人占多数,A的政见和BC相反,支持A的人在全民中占少数。这样导致的后果就是,BC获得的票会比较分散,而A获得的票比较集中从而获得胜利,如果BC中有1人不参加选举,票就会集中到B或者C一个人的手中,从而使多数选民的支持者当选。前面按下不表的戈尔失败的另一个原因,就是有人认为有跟戈尔政见类似的耐德的参与,他分散了部分戈尔的选票。

    可以对此问题有所改善的方案叫做“二选制”。

方案2:二选制,每人一票,如果无人获得大于50%的支持,则将得票最高的两个候选人拿出来,再进行一轮选举,得票多的人获胜。

    法国总统选举就是这样的二选制,但是这样的方法只能改善“鹬蚌困局”,而不能彻底解决,2002年的法国总统大选就出现了类似的情况,当时支持左派政见的民众较多,然而在二选制下,最终的前两名却是一个右派和一个极右派。出现这种情况的原因是当年有16个总统候选人,且多数是持左派政见者,这样就导致左派的票极端分散。

方案3:n选制,每人一票,如果无人获得大于50%的支持,则去掉支持最少的候选人,再进行一轮投票,若依旧无人获得大于50%的支持,再去掉得票最少的候选人,直到有人大于50%支持为止。

    2001年奥委会决定北京为2008年奥运会主办城市的时候,就是用的这样的制度,在第一轮投票里大阪被淘汰,北京在第二轮就获得了半数以上的支持,从而当选。

    n选制的问题在于不实用,如果是奥委会这种只有几百个人投票的情况还可以使用,如果类似前面法国总统选举,有16个候选人,举国上下最多可能进行15次投票,成本太高。

方案4:即刻复选制,每个民众对候选人进行排序,如果某个候选人获得了50%以上的首选,则直接获得胜利,否则淘汰票数最低的候选人,并且把票数最低候选人的得票中的第二候选人拿出来,分给对应的候选人,如果有人获得50%以上,则当选,否则再淘汰一位最低的,并且把他票分给里面排序最高的且未被淘汰的候选人,如此往复。

    爱尔兰总统选举和伦敦市长选举采用的是类似的方案,此方案也有问题,试想如此场景:选民共10人,中间派候选人是3人的首选,左派和右派的候选人分别是4人的首选,当然左派选民最讨厌右派候选人,而右派选民也最讨厌左派候选人,而左派右派的民众对中间派候选人倒是都可以接受,不管是即可复选制还是n选制,中间派候选人都会在第一轮被淘汰。而中间派候选人则是全体民众都可以接受的人,也最能调和各派之间矛盾,最和谐。

    这个方案的本质问题是,虽然每个选民可以对候选人排序,但是在第一轮的时候却只考虑了第一选,没有考虑选民的二、三选。

方案5:上行复选制,跟方案4类似,只不过第一轮淘汰的不是支持最少,而是反对最多的候选人(获得最多末选票的候选人)

    再看上面提到的情况,中间派候选人由于不是任何人的末选,所以第一轮淘汰的是左派或者右派,再第二轮选举中,中间派的候选人就可以获胜了。

    方案5也有方案5的问题,考虑这样一种情况,只有两个候选人AB参选,选民9人,其中6人喜欢A而讨厌B,3人喜欢B而讨厌A,无论按照之前的哪种方式,都会是A获胜。但是现在又多了两个候选人C和D,喜欢B的3人中,都是把A列在最后一个候选的,而喜欢A的6人的末选,却是BCD各2票,这样,在第一轮选举中,A就由于获得了最多的末选票被淘汰了,而通过精心的构造例子,完全可以使B最终当选。仅仅由于CD参选或者不参选,A和B之间的胜负关系就发生了大逆转。

    实际使用此方案的例子不多,只有在公元前507年的雅典有类似的方案,不是让民众投支持票,而是投反对票,把反对最多的人投出局。

方案6:多赛制,民众对候选人排序,然后候选人之间两两pk,统计每一张选票上看候选人A在候选人B前面还是B在A前面,如此找到获胜场次最多的候选人来赢得选举。

    这样的问题是可能导致循环胜负,如ABC三个候选人,有3个民众,投票分别是ABC,BCA,CAB,可以看出AB之间A获胜两次,A>B;BC之间B获胜两次,B>C,AC之间C获胜两次,C>A,这样就构成了一个A>B>C的循环。这个是不是有点像足球联赛的记分制啊,如果积分相同,足球比赛中可以再看净胜球、进球、胜负关系等,但是作者并没有在这个方面进行展开,而是介绍了另一种方式:博达制。

方案7:博达制,民众对候选人排序,假如有n个候选人,第一位的候选人得n分,第二位得n-1分,以此类推,然后统计每个候选人的总分,获得最多分的获胜。

    有人对博达制的批评是:可能有选民会利用这种方式进行作弊(投“策略票”),最支持B的候选人本来心目中的排序是B>A>C,但是由于相对A,他们还是更喜欢B,因此,为了把B拉上来,就得把A拉下去,他们的投票就变成了B>C>A。博达对此批评的回应是:我的制度只适用于诚实的投票者。

    而这本书的作者却认为博达制的“策略票”问题没那么严重,如果无法准确预测民意和精确控制策略票的投法,有可能因为用力过猛,不但把A拉下来了,反而让C获得的支持票增加,这样就使得最支持B的那些人的“策略票”反而使得他们最讨厌的C当选了,当年在IMDB上就发生过类似一幕:

    电影《蝙蝠侠6》上映后,蝙蝠侠的粉丝们觉得这部片太酷了,于是就想把蝙蝠侠6投成IMDB第一位,于是他们疯狂的给蝙蝠侠6打高分,而同时,也纷纷的给当时的IMDB第一《教父》投低分,导致的结果就是用力过猛,教父变成了第三名,原来的第二肖申克的救赎(TSR)变成了第二(原来的第二是排在教父后面,新的第二是排在蝙蝠侠6后面),而后来,随着疯狂粉丝的热情消退,理性的意见占据了上风,蝙蝠侠6的得分逐渐下降,跌到了第10。而教父还是在肖申克的救赎后面,很久没有回去了。

    博达制是否有其他问题呢?

    以上只是对这本书第14章的一个笔记,也仅仅针对“多候选人单职位”问题进行了讨论,书的后面还会对“多候选人多职位”的情况继续探讨,也就是根据每个人对候选人的排序,来决定最终的候选人排序。

    回到搜索引擎领域来,如上策略的变迁会给我们一些启示,先看看之前抽象出来的问题:

    有n个候选人,每个选民对这n个候选人投票,最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人。

    这很像搜索引擎在解决的问题:

    系统里有n个网页,有m个特征(页面质量、页面内容丰富度、页面超链、文本相关性等)对n个网页有不同的打分,如何根据这些特征的“投票”,选出最适合放在第一位的网页呢?

    从选举的例子中,我们可以得到的几个启示:

    1. 设计算法时,要避免出现“赢者通吃”带来的信息丢失问题。

    2. 不要因为某几个特征特别好,就把某个网页排到最前,或者因为某几个特征特别差,就把某个网页抛弃。

    3. 最合适放在首位的网页不一定是在每个特征上都最好,而应该是能够兼顾所有特征,综合表现最好的那个。

    4. 搜索引擎使用者对搜索结果的点击行为,可以看成是对搜索结果进行的“投票”,这样的“投票”信息的使用方式,也要注意考虑是否会带来选举过程中出现的种种不合理。

    以上提到的种种选举方案,仅仅是对“多候选人单职位的”的情况进行讨论,而搜索引擎面对的问题,则更类似于“多候选人排序”的情况,也即:

    系统里有n个网页,有m个特征(页面质量、页面内容丰富度、页面超链、文本相关性等)对n个网页有不同的打分,如何根据这些特征的“投票”,决定n个网页的顺序?

    而这个“多候选人排序”问题,是有一个“不可能的民主”的理论的,该理论的大意是,“合理”的民主应该满足3个条件:

    1. 如果选民都认为A比B好,那么最终结果应该也是A比B好

    2. 没有“独裁者”,也即,不存在这样一个人,无论别人怎么排序,最终结果的排序都和这个人的排序一致

    3. 无关因素独立性,也即,在第一次投票完成后,A排在B前面,现在进行第二次投票,如果所有人都没有改变自己投票中A和B的相对顺序,那最终结果应该也是A在B前面

    而通过数学的证明,可以得出结论:如果某种选举方式满足条件1和3,则必然不满足2,也即必然存在“独裁者”,这个问题的证明,可以参考这篇博客:http://roba.rushcj.com/?p=509

    根据“不可能的民主”理论,和搜索引擎结合起来看,似乎搜索引擎很难给出一个合理的网页排序,但是搜索引擎和投票又似乎有所不同,有两个角度可以破解

    1. 认为条件3过于强,需要弱化。

    2. 也许在网页排序问题上,真的存在这样一个“独裁特征”,这个“独裁特征”从目前看来,最适合的应该就是“用户满意度”了,按照用户的满意程度来排序网页,就是最合理的网页排序。如何衡量“用户满意度”呢?这就是我们一直在努力的。

by liangaili


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/7373.html

Written by cwyalpha

五月 31, 2012 at 4:09 下午

发表在 Uncategorized

Thought this was cool: 数据结构重读 – 赫夫曼树(最优二叉树)

leave a comment »

路径长度:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。

树的路径长度:从树根到每一个结点的路径长度之和。

结点的带全路径长度:从该结点到树根之间的路径长度与结点上权的乘积。

树的带全路径长度:树中所有叶子结点的带全路径长度之和,WPL = Σ (wi x li),其中wi是叶子结点的权重,li是从根到该叶子结点的路径长度,注意,带全路径长度只有叶子结点有权重!其他结点只计算长度无权重!

来看书上三个树的WPL:

WPL(a) = 7*2 + 5* 2 + 2*2 +4*2 = 36

WPL(b)=4*2 + 7*3 + 5*3 + 2 = 46

WPL(c) = 7 + 5 * 2 + 3 * 2 + 4 * 3 = 35

其实c是最优二叉树。

赫夫曼(Huffman)树,又称最优二叉树,是一类带全路径长度最短的树。

赫夫曼编码的用途很广,例如优化if分支条件的组合、数据压缩等等。

赫夫曼算法

设有n个叶子结点,则有对应的n个权值w1…wn。

(1)首先构成n棵二叉树,每棵二叉树中以wi为根结点,左右孩子均为空,设n棵二叉树位于集合F中。
(2)在F中选取两棵根结点权值最小的树做为左右子树,构造一棵新的二叉树,并设置根结点的权值为左、右子树上的根结点的权值之和。
(3)在F中删除这两棵被选中的子树,并且在F中加入新树。
(4)重复(2)和(3)直到F中只包含一棵树为止。
最后形成的这棵树便是赫夫曼树。

其实,赫夫曼算法的思想很简单:让权值大的尽量少在路径短的上面。权值小的在路径长的上面。

由于赫夫曼树中没有度为1的结点,所以一棵有n个叶子结点的赫夫曼树一定有2n-1个结点

 赫夫曼编码

在需要压缩编码的时候,可以另每种字符做为叶子结点,借助最优二叉树(赫夫曼树)设计长短不等的编码。

这种编码叫做前缀编码:长短不等的编码,且必须是任意一个字符的编码都不是另一个字符编码的前缀。

由于赫夫曼编码不仅需要左、右孩子,还需要双亲、还需要计算和合并。我们可以采用如下的结点数据结构:

struct HFNode
{
    int weight;
    int parent, lchild, rchild;
};

typedef struct HFNode[MAX] HFTree;

如上所述,weight是结点的权重。

赫夫曼树用数组存放,lchild和rchild是左右孩子在数组中的下标。

有了这个结构后,实现赫夫曼树的算法就比较简单了。

算法共分为三部分:

(1)构造赫夫曼树
(2)计算(打印)字符的赫夫曼编码
(3)利用赫夫曼编码译码

首先是构造赫夫曼树的编码,假设n个叶子结点(要编码的字符) ,我们用2*n-1个结点的数组存储赫夫曼树:
(a)[0, n-1]是n个叶子结点和weight,parent都是-1(未决定),lchild和rchild是0。
(b)[n, 2*n-1)是非叶子结点,我们从前面选择了min 2个结点后,组装的结点依次存放在n~2*n-1里面。

构造赫夫曼树的算法如下:

注意,算法中“直到只剩下一棵树” 这个条件,我们是可以通过控制for循环的次数控制(i->(n-1, 2*n-1)),而不用去判断的。

#include <stdio.h>

#define NODE 100

#define MAX  2*NODE-1

typedef struct HFNode
{
	int weight;
	int parent;
	int lchild;
	int rchild;
}HFNode, *HFTree;

void hftree_init(HFTree tree)
{
	int i;
	for(i=0;i<MAX;i++)
	{
		tree[i].weight = tree[i].lchild = tree[i].rchild = 0;
		tree[i].parent = -1;
	}
}

int hftree_min(HFTree tree, int start, int end)
{
	int min = 0;
	int minw = 0xffffff;
	int i;
	for(i=start; i<=end;i++)
	{
		if(tree[i].parent==-1 && tree[i].weight<minw)
		{
			minw = tree[i].weight;
			min = i;
		}
	}
	return min;
}

void hftree_build(HFTree tree, int* w, int nw)
{
	int i, m;
	int min1, min2;
	// First , fill HFTree[0:n-1] with weight (leaf node)
	for(i=0;i<nw;i++)
	{
		tree[i].weight = w[i];
		tree[i].lchild = tree[i].rchild = 0; // leaf has no left or right child
		tree[i].parent = -1; // parent undefined
	}
	// Second, build tree and set no-leaf node into HFTree[n: 2*n-1)
	m = 2 * nw - 1;
	for(i=nw;i<m;i++)
	{
		// Select two min and no parent node from [0:i-1]
		min1 = hftree_min(tree, 0, i-1);
		tree[min1].parent = i;
		min2 = hftree_min(tree, 0, i-1);
		tree[min2].parent = i;
		// Make new node and store at i
		tree[i].lchild = min1;
		tree[i].rchild = min2;
		tree[i].weight = tree[min1].weight + tree[min2].weight;
		tree[i].parent = -1;
	}
}

int main()
{
    int i;
    int w[8] = {5, 29, 7, 8, 14, 23, 3, 11};
    int n = sizeof(w) / sizeof(int);
    HFNode hftree[MAX];
    // Init
    hftree_init(hftree);
    // Make tree
    hftree_build(hftree, w, n);
    // Print & Test
    //for(i=0;i<2*n-1;i++)
    //{
    //    printf("%2d %2d %2d %2d\n", hftree[i].weight, hftree[i].parent, hftree[i].lchild, hftree[i].rchild);
    //}
    hfcode_encode(hftree, w, n);
    return 0;    
}

然后是给每个字符(叶子结点) 赋予0/1编码,我们这里规定左子树0,右子树1:

void hfcode_encode(HFTree tree, int* w, int nw)
{
	char tmp[1024];
	int i, p, j;
	// Get Huffman code each leaf to root
	for(i=0;i<nw;i++)
	{
		j = 0;
		p = i;
		while(tree[p].parent!=-1)
		{
			if(tree[tree[p].parent].lchild==p)
			{
				tmp[j++] = '0';
			} else if(tree[tree[p].parent].rchild==p)
			{
				tmp[j++] = '1';
			}
			p = tree[p].parent;
		}
		tmp[j] = '';
		// Print huffman code
		printf("%2d: %s\n", w[i], tmp);
	}
}

最后的编码结果:

 5: 1000
29: 01
 7: 0111
 8: 1111
14: 011
23: 10
 3: 0000
11: 100

from 四号程序员四号程序员: http://www.coder4.com/archives/3226

Written by cwyalpha

五月 28, 2012 at 2:23 上午

发表在 Uncategorized

Thought this was cool: 刚发现在vs studio里汉字也可以当变量名 (转载)

leave a comment »

发信人: guanshuiyong (wakao), 信区: Joke
标 题: Re: 刚发现在vs studio里汉字也可以当变量名
发信站: 水木社区 (Fri May 25 11:12:00 2012), 站内

【 以下文字转载自 CPlusPlus 讨论区 】
发信人: forcey (爱到无可救药), 信区: CPlusPlus
标 题: Re: 刚发现在vs studio里汉字也可以当变量名
发信站: 水木社区 (Fri May 25 05:53:50 2012), 站内

#define 趁还 while
#define 那个啥 int
#define 总的来说 main
#define 买 cin
#define 卖 cout
#define 进 >>
#define 出 <<
#define 拜拜了 return
#define 去掉 -=
#define 等于 =
#define 屁 100e4
#define 我说 (
#define 是吧 )
#define 啊 a
#define 那么就 {
#define 得了 }
#define 呀 ;
#include <iostream>
using namespace std;

那个啥 总的来说 我说 那个啥 啊 是吧
那么就 那个啥 有钱 等于 屁 呀
趁还 我说 有钱 是吧 那么就
那个啥 多少 呀 买 进 多少 呀 卖 出 多少 呀 有钱 去掉 多少 呀
卖 出 多少 呀 得了
拜拜了 啊 呀 得了

【 在 fatalme (火叶) 的大作中提到: 】
: #include <iostream>
: using namesapce std;
: class C{
: ……………….

理想:5D3 1635 2470II ISXB2 24L 35L 50L 85L 135L 百微L
现实:5D2 1740 70300IS 50/1.8 百微USM

还差 15000 刀..

※ 来源:·水木社区 http://newsmth.net·%5BFROM: 131.107.0.*]

from 水木社区 Joke/笑话连篇 保留区: http://www.newsmth.net/bbscon.php?bid=63&id=2971607

Written by cwyalpha

五月 27, 2012 at 5:38 上午

发表在 Uncategorized

Thought this was cool: 【转】Kinect人脸跟踪算法

leave a comment »

After a long journey, my team at Microsoft shipped SDK as part of For Windows 1.5! I worked on the technology (starting from the times when it was part of Avatar Kinect) and so I’d like to describe its capabilities and limitations here. First of all, here is the demo:


You can use the Face Tracking SDK in your program if you install Kinect for Windows Developer Toolkit 1.5. After you install it, go to the provided samples and run/build yourself “Face Tracking Visualization” C++ sample or ”Face Tracking Basics-WPF” C# sample. Off course you need to have Kinect camera attached to your PC ;-)The face tracking engine tracks at the speed of 4-8 ms per frame depending on how powerful your PC is. It does it work on CPU only (does not use GPU on purpose, since you may need it for graphics)

If you look at the 2 mentioned code samples, you can see that it is relatively easy to add face tracking capabilities to your application. You need to link with a provided lib, place 2 dlls in the global path or in the working directory of your your executable (so they can be found) and add something like this to your code (this is in C++, you can also do it in C#, see the code samples):

 

// Include main Kinect SDK .h file
#include "NuiAPI.h"

// Include the face tracking SDK .h file
#include "FaceTrackLib.h"

// Create an instance of a face tracker
IFTFaceTracker* pFT = FTCreateFaceTracker();
if(!pFT)
{
    // Handle errors
}

// Initialize cameras configuration structures.
// IMPORTANT NOTE: resolutions and focal lengths must be accurate, since it affects tracking precision!
// It is better to use enums defined in NuiAPI.h

// Video camera config with width, height, focal length in pixels
// NUI_CAMERA_COLOR_NOMINAL_FOCAL_LENGTH_IN_PIXELS focal length is computed for 640x480 resolution
// If you use different resolutions, multiply this focal length by the scaling factor
FT_CAMERA_CONFIG videoCameraConfig = {640, 480, NUI_CAMERA_COLOR_NOMINAL_FOCAL_LENGTH_IN_PIXELS};

// Depth camera config with width, height, focal length in pixels
// NUI_CAMERA_COLOR_NOMINAL_FOCAL_LENGTH_IN_PIXELS focal length is computed for 320x240 resolution
// If you use different resolutions, multiply this focal length by the scaling factor
FT_CAMERA_CONFIG depthCameraConfig = {320, 240, NUI_CAMERA_DEPTH_NOMINAL_FOCAL_LENGTH_IN_PIXELS};

// Initialize the face tracker
HRESULT hr = pFT->Initialize(&videoCameraConfig, &depthCameraConfig, NULL, NULL);
if( FAILED(hr) )
{
    // Handle errors
}

// Create a face tracking result interface
IFTResult* pFTResult = NULL;
hr = pFT->CreateFTResult(&pFTResult);
if(FAILED(hr))
{
    // Handle errors
}

// Prepare image interfaces that hold RGB and depth data
IFTImage* pColorFrame = FTCreateImage();
IFTImage* pDepthFrame = FTCreateImage();
if(!pColorFrame || !pDepthFrame)
{
    // Handle errors
}

// Attach created interfaces to the RGB and depth buffers that are filled with
// corresponding RGB and depth frame data from Kinect cameras
pColorFrame->Attach(640, 480, colorCameraFrameBuffer, FORMAT_UINT8_R8G8B8, 640*3);
pDepthFrame->Attach(320, 240, depthCameraFrameBuffer, FTIMAGEFORMAT_UINT16_D13P3, 320*2);
// You can also use Allocate() method in which case IFTImage interfaces own their memory.
// In this case use CopyTo() method to copy buffers

FT_SENSOR_DATA sensorData;
sensorData.pVideoFrame = &colorFrame;
sensorData.pDepthFrame = &depthFrame;
sensorData.ZoomFactor = 1.0f;       // Not used must be 1.0
sensorData.ViewOffset = POINT(0,0); // Not used must be (0,0)

bool isFaceTracked = false;

// Track a face
while ( true )
{
    // Call Kinect API to fill videoCameraFrameBuffer and depthFrameBuffer with RGB and depth data
    ProcessKinectIO();

    // Check if we are already tracking a face
    if(!isFaceTracked)
    {
        // Initiate face tracking.
        // This call is more expensive and searches the input frame for a face.
        hr = pFT->StartTracking(&sensorData, NULL, NULL, pFTResult);
        if(SUCCEEDED(hr) && SUCCEEDED(pFTResult->Status))
        {
            isFaceTracked = true;
        }
        else
        {
            // No faces found
            isFaceTracked = false;
        }
    }
    else
    {
        // Continue tracking. It uses a previously known face position.
        // This call is less expensive than StartTracking()
        hr = pFT->ContinueTracking(&sensorData, NULL, pFTResult);
        if(FAILED(hr) || FAILED (pFTResult->Status))
        {
            // Lost the face
            isFaceTracked = false;
        }
    }

    // Do something with pFTResult like visualize the mask, drive your 3D avatar,
    // recognize facial expressions
}

// Clean up
pFTResult->Release();
pColorFrame->Release();
pDepthFrame->Release();
pFT->Release();

 

Note1 about the camera configuration structure –  it is very important to pass correct parameters in it like frame width, height and the corresponding camera focal length in pixels. We don’t read these automatically from Kinect camera to give more advanced users more flexibility. If don’t initialize them to the correct values (that can be read from Kinect APIs), the tracking accuracy will suffer or the tracking will fail entirely.

Note2 about the frame of reference for 3D results –  the face tracking SDK uses both depth and color data, so we had to pick which camera space (video or depth) to use to compute 3D tracking results in. Due to some technical advantages we decided to do it in the color camera space. So the resulting frame of reference for 3D face tracking results is the video camera space. It is a right handed system with Z axis pointing towards a tracked person and Y pointing UP. The measurement units are meters. So it is very similar to Kinect’s skeleton coordinate frame with the exception of the origin and its optical axis orientation (the skeleton frame of reference is in the depth camera space). Online documentation has a sample that describes how to convert from color camera space to depth camera space.

Also, here are several things that will affect tracking accuracy:

1) Light – a face should be well lit without too many harsh shadows on it. Bright backlight or sidelight may make tracking worse.

2) Distance to the Kinect camera – the closer you are to the camera the better it will track. The tracking quality is best when you are closer than 1.5 meters (4.9 feet) to the camera. At closer range Kinect’s depth data is more precise and so the face tracking engine can compute face 3D points more accurately.

3) Occlusions – if you have thick glasses or Lincoln like beard, you may have issues with the face tracking. This is still an open area for improvement :-)   Face color is NOT an issue as can be seen on this video

Here are some technical details for more technologically/math minded people: We used the Active Apperance Model as the foundation for our 2D feature tracker. Then we extended our computation engine to use Kinect’s depth data, so it can track faces/heads in 3D. This made it much more robust and realiable. Active Appearance Models are not quite robust to handle real open world scenarios. Off course, we also used lots of secret sauce to make things working well together :-)   You can read about some of the algorithms herehere and here.

Have fun with the face tracking SDK!

 

来源

Tags: , ,

from 增强视觉 | 计算机视觉 增强现实: http://www.cvchina.info/2012/05/25/kinect-face-tracking/

Written by cwyalpha

五月 25, 2012 at 4:10 下午

发表在 Uncategorized

Thought this was cool: Google code android开源项目(五)

leave a comment »

1.        diskusage http://code.google.com/p/diskusage/

提供了一种找到存储卡上的文件和消耗了大量的空间目录的方法

2.        themissingtabwidget http://code.google.com/p/themissingtabwidget/

水平tab标签页

3.        xinkvpn http://code.google.com/p/xinkvpn/

通过XinkVpn桌面小工具,将可以实现一键连接/关闭VPN

4.        android-aspectj http://code.google.com/p/android-aspectj/

android使用AspectJ 方法跟踪的例子

5.        roboguice http://code.google.com/p/roboguice/

Android 版google-guice(google的依赖注入框架)

6.        ical-import-export http://code.google.com/p/ical-import-export/

导入导出ical文件

7.        android-gps-emulator http://code.google.com/p/android-gps-emulator/

基于地图模拟gps位置

8.        android-ndk-profiler http://code.google.com/p/android-ndk-profiler/

编译进Android NDK代码生成gprof(打印出程序运行中各个函数消耗的时间,可以帮助程序员找出众多函数中耗时最多的函数)兼容的性能信息

9.        flot-android-chart http://code.google.com/p/flot-android-chart/

使Flot(基于JQuery的纯JavaScript实现的绘图库)运行在android平台上

10.    weibo4j/Weibo4Android http://code.google.com/p/weibo4j/

一款基于新浪微博开放平台API(V2)接口的支持oauth2授权认证方式的Java SDK

11.    simple http://code.google.com/p/simple/

Simple是针对Android发展出来的Basic语言版本

12.    android-calendar-view http://code.google.com/p/android-calendar-view/

android日历控件

13.    scirocco http://code.google.com/p/scirocco/

UI自动化测试工具

14.    resting http://code.google.com/p/resting/

REST客户端

15.    icingadroid http://code.google.com/p/icingadroid/

android版Icinga,Icinga是Nagios(网络监视工具)扩展版本。

16.    android-simple-game http://code.google.com/p/android-simple-game/

一个难度较高的弹幕游戏,国人开发

17.    weather-notification-android http://code.google.com/p/weather-notification-android/

通知栏天气预报

 

转自:http://blog.csdn.net/dellheng/article/details/7173112

本文链接

from 博客园_业精于勤,荒于嬉;行成于思,毁于随: http://www.cnblogs.com/hnrainll/archive/2012/05/25/2518184.html

Written by cwyalpha

五月 25, 2012 at 4:10 下午

发表在 Uncategorized