Python中文
首页
教程
问答
标签
搜索
登录
注册
连接元件计数
回答此问题可获得
20
贡献值,回答如果被采纳可获得
50
分。
<p>在<a href="http://en.wikipedia.org/wiki/Connected-component_labeling#Algorithms" rel="nofollow">standard algorithm for connected component counting</a>中,使用了称为<a href="http://en.wikipedia.org/wiki/Union_find" rel="nofollow">union-find</a>的不相交集数据结构。在</p> <p>为什么要使用这种数据结构?我编写了一些代码来线性搜索图像,维护两个线性缓冲区来存储每个连接像素的当前和下一个组件计数,方法是检查四个邻居(E、SE、S、SW),并且在连接的情况下,更新连接映射以将较高的组件与较低的组件连接起来。 完成后,搜索所有未连接的零部件并报告计数。在</p> <p>我只是不明白为什么这种方法比使用union find效率低。在</p> <p>这是我的密码。输入文件已缩减为<code>0</code>s和<code>1</code>s。程序输出由<code>0</code>s组成的连接组件的数量</p> <pre><code>def CompCount(fname): fin = open(fname) b,l = fin.readline().split() b,l = int(b),int(l)+1 inbuf = '1'*l + fin.read() prev = curr = [sys.maxint]*l nextComp = 0 tree = dict() for i in xrange(1, b+1): curr = [sys.maxint]*l for j in xrange(0, l-1): curr[j] = sys.maxint if inbuf[i*l+j] == '0': p = [prev[j+n] for m,n in [(-l+1,1),(-l,0),(-l-1,-1)] if inbuf[i*l + j+m] == '0'] curr[j] = min([curr[j]] + p + [curr[j-1]]) if curr[j] == sys.maxint: nextComp += 1 curr[j] = nextComp tree[curr[j]] = 0 else: if curr[j] < prev[j+1]: tree[prev[j+1]] = curr[j] if curr[j] < prev[j]: tree[prev[j]] = curr[j] if curr[j] < prev[j-1]: tree[prev[j-1]] = curr[j] if curr[j] < curr[j-1]: tree[curr[j-1]] = curr[j] prev = curr return len([x for x in tree if tree[x]==0]) </code></pre>
0 条评论
分类:
Python问答
请先
登录
后评论
默认排序
时间排序
1 个回答
匿名
1天前
擅长:python、mysql、java
<p>我没有完全理解你的问题,把它写清楚并组织好你的问题,对你自己真的有好处。在</p> <p>我的理解是,你想在0-1图像中使用8邻域来标记连接的组件。如果是这样的话,你假设得到的邻域图是平面的,这是错误的。你在“对角线”有十字路口。在这样的图像中构造K{3,3}或K{5}应该很容易。在</p>
请先
登录
后评论
针对此问题:
更多的回答
关注
89
关注
收藏
1
收藏,
216
浏览
网友 提问于 2天前
相关Python问题
如何在python3x中以垂直和水平的方式格式化列表?
1 回答
如何在python3x中创建datetime对象
5 回答
如何在python3x中取消pickle一个在python2.7中被pickle的模型?
8 回答
如何在python3x中格式化字典键
2 回答
如何在python3x中正确地通过sockets发送字典的内容?
5 回答
如何在python3x中调用if语句中的类和函数
1 回答
如何在Python3上三取二列表
10 回答
如何在python3上为方法搜索RegEx创建模式?
1 回答
如何在Python3上使用HTMLUnit和Selenium 2.45.0
10 回答
如何在Python3上使用telebot发送没有bot.polling()的消息
3 回答
如何在python3上使用Tkinter更新GUI?
5 回答
如何在python3上使用urllib和代理对HTTPS页面发出请求
1 回答
如何在Python3上制作按键
8 回答
如何在python3上发布图像和文本多部分表单?
6 回答
如何在Python3上安装Bob?
2 回答
如何在python3上安装Django?
3 回答
如何在python3上安装第三方模块
6 回答
如何在Python3上安装袖扣?
4 回答
如何在python3上打印当前日期?
8 回答
如何在Python3上执行此javascript代码?
1 回答