calculation if images overlap

[chaosjug]

Hi,

does someone have the formulas or a code example how to calculate if images
overlap? So starting with y,p,r,hfov and aspect ratio. I only need an
estimate, so I hope I can neglect the lens type.

Regards
Stephan

[Gunter Königsmann]

Can there be a need to rotate them in order to make them overlap? If no you might want to look into fast convolution algorithms.

-- 
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
To unsubscribe from this group and stop receiving emails from it, send an email to hugin-ptx+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/hugin-ptx/4434312.LvFx2qVVIh%40chaos-home.

[chaosjug]

Not based on content but based on geometry. I have a (pre)aligned panorama
with yaw, pitch, roll for each image and want to know which images overlap.

[John Fine]

I'm lacking hugin knowledge on the first sub-problem below, but I think your problem breaks down into four easy sub-problems.  Then is there a specific one of those you need help with?

1) You need hfov in the same units as y and p.  I don't know if it already is, or if it needs some additional value (assumed subject distance) in order to convert.  You need r and aspect ratio in units you understand.

2) Given (1), it should be easy to compute the y,p coordinate position of each corner of each image.

3) Google and/or StackOverflow can easily be searched for a formula for "is point in quadrangle".  That can be used to tell whether a corner of one image is in the quadrangle of the other.  Assuming no lens correction was used, two images overlap if and only if some corner of the second is within the quadrangle of the first.  (First vs. second works either way and only one of the two ways needs to be tested).

4) You could (and I think should) just "brute force" the testing:  Do all 4*N*(N-1)/2 tests, meaning each corner of each image tested against the quadrangle of each earlier image.  In game writing tutorials you might be able to understand some very complicated approaches to proximity sorting that reduce the problem to 8*N*Log(N).  But that massive research effort would only have value if you were working with a set of over 30 thousand images.

--
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ

---

[aCuria]

Pseudocode:

1) convert y p r to a direction vector 

2) compute angle between two direction vectors A and B

3) compare angle to hfovA/2 + hfovB/2 

4) if the angle is smaller it’s possible it overlaps. Must check rotation of the two images to be sure 

[johnfi...@gmail.com]

The angles compared in your step 3 aren't actually in comparable units.  So your method would miss overlaps near the origin (where two photos each have small y and p values but opposite signs on their y and p values).

[chaosjug]

Not sure if I get your point. The images are not circles so hfov is only an
estimate. The right value would be something between hfov and vfov I guess.
But why is the origin special? Of course I would need to make sure to
calculate the angle between 359° and 1° as 2°. But that is even more tricky
when implementing your version with quadrangles. I'm pretty sure there is some
sort of transformation to avoid those problem...

[johnfi...@gmail.com]

My method does fail to cover the case that any image has y or p values crossing 180 degrees (meaning directly behind the viewpoint of the panorama).  I didn't think that case needed to be covered.

Crossing the 360 point of direction relative to the origin, is an ordinary condition that would need to be covered.  But that was not the problem I was pointing out.

Consider an example:

Photo A has yaw minus 4 degrees, pitch 0 and hfov 10 degrees.  Photo B has yaw plus 4 degrees, pitch 0 and hfov 10 degrees.  Clearly they overlap.  But A has direction vector at minus 90 degrees, while B has direction vector at plus 90 degrees, so they are 180 degrees apart and only 10 degrees wide, so if you thought those angles were comparable measures, you would think the images did not overlap.

[chaosjug]

My interpretation of "direction vector" seems to be different. Not sure what
aCuria meant, because using r for the vector does not make sense to me. I
thought I would just take y and p as vector in spherical coordinate and then
compute the delta angle. For your example this would lead to a delta angle of
8 degrees.

[johnfi...@gmail.com]

Yes, I might have misunderstood what keith... meant.  The way you understood it, the thing you are converting y p and r to is just (y,p) ?

But then it seems like a fairly crude approximation of overlap (because images aren't circles).  That could be useful, by being 10 times faster than a more accurate method, if the more accurate method were too slow.  But all the effort is in coding and you likely need the more accurate method anyway to weed out the false positives, so why not write just the more accurate method.

I agree that using r when computing the direction vector doesn't seem to fit any meaning of "direction vector" I can think of.

The sin and cos of r are used with hfov/2 and vfov/2 to compute the relative positions of the corners given the center position.

[aCuria]

The direction vector I’m talking about is the vector from the centre of the camera sensor to the distant point the camera is pointing directly at. 

You can think of this distant point as the object targeted by the centre focus point of your camera 

Since your camera is aligned… meaning you take one shot then rotate left or right until you cover 360 degrees, you don’t have to do further calculations 

If the images are randomly rotated, then you have to do more complicated computations… I use a shader to brute force the result, you can think of this as shooting a ray from the image A camera origin to each image A pixel and seeing if it intersects with image B. However to do this you need depth information 

--
A list of frequently asked questions is available at: http://wiki.panotools.org/Hugin_FAQ
---
You received this message because you are subscribed to the Google Groups "hugin and other free panoramic software" group.
To unsubscribe from this group and stop receiving emails from it, send an email to hugin-ptx+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/hugin-ptx/1944974.PYKUYFuaPT%40chaos-home.

[chaosjug]

I'm fighting with step 2) at the moment:
The yaw of the corners is not y + hfov/2 it also depends on vfov and p ...

[johnfi...@gmail.com]

I think the corner y values should be y {+ or -} sin(r)*vfov/2 {+ or -} cos(r)*hfov/2

where the four corners are found by the four combinations of + or -

then the corner p values are like that, but using p instead of y and swapping vfov with hfov

[chaosjug]

I don't think so. Simple example:
y = 0, p = 0, r = 0
vfov = 180 degree

Then the yaw of the corners is +/- 90 and the pitch depends on the hfov

[johnfi...@gmail.com]

four y,p pairs are:

1:   y + cos(r)*h - sin(r)*v, p + cos(r)*v + sin(r)*h

2:   y - cos(r)*h - sin(r)*v, p + cos(r)*v - sin(r)*h

3:   y - cos(r)*h + sin(r)*v, p - cos(r)*v - sin(r)*h

4:   y + cos(r)*h + sin(r)*v, p - cos(r)*v + sin(r)*h

[johnfi...@gmail.com]

Sorry, I put an extra post in before seeing your post, which might be confusing.

Your example:

y = 0, p = 0, r = 0
vfov = 180 degree

sin(r) = 0 and cos(r) = 1

so the yaw of the corners should be +/- the hfov/2 not +/- 90

Can you explain how you got the answer for that example?

I could easily be reversing something here.  But rereading my own post, I don't see anything reversed.

[johnfi...@gmail.com]

Two posts ago, I forgot to explain I was being more concise by using v instead of vfov/2 and using h instead of hfov/2

I was trying to show the pattern of sin vs cos interacting with + vs - and wanted to reduce other confusion, but forgetting to define the abbreviation increased confusion.