是否有适当的算法来检测图形的背景颜色？ [英] Is there a proper algorithm for detecting the background color of a figure?

问题描述

对于大学，我们已经获得了一项任务，在给定图像的情况下，我们必须识别数字，它们的颜色以及它们内部的像素组的数量。让我解释一下：

For college, we have been given an assignment where, given an image, we have to identify the "figures", their color, and the amount of "pixel-groups" inside them. Let me explain:

上面的图片有一个数字（图片中可能有多个数字，但让我们暂时忘记这一点。）

The image above has one figure (in the image there can be multiple figures, but let us forget about that for now).

• 画布的背景颜色是0,0处的像素（在本例中为黄色）


• 图形的边框颜色为黑色（可以是除画布背景颜色以外的任何颜色）。


• 图形的背景颜色为白色（也可以与画布相同） '背景颜色。。


• 一个数字只能有一种背景颜色。


• 图中有两个像素组。一个是蓝色像素池，另一个是红色池，里面有一些绿色。如您所见，像素组像素的颜色无关紧要（它与图形的背景颜色不同）。重要的是他们有联系（甚至是对角线）。因此，尽管有两种不同的颜色，但无论如何这种群体只被视为一种颜色。


• 如您所见，边界可以像您希望的那样不规则。然而，它只有一种颜色。


• 众所周知，像素组不会碰到边框。


• 我被告知是一个像素组的颜色可以是除图形背景颜色之外的任何颜色。我假设它可以和图的边框颜色（黑色）相同。

• The background color of the canvas is the pixel at 0,0 (in this case, yellow)
• The border color of the figure is black (it can be any color other than the canvas' background color).
• The figure's background color is white (it can also be the same as the canvas' background color).
• A figure can only have one background color.
• There are two pixel groups in the figure. One is a pool of blue pixels, and the other is a pool of red with some green inside. As you can see, it doesn't matter the color of the pixel group's pixels (it is just different than the figure's background color). What matters is the fact that they're in contact (even diagonally). So despite having two different colors, such group is considered as just one anyway.
• As you can see, the border can be as irregular as you wish. It only has, however, one color.
• It is known that a pixel group will not touch the border.
• I was told that a pixel group's colors can be any except the figure's background color. I assume that then it can be the same as the figure's border color (black).

我们已经获得了一个能够服用的课程图像并将它们转换为矩阵（每个元素都是一个表示像素颜色的整数）。

We have been given a class capable of taking images and converting them to a matrix (each element being an integer representing the color of the pixel).

就是这样。我是用Java做的。

And that's it. I'm doing it with Java.

我做了什么

• 遍历矩阵中的每个像素


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


• 请注意 initialPixel 在我提供的图像中是图中左上角的黑色像素。我有目的地在那里进行了明确的说明。


• 我现在的任务是找到图的背景颜色（在这种情况下是白色）。

• Iterate through each pixel in the matrix
• If I find a pixel that is different from the background color, I will assume it belongs to the border of the figure. I will call this pixel initialPixel from now on.
• Note that the initialPixel in the image I provided is that black pixel in the top-left corner of the figure. I made a sharp cut there purposefully to illustrate it.
• My mission now is to find the background color of the figure (in this case white).

但是我找到这样的背景颜色（白色）会遇到很多麻烦。这是我做的最接近的方法，适用于某些情况 - 但不适用于此图像：

But I'm having quite a great deal of trouble to find such background color (white). This is the closest method I did, which worked for some cases - but not with this image:

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

• Since I know the color of the border, I could find the first different color that is to the south of the initialPixel. Did sound like a good idea - it did work sometimes, but it would not work with the image provided: it will return yellow in this case, since initialPixel is quite away from the figure's contents.

假设我确实找到了数字的背景颜色（白色），我的下一个任务就是要意识到存在两个像素图中的组。这个似乎更容易：

Assuming I did find the figure's background color (white), my next task would be to realize that there exist two pixel groups within the figure. This one seems easier:

• 因为我现在知道图的背景颜色（白色），我可以尝试迭代图中的每个像素，如果我找到一个不属于边框并且不属于图形背景的部分，我已经知道有一个像素组。我可以开始一个递归函数来查找与这样的组相关的所有像素并标记它们，以便在将来的迭代中我可以完全忽略这些像素。

我需要什么

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

Yes, my problem is about how to find the figure's background color (keep in mind it can be the same as the whole image's background color - for now it is yellow, but it can be white as well) based on what I described before.

我不需要任何代码 - 我只是在想一个适当的算法。边界可能有这种奇怪的不规则线条的事实让我感到害怕。

I don't need any code - I'm just having trouble thinking a proper algorithm for such. The fact that the border can have such weird irregular lines is killing me.

甚至更好：我一直都做错了吗？也许我不应该如此关注 initialPixel 。也许一种不同的初始方法会起作用？是否有关于此类主题的文档/示例？我意识到有很多关于计算机视觉等的研究，但我对这个特定的问题找不到多少。

Or even better: have I been doing it wrong all along? Maybe I shouldn't have focused so much on that initialPixel at all. Maybe a different kind of initial method would have worked? Are there any documents/examples about topics like this? I realize there is a lot of research on "computer vision" and such, but I can't find much about this particular problem.

一些代码

我检索带有所有数字的向量的函数：
*注意：图是只是一个包含一些值的类，如背景颜色和元素数。

My function to retrieve a vector with all the figures: *Note: Figure is just a class that contains some values like the background color and the number of elements.

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）是我无法做到的。

Then, clearly, the function retrieveFigure(y,x) is what I am being unable to do.

注意：

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

推荐答案

解决此问题的一个好方法是将图像视为图表，每个颜色填充区域都有一个节点（此答案中的组件）。

A good way to solve this problem is to treat the image as a graph, where there is one node ('component' in this answer) for each color filled area.

这是实现此目的的一种方法方法：

Here is one way to implement this approach:

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



2. 对于每个像素，如果如果没有访问像素，请在其上执行泛滥填充算法。在泛洪填充期间，每个连接的像素都会被访问。

1. Mark all pixels as unvisited.

2. For each pixel, if the pixel is unvisited, perform the flood fill algorithm on it. During the flood fill mark each connected pixel as visited.

现在您应该在图像（或组件）中有一个纯色区域列表，所以你只需要弄清楚它们是如何相互连接的：

Now you should have a list of solid color areas in your image (or 'components'), so you just have to figure out how they are connected to each other:

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

Find the component that has pixels adjacent to the background color component - this is your figure border. Note that you can find the background color component by finding the component with the 0,0 pixel.

现在找到与新找到的像素相邻的组件图边框'组件。将有两个这样的组件 - 选择一个不是背景的组件（即没有0​​,0像素）。这是你的数字背景。

Now find the components with pixels adjacent to the newly found 'figure border' component. There will be two such components - pick the one that isn't the background (ie that doesn't have the 0,0 pixel). This is your figure background.

要查找像素组，只需计算与图背景组件相邻的像素数量（当然忽略图边界成分）

To find the pixel groups, simply count the number of components with pixels adjacent to the figure background component (ignoring of course the figure border component)

这种方法的优点：

• 以O（＃像素）时间运行。


• 易于理解和实施。


• 不承担背景颜色和图形背景颜色不同。

确保了解如何迭代组件及其邻居可能有效，这是步骤5的伪代码实现示例：

To make sure you understand how iterating through the components and their neighbors might work, here's an example pseudocode implementation for step 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++;

这篇关于是否有适当的算法来检测图形的背景颜色？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！