A method for image matching from partial blurry images is presented that leverages existing text retrieval algorithms to provide a solution that scales to hundreds of thousands of images. As an initial application, we present a document image matching system in which the user supplies a query image of a small patch of a paper document taken with a cell phone camera, and the system returns a label identifying the original electronic document if found in a previously indexed collection. Experimental results show that a retrieval rate of over 70% is achieved on a collection of nearly 500,000 document pages.

Visual search connects physical (offline) objects with (online) digital media. Using objects from the environment, like newspapers, magazines, books and posters, we can retrieve supplemental information from the online world. In this demonstration, we show a framework for delivering visual search services to users of mobile devices. We show how users can point a mobile device at any location in a document, magazine or book to view related, online material on the device. We describe client applications now being deployed for the iPhone and the server architecture used for recognition of scanned images.

Mobile applications are increasingly becoming part of our lives and our work. Moreover, visual capture capability on mobile devices is increasingly being used for linking the real world and the digital world. In this demonstration paper we present an application for accessing and browsing Web sites by pointing a mobile phone at a text book or a printout of a Web site, taking a picture of a small region, performing content recognition and automatically displaying a Web site that is linked to the content.

The popularity of camera phones enables many exciting multimedia applications. In this paper, we present a novel technology and several applications that allow users to interact with paper documents, books, and magazines. This interaction is in the form of reading and writing electronic information, such as images, web urls, video, and audio, to the paper medium by pointing a camera phone at a patch of text on a document. Our application does not require any special markings, barcodes, or watermarks on the paper document. Instead, we propose a document recognition algorithm that automatically determines the location of a patch of text in a large collection of document images given a small document image. This is very challenging because the majority of phone cameras lack autofocus and macro capabilities and they produce low quality images and video. We developed a novel algorithm, Brick Wall Coding (BWC), that performs image-based document recognition using the mobile phone video frames. Given a document patch image, BWC utilizes the layout, i.e. relative locations, of word boxes in order to determine the original file, page, and the location on the page. BWC runs real-time (4 frames per second) on a Treo 700w smartphone with a 312 MHz processor and 64MB RAM. Using our method we can recognize blurry document patch frames that contain as little as 4-5 lines of text and a video resolution as low as 176x144. We performed experiments by indexing 4397 document pages and querying this database with 533 document patches. Besides describing the basic algorithm, this paper also describes several applications that are enabled by mobile phone-paper interaction, such as inserting electronic annotations to paper, using paper as a tangible interface to collect and communicate multimedia data, and collaborative homework.

HotPaper enables users to electronically interact with paper documents by pointing their camera phones at a document. Electronic interaction is in the form of reading and/or writing images, audio and video clips, urls, notes, etc to the paper. HotPaper does not require any machine readable code, such as a barcode or watermark, to be present on the document. It utilizes our Brick Wall Coding document recognition algorithm [1] that uses a small document patch image to retrieve electronic versions of documents without performing OCR. The HotPaper demonstration runs on a Treo 700w 312 MHz mobile phone and performs document recognition at 4 frames per second using 176x144 video input.

An algorithm is presented that automatically generates ground-truthed video from a symbolic description for an object and a specification for the movement of a handheld video camera around that object. This provides a method to generate large amounts of training and test data for the development of computer vision algorithms. We describe an implementation of this technique for an imaging application in which a cell phone video camera is moved over a paper document. Experimental results demonstrate the similarity of images captured by the real camera to images generated by the proposed technique.

In this paper, we describe a method for storing an entire video, animation sequence, or any other media type, on paper. The method is based on printing a key frame from a video on paper along with a barcode that encodes the motion information and other auxiliary information in MPEG-4 format. Unlike other video barcode systems in the prior art, a barcode in our system does not contain a link to the video clip; instead it contains motion information. A client device applies the motion information to an image of the video key frame to obtain full motion video. Therefore, the paper document is a self contained representation of a video clip and access to a server is not required. We modified an MPEG-4 [1] encoder and decoder to implement the video flip-book encoder and decoder. Experiments show that it is possible to encode several seconds of video on paper using our method. This is sufficient to create small animations for some printed materials such as video greeting cards and children's books.

It is difficult to view multipage, high resolution documents on devices with small displays. As a solution, we introduce a multimedia thumbnail representation, which can be seen as a multimedia clip that provides an automated guided tour through a document. Multimedia thumbnails are automatically generated by taking a document image as input and first performing visual and audible information analysis on the document to determine salient document elements. Next, the time and information attributes for each document element are computed by taking into account the display and application constraints. An optimization routine, given a time constraint, selects elements to be included in the multimedia thumbnail. Last, the selected elements are synthesized into animated images and audio to create the final multimedia representation

A novel system is described that significantly enhances the usefulness of handwritten notes taken during a presentation by creating a multimedia document that includes scanned images of handouts, personal notes, and links to a multimedia recording of the presentation. Notes are linked to the e-presentation media with automatic content analysis without any special notes capture device. Layout segmentation and template matching automatically detects the presence of presentation handouts during scanning. Presentation-level and slide-level linking of handouts to e-media use text and image features from slides. Experimental results show 95% accuracy in linking of the scanned handouts to the e-presentation media.

Overcoming the semantic-feature gap and adapting to context are two main challenges in content-based retrieval. The problem is even more complicated for unstructured videos such as automated recordings of meetings. To address this problem, we propose a model-based approach to meeting retrieval with user controlled weighting for dynamic similarity comparison. Each video is represented by an HMM, and the similarity between videos is determined by comparing the corresponding models. Users can control the relative importance of temporal and static features by adjusting a weighting parameter in a way similar to content-based image retrieval. Experimental results demonstrate the feasibility and versatility of this approach.

The Office Blogger (OBlog) is an experimental prototype of a multimedia appliance that allows an office worker to easily record events, conversations, meetings, pictures and documents, and helps create blog entries from that data. OBlog employs a novel image classification algorithm and automatic post processing to make the information about images more accessible to users. The OBlog system uses an älways-on" design that makes it convenient to use and it's packaged as a stand-alone system to remove any computational burden from a user's PC. Results show that the image classification algorithm achieves over 90% recall on five image categories commonly encountered by office workers.

A multimedia note taking system called MinuteAid is described that lets users of laptops include multimedia objects in notes they write during a presentation. The multimedia data is provided by devices that capture slide images, whiteboard images, audio and video clips. The MinuteAid system includes a software interface between these devices and a commonly available word processing application (Microsoft Word) and lets the user either insert copies of multimedia objects while they're captured or references to multimedia objects that are automatically retrieved and inserted in the document later. We describe the architecture, implementation and user experience with this system.

The components of a key frame selection algorithm for a paper-based multimedia browsing interface called Video Paper are described. Analysis of video image frames is combined with the results of processing the closed caption to select key frames that are printed on a paper document together with the closed caption. Bar codes positioned near the key frames allow a user to play the video from the corresponding times. This paper describes several component techniques that are being investigated for key frame selection in the Video Paper system, including face detection and text recognition. The Video Paper system implementation is also discussed.

Background subtraction is an essential processing component for many video applications. However, its development has largely been application driven and done in an ad hoc manner. In this paper, we provide a Bayesian formulation of background segmentation based on Gaussian mixture models. We show that the problem consists of two density estimation problems, one application independent and one application dependent, and a set of intuitive and theoretically optimal solutions can be derived for both. The proposed framework was tested on meeting and traffic videos and compared favorably to other well-known algorithms.

Recorded meetings are useful only if people can find, access, and browse them easily. Key-frames and video skims are useful representations that can enable quick previewing of the content without actually watching a meeting recording from beginning to end. This paper proposes a new method for creating meeting video skims based on audio and visual activity analysis together with text analysis. Audio activity analysis is performed by analyzing sound directions-indicating different speakers-and audio amplitude. Detection of important visual events in a meeting is achieved by analyzing the localized luminance variations in consideration with the omni-directional property of the video captured by our meeting recording system. Text analysis is based on the term frequency-inverse document frequency measure. The resulting video skims better capture the important meeting content compared to the skims obtained by uniform sampling.

A paper-based interface for browsing video is proposed. A paper document shows key frames selected from a video, a transcript for the parallel audio track, and bar codes that, when scanned, invoke a multimedia player. The paper document provides a stand-alone representation for a video recording that lets a user both understand the content of the file and replay only selected parts of the multimedia that are necessary to gain a better understanding. This approach applies the two-dimensional display characteristics of a newspaper to multimedia retrieval. By so doing, the user's browsing and search efficiency is greatly improved. This poster describes an implementation of the video paper system using a pocket PC with a bar code reader as the remote control device and an archive of video recordings on the pocket PC or an external server.

An algorithm is presented that automatically matches images of presentation slides to the symbolic source file (e.g., PowerPoint™ or Acrobat™) from which they were generated. The images are captured either by tapping the video output from a laptop connected to a projector or by taking a picture of what's displayed on the screen in a conference room. The matching algorithm extracts features from the image data, including OCR output, edges, projection profiles, and layout and determines the symbolic file that contains the most similar collection of features. This algorithm enables several unique applications for enhancing a meeting in real-time and accessing the audio and video that were recorded while a presentation was being given. These applications include the simultaneous translation of presentation slides during a meeting, linking video clips inside a PowerPoint file that show how each slide was described by the presenter, and retrieving presentation recordings using digital camera images as queries.

Video Paper is a prototype system for multimedia browsing, analysis, and replay. Key frames extracted from a video recording are printed on paper together with bar codes that allow for random access and replay. A transcript for the audio track can also be shown so that users can read what was said, thus making the document a stand-alone representation for the contents of the multimedia recording. The Video Paper system has been used for several applications, including the analysis of recorded meetings, broadcast news, oral histories and personal recordings. This demonstration will show how the Video Paper system was applied to these domains and the various replay systems that were developed, including a self-contained portable implementation on a PDA and a fixed implementation on desktop PC.

The design and implementation of a portable meeting recorder is presented. Composed of an omni-directional video camera with four-channel audio capture, the system saves a view of all the activity in a meeting and the directions from which people spoke. Subsequent analysis computes metadata that includes video activity analysis of the compressed data stream and audio processing that helps locate events that occurred during the meeting. Automatic calculation of the room in which the meeting occurred allows for efficient navigation of a collection of recorded meetings. A user interface is populated from the metadata description to allow for simple browsing and location of significant events.

The ability to automatically record the marks applied to paper documents on their electronic originals would preserve the information represented by those annotations. Users could even lose the original paper document. The marked-up version could be regenerated by merely reprinting it. We describe a solution that saves an electronic representation for the highlights users commonly apply over the top of machine-printed text. A unique combination of algorithms is presented that maps the image captured from a pen scanner affixed to a highlighting pen onto text strings in electronic documents. Documents are automatically located in a large database using characteristics of the highlighted text. We describe here the system components, including the image recognition algorithms, and discuss their performance in finding a unique mapping from an image of text onto a sequence of words in an electronic document within a large database.

A new family of symbolic compression algorithms has recently been developed that includes the ongoing JBIG2 standardization effort as well as related commercial products. These techniques are specifically designed for binary document images. They cluster individual blobs in a document and store the sequence of occurrence of blobs and representative blob templates, hence the name symbolic compression. This paper describes a method for duplicate detection on symbolically compressed document images. It recognizes the text in an image by deciphering the sequence of occurrence of blobs in the compressed representation. We propose a Hidden Markov Model (HMM) method for solving such deciphering problems and suggest applications in multilingual document duplicate detection.

A system is presented that uses texture to retrieve and browse images stored in a large document image database. A method of graphically generating a candidate search image is used that shows the visual layout and content of a target document. All images similar to this candidate are returned for the purpose of browsing or further query. The system is accessed using a World Wide Web (Web) browser. Applications include the retrieval and browsing of document images including newspapers, fares and business letters.

A hierarchical algorithm is presented for determining the similarity and equivalence of document images. Features extracted from the CCITT fax compressed representations of two images are compared to determine their visual similarity and whether they are equivalent. Pass codes in the compressed data are used as features. A fixed grid is imposed on the image and a feature vector is derived from the number of pass codes in each grid cell. The feature vectors are compared to locate a group of documents that are visually similar to the input image. The equivalence of two documents is determined by applying the Hausdorff distance to the two dimensional arrangement of pass codes in small patches of each image.

Algorithms that estimate the angle at which a document image is rotated (called a document’s skew) are surveyed. Four broad classes of technique are identified. These include methods that calculate skew from a horizontal projection profile, a distribution of feature locations, a Hough transform, or the distribution of responses from local, directionally sensitive masks. The basic method used by each class of technique is presented and the contributions of individual algorithms within each class are discussed. 1

The use of a statistical language model to improve the performance of an algorithm for recognizing digital images of handwritten or machine-printed text is discussed. A word recognition algorithm first determines a set of words (called a neighborhood) from a lexicon that are visually similar to each input word image. Syntactic classifications for the words and the transition probabilities between those classifications are input to the Viterbi algorithm. The Viterbi algorithm determines the sequence of syntactic classes (the states of an underlying Markov process) for each sentence that have the maximum a posteriori probability, given the observed neighborhoods. The performance of the word recognition algorithm is improved by removing words from neighborhoods with classes that are not included on the estimated state sequence. An experimental application is demonstrated with a neighborhood generation algorithm that produces a number of guesses about the identity of each word in a running text. The use of zero, first and second order transition probabilities and different levels of noise in estimating the neighborhood are explored.

An hypothesis testing approach for recognizing machine-printed words is presented in this paper. Based on knowledge of the document font and candidates for the identity of a word, this approach searches a tree of word decisions to generate and test hypotheses for character recognition and segmentation. The search starts at each sequential character position from both ends of a word image and proceeds inward. The accumulated cost of reaching a certain partial recognition decision is combined with the estimate of the potential cost to reach a goal state using an A* search algorithm. The proposed algorithm compensates for local degradations by relying on global characteristics of a word image. Tests of the algorithm show a recognition rate of 98.93% on degraded scanned document images with touching characters.

A technique is presented that uses visual relationships between word images in a document to improve the recognition of the text it contains. This technique takes advantage of the visual relationships between word images that are usually lost in most conventional optical character recognition (OCR) techniques. The visual relations are defined to be the equivalence that exists between images of the same word or portions of word images. An algorithm is presented that calculates these relationships in a document. The resulting clusters are integrated with the recognition results provided by an OCR system. Inconsistencies in OCR results between equivalent images are identified and used to improve recognition performance. Experimental results are presented in which the input is provided directly from a commercial OCR system.

The nearest neighbor (NN) approach is a powerful nonparametric technique for pattern classification tasks. In this paper, algorithms for prototype reduction, hierarchical prototype organization and fast NN search are described. To remove redundant category prototypes and to avoid redundant comparisons, the algorithms explain geometrical information of a given prototype set which is represented approximately by computing k-nearest/farthest neighbors of each prototype. The performance of a NN classifier using those algorithms for Japanese character recognition is reported.

Algorithms are presented that determine the visual relationships between word images in a document. These include instances of common word images and common substrings that occur often in English language text images. This information is then used to improve the performance of a commercial optical character recognition (OCR) algorithm. The algorithms presented calculate clusters of equivalent word images as well as common initial and final substrings. Experimental results are presented that show a 40% reduction in word level error rate is achieved on a test set of documents degraded by uniform noise.

An algorithm for word recognition in oriental languages such as Chinese, Japanese, and Korean is presented. The objective is to recognize words, that are composed of a number of consecutive characters, in document images where there are no explicit visually defined word boundaries. The technique exploits the redundancy in these languages that is expressed by the difference between the number of possible character strings of a fixed length and the number of legal words of that length. Sequences of character images are matched simultaneously to lists of legal words and illegal strings that are likely to occur. A word is located if its image is more likely to occur in the current context than any of the illegal strings that are visually similar to it. No intermediate character recognition step is used. The application of contextual information directly to the interpretation of features extracted from the image overcomes noise that could have made isolated character recognition impossible and the location of words with conventional postprocessing algorithms difficult. Experimental results are presented that show the ability of this algorithm to correctly recognize text in the presence of noise.

Describes the control structure for an intelligent handwritten address interpretation system. The system takes a grey-level address image, segments the address into lines and words, parses the address into meaningful syntactic categories, recognizes words using dynamically generated lexicons, and determines the destination code with the aid of postal directories.>

A multiple classifier system is a powerful solution to difficult pattern recognition problems involving large class sets and noisy input because it allows simultaneous use of arbitrary feature descriptors and classification procedures. Decisions by the classifiers can be represented as rankings of classifiers and different instances of a problem. The rankings can be combined by methods that either reduce or rerank a given set of classes. An intersection method and union method are proposed for class set reduction. Three methods based on the highest rank, the Borda count, and logistic regression are proposed for class set reranking. These methods have been tested in applications of degraded machine-printed characters and works from large lexicons, resulting in substantial improvement in overall correctness.>

An image database for handwritten text recognition research is described. Digital images of approximately 5000 city names, 5000 state names, 10000 ZIP Codes, and 50000 alphanumeric characters are included. Each image was scanned from mail in a working post office at 300 pixels/in in 8-bit gray scale on a high-quality flat bed digitizer. The data were unconstrained for the writer, style, and method of preparation. These characteristics help overcome the limitations of earlier databases that contained only isolated characters or were prepared in a laboratory setting under prescribed circumstances. Also, the database is divided into explicit training and testing sets to facilitate the sharing of results among researchers as well as performance comparisons.>

A probabilistic lattice chart parser is proposed for improving the performance of a text recognition technique. Digital images of words are recognized and alternatives for the identity of each are generated. Local word collocation statistics and a probabilistic chart parsing algorithm are used to determine the top N best parses for each sentence using the alternatives provided for the identity of each word by the recognition system. An approach in which text recognition and understanding are tightly integrated is discussed. An objective of this approach is to provide the capacity to process images of unrestricted English text. A large-scale lexicon, which supports the system, was acquired by training on corpora of over 3,000,000 words. The focus is on the implementation and performance of the probabilistic lattice chart parser.>

A method is presented to filter the output of a word recognition algorithm, which may contain errors, to locate decisions that should be correct with a high degree of certainty. The algorithm uses the output of a word recognition system and techniques used in information retrieval to characterize a free-text document database to locate a set of documents that have topics which are similar to that of the input document. The vocabulary from these similar documents is then used to locate the correct word recognition decisions. Experimental results show that a subset of the word recognition decisions for an input document can be located that are between 90 and 99% correct. The subset located by this method can be used to drive other recognition processes applied to the rest of the text.>

Difficult pattern recognition problems involving large class sets and noisy input can be solved by a multiple classifier system, which allows simultaneous use of arbitrary feature descriptors and classification procedures. Independent decisions by each classifier can be combined by methods of the highest rank, Borda count, and logistic regression, resulting in substantial improvement in overall correctness.>

The use of a hidden Markov model (HMM) for language syntax to improve the performance of a text recognition algorithm is proposed. Syntactic constraints are described by the transition probabilities between word classes. The confusion between the feature string for a word and the various syntactic classes is also described probabilistically. A modification of the Viterbi algorithm is also proposed that finds a fixed number of sequences of syntactic classes for a given sentence that have the highest probabilities of occurrence, given the feature strings for the words. An experimental application of this approach is demonstrated with a word hypothesization algorithm that produces a number of guesses about the identity of each word in a running text. The use of first and second order transition probabilities is explored. Overall performance of between 65 and 80 percent reduction in the average number of words that can match a given image is achieved.>

A technique is presented that determines equivalences between word images in a passage of text. A clustering procedure is applied to group visually similar words. Initial hypotheses for the identities of words are then generated by matching the word groups to language statistics that predict the frequency at which certain words will occur. This is followed by a recognition step that assigns identifications to the images in the clusters. This paper concentrates on the clustering algorithm. A clustering technique is presented and its performance on a running text of 1062 word images is determined. It is shown that the clustering algorithm can correctly locate groups of short function words with better than a 95 percent correct rate.>

A top-down approach to word recognition is proposed. Discussions are presented on dynamically selecting the most effective feature combinations, which are applied to discriminate between a limited set of word hypotheses.>

A methodology for classifying syntactic patterns that performs a branch-and-bound search over a set of prototypes is proposed. The prototypes are first clustered hierarchically and the search is performed over the hierarchy. The proposed technique is applied to a pattern recognition system in which images are described by the sequence of features extracted from the chain codes of their contours. A rotationally invariant string distance measure is defined that compares two feature strings. The methodology discussed is compared to a nearest neighbor classifier that uses 12000 prototypes. The proposed technique decreases the time required to recognize a pattern by 93% and maintains a recognition rate of greater than 90%.>

Understanding a block of handwritten text means mapping it into a semantic representation. We describe an approach to reading a block of handwritten text when there are certain loose constraints placed on the spatial layout and syntax of the text. Early recognition of primitives guides the location of syntactic components. A system to read handwritten postal addresses is described as an instance. The semantic representation in this case is a digit string (ZIP Code). Methods for segmenting a string of digits into components and for recognizing digits using a multiplicity of recognizers are given.

An empirical investigation of the importance of accurate assessment of prior probabilities in a typical visual classification problem, handwritten ZIP code recognition, is presented. Prior probabilities for individual digits and entire ZIP codes were investigated; the results for priors of individual digits are summarized. In studies of prior distributions over entire ZIP codes, it was found that the qualitative information had a major effect on the efficacy of the algorithm, whereas quantitative information was relatively unimportant. It is concluded that precise estimation of prior probabilities is unnecessary in the domain of computer vision, whereas accurate qualitative assessment of possibilities is important.>

A methodology for recognizing ZIP codes (US postal codes) in handwritten addresses is presented that uses many diverse pattern recognition and image processing algorithms. Given a high-resolution image of a handwritten address block, the solution invokes routines capable of hypothesizing the location of the ZIP code, segmenting and recognizing ZIP code digits, locating and recognizing city and state names, and looking up the results in a dictionary. The control structure is not strictly sequential, but rather in the form of a blackboard architecture that opportunistically invokes routines as needed. An implementation of the methodology is described as well as results with a database of grey-level images of handwritten addresses (taken from live mail in a US Postal Service mail processing facility). Future extensions of the approach are discussed.>

The use of diverse knowledge sources in text recognition and in correction of letter substitution errors in words of text is considered. Three knowledge sources are defined: channel characteristics as probabilities that observed letters are corruptions of other letters, bottom-up context as letter conditional probabilities (when the previous letters of the word are known), and top-down context as a lexicon. Two algorithms, one based on integrating the knowledge sources in a single step and the other based on sequentially cascading bottom-up and top-down processes, are compared in terms of computational/storage requirements and results of experimentation.

A new algorithm for text recognition that corrects character substitution errors in words of text is presented.The search for a correct word effectively integrates three knowledge sources: channel characteristics, bottom-up context, and top-down context.Channel characteristics are used in the form of probabilities that observed letters are corruptions of other letters; bottom-up context is in the form of the probability of a letter when the previous letters of the word are known; and top-down context is in the form of a lexicon.A one-pass algorithm is obtained by merging a previously known dynamic programming algorithm to compute the maximum a posteriori probability string (known as the Viterbi algorithm) with searching a lexical trie.Analysis of the computational compexity of the algorithm and results of experimentation with a PASCAL implementation are presented.

The binary n-gram and Viterbi algorithms have been suggested as alternative approaches to contextual postprocessing for text produced by a noisy channel such as an optical character recognizer. This correspondence describes the underlying theory of each approach in unified terminology, and presents new implementation algorithms for each approach. In particular, a storage efficient data structure is proposed for the binary n-gram algorithm and a recursive formulation is given for the Viterbi algorithm. Results of extensive experiments with each algorithm are described.