IUPR Publication Repository

Automated OCR Ground Truth Generation

Thu, 07 Aug 2008 06:17:40 +0100

Joost van Beusekom, Faisal Shafait, Thomas M. Breuel, Proceedings of DAS 2008 Accepted for publication, 2008

Most optical character recognition (OCR) systems need to be trained and tested on the symbols that are to be recognized. Therefore, ground truth data is needed. This data consists of character images together with their ASCII code. Among the approaches for generating ground truth of real world data, one promising technique is to use electronic version of the scanned documents. Using an alignment method, the character bounding boxes extracted from the electronic document are matched to the scanned image. Current alignment methods are not robust to different similarity transforms. They also need calibration to deal with non-linear local distortions introduced by the printing/scanning process. In this paper we present a significant improvement over existing methods, allowing to skip the calibration step and having a more accurate alignment, under all similarity transforms. Our method finds a robust and pixel accurate scanner independent alignment of the scanned image with the electronic document, allowing the extraction of accurate ground truth character information. The accuracy of the alignment is demonstrated using documents from the UW3 dataset. The results show that the mean distance between the estimated and the ground truth character bounding box position is less than one pixel.

Navidgator - Similarity Based Browsing for Image & Video Databases

Wed, 06 Aug 2008 13:39:38 +0100

Damian Borth, Christian Schulze, Adrian Ulges, Thomas M. Breuel, KI 2008, 2008

A main problem with the handling of multimedia databases is the navigation through and the search within the content of a database. The problem arises from the difference between the possible textual description (annotation) of the database content and its visual appearance. Overcoming the so called - semantic gap - has been in the focus of research for some time. This paper presents a new system for similarity-based browsing of multimedia databases. The system aims at decreasing the semantic gap by using a tree structure, built up on balanced hierarchical clustering. Using this approach, operators are provided with an intuitive and easy-to-use browsing tool. An important objective of this paper is not only on the description of the database organization and retrieval structure, but also how the illustrated techniques might be integrated into a single system. Our main contribution is the direct use of a balanced tree structure for navigating through the database of keyframes, paired with an easy-to-use interface, offering a coarse to ﬁne similarity-based view of the grouped database content.

Binary Morphology and Related Operations on Run-Length Representations

Mon, 28 Jul 2008 09:28:31 +0100

Thomas M. Breuel, Proceedings VISAPP 2008, 2008

Binary morphology on large images is compute intensive, in particular for large structuring elements. Run-length encoding is a compact and space-saving technique for representing images. This paper describes how to implement binary morphology directly on run-length encoded binary images for rectangular structuring elements. In addition, it describes efficient algorithm for transposing and rotating run-length encoded images. The paper evaluates and compares run length morphologial processing on page images from the UW3 database with an efficient and mature bit blit-based implementation and shows that the run length approach is several times faster than bit blit-based implementations for large images and masks. The experiments also show that complexity decreases for larger mask sizes. The paper also demonstrates running times on a simple morphology-based layout analysis algorithm on the UW3 database and shows that replacing bit blit morphology with run length based morphology speeds up performance approximately two-fold.

The OCRopus Open Source OCR System

Mon, 10 Mar 2008 17:27:56 +0100

Thomas M. Breuel, Proceedings IS&T/SPIE 20th Annual Symposium 2008, 2008

OCRopus is a new, open source OCR system emphasizing modularity, easy extensibility, and reuse, aimed at both the research community and large scale commercial document conversions. This paper describes the current status of the system, its general architecture, as well as the major algorithms currently being used for layout analysis and text line recognition.

Segmentation of Curled Text Lines using Active Contours

Wed, 12 Nov 2008 16:40:55 +0100

Syed Saqib Bukhari, Faisal Shafait, Thomas M. Breuel, DAS, 2008

Segmentation of curled textlines from warped document images is one of the major issues in document image de- warping. Most of the curled textlines segmentation algo- rithms present in the literature today are sensitive to the degree of curl, direction of curl, and spacing between adja- cent lines. We present a new algorithm for curled textline segmentation which is robust to above mentioned problems at the expense of high execution time. We will demon- strate this insensitivity in a performance evaluation section. Our approach is based on the state-of-the-art image seg- mentation technique: Active Contour Model (Snake) with the novel idea of several baby snakes and their conver- gence in a vertical direction only. Experiment on publically available CBDAR 2007 document image dewarping contest dataset shows our textline segmentation algorithm accuracy of 97.96%.

Bayes Optimal DDoS Mitigation by Adaptive History-Based IP Filtering

Wed, 23 Apr 2008 16:34:09 +0100

Markus Goldstein, Christoph Lampert, Matthias Reif, Armin Stahl, Thomas M. Breuel, Proceedings of the Seventh International Conference on Networking (icn 2008), pages 174-179, 2008

Distributed Denial of Service (DDoS) attacks are today the most destabilizing factor in the global internet and there is a strong need for sophisticated solutions. We introduce a formal statistical framework and derive a Bayes optimal packet classifier from it. Our proposed practical algorithm "Adaptive History-Based IP Filtering" (AHIF) mitigates DDoS attacks near the victim and outperforms existing methods by at least 32% in terms of collateral damage. Furthermore, it adjusts to the strength of an ongoing attack and ensures availability of the attacked server. In contrast to other adaptive solutions, firewall rulesets used to resist an attack can be precalculated before an attack takes place. This ensures an immediate response in a DDoS emergency. For evaluation, simulated DDoS attacks and two real-world user traffic datasets are used.

Anomaly Detection by Combining Decision Trees and Parametric Densities

Mon, 08 Sep 2008 16:14:34 +0100

Matthias Reif, Markus Goldstein, Armin Stahl, Thomas M. Breuel, Pattern Recognition, 2008. ICPR 2008. 19th International Conference on, 2008

In this paper a modiﬁed decision tree algorithm for anomaly detection is presented. During the tree building process, densities for the outlier class are used directly in the split point determination algorithm. No artiﬁcial counter-examples have to be sampled from the unknown class, which yields to more precise decision boundaries and a deterministic classiﬁcation result. Furthermore, the prior of the outlier class can be used to adjust the sensitivity of the anomaly detector. The proposed method combines the advantages of classiﬁcation trees with the beneﬁt of a more accurate representation of the outliers. For evaluation, we compare our approach with other state-of-the-art anomaly detection algorithms on four standard data sets including the KDD-Cup 99. The results show that the proposed method performs as well as more complex approaches and is even superior on three out of four data sets.

Automatic Image Tagging using Community-Driven Online Image Databases

Mon, 18 Aug 2008 06:05:52 +0100

Marius Renn, Joost van Beusekom, Daniel Keysers, Thomas M. Breuel, Proceedings of 6th International Workshop on Adaptive Multimedia Retrieval, 2008

Automatic image tagging is becoming increasingly important to organize large amounts of image data. To identify concepts in images, these tagging systems rely on large sets of annotated image training sets. In this work we analyze image sets taken from online community-driven image databases, such as Flickr, for use in concept identification. Real- world performance is measured using our flexible tagging system, Tagr.

Evaluation of Graylevel-Features for Printing Technique Classiﬁcation in ...

Thu, 05 Jun 2008 15:52:03 +0100

Christian Schulze, Marco Schreyer, Armin Stahl, Thomas Breuel, IWCF 2008, 2008

The detection of altered or forged documents is an important tool in large scale office automation. Printing technique examination can therefore be a valuable source of information to determine a questioned documents authenticity. A study of graylevel features for high throughput printing technique recognition was undertaken. The evaluation included printouts generated by 49 different laser and 13 different inkjet printers. Furthermore, the extracted document features were classiﬁed using three different machine learning approaches. We were able to show that, under the given constraints of high-throughput systems, it is possible to determine the printing technique used to create a document.

Performance Evaluation and Benchmarking of Six Page Segmentation Algorithms

Thu, 08 May 2008 14:06:37 +0100

Faisal Shafait, Daniel Keysers, Thomas M. Breuel, IEEE Transactions on Pattern Analysis and Machine Intelligence 30(6), pages 941--954, 2008

Informative benchmarks are crucial for optimizing the page segmentation step of an OCR system, frequently the performance limiting step for overall OCR system performance. We show that current evaluation scores are insufficient for diagnosing specific errors in page segmentation and fail to identify some classes of serious segmentation errors altogether. This paper introduces a vectorial score that is sensitive to, and identifies, the most important classes of segmentation errors (over-, under-, and miss segmentation) and what page components (lines, blocks, etc.) are affected. Unlike previous schemes, our evaluation method has a canonical representation of ground truth data and guarantees pixel-accurate evaluation results for arbitrary region shapes. We present the results of evaluating widely used seg mentation algorithms (x-y cut, smearing, whitespace analysis, constrained text-line finding, docstrum, and Voronoi) on the UW-III database and demonstrate that the new evaluation scheme permits the identification of several specific flaws in individual segmentation methods.

GREC 2007 Arc Segmentation Contest: Evaluation of Four Participating Algorithms

Wed, 26 Mar 2008 14:19:40 +0100

Faisal Shafait, Daniel Keysers, Thomas M. Breuel, Graphics Recognition: Recent Advances and New Opportunities (GREC 2007 post-proceedings) Accepted for publication, 2008

Efficient Implementation of Local Adaptive Thresholding Techniques Using Integral Images

Tue, 18 Mar 2008 07:33:53 +0100

Faisal Shafait, Daniel Keysers, Thomas M. Breuel, Document Recognition and Retrieval XV, 2008

Adaptive binarization is an important first step in many doc- ument analysis and OCR processes. This paper describes a fast adaptive binarization algorithm that yields the same quality of binarization as the Sauvola method [1], but runs in time close to that of global thresholding methods (like Otsu's method [2]), independent of the window size. The algorithm combines the statistical constraints of Sauvola's method with integral images [3]. Testing on the UW-1 dataset demonstrates a 20-fold speedup compared to the original Sauvola algorithm.

Structural Mixtures for Statistical Layout Analysis

Thu, 07 Aug 2008 06:28:48 +0100

Faisal Shafait, Joost van Beusekom, Daniel Keysers, Thomas M. Breuel, Proc. 8th Int. Workshop on Document Analysis Systems (DAS) Accepted for publication, 2008

Background Variability Modeling for Statistical Layout Analysis

Thu, 07 Aug 2008 06:24:28 +0100

Faisal Shafait, Joost van Beusekom, Daniel Keysers, Thomas M. Breuel, Proc. 19th Int. Conf. on Pattern Recognition (ICPR) Accepted for publication, 2008

Rapid Prototyping of CBR Applications with the Open Source Tool myCBR

Mon, 16 Jun 2008 15:02:48 +0100

Armin Stahl, Thomas Roth-Berghofer, Proceedings of the 9th European Conference on Case-Based Reasoning (ECCBR 2008), 2008

Although Case-Based Reasoning (CBR) claims to reduce the effort required for developing knowledge-based systems substantially compared with more traditional Artificial Intelligence approaches, the implementation of a CBR application from scratch is still a time consuming task. In this paper we present a novel, freely available tool for rapid prototyping of CBR applications that focuses on the similarity-based retrieval step, like for example case-based product recommender systems. By providing easy to use model generation, data import, similarity modeling, explanation, and testing functionality together with comfortable graphical user interfaces, the tool enables even CBR novices to rapidly create their first CBR applications. Nevertheless, at the same time it ensures enough flexibility to enable expert users to implement advanced CBR applications.

Learning TRECVID'08 High-Level Features from YouTube

Mon, 27 Oct 2008 15:48:20 +0100

Adrian Ulges, Markus Koch, Christian Schulze, Thomas Breuel, TRECVID-Workshop (unreviewed workshop paper), 2008

We participated in TRECVID's High-level Features task to investigate online video as an alternative data source for concept detector training. Such video material is publicly available in large quantities from video portals like YouTube. In our setup, tags provided by users during upload serve as weak ground truth labels, and training can scale up to thousands of concepts without manual annotation effort. On the downside, online video as a domain is complex, and the labels associated with it are coarse and unreliable, such that performance loss can be expected compared to high-quality standard training sets. To find out if it is possible to train concept detectors on online video, our TRECVID experiments compare the same state-of-the-art (visual only) concept detection systems when (1) training on the standard TRECVID development data and (2) training on clips downloaded from YouTube. Our key observation is that youtube-based detectors work well for some concepts, but are overall significantly outperformed by the "specialized" systems trained on standard TRECVID'08 data (giving a infMAP of 2.2% and 2.1% compared to 5.3% and 6.1%). An in-depth analysis of the results shows that a major reason for this seems to be redundancy in the TV08 dataset.

Identifying Relevant Frames in Weakly Labeled Videos for Training Concept Detectors

Thu, 05 Jun 2008 16:54:42 +0100

Adrian Ulges, Christian Schulze, Daniel Keysers, Thomas Breuel, CIVR, 2008

A key problem with the automatic detection of semantic concepts (like `interview' or `soccer') in video streams is the manual acquisition of adequate training sets. Recently, we have proposed to use online videos downloaded from portals like youtube.com for this purpose, whereas tags provided by users during video upload serve as ground truth annotations. The problem with such training data is that it is weakly labeled: Annotations are only provided on video level, and many shots of a video may be "non-relevant", i.e. not visu- ally related to a tag. In this paper, we present a probabilistic framework for learning from such weakly annotated training videos in the presence of irrelevant content. Thereby, the rel- evance of keyframes is modeled as a latent random variable that is estimated during training. In quantitative experiments on real-world online videos and TV news data, we demonstrate that the proposed model leads to a significantly increased robustness with respect to irrelevant content, and to a better generalization of the re- sulting concept detectors.

Segmentation by Combining Parametric Optical Flow with a Color Model

Mon, 08 Sep 2008 08:44:16 +0100

Adrian Ulges, Thomas M. Breuel, ICPR'08, 2008

We present a simple but efficient model for object segmentation in video scenes that integrates motion and color information in a joint probabilistic framework. Optical flow is modeled using parametric motion with Gaussian noise. The color distribution of foreground and background is described by histograms or Gaus- sian mixture models. Optimization is carried out using an efficient graph cut algorithm. In quantitative experiments on a variety of video data, we demonstrate that the proposed approach leads to significant reductions in error rates compared to a state-of-the-art motion-only segmentation.

Multiple Instance Learning from Weakly Labeled Videos

Mon, 27 Oct 2008 15:52:38 +0100

Adrian Ulges, Christian Schulze, Thomas Breuel, SAMT Workshop on Cross-media Information Analysis, Extraction and Management, 2008

Automatic video tagging systems are targeted at assigning semantic concepts ("tags") to videos by linking textual descriptions with the audio-visual video content. To train such systems, we investigate online video from portals such as youtube as a large-scale, freely available knowledge source. Tags pro- vided by video owners serve as weak annotations indicating that a target concept appears in a video, but not when it appears. This situation resembles the multiple instance learning (MIL) scenario, in which classifiers are trained on labeled bags (videos) of unlabeled samples (the frames of a video). We study MIL in quantitative, large-scale experiments on real-world online videos. Our key findings are: (1) conventional MIL tends to neglect valuable informa- tion in the training data and thus performs poorly. (2) By relaxing the MIL as- sumption, a tagging system can be built that performs comparable or better than its supervised counterpart. (3) Improvements by MIL are minor compared to a kernel-based model we proposed recently.

A System that Learns to Tag Videos by Watching Youtube

Fri, 15 Feb 2008 14:00:57 +0100

Adrian Ulges, Christian Schulze, Daniel Keysers, Thomas Breuel, International Conference on Computer Vision Systems, 2008

We present a system that automatically tags videos, i.e. de- tects high-level semantic concepts like objects or actions in them. To do so, our system does not rely on datasets manually annotated for re- search purposes. Instead, we propose to use videos from online portals like youtube.com as a novel source of training data, whereas tags pro- vided by users during upload serve as ground truth annotations. This allows our system to learn autonomously by automatically downloading its training set. The key contribution of this work is a number of large-scale quantita- tive experiments on real-world online videos, in which we investigate the influence of the individual system components, and how well our tagger generalizes to novel content. Our key results are: (1) Fair tagging results can be obtained by a late fusion of several kinds of visual features. (2) Using more than one keyframe per shot is helpful. (3) To generalize to different video content (e.g., another video portal), the system can be adapted by expanding its training set.