CSE 600 (Ongoing Research Seminar)

In conjunction with ever-increasing high-performance computational power and ever-improving data acquisition technologies, the complexity and scale of the data acquired from physical experiments and numerics-driven simulations has continued to grow at an explosive pace. Consequently, it demands better modeling, analysis, simulation, and visualization tools that can reveal the insight from raw datasets and facilitate the interpretation of high-level knowledge. In this talk, I will present a set of novel deformable models that aim to serve for this need.

Deformable models are geometric object models whose dynamic behaviors are governed by variational principles and/or partial differential equations (PDEs). They have proven to be extremely valuable in an increasing number of applications spanning physical and computational sciences, computer-integrated engineering, visual computing, data visualization, finite element simulation, and medical imaging analysis. In particular, I will present the new PDE-driven, flow-based, subdivision models which are capable of recovering arbitrary, complicated shape geometry as well as its unknown topology simultaneously. Our new deformable models are based on adaptive subdivision geometry, which offers a potent multi-resolution representation and hierarchical structure, while their topological flexibility results from the PDEs associated with the popular level-set approach. After motivating the talk, I will formulate the mathematics of the underlying PDE-based surface flow that will govern the model behavior. I will then discuss the relevant geometric, algorithmic, numerical techniques that enable our new deformable models to work in many applications such as shape and structure extraction from medical images, reverse engineering from unorganized point clouds, reconstructing 3D geometry and texture from 2D visual input, iso-surface extraction for data visualization, and feature and front tracking for time-varying datasets in computational sciences.

Mr. Eugene Zhang is a Ph.D. candidate at Georgia Institute of Technology, where he has been studying Computer Graphics and Visualization with the emphasis on topology-based analysis on surfaces for image synthesis. His works on "feature-based surface parameterization and texture mapping" and "vector field design on surfaces" are two such examples. Prior to coming to Georgia Tech in 1999, He was a database developer and a group manager at Datastream System Inc. from 1995-1999, customizing Computerized Maintenance Management Software. He received a M.Sc in Mathematics in 1994, and a M.Sc in Computer Science in 1995, both from Ohio State University.

Vector field design on surfaces is necessary for many graphics applications: example-based texture synthesis, non-photorealistic rendering, and fluid simulation. In this talk, I will present our vector field design system for surfaces that allows a user to create a large variety of vector fields with relatively little effort. Furthermore, the system allows the user to control the number of singularities in the vector field and their placement. Our system combines basis vector fields to make an initial vector field that meets the user's specifications. The initial vector field often contains unwanted singularities, which cannot always be eliminated due to the Poincar-Hopf index theorem. To reduce the visual artifacts caused by these singularities, our system allows a user to move a singularity to a more favorable location or to cancel a pair of singularities. These operations provide topological guarantees for the vector field in that they only affect the user-specified singularities. Other editing operations are also provided so that the user may change the topological and geometric characteristics of the vector field. At the end, I will show the results of applying our vector field design system to several applications: example-based texture synthesis, painterly rendering of images, and pencil sketch illustrations of smooth surfaces.

The need to navigate through increasingly complex virtual environments for simulation based design, and its validation, has motivated research in computer graphics for long. While hardware performance has grown at an impressive rate, model sizes have grown faster. In order to achieve realistic interactive walkthroughs we need to take a comprehensive approach and enrich models with rendering enhancing information.

In this talk I will present an algorithm to render increasingly large spline and polygonal models. I will describe parallel pre-processing methods to generate data useful for efficient rendering algorithms. I will discuss multi-resolution model representations, dynamic tessellation of parametric surfaces and polygonal simplification. I will present both point and region based visibility algorithms and introduce the notion of vLOD: the visible level of detail. Finally, I will argue that efficient pre-processing and data compression methods enable scalable output sensitive display algorithms that that do not necessarily slow down with increasing model sizes.

Short Bio:

Prof. Kumar is the director of the graphics lab at the Johns Hopkins University. He earned his PhD from the university of North Carlina at Chapel Hill in 1996 before joining the faculty of computer science at the Johns Hopkins University. His research interests include interactive 3D graphics, large-scale walkthrough, curved surface rendering and geometric processing. Prof. Kumar has earned the NSF CAREER award and two best paper awards

Abstract:

Large scale, self-organizing sensor networks are expected to enable numerous applications in environmental monitoring, security and surveillance, etc. Many such systems will face adverse or hostile conditions, including poor or unpredictable wireless channels, node failures or malfunctions due to external destructions or internal faults, or even intentional attacks from malicious parties. Despite these severe situations, sensor networks should possess sufficient resiliency to operate robustly and provide the services normally.

In this talk I will present my work on sensor network resiliency against adverse conditions and malicious attacks. GRAdient Broadcast (GRAB) provides robust data delivery over many hops of unreliable nodes and lossy wireless channels. Instead of binding data delivery to explicit paths, nodes make forwarding decisions on the fly, based on state carried in packets. Thus data delivery is immune from significant node failures and channel errors. Statistical En-route Filtering (SEF) detects and drops bogus sensing data injected by compromised insider nodes en-route, so as to avoid wasting network resources or causing application failures. It aims at intentional attacks launched by malicious parties. These two pieces of work demonstrate that we can exploit the unique characteristics of sensor networks such as scale and redundancy to remove the reliance on individual pieces, thus build resilient systems out of unreliable components.

Speaker Bio:

Fan Ye received his B.E. in 1996 and M.S. in 1999, both from Tsinghua University, China. He is expected to get his Ph.D. in Computer Science from UCLA by June, 2004. His research interests include sensor networks, wireless networks and the Internet, with focus on protocol design, prototyping and evaluation on resiliency and security aspects of large scale sensor networks.

In this talk, I will present the design and evaluation of a new Internet routing architecture (NIRA). The present Internet routing system suffers from two problems: one structural and one architectural. The structural problem is that the current system has little support for users to choose domain-level routes. User choice plays an important role in creating market competition, which fosters innovation and the introduction of new services. The architectural problem is that the current system fails to scale effectively in the presence of real-world requirements such as multi-homing.

NIRA is a scalable architecture that gives a user the ability to choose domain-level routes. The design of NIRA addresses four problems: how routes are discovered and selected, how routes are efficiently represented, how route failures are detected, and how providers are compensated. NIRA augments a strict provider-rooted addressing hierarchy with a new topology distribution and address allocation capability to enable scalable route discovery and efficient route representation. It combines proactive notification and reactive discovery for fast failure detection. NIRA's provider compensation model is still contract-based. The evaluation of NIRA suggests that it is practical.

Bugs in security-critical software are common and costly. I propose a lightweight approach both for finding these bugs and for verifying their absence in large software programs. In this approach, I identify rules of safe programming practice, encode them as safety properties, and verify whether programs satisfy these properties. Since manually verifying properties is expensive, I have developed a model checking tool, MOPS, for automating this process.

To achieve my goal of making model checking for security practical, I must solve three research challenges: making MOPS scale to large programs, helping the MOPS user specify complex but structured properties, and allowing the user to apply MOPS conveniently and comprehend its error reports easily. I will describe my new algorithms and approaches for solving these challenges.

Using MOPS, I checked over one million lines of mature, widely deployed application programs and discovered more than a dozen security vulnerabilities and weaknesses. I checked a security API on several Unix systems and found portability pitfalls, documentation errors, and an implementation bug. I also verified several invariants in the EROS kernel.

Abstract:

Efficient computation and visualization of protein properties is of utmost importance for studying several computational biology applications, such as protein folding and rational drug design. We have developed a system to efficiently solve the non-linear Poisson-Boltzmann equation governing molecular electrostatics. Our system simultaneously improves the accuracy and the efficiency of the solution by adaptively refining the computational grid near the solute-solvent interface. We use pre-computed accumulation of transparency with spherical-harmonics-based compression to accelerate volume rendering of molecular electrostatics.

Next, we discuss how the same idea of pre-computation and spherical-harmonics-based compression can be used to speed up the rendering of translucent materials. The outgoing radiance of a translucent surface is expressed as a 6D integral of a Bi-directional Scattering Surface Reflectance Distribution Function (BSSRDF). Our analysis first reduces it to a 4D function and then uses a novel reference-points scheme to compactly represent the pre-computed integrals using a hierarchical and progressive spherical harmonics representation. Our algorithm scales linearly with the number of mesh vertices and achieves one to two orders of magnitude speedup in rendering translucent meshes.

Speaker Biography:

Xuejun Hao is a doctoral candidate in the Department of Computer Science at the University of Maryland, College Park. He received the BS degree in Physics from Peking University, China. He received the MA degree in Physics and the MS degree in Computer Science from the State University of New York at Stony Brook in 1996 and 2000, respectively. His current research interests are in interactive 3D graphics, scientific visualization, molecular graphics, and illumination modeling.

Abstract:

The nature of mobile devices is changing in two distinct ways: a) With wireless connectivity being enabled in non-traditional mobile devices (e.g., vehicles, smart watches), mobile nodes are not just increasing in sheer number, but also exhibiting significant variation in capabilities (e.g., battery power, memory size). b) An increasing number of personal communication devices (e.g., cell phones, laptops) are being fitted with multiple wireless access technologies. To work across this device and network heterogeneity, the location management system must be adaptive, adjusting its behavior to the mobility patterns and constraints of individual mobile nodes, using as general a set of assumptions as possible. This adaptation must also allow for personalization, so that the same access networks provide location management functions that are customized for each individual-s or group-s preferences. This talk describes ways in which information and coding theory can be used to achieve this adaptation and personalization in future cellular environments.

In the first part of the talk, I'll introduce the relatively new problem of tracking user location in an integrated multi-system wireless environment, where each mobile device has multiple, possibly simultaneously active, interfaces, each corresponding to a different access technology (e.g., satellite, wide-area cellular, WLAN, Bluetooth, etc.) In particular, there is a need for a distributed location tracking strategy, where operators of each individual access technology are not required to publicly share sensitive information, such as network topologies and cell patterns. I-ll explain the optimal bounds on location management costs in terms of the concept of weighted entropy, and then present three different location management techniques, each offering different degrees of decentralization. In the second part of the talk, I shall describe how the well-known rate-distortion framework can be used to capture the tradeoffs between the update and paging costs associated with location tracking, and propose two new algorithms that apply entropy coding on RA-level movement information. Time permitting, I-ll explain how vector quantization techniques can be used in this tradeoff process. I-ll conclude with an overview of open challenges in adaptive mobility management.

Speaker Bio:

Dr. Archan Misra is a Research Staff Member with the Pervasive Security and Networking Department at the IBM TJ Watson Research Center, Hawthorne, NY. His current research efforts are related to services and mobility protocols for next-generation (4G) wireless networks, on-demand middleware for Internet-scale distributed computing systems, and MAC/routing protocols for energy-efficient, high-performance wireless networks. Prior to joining IBM in 2001, Archan spent 3 1/2 years at Telcordia Technologies (formerly called Bellcore), where he worked in the areas of IP-based mobility management, congestion control and Internet QoS architectures. He has published extensively in the areas of wireless networking, congestion control and mobility management and was a co-author on papers that received the Best Paper awards in ACM WOWMOM 2002 and IEEE MILCOM 2001. Archan received his Ph.D. in Electrical and Computer Engineering from the University of Maryland at College Park in May, 2000, and his B.Tech in Electronics and Communication Engineering from IIT Kharagpur, India in July 1993.

Abstract:

Efficient computation and visualization of protein properties is of utmost importance for studying several computational biology applications, such as protein folding and rational drug design. We have developed a system to efficiently solve the non-linear Poisson-Boltzmann equation governing molecular electrostatics. Our system simultaneously improves the accuracy and the efficiency of the solution by adaptively refining the computational grid near the solute-solvent interface. We use pre-computed accumulation of transparency with spherical-harmonics-based compression to accelerate volume rendering of molecular electrostatics.

Next, we discuss how the same idea of pre-computation and spherical-harmonics-based compression can be used to speed up the rendering of translucent materials. The outgoing radiance of a translucent surface is expressed as a 6D integral of a Bi-directional Scattering Surface Reflectance Distribution Function (BSSRDF). Our analysis first reduces it to a 4D function and then uses a novel reference-points scheme to compactly represent the pre-computed integrals using a hierarchical and progressive spherical harmonics representation. Our algorithm scales linearly with the number of mesh vertices and achieves one to two orders of magnitude speedup in rendering translucent meshes.

Speaker Biography:

Xuejun Hao is a doctoral candidate in the Department of Computer Science at the University of Maryland, College Park. He received the BS degree in Physics from Peking University, China. He received the MA degree in Physics and the MS degree in Computer Science from the State University of New York at Stony Brook in 1996 and 2000, respectively. His current research interests are in interactive 3D graphics, scientific visualization, molecular graphics, and illumination modeling.

Bio:

C. R. Ramakrishnan received his PhD in Computer Science from Stony Brook in 1995. He holds M.Sc (Tech.) in Computer Science and M.Sc. (Hons.) in Physics from BITS, Pilani, India. He has been on the faculty in the CS department at Stony Brook since 1997. His areas of interest include Formal Methods, Logic Programming, Programming Languages, and Security.

Abstract:

Most software systems in day-to-day use are composed of many interacting components. As these systems become more complex, the process of creating and maintaining them becomes error prone. Program analysis and verification techniques are aimed at deducing intersting properties of such systems. Many analysis and verification techniques can be simply formulated (and efficiently implemented) as query evaluation over logic programs. More interestingly, novel ways to evaluate logic programs lead to neat solutions to certain crucial problems in program analysis and verification. In this talk, I will illustrate this using two examples from my current research projects: incrementality in program analysis, and state-space reduction in verification.