Copy Link
Add to Bookmark
Report
VISION-LIST Digest 1989 11 08
Vision-List Digest Wed Nov 08 17:22:11 PDT 89
- Send submissions to Vision-List@ADS.COM
- Send requests for list membership to Vision-List-Request@ADS.COM
Today's Topics:
Fractal description of images
Re: Applications of distance maps
Computer Vision in High Energy Physics
3-D Displays
Research Fellowship
----------------------------------------------------------------------
Date: Tue, 7 Nov 89 03:03:56 GMT
From: us214777@mmm.serc.3m.com (John C. Schultz)
Subject: Fractal description of images
Organization: 3M - St. Paul, MN 55144-1000 US
Several weeks ago I asked if anyone had an algorithm they were willing to
share on how to calculate image fractal dimensions. Although I still don't
have an implementation, I DO have a readable reference that even provides
pseudo-code. The reference comes from U of Missouri-Colombia and perhaps
someone at that school could impose on the authors to provide their code? In
any case, I will be working on a realization here for our specific hardware.
Here is the reference and thanks to the authors for a well written paper.
Keller JM, Chen S, & Crownover RM, "Texture Description and Segmentation
through Fractal Geometry", Computer Vision, Graphics, and Image Processing,
45, 150-166 (1989) Academic Press.
--
John C. Schultz EMAIL: jcschultz@mmm.3m.com
3M Company WRK: +1 (612) 733 4047
3M Center, Building 518-01-1 St. Paul, MN 55144-1000
The opinions expressed above are my own and DO NOT reflect 3M's
------------------------------
Date: Tue, 7 Nov 89 12:22:31 +0100
From: Ingemar Ragnemalm <ingemar@isy.liu.se>
Subject: Re: Applications of distance maps
In comp.ai.vision both you and I write:
>I'm writing a thesis on distance mapping techniques, and I need more
>references to applications.
>There are a lot of applications, like:
(I still need more of them! Please?)
>(some of my junk deleted, including some simple examples)
>These examples are with the crude "City Block" metric. There are far better
>metrics [Borgefors], including the exact Euclidean metric [Danielsson].
>E-mail: ingemar@isy.liu.se
>[ Please post responses to the Vision List...
>
> An aside:
> City-block distance metric is particularly easy to compute. Initialized
> chamfer image locations set to 0 for occupied positions; infinity otherwise
> (i.e., a very large integer). Two passes (top-to-bottom/left-to-right and
> bottom-to-top/right-to-left) then compute the chamfer. First pass takes the
> MIN of the current location and the neighbors' chamfer values incremented
> by the indicated values (CP is the current position):
> +2 +1 +2
> +1 CP
> Second pass uses the same mask flipped on both the vertical and horizontal
> axes. Region labelled chamfer obtained by also propagating region labels.
> Region growing in constant time by thresholding the distance chamfer.
> Medial axis transform occurs at maxima in the distance chamfer. Sorry for
> being long winded, but this algorithm (shown to me originally by Daryl
> Lawton) has proven quite useful... N-nearest neighbor algorithms (for
> N>1) get significantly more computationally complex (anyone know of good
> algorithms?).
> phil...]
Actually, most efficient algorithms use this "scanning" technique. A far
better algorithm with masks of the same size is:
+4 +3 +4
+3 0
as suggested by Borgefors [CVGIP 1986]. It is proven the optimal 3*3 chamfer
mask with integer weights. Borgefors also suggests the "5-7-11" mask for the
5*5 mask size.
Danielsson [CGIP 1980] uses a similar technique for the Euclidean distance
transform, as well as myself in some of my own work (published at the 6SCIA
conference 1989). The big difference is that Euclidean DT *must* use more than
two scans. Three or four should be used (as in my paper) or the equivalent
two "double" scans (as in Danielsson's paper).
An interesting point is that a canadian researcher, Frederic Leymarie, who
I met at a conference claimed that the 4-neighbor version of the Euclidean
distance transform is faster than everything but the City Block distance
transform. I'm still waiting for the actual paper, though.
So much for implementation.
BTW, Phil, you didn't say what *you* used the CB distance maps for.
Would you care to share that information?
I'll be back when I've got some more replies.
Ingemar Ragnemalm
Dept. of Electrical Engineering ...!uunet!mcvax!enea!rainier!ingemar
..
University of Linkoping, Sweden ingemar@isy.liu.se
[ Very interesting mask modifications for computing CB chamfers. If I
remember correctly, when the distance metric scale in pixels is important
(i.e., the distance values are in pixel unit CB distance), an "extra pass"
is required to reduce the resulting chamfer values to pixel units of
distance (since I often desired the values in pixel units).
What did I use the CB distance (chamfer) for? Pretty varied uses.
Region growing in constant time (i.e., chamfer and threshold). Determining
the closest surrounding regions to each image region (by propagating
the region ID with the distance metric). I used this to form a graph in
which textels are vertices connected by edges to all chamfer determined
adjacent neighbors, and texture is described as topological properties of
this Voronoi-related graph. (I never published this: CVPR88 had a paper or
two that did something like this, but not quite). I have also used it to
compute the probability dropoff of a vehicle detection against its
background due to radar sensor distortion, occlusion, and uncertainty
(suggested by Doug Morgan of ADS).
Note that use of 1-nearest neighbor is very susceptible to noise,
and its relationship to the Symmetric and Medial Axis Tranforms gives it
some other nasty properties (e.g., small chamges in image topology can
give rise to very large changes in chamfer/SAT/MAT topology). The
n-nearest neighbor moves away from some of these problems. Thing is,
I haven't seen (nor honestly, looked very hard), for n-nearest neighbor
algorithms which are efficient.
phil... ]
------------------------------
Date: Wed, 8 NOV 89 10:06 N
From: DANDREA%ITNVAX.CINECA.IT%ICINECA2.BITNET@CUNYVM.CUNY.EDU
Subject: Computer Vision in High Energy Physics
I'm looking for informations regarding the application
of Computer Vision or Image Processing techniques to
experimental problems in High Energy Physics.
What I'm thinking of could be the applications to the
problem of track reconstruction and particle identification.
If someone else is interested I'll post a summary to the list.
Thanks,
Vincenzo D'Andrea e-mail: DANDREA@ITNCISCA.BITNET
Dipartimento di Fisica
Universita` di Trento
38050 - POVO (TN)
ITALY tel. +39 (461) 881565
------------------------------
Date: 8 Nov 89 10:23:00 EST
From: "V70NL::SCHLICHTING" <schlichting%v70nl.decnet@nusc.navy.mil>
Subject: 3-D Displays
Could you please tell me where I could obtain a copy of the papers listed
in the recent vision list from ACM SIGGRAPH "Tutorial notes on stereo
graphics"?
Thank you,
Christine Schlichting (Schlichting@nusc.navy.mil)
------------------------------
Date: Wed, 8 Nov 89 11:57:23 WET DST
Subject: Research Fellowship
From: M.Petrou%ee.surrey.ac.uk@NSFnet-Relay.AC.UK
VISION, SPEECH AND SIGNAL PROCESSING GROUP
University of Surrey, U. K.
RESEARCH FELLOWSHIP
A research fellowship has become available in the above group for the fixed
term of three years. The research fellow will work on Renormalization Group
techniques in Image Processing, a project funded by SERC.
A good knowledge of a high level programming language is necessary. No
previous experience in Image Processing or Computer Vision is needed, but a
Mathematical background will be an advantage. Starting salary up to
13,527 pounds per annum.
For more information contact Dr M Petrou (tel (483) 571281 ext 2265) or Dr J
Kittler (tel (483) 509294). Applications in the form of a carriculum vitae
(3 copies) including the names and addresses of two referees and a list of
publications should be sent to the Personnel Office (JLC), University of
Surrey, Guildford GU2 5XH, U. K., quoting reference 893 by 1 December 1989.
------------------------------
End of VISION-LIST
********************
