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 the alignment is performed between the input line image to a synthetic one. The energy function works at a connected component level and it combines a visual similarity measure and a learned distance metric that separates between inter-word and intra-word connected components.

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 the segmentation by formulating the problem as an energy minimization task and achieving the minimum using graph cuts. The energy function is derived from properties of the text components. Spatial coherence of the segmented text regions is explicitly encouraged by the energy function. We evaluate the suggested method on a publicly available dataset of 38 historical document images. Experiments show that the suggested approach outperforms another state-of-the-art page segmentation method in terms of segmentation quality and time performance.

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 annotating degraded documents.

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 is done by analyzing the evolution maps of connected components obtained by a sliding threshold. The detected potential characters are grouped into text lines in the second stage using sweep-line approach. The suggested method is especially powerful when applied to torn and damaged documents that other algorithms are not able to deal with.

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 scale threshold. We use these maps to provide a robust algorithm for extracting information about character dimensions in degraded documents, and demonstrate improvement in binarization results using this information. We analyze statistically the characteristics of the evolution maps for text documents, and compare our results with ground truth data.

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 on the fragments of the Hebrew letters and select the k candidate letters that match best the fragments of the Hebrew letters. We then complete the broken Hebrew characters using active contour with the k candidates as shape priors. We use a modified geodesic active contour, which we tailored to occluded text restoration. It is initialized on the fragments of the Hebrew text, then it undergoes an expansion phase and a contraction phase via the occluding Arabic text to form the restored Hebrew character. We measure the distance between the completed character and its corresponding priors and choose the shape with the minimal distance as the reconstructed character. Experimental results are presented. On average 68% of the characters were correctly reconstructed.

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 a range of known features using a Dynamic Time Warping algorithm. In addition we describe a novel meth od for feature-based searching, which uses a number of models for the same character. This method is based on our original DTW algorithm that can match fragments of several models of the same character to match a query character. Consequently, we are not limited to any particular model of the character set. Application of this method leads to a significant improvement, even when using a small set of models.

We propose a novel approach for text line segmentation based on adaptive local projection profiles. Our algorithm is suitable for degraded documents with text lines written in large skew. The main novelty of our approach is applying the local algorithm in an incremental manner that adapts to the skew of each text line as it progresses. The proposed approach achieves very accurate results on a set of degraded documents with lines written in different skew angles and curvatures.

Document skew estimation is an important step in the process of document analysis. In this paper we discuss the properties of the distance transform of binarized documents and derive a fast and accurate method for detecting document skew. The method is based on the observation that the dominant orientation of the gradient of the distance transform accurately reflects the skew of the document. Our experiments suggest the method is robust to large variations in text properties, such as difference in script and page layout, and provides estimation accuracy of state-of-the-art skew detection methods.

We present a a statistical approach to skew detection, where the textual features of a document image are modeled as a mixture of straight lines in Gaussian noise. The EM algorithm is used to estimate the parameters of the mixture model and the skew angle estimate is extracted from the estimated parameters. Experiments prove that our method has some advantages over other existing methods in terms of accuracy and efficiency.

This paper presents a method for automatic extraction of certain pre-specified objects from binary images. The method is applied to letters from historic Hebrew manuscripts and is based on object based erosion transform. The extraction method deals very well with common problems of historical documents, such as broken or merged characters, and can be applied to different writing styles. An average correct extraction rate of 96% is achieved.

Resolution enhancement of an image from a sequence of digital images is possible only if aliasing effects are present. We address the issue of detecting presence of aliasing within a digital image sequence. Given two digital images of the same scene with sub-pixel relative translation between them, we examine the absolute difference between the interpolated versions of these images. If the two images contain no aliasing effects, the difference between them will be random, solely due to noise. If aliasing is present, the difference between the two interpolated images will be highly correlated to the high-frequency elements of each interpolated image. An algorithm for the detection of the presence of aliasing based on this phenomenon is proposed. This algorithm is also able to estimate the extent of aliasing.

A method for resolution enhancement of image sequences by polyphase back-projection filtering is presented. The first super-resolution image is initialized by interpolation of the first low-resolution image. The imaging system is simulated for every super-resolution image at a time, and the error between the simulated image and the corresponding low-resolution image is calculated. The resolution enhancement is achieved by back-projecting this error to the corresponding super-resolution image. The imaging system's PSF and the back-projection filter are estimated with a resolution higher than that of the super-resolution images, and the filtering is done by polyphase versions of these filters. The polyphase filters have embedded sub-pixel displacements corresponding to the translation parameters between the super-resolution image and the low-resolution one. The use of the polyphase filters allows exploitation of the observed data without any smoothing and/or interpolation operations. Also, no modeling of the PSF by an analytical function is necessary. Presented experimental results show encouraging resolution enhancements.

Motion estimation within an ultrasound image sequence can be performed in several manners. When using block-matching technique with the maximum likelihood (ML) estimator, one would try to match a block from the first image with a block in the second image, within a predefined search area. The estimated motion vector is the one maximizing a likelihood function, formulated according to the image formation model. Until now, either the classical L/sup 1/ and L/sup 2/ norms or a model in which only one image is noisy have been used for motion estimation in ultrasound images. Two new ML motion estimation schemes that are suitable for estimating the motion between noisy ultrasound images are presented. The proposed likelihood functions are based on the assumption that both images contain by a Rayleigh distributed multiplicative noise. Presented experimental results show an improvement in the motion estimation compared to other known ML motion estimation methods.

The method for reconstruction and restoration of super resolution images from low resolution sequences presented is an extension of Irani and Peleg's (1991) algorithm . The input is a set of low resolution images that have been registered to a pixel translation accuracy. A high resolution image is initialized and iteratively improved by back-projecting the errors between the low resolution images and the respective images obtained by simulating the imaging system. The sub-pixel translations between the low resolution images are quantized. The imaging system's PSF and back-projection function are estimated with a resolution higher than that of the super resolution image and decimated so that two banks of polyphase filters are obtained. The use of the polyphase filters allows exploitation of all the input images without any smoothing or interpolation operations.

This paper describes a method for producing a sequence of higher resolution images from a sequence of low-resolution images containing sub-pixel shifts. This is possible in cases where aliasing is caused by the digitization process, and images of the low-resolution video sequence contain slightly different, but unique, information. The motion estimation is obtained by the respective group delays of local adaptive filters for optimal linear prediction. The main idea of the proposed iterative super resolution algorithm is that each high-resolution frame in the output sequence is generated from the previous high-resolution frame and a correction image. The correction image is the back projected filtered difference between the observed low-resolution image and the image obtained from the previous high-resolution frame using a simulation of the imaging system.

Given a sequence of blurred low resolution images, the aim of this work is to produce a sequence of higher resolution and restored images. It is assumed that the point spread function of the given imaging process is a combination of a known blurring function and an estimated local motion function. The local motion estimation is obtained by the respective group delays of local adaptive filters. Preliminary experimental results are presented.

A common task in cytogenetic tests is the classification of human chromosomes. Successful separation between touching and overlapping chromosomes in a metaphase image is vital for correct classification. Current systems for automatic chromosome classification are mostly interactive and require human intervention for correct separation between touching and overlapping chromosomes. Since chromosomes are nonrigid objects, special separation methods are required to segregate them. Common methods for overlapping chromosomes separation between touching chromosomes tend to fail where ambiguity or incomplete information are involved, and so are unable to segregate overlapping chromosomes. The proposed approach treats the separation problem as an identification problem, and, in this way, manages to segregate overlapping chromosomes. This approach encompasses low-level knowledge about the objects and uses only extracted information, therefore, it is fast and does not depend on the existence of a separating path. The method described in this paper can be adopted for other applications, where separation between touching and overlapping nonrigid objects is required.

Directional information has a strong meaning in line-drawing images. Therefore, the proposed approach for line-drawing images processing is based on a directional decomposition of the input image into a set of images each containing line segments in a respective range of directions. The directional information is then processed by using newly defined directional morphological operators, called tube-directional, that have accurate selectivity and controllable strictness. When using morphological operators, adaptation to a specific task is achieved only globally by setting the structure of the morphological kernel. The concept of one global adjustment for many local operations is some how conflicting. In the proposed approach the parameters of the tube-directional morphological operators are determined locally for each element of the processed image.

A fast, reliable, and objective system for computerized classification of color textured perthite images is proposed. Computerized classification of perthite textures enables large scale comparative perthite texture studies. In order to locate a perthite crystal's borders, color and texture features are combined in a pixel classification segmentation operation, followed by probabilistic relaxation. A new operator based on vertical-horizontal run length ratios is used in order to identify and separate vein elements. Joint patch elements are disconnected using an iterative procedure that locates patch cores. After the geometrical properties are extracted, the desired distribution of the perthite texture elements is computed. Experimental classification results are presented and compared to expert manual classification.

Feature extraction for exploratory data projection aims for data visualization by a projection of a high-dimensional space onto two or three-dimensional space, while feature extraction for classification generally requires more than two or three features. We study extraction of more than three features, using neural network (NN) implementation of Sammon's mapping to be applied for classification. The experiments reveal that Sammon's mapping, the multilayer perceptron (MLP) and the principal component analysis (PCA) based feature extractors yield similar classification performance. We investigate a random- and PCA-based initializations of Sammon's mapping. When the PCA is applied to initialize Sammon's projection, only one experiment is required and only a fraction of the training period is needed to achieve performance comparable with that of the random initialization. Furthermore, the PCA based initialization affords better human chromosome classification performance even when using a few eigenvectors.

The use of computer aided design requires line drawings and maps to be digitized and stored in databases. The input of line drawings and maps into databases requires vectorization of lines, and recognition of symbols and characters. The paper addresses two aspects related to the input process. The first aspect is an automatic algorithm for the separation of character strings from maps. The second aspect is an algorithm for line thinning. The proposed algorithms are based on directional morphology operations. The character string extraction algorithm is independent of font style, size, and language and is suitable for a variety of map styles with straight or curved lines. The presented experimental results demonstrate very good performance of the algorithms even in cases where the character strings touch or intersect lines in the map.

A multilayer perceptron (MLP) neural network (NN) has been studied for human chromosome classification. Only 10-20 examples were required for the MLP NN to reach its ultimate performance classifying chromosomes of 5 types. The empirical dependence of the entropic error on the number of examples was found to be highly comparable to the 1/t function. The principal component analysis (PCA) was used, both for network initialization and for feature reduction purposes. The PCA demonstrated the importance of retaining most of the image information whenever small training sets are used. The MLP NN classifier outperformed the Bayes piecewise classifier for all the cases tested. The MLP classifier was found to be almost unsusceptible to the ratio of the number of training vectors to the number of features, whereas the piecewise classifier was highly dependent on this ratio.

A multilayer perceptron (MLP) neural network (NN) was used for human chromosome classification. The significance of relevant chromosome features to the classification procedure was evaluated using a feature selection mechanism. It yielded the benefit of using only a part of the available features to get performance close to the ultimate one, classifying chromosomes of 5 types. Only 10-20 examples were required for the MLP NN classifier to reach its supreme performance disregarding the number of features used. Furthermore, the empirical entropic error of the classifier was found to be highly comparable to the 1/t function that is a universal learning curve.

An algorithm for optimal polygonal approximation is presented. Given a value for the maximal allowed distance between the approximation and the curve, the algorithm finds an approximation with the minimal number of vertices. The city-block metric is used to measure the distance between the approximation and the curve. The algorithm worst case complexity is O(n/sup 2/) where n is the number of points in the curve. This complexity is attractive compared to the complexity of other algorithms for optimal approximations. An efficient and optimal solution for the case of closed curves where no initial point is given, is also presented.

This correspondence presents an algorithm for smoothed polygonal approximation of noisy digital planar curves, and feature point detection. The resulting smoothed polygonal representation preserves the signs of the curvature function of the curve. The algorithm is based on a simple decomposition of noisy digital curves into a minimal number of convex and concave sections. The location of each separation point is optimized, yielding the minimal possible distance between the smoothed approximation and the original curve. Curve points within a convex (concave) section are discarded if their angle signs do not agree with the section sign, and if the resulted deviations from the curve are less than a threshold /spl epsi/, which is derived automatically. Inflection points are curve points between pairs of convex-concave sections, and cusps are curve points between pairs of convex-convex or concave-concave sections. Corners and points of local minimal curvature are detected by applying the algorithm to respective total curvature graphs. The detection of the feature points is based on properties of pairs of sections that are determined in an adaptive manner, rather than on properties of single points that are based on a fixed-size neighborhood. The detection is therefore reliable and robust. Complexity analysis and experimental results are presented.>

This paper presents a technique for image pyramid generation, in which the reduction (expansion) factor between layers is any rational number M/L. The image pyramid generation is modeled as an interpolation and filtering followed by a decimation. The model enables frequency domain analysis of the image pyramid, as well as convenient design of the generating kernels. L(M) generating kernels are necessary to produce an image pyramid with reduction (expansion) factor M/L(L/M). A polyphase filter network scheme is used where the L(M) generating kernels can be produced by sampling one prototype low-pass filter with cutoff frequency at omega = pi /max(M,L). Using these polyphase filters, the frequency content of pyramid image decompositions can be adjusted with great flexibility. A systematic procedure is presented here for specifying the relative positions of spatial samples in successive pyramid levels-a complication that arises when generalizing from integer reduction factors to rational factors. Two types of low-pass filters are employed in this work for the prototype filter design: a binomial filter and an FIR linear phase filter. Illustrative examples are presented.>

Multiclass 2-D mapping oriented to classification of multivariate data is discussed. Parametric and nonparametric mapping criteria are used for single level (one shot) projections. A method for reducing the computation complexity of the optimization procedure is suggested.>

A parallel computation approach to two-dimensional shape recognition is proposed and illustrated. The approach uses parallel techniques for contour extraction, parallel computation of normalized contour-based feature strings independent of scale and orientation, and parallel string-matching algorithms. The string matching can be applied in a manner independent of rotation. An implementation on the exclusive read, exclusive write parallel random access memory (EREW PRAM) architecture is discussed, but it can be adapted to other parallel architectures. An illustrated example is presented.>

A discrete cosine transform image coding scheme based on adaptive block size is proposed and demonstrated. The scheme adaptively optimizes the block sizes according to some local activity indexes of the image scenes. The optimization is achieved by applying the technique from graph theory. Nine rectangular block sizes are used, corresponding to all combinations of 8, 16, and 32 pixels per side. This approach reduces interblock correlation between coefficients, and increases the energy compaction in the transform domain. Experimental results are presented and compared to results obtained by an identical coder using a fixed block size.>

An image coding method for low bit rates is proposed. It is based on alternate use of the discrete cosine transform (DCT) and the discrete sine transform (DST) on image blocks. This procedure achieves the removal of redundancies in the correlation between neighboring blocks as well as the preservation of continuity across the block boundaries. An outline of the mathematical justification of the method, assuming a certain first-order Gauss-Markov model, is given. The resulting coding method is then adapted to nonstationary real images by locally adapting the model parameters and improving the block classification technique. Simulation results are shown and compared with the performance of related previous methods, namely adaptive DCT and fast Karhunen-Loeve transform (FKLT).>

The possibility of integrating human visual intelligence into the process of encrypting sensitive information by presenting certain visual information to the recipient's eye is discussed. This adds a new dimension to the cryptocomplexity of such a process. Two implementations are based on this principle are described. The first shows how keys used for encryption can be randomly generated by the transmitter, without the necessity of exchanging them with the legitimate recipient. The keys are 'embedded' in a master key and are recovered from it by the intelligence of the legitimate recipient after he or she uses the master key. No human intelligence can be helpful to a user who does not possess the master key. The second implementation concerns the possibility of creating a secret connection between a numerical key and a specific image (e.g. a face). Such a scheme can be used, for example, in validating the identity of the users of credit cards.>

An approach to stereo image compression based on disparity compensation is proposed and evaluated. The scheme is motivated by the suppression theory in human vision. A methodology for evaluating compressed stereo images is proposed. It is based on time measurements of depth perception tasks performed by human subjects. Subjects taking part in the experiment were exposed to displays of stereo images, some of which had been compressed, and were asked to judge the relative depth within each display as fast as possible. Decision times were measured and used as the major dependent variable. It was found that very deep compression of one of the images of a stereo pair does not interfere with the perception of depth in the stereo image.>

A discrete cosine transform image-coding scheme based on adaptive block size is proposed and demonstrated. The scheme adaptively optimizes the block sizes according to some local activity indices of the image scenes. The optimization algorithm is achieved by applying a technique from graph theory. Nine rectangular block sizes are used, corresponding to all combinations of 8, 16, and 32, pixels per side. The approach reduces interblock correlation between coefficients and increases the energy compaction in the transform domain. Experimental results are presented and compared to results obtained by an identical coder using a fixed block size.>

In this correspondence, some image transforms and features such as projections along linear patterns, convex hull approximations, Hough transform for line detection, diameter, moments, and principal components will be considered. Specifically, we present algorithms for computing these features which are suitable for implementation in image analysis pipeline architectures. In particular, random access memories and other dedicated hardware components which may be found in the implementation of classical techniques are not longer needed in our algorithms. The effectiveness of our approach is demonstrated by running some of the new algorithms in conventional short-pipelines for image analysis. In related papers, we have shown a pipeline architecture organization called PPPE (Parallel Pipeline Projection Engine), which unleashes the power of projection-based computer vision, image processing, and computer graphics. In the present correspondence, we deal with just a few of the many algorithms which can be supported in PPPE. These algorithms illustrate the use of the Radon transform as a tool for image analysis.

This paper deals with the problem of computing, projections of digital images. The novelty of our contribution is that we present algorithms which are suitable for implementation in general purpose image processing and image analysis pipeline architectures. Also, we propose some new pipeline configurations which achieve a remarkable degree of parallelism in the computation of projection data and in fact, of many other geometrical descriptors of digital images. In particular, random access memories and other dedicated hardware devices are not needed in our algorithms. The effectiveness of our approach and feasibility of the proposed architectures are demonstrated by running our algorithms in commercially available short-pipelines for image processing and analysis. Examples are shown of the use of projection data for machine vision applications.

The storage requirements for component labeling and feature extraction operations are unknown a priori. Whenever large images are processed, many labels, and thus a large amount of storage, may be required, making hardware implementation difficult. The proposed labeling procedure eliminates memory overflow by enabling the reuse of memory locations in which features of nonactive labels had been stored. The storage requirement for the worst case conditions is analyzed and is shown to be realizable. The basic procedure can be implemented in two modes, an interrupted mode or a parallel mode. A hardware design is presented.

Shading correction of image sensors is a very important operation in visual inspection applications. The generation and application of shading correction with and without imaging system response linearization is discussed and demonstrated. The linearization is achieved by subtracting the dark current image and by applying a lookup table operation. The content of the lookup table is obtained by fitting an analytical function to the measured system response. The linearization enables the shading correction to be a linear operation. The quality of the linearization and the shading correction was evaluated using statistical parameters of the processed images. The results showed a substantial decrease in the standard deviation of the gray level distribution of uniform reference images.

The concept of planes spanned ions of signal phase plane is generalized to by various nonlinear combinat-derivatives. Such combinations, based on the relative first and second derivatives of signals, are defined and illustrated. A method for feature extraction is proposed and applied to a simple example of handwritten numeral recognition.

Texture is one of the important characteristics used in identifying objects or regions of interest in an image, whether the image be a photomicrograph, an aerial photograph, or a satellite image. This paper describes some easily computable textural features based on gray-tone spatial dependancies, and illustrates their application in category-identification tasks of three different kinds of image data: photomicrographs of five kinds of sandstones, 1:20 000 panchromatic aerial photographs of eight land-use categories, and Earth Resources Technology Satellite (ERTS) multispecial imagery containing seven land-use categories. We use two kinds of decision rules: one for which the decision regions are convex polyhedra (a piecewise linear decision rule), and one for which the decision regions are rectangular parallelpipeds (a min-max decision rule). In each experiment the data set was divided into two parts, a training set and a test set. Test set identification accuracy is 89 percent for the photomicrographs, 82 percent for the aerial photographic imagery, and 83 percent for the satellite imagery. These results indicate that the easily computable textural features probably have a general applicability for a wide variety of image-classification applications.

In many remote sensing applications millions of measurements can be made from a satellite at one time, and many times the data is of marginal value. In these situations clustering techniques might save much data transmission without loss of information since cluster codes may be transmitted instead of multidimensional data points. Data points within a cluster are highly similar so that interpretation of the cluster code can be meaningfully made on the basis of knowing what sort of data point is typical of those in the cluster. We introduce an iterative clustering technique; the procedure suboptimally minimizes the probability of differences between the binary reconstructions from the cluster codes and the original binary data. The iterative clustering technique was programmed for the GE 635 KANDIDATS (Kansas Digital Image Data System) and tested on two data sets. The first was a multi-image set. Twelve images of the northern part of Yellowstone Park were taken by the Michigan scanner system, and the images were reduced and run with the program. Thirty-thousand data points, each consisting of a binary vector of 25 components, were clustered into four clusters. The percentage difference between the components of the reconstructed binary data and the original binary data was 20 percent. The second data set consisted of measurements of the frequency content of the signals from lightning discharges. One hundred and thirty-four data measurements, each consisting of a binary vector of 32 components, were clustered into four clusters.