CODEWITHSUNDEEP
c++algorithm
Bob John
Bob John

Reputation: 3888

Finding distinct sections in an image

Suppose you're given a vector<vector<bool>> (square region) where a 1 corresponds to a "filled" box. Are there any methods to find whole regions in O(n) time? For example, this vector will have two whole regions:

0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0

Upvotes: 1

Views: 105

Answers (1)

carlosdc
carlosdc

Reputation: 12152

This is called 8-connected region growing. It is a standard technique in image processing, you select a seed pixel and "grow". This can be done with BFS in linear time in the number of pixels:

  • keep a queue with the fringe, put there the initial seed
  • get an element from the queue call it current point and added to your "region" list
  • push to the queue the neighbors of the current point that are one, never push to the queue a point that you've already pushed to the queue
  • finish when the queue is empty.

The region list contains a region, set that to zero. Find another seed and run again, until you can't find seeds.

Upvotes: 3

Related Questions