用java查找图片中的图片？ [英] Finding a picture in a picture with java?
问题描述
我想要的是以图片的形式分析来自屏幕的输入。我希望能够在更大的图像中识别图像的一部分，并在更大的图像中获得其坐标。示例：
what i want to to is analyse input from screen in form of pictures. I want to be able to identify a part of an image in a bigger image and get its coordinates within the bigger picture. Example:
必须位于
结果将是大图片中图片的右上角和大图片中左下角的部分。正如你所看到的，图片的白色部分是无关紧要的，我基本上只需要绿色框架。有没有可以为我做这样的事情的图书馆？运行时不是一个问题。
And the result would be the upper right corner of the picture in the big picture and the lower left of the part in the big picture. As you can see, the white part of the picture is irrelevant, what i basically need is just the green frame. Is there a library that can do something like this for me? Runtime is not really an issue.
我想要做的就是生成一些随机像素坐标并识别该位置的大图片中的颜色，以便以后快速识别绿框。如果中间的白框是透明的，那么它会如何降低性能？
What i want to do with this is just generating a few random pixel coordinates and recognize the color in the big picture at that position, to recognize the green box fast later. And how would it decrease performance, if the white box in the middle is transparent?
这个问题在SO上已被多次询问，因为似乎没有一个答案。我发现我在 http://werner.yellowcouch.org/Papers/subimg/找到了解决方案index.html 。不幸的是它在C ++中我并不理解。在SO上实现Java实现会很高兴。
The question has been asked several times on SO as it seems without a single answer. I found i found a solution at http://werner.yellowcouch.org/Papers/subimg/index.html . Unfortunately its in C++ and i do not understand a thing. Would be nice to have a Java implementation on SO.
推荐答案
这个问题很难回答，因为人们对图像匹配的要求通常有不同的要求。有些人可能想要搜索可能具有与他们提供的模板图像不同的大小或方向的图像，在这种情况下需要使用缩放或旋转不变的方法。有各种选项，例如寻找类似的纹理，特征或形状，但我将专注于仅查找与模板图像位于完全相同位置的相似颜色的像素的方法。这似乎最适合您的示例，它似乎属于模板匹配类别。
The problem is hard to answer in general because people often have different requirements for what counts as an image match. Some people might want to search for an image that might have a different size or orientation than the template image they provide, in which case a scale- or rotation-invariant approach is needed. There are various option such as looking for similar textures, features or shapes, but I will focus on approaches that only looks for pixels of a similar colour that are in the exact same positions as the template image. This seems most suited to your example which seems to fall in the category of template matching.
在这种情况下，问题与互相关和卷积，通常使用 FFT 实现，因为它非常快（它的名字！）。这是您链接的方法中使用的内容，以及 FFTW 库在尝试这样的实现时可能会有用，因为它有Java包装器。使用互相关非常有效，如这个问题，以及着名的 waldo 问题。
In this case the problem is closely related to the signal processing concepts of cross-correlation and convolution, which is often implemented using an FFT as it is very fast (its in the name!). This is what was used in the approach you linked to, and the FFTW library could be of use when attempting such an implementation as it has wrappers for Java. Using cross-correlation works quite well, as seen in this question, as well as the famous waldo question.
另一种选择是不使用所有像素进行比较，而是仅使用更容易找到且更有可能的功能独特。这需要一个功能描述符，如 SIFT ， SURF 或其中一个他人的。您需要找到两个图像中的所有要素，然后查找与模板图像中具有相似位置的要素。使用这种方法，我建议您使用 JavaCV 。
Another option is not to use all the pixels for comparison, but rather only the features that are easier to find and more likely to be unique. This would require a feature descriptor like SIFT, SURF or one of many others. You would need to find all the features in both images and then look for features that have similar positions to those in the template image. With this approach I suggest you use JavaCV.
您提到的随机猜测方法应该在可能的情况下快速运行，但遗憾的是它通常不适用，因为它仅对某些在正确位置附近产生紧密匹配的图像组合有用。
The random guessing approach you mentioned should work fast when it is possible, but unfortunately it isn't generally applicable as it will only be useful with certain image combinations that produce a close match near the correct location.
除非你使用外部库，否则Java中最简单的方法就是我称之为暴力方法，尽管它有点慢。蛮力方法仅涉及在整个图像中搜索与您正在寻找的图像最匹配的子区域。我将进一步解释这种方法。首先，您需要定义如何确定两个大小相等的图像之间的相似性。这可以通过对像素颜色之间的差异求和来完成，这需要定义RGB值之间的差异。
Unless you use an external library, the simplest method in Java would be what I would call a brute-force approach, although it is a bit slow. The brute-force approach simply involves searching the whole image for the sub-region that best matches the image you are looking for. I'll explain this approach further. First you need to define how to determine the similarity between two equally sized images. This can be done by summing the differences between the pixel's colours which requires a definition for the difference between RGB values.
确定两个RGB值之间差异的一种方法是使用欧几里德距离：
One way of determining the difference between two RGB values is to use the euclidean distance:
sqrt（（r1-r2）^ 2 +（g1-g2）^ 2 +（b1-b2） ^ 2）
可以使用与RGB不同的颜色空间，但是因为你的子图像很可能接近相同（而不仅仅是视觉上相似），这应该可以正常工作。如果您有ARGB色彩空间，并且您不希望半透明像素影响您的结果，您可以使用：
There are different colour spaces than RGB that can be used, but since your sub-image is most likely near identical (instead of just visually similar), this should work fine. If you have an ARGB colour space and you don't want semi-transparent pixels to influence your results as much, you can use:
a1 * a2 * sqrt（（r1-r2）^ 2 +（g1-g2）^ 2 +（b1-b2）^ 2）
如果颜色具有透明度，则会给出较小的值（假设 a1 和 a2 介于0和1之间。我建议您使用透明度而不是白色区域并使用PNG文件格式，因为它不会使用有损地压缩图像中的颜色。
which will give a smaller value if the colours have transparency (assuming a1 and a2 are between 0 and 1). I would suggest that you use transparency instead of white areas and to use the PNG file format since it doesn't use lossy compression that subtly distorts the colours in the image.
要比较大小相同的图像，您可以将各个像素之间的差异相加。然后，此总和是差异的度量，您可以使用最低差异度量搜索图像中的区域。如果您甚至不知道图像是否包含子图像，则变得更难，但这将通过具有高差异度量的最佳匹配来指示。如果需要，您还可以将差值度量标准化为介于0和1之间，将其除以子图像的大小和最大可能的RGB差异（squ（3）与欧氏距离和RGB值从0到1 ）。零将是一个相同的匹配，任何接近一个的东西都会尽可能不同。
To compare equally-sized images you can sum the difference between their individual pixels. This sum is then a measure of the difference and you can search for the region in the image with the lowest difference measure. It becomes harder if you don't even know whether the image contains the sub-image, but this would be indicated by the best match having a high difference measure. If you want, you could also normalize the difference measure to lie between 0 and 1 by dividing it by the size of the sub-image and the maximum possible RGB difference (sqrt(3) with the euclidean distance and RGB values from 0 to 1). Zero would then be an identical match and anything close to one would be as different as possible.
这是一个使用强力方法搜索图像的简单实现。使用您的示例图像，它发现位于（139,55）的位置是具有最佳匹配（看起来正确）的区域的左上角位置。在我的电脑上运行大约需要10到15秒，位置的标准差测量值约为0.57。
Here's a simple implementation that uses the brute-force approach to search the image. With your example images it found the location at (139,55) to be the top-left location of the region with the best match (which looks correct). It took about 10 to 15 seconds to run on my PC and the normalized difference measure of the location was around 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图像处理库可以也有一些用处：
I haven't looked, but maybe one of these Java image processing libraries could also be of some use:
- Marvin project
- ImageJ
如果速度非常重要我认为最好的方法是使用互相关或功能描述符的实现使用外部库。
If speed is really important I think the best approach would be an implementation using cross-correlation or feature descriptors that uses an external library.
这篇关于用java查找图片中的图片？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
