@article {18558, title = {Countering Botnets: Anomaly-Based Detection, Comprehensive Analysis, and Efficient Mitigation}, year = {2011}, month = {2011/05//}, institution = {GEORGIA TECH RESEARCH CORP ATLANTA}, abstract = {We cover five general areas: (1) botnet detection, (2) botnet analysis, (3) botnet mitigation, (4) add-on tasks to the original contract, including the Conficker Working Group Lessons Learned, Layer-8 Exploration of Botnet Organization, and DREN research, and (5) commercialization in this paper. We have successfully developed new botnet detection and analysis capabilities in this project. These algorithms have been evaluated using real-world data, and have been put into actual, deployed systems. The most significant technical developments include a new dynamic reputation systems for DNS domains, a scalable anomaly detection system for botnet detection in very large network, and a transparent malware analysis system. In addition, on several occasions we have used our botnet data and analysis to help law enforcement agencies arrest botmasters. We also have had great success transitioning technologies to commercial products that are now used by government agencies, ISPs, and major corporations.}, keywords = {*ELECTRONIC SECURITY, *INFORMATION SECURITY, *INTERNET, *INTRUSION DETECTION(COMPUTERS), algorithms, BGP ROUTE INJECTION, BGP(BORDER GATEWAY PROTOCOLS), BOTNET DETECTION, BOTNET TRACEBACK AND ATTRIBUTION, BOTNETS(MALWARE), CLIENT SERVER SYSTEMS, COMMUNICATIONS PROTOCOLS, COMPUTER PROGRAMMING AND SOFTWARE, COMPUTER SYSTEMS MANAGEMENT AND STANDARDS, CYBER ATTACKS, CYBER SECURITY, CYBERNETICS, CYBERTERRORISM, CYBERWARFARE, DATA PROCESSING SECURITY, DNS BASED MONITORING, DNS BASED REDIRECTION, DNS(DOMAIN NAME SYSTEMS), INFORMATION SCIENCE, INTERNET BROWSERS, ISP(INTERNET SERVICE PROVIDERS), MALWARE, MALWARE ANALYSIS, Online Systems, WUAFRLDHS1BOTN}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA543919}, author = {Lee,Wenke and Dagon,David and Giffin,Jon and Feamster, Nick and Ollman,Gunter and Westby,Jody and Wesson,Rick and Vixie,Paul} } @article {12454, title = {A Fast Bilinear Structure from Motion Algorithm Using a Video Sequence and Inertial Sensors}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {33}, year = {2011}, month = {2011/01//}, pages = {186 - 193}, abstract = {In this paper, we study the benefits of the availability of a specific form of additional information-the vertical direction (gravity) and the height of the camera, both of which can be conveniently measured using inertial sensors and a monocular video sequence for 3D urban modeling. We show that in the presence of this information, the SfM equations can be rewritten in a bilinear form. This allows us to derive a fast, robust, and scalable SfM algorithm for large scale applications. The SfM algorithm developed in this paper is experimentally demonstrated to have favorable properties compared to the sparse bundle adjustment algorithm. We provide experimental evidence indicating that the proposed algorithm converges in many cases to solutions with lower error than state-of-art implementations of bundle adjustment. We also demonstrate that for the case of large reconstruction problems, the proposed algorithm takes lesser time to reach its solution compared to bundle adjustment. We also present SfM results using our algorithm on the Google StreetView research data set.}, keywords = {3D urban modeling, algorithms, Artificial intelligence, CAMERAS, computer vision., Convergence, fast bilinear structure, Google StreetView research data set, Image Interpretation, Computer-Assisted, Image reconstruction, Image sensors, Image sequences, Imaging, Three-Dimensional, inertial sensors, Information Storage and Retrieval, Linear systems, minimization, MOTION, motion algorithm, Motion estimation, multiple view geometry, Pattern Recognition, Automated, Sensors, SfM equations, sparse bundle adjustment algorithm, structure from motion, Three dimensional displays, vertical direction, Video Recording, video sequence, video signal processing}, isbn = {0162-8828}, doi = {10.1109/TPAMI.2010.163}, author = {Ramachandran, M. and Veeraraghavan,A. and Chellapa, Rama} } @article {19722, title = {ProPhylo: partial phylogenetic profiling to guide protein family construction and assignment of biological process.}, journal = {BMC Bioinformatics}, volume = {12}, year = {2011}, month = {2011}, pages = {434}, abstract = {

BACKGROUND: Phylogenetic profiling is a technique of scoring co-occurrence between a protein family and some other trait, usually another protein family, across a set of taxonomic groups. In spite of several refinements in recent years, the technique still invites significant improvement. To be its most effective, a phylogenetic profiling algorithm must be able to examine co-occurrences among protein families whose boundaries are uncertain within large homologous protein superfamilies.

RESULTS: Partial Phylogenetic Profiling (PPP) is an iterative algorithm that scores a given taxonomic profile against the taxonomic distribution of families for all proteins in a genome. The method works through optimizing the boundary of each protein family, rather than by relying on prebuilt protein families or fixed sequence similarity thresholds. Double Partial Phylogenetic Profiling (DPPP) is a related procedure that begins with a single sequence and searches for optimal granularities for its surrounding protein family in order to generate the best query profiles for PPP. We present ProPhylo, a high-performance software package for phylogenetic profiling studies through creating individually optimized protein family boundaries. ProPhylo provides precomputed databases for immediate use and tools for manipulating the taxonomic profiles used as queries.

CONCLUSION: ProPhylo results show universal markers of methanogenesis, a new DNA phosphorothioation-dependent restriction enzyme, and efficacy in guiding protein family construction. The software and the associated databases are freely available under the open source Perl Artistic License from ftp://ftp.jcvi.org/pub/data/ppp/.

}, keywords = {algorithms, Archaea, Archaeal Proteins, DNA, Methane, Phylogeny, software}, issn = {1471-2105}, doi = {10.1186/1471-2105-12-434}, author = {Basu, Malay K and Jeremy D Selengut and Haft, Daniel H} } @article {12474, title = {Applications of a Simple Characterization of Human Gait in Surveillance}, journal = {Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on}, volume = {40}, year = {2010}, month = {2010/08//}, pages = {1009 - 1020}, abstract = {Applications of a simple spatiotemporal characterization of human gait in the surveillance domain are presented. The approach is based on decomposing a video sequence into x-t slices, which generate periodic patterns referred to as double helical signatures (DHSs). The features of DHS are given as follows: 1) they naturally encode the appearance and kinematics of human motion and reveal geometric symmetries and 2) they are effective and efficient for recovering gait parameters and detecting simple events. We present an iterative local curve embedding algorithm to extract the DHS from video sequences. Two applications are then considered. First, the DHS is used for simultaneous segmentation and labeling of body parts in cluttered scenes. Experimental results showed that the algorithm is robust to size, viewing angles, camera motion, and severe occlusion. Then, the DHS is used to classify load-carrying conditions. By examining various symmetries in DHS, activities such as carrying, holding, and walking with objects that are attached to legs are detected. Our approach possesses several advantages: a compact representation that can be computed in real time is used; furthermore, it does not depend on silhouettes or landmark tracking, which are sensitive to errors in background subtraction stage.}, keywords = {algorithms, Artificial intelligence, Automated;Photography;Reproducibility of Results;Sensitivity and Specificity;Video Recording;, Biometry, Computer-Assisted;Pattern Recognition, double helical signatures, Gait, gait analysis, human gait, human motion kinematics, HUMANS, Image Enhancement, Image Interpretation, Image motion analysis, iterative local curve embedding algorithm, Object detection, simple spatiotemporal characterization, video sequence, Video surveillance}, isbn = {1083-4419}, doi = {10.1109/TSMCB.2010.2044173}, author = {Yang Ran and Qinfen Zheng and Chellapa, Rama and Strat, T.M.} } @article {12475, title = {Robust Height Estimation of Moving Objects From Uncalibrated Videos}, journal = {IEEE Transactions on Image Processing}, volume = {19}, year = {2010}, month = {2010/08//}, pages = {2221 - 2232}, abstract = {This paper presents an approach for video metrology. From videos acquired by an uncalibrated stationary camera, we first recover the vanishing line and the vertical point of the scene based upon tracking moving objects that primarily lie on a ground plane. Using geometric properties of moving objects, a probabilistic model is constructed for simultaneously grouping trajectories and estimating vanishing points. Then we apply a single view mensuration algorithm to each of the frames to obtain height measurements. We finally fuse the multiframe measurements using the least median of squares (LMedS) as a robust cost function and the Robbins-Monro stochastic approximation (RMSA) technique. This method enables less human supervision, more flexibility and improved robustness. From the uncertainty analysis, we conclude that the method with auto-calibration is robust in practice. Results are shown based upon realistic tracking data from a variety of scenes.}, keywords = {algorithms, Biometry, Calibration, EM algorithm, geometric properties, Geometry, Image Enhancement, Image Interpretation, Computer-Assisted, Imaging, Three-Dimensional, least median of squares, least squares approximations, MOTION, motion information, multiframe measurements, Pattern Recognition, Automated, Reproducibility of results, Robbins-Monro stochastic approximation, robust height estimation, Sensitivity and Specificity, Signal Processing, Computer-Assisted, stochastic approximation, Subtraction Technique, tracking data, uncalibrated stationary camera, uncalibrated videos, uncertainty analysis, vanishing point, video metrology, Video Recording, video signal processing}, isbn = {1057-7149}, doi = {10.1109/TIP.2010.2046368}, author = {Jie Shao and Zhou,S. K and Chellapa, Rama} } @article {19725, title = {Sites Inferred by Metabolic Background Assertion Labeling (SIMBAL): adapting the Partial Phylogenetic Profiling algorithm to scan sequences for signatures that predict protein function.}, journal = {BMC Bioinformatics}, volume = {11}, year = {2010}, month = {2010}, pages = {52}, abstract = {

BACKGROUND: Comparative genomics methods such as phylogenetic profiling can mine powerful inferences from inherently noisy biological data sets. We introduce Sites Inferred by Metabolic Background Assertion Labeling (SIMBAL), a method that applies the Partial Phylogenetic Profiling (PPP) approach locally within a protein sequence to discover short sequence signatures associated with functional sites. The approach is based on the basic scoring mechanism employed by PPP, namely the use of binomial distribution statistics to optimize sequence similarity cutoffs during searches of partitioned training sets.

RESULTS: Here we illustrate and validate the ability of the SIMBAL method to find functionally relevant short sequence signatures by application to two well-characterized protein families. In the first example, we partitioned a family of ABC permeases using a metabolic background property (urea utilization). Thus, the TRUE set for this family comprised members whose genome of origin encoded a urea utilization system. By moving a sliding window across the sequence of a permease, and searching each subsequence in turn against the full set of partitioned proteins, the method found which local sequence signatures best correlated with the urea utilization trait. Mapping of SIMBAL "hot spots" onto crystal structures of homologous permeases reveals that the significant sites are gating determinants on the cytosolic face rather than, say, docking sites for the substrate-binding protein on the extracellular face. In the second example, we partitioned a protein methyltransferase family using gene proximity as a criterion. In this case, the TRUE set comprised those methyltransferases encoded near the gene for the substrate RF-1. SIMBAL identifies sequence regions that map onto the substrate-binding interface while ignoring regions involved in the methyltransferase reaction mechanism in general. Neither method for training set construction requires any prior experimental characterization.

CONCLUSIONS: SIMBAL shows that, in functionally divergent protein families, selected short sequences often significantly outperform their full-length parent sequence for making functional predictions by sequence similarity, suggesting avenues for improved functional classifiers. When combined with structural data, SIMBAL affords the ability to localize and model functional sites.

}, keywords = {algorithms, Amino Acid Sequence, Gene Expression Profiling, Molecular Sequence Data, Phylogeny, Proteins, Sequence Analysis, Protein, Structure-Activity Relationship}, issn = {1471-2105}, doi = {10.1186/1471-2105-11-52}, author = {Jeremy D Selengut and Rusch, Douglas B and Haft, Daniel H} } @article {12470, title = {Sparsity-Inspired Recognition of Targets in Infrared Images}, year = {2010}, month = {2010/09/29/}, abstract = {Sparsity-based methods have recently been suggested for tasks such as face and iris recognition. In this project, we evaluated the effectiveness of such methods for automatic target recognition in infrared images. We show how sparsity can be helpful for efficient utilization of data for target recognition. We evaluated the effectiveness of the proposed algorithm in terms of recognition rate and confusion matrices on the well known Comanche forward-looking infrared (FLIR) data set consisting of ten different military targets at different orientations. This work was done in collaboration with Dr. Nasser Nasrabadi, Chief Scientist, SEDD, Army research laboratory. This work will be presented at the International Conference on Image Processing being held in Hong Kong in September 2010. A journal paper reporting our work is under preparation.}, keywords = {*FORWARD LOOKING INFRARED SYSTEMS, *IMAGE PROCESSING, *TARGET RECOGNITION, algorithms, ARMY RESEARCH, ATR(AUTOMATIC TARGET RECOGNITION), AUTOMATIC, CNN(CONVENTIONAL NEURAL NETWORKS), CS(COMPRESSIVE SENSING), DISCRIMINANT ANALYSIS, FLIR(FORWARD LOOKING INFRARED), INFRARED DETECTION AND DETECTORS, INFRARED IMAGES, LDA(LINEAR DISCRIMINANT ANALYSIS), MILITARY OPERATIONS, MNN(MODULAR NEURAL NETWORKS), neural nets, PCA(PRINCIPAL COMPONENT ANALYSIS), PE611102, SPARSITY, TARGET DIRECTION, RANGE AND POSITION FINDING}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA535424}, author = {Chellapa, Rama} } @conference {11902, title = {Approximate kernel matrix computation on GPUs forlarge scale learning applications}, booktitle = {Proceedings of the 23rd international conference on Supercomputing}, series = {ICS {\textquoteright}09}, year = {2009}, month = {2009///}, pages = {511 - 512}, publisher = {ACM}, organization = {ACM}, address = {Yorktown Heights, NY, USA}, abstract = {Kernel-based learning methods require quadratic space and time complexities to compute the kernel matrix. These complexities limit the applicability of kernel methods to large scale problems with millions of data points. In this paper, we introduce a novel representation of kernel matrices on Graphics Processing Units (GPU). The novel representation exploits the sparseness of the kernel matrix to address the space complexity problem. It also respects the guidelines for memory access on GPUs, which are critical for good performance, to address the time complexity problem. Our representation utilizes the locality preserving properties of space filling curves to obtain a band approximation of the kernel matrix. To prove the validity of the representation, we use Affinity Propagation, an unsupervised clustering algorithm, as an example of kernel methods. Experimental results show a 40x speedup of AP using our representation without degradation in clustering performance.}, keywords = {affinity propagation, algorithms, arrays, gpu, kernel methods, parallel programming, performance, space filling curves, sparse matrices}, isbn = {978-1-60558-498-0}, doi = {10.1145/1542275.1542355}, author = {Hussein,Mohamed E and Abd-Almageed, Wael} } @conference {11907, title = {Efficient band approximation of Gram matrices for large scale kernel methods on GPUs}, booktitle = {Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis}, series = {SC {\textquoteright}09}, year = {2009}, month = {2009///}, pages = {31:1{\textendash}31:10 - 31:1{\textendash}31:10}, publisher = {ACM}, organization = {ACM}, address = {Portland, Oregon}, abstract = {Kernel-based methods require O(N2) time and space complexities to compute and store non-sparse Gram matrices, which is prohibitively expensive for large scale problems. We introduce a novel method to approximate a Gram matrix with a band matrix. Our method relies on the locality preserving properties of space filling curves, and the special structure of Gram matrices. Our approach has several important merits. First, it computes only those elements of the Gram matrix that lie within the projected band. Second, it is simple to parallelize. Third, using the special band matrix structure makes it space efficient and GPU-friendly. We developed GPU implementations for the Affinity Propagation (AP) clustering algorithm using both our method and the COO sparse representation. Our band approximation is about 5 times more space efficient and faster to construct than COO. AP gains up to 6x speedup using our method without any degradation in its clustering performance.}, keywords = {affinity propagation, algorithms, gpu}, isbn = {978-1-60558-744-8}, doi = {10.1145/1654059.1654091}, author = {Hussein,Mohamed and Abd-Almageed, Wael} } @article {12513, title = {Multicamera Tracking of Articulated Human Motion Using Shape and Motion Cues}, journal = {Image Processing, IEEE Transactions on}, volume = {18}, year = {2009}, month = {2009/09//}, pages = {2114 - 2126}, abstract = {We present a completely automatic algorithm for initializing and tracking the articulated motion of humans using image sequences obtained from multiple cameras. A detailed articulated human body model composed of sixteen rigid segments that allows both translation and rotation at joints is used. Voxel data of the subject obtained from the images is segmented into the different articulated chains using Laplacian eigenmaps. The segmented chains are registered in a subset of the frames using a single-frame registration technique and subsequently used to initialize the pose in the sequence. A temporal registration method is proposed to identify the partially segmented or unregistered articulated chains in the remaining frames in the sequence. The proposed tracker uses motion cues such as pixel displacement as well as 2-D and 3-D shape cues such as silhouettes, motion residue, and skeleton curves. The tracking algorithm consists of a predictor that uses motion cues and a corrector that uses shape cues. The use of complementary cues in the tracking alleviates the twin problems of drift and convergence to local minima. The use of multiple cameras also allows us to deal with the problems due to self-occlusion and kinematic singularity. We present tracking results on sequences with different kinds of motion to illustrate the effectiveness of our approach. The pose of the subject is correctly tracked for the duration of the sequence as can be verified by inspection.}, keywords = {2D shape cues, 3D shape cues, algorithms, Anatomic;Models, articulated human motion, automatic algorithm, Biological;Movement;Posture;Skeleton;Video Recording;, Computer-Assisted;Models, Eigenvalues and eigenfunctions, human pose estimation, HUMANS, Image motion analysis, IMAGE PROCESSING, image registration, Image segmentation, Image sequences, kinematic singularity, Laplacian eigenmaps, multicamera tracking algorithm, pixel displacement, pose estimation, single-frame registration technique, temporal registration method, tracking}, isbn = {1057-7149}, doi = {10.1109/TIP.2009.2022290}, author = {Sundaresan, A. and Chellapa, Rama} } @article {17250, title = {Interactive Entity Resolution in Relational Data: A Visual Analytic Tool and Its Evaluation}, journal = {IEEE Transactions on Visualization and Computer Graphics}, volume = {14}, year = {2008}, month = {2008/10//Sept}, pages = {999 - 1014}, abstract = {Databases often contain uncertain and imprecise references to real-world entities. Entity resolution, the process of reconciling multiple references to underlying real-world entities, is an important data cleaning process required before accurate visualization or analysis of the data is possible. In many cases, in addition to noisy data describing entities, there is data describing the relationships among the entities. This relational data is important during the entity resolution process; it is useful both for the algorithms which determine likely database references to be resolved and for visual analytic tools which support the entity resolution process. In this paper, we introduce a novel user interface, D-Dupe, for interactive entity resolution in relational data. D-Dupe effectively combines relational entity resolution algorithms with a novel network visualization that enables users to make use of an entity{\textquoteright}s relational context for making resolution decisions. Since resolution decisions often are interdependent, D-Dupe facilitates understanding this complex process through animations which highlight combined inferences and a history mechanism which allows users to inspect chains of resolution decisions. An empirical study with 12 users confirmed the benefits of the relational context visualization on the performance of entity resolution tasks in relational data in terms of time as well as users{\textquoteright} confidence and satisfaction.}, keywords = {algorithms, Computer Graphics, D-Dupe, data visualisation, database management systems, Databases, Factual, graphical user interface, Graphical user interfaces, human-centered computing, Image Interpretation, Computer-Assisted, Information Storage and Retrieval, Information Visualization, interactive entity resolution, relational context visualization, Relational databases, relational entity resolution algorithm, User interfaces, user-centered design, User-Computer Interface, visual analytic tool}, isbn = {1077-2626}, doi = {10.1109/TVCG.2008.55}, author = {Kang,Hyunmo and Getoor, Lise and Shneiderman, Ben and Bilgic,M. and Licamele,L.} } @article {12544, title = {Model Driven Segmentation of Articulating Humans in Laplacian Eigenspace}, journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on}, volume = {30}, year = {2008}, month = {2008/10//}, pages = {1771 - 1785}, abstract = {We propose a general approach using Laplacian Eigenmaps and a graphical model of the human body to segment 3D voxel data of humans into different articulated chains. In the bottom-up stage, the voxels are transformed into a high-dimensional (6D or less) Laplacian Eigenspace (LE) of the voxel neighborhood graph. We show that LE is effective at mapping voxels on long articulated chains to nodes on smooth 1D curves that can be easily discriminated, and prove these properties using representative graphs. We fit 1D splines to voxels belonging to different articulated chains such as the limbs, head and trunk, and determine the boundary between splines using the spline fitting error. A top-down probabilistic approach is then used to register the segmented chains, utilizing their mutual connectivity and individual properties. Our approach enables us to deal with complex poses such as those where the limbs form loops. We use the segmentation results to automatically estimate the human body models. While we use human subjects in our experiments, the method is fairly general and can be applied to voxel-based segmentation of any articulated object composed of long chains. We present results on real and synthetic data that illustrate the usefulness of this approach.}, keywords = {3D voxel data segmentation, algorithms, Anatomic;Pattern Recognition, Artificial intelligence, Automated;Reproducibility of Results;Sensitivity and Specificity;Whole Body Imaging;, Computer simulation, Computer-Assisted;Imaging, curve fitting, Eigenvalues and eigenfunctions, graph theory, human articulation, human body graphical model, human motion analysis, HUMANS, Image Enhancement, Image Interpretation, Image motion analysis, image registration, Image segmentation, Laplace transforms, Laplacian eigenspace transform, model driven segmentation, probability, representative graph, skeleton registration, Smoothing methods, solid modelling, spline fitting error, splines (mathematics), Three-Dimensional;Joints;Models, top-down probabilistic approach, voxel neighborhood graph}, isbn = {0162-8828}, doi = {10.1109/TPAMI.2007.70823}, author = {Sundaresan, A. and Chellapa, Rama} } @inbook {19606, title = {On the Cost of Persistence and Authentication in Skip Lists}, booktitle = {Experimental Algorithms}, series = {Lecture Notes in Computer Science}, year = {2007}, month = {2007/01/01/}, pages = {94 - 107}, publisher = {Springer Berlin Heidelberg}, organization = {Springer Berlin Heidelberg}, abstract = {We present an extensive experimental study of authenticated data structures for dictionaries and maps implemented with skip lists. We consider realizations of these data structures that allow us to study the performance overhead of authentication and persistence. We explore various design decisions and analyze the impact of garbage collection and virtual memory paging, as well. Our empirical study confirms the efficiency of authenticated skip lists and offers guidelines for incorporating them in various applications.}, keywords = {Algorithm Analysis and Problem Complexity, algorithms, Computer Graphics, Data structures, Discrete Mathematics in Computer Science, Numeric Computing}, isbn = {978-3-540-72844-3, 978-3-540-72845-0}, url = {http://link.springer.com/chapter/10.1007/978-3-540-72845-0_8}, author = {Goodrich, Michael T. and Charalampos Papamanthou and Tamassia, Roberto}, editor = {Demetrescu, Camil} } @article {14182, title = {A 3D shape constraint on video}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {28}, year = {2006}, month = {2006/06//}, pages = {1018 - 1023}, abstract = {We propose to combine the information from multiple motion fields by enforcing a constraint on the surface normals (3D shape) of the scene in view. The fact that the shape vectors in the different views are related only by rotation can be formulated as a rank = 3 constraint. This constraint is implemented in an algorithm which solves 3D motion and structure estimation as a practical constrained minimization. Experiments demonstrate its usefulness as a tool in structure from motion providing very accurate estimates of 3D motion.}, keywords = {3D motion estimation, algorithms, Artificial intelligence, CAMERAS, decoupling translation from rotation, Estimation error, Fluid flow measurement, Image Enhancement, Image Interpretation, Computer-Assisted, Image reconstruction, Imaging, Three-Dimensional, Information Storage and Retrieval, integration of motion fields, Layout, minimisation, Minimization methods, Motion estimation, multiple motion fields, parameter estimation, Pattern Recognition, Automated, Photography, practical constrained minimization, SHAPE, shape and rotation., shape vectors, stability, structure estimation, surface normals, Three-dimensional motion estimation, video 3D shape constraint, Video Recording, video signal processing}, isbn = {0162-8828}, doi = {10.1109/TPAMI.2006.109}, author = {Hui Ji and Ferm{\"u}ller, Cornelia} } @article {16983, title = {Balancing Systematic and Flexible Exploration of Social Networks}, journal = {IEEE Transactions on Visualization and Computer Graphics}, volume = {12}, year = {2006}, month = {2006/10//Sept}, pages = {693 - 700}, abstract = {Social network analysis (SNA) has emerged as a powerful method for understanding the importance of relationships in networks. However, interactive exploration of networks is currently challenging because: (1) it is difficult to find patterns and comprehend the structure of networks with many nodes and links, and (2) current systems are often a medley of statistical methods and overwhelming visual output which leaves many analysts uncertain about how to explore in an orderly manner. This results in exploration that is largely opportunistic. Our contributions are techniques to help structural analysts understand social networks more effectively. We present SocialAction, a system that uses attribute ranking and coordinated views to help users systematically examine numerous SNA measures. Users can (1) flexibly iterate through visualizations of measures to gain an overview, filter nodes, and find outliers, (2) aggregate networks using link structure, find cohesive subgroups, and focus on communities of interest, and (3) untangle networks by viewing different link types separately, or find patterns across different link types using a matrix overview. For each operation, a stable node layout is maintained in the network visualization so users can make comparisons. SocialAction offers analysts a strategy beyond opportunism, as it provides systematic, yet flexible, techniques for exploring social networks}, keywords = {Aggregates, algorithms, attribute ranking, Cluster Analysis, Computer Graphics, Computer simulation, Coordinate measuring machines, coordinated views, Data analysis, data visualisation, Data visualization, exploratory data analysis, Filters, Gain measurement, graph theory, Graphical user interfaces, Information Storage and Retrieval, interactive graph visualization, matrix algebra, matrix overview, Models, Biological, Navigation, network visualization, Pattern analysis, Population Dynamics, Social Behavior, social network analysis, Social network services, social networks, social sciences computing, Social Support, SocialAction, software, statistical analysis, statistical methods, User-Computer Interface}, isbn = {1077-2626}, doi = {10.1109/TVCG.2006.122}, author = {Perer,A. and Shneiderman, Ben} } @article {19662, title = {MCMC Data Association and Sparse Factorization Updating for Real Time Multitarget Tracking with Merged and Multiple Measurements}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {28}, year = {2006}, month = {2006/12//}, pages = {1960 - 1972}, abstract = {In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC}, keywords = {algorithms, approximate inference, Artificial intelligence, auxiliary variable particle filter, Computational efficiency, continuous state space, downdating, Image Enhancement, Image Interpretation, Computer-Assisted, Inference algorithms, Information Storage and Retrieval, laser range scanner, laser range scanner., Least squares approximation, least squares approximations, Least squares methods, linear least squares, Markov chain Monte Carlo, Markov processes, MCMC data association, merged measurements, Monte Carlo methods, Movement, multiple merged measurements, multitarget tracking, particle filter, particle filtering (numerical methods), Particle filters, Pattern Recognition, Automated, probabilistic model, QR factorization, Radar tracking, Rao-Blackwellized, real time multitarget tracking, Reproducibility of results, Sampling methods, Sensitivity and Specificity, sensor fusion, sparse factorization updating, sparse least squares, State-space methods, Subtraction Technique, target tracking, updating}, isbn = {0162-8828}, author = {Zia Khan and Balch, T. and Dellaert, F.} } @article {12607, title = {Physics-Based Detectors Applied to Long-Wave Infrared Hyperspectral Data}, year = {2006}, month = {2006/11//}, institution = {CENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK}, abstract = {Long-wave infrared (LWIR) hyperspectral image (HSI) data presents an interesting challenge for automatic target detection algorithms. LWIR HSI data is useful for both day and night operations, but weak signatures like disturbed soil can be problematic for standard matched-filter techniques. In this paper, we augment the standard matched-filter techniques with physics-based information particular to HSI data. Our results show that these physics-based detectors provide improved detection performance with quick processing times.}, keywords = {*HYPERSPECTRAL IMAGERY, algorithms, AUTOMATIC, DETECTION, FAR INFRARED RADIATION, LOW STRENGTH, Matched filters, MILITARY OPERATIONS, NIGHT, OPTICS, SIGNATURES, SOILS, SPECTROMETERS, TARGET DETECTION}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA481339}, author = {Broadwater,Joshua and Chellapa, Rama} } @article {12618, title = {Robust ego-motion estimation and 3-D model refinement using surface parallax}, journal = {Image Processing, IEEE Transactions on}, volume = {15}, year = {2006}, month = {2006/05//}, pages = {1215 - 1225}, abstract = {We present an iterative algorithm for robustly estimating the ego-motion and refining and updating a coarse depth map using parametric surface parallax models and brightness derivatives extracted from an image pair. Given a coarse depth map acquired by a range-finder or extracted from a digital elevation map (DEM), ego-motion is estimated by combining a global ego-motion constraint and a local brightness constancy constraint. Using the estimated camera motion and the available depth estimate, motion of the three-dimensional (3-D) points is compensated. We utilize the fact that the resulting surface parallax field is an epipolar field, and knowing its direction from the previous motion estimates, estimate its magnitude and use it to refine the depth map estimate. The parallax magnitude is estimated using a constant parallax model (CPM) which assumes a smooth parallax field and a depth based parallax model (DBPM), which models the parallax magnitude using the given depth map. We obtain confidence measures for determining the accuracy of the estimated depth values which are used to remove regions with potentially incorrect depth estimates for robustly estimating ego-motion in subsequent iterations. Experimental results using both synthetic and real data (both indoor and outdoor sequences) illustrate the effectiveness of the proposed algorithm.}, keywords = {3D model refinement, algorithms, Artificial intelligence, Automated;Subtraction Technique;, Computer-Assisted;Imaging, constant parallax model, depth based parallax model, digital elevation map, epipolar field, Image Enhancement, Image Interpretation, iterative algorithm, iterative methods, Motion estimation, robust ego-motion estimation, smooth parallax field, surface parallax, Three-Dimensional;Information Storage and Retrieval;Pattern Recognition}, isbn = {1057-7149}, doi = {10.1109/TIP.2005.864167}, author = {Agrawal,A. and Chellapa, Rama} } @conference {11979, title = {A sensory grammar for inferring behaviors in sensor networks}, booktitle = {Proceedings of the 5th international conference on Information processing in sensor networks}, series = {IPSN {\textquoteright}06}, year = {2006}, month = {2006///}, pages = {251 - 259}, publisher = {ACM}, organization = {ACM}, address = {Nashville, Tennessee, USA}, abstract = {The ability of a sensor network to parse out observable activities into a set of distinguishable actions is a powerful feature that can potentially enable many applications of sensor networks to everyday life situations. In this paper we introduce a framework that uses a hierarchy of Probabilistic Context Free Grammars (PCFGs) to perform such parsing. The power of the framework comes from the hierarchical organization of grammars that allows the use of simple local sensor measurements for reasoning about more macroscopic behaviors. Our presentation describes how to use a set of phonemes to construct grammars and how to achieve distributed operation using a messaging model. The proposed framework is flexible. It can be mapped to a network hierarchy or can be applied sequentially and across the network to infer behaviors as they unfold in space and time. We demonstrate this functionality by inferring simple motion patterns using a sequence of simple direction vectors obtained from our camera sensor network testbed.}, keywords = {algorithms, behavior identification, human activity, human factors, pcfg, real-time and embedded systems, sensor grammars, sensor networks}, isbn = {1-59593-334-4}, doi = {10.1145/1127777.1127817}, author = {Lymberopoulos, Dimitrios and Ogale, Abhijit S. and Savvides, Andreas and Aloimonos, J.} } @article {19663, title = {MCMC-based particle filtering for tracking a variable number of interacting targets}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {27}, year = {2005}, month = {2005/11//}, pages = {1805 - 1819}, abstract = {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}, isbn = {0162-8828}, author = {Zia Khan and Balch, T. and Dellaert, F.} } @article {14230, title = {Motion segmentation using occlusions}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, volume = {27}, year = {2005}, month = {2005/06//}, pages = {988 - 992}, abstract = {We examine the key role of occlusions in finding independently moving objects instantaneously in a video obtained by a moving camera with a restricted field of view. In this problem, the image motion is caused by the combined effect of camera motion (egomotion), structure (depth), and the independent motion of scene entities. For a camera with a restricted field of view undergoing a small motion between frames, there exists, in general, a set of 3D camera motions compatible with the observed flow field even if only a small amount of noise is present, leading to ambiguous 3D motion estimates. If separable sets of solutions exist, motion-based clustering can detect one category of moving objects. Even if a single inseparable set of solutions is found, we show that occlusion information can be used to find ordinal depth, which is critical in identifying a new class of moving objects. In order to find ordinal depth, occlusions must not only be known, but they must also be filled (grouped) with optical flow from neighboring regions. We present a novel algorithm for filling occlusions and deducing ordinal depth under general circumstances. Finally, we describe another category of moving objects which is detected using cardinal comparisons between structure from motion and structure estimates from another source (e.g., stereo).}, keywords = {3D motion estimation, algorithms, Artificial intelligence, CAMERAS, Computer vision, Filling, hidden feature removal, Image Enhancement, Image Interpretation, Computer-Assisted, image motion, Image motion analysis, Image segmentation, Layout, MOTION, Motion detection, Motion estimation, motion segmentation, Movement, Object detection, occlusion, occlusions, optical flow, ordinal depth, Pattern Recognition, Automated, Photography, Reproducibility of results, segmentation, Semiconductor device modeling, Sensitivity and Specificity, video analysis., Video Recording}, isbn = {0162-8828}, doi = {10.1109/TPAMI.2005.123}, author = {Ogale, A. S and Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @article {14932, title = {A new framework for addressing temporal range queries and some preliminary results}, journal = {Theoretical Computer Science}, volume = {332}, year = {2005}, month = {2005/02/28/}, pages = {109 - 121}, abstract = {Given a set of n objects, each characterized by d attributes specified at m fixed time instances, we are interested in the problem of designing space efficient indexing structures such that a class of temporal range search queries can be handled efficiently. When m = 1 , our problem reduces to the d-dimensional orthogonal search problem. We establish efficient data structures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of O ( log n log m + f ) for one-sided queries when d = 1 , where f is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can be solved with a polylogarithmic query time using superlinear space data structures.}, keywords = {algorithms, Data structures, Orthogonal range search, temporal data}, isbn = {0304-3975}, doi = {10.1016/j.tcs.2004.10.013}, url = {http://www.sciencedirect.com/science/article/pii/S0304397504007005}, author = {Shi,Qingmin and JaJa, Joseph F.} } @article {15001, title = {Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines}, journal = {Information Processing Letters}, volume = {95}, year = {2005}, month = {2005/08/16/}, pages = {382 - 388}, abstract = {We develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms.}, keywords = {algorithms, computational geometry, Generalized intersection}, isbn = {0020-0190}, doi = {10.1016/j.ipl.2005.04.008}, url = {http://www.sciencedirect.com/science/article/pii/S0020019005001183}, author = {Shi,Qingmin and JaJa, Joseph F.} } @conference {14814, title = {Parallel Parameter Tuning for Applications with Performance Variability}, booktitle = {Proceedings of the 2005 ACM/IEEE conference on Supercomputing}, series = {SC {\textquoteright}05}, year = {2005}, month = {2005///}, pages = {57{\textendash} - 57{\textendash}}, publisher = {IEEE Computer Society}, organization = {IEEE Computer Society}, abstract = {In this paper, we present parallel on-line optimization algorithms for parameter tuning of parallel programs. We employ direct search algorithms that update parameters based on real-time performance measurements. We discuss the impact of performance variability on the accuracy and efficiency of the optimization algorithms and proposed modified versions of the direct search algorithms to cope with it. The modified version uses multiple samples instead of single sample to estimate the performance more accurately.We present preliminary results that the performance variability of applications on clusters is heavy tailed. Finally, we studay and demonstrate the performance ofthe proposed algorithms for real scientific application.}, keywords = {algorithms, compilers, design}, isbn = {1-59593-061-2}, doi = {http://dx.doi.org/10.1109/SC.2005.52}, url = {http://dx.doi.org/10.1109/SC.2005.52}, author = {Tabatabaee, Vahid and Tiwari, Ananta and Hollingsworth, Jeffrey K} } @article {12654, title = {Statistical bias in 3-D reconstruction from a monocular video}, journal = {Image Processing, IEEE Transactions on}, volume = {14}, year = {2005}, month = {2005/08//}, pages = {1057 - 1062}, abstract = {The present state-of-the-art in computing the error statistics in three-dimensional (3-D) reconstruction from video concentrates on estimating the error covariance. A different source of error which has not received much attention is the fact that the reconstruction estimates are often significantly statistically biased. In this paper, we derive a precise expression for the bias in the depth estimate, based on the continuous (differentiable) version of structure from motion (SfM). Many SfM algorithms, or certain portions of them, can be posed in a linear least-squares (LS) framework Ax=b. Examples include initialization procedures for bundle adjustment or algorithms that alternately estimate depth and camera motion. It is a well-known fact that the LS estimate is biased if the system matrix A is noisy. In SfM, the matrix A contains point correspondences, which are always difficult to obtain precisely; thus, it is expected that the structure and motion estimates in such a formulation of the problem would be biased. Existing results on the minimum achievable variance of the SfM estimator are extended by deriving a generalized Cramer-Rao lower bound. A detailed analysis of the effect of various camera motion parameters on the bias is presented. We conclude by presenting the effect of bias compensation on reconstructing 3-D face models from rendered images.}, keywords = {3D face models, 3D video reconstruction, algorithms, artifacts, Artificial intelligence, Automated;Signal Processing, bias compensation, bundle adjustment, camera motion estimation, Computer simulation, Computer-Assisted;Imaging, Computer-Assisted;Subtraction Technique;Video Recording;, depth estimate, error covariance estimation, error statistics, generalized Cramer-Rao lower bound, Image Enhancement, Image Interpretation, Image reconstruction, initialization procedures, least squares approximations, linear least-squares framework, monocular video, motion compensation, Motion estimation, statistical bias, Statistical;Pattern Recognition, structure from motion algorithms, Three-Dimensional;Information Storage and Retrieval;Models, video signal processing}, isbn = {1057-7149}, doi = {10.1109/TIP.2005.849775}, author = {Roy-Chowdhury, A.K. and Chellapa, Rama} } @article {12698, title = {An information theoretic criterion for evaluating the quality of 3-D reconstructions from video}, journal = {Image Processing, IEEE Transactions on}, volume = {13}, year = {2004}, month = {2004/07//}, pages = {960 - 973}, abstract = {Even though numerous algorithms exist for estimating the three-dimensional (3-D) structure of a scene from its video, the solutions obtained are often of unacceptable quality. To overcome some of the deficiencies, many application systems rely on processing more data than necessary, thus raising the question: how is the accuracy of the solution related to the amount of data processed by the algorithm? Can we automatically recognize situations where the quality of the data is so bad that even a large number of additional observations will not yield the desired solution? Previous efforts to answer this question have used statistical measures like second order moments. They are useful if the estimate of the structure is unbiased and the higher order statistical effects are negligible, which is often not the case. This paper introduces an alternative information-theoretic criterion for evaluating the quality of a 3-D reconstruction. The accuracy of the reconstruction is judged by considering the change in mutual information (MI) (termed as the incremental MI) between a scene and its reconstructions. An example of 3-D reconstruction from a video sequence using optical flow equations and known noise distribution is considered and it is shown how the MI can be computed from first principles. We present simulations on both synthetic and real data to demonstrate the effectiveness of the proposed criterion.}, keywords = {3D reconstruction, algorithms, Artificial intelligence, Automated;Reproducibility of Results;Sensitivity and Specificity;Signal Processing, Computer Graphics, Computer-Assisted;Imaging, Computer-Assisted;Software Validation;Subtraction Technique;Video Recording;, Image Enhancement, Image Interpretation, Image reconstruction, Image sequences, information theoretic criterion, Mutual information, NOISE, noise distribution, optical flow equations, second order moments, statistical analysis, Three-Dimensional;Information Storage and Retrieval;Information Theory;Movement;Pattern Recognition, Video sequences, video signal processing}, isbn = {1057-7149}, doi = {10.1109/TIP.2004.827240}, author = {Roy-Chowdhury, A.K. and Chellapa, Rama} } @article {12680, title = {Video-Based Automatic Target Recognition}, year = {2004}, month = {2004/12//}, institution = {MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH}, abstract = {We present an approach for vehicle classification in IR video sequences by integrating detection, tracking and recognition. The method has two steps. First, the moving target is automatically detected using a detection algorithm. Next, we perform simultaneous tracking and recognition using an appearance-model based particle filter. The tracking result is evaluated at each frame. Low confidence in tracking performance initiates a new cycle of detection, tracking and classification. We demonstrate the robustness of the proposed method using outdoor IR video sequences.}, keywords = {*SEQUENCES(MATHEMATICS), *TARGET RECOGNITION, *VEHICLES, *VIDEO RECORDING, algorithms, AUTOMATIC TRACKING., COMPONENT REPORTS, MOVING TARGETS, SURFACE TRANSPORTATION AND EQUIPMENT, SYMPOSIA, TARGET CLASSIFICATION, TARGET DIRECTION, RANGE AND POSITION FINDING, tracking, VIDEO SIGNALS}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA431617}, author = {Zhou,S. K and Chellapa, Rama and Mei,Xue and Wu,Hao and Qinfen Zheng} } @article {12682, title = {Visual tracking and recognition using appearance-adaptive models in particle filters}, journal = {IEEE Transactions on Image Processing}, volume = {13}, year = {2004}, month = {2004/11//}, pages = {1491 - 1506}, abstract = {We present an approach that incorporates appearance-adaptive models in a particle filter to realize robust visual tracking and recognition algorithms. Tracking needs modeling interframe motion and appearance changes, whereas recognition needs modeling appearance changes between frames and gallery images. In conventional tracking algorithms, the appearance model is either fixed or rapidly changing, and the motion model is simply a random walk with fixed noise variance. Also, the number of particles is typically fixed. All these factors make the visual tracker unstable. To stabilize the tracker, we propose the following modifications: an observation model arising from an adaptive appearance model, an adaptive velocity motion model with adaptive noise variance, and an adaptive number of particles. The adaptive-velocity model is derived using a first-order linear predictor based on the appearance difference between the incoming observation and the previous particle configuration. Occlusion analysis is implemented using robust statistics. Experimental results on tracking visual objects in long outdoor and indoor video sequences demonstrate the effectiveness and robustness of our tracking algorithm. We then perform simultaneous tracking and recognition by embedding them in a particle filter. For recognition purposes, we model the appearance changes between frames and gallery images by constructing the intra- and extrapersonal spaces. Accurate recognition is achieved when confronted by pose and view variations.}, keywords = {adaptive filters, adaptive noise variance, algorithms, appearance-adaptive model, Artificial intelligence, Cluster Analysis, Computer Graphics, Computer simulation, Feedback, Filtering, first-order linear predictor, hidden feature removal, HUMANS, Image Enhancement, Image Interpretation, Computer-Assisted, image recognition, Information Storage and Retrieval, Kinematics, Laboratories, Male, Models, Biological, Models, Statistical, MOTION, Movement, Noise robustness, Numerical Analysis, Computer-Assisted, occlusion analysis, Particle filters, Particle tracking, Pattern Recognition, Automated, Predictive models, Reproducibility of results, robust statistics, Sensitivity and Specificity, Signal Processing, Computer-Assisted, State estimation, statistical analysis, Subtraction Technique, tracking, Training data, visual recognition, visual tracking}, isbn = {1057-7149}, doi = {10.1109/TIP.2004.836152}, author = {Zhou,Shaohua Kevin and Chellapa, Rama and Moghaddam, B.} } @article {15594, title = {A Fast Implementation of the ISOCLUS Algorithm}, journal = {IEEE 2003 International Geoscience and Remote Sensing Symposium}, year = {2003}, month = {2003///}, abstract = {Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in d-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called k-means. One significant feature of ISOCLUS over k-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge lor split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing .interest in the remote sensing community in computing it efficiently. We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm of Kanungo, et al. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for k-means. Both the k-means and ISOCLUS algorithms are based on iterative schemes, in which nearest neighbors are calculated until some convergence criterion is satisfied. Each iteration requires that the nearest center for each data point be computed. Naively, this requires O(kn) time, where k denotes the current number of centers. Traditional techniques for accelerating nearest neighbor searching involve storing the k centers in a data structure. However, because of the iterative nature of the algorithm, this data structure would need to be rebuilt with each new iteration. Our approach is to store the data points in a kd-tree data structure. The assignment of points to nearest neighbors is carried out by a filtering process, which successively eliminates centers that can not possibly be the nearest neighbor for a given region of space. This algorithm is significantly faster, because large groups of data points can be assigned to their nearest center in a single operation. Preliminary results on a number of real Landsat datasets show that our revised ISOCLUS-like scheme runs about twice as fast.}, keywords = {algorithms, Cluster Analysis, Data structures, HEURISTIC METHODS, IMAGE PROCESSING, INTEGERS, LANDSAT SATELLITES, MEAN SQUARE VALUES, Remote sensing}, url = {http://ntrs.nasa.gov/search.jsp?R=20030053175}, author = {Memarsadeghi,Nargess and Mount, Dave and Netanyahu,Nathan S. and LeMoigne,Jacqueline} } @conference {14772, title = {Recompilation for debugging support in a JIT-compiler}, booktitle = {Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering}, series = {PASTE {\textquoteright}02}, year = {2002}, month = {2002///}, pages = {10 - 17}, publisher = {ACM}, organization = {ACM}, address = {Charleston, South Carolina, USA}, abstract = {A static Java compiler converts Java source code into a verifiably secure and compact architecture-neutral intermediate format, called Java byte codes. The Java byte codes can be either interpreted by a Java Virtual Machine or translated into native code by Java Just-In-Time compilers. Static Java compilers embed debug information in the Java class files to be used by the source level debuggers. However, the debug information is generated for architecture independent byte codes and most of the debug information is valid only when the byte codes are interpreted. Translating byte codes into native instructions puts a limitation on the amount of usable debug information that can be used by source level debuggers. In this paper, we present a new technique to generate valid debug information when Just-In-Time compilers are used. Our approach is based on the dynamic recompilation of Java methods by a fast code generator and lazily generates debug information when it is required. We also present three implementations for field watch support in the Java Virtual Machine Debugger Interface to investigate the runtime overhead and code size growth by our approach.}, keywords = {algorithms, debug information, debugging aids, dynamic recompilation, field access watch, java, java virtual machine debugger interface, just-in-time compilation, measurement, performance}, isbn = {1-58113-479-7}, doi = {10.1145/586094.586100}, author = {Tikir, Mustafa M. and Hollingsworth, Jeffrey K and Lueh,Guei-Yuan} } @article {16720, title = {Word-level Alignment for Multilingual Resource Acquisition}, year = {2002}, month = {2002/04//}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {We present a simple, one-pass word alignment algorithm for parallel text. Our algorithm utilizes synchronous parsing and takes advantage of existing syntactic annotations. In our experiments the performance of this model is comparable to more complicated iterative methods. We discuss the challenges and potential benefits of using the model to train syntactic parsers for new languages.}, keywords = {*LEARNING MACHINES, *MULTILINGUAL RESOURCES, *WORDS(LANGUAGE), ACQUISITION, algorithms, ALIGNMENT, BENEFITS, ITERATIONS, LANGUAGE, linguistics}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA458782}, author = {Lopez,Adam and Nossal,Michael and Hwa,Rebecca and Resnik, Philip} } @article {13761, title = {Efficient Language Independent Generation from Lexical Conceptual Structure}, year = {2001}, month = {2001/09//}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {This paper describes a system for generating natural-language sentences from an interlingual representation, Lexical Conceptual Structure (LCS). The system has been developed as part of a Chinese-English Machine Translation system; however, it is designed to be used for many other MT language pairs and Natural Language applications. The contributions of this work include: (1) Development of a language-independent generation system that maximizes efficiency through the use of a hybrid rule-based/statistical module; (2) Enhancements to an interlingual representation and associated algorithms for interpretation of multiply ambiguous input sentences; (3) Development of an efficient reusable language-independent linearization module with a grammar description language that can be used with other systems; (4) Improvements to an earlier algorithm for hierarchically mapping thematic roles to surface positions; (5) Development of a diagnostic tool for lexicon coverage and correctness and use of the tool for verification of English, Spanish, and Chinese lexicons. An evaluation of translation quality shows comparable performance with commercial translation system. The generation system can also be straightforwardly extended to their languages and this is demonstrated and evaluated for Spanish.}, keywords = {*LEXICAL CONCEPTUAL STRUCTURE, *LEXICOGRAPHY, *MACHINE TRANSLATION, *VOCABULARY, *WORDS(LANGUAGE), algorithms, CHINA, COMMERCE, DIAGNOSTIC EQUIPMENT, efficiency, English language, grammars, INPUT, INTERLINGUAL, LANGUAGE, LANGUAGE-INDEPENDENT NLP., linguistics, MAPPING, natural language, QUALITY, SPANISH LANGUAGE, verification}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA458756}, author = {Habash,Nizar and Dorr, Bonnie J and Traum,David} } @conference {18468, title = {Multimodal 3-D tracking and event detection via the particle filter}, booktitle = {IEEE Workshop on Detection and Recognition of Events in Video, 2001. Proceedings}, year = {2001}, month = {2001///}, pages = {20 - 27}, publisher = {IEEE}, organization = {IEEE}, abstract = {Determining the occurrence of an event is fundamental to developing systems that can observe and react to them. Often, this determination is based on collecting video and/or audio data and determining the state or location of a tracked object. We use Bayesian inference and the particle filter for tracking moving objects, using both video data obtained from multiple cameras and audio data obtained using arrays of microphones. The algorithms developed are applied to determining events arising in two fields of application. In the first, the behavior of a flying echo locating bat as it approaches a moving prey is studied, and the events of search, approach and capture are detected. In a second application we describe detection of turn-taking in a conversation between possibly moving participants recorded using a smart video conferencing setup}, keywords = {algorithms, APPROACH, audio data collection, audio signal processing, Bayesian inference, Bayesian methods, belief networks, CAMERAS, capture, conversation, echo, Educational institutions, Event detection, event occurrence, filtering theory, flying echo locating bat behaviour, Image motion analysis, inference mechanisms, Laboratories, microphone arrays, moving object tracking, moving participants, moving prey, multimodal 3D tracking, multiple cameras, Object detection, particle filter, Particle filters, Particle tracking, Robustness, search, smart video conferencing setup, target tracking, Teleconferencing, tracking filters, turn-taking detection, video data collection, video signal processing}, isbn = {0-7695-1293-3}, doi = {10.1109/EVENT.2001.938862}, author = {Zotkin,Dmitry N and Duraiswami, Ramani and Davis, Larry S.} } @article {17555, title = {Approximating low-congestion routing and column-restricted packing problems}, journal = {Information Processing Letters}, volume = {74}, year = {2000}, month = {2000/04//}, pages = {19 - 25}, abstract = {We contribute to a body of research asserting that the fractional and integral optima of column-sparse integer programs are {\textquotedblleft}nearby{\textquotedblright}. This yields improved approximation algorithms for some generalizations of the knapsack problem, with applications to low-congestion routing in networks, file replication in distributed databases, and other packing problems.}, keywords = {algorithms, Approximation algorithms, integer programming, Packing, Routing}, isbn = {0020-0190}, doi = {10.1016/S0020-0190(00)00033-8}, url = {http://www.sciencedirect.com/science/article/pii/S0020019000000338}, author = {Baveja,Alok and Srinivasan, Aravind} } @article {18800, title = {A Geometric Algorithm for Finding the Largest Milling Cutter}, volume = {ISR; TR 2000-40}, year = {2000}, month = {2000///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {In this paper, we describe a new geometric algorithm to determine the largest feasible cutter size for2-D milling operations to be performed using a single cutter. In particular:

1. We give a general definition of the problem as the task of covering a target region without interfering with anobstruction region. This definition encompasses the task of milling a general 2-D profile that includes bothopen and closed edges.

2. We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of thesedefinitions is most appropriate for the above problem.

3. We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we show thatour algorithm is correct.}, keywords = {algorithms, computational geometry, computer aided manufacturing CAM, cutter selection, Manufacturing, Next-Generation Product Realization Systems, path planning}, url = {http://drum.lib.umd.edu//handle/1903/6137}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @article {18801, title = {A Geometric Algorithm for Multi-Part Milling Cutter Selection}, volume = {ISR; TR 2000-42}, year = {2000}, month = {2000///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {Mass customization results in smaller batch sizes in manufacturing that require large numbers of setup and tool changes. The traditional process planning that generates plans for one part at a time is no longer applicable.

In this paper, we propose the idea of process planning for small batch manufacturing, i.e., we simultaneously consider multiple parts and exploit opportunities for sharing manufacturing resources such that the process plan will be optimized over the entire set of parts. In particular, we discuss a geometric algorithm for multiple part cutter selection in 2-1/2D milling operations.

We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we first discuss the lower and upper bond of cutter sizes that are feasible for given parts. Then we introduce the geometric algorithm to find the coverable area for a given cutter. Following that, we discuss the approach of considering cutter loading time and changing time in multiple cutter selection for multiple parts. We represent the cutter selection problem as shortest path problem and use Dijkstra{\textquoteright}s algorithm to solve it. By using this algorithm, a set of cutters is selected to achieve the optimum machining cost for multiple parts.

Our research illustrates the multiple parts process planning approach that is suitable for small batch manufacturing. At the same time, the algorithm given in this paper clarifies the 2-1/2D milling problem and can also help in cutter path planning problem.}, keywords = {algorithms, computer aided manufacturing CAM, cutter selection, Manufacturing, multi-part process planning, Next-Generation Product Realization Systems, OPTIMIZATION}, url = {http://drum.lib.umd.edu//handle/1903/6139}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @article {18863, title = {Selecting Flat End Mills for 2-1/2D Milling Operations}, volume = {ISR; TR 2000-41}, year = {2000}, month = {2000///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {The size of milling cutter significantly affects the machining time. Therefore, in order to perform milling operations efficiently, we need to select a set of milling cutters with optimal sizes. It is difficult for human process planners to select the optimal or near optimal set of milling cutters due to complex geometric interactions among tools size, part shapes, and tool trajectories.

In this paper, we give a geometric algorithm to find the optimal cutters for 2-1/2D milling operations. We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we introduced the offsetting and inverse-offsetting algorithm to find the coverable area for a given cutter. Following that, we represent the cutter selection problem as shortest path problem and discuss the lower and upper bond of cutter sizes that are feasible for given parts. The Dijkstra{\textquoteright}s algorithm is used to solve the problem and thus a set of cutters is selected in order to achieve the optimum machining cost.

We believe the selection of optimum cutter combination can not only save manufacturing time but also help automatic process planning.}, keywords = {algorithms, computer aided manufacturing CAM, cutter selection, Manufacturing, Next-Generation Product Realization Systems}, url = {http://drum.lib.umd.edu//handle/1903/6138}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @article {16718, title = {The Bible, Truth, and Multilingual OCR Evaluation}, year = {1998}, month = {1998/12//}, institution = {University of Maryland, College Park}, abstract = {Multilingual OCR has emerged as an important information technology, thanks to the increasing need for cross-language information access. While many research groups and companies have developed OCR algorithms for various languages, it is difficult to compare the performance of these OCR algorithms across languages. This difficulty arises because most evaluation methodologies rely on the use of a document image dataset in each of the languages and it is difficult to find document datasets in different languages that are similar in content and layout. In this paper we propose to use the Bible as a dataset for comparing OCR accuracy across languages. Besides being available in a wide range of languages, Bible translation are closely parallel in content, carefully translated, surprisingly relevant with respect to modern-day language, and quite inexpensive. A project at the University of Maryland is currently implementing this idea. We have created a scanned image dataset with groundtruth from an Arabic Bible. We have also used image degradation models to create synthetically degraded images of a French Bible. We hope to generate similar Bible datasets for other languages, and we are exploring alternative corpora such as the Koran and the Bhagavad Gita that have similar properties. Quantitative OCR evaluation based on the Arabic Bible dataset is currently in progress.}, keywords = {*BIBLE, *CORPUS, *DATASETS, *GROUNDTRUTH, *OPTICAL CHARACTER RECOGNITION, *TEST SETS, *TRANSLATIONS, accuracy, algorithms, CYBERNETICS, DOCUMENT IMAGES, DOCUMENTS, IMAGES, INFORMATION SCIENCE, LANGUAGE, linguistics, MULTILINGUAL OCR(OPTICAL CHARACTER RECOGNITION), SYMPOSIA, TEST AND EVALUATION}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA458666}, author = {Kanungo,Tapas and Resnik, Philip} } @conference {17609, title = {Improved bounds and algorithms for hypergraph two-coloring}, booktitle = {39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings}, year = {1998}, month = {1998/11/08/11}, pages = {684 - 693}, publisher = {IEEE}, organization = {IEEE}, abstract = {We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn){\texttimes}2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1){\texttimes}2n due to Beck (1978). We further generalize this to a {\textquotedblleft}local{\textquotedblright} version, improving on one of the first applications of the Lovasz Local Lemma}, keywords = {algorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability}, isbn = {0-8186-9172-7}, doi = {10.1109/SFCS.1998.743519}, author = {Radhakrishnan,J. and Srinivasan, Aravind} } @article {14963, title = {Enhancing LZW Coding Using a Variable-Length Binary Encoding}, volume = {ISR-TR-1995-70}, year = {1995}, month = {1995///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {We present here a methodology to enhance the LZW coding for text compression using a variable-length binary encoding scheme. The basic principle of this encoding is based on allocating a set of prefix codes to a set of integers growing dynamically. The prefix property enables unique decoding of a string of elements from this set. We presented the experimental results to show the effectiveness of this variable-length binary encoding scheme.}, keywords = {algorithms, data compression, Systems Integration Methodology}, url = {http://drum.lib.umd.edu/handle/1903/5654}, author = {Acharya,Tinku and JaJa, Joseph F.} } @conference {11982, title = {Global rigidity constraints in image displacement fields}, booktitle = {Proceedings of Fifth International Conference on Computer Vision, 1995}, year = {1995}, month = {1995/06/20/23}, pages = {245 - 250}, publisher = {IEEE}, organization = {IEEE}, abstract = {Image displacement fields-optical flow fields, stereo disparity fields, normal flow fields-due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views}, keywords = {3D motion parameters, algorithms, Automation, Computer science, Computer vision, conic sections, curves, equal vectors, Fluid flow measurement, global geometric structure, global rigidity constraints, image displacement fields, Image motion analysis, Image segmentation, Image sequences, imaging surface, Laboratories, Layout, Motion estimation, Motion measurement, motion vectors, multiple views, normal flow fields, optical flow fields, regions, rigid motion, stereo disparity fields, Stereo vision, vectors, visual information recovery}, isbn = {0-8186-7042-8}, doi = {10.1109/ICCV.1995.466779}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @conference {14168, title = {Global rigidity constraints in image displacement fields}, booktitle = {, Fifth International Conference on Computer Vision, 1995. Proceedings}, year = {1995}, month = {1995/06/20/23}, pages = {245 - 250}, publisher = {IEEE}, organization = {IEEE}, abstract = {Image displacement fields-optical flow fields, stereo disparity fields, normal flow fields-due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views}, keywords = {3D motion parameters, algorithms, Automation, Computer science, Computer vision, conic sections, curves, equal vectors, Fluid flow measurement, global geometric structure, global rigidity constraints, image displacement fields, Image motion analysis, Image segmentation, Image sequences, imaging surface, Laboratories, Layout, Motion estimation, Motion measurement, motion vectors, multiple views, normal flow fields, optical flow fields, regions, rigid motion, stereo disparity fields, Stereo vision, vectors, visual information recovery}, isbn = {0-8186-7042-8}, doi = {10.1109/ICCV.1995.466779}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @article {18833, title = {Feature Recognition for Manufacturability Analysis}, volume = {ISR; TR 1994-10}, year = {1994}, month = {1994///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {While automated recognition of features has been attempted for a wide range of applications, no single existing approach possesses the functionality required to perform manufacturability analysis. In this paper, we present a methodology for taking a CAD model and extracting a set of machinable features suitable for generating all alternative interpretations of the model as collections of MRSEVs (Material Removal Shape Element Volumes, a STEP-based library of machining, features). This set of MRSEVs is to be employed for manufacturability analysis. The algorithm handles a variety of features including those describing holes, pockets, slots, and chamfering and filleting operations. In addition, it considers elementary accessibility constraints for these features and is provably complete over a, significant class of machinable parts the features describe. Further, the approach has low-order polynomial-time worst-case complexity.}, keywords = {algorithms, Automation, COMPUTER AIDED DESIGN, computer aided manufacturing, computer integrated manufacturing, Feature extraction, manufacturability, Manufacturing, Solid modeling, Systems Integration}, url = {http://drum.lib.umd.edu//handle/1903/5490}, author = {Regli,W. C. and Gupta, Satyandra K. and Nau, Dana S.} } @article {14914, title = {Uncertainty Propagation in Model-Based Recognition.}, year = {1994}, month = {1994/12//}, institution = {MASSACHUSETTS INSTITUTE OF TECHNOLOGY ARTIFICIAL INTELLIGENCE LAB}, abstract = {Building robust recognition systems requires a careful understanding of the effects of error in sensed features. Error in these image features results in a region of uncertainty in the possible image location of each additional model feature. We present an accurate, analytic approximation for this uncertainty region when model poses are based on matching three image and model points, for both Gaussian and bounded error in the detection of image points, and for both scaled-orthographic and perspective projection models. This result applies to objects that are fully three-dimensional, where past results considered only two-dimensional objects. Further, we introduce a linear programming algorithm to compute the uncertainty region when poses are based on any number of initial matches. Finally, we use these results to extend, from two-dimensional to three-dimensional objects, robust implementations of alignment interpretation-tree search, and transformation clustering. (AN)}, keywords = {*IMAGE PROCESSING, *PATTERN RECOGNITION, algorithms, APPROXIMATION(MATHEMATICS), CYBERNETICS, ERROR CORRECTION CODES, image registration, Linear programming, MATCHING, MATHEMATICAL MODELS, PIXELS, PROJECTIVE TECHNIQUES., regions, THREE DIMENSIONAL, TWO DIMENSIONAL, Uncertainty}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA295642}, author = {Jacobs, David W. and Alter,T. D.} } @article {12051, title = {Computing Intrinsic Images.}, year = {1986}, month = {1986/08//}, abstract = {Low level modern computer vision is not domain dependent, but concentrates on problems that correspond to identifiable modules in the human visual system. Several theories have been proposed in the literature for the computation of shape from shading, shape from texture, retinal motion from spatiotemporal derivatives of the image intensity function and the like. The problems with the existing approach are basically the following: (1) The employed assumptions are very strong and so most of the algorithms fail when applied to real images. (2) Usually the constraints from the geometry and the physics of the problem are not enough to guarantee uniqueness of the computed parameters. (3) In most cases the resulting algorithms are not robust, in the sense that if there is a slight error in the input this results in a catastrophic error in the output. In this thesis the problem of machine vision is explored from its basics. A low level mathematical theory is presented for the unique robust computation of intrinsic parameters. The computational aspect of the theory envisages a cooperative highly parallel implementation, bringing in information from five different sources (shading, texture, motion, contour and stereo), to resolve ambiguities and ensure uniqueness and stability of the intrinsic parameters. The problems of shape from texture, shape from shading and motion, visual motion analysis and shape and motion from contour are analyzed in detail.}, keywords = {*ARTIFICIAL INTELLIGENCE, *COMPUTERS, *IMAGE PROCESSING, *VISION, algorithms, CAMERAS, CATASTROPHIC CONDITIONS, COMPUTATIONS, CYBERNETICS, ERRORS, HUMANS, IMAGES, INTENSITY, LOW LEVEL, MATHEMATICS, MOTION, RETINA, Robots, SHADOWS, SHAPE, TEXTURE, THEORY, THESES.}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA189440}, author = {Aloimonos, J.} } @article {15672, title = {Voronoi Diagrams on the Surface of a Polyhedron.}, year = {1985}, month = {1985/05//}, institution = {CENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK}, abstract = {This document presents an algorithm that computes the Voronol diagram of a set of point lying on the surface of a possibly nonconvex polyhedron. Distances are measured in the Euclidean metric along the surface of the polyhedron. The algorithm runs in O(n squared log n) time and requires O(n squared) space to store the final data structure, where n is the maximum of the number of edges and source points on the polyhedron. This algorithm generalizes or improves the running times of a number of shortest path problems both on polyhedra and in the plane amidst polygonal obstacles. By applying standard algorithms for point location, we can determine the distance from a query point to the nearest source in O(log n) time and can list the shortest path in O(k + log n) time, where k is the number of faces traversed by the path. The algorithm achieves its efficiency by a novel method of searching the polyhedron{\textquoteright}s surface. (Author)}, keywords = {*POLYGONS, *Polyhedrons, algorithms, DIAGRAMS., EDGES, INTERROGATION, PATHS, PE61102F, POSITION(LOCATION), SURFACES, THEORETICAL MATHEMATICS, WUAFOSR2304A7}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA166220}, author = {Mount, Dave} }