Лучший алгоритм поиска области с одинаковыми значениями

Question

Я хотел бы вернуть список пикселей, принадлежащих к той же области, после нажатия на один из них. На входе будет выбранный пиксель (начальное число), а на выходе будет список всех пикселей, имеющих одинаковое значение и принадлежащих к одной и той же области (не разделенных ни одним пикселем другого значения).

Моя идея состояла в том, чтобы создать вспомогательный список семян и проверить соседей каждого из них. Если значение соседнего узла совпадает со значением начального числа, оно добавляется в список регионов. Моя python реализация ниже:

def region_growing(x, y):

    value = image[x,y]
    region = [(x,y),]
    seeds = [(x,y),]

    while seeds:
        seed = seeds.pop()
        x = seed[0]
        y = seed[1]
        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                if image[i,j] == value:
                    point = (i,j,z)
                    if point not in region:
                        seeds.append(point)
                        region.append(point)
    return region

Это работает, но очень медленно для больших регионов. Какой алгоритм вы бы предложили?

Answer 1

Проблема в инструкции if point not in region, время выполнения которой будет увеличиваться с увеличением размера региона. Сложность, таким образом, квадратична c.

Другая проблема состоит в том, что вы посещаете одни и те же пиксели несколько раз на границе области, поскольку отслеживаете только пиксели в области.

Вы можете избежать этого, используя словарь посещенных пикселей с точкой в ​​качестве ключа.

def region_growing(x, y):
    value = image[x,y]
    region = [(x,y),]
    seeds = [(x,y),]
    visited = {(x,y):true}

    while seeds:
        seed = seeds.pop()
        x = seed[0]
        y = seed[1]
        for i in range(x-1, x+2):
            for j in range(y-1, y+2):
                point = (i,j)
                if point in visited:
                    continue
                visited[point] = true
                if image[i,j] == value:
                    region.append(point)
                    seeds.append(point)
    return region

Другой метод заключается в использовании матрицы логических значений вместо словаря. Это быстрее, но требует больше памяти.

Answer 2

Я могу предложить вам использовать любой алгоритм заполнения области / рисования и исправлять его не для рисования, а для отслеживания пикселей той же области. Известно, что алгоритм Смита является быстрым и эффективным, см. Алгоритм заливки оттенка .

. Обратите внимание, что хранить все пиксели неэффективно, но, как показывает алгоритм, горизонтальных сегментов достаточно (поэтому только два пикселя в сегменте).