1. 首頁
  2. 問答
  3. 查找矩陣/位圖中的質量簇

查找矩陣/位圖中的質量簇

2009-01-04 67 views
5

這是繼續發佈的問題： Finding the center of mass on a 2D bitmap其中討論瞭如何在布爾矩陣中找到質心，如給出的示例。查找矩陣/位圖中的質量簇

假設現在我們的矩陣擴展到這種形式：

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個不同的集羣。

我們已經知道如何找到一個質量中心，因爲只有一個存在，如果我們在這個矩陣上運行該算法，我們會在矩陣的中間得到一些點，這對我們沒有幫助。

什麼可以是一個很好，正確和快速的算法來找到這些質量羣？

來源

2009-01-04 Yuval Adam

回答

3

我想我會檢查矩陣中的每個點，並根據它的鄰居找出它的質量。點的質量會隨着距離的平方而下降。然後你可以選擇距離彼此最小的前四個點。

下面是一些Python代碼，我一起試着說明找出每個點的質量的方法。

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

要計算質量對於給定的點：

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

注：我使用Manhattan距離（又名Cityblock，又名出租車幾何）在這裏，因爲我不使用你的榜樣矩陣一些設置認爲使用歐幾里德距離的附加精度值得調用sqrt（）的代價。

迭代通過我們的矩陣和建立一個元組列表像（X，Y，質量（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)))

排序的質量對每個點的地址列表：

from operator import itemgetter 
point_mass.sort(key=itemgetter(2), reverse=True)

望着在排序列表頂部9點：

(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)

如果我們將努力從最高到最低，並過濾接[R遠點過於接近已經看到了，我們會得到點（我做手工，因爲我已經用完了時間，現在做在代碼中...）：

(6, 2, 6.1580555555555554) 
(2, 1, 5.4861111111111107) 
(1, 4, 4.5938888888888885) 
(4, 7, 4.4480555555555554)

哪個一個非常直觀的結果，只需查看矩陣（請注意，與您的示例進行比較時，座標爲零）。

來源

2009-01-04 22:57:53 PEZ

1

我首先想到的是首先找到任何非零值的單元格。從那裏做一些洪水填充算法，並計算找到的細胞的質心。接下來從矩陣中找出找到的單元格，並從頂部開始。

這當然不會像Google的方法那樣擴展，即tuinstoel鏈接，但對於較小的矩陣更容易實現。

編輯：

Disjoint sets（使用路徑壓縮和工會通過秩）也許會有幫助。它們具有ø（α（Ñ））時爲聯合複雜性和查找集，其中

α（Ñ）= MIN {ķ：甲ķ（1）≥ n}。

甲ķ（Ñ）是阿克曼功能，所以α（Ñ）將基本上是ø（1）對於任何合理的值。唯一的問題是不相交集合是項目到集合的單向映射，但是如果你要通過所有項目，這並不重要。

這裏是一個演示簡單的Python腳本：

from collections import defaultdict 

class DisjointSets(object): 
    def __init__(self): 
     self.item_map = defaultdict(DisjointNode) 

    def add(self,item): 
     """Add item to the forest.""" 
     # It's gets initialized to a new node when 
     # trying to access a non-existant item. 
     return self.item_map[item] 

    def __contains__(self,item): 
     return (item in self.item_map) 

    def __getitem__(self,item): 
     if item not in self: 
      raise KeyError 
     return self.item_map[item] 

    def __delitem__(self,item): 
     del self.item_map[item] 

    def __iter__(self): 
     # sort all items into real sets 
     all_sets = defaultdict(set) 
     for item,node in self.item_map.iteritems(): 
      all_sets[node.find_set()].add(item) 
     return all_sets.itervalues() 

class DisjointNode(object): 
    def __init__(self,parent=None,rank=0): 
     if parent is None: 
      self.parent = self 
     else: 
      self.parent = parent 
     self.rank = rank 

    def union(self,other): 
     """Join two sets.""" 
     node1 = self.find_set() 
     node2 = other.find_set() 
     # union by rank 
     if node1.rank > node2.rank: 
      node2.parent = node1 
     else: 
      node1.parent = node2 
      if node1.rank == node2.rank: 
       node2.rank += 1 
     return node1 

    def find_set(self): 
     """Finds the root node of this set.""" 
     node = self 
     while node is not node.parent: 
      node = node.parent 
     # path compression 
     root, node = node, self 
     while node is not node.parent: 
      node, node.parent = node.parent, root 
     return root 

def find_clusters(grid): 
    disj = DisjointSets() 
    for y,row in enumerate(grid): 
     for x,cell in enumerate(row): 
      if cell: 
       node = disj.add((x,y)) 
       for dx,dy in ((-1,0),(-1,-1),(0,-1),(1,-1)): 
        if (x+dx,y+dy) in disj: 
         node.union(disj[x+dx,y+dy]) 
    for index,set_ in enumerate(disj): 
     sum_x, sum_y, count = 0, 0, 0 
     for x,y in set_: 
      sum_x += x 
      sum_y += y 
      count += 1 
     yield 1.0 * sum_x/count, 1.0 * sum_y/count 

def main(): 
    grid = [[('.' != cell) for cell in row if not cell.isspace()] for row in (
     ". X X . . . . . .", 
     ". X X X . . X . .", 
     ". . . . . X X X .", 
     ". . . . . . X . .", 
     ". X X . . . . . .", 
     ". X . . . . . . .", 
     ". X . . . . . . .", 
     ". . . . X X . . .", 
     ". . . . X X . . .", 
    )] 
    coordinates = list(find_clusters(grid)) 
    centers = dict(((round(x),round(y)),i) for i,(x,y) in enumerate(coordinates)) 
    for y,row in enumerate(grid): 
     for x,cell in enumerate(row): 
      if (x,y) in centers: 
       print centers[x,y]+1, 
      elif cell: 
       print 'X', 
      else: 
       print '.', 
     print 
    print 
    print '%4s | %7s %7s' % ('i','x','y') 
    print '-'*22 
    for i,(x,y) in enumerate(coordinates): 
     print '%4d | %7.4f %7.4f' % (i+1,x,y) 

if __name__ == '__main__': 
    main()

輸出：

. X X . . . . . . 
. X 3 X . . X . . 
. . . . . X 4 X . 
. . . . . . X . . 
. X X . . . . . . 
. 2 . . . . . . . 
. X . . . . . . . 
. . . . X X . . . 
. . . . X 1 . . . 

    i |  x  y 
---------------------- 
    1 | 4.5000 7.5000 
    2 | 1.2500 4.7500 
    3 | 1.8000 0.6000 
    4 | 6.0000 2.0000

的這點是要證明不相交的集合。 find_clusters()中的實際算法可以升級爲更強大的功能。

參考

  • 算法導論。 2nd ed。 Cormen et.al.

來源

2009-01-04 22:59:27

1

Here's一個類似的問題，一個不那麼快的算法，以及其他幾個更好的方法來做到這一點。

來源

2009-01-05 11:40:05

相關問題

 相關問題