You are here

A robust and efficient tool for the formation of 2D images

Technology Number: 

1799

Principal Investigator

Prof.
Ronen Ezra
Basri

Department: 

Computer Science and Applied Mathematics

Patent Status: 

Pending
Summary 

A new computer graphics tool for the efficient and robust deformation of 2D images was developed by the group of Prof. Lipman.

Space deformation is an important tool in graphics and image processing, with applications ranging from image warping and character animation, to non-rigid registration and shape analysis. Virtually all methods attempt to find maps that possess three key properties: smoothness, injectivity and shape preservation. Furthermore, for the purpose of warping and posing characters, the method should have interactive performance. However, there is no known method that possesses all of these properties.

Previous deformation models can be roughly divided into meshbased and meshless models. Mesh-based maps are predominantly constructed using linear finite elements, and are inherently not smooth, but can be made to look smooth by using highly dense elements. Although the methods for creating maps with controlled distortion exist, they are time-consuming, and dense meshes prohibit their use in an interactive manner. On the other hand, meshless maps are usually defined using smooth bases and hence are smooth themselves. Yet we are unaware of any known technique that ensures their injectivity and/or bounds on their distortion.

The new method presented here bridges the gap between mesh and meshless methods, by providing a generic framework for making any smooth function basis suitable for deformation.

Applications


  • Computer graphics and animation
  • Image registration for medical imaging, satellite imaging and military applications

Advantages


  • Robust, fast, efficient and scalable

  • Generic, can be applied to various scenarios

  • Possesses smoothness, injectivity and shape preservation with interactive performance


Technology's Essence


Deformation od 2D images is accomplished by enabling direct control over the distortion of the Jacobian during optimization, including preservation of orientation (to avoid flips). The method generates maps by constraining the Jacobian on a dense set of ”collocation” points, using an active-set approach. Only a sparse subset of the collocation points needs to be active at every given moment, resulting in fast performance, while retaining the distortion and injectivity guarantees. Furthermore, a precise mathematical relationship between the density of the collocation points, the maximal distortion achieved on them, and the maximal distortion achieved everywhere in the domain of interest is derived.

More technologies in Mathematics and Computer Science