(De-)Warping an image with a book

[sandreas]

Hello,

i am trying to perform a simple warp operation for a book page. Here is my Algorithm:

Detect Book Corners (works)

Compute width (topRight.x - topLeft.x + bottomRight.x - bottomLeft.x) / 2 and height (similar to width) (works)

Detect Book Edge-Lines, all Points for top, right, bottom, and left  (works)

Compute the Warp-Target-Rectangle (topLeft.x, topLeft.y, width, height) (works)

Compute the Warp-Point-Association and perform the warp (does not work, but partially)

I am trying this with the Remove-Perspective-Distortion example (see http://boofcv.org/index.php?title=Example_Remove_Perspective_Distortion). It works, if i use the four Corner-Points for associatedPairs, but if i use the complete Border, it does not work, as expected (image is totally twisted. Here is some code, that my approach is more understandable

// Specify the pixel coordinates from destination to target
ArrayList<AssociatedPair> associatedPairs = new ArrayList<AssociatedPair>();

// Projection for the 4 Corners, DOES Work
Point2D_F64 pointSource = new Point2D_F64(topLeft.x, topLeft.y);
Point2D_F64 pointDest = new Point2D_F64(minX, minY);
associatedPairs.add(new AssociatedPair(pointDest, pointSource));
pointSource = new Point2D_F64(topRight.x, topRight.y);
pointDest = new Point2D_F64(maxX, minY);
associatedPairs.add(new AssociatedPair(pointDest, pointSource));
pointSource = new Point2D_F64(bottomRight.x, bottomRight.y);
pointDest = new Point2D_F64(maxX, maxY);
associatedPairs.add(new AssociatedPair(pointDest, pointSource));
pointSource = new Point2D_F64(bottomLeft.x, bottomLeft.y);
pointDest = new Point2D_F64(minX, maxY);
associatedPairs.add(new AssociatedPair(pointDest, pointSource));

// Projection for all borders, does not work

int destX = topLeft.x;

int destY = topLeft.y;

for(Point2D_F64 pointSource: top) {

    Point2D_F64 pointDest = new Point2D_F64(destX, destY);

    associatedPairs.add(new AssociatedPair(pointDest, pointSource));
    destX++;

}

// do that for top, right, left and right

// ....

 
// Compute the homography
DenseMatrix64F H = new DenseMatrix64F(3,3);
computeHomography.process(associatedPairs, H);
 
		// Create the transform for distorting the image
PointTransformHomography_F32 homography = new PointTransformHomography_F32(H);
PixelTransform_F32 pixelTransform = new PointToPixelTransform_F32(homography);
 
// Apply distortion and show the results
DistortImageOps.distortMS(input,output,pixelTransform,true, TypeInterpolate.BILINEAR);
 

Why does this not work and is there a possibility to do the dewarping?

Sample-Image:

Link: http://abload.de/image.php?img=image_with_corners_makzacf.jpg

[sandreas]

Perhaps i also should state out my primary approach: I am working on a bookscanner, which, obviously, should do the following things:

• Find the borders of the book
  
• Extract the book pages
  
• Perform some image optizations
  
• Dewarp the text, so that it is best readable
  
• Embed OCR-Data as invisible layer, so that the book is searchable
  

The bookscanner is a console app, so everything should be performed automatically, best without any settings but input-path and output-file. It is working quite well, but there are things, that should be improved:

• Dewarping: Uses the 4 Corners instead of a more sophisticated approach
  
• OCR Embedding: Uses the external free Software "PDF X-Change Viewer", instead of a integrated approach with an ocr lib
• Page-Detection (actually, my approach is very very simple and it will not work on single page scans)
• Perform Image optimizations: Local Thresholding and Text-Smoothing produce impressive results for text only, but when there are images on the pages, they have bad quality after thresholding

Now, back to dewarping, i spent some time for researching and found the following:

ImageJ-Plugin, that does Warping very sophisticated: 

http://biocomp.cnb.csic.es/~iarganda/bUnwarpJ/

ImageJ-Plugin, that reconstructs a 3D Model out of color differences: 

http://rsb.info.nih.gov/ij/plugins/surface-plot-3d.html

Here is a picture of 3D-Reconstruction my 2D book-pages:

http://abload.de/image.php?img=3d-plotftpci.jpg

Papers, how 3D-Reconstruction can be done (3D to 2D unfolding): h

ttp://webee.technion.ac.il/~ayellet/Ps/STL06.pdf

http://people.csail.mit.edu/dran/paper/An2014icra.pdf

It would be great, if there was a possibility to do a 3D-Unwarp / unfold, but i think this is not in the scope of boofcv. 

JH-LABS great Filter-Lib, which is indeed very sophisticated, but not half as fast as boofcv:

Warp-Filter: http://www.jhlabs.com/ip/filters/WarpFilter.html

List of all available Filters: http://www.jhlabs.com/ip/filters/

Download Sourcecode (Apache 2 License): http://www.jhlabs.com/ip/filters/download.html

[Peter A]

Can you show an image which demonstrates how BoofCV is distorting your image?  Your code looks right, assuming (minX,minY) = (0,0) and (maxX,maxY) = (width-1,height-1) of the output image.  It won't be perfect because your pages are not perfectly flat.

Thanks for looking up those interesting projects/papers!  Some of that could work its way into BoofCV some day.  When code gets added is a function of applicability to a high level goal and implementation complexity.  For example, the Otsu and Sauvola were fairly easy to implement and turn out to be useful for detecting fiducials too.  Would be nice if there was built in OCR functionality, but other tasks have higher priority right now.

- Peter

--
You received this message because you are subscribed to the Google Groups "BoofCV" group.
To unsubscribe from this group and stop receiving emails from it, send an email to boofcv+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
"Now, now my good man, this is no time for making enemies."    — Voltaire (1694-1778), on his deathbed in response to a priest asking that he renounce Satan.

[sandreas]

Well, my pleasure :-) I'm glad, that you take care of it.

Quote: assuming (minX,minY) = (0,0) and (maxX,maxY) = (width-1,height-1) of the output image

Perhaps it has something to do with the fact, that i do not use the full size of the output image as warp target, I'll check that later.

Here is a pastebin (just the code, to take a quick look):

http://pastebin.com/aQwW7UsS

I uploaded the sample (with images) to do further experiments here: 

http://www40.zippyshare.com/v/73224464/file.html

It is not perfectly clean code but it should be understandable. The Corner-Find-Algorithm is not relevant for the sample, so i used fix values to compare in the for loop ( // switch edge: top -> left, etc.). As you will see, i look for the borders and then add a point association for each of the border points mapping it to the warpTarget rectangle. Top line works, right also kind of works. But if i begin adding warpDestination-Points to the right, something weird happens to the lowerLeft corner.

I also impilemented the 4-corners-warp (findCornerPointAssociations), which works nicely.

Thank you very much for your help :-)

[sandreas]

Next try. Changelog:

• Output-Image with changed dimensions (warpTarget-Rectangle size instead of source image size) ==> does not help
  
• new Method findMorePointAssociations, which uses the corners and the middle point between the corners => seems to work, but there is something wrong (looks like a slight /_\ distortion is produced)
  
• Added the missing Point-Associations for Full Distortion, which totally messes it up (seems, that i did something wrong, i'm working on it)
  

http://pastebin.com/eCLgc0vG

[Peter A]

Technically the min/max doesn't need to the be output image's corners.  Looking at the dewarped image it appears that the corners are a bit off.  I would expect the output book to rectangular or at least close to that if done correctly.  My advice is to try to recreate the example in BoofCV. As in, put a picture flat on a table then take a photo of it from an angle.  Then manually select the corners and see if you can remove the perspective distortion.  As mentioned before, since the pages are not flat you won't be able to remove all the distortion from the book. That program you showed which estimates the 3d structure of the book probably does a better job.

- Peter

[sandreas]

Hey Peter,

i did some research for the image warping / distortion task and wanted to share my results. It seems, that the way distortion is done in boofcv does not fit my needs (perhaps it is a bug, i still need to verify this).

For my task, the warping approach of the following paper will work better i think. I am on it.

Paper: http://faculty.cs.tamu.edu/schaefer/research/mls.pdf

Projects that use this papers proposal:

https://code.google.com/p/imgwarp-opencv/

https://github.com/cxcxcxcx/imgwarp-js/ (http://chenxing.name/fun/imgwarp-js/)

Other interesting Links:

http://www.fmwconcepts.com/imagemagick/meshwarp/index.php

http://www.codeproject.com/Articles/21981/Image-Warping-Using-Linear-Interpolation-and-Doubl

http://www.codeproject.com/Articles/3419/Image-Processing-for-Dummies-with-C-and-GDI-Part

[sandreas]

Oh, i forgot:

http://www.codeproject.com/Articles/706984/Image-Warping-using-Simplified-MLS-in-Csharp-WPF

Am Mittwoch, 6. August 2014 14:21:49 UTC+2 schrieb Peter:

[sandreas]

Got it, i ported the papers warp algorithm and it works as expected. As you see in the image, the borders are warped correctly now and completely straight (disregarding the fingers and other little mistakes). I did not change my initial Algorithm to detect border points / calculate the warp associations, so the calculation here was correct.

Unfortunately the resulting text is not straight at all because of the uneven borders, like you did already mention, but perhaps this "new" Warp-Algorithm is useful for boofcv. It'll need huge refactoring, but for now it seems to work. Additionally it could be a bit faster than the existing distortion removal algorithm in boofcv (my subjective impression, i did not measure it). If you wish to see it, I'll submit the code, as soon as it is ready refactored.

For straightening the text I'm Working on a text-line-detection / line slope algorithm. I think this would be the right strategy for straighten up the text.

In addition to that I ported back your Sauvola implementation (thanks man!) to my own code and combined it with a global otsu threshold. The thresholding result for text is impressive (no artefacts any more, as you see in the image) and quite fast, because no local thresholding is needed any more. Usage:

- Apply Sauvola on original image (radius=15, k=0.1f)

- Apply Otsu on original image

- Make all pixels white, that are white on both images

Before doing the Thresholding, I apply an AutoContrast-Filter, which is based on YUV / YCbCr color model. It applies perfect for this image. Just ask, if you would like to see the code for it.

Am Mittwoch, 6. August 2014 14:21:49 UTC+2 schrieb Peter:

[Peter A]

Sure could you post the code?  Is the warping done by using the 4 corners of the book as control points?

- Peter

[sandreas]

Hey Peter,

slightly better performance here. Same AssociatedPairs-ArrayList as in youre "Distortion Removal Example":

Am Freitag, 22. August 2014 20:00:42 UTC+2 schrieb Peter:

Sure could you post the code?  Is the warping done by using the 4 corners of the book as control points?

- Peter

On Tue, Aug 19, 2014 at 5:48 PM, sandreas <andreas....@googlemail.com> wrote:

Got it, i ported the papers warp algorithm and it works as expected. As you see in the image, the borders are warped correctly now and completely straight (disregarding the fingers and other little mistakes). I did not change my initial Algorithm to detect border points / calculate the warp associations, so the calculation here was correct.

Unfortunately the resulting text is not straight at all because of the uneven borders, like you did already mention, but perhaps this "new" Warp-Algorithm is useful for boofcv. It'll need huge refactoring, but for now it seems to work. Additionally it could be a bit faster than the existing distortion removal algorithm in boofcv (my subjective impression, i did not measure it). If you wish to see it, I'll submit the code, as soon as it is ready refactored.

For straightening the text I'm Working on a text-line-detection / line slope algorithm. I think this would be the right strategy for straighten up the text.

In addition to that I ported back your Sauvola implementation (thanks man!) to my own code and combined it with a global otsu threshold. The thresholding result for text is impressive (no artefacts any more, as you see in the image) and quite fast, because no local thresholding is needed any more. Usage:

- Apply Sauvola on original image (radius=15, k=0.1f)

- Apply Otsu on original image

- Make all pixels white, that are white on both images

Before doing the Thresholding, I apply an AutoContrast-Filter, which is based on YUV / YCbCr color model. It applies perfect for this image. Just ask, if you would like to see the code for it.

[sandreas]

More Information:

Performance: 4.091s (boofcv) vs. 3.201s (new approach)

Screenshot: http://abload.de/img/boofcvperformancerwkqi.jpg

Usage: 4 corner Points as associated pairs

Result: boofcv result is more exact using 4 points, new approach is more exact using more than about 10 points (e.g. full contour results in nearly straight edges)
Progress: Refactoring is almost done. I think i still can boost it a bit. It already uses Point2D_F64 and MultiSpectral<ImageFloat32> types from boofcv

Perhaps you can tell me a bit more about the quality of the new approach itself, i don't even exactly understand how it works :-) Hopefully it really is an improvement for boofcv. I'll post a full example at pastebin as soon as i can.

A few questions remain. The new approach uses following Math. Is there an implementation in boofcv or its dependencies, which could boost performance?

2x2 Matrix: determinant, multiply, adjugate,inverse, etc.

Point: InfintyNormDistanceTo, add, substract, etc.

[sandreas]

Here it is, finally. A full dewarp example with the new approach including dependencies.

http://www12.zippyshare.com/v/77436721/file.html

Things you should now:

• Main-Class is "NewWarp.java"
  
• The method loadPointAssociations can either load "corners-only" or "full-edge" associations via uncommenting one line (hardcoded, detected and exported with a simple, before mentioned border detection algorithm, so it is not perfect at all, but it gets the edges straight :-)
  
• Sample-Image is included (data/images/bookphoto.jpg)
  
• There is a "new" rotation-filter part of the package, because the edges were detected after a 180 degree rotation (perhaps here is another boofcv improvement possible, the rotation-filter automatically changes size of the image and dimensions, depending on the content after rotation)
  
• I only ported https://github.com/cxcxcxcx/imgwarp-js/ to java and optimized it a bit. It uses MIT-License, but this is not fully my creation, so please be sure to avoid licensing issues. For my part of the work: You can use and change every part of it to improve boofcv, but without any warranty :-)

Feedback is welcome, i hope it works :-)