Progress on dewarping functionality
Moderator: peterZ

 Posts: 3
 Joined: 08 Sep 2010, 15:40
Re: Progress on dewarping functionality
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.)
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
 Posts: 773
 Joined: 03 Jun 2009, 13:50
 Ebook readers owned: iRex iLiad, Kindle 2
 Number of books owned: 4000
 Country: United States
 Location: Maryland, United States
 Contact:
Re: Progress on dewarping functionality
I think I very briefly tried something like this, using nonlinear regression to find tvalues. 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.Tulon wrote: Now, while hardcoding tension factors is fine, preassigning t values is generally not. If I don't, I believe the problem will become a nonlinear 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 Bsplines again, but might be applicable to Xsplines.
What formula did you use for the Xspline 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
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first allmechanical steampowered computer.
Re: Progress on dewarping functionality
That's exactly what we need.rob wrote:I think I very briefly tried something like this, using nonlinear regression to find tvalues.
We don't need that. 4 or 5 knots seems to always be enough.rob wrote:I do know that I wasn't able to fit the number of knots
OK, let's go.rob wrote:What formula did you use for the Xspline basis functions?
Assuming N is the number of knots and t is in range of [0, N1), 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)
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
Code: Select all
z = t  floor(t)
Scan Tailor experimental doesn't output 96 DPI images. It's just what your software shows when DPI information is missing. Usually what you get is input DPI times the resolution enhancement factor.
 rob
 Posts: 773
 Joined: 03 Jun 2009, 13:50
 Ebook readers owned: iRex iLiad, Kindle 2
 Number of books owned: 4000
 Country: United States
 Location: Maryland, United States
 Contact:
Re: Progress on dewarping functionality
Can you expand a bit on how this translates to (x,y) values? Thanks.
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first allmechanical steampowered computer.
Re: Progress on dewarping functionality
C values are 2component vectors.rob wrote:Can you expand a bit on how this translates to (x,y) values? Thanks.
Scan Tailor experimental doesn't output 96 DPI images. It's just what your software shows when DPI information is missing. Usually what you get is input DPI times the resolution enhancement factor.
 rob
 Posts: 773
 Joined: 03 Jun 2009, 13:50
 Ebook readers owned: iRex iLiad, Kindle 2
 Number of books owned: 4000
 Country: United States
 Location: Maryland, United States
 Contact:
Re: Progress on dewarping functionality
Oh, I see. So as t goes from 0 to N1, in theory the line will go from x=left margin to x=right margin. Got it.
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first allmechanical steampowered computer.
 rob
 Posts: 773
 Joined: 03 Jun 2009, 13:50
 Ebook readers owned: iRex iLiad, Kindle 2
 Number of books owned: 4000
 Country: United States
 Location: Maryland, United States
 Contact:
Re: Progress on dewarping functionality
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:
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:
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 computeintensive.
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.
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)
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);
}
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((cxxdata[i])*(cxxdata[i])+(cyydata[i])*(cyydata[i]));
}
return sum;
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.
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first allmechanical steampowered computer.
Re: Progress on dewarping functionality
Thanks a lot Rob, I'll try that over the weekend.
Scan Tailor experimental doesn't output 96 DPI images. It's just what your software shows when DPI information is missing. Usually what you get is input DPI times the resolution enhancement factor.
Re: Progress on dewarping functionality
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 ?
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 ?
Re: Progress on dewarping functionality
Do you mean the manual dewarping or have you tested line tracing in debugging mode?Klaus wrote:This functionality is awesome, thank you for the marvellous work! I compiled the current repository version and it worked perfectly on my images.
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.Klaus wrote: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 ?
Scan Tailor experimental doesn't output 96 DPI images. It's just what your software shows when DPI information is missing. Usually what you get is input DPI times the resolution enhancement factor.