The Self-Organizing Desk

1 Introduction

We wish to create smart physical worlds, that can augment reality with electronic information. Such spaces will keep track of their own contents, index­ ing and organizing their objects in electronic views. We hope to achieve this vision by using sensors to extract information about the physical world. The self-organizing desk, a system that can keep track of its contents autonomously, is an example of such sys­ tems. Consider the flow of paper that arrives for pro­ cessing at someone's desk. Many paper documents potentially relevant to planning and scheduling arrive every day. These documents are filtered and filed in filing cabinets, or in random piles. In this space one has to manage queries such as "where is the letter from John Hopcroft?", "where is the paper I received last week that has a red table in the upper right corner?", "where is all the information I need to complete this report?", etc. Answers to these queries should be of the form "the top, right pile, of the desk, about half­ way down". Such query processing would be much easier if all the data on the desk-top were available electronically. The self-organizing desk described in this paper implements these ideas.

Systems capable of self-organization present their users with accurate summaries at various levels of de-

The Self-Organizing Desk

Daniela Rus Peter de Santis

Department of Computer Science Dartmouth College Hanover, NH 03755

{rus,gwitto }@cs.dartmouth.edu

tail, even when the data changes dynamically. Self­ organization is implemented by using sensors to ob­ serve and extract information about the objects in a physical space. The sensori-data is captured, in­ dexed, and organized in electronic views. The views are aggregated as a database and stamped with spa­ tial and temporal information. In selecting electronic views, our premise is that textual cues, visual cues, and topic-subtopic relationships are equally important for locating and manipulating documents.

In this paper we describe a system that implements the self-organization metaphor on the documents on a desk-top. The self-organizing desk uses a robot eye (a steerable, 3 degree of freedom computer control cam­ era) to survey the documents on a desk-top, to cap­ ture and index their attributes (words, color, images, tables, location, time, etc.). The system interacts with users through a GUI to help them locate items on the piles on the desk top, or visualize conceptually the content of the desk. It supports operations to add a document to a random location on the desk, to remove a document from the desk top, and to shift a stack of documents from one desk-top location to another.

The paper is organized as follows. First, we present the system that implements the self-organization metaphor for a desk. Second, we describe our experi­ ments with the desk. Finally, we discuss related work and future extensions.

2 The System Description

The architecture of the self-organizing desk system is shown in Figure 1. The system uses a camera that surveys a desk top by sweeping above its surface con­ tinuously, looking for changes. We assume that the only objects on the desk are standard size papers 1

1 The presence of other objects for example coffee cups, does not affect the performance of the system. At the moment such objects are simply not recognized or processed by the system.

and that these papers undergo changes one at a time. The change can be one of the following: add a new paper, remove a paper, or shift a stack of papers from one location to another. Change is detected by the camera via the segmentation module. Each time the system notices a change, the following set of opera­ tions are executed. Suppose, for simplicity, that the system has noticed a new paper that was added to the desk. The approximate coordinates of the pa­ per are computed (by the segmentation module) and the camera is automatically positioned (by the cam­ era control module) so as to capture a picture of maxi­ mum detail of the new document. The resulting image is passed through a variety of filters including OCR, color, and tables and the filtered data is indexed in a database, In addition to layout, the database also contains space, time, and history information for each document. History captures the order in which the documents arrive and is used for defining stacks (or piles) of documents. This database is indexed, up­ dated, organized and summarized on-line (as its con­ tents changes dynamically) by the information access module. The user can query this module by speci­ fying full text, visual attributes, and/or requests for content summaries, content organization, and visual­ ization. Queries are answered in the form of a GUI that points the user to the location of the relevant documents.

The following sections describe these modules m greater detail.

2.1 Surveying the Desk

The desk-top surveillance system consists of a Canon VC-C1 camera with zooming capabilities that is mounted on a pan-tilt computer steerable platform. The camera is connected to a Silicon Graphics Indy

(SGI) that controls its operation. Our initial experi­ ments established that the manufacturer's motion con­ trol for this camera is inadequate for two reasons: it is inaccurate and inflexible. Instead of using the com­ mercially supplied controller we developed an expres­ sive interface and accurate control. The following op­ erations are currently supported: (1) pan or tilt along the entire sweeping range , (2) pan or tilt to a spe­ cific location, (3) zoom to a specific location, and (4) capture the image.

2.2 Extracting Documents from Images

Currently, it is near-impossible to extract concep­ tual information about arbitrary three dimensional objects that are subject to noise and occlusion. How­ ever, since we restrict the objects in our application to be standard paper documents, we can develop effec­ tive segmentation algorithms. Consider Figure 2. It represents the image of a desk-top taken with a very low-resolution camera and the corresponding edge­ detected image. The edge-detected image has signifi­ cant noise but enough detail that can be detected and parsed automatically.

One important feature of a segmentation algorithm for this application is robustness in the presence of noise. Noise arises naturally here in two ways. Every time a human touches a paper on the desk, its position may be shifted by a small amount. The segmentation algorithm should tolerate this. Second, when papers are stacked on top of one another as in Figure 2( right) the edges of the stack are not perfectly aligned. The segmentation algorithm should find one set of edges only to approximate the location of the stack.

We have developed a statistical segmentation algo­ rithm that has noise tolerance built-in. This algorithm has four steps. Step 1 compares the base image taken when the last event was detected against the current image. When a change is detected, the area of change is extracted from the image. Step 2 generates a new image of maximal detail that contains the entire area identified in Step 1. This is accomplished by aiming and zooming the camera. The correct camera motion (pan/tilt/zoom parameters) is computed by using the absolute camera and desk space coordinates, and the relative coordinates of the area of interest in the space. Step 3 identifies the enclosing border of the area of in­ terest. This algorithm relies on object features and uses statistics on pixels to recognize and enclose the page boundaries. The basic idea is to do a walk along pixels that identifies a simple polygon, called the bor­ der polygon. The greatest challenge of this algorithm is noise: for the case of a desk-top, any form of object manipulation is likely to displace the paper by a small amount. Our algorithm uses statistics to address the slop problem by fitting a line through the pixels in an incremental fashion. Figure 3 shows a snapshot from the execution of this algorithm. Finally, the fourth step of the algorithm takes the border polygon and parses it to identify the pages. For the self-organizing desk application, this reduces to finding a cover of this polygon by rectangles, that is consistent with the doc­ ument history. In our current implementation we as­ sume that the documents on the desk top can only be translated relative to each other. We use this as­ sumption to determine the vertices of a new document when the difference between the current image and the previous image returns 1, 2, or 3 vertices only. This situation arises when the new document overlaps ex­ isting documents on the desk.

2.3 Capturing Electronic Information about the Desk

The output of the border detection and document extraction algorithm consists of the relative coordi­ nates of the page within the physical space. These coordinates are used to compute a camera configura­ tion that can capture a new image of the object of in­ terest, of maximal detail. This new image is ready for information extraction. A multitude offeatures is use­ ful for defining attributes users can query on: arrival time of the document, physical location of the doc­ ument, textual content, figures, color, tabular data, and layout content (for instance, is the document a letter?). Visual and layout cues like tables, color, and figures , complement the textual content of documents and they play an equally important role in information access.

The self-organizing desk supports queries that com­ bine textual with layout information through multiple representations, each representation corresponding to an attribute detectable by a filter. This information extraction is carried by a library of smart filters . Our current library consists of three filters: OCR, color, and tables, but the architecture is expandable and we will add new filters in the future .

OCR. We have investigated the use of text filters (OCR systems) on camera images. We found that commercial OCR systems do not work well on images because the resolution is not high enough. Our ap­ proach was to enhance the resolution by dividing the image into n subimages (n is determined by the desired OCR accuracy), doing a linear interpolation for each pixel in. the resulting images, and feeding the result­ ing images to the OCR system. This method improved the performance of the OCR system from 60% to 95% in character recognition accuracy.

Color. The color filter works by building a color his­ togram annotated with layout information for each object. The filter determines the 24 most prevalent colors occuring in the document and the location of each color. Location is a layout attribute determined by placing a 3 x 3 grid on the paper.

Space, time, and history. Each paper gets as­ signed a location on the desk by using the coordinates computed by the camera. Each paper is also time stamped. In addition, each paper is associated with a list of papers above it and papers below it, to cap­ ture the history of the desk-top. This information is necessary to implement the stack-shift operation. It is also necessary to estimate the location of a docu­ ment on the desk if the document is covered by other documents.

2.4 Searching, Organizing, and Visualiz­ ing the Desk

The filters defined in Section 2.3 generate a web of representations for each document. We compile this multiplicity of representations in a database. In this database we also capture temporal information for each document (its arrival time on the desk) , spatial information (its location on the physical desk), and history information (if the paper is in a pile, which documents are above it, and which documents are be­ low it .) This database supports the following desk op­ erations: adding a paper to a random location on the desk, removing a paper from the desk, and re-locating a paper or a stack on papers on the desk. The informa­ tion in this database changes dynamically, as driven by these operations. In response to each event, the database is updated automatically.

The database comprises a collection of inverted in­ dices, one for each attribute. An inverted index asso­ ciates each attribute instance with a list of documents containing it. The advantage of this representation scheme is a speed-up in search: given a specific at­ tribute (an word, a color, etc.), the list of documents containing this attribute is available in constant time.

We implemented several methods for searching, or­ ganizing, and visualizing the contents of this database.

Search. The self-organizing desk can be queried with keywords, with an entire document (full text), with color and layout information, with table informa­ tion, and any boolean combination of these attributes. We use an augmented version of the Smart System [Sal91], which is a sophisticated text-retrieval system. We augmented Smart to also support color, layout, and table indices. Smart copes well with partially corrupted (by OCR) text. Its basic premise is that two documents are similar if they use the same words. Documents and queries are modeled as points in a vec­ tor space defined by the important words occurring in the corpus. When all texts and text queries are rep­ resented as weighted vectors, a similarity measure can be computed between pairs of vectors that captures the text similarity. We use this similarity measure as the basis for computing hyperlinks between docu­ ments that are similar to each other in this statistical framework .

Organization. The textual information contained in the documents on the desk is organized by topic using our own clustering algorithm (called the star al­ gorithm) on the vectors in the document space. Our implementation uses a modification of the Smart sys­ tem and the underlying cosine metric. The star algo­ rithm gives a hierarchical organization of a collection into clusters. Each level in the hierarchy is determined by a threshold for the minimum similarity between pairs of documents within a cluster at that particular level in the hierarchy. This method conveys the topic­ subtopic structure of the corpus according to the sim­ ilarity measure used. The star algorithm is accurate in that it produces dense clusters that approximate cliques with provable guarantees on the pairwise simi­ larity between cluster documents, yet are computable in O(E), where E is the number of edges above thresh­ old in the document collection 2 . The documents in each cluster are tightly inter-related and a minimum similarity distance between all the document pairs in the cluster is guaranteed. This resulting structure re­ flects the underlying topic structure of the data.

Summaries. A topic summary for each cluster com­ puted by the star algorithm is provided by the center of the underlying star for the cluster.

Visualization. We developed a visualization method for organized data that presents users with three views of the data: a Euclidean projection of the documents on the planar representation of the desk, a graph that shows the similarity relationship between all the documents, and a graph that shows the topic structure of the desk. The views allow users to select objects with a mouse and they are connected in that when an object is selected in one view, it gets high­ lighted in the other views. For instance, the user may select a cluster, which will highlight the areas of the desk where the documents in the cluster are located.

3 Experiments

We implemented all the modules described in Sec­ tion 2 and constructed the following experiment. The VC-Cl camera is mounted on the tripod and con­ nected to an SGI. The OCR package we use is EasyRead (which is a version of ScanWorks ported to SGis.) The desk-top is set up vertically, on a wall . Documents are added/removed by pasting/removing them on the wall. Users interact with this system by physically moving papers, by entering queries in the GUI (see Figure 4) , and by observing the visualization of the results returned by the search engine.

2 E is at most N 2 , where N is the number of documents.

We have repeated the following two experiments over fifty times recently. In the first experiment, three papers were added sequentially to the desk. The sec­ ond paper was placed to overlap the first paper and the third paper was placed to overlap the previous two. In the second experiment we created a desk top by adding three papers sequentially. The first paper was placed randomly. The second paper was placed as in the first experiment. The third paper was placed approxi­ mately above the first paper so as to make up a stack. The addition of each paper was noticed by the cam­ era, which triggered the main loop through the self­ organization system. The location of each paper was computed by the segmentation module, the camera was then zoomed to capture the document location, the extracted images was passed through the OCR fil­ ter and the color filter. The results of these operations were entered in the database along with the space, time, and history of the document and the database was updated with this information. The database was then organized by content and summarized using the topic clustering and summarization algorithms. The experimental data for the segmentation and OCR as­ pects of the system is presented in Figure 5. Our hu­ man user input the following queries: "orange in upper right corner and distributed mobile robotics", "green anywhere", and "manipulation" . For all' these queries the relevant documents were identified and the user was given pointers to their physical location of the desk. The only query failures we observed are for key­ word searches on words corrupted by OCR.

The system takes approximately 30 seconds to de­ termine a change on the desk. The enhanced OCR scheme (that processes and then merges 9 individual images per page) takes approximately 15 minutes, the initialization and update of the database takes negli­ gible time (less than 1 second), and the queries take negligible time (less than 1 second.)

The failures of the system are due to the cam­ era and the OCR. The current camera resolution and the current implementation of the segmentation algo­ rithm make it impossible to distinguish corners that are closer than 1cm to each other. OCR is too slow. The character recognition is poor even with our en­ hancements. This problem could be solved by using a higher-resolution camera and a better OCR package.

4 Related Work

Efforts to enhance physical environments with electronic information include The Intelligent Room project at the AI Lab at MIT and the ALIVE project at the Media Lab at MIT, The goal of the Intelligent Room project is to create a room surveyed by cameras that can recognize and understand physical gestures. Progress on this project has been reported in [Tor95]. The ALIVE project allows users to interact with an­ imated electronic characters and has been descibed in [Mae95].0ther related projects include efforts from Euro Xerox and Hitachi to create interactive desks, where the user can write with a stylus pen on the desk top. The desk-top consists of a display that can capture the user's input. A camera mounted on the desk top is used to project on the desk top rather than extract information [AM+95].

The self-organizing desk draws from progress made in several areas: self-organizing systems [Koh90, CKP93], information retrieval and organi­ zation [Sal91, RA95], robotics and vision [MRR96, HKR93], automated document structuring [TA92, RS95b, NSV92], and user interfaces [CAC93] .

5 Discussion

We have described a system that implements the self-organization metaphor to enhance a physical space with electronic information. This system uses a number of key technologies in robotics, computer vision, OCR, information retrieval, filtering, and orga­ nization, and integrates them into a system that solves a new application. Our experiments demonstrate the feasibility and power of enhancing a desk-top with the electronic information extracted from the objects on the desk top. Applications of the technology demon­ strated by this work reach beyond the self-organizing desk, into the area of using smart sensors for informa­ tion processing in augmented reality. Candidates are dynamically changing physical space whose objects are simple enough that segmentation and feature extrac­ tion is possible. The smart sensors will support index­ ing, searching, and organizing the physical space. One immediate extension is a self-organizing bookcase.

The biggest computation sink in this system is the image segmentation module and the OCR. OCR per­ forms poorly on camera-extracted images. We by­ passed this problem by scanning images. We are cur­ rently building a self-organizing filing cabinet where documents are actively scanned in before being filed away. Our preliminary tests show that this system is fast and more reliable. In parallel with this effort, we are also developing better image segmentation tools for desk tops, smarter filters, and better GUis.

Acknowledgements

The camera control package was implemented by Scott Silver. The first version of the image segmen­ tation package was implemented by Michael Taylor . The color filter and G UI was implemented by Hans Kieserman and the information organization system was implemented by Katya Pelekhov. We thank Carlo Tomasi for the initial discussion on image segmenta­ tion in the presence of slop.