java - 是否有适当的算法来检测图形的背景颜色？

Question

在大学里，我们接到了一项作业，在给定图像的情况下，我们必须识别“图形”、它们的颜色以及其中的“像素组”数量。让我解释:



上图有一个 图 (在图像中可以有多个数字，但让我们暂时忘记这一点)。

Canvas 的背景颜色是 0,0 处的像素(在本例中为黄色)

图形的边框颜色为黑色(可以是 Canvas 背景色以外的任何颜色)。

图形的背景颜色为白色(也可以与 Canvas 的背景颜色相同)。

一个图形只能有一种背景颜色。

图中有两个像素组。一个是蓝色像素池，另一个是内部带有一些绿色的红色像素池。如您所见，像素组像素的颜色无关紧要(它只是与图形的背景颜色不同)。重要的是他们接触(甚至是对角线)这一事实。因此，尽管有两种不同的颜色，但无论如何，这样的组都被视为一种。

如您所见，边框可以随心所欲地不规则。然而，它只有一种颜色。

众所周知，像素组不会接触边界。

有人告诉我，像素组的颜色可以是除图形背景颜色之外的任何颜色。我假设它可以与图形的边框颜色(黑色)相同。

我们得到了一个能够拍摄图像并将它们转换为矩阵的类(每个元素都是一个代表像素颜色的整数)。

就是这样。我正在用 Java 做这件事。

到目前为止我做了什么

遍历矩阵中的每个像素

如果我发现一个与背景颜色不同的像素，我会认为它属于图形的边框。我将把这个像素称为 initialPixel从现在开始。

请注意 initialPixel在我提供的图像中，是图左上角的黑色像素。我故意在那里做了一个锐利的剪裁来说明它。

我现在的任务是找到图形的背景颜色(在本例中为白色)。

但是我很难找到这样的背景颜色(白色)。这是我所做的最接近的方法，它适用于某些情况 - 但不适用于此图像:

因为我知道边框的颜色，所以我可以找到第一个与 不同的颜色。南的initialPixel .听起来是个好主意 - 它有时确实有效，但它不适用于提供的图像:在这种情况下它将返回黄色，因为 initialPixel与图的内容相差甚远。

假设我确实找到了图形的背景颜色(白色)，我的下一个任务是意识到图形中存在两个像素组。这个似乎更容易:

由于我现在知道图形的背景颜色(白色)，我可以尝试遍历图形中的每个像素，如果我找到一个不属于边框且不属于图形背景的像素，我已经可以知道有一个像素组。我可以开始一个递归函数来查找与此类组相关的所有像素并“标记”它们，以便在 future 的迭代中我可以完全忽略此类像素。

我需要什么

是的，我的问题是关于如何根据我之前描述的内容找到图形的背景颜色(请记住，它可以与整个图像的背景颜色相同 - 现在它是黄色，但也可以是白色)。

我不需要任何代码——我只是在想一个合适的算法时遇到了麻烦。边界可以有如此奇怪的不规则线条这一事实让我很伤心。

或者甚至更好:我一直做错了吗？也许我不应该太关注那个 initialPixel根本。也许一种不同的初始方法会起作用？是否有任何关于此类主题的文档/示例？我意识到有很多关于“计算机视觉”等的研究，但我找不到关于这个特定问题的太多信息。

一些代码

我用所有数字检索 vector 的函数:
*注:Figure只是一个包含一些值的类，比如背景颜色和元素数量。

public Figure[] getFiguresFromImage(Image image) {
    Figure[] tempFigures = new Figure[100];
    int numberOfFigures = 0;
    matrixOfImage = image.getMatrix();
    int imageBackgroundColor = matrixOfImage[0][0];
    int pixel = 0;

    for (int y = 0; y < matrixOfImage.length; ++y) {
        for (int x = 0; x < matrixOfImage[0].length; ++x) {
            pixel = matrixOfImage[y][x];
            if (!exploredPixels[y][x]) {
                // This pixel has not been evaluated yet
                if (pixel != imageBackgroundColor ) {
                    // This pixel is different than the background color
                    // Since it is a new pixel, I assume it is the initial pixel of a new figure
                    // Get the figure based on the initial pixel found
                    tempFigures[numberOfFigures] = retrieveFigure(y,x);
                    ++numberOfFigures;
                }
            }
        }   
    }

    // ** Do some work here after getting my figures **

    return null;
}

那么，显然，函数 retrieveFigure(y,x)是我无法做到的。

备注:

出于学习目的，我不应该使用任何外部库。

Answer 1

解决此问题的一个好方法是将图像视为 graph ，其中每个颜色填充区域都有一个节点(本答案中的“组件”)。
这是实现这种方法的一种方法:

将所有像素标记为未访问。

对于每个像素，如果该像素未被访问，则执行 flood fill其上的算法。在洪水填充期间，将每个连接的像素标记为已访问。
现在您应该在您的图像(或“组件”)中有一个纯色区域的列表，所以您只需要弄清楚它们是如何相互连接的:

找到像素与背景颜色组件相邻的组件 - 这是您的图形边框。请注意，您可以通过查找具有 0,0 像素的组件来找到背景颜色组件。

现在找到像素与新发现的“图形边框”组件相邻的组件。将有两个这样的组件 - 选择一个不是背景的组件(即没有 0,0 像素)。这是你的人物背景。

要找到像素组，只需计算与图形背景组件相邻的像素的组件数量(当然忽略图形边框组件)

这种方法的优点:

在 O(# 像素) 时间内运行。

易于理解和实现。

不假设背景颜色和图形背景颜色不同。

为确保您了解迭代组件及其邻居的工作原理，以下是步骤 5 的示例伪代码实现:

List<Component> allComponents; // created in step 2
Component background; // found in step 3 (this is the component with the 0,0 pixel)
Component figureBorder; // found in step 4
List<Component> pixelGroups = new List<Component>(); // list of pixel groups

for each Component c in allComponents:
    if c == background:
        continue;
    for each Pixel pixel in c.pixelList:
        for each Pixel neighbor in pixel.neighbors:
            if neighbor.getComponent() == figureBorder:
                c.isPixelGroup = true;

int numPixelGroups = 0;
for each Component c in allComponents:
    if (c.isPixelGroup)
        numPixelGroups++;