 |
 |
|
|
|
|
| Title: |
Israel SIGGRAPH Professional Chapter Meeting |
|
|
| Date: |
July 18, 2008 |
| Place: |
Arazi-Ofer Building, Room CL03, Inter-Disciplinary Center, Herzeliya |
| Chair: |
Zachi Karni, Technion |
|
|
 |
|
|
|
Sponsored by:   |
|
|
| Abstracts |
|
 |
Straight Skeletons of Three-Dimensional Polyhedra |
| |
We study the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned) voxels. We analyze the ways in which the skeleton may intersect each voxel of the polyhedron, and show that the skeleton may be constructed by a simple voxel-sweeping algorithm taking constant time per voxel. In addition, we describe a more complex algorithm for straight skeletons of voxel-based polyhedra, which takes time proportional to the area of the surfaces of the straight skeleton rather than the volume of the polyhedron. We also consider more general polyhedra with axis-parallel edges and faces, and show that any n-vertex polyhedron of this type has a straight skeleton with O(n2) features. We provide algo-rithms for constructing the straight skeleton, with running time O(min(n2logn,klogO(1)n)), where k is the output complexity. Next, we discuss the straight skeleton of a general nonconvex polyhedron. We show that it has an ambiguity issue, and suggest a consistent method to resolve it. We prove that the straight skeleton of a general polyhedron has a superquadratic complexity in the worst case. Thus, we show that straight skeletons are strictly simpler for orthogonal polyhedra than they are for more general polyhedra. Finally, we report on an implementation of a simple algorithm for the general case.
Joint work with Gill Barequet, D. Eppstein, and Michael T. Goodrich |
| |
back to top |
 |
| |
|
 |
Target localization errors in landmark based rigid registration: a worst-case analysis |
| |
Landmark-based rigid-body registration is the method of choice for aligning a preoperative image with intra-operative physical anatomy in existing image-guided surgery systems. The registration transformation aims at minimizing the Target Registration Error (TRE), which is the discrepancy between the image and the physical targets locations. The TRE cannot be measured directly for targets inside the anatomy, and instead, the landmarks Root Mean Square (RMS) distance, called Fiducial Registration Error (FRE), or Fitzpatrick TRE (F-TRE) estimate are used. Previously presented artificial examples and clinical observations show that the FRE and the F-TRE values may differ significantly from the actual TRE, but the low relation between the measurements is not formally justified or explained. In this paper, we describe a mechanism and a theorem that explains and formally justifies the potential low relation between the different error measurements. The mechanism is described as a custom function that deforms the landmarks localization error such that the registration is resulted with exactly any predefined FRE or F-TRE value, but the TRE remains constant. Our findings support and generalize the previous observations and surface the need for better TRE estimators and methods for its minimization.
Joint work with Leo Joskowicz |
| |
back to top |
 |
| |
|
|
Edge-Preserving Decompositions for Multi-Scale Tone and Detail Manipulation |
| |
Many recent computational photography techniques decompose an image into a piecewise smooth base layer, containing large scale variations in intensity, and a residual detail layer capturing the smaller scale details in the image. In many of these applications, it is important to control the spatial scale of the extracted details, and it is often desirable to manipulate details at multiple scales, while avoiding visual artifacts. In this work we introduce a new way to construct edge-preserving multi-scale image decompositions. We show that current base-detail decomposition techniques, based on the bilateral filter, are limited in their ability to extract detail at arbitrary scales. Instead, we advocate the use of an alternative edge-preserving smoothing operator, based on the weighted least squares optimization framework, which is particularly well suited for progressive coarsening of images and for multi-scale detail extraction. After describing this operator, we show how to use it to construct edge-preserving multi-scale decompositions, and compare it to the bilateral filter, as well as to other schemes. Finally, we demonstrate the effectiveness of our edge-preserving decompositions in the context of LDR and HDR tone mapping, detail enhancement, and other applications.
Joint work with Zeev Farbman, Raanan Fattal, and Rick Szeliski |
| |
back to top |
|
| |
|
|
Three examples of nonlinear subdivision schemes in geometric modeling |
| |
Subdivision schemes are efficient computational methods for the de-sign, representation and approximation of 2D and 3D curves, and of surfaces of arbitrary topology in 3D. Subdivision schemes generate curves/surfaces from discrete data by repeated refinements. While these methods are simple to implement, their analysis is rather com-plicated even in the linear case. The talk presents three examples of nonlinear subdivision schemes, which depend on the geometry of the data, and which are extensions of univariate linear schemes. The first two are schemes refining control points and generating curves. The last is a scheme refining curves in a geometry-dependent way, and generating surfaces. The computation and the analysis of the different schemes will be discussed, and their performance will be demonstrated. |
| |
back to top |
|
| |
|
|
Linear Parametric Model for Geometric Uncertainty: points, lines, and their relative positioning |
| |
Characterizing geometric uncertainty is a central problem in many fields such as mechanical CAD/CAM, robotics, and computer vision. Geometric uncertainty is usually studied with models that assume independent, isocentric, and isotropic geometric errors. These models fail to capture many real-life situations and may lead to erroneous conclusions. In this paper, we introduce the Linear Parametric Geome-tric Uncertainty Model (LPGUM) and derive the worst-case uncertainty zones of basic geometric entities. The model is general and ex-pressive, allows for parameter dependencies typical of design specifi-cations and metrology measurements, and is useful to study a wide variety of basic geometric problems. We present the LPGUM of a point and a line in the plane and describe their properties. We study the relative positioning of uncertain points and lines and derive their prop-erties. In most cases the geometric complexity is low-polynomial in the number of dependent parameters. We present efficient algorithms to compute the uncertainty zones and answer relative position queries.
Joint work with L. Joskowicz |
| |
back to top |
|
| |
|
|
Improved Seam Carving for Video Retargeting |
| |
Video, like images, should support content aware resizing. We present video retargeting using an improved seam carving operator. Instead of removing 1D seams from 2D images we remove 2D seam manifolds from 3D space-time volumes. To achieve this we replace the dynamic programming method of seam carving with graph cuts that are suitable for 3D volumes. In the new formulation, a seam is given by a minimal cut in the graph and we show how to construct a graph such that the resulting cut is a valid seam. That is, the cut is monotonic and connected. In addition, we present a novel energy criterion that improves the visual quality of the retargeted images and videos. The original seam carving operator is focused on removing seams with the least amount of energy, ignoring energy that is introduced into the images and video by applying the operator. To counter this, the new criterion is looking forward in time - removing seams that introduce the least amount of energy into the retargeted result. We show how to encode the improved criterion into graph cuts (for images and video) as well as dynamic programming (for images). We apply our technique to images and videos and present results of various applications.
Joint work with Michael Rubinstein and Shai Avidan |
| |
back to top |
|
|
|
 |
|
 |
|
Phone: +972 4 8294906