Welcome to Doom9's Forum, THE in-place to be for everyone interested in DVD conversion.

Before you start posting please read the forum rules. By posting to this forum you agree to abide by the rules.

 

Go Back   Doom9's Forum > Announcements and Chat > General Discussion

Reply
 
Thread Tools Search this Thread Display Modes
Old 8th August 2015, 13:30   #1  |  Link
luquinhas0021
The image enthusyast
 
Join Date: Mar 2015
Location: Brazil
Posts: 270
Helping with image function

How can I find a function z = f(x,y) that passes through the k x p (Same thing of image resolution) values of an image (Values of one component: r, g or b; Y, Cb or Cr), and have a continuus and pretty accurate first, second and third partial derivates and full derivates?
If isn't possible discover a function for all k x p image points, is possible find a function for a block of a x a points? a x a is included in k x p.
I asked it because all polynomial interpolation methods generates a so expensive order polynoms, and, it seems, doesn't have continuus and pretty accurate derivates.
__________________
Searching for great solutions

Last edited by luquinhas0021; 8th August 2015 at 13:43.
luquinhas0021 is offline   Reply With Quote
Old 8th August 2015, 18:51   #2  |  Link
colours
Registered User
 
colours's Avatar
 
Join Date: Mar 2014
Posts: 308
I'm going to assume that you're once again asking about things that sounded ideal in your head but you didn't bother working out any of the details. Maybe you should.

If your image comes with partial derivative information (which is impossible), then yeah, you'd have to do a polynomial interpolation over the whole image. Which, apart from being slow to evaluate, also sounds like a totally wrong thing to do anyway because of Runge's phenomenon. It's possible to do some fancy stuff with bump functions to avoid this while remaining infinitely differentiable, but using bump functions is cheating so we don't do that.

Otherwise, in the one-dimensional case, if you want continuous derivatives of arbitrarily high order, you can use B-spline interpolation. (This is Θ(n) arithmetic operations per output pixel if you want continuous nth derivatives.) For more dimensions, just interpolate in each dimension separately and you'll get your continuous partial derivatives. Quartic and quintic B-spline interpolation give continuous derivatives up to the fourth order (but not the fifth), which sounds a bit like what you're asking for.
__________________
Say no to AviSynth 2.5.8 and DirectShowSource!

Last edited by colours; 8th August 2015 at 19:13. Reason: >counting
colours is offline   Reply With Quote
Old 8th August 2015, 19:35   #3  |  Link
wonkey_monkey
Formerly davidh*****
 
wonkey_monkey's Avatar
 
Join Date: Jan 2004
Posts: 2,048
Quote:
Originally Posted by luquinhas0021 View Post
How can I find a function z = f(x,y) that passes through the k x p (Same thing of image resolution) values of an image (Values of one component: r, g or b; Y, Cb or Cr), and have a continuus and pretty accurate first, second and third partial derivates and full derivates?
I may be wrong, but aren't there an infinite number of functions that can pass through any particular set of points? So how would you know which one was "accurate"? They'd all be "correct."
__________________
My AviSynth filters / I'm the Doctor
wonkey_monkey is offline   Reply With Quote
Old 9th August 2015, 13:52   #4  |  Link
LoRd_MuldeR
Software Developer
 
LoRd_MuldeR's Avatar
 
Join Date: Jun 2005
Location: Last House on Slunk Street
Posts: 13,177
Quote:
Originally Posted by davidhorman View Post
I may be wrong, but aren't there an infinite number of functions that can pass through any particular set of points? So how would you know which one was "accurate"? They'd all be "correct."
Yes, in general, there is an infinite number of functions that can pass through any particular set of points. But you can define some constraints in order to get a "smooth" and "natural-looking" (and unambiguous) curve.

For example, Cubic Splines are commonly used to create a function that passes through a particular set of points and that comes out "smooth".

The Cubic Spline is constructed, piecewise, of third-order polynomials. For each sub-interval, the current third-order polynomial has to go through the "starting" point and the "ending" point. That alone, would allow for an infinite number of solutions. But there is the additional constraint: At the "junction points", the first- and second-order derivatives of the "neighboring" polynomials have to be equal. This way, we get a smooth transition - rather than a "kink" - at the junction points.

Given these constraints, there is only one solution for any given set of points...
__________________
There was of course no way of knowing whether you were being watched at any given moment.
How often, or on what system, the Thought Police plugged in on any individual wire was guesswork.



Last edited by LoRd_MuldeR; 9th August 2015 at 18:19.
LoRd_MuldeR is offline   Reply With Quote
Old 11th August 2015, 06:00   #5  |  Link
luquinhas0021
The image enthusyast
 
Join Date: Mar 2015
Location: Brazil
Posts: 270
I don't like b-spline because it causes excessive smoothness.
After research over and over, I found the Hermite spline and the Clamped spline. In all sites is said that Clamped Spline has better accuracy than Natural Cubic spline, given same function and same dots. But the unique site that compares Hermite Cubic spline and Natural Cubic spline says that, given a same function and same dots, Hermite Cubic spline is more accurate. In image is no different: in fact, Hermite Cubic spline based resizer (Spline 144) gives a sharper and more detailed result than Natural Cubic spline based resizer (Spline 36. The results of it are compared with bicubic -0.001, 0.505). So, does someone know say to me if Clamped spline is more accurate than Hermite splines, given the same function and same dots, be an image or other data?
Increase the spline polynomial degree improves it accuracy, given same type of spline, such Hermite spline (Like make quintic Hermitespline)?
By the way, highest order spline, such sextic, septic, octic, nontic, tenth, eleventh, twelft and thirteenthhas continuum first, second and third derivatives?
Please, who knows, reply me.
__________________
Searching for great solutions
luquinhas0021 is offline   Reply With Quote
Old 11th August 2015, 06:32   #6  |  Link
feisty2
I'm Siri
 
feisty2's Avatar
 
Join Date: Oct 2012
Location: Providence, RI
Posts: 2,469
spline144 (aka 6tap spline), I'll take what you mean "accurate" by "more taps", well, 6 taps ain't no the biggest, try "taps=128" and welcome to the big bright world of "ringing"
https://en.wikipedia.org/wiki/Ringing_artifacts
__________________
If I got new ideas, will post here: https://github.com/IFeelBloated
feisty2 is offline   Reply With Quote
Old 11th August 2015, 11:24   #7  |  Link
foxyshadis
ангел смерти
 
foxyshadis's Avatar
 
Join Date: Nov 2004
Location: Lost
Posts: 9,556
Quote:
Originally Posted by feisty2 View Post
spline144 (aka 6tap spline), I'll take what you mean "accurate" by "more taps", well, 6 taps ain't no the biggest, try "taps=128" and welcome to the big bright world of "ringing"
https://en.wikipedia.org/wiki/Ringing_artifacts
Great. Now there's going to be a new "How to make spline65536 using nnedi3" thread tomorrow.
foxyshadis is offline   Reply With Quote
Old 11th August 2015, 11:26   #8  |  Link
luquinhas0021
The image enthusyast
 
Join Date: Mar 2015
Location: Brazil
Posts: 270
You're so funny, Feisty! I like Spline 144 'cause it retain much detail, more than others, and has less aliasing and less ringing than bicubic -0.001, 0.505; and is fast! Good algorithm, not?! But I'm worried about upscaling bigger than 2x, hence spline 144, although has little artifacts, even has it.
If you know about questions I did today, please, answer me!
__________________
Searching for great solutions
luquinhas0021 is offline   Reply With Quote
Old 11th August 2015, 19:16   #9  |  Link
colours
Registered User
 
colours's Avatar
 
Join Date: Mar 2014
Posts: 308
Quote:
Originally Posted by luquinhas0021 View Post
I don't like b-spline because it causes excessive smoothness.
lol no

Read this. And the articles it cites. Or at the very least, LoRd_MuldeR's post above if you can't handle all the ~mathematics~.

Quote:
Originally Posted by luquinhas0021 View Post
Hermite Cubic spline based resizer (Spline 144) [] Natural Cubic spline based resizer (Spline 36
lol no

Quote:
Originally Posted by luquinhas0021 View Post
By the way, highest order spline, such sextic, septic, octic, nontic, tenth, eleventh, twelft and thirteenthhas continuum first, second and third derivatives?
Please, who knows, reply me.
I somehow was psychic enough to have answered this question before you even posted it. If you can't read English, maybe you should go learn that before trying to do research in a field where most of the literature is in, guess what, English.
__________________
Say no to AviSynth 2.5.8 and DirectShowSource!

Last edited by colours; 11th August 2015 at 19:24.
colours is offline   Reply With Quote
Old 15th August 2015, 14:31   #10  |  Link
luquinhas0021
The image enthusyast
 
Join Date: Mar 2015
Location: Brazil
Posts: 270
According I see, at least Cubic B-spline image upscaling gives so smoother results, when compared with Bicubic. Maybe Bicubic B-spline gives sharper results.
Sure, Colours? In Spline resizer Avisynth documentation (Is that we see in External Filters, in Avisynth Wiki) tell us the same thing I spoke: Avisynth Spline internal resizers (Spline 16, Spline 36 and Spline 64), are based in Natural Cubic Spline. The other (External Spline resizers) are based in Cubic Splines, which is the same of Hermite Cubic Spline.
Yes, I understand English: read, write, listen and speak.
__________________
Searching for great solutions

Last edited by luquinhas0021; 15th August 2015 at 16:58.
luquinhas0021 is offline   Reply With Quote
Old 15th August 2015, 16:56   #11  |  Link
colours
Registered User
 
colours's Avatar
 
Join Date: Mar 2014
Posts: 308
Quote:
Originally Posted by luquinhas0021 View Post
In Spline resizer Avisynth documentation (Is that we see in External Filters, in Avisynth Wiki) tell us the same thing I spoke: Avisynth Spline internal resizers (Spline 16, Spline 36 and Spline 64), are based in Natural Cubic Spline. The other (External Spline resizers) are based in Cubic Splines, which is the same of Hermite Cubic Spline.
So, for the first time, because I almost thought I was wrong on the internet (truly an embarrassing plight to be in), I carefully went through Wilbert's description of Panorama Tools' "Spline" resampling kernels. Very carefully.

The kernels are defined piecewise. Within the interval [−n,n], it is defined as the natural cubic spline passing through the 2n+1 knots (0,1), (1,0), (2,0), , (n,0); outside [−n,n], it is defined to be 0. (n is the parameter corresponding to the number of taps on one side; i.e. n = 2 ⇒ Spline16; n = 3 ⇒ Spline36; etc.) The resulting kernel is not everywhere continuously differentiable, as the derivative has a jump discontinuity at n. As n tends to infinity, the kernels converge (uniformly) to the cubic B-spline interpolation kernel, so you might as well just use that directly. Going by the operation count, which is totally (not) a valid way of estimating algorithm speed, cubic B-spline interpolation should be about as fast as Spline64.

(Fun fact: swscale's "spline" kernel is also a cubic spline passing through those same knots, but without boundary conditions set. Instead, the function is defined to be equal to the cubic B-spline interpolation kernel over [0,1], and then extrapolated to [1,2], [2,3], [3,4], and so on. (Each such segment [k,k+1] is given by a cubic function, which has four coefficients. The four equations to solve these coefficients come from f(k) = 0, f(k+1) = 0, the continuity of f' at k, and the continuity of f'' at k.) This converges to the cubic B-spline interpolation kernel, modulo numerical stability issues because the associated linear map has an eigenvalue greater than 1.)

At any rate, just because the kernel was derived as a natural cubic spline doesn't mean that convolving with it is equivalent to natural cubic spline interpolation. Natural cubic spline interpolation is exactly the same as cubic B-spline interpolation with a specific set of boundary conditions. The cubic B-spline interpolation kernel has infinite support and is twice continuously differentiable, both of which are evidently untrue for Panorama's spline kernels.

Hermite splines are a different thing, and only force continuity of the first derivative, not the second. They're not related to Panorama's Spline kernels, and I have no idea where you even read anything making any claim otherwise.

If you want quintic Hermite splines, I suggest looking up what Hermite interpolation is and making the obvious conclusion.

Tl;dr: So yeah, you were technically correct to say Spline36 and Spline64 were based on natural cubic splines, but merely being "based on" doesn't mean much. You were also wrong in claiming that Spline144 was related to Hermite splines, so there.

PS: If you want cubic B-spline interpolation in AviSynth, you can use debilinear or debicubic for the prefiltering step. I'm not going to spoonfeed how to do this because (i) I shouldn't have to do all your work for you and (ii) I'm actually just really lazy.
__________________
Say no to AviSynth 2.5.8 and DirectShowSource!

Last edited by colours; 15th August 2015 at 17:09.
colours is offline   Reply With Quote
Old 15th August 2015, 19:32   #12  |  Link
wonkey_monkey
Formerly davidh*****
 
wonkey_monkey's Avatar
 
Join Date: Jan 2004
Posts: 2,048
I just subjected the spline resizers to a test - applying 256 rounds of down/upscaling with each resizer. Here are the results:



In order:
Original
spline16resize
spline36resize
spline64resize

Is there something wrong with spline36resize? See how it darkens the interior of the white curves in the top left, which the other two don't do.
__________________
My AviSynth filters / I'm the Doctor
wonkey_monkey is offline   Reply With Quote
Old 16th August 2015, 00:11   #13  |  Link
luquinhas0021
The image enthusyast
 
Join Date: Mar 2015
Location: Brazil
Posts: 270
Colours, I was wrong when I said B-spline generates a smoothest results. Thank for this correction, for anothers and for every other things you teach me.
__________________
Searching for great solutions
luquinhas0021 is offline   Reply With Quote
Old 23rd August 2015, 05:53   #14  |  Link
*.mp4 guy
Registered User
 
*.mp4 guy's Avatar
 
Join Date: Feb 2004
Posts: 1,350
Quote:
Originally Posted by davidhorman View Post
Is there something wrong with spline36resize? See how it darkens the interior of the white curves in the top left, which the other two don't do.
There is nothing wrong with spline36, the artifact you are seeing is called "being a linear interpolator with a third lobe (aka tap)" spline 64 also has the same problem if you look (very) closely, it is just obscured by the heaping amount of blur that the spline64 kernel has compared to spline36.
*.mp4 guy is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 00:40.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.