c# - 在图像或笛卡尔平面中寻找负空间

Question

Please Note - This is a Math question essentially. However, i have also tagged C# as this is the language i am working in

总结

我正在寻找一种可以在图像中找到负空间(或空间)的算法(或其名称)。我找到的最接近的Dijkstra's algorithm (这看起来很接近)，但它实际上是实际问题的一个子集。也就是说，通过 笛卡尔平面 遍历每个未填充的坐标(在我的例子中为黑色)以找到 mask 。下面的例子

Dijkstra 算法示例

背景

我需要整理 10 万张包含人工制品的图像。通过清理我的意思是这些事情:

1. 使用边缘检测找到图像中对象的边缘
2. 屏蔽 负空间 这样我就可以将图像背景转换为纯白色
3. 裁剪图像至最佳尺寸。

目前我正在使用 Canny 边缘检测 来查找图像中最重要的部分。我可以很好地裁剪图像(如下所示)，还可以找到所有有问题的图像。但是，我无法找到找到负空间的最佳算法(或其名称)。

---

原图示例

如您所见，图像看起来很干净，但实际上并非如此

---

突出问题的例子

图像背景中有很多伪影，需要将它们移除

---

Canny 边缘检测示例

这在清理图像方面做得很好

---

问题

Dijkstra's algorithms前提是它寻找所有可能的路径，它基本上解决了Travelling Sales man problem

问题是；该算法实际上在称重和距离测量方面做的比我需要做的要多得多，并且当它具有最短路径时(我需要它来完成图像)它会停止。

伪代码

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance
14                                                      // will be selected first
15          remove u from Q 
16          
17          for each neighbor v of u:           // where v is still in Q.
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               // A shorter path to v has been found
20                  dist[v] ← alt 
21                  prev[v] ← u 
22
23      return dist[], prev[]

任何人都可以建议一种算法或将伪代码修改为Dijkstra 算法来实现这一点吗？

Answer 1

问题的答案很简单，就是洪水填充算法。

但是，要解决从图像中清除细微伪影的整个问题，总的解决方案如下。

1. 使用具有适当阈值的 Canny 边缘检测来获取图像中对象的轮廓

2. 使用高斯模糊对 Canny 结果进行足够的模糊处理，这样泛洪就不会溢出

3. 使用泛光填充创建蒙版并将其应用回原始图像

一些适合年轻玩家的陷阱。

• PixelFormats，您需要确保所有内容都使用相同的格式
• 不使用扫描线或锁定像素直接编辑位图
• 尽可能使用并行算法，在这种情况下，洪水填充和模糊是很好的候选者

更新

甚至更快的方法就是使用具有颜色阈值值的Parallel FloodFill

颜色阈值

public static bool IsSimilarColor(this Color source, Color target, int threshold)
{
   int r = source.R - target.R, g = source.G - target.G, b = source.B - target.B;

   return (r * r + g * g + b * b) <= threshold * threshold;
}

并行填充

public static Bitmap ToWhiteCorrection(this Bitmap source, Color sourceColor, Color targetColor, Color maskColor, int threshold, Size tableSize, int cpu = 0)
{
   using (var dbMask = new DirectBitmap(source))
   {
      using (var dbDest = new DirectBitmap(source))
      {
         var options = new ParallelOptions
            {
               MaxDegreeOfParallelism = cpu <= 0 ? Environment.ProcessorCount : cpu
            };

         // Divide the image up
         var rects = dbMask.Bounds.GetSubRects(tableSize);

         Parallel.ForEach(rects, options, rect => ProcessWhiteCorrection(dbMask, dbDest, rect, sourceColor, targetColor, maskColor, threshold));

         return dbDest.CloneBitmap();
      }
   }
}

  private static void ProcessWhiteCorrection(this DirectBitmap dbMask, DirectBitmap dbDest, Rectangle rect, Color sourceColor, Color targetColor, Color maskColor, int threshold)
  {
     var pixels = new Stack<Point>();

     AddStartLocations(dbMask, rect, pixels, sourceColor, threshold);

     while (pixels.Count > 0)
     {
        var point = pixels.Pop();

        if (!rect.Contains(point))
        {
           continue;
        }

        if (!dbMask[point]
              .IsSimilarColor(sourceColor, threshold))
        {
           continue;
        }

        dbMask[point] = maskColor;
        dbDest[point] = targetColor;

        pixels.Push(new Point(point.X - 1, point.Y));
        pixels.Push(new Point(point.X + 1, point.Y));
        pixels.Push(new Point(point.X, point.Y - 1));
        pixels.Push(new Point(point.X, point.Y + 1));
     }
  }

worker

private static void ProcessWhiteCorrection(this DirectBitmap dbMask, DirectBitmap dbDest, Rectangle rect, Color sourceColor, Color targetColor, Color maskColor, int threshold)
{
   var pixels = new Stack<Point>();

   // this basically looks at a 5 by 5 rectangle in all 4 corners of the current rect
   // and looks to see if we are all the source color
   // basically it just picks good places to start the fill
   AddStartLocations(dbMask, rect, pixels, sourceColor, threshold);

   while (pixels.Count > 0)
   {
      var point = pixels.Pop();

      if (!rect.Contains(point))
      {
         continue;
      }

      if (!dbMask[point].IsSimilarColor(sourceColor, threshold))
      {
         continue;
      }

      dbMask[point] = maskColor;
      dbDest[point] = targetColor;

      pixels.Push(new Point(point.X - 1, point.Y));
      pixels.Push(new Point(point.X + 1, point.Y));
      pixels.Push(new Point(point.X, point.Y - 1));
      pixels.Push(new Point(point.X, point.Y + 1));
   }
}

直接位图

public class DirectBitmap : IDisposable
{
   public DirectBitmap(int width, int height, PixelFormat pixelFormat = PixelFormat.Format32bppPArgb)
   {
      Width = width;
      Height = height;
      Bounds = new Rectangle(0, 0, Width, Height);
      Bits = new int[width * height];
      BitsHandle = GCHandle.Alloc(Bits, GCHandleType.Pinned);
      Bitmap = new Bitmap(width, height, width * 4, PixelFormat.Format32bppPArgb, BitsHandle.AddrOfPinnedObject());

      using (var g = Graphics.FromImage(Bitmap))
      {
         g.Clear(Color.White);
      }
   }

   public DirectBitmap(Bitmap source)
   {
      Width = source.Width;
      Height = source.Height;
      Bounds = new Rectangle(0, 0, Width, Height);
      Bits = new int[source.Width * source.Height];
      BitsHandle = GCHandle.Alloc(Bits, GCHandleType.Pinned);
      Stride = (int)GetStride(PixelFormat, Width);

      Bitmap = new Bitmap(source.Width, source.Height, Stride, PixelFormat.Format32bppPArgb, BitsHandle.AddrOfPinnedObject());

      using (var g = Graphics.FromImage(Bitmap))
      {
         g.DrawImage(source, new Rectangle(0, 0, source.Width, source.Height));
      }
   }
   
   ...