C# - 从照片中识别黑点
C# - Black points recognition from a photo
我有一些白页的照片，上面画了一些黑点，像这样：
photo（点不是很圆，我可以画的更好），
我会找到这些点的坐标。
我可以将图像二值化（之前的照片二值化：image），但是如何找到这些黑点的坐标呢？我只需要每个点一个像素的坐标，大概中心点。
这是学校作业。
由于是学业，所以只提供高阶算法。
既然背景保证是白色的，那你走运了。
首先，您需要在要视为黑点颜色的黑色级别上定义一个阈值。
#ffffff为纯白，#000000为纯黑。我会建议一些像 #383838 这样的地方作为你的门槛。
然后你制作一个二维 bool 数组来跟踪你已经访问过的像素。
现在我们可以开始看图了。
你当时横向读取一个像素，看像素是否>阈值。如果是，那么你做一个 DFS 或 BFS 来找到像素的邻居也 > 阈值的整个区域。
在此过程中，您将标记我们之前创建的 bool 数组，以指示您已经访问过该像素。
因为它是一个圆点，你可以只取x和y坐标的最小值，最大值并计算中心点。
完成一个点后，您将继续遍历图片的像素并找到您未访问过的点（bool 数组中为 false）
由于照片上的点在边缘包含一些小点，这些小点未连接到大点，因此您可能需要做一些数学运算以查看半径是否大于某个数字才能认为有效观点。或者你做一个 5 - 10 像素的邻居而不是半径 1 的邻居 BFS/DFS 来包括那些真正靠近主要点的邻居。
可以找到处理图像数据的基础知识 ，所以我不会对此进行更深入的讨论，但是对于具体的阈值检查，我会通过收集红色、绿色和每个像素的蓝色字节（如我 link 编辑的答案所示），然后将它们组合成 Color c = Color.FromArgb(r,g,b) 并使用 c.GetBrightness() < brightnessThreshold 测试它是 "dark"。 0.4 的值是测试图像的一个很好的阈值。
您应该将此阈值检测的结果存储在一个数组中，其中每一项都是一个值，表示阈值检查是通过还是失败。这意味着您可以使用像二维 Boolean 数组一样简单的东西，其中包含原始图像的高度和宽度。
如果你已经有了做这一切的方法，那就更好了。只要确保你有某种数组，你可以在其中轻松查找二值化的结果。如果您使用的方法将结果作为图像提供给您，您将更有可能得到一个简单的一维字节数组，但是您的查找将只是一种格式，如 imagedata[y * stride + x]。这在功能上与二维数组中的内部查找的发生方式相同，因此效率不会降低。
现在，正如我在评论中所说，这里真正的东西是一种算法，用于检测哪些像素应该组合在一起 "blob"。
此算法的一般用法是遍历图像上的每个像素，然后检查 A) 它是否清除了阈值，以及 B) 它是否不在您现有的检测到的斑点之一中。如果像素符合条件，则生成一个新列表，其中包含所有连接到该像素的通过阈值的像素，并将该新列表添加到检测到的斑点列表中。我使用 Point class 来收集坐标，使我的每个斑点成为 List<Point>，而我的斑点集合成为 List<List<Point>>.
至于算法本身，你所做的就是收集两个点。一个是您正在构建的相邻点的完整集合（点列表），另一个是您正在扫描的当前边缘（当前边缘列表). 当前边缘列表 将开始包含您的原点，只要您的当前边缘列表 中有项目，以下步骤就会循环：
- 将当前边缘列表中的所有项目添加到完整的点列表。
- 为您的下一个边缘（下一个边缘列表）创建一个新集合。
- 对于当前边缘列表中的每个点，获取其直接相邻点的列表（不包括任何落在图像边界之外的点），并检查所有这些如果它们清除了阈值，并且它们既不在点列表中，也不在下一个边缘列表中。将通过检查的点添加到下一个边缘列表。
- 在current edge list循环结束后，用next edge替换原来的current edge list列表.
...并且，正如我所说，循环这些步骤，只要您的 当前边缘列表 在最后一步之后不为空。
这将创建一个边缘，该边缘会扩展直到它匹配所有阈值清除像素，并将它们全部添加到列表中。最终，由于所有相邻像素都在主列表中，新生成的边缘列表将变为空，算法将结束。然后将新的 points list 添加到 blob 列表中，之后循环遍历的任何像素都可以被检测为已经在这些 blob 中，因此不会对它们重复该算法。
邻点有两种方法；你要么得到周围的四个点，要么全部八个。不同之处在于，使用四不会使算法进行对角线跳跃，而使用八则会。 （一个附加的效果是，一个导致算法以菱形扩展，而另一个以正方形扩展。）由于您的斑点周围似乎有一些杂散像素，我建议您全部八个。
正如 Steve 指出的那样 ，检查一个点是否存在于集合中的一种非常快速的方法是创建一个二维 Boolean 数组，其维度为图片，例如Boolean[,] inBlob = new Boolean[height, width];，您与实际积分列表保持同步。所以每当你添加一个点时，你也将布尔数组中的 [y, x] 位置标记为 true。这将对 if (collection.contains(point)) 类型进行相当繁重的检查，就像 if (inBlob[y,x]) 一样简单，这需要 根本不需要迭代 .
我有一个 List<Boolean[,]> inBlobs 与我构建的 List<List<Point>> blobs 保持同步，并且在扩展边缘算法中我为 next edge list和points list（后者在末尾添加到inBlobs）。
正如我评论的那样，一旦你有了斑点，只需循环遍历每个斑点内的点，并获得 X 和 Y 的最小值和最大值，这样你就可以得到斑点的边界。然后取这些平均值以获得斑点的中心。
额外内容：
如果保证所有的点都相距很远，消除浮动边缘像素的一种非常简单的方法是获取每个斑点的边缘边界，将它们全部扩展一定阈值（我为此取了 2 个像素），然后遍历这些矩形并检查是否有任何相交，并合并那些相交的矩形。 Rectangle class 既有便于检查的 IntersectsWith()，也有增加矩形大小的静态 Rectangle.Inflate。
您可以通过在主列表中仅存储边缘点（在四个主要方向中的任何一个方向上具有不匹配邻居的阈值匹配点）来优化填充方法的内存使用。最终边界以及中心将保持不变。然后要记住的重要一点是，当你从 blob 列表中排除一堆点时，你 应该 在用于检查的 Boolean[,] 数组中标记所有这些点已经处理过的像素。无论如何，这不会占用任何额外的内存。
完整算法，包括优化，对您的照片起作用，使用 0.4 作为亮度阈值：
蓝色是检测到的斑点，红色是检测到的轮廓（通过使用内存优化方法），单个绿色像素表示所有斑点的中心点。
[编辑]
自从我发布这篇文章已经将近一年了，我想我还不如 link 到 the implementation I made of this. I actually managed to use it myself about a month after I wrote it, when recreating the video compression algorithm of an old DOS game，它使用了分块的 diff 帧。
我有一些白页的照片，上面画了一些黑点，像这样： photo（点不是很圆，我可以画的更好）， 我会找到这些点的坐标。 我可以将图像二值化（之前的照片二值化：image），但是如何找到这些黑点的坐标呢？我只需要每个点一个像素的坐标，大概中心点。
这是学校作业。
由于是学业，所以只提供高阶算法。
既然背景保证是白色的，那你走运了。
首先，您需要在要视为黑点颜色的黑色级别上定义一个阈值。
#ffffff为纯白，#000000为纯黑。我会建议一些像 #383838 这样的地方作为你的门槛。
然后你制作一个二维 bool 数组来跟踪你已经访问过的像素。
现在我们可以开始看图了。
你当时横向读取一个像素，看像素是否>阈值。如果是，那么你做一个 DFS 或 BFS 来找到像素的邻居也 > 阈值的整个区域。
在此过程中，您将标记我们之前创建的 bool 数组，以指示您已经访问过该像素。
因为它是一个圆点，你可以只取x和y坐标的最小值，最大值并计算中心点。
完成一个点后，您将继续遍历图片的像素并找到您未访问过的点（bool 数组中为 false）
由于照片上的点在边缘包含一些小点，这些小点未连接到大点，因此您可能需要做一些数学运算以查看半径是否大于某个数字才能认为有效观点。或者你做一个 5 - 10 像素的邻居而不是半径 1 的邻居 BFS/DFS 来包括那些真正靠近主要点的邻居。
可以找到处理图像数据的基础知识 Color c = Color.FromArgb(r,g,b) 并使用 c.GetBrightness() < brightnessThreshold 测试它是 "dark"。 0.4 的值是测试图像的一个很好的阈值。
您应该将此阈值检测的结果存储在一个数组中，其中每一项都是一个值，表示阈值检查是通过还是失败。这意味着您可以使用像二维 Boolean 数组一样简单的东西，其中包含原始图像的高度和宽度。
如果你已经有了做这一切的方法，那就更好了。只要确保你有某种数组，你可以在其中轻松查找二值化的结果。如果您使用的方法将结果作为图像提供给您，您将更有可能得到一个简单的一维字节数组，但是您的查找将只是一种格式，如 imagedata[y * stride + x]。这在功能上与二维数组中的内部查找的发生方式相同，因此效率不会降低。
现在，正如我在评论中所说，这里真正的东西是一种算法，用于检测哪些像素应该组合在一起 "blob"。
此算法的一般用法是遍历图像上的每个像素，然后检查 A) 它是否清除了阈值，以及 B) 它是否不在您现有的检测到的斑点之一中。如果像素符合条件，则生成一个新列表，其中包含所有连接到该像素的通过阈值的像素，并将该新列表添加到检测到的斑点列表中。我使用 Point class 来收集坐标，使我的每个斑点成为 List<Point>，而我的斑点集合成为 List<List<Point>>.
至于算法本身，你所做的就是收集两个点。一个是您正在构建的相邻点的完整集合（点列表），另一个是您正在扫描的当前边缘（当前边缘列表). 当前边缘列表 将开始包含您的原点，只要您的当前边缘列表 中有项目，以下步骤就会循环：
- 将当前边缘列表中的所有项目添加到完整的点列表。
- 为您的下一个边缘（下一个边缘列表）创建一个新集合。
- 对于当前边缘列表中的每个点，获取其直接相邻点的列表（不包括任何落在图像边界之外的点），并检查所有这些如果它们清除了阈值，并且它们既不在点列表中，也不在下一个边缘列表中。将通过检查的点添加到下一个边缘列表。
- 在current edge list循环结束后，用next edge替换原来的current edge list列表.
...并且，正如我所说，循环这些步骤，只要您的 当前边缘列表 在最后一步之后不为空。
这将创建一个边缘，该边缘会扩展直到它匹配所有阈值清除像素，并将它们全部添加到列表中。最终，由于所有相邻像素都在主列表中，新生成的边缘列表将变为空，算法将结束。然后将新的 points list 添加到 blob 列表中，之后循环遍历的任何像素都可以被检测为已经在这些 blob 中，因此不会对它们重复该算法。
邻点有两种方法；你要么得到周围的四个点，要么全部八个。不同之处在于，使用四不会使算法进行对角线跳跃，而使用八则会。 （一个附加的效果是，一个导致算法以菱形扩展，而另一个以正方形扩展。）由于您的斑点周围似乎有一些杂散像素，我建议您全部八个。
正如 Steve 指出的那样 Boolean 数组，其维度为图片，例如Boolean[,] inBlob = new Boolean[height, width];，您与实际积分列表保持同步。所以每当你添加一个点时，你也将布尔数组中的 [y, x] 位置标记为 true。这将对 if (collection.contains(point)) 类型进行相当繁重的检查，就像 if (inBlob[y,x]) 一样简单，这需要 根本不需要迭代 .
我有一个 List<Boolean[,]> inBlobs 与我构建的 List<List<Point>> blobs 保持同步，并且在扩展边缘算法中我为 next edge list和points list（后者在末尾添加到inBlobs）。
正如我评论的那样，一旦你有了斑点，只需循环遍历每个斑点内的点，并获得 X 和 Y 的最小值和最大值，这样你就可以得到斑点的边界。然后取这些平均值以获得斑点的中心。
额外内容：
如果保证所有的点都相距很远，消除浮动边缘像素的一种非常简单的方法是获取每个斑点的边缘边界，将它们全部扩展一定阈值（我为此取了 2 个像素），然后遍历这些矩形并检查是否有任何相交，并合并那些相交的矩形。
Rectangleclass 既有便于检查的IntersectsWith()，也有增加矩形大小的静态Rectangle.Inflate。您可以通过在主列表中仅存储边缘点（在四个主要方向中的任何一个方向上具有不匹配邻居的阈值匹配点）来优化填充方法的内存使用。最终边界以及中心将保持不变。然后要记住的重要一点是，当你从 blob 列表中排除一堆点时，你 应该 在用于检查的
Boolean[,]数组中标记所有这些点已经处理过的像素。无论如何，这不会占用任何额外的内存。
完整算法，包括优化，对您的照片起作用，使用 0.4 作为亮度阈值：
蓝色是检测到的斑点，红色是检测到的轮廓（通过使用内存优化方法），单个绿色像素表示所有斑点的中心点。
[编辑]
自从我发布这篇文章已经将近一年了，我想我还不如 link 到 the implementation I made of this. I actually managed to use it myself about a month after I wrote it, when recreating the video compression algorithm of an old DOS game，它使用了分块的 diff 帧。