CODEWITHSUNDEEP
algorithmimage-processing
Karol Borkowski
Karol Borkowski

Reputation: 742

Best algorithm to find a region of the same values

I would like to return a list of the pixels that belongs to the same region, after clicking on one of them. The input would be the chosen pixel (seed) and the output would be a list of all pixels that have the same value and belongs to the same region (are not separatet by any pixel of different value).

My idea was to create an auxiliary list of seeds and check the neighbours of each of them. If the value of the neighbour is the same as of the seed, it is appended to the region list. My python implementation is below:

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

It works, but is very slow for bigger regions. What algorithm would you suggest?

Upvotes: 0

Views: 400

Answers (2)

chmike
chmike

Reputation: 22134

The problem is the instruction if point not in region whose execution time will increase with the size of the region. The complexity is thus quadratic.

Another problem is that you visit the same pixels multiple times at the boundary of the region since you only keep track of pixels in the region.

You can avoid this by using a dictionary of visited pixels with the point as key. 


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

Another method is to use a matrix of booleans instead of the dictionary. This is faster but requires more memory space.

Upvotes: 3

Jean-Baptiste Yunès
Jean-Baptiste Yunès

Reputation: 36401

I can suggest you to use any region-fill/paint algorithm and patch it not to paint but to track pixels of the same region. The Smith's algorithm is known to be fast and efficient, see Tint Fill Algorithm.

Note that it is inefficient to store all pixels, but as the algorithm suggest horizontal segments are sufficient (thus only two pixels par segment).

Upvotes: 1

Related Questions