Sort border pixels of images by their order in the image
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

This is an example for an image border - https://d.pr/free/i/XAW58T

The function will get a list of all the pixels coords in the image (each pixel is represented by [x,y]) and will output the same list but the pixels will be ordered by their place on the digit/image areas borders paths.

By the path order I mean by the order that we humans will describe if we will be asked to start following the border with our fingers from start to finish.

Few points that needs to be addressed:

  1. In the example image, one pixel would appear twice in the output list (https://d.pr/free/i/wtTlBM the pixel is highlighted in red) because this highlighted pixel comes up twice when you follow the path around the digit.

  2. An image can have few areas with border, this image has 2 areas. each area should be a separate list of ordered pixel.

  3. It does not matter who will be the first pixel in the list.

  4. You can use every language (preferably cpp or python) and every open source package.

  5. Be aware that not always the nearest pixel to one of the border pixels is the next one in the path, there can be a situation where there are few nearest pixels and the chosen pixel should be the one who is really the next one on the path.

Edit: here are examples of images:

https://d.pr/free/f/cYN94z

awarded to CyteBode

Crowdsource coding tasks.

1 Solution


Dependencies

  • Python 2.7 or 3 (tested with 2.7 and 3.6)
  • Pillow (PIL might work too)

Assumptions

  • The image has 1:1 pixels and exactly two colors, one for the background and one for the borders.
  • Separate borders neither overlap nor touch each other, but a given border can overlap with itself or touch itself.
  • A zone of pixels contained within a border is continuous so it can't be broken down in multiple parts by the border.
  • The borders never have outer corners, but they can have inner corners.

Code

from PIL import Image, ImageDraw
import math
import random


def four_neighbors(img, coord):
    if (coord[1] > 0):
        yield (coord[0]    , coord[1] - 1) # N
    if (coord[1] < img.height - 1):
        yield (coord[0]    , coord[1] + 1) # S
    if (coord[0] < img.width - 1):
        yield (coord[0] + 1, coord[1]    ) # E
    if (coord[0] > 0):
        yield (coord[0] - 1, coord[1]    ) # W


def eight_neighbors(img, coord):
    if (coord[0] > 0):
        yield (coord[0] - 1, coord[1]    ) # W
        if (coord[1] < img.height - 1):
            yield (coord[0] - 1, coord[1] + 1) # SW
    if (coord[1] > 0):
        yield (coord[0]    , coord[1] - 1) # N
        if (coord[0] > 0):
            yield (coord[0] - 1, coord[1] - 1) # NW
    if (coord[0] < img.width - 1):
        yield (coord[0] + 1, coord[1]    ) # E
        if (coord[1] > 0):
            yield (coord[0] + 1, coord[1] - 1) # NE
    if (coord[1] < img.height - 1):
        yield (coord[0]    , coord[1] + 1) # S
        if (coord[0] < img.width - 1):
            yield (coord[0] + 1, coord[1] + 1) # SE


def get_border_pixels(img):
    img = img.convert("P", palette=Image.ADAPTIVE, colors=2)
    acc = img.load()

    # Partition the pixels by color and measure the connectedness
    pixels = [set(), set()]
    connectedness = [0, 0]
    for y in range(img.height):
        for x in range(img.width):
            color = acc[x, y]
            pixels[color].add((x, y))

            connected = 0
            for nc in eight_neighbors(img, (x, y)):
                if acc[nc] == color:
                    connected += 1
            connectedness[color] += connected

    # Divide the connectedness by the number of pixels to get an average
    for color, coords in enumerate(pixels):
        connectedness[color] = float(connectedness[color]) / len(coords)

    # Take the less connected group of pixels as the border
    color = sorted([0, 1], key = lambda c: connectedness[c])[0]
    # Background pixels typically have 8 neighbors whereas border pixels
    # typically only have 2, so the less connected group should be the borders
    return list(pixels[color])


def get_borders(img, border_pixels):
    BG_COLOR = (0x00, 0x00, 0x00)
    ZN_COLOR = (0x80, 0x80, 0x80)
    FG_COLOR = (0xFF, 0xFF, 0xFF)

    def prepare_image(img, border_pixels):
        img = img.convert("P", palette=Image.ADAPTIVE, colors=2)
        acc = img.load()

        # Determine whether the foreground is index 1 or 0 and
        # set the palette accordinly
        if (acc[border_pixels[0]] == 1):
            PALETTE = ZN_COLOR + FG_COLOR
            bg_index = 0
        else:
            PALETTE = FG_COLOR + ZN_COLOR
            bg_index = 1
        img.putpalette(PALETTE)

        # Expand the image by 1 pixel on all side so the background is always
        # connected to (0, 0) no matter what
        expanded = Image.new("P", (img.width+2, img.height+2), bg_index)
        expanded.putpalette(PALETTE)
        expanded.paste(img, (1, 1))

        img = expanded.convert("RGB")
        ImageDraw.floodfill(img, (0, 0), BG_COLOR)

        # Offset the coordinates by (1, 1)
        return (img, [(px[0]+1, px[1]+1) for px in border_pixels])

    def fill_zones(img):
        zones = set()
        acc = img.load()

        def random_color():
            while True:
                color = tuple(random.randint(0x00, 0xFF) for _ in range(3))
                if (color not in (BG_COLOR, ZN_COLOR, FG_COLOR) and
                    color not in zones):
                   return color

        # Horizontal scan
        for y in range(img.height):
            last_color = BG_COLOR
            last_fill = None
            for x in range(img.width):
                color = acc[x, y]
                if color != FG_COLOR and last_color != color:
                    if color == ZN_COLOR:
                        # New zone
                        if last_color == BG_COLOR:
                            # Inside
                            color = random_color()
                            zones.add(color)
                            last_fill = ((x, y), color)
                        else:
                            # Outside
                            color = BG_COLOR
                        ImageDraw.floodfill(img, (x, y), color)
                        last_color = color
                    elif color != BG_COLOR:
                        # Old zone
                        if last_color != BG_COLOR:
                            # Invalid transition
                            if color != last_color and last_fill:
                                xy, old_color = last_fill
                                zones.remove(old_color)
                                ImageDraw.floodfill(img, xy, BG_COLOR)
                                last_fill = None
                    last_color = color

        return zones

    def pixels_by_zone(img, border_pixels, zones):
        acc = img.load()

        border_pixels = set(border_pixels)
        by_zone = dict((zone_color, set()) for zone_color in zones)
        remaining = set(border_pixels)

        # Attach the pixels to the zone they are 4-connected to
        for px in border_pixels:
            for nc in four_neighbors(img, px):
                color = acc[nc]
                if color in by_zone:
                    by_zone[color].add(px)
                    if px in remaining:
                        remaining.remove(px)
                    continue

        # Attach the remaining pixels to the background zone
        for px in remaining:
            by_zone.setdefault(BG_COLOR, set()).add(px)

        return by_zone

    # Prepare the image and the border pixels (offset by (1, 1))
    img, border_pixels = prepare_image(img, border_pixels)

    # Fill the zones and attach the border pixels to their zone
    by_zone = pixels_by_zone(img, border_pixels, fill_zones(img))

    acc = img.load()
    borders = []
    for zone_color, pixels in by_zone.items():
        pixels = set(pixels)

        while pixels:
            border = []

            # Find an appropriate start coordinate for the wall follower
            fc = None
            for px in pixels:
                if   acc[px[0]    , px[1] + 1] == zone_color:   #   |  |  
                    fc = (2*(px[0]    )    , 2*(px[1] + 1)    ) #   | 2|  
                elif acc[px[0] + 1, px[1]    ] == zone_color:   # --+--+--
                    fc = (2*(px[0] + 1)    , 2*(px[1]    ) + 1) #  3|XX|  
                elif acc[px[0]    , px[1] - 1] == zone_color:   #   |XX|1 
                    fc = (2*(px[0]    ) + 1, 2*(px[1] - 1) + 1) # --+--+--
                elif acc[px[0] - 1, px[1]    ] == zone_color:   #   |0 |  
                    fc = (2*(px[0] - 1) + 1, 2*(px[1]    )    ) #   |  |  
                if fc is not None:
                    border.append(px)
                    break

            if fc is None:
                # Could not find a good coordinate to start the wall follower
                break

            # Left-handed wall-following in 2x coordinates
            start = fc
            while True:
                if fc[0] % 2 == 0:
                    if fc[1] % 2 == 0: # 0 0 (Upper-left)
                        side = ((fc[0]    ) // 2, (fc[1] - 1) // 2) # Up
                        if side in pixels:
                            fc = (fc[0] + 1, fc[1]) # Right
                        else:
                            fc = (fc[0], fc[1] - 1) # Up
                    else:              # 0 1 (Lower-left)
                        side = ((fc[0] - 1) // 2, (fc[1]    ) // 2) # Left
                        if side in pixels:
                            fc = (fc[0], fc[1] - 1) # Up
                        else:
                            fc = (fc[0] - 1, fc[1]) # Left
                else:
                    if fc[1] % 2 == 0: # 1 0 (Upper-right)
                        side = ((fc[0] + 1) // 2, (fc[1]    ) // 2) # Right
                        if side in pixels:
                            fc = (fc[0], fc[1] + 1) # Down
                        else:
                            fc = (fc[0] + 1, fc[1]) # Right
                    else:              # 1 1 (Lower-right)
                        side = ((fc[0]    ) // 2, (fc[1] + 1) // 2) # Down
                        if side in pixels:
                            fc = (fc[0] - 1, fc[1]) # Left
                        else:
                            fc = (fc[0], fc[1] + 1) # Down

                # Add the side pixel if it's valid
                if side in pixels and border[-1] != side:
                    border.append(side)

                if fc == start:
                    break

            # Remove the last pixel if it's the same as the first
            if len(border) > 1 and border[0] == border[-1]:
                border.pop(-1)

            # Reverse the borders that are attached to BG_COLOR as they're
            # actually outside
            if zone_color == BG_COLOR:
                border.reverse()

            # Un-offset the coordinates by (1, 1)
            borders.append([(px[0]-1, px[1]-1) for px in border])
            pixels = pixels.difference(set(border))

    return borders


def main():
    import itertools

    # Load the image
    img = Image.open("digit_problem9.png")

    # The border pixels can also be supplied manually
    border_pixels = get_border_pixels(img)
    borders = get_borders(img, border_pixels)

    # Pretty-print the output
    for i, border in enumerate(sorted(borders, key = lambda b: len(b))):
        print("Border %d:" % (i + 1))
        for coord in border:
            print("  %s" % (coord,))
        print("")


    def draw_arrow(img, draw, start, end, color, arrow_sz = None):
        if arrow_sz is None:
            arrow_sz = (1, 4)

        v = (end[0] - start[0], end[1] - start[1])
        length = math.sqrt(v[0]*v[0] + v[1]*v[1])
        angle = math.atan2(v[1], v[0]) * 180.0 / math.pi + 180.0

        start = (int(round(start[0] + v[0]*0.1)),
                 int(round(start[1] + v[1]*0.1)))
        end   = (int(round(start[0] + v[0]*0.8)),
                 int(round(start[1] + v[1]*0.8)))
        draw.line((start, end), color, arrow_sz[0])

        end = (int(round(start[0] + v[0]*0.9)),
               int(round(start[1] + v[1]*0.9)))
        box = ((int(round(end[0] - arrow_sz[1])),
                int(round(end[1] - arrow_sz[1]))),
               (int(round(end[0] + arrow_sz[1])),
                int(round(end[1] + arrow_sz[1]))))
        draw.pieslice(box, angle - 20, angle + 20, color)

        return img

    # Embiggen the image by some factor for showing the borders with arrows
    F = 63
    H = F // 2

    img = img.convert("RGB")

    # Calculate the brightness of a border pixel to determine the arrow color
    r, g, b = img.getpixel(border_pixels[0])
    if math.sqrt(0.299*r*r + 0.587*g*g + 0.114*b*b) / 255.0 >= 0.5:
        arrow_color = "black"
    else:
        arrow_color = "white"

    bigger = img.resize((img.width*F, img.height*F), Image.NEAREST)
    draw = ImageDraw.Draw(bigger)

    # Draw the borders with arrows
    for border in borders:
        if len(border) > 1:
            # Draw a loop of arrows
            previous = border[0]
            segments_iter = itertools.chain(border[1:], [border[0]])
            for i, next_ in enumerate(segments_iter):
                draw_arrow(bigger, draw, (previous[0]*F+H, previous[1]*F+H),
                                      (   next_[0]*F+H,    next_[1]*F+H),
                           arrow_color, (4, 16))
                previous = next_
        else:
            # Draw a small square
            draw.rectangle((border[0][0]*F+H-4, border[0][1]*F+H-4,
                            border[0][0]*F+H+4, border[0][1]*F+H+4),
                           fill=arrow_color)

    # Downsize the image to achieve supersampling antialiasing
    bigger.resize((img.width*24, img.height*24), Image.BILINEAR).show()


if __name__ == '__main__':
    main()

Result

The borders are output as a list of list of (x, y) coordinates (one sublist per border), in clockwise order for an outside border, and counter-clockwise for an inside border. As an image: https://i.imgur.com/YQlc5BH.png

Border 1:
  (13, 16)
  (12, 16)
  (11, 16)
  (10, 16)
  (9, 15)
  (8, 15)
  (7, 16)
  (6, 15)
  (6, 14)
  (6, 13)
  (6, 12)
  (7, 11)
  (7, 10)
  (8, 9)
  (9, 8)
  (10, 7)
  (11, 6)
  (12, 6)
  (13, 6)
  (14, 6)
  (15, 7)
  (16, 7)
  (17, 7)
  (18, 7)
  (19, 7)
  (20, 7)
  (21, 7)
  (22, 7)
  (23, 7)
  (24, 7)
  (25, 8)
  (26, 9)
  (25, 10)
  (24, 10)
  (23, 10)
  (22, 10)
  (21, 10)
  (20, 9)
  (19, 9)
  (18, 10)
  (17, 10)
  (16, 10)
  (15, 10)
  (14, 10)
  (13, 11)
  (12, 11)
  (11, 11)
  (10, 12)
  (10, 13)
  (11, 13)
  (12, 13)
  (13, 13)
  (14, 13)
  (15, 13)
  (16, 14)
  (17, 14)
  (18, 14)
  (19, 15)
  (20, 16)
  (21, 17)
  (21, 18)
  (21, 19)
  (21, 20)
  (20, 21)
  (19, 22)
  (18, 23)
  (17, 23)
  (16, 24)
  (15, 24)
  (14, 24)
  (13, 24)
  (12, 23)
  (11, 22)
  (10, 22)
  (9, 21)
  (8, 20)
  (7, 19)
  (7, 18)
  (8, 17)
  (9, 18)
  (10, 19)
  (11, 20)
  (12, 20)
  (13, 21)
  (14, 21)
  (15, 21)
  (16, 20)
  (17, 20)
  (18, 19)
  (18, 18)
  (18, 17)
  (17, 17)
  (16, 17)
  (15, 17)
  (14, 16)

Edit 1: Made it so the outside corners that are ignored by the wall following algorithm are added back where they belong (not a problem with the test image). Removed the first pixel being added again at the end of the border list and made it so the arrow drawing part simply reuses the first pixel. Fixed some minor typos.

Edit 2: Fixed the bug that could cause an infinite loop. Added hacks for partial support of borders that are inside another border.

Edit 3: Refined the hacks so it works better with borders within borders. Added support for borders that are just a line (as a degenerate loop).

Edit 4: Added vertical scan to find inner zones (fix for digit_problem9.png). Fixed the wall follower start coordinate finding (fix for 10 and 11). Commented out the outside corner reconnecting code from Edit 1 since none of the examples require it.

Edit 5: Cleaned up the code and added more comments. Made it so the image gets expanded by 1 pixel on all side in order to ensure the background is well connected to (0, 0). Changed get_border_pixels so it takes the average connectedness of the pixels into account instead of the number of pixels. Fixed the scanning algorithm in fill_zones as it didn't make much sense and was incorrectly un-coloring the zones of outer borders inside inner borders. Fixed a small bug that could cause the first pixel to be inserted again at the end of the border (when the start pixel sticks out). Switched from my own flood fill implementation to PIL's undocumented ImageDraw.floodfill. Made four_neighbors and eight_neighbors more efficient, albeit less clear. Removed the palette requirements and formalized the assumptions. Made the graphical rendering look better with supersampling antialiasing.

Edit 6: Fixed a small bug that could rarely cause a pixel where the border overlaps to be skipped (when it's chosen as the start pixel). Cleaned up get_border_pixels and fixed the formatting error at the beginning of the code from the last edit.

Amazing response! great work man. Just a few bugs that needs to be fixed, I uploaded a zip with images that does not have good output (and some get into infinite loop) - https://d.pr/free/f/cYN94z Be aware that one of the image areas does not have to be closed, it can be only a line. Thank you so much :)
yosih 3 months ago
I fixed the infinite loop bug and added a hack so it somewhat works with inner borders, but it's not working well with every example. In order to work properly, I'll have to completely rethink my approach. I don't really agree that the solution was incomplete, considering it wasn't clear in your original specs that the borders could be inside another, or that they could just be a line.
CyteBode 3 months ago
Sorry for the unclear spec. Would adding 50$ will able you to rethink your solution for all those possibilities? Thank you 🙏
yosih 3 months ago
You could tip my current solution or accept it, and I would very much appreciate it. I do have ideas for rethinking my approach and I'm currently tackling one of them.
CyteBode 3 months ago
I've managed to refine my current solution so that it works perfectly with all the problematic images you've provided. The idea I had started tackling turned out to be a dead end; it really is a surprisingly hard problem!
CyteBode 3 months ago
Awesome :) but now the first digit (https://d.pr/free/i/XAW58T) has a small bug in it (3 areas instead of 2), also it would be wonderful if those 3 images https://d.pr/free/f/MzEraZ could work.
yosih 3 months ago
I have a fix for the problem with the first digit, but I'll have to look at what's going on with these three new digits. Could you please award me the bounty? I believe I already did more than enough to deserve it.
CyteBode 3 months ago
Done! I tipped you with additional 50$, it would be great if you could improve the code to solve the additional images :) (digit_problem9.png image should be one area, the path should be aligned with the digit '5' path)
yosih 3 months ago
Thank you very much! Don't worry, I'm on it. I already have digit_problem9.png working and I found out what's going on with the other two.
CyteBode 3 months ago
There you go. I've tested all the digits and it's working as it should for all of them.
CyteBode 3 months ago
Hey, I know it's been nearly a week, but it was bugging me that the solution I gave before involved some ugly hacks that didn't make much sense, just to make things work with the problematic digits. It wasn't hard for me to create images that would produce incorrect results, so the code clearly wasn't very robust. I also found a few minor bugs that were worth fixing. It threw me into some graph coloring rabbit hole, but the revised code should work much better in the general case. I'm still not 100% sure that's it completely correct, but I haven't managed to find an image that makes it break.
CyteBode 2 months ago
Thanks you very much mate, I will check it out :)
yosih 2 months ago