Graphics Lunch

Home Members Applications Projects Seminars Publications Facilities Internal Web Contact Us

Search

Graphics Lunch - Fall, 2006

Graphics Lunch is a forum for informal and formal discussions over lunch for those interested in graphics and visualization issues at Maryland. It also serves as a forum for talks from visitors to our lab about their recent research in graphics and visualization. Students and faculty can use this venue to practise and prepare for their conference papers, discuss recent and upcoming papers and conferences, or inform others about graphics and visualization news. Meetings are held on Mondays from 12:00pm to 1:30pm in AVW 4185 .
Announcements regarding Graphics Lunch will be sent to the graphics-local mailing list. You may join this list at http://www.cs.umd.edu/mailman/listinfo/graphics-local.

  Recent Seminars

Dec 4, 2006 TBA

Presented By Jin Hyuk Jung, University of Maryland, College Park

Comments Graphics Seminar Series

Abstract
A central computation in solving minimizaton problems is finding a search direction that can be used to lower the function value. In Interior Point Methods (IPMs) for linear programming, for example, we compute the direction by solving the normal equations $\mathbf{A}\mathbf{D}\mathbf{A} ^T\Delta\mathbf{x} = \mathbf{r}$, where $\mathbf{A}$ is an $m \times n$ matrix, $\mathbf{D}$ is an $n \times n$ diagonal matrix, and $\Delta\mathbf{x}$ and $\mathbf{r}$ are column vectors. To solve these equations, we need to form the matrix and compute its Cholesky factor, which is a lower triangular matrix. For efficiency we should exploit the symmetry of the matrix.

In this work we present efficient algorithms for assembling and factoring the matrix using triangular rasterization on a GPU. Since the matrix is symmetric, only its lower triangular part needs to be computed. So we reduce computational effort by half by computing via triangular rasterization. We also use triangular rasterization to implement a Cholesky decomposition algorithm, which performs 95\% faster for large matrices than the LU decomposition (without pivoting) proposed by Galoppo et al.

In addition we present efficient GPU algorithms for assembling and decomposing the matrix in a rectangular packed format, which requires only half the storage space, without sacrificing performance. We store the right lower-triangular submatrix in the unused upper left corner by rotating the submatrix by 180 degrees. By rasterizing two triangles simultaneously, we demonstrate that assembling and decomposing the packed matrix can be performed as fast as for the non-packed matrix.

In the IPM, assembling and decomposing the matrix are most demanding of computational resources, and support for triangular rasterization is essential in exploiting the symmetric structure of the matrix. This provides one reason for developers of streaming languages targeting GPUs to consider implementing this feature.

Nov 13, 2006 Display Wall and VNode Cluster Overview

Presented By Derek Juba, University of Maryland, College Park

Comments Graphics Seminar Series
Slides from this talk

Abstract
For this Graphics Lunch I will be giving an intro to the vnode CPU/GPU cluster. This cluster was created as the result of a collaboration between many different faculty members for coupled CPU/GPU computing and visualization. After the intro talk, we'll go over to GVIL where I'll show some demos on the tiled LCD display wall.

This talk should be of interest to anyone planning to do research on the cluster, or anyone who's curious about what that giant black panel in AVW 4406 is.

Oct 16, 2006 VAST presentation practice

Presented By Various

Comments Graphics Seminar Series
Held in AVW 3258

Abstract
The papers to be presented are:

D-Dupe: An Interactive Tool for Entity Resolution in Social Networks
      Mustafa Bilgic*, Louis Licamele, Lise Getoor, Ben Shneiderman

NetLens: Iterative Exploration of Content-Actor Network Data
      Hyunmo Kang, Catherine Plaisant*, Bongshin Lee, Benjamin B. Bederson

A Visual Interface for Multivariate Temporal Data:
Finding Patterns of Events across Multiple Histories
      Jerry Fails, Amy Karlson, Layla Shahamat, Ben Shneiderman*

Oct 9, 2006 Vis and InfoVis presentation practice

Presented By Various

Comments Graphics Seminar Series
Held in AVW 3258

Abstract
The papers to be presented are:

Saliency-guided Enhancement for Volume Visualization
      Youngmin Kim* and Amitabh Varshney

Balancing Systematic and Flexible Exploration of Social Networks
      Adam Perer* and Ben Shneiderman

Network Visualization by Semantic Substrates
      Ben Shneiderman* and Aleks Aris

Oct 2, 2006 3D Segmentation and its applications for quantifying the organization of cells in tissue genes in nuclei

Presented By Stephen Lockett, Image Analysis Laboratory at NCI-Fredrick

Comments Graphics Seminar Series

Abstract
Communications between neighboring cells in large part drive tissue development and function, as well as disease-related processes such as tumorigenesis. In order to understand the molecular basis of these processes, it is necessary to quantitatively analyze specific molecules in adjacent individual cells or cell nuclei of intact tissue. A major bottleneck preventing widespread use of such analyses is the lack of an efficient method that correctly segments all individual, whole cells in intact tissue samples. Consequently, we have developed semi-interactive software for segmenting each individual cell or cell nucleus from 3D microscope images of tissue labeled with a fluorescent cell surface or nuclear marker. The dynamic programming-based algorithms have been tested on a variety of biological tissue samples and accurately detected virtually 100% of cells including irregularly shaped cells containing concavities.

We demonstrate how segmentation of cells in tissue and cell culture samples, coupled with feature measurement, feature classification and spatial statistical analysis can be utilized in two biology studies. The first study analyzed cell-to-cell genetic variability in breast cancer, and additionally detects evidence of clonal outgrowths in tumors. The second study analyzed the in-situ positioning specific DNA sequences leading to further understanding the relationship between gene locations and gene expression in interphase nuclei.
Sept 15, 2006 A Fast k-Neighborhood Algorithm for Large Point-Clouds

Presented By Jagan Sankaranarayanan, University of Maryland, College Park

Comments Graphics Seminar Series

Abstract
Joint work with Hanan Samet and Amitabh Varshney.

Algorithms that use point-cloud models make heavy use of the neighborhoods of the points. These neighborhoods are used to compute the surface normals for each point, mollification, and noise removal. All of these primitive operations require the seemingly repetitive process of finding the k nearest neighbors of each point. These algorithms are primarily designed to run in main memory. However, rapid advances in scanning technologies have made available point-cloud models that are too large to fit in the main memory of a computer. This calls for more efficient methods of computing the k nearest neighbors of a large collection of points many of which are already in close proximity. A fast k nearest neighbor algorithm is presented that makes use of the locality of successive points whose k nearest neighbors are sought to significantly reduce the time needed to compute the neighborhood needed for the primitive operation as well as enable it to operate in an environment where the data is on disk. Results of experiments demonstrate one order of improvement in the time to perform the algorithm and several orders of improvement in work efficiency when compared with a prominent existing method.

Proceedings of the IEEE/Eurographics Symposium on Point-Based Graphics (PBG 2006), July 2006, 75--84, Boston, MA.
Sept 18, 2006 Isosurface Extraction and Spatial Filtering Using Persistent Octree

Presented By Qingmin Shi, University of Maryland, College Park

Comments Graphics Seminar Series

Abstract
We propose a novel Persistent OcTree (POT) indexing structure for accelerating isosurface extraction and spatial filtering from volumetric data. This data structure efficiently handles a wide range of visualization problems such as the generation of view-dependent isosurfaces, ray tracing, and isocontour slicing for high dimensional data. POT can be viewed as a hybrid data structure between the interval tree and the Branch-On-Need Octree (BONO) in the sense that it achieves the asymptotic bound of the interval tree for identifying the active cells corresponding to an isosurface and is more efficient than BONO for handling spatial queries. We encode a compact octree for each isovalue. Each such octree contains only the corresponding active cells, in such a way that the combined structure has linear space. The inherent hierarchical structure associated with the active cells enables very fast filtering of the active cells based on spatial constraints. We demonstrate the effectiveness of our approach by performing view-dependent isosurfacing on a wide variety of volumetric data sets and 4D isocontour slicing on the time-varying Richtmyer-Meshkov instability dataset.
Sept 11, 2006 Surgical Simulation: Technology, Research, and Practice

Presented By Alan Liu, Surgical Simulation Laboratory, National Capital Area Medical Simulation Center (SimCen)

Comments Graphics Seminar Series

Abstract
Surgical simulation has traditionally used an apprenticeship model. Skills are acquired and improved while performing actual procedures. Demands on patient safety and the increased complexity of modern surgical techniques are straining this learning model. Simulators provide a safe, effective environment for acquiring and improving surgical skills, and for rehearsing difficult procedures. This talk will examine current research issues in the development of surgical simulators. Both experimental and commercially available systems will be described. The use of simulation for medical training at the National Capital Area Medical Simulation Center (SimCen) will be highlighted. The SimCen's planned development of a very large CAVE environment for mass-casualty/triage simulation will also be discussed.

About the NCA Medical Simulation Center:
The SimCen focuses on the use and development of simulation for medical education. The SimCen has one of the largest arrays of computer-based simulators actively used for surgical and medical training. The SimCen developed two new needle-based simulators that are first-in-kind: Pericardiocentesis and Diagnostic Peritoneal Lavage. The SimCen also conducted the nation's first Advanced Trauma Life Support (ATLS) course using computer-based simulators, computer-controlled mannequins, and medical models instead of animals.

About the speaker:
Alan Liu is the Director of Virtual Medical Environments at the SimCen. He is involved in defining research directions and technical infrastructure, and has developed surgical simulators to support the education and training objectives of the simulation center. Dr. Liu received his Ph.D. in Computer Science from the University of North Carolina at Chapel Hill.

  Old Seminars

2007(Spring/Fall)

2006(Spring/Fall)

2005

2004

2003

2002(Summer/Spring/Fall)

2001

Top

Dec 4, 2006	TBA
Presented By	Jin Hyuk Jung, University of Maryland, College Park
Comments	Graphics Seminar Series
Abstract	A central computation in solving minimizaton problems is finding a search direction that can be used to lower the function value. In Interior Point Methods (IPMs) for linear programming, for example, we compute the direction by solving the normal equations $\mathbf{A}\mathbf{D}\mathbf{A} ^T\Delta\mathbf{x} = \mathbf{r}$, where $\mathbf{A}$ is an $m \times n$ matrix, $\mathbf{D}$ is an $n \times n$ diagonal matrix, and $\Delta\mathbf{x}$ and $\mathbf{r}$ are column vectors. To solve these equations, we need to form the matrix and compute its Cholesky factor, which is a lower triangular matrix. For efficiency we should exploit the symmetry of the matrix. In this work we present efficient algorithms for assembling and factoring the matrix using triangular rasterization on a GPU. Since the matrix is symmetric, only its lower triangular part needs to be computed. So we reduce computational effort by half by computing via triangular rasterization. We also use triangular rasterization to implement a Cholesky decomposition algorithm, which performs 95\% faster for large matrices than the LU decomposition (without pivoting) proposed by Galoppo et al. In addition we present efficient GPU algorithms for assembling and decomposing the matrix in a rectangular packed format, which requires only half the storage space, without sacrificing performance. We store the right lower-triangular submatrix in the unused upper left corner by rotating the submatrix by 180 degrees. By rasterizing two triangles simultaneously, we demonstrate that assembling and decomposing the packed matrix can be performed as fast as for the non-packed matrix. In the IPM, assembling and decomposing the matrix are most demanding of computational resources, and support for triangular rasterization is essential in exploiting the symmetric structure of the matrix. This provides one reason for developers of streaming languages targeting GPUs to consider implementing this feature.
Nov 13, 2006	Display Wall and VNode Cluster Overview
Presented By	Derek Juba, University of Maryland, College Park
Comments	Graphics Seminar Series Slides from this talk
Abstract	For this Graphics Lunch I will be giving an intro to the vnode CPU/GPU cluster. This cluster was created as the result of a collaboration between many different faculty members for coupled CPU/GPU computing and visualization. After the intro talk, we'll go over to GVIL where I'll show some demos on the tiled LCD display wall. This talk should be of interest to anyone planning to do research on the cluster, or anyone who's curious about what that giant black panel in AVW 4406 is.
Oct 16, 2006	VAST presentation practice
Presented By	Various
Comments	Graphics Seminar Series Held in AVW 3258
Abstract	The papers to be presented are: D-Dupe: An Interactive Tool for Entity Resolution in Social Networks Mustafa Bilgic, Louis Licamele, Lise Getoor, Ben Shneiderman NetLens: Iterative Exploration of Content-Actor Network Data Hyunmo Kang, Catherine Plaisant, Bongshin Lee, Benjamin B. Bederson A Visual Interface for Multivariate Temporal Data: Finding Patterns of Events across Multiple Histories Jerry Fails, Amy Karlson, Layla Shahamat, Ben Shneiderman*
Oct 9, 2006	Vis and InfoVis presentation practice
Presented By	Various
Comments	Graphics Seminar Series Held in AVW 3258
Abstract	The papers to be presented are: Saliency-guided Enhancement for Volume Visualization Youngmin Kim* and Amitabh Varshney Balancing Systematic and Flexible Exploration of Social Networks Adam Perer* and Ben Shneiderman Network Visualization by Semantic Substrates Ben Shneiderman* and Aleks Aris
Oct 2, 2006	3D Segmentation and its applications for quantifying the organization of cells in tissue genes in nuclei
Presented By	Stephen Lockett, Image Analysis Laboratory at NCI-Fredrick
Comments	Graphics Seminar Series
Abstract	Communications between neighboring cells in large part drive tissue development and function, as well as disease-related processes such as tumorigenesis. In order to understand the molecular basis of these processes, it is necessary to quantitatively analyze specific molecules in adjacent individual cells or cell nuclei of intact tissue. A major bottleneck preventing widespread use of such analyses is the lack of an efficient method that correctly segments all individual, whole cells in intact tissue samples. Consequently, we have developed semi-interactive software for segmenting each individual cell or cell nucleus from 3D microscope images of tissue labeled with a fluorescent cell surface or nuclear marker. The dynamic programming-based algorithms have been tested on a variety of biological tissue samples and accurately detected virtually 100% of cells including irregularly shaped cells containing concavities. We demonstrate how segmentation of cells in tissue and cell culture samples, coupled with feature measurement, feature classification and spatial statistical analysis can be utilized in two biology studies. The first study analyzed cell-to-cell genetic variability in breast cancer, and additionally detects evidence of clonal outgrowths in tumors. The second study analyzed the in-situ positioning specific DNA sequences leading to further understanding the relationship between gene locations and gene expression in interphase nuclei.
Sept 15, 2006	A Fast k-Neighborhood Algorithm for Large Point-Clouds
Presented By	Jagan Sankaranarayanan, University of Maryland, College Park
Comments	Graphics Seminar Series
Abstract	Joint work with Hanan Samet and Amitabh Varshney. Algorithms that use point-cloud models make heavy use of the neighborhoods of the points. These neighborhoods are used to compute the surface normals for each point, mollification, and noise removal. All of these primitive operations require the seemingly repetitive process of finding the k nearest neighbors of each point. These algorithms are primarily designed to run in main memory. However, rapid advances in scanning technologies have made available point-cloud models that are too large to fit in the main memory of a computer. This calls for more efficient methods of computing the k nearest neighbors of a large collection of points many of which are already in close proximity. A fast k nearest neighbor algorithm is presented that makes use of the locality of successive points whose k nearest neighbors are sought to significantly reduce the time needed to compute the neighborhood needed for the primitive operation as well as enable it to operate in an environment where the data is on disk. Results of experiments demonstrate one order of improvement in the time to perform the algorithm and several orders of improvement in work efficiency when compared with a prominent existing method. Proceedings of the IEEE/Eurographics Symposium on Point-Based Graphics (PBG 2006), July 2006, 75--84, Boston, MA.
Sept 18, 2006	Isosurface Extraction and Spatial Filtering Using Persistent Octree
Presented By	Qingmin Shi, University of Maryland, College Park
Comments	Graphics Seminar Series
Abstract	We propose a novel Persistent OcTree (POT) indexing structure for accelerating isosurface extraction and spatial filtering from volumetric data. This data structure efficiently handles a wide range of visualization problems such as the generation of view-dependent isosurfaces, ray tracing, and isocontour slicing for high dimensional data. POT can be viewed as a hybrid data structure between the interval tree and the Branch-On-Need Octree (BONO) in the sense that it achieves the asymptotic bound of the interval tree for identifying the active cells corresponding to an isosurface and is more efficient than BONO for handling spatial queries. We encode a compact octree for each isovalue. Each such octree contains only the corresponding active cells, in such a way that the combined structure has linear space. The inherent hierarchical structure associated with the active cells enables very fast filtering of the active cells based on spatial constraints. We demonstrate the effectiveness of our approach by performing view-dependent isosurfacing on a wide variety of volumetric data sets and 4D isocontour slicing on the time-varying Richtmyer-Meshkov instability dataset.
Sept 11, 2006	Surgical Simulation: Technology, Research, and Practice
Presented By	Alan Liu, Surgical Simulation Laboratory, National Capital Area Medical Simulation Center (SimCen)
Comments	Graphics Seminar Series
Abstract	Surgical simulation has traditionally used an apprenticeship model. Skills are acquired and improved while performing actual procedures. Demands on patient safety and the increased complexity of modern surgical techniques are straining this learning model. Simulators provide a safe, effective environment for acquiring and improving surgical skills, and for rehearsing difficult procedures. This talk will examine current research issues in the development of surgical simulators. Both experimental and commercially available systems will be described. The use of simulation for medical training at the National Capital Area Medical Simulation Center (SimCen) will be highlighted. The SimCen's planned development of a very large CAVE environment for mass-casualty/triage simulation will also be discussed. About the NCA Medical Simulation Center: The SimCen focuses on the use and development of simulation for medical education. The SimCen has one of the largest arrays of computer-based simulators actively used for surgical and medical training. The SimCen developed two new needle-based simulators that are first-in-kind: Pericardiocentesis and Diagnostic Peritoneal Lavage. The SimCen also conducted the nation's first Advanced Trauma Life Support (ATLS) course using computer-based simulators, computer-controlled mannequins, and medical models instead of animals. About the speaker: Alan Liu is the Director of Virtual Medical Environments at the SimCen. He is involved in defining research directions and technical infrastructure, and has developed surgical simulators to support the education and training objectives of the simulation center. Dr. Liu received his Ph.D. in Computer Science from the University of North Carolina at Chapel Hill.