时间戳

首页 > 解决方案 > 如何在二进制图片中“查找线”？

algorithm - 如何在二进制图片中“查找线”？

问题描述

如果所有这些看起来令人困惑，请先道歉。我尽量说清楚。

我班上的一个挑战问题是编写一个在黑白图像上找到线段的程序。这些线条总是一个像素宽，白色背景上的黑色，没有灰度或其他颜色。每个图像最多包含 2 行。我的程序的输出应该是每条线段的起点和终点的坐标（如果有的话）。坐标将始终是整个像素坐标。

图像将由文本文件表示。文件中的一行是图像的一行。行中的每个字符是一个像素。一个像素的值可以是 0 或 1。0 表示该像素不是一条线的一部分（它是白色的）。1 表示，这个像素是一条线的一部分（它是黑色的）。像往常一样，在表示图像时，左上角的像素具有 (0, 0) 坐标。X 轴向右增加，而 Y 轴向下增加。

在常规输入集中，线条不会相互接触或相交。

程序的输出应该为每个图像有一行。该行应以图像的文件名开头，然后是端点的坐标。每个坐标都应该用括号括起来。每个坐标的第一个值应该是 X 位置，第二个是 Y 位置。这些值应该用逗号分隔。坐标应以空格分隔。同一行的两个端点在输出中应相互跟随。

所以我也得到了一组由 1 和 0 组成的“图片”。基本上它看起来像下面这样：

'二进制图片'？

我完全不知道如何从这类问题开始。甚至还有一个奖励部分，他们要求您使程序能够找到相互接触的线条

提前非常感谢！

这是我得到的“图片”之一的样本。它实际上是一个 txt 文件，因为里面的所有内容都是 0 和 1

000000000000000000000000000100000000000000 000000000000000000000000000100000000000000 000000000000000000000000000100000000000000 000000000000000000000000000100000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 0000000000000000000000001000000000000000000000000000000000000000001000000000000000000 0000000000000000000000010000000000000000000 0000000000000000000000000000000000

标签： algorithm

解决方案

如果线条没有相互接触，您可以一个接一个地检查图像中的每个像素。一旦你找到一条线（你还没有看到），你就跟随这条线并记住它。

伪代码中的算法可能如下所示：

list<lines> find_lines(int[][] image) {//here the image is represented as an int array, because it's only numbers
    lines = new empty list //where the entries in this list should be lines consisting of coordinates

    for int y from 0 to image.length {//iterate over each line of the image
        for int x from 0 to image[0].length {//iterate over each column of the image
            if (image[y][x] == 1 && coordinate(x, y) not in lines) {//line that is not known yet
                lines.add(follow_line(image, x, y))//follow the line and add the new line to the list
            }
        }
    }

    return lines
}

line follow_line(int[][] image, int x, int y) {
    line = new empty list of coordinates //the coordinates of all pixels in the line
    new_fields_in_line = new empty list of coordinates //the coordinates of new found pixels in the line

    new_fields_in_line.add(coordinate(x, y)) //add the first known pixel to start the loop

    while (!new_fields_in_line.isEmpty()) {
        line.addAll(new_fields_in_line) //add all fields found to the list of lines

        //find all pixels that are part of the line by finding the ones near the new_fields_in_line coordinates
        next_new_fields = empty list of coordinates
        foreach field in new_fields_in_line {
            if (a pixel near the current field is also a black pixel) { 
                next_new_fields.add(the found pixel)
            }
        }

        new_fields_in_line.clear() //empty the list of new fields
        new_fields_in_line.addAll(next_new_fields)
    }

    return line

像这样的算法将找到图像中的所有线条。之后，您只需以正确的格式打印行。}

推荐阅读