Align images using reference image

[Pash91]

I have a few scanned forms that are cropped differently, a little rotated, and feature other scanning issues. I'd like to make sure that they're all aligned correctly given one reference image. They should be the same dimensions, and the boxes should overlay one on top of the other so when doing subimage crops, I crop the same regions on all images.

Is this possible to do in an automated fashioned? I've played a little with removing the borders and trying to get the images closer together, but I'm still having issues with getting them perfectly overlayed.

[fmw42]

Imagemagick does not have any direct function to do that. But user snibgo has developed some techniques that combine IM functions to do something like that. See

http://im.snibgo.com/alignpnt.htm
http://im.snibgo.com/simpalign.htm

Probably the first is what you need. But he will have to comment further whether it applies to your images.

You might provide a couple of images and your IM version (if you have loaded it) and platform. You can post images to dropbox.com for free and put the URLs here. IM does not allow attachments, itself.

[Pash91]

Thank you, here are samples of 2 of the images:



I have many more of them and would like to align them to eachother. I'll take a look at the link you sent. I also noticed the limereg project. I compiled it, but there are no instructions on how to actually use it.

[Pash91]

I'm using:
Version: ImageMagick 6.9.0-0 Q16 x86_64 2015-02-11 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2014 ImageMagick Studio LLC
Features: DPC OpenMP
Delegates (built-in): autotrace bzlib cairo fftw fontconfig freetype fpx gslib jbig jng jpeg lcms lzma pangocairo png ps rsvg tiff webp x xml zlib

On both cygwin and a linux machine.

[fmw42]

If there is no scale change, you might consider just using -deskew on all of them to orient them so that the lines are horizontal and vertical. See http://www.imagemagick.org/script/comma ... php#deskew

[snibgo]

My script whatRot.bat doesn't find the correct rotation because the images are very sparse. "-deskew 40" works fine, as we see from:

Code: Select all

convert grid2.jpg grid1.jpg -deskew 40 -compose Darken -composite x.png

The rotation looks good. We see that we need a translation in y, and both a translation and scale in x. You could crop a square from each corner, find the box corners in one set of four corners, and search for them in the other four corners. This gives us four pairs of coordinates we can use for a perspective transformation. That's probably the most reliable method for these images.

[fmw42]

snibgo, could your script be changed to use detected corners where the line intersect using morphology to find the corners? Would that make sense. (Not asking you to do that, just wondering about feasibility)

[snibgo]

With a correlated search, http://www.imagemagick.org/Usage/convol ... ate_search , you mean?

The problem there is that the lines aren't clean. They would need to be cleaned: skeletonized, roughness smoothed out, gaps filled, whatever. Yuck. I suppose the scanned forms have been hand-written, so the script would also have to ignore that.

A simple search is quick, easy and effective:

Code: Select all

convert grid1.jpg -deskew 40 g1.png

convert grid2.jpg -deskew 40 g2.png

convert g1.png -crop 150x150+10+10 +repage g1a.png

convert g2.png -crop 150x150+10+10 +repage -fuzz 10% -trim +write info: +repage g2a.png

g2.png PNG 63x94 150x150+87+56 8-bit Grayscale Gray 256c 0.000u 0:00.000

compare   -similarity-threshold 0 -dissimilarity-threshold 1   -metric RMSE -subimage-search   g1a.png g2a.png   x.png

10896.9 (0.166276) @ 60,44

This tells us that coord (60,44) on g1a.png corresponds to (87,56) on g2a.png. Repeat for the four corners, for a perspective distortion.

This method would fail if the handwriting obscures the corners, or if the corners haven't scanned reasonably well.

[fmw42]

With a correlated search, http://www.imagemagick.org/Usage/convol ... ate_search , you mean?

The problem there is that the lines aren't clean. They would need to be cleaned: skeletonized, roughness smoothed out, gaps filled, whatever. Yuck. I suppose the scanned forms have been hand-written, so the script would also have to ignore that.

Yes, I see your point.

Locating the corners is not easy either, if you want to do it automatically, since there may be dark areas outside the bounds of the outer box. Thus one does not know exactly how much to crop without manual intervention.

[fmw42]

Another idea would be to do a Hough Line transform, which IM has. Then look for the line intersections of the longest (orthogonal) lines and take the 4 most distant intersections (presumably the outer box corners) for the match points. Then use those points to do an affine, bilinear or perspective transform with -distort.


see
http://www.imagemagick.org/script/comma ... ough-lines
viewtopic.php?f=4&t=25476


EDIT: It may even be easier. One could look for endpoints (of the longest lines) that are close together (if not identical) to find the outer box corners.

[snibgo]

Yes, Hough would work well:

Code: Select all

%IM%convert ^
  g1.png ^
  -negate ^
  -background #8ff -fill red ^
  -hough-lines 2x2+1000 ^
  +write lines.mvg ^
  h.png

From each MVG, a script can readily find the top-most and bottom-most lines, and left-most and right-most. The intersections and the coordinates required for the perspective distortion.

The coordinates can be obtained in a more graphical way by flood-filling corners:

Code: Select all

%IM%convert ^
  h.png ^
  -fill Lime ^
  -draw "color 0,0 floodfill" ^
  -fill Black +opaque Lime ^
  -bordercolor Black -trim +repage ^
  hr.png

The width and height of hr.png, plus 1, are the coordinates of the top-left intersection.

[fmw42]

a script can readily find the top-most and bottom-most lines, and left-most and right-most. The intersections and the coordinates required for the perspective distortion.

Yes, that is probably a better approach than mine above.

You can avoid writing to a file by writing to a string and then processing the string. In unix syntax, this would be

Code: Select all

list=`convert \
g1.jpg \
-negate \
-background "#8ff" -fill red \
-hough-lines 2x2+1000 \
+write MVG:- null: | cat -`

Code: Select all

echo "$list"

Code: Select all

# Hough line transform: 2x2+1000
viewbox 0 0 2550 3300
line 0,52 2550,52  # 1362
line 0,189 2550,189  # 1194
line 0,236 2550,236  # 1350
line 74,0 74,3300  # 1755
line 0,618 2550,618  # 1448
line 0,814 2550,814  # 1381
line 0,865 2550,865  # 1399
line 0,915 2550,915  # 1405
line 0,1076 2550,1076  # 1486
line 0,1130 2550,1130  # 1459
line 0,1292 2550,1292  # 1369
line 0,1347 2550,1347  # 1462
line 0,1596 2550,1596  # 1519
line 0,1647 2550,1647  # 1475
line 0,1895 2550,1895  # 1484
line 0,1947 2550,1947  # 1553
line 0,2567 2550,2567  # 1512
line 0,2680 2550,2680  # 1554
line 0,2734 2550,2734  # 1508
line 2403,0 2403,3300  # 1293
line 2406,0 2406,3300  # 1136
line 0,3135 2550,3135  # 1665
line 0,3296 2550,3296  # 2550
line 0,3297 2550,3297  # 2550
line 0,3298 2550,3298  # 2550
line 0,3299 2550,3299  # 2550

[snibgo]

Here is a complete solution, as a Windows BAT script. No calculations are done outside IM. It uses Hough lines, and assumes they are orthogonal so only finds the top-left and bottom-right corners.

Inputs are grid1.jpg and grid2.jpg, as provided by the OP. Outputs are g1.png (which is grid1.jpg deskewed and slightly cropped) and g2d.png (which is grid2.jpg deskewed and slightly cropped, and distorted to match g1.png).

The slight cropping is to get rid of paper-edge scanning artefacts.

It also makes gcomp.png, a composite of both outputs. This shows the match is very good, but one image has slight horizontal stretching at the middle-top.

Code: Select all

%IM%convert grid1.jpg -deskew 40 -crop 99%%x99%%+0+0 +repage +depth g1.png
%IM%convert grid2.jpg -deskew 40 -crop 99%%x99%%+0+0 +repage +depth g2.png

%IM%convert ^
  g1.png ^
  -negate ^
  -background #8ff -fill red ^
  -hough-lines 2x2+1000 ^
  h1.png

%IM%convert ^
  g2.png ^
  -negate ^
  -background #8ff -fill red ^
  -hough-lines 2x2+1000 ^
  h2.png

for /F "usebackq" %%L in (`%IM%convert ^
  h1.png ^
  ^( -clone 0 ^
    -fill Lime ^
    -draw "color 0,0 floodfill" ^
    -fill Black +opaque Lime ^
    -bordercolor Black -trim ^
    -format "X1A=%%[fx:w+1]\nY1A=%%[fx:h+1]\n" ^
    +write info: ^
    +delete ^
  ^) ^
  ^( -clone 0 ^
    -flip -flop ^
    -fill Lime ^
    -draw "color 0,0 floodfill" ^
    -fill Black +opaque Lime ^
    -bordercolor Black -trim ^
    -format "X1B=%%[fx:page.width-w-1]\nY1B=%%[fx:page.height-h-1]\n" ^
    +write info: ^
    +delete ^
  ^) ^
  NULL:`) do set %%L

for /F "usebackq" %%L in (`%IM%convert ^
  h2.png ^
  ^( -clone 0 ^
    -fill Lime ^
    -draw "color 0,0 floodfill" ^
    -fill Black +opaque Lime ^
    -bordercolor Black -trim ^
    -format "X2A=%%[fx:w+1]\nY2A=%%[fx:h+1]\n" ^
    +write info: ^
    +delete ^
  ^) ^
  ^( -clone 0 ^
    -flip -flop ^
    -fill Lime ^
    -draw "color 0,0 floodfill" ^
    -fill Black +opaque Lime ^
    -bordercolor Black -trim ^
    -format "X2B=%%[fx:page.width-w-1]\nY2B=%%[fx:page.height-h-1]\n" ^
    +write info: ^
    +delete ^
  ^) ^
  NULL:`) do set %%L

%IM%convert ^
  g2.png ^
  -distort Perspective ^
%X2A%,%Y2A%,%X1A%,%Y1A%,^
%X2A%,%Y2B%,%X1A%,%Y1B%,^
%X2B%,%Y2A%,%X1B%,%Y1A%,^
%X2B%,%Y2B%,%X1B%,%Y1B% ^
  g2d.png

%IM%convert ^
  g1.png ^
  g2d.png ^
  -compose Darken -composite ^
  gcomp.png

[Pash91]

Wow, you guys are awesome, thanks for the discussion and all the help on this. I just tried it out and it worked very well on everything but the left edge on the first image I uploaded. I've noticed that I've had very good luck with all the documents except that one. I had to use the virtual-pixel edge to blur it and trim and that has been the closest I've gotten. I don't know what it is specifically about that document that's not working well.

[snibgo]

What is wrong with the left edge? Are you running my script above? What results do you get?

My script is readily translated to bash:

Code: Select all

#!/bin/bash

convert grid1.jpg -deskew 40 -crop 99%x99%+0+0 +repage +depth g1.png
convert grid2.jpg -deskew 40 -crop 99%x99%+0+0 +repage +depth g2.png

convert \
  g1.png \
  -negate \
  -background "#8ff" -fill red \
  -hough-lines 2x2+1000 \
  h1.png

convert \
  g2.png \
  -negate \
  -background "#8ff" -fill red \
  -hough-lines 2x2+1000 \
  h2.png

declare `convert \
  h1.png \
  \( -clone 0 \
    -fill Lime \
    -draw "color 0,0 floodfill" \
    -fill Black +opaque Lime \
    -bordercolor Black -trim \
    -format "X1A=%[fx:w+1]\nY1A=%[fx:h+1]\n" \
    +write info: \
    +delete \
  \) \
  \( -clone 0 \
    -flip -flop \
    -fill Lime \
    -draw "color 0,0 floodfill" \
    -fill Black +opaque Lime \
    -bordercolor Black -trim \
    -format "X1B=%[fx:page.width-w-1]\nY1B=%[fx:page.height-h-1]\n" \
    +write info: \
    +delete \
  \) \
  NULL:`

declare `convert \
  h2.png \
  \( -clone 0 \
    -fill Lime \
    -draw "color 0,0 floodfill" \
    -fill Black +opaque Lime \
    -bordercolor Black -trim \
    -format "X2A=%[fx:w+1]\nY2A=%[fx:h+1]\n" \
    +write info: \
    +delete \
  \) \
  \( -clone 0 \
    -flip -flop \
    -fill Lime \
    -draw "color 0,0 floodfill" \
    -fill Black +opaque Lime \
    -bordercolor Black -trim \
    -format "X2B=%[fx:page.width-w-1]\nY2B=%[fx:page.height-h-1]\n" \
    +write info: \
    +delete \
  \) \
  NULL:`

convert \
  g2.png \
  -distort Perspective \
$X2A,$Y2A,$X1A,$Y1A,\
$X2A,$Y2B,$X1A,$Y1B,\
$X2B,$Y2A,$X1B,$Y1A,\
$X2B,$Y2B,$X1B,$Y1B \
  g2d.png

convert \
  g1.png \
  g2d.png \
  -compose Darken -composite \
  gcomp.png

This works fine with Cygwn's bash. I'd be grateful for reports of whether it works in other environments (Max, Linux, whatever).