CODEWITHSUNDEEP
algorithm
Andy
Andy

Reputation: 21

how to 'Find lines' in binary picture?

apology first if all these might seem confusing. i try to make it as clear as possible.

One challenge question from my class is to write a program which finds line segments on black and white images. The lines will always be one pixel wide, black on a white background, no grayscale or other colors. Each image will contain up to 2 lines. The output of my program should be the coordinates of the start and end of each line segment if there are any. The coordinates will be always whole pixel coordinates.

The images will be represented by text files. One row in the file is one row of the image. Each character in the row is one pixel. A pixel can have a value of 0 or 1. 0 means, this pixel is not part of a line (it’s white). 1 means, this pixel is part of a line (it’s black). As usual, when representing images, the top-left pixel has (0, 0) coordinates. The X axis increases to the right, whereas the Y axis increases downwards.

In the regular input set the lines will not be touching or intersecting each other.

The output of the program should have one row for each image. The row should begin with the filename of the image, followed by the coordinates of the endpoints. Each coordinate should be surrounded by parentheses. The first value for each coordinate should be the X position, the second the Y position. The values should be separated by comas. The coordinates should be separated by spaces. The two endpoints of the same line should follow each other in the output.

So I also get a set of 'pictures' composed of 1s and 0s. basically it looks like one below:

the 'binary picture'?

I am completely out of any clue how to even start on this kind of question. There is even a bonus part which they ask you to make the program able to find lines which touch each other

Thanks a lot in advance!

Here is a sample of one of the 'picture' I got. it is actually a txt file since everything inside is just 0s and 1s

000000000000000000000000000100000000000000 000000000000000000000000000100000000000000 000000000000000000000000000100000000000000 000000000000000000000000000100000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000001000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000010000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 000000000000000000000000100000000000000000 000000000000000000000001000000000000000000 000000000000000000000001000000000000000000 000000000000000000000001000000000000000000

Upvotes: 1

Views: 311

Answers (1)

Tobias
Tobias

Reputation: 2575

If the lines are not touching each other you can check every pixel in your image one after another. As soon as you find a line (which you have not already seen) you follow this line and remember it.

An algorithm in pseudocode could look like this:

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

An algorithm like this will find all the lines in your image. Afterwards you just have to print the lines in the correct formatt. }

Upvotes: 1

Related Questions