Find perimeter of the image binary object

Question

I am trying to find perimeter of binary object.

Consider following picture

[ 0 0 0 0 1 1 0 ]
[ 0 0 1 0 0 0 0 ]
[ 0 1 1 0 1 1 0 ]
[ 0 1 1 0 0 1 0 ]
[ 0 1 1 1 0 0 0 ]
[ 0 1 0 0 1 1 0 ]
[ 0 0 0 0 1 1 0 ]

Labeled image will look like this

[ 0 0 0 0 1 1 0 ]
[ 0 0 2 0 0 0 0 ]
[ 0 2 2 0 3 3 0 ]
[ 0 2 2 0 0 3 0 ]
[ 0 2 2 0 0 0 0 ]
[ 0 2 0 0 4 4 0 ]
[ 0 0 0 0 4 4 0 ]

Also I collected each object pixels in array list

So for example for 4 marked object the list will be

{ (5,4), (5,5) , (6,4), (6,5) }

Area is just the size of each object pixel array, but how can I find perimeter, should I again iterate over whole image finding neighbors of cell check if it is the corner pixel of the object or there is much easier way to do this just basing on the coordinates.

Please suggest what is the most easier way to find perimeter, any code example will be highly appreciated

Answer 1

Try doing a breadth-first search of your image, (or alternatively iterate through your list of points), and tag every pixel that neighbors another pixel that isn't of the same group.

It's not clear to me if the perimeter you want is every pixel on the outside edge of the requested object, or every pixel that borders the object. I'll assume the former for now.

Set up the image:

Here's how you'd go about doing this. First, set up your image as a 2-D array, with each pixel labeled with the group number:

[ 0 0 0 0 1 1 0 ]
[ 0 0 2 0 0 0 0 ]
[ 0 2 2 0 3 3 0 ]
[ 0 2 2 0 0 3 0 ]
[ 0 2 2 0 0 0 0 ]
[ 0 2 0 0 4 4 0 ]
[ 0 0 0 0 4 4 0 ]

A good way to load this would be to use a Scanner object to get each point, one by one:

List<Point> points = new ArrayList<>();
Scanner scanner = new Scanner( /* whatever your input source is */ );
String pointRegex = "\\(\\d,\\d\\)"; //looks for something like "(#,#)"
while(!scanner.hasNext(pointRegex)){
    String pointText = scanner.next(pointRegex); //For example, "(5,4)"
    Point point = getPointFromText(pointText); //turns a string into a point
    points.add(point);
}

Notice the use of Scanner.next(String pattern). This is a method that will return the next String that looks like that pattern. (Read up on regular expressions if you want to learn more about how this works.)

Now on to populating the grid:

boolean[][] binaryImage = new boolean[width][height];
for(Point p : points){ //Iterate through each Point inside our List of Point objects
    binaryImage[p.getX()][p.getY()] = true;
}

This puts the object, represented by our collection of Point objects "points", into a grid of booleans. We only need to worry about this one object, so we don't need to load any of the others. Now to finding out what points are on the perimeter.

Recursive method:

boolean[][] visitedBefore = new boolean[width][height];
boolean[][] isOnPerimeter = new boolean[width][height];
int[] deltaX = {-1,  0,  1, -1, 1, -1, 0, 1},
      deltaY = {-1, -1, -1,  0, 0,  1, 1, 1};
Queue<Point> searchNext = new LinkedList<>();
searchNext.add(points.get(0)); //Just need one point to get going
while(!searchNext.isEmpty()){
    Point p = searchNext.remove(); //take what's waiting at the front of the queue
    if(visitedBefore[p.getX()][p.getY()]){
        continue; //already check this spot!
    }

    //mark that we've been here
    visited[p.getX()][p.getY()] = true;

    //look at all of this Point's neighbors
    for(int i = 0 ; i < deltaX.length ; i++){
        int newX = p.getX() + deltaX[i];
        int newY = p.getY() + deltaY[i];

        //make sure this isn't out of bounds
        if(newX < 0 || newX >= width || newY<0 || newY>=height){
            isOnPerimeter[p.getX()][p.getY()] = true; //if you decide bordering the edge of the image counts as being on the perimeter
            continue;
        }

        //check if this new point we're considering isn't part of the image
        if( binaryImage[p.getX()][p.getY()] != binaryImage[newX][newY] ){
            //if it isn't, then this Point p must be on the perimeter
            isOnPerimeter[p.getX()][p.getY()] = true;
        } else {
            /* otherwise, this new point we're considering is part of the
             * same object, and could be part of the perimeter. */
            searchNext.add(new Point(newX, newY));
        }
    }
}

Now you have a grid with each point on the perimeter marked as true. If you need these as a list, picking out those points is easy:

List<Point> perimeter = new ArrayList<Point>();
for(int x = 0 ; x < isOnPerimeter.length ; x++)
    for(int y = 0 ; y < isOnPerimeter[x].length ; y++)
        perimeter.add( new Point(x,y) );

Iterative method:

This is pretty similar to the above, but jumps straight to putting the perimeter points into a list.

int[] deltaX = {-1,  0,  1, -1, 1, -1, 0, 1},
      deltaY = {-1, -1, -1,  0, 0,  1, 1, 1};
outer: for(Point p : points){
    inner: for(int i = 0 ; i < deltaX.length ; i++){
        int newX = p.getX() + deltaX[i];
        int newY = p.getY() + deltaY[i];
        //check if this new point we're considering is outside the image
        if(newX < 0 || newX >= width || newY<0 || newY>=height){
            perimeter.add(p); //if you decide bordering the edge of the image counts as being on the perimeter
            continue outer;
        }

        //check if this new point we're considering isn't part of the image
        if( binaryImage[p.getX()][p.getY()] != binaryImage[newX][newY] ){
            //if it isn't, then this Point p must be on the perimeter
            perimeter.add(p);
            continue outer;
        }
    }
}

Notice the labels outer: and inner:. This lets us choose which for loop to skip along when we say continue outer;.

There you go! This should help you get the perimeter of any object as either an binary image or as a List.