Physical Sciences and Mathematics Commons^™

A Methodology For Efficiently Sampling The Conformation Space Of Molecular Structures, Audrey Lee, Ileana Streinu, Oliver Brock

Computer Science: Faculty Publications

Motivated by recently developed computational techniques for studying protein flexibility, and their potential applications in docking, we propose an efficient method for sampling the conformational space of complex molecular structures. We focus on the loop closure problem, identified in the work of Thorpe and Lei (2004 Phil. Mag. 84 1323-31) as a primary bottleneck in the fast simulation of molecular motions. By modeling a molecular structure as a branching robot, we use an intuitive method in which the robot holds onto itself for maintaining loop constraints. New conformations are generated by applying random external forces, while internal, attractive forces pull …

Flow Lookup And Biological Motion Perception, Nicholas Howe

Computer Science: Faculty Publications

Optical flow in monocular video can serve as a key for recognizing and tracking the three-dimensional pose of human subjects. In comparison with prior work using silhouettes as a key for pose lookup, flow data contains richer information and in experiments can successfully track more difficult sequences. Furthermore, flow recognition is powerful enough to model human abilities in perceiving biological motion from sparse input. The experiments described herein show that a tracker using flow moment lookup can reconstruct a common biological motion (walking) from images containing only point light sources attached to the joints of the moving subject.

Boosted Decision Trees For Word Recognition In Handwritten Document Retrieval, Nicholas Howe, Toni M. Rath, R. Manmatha

Computer Science: Faculty Publications

Recognition and retrieval of historical handwritten material is an unsolved problem. We propose a novel approach to recognizing and retrieving handwritten manuscripts, based upon word image classification as a key step. Decision trees with normalized pixels as features form the basis of a highly accurate AdaBoost classifier, trained on a corpus of word images that have been resized and sampled at a pyramid of resolutions. To stem problems from the highly skewed distribution of class frequencies, word classes with very few training samples are augmented with stochastically altered versions of the originals. This increases recognition performance substantially. On a standard …

Non-Stretchable Pseudo-Visibility Graphs, Ileana Streinu

Computer Science: Faculty Publications

We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The example is based on the characterization of vertex-edge pseudo-visibility graphs of O'Rourke and Streinu [Proc. ACM Symp. Comput. Geometry, Nice, France, 1997, pp. 119-128] and extends a recent result of the author [Proc. ACM Symp. Comput. Geometry, Miami Beach, 1999, pp. 274-280] on non-stretchable vertex-edge visibility graphs. We construct a pseudo-visibility graph for which there exists a unique compatible vertex-edge visibility graph, which is then shown to be non-stretchable. The construction is then extended to an infinite family. © …

Finding And Maintaining Rigid Components, Audrey Lee, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

We give the first complete analysis that the complexity of finding and maintaining rigid components of planar bar-and-joint frameworks and arbitrary d-dimensional body-and-bar frameworks, using a family of algorithms called pebble games, is O(n2). To this end, we intro- duce a new data structure problem called union pair- find, which maintains disjoint edge sets and supports pair-find queries of whether two vertices are spanned by a set. We present solutions that apply to generalizations of the pebble game algorithms, beyond the original rigidity motivation.

Computing Rigid Components Of Pseudo-Triangulation Mechanisms In Linear Time, Jack Snoeyink, Ileana Streinu

Computer Science: Faculty Publications

We investigate the problem of detecting rigid components (maximal Laman subgraphs) in a pseudotriangulation mechanism and in arbitrary pointed planar frameworks.F or general Laman graphs with some missing edges, it is known that rigid components can be computed in O(n2) time.Here we make substantial use of the special geometry of pointed pseudo-triangulation mechanisms to achieve linear time. The main application is a more robust implementation and a substantial reduction in numerical computations for the solution to the Carpenter's Rule problem given by the second author.

Pseudo-Triangulations, Rigidity And Motion Planning, Ileana Streinu

Computer Science: Faculty Publications

This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter's Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm …

The Correlation Between Internal & External Markers For Abdominal Tumors: Implications For Respiratory Gating, David P. Gierga, Johanna Brewer, Gregory C. Sharp, Margrit Betke, Christopher G. Willett, George T.Y. Chen

Computer Science: Faculty Publications

Purpose: The correlation of the respiratory motion of external patient markers and abdominal tumors was examined. Data of this type are important for image-guided therapy techniques, such as respiratory gating, that monitor the movement of external fiducials.

Methods and Materials: Fluoroscopy sessions for 4 patients with internal, radiopaque tumor fiducial clips were analyzed by computer vision techniques. The motion of the internal clips and the external markers placed on the patient’s abdominal skin surface were quantified and correlated.

Results: In general, the motion of the tumor and external markers were well correlated. The maximum amount of peak-to-peak craniocaudal tumor motion …

A Dictionary Construction Technique For Code Compression Systems With Echo Instructions, Philip Brisk, Jamie Macbeth, Ani Nahapetian, Majid Sarrafzadeh

Computer Science: Faculty Publications

No abstract provided.