The secondorder sharpening of blurred smooth borders
Author:
Blair Swartz
Journal:
Math. Comp. 52 (1989), 675714, S35
MSC:
Primary 65D99; Secondary 65P05
MathSciNet review:
983313
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The problem is to approximate, with local secondorder 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. "Secondorder", 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 secondorder 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 secondorder 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
(55 #1711)
 [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
(49 #3381)
 [4]
C. de Boor, "Splines as linear combinations of Bsplines," in Approximation Theory II (G. G. Lorentz, C. K. Chui &. L. L. Schumaker, eds.), Academic Press, New York, 1976, pp. 147.
 [5]
Carl
de Boor, A practical guide to splines, Applied Mathematical
Sciences, vol. 27, SpringerVerlag, New YorkBerlin, 1978. MR 507062
(80a:65027)
 [6]
Carl
de Boor, The condition of the 𝐵spline basis for
polynomials, SIAM J. Numer. Anal. 25 (1988),
no. 1, 148–152. MR 923931
(88m:65073), http://dx.doi.org/10.1137/0725011
 [7]
D. S. Carter, G. Pimbley &. G. M. Wing, On the Unique Solution for the Density Function in Phermex, (Declassified) Memo T52023, 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
(86d:80001), http://dx.doi.org/10.1016/00219991(85)901913
 [9]
M.
G. Cox, The numerical evaluation of 𝐵splines, J.
Inst. Math. Appl. 10 (1972), 134–149. MR 0334456
(48 #12775)
 [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
(36 #1884)
 [11]
R. B. DeBar, Fundamentals of the KRAKEN Code, Report UCID17366, Lawrence Livermore Laboratory, Livermore, CA, 1974, 17pp.
 [12]
G. de Cecco, "Il teorema del sandwich al prosciutto," Archimede, v. 37, 1985, pp. 98106. (Italian)
 [13]
V. Faber & G. M. Wing, The Abel Integral Equation, Report LA11016MS, 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
(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. 103127.
 [17]
B. R. Hunt (editor), "Special image processing issue," Proc. IEEE, v. 69, 1981, pp. 499655.
 [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. 396407.
 [20]
H.O.
Kreiss, T.
A. Manteuffel, B.
Swartz, B.
Wendroff, and A.
B. White Jr., Supraconvergent schemes on irregular
grids, Math. Comp. 47
(1986), no. 176, 537–554. MR 856701
(88b:65082), http://dx.doi.org/10.1090/S00255718198608567015
 [21]
R.
C. Mjolsness and Blair
Swartz, Some plane curvature
approximations, Math. Comp.
49 (1987), no. 179, 215–230. MR 890263
(88g:65017), http://dx.doi.org/10.1090/S00255718198708902632
 [22]
B. D. Nichols & C. W. Hirt, Methods for Calculating MultiDimensional, 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.), SpringerVerlag, New York, 1976, pp. 330340.
 [24]
B. Swartz, The SecondOrder Sharpening of Blurred Smooth Borders, Report LAUR872933, Los Alamos National Laboratory, 1987, 35pp.
 [25]
Blair
Swartz, Conditioning collocation, SIAM J. Numer. Anal.
25 (1988), no. 1, 124–147. MR 923930
(89b:65181), http://dx.doi.org/10.1137/0725010
 [26]
G. M. Wing, A Primer on Integral Equations of the First Kind, Report LAUR841234, 1984, 98pp.
 [27]
D. L. Youngs, private communication, 1978.
 [28]
D. L. Youngs, "Timedependent multimaterial flow with large fluid distortion," Numerical Methods for Fluid Dynamics (K. W. Morton & M. J. Baines, eds.), Academic Press, New York, 1982, pp. 274285.
 [29]
D. L. Youngs, An Interface Tracking Method for a 3D Eulerian Hydrodynamics Code, Atomic Weapons Research Establishment Report AWRE449235, Aldermaston, Berks., 1987, 47pp.
 [30]
C. Zemach, TDivision, Los Alamos National Laboratory; private communication, 1988.
 [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 Bsplines, Report LA4728MS, Los Alamos Scientific Laboratory, 1971, 12 pp. (see also SIAM J. Numer. Anal., v. 14, 1977, pp. 441472). MR 0428691 (55:1711)
 [3]
 C. de Boor, "On calculating with Bsplines," J. Approx. Theory, v. 6, 1972, pp. 5062. MR 0338617 (49:3381)
 [4]
 C. de Boor, "Splines as linear combinations of Bsplines," in Approximation Theory II (G. G. Lorentz, C. K. Chui &. L. L. Schumaker, eds.), Academic Press, New York, 1976, pp. 147.
 [5]
 C. de Boor, A Practical Guide to Splines, Appl. Math. Sci. #27, SpringerVerlag, New York, 1978. MR 507062 (80a:65027)
 [6]
 C. de Boor, "The condition of the Bspline basis for polynomials," SIAM J. Numer. Anal., v. 25, 1988, pp. 148152. 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 T52023, Los Alamos Scientific Laboratory, Los Alamos, NM, 1957, 7 pp.
 [8]
 A. J. Chorin, "Curvature and solidification," J. Comput. Phys., v. 57, 1985, pp. 472490. MR 782993 (86d:80001)
 [9]
 M. G. Cox, "The numerical evaluation of Bsplines," J. Inst. Math. Appl., v. 10, 1972, pp. 134149. 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. 71107. MR 0218800 (36:1884)
 [11]
 R. B. DeBar, Fundamentals of the KRAKEN Code, Report UCID17366, Lawrence Livermore Laboratory, Livermore, CA, 1974, 17pp.
 [12]
 G. de Cecco, "Il teorema del sandwich al prosciutto," Archimede, v. 37, 1985, pp. 98106. (Italian)
 [13]
 V. Faber & G. M. Wing, The Abel Integral Equation, Report LA11016MS, 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. 103127.
 [17]
 B. R. Hunt (editor), "Special image processing issue," Proc. IEEE, v. 69, 1981, pp. 499655.
 [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. 396407.
 [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. 537554. MR 856701 (88b:65082)
 [21]
 R. C. Mjolsness & B. Swartz, "Some plane curvature approximatons," Math. Comp., v. 49, 1987, pp. 215230. MR 890263 (88g:65017)
 [22]
 B. D. Nichols & C. W. Hirt, Methods for Calculating MultiDimensional, 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.), SpringerVerlag, New York, 1976, pp. 330340.
 [24]
 B. Swartz, The SecondOrder Sharpening of Blurred Smooth Borders, Report LAUR872933, Los Alamos National Laboratory, 1987, 35pp.
 [25]
 B. Swartz, "Conditioning collocation," SIAM J. Numer. Anal., v. 25, 1988, pp. 124147. MR 923930 (89b:65181)
 [26]
 G. M. Wing, A Primer on Integral Equations of the First Kind, Report LAUR841234, 1984, 98pp.
 [27]
 D. L. Youngs, private communication, 1978.
 [28]
 D. L. Youngs, "Timedependent multimaterial flow with large fluid distortion," Numerical Methods for Fluid Dynamics (K. W. Morton & M. J. Baines, eds.), Academic Press, New York, 1982, pp. 274285.
 [29]
 D. L. Youngs, An Interface Tracking Method for a 3D Eulerian Hydrodynamics Code, Atomic Weapons Research Establishment Report AWRE449235, Aldermaston, Berks., 1987, 47pp.
 [30]
 C. Zemach, TDivision, 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
DOI:
http://dx.doi.org/10.1090/S00255718198909833138
PII:
S 00255718(1989)09833138
Keywords:
Blurred,
boundary,
border,
edge,
curve,
surface,
interface,
approximation,
reconstruction
Article copyright:
© Copyright 1989
American Mathematical Society
