PhD thesis research (2004 - 2010)

Optimal triangulations in plane, terrain and space

2.5D

- image reconstruction, minification, magnification

- detailization

- virtual reality: panoramas, generation of Level Of Detail textures

- multitexturing

- reverse engineering

- data compression

- ...

3D

- medical informatics contribution

- compression

- hierarchical decomposition

- collision and mesh deformation

- faster global illumination computing

- ...

nD

- reconstruction of physical (geographical, meteorological, biological) multidimensional data

In present I focus on special subgroup of optimal triangulations called data dependent triangulation introduced by Nira Dyn in 1991. These triangulations allow the generation of "long" and "tiny" triangles which are suitable for feature preserving, fitting. Each vertex holds a data value, and the goal is to reconstruct the underlying function from these discrete samples. This research is done under the supervision of doc. RNDr. Andrej Ferko, PhD. (at Department of Algebra, Geometry and Didactics of Mathematics, Faculty of Mathematics, Physics and Informatics Comenius University) and with a cooperation of members from Vienna University of Technology, Institute of Computer Graphics and Algorithms. Except of feature preserving triangulations the selection of the quality preserving function is also important. These functions describe how the important features are represented in the data.

Results from trilinear interpolation (left), and from our 3D DDT approach (right). (results are converted into png format, cause the speed restrictions)

Appropriate tools are necessary for quality measurement in each application area (for example for application area of image reconstruction for measuring of radiometric quality are used perceptual metrics). Their design as the determination of the optimum means improvement towards an optimal reconstruction. In other words, it is possible to separate heuristics from the cost functions, and consider them as relatively independent layers.

The existing numerical techniques and the solutions from image processing field doesn’t yield as strong feature preserving property as our approach, which is based on the generalization of data-dependent triangulations.

Publications

Tóth Zs. Triangulácie v rovine, teréne a priestore. Dissertation Thesis, Bratislava SR, 2010.
Supervisor doc. RNDr. Andrej Ferko, PhD.

Abstract: This thesis deals with a special subset of optimal triangulations, called data dependent triangulations. This technique has wide usability because of its properties. The main goal is the investigation of the reconstruction behavior of this method, and the approximation of the globally optimal solution, which is NP-hard to find. The thesis contains the summarization of the existing approaches and introduces several improvements and extensions. The main contributions are the following: extension of the data dependent technique for n-dimensional usage; a parallel approach, which uses the graphics hardware for the locally optimal triangulations generation. Besides of these results there are several improvements presented for the planar data dependent triangulations. For image reconstruction usage is presented an approach which combines the results of the convolution techniques with the results from the data dependent methods. A concept for a multidimensional scattered data compression is also introduced. The results are analyzed from different points of view, and several future work ideas are presented.

download the thesis download the shortened version download the presentation

Cervenanský M., Tóth Zs., Starinský J., Ferko A., Šrámek M.: Parallel GPU-based data-dependent triangulations, Computers & Graphics, Volume 34, Issue 2, April 2010, ISSN 0097-8493, pp. 125-135.

Abstract: In this paper we introduce a new technique for data-dependent triangulation which is suitable for implementation on a GPU. Our solution is based on a new parallel version of the well known Lawson’s optimization process and is fully compatible with restrictions of the GPU hardware. We test and compare the quality of our solution in an image reconstruction problem. In comparison with the standard implementations we achieve significant speed-up (eight times on average) with comparable quality of the reconstructed image. Further, several other improvements and optimizations are introduced and tested, and the results are discussed in detail.

link to the paper

Tóth Zs., Viola I., Ferko A., Gröller M. E.: N-dimensional Data-Dependent Reconstruction Using Topological Changes. In Topology-Based Methods in Visualization. Springer Mathematics + Visualization Series. Editors: Hauser H., Hagen H., Theisel H. 2007, ISBN-I3 978-3-540-70822-3, pp. 183-198.

Abstract: We introduce a new concept for a geometrically based feature preserving reconstruction technique of n-dimensional scattered data. Our goal is to generate an n-dimensional triangulation, which preserves the high frequency regions via local topology changes. It is the generalization of a 2D reconstruction approach based on data-dependent triangulation and Lawson‘s optimization procedure. The definition of the mathematic optimum of the reconstruction is given. We discuss an original cost function and a generalization of known functions for the n-dimensional case.

download the paper

Tóth Zs. Illustration of data dependent triangulation reconstruction technique Animations of Computer Graphics exhibition in Proceedings of Spring Conference on Computer Graphics 2006, Castá-Papiernicka, ISSN 1335-5694, pp. 104.

The next animation shows the workflow of data dependent triangulation technique for image reconstrucion purpose. It converts digital image into feature preserving triangular mesh. This kind of triangulation allows the generation of inevitable long and tiny triangles to preserve high-frequency features. The image data is resampled on the base of this mesh. On the displayed example (second animation) we can clearly see how this technique improves the mesh from the inital triangulation structrure to be able to fit the underlying data. These animations were created for illustration of this technique, as a part of our research work done in this field.

download the animation

Tóth Zs. Towards an Optimal Texture Reconstruction, CESCG 2000-2005 Best Paper Selection, Österreichische Computer Gesellschaft Wien, 2006, ISBN 3-85403-204-8, pp. 197-212.

Abstract: Visually pleasant texture reconstruction plays an important role in computer graphics. In this paper we propose special triangulations for texture reconstruction. We introduce two new algorithms for data-dependent triangulation. The new deterministic algorithm named image partitioning algorithm (IPA) shifts this reconstruction method closer to real usage. We present a new modification of the optimization technique simulated annealing with generalized look-ahead process (SALA). Also a new way of utilization of color information is presented. It supports achieving qualitative way of reconstruction of color images. Results obtained demonstrate both theoretical and practical superiority over another methods. This work is a part of the Virtual Bratislava research.

download the paper

Tóth Zs. Triangulácie v rovine, teréne a priestore. Project of dissertation, Bratislava SR, 2006.
Supervisor doc. RNDr. Andrej Ferko, PhD.

Abstrakt: V tejto práci prezentujeme preh¾ad geometricky založenej techniky, ktorá zachováva významné èrty v dátach a je nazývaná dátovo závislá triangulácia. Sú tu predstavené dva nové deterministické prístupy, ktoré majú za úlohu posunú� túto metóodu bližšie k reálnemu použitiu. Ponúkame modifikáciu optimalizaèného prístupu simulovaného žíhania v kombinácii s look-ahead prístupom. Hlavným prínosom je rozšírenie dátovo závislej techniky na rekonštrukciu n-dimenzionálnych dát. Naším cie¾om je generovanie n-dimenzionálnej triangulácie, ktorá zachováva vysokofrekvenèné oblasti pomocou topolóogických zmien. Je to zovšeobecnenie 2D prístupu založeného na dátovo závislých trianguláciách a Lawsonovho optimalizaèného procesu. Predstavíme novú cenovú funkciu a zovšeobecnenie existujúcich cenových funkcií n-dimenzií. Na záver uvedieme možnosti ïalšieho výskumu ako projekt dizertaènej práce.

download the thesis

Tóth Zs. Dátovo závislé triangulácie. Rigorous thesis, Comenius University, Bratislava SR, 2005.
Supervisor doc. RNDr. Andrej Ferko, PhD.

More material for this publication is not aviable.

Publications

Tóth Zs. Rekonštrukcia obrazu pomocou triangulácie. MSc thesis, Comenius University, Bratislava SR, 2004.
Supervisor doc. RNDr. Andrej Ferko, PhD.

Abstrakt: Vizuálne príjemná rekonštrukcia obrazov zohráva dôlezitú úlohu v pocítacovej grafike. V tejto práci je skúmaná vyuzitelnost triangulácií na rekonštrukciu obrazov. Sú uvedené dva nové algoritmy na vytváranie dátovo závislých triangulácií. Nový deterministický algoritmus pomenovaný ako IPA (image partitioning algorithm) posunie túto rekonštrukcnú metódu blizšie ku praktickej vyuzitelnosti. Je uvedená nová modifikácia optimalizacnej techniky - simulované zíhanie, pomenované ako SALA, ktorá vyuzíva look-ahead techniku. Je popísaná nová skupina metód - kvázi-dátovo závislé triangulácie, ktoré len v casti vyuzívajú dátovú závislost. Prezentovaný je aj nový spôsob vyuzitia farebných informácií na dosiahnutie kvalitnejšieho priebehu rekonštrukcií farebných obrázkov. Výsledky vykazujú teoretickú a praktickú prevahu nad inými metódami. Táto práca je castou APVT projektu Virtual Bratislava.

download the thesis - in Slovak language

download the contents - in English language

Tóth Zs. Towards an Optimal Texture Reconstruction. Central European Seminar on Computer Graphics 2004 (Budmerice, SR), 2004, pp. 23-30.

Abstract: Visually pleasant texture reconstruction has important role in computer graphics. In this paper we explore the applicability of triangulations for texture reconstruction. Two new algorithms are introduced for generation of data-dependent triangulation. The new deterministic algorithm entitled as image partitioning algorithm (IPA) shifts this reconstruction method closer to real usage. We present a new modification of the optimization technique simulated annealing with generalized look-ahead process (SALA). Also a new way of utilization of color information is presented, to achieve qualitative course of reconstruction of color images. Results show both theoretical and practical superiority over another methods. This work is a part of the APVT project Virtual Bratislava.

download the paper

Tóth Zs. Image Reconstruction Using Triangulations. Študentská vedecká konferencia FMFI UK 2004 (Bratislava, SR), 2004.

More material for this publication is not aviable.