Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The second-order sharpening of blurred smooth borders

Author: Blair Swartz
Journal: Math. Comp. 52 (1989), 675-714, S35
MSC: Primary 65D99; Secondary 65P05
MathSciNet review: 983313
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The problem is to approximate, with local second-order accuracy, the smooth boundary separating a black and a white region in the plane, given discretely located gray values associated with a blurring of that border. "Second-order", here, is with respect to the size h of the scale of the prescribed blurring. The locally determined approximations are line segments. The algorithms discussed here can result in second-order accuracy, but they may not in certain geometric circumstances. Typical local curvature estimates based on adjacent line segments do not converge, but an atypical one does. Consideration of a class of scaled blurrings leads to a type of blurring of borders which is particularly easy for a computer to undo locally, yielding a line which is locally second-order accurate. Some extensions to three (and more) dimensions are appended.

References [Enhancements On Off] (What's this?)

  • [1] W. A. Beyer & B. Swartz, Halfway Points (a report in preparation), Los Alamos National Laboratory, Los Alamos, NM, 1989.
  • [2] Carl de Boor, Package for calculating with 𝐵-splines, SIAM J. Numer. Anal. 14 (1977), no. 3, 441–472. MR 0428691,
  • [3] Carl de Boor, On calculating with 𝐵-splines, J. Approximation Theory 6 (1972), 50–62. Collection of articles dedicated to J. L. Walsh on his 75th birthday, V (Proc. Internat. Conf. Approximation Theory, Related Topics and their Applications, Univ. Maryland, College Park, Md., 1970). MR 0338617
  • [4] C. de Boor, "Splines as linear combinations of B-splines," in Approximation Theory II (G. G. Lorentz, C. K. Chui &. L. L. Schumaker, eds.), Academic Press, New York, 1976, pp. 1-47.
  • [5] Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062
  • [6] Carl de Boor, The condition of the 𝐵-spline basis for polynomials, SIAM J. Numer. Anal. 25 (1988), no. 1, 148–152. MR 923931,
  • [7] D. S. Carter, G. Pimbley &. G. M. Wing, On the Unique Solution for the Density Function in Phermex, (Declassified) Memo T-5-2023, Los Alamos Scientific Laboratory, Los Alamos, NM, 1957, 7 pp.
  • [8] Alexandre Joel Chorin, Curvature and solidification, J. Comput. Phys. 57 (1985), no. 3, 472–490. MR 782993,
  • [9] M. G. Cox, The numerical evaluation of 𝐵-splines, J. Inst. Math. Appl. 10 (1972), 134–149. MR 0334456
  • [10] H. B. Curry and I. J. Schoenberg, On Pólya frequency functions. IV. The fundamental spline functions and their limits, J. Analyse Math. 17 (1966), 71–107. MR 0218800,
  • [11] R. B. DeBar, Fundamentals of the KRAKEN Code, Report UCID-17366, Lawrence Livermore Laboratory, Livermore, CA, 1974, 17pp.
  • [12] G. de Cecco, "Il teorema del sandwich al prosciutto," Archimede, v. 37, 1985, pp. 98-106. (Italian)
  • [13] V. Faber & G. M. Wing, The Abel Integral Equation, Report LA-11016-MS, Los Alamos National Laboratory, Los Alamos, NM, 1987, 48pp.
  • [14] C. Fenske, Math. Rev., 87h:54078, 1987.
  • [15] Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
  • [16] K. Höllig, "Multivariate splines," in Approximation Theory (C. de Boor, ed.), AMS Short Course Lecture Notes #36, Amer. Math. Soc., Providence, R.I., 1986, pp. 103-127.
  • [17] B. R. Hunt (editor), "Special image processing issue," Proc. IEEE, v. 69, 1981, pp. 499-655.
  • [18] A. Huxley, An Illustrated History of Gardening, Paddington Press (Grosset and Dunlap), New York, 1978.
  • [19] J. M. Hyman, "Numerical methods for tracking interfaces," in Fronts, Interfaces and Patterns (A. R. Bishop, L. J. Campbell & P. J. Channell, eds.), Elsevier, New York, 1984, pp. 396-407.
  • [20] H.-O. Kreiss, T. A. Manteuffel, B. Swartz, B. Wendroff, and A. B. White Jr., Supra-convergent schemes on irregular grids, Math. Comp. 47 (1986), no. 176, 537–554. MR 856701,
  • [21] R. C. Mjolsness and Blair Swartz, Some plane curvature approximations, Math. Comp. 49 (1987), no. 179, 215–230. MR 890263,
  • [22] B. D. Nichols & C. W. Hirt, Methods for Calculating Multi-Dimensional, Transient Free Surface Flows Past Bodies, Proc. First Internat. Conf. Numer. Ship Hydrodynamics, Gaithersburg, MD, 1975.
  • [23] W. F. Noh & P. Woodward, "SLIC (Simple Line Interface Calculation)," in Proc. Fifth Internat. Conf. on Numer. Methods in Fluid Dynamics, Lecture Notes in Physics (A. I. van der Vooren & P. J. Zandbergen, eds.), Springer-Verlag, New York, 1976, pp. 330-340.
  • [24] B. Swartz, The Second-Order Sharpening of Blurred Smooth Borders, Report LA-UR-87-2933, Los Alamos National Laboratory, 1987, 35pp.
  • [25] Blair Swartz, Conditioning collocation, SIAM J. Numer. Anal. 25 (1988), no. 1, 124–147. MR 923930,
  • [26] G. M. Wing, A Primer on Integral Equations of the First Kind, Report LA-UR-84-1234, 1984, 98pp.
  • [27] D. L. Youngs, private communication, 1978.
  • [28] D. L. Youngs, "Time-dependent multi-material flow with large fluid distortion," Numerical Methods for Fluid Dynamics (K. W. Morton & M. J. Baines, eds.), Academic Press, New York, 1982, pp. 274-285.
  • [29] D. L. Youngs, An Interface Tracking Method for a 3D Eulerian Hydrodynamics Code, Atomic Weapons Research Establishment Report AWRE-44-92-35, Aldermaston, Berks., 1987, 47pp.
  • [30] C. Zemach, T-Division, Los Alamos National Laboratory; private communication, 1988.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65D99, 65P05

Retrieve articles in all journals with MSC: 65D99, 65P05

Additional Information

Keywords: Blurred, boundary, border, edge, curve, surface, interface, approximation, reconstruction
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society