2015-05-06 09:27:53 hjimce 阅读数 5922

这里要跟大家分享的paper为基于特征线的图像 morphing,对应的英文文献为《Feature-Based Image Metamorphosis》,是1992年SIGGRAPH 上的一篇paper,比较老的一篇paper,然而这篇paper引用率非常高,用于图像变形效果还是挺不错的,这个算法一般用于图像的morphing。因为这篇paper算法原理简单,易于实现,所以不用怕学习这个算法需要多长的时间。

开始之前先声明一下,这篇博文主要参考自:http://www.csie.ntu.edu.tw/~b97074/vfx_html/hw1.html  同时结合我自己的理解,跟大家分享算法,帮助更多爱好者学习,非商业用途。

一、相关理论

我们知道图像变形的本质,其实就是求取光流场,就是求取目标图像的每一个像素点在原图像的对应位置点,然后同过双线性插值的方法就可以求得目标图像。

1、单线段约束变形:


给定原图像Source Image,我们希望把原图像上的像素点P'、Q'位置移动到P、Q位置,那么其它的像素点的位置要怎么移动,才能使得得到的结果图像Destination Image不会发生严重扭曲,这便是图像变形的研究内容。如图所示,如果用逆向映射的变形方法,对于目标图像上的任意一点X,我们只需要求取source image 上的对应点X'就可以了,当然逆向映射X'往往不是整数,需要经过线性插值,获取X'的像素值。

已知PQ,P'Q',X点,我们要怎么求出X的对应点X'呢?


其实很简单,其原理是通过保证图中二维(u,v)坐标不变就可以了,也就是我们可以通过上面的三个计算公式,求出X'。说的简单一点呢,就是保证X相对于PQ的比例位置坐标(u,v)不变。

2、多线段约束变形

上面是对于单线段约束而言的,对于多线段的情况,主要是通过加权平均的方法。


如图,现在已知P1Q1,P2Q2,X,以及源图像的P1'Q1',P2'Q2',我们要求取X'点。

这个时候我们可以先用单线段约束的方法

(1)通过P1Q1 、P1'Q1'、X 计算出X1’;

(2)通过P2Q2 、P2'Q2'、X 计算出X2’;

然后通过加权平均的方法,求出X':


其中权值w的计算方法就是通过点X到线段的距离成反比的函数计算:


其中length表示线段的长度,dist表示点X到线段的最短距离。a,b,p为常数,对于它们的取值我们可以选p = 0 , a = 1 , b = 2。

ok,到了这里算法就结束了,感觉松松,我们就可以计算出X’点,


因为X'计算出来一般不可能刚好位于原图像像素点的位置,因此我们需要通过双线性插值的方法,求取X'的像素值。

看完上面应该知道怎么计算X'点了吧。接着我们要进入算法实现阶段。

二、算法实现

说明以下代码参考自:http://www.csie.ntu.edu.tw/~b97074/vfx_html/hw1.html

Algorithm:

1、根据公式1,2,计算X点相对于各线段的位置(u,v)坐标。


double new_u = dst_line.Getu(X);
double new_v = dst_line.Getv(X);
//公式1
double Line::Getu(Vector2 X)
{
	double X_P_x = X.x - P.x; 
	double X_P_y = X.y - P.y;
	double Q_P_x = Q.x - P.x;
	double Q_P_y = Q.y - P.y;
	double u = ((X_P_x * Q_P_x) + (X_P_y * Q_P_y)) / (len * len)  ;
	return u ;
}
//公式2
double Line::Getv(Vector2 X){
	double X_P_x = X.x - P.x;
	double X_P_y = X.y - P.y;
	double Q_P_x = Q.x - P.x;
	double Q_P_y = Q.y - P.y;
	double Perp_Q_P_x = Q_P_y ;  
	double Perp_Q_P_y = -Q_P_x ;
	double v = ((X_P_x * Perp_Q_P_x) + (X_P_y * Perp_Q_P_y))/len ; 
	return v ; 
}

2、根据公式3,然后反算X点在源图像的位置对应点X'。

Vector2 src_point = src_line.Get_Point(new_u , new_v);
//根据u,v坐标可计算出pq线段的对应点x
Vector2 Line::Get_Point(double u , double v)
{
	double Q_P_x = Q.x - P.x;
	double Q_P_y = Q.y - P.y;
	double Perp_Q_P_x = Q_P_y ;  
	double Perp_Q_P_y = -Q_P_x ;
	double Point_x = P.x + u * (Q.x - P.x) + ((v * Perp_Q_P_x)/len) ;
	double Point_y = P.y + u * (Q.y - P.y) + ((v * Perp_Q_P_y)/len) ;
	Vector2 X;
	X.x = Point_x;
	X.y = Point_y;
	return X ;
}

3、计算各个线段的权重。

double src_weight = dst_line.Get_Weight(dst_point);

double Line::Get_Weight(Vector2 X )
{
	double a = parameter_a;
	double b = parameter_b;
	double p = parameter_p;
	double d = 0.0;

	double u = Getu(X);
	if(u > 1.0 )
		d = sqrt((X.x - Q.x) * (X.x - Q.x) + (X.y - Q.y) * (X.y - Q.y));
	else if(u < 0)
		d = sqrt((X.x - P.x) * (X.x - P.x) + (X.y - P.y) * (X.y - P.y));
	else
		d = abs(Getv(X));


	double weight =pow(pow((float)len,(float)p)/(a + d) , b);
	return weight; 
}

然后对所有的X'点进行加权求和就可以了。

ok,上面过程的代码合在一起,遍历每一条约束线段。

4、最后进行双线性插值。

双线性插值函数如下:

void bilinear(BitmapData *psrcImgData,float X ,float Y,byte*resultpiexl)
{
	int x_floor = (int)X ;
	int y_floor = (int)Y ;
	int x_ceil = x_floor + 1 ;
	int y_ceil = y_floor + 1 ;
	float a = X - x_floor ;
	float b = Y - y_floor ;

	if(x_ceil >= psrcImgData->Width-1) 
		x_ceil =psrcImgData->Width-1 ;
	if(y_ceil >= psrcImgData->Height-1) 
		y_ceil = psrcImgData->Height-1 ;
	byte leftdown[3]; 
	byte lefttop[3]; 
	byte rightdown[3]; 
	byte righttop[3]; 
    Get2D(psrcImgData,y_floor,x_floor,leftdown);
	Get2D(psrcImgData,y_ceil,x_floor,lefttop);
	Get2D(psrcImgData,y_floor,x_ceil,rightdown);
	Get2D(psrcImgData,y_ceil,x_ceil,righttop);
	for(int i = 0 ; i < 3 ; i ++)
	{
		resultpiexl[i] = (1-a)*(1-b)*leftdown[i] + a*(1-b)*rightdown[i] + a*b*righttop[i] + (1-a)*b*lefttop[i];
	}
}
void Get2D(BitmapData *psrcImgData, int Y,int X, byte*piexl)
{
	byte*pdata=(byte*)psrcImgData->Scan0+(psrcImgData->Width*Y+X)*4;
	for (int i=0;i<3;i++)
	{
		piexl[i]=pdata[i];
	}

}


最后贴一下整个过程的代码:

	int nWidth=prightImgData->Width;
	int nHeight=prightImgData->Height;
    for(int x = 0 ; x < nWidth ; x++)
	{
        for(int y = 0 ; y < nHeight ; y++)
		{
			Vector2 dst_point ;
			dst_point.x= x ; 
			dst_point.y= y;
			double leftXSum_x = 0.0;
			double leftXSum_y = 0.0;
			double leftWeightSum = 0.0;
			double rightXSum_x = 0.0;
			double rightXSum_y = 0.0;
			double rightWeightSum = 0.0;
			for(int i = 0 ; i < pairs.size() ; i++)
			{

				Line src_line = pairs[i].leftLine;	
				Line dst_line = pairs[i].rightLine;

				double new_u = dst_line.Getu(X);//计算(u,v)坐标
				double new_v = dst_line.Getv(X);

				Vector2 src_point = src_line.Get_Point(new_u , new_v);//计算源图像的对应点X'
				double src_weight = dst_line.Get_Weight(dst_point);//计算权重
				leftXSum_x = leftXSum_x + (double)src_point.x * src_weight ;//加权求X'的平均位置
				leftXSum_y = leftXSum_y + (double)src_point.y * src_weight ;
				leftWeightSum = leftWeightSum + src_weight ;
			}
			double left_src_x = leftXSum_x / leftWeightSum;
			double left_src_y = leftXSum_y / leftWeightSum;
			double right_src_x = x;
			double right_src_y = y;


			if(left_src_x<0)//判断是否越界
				left_src_x=0;
			if(left_src_y<0)
				left_src_y=0;
			if(left_src_x>=pleftImgData->Width)
				left_src_x=pleftImgData->Width-1;
			if(left_src_y>=pleftImgData->Height)
				left_src_y=pleftImgData->Height-1;

			byte leftimg[3];//存储最后的(x,y)点的像素值
			bilinear(pleftImgData,left_src_x,left_src_y,leftimg);//线性插值
			for (int i=0;i<3;i++)
			{
				float newpiexl=leftimg[i];


			}
        }
    }

本文地址:http://blog.csdn.net/hjimce/article/details/45531039     作者:hjimce     联系qq:1393852684   更多资源请关注我的博客:http://blog.csdn.net/hjimce                原创文章,转载请保留本行信息。

最后看一下,用这个算法实现的变形融合:

原图像:


变形融合结果:


参考文献:

1、http://www.csie.ntu.edu.tw/~b97074/vfx_html/hw1.html
2、Feature-Based Image Metamorphosis


2015-09-11 16:09:03 meteor_0033 阅读数 173
         今天学习一篇论文,《采用多组单应约束和马尔可夫随机场的运动目标检测算法》,其中讲到实验数据来自Hopkins 155数据集,我也需要数据中的视频数据,在网站上搜索没有找到,通过论文中引用的参考文献《A_benchmark_for_the_comparison_of_3D_motion_segment_algorithms.pdf》,终于找到了出处http://vision.jhu.edu/data/,已成功下载,尽天下午,收获很大,感谢两位作者。
2012-05-30 08:41:34 dcraw 阅读数 14487

Last update: 2012-6-7


这一章是计算机视觉部分,主要侧重在底层特征提取,视频分析,跟踪,目标检测和识别方面等方面。对于自己不太熟悉的领域比如摄像机标定和立体视觉,仅仅列出上google上引用次数比较多的文献。有一些刚刚出版的文章,个人非常喜欢,也列出来了。


本章的下载地址:

http://iask.sina.com.cn/u/2252291285/ish?folderid=868772


1. Active Appearance Models

活动表观模型和活动轮廓模型基本思想来源Snake,现在在人脸三维建模方面得到了很成功的应用,这里列出了三篇最初最经典的文章。对这个领域有兴趣的可以从这三篇文章开始入手。

[1998 ECCV] ActiveAppearance Models

[2001 PAMI] ActiveAppearance Models

 

2. Active Shape Models

[1995 CVIU]Active ShapeModels-Their Training and Application

 

3. Background modeling andsubtraction

背景建模一直是视频分析尤其是目标检测中的一项关键技术。虽然最近一直有一些新技术的产生,demo效果也很好,比如基于dynamical texture的方法。但最经典的还是Stauffer等在1999年和2000年提出的GMM方法,他们最大的贡献在于不用EM去做高斯拟合,而是采用了一种迭代的算法,这样就不需要保存很多帧的数据,节省了buffer。Zivkovic在2004年的ICPR和PAMI上提出了动态确定高斯数目的方法,把混合高斯模型做到了极致。这种方法效果也很好,而且易于实现。在OpenCV中有现成的函数可以调用。在背景建模大家族里,无参数方法(2000 ECCV)和Vibe方法也值得关注。

[1997 PAMI] PfinderReal-Time Tracking of the Human Body

[1999 CVPR] Adaptivebackground mixture models for real-time tracking

[1999 ICCV] WallflowerPrinciples and Practice of Background Maintenance

[2000 ECCV] Non-parametricModel for Background Subtraction

[2000 PAMI] LearningPatterns of Activity Using Real-Time Tracking

[2002 PIEEE] Backgroundand foreground modeling using nonparametric kernel density estimation forvisual surveillance

[2004 ICPR] Improvedadaptive Gaussian mixture model for background subtraction

[2004 PAMI] Recursiveunsupervised learning of finite mixture models

[2006 PRL] Efficientadaptive density estimation per image pixel for the task of backgroundsubtraction

[2011 TIP] ViBe AUniversal Background Subtraction Algorithm for Video Sequences

 

4.  Bag of Words

词袋,在这方面暂时没有什么研究。列出三篇引用率很高的文章,以后逐步解剖之。

[2003 ICCV] Video Google AText Retrieval Approach to Object Matching in Videos

[2004 ECCV] VisualCategorization with Bags of Keypoints

[2006 CVPR] Beyond bags offeatures Spatial pyramid matching for recognizing natural scene categories

 

5.  BRIEF

BRIEF是BinaryRobust Independent Elementary Features的简称,是近年来比较受关注的特征描述的方法。ORB也是基于BRIEF的。

[2010 ECCV] BRIEF BinaryRobust Independent Elementary Features

[2011 ICCV] ORB anefficient alternative to SIFT or SURF

[2012 PAMI] BRIEFComputing a Local Binary Descriptor Very Fast

 

6. Camera Calibration and StereoVision

非常不熟悉的领域。仅仅列出了十来篇重要的文献,供以后学习。

[1979 Marr] AComputational Theory of Human Stereo Vision

[1985] Computationalvision and regularization theory

[1987 IEEE] A versatilecamera calibration technique for high-accuracy 3D machine vision metrologyusing off-the-shelf TV cameras and lenses

[1987] ProbabilisticSolution of Ill-Posed Problems in Computational Vision

[1988 PIEEE] Ill-PosedProblems in Early Vision

[1989 IJCV] KalmanFilter-based Algorithms for Estimating Depth from Image Sequences

[1990 IJCV] RelativeOrientation

[1990 IJCV] Usingvanishing points for camera calibration

[1992 ECCV] Cameraself-calibration Theory and experiments

[1992 IJCV] A theory ofself-calibration of a moving camera

[1992 PAMI] Cameracalibration with distortion models and accuracy evaluation

[1994 IJCV] TheFundamental Matrix Theory, Algorithms, and Stability Analysis

[1994 PAMI] a stereomatching algorithm with an adaptive window theory and experiment

[1999 ICCV] Flexiblecamera calibration by viewing a plane from unknown orientations

[1999 IWAR] Markertracking and hmd calibration for a video-based augmented reality conferencingsystem

[2000 PAMI] A flexible newtechnique for camera calibration

 

7. Color and Histogram Feature

这里面主要来源于图像检索,早期的图像检测基本基于全局的特征,其中最显著的就是颜色特征。这一部分可以和前面的Color知识放在一起的。

[1995 SPIE] Similarity ofcolor images

[1996 PR] IMAGE RETRIEVALUSING COLOR AND SHAPE

[1996] comparing imagesusing color coherence vectors

[1997 ] Image IndexingUsing Color Correlograms

[2001 TIP] An EfficientColor Representation for Image Retrieval

[2009 CVIU] Performanceevaluation of local colour invariants

 

8. Deformable Part Model

大红大热的DPM,在OpenCV中有一个专门的topic讲DPM和latent svm

[2008 CVPR] ADiscriminatively Trained, Multiscale, Deformable Part Model

[2010 CVPR] Cascade ObjectDetection with Deformable Part Models

[2010 PAMI] ObjectDetection with Discriminatively Trained Part-Based Models

 

9. Distance Transformations

距离变换,在OpenCV中也有实现。用来在二值图像中寻找种子点非常方便。

[1986 CVGIP] DistanceTransformations in Digital Images

[2008 ACM] 2D EuclideanDistance Transform Algorithms A Comparative Survey

 

10. Face Detection

最成熟最有名的当属Haar+Adaboost

[1998 PAMI] NeuralNetwork-Based Face Detection

[2002 PAMI] Detectingfaces in images a survey

[2002 PAMI] Face Detectionin Color Images

[2004 IJCV] RobustReal-Time Face Detection

 

11. Face Recognition

不熟悉,简单罗列之。

[1991] Face RecognitionUsing Eigenfaces

[2000 PAMI] AutomaticAnalysis of Facial Expressions The State of the Art

[2000] Face Recognition ALiterature Survey

[2006 PR] Face recognitionfrom a single image per person A survey

[2009 PAMI] Robust FaceRecognition via Sparse Representation

 

12. FAST

用机器学习的方法来提取角点,号称很快很好。

[2006 ECCV] Machinelearning for high-speed corner detection

[2010 PAMI] Faster andBetter A Machine Learning Approach to Corner Detection

 

13.  Feature Extraction

这里的特征主要都是各种不变性特征,SIFT,Harris,MSER等也属于这一类。把它们单独列出来是因为这些方法更流行一点。关于不变性特征,王永明与王贵锦合著的《图像局部不变性特征与描述》写的还不错。Mikolajczyk在2005年的PAMI上的文章以及2007年的综述是不错的学习材料。

[1989 PAMI] On thedetection of dominant points on digital curves

[1997 IJCV] SUSAN—A NewApproach to Low Level Image Processing

[2004 IJCV] MatchingWidely Separated Views Based on Affine Invariant Regions

[2004 IJCV] Scale &Affine Invariant Interest Point Detectors

[2005 PAMI] A performanceevaluation of local descriptors

[2006 IJCV] A Comparisonof Affine Region Detectors

[2007 FAT] Local InvariantFeature Detectors - A Survey

[2011 IJCV] Evaluation ofInterest Point Detectors and Feature Descriptors

 

14. Feature Matching

[2012 PAMI] LDAHashImproved Matching with Smaller Descriptors

 

15.  Harris

虽然过去了很多年,Harris角点检测仍然广泛使用,而且基于它有很多变形。如果仔细看了这种方法,从直观也可以感觉到这是一种很稳健的方法。

[1988 Harris] A combinedcorner and edge detector

 

16.   Histograms of OrientedGradients

HoG方法也在OpenCV中实现了:HOGDescriptor。

[2005 CVPR] Histograms ofOriented Gradients for Human Detection

NavneetDalalThesis.pdf

 

17. Image Distance

[1993 PAMI] ComparingImages Using the Hausdorff Distance

 

18. Image Stitching

图像拼接,另一个相关的词是Panoramic。在Computer Vision: Algorithms and Applications一书中,有专门一章是讨论这个问题。这里的两面文章一篇是综述,一篇是这方面很经典的文章。

[2006 Fnd] Image Alignmentand Stitching A Tutorial

[2007 IJCV] AutomaticPanoramic Image Stitching using Invariant Features

 

19.  KLT

KLT跟踪算法,基于Lucas-Kanade提出的配准算法。除了三篇很经典的文章,最后一篇给出了OpenCV实现KLT的细节。

[1981] An Iterative ImageRegistration Technique with an Application to Stereo Vision full version

[1994 CVPR] Good Featuresto Track

[2004 IJCV]  Lucas-Kanade 20 Years On A Unifying Framework

Pyramidal Implementationof the Lucas Kanade Feature Tracker OpenCV

 

20. Local Binary Pattern

LBP。OpenCV的Cascade分类器也支持LBP,用来取代Haar特征。

[2002 PAMI]Multiresolution gray-scale and rotation Invariant Texture Classification withLocal Binary Patterns

[2004 ECCV] FaceRecognition with Local Binary Patterns

[2006 PAMI] FaceDescription with Local Binary Patterns

[2011 TIP]Rotation-Invariant Image and Video Description With Local Binary PatternFeatures

 

21. Low-Level Vision

关于Low level vision的两篇很不错的文章

[1998 TIP] A generalframework for low level vision

[2000 IJCV] LearningLow-Level Vision

 

22. Mean Shift

均值漂移算法,在跟踪中非常流行的方法。Comaniciu在这个方面做出了重要的贡献。最后三篇,一篇是CVIU上的top download文章,一篇是最新的PAMI上关于Mean Shift的文章,一篇是OpenCV实现的文章。

[1995 PAMI] Mean shift,mode seeking, and clustering

[2002 PAMI] Mean shift arobust approach toward feature space analysis

[2003 CVPR] Mean-shiftblob tracking through scale space

[2009 CVIU] Objecttracking using SIFT features and mean shift

[2012 PAMI] Mean ShiftTrackers with Cross-Bin Metrics

OpenCV Computer VisionFace Tracking For Use in a Perceptual User Interface

 

23.  MSER

这篇文章发表在2002年的BMVC上,后来直接录用到2004年的IVC上,内容差不多。MSER在Sonka的书里面也有提到。

[2002 BMVC] Robust WideBaseline Stereo from Maximally Stable Extremal Regions

[2003] MSER AuthorPresentation

[2004 IVC] Robustwide-baseline stereo from maximally stable extremal regions

[2011 PAMI] Are MSERFeatures Really Interesting

 

24. Object Detection

首先要说的是第一篇文章的作者,Kah-Kay Sung。他是MIT的博士,后来到新加坡国立任教,极具潜力的一个老师。不幸的是,他和他的妻子都在2000年的新加坡空难中遇难,让人唏嘘不已。

http://en.wikipedia.org/wiki/Singapore_Airlines_Flight_006

最后一篇文章也是Fua课题组的,作者给出的demo效果相当好。

[1998 PAMI] Example-basedlearning for view-based human face detection

[2000 CVPR] A Statistical Method for 3D Object Detection Applied to Faces and Cars

[2003 IJCV] Learning theStatistics of People in Images and Video

[2011 PAMI] Learning toDetect a Salient Object

[2012 PAMI] A Real-TimeDeformable Detector

 

25. Object Tracking

跟踪也是计算机视觉中的经典问题。粒子滤波,卡尔曼滤波,KLT,mean shift,光流都跟它有关系。这里列出的是传统意义上的跟踪,尤其值得一看的是2008的Survey和2003年的Kernel based tracking。

[2003 PAMI] Kernel-basedobject tracking

[2007 PAMI] TrackingPeople by Learning Their Appearance

[2008 ACM] Object TrackingA Survey

[2008 PAMI] Segmentationand Tracking of Multiple Humans in Crowded Environments

[2011 PAMI] Hough Forestsfor Object Detection, Tracking, and Action Recognition

[2011 PAMI] Robust ObjectTracking with Online Multiple Instance Learning

[2012 IJCV] PWP3DReal-Time Segmentation and Tracking of 3D Objects

 

26. OCR

一个非常成熟的领域,已经很好的商业化了。

[1992 IEEE] Historical reviewof OCR research and development

Video OCR A Survey andPractitioner's Guide

 

27. Optical Flow

光流法,视频分析所必需掌握的一种算法。

[1981 AI] DetermineOptical Flow

[1994 IJCV] Performance ofoptical flow techniques

[1995 ACM] The Computationof Optical Flow

[2004 TR] TutorialComputing 2D and 3D Optical Flow

[2005 BOOK] Optical FlowEstimation

[2008 ECCV] LearningOptical Flow

[2011 IJCV] A Database andEvaluation Methodology for Optical Flow

 

28.  Particle Filter

粒子滤波,主要给出的是综述以及1998 IJCV上的关于粒子滤波发展早期的经典文章。

[1998 IJCV] CONDENSATION—ConditionalDensity Propagation for Visual Tracking

[2002 TSP] A tutorial onparticle filters for online nonlinear non-Gaussian Bayesian tracking

[2002 TSP] Particlefilters for positioning, navigation, and tracking

[2003 SPM] particle filter

 

29. Pedestrian and Human detection

仍然是综述类,关于行人和人体的运动检测和动作识别。

[1999 CVIU] Visualanalysis of human movement_ A survey

[2001 CVIU] A Survey ofComputer Vision-Based Human Motion Capture

[2005 TIP] Image changedetection algorithms a systematic survey

[2006 CVIU] a survey ofavdances in vision based human motion capture

[2007 CVIU] Vision-basedhuman motion analysis An overview

[2007 IJCV] PedestrianDetection via Periodic Motion Analysis

[2007 PR] A survey ofskin-color modeling and detection methods

[2010 IVC] A survey onvision-based human action recognition

[2012 PAMI] PedestrianDetection An Evaluation of the State of the Art

 

30. Scene Classification

当相机越来越傻瓜化的时候,自动场景识别就非常重要。这是比拼谁家的Auto功能做的比较好的时候了。

[2001 IJCV] Modeling theShape of the Scene A Holistic Representation of the Spatial Envelope

[2001 PAMI] Visual WordAmbiguity

[2007 PAMI] A ThousandWords in a Scene

[2010 PAMI] EvaluatingColor Descriptors for Object and Scene Recognition

[2011 PAMI] CENTRIST AVisual Descriptor for Scene Categorization

 

31. Shadow Detection

[2003 PAMI] Detectingmoving shadows-- algorithms and evaluation

32.  Shape

关于形状,主要是两个方面:形状的表示和形状的识别。形状的表示主要是从边缘或者区域当中提取不变性特征,用来做检索或者识别。这方面Sonka的书讲的比较系统。2008年的那篇综述在这方面也讲的不错。至于形状识别,最牛的当属J Malik等提出的Shape Context。

[1993 PR] IMPROVED MOMENTINVARIANTS FOR SHAPE DISCRIMINATION

[1993 PR] PatternRecognition by Affine Moment Invariants

[1996 PR] IMAGE RETRIEVALUSING COLOR AND SHAPE

[2001 SMI] Shape matchingsimilarity measures and algorithms

[2002 PAMI] Shape matchingand object recognition using shape contexts

[2004 PR] Review of shaperepresentation and description techniques

[2006 PAMI] IntegralInvariants for Shape Matching

[2008] A Survey of ShapeFeature Extraction Techniques

 

33.  SIFT

关于SIFT,实在不需要介绍太多,一万多次的引用已经说明问题了。SURF和PCA-SIFT也是属于这个系列。后面列出了几篇跟SIFT有关的问题。

[1999 ICCV] Objectrecognition from local scale-invariant features

[2000 IJCV] Evaluation ofInterest Point Detectors

[2003 CVIU] Speeded-UpRobust Features (SURF)

[2004 CVPR] PCA-SIFT AMore Distinctive Representation for Local Image Descriptors

[2004 IJCV] DistinctiveImage Features from Scale-Invariant Keypoints

[2010 IJCV] ImprovingBag-of-Features for Large Scale Image Search

[2011 PAMI] SIFTflow DenseCorrespondence across Scenes and its Applications

 

34.  SLAM

Simultaneous Localization and Mapping, 同步定位与建图。

SLAM问题可以描述为: 机器人在未知环境中从一个未知位置开始移动,在移动过程中根据位置估计和地图进行自身定位,同时在自身定位的基础上建造增量式地图,实现机器人的自主定位和导航。

[2002 PAMI] SimultaneousLocalization and Map-Building Using Active Vision

[2007 PAMI] MonoSLAMReal-Time Single Camera SLAM

 

35. Texture Feature

纹理特征也是物体识别和检索的一个重要特征集。

[1973] Textural featuresfor image classification

[1979 ] Statistical andstructural approaches to texture

[1996 PAMI] Texturefeatures for browsing and retrieval of image data

[2002 PR] Brief review ofinvariant texture analysis methods

[2012 TIP] Color LocalTexture Features for Color Face Recognition

 

36.  TLD

Kadal创立了TLD,跟踪学习检测同步进行,达到稳健跟踪的目的。他的两个导师也是大名鼎鼎,一个是发明MSER的Matas,一个是Mikolajczyk。他还创立了一个公司TLDVision s.r.o. 这里给出了他的系列文章,最后一篇是刚出来的PAMI。

[2009] Online learning ofrobust object detectors during unstable tracking

[2010 CVPR] P-N LearningBootstrapping Binary Classifiers by Structural Constraints

[2010 ICIP] FACE-TLDTRACKING-LEARNING-DETECTION APPLIED TO FACES

[2012 PAMI]Tracking-Learning-Detection

 

37.  Video Surveillance

前面两个是两个很有名的视频监控系统,里面包含了很丰富的信息量,比如CMU的那个系统里面的背景建模算法也是相当简单有效的。最后一篇是比较近的综述。

[2000 CMU TR] A System forVideo Surveillance and Monitoring

[2000 PAMI] W4-- real-timesurveillance of people and their activitie

[2008 MVA] The evolutionof video surveillance an overview

 

38.  Viola-Jones

Haar+Adaboost的弱弱联手,组成了最强大的利器。在OpenCV里面有它的实现,也可以选择用LBP来代替Haar特征。

[2001 CVPR] Rapid objectdetection using a boosted cascade of simple features

[2004 IJCV] RobustReal-time Face Detection



2015-05-23 10:09:52 hjimce 阅读数 4837

grab cut图像分割

原文地址http://blog.csdn.net/hjimce/article/details/45932569

作者:hjimce

Grab cut算法是2004年才有的算法,自从这个算法出来,在交互是图像分割领域影响极其深刻,目前文献《“GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts》的引用率真不是一般的高,于是图论分割的算法就有很多新算法出现了,还有什么Normarlized Cut 、One cut,但是大体的思路大同小异。

       我第一次学这个算法是在半年前,当时对于高斯混合建模理解的不是很透彻,然后又有Max flow 也不懂,而项目也催的很紧急,所以这个算法当时给我的印象是“好难”。最后只是把图像分割之(二)Graph Cut(图割)这位哥们的博客看了一下,然后思路迷迷糊糊的,不过很感谢他让我学会了grab cut 算法。现在回想起来其实这个算法也不过如此,好了废话不多说,我这里主要结合opencv的grab cut 代码进行讲解,同时参考图像分割之(三)从Graph Cut到Grab Cut 的博文,进行解说grab cut 过程实现流程。不打算将理论的东西,因为理论总是看起来很深奥的样子,其实有时候十几页的理论,就是几行代码的事。

如果你想把原版grab cut代码自己写过一遍,那么需要对以下基础知识非常熟悉:

1、k均值聚类

1、高斯混合模型建模

2、max flow/min cut

一、算法流程

输入:图像、被标记好的前景、背景

输出:分割图像

其中输入的前景、背景指的是一种概率,如果你已经明确某一块区域是背景,那么它属于背景的概率为1;当然如果你觉得它有可能背景,但是没有百分百的肯定,这个时候你就要用到高斯模型,对其进行建模,然后估算概率,这也正是文献的精髓部分。现在我以下图为例,用户通过交互输入框选区域,前景位于框选区域内,也就是说矩形区域外的全部属于背景,且概率为百分百。然后方框内可能属于前景,概率需要用高斯混合建模求解。


其大体算法流程如下:

1、用户交互输入矩形结果,初始化。

/* 
  由用户输入的矩形外面 全部标记为一定是背景
  矩形内部标记为 可能是前景
*/  
void GrabCut::initMaskWithRect( Eigen::MatrixXf& mask, CRect rect )  
{  
	mask.resize(m_Image->Height,m_Image->Width);
	mask.setZero();
	for (int i=rect.TopLeft().y;i<rect.BottomRight().y;i++)
	{
		for (int j=rect.TopLeft().x;j<rect.BottomRight().x;j++)
		{
			mask(i,j)=GC_PR_FGD;

		}
	}
}  


2、建模阶段。根据被标记的信息对前景和背景进行分别高斯混合模型建模。过程大体是先通过k均值进行初始化聚类,然后根据聚类结果,计算每个类的高斯模型参数

/* 
  通过k均值进行聚类 然后根据聚类结果的各类进行高斯建模
*/  
//mask为由用户交互输入的信息
//GC_BGD表示确定为背景 GC_PR_BGD表示可能为背景,也就是属于背景的概率比较大
//GCD_FGD表示确定是前景 GCD_PR_FGD表示可能为前景即前景的概率比较大
void GrabCut::initGMMs(const Eigen::MatrixXf& mask, GMM& bgdGMM, GMM& fgdGMM )  
{  
	int height=m_Image->Height;
	int width=m_Image->Width;
    const int kMeansItCount = 10; //k均值聚类最大迭代次数  
    const int kMeansType = cv::KMEANS_PP_CENTERS;  
  
    cv::Mat bgdLabels, fgdLabels; //聚类结果标号存储
    vector<cv::Vec3f> bgdSamples, fgdSamples; 
    CPoint p;  
    for( p.y = 0; p.y <height; p.y++ )  
    {  
        for( p.x = 0; p.x <width; p.x++ )  
        {  
            
			Eigen::Vector3f  ev=GetPiexl(p,m_Image);
			//把用户输入可能属于背景、或者百分百属于背景的像素点扔进的bgdSamples
            if(mask(p.y,p.x)== GC_BGD || mask(p.y,p.x) == GC_PR_BGD )  
                bgdSamples.push_back(cv::Vec3f(ev[0],ev[1],ev[2]));  
			//把用户输入可能属于前景、或者百分百属于前景的像素点扔进的fgdSamples
            else 
                fgdSamples.push_back(cv::Vec3f(ev[0],ev[1],ev[2]));  
        }  
    }  
    ASSERT( !bgdSamples.empty() && !fgdSamples.empty() );  
      
    //利用k均值初始化聚类 _bgdSamples,得到结果bgdLabels
    cv::Mat _bgdSamples( (int)bgdSamples.size(), 3, CV_32FC1, &bgdSamples[0][0] );  
    kmeans( _bgdSamples, GMM::componentsCount, bgdLabels,  
            cv::TermCriteria( CV_TERMCRIT_ITER, kMeansItCount, 0.0), 0, kMeansType ); 
	//利用k均值初始化聚类fgdSamples 得到结果fgdLabels
    cv::Mat _fgdSamples( (int)fgdSamples.size(), 3, CV_32FC1, &fgdSamples[0][0] );  
    kmeans( _fgdSamples, GMM::componentsCount, fgdLabels,  
            cv::TermCriteria( CV_TERMCRIT_ITER, kMeansItCount, 0.0), 0, kMeansType );  
     
    //根据k均值聚类结果,对每个背景中的高斯混合模型类进行高斯建模 
    bgdGMM.initLearning();  
    for( int i = 0; i < (int)bgdSamples.size(); i++ )  
        bgdGMM.addSample( bgdLabels.at<int>(i,0),Eigen::Vector3f(bgdSamples[i][0],bgdSamples[i][1],bgdSamples[i][2]) );  
    bgdGMM.endLearning();  
    //根据k均值聚类结果,对每个前景中的高斯混合模型类进行高斯建模 
    fgdGMM.initLearning();  
    for( int i = 0; i < (int)fgdSamples.size(); i++ )  
        fgdGMM.addSample( fgdLabels.at<int>(i,0),Eigen::Vector3f(fgdSamples[i][0],fgdSamples[i][1],fgdSamples[i][2]));  
    fgdGMM.endLearning();  
}  

高斯混合模型建模相关函数:

//相关高斯模型参数初始化,可放在析构函数中 
void GMM::initLearning()  
{  
	for( int ci = 0; ci < componentsCount; ci++)  
	{  
		sums[ci][0] = sums[ci][1] = sums[ci][2] = 0;  
		prods[ci][0][0] = prods[ci][0][1] = prods[ci][0][2] = 0;  
		prods[ci][1][0] = prods[ci][1][1] = prods[ci][1][2] = 0;  
		prods[ci][2][0] = prods[ci][2][1] = prods[ci][2][2] = 0;  
		sampleCounts[ci] = 0;  
	}  
	totalSampleCount = 0;  
}  
//根据k均值的聚类标记 计算每个高斯模型的均值及其协方差矩阵
//外部调用 
void GMM::addSample( int ci, const Eigen::Vector3f color )  
{  
	sums[ci][0] += color[0]; sums[ci][1] += color[1]; sums[ci][2] += color[2];  
	prods[ci][0][0] += color[0]*color[0]; prods[ci][0][1] += color[0]*color[1]; prods[ci][0][2] += color[0]*color[2];  
	prods[ci][1][0] += color[1]*color[0]; prods[ci][1][1] += color[1]*color[1]; prods[ci][1][2] += color[1]*color[2];  
	prods[ci][2][0] += color[2]*color[0]; prods[ci][2][1] += color[2]*color[1]; prods[ci][2][2] += color[2]*color[2];  
	sampleCounts[ci]++;  
	totalSampleCount++;  
}  
//外部调用,结束学习
void GMM::endLearning()  
{  
	const float variance = 0.01;  
	for( int ci = 0; ci < componentsCount; ci++ )  
	{  
		int n = sampleCounts[ci]; //第ci个高斯模型的样本像素个数  
		if( n == 0 )  
			coefs[ci] = 0;  
		else  
		{  
			//计算第ci个高斯模型的权值系数 ,也就是这个属于这个类的像素点数占总数的百分比 
			coefs[ci] = (float)n/totalSampleCount;   

			//计算第ci个高斯模型的均值  
			float* m = mean + 3*ci;  
			m[0] = sums[ci][0]/n; m[1] = sums[ci][1]/n; m[2] = sums[ci][2]/n;  

			//计算协方差矩阵结果 
			float* c = cov + 9*ci;  
			c[0] = prods[ci][0][0]/n - m[0]*m[0]; c[1] = prods[ci][0][1]/n - m[0]*m[1]; c[2] = prods[ci][0][2]/n - m[0]*m[2];  
			c[3] = prods[ci][1][0]/n - m[1]*m[0]; c[4] = prods[ci][1][1]/n - m[1]*m[1]; c[5] = prods[ci][1][2]/n - m[1]*m[2];  
			c[6] = prods[ci][2][0]/n - m[2]*m[0]; c[7] = prods[ci][2][1]/n - m[2]*m[1]; c[8] = prods[ci][2][2]/n - m[2]*m[2];  

			//计算协方差矩阵行列式
			float dtrm = c[0]*(c[4]*c[8]-c[5]*c[7]) - c[1]*(c[3]*c[8]-c[5]*c[6]) + c[2]*(c[3]*c[7]-c[4]*c[6]);  
			if( dtrm <= std::numeric_limits<float>::epsilon() )  
			{    
				c[0] += variance;  
				c[4] += variance;  
				c[8] += variance;  
			}  

			//计算第ci个高斯模型的协方差的逆Inverse和行列式Determinant  
			calcInverseCovAndDeterm(ci);  
		}  
	}  
}  

//计算第ci个高斯模型的协方差逆矩阵,及其行列式 这个是为了后面计算高斯概率方便 
void GMM::calcInverseCovAndDeterm( int ci )  
{  
	if( coefs[ci] > 0 )  
	{  
		//第ci个高斯模型协方差
		float *c = cov + 9*ci;  
		float dtrm =  
			covDeterms[ci] = c[0]*(c[4]*c[8]-c[5]*c[7]) - c[1]*(c[3]*c[8]-c[5]*c[6])   
			+ c[2]*(c[3]*c[7]-c[4]*c[6]); 
		float fa= std::numeric_limits<float>::epsilon();
		ASSERT( dtrm > std::numeric_limits<float>::epsilon() );  
		//矩阵求逆公式 
		inverseCovs[ci][0][0] =  (c[4]*c[8] - c[5]*c[7]) / dtrm;  
		inverseCovs[ci][1][0] = -(c[3]*c[8] - c[5]*c[6]) / dtrm;  
		inverseCovs[ci][2][0] =  (c[3]*c[7] - c[4]*c[6]) / dtrm;  
		inverseCovs[ci][0][1] = -(c[1]*c[8] - c[2]*c[7]) / dtrm;  
		inverseCovs[ci][1][1] =  (c[0]*c[8] - c[2]*c[6]) / dtrm;  
		inverseCovs[ci][2][1] = -(c[0]*c[7] - c[1]*c[6]) / dtrm;  
		inverseCovs[ci][0][2] =  (c[1]*c[5] - c[2]*c[4]) / dtrm;  
		inverseCovs[ci][1][2] = -(c[0]*c[5] - c[2]*c[3]) / dtrm;  
		inverseCovs[ci][2][2] =  (c[0]*c[4] - c[1]*c[3]) / dtrm;  
	}  
}  

3、概率计算。OK,到了这一步,可以说已经完成了算法的上半部分,我们得到的结果是:

a、前景的高斯混合模型(原paper中选择聚类成5个),其包含5个单高斯模型的相关参数,每个单高斯模型包含三个参数:均值、协方差矩阵、此模型所占的比例权重(这个参数是根据k均值聚类后,计算每个类的像素点个数占总数的比例:

coefs[ci] = (float)n/totalSampleCount; 

其它参数,什么协方差矩阵的逆矩阵、行列式值只是为了计算方便而进行存储,根据协方差矩阵就可以把这两个参数计算出来。

b、与前景一样,对背景建模后的5个高斯模型的相关参数。

因为我们的模型前景及背景的高斯混合模型已经建立完毕,现在我假设,如果给定一点像素点的color值,那么我们可以很快的计算出其分别属于前景及背景的概率,计算公式如下

也就是把像素点p(x,y)属于某个高斯成分的概率与该成分的权重的乘积,最后进行累加。

//输入像素点的颜色值 计算其在高斯混合模型中的总概率和
float GMM::operator()( const Eigen::Vector3f color ) const  
{  
	float res = 0;  
	for( int ci = 0; ci < componentsCount; ci++ )  
		res += coefs[ci] * (*this)(ci, color );  //component权重与该像素点属于这个component概率相乘
	return res;  
}
//计算像素点颜色值color ,属于第ci个高斯模型的概率
float GMM::operator()( int ci, const Eigen::Vector3f color ) const  
{  
	float res = 0;  
	if( coefs[ci] > 0 )  
	{  
		ASSERT( covDeterms[ci] > std::numeric_limits<float>::epsilon() );  
		Eigen::Vector3f diff = color;  
		float* m = mean + 3*ci;  
		diff[0] -= m[0]; diff[1] -= m[1]; diff[2] -= m[2];  
		float mult = diff[0]*(diff[0]*inverseCovs[ci][0][0] + diff[1]*inverseCovs[ci][1][0] + diff[2]*inverseCovs[ci][2][0])  
			+ diff[1]*(diff[0]*inverseCovs[ci][0][1] + diff[1]*inverseCovs[ci][1][1] + diff[2]*inverseCovs[ci][2][1])  
			+ diff[2]*(diff[0]*inverseCovs[ci][0][2] + diff[1]*inverseCovs[ci][1][2] + diff[2]*inverseCovs[ci][2][2]);  
		res = 1.0f/sqrt(covDeterms[ci]) * exp(-0.5f*mult);  
	}  
	return res;  
} 

因为后面就是要计算被标记为GC_PR_BGD、 GC_PR_FGD的概率,所以你可以把这些像素点分别属于前景模型及背景模型的概率计算出来,并存储起来,后面将用这玩意进行图的构建。

4、图的构建。这一步要用到图论的一些简单知识,其中最主要的算法当然是max flow /min cut 了。如下图,其中s代表前景,t代表背景,这两个点是为了进行图割,人为的加进去的两个顶点,也就是说假设图片为3*3大小的图片,其共有9个像素点,那么加上s、t两个点,最后我们构建的图就有11个顶点。

这个图有两种边:

第一种边:每两个邻接像素点间会有一条边,而这条边的长度(流、权重)就是这两个像素点的颜色差值。

//图的第一种边长,相邻像素点间的边长计算,这个函数是直接求取像素点的4邻域像素点与该像素点的像素差值模长(opencv采用的是高斯函数)
//gamma可以理解为一个权重系数,或者说是一个归一化系数(当然不是真正的归一哈)
//<span style="font-family: Arial, Helvetica, sans-serif;">,这是因为我们通过高斯混合模型计算的概率值是0~1的值,</span>然而相邻像素点每个通道就有0~255,这样计算出来的边长是0~255*255*255,
//因此我们必须让这个根据像素值构建的边进行合适的缩放,
//不然高斯概率取值范围最大也才为1,也就是第二种边的长度最长也才为1,相对于255*255*255,这个简直没法活了
void GrabCut::calcNWeights(Eigen::MatrixXf& leftW, Eigen::MatrixXf& upleftW, Eigen::MatrixXf& upW,   
                            Eigen::MatrixXf& uprightW, float beta, float gamma )  
{  
    const float gammaDivSqrt2 = gamma / std::sqrt(2.0f);  
    //每个方向的边的权值通过一个和图大小相等的Eigen::MatrixXf来保存 
	int height=m_Image->Height;
	int width=m_Image->Width;
    leftW.resize(height,width);
    upleftW.resize(height,width);;  
    upW.resize(height,width);;  
    uprightW.resize(height,width);;  
    for( int y = 0; y <height; y++ )  
    {  
        for( int x = 0; x < width; x++ )  
        {  
            Eigen::Vector3f color =GetPiexl(CPoint(x,y),m_Image);  
            if( x-1>=0 )
            {  
                Eigen::Vector3f diff = color -GetPiexl(CPoint(x-1,y),m_Image);  
                leftW(y,x) = gamma * exp(-beta*diff.dot(diff)); //高斯函数又来了,计算距离权重的神器 
            }  
            else  
                leftW(y,x) = 0;  
            if( x-1>=0 && y-1>=0 ) 
            {  
                Eigen::Vector3f diff = color -GetPiexl(CPoint(x-1,y-1),m_Image);  
                upleftW(y,x) = gammaDivSqrt2 * exp(-beta*diff.dot(diff));  
            }  
            else  
                upleftW(y,x) = 0;  
            if( y-1>=0 ) // up  
            {  
                Eigen::Vector3f diff = color -GetPiexl(CPoint(x,y-1),m_Image);  
                upW(y,x) = gamma * exp(-beta*diff.dot(diff));  
            }  
            else  
                upW(y,x) = 0;  
            if( x+1<width && y-1>=0 ) // upright  
            {  
                Eigen::Vector3f diff = color - GetPiexl(CPoint(x+1,y-1),m_Image);  
                uprightW(y,x) = gammaDivSqrt2 * exp(-beta*diff.dot(diff));  
            }  
            else  
                uprightW(y,x) = 0;  
        }  
    }  
}  


第二种边:也就是我们第3步计算每个像素点属于前景、背景的概率。s(前景)到每个像素点p的连接边,就是p点属于s的概率。t(背景)到每个像素点p的连接边,也就是p点属于t的概率。这些我们在第3步就已经可以计算好了,也就是前面的所有步骤中,其实都只是为了计算s、t分别到每个像素顶点的连接边的长度而已。



图的具体构建函数为:

//图的构建 输入参数包括:交互输入的mask,前面高斯建模的结果bgdGMM、fgdGMM。
//lambda为调节参数,可以理解为无穷大的数,用于连接被标记为GC_BGD、GC_FGD的长度,因为这两个是已经确定的
//所以我们自然而然要在后面的图割中,把GC_BGD分割给背景t,把GC_FGD分割给前景s,这就是为什么这个数为无穷大的原因了
//leftW、upleftW、upW、uprightW存储了第一类边长
//输出:graph
void GrabCut::constructGCGraph(const Eigen::MatrixXf& mask, const GMM& bgdGMM, const GMM& fgdGMM, float lambda,  
                       const Eigen::MatrixXf& leftW, const Eigen::MatrixXf& upleftW, const Eigen::MatrixXf& upW, const Eigen::MatrixXf& uprightW,  
                       GCGraph<float>& graph )  
{  
    int vtxCount = m_Image->Height*m_Image->Width; //图顶点个数
    int edgeCount = 2*(4*vtxCount - 3*(m_Image->Width + m_Image->Height) + 2); //图边数计算 
    graph.create(vtxCount, edgeCount); //根据顶点个数、边数,先初始化构建一个图,所得简单点就是先分配好内存 
    CPoint  p; 
	int heigth=m_Image->Height;
	int width=m_Image->Width;
    for( p.y = 0; p.y <heigth; p.y++ )  
    {  
        for( p.x = 0; p.x < width; p.x++)  
        {  
            int vtxIdx = graph.addVtx();//这个函数可以返回接着要添加的顶点的索引,有点神奇,是GCGraph类写的挺方便的 
            Eigen::Vector3f color = GetPiexl(p,m_Image);//获取像素点颜色值  
  //第二类边,根据前景及背景的高斯模型计算第二类边长长度
            float fromSource, toSink;  
            if( mask(p.y,p.x) == GC_PR_BGD || mask(p.y,p.x)== GC_PR_FGD )  
            {  
				//这里需要注意的是长度并不是简单的概率,而是对其取对数,然后取负数
                fromSource = -log( bgdGMM(color) );  
                toSink = -log( fgdGMM(color) );  
            }  
            else if( mask(p.y,p.x)== GC_BGD )  
            {  
                //如果已经去确定为背景 那么其连接前景的边长值为0,而连接背景的边长值为无穷大
                fromSource = 0;  
                toSink = lambda;  
            }  
            else // GC_FGD  
            {  
                fromSource = lambda;  
                toSink = 0;  
            }  
            //两条图的连接边把vtxIdx分别与Source、toSink连接起来
            graph.addTermWeights( vtxIdx, fromSource, toSink );  
             
  //第一类边,增加这个像素点与其4个邻接顶点的相连接的4条边
            if( p.x>0 )  
            {  
                float w = leftW(p.y,p.x);  
                graph.addEdges( vtxIdx, vtxIdx-1, w, w );  
            }  
            if( p.x>0 && p.y>0 )  
            {  
                float w = upleftW(p.y,p.x);  
                graph.addEdges( vtxIdx, vtxIdx-width-1, w, w );  
            }  
            if( p.y>0 )  
            {  
                float w = upW(p.y,p.x);  
                graph.addEdges( vtxIdx, vtxIdx-width, w, w );  
            }  
            if( p.x<width-1 && p.y>0 )  
            {  
                float w = uprightW(p.y,p.x);  
                graph.addEdges( vtxIdx, vtxIdx-width+1, w, w );  
            }  
        }  
    }  
}  

5、图割与更新标记阶段。根据上面构建的图,进行最大流/最小割。个人感觉最大流/最小割跟最短路径Dijkstra算法很像,只要很熟悉Dijkstra算法,那么写max flow算法不是什么难事,不过我自己写的代码当然比不上大牛写的代码,高手都是用了各种数据结构写的,速度杠杠的,我这种菜鸟写出来的速度,慢了别人几倍。所以如果想要用,直接用opencv的,才是王道

//max flow进行图割、并更新mask函数
//graph就是我们上一步构建的图
void GrabCut::estimateSegmentation( GCGraph<float>& graph, Eigen::MatrixXf& mask )  
{  
    graph.maxFlow(); //图割 将把图分割成两部分
    CPoint p;  
    for( p.y = 0; p.y <mask.rows(); p.y++ )  
    {  
        for( p.x = 0; p.x < mask.cols(); p.x++ )  
        {  
            //更新不明确点GC_PR_BGD 、GC_PR_FGD 的标号
            if( mask(p.y,p.x)==GC_PR_BGD|| mask(p.y,p.x)== GC_PR_FGD )  
            {  
                if( graph.inSourceSegment( p.y*mask.cols()+p.x ))//这个像素点被分割给了s  
                    mask(p.y,p.x)= GC_PR_FGD;  
                else  //这个像素点被分割给了t
                    mask(p.y,p.x)= GC_PR_BGD;  
            }  
        }  
    }  
} 
图割结果:

图割完以后,我们可以把图片的像素点归为两类,一类被s给割走了,一类被t给割走了,被s给割走,那么它就相当于属于s(前景),被t给割走那么它就相当属于背景了。因此割完以后,我们需要更新那些不确定属于前景还是背景的点的标号。

到了这里可以说算法已经结束了,接着就只是迭代的事了,你可以选择只迭代一次,就万事大吉,图割学习完毕了。贴一下结果:



最后要说的一句是:原版的grab cut 算法分割很粗糙,而且速度很慢,后面许多大牛,对这篇文献做了相关的改进,还有一大堆效果非常好的改进的grab cut 算法等着我们去学习。

*************作者:hjimce     联系qq:1393852684   更多资源请关注我的博客:http://blog.csdn.net/hjimce                  原创文章,转载请保留本行信息*********

参考文献:

1、“GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts

2、http://blog.csdn.net/zouxy09/article/details/8532111

3、Opencv

2014-07-06 12:15:44 xinzhangyanxiang 阅读数 15287

图像物体检测识别中的LBP特征

1        引言

之前讲了人脸识别中的Haar特征,本文则关注人脸检测中的LBP特征,说是对于人脸检测的,其实对于其他物体也能检测,只需修改训练数据集即可。所以本文的题目是物体检测识别,比如可以检测是否汽车是否有车牌号等。

在opencv实现的haar特征的人脸识别算法中,LBP特征也被支持。

haar特征的博文链接:http://blog.csdn.net/stdcoutzyx/article/details/34842233

2        LBP的历史

1996年,Ojala老大爷搞出了LBP特征,也即参考文献1。当时好像并未引发什么波澜。到了2002年的时候,老大爷又对LBP的特性进行了总结,产生了参考文献2,这篇文献目前为止引用数目4600+,足见其分量之重了。

到了2004年的时候,Ahonen将LBP特征首次用于人脸检测,即参考文献3。由于该特征的简单易算性,虽然其总体效果不如Haar特征,但速度则快于Haar,所以也得到了广泛的使用。

2007年的时候,中科院的一帮大神将Haar特征计算的积分图方法引入进来,产生了多尺度的LBP特征,也即参考文献4。使得LBP在人脸识别的检测率上又提高了不少。

LBP特征与多尺度LBP以及LBP在人脸识别中的应用就是本文的主要内容。

3        LBP特征

言归正传,什么是LBP特征呢?LBP,是Local Binary Pattern(局部二值模式)的缩写。其定义如下:

以邻域中心像素为阈值,将相邻的8个像素的灰度值与其进行比较,若周围像素值大于中心像素值,则该像素点的位置被标记为1,否则为0。这样,3x3邻域内的8个点经比较可产生8位二进制数(通常转换为十进制数即LBP码,共256种),即得到该邻域中心像素点的LBP值,并用这个值来反映该区域的纹理信息。

下图反应了某个像素的具体的LBP特征值的计算过程,需要注意的是,LBP值是按照顺时针方向组成的二进制数。


用公式来定义的话,如下所示:


其中代表3x3邻域的中心元素,它的像素值为ic,ip代表邻域内其他像素的值。s(x)是符号函数,定义如下:


4        LBP特征的圆形化改进

原始论文[1]中定义了基础LBP后,还定义了一种改进方法,即圆形化LBP。

基本的 LBP算子的最大缺陷在于它只覆盖了一个固定半径范围内的小区域,这显然不能满足不同尺寸和频率纹理的需要。为了适应不同尺度的纹理特征,并达到灰度和旋转不变性的要求,Ojala等对 LBP 算子进行了改进,将 3×3邻域扩展到任意邻域,并用圆形邻域代替了正方形邻域,改进后的 LBP 算子允许在半径为 R 的圆形邻域内有任意多个像素点。从而得到了诸如半径为R的圆形区域内含有P个采样点的LBP算子。

比如下图定了一个5x5的邻域:


上图内有八个黑色的采样点,每个采样点的值可以通过下式计算:


其中为邻域中心点,为某个采样点。通过上式可以计算任意个采样点的坐标,但是计算得到的坐标未必完全是整数,所以可以通过双线性插值来得到该采样点的像素值:


下图列举了几种不同半径不同采样点的LBP算子样例。


5        LBP特征的再转化

经过LBP算子的计算后,图像上对应于每个像素都会有一个LBP特征值,如果LBP特征计算时采样点是8个的话,那么LBP特征值的范围也是0~255。也可以表示成一张图像。称之为LBP图谱。如下图所示:


上图中,上面一行是原图,下面一行是LBP图谱。可以看到LBP特征的一个优势,就是LBP对光照有很好的鲁棒性。

但是,在实际应用中,并不使用LBP图谱做特征。那使用什么哩?

对于八采样点的LBP算子来说,特征值范围为0~255,对每个特征值进行统计,比如得到特征值为1的LBP值有多少个、特征值为245的LBP值有多少个等等。这样就形成了一个直方图,该直方图有256个bin,即256个分量,也可以把该直方图当做一个长度为256的向量。

如果直接使用该向量的话,那么对八采样点的LBP算子来说,一张图片至多会形成一个256长度的一个向量,这样位置信息就全部丢失了,会造成很大的精度问题。所以在实际中还会再有一个技巧,就是先把图像分成若干个区域,对每个区域进行统计得到直方图向量,再将这些向量整合起来形成一个大的向量。下图就将一张人脸图像分成了7x7的子区域。


6        LBP特征的使用

本文介绍两个LBP特征的使用。其一是图像相似度计算,其二是人脸检测。

6.1   图像相似度计算

每个图像都可以使用一个LBP特征向量来表示,图像的相似度就可以使用向量的相似度来计算。

向量的相似度计算方法有很多,比如余弦、距离等。在文献3中,这种基于直方图向量的相似度计算方法给出了三种,如下图所示。


上图中公式只是针对一个直方图的,使用中还会将图像分为多个区域分别计算直方图。所以在实际使用中,还可对不同区域进行加权。


6.2   特定人脸检测

在上述计算图像相似度的公式中,需要对每个分量计算一个值(差值、最小值等),然后将这些值累加。我们还可以这样考虑,不将每个分量计算出的值累加,而是形成一个新的向量,暂时称之为差异向量。这样就可以针对特定人脸进行检测了。

具体训练方法是这样:

a)        首先准备训练集,正例是同一个人的人脸的两张图像的差异向量,负例是不同人的人脸的两张图像的差异向量。

b)       然后,使用如Adaboost、SVM、朴素贝叶斯等分类方法对训练集进行训练,得到分类模型。

在测试时,假设有一张图像A,现在需要判断图像B与图像A中的人脸是否是同一个人,那么首先计算出两张图像的差异向量,然后使用训练得到的分类模型对其进行分类,如果分类为正,则是同一个人。当然,前提假设是图像A与图像B都是人脸图像。

7        LBP特征降维

一个LBP算子可以产生不同的二进制模式,对于半径为R的圆形区域内含有P个采样点的LBP算子将会产生2^P种模式。很显然,随着邻域集内采样点数的增加,二进制模式的种类是急剧增加的。例如:5×5邻域内20个采样点,有2^20=1,048,576种二进制模式。如此多的二值模式无论对于纹理的提取还是对于纹理的识别、分类及信息的存取都是不利的。同时,过多的模式种类对于纹理的表达是不利的。例如,将LBP算子用于纹理分类或人脸识别时,常采用LBP模式的统计直方图来表达图像的信息,而较多的模式种类将使得数据量过大,且直方图过于稀疏。因此,需要对原始的LBP模式进行降维,使得数据量减少的情况下能最好的代表图像的信息。

为了解决二进制模式过多的问题,提高统计性,Ojala提出了采用一种“等价模式”(Uniform Pattern)来对LBP算子的模式种类进行降维。Ojala等认为,在实际图像中,绝大多数LBP模式最多只包含两次从1到0或从0到1的跳变。因此,Ojala将“等价模式”定义为:当某个LBP所对应的循环二进制数从0到1或从1到0最多有两次跳变时,该LBP所对应的二进制就称为一个等价模式类。如00000000(0次跳变),00000111(只含一次从0到1的跳变),10001111(先由1跳到0,再由0跳到1,共两次跳变)都是等价模式类。除等价模式类以外的模式都归为另一类,称为混合模式类,例如10010111(共四次跳变)。比如下图给出了几种等价模式的示意图。


通过这样的改进,二进制模式的种类大大减少,而不会丢失任何信息。模式数量由原来的2P种减少为 P ( P-1)+2种,其中P表示邻域集内的采样点数。对于3×3邻域内8个采样点来说,二进制模式由原始的256种减少为58种,这使得特征向量的维数更少,并且可以减少高频噪声带来的影响。

由上可见,等价模式降维的理论基础是至多包含两次跳变的模式的数目占全部模式的大多数。实验也表明,一般情况下,基础LBP特征中,至多包含两次跳变的模式的数目占了全部模式数目的90%。

8        多尺度LBP

本节主要是参考文献4的成果。

基本LBP是计算的单个像素与其相邻像素的差值信息。它捕捉的是微观特征。但是不能捕捉宏观上的特征。文献4在此方面进行了改进。它提出可以将LBP算子等比例放大,计算区域与区域之间的差值信息。如下图所示:


上图就是放大3倍后的LBP算子,这时,中心元素变为了0区域9个像素的像素和,该区域的LBP特征值就变为0区域和其他区域的像素和之间的计算了。在此需要注意的是,此时的LBP特征针对的是一个区域而不是一个像素了。在计算像素和之差的时候,可以使用Haar特征时提到的积分图方法进行加速计算。

多尺度模式下,等价模式类降维的理论基础不复存在。那么,它是如何降维的呢?

论文中提到的方法是直接采用统计的方法对不同尺度的LBP算子的模式进行统计,选取占比例较高的模式。而不是利用跳变规则。

9        总结

LBP特征与Haar特征虽然计算方法差异很大,但它们都有一个共同的目标,那就是对图像的信息进行表示,从而使图像的所存储的信息能更充分的被算法所利用。图像中像素与LBP特征、Haar特征之间的关系比较类似于文本分析中字与词之间的关系。文本分析中,如果想要获得语义理解的话,那应该需要处理句子、短语、词语等,单单分析字是远远不够的。图像处理中,要想得到丰富的图像包含的信息,单单分析像素也是不够的。

本文与Haar特征的那篇博文都使用到了Adaboost分类器,但其使用的目的却完全不一样,Haar特征中使用Adaboost是对有脸和无脸的图像进行分类,而本文是对是不是同一个人的脸进行分类。从这就可以感觉的到,很多机器学习问题其实本质上都可以化为分类问题,当然,另一大类是回归问题。

个人觉得本篇博文对LBP的讨论已经够全面了。有想深入学习的同学请阅读参考文献,欢迎来信讨论。

转载请注明:http://blog.csdn.net/stdcoutzyx/article/details/37317863

参考文献

[1]. Ojala, T., Pietik¨ainen, M., Harwood, D.: A comparative study of texture measures with classification based on feature distributions. Pattern Recognition 29 (1996)51–59.
[2]. Ojala T, Pietikainen M, Maenpaa T. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2002, 24(7): 971-987. 
[3]. Ahonen T, Hadid A, Pietikäinen M. Face recognition with local binary patterns[M]//Computer vision-eccv 2004. Springer Berlin Heidelberg, 2004: 469-481. 
[4]. Liao S, Zhu X, Lei Z, et al. Learning multi-scale block local binary patterns for face recognition[M]//Advances in Biometrics. Springer Berlin Heidelberg, 2007: 828-837. 

[5]. http://blog.csdn.net/smartempire/article/details/23249517

[6]. http://blog.csdn.net/zouxy09/article/details/7929531

关于建模

阅读数 73

没有更多推荐了,返回首页