Bayesian summarization at DUC and a suggestion for extrinsic evaluation - Daumé, Hal; Marcu,D. (Document understanding conference, 2005)

Camera-Based Analysis of Text and Documents: ASurvey - Liang,Jian; David Doermann; Huiping Li (International Journal on Document Analysis and Recognition, 2005)

The Challenge of Personal Information Management - Dix,A.; Jones,W.; Czerwinski,M.; Teevan,J.; Plaisant, Catherine; Moran,TP (INTERACT'05: Communicating Naturally through Computers (Adjunct Proceedings), 2005)

Child's play: a comparison of desktop and physical interactive environments - Fails,J. A; Druin, Allison; Guha,M.L.; Chipman,G.; Simms,S.; Churaman,W. (Proceedings of the 2005 conference on Interaction design and children, 2005)

Chosen-ciphertext security of multiple encryption - Dodis,Y.; Katz, Jonathan (Theory of Cryptography, 2005)
Encryption of data using multiple, independent encryption schemes (“multiple encryption”) has been suggested in a variety of contexts, and can be used, for example, to protect against partial key exposure or cryptanalysis, or to enforce threshold access to data. Most prior work on this subject has focused on the security of multiple encryption against chosen-plaintext attacks, and has shown constructions secure in this sense based on the chosen-plaintext security of the component schemes. Subsequent work has sometimes assumed that these solutions are also secure against chosen-ciphertext attacks when component schemes with stronger security properties are used. Unfortunately, this intuition is false for all existing multiple encryption schemes.Here, in addition to formalizing the problem of chosen-ciphertext security for multiple encryption, we give simple, efficient, and generic constructions of multiple encryption schemes secure against chosen-ciphertext attacks (based on any component schemes secure against such attacks) in the standard model. We also give a more efficient construction from any (hierarchical) identity-based encryption scheme secure against selective-identity chosen plaintext attacks. Finally, we discuss a wide range of applications for our proposed schemes.

Closely coupled object detection and segmentation - Zhao, L.; Davis, Larry S. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
We propose a closely coupled object detection and segmentation algorithm for enhancing both processes in a cooperative and iterative manner. Figure-ground segmentation reduces the effect of background clutter on template matching; the matched template provides shape constraints on segmentation. More precisely, we estimate the probability of each pixel belonging to the foreground by a weighted sum of the estimates based on shape and color alone. The weight on the shape-based estimate is related to the probability that a familiar object is present and is updated dynamically so that we enforce shape constraints only where the object is present. Experiments on detecting people in images of cluttered scenes demonstrate that the proposed algorithm improves both segmentation and detection. More accurate object boundaries are extracted; higher object detection rates and lower false alarm rates are achieved than performing the two processes separately or sequentially.

Clustering Techniques for Out-of-Core Multi-resolution Modeling - Danovaro,Emanuele; De Floriani, Leila; Puppo,Enrico; Samet, Hanan (Visualization Conference, IEEE, 2005)
Thanks to improvements in simulation tools, high resolution scanning facilities and multidimensional medical imaging, huge datasets are commonly available. Multi-resolution models manage the complexity of such data sets, by varying resolution and focusing detail in specific areas of interests. Since many currently available data sets cannot fit in main memory, the need arises to design data structures, construction and query algorithms for multi-resolution models which work in secondary memory.

Comparative Genomics of Trypanosomatid Parasitic Protozoa - El‐Sayed, Najib M.; Myler,Peter J.; Blandin,Gaëlle; Berriman,Matthew; Crabtree,Jonathan; Aggarwal,Gautam; Caler,Elisabet; Renauld,Hubert; Worthey,Elizabeth A.; Hertz-Fowler,Christiane; Ghedin,Elodie; Peacock,Christopher; et al. (Science, 2005)
A comparison of gene content and genome architecture of Trypanosoma brucei, Trypanosoma cruzi, and Leishmania major, three related pathogens with different life cycles and disease pathology, revealed a conserved core proteome of about 6200 genes in large syntenic polycistronic gene clusters. Many species-specific genes, especially large surface antigen families, occur at nonsyntenic chromosome-internal and subtelomeric regions. Retroelements, structural RNAs, and gene family expansion are often associated with syntenic discontinuities that—along with gene divergence, acquisition and loss, and rearrangement within the syntenic regions—have shaped the genomes of each parasite. Contrary to recent reports, our analyses reveal no evidence that these species are descended from an ancestor that contained a photosynthetic endosymbiont.

Comparison of the Efficiency of Translation Operators Used in the Fast Multipole Method for the 3D Laplace Equation - Gumerov, Nail A.; Duraiswami, Ramani (Technical Reports from UMIACS UMIACS-TR–2005-09, 2005)
We examine the practical implementation of a fast multipole method algorithm for the rapid summation of Laplace multipoles. Several translation operators with different asymptotic computational and memory complexities have been proposed for this problem. These algorithms include: Method 0 — the originally proposed matrix based translations due to Greengard andRokhlin (1987), Method 1 — the rotation, axial translation and rotation algorithm due to White and Martin Head-Gordon (1993), and Method 3 — the plane-wave version of the multipole-to local translation operator due to Greengard and Rokhlin (1997). We compare the algorithms on data sets of varying size and with varying imposed accuracy requirements. While from the literature it would have been expected that method 2 would always be the method of choice, at least as far as computational speed is concerned, we find that this is not always the case. We find that as far as speed is concerned the choice between methods 1 and 2 depends on problem size and error requirements. Method 2 is the algorithm of choice for large problems where high accuracy is required, though the advantage is not clear cut, especially if memory requirements are an issue. If memory is an issue, Method 1 is the method of choice for most problems. A new analysis of the computational complexities of the algorithms is provided, which explains the observed results. We provide guidelines for choosing parameters for FMM algorithms.
Keywords: Fast Algorithms; Fast Multipole Method; Harmonic analysis; Laplace Equation in 3D; Translation operators

Computation of scattering from clusters of spheres using the fast multipole method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2005)

Computation of scattering from clusters of spheres using the fast multipole method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2005)
A T-matrix based method of solution of the multiple scattering problem was presented by the authors [J. Acoust Soc. Am. 112, 2688–2701 (2002)]. This method can be applied to the computation of relatively small problems, since the number of operations required grows with the number of spheres N as O(N3), and with the sixth power of the wave number. The use of iterative techniques accelerated using the fast multipole method (FMM) can accelerate this solution, as presented by Koc and Chew [J. Acoust. Soc. Am. 103, 721–734 (1998)] originally. In this study we present a method that combines preconditioned Krylov subspace iterative techniques, FMM accelerated matrix vector products, a novel FMM-based preconditioner, and fast translation techniques that enable us to achieve an overall algorithm in which the cost of the matrix-vector multiplication grows with N as O(N log N) and with the third power of the wave number. We discuss the convergence of the iterative techniques, selection of the truncation number, errors in the solution, and other issues. The results of the solution of test problems obtained with the method for N ∼ 102–104 for different wave numbers are presented. © 2005 Acoustical Society of America.
Keywords: acoustic wave scattering; convergence of numerical methods; iterative methods; matrix multiplication

Constrained spectral clustering under a local proximity structure assumption - Xu,Q.; desJardins, Marie (In Proceedings of the 18th International Conference of the Florida Artificial Intelligence Research Society (FLAIRS-05), 2005)
This work focuses on incorporating pairwise constraints into a spectral clustering algorithm. A new constrained spectral clustering method is proposed, as well as an active constraint acquisition technique and a heuristic for parameter selection. We demonstrate that our constrained spectral clustering method, CSC, works well when the data exhibits what we term local proximity structure. Empirical results on synthetic and real data sets show that CSC outperforms two other constrained clustering algorithms.

Constructing task visibility intervals for a surveillance system - Lim,Ser-Nam; Mittal,Anurag; Davis, Larry S. (Proceedings of the third ACM international workshop on Video surveillance & sensor networks, 2005)
One of the goals of a multi-camera surveillance system is to collect useful video clips of objects in the scene. Objects in the collected videos should be unobstructed, in the field of view of the given camera, and meet task-specific resolution requirement. For this purpose, we describe an algorithm that constructs "task visibility intervals", which are tuples of information about what to sense (task-object pairs), when to sense (feasible future temporal intervals to start a task) and how to sense (the camera to use and the corresponding viewing angles and focal length). The algorithm first looks for temporal intervals within which the angular extents of objects overlap each other, causing the object farthest from the given camera to be occluded. Outside these intervals, sub-intervals are then constructed such that feasible camera settings exist for capturing the object. Experimental results are provided to illustrate the system capabilities in constructing such task visibility intervals, followed by scheduling them using a greedy algorithm.
Keywords: scheduling; sensor

Data Redistribution and Remote Method Invocation in Parallel Component Architectures - Bertrand,Felipe; Bramley,Randall; Sussman, Alan; Bernholdt,David E.; Kohl,James A.; Larson,Jay W.; Damevski,Kostadin B. (Parallel and Distributed Processing Symposium, International, 2005)
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.

Data structures for simplicial complexes: an analysis and a comparison - De Floriani, Leila; Hui,Annie (Proceedings of the third Eurographics symposium on Geometry processing, 2005)
In this paper, we review, analyze and compare representations for simplicial complexes. We classify such representations, based on the dimension of the complexes they can encode, into dimension-independent structures, and data structures for three- and for two-dimensional simplicial complexes. We further classify the data structures in each group according to the basic kinds of the topological entities they represent. We present a description of each data structure in terms of the entities and topological relations encoded, and we evaluate it based on its expressive power, on its storage cost and on the efficiency in supporting navigation inside the complex, i.e., in retrieving topological relations not explicitly encoded. We compare the various data structures inside each category based on the above features.

DD-PREF: A language for expressing preferences over sets - desJardins, Marie (In AAAI-05, 2005)
In many application domains, it is useful to be able to represent and reason about a user’s preferences over sets of objects. We present a representation language, DD-PREF (for Diversity and Depth PREFerences), for specifying the desired diversity and depth of sets of objects where each object is represented as a vector of feature values. A strong diversity preference for a particular feature indicates that the user would like the set to include objects whose values are evenly dispersed across the range of possible values for that feature. A strong depth preference for a feature indicates that the user is interested in specific target values or ranges. Diversity and depth are complementary, but are not necessarily opposites. We define an objective function that, when maximized, identifies the subset of objects that best satisfies a statement of preferences in DD-PREF. Exhaustively searching the space of all possible subsets is intractable for large problem spaces; therefore, we also present an efficient greedy algorithm for generating preferred object subsets. We demonstrate the expressive power of DD-PREF and the performance of our greedy algorithm by encoding and applying qualitatively different preferences for multiple tasks on a blocks world data set. Finally, we provide experimental results for a collection of Mars rover images, demonstrating that we can successfully capture individual preferences of different users, and use them to retrieve high-quality image subsets.

Detecting rotational symmetries - Shiv Naga Prasad,V.; Davis, Larry S. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
We present an algorithm for detecting multiple rotational symmetries in natural images. Given an image, its gradient magnitude field is computed, and information from the gradients is spread using a diffusion process in the form of a gradient vector flow (GVF) field. We construct a graph whose nodes correspond to pixels in tire image, connecting points that are likely to be rotated versions of one another The n-cycles present in tire graph are made to vote for Cn symmetries, their votes being weighted by the errors in transformation between GVF in the neighborhood of the voting points, and the irregularity of the n-sided polygons formed by the voters. The votes are accumulated at tire centroids of possible rotational symmetries, generating a confidence map for each order of symmetry. We tested the method with several natural images.
Keywords: axial; computational; detection; field; flow; geometry; gradient; graph; graph; image; image; magnitude; methods; multiple; n-sided; object; polygons; recognition; rotational; symmetries; symmetry; theory; tire; tyres; vector

Detection, analysis and matching of hair - Yacoob,Yaser; Davis, Larry S. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
We develop computational models for measuring hair appearance for comparing different people. The models and methods developed have applications to person recognition and face 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 dataset 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: automatic hair detection; eigenface-based recognition; eigenface-hair based identification; Eigenvalues and eigenfunctions; face image indexing; face recognition; Feature extraction; hair analysis; hair appearance; hair attributes; hair matching; Image matching; image representation; multidimensional representation; person recognition

Distributed Algorithms for Dynamic Survivability of Multiagent Systems - Subrahmanian,V.; Kraus,Sarit; Zhang,Yingqian (Computational Logic in Multi-Agent SystemsComputational Logic in Multi-Agent Systems, 2005)
Though multiagent systems (MASs) are being increasingly used, few methods exist to ensure survivability of MASs. All existing methods suffer from two flaws. First, a centralized survivability algorithm (CSA) ensures survivability of the MAS – unfortunately, if the node on which the CSA exists goes down, the survivability of the MAS is questionable. Second, no mechanism exists to change how the MAS is deployed when external factors trigger a re-evaluation of the survivability of the MAS. In this paper, we present three algorithms to address these two important problems. Our algorithms can be built on top of any CSA. Our algorithms are completely distributed and can handle external triggers to compute a new deployment. We report on experiments assessing the efficiency of these algorithms.
Keywords: Computer; Science

DOCLIB: A document processing research tool - Chen,Kevin; Jaeger,Stefan; Zhu,Guangyu; David Doermann (Symposium on Document Image Understanding Technology, 2005)
Often, valuable document processing intellectual capital is lost due to staff transitions or project restructuring prior to technology transfer. Furthermore, hardware and software integrity, dependencies, and compatibility are critical components that often impede technology migration. While many open source tools attempt to mitigate these issues, they do not always address specific design needs and tailored-process that Government organizations must adhere to. This paper addresses the need for a common document processing research vehicle through which institutions can develop and share research-related software and applications across academic, business, and Government domains.

Document Ranking by Layout Relevance - Huang,Mei; DeMenthon,Daniel; David Doermann; Golebiowski,Lynn (ICDAR, 2005)
This paper describes the development of a new document ranking system based on layout similarity. The user has a need represented by a set of ”wanted” documents, and the system ranks documents in the collection according to this need. Rather than performing complete document analysis, the system extracts text lines, and models layouts as relationships between pairs of these lines. This paper explores three novel feature sets to support scoring in large document collections. First, pairs of lines are used to form quadrilaterals, which are represented by their turning functions. A non- Euclidean distance is used to measure similarity. Second, the quadrilaterals are represented by 5DEuclidean vectors, and third, each line is represented by a 5DEuclidean vector. We compare the classification performance and computation speed of these three feature sets using a large database of diverse documents including forms, academic papers and handwritten pages in English and Arabic. The approach using quadrilaterals and turning functions produces slightly better results, but the approach using vectors to represent text lines is much faster for large document databases.

Doubleshot: an interactive user-aided segmentation tool - Tom Yeh; Darrell,Trevor (Proceedings of the 10th international conference on Intelligent user interfaces, 2005)
In this paper, we describe an intelligent user interface designed for camera phones to allow mobile users to specify the object of interest in the scene simply by taking two pictures: one with the object and one without the object. By comparing these two images, the system can reliably extract the visual appearance of the object, which can be useful to a wide-range of applications such as content-based image retrieval and object recognition.
Keywords: Computer vision; mobile application; Object recognition

Dynamic Queries and Brushing on Choropleth Maps (2001) - Dang,Gunjan; North,Chris; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Users who must combine demographic, economic or other data in a geographic context are often hampered by the integration of tabular and map representations. Static, paper-based solutions limit the amount of data that can be placed on a single map or table. By providing an effective user interface, we believe that researchers, journalists, teachers, and students can explore complex data sets more rapidly and effectively. This paper presents Dynamaps, a generalized map-based information-visualization tool for dynamic queries and brushing on choropleth maps. Users can use color coding to show a variable on each geographic region, and then filter out areas that do not meet the desired criteria. In addition, a scattergram view and a detailson- demand window support overviews and specific fact finding.
Keywords: Technical Report

Efficient kernel machines using the improved fast Gauss transform - Yang,C.; Duraiswami, Ramani; Davis, Larry S. (Advances in neural information processing systems, 2005)
The computation and memory required for kernel machines with N train- ing samples is at least O(N 2). Such a complexity is significant even for moderate size problems and is prohibitive for large datasets. We present an approximation technique based on the improved fast Gauss transform to reduce the computation to O(N ). We also give an error bound for the approximation, and provide experimental results on the UCI datasets.

Efficient mean-shift tracking via a new similarity measure - Yang,Changjiang; Duraiswami, Ramani; Davis, Larry S. (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
The mean shift algorithm has achieved considerable success in object tracking due to its simplicity and robustness. It finds local minima of a similarity measure between the color histograms or kernel density estimates of the model and target image. The most typically used similarity measures are the Bhattacharyya coefficient or the Kullback-Leibler divergence. In practice, these approaches face three difficulties. First, the spatial information of the target is lost when the color histogram is employed, which precludes the application of more elaborate motion models. Second, the classical similarity measures are not very discriminative. Third, the sample-based classical similarity measures require a calculation that is quadratic in the number of samples, making real-time performance difficult. To deal with these difficulties we propose a new, simple-to-compute and more discriminative similarity measure in spatial-feature spaces. The new similarity measure allows the mean shift algorithm to track more general motion models in an integrated way. To reduce the complexity of the computation to linear order we employ the recently proposed improved fast Gauss transform. This leads to a very efficient and robust nonparametric spatial-feature tracking algorithm. The algorithm is tested on several image sequences and shown to achieve robust and reliable frame-rate tracking.
Keywords: algorithm; analysis; Bhattacharyya; coefficient; Color; colour; density; divergence; estimates; extraction; fast; feature; frame-rate; Gauss; Gaussian; histograms; image; Kernel; Kullback-Leibler; matching; Mean-shift; measures; nonparametric; processes; sample-based; sequences; similarity; spaces; spatial-feature; tracking; tracking; transform

Envisioning help resources for the future information ecology: Toward an enriched sense of help - Haas,Stephanie W; Brown,Laurie; Denn,Sheila; Locke,David; Shneiderman, Ben (Proceedings of the American Society for Information Science and Technology, 2005)

Evaluating Summaries and Answers: Two Sides of the Same Coin? - Jimmy Lin; Demner-Fushman,D. (Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, 2005)
This paper discusses the convergencebetween question answering and multi- document summarization, pointing out implications and opportunities for knowl- edge transfer in both directions. As a case study in one direction, we discuss the recent development of an automatic method for evaluating definition questions based on n-gram overlap, a commonly- used technique in summarization evalua- tion. In the other direction, the move to- wards topic-oriented summaries requires an understanding of relevance and topi- cality, issues which have received atten- tion in the question answering literature. It is our opinion that question answering and multi-document summarization repre- sent two complementary approaches to the same problem of satisfying complex user information needs. Although this points to many exciting opportunities for system- building, here we primarily focus on im- plications for system evaluation.

An evolutionary testbed for software technology evaluation - Lindvall,M.; Rus,I.; Shull, F.; Zelkowitz, Marvin V; Donzelli,P.; Memon, Atif M.; Basili, Victor R.; Costa,P.; Tvedt,R.; Hochstein, L. (Innovations in Systems and Software Engineering, 2005)
Empirical evidence and technology evaluation are needed to close the gap between the state of the art and the state of the practice in software engineering. However, there are difficulties associated with evaluating technologies based on empirical evidence: insufficient specification of context variables, cost of experimentation, and risks associated with trying out new technologies. In this paper, we propose the idea of an evolutionary testbed for addressing these problems. We demonstrate the utility of the testbed in empirical studies involving two different research technologies applied to the testbed, as well as the results of these studies. The work is part of NASArsquos High Dependability Computing Project (HDCP), in which we are evaluating a wide range of new technologies for improving the dependability of NASA mission-critical systems.

Exploiting Correlated Attributes in Acquisitional Query Processing - Deshpande, Amol; Guestrin,C.; Wei Hong; Madden,S. (21st International Conference on Data Engineering, 2005. ICDE 2005. Proceedings, 2005)
Sensor networks and other distributed information systems (such as the Web) must frequently access data that has a high per-attribute acquisition cost, in terms of energy, latency, or computational resources. When executing queries that contain several predicates over such expensive attributes, we observe that it can be beneficial to use correlations to automatically introduce low-cost attributes whose observation will allow the query processor to better estimate the selectivity of these expensive predicates. In particular, we show how to build conditional plans that branch into one or more sub-plans, each with a different ordering for the expensive query predicates, based on the runtime observation of low-cost attributes. We frame the problem of constructing the optimal conditional plan for a given user query and set of candidate low-cost attributes as an optimization problem. We describe an exponential time algorithm for finding such optimal plans, and describe a polynomial-time heuristic for identifying conditional plans that perform well in practice. We also show how to compactly model conditional probability distributions needed to identify correlations and build these plans. We evaluate our algorithms against several real-world sensor-network data sets, showing several-times performance increases for a variety of queries versus traditional optimization techniques.
Keywords: acquisitional query processing; Computer networks; Costs; data acquisition; Delay; Distributed computing; distributed information system; Distributed information systems; distributed processing; exponential time algorithm; optimization techniques; polynomial-time heuristic; Polynomials; probability; Query processing; real-time systems; real-world sensor-network; Runtime; Sensor phenomena and characterization; Sensor systems

Extracting regions of symmetry - Gupta,A.; Prasad,V. S.N; Davis, Larry S. (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
This paper presents an approach for extending the normalized-cut (n-cut) segmentation algorithm to find symmetric regions present in natural images. We use an existing algorithm to quickly detect possible symmetries present in an image. The detected symmetries are then individually verified using the modified n-cut algorithm to eliminate spurious detections. The weights of the n-cut algorithm are modified so as to include both symmetric and spatial affinities. A global parameter is defined to model the tradeoff between spatial coherence and symmetry. Experimental results indicate that symmetric quality measure for a region segmented by our algorithm is a good indicator for the significance of the principal axis of symmetry.
Keywords: algorithm; coherence; DETECTION; detection; elimination; extraction; feature; image; images; natural; normalized-cut; object; region; segmentation; segmentation; spatial; spurious; symmetry

Extracting the frequencies of the pinna spectral notches in measured head related impulse responses - Raykar,Vikas C.; Duraiswami, Ramani; Yegnanarayana,B. (The Journal of the Acoustical Society of America, 2005)
The head related impulse response (HRIR) characterizes the auditory cues created by scattering of sound off a person’s anatomy. The experimentally measured HRIR depends on several factors such as reflections from body parts (torso, shoulder, and knees), head diffraction, and reflection/diffraction effects due to the pinna. Structural models (Algazi et al., 2002; Brown and Duda, 1998) seek to establish direct relationships between the features in the HRIR and the anatomy. While there is evidence that particular features in the HRIR can be explained by anthropometry, the creation of such models from experimental data is hampered by the fact that the extraction of the features in the HRIR is not automatic. One of the prominent features observed in the HRIR, and one that has been shown to be important for elevation perception, are the deep spectral notches attributed to the pinna. In this paper we propose a method to robustly extract the frequencies of the pinna spectral notches from the measured HRIR, distinguishing them from other confounding features. The method also extracts the resonances described by Shaw (1997). The techniques are applied to the publicly available CIPIC HRIR database (Algazi et al., 2001c). The extracted notch frequencies are related to the physical dimensions and shape of the pinna.
Keywords: acoustic wave reflection; acoustic wave scattering; anthropometry; Ear; hearing; physiological models

A fast approximation scheme for probabilistic wavelet synopses - Deligiannakis,A.; Garofalakis,M.; Roussopoulos, Nick (Proceedings of the 17th International Conference on Scientific and Statistical Database Management (SSDBM), 2005)

Fast Camera Motion Estimation for Hand-Devices and Applications - Liu,Xu; David Doermann; Huiping Li (4th International Conference on Mobile and Ubiquitous Multimedia, 2005)
In this paper we present an efficient motion estimation algorithm for camera-enabled handheld devices, such as mobile phones and PDAs. Compared to general camera motion estimation, the estimation of ego-motion of handheld devices presents unique challenges because most devices are limited in resources (processing power, memory and battery). The algorithm must be lightweight so it can be efficiently embedded and run fast enough to produce smooth seamless translation. Our solution includes a multi-resolution scheme which searches the match from coarse to fine; and optimization of the search space. As a demonstration, we implemented the algorithm on the Symbian based Nokia 3650/6600 camera phone, and explored several interesting applications, including using camera motion for browsing documents and as a pointing device. A cross-platform implementation is also discussed.

Fast Computation of Sums of Gaussians in High Dimensions - Raykar,Vikas Chandrakant; Yang,Changjaing; Duraiswami, Ramani; Gumerov, Nail A. (Technical Reports from UMIACS UMIACS-TR-2005-69, 2005)
Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computational statistics andmachine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel functions and the evaluation points. The fast Gauss transform proposed by Greengard and Strain (1991) is a $ε$-exact approximation algorithm that reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points in $d$ dimensions from $\mathcal{O}(MN)$ to $\mathcal{O}(M+N)$. However, the constant factor in $\mathcal{O}(M+N)$ grows exponentially with increasing dimensionality $d$, which makes the algorithm impractical for dimensions greater than three. In this paper we present a new algorithm where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor's series expansion (which can act both as a local as well as a far field expansion) scheme combined with the efficient space subdivision using the $k$-center algorithm. The proposed method differs from the original fast Gauss transform in terms of a different factorization, efficient space subdivision, and the use of point-wise error bounds. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments are presented. As an example we shows how the proposed method can be used for very fast $ε$-exact multivariate kernel density estimation.
Keywords: Technical Report

Fast illumination-invariant background subtraction using two views: error analysis, sensor placement and applications - Lim,Ser-Nam; Mittal,A.; Davis, Larry S.; Paragios,N. (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
Background modeling and subtraction to detect new or moving objects in a scene is an important component of many intelligent video applications. Compared to a single camera, the use of multiple cameras leads to better handling of shadows, specularities and illumination changes due to the utilization of geometric information. Although the result of stereo matching can be used as the feature for detection, it has been shown that the detection process can be made much faster by a simple subtraction of the intensities observed at stereo-generated conjugate pairs in the two views. The methodology however, suffers from false and missed detections due to some geometric considerations. In this paper, we perform a detailed analysis of such errors. Then, we propose a sensor configuration that eliminates false detections. Algorithms are also proposed that effectively eliminate most detection errors due to missed detections, specular reflections and objects being geometrically close to the background. Experiments on several scenes illustrate the utility and enhanced performance of the proposed approach compared to existing techniques.
Keywords: analysis; application; background; cameras; configuration; DETECTION; detection; error; error; extraction; false; feature; handling; illumination-invariance; image; intelligent; matching; modeling; object; placement; processing; sensor; sensors; shadow; stereo; subtraction; video

Fast multiple object tracking via a hierarchical particle filter - Yang,Changjiang; Duraiswami, Ramani; Davis, Larry S. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
A very efficient and robust visual object tracking algorithm based on the particle filter is presented. The method characterizes the tracked objects using color and edge orientation histogram features. While the use of more features and samples can improve the robustness, the computational load required by the particle filter increases. To accelerate the algorithm while retaining robustness we adopt several enhancements in the algorithm. The first is the use of integral images for efficiently computing the color features and edge orientation histograms, which allows a large amount of particles and a better description of the targets. Next, the observation likelihood based on multiple features is computed in a coarse-to-fine manner, which allows the computation to quickly focus on the more promising regions. Quasi-random sampling of the particles allows the filter to achieve a higher convergence rate. The resulting tracking algorithm maintains multiple hypotheses and offers robustness against clutter or short period occlusions. Experimental results demonstrate the efficiency and effectiveness of the algorithm for single and multiple object tracking.
Keywords: (numerical; algorithm; analysis; Color; colour; Computer; Convergence; detection; edge; fast; filter; Filtering; hierarchical; histogram; image; images; integral; likelihood; methods); methods; multiple; numerical; object; observation; of; orientation; particle; processes; quasirandom; random; sampling; tracking; tracking; vision; visual

Fast Multipole Method for the Biharmonic Equation - Gumerov, Nail A.; Duraiswami, Ramani (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2005)
The evaluation of sums (matrix-vector products) of the solutions ofthe 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. Compared to previous methods that required the translation of five Laplace elementary solutions for the biharmonic Green's function, and much larger numbers for higher order multipoles, our method is significantly 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\ is faster than direct solution for a matrix size of $550$ for an accuracy of $10^{-3},$ 950 for an accuracy of $10^{-6} and $N=3550$ for an accuracy of $10^{-9}$.
Keywords: Technical Report

Fault-Tolerant Middleware and the Magical 1% - Tudor Dumitras; Narasimhan, Priya (Middleware 2005, 2005)
Through an extensive experimental analysis of over 900 possible configurations of a fault-tolerant middleware system, we present empirical evidence that the unpredictability inherent in such systems arises from merely 1% of the remote invocations. The occurrence of very high latencies cannot be regulated through parameters such as the number of clients, the replication style and degree or the request rates. However, by selectively filtering out a “magical 1%” of the raw observations of various metrics, we show that performance, in terms of measured end-to-end latency and throughput, can be bounded, easy to understand and control. This simple statistical technique enables us to guarantee, with some level of confidence, bounds for percentile-based quality of service (QoS) metrics, which dramatically increase our ability to tune and control a middleware system in a predictable manner.
Keywords: Computer Communication Networks; Information Systems Applications (incl.Internet); Operating systems; Programming Languages, Compilers, Interpreters; Programming Techniques; software engineering

Finite-State Language resources and Language Processing - Hale,K.; Keyser,S.J.; Hutchins,W.J.; Habash,N.; Dorr, Bonnie J; Traum,D. (Machine Translation, 2005)

Flattening curved documents in images - Liang,Jian; DeMenthon,D.; David Doermann (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
Compared to scanned images, document pictures captured by camera can suffer from distortions due to perspective and page warping. It is necessary to restore a frontal planar view of the page before other OCR techniques can be applied. In this paper we describe a novel approach for flattening a curved document in a single picture captured by an uncalibrated camera. To our knowledge this is the first reported method able to process general curved documents in images without camera calibration. We propose to model the page surface by a developable surface, and exploit the properties (parallelism and equal line spacing) of the printed textual content on the page to recover the surface shape. Experiments show that the output images are much more OCR friendly than the original ones. While our method is designed to work with any general developable surfaces, it can be adapted for typical special cases including planar pages, scans of thick books, and opened books.
Keywords: calibration; camera; character; content; curved; distortion; document; document; image; images; OCR; optical; page; pictures; printed; processing; recognition; restoration; scanned; techniques; textual; warping

Font identification using the grating cell texture operator - Ma,H.; David Doermann (SPIE Conference on Document Recogntion and Retreival XXII, 2005)
In this paper, a new feature extraction operator, the grating cell operator, is applied to analyze the texture features and classify fonts of scanned document images. This operator is compared with the isotropic Gabor filter which was also employed for font classification. In order to improve the performance, a back-propagation neural network (BPNN) classifier was applied and compared with the simple weighted Euclidean distance (WED) classifier. Experimental results for five fonts of three scripts show that the grating cell operator performs better than the isotropic Gabor filter, and the BPNN classifier can provide more accurate classification results than the WED classifier.

Frame semantic enhancement of lexical-semantic resources - Green,Rebecca; Dorr, Bonnie J (Proceedings of the ACL-SIGLEX Workshop on Deep Lexical Acquisition, 2005)
SemFrame generates FrameNet-like frames, complete with semantic roles and evoking lexical units. This output can enhance FrameNet by suggesting new frames, as well as additional lexical units that evoke existing frames. SemFrame output can also support the addition of frame semantic relationships to WordNet.

A framework for decomposing reputation in MAS into competence and integrity - Smith,Michael J.; desJardins, Marie (Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, 2005)

The genome of the protist parasite Entamoeba histolytica - Loftus,B.; Anderson,I.; Davies,R.; Alsmark,U. C.M; Samuelson,J.; Amedeo,P.; Roncaglia,P.; Berriman,M.; Hirt,R. P; Mann,B. J; others (Nature, 2005)

The Genome Sequence of Trypanosoma cruzi, Etiologic Agent of Chagas Disease - El‐Sayed, Najib M.; Myler,Peter J.; Bartholomeu,Daniella C.; Nilsson,Daniel; Aggarwal,Gautam; Tran,Anh-Nhi; Ghedin,Elodie; Worthey,Elizabeth A.; Delcher,Arthur L.; Blandin,Gaëlle; Westenberger,Scott J.; Caler,Elisabet; et al. (Science, 2005)
Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.

The Genome Sequence of Trypanosoma Cruzi, Etiologic Agent of Chagas Disease - El‐Sayed, Najib M.; Myler,Peter J.; Bartholomeu,Daniella C.; Nilsson,Daniel; Aggarwal,Gautam; Tran,Anh-Nhi; Ghedin,Elodie; Worthey,Elizabeth A.; Delcher,Arthur L.; Blandin,Gaëlle; Westenberger,Scott J.; Caler,Elisabet; et al. (ScienceScience, 2005)
Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.

The genome sequence of Trypanosoma cruzi, etiologic agent of Chagas disease - El-Sayed, N.M.; Myler,P. J; Bartholomeu,D. C; Nilsson,D.; Aggarwal,G.; Tran,A. N; Ghedin,E.; Worthey,E. A; Delcher,A. L; Blandin,G.; others (Science, 2005)

A graph theoretical foundation for integrating RDF ontologies - Udrea,O.; Deng,Y.; Ruckhaus,E.; V.S. Subrahmanian (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2005)
RDF ontologies are rapidly increasing in number. We studythe problem of integrating two RDF ontologies under a given set H of Horn clauses that specify semantic relationships be- tween terms in the ontology, as well as under a given set of negative constraints. We formally define the notion of a “wit- ness” to the integrability of two RDF ontologies under such constraints. A witness represents a way of integrating the ontologies together. We define a “minimal” witnesses and provide the polynomial CROW (Computing RDF Ontology Witness) algorithm to find a witness. We report on the per- formance of CROW both on DAML, SchemaWeb and Onto- Broker ontologies as well as on synthetically generated data. The experiments show that CROW works very well on real- life ontologies and scales to massive ontologies.

The half-edge tree: a compact data structure for level-of-detail tetrahedral meshes - Danovaro,E.; De Floriani, Leila; Magillo,P.; Puppo,E.; Sobrero,D.; Sokolovsky,N. (Shape Modeling and Applications, 2005 International Conference, 2005)
We propose a new data structure for the compact encoding of a level-of detail (LOD) model of a three-dimensional scalar field based on unstructured tetrahedral meshes. Such data structure, called a half-edge tree (HET), is built through the iterative application of a half-edge collapse, i.e. by contracting an edge to one of its endpoints. We also show that selective refined meshes extracted from an HET contain on average about 34% and up to 75% less tetrahedra than those extracted from an LOD model built through a general edge collapse.
Keywords: application; compact; computational; data; detection; edge; encoding; generation; geometry; half-edge; iterative; level-of-detail; mesh; meshes; methods; model; structure; structures; tetrahedral; tree; tree

Handwriting matching and its application to handwriting synthesis - Yefeng Zheng; David Doermann (Document Analysis and Recognition, 2005. Proceedings. Eighth International Conference on, 2005)
Since it is extremely expensive to collect a large volume of handwriting samples, synthesized data are often used to enlarge the training set. We argue that, in order to generate good handwriting samples, a synthesis algorithm should learn the shape deformation characteristics of handwriting from real samples. In this paper, we present a point matching algorithm to learn the deformation, and apply it to handwriting synthesis. Preliminary experiments show the advantages of our approach.
Keywords: (artificial; deformation; deformation; handwriting; image; intelligence); learning; learning; matching; point; recognition; sampling; SHAPE; synthesis

Headline Generation for Written and Broadcast News - Zajic, David; Dorr, Bonnie J; Schwartz,Richard (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2005)
This technical report is an overview of work done on Headline Generation for written and broadcast news. The report covers HMM Hedge, a statistical approach based on the noisy channel model, Hedge Trimmer, a parse-and-trim approach using linguistically motivated trimming rules, and Topiary, a combination of Trimmer and Unsupervised Topic Discovery. Automatic evaluation of summaries using ROUGE and BLEU is described and used to evaluate the Headline Generation systems.
Keywords: *INFORMATION RETRIEVAL; *RADIO BROADCASTING; AUTOMATIC; AUTOMATIC SUMMARIZATION; HEDGE TRIMMER; INFORMATION SCIENCE; RADIO COMMUNICATIONS; STATISTICAL PROCESSES; TEST AND EVALUATION; WORDS(LANGUAGE)

High Order Spatial Audio Capture and Binaural Head-Tracked Playback over Headphones with HRTF Cues - Duraiswami, Ramani; Zotkin,Dmitry N; Li,Z.; Grassi,E.; Gumerov, Nail A.; Davis, Larry S. (Proceedings 119th convention of AES, 2005)
A theory and a system for capturing an audio scene and then rendering it remotely are developed andpresented. The sound capture is performed with a spherical microphone array. The sound field at the location of the array is deduced from the captured sound and is represented using either spherical wave-functions or plane-wave expansions. The sound field representation is then transmitted to a remote location for immediate rendering or stored for later use. 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. Rigorous error bounds and Nyquist-like sampling criterion for the representation of the sound field are presented and verified.

High Order Spatial Audio Capture and Its Binaural Head-Tracked Playback Over Headphones with HRTF Cues - Zotkin,Dmitry N; Davis, Larry S.; Duraiswami, Ramani; Grassi,Elena; Gumerov, Nail A.; Zhiyun,Li (Audio Engineering Society Convention 119, 2005)

High Order Spatial Audio Capture and Its Binaural Head-Tracked Playback Over Headphones with HRTF Cues - Davis, Larry S.; Duraiswami, Ramani; Grassi,E.; Gumerov, Nail A.; Li,Z.; Zotkin,Dmitry N (Audio Engineering Society Convention 119, 2005)
A theory and a system for capturing an audio scene and then rendering it remotely are developed and presented. The sound capture is performed with a spherical microphone array. The sound field at the location, and in a region of space in the neighborhood, of the array is deduced from the captured sound and represented using either spherical wave-functions or plane-wave expansions. The representation is then transmitted to a remote location for immediate rendering or stored for later reproduction. 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. Rigorous error bounds and a Nyquist-like sampling criterion for the representation of the sound field are presented and verified.

HOPE: A Homotopy Optimization Method for Protein Structure Prediction - Dunlavy,Daniel M.; O'Leary, Dianne P.; Klimov,Dmitri; Thirumalai,D. (Journal of Computational Biology, 2005)
We use a homotopy optimization method, HOPE, to minimize the potential energy associated with a protein model. The method uses the minimum energy conformation of one protein as a template to predict the lowest energy structure of a query sequence. This objective is achieved by following a path of conformations determined by a homotopy between the potential energy functions for the two proteins. Ensembles of solutions are produced by perturbing conformations along the path, increasing the likelihood of predicting correct structures. Successful results are presented for pairs of homologous proteins, where HOPE is compared to a variant of Newton's method and to simulated annealing.

How do I find blue books about dogs? The errors and frustrations of young digital library users - Hutchinson,H.; Druin, Allison; Bederson, Benjamin B.; Reuter,K.; Rose,A.; Weeks,A. C (Proceedings of HCII 2005, 2005)

Identifying and segmenting human-motion for mobile robot navigation using alignment errors - Abd-Almageed, Wael; Burns,B. J; Davis, Larry S. (12th International Conference on Advanced Robotics, 2005. ICAR '05. Proceedings, 2005)
This paper presents a new human-motion identification and segmentation algorithm, for mobile robot platforms. The algorithm is based on computing the alignment error between pairs of object images acquired from a moving platform. Pairs of images generating relatively small alignment errors are used to estimate the fundamental frequency of the object's motion. A decision criterion is then used to test the significance of the estimated frequency and to classify the object's motion. To verify the validity of the proposed approach, experimental results are shown on different classes of objects
Keywords: Computer errors; Educational institutions; Frequency estimation; human-motion identification; human-motion segmentation; HUMANS; Image motion analysis; Image segmentation; mobile robot navigation; Mobile robots; Motion estimation; Navigation; Object detection; robot vision; SHAPE

Identifying Script on Word-Level with Informational Confidence - Jaeger,Stefan; Ma,Huanfeng; David Doermann (8th Int. Conf. on Document Analysis and Recognition, 2005)
In this paper, we present a multiple classifier system for script identification. Applying a Gabor filter analysis of textures on word-level, our system identifies Latin and non-Latin words in bilingual printed documents. The classifier system comprises four different architectures based on nearest neighbors, weighted Euclidean distances, Gaussian mixture models, and support vector machines. We report results for Arabic, Chinese, Hindi, and Korean script. Moreover, we show that combining informational confidence values using sum-rule can consistently outperform the best single recognition rate.

Induction of Word and Phrase Alignments for Automatic Document Summarization - Daumé, Hal; Marcu,Daniel (Computational Linguistics, 2005)

Information Visualization and the Challenge of Universal Usability - Plaisant, Catherine (Exploring GeovisualizationExploring Geovisualization, 2005)
Information Visualization aims to provide compact graphical presentations and user interfaces for interactively manipulating large numbers of items. We present a simple “data by tasks taxonomy” then discuss the challenges of providing universal usability, with example applications using geo-referenced data. Information Visualization has been shown to be a powerful visual thinking or decision tool but it is becoming important for services to reach and empower every citizen. Technological advances are needed to deal with user diversity (age, language, disabilities, etc.) but also with the variety of technology used (screen size, network speed, etc.) and the gaps in user's knowledge (general knowledge, knowledge of the application domain, of the interface syntax or semantic). We present examples that illustrate how those challenges can be addressed.

The International Children’s Digital Library: A Case Study in Designing for a MultiLingual - Hutchinson,H.B.; Rose,A.; Bederson, Benjamin B.; Weeks,A. C; Druin, Allison (Multi-Cultural, Multi-Generational Audience. Information Technology and Libraries, 2005)

Introduction to the special issue on link mining - Getoor, Lise; Diehl,Christopher P. (ACM SIGKDD Explorations Newsletter, 2005)
An emerging challenge for data mining is the problem of mining richly structured datasets, where the objects are linked in some way. Many real-world datasets describe a variety of entity types linked via multiple types of relations. These links provide additional context that can be helpful for many data mining tasks. Yet multi-relational data violates the traditional assumption of independent, identically distributed data instances that provides the basis for many statistical machine learning algorithms. Therefore, new approaches are needed that can exploit the dependencies across the attribute and link structure.

Iterative translation disambiguation for cross-language information retrieval - Monz,Christof; Dorr, Bonnie J (Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, 2005)
Finding a proper distribution of translation probabilities is one of the most important factors impacting the effectiveness of a cross-language information retrieval system. In this paper we present a new approach that computes translation probabilities for a given query by using only a bilingual dictionary and a monolingual corpus in the target language. The algorithm combines term association measures with an iterative machine learning approach based on expectation maximization. Our approach considers only pairs of translation candidates and is therefore less sensitive to data-sparseness issues than approaches using higher n-grams. The learned translation probabilities are used as query term weights and integrated into a vector-space retrieval system. Results for English-German cross-lingual retrieval show substantial improvements over a baseline using dictionary lookup without term weighting.
Keywords: cross-language retrieval; query formulation; term co-occurrence measures; term weighting; translation disambiguation

Johns Hopkins summer workshop final report on parsing and spoken structural event detection - Harper,MP; Dorr, Bonnie J; Hale,J.; Roark,B.; Shafran,I.; Lease,M.; Liu,Y.; Snover,M.; Yung,L.; Krasnyanskaya,A. (Johns Hopkins University, Tech. Rep, 2005)
This report describes research conducted by the Parsing and Spoken Structural Event Detection(PaSSED) team as part of the 2005 Johns Hopkins Summer Workshop on Language Engineering. This project investigated the interaction between parsing and the detection of structural metadata in conversational speech, including sentence boundaries, edits (the reparandum portion of speech repairs), and fillers. In terms of parsing, we explored alternative methods of exploiting metadata information in parsing models and measured how varying accuracy in transcription and metadata information affects parsing accuracy. In the other direction, we similarly considered how syntactic and prosodic knowledge could be leveraged in metadata detection, measuring how this knowledge impacts metadata detection accuracy. As part of this work, we investigated metrics for evaluating parse accuracy in the presence of tran- scription and metadata detection errors, and we report on our experience using these metrics with several parsers and across varying experimental conditions. A range of methods for handling edits during pars- ing were evaluated in this research (excision, addition of markups to the input string, and grammar modification). We also developed a ToBI (a prosodic structure annotation scheme [SBP+92]) prosodic event classifier and describe its evaluation. Finally, we present methods for effective n-best sentence boundary candidate generation and reranking using syntactic, prosodic, and other features. These stud- ies are complemented by a second set of reranking investigations wherein we optimize sentence boundary detection explicitly to improve parse accuracy. The PaSSED project has: • investigated various techniques to enhance parsing of speech given metadata detection on conver- sational speech; • defined metrics for evaluating speech parsing accuracy, implemented them in the publically avail- able SParseval software package, and evaluated them under a wide variety of conditions; • recast SU detection as an n-best reranking problem with a relatively small n. Using this approach, we demonstrated significant improvements over a very strong baseline SU detection system. • reported on the interaction between parsing and metadata detection and their synergy; • fostered new collaborations and identified a number of interesting avenues for future work.

Kernel-based Bayesian filtering for object tracking - Han,Bohyung; Zhu,Ying; Comaniciu, D.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
Particle filtering provides a general framework for propagating probability density functions in nonlinear and non-Gaussian systems. However, the algorithm is based on a Monte Carlo approach and sampling is a problematic issue, especially for high dimensional problems. This paper presents a new kernel-based Bayesian filtering framework, which adopts an analytic approach to better approximate and propagate density functions. In this framework, the techniques of density interpolation and density approximation are introduced to represent the likelihood and the posterior densities by Gaussian mixtures, where all parameters such as the number of mixands, their weight, mean, and covariance are automatically determined. The proposed analytic approach is shown to perform sampling more efficiently in high dimensional space. We apply our algorithm to real-time tracking problems, and demonstrate its performance on real video sequences as well as synthetic examples.
Keywords: approach; approximation; Bayes; Bayesian; Carlo; density; detection; filtering; functions; Gaussian; interpolation; kernel-based; methods; mixtures; Monte; nonGaussian; nonlinear; object; particle; probability; probability; processes; recognition; sampling; sampling; sequences; system; tracking; video

A large-scale exploration of effective global features for a joint entity detection and tracking model - Daumé, Hal; Marcu,D. (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)

Learning as search optimization: approximate large margin methods for structured prediction - Daumé, Hal; Marcu,Daniel (Proceedings of the 22nd international conference on Machine learning, 2005)
Mappings to structured output spaces (strings, trees, partitions, etc.) are typically learned using extensions of classification algorithms to simple graphical structures (eg., linear chains) in which search and parameter estimation can be performed exactly. Unfortunately, in many complex problems, it is rare that exact search or parameter estimation is tractable. Instead of learning exact models and searching via heuristic means, we embrace this difficulty and treat the structured output problem in terms of approximate search. We present a framework for learning as search optimization, and two parameter updates with convergence the-orems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.

Link mining: a survey - Getoor, Lise; Diehl,Christopher P. (ACM SIGKDD Explorations Newsletter, 2005)
Many datasets of interest today are best described as a linked collection of interrelated objects. These may represent homogeneous networks, in which there is a single-object type and link type, or richer, heterogeneous networks, in which there may be multiple object and link types (and possibly other semantic information). Examples of homogeneous networks include single mode social networks, such as people connected by friendship links, or the WWW, a collection of linked web pages. Examples of heterogeneous networks include those in medical domains describing patients, diseases, treatments and contacts, or in bibliographic domains describing publications, authors, and venues. Link mining refers to data mining techniques that explicitly consider these links when building predictive or descriptive models of the linked data. Commonly addressed link mining tasks include object ranking, group detection, collective classification, link prediction and subgraph discovery. While network analysis has been studied in depth in particular areas such as social network analysis, hypertext mining, and web analysis, only recently has there been a cross-fertilization of ideas among these different communities. This is an exciting, rapidly expanding area. In this article, we review some of the common emerging themes.

The manifolds of spatial hearing - Duraiswami, Ramani; Raykar,V.C. (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
We present exploratory studies on learning the non-linear manifold structure, in head related impulse responses (HRIRs). We use the recently popular locally linear embedding technique. The lower dimensional manifold encodes the perceptual information in the HRIRs, namely the direction of the sound source. Based on this, we propose a new method for HRIR interpolation. We also propose that the distance between two HRIRs of an individual be taken as the geodesic distance on the learned manifold.
Keywords: acoustics; dimensional; direction; distance; EMBEDDING; encoding; geodesic; Head; hearing; hearing; HRIR; impulse; information; interpolation; learned; linear; localization; locally; low; manifold; manifold; manifolds; nonlinear; perceptual; related; response; responses; sound; source; spatial; structure; technique; transient

MCMC-based particle filtering for tracking a variable number of interacting targets - Zia Khan; Balch, T.; Dellaert, F. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005)
We describe a particle filter that effectively deals with interacting targets, targets that are influenced by the proximity and/or behavior of other targets. The particle filter includes a Markov random field (MRF) motion prior that helps maintain the identity of targets throughout an interaction, significantly reducing tracker failures. We show that this MRF prior can be easily implemented by including an additional interaction factor in the importance weights of the particle filter. However, the computational requirements of the resulting multitarget filter render it unusable for large numbers of targets. Consequently, we replace the traditional importance sampling step in the particle filter with a novel Markov chain Monte Carlo (MCMC) sampling step to obtain a more efficient MCMC-based multitarget filter. We also show how to extend this MCMC-based filter to address a variable number of interacting targets. Finally, we present both qualitative and quantitative experimental results, demonstrating that the resulting particle filters deal efficiently and effectively with complicated target interactions.
Keywords: algorithms; Animals; Artificial intelligence; Computer simulation; Computer vision; Filtering; filtering theory; HUMANS; Image Enhancement; Image Interpretation, Computer-Assisted; Index Terms- Particle filters; Information Storage and Retrieval; Insects; interacting targets; Markov chain Monte Carlo sampling step; Markov chain Monte Carlo.; Markov chains; Markov processes; Markov random field motion; Markov random fields; Models, Biological; Models, Statistical; Monte Carlo Method; Monte Carlo methods; MOTION; Movement; multitarget filter; multitarget tracking; particle filtering; Particle filters; Particle tracking; Pattern Recognition, Automated; Sampling methods; Subtraction Technique; target tracking; Video Recording

MEAD: support for Real-Time Fault-Tolerant CORBA - Narasimhan, P.; Tudor Dumitras; Paulos, A. M.; Pertet, S. M.; Reverte, C. F.; Slember, J. G.; Srivastava, D. (Concurrency and Computation: Practice and Experience, 2005)
The OMG's Real-Time CORBA (RT-CORBA) and Fault-Tolerant CORBA (FT-CORBA) specifications make it possible for today's CORBA implementations to exhibit either real-time or fault tolerance in isolation. While real-time requires a priori knowledge of the system's temporal operation, fault tolerance necessarily deals with faults that occur unexpectedly, and with possibly unpredictable fault recovery times. The MEAD (Middleware for Embedded Adaptive Dependability) system attempts to identify and to reconcile the conflicts between real-time and fault tolerance, in a resource-aware manner, for distributed CORBA applications. MEAD supports transparent yet tunable fault tolerance in real-time, proactive dependability, resource-aware system adaptation to crash, communication and timing faults with bounded fault detection and fault recovery. Copyright © 2005 John Wiley & Sons, Ltd.
Keywords: CORBA; Fault tolerance; non-determinism; predictability; real-time; recovery; trade-offs

Merging Network Measurement with Data Transport - Papageorgiou,Pavlos; Hicks, Michael W. (Passive and Active Network MeasurementPassive and Active Network Measurement, 2005)
The tasks of measurement and data transport are often treated independently, but we believe there are benefits to bringing them together. This paper proposes the simple idea of a transport agent to encapsulate useful data within probe packets in place of useless padding.

A methodology for extrinsic evaluation of text summarization: Does ROUGE correlate - Dorr, Bonnie J; Monz,C.; President,S.; Schwartz,R.; Zajic, David (Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, 2005)
This paper demonstrates the usefulness of sum-maries in an extrinsic task of relevance judgment based on a new method for measuring agree- ment, Relevance-Prediction, which compares sub- jects’ judgments on summaries with their own judg- ments on full text documents. We demonstrate that, because this measure is more reliable than previ- ous gold-standard measures, we are able to make stronger statistical statements about the benefits of summarization. We found positive correlations be- tween ROUGE scores and two different summary types, where only weak or negative correlations were found using other agreement measures. How- ever, we show that ROUGE may be sensitive to the choice of summarization style. We discuss the im- portance of these results and the implications for fu- ture summarization evaluations.

Model of Object-Based Coding for Surveillance Video - Yu,Yang; David Doermann (Proceedings in the ICASSP'04 IEEE International Conference on Computer Vision, 2005)
In this paper, we explore the model of potential savingsof object-based coding for surveillance video. Moving foreground objects in stationary camera surveillance video are detected by a background subtraction technique [3] and encoded with MPEG-4 object-based coding. Experiment results show that compared with frame-based coding, object-based coding can achieve significant savings which are dependent on the video content. We further model the relationship of compression efficiency and the number and size of video objects using statistical learning method. Simulations show that the model is representative. The model can be used to predict the savings of object-based coding and select the coding methods for surveillance video.

Model-based approximate querying in sensor networks - Deshpande, Amol; Guestrin,Carlos; Madden,Samuel; Hellerstein,Joseph; Wei Hong (The VLDB Journal, 2005)
Declarative queries are proving to be an attractive paradigm for interacting with networks of wireless sensors. The metaphor that “the sensornet is a database” is problematic, however, because sensors do not exhaustively represent the data in the real world. In order to map the raw sensor readings onto physical reality, a model of that reality is required to complement the readings. In this article, we enrich interactive sensor querying with statistical modeling techniques. We demonstrate that such models can help provide answers that are both more meaningful, and, by introducing approximations with probabilistic confidences, significantly more efficient to compute in both time and energy. Utilizing the combination of a model and live data acquisition raises the challenging optimization problem of selecting the best sensor readings to acquire, balancing the increase in the confidence of our answer against the communication and data acquisition costs in the network. We describe an exponential time algorithm for finding the optimal solution to this optimization problem, and a polynomial-time heuristic for identifying solutions that perform well in practice. We evaluate our approach on several real-world sensor-network datasets, taking into account the real measured data and communication quality, demonstrating that our model-based approach provides a high-fidelity representation of the real phenomena and leads to significant performance gains versus traditional data acquisition techniques.

Morse-Smale decompositions for modeling terrain knowledge - Čomić,L.; De Floriani, Leila; Papaleo,L. (Spatial Information Theory, 2005)
In this paper, we describe, analyze and compare techniques for extracting spatial knowledge from a terrain model. Specifically, we investigate techniques for extracting a morphological representation from a terrain model based on an approximation of a Morse-Smale complex. A Morse-Smale complex defines a decomposition of a topographic surface into regions with vertices at the critical points and bounded by integral lines which connect passes to pits and peaks. This provides a terrain representation which encompasses the knowledge on the salient characteristics of the terrain. We classify the various techniques for computing a Morse-Smale complexe based on the underlying terrain model, a Regular Square Grid (RSG) or a Triangulated Irregular Network (TIN), and based on the algorithmic approach they apply. Finally, we discuss hierarchical terrain representations based on a Morse-Smale decomposition.

Multi-resolution out-of-core modeling of terrain and geological data - Danovaro,Emanuele; De Floriani, Leila; Puppo,Enrico; Samet, Hanan (Proceedings of the 13th annual ACM international workshop on Geographic information systems, 2005)
Multi-resolution is a useful tool for managing the complexity of huge terrain and geological data sets. Since encoding large data sets may easily exceed main memory capabilities, data structures and algorithms capable of efficiently working in external memory are needed. In our work, we aim at developing an out-of-core multi-resolution model dimension-independent, that can be used for both terrains, represented by Triangulated Irregular Networks(TINs), and 3D data, such as geological data, represented by tetrahedral meshes. We have based our approach on a general multi-resolution model, that we have proposed in our previous work, which supports the extraction of variable-resolution representations. As first step, we have developed, in a prototype simulation system, a large number of clustering techniques for the modifications in a multi-resolution model. Here, we describe such techniques, and analyze and evaluate them experimentally. The result of this investigation has led us to select a specific clustering approach as the basis for an efficient out-of-core data structure.
Keywords: Multi-resolution; out-of-core; terrain models

Multitarget tracking with split and merged measurements - Zia Khan; Balch, T.; Dellaert, F. (IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005, 2005)
In many multitarget tracking applications in computer vision, a detection algorithm provides locations of potential targets. Subsequently, the measurements are associated with previously estimated target trajectories in a data association step. The output of the detector is often imperfect and the detection data may include multiple, split measurements from a single target or a single merged measurement from several targets. To address this problem, we introduce a multiple hypothesis tracker for interacting targets that generate split and merged measurements. The tracker is based on an efficient Markov chain Monte Carlo (MCMC) based auxiliary variable particle filter. The particle filter is Rao-Blackwellized such that the continuous target state parameters are estimated analytically, and an MCMC sampler generates samples from the large discrete space of data associations. In addition, we include experimental results in a scenario where we track several interacting targets that generate these split and merged measurements.
Keywords: Application software; Computer vision; Detection algorithms; Detectors; filtering theory; Markov chain Monte Carlo based auxiliary variable particle filter; Markov processes; merged measurements; Monte Carlo methods; multiple hypothesis tracker; multitarget tracking; parameter estimation; Particle filters; Particle tracking; Rao-Blackwellized filter; split measurements; target tracking; Trajectory

NeurAlign: combining word alignments using neural networks - Ayan,Necip Fazil; Dorr, Bonnie J; Monz,Christof (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)
This paper presents a novel approach to combining different word alignments. We view word alignment as a pattern classification problem, where alignment combination is treated as a classifier ensemble, and alignment links are adorned with linguistic features. A neural network model is used to learn word alignments from the individual alignment systems. We show that our alignment combination approach yields a significant 20--34% relative error reduction over the best-known alignment combination technique on English-Spanish and English-Chinese data.

Neuromimetic sound representation for percept detection and manipulation - Zotkin,Dmitry N; Chi,T.; Shamma,S.A.; Duraiswami, Ramani (EURASIP Journal on Applied Signal Processing, 2005)
The acoustic wave received at the ears is processed by the human auditory system to separate different sounds along the intensity,pitch, and timbre dimensions. Conventional Fourier-based signal processing, while endowed with fast algorithms, is unable to easily represent a signal along these attributes. In this paper, we discuss the creation of maximally separable sounds in auditory user interfaces and use a recently proposed cortical sound representation, which performs a biomimetic decomposition of an acoustic signal, to represent and manipulate sound for this purpose. We briefly overview algorithms for obtaining, manipulating, and inverting a cortical representation of a sound and describe algorithms for manipulating signal pitch and timbre separately. The algorithms are also used to create sound of an instrument between a “guitar” and a “trumpet.” Excellent sound quality can be achieved if processing time is not a concern, and intelligible signals can be reconstructed in reasonable processing time (about ten seconds of computational time for a one-second signal sampled at 8 kHz). Work on bringing the algorithms into the real-time processing domain is ongoing.

On-line density-based appearance modeling for object tracking - Han,B.; Davis, Larry S. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
Object tracking is a challenging problem in real-time computer vision due to variations of lighting condition, pose, scale, and view-point over time. However, it is exceptionally difficult to model appearance with respect to all of those variations in advance; instead, on-line update algorithms are employed to adapt to these changes. We present a new on-line appearance modeling technique which is based on sequential density approximation. This technique provides accurate and compact representations using Gaussian mixtures, in which the number of Gaussians is automatically determined. This procedure is performed in linear time at each time step, which we prove by amortized analysis. Features for each pixel and rectangular region are modeled together by the proposed sequential density approximation algorithm, and the target model is updated in scale robustly. We show the performance of our method by simulations and tracking in natural videos
Keywords: appearance; approximation; Gaussian; Computer; density; density-based; detection; target; Gaussian; mixtures; object; modeling; modeling; real-time; processes; computer; sequences; object; technique; online; tracking; tracking; online; vision; image; vision; sequential

Optimal status sets of heterogeneous agent programs - Stroe,Bogdan; V.S. Subrahmanian; Dasgupta,Sudeshna (Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, 2005)
There are many situations where an agent can perform one of several sets of actions in responses to changes in its environment, and the agent chooses to perform the set of actions that optimizes some objective function. In past work, Eiter et. al. have proposed a rule based framework for programming agents on top of heterogeneous data sources, but they provide no solutions to the above problem. In this paper, we propose a semantics called optimal feasible status set semantics for agents which allows the agent to associate an objective function with feasible status sets and act according to the feasible status set that optimizes this objective function. We provide both an algorithm to compute exact optimal feasible status sets as well as the TierOpt and FastOpt algorithms to find (suboptimal) feasible status set much faster. We report on experiments on a suite of real agent applications showing that the heuristic algorithms works well in practice.
Keywords: heterogeneous agents; heuristic search; non-ground representations; optimal status sets

A pairwise key predistribution scheme for wireless sensor networks - Du,Wenliang; Deng,Jing; Han,Yunghsiang S.; Varshney,Pramod K.; Katz, Jonathan; Khalili,Aram (ACM Trans. Inf. Syst. Secur., 2005)
To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent between sensor nodes. Before doing so, keys for performing encryption and authentication must be agreed upon by the communicating parties. Due to resource constraints, however, achieving key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and other public-key based schemes, are not suitable for wireless sensor networks due to the limited computational abilities of the sensor nodes. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory this requires when the network size is large.In this paper, we provide a framework in which to study the security of key predistribution schemes, propose a new key predistribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary for the adversary to attack a large fraction of the network before it can achieve any significant gain.
Keywords: key predistribution; Security; Wireless sensor networks

Pathogenic Vibrio species in the marine and estuarine environment - Pruzzo,C.; Huq,A.; Rita R Colwell; Donelli,G. (Oceans and health: pathogens in the marine environment, 2005)
The genus Vibrio includes more than 30 species, at least 12 of which are pathogenic to humans and/or have been associated with foodborne diseases (Chakraborty et al., 1997). Among these species, Vibrio cholerae, serogroups O1 and O139, are the most important, since they are associated with epidemic and pandemic diarrhea outbreaks in many parts of the world (Centers for Disease Control and Prevention, 1995; Kaper et al., 1995). However, other species of vibrios capable of causing diarrheal disease in humans have received greater attention in the last decade. These include Vibrio parahaemolyticus, a leading cause of foodborne disease outbreaks in Japan and Korea (Lee et al., 2001), Vibrio vulnificus, Vibrio alginolyticus, Vibrio damsela, Vibrio fluvialis, Vibrio furnissii, Vibrio hollisae, Vibrio metschnikovii, and Vibrio mimicus (Altekruse et al., 2000; Høi et al., 1997). In the USA, Vibrio species have been estimated to be the cause of about 8000 illnesses annually (Mead et al., 1999).

Pedestrian classification from moving platforms using cyclic motion pattern - Yang Ran; Qinfen Zheng; Weiss, I.; Davis, Larry S.; Abd-Almageed, Wael; Liang Zhao (IEEE International Conference on Image Processing, 2005. ICIP 2005, 2005)
This paper describes an efficient pedestrian detection system for videos acquired from moving platforms. Given a detected and tracked object as a sequence of images within a bounding box, we describe the periodic signature of its motion pattern using a twin-pendulum model. Then a principle gait angle is extracted in every frame providing gait phase information. By estimating the periodicity from the phase data using a digital phase locked loop (dPLL), we quantify the cyclic pattern of the object, which helps us to continuously classify it as a pedestrian. Past approaches have used shape detectors applied to a single image or classifiers based on human body pixel oscillations, but ours is the first to integrate a global cyclic motion model and periodicity analysis. Novel contributions of this paper include: i) development of a compact shape representation of cyclic motion as a signature for a pedestrian, ii) estimation of gait period via a feedback loop module, and iii) implementation of a fast online pedestrian classification system which operates on videos acquired from moving platforms.
Keywords: compact shape representation; cyclic motion pattern; data mining; Detectors; digital phase locked loop; digital phase locked loops; feedback loop module; gait analysis; gait phase information; human body pixel oscillations; HUMANS; image classification; Image motion analysis; image representation; image sequence; Image sequences; Motion detection; Object detection; pedestrian classification; pedestrian detection system; Phase estimation; Phase locked loops; principle gait angle; SHAPE; tracking; Videos

Pedestrian classification from moving platforms using cyclic motion pattern - Yang Ran; Qinfen Zheng; Weiss, I.; Davis, Larry S.; Abd-Almageed, Wael; Liang Zhao (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
This paper describes an efficient pedestrian detection system for videos acquired from moving platforms. Given a detected and tracked object as a sequence of images within a bounding box, we describe the periodic signature of its motion pattern using a twin-pendulum model. Then a principle gait angle is extracted in every frame providing gait phase information. By estimating the periodicity from the phase data using a digital phase locked loop (dPLL), we quantify the cyclic pattern of the object, which helps us to continuously classify it as a pedestrian. Past approaches have used shape detectors applied to a single image or classifiers based on human body pixel oscillations, but ours is the first to integrate a global cyclic motion model and periodicity analysis. Novel contributions of this paper include: i) development of a compact shape representation of cyclic motion as a signature for a pedestrian, ii) estimation of gait period via a feedback loop module, and iii) implementation of a fast online pedestrian classification system which operates on videos acquired from moving platforms.
Keywords: analysis; angle; body; classification; compact; cyclic; DETECTION; detection; digital; Feedback; Gait; human; image; information; locked; loop; loop; loops; module; MOTION; object; oscillations; pattern; pedestrian; phase; Pixel; principle; representation; sequence; sequences; SHAPE; system

A picture is worth a thousand keywords: image-based object search on a mobile platform - Tom Yeh; Grauman,Kristen; Tollmar,Konrad; Darrell,Trevor (CHI '05 extended abstracts on Human factors in computing systems, 2005)
Finding information based on an object's visual appearance is useful when specific keywords for the object are not known. We have developed a mobile image-based search system that takes images of objects as queries and finds relevant web pages by matching them to similar images on the web. Image-based search works well when matching full scenes, such as images of buildings or landmarks, and for matching objects when the boundary of the object in the image is available. We demonstrate the effectiveness of a simple interactive paradigm for obtaining a segmented object boundary, and show how a shape-based image matching algorithm can use the object outline to find similar images on the web.
Keywords: content-based image retrieval; interactive segmentation; mobile interface; Object recognition

Pioneer: verifying code integrity and enforcing untampered code execution on legacy systems - Seshadri, Arvind; Luk, Mark; Elaine Shi; Perrig, Adrian; van Doorn, Leendert; Khosla, Pradeep (ACM SIGOPS Operating Systems Review, 2005)
We propose a primitive, called Pioneer, as a first step towards verifiable code execution on untrusted legacy hosts. Pioneer does not require any hardware support such as secure co-processors or CPU-architecture extensions. We implement Pioneer on an Intel Pentium IV Xeon processor. Pioneer can be used as a basic building block to build security systems. We demonstrate this by building a kernel rootkit detector.
Keywords: dynamic root of trust; rootkit detection; self-check-summing code; software-based code attestation; verifiable code execution

Plane-wave decomposition analysis for spherical microphone arrays - Duraiswami, Ramani; Zhiyun Li; Zotkin,Dmitry N; Grassi,E.; Gumerov, Nail A. (IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 2005, 2005)
Spherical microphone arrays have attracted attention for analyzing the sound field in a region and beamforming. The analysis of the recorded sound has been performed in terms of spherical wave-functions, and recently the use of plane-wave expansions has been suggested. We show that the plane-wave basis is intimately related to the spherical wave-functions. Reproduction in terms of both representations satisfies certain band-limit criteria. We provide an error bound that shows that to reproduce the spatial characteristics of a sound of a certain frequency we need to be able to accurately represent sounds of up to a particular order, which establishes a Nyquist-like criterion. The order of the sound field in turn is related to the number of microphones in the array necessary to achieve accurate quadrature on the sphere. These results are illustrated with simulations.
Keywords: Acoustic propagation; Acoustic scattering; acoustic signal processing; acoustic waves; array signal processing; band-limit criteria; beamforming; Educational institutions; Fourier transforms; Frequency; Laboratories; microphone arrays; Nails; Nyquist criterion; Nyquist-like criterion; Partial differential equations; plane-wave decomposition analysis; sound field analysis; spherical microphone arrays; spherical wave-functions

Processing of reverberant speech for time-delay estimation - Yegnanarayana,B.; Prasanna,S. R.M; Duraiswami, Ramani; Zotkin,Dmitry N (IEEE Transactions on Speech and Audio Processing, 2005)
In this paper, we present a method of extracting the time-delay between speech signals collected at two microphone locations. Time-delay estimation from microphone outputs is the first step for many sound localization algorithms, and also for enhancement of speech. For time-delay estimation, speech signals are normally processed using short-time spectral information (either magnitude or phase or both). The spectral features are affected by degradations in speech caused by noise and reverberation. Features corresponding to the excitation source of the speech production mechanism are robust to such degradations. We show that these source features can be extracted reliably from the speech signal. The time-delay estimate can be obtained using the features extracted even from short segments (50-100 ms) of speech from a pair of microphones. The proposed method for time-delay estimation is found to perform better than the generalized cross-correlation (GCC) approach. A method for enhancement of speech is also proposed using the knowledge of the time-delay and the information of the excitation source.
Keywords: Acoustic noise; acoustic signal processing; array signal processing; data mining; Degradation; delay estimation; Feature extraction; Hilbert envelope; localization algorithm; microphone arrays; microphone location; Microphones; Phase estimation; reverberation; short-time spectral information; Signal processing; source features; source information excitation; speech enhancement; Speech processing; speech production mechanism; speech signal; time-delay; time-delay estimation

RDF aggregate queries and views - Hung,E.; Deng,Yu; V.S. Subrahmanian (Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on, 2005)
Resource description framework (RDF) is a rapidly expanding Web standard. RDF databases attempt to track the massive amounts of Web data and services available. In this paper, we study the problem of aggregate queries. We develop an algorithm to compute answers to aggregate queries over RDF databases and algorithms to maintain views involving those aggregates. Though RDF data can be stored in a standard relational DBMS (and hence we can execute standard relational aggregate queries and view maintenance methods on them), we show experimentally that our algorithms that operate directly on the RDF representation exhibit significantly superior performance.
Keywords: aggregate; databases; DBMS; description; framework; languages; Maintenance; methods; processing; queries; query; RDF; relational; resource; standard; standards; view; Web

Real-time foreground-background segmentation using codebook model - Kim,K.; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (Real-time imaging, 2005)

Reliable Segmentation of Pedestrians in Moving Scenes - Ran, Y.; Zheng,Q.; Weiss, I.; Davis, Larry S. (The 2005 International Conference on Acoustics, Speech, and Signal Processing (ICASSP2005), 2005)
This paper describes a periodic motion based pedestriansegmentation algorithm for videos acquired from moving platforms. Given a sequence of bounding boxes containing the detected and tracked walking human, the goal is to analyze the low dimension structure by considering every object sample as a point in the high dimensional manifold space and use the learned structure for segmentation. In this work, unlike the traditional top- down dimension reduction (manifold learning) methods such as Isomap and locally linear embedding (LLE) [9], we introduce a novel bottom-up learning approach. We represent the human stride as a cascade of models with increasing parameter numbers. These parameters describe the dynamics of pedestrians from coarse to fine. By applying the learned manifold structure, we can predict the location of body parts, especially legs, with high accuracy at every frame. The segmentation in consecutive images is done by EM clustering. With the accuracy for prediction using twin-pendulum model, EM is more likely to converge to global maximums. Experimental results for real videos are presented. The algorithm has demonstrated a reliable performance for videos acquired from moving platforms.

Resource-aware wireless sensor-actuator networks - Deshpande, Amol; Guestrin,C.; Madden,S. R (Data Engineering, 2005)

Robotic apparatus and wireless communication system - Lathan,Corinna E.; Tracey,Michael R.; Vice,Jack M.; Druin, Allison; Plaisant, Catherine (2005)
A robotic apparatus and system adapted to communicate with a wireless sensor. The apparatus may be either physical or virtual in nature and is adapted to communicate physical movements with a wireless sensor. Data received from the sensor and/or robotic apparatus may be reviewed in a real-time mode, or may be saved for review at a later time. In addition, the apparatus may be controlled through an operator that is in local or remote communication with the apparatus. The robotic system may include pre-programmed interactive platforms for enabling communication between a user and the apparatus in a dynamic mode. In addition, the system may allow an operator to program a game/story for use as an interactive platform. Accordingly, the apparatus and system provides a platform for rehabilitative exercise of a patient as well as an entertainment device.

A robust and self-reconfigurable design of spherical microphone array for multi-resolution beamforming - Zhiyun Li; Duraiswami, Ramani (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
We describe a robust and self-reconfigurable design of a spherical microphone array for beamforming. Our approach achieves a multi-resolution spherical beamformer with performance that is either optimal in the approximation of desired beampattern or is optimal in the directivity achieved, both robustly. Our implementation converges to the optimal performance quickly while exactly satisfying the specified frequency response and robustness constraint in each iteration step without accumulated round-off errors. The advantage of this design lies in its robustness and self-reconfiguration in microphone array reorganization, such as microphone failure, which is highly desirable in online maintenance and anti-terrorism. Design examples and simulation results are presented.
Keywords: 3D; anti-terrorism; array; array; arrays; audio; beam; beamforming; beampattern; directivity; Frequency; microphone; multiresolution; omnidirectional; optimisation; optimization; processing; reorganization; response; robustness; sampling; self-reconfigurable; signal; soundfield; spherical; steering

Robust observations for object tracking - Han,Bohyung; Davis, Larry S. (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
It is a difficult task to find an observation model that will perform well for long-term visual tracking. In this paper, we propose an adaptive observation enhancement technique based on likelihood images, which are derived from multiple visual features. The most discriminative likelihood image is extracted by principal component analysis (PCA) and incrementally updated frame by frame to reduce temporal tracking error. In the particle filter framework, the feasibility of each sample is computed using this most discriminative likelihood image before the observation process. Integral image is employed for efficient computation of the feasibility of each sample. We illustrate how our enhancement technique contributes to more robust observations through demonstrations.
Keywords: (numerical; adaptive; analysis; component; enhancement; filter; Filtering; framework; image; images; likelihood; methods); object; observation; particle; PCA; principal; tracking

Robust Point Matching for Two-Dimensional Nonrigid Shapes - Yefeng Zheng; David Doermann (Proceedings in the ICASSP'04 IEEEInternational Conference on Computer Vision, 2005)
Recently, nonrigid shape matching has received more and more attention. For nonrigid shapes, most neighboring points cannot move independently under deformation due to physical constraints. Furthermore, the rough structure of a shape should be preserved under deformation, otherwise even people cannot match shapes reliably. Therefore, though the absolute distance between two points may change significantly, the neighborhood of a point is well preserved in general. Based on this observation, we formulate point matching as a graph matching problem. Each point is a node in the graph, and two nodes are connected by an edge if their Euclidean distance is less than a threshold. The optimal match between two graphs is the one that maximizes the number of matched edges. The shape context distance is used to initialize the graph matching, followed by relaxation labeling for refinement. Nonrigid deformation is overcome by bringing one shape closer to the other in each iteration using deformation parameters estimated from the current point correspondence. Experiments demonstrate the effectiveness of our approach: it outperforms the shape context and TPS-RPM algorithms under nonrigid deformation and noise on a public data set.

Search-based structured prediction as classification - Daumé, Hal; Langford,J.; Marcu,D. (NIPS Workshop on Advances in Structured Learning for Text and Speech Processing, Whistler, Canada, 2005)

Secure remote authentication using biometric data - Boyen,X.; Dodis,Y.; Katz, Jonathan; Ostrovsky,R.; Smith,A. (Advances in Cryptology–EUROCRYPT 2005, 2005)
Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly distributed; and (2) they are not exactly reproducible. Recent work, most notably that of Dodis, Reyzin, and Smith, has shown how these obstacles may be overcome by allowing some auxiliary public information to be reliably sent from a server to the human user. Subsequent work of Boyen has shown how to extend these techniques, in the random oracle model, to enable unidirectional authentication from the user to the server without the assumption of a reliable communication channel.We show two efficient techniques enabling the use of biometric data to achieve mutual authentication or authenticated key exchange over a completely insecure (i.e., adversarially controlled) channel. In addition to achieving stronger security guarantees than the work of Boyen, we improve upon his solution in a number of other respects: we tolerate a broader class of errors and, in one case, improve upon the parameters of his solution and give a proof of security in the standard model.

Seeking the source: software source code as a social and technical artifact - de Souza,Cleidson; Jon Froehlich; Dourish,Paul (Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work, 2005)
Keywords: data mining; social networks; socio-technical systems; software repositories

Segmentation and appearance model building from an image sequence - Liang Zhao; Davis, Larry S. (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
In this paper we explore the problem of accurately segmenting a person from a video given only approximate location of that person. Unlike previous work which assumes that the appearance model is known in advance, we developed an iterative expectation-sampling (ES) algorithm for solving segmentation and appearance modeling simultaneously The appearance model is encoded with a kernel-based PDF defined in a joint color/path-length space. This appearance model remains unchanged during a short time period, although the object can articulate. Thus, we can perform the ES iteration not only for a single frame but also for an image sequence. The algorithm is iterative, but simple, efficient and gives visually good results.
Keywords: algorithm; color-path-length; expectation-sampling; image; iterative; joint; kernel-based; methods; PDF; person; segmentation; sequence; sequences; space

A sentence-trimming approach to multi-document summarization - Zajic, David; Dorr, Bonnie J; Jimmy Lin; Monz,C.; Schwartz,R. (Proceedings of DUC2005, 2005)
We implemented an initial applicationof a sentence-trimming approach (Trim- mer) to the problem of multi-document summarization in the MSE2005 and DUC2005 tasks. Sentence trimming was incorporated into a feature-based summarization system, called Multi- Document Trimmer (MDT), by us- ing sentence trimming as both a pre- processing stage and a feature for sen- tence ranking. We demonstrate that we were able to port Trimmer easily to this new problem. Although the direct im- pact of sentence trimming was minimal compared to other features used in the system, the interaction of the other fea- tures resulted in trimmed sentences ac- counting for nearly half of the selected summary sentences.

Serendipitous discovery of Wolbachia genomes in multiple Drosophila species - Salzberg,Steven L.; Hotopp,Julie CD; Delcher,Arthur L.; Pop, Mihai; Smith,Douglas R.; Eisen,Michael B.; Nelson,William C. (Genome Biology, 2005)
The Trace Archive is a repository for the raw, unanalyzed data generated by large-scale genome sequencing projects. The existence of this data offers scientists the possibility of discovering additional genomic sequences beyond those originally sequenced. In particular, if the source DNA for a sequencing project came from a species that was colonized by another organism, then the project may yield substantial amounts of genomic DNA, including near-complete genomes, from the symbiotic or parasitic organism.

Software process improvement in small organizations: a case study - Dangle,K.C.; Larsen,P.; Shaw,M.; Zelkowitz, Marvin V (Software, IEEE, 2005)
The Capability Maturity Model for software has become a major force in software development process improvement. We looked at the role of process improvement in the context of a small organization. Although the Capability Maturity Model integration is replacing the CMM, we focused on the older CMM. We had to look at more than which CMM key process areas apply to small businesses. Our overall goal was to institute good software development practices, we used the language of the CMM to gain the management's cooperation. Applying these practices is essential to managing growth, yet undertaking this effort without prior experience could impede a small company's innovative nature. This case study's purpose was to investigate the success factors of a software process improvement effort for a small software development organization.
Keywords: area; aspects; capability; CMM; development; improvement; key; management; Maturity; model; organisational; organization; process; small; software

Speaker Localization Using Excitation Source Information in Speech - Raykar,V.C.; Yegnanarayana,B.; Prasanna,S. R.M; Duraiswami, Ramani (Speech and Audio Processing, IEEE Transactions on, 2005)
This paper presents the results of simulation and real room studies for localization of a moving speaker using information about the excitation source of speech production. The first step in localization is the estimation of time-delay from speech collected by a pair of microphones. Methods for time-delay estimation generally use spectral features that correspond mostly to the shape of vocal tract during speech production. Spectral features are affected by degradations due to noise and reverberation. This paper proposes a method for localizing a speaker using features that arise from the excitation source during speech production. Experiments were conducted by simulating different noise and reverberation conditions to compare the performance of the time-delay estimation and source localization using the proposed method with the results obtained using the spectrum-based generalized cross correlation (GCC) methods. The results show that the proposed method shows lower number of discrepancies in the estimated time-delays. The bias, variance and the root mean square error (RMSE) of the proposed method is consistently equal or less than the GCC methods. The location of a moving speaker estimated using the time-delays obtained by the proposed method are closer to the actual values, than those obtained by the GCC method.
Keywords: correlation; correlation; cross; Delay; error; error; estimation; excitation; generalized; information; localization; mean; methods; processing; production; root; source; speaker; speech; square; TIME

Structural metadata and parsing speech - Harper,M.; Dorr, Bonnie J; Hale,J.; Roark,B.; Shafran,I.; Lease,M.; Liu,Y.; Snover,M.; Yung,L.; Krasnyanskaya,A.; others (JHU Language Engineering Workshop, 2005)

System for capturing of highorder spatial audio using spherical microphone array and binaural head-tracked playback over headphones with head related transfer function cues - Duraiswami, Ramani; Zotkin,Dmitry N; Li,Z.; Grassi,E.; Gumerov, Nail A.; Davis, Larry S. (Proc. 119th convention AES, 2005)

A system for performing content-based searches on a database of mechanical assemblies - Deshmukh,A. S.; Gupta,S.K.; Karnik,M. V.; Sriram,R.D. (2005)
The increased use of 3D CAD systems by productdevelopment organizations has resulted in large databases of assemblies; this explosion of assembly data will continue in the future. Currently, there are no effective content-based techniques to search these databases. Ability to perform content-based searches on these databases is expected to help the designers in the following two ways. First, it can facilitate reuse of existing assembly designs, and thereby reducing the design time. Second, a lot of useful Design for Manufacturing and Assembly (DFMA) knowledge is embedded in existing assemblies. Therefore a capability to locate existing assemblies and examine them can be used as a learning tool by the designers to learn from the existing assembly designs and hence transfer the best DFMA practices to new designers. This paper describes a system for performing content-based searches on assembly databases. We identify templates for comprehensive search definitions and describe algorithms to perform content-based searches for mechanical assemblies. We also illustrate capabilities of our system through several examples.

Temporal visualization of planning polygons for e~cient partitioning of geo-spatial data - Shanbhag,P.; Rheingans,P.; desJardins, Marie (Information Visualization, 2005. INFOVIS 2005. IEEE Symposium on, 2005)
Partitioning of geo-spatial data for efficient allocation of resources such as schools and emergency health care services is driven by a need to provide better and more effective services. Partitioning of spatial data is a complex process that depends on numerous factors such as population, costs incurred in deploying or utilizing resources and target capacity of a resource. Moreover, complex data such as population distributions are dynamic i.e. they may change over time. Simple animation may not effectively show temporal changes in spatial data. We propose the use of three temporal visualization techniques -wedges, rings and time slices - to display the nature of change in temporal data in a single view. Along with maximizing resource utilization and minimizing utilization costs, a partition should also ensure the long term effectiveness of the plan. We use multi-attribute visualization techniques to highlight the strengths and identify the weaknesses of a partition. Comparative visualization techniques allow multiple partitions to be viewed simultaneously. Users can make informed decisions about how to partition geo spatial data by using a combination of our techniques for multi-attribute visualization, temporal visualization and comparative visualization.

Toward on-line schema evolution for non-stop systems - Deshpande, Amol; Hicks, Michael W. (11th High Performance Transaction Systems Workshop, 2005)

Umd/bbn at mse2005 - Zajic, David; Dorr, Bonnie J; Jimmy Lin; Schwartz,R. (Proceedings of the MSE2005 track of the Association for Computational Linguistics Workshop on Intrinsic and Extrinsic Evaluation Meatures for MT and/or Summarization, Ann Arbor, MI, 2005)
We implemented an initial applicationof a sentence-trimming approach (Trim- mer) to the problem of multi-document summarization in the MSE2005 task. Sentence trimming was incorporated into a feature-based summarization sys- tem, called Multi-Document Trimmer (MDT), by using sentence trimming as both a pre-processing stage and a fea- ture for sentence ranking. We demon- strate that we were able to port Trimmer easily to this new problem, although the impact of sentence trimming was min- imal compared to other features used in the system. The performance of our sys- tem in the official MSE2005 task was around the middle of the pack (16 out of 27). After some minor bug fixes and a simple correction (dateline removal) we obtained an improvement on a post-hoc run on the test data.

Unwarping Images of Curved Documents Using Global Shape Optimization - Liang,Jian; DeMenthon,Daniel; David Doermann (Proc. Fist International Workshop on Camera-based Document Analysis and Recognition, 2005)

Using Computer Vision to Detect Web Browser Display Errors - Liu,Xu; David Doermann (3rd Web Document Analysis Workshop (on ICDAR 2005), 2005)
As the functionality and complexity of the WWW continues to grow so does the need for WWW quality assurance and testing. Although there have been numerous approaches to automated Web testing, existing techniques analyze primarily textual information, and the final judgment on correctness of layout is via human observation. The motivation of this paper is to employ computer vision techniques to detect Web display errors. To do this, we analyze images of the rendered pages rather than the HTML to discover errors. Our approach includes page segmentation, dynamic matching and outlier identification. We show that the approach successfully detects layout errors in the Opera browser on Microsoft Websites, while minimizing false alarms.

Using Dynamic Tracing Sampling to Measure Long Running Programs - Odom, Jeffrey; Hollingsworth, Jeffrey K; DeRose,Luiz; Ekanadham, Kattamuri; Sbaraglia, Simone (Proceedings of the 2005 ACM/IEEE conference on Supercomputing, 2005)
Detailed cache simulation can be useful to both system developers and application writers to understand an application's performance. However, measuring long running programs can be extremely slow. In this paper we present a technique to use dynamic sampling of trace snippets throughout an application's execution. We demonstrate that our approach improves accuracy compared to sampling a few timesteps at the beginning of execution by judiciously choosing the frequency, as well as the points in the control flow, at which samples are collected. Our approach is validated using the SIGMA tracing and simulation framework for the IBM Power family of processors.
Keywords: data communications; design; experimentation; measurement; performance; tracing

Using NMR Spectroscopy to Monitor Ubiquitin Chain Conformation and Interactions with Ubiquitin‐Binding Domains - Varadan,Ranjani; Assfalg,Michael; Fushman, David (Ubiquitin and Protein Degradation, Part B, 2005)
Polyubiquitin (polyUb) chains function as signaling molecules that mediate a diverse set of cellular events. The outcome of polyubiquitination depends on the specific linkage between Ub moieties in the chain, and differently linked chains function as distinct intracellular signals. Although an increasing number of Ub‐binding proteins that transmit the regulatory information conferred by (poly)ubiquitination have been identified, the molecular mechanisms of linkage‐specific signaling and recognition still remain to be understood. Knowledge of the chain structure is expected to provide insights into the basis of diversity in polyUb signaling. Here we describe several NMR approaches aimed at determining the physiological conformation of polyUb and characterization of the chains' interactions with ubiquitin‐binding proteins.

Using probabilistic models for data management in acquisitional environments - Deshpande, Amol; Guestrin,C.; Madden,S. (Proc. CIDR, 2005)

A video-based framework for the analysis of presentations/posters - Zandifar,A.; Duraiswami, Ramani; Davis, Larry S. (International Journal on Document Analysis and Recognition, 2005)
Detection and recognition of textual information in an image or video sequence is important for many applications. The increased resolution and capabilities of digital cameras and faster mobile processing allow for the development of interesting systems. We present an application based on the capture of information presented at a slide-show presentation or at a poster session. We describe the development of a system to process the textual and graphical information in such presentations. The application integrates video and image processing, document layout understanding, optical character recognition (OCR), and pattern recognition. The digital imaging device captures slides/poster images, and the computing module preprocesses and annotates the content. Various problems related to metric rectification, key-frame extraction, text detection, enhancement, and system integration are addressed. The results are promising for applications such as a mobile text reader for the visually impaired. By using powerful text-processing algorithms, we can extend this framework to other applications, e.g., document and conference archiving, camera-based semantics extraction, and ontology creation.

VidMAP: video monitoring of activity with Prolog - Shet,V. D; Harwood,D.; Davis, Larry S. (Advanced Video and Signal Based Surveillance, 2005. AVSS 2005. IEEE Conference on, 2005)
This paper describes the architecture of a visual surveillance system that combines real time computer vision algorithms with logic programming to represent and recognize activities involving interactions amongst people, packages and the environments through which they move. The low level computer vision algorithms log primitive events of interest as observed facts, while the higher level Prolog based reasoning engine uses these facts in conjunction with predefined rules to recognize various activities in the input video streams. The system is illustrated in action on a multi-camera surveillance scenario that includes both security and safety violations.
Keywords: activities; algorithms; based; Computer; computerised; engine; higher; image; level; Logic; monitoring; multicamera; processing; programming; Prolog; PROLOG; reasoning; recognition; scenario; signal; streaming; streams; Surveillance; surveillance; system; video; VISION; vision; visual

Visualizing missing data: classification and empirical study - Eaton,C.; Plaisant, Catherine; Drizd,T. (Proceedings of INTERACT, 2005)
Most visualization tools fail to provide support for missing data. We identify sources of missing, and categorize data visualization techniques based on the impact missing data have on the display: region dependent, attribute dependent, and neighbor dependent. We then report on a user study with 30 participants that compared three design variants. A between-subject graph interpretation study provides strong evidence for the need of indicating the presence of missing information, and some direction for addressing the problem.

Visualizing Missing Data: Graph Interpretation User Study - Eaton,Cyntrica; Plaisant, Catherine; Drizd,Terence (Human-Computer Interaction - INTERACT 2005, 2005)
Most visualization tools fail to provide support for missing data. In this paper, we identify sources of missing data and describe three levels of impact missing data can have on the visualization: perceivable, invisible or propagating. We then report on a user study with 30 participants that compared three design variants. A between-subject graph interpretation study provides strong evidence for the need of indicating the presence of missing information, and some direction for addressing the problem.

What Are the Ants Doing? Vision-Based Tracking and Reconstruction of Control Programs - Egerstedt, M.; Balch, T.; Dellaert, F.; Delmotte, F.; Zia Khan (Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005. ICRA 2005, 2005)
In this paper, we study the problem of going from a real-world, multi-agent system to the generation of control programs in an automatic fashion. In particular, a computer vision system is presented, capable of simultaneously tracking multiple agents, such as social insects. Moreover, the data obtained from this system is fed into a mode-reconstruction module that generates low-complexity control programs, i.e. strings of symbolic descriptions of control-interrupt pairs, consistent with the empirical data. The result is a mechanism for going from the real system to an executable implementation that can be used for controlling multiple mobile robots.
Keywords: Animals; Automatic generation control; Biological information theory; Computer vision; Control systems; Mobile robots; Probability distribution; Robot control; target tracking; Trajectory

What children can teach us: Developing digital libraries for children with children - Druin, Allison (Library Quarterly, 2005)

Accelerated speech source localization via a hierarchical search of steered response power - Zotkin,Dmitry N; Duraiswami, Ramani (IEEE Transactions on Speech and Audio Processing, 2004)
Accurate and fast localization of multiple speech sound sources is a problem that is of significant interest in applications such as conferencing systems. Recently, approaches that are based on search for local peaks of the steered response power are becoming popular, despite their known computational expense. Based on the observation that the wavelengths of the sound from a speech source are comparable to the dimensions of the space being searched and that the source is broadband, we have developed an efficient search algorithm. Significant speedups are achieved by using coarse-to-fine strategies in both space and frequency. We present applications of the search algorithm to speed up simple delay-and-sum beamforming and steered response power phase-transform weighted (SRP-PHAT) source localization algorithms. A systematic series of comparisons with previous algorithms are made that show that the technique is much faster, robust, and accurate. The performance of the algorithm can be further improved by using constraints from computer vision.
Keywords: accelerated speech source localization; Acceleration; array signal processing; conferencing system; Delay; delay-and-sum beamforming; direction-of-arrival estimation; Frequency; hierarchical search algorithm; Inverse problems; multimedia applications; Multimedia communication; multiple speech sound source; Position measurement; Robustness; search problems; Sensor arrays; Signal processing algorithms; speech; speech enhancement; Speech processing; steered response power; steered response power phase-transform weighted source localization algorithm; transducer arrays; User interfaces

Adapting network structure for efficient team formation - Gaston,M.; Simmons,J.; desJardins, Marie (Proceedings of the AAAI 2004 Fall Symposium on Artificial Multi-agent Learning, 2004)

Adaptive Hindi OCRUsing Generalized Hausdorff Image Comparison - Ma,Huanfeng; David Doermann (ACMTransactions on Asian Language Information Processing, 2004)

An Appearance-based Approach for Consistent Labeling of Humans and Objects in Video - Balcells-Capellades,M.; DeMenthon,D.; David Doermann (Pattern Analysis and Applications, 2004)
We present an approach for consistently labeling people and for detecting human-object interactions using mono-camera surveillance video. The approach is based on a robust appearance based correlogram model which is combined with histogram information to model color distributions of people and objects in the scene. The models are dynamically built from non-stationary objects which are the outputs of background subtraction, and are used to identify objects on a frame-by-frame basis. We are able to detect when people merge into groups and to segment them even during partial occlusion. We can also detect when a person deposits or removes an object. The models persist when a person or object leaves the scene and are used to identify them when they reappear. Experiments show that the models are able to accommodate perspective foreshortening that occurs with overhead camera angles, as well as partial occlusion. The results show that this is an effective approach able to provide important information to algorithms performing higher-level analysis such as activity recognition, where human-object interactions play an important role.

Automatic position calibration of multiple microphones - Raykar,V.C.; Duraiswami, Ramani (Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on, 2004)
We describe a method to determine automatically the relative three dimensional positions of multiple microphones using at least five loudspeakers in unknown positions. The only assumption we make is that there is a microphone which is very close to a loudspeaker. In our experimental setup, we attach one microphone to each loudspeaker. We derive the maximum likelihood estimator and the solution turns out to be a non-linear least squares problem. A closed form solution which can be used as the initial guess for the minimization routine is derived. We also derive an approximate expression for the covariance of the estimator using the implicit function theorem. Using this, we analyze the performance of the estimator with respect to the positions of the loudspeakers. The algorithm is validated using both Monte-Carlo simulations and a real-time experimental setup.
Keywords: approximations; array; audio; AUTOMATIC; calibration; closed; covariance; dimensional; estimation; form; function; implicit; least; likelihood; loudspeakers; maximum; microphone; microphones; minimisation; minimization; multiple; nonlinear; position; positions; problem; processing; signal; solution; squares; theorem; three

Automatic recognition of spontaneous speech for access to multilingual oral history archives - Byrne,W.; David Doermann; Franz,M.; Gustman,S.; Hajic,J.; Oard, Douglas; Picheny,M.; Psutka,J.; Ramabhadran,B. (IEEE Transactions on Speech and Audio Processing, Special Issue on Spontaneous Speech Processing, 2004)
The MALACH project has the goal of developing the technologies needed to facilitate access to large collections of spontaneous speech. Its aim is to dramatically improve the state of the art in key Automatic Speech Recognition (ASR), Natural Language Processing (NLP) technologies for use in large-scale retrieval systems. The project leverages a unique collection of oral history interviews with survivors of the Holocaust that has been assembled and extensively annotated by the Survivors of the Shoah Visual History Foundation. This paper describes the collection, 116,000 hours of interviews in 32 languages, and the way in which system requirements have been discerned through user studies. It discusses ASR methods for very difficult speech (heavily accented, emotional, and elderly spontaneous speech), including transcription to create training data and methods for language modeling and speaker adaptation. Results are presented for for English and Czech. NLP results are presented for named entity tagging, topic segmentation, and supervised topic classification, and the architecture of an integrated search system that uses these results is described.

Background modeling and subtraction by codebook construction - Kim,Kyungnam; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
We present a new fast algorithm for background modeling and subtraction. Sample background values at each pixel are quantized into codebooks which represent a compressed form of background model for a long image sequence. This allows us to capture structural background variation due to periodic-like motion over a long period of time under limited memory. Our method can handle scenes containing moving backgrounds or illumination variations (shadows and highlights), and it achieves robust detection for compressed videos. We compared our method with other multimode modeling techniques.
Keywords: (signal); analysis; background; codebook; coding; colour; compression; construction; data; image; modeling; modeling; MOTION; multimode; quantisation; representation; sequence; sequences; subtraction; technique; video

Bbn/umd at duc-2004: Topiary - Zajic, David; Dorr, Bonnie J; Schwartz,R. (Proceedings of the HLT-NAACL 2004 Document Understanding Workshop, Boston, 2004)
This paper reports our results at DUC-2004 and describes our approach, im- plemented in a system called Topiary. We will show that the combination of linguistically motivated sentence com- pression with statistically selected topic terms performs better than either alone, according to some automatic summary evaluation measures.

Bringing together children and books: An initial descriptive study of children's book searching and selection behavior in a digital library - Reuter,K.; Druin, Allison (Proceedings of the American Society for Information science and Technology, 2004)

Building an information retrieval test collection for spontaneous conversational speech - Oard, Douglas; Soergel,Dagobert; David Doermann; Huang,Xiaoli; Murray,G. Craig; Wang,Jianqiang; Ramabhadran,Bhuvana; Franz,Martin; Gustman,Samuel; Mayfield,James; Kharevych,Liliya; Strassel,Stephanie (Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, 2004)
Test collections model use cases in ways that facilitate evaluation of information retrieval systems. This paper describes the use of search-guided relevance assessment to create a test collection for retrieval of spontaneous conversational speech. Approximately 10,000 thematically coherent segments were manually identified in 625 hours of oral history interviews with 246 individuals. Automatic speech recognition results, manually prepared summaries, controlled vocabulary indexing, and name authority control are available for every segment. Those features were leveraged by a team of four relevance assessors to identify topically relevant segments for 28 topics developed from actual user requests. Search-guided assessment yielded sufficient inter-annotator agreement to support formative evaluation during system development. Baseline results for ranked retrieval are presented to illustrate use of the collection.
Keywords: assessment; Automatic speech recognition; oral history; search-guided relevance

Building KidPad: an application for children's collaborative storytelling - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison (Software: Practice and Experience, 2004)

Capture and recreation of higher order 3d sound fields via reciprocity - Li,Z.; Duraiswami, Ramani; Gumerov, Nail A. (International Conference on Audio Display, 2004)
We propose a unified and simple approach for capturing andrecreating 3D sound fields by exploring the reciprocity prin- ciple that is satisfied between the two processes. Our ap- proach makes the system easy to build, and practical. Us- ing this approach, we can capture the 3D sound field by a spherical microphone array and recreate it using a spheri- cal loudspeaker array, and ensure that the recreated sound field matches the recorded field up to a high order of spheri- cal harmonics. A design example and simulation results are presented. For some regular or semi-regular microphone layouts, we design an efficient parallel implementation of the multi-directional spherical beamformer by using the ro- tational symmetries of the beampattern and of the spherical microphone array. This can be implemented in either soft- ware or hardware. A simple design example is presented to demonstrate the idea. It can be easily adapted for other regular or semi-regular layouts of microphones.

Characterization of the Overall Rotational Diffusion of a Protein From 15N Relaxation Measurements and Hydrodynamic Calculations - Blake-Hall,Jennifer; Walker,Olivier; Fushman, David (Protein NMR Techniques, 2004)
In this chapter, we discuss experimental and theoretical methods for characterizing the overall rotational diffusion of molecules in solution. The methods are illustrated for the B3 domain of protein G, a small protein with rotational anisotropy of D par / D perp = 1.4. The rotational diffusion tensor of the protein is determined directly from 15 N relaxation measurements. The experimental data are treated assuming various possible models for the overall tumbling: isotropic, axially symmetric, and fully anisotropic, and the results of these analyses are compared to determine an adequate diffusion model for the protein. These experimentally derived characteristics of the protein are compared with the results of theoretical calculations of the diffusion tensor using various hydrodynamic models, to find optimal models and parameter sets for theoretical predictions. We also derive model-free characteristics of internal backbone motions in the protein, to show that different models for the overall motion can result in significantly different pictures of motion. This emphasizes the necessity of accurately characterizing the overall tumbling of a molecule to determine its local dynamics.
Keywords: Biomedical and Life Sciences

Comparative Genome Assembly - Pop, Mihai; Phillippy,Adam; Delcher,Arthur L.; Salzberg,Steven L. (Briefings in Bioinformatics, 2004)
One of the most complex and computationally intensive tasks of genome sequence analysis is genome assembly. Even today, few centres have the resources, in both software and hardware, to assemble a genome from the thousands or millions of individual sequences generated in a whole-genome shotgun sequencing project. With the rapid growth in the number of sequenced genomes has come an increase in the number of organisms for which two or more closely related species have been sequenced. This has created the possibility of building a comparative genome assembly algorithm, which can assemble a newly sequenced genome by mapping it onto a reference genome.We describe here a novel algorithm for comparative genome assembly that can accurately assemble a typical bacterial genome in less than four minutes on a standard desktop computer. The software is available as part of the open-source AMOS project.
Keywords: Assembly; comparative genomics; open source; shotgun sequencing

Compressing historical information in sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04, 2004)

Computation of Green's function for finite-size photonic crystals by boundary element method - Seydou,F.; Ramahi,O.; Duraiswami, Ramani; Seppdnen,T. (Antennas and Propagation Society International Symposium, 2004. IEEE, 2004)
We have derived a new integral equation method for computing the Green's function for 2D electromagnetic wave propagation in a finite size photonic crystal. The method is also used for deriving the multipole expansions for the case of circular cylinders. This derivation is different from the ones in the literature. Our numerical results show an excellent agreement of the two algorithms. In the future we would like to expand the method to the numerical solution of the three-dimensional electromagnetic problem.
Keywords: 2D; boundary; boundary-elements; circular; crystals; cylinders; electromagnetic; element; equation; equations; expansions; finite-size; function; function; Green; Green's; integral; method; methods; multipole; photonic; propagation; wave

Constant-time navigation in four-dimensional nested simplicial meshes - Lee,M.; De Floriani, Leila; Samet, Hanan (Shape Modeling Applications, 2004. Proceedings, 2004)
We consider a recursive decomposition of a four-dimensional hypercube into a hierarchy of nested 4-dimensional simplexes, that we call pentatopes. The paper presents an algorithm for finding the neighbors of a pentatope along its five tetrahedral faces in constant time. To this aim, we develop a labeling technique for nested pentatopes that enables their identification by using location codes. The constant-time behavior is achieved through bit manipulation operations, thus avoiding traversing the simplicial hierarchy via pointer following. We discuss an application of this representation to multi-resolution representations of four-dimensional scalar fields. Extracting adaptive continuous approximations of the scalar field from such a model requires generating conforming meshes, i.e., meshes in which the pentatopes match along their tetrahedral faces. Our neighbor finding algorithm enables computing face-adjacent pentatopes efficiently.
Keywords: 4-dimensional; adaptive; algorithm; approximations; bit; codes; computational; constant-time; continuous; decomposition; face-adjacent; faces; fields; finding; following; four-dimensional; generation; geometry; hierarchy; hypercube; location; manipulation; mesh; meshes; multiresolution; navigation; neighbor; nested; operations; pentatopes; pointer; recursive; representation; scalar; simplexes; simplicial; tetrahedral

A data structure for non-manifold simplicial d-complexes - De Floriani, Leila; Greenfieldboyce,David; Hui,Annie (Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 2004)
We propose a data structure for d-dimensional simplicial complexes, that we call the Simplified Incidence Graph (SIG). The simplified incidence graph encodes all simplices of a simplicial complex together with a set of boundary and partial co-boundary topological relations. It is a dimension-independent data structure in the sense that it can represent objects of arbitrary dimensions. It scales well to the manifold case, i.e. it exhibits a small overhead when applied to simplicial complexes with a manifold domain, Here, we present efficient navigation algorithms for retrieving all topological relations from a SIG, and an algorithm for generating a SIG from a representation of the complex as an incidence graph. Finally, we compare the simplified incidence graph with the incidence graph, with a widely-used data structure for d-dimensional pseudo-manifold simplicial complexes, and with two data structures specific for two-and three-dimensional simplicial complexes.

Divergence Unraveling for Word Alignment... - Dorr, Bonnie J; Ayan,N.F.; Habash,N. (Natural Language Engineering, 2004)
We describe the use of parallel text for divergence unraveling in word-level alignment. DUSTer (Divergence Unraveling for Statistical Translation) is a system that combines linguistic and statistical knowledge to resolve structural di#erences between languages, i.e., translation divergences, during the process of alignment. Our immediate goal is to induce word-level alignments that are more accurate than those produced by an existing state-ofthe -art statistical system. The long-term goal is to improve the output quality of statistical machine translation and lexical acquisition systems by using DUSTer as one possible input to a framework that accommodates multiple alignments. We show that a systematic characterization of alignment errors made by a statistical system validates the use of linguistically-motivated universal rules for identifying and handling divergences. These rules relate one or more linguistically-motivated categories associated with the (English) input words to those of another language (foreign language); the resulting match sets are used to infer corrected alignments. Using a human-aligned corpus as our gold standard, we demonstrate an improvement in alignments over an existing state-of-the-art alignment algorithm.

An Efficient and Robust Human Classification Algorithm using Finite Frequencies Probing - Yang Ran; Weiss, I.; Qinfen Zheng; Davis, Larry S. (Computer Vision and Pattern Recognition Workshop, 2004. CVPRW '04. Conference on, 2004)
This paper describes a periodicity motion detection based object classification algorithm for infrared videos. Given a detected and tracked object, the goal is to analyze the periodic signature of its motion pattern. We propose an efficient and robust solution, which is related to the frequency estimation in speech recognition. Periodic reference functions are correlated with the video signal. Experimental results for both infrared and visible videos acquired by ground-based as well as airborne moving sensors are presented.

Efficient computation of acoustical scattering from N spheres via the fast multipole method accelerated flexible generalized minimal residual method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2004)
Many problems require computation of acoustic fields in systems consisting of a large number of scatterers, which can be modeled as spheres (or enclosed by them). These spheres can have different sizes, can be arbitrarily distributed in three dimensional space, and can have different surface impedance. Solution of this problem via direct T‐matrix approach [Gumerov and Duraiswami, J. Acoust. Soc. Am., 112, 2688–2701 (2002)] is practical only for relatively low number of scatterers, N, since its computational complexity grows as O(N3). We developed and implemented an efficient computational technique, based on an iterative solver employing a flexible generalized minimal residual method with a right preconditioner. Matrix‐vector multiplications involving a large system matrix and the preconditioner are sped up with the aid of the multilevel fast multipole method. We tested the accuracy, convergence and complexity of the method on example problems with N∼104 (millions of unknowns). These tests showed that the method is accurate for a range of frequencies, and experimentally scales as O(N1.25). The method has substantial advantages in speed and convergence compared to the reflection method reported earlier [Gumerov and Duraiswami, J. Acoust. Soc. Am., 113, 2334 (2002)]. [Work supported NSF Awards 0086075 and 0219681, which are gratefully acknowledged.]

Empirical-based estimation of the effect on software dependability of a technique for architecture conformance verification - Asgari, S.; Basili, Victor R.; Costa,P.; Donzelli,P.; Hochstein, L.; Lindvall,M.; Rus,I.; Shull, F.; Tvedt,R.; Zelkowitz, Marvin V (Proceedings of the ICSE 2004 Workshop on Architecting Dependable Systems, Edinburgh, UK, 2004)
The High Dependability Computing Program (HDCP)project is a NASA initiative for increasing dependability of software-based systems. It researches achieving high dependability by introducing new technologies. We focus on the evaluation of the effectiveness of technologies with respect to dependability. We employ empirical evaluation methods along with evaluation testbeds. In this paper, our technology evaluation approach is described. A testbed representative of air traffic control applications is used. An experiment to evaluate a technology to for identification of architectural violations is presented.

Enabling On-chip Diversity Through Architectural Communication Design - Tudor Dumitras; Kerner, Sam; Marculescu, Radu (ASP-DAC '04 Proceedings of the 2004 Asia and South Pacific Design Automation Conference, 2004)
In this paper, we explore a new concept, called on-chip diversity, and introduce a design methodology for such emerging systems. Simply speaking, on-chip diversity means mixing different architectures and/or technologies in a multiple voltage/frequency island setup in order to achieve the highest levels of performance, fault-tolerance and the needed flexibility in SoC design. As the main contribution, we present the challenges in implementing an efficient communication architecture for on-chip diversity and outline a unified framework which addresses some of these issues. We then provide comparative experimental results and make a qualitative analysis of different architectural choices in the design of the on-chip communication. Having the acoustic beamforming as driver application, we show that an efficient communication infrastructure can be constructed by carefully analyzing the characteristics of the application and the required levels of power, performance and fault-tolerance.

Extracting the frequencies of the pinna spectral notches from measured head-related impulse responses - Raykar,Vikas C.; Duraiswami, Ramani; Yegnanarayana,B. (The Journal of the Acoustical Society of America, 2004)
Experimental data are available for the Head‐related impulse response (HRIR) for several azimuth and elevation angles, and for several subjects. The measured HRIR depends on several factors such as reflections from body parts (torso, shoulder, and knees), head diffraction, and reflection/diffraction effects due to the external ear (pinna). Due to the combined influence of these factors on the HRIR, it is difficult to isolate features thought to be perceptually important (such as the frequencies of pinna spectral notches) using standard signal‐processing techniques. Signal‐processing methods to extract the frequencies of the pinna spectral notches from the HRIR are presented. The techniques are applied to extracting the frequencies of the pinna spectral notches from the publicly available HRIR databases. A brief discussion relating the notch frequencies to the physical dimensions and the shape of the pinna is given. [The support of NSF Award ITR‐0086075 is gratefully acknowledged.]

Extrinsic Evaluation of Automatic Metrics for Summarization - Dorr, Bonnie J; Monz,Christof; Oard, Douglas; President,Stacy; Zajic, David; Schwartz,Richard (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
This paper describes extrinsic-task evaluation of summarization. We show that it is possible to save time using summaries for relevance assessment without adversely impacting the degree of accuracy that would be possible with full documents. In addition, we demonstrate that the extrinsic task we have selected exhibits a high degree of interannotator agreement, i.e., consistent relevance decisions across subjects. We also conducted a composite experiment that better reflects the actual document selection process and found that using a surrogate improves the processing speed over reading the entire document. Finally, we have found a small yet statistically significant correlation between some of the intrinsic measures and a user's performance in an extrinsic task. The overall conclusion we can draw at this point is that ROUGE-1 does correlate with precision and to a somewhat lesser degree with accuracy, but that it remains to be investigated how stable these correlations are and how differences in ROUGE-1 translate into significant differences in human performance in an extrinsic task.
Keywords: *ABSTRACTS; *ACCURACY; *DATA SUMMARIZATION; *DOCUMENT SUMMARIES; *DOCUMENTS; *READING MACHINES; *SOFTWARE METRICS; *STATISTICAL ANALYSIS; ABSTRACT SELECTION; ANNOTATIONS; Automation; COMPUTER PROGRAMMING AND SOFTWARE; COMPUTER SYSTEMS; CORRELATION TECHNIQUES; DATA PROCESSING; DOCUMENT SUMMARIES; EXTRINSIC TASKS; Information retrieval; INFORMATION SCIENCE; PERFORMANCE(HUMAN); PRECISION; RELEVANCY; ROUGE-1 COMPUTER PROGRAM; STATISTICS AND PROBABILITY; TEST AND EVALUATION

FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES - Tang,Zhihui; Duraiswami, Ramani; Gumerov, Nail A. (Technical Reports from UMIACS UMIACS-TR-2004-08, 2004)
The Pascal matrix arises in a number of applications. We present a few waysto decompose the Pascal matrices of size $n × n$ into products of matrices with structure. Based on these decompositions, we propose fast algorithms to compute the product of a Pascal matrix and a vector with omplexity $O(n\log n)$. We also present a strategy to stabilize the proposed algorithms. Finally, we also present some interesting properties of the Pascal matrices that help us to compute fast the product of the inverse of a Pascal matrix and a vector, and fast algorithms for generalized Pascal Matrices. UMIACS-TR-2004-08
Keywords: Technical Report

Fast Multipole Methods For The Helmholtz Equation In Three Dimensions - Gumerov, Nail A.; Duraiswami, Ramani (Elsevier, 2004)
This volume in the Elsevier Series in Electromagnetism presents a detailed, in-depth and self-contained treatment of the Fast Multipole Method and its applications to the solution of the Helmholtz equation in three dimensions. The Fast Multipole Method was pioneered by Rokhlin and Greengard in 1987 and has enjoyed a dramatic development and recognition during the past two decades. This method has been described as one of the best 10 algorithms of the 20th century. Thus, it is becoming increasingly important to give a detailed exposition of the Fast Multipole Method that will be accessible to a broad audience of researchers. This is exactly what the authors of this book have accomplished. For this reason, it will be a valuable reference for a broad audience of engineers, physicists and applied mathematicians.The Only book that provides comprehensive coverage of this topic in one location.Presents a review of the basic theory of expansions of the Helmholtz equation solutionsComprehensive description of both mathematical and practical aspects of the fast multipole method and it's applications to issues described by the Helmholtz equation
Keywords: Electronic books; Helmholtz equation; Mathematics / Mathematical Analysis; Science / Physics / Electromagnetism; Science / Physics / Magnetism; Technology & Engineering / Acoustics & Sound; Technology & Engineering / Electrical

A fine-structure image/video quality measure using local statistics - Kim,Kyungnam; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
An objective no-reference measure is presented to assess line-structure image/video quality. It was designed to measure image/video quality for video surveillance applications, especially for background modeling and foreground object detection. The proposed measure using local statistics reflects image degradation well in terms of noise and blur. The experimental results on a background subtraction algorithm validate the usefulness of the proposed measure, by showing its correlation with the algorithm's performance.
Keywords: algorithm; background; degradation; detection; foreground; image; line-structure; local; measure; modeling; no-reference; object; objective; processing; QUALITY; signal; statistics; subtraction; surveillance; video

Flexible layout and optimal cancellation of the orthonormality error for spherical microphone arrays - Zhiyun Li; Duraiswami, Ramani; Grassi,E.; Davis, Larry S. (Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on, 2004)
This paper describes an approach to achieving a flexible layout of microphones on the surface of a spherical microphone array for beamforming. Our approach achieves orthonormality of spherical harmonics to higher order for relatively distributed layouts. This gives great flexibility in microphone layout on the spherical surface. One direct advantage is that it makes it much easier to build a real world system, such as those with cable outlets and a mounting base, with minimal effects on the performance. Simulation results are presented.
Keywords: array; audio; base; beamforming; cable; cancellation; correction; error; flexible; harmonics; higher; layout; microphone; microphones; mounting; optimization; order; orthonormality; outlets; processing; signal; spherical; surface

Free-Living to Freewheeling: The Evolution of Vibrio cholerae from Innocence to Infamy - Rita R Colwell; Faruque,S. M.; Nair,G. B. (Infectious Disease and Host-Pathogen EvolutionInfectious Disease and Host-Pathogen Evolution, 2004)

Gait recognition using image self-similarity - BenAbdelkader,Chiraz; Cutler,Ross G.; Davis, Larry S. (EURASIP J. Appl. Signal Process., 2004)
Gait is one of the few biometrics that can be measured at a distance, and is hence useful for passive surveillance as well as biometric applications. Gait recognition research is still at its infancy, however, and we have yet to solve the fundamental issue of finding gait features which at once have suffcient discrimination power and can be extracted robustly and accurately from low-resolution video. This paper describes a novel gait recognition technique based on the image self-similarity of a walking person. We contend that the similarity plot encodes a projection of gait dynamics. It is also correspondence-free, robust to segmentation noise, and works well with low-resolution video. The method is tested on multiple data sets of varying sizes and degrees of diffculty. Performance is best for fronto-parallel viewpoints, whereby a recognition rate of 98% is achieved for a data set of 6 people, and 70% for a data set of 54 people.
Keywords: behavioral biometrics; gait recognition; human identification at a distance; human movement analysis; pattern recognition

A generic construction for intrusion-resilient public-key encryption - Dodis,Y.; Franklin,M.; Katz, Jonathan; Miyaji,A.; Yung,M. (Topics in Cryptology–CT-RSA 2004, 2004)
In an intrusion-resilient cryptosystem [10], two entities (a user and a base) jointly evolve a secret decryption key; this provides very strong protection against an active attacker who can break into the user and base repeatedly and even simultaneously. Recently, a construction of an intrusion-resilient public-key encryption scheme based on specific algebraic assumptions has been shown [6]. We generalize this previous work and present a more generic construction for intrusion-resilient public-key encryption from any forward-secure public-key encryption scheme satisfying a certain homomorphic property.

Generic sentence fusion is an ill-defined summarization task - Daumé, Hal; Marcu,D. (Proceedings of the Text Summarization Branches Out Workshop at ACL, 2004)

Handling estimation errors in database query processing - Deshpande, Amol (University of California at Berkeley, 2004)
A query optimizer is among the core pieces of a modern database management system, responsible for choosing a query execution plan for a user-provided declarative query. Query optimizers typically employ a cost estimation procedure to compare costs of different execution plans. Errors in this estimation process are quite common and arise due to reasons such as incomplete and insufficient statistical information about the data, and highly variable runtime environments that can affect the plan costs in unpredictable manners. Two approaches have been previously proposed for handling such estimation errors: (1) building sophisticated synopsis techniques that succintly summarize the data in the database and thus provide more statistical information to the query optimizer, and (2) aggressive reoptimization schemes that attempt to change the execution plans chosen to execute queries, on-the-fly. In the first part of this dissertation, we focus on building and using sophisticated synopsis techniques in the context of a traditional query optimizer. We propose a class of synopsis techniques called DEPENDENCY-B ASED Histograms that use statistical interaction models to exploit the correlations in the data, and to estimate selectivities efficiently. We also develop an efficient algorithm to search through the class of statistical models that we employ. Using sophisticated synopsis techniques such as these in the context of a traditional query optimizer poses interesting computational challenges; a naive approach to doing this could make the query optimization process so expensive as to be ineffective. This naturally leads to an “estimation planning” problem that asks for the best strategy to compute all the estimates required by an optimizer using the synopses at its disposal. We analyze this problem, its solution space, and propose algorithms to efficiently find good estimation plans. There are many scenarios where sophisticated synopsis techniques may not be applicable; examples include wide area and web based data sources, data streams and complex data domains. In the second part of this dissertation, we explore a highly-adaptive query processing technique called eddies that treats query processing as routing of tuples through operators, and adapts to changing data and runtime characteristics by continuously changing the order in which tuples are routed. We analyze the eddies architecture and identify a fundamental flaw in the basic design of the architecture: the burden of history in routing. (Abstract shortened by UMI.)

Headline evaluation experiment results - Zajic, David; Dorr, Bonnie J; Schwartz,R.; President,S. (University of Maryland, College Park, MD. UMIACS-TR-2004-18, 2004)
This technical report describes an experiment intending to show that different summarizationtechniques have an effect on human performance of an extrinsic task. The task is document selection in the context of information retrieval. We conclude that the task was too difficult and ambiguous for subjects to perform at the level required in order to make statistically significant claims about the relationship between summarization techniques and human performance. An alternate interpretation of the experimental results is described and plans for future experiments are discussed.

Hierarchical in-network data aggregation with quality guarantees - Deligiannakis,A.; Kotidis,Y.; Roussopoulos, Nick (Advances in Database Technology-EDBT 2004, 2004)

iCLEF 2003 at Maryland: Translation Selection and Document Selection - Dorr, Bonnie J; He,Daqing; Luo,Jun; Oard, Douglas; Schwartz,Richard; Wang,Jianqiang; Zajic, David (Comparative Evaluation of Multilingual Information Access SystemsComparative Evaluation of Multilingual Information Access Systems, 2004)
Maryland performed two sets of experiments for the 2003 Cross-Language Evaluation Forum’s interactive track, one focused on interactive selection of appropriate translations for query terms, the second focused on interactive selection of relevant documents. Translation selection was supported using possible synonyms discovered through back translation and two techniques for generating KeyWord In Context (KWIC) examples of usage. The results indicate that searchers typically achieved a similar search effectiveness using fewer query iterations when interactive translation selection was available. For document selection, a complete extract of the first 40 words of each news story was compared to a compressed extract generated using an automated parse-and-trim approach that approximates one way in which people can produce headlines. The results indicate that compressed “headlines” result in faster assessment, but with a 20% relative reduction in the F α = 0.8 search effectiveness measure.

iCLEF 2003 at Maryland: Translation selection and document selection - Dorr, Bonnie J; He,D.; Luo,J.; Oard, Douglas; Schwartz,R.; Wang,J.; Zajic, David (Comparative Evaluation of Multilingual Information Access Systems, 2004)

IDeixis: image-based Deixis for finding location-based information - Tom Yeh; Tollmar,Konrad; Darrell,Trevor (CHI '04 extended abstracts on Human factors in computing systems, 2004)
We demonstrate an image-based approach to specifying location and finding location-based information from camera-equipped mobile devices. We introduce a point-by-photograph paradigm, where users can specify a location 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. In contrast to conventional approaches to location detection, our method can refer to distant locations and does not require any physical infrastructure beyond mobile internet service. We have developed a prototype on a camera phone and conducted user studies to demonstrate the efficacy of our approach compared to other alternatives.
Keywords: content-based image retrieval; context-aware computing; location-awareness; Mobile computing

Ideixis-image-based deixis for finding location-based information - Tollmar,K.; Tom Yeh; Darrell,T. (Mobile HCI, Vienna, Austria, Pages, 2004)

IDeixis–Searching the Web with Mobile Images for Location-Based Information - Tollmar,K.; Tom Yeh; Darrell,T. (Mobile Human-Computer Interaction–MobileHCI 2004, 2004)

Identification of confusable drug names: a new approach and evaluation methodology - Kondrak,Grzegorz; Dorr, Bonnie J (Proceedings of the 20th international conference on Computational Linguistics, 2004)
This paper addresses the mitigation of medical errors due to the confusion of sound-alike and look-alike drug names. Our approach involves application of two new methods---one based on orthographic similarity ("look-alike") and the other based on phonetic similarity ("sound-alike"). We present a new recall-based evaluation methodology for determining the effectiveness of different similarity measures on drug names. 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 the feature-based phonetic approach (ALINE) outperforms orthographic approaches on a test set containing solely sound-alike confusion pairs. However, an approach that combines several different measures achieves the best results on both test sets.

Improved Multiuser Detectors Employing Genetic Algorithms in a Space-Time Block Coded System, Yinggang Du and Kam Tai Chan - Self-Similarity,G.R.U.I.; BenAbdelkader,C.; Cutler,R.G.; Davis, Larry S.; Local,F.R.U.; Global Features,J.H.; Yuen, P.C.; Lai,JH; Li,C. (Signal, 2004)

Improving performance of heterogeneous agents - \Özcan,F.; V.S. Subrahmanian; Dix,J. (Annals of Mathematics and Artificial Intelligence, 2004)

In Memory of Azriel Rosenfeld - Davis, Larry S. (International Journal of Computer Vision, 2004)

Incremental density approximation and kernel-based bayesian filtering for object tracking - Han,B.; Comaniciu, D.; Zhu,Y.; Davis, Larry S. (IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004)
Statistical density estimation techniques are used in manycomputer vision applications such as object tracking, back- ground subtraction, motion estimation and segmentation. The particle filter (Condensation) algorithm provides a gen- eral framework for estimating the probability density func- tions (pdf) of general non-linear and non-Gaussian systems. However, since this algorithm is based on a Monte Carlo ap- proach, where the density is represented by a set of random samples, the number of samples is problematic, especially for high dimensional problems. In this paper, we propose an alternative to the classical particle filter in which the un- derlying pdf is represented with a semi-parametric method based on a mode finding algorithm using mean-shift. A mode propagation technique is designed for this new representa- tion for tracking applications. A quasi-random sampling method [14] in the measurement stage is used to improve performance, and sequential density approximation for the measurements distribution is performed for efficient compu- tation. We apply our algorithm to a high dimensional color- based tracking problem, and demonstrate its performance by showing competitive results with other trackers.

Inducing a semantic frame lexicon from WordNet data - Green,Rebecca; Dorr, Bonnie J (Proceedings of the 2nd Workshop on Text Meaning and Interpretation, 2004)
This paper presents SemFrame, a system that automatically induces the names and internal structures of semantic frames. After SemFrame identifies sets of frame-evoking verb synsets, the conceptual density of nodes in the WordNet network for corresponding nouns and noun synsets is computed and analyzed. Conceptually dense nodes are candidates for frame names and frame slots. Ca. 76% of the frame names and 87% of the frame slots generated by SemFrame are rated adequate by human judges.

Inducing frame semantic verb classes from WordNet and LDOCE - Green,R.; Dorr, Bonnie J; Resnik, Philip (Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, 2004)
This paper presents SemFrame, a systemthat induces frame semantic verb classes from WordNet and LDOCE. Semantic frames are thought to have significant potential in resolving the paraphrase problem challenging many language- based applications. When compared to the handcrafted FrameNet, SemFrame achieves its best recall-precision balance with 83.2% recall (based on SemFrame's coverage of FrameNet frames) and 73.8% precision (based on SemFrame verbs’ semantic relatedness to frame-evoking verbs). The next best performing semantic verb classes achieve 56.9% recall and 55.0% precision.

An initial study of overheads of eddies - Deshpande, Amol (SIGMOD Rec., 2004)
An eddy [2] is a highly adaptive query processing operator that continuously reoptimizes a query in response to changing runtime conditions. It does this by treating query processing as routing of tuples through operators and making per-tuple routing decisions. The benefits of such adaptivity can be significant, especially in highly dynamic environments such as data streams, sensor query processing, web querying, etc. Various parties have asserted that the cost of making per-tuple routing decisions is prohibitive. We have implemented eddies in the PostgreSQL open source database system [1] in the context of the TelegraphCQ project. In this paper, we present an "apples-to-apples" comparison of PostgreSQL query processing overhead with and without eddies. Our results show that with some minor tuning, the overhead of the eddy mechanism is negligible.

Interlingual Annotation for MT Development - Reeder,Florence; Dorr, Bonnie J; Farwell,David; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Levin,Lori; Mitamura,Teruko; Miller,Keith; Rambow,Owen; Siddharthan,Advaith (Machine Translation: From Real Users to ResearchMachine Translation: From Real Users to Research, 2004)
MT systems that use only superficial representations, including the current generation of statistical MT systems, have been successful and useful. However, they will experience a plateau in quality, much like other “silver bullet” approaches to MT. We pursue work on the development of interlingual representations for use in symbolic or hybrid MT systems. In this paper, we describe the creation of an interlingua and the development of a corpus of semantically annotated text, to be validated in six languages and evaluated in several ways. We have established a distributed, well-functioning research methodology, designed a preliminary interlingua notation, created annotation manuals and tools, developed a test collection in six languages with associated English translations, annotated some 150 translations, and designed and applied various annotation metrics. We describe the data sets being annotated and the interlingual (IL) representation language which uses two ontologies and a systematic theta-role list. We present the annotation tools built and outline the annotation process. Following this, we describe our evaluation methodology and conclude with a summary of issues that have arisen.

Interlingual annotation of multilingual text corpora - Farwell,D.; Helmreich,S.; Dorr, Bonnie J; Habash,N.; Reeder,F.; Miller,K.; Levin,L.; Mitamura,T.; Hovy,E.; Rambow,O.; others (Proceedings of the North American Chapter of the Association for Computational Linguistics Workshop on Frontiers in Corpus Annotation, 2004)
This paper describes a multi-site project toannotate six sizable bilingual parallel corpora for interlingual content. After presenting the background and objectives of the effort, we describe the data set that is being annotated, the interlingua representation language used, an interface environment that supports the an- notation task and the annotation process itself. We will then present a preliminary version of our evaluation methodology and conclude with a summary of the current status of the project along with a number of issues which have arisen.

INTERPOLATION AND RANGE EXTRAPOLATION OF HEAD RELATED TRANSFER FUNCTIONS - Duraiswami, Ramani; Zotkin,Dmitry N; Gumerov, Nail A. (IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 2004)

Iterative figure-ground discrimination - Zhao, L.; Davis, Larry S. (Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on, 2004)
Figure-ground discrimination is an important problem in computer vision. Previous work usually assumes that the color distribution of the figure can be described by a low dimensional parametric model such as a mixture of Gaussians. However, such approach has difficulty selecting the number of mixture components and is sensitive to the initialization of the model parameters. In this paper, we employ non-parametric kernel estimation for color distributions of both the figure and background. We derive an iterative sampling-expectation (SE) algorithm for estimating the color, distribution and segmentation. There are several advantages of kernel-density estimation. First, it enables automatic selection of weights of different cues based on the bandwidth calculation from the image itself. Second, it does not require model parameter initialization and estimation. The experimental results on images of cluttered scenes demonstrate the effectiveness of the proposed algorithm.
Keywords: algorithm; analysis; Bandwidth; calculation; Color; colour; Computer; density; dimensional; discrimination; distribution; distributions; Estimation; estimation; expectation; figure; Gaussian; ground; image; initialization; iterative; Kernel; low; methods; mixture; model; model; nonparametric; parameter; parametric; processes; sampling; sampling; segmentation; segmentation; statistics; theory; vision

A lexically-driven algorithm for disfluency detection - Snover,Matthew; Dorr, Bonnie J; Schwartz,Richard (Proceedings of HLT-NAACL 2004: Short Papers, 2004)
This paper describes a transformation-based learning approach to disfluency detection in speech transcripts using primarily lexical features. Our method produces comparable results to two other systems that make heavy use of prosodic features, thus demonstrating that reasonable performance can be achieved without extensive prosodic cues. In addition, we show that it is possible to facilitate the identification of less frequently disfluent discourse markers by taking speaker style into account.

Lifting the burden of history from adaptive query processing - Deshpande, Amol; Hellerstein,Joseph M. (Proceedings of the Thirtieth international conference on Very large data bases - Volume 30, 2004)
Adaptive query processing schemes attempt to re-optimize query plans during the course of query execution. A variety of techniques for adaptive query processing have been proposed, varying in the granularity at which they can make decisions [8]. The eddy [1] is the most aggressive of these techniques, with the flexibility to choose tuple-by-tuple how to order the application of operators. In this paper we identify and address a fundamental limitation of the original eddies proposal: the burden of history in routing. We observe that routing decisions have long-term effects on the state of operators in the query, and can severely constrain the ability of the eddy to adapt over time. We then propose a mechanism we call STAIRs that allows the query engine to manipulate the state stored inside the operators and undo the effects of past routing decisions. We demonstrate that eddies with STAIRs achieve both high adaptivity and good performance in the face of uncertainty, outperforming prior eddy proposals by orders of magnitude.

Location diversity in anonymity networks - Feamster, Nick; Dingledine,Roger (Proceedings of the 2004 ACM workshop on Privacy in the electronic society, 2004)
Anonymity networks have long relied on diversity of node location for protection against attacks---typically an adversary who can observe a larger fraction of the network can launch a more effective attack. We investigate the diversity of two deployed anonymity networks, Mixmaster and Tor, with respect to an adversary who controls a single Internet administrative domain. Specifically, we implement a variant of a recently proposed technique that passively estimates the set of administrative domains (also known as autonomous systems, or ASes) between two arbitrary end-hosts without having access to either end of the path. Using this technique, we analyze the AS-level paths that are likely to be used in these anonymity networks. We find several cases in each network where multiple nodes are in the same administrative domain. Further, many paths between nodes, and between nodes and popular endpoints, traverse the same domain.
Keywords: anonymity; interdomain routing; mix networks

Low-dimensional embedding with extra information - Bǎdoiu,M.; Demaine,E. D; Hajiaghayi, Mohammad T.; Indyk,P. (Proceedings of the twentieth annual symposium on Computational geometry, 2004)

Machine printed text and handwriting identification in noisy document images - Yefeng Zheng; Huiping Li; David Doermann (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2004)
In this paper, we address the problem of the identification of text in noisy document images. We are especially focused on segmenting and identifying between handwriting and machine printed text because: 1) Handwriting in a document often indicates corrections, additions, or other supplemental information that should be treated differently from the main content and 2) the segmentation and recognition techniques requested for machine printed and handwritten text are significantly different. A novel aspect of our approach is that we treat noise as a separate class and model noise based on selected features. Trained Fisher classifiers are used to identify machine printed text and handwriting from noise and we further exploit context to refine the classification. A Markov Random Field-based (MRF) approach is used to model the geometrical structure of the printed text, handwriting, and noise to rectify misclassifications. Experimental results show that our approach is robust and can significantly improve page segmentation in noisy document collections.
Keywords: Automated; Reading; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Computer-Assisted; Information Storage and Retrieval; Models; Computer-Assisted; Pattern Recognition; Computer-Assisted; Stochastic Processes; Subtraction Technique; User-Computer Interface; Writing; Markov random field; fisher classifiers; handwriting identification; machine printed text; noisy document images; page segmentation; recognition techniques; text identification; Markov processes; document image processing; feature extraction; handwriting recognition; Statistical; Numerical Analysis

Maintaining RDF views - Deng,Y.; Hung,E.; V.S. Subrahmanian (Tech. Rep. CS-TR-4612 (UMIACS-TR-2004-54), 2004)
Resource Description Framework (RDF) has been recommended bythe World Wide Web Consortium for integrating web data. RDF specifications are increasingly being stored in RDF databases. Many applications will maintain views over RDF databases – these views may describe resources of interest to the owner of the views. As data about the resources available on the web is subject to frequent change, there is a need to incrementally maintain such views. We present algorithms to maintain materialized RDF views when data is inserted into, deleted from, or modified in RDF database instances. We have developed a prototype of our algorithms. For each of these three cases, we compare the performance of our algorithm against the naive approach of storing RDF data in a relational database and using the standard view maintenance algorithm

An MCMC-Based Particle Filter for Tracking Multiple Interacting Targets - Zia Khan; Balch, Tucker; Dellaert, Frank (Computer Vision - ECCV 2004, 2004)
We describe a Markov chain Monte Carlo based particle filter that effectively deals with interacting targets, i.e., targets that are influenced by the proximity and/or behavior of other targets. Such interactions cause problems for traditional approaches to the data association problem. In response, we developed a joint tracker that includes a more sophisticated motion model to maintain the identity of targets throughout an interaction, drastically reducing tracker failures. The paper presents two main contributions: (1) we show how a Markov random field (MRF) motion prior, built on the fly at each time step, can substantially improve tracking when targets interact, and (2) we show how this can be done efficiently using Markov chain Monte Carlo (MCMC) sampling. We prove that incorporating an MRF to model interactions is equivalent to adding an additional interaction factor to the importance weights in a joint particle filter. Since a joint particle filter suffers from exponential complexity in the number of tracked targets, we replace the traditional importance sampling step in the particle filter with an MCMC sampling step. The resulting filter deals efficiently and effectively with complicated interactions when targets approach each other. We present both qualitative and quantitative results to substantiate the claims made in the paper, including a large scale experiment on a video-sequence of over 10,000 frames in length.
Keywords: Artificial Intelligence (incl. Robotics); Computer Graphics; Image Processing and Computer Vision; pattern recognition

Mining tool for surveillance video - Ghanem,N.M.; David Doermann; Davis, Larry S.; DeMenthon,D. (SPIE 16th International Symposium on Electronic Imaging, Storage and Retrieval Methods and Applications for Multimedia, 2004)
This paper describes a system for the mining of surveillance video. Our main contributions are: providing ahigh level query language for submitting queries about spatial and temporal relations of background regions and moving entities, and about human activities; providing a compiler to map high level queries into a set of novel Petri net filters that utilize computer vision algorithms to answer components of the queries; and providing a powerful graphical interface where users have the ability to formulate the query visually.

Mining Tools for Surveillance Video - Ghanem,N.; David Doermann; Davis, Larry S.; DeMenthon,D. (Proceedings in SPIE 16th International Symposium on Electronic Imaging, 2004)

Mixing ideas: a new technique for working with young children as design partners - Guha,M.L.; Druin, Allison; Chipman,G.; Fails,J. A; Simms,S.; Farber,A. (Proceedings of the 2004 conference on Interaction design and children: building a community, 2004)

Model-driven data acquisition in sensor networks - Deshpande, Amol; Guestrin,Carlos; Madden,Samuel R.; Hellerstein,Joseph M.; Wei Hong (Proceedings of the Thirtieth international conference on Very large data bases - Volume 30, 2004)
Declarative queries are proving to be an attractive paradigm for ineracting with networks of wireless sensors. The metaphor that "the sensornet is a database" is problematic, however, because sensors do not exhaustively represent the data in the real world. In order to map the raw sensor readings onto physical reality, a model of that reality is required to complement the readings. In this paper, we enrich interactive sensor querying with statistical modeling techniques. We demonstrate that such models can help provide answers that are both more meaningful, and, by introducing approximations with probabilistic confidences, significantly more efficient to compute in both time and energy. Utilizing the combination of a model and live data acquisition raises the challenging optimization problem of selecting the best sensor readings to acquire, balancing the increase in the confidence of our answer against the communication and data acquisition costs in the network. We describe an exponential time algorithm for finding the optimal solution to this optimization problem, and a polynomial-time heuristic for identifying solutions that perform well in practice. We evaluate our approach on several real-world sensor-network data sets, taking into account the real measured data and communication quality, demonstrating that our model-based approach provides a high-fidelity representation of the real phenomena and leads to significant performance gains versus traditional data acquisition techniques.

Multi-align: Combining Linguistic and Statistical Techniques to Improve Alignments for Adaptable MT - Ayan,Necip; Dorr, Bonnie J; Habash,Nizar (Machine Translation: From Real Users to ResearchMachine Translation: From Real Users to Research, 2004)
An adaptable statistical or hybrid MT system relies heavily on the quality of word-level alignments of real-world data. Statistical alignment approaches provide a reasonable initial estimate for word alignment. However, they cannot handle certain types of linguistic phenomena such as long-distance dependencies and structural differences between languages. We address this issue in Multi-Align, a new framework for incremental testing of different alignment algorithms and their combinations. Our design allows users to tune their systems to the properties of a particular genre/domain while still benefiting from general linguistic knowledge associated with a language pair. We demonstrate that a combination of statistical and linguistically-informed alignments can resolve translation divergences during the alignment process.

Multi-cue exemplar-based nonparametric model for gesture recognition - Shet,V. D; Prasad,V. S.N; Elgammal,A.; Yacoob,Yaser; Davis, Larry S. (Indian Conference on Computer Vision, Graphics and Image Processing, 2004)
This paper presents an approach for a multi-cue, view-based recognition of gestures. We describe an exemplar- based technique that combines two different forms of exem- plars - shape exemplars and motion exemplars - in a uni- fied probabilistic framework. Each gesture is represented as a sequence of learned body poses as well as a sequence of learned motion parameters. The shape exemplars are comprised of pose contours, and the motion exemplars are represented as affine motion parameters extracted using a robust estimation approach. The probabilistic framework learns by employing a nonparametric estimation technique to model the exemplar distributions. It imposes temporal constraints between different exemplars through a learned Hidden Markov Model (HMM) for each gesture. We use the proposed multi-cue approach to recognize a set of four- teen gestures and contrast it against a shape only, single- cue based system.

Multi-level fast multipole method for thin plate spline evaluation - Zandifar,A.; Lim,S.; Duraiswami, Ramani; Gumerov, Nail A.; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
Image registration is an important problem in image processing and computer vision. Much recent work in image registration is on matching non-rigid deformations. Thin plate splines are an effective image registration method when the deformation between two images can be modeled as the bending of a thin metal plate on point constraints such that the topology is preserved (non-rigid deformation). However, because evaluating the computed TPS model at all the image pixels is computationally expensive, we need to speed it up. We introduce the use of multi-level fast muitipole method (MLFMM) for this purpose. Our contribution lies in the presentation of a clear and concise MLFMM framework for TPS, which will be useful for future application developments. The achieved speedup using MLFMM is an improvement from O(N2) to O(N log N). We show that the fast evaluation outperforms the brute force method while maintaining acceptable error bound.
Keywords: (mathematics); Computer; deformation; evaluation; fast; image; MATCHING; matching; metal; method; multilevel; multipole; nonrigid; pixel; plate; plate; processing; registration; resolution; spline; splines; thin; vision

Multi-resolution modeling, visualization and streaming of volume meshes - Cignoni,P.; De Floriani, Leila; Lindstrom,P.; Pascucci,V.; Rossignac,J.; Silva,C. (Eurographics 2004, Tutorials 2: Multi-resolution Modeling, Visualization and Streaming of Volume Meshes, 2004)

A multi-resolution topological representation for non-manifold meshes - De Floriani, Leila; Magillo,Paola; Puppo,Enrico; Sobrero,Davide (Computer-Aided Design, 2004)
We address the problem of representing and processing 3D objects, described through simplicial meshes, which consist of parts of mixed dimensions, and with a non-manifold topology, at different levels of detail. First, we describe a multi-resolution model, that we call a non-manifold multi-tessellation (NMT), and we consider the selective refinement query, which is at the heart of several analysis operations on multi-resolution meshes. Next, we focus on a specific instance of a NMT, generated by simplifying simplicial meshes based on vertex-pair contraction, and we describe a compact data structure for encoding such a model. We also propose a new data structure for two-dimensional simplicial meshes, capable of representing both connectivity and adjacency information with a small memory overhead, which is used to describe the mesh extracted from an NMT through selective refinement. Finally, we present algorithms to efficiently perform updates on such a data structure.
Keywords: Data structures; Multi-resolution; Non-manifold modeling

New year’s resolutions for software quality - Basili, Victor R.; Boehm,B.; Davis,A.; Humphrey,W. S; Leveson,N.; Mead,N. R; Musa,J. D; Parnas,D. L; Pfleeger,S. L; Weyuker,E. (IEEE Software, 2004)
In the spirit of making resolutions for betterment in the New Year, ten distinguished individuals in the software quality field offer their recommendations on how organizations can improve software quality In the spirit of making resolutions for betterment in the New Year, ten distinguished individuals in the software quality field offer their recommendations on how organizations can improve software quality.

Np bracketing by maximum entropy tagging and SVM reranking - Daumé, Hal; Marcu,D. (Proceedings of EMNLP, 2004)

Oasys: An opinion analysis system - Cesarano,C.; Dorr, Bonnie J; Picariello, A.; Reforgiato,D.; Sagoff,A.; V.S. Subrahmanian (AAAI Spring symposium on Computational Approaches to Analyzing Weblogs, 2004)
There are numerous applications in which we would like toassess what opinions are being expressed in text documents. For 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.

Object tracking by adaptive feature extraction - Han,Bohyung; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
Tracking objects in the high-dimensional feature space is not only computationally expensive but also functionally inefficient. Selecting a low-dimensional discriminative feature set is a critical step to improve tracker performance. A good feature set for tracking can differ from frame to frame due to the changes in the background against the tracked object, and due to an on-line algorithm that adaptively determines a advantageous distinctive feature set. In this paper, multiple heterogeneous features are assembled, and likelihood images are constructed for various subspaces of the combined feature space. Then, the most discriminative feature is extracted by principal component analysis (PCA) based on those likelihood images. This idea is applied to the mean-shift tracking algorithm [D. Comaniciu et al., June 2000], and we demonstrate its effectiveness through various experiments.
Keywords: adaptive; algorithm; analysis; colour; component; extraction; feature; feature; heterogeneous; image; image; likelihood; Mean-shift; object; online; principal; tracking; tracking

On-Line Kernel-Based Tracking in Joint Feature-Spatial Spaces - Yang,C.; Duraiswami, Ramani; Elgammal,A.; Davis, Larry S. (IEEE, 0-7695-2158-2164, 2004)
We will demonstrate an object tracking algorithm thatuses a novel simple symmetric similarity function between spatially-smoothed kernel-density estimates of the model and target distributions. The similarity measure is based on the expectation of the density estimates over the model or target images. The density is estimated using radial-basis kernel functions which measure the affinity between points and provide a better outlier rejection property. The mean- shift algorithm is used to track objects by iteratively max- imizing this similarity function. To alleviate the quadratic complexity of the density estimation, we employ Gaussian kernels and the fast Gauss transform to reduce the compu- tations to linear order. This leads to a very efficient and robust nonparametric tracking algorithm. More details can be found in [2]. The system processes online video stream on a P4 1.4GHz and achieves 30 frames per second using an ordinary webcam.

A phrase-based hmm approach to document/abstract alignment - Daumé, Hal; Marcu,D. (Proceedings of EMNLP, 2004)

Preschool children's use of mouse buttons - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison (CHI'04 extended abstracts on Human factors in computing systems, 2004)

Product approximation by minimizing the upper bound of Bayes error rate for Bayesian combination of classifiers - Kang,Hee-Joong; David Doermann (Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on, 2004)
In combining multiple classifiers using a Bayesian formalism, a high dimensional probability distribution is composed of a class and decisions of classifiers. In order to do product approximation of the probability distribution, the upper bound of Bayes error rate, bounded by the conditional entropy of a class and decisions, should be minimized. A second-order dependency-based product approximation is proposed in this paper by considering the second-order dependency between the class and decisions. The proposed method is evaluated by combining the classifiers recognizing unconstrained handwritten numerals.
Keywords: approximation; Bayes; Bayesian; bound; character; classification; classifiers; conditional; distribution; entropy; error; formalism; handwritten; methods; minimisation; multiple; numerals; pattern; probability; probability; Product; rate; recognition; statistics; unconstrained; upper