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] C. de Boor, Subroutine Package for Calculating with B-splines, Report LA-4728-MS, Los Alamos Scientific Laboratory, 1971, 12 pp. (see also SIAM J. Numer. Anal., v. 14, 1977, pp. 441-472). MR 0428691 (55:1711)
  • [3] C. de Boor, "On calculating with B-splines," J. Approx. Theory, v. 6, 1972, pp. 50-62. MR 0338617 (49:3381)
  • [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] C. de Boor, A Practical Guide to Splines, Appl. Math. Sci. #27, Springer-Verlag, New York, 1978. MR 507062 (80a:65027)
  • [6] C. de Boor, "The condition of the B-spline basis for polynomials," SIAM J. Numer. Anal., v. 25, 1988, pp. 148-152. MR 923931 (88m:65073)
  • [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] A. J. Chorin, "Curvature and solidification," J. Comput. Phys., v. 57, 1985, pp. 472-490. MR 782993 (86d:80001)
  • [9] M. G. Cox, "The numerical evaluation of B-splines," J. Inst. Math. Appl., v. 10, 1972, pp. 134-149. MR 0334456 (48:12775)
  • [10] H. B. Curry & I. J. Schoenberg, "On Pólya frequency functions. IV: The fundamental spline functions and their limits," J. Analyse Math., v. 17, 1966, pp. 71-107. MR 0218800 (36:1884)
  • [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] G. H. Golub & C. F. Van Loan, Matrix Computations, Johns Hopkins Univ. Press, Baltimore, MD, 1983. MR 733103 (85h:65063)
  • [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 & A. B. White, "Supraconvergent schemes on irregular grids," Math. Comp., v. 47, 1986, pp. 537-554. MR 856701 (88b:65082)
  • [21] R. C. Mjolsness & B. Swartz, "Some plane curvature approximatons," Math. Comp., v. 49, 1987, pp. 215-230. MR 890263 (88g:65017)
  • [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] B. Swartz, "Conditioning collocation," SIAM J. Numer. Anal., v. 25, 1988, pp. 124-147. MR 923930 (89b:65181)
  • [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