15723189
Impact of imperfect OCR on part-of-speech tagging
Part-of-speech (POS) tagging is the foundation of natural language processing (NLP) systems, and thus has been an active area of research for many years. However, one question remains unanswered: How will a POS tagger behave when the input text is not error-free? This issue can be of great importance when the text comes from imperfect sources like optical character recognition (OCR). This paper analyzes the performance of both individual POS taggers and combination systems on imperfect text. Experimental results show that a POS tagger's accuracy decreases linearly with the character error rate and the slope indicates a tagger's sensitivity to input text errors.
2250003
ICDAR 2003 robust reading competitions: entries, results, and future directions
Abstract.This paper describes the robust reading competitions for ICDAR 2003. With the rapid growth in research over the last few years on recognizing text in natural scenes, there is an urgent need to establish some common benchmark datasets and gain a clear understanding of the current state of the art. We use the term ‘robust reading’ to refer to text images that are beyond the capabilities of current commercial OCR packages. We chose to break down the robust reading problem into three subproblems and run competitions for each stage, and also a competition for the best overall system. The subproblems we chose were text locating, character recognition and word recognition. By breaking down the problem in this way, we hoped to gain a better understanding of the state of the art in each of the subproblems. Furthermore, our methodology involved storing detailed results of applying each algorithm to each image in the datasets, allowing researchers to study in depth the strengths and weaknesses of each algorithm. The text-locating contest was the only one to have any entries. We give a brief description of each entry and present the results of this contest, showing cases where the leading entries succeed and fail. We also describe an algorithm for combining the outputs of the individual text locators and show how the combination scheme improves on any of the individual systems.
8341476
Active document layout synthesis
Document layout analysis has been researched for many years. However, there is little work on the reverse of document layout analysis: document layout synthesis, whose goal is to generate logically correct and aesthetically appealing layout given the text/image contents and the flexible layout template. This paper introduces a new automatic document layout synthesis method, which can actively pursue the optimal text block height-width tradeoff simultaneously with the block position adjustment. The key idea is to use a cluster of linear functions to approximate the nonlinear height-width curve. Then two-pass simplex algorithm is used to solve the layout synthesis problem. This method has a wide range of applications, such as variable data printing (VDP), automatic table formatting, and automating document layout ground truth generation.
5163377
Handwritten numeral recognition using MFNN based multiexpert combination strategy
A novel unconstrained numeral recognition system using an MFNN (multilayered feedforward neural net)-based multi-expert combination strategy is proposed. Taking advantage of every method's confidence value as well as its output label, this strategy can improve the system's performance significantly with as few as two experts. Another novel feature of the system is that the multi-expert combination problem is converted into a new classification problem, and then the MFNNs are used to handle the combination adaptively. The proposed system has achieved promising results on the NIST database.
13382977
Quality assurance in high volume document digitization: a survey
Quality assurance (QA) plays a critical role in high volume document digitization projects by making sure that the specified quality standard is reached under cost and time constraints. This paper takes a systematic view on this issue by summarizing and abstracting related existing work: quality bottlenecks and technical solutions throughout the whole processing pipeline, including cataloging, capture, image analysis and recognition, and error cascading; various strategies to conduct cost-effective QA, such as combination of auto-QA and manual QA, batch QA, special QA user interface, and open source QA
26474180
Adaptive confidence transform based classifier combination for Chinese character recognition
Abstract Classifier combination is an effective way to improve recognition performance. However, in Chinese character recognition the extremely large number of categories results in several difficulties for the combination. In order to overcome these difficulties a novel combination method is presented in this paper. It consists of three main components: adaptive confidence transform (ACT), consensus theoretic combination and reliability based speedup scheme. ACT, which can estimate a posteriori probabilities from raw measurement values, is the focus of this paper. Experimental results show a significant reduction of error rates in both printed (PCCR) and handwritten Chinese character recognition (HCCR).
4440052
An Optimal Divide-Conquer Algorithm for 2D Skyline Queries
Skyline query processing is fundamental to many applications including multi-criteria decision making. In this paper, we will present an optimal algorithm for computing skyline in the two dimensional space. The algorithm has the progressive nature and adopts the divide-conquer paradigm. It can be shown that our algorithm achieves the minimum I/O costs, and is more efficient and scalable than the existing techniques. The experiment results demonstrated that our algorithm greatly improves the performance of the existing techniques.
18316669
On Linear-Spline Based Histograms
Approximation is a very effective paradigm to speed up query processing in large databases. One popular approximation mechanism is data size reduction. There are three reduction techniques: sampling, histograms, and wavelets. Histogram techniques are supported by many commercial database systems, and have been shown very effective for approximately processing aggregation queries. In this paper, we will investigate the optimal models for building histograms based on linear spline techniques. We will firstly propose several novel models. Secondly, we will present efficient algorithms to achieve these proposed optimal models. Our experiment results showed that our new techniques can greatly improve the approximation accuracy comparing to the existing techniques.
16928019
Map Displays for Information Retrieval
The focus of this article is to develop a map display for to stack in the dark, without knowing what stacks that information retrieval. Through an examination of relawe have walked through. We can get a few books each tionships among visual displays, information retrieval, time and walk out of the library to see if the book we and browsing, advantages of visual displays for informaare searching for is among them. If not, we have to walk tion retrieval are characterized as (1) the ability to conin again, based on our knowledge and our previous experivey a large amount of information in a limited space, (2) the potential to reveal semantic relationships of terms ence, to a location where we hope the book would be. In and documents, and (3) the facilitation of browsing and this situation, success in finding a book greatly depends perceptual inferences on retrieval interfaces. These adon whether we can walk to the right place in the dark (to vantages are further demonstrated through a map disgenerate a good query), and whether we know how to play generated by a neural network’s self-organizing aladjust our locations until we get to the right place (to gorithm. The map display detects complex relationships among given documents, and reveals the relationships modify queries interactively) . through a spatial arrangement of terms abstracted from Can we turn on the light for such a library? Can we the documents. The map display also provides interdevelop some visible cues in our retrieval systems so that active tools to allow the user to interact with the underlywe can use our perception for information seeking in ing information. Examples of the map displays show that the digital environment? Answers to these questions may such map displays can be used both as an overview tool and an access or exploration tool, and the map displays reside in the recent advance of information technology. will likely increase the amount of information that the ‘‘Information processing has been evolving from numeriuser is willing to browse. cal computation to character handling, and now to visual information processing’’ (Kunii, 1989). As a result, visualization will become ‘‘the second computer revolution’’ Introduction (Friedhoff & Benzon, 1989). Computers are expected to be used to reveal associations and properties of electronic The world in which we live is a visual world. We look, information to allow people to use their visual capabilities we see, and we find things. Even for written information, for information seeking (Veith, 1988). we expect to see it on tangible media stored in visible locations. We have developed a whole set of perception This article discusses using some mapping techniques and association techniques to get what we need from the to create visual displays for textual information stored in environment. However, when we search information by the computer. The focus of the article is on the developcomputer, all the things, information, media, locations, ment of a map display for information retrieval. The map as well as their relationships, become invisible; all the display attempts to show both contents and semantic clues for visual perceptions and associations disappear. structures of a document space by mapping major conWe heavily rely on our competence to generate queries cepts and documents of a document space to a two-dimenand the computer’s ability to match the queries with inforsional map. It preserves, as faithfully as possible, documation stored in the computer. At best, when interaction ment semantic relationships and reveals these relationis involved, we can modify queries based on the retrieved ships through various visual components of the display. results of a previous query. This is like searching books By communicating a spatial metaphor to the user and in a library without light. We can walk around from stack making information in a document space graphically visible, the map display provides a visual guide to help the user perceive contents and structures of the document Received May 26, 1995; revised December 18, 1995; accepted Decemspace. ber 18, 1995. In the following, relationships among information retrieval, browsing, and visual displays are discussed first, q 1997 John Wiley & Sons, Inc.
2460253
Approximate processing of massive continuous quantile queries over high-speed data streams
Quantile computation has many applications including data mining and financial data analysis. It has been shown that an /spl epsi/-approximate summary can be maintained so that, given a quantile query (/spl phi/,/spl epsi/), the data item at rank /spl lceil//spl phi/N/spl rceil/ may be approximately obtained within the rank error precision /spl epsi/N over all N data items in a data stream or in a sliding window. However, scalable online processing of massive continuous quantile queries with different /spl phi/ and /spl epsi/ poses a new challenge because the summary is continuously updated with new arrivals of data items. In this paper, first we aim to dramatically reduce the number of distinct query results by grouping a set of different queries into a cluster so that they can be processed virtually as a single query while the precision requirements from users can be retained. Second, we aim to minimize the total query processing costs. Efficient algorithms are developed to minimize the total number of times for reprocessing clusters and to produce the minimum number of clusters, respectively. The techniques are extended to maintain near-optimal clustering when queries are registered and removed in an arbitrary fashion against whole data streams or sliding windows. In addition to theoretical analysis, our performance study indicates that the proposed techniques are indeed scalable with respect to the number of input queries as well as the number of items and the item arrival rate in a data stream.
1683223
A Scalable and I/O Optimal Skyline Processing Algorithm
In this paper, we will present a novel progressive algorithm for computing skyline queries. The algorithm is based on the depth-first search paradigm. It can be shown that the new algorithm is I/O optimal. Further, we can show that the algorithm takes a logarithmic memory space in 2D-space in the worst case if there are not many intersections in an adopted R-tree. Our experiment demonstrated that the new algorithm is more scalable and efficient than the existing techniques especially in a low dimensional space. The experiment also showed that the algorithm is progressive in a way sensitive to a user’s preference.