global motion estimation, special case

[jmac698]

Hello,
I have a special case of global motion estimating. I have a frame from two sources, of the same image, but with different sizes and aspects.
A usual global estimate can estimate pan, zoom, and even rotation. I looked at the manuals for depan, mvtools, and they say to set aspect ratio and this is very important.
I don't know aspect ratio, this is the "X" unknown quantity I need to find. The expected variances are: pan, zoom, aspect ratio.
Sources are progressive, no probs there.
I will try this soon and report, however I believe global zoom cannot be computed with differing x/y zoom factors.
Any ideas how I could extract this info?

To be clear: take one source, ATSC HD upconverted, another source PAL SD. 1920x1080 and 720x576. Compare both images of exact same frame, to determine with mathematical preciseness, the zoom, aspect, cropping and position to convert one frame to another. They are both yv12.
I do this often for calibration, reverse engineering and educational purposes, and by hand it is very time consuming, and not precise!

[Fizick]

probably various X and Y zoom may be estimated, but
I am afraid you can not get precise data so way.
Every frame may produce a little different estimation.

Currently you can resize (by hand) one clip, interleve with other (similar size), crop to same size, and use DePanEstimate(info) to compare the trust.

[jmac698]

Ah, Fizick, the master of motion estimation :)
I did that exactly, and it helped find a good manual estimate. I could write a Animate() type resizing script and find the best Trust value.
But don't you think there is a mathematical way to do this? Why not a full search with correlation coeficient to find best match?
I did an investigation of correlation and it matches disregarding brightness and even contrast (these are both linear operations). It even matches disregarding order (if the pixels in block were scambled). Noise doesn't bother it too much either.
But because it is unordered, other images could match it. I suppose you could fix this.
Do you know any other algorithms to match regardless of scale? This is used in fractal compression? Multiscale analysis?
http://en.wikipedia.org/wiki/Correlation

[Fizick]

But because it is unordered, other images could match it. I suppose you could fix this.

Sorry, I do not understand you.
What I must to fix?

By the way, recently I released DePanEstimate source under GPL.

Other algorithms to match regardless of scale?
Try look to computer vision. It use objects recognition and tracking.
But I am still do not understand your goal.

[jmac698]

correlation formula, from statistics, takes two sets of numbers, x0,x1,x2,... and y0,y1,y2... and in the end, correlation(x0,...y0,..)=(-1,+1).
If +1, then x.. and y... are strongly related.
If 0, then x and y are very different!
If -1, then x and y are opposite!

Order: because this formula, uses addition (greek Sigma, look like "E"), then order of points makes no difference. So picture:
"***...***" will match perfect: "***..**.*"

In 2d case, this means, that if same colored pixels (within, linear effects of contrast, brightness), are present in each area (X,Y ) compared, then there is a match. For example, 8x8 block X will match 8x8 block Y even if Y is mirror image, or rotated 90 image, or even random shuffled pixels (64 shuffled random order pixels) image, it is matching perfectly.

X image:
*
***
*

Y image:
*
***
*
correlation (X,Y)=+1

Y image:
.
...
.
(less bright)
correlation (X,Y)=+1

Y image:
*
**
*
correlation (X,Y)<=+1

To code this idea, use formula for Pearson's coeficcient (look up formula, very simple).

My goal: again, to find, between two frames, translation and scaling transformation., ie X==Y.crop(8,0,8,0).letterbox(8,0,0,0).resize(.5*width(Y),.6*height(Y)

[Fizick]

I find correlation in FFT (DFT, so periodic) domain.
It is fast.

Are your goal to find transformation between frames or clips?
probably you must code it yourself. :)

[jmac698]

Frames or clips, doesn't matter, the transformation is constant. Ah, yes, adding two FFTs causes correlation? Hmm...

http://local.wasp.uwa.edu.au/~pbourke/other/correlate/

that looks like exactly what I need... the delay is the pixel shift.. is your code very close to this?

[Fizick]

No. I use phase correlation.
http://en.wikipedia.org/wiki/Phase_correlation

[wonkey_monkey]

My goal: again, to find, between two frames, translation and scaling transformation., ie X==Y.crop(8,0,8,0).letterbox(8,0,0,0).resize(.5*width(Y),.6*height(Y)

It sounds like you should only need a quick back of the envelope calculation, using the x,y coordinates of two matching points between images... or have I missed something?

Find two points, a and b, that are in both images and preferably as far apart as possible. Your horizontal scaling factor will be (HDax-HDbx)/(SDax-SDbx), and similar for vertical. Once you've got the scaling factors, it's pretty simple to work out the translation.

ETA: have I misunderstood what you meant by "special case"? I thought you meant this would be a one-off, but maybe you don't.

David

[jmac698]

David: that's a good idea, and it's exactly what I have used before. I found a spot with stars moving inwards and could match two stars together, in diagonally opposite corners. I couldn't match to the pixel however, as they looked somewhat different. It's not as easy as it seems; you need a very hard edge to match pixels. Also one image was sharpened so it's even harder. I need within one pixel to get the accuracy I'm really interested in.

I need to solve this once in a while, but only needs to calculated for two frames.

Phase Correlation is an awesome algorithm; mathematically you get 1 at the spot of translation and 0 at all other spots, there couldn't be a clearer separation. I will try your DePan with a shifted and noisy frame to duplicate the illustration in the article.

However there are algorithms to estimate translation and scale, with similar programming to DePan, so perhaps if it's easy it could be added!

http://www.cs.brown.edu/~morgan/papers/(McGuire%2098)%20Registration.pdf

This may turn out to be my first filter...

Update: online demo at
http://nayana.ece.ucsb.edu/registration/
upload two similar images. It wouldn't work for me however because it can't find zoom different in x,y. It's a really cool webpage though!