I need to find all closed shapes in an image and get coordinates of it. I need this in Python but a explanation on how to do this is also enough. Feel free to answer with Python code if you want though. I already searched a lot on Google and found these two things:
The answer in the first link paints all areas instead of giving me coordinates of closed areas. I don't understand the first answer in the second link and some comments say it doesn't work. The second answer in the second link doesn't work for images like this:
I tried to make my own code too, but it took longer than a second to calculate and it has to be much faster (not really, really fast, but at least faster than 1/10 second).
How can I find these areas?
PS: There are some lines in the images that aren't part of a closed shape.
Here's a function
find_groups that groups each pixel in the image into one of three categories: free, closed and border, along with a function
print_groups to test it in a readable way.
from collections import namedtuple from copy import deepcopy def find_groups(inpixels): """ Group the pixels in the image into three categories: free, closed, and border. free: A white pixel with a path to outside the image. closed: A white pixels with no path to outside the image. border: A black pixel. Params: pixels: A collection of columns of rows of pixels. 0 is black 1 is white. Return: PixelGroups with attributes free, closed and border. Each is a list of tuples (y, x). """ # Pad the entire image with white pixels. width = len(inpixels) + 2 height = len(inpixels) + 2 pixels = deepcopy(inpixels) for y in pixels: y.insert(0, 1) y.append(1) pixels.insert(0, [1 for x in range(width)]) pixels.append([1 for x in range(width)]) # The free pixels are found through a breadth first traversal. queue = [(0,0)] visited = [(0,0)] while queue: y, x = queue.pop(0) adjacent = ((y+1, x), (y-1, x), (y, x+1), (y, x-1)) for n in adjacent: if (-1 < n < height and -1 < n < width and not n in visited and pixels[n][n] == 1): queue.append(n) visited.append(n) # Remove the padding and make the categories. freecoords = [(y-1, x-1) for (y, x) in visited if (0 < y < height-1 and 0 < x < width-1)] allcoords = [(y, x) for y in range(height-2) for x in range(width-2)] complement = [i for i in allcoords if not i in freecoords] bordercoords = [(y, x) for (y, x) in complement if inpixels[y][x] == 0] closedcoords = [(y, x) for (y, x) in complement if inpixels[y][x] == 1] PixelGroups = namedtuple('PixelGroups', ['free', 'closed', 'border']) return PixelGroups(freecoords, closedcoords, bordercoords) def print_groups(ysize, xsize, pixelgroups): ys=  for y in range(ysize): xs =  for x in range(xsize): if (y, x) in pixelgroups.free: xs.append('.') elif (y, x) in pixelgroups.closed: xs.append('X') elif (y, x) in pixelgroups.border: xs.append('#') ys.append(xs) print('\n'.join([' '.join(k) for k in ys]))
Now to use it:
pixels = [[0, 1, 0, 0, 1, 1], [1, 0, 1, 1, 0, 1], [1, 0, 1, 1, 0, 1], [1, 0 ,1 ,1 ,0, 1], [1, 0, 1 ,0 ,1, 1], [1, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1]] pixelgroups = find_groups(pixels) print_groups(7, 6, pixelgroups) print("closed: " + str(pixelgroups.closed))
# . # # . . . # X X # . . # X X # . . # X X # . . # X # . . . # # . . . . . . . . . closed: [(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3), (4, 2)]
You'll notice random dots and streaks are classified as borders. But you can always distinguish between real borders and streaks as follows.
# pseudo code realborders = [i for i in pixelgroups.border if i has an adjacent closed pixel] streaks = [otherwise]