Clever Geek Handbook

セグメンテーションアルゴリズムの概要







今年の夏、私は幸運にもイッテスで夏のインターンシップを得ることができました。 画像内のオブジェクトの位置を強調する最新の方法を調査するように依頼されました。 基本的に、そのような方法はセグメンテーションに依存しているため、このコンピュータービジョンの分野に慣れることから仕事を始めました。

画像の分割とは、画像をそれをカバーする多くの領域に分割することです。 セグメンテーションは、多くの分野で使用されます。たとえば、部品の組み立てにおける欠陥を示すための生産、画像の一次処理のための医学、衛星画像から地形図を編集するために使用されます。 そのようなアルゴリズムがどのように機能するかを理解することに興味がある人のために、catへようこそ。 OpenCVコンピュータビジョンライブラリのいくつかのメソッドを見ていきます。



流域セグメンテーションアルゴリズム（WaterShed）











このアルゴリズムは、2つの変数f = I（x、y）の関数として画像を処理します。ここで、 x、yはピクセル座標です。







関数の値は、勾配の強度またはモジュラスです。 最大のコントラストを得るには、画像からグラデーションを取得できます。 勾配の絶対値をOZ軸に沿ってプロットすると、強度差のある場所に隆起が形成され、均質な領域に平野が形成されます。 関数fの最小値を見つけた後、グローバルな最小値で始まる「水」で満たすプロセスがあります。 水位が次のローカル最小値に達するとすぐに、水が満たされ始めます。 2つの領域が結合し始めると、領域の統合を防ぐためにパーティションが構築されます[2]。 人工的に構築されたパーティションによってのみ地域が分離されるまで、水は上昇し続けます（図1）。





図1 水充填イラスト



このようなアルゴリズムは、画像の極小数が少ない場合に役立ちますが、極小数が多い場合は、セグメントへの過剰な分割があります。 たとえば、アルゴリズムを図に直接適用する場合 2、私たちは多くの小さな詳細図を取得します。 3。





図 2.元の画像





図 3. WaterShedアルゴリズムによるセグメンテーション後の画像



細部に対処する方法
細部の余分な部分を取り除くために、最も近い安値に結び付けられるエリアを指定できます。 パーティションは、マーカーのある2つの領域の結合がある場合にのみ構築されます。そうでない場合、これらのセグメントはマージされます。 このアプローチは、過度のセグメンテーションの影響を取り除きますが、図の画像でインタラクティブに示すことができるマーカーを強調するために画像の前処理が必要です。 4、5。





図 4.マーカー付きの画像





図 5.マーカーを使用したWaterShedアルゴリズムを使用したセグメンテーション後の画像



ユーザーの介入なしで自動的に行動したい場合は、たとえばfindContours（）関数を使用してマーカーを選択できますが、ここでも、より良いセグメンテーションのために、小さなアウトラインを図から除外する必要があります。 6.たとえば、輪郭の長さに沿ってしきい値に沿ってそれらを削除します。 または、輪郭を分離する前に、膨張浸食を使用して小さな部品を削除します。





図 6.マーカーとして、特定のしきい値を超える長さの輪郭を使用した



アルゴリズムの結果として、1つのセグメントのピクセルが同じラベルでマークされ、接続された領域を形成する、セグメント化された画像を持つマスクを取得します。 このアルゴリズムの主な欠点は、多数の極小値を持つ画像（複雑なテクスチャと豊富な色の画像）の前処理手順の使用です。



アルゴリズムを実行するサンプルコード： 
Mat image = imread("coins.jpg", CV_LOAD_IMAGE_COLOR); //   Mat imageGray, imageBin; cvtColor(image, imageGray, CV_BGR2GRAY); threshold(imageGray, imageBin, 100, 255, THRESH_BINARY); std::vector<std::vector<Point> > contours; std::vector<Vec4i> hierarchy; findContours(imageBin, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE); Mat markers(image.size(), CV_32SC1); markers = Scalar::all(0); int compCount = 0; for(int idx = 0; idx >= 0; idx = hierarchy[idx][0], compCount++) { drawContours(markers, contours, idx, Scalar::all(compCount+1), -1, 8, hierarchy, INT_MAX); } std::vector<Vec3b> colorTab(compCount); for(int i = 0; i < compCount; i++) { colorTab[i] = Vec3b(rand()&255, rand()&255, rand()&255); } watershed(image, markers); Mat wshed(markers.size(), CV_8UC3); for(int i = 0; i < markers.rows; i++) { for(int j = 0; j < markers.cols; j++) { int index = markers.at<int>(i, j); if(index == -1) wshed.at<Vec3b>(i, j) = Vec3b(0, 0, 0); else if (index == 0) wshed.at<Vec3b>(i, j) = Vec3b(255, 255, 255); else wshed.at<Vec3b>(i, j) = colorTab[index - 1]; } } imshow("watershed transform", wshed); waitKey(0);




MeanShiftセグメンテーションアルゴリズム



MeanShiftは、類似の属性を持つオブジェクトをグループ化します。 類似の特徴を持つピクセルは1つのセグメントに結合され、出力では均一な領域の画像が得られます。







たとえば、ピクセル空間 （x、y）およびRGBピクセルコンポーネントをフィーチャスペースの座標として選択できます。 標識のスペースにピクセルを描いたので、特定の場所に凝縮が見られることがあります。











図 7.（a）標識の2次元空間内のピクセル。 （b）1つの極大値に到達するピクセルは、同じ色に着色されます。 （c） -密度関数、最大値は、ピクセルの最高濃度の場所に対応します。 記事[3]から抜粋した図。



点の凝縮を簡単に記述するために、密度関数が導入されています。

i番目のピクセルの特徴のベクトル、 dは特徴の数、 Nはピクセルの数、 hは滑らかさの原因となるパラメーター、 -コア。 関数の最大値 画像空間標識内のピクセルの集中点に位置します。 1つの極大値に属するピクセルは、1つのセグメントに結合されます。 ピクセルがどの凝縮の中心に属しているかを見つけるために、勾配に沿って歩まなければならないことがわかります 最寄りの極大値を見つけます。



密度関数の勾配推定
密度関数の勾配を推定するには、平均シフトベクトルを使用できます

コアとして OpenCVはYepanechnikovコアを使用します[4]：



単位半径を持つd次元の球の体積です。



は、合計がすべてのピクセルではなく、ベクトルが指し示す点を中心とする半径hの球体に入るピクセルのみを超えることを意味します 標識のスペース[4]。 これは、特に計算量を減らすために導入されました。 半径hのd次元球の体積です。空間座標の半径と色空間の半径を個別に設定できます。 -球に落ちるピクセルの数。 価値 値の推定値と見なすことができます フィールドで 。





したがって、勾配に沿って進むには、値を計算するだけで十分です -平均シフトベクトル。 別のコアを選択すると、平均シフトベクトルが異なって見えることに注意してください。



記号として色でピクセルと強度を選択すると、類似した色を持ち、互いに近くにあるピクセルが1つのセグメントに結合されます。 したがって、フィーチャの別のベクトルを選択した場合、セグメントへのピクセルの結合は既にそれに沿っています。 たとえば、属性から座標を削除すると、空と湖は1つのセグメントと見なされます。これは、属性空間内のこれらのオブジェクトのピクセルが1つの極大値に落ちるためです。



選択するオブジェクトが色の大幅に異なる領域で構成されている場合、 MeanShiftはこれらの領域を1つに結合できず、オブジェクトは複数のセグメントで構成されます。 しかし、雑多な背景に対して色の均一なオブジェクトに対処することは良いことです。 MeanShiftは、移動オブジェクトの追跡アルゴリズムの実装にも使用されます[5]。



アルゴリズムを実行するサンプルコード： 
 Mat image = imread("strawberry.jpg", CV_LOAD_IMAGE_COLOR); Mat imageSegment; int spatialRadius = 35; int colorRadius = 60; int pyramidLevels = 3; pyrMeanShiftFiltering(image, imageSegment, spatialRadius, colorRadius, pyramidLevels); imshow("MeanShift", imageSegment); waitKey(0);


結果：



図 8.元の画像





図 9. MeanShiftアルゴリズムによるセグメンテーション後



セグメンテーションアルゴリズムFloodFill



FloodFill （塗りつぶしまたは塗りつぶし方法）を使用すると、色が均一な領域を選択できます。 これを行うには、初期ピクセルを選択し、元のピクセルを基準にして隣接ピクセルの色を変更する間隔を設定します。 間隔は非対称かもしれません。 アルゴリズムは、指定された範囲内にあるピクセルを1つのセグメントに結合します（1つの色で塗りつぶします）。 出力は、特定の色で塗りつぶされたセグメントと、ピクセル単位の領域になります。



このようなアルゴリズムは、弱い色差のある領域を均一な背景で塗りつぶすのに役立ちます。 FloodFillを使用する1つのオプションは、オブジェクトの破損したエッジを識別することです。 たとえば、均一な領域を特定の色で塗りつぶすと、アルゴリズムが隣接する領域を塗りつぶすと、これらの領域間の境界の整合性が侵害されます。 以下の画像では、塗りつぶされた領域の境界の整合性が保持されていることがわかります。



図 10、11.元の画像といくつかの領域を埋めた後の結果



また、次の写真は、前の画像のいずれかの境界線が損傷した場合のFloodFillのオプションを示しています。





図 12、13.塗りつぶされた領域間の境界の整合性に違反するFloodFillの動作の図解



アルゴリズムを実行するサンプルコード： 
 Mat image = imread("cherry.jpg", CV_LOAD_IMAGE_COLOR); Point startPoint; startPoint.x = image.cols / 2; startPoint.y = image.rows / 2; Scalar loDiff(20, 20, 255); Scalar upDiff(5, 5, 255); Scalar fillColor(0, 0, 255); int neighbors = 8; Rect domain; int area = floodFill(image, startPoint, fillColor, &domain, loDiff, upDiff, neighbors); rectangle(image, domain, Scalar(255, 0, 0)); imshow("floodFill segmentation", image); waitKey(0);


変数「 area 」は、「フラッディング」ピクセルの数を記録します。

結果：





GrabCutセグメンテーションアルゴリズム



これは、オブジェクトを選択するための対話型アルゴリズムです;磁気投げ縄のより便利な代替手段として開発されました（オブジェクトを選択するには、ユーザーがマウスでその周りに円を描く必要がありました）。 アルゴリズムが機能するには、オブジェクトを背景の一部と一緒に長方形（グラブ）で囲むだけで十分です。 オブジェクトは自動的にセグメント化されます（カット）。







オブジェクトだけでなく背景にも多数ある色が境界矩形内にある場合、セグメンテーション中に問題が発生する可能性があります。 この場合、オブジェクト（赤い線）と背景（青い線）に追加のマークを付けることができます。







アルゴリズムのアイデアを検討してください。 ユーザーが背景とオブジェクトにマーカーを配置する必要があるインタラクティブなセグメンテーションGraphCutのアルゴリズムに基づきます。 画像は配列として扱われます。 。 Z-ピクセル強度値、 N-ピクセルの総数。 オブジェクトを背景から分離するために、アルゴリズムは透明度配列の要素の値を決定します 、そして 次の場合、2つの値を取ることができます = 0の場合、ピクセルは背景に属します。 = 1 、次にオブジェクト。 内部パラメーター 前景の強度の分布のヒストグラムと背景のヒストグラムが含まれています。

。

セグメンテーションのタスクは、未知のものを見つけることです 。 エネルギー関数が考慮されます：



さらに、最小エネルギーは最適なセグメンテーションに対応します。



V（a、z） -この用語は、ピクセル間の関係を担当します。 合計は、隣接するピクセルのすべてのペアに渡り、 dis（m、n）はユークリッド距離です。 a n = a mの場合、合計にピクセルのペアが関与することになり、このペアは考慮されません。

-セグメンテーションの品質、つまり 背景からのオブジェクトの分離。



エネルギー関数Eのグローバル最小値を見つけると、透明度の配列が得られます 。 エネルギー関数を最小化するために、画像はグラフとして記述され、グラフの最小セクションが求められます。 GrabCutアルゴリズムのGraphCutとは異なり、ピクセルはRGB空間で表示されるため、ガウス混合（Gaussian Mixture Model-GMM）を使用して色統計を記述します。 OpenCVサンプルgrabcut.cppを実行すると、GrabCutアルゴリズムの動作を確認できます。



既存のアルゴリズムのごく一部のみを検討しました。 画像のセグメンテーションの結果、選択された特性に従ってピクセルが結合される領域が選択されます。 FloodFillは 、均一な色のオブジェクトを塗りつぶすのに適しています。 背景から特定のオブジェクトを分離するタスクは、 GrabCutによって適切に処理されます 。 OpenCVのMeanShift実装を使用する場合、色と座標が近いピクセルがクラスター化されます。 WaterShedは 、シンプルなテクスチャの画像に適しています。 したがって、もちろん、特定のタスクに基づいてセグメンテーションアルゴリズムを選択する必要があります。



参照：



  1. G. Bradski、A。Kaehler Learning OpenCV：OReilly、第2版2013
  2. R.ゴンザレス、R。ウッズデジタル画像処理、モスクワ：テクノスフィア、2005。-1072 p。
  3. D. Comaniciu、P。Meer Mean Shift：特徴空間分析に向けた堅牢なアプローチ。 IEEEトランザクションパターン分析とマシンインテリジェンス、2002年、pp。 603-619。
  4. D. Comaniciu、P。Meer Mean平均シフト分析およびアプリケーション、コンピュータービジョンに関するIEEE国際会議、1999年、vol。 2、pp。 1197。
  5. D. Comaniciu、V。Ramesh、P。Mean Shiftを使用した非剛体オブジェクトのリアルタイムトラッキング、Conference on CVPR、2000、vol。 2、pp。 1-8。
  6. C. Rother、V。Kolmogorov、A。Blake Grabcut-反復グラフカットを使用したインタラクティブな前景抽出、2004
  7. OpenCVサンプル




More articles:


All Articles