answer_59.py: result is wrong for some picture

[supernatural]

This is a random generated 8x8 picture, the generated picture (1900% scaled) is wrong: pixel (0,5) is marked as green which should be red.

[supernatural]

A script to generate random picture and verify the result.

#!/usr/bin/env python3
# -*- encoding: utf-8 -*-

import cv2
import numpy as np

def check(img):
    H,W = img.shape
    # verify if result is correct
    for i in range(1,H-1):
        for j in range(1,W-1):
            if img[i,j] != 0:
                v = [img[i-1,j-1],img[i-1,j],img[i-1,j+1]
                    ,img[i,j-1],img[i,j],img[i,j+1]
                    ,img[i+1,j-1],img[i+1,j],img[i+1,j+1]]
                big = max(v)
                small = min(v, key=lambda x : x if x != 0 else 65535)
                if big != small:
                    print("invalid area",i,j,",big:",big,"small:",small)
                    exit()

def labeling_8b(image):
    H,W = image.shape

    img = np.zeros((H+2,W+2)).astype(np.int)
    img[1:H+1,1:W+1] = image[:,:]
    lookup_table = set()
    id = 1

    for i in range(1,H+1):
        for j in range(1,W+1):
            if img[i,j] != 0:
                v = [img[i-1,j], img[i,j-1], img[i-1,j-1],img[i-1,j+1]]
                big = max(v)
                small = min(v, key=lambda x: x if x != 0 else 65535)
                if big == 0:
                    img[i,j] = id
                    id += 1
                    if id == 255:
                        id += 1
                else:
                    img[i,j] = small
                    for s in [x for x in v if x > small]:
                        lookup_table.add((s, small))

    flat_table = []
    for (big, small) in lookup_table:
        Found = False
        blist = None
        index = len(flat_table)-1
        while index >= 0:
            alist = flat_table[index]
            if Found and (big in alist or small in alist):
                blist.extend(alist)
                flat_table.pop(index)
            elif big in alist:
                if not small in alist:
                    alist.append(small)
                Found = True
                blist = alist
            elif small in alist:
                alist.append(big)
                Found = True
                blist = alist
            index-=1
        if not Found:
            flat_table.append([big,small])

    for alist in flat_table:
        smallest = min(alist)
        for o in alist:
            img[img==o] = smallest
    
    check(img)

def labeling_8(image):
    H,W = image.shape

    img = np.zeros((H+2,W+2)).astype(np.int)
    img[1:H+1,1:W+1] = image[:,:]
    lookup_table = dict()
    id = 1

    for i in range(1,H+1):
        for j in range(1,W+1):
            if img[i,j] != 0:
                v = [img[i-1,j], img[i,j-1], img[i-1,j-1],img[i-1,j+1]]
                big = max(v)
                small = min(v, key=lambda x: x if x != 0 else 65535)
                if big == 0:
                    img[i,j] = id
                    id += 1
                    if id == 255:
                        id += 1
                else:
                    img[i,j] = small
                    for s in [x for x in v if x > small]:
                        if not s in lookup_table:
                            lookup_table[s] = [small]
                        elif not small in lookup_table[s]:
                            lookup_table[s].append(small)

    flat_table = []
    sorted_keys = sorted(lookup_table)
    while len(sorted_keys) > 0:
        key = sorted_keys.pop()
        smallest = min(lookup_table[key])
        v = [x for x in lookup_table[key] if x > smallest]
        flat_table.append((key, smallest))
        for x in v:
            if not x in lookup_table:
                lookup_table[x] = [smallest]
                sorted_keys.append(x)
            elif not smallest in lookup_table[x]:
                lookup_table[x].append(smallest)
        if len(v) > 0: sorted_keys = sorted(sorted_keys)

    for (big, small) in flat_table:
        img[img==big] = small
    
    check(img)

def labeling_8nn(img):
    H, W = img.shape
    
    label = np.zeros((H, W), dtype=np.int)
    label[img[...]>0] = 1
    
    LUT = [0 for _ in range(H*W)]
    
    n = 1
    
    for y in range(H):
        for x in range(W):
            if label[y, x] == 0:
                continue
            c2 = label[max(y-1,0), min(x+1, W-1)]
            c3 = label[max(y-1,0), x]
            c4 = label[max(y-1,0), max(x-1,0)]
            c5 = label[y, max(x-1,0)]
            if c3 < 2 and c5 < 2 and c2 < 2 and c4 < 2:
                n += 1
                label[y, x] = n
            else:
                _vs = [c3, c5, c2, c4]
                vs = [a for a in _vs if a > 1]
                v = min(vs)
                label[y, x] = v
    
                minv = v
                for _v in vs:
                    if LUT[_v] != 0:
                        minv = min(minv, LUT[_v])
                for _v in vs:
                    LUT[_v] = minv
                    
    count = 1
    
    for l in range(2, n+1):
        flag = True
        for i in range(n+1):
            if LUT[i] == l:
                if flag:
                    count += 1
                    flag = False
                LUT[i] = count
    
    COLORS = [[0, 0, 255], [0, 255, 0], [255, 0, 0], [255, 255, 0]]
    out = np.zeros((H, W), dtype=np.uint8)
    
    for i, lut in enumerate(LUT[2:]):
        out[label == (i+2)] = lut-1
    
    # verify if result is correct
    check(out)

def rand_img(h,w):
    i = np.random.choice((0,255), (h,w))
    return i

for i in range(100):
    #labeling_8b(rand_img(128,128))
    labeling_8nn(rand_img(8,8))
    print("Loop",i,"pass")