| 16 | // ---------------------------------------------------------------------------------------- |
| 17 | |
| 18 | std::vector<long> align_points( |
| 19 | const std::vector<dpoint>& from, |
| 20 | const std::vector<dpoint>& to, |
| 21 | double min_angle = -90*pi/180.0, |
| 22 | double max_angle = 90*pi/180.0, |
| 23 | long num_angles = 181 |
| 24 | ) |
| 25 | /*! |
| 26 | ensures |
| 27 | - Figures out how to align the points in from with the points in to. Returns an |
| 28 | assignment array A that indicates that from[i] matches with to[A[i]]. |
| 29 | |
| 30 | We use the Hungarian algorithm with a search over reasonable angles. This method |
| 31 | works because we just need to account for a translation and a mild rotation and |
| 32 | nothing else. If there is any other more complex mapping then you probably don't |
| 33 | have landmarks that make sense to flip. |
| 34 | !*/ |
| 35 | { |
| 36 | DLIB_CASSERT(from.size() == to.size()); |
| 37 | |
| 38 | std::vector<long> best_assignment; |
| 39 | double best_assignment_cost = std::numeric_limits<double>::infinity(); |
| 40 | |
| 41 | matrix<double> dists(from.size(), to.size()); |
| 42 | matrix<long long> idists; |
| 43 | |
| 44 | for (auto angle : linspace(min_angle, max_angle, num_angles)) |
| 45 | { |
| 46 | auto rot = rotation_matrix(angle); |
| 47 | for (long r = 0; r < dists.nr(); ++r) |
| 48 | { |
| 49 | for (long c = 0; c < dists.nc(); ++c) |
| 50 | { |
| 51 | dists(r,c) = length_squared(rot*from[r]-to[c]); |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | idists = matrix_cast<long long>(-round(std::numeric_limits<long long>::max()*(dists/max(dists)))); |
| 56 | |
| 57 | auto assignment = max_cost_assignment(idists); |
| 58 | auto cost = assignment_cost(dists, assignment); |
| 59 | if (cost < best_assignment_cost) |
| 60 | { |
| 61 | best_assignment_cost = cost; |
| 62 | best_assignment = std::move(assignment); |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | |
| 67 | // Now compute the alignment error in terms of average distance moved by each part. We |
| 68 | // do this so we can give the user a warning if it's impossible to make a good |
| 69 | // alignment. |
| 70 | running_stats<double> rs; |
| 71 | std::vector<dpoint> tmp(to.size()); |
| 72 | for (size_t i = 0; i < to.size(); ++i) |
| 73 | tmp[best_assignment[i]] = to[i]; |
| 74 | auto tform = find_similarity_transform(from, tmp); |
| 75 | for (size_t i = 0; i < from.size(); ++i) |
no test coverage detected