Detecting lines in image, rotating based on that line's angle

Discuss digital image processing techniques and algorithms. We encourage its application to ImageMagick but you can discuss any software solutions here.
Post Reply
friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-11T07:44:35-07:00

We have some custom built software to reconstruct encoded color information in black and white 16mm film scans, using the lenticular kodacolor process (a film format from the late 1920s-early 1930s). Essentially, there are lenticular prisms on the film and a filter in front of the lens that splits up the color, "encoding" the color on the B/W film. On projection through the same filter, the color was reconstructed.

We are doing 4k scans of some of this film, and reconstructing the color in software. However, if the lenticules aren't perfectly vertical in the scanned frame, they won't align correctly in our software and we wind up with strange color artifacts. This rotational value isn't always the same from frame to frame, it seems to vary a bit, and it's also different from film reel to film reel (possibly due to shrinkage, or variations in the manufacturing of the film).

So what I'd like to do is pre-process the images in ImageMagick in the following way:

1) Take a sample from the frame from some fixed set of coordinates. of the 4096x3112 original image, maybe something from the middle.
2) Detect the edges in that sample
3) Figure out the angle they're at
4) Rotate the image accordingly, to make those edges perfectly vertical

We need to be precise to thousandth of a degree, so we can really dial it in.

A sample scanned (original/unprocessed) frame is here (warning: it's about 25MB)

How would we go about doing this?

(also - as an aside: we run our software on Linux, and will be building a new PC for this, since we have a fair bit of this material to work on. Does Imagemagick benefit from faster GPUs, or is everything done in the CPU? What would best speed up this kind of processing? higher clock speeds or more cores?)

Thanks!
Last edited by friolator on 2017-01-11T09:03:28-07:00, edited 1 time in total.

snibgo
Posts: 9378
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Detecting lines in image, rotating based on that line's angle

Post by snibgo » 2017-01-11T08:24:06-07:00

Interesting project.

In the example frame, we have approx 15 pixels between edges, but the edges are not exactly vertical. There is a drift from top to bottom of about 22 pixels, so about 0.4 degrees. Is this fairly typical? Would you say there is a maximum angle, eg it is never more than 1 degree?

Is this drift equal from one side of the frame to the other? If so, then you want just one angle per frame. Is that correct?

As the height is 3112 pixels, and atan(1/3112) = 0.0184 degrees, I don't think you will get a precision much better than that.


You want to rotate, to put the edges vertical, I assume. I guess you then want to trim the new triangular pieces from the image boundary. Do you need edges to align from one frame to the next? If so, then each frame would be trimmed a little more.

Yes, the job is certainly doable. I'm not sure of the best approach. One possible approach: apply a rotation, and scale to a single row. The angle that gives the greatest contrast is the desired result. A binary chop could be used.

Another possible approach: Fourier. Yeah, I think that would do it.

The result might not be fast as a script, but when it does what you want you could code it in a compiled language to avoid reading the same frame multiple times.
snibgo's IM pages: im.snibgo.com

snibgo
Posts: 9378
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Detecting lines in image, rotating based on that line's angle

Post by snibgo » 2017-01-11T08:35:48-07:00

On the hardware issue: only a small proportion of IM operations use a GPU. Clock versus cores? I haven't tested that properly. Twice the clock speed is better than twice the cores (fairly obviously). My feeling is that you need to multiply cores by four to get the equivalent of twice the clock speed, but that's just a guess.

It may be quicker to process single-threaded, but with a few processes running simultaneously.

Do you have a feeling for how fast you want this to be? It might take up to a minute per frame, and there are an awful lot of frames in a film.
snibgo's IM pages: im.snibgo.com

friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Re: Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-11T08:46:06-07:00

Thanks. So to answer your questions:
In the example frame, we have approx 15 pixels between edges, but the edges are not exactly vertical. There is a drift from top to bottom of about 22 pixels, so about 0.4 degrees. Is this fairly typical? Would you say there is a maximum angle, eg it is never more than 1 degree?
Hard to say exactly, but it'll probably never be much more than that. This example is one that I posted only because it's my own film and I don't need client permission, and it's significantly more off than some other reels we've been testing with (those are closer to .2 degrees)
Is this drift equal from one side of the frame to the other? If so, then you want just one angle per frame. Is that correct?
In a perfect world, with perfect film, yes. But if the film is oddly warped or shrunken then it could be different on opposite ends of the frame. Or it might be off in the middle but the same on the edges. That said, we're not going to be concerned with this situation for right now, and we're treating it as one angle correction per frame. I'm hesitant to do any complicated dewarping, for fear of altering the encoded data and screwing up the color. Though, it may be something we look into in the future. For now, a global angle change per frame is what I'm looking to do.
As the height is 3112 pixels, and atan(1/3112) = 0.0184 degrees, I don't think you will get a precision much better than that.
I think that's fine. In Photoshop we can only rotate to a hundredth of a degree, but in testing with ImageMagick, we're getting better results if we can get into the thousandths (I mistyped earlier - not enough coffee. we need thousandths). In one of the cases, there was a frame that worked at .125, another at .2, another at .058, all within the same reel of film
You want to rotate, to put the edges vertical, I assume. I guess you then want to trim the new triangular pieces from the image boundary. Do you need edges to align from one frame to the next? If so, then each frame would be trimmed a little more.
Rotate, yes. The trim operation isn't necessary. Once the color is reconstructed, this would go into our color correction system, where we'd apply the final crop and output to whatever client deliverable format we need.

friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Re: Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-11T08:57:27-07:00

snibgo wrote:
2017-01-11T08:35:48-07:00
Do you have a feeling for how fast you want this to be? It might take up to a minute per frame, and there are an awful lot of frames in a film.
Well, the color reconstruction is done in about 1 second per frame on our current system, which isn't a very fast machine (a Pentium 3240 dual-core @3.1GHz). A typical reel of this stuff is 50 feet long, so that means about 2000 frames, or about half an hour to process the whole reel. I'd like to see the preprocessing in a similar timeframe, because much more than that is going to get really slow if we're doing a bunch of this at once.

We have a machine we're not using that has an i72600K in it (3.4GHz, 4 cores), which should be significantly faster. But I'm also willing to sink a little money into this and build something faster if it'll help.

snibgo
Posts: 9378
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Detecting lines in image, rotating based on that line's angle

Post by snibgo » 2017-01-11T09:41:30-07:00

Yes, the trial-rotation technique works. This is:

Rotate in 0.1 degree intervals between 0 and 1 degree. At each one, crop the central 95% of width and height. Scale this to a single row. Calculate the standard deviation. The largest SD is at the best angle. By inspection we see which side of the actual peak this is, so we know the second-best angle.

Repeat between best and second best, at 0.01 degree intervals.

Repeat between best and second best, at 0.001 degree intervals.

This gives a best angle of 0.3128 degrees, which seems to be exactly correct.

The process did 45 rotations, and took 1 minute 16 seconds. A proper chopping technique would halve the number of rotations.

A method with Fourier may be much quicker. Fred Weinhaus is the expert on that.
snibgo's IM pages: im.snibgo.com

friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Re: Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-11T09:43:42-07:00

snibgo wrote:
2017-01-11T08:24:06-07:00
Another possible approach: Fourier. Yeah, I think that would do it.
Can you elaborate? This is getting into math that's beyond my paygrade, so if you have an example of how you'd approach this, I'm all ears!

Thanks!

snibgo
Posts: 9378
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Detecting lines in image, rotating based on that line's angle

Post by snibgo » 2017-01-11T10:23:41-07:00

Fourier is beyond my paygrade, or brain power. California has woken up, so Fred will probably be at his desk in 10 minutes or so.
snibgo's IM pages: im.snibgo.com

User avatar
fmw42
Posts: 22079
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: Detecting lines in image, rotating based on that line's angle

Post by fmw42 » 2017-01-11T11:54:17-07:00

FFT can be used to determine the rotation from the lines in the image. However, I caution that since your lines are not straight, I doubt you can get accuracy to the third decimal position.

For a tutorial on FFT processing, see http://www.fmwconcepts.com/imagemagick/ ... urier.html

Here is how it works from your example. I took your image and cropped a 512x512 region near the top center that had good contrast. I saved as png so that the images would display below. The process is just to get the angle, so keeping as tif is not important.

Image

For reasons I will explain later, I rotated it 90 degrees so that the lines were nearly horizontal.
Image

Next, I generated the FFT spectrum.

Code: Select all

convert test_crop.png -fft -delete 1 -evaluate log 100000 test_crop_spectrum.png
Image

The fft spectrum will show lines that are perpendicular to those in the input image and will be spaced further. But these lines in the fft spectrum will intersect the coordinate axes and show dots. Those dots can be located and a least square fit performed to get the rotation angle.

The reason I rotated the image was that I have a script, textdeskew, that already does this extraction of the rotation angle and correction. It was designed to unrotate images of lines of text that are horizontal bands of white and dark from the text.

So processing your rotated subsection, I get two images. The un-rotated image and the mask showing the dots. And of course the rotation angle used. You can then rotate your original image by this same angle to correct it. However, note, that it is also sensitive to the size of the mask dots and outliers. So again, I am not sure of the accuracy of this process.

Code: Select all

textdeskew -r 3 test_crop_r90.png test_crop_r90_deskew.png test_crop_r90_deskew_mask.png
Rotated image:
Image

Mask image:
Image

friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Re: Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-11T12:06:13-07:00

Wow. Thanks. Ok, I need to dig into this a little deeper to understand what's going on, but I'll play with it later this afternoon.

Cool!

User avatar
fmw42
Posts: 22079
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: Detecting lines in image, rotating based on that line's angle

Post by fmw42 » 2017-01-11T12:13:07-07:00

P.S. My scripts only work on Unix-like OS systems. The do not work in native Windows and are not bat script. They are unix shell scripts.

friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Re: Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-11T12:21:21-07:00

That's fine - we're on linux

snibgo
Posts: 9378
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Detecting lines in image, rotating based on that line's angle

Post by snibgo » 2017-01-12T01:08:07-07:00

I'll leave Fourier in Fred's very capable hands.

My trial-and-error method works well (for this image) but takes 75 seconds, where you want around 1 second.

Possible speed improvements:

1. My CPU is i7-4700MQ @ 2.40GHz (8 cores, I think). Run the process single-threaded, but with 8 processes running simultaneously (on 8 different frames, of course). I tried this but it made no significant difference, on my machine.

2. Instead of making trial rotations of the entire frame, use just the central 30% or whatever of the width, which takes 28 seconds. However, this loses both precision and accuracy.

3. In the initial trials, we can work with a smaller version of the entire image. Provided we don't overcook this, we retain both precision and accuracy. Using 25% size for the first round and 50% for the second, the time is now 47 seconds. More work would be needed, on a variety of frames, to find how far you could reduce sizes.

4. This proof of concept makes 11 rotations in the first round, and the same in the next three rounds. Plus the final rotation makes 45. A proper binary chop would halve the required number.

I expect a final script might take about 20 seconds per frame. A compiled program wouldn't be much faster.

For your entertainment, here is the script I used. Windows BAT syntax, not bash, sorry. It is merely proof of concept.

Code: Select all

call StopWatch

set SRC=\web\im\LENTICULAR_rotation_0000849.tif

set sTHREADS=-limit thread 1
set sTHREADS=
set sCROP=-gravity center -crop 30%%x100%%+0+0 +repage
set sCROP=

set sRESIZE1=
set sRESIZE1=-resize 25%%

set sRESIZE2=
set sRESIZE2=-resize 50%%

set sPROC=-gravity center -crop 95%%x95%%+0+0 +repage -scale "x1^^^!" ^
  -format "%%[fx:standard_deviation]\n" +write info: +delete

%IM%convert ^
  %sTHREADS% ^
  %SRC% ^
  %sCROP% ^
  %sRESIZE1% ^
  ( +clone -rotate 0.0 %sPROC% ) ^
  ( +clone -rotate 0.1 %sPROC% ) ^
  ( +clone -rotate 0.2 %sPROC% ) ^
  ( +clone -rotate 0.3 %sPROC% ) ^
  ( +clone -rotate 0.4 %sPROC% ) ^
  ( +clone -rotate 0.5 %sPROC% ) ^
  ( +clone -rotate 0.6 %sPROC% ) ^
  ( +clone -rotate 0.7 %sPROC% ) ^
  ( +clone -rotate 0.8 %sPROC% ) ^
  ( +clone -rotate 0.9 %sPROC% ) ^
  ( +clone -rotate 1.0 %sPROC% ) ^
  NULL:

rem Assume 0.3 is the best, and 0.4 is second-best.

%IM%convert ^
  %sTHREADS% ^
  %SRC% ^
  %sCROP% ^
  %sRESIZE2% ^
  ( +clone -rotate 0.30 %sPROC% ) ^
  ( +clone -rotate 0.31 %sPROC% ) ^
  ( +clone -rotate 0.32 %sPROC% ) ^
  ( +clone -rotate 0.33 %sPROC% ) ^
  ( +clone -rotate 0.34 %sPROC% ) ^
  ( +clone -rotate 0.35 %sPROC% ) ^
  ( +clone -rotate 0.36 %sPROC% ) ^
  ( +clone -rotate 0.37 %sPROC% ) ^
  ( +clone -rotate 0.38 %sPROC% ) ^
  ( +clone -rotate 0.39 %sPROC% ) ^
  ( +clone -rotate 0.40 %sPROC% ) ^
  NULL:

rem Assume 0.31 is the best, and 0.32 is second-best.

%IM%convert ^
  %sTHREADS% ^
  %SRC% ^
  %sCROP% ^
  ( +clone -rotate 0.310 %sPROC% ) ^
  ( +clone -rotate 0.311 %sPROC% ) ^
  ( +clone -rotate 0.312 %sPROC% ) ^
  ( +clone -rotate 0.313 %sPROC% ) ^
  ( +clone -rotate 0.314 %sPROC% ) ^
  ( +clone -rotate 0.315 %sPROC% ) ^
  ( +clone -rotate 0.316 %sPROC% ) ^
  ( +clone -rotate 0.317 %sPROC% ) ^
  ( +clone -rotate 0.318 %sPROC% ) ^
  ( +clone -rotate 0.319 %sPROC% ) ^
  ( +clone -rotate 0.320 %sPROC% ) ^
  NULL:

rem Assume 0.313 is the best, and 0.312 is second-best.

%IM%convert ^
  %sTHREADS% ^
  %SRC% ^
  %sCROP% ^
  ( +clone -rotate 0.3120 %sPROC% ) ^
  ( +clone -rotate 0.3121 %sPROC% ) ^
  ( +clone -rotate 0.3122 %sPROC% ) ^
  ( +clone -rotate 0.3123 %sPROC% ) ^
  ( +clone -rotate 0.3124 %sPROC% ) ^
  ( +clone -rotate 0.3125 %sPROC% ) ^
  ( +clone -rotate 0.3126 %sPROC% ) ^
  ( +clone -rotate 0.3127 %sPROC% ) ^
  ( +clone -rotate 0.3128 %sPROC% ) ^
  ( +clone -rotate 0.3129 %sPROC% ) ^
  ( +clone -rotate 0.3130 %sPROC% ) ^
  NULL:

rem 0.3128 is the best.

%IM%convert ^
  %sTHREADS% ^
  %SRC% ^
  -rotate 0.3128 ^
  x.png

call StopWatch
snibgo's IM pages: im.snibgo.com

User avatar
fmw42
Posts: 22079
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: Detecting lines in image, rotating based on that line's angle

Post by fmw42 » 2017-01-12T10:25:22-07:00

I would note that one could do the FFT on the whole image. But I am still concerned that since the lines curve a bit, you will not be able to get 3 decimal place accuracy, because it is spatially varying.

friolator
Posts: 23
Joined: 2014-02-18T15:57:30-07:00
Authentication code: 6789

Re: Detecting lines in image, rotating based on that line's angle

Post by friolator » 2017-01-12T12:50:08-07:00

I modified your shell script a bit, so that it extracts a 512x512 image and rotates it internally, then at the end it runs the rotation value against the whole image. Seems to take about 2 seconds per frame, which isn't too bad, considering the machine is no powerhouse and these are big images. There are some pretty funny results at the head and tail of the reels, where there is no image, it's just pure white so we get totally nutty rotation values (but that's to be expected). We'll just cut that out later.

Once it hits legitimate frames, though, it's doing a nice job so far. I've tested a handful of random frames in our color reconstruction software and in general the results are much better than we were getting before.

I'm hoping to run a batch color reconstruction job overnight, so I may be able to post something soon.

Thanks for the help, and for providing the scripts!

Post Reply