CODEWITHSUNDEEP
matrixconnectivity
Phrixus
Phrixus

Reputation: 1219

Counting number of regions in matrix

I have the array:

1 1 1 1
2 2 1 1
1 1 2 1
1 1 2 2

Assuming that the array has only 1s and 2s I want to count the regions of 2s. For the above example the answer is 2 regions.

My algorithm is the following:

I have another array of the same size holding boolean values, true for visited, false for un-visted.

1) Loop through the array
2) If is 1 and un-visted mark it as visited
3) If it is 2 and unvisited then I have to check cross-style the neighbours of this 2, that is Left, Right, Top, Bottom.
4) If in 3 the neighbour is 2 and unvisited then mark it as visited and continue the cross-style searching.
5) If at any given point, the left, right, top and bottom are seen it means that it is a region?

I am not sure if this algorithm will find all the possibles ways to count 2s regions and if this will work if with a simple loop I can move the cross-style shape to find the neighbours.

Can somebody give me a hint or if my logic is not in the right how can I make it work?

Upvotes: 0

Views: 3257

Answers (4)

py-coder
py-coder

Reputation: 315

I have written a generalised code to count the number of regions from a matrix that works with time complexity O(M*N)

rows, cols = 0, 0
def traverse_matrix(A, directions, i, j, visited):
    global rows, cols
    def isSafe(A, row, col, visited, current):
        return ( row >=0 and row < rows and col >=0 and col < cols and \
            not visited[row][col] and (current == A[row][col]))
    visited[i][j] = True
    #print i, j
    for k in range(len(directions)):
        if isSafe(A, i+directions[k][0], j+directions[k][1], visited, A[i][j]):
            traverse_matrix(A, directions, i+directions[k][0], j+directions[k][1], visited)

def solution(A):
    global rows, cols
    rows, cols = len(A), len(A[0])
    print A
    if(rows is 1 and cols is 1):
        return 1
    directions = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    visited = []
    for i in range(rows):
        l = []
        for j in range(cols):
            l.append(False)
        visited.append(l)

    count = 0
    for i in range(rows):
        for j in range(cols):
            if not visited[i][j]:
                traverse_matrix(A, directions, i, j, visited)
                count += 1
    print "Regions count: {0}".format(count)

Output:
[[5, 4, 4], [4, 3, 4], [3, 2, 4], [2, 2, 2], [3, 3, 4], [1, 4, 4], [4, 1, 1]]
Regions count: 11
[[2, 3, 3], [4, 4, 1], [2, 1, 1], [5, 2, 3], [5, 2, 2], [1, 4, 1], [3, 4, 1]]
Regions count: 12
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Regions count: 9
[[1, 1, 1], [2, 2, 2], [3, 3, 3]]
Regions count: 3
[[1, 1], [2, 2], [3, 3]]
Regions count: 3
[[1, 2], [1, 2]]
Regions count: 2
[[1, 2], [3, 4]]
Regions count: 4
[[1, 1], [1, 1]]
Regions count: 1

Upvotes: 0

Leandro Caniglia
Leandro Caniglia

Reputation: 14868

Let m be a matrix of n rows and m columns. Here is the pseudo code of an algorithm that computes the desired number of regions inspired in the one described in the question. Note that I've used the collection of unvisited entries, rather than the collection of visited ones.

Let unvisited be the collection of all pairs (i, j); 1<=i<= n, 1<=j<=m.
Initialize the region counter := 0.
While unvisited is not empty do:
    Pick any unvisited pair (i, j).
    If matrix[i, j] = 2
      then
        counter := counter + 1
        visit(i, j)
      else remove (i, j) from unvisited.
Return counter

Where visit(i, j) is the recursive routine:

If unvisited contains (i, j) then
  Remove (i, j) from unvisited
  If matrix[i, j] = 2 then
    If j > 1 then visit(i, j - 1)
    If j < m then visit(i, j + 1)
    If i > 1 then visit(i - 1, j)
    If i < n then visit(i + 1, j)

Upvotes: 1

Anton
Anton

Reputation: 559

Initialize a mask. Then loop through each pixel. If it is not labeled, use it as a seed to find a connected component, such as all connected pixel label to 1. then label all pixels in the region. In the end, find biggest number in the mask.

Upvotes: 0

ElConrado
ElConrado

Reputation: 1640

Not exactly, because count of searching will give you number of regions. Like in the following example:

    int region=0;

    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(array[i][j]==1)
                ar[i][j]=true;
            else if(ar[i][j]==false){
                check(array,ar,4,i,j);
                region++;
            }

function check is for cross-searching, it bring two arrays and modifiy them. Its of course recursion function.

Upvotes: 0

Related Questions