플러드 필

플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다.

알고리즘

플러드 필 알고리즘은 시작 칸, 목표 색, 대체 색의 세 개의 인자를 받는다. 이 알고리즘은 배열에 있는 시작 칸에서 목표 색으로 연결된 모든 칸을 방문해서 대체 색으로 바꾼다. 플러드 필 알고리즘을 구현하는 방법은 여러가지가 있지만, 대부분 큐나 스택과 같은 자료구조를 사용한다.

모서리가 맞닿은 칸이 연결되어 있는 지에 따라서 두 가지 변형이 있다: 각각 4방향과 8방향이다.

스택 기반 재귀 수행 (4 방향)

암시적 스택 기반 (재귀적) 플러드 필 수행(이차원 배열)은 다음과 같다:

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

위에서 사용되는 알고리즘의 수행은 이해하기 쉽지만, 스택공간이 매우 제한된 언어나 환경(예: 자바 애플릿)에서는 실용적이지 않다.

큐 기반 수행

명시적인 큐 기반 수행(종종 "산불 알고리즘"이라고도 불린다^[1])은 아래에 의사 코드로 나타나 있다. 이 수행은 단순한 재귀 해법과 비슷하지만 재귀 호출을 하지 않고 칸을 큐에 넣는다:

Flood-fill (node, target-color, replacement-color):
  1. If target-color is equal to replacement-color, return.
  2. If color of node is not equal to target-color, return.
  3. Set Q to the empty queue.
  4. Set the color of node to replacement-color.
  5. Add node to the end of Q.
  6. While Q is not empty:
  7.     Set n equal to the first element of Q.
  8.     Remove first element from Q.
  9.     If the color of the node to the west of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 10.     If the color of the node to the east of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 11.     If the color of the node to the north of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 12.     If the color of the node to the south of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 13. Continue looping until Q is exhausted.
 14. Return.

대부분의 실용적인 수행은 스택이나 큐의 오버플로우를 막기 위해 가로 방향 루프를 사용해서 최척화한다:

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If color of node is not equal to target-color, return.
 3. Set Q to the empty queue.
 4. Add node to Q.
 5. For each element N of Q:
 6.     Set w and e equal to N.
 7.     Move w to the west until the color of the node to the west of w no longer matches target-color.
 8.     Move e to the east until the color of the node to the east of e no longer matches target-color.
 9.     For each node n between w and e:
10.         Set the color of n to replacement-color.
11.         If the color of the node to the north of n is target-color, add that node to Q.
12.         If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.

이 알고리즘에서 영역의 모양을 저장하도록 추가로 배열을 사용하면 채워진 영역의 특정한 경계에서 칸이 다를 수 있는 "흐린" 플러드 필로 일반화 할 수 있다. 이 추가적인 배열을 알파 채널로 사용하면 채워진 영역의 경계에서 채워지지 않은 영역과 부드럽게 섞일 수 있다.^{[출처 필요]}

고정 메모리 방법(오른손 채우기 방법)

알고리즘이 화가가 되어서 자신이 있는 칸을 색칠하는 것을 미뤄두고 주변의 4방향 연결된 영역을 색칠하기 위한 메모리가 본질적으로 없을 때 사용되는 방법이 있다. 이는 또한 미로를 푸는 방법이기도 하다. 일차적인 경계를 형성하는 네 픽셀은 어떤 행동을 취할지를 알기 위해서 확인한다. 화가는 다음 중 한 가지 상태에 있을 수 있다:

네 경계에 있는 모든 픽셀이 채워져 있다.
경계 픽셀 중 세 픽셀이 채워져 있다.
경계 픽셀 중 두 픽셀이 채워져 있다.
한 경계 픽셀이 채워져 있다.
경계 픽셀이 모두 채워져 있지 않다.

경로나 경계를 따라가기 위해서 오른손의 법칙을 사용한다. 화가는 오른손을 벽에(영역의 경계) 짚고 손을 떼지 않으면서 영역의 경계를 따라 칠한다.

1번 경우, 화가는 자신이 있는 픽셀을 칠하고 알고리즘을 끝낸다.

2번 경우, 그 영역을 나가는 경로가 있다. 자신이 있는 픽셀을 칠하고 열린 경로로 이동한다.

3번 경우, 현재 픽셀을 칠하면 반대편 경로로 가는 것이 불가능 할 수 있기 때문에 두 경계 픽셀이 경로를 결정한다. 따라서 만약 이 픽셀로 되돌아왔을 때 보기 위해 이 픽셀의 위치와 어느 방향으로 향하는 지를 "표시"해야 한다. 만약 이미 그런 "표시"가 있다면, 이전의 표시를 그대로 두고는 오른손 법칙을 따라서 다음 픽셀로 간다.

표시는 처음 찾은 2 픽셀 경계에서 통로가 어디서 시작했으며 화가가 어느 방향으로 움직였는지를 기억하기 위해서 사용한다. 만약 이 표시를 다시 찾았고, 화가가 같은 방향으로 가고 있다면, 표시가 있는 칸을 칠해도 괜찮기 때문에 칠하고 같은 방향으로 이동한다. 왜냐하면 나중에 (어떤 경로로든)표시와 반대쪽에 있는 픽셀에 도달해 칠할 수 있기 때문이다. 이 표시는 나중에 쓰기 위해 지운다.

만약 화가가 표시를 다시 찾았으나 다른 방향으로 가고 있었다면, 화가가 표시로 되돌아 오게 만든 어떤 루프가 있는 것이다. 이 루프는 없애야만 한다. 표시를 주워서 표시에 쓰여 있던 방향으로 다시 가되, 이번에는 왼손 법칙(오른손 법칙과 비슷하지만 왼손을 이용한다)을 이용해서 교차로(경계 픽셀이 셋 이상 열린 곳)를 찾을 때까지 계속 작업한다. 계속 왼손 법칙을 사용하지만 이번에는 단순한 통로(경계 픽셀 두 개로 이루어진 곳)을 찾는다. 이 두 픽셀 경계를 가지는 통로를 찾으면, 그 픽셀을 색칠한다. 이는 루프를 끝내고 알고리즘이 계속될 수 있게 한다.

4번 경우, 반대쪽 8방향 연결된 모서리가 채워졌는지를 검사해야 한다. 만약 둘 중 하나라도 채워져 있다면, 이 칸은 다경로 교차로를 만들기 때문에 칠해서는 안된다. 만약 둘 다 비었을 경우에는, 현재 픽셀을 칠하고 화가는 오른손 법칙을 따라서 이동한다.

이 알고리즘은 시간을 메모리로 바꾼다. 단순한 도형에 대해서는 매우 효율적이지만, 모양이 복잡하고 특징이 많으면, 모든 영역이 칠해졌다는 것을 확실히 하기 위해서 영역의 경계에서 매우 많은 시간을 소요한다.

이 알고리즘은 1981년에 처음으로 Vicom Systems, Inc에서 제작한 Vicom Image Processing 시스템에서 상업적으로 이용 가능해졌다. 이 시스템에서는 평범한 재귀 플러드 필 알고리즘도 사용 가능하다.

의사코드

다음은 최적의 고정 메모리 플러드 필 알고리즘의 의사코드 수행이다:

변수:

cur, mark, 그리고 mark2는 각각 픽셀의 좌표나 널 값을 가진다
    참고: mark가 널 값으로 설정 된다면, 이전 좌표 값을 지우면 안 된다.
        이 좌표들은 필요할 때마다 불러올 수 있게 해야 한다.
cur-dir, mark-dir, 그리고 mark2-dir는 각각 방향을 가진다 (왼쪽, 오른쪽, 위, 또는 아래)
backtrack과 findloop은 각각 논릿값을 가진다
count는 정수이다

알고리즘:

(참고: 모든 방향(front, back, left, right)은 cur-dir에 대해서 상대적이다)

set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false

while front-pixel is empty
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is empty
        if backtrack is true and findloop is false and either front-pixel or left-pixel is empty
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
    if count is not 4
        do
            turn right
        while front-pixel is empty
        do
            turn left
        while front-pixel is filled
    end if
    switch count
        case 1
            if backtrack is true
                set findloop to true
            else if findloop is true
                if mark is null
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both empty
                clear mark
                fill cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is filled
                if front-left-pixel is not filled
                    clear mark
                    fill cur
                    jump to PAINT
                end if
            else if mark is not set
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set
                    if cur is at mark
                        if cur-dir is the same as mark-dir
                            clear mark
                            turn around
                            fill cur
                            jump to PAINT
                        else
                            set backtrack to true
                            set findloop to false
                            set cur-dir to mark-dir
                        end if
                    else if findloop is true
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark
                        set cur to mark2
                        set cur-dir to mark2-dir
                        clear mark and mark2
                        set backtrack to false
                        turn around
                        fill cur
                        jump to PAINT
                    else if cur at mark2
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end
                end if
            end if
        end case
        case 3
            clear mark
            fill cur
            jump to PAINT
        end case
        case 4
            fill cur
            done
        end case
    end switch
end MAIN LOOP

주사선 채우기

이 알고리즘은 한 줄을 채움으로써 속도를 높일 수 있다. 가능한 픽셀 좌표를 각각 스택에 집어 넣는 것이 아니라, 다음에 채울 조각을 찾을 때 이웃한 줄(이전 줄과 다음 줄)을 넣는다. 선분의 좌표(시작과 끝)가 스택에 들어간다. 대부분의 경우, 주사선 알고리즘은 픽셀 단위 알고리즘보다 적어도 크기만큼 빠르다.

효율성: 각각의 픽셀은 한 번만 검사된다.

벡터 수행

잉크스케이프 버전 0.46은 채우기 도구가 있어서 일반적인 비트맵 연산과 비슷한 결과를 내며 실제로 사용한다: 캔버스가 렌더 되고, 플러드 필 연산을 선택된 영역에 수행한 후, 그 결과를 가지고 경로를 되돌아간다. 이는 경계 조건의 개념을 사용한다.

큰 규모에서 양상

큐를 저장 공간으로 사용하는 4방향 플러드 필

스택을 저장 공간으로 사용하는 4방향 플러드 필

플러드 필을 조작할 때 주로 사용되는 기술은 데이터 중심과 처리 중심이 있다. 데이터 중심 접근은 확인 할 시드 픽셀을 쫓아가기 위해서 스택이나 큐를 사용할 수 있다. 처리 중심 알고리즘은 반드시 스택을 사용해야 한다.

인접 기술과 시드 픽셀 저장으로 큐를 사용하는 4방향 플러드 필 알고리즘은 확장하는 마름모꼴의 형태로 채운다.

효율성: 각각의 픽셀이 채워질 때 4픽셀이 검사된다 (8방향에서는 8픽셀).

인접 기술과 시드 픽셀 저장으로 스택을 사용하는 4방향 플러드 필 알고리즘은 "틈은 나중에 메우는" 양상을 띄며 선형적으로 채운다. 이 접근은 특히 Graphic Adventure Creator에서 만든 게임 같은 오래된 8비트 게임에서 나타난다.

효율성: 각각의 픽셀이 채워질 때 4픽셀이 검사된다 (8방향에서는 8픽셀).

같이 보기

외부 링크

Didactical Javascript implementation of scanline polygon fill, by Guilherme Polo.
Sample implementations for recursive and non-recursive, classic and scanline flood fill, by Lode Vandevenne.
Flash flood fill implementation, by Emanuele Feronato.
QuickFill: An efficient flood fill algorithm., by John R. Shaw.

각주

↑ Torbert, Shane (2016). 《Applied Computer Science》 2판. Springer (2016년 6월 1일에 출판됨). 158쪽. doi:10.1007/978-3-319-30866-1. ISBN 978-3-319-30864-7. LCCN 2016936660. 2016년 12월 21일에 원본 문서에서 보존된 문서.

[1] Torbert, Shane (2016). 《Applied Computer Science》 2판. Springer (2016년 6월 1일에 출판됨). 158쪽. doi:10.1007/978-3-319-30866-1. ISBN 978-3-319-30864-7. LCCN 2016936660. 2016년 12월 21일에 원본 문서에서 보존된 문서.

[1]