개요
컴퓨터 그래픽스에서 이미지의 특정 영역을 색으로 채우는 작업은 매우 중요한 기능입니다. 이번 글에서는 대표적인 영역 채우기(area-filling) 알고리즘인 플러드 필(Flood-Fill)과 바운더리 필(Boundary-Fill)의 차이점을 자세히 살펴보겠습니다. 두 알고리즘 모두 영역을 채우는 목적은 같지만, 임의의 픽셀이 해당 영역의 원래 색상을 가지고 있는지 여부에 따라 구분됩니다.
플러드 필(Flood-Fill) 알고리즘이란?
플러드 필 알고리즘은 시드 필(seed fill) 알고리즘이라고도 불리며, 다차원 배열에서 주어진 노드(시작점)에 연결된 영역을 계산하는 방식으로 동작합니다.
- 내부에 서로 다른 색상이 섞여 있는 특정 영역을 채우거나 다시 칠하는 방식으로 작동하며, 결과적으로 이미지의 경계가 형성됩니다.
- 테두리가 있고 색상별로 구분된 영역을 가진 그림에서 특정 내부 색상을 다른 색으로 교체할 때 유용하게 사용됩니다.
- 임의의 새로운 색상으로 내부를 칠할 수 있으며, 기존 픽셀은 새로운 픽셀로 대체됩니다.
- 둘 이상의 경계 색상을 포함하는 이미지도 처리할 수 있는 유연성을 갖추고 있습니다.
- 알고리즘 구조가 비교적 간단하고 직관적이며 효율적입니다.
- 다만 메모리 소비량이 많고, 바운더리 필 알고리즘에 비해 처리 속도가 상대적으로 느린 편입니다.
픽셀 연결 방식: 4-연결과 8-연결
플러드 필 알고리즘에서 픽셀들을 연결해 영역을 확장하는 방법에는 두 가지가 있습니다.
- 4-연결(4-connected) 방식: 하나의 픽셀은 최대 4개의 이웃을 가질 수 있습니다. 이웃 픽셀은 현재 픽셀의 왼쪽, 오른쪽, 위, 아래 위치에 해당합니다.
- 8-연결(8-connected) 방식: 하나의 픽셀은 최대 8개의 이웃을 가질 수 있습니다. 4-연결 방식의 네 방향에 더해 네 개의 대각선 방향 픽셀까지 함께 검사합니다.
8-연결 방식이 더 넓은 범위를 탐색하지만, 그만큼 연산량과 메모리 사용이 증가할 수 있다는 점을 고려해야 합니다.
바운더리 필(Boundary-Fill) 알고리즘이란?
바운더리 필 알고리즘은 경계 색상을 기준으로 영역을 채우는 방식입니다. 경계가 단일 색상으로 이루어져 있을 때, 알고리즘은 경계 색상을 만날 때까지 바깥 방향으로 픽셀 단위로 진행하며 영역을 채웁니다.
- 내부 시작점을 사용자가 쉽게 지정할 수 있는 대화형 그리기 프로그램(페인트 패키지)에서 널리 구현됩니다.
- 알고리즘은 내부 점의 좌표 (x, y), 경계 색상(boundary color), 채우기 색상(fill color)을 입력으로 받는 것으로 시작합니다.
- 시작점 (x, y)에서부터 인접한 픽셀들이 경계 색상에 해당하는지 여부를 검사합니다.
- 경계 색상이 아니라면 해당 픽셀을 채우기 색상으로 칠하고, 인접한 픽셀들에 대해 동일한 조건 검사를 반복합니다.
- 경계 색상에 도달할 때까지 모든 픽셀을 검사하면 알고리즘이 종료됩니다.
- 영역이 단일 색상의 경계로 명확하게 정의되어야 하므로, 단일 경계 색상을 가진 이미지만 처리할 수 있습니다.
- 메모리 소비량이 적고 플러드 필 알고리즘보다 처리 속도가 빠릅니다.
- 반면 알고리즘의 구조와 구현은 플러드 필에 비해 상대적으로 복잡합니다.
두 알고리즘의 핵심 차이점 비교
| 구분 | 플러드 필(Flood-Fill) | 바운더리 필(Boundary-Fill) |
|---|---|---|
| 채우기 기준 | 기존 내부 색상(interior color) 기준 | 경계 색상(boundary color) 기준 |
| 경계 색상 수 | 둘 이상의 경계 색상 처리 가능 | 단일 경계 색상만 처리 가능 |
| 메모리 사용량 | 많음 | 적음 |
| 처리 속도 | 상대적으로 느림 | 상대적으로 빠름 |
| 구현 난이도 | 비교적 간단함 | 비교적 복잡함 |
| 주요 활용 분야 | 그림 채우기 도구, 퍼즐 게임(지뢰찾기 등), 이미지 편집 | 대화형 페인팅 프로그램, 폴리곤 내부 채우기 |
마무리
정리하면, 플러드 필 알고리즘은 내부 색상을 기준으로 영역을 채우기 때문에 여러 색상이 섞인 영역도 처리할 수 있는 반면, 바운더리 필 알고리즘은 경계 색상을 기준으로 영역을 채우기 때문에 더 빠르고 메모리 효율적입니다. 두 알고리즘의 특성을 잘 이해하면 이미지 편집 도구나 그래픽 응용 프로그램 개발 시 상황에 맞는 최적의 선택을 할 수 있습니다.