Multi-scale dual morse complexes for representing terrain morphology - Danovaro,Emanuele; De Floriani, Leila; Vitali,Maria; Magillo,Paola (Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, 2007)
We propose a new multi-scale terrain model, based on a hierarchical representation for the morphology of a terrain. The basis of our morphological model is a dual Morse decomposition of the terrain, composed by the stable and unstable manifolds defined by its critical points and its integral lines. We propose a two-level representation of the dual Morse decomposition and we define new simplification operators for the Morse decomposition which act on such representation. Based on these operators, we define a hierarchical morphology-based representation, that we call a Multi-scale Morse Complex (MMC). Results from our implementation of the MMC are presented.
Keywords: Morphology; multi-scale representations; terrain modeling

Multi-scale Structural Saliency for Signature Detection - Zhu,Guangyu; Yefeng Zheng; David Doermann; Jaeger,Stefan (IEEEConference on Computer Vision and Pattern Recognition (CVPR 2007)IEEEConference on Computer Vision and Pattern Recognition (CVPR 2007), 2007)
Detecting and segmenting free-form objects from cluttered backgrounds is a challenging problem in computer vision. Signature detection in document images is one classic example and as of yet no reasonable solutions have been presented. In this paper, we propose a novel multi-scale approach to jointly detecting and segmenting signatures from documents with diverse layouts and complex backgrounds. Rather than focusing on local features that typically have large variations, our approach aims to capture the structural saliency of a signature by searching over multiple scales. This detection framework is general and computationally tractable. We present a saliency measure based on a signature production model that effectively quantifies the dynamic curvature of 2-D contour fragments. Our evaluation using large real world collections of handwritten and machine printed documents demonstrates the effectiveness of this joint detection and segmentation approach.

Multi-scale video cropping - El-Alfy,Hazem; Jacobs, David W.; Davis, Larry S. (Proceedings of the 15th international conference on Multimedia, 2007)
We consider the problem of cropping surveillance videos. This process chooses a trajectory that a small sub-window can take through the video, selecting the most important parts of the video for display on a smaller monitor. We model the information content of the video simply, by whether the image changes at each pixel. Then we show that we can find the globally optimal trajectory for a cropping window by using a shortest path algorithm. In practice, we can speed up this process without affecting the results, by stitching together trajectories computed over short intervals. This also reduces system latency. We then show that we can use a second shortest path formulation to find good cuts from one trajectory to another, improving coverage of interesting events in the video. We describe additional techniques to improve the quality and efficiency of the algorithm, and show results on surveillance videos.
Keywords: shortest path algorithm; Surveillance; video cropping

Numerical Analysis of Plasmon Resonances in Nanoparticles Based on Fast Multipole Method - Zhang,Zhenyu; Mayergoyz, Issak D; Gumerov, Nail A.; Duraiswami, Ramani (Magnetics, IEEE Transactions on, 2007)
A novel technique for the numerical analysis of plasmon resonances by using the fast multipole method (FMM) is presented. This approach is based on the solution of the eigenvalue problem for boundary integral equations, which can be naturally implemented by using the FMM. Numerical examples that highlight the efficiency of the fast multipole implementation are reported
Keywords: analysis; boundary; and; boundary; eigenfunctions; nanoparticles; plasmons; equations; eigenvalue; equations; eigenvalues; integral; method; nanoparticle; multipole; plasmon; problems; fast; resonance; numerical

Object detection using a shape codebook - Yu,X.; Yi,L.; Fermüller, Cornelia; David Doermann (British Machine Vision Conference, 2007)
This paper presents a method for detecting categories of objects in real-worldimages. Given training images of an object category, our goal is to recognize and localize instances of those objects in a candidate image. The main contribution of this work is a novel structure of the shape code- book for object detection. A shape codebook entry consists of two compo- nents: a shape codeword and a group of associated vectors that specify the object centroids. Like their counterpart in language, the shape codewords are simple and generic such that they can be easily extracted from most object categories. The associated vectors store the geometrical relationships be- tween the shape codewords, which specify the characteristics of a particular object category. Thus they can be considered as the “grammar” of the shape codebook. In this paper, we use Triple-Adjacent-Segments (TAS) extracted from im- age edges as the shape codewords. Object detection is performed in a prob- abilistic voting framework. Experimental results on public datasets show performance similiar to the state-of-the-art, yet our method has significantly lower complexity and requires considerably less supervision in the training (We only need bounding boxes for a few training samples, do not need fig- ure/ground segmentation and do not need a validation dataset).

Object Detection Using Shape Codebook - Yu,Xiaodong; Li,Yi; Fermüller, Cornelia; David Doermann (British Machine Vision Conference (BMVC'07), 2007)
This paper presents a method for detecting categories of objects in real-world images. Given training images of an object category, our goal is to recognize and localize instances of those objects in a candidate image. The main contribution of this work is a novel structure of the shape codebook for object detection. A shape codebook entry consists of two components: a shape codeword and a group of associated vectors that specify the object centroids. Like their counterpart in language, the shape codewords are simple and generic such that they can be easily extracted from most object categories. The associated vectors store the geometrical relationships between the shape codewords, which specify the characteristics of a particular object category. Thus they can be considered as the “grammar” of the shape codebook. In this paper, we use Triple-Adjacent-Segments (TAS) extracted from image edges as the shape codewords. Object detection is performed in a probabilistic voting framework. Experimental results on public datasets show performance similar to the state-of-the-art, yet our method has significantly lower complexity and requires considerably less supervision in the training (We only need bounding boxes for a few training samples, do not need figure/ground segmentation and do not need a validation dataset).

Object Tracking at Multiple Levels of Spatial Resolutions - Tran,S.D.; Davis, Larry S. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
Tracking is usually performed at a single level of data resolution. This paper describes a multi-resolution tracking framework developed with efficiency and robustness in mind. Efficiency is achieved by processing low resolution data whenever possible. Robustness results from multiple level coarse-to-fine searching in the tracking state space. We combine sequential filtering both in time and resolution levels into a probabilistic framework. A color blob tracker is implemented and the tracking results are evaluated in a number of experiments.
Keywords: coarse-to-fine; detection; tracking; filtering; spatial; framework; object; levels; tracking; multiple; resolution; multiresolution; resolutions; searching; data; space; computer; state; tracking; tracking; sequential; vision; object

Objects in Action: An Approach for Combining Action Understanding and Object Perception - Gupta,A.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, 2007)
Analysis of videos of human-object interactions involves understanding human movements, locating and recognizing objects and observing the effects of human movements on those objects. While each of these can be conducted independently, recognition improves when interactions between these elements are considered. Motivated by psychological studies of human perception, we present a Bayesian approach which unifies the inference processes involved in object classification and localization, action understanding and perception of object reaction. Traditional approaches for object classification and action understanding have relied on shape features and movement analysis respectively. By placing object classification and localization in a video interpretation framework, we can localize and classify objects which are either hard to localize due to clutter or hard to recognize due to lack of discriminative features. Similarly, by applying context on human movements from the objects on which these movements impinge and the effects of these movements, we can segment and recognize actions which are either too subtle to perceive or too hard to recognize using motion features alone.
Keywords: analysis; image; approach; action; Bayesian; classification; image; classification; object; framework; Bayes; interactions; inference; interpretation; localization; object; methods; gesture; MOTION; movements; human; perception; perception; human-object; perception; object; process; object; processing; visual; recognition; image; recognition; video; segmentation; action; segmentation; object; signal; understanding; human

Out-of-core Multi-resolution Terrain Modeling - Danovaro,E.; De Floriani, Leila; Puppo,E.; Samet, Hanan (Spatial data on the Web: modeling and management, 2007)

Parameterized Looped Schedules for Compact Representation of Execution Sequences in DSP Hardware and Software Implementation - Ming-Yung Ko; Zissulescu,C.; Puthenpurayil,S.; Bhattacharyya, Shuvra S.; Kienhuis,B.; Deprettere,E. F (IEEE Transactions on Signal Processing, 2007)
In this paper, we present a technique for compact representation of execution sequences in terms of efficient looping constructs. Here, by a looping construct, we mean a compact way of specifying a finite repetition of a set of execution primitives. Such compaction, which can be viewed as a form of hierarchical run-length encoding (RLE), has application in many very large scale integration (VLSI) signal processing contexts, including efficient control generation for Kahn processes on field-programmable gate arrays (FPGAs), and software synthesis for static dataflow models of computation. In this paper, we significantly generalize previous models for loop-based code compaction of digital signal processing (DSP) programs to yield a configurable code compression methodology that exhibits a broad range of achievable tradeoffs. Specifically, we formally develop and apply to DSP hardware and software synthesis a parameterizable loop scheduling approach with compact format, dynamic reconfigurability, and low-overhead decompression
Keywords: Application software; array signal processing; code compression methodology; compact representation; Compaction; data compression; Design automation; Digital signal processing; digital signal processing chips; DSP; DSP hardware; embedded systems; Encoding; Field programmable gate arrays; field-programmable gate arrays (FPGAs); FPGA; Hardware; hierarchical runlength encoding; high-level synthesis; Kahn process; loop-based code compaction; looping construct; parameterized loop schedules; program compilers; reconfigurable design; runlength codes; scheduling; Signal generators; Signal processing; Signal synthesis; software engineering; software implementation; static dataflow models; Very large scale integration; VLSI

Pedestrian detection via periodic motion analysis - Ran, Y.; Weiss, I.; Zheng,Q.; Davis, Larry S. (International Journal of Computer Vision, 2007)
We describe algorithms for detecting pedestrians in videos acquired by infrared (and color) sensors. Two approaches are proposed based on gait. The first employs computationally efficient periodicity measurements. Unlike other methods, it estimates a periodic motion frequency using two cascading hypothesis testing steps to filter out non-cyclic pixels so that it works well for both radial and lateral walking directions. The extraction of the period is efficient and robust with respect to sensor noise and cluttered background. In order to integrate shape and motion, we convert the cyclic pattern into a binary sequence by Maximal Principal Gait Angle (MPGA) fitting in the second method. It does not require alignment and continuously estimates the period using a Phase-locked Loop. Both methods are evaluated by experimental results that measure performance as a function of size, movement direction, frame rate and sequence length.

Plasma Turbulence Simulation and Visualization on Graphics Processors: Efficient Parallel Computing on the Desktop - Stantchev,George; Juba,Derek; Dorland,William; Varshney, Amitabh (Bulletin of the American Physical Society, 2007)
Direct numerical simulation (DNS) of turbulence is computationally very intensive and typically relies on some form of parallel processing. Spectral kernels used for spatial discretization are a common computational bottleneck on distributed memory architectures. One way to increase the efficiency of DNS algorithms is to parallelize spectral kernels using tightly-coupled SPMD multiprocessor hardware architecture with minimal inter-processor communication latency. In this poster we present techniques to take advantage of the recent programmable interfaces for modern Graphics Processing Units (GPUs) to carefully map DNS computations to GPU architectures that are characterized by a very high memory bandwidth and hundreds of SPMD processors. We compare and contrast the performance of our parallel algorithm on a modern GPU versus a CPU implementation of several turbulence simulation codes. We also demonstrate a prototype of a scalable computational steering framework based on turbulence simulation and visualization coupling on the GPU.

Plasmonics and the parallel programming problem - Vishkin, Uzi; Smolyaninov,I.; Davis,C. (Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2007)
While many parallel computers have been built, it has generally been too difficult to program them. Now, all computersare effectively becoming parallel machines. Biannual doubling in the number of cores on a single chip, or faster, over the coming decade is planned by most computer vendors. Thus, the parallel programming problem is becoming more critical. The only known solution to the parallel programming problem in the theory of computer science is through a parallel algorithmic theory called PRAM. Unfortunately, some of the PRAM theory assumptions regarding the bandwidth between processors and memories did not properly reflect a parallel computer that could be built in previous decades. Reaching memories, or other processors in a multi-processor organization, required off-chip connections through pins on the boundary of each electric chip. Using the number of transistors that is becoming available on chip, on-chip architectures that adequately support the PRAM are becoming possible. However, the bandwidth of off-chip connections remains insufficient and the latency remains too high. This creates a bottleneck at the boundary of the chip for a PRAM-On-Chip architecture. This also prevents scalability to larger “supercomputing” organizations spanning across many processing chips that can handle massive amounts of data. Instead of connections through pins and wires, power-efficient CMOS-compatible on-chip conversion to plasmonic nanowaveguides is introduced for improved latency and bandwidth. Proper incorporation of our ideas offer exciting avenues to resolving the parallel programming problem, and an alternative way for building faster, more useable and much more compact supercomputers.

Poster Session 5: Matching and Registration-Simultaneous Appearance Modeling and Segmentation for Matching People Under Occlusion - Lin,Z.; Davis, Larry S.; David Doermann; DeMenthon,D. (Lecture Notes in Computer Science, 2007)

A probabilistic framework for correspondence and egomotion - Domke, J.; Aloimonos, J. (Dynamical Vision, 2007)

Probabilistic Fusion Tracking Using Mixture Kernel-Based Bayesian Filtering - Han,Bohyung; Joo,Seong-Wook; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Even though sensor fusion techniques based on particle filters have been applied to object tracking, their implementations have been limited to combining measurements from multiple sensors by the simple product of individual likelihoods. Therefore, the number of observations is increased as many times as the number of sensors, and the combined observation may become unreliable through blind integration of sensor observations - especially if some sensors are too noisy and non-discriminative. We describe a methodology to model interactions between multiple sensors and to estimate the current state by using a mixture of Bayesian filters - one filter for each sensor, where each filter makes a different level of contribution to estimate the combined posterior in a reliable manner. In this framework, an adaptive particle arrangement system is constructed in which each particle is allocated to only one of the sensors for observation and a different number of samples is assigned to each sensor using prior distribution and partial observations. We apply this technique to visual tracking in logical and physical sensor fusion frameworks, and demonstrate its effectiveness through tracking results.
Keywords: (numerical; adaptive; arrangement; Bayesian; Filtering; filtering; multiple; filters; probabilistic; fusion; fusion; tracking; integration; mixture; kernel-based; methods); sensor; methods; array; particle; processing; particle; sensors; object; signal; system; blind; techniques; visual; tracking; Bayes; tracking; particle; tracking; sensor

Probabilistic graphical models and their role in databases - Deshpande, Amol; Sarawagi,Sunita (Proceedings of the 33rd international conference on Very large data bases, 2007)
Probabilistic graphical models provide a framework for compact representation and efficient reasoning about the joint probability distribution of several interdependent variables. This is a classical topic with roots in statistical physics. In recent years, spurred by several applications in unstructured data integration, sensor networks, image processing, bio-informatics, and code design, the topic has received renewed interest in the machine learning, data mining, and database communities. Techniques from graphical models have also been applied to many topics directly of interest to the database community including information extraction, sensor data analysis, imprecise data representation and querying, selectivity estimation for query optimization, and data privacy. As database research continues to expand beyond the confines of traditional enterprise domains, we expect both the need and applicability of probabilistic graphical models to increase dramatically over the next few years. With this tutorial, we are aiming to provide a foundational overview of probabilistic graphical models to the database community, accompanied by a brief overview of some of the recent research literature on the role of graphical models in databases.

A probabilistic notion of camera geometry: Calibrated vs. uncalibrated - Domke, J.; Aloimonos, J. (PHOTOGRAMMETRIE FERNERKUNDUNG GEOINFORMATION, 2007)

Probabilistic wavelet synopses for multiple measures - Deligiannakis,Antonios; Garofalakis,Minos N.; Roussopoulos, Nick (2007)
A technique for building probabilistic wavelet synopses for multi-measure data sets is provided. In the presence of multiple measures, it is demonstrated that the problem of exact probabilistic coefficient thresholding becomes significantly more complex. An algorithmic formulation for probabilistic multi-measure wavelet thresholding based on the idea of partial-order dynamic programming (PODP) is provided. A fast, greedy approximation algorithm for probabilistic multi-measure thresholding based on the idea of marginal error gains is provided. An empirical study with both synthetic and real-life data sets validated the approach, demonstrating that the algorithms outperform naive approaches based on optimizing individual measures independently and the greedy thresholding scheme provides near-optimal and, at the same time, fast and scalable solutions to the probabilistic wavelet synopsis construction problem.

QCS: A system for querying, clustering and summarizing documents - Dunlavy,Daniel M.; O’Leary,Dianne P.; Conroy,John M.; Schlesinger,Judith D. (Information Processing & Management, 2007)
Information retrieval systems consist of many complicated components. Research and development of such systems is often hampered by the difficulty in evaluating how each particular component would behave across multiple systems. We present a novel integrated information retrieval system—the Query, Cluster, Summarize (QCS) system—which is portable, modular, and permits experimentation with different instantiations of each of the constituent text analysis components. Most importantly, the combination of the three types of methods in the QCS design improves retrievals by providing users more focused information organized by topic.We demonstrate the improved performance by a series of experiments using standard test sets from the Document Understanding Conferences (DUC) as measured by the best known automatic metric for summarization system evaluation, ROUGE. Although the DUC data and evaluations were originally designed to test multidocument summarization, we developed a framework to extend it to the task of evaluation for each of the three components: query, clustering, and summarization. Under this framework, we then demonstrate that the QCS system (end-to-end) achieves performance as good as or better than the best summarization engines. Given a query, QCS retrieves relevant documents, separates the retrieved documents into topic clusters, and creates a single summary for each cluster. In the current implementation, Latent Semantic Indexing is used for retrieval, generalized spherical k-means is used for the document clustering, and a method coupling sentence “trimming” and a hidden Markov model, followed by a pivoted QR decomposition, is used to create a single extract summary for each cluster. The user interface is designed to provide access to detailed information in a compact and useful format. Our system demonstrates the feasibility of assembling an effective IR system from existing software libraries, the usefulness of the modularity of the design, and the value of this particular combination of modules.
Keywords: clustering; Information retrieval; latent semantic indexing; Sentence trimming; Summarization; TEXT PROCESSING

Real Time Capture of Audio Images and their Use with Video - O'donovan,Adam; Duraiswami, Ramani; Gumerov, Nail A. (Applications of Signal Processing to Audio and Acoustics, 2007 IEEE Workshop on, 2007)
Spherical microphone arrays provide an ability to compute the acoustical intensity corresponding to different spatial directions in a given frame of audio-data. These intensities may be exhibited as an image and these images updated at a high frame rate to achieve a video stream if the data capture and intensity computations can be performed sufficiently quickly, there by creating a frame-rate audio camera. We describe how such a camera can be built and the processing done sufficiently quickly using graphics processors. The joint processing of captured frame-rate audio and video images enables applications such as visual identification of noise sources, beamforming and noise-suppression in video conferencing and others, provided it is possible to account for the spatial differences in the location of the audio and the video cameras. Based on the recognition that the spherical array can be viewed as a central projection camera it is possible to perform such joint analysis. We provide several examples of real-time applications.

Recovery in culture of viable but nonculturable Vibrio parahaemolyticus: regrowth or resuscitation? - Coutard,Fran|[ccedil]|ois; Crassous,Philippe; Droguet,Micka|[euml]|l; Gobin,Eric; Rita R Colwell; Pommepuy,Monique; Hervio-Heath,Dominique (The ISME Journal, 2007)
The objective of this study was to explore the recovery of culturability of viable but nonculturable (VBNC) Vibrio parahaemolyticus after temperature upshift and to determine whether regrowth or resuscitation occurred. A clinical strain of V. parahaemolyticus Vp5 was rendered VBNC by exposure to artificial seawater (ASW) at 4°C. Aliquots of the ASW suspension of cells (0.1, 1 and 10 ml) were subjected to increased temperatures of 20°C and 37°C. Culturability of the cells in the aliquots was monitored for colony formation on a rich medium and changes in morphology were measured by scanning (SEM) and transmission (TEM) electron microscopy. Samples of VBNC cells were fixed and examined by SEM, revealing a heterogeneous population comprising small cells and larger, flattened cells. Forty-eight hours after temperature upshift to 20°C or 37°C, both elongation and division by binary fission of the cells were observed, employing SEM and TEM, but only in the 10-ml aliquots. The results suggest that a portion of VBNC cells is able to undergo cell division. It is concluded that a portion of VBNC cells of V. parahaemolyticus subjected to cold temperatures remain viable. After temperature upshift, regrowth of those cells, rather than resuscitation of all bacteria of the initial inoculum, appears to be responsible for recovery of culturability of VBNC cells of V. parahaemolyticus. Nutrient in filtrates of VBNC cells is hypothesized to allow growth of the temperature-responsive cells, with cell division occurring via binary fission, but also including an atypical, asymmetric cell division.
Keywords: ecophysiology; ecosystems; environmental biotechnology; geomicrobiology; ISME J; microbe interactions; microbial communities; microbial ecology; microbial engineering; microbial epidemiology; microbial genomics; microorganisms

Relationship identification for social network discovery - Diehl,C. P; Namata,G.; Getoor, Lise (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2007)
In recent years, informal, online communication has trans- formed the ways in which we connect and collaborate with friends and colleagues. With millions of individuals commu- nicating online each day, we have a unique opportunity to ob- serve the formation and evolution of roles and relationships in networked groups and organizations. Yet a number of chal- lenges arise when attempting to infer the underlying social network from data that is often ambiguous, incomplete and context-dependent. In this paper, we consider the problem of collaborative network discovery from domains such as intel- ligence analysis and litigation support where the analyst is at- tempting to construct a validated representation of the social network. We specifically address the challenge of relation- ship identification where the objective is to identify relevant communications that substantiate a given social relationship type. We propose a supervised ranking approach to the prob- lem and assess its performance on a manager-subordinate re- lationship identification task using the Enron email corpus. By exploiting message content, the ranker routinely cues the analyst to relevant communications relationships and mes- sage traffic that are indicative of the social relationship.

Report on the Fourth International Workshop on Data Management for Sensor Networks (DMSN 2007) - Balazinska,Magdalena; Deshpande, Amol; Labrinidis,Alexandros; Luo,Qiong; Madden,Samuel; Yang,Jun (SIGMOD Rec., 2007)
Sensor networks enable an unprecedented level of access to the physical world, and hold tremendous potential to revolutionize many application domains. Research on sensor networks spans many areas of computer science, and there are now major conferences, e.g., IPSN and SenSys, devoted to sensor networks. However, there is no focused forum for discussion of early and innovative work on data management in sensor networks. The International Workshop on Data Management for Sensor Networks (DMSN), inaugurated in 2004, aims to fill this significant gap in the database and sensor network communities.

Representing and Querying Correlated Tuples in Probabilistic Databases - Sen,Prithviraj; Deshpande, Amol (Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on, 2007)
Probabilistic databases have received considerable attention recently due to the need for storing uncertain data produced by many real world applications. The widespread use of probabilistic databases is hampered by two limitations: (1) current probabilistic databases make simplistic assumptions about the data (e.g., complete independence among tuples) that make it difficult to use them in applications that naturally produce correlated data, and (2) most probabilistic databases can only answer a restricted subset of the queries that can be expressed using traditional query languages. We address both these limitations by proposing a framework that can represent not only probabilistic tuples, but also correlations that may be present among them. Our proposed framework naturally lends itself to the possible world semantics thus preserving the precise query semantics extant in current probabilistic databases. We develop an efficient strategy for query evaluation over such probabilistic databases by casting the query processing problem as an inference problem in an appropriately constructed probabilistic graphical model. We present several optimizations specific to probabilistic databases that enable efficient query evaluation. We validate our approach by presenting an experimental evaluation that illustrates the effectiveness of our techniques at answering various queries using real and synthetic datasets.

Representing Tuple and Attribute Uncertainty in Probabilistic Databases - Sen,P.; Deshpande, Amol; Getoor, Lise (Seventh IEEE International Conference on Data Mining Workshops, 2007. ICDM Workshops 2007, 2007)
There has been a recent surge in work in probabilistic databases, propelled in large part by the huge increase in noisy data sources-sensor data, experimental data, data from uncurated sources, and many others. There is a growing need to be able to flexibly represent the uncertainties in the data, and to efficiently query the data. Building on existing probabilistic database work, we present a unifying framework which allows a flexible representation of correlated tuple and attribute level uncertainties. An important capability of our representation is the ability to represent shared correlation structures in the data. We provide motivating examples to illustrate when such shared correlation structures are likely to exist. Representing shared correlations structures allows the use of sophisticated inference techniques based on lifted probabilistic inference that, in turn, allows us to achieve significant speedups while computing probabilities for results of user-submitted queries.
Keywords: attribute uncertainty; Computer science; Conferences; correlation structures; data mining; Data models; database management systems; Educational institutions; inference mechanisms; noisy data sources; probabilistic database; probabilistic inference; Probability distribution; Query processing; Relational databases; Sensor phenomena and characterization; tuple representation; Uncertainty; uncertainty handling

Robust appearance modeling for pedestrian and vehicle tracking - Abd-Almageed, Wael; Davis, Larry S. (Multimodal Technologies for Perception of Humans, 2007)
This paper describes a system for tracking people and vehicles for stationary-camera visual surveillance. The appearance of objects being tracked is modeled using mixtures of mixtures of Gaussians. Particles filters are used to track the states of object. Results show the robustness of the system to various lighting and object conditions.

Robust Object Tracking with Regional Affine Invariant Features - Tran,Son; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
We present a tracking algorithm based on motion analysis of regional affine invariant image features. The tracked object is represented with a probabilistic occupancy map. Using this map as support, regional features are detected and probabilistically matched across frames. The motion of pixels is then established based on the feature motion. The object occupancy map is in turn updated according to the pixel motion consistency. We describe experiments to measure the sensitivities of our approach to inaccuracy in initialization, and compare it with other approaches.
Keywords: affine; algorithm; feature; analysis; image; analysis; pixel; consistency; regional; detection; motion; detection; tracking; extraction; image; feature; features; robust; invariant; matching; image; MOTION; object; resolution; object; tracking

SAAR: A shared control plane for overlay multicast - Nandi,A.; Ganjam,A.; Druschel,P.; Ng,T. S.E; Stoica,I.; Zhang,H.; Bhattacharjee, Bobby (Proceedings of 4th USENIX Symposium on Networked Systems Design & Implementation, 2007)
Many cooperative overlay multicast systems of diverse designs have been implemented and deployed. In this paper, we explore a new architecture for overlay multicast: we factor out the control plane into a separate overlay that provides a single primitive: a configurable anycast for peer selection. This separation of control and data overlays has several advantages. Data overlays can be optimized for efficient content delivery, while the control overlay can be optimized for flexible and efficient peer selection. Several data channels can share a control plane for fast switching among content channels, which is particularly important for IPTV. And, the control overlay can be reused in multicast systems with different data plane organizations.We designed and evaluated a decentralized control overlay for endsystem multicast. The overlay proactively aggregates system state and implements a powerful anycast primitive for peer selection. We demonstrate that SAAR's efficiency in locating peers reduces channel switching time, improves the quality of content delivery, and reduces overhead, even under dynamic conditions and at scale. An experimental evaluation demonstrates that the system can efficiently support single-tree, multi-tree and block-based multicast systems.

A scalar potential formulation and translation theory for the time-harmonic Maxwell equations - Gumerov, Nail A.; Duraiswami, Ramani (Journal of Computational Physics, 2007)
We develop a computational method based on the Debye scalar potential representation, which efficiently reduces the solution of Maxwell’s equations to the solution of two scalar Helmholtz equations. One of the key contributions of this paper is a theory for the translation of Maxwell solutions using such a representation, since the scalar potential form is not invariant with respect to translations. The translation theory is developed by introducing “conversion” operators, which enable the representation of the electric and magnetic vector fields via scalar potentials in an arbitrary reference frame. Advantages of this representation include the fact that only two Helmholtz equations need be solved, and moreover, the divergence free constraints are satisfied automatically by construction. Truncation error bounds are also presented. The availability of a translation theory and error bounds for this representation can find application in methods such as the Fast Multipole Method.For illustration of the use of the representation and translation theory we implemented an algorithm for the simulation of Mie scattering off a system of spherical objects of different sizes and dielectric properties using a variant of the T-matrix method. The resulting system was solved using an iterative method based on GMRES. The results of the computations agree well with previous computational and experimental results.
Keywords: Debye potentials; Electromagnetic scattering; Fast Multipole Method; Helmholtz equation; Maxwell equations; Mie scattering; T-matrix method; Translation operators

Scheduling to minimize gaps and power consumption - Demaine,E. D; Ghodsi,M.; Hajiaghayi, Mohammad T.; Sayedi-Roshkhar,A. S; Zadimoghaddam,M. (Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, 2007)

Segmentation using Meta-texture Saliency - Yacoob,Yaser; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
We address segmentation of an image into patches that have an underlying salient surface-roughness. Three intrinsic images are derived: reflectance, shading and meta- texture images. A constructive approach is proposed for computing a meta-texture image by preserving, equalizing and enhancing the underlying surface-roughness across color, brightness and illumination variations. We evaluate the performance on sample images and illustrate quantitatively that different patches of the same material, in an image, are normalized in their statistics despite variations in color, brightness and illumination. Finally, segmentation by line-based boundary-detection is proposed and results are provided and compared to known algorithms.
Keywords: analysis; image; colour; enhancement; image; image; image; salient; patches; image; segmentation; image; segmentation; meta-texture; surface-roughness; image; texture

A semantic web environment for digital shapes understanding - De Floriani, Leila; Hui,Annie; Papaleo,Laura; Huang,May; Hendler,James (Proceedings of the semantic and digital media technologies 2nd international conference on Semantic Multimedia, 2007)
In the last few years, the volume of multimedia content available on the Web significantly increased. This led to the need for techniques to handle such data. In this context, we see a growing interest in considering the Semantic Web in action and in the definition of tools capable of analyzing and organizing digital shape models. In this paper, we present a Semantic Web environment, be-SMART, for inspecting 3D shapes and for structuring and annotating such shapes according to ontology-driven metadata. Specifically, we describe in details the first module of be-SMART, the Geometry and Topology Analyzer, and the algorithms we have developed for extracting geometrical and topological information from 3D shapes. We also describe the second module, the Topological Decomposer, which produces a graph-based representation of the decomposition of the shape into manifold components. This is successively modified by the third and the fourth modules, which perform the automatic and manual segmentation of the manifold parts.
Keywords: digital shapes; semantic annotation; semantic web; shape analysis; shape understanding

Signal Processing for Biometric Systems [DSP Forum] - Jain, A.K.; Chellapa, Rama; Draper, S.C.; Memon, N.; Phillips,P.J.; Vetro, A. (Signal Processing Magazine, IEEE, 2007)
This IEEE signal processing magazine (SPM) forum discuses signal processing applications, technologies, requirements, and standardization of biometric systems. The forum members bring their expert insights into issues such as biometric security, privacy, and multibiometric and fusion techniques. The invited forum members are Prof. Anil K. Jain of Michigan State University, Prof. Rama Chellappa of the University of Maryland, Dr. Stark C. Draper of theUniversity of Wisconsin in Madison, Prof. Nasir Memon of Polytechnic University, and Dr. P. Jonathon Phillips of the National Institute of Standards and Technology. The moderator of the forum is Dr. Anthony Vetro of Mitsubishi Electric Research Labs, and associate editor of SPM.
Keywords: (access; biometric; control); security; signal; forum; signal; magazine; PROCESSING; processing; security; biometric; standardization; fusion; systems; technique; multibiometric; technique; signal; technology; biometrics

Simultaneous appearance modeling and segmentation for matching people under occlusion - Zhe Lin; Davis, Larry S.; David Doermann; DeMenthon,Daniel (Proceedings of the 8th Asian conference on Computer vision - Volume Part II, 2007)
We describe an approach to segmenting foreground regions corresponding to a group of people into individual humans. Given background subtraction and ground plane homography, hierarchical parttemplate matching is employed to determine a reliable set of human detection hypotheses, and progressive greedy optimization is performed to estimate the best configuration of humans under a Bayesian MAP framework. Then, appearance models and segmentations are simultaneously estimated in an iterative sampling-expectation paradigm. Each human appearance is represented by a nonparametric kernel density estimator in a joint spatial-color space and a recursive probability update scheme is employed for soft segmentation at each iteration. Additionally, an automatic occlusion reasoning method is used to determine the layered occlusion status between humans. The approach is evaluated on a number of images and videos, and also applied to human appearance matching using a symmetric distance measure derived from the Kullback-Leiber divergence.

Something that is interesting is interesting then: Using text minig and visualizations to aid interpreting repetition in Gertrude Stein’s The Making of Americans - Clement,T.; Don,A.; Plaisant, Catherine; Auvil,L.; Pape,G.; Goren,V. (Proceedings of the Digital Humanities Conference, 2007)

SplicePort--An interactive splice-site analysis tool - Dogan,R. I; Getoor, Lise; Wilbur,W. J; Mount, Stephen M. (Nucleic Acids Research, 2007)
SplicePort is a web-based tool for splice-site analysis that allows the user to make splice-site predictions for submitted sequences. In addition, the user can also browse the rich catalog of features that underlies these predictions, and which we have found capable of providing high classification accuracy on human splice sites. Feature selection is optimized for human splice sites, but the selected features are likely to be predictive for other mammals as well. With our interactive feature browsing and visualization tool, the user can view and explore subsets of features used in splice-site prediction (either the features that account for the classification of a specific input sequence or the complete collection of features). Selected feature sets can be searched, ranked or displayed easily. The user can group features into clusters and frequency plot WebLogos can be generated for each cluster. The user can browse the identified clusters and their contributing elements, looking for new interesting signals, or can validate previously observed signals. The SplicePort web server can be accessed at http://www.cs.umd.edu/projects/SplicePort and http://www.spliceport.org.

Structural Footprinting in Protein Structure Comparison: The Impact of Structural Fragments - Zotenko,Elena; Dogan,Rezarta Islamaj; Wilbur,W. John; O'Leary, Dianne P.; Przytycka,Teresa M. (BMC Structural Biology, 2007)
Abstract Background One approach for speeding-up protein structure comparison is the projection approach, where a protein structure is mapped to a high-dimensional vector and structural similarity is approximated by distance between the corresponding vectors. Structural footprinting methods are projection methods that employ the same general technique to produce the mapping: first select a representative set of structural fragments as models and then map a protein structure to a vector in which each dimension corresponds to a particular model and "counts" the number of times the model appears in the structure. The main difference between any two structural footprinting methods is in the set of models they use; in fact a large number of methods can be generated by varying the type of structural fragments used and the amount of detail in their representation. How do these choices affect the ability of the method to detect various types of structural similarity? Results To answer this question we benchmarked three structural footprinting methods that vary significantly in their selection of models against the CATH database. In the first set of experiments we compared the methods' ability to detect structural similarity characteristic of evolutionarily related structures, i.e., structures within the same CATH superfamily. In the second set of experiments we tested the methods' agreement with the boundaries imposed by classification groups at the Class, Architecture, and Fold levels of the CATH hierarchy. Conclusion In both experiments we found that the method which uses secondary structure information has the best performance on average, but no one method performs consistently the best across all groups at a given classification level. We also found that combining the methods' outputs significantly improves the performance. Moreover, our new techniques to measure and visualize the methods' agreement with the CATH hierarchy, including the threshholded affinity graph, are useful beyond this work. In particular, they can be used to expose a similar composition of different classification groups in terms of structural fragments used by the method and thus provide an alternative demonstration of the continuous nature of the protein structure universe.

Supporting elementary-age children's searching and browsing: Design and evaluation using the international children's digital library - Hutchinson,H.B.; Druin, Allison; Bederson, Benjamin B. (Journal of the American Society for Information Science and Technology, 2007)

Surface Segmentation through Concentrated Curvature - Mesmoudi,M. M.; Danovaro,E.; De Floriani, Leila; Port,U. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
Curvature is one of the most relevant notions that links the metric properties of a surface to its geometry and to its topology (Gauss-Bonnet theorem). In the literature, a variety of approaches exist to compute curvatures in the discrete case. Several techniques are computationally intensive or suffer from convergence problems. In this paper, we discuss the notion of concentrated curvature, introduced by Troyanov [24]. We discuss properties of this curvature and compare with a widely-used technique that estimates the Gaussian curvatures on a triangulated surface. We apply our STD method [13] for terrain segmentation to segment a surface by using different curvature approaches and we illustrate our comparisons through examples.
Keywords: curvature; convergence; curvatures; concentrated; Gauss-Bonnet; problems; surface; processes; image; segmentation; segmentation; terrain; segmentation; triangulated; surface; Gaussian; theorem; Gaussian

Swarm Intelligence Systems Using Guided Self-Organization for Collective Problem Solving - RodrIGuez,A.; Grushin,A.; Reggia, James A.; HAUPTMAN,AMI; SIPPER,M.; PAN,Z.; Reggia, James A.; GAO,D.; DARABOS,C.; GIACOBINI,M.; others (Advances in Complex Systems, 2007)

Task scheduling in large camera networks - Lim,S.N.; Davis, Larry S.; Mittal,A. (Computer Vision–ACCV 2007, 2007)
Visibility in architectural layouts affects humannavigation, so a suitable representation of visibility context is useful in understanding human activity. Motivated by studies of spatial behavior, we use a set of features from visibility analysis to represent spatial context in the interpretation of human activity. An agent’s goal, belief about the world, trajectory and visible layout are considered to be random variables that evolve with time during the agent’s movement, and are modeled in a Bayesian framework. We design a search-based task in a sprite-world, and compare the results of our framework to those of human subject experiments. Our findings confirm that knowledge of spatial layout improves human interpretations of the trajectories (implying that visibility context is useful in this task). Since our framework demonstrates performance close to that of human subjects with knowledge of spatial layout, our findings confirm that our model makes adequate use of visibility context. In addition, the representation we use for visibility context allows our model to generalize well when presented with new scenes.

Task-based evaluation of text summarization using Relevance Prediction - Hobson,Stacy President; Dorr, Bonnie J; Monz,Christof; Schwartz,Richard (Information Processing & Management, 2007)
This article introduces a new task-based evaluation measure called Relevance Prediction that is a more intuitive measure of an individual’s performance on a real-world task than interannotator agreement. Relevance Prediction parallels what a user does in the real world task of browsing a set of documents using standard search tools, i.e., the user judges relevance based on a short summary and then that same user—not an independent user—decides whether to open (and judge) the corresponding document. This measure is shown to be a more reliable measure of task performance than LDC Agreement, a current gold-standard based measure used in the summarization evaluation community. Our goal is to provide a stable framework within which developers of new automatic measures may make stronger statistical statements about the effectiveness of their measures in predicting summary usefulness. We demonstrate—as a proof-of-concept methodology for automatic metric developers—that a current automatic evaluation measure has a better correlation with Relevance Prediction than with LDC Agreement and that the significance level for detected differences is higher for the former than for the latter.
Keywords: Relevance prediction; Summarization evaluation; Summary usefulness

A taxonomy for medical image registration acceleration techniques - Plishker,W.; Dandekar,O.; Bhattacharyya, Shuvra S.; Shekhar,R. (Life Science Systems and Applications Workshop, 2007. LISA 2007. IEEE/NIH, 2007)

A theoretical model of children's storytelling using physically-oriented technologies (SPOT) - Guha,M.L.; Druin, Allison; Montemayor,J.; Chipman,G.; Farber,A. (Journal of Educational Multimedia and Hypermedia, 2007)

Topological Decompositions for 3D Non-manifold Simplicial Shapes - Hui,Annie; De Floriani, Leila (Department of Computer Science, University of Maryland, College Park, 2007)
Modeling and understanding complex non-manifold shapes is a key issue in several applications including form-feature identification in CAD/CAE, and shape recognition for Web searching. Geometric shapes are commonly discretized as simplicial 2- or 3-complexes embedded in the 3D Euclidean space. The topological structure of a non-manifold simplicial shape can be analyzed through its decomposition into a collection of components with simpler topology. The granularity of the decomposition depends on the combinatorial complexity of the components. In this paper, we present topological tools for structural analysis of three-dimensional non-manifold shapes. This analysis is based on a topological decomposition at two different levels. We discuss the topological properties of the components at each level, and we present algorithms for computing such decompositions. We investigate the relations among the components, and propose a graph-based representation for such relations.
Keywords: Technical Report

Towards a heterogeneous medical image registration acceleration platform - Plishker,W.; Dandekar,O.; Bhattacharyya, Shuvra S.; Shekhar,R. (Biomedical Circuits and Systems Conference, 2007. BIOCAS 2007. IEEE, 2007)

Towards a semantic web system for understanding real world representations - Papaleo,L.; De Floriani, Leila; Hendler,J.; Hui,A. (Proceedings of the Tenth International Conference on Computer Graphics and Artificial Intelligence, 2007)
As the volume of multimedia content available on the Web continues to increase, there is a clearneed for more advanced techniques for effective retrieval and management of such data. In this context, we see a growing interest in exploiting the potential of the Semantic Web in different research fields. But, on the other hand, there is a general lack of tools able to analyse, organize and understand digital shape models (especially 3D models) for easily populating repositories with complete and well-detailed metadata. Several steps are necessary to create and associate semantics with a shape and some of them are clearly context-dependent. In this paper, we present the design details of our new system, that we call be-SMART, for inspecting digital 3D shapes by extracting geometrical and topological information from them and for structuring and annotating these shapes using ontology-driven metadata. In particular, we describe the general structure of the system, the different modules and their mutual relations. We then concentrate on the first two modules of the system showing how the 3D models are annotated following ontology-driven metadata. We also provide motivations for further work in developing new techniques for both annotating and managing 3D models on the Web.

TREC 2007 ciQA Task: University of Maryland - Madnani,N.; Jimmy Lin; Dorr, Bonnie J (Proceedings of TREC, 2007)

A two-level topological decomposition for non-manifold simplicial shapes - Hui,Annie; De Floriani, Leila (Proceedings of the 2007 ACM symposium on Solid and physical modeling, 2007)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis. Geometric shapes are commonly discretized as two- or three-dimensional simplicial complexes embedded in the 3D Euclidean space. The topological structure of a nonmanifold simplicial shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we present a topological decomposition of a shape at two different levels, with different degrees of granularity. We discuss the topological properties of the components at each level, and we present algorithms for computing such decompositions. We investigate the relations among the components, and propose a graph-based representation for such relations.
Keywords: Non-manifold modeling; shape decomposition; shape modeling; simplicial complexes

A unified model explaining the offsets of overlapping and near-overlapping prokaryotic genes - Kingsford, Carl; Delcher,A. L; Salzberg,S. L (Molecular biology and evolution, 2007)

Using multiresolution learning for transfer in image classification - Eaton,Eric; desJardins, Marie; Stevenson,John (Proceedings of the 22nd national conference on Artificial intelligence - Volume 2, 2007)
Our work explores the transfer of knowledge at multiple levels of abstraction to improve learning. By exploiting the similarities between objects at various levels of detail, multiresolution learning can facilitate transfer between image classification tasks.We extract features from images at multiple levels of resolution, then use these features to create models at different resolutions. Upon receiving a new task, the closest-matching stored model can be generalized (adapted to the appropriate resolution) and transferred to the new task.

Using paraphrases for parameter tuning in statistical machine translation - Madnani,Nitin; Ayan,Necip Fazil; Resnik, Philip; Dorr, Bonnie J (Proceedings of the Second Workshop on Statistical Machine Translation, 2007)
Most state-of-the-art statistical machine translation systems use log-linear models, which are defined in terms of hypothesis features and weights for those features. It is standard to tune the feature weights in order to maximize a translation quality metric, using held-out test sentences and their corresponding reference translations. However, obtaining reference translations is expensive. In this paper, we introduce a new full-sentence paraphrase technique, based on English-to-English decoding with an MT system, and we demonstrate that the resulting paraphrases can be used to drastically reduce the number of human reference translations needed for parameter tuning, without a significant decrease in translation quality.

Using paraphrases for parameter tuning in statistical machine translation - Madnani,N.; Ayan,N.F.; Resnik, Philip; Dorr, Bonnie J (Proceedings of the Second Workshop on Statistical Machine Translation, 2007)

3D structure recovery and unwarping of surfaces applicable to planes - Gumerov, Nail A.; Zandifar,A.; Duraiswami, Ramani; Davis, Larry S. (International journal of computer vision, 2006)
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.

3d surface reconstruction using graph cuts with surface constraints - Tran,S.; Davis, Larry S. (Computer Vision–ECCV 2006, 2006)
We describe a graph cut algorithm to recover the 3D object surface using both silhouette and foreground color information. The graph cut algorithm is used for optimization on a color consistency field. Constraints are added to improve its performance. These constraints are a set of predetermined locations that the true surface of the object is likely to pass through. They are used to preserve protrusions and to pursue concavities respectively in the first and the second phase of the algorithm. We also introduce a method for dealing with silhouette uncertainties arising from background subtraction on real data. We test the approach on synthetic data with different numbers of views (8, 16, 32, 64) and on a real image set containing 30 views of a toy squirrel.

Adaptive Transformation-based Learning for Improving Dictionary Tagging - Karagol-Ayan,Burcu; Doermann, David; Weinberg, Amy (Proceedings of the 11th Conference on European Chapter of the Association for Computational Linguistics, 2006)
We present an adaptive technique that enables users to produce a high quality dictionary parsed into its lexicographic components (headwords, parts of speech, translations, etc.) using an extremely small amount of user provided training data. We use transformation-based learning (TBL) as a postprocessor at two points in the system to improve performance. The results show that the tagging accuracy is increased from 83% and 91% to 93% and 94% for individual words or tokens , and from 64% and 83% to 90% and 93% for contiguous phrases such as definitions or examples of usage.

ANew Algorithm for Detecting Text Line in Handwritten Documents - Li,Yi; Yefeng Zheng; David Doermann; Jaeger,Stefan (10th International Workshop on Frontiers in Handwriting Recognition, 2006)
Curvilinear text line detection and segmentation in handwritten documents is a significant challenge for handwriting recognition. Given no prior knowledge of script, we model text line detection as an image segmentation problem by enhancing text line structure using a Gaussian window, and adopting the level set method to evolve text line boundaries. Experiments show that the proposed method achieves high accuracy for detecting text lines in both handwritten and machine printed documents with many scripts.

Annotation compatibility working group report - Meyers,A.; Fang,A. C.; Ferro,L.; Kübler,S.; Jia-Lin,T.; Palmer,M.; Poesio,M.; Dolbey,A.; Schuler,K. K.; Loper,E.; Zinsmeister,H.; Penn,G.; et al. (Proceedings of the Workshop on Frontiers in Linguistically Annotated Corpora 2006, 2006)
This report explores the question of compatibility between annotation projects including translating annotation formalisms to each other or to common forms. Compatibility issues are crucial for systems that use the results of multiple annotation projects. We hope that this report will begin a concerted effort in the field to track the compatibility of annotation schemes for part of speech tagging, time annotation, treebanking, role labeling and other phenomena.

Appearance-based person recognition using color/path-length profile - Yoon,K.; Harwood,D.; Davis, Larry S. (Journal of Visual Communication and Image Representation, 2006)

Approximate Data Collection in Sensor Networks using Probabilistic Models - Chu,D.; Deshpande, Amol; Hellerstein,J. M; Wei Hong (Proceedings of the 22nd International Conference on Data Engineering, 2006. ICDE '06, 2006)
Wireless sensor networks are proving to be useful in a variety of settings. A core challenge in these networks is to minimize energy consumption. Prior database research has proposed to achieve this by pushing data-reducing operators like aggregation and selection down into the network. This approach has proven unpopular with early adopters of sensor network technology, who typically want to extract complete "dumps" of the sensor readings, i.e., to run "SELECT *" queries. Unfortunately, because these queries do no data reduction, they consume significant energy in current sensornet query processors. In this paper we attack the "SELECT " problem for sensor networks. We propose a robust approximate technique called Ken that uses replicated dynamic probabilistic models to minimize communication from sensor nodes to the network’s PC base station. In addition to data collection, we show that Ken is well suited to anomaly- and event-detection applications. A key challenge in this work is to intelligently exploit spatial correlations across sensor nodes without imposing undue sensor-to-sensor communication burdens to maintain the models. Using traces from two real-world sensor network deployments, we demonstrate that relatively simple models can provide significant communication (and hence energy) savings without undue sacrifice in result quality or frequency. Choosing optimally among even our simple models is NPhard, but our experiments show that a greedy heuristic performs nearly as well as an exhaustive algorithm.
Keywords: Batteries; Biological system modeling; Biosensors; data mining; Databases; Energy consumption; Intelligent networks; Intelligent sensors; Robustness; Wireless sensor networks

ARobust Stamp Detection Framework on Degraded Documents - Zhu,Guangyu; Jaeger,Stefan; David Doermann (International Conference on Document Recognition and Retrieval XIII, 2006)
In this paper, we present a novel stamp detection framework based on parameter estimation of connected edge features. Using robust basic shape detectors, the approach is effective for stamps with analytically shaped contours. For elliptic/circular stamps, it efficiently makes use of the orientation information from pairs of edge points to determine its center position and area without computing all the five parameters of ellipse. When linking connected edges, we introduce an effective template-based junction removal technique to specifically address the problem that stamps often spatially overlap with background contents. These give our approach significant advantage in terms of computation complexity over traditional Hough transform methods. Experimental results on real degraded documents demonstrated the robustness of this retrieval approach on large document database, which consists of both printed text and handwritten notes. This enables us to reliably retrieve documents from a specific source by detecting its official stamps with analytically-shape contours when only limited samples are available.

Automatic identification of confusable drug names - Kondrak,Grzegorz; Dorr, Bonnie J (Artificial Intelligence in Medicine, 2006)
SummaryObjectiveMany hundreds of drugs have names that either look or sound so much alike that doctors, nurses and pharmacists can get them confused, dispensing the wrong one in errors that can injure or even kill patients. Methods and material We propose to address the problem through the application of two new methods—one based on orthographic similarity (“look-alike”), and the other based on phonetic similarity (“sound-alike”). In order to compare the effectiveness of the new methods for identifying confusable drug names with other known similarity measures, we developed a novel evaluation methodology. Results We show that the new orthographic measure (BI-SIM) outperforms other commonly used measures of similarity on a set containing both look-alike and sound-alike pairs, and that a new feature-based phonetic approach (ALINE) outperforms orthographic approaches on a test set containing solely sound-alike pairs. However, an approach that combines several different measures achieves the best results on two test sets. Conclusion Our system is currently used as the basis of a system developed for the U.S. Food and Drug Administration for detection of confusable drug names.
Keywords: Drug names; Evaluation methodology; Lexical similarity; Medical errors

Ballistic hand movements - Prasad,V.; Kellokumpu,V.; Davis, Larry S. (Articulated Motion and Deformable Objects, 2006)
Common movements like reaching, striking, etc. observed during surveillance have highly variable target locations. This puts appearance-based techniques at a disadvantage for modelling and recognizing them. Psychological studies indicate that these actions are ballistic in nature. Their trajectories have simple structures and are determined to a great degree by the starting and ending positions. We present an approach for movement recognition that explicitly considers their ballistic nature. This enables the decoupling of recognition from the movement’s trajectory, allowing generalization over a range of target-positions. A given movement is first analyzed to determine if it is ballistic. Ballistic movements are further classified into reaching, striking, etc. The proposed approach was tested with motion capture data obtained from the CMU MoCap database.

A Bayesian model for supervised clustering with the Dirichlet process prior - Daumé, Hal; Marcu,D. (Journal of Machine Learning Research, 2006)

Bayesian query-focused summarization - Daumé, Hal; Marcu,Daniel (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
We present BAYESUM (for "Bayesian summarization"), a model for sentence extraction in query-focused summarization. BAYESUM leverages the common case in which multiple documents are relevant to a single query. Using these documents as reinforcement for query terms, BAYESUM is not afflicted by the paucity of information in short queries. We show that approximate inference in BAYESUM is possible on large data sets and results in a state-of-the-art summarization system. Furthermore, we show how BAYESUM can be understood as a justified query expansion technique in the language modeling for IR framework.

Camera-Based Document Image Mosaicing - Liang,Jian; DeMenthon,Daniel; David Doermann (ICPR'06, 2006)
In this paper we present an image mosaicing method for camera-captured document images. Our method is unique in not restricting the camera position, thus allowing greater flexibility than scanner-based or fixed-camera-based approaches. To accommodate for the perspective distortions introduced by varying poses, we implement a two-step image registration process that relies on accurately computing the projectivity between any two document images with an overlapping area as small as 10%. In the overlapping area, we apply a sharpness based selection process to obtain seamless blending across the border and within. Experiments show that our approach can produce a very sharp, high resolution and accurate full page mosaic from small image patches of a document.

Can DNS-based blacklists keep up with bots - Ramachandran,A.; Dagon,D.; Feamster, Nick (Conference on email and anti-spam, 2006)

Capture and rendering of spatial sound over headphones - Duraiswami, Ramani; Zotkin,Dmitry N; O'donovan,Adam (The Journal of the Acoustical Society of America, 2006)
A theory for capturing an audio scene and then rendering it remotely over headphones is developed. The method relies on capture of a sound field up to a certain order in terms of spherical wave functions. Then, the captured sound field is convolved with the head‐related transfer function and rendered to provide presence in the auditory scene. The sound‐field representation is then transmitted to a remote location for immediate rendering or stored for later use. A system that implements the capture using a spherical array is developed and tested. Head‐related transfer functions are measured using the system described in [D.N. Zotkin et al., J. Acoustic. Soc. Am. (to appear)]. The sound renderer, coupled with the head tracker, reconstructs the acoustic field using individualized head‐related transfer functions to preserve the perceptual spatial structure of the audio scene. [Work partially supported by VA.]

A case study of tangible flags: a collaborative technology to enhance field trips - Chipman,G.; Druin, Allison; Beer,D.; Fails,J. A; Guha,M.L.; Simms,S. (Proceedings of the 2006 conference on Interaction design and children, 2006)

Challenges in building an Arabic-English GHMT system with SMT components - Habash,N.; Dorr, Bonnie J; Monz,C. (Proceedings of the 11th Annual Conference of the European Association for Machine Translation (EAMT-2006), 2006)
The research context of this paper is de-veloping hybrid machine translation (MT) systems that exploit the advantages of linguistic rule-based and statistical MT systems. Arabic, as a morphologically rich language, is especially challenging even without addressing the hybridiza- tion question. In this paper, we describe the challenges in building an Arabic- English generation-heavy machine trans- lation (GHMT) system and boosting it with statistical machine translation (SMT) components. We present an extensive evaluation of multiple system variants and report positive results on the advantages of hybridization.

Combination can be hard: Approximability of the unique coverage problem - Demaine,E. D; Hajiaghayi, Mohammad T.; Feige,U.; Salavatipour,M. R (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

Conservation Patterns in cis-Elements Reveal Compensatory Mutations - Evans,Perry; Donahue,Greg; Hannenhalli, Sridhar (Comparative GenomicsComparative Genomics, 2006)
Transcriptional regulation critically depends on proper interactions between transcription factors (TF) and their cognate DNA binding sites or cis elements. A better understanding and modelling of the TF-DNA interaction is an important area of research. The Positional Weight Matrix (PWM) is the most common model of TF-DNA binding and it presumes that the nucleotide preferences at individual positions within the binding site are independent. However, studies have shown that this independence assumption does not always hold. If the nucleotide preference at one position depends on the nucleotide at another position, a chance mutation at one position should exert selection pressures at the other position. By comparing the patterns of evolutionary conservation at individual positions within cis elements, here we show that positional dependence within binding sites is highly prevalent. We also show that dependent positions are more likely to be functional, as evidenced by a higher information content and higher conservation. We discuss two examples—Elk-1 and SAP-1 where the inferred compensatory mutation is consistent with known TF-DNA crystal structure.

Constraint Integration for Multiview Pose Estimation of Humans with Self-Occlusions - Gupta,A.; Mittal,A.; Davis, Larry S. (3D Data Processing, Visualization, and Transmission, Third International Symposium on, 2006)
Detection of articulated objects such as humans is an important task in computer vision. We present a system that incorporates a variety of constraints in a unified multi- view framework to automatically detect humans in possibly crowded scenes. These constraints include the kinematic constraints, the occlusion of one part by another and the high correlation between the appearance of parts such as the two arms. The graphical structure (non-tree) obtained is optimized in a nonparametric belief propagation framework using prior based search.
Keywords: articulated; belief; constraint; multiview; detection; computer; detection; pose; estimation; estimation; nonparametric; framework; self-occlusion; computer; graphics; computer; method; graphical; methods; object; object; pose; propagation; structure; kinematic; vision; correlation

Constructing task visibility intervals for video surveillance - Lim,S.N.; Davis, Larry S.; Mittal,A. (Multimedia systems, 2006)
Vision systems are increasingly being deployed to perform complex surveillance tasks. While improved algorithms are being developed to perform these tasks, it is also important that data suitable for these algorithms be acquired – a non-trivial task in a dynamic and crowded scene viewed by multiple PTZ cameras. In this paper, we describe a real-time multi-camera system that collects images and videos of moving objects in such scenes, subject to task constraints. The system constructs “task visibility intervals” that contain information about what can be sensed in future time intervals. Constructing these intervals requires prediction of future object motion and consideration of several factors such as object occlusion and camera control parameters. Such intervals can also be combined to form multi-task intervals, during which a single camera can collect videos suitable for multiple tasks simultaneously. Experimental results are provided to illustrate the system capabilities in constructing such task visibility intervals, followed by scheduling them using a greedy algorithm.

Content-based search techniques for searching CAD databases - Gupta, Satyandra K.; Cardone, Antonio; Deshmukh,A. (CAD Conference, 2006)
The popularity of 3D CAD systems is resulting in large assembly and part databases being createdby product development organizations. Over the last few years several content-based techniques have emerged to search these databases. Ability to perform content-based searches on CAD databases is expected to help the designers and manufacturing engineers in many different ways. Representative examples include part-family formation, redesign suggestion generation, supplier selection, cost estimation, tooling design, machine selection, stock selection, and design reuse. This paper covers the following three topics. First, it presents an overview of different types of part search techniques. Second, it presents an overview of the different aspects of assembly search techniques. Finally, it identifies the open challenges in these areas and outlines future research directions.

Cross-Language Access to Recorded Speech in the MALACH Project - Oard, Douglas; Demner-Fushman,Dina; Hajič,Jan; Ramabhadran,Bhuvana; Gustman,Samuel; Byrne,William; Soergel,Dagobert; Dorr, Bonnie J; Resnik, Philip; Picheny,Michael (Text, Speech and DialogueText, Speech and Dialogue, 2006)
The MALACH project seeks to help users find information in a vast multilingual collections of untranscribed oral history interviews. This paper introduces the goals of the project and focuses on supporting access by users who are unfamiliar with the interview language. It begins with a review of the state of the art in crosslanguage speech retrieval; approaches that will be investigated in the project are then described. Czech was selected as the first non-English language to be supported, so results of an initial experiment with Czech/English cross-language retrieval are reported.

Data redistribution and remote method invocation for coupled components - Bertrand,Felipe; Bramley,Randall; Bernholdt,David E.; Kohl,James A.; Sussman, Alan; Larson,Jay W.; Damevski,Kostadin B. (Journal of Parallel and Distributed Computing, 2006)
With the increasing availability of high-performance massively parallel computer systems, the prevalence of sophisticated scientific simulation has grown rapidly. The complexity of the scientific models being simulated has also evolved, leading to a variety of coupled multi-physics simulation codes. Such cooperating parallel programs require fundamentally new interaction capabilities, to efficiently exchange parallel data structures and collectively invoke methods across programs. So-called “ M × N ” research, as part of the common component architecture (CCA) effort, addresses these special and challenging needs, to provide generalized interfaces and tools that support flexible parallel data redistribution and parallel remote method invocation. Using this technology, distinct simulation codes with disparate distributed data decompositions can work together to achieve greater scientific discoveries.
Keywords: Common component architecture; Model coupling; Parallel data redistribution; Parallel remote method invocation

A decomposition-based representation for 3D simplicial complexes - Hui,Annie; Vaczlavik,Lucas; De Floriani, Leila (Proceedings of the fourth Eurographics symposium on Geometry processing, 2006)
We define a new representation for non-manifold 3D shapes described by three-dimensional simplicial complexes, that we call the Double-Level Decomposition (DLD) data structure. The DLD data structure is based on a unique decomposition of the simplicial complex into nearly manifold parts, and encodes the decomposition in an efficient and powerful two-level representation. It is compact, and it supports efficient topological navigation through adjacencies. It also provides a suitable basis for geometric reasoning on non-manifold shapes. We describe an algorithm to decompose a 3D simplicial complex into nearly manifold parts. We discuss how to build the DLD data structure from a description of a 3D complex as a collection of tetrahedra, dangling triangles and wire edges, and we present algorithms for topological navigation. We present a thorough comparison with existing representations for 3D simplicial complexes.

Deformation and viewpoint invariant color histograms - Domke, J.; Aloimonos, J. (British Machine Vision Conference, 2006)

Density estimation using mixtures of mixtures of Gaussians - Abd-Almageed, Wael; Davis, Larry S. (Computer Vision–ECCV 2006, 2006)
In this paper we present a new density estimation algorithm using mixtures of mixtures of Gaussians. The new algorithm overcomes the limitations of the popular Expectation Maximization algorithm. The paper first introduces a new model selection criterion called the Penalty-less Information Criterion, which is based on the Jensen-Shannon divergence. Mean-shift is used to automatically initialize the means and covariances of the Expectation Maximization in order to obtain better structure inference. Finally, a locally linear search is performed using the Penalty-less Information Criterion in order to infer the underlying density of the data. The validity of the algorithm is verified using real color images.

Detecting Text Line in Handwritten Documents - Li,Yi; Yefeng Zheng; David Doermann (ICPR'06, 2006)
Although detecting text lines in machine printed documents is typically considered as a solved problem, it is still a challenge to segment handwritten text lines in the general sense given no prior knowledge of scrip. This paper models text line detection as an image segmentation problem by enhancing text line structure using a Gaussian window, and adopting the level set method to evolve text line boundaries. Experiments show that the method, which is script independent, achieves high accuracy for detecting text lines in both handwritten and machine printed documents.

Detection and analysis of hair - Yacoob,Yaser; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2006)
We develop computational models for measuring hair appearance for comparing different people. The models and methods developed have applications to person recognition and image indexing. An automatic hair detection algorithm is described and results reported. A multidimensional representation of hair appearance is presented and computational algorithms are described. Results on a data set of 524 subjects are reported. Identification of people using hair attributes is compared to eigenface-based recognition along with a joint, eigenface-hair-based identification
Keywords: analysis; hair; appearance; image; AUTOMATIC; detection; detection; hair; extraction; image; hair; indexing; multidimensional; recognition; face; recognition; feature; representation; object; representation; person

A Dimension-Independent Representation for Multiresolution Nonmanifold Meshes - De Floriani, Leila; Hui,Annie (Journal of Computing and Information Science in Engineering, 2006)
We consider the problem of representing and manipulating nonmanifold objects of any dimension and at multiple resolutions. We present a modeling scheme based on (1) a multiresolution representation, called the vertex-based nonmanifold multitessellation, (2) a compact and dimension-independent data structure, called the Simplified Incidence Graph (SIG), and (3) an atomic mesh update operator, called vertex-pair contraction/vertex expansion. We propose efficient algorithms for performing the vertex-pair contraction on a simplicial mesh encoded as a SIG, and an effective representation for encoding this multiresolution model based on a compact encoding of vertex-pair contractions and vertex expansions.
Keywords: computational geometry; graph theory; mesh generation

A dimension-independent simplicial data structure for non-manifold shapes - Hui,Annie; De Floriani, Leila (Department of Computer Science, University of Maryland, College Park, 2006)
We consider the problem of representing and manipulating non-manifoldmulti-dimensional shapes, discretized as $d$-dimensional simplicial Euclidean complexes, for modeling finite element meshes derived from CAD models. We propose a dimension-independent data structure for simplicial complexes, that we call the {\em Incidence Simplicial (IS)} data structure. The IS data structure is scalable to manifold complexes, and supports efficient traversal and update algorithms for performing topological modifications, such as hole removal or dimension reduction. It has the same expressive power and performances as the incidence graph, commonly used for dimension-independent representation of simplicial and cell complexes, but it is much more compact. We present efficient algorithms for traversing, generating and updating a simplicial complex described as an IS data structure. We compare the IS data structure with dimension-independent and dimension-specific representations for simplicial complexes. Finally, we briefly discuss two applications that the IS data structure supports, namely decomposition of non-manifold objects for effective geometric reasoning, and multi-resolution modeling of non-manifold multi-dimensional shapes.
Keywords: Technical Report

Dissemination of compressed historical information in sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (The VLDB JournalThe VLDB Journal, 2006)

DOCLIB: a Software Library for Document Processing - Jaeger,Stefan; Zhu,Guangyu; David Doermann; Chen,Kevin; Sampat,Summit (International Conference on Document Recognition and Retrieval XIII, 2006)
Most researchers would agree that research in the field of document processing can benefit tremendously from a common software library through which institutions are able to develop and share research-related software and applications across academic, business, and government domains. However, despite several attempts in the past, the research community still lacks a widely-accepted standard software library for document processing. This paper describes a new library called DOCLIB, which tries to overcome the drawbacks of earlier approaches. Many of DOCLIB’s features are unique either in themselves or in their combination with others, e.g. the factory concept for support of different image types, the juxtaposition of image data and metadata, or the add-on mechanism. We cherish the hope that DOCLIB serves the needs of researchers better than previous approaches and will readily be accepted by a larger group of scientists.

Domain adaptation for statistical classifiers - Daumé, Hal; Marcu,D. (Journal of Artificial Intelligence Research, 2006)

Dwarf cube architecture for reducing storage sizes of multidimensional data - Roussopoulos, Nick; Sismanis,John; Deligiannakis,Antonios (2006)
The invention relates to data warehouses and the ability to create and maintain data cubes of multi-dimensional data. More specifically, the invention pertains to data cube architectures that permit significant reduction of storage, exhibit very efficient retrieval and provide a very efficient incremental update of the data cubes.

Edge affinity for pose-contour matching - Prasad,V. S.N; Davis, Larry S.; Tran,Son Dinh; Elgammal,Ahmed (Computer Vision and Image Understanding, 2006)
We present an approach for whole-body pose-contour matching. Contour matching in natural images in the absence of foreground–background segmentation is difficult. Usually an asymmetric approach is adopted, where a contour is said to match well if it aligns with a subset of the image’s gradients. This leads to problems as the contour can match with a portion of an object’s outline and ignore the remainder. We present a model for using edge continuity to address this issue. Pairs of edge elements in the image are linked with affinities if they are likely to belong to the same object. A contour that matches with a set of image gradients is constrained to also match with other gradients having high affinities with the chosen ones. Experimental results show that this improves matching performance.
Keywords: Contour matching; Edge continuity

Efficient computation of 3-D acoustical scattering from multiple arbitrarily shaped objects using the boundary element method/fast multipole method (BEM/FMM) - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2006)
Many applications require computation of acoustic fields in systems consisting of a large number of scatterers, which may have complex shape. Despite the boundary element method being a well‐known technique for solution of the boundary value problems for the Helmholtz equation, its capabilities are usually limited by the memory and speed of computers, and conventional methods can be applicable to relatively small (up to order of 10 000 boundary elements) problems. We developed and implemented an efficient computational technique, based on an iterative solver employing generalized minimal residual method in combination with matrix‐vector multiplication speeded up with the fast multipole method. We demonstrate that this technique has O(N) memory and computational complexity and enables solution of problems with thousands of scatterers (millions of boundary elements) on a desktop PC. The test problems solved are of moderate frequency (up to kD≤150, where k is the wavenumber and D is the size of the computational domain). Solution of large scale scattering problems was tested by comparison with the FMM‐based T‐matrix method applicable for simple shape objects reported earlier [Gumerov and Duraiswami, J. Acoust. Soc. Am., 117(4), 1744–1761 (2005)], visualization, and physical interpretation of the results.

Employing the hand as an interface device - Sepehri,A.; Yacoob,Yaser; Davis, Larry S. (Journal of Multimedia, 2006)

Employing the Hand as an Interface Device - Sepehri,Afshin; Yacoob,Yaser; Davis, Larry S. (Journal of Multimedia, 2006)
We propose algorithms and applications for using the hand as an interface device in virtual and physical spaces. In virtual drawing, by tracking the hand in 3-D and estimating a virtual plane in space, the intended drawing of user is recognized. In a virtual marble game, the instantaneous orientation of the hand is simulated to render a graphical scene of the game board. Real-time visual feedback allows the user to navigate a virtual ball in a maze. In 3-D model construction, the system tracks the hand motion in space while the user is traversing edges of a physical object. The object is then rendered virtually by the computer. These applications involve estimating the 3-D absolute position and/or orientation of the hand in space. We propose parametric modelling of the central region of the hand to extract this information. A stereo camera is used to first build a preliminary disparity map of the hand. Then, the best fitting plane to the disparity points is computed using robust estimation. The 3-D hand plane is calculated based on the disparity plane and the position and orientation parameters of the hand. Tracking the hand region over a sequence of frames and coping with noise using robust modelling of the hand motion enables estimating the trajectory of the hand in space. The algorithms are real-time and experiments are presented to demonstrate the proposed applications of using the hand as an interface device.

Estimation of Anthropomeasures from a Single Calibrated Camera - BenAbdelkader,C.; Davis, Larry S. (Automatic Face and Gesture Recognition, 2006. FGR 2006. 7th International Conference on, 2006)
We are interested in the recovery of anthropometric dimensions of the human body from calibrated monocular sequences, and their use in multi-target tracking across multiple cameras and identification of individual people. In this paper, we focus on two specific anthropomeasures that are relatively easy to estimate from low-resolution images: stature and shoulder breadth. Precise average estimates are obtained for each anthropomeasure by combining measurements from multiple frames in the sequence. Our contribution is two-fold: (i) a novel technique for automatic and passive estimation of shoulder breadth, that is based on modelling the shoulders as an ellipse, and (U) a novel method for increasing the accuracy of the mean estimates of both anthropomeasures. The latter is based on the observation that major sources of error in the measurements are landmark localization the 2D image and 3D modelling error, and that both of these are correlated with gait phase and body orientation with respect to the camera. Consequently, estimation error can be significantly reduced via appropriate selection or control of these two variables
Keywords: anthropomeasures; calibrated; camera; anthropometry; error; estimation; error; estimation; gait; identification; image; phase; image; recovery; image; resolution; image; resolution; monocular; restoration; image; sensors; image; sequences; sequences; single; statistics; image

Evaluation of Multilingual and Multi-modal Information Retrieval-Seventh Workshop of the Cross-Language Evaluation Forum, CLEF 2006, Alicante, Spain, September 19-21, 2006, Revised Selected Papers - Peters,C.; Clough,P.; Gey,F.; Karlgren,J.; Magnini,B.; Oard, Douglas; De Rijke,M.; Stempfhuber,M. (Seventh Workshop of the Cross-Language Evaluation Forum, CLEF 2006, 2006)

The evolution of the international children's digital library searching and browsing interface - Hutchinson,H.B.; Bederson, Benjamin B.; Druin, Allison (Proceedings of the 2006 conference on Interaction design and children, 2006)

Exploiting independence for branch operations in Bayesian learning of C&RTs - Angelopoulos,N.; Cussens,J.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
In this paper we extend a methodology for Bayesian learning via MCMC, with the ability to grow arbitrarily long branches in C&RT models. We are able to do so by exploiting independence in the model construction process. The ability to grow branches rather than single nodes has been noted as desirable in the literature. The most singular feature of the underline methodology used here in comparison to other approaches is the coupling of the prior and the proposal. The main contribution of this paper is to show how taking advantage of independence in the coupled process, can allow branch growing and swapping for proposal models.

Exploring the limits of single-iteration clarification dialogs - Jimmy Lin; Wu,Philip; Demner-Fushman,Dina; Abels,Eileen (Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, 2006)
Single-iteration clarification dialogs, as implemented in the TREC HARD track, represent an attempt to introduce interaction into ad hoc retrieval, while preserving the many benefits of large-scale evaluations. Although previous experiments have not conclusively demonstrated performance gains resulting from such interactions, it is unclear whether these findings speak to the nature of clarification dialogs, or simply the limitations of current systems. To probe the limits of such interactions, we employed a human intermediary to formulate clarification questions and exploit user responses. In addition to establishing a plausible upper bound on performance, we were also able to induce an "ontology of clarifications" to characterize human behavior. This ontology, in turn, serves as the input to a regression model that attempts to determine which types of clarification questions are most helpful. Our work can serve to inform the design of interactive systems that initiate user dialogs.
Keywords: interactive retrieval; intermediated search; TREC HARD

Eye of the Beholder: Phone-Based Text-Recognition for the Visually-Impaired - Tudor Dumitras; Lee, M.; Quinones, P.; Smailagic, A.; Siewiorek, Dan; Narasimhan, P. (2006 10th IEEE International Symposium on Wearable Computers, 2006)
Blind and visually-impaired people cannot access essential information in the form of written text in our environment (e.g., on restaurant menus, street signs, door labels, product names and instructions, expiration dates). In this paper, we present and evaluate a mobile text-recognition system capable of extracting written information from a wide variety of sources and communicating it on-demand to the user. The user needs no additional hardware except an ordinary, Internet- enabled mobile camera-phone - a device that many visually-impaired individuals already own. This approach fills a gap in assistive technologies for the visually- impaired because it makes users aware of textual information not available to them through any other means.
Keywords: CAMERAS; data mining; handicapped aids; Hardware; Image quality; Internet; Land mobile radio cellular systems; Mobile computing; mobile handsets; mobile text-recognition system; Optical character recognition software; phone-based text-recognition; Product safety; Text recognition; visually-impaired

Fast head-related transfer function measurement via reciprocity - Zotkin,Dmitry N; Duraiswami, Ramani; Grassi,Elena; Gumerov, Nail A. (The Journal of the Acoustical Society of America, 2006)
An efficient method for head-related transfer function (HRTF) measurement is presented. By applying the acoustical principle of reciprocity, one can swap the speaker and the microphone positions in the traditional (direct) HRTF measurement setup, that is, insert a microspeaker into the subject’s ear and position several microphones around the subject, enabling simultaneous HRTF acquisition at all microphone positions. The setup used for reciprocal HRTF measurement is described, and the obtained HRTFs are compared with the analytical solution for a sound-hard sphere and with KEMAR manikin HRTF obtained by the direct method. The reciprocally measured sphere HRTF agrees well with the analytical solution. The reciprocally measured and the directly measured KEMAR HRTFs are not exactly identical but agree well in spectrum shape and feature positions. To evaluate if the observed differences are significant, an auditory localization model based on work byJ. C. Middlebrooks [J. Acoust. Soc. Am. 92, 2607–2624 (1992) ] was used to predict where a virtual sound source synthesized with the reciprocally measured HRTF would be localized if the directly measured HRTF were used for the localization. It was found that the predicted localization direction generally lies close to the measurement direction, indicating that the HRTFs obtained via the two methods are in good agreement.
Keywords: hearing; Microphones; Transfer functions

Fast multipole method for the biharmonic equation in three dimensions - Gumerov, Nail A.; Duraiswami, Ramani (Journal of Computational Physics, 2006)
The evaluation of sums (matrix–vector products) of the solutions of the three-dimensional biharmonic equation can be accelerated using the fast multipole method, while memory requirements can also be significantly reduced. We develop a complete translation theory for these equations. It is shown that translations of elementary solutions of the biharmonic equation can be achieved by considering the translation of a pair of elementary solutions of the Laplace equations. The extension of the theory to the case of polyharmonic equations in R 3 is also discussed. An efficient way of performing the FMM for biharmonic equations using the solution of a complex valued FMM for the Laplace equation is presented. Compared to previous methods presented for the biharmonic equation our method appears more efficient. The theory is implemented and numerical tests presented that demonstrate the performance of the method for varying problem sizes and accuracy requirements. In our implementation, the FMM for the biharmonic equation is faster than direct matrix–vector product for a matrix size of 550 for a relative L2 accuracy ϵ2 = 10−4, and N = 3550 for ϵ2 = 10−12.

Fast optimal bandwidth selection for kernel density estimation - Raykar,V.C.; Duraiswami, Ramani (Proceedings of the sixth SIAM International Conference on Data Mining, 2006)
We propose a computationally efficient ϵ−exact approxima-tion algorithm for univariate Gaussian kernel based density derivative estimation that reduces the computational com- plexity from O(MN) to linear O(N +M). We apply the pro- cedure to estimate the optimal bandwidth for kernel density estimation. We demonstrate the speedup achieved on this problem using the ”solve-the-equation plug-in” method, and on exploratory projection pursuit techniques.

Find that photo!: interface strategies to annotate, browse, and share - Shneiderman, Ben; Bederson, Benjamin B.; Drucker,Steven M. (Communications of the ACM - Supporting exploratory search, 2006)

First Steps Toward an Electronic Field Guide for Plants - Haibin,Gaurav Agarwal; Agarwal,Gaurav; Ling,Haibin; Jacobs, David W.; Shirdhonkar,Sameer; Kress,W. John; Russell,Rusty; Belhumeur,Peter; Dixit,An; Feiner,Steve; Mahajan,Dhruv; Sunkavalli,Kalyan; et al. (Taxon, 2006)
this paper, we will describe our progress towards building a digital collection of the Smithsonian's type specimens, developing recognition algorithms that can match an image of a leaf to the species of plant from which it comes, and designing user interfaces for interacting with an electronic field guide. To start, we are developing a prototype electronic field guide for the flora of Plummers Island, a small, well-studied island in the Potomac River. This prototype system contains multiple images for each of about 130 species of plants on the island, and should soon grow to cover all 200+ species currently recorded (Shetler et al., 2005). Images of full specimens are available, as well as images of isolated leaves of each species. A zoomable user interface allows a user to browse these images, zooming in on ones of interest. Visual recognition algorithms assist a botanist in locating the specimens that are most relevant to identify the species of a plant. The system currently runs on a small hand-held computer. We will describe the components of this prototype, and also describe some of the future challenges we anticipate if we are to provide botanists in the field with all the resources that are now currently available in the world's museums and herbaria. Type Specimen Digital Collection The first challenge in producing our electronic field guide is to create a digital collection covering all of the Smithsonian's 85,000 vascular plant type specimens. For each type specimen, the database should eventually include systematically acquired high-resolution digital images of the specimen, textual descriptions, links to decision trees, images of live plants, and 3D models. Figure 1: On the left, our set-up at the Smithsonian for digitally photographing type specimens. On the...

Flow algorithms for two pipelined filter ordering problems - Condon,Anne; Deshpande, Amol; Hellerstein,Lisa; Wu,Ning (Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006)
Pipelined filter ordering is a central problem in database query optimization, and has received renewed attention recently in the context of environments such as the web, continuous high-speed data streams and sensor networks. We present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a distributional type problem where the filters run in parallel and the goal is to maximize throughput, and (2) an adversarial type problem where the goal is to minimize the expected value of multiplicative regret. We show that both problems can be solved using similar flow algorithms, which find an optimal ordering scheme in time O(n2), where n is the number of filters. Our algorithm for (1) improves on an earlier O(n3 log n) algorithm of Kodialam.
Keywords: flow algorithms; Pipelined filter ordering; Query optimization; selection ordering

FMM accelerated BEM for 3D Laplace & Helmholtz equations - Gumerov, Nail A.; Duraiswami, Ramani (Proceedings Int. Conf. on Boundary Element Techniques, 2006)

Frequency Independent Flexible Spherical Beamforming Via Rbf Fitting - Yerukhimovich,A.; Duraiswami, Ramani; Gumerov, Nail A.; Zotkin,Dmitry N (2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings, 2006)
We describe a new method for sound analysis using a spherical microphone array without the use of quadrature over the sphere. Quadrature based solutions are very sensitive to the placement of microphones on the sphere, needing measurements to be made at exactly the quadrature positions. We propose to use fitting with band-limited radial basis functions (RBFs) rather than quadrature. Our approach results in frequency independent beamformer weights for flexibly placed microphone locations. Results are demonstrated using both synthetic and real spherical array data
Keywords: acoustic signal processing; array signal processing; band-limited radial basis functions; Computer science; Educational institutions; Eigenvalues and eigenfunctions; Equations; Frequency; frequency independent beamformer weights; frequency independent flexible spherical beamforming; microphone arrays; Nails; Position measurement; RBF fitting; Robustness; sound analysis; spherical array data; spherical microphone array

Going beyond AER: an extensive analysis of word alignments and their impact on MT - Ayan,Necip Fazil; Dorr, Bonnie J (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
This paper presents an extensive evaluation of five different alignments and investigates their impact on the corresponding MT system output. We introduce new measures for intrinsic evaluations and examine the distribution of phrases and untranslated words during decoding to identify which characteristics of different alignments affect translation. We show that precision-oriented alignments yield better MT output (translating more words and using longer phrases) than recall-oriented alignments.

Headphone-Based Reproduction of 3D Auditory Scenes Captured by Spherical/Hemispherical Microphone Arrays - Zhiyun Li; Duraiswami, Ramani (Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, 2006)
We propose a method to reproduce 3D auditory scenes captured by spherical microphone arrays over headphones. This algorithm employs expansions of the captured sound and the head related transfer function over the sphere and uses the orthonormality of the spherical harmonics. Using a spherical microphone array, we first record the 3D auditory scene, then the recordings are spatially filtered and reproduced through headphones in the orthogonal beam-space of the head related transfer functions (HRTFs). We use the KEMAR HRTF measurements to verify our algorithm
Keywords: 3D; analysis; headphones; microphone; arrays; orthogonal; arrays; spatial; auditory; beam-space; spatial; filter; spherical; filters; function; headphone-based; harmonics; array; microphone; processing; audio; processing; harmonic; related; reproduction; hemispherical; scenes; head; signal; transfer

Head-related transfer functions via the fast multipole accelerated boundary element method - Gumerov, Nail A.; Duraiswami, Ramani; Zotkin,Dmitry N (The Journal of the Acoustical Society of America, 2006)
Computation of head‐related transfer functions (HRTF) via geometrical meshes and numerical methods has been suggested by a number of authors. An issue facing this approach is the large computational time needed for high frequencies, where the discretization must include hundreds of thousands of elements. Conventional computational methods are unable to achieve such computations without excessive time or memory. We use a newly developed fast multipole accelerated boundary element method (FMM/BEM) that scales linearly both in time and memory. The method is applied to the mesh of the widely used KEMAR manikin and its HRTF computed up to 20 kHz. The results are compared with available experimental measurements.

Heuristic search and information visualization methods for school redistricting - desJardins, Marie; Bulka,Blazej; Carr,Ryan; Hunt,Andrew; Rathod,Priyang; Rheingans,Penny (Proceedings of the 18th conference on Innovative applications of artificial intelligence - Volume 2, 2006)
We describe an application of AI search and information visualization techniques to the problem of school redistricting, in which students are assigned to home schools within a county or school district. This is a multicriteria optimization problem in which competing objectives must be considered, such as school capacity, busing costs, and socioeconomic distribution. Because of the complexity of the decision-making problem, tools are needed to help end users generate, evaluate, and compare alternative school assignment plans. A key goal of our research is to aid users in finding multiple qualitatively different redistricting plans that represent different tradeoffs in the decision space.We present heuristic search methods that can be used to find a set of qualitatively different plans, and give empirical results of these search methods on population data from the school district of Howard County, Maryland. We show the resulting plans using novel visualization methods that we have developed for summarizing and comparing alternative plans.

How Multirobot Systems Research will Accelerate our Understanding of Social Animal Behavior - Balch, T.; Dellaert, F.; Feldman, A.; Guillory, A.; Isbell, C.L.; Zia Khan; Pratt, S.C.; Stein, A.N.; Wilde, H. (Proceedings of the IEEE, 2006)
Our understanding of social insect behavior has significantly influenced artificial intelligence (AI) and multirobot systems' research (e.g., ant algorithms and swarm robotics). In this work, however, we focus on the opposite question: "How can multirobot systems research contribute to the understanding of social animal behavior?" As we show, we are able to contribute at several levels. First, using algorithms that originated in the robotics community, we can track animals under observation to provide essential quantitative data for animal behavior research. Second, by developing and applying algorithms originating in speech recognition and computer vision, we can automatically label the behavior of animals under observation. In some cases the automatic labeling is more accurate and consistent than manual behavior identification. Our ultimate goal, however, is to automatically create, from observation, executable models of behavior. An executable model is a control program for an agent that can run in simulation (or on a robot). The representation for these executable models is drawn from research in multirobot systems programming. In this paper we present the algorithms we have developed for tracking, recognizing, and learning models of social animal behavior, details of their implementation, and quantitative experimental results using them to study social insects
Keywords: Acceleration; Animal behavior; ant movement tracking; Artificial intelligence; biology computing; Computer vision; control engineering computing; Insects; Intelligent robots; Labeling; monkey movement tracking; multi-robot systems; multirobot systems; robotics algorithms; Robotics and automation; social animal behavior; social animals; social insect behavior; Speech recognition; tracking

IDiexis: Mobile image-based search on world wide web-a picture is worth a thousand keywords - Tollmar,K.; Tom Yeh; Darrell,T. (Proc. of Mobisys, 2006)
Images of objects as queries is a new approach to searchfor information on the web. Image-based information retrieval goes beyond only matching images, as information in other modalities also can be extracted from data collections using image search. We demonstrate a new system that uses images to search for web-based information. We introduce a point-by-photograph paradigm, where users can specify an object simply by taking pictures. Our technique uses content-based image retrieval methods to search the web or other databases for matching images and their source pages to find relevant location-based information. We have developed a prototype on a camera phone and conducted user studies to demonstrate the efficacy of our approach compared to other alternatives.

Imaging as an Alternative Data Channel for Camera Phones - Liu,Xu; Huiping Li; David Doermann (ACM International Conference Proceeding Series; Proceedings of the 5th International Conference on Mobile and Ubiquitous Multimedia, 2006)
In this paper, we demonstrate a solution to use cameras to download data to cell phones as an alternative to existing wireless (CDMA/GPRS, BlueTooth), infrared or cable connections. In our method the data is encoded as a sequence of images, which can be displayed on any flat display, captured by users with their camera phones, and decoded by pre-embedded software. To solve this problem we need to be able to (1) encode arbitrary data as a sequence of images, (2) process captured images under various lighting variations and perspective distortions while maintaining real-time performance, and (3) decode the processed images robustly even when partial data is lost. In the paper we address these challenges in detail and present our solution. We have implemented a prototype which allows users to successfully download various types of files, including pictures, ring tones and Java programs to the camera phones. We discuss the limitations of our solution, and future works to overcome these limitations.

Inferring formal titles in organizational email archives - Namata,G.M.; Getoor, Lise; Diehl,C. (Proc. of the ICML Workshop on Statistical Network Analysis, 2006)
In the social network of large groups of people, such as companiesand organizations, formal hierarchies with titles and lines of authority are established to define the responsibilities and order of power within that group. Although this information may be readily available for individuals within that group, the context this hierarchy provides in communications is not available to those outside the group. In this paper, we define the problem of inferring this formal hierarchy in the context of organizational email archives. We present a new dataset for the widely used Enron email dataset, for use with analysis of the Enron social network hierarchy. We then provide some preliminary results on the problem of classifying individuals to their formal titles using standard classification algorithms.

Initial findings from a three-year international case study exploring children's responses to literature in a digital library - Druin, Allison; Massey,S.; Weeks,A. C (Library trends, 2006)

Integration of visual and inertial information for egomotion: a stochastic approach - Domke, J.; Aloimonos, J. (Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006, 2006)
We present a probabilistic framework for visual correspondence, inertial measurements and egomotion. First, we describe a simple method based on Gabor filters to produce correspondence probability distributions. Next, we generate a noise model for inertial measurements. Probability distributions over the motions are then computed directly from the correspondence distributions and the inertial measurements. We investigate combining the inertial and visual information for a single distribution over the motions. We find that with smaller amounts of correspondence information, fusion of the visual data with the inertial sensor results in much better egomotion estimation. This is essentially because inertial measurements decrease the "translation-rotation" ambiguity. However, when more correspondence information is used, this ambiguity is reduced to such a degree that the inertial measurements provide negligible improvement in accuracy. This suggests that inertial and visual information are more closely integrated in a compositional sense
Keywords: Computer vision; data mining; Distributed computing; egomotion estimation; Gabor filters; Gravity; inertial information; inertial sensor; Laboratories; Motion estimation; Noise measurement; Probability distribution; probability distributions; Rotation measurement; stochastic approach; Stochastic processes; visual information

Interactive sonification for blind people exploration of geo-referenced data: comparison between a keyboard-exploration and a haptic-exploration interfaces - Delogu,Franco; Belardinelli,Marta; Palmiero,Massimiliano; Pasqualotto,Emanuele; Zhao,Haixia; Plaisant, Catherine; Federici,Stefano (Cognitive Processing, 2006)

Knowledge transfer with a multiresolution ensemble of classifiers - Eaton,E.; desJardins, Marie (ICML Workshop on Structural Knowledge Transfer for Machine Learning, 2006)

Learning through failure - Sato,T.; Kameya,Y.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
PRISM, a symbolic-statistical modeling language we have been developing since '97, recently incorporated a program transformation technique to handle failure in generative modeling. I'll show this feature opens a way to new breeds of symbolic models, including EM learning from negative observations, constrained HMMs and finite PCFGs.

Learning user preferences for sets of objects - desJardins, Marie; Eaton,Eric; Wagstaff,Kiri L (Proceedings of the 23rd international conference on Machine learning, 2006)
Most work on preference learning has focused on pairwise preferences or rankings over individual items. In this paper, we present a method for learning preferences over sets of items. Our learning method takes as input a collection of positive examples---that is, one or more sets that have been identified by a user as desirable. Kernel density estimation is used to estimate the value function for individual items, and the desired set diversity is estimated from the average set diversity observed in the collection. Since this is a new learning problem, we introduce a new evaluation methodology and evaluate the learning method on two data collections: synthetic blocks-world data and a new real-world music data collection that we have gathered.

Leveraging recurrent phrase structure in large-scale ontology translation - Murray,G. C; Dorr, Bonnie J; Jimmy Lin; Hajič,J.; Pecina,P. (Proceedings of the 11th Annual Conference of the European Association for Machine Translation, 2006)
This paper presents a process for leveraging structural relationships and reusablephrases when translating large-scale ontologies. Digital libraries are becoming more and more prevalent. An important step in providing universal access to such material is to pro- vide multi-lingual access to the underlying principles of organization via ontologies, thesauri, and controlled vocabularies. Machine translation of these resources requires high accuracy and a deep vocabulary. Human input is often required, but full manual translation can be slow and expensive. We report on a cost-effective approach to ontology translation. We describe our technique of prioritization, our process of collecting aligned translations and generating a new lexicon, and the resulting improvement to translation system output. Our preliminary evaluation indicates that this technique provides significant cost savings for human-assisted translation. The process we developed can be applied to ontologies in other domains and is easily incorporated into other translation systems.

Leveraging reusability: cost-effective lexical acquisition for large-scale ontology translation - Murray,G. Craig; Dorr, Bonnie J; Jimmy Lin; Hajič,Jan; Pecina,Pavel (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
Thesauri and ontologies provide important value in facilitating access to digital archives by representing underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most ontologies precludes fully-automated machine translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations when constructing domain-specific lexical resources. We evaluate the effectiveness of this process by producing a probabilistic phrase dictionary and translating a thesaurus of 56,000 concepts used to catalogue a large archive of oral histories. Our experiments demonstrate a cost-effective technique for accurate machine translation of large ontologies.

Machine Translation: Interlingual Methods - Dorr, Bonnie J; Hovy,E.; Levin,L. (Encyclopedia of Language & Linguistics (Second Edition)Encyclopedia of Language & Linguistics (Second Edition), 2006)
An interlingua is a notation for representing the content of a text that abstracts away from the characteristics of the language itself and focuses on the meaning (semantics) alone. Interlinguas are typically used as pivot representations in machine translation, allowing the contents of a source text to be generated in many different target languages. Because of the complexities involved, few interlinguas are more than demonstration prototypes, and only one has been used in a commercial MT system. In this article, we define the components of an interlingua and the principal issues faced by designers and builders of interlinguas and interlingua MT systems, illustrating with examples from operational systems and research prototypes. We discuss current efforts to annotate texts with interlingua-based information.
Keywords: approximate interlingua; compositionality; conceptual knowledge; cross-language divergences; interlingua; interlingual speech translation; language-independent representation; lexical-conceptual structure; Machine translation; ontology; predicate-argument structure; semantic annotation; semantic frames; semantic zones; text-meaning representations; THEMATIC ROLES

Machining feature-based similarity assessment algorithms for prismatic machined parts - Cardone, Antonio; Gupta, Satyandra K.; Deshmukh,Abhijit; Karnik,Mukul (Computer-Aided Design, 2006)
This paper presents algorithms for identifying machined parts in a database that are similar to a given query part based on machining features. In this paper we only consider parts that are machined on 3-axis machining centers. We utilize reduced feature vectors consisting of machining feature access directions, feature types, feature volumes, feature dimensional tolerances and feature group cardinality as a basis for assessing shape similarity. We have defined a distance function between two sets of reduced feature vectors to assess the similarity between them from the machining effort point of view. To assess the similarity between the two parts, one set of reduced feature vectors is transformed in space using rigid body transformations with respect to the other set such that the distance between them is minimized. The distance between the two sets of aligned reduced feature vectors is used as a measure of similarity between the two parts. The existing machined parts are rank ordered based on the value of the distance with respect to the query part. The cost of previously machined parts that have a very small distance from the query part can be used as a basis for estimating the cost of machining the new part.
Keywords: Feature vector alignment; Machining features; Similarity assessment

MauveDB: supporting model-based user views in database systems - Deshpande, Amol; Madden,Samuel (Proceedings of the 2006 ACM SIGMOD international conference on Management of data, 2006)
Real-world data --- especially when generated by distributed measurement infrastructures such as sensor networks --- tends to be incomplete, imprecise, and erroneous, making it impossible to present it to users or feed it directly into applications. The traditional approach to dealing with this problem is to first process the data using statistical or probabilistic models that can provide more robust interpretations of the data. Current database systems, however, do not provide adequate support for applying models to such data, especially when those models need to be frequently updated as new data arrives in the system. Hence, most scientists and engineers who depend on models for managing their data do not use database systems for archival or querying at all; at best, databases serve as a persistent raw data store.In this paper we define a new abstraction called model-based views and present the architecture of MauveDB, the system we are building to support such views. Just as traditional database views provide logical data independence, model-based views provide independence from the details of the underlying data generating mechanism and hide the irregularities of the data by using models to present a consistent view to the users. MauveDB supports a declarative language for defining model-based views, allows declarative querying over such views using SQL, and supports several different materialization strategies and techniques to efficiently maintain them in the face of frequent updates. We have implemented a prototype system that currently supports views based on regression and interpolation, using the Apache Derby open source DBMS, and we present results that show the utility and performance benefits that can be obtained by supporting several different types of model-based views in a database system.
Keywords: Query processing; regression; sensor networks; statistical models; uncertain data; views

A maximum entropy approach to combining word alignments - Ayan,Necip Fazil; Dorr, Bonnie J (Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, 2006)
This paper presents a new approach to combining outputs of existing word alignment systems. Each alignment link is represented with a set of feature functions extracted from linguistic features and input alignments. These features are used as the basis of alignment decisions made by a maximum entropy approach. The learning method has been evaluated on three language pairs, yielding significant improvements over input alignments and three heuristic combination methods. The impact of word alignment on MT quality is investigated, using a phrase-based MT system.

MCMC Data Association and Sparse Factorization Updating for Real Time Multitarget Tracking with Merged and Multiple Measurements - Zia Khan; Balch, T.; Dellaert, F. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006)
In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC
Keywords: algorithms; approximate inference; Artificial intelligence; auxiliary variable particle filter; Computational efficiency; continuous state space; downdating; Image Enhancement; Image Interpretation, Computer-Assisted; Inference algorithms; Information Storage and Retrieval; laser range scanner; laser range scanner.; Least squares approximation; least squares approximations; Least squares methods; linear least squares; Markov chain Monte Carlo; Markov processes; MCMC data association; merged measurements; Monte Carlo methods; Movement; multiple merged measurements; multitarget tracking; particle filter; particle filtering (numerical methods); Particle filters; Pattern Recognition, Automated; probabilistic model; QR factorization; Radar tracking; Rao-Blackwellized; real time multitarget tracking; Reproducibility of results; Sampling methods; Sensitivity and Specificity; sensor fusion; sparse factorization updating; sparse least squares; State-space methods; Subtraction Technique; target tracking; updating

Metagenomic Analysis of the Human Distal Gut Microbiome - Gill,Steven R.; Pop, Mihai; DeBoy,Robert T.; Eckburg,Paul B; Turnbaugh,Peter J; Samuel,Buck S; Gordon,Jeffrey I; Relman,David A; Fraser-Liggett,Claire M; Nelson,Karen E. (Science, 2006)
The human intestinal microbiota is composed of 1013 to 1014 microorganisms whose collective genome (“microbiome”) contains at least 100 times as many genes as our own genome. We analyzed ∼78 million base pairs of unique DNA sequence and 2062 polymerase chain reaction–amplified 16S ribosomal DNA sequences obtained from the fecal DNAs of two healthy adults. Using metabolic function analyses of identified genes, we compared our human genome with the average content of previously sequenced microbial genomes. Our microbiome has significantly enriched metabolism of glycans, amino acids, and xenobiotics; methanogenesis; and 2-methyl-d-erythritol 4-phosphate pathway–mediated biosynthesis of vitamins and isoprenoids. Thus, humans are superorganisms whose metabolism represents an amalgamation of microbial and human attributes.

Methods for automatically evaluating answers to complex questions - Jimmy Lin; Demner-Fushman,D. (Information Retrieval, 2006)
Evaluation is a major driving force in advancing the state of the art in language technologies. In particular, methods for automatically assessing the quality of machine output is the preferred method for measuring progress, provided that these metrics have been validated against human judgments. Following recent developments in the automatic evaluation of machine translation and document summarization, we present a similar approach, implemented in a measure called POURPRE, an automatic technique for evaluating answers to complex questions based on n-gram co-occurrences between machine output and a human-generated answer key. Until now, the only way to assess the correctness of answers to such questions involves manual determination of whether an information “nugget” appears in a system's response. The lack of automatic methods for scoring system output is an impediment to progress in the field, which we address with this work. Experiments with the TREC 2003, TREC 2004, and TREC 2005 QA tracks indicate that rankings produced by our metric correlate highly with official rankings, and that POURPRE outperforms direct application of existing metrics.

Morphology Induction from Limited Noisy Data Using Approximate String Matching - Karagol-Ayan,Burcu; David Doermann; Weinberg, Amy (Proceedings of the Eighth Meeting of the ACL Special Interest Group in Computational Phonology (SIGPHON 2006), 2006)
For a language with limited resources, a dictionary may be one of the few available electronic resources. To make effective use of the dictionary for translation, however, users must be able to access it using the root form of morphologically deformed variant found in the text. Stemming and data driven methods, however, are not suitable when data is sparse. We present algorithms for discovering morphemes from limited, noisy data obtained by scanning a hard copy dictionary. Our approach is based on the novel application of the longest common substring and string edit distance metrics. Results show that these algorithms can in fact segment words into roots and affixes from the limited data contained in a dictionary, and extract affixes. This in turn allows non native speakers to perform multilingual tasks for applications where response must be rapid, and their knowledge is limited. In addition, this analysis can feed other NLP tools requiring lexicons.

Mosaicing of Camera-captured Documents Without Pose Restriction - Liang,Jian; DeMenthon,Daniel; David Doermann (Computer Vision and Image Understanding, 2006)
In this paper we present an image mosaicing method for camera-captured documents. Our method is unique in not restricting the camera position, thus allowing greater flexibility than approaches using scanner or fixed-cameras. To accommodate for the perspective distortions introduced by varying poses, we implement a two step image registration process that accurately computes the projectivity between any two document images with an overlapping area that may be as small as 10%. In the overlapping area, we apply a sharpness based selection process to obtain seamless composition across the border and within. Experiments show that our approach can produce a very sharp, high resolution and accurate full page mosaic from small image patches of a document captured from unconstrained positions.

Multi-camera tracking and segmentation of occluded people on ground plane using search-guided particle filtering - Kim,K.; Davis, Larry S. (Computer Vision–ECCV 2006, 2006)
A multi-view multi-hypothesis approach to segmenting and tracking multiple (possibly occluded) persons on a ground plane is proposed. During tracking, several iterations of segmentation are performed using information from human appearance models and ground plane homography. To more precisely locate the ground location of a person, all center vertical axes of the person across views are mapped to the top-view plane and their intersection point on the ground is estimated. To tackle the explosive state space due to multiple targets and views, iterative segmentation-searching is incorporated into a particle filtering framework. By searching for people’s ground point locations from segmentations, a set of a few good particles can be identified, resulting in low computational cost. In addition, even if all the particles are away from the true ground point, some of them move towards the true one through the iterated process as long as they are located nearby. We demonstrate the performance of the approach on several video sequences.

A multi-resolution representation for terrain morphology - Danovaro,E.; De Floriani, Leila; Papaleo,L.; Vitali,M. (Geographic Information Science, 2006)
Mesh-based terrain representations provide accurate descriptions of a terrain, but fail in capturing its morphological structure. The morphology of a terrain is defined by its critical points and by the critical lines joining them, which form a so-called surface network. Because of the large size of current terrain data sets, a multi-resolution representation of the terrain morphology is crucial. Here, we address the problem of representing the morphology of a terrain at different resolutions. The basis of the multi-resolution terrain model, that we call a Multi-resolution Surface Network (MSN), is a generalization operator on a surface network, which produces a simplified representation incrementally. An MSN is combined with a multi-resolution mesh-based terrain model, which encompasses the terrain morphology at different resolutions. We show how variable-resolution representations can be extracted from an MSN, and we present also an implementation of an MSN in a compact encoding data structure.

Multivalued default logic for identity maintenance in visual surveillance - Shet,V.; Harwood,D.; Davis, Larry S. (Computer Vision–ECCV 2006, 2006)
Recognition of complex activities from surveillance video requires detection and temporal ordering of its constituent “atomic” events. It also requires the capacity to robustly track individuals and maintain their identities across single as well as multiple camera views. Identity maintenance is a primary source of uncertainty for activity recognition and has been traditionally addressed via different appearance matching approaches. However these approaches, by themselves, are inadequate. In this paper, we propose a prioritized, multivalued, default logic based framework that allows reasoning about the identities of individuals. This is achieved by augmenting traditional appearance matching with contextual information about the environment and self identifying traits of certain actions. This framework also encodes qualitative confidence measures for the identity decisions it takes and finally, uses this information to reason about the occurrence of certain predefined activities in video.

Multi-View Learning and Link Farm Discovery - Scheffer,T.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
The first part of this abstract focuses on estimation of mixture models for problems in which multiple views of the instances are available. Examples of this setting include clustering web pages or research papers that have intrinsic (text) and extrinsic (references) attributes. Mixture model estimation is a key problem for both semi-supervised and unsupervised learning. An appropriate optimization criterion quantifies the likelihood and the consensus among models in the individual views; maximizing this consensus minimizes a bound on the risk of assigning an instance to an incorrect mixture component. An EM algorithm maximizes this criterion. The second part of this abstract focuses on the problem of identifying link spam. Search engine optimizers inflate the page rank of a target site by spinning an artificial web for the sole purpose of providing inbound links to the target. Discriminating natural from artificial web sites is a difficult multi-view problem.

Multi-view Reconstruction of Static and Dynamic Scenes - Agrawal,M.; Mittal,A.; Davis, Larry S. (Handbook of Mathematical Models in Computer Vision, 2006)
We explore the reconstruction of a three-dimensional scene from multiple images captured from far away viewpoints (wide-baseline camera arrangement). Such an arrangement is required for complex scenes where the visibility flora any one viewpoint is not sufficient to adequately reconstruct the entire scene. Also, such an arrangement reduces the error in triangulation of the features, thereby improving the accuracy of reconstruction. Our emphasis is on algorithms that recover a volumetric model of the scene from calibrated cameras by explicitly modeling and detecting occlusions. We present a brief overview of the state of the art in such methods for multi-view reconstruction. In particular, algorithms based on a probabilistic framework have become quite popular and produce very accurate models. Several such probabilistic volume reconstruction methods will be described. For the dynamic parts of the scene, where an online reconstruction is needed, simpler methods are required. An important case of such scenes is that of walking people in a surveillance scenario. For this case, we present fast online algorithms that recover approximate shape and appearance models and 3D trajectories of people as they walk in the scene. Finally, we address the problem of optimal placement of cameras in order to acquire the best possible image data for the reconstruction of a given scene according to the particular task specification.

Name reference resolution in organizational email archives - Diehl,C. P; Getoor, Lise; Namata,G. (SIAM International Conference on Data Mining, 2006)

Nuclear Envelope Dystrophies Show a Transcriptional Fingerprint Suggesting Disruption of Rb–MyoD Pathways in Muscle Regeneration - Bakay,Marina; Wang,Zuyi; Melcon,Gisela; Schiltz,Louis; Xuan,Jianhua; Zhao,Po; Sartorelli,Vittorio; Seo,Jinwook; Pegoraro,Elena; Angelini,Corrado; Shneiderman, Ben; Escolar,Diana; et al. (BrainBrain, 2006)
Mutations of lamin A/C (LMNA) cause a wide range of human disorders, including progeria, lipodystrophy, neuropathies and autosomal dominant Emery–Dreifuss muscular dystrophy (EDMD). EDMD is also caused by X-linked recessive loss-of-function mutations of emerin, another component of the inner nuclear lamina that directly interacts with LMNA. One model for disease pathogenesis of LMNA and emerin mutations is cell-specific perturbations of the mRNA transcriptome in terminally differentiated cells. To test this model, we studied 125 human muscle biopsies from 13 diagnostic groups (125 U133A, 125 U133B microarrays), including EDMD patients with LMNA and emerin mutations. A Visual and Statistical Data Analyzer (VISDA) algorithm was used to statistically model cluster hierarchy, resulting in a tree of phenotypic classifications. Validations of the diagnostic tree included permutations of U133A and U133B arrays, and use of two probe set algorithms (MAS5.0 and MBEI). This showed that the two nuclear envelope defects (EDMD LMNA, EDMD emerin) were highly related disorders and were also related to fascioscapulohumeral muscular dystrophy (FSHD). FSHD has recently been hypothesized to involve abnormal interactions of chromatin with the nuclear envelope. To identify disease-specific transcripts for EDMD, we applied a leave-one-out (LOO) cross-validation approach using LMNA patient muscle as a test data set, with reverse transcription–polymerase chain reaction (RT–PCR) validations in both LMNA and emerin patient muscle. A high proportion of top-ranked and validated transcripts were components of the same transcriptional regulatory pathway involving Rb1 and MyoD during muscle regeneration (CRI-1, CREBBP, Nap1L1, ECREBBP/p300), where each was specifically upregulated in EDMD. Using a muscle regeneration time series (27 time points) we develop a transcriptional model for downstream consequences of LMNA and emerin mutations. We propose that key interactions between the nuclear envelope and Rb and MyoD fail in EDMD at the point of myoblast exit from the cell cycle, leading to poorly coordinated phosphorylation and acetylation steps. Our data is consistent with mutations of nuclear lamina components leading to destabilization of the transcriptome in differentiated cells.
Keywords: EDMD = Emery–Dreifuss muscular dystrophy; emerin; Emery-Dreifuss muscular dystrophy; FSHD = fascioscapulohumeral muscular dystrophy; IDG = individual discriminatory genes; JDG = jointly discriminatory genes; lamin A/C; LGMD = limb-girdle muscular dystrophy; LOO = leave-one-out; RT–PCR = reverse transcription–polymerase chain reaction; VISDA = Visual and Statistical Data Analyzer; Skeletal muscle; wFC = weighted Fisher criterion

Numerical Analysis of Plasmon Resonances Based on Fast Multipole Method - Zhang,Zhenyu; Mayergoyz, Issak D; Gumerov, Nail A.; Duraiswami, Ramani (Electromagnetic Field Computation, 2006 12th Biennial IEEE Conference on, 2006)
A novel technique for the numerical analysis of plasmon resonances by using fast multipole method (FMM) is presented. This approach is based on the solution of eigenvalue problem for boundary integral equations, which can be naturally implemented by using the fast multipole method. Numerical examples that highlight the efficiency of the fast multipole implementation are reported
Keywords: analysis; plasmon; and; boundary; eigenfunctions; plasmons; equations; eigenvalue; equations; eigenvalues; integral; method; numerical; multipole; problem; fast; resonances; boundary

Numerical computation of the Green?s function for two-dimensional finite-size photonic crystals of infinite length - Seydou,F.; Ramahi,Omar M.; Duraiswami, Ramani; Seppänen,T. (Optics ExpressOpt. Express, 2006)
We develop a numerical algorithm that computes the Green’s function of Maxwell equation for a 2D finite-size photonic crystal, composed of rods of arbitrary shape. The method is based on the boundary integral equation, and a Nyström discretization is used for the numerical solution. To provide an exact solution that validates our code we derive multipole expansions for circular cylinders using our integral equation approach. The numerical method performs very well on the test case. We then apply it to crystals of arbitrary shape and discuss the convergence.
Keywords: Diffraction and gratings; Multiple scattering

A One-Threshold Algorithm for Detecting Abandoned Packages Under Severe Occlusions Using a Single Camera - Lim,Ser-Nam; Davis, Larry S. (Technical Reports from UMIACS, 2006)
We describe a single-camera system capable of detecting abandoned packages under severe occlusions, which leads to complications on several levels. The first arises when frames containing only background pixels are unavailable for initializing the background model - a problem for which we apply a novel discriminative measure. The proposed measure is essentially the probability of observing a particular pixel value, conditioned on the probability that no motion is detected, with the pdf on which the latter is based being estimated as a zero-mean and unimodal Gaussian distribution from observing the difference values between successive frames. We will show that such a measure is a powerful discriminant even under severe occlusions, and can deal robustly with the foreground aperture effect - a problem inherently caused by differencing successive frames. The detection of abandoned packages then follows at both the pixel and region level. At the pixel-level, an ``abandoned pixel'' is detected as a foreground pixel, at which no motion is observed. At the region-level, abandoned pixels are ascertained in a Markov Random Field (MRF), after which they are clustered. These clusters are only finally classified as abandoned packages, if they display temporal persistency in their size, shape, position and color properties, which is determined using conditional probabilities of these attributes. The algorithm is also carefully designed to avoid any thresholding, which is the pitfall of many vision systems, and which significantly improves the robustness of our system. Experimental results from real-life train station sequences demonstrate the robustness and applicability of our algorithm.
Keywords: Technical Report

Open problems in relational data clustering - Anthony,A.; desJardins, Marie (Proceedings of the ICML Workshop on Open Problems in Stastistical Relational Learning, 2006)
Data clustering is the task of detecting pat-terns in a set of data. Most algorithms take non-relational data as input and are sometimes unable to find significant patterns. Many data sets can include relational infor- mation, as well as independent object at- tributes. We believe that clustering with re- lational data will help find significant pat- terns where non-relational algorithms fail. This paper discusses two open problems in relational data clustering: clustering hetero- geneous data, and relation selection or ex- traction. Potential methods for addressing the problems are presented.

Opinion Analysis in Document Databases - Cesarano,C.; Dorr, Bonnie J; Picariello, A.; Reforgiato,D.; Sagoff,A.; V.S. Subrahmanian (Proc. AAAI Spring Symposium on Computational Approaches to Analyzing Weblogs, Stanford, CA, 2006)
There are numerous applications in which we would like toassess what opinions are being expressed in text documents. Forr example, Martha Stewart’s company may have wished to assess the degree of harshness of news articles about her in the recent past. Likewise, a World Bank official may wish to as- sess the degree of criticism of a proposed dam in Bangladesh. The ability to gauge opinion on a given topic is therefore of critical interest. In this paper, we develop a suite of algo- rithms which take as input, a set D of documents as well as a topic t, and gauge the degree of opinion expressed about topic t in the set D of documents. Our algorithms can return both a number (larger the number, more positive the opinion) as well as a qualitative opinion (e.g. harsh, complimentary). We as- sess the accuracy of these algorithms via human experiments and show that the best of these algorithms can accurately re- flect human opinions. We have also conducted performance experiments showing that our algorithms are computationally fast.

Out–of–Core Multiresolution Terrain Modeling - Danovaro,E.; De Floriani, Leila; Puppo,E.; Samet, Hanan (Modeling and Management of Geographical Data over Distributed Architectures. Springer–Verlag, 2006)

Parallel syntactic annotation of multiple languages - Rambow,O.; Dorr, Bonnie J; Farwell,D.; Green,R.; Habash,N.; Helmreich,S.; Hovy,E.; Levin,L.; Miller,K.J.; Mitamura,T.; others (Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC2006). Genoa, Italy, 2006)
This paper describes an effort to investigate the incrementally deepening development of an interlingua notation, validated by humanannotation of texts in English plus six languages. We begin with deep syntactic annotation, and in this paper present a series of annotation manuals for six different languages at the deep-syntactic level of representation. Many syntactic differences between languages are removed in the proposed syntactic annotation, making them useful resources for multilingual NLP projects with semantic components.

Parametric Hand Tracking for Recognition of Virtual Drawings - Sepehri,A.; Yacoob,Yaser; Davis, Larry S. (Computer Vision Systems, 2006 ICVS '06. IEEE International Conference on, 2006)
A hand tracking system for recognition of virtual spatial drawings is presented. Using a stereo camera, the 3D position of the hand in space is estimated. Then, by tracking the central region of the hand in 3D and estimating a virtual plane in space, the intended drawing of the user is recognized. Experimental results demonstrate the accuracy and effectiveness of this technique. The system can be used to communicate drawings and alphabets to a computer where a classifier can transform the drawn alphabets into interpretable characters.

PCFGs with syntactic and prosodic indicators of speech repairs - Hale,John; Shafran,Izhak; Yung,Lisa; Dorr, Bonnie J; Harper,Mary; Krasnyanskaya,Anna; Lease,Matthew; Liu,Yang; Roark,Brian; Snover,Matthew; Stewart,Robin (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
A grammatical method of combining two kinds of speech repair cues is presented. One cue, prosodic disjuncture, is detected by a decision tree-based ensemble classifier that uses acoustic cues to identify where normal prosody seems to be interrupted (Lickley, 1996). The other cue, syntactic parallelism, codifies the expectation that repairs continue a syntactic category that was left unfinished in the reparandum (Levelt, 1983). The two cues are combined in a Treebank PCFG whose states are split using a few simple tree transformations. Parsing performance on the Switchboard and Fisher corpora suggests that these two cues help to locate speech repairs in a synergistic way.

PDR: A Performance Evaluation Method for Foreground-Background Segmentation Algorithms - Kim,K.; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (EURASIP Journal on Applied Signal Processing, 2006)
We introduce a performance evaluation methodologycalled Perturbation Detection Rate (PDR) analysis for measuring performance of foreground-background seg- mentation. It has some advantages over the commonly used Receiver Operation Characteristics (ROC) analy- sis. Specifically, it does not require foreground targets or knowledge of foreground distributions. It measures the sensitivity of a background subtraction algorithm in detecting possible low contrast targets against the background as a function of contrast, also depending on how well the model captures mixed (moving) back- ground events. We compare four background subtrac- tion algorithms using the methodology. The experimen- tal results show how PDR is used to measure perfor- mance with respect to detection sensitivity in interest- ing low contrast regions.

Probabilistic, Logical and Relational Learning-Towards a Synthesis - De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H; Lloyd,J. W; Sears,T. D; Milch,B.; Marthi,B.; Russell,S.; Sontag,D. (Dagstuhl Seminar Proceedings, 2006)

A probabilistic notion of correspondence and the epipolar constraint - Domke, J.; Aloimonos, J. (Proceedings of the Third International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'06), 2006)

Processing approximate aggregate queries in wireless sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Information Systems, 2006)
In-network data aggregation has been recently proposed as an effective means to reduce the number of messages exchanged in wireless sensor networks. Nodes of the network form an aggregation tree, in which parent nodes aggregate the values received from their children and propagate the result to their own parents. However, this schema provides little flexibility for the end-user to control the operation of the nodes in a data sensitive manner. For large sensor networks with severe energy constraints, the reduction (in the number of messages exchanged) obtained through the aggregation tree might not be sufficient. In this paper, we present new algorithms for obtaining approximate aggregate statistics from large sensor networks. The user specifies the maximum error that he is willing to tolerate and, in turn, our algorithms program the nodes in a way that seeks to minimize the number of messages exchanged in the network, while always guaranteeing that the produced estimate lies within the specified error from the exact answer. A key ingredient to our framework is the notion of the residual mode of operation that is used to eliminate messages from sibling nodes when their cumulative change to the computed aggregate is small. We introduce two new algorithms, based on potential gains, which adaptively redistribute the error thresholds to those nodes that benefit the most and try to minimize the total number of transmitted messages in the network. Our techniques significantly reduce the number of messages, often by a factor of 10 for a modest 2% relative error bound, and consistently outperform previous techniques for computing approximate aggregates, which we have adapted for sensor networks.
Keywords: Aggregate queries; approximation; sensor networks

Proximity problems on line segments spanned by points - Daescu,Ovidiu; Luo,Jun; Mount, Dave (Computational Geometry, 2006)
Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O ( n log n ) time, O ( n ) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S ∖ { q } in optimal O ( n log n ) time and O ( n ) space. Finally, we give an O ( n log n ) time, O ( n ) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O ( n log n + k ) time and O ( n + k ) space.
Keywords: Closest; Farthest; k closest lines; Minimum (maximum) area triangle; Proximity problem

Real-Time Distributed Algorithms for Visual and Battlefield Reasoning - Davis, Larry S.; Basili, Victor R.; V.S. Subrahmanian; Reggia, James A.; Aloimonos, J. (MARYLAND UNIV COLLEGE PARK OFFICE OF RESEARCH ADMINISTRATION AND ADVANCEMENT, 2006)
Information is key to the success of the next generation battlefield. There is a critical need to determine, in real-time, what the enemy is doing, and to interpret that information in the context of past related events. In this project we examined two aspects of this issue: development of a high-level task definition language for tasking a network of sensors to carry out given objectives, and interpreting recounted events so that past related scenarios could be automatically identified from a case database.

Real-Time Human Detection, Tracking, and Verification in Uncontrolled Camera Motion Environments - Hussein,M.; Abd-Almageed, Wael; Yang Ran; Davis, Larry S. (Computer Vision Systems, 2006 ICVS '06. IEEE International Conference on, 2006)
In environments where a camera is installed on a freely moving platform, e.g. a vehicle or a robot, object detection and tracking becomes much more difficult. In this paper, we presents a real time system for human detection, tracking, and verification in such challenging environments. To deliver a robust performance, the system integrates several computer vision algorithms to perform its function: a human detection algorithm, an object tracking algorithm, and a motion analysis algorithm. To utilize the available computing resources to the maximum possible extent, each of the system components is designed to work in a separate thread that communicates with the other threads through shared data structures. The focus of this paper is more on the implementation issues than on the algorithmic issues of the system. Object oriented design was adopted to abstract algorithmic details away from the system structure.

Reranking for Sentence Boundary Detection in Conversational Speech - Roark,B.; Liu,Yang; Harper,M.; Stewart,R.; Lease,M.; Snover,M.; Shafran,I.; Dorr, Bonnie J; Hale,J.; Krasnyanskaya,A.; Yung,L. (2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings, 2006)
We present a reranking approach to sentence-like unit (SU) boundary detection, one of the EARS metadata extraction tasks. Techniques for generating relatively small n-best lists with high oracle accuracy are presented. For each candidate, features are derived from a range of information sources, including the output of a number of parsers. Our approach yields significant improvements over the best performing system from the NIST RT-04F community evaluation
Keywords: Automatic speech recognition; conversational speech; data mining; Ear; EARS metadata extraction tasks; Feature extraction; hidden Markov models; meta data; Model driven engineering; NIST; NIST RT-04F community evaluation; oracle accuracy; performance evaluation; reranking; sentence-like unit boundary detection; Speech processing; Speech recognition; Telephony

Revealing botnet membership using DNSBL counter-intelligence - Ramachandran,A.; Feamster, Nick; Dagon,D. (Proc. 2nd USENIX Steps to Reducing Unwanted Traffic on the Internet, 2006)
Botnets—networks of (typically compromised) machines—are often used for nefarious activities (e.g., spam, click fraud, denial-of-service attacks, etc.). Identifying members of botnets could help stem these attacks, but passively detecting botnet membership (i.e., without disrupting the operation of the botnet) proves to be difficult. This paper studies the effectiveness of monitoring lookups to a DNS-based blackhole list (DNSBL) to expose botnet membership. We perform counter-intelligence based on the insight that botmasters themselves perform DNSBL lookups to determine whether their spamming bots are blacklisted. Using heuristics to identify which DNSBL lookups are perpetrated by a botmaster performing such reconnaissance, we are able to compile a list of likely bots. This paper studies the prevalence of DNSBL reconnaissance observed at a mirror of a well-known blacklist for a 45-day period, identifies the means by which botmasters are performing reconnaissance, and suggests the possibility of using counter-intelligence to discover likely bots. We find that bots are performing reconnaissance on behalf of other bots. Based on this finding, we suggest counter-intelligence techniques that may be useful for early bot detection.

Robust fuzzy extractors and authenticated key agreement from close secrets - Dodis,Y.; Katz, Jonathan; Reyzin,L.; Smith,A. (Advances in Cryptology-CRYPTO 2006, 2006)
Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys R j using multiple pairs {(W j , W′ j )}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.

Robust Point Matching for Nonrigid Shapes By Preserving Local Neighborhood Structures - Yefeng Zheng; David Doermann (IEEETransactions on Pattern Analysis and Machine Intelligence, 2006)
In previous work on point matching, a set of points is often treated as an instance of a joint distribution to exploit global relationships in the point set. For nonrigid shapes, however, the local relationship among neighboring points is stronger and more stable than the global one. In this paper, we introduce the notion of a neighborhood structure for the general point matching problem. We formulate point matching as an optimization problem to preserve local neighborhood structures during matching. Our approach has a simple graph matching interpretation, where each point is a node in the graph, and two nodes are connected by an edge if they are neighbors. The optimal match between two graphs is the one that maximizes the number of matched edges. Existing techniques are leveraged to search for an optimal solution with the shape context distance used to initialize the graph matching, followed by relaxation labeling updates for refinement. Extensive experiments show the robustness of our approach under deformation, noise in point locations, outliers, occlusion, and rotation. It outperforms the shape context and TPS-RPM algorithms on most scenarios.

The role of knowledge in conceptual retrieval: a study in the domain of clinical medicine - Jimmy Lin; Demner-Fushman,Dina (Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, 2006)
Despite its intuitive appeal, the hypothesis that retrieval at the level of "concepts" should outperform purely term-based approaches remains unverified empirically. In addition, the use of "knowledge" has not consistently resulted in performance gains. After identifying possible reasons for previous negative results, we present a novel framework for "conceptual retrieval" that articulates the types of knowledge that are important for information seeking. We instantiate this general framework in the domain of clinical medicine based on the principles of evidence-based medicine (EBM). Experiments show that an EBM-based scoring algorithm dramatically outperforms a state-of-the-art baseline that employs only term statistics. Ablation studies further yield a better understanding of the performance contributions of different components. Finally, we discuss how other domains can benefit from knowledge-based approaches.
Keywords: Question answering; reranking; semantic models

Script-Independent Text Line Segmentation in Freestyle Handwritten Documents - Li,Yi; Yefeng Zheng; David Doermann; Jaeger,Stefan (University of Maryland, College Park, 2006)
Text line segmentation in freestyle handwritten documents remains an open document analysis problem. Curvilinear text lines and small gaps between neighboring text lines present a challenge to algorithms developed for machine printed or hand-printed documents. In this paper, we propose a novel approach based on density estimation and a state-of-the-art image segmentation technique, the level set method. From an input document image, we estimate a probability map, where each element represents the probability that the underlying pixel belongs to a text line. The level set method is then exploited to determine the boundary of neighboring text lines by evolving an initial estimate. Unlike most connected component based methods [1, 2], the proposed algorithm does not use any script-specific knowledge. Extensive quantitative experiments on freestyle handwritten documents with diverse scripts, such as Arabic, Chinese, Korean, and Hindi, demonstrate that our algorithm consistently outperforms previous methods [3, 1, 2]. Further experiments show the proposed algorithm is robust to scale change, rotation, and noise.

Segmentation of planar objects and their shadows in motion sequences - Yacoob,Yaser; Davis, Larry S. (International journal of computer vision, 2006)
We investigate segmentation of planar objects and their cast shadows in image sequences. Given two moving image regions in an image sequence we present an algorithm for determining if the two moving regions can be interpreted as a planar object and its cast shadow. Projective geometry and motion properties are employed to directly recover a homology that constrains point correspondences of the outlines of the image regions and determine if they obey an object/shadow relationship. This homology is derived directly from the motions of the regions and therefore is easier to accomplish than determining point-to-point correspondences between candidate object-shadow pairs. Several experiments under approximate point light source illumination are presented.

Segmenting people in small groups - Davis, Larry S. (Proceedings of the 4th ACM international workshop on Video surveillance and sensor networks, 2006)
In this paper we review prior work on the problem of segmenting small groups of people into individuals in surveillance video.
Keywords: segmentation; Surveillance; video analysis

Semi-Parametric Model-Based Clustering for DNA Microarray Data - Han,Bohyung; Davis, Larry S. (Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, 2006)
Various clustering methods have been proposed for the analysis of gene expression data, but conventional clustering algorithms have several critical limitations; how to set parameters such as number of clusters, initial cluster centers, and so on. In this paper, we propose a semi-parametric model-based clustering algorithm in which the underlying model is a mixture of Gaussian. Each gene expression data builds a Gaussian kernel, and the uncertainty of microarray data is naturally integrated in the data representation. Our algorithm provides a principled method to automatically determine parameters - number of components in the mixture, mean, covariance, and weight of each Gaussian - by mean-shift procedure (Comaniciu and Meer, 1999) and curvature fitting. After the initialization, expectation maximization (EM) algorithm is employed for clustering to achieve maximum likelihood (ML). The performance of our algorithm is compared with standard EM algorithm using real data as well as synthetic data
Keywords: clustering; clustering; DNA; Gaussian; computing; genetics; pattern; data; Gaussian; data; maximum; DNA; Expression; fitting; data; kernel; Gaussian; likelihood; mean-shift; maximization; gene; Microarray; mixtures; curvature; model-based; procedure; semiparametric; processes; biology; representation; expectation

Sentence compression as a component of a multi-document summarization system - Zajic, David; Dorr, Bonnie J; Jimmy Lin; Schwartz,R. (Proceedings of the 2006 Document Understanding Workshop, New York, 2006)
We applied a single-document sentence-trimming approach (Trimmer) to the problem of multi-document summariza- tion. Trimmer was designed with the in- tention of compressing a lead sentence into a space consisting of tens of char- acters. In our Multi-Document Trimmer (MDT), we use Trimmer to generate multiple trimmed candidates for each sentence. Sentence selection is used to determine which trimmed candidates provide the best combination of topic coverage and brevity. We demonstrate that we were able to port Trimmer easily to this new problem. We also show that MDT generally ranked higher for recall than for precision, suggesting that MDT is currently more successful at finding relevant content than it is at weeding out irrelevant content. Finally, we present an error analysis that shows that, while sentence compressions is making space for additional sentences, more work is needed in the area of generating and se- lecting the right candidates.

Sentence Trimming and Selection: Mixing and Matching - Zajic, David; Dorr, Bonnie J; Jimmy Lin; O'Leary, Dianne P.; Conroy,John M.; Schlesinger,Judith D. (DUC 06 Conference Proceedings, 2006)
We describe how components from two distinct multi-document summarization systems were combined. Twenty four possible combinations of components were considered. We observed some contrasts between conservative and aggressive sentence compression (i.e., trimming) in the context of multi-document summarization.

Shared family calendars: Promoting symmetry and accessibility - Plaisant, Catherine; Clamage,Aaron; Hutchinson,Hilary Browne; Bederson, Benjamin B.; Druin, Allison (ACM Trans. Comput.-Hum. Interact., 2006)
We describe the design and use of a system facilitating the sharing of calendar information between remotely located, multi-generational family members. Most previous work in this area involves software enabling younger family members to monitor their parents. We have found, however, that older adults are equally if not more interested in the activities of younger family members. The major obstacle preventing them from participating in information sharing is the technology itself. Therefore, we developed a multi-layered interface approach that offers simple interaction to older users. In our system, users can choose to enter information into a computerized calendar or write it by hand on digital paper calendars. All of the information is automatically shared among everyone in the distributed family. By making the interface more accessible to older users, we promote symmetrical sharing of information among both older and younger family members. We present our participatory design process, describe the user interface, and report on an exploratory field study in three households of an extended family.
Keywords: calendar; digital paper; elderly; family technology; Home; layered interface; privacy; universal usability

SOFTCBIR: Object Searching in Videos Combining Keypoint Matching and Graduated Assignment - Luo,Ming; DeMenthon,Daniel; Yu,Xiaodong; David Doermann (University of Maryland, College Park, 2006)
This paper proposes a new approach to object searching in video databases, SoftCBIR, which combines a keypoint matching algorithm and a graduated assignment algorithm based on softassign. Compared with previous approaches, SoftCBIR is an innovative combination of two powerful techniques: 1) An energy minimization algorithm is applied to match two groups of keypoints while accounting for both their similarity in descriptor space and the consistency of their geometric configuration. The algorithm computes correspondence and pose transformation between two groups of keypoints iteratively and alternately toward an optimal result. The objective energy function combines normalized distance errors in descriptor space and in the spatial domain. 2) Initial individual keypoint matching relies on Approximate K-Nearest Neighbor (ANN) search. ANN achieves much more accurate initial keypoint matching results in the descriptor space than K-means labeling. Experiments prove the effectiveness of our approach, and demonstrate the performance improvements rising from the combination of the two proposed techniques in the SoftCBIR algorithm. The support of this research by the Department of Defense under contract MDA-9040-2C-0406 is gratefully acknowledged.

SParseval: Evaluation metrics for parsing speech - Roark,B.; Harper,M.; Charniak,E.; Dorr, Bonnie J; Johnson,M.; Kahn,J.; Liu,Y.; Ostendorf,M.; Hale,J.; Krasnyanskaya,A.; others (Proc. LREC, 2006)
While both spoken and written language processing stand to benefit from parsing, the standard Parseval metrics (Black et al., 1991) andtheir canonical implementation (Sekine and Collins, 1997) are only useful for text. The Parseval metrics are undefined when the words input to the parser do not match the words in the gold standard parse tree exactly, and word errors are unavoidable with automatic speech recognition (ASR) systems. To fill this gap, we have developed a publicly available tool for scoring parses that implements a variety of metrics which can handle mismatches in words and segmentations, including: alignment-based bracket evaluation, alignment-based dependency evaluation, and a dependency evaluation that does not require alignment. We describe the different metrics, how to use the tool, and the outcome of an extensive set of experiments on the sensitivity of the metrics.

Spherical and hemispherical microphone arrays for capture and analysis of sound fields - Duraiswami, Ramani; Zhiyun Li; Zotkin,Dmitry N; Grassi,Elena (The Journal of the Acoustical Society of America, 2006)
The capture of the spatial structure of a sound field and analysis is important in many fields including creating virtual environments, source localization and detection, noise suppression, and beamforming. Spherical microphone arrays are a promising development to help achieve such capture and analysis, and have been studied by several groups. We develop a practical spherical microphone array and demonstrate its utility in applications for sound capture, room measurement and for beamforming and tracking. To accommodate equipment failure and manufacturing imprecision we extend their theory to handle arbitrary microphone placement. To handle speech capture and surveillance we describe the development of a new sensor, the hemispherical microphone array. For each array the practical performance follows that predicted by theory. Future applications and improvements are also discussed. [Work supported by NSF.]

A study of translation edit rate with targeted human annotation - Snover,M.; Dorr, Bonnie J; Schwartz,R.; Micciulla,L.; Makhoul,J. (Proceedings of Association for Machine Translation in the Americas, 2006)
We examine a new, intuitive measurefor evaluating machine-translation output that avoids the knowledge intensiveness of more meaning-based approaches, and the labor-intensiveness of human judg- ments. Translation Edit Rate (TER) mea- sures the amount of editing that a hu- man would have to perform to change a system output so it exactly matches a reference translation. We show that the single-reference variant of TER correlates as well with human judgments of MT quality as the four-reference variant of BLEU. We also define a human-targeted TER (or HTER) and show that it yields higher correlations with human judgments than BLEU—even when BLEU is given human-targeted references. Our results in- dicate that HTER correlates with human judgments better than HMETEOR and that the four-reference variants of TER and HTER correlate with human judg- ments as well as—or better than—a sec- ond human judgment does.

Summarization-Inspired Temporal-Relation Extraction: Tense-Pair Templates and Treebank-3 Analysis - Dorr, Bonnie J; Gaasterland,Terry (Department of Computer Science, University of Maryland, College Park, 2006)
This document describes the information used for summarization-inspired temporal-relation extraction [Dorr and Gaasterland, 2007]. We present a set of tense/aspect extraction templates that are applied to a Penn Treebank-style analysis of the input sentence. We also present an analysis of tense-pair combinations for different temporal connectives based on a corpus analysis of complex tense structures in Treebank-3. Finally, we include analysis charts and temporal relation tables for all combinations of intervals/points for each legal BTS combinations.
Keywords: *COMPUTATIONAL LINGUISTICS; CYBERNETICS; linguistics; operations research; TEMPORALRELATION EXTRACTION; TENSE-PAIR COMBINATIONS; TEXT PROCESSING

SYSTEM AND METHOD FOR FAST ILLUMINATION-INVARIANT BACKGROUND SUBTRACTION USING TWO VIEWS - Davis, Larry S.; Lim,S.N.; Mittal,A. (2006)
A method for eliminating errors in foreground object detection in digitized images comprises providing (1101) a reference camera and a secondary camera, vertically aligning each said camera with a baseline that is approximately perpendicular to a ground plane, wherein said reference camera is placed lower than said secondary camera, selecting (1104) a foreground pixel in a reference view of a first point in a foreground object, finding (1105) a conjugate pixel of the foreground pixel in a secondary view, using (1106) the foreground and conjugate pixels to determine an image base pixel of a base point in the reference view, wherein said base point is a point on the ground plane below the first point, and using (1107) the foreground and image base pixels to find a location where the ground plane is first visible.

Task-Driven Video Collection - Lim,Ser-Nam; Mittal,Anuarg; Davis, Larry S. (Technical Reports from UMIACS, 2006)
Vision systems are increasingly being deployed to perform complexsurveillance tasks. While improved algorithms are being developed to perform these tasks, it is also important that data suitable for these algorithms be acquired - a non-trivial task in a dynamic and crowded scene viewed by multiple PTZ cameras. In this paper, we describe a multi-camera system that collects images and videos of moving objects in such scenes, subject to task constraints. The system constructs "task visibility intervals" that contain information about what can be sensed in future time intervals. Constructing these intervals requires prediction of future object motion and consideration of several factors such as object occlusion and camera control parameters. Using a plane-sweep algorithm, these atomic intervals can be combined to form multi-task intervals, during which a single camera can collect videos suitable for multiple tasks simultaneously. Although cameras can then be scheduled based on the constructed intervals, finding an optimal schedule is a typical NP-hard problem. Due to this, and the lack of exact future information in a dynamic environment, we propose several methods for fast camera scheduling that yield solutions within a small constant factor of optimal. Experimental results illustrate system capabilities for both real and more complicated simulated scenarios.
Keywords: Technical Report

Is there a grand challenge or X-prize for data mining? - Piatetsky-Shapiro,Gregory; Grossman,Robert; Djeraba,Chabane; Feldman,Ronen; Getoor, Lise; Zaki,Mohammed (Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006)
This panel will discuss possible exciting and motivating Grand Challenge problems for Data Mining, focusing on bioinformatics, multimedia mining, link mining, text mining, and web mining.
Keywords: Bioinformatics; data mining; grand challenge; image mining; link mining; multimedia mining; text mining; video mining; web mining; X-prize

Top-down, bottom-up multivalued default reasoning for identity maintenance - Shet,Vinay D.; Harwood,David; Davis, Larry S. (Proceedings of the 4th ACM international workshop on Video surveillance and sensor networks, 2006)
Persistent tracking systems require the capacity to track individuals by maintaining identity across visibility gaps caused by occlusion events. In traditional computer vision systems, the flow of information is typically bottom-up. The low level image processing modules take video input, perform early vision tasks such as background subtraction and object detection,and pass this information to the high level reasoning module. This paper describes the architecture of a system that uses top-down information flow to perform identity maintenance across occlusion events. This system uses the high level reasoning module to provide control feedback to the low level image processing module to perform forensic analysis of archival video and actively acquire information required to arrive at identity decisions. This functionality is in addition to traditional bottom-up reasoning about identity, employing contextual cues and appearance matching, within the multivalued default logic framework proposed in [18]. This framework, in addition to bestowing upon the system the property of nonmonotonicity, also allows for it to qualitatively encode its confidence in the identity decisions it takes.
Keywords: default logic; identity maintenance; nonmonotonic reasoning; tracking; visual surveillance

Topology-based reasoning on non-manifold shapes - De Floriani, Leila; Hui,A.; Papaleo,L. (Proceedings of the 1st International Symposium on Shapes and Semantics, Matsushima, Japan, 2006)
Topological information is a promising resource to research in shape-understanding as it provides a high-level description of the characteristics of a shape, and such high-level description often has strong association with the semantics of an object. The Shape Acquisition and Processing (SAP) ontology has been designed to maintain useful information of a model. We propose here an extension to the SAP ontology, that addresses the non-manifold properties of a model. Useful information about the connectivity of an object can be obtained based on an analysis of its non- manifold properties, because the structure of a non-manifold object can be considered as a graph of manifold parts connected together at non-manifold joints. The manifold parts are often pieces that have strong semantic associations. In this work, we describe the type of non-manifold properties, the various types of connected components in a non-manifold object and their semantical significance. We address how the Euler’ characteristics of a non-manifold object can be found based on such information. All such information are extractable from a model using TopMesh, a tool that we have developed. In this work, we also describe the features of TopMesh, namely, all the topological properties it extracts.

Toward an enriched (and revitalized) sense of help: Summary of an ASIS&T 2005 panel session - Haas,Stephanie W; Denn,Sheila; Locke,David; Shneiderman, Ben; Brown,Laurie (Bulletin of the American Society for Information Science and Technology, 2006)

Tracking Articulating Objects from Ground Vehicles using Mixtures of Mixtures - Abd-Almageed, Wael; Hussein,M.; Davis, Larry S. (Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on, 2006)
An algorithm for tracking articulating objects from moving camera platforms is presented. Mixtures of mixtures are used to model the appearance of the object and the background. The state of the object is tracked using a particle filter. Egomotion information are estimated and used to set the state variance of the particle filter. Results of tracking human objects from an unmanned ground vehicle are used to evaluate the tracking algorithm
Keywords: articulating; filter; unmanned; ground; information; mixtures; mixtures; particle; objects; of; operated; tracking; egomotion; vehicle; remotely; vehicles; robot; vision

The Trypanosoma cruzi L1Tc and NARTc non-LTR retrotransposons show relative site specificity for insertion - Bringaud,F.; Bartholomeu,D. C; Blandin,G.; Delcher,A.; Baltz,T.; El‐Sayed, Najib M.; Ghedin,E. (Molecular biology and evolution, 2006)

Very fast optimal bandwidth selection for univariate kernel density estimation - Raykar,Vikas Chandrakant; Duraiswami, Ramani (Technical Reports from UMIACS UMIACS-TR-2005-73, 2006)
Most automatic bandwidth selection procedures for kernel density estimates require estimation of quantities involvingthe density derivatives. Estimation of modes and inflexion points of densities also require derivative estimates. The computational complexity of evaluating the density derivative at M evaluation points given N sample points from the density is O(MN). In this paper we propose a computationally efficient $ε$-exact approximation algorithm for univariate, Gaussian kernel based, density derivative estimation that reduces the computational complexity from O(MN) to linear order (O(N+M)). The constant depends on the desired arbitrary accuracy, $ε$. We apply the density derivative evaluation procedure to estimate the optimal bandwidth for kernel density estimation, a process that is often intractable for large data sets. For example for N = M = 409,600 points while the direct evaluation of the density derivative takes around 12.76 hours the fast evaluation requires only 65 seconds with an error of around $10^{-12)$. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments are presented. We demonstrate the speedup achieved on the bandwidth selection using the ``solve-the-equation plug-in method'' [18]. We also demonstrate that the proposed procedure can be extremely useful for speeding up exploratory projection pursuit techniques.
Keywords: Approximation algorithms; computational statistics; fast gauss transform; kernel density estimation; projection pursuit

Video Retrieval of Near-Duplicates using k-Nearest Neighbor Retrieval of Spatio-Temporal Descriptors - DeMenthon,Daniel; David Doermann (Multimedia Tools and Applications (MTAP), 2006)
This paper describes a novel methodology for implementing video search func- tions such as retrieval of near-duplicate videos and recognition of actions in surveil- lance 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 prop- erties 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, orientation 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 efficient k-nearest neighbor retrieval. The retrieval phase uses video segments as queries. Half-second clips of these queries are again segmented by space-time segmentation 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 differ from the indexed broadcasts by the addition of large overlays. Then we describe experiments in which office 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 of action recognition 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.

View-invariant estimation of height and stride for gait recognition - BenAbdelkader,C.; Cutler, R.; Davis, Larry S. (Biometric Authentication, 2006)
We present a parametric method to automatically identify people in monocular low-resolution video by estimating the height and stride parameters of their walking gait. Stride parameters (stride length and cadence) are functions of body height, weight, and gender. Previous work has demonstrated effective use of these biometrics for identification and verification of people. In this paper, we show that performance is significantly improved by using height as an additional discriminant feature. Height is estimated by robustly segmenting the person from the background and fitting their apparent height to a time-dependent model. This method is correspondence-free and works with low-resolution images of people. It is also view-invariant, albeit performance is optimal in near fronto-parallel configurations. Identification accuracy is estimated at 47% for fronto-parallel sequences of 41 people, and 65% for non-fronto-parallel sequences of 17 people, compared with 18% and 51%, respectively, when only stride and cadence are used.

Visualization Support for Fusing Relational, Spatio-Temporal Data: Building Career Histories - Blythe,Jim; Patwardhan,Mithila; Oates,Tim; desJardins, Marie; Rheingans,Penny (Information Fusion, 2006 9th International Conference on, 2006)
Many real-world domains resist analysis because they are best characterized by a variety of data types, including relational, spatial, and temporal components. Examples of such domains include disease outbreaks, criminal networks, and the World-Wide Web. We present two types of visualizations based on physical metaphors that facilitate fusion, analysis, and deep understanding of relational, spatio-temporal data. The first visualization is based on the metaphor of fluid flow through elastic pipes, and the second on wave propagation. We discuss both types of visualizations in the context of fusing information about the activities of scientists over time with the goal of constructing career histories

Voting with Your Feet: An Investigative Study of the Relationship Between Place Visit Behavior and Preference - Jon Froehlich; Chen,Mike; Smith,Ian; Potter,Fred (UbiComp 2006: Ubiquitous Computing, 2006)
Real world recommendation systems, personalized mobile search, and online city guides could all benefit from data on personal place preferences. However, collecting explicit rating data of locations as users travel from place to place is impractical. This paper investigates the relationship between explicit place ratings and implicit aspects of travel behavior such as visit frequency and travel time. We conducted a four-week study with 16 participants using a novel sensor-based experience sampling tool, called My Experience (Me), which we developed for mobile phones. Over the course of the study Me was used to collect 3,458 in-situ questionnaires on 1,981 place visits. Our results show that, first, sensor-triggered experience sampling is a useful methodology for collecting targeted information in situ. Second, despite the complexities underlying travel routines and visit behavior, there exist positive correlations between place preference and automatically detectable features like visit frequency and travel time. And, third, we found that when combined, visit frequency and travel time result in stronger correlations with place rating than when measured individually. Finally, we found no significant difference in place ratings due to the presence of others.

What are the grand challenges for data mining? - KDD-2006 panel report - Piatetsky-Shapiro,G.; Djeraba,C.; Getoor, Lise; Grossman,R.; Feldman,R.; Zaki,M. (ACM SIGKDD Explorations Newsletter, 2006)
We discuss what makes exciting and motivating Grand Challenge problems for Data Mining, and propose criteria for a good Grand Challenge. We then consider possible GC problems from multimedia mining, link mining, large- scale modeling, text mining, and proteomics. This report is the result of a panel held at KDD-2006 conference.

Will pyramids built of nuggets topple over? - Jimmy Lin; Demner-Fushman,Dina (Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, 2006)
The present methodology for evaluating complex questions at TREC analyzes answers in terms of facts called "nuggets". The official F-score metric represents the harmonic mean between recall and precision at the nugget level. There is an implicit assumption that some facts are more important than others, which is implemented in a binary split between "vital" and "okay" nuggets. This distinction holds important implications for the TREC scoring model---essentially, systems only receive credit for retrieving vital nuggets---and is a source of evaluation instability. The upshot is that for many questions in the TREC testsets, the median score across all submitted runs is zero. In this work, we introduce a scoring model based on judgments from multiple assessors that captures a more refined notion of nugget importance. We demonstrate on TREC 2003, 2004, and 2005 data that our "nugget pyramids" address many shortcomings of the present methodology, while introducing only minimal additional overhead on the evaluation flow.

3D Visualization of Semantic Metadata Models and Ontologies - Charalampos Papamanthou; Tollis, Ioannis G.; Doerr, Martin (Graph Drawing, 2005)
We propose an algorithm for the 3D visualization of general ontology models used in many applications, such as semantic web, entity-relationship diagrams and other database models. The visualization places entities in the 3D space. Previous techniques produce drawings that are 2-dimensional, which are often complicated and hard to comprehend. Our technique uses the third dimension almost exclusively for the display of the isa relationships (links) while the property relationships (links) are placed on some layer (plane). Thus the semantic difference between isa links and property links, which should be as vertical or as horizontal as possible respectively, is emphasized. Special reference is made on a certain model, the CIDOC Conceptual Reference Model.
Keywords: Algorithm Analysis and Problem Complexity; Computer Graphics; Data structures; Discrete Mathematics in Computer Science

Active Constrained Clustering by Examining Spectral Eigenvectors - Xu,Qianjun; desJardins, Marie; Wagstaff,Kiri (Discovery ScienceDiscovery Science, 2005)
This work focuses on the active selection of pairwise constraints for spectral clustering. We develop and analyze a technique for Active Constrained Clustering by Examining Spectral eigenvectorS (ACCESS) derived from a similarity matrix. The ACCESS method uses an analysis based on the theoretical properties of spectral decomposition to identify data items that are likely to be located on the boundaries of clusters, and for which providing constraints can resolve ambiguity in the cluster descriptions. Empirical results on three synthetic and five real data sets show that ACCESS significantly outperforms constrained spectral clustering using randomly selected constraints.

Adaptive OCR with Limited User Feedback - Ma,Huanfeng; David Doermann (8th Int. Conf. on Document Analysis and Recognition (ICDAR'05), 2005)
A methodology is proposed for processing noisy printed documents with limited user feedback. Without the support of ground truth, a specific collection of scanned documents can be processed to extract character templates. The adaptiveness of this approach lies in that the extracted templates are used to train an OCR classifier quickly and with limited user feedback. Experimental results show that this approach is extremely useful for the processing of noisy documents with many touching characters.

Agent-organized networks for dynamic team formation - Gaston,Matthew E.; desJardins, Marie (Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, 2005)
Many multi-agent systems consist of a complex network of autonomous yet interdependent agents. Examples of such networked multi-agent systems include supply chains and sensor networks. In these systems, agents have a select set of other agents with whom they interact based on environmental knowledge, cognitive capabilities, resource limitations, and communications constraints. Previous findings have demonstrated that the structure of the artificial social network governing the agent interactions is strongly correlated with organizational performance. As multi-agent systems are typically embedded in dynamic environments, we wish to develop distributed, on-line network adaptation mechanisms for discovering effective network structures. Therefore, within the context of dynamic team formation, we propose several strategies for agent-organized networks (AONs) and evaluate their effectiveness for increasing organizational performance.
Keywords: multi-agent systems; organizational learning; team formation

Agent-organized networks for multi-agent production and exchange - Gaston,Matthew E.; desJardins, Marie (Proceedings of the 20th national conference on Artificial intelligence - Volume 1, 2005)
As multi-agent systems grow in size and complexity, social networks that govern the interactions among the agents will directly impact system behavior at the individual and collective levels. Examples of such large-scale, networked multi-agent systems include peer-to-peer networks, distributed information retrieval, and agent-based supply chains. One way of dealing with the uncertain and dynamic nature of such environments is to endow agents with the ability to modify the agent social network by autonomously adapting their local connectivity structure. In this paper, we present a framework for agent-organized networks (AONs) in the context of multi-agent production and exchange, and experimentally evaluate the feasibility and efficiency of specific AON strategies. We find that decentralized network adaptation can significantly improve organizational performance. Additionally, we analyze several properties of the resulting network structures and consider their relationship to the observed increase in organizational performance.

Algorithmic graph minor theory: Decomposition, approximation, and coloring - Demaine,E. D; Hajiaghayi, Mohammad T.; Kawarabayashi,K. (Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, 2005)
At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.
Keywords: algorithmic graph minor theory; approximation algorithm; combinatorial polylogarithmic approximation; computational complexity; constant-factor approximation; graph algorithm; graph coloring; graph colouring; half-integral multicommodity flow; largest grid minor; maximization problem; minimization problem; polynomial-time algorithm; subexponential fixed-parameter algorithm; topological graph theory; treewidth

Alignment link projection using transformation-based learning - Ayan,Necip Fazil; Dorr, Bonnie J; Monz,Christof (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)
We present a new word-alignment approach that learns errors made by existing word alignment systems and corrects them. By adapting transformation-based learning to the problem of word alignment, we project new alignment links from already existing links, using features such as POS tags. We show that our alignment link projection approach yields a significantly lower alignment error rate than that of the best performing alignment system (22.6% relative reduction on English-Spanish data and 23.2% relative reduction on English-Chinese data).

AParallel-Line Detection Algorithm Based on HMMDecoding - Yefeng Zheng; Huiping Li; David Doermann (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005)
The detection of groups of parallel lines is important in applications such as form processing and text (handwriting) extraction from 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 (such as skew correction and text filtering), we use trained Hidden Markov Models (HMM) to locate the optimal positions of all lines simultaneously on the horizontal or vertical projection profiles, based on the Viterbi decoding. The algorithm is trainable so it can be easily adapted to different application scenarios. The experiments conducted on known form processing and rule line detection show our method is robust, and achieves better results than other widely used line detection methods.

Approximate expressions for the mean and the covariance of the maximum likelihood estimator for acoustic source localization - Raykar,V.C.; Duraiswami, Ramani (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
Acoustic source localization using multiple microphones can be formulated as a maximum likelihood estimation problem. The estimator is implicitly defined as the minimum of a certain objective function. As a result, we cannot get explicit expressions for the mean and the covariance of the estimator. We derive approximate expressions for the mean vector and covariance matrix of the estimator using Taylor's series expansion of the implicitly defined estimator. The validity of our expressions is verified by Monte-Carlo simulations. We also study the performance of the estimator for different microphone array configurations.
Keywords: (mathematics); acoustic; approximate; approximation; array; array; covariance; estimation; expansion; expressions; function; likelihood; localization; matrices; matrix; maximum; mean; microphone; objective; processing; series; signal; source; Taylor; theory; vector; vectors

Architecting and Implementing Versatile Dependability - Tudor Dumitras; Srivastava, Deepti; Narasimhan, Priya (Architecting Dependable Systems III, 2005)
Distributed applications must often consider and select the appropriate trade-offs among three important aspects – fault-tolerance, performance and resources. We introduce a novel concept, called versatile dependability, that provides a framework for analyzing and reasoning about these trade-offs in dependable software architectures. We present the architecture of a middleware framework that implements versatile dependability by providing the appropriate ”knobs” to tune and re-calibrate the trade-offs. Our framework can adjust the properties and the behavior of the system at development-time, at deployment-time, and throughout the application’s life-cycle. This renders the versatile dependability approach useful both to applications that require static fault-tolerance configurations supporting the loss/addition of resources and changing workloads, as well as to applications that evolve in terms of their dependability requirements. Through a couple of specific examples, one on adapting the replication style at runtime and the other on tuning the system scalability under given constraints, we demonstrate concretely how versatile dependability can provide an extended coverage of the design space of dependable distributed systems.
Keywords: Operating systems; software engineering

Background updating for visual surveillance - Kim,K.; Harwood,D.; Davis, Larry S. (Advances in Visual Computing, 2005)
Scene changes such as moved objects, parked vehicles, or opened/closed doors need to be carefully handled so that interesting foreground targets can be detected along with the short-term background layers created by those changes. A simple layered modeling technique is embedded into a codebook-based background subtraction algorithm to update a background model. In addition, important issues related to background updating for visual surveillance are discussed. Experimental results on surveillance examples, such as unloaded packages and unattended objects, are presented by showing those objects as short-term background layers.

Bayesian filtering and integral image for visual tracking - Han,B.; Yang,C.; Duraiswami, Ramani; Davis, Larry S. (Proceedings of the Worshop on Image Analysis for Multimedia Interactive Services (WIAMIS'05), 2005)
This paper describes contributions to two problems related tovisual tracking: control model design and observation process design. We describe the use of kernel-based Bayesian filtering for the tracking control procedure, and feature-based tracking to improve the observation process of tracking. In the kernel- based Bayesian filtering framework, the analytical represen- tation of density functions by density interpolation and density approximation for the likelihood and the posterior contributes to efficient sampling. Feature-based tracking combines rec- tangular features with edge oriented histogram so that the combined features are robust to illumination changes, partial occlusion, and clutter while capturing the spatial information of the target. The use of integral image allows the features to be efficiently evaluated. The effectiveness of both algorithms are demonstrated by object tracking results on real videos.

Bayesian network learning with abstraction hierarchies and context-specific independence - desJardins, Marie; Rathod,P.; Getoor, Lise (Machine Learning: ECML 2005, 2005)
Context-specific independence representations, such as tree-structured conditional probability tables (TCPTs), reduce the number of parameters in Bayesian networks by capturing local independence relationships and improve the quality of learned Bayesian networks. We previously presented Abstraction-Based Search (ABS), a technique for using attribute value hierarchies during Bayesian network learning to remove unimportant distinctions within the CPTs. In this paper, we introduce TCPT ABS (TABS), which integrates ABS with TCPT learning. Since expert-provided hierarchies may not be available, we provide a clustering technique for deriving hierarchies from data. We present empirical results for three real-world domains, finding that (1) combining TCPTs and ABS provides a significant increase in the quality of learned Bayesian networks (2) combining TCPTs and ABS provides a dramatic reduction in the number of parameters in the learned networks, and (3) data-derived hierarchies perform as well or better than expert-provided hierarchies.