フラッドフィルアルゴリズムとバウンダリフィルアルゴリズムの違いとは?特徴を徹底比較

本記事では、フラッドフィル(Flood Fill)アルゴリズムとバウンダリフィル(Boundary Fill)アルゴリズムの違いについて詳しく解説します。両者ともコンピュータグラフィックスにおける代表的な「領域塗りつぶし」アルゴリズムであり、その最大の違いは、対象となるピクセルが領域の元の色を持っているかどうかという判定基準にあります。

フラッドフィルアルゴリズムとは

フラッドフィルアルゴリズムは、「シードフィル(Seed Fill)アルゴリズム」とも呼ばれます。多次元配列上で、指定されたノード(開始点)に連結された領域全体を計算し、塗りつぶす手法です。

主な特徴

• 内部に複数の色が含まれる特定の領域を、まとめて塗りつぶし・再着色する方式である
• 境界線を持ち、色ごとに分かれた領域からなる画像に対して適用される
• 特定の内部色を別の色に置き換えることで、目的の部分を着色できる
• メモリ消費量は比較的多い
• アルゴリズム自体は比較的シンプルで理解しやすい
• 複数の境界色を含む画像でも処理可能
• バウンダリフィルアルゴリズムと比べると処理速度はやや遅い
• 内部は任意の色で塗りつぶすことができ、既存のピクセル色が新しい色に置き換えられる
• 全体的に見て効率の良いアルゴリズムである

ピクセルの連結方法(4近傍と8近傍)

フラッドフィルでは、隣接するピクセル同士をつなげて領域を定義します。その連結方法には以下の2種類があります。

• 4近傍方式(4-connected):各ピクセルは最大4つの隣接ピクセルを持ちます。隣接位置は現在のピクセルの「左・右・上・下」の4方向です。
• 8近傍方式(8-connected):各ピクセルは最大8つの隣接ピクセルを持ちます。上下左右に加え、4つの対角方向のピクセルも隣接判定の対象となります。

バウンダリフィルアルゴリズムとは

バウンダリフィルアルゴリズムは、境界線の色を基準として領域を塗りつぶす手法です。境界が単一色で構成されている場合、アルゴリズムは境界色に到達するまで、1ピクセルずつ外側へと処理を進めていきます。

主な特徴

• 内部点を簡単に指定できるインタラクティブなペイントソフトウェアで広く利用されている
• 内部点の座標(x, y)、境界色、塗りつぶし色の3つを入力として受け取ることから処理が始まる
• 起点(x, y)から隣接するピクセルを順に調べ、それが境界色かどうかを判定する
• 境界色でない場合は塗りつぶし色で描画し、さらにその隣接ピクセルに対して同じ判定を繰り返す
• 境界色までのすべてのピクセルのチェックが完了した時点で処理が終了する
• 領域は単一色の境界線によって定義される
• メモリ消費量は比較的少ない
• フラッドフィルアルゴリズムよりも高速に動作する
• その反面、フラッドフィルアルゴリズムよりも実装が複雑
• 処理できるのは単一の境界色を持つ画像のみ

両者の違いのまとめ

このように、フラッドフィルは「内部の色」を手がかりに柔軟に領域を認識できる一方、バウンダリフィルは「境界の色」を基準に高速かつ省メモリで動作します。用途や画像の特性に応じて、適切なアルゴリズムを選択することが重要です。