image processing - MATLAB - Find contour of a binary bit map?

Question

I have a 10x10 binary bit map as follows. I am looking for an efficient way of finding its contour in MATLAB. (I have tried letting every value "look around" its neighbors' values and decide, but it is too inefficient. I expect the algorithm to scale up.)

false   false   false   false   false   false   false   false   false   false
false   false   true    true    true    true    true    true    false   false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   false   true    true    true    true    true    true    false   false
false   false   false   false   false   false   false   false   false   false

Let's assume each boolean value resembles a square, and the left-bottom one sits over x: 0-1; y: 0-1. The output should be the points that form the boundary. You may assume the inner true block is alway convex.

Answer 1

This is dead simple. Use the bwperim command in MATLAB, assuming you have the image processing toolbox.

You can call the function like so:

out = bwperim(A);  %//or
out = bwperim(A,conn);

The first way assumes that the pixel connectivity is a 4-pixel neighbourhood. This will only look at the north, south, east and west directions.

If you specify an additional parameter called conn which is a single number, you can override this behaviour and specify the kind of behaviour you want when looking at neighbouring pixels. For example, if conn=8, you would look at 8-pixel neighbourhoods for 2D (so N, NE, E, SE, S, SW, W, NW), or you can go into 3D if you have a 3D binary image... but for now, I'm assuming it's just 2D. For the best accuracy, use 8.

As such, we have:

A = [false   false   false   false   false   false   false   false   false   false
false   false   true    true    true    true    true    true    false   false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   true    true    true    true    true    true    true    true    false
false   false   true    true    true    true    true    true    false   false
false   false   false   false   false   false   false   false   false   false];

out = bwperim(A,8);

And it looks like:

out =

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

MATLAB outputs 1 for true and 0 for false.

As a bonus, this is what the shapes look like side by side:

Edit from the comments

Going with your comments, you wish to find the set of points that make the perimeter. As such, you can simply use the find command to do that for you.

[X,Y] = find(out == 1);
coords = [X Y];

What the find command does is that it searches your array and finds locations in the array that match the Boolean expression given in the parameter of find. In this case, we wish to find all co-ordinates that have a pixel in out equal to 1, and out is our perimeter image. As such, this effectively finds all pixels that are perimeter pixels.

We thus get:

coords =

  3     2
  4     2
  5     2
  6     2
  7     2
  8     2
  2     3
  3     3
  8     3
  9     3
  2     4
  9     4
  2     5
  9     5
  2     6
  9     6
  2     7
  9     7
  2     8
  3     8
  8     8
  9     8
  3     9
  4     9
  5     9
  6     9
  7     9
  8     9

X are the row co-ordinates, while Y are the column co-ordinates. I've placed X and Y into a single 2D array for better presentation, but you can take the X and Y variables by themselves for further processing.

Hope this helps!