Re: Remove speckles in bilevel (bw) image


Yesterday I wrote:

I may discuss elimination of bigger blobs at a
later time; most of the methods to be used here
do apply, but enhancements of technique and
reformulation of results seem necessary.

Such a discussion seems to fall into place
without a serious hitch provided we agree that
the suppression of a black blob B_0 in general
entails painting in white somewhat more than the
pixels of B_0. Namely we consider the outermost
circle component C of the external rampart
E(B_0) of B_0. The unbounded connected component
of R^2 - C is is disjoint from B_0 and hence
homeomorphic to the open annulus C \times R, as
is the connected component of R^2 - B_0
containing C. The other component of R^2 - C
contains B_0 and has closure in R^2 that is a
2-disk D; it contains B_0 and perhaps some of the
other connected components, say B_1, B_2, ..., of
B. Assuming that B_0 turns out to be small, we
will paint white not just B_0 but \D \cap B which
is all of the connected components of B that
happen to lie in D.

One gets a clearer picture of B1, B_2,... by
considering the frontier loops C', C'',... of
N(B_0) that are distinct from the outermost loop
C. They are the boundaries of disjoint 2-disks
D', D'',... that we call the 'alveoles' of B_0
each disjoint from B_0. The connected components
of B that lie in some one of the alveoles D',
D'', ... are the components of B that get painted
white along with B_0.

This picture is not really useful to our
computer because the painting operation occurs
after it has calculated C but before it has
calculated C', C''. Fortunately, given a
calculation of C there are calculations
(e.g. row-by-row) of the pixels within C
--- well known in computer graphics programs.
Incidentally we have essentially described a slow
one yesterday. Namely use the projection
p_B(C) to paint white the pixels that this singular
path touches. This can be viewed as eroding D and
the collection of pixels in it, strictly reducing
the number of those pixels. One can iterate this
sort of erosion until all pixels in D are painted
white.

This more vigorous blob suppression is
reasonable because each of the other connected
components of B is always no larger than B_0
according to several common measures of size (but
not by all, e.g. perimeter!). The most convenient
measure of size in the present context seems to
be 'bounding box size'. The bounding box of a
compact set in R^2 is the least rectangle
containing it and having sides parallel to the
coordinate axes.

Lemma 1. Let D be a 2-disk embedded in R^2
with boundary loop C. Then the bounding
box \bbox C of C in R^2 is exactly the bounding
box \bbox D of D.\qed


Lemma 2. If X and Y are compacta in R^2
and Y is a neighborhood of X, then
\bbox Y is a neighborhood of \bbox X. \qed

______________


REMARK ON EFFICIENCY: In the algorithm of
yesterday for elimination of blobs of =< 3 pixels
we gained speed by aborting the calculation of
p_B(C) whenever an initial segment touched >= 4 pixels.
A similar trick applies in the present context.
If the bounding box for an initial segment of C
becomes larger than that allowed for a black blob
B_0 whose elimination is being contemplated,
then, by the above lemmas and the fact that
epsilon is arbitrarily small, we immediately know
that \bbox B_0 will also be too big, and we can
forthwith abort efforts to paint D \cap B white.

______________


Putting the above modifications onto the
algorithm described yesterday seems to establish:

ASSERTION.

Let I be a black-white image in the plane
R^2, whose pixels are the unit squares about the
integral points. Suppose that, outside some
bounded rectangle, all pixels are white, or else
all pixels are black.

For this data we have just described an
algorithm that, given a pair of positive integers
(a,b), paints white all the the black blobs that
lie within some pixel rectangle of width =< a and
height =< b. It alters no other black pixels and
it alters no white pixel.

______________

VARIANT 1.
The same of course holds with black and
white exchanged.

______________

Applying this and the first algorithm (or
better running them unterlaced?) yields:

VARIANT 2.

For the same data we have described
algorithms that, given two pairs of positive
integers (a,b) and (a',b'), eliminate all the
the black blobs that lie within some pixel
rectangle of width a and height b, and eliminate
all the white blobs that lie within some pixel
rectangle of width a' and height b'.

In this process:

(i) A black blob B_0 not lying in an a\times b
pixel rectangle is modified by filling with black
poxels all the white alveoles in it that lie in
an a' \times b' pixel rectangle. But B_0 is
altered in no other respect; in particular, its
outermost rampart loop and its bounding box are
unchanged.

(ii) A white blob W_0 not lying in an a'\times b'
pixel rectangle is modified by filling with white
the alveoles in it that lie in an
a \times b pixel rectangle. But W_0 is it is
altered in no other respect; in particular, its
outermost rampart loop and its bounding box are
unchanged.

______________

VARIATION 3. It seems that taxicab length of
diagonal of bounding box can replace the \bbox
size used above. The taxicab length of a pixel
rectangle diagonal is a+b for an (a \times b
bounding) box. Many very different boxes have the
same taxicab diagonal-length.


I hope that all this is not already too
complex to program :)

The blob-enumeration algorithms I have seen
discussed are quite different.

Cheers

Laurent S.
.

Relevant Pages

  • Re: System.Drawing , Drawimage . Pixels are blurred
    ... My objective is to position a set of pixels in a bitmap ... and enlarge it based on the dimension specified for the container.I choose ... gradient from the middle to the edges of each pixel rectangle. ... really want is something which is of equal gradient in the stretched pixel. ...
    (microsoft.public.win32.programmer.gdi)
  • Re: Image detection
    ... pixels and length of 500 pixels. ... the problem of discarding the non-textual components of the image ... may be solved by deleting the connected components that are too large ... Illumination problems can also affect results. ...
    (comp.soft-sys.matlab)
  • Re: stenciling out ps-invocations?
    ... Doing stencil ops inside the bounding box will potentially touch a lot of pixels that the object itself wil never touch. ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: Simple matrix question
    ... bounding box around a set of pixels. ... With your specification of pixels being only 0 and 1, ... and findwill tell you the last occupied row. ... if the arms are equal length, then the center of the object ...
    (comp.soft-sys.matlab)
  • Re: How does bwlabel work?
    ... Ross asked about the order in which bwlabel searches for connected components, and whether it's possible to change that order. ... All the pixels in a connected components are ... 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. ...
    (comp.soft-sys.matlab)