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 Free Access

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.

**[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**, 10.1137/0725011**[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**, 10.1016/0021-9991(85)90191-3**[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**, 10.1090/S0025-5718-1986-0856701-5**[21]**R. C. Mjolsness and Blair Swartz,*Some plane curvature approximations*, Math. Comp.**49**(1987), no. 179, 215–230. MR**890263**, 10.1090/S0025-5718-1987-0890263-2**[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**, 10.1137/0725010**[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*3*D 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.

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1989-0983313-8

Keywords:
Blurred,
boundary,
border,
edge,
curve,
surface,
interface,
approximation,
reconstruction

Article copyright:
© Copyright 1989
American Mathematical Society