NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/image/processi/1696

Text File | 1993-01-25 | 9.1 KB | 263 lines

Newsgroups: sci.image.processing
Path: sparky!uunet!mcsun!julienas!edf.edf.fr!cli23ne!ponthieu
From: [e-mail] ( Laurent PONTHIEU )
Subject: Efficient algorithms for math. morphology : SUMMARY
Message-ID: <[e-mail]>
Sender: [e-mail]
Reply-To: [e-mail] ( Laurent PONTHIEU )
Organization: Electricite de France - DER , Clamart FRANCE
Date: Mon, 25 Jan 1993 09:29:06 GMT
Lines: 251

Hello,

some time ago, I posted a request for information about efficient
algorithms for mathematical morphology (see the end of this posting).

Here is the summary of all private mails I have recieved. You'll have
probably noticed that some answers were also given directly in this
newsgroup.

Thanks again to all that helped.

Laurent.

======================================================================

From [e-mail] Fri Jan  8 16:17:04 1993
Return-Path: <[e-mail]>


Pour toute question non triviale concernant la morpho mat, je
suggere de contacter Michel Schmitt, au Labo
Central de Recherche de Thomson (CSF ?), aux environs
de Paris.

[ "please contact Michel Schmitt, at Labo Central de Recherche de
Thomson" : [e-mail] ]

Desole, pas de coordonnees.

Bonne chance,


Konrad Weigl               Tel. [phone]
Projet Pastis              Fax  [phone]
INRIA                      email [e-mail]
B.P. 93
06902 Sophia Antipolis Cedex
France

======================================================================

From [e-mail] Fri Jan  8 16:19:20 1993
Return-Path: <[e-mail]>

In sci.image.processing you write:

>
>    [ deleted ]
>

I can't post, otherwise I would, but check out my recent paper in
Pattern Recognition Letters:

"Fast erosion and dilation by contour processing and thresholding of
distance maps", Pattern Recognition Letters 13 (1992), pp 161-166.

The algorithm does not allow arbitrary structuring element, so perhaps
it is not the whole story, but I believe that it's impossible to make
significant speedups over the straighforward implementations using
arbitrary structuring elements. With my method, you can use circular or
diamond-shape element, and with some modifications some other, but only
convex shapes.

An older version of the paper is also in the Proc. of the latest Scandinavian
Conf. on Image Analysis (SCIA).

--
Ingemar Ragnemalm
Dept. of Electrical Engineering         ...!uunet!mcvax!enea!rainier!ingemar
                  ..
University of Linkoping, Sweden         [e-mail]

========================================================================

From [e-mail] Fri Jan  8 17:31:55 1993
Return-Path: <[e-mail]>
From: Roland Schaefer <[e-mail]>
Organization: Electrical and Computer Engineering, Carnegie Mellon

In article <[e-mail]> you write:
>
> [ deleted ]
>

I know we here use thresholded correlations to do our erosions and dilations.
We have a vector processor that does the FFTs pretty fast, and since we use
fairly large SEs, it's a lot faster than doing the work in the image domain.

Roly.

======================================================================

From [e-mail] Sat Jan  9 03:19:29 1993
Return-Path: <[e-mail]>

Erode and dilate can be written in terms of image translations and logical
and/or/invert operations on images.  If you have an efficient means for
translating images (such as efficient hardware block moves, shifts, etc.)
and for performing these logical operations, MM operations can be written
very efficiently.  Good luck.

--
Bryan Morse                University of North Carolina at Chapel Hill
[e-mail]           Department of Computer Science

======================================================================

From [e-mail] Sun Jan 10 12:03:21 1993
Return-Path: <[e-mail]>
From: [e-mail] (Thomas M. Breuel)
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
    Perceptive)



For convex structuring elements, you can use the distance transform,
which can be computed relatively quickly. But on 3000x3000 images,
anything is going to be slow (several minutes for the DT).

                    Thomas.

======================================================================

From [e-mail] Mon Jan 11 08:03:10 1993
Return-Path: <[e-mail]>
From: William Katz <[e-mail]>
Organization: Medical Scientist Training Program, Univ. of Virginia

Hi,

I do alot of MM on very large images from MRI (256 x 256 x 128 voxels).
The fastest way to do basic dilation/erosion/opening/closing is by
using the Euclidean Distance Map as described by Russ' book
Image Processing Handbook.  The first scan will store all border
voxels/pixels in a queue, and then further erosion/dilation can
be done from just those voxels/pixels in the queue.

-Bill

======================================================================

From [e-mail] Mon Jan 11 11:45:31 1993
Return-Path: <[e-mail]>

Pour ce genre d'algorithmes, lire la these de Luc Vincent
{Vincent90,
    AUTHOR = "L. Vincent",
    TITLE = "Algorithmes Morphologiques \`a Base de Files d'Attente et de
        Lacets~: Extension aux Graphes",
    HOWPUBLISHED = "Th\`ese Ecole des Mines de Paris",
    MONTH = "May",
    YEAR = "1990"
}

Ou le livre de Michel Schmitt et Luc Vincent sur la M.M., qui sortira
bientot (on espere).

A une prochaine visite au L.C.R.,

    Laurent Najman
    A.S.R.F.
    Thomson-CSF - Laboratoire Central de Recherches
    Domaine de Corbeville 91404 - Orsay Cedex / France
    Tel : [phone] / Fax : [phone]
        / Telex : THOM 616 780 F
    E-mail :     [e-mail]

======================================================================

From [e-mail] Mon Jan 11 22:35:42 1993
Return-Path: <[e-mail]>
From: [e-mail] ( James J. Song       )
Organization: Applied Computing Devices, Inc., Terre Haute IN

I worked on the MM for a while. Since basic morphological transforms
are very simple operations, especially for binary images, you can code
the transforms without having to look for the existing software or
fast algorithms.  As a matter of fact, I don't think those fast
algorithms are really faster and most likely they are slower.

When you code, consider the image as an image plain. Than shift the whole
plain around according to the structuring element and perform binary
operation between the shifted plain and the unshifted one. The only thing
you need to figure out is how to take care of the boundaries of the image
plain. I don't think the size of the code for each transform should
exceed 50 lines.

Since I am not working on that anymore and lost the interest in the
area, I didn't keep my codes. So sorry that I cannot help with the
code.

Good luck on MM research and development.

James


======================================================================

ORIGINAL POSTING :

> Path: cli23ne!ponthieu
> Newsgroups: sci.image.processing
> Distribution: world
> Followup-To:
> From: [e-mail] ( Laurent PONTHIEU )
> Reply-To: [e-mail] ( Laurent PONTHIEU )
> Organization: Electricite de France - DER , Clamart FRANCE
> Subject: Efficient algorithms for math. morphology : where are you ?
> Keywords:
>
> There seems to be some interest here about mathematical morphology,
> thus my question :
>
> Does anybody know about _efficient_ algorithms for MM on binary images ?
> Either article, book, ftp or _even_ commercial software.
>
> Following Jose E. Hernandez's hint (of 14 Oct 92, in this newsgroup), I've
> bought
>     "Morphological Methods in Image & Signal Processing" by C.R. Giardina
>     & E.R. Dougherty, Prentice Hall, 1987, ISBN 0-13-601295-7,
> which does not cover the question of algorithms efficiency.
>
> I've also digged Khoros' lib without success : there, as everywhere I've
> looked, opening and closings are implemented by composition of erosion and
> dilatation, which in turn are made with brute force four level nested loops.
>
> I must say that we work here on symbol recognition on binary images which,
> at least for now, are 3000x3000 pixels large. Size is to increase for the
> real application, and the results we've got make us think that we must not
> abandon this method !
>
> I have developed some algorithms inspired by classical string searching in
> texts but I'm not fully satisfied because they do not work for arbitrary
> structuring elements.
>
> I've been told that contour or distance coding might be the good way.
>
> What's you experience with all that ?
>
> Feel free to answer. Thanks.
> (I'll post a summary of personal answers, if any).
>
> ------------------------------------------------------------------------
>   Laurent PONTHIEU            |
>   Electricite de France            | Tel: [phone]
>   Direction des Etudes et Recherches    |
>   Dept Traitement de l'Information    | Fax: [phone]
>     et Etudes Mathematiques        |
>   1, Avenue du General de Gaulle    | E-m: [e-mail]
>   92141 CLAMART Cedex, FRANCE        |      [e-mail]
> ------------------------------------------------------------------------