算法的基本特征：

有限性：一个算法在执行有限步之后必须会终止。

确定性：一个算法的每个步骤都必须精确地定义，可以严格地、无歧义地执行。
输入：一个算法在运行之前赋给它的量，或在运行过程中动态地赋给它的量。
输出：一个算法运行结束时的结果。
有效性：一个算法在运行过程中，所有运算必须是充分基本的，是可行的，原则上人们可以用笔和纸在有限的时间内精确地完成这些运算。

一、 有穷性：一个算法必须在执行有限个操作步骤后终止。
二、 确定性：算法中每一步的含义必须是确切的，不可出现任何二义性。
三、 有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的，例如，一个数被0除的操作就是无效的，应当避免这种操作。
四、 有零个或多个输入： 这里的输入是指在算法开始之前所需要的初始数据。这些输入的多少取决于特定的问题。
五、 有一个或多个输出： 所谓输出是指与输入有某种特定关系的量，在一个完美的算法中至少有一个输出。

算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。
 　　1）算法的基本特征
 　　（1）可行性:由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的。
 　　（2）确定性:算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。
 　　（3）有穷性:算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。
 　　（4）拥有足够的情报:算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。
 　　2）算法的基本要素
 　　一是数据对象的运算和操作，二是算法的控制结构。
 　　（1）算法中对数据的运算和操作
 　　算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。
 　　（2）算法的控制结构
 　　在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序结构、选择结构和循环结构。
 　　3）算法设计的基本方法
 　　（1）列举法:基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。
 　　（2）归纳法:基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
 　　（3）递推:是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。本质也是一种归纳，递推关系式通常是归纳的结果。
 　　（4）递归:在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。分为直接递归和间接递归两种方法。
 　　（5）减半递推技术:减半递推即将问题的规模减半，然后，重复相同的递推操作。
 　　（6）回溯法:有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。
转载于:https://www.cnblogs.com/dinhh001/p/4438764.html

Reference:图像处理基本算法之形状特征

下文是在原文基础上进行修改的，具体可以查看原文。

（一）形状特征

  （一）特点：各种基于形状特征的检索方法都可以比较有效地利用图像中感兴趣的目标来进行检索，但它们也有一些共同的问题，包括：①目前基于形状的检索方法还缺乏比较完善的数学模型；②如果目标有变形时检索结果往往不太可靠；③许多形状特征仅描述了目标局部的性质，要全面描述目标常对计算时间和存储量有较高的要求；④许多形状特征所反映的目标形状信息与人的直观感觉不完全一致，或者说，特征空间的相似性与人视觉系统感受到的相似性有差别。另外，从 2-D 图像中表现的 3-D 物体实际上只是物体在空间某一平面的投影，从 2-D 图像中反映出来的形状常不是 3-D 物体真实的形状，由于视点的变化，可能会产生各种失真。

 

（二）常用的特征提取与匹配方法

 

Ⅰ几种典型的形状特征描述方法

 

通常情况下，形状特征有两类表示方法，一类是轮廓特征，另一类是区域特征。图像的轮廓特征主要针对物体的外边界，而图像的区域特征则关系到整个形状区域。

 

几种典型的形状特征描述方法：

（1）边界特征法该方法通过对边界特征的描述来获取图像的形状参数。其中Hough 变换检测平行直线方法和边界方向直方图方法是经典方法。Hough 变换是利用图像全局特性而将边缘像素连接起来组成区域封闭边界的一种方法，其基本思想是点—线的对偶性；边界方向直方图法首先微分图像求得图像边缘，然后，做出关于边缘大小和方向的直方图，通常的方法是构造图像灰度梯度方向矩阵。

（2）傅里叶形状描述符法

 

傅里叶形状描述符(Fourier shape descriptors)基本思想是用物体边界的傅里叶变换作为形状描述，利用区域边界的封闭性和周期性，将二维问题转化为一维问题。

 

由边界点导出三种形状表达，分别是曲率函数、质心距离、复坐标函数。

 

（3）几何参数法

 

形状的表达和匹配采用更为简单的区域特征描述方法，例如采用有关形状定量测度（如矩、面积、周长等）的形状参数法（shape factor）。在 QBIC 系统中，便是利用圆度、偏心率、主轴方向和代数不变矩等几何参数，进行基于形状特征的图像检索。

 

需要说明的是，形状参数的提取，必须以图像处理及图像分割为前提，参数的准确性必然受到分割效果的影响，对分割效果很差的图像，形状参数甚至无法提取。

 

（4）形状不变矩法

 

利用目标所占区域的矩作为形状描述参数。

 

（5）其它方法

 

近年来，在形状的表示和匹配方面的工作还包括有限元法（Finite Element Method 或 FEM）、旋转函数（Turning Function）和小波描述符（Wavelet Descriptor）等方法。

 

实际上，只是提取物体的形状，这并不难，最难的是这些特征该怎么用！

特征嘛，自然是讲此物区分彼物的特点。

那么假如，给出了一系列不同形状物体的轮廓该如何识别出他们呢？正方形，圆形，矩形，椭圆，不规则图形，再进一步，这些图形由于受到信号的干扰，有噪声存在时，该如何去识别他们呢？

那就可以使用形状的特征了，我们定义一些参数，来描述这些形状。

1 矩形度：R = A0/A; A0为区域面积，A为区域最小外接矩形面积。

那么R = 1 时，为矩形的概率很大，R = PI/4时为圆的可能性最大

2 体态比 T = a/b;

a b 分别为区域最小外接矩形的长和宽。

T = 1 为正方形或者圆形，

T>1 为细长图形

3 球状性 S = Ri/Rc

Ri Rc分别为内切圆和外接圆半径，圆心都在中心上

4 球状性 C = Ur/Pr

Ur 为区域重心到轮廓点的平均距离

Pr 为区域重心到轮廓点的均方差

5 中心矩

这一特征，使用颇为频繁，OpenCV有专门的函数求解（p，q）次矩

6 长轴 短轴

最小外接矩形的长轴和短轴

7面积

一般会作为阈值使用，判定某个区域的面积在两个阈值之间才判定有效

 

 下面给出各个形状特征的求法：

//图像的形状特征分析
#include <cv.h>
#include <cxcore.h>
#include <highgui.h>
#include <iostream>
using namespace std;

int main()
{
	IplImage *src = cvLoadImage("E:\\image\\mapleleaf.tif",0);
	IplImage *image = cvCreateImage(cvGetSize(src),8,3); 
	image = cvCloneImage(src);
	cvNamedWindow("src",1);
	cvNamedWindow("dst",1);
	cvShowImage("src",src);

	CvMemStorage *storage = cvCreateMemStorage(0);
	CvSeq * seq = cvCreateSeq(CV_SEQ_ELTYPE_POINT, sizeof(CvSeq), sizeof(CvPoint), storage);
	CvSeq * tempSeq = cvCreateSeq(CV_SEQ_ELTYPE_POINT, sizeof(CvSeq), sizeof(CvPoint), storage);
	//新图，将轮廓绘制到dst
	IplImage *dst = cvCreateImage(cvGetSize(src),8,3); 
	cvZero(dst);//赋值为0
	double length,area;

	//获取轮廓
	int cnt = cvFindContours(src,storage,&seq);//返回轮廓的数目
	cout<<"number of contours   "<<cnt<<endl;
	
	//计算边界序列的参数 长度 面积 矩形 最小矩形 
	//并输出每个边界的参数
	CvRect rect;
	CvBox2D box;
	double axislong,axisShort;//长轴和短轴
	double temp1= 0.0,temp2 = 0.0;
	double Rectangle_degree;//矩形度
	double long2short;//体态比
	double x0,y0;
	long sumX  = 0 ,sumY = 0;
	double sum =0.0;
	int i,j,m,n;
	unsigned char* ptr;

	double UR;//区域重心到轮廓的平均距离
	double PR;//区域重心到轮廓点的均方差
	CvPoint * contourPoint; 
	int count = 0;
	double CDegree;//圆形性

	CvPoint *A,*B,*C;
	double AB,BC,AC;
	double cosA,sinA;
	double tempR,inscribedR;
	
	for (tempSeq = seq;tempSeq != NULL; tempSeq = tempSeq->h_next)
	{
		//tempSeq = seq->h_next;
		length = cvArcLength(tempSeq);
		area = cvContourArea(tempSeq);
		cout<<"Length = "<<length<<endl;
		cout<<"Area = "<<area<<endl;
		cout<<"num of point "<<tempSeq->total<<endl;
		//外接矩形
		rect = cvBoundingRect(tempSeq,1);
		

		//绘制轮廓和外接矩形
		cvDrawContours(dst,tempSeq,CV_RGB(255,0,0),CV_RGB(255,0,0),0);
		cvRectangleR(dst,rect,CV_RGB(0,255,0));
		cvShowImage("dst",dst);
		//cvWaitKey();

		//绘制轮廓的最小外接圆 
		CvPoint2D32f center;//亚像素精度 因此需要使用浮点数
		float radius;
		cvMinEnclosingCircle(tempSeq,¢er,&radius);
		cvCircle(dst,cvPointFrom32f(center),cvRound(radius),CV_RGB(100,100,100));
		cvShowImage("dst",dst);
		//cvWaitKey();

		//寻找近似的拟合椭圆 可以使斜椭圆
		CvBox2D ellipse = cvFitEllipse2(tempSeq);
		cvEllipseBox(dst,ellipse,CV_RGB(255,255,0));
		cvShowImage("dst",dst);
		//cvWaitKey();


		//绘制外接最小矩形
		CvPoint2D32f pt[4];
		box = cvMinAreaRect2(tempSeq,0);
		cvBoxPoints(box,pt);
		for(int i = 0;i<4;++i){
			cvLine(dst,cvPointFrom32f(pt[i]),cvPointFrom32f(pt[((i+1)%4)?(i+1):0]),CV_RGB(0,0,255));
		}
		cvShowImage("dst",dst);
		//cvWaitKey();


		//下面开始分析图形的形状特征 
		//长轴 短轴
		temp1 = sqrt(pow(pt[1].x -pt[0].x,2) + pow(pt[1].y -pt[0].y,2));
		temp2 = sqrt(pow(pt[2].x -pt[1].x,2) + pow(pt[2].y -pt[1].y,2));

		if (temp1 > temp2)
		{
			axislong = temp1;
			axisShort=temp2;
		} 
		else
		{
			axislong = temp2;
			axisShort=temp1;
		}
		
		cout<<"long axis： "<<axislong<<endl;
		cout<<"short axis: "<<axisShort<<endl;
		//矩形度 轮廓面积和最小外接矩形面积（可以是斜矩形）之比
		Rectangle_degree = (double)area/(axisShort*axislong);

		cout<<"Rectangle degree :"<<Rectangle_degree<<endl;
		//体态比or长宽比 最下外接矩形的长轴和短轴的比值
		long2short = axislong/axisShort;
		cout<<"ratio of long axis to short axis: "<<long2short<<endl;
		//球状性 由于轮廓的内切圆暂时无法求出先搁置 
		//先求内切圆半径 枚举任意轮廓上的三个点，半径最小的就是内切圆的半径
		//以下的最大内切圆半径求法有误 待改进
		
		/*
		for (int i = 0 ; i< tempSeq->total -2;i++)
		{
			for (int j= i+1; j<tempSeq->total-1;j++)
			{
				for (int m = j+1; m< tempSeq->total; m++)
				{
					//已知圆上三点，求半径
					A = (CvPoint*)cvGetSeqElem(tempSeq ,i);
					B = (CvPoint*)cvGetSeqElem(tempSeq ,j);
					C = (CvPoint*)cvGetSeqElem(tempSeq,m);
					AB = sqrt(pow((double)A->x - B->x,2)+ pow((double)A->y - B->y,2));
					AC =sqrt(pow((double)A->x - C->x,2) + pow((double)A->y - C->y,2));
					BC = sqrt(pow((double)B->x - C->x,2)+ pow((double)B->y - C->y,2));

					cosA = ((B->x - A->x)*(C->x - A->x) + (B->y - A->y)*(C->y - A->y))/(AB*AC);
					sinA = sqrt(1 - pow(cosA,2));
					tempR = BC/(2*sinA);

					if (m == 2)
					{
						inscribedR = tempR;
					} 
					else
					{
						if (tempR < inscribedR)
						{
							inscribedR = tempR;
						}
					}


				}
			}
		}

		//输出最大内切圆半径
		cout<<"radius of max inscribed circle  "<<inscribedR<<endl;
		*/
		//圆形性 假设轮廓内是实心的
		//球区域中心x0 y0
		sumX = 0;
		sumY = 0;
		src = cvCloneImage(image);
		for (int i = 0 ; i< src->height;i++)
		{
			for (int j = 0; j< src->width;j++)
			{
				ptr = (unsigned char *)src->imageData + i*src->widthStep + j;
				if ((*ptr) > 128)
				{
					sumX += (long)j;
					sumY += (long)i;
				}

			}
		}
		x0 = sumX/area;
		y0 = sumY/area;
		cout<<"center of gravity "<<x0<<"   "<<y0<<endl;
     //求区域到重心的平均距离
		sum = 0;
		count = 0;
		for (m = 0 ; m< tempSeq->total;m++)
		{
			contourPoint = (CvPoint*)cvGetSeqElem(tempSeq,m);
			sum += sqrt(pow(contourPoint->x - x0,2)+ pow(contourPoint->y - y0,2));
			count++;
		}
		UR = sum/count;
		cout<<"mean distance to center of gravity"<<UR<<endl;
		//求区域重心到轮廓点的均方差
		sum = 0;
		for (m = 0 ; m< tempSeq->total;m++)
		{
			contourPoint = (CvPoint*)cvGetSeqElem(tempSeq,m);
			temp1 = sqrt(pow(contourPoint->x - x0,2)+ pow(contourPoint->y - y0,2));
			sum += pow(temp1 - UR,2);
		}
		PR = sum/count;
		cout<<"mean square error of distance to center of gravity"<<PR<<endl;
		//圆形性 
		CDegree= UR/PR;
        cout<<"degree of circle "<<CDegree<<endl;
		//中心距
		
		cvWaitKey(0);
	}
	
	
	cvReleaseImage(&src);
	cvReleaseImage(&dst);
	cvReleaseMemStorage(&storage);	
	
	return 0;
}