尽可能快地获取BufferedImage和BufferedImage部分的平均颜色

Question

我正在尝试在一张图片中查找另一张图片，这是为了桌面自动化。目前，我试图追求速度而非精确度。因此，我决定仅基于相同的平均颜色匹配类似的图像。

举个例子，如果我在我的桌面上选取几个图标：

然后我要搜索最后一个图标（我还在想这是什么文件）：

你可以清楚地看到最可能匹配的内容：

在不同的情况下，这种方法可能行不通。但是当给定图像大小时，它应该是相当可靠和极快的。

我可以将屏幕截图作为BufferedImage对象获取：

MSWindow window = MSWindow.windowFromName("Firefox", false);
BufferedImage img = window.screenshot();
//Or, if I can estimate smaller region for searching:
BufferedImage img2 = window.screenshotCrop(20,20,50,50);

当然，用于搜索图像的图像将从保存在文件中的模板加载：

BufferedImage img = ImageIO.read(...whatever goes in there, I'm still confused...);

我解释了我所知道的一切，这样我们就可以专注于唯一的问题：

• Q：如何在缓冲图像上获得平均颜色？如何在该图像的子矩形上获得平均颜色？

速度是关键。在这种特殊情况下，我认为它比代码可读性更有价值。

- Tomáš Zato

---

你可能想考虑使用积分图像：http://en.wikipedia.org/wiki/Summed_area_table - Rosa Gronchi

这真是太聪明了！每次我开始编程，迟早都要承认数学是天才的。 - Tomáš Zato

Answer 1

我认为无论你做什么，你都需要进行一个 O(wh) 的操作，其中 w 是宽度，h 是高度。

因此，我会发布这个（天真的）解决方案来完成您问题的第一部分，因为我不认为有更快的解决方案。

/*
 * Where bi is your image, (x0,y0) is your upper left coordinate, and (w,h)
 * are your width and height respectively
 */
public static Color averageColor(BufferedImage bi, int x0, int y0, int w,
        int h) {
    int x1 = x0 + w;
    int y1 = y0 + h;
    long sumr = 0, sumg = 0, sumb = 0;
    for (int x = x0; x < x1; x++) {
        for (int y = y0; y < y1; y++) {
            Color pixel = new Color(bi.getRGB(x, y));
            sumr += pixel.getRed();
            sumg += pixel.getGreen();
            sumb += pixel.getBlue();
        }
    }
    int num = w * h;
    return new Color(sumr / num, sumg / num, sumb / num);
}

- k_g

---

你实际上指出的是，我的方法并没有节省太多的处理时间 - 现在似乎直接比较像素会更快，更精确。感谢回答！ - Tomáš Zato

通过对像素进行采样，即仅读取每个第n行中的每个第n个像素，您可以获得一些性能提升。这不会给您完美的结果，但可能快几个数量级。 - Hendrik

Answer 2

有一种常数时间的方法可以找到图像矩形部分的平均颜色，但需要进行线性预处理。在您的情况下，这应该没问题。此方法还可用于查找3D数组中的矩形棱柱体的平均值或任何更高维度的类似问题。我将使用灰度示例，但只需重复该过程即可轻松扩展到3个或更多通道。

假设我们有一个二维数字数组，我们称之为“img”。

第一步是生成一个相同维度的新数组，在该数组中，每个元素都包含原始图像中位于该元素和图像左上角之间的矩形内所有值的总和。

您可以使用以下方法在线性时间内构造这样的图像：

int width = 1920;
int height = 1080;

//source data
int[] img = GrayScaleScreenCapture();
int[] helperImg = int[width * height]

for(int y = 0; y < height; ++y)
{
    for(int x = 0; x < width; ++x)
    {
        int total = img[y * width + x];

        if(x > 0)
        {
            //Add value from the pixel to the left in helperImg
            total += helperImg[y * width + (x - 1)];
        }

        if(y > 0)
        {
            //Add value from the pixel above in helperImg
            total += helperImg[(y - 1) * width + x];
        }

        if(x > 0 && y > 0)
        {
            //Subtract value from the pixel above and to the left in helperImg
            total -= helperImg[(y - 1) * width + (x - 1)];
        }

        helperImg[y * width + x] = total;
    }
}

现在我们可以使用helperImg在常数时间内找到img中给定矩形内所有值的总和：

//Some Rectangle with corners (x0, y0), (x1, y0) , (x0, y1), (x1, y1)
int x0 = 50;
int x1 = 150;
int y0 = 25;
int y1 = 200;

int totalOfRect = helperImg[y1 * width + x1];

if(x0 > 0)
{
    totalOfRect -= helperImg[y1 * width + (x0 - 1)];
}

if(y0 > 0)
{
    totalOfRect -= helperImg[(y0 - 1) * width + x1];
}

if(x0 > 0 && y0 > 0)
{
    totalOfRect += helperImg[(y0 - 1) * width + (x0 - 1)];
}

最后，我们只需将totalOfRect除以矩形的面积即可得到平均值：

int rWidth = x1 - x0 + 1;
int rheight = y1 - y0 + 1;

int meanOfRect = totalOfRect / (rWidth * rHeight);

- Khan Maxfield

Answer 3

这是一个基于k_g的答案的版本，用于具有可调节采样精度（步长）的完整BufferedImage。

public static Color getAverageColor(BufferedImage bi) {
    int step = 5;

    int sampled = 0;
    long sumr = 0, sumg = 0, sumb = 0;
    for (int x = 0; x < bi.getWidth(); x++) {
        for (int y = 0; y < bi.getHeight(); y++) {
            if (x % step == 0 && y % step == 0) {
                Color pixel = new Color(bi.getRGB(x, y));
                sumr += pixel.getRed();
                sumg += pixel.getGreen();
                sumb += pixel.getBlue();
                sampled++;
            }
        }
    }
    int dim = bi.getWidth()*bi.getHeight();
    // Log.info("step=" + step + " sampled " + sampled + " out of " + dim + " pixels (" + String.format("%.1f", (float)(100*sampled/dim)) + " %)");
    return new Color(Math.round(sumr / sampled), Math.round(sumg / sampled), Math.round(sumb / sampled));
}

- IkeC