Key-Point Interpolation: A Sparse Data Interpolation Algorithm based on B-splines

Bolun Wang, Xin Jiang, Guanying Huo, Cheng Su, Dong‐Ming Yan, Zhiming Zheng

TL;DR

This paper introduces a novel algorithm called Key-Point Interpolation (KPI) that can accurately reconstruct dynamic surfaces from sparse and irregularly distributed data. By combining Kriging for data densification with a two-stage B-spline fitting process, KPI overcomes limitations of traditional methods that require gridded data, enabling applications like dynamic environmental modeling.

What Problem Does This Paper Address?

Many real-world datasets, such as those from LIDAR scans or weather stations, are inherently sparse and non-uniformly distributed. Traditional B-spline surface interpolation algorithms, widely used in fields like reverse engineering and computer-aided design, typically assume data is arranged in regular grids or rows. Applying these methods to sparse data often leads to an explosion in the number of control points, increasing computational cost and memory usage. This paper addresses the challenge of interpolating and reconstructing surfaces from such sparse, non-uniform data, particularly for dynamic scenarios where data changes over time.

Methods

The proposed Key-Point Interpolation (KPI) algorithm is a two-stage process designed to handle sparse and non-uniform data for B-spline surface reconstruction.

  1. Dataset Generation:
    • Triangulation and Parameterization: The sparse data points are first triangulated using a Constrained Delaunay Triangulation (CDT) method. To handle complex borders, a simplification step is employed to ensure the number of border points is comparable to the data points. Mean value coordinates are then used to parameterize the triangulated mesh into a quad-domain.
  2. Parameter Perturbation: To reduce the computational burden associated with dense and non-uniform parameters, a perturbation method is introduced. This method iteratively merges close parameters in both the u and v directions, while ensuring the topological integrity of the mesh by checking triangle orientation.
  3. Kriging Interpolation: Kriging, a geostatistical method for optimal linear unbiased interpolation, is used to generate a gridded dataset from the sparse and parameterized data. This gridded data, along with the original sparse data, forms the input for the next stage.
  4. Control Points Solving based on KPI:
    • Iterative B-spline Fitting: The core of the KPI method involves iteratively fitting B-spline curves. The algorithm uses a two-stage approach for each level of iteration.
  5. Key Point Determination: In the first level, the sparse data points are directly used as key points. For subsequent levels, where the data points are the control points from the previous level, key points are determined based on the local support property of B-splines, selecting a limited number of control points that correspond to non-zero B-spline bases.
  6. Curve Interpolation: A KPI curve is generated by minimizing the difference between the fitted curve and the data points (both sparse and Kriging-generated), while ensuring the curve interpolates the determined key points. This process is repeated for three levels to construct the dynamic B-spline surface.

Datasets

The paper uses a dataset of temperature measurements from 98 weather stations in Shanxi Province, China, collected hourly from October 15-17, 2017. This dataset is used to demonstrate the algorithm's ability to interpolate dynamic environmental data.

Key Insights and Ideas

  • Bridging the Gap for Sparse Data: The most significant insight is the development of a robust method (KPI) that effectively interpolates sparse and non-uniform data for B-spline surface reconstruction, a long-standing challenge.
  • Two-Stage Approach Synergy: The combination of Kriging for data densification and a carefully designed iterative KPI method for control point generation proves to be a powerful strategy. Kriging provides a smooth, gridded foundation, while KPI leverages this to accurately capture the underlying sparse data's characteristics.
  • Parameter Perturbation for Efficiency: The parameter perturbation method is crucial for reducing the computational complexity, making the algorithm more practical for real-world applications where parameter spaces can be very dense.
  • Dynamic Surface Reconstruction: The algorithm's extension to higher dimensions allows for the reconstruction of dynamic surfaces, opening doors for applications in time-series data analysis and simulation.

Key Results

  • The KPI algorithm successfully interpolates sparse temperature data from weather stations in Shanxi Province.
  • The generated dynamic B-spline surface accurately represents the temperature data, with a reported maximum interpolation error of 9.95×10⁻¹⁴.
  • The method preserves the dynamic characteristics of the temperature data, making it useful for meteorological studies.
  • The parameter perturbation method effectively reduced the number of parameters from an initial 124x120 to 66x68 after three iterations.

Limitations and Future Work

  • Parameterization Failures: The paper acknowledges the potential for parametrization failures and includes an extra check to mitigate this. However, the robustness of this check across all complex scenarios might be a point for further investigation.
  • Kriging's Influence: While Kriging helps in generating a smooth surface, its inherent assumptions about spatial correlation might influence the final reconstruction, especially in highly heterogeneous regions.
  • Future Work: The authors suggest that the algorithm can be extended to higher dimensional data interpolation for reconstructing dynamic surfaces. Further exploration into optimizing the parameter perturbation and key-point selection strategies could also be beneficial.

Summary updated

Abstract

Abstract B-splines are widely used in the fields of reverse engineering and computer-aided design, due to their superior properties. Traditional B-spline surface interpolation algorithms usually assume regularity of the data distribution. In this paper, we introduce a novel B-spline surface interpolation algorithm: KPI, which can interpolate sparsely and non-uniformly distributed data points. As a two-stage algorithm, our method generates the dataset out of the sparse data using Kriging, and uses the proposed KPI (Key-Point Interpolation) method to generate the control points. Our algorithm can be extended to higher dimensional data interpolation, such as reconstructing dynamic surfaces. We apply the method to interpolating the temperature of Shanxi Province. The generated dynamic surface accurately interpolates the temperature data provided by the weather stations, and the preserved dynamic characteristics can be useful for meteorology studies.
BibTeX
@article{wang2021key,
  author = {Bolun Wang and Xin Jiang and Guanying Huo and Cheng Su and Dong‐Ming Yan and Zhiming Zheng},
  title = {{Key-Point Interpolation: A Sparse Data Interpolation Algorithm based on B-splines}},
  journal = {Journal of Physics Conference Series},
  year = {2021},
  doi = {10.1088/1742-6596/2068/1/012010},
}
Figure