Modern web search engines are federated --- a user query is sent to the numerous specialized search engines called verticals like web (text documents), News, Image, Video, etc. and the results returned by these engines are then aggregated and composed into a search result page (SERP) and presented to the user. For a specific query, multiple verticals could be relevant, which makes the placement of these vertical results within blocks of textual web results challenging: how do we represent, assess, and compare the relevance of these heterogeneous entities?

Modern day federated search engines aggregate heterogeneous types of results from multiple vertical search engines and compose a single search engine result page (SERP). The search engine aggregates the results and produces one ranked list, constraining the vertical results to specific slots on the SERP.

Eye tracking experiments have shown that titles of Web search results play a crucial role in guiding a user's search process. We present a machine-learned algorithm that trains a boosted tree to pick the most relevant title for a Web search result. We compare two modeling approaches: i) using absolute editorial judgments and ii) using pairwise preference judgments. We find that the pairwise modeling approach gives better results in terms of three offline metrics. We present results of our models in four regions. We also describe a hybrid user satisfaction evaluation process -- search success -- that combines page relevance and user click behavior, and show that our machine-learned algorithm improves in search success.

Readability is a crucial presentation attribute that web summarization algorithms consider while generating a querybaised web summary. Readability quality also forms an important component in real-time monitoring of commercial search-engine results since readability of web summaries impacts clickthrough behavior, as shown in recent studies, and thus impacts user satisfaction and advertising revenue.

Computer vision software is complex, involving many tens of thousands of lines of code. Coding mistakes are not uncommon. When the vision algorithms are run on controlled data which meet all the algorithm assumptions, the results are often statistically predictable. This renders it possible to statistically validate the computer vision software and its associated theoretical derivations. In this paper, we review the general theory for some relevant kinds of statistical testing and then illustrate this experimental methodology to validate our building parameter estimation software. This software estimates the 3D positions of buildings vertices based on the input data obtained from multi-image photogrammetric resection calculations and 3D geometric information relating some of the points, lines and planes of the buildings to each other.

Noise models are crucial for designing image restoration algorithms, generating synthetic training data, and predicting algorithm performance. There are two related but distinct estimation scenarios. The first is model calibration, where it is assumed that the input ideal bitmap and the output of the degradation process are both known. The second is the general estimation problem, where only the image from the output of the degradation process is given. While researchers have addressed the problem of calibration of models, issues with the general estimation problems have not been addressed in the literature. In this paper, we describe a parameter estimation algorithm for a morphological, binary, page-level image degradation model. The inputs to the estimation algorithm are 1) the degraded image and 2) information regarding the font type (italic, bold, serif, sans serif). We simulate degraded images using our model and search for the optimal parameter by looking for a parameter value for which the local neighborhood pattern distributions in the simulated image and the given degraded image are most similar. The parameter space is searched using a direct search optimization algorithm. We use the p-value of the Kolmogorov-Smirnov test as the measure of similarity between the two neighborhood pattern distributions. We show results of our algorithm on degraded document images.

Structural information about a document is essential for structured query processing, indexing, and retrieval. A document page can be partitioned into a hierarchy of homogeneous regions such as columns, paragraphs, etc.; these regions are called physical components, and define the physical layout of the page. In this paper we develop a class of models for the physical layouts of technical paper title pages. We model physical layout using hidden semiMarkov models for directional projections of page regions, and a stochastic attributed K-d tree grammar model for the 2D hierarchical structure of these regions. We use the models to generate sets of synthetic title page images of three distinctive styles, which we use in controlled experiments on page structure analysis.

Most relational query optimizers make use of information about the costs of accessing tuples and data structures on various storage devices. This information can at times be off by several orders of magnitude due to human error in configuration setup, sudden changes in load, or hardware failure. In this paper, we attempt to answer the following questions:• Are inaccurate access cost estimates likely to cause a typical query optimizer to choose a suboptimal query plan?• If an optimizer chooses a suboptimal plan as a result of inaccurate access cost estimates, how far from optimal is this plan likely to be?To address these issues, we provide a theoretical, vector-based framework for analyzing the costs of query plans under various storage parameter costs. We then use this geometric framework to characterize experimentally a commercial query optimizer. We develop algorithms for extracting detailed information about query plans through narrow optimizer interfaces, and we perform the characterization using database statistics from a published run of the TPC-H benchmark and a wide range of storage parameters.We show that, when data structures such as tables, indexes, and sorted runs reside on different storage devices, the optimizer can derive significant benefits from having accurate and timely information regarding the cost of accessing storage devices.

This paper describes Seeker, a platform for large-scale text analytics, and SemTag, an application written on the platform to perform automated semantic tagging of large corpora. We apply SemTag to a collection of approximately 264 million web pages, and generate approximately 434 million automatically disambiguated semantic tags, published to the web as a label bureau providing metadata regarding the 434 million annotations. To our knowledge, this is the largest scale semantic tagging effort to date.We describe the Seeker platform, discuss the architecture of the SemTag application, describe a new disambiguation algorithm specialized to support ontological disambiguation of large-scale data, evaluate the algorithm, and present our final results with information about acquiring and making use of the semantic tags. We argue that automated large scale semantic tagging of ambiguous content can bootstrap and accelerate the creation of the semantic web.

Image segmentation is an important component of any document image analysis system. While many segmentation algorithms exist in the literature, very few i) allow users to specify the physical style, and ii) incorporate user-specified style information into the algorithm's objective function that is to be minimized. We describe a segmentation algorithm that models a document's physical structure as a hierarchical structure where each node describes a region of the document using a stochastic regular grammar. The exact form of the hierarchy and the stochastic language is specified by the user, while the probabilities associated with the transitions are estimated from groundtruth data. We demonstrate the segmentation algorithm on images of bilingual dictionaries.

In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+ε)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-ε). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.

Parsing bilingual dictionaries is important for building cross-language retrieval systems and speech recognition algorithms. We describe a general purpose algorithm that can be easily modified to convert printed bilingual dictionaries in various layouts and language pairs into electronic/symbolic lexicons. In a previous paper [SPIE Document Recognition and Retrieval, San Jose, January 2002], we described an algorithm for segmenting the physical layout of dictionaries into columns and lines. In this paper we assume that the physical lines are given then recognize the lines that constitute a dictionary item. Furthermore, the algorithm simultaneously recognizes the logical structure within the dictionary items (head-word, pronounciation, part of speech and definition). We demonstrate our algorithm on 30 scanned Chinese-English dictionary pages which include more than 2500 lexicon items.

In k-means clustering, we are given a set of n data points in d-dimensional space R/sup d/ and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation.

Noise models are crucial for designing image restoration algorithms, generating synthetic training data, and predicting algorithm performance. However, to accomplish any of these tasks, an estimate of the degradation model parameters is essential. We describe a parameter estimation algorithm for a morphological, binary image degradation model. Inputs to the estimation algorithm are the ideal and degraded images. We search for the optimal parameter by looking for a parameter value for which the corresponding noise pattern distribution in the simulated image and the given degraded image are most similar. The parameter space is searched using the downhill simplex algorithm of Nelder and Mead (1965). We use the p-value of the Kolmogorov-Smirnov test of difference between the two pattern distributions as the objective function value. We show results of applying our algorithm on document images.

Document images undergo various degradation processes. Numerous models of these degradation processes have been proposed in the literature. In this paper we propose a model-based restoration algorithm. The restoration algorithm first estimates the parameters of a degradation model and then uses the estimated parameters to construct a lookup table for restoring the degraded image. The estimated degradation model is used to estimate the probability of an ideal binary pattern, given the noisy observed pattern. This probability is estimated by degrading noise-free document images and then computing the frequency of corresponding noise-free and noisy pattern pairs. This conditional probability is then used to construct a lookup table to restore noisy images. The impact of the restoration process is then quantified by computing the decrease in OCR word and character error rate. We find that given the estimated degradation model parameter values, the restoration algorithm decreases the character error rate by 16.1% and the word error rate by 7.35%. In some categories of degradation (e.g. model parameters that give rise to broken characters) there is a 41.5% reduction in character error rate and 20.4% reduction in word error rate.

While numerous page segmentation algorithms have been proposed in the literature, there is lack of comparative evaluation of these algorithms. In the existing performance evaluation methods, two crucial components are usually missing: 1) automatic training of algorithms with free parameters and 2) statistical and error analysis of experimental results. We use the following five-step methodology to quantitatively compare the performance of page segmentation algorithms: 1) first, we create mutually exclusive training and test data sets with groundtruth, 2) we then select a meaningful and computable performance metric, 3) an optimization procedure is then used to search automatically for the optimal parameter values of the segmentation algorithms on the training data set, 4) the segmentation algorithms are then evaluated on the test data set, and, finally, 5) a statistical and error analysis is performed to give the statistical significance of the experimental results. In particular, instead of the ad hoc and manual approach typically used in the literature for training algorithms, we pose the automatic training of algorithms as an optimization problem and use the simplex algorithm to search for the optimal parameter value. A paired-model statistical analysis and an error analysis are then conducted to provide confidence intervals for the experimental results of the algorithms. This methodology is applied to the evaluation of live page segmentation algorithms of which, three are representative research algorithms and the other two are well-known commercial products, on 978 images from the University of Washington III data set. It is found that the performance indices of the Voronoi, Docstrum, and Caere segmentation algorithms are not significantly different from each other, but they are significantly better than that of ScanSoft's segmentation algorithm, which, in turn, is significantly better than that of X-Y cut.

Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m x n image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image.

means clustering is a very popular clustering technique, which is used in numerous applications.Given a set of n data points in R d and an integer k, the problem is to determine a set of k points R d, called centers, so as to minimize the mean squared distance from each data point to its nearest center.A popular heuristic for k-means clustering is Lloyd's algorithm.In this paper we present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm.This algorithm is very easy to implement.It differs from most other approaches in that it precomputes a kd-tree data structure for the data points rather than the center points.We establish the practical efficiency of the filtering algorithm in two ways.First, we present a data-sensitive analysis of the algorithm's running time.Second, we have implemented the algorithm and performed a number of empirical studies, both on synthetically generated data and on real data from applications in color quantization, compression, and segmentation.

Most page segmentation algorithms have user-specifiable free parameters. However, algorithm designers typically do not provide a quantitative/rigorous method for choosing values for these parameters. The free parameter values can affect the segmentation result quite drastically and are very dependent on the particular dataset that the algorithm is being used on. We present an automatic training method for choosing free parameters of page segmentation algorithms. The automatic training problem is posed as a multivariate non-smooth function optimization problem. An efficient direct search method-simplex method-is used to solve this optimization problem. This training method is used applied to the training of Kise's page segmentation algorithm. It is found that a set of optimal parameter values and their corresponding performance index can be found using relatively few function evaluations. The UW III dataset was used for conducting our experiments.

Printing, photocopying, and scanning processes degrade the image quality of a document. Statistical models of these degradation processes are crucial for document image understanding research. In this paper, we present a statistical methodology that can be used to validate local degradation models. This method is based on a nonparametric, two-sample permutation test. Another standard statistical device, the power function, is then used to choose between algorithm variables such as distance functions. Since the validation and the power function procedures are independent of the model, they can be used to validate any other degradation model. A method for comparing any two models is also described. It uses p-values associated with the estimated models to select the model that is closer to the real world.

Character groundtruth for real, scanned document images is crucial for evaluating the performance of OCR systems, training OCR algorithms, and validating document degradation models. Unfortunately, manual collection of accurate groundtruth for characters in a real (scanned) document image is not practical because (i) accuracy in delineating groundtruth character bounding boxes is not high enough, (ii) it is extremely laborious and time consuming, and (iii) the manual labor required for this task is prohibitively expensive. Ee describe a closed-loop methodology for collecting very accurate groundtruth for scanned documents. We first create ideal documents using a typesetting language. Next we create the groundtruth for the ideal document. The ideal document is then printed, photocopied and then scanned. A registration algorithm estimates the global geometric transformation and then performs a robust local bitmap match to register the ideal document image to the scanned document image. Finally, groundtruth associated with the ideal document image is transformed using the estimated geometric transformation to create the groundtruth for the scanned document image. This methodology is very general and can be used for creating groundtruth for documents in typeset in any language, layout, font, and style. We have demonstrated the method by generating groundtruth for English, Hindi, and FAX document images. The cost of creating groundtruth using our methodology is minimal. If character, word or zone groundtruth is available for any real document, the registration algorithm can be used to generate the corresponding groundtruth for a rescanned version of the document.

Previously a new object representation using appearance-based parts and relations to recognize 3D objects from 2D images, in the presence of occlusion and background clutter, was introduced. Appearance-based parts and relations are defined in terms of closed regions and the union of these regions, respectively. The regions are segmented using the MDL principle, and their appearance is obtained from collection of images and compactly represented by parametric manifolds in the eigenspaces spanned by the parts and the relations. In this paper we introduce the discriminatory power of the proposed features and describe how to use it to organize large databases of objects.

The recognition of general three-dimensional objects in cluttered scenes is a challenging problem. In particular, the design of a good representation suitable to model large numbers of generic objects that is also robust to occlusion has been a stumbling block in achieving success. In this paper, we propose a representation using appearance-based parts and relations to overcome these problems. Appearance-based parts and relations are defined in terms of closed regions and the union of these regions, respectively. The regions are segmented using the MDL principle, and their appearance is obtained from collection of images and compactly represented by parametric manifolds in the two eigenspaces spanned by the parts and the relations.

Character groundtruth for scanned document images is crucial for evaluating OCR system performance, training OCR algorithms, and validating document degradation models. Manual collection of accurate character groundtruth in a real (scanned) document image is not possible because (i) accuracy in delineating groundtruth character bounding boxes is too low, (ii) it is very laborious and time consuming and (iii) the manual labor required is prohibitively expensive. We present a closed-loop methodology. We first create ideal documents using a typesetting language. Next we create the groundtruth for the ideal document. The document is then printed, photocopied and scanned. A registration algorithm estimates the geometric transformation that registers the ideal document image to the scanned document image. Finally, groundtruth associated with the ideal document image is transformed using the estimated geometric transform to create the groundtruth for the scanned document image. This methodology is very general and can be used for creating groundtruth for documents typeset in any language, layout, font, and style. The cost of creating groundtruth using our methodology is minimal. We use this methodology to groundtruth 33 English documents consisting of over 62000 symbols. The procedure takes approximately 5 minutes per page on a SUN Sparc 10. We also use the method for Hindi and FAX documents.

Efficient implementation of morphological operations requires the decomposition of structuring elements into the dilation of smaller structuring elements. Zhuang and Haralick (1986) presented a search algorithm to find optimal decompositions of structuring elements in binary morphology. We use the concepts of Top of a set and Umbra of a surface to extend this algorithm to find an optimal decomposition of any arbitrary gray-scale structuring element.

Two document degradation models that model the perturbations introduced during the document printing and scanning process were proposed recently. Although degradation models are very useful, it is very important that we validate these models by comparing the synthetically generated images against real images. In recent past, two different validation procedures have also been proposed to validate such document degradation models. These validation procedures are functions of sample size and various distance functions. In this paper we outline a statistical methodology to compare the various validation schemes that result by using different distance functions. This methodology is general enough to compare any two validation schemes.

Receiver operating characteristics (ROC) curves have the property that they start at (0,1) and end at (1,0) and are monotonically decreasing. Furthermore, a parametric representation for the curves is more natural, since ROCs need not be single valued functions: they can start with infinite slope. We show how to fit parametric splines and polynomials to ROC data with the end-point and monotonicity constraints. Spline and polynomial representations provide us a way of computing derivatives at various locations of the ROC curve, which are necessary in order to find the optimal operating points. Density functions are not monotonic but the cumulative density functions are. Thus in order to fit a spline to a density function, we fit a monotonic spline to the cumulative density function and then take the derivative of the fitted spline function. Just as ROCs have end-point constraints, the density functions have end-point constraints. Furthermore, derivatives of splines are spline functions and can be computed in closed form. Thus smoothing of histograms can also be treated as a constrained monotone regression problem. The algorithms were implementation in a mathematical programming language called AMPL and results on sample data sets are given.

The receiver operating characteristic curve is a standard method for reporting the performance of a system. In this paper we show how do choose the optimal operating point when we are given a receiver operating curve, the prior probabilities, and the economic gain matrix. Unlike earlier methods, we make no assumptions regarding underlying distributions.

We consider the problem of image segmentation and describe an algorithm that is based on the Minimum Description Length (MDL) principle, is fast, is applicable to multi-band images, and guarantees closed regions. We construct an objective function that, when minimized, yields a partitioning of the image into regions where the pixel values in each band of each region are described by a polynomial surface plus noise. The polynomial orders and their coefficients are determined by the algorithm. The minimization is difficult because (1) it involves a search over a very large space and (2) there is extensive computation required at each stage of the search. To address the first of these problems we use a region-merging minimization algorithm. To address the second we use an incremental polynomial regression that uses computations from the previous stage to compute results in the current stage, resulting in a significant speed up over the non-incremental technique. The segmentation result obtained is suboptimal in general but of high quality. Results on real images are shown.>

The authors present a methodology for designing experiments to characterize detection algorithms. The usual method is to vary parameters of the input images or parameters of the algorithms and then construct operating curves that relate the probability of misdetection and false alarm for each parameter setting. Such an analysis does not integrate the performance of the numerous operating curves. A methodology is outlined for summarizing many operating curves into a few performance curves. This methodology is adapted from the human psychophysics literature and is general to any detection algorithm. The central concept is to measure the effect of variables in terms of the equivalent effect of a critical signal variable. The methodology is demonstrated by comparing the performance of two line detection algorithms.>

Two sources of document degradation are modeled: i) perspective distortion that occurs while photocopying or scanning thick, bound documents, and ii) degradation due to perturbations in the optical scanning and digitization process: speckle, blurr, jitter, thresholding. Perspective distortion is modeled by studying the underlying perspective geometry of the optical system of photocopiers and scanners. An illumination model is described to account for the nonlinear intensity change occuring across a page in a perspective-distorted document. The optical distortion process is modeled morphologically. First, a distance transform on the foreground is performed, followed by a random inversion of binary pixels where the probability of flip is a function of the distance of the pixel to the boundary of the foreground. Correlating the flipped pixels is modeled by a morphological closing operation.>

The opening transformation on N-dimensional discrete space Z/sup N/ is discussed. The transform efficiently computes the binary opening (closing) with any size structuring element. It also provides a quick way to calculate the pattern spectrum of an image. The pattern spectrum is found to be nothing more than a histogram of the opening transform. An efficient two-pass recursive opening transform algorithm is developed and implemented. The correctness of the algorithm is proved, and some experimental results are given. The results show that the execution time of the algorithm is a linear function of n, where n is the product of the number of points in the structuring element. When the input binary image size is 256*256 and 50% of the image is covered by the binary-one pixels, it takes approximately 250 ms to do an arbitrary sized line opening and approximately 500 ms to do an arbitrary size box opening on the Sun/Sparc II workstation (with C compiler optimization flag on).>

Restricted domains, which are a restricted class of 2-D shapes, are defined. It is proved that any restricted domain can be decomposed as n-fold dilations of thirteen basis structuring elements and hence can be represented in a thirteen-dimensional space. This thirteen-dimensional space is spanned by the thirteen basis structuring elements comprising of lines, triangles, and a rhombus. It is shown that there is a linear transformation from this thirteen-dimensional space to an eight-dimensional space wherein a restricted domain is represented in terms of its side lengths. Furthermore, the decomposition in general is not unique, and all the decompositions can be constructed by finding the homogeneous solutions of the transformation and adding it to a particular solution. An algorithm for finding all possible decompositions is provided.>

Efficient implementation of morphological operations requires the decomposition of structuring elements into the dilation of smaller structuring elements. Zhuang and Haralick (1986) presented an algorithm to find optimal decompositions of structuring elements in binary morphology. In this paper the authors extend the algorithm to find optimal structuring element decomposition for gray scale morphology.>

Describes an implementation of a processor node on a Texas Instruments EVM16 microprogrammable machine. In addition, the authors give an algorithm for performing morphological image processing-a commonly used image processing tool today-on such a distributed control architecture. Finally, they give an overview of a software simulator being implemented for simulating the whole pyramid machine. A simulator is essential for testing the working of the architecture and the algorithms before building the hardware.>