求最小外接矩形的原理
最近在做课程设计的过程中遇到了一个问题,需要求出一幅图像中物体的矩形度,但是求解矩形度需要用到该物体的最小外接矩形的面积。所以我查了各种资料想要写一个求解物体最小外接矩形的代码。
首先我们来看一下求解的原理。一个物体的与x轴和y轴平行的外接矩形就是这个物体的简单外接矩形,显然,物体的简单外接矩形是比较容易计算面积的。那么我们只需要将物体旋转一定的角度,再求出旋转后的简单外接矩形,最后得到最小的简单外接矩形的面积就行了,而旋转的角度在正负90°之间,以1°为1个间隔。
因为我们只要求解面积而不需要将这个矩形画出来,所以可以采用C++中的set容器来实现,set容器具有自动排序的功能。
大致实现算法如下:
C++实现代码
// 求解最小外接矩形面积
long lengthAndWidth(LPSTR lpSrcStartBits, long lSrcWidth, long lSrcHeight, int label)
{
unsigned char* lpSrc;
int* pixel = new int[2];
pixel[0] = pixel[1] = 0;
long lLineBytes = WIDTHBYTES(lSrcWidth * 8);
// 旋转角度(弧度)
float fRotateAngle;
// 旋转角度的正弦和余弦
float fSina, fCosa;
int rotate = 0;
long x0, y0;
std::set<int> setx,sety;
long min = 10000000;
long square = 0;
for (rotate = -90;rotate <= 90;rotate++)
{
// 将旋转角度从度转换到弧度
fRotateAngle = (float)((rotate)*PI / 180.0);
// 计算旋转角度的正弦
fSina = (float)sin((double)fRotateAngle);
// 计算旋转角度的余弦
fCosa = (float)cos((double)fRotateAngle);
for (long i = 0;i < lSrcHeight;i++)//旋转
{
for (long j = 0;j < lSrcWidth;j++)
{
lpSrc = (unsigned char*)lpSrcStartBits + lLineBytes * (lSrcHeight - 1 - i) + j;
if (*lpSrc == label)
{
x0 = j * fCosa - i * fSina + 0.5;
y0 = j * fSina + i * fCosa + 0.5;
setx.insert(x0);
sety.insert(y0);
}
}
}
square = abs((*setx.rbegin() - *setx.begin() + 1) * (*sety.rbegin() - *sety.begin() + 1));
if(min > square)
{
min = square;
pixel[0] = *setx.rbegin() - *setx.begin() + 1;
pixel[1] = *sety.rbegin() - *sety.begin() + 1;
}
setx.clear();sety.clear();
}
return (pixel[0]*pixel[1]);
}
当然这份代码只对8位图像有效,我们也可以参照算法把它改成适用于24位图像的代码。
参考文章:
https://zhuanlan.zhihu.com/p/97855964.