플러드 필
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
플러드 필은 주어진 시작 지점과 색상을 기준으로 연결된 영역을 다른 색상으로 채우는 알고리즘이다. 이 알고리즘은 큐나 스택과 같은 자료 구조를 사용하여 구현되며, 4방향 또는 8방향으로 인접한 픽셀을 연결하여 채우기를 수행한다. 플러드 필은 재귀, 큐, 주사선 채우기, 고정 메모리 방법 등 다양한 방식으로 구현될 수 있으며, 그래프 이론을 적용하여 채우기를 수행하는 방법도 있다. 플러드 필은 비트맵 연산, 벡터 수행 등 다양한 분야에서 활용되며, 데이터 중심 또는 처리 중심의 접근 방식을 통해 효율적으로 수행될 수 있다.
더 읽어볼만한 페이지
- 의사코드가 있는 문서 - 플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 동적 계획법의 일종으로, 그래프 내의 모든 정점 쌍 간의 최단 경로를 찾아 시간 복잡도 O(N^3)으로 계산하며, 유향 그래프의 최단 경로 탐색 등 다양한 문제에 적용된다. - 의사코드가 있는 문서 - 데이크스트라 알고리즘
데이크스트라 알고리즘은 에츠허르 데이크스트라가 고안한 알고리즘으로, 그래프에서 한 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾으며, 내비게이션과 네트워크 라우팅 등에 응용되고 가중치가 음수가 아닌 그래프에서 효율적으로 작동한다. - 컴퓨터 그래픽스 알고리즘 - 알파 합성
알파 합성은 이미지의 투명도를 표현하고 합성하는 기술로, 알파 채널을 사용하여 투명도 정보를 저장하고 스트레이트 알파와 프리멀티플라이드 알파 방식으로 이미지를 합성하며, PNG, TIFF, GIF 등 다양한 이미지 형식이 이를 지원한다. - 컴퓨터 그래픽스 알고리즘 - 클리어타입
클리어타입은 마이크로소프트에서 개발한 서브픽셀 렌더링 기술로, LCD와 같은 평판 모니터에서 텍스트 가독성을 향상시키기 위해 픽셀을 구성하는 서브픽셀을 개별적으로 제어하여 글꼴의 앤티에일리어싱 효과를 개선하고 텍스트를 더 부드럽게 보이도록 하는 기술이다.
| 플러드 필 | |
|---|---|
| 알고리즘 정보 | |
| 유형 | 영역 채우기 알고리즘 |
| 목적 | 이미지의 특정 영역을 색상 또는 무늬로 채우기 |
| 입력 | 시작점 (seed point) 대상 영역 채울 색상 또는 무늬 |
| 출력 | 채워진 이미지 |
| 기본 정보 | |
| 다른 이름 | 씨앗 채우기 (seed fill) 영역 채우기 (area fill) |
| 범주 | 컴퓨터 그래픽스 알고리즘 |
| 사용 분야 | 이미지 편집 게임 개발 컴퓨터 그래픽스 |
| 작동 원리 | |
| 설명 | 시작점으로부터 인접한 픽셀들을 검사하며, 대상 영역의 경계에 도달할 때까지 지정된 색상 또는 무늬로 채워나가는 방식 |
| 방식 | 재귀적 (recursive) 반복적 (iterative) |
| 주요 단계 | 시작점을 스택에 넣기 스택이 빌 때까지 다음을 반복: 스택에서 픽셀을 꺼내 지정된 색상으로 채우기 픽셀의 상하좌우 이웃 픽셀이 대상 영역 내에 있고 아직 채워지지 않았다면 스택에 넣기 |
| 종류 | |
| 4방향 플러드 필 (4-way flood fill) | 상하좌우 4방향으로 인접한 픽셀을 검사 |
| 8방향 플러드 필 (8-way flood fill) | 상하좌우 및 대각선 8방향으로 인접한 픽셀을 검사 |
| 장단점 | |
| 장점 | 구현이 비교적 간단함 |
| 단점 | 재귀적 방식은 스택 오버플로 발생 가능성 존재 복잡한 모양의 영역을 채울 때 성능 저하 발생 가능성 존재 |
| 성능 향상 기법 | |
| 설명 | 스택 대신 큐(queue) 사용 영역의 경계를 미리 계산하여 불필요한 픽셀 검사 줄이기 병렬 처리 활용 |
| 활용 예시 | |
| 이미지 편집 프로그램 | 특정 영역을 선택하여 색상 변경, 패턴 채우기 등에 사용 |
| 게임 개발 | 특정 영역을 색칠하거나, 게임 맵 생성 등에 사용 |
| 기타 | CAD (Computer-Aided Design) 소프트웨어 의료 영상 처리 |
| 관련 알고리즘 | |
| 설명 | 경계 채우기 (boundary fill): 특정 경계 내의 영역을 채우는 알고리즘 스캔 라인 채우기 (scanline fill): 스캔 라인을 따라 영역을 채우는 알고리즘 |
2. 알고리즘
플러드 필 알고리즘은 시작 칸, 목표 색, 대체 색의 세 개의 인자를 받는다. 이 알고리즘은 배열에 있는 시작 칸에서 목표 색으로 연결된 모든 칸을 방문해서 대체 색으로 바꾼다. 플러드 필 알고리즘을 구현하는 방법은 여러가지가 있지만, 대부분 큐나 스택과 같은 자료구조를 사용한다.
모서리가 맞닿은 칸이 연결되어 있는 지에 따라서 두 가지 변형이 있다: 각각 4방향과 8방향이다.
전통적인 플러드 필 알고리즘은 시작 노드, 대상 색상, 대체 색상 등 세 가지 매개변수를 사용한다. 이 알고리즘은 배열에서 대상 색상의 경로로 시작 노드에 연결된 모든 노드를 찾아 대체 색상으로 변경한다. 경계 채우기의 경우, 대상 색상 대신 경계 색상이 제공된다.
일반적인 방식으로 알고리즘을 일반화하기 위해, 다음 설명에서는 두 개의 루틴을 사용할 수 있다.[7] 하나는 채워지지 않은 점이 해당 색상에 의해 채워진 영역 내부에 있는 경우 true를 반환하는 Inside라고 하고, 다른 하나는 픽셀/노드를 채우는 Set이라고 한다. Set이 호출된 노드는 더 이상 Inside가 아니어야 한다.
모서리에서 접촉하는 노드를 연결된 것으로 간주할지 여부에 따라, 각각 8방향과 4방향의 두 가지 변형이 있다.
2. 1. 스택 기반 재귀 수행 (4방향)
스택 기반 재귀 수행(4방향)은 재귀 함수를 이용하여 플러드 필을 구현하는 방식이다.[3][4][5][6] 코드가 간결하다는 장점이 있지만, 스택 공간이 제한된 환경(자바 애플릿, 마이크로컨트롤러 등)에서는 스택 오버플로우가 발생할 위험이 있어 실용적이지 않다.[5]기본적인 플러드 필 알고리즘의 작동 방식은 다음과 같다:
'''플러드 필''' (노드):
1. 만약 ''노드''가 ''내부''가 아니면, 반환한다.
2. ''노드''를 ''설정''한다.
3. ''노드''의 남쪽으로 한 단계 '''플러드 필'''을 수행한다.
4. ''노드''의 북쪽으로 한 단계 '''플러드 필'''을 수행한다.
5. ''노드''의 서쪽으로 한 단계 '''플러드 필'''을 수행한다.
6. ''노드''의 동쪽으로 한 단계 '''플러드 필'''을 수행한다.
7. 반환한다.
재귀 호출 대신 스택 또는 큐와 같은 자료 구조를 사용하여 스택 오버플로우를 방지할 수 있다.
2. 2. 큐 기반 수행
큐 기반 수행은 명시적인 큐를 사용하여 칸을 관리하는 방식으로, "산불 알고리즘"이라고도 불린다.[13] 이 방식은 단순 재귀 해법과 유사하지만 재귀 호출 대신 칸을 큐에 넣어 처리한다. 의사 코드는 다음과 같다.:'''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.
추가적인 배열을 사용하여 채워진 영역의 경계를 흐리게 처리하는 "흐린" 플러드 필로 일반화할 수 있다. 이 배열은 알파 채널로 사용되어 채워진 영역과 채워지지 않은 영역을 부드럽게 혼합한다.
재귀를 스택 또는 큐와 같은 자료 구조로 옮기면 스택 오버플로우를 방지할 수 있다. 자료 구조의 선택은 확산 패턴에 영향을 준다.
'''플러드 필''' (노드):
: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. 반환한다.
추가적으로 수행성능을 높이기 위해 다음과 같은 최적화 기법들이 존재한다.[5]
- 각 노드를 스택/큐에 추가하기 전에 해당 노드의 픽셀 색상을 확인하고 설정하여 스택/큐의 크기를 줄인다.
- 동서 방향에 루프를 사용하여 위/아래 픽셀을 큐에 추가한다(아래의 범위 채우기 알고리즘과 유사하게 만든다).
- 아웃오브오더 프로세서가 병렬화할 수 있는 기회를 더 많이 제공하기 위해 추가 스택/큐를 사용하여 코드의 두 개 이상의 복사본을 인터리브한다.
- 여러 스레드를 사용한다.
2. 3. 주사선 채우기
주사선 채우기는 한 번에 한 줄씩 채워나가는 방식이다. 이는 스택이나 큐를 사용하여 다음에 채울 줄을 관리하는 방식으로, 픽셀 단위 알고리즘보다 효율적이다.[1]
이 알고리즘은 한 줄을 채움으로써 속도를 높일 수 있다. 가능한 픽셀 좌표를 각각 스택에 집어 넣는 것이 아니라, 다음에 채울 조각을 찾을 때 이웃한 줄(이전 줄과 다음 줄)을 넣는다. 선분의 좌표(시작과 끝)가 스택에 들어간다. 대부분의 경우, 주사선 알고리즘은 픽셀 단위 알고리즘보다 적어도 크기만큼 빠르다. 각각의 픽셀은 한 번만 검사된다.
스팬, 즉 `y`가 일정한 행을 주로 사용하면 더 효율적으로 작업할 수 있다. 최초로 공개된 완전한 예제는 다음과 같은 기본 원리로 작동한다.[1]
# 시드 포인트로 시작하여 왼쪽과 오른쪽을 채운다. 가장 왼쪽 채워진 점 `lx`와 가장 오른쪽 채워진 점 `rx`를 추적한다. 이는 스팬을 정의한다.
# 시드 포인트 위와 아래의 `lx`에서 `rx`까지 스캔하여 계속 진행할 새로운 시드 포인트를 찾는다.
최적화를 위해 스캔 알고리즘은 모든 시드 포인트에서 다시 시작할 필요 없이 다음 스팬의 시작점에 있는 시드 포인트에서만 시작하면 된다. 스택을 사용하면 스팬을 깊이 우선으로 탐색하는 반면, 큐를 사용하면 스팬을 너비 우선으로 탐색한다.
시간이 지남에 따라 다음과 같은 최적화가 이루어졌는데, 새로운 스캔이 조상 스팬 내에서 완전히 이루어질 경우, 채워진 픽셀만 발견하므로 큐에 넣을 필요가 없다.[1][5][7] 또한 새로운 스캔이 조상 스팬과 겹칠 경우, 오버행(U-턴 및 W-턴)만 스캔하면 된다.[7] 시드를 스캔하는 동안 채울 수 있다.[5]
최종적으로 결합된 스캔 및 채우기 스팬 채우기가 1990년에 공개되었다.[8] 이 알고리즘은 픽셀 재귀 알고리즘보다 2~8배 빠르며, 접근 방식이 캐시 및 비트 플레인에 친화적이다.[5] 개별 픽셀을 설정하는 대신 수평선을 그릴 수 있다.[5] 하지만 이미 채워진 픽셀을 계속 방문하며, 널리 사용되는 알고리즘의 경우, 대부분의 픽셀을 3번 스캔한다. (마지막 스캔에서는 채워진 영역에 구멍이 있는 픽셀만 추가로 스캔한다.)[7] 픽셀 테스트 결과가 변경되어야 하므로 패턴 채우기에는 적합하지 않다.
2. 4. 고정 메모리 방법 (오른손 채우기 방법)
고정 메모리 방법(오른손 채우기 방법)은 제한된 메모리 환경에서 플러드 필 알고리즘을 수행하는 방식이다. 이 방법은 마치 미로를 탐색하는 것처럼 영역의 경계를 따라 이동하며 채우기를 수행한다.[12]화가는 다음 조건 중 하나에 놓인다.[12]
| 조건 | 설명 |
|---|---|
| 4개의 경계 픽셀이 모두 채워져 있음 | 현재 픽셀을 채우고 알고리즘을 종료한다. |
| 3개의 경계 픽셀이 채워져 있음 | 현재 픽셀을 채운다. |
| 2개의 경계 픽셀이 채워져 있음 | 현재 픽셀을 채우면 경로가 막힐 수 있으므로, "표시"를 사용하여 위치와 방향을 기억한다. 표시가 이미 있으면 이전 표시를 유지하고 오른손 법칙에 따라 다음 픽셀로 이동한다. 표시를 다시 만났을 때 방향이 같으면 표시 위치를 채우고, 다르면 루프를 제거하는 과정을 거친다. |
| 1개의 경계 픽셀이 채워져 있음 | 현재 픽셀을 채우고 오른손 법칙에 따라 이동한다. 8방향 연결된 모서리가 채워져 있는지 확인하여 다중 경로 교차로 생성을 방지한다. |
| 0개의 경계 픽셀이 채워져 있음 | 현재 픽셀을 채우고 오른손 법칙에 따라 이동한다. |
이 알고리즘은 오른손 법칙을 사용하여 영역의 경계를 따라 이동한다. 즉, 화가는 오른손을 벽에 짚고 손을 떼지 않으면서 영역을 채워 나간다.[12] 2개의 경계 픽셀이 채워진 경우, "표시"를 사용하여 루프를 처리하고 경로를 유지한다.
이 알고리즘은 시간을 메모리로 교환하는 방식이다. 단순한 형태에서는 효율적이지만, 복잡한 형태에서는 영역 경계를 따라 이동하는 데 많은 시간을 소비할 수 있다.[12] 1981년에 Vicom Systems, Inc에서 제작한 Vicom Image Processing 시스템에서 처음 상업적으로 사용되었다.[12]
보행 알고리즘은 1994년에 발표되었다.[12]
2. 5. 그래프 이론적 채우기
픽셀 집합을 그래프의 노드로 간주하고 연결성을 연구하여 명시적인 그래프 이론을 적용해 채우기를 수행한다.[9] 최초로 공개된 그래프 이론 알고리즘은 범위 채우기와 유사하게 작동했지만 범위 채우기의 중복을 감지하는 방법이 있었다.[9] 그러나 이 알고리즘은 일부 채우기를 완료하지 못하게 하는 버그가 있었다.[10] 이후 수정된 알고리즘이 공개되었지만, 프로그램 인터페이스를 복잡하게 만들기 위해 잠재적인 루프를 일시적으로 차단하기 위해 이미지를 변경하는 방식을 사용했다.[10] 나중에 공개된 알고리즘은 경계가 이미지의 다른 모든 것과 구별되어야 하므로 대부분의 용도에 적합하지 않으며, 기록 유지를 위해 픽셀당 추가 비트가 필요하다는 단점이 있다.[11][7]그래프 이론적 채우기는 패턴 채우기에 적합하며, 채워진 픽셀을 다시 검사하지 않는다.[9][10][11] 단순한 채우기의 경우, 기존의 스팬 알고리즘보다 속도가 두 배 빠르다.[7] 엑세스 패턴이 캐시와 비트 플레인에 친화적이다.[5][7] 하지만 정기적으로 범위는 큐에 있는 다른 모든 '앞쪽'과 비교해야 하므로 복잡한 채우기 작업의 속도가 현저히 느려진다.[7] 또한, 그래프 이론 및 픽셀 도메인 간의 전환은 이해를 복잡하게 만들고, 코드가 복잡하여 버그가 발생할 가능성이 높다는 단점이 있다.
3. 벡터 수행
잉크스케이프 버전 0.46은 채우기 도구가 있어서 일반적인 비트맵 연산과 비슷한 결과를 내며 실제로 사용한다. 캔버스가 렌더 되고, 플러드 필 연산을 선택된 영역에 수행한 후, 그 결과를 가지고 경로를 되돌아간다. 이는 경계 조건의 개념을 사용한다.
4. 큰 규모에서의 양상
플러드 필을 조작할 때 주로 사용되는 기술은 데이터 중심과 처리 중심이 있다. 데이터 중심 접근은 확인 할 시드 픽셀을 쫓아가기 위해서 스택이나 큐를 사용할 수 있다. 처리 중심 알고리즘은 반드시 스택을 사용해야 한다.
인접 기술과 시드 픽셀 저장으로 큐를 사용하는 4방향 플러드 필 알고리즘은 확장하는 마름모꼴의 형태로 채운다.
인접 기술과 시드 픽셀 저장으로 스택을 사용하는 4방향 플러드 필 알고리즘은 "틈은 나중에 메우는" 양상을 띄며 선형적으로 채운다. 이 접근은 특히 ''Graphic Adventure Creator''에서 만든 게임 같은 오래된 8비트 게임에서 나타난다.
효율성: 각각의 픽셀이 채워질 때 4픽셀이 검사된다 (8방향에서는 8픽셀).
참조
[1]
학회
Tint Fill
[2]
학회
The edge flag algorithm — A fill method for raster scan displays
[3]
서적
Principles of Interactive Computer Graphics
McGraw-Hill
[4]
서적
Algorithms for Graphics and Image Processing
Springer-Verlag
[5]
학회
Area Flooding Algorithms
[6]
서적
Computer Graphics: Principles and Practice
Addison–Wesley
[7]
학회
An Analysis and Algorithm for Filling Propagation
[8]
서적
Graphics Gems
Academic Press
[9]
학회
How to Color in a Coloring Book
[10]
학회
Filling regions in binary raster images: A graph-theoretic approach
[11]
학회
Contour Filling in Raster Graphics
[12]
학회
Space-efficient region filling in raster graphics
[13]
서적
Applied Computer Science
https://books.google[...]
Springer
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com