Add 3rd and 4th order convergent cubic convolution interpolation methods with continuous first derivates in any number of dimensions, including extrapolation support #602
Conversation
This change implements the following algorithm: "Cubic Convolution Interpolation for Digital Image Processing" by Robert G. Keys (1981) IEEE Transactions On Acoustics, Speech And Signal Processing. Its order of accuracy is between that of linear interpolation and cubic splines.
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## master #602 +/- ##
===========================================
- Coverage 87.18% 73.67% -13.51%
===========================================
Files 28 33 +5
Lines 1888 2234 +346
===========================================
Hits 1646 1646
- Misses 242 588 +346 ☔ View full report in Codecov by Sentry. |
.gitignore
Outdated
| @@ -2,3 +2,4 @@ | |||
| docs/build/ | |||
| Manifest.toml | |||
| .vscode | |||
| temp_tester.jl | |||
There was a problem hiding this comment.
| temp_tester.jl |
Please revert this.
|
I like where this is heading. Could you increase test coverage, please? I am wondering about the name |
src/convolution.jl
Outdated
| ConvolutionInterpolation{T,N,typeof(coefs),typeof(it),typeof(knots)}(coefs, (knots_new), it, h, ConvolutionKernel()) | ||
| end | ||
|
|
||
| function create_coefs(knots::Tuple{AbstractVector}, vs::AbstractVector{T}) where T |
There was a problem hiding this comment.
This name seems too general. Perhaps rename is to create_cubic_convolutional_coefs?
I updated the requested names. I added 3D boundary conditions and some smaller improvements.
|
I also added 3D support and implemented your requested naming updates. |
|
I will look into testing in the weekend. :) |
NikoBiele
changed the title
Keeping specialized boundary and interpolation methods up to 3D to ensure speed
NikoBiele
changed the title
|
Tomorrow is dedicated to writing tests. :) |
NikoBiele
changed the title
NikoBiele
changed the title
Both 3rd and 4th order convergence are options with 4th order being the default. Extrapolation is possible with boundary conditions, default being an error if attempting extrapolation.
|
I will write some tests now :) |
The constructed interpolator is tested in 1D, 2D, 3D and 4D against random data at grid points, against linear mean values between grid points and for two extrapolation boundary conditions.
|
In the spirit of the paper mentioned above I derived and tested several of my own kernels! I finally found a really good and smooth one with continuous second derivatives which is 3rd order accurate and like the other ones here it only requires the original values as coefficients, as well as boundary conditions. :) I will implement it here when I find the time. :) |
|
I will close this pull request and instead make my own package implementing this methodology. :) |
|
OK. I'm a little confused. Did you finish writing your tests? |
|
I added tests above. But since nobody replied I interpreted this as a lack of interest. Also I'm getting very good at deriving these kernels, so I think this idea should have it's own space, so to speak. :) |
|
It's not lack of interest. I just did not know you were ready for the pull request to be reviewed again. Your last comment implied that you were still working on something. If you want to reopen, I can take a look. We could also consider restructuring this as an extension that will load when your package is present. |
|
Thanks. I'm sorry that I misinterpreted your intent. No hard feelings at all. But I still thinks that this deserves its own package, as the progress I'm seeing currently suggests that my method will outperform cubic B-splines on important parameters (on equally spaced data), such as setup time (no linear system), accuracy (maximum absolute error, continuity and order of accuracy), simplicity and dimensionality, while having very similar execution time (hopefully on the order of 10 microseconds for 1d). Maybe the extension is a nice option. :) |
Hi interpolators!
I noticed there had been a wish for gridded spline interpolations for a while.
I do not know how to accomplish gridded spline interpolations, but I had an implementation of a cubic convolution algorithm which I have translated. It implements "Cubic Convolution Interpolation for Digital Image
Processing" by Robert G. Keys (1981) IEEE Transactions On Acoustics, Speech, And Signal Processing, vol. ASSP-29, no. 6, December 1981.
I have attempted to implement it according to the package standards with a constructor and an interpolator (it also supports extrapolation). It supports interpolation in any number of dimensions, it has continuous first derivatives and feature both a 3rd and 4th order convergent implementation. The fact that this algorithm does not require continuous second derivatives can be an advantage in some cases, if one desires less overshoot than cubic splines achieves. This is especially true for the 3rd order cubic convolution interpolation, and as such it may be viewed as a compromise between splines and linear interpolation.
Kind regards, Nikolaj