Python 2D 클러스터 찾기

나는 0과 1로 구성된 배열을 가졌습니다. 1은 이미지에 보여지는 연속 클러스터를 형성합니다.Python 2D 클러스터 찾기

Clustering

는 클러스터의 수는 사전에 공지되지 않는다.

모든 클러스터의 위치 또는 모든 구성원의 위치를 포함하는 각 클러스터의 목록으로 목록을 만드는 방법이 있습니까? 예 :

cluster_list = continuous_cluster_finder(data_array) 
cluster_list[0] = [(pixel1_x, pixel1_y), (pixel2_x, pixel2_y),...]

출처

2012-12-12 Magnus

를 해결 아래? 그들 각각의 클러스터가 0으로 둘러싸여 있다고 말하는 것이 안전합니까? 위, 아래, 왼쪽, 오른쪽 의미는 0입니까? – vkontori

'data_array'의 형식은 무엇입니까? 목록 목록? 열거 한 배열? 파이썬의 배열 중 하나? –

설명에서 문제의 정확한 제약 조건은 무엇인지 명확하지 않습니다. 당신이에 제로하여 클러스터를 구별 할 수있다 가정하면 왼쪽, 오른쪽, 위, 그 다음이 문제 ... 정확히 클러스터를 분리 무엇

#!/usr/bin/env python 

data = [ #top-left 
     [0,0,1,1,0,0], 
     [0,0,1,1,0,0], 
     [1,1,0,0,1,1], 
     [1,1,0,0,1,1], 
     [0,0,1,1,0,0], 
     [0,0,1,1,0,0], 
     [1,1,0,0,1,1], 
     [1,1,0,0,1,1], 
     ]    # bottom-right 

d = {} # point --> clid 
dcl = {} # clid --> [point1,point2,...] 

def process_point(t): 
    global clid # cluster id 
    val = data[t[0]][t[1]] 
    above = (t[0]-1, t[1]) 
    abovevalid = 0 <= above[0] < maxX and 0 <= above[1] < maxY 
    #below = (t[0]+1, t[1]) # We do not need that because we scan from top-left to bottom-right 
    left = (t[0], t[1]-1) 
    leftvalid = 0 <= left[0] < maxX and 0 <= left[1] < maxY 
    #right = (t[0], t[1]+1) # We do not need that because we scan from top-left to bottom-right 

    if not val: # for zero return 
     return 
    if left in d and above in d and d[above] != d[left]: 
     # left and above on different clusters, merge them 
     prevclid = d[left] 
     dcl[d[above]].extend(dcl[prevclid]) # update dcl 
     for l in dcl[d[left]]: 
      d[l] = d[above] # update d 
     del dcl[prevclid] 
     dcl[d[above]].append(t) 
     d[t] = d[above] 
    elif above in d and abovevalid: 
     dcl[d[above]].append(t) 
     d[t] = d[above] 
    elif left in d and leftvalid: 
     dcl[d[left]].append(t) 
     d[t] = d[left] 
    else: # First saw this one 
     dcl[clid] = [t] 
     d[t] = clid 
     clid += 1 

def print_output(): 
    for k in dcl: # Print output 
     print k, dcl[k] 

def main(): 
    global clid 
    global maxX 
    global maxY 
    maxX = len(data) 
    maxY = len(data[0]) 
    clid = 0 
    for i in xrange(maxX): 
     for j in xrange(maxY): 
      process_point((i,j)) 
    print_output() 

if __name__ == "__main__": 
    main()

그것은 인쇄 ...

0 [(0, 2), (0, 3), (1, 2), (1, 3)] 
1 [(2, 0), (2, 1), (3, 0), (3, 1)] 
2 [(2, 4), (2, 5), (3, 4), (3, 5)] 
3 [(4, 2), (4, 3), (5, 2), (5, 3)] 
4 [(6, 0), (6, 1), (7, 0), (7, 1)] 
5 [(6, 4), (6, 5), (7, 4), (7, 5)]

출처

2012-12-12 04:17:55 vkontori

연결된 구성 요소 알고리즘을 잘 구현합니다. 각각의 방문하지 않은 노드의 DFS를 사용한 그래프 채색 방식은 더 빠를 것이라고 생각합니다. – Arcturus

이미지 처리에 사용되는 잘 알려진 '얼룩'찾기 알고리즘을 사용하면 동일한 색상의 영역을 분리 할 수 있습니다. 섬을 찾아서 방문을 표시하여 자신 만의 풍미를 만들 수도 있습니다 (처음에는 모두 방문하지 않았습니다). 모두 연결된 (3x3 그리드에서 중앙 픽셀은 8 개의 연결됨) 및 방문 픽셀은 하나의 영역을 형성합니다. 지도에서 그러한 모든 지역을 찾아야합니다.

블로 브 찾기가 필요합니다.

출처

2012-12-12 03:22:11 Arcturus

Python 2D 클러스터 찾기

답변

관련 문제