Anyway. I was also thinking about "rolling my own" aligner, even though
I haven't started yet. But since you have already tried... have you
tried adding artificial marks to the scan?
Yes, I started out by writing a "global" alignment program. However,
the problem was this takes a very long time to run! It's virtually
impossible to do the ~120 MB files I'm working with.
So, I limited the alignment to a 500x500 or 1000x1000 pixel square in
the middle of the image. To my surprise I then discovered that the
corners were out of alignment - and often in opposite directions!!!
So, I then put 4 anchor points in all corners with variable offset
from the edge to try out different settings. This improved things but
then the middle was often out of alignment! Aaaarrrggg!
So, the next step is to overlay a matrix of points across the whole
image and align based on that. The problems are many... For one, it
takes a very long time to correlate all those points! But first of all
I have to determine the minimum distance between individual points.
In other words, I need to establish the rate of misalignment. This is
not easy as misalignment is different with each scan! So I'll have to
average...
What I find most frustrating is that the firmware does *not* allow
scanning each line individually. If that were implemented there would
be no need for alignment!
I could then not only do multiple exposures "in situ" but also
multiple focus settings! And then advance the stepper motor to the
next line! That would be fantastic! Not only would the dynamic range
be perfect but I could have every point in focus (my cardboard mounted
Kodachromes are quite warped).
For example, you could print evenly-spaced marks (thin lines, for
example) on a strip of paper, and place that strip of paper next to the
film.
After you've got the scans, wouldn't alignment be easier and faster if
performed on the marks instead of on the image?
Perhaps even the film holes could be used as marks, if the scanner
doesn't allow scanning an area larger than the film.
The problem, as I hinted above, is that the misalignment is in all
directions. So you can't rely on edges alone. Well, at least that's
what happens on my Nikon LS-50.
Also, can you explain shortly the kind of algorithms you worked with?
I have no clue how "real" programs do it; to begin with, I thought of
just writing a shell script that uses the Netpbm tools.
In particular, these commands sound interesting:
pnmpsnr measure difference between two images
pgmedge edge-detect a PGM image
I didn't know either how the real programs did this. First, I tried
figuring it out for myself and "invented" bilinear interpolation only
find out about it later.
Next I spent weeks on the Net and did a lot of reading/learning. It's
all quite complicated and I didn't want to spend too much time
digressing but essentially it involves two steps: correlation and
interpolation.
Correlation is a mathematical process in order to determine the
"similarity" of two items. It involves floating point math which is
why it takes such a long time.
Once the sub-pixel (mis)alignment is established interpolation is used
to shift the images. There are different methods and the most common
are bilinear, biquadratic and bicubic. All of them cause blurring
whereby bilinear causes most, but it's the fastest, and bicubic causes
least, but it's very time consuming.
I thought there was also a command to "measure an image's sharpness" or
something like that, but I can't find it anymore. No idea how it was
supposed to work, assuming I haven't just dreamed it existed.
I'm not familiar with Netpbm tools but I'm sure there are many Linux
libs for this. I work on a Windows machine and since this is "labor of
love" I wanted to do everything myself rather than use existing
libraries. Of course, that's very time consuming...
I would basically just move one of the two images randomly and take a
measurement, either with pnmpsnr or by creating a third image with
pgmedge and seeing how bright it is.
Then I would iterate the process until pnmpsnr gives me a high enough
value, or the brightness of the pgmedge-generated image gets low
enough.
I did correlation in two steps: full pixel alignment, and then
sub-pixel alignment. In each case I specify a "radius" where to
search.
For example, I know from empirical data that my scans are never more
than 1 pixel apart, so I specify a radius of 2 pixels, just in case.
This means, I have to compare each pixel to 25 pixels in the other
image!
Once that's done, I do sub-pixel alignment. After a lot of empirical
testing I settled on 4 divisions per axis. And that means 49 sub-pixel
positions to compare each pixel to!
At every iteration, I would reduce the range for random motion, based
on pnmpsnr's or pgmedge's feedback. However, I'm afraid both programs
would give me steadily meaningless results while the images are badly
aligned, and only start working correctly when they are already
almost-well-aligned.
That's why I do the rough full-pixel alignment first.
In theory, one should compare each pixel in one image to *all* pixels
in the other image, and do that at every sub-pixel division!
Not enough time in this Universe to do that ;o) so I settled on the
above process.
Don.
)