Title
Ефикасна паралелна компресија поља висина
Creator
Đurđević, Đorđe, 1976-
Copyright date
2013
Object Links
Select license
Autorstvo-Nekomercijalno-Deliti pod istim uslovima 3.0 Srbija (CC BY-NC-SA 3.0)
License description
Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odredjen od strane autora ili davaoca licence i ako se prerada distribuira pod istom ili sličnom licencom. Ova licenca ne dozvoljava komercijalnu upotrebu dela i prerada. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc-sa/3.0/rs/deed.sr_LATN Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc-sa/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Theses Type
Doktorska disertacija
description
Датум одбране: 24.04.2013.
Other responsibilities
mentor
Tartalja, Igor, 1959-
član komisije
Jovanović, Zoran, 1974-
član komisije
Starčević, Dušan, 1949-
član komisije
Tomašević, Milo, 1957-
član komisije
Prokin, Milan, 1963-
Academic Expertise
Tehničko-tehnološke nauke
University
Univerzitet u Beogradu
Faculty
Elektrotehnički fakultet
Alternative title
Efficient parallel compression of height fields
Publisher
[Ђ. Ђурђевић]
Format
PDF/A (121 list)
description
Електротехника и рачунарство - Рачунарска техника и информатика / Electrical and Computer Engineering - Computer and Software Engineering
Abstract (sr)
Дисертација предлаже нову методу за брзу компресију и декомпресију правилних
поља висина, са или без губитака. Правилна поља висина су најчешће усвојен
начин представљања површи узоркованих на правилним растојањима дуж две осе
картезијанског координатног система у хоризонталној равни. Захваљујући
напретку у техници детекције на даљину (енг. remote sensing) у протеклој
деценији, која је достигла хоризонталне и вертикалне резолуције узорковања реда
метра и дециметра, респективно, потребан је значајан простор за смештање описа
површи реалних терена. При наведеним резолуцијама, површ неке планете
величине Земље захтева неколико десетина терабајта. Компресија поља висина је
потребна не само за компактно смештање, већ и за ефикасан пренос и
манипулацију тако великим количинама података. Развијена метода погодна је за
SIMD паралелну имплементацију, па самим тим и за архитектуре модерних
графичких процесора, који значајно надмашују централни процесор у брзини
рачунања, а већ су доступни у кућним рачунарима.
Компресија са губицима постиже се апроксимацијом поља висина скупом
квадратних Безјеових површи. Безјеове површи су изабране зато што су
релативно једноставне за рачунање и поседују неколико пожељних особина, које
су од суштинског значаја за примену предложене методе у инжењерству.
Компресија без губитака постиже се додавањем два слоја резидуала на
апроксимацију. Додатно, предлаже се опциони паралелни алгоритам,
специјализован за компресију резидуала. Могућност додатне примене овог
алгоритма дозвољава балансирање између степена компресије и брзине
декомпресије методе.
Предложену методу одликују јединствене особине, које нису присутне ни у једној
другој методи компресије поља висина. Метода омогућава независну
декомпресију појединачних тачака, као и прогресивну декомпресију. Чак и у
случају декомпресије са губицима, декомпримована површ је инхерентно без
пукотина. У поређењу са савременим компетитивним методама, које се
извршавају на GPU (графичком процесору), предложена метода, у комбинацији са
II
широко распрострањеном општенаменском методом компресије без губитака
(попут DEFLATE, која се користи у популарном алату за компресију података
ZIP), или комбинована са специјализованом методом за компресију резидуала без
губитака, постиже поредиве степене компресије. Ефикасност методе потврђена је
кроз CUDA имплементацију алгоритама компресије и декомпресије.
Имплементација основне методе (без додатне компресије резидуала), по цену
разумно мањег степена компресије, благо надмашује брзину савремене
компетитивне методе за велика оптерећења и значајно за мала, остварујући све
горе наведене јединствене карактеристике...
Abstract (en)
This thesis presents a novel method for fast lossy or lossless compression and
decompression of regular height fields. Regular height fields are a commonly adopted
solution for representing surfaces sampled at uniform rates along the two Cartesian axes
in the horizontal plane. Due to the improvements in the remote sensing technology
during the last decade, which has reached horizontal and vertical sampling resolutions
of the order of a meter and a decimeter, respectively, significant storage space is needed
for the surface of real terrains. At these resolutions, the surface of a planet of the size
similar to Earth requires a few dozens of terabytes of storage space. Compression of
height fields is needed not only for efficient storage, but also for efficient transfer and
manipulation of such large amounts of data. The developed method is suitable for SIMD
parallel implementation and thus inherently suitable for modern GPU architectures,
which significantly outperform modern CPUs in computation speed, and are already
present in home computers.
Lossy compression is achieved by approximating the height field with a set of quadratic
Bezier surfaces. Bezier surfaces have been chosen because they are relatively simple to
compute and have several desirable features, essential for the application of the method
in engineering. Lossless compression is achieved by superimposing two layers of
residuals over the lossy approximation. In addition, an optional parallel algorithm,
specialized for compression of residuals is proposed. The possibility of additional
application of this algorithm allows for a tradeoff between the compression ratio and the
decompression speed of the method.
The proposed method is characterized with unique properties, which are not present in
any of the height field compression methods. The method allows independent
decompression of individual data points, as well as progressive decompression. Even in
the case of lossy decompression, the decompressed surface is inherently seamless. In
comparison with the GPU-oriented competitive state-of-the-art method, the proposed
method, combined with a widely available general purpose lossless compression
method (such as DEFLATE, used in the popular ZIP data compression utility), or
combined with a specialized method for lossless compression of the residuals, achieves
IV
comparable compression ratios. The method's efficiency was confirmed through a
CUDA implementation of compression and decompression algorithms. The
implementation of the basic method (without additional compression of residuals), at
the expense of reasonably worse compression ratio, slightly outperforms the
competitive state-of-the-art method for very high workloads and considerably for lower
workloads, achieving all of the above mentioned unique features...
Authors Key words
Vizuelizacija terena
Type
Tekst
Abstract (sr)
Дисертација предлаже нову методу за брзу компресију и декомпресију правилних
поља висина, са или без губитака. Правилна поља висина су најчешће усвојен
начин представљања површи узоркованих на правилним растојањима дуж две осе
картезијанског координатног система у хоризонталној равни. Захваљујући
напретку у техници детекције на даљину (енг. remote sensing) у протеклој
деценији, која је достигла хоризонталне и вертикалне резолуције узорковања реда
метра и дециметра, респективно, потребан је значајан простор за смештање описа
површи реалних терена. При наведеним резолуцијама, површ неке планете
величине Земље захтева неколико десетина терабајта. Компресија поља висина је
потребна не само за компактно смештање, већ и за ефикасан пренос и
манипулацију тако великим количинама података. Развијена метода погодна је за
SIMD паралелну имплементацију, па самим тим и за архитектуре модерних
графичких процесора, који значајно надмашују централни процесор у брзини
рачунања, а већ су доступни у кућним рачунарима.
Компресија са губицима постиже се апроксимацијом поља висина скупом
квадратних Безјеових површи. Безјеове површи су изабране зато што су
релативно једноставне за рачунање и поседују неколико пожељних особина, које
су од суштинског значаја за примену предложене методе у инжењерству.
Компресија без губитака постиже се додавањем два слоја резидуала на
апроксимацију. Додатно, предлаже се опциони паралелни алгоритам,
специјализован за компресију резидуала. Могућност додатне примене овог
алгоритма дозвољава балансирање између степена компресије и брзине
декомпресије методе.
Предложену методу одликују јединствене особине, које нису присутне ни у једној
другој методи компресије поља висина. Метода омогућава независну
декомпресију појединачних тачака, као и прогресивну декомпресију. Чак и у
случају декомпресије са губицима, декомпримована површ је инхерентно без
пукотина. У поређењу са савременим компетитивним методама, које се
извршавају на GPU (графичком процесору), предложена метода, у комбинацији са
II
широко распрострањеном општенаменском методом компресије без губитака
(попут DEFLATE, која се користи у популарном алату за компресију података
ZIP), или комбинована са специјализованом методом за компресију резидуала без
губитака, постиже поредиве степене компресије. Ефикасност методе потврђена је
кроз CUDA имплементацију алгоритама компресије и декомпресије.
Имплементација основне методе (без додатне компресије резидуала), по цену
разумно мањег степена компресије, благо надмашује брзину савремене
компетитивне методе за велика оптерећења и значајно за мала, остварујући све
горе наведене јединствене карактеристике...
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.