라벨의 이중 배열을 세분화

Question

문제점 :

나는 다양한 라벨로 채워진 대형 더블 (2 차원) 배열을 가지고있다. double 배열의 각 요소 (셀)에는 레이블 집합이 들어 있고 double 배열의 일부 요소는 비어있을 수 있습니다. 이중 배열의 요소를 개별 세그먼트로 클러스터링하는 알고리즘이 필요합니다. 세그먼트는 이중 배열에서 인접한 픽셀 집합과 세그먼트의 모든 픽셀이 공통으로 갖는 레이블 하나로서 정의됩니다. 대각선 인접성은 계산되지 않으며 빈 셀을 클러스터링하지 않습니다. 구 개 요소에 분포 레이블 상기 구성에서

|-------|-------|-------| 
| Jane | Joe |  | 
| Jack | Jane |  | 
|-------|-------|-------| 
| Jane | Jane |  | 
|  | Joe |  | 
|-------|-------|-------| 
|  | Jack | Jane | 
|  | Joe |  | 
|-------|-------|-------| 

, 최대 규모의 클러스터는 네 왼쪽 상단 세포를 점유 "제인"클러스터입니다.

내가 이중 배열의 모든 셀의 모든 라벨을 반복 검사에서 셀 라벨 조합이 기존 세그먼트와 연관 ​​될 수 있는지 확인하기 위해 테스트를 생각했습니다 내가 고려했습니다 무엇

. 검사중인 요소가 기존 세그먼트와 연관 ​​될 수없는 경우 새 세그먼트의 첫 번째 구성원이됩니다. 레이블/셀 조합이 기존 세그먼트와 연관 ​​될 수 있으면 레이블/셀 조합이 연관됩니다.

물론이 방법을 합리적으로 만들기 위해서는 정교한 해싱 시스템을 구현해야합니다. 기존 세그먼트에 인접한 셀 레이블 조합을 모두 추적해야하며 이중 배열을 통해 반복되는 인덱스가 증가하는 경로에 있어야합니다. 이 해시 방법은 인접성을 찾기 위해 모든 기존 세그먼트의 모든 픽셀을 반복해야하는 번거 로움을 피할 수 있습니다.

나는 그것을 좋아하지 않아 이유 :

을있는 그대로, 고려 이중 배열의 요소는 두 개의 독특한 세그먼트의 하나와 연관 될 수있는 경우를 고려하지 않습니다 위의 알고리즘 수평 방향으로 하나, 수직 방향으로 하나씩. 이러한 사례를 올바르게 처리하려면이 특정 사례에 대한 테스트를 구현 한 다음 검사중인 요소를 세그먼트와 연결 한 다음 인접한 두 개의 동일한 세그먼트를 연결하는 메서드를 구현해야합니다.

전체적으로이 방법과 필요한 복잡한 해싱 시스템은 매우 우아하지 않습니다. 또한 이중 배열에서 큰 세그먼트를 찾는 것에 대해서만 신경을 쓰고 세그먼트 알고리즘의 정확도보다이 알고리즘의 속도에 훨씬 더 관심이 있습니다. 따라서 더 나은 방법을 찾고 있습니다. 나는 이것을 생각한 적이없는 확률적인 방법이 있다고 가정합니다.

제안 사항?

편집 :

내 원하는 출력 세그먼트의 목록은, 라벨과 지점의 목록 인 각 세그먼트. - 이미지 세트, 독특한 라벨 당 하나의 같은 배열을 고려

Segment 1 - Jane: (1,3), (2,3), (1,2), (2,2) 
Segment 2 - Joe: (2,3), (2,2), (2,1) 

Answer 1

당신은 기본적으로 홍수 채우기 알고리즘을 구현하려는 : 따라서, 예제에서 나는 두 개의 세그먼트가 반환 싶어 위 label은 색깔이고, label이 없다는 것은 검은 색이다. 그런 다음 해당 색상의 연결된 모든 구성 요소로 세그먼트를 분할하려고합니다.

모든 라벨에 대해 반복하면 완료됩니다.

레이블이 희박한 경우 실제로 각 레이블에 이미지를 작성하지 않고 기존 플러드 채우기 루틴을 사용하는 것이 좋습니다. 이 경우 배열의 복사본을 만들고 기존 레이블을 손상시키면서 연결된 레이블을 한 번에 하나씩 작성하여 폭 넓은 첫 번째 채우기를 수행하십시오.

하나의 항목을 "픽셀"이라고하고 전체 배열을 "이미지"라고하겠습니다.

알고리즘이 파괴이기 때문에, 당신이 되돌아에 대해 걱정할 필요가 없습니다, 약,

for each pixel in the image 
    for each label in the pixel 
    1. remove the label 
    2. mark the current pixel 
    3. for each marked pixel, look in every adjacent pixel for the label 
    4. remove any labels found 
    5. if labels are found, clear marks, and mark the newly label-removed pixels 
    6. if anything is marked, go back to 3 
    7. report the set of points where you removed labels 

간다. (원본을 파기 할 수없고 사본을 만들 수 없다면 방해가되는 일을 추적해야합니다.