可用分押宝游戏火热进行中...	专题改版：Java Web 专题

求想法、思路!找一图形的最窄处！大家多提意见。来者有分.

楼主aming112（测试并开发着）2004-09-02 11:52:52 在 VC/MFC / 图形处理/算法提问

我现在手上有一图形，形状和狗骨头差不多，我要找出它的最窄处。应该怎么做？多提意见？
样图地址：http://www.kigroups.com/sample.jpg 问题点数：100、回复次数：28Top

1 楼xiaoxiaodada（玲）回复于 2004-09-02 12:14:27 得分 0

我也不大懂，发表一下自己的看法而已！！勿笑。
1、对图象进行处理，将你要的图象部分完全提出来，比如让其他部分为白色。
2、提取图形边界。
3、逐行进行扫描，计算两侧边界的距离，找出最短处！Top

2 楼aming112（测试并开发着）回复于 2004-09-02 12:20:03 得分 0

to xiaoxiaodada(玲) 首先很感谢你的回复，你说的前面两点我都做到了，就是最后的如何测算距离的问题，我还没谱，不知道该具体怎么做。望大家不吝赐教。Top

3 楼alec626（月吻长河Blog:spaces.msn.com/filebase）回复于 2004-09-02 12:28:32 得分 5

有点难
不知道有没有现成的算法
找本《图形学》看看Top

4 楼LongLongAgoImBoy（ThereIsAMe）回复于 2004-09-02 12:34:52 得分 5

算法，不懂，凑凑热闹。呵呵
Top

5 楼mdzhao（读破书万卷）回复于 2004-09-02 13:16:55 得分 10

刚学完图形学说的不对大家别笑话

把图形的每个像素顺序存到一个数组或链表里,个人觉得还是链表好,因为可以把边界也定下来,如:struct map{long x,y;//行列值
bool is_full;//是黑色是白色
bool is_edge;
bool is_vary//是不是颜色改变处
struct map *prevenientPtr;
struct map *nextPtr;}//单色图案
每行分别从左到右从右到左，扫描

把颜色值改变的点记录下来，写到链表里is_vary,
如果是封闭图形的话，每一行就只会出现2个有标记的点，或0个
之后再分别计算每行is_vary == true的两点见的像素数

计算量大了点，哈哈，见笑了，如果图形太大，可能算得很慢Top

6 楼aming112（测试并开发着）回复于 2004-09-02 14:06:24 得分 0

mdzhao(狼) 你这样做，只是把要的图形的边界找出来了，但是对于寻找最窄处没有什么特别的帮助。关于图象的边界我用行扫描的办法已经求出来了（速度还不错），现在就是求两侧边的距离的问题不知道怎么做。
大家帮忙UP！Top

7 楼Arlene_cn（绿茶）回复于 2004-09-02 14:47:03 得分 5

我晕，图形边界都找出来了，还不知道算距离？用同一行（列）的两个边界点的X（Y）坐标相减不就得到了吗。我还以为是有角度的，原来就是垂直或水平两个方向。Top

8 楼aming112（测试并开发着）回复于 2004-09-02 14:48:51 得分 0

不是，上面这位兄弟误会了。
样图是我手画的，实际上的图很复杂，什么角度都有，而且很不规则的。一幅图中也不是只有一个物体，而是很多个。Top

9 楼mdzhao（读破书万卷）回复于 2004-09-02 15:17:23 得分 5

噢,那就复杂了,看你要求的是具体的那一个图形的最窄处了.
看看,计算机图形学方面的书吧,

帮你UP吧

不过有个问题:"关于图象的边界我用行扫描的办法已经求出来了（速度还不错）"
你只扫描行,而不扫描列吗?? 如果图形是垂直方向有最窄处该怎么办??Top

10 楼aming112（测试并开发着）回复于 2004-09-02 15:30:54 得分 0

所以我用行扫描只是找出了边界。
而且即使用列扫描，有的物体是有角度的，可能也不行，就是在这里等大家提建议啊！Top

11 楼aming112（测试并开发着）回复于 2004-09-02 15:38:56 得分 0

我需要求出图中的每一个物体的最窄处！Top

12 楼Thomasdu（海浪）回复于 2004-09-02 16:08:13 得分 20

先找出各个物体区域。
一个方法是：在各个区域上用腐蚀的方法，看哪里先断成两个，则这个地方最窄。（当然最好事先知道最窄处的宽度）
另一个方法：二值化后计算出图像区域的市街区距离(就是非零点到零点的最小距离)，然后沿着最大值搜索出骨架，最后找出最小值就是图像的最窄处。这个方法比较容易一些。
Top

13 楼aming112（测试并开发着）回复于 2004-09-02 16:22:28 得分 0

Thomasdu(海浪)
你说的第一种方法我考虑过，但是我怎么知道它断成了2个呢？
第二种方法可不可以麻烦你说的具体一点。
Top

14 楼autoegg（哲学指引生活 && (动心忍性，增益其所不能)）回复于 2004-09-02 18:29:09 得分 10

是否可以考虑腐蚀算法？最先腐蚀掉的区域应该是较窄的区域。Top

15 楼redmoons（臭臭）回复于 2004-09-02 19:12:00 得分 5

是不是可以使用网格，思路还不是很成熟，不过在国外的站上有相关的方法!
搜搜MESHTop

16 楼jijinxu（）回复于 2004-09-03 00:07:54 得分 0

图形的最窄处，指的是什么意思？不理解。。。Top

17 楼jijinxu（）回复于 2004-09-03 00:11:32 得分 10

不明白楼主所指最窄是何意。例如，一个图形为一个圆形，假设半径为a,那它的最窄处是多窄？圆上的各点，可以认为地位是相同的，所以它的最窄处应该就是一个点和它相邻点的距离吧？那不就是无限接近于0？
同样，对于任意封闭图形，所谓最窄到底是什么意思？Top

18 楼BadEnglish（BadEnglish）回复于 2004-09-03 01:04:58 得分 5

首先从超低分辨图象入手，找到可能是目标的区域，然后无论是那种算法，计算量应该比较小，
然后逐步提高实际分辨率，把刚才找到的点精细定位,排除粗定位可能给出的错解。
比如说，1000*1000的图象先缩小到125*125分析......Top

19 楼Thomasdu（海浪）回复于 2004-09-03 09:06:06 得分 0

先找出各个物体区域。---这个你是怎么找的？：）
二值化后计算出图像区域的市街区距离(就是非零点到零点的最小距离)，
这个说起来比较麻烦openCV里有现成的算法。

然后沿着最大值搜索出骨架，最后找出最小值就是图像的最窄处。
找到一个局部最大值后就可以沿着这个局部最大值搜索下去了。
Top

20 楼wangweixing2000（星(inspiration（灵感）)）回复于 2004-09-03 09:23:58 得分 10

前期处理我就不说了！轮廓提取出来以后！然后2值化，把边界拟合成某个样条曲线或者多种曲线的组合，剩下的就可以算了因为已经是个几何矢量了！做好能把两头大的给剔除掉，然后你再拟合曲线！Top

21 楼Phourm（）回复于 2004-09-03 09:33:29 得分 0

1 二值化(只有黑白)图象
2 找到所有边界点(去除噪音)
3 比较所有边界点两两距离,找到最小值,那么这两点的连线就是你要的Top

22 楼Phourm（）回复于 2004-09-03 09:39:27 得分 0

第三不对!
可能考虑用圆来通过图像就小圆就是最窄的宽度,Top

23 楼netxy（netxy）回复于 2004-09-03 09:59:57 得分 0

autoegg的看法值得考虑，楼上所说的其实也就是腐蚀算法。
用可变大小的圆来腐蚀原图，找到可以将原图分为二或二以上部份的最小圆，则其直径就是原图的最窄部份。Top

24 楼wrcluomo（落木）回复于 2004-09-03 11:32:24 得分 10

用链码法找出边界,所给只作参考,只参考思想就可以了:
//(14)返回最小直径和最大直径444444444444444444444444444444444444444444444444444444444444
int * CTwoColorTrace::GetDiameter()
{
//如果中心点和起点在一条直线上的情况（竖直）
/* if (m_MidPoint.x-m_ipX[0]==0)
{
m_adDiameter[0]=1;
m_adDiameter[1]=m_ipY[m_lSegmentCount-1]-m_ipY[0];
AfxMessageBox("1");
return m_adDiameter;

}
//如果中心点和起点在一条直线上的情况（水平）
if (m_MidPoint.y-m_ipY[0]==0)
{
m_adDiameter[0]=1;
m_adDiameter[1]=2*(m_MidPoint.x-m_ipX[0]);
AfxMessageBox("2");
return m_adDiameter;
}*/

long lMaxDiameter,lMinDiameter,lTemLen;
int i,j,n;
int iTemX=m_ipTraceX[0];
float iTemY;
//直线平行X轴,寻找具有相同Y坐标且X坐标大于中心点X坐标的点
if(m_MidPoint.y-m_ipTraceY[0]==0)

{for(i=1;i<m_lLianMaCount;i++)

if(m_ipTraceY[0]==m_ipTraceY[i]&&m_ipTraceX[i]>m_MidPoint.x)
break;
}
//直线平行Y,寻找具有相同X坐标且Y坐标大于中心点Y坐标的点
else if(m_MidPoint.x-m_ipTraceX[0]==0)
{
for(i=1;i<m_lLianMaCount;i++)
if(m_ipTraceY[0]>m_MidPoint.y)
{
if(m_ipTraceX[0]==m_ipTraceX[i]&&m_ipTraceY[i]<m_MidPoint.y)
break;
}
else
{
if(m_ipTraceX[0]==m_ipTraceX[i]&&m_ipTraceY[i]>m_MidPoint.y)
break;

}
}
//其它情况，符合两点直线公式的情况
else
{
for(i=1;i<m_lLianMaCount;i++)
{
if((m_ipTraceX[i]-m_ipTraceX[0])==0)continue;
iTemY=(float)(m_MidPoint.x-m_ipTraceX[0])*(m_ipTraceY[i]-m_ipTraceY[0])/
(m_ipTraceX[i]-m_ipTraceX[0])+m_ipTraceY[0];
if(iTemY>=m_MidPoint.y-0.9&&iTemY<m_MidPoint.y+0.9&&m_ipTraceX[i]>m_MidPoint.x)
{
//AfxMessageBox("ok1");
break;
}

}

}
//如果没有找到就取链码的1/2之处
if(i==m_lLianMaCount)
i=m_lLianMaCount/2;

n=1;
lMaxDiameter=lMinDiameter=(m_ipTraceX[i]-m_ipTraceX[0])*(m_ipTraceX[i]-m_ipTraceX[0])+(m_ipTraceY[i]-m_ipTraceY[0])*(m_ipTraceY[i]-m_ipTraceY[0]);
m_adDiameter[6]=m_adDiameter[2]=m_ipTraceX[0];
m_adDiameter[7]=m_adDiameter[3]=m_ipTraceY[0];
m_adDiameter[8]=m_adDiameter[4]=m_ipTraceX[i];
m_adDiameter[9]=m_adDiameter[5]=m_ipTraceY[i];
for(j=i+1;j<m_lLianMaCount-1;j++,n++)
{
lTemLen=(m_ipTraceX[j]-m_ipTraceX[n])*(m_ipTraceX[j]-m_ipTraceX[n])+(m_ipTraceY[j]-m_ipTraceY[n])*(m_ipTraceY[j]-m_ipTraceY[n]);
if(lMaxDiameter<lTemLen)
{
lMaxDiameter=lTemLen;
m_adDiameter[6]=m_ipTraceX[n];
m_adDiameter[7]=m_ipTraceY[n];
m_adDiameter[8]=m_ipTraceX[j];
m_adDiameter[9]=m_ipTraceY[j];
}
if(lMinDiameter>lTemLen)
{
lMinDiameter=lTemLen;
m_adDiameter[2]=m_ipTraceX[n];
m_adDiameter[3]=m_ipTraceY[n];
m_adDiameter[4]=m_ipTraceX[j];
m_adDiameter[5]=m_ipTraceY[j];
}
}

m_adDiameter[0]=(int)(sqrt(lMinDiameter)+0.5);
m_adDiameter[1]=(int)(sqrt(lMaxDiameter)+0.5);

return m_adDiameter;

}
//（14）44444444444444444444444444444444444444444444444444444444444444444444444444444444
Top

25 楼wqs6（竹山）回复于 2004-09-03 13:19:05 得分 0

Thomasdu(海浪)
你说的第一种方法我考虑过，但是我怎么知道它断成了2个呢？
第二种方法可不可以麻烦你说的具体一点。

可以看看边界跟踪，由此得到不同的物体边界Top

26 楼aming112（测试并开发着）回复于 2004-09-03 18:38:47 得分 0

谢谢大家的意见~！周末好好看一下，下周一来揭贴！！Top

27 楼eastsun（）回复于 2004-09-04 13:05:42 得分 0

有这样的狗骨头吗？

令人气愤。

Top

28 楼aming112（测试并开发着）回复于 2004-09-05 16:46:12 得分 0

你这人说话就不对了，实际当中当然不是这样的，但是我以这个做为例子有何不可？你气愤什么，不懂就不要乱开黄腔!!Top