注釈
多くの場合、画像の塗りつぶしは実用的な作業であり、その本質は画像の特定の領域を塗りつぶすことであり、色で指定されたアウトラインによって制限されます。 そして、すべてがシンプルに思えたが、しばしばゆっくりと曲がった。 この記事では、よく知られているスタックベースのフィルアルゴリズムについて説明し、MatLab擬似コードの実装を提供します。 そのような退屈なトピックを興味深いビデオクリップで埋めようとし、再びMatLabを使用してそれらを取得するプロセスを説明しました。 この記事では、通常の解像度ではこれらの目的のためのhabralogotypeを見つけられなかったため、屋根の上に住んでいるCarlsonを殺します。 MatLabで写真を読み、操作する方法に関する数行のコード。
背景と前提条件
簡単な方法で、順序付けられた座標ペアのセットに連結性または近傍の関係を導入します。 ポイントに4つの近傍がある場合（図1a）と、ポイントに8つの近傍がある場合（図1b）を区別します。
これを行う理由と選択する内容を図2に示します。
図2では、小さな正方形はデジタル画像の条件付きピクセルを表し、黒いピクセルは2つの領域（上部と下部）の境界を表します。 上の白い領域を青いペンキで塗りつぶします。 1つのポイントに4つの隣人だけを入力すると、青い絵の具は黒い境界線を通過せず（図2b）、下の領域は白のままになります.8つの隣人を使用すると、黒い境界線は境界線ではなく、 ふるい -下部領域に塗料をこぼします。
どのような接続を選択しますか？ 平面上では、選択は小さく、4つまたは8つの隣人であり、選択は元の問題の定式化に依存しますが、多次元空間ではすべてがより難しく、想像することさえ不可能であり、記事ではフラットなケースのみを検討します。 この場合、4つの近傍の場合を考慮しますが、これは8つの場合に簡単に拡張できます。
ペイントの私の趣味と表現に合わせて描かれたカールソンの絵は、記事の注釈で何となく曲がっていて、境界線には黒い輪郭があり、色付きの領域があり、白と灰色の点が私の目に印象的ですか？ これは、Carlsonがバイナリカラーではなく、グレーのグラデーションであるために発生しました。 最初に行うことは、この重大な欠陥を削除し、写真を2値化することです。1つのチャネルのみで作業するのに十分です。最初のチャネルは赤にしましょう。
だから：
% //
source_image = imread( 'karlson.bmp' );
% //
gray_image = source_image(:,:,1);
% // 0.5
bim=double(im2bw(gray_image, 0.5));
% //
imagesc(bim);
* This source code was highlighted with Source Code Highlighter .
% //
source_image = imread( 'karlson.bmp' );
% //
gray_image = source_image(:,:,1);
% // 0.5
bim=double(im2bw(gray_image, 0.5));
% //
imagesc(bim);
* This source code was highlighted with Source Code Highlighter .
図3は、スロッパーの足を元の形（図3a）および2値化後（図3b）に示したもので、予想されるように輪郭が薄くなり、黒い点のみで構成され、一部の境界が欠落しています。
次に、2つの充填アルゴリズムを検討しますが、それらを再帰的にプログラムするのではなく（余分なホリバーを生成せず、オーバーフローを回避するため）、再帰をスタックに拡張します。
用語を定義しましょう：
- 開始点 -ユーザーがペイント缶のようにクリックしたピクセル
- 古い色 -塗りつぶされた領域の色
- 新しい色は、塗りつぶした後の領域の色です。
シンプルでスローフィルのアルゴリズム
画像の端も画像の境界と見なされます。
アルゴリズムの本質は単純です。現在の時点で、古い色が新しい色である場合は新しい色に置き換え、新しい場合は何も行いません。 次に、色が古い色に等しい4つの近傍に対して同じ操作を実行します。
本質を示すために、再帰的な実装でソースコードを 1回盗みます 。
//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4( int x, int y, int newColor, int oldColor)
{
if (x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion
floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
* This source code was highlighted with Source Code Highlighter .
//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4( int x, int y, int newColor, int oldColor)
{
if (x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion
floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
* This source code was highlighted with Source Code Highlighter .
Matlabでどのように表示されますか？ そして、ここに方法があります：
%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);
newColor = 0.5; oldColor = 1;
point.x = 48; point.y = 234;
stack = [point];
[wh] = size(bim);
stack_size = [];
mov = avifile( 'karlson_fill2.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
bim(point.x,point.y) = newColor; %
if (point.x+1 <= w && bim(point.x+1,point.y) == oldColor)
newpoint.x = point.x+1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.x-1 > 0 && bim(point.x-1,point.y) == oldColor)
newpoint.x = point.x-1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.y+1 <= h && bim(point.x,point.y+1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y+1;
stack = [stack newpoint];
end;
if (point.y-1 > 0 && bim(point.x,point.y-1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y-1;
stack = [stack newpoint];
end;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
mov = close(mov);
figure; imagesc(bim);
figure; plot(stack_size);
* This source code was highlighted with Source Code Highlighter .
%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);
newColor = 0.5; oldColor = 1;
point.x = 48; point.y = 234;
stack = [point];
[wh] = size(bim);
stack_size = [];
mov = avifile( 'karlson_fill2.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
bim(point.x,point.y) = newColor; %
if (point.x+1 <= w && bim(point.x+1,point.y) == oldColor)
newpoint.x = point.x+1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.x-1 > 0 && bim(point.x-1,point.y) == oldColor)
newpoint.x = point.x-1;
newpoint.y = point.y;
stack = [stack newpoint];
end;
if (point.y+1 <= h && bim(point.x,point.y+1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y+1;
stack = [stack newpoint];
end;
if (point.y-1 > 0 && bim(point.x,point.y-1) == oldColor)
newpoint.x = point.x;
newpoint.y = point.y-1;
stack = [stack newpoint];
end;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
mov = close(mov);
figure; imagesc(bim);
figure; plot(stack_size);
* This source code was highlighted with Source Code Highlighter .
私たちの眉毛が灰色に塗られている間にお茶を飲むことができます。 同時に、提案されたコードは、各反復でスタック占有率のグラフも描画し、それについて説明します。 また、素敵なボーナスコードとして、出力は塗りつぶしを示すビデオクリップでもあります。 Matlab実行可能言語の機能を考慮して、たとえば腹など他のものを注ぐことは有限の時間では不可能なので、眉毛のように小さな詳細を選んだのはなぜですか。
実際に、得られた結果は次のとおりです。スタックの充満度のグラフは、図5の対数座標で示されています。
色付きの眉毛が付いた頭部を図6に示します。この領域を塗りつぶすプロセスを説明するビデオを以下に表示します。 アルゴリズムの動作が非常に遅いことはすべてわかります。図5（X軸は反復数、Y軸は未処理のポイントの数）スタックが空になる速度（対数座標を考慮）を見てください。余分なポイントチェックが多すぎます。 前の段階で浸水したポイントは、次の段階でまだチェックされています。 もちろんこれはダメです。 次に、この不正を排除します！ ビデオファイル-1秒あたり50フレーム。
塗りつぶしアルゴリズム-高速、裏地付き
再帰アルゴリズムの本質：
現在の線を一方の端からもう一方の端まで塗りつぶします。
最初に開始点から上へ、次に下へ。
出発点に戻ります。 開始点の左側に古い色があり、境界線がない場合は、新しい行に記入します。
出発点に戻ります。 開始点の右側に古い色があり、境界線がない場合は、新しい行に記入します。
アルゴリズムコード：
clear all;
%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);
newColor = 0.5; oldColor = 1;
point.x = 17; point.y = 143;
stack = [point];
[wh] = size(bim);
stack_size = []; spanLeft = 0; spanRight = 0;
mov = avifile( 'karlson_fill3.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
y1 = point.y;
%
while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
y1 = y1 + 1;
spanLeft = 0; spanRight = 0;
%
while (y1 < h && bim(point.x,y1) == oldColor)
bim(point.x,y1) = newColor; %
if (spanLeft == 0 && point.x > 0 && bim(point.x-1,y1) == oldColor)
newpoint.x = point.x-1; newpoint.y = y1; stack = [stack newpoint];
spanLeft = 1;
elseif (spanLeft == 1 && point.x > 0 && bim(point.x-1,y1) ~= oldColor)
spanLeft = 0;
end;
if (spanRight == 0 && point.x < w && bim(point.x+1,y1) == oldColor)
newpoint.x = point.x+1; newpoint.y = y1; stack = [stack newpoint];
spanRight= 1;
elseif (spanRight == 1 && point.x < w && bim(point.x+1,y1) ~= oldColor)
spanRight = 0;
end;
y1 = y1 + 1;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
end;
mov = close(mov);
* This source code was highlighted with Source Code Highlighter .
clear all;
%
source_image = imread( 'karlson.bmp' );
%
gray_image = source_image(:,:,1);
% 0.5
bim= double (im2bw(gray_image, 0.5));
%
imagesc(bim);
newColor = 0.5; oldColor = 1;
point.x = 17; point.y = 143;
stack = [point];
[wh] = size(bim);
stack_size = []; spanLeft = 0; spanRight = 0;
mov = avifile( 'karlson_fill3.avi' , 'fps' ,50);
figure;
while (length(stack) ~=0)
point = stack(1);
stack(1) = []; %
y1 = point.y;
%
while (y1 >= 1 && bim(point.x,y1) == oldColor) y1 = y1 - 1; end;
y1 = y1 + 1;
spanLeft = 0; spanRight = 0;
%
while (y1 < h && bim(point.x,y1) == oldColor)
bim(point.x,y1) = newColor; %
if (spanLeft == 0 && point.x > 0 && bim(point.x-1,y1) == oldColor)
newpoint.x = point.x-1; newpoint.y = y1; stack = [stack newpoint];
spanLeft = 1;
elseif (spanLeft == 1 && point.x > 0 && bim(point.x-1,y1) ~= oldColor)
spanLeft = 0;
end;
if (spanRight == 0 && point.x < w && bim(point.x+1,y1) == oldColor)
newpoint.x = point.x+1; newpoint.y = y1; stack = [stack newpoint];
spanRight= 1;
elseif (spanRight == 1 && point.x < w && bim(point.x+1,y1) ~= oldColor)
spanRight = 0;
end;
y1 = y1 + 1;
stack_size = [stack_size length(stack)];
imagesc(bim); colormap gray; axis image;
F = getframe(gca); mov = addframe(mov,F);
end;
end;
mov = close(mov);
* This source code was highlighted with Source Code Highlighter .
図7には、スタック占有率のグラフがありますが、すでに通常の座標になっています。 足を新しい色で塗りつぶす様子を示すビデオを以下に提案します。 同じ方法で行われます-1秒あたり50フレーム。
この場合に見られるように、スタック（図7）は塗りつぶし全体を埋め尽くすことはほとんどなく、より少ない深さで検索することで高速に勝ちました。
おわりに
結論として、私は言いたいです- 美しさは力であるため、このような単純なアルゴリズムでさえ、すべてを説明します。
また、長い記事をおarticleびし、おそらく次の記事の種として
記事へのリンクを提供します。 これは、以前に私が知らなかった非常に興味深い別の非常に高速な塗りつぶしアルゴリズムについて説明しています。 おそらく、このアルゴリズムを詳細に、そしてイラストで分析する自由時間のヒーローがいるでしょう。
誰かがより強力なリソースを持っている場合は、Carlysonの腹を埋めてここにビデオをアップロードすることをお勧めします。そうしないと、ビデオの作成中に我慢できません。 これの利点は、すべてのコードです。