Thread Subject: How does bwlabel work?

I'm trying to understand the algorithm of the bwlabel
command. Basically, I want to know how bwlabel determines
the order of labelling (which blob is 1, which blob is 2
etc.) and if there's a way to change that ordering.

I checked the Matlab help and it refers to certain pages
from a book which I don't have access to.

Can anyone explain how bwlabel works.
 
Thanks.

"Ross " <ross.nospam.kozz@yahoo.com> wrote in message
<fnrdc1$es0$1@fred.mathworks.com>...
> I'm trying to understand the algorithm of the bwlabel
> command. Basically, I want to know how bwlabel
determines
> the order of labelling (which blob is 1, which blob is 2
> etc.) and if there's a way to change that ordering.
>
> I checked the Matlab help and it refers to certain pages
> from a book which I don't have access to.
>
> Can anyone explain how bwlabel works.
>
> Thanks.


edit bwlabel
You can see the code.
Vihang

BWlabel basically finds the connected components of a binary image. All the pixels in a connected components are given a level. The searching of the connected components is done in the coulmn-wise fashion, in other words, in top-to-bottom scan order. All pixels in the first conected component is labeled -1 and those in the second as 2 and so on.

See:
http://blogs.mathworks.com/steve/category/connected-components/



Yumnam Kirani Singh <kirani.singh@gmail.com> wrote in
message
<14977013.1201760451936.JavaMail.jakarta@nitrogen.mathforum.org>...
> BWlabel basically finds the connected components of a
binary image. All the pixels in a connected components are
given a level. The searching of the connected components is
done in the coulmn-wise fashion, in other words, in
top-to-bottom scan order. All pixels in the first conected
component is labeled -1 and those in the second as 2 and so on.

Ross asked about the order in which bwlabel searches for connected
components, and whether it's possible to change that order.

Yumnam wrote:

 > BWlabel basically finds the connected components of a
 > binary image. All the pixels in a connected components are
 > given a level. The searching of the connected components is
 > done in the coulmn-wise fashion, in other words, in
 > top-to-bottom scan order. All pixels in the first conected
 > component is labeled 1 and those in the second as 2 and so on.

Right. Some ordering changes can happen when two or more sets of pixels
are initially assigned different labels, but later the algorithm
discovers they actually belong to the same object.

There's no way to tell bwlabel to search in a different order. If it
did search in a different order, it would run significantly slower
because of memory cache effects.

Wolfgang Schwanghart wrote:
> See:
> http://blogs.mathworks.com/steve/category/connected-components/

Thanks for the plug, Wolfgang.

Since this question has come up multiple times, I've added "show how to
post-process output of bwlabel to sort object labels as desired" to my
list of potential blog topics. Watch for it, maybe soon.

---
Steve Eddins
http://blogs.mathworks.com/steve/

In article <fnsk56$1oh$1@fred.mathworks.com>,
Steve Eddins <Steve.Eddins@mathworks.com> wrote:

>There's no way to tell bwlabel to search in a different order. If it
>did search in a different order, it would run significantly slower
>because of memory cache effects.

You (the programmer desiring the "different order") could transpose
or fliplr or flipud the matrix first ;-)


I have never tried bwlabel(), so I do not have any feel for its
performance on different image sizes, and I have not looked at
the algorithm used. But as a user, I would think that if I have
good reasons to want a different search order, that I would accept
the performance implications that went along with chosing that
option. I would suggest, then, that you consider allowing an
optional parameter which is a permutation vector of the
(1-D) pixel indices, with the pixels to be visited in the order
of that vector.
--
   "I was very young in those days, but I was also rather dim."
   -- Christopher Priest

Walter Roberson wrote:
> In article <fnsk56$1oh$1@fred.mathworks.com>,
> Steve Eddins <Steve.Eddins@mathworks.com> wrote:
>
>> There's no way to tell bwlabel to search in a different order. If it
>> did search in a different order, it would run significantly slower
>> because of memory cache effects.
>
> You (the programmer desiring the "different order") could transpose
> or fliplr or flipud the matrix first ;-)
>
>
> I have never tried bwlabel(), so I do not have any feel for its
> performance on different image sizes, and I have not looked at
> the algorithm used. But as a user, I would think that if I have
> good reasons to want a different search order, that I would accept
> the performance implications that went along with chosing that
> option. I would suggest, then, that you consider allowing an
> optional parameter which is a permutation vector of the
> (1-D) pixel indices, with the pixels to be visited in the order
> of that vector.

It's a good suggestion, but I would not be inclined to make that change
for these reasons:

a. User can preprocess image, as you suggested
b. User can postprocess output labels, as I will probably demonstrate
soon on my blog
c. Lack of well-defined sorting order for two-dimensional space
d. Substantial increase in complexity of code and testing, with a
corresponding increase in the likelihood of programming errors
e. "Opportunity cost" - implementing this change means we would not have
time for implementing other requested features, including other
user-suggested changes to bwlabel that would have broader benefit

In my opinion, user post-processing, assisted by the output of
regionprops, is probably the best way to go because of reason c. Even
if we permute the search order, the output labels may still not be
ordered exactly the way the user desired, whatever that might be.

Thanks,

Steve

Wolfgang, thanks for this link -

http://blogs.mathworks.com/steve/category/connected-
components/

That's an excellent resource.

Steve, I look forward to your blog update. Basically, I'm
trying to assign "identities" to each blob. So if a blob
starts labelled as 2, even if it moves to a different
location, I'd like it to remain as 2, and not change to a
different label.

That will give me the ability to track these blobs rather
than just know where the blobs are.

In article <fnt68l$tv$1@fred.mathworks.com>,
Ross <ross.nospam.kozz@yahoo.com> wrote:
>Basically, I'm
>trying to assign "identities" to each blob. So if a blob
>starts labelled as 2, even if it moves to a different
>location, I'd like it to remain as 2, and not change to a
>different label.

>That will give me the ability to track these blobs rather
>than just know where the blobs are.

That is not possible in general, unless additional motion information
can be provided.

Consider image1 with two non-intersecting circles, C1, C2, near the
bottom of the image, and then consider image2 with two non-intersecting
circles near the top of the image. So C1 moved upwards and C2 moved
upwards? Not necessarily: C1 and C2 might have moved in diagonally
opposite directions and changed places, so in image2 the identities
might be in the order C2 then C1.

The tracking problem is significantly worse if the blobs can shrink
or grow or divide (one blob split, or two overlapping blobs seperate).
Recorded color changes with shadows and lighting angle, so the
boundaries of a moving blob might not be the same in two images,
even beyond "staircase" effects of image quantization into
discrete pixels.

bwlabel thus cannot really be expected to track blob identities.
You need to do some kind of post processing to find some kind of
"signature" for each blob to determine which is which, and that
signature is likely to need to incorporate domain-specific knowledge.
--
  "All is vanity." -- Ecclesiastes