Align Hole Punches

[dfort]

I'm doing some hand drawn 2D paper animation and would like to line up my scanned images using the hole punches. There are several commercial animation packages that can do this including Toon Boom, TV Paint, DigiCel Flipbook, Animo and probably a few others.

In addition, there is a free program specifically for this purpose called ScanFix - http://people.rit.edu/dpalyka/ScanFix.html - but it can only use TIFF files with Macintosh byte order--my scanner writes to a memory card in JPEG format. I tried converting the scans with imagemagick but the program seems to work only on files captured on a Macintosh via TWAIN in Photoshop. Although it is written in Java, it doesn't work at all on Linux.

It seems to me that it would be trivial to write a script that would line up a batch of scans to a reference image of a blank sheet of paper with just the hole punches. However, I'm not very skilled at coding and have no idea where to begin.

I made these scans with the scanner top open so the hole punches would show up better and so the built in automatic cropping wouldn't cut off any of the image.

Reference Image


Sample Scan (re-sized for this post)


Note that I'm using standard 1/4 inch 3-hole punched paper but the script should also be able to handle acme punched paper.


I'm currently solving this problem by temporarily taping a metal pegbar directly to the scanner's glass platen but the pegbar cannot stay attached permanently because the scanner is used for other purposes. Re-positioning the pegbar to the same position is pretty much impossible so if I need to do a fix on paper and re-scan a drawing, the entire scene needs to be re-scanned--Ugh! Going paperless and drawing on a Wacom tablet or Cintiq isn't an option.

Thanks for any help!

[GreenKoopa]

In addition, there is a free program specifically for this purpose called ScanFix - http://people.rit.edu/dpalyka/ScanFix.html - but it can only use TIFF files with Macintosh byte order--my scanner writes to a memory card in JPEG format. I tried converting the scans with imagemagick but the program seems to work only on files captured on a Macintosh via TWAIN in Photoshop. Although it is written in Java, it doesn't work at all on Linux.

So ScanFix is not an option regardless of what ImageMagick can do?

It seems to me that it would be trivial to write a script that would line up a batch of scans to a reference image of a blank sheet of paper with just the hole punches. However, I'm not very skilled at coding and have no idea where to begin.

ImageMagick can certainly rotate and translate an image with ease. (Scale, skew, and much more if needed.) The not-trivial part is automatically determining how much to rotate and translate. So non-trivial that I hope someone has a script to offer you as a starting point.

[dfort]

So ScanFix is not an option regardless of what ImageMagick can do?

No--it has good intentions but I can't get it to work reliably.

I'm thinking that using a template might be a good idea because ScanFix uses the first image as the "anchor" and all the other scans are aligned to it. If that first scan is skewed from the last batch, then all the scans will be skewed.

By the way, auto align using peg holes is quite common as many studios and students of animation have replaced their rostrum camera setups with scanners that have automatic document feeders.

ImageMagick can certainly rotate and translate an image with ease. (Scale, skew, and much more if needed.) The not-trivial part is automatically determining how much to rotate and translate. So non-trivial that I hope someone has a script to offer you as a starting point.

I would think somebody has already worked this out. It is similar to match-moving or removing camera shake in video editing but hopefully much simpler. However, no matter how much I Google I can't find any starting point on how to do this with imagemagick or Gimp. I'd rather use only free and open source software in my production pipeline.

[anthony]

You do not need a 'reference' image, though it could be some help.

The tricky part is not distorting the image to align them.
The tricky part is to find the location of the punch hole holes.
Those locations will give you the coordinates needed to do the distortion.

One method is to make a small image of the punch hole, and search the image for the location of the punch hole. This is a sub-image search and a number of methods exist, though "compare" is probably the simplest.

Matching Sub-Images and Shapes
http://www.imagemagick.org/Usage/compare/#sub-image

This however will generate a lot of false positives.

The better method is to program in an better understanding of the things you are searching for. And that requires morphology....
http://www.imagemagick.org/Usage/morphology/#basic

For example
convert bulldog.jpg -level 80,20% -morphology erode disk:4.3 bulldog_nolines.png
I first use -level to negate and increase the contrast of the imageto reduce the off-colors
The 'erode' then reduces the size of all lines and dots so that punch holes become a very very
small 'dot'.

Of course other parts will still remain, like the black edge, the nose and inside the mouth, but they will not be a small simple isolated 'dot'.

I can now find those dots (center of punch holes) using a 'peak' kernel and hit and miss
http://www.imagemagick.org/Usage/morphology/#hitmiss
http://www.imagemagick.org/Usage/morphology/#peaks
For example...
convert bulldog.jpg -level 80,20% -morphology erode disk:4.3 \
-morphology hitandmiss peaks:1.5,2.5 punch_holes.png

Take the two outermost pixel locations and use a 2 point Affine Distortion to align the original image (See Distort using control points)
http://www.imagemagick.org/Usage/distor ... rol_points

With those two points you can translate, rotate and scale the images to match!

For a image with 'acme' punched paper, the above (with approprite adjustments) will only find the center hole. That is your position adjustment (translation and center of rotation). A separate search from the two thinner long holes will then give it a line for the rotation of the image.

So you get a 'handle' for translation and a angle of rotation, but no scaling factor.
You fee those two items into a SRT distortion
http://www.imagemagick.org/Usage/distorts/#srt



Another method is to ignore the punch holes completely. Instead use the paper edge!

That may be easier to use to match up images. Fred Weinhaus as some edge detection scripts that will work perfectly for this, though his scripts work best when ALL the edges of the paper is visible. See his script "white board"
http://www.fmwconcepts.com/imagemagick/ ... /index.php

[dfort]

Wow, that's a lot of information to digest. I never even knew about morphology.

Interesting you should mention Fred's whiteboard script. I looked into the possibility of shooting the drawings with a hand held camera and running them through a script to square up the edges. However, the script requires you to specify the coordinates of the corners--not exactly an automated process. There are some edge and corner detection algorithms that are mainly used by "computer vision" developers but it seems that it might be possible using morphology.

corner.gif

Code: Select all

convert corner.gif -morphology HitAndMiss Corners hitmiss_corner.gif

hitmiss_corner.gif


Of course this works only with these super clean images but if we're talking about shooting photos of white paper on a black background it might be possible to get the corner locations and feed them into the whiteboard script.

However, not only am I in over my head right now, I'm also off topic. No matter how well a crookedly photographed or scanned image can be trued up--the critical alignment must be done using the peg holes.

[anthony]

You can feed it scanned images, if you include all the paper edges.

The corner inputs I think is for how to re-align the image (output corners). It should not be for corner inputs.

I was not suggesting using 'corner' in morphology, but finding the punch holes which are round!
Try the given commands on your bullbog image! you will get an image with three locations, the centers of the punch-holes. extract those pixels using threshold and txt: and get the two groups that are furthest from each other!

[dfort]

Sorry, I got off track. I ran your suggested commands and wow.

Code: Select all

convert bulldog.jpg -level 80,20% -morphology erode disk:4.3 \
-morphology hitandmiss peaks:1.5,2.5 punch_holes.png

By the way, I was in Brisbane, Australia--briefly, way back in 1976. Oops, I'm off topic again.

Now I've got to tweak the setting so it will work with the full-size scans and of course figure out the rest of the commands in order to line up a stack of drawings but this is a great starting place.

Thanks so much!

[anthony]

You only need to now get those small clusters down to pixel or sub-pixel coordinates.
But grabbing the two outside points will then let you align your images.

Please let us know how you make out, or if you need more help.

[dfort]

Well, I'm not making out all that great.

The bulldog.jpg file we've been working with is a scaled down (500x363) and rotated copy of the original scan. The original is portrait oriented and much larger (1696x2336). When I ran

Code: Select all

 convert SCAN0375.JPG -level 80,20% -morphology erode disk:4.3 \ -morphology hitandmiss peaks:1.5,2.5 punch_holes.png

on the original scan I got a black image. After playing around with the various settings and getting nowhere I started thinking--what happens if there are other black circles in the image, wouldn't it trip up this method? Also, how would I make this work reliably with Acme holes?

Basically, the scans are "pretty good" meaning that they only need to be adjusted slightly in order to get them in perfect alignment. I can also figure out where the center of the holes "should" be located. In any case, I started to check out other methods. Not that morphology isn't a brilliant solution, it's just that I can't get my head wrapped around it.

I thought that looking into some of Fred's imagemagick scripts might be a good starting place. After many failures I came up with a way to find all the coordinates in a shape (either round or acme) as long as the paper was placed on the scanner close enough to the right position so that feeding in the expected center doesn't totally miss the hole. Thanks to Fred Weinhaus for the floodfill tip.

Code: Select all

convert bulldog.jpg -fill red -fuzz 50% -draw "color 52.2,339.8 floodfill" txt:- | grep "red" | sed -n 's/^\(.*\):.*$/\1/p' > hole.txt

Of course the coordinates will eventually be fed into an array so that all the x and y points can be averaged together in order to find the center--am I correct on this? Here's where I got that tip:
http://archive.chipcenter.com/circuitce ... 201ts2.htm

This would seem like a fair place to start but I've still got a few issues. There shouldn't be a real need to make a temp image with one of the hole punched filled in red just to get the coordinates of all the pixels that floodfill finds so redirecting the output to text seemed to me the right thing to do. It is a bit slow on the small bulldog.jpg image but unbearably slow when I tried it on the original scan. There are 87 pixels colored in the small image but 1925 coordinates on the original. Another thing is that I'm coloring the hole red just because that's what some of the scripts I was examining were doing but wouldn't it be better if we go with "mask" instead of "color"?

I think this is a good start but there's much more to do and I'm taking it one baby step at a time. My pseudo code goes something like this:

Code: Select all

enter coordinates where hole 1 is supposed to be
get actual center of hole 1
enter coordinates of where hole 3 is supposed to be
get actual center of hole 3
determine where hole 2 (middle) is located - halfway between 1 and 3
move and/or rotate image using hole 2 as the pivot point //don't resize--all the scans should be the same dimensions

Sorry to ask such basic questions but am I on the right track with this?

[fmw42]

If the holes are the same size in all the images, then you could make a hole template image which is just the hole surrounded by a slight amount of white (or background color) as small square image. Then you could use

compare -metric rmse -subimage-search fullimage holetemplate resultimage

The second resultimage, ie resultimage-1 will be the similarity image and the bright areas will be the the best match. This would be similar to the example at viewtopic.php?f=1&t=14613&p=51076&hilit ... ric#p51076

However, you still need to find the brightest points in a each bright region.

[anthony]

Well, I'm not making out all that great.

The bulldog.jpg file we've been working with is a scaled down (500x363) and rotated copy of the original scan. The original is portrait oriented and much larger (1696x2336). When I ran

Code: Select all

 convert SCAN0375.JPG -level 80,20% -morphology erode disk:4.3 \ -morphology hitandmiss peaks:1.5,2.5 punch_holes.png

on the original scan I got a black image.

Note the size of the erode disk will need to be adjusted larger for the higher resolution image. It should not be so big as to erode the hole completely or so small the final 'center dots' is too big for the hit and hiss peaks search to find. (you may have to adjust that search too).

After playing around with the various settings and getting nowhere I started thinking--what happens if there are other black circles in the image, wouldn't it trip up this method? Also, how would I make this work reliably with Acme holes?

Once you have various posible locations, you will of course need to find them. Searching for
* three holes in a line, equidistant and a reasonable distance apart.
* or find them in a rough area. You could crop out that area first before the erode to make it easier.

There is no guarantee you will not get a match in the wrong spot, but with some you should be able to discount them.

I am sorry about the miss-lead on Freds whiteboard script. I thought it did find the rectangle corners, but it seems I was wrong. However even then their are ways of locating the pages using the paper edges rather than the holes, Look at his "unrotate" script which uses a different technique
http://www.fmwconcepts.com/imagemagick/ ... /index.php

Not that morphology isn't a brilliant solution, it's just that I can't get my head wrapped around it.

Erode just enlarges the black areas (of the negated image). The disk just makes it do so equally in all directions by the radius given. This gets rid of thin lines, and makes the holes smaller do a more precise center location can be found.

The hit and miss with 'peaks' just looks for small groups of pixels (white) completely surrounded by background (black) anything else is removed (to black) the two values are the inside and outside radius of the 'ring' of black pixels it is looking for.

I think this is a good start but there's much more to do and I'm taking it one baby step at a time.

baby steps is always good.

Sorry to ask such basic questions but am I on the right track with this?

I would say yes. As you say, baby steps.

[bwroga]

It's nine years since the original post, but I am trying to figure out how to locate the position of 'acme' elongated holes.

My idea was to repeatedly thin inwards from the top, bottom, left and right until just one pixel remains and will hopefully be the center of the hole.

This could even work for the rounded middle hole, and would work with different resolutions.

Does this seem to be a reasonable solution? Or am I overlooking something simpler?

[snibgo]

A suppose that in each scanned image, the holes are near to one edge. Correct? Is it the same edge for all images? If so, this reduces the search area, which can be cropped.

Better still, the cropped area contains just white paper, black holes and black paper-edge, with some noise. It that correct?

If so, then remove the edge and noise. That leaves three holes. Connected-components can find the centroid of each. This gives a scale (which may not be needed), rotation and translation.

[bwroga]

A suppose that in each scanned image, the holes are near to one edge. Correct? Is it the same edge for all images? If so, this reduces the search area, which can be cropped.

Better still, the cropped area contains just white paper, black holes and black paper-edge, with some noise. It that correct?

If so, then remove the edge and noise. That leaves three holes. Connected-components can find the centroid of each. This gives a scale (which may not be needed), rotation and translation.

Thanks snibgo. All your assumptions are correct, and I think that will work.

[snibgo]

What version of IM, on what platform? I'll assume IM v7, with Windows BAT.

I'll use the fierce dog scan from the OP. A real scan would be larger, and probably not JPG format.

Code: Select all

magick ^
  fiercedog.jpg ^
  -gravity South ^
  -crop 100x10%%+0+0 +repage ^
  -threshold 50%% ^
  -define connected-components:verbose=true ^
  -connected-components 4 ^
  null:

( For bash, change %% to %, and ^ to \ )

The text output is:

Code: Select all

Objects (id: bounding-box centroid area mean-color):
  0: 471x36+0+0 235.0,17.6 16684 srgb(255,255,255)
  2: 29x36+471+0 485.0,17.5 1044 srgb(0,0,0)
  3: 11x11+411+7 415.9,12.1 92 srgb(0,0,0)
  4: 11x10+47+8 52.1,12.5 88 srgb(0,0,0)
  5: 11x10+229+8 234.3,12.4 88 srgb(0,0,0)
  1: 1x4+207+0 207.0,1.5 4 srgb(0,0,0)

The holes are black, ie srgb(0,0,0). As the peg holes are about the same size, the three entries are clearly the ones with area 92, 88 and 88. So the centroids are (415.9,12.1), (52.1,12.5) and (234.3,12.4).

Of these three, the most central is at x=234.3 pixels. So to translate another scan to this one, move its central hole to (234.3,12.4).

For the rotation, we might rotate so the extreme holes are exactly horizontal. The distance between them is sqrt((415.9-52.1)**2+(12.1-12.5)**2) where "**2" means "squared". This is 363.8 pixels. The angle to make this line horizontal is asin((12.5-12.1)/363. = 0.063 degrees.

Note that an alternative is to align all scans to a master using the centroids of the holes. This avoids arithmetic in the script.

Can you take it from there? If you need help, I suggest you link to a couple of sample scans.