图像的区域协方差特征是几乎线性的特征

2012年03月7日

2006年由Oncel Tuzel等人在ECCV上发表了一篇题为《Region Covariance: A Fast Descriptor for Detection and Classification》的论文,提出了一种新的、可以通过积分图像快速计算大图中任何区域子图的协方差特征。这个特征和常见的向量形式的特征最大的 不同之处就是其为矩阵形式。应用矩阵代替向量作为机器学习方法中的训练和测试样本(模式)有其独有的优势,比如矩阵拥用行和列两个方向的数据关联性,而向 量则只有一个方向的关联性,因此矩阵就同样的维数来说能比向量蕴含更多的信息。南航的陈松灿教授等人就矩阵作为样本做过较为系统的研究《Feature extraction approaches based on matrix pattern: MatPCA and MatFLDA》,并将PCA与FLDA这两个经典算法推广到了矩阵样本下。

协方差矩阵本身的研究工作有很多,在信号处理,医学图像处理领域里应用非常广泛。协方差矩阵本身是一个正定对称矩阵,而对正定对称矩阵的数学方面的研究工作又有比较多的成果,比如:Pennec的《A Riemannian Framework for Tensor Computing》,V. Arsigny的《Geometric means in a novel vector space structure on symmetric positive-definite matrices》,Fo ̈rstner的《A metric for covariance matrices》等。

由于协方差矩阵张成的空间并不是线性的,而是一个非线性的流形空间。很多学者有利用协方差矩阵作为特征并应用到目标跟踪,如《Covariance Tracking using Model Update Based on Lie Algebra》,行人检测如《Fast Pedestrian Detection Using a Cascade of Boosted Covariance Features》等,还有分类方面的《Region Covariance: A Fast Descriptor for Detection and Classification》等等,几乎常见的特征应用场合均可使用,且效果不错。

上面说到,由于协方差特征是分布于非线性流形空间中的点,因此对于均值计算和空间中任意两点(两个矩阵)之间的距离度量就会有相应的研究:《A metric for covariance matrices》、《Geometric means in a novel vector space structure on symmetric positive-definite matrices》、《Matrix means and the Riemannian center of mass》、《Learning Averages over the Lie Group of Symmetric Positive-Definite Matrices》等等。

上面介绍完协方差特征,现在切入我想说的正题,很简单的一个内容:通过Lie-Fisher算法及基于李群(矩阵)核的KLieDA和SVM算法的实验分 析,协方差矩阵虽然是流形空间中的样本,但是非常线性!Lie-Fisher将协方差特征投影到李代数(单位元处的切平面)后,采用近似线性的算法达到很 好的分类效果。另外,KLieDA和SVM对协方差矩阵采用(我自己推导的)线性核或低阶多项式核后分类效果也非常理想。目前的实验是在MNIST和 USPS两个手写体数据集上得出的这个结果。

下图是Lie-Fisher对MNIST数据集中1和9的分类结果,纵坐标是分类精度(%),横坐标是运行次数,每次均随机抽取200个测试样本,200个训练样本,每类100个:

KLieDA和SVM的实验目前只得到数据,图还没画,稍后贴上。

同时本文也发布在我的人人小站《李群机器学习》上,网址为:http://zhan.renren.com/liegroupml?from=rrprofile

Gouraud着色的实现(附图+源码)

2011年12月19日

前段时间抽了几个晚上的空写了下Gouraud着色的代码,放在这里简单讲讲。

在实时计算机图形学里,多边形的光栅化填充算法有很多,比如Flat Shading,Gouraud Shading,Texture等等,其中Texture里又有很多版本,比如二线性插值,三线性插值等等,今天我在这里只谈Gouraud着色。简单讲讲过程,详细原理就不讲了,读者可以参考很多教材或资料,以及我放在下面的源代码。

Flat着色是最简单的填充算法,整个多边形只需要单一的颜色将封闭多边形内部区或填满即可,而Gouraud着色不同的地方在于其填充颜色不止一种,对于一般的三角形来说,给每一个顶点一个独立的颜色,填充完毕后的效果要使每个顶点周围的像素颜色很接近顶点颜色,而慢慢过渡到其他顶点的像素颜色也按纵向和横向两个方向进行线性插值,计算得到当前像素位置的颜色,不断循环,直至完成所有多边形内像素的颜色计算与填充。

现在对照下面的图来简单说一下算法思想:

图1.三角形

阅读这个条目剩下部分 »

简单的李群分类器代码及实验

2011年03月22日

前几天和张老师交谈,谈话间,张老师要我写一个最简单的李群分类器的实验代码,于是回去后,尝试写了一下,当天晚上写了最初的实验,但效果不佳,经过小的改进,实验效果已经比较理想.

实验在Matlab7(R14)下完成,因为只是为了演示李群分类器的方法,因此为简便起见, 训练数据和测试数据均用randn(n,2)+u生成二维高斯分布的随机数据.然后对每个二维的样本点进行李群化,方法是:

给定一个参考向量,如rv(1,1), 对于样本点x(x1,x2),的模长(二阶范数)记为a=sqrt(x1^2+x2^2), 记算样本x向量和rv向量的夹角: angle = acos( (rv(1)*x(1)+rv(2)*x(2)) / (rv_l*a) );(rv_l是向量rv的模长). 对于任一向量x变换到向量rv(或和rv的差异)可以用a和angle两个量来衡量, 因为向量就是大小和方向,那么对x的方向按顺时针(或逆时针)转angle角就可和参考向量rv一致, 对于x的模长,也只要按a倍缩放便可达到,于是对于任何一个样本点x(x1,x2),可以相当于乘上一个变换矩阵M就可变换成为参考向量rv,M可表示成:

阅读这个条目剩下部分 »

Nomad3D纯软件3D引擎初步支持MS3D骨骼动画,上图

2011年03月1日

Nomad3D在设计当初就采用纯软件渲染作为后台实现,主要针对无GPU的手掌设备,小型设备,运算基本都由CPU完成,因为这个特点,考虑到这些设备一般也没有太大的内存空间和充分大的显示屏,因为不怎么需要功能过于丰富的大型建模软件的格式,所以一开始就决定采用MilkShape 3D的MS3D格式作为主要格式,由于从最初编码工作的各阶段进度都没有写成博客贴出来,今天因为昨晚完成了MS3D骨骼动画显示的重要成果(这是对我来说的),于是就贴一下,以后也会陆续发表关于Nomad3D开发进度的相关博文。 

关于MilkShape 3D的MS3D格式,其实很多国外3D游戏开发的教材都有提到,包括代码连NeHe的OpenGL教程也有详细的介绍和代码:NeHe OpenGL Lesson: 31,但该教程关于MS3D格式的骨骼动画并没有涉及,只是简单读取3D模型并借以OpenGL显示出来而以,另有一本书《Focus On 3D Model》中第6章详细分析了MS3D文件格式(by the way,这是一本非常好的介绍各种3D模型文件格式的书,第五章还对骨骼动画的原理进行了很浅显易懂的讲解,我已将这章翻译了,感兴趣的读者可以跳转到:骨骼动画导论(一)以及骨骼动画导论(二)),同时书本的配套源码实现了MS3D骨骼动画,不过也是借以OpenGL方式进行渲染,由于Nomad3D的实现不依赖OpenGL和DirectX技术,而相关的MS3D格式骨骼动画的文章不是很少就是讲解不够充分,因此使得用软件实现MS3D骨骼动画的难度稍大了一点,这主要是OpenGL的矩阵是右乘,变换和Nomad3D的实现也有点不同。通过分析《Focus On 3D Model》的代码,并跟踪代码,加上经推导我的变换矩阵,等等排除多种障碍,终于完成了Nomad3D的MS3D的骨骼动画,上图,图1为模型文件骨骼动画的第一帧,图2.左为在MilkShape 3D软件中原始模型文件的标准参考姿式,右为在MilkShape 3D中显示的第一帧。 

 

图1.   图中的人物模型来自《Focus On 3D Model》一书配套资源,图中显示的是骨骼动画的第一帧(光源放置在后方)。 

阅读这个条目剩下部分 »

完成将当前版本的GB模拟器移植到NDS上(附图)

2011年02月16日

花了两天时间,将当前版本的NomadGB(无声音支持)移植到了NDS上,除了运行速度比较慢以外,其他效果均与PC版无异,由于代码是由C++写的,没有任何优化移植到主CPU为68Mhz的NDS上运行,速度慢是可想而知的,不过可以优化的余地很大,比如目前内存和IO寄存器读写的函数改为内联,因为这几个函数调用频率非常高,至少一个机器周期(从内存取指)内就会被调用到,遇到中断保留现场,压栈等情况,总之改为内联后肯定速度明显提升。另外,将这几个函数,CPU指令集的模拟代码以及画扫描线的代码改为汇编的话,肯定有质的提升。如果以后有空,就试着改进一下吧,现在就先放几张NDS版的截图:

阅读这个条目剩下部分 »

我的GameBoy模拟器开发进展(含截图):添加MBC2芯片模拟, 调试通过MBC1和MBC2的RAM保存功能

2010年12月18日

MBC2的代码前阵子加的, 今天下午调试了一下MBC1和MBC2两块内存块控制芯片的写入功能, 也就是卡带上RAM的写入功能, 并简单测试通过了,下面这个截图是使用MBC2芯片的游戏<圣斗士星矢>的保存界面(已保存OK):

一共可保存两条记录,第一条保存,第二条未用.

阅读这个条目剩下部分 »

公交公司的数据分析及导入程序终于搞完

2010年12月4日

同学导师的手头有一个项目,是关于苏州公交公司数据分析与数据挖掘的一个项目,要求我同学帮他把数据导入到数据库,而这些文件格式为纯文本,但文件非常大(大到几个G),试了N多软件都没法处理,于是我帮他写了个程序将文件内的数据分析出来后,再导入到数据库.

花了前天和昨天两天时间,终于将程序搞定.

支持用ini文件配置数据,  数据库操作用ADO, 为了在分析和导入数据时不至于导致应用程序界面无法响应消息, 采用多线程来处理,界面控件消息响应和数据处理为单独线程,互不干扰,另外源数据文件本身格式为UTF8格式, 程序添加了将分析出来的UTF8编码转换为GB2312的功能, 然后再导入数据库.

昨天已成功导入多份数据文件,今天开始导入一个近4G的文件,速度还不错,下面是程序运行的截图:

我的GameBoy模拟器新进度(附截图):添加带MBC1芯片游戏模拟, 按键功能添加

2010年12月2日

进度1: 按键功能添加上了,是在更新每一帧之间对按键做的处理, 1/60秒的处理间隔, 应该没什么问题, 试玩了一下感觉不错.

进度2: 花了几个小时调试了一下之前写的MBC1芯片的代码, 终于可以运行带MBC1芯片的游戏了,经典的<Super Mario Land>跑起来的画面,真是激动了一下.

问题: 发现了一些问题,主要感觉是Tile Map的处理问题, 部分游戏几本没影响, 而另一部分游戏会在显示上出现一些小问题.

放上效果图:

带MBC1芯片的<Super Mario Land>基本正常,只有暂停时会有小小的Tile Map错误

阅读这个条目剩下部分 »

我的GameBoy模拟器新进度:无MBC芯片游戏模拟效果截图

2010年11月30日

经过一个下午加上一个晚上的努力调试和排错,终于在上午完成正常启动开机ROM的情况下,完成了无MBC芯片的游戏的模拟,附几张截图,如下


32KB大小的的俄罗斯方块
阅读这个条目剩下部分 »

我的GameBoy模拟器开发进展(含截图):开机运行画面正常

2010年11月30日

前几个星期花了不少时间钻研GameBoy掌机的非官方硬件文档,感觉不难,于是着手试着模拟GB掌机,目前已完成大部分硬件的模拟,黑白版GameBoy开机运行的256Byte的CPU内部ROM也很正常,比较OK,开机画面的截图如下:


这是GB开机后的效果:Nintendo(任天堂)Logo从屏幕上方渐渐移动到屏幕中间的过程
阅读这个条目剩下部分 »