最大限に安定した極限領域

コンピュータビジョンでは、画像内のブロブ検出の方法として、最大安定極値領域（MSER ）技術が使用されています。この技術は、異なる視点から撮影された2つの画像から取得された画像要素間の対応関係を見つけるために、 Matasら^[1]によって提案されました。対応する画像要素を包括的に抽出するこの方法は、ワイドベースラインマッチングに貢献し、ステレオマッチングや物体認識アルゴリズムの改善につながっています。

画像 はマッピングです。次の場合、画像上で極値領域が適切に定義されます。 ${\displaystyle I}$${\displaystyle I:D\subset \mathbb {Z} ^{2}\to S}$

1. ${\displaystyle S}$完全に順序付けられている（全関係、反対称関係、推移的二項関係が存在する）。${\displaystyle \leq }$
2. 隣接関係が定義されています。2 つの点が隣接していることを と表します。${\displaystyle A\subset D\times D}$${\displaystyle pAq}$

領域は の連続した（つまり連結した）部分集合です。（それぞれ に対してのようなシーケンスが存在します。）この定義では、領域に「穴」が含まれる場合があることに注意してください（たとえば、リング状の領域は連結されていますが、その内部の円は の一部ではありません）。 ${\displaystyle Q}$${\displaystyle D}$${\displaystyle p,q\in Q}$${\displaystyle p,a_{1},a_{2},..,a_{n},q}$${\displaystyle pAa_{1},a_{1}Aa_{2},\dots ,a_{n-1}Aa_{n},a_{n}Aq}$${\displaystyle Q}$

(外部) 領域境界 。つまり、 の境界は の少なくとも 1 つのピクセルに隣接しているが には属さないピクセルの集合です。また、「穴」のある領域の場合、領域境界は の連結されたサブセットである必要はありません(リングには交差しない内境界と外境界があります)。 ${\displaystyle \partial Q=\{q\in D\setminus Q:\exists p\in Q:qAp\}}$${\displaystyle \partial Q}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle D}$

極値領域 とは、すべて(最大強度領域) またはすべて (最小強度領域) のいずれかが成り立つ領域です。 が完全に順序付けられている限り、これらの条件をそれぞれ最大強度領域および最小強度領域として再定式化できます。 この形式では、領域とその境界を分ける閾値強度値の概念を使用できます。 ${\displaystyle Q\subset D}$${\displaystyle p\in Q,q\in \partial Q:I(p)>I(q)}$${\displaystyle p\in Q,q\in \partial Q:I(p)<I(q)}$${\displaystyle S}$${\displaystyle \min(I(p))>\max(I(q))}$${\displaystyle \max(I(p))<\min(I(q))}$

最大安定極値領域極値領域上のすべての点の強度が より小さいような極値領域があるとします。すべての正の に対して であることに注意してください。極値領域が最大安定なのは、が で極小値を持つ場合のみです。(ここで は濃度を表します)。は、ここではメソッドのパラメータです。 ${\displaystyle Q_{i}}$${\displaystyle i\in S}$${\displaystyle Q_{i}\subset Q_{i+\Delta }}$${\displaystyle \Delta \in S}$${\displaystyle Q_{i*}}$${\displaystyle |Q_{i+\Delta }\setminus Q_{i-\Delta }|/|Q_{i}|}$${\displaystyle i*}$${\displaystyle |\cdot |}$${\displaystyle \Delta \in S}$

この式は、特定の数のしきい値を超えて安定したままの領域をチェックします。領域が領域よりも大幅に大きくない場合、領域は最大限に安定した領域と見なされます。 ${\displaystyle Q_{i+\Delta }}$${\displaystyle Q_{i-\Delta }}$${\displaystyle Q_{i}}$

この概念は、しきい値設定によってより簡単に説明できます。特定のしきい値を下回るすべてのピクセルは「黒」になり、しきい値以上または同等のすべてのピクセルは「白」になります。ソース イメージが与えられ、各イメージが増加するしきい値 t に対応するしきい値設定結果イメージのシーケンスが生成されると、最初に白いイメージが表示され、次に局所的な強度の最小値に対応する「黒い」スポットが表示され、その後大きくなります。これらの黒い領域のいずれかのサイズが前のイメージと同じ (またはほぼ同じ) 場合、最大限安定した極値領域が見つかります。 ${\displaystyle I_{t}}$${\displaystyle t}$

これらの「黒い」斑点は最終的に融合し、画像全体が黒くなります。シーケンス内のすべての連結コンポーネントの集合は、すべての極値領域の集合です。その意味で、MSERの概念は画像のコンポーネントツリーの概念とリンクしています。^[2]コンポーネントツリーは確かにMSERを実装するための簡単な方法を提供します。^[3]

この文脈における極値領域には、集合が閉じているという 2 つの重要な特性があります...

1. 画像座標の連続的な変換。これはアフィン不変であり、画像が歪んでいたり、ゆがんでいたりしても問題ないことを意味します。
2. 画像強度の単調な変換。このアプローチは、もちろん日光の変化や影の移動などの自然光の影響に敏感です。

領域は、領域内の強度関数と外側の境界によってのみ定義されるため、領域を有用にする多くの重要な特性がもたらされます。広範囲のしきい値にわたって、ローカルな 2 値化は特定の領域で安定しており、以下にリストする特性を持ちます。

• 画像強度のアフィン変換に対する不変性
• 画像領域における隣接関係保存（連続）変換への共変性 ${\displaystyle T:D\to D}$
• 安定性: しきい値の範囲にわたってサポートがほぼ同じである領域のみが選択されます。
• 平滑化を伴わないマルチスケール検出
  では、微細構造と大規模構造の両方が検出されます。ただし、スケールピラミッドでのMSERの検出により、再現性が向上し、スケールの変化にわたる対応の数が増えることに注意してください。^[4]
• 最悪の場合、すべての極値領域の集合は、画像内のピクセル数で列挙することができる。 ^[5]${\displaystyle O(n)}$${\displaystyle n}$

Mikolajczykら^[6]では、 6つの領域検出器（ハリスアフィン、ヘッセアンアフィン、MSER、エッジベース領域、強度極値、および顕著領域）が研究されています。他の5つと比較したMSERのパフォーマンスの概要は次のとおりです。

• 領域密度– 他のものと比較して、MSER は最も多様性に富んでおり、テクスチャのあるぼかしシーンでは約 2600 の領域、光が変化するシーンでは 230 の領域を検出します。多様性は一般的に良好であると考えられています。また、このテストでは MSER の再現性は 92% でした。
• 領域サイズ– MSER は、大きな領域が遮蔽されているか、シーンの平面部分をカバーしていない可能性が高いのに対し、小さな領域を多数検出する傾向があります。ただし、大きな領域の方が一致が若干容易になる場合があります。
• 視点の変更– MSER は、元の画像とテクスチャ モチーフが繰り返される画像の両方で、他の 5 つの領域検出器よりも優れたパフォーマンスを発揮します。
• スケール変更- ヘッセアフィン検出器に続いて、スケール変更と平面回転では MSER が 2 番目になります。
• ぼかし– MSER は、この種の画像の変化に対して最も敏感であることが証明されました。これは、この種の検出が欠けている唯一の領域です。
  ただし、この評価では、ぼかしの下での再現性を向上させることが示されているマルチ解像度検出を使用していないことに注意してください。^[4]
• 光の変化– MSER はこのタイプのシーンで最も高い再現性スコアを示し、他のすべてのシーンでも同様に優れた堅牢性を示しました。

MSERは多くのテストを通じて一貫して最高スコアを獲得し、信頼性の高い領域検出器であることを証明しました。^[6]

Matas らの元のアルゴリズム^[1]はピクセル数です。このアルゴリズムは、まずピクセルを強度でソートすることから始まります。これにはBINSORT を使用し、時間がかかります。ソート後、画像内のピクセルがマークされ、結合検索アルゴリズムを使用して、成長および結合する接続コンポーネントとその面積のリストが維持されます。これには時間がかかります。実際には、これらの手順は非常に高速です。このプロセス中に、強度の関数として各接続コンポーネントの面積が保存され、データ構造が生成されます。2 つのコンポーネントの結合は、小さい方のコンポーネントの存在の終了と、小さい方のコンポーネントのすべてのピクセルが大きい方のコンポーネントへの挿入と見なされます。極値領域では、「最大限に安定している」領域は、しきい値の相対的な変化の関数としての相対的な面積の変化が局所的最小値であるしきい値に対応する領域です。つまり、MSER は、しきい値の広い範囲にわたって局所的な 2 値化が安定している画像の部分です。^{[1] [6]}${\displaystyle O(n\,\log(\log(n)))}$${\displaystyle n\,}$${\displaystyle O(n)\,}$${\displaystyle O(n\,\log(\log(n)))}$

コンポーネントツリーは、画像のしきい値のすべての接続コンポーネントを包含順に並べた集合です。これを計算するための効率的な（重みの範囲に関係なく準線形の）アルゴリズムが存在します。^[2]したがって、この構造は MSER を実装するための簡単な方法を提供します。^[3]

最近では、NisterとSteweniusが、重みが小さな整数である場合に本当に最悪のケースの手法を提案しました。 ^[5]これは実際にははるかに高速です。このアルゴリズムは、Ph.Salembierらのアルゴリズムに似ています。^[7]${\displaystyle O(n)\,}$

このアルゴリズムの目的は、MSER を一致させて画像間の対応点を確立することです。最初に、強度画像 (MSER+) と反転画像 (MSER-) で MSER 領域が計算されます。測定領域は、実際の領域のサイズ、領域の 1.5 倍、2 倍、3 倍にスケールされた凸包など、複数のスケールで選択されます。マッチングは堅牢な方法で実行されるため、領域のプレイメージの乱雑さや非平面性に大きく影響されることなく、大きな領域の独自性を高めるのが適切です。安定した不変記述を持つシーンのほぼ平面のパッチから取得された測定値は、「良好な測定」と呼ばれます。不安定なものや、非平面または不連続面上の測定値は、「破損した測定」と呼ばれます。堅牢な類似性は次のように計算されます。 の各領域について、に最も近い対応する i 番目の測定値を持つ他の画像の領域が検索され、 と のそれぞれが対応していることを示唆する投票が行われます。すべての測定について投票が合計され、確率分析を使用して、「不正な測定」は投票をランダムに分散させる可能性が高いため、「良い測定」を選択できます。領域の重心にRANSAC を適用することで、大まかなエピポーラ幾何学を計算できます。潜在的に一致する領域のペア間のアフィン変換が計算され、対応によって回転までが定義され、回転はエピポーラ線によって決定されます。次に領域がフィルタリングされ、変換された画像の相関がしきい値を超える領域が選択されます。より狭いしきい値でRANSACが再度適用され、最終的なエピポーラ幾何学が8 点アルゴリズムによって推定されます。 ${\displaystyle M_{A}^{i}}$${\displaystyle A,k}$${\displaystyle B_{1},\dots ,B_{k}}$${\displaystyle M_{B_{1}}^{i},\dots ,M_{B_{k}}^{i}}$${\displaystyle M_{A}^{i}}$${\displaystyle B_{1},\dots ,B_{k}}$

このアルゴリズムはここでテストできます（エピポーラまたはホモグラフィジオメトリ制約マッチ）：WBS Image Matcher

Chen は、MSER とCanny エッジを組み合わせて、MSER アルゴリズムをテキスト検出に使用しました。Canny エッジは、ぼやけに対する MSER の弱点に対処するために使用されます。まず、MSER を対象画像に適用して、文字領域を決定します。MSER 領域を強調するため、Canny エッジによって形成された境界の外側にあるピクセルはすべて削除されます。エッジによって提供される後者の分離により、ぼやけたテキストの抽出における MSER の有用性が大幅に向上します。^[8]

テキスト検出における MSER の別の使用法として、グラフ モデルを使用する Shi の研究があります。この方法では、画像に MSER を適用して予備領域を生成します。次に、これらを使用して、ノードとして扱われる各 MSER 間の位置距離と色距離に基づいてグラフ モデルを構築します。次に、コスト関数を使用してノードを前景と背景に分離します。コスト関数の 1 つは、ノードから前景と背景までの距離を関連付けるものです。もう 1 つは、ノードが隣接ノードと大幅に異なる場合にペナルティを課します。これらが最小化されると、グラフがカットされ、テキスト ノードが非テキスト ノードから分離されます。^[9]

一般的なシーンでテキスト検出を可能にするために、ノイマンはさまざまな投影で MSER アルゴリズムを使用しています。グレースケールの強度投影に加えて、赤、青、緑のカラー チャネルを使用して、色は区別できるがグレースケールの強度では必ずしも区別できないテキスト領域を検出します。この方法では、上記の MSER+ および MSER- 関数のみを使用するよりも多くのテキストを検出できます。^[10]

• MSERアルゴリズムは、強度関数の閾値設定を色の勾配に基づく凝集型クラスタリングに置き換えることで、カラー画像に適応されている。 ^[11]
• MSERアルゴリズムは、強度ではなく色に基づいて領域を検出するために使用できます。これは、ChavezによってHSV色空間で赤、緑、青の強度関数を作成することによって行われます。次に、MSERアルゴリズムを5回実行します。3色の疑似強度に対して実行し、次に標準のMSER+およびMSER-関数を使用してグレースケール強度に対して実行します。^[12]
• MSERアルゴリズムは、色分布に対するマハラノビス距離でMSER検出を実行することで、色付きオブジェクトを追跡するために使用できます。 ^[3]
• MSERを複数の解像度で検出することで、ぼやけやスケールの変化に対する堅牢性を向上させることができます。^[4]

• 最大安定極値領域の形状記述子
• 効率的な最大安定極値領域（MSER）追跡
• 最大安定極値領域のための N ツリー分離集合フォレスト
• ビデオ グーグルとビデオ ショットのオブジェクト レベルのグループ化
• FPGA 上で最大安定極値領域のリアルタイム抽出
• 認識とマッチングのための最大限に安定した色領域

• ブロブ検出
• 特徴検出（コンピュータビジョン）

• VLFeat、 C言語のオープンソースコンピュータビジョンライブラリ（ MATLABへのMEXインターフェース付き）、MSERの実装を含む
• OpenCV は、C/ C++のオープンソース コンピュータ ビジョン ライブラリで、線形時間 MSER の実装が含まれています。
• 検出器の再現性研究、Kristian Mikolajczyk バイナリ (Win/Linux で MSER/HarrisAffine を計算...)。彼の再現性研究で使用されたバイナリ。
• 線形時間 MSER 実装、Charles Dubout、ブロブ検出器としての MSER の C++ 実装