Ефикасна паралелна компресија поља висина

Abstract

Дисертација предлаже нову методу за брзу компресију и декомпресију правилних поља висина, са или без губитака. Правилна поља висина су најчешће усвојен начин представљања површи узоркованих на правилним растојањима дуж две осе картезијанског координатног система у хоризонталној равни. Захваљујући напретку у техници детекције на даљину (енг. remote sensing) у протеклој деценији, која је достигла хоризонталне и вертикалне резолуције узорковања реда метра и дециметра, респективно, потребан је значајан простор за смештање описа површи реалних терена. При наведеним резолуцијама, површ неке планете величине Земље захтева неколико десетина терабајта. Компресија поља висина је потребна не само за компактно смештање, већ и за ефикасан пренос и манипулацију тако великим количинама података. Развијена метода погодна је за SIMD паралелну имплементацију, па самим тим и за архитектуре модерних графичких процесора, који значајно надмашују централни процесор у брзини рачунања, а већ су доступни у кућним рачунарима. Компресија са губицима постиже се апроксимацијом поља висина скупом квадратних Безјеових површи. Безјеове површи су изабране зато што су релативно једноставне за рачунање и поседују неколико пожељних особина, које су од суштинског значаја за примену предложене методе у инжењерству. Компресија без губитака постиже се додавањем два слоја резидуала на апроксимацију. Додатно, предлаже се опциони паралелни алгоритам, специјализован за компресију резидуала. Могућност додатне примене овог алгоритма дозвољава балансирање између степена компресије и брзине декомпресије методе. Предложену методу одликују јединствене особине, које нису присутне ни у једној другој методи компресије поља висина. Метода омогућава независну декомпресију појединачних тачака, као и прогресивну декомпресију. Чак и у случају декомпресије са губицима, декомпримована површ је инхерентно без пукотина. У поређењу са савременим компетитивним методама, које се извршавају на GPU (графичком процесору), предложена метода, у комбинацији са II широко распрострањеном општенаменском методом компресије без губитака (попут DEFLATE, која се користи у популарном алату за компресију података ZIP), или комбинована са специјализованом методом за компресију резидуала без губитака, постиже поредиве степене компресије. Ефикасност методе потврђена је кроз CUDA имплементацију алгоритама компресије и декомпресије. Имплементација основне методе (без додатне компресије резидуала), по цену разумно мањег степена компресије, благо надмашује брзину савремене компетитивне методе за велика оптерећења и значајно за мала, остварујући све горе наведене јединствене карактеристике...

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...