Effective object and scene classification and indexing depend on extraction of informative image features. This paper shows how large families of complex image features in the form of subgraphs can be built out of simpler ones through construction of a graph lattice—a hierarchy of related subgraphs linked in a lattice. Robustness is achieved by matching many overlapping and redundant subgraphs, which allows the use of inexpensive exact graph matching, instead of relying on expensive error-tolerant graph matching to a minimal set of ideal model graphs. Efficiency in exact matching is gained by exploitation of the graph lattice data structure. Additionally, the graph lattice enables methods for adaptively growing a feature space of subgraphs tailored to observed data. We develop the approach in the domain of rectilinear line art, specifically for the practical problem of document forms recognition. We are especially interested in methods that require only one or very few labeled training examples per category. We demonstrate two approaches to using the subgraph features for this purpose. Using a bag-of-words feature vector we achieve essentially single-instance learning on a benchmark forms database, following an unsupervised clustering stage. Further performance gains are achieved on a more difficult dataset using a feature voting method and feature selection procedure.

The Receipts2Go system is about the world of one-page documents: cash register receipts, book covers, cereal boxes, price tags, train tickets, fire extinguisher tags. In that world, we're exploring techniques for extracting accurate information from documents for which we have no layout descriptions -- indeed no initial idea of what the document's genre is -- using photos taken with cell phone cameras by users who aren't skilled document capture technicians. This paper outlines the system and reports on some initial results, including the algorithms we've found useful for cleaning up those document images, and the techniques used to extract and organize relevant information from thousands of similar-but-different page layouts.

We propose a novel method to evaluate table segmentation results based on a table image ground truther. In the ground-truthing process, we first extract connected components from a given table image and connect them into an atom graph with weighed edges. Edge weight takes neighboring connected components' size similarities and distances into consideration. Then the ground truther semi-automatically determines the locations and spans of row/column separators according to projection profiles, under human supervision. We evaluate a given table segmentation by computing edit distance from its row and column separator assertions relative to ground truth. The edit distance is the sum of all the edit operation costs that correct wrong row and column separators. Each edit operation cost is a function of the sum of the weights of the edges that the separator cuts through. Thus, separator errors incur different costs depending on the severity of the error, where severity roughly corresponds to how forgivable the error would be considered by a human observer. Experimental results demonstrate that the proposed evaluation method is not only efficient, but also useful in formalizing the intuitive quality of different segmentations.

Document classification and indexing methods depend on having informative image features. This paper shows how large families of complex features can be built out of simpler ones through construction of a graph lattice -- a hierarchy of related sub graphs linked in a lattice. A graph lattice enables efficiency gains that make it possible to effectively employ bag-of-words methods for document classification using high-dimensional feature vectors. Each feature is itself a subgraph, and a feature vector is a count of occurrences of sub graphs in the image. The graph lattice enables methods for adaptively growing a feature space of sub graphs tailored to observed document genres. We demonstrate the approach through classification of forms containing rectilinear line art.

We present a system that classifies pixels in a document image according to marking type such as machine print,handwriting, and noise. A segmenter module first splits an input image into fragments, sometimes breaking connected components. Each fragment is then classified by an automatically trained multi-stage classifier that is fast and considers features of the fragment, as well as its neighborhood. Features relevant for discrimination are picked out automatically from among hundreds of measurements. Our system is trainable from example images in which each foreground pixel has a ldquoground-truthrdquo label. The main distinction of our system is the level of accuracy achieved in classifying fragments at sub-connected component level, rather than larger aggregate groups such as words or text-lines.We have trained this system to detect handwriting, machine print text, machine print graphics, and noise.

We present a user interface design for labeling elements in document images at a pixel level. Labels are represented by overlay color, which might map to such terms as ldquohandwritingrdquo, ldquomachine printrdquo, ldquographicsrdquo, etc. The primary purpose is to streamline processes for manual production of ground truth data, which is necessary for training algorithms and evaluating performance. Unlike general paint-type programs, the UI design is targeted specifically toward selection of collections of foreground pixels that are likely to be meaningful elements in a document image analysis context. Our implementation, called PixLabeler, is available for download and allows customized plug-ins for bootstrapping according to the labeling task.

This paper presents a framework for understanding tables of contents (TOC) of books, journals, and magazines. We propose a universal logical structure representation in terms of a hierarchy of entries, each of which may contain a descriptor and a locator. We enumerate graphical and perceptual cues that provide cues to parsing of tables of contents in terms of this formalism. We make initial suggestions about the form of evaluation metrics for comparing ground truthed tables of contents with the output of recognition algorithms. Typical and a typical tables of contents are used throughout to illustrate significant phenomena that must be dealt with in principled ways in any general TOC interpretation scheme. Finally we discuss implications of our observations on the design of recognition algorithms.

This paper investigates several issues in the problem of detecting handwritten markings, or annotations, on printed documents. One issue is to define the appropriate units over which to perform feature measurements and assign type labels. We propose an alpha-shape tree that operates across multiple scales. A second issue is to devise image features that offer inferential power for machine learning algorithms. We report on a feature that measures edge turn statistics. A third issue is how to combine local and neighborhood evidence. We exploit the alpha shape tree in a direct inference architecture. Information propagation schemes such as Markov random fields may be readily layered on top of our output.

This paper presents representation and logic for labeling contrast edges and ridges in visual scenes in terms of both surface occlusion (border ownership) and thinline objects. In natural scenes, thinline objects in- clude sticks and wires, while in human graphical communication thin- lines include connectors, dividers, and other abstract devices. Our analy- sis is directed at both natural and graphical domains. The basic problem is to formulate the logic of the interactions among local image events, specifically contrast edges, ridges, junctions, and alignment relations, such as to encode the natural constraints among these events in visual scenes. In a sparse heterogeneous Markov Random Field framework, we define a set of interpretation nodes and energy/potential functions among them. The minimum energy configuration found by Loopy Belief Prop- agation is shown to correspond to preferred human interpretation across a wide range of prototypical examples including important illusory con- tour figures such as the Kanizsa Triangle, as well as more difficult ex- amples. In practical terms, the approach delivers correct interpretations of inherently ambiguous hand-drawn box-and-connector diagrams at low computational cost.

This extended abstract reprises our UIST '03 paper on "Perceptually-Supported Image Editing of Text and Graphics." We introduce a novel image editing program, called ScanScribe , that emphasizes easy selection and manipulation of material found in informal, casual documents such as sketches, handwritten notes, whiteboard images, screen snapshots, and scanned documents.

This paper presents a novel image editing program emphasizing easy selection and manipulation of material found in informal, casual documents such as sketches, handwritten notes, whiteboard images, screen snapshots, and scanned documents. The program, called ScanScribe, offers four significant advances. First, it presents a new, intuitive model for maintaining image objects and groups, along with underlying logic for updating these in the course of an editing session. Second, ScanScribe takes advantage of newly developed image processing algorithms to separate foreground markings from a white or light background, and thus can automatically render the background transparent so that image material can be rearranged without occlusion by background pixels. Third, ScanScribe introduces new interface techniques for selecting image objects with a pointing device without resorting to a palette of tool modes. Fourth, ScanScribe presents a platform for exploiting image analysis and recognition methods to make perceptually significant structure readily available to the user. As a research prototype, ScanScribe has proven useful in the work of members of our laboratory, and has been released on a limited basis for user testing and evaluation.

This paper offers a solution to the mode problem in computer sketch/notetaking programs. Conventionally, the user must specify the intended "draw" or "command" mode prior to performing a stroke. This necessity has proven to be a barrier to the usability of pen/stylus systems. We offer a novel Inferred-Mode interaction protocol that avoids the mode hassles of conventional sketch systems. The system infers the user's intent, if possible, from the properties of the pen trajectory and the context of the trajectory. If the intent is ambiguous, the user is offered a choice mediator in the form of a pop-up button. To maximize the fluidity of drawing, the user is entitled to ignore the mediator and continue drawing. We present decision logic for the inferred mode protocol, and discuss subtleties learned in the course of its development. We also present results of initial user trials validating the usability of this interaction design.

Closed or nearly closed regions are an important form of perceptual structure arising both in natural imagery and in many forms of human-created imagery including sketches, line art, graphics, and formal drawings. We present an effective algorithm especially suited for finding perceptually salient, compact closed region structure in hand-drawn sketches and line art. We start with a graph of curvilinear fragments whose proximal endpoints form junctions. The key problem is to manage the search of possible path continuations through junctions in an effort to find paths satisfying global criteria for closure and figural salience. We identify constraints particular to this domain for ranking path continuations through junctions, based on observations of the ways that junctions arise in line drawings. In particular, we delineate the roles of the principle of good continuation versus maximally turning paths. Best-first bidirectional search checks for the cleanest, most obvious paths first, then reverts to more exhaustive search to find paths cluttered by blind alleys. Results are demonstrated on line drawings from several sources including line art, engineering drawings, sketches on whiteboards, as well as contours from photographic imagery.

This paper offers computational theory and an algorithmic framework for perceptual organization of image contours arising from static occluding surfaces of constant lightness. We articulate constraints and biases underlying the inference of such physical events as visible surface overlap and invisible (modal and amodal) surface boundaries, from ambiguous visual evidence including visible contrast edges and L-type and T-type junctions. For any given scene, an energy or cost function is constructed over interpretation labels for nodes of a sparse graph, or belief net. Annealing-style optimization permits local cues to propagate smoothly to give rise to a global solution. We demonstrate that this approach leads to correct interpretations (in the sense of agreeing with human percepts) of popular simple "Colorforms" figures known to induce illusory contours, as well as more difficult figures where interpretations acknowledging accidental alignment are preferred.

A Collaborage is a collaborative collage of physically represented information on a surface that is connected with electronic information, such as a physical In/Out board connected to a people-locator database. The physical surface (board) contains items that are tracked by camera and computer vision technology. Events on the board trigger electronic services. This paper motivates this concept, presents three different applications, describes the system architecture and component technologies, and discusses several design issues.

The paper shows how techniques from computational vision can be deployed to support interactive sketch editing. While conventional computer supported drawing tools give users access to visible marks or image objects at a single level of abstraction, a human user's visual system rapidly constructs complex groupings and associations among image elements according to his or her immediate purposes. We have been exploring perceptually supported sketch editors in which computer vision algorithms run continuously, behind the scenes, to afford users efficient access to emergent visual objects in a drawing. We employ a flexible image interpretation architecture based on token grouping in a multiscale blackboard data structure. This organization supports multiple perceptual interpretations of line drawing data, domain specific knowledge bases for interpreting visual structures, and natural gesture based selection of visual objects.>

This paper presents a formulation for unsupervised learning of clusters reflecting multiple causal structure in binary data. Unlike the “hard” k-means clustering algorithm and the “soft” mixture model, each of which assumes that a single hidden event generates each data point, a multiple cause model accounts for observed data by combining assertions from many hidden causes, each of which can pertain to varying degree to any subset of the observable dimensions. We employ an objective function and iterative gradient descent learning algorithm resembling the conventional mixture model. A crucial issue is the mixing function for combining beliefs from different cluster centers in order to generate data predictions whose errors are minimized both during recognition and learning. The mixing function constitutes a prior assumption about underlying structural regularities of the data domain; we demonstrate a weakness inherent to the popular weighted sum followed by sigmoid squashing, and offer alternative forms of the nonlinearity for two types of data domain. Results are presented demonstrating the algorithm's ability successfully to discover coherent multiple causal representations in several experimental data sets.

The human visual system makes a great deal more of images than the elemental marks on a surface. In the course of viewing, creating, or editing a picture, we actively construct a host of visual structures and relationships as components of sensible interpretations. This paper shows how some of these computational processes can be incorporated into perceptually-supported image editing tools, enabling machines to better engage users at the level of their own percepts. We focus on the domain of freehand sketch editors, such as an electronic whiteboard application for a pen-based computer. By using computer vision techniques to perform covert recognition of visual structure as it emerges during the course of a drawing/editing session, a perceptually supported image editor gives users access to visual objects as they are perceived by the human visual system. We present a flexible image interpretation architecture based on token grouping in a multiscale blackboard data structure. This organization supports multiple perceptual interpretations of line drawing data, domain-specific knowledge bases for interpretable visual structures, and gesture-based selection of visual objects. A system implementing these ideas, called PerSketch, begins to explore a new space of WYPIWYG (What You Perceive Is What You Get) image editing tools.

An algorithm for labeling curvilinear structure at multiple scales in line drawings and edge images is presented. Symbolic curve-element tokens residing in a spatially indexed and scale-indexed data structure denote circular arcs fit to image data. Tokens are computed via a small-to-large scale grouping procedure using a greedy best-first strategy for choosing the support of new tokens. The resulting image description is rich and redundant in that a given segment of image contour may be described by multiple tokens at different scales, and by more than one token at any given scale. This property facilitates selection and characterization of portions of the image based on curve-element attributes.>

The notion of distributed representation has gained significance in explanations of connectionist or “neural” networks. This communication shows that the concept also offers motivation in devising representations for visual shape within a symbolic computing paradigm. In a representation for binary (silhouette) shapes, and in analogy with conventional distributed connectionist networks, descriptive power is gained when microfeatures are available naming important spatial relationships in images. Our symbolic approach is introduced through a vocabulary of 31 “hand built” shape descriptors operating in the two-dimensional shape world of the dorsal fins of fishes.

A symbolic approach to constructing a multiscale primitive shape description to 2-D binary (silhouette) shape images is presented. In contrast to contour or region smoothing techniques, grouping operations are performed over collections of tokens residing on a scale-space blackboard. Two types of grouping operations are identified that, respectively, aggregate edge primitives at one scale into edge primitives at a coarser scale and group edge primitives into partial-region assertions, including curved contours, primitive corners, and bars. Procedures to perform these computations are presented.>

The author shows how a scale dimension can be added to Marr's (1976) primal sketch to facilitate construction of multiscale descriptions of two-dimensional scales. In contrast to conventional scale-space approaches, this method omits any smoothing or blurring and performs grouping operations on symbolic shape tokens residing in a scale-space blackboard data structure. Two types of grouping operation are introduced: (1) fine-to-coarse aggregation of primitive-edge tokens builds coarser-scale edge maps from finer-scale information; and (2) pairwise grouping of symmetrically placed primitive edges gives rise to a primitive partial region token denoting curved-contour, primitive-corner, and bar events. The resulting collection of tokens makes the fundamental edge and region components of a shape's geometry available to later symbolic processes, leading to shape recognition or other tasks.>

A method is presented for using connectionist networks of simple computing elements to discover a particular type of constraint in multidimensional data. Suppose that some data source provides samples consisting of n-dimensional feature-vectors, but that this data all happens to lie on an m-dimensional surface embedded in the n-dimensional feature space. Then occurrences of data can be more concisely described by specifying an m-dimensional location of the embedded surface than by reciting all n components of the feature vector. The recording of data in such a way is known as dimensionality-reduction. A method is presented for performing dimensionality-reduction in a wide class of situations for which an assumption of linearity need not be made about the underlying constraint surface. The method takes advantage of self-organizing properties of connectionist networks of simple computing elements. The authors present a scheme for representing the values of continuous (scalar) variables in subsets of units.>