🚀 go-pugleaf

Segmenting images (and a bit about penguins)

Forget about the colour bit for the moment.  Let's segment a monochrome image.
There are several ways to do this.  We can (1) draw boundaries when there is a 
significant jump in the image value, or we can start at the other end and (2)
join regions that are similar.

(1) Can give boundaries between a region and itself if it has a very slow
    gradient and meets itself, like the penguins around Antarctica that can
    interbreed with the penguins on either side of it, until you have gone
    all the way around the continent when the penguins are so distantly 
    related that they can't.

(2) This will tend to divide a gradual slope up into bands of the same value.
    The smoother your initial data the more arbitrary the positions of the
    boundaries become.  But at least you can asign a single average value to 
    the patch.

There is a not on this by T.N.Pappas in IEEE Trans on Signal Processing 
Vol 40, Apr 1992.  See also Prof. A.G. Constantiniades and other's work
on shortest spanning trees.

This reminded me of an eldritch program in Fortran 
we had on a PDP back in 1988.  It (the program) worked as follows...

We have points and links as follows....

    Point N		Point N+1
      +-----(link +N)---->*
      |
      |
      |
      |
   (link -N)
      |
      |
      V
   Point(N+L)    ....where L is the number of pixels in the region.

Assume throughout we are doing something sensible at the edges of the image 
to stop things wrapping around.  Usually an extra line of dummy values will 
do the trick.

What we are going to do is to recursively find the link spanning the smallest
jump in pixel value; then merge the two regions it joins, giving both an
average value; then do the whole thing over again until our minimum difference
is above some threshold, when we stop.

For each region (r) we need to know the number (m) of points it contains
and its average value (v).  We will start off with r=N (pixel number), m=1
(one pixel), v=pixel value.  To make merging two regions easy we reserve the
conditon (m==0) to indicate the region has been merged with another region
whose number is stored in v.  You may have to follow the pointer several times
to get to the actual region number and value.

We have a list of all the link numbers.  This starts off containing all the 
numbers from -N to +N excepting 0 and all the line breaks, etc.  We go through 
this list finding the difference between the values for each link, until we
find the link with the smallest difference.  We merge the regions ra rb
by setting va = (va*ma + vb*mb)/(ma+mb), ma = ma+mb, vb = ra, mb = 0; then
chuck the link off the link list (the fact that there is no link 0 can be 
used to avoid a lot of list shuffling).

If you are going to do this to the whole image, then finding the smallest link
can be a pretty grim buisness.  There are a few speed-ups...

(1) Whenever a link joins regions with the same value, merge the regions, then
    continue with the search for the lowest value as though nothing had 
    happened.  This causes the number of links to go down much more rapidly
    in the early stages.

(2) Deal with the image in small blocks (4*4) or (8*8) to start with.  Find the
    closest two regions in a local area rather than searching the whole image.
    This is no good as the regions get larger, but it can take a lot of work
    out of the early stages.

(3) Keep a table of the eliminated regions and their new region number, and
    periodically purge out multiple references from one region to another to
    a third...

(4) Have a pre-pass that rounds pixel values up or down to (say) the nearest
    multiple of 2, with error propagation.  This makes it more likely two
    neighbours have the same value, and up the link elimination rate in the 
    early stages without really affecting the overall statistics of the image.

Even if I could dig out the code, it was for segmenting 8*8 regions of an image
for some arcane DCT compression reason, and the algorithm was bent out of
shape by the tiny data store of the machine.

An interesting filter is to repeatedly replace each pixel with the nearest of
its two neighbours if it is closer than a certain threshold, first in one 
direction, than in the other.  This divides the image up into segments after 
a fashion, but can louse up the overall image statistics.  It is really more 
of a special effect than a useful tool.

Hope this helps.



-- 
Richard Kirk         Image Processing Group    Crosfield Electronics Ltd. U.K.
rak@crosfield.co.uk  0442-230000 x3361/3591    Hemel Hempstead, Herts, HP2 7RH