The second-order sharpening of blurred smooth borders

Author:
Blair Swartz

Journal:
Math. Comp. **52** (1989), 675-714, S35

MSC:
Primary 65D99; Secondary 65P05

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

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.

**[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*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