Piecewise approximation of functions of two variables through regions with variable boundaries

ABSTRACT

The domain of a function f(x,y) is subdivided into regions D1, D2,...DM such that on each one of them f(x,y) can be approximated by a low order polynomial within a given tolerance. It is desirable to chose the boundaries of the regions in such a way as to minimize the amount of storage required for the approximate description of f(x,y). A suboptimal solution to this problem is presented. It is based on a two step procedure. First the optimal segmentation is obtained for profiles of f(x,y) along certain lines of its domain. The regions so obtained are then grouped together to form the final subdivisions. Examples of application of the method in the compression of topographical data are presented. Compression ratios of over 20:1 are obtained for RMS error 2%.

REFERENCES

• 1: Lawson, C.L. "Characteristic Properties of the Segmented Rational Minimax Approximation Problem" Numer. Math. v. 6 (1964) pp. 293-301
• 2: Birkhoff, G. and C. R. De Boor "Piecewise Polynomial Interpolation and Approximation" in Approximation of Functions (H. L. Garabedian, Ed), Elsevier Publishing Co, (Amsterdam, 1965) pp. 164-190
• 3: Esch, R. E. and W. L. Eastman "Computational Methods for Best Approximation" Tech. Report SEG-TR-67-30, Dec. 1967, Sperry Rand Research Center, Sudbury, Mass.
• 4: Schumaker, L. L. "Uniform Approximation by Chebyshev spline functions. II: Free Knots" SIAM J. Numer. Anal. v. 5 (1968) pp. 647-656
• 5: DeBoor, C. E. and J. R. Rice "Least Square Cubic Spline Approximation: Variable Knots" Tech Report No. 81 (April 1968) Computer Science Department, Purdue University
• 6: Esch, R.E. and W. L. Eastman "Computational Methods for Best Spline Approximation" J. of Approx. Theory, v. 2 (1969) pp. 85-96
• 7: Braess, D. D. "Chebyshev Approximation by Spline Functions with Free Knots" Numer. Math, v. 17 (1971) pp. 357-366
• 8: Stancu, D. D. "The remainder of Certain Linear Approximation Formulas in Two Variables" SIAM J. Numer. Anal., v. 1 (1964) pp. 137-163
• 9: Birkhoff, G., M. M. Schultz and R. S. Varga "Piecewise Hermite Interpolation in One and Two Variables with Approximations to Partial Differential Equations" Numer. Math., v. 11 (1968) pp. 232-256
• 10: Ritter, K. "Two-Dimensional Spline Functions and Best Approximations of Linear Functionals" J. of Approx. Theory, v. 3 (1970), pp. 352-368
• 11: Zenisek, A. "Interpolation Polynomials on the Triangle" Numer. Math., v. 15 (1970) pp. 283-296
• 12: Carlson, R. E. and C.A. Hall "On piecewise Polynomial Interpolation in Rectangular Polygons" J. of Approx. Theory, v. 4 (1971) pp. 37-53
• 13: Barry W. Boehm, Tabular representation of multivariate functions—with applications to topographic modeling, Proceedings of the 1967 22nd national conference, p.403-415, January 1967, Washington, D.C., United States [doi>10.1145/800196.806009]
• 14: Rosenfeld, A. Picture Processing by Computer, Academic Press, (1969)
• 15: Wilkins, L. C. and P. A. Wintz "Bibliography on Data Compression, Picture Properties and Picture Coding" Tech. Report No. TR-EE69-10, July 1969, Purdue University, Lafayette, Indiana
• 16: Kirsch, R. A. "Computer Determination of the Constituent Structure of Biological Images" Computers and Biomedical Research v. 4 (1971) pp. 315-328
• 17: Pavlidis, T. "Compression of Topographical Data and Applications" Tech Report No. 31, March 1970, Information Sciences and Systems Laboratory Princeton University, Princeton, New Jersey
• 18: Pavlidis, T. "Piecewise Approximation of Functions of Two Variables and its Application in Topographical Data Reduction" Tech. Report No. 86, Sept. 1970, Computer Science Laboratory, Princeton University, Princeton, New Jersey
• 19: E. L. Amidon , G. S. Akin, Algorithmic selection of the best method for compressing map data strings, Communications of the ACM, v.14 n.12, p.769-774, Dec. 1971 [doi>10.1145/362919.362931]
• 20: Davisson, L. D. "The Theoretical Analysis of Data Compression Systems" Proc. IEEE, vol. 56 (1968) pp. 176-186
• 21: John F. Hart, Computer Approximations, Krieger Publishing Co., Inc., Melbourne, FL, 1978
• 22: Pavlidis, T. "Linguistic Analysis of Waveforms" in Software Engineering, (J. Tou, Ed) Acad. Press, 1971 203-225
• 23: Maika, A. P. "Minimax Piecewise Linear Approx. of Functions" MSE Thesis, D. of E. Eng. Princeton U. Aug. 1971.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

General Terms:
Theory

Keywords:
Bivariate piecewise approximation, Piecewise polynomial approximation, Topographical data compression