1 // This is oxl/mvl/FMatrixCompute7Point.cxx
2 #include <vector>
3 #include <iostream>
4 #include <cmath>
5 #include "FMatrixCompute7Point.h"
6 //:
7 // \file
8 // \author David N. McKinnon, UQ I.R.I.S
9 // \date 25 Nov 2000
10 //-----------------------------------------------------------------------------
11
12 #ifdef _MSC_VER
13 # include "vcl_msvc_warnings.h"
14 #endif
15
16 #include "vnl/vnl_matrix.h"
17 #include "vnl/vnl_math.h"
18 #include <vnl/algo/vnl_svd.h>
19
20 #include <mvl/HomgMetric.h>
21 #include <mvl/PairMatchSetCorner.h>
22 #include <mvl/FDesignMatrix.h>
23 #include <mvl/HomgNorm2D.h>
24
FMatrixCompute7Point(bool precondition,bool rank2_truncate)25 FMatrixCompute7Point::FMatrixCompute7Point(bool precondition, bool rank2_truncate)
26 : precondition_(precondition),
27 rank2_truncate_(rank2_truncate)
28 {
29 }
30
31 //-----------------------------------------------------------------------------
32 //
33 //: Compute a fundamental matrix for a set of 7 point matches.
34 //
35 // Return false if the calculation fails or there are fewer than eight point
36 // matches in the list.
37
compute(PairMatchSetCorner & matches,std::vector<FMatrix * > & F)38 bool FMatrixCompute7Point::compute(PairMatchSetCorner& matches, std::vector<FMatrix*>& F)
39 {
40 // Copy matching points from matchset.
41 std::vector<HomgPoint2D> points1(matches.count());
42 std::vector<HomgPoint2D> points2(matches.count());
43 matches.extract_matches(points1, points2);
44 return compute(points1, points2, F);
45 }
46
47 //-----------------------------------------------------------------------------
compute(std::vector<vgl_homg_point_2d<double>> & points1,std::vector<vgl_homg_point_2d<double>> & points2,std::vector<FMatrix * > & F) const48 bool FMatrixCompute7Point::compute(
49 std::vector<vgl_homg_point_2d<double>> &points1,
50 std::vector<vgl_homg_point_2d<double>> &points2,
51 std::vector<FMatrix *> &F) const {
52 if (points1.size() < 7 || points2.size() < 7) {
53 std::cerr << "FMatrixCompute7Point: Need at least 7 point pairs.\n"
54 << "Number in each set: " << points1.size() << ", " << points2.size() << '\n';
55 return false;
56 }
57
58 if (precondition_) {
59 // Condition points
60 HomgNorm2D conditioned1(points1);
61 HomgNorm2D conditioned2(points2);
62
63 // Compute F with preconditioned points
64 if (!compute_preconditioned(conditioned1.get_normalized_points(),
65 conditioned2.get_normalized_points(), F))
66 return false;
67
68 // De-condition F
69 for (auto & i : F) {
70 FMatrix* oldF = i;
71 i = new FMatrix(HomgMetric::homg_to_image_F(*i, &conditioned1,
72 &conditioned2));
73 delete oldF;
74 }
75 }
76 else
77 if (!compute_preconditioned(points1, points2, F))
78 return false;
79
80 return true;
81 }
82
83 //-----------------------------------------------------------------------------
compute(std::vector<HomgPoint2D> & points1,std::vector<HomgPoint2D> & points2,std::vector<FMatrix * > & F) const84 bool FMatrixCompute7Point::compute(std::vector<HomgPoint2D> &points1,
85 std::vector<HomgPoint2D> &points2,
86 std::vector<FMatrix *> &F) const {
87 if (points1.size() < 7 || points2.size() < 7) {
88 std::cerr << "FMatrixCompute7Point: Need at least 7 point pairs.\n"
89 << "Number in each set: " << points1.size() << ", " << points2.size() << '\n';
90 return false;
91 }
92
93 if (precondition_) {
94 // Condition points
95 HomgNorm2D conditioned1(points1);
96 HomgNorm2D conditioned2(points2);
97
98 // Compute F with preconditioned points
99 if (!compute_preconditioned(conditioned1.get_normalized_points(),
100 conditioned2.get_normalized_points(), F))
101 return false;
102
103 // De-condition F
104 for (auto & i : F) {
105 FMatrix* oldF = i;
106 i = new FMatrix(HomgMetric::homg_to_image_F(*i, &conditioned1,
107 &conditioned2));
108 delete oldF;
109 }
110 return true;
111 }
112 else return compute_preconditioned(points1, points2, F);
113 }
114
115 //-----------------------------------------------------------------------------
compute_preconditioned(std::vector<vgl_homg_point_2d<double>> & points1,std::vector<vgl_homg_point_2d<double>> & points2,std::vector<FMatrix * > & F) const116 bool FMatrixCompute7Point::compute_preconditioned(std::vector<vgl_homg_point_2d<double> >& points1,
117 std::vector<vgl_homg_point_2d<double> >& points2,
118 std::vector<FMatrix*>& F) const
119 {
120 // Create design matrix from conditioned points
121 FDesignMatrix design(points1, points2);
122
123 // Normalize rows for better conditioning
124 design.normalize_rows();
125
126 // Extract vnl_svd<double> of design matrix
127 vnl_svd<double> svd(design);
128
129 vnl_matrix<double> W = svd.nullspace();
130
131 // Take the first and second nullvectors from the nullspace
132 // Since rank 2 these should be the only associated with non-zero
133 // root (Probably need conditioning first to be actually rank 2)
134 FMatrix F1(vnl_double_3x3(W.get_column(0).data_block()));
135 FMatrix F2(vnl_double_3x3(W.get_column(1).data_block()));
136
137 // Using the fact that Det(alpha*F1 +(1 - alpha)*F2) == 0
138 // find the real roots of the cubic equation that satisfy
139 std::vector<double> a = FMatrixCompute7Point::GetCoef(F1, F2);
140 std::vector<double> roots = FMatrixCompute7Point::solve_cubic(a);
141
142 if (roots.empty())
143 return false;
144
145 for (unsigned int i = 0; i < roots.size(); i++) {
146 vnl_matrix<double> F_temp =
147 F1.get_matrix().as_ref()*roots[0] + F2.get_matrix()*(1 - roots[i]);
148 F.push_back(new FMatrix(F_temp));
149 }
150 // Rank-truncate F
151 if (rank2_truncate_) {
152 for (auto & h : F) {
153 h->set_rank2_using_svd();
154 }
155 }
156 return true;
157 }
158
159 //-----------------------------------------------------------------------------
compute_preconditioned(std::vector<HomgPoint2D> & points1,std::vector<HomgPoint2D> & points2,std::vector<FMatrix * > & F) const160 bool FMatrixCompute7Point::compute_preconditioned(std::vector<HomgPoint2D>& points1,
161 std::vector<HomgPoint2D>& points2,
162 std::vector<FMatrix*>& F) const
163 {
164 // Create design matrix from conditioned points
165 FDesignMatrix design(points1, points2);
166
167 // Normalize rows for better conditioning
168 design.normalize_rows();
169
170 // Extract vnl_svd<double> of design matrix
171 vnl_svd<double> svd(design);
172
173 vnl_matrix<double> W = svd.nullspace();
174
175 // Take the first and second nullvectors from the nullspace
176 // Since rank 2 these should be the only associated with non-zero
177 // root (Probably need conditioning first to be actually rank 2)
178 FMatrix F1(vnl_double_3x3(W.get_column(0).data_block()));
179 FMatrix F2(vnl_double_3x3(W.get_column(1).data_block()));
180
181 // Using the fact that Det(alpha*F1 +(1 - alpha)*F2) == 0
182 // find the real roots of the cubic equation that satisfy
183 std::vector<double> a = FMatrixCompute7Point::GetCoef(F1, F2);
184 std::vector<double> roots = FMatrixCompute7Point::solve_cubic(a);
185
186 for (unsigned int i = 0; i < roots.size(); i++) {
187 vnl_matrix<double> F_temp =
188 F1.get_matrix().as_ref()*roots[0] + F2.get_matrix()*(1 - roots[i]);
189 F.push_back(new FMatrix(F_temp));
190 }
191 // Rank-truncate F
192 if (rank2_truncate_) {
193 for (auto & h : F) {
194 h->set_rank2_using_svd();
195 }
196 }
197 return true;
198 }
199
200 //
201 // Det(alpha*F1 +(1 - alpha)*F2) == 0
202 // (I obtained these coefficients from Maple (fingers crossed!!!))
203 //
GetCoef(FMatrix const & F1,FMatrix const & F2)204 std::vector<double> FMatrixCompute7Point::GetCoef(FMatrix const& F1, FMatrix const& F2)
205 {
206 double a=F1.get(0,0), j=F2.get(0,0), aa=a-j,
207 b=F1.get(0,1), k=F2.get(0,1), bb=b-k,
208 c=F1.get(0,2), l=F2.get(0,2), cc=c-l,
209 d=F1.get(1,0), m=F2.get(1,0), dd=d-m,
210 e=F1.get(1,1), n=F2.get(1,1), ee=e-n,
211 f=F1.get(1,2), o=F2.get(1,2), ff=f-o,
212 g=F1.get(2,0), p=F2.get(2,0), gg=g-p,
213 h=F1.get(2,1), q=F2.get(2,1), hh=h-q,
214 i=F1.get(2,2), r=F2.get(2,2), ii=i-r;
215
216 double a1=ee*ii-ff*hh, b1=ee*r+ii*n-ff*q-hh*o, c1=r*n-o*q;
217 double d1=bb*ii-cc*hh, e1=bb*r+ii*k-cc*q-hh*l, f1=r*k-l*q;
218 double g1=bb*ff-cc*ee, h1=bb*o+ff*k-cc*n-ee*l, i1=o*k-l*n;
219
220 std::vector<double> v;
221 v.push_back(aa*a1-dd*d1+gg*g1);
222 v.push_back(aa*b1+a1*j-dd*e1-d1*m+gg*h1+g1*p);
223 v.push_back(aa*c1+b1*j-dd*f1-e1*m+gg*i1+h1*p);
224 v.push_back(c1*j-f1*m+i1*p);
225
226 return v;
227 }
228
229 //--------------------
230 //:
231 // Gives solutions to 0x^3 + ax^2 + bx + c = 0.
232 // Returns the set of real solutions, so if both are imaginary it returns an
233 // empty list, otherwise a list of length two.
234 // v is a 4-vector of which the first element is ignored.
235 //-------------------
solve_quadratic(std::vector<double> v)236 std::vector<double> FMatrixCompute7Point::solve_quadratic (std::vector<double> v)
237 {
238 double a = v[1], b = v[2], c = v[3];
239 double s = (b > 0.0) ? 1.0 : -1.0;
240 double d = b * b - 4 * a * c;
241
242 // round off error
243 if ( d > -1e-5 && d < 0)
244 d = 0.0;
245
246 if (d < 0.0) // doesn't work for complex roots
247 return std::vector<double>(); // empty list
248
249 double q = -0.5 * ( b + s * std::sqrt(d));
250
251 std::vector<double> l; l.push_back(q/a); l.push_back(c/q);
252 return l;
253 }
254
255 // Compute cube root of a positive or a negative number
my_cbrt(double x)256 inline double my_cbrt(double x)
257 {
258 return (x>=0) ? std::exp(std::log(x)/3.0) : -std::exp(std::log(-x)/3.0);
259 }
260
261 //------------------
262 //:
263 // Solves a cubic and returns the real solutions.
264 // Thus it returns a list of length 1 if there are 2 complex roots and 1 real,
265 // of length 2 if it is in fact a quadratic with 2 solutions,
266 // of length 3 if there are 3 real solutions
267 // a x^3 + b x^2 + c x + d = 0
268 //-------------------
269 // Rewritten and documented by Peter Vanroose, 23 October 2001.
270
solve_cubic(std::vector<double> v)271 std::vector<double> FMatrixCompute7Point::solve_cubic(std::vector<double> v)
272 {
273 double a = v[0], b = v[1], c = v[2], d = v[3];
274
275 /* firstly check to see if we have approximately a quadratic */
276 double len = a*a + b*b + c*c + d*d;
277 if (std::abs(a*a/len) < 1e-6 )
278 return FMatrixCompute7Point::solve_quadratic(v);
279
280 b /= a; c /= a; d /= a; b /= 3;
281 // With the substitution x = y-b, the equation becomes y^3-3qy+2r = 0:
282 double q = b*b - c/3;
283 double r = b*(b*b-c/2) + d/2;
284 // At this point, a, c and d are no longer needed (c and d will be reused).
285
286 if (q == 0) {
287 std::vector<double> w; w.push_back(my_cbrt(-2*r) - b); return w;
288 }
289
290 // With the Vieta substitution y = z+q/z this becomes z^6+2rz^3+q^3 = 0
291 // which is essentially a quadratic equation:
292
293 d = r*r - q*q*q;
294 if ( d >= 0.0 )
295 {
296 double z = my_cbrt(-r + std::sqrt(d));
297 // The case z=0 is excluded since this is q==0 which is handled above
298 std::vector<double> w; w.push_back(z + q/z - b); return w;
299 }
300
301 // And finally the "irreducible case" (with 3 solutions):
302 c = std::sqrt(q);
303 double theta = std::acos( r/q/c ) / 3;
304 std::vector<double> l;
305 l.push_back(-2.0*c*std::cos(theta) - b);
306 l.push_back(-2.0*c*std::cos(theta + vnl_math::twopi/3) - b);
307 l.push_back(-2.0*c*std::cos(theta - vnl_math::twopi/3) - b);
308 return l;
309 }
310