मैट्रिक्स/बिटमैप में द्रव्यमान के क्लस्टर ढूंढना

Question

यह यहां पोस्ट किए गए प्रश्न के साथ जारी है: 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 केन्द्रों, किया है।

हम पहले से ही जानते हैं कि द्रव्यमान का केंद्र कैसे ढूंढें, केवल एक मौजूद है, अगर हम इस मैट्रिक्स पर उस एल्गोरिदम को चलाते हैं तो हमें मैट्रिक्स के बीच में कुछ बिंदु मिलेगा जो हमारी मदद नहीं करता है।

द्रव्यमान के इन समूहों को खोजने के लिए एक अच्छा, सही और तेज़ एल्गोरिदम क्या हो सकता है?

Answer 1

मुझे लगता है कि मैं मैट्रिक्स में प्रत्येक बिंदु की जांच करता हूं और इसके पड़ोसियों के आधार पर इसका द्रव्यमान समझता हूं। अंक के लिए द्रव्यमान दूरी के वर्ग के साथ गिर जाएगा। फिर आप शीर्ष चार बिंदुओं को एक दूसरे से न्यूनतम दूरी के साथ चुन सकते हैं।

यहां कुछ पायथन कोड है जो मैंने प्रत्येक बिंदु के लिए द्रव्यमान को खोजने के दृष्टिकोण को चित्रित करने के लिए एक साथ चाबुक किया है। कुछ सेटअप अपने उदाहरण मैट्रिक्स का उपयोग करते हुए:

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, उर्फ ​​Taxicab रेखागणित) का उपयोग कर रहा हूँ यहाँ क्योंकि मैं डॉन यूक्लिडियन दूरी का उपयोग करके जोड़ा गया सटीकता एसकर्ट() को कॉल करने की लागत के लायक नहीं है।

हमारे मैट्रिक्स के माध्यम से बार-बार दोहराना और जैसे tuples की एक सूची का निर्माण (एक्स, वाई, बड़े पैमाने पर (एक्स, वाई)):

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) 

हम उच्चतम से न्यूनतम और filte करने के लिए काम करेंगे, तो आर दूर अंक है कि बहुत पहले से ही अंक हम मिल जाएगा देखा के करीब हैं (के बाद से मैं समय समाप्त हो चुकी है अब कोड में यह करने के लिए मैं इसे स्वयं कर रहा हूँ ...):

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

है कौन सा अपने मैट्रिक्स को देखने से एक सुंदर सहज परिणाम (ध्यान दें कि आपके उदाहरण की तुलना करते समय निर्देशांक शून्य आधारित होते हैं)।

Answer 2

मेरा पहला विचार पहले किसी भी सेल को गैर-शून्य मान के साथ ढूंढना होगा। वहां से कुछ बाढ़ भरने वाले एल्गोरिदम हैं, और पाए गए कोशिकाओं के द्रव्यमान के केंद्र की गणना करें। मैट्रिक्स से पाए गए कोशिकाओं को आगे शून्य करें, और शीर्ष से शुरू करें।

यह निश्चित रूप से स्केल के साथ-साथ Google की विधि भी नहीं होगा, जो कि tuinstoel से जुड़ा हुआ है, लेकिन छोटे मैट्रिस के लिए कार्यान्वित करना आसान होगा।

संपादित करें:

Disjoint sets (पथ संपीड़न और संघ-दर-पद का प्रयोग करके) उपयोगी यहाँ हो सकता है। एक _{कश्मीर: वे हे (α (n)) संघ के लिए समय जटिलता और पाते हैं-सेट, जहां}

α (n) = मिनट {कश्मीर है (1) ≥ एन}।

एक _{कश्मीर} (n) एकरमैन समारोह है, इसलिए α (n) अनिवार्य रूप से किया जाएगा हे (1) किसी भी उचित मूल्यों के लिए। एकमात्र समस्या यह है कि डिजॉइंट सेट सेट करने के लिए आइटम का एक-तरफा मानचित्रण है, लेकिन इससे कोई फर्क नहीं पड़ता कि आप सभी वस्तुओं को कम कर रहे हैं।

यहाँ प्रदर्शन के लिए एक सरल अजगर स्क्रिप्ट है:

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() में वास्तविक एल्गोरिदम को और अधिक मजबूत में अपग्रेड किया जा सकता है।

एल्गोरिदम के लिए संदर्भ

• परिचय। दूसरा संस्करण। कॉर्मन et.al.

Answer 3

Here's एक तेज़ एल्गोरिदम के साथ एक समान प्रश्न, और ऐसा करने के कई अन्य बेहतर तरीके।

Answer 4

आपको क्लस्टरिंग एल्गोरिदम की आवश्यकता है, यह आसान है क्योंकि आपके पास केवल 2 आयामी ग्रिड है, और प्रविष्टियां एक-दूसरे के किनारे हैं। आप बस floodfill algorithm का उपयोग कर सकते हैं। एक बार आपके पास प्रत्येक क्लस्टर होने के बाद, आप केंद्र को 2D center of mass article. में ढूंढ सकते हैं।