Finite differences in forward and inverse imaging problems: maxpol design. (English) Zbl 1404.65215
The authors introduce a generalized numerical framework to derive lowpass/fullband derivative kernels in a closed form solution based on the maximally flat design technique. Four possible cases of derivative matrices are designed which encode high accuracy boundary formulation with arbitrary derivative order, polynomial accuracy, and lowpass/fullband design. The stability of these matrices is discussed by studying their eigenvalue distribution in the complex plane. The theoretical approach is further illustrated on several specific numerical experiments.
Reviewer: Marius Ghergu (Dublin)
MSC:
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 65D25 | Numerical differentiation |
| 65N21 | Numerical methods for inverse problems for boundary value problems involving PDEs |
| 68U10 | Computing methodologies for image processing |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
Keywords:
numerical differentiation; boundary condition; derivative matrix; fullband/lowpass FIR differentiation; maxflat technique; inverse Vandermonde; gradient surface recovery; image stitchingReferences:
| [1] | A. Agrawal, R. Raskar, and R. Chellappa, What is the range of surface reconstructions from a gradient field?, in Proceedings of the European Conference on Computer Vision, Springer, 2006, pp. 578–591. |
| [2] | A. Aprovitola and L. Gallo, Edge and junction detection improvement using the Canny algorithm with a fourth order accurate derivative filter, in Proceedings of the Tenth International IEEE Conference on Signal-Image Technology and Internet-Based Systems (SITIS), 2014, pp. 104–111. |
| [3] | A. Aprovitola and L. Gallo, Knee bone segmentation from MRI: A classification and literature review, Biocybern. Biomed. Eng., 36 (2016), pp. 437–449. |
| [4] | R. H. Bartels and G. Stewart, Solution of the matrix equation ax+ xb= c [f4], Comm. ACM, 15 (1972), pp. 820–826. · Zbl 1372.65121 |
| [5] | A. Belyaev, Implicit image differentiation and filtering with applications to image sharpening, SIAM J. Imaging Sci., 6 (2013), pp. 660–679, . · Zbl 1279.68320 |
| [6] | J. M. Bioucas-Dias and G. Valadao, Phase unwrapping via graph cuts, IEEE Trans. Image Process., 16 (2007), pp. 698–709. |
| [7] | K. Bredies, K. Kunisch, and T. Pock, Total generalized variation, SIAM J. Imaging Sci., 3 (2010), pp. 492–526, . · Zbl 1195.49025 |
| [8] | A. Buades, B. Coll, and J. M. Morel, A review of image denoising algorithms, with a new one, Multiscale Model. Simul., 4 (2005), pp. 490–530, . · Zbl 1108.94004 |
| [9] | N. Burch, P. E. Fishback, and R. Gordon, The least-squares property of the Lanczos derivative, Math. Mag., 78 (2005), pp. 368–378. · Zbl 1086.65015 |
| [10] | C. Bustacara-Medina and L. Flórez-Valencia, Comparison and evaluation of first derivatives estimation, in Proceedings of the International Conference on Computer Vision and Graphics, Springer, 2016, pp. 121–133. |
| [11] | J. Canny, A computational approach to edge detection, IEEE Trans. Pattern Anal. Mach. Intell., 8 (1986), pp. 679–698. |
| [12] | B. Carlsson, Maximum flat digital differentiator, Electron. Lett., 27 (1991), pp. 675–677. |
| [13] | C. Chen and K. Leung, A new look at partial fraction expansion from a high-level language viewpoint, Comput. Math. Appl., 7 (1981), pp. 361–367. · Zbl 0461.65015 |
| [14] | A. Cichocki, D. Mandic, L. D. Lathauwer, G. Zhou, Q. Zhao, C. Caiafa, and H. A. PHAN, Tensor decompositions for signal processing applications: From two-way to multiway component analysis, IEEE Signal Process. Mag., 32 (2015), pp. 145–163. |
| [15] | P. Comon, Tensors: A brief introduction, IEEE Signal Process. Mag., 31 (2014), pp. 44–53. |
| [16] | K. Delibasis and A. Kechriniotis, A new formula for bivariate Hermite interpolation on variable step grids and its application to image interpolation, IEEE Trans. Image Process., 23 (2014), pp. 2892–2904. · Zbl 1388.65020 |
| [17] | K. Delibasis, A. Kechriniotis, and I. Maglogiannis, On centered and compact signal and image derivatives for feature extraction, in Artificial Intelligence Applications and Innovations, H. Papadopoulos, A. Andreou, L. Iliadis, and I. Maglogiannis, eds., IFIP Adv. Inf. Commun. Technol. 412, Springer, 2013, pp. 318–327. |
| [18] | R. Deriche, Recursively Implementating the Gaussian and Its Derivatives, Ph.D. thesis, INRIA, 1993. |
| [19] | C. E. Duchon, Lanczos filtering in one and two dimensions, J. Appl. Meteorol., 18 (1979), pp. 1016–1022. |
| [20] | J.-D. Durou and F. Courteille, Integration of a normal field without boundary condition, in Proceedings of the First International Workshop on Photometric Analysis For Computer Vision (PACV 2007), INRIA, 2007. |
| [21] | A. Eisinberg and G. Fedele, On the inversion of the Vandermonde matrix, Appl. Math. Comput., 174 (2006), pp. 1384–1397. · Zbl 1124.65028 |
| [22] | M. Elad and P. Milanfar, Style transfer via texture synthesis, IEEE Trans. Image Process., 26 (2017), pp. 2338–2351. · Zbl 1409.94137 |
| [23] | V. Estellers, M. A. Scott, and S. Soatto, Robust surface reconstruction, SIAM J. Imaging Sci., 9 (2016), pp. 2073–2098, . · Zbl 1365.65036 |
| [24] | H. Farid and E. Simoncelli, Optimally rotation-equivariant directional derivative kernels, in Computer Analysis of Images and Patterns, G. Sommer, K. Daniilidis, and J. Pauli, eds., Lecture Notes in Comput. Sci. 1296, Springer, 1997, pp. 207–214. |
| [25] | H. Farid and E. Simoncelli, Differentiation of discrete multidimensional signals, IEEE Trans. Image Process., 13 (2004), pp. 496–508. |
| [26] | M. Fiedler, Special Matrices and Their Applications in Numerical Mathematics, Courier Corporation, 2008. · Zbl 1170.65018 |
| [27] | B. Fornberg, Generation of finite difference formulas on arbitrarily spaced grids, Math. Comp., 51 (1988), pp. 699–706. · Zbl 0701.65014 |
| [28] | B. Fornberg, Calculation of weights in finite difference formulas, SIAM Rev., 40 (1998), pp. 685–691, . · Zbl 0914.65010 |
| [29] | W. T. Freeman and E. H. Adelson, The design and use of steerable filters, IEEE Trans. Pattern Anal. Mach. Intell., 13 (1991), pp. 891–906. |
| [30] | A. Gambaruto, Processing the image gradient field using a topographic primal sketch approach, Int. J. Numer. Methods Biomed. Eng., 31 (2015), e02706. |
| [31] | P. A. Gorry, General least-squares smoothing and differentiation by the convolution (Savitzky-Golay) method, Anal. Chem., 62 (1990), pp. 570–573. |
| [32] | C. Groetsch, Lanczo’s generalized derivative, Amer. Math. Monthly, 105 (1998), pp. 320–326. · Zbl 0927.26003 |
| [33] | M. Harker and P. O’Leary, Regularized reconstruction of a surface from its measured gradient field, J. Math. Imaging Vision, 51 (2015), pp. 46–70. · Zbl 1331.68251 |
| [34] | H. Hassan, A. Mohamad, and G. Atteia, An algorithm for the finite difference approximation of derivatives with arbitrary degree and order of accuracy, J. Comput. Appl. Math., 236 (2012), pp. 2622–2631. · Zbl 1238.65014 |
| [35] | K. He, J. Sun, and X. Tang, Guided image filtering, IEEE Trans. Pattern Anal. Mach. Intell., 35 (2013), pp. 1397–1409. |
| [36] | O. Herrmann, On the approximation problem in nonrecursive digital filter design, IEEE Trans. Circuit Theory, 18 (1971), pp. 411–413. |
| [37] | B. K. Horn and M. J. Brooks, The variational approach to shape from shading, Comput. Gr. Image Process., 33 (1986), pp. 174–208. · Zbl 0629.65125 |
| [38] | R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 2012. |
| [39] | M. S. Hosseini and K. N. Plataniotis, Derivative kernels: Numerics and applications, IEEE Trans. Image Process., 26 (2017), pp. 4596–4611. |
| [40] | A. Ignjatovic, Signal Processor with Local Signal Behavior, U.S. Patent 6,115,726, Sept. 5, 2000. |
| [41] | A. Ignjatovic, Chromatic derivatives and local approximations, IEEE Trans. Signal Process., 57 (2009), pp. 2998–3007. · Zbl 1391.94249 |
| [42] | A. Ignjatovic and N. A. Carlin, Method and a System of Acquiring Local Signal Behavior Parameters for Representing and Processing a Signal, U.S. Patent 6,313,778, Nov. 6, 2001. |
| [43] | A. Ignjatovic and A. Zayed, Multidimensional chromatic derivatives and series expansions, Proc. Amer. Math. Soc., 139 (2011), pp. 3513–3525. · Zbl 1242.41032 |
| [44] | A. Jalba, M. Wilkinson, and J. Roerdink, Shape representation and recognition through morphological curvature scale spaces, IEEE Trans. Image Process., 15 (2006), pp. 331–341. |
| [45] | J. Kaiser and R. Hamming, Sharpening the response of a symmetric nonrecursive filter by multiple use of the same filter, IEEE Trans. Acoust. Speech Signal Process., 25 (1977), pp. 415–422. · Zbl 0373.93039 |
| [46] | J. Kaiser and W. Reed, Data smoothing using low-pass digital filters, Rev. Sci. Instrum., 48 (1977), pp. 1447–1457. |
| [47] | I. Khan and R. Ohba, New design of full band differentiators based on Taylor series, in IEE Proceedings—Vision, Image and Signal Processing, Vol. 146, 1999, pp. 185–189. |
| [48] | I. R. Khan and R. Ohba, Closed-form expressions for the finite difference approximations of first and higher derivatives based on Taylor series, J. Comput. Appl. Math., 107 (1999), pp. 179–193. · Zbl 0939.65031 |
| [49] | I. R. Khan and R. Ohba, New finite difference formulas for numerical differentiation, J. Comput. Appl. Math., 126 (2000), pp. 269–276. · Zbl 0971.65014 |
| [50] | I. R. Khan and R. Ohba, Taylor series based finite difference approximations of higher-degree derivatives, J. Comput. Appl. Math., 154 (2003), pp. 115–124. · Zbl 1018.65032 |
| [51] | I. R. Khan, R. Ohba, and N. Hozumi, Mathematical proof of closed form expressions for finite difference approximations based on Taylor series, J. Comput. Appl. Math., 150 (2003), pp. 303–309. · Zbl 1017.65015 |
| [52] | B. Kumar and S. Dutta Roy, Design of digital differentiators for low frequencies, Proc. IEEE, 76 (1988), pp. 287–289. |
| [53] | B. Kumar and S. Dutta Roy, Maximally linear FIR digital differentiators for high frequencies, IEEE Trans. Circuits Syst., 36 (1989), pp. 890–893. |
| [54] | B. Kumar, S. Dutta Roy, and H. Shah, On the design of FIR digital differentiators which are maximally linear at the frequency pi;/p, p isin; positive integers, IEEE Trans. Signal Process., 40 (1992), pp. 2334–2338. |
| [55] | C. Lanczos, Applied Analysis, Prentice–Hall, 1956. · Zbl 0111.12403 |
| [56] | C. Lanczos, Applied Analysis, Courier Corporation, 1988. |
| [57] | A. Levin, A. Zomet, S. Peleg, and Y. Weiss, Seamless image stitching in the gradient domain, in Proceedings of the European Conference on Computer Vision, Springer, 2004, pp. 377–389. · Zbl 1098.68804 |
| [58] | J. Li, General explicit difference formulas for numerical differentiation, J. Comput. Appl. Math., 183 (2005), pp. 29–52. · Zbl 1077.65021 |
| [59] | J. Liao, B. Buchholz, J. M. Thiery, P. Bauszat, and E. Eisemann, Indoor scene reconstruction using near-light photometric stereo, IEEE Trans. Image Process., 26 (2017), pp. 1089–1101. · Zbl 1409.94332 |
| [60] | T. Lindeberg, Feature detection with automatic scale selection, Int. J. Comput. Vis., 30 (1998), pp. 79–116. |
| [61] | D. G. Lowe, Distinctive image features from scale-invariant keypoints, Int. J. Comput. Vis., 60 (2004), pp. 91–110. |
| [62] | J. Luo, K. Ying, P. He, and J. Bai, Properties of Savitzky–Golay digital differentiators, Digit. Signal Process., 15 (2005), pp. 122–136. |
| [63] | Y.-K. Man, On the inversion of Vandermonde matrices, in Proceedings of the World Congress on Engineering, Vol. 2, 2014. |
| [64] | D. Marr and E. Hildreth, Theory of edge detection, Roy. Soc. Lond. Proc. Ser. Biol. Sci., 207 (1980), pp. 187–217. |
| [65] | M. Mboup, C. Join, and M. Fliess, Numerical differentiation with annihilators in noisy environment, Numer. Algorithms, 50 (2009), pp. 439–467. · Zbl 1162.65009 |
| [66] | T. J. McDevitt, Discrete Lanczos derivatives of noisy data, Int. J. Comput. Math., 89 (2012), pp. 916–931. · Zbl 1259.65051 |
| [67] | R. Mecca, Y. Quéau, F. Logothetis, and R. Cipolla, A single-lobe photometric stereo approach for heterogeneous material, SIAM J. Imaging Sci., 9 (2016), pp. 1858–1888, . · Zbl 1375.94023 |
| [68] | P. Meer and I. Weiss, Smoothed differentiation filters for images, in Proceedings of the 10th International IEEE Conference on Pattern Recognition, Vol. 2, 1990, pp. 121–126. · Zbl 0825.68580 |
| [69] | F. Mokhtarian and A. Mackworth, Scale-based description and recognition of planar curves and two-dimensional shapes, IEEE Trans. Pattern Anal. Mach. Intell., 8 (1986), pp. 34–43. |
| [70] | T. Möller, R. Machiraju, Y. Kurzion, K. Mueller, and R. Yagel, Spatial Domain Filter Design, Ph.D. thesis, Ohio State University, 1999. |
| [71] | T. Möller, R. Machiraju, K. Mueller, and R. Yagel, Evaluation and design of filters using a Taylor series expansion, IEEE Trans. Vis. Comput. Graphics, 3 (1997), pp. 184–199. |
| [72] | T. Möller, K. Mueller, Y. Kurzion, R. Machiraju, and R. Yagel, Design of accurate and smooth filters for function and derivative reconstruction, in Proceedings of the 1998 IEEE Symposium on Volume Visualization, ACM, 1998, pp. 143–151. |
| [73] | P. O’Leary and M. Harker, An algebraic framework for discrete basis functions in computer vision, in Proceedings of the Sixth IEEE Indian Conference on Computer Vision, Graphics & Image Processing (ICVGIP), 2008, pp. 150–157. |
| [74] | P. O’Leary and M. Harker, A framework for the evaluation of inclinometer data in the measurement of structures, IEEE Trans. Instrum. Meas., 61 (2012), pp. 1237–1251. |
| [75] | L. Pantanowitz and A. V. Parwani, Digital Pathology, American Society for Clinical Pathology, 2017. |
| [76] | K. Papafitsoros and C. Schönlieb, A combined first and second order variational approach for image reconstruction, J. Math. Imaging Vision, 48 (2014), pp. 308–338. · Zbl 1362.94009 |
| [77] | V. M. Patel, R. Maleh, A. C. Gilbert, and R. Chellappa, Gradient-based image recovery methods from incomplete Fourier measurements, IEEE Trans. Image Process., 21 (2012), pp. 94–105. · Zbl 1372.94203 |
| [78] | P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Mach. Intell., 12 (1990), pp. 629–639. |
| [79] | A. Polesel, G. Ramponi, and V. J. Mathews, Image enhancement via adaptive unsharp masking, IEEE Trans. Image Process., 9 (2000), pp. 505–510. |
| [80] | Y. Quéau, J.-D. Durou, and J.-F. Aujol, Normal Integration: A Survey with New Insights, preprint. 2016. |
| [81] | Y. Romano, J. Isidoro, and P. Milanfar, RAISR: Rapid and accurate image super resolution, IEEE Trans. Comput. Imaging, 3 (2017), pp. 110–125. |
| [82] | B. Sadiq and D. Viswanath, Finite difference weights, spectral differentiation, and superconvergence, Math. Comp., 83 (2014), pp. 2403–2427. · Zbl 1301.65018 |
| [83] | A. Savitzky and M. J. E. Golay, Smoothing and differentiation of data by simplified least squares procedures, Anal. Chem., 36 (1964), pp. 1627–1639. |
| [84] | R. W. Schafer, What is a Savitzky-Golay filter? [lecture notes], IEEE Signal Process. Mag., 28 (2011), pp. 111–117. |
| [85] | I. Selesnick, Maximally flat low-pass digital differentiator, IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., 49 (2002), pp. 219–223. |
| [86] | I. Selesnick and C. Burrus, Maximally flat low-pass fir filters with reduced delay, IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., 45 (1998), pp. 53–68. |
| [87] | I. W. Selesnick, Low-pass filters realizable as all-pass sums: design via a new flat delay filter, IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., 46 (1999), pp. 40–50. |
| [88] | I. W. Selesnick and C. S. Burrus, Generalized digital Butterworth filter design, IEEE Trans. Signal Process., 46 (1998), pp. 1688–1694. |
| [89] | T. Simchony, R. Chellappa, and M. Shao, Direct analytical methods for solving Poisson equations in computer vision problems, IEEE Trans. Pattern Anal. Mach. Intell., 12 (1990), pp. 435–446. · Zbl 1316.94015 |
| [90] | E. Simoncelli, Design of multi-dimensional derivative filters, in Proceedings of the IEEE International Conference on Image Processing (ICIP), Vol. 1, 1994, pp. 790–794. |
| [91] | W. Stanley, A time-to-frequency-domain matrix formulation, Proc. IEEE, 52 (1964), pp. 874–875. |
| [92] | G. W. Stewart, Matrix Algorithms. Volume 2: Eigensystems, SIAM, 2001, . · Zbl 0984.65031 |
| [93] | R. Szeliski, Image alignment and stitching: A tutorial, Found. Trends Comput. Graph. Vis., 2 (2006), pp. 1–104. · Zbl 1126.68092 |
| [94] | H. Talebi and P. Milanfar, Fast multilayer Laplacian enhancement, IEEE Trans. Comput. Imaging, 2 (2016), pp. 496–509. |
| [95] | L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, 2005. · Zbl 1085.15009 |
| [96] | M. Unser, A. Aldroubi, and M. Eden, B-spline signal processing. I. Theory, IEEE Trans. Signal Process., 41 (1993), pp. 821–833. · Zbl 0825.94086 |
| [97] | M. Unser, A. Aldroubi, and M. Eden, B-spline signal processing. II. Efficiency design and applications, IEEE Trans. Signal Process., 41 (1993), pp. 834–848. · Zbl 0825.94087 |
| [98] | S. Uras, F. Girosi, A. Verri, and V. Torre, A computational approach to motion perception, Biol. Cybernet., 60 (1988), pp. 79–87. |
| [99] | B. D. Welfert, Generation of pseudospectral differentiation matrices I, SIAM J. Numer. Anal., 34 (1997), pp. 1640–1657, . · Zbl 0889.65013 |
| [100] | W. Xie, Y. Zhang, C. C. Wang, and R. C.-K. Chung, Surface-from-gradients: An approach based on discrete geometry processing, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 2195–2202. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
