Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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