#
Monday Lecture and Colloquium

**Monday, June 15, 2009**

Freie Universität Berlin

Institut für Informatik

Takustrasse 9

14195 Berlin

** Lecture - 14:15**

###
Johannes Blömer - Paderborn

### Clustering for Metric and Non-Metric Distance Measure

*Abstract:*

Clustering is the (meta-)problem of partitioning a given set of objects
into subsets of similar objects. It has
application in various areas of computer science such as machine
learning, data compression, data mining,
or pattern recognition. Depending on the application we want to cluster
such diverse objects as text documents,
probability distributions, feature vectors, etc. Obviously, different
objects and different applications
also require different notions of (dis-)similarity of objects. As a
consequence, there are numerous different
formulations of clustering. In theoretical computer science many
approximation algorithms have been developed
for variants of clustering, where the points come from a metric space.
However, for non-metric dissimilarity
measures almost few approximation algorithms are known. In this talk I
will discuss some simple approximation algorithms
that apply to a variety a distance measures. These distance measures
include the Kullback-Leibler divergence from information
theory, Mahalanobis divergences from statistics, and the Itakura-Saito
divergence from speech processing.

**Colloquium - 16:00**

###
Lei Zhang -
City University of New York

###
Methods to invert the geometric distortions induced by a book
scanner

*Abstract:*

The purpose of this project is to design and implement
algorithms to invert the geometric distortions induced by a book
scanner. We will assume that the book is placed face-up in a V-shape
cradle. An overhead camera takes pictures of the exposed pages. Page
curvature is highest near the spine, which causes the scanned pages to
be warped. This project proposes to use Coons patches to warp the
scanned images to make them appear as close to the original versions as
possible. We will measure and verify the numerical accuracy in restoring
these warped images to their original form by asking industry to test
our images using Optical Character Recognition (OCR).

Letzte Aktualisierung:
15.06.2009