Progress on dewarping functionality

[ArchCarrier]

Thank you - it works wonderfully. I can't wait for the automatic dewarper!

If I may make a suggestion: the first part of the dewarping functionality (setting the four points around the text) might be split into a seperate function (maybe even incorporated in the Deskew or Select Content tabs). This way, scans that are keystoned (like a trapezium) but not curved could probably be processed a lot quicker.

(Of course, I have no idea of the workings of Scan Tailor, but I assume that a perspective correction like keystoning takes less processing power than straightening curved lines.)

[rob]

Now, while hardcoding tension factors is fine, pre-assigning t values is generally not. If I don't, I believe the problem will become a non-linear least squares one. That's something beyond my maths skills, but I know you can do it. Take a look at this paper as well. It may be an overkill for our purposes, but who knows. It's about B-splines again, but might be applicable to X-splines.

I think I very briefly tried something like this, using nonlinear regression to find t-values. I'll have to look through my notes to see what I did. In any case, I'll take a look at the paper, get the basic equations, and see if I can derive the expressions required for nonlinear regression. I do know that I wasn't able to fit the number of knots, just the positions of the knots based on a fixed number of knots.

What formula did you use for the X-spline basis functions?

You will probably have to find an open source C library that does nonlinear regression. This is probably a very good one, under GPL: http://www.gnu.org/software/gsl

[Tulon]

I think I very briefly tried something like this, using nonlinear regression to find t-values.

That's exactly what we need.

I do know that I wasn't able to fit the number of knots

We don't need that. 4 or 5 knots seems to always be enough.

What formula did you use for the X-spline basis functions?

OK, let's go.
Assuming N is the number of knots and t is in range of [0, N-1), we get:

Code: Select all

spline(t) = (C[floor(t)-1] * A0 + C[floor(t)] * A1 + C[floor(t)+1] * A2 + C[floor(t)+2] * A3) / (A0 + A1 + A2 + A3)

Where C is an array of N control points. Accessing C[< 0] gives us C[0] and accessing C[>= N] gives us C[N-1].
Now let's further assume all the tension factors are set to 1. In reality I set it to zero at endpoints, to force the spline go through those endpoints, but for simplicity let's assume all of them are set to 1. Then we get:

Code: Select all

A0 = 2 * (0.5 - 0.5*z)^3 + (0.5 - 0.5*z)^4 - 2 * (0.5 - 0.5*z)^5
A1 = 2 * (1 - 0.5*z)^3) + (1 - 0.5*z)^4 - 2 * (1 - 0.5*z)^5
A2 = 2 * (0.5 + 0.5*z)^3 + (0.5 + 0.5*z)^4 - 2 * (0.5 + 0.5*z)^5
A3 = 2 * (0.5*z)^3 + (0.5*z)^ 4 - 2 * (0.5*z)^5

Where

Code: Select all

z = t - floor(t)

[rob]

Can you expand a bit on how this translates to (x,y) values? Thanks.

[Tulon]

Can you expand a bit on how this translates to (x,y) values? Thanks.

C values are 2-component vectors.

[rob]

Oh, I see. So as t goes from 0 to N-1, in theory the line will go from x=left margin to x=right margin. Got it.

[rob]

Hmm, so it seems that you have a set of data points to fit (x,y), and a parameterized curve x(t), y(t). Rather than use nonlinear regression, let's treat this as a minimization. Given your N knots, define function f to be the sum of the distances of your data points to the spline curve. Obviously the closer the curve is to the data points, the lower f is. By minimizing f with respect to the knot coordinates, we end up with a spline curve that is closest to the data points -- or at least, you will find a local minimum of f.

For minimization, first we define f. The GNU GSL library defines f as follows:

Code: Select all

double (* f) (const gsl_vector * x, void * params)

Here, the vector x will consist of the N knots, and params is null -- these are actually fixed parameters to the equation to be minimized. We have no fixed parameters.

We first extract the knot values from vector as follows:

Code: Select all

double xknot[N], yknot[N];

for (int i=0; i<N; i++)
{
  xknot[i] = gsl_vector_get(x, 2*i);
  yknot[i] = gsl_vector_get(x, 2*i+1);
}

Next, we have to decide on a distance measure. Probably the simplest is to use the vertical distance between each data point to the curve. However, we cannot iterate over the data points because then we would need to solve a quintic equation to determine the location of the curve. Rather than do that, we'll do something equivalent, which is iterate t from 0 to N with a given step size (you can put that step size in the params array if you want). Then, you can either sum up the distance from each such point on the curve to every data point, or you can find the data point that is closest and use that distance. They are equally compute-intensive.

Code: Select all

double sum = 0;

for (double t=0; t<N; t+=step_size)
{
  double cx, cy;

  // Compute curve (cx,cy) at t here, which is left as an exercise for the Tulon :)

  for (int i=0; i<data_set_size; i++)
    sum += sqrt((cx-xdata[i])*(cx-xdata[i])+(cy-ydata[i])*(cy-ydata[i]));
}

return sum;

This function goes into a variable of type gsl_multimin_function, along with n (=2N) and params (=null).

At this point, you need merely to call gsl_multimin_fminimizer_nmsimplex2 with your gsl_multimin_function. You need to provide an initial set of knot coordinates that is "good enough", and you can do that, for example, by choosing the x coordinates to be uniform across the line, and then use the y coordinates closest in the data set.

See here for further details on minimization using the GSL library. The chapter Multimin Algorithms without Derivatives is where you'll find the reference to gsl_multimin_fminimizer_nmsimplex2.

[Tulon]

Thanks a lot Rob, I'll try that over the weekend.

[Klaus]

Hello,
This functionality is awesome, thank you for the marvellous work! I compiled the current repository version and it worked perfectly on my images.

May I wonder, even if this is still under developement, if it is already possible to use this on a big number of images without having to set the curves on each ?

[Tulon]

This functionality is awesome, thank you for the marvellous work! I compiled the current repository version and it worked perfectly on my images.

Do you mean the manual dewarping or have you tested line tracing in debugging mode?

May I wonder, even if this is still under developement, if it is already possible to use this on a big number of images without having to set the curves on each ?

It's not complete yet. Close, but still not quite there. As for the success rate, I don't have any data on that, as I am only testing it on the two pages from the progress update videos. I am trying to make it as robust as possible though.