0

After having much trial and errors and failures, i decide to ask the question. Supposing that i have an array of red green and blue values as in here : http://pastebin.com/FatLy5FW and i also have written a function to generate a cubic Bezier curve and use it in image manipulation like color curves in gimp or other image editing software's. http://pastebin.com/hAxaYYGJ

How do i determine and set the control points, so that the output of the array of points generated by the bezier curve has same values as that of the values in the array in the former paste.

shortCircuit
  • 169
  • 2
  • 10
  • There seems to be an error in $b2, it should be `return (3 * $t * $t * (1-$t))` – David Jan 08 '14 at 23:49
  • can you actually show what you mean with a picture and maybe a more detailed description of "if I have points like ..., I would expect to end up with a curve that ..., which I can then use for ..."? If you want to do data fitting, Bezier curves are the least obvious choice, because they don't go through points, they circumnavigate a point set and only touch the start and end points. A Catmull-Rom spline might make more sense, but without a clear description of what you really need to do, that suggestion might be equally silly. – Mike 'Pomax' Kamermans Jan 09 '14 at 09:04
  • @Mike'Pomax'Kamermans i am actually trying to realize the color curves adjustments that is found in popular image editing softwares. And i am getting this feeling, Bezier Curve is not going to be a good solution for this problem. – shortCircuit Jan 09 '14 at 09:31
  • yeah, those don't use bezier curves, they generally use power functions (typically several that link up at their end points) – Mike 'Pomax' Kamermans Jan 09 '14 at 09:37
  • @Mike'Pomax'Kamermans can u please link up to atleast one resource. I mean if i get a little idea about this i may be able to do it. I know there are several image filter apps out there, my personal favourite being pixlr, but i didnot think making one would be so difficult. – shortCircuit Jan 09 '14 at 09:57
  • not without knowing exactly what you want to do. your question was about curve fitting, but now we discover that the true intent is to write an image filter. Those are two completely different things, so it's probably better to first start at what you truly want to do, and search on that. For instance, finding some tutorials on writing image filters. – Mike 'Pomax' Kamermans Jan 09 '14 at 10:04
  • i actually posted a question on how to develop algorithms for developing photo filters. but the question was put on hold. it has been nearly 3 weeks i have been dealing with this photo filter application. i did find tutorials on image filter, with the help of those i developed some very basic filters like contrast, brightness, sepia, grayscale, saturation using the colormatrices , and blur and sharpen with convolution matrices and a Vignette using RadialGradient. But i want to develop those effects like crossProcess, Lomo etc like those found in pixlr or picasa .. – shortCircuit Jan 09 '14 at 10:18
  • but i didnot find a single resource that describes how to produce those effects, the best i have found here at SO , which stated " replicate the action that were being performed in photoshop or gimp to produce that effect" . So i stumbled upon a github project named filtrr2. It looks that they were trying to use Bezier Curves as Color Curves, So i was trying to do the same too, until i realize its not happening. – shortCircuit Jan 09 '14 at 10:20
  • @Mike'Pomax'Kamermans .... – shortCircuit Jan 09 '14 at 21:20
  • 1
    the idea color curve (but really, intensity curve) correction is simply to take the linear range for an intensity (r, g, b, a, or a mix of two or more of those) and dampen or boost their value based on a function, or set of functions (where each function acts only on an interval of the input). Say you have have intensities from 0 to 255, then your leveling function could, for instance, be `f(i) = i*i - i`, the output of which you then map back to the interval [0,255]. You want a 1D function for this, or a 2D function with your input as one, and a controllable variable as the second option. – Mike 'Pomax' Kamermans Jan 10 '14 at 07:47
  • 1
    You can use loads of different functions for this, but Bezier curves (or really any parametric curve) is exactly the wrong class, because it doesn't model a simply f(x) -> y relation, but a far more complicated f(t) -> (x,y) - one input, multiple outputs, rather than the necessary one-or-more inputs, one output. Graphics applications tend to user power functions to achieve levelling, because they're nice and smooth, without touching the start/end poitns, but you can experiment with any simple f(x)->y function really. – Mike 'Pomax' Kamermans Jan 10 '14 at 07:50

1 Answers1

2

TL;DR Check out a better answer here: Algorithm for deriving control points of a bezier curve from points along that curve?

First, use the excellent search function on stackoverflow to find all questions that are similar to your problem. Like this: https://stackoverflow.com/search?q=fit+points+to+bezier+curve

Now I didn't see that until I had written a great wall of text. So I'm gonna share it, with the caveat that ultimately, there may be a simpler (and tested) solution among the search results.

A quadratic Bezier curve is defined by four control points. The mathematical notation (from wikipedia) is:

B(t) = (1-t)^3*P0 + 3(1-t)^2*t*P1 + 3(1-t)*t^2*P2 + t^3*P3

The line is guaranteed to go through the end points P0 and P3, but not P1 and P2. The equation should hold for every pixel on the curve. Each pixel has an x and a y coordinate. Select a pixel you know is on the curve - that's B(t). This translates to two equations, one for each coordinate. The unknowns are t, P1-x, P1-y, P2-x and P2-y since the control points have two coordinates each; a total of 5. If you only pick one point on the curve, you get 2 equations with 5 unknowns. But if we add a point, we get another t and end up with 4 equations and 6 unknowns. Add 2 more to get 8 equations and 8 unknowns. Since it's a linear equation system it can be solved using Gauss elimination. Stack overflow has answered questions about Gauss elimination so I suggest you implement one of those solutions, this one for example: Logic error for Gauss elimination

There are a number of pitfalls you need to watch out for:

  • Either use integers or floating-point numbers, consequently. Since the solution is going to be in integers (integer pixel values for the control points) it might be possible to use integers.
  • Don't assume that the pixels fit exactly to the curve, they may be up to 0.5 pixels away in either direction. This affects the accuracy of the answer. You can either do research to make sure it's within acceptable limits for your purposes, or you can do the calculation multiple times with randomly chosen points and select the points that fit the best.
  • If you do use a floating-point algorithm, beware of rounding errors. Floating-point 0.5 for example may not be stored exactly which could lead to 2*0.5 == 1 being false and other crazy stuff.
  • Take care to select good points. Ideally you'd want the pixels you pick evenly spaced on the curve. Check if it makes a difference if the pixels are clumped together instead of spaced out.

Update: it's actually not a linear equation system so my approach won't work. Check out the answer linked at the top instead.

Community
  • 1
  • 1
David
  • 943
  • 1
  • 10
  • 26
  • Maybe it is too late, but sorry I have a small question. When we add equations to get a system of 8 equations 8 unknowns(as you stated above) where the unkonwn are the coordinated of the points P1 and P2(two for each so we end up with 4 unkowns) and 4 t unkowns. However my question is that this system is a linear system ?? what about t multiplied by the points P1 and P2 ?? – Nizar Oct 20 '15 at 09:02
  • @Nizar you're right, it's not linear so Gauss elimination won't work. My mistake. – David Oct 21 '15 at 10:06
  • Thank yo for your reply. Indeed, I found a good way to find The Bezier curve giving n point. This is (the link) [http://www.mathworks.com/matlabcentral/fileexchange/15542-cubic-bezier-least-square-fitting] I post it just if someone would like to check this later . – Nizar Oct 21 '15 at 12:01