Seminar Archive – Spring 1998

January 6, 1998

In this talk, we describe conference network of servers based on a configurable computing architecture to support creation and maintenance of simultaneous conferences among sets of $$N$$ conferees with on-line conference requests, where a conference realized on conference network by connecting servers assigned to the conferees remains until its termination. A conference network of $$M$$ servers with link capacity $$c$$ is required to support conferencing for $$N$$ users with certain capabilities such as strictly nonblocking where requests can be assigned arbitrarily, and wide-sense nonblocking where a request assignment algorithm is needed. We study the structural design requirement, on number $$M$$ of servers and link capacity $$C$$, for network of certain structure, and connection management for the server architecture.

We consider conference network models with single and multiple link capacity. For single-capacity case, we show the necessary and sufficient conditions such that an $$r$$-dimensional conferencing mesh of $$M$$ servers provides strictly non-blocking conferencing to $$N$$ conferees are $$M = O(N^{(r+1)/r})$$ nodes for fixed $$r$$, while $$M = O(r N^{(r+1)/r})$$ nodes are sufficient for $$r$$-D mesh with arbitrary $$r$$. A fundamental relationship involving isoperimetric ratios is established between $$M$$ and $$N$$ for general graphs; For multi-capacity meshes, we show $$c = O(N^{1/r})$$ capacity is sufficient for $$r$$-D mesh of $$M = N$$ nodes to support $$N$$ users for wide-sense nonblocking. Interesting trade-off between number $$M$$ of servers and link capacity $$c$$ is thus obtained. Greedy algorithm is designed to satisfy on-line conference requests and its performance is evaluated analytically and studied by simulation. The study shows the algorithm performs very well for meshes with small link capacity. The multi-capacity mesh design offers a practical construction for conference networks.

We also consider scalable hierarchical topology aggregation approach for routing management of large scale networks. Topology aggregation schemes are used in hierarchical source routing frameworks such as the ATM PNNI standard for scalability and security reasons. We discuss the design and implementation of a simulation environment which emulates PNNI. Using this simulator, we study by simulation the performance, in terms of network throughput and signaling delay, of link cost metrics and various topology aggregation schemes. Our study results in verification of theoretical superiority of the exponential cost metric for hierarchical routing and identification of aggregation schemes with good performance/representation trade-off. New re-aggregation policy called logarithmic update is studied to achieve reduction on computation overhead.

January 29, 1998

With over 3000 systems installed, the RS/6000 SP is doing phenomenally well in both technical and commercial high performance computing environments. These environments are evolving to bring together simulation and modelling, visualisation, database management, data mining, and network computing. The presentation will highlight the architecture and design principles that make the RS/6000 SP a truly general purpose parallel computer and indicate how this architecture will evolve in the future to satisfy user requirements in an unprecedented manner.

February 20, 1998

Polygonal models currently dominate the field of interactive three-dimensional computer graphics. This is largely because their mathematical simplicity allows rapid rendering of polygonal datasets, which in turn has led to widely available polygon- rendering hardware. Moreover, polygons serve as a sort of lowest common denominator for computer models, since almost any model representation (spline, implicit-surface, volumetric) can be converted with arbitrary accuracy to a polygonal mesh.

In many cases the complexity of such models exceeds the capability of graphics hardware to render them interactively. Polygonal simplification methods simplify the polygonal geometry of small or distant objects to reduce the rendering cost without a significant loss in the visual content of the scene. I will Simplification, or HDS. HDS operates dynamically, retessellating the scene continuously as the user’s viewing position shifts, and adaptively, processing the entire database without first decomposing the environment into individual objects. By supporting various preprocessing algorithms and various run-time criteria, HDS provides a general framework for dynamic view-dependent simplification.

February 27, 1998

March 2, 1998

An object’s appearance depends on both the observer’s viewpoint and the illumination. The question arises: What is the set of images of an object under all lighting conditions and viewpoints? In this talk, we focus on enlightenment, including multiple, extended light sources and shadowing. It will be shown that the set of n-pixel images of an object of any shape and with a general reflectance function, seen under all possible illumination conditions forms a convex cone in $$R^n$$. If the object is convex with a Lambertian reflectance function and is illuminated by an arbitrary number of point light sources at infinity, this illumination cone is polyhedral, and its dimension equals the number of distinct surface normals on the object. It can be constructed from three or more images, and recognition from a single image can be cast as determining set membership.

This leads us to another question: What objects are indistinguishable from only their images? It will be shown that if two objects differ by a “generalized bas-relief transformation,” then their illumination cones are identical. For each image of a surface produced by a light source, there exists an identical image of the bas-relief produced by a transformed light source. This equality holds for both shaded and shadowed regions. Since antiquity, artists have been aware of this ambiguity when creating flattened bas-relief sculptures which give an exaggerated perception of depth. For a moving observer, the set of all possible motion fields for a bas-relief is identical to the set produced by a full relief. Thus, neither small observer motions nor changes of illumination can resolve the bas-relief ambiguity.

These results are consistent with recent psychophysical studies and have lead to new methods for shape reconstruction from shadows. They have been used for face recognition in a system which is trained with a small number of well-illuminated images, yet which can perform recognition under illumination extremes where faces are heavily shadowed. When compared to competitive techniques, our method had an order of magnitude fewer errors.

March 6, 1998

This talk describes the Xtrieve cross-modal information retrieval system, a prototype system for demonstrating cross-modal retrieval of multimedia content. Multimedia data is rapidly accumulating and powerful computational methods for accessing specific content are desperately needed. This is a difficult problem, involving speech recognition, image understanding, and pattern recognition over a diverse range of noisy and imprecise data. General solutions to this problem are proving elusive. Cross-modal information retrieval is a new multimedia data access technology based on searching one media in response to a query and presenting the result in an alternative, potentially heterogeneous media. In many cases correlations exist between media streams which can be exploited to facilitate this process and allow reliable retrieval. One example is the temporal relationship between speech audio and a transcript of that audio. If this temporal relationship can be discovered, a query into the text transcript can produce an audio result.

Xtrieve is the first experimental system to specifically address cross-modal information retrieval. Xtrieve implements a general structure for cross-modal access. Specific cross-modal correlation of text to audio and text to alternative text are demonstrated. Many important issues addressed in the Xtrieve development process will be described including retrieval granularity, temporal presentation of results, and content structure analysis. The underlying synchronization technology, multiple media stream correlation, will also be discussed. Additional applications for this new technology include language translation align

March 13, 1998

A fundamental goal in visualization research is the quest for insight into the science behind the art of effective visual communication. In this talk I will present some of my research into methods for facilitating a rapid, comprehensive understanding of the complex spatial relationships between multiple superimposed structures in 3D datasets. In the first part of my talk, I will focus on issues in the perception and representation of surface shape. I will describe the perceptual motivation, artistic inspiration, and practical implementation of techniques for using opaquely rendered valley and sharp ridge lines to create a viewpoint-independent 3D ‘sketch’ of a transparent object that highlights its essential shape features, and for generating and applying principal direction stroke textures to intuitively convey the 3D shape of smoothly curving surfaces that are not well-characterized by ridge or valley lines. I will discuss the design and implementation of a controlled observer experiment intended to assess the practical benefit of adding discrete, opaque texture to a transparent surface, and will summarize and discuss the implications of the experimental results. In the second part of my talk, I will focus on issues in the effective visualization of 3D flow. I will show how line integral convolution techniques can be used to illustrate 3D flow through a volume, and how the introduction of visibility-impeding ‘halos’ can clarify the depth order relationships among densely clustered, overlapping streamlines by subtly emphasizing the depth discontinuities in any arbitary 2D projection of the flow. I will describe how information about the direction of the flow can be efficiently incorporated into the 3D representation, and how color can be applied to convey information about related scalar quantities over the flow. The talk will conclude with a brief discussion of future directions for work.