Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!ADS.COM!Vision-List-Request From: Vision-List-Request@ADS.COM (Vision-List moderator Phil Kahn) Newsgroups: comp.ai.vision Subject: Vision-List delayed redistribution Message-ID: <8911090500.AA02144@deimos.ads.com> Date: 9 Nov 89 01:22:11 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Vision-List@ADS.COM Distribution: inet Organization: The Internet Lines: 209 Approved: vision-list@ads.com 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 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" 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 ********************