홍수 채우기: 컴퓨터 시각 인식의 동적 지형 탐색

By Fouad Sabry

플러드 필이란 무엇인가요?

시드 필이라고도 불리는 플러드 필은 다차원 배열의 특정 노드에 연결된 영역을 결정하고 변경하는 플러딩 알고리즘입니다. 일치하는 속성이 있습니다. 이는 페인트 프로그램의 "버킷" 채우기 도구에서 연결되어 있고 유사한 색상의 영역을 다른 색상으로 채우는 데 사용되며 가서 지뢰 찾기와 같은 게임에서는 어느 조각이 지워지는지 결정하는 데 사용됩니다. 경계 채우기라는 변형은 동일한 알고리즘을 사용하지만 특정 속성이 없는 특정 노드에 연결된 영역으로 정의됩니다.

혜택을 받는 방법

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 홍수 채우기

2장: 스캔라인 렌더링

3장: 깊이 -첫 번째 검색

4장: 쿼드트리

5장: 그래프 순회

6장: 연결된 구성 요소 레이블 지정

7장: 유역(이미지 처리)

8장: 미로 해결 알고리즘

9장: 광선 캐스팅

10장: 상자 흐림

(II) 홍수 채우기에 관한 대중의 주요 질문에 답합니다.

(III) 다양한 분야에서 홍수 채우기 사용에 대한 실제 사례.

이 책은 누구를 위한 것인가요?

전문가, 학부 및 대학원생, 열성팬, 취미생활자 및 모든 종류의 홍수 채우기에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들.

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 4, 2024

Book preview

1장: 홍수 채우기

시드 채우기라고도 하는 홍수 채우기는 특정 속성을 가진 특정 노드와 연결된 다차원 배열에서 영역을 선택하고 수정하는 홍수 알고리즘입니다. Go 및 Minesweeper와 같은 게임에서 어떤 조각이 제거되는지 결정하는 데 사용되며 페인트 응용 프로그램의 버킷 채우기 도구에서 연결된 유사한 색상의 영역을 고유한 색조로 채우는 데 사용됩니다. 지정된 노드에 연결되었지만 특정 특성이 없는 영역은 동일한 기술을 사용하는 테두리 채우기로 알려진 변형을 의미합니다.

플러드 필링은 더 예리한 모서리의 특정 픽셀을 놓치기 때문에 채워진 다각형을 그리는 데 적합하지 않습니다. 대신 Nonzero Rule(0이 아닌 규칙)과 Even-Odd Rule(짝수-홀수 규칙)을 선택합니다.

기존 플러드 채우기 알고리즘에는 세 가지 변수, 즉 시작 노드, 대상 색상 및 대체 색상이 필요합니다. 이 메서드는 대상 색인 경로로 시작 노드에 연결된 배열의 모든 노드에 대한 대체 색으로 전환됩니다. 대상 색 대신 경계 채우기를 위해 테두리 색이 제공됩니다.

대신에, 통상적인 방식으로 방법을 일반화하기 위해 두 개의 루틴이 다음 설명에서 제공될 것이다. 이 중에는 픽셀 또는 노드를 채우는 Set과 색상에 따라 채워진 영역 내부에 있는 채워지지 않은 점에 대해 true를 반환하는 Inside가 있습니다. 노드에서 Set 이 호출되면 Inside를 벗어나야 합니다.

모서리에 닿는 노드를 연결된 것으로 계산하는지 여부에 따라 각각 8방향 및 4방향의 두 가지 버전이 있습니다.

다음은 암시적으로 스택 기반인 가장 초기에 알려진 4방향 플러드 필 구현입니다.

홍수 채우기(노드):

1. 노드 가 내부가 아닌 경우 반환합니다.

2. 노드 설정

3. 노드 남쪽으로 한 단계 범람 채우기를 수행합니다.

4. 노드 북쪽으로 한 단계 Flood-fill  을 수행합니다.

5. 노드 서쪽으로 한 단계 Flood-fill  을 수행합니다.

6. 노드의 동쪽으로 한 단계 Flood-fill  을 수행합니다.

7. 반환.

스택 공간이 극도로 제한된 언어 및 상황에서는 위에서 사용한 기술을 구현하기가 쉽지만 작동할 수 없습니다(예: 마이크로 컨트롤러).

스택 오버플로는 재귀를 스택 또는 큐와 같은 데이터 구조로 이동하여 방지됩니다. 데이터 구조의 선택은 확산 패턴에 영향을 미치지만 재귀 호출을 수행하는 대신 노드를 스택 또는 큐로 밀어 넣는다는 점에서 단순 재귀 방법과 유사합니다.

홍수 채우기(노드):

1. Q 를 빈 대기열 또는 스택으로 설정합니다.

2. Q의 끝에 노드를 추가합니다.

3. Q 가 비어 있지 않은 경우:

4. n을 Q의 첫 번째 요소와 같 게 설정합니다.

5. Q에서 첫 번째 요소를 제거합니다.

6. n 이 내부에 있는 경우:

n을 설정합니다.

n의 서쪽에서 Q의 끝에 노드를 추가합니다.

n의 동쪽에서 Q의 끝에 있는 노드를 추가합니다.

n의 북쪽에서 Q의 끝에 노드를 추가합니다.

n의 남쪽에서 Q의 끝에 있는 노드를 추가합니다.

7. Q  가 소진될 때까지 계속 반복합니다.

8. 반환.

스택 또는 대기열에 노드를 추가하기 전에 스택 또는 대기열의 크기를 최소화하기 위해 픽셀 색상을 결정하고 설정합니다.

루프를 사용하여 위와 아래의 픽셀을 대기열에 넣으면서 동서 방향으로 이동합니다(아래의 스팬 채우기 알고리즘과 유사하게 만들기).

순서가 잘못된 프로세서에 병렬화할 수 있는 더 많은 기회를 제공하려면 두 개 이상의 코드 복사본을 추가 스택 및 큐와 인터리브합니다.

여러 스레드를 사용하되 방문 일정이 약간 다르면 한 곳에 모이지 않도록 하는 것이 좋습니다.

버그가 없는 간단한 방법으로 간단하게 만들 수 있습니다.

특히 스택을 사용할 때 메모리를 많이 사용합니다.

가장 많이 채워진 픽셀을 총 4번 테스트합니다.

패턴 채우기는 픽셀 테스트의 결과가 변경되어야 하므로 불가능합니다.

큐 변형에 대한 액세스 패턴은 캐시에 친숙하지 않습니다.

비트플레인 또는 다중 픽셀 단어에 최적화하기 어렵습니다.

주로 스팬, 상수 y를 가진 행으로 작업하면 추가 최적화가 가능합니다. 첫 번째로 게시된 전체 예제는 다음과 같은 기본 원칙에 따라 작동합니다.

시드 포인트 뒤의 왼쪽과 오른쪽을 채웁니다. 가장 왼쪽과 가장 오른쪽에 채워진 점(lx와 rx)을 각각 추적합니다. 이렇게 하면 범위가 설정됩니다.

현재 시드 포인트 위와 아래의 lx에서 rx로 스캔하여 더 많은 시드 포인트를 검색합니다.

스캔 프로세스는 다음 범위의 시작 부분에 있는 시드 지점만 다시 시작해야 하도록 최적화됩니다. 대기열은 스팬을 먼저 탐색하는 반면, 스택은 깊이 측면에서 스팬을 먼저 조사합니다.

가장 많이 채워진 픽셀을 총 세 번 확인함에도 불구하고 이 접근 방식은 구현 및 인용 측면에서 가장 일반적입니다.

fn 채우기 (x, y) :

Inside(x, y) 가 아닌 경우 반환

let s = 새로운 빈 스택 또는 대기열

s에 (x, y)를 추가합니다.

s가 비어 있지 않은 경우:

s에서 (x, y) 를 제거합니다.

lx = x 라고 하자

내부 (lx - 1, y) :

세트(lx - 1, y)

lx = lx - 1

내부 (x, y) :

세트(x, y)

x = x + 1

스캔(lx, x - 1, y + 1, s)

스캔(lx, x - 1, y - 1, s)

fn 스캔(lx, rx, y, s):

span_added = 거짓이라고 하자

lx의 x .. 수신:

내부(x, y)가 아닌 경우:

span_added = 거짓

그렇지 않으면 span_added :

s에 (x, y)를 추가합니다.

span_added = 참

시간이 지남에 따라 다음과 같은 개선 사항이 적용되었습니다.

새로운 스캔은 채워진 픽셀만 감지하기 때문에 조부모 범위 내에 있는 경우 큐에 대기할 필요가 없습니다.

또한 새로운 스캔이 조부모 스팬을 가로지르는 경우 돌출부(U턴 및 W턴)만 스캔해야 합니다.

씨앗을 찾으면서 채울 수 있습니다.

fn 채우기 (x, y) :

Inside(x, y) 가 아닌 경우 반환

let s = 새로운 빈 대기열 또는 스택

s에 (x, x, y, 1)을 더합니다.

s에 (x, x, y - 1, -1)을 더합니다.

s가 비어 있지 않은 경우:

s에서 (x1, x2, y, dy) 를 제거합니다.

x = x1 이라고 하자

내부(x, y)인 경우:

내부 (x-1, y) :

세트(x - 1, y)

x = 엑스 - 1

x가 x1< 경우:

s에 (x, x1-1, y-dy, -dy)를 추가합니다.

x1