A Rao-Blackwellized particle filter for EigenTracking - Zia Khan; Balch, T.; Dellaert, F. (Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004, 2004)
Subspace representations have been a popular way to model appearance in computer vision. In Jepson and Black's influential paper on EigenTracking, they were successfully applied in tracking. For noisy targets, optimization-based algorithms (including EigenTracking) often fail catastrophically after losing track. Particle filters have recently emerged as a robust method for tracking in the presence of multi-modal distributions. To use subspace representations in a particle filter, the number of samples increases exponentially as the state vector includes the subspace coefficients. We introduce an efficient method for using subspace representations in a particle filter by applying Rao-Blackwellization to integrate out the subspace coefficients in the state vector. Fewer samples are needed since part of the posterior over the state vector is analytically calculated. We use probabilistic principal component analysis to obtain analytically tractable integrals. We show experimental results in a scenario in which we track a target in clutter.
Keywords: analytically tractable integrals; Computer vision; EigenTracking; Filters; Gaussian processes; modal analysis; multi-modal distributions; NOISE; noisy targets; optimisation; optimization-based algorithms; Particle filters; Particle measurements; Particle tracking; Principal component analysis; probabilistic principal component analysis; Rao-Blackwellized particle filter; Robustness; SHAPE; State estimation; state vector; subspace coefficients; Subspace representations; target tracking; vectors

Real-Time Kernel-Based Tracking in Joint Feature-Spatial Spaces - Yang,Changjiang; Duraiswami, Ramani; Elgammal,Ahmed; Davis, Larry S. (Technical Reports from UMIACS, 2004)
An object tracking algorithm that uses a novel simple symmetric similarityfunction between spatially-smoothed kernel-density estimates of the model and target distributions is proposed and tested. The similarity measure is based on the expectation of the density estimates over the model or target images. The density is estimated using radial-basis kernel functions which measure the affinity between points and provide a better outlier rejection property. The mean-shift algorithm is used to track objects by iteratively maximizing this similarity function. To alleviate the quadratic complexity of the density estimation, we employ Gaussian kernels and the fast Gauss transform to reduce the computations to linear order. This leads to a very efficient and robust nonparametric tracking algorithm. The proposed algorithm is tested with several image sequences and shown to achieve robust and reliable real-time tracking. (UMIACS-TR-2004-12)
Keywords: Technical Report

Reconfigurable optical wireless sensor networks - Llorca,Jaime; Desai,Aniket; Vishkin, Uzi; Davis,Christopher C.; Milner,Stuart D (Proceedings of SPIE, 2004)
Optical wireless networks are emerging as a viable, cost effective technology for rapidly deployable broadband sensor communication infrastructures. The use of directional, narrow beam, optical wireless links provides great promise for secure, extremely high data rate communication between fixed or mobile nodes, very suitable for sensor networks in civil and military contexts. The main challenge is to maintain the quality of such networks, as changing atmosphericand platform conditions critically affect their performance. Topology control is used as the means to achieve survivable optical wireless networking under adverse conditions, based on dynamic and autonomous topology reconfiguration. The topology control process involves tracking and acquisition of nodes, assessment of link-state information, collection and distribution of topology data, and the algorithmic solution of an optimal topology. This paper focuses onthe analysis, implementation and evaluation of algorithms and heuristics for selecting the best possible topology in order to optimize a given performance objective while satisfying connectivity constraints. The work done at the physical layer is based on link cost information. A cost measure is defined in terms of bit-error-rate and the heuristics developed seek to form a bi-connected topology which minimizes total network cost. At the network layer a key factor is the traffic matrix, and heuristics were developed in order to minimize congestion, flow-rate or end-to-end delay.

Recording and reproducing high order surround auditory scenes for mixed and augmented reality - Zhiyun Li; Duraiswami, Ramani; Davis, Larry S. (Mixed and Augmented Reality, 2004. ISMAR 2004. Third IEEE and ACM International Symposium on, 2004)
Virtual reality systems are largely based on computer graphics and vision technologies. However, sound also plays an important role in human's interaction with the surrounding environment, especially for the visually impaired people. In this paper, we develop the theory of recording and reproducing real-world surround auditory scenes in high orders using specially designed microphone and loudspeaker arrays. It is complementary to vision-based technologies in creating mixed and augmented realities. Design examples and simulations are presented.
Keywords: array; audio; auditory; augmented; Computer; graphics; high; loudspeaker; microphone; mixed; order; processing; reality; reality; scene; signal; surround; system; technology; virtual; VISION; vision

Recursions for the computation of multipole translation and rotation coefficients for the 3-D Helmholtz equation - Gumerov, Nail A.; Duraiswami, Ramani (SIAM Journal on Scientific Computing, 2004)
We develop exact expressions for the coefficients of series representations of trans-lations and rotations of local and multipole fundamental solutions of the Helmholtz equation in spherical coordinates. These expressions are based on the derivation of recurrence relations, some of which, to our knowledge, are presented here for the first time. The symmetry and other properties of the coefficients are also examined and, based on these, efficient procedures for calculating them are presented. Our expressions are direct and do not use the Clebsch–Gordan coefficients or the Wigner 3-j symbols, although we compare our results with methods that use these to prove their accuracy. For evaluating an Nt term truncation of the translated series (involving O(N2t) multipoles), our expressions require O(N3t) evaluations, compared to previous exact expressions that require O(N5t) operations.

Rendering localized spatial audio in a virtual auditory space - Zotkin,Dmitry N; Duraiswami, Ramani; Davis, Larry S. (IEEE Transactions on Multimedia, 2004)
High-quality virtual audio scene rendering is required for emerging virtual and augmented reality applications, perceptual user interfaces, and sonification of data. We describe algorithms for creation of virtual auditory spaces by rendering cues that arise from anatomical scattering, environmental scattering, and dynamical effects. We use a novel way of personalizing the head related transfer functions (HRTFs) from a database, based on anatomical measurements. Details of algorithms for HRTF interpolation, room impulse response creation, HRTF selection from a database, and audio scene presentation are presented. Our system runs in real time on an office PC without specialized DSP hardware.
Keywords: -D audio processing; 3-D audio processing; Audio databases; audio signal processing; audio user interfaces; augmented reality; data sonification; Digital signal processing; head related transfer functions; head-related transfer function; Interpolation; Layout; perceptual user interfaces; Real time systems; Rendering (computer graphics); Scattering; spatial audio; Transfer functions; User interfaces; virtual audio scene rendering; virtual auditory spaces; virtual environments; Virtual reality; virtual reality environments

Rendering localized spatial audio in a virtual auditory space - Zotkin,Dmitry N; Duraiswami, Ramani; Davis, Larry S. (Multimedia, IEEE Transactions on, 2004)
High-quality virtual audio scene rendering is required for emerging virtual and augmented reality applications, perceptual user interfaces, and sonification of data. We describe algorithms for creation of virtual auditory spaces by rendering cues that arise from anatomical scattering, environmental scattering, and dynamical effects. We use a novel way of personalizing the head related transfer functions (HRTFs) from a database, based on anatomical measurements. Details of algorithms for HRTF interpolation, room impulse response creation, HRTF selection from a database, and audio scene presentation are presented. Our system runs in real time on an office PC without specialized DSP hardware.
Keywords: (computer; 3-D; audio; audio; auditory; augmented; data; environments; functions; graphics); Head; interfaces; perceptual; processing; reality; reality; related; rendering; rendering; scene; signal; sonification; spaces; spatial; transfer; user; virtual

Representation and Recognition of Events in Surveillance Video Using Petri Nets - Ghanem,N.; DeMenthon,D.; David Doermann; Davis, Larry S. (Second IEEEWorkshop on Event Mining 2004, CVPR2004, 2004)
Detection of events is an essential task in surveillance applications. This task requires finding a general event representation method and developing efficient recognition algorithms dealing with this representation. In this paper, we describe an interactive system for querying surveillance video about events. The queries may not be known in advance and have to be composed from primitive events and previously defined queries. We propose using Petri nets as both representation and recognition methods. The Petri net representation for users' queries is derived automatically from simpler event nets. Recognition is then performed by tokens moving through the Petri nets.

Robust Point Matching for Non-Rigid Shapes: ARelaxation Labeling Based Approach - Yefeng Zheng; David Doermann (University of Maryland, College Park, 2004)
Shape matching or image registration, which is often formulated as a point matching problem, is frequently encountered in image analysis, computer vision, and pattern recognition. Although the problem of registering rigid shapes was widely studied, non-rigid shape matching has recently received more and more attention. For non-rigid shapes, most neighboring points cannot move independently under deformation due to physical constraints. Therefore, though the absolute distance between two points may change significantly, the neighborhood of a point is well preserved in general. Based on this observation, we formulate point matching as a graph matching problem. Each point is a node in the graph, and two nodes are connected by an edge if their Euclidean distance is less than a threshold. The optimal match between two graphs is the one that maximizes the number of matched edges. The shape context distance is used to initialize the graph matching, and relaxation labeling (after enforcing one-to-one matching) is used to refine the matching results. Non-rigid deformation is overcome by bringing one shape closer to the other in each iteration using deformation parameters estimated from the current point correspondence. Experiments on real and synthesized data demonstrate the effectiveness of our approach: it outperforms shape context and TPS-RPM algorithms under non-rigid deformation and noise on a public data set.

RT-S: Surface rich transcription scoring, methodology, and initial results - Snover,M.; Schwartz,R.; Dorr, Bonnie J; Makhoul,J. (Proc. DARPA Rich Transcription Workshop, 2004)
In this paper we present a methodoly for the scoring ofpunctuation annotated texts, as well as a preliminary system to perform the task. We modify SCLITE’s scoring method- ology to support scoring of punctuation. Using this method- ology, we show that the error rate of an initial automatic sys- tem is comparable to annotator inconsistency. However, the use of multiple references allows us to differentiate between human inconsistencies and system errors.

Searching the web with mobile images for location recognition - Tom Yeh; Tollmar,K.; Darrell,T. (Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, 2004)
We describe an approach to recognizing location from mobile devices using image-based Web search. We demonstrate the usefulness of common image search metrics applied on images captured with a camera-equipped mobile device to find matching images on the World Wide Web or other general-purpose databases. Searching the entire Web can be computationally overwhelming, so we devise a hybrid image-and-keyword searching technique. First, image-search is performed over images and links to their source Web pages in a database that indexes only a small fraction of the Web. Then, relevant keywords on these Web pages are automatically identified and submitted to an existing text-based search engine (e.g. Google) that indexes a much larger portion of the Web. Finally, the resulting image set is filtered to retain images close to the original query. It is thus possible to efficiently search hundreds of millions of images that are not only textually related but also visually relevant. We demonstrate our approach on an application allowing users to browse Web pages matching the image of a nearby location.

Selective refinement on nested tetrahedral meshes - De Floriani, Leila; Lee,M. (Geometric Modeling for Scientific VisualizationGeometric Modeling for Scientific Visualization, 2004)

Selective refinement queries for volume visualization of unstructured tetrahedral meshes - Cignoni,P.; De Floriani, Leila; Magillo,P.; Puppo,E.; Scopigno,R. (Visualization and Computer Graphics, IEEE Transactions on, 2004)
We address the problem of the efficient visualization of large irregular volume data sets by exploiting a multiresolution model based on tetrahedral meshes. Multiresolution models, also called Level-Of-Detail (LOD) models, allow encoding the whole data set at a virtually continuous range of different resolutions. We have identified a set of queries for extracting meshes at variable resolution from a multiresolution model, based on field values, domain location, or opacity of the transfer function. Such queries allow trading off between resolution and speed in visualization. We define a new compact data structure for encoding a multiresolution tetrahedral mesh built through edge collapses to support selective refinement efficiently and show that such a structure has a storage cost from 3 to 5.5 times lower than standard data structures used for tetrahedral meshes. The data structures and variable resolution queries have been implemented together with state-of-the art visualization techniques in a system for the interactive visualization of three-dimensional scalar fields defined on tetrahedral meshes. Experimental results show that selective refinement queries can support interactive visualization of large data sets.
Keywords: Automated; Signal Processing; Computer-Assisted; Imaging; Computer-Assisted; User-Computer Interface; data structure; geometric modeling; interactive visualization; large data sets; multiresolution model; selective refinement queries; unstructured tetrahedral meshes; variable resolution queries; volume data visualization; data visualisation; mesh generation; query p; Three-Dimensional; Online Systems; Pattern Recognition

Semantic annotation and lexico-syntactic paraphrase - Dorr, Bonnie J; Green,R.; Levin,L.; Rambow,O.; Farwell,D.; Habash,N.; Helmreich,S.; Hovy,E.; Miller,K.J.; Mitamura,T.; others (Proceedings of the 4th International Conference on Language Resources and Evaluation (LREC) Workshop on Building Lexical Resources from Semantically Annotated Corpora, 2004)
The IAMTC project (Interlingual Annotation of Multilingual Translation Corpora) is developing an interlingual representation frameworkfor annotation of parallel corpora (English paired with Arabic, French, Hindi, Japanese, Korean, and Spanish) with deep-semantic representations. In particular, we are investigating meaning equivalent paraphrases involving conversives and non-literal language use, as well as extended paraphrases involving syntax, lexicon, and grammatical features. The interlingua representation has three levels of depth. Each level is characterized by the types of meaning equivalent paraphrases that receive identical representations at that level.

Semantic Annotation for Interlingual Representation of Multilingual Texts - Mitamura,T.; Miller,K.; Dorr, Bonnie J; Farwell,D.; Habash,N.; Helmreich,S.; Hovy,E.; Levin,L.; Rambow,O.; Reeder,F.; others (Workshop Programme, 2004)
This paper describes the annotation process being used in a multi-site project to create six sizable bilingual parallel corpora annotated with a consistent interlingua representation. After presenting the background and objectives of the effort, we describe the multilingual corpora and the three stages of interlingual representation being developed. We then focus on the annotation process itself, including an interface environment that supports the annotation task, and the methodology for evaluating the interlingua representation. Finally, we discuss some issues encountered during the annotation tasks. The resulting annotated multilingual corpora will be useful for a wide range of natural language processing research tasks, including machine translation, question answering, text summarization, and information extraction.

Sequential kernel density approximation through mode propagation: applications to background modeling - Han,B.; Comaniciu, D.; Davis, Larry S. (Proc. ACCV, 2004)
Density-based modeling of visual features is very commonin computer vision, either by using non-parametric techniques or through representing the underlying density function as a weighted sum of Gaussians. A number of real-time tasks such as background modeling or modeling the appearance of a moving target require sequential density estimation, where new data is incorporated in the model as it becomes avail- able. Nevertheless, current methods for updating the den- sity function either lack flexibility, by fixing the number of Gaussians in the mixture, or require large memory amounts, by maintaining a non-parametric representation of the den- sity. This paper presents an efficient method for recursive density approximation that relies on the propagation of the density modes. At each time step, the modes of the density are re-estimated and a Gaussian component is assigned to each mode. The covariance of each component is derived from the Hessian matrix estimated at the mode location. To detect the modes we employ the variable-bandwidth mean shift. While the proposed density representation is mem- ory efficient (which is typical for mixture densities), it in- herits the flexibility of non-parametric methods, by allow- ing the number of modes to adapt in time. We show that the same mode propagation principle applies for subspaces derived from eigen analysis. Extensive experimental back- ground modeling results demonstrate the performance of the method.

Shot boundary detection based on Image correlation features in video - Luo,Ming; DeMenthon,D.; David Doermann (TREC-VID: Text Retrieval and Evaluation Conference, 2004)
This paper introduced a framework of shot boundary detection used by the LAMPLAB, University of Maryland, College Park. It deals with cuts and dissolves detection. Generally, it is based on image correlation features in the videos. The cut detection is based on the so-called 2max ratio criterion in a sequential image buffer. The dissolve detection is based on the skipping image difference and linearity error in a sequential image buffer. We also eliminated the effect of flashlights in our algorithms. We submitted 5 runs to TRECVID 2004. Their run-ids are “D0, D1, … , D4”. They use the same algorithms with different parameter settings. These runs show a tradeoff curve between precision and recall on the testing data of TRECVID 2004.

Similarity measure for nonparametric kernel density based object tracking - Yang,C.; Duraiswami, Ramani; Davis, Larry S. (Eighteenth Annual Conference on Neural Information Processing Systems, Vancouver, 2004)
An object tracking algorithm using a novel simple symmetric similar-ity function between spatially-smoothed kernel-density estimates of the model and target distributions is proposed and tested. The similarity measure is based on the expectation of the density estimates over the model or target images. The density is estimated using radial-basis ker- nel functions that measure the affinity between points and provide a bet- ter outlier rejection property. The mean-shift algorithm is used to track objects by iteratively maximizing this similarity function. To alleviate the quadratic complexity of the density estimation, we employ Gaussian kernels and the fast Gauss transform to reduce the computations to linear order. This leads to a very efficient and robust nonparametric tracking al- gorithm. The proposed algorithm is tested with several image sequences and shown to achieve robust and reliable real-time tracking. Several se- quences are placed at http://www.cs.umd.edu/users/yangcj/node3.html.

SoftPOSIT: Simultaneous pose and correspondence determination - David,P.; DeMenthon,D.; Duraiswami, Ramani; Samet, Hanan (International Journal of Computer Vision, 2004)
The problem of pose estimation arises in many areas of computer vision, including object recognition, object tracking, site inspection and updating, and autonomous navigation when scene models are available. We present a new algorithm, called SoftPOSIT, for determining the pose of a 3D object from a single 2D image when correspondences between object points and image points are not known. The algorithm combines the iterative softassign algorithm (Gold and Rangarajan, 1996; Gold et al., 1998) for computing correspondences and the iterative POSIT algorithm (DeMenthon and Davis, 1995) for computing object pose under a full-perspective camera model. Our algorithm, unlike most previous algorithms for pose determination, does not have to hypothesize small sets of matches and then verify the remaining image points. Instead, all possible matches are treated identically throughout the search for an optimal pose. The performance of the algorithm is extensively evaluated in Monte Carlo simulations on synthetic data under a variety of levels of clutter, occlusion, and image noise. These tests show that the algorithm performs well in a variety of difficult scenarios, and empirical evidence suggests that the algorithm has an asymptotic run-time complexity that is better than previous methods by a factor of the number of image points. The algorithm is being applied to a number of practical autonomous vehicle navigation problems including the registration of 3D architectural models of a city to images, and the docking of small robots onto larger robots.

Sonification of geo-referenced data for auditory information seeking: Design principle and pilot study - Zhao,H.; Plaisant, Catherine; Shneiderman, Ben; Duraiswami, Ramani (Proceedings of ICAD, 2004)
We present an Auditory Information Seeking Principle (AISP)(gist, navigate, filter, and details-on-demand) modeled after the visual information seeking mantra [1]. We propose that data sonification designs should conform to this principle. We also present some design challenges imposed by human auditory perception characteristics. To improve blind access to geo- referenced statistical data, we developed two preliminary sonifications adhering to the above AISP, an enhanced table and a spatial choropleth map. Our pilot study shows people can recognize geographic data distribution patterns on a real map with 51 geographic regions, in both designs. The study also shows evidence that AISP conforms to people’s information seeking strategies. Future work is discussed, including the improvement of the choropleth map design.

A spherical microphone array system for traffic scene analysis - Zhiyun Li; Duraiswami, Ramani; Grassi,E.; Davis, Larry S. (Intelligent Transportation Systems, 2004. Proceedings. The 7th International IEEE Conference on, 2004)
This paper describes a practical spherical microphone array system for traffic auditory scene capture and analysis. Our system uses 60 microphones positioned on the rigid surface of a sphere. We then propose an optimal design of a robust spherical beamformer with minimum white noise gain (WNG) of -6 dB. We test this system in a real-world traffic environment. Some preliminary simulation and experimental results are presented to demonstrate its performance. This system may also find applications in broader areas such as 3D audio, virtual environment, etc.
Keywords: -6; 3D; analysis; array; arrays; audio; auditory; beamformer; capture; dB; environment; gain; microphone; NOISE; noise; processing; real; robust; scene; signal; spherical; system; traffic; traffic; virtual; white; World

Structure of applicable surfaces from single views - Gumerov, Nail A.; Zandifar,A.; Duraiswami, Ramani; Davis, Larry S. (Computer Vision-ECCV 2004, 2004)
The deformation of applicable surfaces such as sheets of paper satisfies the differential geometric constraints of isometry (lengths and areas are conserved) and vanishing Gaussian curvature. We show that these constraints lead to a closed set of equations that allow recovery of the full geometric structure from a single image of the surface and knowledge of its undeformed shape. We show that these partial differential equations can be reduced to the Hopf equation that arises in non-linear wave propagation, and deformations of the paper can be interpreted in terms of the characteristics of this equation. A new exact integration of these equations is developed that relates the 3-D structure of the applicable surface to an image. The solution is tested by comparison with particular exact solutions. We present results for both the forward and the inverse 3D structure recovery problem.

A study of the pinna anthropometry and the spectral notch frequencies - Raykar,Vikas C.; Duraiswami, Ramani; Yegnanarayana,B. (The Journal of the Acoustical Society of America, 2004)
The head‐related transfer function (HRTF) varies significantly between individuals due to the different sizes and shapes of different anatomical parts like the pinnae, head, and torso. Applications in the creation of virtual auditory displays require individual HRTFs for perceptual fidelity. A generic HRTF would not work satisfactorily, since it has been shown that nonindividual HRTFs result in poor elevation perception. While good geometrical models exist for the effects of head, torso, and shoulders, a simple model for the pinna that connects the anthropometry to the features in the HRTF does not exist. One of the prominent cues contributed by the pinna are the sharp spectral notches, which encode the elevation of the sound source. Recently, we proposed a method to extract the frequencies of the pinna spectral notches from the HRTF. In this paper we study the relationship between the extracted notch frequency and pinna anthropometry. Based on these observations new approaches for HRTF customization can be developed. [The support of NSF Award ITR‐0086075 is gratefully acknowledged.]

Supervised clustering with the dirichlet process - Daumé, Hal; Marcu,D. (NIPS'04 Learning With Structured Outputs Workshop, 2004)

Symbolic MT With Statistical NLP Components - Dorr, Bonnie J; Habash,Nizar Y; Monz,Christof (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
This reports provides an overview of the findings and software that have evolved from the "Symbolic MT with Statistical NLP Components" project over the last year. We present the major goals that have been achieved and discuss some of the open issues that we intend to address in the near future. This report also contains some details on the usage of some software that has been implemented during the project.
Keywords: *MACHINE TRANSLATION; computational linguistics; COMPUTER PROGRAMS; CYBERNETICS; DIVERGENCE UNRAVELING; GHMT(GENERATION-HEAVY MACHINE TRANSLATION); INFORMATION SCIENCE; linguistics; natural language; RESOURCE PROJECTION

TM Electromagnetic Scattering from 2D Multilayered Dielectric Bodies-Numerical Solution - Duraiswami, Ramani; Seydou,F.; Gumerov, Nail A. (Applied Computational Electromagnetics Society journal, 2004)
An integral equation approach is derived for an electromagnetic scattering from an M arbitrary multilayereddielectric domain. The integral equation is valid for the 2D and 3D Helmholtz equation. Here we show the numerical solution for the 2D case by using the Nyström method. For validating the method we develop a mode matching method for the case when the domains are multilayered circular cylinders and give numerical results for illustrating the algorithm.

Tools for children to create physical interactive storyrooms - Montemayor,J.; Druin, Allison; Chipman,G.; Farber,A.; Guha,M.L. (Computers in Entertainment (CIE), 2004)

TOSS: an extension of TAX with ontologies and similarity queries - Hung,Edward; Deng,Yu; V.S. Subrahmanian (Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004)
TAX is perhaps the best known extension of the relational algebra to handle queries to XML databases. One problem with TAX (as with many existing relational DBMSs) is that the semantics of terms in a TAX DB are not taken into account when answering queries. Thus, even though TAX answers queries with 100% precision, the recall of TAX is relatively low. Our TOSS system improves the recall of TAX via the concept of a similarity enhanced ontology (SEO). Intuitively, an ontology is a set of graphs describing relationships (such as isa, partof, etc.) between terms in a DB. An SEO also evaluates how similarities between terms (e.g. "J. Ullman", "Jeff Ullman", and "Jeffrey Ullman") affect ontologies. Finally, we show how the algebra proposed in TAX can be extended to take SEOs into account. The result is a system that provides a much higher answer quality than TAX does alone (quality is defined as the square root of the product of precision and recall). We experimentally evaluate the TOSS system on the DBLP and SIGMOD bibliographic databases and show that TOSS has acceptable performance.
Keywords: ontologies; semantic integration of heterogeneous data; similarity enhancement; XML databases

A tree-position kernel for document compression - Daumé, Hal; Marcu,D. (Proceedings of the Fourth Document Understanding Conference (DUC 2004), 2004)

Ubistatins Inhibit Proteasome-Dependent Degradation by Binding the Ubiquitin Chain - Verma,Rati; Peters,Noel R.; D'Onofrio,Mariapina; Tochtrop,Gregory P.; Sakamoto,Kathleen M.; Varadan,Ranjani; Zhang,Mingsheng; Coffino,Philip; Fushman, David; Deshaies,Raymond J.; King,Randall W. (Science, 2004)
To identify previously unknown small molecules that inhibit cell cycle machinery, we performed a chemical genetic screen in Xenopus extracts. One class of inhibitors, termed ubistatins, blocked cell cycle progression by inhibiting cyclin B proteolysis and inhibited degradation of ubiquitinated Sic1 by purified proteasomes. Ubistatins blocked the binding of ubiquitinated substrates to the proteasome by targeting the ubiquitin-ubiquitin interface of Lys48-linked chains. The same interface is recognized by ubiquitin-chain receptors of the proteasome, indicating that ubistatins act by disrupting a critical protein-protein interaction in the ubiquitin-proteasome system.

Uncalibrated stereo rectification for automatic 3D surveillance - Lim,S.-N.; Mittal,A.; Davis, Larry S.; Paragios,N. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
We describe a stereo rectification method suitable for automatic 3D surveillance. We take advantage of the fact that in a typical urban scene, there is ordinarily a small number of dominant planes. Given two views of the scene, we align a dominant plane in one view with the other. Conjugate epipolar lines between the reference view and plane-aligned image become geometrically identical and can be added to the rectified image pair line by line. Selecting conjugate epipolar lines to cover the whole image is simplified since they are geometrically identical. In addition, the polarities of conjugate epipolar lines are automatically preserved by plane alignment, which simplifies stereo matching.
Keywords: 3D; AUTOMATIC; conjugate; epipolar; image; lines; matching; method; processing; rectification; scene; stereo; surveillance; uncalibrated; urban

Unifying artifacts and activities in a visual tool for distributed software development teams - Jon Froehlich; Dourish,P. (26th International Conference on Software Engineering, 2004. ICSE 2004. Proceedings, 2004)
In large projects, software developers struggle with two sources of complexity - the complexity of the code itself, and the complexity of the process of producing it. Both of these concerns have been subjected to considerable research investigation, and tools and techniques have been developed to help manage them. However, these solutions have generally been developed independently, making it difficult to deal with problems that inherently span both dimensions. We describe Augur, a visualization tool that supports distributed software development processes. Augur creates visual representations of both software artifacts and software development activities, and, crucially, allows developers to explore the relationship between them. Augur is designed not for managers, but for the developers participating in the software development process. We discuss some of the early results of informal evaluation with open source software developers. Our experiences to date suggest that combining views of artifacts and activities is both meaningful and valuable to software developers.
Keywords: Augur; complexity management; distributed programming; distributed software development teams; open source software developers; program visualisation; Programming; public domain software; software artifacts; software engineering; software tools; visual representations; visual tool; visualization tool

Update operations on 3D simplicial decompositions of non-manifold objects - De Floriani, Leila; Hui,Annie (Proceedings of the ninth ACM symposium on Solid modeling and applications, 2004)
We address the problem of updating non-manifold mixed-dimensional objects, described by three-dimensional simplicial complexes embedded in 3D Euclidean space. We consider two local update operations, edge collapse and vertex split, which are the most common operations performed for simplifying a simplicial complex. We examine the effect of such operations on a 3D simplicial complex, and we describe algorithms for edge collapse and vertex split on a compact representation of a 3D simplicial complex, that we call the Non-Manifold Indexed data structure with Adjacencies (NMIA). We also discuss how to encode the information needed for performing a vertex split and an edge collapse on a 3D simplicial complex. The encoding of such information together with the algorithms for updating the NMIA data structure form the basis for defining progressive as well as multi-resolution representations for objects described by 3D simplicial complexes and for extracting variable-resolution object descriptions.

Use of Minimal Lexical Conceptual Structures for Single-Document Summarization - Dorr, Bonnie J; Habash,Nizar Y; Monz,Christof; Schwartz,Richard (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
This reports provides an overview of the findings and software that have evolved from the Use of Minimal Lexical Conceptual Structures for Single-Document Summarization project over the last six months. We present the major goals that have been achieved and discuss some of the open issues that we intend to address in the near future. This report also contains some details on the usage of some software that has been implemented during the project.
Keywords: *COMPUTATIONAL LINGUISTICS; AUTOMATIC HEADLINE GENERATION; CYBERNETICS; DOCUMENT SUMMARIZATION; Information retrieval; INFORMATION SCIENCE; linguistics; Machine translation

Using Trust in Recommender Systems: An Experimental Analysis - Massa,Paolo; Bhattacharjee, Bobby (Trust ManagementTrust Management, 2004)
Recommender systems (RS) have been used for suggesting items (movies, books, songs, etc.) that users might like. RSs compute a user similarity between users and use it as a weight for the users’ ratings. However they have many weaknesses, such as sparseness, cold start and vulnerability to attacks. We assert that these weaknesses can be alleviated using a Trust-aware system that takes into account the “web of trust” provided by every user. Specifically, we analyze data from the popular Internet web site epinions.com . The dataset consists of 49290 users who expressed reviews (with rating) on items and explicitly specified their web of trust, i.e. users whose reviews they have consistently found to be valuable. We show that any two users have usually few items rated in common. For this reason, the classic RS technique is often ineffective and is not able to compute a user similarity weight for many of the users. Instead exploiting the webs of trust, it is possible to propagate trust and infer an additional weight for other users. We show how this quantity can be computed against a larger number of users.
Keywords: Computer; Science

Visibility analysis and sensor planning in dynamic environments - Mittal,A.; Davis, Larry S. (Computer Vision-ECCV 2004, 2004)
We analyze visibility from static sensors in a dynamic scene with moving obstacles (people). Such analysis is considered in a probabilistic sense in the context of multiple sensors, so that visibility from even one sensor might be sufficient. Additionally, we analyze worst-case scenarios for high-security areas where targets are non-cooperative. Such visibility analysis provides important performance characterization of multi-camera systems. Furthermore, maximization of visibility in a given region of interest yields the optimum number and placement of cameras in the scene. Our analysis has applications in surveillance – manual or automated – and can be utilized for sensor planning in places like museums, shopping malls, subway stations and parking lots. We present several example scenes – simulated and real – for which interesting camera configurations were obtained using the formal analysis developed in the paper.

Visibility Planning: Predicting Continuous Period of Unobstructed Views - Lim,Ser-Nam; Davis, Larry S.; Wan,Yung-Chun (Justin) (Technical Reports from UMIACS, 2004)
To perform surveillance tasks effectively, unobstructed views ofobjects are required e.g. unobstructed video of objects are often needed for gait recognition. As a result, we need to determine intervals for video collection during which a desired object is visible w.r.t. a given sensor. In addition, these intervals are in the future so that the system can effectively plan and schedule sensors for collecting these videos. We describe an approach to determine these visibility intervals. A Kalman filter is first used to predict the trajectories of the objects. The trajectories are converted to polar coordinate representations w.r.t. a given sensor. Trajectories with the same angular displacement w.r.t. the sensor over time can be found by determining intersection points of functions representing these trajectories. Intervals between these intersection points are suitable for video collection. We also address the efficiency issue of finding these intersection points. An obvious brute force approach of $O(N^2)$ exists, where $N$ is the number of objects. This approach suffices when $N$ is small. When $N$ is large, we introduce an optimal segment intersection algorithm of $O(N\log^2N+I)$, $I$ being the number of intersection points. Finally, we model the prediction errors associated with the Kalman filter using a circular object representation. Experimental results that compare the performance of the brute force and the optimal segment intersection algorithms are shown. (UMIACS-TR-2004-22)
Keywords: Technical Report

Visualization and analysis of microarray and gene ontology data with treemaps - Baehrecke,Eric H; Dang,Niem; Babaria,Ketan; Shneiderman, Ben (BMC Bioinformatics, 2004)
The increasing complexity of genomic data presents several challenges for biologists. Limited computer monitor views of data complexity and the dynamic nature of data in the midst of discovery increase the challenge of integrating experimental results with information resources. The use of Gene Ontology enables researchers to summarize results of quantitative analyses in this framework, but the limitations of typical browser presentation restrict data access.

Web search intent induction via automatic query reformulation - Daumé, Hal; Brill,E. (Proceedings of HLT-NAACL 2004: Short Papers on XX, 2004)

Whole-genome shotgun assembly and comparison of human genome assemblies - Istrail,S.; Sutton,G. G; Florea,L.; Halpern,A. L; Mobarry,C. M; Lippert,R.; Walenz,B.; Shatkay,H.; Dew,I.; Miller,J. R; others (Proceedings of the National Academy of Sciences of the United States of America, 2004)

Window-based, discontinuity preserving stereo - Agrawal,M.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, 2004)
Traditionally, the problem of stereo matching has been addressed either by a local window-based approach or a dense pixel-based approach using global optimization. In this paper we present an algorithm which combines window-based local matching into a global optimization framework. Our local matching algorithm assumes that local windows can have at most two disparities. Under this assumption, the local matching can be performed very efficiently using graph cuts. The global matching is formulated as minimization of an energy term that takes into account the matching constraints induced by the local stereo algorithm. Fast, approximate minimization of this energy is achieved through graph cuts. The key feature of our algorithm is that it preserves discontinuities both during the local as well as global matching phase.
Keywords: algorithm; approach; based; cuts; dense; discontinuity; global; graph; image; local; MATCHING; matching; minimisation; optimization; Pixel; preserving; processing; stereo; theory; window

Word Level Script Identification on Scanned Document Images - Ma,Huanfeng; David Doermann (SPIEConference on Document Recognition and Retrieval, 2004)

19th Biennial Conference on Mechanical Vibration and Noise - Gupta,A. K.; Fadel,G. M.; Lewicki,D. G.; Shabana,A. A.; Royston,T. J.; Gupta,S.K.; Hayes,C.; Herrmann,J.W.; Dym,C. L.; Schmidt,L. C. (American Society of Mechanical Engineers, 2003)

A 2D profile reconstruction in a multilayered waveguide structure - Seydou,F.; Duraiswami, Ramani; Seppanen,T. (Antennas and Propagation Society International Symposium, 2003. IEEE, 2003)
We discuss the problem of finding a profile or its location for a 2D scattering of electromagnetic waves with fixed frequencies in a waveguide multilayered domain. We use the dual space method (DSM) of Colton and Monk. Our goal is to extend our previous work of TE and TM cases to the more complicated case of a waveguide. We emphasize on the frequency range in the reconstruction.
Keywords: (mathematics); 2D; dual; duality; electromagnetic; equations; inhomogeneous; Maxwell; media; method; multilayered; multilayers; profile; reconstruction; scattering; space; structure; theory; wave; waveguide; waveguides

Accuracy, Target Reentry and Fitts’ Law Performance of Preschool Children Using Mice - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison; Guimbretiere,F. (University of Maryland Technical Report, HCIL-2003, 2003)

Acoustical scattering from N spheres using a multilevel fast multipole method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2003)
We develop an efficient computational method for wave scattering from a large number of spherical objects that are characterized by their radii, locations, and complex acoustical impedances of the surfaces. The direct T‐matrix method for solution of the problem that was developed and tested in [Gumerov and Duraiswami, J. Acoust. Soc. Am. 112, 2688–2701 (2002)] is inefficient for computations involving a large number of scatterers. Here, we implement and test a multilevel fast multipole method for speeding up the solution and achieving better memory complexity. The method is based on hierarchical space subdivision with oct‐trees using optimal space‐partitioning, on a theory for fast translation and re‐expansion of multipole solutions of the Helmholtz equation, and employs an iterative technique for the solution of large dense systems of linear equations with reflection‐based iterations. For N scatterers the method provides O(N log N) asymptotic complexity opposed to O(N3) complexity of the direct T‐matrix approach. The results of computations were tested against solutions obtained by other methods, such as the boundary element method and the direct T‐matrix method tested in our early study, and show the computational efficiency and accuracy of the solution technique. [Work supported by NSF Awards 0086075 and 0219681 is gratefully acknowledged.]

Acquisition of bilingual MT lexicons from OCRed dictionaries - Karagol-Ayan,B.; David Doermann; Dorr, Bonnie J (Proceedings of the 9th MT Summit, 2003)
This paper describes an approach to analyzing the lexical structure of OCRed bilingual dictionaries to construct re-sources suited for machine translation of low-density languages, where online resources are limited. A rule-based, an HMM-based, and a post-processed HMM-based method are used for rapid construction of MT lexicons based on sys- tematic structural clues provided in the original dictionary. We evaluate the effectiveness of our techniques, concluding that: (1) the rule-based method performs better with dictionaries where the font is not an important distinguishing fea- ture for determining information types; (2) the post-processed stochastic method improves the results of the stochastic method for phrasal entries; and (3) Our resulting bilingual lexicons are comprehensive enough to provide the basis for reasonable translation results when compared to human translations.

Acquisition of Bilingual MTLexicons from OCRed Dictionaries - Karagol-Ayan,B.; David Doermann; Dorr, Bonnie J (Proceedings of the Ninth Machine Translation Summit, 2003)

Adaptive Hindi OCRUsing Generalized Hausdorff Image Comparison - Ma,Huanfeng; David Doermann (University of Maryland, College Park, 2003)
In this paper, we present an adaptive Hindi OCR using generalized Hausdor image comparison implemented as part of a rapidly retargetable language tool effort. The system includes: script identification, character segmentation, training sample creation and character recognition. The OCR design (completed in one month) was applied to a complete Hindi-English bilingual dictionary (with 1083 pages) and a collection of ideal images extracted from Hindi documents in PDF format. Experimental results show the recognition accuracy can reach 88% for noisy images and 95% for ideal images, both at the character level. The presented method can also be extended to design OCR systems for different scripts.

Algorithms for computing global accessibility cones - Dhaliwal,S.; Gupta,S.K.; Huang,J.; Priyadarshini,A. (Journal of Computing and Information Science in Engineering, 2003)

AModel-based Line Detection Algorithm in Documents - Zheng,Y.; Li,H.; David Doermann (ICDAR, 2003)

Analysis of particular phononic structures using single integral equations - Seydou,Fadoulourahmane; Duraiswami, Ramani; Gumerov, Nail A. (The Journal of the Acoustical Society of America, 2003)
A fast method for determining phononic (and photonic) bandgaps in composite materials is developed. It is known that in the propagation of waves in a 3D medium containing N scatterers arranged periodically, there exist refractive indices for which such structures have bandgaps, i.e., frequencies for which no waves can propagate inside. Our task is to find the frequencies that generate these prohibited waves. This requires the solution of an eigenvalue problem for the Helmholtz operator. To solve this problem we choose an alternate route which uses boundary integral equations. We derive a single integral equation on each of the interfaces between the outer region and the scatterers, considering a general transmission boundary condition, by using a hybrid method using layer potentials and Green’s formula. This approach reduces the number of unknowns considerably in comparison to other methods, but requires the treatment of large dense matrices and many matrix vector multiplications. To remedy this, we use the Fast Multipole Method. For solving the eigenvalue problem we discuss two methods: the Newton method and a method based on the Cauchy formula. Details of the numerical implementation, and results will be presented for different cases: sound hard, sound soft, impedance and transmission boundary conditions. [Work partially supported by NSF Award 0219681 is gratefully acknowledged.]

AParallel Line Detection Algorithm Based on HMMDecoding - Yefeng Zheng; Huiping Li; David Doermann (University of Maryland, College Park, 2003)
The detection of groups of parallel lines is important in applications such as form processing and text (handwriting) extraciton in rule lined paper. These tasks can be very challenging in degraded documents where the lines are severely broken. In this paper we propose a novel model-based method which incorporates high level context to detect these lines. After preprocessing and skew correction, we use trained Hidden Markov Models (HMM) to locate the optimal positions of all lines simultaneously, based on the Viterbi decoding. The algorithm is trainable, therefore, it can easily be adapted to different application scenarios. The experiments conducted on known form processing and rule line detection show our method is robust, and achieved better results than other widely used line detection methods, such as the Hough transform, projection or vectorization-based methods.

An appearance based approach for human and object tracking - Capellades,M. B; David Doermann; DeMenthon,D.; Chellapa, Rama (Image Processing, 2003. ICIP 2003. Proceedings. 2003 International Conference on, 2003)
A system for tracking humans and detecting human-object interactions in indoor environments is described. A combination of correlogram and histogram information is used to model object and human color distributions. Humans and objects are detected using a background subtraction algorithm. The models are built on the fly and used to track them on a frame by frame basis. The system is able to detect when people merge into groups and segment them during occlusion. Identities are preserved during the sequence, even if a person enters and leaves the scene. The system is also able to detect when a person deposits or removes an object from the scene. In the first case the models are used to track the object retroactively in time. In the second case the objects are tracked for the rest of the sequence. Experimental results using indoor video sequences are presented.
Keywords: algorithm; analysis; background; basis; by; Color; colour; correlogram; detection; distributions; frame; histogram; human; image; information; object; processing; segmentation; sequences; signal; subtraction; tracking; video

AUDIO-P2. 1: PITCH AND TIMBRE MANIPULATIONS USING CORTICAL REPRESENTATION OF SOUND - Zotkin,Dmitry N; Shamma,S.A.; Ru,P.; Duraiswami, Ramani; Davis, Larry S. (IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 2003)

Augmented intelligibility in simultaneous multi-talker environments - Mesgarani,N.; Shamma,S.; Grant,K.W.; Duraiswami, Ramani (Proc. International Conference on Auditory Display (ICAD’03), 2003)
Speech intelligibility can be severely compromised inenvironments where there are several competing speakers. It may be possible, however, to improve speech intelligibility in such environments by manipulating certain acoustic parameters known to facilitate the segregation of competing signals. The first step in designing such a feature-rich audio display is to understand the significant elements of human auditory perception that affect information transmission capacity. We review a series of experiments to examine the impact of different audio-display design parameters on overall intelligibility of simultaneous speech messages and show how using these features may improve intelligibility.

A boundary element method for electromagnetic scattering by multiple cylinders - Seydou,F.; Duraiswami, Ramani; Seppanen,T. (Antennas and Propagation Society International Symposium, 2003. IEEE, 2003)
An integral equation approach is derived for an electromagnetic scattering from M multiple cylinders. The problem is two-dimensional and the integral equation is solved using the Nystrom method. We give numerical examples that illustrate the algorithm.
Keywords: algorithm; boundary; boundary-elements; cylinders; electromagnetic; element; equations; Fredholm; integral; method; methods; multiple; Nystrom; scattering; two-dimensional; type; wave

Bringing Treasures to the Surface: Previews and Overviews in a Prototype for the Library of Congress National Digital Library - Marchionini,A.S.; Nation,D.; Karasik,S.; Cronnell,T.; Shneiderman, Ben; Spotfire,V.D.M.U.; Bederson, Benjamin B.; Data,T.S.; Hochheiser,H.; Shneiderman, Ben; others (The craft of information visualization: readings and reflections, 2003)

Cache-and-query for wide area sensor databases - Deshpande, Amol; Nath,Suman; Gibbons,Phillip B.; Seshan,Srinivasan (Proceedings of the 2003 ACM SIGMOD international conference on Management of data, 2003)
Webcams, microphones, pressure gauges and other sensors provide exciting new opportunities for querying and monitoring the physical world. In this paper we focus on querying wide area sensor databases, containing (XML) data derived from sensors spread over tens to thousands of miles. We present the first scalable system for executing XPATH queries on such databases. The system maintains the logical view of the data as a single XML document, while physically the data is fragmented across any number of host nodes. For scalability, sensor data is stored close to the sensors, but can be cached elsewhere as dictated by the queries. Our design enables self starting distributed queries that jump directly to the lowest common ancestor of the query result, dramatically reducing query response times. We present a novel query-evaluate gather technique (using XSLT) for detecting (1) which data in a local database fragment is part of the query result, and (2) how to gather the missing parts. We define partitioning and cache invariants that ensure that even partial matches on cached data are exploited and that correct answers are returned, despite our dynamic query-driven caching. Experimental results demonstrate that our techniques dramatically increase query throughputs and decrease query response times in wide area sensor databases.

Camera calibration using spheres: a semi-definite programming approach - Agrawal,M.; Davis, Larry S. (Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, 2003)
Vision algorithms utilizing camera networks with a common field of view are becoming increasingly feasible and important. Calibration of such camera networks is a challenging and cumbersome task. The current approaches for calibration using planes or a known 3D target may not be feasible as these objects may not be simultaneously visible in all the cameras. In this paper, we present a new algorithm to calibrate cameras using occluding contours of spheres. In general, an occluding contour of a sphere projects to an ellipse in the image. Our algorithm uses the projection of the occluding contours of three spheres and solves for the intrinsic parameters and the locations of the spheres. The problem is formulated in the dual space and the parameters are solved for optimally and efficiently using semidefinite programming. The technique is flexible, accurate and easy to use. In addition, since the contour of a sphere is simultaneously visible in all the cameras, our approach can greatly simplify calibration of multiple cameras with a common field of view. Experimental results from computer simulated data and real world data, both for a single camera and multiple cameras, are presented.
Keywords: 3D; algorithms; calibration; cameras; computer; approach; sphere; calibration; camera; contours; semidefinite; extraction; field; ellipse; intrinsic; location; spheres; vision; networks; common; parameters; occluding; Programming; target; camera; view; vision; feature

A categorial variation database for English - Habash,Nizar; Dorr, Bonnie J (Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1, 2003)
We describe our approach to the construction and evaluation of a large-scale database called "CatVar" which contains categorial variations of English lexemes. Due to the prevalence of cross-language categorial variation in multilingual applications, our categorial-variation resource may serve as an integral part of a diverse range of natural language applications. Thus, the research reported herein overlaps heavily with that of the machine-translation, lexicon-construction, and information-retrieval communities.We apply the information-retrieval metrics of precision and recall to evaluate the accuracy and coverage of our database with respect to a human-produced gold standard. This evaluation reveals that the categorial database achieves a high degree of precision and recall. Additionally, we demonstrate that the database improves on the linkability of Porter stemmer by over 30%.

CATVAR: A database of categorial variations for English - Habash,N.; Dorr, Bonnie J (Proceedings of the MT Summit, 2003)
We present a new large-scale database called “CatVar” (Habash and Dorr, 2003) which contains categorial variationsof English lexemes. Due to the prevalence of cross-language categorial variation in multilingual applications, our categorial-variation resource may serve as an integral part of a diverse range of natural language applications. Thus, the research reported herein overlaps heavily with that of the machine-translation, lexicon-construction, and information- retrieval communities. We demonstrate this database, embedded in a graphical interface; we also show a GUI for user input of corrections to the database.

The Challenge of Missing and Uncertain Data - Eaton,Cyntrica; Plaisant, Catherine; Drizd,Terence (Proceedings of the 14th IEEE Visualization 2003 (VIS'03), 2003)

Clustering and Summarizing Medline Abstracts - Dunlavy,Daniel M.; Conroy,John M.; O'Leary,Timothy J; O'Leary, Dianne P. (BISTI 2003 Symposium on Digital Biology: The Emerging ParadigmBISTI 2003 Symposium on Digital Biology: The Emerging Paradigm, 2003)

A collaborative digital library for children - Druin, Allison; Revelle,G.; Bederson, Benjamin B.; Hourcade,J. P; Farber,A.; Lee,J.; Campbell,D. (Journal of Computer Assisted Learning, 2003)

Complete camera calibration using spheres: Dual space approach - Agrawal,M.; Davis, Larry S. (IEEE, 2003)
Camera calibration is a fundamental problem in computer vision and photogrammetry. We present a new algorithmto calibrate cameras using spheres. In general, an occluding contour of a sphere projects to an ellipse in the image. Our algorithm uses the projection of the occluding contours of three spheres and solves for the intrinsic parameters and the locations of the spheres. The problem is formulated in the dual space and the parameters are solved for optimally and efficiently using semi-definite programming. The technique is flexible, accurate and easy to use. In addition, it can be used to simultaneously calibrate multiple cameras with a common field of view. Experimen- tal results from computer simulated data and real world data, both for a single camera and multiple cameras, are presented.

Content Features for Logical Document Labeling - Liang,Jian; David Doermann (Proc. SPIE Conference on Document Recognition and Retrieval X, 2003)
The use of content features extracted from recognized text is valuable in labeling logical elements in documents withoutrigid layout structure, like business letters. This paper discusses a model-based approach to combining content features with other geometrical and presentation features for logical labeling. Models are automatically initialized and adaptively improved using training samples. Satisfactory experimental results are presented.

Cross-language headline generation for Hindi - Dorr, Bonnie J; Zajic, David; Schwartz,Richard (ACM Transactions on Asian Language Information Processing (TALIP), 2003)
This paper presents new approaches to headline generation for English newspaper texts, with an eye toward the production of document surrogates for document selection in cross-language information retrieval. This task is difficult because the user must make decisions about relevance based on (often poor) translations of retrieved documents. To facilitate the decision-making process we need translations that can be assessed rapidly and accurately; our approach is to provide an English headline for the non-English document. We describe two approaches to headline generation and their application to the recent DARPA TIDES-2003 Surprise Language Exercise for Hindi. For comparison, we also implemented an alternative method for surrogate generation: a system that produces topic lists for (Hindi) articles. We present the results of a series of experiments comparing each of these approaches. We demonstrate in both automatic and human evaluations that our linguistically motivated approach outperforms two other surrogate-generation methods: a statistical system and a topic discovery system.

Data structures for 3D Multi-Tessellations: an overview - Danovaro,E.; De Floriani, Leila; Magillo,P.; Puppo,E. (Data Visualization: The State of the ArtData Visualization: The State of the Art, 2003)

Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in $d$ Dimensions - Gumerov, Nail A.; Duraiswami, Ramani; Borovikov,Eugene A. (Technical Reports from UMIACS UMIACS-TR-2003-28, 2003)
We present an overview of the Fast Multipole Method, explain the use ofoptimal data structures and present complexity results for the algorithm. We explain how octree structures and bit interleaving can be simply used to create efficient versions of the multipole algorithm in $d$ dimensions. We then present simulations that demonstrate various aspects of the algorithm, including optimal selection of the clustering parameter, the influence of the error bound on the complexity, and others. The use of these optimal parameters results in a many-fold speed-up of the FMM, and prove very useful in practice. UMIACS-TR-2003-28
Keywords: Technical Report

Decomposing non-manifold objects in arbitrary dimensions - De Floriani, Leila; Mesmoudi,Mostefa M.; Morando,Franco; Puppo,Enrico (Graphical Models, 2003)
We address the problem of building valid representations of non-manifold d-dimensional objects through an approach based on decomposing a non-manifold d-dimensional object into an assembly of more regular components. We first define a standard decomposition of d-dimensional non-manifold objects described by abstract simplicial complexes. This decomposition splits a non-manifold object into components that belong to a well-understood class of objects, that we call initial quasi-manifold. Initial quasi-manifolds cannot be decomposed without cutting them along manifold faces. They form a decidable superset of d-manifolds for d⩾3, and coincide with manifolds for d⩽2. We then present an algorithm that computes the standard decomposition of a general non-manifold complex. This decomposition is unique, and removes all singularities which can be removed without cutting the complex along its manifold faces.

Designing a digital library for young children: An intergenerational partnership - Druin, Allison; Bederson, Benjamin B.; Hourcade,J. P; Sherman,L.; Revelle,G.; Platner,M.; Weng,S. (The craft of information visualization: readings and reflections, 2003)

Desparately seeking cebuano - Oard, Douglas; David Doermann; Dorr, Bonnie J; He,D.; Resnik, Philip; Weinberg, Amy; Byrne,W.; Khudanpur,S.; Yarowsky,D.; Leuski,A.; others (Third Conference on Human Language Technologies, 2003)
This paper describes an effort to rapidly de-velop language resources and component tech- nology to support searching Cebuano news sto- ries using English queries. Results from the first 60 hours of the exercise are presented.

The dog genome: survey sequencing and comparative analysis - Kirkness,E. F; Bafna,V.; Halpern,A. L; Levy,S.; Remington,K.; Rusch,D. B; Delcher,A. L; Pop, Mihai; Wang,W.; Fraser,C. M; others (Science, 2003)

The Dog Genome: Survey Sequencing and Comparative Analysis - Kirkness,Ewen F.; Bafna,Vineet; Halpern,Aaron L.; Levy,Samuel; Remington,Karin; Rusch,Douglas B; Delcher,Arthur L.; Pop, Mihai; Wang,Wei; Fraser,Claire M.; Venter,J. Craig (ScienceScience, 2003)
A survey of the dog genome sequence (6.22 million sequence reads; 1.5× coverage) demonstrates the power of sample sequencing for comparative analysis of mammalian genomes and the generation of species-specific resources. More than 650 million base pairs (>25%) of dog sequence align uniquely to the human genome, including fragments of putative orthologs for 18,473 of 24,567 annotated human genes. Mutation rates, conserved synteny, repeat content, and phylogeny can be compared among human, mouse, and dog. A variety of polymorphic elements are identified that will be valuable for mapping the genetic basis of diseases and traits in the dog.

Domain Tuning of Bilingual Lexicons for MT - Ayan,Necip F; Dorr, Bonnie J; Kolak,Okan (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2003)
Our overall objective is to translate a domain-specific document in a foreign language (in this case, Chinese) to English. Using automatically induced domain-specific, comparable documents and language-independent clustering, we apply domain-tuning techniques to a bilingual lexicon for downstream translation of the input document to English. We will describe our domain-tuning technique and demonstrate its effectiveness by comparing our results to manually constructed domain-specific vocabulary. Our coverage/accuracy experiments indicate that domain-tuned lexicons achieve 88/% precision and 66/% recall. We also ran a Bleu experiment to compare our domain-tuned version to its un-tuned counterpart in an IR Ni-style NIT system. Our domain-tuned lexicons brought about an improvement in the Blen scores: 9.4/% higher than a system trained on a uniformly- weighted dictionary and 275/% higher than a system trained on no dictionary at all.
Keywords: *DICTIONARIES; *FOREIGN LANGUAGES; accuracy; BILINGUAL LEXICONS; DOCUMENTS; linguistics; Vocabulary

The effect of bilingual term list size on dictionary-based cross-language information retrieval - Demner-Fushman,D.; Oard, Douglas (Proceedings of the 36th Annual Hawaii International Conference on System Sciences, 2003, 2003)
Bilingual term lists are extensively used as a resource for dictionary-based cross-language information retrieval (CLIR), in which the goal is to find documents written in one natural language based on queries that are expressed in another. This paper identifies eight types of terms that affect retrieval effectiveness in CLIR applications through their coverage by general-purpose bilingual term lists, and reports results from an experimental evaluation of the coverage of 35 bilingual term lists in news retrieval application. Retrieval effectiveness was found to be strongly influenced by term list size for lists that contain between 3,000 and 30,000 unique terms per language. Supplemental techniques for named entity translation were found to be useful with even the largest lexicons. The contribution of named-entity translation was evaluated in a cross-language experiment involving English and Chinese. Smaller effects were observed from deficiencies in the coverage of domain-specific terminology when searching news stories.
Keywords: bilingual term list; Chinese language; Computer science; Control systems; Cross-language information retrieval; data mining; Dictionaries; dictionary-based information retrieval; Educational institutions; English language; Frequency; Information retrieval; language translation; named-entity translation; natural languages; Surface morphology; Terminology

Effect of treatment on the dynamics of circulating hypodermin C in cattle naturally infested with Hypoderma lineatum (Diptera: Oestridae) - Douglas D Colwell; Panadero-Fontan,Rosario; López-Sandez,Ceferino; Parra-Fernandez,Francisco; Paz-Silva,A; Sánchez-Andrade,Rita; Dı́ez-Baños,Pablo (Veterinary Parasitology, 2003)
An antigen capture ELISA, using a murine monoclonal antibody recognising recombinant hypodermin C (rHyC), was used to evaluate the influence of early treatment with eprinomectin (Eprinex®) or fenthion (Spotton®) on the kinetics of circulating hypodermin C in calves naturally infested with Hypoderma lineatum. No viable larvae were collected from treated animals, whereas a variable number of warbles were found in control animals. Treatment provoked a decrease in circulating HyC levels that was significant 9 days post-treatment (p.t.). Circulating antigen levels in the treated cattle remained detectable for approximately 99 days p.t. In contrast, control animals had no detectable antigen at 64 days p.t., 42 days earlier than in the treated animals. These results suggest that larvae were either gradually killed, resulting in slow release of antigen or they were encapsulated, leading to the slow liberation of antigen. Kinetics of circulating HyC did not differ among the two insecticide treatments. Antibodies persisted, in all groups, throughout the 120-day study. These results suggest that the antigen capture ELISA will be useful as a technique for detecting successful treatment of cattle grub infestations and for the detection of new infestations in previously infested cattle.
Keywords: Capture ELISA; Cattle-arthropoda; Control methods-arthropoda; Eprinomectin; Fenthion; Hypoderma spp.

Efficient kernel density estimation using the fast gauss transform with applications to color modeling and tracking - Elgammal,A.; Duraiswami, Ramani; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2003)
Many vision algorithms depend on the estimation of a probability density function from observations. Kernel density estimation techniques are quite general and powerful methods for this problem, but have a significant disadvantage in that they are computationally intensive. In this paper, we explore the use of kernel density estimation with the fast Gauss transform (FGT) for problems in vision. The FGT allows the summation of a mixture of ill Gaussians at N evaluation points in O(M+N) time, as opposed to O(MN) time for a naive evaluation and can be used to considerably speed up kernel density estimation. We present applications of the technique to problems from image segmentation and tracking and show that the algorithm allows application of advanced statistical techniques to solve practical vision problems in real-time with today's computers.
Keywords: algorithms; Color; Computer; density; estimation; fast; function; Gauss; image; Kernel; modeling; segmentation; tracking; transform; transforms; VISION; vision

Efficient kernel density estimation using the fast gauss transform with applications to color modeling and tracking - Elgammal,A.; Duraiswami, Ramani; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2003)

Efficient particle filter-based tracking of multiple interacting targets using an MRF-based motion model - Zia Khan; Balch, T.; Dellaert, F. (2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings, 2003)
We describe a multiple hypothesis particle filter for tracking targets that are influenced by the proximity and/or behavior of other targets. Our contribution is to show how a Markov random field motion prior, built on the fly at each time step, can model these interactions to enable more accurate tracking. We present results for a social insect tracking application, where we model the domain knowledge that two targets cannot occupy the same space, and targets actively avoid collisions. We show that using this model improves track quality and efficiency. Unfortunately, the joint particle tracker we propose suffers from exponential complexity in the number of tracked targets. An approximation to the joint filter, however, consisting of multiple nearly independent particle filters can provide similar track quality at substantially lower computational cost.
Keywords: collision avoidance; computational cost; Computational efficiency; Educational institutions; exponential complexity; Filtering; filtering theory; Insects; joint particle tracker; Markov processes; Markov random field motion; Markov random fields; multiple interacting targets; particle filter-based tracking; Particle filters; Particle tracking; Radar tracking; social insect tracking application; target tracking; Trajectory

Electromagnetic scattering from a multilayered cylindrical waveguide - Seydou,F.; Duraiswami, Ramani; Seppanen,T. (Antennas and Propagation Society International Symposium, 2003. IEEE, 2003)
This paper is devoted to electromagnetic scattering from an N multilayered circular cylinder. We consider waveguides in the z direction; that is, we look for the solution of Maxwell equations along the z direction. We assume a dielectric core and derive a mode matching approach for solving the problem. A numerical result is presented that illustrates the algorithm.
Keywords: circular; core; cylinder; cylindrical; dielectric; dielectric-loaded; electromagnetic; EM; equations; matching; Maxwell; mode; multilayered; scattering; theory; wave; waveguide; waveguide; waveguides

Evaluation Techniques Applied to Domain Tuning of MT Lexicons - Ayan,N.F.; Dorr, Bonnie J; Kolak,O. (Proceedings of the Workshop “Towards Systematizing MT Evaluation, 2003)
We describe a set of evaluation techniques applied to domain tuning of bilingual lexicons for machine translation.Our overall objective is to translate a domain-specific document in a foreign language (in this case, Chinese) to En- glish. First, we perform an intrinsic evaluation of the effectiveness of our domain-tuning techniques by comparing our domain-tuned lexicon to a manually constructed domain-specific bilingual termlist. Our results indicate that we achieve 66% recall and 95% precision with respect to a human-derived gold standard. Next, an extrinsic evaluation demonstrates that our domain-tuned lexicon improves the Bleu scores 50% over a statistical system—with a smaller improvement when the system is trained on a uniformly-weighted dictionary.

Exemplar-based tracking and recognition of arm gestures - Elgammal,A.; Shet,V.; Yacoob,Yaser; Davis, Larry S. (Image and Signal Processing and Analysis, 2003. ISPA 2003. Proceedings of the 3rd International Symposium on, 2003)
This paper presents a probabilistic exemplar-based framework for recognizing gestures. The approach is based on representing each gesture as a sequence of learned body poses. The gestures are recognized through a probabilistic framework for matching these body poses and for imposing temporal constrains between different poses. Matching individual poses to image data is performed using a probabilistic formulation for edge matching to obtain a likelihood measurement for each individual pose. The paper introduces a correspondence-free weighted matching scheme for edge templates that emphasize discriminating features in the matching. The weighting does not require establishing correspondences between the different pose models. The probabilistic framework also imposes temporal constrains between different pose through a learned hidden Markov model (HMM) of each gesture.
Keywords: arm; constrains; correspondence-free; edge; exemplar-based; framework; gesture; hidden; HMM; image; logic; Markov; MATCHING; matching; model; models; probabilistic; recognition; scheme; segmentation; temporal; tracking; weighted

Extracting significant features from the hrtf - Raykar,V.C.; Duraiswami, Ramani; Davis, Larry S.; Yegnanarayana,B. (Proceedings of the 2003 International Conference on Auditory Display, 2003)
The Head Related Transfer Function (HRTF) characterizes the au-ditory cues created by scattering of sound off a person’s anatomy. While it is known that features in the HRTF can be associated with various phenomena, such as head diffraction, head and torso re- flection, knee reflection and pinna resonances and anti resonances, identification of these phenomena are usually qualitative and/or heuristic. The objective of this paper is to attempt to decompose the HRTF and extract significant features that are perceptually im- portant for source localization. Some of the significant features that have been identified are the pinna resonances and the notches in the spectrum caused by various parts of the body. We develop signal processing algorithms to decompose the HRTF into compo- nents, and extract the features corresponding to each component. The support of NSF award ITR-0086075 is gratefully acknowl- edged

Extracting significant features from the HRTF - Raykar,V.C.; Duraiswami, Ramani; Davis, Larry S.; Yegnanarayana,B. (Proceedings of the 2003 International Conference on Auditory Display, 2003)
The Head Related Transfer Function (HRTF) characterizes the au-ditory cues created by scattering of sound off a person’s anatomy. While it is known that features in the HRTF can be associated with various phenomena, such as head diffraction, head and torso re- flection, knee reflection and pinna resonances and anti resonances, identification of these phenomena are usually qualitative and/or heuristic. The objective of this paper is to attempt to decompose the HRTF and extract significant features that are perceptually im- portant for source localization. Some of the significant features that have been identified are the pinna resonances and the notches in the spectrum caused by various parts of the body. We develop signal processing algorithms to decompose the HRTF into compo- nents, and extract the features corresponding to each component. The support of NSF award ITR-0086075 is gratefully acknowl- edged

Family Calendar Survey - Hutchinson,Hilary; Bederson, Benjamin B.; Plaisant, Catherine; Druin, Allison (Technical Reports from UMIACS, 2003)
Beginning in late July 2002, we conducted a survey about people's personal andfamily calendaring habits. By the end of September, we had over 400 responses, which are summarized below. The survey was conducted to help inform our work in designing new technologies for families, motivated in part by our work on the interLiving project. InterLiving is a 3 year, European Union-funded project where we work with distributed, multi-generational families as design partners to create new technologies (see http://www.cs.umd.edu/hcil/interliving for details). The survey was administered from a web page (https://www.cs.umd.edu/users/hilary/survey/survey.htm), and participants were solicited via a "chain-mail" email approach. We began by sending a request to fill out a survey to our friends, families, and colleagues. We asked that they forward the request on to their friends, family and colleagues as well. While we realize that this was an imperfect approach, we believed that the respondents would be representative of the users we are initially targeting in our research on family calendaring and coordination - individuals who are already making relatively heavy use of computers at home and/or work. The results seem to validate this assumption. Many of our respondents likely come from the HCI community as the mailing went to our large lab mailing list. We may have some pollution in the data as a result of people in the same household (e.g. husband and wife) both filling out the survey. Despite these issues, the results we got were helpful in eliciting a number of important findings, namely that people rely on multiple calendars, many of which are still paper. (UMIACS-TR-2002-92) (HCIL-TR-2002-21)
Keywords: Technical Report

Gabor Filter Based Multi-class Classifier for Scanned Document Images - Ma,H.; David Doermann (7th International Conference on Document Analysis and Recognition (ICDAR), 2003)
When scanning documents with a large number of pagessuch as books, it is often feasible to provide a minimal number of training samples to personalize the system to compensate for global shifts in how the document was created or in scanning parameters. In this paper, we present a supervised multi-class classifier based on Gabor filters that is used to classify the scripts, font-faces, and font-styles (bold, italic, normal etc.) in an application where the classes are known. Classification is performed at the word level (glyphs separated by white space) given training samples of each class. This method was applied to a variety of bilingual dictionaries to identify different scripts, and simultaneously, to classify Roman scripts into bold, italic and normal font-styles. Experimental results show the effectiveness of this approach in increasing performance over classifiers trained for general documents.

The genome sequence of Bacillus anthracis Ames and comparison to closely related bacteria - Read,Timothy D.; Peterson,Scott N.; Tourasse,Nicolas; Baillie,Les W.; Paulsen,Ian T.; Nelson,Karen E.; Tettelin,Herv|[eacute]|; Fouts,Derrick E.; Eisen,Jonathan A.; Gill,Steven R.; Holtzapple,Erik K.; |[Oslash]|kstad,Ole Andreas; et al. (Nature, 2003)
Bacillus anthracis is an endospore-forming bacterium that causes inhalational anthrax1. Key virulence genes are found on plasmids (extra-chromosomal, circular, double-stranded DNA molecules) pXO1 (ref. 2) and pXO2 (ref. 3). To identify additional genes that might contribute to virulence, we analysed the complete sequence of the chromosome of B. anthracis Ames (about 5.23 megabases). We found several chromosomally encoded proteins that may contribute to pathogenicity—including haemolysins, phospholipases and iron acquisition functions—and identified numerous surface proteins that might be important targets for vaccines and drugs. Almost all these putative chromosomal virulence and surface proteins have homologues in Bacillus cereus, highlighting the similarity of B. anthracis to near-neighbours that are not associated with anthrax4. By performing a comparative genome hybridization of 19 B. cereus and Bacillus thuringiensis strains against a B. anthracis DNA microarray, we confirmed the general similarity of chromosomal genes among this group of close relatives. However, we found that the gene sequences of pXO1 and pXO2 were more variable between strains, suggesting plasmid mobility in the group. The complete sequence of B. anthracis is a step towards a better understanding of anthrax pathogenesis.

Groundtruth Image Generation from Electronic Text (Demonstration) - David Doermann; Zi,G. (Symposium on Document Image Understanding Technology, 2003)

HCIL Technical Report Listing (1993-2002) - Ceaparu,I.; Druin, Allison; Guimbretiere,F.; Manipulation,D.; Shneiderman, Ben; Westerlurid,B.; Keogh,E.; Hochheiser,H.; Shrieidemian,B.; Shneidemiari,B.; others (The craft of information visualization: readings and reflections, 2003)

Hedge Trimmer: a parse-and-trim approach to headline generation - Dorr, Bonnie J; Zajic, David; Schwartz,Richard (Proceedings of the HLT-NAACL 03 on Text summarization workshop - Volume 5, 2003)
This paper presents Hedge Trimmer, a HEaDline GEneration system that creates a headline for a newspaper story using linguistically-motivated heuristics to guide the choice of a potential headline. We present feasibility tests used to establish the validity of an approach that constructs a headline by selecting words in order from a story. In addition, we describe experimental results that demonstrate the effectiveness of our linguistically-motivated approach over a HMM-based model, using both human evaluation and automatic metrics for comparing the two approaches.

Hierarchical dwarfs for the rollup cube - Sismanis,Yannis; Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Proceedings of the 6th ACM international workshop on Data warehousing and OLAP - DOLAP '03, 2003)

HRTF personalization using anthropometric measurements - Zotkin,Dmitry N; Hwang,J.; Duraiswami, Ramani; Davis, Larry S. (Applications of Signal Processing to Audio and Acoustics, 2003 IEEE Workshop on., 2003)
Individualized head related transfer functions (HRTFs) are needed for accurate rendering of spatial audio, which is important in many applications. Since these are relatively tedious to acquire, they may not be acceptable for some applications. A number of studies have sought to perform simple customization of the HRTF. We propose and test a strategy for HRTF personalization, based on matching certain anthropometric ear parameters with the HRTF database, and the incorporation of a low-frequency "head-and-torso" model. We present preliminary tests aimed at evaluation of this customization. Results show that the approach improves both the accuracy of the localization and subjective perception of the virtual auditory scene.
Keywords: acoustic; anthropometric; audio; audio; auditory; Ear; functions; Head; head-and-torso; HRTF; individualized; localization; measurements; model; models; parameters; perception; personalization; physiological; processing; related; scattering; scene; signal; sound; spatial; subjective; transfer; virtual; wave

Human body pose estimation using silhouette shape analysis - Mittal,A.; Liang Zhao; Davis, Larry S. (Proceedings. IEEE Conference on Advanced Video and Signal Based Surveillance, 2003., 2003)
We describe a system for human body pose estimation from multiple views that is fast and completely automatic. The algorithm works in the presence of multiple people by decoupling the problems of pose estimation of different people. The pose is estimated based on a likelihood function that integrates information from multiple views and thus obtains a globally optimal solution. Other characteristics that make our method more general than previous work include: (1) no manual initialization; (2) no specification of the dimensions of the 3D structure; (3) no reliance on some learned poses or patterns of activity; (4) insensitivity to edges and clutter in the background and within the foreground. The algorithm has applications in surveillance and promising results have been obtained.
Keywords: 3D; analysis; body; classification; clutter; detection; estimation; extraction; feature; function; human; image; likelihood; multiple; object; parameter; parameters; Pixel; pose; probability; segmentation; segmentations; SHAPE; silhouette; structure; surveillance; views

Hybrid Natural Language Generation from Lexical Conceptual Structures - Habash,Nizar; Dorr, Bonnie J; Traum,David (Machine Translation, 2003)
This paper describes Lexogen, a system for generating natural-languagesentences from Lexical Conceptual Structure, an interlingualrepresentation. The system has been developed as part of aChinese–English Machine Translation (MT) system; however, it isdesigned to be used for many other MT language pairs and naturallanguage applications. The contributions of this work include: (1)development of a large-scale Hybrid Natural Language Generation system withlanguage-independent components; (2) enhancements to an interlingualrepresentation and associated algorithm forgeneration from ambiguous input; (3) development of an efficientreusable language-independent linearization module with a grammardescription language that can be used with other systems; (4)improvements to an earlier algorithm forhierarchically mapping thematic roles to surface positions; and (5)development of a diagnostic tool for lexicon coverage and correctnessand use of the tool for verification of English, Spanish, and Chineselexicons. An evaluation of Chinese–English translation quality showscomparable performance with a commercial translation system. Thegeneration system can also be extended to other languages and this isdemonstrated and evaluated for Spanish.

Image-based pan-tilt camera control in a multi-camera surveillance environment - Lim,Ser-Nam; Elgammal,A.; Davis, Larry S. (Multimedia and Expo, 2003. ICME '03. Proceedings. 2003 International Conference on, 2003)
In automated surveillance systems with multiple cameras, the system must be able to position the cameras accurately. Each camera must be able to pan-tilt such that an object detected in the scene is in a vantage position in the camera's image plane and subsequently capture images of that object. Typically, camera calibration is required. We propose an approach that uses only image-based information. Each camera is assigned a pan-tilt zero-position. Position of an object detected in one camera is related to the other cameras by homographies between the zero-positions while different pan-tilt positions of the same camera are related in the form of projective rotations. We then derive that the trajectories in the image plane corresponding to these projective rotations are approximately circular for pan and linear for tilt. The camera control technique is subsequently tested in a working prototype.
Keywords: automated; camera; cameras; control; detection; environment; image; image-based; information; multicamera; object; pan-tilt; position; processing; sensors; Surveillance; surveillance; systems; vantage; zero-position; zero-positions

IMPACTing SHOP: Putting an AI Planner Into a Multi-Agent Environment - Dix,Jürgen; Muñoz-Avila,Héctor; Nau, Dana S.; Zhang,Lingling (Annals of Mathematics and Artificial Intelligence, 2003)
In this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. We define the A-SHOP algorithm, an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that A-SHOP is both sound and complete if certain conditions are met.
Keywords: Computer science

Improved fast gauss transform and efficient kernel density estimation - Yang,C.; Duraiswami, Ramani; Gumerov, Nail A.; Davis, Larry S. (Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, 2003)
Evaluating sums of multivariate Gaussians is a common computational task in computer vision and pattern recognition, including in the general and powerful kernel density estimation technique. The quadratic computational complexity of the summation is a significant barrier to the scalability of this algorithm to practical applications. The fast Gauss transform (FGT) has successfully accelerated the kernel density estimation to linear running time for low-dimensional problems. Unfortunately, the cost of a direct extension of the FGT to higher-dimensional problems grows exponentially with dimension, making it impractical for dimensions above 3. We develop an improved fast Gauss transform to efficiently estimate sums of Gaussians in higher dimensions, where a new multivariate expansion scheme and an adaptive space subdivision technique dramatically improve the performance. The improved FGT has been applied to the mean shift algorithm achieving linear computational complexity. Experimental results demonstrate the efficiency and effectiveness of our algorithm.
Keywords: adaptive; algorithm; multivariate; complexity; computer; complexity; Gaussian; computational; density; estimation; mean; expansion; Gauss; processes; computational; recognition; quadratic; scheme; pattern; shift; space; subdivision; technique; computer; theory; transform; kernel; vision; estimation; vision; fast

Improving the Arabidopsis genome annotation using maximal transcript alignment assemblies - Haas,Brian J.; Delcher,Arthur L.; Mount, Stephen M.; Wortman,Jennifer R.; Jr,Roger K. Smith; Hannick,Linda I.; Maiti,Rama; Ronning,Catherine M.; Rusch,Douglas B; Town,Christopher D.; Salzberg,Steven L.; White,Owen (Nucleic Acids ResearchNucl. Acids Res., 2003)
The spliced alignment of expressed sequence data to genomic sequence has proven a key tool in the comprehensive annotation of genes in eukaryotic genomes. A novel algorithm was developed to assemble clusters of overlapping transcript alignments (ESTs and full‐length cDNAs) into maximal alignment assemblies, thereby comprehensively incorporating all available transcript data and capturing subtle splicing variations. Complete and partial gene structures identified by this method were used to improve The Institute for Genomic Research Arabidopsis genome annotation (TIGR release v.4.0). The alignment assemblies permitted the automated modeling of several novel genes and >1000 alternative splicing variations as well as updates (including UTR annotations) to nearly half of the ∼27 000 annotated protein coding genes. The algorithm of the Program to Assemble Spliced Alignments (PASA) tool is described, as well as the results of automated updates to Arabidopsis gene annotations.

Integral equation solution of electromagnetic scattering from a multilayered cylindrical waveguide - Seydou,F.; Duraiswami, Ramani; Seppanen,T. (Antennas and Propagation Society International Symposium, 2003. IEEE, 2003)
This paper is devoted to the electromagnetic scattering from an N multilayered cylinder. We consider waveguides in the z direction, that is: we look for the solution of Maxwell equations along the z direction. We assume a dielectric core and discuss the problem for the case of general domains. We use an integral equation approach to solve the problem and the Nystrom method for the numerical approximation.
Keywords: approximation; circular; core; cylinder; cylindrical; dielectric; dielectric-loaded; electromagnetic; EM; equations; integral; Maxwell; method; multilayered; numerical; Nystrom; scattering; theory; wave; waveguide; waveguides

Interactive Visualization of Large Tetrahedral Meshes through Selective Refinement - Cignoni,P.; De Floriani, Leila; Magillo,P.; Puppo,E.; Scopigno,R.; di Genova,U. (IEEE Transactions on Visualization and Computer Graphics, 2003)
In this paper, we address the problem of the efficient visualization of very largeirregular volume datasets. To this aim, we exploit a multiresolution representation based on a domain decomposition into tetrahedral cells. A new compact data struc- ture is described which encodes the whole dataset at a virtually continuous range of different resolutions, with a storage cost six times lower than a standard data struc- ture for tetrahedral meshes. Such structure supports on-line selective refinement to focus resolution on areas that the user considers more critical, based on either field values, or domain location, or opacity of the transfer function. Selective refinement is used to trade-off between resolution and speed in visualization, according to user needs and hardware constraints. These features have been implemented in a new system, called TAn2 (Tetrahedra Analyzer), for the interactive visualization of three- dimensional scalar fields defined on very large tetrahedral meshes. Multiresolution representation and selective refinement make the system fully scalable with respect to the size of the dataset and to hardware requirements.

The International Children's Digital Library - Druin, Allison; Bederson, Benjamin B.; Weeks,A.; Farber,A.; Grosjean,J.; Guha,M.L.; Hourcade,J. P; Lee,J.; Liao,S.; Reuter,K.; others (First Monday, 2003)

The International Children's Digital Library: Description and analysis of first use - Druin, Allison; Bederson, Benjamin B.; Weeks,A.; Farber,A.; Grosjean,J.; Guha,M.L.; Hourcade,J. P; Lee,J.; Liao,S.; Reuter,K.; others (First Monday, 2003)

The International Children's Digital Library: viewing digital books online - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison; Rose,A.; Farber,A.; Takayama,Y. (Interacting with Computers, 2003)

Intrusion-resilient public-key encryption - Dodis,Y.; Franklin,M.; Katz, Jonathan; Miyaji,A.; Yung,M. (Topics in Cryptology—CT-RSA 2003, 2003)
Exposure of secret keys seems to be inevitable, and may in practice represent the most likely point of failure in a cryptographic system. Recently, the notion of intrusion-resilience [17] (which extends both the notions of forward security [3], [5] and key insulation [11]) was proposed as a means of mitigating the harmful effects that key exposure can have. In this model, time is divided into distinct periods; the public key remains fixed throughout the lifetime of the protocol but the secret key is periodically updated. Secret information is stored by both a user and a base; the user performs all cryptographic operations during a given time period, while the base helps the user periodically update his key. Intrusion-resilient schemes remain secure in the face of multiple compromises of both the user and the base, as long as they are not both compromised simultaneously. Furthermore, in case the user and base are compromised simultaneously, prior time periods remain secure (as in forward-secure schemes). Intrusion-resilient signature schemes have been previously constructed [17], [15]. Here, we give the first construction of an intrusion-resilient publickey encryption scheme, based on the recently-constructed forwardsecure encryption scheme of [8]. We also consider generic transformations for securing intrusion-resilient encryption schemes against chosenciphertext attacks.

IRIS: Internet-scale Resource-Intensive Sensor Services - Deshpande, Amol; Nath,S.; Gibbons,P.B.; Seshan,S. (Intel Research, UC Berkeley, Carnegie Mellon University, 2003)
The proliferation and affordability of smart sensors such aswebcams, microphones etc., has created opportunities for exciting new classes of distributed services. A key stum- bling block to mining these rich information sources is the lack of a common, scalable networked infrastructure for col- lecting, filtering, and combining the video feeds, extracting the useful information, and enabling distributed queries. In this demo, we demonstrate the design and an early prototype of such an infrastructure, called IRIS (Internet- scale Resource-Intensive Sensor services). IRIS is a poten- tially global network of smart sensor nodes, with webcams or other sensors, and organizing nodes that provide the means to query recent and historical sensor-based data. IRIS ex- ploits the fact that high-volume sensor feeds are typically attached to devices with significant computing power and storage, and running a standard operating system. Aggres- sive filtering, smart query routing, and semantic caching are used to dramatically reduce network bandwidth utilization and improve query response times, as we will demonstrate. The service that we demonstrate here is that of a park- ing space finder. This service utilizes webcams that monitor parking spaces to answer queries such as the availability of parking spaces near a user’s destination.

IrisNet: an architecture for internet-scale sensing services - Nath,Suman; Deshpande, Amol; Ke,Yan; Gibbons,Phillip B.; Karp,Brad; Seshan,Srinivasan (Proceedings of the 29th international conference on Very large data bases - Volume 29, 2003)
We demonstrate the design and an early prototype of IrisNet (Internet-scale Resource-Intensive Sensor Network services), a common, scalable networked infrastructure for deploying wide area sensing services. IrisNet is a potentially global network of smart sensing nodes, with webcams or other monitoring devices, and organizing nodes that provide the means to query recent and historical sensor-based data. IrisNet exploits the fact that high-volume sensor feeds are typically attached to devices with significant computing power and storage, and running a standard operating system. It uses aggressive filtering, smart query routing, and semantic caching to dramatically reduce network bandwidth utilization and improve query response times, as we demonstrate. Our demo will present two services built on Iris-Net, from two very different application domains. The first one, a parking space finder, utilizes webcams that monitor parking spaces to answer queries such as the availability of parking spaces near a user's destination. The second one, a distributed infrastructure monitor, uses measurement tools installed in individual nodes of a large distributed infrastructure to answer queries such as average network bandwidth usage of a set of nodes.

Learning dynamics for exemplar-based gesture recognition - Elgammal,A.; Shet,V.; Yacoob,Yaser; Davis, Larry S. (Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, 2003)
This paper addresses the problem of capturing the dynamics for exemplar-based recognition systems. Traditional HMM provides a probabilistic tool to capture system dynamics and in exemplar paradigm, HMM states are typically coupled with the exemplars. Alternatively, we propose a non-parametric HMM approach that uses a discrete HMM with arbitrary states (decoupled from exemplars) to capture the dynamics over a large exemplar space where a nonparametric estimation approach is used to model the exemplar distribution. This reduces the need for lengthy and non-optimal training of the HMM observation model. We used the proposed approach for view-based recognition of gestures. The approach is based on representing each gesture as a sequence of learned body poses (exemplars). The gestures are recognized through a probabilistic framework for matching these body poses and for imposing temporal constraints between different poses using the proposed non-parametric HMM.
Keywords: arbitrary; body; by; Computer; constraint; detection; discrete; distribution; dynamics; edge; estimation; example; exemplar; exemplar-based; extraction; feature; framework; gesture; gesture; hidden; HMM; human; image; learning; Markov; matching; model; models; motion; nonparametric; pose; probabilistic; recognition; sequence; space; state; statistics; system; temporal; tool; view-based; vision

M 2 Tracker: a multi-view approach to segmenting and tracking people in a cluttered scene - Mittal,A.; Davis, Larry S. (International Journal of Computer Vision, 2003)
When occlusion is minimal, a single camera is generally sufficient to detect and track objects. However, when the density of objects is high, the resulting occlusion and lack of visibility suggests the use of multiple cameras and collaboration between them so that an object is detected using information available from all the cameras in the scene.In this paper, we present a system that is capable of segmenting, detecting and tracking multiple people in a cluttered scene using multiple synchronized surveillance cameras located far from each other. The system is fully automatic, and takes decisions about object detection and tracking using evidence collected from many pairs of cameras. Innovations that help us tackle the problem include a region-based stereo algorithm capable of finding 3D points inside an object knowing only the projections of the object (as a whole) in two views, a segmentation algorithm using bayesian classification and the use of occlusion analysis to combine evidence from different camera pairs. The system has been tested using different densities of people in the scene. This helps us determine the number of cameras required for a particular density of people. Experiments have also been conducted to verify and quantify the efficacy of the occlusion analysis scheme.

Machine Printed Text and Handwriting Identification in Noisy Document Images - Yefeng Zheng; Huiping Li; David Doermann (University of Maryland, College Park, 2003)
In this paper we address the problem of the identification of text in noisy document images. We are especially focused on segmenting and identifying between handwriting and machine printed text because: 1) handwriting in a document often indicates corrections, additions, or other supplemental information that should be treated differently from the main content, and 2) the segmentation and recognition techniques requested for machine printed and handwritten text are significantly different. A novel aspect of our approach is that we treat noise as a separate class and model noise based on selected features. Trained Fisher classifiers are used to identify machine printed text and handwriting from noise, and we further exploit context to refine the classification. AMarkov Random Field (MRF) based approach is used to model the geometrical structure of the printed text, handwriting, and noise to rectify misclassifications. Experimental results show that our approach is robust and can significantly improve page segmentation in noisy document collections.

Making miracles: Interactive translingual search for cebuano and hindi - He,D.; Oard, Douglas; Wang,J.; Luo,J.; Demner-Fushman,D.; Darwish,K.; Resnik, Philip; Khudanpur,S.; Nossal,M.; Subotin,M.; others (ACM Transactions on Asian Language Information Processing (TALIP), 2003)

Mean-shift analysis using quasiNewton methods - Yang,C.; Duraiswami, Ramani; DeMenthon,D.; Davis, Larry S. (Image Processing, 2003. ICIP 2003. Proceedings. 2003 International Conference on, 2003)
Mean-shift analysis is a general nonparametric clustering technique based on density estimation for the analysis of complex feature spaces. The algorithm consists of a simple iterative procedure that shifts each of the feature points to the nearest stationary point along the gradient directions of the estimated density function. It has been successfully applied to many applications such as segmentation and tracking. However, despite its promising performance, there are applications for which the algorithm converges too slowly to be practical. We propose and implement an improved version of the mean-shift algorithm using quasiNewton methods to achieve higher convergence rates. Another benefit of our algorithm is its ability to achieve clustering even for very complex and irregular feature-space topography. Experimental results demonstrate the efficiency and effectiveness of our algorithm.
Keywords: analysis; classification; clustering; clustering; Convergence; density; estimation; feature-space; image; irregular; iterative; Mean-shift; method; methods; Newton; nonparametric; pattern; procedure; quasiNewton; rates; segmentation; technique; topography

Measuring Structural Similarity of Document Pages for Searching Document Image Databases - Shin,C.; David Doermann; Rosenfeld, A. (5th IASTEDInternational Conference on Signal and Image Processing, 2003)
Current document management and database systems provide text search and retrieval capabilities, but generally lack the ability to utilize the documents’ logical and physical structures. This paper describes a general system for document image retrieval that is able to make use of document structure. It discusses the use of structural similarity for retrieval; it defines a measure of structural similarity between document images based on content area overlap, and also compares similarity ratings based on this measure with human relevance judgments.

MobiCom poster: mining a world of smart sensors - Nath,Suman; Deshpande, Amol; Gibbons,Phillip B.; Seshan,Srinivasan (SIGMOBILE Mob. Comput. Commun. Rev., 2003)

Modelling pedestrian shapes for outlier detection: a neural net based approach - Nanda,H.; Benabdelkedar,C.; Davis, Larry S. (Intelligent Vehicles Symposium, 2003. Proceedings. IEEE, 2003)
In this paper we present an example-based approach to learn a given class of complex shapes, and recognize instances of that shape with outliers. The system consists of a two-layer custom-designed neural network. We apply this approach to the recognition of pedestrians carrying objects from a single camera. The system is able to capture and model an ample range of pedestrian shapes at varying poses and camera orientations, and achieves a 90% correct recognition rate.
Keywords: (artificial; complex; Computer; computing; custom; design; detection; engineering; intelligence); layer; learning; method; modelling; net; nets; neural; object; outlier; pedestrian; pedestrians; rate; recognition; recognition; SHAPE; shapes; traffic; two; vision

Morphology-driven simplification and multiresolution modeling of terrains - Danovaro,Emanuele; De Floriani, Leila; Magillo,Paola; Mesmoudi,Mohammed Mostefa; Puppo,Enrico (Proceedings of the 11th ACM international symposium on Advances in geographic information systems, 2003)
We propose a technique for simplification and multiresolution modeling of a terrain represented as a TIN. Our goal is to maintain the morphological structure of the terrain in the resulting multiresolution model. To this aim, we extend Morse theory, developed for continuous and differentiable functions, to the case of piecewise linear functions. We decompose a TIN into areas with uniform morphological properties (such as valleys, basins, etc.) separated by a network of critical lines and points. We describe an algorithm to compute the above decomposition and the critical net, and a TIN simplification algorithm that preserves them. On this basis, we build a multiresolution terrain model, which provides a representation of critical features at any level of detail.
Keywords: morphological structure; Multi-resolution; terrain models

On-chip stochastic communication [SoC applications] - Tudor Dumitras; Marculescu, R. (Design, Automation and Test in Europe Conference and Exhibition, 2003, 2003)
As CMOS technology scales down into the deep-submicron (DSM) domain, the costs of design and verification for systems-on-chip (SoCs) are rapidly increasing due to the inefficiency of traditional CAD tools. Relaxing the requirement of 100% correctness for devices and interconnects drastically reduces the costs of design but, at the same time, requires that SoCs be designed with some system-level fault-tolerance. In this paper, we introduce a new communication paradigm for SoCs, namely stochastic communication. The newly proposed scheme not only separates communication from computation, but also provides the required built-in fault-tolerance to DSM failures, is scalable and cheap to implement. For a generic tile-based architecture, we show how a ubiquitous multimedia application (an MP3 encoder) can be implemented using stochastic communication in an efficient and robust manner. More precisely, up to 70% data upsets, 80% packet drops because of buffer overflow, and severe levels of synchronization failures can be tolerated while maintaining a low latency.
Keywords: buffer overflow; CMOS technology; CMOS technology scaling; Costs; data upsets; Design automation; Digital audio players; Fault tolerance; Fault tolerant systems; generic tile-based architecture; integrated circuit design; integrated circuit interconnections; interconnect correctness requirements; Logic Design; logic simulation; MP3 encoder; Multiprocessor interconnection networks; on-chip fault-tolerance; on-chip stochastic communication; packet drops; Pervasive computing; Robustness; SoC design; SoC verification; Stochastic processes; Synchronisation; synchronization failures; system latency; system-level fault-tolerance; system-on-chip; systems-on-chip; video coding

Overlaying graph links on treemaps - Fekete,J. D; Wang,D.; Dang,N.; Aris,A.; Plaisant, Catherine (IEEE Symposium on Information Visualization Conference Compendium (demonstration), 2003)
Every graph can be decomposed into a tree structure plus a set ofremaining edges. We describe a visualization technique that displays the tree structure as a Treemap and the remaining edges as curved links overlaid on the Treemap. Link curves are designed to show where the link starts and where it ends without requiring an explicit arrow that would clutter the already dense visualization. This technique is effective for visualizing structures where the underlying tree has some meaning, such as Web sites or XML documents with cross-references. Graphic attributes of the links – such as color or thickness – can be used to represent attributes of the edges. Users can choose to see all links at once or only the links to and from the node or branch under the cursor.

Parsing and Tagging of Bilingual Dictionaries - Ma,Huanfeng; Karagol-Ayan,Burcu; David Doermann; Oard, Douglas; Wang,Jianqiang (TALTraitement Automatique Des Langues, 2003)
Bilingual dictionaries hold great potential as a source of lexical resources for training and testing automated systems for optical character recognition, machine translation, and cross-language information retrieval. In this paper, we describe a system for extracting term lexicons from printed bilingual dictionaries. Our work was divided into three phases - dictionary segmentation, entry tagging, and generation. In segmentation, pages are divided into logical entries based on structural features learned from selected examples. The extracted entries are associated with functional labels and passed to a tagging module which associates linguistic labels with each word or phrase in the entry. The output of the system is a structure that represents the entries from the dictionary. We have used this approach to parse a variety of dictionaries with both Latin and non-Latin alphabets, and demonstrate the results of term lexicon generation for retrieval from a collection of French news stories using English queries.

Performance of a Three-Stage System for Multi-Document Summarization - Dunlavy,Daniel M.; Conroy,John M.; Schlesinger,Judith D.; Goodman,Sarah A.; Okurowski,Mary Ellen; O'Leary, Dianne P.; Halteren,Hans van (DUC 03 Conference ProceedingsDUC 03 Conference Proceedings, 2003)

Persistence of adhesive properties in Vibrio cholerae after long‐term exposure to sea water - Pruzzo,Carla; Tarsi,Renato; Del Mar Lleò,Maria; Signoretto,Caterina; Zampini,Massimiliano; Pane,Luigi; Rita R Colwell; Canepari,Pietro (Environmental Microbiology, 2003)
The effect of exposure to artificial sea water (ASW) on the ability of classical Vibrio cholerae O1 cells to interact with chitin-containing substrates and human intestinal cells was studied. Incubation of vibrios in ASW at 5°C and 18°C resulted in two kinds of cell responses: the viable but non-culturable (VBNC) state (i.e. <0.1 colony forming unit ml−1) at 5°C, and starvation (i.e. maintenance of culturability of the population) at 18°C. The latter remained rod shaped and, after 40 days’ incubation, presented a 47–58% reduction in the number of cells attached to chitin, a 48–53% reduction in the number of bacteria adhering to copepods, and a 48–54% reduction in the number of bacteria adhering to human cultured intestinal cells, compared to control cells not suspended in ASW. Bacteria suspended in ASW at 5°C became coccoid and, after 40 days, showed 34–42% fewer cells attached to chitin, 52–55% fewer adhering to copep-ods, and 45–48% fewer cells adhering to intestinal cell monolayers, compared to controls. Sarkosyl-insoluble membrane proteins that bind chitin particles were isolated and analysed by SDS-PAGE. After 40 days incubation in ASW at both 5°C and 18°C vibrios expressed chitin-binding ligands similar to bacteria harvested in the stationary growth phase. It is concluded that as vibrios do not lose adhesive properties after long-term exposure to ASW, it is important to include methods for VBNC bacteria when testing environmental and clinical samples for purposes of public health safety.

A perturbation method for evaluating background subtraction algorithms - Chalidabhongse,T.H.; Kim,K.; Harwood,D.; Davis, Larry S. (Joint IEEE International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance (VS-PETS), 2003)
We introduce a performance evaluation methodology calledPerturbation Detection Rate (PDR) analysis, for measuring performance of background subtraction (BGS) algorithms. It has some advantages over the commonly used Receiver Operation Characteristics (ROC) analysis. Specifically, it does not require foreground targets or knowledge of fore- ground distributions. It measures the sensitivity of a BGS algorithm in detecting low contrast targets against back- ground as a function of contrast, also depending on how well the model captures mixed (moving) background events. We compare four algorithms having similarities and differ- ences. Three are in [2, 3, 5] while the fourth is recently de- veloped, called Codebook BGS. The latter algorithm quan- tizes sample background values at each pixel into code- books which represent a compressed form of background model for a long image sequence.

Pitch and timbre manipulations using cortical representation of sound - Zotkin,Dmitry N; Shamma,S.A.; Ru,P.; Duraiswami, Ramani; Davis, Larry S. (Multimedia and Expo, IEEE International Conference on, 2003)
The sound receiver at the ears is processed by humans using signal processing that separate the signal along intensity, pitch and timbre dimensions. Conventional Fourier-based signal processing, while endowed with fast algorithms, is unable to easily represent signal along these attributes. In this paper we use a cortical representation to represent the manipulate sound. We briefly overview algorithms for obtaining, manipulating and inverting cortical representation of sound and describe algorithms for manipulating signal pitch and timbre separately. The algorithms are first used to create sound of an instrument between a guitar and a trumpet. Applications to creating maximally separable sounds in auditory user interfaces are discussed.

A planner for composing services described in DAML-S - Sheshagiri,M.; desJardins, Marie; Finin,T. (International Conference on Automated Planning and Scheduling (ICAPS) 2003 Workshop on planning for web services, 2003)

Planning in Answer Set Programming Using Ordered Task Decomposition - Dix,Jürgen; Kuter,Ugur; Nau, Dana S. (KI 2003: Advances in Artificial Intelligence, 2003)
In this paper we introduce a formalism for solving Hierarchical Task Network ( HTN ) Planning using Answer Set Programming ( ASP ). We consider the formulation of HTN planning as described in the SHOP planning system and define a systematic translation method from SHOP ’s representation of the planning problem into logic programs with negation. We show that our translation is sound and complete : answer sets of the logic program obtained by our translation correspond exactly to the solutions of the planning problem. We compare our method to (1) similar approaches based on non- HTN planning and (2) SHOP , a dedicated planning system. We show that our approach outperforms non- HTN methods and that its performance is better with ASP systems that allow for nonground programs than with ASP systems that require ground programs.
Keywords: Computer science

Probabilistic structured query methods - Darwish,Kareem; Oard, Douglas (Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, 2003)
Structured methods for query term replacement rely on separate estimates of term tes of replacement probabilities. Statistically significantfrequency and document frequency to compute a weight for each query term. This paper reviews prior work on structured query techniques and introduces three new variants that leverage estima improvements in retrieval effectiveness are demonstrated for cross-language retrieval and for retrieval based on optical character recognition when replacement probabilities are used to estimate both term frequency and document frequency.
Keywords: arabic; CLIR; OCR; structured queries; term replacement

Probabilistic tracking in joint feature-spatial spaces - Elgammal,A.; Duraiswami, Ramani; Davis, Larry S. (Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, 2003)
In this paper, we present a probabilistic framework for tracking regions based on their appearance. We exploit the feature-spatial distribution of a region representing an object as a probabilistic constraint to track that region over time. The tracking is achieved by maximizing a similarity-based objective function over transformation space given a nonparametric representation of the joint feature-spatial distribution. Such a representation imposes a probabilistic constraint on the region feature distribution coupled with the region structure, which yields an appearance tracker that is robust to small local deformations and partial occlusion. We present the approach for the general form of joint feature-spatial distributions and apply it to tracking with different types of image features including row intensity, color and image gradient.
Keywords: analysis; appearance; appearance; color; colour; Computer; constraint; deformation; detection; distribution; edge; estimation; extraction; feature; feature-spatial; feature; function; gradient; image; intensity; joint; likelihood; local; maximization; maximum; nonparametric; object; objective; occlusion; optical; partial; probabilistic; probability; region; representation; row; similarity-based; small; space; structure; target; tracker; tracking; transformation; vision

A query language to support scientific discovery - Eckman,B.; Deutsch,K.; Janer,M.; Lacroix,Z.; Raschid, Louiqa (Proc. 2nd IEEE International Computer Society, 2003)

Rapid porting of DUSTer to Hindi - Dorr, Bonnie J; Ayan,Necip Fazil; Habash,Nizar; Madnani,Nitin; Hwa,Rebecca (ACM Transactions on Asian Language Information Processing (TALIP), 2003)
The frequent occurrence of divergences—structural differences between languages---presents a great challenge for statistical word-level alignment and machine translation. This paper describes the adaptation of DUSTer, a divergence unraveling package, to Hindi during the DARPA TIDES-2003 Surprise Language Exercise. We show that it is possible to port DUSTer to Hindi in under 3 days.
Keywords: Divergences; Machine translation

A representation for abstract simplicial complexes: an analysis and a comparison - De Floriani, Leila; Morando,F.; Puppo,E. (Discrete Geometry for Computer Imagery, 2003)
Abstract simplicial complexes are used in many application contexts to represent multi-dimensional, possibly non-manifold and non-uniformly dimensional, geometric objects. In this paper we introduce a new general yet compact data structure for representing simplicial complexes, which is based on a decomposition approach that we have presented in our previous work [3]. We compare our data structure with the existing ones and we discuss in which respect it performs better than others.

Representation of non-manifold objects - De Floriani, Leila; Morando,Franco; Puppo,Enrico (Proceedings of the eighth ACM symposium on Solid modeling and applications, 2003)
In our previous work [2], we have shown that a non-manifold, mixed-dimensional object described by simplicial complexes can be decomposed in a unique way into regular components, all belonging to a well-understood class. Based on such decomposition, we define here a two-level topological data structure for representing non-manifold objects in any dimension: the first level represents components; while the second level represents the connectivity relation among them. The resulting data structure is compact and scalable, allowing for the efficient treatment of singularities without burdening well-behaved parts of a complex with excessive space overheads.
Keywords: Data structures; Non-manifold modeling; simplicial complexes

A scalable data structure for three-dimensional non-manifold objects - De Floriani, Leila; Hui,Annie (Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 2003)
In this paper, we address the problem of representing and manipulating non-manifold, mixed-dimensional objects described by three-dimensional simplicial complexes embedded in the 3D Euclidean space. We describe the design and the implementation of a new data structure, that we call the non-manifold indexed data structure with adjacencies (NMIA), which can represent any three-dimensional Euclidean simplicial complex compactly, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. The NMIA structure supports efficient traversal algorithms which retrieve topological relations in optimal time, and it scales very well to the manifold case. Here, we sketch traversal algorithms, and we compare the NMIA structure with data structures for manifold and regular 3D simplicial complexes.

Scalable image-based multi-camera visual surveillance system - Lim,Ser-Nam; Davis, Larry S.; Elgammal,A. (Proceedings. IEEE Conference on Advanced Video and Signal Based Surveillance, 2003., 2003)
We describe the design of a scalable and wide coverage visual surveillance system. Scalability (the ability to add and remove cameras easily during system operation with minimal overhead and system degradation) is achieved by utilizing only image-based information for camera control. We show that when a pan-tilt-zoom camera pans and tilts, a given image point moves in a circular and a linear trajectory, respectively. We create a scene model using a plan view of the scene. The scene model makes it easy for us to handle occlusion prediction and schedule video acquisition tasks subject to visibility constraints. We describe a maximum weight matching algorithm to assign cameras to tasks that meet the visibility constraints. The system is illustrated both through simulations and real video from a 6-camera configuration.
Keywords: ACQUISITION; algorithm; camera; constraints; feature; hidden; image-based; MATCHING; maximum; multi-camera; occlusion; pan-tilt-zoom; PLAN; prediction; processing; removal; scalable; scheduling; signal; Surveillance; surveillance; system; task; video; view; visibility; visual; weight

A search engine for 3D models - Funkhouser,Thomas; Min,Patrick; Kazhdan,Michael; Chen,Joyce; Halderman,Alex; Dobkin,David; Jacobs, David W. (ACM Trans. Graph., 2003)
As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).
Keywords: Search engine; shape matching; shape representation; shape retrieval

A Simple and Optimal Energy Surface Reconstruction Algorithm from Volumetric Data - Liu,Kexue; Duraiswami, Ramani; Davis, Larry S. (Technical Reports from UMIACS, 2003)
We describe a new method for building 3D surface meshes from volumetricimages, as are created in Magnetic Resonance Imaging (MRI). The method works by first extracting the contours from the MRI data, and then using modified polygon boolean operations to find difference polygons. The last step is performed by applying a Constrained Delauny Triangulation (CDT) algorithm to build a surface mesh. Since it is based on CDT, the mesh quality is usually very good. Moreover, the resulting triangular surface mesh is the optimal one for surface interpolation. In case of undersampled images, the mesh quality can be improved dramatically by inserting new Steiner points in to the mesh. Thus the mesh can be made suitable for use in scientific computation. Our method has the advantages of combining the generation and optimization of the mesh in one step compared with other methods. These advantages are illustrated. Also UMIACS-TR-2003-11
Keywords: Technical Report

A simplified Newton method for the inverse orthotropic problem - Seydou,F.; Seppanen,T.; Duraiswami, Ramani (Antennas and Propagation Society International Symposium, 2003. IEEE, 2003)
We consider one of the most challenging inverse problems in electromagnetic scattering for inhomogeneous medium. We try to reconstruct the elements of a matrix from scattering data in an orthotropic medium. To solve the inverse problem, we implement a simplified Newton method and present some numerical results.
Keywords: algebra; electromagnetic; inhomogeneous; inverse; matrix; matrix; media; medium; method; Newton; orthotropic; problem; problems; scattering; wave

Simultaneous pose and correspondence determination using line features - David,P.; DeMenthon,D.; Duraiswami, Ramani; Samet, Hanan (Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, 2003)
We present a new robust line matching algorithm for solving the model-to-image registration problem. Given a model consisting of 3D lines and a cluttered perspective image of this model, the algorithm simultaneously estimates the pose of the model and the correspondences of model lines to image lines. The algorithm combines softassign for determining correspondences and POSIT for determining pose. Integrating these algorithms into a deterministic annealing procedure allows the correspondence and pose to evolve from initially uncertain values to a joint local optimum. This research extends to line features the SoftPOSIT algorithm proposed recently for point features. Lines detected in images are typically more stable than points and are less likely to be produced by clutter and noise, especially in man-made environments. Experiments on synthetic and real imagery with high levels of clutter, occlusion, and noise demonstrate the robustness of the algorithm.
Keywords: algorithm; algorithms; annealing; clutter; cluttered; Computer; correspondence; detection; determination; deterministic; environment; extraction; feature; feature; image; image; imagery; images; joint; line; local; man-made; MATCHING; matching; measurement; model-to-image; noise; occlusion; optimum; perspective; point; pose; position; problem; processing; real; realistic; registration; simulated; softassign; SoftPOSIT; stereo; synthetic; vision

Special Issue on Visual Analysis of Human Movement - Davis, Larry S.; Horaud,R. (The International Journal of Robotics Research, 2003)

Sports Video Classification Using HMM - Gilbert,X.; Li,H.; David Doermann (ICME, 2003)

Starting an intergenerational technology design team: a case study - Knudtzon,Kendra; Druin, Allison; Kaplan,Nancy; Summers,Kathryn; Chisik,Yoram; Kulkarni,Rahul; Moulthrop,Stuart; Weeks,Holly; Bederson, Benjamin B. (Proceedings of the 2003 conference on Interaction design and children, 2003)
This paper presents a case study of the first three months of a new intergenerational design team with children ages 10--13. It discusses the research and design methods used for working with children of this age group, the challenges and opportunities of starting a new team, and the lessons learned.
Keywords: children; cooperative inquiry; design methods; educational applications; intergenerational design teams; participatory design

Tagging and Parsing of Bilingual Dictionary - Ma,Huanfeng; Karagol-Ayan,Burcu; David Doermann; Oard, Douglas; Wang,Jianqiang (University of Maryland, College Park, 2003)
Bilingual dictionaries hold great potential as a source of lexical resources for training and testing automated systems for optical character recognition, machine translation, and cross-language information retrieval. In this paper, we describe a system for extracting term lexicons from printed bilingual dictionaries. Our work was divided into three phases - dictionary segmentation, entry tagging, and generation. In segmentation, pages are divided into logical entries based on structural features learned from selected examples. The extracted entries are associated with functional labels and passed to a tagging module which associates linguistic labels with each word or phrase in the entry. The output of the system is a structure that represents the entries from the dictionary. We have used this approach to parse a variety of dictionaries with both Latin and non-Latin alphabets, and demonstrate the results of term lexicon generation for retrieval from a collection of French news stories using English queries.

Team formation in complex networks - Gaston,M.; desJardins, Marie (Proceedings of the 1st NAACSOS Conference, 2003)
The concept of team formation, or joint action, is central to a wide variety of disciplines includingorganizational design, computational organization theory, planning and learning in multi-agent systems, and distributed artificial intelligence. One key feature of team formation is the under- lying social network topology which determines the direct interactions among the individuals of the organization. Traditional models of social phenomena have been restricted to regular lattice, or fully-connected, network topologies, but recent results have shown that real-world networks have much different and much richer structure. Using a simple agent-based computational model of team formation, various virtual experiments are conducted to examine the impact of complex network structures on the dynamics of team formation.

Technology probes: inspiring design for and with families - Hutchinson,Hilary; Mackay,Wendy; Westerlund,Bo; Bederson, Benjamin B.; Druin, Allison; Plaisant, Catherine; Beaudouin-Lafon,Michel; Conversy,Stéphane; Evans,Helen; Hansen,Heiko; Roussel,Nicolas; Eiderbäck,Björn (Proceedings of the SIGCHI conference on Human factors in computing systems, 2003)
We describe a new method for use in the process of co-designing technologies with users called technology probes. Technology probes are simple, flexible, adaptable technologies with three interdisciplinary goals: the social science goal of understanding the needs and desires of users in a real-world setting, the engineering goal of field-testing the technology, and the design goal of inspiring users and researchers to think about new technologies. We present the results of designing and deploying two technology probes, the messageProbe and the videoProbe, with diverse families in France, Sweden, and the U.S. We conclude with our plans for creating new technologies for and with families based on our experiences.
Keywords: computer mediated communication; ethnography; Home; participatory design and cooperative design

TelegraphCQ: An architectural status report - Krishnamurthy, S.; Chandrasekaran,S.; Cooper,O.; Deshpande, Amol; Franklin,M.J.; Hellerstein,J. M; Hong,W.; Madden,S.; Reiss,F.; Shah,M. A (IEEE Data Engineering Bulletin, 2003)

TelegraphCQ: continuous dataflow processing - Chandrasekaran,Sirish; Cooper,Owen; Deshpande, Amol; Franklin,Michael J.; Hellerstein,Joseph M.; Wei Hong; Krishnamurthy,Sailesh; Madden,Samuel R.; Reiss,Fred; Shah,Mehul A. (Proceedings of the 2003 ACM SIGMOD international conference on Management of data, 2003)

Text Identification in Noisy Document Images Using Markov Random Field - Zheng,Y.; Li,H.; David Doermann (ICDAR, 2003)

Three dimensional acoustic scattering from an M multilayered domain via an integral equation approach - Seydou,F.; Duraiswami, Ramani; Seppanen,T. (Antennas and Propagation Society International Symposium, 2003. IEEE, 2003)
An integral equation approach is derived for three dimensional acoustic scattering from an M multilayered domain. The integral equation is solved using the collocation method. To validate the method, we compare the exact and approximate results. The numerous matrix vector multiplications of our method may be thought a disadvantage. This problem can be overcome by using fast multiple methods where these operations are done very quickly.
Keywords: acoustic; collocation; dimensional; domain; equation; equations; fast; inhomogeneous; integral; matrix; media; method; methods; multilayered; multilayers; multiple; multiplication; multiplications; scattering; three; vector; wave

Thwarting Web Censorship with Untrusted Messenger Discovery - Feamster, Nick; Balazinska,Magdalena; Wang,Winston; Balakrishnan,Hari; Karger,David (Privacy Enhancing TechnologiesPrivacy Enhancing Technologies, 2003)
All existing anti-censorship systems for the Web rely on proxies to grant clients access to censored information. Therefore, they face the proxy discovery problem : how can clients discover the proxies without having the censor discover and block these proxies? To avoid widespread discovery and blocking, proxies must not be widely published and should be discovered in-band. In this paper, we present a proxy discovery mechanism called keyspace hopping that meets this goal. Similar in spirit to frequency hopping in wireless networks, keyspace hopping ensures that each client discovers only a small fraction of the total number of proxies. However, requiring clients to independently discover proxies from a large set makes it practically impossible to verify the trustworthiness of every proxy and creates the possibility of having untrusted proxies. To address this, we propose separating the proxy into two distinct components—the messenger , which the client discovers using keyspace hopping and which simply acts as a gateway to the Internet; and the portal , whose identity is widely-published and whose responsibility it is to interpret and serve the client’s requests for censored content. We show how this separation, as well as in-band proxy discovery, can be applied to a variety of anti-censorship systems.
Keywords: Computer science

Topological analysis and characterization of discrete scalar fields - Danovaro,E.; De Floriani, Leila; Mesmoudi,M. (Geometry, Morphology, and Computational Imaging, 2003)
In this paper, we address the problem of analyzing the topology of discrete scalar fields defined on triangulated domains. To this aim, we introduce the notions of discrete gradient vector field and of Smalelike decomposition for the domain of a d-dimensional scalar field. We use such notions to extract the most relevant features representing the topology of the field. We describe a decomposition algorithm, which is independent of the dimension of the scalar field, and, based on it, methods for extracting the critical net of a scalar field. A complete classification of the critical points of a 2-dimensional field that corresponds to a piecewise differentiable field is also presented.

Towards On-chip Fault-tolerant Communication - Tudor Dumitras; Kerner, Sam; M\uarculescu, Radu (ASP-DAC '03 Proceedings of the 2003 Asia and South Pacific Design Automation Conference, 2003)
As CMOS technology scales down into the deep-submicron (DSM) domain, devices and interconnects are subject to new types of malfunctions and failures that are harder to predict and avoid with the current system-on-chip (SoC) design methodologies. Relaxing the requirement of 100% correctness in operation drastically reduces the costs of design but, at the same time, requires SoCs be designed with some degree of system-level fault-tolerance. In this paper, we introduce a high-level model of DSM failure patterns and propose a new communication paradigm for SoCs, namely stochastic communication. Specifically, for a generic tile-based architecture, we propose a randomized algorithm which not only separates computation from communication, but also provides the required fault-tolerance to on-chip failures. This new technique is easy and cheap to implement in SoCs that integrate a large number of communicating IP cores.

Tracking a moving speaker using excitation source information - Raykar,V.C.; Duraiswami, Ramani; Yegnanarayana,B.; Prasanna,S. R.M (Eighth European Conference on Speech Communication and Technology, 2003)
Microphone arrays are widely used to detect, locate, and track a stationary or moving speaker. The first step is to estimate the time delay, between the speech signals received by a pair of microphones. Conventional methods like generalized cross-correlation are based on the spectral content of the vocal tract system in the speech signal. The spectral content of the speech signal is affected due to degradations in the speech signal caused by noise and reverberation. However, features corresponding to the excitation source of speech are less affected by such degradations. This paper proposes a novel method to estimate the time delays using the excitation source information in speech. The estimated delays are used to get the position of the moving speaker. The proposed method is compared with the spectrum-based approach using real data from a microphone array setup.

Two methods for solving a 3D acoustic inverse scattering problem - Seydou,Fadoulourahmane; Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2003)
We consider the problem of finding the refractive index of a buried object by using far‐field measurements in an inhomogeneous medium. We describe two methods for solving the inverse problem. Both methods are implemented in two steps in order to better deal with the ill‐posedness of the problem. In the first method an integral equation of the first kind is derived for the far‐field operator which is solved via least‐squares and Tikhonov regularization. We then use the solution of the integral equation to derive an over‐posed boundary value problem, i.e., the Helmholtz equation in a bounded domain with Cauchy data on the boundary. The index that satisfies this over‐posed problem most closely is obtained via the Levenberg–Marquardt algorithm. The second method is an iterative method and is based on the Lippmann–Schwinger equation. It is implemented via the Newton method. The first step consists, as for the other method. Here we use a Fourier integral approach and regularization via discretization. The second step is to obtain the index by iterating the Lippmann–Schwinger equation starting with the Born approximation.

Use of OCR for Rapid Construction of Bilingual Lexicons - Karagol-Ayan,Burcu; David Doermann; Dorr, Bonnie J (University of Maryland, College Park, 2003)
This paper describes an approach to analyzing the lexical structure of OCRed bilingual dictionaries to construct resources suited for machine translation of low-density languages, where online resources are limited. A rule-based and an HMM-based method are used for rapid construction of MT lexicons based on systematic structural clues provided in the original dictionary. We evaluate the effectiveness of our techniques, concluding that: (1) the rule-based method performs better on dictionaries with a simple structure; (2) the stochastic method performs better on dictionaries with an enriched structure; (3) regardless of the degree of dictionary richness, the rule-based method gives better results for phrasal entries than for single-word entries; and (4) Our resulting bilingual lexicons are comprehensive enough to provide reasonable MT results when compared to human-constructed lexicons.

Using computer vision to generate customized spatial audio - Mohan,A.; Duraiswami, Ramani; Zotkin,Dmitry N; DeMenthon,D.; Davis, Larry S. (Multimedia and Expo, IEEE International Conference on, 2003)
Creating high quality virtual spatial audio over headphones requires real-time head tracking, personalized head-related transfer functions (HRTFs) and customized room response models. While there are expensive solutions to address these issues based on costly head trackers, measured personalized HRTFs and room responses, these are not suitable for widespread or easy deployment and use. We report on the development of a system that uses computer vision to produce customizable models for both the HRTF and the room response, and to achieve head-tracking. The system uses relatively inexpensive cameras and widely available personal computers. Computer-vision based anthropometric measurements of the head, torso, and the external ears are used for HRTF customization. For low-frequency HRTF customization we employ a simple head-and-torso model developed recently [V. R. Algazi et al., 2002]. For high frequency customization we employ measured pinna characteristics as an index into a database of HRTFs [D. N. Zotkin et al., 2002]. For head tracking we employ an online implementation of the POSIT algorithm [D. DeMenthon and L. Davis, 1995] along with active markers to compute head pose in real-time. The system provides an enhanced virtual listening experience at low cost.

Using state modules for adaptive query processing - Vijayshankar Raman; Deshpande, Amol; Hellerstein,J. M (19th International Conference on Data Engineering, 2003. Proceedings, 2003)
We present a query architecture in which join operators are decomposed into their constituent data structures (State Modules, or SteMs), and dataflow among these SteMs is managed adaptively by an eddy routing operator [R. Avnur et al., (2000)]. Breaking the encapsulation of joins serves two purposes. First, it allows the eddy to observe multiple physical operations embedded in a join algorithm, allowing for better calibration and control of these operations. Second, the SteM on a relation serves as a shared materialization point, enabling multiple competing access methods to share results, which can be leveraged by multiple competing join algorithms. Our architecture extends prior work significantly, allowing continuously adaptive decisions for most major aspects of traditional query optimization: choice of access methods and join algorithms, ordering of operators, and choice of a query spanning tree. SteMs introduce significant routing flexibility to the eddy, enabling more opportunities for adaptation, but also introducing the possibility of incorrect query results. We present constraints on eddy routing through SteMs that ensure correctness while preserving a great deal of flexibility. We also demonstrate the benefits of our architecture via experiments in the Telegraph dataflow system. We show that even a simple routing policy allows significant flexibility in adaptation, including novel effects like automatic "hybridization " of multiple algorithms for a single join.
Keywords: adaptive query processing; Bandwidth; Calibration; data encapsulation; data structure; Data structures; Databases; Dictionaries; eddy routing; eddy routing operator; Encapsulation; join operator; multiple algorithm automatic hybridization; multiple competing join algorithm; query architecture; Query processing; query spanning tree; Routing; routing policy; Runtime; shared materialization point; State Module; SteMs; Telegraph dataflow system; Telegraphy; Tree data structures

Video Analysis for Pervasive Environments - David Doermann; Karunanidhi,A. (ICME, 2003)

Video Mining - Rosenfeld,Azriel; David Doermann; DeMenthon,Daniel (Springer, 2003)
Video Mining is an essential reference for the practitioners and academicians in the fields of multimedia search engines.Half a terabyte or 9,000 hours of motion pictures are produced around the world every year. Furthermore, 3,000 television stations broadcasting for twenty-four hours a day produce eight million hours per year, amounting to 24,000 terabytes of data. Although some of the data is labeled at the time of production, an enormous portion remains unindexed. For practical access to such huge amounts of data, there is a great need to develop efficient tools for browsing and retrieving content of interest, so that producers and end users can quickly locate specific video sequences in this ocean of audio-visual data.Video Mining is important because it describes the main techniques being developed by the major players in industry and academic research to address this problem. It is the first time research from these leaders in the field developing the next-generation multimedia search engines is being described in great detail and gathered into a single volume.Video Mining will give valuable insights to all researchers and non-specialists who want to understand the principles applied by the multimedia search engines that are about to be deployed on the Internet, in studios' multimedia asset management systems, and in video-on-demand systems.
Keywords: Computers / Client-Server Computing; Computers / Computer Science; Computers / Database Management / Data Mining; Computers / Database Management / General; Computers / Information Technology; Computers / Information Theory; Computers / Intelligence (AI) & Semantics; Computers / Interactive & Multimedia; Computers / Networking / General; Computers / Security / Cryptography; data mining; Data mining/ Congresses; Mathematics / General; Medical / General; multimedia systems; Multimedia systems/ Congresses; Technology & Engineering / Electrical; Technology & Engineering / Telecommunications

Video Retrieval using Spatio-Temporal Descriptors - DeMenthon,Daniel; David Doermann (ACMMultimedia '03, 2003)
This paper describes a novel methodology for implementing video search functions such as retrieval of near-duplicate videos and recognition of actions in surveillance video. Videos are divided into half-second clips whose stacked frames produce 3D space-time volumes of pixels. Pixel regions with consistent color and motion properties are extracted from these 3D volumes by a threshold-free hierarchical space-time segmentation technique. Each region is then described by a high-dimensional point whose components represent the position, motion and, when possible, color of the region. In the indexing phase for a video database, these points are assigned labels that specify their video clip of origin. All the labeled points for all the clips are stored into a single binary tree for ecient k-nearest neighbor retrieval. The retrieval phase uses video segments as queries. Half-second clips of these queries are again segmented to produce sets of points, and for each point the labels of its nearest neighbors are retrieved. The labels that receive the largest numbers of votes correspond to the database clips that are the most similar to the query video segment. We illustrate this approach for video indexing and retrieval and for action recognition. First, we describe retrieval experiments for dynamic logos, and for video queries that di er from the indexed broadcasts by the addition of large overlays. Then we describe experiments in which oce actions (such as pulling and closing drawers, taking and storing items, picking up and putting down a phone) are recognized. Color information is ignored to insure independence to people's appearance. One of the distinct advantages of using this approach for action recognition is that there is no need for detection or recognition of body parts.

The World's Information in Digital Libraries - Plaisant, Catherine; Marchimini,G.; Bruns,T.; Komlodi,A.; Campbell,L.; Rose,A.; Ding,G.M.; Beale Jr,J.; Nolet,V.; Shneiderman, Ben; others (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

AAAI 2002 Workshops - Blake,Brian; Haigh,Karen; Hexmoor,Henry; Falcone,Rino; Soh,Leen-Kiat; Baral,Chitta; McIlraith,Sheila; Gmytrasiewicz,Piotr; Parsons,Simon; Malaka,Rainer; Krueger,Antonio; Bouquet,Paolo; et al. (AI Magazine, 2002)

Agents dealing with time and uncertainty - Dix,Jürgen; Kraus,Sarit; V.S. Subrahmanian (Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, 2002)
Situated agents in the real world need to handle the fact that events occur frequently, as well as the fact that the agent typically has uncertain knowledge about what is true in the world. The ability to reason about both time and uncertainty is therefore very important. In this paper, we develop a formal theory of agents that can reason about both time and uncertainty. The theory extends the notion of agents described in [10, 21] and proposes the notion of temporal probabilistic (or TP) agents. A formal semantics for TP-agents is proposed - this semantics is described via structures called feasible TP-status interpretations (FTPSI's). TP-agents continuously evaluate changes (in the state of the environment they are situated in) and compute appropriate FTPSI's. For a class of TP-agents called positive TP-agents, we develop a provably sound and complete procedure to compute FTPSI's.
Keywords: formalisms and logics; logic programming; probabilistic/uncertain reasoning; temporal reasoning; theories of agency

Analysis of stage-specific gene expression in the bloodstream and the procyclic form of Trypanosoma brucei using a genomic DNA-microarray - Diehl,Susanne; Diehl,Frank; El‐Sayed, Najib M.; Clayton,Christine; Hoheisel,Jörg D. (Molecular and Biochemical Parasitology, 2002)
A microarray comprising 21[punctuation space]024 different PCR products spotted on glass slides was constructed for gene expression studies on Trypanosoma brucei. The arrayed fragments were generated from a T. brucei shotgun clone library, which had been prepared from randomly sheared and size-fractionated genomic DNA. For the identification of stage-specific gene activity, total RNA from in vitro cultures of the human, long slender form and the insect, procyclic form of the parasite was labelled and hybridised to the microarray. Approximately 75% of the genomic fragments produced a signal and about 2% exhibited significant differences between the transcript levels in the bloodstream and procyclic forms. A few results were confirmed by Northern blot analysis or reverse-transcription and PCR. Three hundred differentially regulated clones have been selected for sequencing. So far, of 33 clones that showed about 2-fold or more over-expression in bloodstream forms, 15 contained sequences similar to those of VSG expression sites and at least six others appeared non-protein-coding. Of 29 procyclic-specific clones, at least eight appeared not to be protein-coding. A surprisingly large proportion of known regulated genes was already identified in this small sample, and some new ones were found, illustrating the utility of genomic arrays.
Keywords: Expression; Gene; Microarray; Regulation; Trypanosoma brucei

Approximating the head-related transfer function using simple geometric models of the head and torso - Algazi,V. R; Duda,R. O; Duraiswami, Ramani; Gumerov, Nail A.; Tang,Z. (The Journal of the Acoustical Society of America, 2002)

Argument structure saturation in a constraint based model - Drury,J.; Resnik, Philip; Weinberg, Amy; Gennari,S.; Aoshima,S. (2002)

Automatic headline generation for newspaper stories - Zajic, David; Dorr, Bonnie J; Schwartz,R. (Proceedings of the ACL-2002 Workshop on Text Summarization, 2002)
In this paper we propose a novelapplication of Hidden Markov Models to automatic generation of informative headlines for English texts. We propose four decoding parameters to make the headlines appear more like Headlinese, the language of informative newspaper headlines. We also allow for morphological variation in words between headline and story English. Informal and formal evaluations indicate that our approach produces informative headlines, mimicking a Headlinese style generated by humans.

Automatic transcription of Czech language oral history in the MALACH project: resources and initial experiments - Oard, Douglas; Demner-Fushman,D.; Hajic,J.; Ramabhadran,B.; Gustman,S.; Byrne,WJ; Soergel,D.; Dorr, Bonnie J; Resnik, Philip; Picheny,M. (Proceedings of the The 5th International Conference on Text, Speech and Dialogue, 2002)

Beam Search for Feature Selection in Automatic SVMDefect Classification - Gupta,P.; David Doermann; DeMenthon,D. (International Conference on Pattern Recognition, 2002)
Often in pattern classification problems, one tries to extract a large number of features and base the classifier decision on as much information as possible. This yields an array of features that are 'potentially' useful. Most of the time however, large feature sets are sub-optimal in describing the samples since they tend to over-represent the data and model noise along with the useful information in the data. Selecting relevant features from the available set of features is, therefore, a challenging task. In this paper, we present an innovative feature selection algorithm called Smart Beam Search (SBS), which is used with a Support Vector Machine based classifier for automatic defect classification. This feature selection approach not only reduces the dimensionality of the feature space substantially, but also improves the classifier performance.

Binarization of low quality text using a Markov random field model - Wolf,C.; David Doermann (Pattern Recognition, 2002. Proceedings. 16th International Conference on, 2002)
Binarization techniques have been developed in the document analysis community for over 30 years and many algorithms have been used successfully. On the other hand, document analysis tasks are more and more frequently being applied to multimedia documents such as video sequences. Due to low resolution and lossy compression, the binarization of text included in the frames is a non-trivial task. Existing techniques work without a model of the spatial relationships in the image, which makes them less powerful. We introduce a new technique based on a Markov random field model of the document. The model parameters (clique potentials) are learned from training data and the binary image is estimated in a Bayesian framework. The performance is evaluated using commercial OCR software.
Keywords: analysis; annealing; Bayes; Bayesian; binarization; computing; distributions; document; documents; field; Gibbs; image; low; Markov; method; methods; multimedia; optimization; probability; processes; processing; QUALITY; random; simulated; text

Case study: a message board as a technology probe for family communication and coordination - Hutchinson,H.; Plaisant, Catherine; Druin, Allison (Proceedings of the 2002 Conference on Human Factors in Computing Systems, 2002)
In this paper, we describe the design of an electronic family message board and the initial results of its deployment in three households. The message board was used as a “technology probe” to help understand the communication and coordination needs of a distributed, multigenerational family. Using this information, we are working with the family as design partners to design new technologies.

The child as learner, critic, inventor, and technology design partner: An analysis of three years of Swedish student journals - Druin, Allison; Fast,C. (International Journal of Technology and Design Education, 2002)

Combinatorial Algorithms for Design of DNA Arrays - Hannenhalli, Sridhar; Hubbell,Earl; Lipshutz,Robert; Pevzner,Pavel (Chip TechnologyChip Technology, 2002)
Optimal design of DNA arrays requires the development of algorithms with two-fold goals: reducing the effects caused by unintended illumination ( border length minimization problem ) and reducing the complexity of masks ( mask decomposition problem ). We describe algorithms that reduce the number of rectangles in mask decomposition by 20–30% as compared to a standard array design under the assumption that the arrangement of oligonucleotides on the array is fixed. This algorithm produces provably optimal solution for all studied real instances of array design. We also address the difficult problem of finding an arrangement which minimizes the border length and come up with a new idea of threading that significantly reduces the border length as compared to standard designs.

Complete genome sequence and comparative analysis of the metabolically versatile Pseudomonas putida KT2440 - Nelson,K. E; Weinel,C.; Paulsen,IT; Dodson,RJ; Hilbert,H.; Martins dos Santos,VAP; Fouts,DE; Gill,S. R; Pop, Mihai; Holmes,M.; others (Environmental microbiology, 2002)
Pseudomonas putida is a metabolically versatile saprophytic soil bacterium that has been certified as a biosafety host for the cloning of foreign genes. The bacterium also has considerable potential for biotechnological applications. Sequence analysis of the 6.18 Mb genome of strain KT2440 reveals diverse transport and metabolic systems. Although there is a high level of genome conservation with the pathogenic Pseudomonad Pseudomonas aeruginosa (85% of the predicted coding regions are shared), key virulence factors including exotoxin A and type III secretion systems are absent. Analysis of the genome gives insight into the non-pathogenic nature of P. putida and points to potential new applications in agriculture, biocatalysis, bioremediation and bioplastic production.

Compression methods for triangle meshes Preliminary version - Danovaro,E.; De Floriani, Leila; Magillo,P. (Department of Computer Science and Information Science, University of Genoa, 2002)

Computation of scattering from N spheres using multipole reexpansion - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2002)

Constraints on the Generation of Tense, Aspect, and Connecting Words from Temporal Expressions - Dorr, Bonnie J; Gaasterland,T. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
Generating language that reflects the temporal organization of represented knowledgerequires a language generation model that integrates contemporary theories of tense and aspect, temporal representations, and methods to plan text. This paper presents a model that produces event combinations and appropriate connecting words to relate them. We distinguish between inherent and non-inherent aspectual features of verbs and describe an algorithm that uses these features to select tense, aspect, and temporal connecting words for generating text based on time-stamped information. The main result of this work is the successful incorporation of constrained linguistic theories of tense and as- pect in a self-contained module called CONGEN that produces a ranked list of temporal connectives and tense/aspect possibilities from pairs of time-stamped literals. We show that the theoretical results described herein have been verified in a large-scale corpus analysis. The framework serves as the basis of a component designed to enhance the English output of a constrained generation system.

Construction of a Chinese-English Verb Lexicon for Embedded Machine Translation in Cross-Language Information Retrieval - Dorr, Bonnie J; Lin,Dekang; Levow,Gina-Anne (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
This paper addresses the problem of automatic acquisition of lexical knowledge for rapid construction of MT engines for use in multilingual applications. We describe new techniques for large-scale construction of a Chinese-English verb lexicon and we evaluate the coverage and effectiveness of the resulting lexicon for a structured MT approach that is embedded in a cross-language information retrieval system. Leveraging off an existing Chinese conceptual database called HowNet and a large, semantically rich English verb database, we use thematic-role information to create links between Chinese concepts and English classes. We apply the metrics of recall and precision to evaluate the coverage and effectiveness of the linguistic resources. The results of this work indicate that: (1) we are able to obtain reliable Chinese-English entries both with and without pre-existing semantic links between the two languages; (2) if we have pre-existing semantic links, we are able to produce a more robust lexical resource by merging these with our semantically rich English database; (3) In our comparisons with manual lexicon creation, our automatic techniques were shown to achieve 62% precision, compared to a much lower precision of 10% for arbitrary assignment of semantic links.
Keywords: *ACQUISITION; *AUTOMATIC; *CROSS-LANGUAGE INFORMATION RETRIEVAL; *INFORMATION RETRIEVAL; *LEXICAL ACQUISITION; *MACHINE TRANSLATION; *VOCABULARY; Chinese language; CHINESE-ENGLISH LEXICONS; DATA BASES; EMBEDDED MT(MACHINE TRANSLATION) RESOURCES; EMBEDDING; English language; INFORMATION SCIENCE; linguistics; semantics; THEMATIC ROLES

Construction of a Chinese–English Verb Lexicon for Machine Translation and Embedded Multilingual Applications - Dorr, Bonnie J; Levow,Gina-Anne; Lin,Dekang (Machine Translation, 2002)
This paper addresses the problem of automatic acquisition of lexical knowledge for rapid construction of engines for machine translation and embedded multilingual applications. We describe new techniques for large-scale construction of a Chinese–English verb lexicon and we evaluate the coverage and effectiveness of the resulting lexicon. Leveraging off an existing Chinese conceptual database called How Net and a large, semantically rich English verb database, we use thematic-role information to create links between Chinese concepts and English classes. We apply the metrics of recall and precision to evaluate the coverage and effectiveness of the linguistic resources. The results of this work indicate that: (a) we are able to obtain reliable Chinese–English entries both with and without pre-existing semantic links between the two languages; (b) if we have pre-existing semantic links, we are able to produce a more robust lexical resource by merging these with our semantically rich English database; (c) in our comparisons with manual lexicon creation, our automatic techniques were shown to achieve 62% precision, compared to a much lower precision of 10% for arbitrary assignment of semantic links.

Creation of virtual auditory spaces - Zotkin,Dmitry N; Duraiswami, Ramani; Davis, Larry S. (2002 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2002)
High-quality virtual audio scene rendering is a must for emerging virtual/augmented reality applications and for perceptual user interfaces. We describe algorithms for creation of virtual auditory spaces using measured and non-individualized HRTFs and head tracking. Details of algorithms for HRTF interpolation, room impulse response creation, and audio scene presentation are presented. Tests show that individuals externalize well, and find our interface natural. The system runs in real time with latency of less than 30 ms on an office PC without specialized DSP.
Keywords: accuracy; Estimation; Finite impulse response filter; Heating; Program processors; Rendering (computer graphics); System-on-a-chip

Customizable auditory displays - Zotkin,Dmitry N; Duraiswami, Ramani; Davis, Larry S. (Proceedings of the International Conference on Auditory Display, 2002)

Decoupled query optimization for federated database systems - Deshpande, Amol; Hellerstein,J. M (18th International Conference on Data Engineering, 2002. Proceedings, 2002)
We study the problem of query optimization in federated relational database systems. The nature of federated databases explicitly decouples many aspects of the optimization process, often making it imperative for the optimizer to consult underlying data sources while doing cost-based optimization. This not only increases the cost of optimization, but also changes the trade-offs involved in the optimization process significantly. The dominant cost in the decoupled optimization process is the "cost of costing" that traditionally has been considered insignificant. The optimizer can only afford a few rounds of messages to the underlying data sources and hence the optimization techniques in this environment must be geared toward gathering all the required cost information with minimal communication. In this paper, we explore the design space for a query optimizer in this environment and demonstrate the need for decoupling various aspects of the optimization process. We present minimum-communication decoupled variants of various query optimization techniques, and discuss tradeoffs in their performance in this scenario. We have implemented these techniques in the Cohera federated database system and our experimental results, somewhat surprisingly, indicate that a simple two-phase optimization scheme performs fairly well as long as the physical database design is known to the optimizer, though more aggressive algorithms are required otherwise
Keywords: Algorithm design and analysis; Cohera federated database; Computer science; Corporate acquisitions; Cost function; Database systems; decoupled optimization; Design optimization; distributed databases; federated databases; federated relational database systems; Internet; Query optimization; query optimizer; Query processing; Relational databases; Space exploration

Domain-Specific Term-List Expansion Using Existing Linguistic Resources - Dorr, Bonnie J; Zhao,Tiejun (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
This report describes a series of experiments involving expansion of a domain-specific human-generated "seed list" using available linguistic resources. The resources used for the expansion are intended to be general purpose: two large-scale Chinese-English dictionaries and a Chinese lexical knowledge base (HowNet). The methodology involves three steps: (1) hand extraction of head words from each entry in the human-generated seed list; (2) automatic comparison of these head words against entries in the linguistic resources-where an entry matches if the head word matches the entry exactly or is included in its the semantic definition; and (3) collection of any resulting matching entries into a larger term list. The terms extracted by this process were verified manually to confirm whether they were relevant to the topic of a specific domain. An important contribution of this work is the finding that the use of a bilingual term list for the expansion proces does not provide a significant improvement over the use of a simpler, more easily produced, monoligual term list.
Keywords: *LEXICOGRAPHY; *LINGUISTICS; AUTOMATIC; CHINA; COMPARISON; EXTRACTION; HANDS; knowledge based systems; linguistics; resources; WORDS(LANGUAGE)

DUSTer: A Method for Unraveling Cross-Language Divergences for Statistical Word-Level Alignment - Dorr, Bonnie J; Pearl,Lisa; Hwa,Rebecca; Habash,Nizar (Machine Translation: From Research to Real UsersMachine Translation: From Research to Real Users, 2002)
The frequent occurrence of divergenceS —structural differences between languages—presents a great challenge for statistical word-level alignment. In this paper, we introduce DUSTer, a method for systematically identifying common divergence types and transforming an English sentence structure to bear a closer resemblance to that of another language. Our ultimate goal is to enable more accurate alignment and projection of dependency trees in another language without requiring any training on dependency-tree data in that language. We present an empirical analysis comparing the complexities of performing word-level alignments with and without divergence handling. Our results suggest that our approach facilitates word-level alignment, particularly for sentence pairs containing divergences.

Dwarf - Sismanis,Yannis; Deligiannakis,Antonios; Roussopoulos, Nick; Kotidis,Yannis (Proceedings of the 2002 ACM SIGMOD international conference on Management of data - SIGMOD '02, 2002)

Embedded grammar tags: advancing natural language interaction on the Web - Dorai,G. K; Yacoob,Yaser (Intelligent Systems, IEEE, 2002)
Embedded grammar tags (EGTs) reflect Web page content by anticipating queries users might launch to retrieve that content. The grammars provide a unifying component for speech recognition engines, semantic Web page representation, and speech output generation. We propose a new framework that lets intelligent agents discover accurate, concise responses to natural language queries. This framework's backbone consists of embedded grammar tags that capture natural language queries. EGTs reflect information content in Web pages by anticipating the queries that users might launch to retrieve particular content.
Keywords: embedded grammar tags; grammars; information content; information resources; intelligent agents; Internet; natural language interaction; natural language queries; natural languages; Search engines; semantic Web page representation; software agents; speech output generation; Speech recognition; speech recognition engines; Web page content

Empirical findings in agile methods - Lindvall,M.; Basili, Victor R.; Boehm,B.; Costa,P.; Dangle,K.; Shull, F.; Tesoriero,R.; Williams,L.; Zelkowitz, Marvin V (Extreme Programming and Agile Methods—XP/Agile Universe 2002, 2002)
In recent years, the use of, interest in, and controversy about Agile methodologies have realized dramatic growth. Anecdotal evidence is rising regarding the effectiveness of agile methodologies in certain environments and for specified projects. However, collection and analysis of empirical evidence of this effectiveness and classification of appropriate environments for Agile projects has not been conducted. Researchers from four institutions organized an eWorkshop to synchronously and virtually discuss and gather experiences and knowledge from eighteen Agile experts spread across the globe. These experts characterized Agile Methods and communicated experiences using these methods on small to very large teams. They discussed the importance of staffing Agile teams with highly skilled developers. They shared common success factors and identified warning signs of problems in Agile projects. These and other findings and heuristics gathered through this valuable exchange can be useful to researchers and to practitioners as they establish an experience base for better decision making.

Evaluating Arabic Retrieval from English or French Queries: The TREC-2001 Cross-Language Information Retrieval Track - Oard, Douglas; Gey,F.C.; Dorr, Bonnie J (Proceedings of the Post Workshop of LREC, 2002)
The Cross-language information retrieval track at the 2001 Text Retrieval Conference (TREC-2001) produced the first large informationretrieval test collection for Arabic. The collection contains 383,872 Arabic news stories, 25 topic descriptions in Arabic, English and French from which queries can be formed, and manual (ground truth) relevance judgments for a useful subset of the topic-document combinations. This paper describes the way in which the collection was created, explains the evaluation measures that the collection is designed to support, and provides an overview of the results from the first set of experiments with the collection. The results make it possible to draw some inferences regarding the utility of the collection for post hoc evaluations.

Evaluation of the SoftPOSIT Model-to-Image Registration Algorithm - David,P.; DeMenthon,D.; Duraiswami, Ramani; Samet, Hanan (Technical Reports from UMIACS, UMIACS-TR-2002-22, 2002)
The problem of pose estimation arises in many areas of computer vision, including object recognition,object tracking, site inspection and updating, and autonomous navigation when scene models are avail- able. We present a new algorithm, called SoftPOSIT, for determining the pose of a 3D object from a single 2D image when correspondences between model points and image points are not known. The algorithm combines Gold’s iterative softassign algorithm [20, 21] for computing correspondences and DeMenthon’s iterative POSIT algorithm [14] for computing object pose under a full-perspective camera model. Our algorithm, unlike most previous algorithms for pose determination, does not have to hypoth- esize small sets of matches and then verify the remaining image points. Instead, all possible matches are treated identically throughout the search for an optimal pose. The performance of the algorithm is extensively evaluated in Monte Carlo simulations on synthetic data under a variety of levels of clutter, occlusion, and image noise. These tests show that the algorithm performs well in a variety of difficult sce- narios, and empirical evidence suggests that the algorithm has an asymptotic run-time complexity that is better than previous methods by a factor of the number of image points. The algorithm is being applied to a number of practical autonomous vehicle navigation problems including the registration of 3D archi- tectural models of a city to images, and the docking of small robots onto larger robots.

Exponential speedup of fixed-parameter algorithms on K 3, 3-minor-free or K 5-minor-free graphs - Demaine,E.; Hajiaghayi, Mohammad T.; Thilikos,D. (Algorithms and Computation, 2002)

Extraction of Critical Nets Based on a Discrete Gradient Vector Field - De Floriani, Leila; Mesmoudi,M. M.; Danovaro,E. (Proceedings of Eurographics, 2002)
In this paper we address the problem of representing the topology of discrete scalar fieldsdefined on triangulated domains in two and three dimensions. To this aim, we use the notion of discrete gradient vector field that we have introduced in [3] to classify critical points and extract a critical net representing the main features of a scalar field defined on a two-dimensional domain. The nature of the critical points provided by the discrete gradient vector field is quite different from those obtained in the differentiable case. Thus, we show that our critical net generalizes classical critical nets corresponding to (the classical differentiable) Morse functions.

Generating A Parsing Lexicon from an LCS-Based Lexicon - Ayan,N.F.; Dorr, Bonnie J (LREC 2002 Workshop Proceedings: Linguistic Knowledge Acquisition and Representation: Bootstrapping Annotated Language Data, 2002)
This paper describes a technique for generating parsing lexicons for a principle-based parser (Minipar). Our approach mapslexical entries in a large LCS-based repository of semantically classified verbs to their corresponding syntactic patterns. A by-product of this mapping is a lexicon that is directly usable in the Minipar system. We evaluate the accuracy and coverage of this lexicon using LDOCE syntactic codes as a gold standard. We show that this lexicon is comparable to the hand-generated Minipar lexicon (i.e., similar recall and precision values). In a later experiment, we automate the process of mapping between the LCS-based repository and syntactic patterns. The advantage of automating the process is that the same technique can be applied directly to lexicons we have for other languages, for example, Arabic, Chinese, and Spanish.

Generating A Parsing Lexicon From Lexical-Conceptual Structure - Ayan,N.F.; Dorr, Bonnie J (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
This paper describes the generation of a lexicon for a principle-based parser (Minipar[5,6]) using descriptions of verbs based on Lexical-Conceptual Structure (LCS [1,2]).1 We aim to determine how much syntactic information we can obtain from a semantic- based lexicon. More specifically, we aim to provide a general approach to projection of syntactic entries from semantic (language-independent) lexicons-and to test the effect of such lexicons on parser performance. Verbs are grouped together into classes-each denoted by an LCS representation adn the thematic grid. These are mapped systemat- ically into syntactic categories associated with entries in the Minipar parser. The main advantage of this LCS-to-syntax projection is language protability: We currently have LCS lexicons for English, Arabic, Spanish, and Chinese; thus, our LCS-projection ap- proach allows us to produce syntactic lexicons for parsing in each of these languages. For comparing the performance of the projection from the LCS to Minpar coes, we also generated the mappings for the codes of Longman's Directionary of Contemporary En- glish (LDOCE [8])-the most comprehensive online dictionary for syntactic categorization. Preliminary experiments indicate that our approach yields a categorization of verbs with 58% precision and 65% recall as measured against LDOCE-with an improved precision of 74% when redundancy is removed. The next section presents a brief description of each code set we use. In Section 3, we explain how we generated Minipar codes from LCS representation. Finally, Section 4, discusses our experiments and results.

GLEANS: A generator of logical extracts and abstracts for nice summaries - Daumé, Hal; Echihabi,A.; Marcu,D.; Munteanu,D.; Soricut,R. (Workshop on Automatic Summarization, 2002)

Half-edge Multi-Tessellation: a compact representations for multiresolution tetrahedral meshes - Danovaro,E.; De Floriani, Leila (Proceedings 1st International Symposium on 3D Data Processing Visualization and Transmission, 2002)
This paper deals with the problem of analyzing and vi-sualizing volume data sets of large size. To this aim, we define a three-dimensional multi-resolution model based on unstructured tetrahedral meshes, and built through a half- edge-collapse simplification strategy, that we call a Half- Edge Multi-Tessellation (MT). We propose a new compact data structure for a half-edge MT, and we analyze it with respect to both its space requirements and its efficiency in supporting Level-Of-Detail (LOD) queries based on selec- tive refinement.

Handling Translation Divergences: Combining Statistical and Symbolic Techniques in Generation-Heavy Machine Translation - Habash,Nizar; Dorr, Bonnie J (Machine Translation: From Research to Real UsersMachine Translation: From Research to Real Users, 2002)
This paper describes a novel approach to handling translation divergences in a Generation-Heavy Hybrid Machine Translation (GHMT) system. The translation divergence problem is usually reserved for Transfer and Interlingual MT because it requires a large combination of complex lexical and structural mappings. A major requirement of these approaches is the accessibility of large amounts of explicit symmetric knowledge for both source and target languages. This limitation renders Transfer and Interlingual approaches ineffective in the face of structurally-divergent language pairs with asymmetric resources. GHMT addresses the more common form of this problem, source-poor/targetrich, by fully exploiting symbolic and statistical target-language resources. This non-interlingual non-transfer approach is accomplished by using target-language lexical semantics, categorial variations and subcategorization frames to overgenerate multiple lexico-structural variations from a target-glossed syntactic dependency of the source-language sentence. The symbolic overgeneration, which accounts for different possible translation divergences, is constrained by a statistical target-language model.

Hidden loop recovery for handwriting recognition - David Doermann; Intrator,N.; Rivin,E.; Steinherz,T. (Frontiers in Handwriting Recognition, 2002. Proceedings. Eighth International Workshop on, 2002)
One significant challenge in the recognition of off-line handwriting is in the interpretation of loop structures. Although this information is readily available in online representation, close proximity of strokes often merges their centers making them difficult to identify. In this paper a novel approach to the recovery of hidden loops in off-line scanned document images is presented. The proposed algorithm seeks blobs that resemble truncated ellipses. We use a sophisticated form analysis method based on mutual distance measurements between the two sides of a symmetric shape. The experimental results are compared with the ground truth of the online representations of each off-line word image. More than 86% percent of the meaningful loops are handled correctly.
Keywords: analysis; character; contour; cursive; detection; distance; edge; ellipses; form; handwritten; hidden; loop; measurements; mutual; partitioning; recognition; recovery; SHAPE; shape; sophisticated; strokes; symmetric; truncated; word

How young can our design partners be - Farber,A.; Druin, Allison; Chipman,G.; Julian,D.; Somashekhar,S. (Proceedings of the Participatory Design Conference, 2002)

HTN Planning in Answer Set Programming - Dix,Jurgen; Kuter,Ugur; Nau, Dana S. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
In this paper we introduce a formalism for solving Hierarchical Task NEtwork(HTN) Planning using Answer Set Programming (ASP). The ASP paradigm evolved out of the stable semantics for logic programs in recent years and is strongly related to nonmonotonic logics. We consider the formulation of HTM planning as described in the SHOP planning system and define a systematic translation method from SHOP's representation of the planning problems into logic programs with negation. We show that our translation is sound and complete: answer sets of the logic programs obtained by our translation correspond exactly to the solutions of the planning problems. Our approach does not rly on a particular system for computing answer sets. It can therefore serve as a means to evaluate ASP systems by using well-established benchmarks from the planning community. We tested our method on various such benchmarks and used smodels and DLV for computing answer sets. We compared our method to (1) similar approaches based on non-HTN planning and (2) SHOP, a dedicated planning system. We show that our approach outperforms non-HTN methods and that its performance is closer to that of SHOP, when we are using ASP systems which allow for nonground programs. (Also UMIACS-TR-2002-18)
Keywords: Technical Report

The importance of lexicalized syntax models for natural language generation tasks - Daumé, Hal; Knight,K.; Langkilde-Geary,I.; Marcu,D.; Yamada,K. (Proc. of INLG, 2002)

Improved Word-Level Alignment: Injecting Knowledge about MT Divergences - Dorr, Bonnie J; Pearl,Lisa; Hwa,Rebecca; Habash,Nizar (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
Word-level alignments of bilingual text (bitexts) are not an integral part of statistical machine translation models, but also useful for lexical acquisition, treebank construction. and part-of-speech tagging. The frequent occurrence of divergences, structural differences between languages, presents a great challenge to the alignment task. We resolve some of the most prevalent divergence cases by using syntactic parse information to transform the sentence structure of one language to bear a closer resemblance to that of the other language. In this paper, we show that common divergence types can be found in multiple language pairs (in particular, we focus on English-Spanish and English-Arabic) and systematically identified. We describe our techniques for modifying English parse trees to form resulting sentences that share more similarity with the sentences in the other languages; finally, we present an empirical analysis comparing the complexities of performing word-level alignments with an without divergence handling. Our results suggest that divergence-handling can improve word-level alignment.
Keywords: *LEXICOGRAPHY; *MACHINE TRANSLATION; *STATISTICAL ANALYSIS; *WORDS(LANGUAGE); ACQUISITION; ALIGNMENT; EXPERIMENTAL DATA; LANGUAGE; linguistics; MATHEMATICAL MODELS; STATISTICS AND PROBABILITY; TREES