2D列表中的聚类上的边界框 [英] Bounding box on clusters in a 2D list

问题描述

如果我有


ex：x = [[1,1,1,0,0,0,0,0,0,0,0,1,1， 1,1,0,0,0]，

[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1， 0,0,0]，

[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0， 0]，

[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]]

我想要的是一个边界框，我们在这个区域找到了

1'的集群。所以例如在上面的列表中，前3个roes和colums有1'' s

所以那个盒子的面积是3x3

所以我的最后一个阵列应该有一个大约的区域阵列

1''像

area = [9,4 ....]

希望我对我的问题很清楚。

解决方案

我希望这就是你所需要的，有时候理解这个问题是

其中一个最难的部分:-)


如果你可以使用图形数据结构，你可以创建一个图形，然后

你可以找到所有连接组件的长度（缩进

减少到2个空间s）：


.. def mat2graph（g，m，good =无，w = 1）：

.."功能文档...

.. g.clear（）

..如果m和isinstance（m，（list，tuple））：

。如果好的话！=无：

.. m = [行中e的好（e）]行中的m]

.. maxy = len（m ）-1

.. maxx = len（m [0]） - 1

.. add = g.addBiArc

.. for y，枚举（m）行：

..对于x，e在枚举（行）中：

..如果e：

.. g.addNode（（x，y））＃对于孤立节点是必需的。

..如果x> 0且m [y] [x-1]：add（（x，y） ，（x-1，y），w = w）

..如果x< maxx和m [y] [x + 1]：add（（x，y），（x + 1） ，y），w = w）

..如果y> 0且m [y-1] [x]：add（（x，y），（x，y-1），w = w）

..如果y< maxy和m [y + 1] [x]：add（（x，y），（x，y + 1），w = w）

..

..来自图形导入图

.. g =图形（）

.. m = [ [1,1,1,0,0,0 ，0,0,0,0,0,1,1,1,1,0,0,0]，

.. [1,1,1,0,1,1,0 ，0,0,0,0,1,1,1,1,0,0,0]，

.. [1,1,1,0,1,1,1,0 ，1,1,0,1,1,1,0,0,0,0]，

.. [0,0,0,0,0,0,0,0,1 ，1,0,0,0,0,0,0,0,0]]

.. mat2graph（g，m）

..打印地图（len ，g.connectedComponents（））

类似于mat2graph的东西可能会成为Graph的一种方法。

一个非常类似的程序可以用于其他python图形图书馆。


如果你不能使用图形数据结构，如果你需要更快，

你可以使用针对这个问题调整的泛洪填充算法：

.. def connected（m，foreground = 1，background = 0）：

.. def floodFill4（m，r，c，newCol，oldCol）：

.."""最简单的4连接泛洪填充算法，有很多

..更快的非递归填充算法。我修改了这个：

.. http://www.student.kuleuven.ac.be/~m0216922/CG/floodfill.html"""

..如果c> = 0且c< maxc和r> = 0且r< maxr和m [r] [c] == oldCol：

.. m [r] [ c] = newCol

.. floodFill4（m，r + 1，c，newCol，oldCol）

.. floodFill4（m，r-1，c，newCol， oldCol）

.. floodFill4（m，r，c + 1，newCol，oldCol）

.. floodFill4（m，r，c-1，newCol，oldCol）

..

.. maxr = len（m）

.. maxc = len（m [0]）

.. newCol = 2

.. oldCol =前景

..对于x inrange（maxr）：

.. for c in xrange（maxc）：

..如果m [r] [c] == oldCol：

.. floodFill4（m，r，c，newCol = newCol ，oldCol = oldCol）

.. newCol + = 1

..＃Frequences，这可以成为标准的python命令

.. freq = {}

..对于m中的行：

..对于e排：

..如果e in freq：

.. freq [e] + = 1

.. else：

.. freq [e] = 1

.. del freq [背景]

..返回freq.values（）

..

.. m = [[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1， 0,0,0]，

.. [1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0， 0,0]，

.. [1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0， 0]，

.. [0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0] ]

..打印连接（m）

有更快的方法来进行洪水填充：
http://www.codeproject.com/gdi/QuickFill.asp

我认为Python PIL并不支持洪水填充，我认为使用Numarray这样做是很慢的，并且它只对减少使用的

内存非常有用。 />
这个连接的程序很慢且很原始，并且它使用递归很多，

所以它可能会崩溃译码。您可以使用数据结构来自行实现堆栈，以加快此程序的运行速度。但是对于小的

矩阵我觉得这个连接就足够了^ _ ^


熊抱抱，

Bearophile

2005年4月23日13:17:55 -0700，su ******* @ gmail.com <苏******* @ gmail.com>写道：

如果我有

ex：x = [[1,1,1,0,0,0,0,0,0,0 ，0,1,1,1,1,0,0,0]，
[1,1,1,0,1,1,0,0,0,0,0,1,1,1 ，1,0,0,0]，
[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0 ]，
[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]]
我是什么想要的是一个边界框，我们在这个区域找到了1个的簇。所以例如在上面的列表中，前3个roes和colums有1个'
所以那个盒子的面积是3x3
所以我的最后一个数组应该有一个大约区域的数组
1'就像
area = [9,4 ....]
4来自？

希望我对我的问题很清楚。

不清楚是否群集必须是矩形并填充他们的边界框

或是否


[[0,0,0,0,0]，

+ ----- +

[0，| 1,1，| 0,0]，

| |

[0，| 0,1，| 0,0]，

+ ----- +

[0,0 ，0,0,0]]


是一个有三个1'的集群。或者实际上是否是边界框。必须是矩形的。

即，对角线簇怎么样？

，__，

[[0,0，| 1，| 0 ，0]，

_ / _ /，__，

[0，/ 1，/ 0,0，| 1]，

_ / _ / _ / /

[1，/ 0,0，/ 1，/ 0]，

_ / /

[ 0,0，/ 1，/ 0,0]]


或者应该是

+ ------------ - +

[[| 0,0,1,0,0 |]，

| |

[| 0,1,0,0,1 |]，

| |

[| 1,0,0,1,0 |]，

| |

[| 0,0,1,0,0 |]]

+ ------------- +


因为长度为3对角线的两个3x3正方形会重叠。


问候，

Bengt Richter

里希特，是的，我正在寻找的是具有矩形

边界框的集群，如第一个图所示。

If I have

ex: x = [[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]]
what I want is a boundingbox over the region where we find clusters of
1''s.So for instance in the above list first 3 roes and colums have 1''s
so the area of that box is 3x3
so my final array should have an array of approx areas of clusters of
1''s like
area = [ 9,4 ....]
Hope I am clear with my question.

解决方案

I hope this is what you need, sometimes understanding the question is
one of the hardest parts :-)

If you can use a graph data structure, you can create a graph, and then
you can find the lenght of all its connected components (indentations
reduced to 2 spaces):

.. def mat2graph(g, m, good=None, w=1):
.. "Function docs..."
.. g.clear()
.. if m and isinstance(m, (list, tuple)):
.. if good != None:
.. m = [[good(e) for e in row] for row in m]
.. maxy = len(m)-1
.. maxx = len(m[0])-1
.. add = g.addBiArc
.. for y, row in enumerate(m):
.. for x, e in enumerate(row):
.. if e:
.. g.addNode((x,y)) # Necessary for isolated nodes.
.. if x>0 and m[y][x-1]: add( (x,y), (x-1,y), w=w)
.. if x<maxx and m[y][x+1]: add( (x,y), (x+1,y), w=w)
.. if y>0 and m[y-1][x]: add( (x,y), (x,y-1), w=w)
.. if y<maxy and m[y+1][x]: add( (x,y), (x,y+1), w=w)
..
.. from graph import Graph
.. g = Graph()
.. m = [[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
.. [1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
.. [1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0],
.. [0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]]
.. mat2graph(g, m)
.. print map(len, g.connectedComponents())

Something similar to mat2graph will probably become a method of Graph.
A quite similar program can be used for other python graph libraries.

If you cannot use a graph data structure, of if you need to go faster,
you can use a flood fill algorithm tuned for this problem:
.. def connected(m, foreground=1, background=0):
.. def floodFill4(m, r,c, newCol, oldCol):
.. """Simplest 4-connected flood fill algorithm, there are much
.. faster non-recursive ones. I''ve modified this from:
.. http://www.student.kuleuven.ac.be/~m0216922/CG/floodfill.html"""
.. if c>=0 and c<maxc and r>=0 and r<maxr and m[r][c]==oldCol:
.. m[r][c] = newCol
.. floodFill4(m, r+1, c, newCol, oldCol)
.. floodFill4(m, r-1, c, newCol, oldCol)
.. floodFill4(m, r, c+1, newCol, oldCol)
.. floodFill4(m, r, c-1, newCol, oldCol)
..
.. maxr = len(m)
.. maxc = len(m[0])
.. newCol = 2
.. oldCol = foreground
.. for r in xrange(maxr):
.. for c in xrange(maxc):
.. if m[r][c] == oldCol:
.. floodFill4(m, r,c, newCol=newCol, oldCol=oldCol)
.. newCol += 1
.. # Frequences, this can be become a standard python command
.. freq = {}
.. for row in m:
.. for e in row:
.. if e in freq:
.. freq[e] += 1
.. else:
.. freq[e] = 1
.. del freq[background]
.. return freq.values()
..
.. m = [[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
.. [1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
.. [1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0],
.. [0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]]
.. print connected(m)
There are much faster ways to do flood fills:
http://www.codeproject.com/gdi/QuickFill.asp
I think Python PIL doesn''t support flood fills, and I think doing it
with Numarray is slower, and it''s useful only to reduce the used
memory.
This connected program is slow and raw, and it uses recursivity a lot,
so it can crash the interpreter. You can use a data structure to
implement the stack yourself, to speed this program up. But for small
matrices I think this connected is enough ^_^

Bear hugs,
Bearophile

On 23 Apr 2005 13:17:55 -0700, "su*******@gmail.com" <su*******@gmail.com> wrote:

If I have

ex: x = [[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]]
what I want is a boundingbox over the region where we find clusters of
1''s.So for instance in the above list first 3 roes and colums have 1''s
so the area of that box is 3x3
so my final array should have an array of approx areas of clusters of
1''s like
area = [ 9,4 ....] Where does the 4 come from?
Hope I am clear with my question.

Not quite clear on if "clusters" have to be rectangular and fill their bounding boxes
or whether

[[0, 0, 0, 0, 0],
+-----+
[0,|1, 1,|0, 0],
| |
[0,|0, 1,|0, 0],
+-----+
[0, 0, 0, 0, 0]]

is a cluster with three 1''s. Or indeed whether "bounding boxes" have to be rectangular.
I.e., what about diagonal clusters?
,__,
[[0, 0,|1,|0, 0],
_/ _/ ,__,
[0,/1,/0, 0,|1],
_/ _/ _/ /
[1,/0, 0,/1,/0],
_/ /
[0, 0,/1,/0, 0]]

Or should that be
+-------------+
[[|0, 0, 1, 0, 0|],
| |
[|0, 1, 0, 0, 1|],
| |
[|1, 0, 0, 1, 0|],
| |
[|0, 0, 1, 0, 0|]]
+-------------+

since two 3x3 squares around the length-3 diagonals would overlap.

Regards,
Bengt Richter

Richter,yes what I am looking for is for cluster with rectangular
bounding boxes as you explained in the first figure.

这篇关于2D列表中的聚类上的边界框的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！