以最小的整个图像变化去除黑线

Question

我有包含多边形的图像。有黑线穿过这些多边形。我需要一种方法来删除这些黑线，同时对多边形进行最少的改动。到目前为止我尝试了什么：

Step 1) parse the image from the top left corner to the bottom right corner(line by line).
Step 2) Loop through each pixel of a line/row.
Step 3) If you encounter a non-black pixel, put the color value of it in 
        a variable (lets call it lastNonBlack). 
Step 4) If you encounter a black pixel, just overwrite it's color value with lastNonBlack.

这就是该算法的问题。在某些情况下，它会分割一个多边形（见第一张图片）或用一条线扩展多边形（见第二张图片）。

然后我尝试了另一种方法，我采用上面像素的颜色，但这也不起作用。不是 "splits" 和 "extensions" 不是水平的而是垂直的。

PS：我使用 Java，因此最好使用 java 解决方案，但由于这是一个算法问题，欢迎任何人:)

edit: 上图是构造实例，给大家展示一下问题所在。我的图像是这样的：

edit2：我用更大的图片替换了能更好地显示问题的图片

Answer 1

您可以尝试对图像进行某种侵蚀。 Select 最适合您的线路类型的 Structure Element。

我会选择两条线，一条垂直，一条水平。要解决您的特定图像，您可以 select 尺寸 3:

[l][c][r]         [t]
            and   [c]
                  [b]

其中 c 是中心像素，l 和 r 分别是您的左右邻居， t 和 b - 顶部和底部.要调整 "bigger" 问题的解决方案，您必须 select 更长的 SE，我会建议 maxBlackLineWidth + 2 （或 +3 这样和是奇数）。

要计算精确的线宽：

For pixel in blackPixel 
    #find the major principle axes of the line
    map(Points) visited = bfs(pixel, depth = k)
    #adjust k depending on predicted line width
    x,y = regressionVector(visited) #direction of vector doesn't matter

    x,y = -y,x #perpendicular to that vector
    loop across (x,y) direction from pixel: count black pixel
    loop across (-x,-y,) direction from pixel: count black pixel
    #the sum of the black pixel is the width, record max

要遍历垂直向量，您可以调整 Bresenham's line algorithm

现在用调整大小的两行遍历你的图像。

For pixel in blackPixels
    rc = redPixelCount(vertical(pixel))
    rc += redPixelCount(horizontal(pixel))
    wc = whitePixelCount(vertical(pixel))
    wc += whitePixelCount(horizontal(pixel))
    pixel = rc > wc ? red : white

如果您的矩形与轴对齐，您可以轻松填充您可能遇到的小边框错误。

Answer 2

欢迎使用算法，我将向您展示如何使用安装在大多数 Linux 发行版上并可用于 OSX 和 Windows 的 ImageMagick。

我的算法是制作一个所有黑色像素都是透明的蒙版，然后将其覆盖在原始图像的中值过滤副本之上。在中值滤波图像中，黑色像素将在每个点处落到已排序像素集的底部，因此永远不会被选为中值，因此只有附近的彩色像素才能成为新的输出像素。然后覆盖黑色像素转换为透明的蒙版图像，以便原始图像中只有黑色像素变得透明，并且在这些地方您可以透过原始图像看到中值过滤的图像。这比听起来容易...

使黑色像素透明：

convert in.png -transparent black mask.png

生成 7x7 邻域中位数的过滤图像

convert in.png -median 7x7 median.png

在经过中值滤波的图像上叠加蒙版，因此经过滤波的图像仅在黑色像素处显示（现在是透明的）

convert median.png mask.png -composite result.png

Answer 3

我会创建一个 "voting" 解决方案。您遍历图像并将黑色像素的颜色更改为该像素附近出现频率最高的颜色。这是一个 "Java code":

class Pixel
{
    private int R;
    private int G;
    private int B;

    //...

    public int getR() { return R; }
    public int getG() { return G; }
    public int getB() { return B; }

    public boolean equalWithPixel(Pixel p)
    {
        return ( (this.getR() == p.getR()) &&
                 (this.getG() == p.getG()) &&
                 (this.getB() == p.getB()) );
    }

    //...
}

class Solution
{
    public static Pixel[][] removeBlackLine(Pixel[][] image)
    {
        //Get size
        int N = image.length;
        int M = image[0].length;

        //Init result
        Pixel[][] result = new Pixel[N][M];

        //Iteration over all pixels
        for (int y = 0; y < N; y++)
        {
            for (int x = 0; x < M; x++)
            {
                //Get pixel value
                int R = image[y][x].getR();
                int G = image[y][x].getG();
                int B = image[y][x].getB();

                //Check color
                if ( (R == 0) && (G == 0) && (B == 0) ) //Black
                {
                    result[y][x] = Solution.neighbourPixel(image, y, x);
                }
                else //Other color
                {
                    result[y][x] = new Pixel(R, G, B);
                }
            }
        }
    }

    private static void neighbourPixel(Pixel[][] image, int y, int x)
    {
        //Init pixel list
        ArrayList<Pixel> pixels = new ArrayList<Pixel>();
        ArrayList<Integer> numbers = new ArrayList<Integer>();

        //Get size
        int N = image.length;
        int M = image[0].length;

        //Check all pixels
        for (int j = y - 1; y <= y + 1; j++)
        {
            //Check index
            if ( (j < 0) || (j >= N) ) continue;

            for (int i = x - 1; i <= x + 1; i++)
            {
                //Check index
                if ( (i < 0) || (i >= M) ) continue;
                if ( (i == x) && (j == y) ) continue;

                //Get pixel
                Pixel pixel = image[j][i];

                //Check that it is black or not
                if ( (pixel.getR() == 0) &&
                     (pixel.getG() == 0) &&
                     (pixel.getB() == 0) )
                     continue;

                //Check pixel
                int index = 0;
                boolean found = false;
                for (Pixel p : pixels)
                {
                    if (p.equalWithPixel(pixel))
                    {
                        found = true;
                        break;
                    }
                    index++;
                }
                if (found)
                    numbers[index] = numbers[index] + 1;
                else
                {
                    pixels.add(pixel);
                    numbers.add(1);
                }
            }
        }

        //Find most freq. pixel
        int imax = -1;
        int max = 0;
        for (int i = 0; i < numbers.length; i++)
        {
            if (numbers[i] > max)
            {
                max = numbers[i];
                imax = i;
            }
        }
        if (imax >= 0)
            Pixel best = pixels[imax];
        else
            Pixel best = new Pixel(0, 0, 0);

        //Return
        return new Pixel(best.getR(), best.getG(), best.getB());
    }
}

Answer 4

Alexandru 走在正确的轨道上。您想要的是更像是 "nearest neighbor" 分类器的东西。如果您对此不熟悉，则意味着您想知道 pixel(x,y) 应该是什么颜色。你看着它周围的像素然后说，这些有什么价值？无论多数是什么 pixel(x,y) 应该是什么。

正如他所说，做一个结构元素，然后做一个最近邻分类器。这是一张包含 3 个示例的图片

让我们看看X。如果我们在像素X（右下角）并且想决定这个像素应该是什么颜色？我们查看它周围的像素并进行小投票。我们这里的结构元素是一个以像素 X 为中心的 7x7 邻域，我们看到它是 green=24, black=7, white = 18 因为大多数像素是绿色像素 X 应该是绿色的。

这很好，下一个问题是我们的结构元素有多大？它应该与线的最大尺寸成正比。我认为应该是 2*max_line_width + 1 加上 1 是为了使它的大小变得奇数（减少有联系的可能性，并防止涂抹）。为什么是这个尺寸？因为它比线大，所以这意味着单线不会对像素产生太大影响。但它足够小，信息仍然与像素相关。让我们看一些例子。

Y 像素（右上）最大线宽=1。像素 Y 应该是什么颜色？ green=8, black=5, white =12 所以 Y 应该是白色的。但这是不正确的，这是尺寸太大时的常见错误。如果我们使用 3x3 邻域，我们会得到这个 green=3,black=3,white=3 你必须以某种方式在这里做出判断。但是你可以看到它不会被错误分类

无论选择什么尺码，边角问题总会有的。查看像素 Z 3x3 Z=黑色，5x5 z=黑色，7x7 z=黑色。所以这个方法并不完美，但效果相当好。

为了讨论另一个形状，alexandru 提到了一个 t 形

它与最近邻算法相同，只是使用了不同的邻域形状，正如您在本例中看到的那样，像素将是黑色的。但正如我们已经看到的，每个 method/shape 都有缺点。祝你好运

Answer 5

我会采用中值过滤方法，下面显示了 C++ 代码。您可以传递一个内核大小 1x1、3x3、5x5、7x7，它会根据您的需要给出不同的结果需要（图像类型）。

//inputImage = std::vector , kernalSize = 3, width = 256, height= 256 //

 std::vector<double> medianFilter(std::vector<double> inputImage, double kernalSize,int width, int height)
    {
       /* Fill all the values to output image */
       vector<double> outImage = inputImage;
      for(int y = kernalSize; y < height - kernalSize; y++)
      {
         for(int x = kernalSize; x < width - kernalSize; x++)
         {
           std::vector<double> tempList;
           for(int i = - kernalSize; i <= kernalSize; i++)
             {
               for(int j = -kernalSize; j <= kernalSize; j++)
                 {
                   double pixelValue = inputImage[(y+j)*width + (x+i)];
                   tempList.push_back(pixelValue);
                 }
             }
            std::sort(tempList.begin(),tempList.end());
            double newPixelValue = tempList[tempList.size()/2];
            outImage[y*width + x] = newPixelValue;
          }
       }   
      return outImage;          
     }

以最小的整个图像变化去除黑线

remove black lines with a minimum change of whole image

algorithm

image

pixel

colors

image-processing