ODETLAP is my technique for approximating terrain and other data by solving an overdetermined sparse set of equations.
(These pages under construction; more info on request).
2016
- Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, Marcus V. A. Andrade, and David L. Hedin.
3D segmented ODETLAP compression.
2016.
[abstract▼] [details] [full text]
[BibTeX▼]
We propose a segmented ODETLAP compression algorithm to increase speed, and show that it is usually better in the maximum absolute error than JP3D for 3D datasets. Overdetermined Laplacian partial differential equations (ODETLAP) is a spatial approximation and data compression method. We use the CUSP library to accelerate ODETLAP approximation and the speedup is about 7 times on a GPU over a CPU core. Segmented ODETLAP compression is faster and uses less memory than unsegmented ODETLAP compression. We use the algorithm to compress several atmospheric datasets and an MRI dataset. For evaluation, we also compress the datasets using JPEG 2000 Part 10 JP3D. The results show that the compressed size of the algorithm is about 60\% that of JP3D for the same maximum absolute error.
@misc{wenli-odetlap-2016,
author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Hedin, David L.",
title = "{3D} Segmented {ODETLAP} Compression",
booktitle = "(unpublished)",
year = "2016",
href = "\bibhref{212-wenli-odetlap-2016}",
mykey = "wenlili marcus salles odetlap"
}
2015
- Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães.
Segmented ODETLAP compression.
In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015.
(extended abstract).
[details] [full text]
[BibTeX▼]
@inproceedings{wenli-segment-fwcg-2015,
author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
title = "Segmented {ODETLAP} Compression",
booktitle = "25th Fall Workshop on Computational Geometry",
year = "2015",
month = "23-24 Oct",
address = "U. Buffalo, New York, USA",
note = "(extended abstract)",
mykey = "wenlili salles odetlap",
href = "\bibhref{202-wenli-segment-fwcg-2015}"
}
- Wenli Li, W. Randolph Franklin, Marcus Andrade, and Salles de Magalhães.
Research summary: siting and ODETLAP.
Talk at CCNY, 15 April 2015.
[details] [slides]
[BibTeX▼]
@misc{wenli-ccny-2015,
author = "Li, Wenli and Franklin, W. Randolph and Andrade, Marcus and de Magalhães, Salles",
title = "Research Summary: Siting and {ODETLAP}",
howpublished = "Talk at CCNY",
month = "15 April",
year = "2015",
mykey = "wenlili marcus salles odetlap",
customlinkslides = "https://wrfranklin.org/p/193-wenli-ccny-2015.pdf",
href = "\bibhreft{193-wenli-ccny-2015.pdf}"
}
2013
- Daniel Benedetti, W. Randolph Franklin, and Wenli Li.
CUDA-accelerated ODETLAP: a parallel lossy compression implementation.
In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013.
(extended abstract).
[abstract▼] [details] [full text] [slides]
[BibTeX▼]
We present an implementation of Overdetermined Laplacian Partial Differentiation Equations (ODETLAP) that uses CUDA directly. This lossy compression technique approximates a solution to an overdetermined system of equations in order to reconstruct gridded, correlated data. ODETLAP can be used to compress a dataset or to reconstruct missing data. Parallelism in CUDA provides speed performance improvements over other implementation methods. ODETLAP is inspired by the Laplacian Partial Differential Equation, though it is capable of preserving local extrema. Typical compression techniques are limited to viewing data as being one dimensional. The ODETLAP algorithm instead utilizes the autocorrelation of data in multiple dimensions to perform compression. This allows for improved compression of higher dimensional datasets, as can be found in geographical and environmental data[1, 2]. ODETLAP requires the construction and solution approximation of a sparse over-determined linear system of equations. As a result, the algorithm is quite compute-intensive. Parallelization techniques offer means of improving performance of this algorithm. The CUDA libraries, Thrust and CUSP, will be utilized in this parallel implementation of ODETLAP The Thrust library provides means for construction of the overdetermined system matrix, while the CUSP library contains solvers for such systems.
@inproceedings{benedetti-fwcg-2013,
author = "Benedetti, Daniel and Franklin, W. Randolph and Li, Wenli",
title = "{CUDA}-Accelerated {ODETLAP}: A Parallel Lossy Compression Implementation",
booktitle = "23rd Fall Workshop on Computational Geometry",
year = "2013",
month = "25--26 Oct",
address = "City College, New York City, USA",
note = "(extended abstract)",
href = "\bibhrefpt{172-fwcg2013-benedetti-cuda-odetlap}{172-fwcg2013-benedetti-cuda-odetlap-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/172-fwcg2013-benedetti-cuda-odetlap-talk.pdf",
mykey = "benedetti wenlili odetlap parallel"
}
- W. Randolph Franklin, You Li, Tsz-Yam Lau, and Peter Fox.
CUDA-accelerated HD-ODETLAP: lossy high dimensional gridded data compression.
In Xuan Shi, Volodymyr Kindratenko, and Chaowei Yang, editors, Modern Accelerator Technologies for Geographic Information Science.
Springer, 2013.
[abstract▼] [details] [full text]
[BibTeX▼]
We present High-dimensional Overdetermined Laplacian Partial Differential Equations (HD-ODETLAP), an algorithm and implementation for lossy compression of high-dimensional arrays of data. HD-ODETLAP exploits autocorrelations in the data in any dimension. It also adapts to regions in the data with varying value ranges, resulting in the maximum error being closer to the RMS error. HD-ODETLAP compresses a data array by iteratively selecting a representative set of points from the array. That set of points, efficiently coded, is the compressed dataset. The compressed dataset is uncompressed by solving an overdetermined sparse system of linear equations for an approximation to the original array. HD-ODETLAP uses NVIDIA CUDA called from MATLAB to exploit GPU parallel processing to achieve considerable speedup compared to execution on a CPU. In addition, HD-ODETLAP compresses much better than JPEG2000 and 3D-SPIHT, when fixing either the average or the maximum error. An application is to facilitate storage and transmission of voluminous datasets for better climatological and environmental analysis and prediction.
@incollection{hdodetlap-2013,
author = "Franklin, W. Randolph and Li, You and Lau, Tsz-Yam and Fox, Peter",
editor = "Shi, Xuan and Kindratenko, Volodymyr and Yang, Chaowei",
title = "{CUDA}-accelerated {HD-ODETLAP}: Lossy high dimensional gridded data compression",
booktitle = "Modern Accelerator Technologies for Geographic Information Science",
year = "2013",
isbn = "978-1-4614-8744-9",
publisher = "Springer",
href = "\bibhref{165-2013-hdodetlap}",
mykey = "youli lau odetlap parallel"
}
2012
- Tsz-Yam Lau and W. Randolph Franklin.
Automated artifact-free seafloor surface reconstruction with two-step ODETLAP (Ph.D. showcase).
In 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012). Redondo Beach, CA, 6–9 Nov 2012.
[details] [full text] [poster]
[BibTeX▼]
@inproceedings{lau-acmgis-2012,
author = "Lau, Tsz-Yam and Franklin, W. Randolph",
title = "Automated artifact-free seafloor surface reconstruction with two-step {ODETLAP} ({Ph.D.} Showcase)",
booktitle = "20th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2012)",
year = "2012",
address = "Redondo Beach, CA",
month = "6--9 Nov",
mykey = "lau odetlap",
customlinkposter = "https://wrfranklin.org/p/160-acmgis2012-seafloor-poster.pdf",
href = "\bibhrefpp{160-acmgis2012-seafloor}{160-acmgis2012-seafloor-poster.pdf}"
}
- W. Randolph Franklin, You Li, Tsz-Yam Lau, and Peter Fox.
CUDA-accelerated HD-ODETLAP: lossy high dimensional gridded data compression.
In 2012 International Workshop on Modern Accelerator Technologies for GIScience (MAT4GIScience 2012). Columbus OH, 18 Sep 2012.
[details] [full text] [slides]
[BibTeX▼]
@inproceedings{giscience-hdodetlap-2012,
author = "Franklin, W. Randolph and Li, You and Lau, Tsz-Yam and Fox, Peter",
title = "{CUDA}-accelerated {HD-ODETLAP}: Lossy high dimensional gridded data compression",
booktitle = "2012 International Workshop on Modern Accelerator Technologies for {GIScience} ({MAT4GIScience} 2012)",
year = "2012",
address = "Columbus OH",
month = "18 Sep",
mykey = "youli lau odetlap",
customlinkslides = "https://wrfranklin.org/p/156-mat4giscience2012-hdodetlap-talk.pdf",
href = "\bibhrefpt{156-mat4giscience2012-hdodetlap}{156-mat4giscience2012-hdodetlap-talk.pdf}"
}
- Tsz-Yam Lau.
Two-step ODETLAP and induced terrain for improved geographical data reconstruction.
PhD thesis, Rensselaer Polytechnic Institute, 2012.
[details] [full text]
[BibTeX▼]
@phdthesis{lau-phd,
author = "Lau, Tsz-Yam",
title = "Two-step {ODETLAP} and induced terrain for improved geographical data reconstruction",
school = "Rensselaer Polytechnic Institute",
mykey = "odetlap hydro lau theses bathy",
year = "2012"
}
- Chris Stuetzle.
Representation and generation of terrain using mathematical modeling.
PhD thesis, Rensselaer Polytechnic Institute, 2012.
[details] [full text]
[BibTeX▼]
@phdthesis{stuetzle-phd,
author = "Stuetzle, Chris",
title = "Representation and generation of terrain using mathematical modeling",
school = "Rensselaer Polytechnic Institute",
mykey = "odetlap theses",
year = "2012"
}
2011
- You Li.
CUDA-accelerated HD-ODETLAP: a high dimensional geospatial data compression framework.
PhD thesis, Rensselaer Polytechnic Institute, 2011.
[details] [full text]
[BibTeX▼]
@phdthesis{li-phd,
author = "Li, You",
title = "{CUDA}-accelerated {HD-ODETLAP}: a high dimensional geospatial data compression framework",
school = "Rensselaer Polytechnic Institute",
mykey = "odetlap youli theses",
year = "2011"
}
2010
- Tsz-Yam Lau and W. Randolph Franklin.
Completing river networks with only partial river observations via hydrology-aware ODETLAP.
In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010). Stony Brook University, Stony Brook, NY 11794, USA, 29–30 Oct 2010.
(extended abstract and talk).
[details] [full text] [slides]
[BibTeX▼]
@inproceedings{lau-fwcg-2010,
author = "Lau, Tsz-Yam and Franklin, W. Randolph",
title = "Completing River Networks with Only Partial River Observations via Hydrology-Aware {ODETLAP}",
booktitle = "20th Annual Fall Workshop on Computational Geometry ({FWCG} 2010)",
month = "29--30 Oct",
year = "2010",
note = "(extended abstract and talk)",
mykey = "lau hydro odetlap",
address = "Stony Brook University, Stony Brook, NY 11794, USA",
customlinkslides = "https://wrfranklin.org/p/138-fwcg2010-lau-talk.pdf",
href = "\bibhrefat{138-fwcg2010-lau}{138-fwcg2010-lau-talk.pdf}"
}
- You Li and W. Randolph Franklin.
4D-ODETLAP: a novel high-dimensional compression method on time-varying geospatial data.
In Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of ISPRS Technical Commission IV & AutoCarto 2010. Orlando, Florida, 15–18 Nov 2010.
[details] [full text] [slides]
[BibTeX▼]
@inproceedings{li-autocarto-2010,
author = "Li, You and Franklin, W. Randolph",
title = "{4D-ODETLAP}: A Novel High-dimensional Compression Method on Time-varying Geospatial Data",
booktitle = "Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of {ISPRS} Technical Commission {IV} \\& {AutoCarto} 2010",
year = "2010",
address = "Orlando, Florida",
mykey = "youli odetlap",
month = "15--18 Nov",
customlinkslides = "https://wrfranklin.org/p/136-autocarto2010-li-talk.pptx",
href = "\bibhrefpt{136-autocarto2010-li}{136-autocarto2010-li-talk.pptx}"
}
- You Li, Tsz-Yam Lau, Chris Stuetzle, Peter Fox, and W. Randolph Franklin.
3D oceanographic data compression using 3D-ODETLAP.
In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010.
(PhD Dissertation showcase).
[details] [full text] [slides]
[BibTeX▼]
@inproceedings{li-acmgis-2010,
author = "Li, You and Lau, Tsz-Yam and Stuetzle, Chris and Fox, Peter and Franklin, W. Randolph",
title = "{3D} oceanographic data compression using {3D-ODETLAP}",
booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)",
year = "2010",
month = "2--5 Nov",
mykey = "youli odetlap lau stuetzle",
address = "San Jose, CA, USA",
customlinkslides = "https://wrfranklin.org/p/139-acmgis2010-li-talk.pptx",
href = "\bibhrefpt{139-acmgis2010-li}{139-acmgis2010-li-talk.pptx}",
note = "(PhD Dissertation showcase)"
}
2009
- Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin.
Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP.
In 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009). Seattle WA USA, 4–6 Nov 2009.
Winner of the best fast forward presentation award.
[details] [full text] [slides] [poster] [video] [award]
[BibTeX▼]
@inproceedings{lau-acmgis-2009,
author = "Lau, Tsz-Yam and Li, You and Xie, Zhongyi and Franklin, W. Randolph",
title = "Sea Floor Bathymetry Trackline Surface Fitting Without Visible Artifacts Using {ODETLAP}",
booktitle = "17th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2009)",
year = "2009",
address = "Seattle WA USA",
month = "4--6 Nov",
note = "Winner of the best fast forward presentation award",
customlinkslides = "https://wrfranklin.org/p/129-acmgis2009-lau-talk.pdf",
customlinkposter = "https://wrfranklin.org/p/129-acmgis2009-lau-poster.pdf",
customlinkvideo = "https://wrfranklin.org/p/129-acmgis2009-lau-video.avi",
customlinkaward = "https://wrfranklin.org/p/129-acmgis2009-lau-ffaward.jpg",
href = "\bibhrefpttppv{129-acmgis2009-lau}",
mykey = "xie youli odetlap bathy lauacmgis2009"
}
- Daniel M. Tracy.
Path Planning and Slope Representation on Compressed Terrain.
PhD thesis, Rensselaer Polytechnic Institute, 2009.
[details] [full text]
[BibTeX▼]
@phdthesis{tracy-phd,
author = "Tracy, Daniel M.",
title = "Path Planning and Slope Representation on Compressed Terrain",
school = "Rensselaer Polytechnic Institute",
mykey = "odetlap theses tracy",
year = "2009"
}
2008
- Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Daniel M. Tracy, and Marcus V.A. Andrade.
Parallel ODETLAP for terrain compression and reconstruction.
In Walid G. Aref, editor, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). 5–7 Nov 2008.
URL: http://acmgis08.cs.umn.edu/.
[abstract▼] [details] [full text] [slides] [poster]
[BibTeX▼]
We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patchbased implementation takes 2 seconds to run ODETLAP on an 800 × 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 × 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors.
@inproceedings{stookey-acmgis-2008,
author = "Stookey, Jared and Xie, Zhongyi and Cutler, Barbara and Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus V.A.",
editor = "Aref, Walid G.",
title = "Parallel {ODETLAP} for terrain compression and reconstruction",
booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
year = "2008",
location = "Irvine CA",
month = "5--7 Nov",
href = "\bibhrefptp{123-acmgis2008-stookey}{123-acmgis2008-stookey-talk.ppt}{123-acmgis2008-stookey-poster.ppt}",
url = "http://acmgis08.cs.umn.edu/",
customlinkslides = "https://wrfranklin.org/p/123-acmgis2008-stookey-talkb.pdf",
customlinkposter = "https://wrfranklin.org/p/123-acmgis2008-stookey-poster.ppt",
mykey = "odetlap tracy marcus xie stuetzle parallel"
}
- Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy.
Evaluating hydrology preservation of simplified terrain representations.
(unpublished), Apr 2008.
[details] [full text]
[BibTeX▼]
@unpublished{muckell-HydroMetric-ODETLAP-2008,
author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
title = "Evaluating Hydrology Preservation of Simplified Terrain Representations",
href = "\bibhref{121-muckell-HydroMetric-ODETLAP-2008}",
note = "(unpublished)",
month = "Apr",
mykey = "odetlap tracy inanc marcus muckell xie hydro",
year = "2008"
}
- Metin Inanc.
Compressing Terrain Elevation Datasets.
PhD thesis, Rensselaer Polytechnic Institute, 2008.
[details] [full text]
[BibTeX▼]
@phdthesis{inanc-phd,
author = "Inanc, Metin",
title = "Compressing Terrain Elevation Datasets",
school = "Rensselaer Polytechnic Institute",
mykey = "theses odetlap inanc",
year = "2008"
}
- Zhongyi Xie.
Representation, compression and progressive transmission of digital terrain data using over-determined laplacian partial differential equations.
Master's thesis, Rensselaer Polytechnic Institute, 2008.
[details]
[BibTeX▼]
@mastersthesis{xie-ms,
author = "Xie, Zhongyi",
title = "Representation, Compression and Progressive Transmission of Digital Terrain Data Using Over-Determined Laplacian Partial Differential Equations",
mykey = "odetlap xie",
school = "Rensselaer Polytechnic Institute",
year = "2008"
}
2007
- Zhongyi Xie, Marcus A. Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Daniel M. Tracy, and Jonathan Muckell.
Approximating terrain with over-determined Laplacian PDEs.
In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007.
(poster session, no formal proceedings).
[details] [full text] [poster]
[BibTeX▼]
@inproceedings{xie-fwcg-2007,
author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Tracy, Daniel M. and Muckell, Jonathan",
title = "Approximating terrain with over-determined {Laplacian} {PDEs}",
booktitle = "17th Fall Workshop on Computational Geometry",
month = "2--3 Nov",
mykey = "tracy inanc marcus xie muckell odetlap",
year = "2007",
note = "(poster session, no formal proceedings)",
address = "IBM TJ Watson Research Center, Hawthorne NY",
customlinkposter = "https://wrfranklin.org/p/117-fwcg07-xie-poster.ppt",
href = "\bibhrefap{117-fwcg07-xie-abs}{117-fwcg07-xie-poster.ppt}"
}
- Zhongyi Xie, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Metin Inanc, and Daniel M. Tracy.
Surface compression using over-determined Laplacian approximation.
In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering.
paper 6697-15.
[abstract▼] [details] [full text]
[BibTeX▼]
@inproceedings{zx-wrf-spie-2007,
author = "Xie, Zhongyi and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Inanc, Metin and Tracy, Daniel M.",
title = "Surface compression using over-determined {Laplacian} approximation",
booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}",
year = "2007",
month = "27 August",
organization = "International Society for Optical Engineering",
address = "San Diego CA",
note = "paper 6697-15",
href = "\bibhref{113-spie07-xie}",
mykey = "marcus inanc xie odetlap"
}
1998
- Michael Gousie and W. Randolph Franklin.
Converting elevation contours to a grid.
In Eighth International Symposium on Spatial Data Handling, 647–656. Vancouver BC Canada, July 1998. Dept of Geography, Simon Fraser University, Burnaby, BC, Canada.
[details] [full text] [slides]
[BibTeX▼]
@inproceedings{gousie98,
author = "Gousie, Michael and Franklin, W. Randolph",
title = "Converting Elevation Contours to a Grid",
booktitle = "Eighth International Symposium on Spatial Data Handling",
address = "Vancouver BC Canada",
year = "1998",
month = "July",
pages = "647-656",
publisher = "Dept of Geography, Simon Fraser University, Burnaby, BC, Canada",
customlinkslides = "https://wrfranklin.org/p/89-vancouver-sdh98-contour-gousie-talk.pdf",
mykey = "terrain odetlap",
href = "\bibhrefpt{89-vancouver-sdh98-contour-gousie}{89-vancouver-sdh98-contour-gousie-talk.pdf}"
}
- Michael B Gousie.
Contours to digital elevation models: grid-based surface reconstruction methods.
PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, 1998.
[details]
[BibTeX▼]
@phdthesis{gousie-phd,
author = "Gousie, Michael B",
title = "Contours to digital elevation models: grid-based surface reconstruction methods",
school = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
mykey = "odetlap theses",
year = "1998"
}
Contact: WRF