ea5e2f7a8db1bc6387e4bb1251acc24a09ffe642
[blender.git] / extern / libmv / libmv / autotrack / autotrack.cc
1 // Copyright (c) 2014 libmv authors.
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a copy
4 // of this software and associated documentation files (the "Software"), to
5 // deal in the Software without restriction, including without limitation the
6 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
7 // sell copies of the Software, and to permit persons to whom the Software is
8 // furnished to do so, subject to the following conditions:
9 //
10 // The above copyright notice and this permission notice shall be included in
11 // all copies or substantial portions of the Software.
12 //
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
19 // IN THE SOFTWARE.
20 //
21 // Author: mierle@gmail.com (Keir Mierle)
22
23 #include "libmv/autotrack/autotrack.h"
24 #include "libmv/autotrack/quad.h"
25 #include "libmv/autotrack/frame_accessor.h"
26 #include "libmv/autotrack/predict_tracks.h"
27 #include "libmv/logging/logging.h"
28 #include "libmv/numeric/numeric.h"
29
30 namespace mv {
31
32 namespace {
33
34 template<typename QuadT, typename ArrayT>
35 void QuadToArrays(const QuadT& quad, ArrayT* x, ArrayT* y) {
36   for (int i = 0; i < 4; ++i) {
37     x[i] = quad.coordinates(i, 0);
38     y[i] = quad.coordinates(i, 1);
39   }
40 }
41
42 void MarkerToArrays(const Marker& marker, double* x, double* y) {
43   Quad2Df offset_quad = marker.patch;
44   Vec2f origin = marker.search_region.Rounded().min;
45   offset_quad.coordinates.rowwise() -= origin.transpose();
46   QuadToArrays(offset_quad, x, y);
47   x[4] = marker.center.x() - origin(0);
48   y[4] = marker.center.y() - origin(1);
49 }
50
51 FrameAccessor::Key GetImageForMarker(const Marker& marker,
52                                      FrameAccessor* frame_accessor,
53                                      FloatImage* image) {
54   // TODO(sergey): Currently we pass float region to the accessor,
55   // but we don't want the accessor to decide the rounding, so we
56   // do rounding here.
57   // Ideally we would need to pass IntRegion to the frame accessor.
58   Region region = marker.search_region.Rounded();
59   return frame_accessor->GetImage(marker.clip,
60                                   marker.frame,
61                                   FrameAccessor::MONO,
62                                   0,  // No downscale for now.
63                                   &region,
64                                   NULL,
65                                   image);
66 }
67
68 }  // namespace
69
70 bool AutoTrack::TrackMarker(Marker* tracked_marker,
71                             TrackRegionResult* result,
72                             const TrackRegionOptions* track_options) {
73   // Try to predict the location of the second marker.
74   bool predicted_position = false;
75   if (PredictMarkerPosition(tracks_, tracked_marker)) {
76     LG << "Succesfully predicted!";
77     predicted_position = true;
78   } else {
79     LG << "Prediction failed; trying to track anyway.";
80   }
81
82   Marker reference_marker;
83   tracks_.GetMarker(tracked_marker->reference_clip,
84                     tracked_marker->reference_frame,
85                     tracked_marker->track,
86                     &reference_marker);
87
88   // Convert markers into the format expected by TrackRegion.
89   double x1[5], y1[5];
90   MarkerToArrays(reference_marker, x1, y1);
91
92   double x2[5], y2[5];
93   MarkerToArrays(*tracked_marker, x2, y2);
94
95   // TODO(keir): Technically this could take a smaller slice from the source
96   // image instead of taking one the size of the search window.
97   FloatImage reference_image;
98   FrameAccessor::Key reference_key = GetImageForMarker(reference_marker,
99                                                        frame_accessor_,
100                                                        &reference_image);
101   if (!reference_key) {
102     LG << "Couldn't get frame for reference marker: " << reference_marker;
103     return false;
104   }
105
106   FloatImage tracked_image;
107   FrameAccessor::Key tracked_key = GetImageForMarker(*tracked_marker,
108                                                      frame_accessor_,
109                                                      &tracked_image);
110   if (!tracked_key) {
111     LG << "Couldn't get frame for tracked marker: " << tracked_marker;
112     return false;
113   }
114
115   // Store original position befoer tracking, so we can claculate offset later.
116   Vec2f original_center = tracked_marker->center;
117
118   // Do the tracking!
119   TrackRegionOptions local_track_region_options;
120   if (track_options) {
121     local_track_region_options = *track_options;
122   }
123   local_track_region_options.num_extra_points = 1;  // For center point.
124   local_track_region_options.attempt_refine_before_brute = predicted_position;
125   TrackRegion(reference_image,
126               tracked_image,
127               x1, y1,
128               local_track_region_options,
129               x2, y2,
130               result);
131
132   // Copy results over the tracked marker.
133   Vec2f tracked_origin = tracked_marker->search_region.Rounded().min;
134   for (int i = 0; i < 4; ++i) {
135     tracked_marker->patch.coordinates(i, 0) = x2[i] + tracked_origin[0];
136     tracked_marker->patch.coordinates(i, 1) = y2[i] + tracked_origin[1];
137   }
138   tracked_marker->center(0) = x2[4] + tracked_origin[0];
139   tracked_marker->center(1) = y2[4] + tracked_origin[1];
140   Vec2f delta = tracked_marker->center - original_center;
141   tracked_marker->search_region.Offset(delta);
142   tracked_marker->source = Marker::TRACKED;
143   tracked_marker->status = Marker::UNKNOWN;
144   tracked_marker->reference_clip  = reference_marker.clip;
145   tracked_marker->reference_frame = reference_marker.frame;
146
147   // Release the images from the accessor cache.
148   frame_accessor_->ReleaseImage(reference_key);
149   frame_accessor_->ReleaseImage(tracked_key);
150
151   // TODO(keir): Possibly the return here should get removed since the results
152   // are part of TrackResult. However, eventually the autotrack stuff will have
153   // extra status (e.g. prediction fail, etc) that should get included.
154   return true;
155 }
156
157 void AutoTrack::AddMarker(const Marker& marker) {
158   tracks_.AddMarker(marker);
159 }
160
161 void AutoTrack::SetMarkers(vector<Marker>* markers) {
162   tracks_.SetMarkers(markers);
163 }
164
165 bool AutoTrack::GetMarker(int clip, int frame, int track,
166                           Marker* markers) const {
167   return tracks_.GetMarker(clip, frame, track, markers);
168 }
169
170 void AutoTrack::DetectAndTrack(const DetectAndTrackOptions& options) {
171   int num_clips = frame_accessor_->NumClips();
172   for (int clip = 0; clip < num_clips; ++clip) {
173     int num_frames = frame_accessor_->NumFrames(clip);
174     vector<Marker> previous_frame_markers;
175     // Q: How to decide track #s when detecting?
176     // Q: How to match markers from previous frame? set of prev frame tracks?
177     // Q: How to decide what markers should get tracked and which ones should not?
178     for (int frame = 0; frame < num_frames; ++frame) {
179       if (Cancelled()) {
180         LG << "Got cancel message while detecting and tracking...";
181         return;
182       }
183       // First, get or detect markers for this frame.
184       vector<Marker> this_frame_markers;
185       tracks_.GetMarkersInFrame(clip, frame, &this_frame_markers);
186       LG << "Clip " << clip << ", frame " << frame << " have "
187          << this_frame_markers.size();
188       if (this_frame_markers.size() < options.min_num_features) {
189         DetectFeaturesInFrame(clip, frame);
190         this_frame_markers.clear();
191         tracks_.GetMarkersInFrame(clip, frame, &this_frame_markers);
192         LG << "... detected " << this_frame_markers.size() << " features.";
193       }
194       if (previous_frame_markers.empty()) {
195         LG << "First frame; skipping tracking stage.";
196         previous_frame_markers.swap(this_frame_markers);
197         continue;
198       }
199       // Second, find tracks that should get tracked forward into this frame.
200       // To avoid tracking markers that are already tracked to this frame, make
201       // a sorted set of the tracks that exist in the last frame.
202       vector<int> tracks_in_this_frame;
203       for (int i = 0; i < this_frame_markers.size(); ++i) {
204         tracks_in_this_frame.push_back(this_frame_markers[i].track);
205       }
206       std::sort(tracks_in_this_frame.begin(),
207                 tracks_in_this_frame.end());
208
209       // Find tracks in the previous frame that are not in this one.
210       vector<Marker*> previous_frame_markers_to_track;
211       int num_skipped = 0;
212       for (int i = 0; i < previous_frame_markers.size(); ++i) {
213         if (std::binary_search(tracks_in_this_frame.begin(),
214                                tracks_in_this_frame.end(),
215                                previous_frame_markers[i].track)) {
216           num_skipped++;
217         } else {
218           previous_frame_markers_to_track.push_back(&previous_frame_markers[i]);
219         }
220       }
221
222       // Finally track the markers from the last frame into this one.
223       // TODO(keir): Use OMP.
224       for (int i = 0; i < previous_frame_markers_to_track.size(); ++i) {
225         Marker this_frame_marker = *previous_frame_markers_to_track[i];
226         this_frame_marker.frame = frame;
227         LG << "Tracking: " << this_frame_marker;
228         TrackRegionResult result;
229         TrackMarker(&this_frame_marker, &result);
230         if (result.is_usable()) {
231           LG << "Success: " << this_frame_marker;
232           AddMarker(this_frame_marker);
233           this_frame_markers.push_back(this_frame_marker);
234         } else {
235           LG << "Failed to track: " << this_frame_marker;
236         }
237       }
238       // Put the markers from this frame
239       previous_frame_markers.swap(this_frame_markers);
240     }
241   }
242 }
243
244 }  // namespace mv