Ceres-based homography and fundamental estimation

This change moves homography and fundamental estimation code to a generic multiview library, so everyone might use homography/fundamental estimation followed by a ceres-bases refinement.

New functions are supposed to be flexible enough by tweaking settings in an options structure passed to them.

For artists this change would mean more accurate plane track motion estimation.

[mierle, 2013-09-30 16:48:11]

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/f...
File extern/libmv/libmv/multiview/fundamental.h (right):

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/f...
extern/libmv/libmv/multiview/fundamental.h:154: typedef struct
FundamentalEstimationOptions {
This isn't C don't use typedef struct

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/f...
extern/libmv/libmv/multiview/fundamental.h:169: } FundamentalEstimationOptions;
Remove useless struct name

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
File extern/libmv/libmv/multiview/homography.cc (right):

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.cc:188: residuals[0] = H_x(0) -
T(y_(0));
Put a comment that this is the forward error

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.cc:191: residuals[2] = Hinv_y(0) -
T(x_(0));
And that this is the backward error

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.cc:204: bool
Homography2DFromCorrespondencesEuc(const Mat &x1,
I would remove the "Euc" from the name; this is an implementation detail. We may
end up supporting from homogenous coordinates as well, so let's not limit
ourselves.

Also consider naming this

EstimateHomography

and

EstimateHomographyOptions

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.cc:206: const
HomographyEstimationOptions &options,
80 columns

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.cc:208: /* TODO(sergey): Support
homogenous coordinates, not just euclidean. */
Don't use *-style commens.

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.cc:260: summary.termination_type ==
ceres::NO_CONVERGENCE ||
No convergence doesn't necessarily indicate failure; just not convergence.

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
File extern/libmv/libmv/multiview/homography.h (right):

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.h:63: typedef struct
HomographyEstimationOptions {
Remove typedef; this isn't C

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.h:65: HomographyEstimationOptions(void);
Don't put void in there; this isn't c.

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.h:67: /* Expected precision of algebraic
estimation. */
What units are precision? This is meaningless.

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.h:77: float parameter_tolerance;
Explain units of parameter tolerance. Consider using tolerance similar to what I
do in the planar tracker; the issue is that the norm of the H vector is
semi-meaningless. Instead it's better to offer an error in pixels which is
something you can think about.

https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
extern/libmv/libmv/multiview/homography.h:81: } HomographyEstimationOptions;
Remove useless struct name; this isn't C.

[sergey.vfx, 2013-10-01 11:17:31]

message: On 2013/09/30 16:48:11, mierle wrote:
>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/f...
> File extern/libmv/libmv/multiview/fundamental.h (right):
> 
>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/f...
> extern/libmv/libmv/multiview/fundamental.h:154: typedef struct
> FundamentalEstimationOptions {
> This isn't C don't use typedef struct

done.


>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/f...
> extern/libmv/libmv/multiview/fundamental.h:169: }
FundamentalEstimationOptions;
> Remove useless struct name

done.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> File extern/libmv/libmv/multiview/homography.cc (right):
> 
>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.cc:188: residuals[0] = H_x(0) -
> T(y_(0));
> Put a comment that this is the forward error

done.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.cc:191: residuals[2] = Hinv_y(0) -
> T(x_(0));
> And that this is the backward error

done.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.cc:204: bool
> Homography2DFromCorrespondencesEuc(const Mat &x1,
> I would remove the "Euc" from the name; this is an implementation detail. We
may
> end up supporting from homogenous coordinates as well, so let's not limit
> ourselves.
> 
> Also consider naming this
> 
> EstimateHomography
> 
> and
> 
> EstimateHomographyOptions

What about EstimateHomographyFromCorrespondencies? Just thinking we might want
to estimate homography from other things in the future.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.cc:206: const
> HomographyEstimationOptions &options,
> 80 columns

done.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.cc:208: /* TODO(sergey): Support
> homogenous coordinates, not just euclidean. */
> Don't use *-style commens.

done.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.cc:260: summary.termination_type ==
> ceres::NO_CONVERGENCE ||
> No convergence doesn't necessarily indicate failure; just not convergence.

True enough, done. Are there other cases missed here btw?

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> File extern/libmv/libmv/multiview/homography.h (right):
> 
>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.h:63: typedef struct
> HomographyEstimationOptions {
> Remove typedef; this isn't C

done.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.h:65:
HomographyEstimationOptions(void);
> Don't put void in there; this isn't c.
> 
>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.h:67: /* Expected precision of
algebraic
> estimation. */
> What units are precision? This is meaningless.

For now it just pipes precision to Homography2DFromCorrespondencesLinear. If you
want to be menaingful here we need to change that as well.

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.h:77: float parameter_tolerance;
> Explain units of parameter tolerance. Consider using tolerance similar to what
I
> do in the planar tracker; the issue is that the norm of the H vector is
> semi-meaningless. Instead it's better to offer an error in pixels which is
> something you can think about.

On the second thought i might agree here, on the second -- not just yet. You're
not necessarily estimates homography from correspondences in pixel space (in
fact, currently estimation happens in normalized space). And in this case
forcing units of tolerance to pixel space is kind of meaningless.

I'd say:
Units of tolerance matches units of input correspondences. This means
correspondences are in pixel space, tolerance is also measured in pixel space,
and if they're in normalized space, tolerance is also in normalized units.

But it doesn't seem to be trivial to translate this directly to Ceres options.
Guess we need to use user callbacks here?

And one more thing, seems i need to investigate why exactly fundamental
estimation doesn't work in pixel space

>
https://codereview.appspot.com/13896044/diff/1/extern/libmv/libmv/multiview/h...
> extern/libmv/libmv/multiview/homography.h:81: } HomographyEstimationOptions;
> Remove useless struct name; this isn't C.

done.

[sergey.vfx, 2013-10-01 20:07:09]

Stage 2

[sergey.vfx, 2013-10-01 20:11:12]

Changes:

- Changed naming of the structures and functions.
- Added use_normalization to homography estimation in order to deal with coords
in pixel space. This makes algebraic estimation more stable. 

It' not clear why using T2.transpose() doesn't work instead of T2.inverse().
This matrix is just a transform+scale, so for my knowledge transpose shall do
the job..

And it's still unclear how to make fundamental estimation working in pixel
space. When you try using it with coords in pixel space, depth of the
reconstruction is really get lost. Not sure, is it even mathematically possible
to have a fundamental estimation which would work for both pixel and normalized
coordinates?

[sergey.vfx, 2013-10-02 19:31:01]

Stage 2, round 2

[sergey.vfx, 2013-10-02 19:37:40]

Stage 0

[sergey.vfx, 2013-10-02 19:38:57]

Stage 0

[sergey.vfx, 2013-10-02 19:50:04]

Stage 2

[sergey.vfx, 2013-10-02 19:53:36]

Switched to tomato, because odereview being stupid and doesn't take revision
number from the patch into account.

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv-capi.cc
File extern/libmv/libmv-capi.cc (right):

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv-capi.cc...
extern/libmv/libmv-capi.cc:1096: void
libmv_homography2DFromCorrespondencesEuc(double (*x1)[2], double (*x2)[2], int
num_points, double H[3][3])
Need to be renamed to libmv_estimateHomography2DFromCorrespondences

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv-capi.cc...
extern/libmv/libmv-capi.cc:1112: libmv::HomographyEstimationOptions options;
Yes i know, this uses out-of-date names. Need to be EstimateHomographyOptions
and EstimateHomography2DFromCorrespondences.

Don't blame on this piece of code now, at least this patch worked!

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv/simple_...
File extern/libmv/libmv/simple_pipeline/keyframe_selection.cc (right):

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv/simple_...
extern/libmv/libmv/simple_pipeline/keyframe_selection.cc:136: void
SelectKeyframesBasedOnGRICAndVariance(const Tracks &tracks,
Rename left here from another patch, which wasn't merged to tomato yet.

[sergey.vfx, 2013-10-06 14:59:39]

Added proper termination callback

[sergey.vfx, 2013-10-06 15:04:46]

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/simple_...
File extern/libmv/libmv/simple_pipeline/keyframe_selection.h (right):

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/simple_...
extern/libmv/libmv/simple_pipeline/keyframe_selection.h:46: void
SelectKeyframesBasedOnGRICAndVariance(const Tracks &tracks,
Don't mind this change. It's caused by tomato using out-of-date libmv checkout.

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/trackin...
File extern/libmv/libmv/tracking/track_region.cc (left):

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/trackin...
extern/libmv/libmv/tracking/track_region.cc:1563: void
ApplyInverseCanonicalHomography(const double x, const double y,
This also caused by out-of-date libmv in tomato, not related to actual patch.

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/trackin...
File extern/libmv/libmv/tracking/track_region.h (left):

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/trackin...
extern/libmv/libmv/tracking/track_region.h:152: void
ApplyInverseCanonicalHomography(const double x, const double y,
This also caused by out-of-date libmv in tomato, not related to actual patch.

[mierle, 2013-10-07 05:33:45]

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv/multivi...
File extern/libmv/libmv/multiview/fundamental.cc (right):

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv/multivi...
extern/libmv/libmv/multiview/fundamental.cc:450: /* Fundamental transformation
estimation. */
Don't use /* */ comments except for doxygen comments.

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/multivi...
File extern/libmv/libmv/multiview/fundamental.cc (right):

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/multivi...
extern/libmv/libmv/multiview/fundamental.cc:472: average_distance =
SymmetricEpipolarDistance(*F_,
Wait... is this the same as the ceres total cost function? In which case it
could be cost function tolerance instead of this entire callback?

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/multivi...
File extern/libmv/libmv/multiview/homography.cc (right):

https://codereview.appspot.com/13896044/diff/55001/extern/libmv/libmv/multivi...
extern/libmv/libmv/multiview/homography.cc:322: TerminationCheckingCallback
callback(x1, x2, options, H);
Ceres has a tolerance for this; function tolerance. I think this extra callback
is unnecessary.

[sergey.vfx, 2013-10-07 07:33:12]

That is indeed pretty close to total function cost (could miss some missing
square root or so tho :) but it wouldn't be the same termination as a function
tolerance.

From what could i see, in ceres function tolerance aborts minimization when
delta between new and old costs is less than tolerance (well, actually tolerance
multiplied by an old cost). And here we do termination criteria based on
absolute value of cost function.

Imagine situation when you do need homography for some proxy display or preview,
when 0.5 px of average error is more than enough. With the implementation from
this patch, you configure options like this:

  EstimateHomograpfyOption options;
  options.expected_average_symmetric_distance = 0.5;

Not sure how would you do the same with Ceres's function tolerance. Also, in
which units that tolerance would be measured?

The only thing i was thinking about is, maybe instead of using average cost here
do a termination based on maximal distance (so all the points are guaranteed to
be projected with a given accuracy).

[sergey.vfx, 2013-10-07 11:08:38]

Fixed wrong usage of /*. Will publish new patch when we figure what to with the
callback.

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv/multivi...
File extern/libmv/libmv/multiview/fundamental.cc (right):

https://codereview.appspot.com/13896044/diff/47001/extern/libmv/libmv/multivi...
extern/libmv/libmv/multiview/fundamental.cc:450: /* Fundamental transformation
estimation. */
On 2013/10/07 05:33:45, mierle wrote:
> Don't use /* */ comments except for doxygen comments.

Done.