The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We define and prove properties of the consensus shape for a protein family, a protein-like structure that provides a compact summary of the significant structural information for a protein family. If all members of the protein family exhibit a geometric relationship between corresponding -carbons, then that relationship is preserved in the consensus shape. In particular, distances and angles that...
We show that, using the L∞ metric, the minimum Hausdorff distance under translation between two point sets of cardinality n in d-dimensional space can be computed in time O(n(4d−2)/3 log2n) for d>3. Thus we improve the previous time bound of O(n2d−2 log2n) due to Chew and Kedem. For d=3 we obtain a better result of O(n3 log2 ...
We consider the following geometric pattern matching problem: find the minimum Hausdorff distance between two point sets under translation with L1 or L∞ as the underlying metric. Huttenlocher, Kedem, and Sharir have shown that this minimum distance can be found by constructing the upper envelope of certain Voronoi surfaces. Further, they show that if the two sets are each of...
Given a set P of n points in the plane, we seek two squares whose center points belong to P, their union contains P, and the area of the larger square is minimal. We present efficient algorithms for three variants of this problem: In the first the squares axe axis parallel, in the second they are free to rotate but must remain parallel to each other, and in the third they are free to rotate independently.
We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the k rectilinear nearest neighbors to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0 report all the pairs of points...
Conformational polymorphs are identical molecules that crystallize in different spatial formations. Understanding the amount of difference between the polymorphs might aid drug design as there is a widespread assumption that there exists a direct connection between the conformations in the crystallized form of the molecule and the conformations in the solvent. We define a measure of similarity...
In this paper we apply the selection and optimization technique of Fredrickson and Johnson to a number of geometric selection and optimization problems, some of which have previously been solved by parametric search, and provide efficient and simple algorithms. Our technique improves the solutions obtained by parametric search by a log n factor. For example, we apply the technique to the two-line-center...
We present efficient algorithms for two problems of facility location. In both problems we want to determine the location of a single facility with respect to n given sites. In the first we seek a location that maximizes a weighted distance function between the facility and the sites, and in the second we find a location that minimizes the sum (or sum of the squares) of the distances of k of the sites...
We propose a pyramid-based method for keyword spotting in historical document images. The documents are represented by a scale-space pyramid of their features. The search for a query keyword begins at the highest level of the pyramid, where the initial candidates for matching are located. The candidates are further refined at each level of the pyramid. The number of levels is adaptive and depends...
Complex document layouts pose prominent challenges for document image understanding algorithms. These layouts impose irregularities on the location of text paragraphs which consequently induces difficulties in reading the text. In this paper we present a robust framework for analyzing historical manuscripts with complex layouts. This framework aims to provide a convenient reading experience for historians...
An ongoing considerable effort for digitizing historical manuscripts has produced images of original manuscripts, some accompanied by transcripts. Aligning the text in the input image with the text in the transcript will allow learning, training and evaluating recognition algorithms. Here we propose a system that computes the alignment by formulating the problem as an energy minimization task, where...
In this paper, we present a novel scheme for subdividing a pictorial representation of a word or word-part into a sequence of blobs, that resemble the stroke representing the word. These blobs are generated by applying a bank of Gabor filters that capture the width of the strokes in multiple directions and segment the strong response regions. From the resulting blobs we extract representative features...
Many applications along the manuscript analysis pipeline rely on the accuracy of pre-processing steps. Perfectly detecting the main text area in ancient historical documents is of great importance for these applications. We propose a learning-free approach to detect the main text area in ancient manuscripts. First, we coarsely segment the main text area by using a texture-based filter. Then, we refine...
We study the effect of language orthographic characteristics on the performance of digital word recognition in degraded documents such as historical documents. We provide a rigorous scheme for quantifying the influence of the orthographic characteristics on the quality of word recognition in such documents. We study and compare several orthographic characteristics for four natural languages and measure...
Most of the algorithms proposed for text line detection are designed to process binary images as input. For severely degraded documents, binarization often introduces significant noise and other artifacts. In this work we present a novel method designed to detect text lines directly in gray scale images. The method consists of two stages. Potential characters are detected in the first stage. This...
We present WebGT, the first web-based system to help users produce ground truth data for document images. This user-friendly software system helps historians and computer scientists collectively annotate historical documents. It supports real time collaboration among remote sites independent of the local operating system and also provides several novel semi-automatic tools that have proven effective...
For highly degraded text documents, common tasks such as binarization and line extraction, remain difficult tasks. Equipped with a reliable information regarding the distribution of character dimensions in the document, one can improve results of these algorithms significantly. We introduce a novel perspective of the image data which maps the evolution of connected components along the change in gray...
Broken or partially visible characters is common phenomenon in historical documents. It stems from various factors, such as overlaid text or degradation. Restoring such characters is necessary for document analysis applications. This paper presents a new approach for restoring underlaying Hebrew broken characters that were partially occluded by Arabic text in a palimpsest. We apply text recognition...
Searching for a letter or a word in historical documents is a practical challenge due to the various degradations present in such documents and the wide variance of handwriting. Searching in historical Hebrew documents is somewhat harder because of high similarities among Hebrew characters. In order to determine the features and their combinations appropriate for recognizing Hebrew script, we study...
In this paper, we present a vision-based approach for transmitting virtual models for Augmented Reality, which we name In-Place Augmented Reality (IPAR). A two-dimensional representation of the virtual models is embedded in a printed image. We apply computer vision techniques to interpret the printed image and extract the virtual models, which are then overlaid on the printed image. The main advantages...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.