22

私がしたいのは、画面からの入力を写真の形で分析することです。より大きな画像で画像の一部を識別し、より大きな画像内でその座標を取得できるようにしたいと考えています。例：

箱

に配置する必要があります

大局

その結果、全体像では画像の右上隅になり、全体像では部分の左下になります。ご覧のとおり、写真の白い部分は関係ありません。基本的に必要なのは緑のフレームだけです。私のためにこのようなことを行うことができるライブラリはありますか? ランタイムは実際には問題ではありません。

これでやりたいことは、いくつかのランダムなピクセル座標を生成し、その位置で全体像の色を認識して、後で緑色のボックスをすばやく認識することです。また、中央の白いボックスが透明な場合、どのようにパフォーマンスが低下しますか?

単一の答えがないように見えるため、質問はSOで何度か尋ねられました。http://werner.yellowcouch.org/Papers/subimg/index.htmlで解決策を見つけました。残念ながら、それはC ++であり、私は物事を理解していません。SO で Java を実装できればいいのですが。

4

2 に答える 2

27

画像の一致と見なされるものについては、人によってさまざまな要件があることが多いため、一般的にこの問題に答えるのは困難です。提供するテンプレート画像とは異なるサイズまたは向きの画像を検索したい人もいるかもしれません。その場合、スケールまたは回転不変のアプローチが必要です。類似したテクスチャ、機能、または形状を探すなど、さまざまなオプションがありますが、テンプレート画像とまったく同じ位置にある類似した色のピクセルのみを探すアプローチに焦点を当てます。これは、テンプレート マッチングのカテゴリに該当すると思われる例に最も適しているようです。

可能なアプローチ

この場合、問題は相互相関と畳み込みの信号処理の概念に密接に関連しています。これは、非常に高速であるため、 FFTを使用して実装されることがよくあります (その名前です!)。これは、リンク先のアプローチで使用されたものであり、Java のラッパーがあるため、そのような実装を試みるときにFFTWライブラリが役立つ可能性があります。この質問や有名なワルドの質問に見られるように、相互相関の使用は非常にうまく機能します。

もう 1 つのオプションは、すべてのピクセルを比較に使用するのではなく、見つけやすく、固有である可能性が高い特徴のみを使用することです。これには、 SIFTやSURFなどの機能記述子が必要です。両方の画像ですべてのフィーチャを見つけてから、テンプレート画像のフィーチャと同様の位置にあるフィーチャを探す必要があります。このアプローチでは、JavaCVを使用することをお勧めします。

あなたが言及したランダムな推測アプローチは、可能な場合は高速に機能するはずですが、残念ながら、正しい場所の近くで密接に一致する特定の画像の組み合わせでのみ役立つため、一般的には適用できません。

外部ライブラリを使用しない限り、Java で最も単純な方法は、私がブルート フォース アプローチと呼んでいるものですが、少し時間がかかります。力ずくのアプローチでは、探している画像に最もよく一致する部分領域を画像全体から検索するだけです。このアプローチについてさらに説明します。最初に、同じサイズの 2 つの画像の類似性を判断する方法を定義する必要があります。これは、RGB 値の違いの定義を必要とするピクセルの色の違いを合計することで実行できます。

色の類似性

2 つの RGB 値の差を決定する 1 つの方法は、ユークリッド距離を使用することです。

sqrt( (r1-r2)^2 + (g1-g2)^2 + (b1-b2)^2 )

使用できる RGB とは異なる色空間がありますが、サブイメージは (単に視覚的に似ているのではなく) ほぼ同一である可能性が高いため、これは正常に機能するはずです。ARGB 色空間があり、半透明のピクセルが結果にあまり影響を与えたくない場合は、次を使用できます。

a1 * a2 * sqrt( (r1-r2)^2 + (g1-g2)^2 + (b1-b2)^2 )

色に透明度がある場合は、より小さい値になります ( と が 0 から 1 の間であると仮定a1) a2。白い領域の代わりに透過性を使用し、PNG ファイル形式を使用することをお勧めします。これは、画像の色を微妙に歪める非可逆圧縮を使用しないためです。

画像の比較

同じサイズの画像を比較するには、個々のピクセルの差を合計できます。この合計は差の測定値であり、最小の差測定値を持つ画像内の領域を検索できます。画像にサブ画像が含まれているかどうかさえわからない場合はさらに難しくなりますが、これは、差分測定値が高いベスト マッチによって示されます。必要に応じて、サブイメージのサイズと最大可能 RGB 差 (ユークリッド距離と 0 から 1 の RGB 値を持つ sqrt(3)) で除算することにより、差分測定値を 0 と 1 の間に正規化することもできます。 ）。ゼロは同一の一致であり、1 に近いものは可能な限り異なります。

ブルートフォース実装

ブルート フォース アプローチを使用して画像を検索する簡単な実装を次に示します。サンプル画像では、(139,55) の場所が、最も一致する領域の左上の場所であることがわかりました (これは正しいようです)。私のPCで実行するのに約10〜15秒かかり、位置の正規化された差分測定値は約0.57でした. 

 /**
 * Finds the a region in one image that best matches another, smaller, image.
 */
 public static int[] findSubimage(BufferedImage im1, BufferedImage im2){
   int w1 = im1.getWidth(); int h1 = im1.getHeight();
   int w2 = im2.getWidth(); int h2 = im2.getHeight();
   assert(w2 <= w1 && h2 <= h1);
   // will keep track of best position found
   int bestX = 0; int bestY = 0; double lowestDiff = Double.POSITIVE_INFINITY;
   // brute-force search through whole image (slow...)
   for(int x = 0;x < w1-w2;x++){
     for(int y = 0;y < h1-h2;y++){
       double comp = compareImages(im1.getSubimage(x,y,w2,h2),im2);
       if(comp < lowestDiff){
         bestX = x; bestY = y; lowestDiff = comp;
       }
     }
   }
   // output similarity measure from 0 to 1, with 0 being identical
   System.out.println(lowestDiff);
   // return best location
   return new int[]{bestX,bestY};
 }

 /**
 * Determines how different two identically sized regions are.
 */
 public static double compareImages(BufferedImage im1, BufferedImage im2){
   assert(im1.getHeight() == im2.getHeight() && im1.getWidth() == im2.getWidth());
   double variation = 0.0;
   for(int x = 0;x < im1.getWidth();x++){
     for(int y = 0;y < im1.getHeight();y++){
        variation += compareARGB(im1.getRGB(x,y),im2.getRGB(x,y))/Math.sqrt(3);
     }
   }
   return variation/(im1.getWidth()*im1.getHeight());
 }

 /**
 * Calculates the difference between two ARGB colours (BufferedImage.TYPE_INT_ARGB).
 */
 public static double compareARGB(int rgb1, int rgb2){
   double r1 = ((rgb1 >> 16) & 0xFF)/255.0; double r2 = ((rgb2 >> 16) & 0xFF)/255.0;
   double g1 = ((rgb1 >> 8) & 0xFF)/255.0;  double g2 = ((rgb2 >> 8) & 0xFF)/255.0;
   double b1 = (rgb1 & 0xFF)/255.0;         double b2 = (rgb2 & 0xFF)/255.0;
   double a1 = ((rgb1 >> 24) & 0xFF)/255.0; double a2 = ((rgb2 >> 24) & 0xFF)/255.0;
   // if there is transparency, the alpha values will make difference smaller
   return a1*a2*Math.sqrt((r1-r2)*(r1-r2) + (g1-g2)*(g1-g2) + (b1-b2)*(b1-b2));
 }

私は見ていませんが、おそらくこれらの Java 画像処理ライブラリの 1 つも役立つ可能性があります。

速度が本当に重要な場合、最良のアプローチは、外部ライブラリを使用する相互相関または機能記述子を使用した実装になると思います。

于 2012-09-30T14:40:52.357 に答える
9

あなたが望むのは、マスク/境界で画像ブロックを見つけることです。

外部ライブラリなしで実行できます。低レベルでは、すべての画像は数値の行列であり、マスクも数値の行列です。大きなマトリックスを線形スキャンして、マスクで定義されたルールに従う領域を見つけることができます。

例：

大きなマトリックス:

1 0 1 1 1 1 
0 1 0 1 0 0
0 0 0 1 1 1
0 1 1 0 0 0

マスク：

1 1 1
1 0 0
1 1 1

このアルゴリズムを適用すると、右上隅の大きな行列で一致するブロックが検出され、開始/終了の行列インデックスが得られ、これらの値をピクセル単位で計算できます。

実際の問題では、数値セットはありません[0, 1]が、はるかに大きくなります-byteたとえば ( [0, 256])。アルゴリズムをより適切に機能させるために、一致とは、正確な数の一致ではなく、+-5 などの偏差があれば可能であることを意味します。

于 2012-09-26T10:10:52.493 に答える