找到簇质量以矩阵/位图 [英] Finding clusters of mass in a matrix/bitmap
问题描述
这是在延续与张贴在这里的问题是： <一href="http://stackoverflow.com/questions/408358/finding-the-center-of-mass-on-a-2d-bitmap">http://stackoverflow.com/questions/408358/finding-the-center-of-mass-on-a-2d-bitmap里面讲到发现质量中心在布尔矩阵，作为例子给出。
This is in continuation with the question posted here: http://stackoverflow.com/questions/408358/finding-the-center-of-mass-on-a-2d-bitmap which talked about finding the center of mass in a boolean matrix, as the example was given.
现在假设我们扩大矩阵这种形式：
Suppose now we expand the matrix to this form:
0 1 2 3 4 5 6 7 8 9
1 . X X . . . . . .
2 . X X X . . X . .
3 . . . . . X X X .
4 . . . . . . X . .
5 . X X . . . . . .
6 . X . . . . . . .
7 . X . . . . . . .
8 . . . . X X . . .
9 . . . . X X . . .
正如你所看到的，我们现在有质量的4个中心，为4个不同的集群。
As you can see we now have 4 centers of mass, for 4 different clusters.
我们已经知道如何找到给定质量的中心只有一个存在，如果我们运行这个矩阵算法，我们会得到一些点在矩阵中间不帮助我们。
We already know how to find a center of mass given that only one exists, if we run that algorithm on this matrix we'll get some point in the middle of the matrix which does not help us.
什么是一个很好的，正确的和快速的算法来查找这些集群质量？
What can be a good, correct and fast algorithm to find these clusters of mass?
推荐答案
我想我会检查矩阵中的每个点，并计算出它的质量基础上的邻居。大众的点会落在同说，距离的平方。然后，您可以挑选前四点彼此的最小距离。
I think I would check each point in the matrix and figure out it's mass based on it's neighbours. The mass for points would fall with say the square of the distance. You could then pick the top four points with a minimum distance from each other.
下面是一些Python code我鞭打在一起，试图说明以找出质量的每个点的方法。使用例如矩阵的一些设置：
Here's some Python code I whipped together to try to illustrate the approach for finding out the mass for each point. Some setup using your example matrix:
matrix = [[1.0 if x == "X" else 0.0 for x in y] for y in """.XX......
.XXX..X..
.....XXX.
......X..
.XX......
.X.......
.X.......
....XX...
....XX...""".split("\n")]
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
Y_RADIUS = HEIGHT / 2
X_RADIUS = WIDTH / 2
要计算质量对于给定的点：
To calculate the mass for a given point:
def distance(x1, y1, x2, y2):
'Manhattan distance http://en.wikipedia.org/wiki/Manhattan_distance'
return abs(y1 - y2) + abs(x1 - x2)
def mass(m, x, y):
_mass = m[y][x]
for _y in range(max(0, y - Y_RADIUS), min(HEIGHT, y + Y_RADIUS)):
for _x in range(max(0, x - X_RADIUS), min(WIDTH, x + X_RADIUS)):
d = max(1, distance(x, y, _x, _y))
_mass += m[_y][_x] / (d * d)
return _mass
注：我使用的是曼哈顿距离（又名Cityblock，又名曼哈顿距离），在这里，因为我不认为使用欧几里得距离增加的准确性值得调用的sqrt（）的成本。
Note: I'm using Manhattan distances (a k a Cityblock, a k a Taxicab Geometry) here because I don't think the added accuracy using Euclidian distances is worth the cost of calling sqrt().
迭代通过我们的矩阵和建立像元组的列表（X，Y，质量（X，Y））：
Iterating through our matrix and building up a list of tuples like (x, y, mass(x,y)):
point_mass = []
for y in range(0, HEIGHT):
for x in range(0, WIDTH):
point_mass.append((x, y, mass(matrix, x, y)))
排序名单上的群众每个点：
Sorting the list on the mass for each point:
from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)
看着在排序列表中的前9分：
Looking at the top 9 points in that sorted list:
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 1, 4.6736111111111107)
(1, 4, 4.5938888888888885)
(2, 0, 4.54)
(4, 7, 4.4480555555555554)
(1, 5, 4.4480555555555554)
(5, 7, 4.4059637188208614)
(4, 8, 4.3659637188208613)
如果我们将努力从最高到最低，并过滤掉那些过于接近已经看到了点，我们会得到（我做手工，因为我已经跑出来的时候，现在做这件事$ C $点C ...）：
If we would work from highest to lowest and filter away points that are too close to already seen points we'll get (I'm doing it manually since I've run out of time now to do it in code...):
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)
这是一个pretty的直观结果从刚才看你的矩阵（注意，坐标是基于零的时候用你的例子进行比较）。
Which is a pretty intuitive result from just looking at your matrix (note that the coordinates are zero based when comparing with your example).
这篇关于找到簇质量以矩阵/位图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
