[Colloquium] Codenotti/MS Presentation/April 20, 2007

[Margaret Jaffey]

This is an announcement of Paolo Codenotti's MS Presentation.

---------------------------------------------
Date:  Friday, April 20, 2007

Time:  2:30 p.m.

Place:  Ryerson 277

M.S. Candidate:  Paolo Codenotti

M.S. Paper Title:  2Dimensional Min-Filters with Polygons

Abstract:
Computing the min-filter is an important operation in image
processing. Min-filters are the basic building blocks for translation
invariant morphological operators, which are used to preform
operations such as noise suppression, image smoothing, contrast
enhancement, and edge detection. Min-filters are a special case of
min-convolutions, which are used for a variety of applications,
including signal processing, and combinatorial optimization. The most
widely used approach for computing min-filters decomposes the
filtering element as a Minkowsky sum of smaller filters. However this
approach can be expensive for large filtering elements. There is an
algorithm to perform the min filter efficiently, but it only applies
to axis parallel rectangles.  We present an efficient algorithm to
compute the min filter when the  filtering element is a polygon for
certain polygons. Because the polygon will be given as a non digital
geometric object, we relax the conditions by allowing the algorithm to
choose a valid digitization of the polygon for each  placement. With
this relaxation, we present an algorithm to compute the min filter by
arbitrary rectangles and isosceles right triangles in logarithmic time
per pixel, in the size of the polygon. We also show how to compute the
min filter by arbitrary triangles in time $O(\frac{\log
A}{\sin\gamma}$ per pixel, where $A$ is the area of the triangle, and
$\gamma$ is the size of the smallest angle in the triangle.

Advisor:  Prof. Laszlo Babai

A draft copy of Paolo Codenotti's MS Paper will be available soon in  
Ry 161A.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=