[源码笔记] OpenCV 2.3 :: Random Trees(二)

源码细节:

训练函数

bool CvRTrees::train( const CvMat _train_data, int _tflag,
const CvMat
_responses, const CvMat _var_idx,
const CvMat
_sample_idx, const CvMat _var_type,
const CvMat
_missing_mask, CvRTParams params )



Step1:清理现场,调用clear()函数,删除和释放所有决策树,清除训练数据等;

Step2:构造适用于单棵决策树训练的参数包CvDTreeParams,主要就是对CvRTParams中一些参数的拷贝;

Step3:构建训练数据CvDTreeTrainData,主要涉及CvDTreeTrainData::set_data()函数。CvDTreeTrainData包含CvDTreeParams格式的参数包、被所有树共享的训练数据(优化结构使最优分裂更迅速)以及response类型和类数目等常用数据,还包括最终构造出来的树节点缓存等。

Step4:检查CvRTParams::nactive_vars使其不大于最大启用变量数;若nactive_vars传参为0,则默认赋值为最大启用变量数的平方根;若小于0,则报错退出;

Step5:创建并初始化一个变量活跃Mask(1×变量总数),初始化过程设置前nactive_vars个变量mask为1(活跃),其余为0(非活跃);

Step6:调用CvRTrees::grow_forest()开始生成森林。

Read More

[无责任乱翻] M.L.是咩啊

[无责任乱翻] Machine Learning, Wald I, July 2002

M.L.是咩啊?(这个缩写邪恶吧)

神经网络(Neural Net,NN)大约发明于1985年,它将两个不同的团体带到了一起:
脑科学家——用NN为人脑的各种功能建模
计算机学者——研究语音识别(Speech Recognition)、字迹识别(Written Character Recognition)以及其他一些困难的预测问题(Prediction Problem)

之后:
一群机器人狂热分子也加入了这个团体,他们感兴趣的有:
监督式训练(Supervised Training)、自学习机器人(Self-learning Robots)

还有:
其余杂七杂八的团体人工智能(Artificial Intelligence)、PCA学习(PAC Learning)

然后,有个毛会——NIPS(Neural Information Processing Systems)诞生了。刚开始,NIPS是各种NN应用目的萌发的温床。NN在预测问题上工作得很好,尽管存在它有一坨局部极值,尽管它总是面临过拟合(Overfitting)的危险。一些牛掰的人开始裁剪NN巨大的结构,来解决一些特殊的问题,比如旋转平移无关的字母识别,等等。

Read More

GOOD LUCK MY WAY

钢炼今年剧场版的主题歌

Hyde老了。曲子和词还是欢乐的,可是高音不亮了。今天我还写检讨了。最近这什么日子啊!
当年钢炼05的OP,放在同一张单曲里,差别感好强烈。

Ready Steady Go

好怀念青春年少!LARUKU、吉普力、小BONEZ,你们都怎么了?!

吐槽Android和宫崎大神

忙了一阵,写了个Android上的媒体程序杂烩,图片浏览、视频播放什么的,用作手势识别的控制Demo。Android或者说Java这个东西,果然是写C++的人三天就能上手的。不过,我还是很不喜欢Java不让主动释放对象这一设计,前段时间写Cuda让我对内存什么的变得相当敏感,定义个状态能bool一定不char,存个值能short一定不int。说到底,还是不信Java能管理任意程序的内存都管理得比开发者或者和开发者一样好。对于没有指针这件事情,也另人纠结,我喜欢星号啊。另外,吐槽一下Java里的boolean,为啥不用bool呢,明明是基于C++,为啥不延续,而偏偏让人多敲3个字符。。不满啊。不过,我很喜欢Java的接口设计。

至于Android,槽点太多,我都懒得吐了。充满差错的注释,混乱的函数命名,死板的工程结构,以及比摩托罗拉还慢的速度,我每天晚上吃饭前都要骂它几句,这货到底是不是Google生的啊。除了开源,除了便宜,除了能方便地用Google的服务,我想不到它有什么好处。如果让我挑平台,一定果断地投靠iOS,人家有一级流畅的UI,酷的基础气质,更重要的是有消费习惯良好的用户群体啊。以前我还抱怨过QT的UI,现在用过Android我就知道自己错了,QT相对Android在UI方面绝对是神级的存在。
有天吃饭时,边上一mm用一HTC手机切水果,黄香蕉出来的时候那叫一个卡啊,一帧一帧的,我这厢拿一iPhone眼看着水果一个个噌噌噌往下掉,羡慕嫉妒恨啊,原来在Android的机器上有没冰香蕉是一样的效果啊。

Read More

[论文笔记] Real-Time Human Pose Recognition in Parts from Single Depth Images

Paper:J. Shotton, A. Fitzgibbon, M. Cook, T. Sharp, M. Finocchio, R. Moore, A. Kipman, and A. Blake. Real-Time Human Pose Recognition in Parts from a Single Depth Image. In CVPR 2011. http://research.microsoft.com/apps/pubs/default.aspx?id=145347


问题描述:文章提出了一种从单张深度图中提取3D骨架节点的方法。这种方法并不使用动作的时序信息,但是快速有效,识别帧率在200fps左右(GPU加速后),精度不逊于现有算法。这也是Kinect动作识别的核心算法。
文章最主要的贡献在于:将Pose estimation作为Object recognition看待,提出了一种新颖的识别方法——将Body part segmentation问题作为基于像素的分类问题来处理,这样就不需要对不同节点组合进行搜索,但同时单一部位很可能在局部剧烈地变化。算法的计算复杂度低,精度高。文章的实验部分还论证了以下观点:1)作为训练用的深度数据,合成数据可以很好地代替真实数据;2)获得高精度的重要一步是扩大并丰富训练数据;3)文章中提出的基于部位的识别方法比模糊的精确最近相邻节点更具有通用性。
2011-5-12 20-04-00

Read More

[论文笔记] Randomized Trees for Real-Time Keypoint Recognition

Paper:V. Lepetit, P. Lagger, and P. Fua. Randomized Trees for Real-Time Keypoint Recognition. In Proceedings of the Conference on Computer Vision and Pattern Recognition, San Diego, CA, June 2005.


问题描述:文章是作者在前作基础上(04年ICCV)的完善之作,研究广泛意义上的特征点匹配问题,应用于相机定标、目标检测等各种领域。特征点匹配算法发展到现在,虽然对形状、视点、光照等变化及遮挡等逐渐变得鲁棒,但是没有算法引入过目标的三维信息和可能可以获得的训练图片等,匹配效果还有较大的提升空间。文章提出的算法引入了这些额外的信息,离线合成目标稳定特征点的各个视角,实时通过多类随机决策树将检测到的特征点分类(识别对应视角),最终使用RANSAC-method估计目标的3D姿态,达到匹配的目的。算法有效、实时、鲁棒。

训练数据的获取
对于立体目标,至少需要2张训练图片;对于平面目标,至少1张。对于目标的每一个特征点,生成其在各个视点下以其为中心的patch合集,如下图所示。假设目标是平面的,简单的仿射变换即可,定义缩放、选择、扭曲等参数,通过随机参数的方式生成样例;但对于立体的目标,至少需要2张不同视角的图片,用于重建目标的三维模型,再通过渲染技术生成样例(或者像google街景一样使用基于图像的渲染技术)。注:只适用于非凹体。所有的样本在训练之前还会进行高斯化、2D朝向估计与对齐的预处理,作为归一化的手段,使得分类更为容易。
2011-5-10 14-11-42

Read More

[基础算法] Graph Cut and Its Application in Computer Vision

网络流算法最初用于解决流网络的优化问题,比如水管网络、通信传输和城市的车流等。Graph cut作为其中一类最常见的算法,用于求解流网络的最小割,即寻找一个总容量最小的边集合,去掉这个集合中的所有边将阻断这个网络。图像和视频也能被视作网络(或者MRF),以像素作为节点,具体应用定义相邻像素间边的能量值(容量)。因此从九十年代末开始,Graph cut渐渐被引入计算机视觉、图像处理和机器学习领域,用于优化分类、分割和合成等问题。

The Max-Flow and Min-Cost Problem:
定义图(或者流网络)G = (V, E),可以为有向图或无向图。图中所有的边 e(u, v) ∈ E 附有一个非负的容量 c(u, v) ≥ 0,即该边所能承受的最大流量。图中通常定义两个特殊的节点,源点 s 和终点 t;存在拥有多个端点的图,对其的Max-flow求解为NP问题,需要转化为双端点问题求解次优解。定义满足以下条件的 f : VXV → R 为图 G 上的流:
   ●  Capacity Constrain,对于所有 u, v ∈ Vf(u, v) ≤ c(u, v)    ●  Skew Symmetry,对于所有 u, v ∈ Vf(u, v) = ﹣f(u, v)    ●  Flow Conservation,对于所有 u ∈ V﹣{s, t}v ∈ V∑ f(u, v) = 0 s 出发的所有流量的总和就是整个图的总流量。如下图所示,图的当前总流量为19,没有达到最大值。
 
Cut(割)将整个图的所有节点分为两个不相交的集合 ST,比如s ∈ St ∈ T。割的容量定义为:
     c(S, T) = ∑x∈S y∈T c(x, y)
Min-cut(最小割)就是图的所有割中容量最小的一个。算法上要直接找Min-cut是十分困难的,根据最大流最小割定理,即图的最大流量等于图的最小割容量,通常要将问题转化为与之等价的Max-flow问题(理论推导点我)。

Read More

[论文笔记] CUDA Cuts: Fast Graph Cuts on the GPU

Paper:V. Vineet, P. J. Narayanan. CUDA cuts: Fast graph cuts on the GPU. In Proc. CVPR Workshop, 2008.


问题概述:Graph cut是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。但在获得不错效果的同时,Max-flow / Min-cost问题求解的时间代价却很大。本文作者称其所知最佳的Graph cut实现求解一张640×480的图至少需100毫秒(平均数据会差得多),无法满足实时应用的需求。但事实上,Max-flow求解中经典的Push-relabel算法在流的计算和维护上只与局部相关,具有潜在的可并行性,适于GPU加速。因此,作者实现了push-relabel算法的GPU版。作者称其算法于一张640×480的图平均每秒可以求解150次Graph cut(Nvidia 8800 GTX),也就是约6.7毫秒速,是传统CPU算法约30-40倍速。作者还提供源码的下载,点我

Definition & Notation: 对于一个图 G = (V, E) ,其中 V 为节点集合,包括源点 s 和终点 t (也可以定义多个端点,其可以优化为双顶点图)、以及其他诸多中间节点集合 V’E 为连接这些节点的边,每条边附有容量 c(u, v) 代表节点 u 通过这条边流向节点 v 所能承受的最大流量,在具体应用中边的容量通常等价于其能量值。Graph cut的目的在于找到图的Min-cut,Cut将 V’ 分割为两个部分,去掉这些边将使舍得图中的任意一个节点只与 st 相连通(如下图),而Min-cut是所有cut中边的能量值总和最小的一个。
3-2-2011 2-56-05 PM

Read More