diff options
Diffstat (limited to 'extern')
24 files changed, 2436 insertions, 391 deletions
diff --git a/extern/libmv/CMakeLists.txt b/extern/libmv/CMakeLists.txt index 09c36fc4383..bd27228ec14 100644 --- a/extern/libmv/CMakeLists.txt +++ b/extern/libmv/CMakeLists.txt @@ -66,7 +66,7 @@ if(WITH_LIBMV) list(APPEND INC_SYS ../Eigen3 - ${PNG_INCLUDE_DIRS} + ${PNG_INCLUDE_DIR} ${ZLIB_INCLUDE_DIRS} ) @@ -79,6 +79,9 @@ if(WITH_LIBMV) intern/reconstruction.cc intern/track_region.cc intern/tracks.cc + libmv/autotrack/autotrack.cc + libmv/autotrack/predict_tracks.cc + libmv/autotrack/tracks.cc libmv/base/aligned_malloc.cc libmv/image/array_nd.cc libmv/image/convolve.cc @@ -122,6 +125,16 @@ if(WITH_LIBMV) intern/reconstruction.h intern/track_region.h intern/tracks.h + libmv/autotrack/autotrack.h + libmv/autotrack/callbacks.h + libmv/autotrack/frame_accessor.h + libmv/autotrack/marker.h + libmv/autotrack/model.h + libmv/autotrack/predict_tracks.h + libmv/autotrack/quad.h + libmv/autotrack/reconstruction.h + libmv/autotrack/region.h + libmv/autotrack/tracks.h libmv/base/aligned_malloc.h libmv/base/id_generator.h libmv/base/scoped_ptr.h @@ -171,6 +184,7 @@ if(WITH_LIBMV) libmv/simple_pipeline/tracks.h libmv/tracking/brute_region_tracker.h libmv/tracking/hybrid_region_tracker.h + libmv/tracking/kalman_filter.h libmv/tracking/klt_region_tracker.h libmv/tracking/pyramid_region_tracker.h libmv/tracking/region_tracker.h @@ -197,6 +211,8 @@ if(WITH_LIBMV) if(WITH_GTESTS) blender_add_lib(libmv_test_dataset "./libmv/multiview/test_data_sets.cc" "" "") + BLENDER_SRC_GTEST("libmv_predict_tracks" "./libmv/autotrack/predict_tracks_test.cc" "libmv_test_dataset;extern_libmv;extern_ceres") + BLENDER_SRC_GTEST("libmv_tracks" "./libmv/autotrack/tracks_test.cc" "libmv_test_dataset;extern_libmv;extern_ceres") BLENDER_SRC_GTEST("libmv_scoped_ptr" "./libmv/base/scoped_ptr_test.cc" "libmv_test_dataset;extern_libmv;extern_ceres") BLENDER_SRC_GTEST("libmv_vector" "./libmv/base/vector_test.cc" "libmv_test_dataset;extern_libmv;extern_ceres") BLENDER_SRC_GTEST("libmv_array_nd" "./libmv/image/array_nd_test.cc" "libmv_test_dataset;extern_libmv;extern_ceres") @@ -229,7 +245,7 @@ if(WITH_LIBMV) endif() else() list(APPEND SRC - intern/stub.cc + libmv-capi_stub.cc ) endif() @@ -240,7 +256,7 @@ if(WITH_LIBMV) endif() # make GLog a separate target, so it can be used for gtest as well. -if(WITH_LIBMV OR WITH_GTESTS OR WITH_CYCLES_LOGGING) +if(WITH_LIBMV OR WITH_GTESTS) # We compile GLog together with GFlag so we don't worry about # adding extra lib to linker. set(GLOG_SRC diff --git a/extern/libmv/ChangeLog b/extern/libmv/ChangeLog index 276fbb2ff0d..5c2129b6b1a 100644 --- a/extern/libmv/ChangeLog +++ b/extern/libmv/ChangeLog @@ -1,3 +1,365 @@ +commit d976e034cdf74b34860e0632d7b29713f47c5756 +Author: Keir Mierle <mierle@gmail.com> +Date: Sat Aug 23 00:38:01 2014 -0700 + + Minor keyframe selection cleanups + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D757 + +commit bc99ca55dadfca89fde0f93764397c2fe028943d +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Sat Aug 23 01:55:32 2014 +0600 + + implement backward prediction + + The title actually says it all, just extend current implementation + of PredictMarkerPosition() to cases when tracking happens in the reverse + order (from the end frame to start). + + it's still doesn't solve all the ambiguity happening in the function + in cases when one tracks the feature and then re-tracks it in order + to refine the sliding. This is considered a separate TODO for now and + will likely be solved by passing tracking direction to the prediction + function. + + Reviewers: keir + + Reviewed By: keir + + Differential Revision: https://developer.blender.org/D663 + +commit 5b87682d98df65ade02638bc6482d824cf0dd0b3 +Author: Keir Mierle <mierle@gmail.com> +Date: Thu Aug 21 22:45:22 2014 -0700 + + Make libmv compile on Ubuntu 14.04 + + Reviewers: fsiddi + + Reviewed By: fsiddi + + Subscribers: sergey + + Differential Revision: https://developer.blender.org/D755 + +commit 0a81db623c458e0384b4f7060d1bcff8993fb469 +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Wed Jul 23 00:42:00 2014 +0600 + + Fix wrong residual blocks counter + + This happened in cases when having zero-weighted tracks + and could lead to some assert failures on marking parameter + block constant. + +commit 2824dbac54cacf74828678be7a5c9fd960ce83e2 +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Fri Jul 18 12:52:03 2014 +0600 + + Fix search area sliding issue + + The only way to do this is to store search region in floats + and round when we need to sample it. Otherwise you'll always + have sliding effect caused by rounding the issues, especially + when doing incremental offset (thing which happens in the + prediction code). + + Pretty much straightforward change apart from stuff to be kept + in mind: offset calculation int should happen relative to the + rounded search region. This is because tracker works in the space + of the search window image which get's rounded on the frame access, + + This makes API a bit creepy because frame accessor uses the same + Region struct as the search window in Marker and ideally we would + need to have either IntRegion or Region<int> in order to make + Libmv fully track on what's getting rounded and when. + + Reviewers: keir + + Reviewed By: keir + + Differential Revision: https://developer.blender.org/D616 + +commit 04862c479332308be47a0f27361402444ace8880 +Author: Keir Mierle <mierle@gmail.com> +Date: Fri May 9 23:00:03 2014 +0200 + + Start the automatic 2D tracking code + + This starts the 2D automatic tracking code. It is totally unfinished. + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D523 + +commit be679f67d807a2139c1f7d7e2ca45141940b30d5 +Author: Keir Mierle <mierle@gmail.com> +Date: Fri May 9 14:36:04 2014 +0200 + + Also shift the search window + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D520 + +commit 66b8f5eef2633ebcde32a388fc14c60171011821 +Author: Keir Mierle <mierle@gmail.com> +Date: Fri May 9 13:06:28 2014 +0200 + + Change the search region to absolute frame coordinates + + Smarter Eigen usage + + Better error logging + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D519 + +commit a08193319ae409fad8f08887eae1f79f02e91eaa +Author: Keir Mierle <mierle@gmail.com> +Date: Fri May 9 12:02:47 2014 +0200 + + First cut at predictive tracing + + This adds a Kalman filter-based approach to predict where a marker + will go in the next frame to track. Hopefully this will make the + tracker work faster by avoiding lengthy searches. This code + compiles, but is otherwise untested, and likely does not work. + + Fix else branch + + Add some tests + + Update patch coordinates as well (and test) + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D518 + +commit 607ffb2f62b56e34a841abbb952d83e19cd1e23c +Author: Keir Mierle <mierle@gmail.com> +Date: Thu May 8 16:05:28 2014 +0200 + + Add constructor to AutoTrack + +commit c39e20a0c27da3733804c3848454b5d4c4f0e66b +Author: Keir Mierle <mierle@gmail.com> +Date: Thu May 8 16:04:20 2014 +0200 + + Fix GetMarker compilation issue + +commit 8dd93e431b6e44439c803bfd26ec2669b656177e +Author: Keir Mierle <mierle@gmail.com> +Date: Thu May 8 15:50:26 2014 +0200 + + Expose GetMarker() in AutoTrack + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D516 + +commit 4405dff60ea08d454b64da1a7c0595d9328cf8a3 +Author: Keir Mierle <mierle@gmail.com> +Date: Thu May 8 15:38:14 2014 +0200 + + Add public SetMarkers to AutoTrack + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D515 + +commit c90837f6db276a3b1f610eaad509155f6a43b24f +Author: Keir Mierle <mierle@gmail.com> +Date: Thu May 8 15:17:48 2014 +0200 + + Make autotrack skeleton compile + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D514 + +commit be01baa2e82e36f63e548f073157e68d2ff870c0 +Author: Keir Mierle <mierle@gmail.com> +Date: Wed May 7 18:48:55 2014 +0200 + + Add preliminary TrackMarkerToFrame in autotrack + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D509 + +commit 0cab028d591b3d08672ca86eb6c6e4ac1aacf1d0 +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Wed May 7 17:59:11 2014 +0200 + + Remove assert from ArrayND Resize + + That assert broke initialization of arrays which doesn't + own the data since constructor uses Resize to set shape + and strides. + + Strides are still to be fixed, but that's for later. + +commit 64f9c118029a9351e9023e96527c120e1d724d5b +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Wed May 7 17:42:21 2014 +0200 + + Fix ArrayND freeing the data it doesn't own + + Can't really guarantee it works fully correct now, + but at least this check is needed anyway and compilation + works just fine. + + Reviewers: keir + + Reviewed By: keir + + Differential Revision: https://developer.blender.org/D508 + +commit 0618f1c8e88dfc738cdde55784da80b889905e7c +Author: Keir Mierle <mierle@gmail.com> +Date: Wed May 7 12:03:32 2014 +0200 + + Minor changes + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D505 + +commit 5c34335e1bb90c4ed701ee830c718ed4e20dbffa +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Wed May 7 11:12:23 2014 +0200 + + Fix compilation error in frame accessor + + - int64 is not a standard type, we've got int64_t defined in + std int. We also have an msvc port of this header, so should + not be an issue. + + - Fixed inconsistency in usage of CacheKey and Key, used Key. + + - Some functions weren't marked as virtual. + + Additional change: added self to authors. + + Reviewers: keir + + Reviewed By: keir + + Differential Revision: https://developer.blender.org/D504 + +commit 06bc207614e262cd688e2c3ed820ade7c77bdb66 +Author: Keir Mierle <mierle@gmail.com> +Date: Tue May 6 22:30:59 2014 +0200 + + Start new Tracks implementation + + This adds the new Tracks implementation, as well as a + trivial test to show it compiles. + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D502 + +commit 25ce061e6da69881460ba7718bb0d660a2380a02 +Author: Keir Mierle <mierle@gmail.com> +Date: Tue May 6 19:10:51 2014 +0200 + + Add Reconstruction class for new API + + This starts the new Reconstruction class (with support for e.g. planes). This + also starts the new namespace "mv" which will eventually have all the symbols + we wish to export. + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D501 + +commit 0a6af3e29016048978aea607673340500e050339 +Author: Keir Mierle <mierle@gmail.com> +Date: Tue May 6 17:52:53 2014 +0200 + + Add a new Tracks implementation + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D500 + +commit 887b68d29c2b198f4939f9ab5153881aa2c1806e +Author: Keir Mierle <mierle@gmail.com> +Date: Tue May 6 17:01:39 2014 +0200 + + Initial commit of unfinished AutoTrack API + + This starts the creating the new AutoTrack API. The new API will + make it possible for libmv to do full autotracking, including + predictive tracking and also support multiple motion models (3D + planes etc). + + The first goal (not in this patch) is to convert Blender to use + the new API without adding any new functionality. + + Note: This does not add any of the API to the build system! + It likely does not compile. + + Reviewers: sergey + + Reviewed By: sergey + + Differential Revision: https://developer.blender.org/D499 + +commit 08cc227d431d257d27f300fbb8e6991e663302da +Author: Sergey Sharybin <sergey.vfx@gmail.com> +Date: Tue May 6 13:09:22 2014 +0200 + + Fix homography test failure + + It was caused by assuming that reconstructed homography matrix + should look exactly the same as the matrix used to generate a + test case. + + It's not actually valid assumption because different-looking + matrices could correspond to the same exact transform. + + In this change we make it so actual "re-projected" vectors + are being checked, not the values in matrix. This makes it + more predictable verification. + + Reviewers: keir + + Reviewed By: keir + + Differential Revision: https://developer.blender.org/D488 + commit 0b7d83dc9627447dc7df64d7e3a468aefe9ddc13 Author: Sergey Sharybin <sergey.vfx@gmail.com> Date: Wed Apr 23 19:14:55 2014 +0600 @@ -338,342 +700,3 @@ Date: Thu Feb 13 23:55:03 2014 +0600 Actually we're to switch to external Ceres rather than bundled one, would make life much easier actually. - -commit b1381540305d69c702eb2f051bd543fb5c1c3e2c -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Thu Feb 6 18:01:58 2014 +0600 - - Made FAST detector optional - - This way it's possible to bundle Libmv sources subset - to applications which doesn't need FAST detector. - - Mainly this is done for Blender integration. - -commit da4607f010bca0b3532cd4444afbb10bc774fc32 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Jan 28 18:32:39 2014 +0600 - - Implemented scoped_array and use it in detector - - scoped_array is pretty much the same as scoped_ptr - with the only difference that it'll free memory using - delete[] operator. - - It also gives some additional API functions to access - array elements. - - Currently it only used to manage images denoted as byte - arrays in detector. - - Reviewers: keir - - Reviewed By: keir - - Differential Revision: https://developer.blender.org/D266 - -commit cd7eb3eff2e69ce5e08570ead83ae6d35ee48857 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Jan 28 17:23:47 2014 +0600 - - Improvements to weighted tracks behavior - - First thing changed by this commit is making it so - Euclidean intersection takes track weight into account - when solving minimization problem. This behaves the - same exact way as it is for BA step. - - Second thing is related on how average reprojection error - is being calculated. It didn't take track weight into - account which could confuse users. Now average reprojection - error will give the same result as intersection/BA uses - during minimization which gives much more predictable - behavior. - - Reviewers: keir - - Reviewed By: keir - - CC: sebastian_k - - Differential Revision: https://developer.blender.org/D265 - -commit 6559b36dc14369175bfa0830323146acd3426483 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Jan 28 16:39:14 2014 +0600 - - Fixes for keyframe selection - - Using tracks with constant zero weight used to crash - keyframe selection since it was trying to use missing - parameter blocks for Jacobian evaluation, - - Also fixed possible issues with wrong camera block being - marked as variable. This could technically happen when - having zero weighted tracks. Made it so all camera blocks - are marked as variable for now. - -commit 557d531b061aa69d114e89cbb325c5175389afec -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Jan 28 16:10:33 2014 +0600 - - Style cleanup: wrong indentation of wrapped line - -commit ca15262cf07a873268173965ee1fb84f9729b744 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Jan 28 15:21:36 2014 +0600 - - Rework detector API and implement Harris detector - - Switch the detector API to a single function which accepts - a float image and detector options. This makes usage of - feature detection more unified across different algorithms. - - Options structure is pretty much straightforward and contains - detector to be used and all the detector-specific settings. - - Also implemented Harris feature detection algorithm which - is not as fast as FAST one but is expected to detect more - robust feature points. - - Reviewers: keir - - Reviewed By: keir - - Differential Revision: https://developer.blender.org/D258 - -commit 6458915f64fceba108c5279b7320ca8c76e8a742 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Fri Jan 24 19:14:18 2014 +0600 - - Add arcanist configuration file - -commit 0a69fadadc5aacbd339f839ac5bd12c3571278b1 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Thu Jan 9 15:50:11 2014 +0600 - - Fix compilation error on NetBSD - - - NetBSD doesn't provide sincos(3) in libm, so don't try to use it - - Use posix_memalign on NetBSD - - Original patch is by Jeorg Sonnenberger to Blender patch tracker, thanks! - -commit b0df3e291e6c85f791658be04334efafc41989f5 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Thu Jan 2 15:12:18 2014 +0600 - - Fix build configuration warnings - - Those warnings were mainly caused by installation - configuration of Ceres. Made some tweaks to make - CMake happy for now. - - But for sure bigger cleanup here is needed. - -commit b68de6acd20f3ffab92e0cd450198a700cd109ab -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Thu Jan 2 15:04:05 2014 +0600 - - Code and style cleanup - - Mainly fixed some style warnings reported by cpplint. - - Also changed how camera (un)distortion happens internally - by replacing number of channels as a template argument - with number as channels passing as function argument. - Makes code easier to follow by eliminating loads checks - how much channels are used and which argument to pass to - the template. - -commit b9e467e7c077b58199c4110f6967b7c18d1e7bf7 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 20:34:39 2013 +0600 - - Update Ceres to the latest upstream - - This brings up much easier termination type usage, - which for us means we might use: - - ceres::Summary::IsSolutionUsable() - - instead of doing manual funky enum values check. - -commit 3aeb2367e50b52ca2b9d59d4f0f0b4bbfd6a05e8 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 20:43:24 2013 +0600 - - Update gtest to latest version 1.7.0 - - Also reshuffled CMakeLists in order to avoid - conflicts happening between gflags bundled to - Ceres and third_party. - -commit 30aaa9cd0b4a4eb0948a17824e7e7622d8ebcb41 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 20:10:06 2013 +0600 - - Changes for VC2013 - - Solves compilation error when using msvc2013 - - Original patch is by Alexandr Kuznetsov to blender.git - -commit b204c0d25065a2b149de256929ff37d8f00f45bb -Author: Keir Mierle <mierle@gmail.com> -Date: Tue Dec 31 20:05:58 2013 +0600 - - Eagerly attempt to refine a track before doing a brute search - - Before the refinement phase of tracking, a brute force SAD search - is run across the search area. This works well but is slow; - especially if the guess for the track's location is accurate. - - This patch runs a refinement phase before running a brute force - search, hoping that the guessed position (in x2, y2) is close to - the best answer. If it is, then no brute search is done. If it is - not, then a normal brute force search followed by refinement is - done. - - In some cases this may produce worse tracks than before; the - regressions will need investigation. The predictive motion model - (to be implemented) will reduce the probability of that happening. - -commit 5361513f0328ff94b53125d29129561bb03132e8 -Author: Keir Mierle <mierle@gmail.com> -Date: Tue Dec 31 20:04:46 2013 +0600 - - Fix bug where libmv tracking incorrectly succeeds on failure - - Before this patch, if Ceres returned USER_SUCCESS indicating that - Ceres was only changing the tracked quad slightly between - iterations (indicating convergence), no final correlation check - was done. This leads to incorrectly returning that the tracking - was successful, when it actually failed. - -commit ba9e63eed09e33a48bbcb081058f45ac16f8738e -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 20:00:46 2013 +0600 - - Implementation of weighted tracks - - Added a weight field to Track structure which means - how much affect this track will have on the final - reconstruction. - - Currently it affects on BA step only which in most - cases will work just fine. However, it worth looking - into weight support for intersection/resection. - -commit 4600df8b685ca8c4daa22d6c3b0125fd42c3bc67 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 19:30:14 2013 +0600 - - Code cleanup: move function prototype to header file - -commit 0ce5b6efde774b3f042acf9e42c95674548f1c01 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 19:26:48 2013 +0600 - - Get rid of Allow Fallback option for euclidean resection - - It was rather confusing from the user usage point of view - and didn't get so much improvement after new bundle adjuster - was added. - - In the future we might want to switch resection to PPnP algorithm, - which could also might be a nice alternative to fallback option. - -commit 5d063426f4809000c27f38ed798e4224bbd09a6d -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 19:24:05 2013 +0600 - - Use explicit declaration of int types sign - - Mainly needs to make blender happy with this custom - header which used to run into conflict with other int - types headers. - - Wouldn't harm being more explicit here anyway. - -commit c5be59dee94f94de369006c544080282cfb245cc -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Tue Dec 31 14:50:00 2013 +0600 - - Implement refinement of estimated homography/fundamental matrices - - It was only possible to perform algebraic estimation, which didn't - give so much accurate results. - - Implemented a way to perform algebraic estimation followed with - refinement step using Ceres minimizer. - - The code was actually mostly already there since keyframe selection - patch. Made such estimation a generic function in multiview/ and - hanged API for estimation in order to pass all additional options via - an options structure (the same way as it's done fr Ceres). - - Most of the options are straight-forward to understand,but some - deserves more description here: - - * expected_average_symmetric_distance is used as an early output check - and as soon as average symmetric error goes below this threshold - refining finishes. - - This distance is measured in the same units as input points are. - - It is arguable whether we need callback for this or not, but seems - Ceres doesn't have some kind of absolute threshold for function value - and function_tolerance behaves different from logic behind expected - symmetric error. - - * There' an option to normalize correspondences before estimating the - homography in order to increase estimation stability. See - - R. Hartley and A. Zisserman. Multiple View Geometry in Computer - Vision. Cambridge University Press, second edition, 2003. - - https://www.cs.ubc.ca/grads/resources/thesis/May09/Dubrofsky_Elan.pdf - -commit 1cdad972c4a9005e78891524cbd6d65600ca7e99 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Wed Sep 25 16:12:29 2013 +0600 - - Code cleanup: Minor function capitalization fix - - Original patch by Joseph Mansfield to the Blender repository. - -commit 434316d084e8a41fd452f03610d7244d664948dc -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Wed Sep 25 16:07:43 2013 +0600 - - Code cleanup: spelling correction - - Original patch by Joseph Mansfield to the Blender repository. - -commit 5cfe8465ac70407c0959c53bcd5206657a1322a2 -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Wed Sep 25 16:02:48 2013 +0600 - - Fix for uninitialized covariance matrix - - Lead to unpredictable tracking termination criteria. - -commit fd86b77d413489649a989f075b061714ed9a72fc -Author: Sergey Sharybin <sergey.vfx@gmail.com> -Date: Wed Sep 25 16:01:19 2013 +0600 - - Add Procrustes PNP ("PPnP") resection algorithm to libmv - - This adds a new Euclidean resection method, used to create the - initial reconstruction in the motion tracker, to libmv. The method - is based on the Procrustes PNP algorithm (aka "PPnP"). Currently - the algorithm is not connected with the motion tracker, but it - will be eventually since it supports initialization. - - Having an initial guess when doing resection is important for - ambiguous cases where potentially the user could offer extra - guidance to the solver, in the form of "this point is in front of - that point". - - Original patch by Keir Mierle made to Blender repository. diff --git a/extern/libmv/SConscript b/extern/libmv/SConscript index 162fb88df53..96282f3c3c2 100644 --- a/extern/libmv/SConscript +++ b/extern/libmv/SConscript @@ -6,7 +6,6 @@ import sys import os -from FindSharedPtr import FindSharedPtr Import('env') @@ -29,6 +28,7 @@ if env['WITH_BF_LIBMV']: src = env.Glob('intern/*.cc') src.remove('intern' + os.sep + 'stub.cc') + src += env.Glob('libmv/autotrack/*.cc') src += env.Glob('libmv/base/*.cc') src += env.Glob('libmv/image/*.cc') src += env.Glob('libmv/multiview/*.cc') diff --git a/extern/libmv/files.txt b/extern/libmv/files.txt index f1eb9580ff5..a206ffe1edd 100644 --- a/extern/libmv/files.txt +++ b/extern/libmv/files.txt @@ -1,3 +1,18 @@ +libmv/autotrack/autotrack.cc +libmv/autotrack/autotrack.h +libmv/autotrack/callbacks.h +libmv/autotrack/frame_accessor.h +libmv/autotrack/marker.h +libmv/autotrack/model.h +libmv/autotrack/predict_tracks.cc +libmv/autotrack/predict_tracks.h +libmv/autotrack/predict_tracks_test.cc +libmv/autotrack/quad.h +libmv/autotrack/reconstruction.h +libmv/autotrack/region.h +libmv/autotrack/tracks.cc +libmv/autotrack/tracks.h +libmv/autotrack/tracks_test.cc libmv/base/aligned_malloc.cc libmv/base/aligned_malloc.h libmv/base/id_generator.h @@ -104,6 +119,7 @@ libmv/tracking/brute_region_tracker.h libmv/tracking/brute_region_tracker_test.cc libmv/tracking/hybrid_region_tracker.cc libmv/tracking/hybrid_region_tracker.h +libmv/tracking/kalman_filter.h libmv/tracking/klt_region_tracker.cc libmv/tracking/klt_region_tracker.h libmv/tracking/klt_region_tracker_test.cc diff --git a/extern/libmv/libmv/autotrack/autotrack.cc b/extern/libmv/libmv/autotrack/autotrack.cc new file mode 100644 index 00000000000..ea5e2f7a8db --- /dev/null +++ b/extern/libmv/libmv/autotrack/autotrack.cc @@ -0,0 +1,244 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#include "libmv/autotrack/autotrack.h" +#include "libmv/autotrack/quad.h" +#include "libmv/autotrack/frame_accessor.h" +#include "libmv/autotrack/predict_tracks.h" +#include "libmv/logging/logging.h" +#include "libmv/numeric/numeric.h" + +namespace mv { + +namespace { + +template<typename QuadT, typename ArrayT> +void QuadToArrays(const QuadT& quad, ArrayT* x, ArrayT* y) { + for (int i = 0; i < 4; ++i) { + x[i] = quad.coordinates(i, 0); + y[i] = quad.coordinates(i, 1); + } +} + +void MarkerToArrays(const Marker& marker, double* x, double* y) { + Quad2Df offset_quad = marker.patch; + Vec2f origin = marker.search_region.Rounded().min; + offset_quad.coordinates.rowwise() -= origin.transpose(); + QuadToArrays(offset_quad, x, y); + x[4] = marker.center.x() - origin(0); + y[4] = marker.center.y() - origin(1); +} + +FrameAccessor::Key GetImageForMarker(const Marker& marker, + FrameAccessor* frame_accessor, + FloatImage* image) { + // TODO(sergey): Currently we pass float region to the accessor, + // but we don't want the accessor to decide the rounding, so we + // do rounding here. + // Ideally we would need to pass IntRegion to the frame accessor. + Region region = marker.search_region.Rounded(); + return frame_accessor->GetImage(marker.clip, + marker.frame, + FrameAccessor::MONO, + 0, // No downscale for now. + ®ion, + NULL, + image); +} + +} // namespace + +bool AutoTrack::TrackMarker(Marker* tracked_marker, + TrackRegionResult* result, + const TrackRegionOptions* track_options) { + // Try to predict the location of the second marker. + bool predicted_position = false; + if (PredictMarkerPosition(tracks_, tracked_marker)) { + LG << "Succesfully predicted!"; + predicted_position = true; + } else { + LG << "Prediction failed; trying to track anyway."; + } + + Marker reference_marker; + tracks_.GetMarker(tracked_marker->reference_clip, + tracked_marker->reference_frame, + tracked_marker->track, + &reference_marker); + + // Convert markers into the format expected by TrackRegion. + double x1[5], y1[5]; + MarkerToArrays(reference_marker, x1, y1); + + double x2[5], y2[5]; + MarkerToArrays(*tracked_marker, x2, y2); + + // TODO(keir): Technically this could take a smaller slice from the source + // image instead of taking one the size of the search window. + FloatImage reference_image; + FrameAccessor::Key reference_key = GetImageForMarker(reference_marker, + frame_accessor_, + &reference_image); + if (!reference_key) { + LG << "Couldn't get frame for reference marker: " << reference_marker; + return false; + } + + FloatImage tracked_image; + FrameAccessor::Key tracked_key = GetImageForMarker(*tracked_marker, + frame_accessor_, + &tracked_image); + if (!tracked_key) { + LG << "Couldn't get frame for tracked marker: " << tracked_marker; + return false; + } + + // Store original position befoer tracking, so we can claculate offset later. + Vec2f original_center = tracked_marker->center; + + // Do the tracking! + TrackRegionOptions local_track_region_options; + if (track_options) { + local_track_region_options = *track_options; + } + local_track_region_options.num_extra_points = 1; // For center point. + local_track_region_options.attempt_refine_before_brute = predicted_position; + TrackRegion(reference_image, + tracked_image, + x1, y1, + local_track_region_options, + x2, y2, + result); + + // Copy results over the tracked marker. + Vec2f tracked_origin = tracked_marker->search_region.Rounded().min; + for (int i = 0; i < 4; ++i) { + tracked_marker->patch.coordinates(i, 0) = x2[i] + tracked_origin[0]; + tracked_marker->patch.coordinates(i, 1) = y2[i] + tracked_origin[1]; + } + tracked_marker->center(0) = x2[4] + tracked_origin[0]; + tracked_marker->center(1) = y2[4] + tracked_origin[1]; + Vec2f delta = tracked_marker->center - original_center; + tracked_marker->search_region.Offset(delta); + tracked_marker->source = Marker::TRACKED; + tracked_marker->status = Marker::UNKNOWN; + tracked_marker->reference_clip = reference_marker.clip; + tracked_marker->reference_frame = reference_marker.frame; + + // Release the images from the accessor cache. + frame_accessor_->ReleaseImage(reference_key); + frame_accessor_->ReleaseImage(tracked_key); + + // TODO(keir): Possibly the return here should get removed since the results + // are part of TrackResult. However, eventually the autotrack stuff will have + // extra status (e.g. prediction fail, etc) that should get included. + return true; +} + +void AutoTrack::AddMarker(const Marker& marker) { + tracks_.AddMarker(marker); +} + +void AutoTrack::SetMarkers(vector<Marker>* markers) { + tracks_.SetMarkers(markers); +} + +bool AutoTrack::GetMarker(int clip, int frame, int track, + Marker* markers) const { + return tracks_.GetMarker(clip, frame, track, markers); +} + +void AutoTrack::DetectAndTrack(const DetectAndTrackOptions& options) { + int num_clips = frame_accessor_->NumClips(); + for (int clip = 0; clip < num_clips; ++clip) { + int num_frames = frame_accessor_->NumFrames(clip); + vector<Marker> previous_frame_markers; + // Q: How to decide track #s when detecting? + // Q: How to match markers from previous frame? set of prev frame tracks? + // Q: How to decide what markers should get tracked and which ones should not? + for (int frame = 0; frame < num_frames; ++frame) { + if (Cancelled()) { + LG << "Got cancel message while detecting and tracking..."; + return; + } + // First, get or detect markers for this frame. + vector<Marker> this_frame_markers; + tracks_.GetMarkersInFrame(clip, frame, &this_frame_markers); + LG << "Clip " << clip << ", frame " << frame << " have " + << this_frame_markers.size(); + if (this_frame_markers.size() < options.min_num_features) { + DetectFeaturesInFrame(clip, frame); + this_frame_markers.clear(); + tracks_.GetMarkersInFrame(clip, frame, &this_frame_markers); + LG << "... detected " << this_frame_markers.size() << " features."; + } + if (previous_frame_markers.empty()) { + LG << "First frame; skipping tracking stage."; + previous_frame_markers.swap(this_frame_markers); + continue; + } + // Second, find tracks that should get tracked forward into this frame. + // To avoid tracking markers that are already tracked to this frame, make + // a sorted set of the tracks that exist in the last frame. + vector<int> tracks_in_this_frame; + for (int i = 0; i < this_frame_markers.size(); ++i) { + tracks_in_this_frame.push_back(this_frame_markers[i].track); + } + std::sort(tracks_in_this_frame.begin(), + tracks_in_this_frame.end()); + + // Find tracks in the previous frame that are not in this one. + vector<Marker*> previous_frame_markers_to_track; + int num_skipped = 0; + for (int i = 0; i < previous_frame_markers.size(); ++i) { + if (std::binary_search(tracks_in_this_frame.begin(), + tracks_in_this_frame.end(), + previous_frame_markers[i].track)) { + num_skipped++; + } else { + previous_frame_markers_to_track.push_back(&previous_frame_markers[i]); + } + } + + // Finally track the markers from the last frame into this one. + // TODO(keir): Use OMP. + for (int i = 0; i < previous_frame_markers_to_track.size(); ++i) { + Marker this_frame_marker = *previous_frame_markers_to_track[i]; + this_frame_marker.frame = frame; + LG << "Tracking: " << this_frame_marker; + TrackRegionResult result; + TrackMarker(&this_frame_marker, &result); + if (result.is_usable()) { + LG << "Success: " << this_frame_marker; + AddMarker(this_frame_marker); + this_frame_markers.push_back(this_frame_marker); + } else { + LG << "Failed to track: " << this_frame_marker; + } + } + // Put the markers from this frame + previous_frame_markers.swap(this_frame_markers); + } + } +} + +} // namespace mv diff --git a/extern/libmv/libmv/autotrack/autotrack.h b/extern/libmv/libmv/autotrack/autotrack.h new file mode 100644 index 00000000000..7f8dbb91d98 --- /dev/null +++ b/extern/libmv/libmv/autotrack/autotrack.h @@ -0,0 +1,226 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_AUTOTRACK_H_ +#define LIBMV_AUTOTRACK_AUTOTRACK_H_ + +#include "libmv/autotrack/tracks.h" +#include "libmv/autotrack/region.h" +#include "libmv/tracking/track_region.h" + +namespace libmv { +class CameraIntrinsics; +}; + +namespace mv { + +using libmv::CameraIntrinsics; +using libmv::TrackRegionOptions; +using libmv::TrackRegionResult; + +class FrameAccessor; +class OperationListener; + +// The coordinator of all tracking operations; keeps track of all state +// relating to tracking and reconstruction; for example, 2D tracks and motion +// models, reconstructed cameras, points, and planes; tracking settings; etc. +// +// Typical usage for full autotrack: +// +// AutoTrack auto_track(image_accessor); +// auto_track.SetNumFramesInClip(0, 10); +// auto_track.SetNumFramesInClip(1, 54); +// auto_track.AutoTrack() +// +// It is also possible to specify options to control the reconstruction. +// Furthermore, the individual methods of reconstruction are exposed to make it +// possible to interact with the pipeline as it runs. For example, to track one +// marker across frames, +// +// AutoTrack auto_track(image_accessor); +// auto_track.SetNumFramesInClip(0, 10); +// auto_track.SetNumFramesInClip(1, 54); +// auto_track.AddMarker(...); +// auto_track.TrackMarkerToFrame(int clip1, int frame1, +// int clip2, int frame2, +// options?) +// +class AutoTrack { + public: + struct Options { + // Default configuration for 2D tracking when calling TrackMarkerToFrame(). + TrackRegionOptions track_region; + + // Default search window for region tracking, in absolute frame pixels. + Region search_region; + }; + + AutoTrack(FrameAccessor* frame_accessor) + : frame_accessor_(frame_accessor) {} + + // Marker manipulation. + // Clip manipulation. + + // Set the number of clips. These clips will get accessed from the frame + // accessor, matches between frames found, and a reconstruction created. + //void SetNumFrames(int clip, int num_frames); + + // Tracking & Matching + + // Find the marker for the track in the frame indicated by the marker. + // Caller maintains ownership of *result and *tracked_marker. + bool TrackMarker(Marker* tracked_marker, + TrackRegionResult* result, + const TrackRegionOptions* track_options=NULL); + + // Wrapper around Tracks API; however these may add additional processing. + void AddMarker(const Marker& tracked_marker); + void SetMarkers(vector<Marker>* markers); + bool GetMarker(int clip, int frame, int track, Marker* marker) const; + + // TODO(keir): Implement frame matching! This could be very cool for loop + // closing and connecting across clips. + //void MatchFrames(int clip1, int frame1, int clip2, int frame2) {} + + // Wrapper around the Reconstruction API. + // Returns the new ID. + int AddCameraIntrinsics(CameraIntrinsics* intrinsics) { + (void) intrinsics; + return 0; + } // XXX + int SetClipIntrinsics(int clip, int intrinsics) { + (void) clip; + (void) intrinsics; + return 0; + } // XXX + + enum Motion { + GENERAL_CAMERA_MOTION, + TRIPOD_CAMERA_MOTION, + }; + int SetClipMotion(int clip, Motion motion) { + (void) clip; + (void) motion; + return 0; + } // XXX + + // Decide what to refine for the given intrinsics. bundle_options is from + // bundle.h (e.g. BUNDLE_FOCAL_LENGTH | BUNDLE_RADIAL_K1). + void SetIntrinsicsRefine(int intrinsics, int bundle_options) { + (void) intrinsics; + (void) bundle_options; + } // XXX + + // Keyframe read/write. + struct ClipFrame { + int clip; + int frame; + }; + const vector<ClipFrame>& keyframes() { return keyframes_; } + void ClearKeyframes() { keyframes_.clear(); } + void SetKeyframes(const vector<ClipFrame>& keyframes) { + keyframes_ = keyframes; + } + + // What about reporting what happened? -- callbacks; maybe result struct. + void Reconstruct(); + + // Detect and track in 2D. + struct DetectAndTrackOptions { + int min_num_features; + }; + void DetectAndTrack(const DetectAndTrackOptions& options); + + struct DetectFeaturesInFrameOptions { + }; + void DetectFeaturesInFrame(int clip, int frame, + const DetectFeaturesInFrameOptions* options=NULL) { + (void) clip; + (void) frame; + (void) options; + } // XXX + + // Does not take ownership of the given listener, but keeps a reference to it. + void AddListener(OperationListener* listener) {(void) listener;} // XXX + + // Create the initial reconstruction, + //void FindInitialReconstruction(); + + // State machine + // + // Question: Have explicit state? Or determine state from existing data? + // Conclusion: Determine state from existing data. + // + // Preliminary state thoughts + // + // No tracks or markers + // - Tracks empty. + // + // Initial tracks found + // - All images have at least 5 tracks + // + // Ran RANSAC on tracks to mark inliers / outliers. + // - All images have at least 8 "inlier" tracks + // + // Detector matching run to close loops and match across clips + // - At least 5 matching tracks between clips + // + // Initial reconstruction found (2 frames)? + // - There exists two cameras with intrinsics / extrinsics + // + // Preliminary reconstruction finished + // - Poses for all frames in all clips estimated. + // + // Final reconstruction finished + // - Final reconstruction bundle adjusted. + + // For now, expose options directly. In the future this may change. + Options options; + + private: + bool Log(); + bool Progress(); + bool Cancelled() { return false; } + + Tracks tracks_; // May be normalized camera coordinates or raw pixels. + //Reconstruction reconstruction_; + + // TODO(keir): Add the motion models here. + //vector<MotionModel> motion_models_; + + // TODO(keir): Should num_clips and num_frames get moved to FrameAccessor? + // TODO(keir): What about masking for clips and frames to prevent various + // things like reconstruction or tracking from happening on certain frames? + FrameAccessor* frame_accessor_; + //int num_clips_; + //vector<int> num_frames_; // Indexed by clip. + + // The intrinsics for each clip, assuming each clip has fixed intrinsics. + // TODO(keir): Decide what the semantics should be for varying focal length. + vector<int> clip_intrinsics_; + + vector<ClipFrame> keyframes_; +}; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_AUTOTRACK_H_ diff --git a/extern/libmv/libmv/autotrack/callbacks.h b/extern/libmv/libmv/autotrack/callbacks.h new file mode 100644 index 00000000000..e65841de3ce --- /dev/null +++ b/extern/libmv/libmv/autotrack/callbacks.h @@ -0,0 +1,38 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_LISTENER_H_ +#define LIBMV_AUTOTRACK_LISTENER_H_ + +namespace mv { + +struct OperationListener { + // All hooks return true to continue or false to indicate the operation + // should abort. Hooks should be thread safe (reentrant). + virtual bool Log(const string& message) = 0; + virtual bool Progress(double fraction) = 0; + virtual bool Cancelled() = 0; +}; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_LISTENER_H_ diff --git a/extern/libmv/libmv/autotrack/frame_accessor.h b/extern/libmv/libmv/autotrack/frame_accessor.h new file mode 100644 index 00000000000..e788bb8ab97 --- /dev/null +++ b/extern/libmv/libmv/autotrack/frame_accessor.h @@ -0,0 +1,85 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_FRAME_ACCESSOR_H_ +#define LIBMV_AUTOTRACK_FRAME_ACCESSOR_H_ + +#include <stdint.h> + +#include "libmv/image/image.h" + +namespace mv { + +struct Region; + +using libmv::FloatImage; + +// This is the abstraction to different sources of images that will be part of +// a reconstruction. These may come from disk or they may come from Blender. In +// most cases it's expected that the implementation provides some caching +// otherwise performance will be terrible. Sometimes the images need to get +// filtered, and this interface provides for that as well (and permits +// implementations to cache filtered image pieces). +struct FrameAccessor { + struct Transform { + // The key should depend on the transform arguments. Must be non-zero. + virtual int64_t key() const = 0; + + // Apply the expected transform. Output is sized correctly already. + // TODO(keir): What about blurs that need to access pixels outside the ROI? + virtual void run(const FloatImage& input, FloatImage* output) const = 0; + }; + + enum InputMode { + MONO, + RGBA + }; + + typedef void* Key; + + // Get a possibly-filtered version of a frame of a video. Downscale will + // cause the input image to get downscaled by 2^downscale for pyramid access. + // Region is always in original-image coordinates, and describes the + // requested area. The transform describes an (optional) transform to apply + // to the image before it is returned. + // + // When done with an image, you must call ReleaseImage with the returned key. + virtual Key GetImage(int clip, + int frame, + InputMode input_mode, + int downscale, // Downscale by 2^downscale. + const Region* region, // Get full image if NULL. + const Transform* transform, // May be NULL. + FloatImage* destination) = 0; + + // Releases an image from the frame accessor. Non-caching implementations may + // free the image immediately; others may hold onto the image. + virtual void ReleaseImage(Key) = 0; + + virtual bool GetClipDimensions(int clip, int* width, int* height) = 0; + virtual int NumClips() = 0; + virtual int NumFrames(int clip) = 0; +}; + +} // namespace libmv + +#endif // LIBMV_AUTOTRACK_FRAME_ACCESSOR_H_ diff --git a/extern/libmv/libmv/autotrack/marker.h b/extern/libmv/libmv/autotrack/marker.h new file mode 100644 index 00000000000..dc73de84ee2 --- /dev/null +++ b/extern/libmv/libmv/autotrack/marker.h @@ -0,0 +1,135 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_MARKER_H_ +#define LIBMV_AUTOTRACK_MARKER_H_ + +#include <ostream> + +#include "libmv/autotrack/quad.h" +#include "libmv/autotrack/region.h" +#include "libmv/numeric/numeric.h" + +namespace mv { + +using libmv::Vec2f; + +// A marker is the 2D location of a tracked region (quad) in an image. +// Note that some of this information could be normalized by having a +// collection of inter-connected structs. Instead the "fat Marker" design below +// trades memory for data structure simplicity. +struct Marker { + int clip; // The clip this marker is from. + int frame; // The frame within the clip this marker is from. + int track; // The track this marker is from. + + // The center of the marker in frame coordinates. This is typically, but not + // always, the same as the center of the patch. + Vec2f center; + + // A frame-realtive quad defining the part of the image the marker covers. + // For reference markers, the pixels in the patch are the tracking pattern. + Quad2Df patch; + + // Some markers are less certain than others; the weight determines the + // amount this marker contributes to the error. 1.0 indicates normal + // contribution; 0.0 indicates a zero-weight track (and will be omitted from + // bundle adjustment). + float weight; + + enum Source { + MANUAL, // The user placed this marker manually. + DETECTED, // A keypoint detector found this point. + TRACKED, // The tracking algorithm placed this marker. + MATCHED, // A matching algorithm (e.g. SIFT or SURF or ORB) found this. + PREDICTED, // A motion model predicted this marker. This is needed for + // handling occlusions in some cases where an imaginary marker + // is placed to keep camera motion smooth. + }; + Source source; + + // Markers may be inliers or outliers if the tracking fails; this allows + // visualizing the markers in the image. + enum Status { + UNKNOWN, + INLIER, + OUTLIER + }; + Status status; + + // When doing correlation tracking, where to search in the current frame for + // the pattern from the reference frame, in absolute frame coordinates. + Region search_region; + + // For tracked and matched markers, indicates what the reference was. + int reference_clip; + int reference_frame; + + // Model related information for non-point tracks. + // + // Some tracks are on a larger object, such as a plane or a line or perhaps + // another primitive (a rectangular prisim). This captures the information + // needed to say that for example a collection of markers belongs to model #2 + // (and model #2 is a plane). + enum ModelType { + POINT, + PLANE, + LINE, + CUBE + }; + ModelType model_type; + + // The model ID this track (e.g. the second model, which is a plane). + int model_id; + + // TODO(keir): Add a "int model_argument" to capture that e.g. a marker is on + // the 3rd face of a cube. + + // Offset everything (center, patch, search) by the given delta. + template<typename T> + void Offset(const T& offset) { + center += offset.template cast<float>(); + patch.coordinates.rowwise() += offset.template cast<int>(); + search_region.Offset(offset); + } + + // Shift the center to the given new position (and patch, search). + template<typename T> + void SetPosition(const T& new_center) { + Offset(new_center - center); + } +}; + +inline std::ostream& operator<<(std::ostream& out, const Marker& marker) { + out << "{" + << marker.clip << ", " + << marker.frame << ", " + << marker.track << ", (" + << marker.center.x() << ", " + << marker.center.y() << ")" + << "}"; + return out; +} + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_MARKER_H_ diff --git a/extern/libmv/libmv/autotrack/model.h b/extern/libmv/libmv/autotrack/model.h new file mode 100644 index 00000000000..1165281cdac --- /dev/null +++ b/extern/libmv/libmv/autotrack/model.h @@ -0,0 +1,44 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_MODEL_H_ +#define LIBMV_AUTOTRACK_MODEL_H_ + +#include "libmv/numeric/numeric.h" +#include "libmv/autotrack/quad.h" + +namespace mv { + +struct Model { + enum ModelType { + POINT, + PLANE, + LINE, + CUBE + }; + + // ??? +}; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_MODEL_H_ diff --git a/extern/libmv/libmv/autotrack/predict_tracks.cc b/extern/libmv/libmv/autotrack/predict_tracks.cc new file mode 100644 index 00000000000..adc986a0033 --- /dev/null +++ b/extern/libmv/libmv/autotrack/predict_tracks.cc @@ -0,0 +1,316 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#include "libmv/autotrack/marker.h" +#include "libmv/autotrack/predict_tracks.h" +#include "libmv/autotrack/tracks.h" +#include "libmv/base/vector.h" +#include "libmv/logging/logging.h" +#include "libmv/tracking/kalman_filter.h" + +namespace mv { + +namespace { + +using libmv::vector; +using libmv::Vec2; + +// Implied time delta between steps. Set empirically by tweaking and seeing +// what numbers did best at prediction. +const double dt = 3.8; + +// State transition matrix. + +// The states for predicting a track are as follows: +// +// 0 - X position +// 1 - X velocity +// 2 - X acceleration +// 3 - Y position +// 4 - Y velocity +// 5 - Y acceleration +// +// Note that in the velocity-only state transition matrix, the acceleration +// component is ignored; so technically the system could be modelled with only +// 4 states instead of 6. For ease of implementation, this keeps order 6. + +// Choose one or the other model from below (velocity or acceleration). + +// For a typical system having constant velocity. This gives smooth-appearing +// predictions, but they are not always as accurate. +const double velocity_state_transition_data[] = { + 1, dt, 0, 0, 0, 0, + 0, 1, 0, 0, 0, 0, + 0, 0, 1, 0, 0, 0, + 0, 0, 0, 1, dt, 0, + 0, 0, 0, 0, 1, 0, + 0, 0, 0, 0, 0, 1 +}; + +// This 3rd-order system also models acceleration. This makes for "jerky" +// predictions, but that tend to be more accurate. +const double acceleration_state_transition_data[] = { + 1, dt, dt*dt/2, 0, 0, 0, + 0, 1, dt, 0, 0, 0, + 0, 0, 1, 0, 0, 0, + 0, 0, 0, 1, dt, dt*dt/2, + 0, 0, 0, 0, 1, dt, + 0, 0, 0, 0, 0, 1 +}; + +// This system (attempts) to add an angular velocity component. However, it's +// total junk. +const double angular_state_transition_data[] = { + 1, dt, -dt, 0, 0, 0, // Position x + 0, 1, 0, 0, 0, 0, // Velocity x + 0, 0, 1, 0, 0, 0, // Angular momentum + 0, 0, dt, 1, dt, 0, // Position y + 0, 0, 0, 0, 1, 0, // Velocity y + 0, 0, 0, 0, 0, 1 // Ignored +}; + +const double* state_transition_data = velocity_state_transition_data; + +// Observation matrix. +const double observation_data[] = { + 1., 0., 0., 0., 0., 0., + 0., 0., 0., 1., 0., 0. +}; + +// Process covariance. +const double process_covariance_data[] = { + 35, 0, 0, 0, 0, 0, + 0, 5, 0, 0, 0, 0, + 0, 0, 5, 0, 0, 0, + 0, 0, 0, 35, 0, 0, + 0, 0, 0, 0, 5, 0, + 0, 0, 0, 0, 0, 5 +}; + +// Process covariance. +const double measurement_covariance_data[] = { + 0.01, 0.00, + 0.00, 0.01, +}; + +// Initial covariance. +const double initial_covariance_data[] = { + 10, 0, 0, 0, 0, 0, + 0, 1, 0, 0, 0, 0, + 0, 0, 1, 0, 0, 0, + 0, 0, 0, 10, 0, 0, + 0, 0, 0, 0, 1, 0, + 0, 0, 0, 0, 0, 1 +}; + +typedef mv::KalmanFilter<double, 6, 2> TrackerKalman; + +TrackerKalman filter(state_transition_data, + observation_data, + process_covariance_data, + measurement_covariance_data); + +bool OrderByFrameLessThan(const Marker* a, const Marker* b) { + if (a->frame == b->frame) { + if (a->clip == b->clip) { + return a->track < b->track; + } + return a->clip < b->clip; + } + return a->frame < b-> frame; +} + +// Predicted must be after the previous markers (in the frame numbering sense). +void RunPrediction(const vector<Marker*> previous_markers, + Marker* predicted_marker) { + TrackerKalman::State state; + state.mean << previous_markers[0]->center.x(), 0, 0, + previous_markers[0]->center.y(), 0, 0; + state.covariance = Eigen::Matrix<double, 6, 6, Eigen::RowMajor>( + initial_covariance_data); + + int current_frame = previous_markers[0]->frame; + int target_frame = predicted_marker->frame; + + bool predict_forward = current_frame < target_frame; + int frame_delta = predict_forward ? 1 : -1; + + for (int i = 1; i < previous_markers.size(); ++i) { + // Step forward predicting the state until it is on the current marker. + int predictions = 0; + for (; + current_frame != previous_markers[i]->frame; + current_frame += frame_delta) { + filter.Step(&state); + predictions++; + LG << "Predicted point (frame " << current_frame << "): " + << state.mean(0) << ", " << state.mean(3); + } + // Log the error -- not actually used, but interesting. + Vec2 error = previous_markers[i]->center.cast<double>() - + Vec2(state.mean(0), state.mean(3)); + LG << "Prediction error for " << predictions << " steps: (" + << error.x() << ", " << error.y() << "); norm: " << error.norm(); + // Now that the state is predicted in the current frame, update the state + // based on the measurement from the current frame. + filter.Update(previous_markers[i]->center.cast<double>(), + Eigen::Matrix<double, 2, 2, Eigen::RowMajor>( + measurement_covariance_data), + &state); + LG << "Updated point: " << state.mean(0) << ", " << state.mean(3); + } + // At this point as all the prediction that's possible is done. Finally + // predict until the target frame. + for (; current_frame != target_frame; current_frame += frame_delta) { + filter.Step(&state); + LG << "Final predicted point (frame " << current_frame << "): " + << state.mean(0) << ", " << state.mean(3); + } + + // The x and y positions are at 0 and 3; ignore acceleration and velocity. + predicted_marker->center.x() = state.mean(0); + predicted_marker->center.y() = state.mean(3); + + // Take the patch from the last marker then shift it to match the prediction. + const Marker& last_marker = *previous_markers[previous_markers.size() - 1]; + predicted_marker->patch = last_marker.patch; + Vec2f delta = predicted_marker->center - last_marker.center; + for (int i = 0; i < 4; ++i) { + predicted_marker->patch.coordinates.row(i) += delta; + } + + // Alter the search area as well so it always corresponds to the center. + predicted_marker->search_region = last_marker.search_region; + predicted_marker->search_region.Offset(delta); +} + +} // namespace + +bool PredictMarkerPosition(const Tracks& tracks, Marker* marker) { + // Get all markers for this clip and track. + vector<Marker> markers; + tracks.GetMarkersForTrackInClip(marker->clip, marker->track, &markers); + + if (markers.empty()) { + LG << "No markers to predict from for " << *marker; + return false; + } + + // Order the markers by frame within the clip. + vector<Marker*> boxed_markers(markers.size()); + for (int i = 0; i < markers.size(); ++i) { + boxed_markers[i] = &markers[i]; + } + std::sort(boxed_markers.begin(), boxed_markers.end(), OrderByFrameLessThan); + + // Find the insertion point for this marker among the returned ones. + int insert_at = -1; // If we find the exact frame + int insert_before = -1; // Otherwise... + for (int i = 0; i < boxed_markers.size(); ++i) { + if (boxed_markers[i]->frame == marker->frame) { + insert_at = i; + break; + } + if (boxed_markers[i]->frame > marker->frame) { + insert_before = i; + break; + } + } + + // Forward starts at the marker or insertion point, and goes forward. + int forward_scan_begin, forward_scan_end; + + // Backward scan starts at the marker or insertion point, and goes backward. + int backward_scan_begin, backward_scan_end; + + // Determine the scanning ranges. + if (insert_at == -1 && insert_before == -1) { + // Didn't find an insertion point except the end. + forward_scan_begin = forward_scan_end = 0; + backward_scan_begin = markers.size() - 1; + backward_scan_end = 0; + } else if (insert_at != -1) { + // Found existing marker; scan before and after it. + forward_scan_begin = insert_at + 1; + forward_scan_end = markers.size() - 1;; + backward_scan_begin = insert_at - 1; + backward_scan_end = 0; + } else { + // Didn't find existing marker but found an insertion point. + forward_scan_begin = insert_before; + forward_scan_end = markers.size() - 1;; + backward_scan_begin = insert_before - 1; + backward_scan_end = 0; + } + + const int num_consecutive_needed = 2; + + if (forward_scan_begin <= forward_scan_end && + forward_scan_end - forward_scan_begin > num_consecutive_needed) { + // TODO(keir): Finish this. + } + + bool predict_forward = false; + if (backward_scan_end <= backward_scan_begin) { + // TODO(keir): Add smarter handling and detecting of consecutive frames! + predict_forward = true; + } + + const int max_frames_to_predict_from = 20; + if (predict_forward) { + if (backward_scan_begin - backward_scan_end < num_consecutive_needed) { + // Not enough information to do a prediction. + LG << "Predicting forward impossible, not enough information"; + return false; + } + LG << "Predicting forward"; + int predict_begin = + std::max(backward_scan_begin - max_frames_to_predict_from, 0); + int predict_end = backward_scan_begin; + vector<Marker*> previous_markers; + for (int i = predict_begin; i <= predict_end; ++i) { + previous_markers.push_back(boxed_markers[i]); + } + RunPrediction(previous_markers, marker); + return true; + } else { + if (forward_scan_end - forward_scan_begin < num_consecutive_needed) { + // Not enough information to do a prediction. + LG << "Predicting backward impossible, not enough information"; + return false; + } + LG << "Predicting backward"; + int predict_begin = + std::min(forward_scan_begin + max_frames_to_predict_from, + forward_scan_end); + int predict_end = forward_scan_begin; + vector<Marker*> previous_markers; + for (int i = predict_begin; i >= predict_end; --i) { + previous_markers.push_back(boxed_markers[i]); + } + RunPrediction(previous_markers, marker); + return false; + } + +} + +} // namespace mv diff --git a/extern/libmv/libmv/autotrack/predict_tracks.h b/extern/libmv/libmv/autotrack/predict_tracks.h new file mode 100644 index 00000000000..9ff13ad2125 --- /dev/null +++ b/extern/libmv/libmv/autotrack/predict_tracks.h @@ -0,0 +1,37 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_PREDICT_TRACKS_H_ +#define LIBMV_AUTOTRACK_PREDICT_TRACKS_H_ + +namespace mv { + +class Tracks; +class Marker; + +// Predict the position of the given marker, and update it accordingly. The +// existing position will be overwritten. +bool PredictMarkerPosition(const Tracks& tracks, Marker* marker); + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_PREDICT_TRACKS_H_ diff --git a/extern/libmv/libmv/autotrack/predict_tracks_test.cc b/extern/libmv/libmv/autotrack/predict_tracks_test.cc new file mode 100644 index 00000000000..fc90e260d94 --- /dev/null +++ b/extern/libmv/libmv/autotrack/predict_tracks_test.cc @@ -0,0 +1,201 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#include "libmv/autotrack/predict_tracks.h" + +#include "libmv/autotrack/marker.h" +#include "libmv/autotrack/tracks.h" +#include "libmv/logging/logging.h" +#include "testing/testing.h" + +namespace mv { + +void AddMarker(int frame, float x, float y, Tracks* tracks) { + Marker marker; + marker.clip = marker.track = 0; + marker.frame = frame; + marker.center.x() = x; + marker.center.y() = y; + marker.patch.coordinates << x - 1, y - 1, + x + 1, y - 1, + x + 1, y + 1, + x - 1, y + 1; + tracks->AddMarker(marker); +} + +TEST(PredictMarkerPosition, EasyLinearMotion) { + Tracks tracks; + AddMarker(0, 1.0, 0.0, &tracks); + AddMarker(1, 2.0, 5.0, &tracks); + AddMarker(2, 3.0, 10.0, &tracks); + AddMarker(3, 4.0, 15.0, &tracks); + AddMarker(4, 5.0, 20.0, &tracks); + AddMarker(5, 6.0, 25.0, &tracks); + AddMarker(6, 7.0, 30.0, &tracks); + AddMarker(7, 8.0, 35.0, &tracks); + + Marker predicted; + predicted.clip = 0; + predicted.track = 0; + predicted.frame = 8; + + PredictMarkerPosition(tracks, &predicted); + double error = (libmv::Vec2f(9.0, 40.0) - predicted.center).norm(); + LG << "Got error: " << error; + EXPECT_LT(error, 0.1); + + // Check the patch coordinates as well. + double x = 9, y = 40.0; + Quad2Df expected_patch; + expected_patch.coordinates << x - 1, y - 1, + x + 1, y - 1, + x + 1, y + 1, + x - 1, y + 1; + + error = (expected_patch.coordinates - predicted.patch.coordinates).norm(); + LG << "Patch error: " << error; + EXPECT_LT(error, 0.1); +} + +TEST(PredictMarkerPosition, EasyBackwardLinearMotion) { + Tracks tracks; + AddMarker(8, 1.0, 0.0, &tracks); + AddMarker(7, 2.0, 5.0, &tracks); + AddMarker(6, 3.0, 10.0, &tracks); + AddMarker(5, 4.0, 15.0, &tracks); + AddMarker(4, 5.0, 20.0, &tracks); + AddMarker(3, 6.0, 25.0, &tracks); + AddMarker(2, 7.0, 30.0, &tracks); + AddMarker(1, 8.0, 35.0, &tracks); + + Marker predicted; + predicted.clip = 0; + predicted.track = 0; + predicted.frame = 0; + + PredictMarkerPosition(tracks, &predicted); + LG << predicted; + double error = (libmv::Vec2f(9.0, 40.0) - predicted.center).norm(); + LG << "Got error: " << error; + EXPECT_LT(error, 0.1); + + // Check the patch coordinates as well. + double x = 9.0, y = 40.0; + Quad2Df expected_patch; + expected_patch.coordinates << x - 1, y - 1, + x + 1, y - 1, + x + 1, y + 1, + x - 1, y + 1; + + error = (expected_patch.coordinates - predicted.patch.coordinates).norm(); + LG << "Patch error: " << error; + EXPECT_LT(error, 0.1); +} + +TEST(PredictMarkerPosition, TwoFrameGap) { + Tracks tracks; + AddMarker(0, 1.0, 0.0, &tracks); + AddMarker(1, 2.0, 5.0, &tracks); + AddMarker(2, 3.0, 10.0, &tracks); + AddMarker(3, 4.0, 15.0, &tracks); + AddMarker(4, 5.0, 20.0, &tracks); + AddMarker(5, 6.0, 25.0, &tracks); + AddMarker(6, 7.0, 30.0, &tracks); + // Missing frame 7! + + Marker predicted; + predicted.clip = 0; + predicted.track = 0; + predicted.frame = 8; + + PredictMarkerPosition(tracks, &predicted); + double error = (libmv::Vec2f(9.0, 40.0) - predicted.center).norm(); + LG << "Got error: " << error; + EXPECT_LT(error, 0.1); +} + +TEST(PredictMarkerPosition, FourFrameGap) { + Tracks tracks; + AddMarker(0, 1.0, 0.0, &tracks); + AddMarker(1, 2.0, 5.0, &tracks); + AddMarker(2, 3.0, 10.0, &tracks); + AddMarker(3, 4.0, 15.0, &tracks); + // Missing frames 4, 5, 6, 7. + + Marker predicted; + predicted.clip = 0; + predicted.track = 0; + predicted.frame = 8; + + PredictMarkerPosition(tracks, &predicted); + double error = (libmv::Vec2f(9.0, 40.0) - predicted.center).norm(); + LG << "Got error: " << error; + EXPECT_LT(error, 2.0); // Generous error due to larger prediction window. +} + +TEST(PredictMarkerPosition, MultipleGaps) { + Tracks tracks; + AddMarker(0, 1.0, 0.0, &tracks); + AddMarker(1, 2.0, 5.0, &tracks); + AddMarker(2, 3.0, 10.0, &tracks); + // AddMarker(3, 4.0, 15.0, &tracks); // Note the 3-frame gap. + // AddMarker(4, 5.0, 20.0, &tracks); + // AddMarker(5, 6.0, 25.0, &tracks); + AddMarker(6, 7.0, 30.0, &tracks); // Intermediate measurement. + // AddMarker(7, 8.0, 35.0, &tracks); + + Marker predicted; + predicted.clip = 0; + predicted.track = 0; + predicted.frame = 8; + + PredictMarkerPosition(tracks, &predicted); + double error = (libmv::Vec2f(9.0, 40.0) - predicted.center).norm(); + LG << "Got error: " << error; + EXPECT_LT(error, 1.0); // Generous error due to larger prediction window. +} + +TEST(PredictMarkerPosition, MarkersInRandomOrder) { + Tracks tracks; + + // This is the same as the easy, except that the tracks are randomly ordered. + AddMarker(0, 1.0, 0.0, &tracks); + AddMarker(2, 3.0, 10.0, &tracks); + AddMarker(7, 8.0, 35.0, &tracks); + AddMarker(5, 6.0, 25.0, &tracks); + AddMarker(4, 5.0, 20.0, &tracks); + AddMarker(3, 4.0, 15.0, &tracks); + AddMarker(6, 7.0, 30.0, &tracks); + AddMarker(1, 2.0, 5.0, &tracks); + + Marker predicted; + predicted.clip = 0; + predicted.track = 0; + predicted.frame = 8; + + PredictMarkerPosition(tracks, &predicted); + double error = (libmv::Vec2f(9.0, 40.0) - predicted.center).norm(); + LG << "Got error: " << error; + EXPECT_LT(error, 0.1); +} + +} // namespace mv diff --git a/extern/libmv/libmv/autotrack/quad.h b/extern/libmv/libmv/autotrack/quad.h new file mode 100644 index 00000000000..0c70f9882da --- /dev/null +++ b/extern/libmv/libmv/autotrack/quad.h @@ -0,0 +1,57 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_QUAD_H_ +#define LIBMV_AUTOTRACK_QUAD_H_ + +#include <Eigen/Core> + +namespace mv { + +template<typename T, int D> +struct Quad { + // A quad is 4 points; generally in 2D or 3D. + // + // +----------> x + // |\. + // | \. + // | z (z goes into screen) + // | + // | r0----->r1 + // | ^ | + // | | . | + // | | V + // | r3<-----r2 + // | \. + // | \. + // v normal goes away (right handed). + // y + // + // Each row is one of the corners coordinates; either (x, y) or (x, y, z). + Eigen::Matrix<T, 4, D> coordinates; +}; + +typedef Quad<float, 2> Quad2Df; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_QUAD_H_ diff --git a/extern/libmv/libmv/autotrack/reconstruction.h b/extern/libmv/libmv/autotrack/reconstruction.h new file mode 100644 index 00000000000..e1d4e882cbd --- /dev/null +++ b/extern/libmv/libmv/autotrack/reconstruction.h @@ -0,0 +1,89 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_RECONSTRUCTION_H_ +#define LIBMV_AUTOTRACK_RECONSTRUCTION_H_ + +#include "libmv/base/vector.h" +#include "libmv/numeric/numeric.h" +#include "libmv/simple_pipeline/camera_intrinsics.h" + +namespace mv { + +using libmv::CameraIntrinsics; +using libmv::vector; + +class Model; + +class CameraPose { + int clip; + int frame; + int intrinsics; + Mat3 R; + Vec3 t; +}; + +class Point { + int track; + + // The coordinates of the point. Note that not all coordinates are always + // used; for example points on a plane only use the first two coordinates. + Vec3 X; +}; + +// A reconstruction for a set of tracks. The indexing for clip, frame, and +// track should match that of a Tracs object, stored elsewhere. +class Reconstruction { + public: + // All methods copy their input reference or take ownership of the pointer. + void AddCameraPose(const CameraPose& pose); + int AddCameraIntrinsics(CameraIntrinsics* intrinsics); + int AddPoint(const Point& point); + int AddModel(Model* model); + + // Returns the corresponding pose or point or NULL if missing. + CameraPose* CameraPoseForFrame(int clip, int frame); + const CameraPose* CameraPoseForFrame(int clip, int frame) const; + Point* PointForTrack(int track); + const Point* PointForTrack(int track) const; + + const vector<vector<CameraPose> >& camera_poses() const { + return camera_poses_; + } + + private: + // Indexed by CameraPose::intrinsics. Owns the intrinsics objects. + vector<CameraIntrinsics*> camera_intrinsics_; + + // Indexed by Marker::clip then by Marker::frame. + vector<vector<CameraPose> > camera_poses_; + + // Indexed by Marker::track. + vector<Point> points_; + + // Indexed by Marker::model_id. Owns model objects. + vector<Model*> models_; +}; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_RECONSTRUCTION_H_ diff --git a/extern/libmv/libmv/autotrack/region.h b/extern/libmv/libmv/autotrack/region.h new file mode 100644 index 00000000000..b35d99eb60d --- /dev/null +++ b/extern/libmv/libmv/autotrack/region.h @@ -0,0 +1,67 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_REGION_H_ +#define LIBMV_AUTOTRACK_REGION_H_ + +#include "libmv/numeric/numeric.h" + +namespace mv { + +using libmv::Vec2f; + +// A region is a bounding box within an image. +// +// +----------> x +// | +// | (min.x, min.y) (max.x, min.y) +// | +-------------------------+ +// | | | +// | | | +// | | | +// | +-------------------------+ +// v (min.x, max.y) (max.x, max.y) +// y +// +struct Region { + Vec2f min; + Vec2f max; + + template<typename T> + void Offset(const T& offset) { + min += offset.template cast<float>(); + max += offset.template cast<float>(); + } + + Region Rounded() const { + Region result; + result.min(0) = ceil(this->min(0)); + result.min(1) = ceil(this->min(1)); + result.max(0) = ceil(this->max(0)); + result.max(1) = ceil(this->max(1)); + return result; + } +}; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_REGION_H_ diff --git a/extern/libmv/libmv/autotrack/tracks.cc b/extern/libmv/libmv/autotrack/tracks.cc new file mode 100644 index 00000000000..174f264f3f2 --- /dev/null +++ b/extern/libmv/libmv/autotrack/tracks.cc @@ -0,0 +1,193 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#include "libmv/autotrack/tracks.h" + +#include <algorithm> +#include <vector> +#include <iterator> + +#include "libmv/numeric/numeric.h" + +namespace mv { + +Tracks::Tracks(const Tracks& other) { + markers_ = other.markers_; +} + +Tracks::Tracks(const vector<Marker>& markers) : markers_(markers) {} + +bool Tracks::GetMarker(int clip, int frame, int track, Marker* marker) const { + for (int i = 0; i < markers_.size(); ++i) { + if (markers_[i].clip == clip && + markers_[i].frame == frame && + markers_[i].track == track) { + *marker = markers_[i]; + return true; + } + } + return false; +} + +void Tracks::GetMarkersForTrack(int track, vector<Marker>* markers) const { + for (int i = 0; i < markers_.size(); ++i) { + if (track == markers_[i].track) { + markers->push_back(markers_[i]); + } + } +} + +void Tracks::GetMarkersForTrackInClip(int clip, + int track, + vector<Marker>* markers) const { + for (int i = 0; i < markers_.size(); ++i) { + if (clip == markers_[i].clip && + track == markers_[i].track) { + markers->push_back(markers_[i]); + } + } +} + +void Tracks::GetMarkersInFrame(int clip, + int frame, + vector<Marker>* markers) const { + for (int i = 0; i < markers_.size(); ++i) { + if (markers_[i].clip == clip && + markers_[i].frame == frame) { + markers->push_back(markers_[i]); + } + } +} + +void Tracks::GetMarkersForTracksInBothImages(int clip1, int frame1, + int clip2, int frame2, + vector<Marker>* markers) const { + std::vector<int> image1_tracks; + std::vector<int> image2_tracks; + + // Collect the tracks in each of the two images. + for (int i = 0; i < markers_.size(); ++i) { + int clip = markers_[i].clip; + int frame = markers_[i].frame; + if (clip == clip1 && frame == frame1) { + image1_tracks.push_back(markers_[i].track); + } else if (clip == clip2 && frame == frame2) { + image2_tracks.push_back(markers_[i].track); + } + } + + // Intersect the two sets to find the tracks of interest. + std::sort(image1_tracks.begin(), image1_tracks.end()); + std::sort(image2_tracks.begin(), image2_tracks.end()); + std::vector<int> intersection; + std::set_intersection(image1_tracks.begin(), image1_tracks.end(), + image2_tracks.begin(), image2_tracks.end(), + std::back_inserter(intersection)); + + // Scan through and get the relevant tracks from the two images. + for (int i = 0; i < markers_.size(); ++i) { + // Save markers that are in either frame and are in our candidate set. + if (((markers_[i].clip == clip1 && + markers_[i].frame == frame1) || + (markers_[i].clip == clip2 && + markers_[i].frame == frame2)) && + std::binary_search(intersection.begin(), + intersection.end(), + markers_[i].track)) { + markers->push_back(markers_[i]); + } + } +} + +void Tracks::AddMarker(const Marker& marker) { + // TODO(keir): This is quadratic for repeated insertions. Fix this by adding + // a smarter data structure like a set<>. + for (int i = 0; i < markers_.size(); ++i) { + if (markers_[i].clip == marker.clip && + markers_[i].frame == marker.frame && + markers_[i].track == marker.track) { + markers_[i] = marker; + return; + } + } + markers_.push_back(marker); +} + +void Tracks::SetMarkers(vector<Marker>* markers) { + std::swap(markers_, *markers); +} + +bool Tracks::RemoveMarker(int clip, int frame, int track) { + int size = markers_.size(); + for (int i = 0; i < markers_.size(); ++i) { + if (markers_[i].clip == clip && + markers_[i].frame == frame && + markers_[i].track == track) { + markers_[i] = markers_[size - 1]; + markers_.resize(size - 1); + return true; + } + } + return false; +} + +void Tracks::RemoveMarkersForTrack(int track) { + int size = 0; + for (int i = 0; i < markers_.size(); ++i) { + if (markers_[i].track != track) { + markers_[size++] = markers_[i]; + } + } + markers_.resize(size); +} + +int Tracks::MaxClip() const { + int max_clip = 0; + for (int i = 0; i < markers_.size(); ++i) { + max_clip = std::max(markers_[i].clip, max_clip); + } + return max_clip; +} + +int Tracks::MaxFrame(int clip) const { + int max_frame = 0; + for (int i = 0; i < markers_.size(); ++i) { + if (markers_[i].clip == clip) { + max_frame = std::max(markers_[i].frame, max_frame); + } + } + return max_frame; +} + +int Tracks::MaxTrack() const { + int max_track = 0; + for (int i = 0; i < markers_.size(); ++i) { + max_track = std::max(markers_[i].track, max_track); + } + return max_track; +} + +int Tracks::NumMarkers() const { + return markers_.size(); +} + +} // namespace mv diff --git a/extern/libmv/libmv/autotrack/tracks.h b/extern/libmv/libmv/autotrack/tracks.h new file mode 100644 index 00000000000..0b7de91d211 --- /dev/null +++ b/extern/libmv/libmv/autotrack/tracks.h @@ -0,0 +1,82 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#ifndef LIBMV_AUTOTRACK_TRACKS_H_ +#define LIBMV_AUTOTRACK_TRACKS_H_ + +#include "libmv/base/vector.h" +#include "libmv/autotrack/marker.h" + +namespace mv { + +using libmv::vector; + +// The Tracks container stores correspondences between frames. +class Tracks { + public: + Tracks() { } + Tracks(const Tracks &other); + + // Create a tracks object with markers already initialized. Copies markers. + explicit Tracks(const vector<Marker>& markers); + + // All getters append to the output argument vector. + bool GetMarker(int clip, int frame, int track, Marker* marker) const; + void GetMarkersForTrack(int track, vector<Marker>* markers) const; + void GetMarkersForTrackInClip(int clip, + int track, + vector<Marker>* markers) const; + void GetMarkersInFrame(int clip, int frame, vector<Marker>* markers) const; + + // Get the markers in frame1 and frame2 which have a common track. + // + // This is not the same as the union of the markers in frame1 and + // frame2; each marker is for a track that appears in both images. + void GetMarkersForTracksInBothImages(int clip1, int frame1, + int clip2, int frame2, + vector<Marker>* markers) const; + + void AddMarker(const Marker& marker); + + // Moves the contents of *markers over top of the existing markers. This + // destroys *markers in the process (but avoids copies). + void SetMarkers(vector<Marker>* markers); + bool RemoveMarker(int clip, int frame, int track); + void RemoveMarkersForTrack(int track); + + int MaxClip() const; + int MaxFrame(int clip) const; + int MaxTrack() const; + int NumMarkers() const; + + const vector<Marker>& markers() const { return markers_; } + + private: + vector<Marker> markers_; + + // TODO(keir): Consider adding access-map data structures to avoid all the + // linear lookup penalties for the accessors. +}; + +} // namespace mv + +#endif // LIBMV_AUTOTRACK_TRACKS_H_ diff --git a/extern/libmv/libmv/autotrack/tracks_test.cc b/extern/libmv/libmv/autotrack/tracks_test.cc new file mode 100644 index 00000000000..028b4a10913 --- /dev/null +++ b/extern/libmv/libmv/autotrack/tracks_test.cc @@ -0,0 +1,52 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. +// +// Author: mierle@gmail.com (Keir Mierle) + +#include "libmv/autotrack/tracks.h" + +#include "testing/testing.h" +#include "libmv/logging/logging.h" + +namespace mv { + +TEST(Tracks, MaxFrame) { + Marker marker; + Tracks tracks; + + // Add some markers to clip 0. + marker.clip = 0; + marker.frame = 1; + tracks.AddMarker(marker); + + // Add some markers to clip 1. + marker.clip = 1; + marker.frame = 1; + tracks.AddMarker(marker); + + marker.clip = 1; + marker.frame = 12; + tracks.AddMarker(marker); + + EXPECT_EQ(1, tracks.MaxFrame(0)); + EXPECT_EQ(12, tracks.MaxFrame(1)); +} + +} // namespace mv diff --git a/extern/libmv/libmv/base/vector.h b/extern/libmv/libmv/base/vector.h index 067db4ba7f7..1931fb0b1f9 100644 --- a/extern/libmv/libmv/base/vector.h +++ b/extern/libmv/libmv/base/vector.h @@ -101,8 +101,6 @@ class vector { size_ = size; } - - void push_back(const T &value) { if (size_ == capacity_) { reserve(size_ ? 2 * size_ : 1); @@ -130,6 +128,10 @@ class vector { } } + bool empty() { + return size_ == 0; + } + private: void construct(int start, int end) { for (int i = start; i < end; ++i) { diff --git a/extern/libmv/libmv/image/array_nd.h b/extern/libmv/libmv/image/array_nd.h index c5099f24d7b..b56a765223b 100644 --- a/extern/libmv/libmv/image/array_nd.h +++ b/extern/libmv/libmv/image/array_nd.h @@ -41,33 +41,35 @@ class ArrayND : public BaseArray { typedef Tuple<int, N> Index; /// Create an empty array. - ArrayND() : data_(NULL), own_data(true) { Resize(Index(0)); } + ArrayND() : data_(NULL), own_data_(true) { Resize(Index(0)); } /// Create an array with the specified shape. - ArrayND(const Index &shape) : data_(NULL), own_data(true) { Resize(shape); } + ArrayND(const Index &shape) : data_(NULL), own_data_(true) { Resize(shape); } /// Create an array with the specified shape. - ArrayND(int *shape) : data_(NULL), own_data(true) { Resize(shape); } + ArrayND(int *shape) : data_(NULL), own_data_(true) { Resize(shape); } /// Copy constructor. - ArrayND(const ArrayND<T, N> &b) : data_(NULL), own_data(true) { + ArrayND(const ArrayND<T, N> &b) : data_(NULL), own_data_(true) { ResizeLike(b); std::memcpy(Data(), b.Data(), sizeof(T) * Size()); } - ArrayND(int s0) : data_(NULL), own_data(true) { Resize(s0); } - ArrayND(int s0, int s1) : data_(NULL), own_data(true) { Resize(s0, s1); } - ArrayND(int s0, int s1, int s2) : data_(NULL), own_data(true) { + ArrayND(int s0) : data_(NULL), own_data_(true) { Resize(s0); } + ArrayND(int s0, int s1) : data_(NULL), own_data_(true) { Resize(s0, s1); } + ArrayND(int s0, int s1, int s2) : data_(NULL), own_data_(true) { Resize(s0, s1, s2); } - ArrayND(T* data, int s0, int s1, int s2) : data_(data), own_data(false) { + ArrayND(T* data, int s0, int s1, int s2) : data_(data), own_data_(false) { Resize(s0, s1, s2); } /// Destructor deletes pixel data. ~ArrayND() { - delete [] data_; + if (own_data_) { + delete [] data_; + } } /// Assignation copies pixel data. @@ -97,7 +99,7 @@ class ArrayND : public BaseArray { for (int i = N - 1; i > 0; --i) { strides_(i - 1) = strides_(i) * shape_(i); } - if (own_data) { + if (own_data_) { delete [] data_; data_ = NULL; if (Size() > 0) { @@ -336,7 +338,7 @@ class ArrayND : public BaseArray { T *data_; /// Flag if this Array either own or reference the data - bool own_data; + bool own_data_; }; /// 3D array (row, column, channel). diff --git a/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc b/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc index 7b90c28bbca..241b5600505 100644 --- a/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc +++ b/extern/libmv/libmv/simple_pipeline/keyframe_selection.cc @@ -69,54 +69,50 @@ double GRIC(const Vec &e, int d, int k, int r) { // http://www.robots.ox.ac.uk/~vgg/publications/papers/torr99.ps.gz double lambda3 = 2.0; - // measurement error of tracker + // Variance of tracker position. Physically, this is typically about 0.1px, + // and when squared becomes 0.01 px^2. double sigma2 = 0.01; - // Actual GRIC computation - double gric_result = 0.0; - + // Finally, calculate the GRIC score. + double gric = 0.0; for (int i = 0; i < n; i++) { - double rho = std::min(e(i) * e(i) / sigma2, lambda3 * (r - d)); - gric_result += rho; + gric += std::min(e(i) * e(i) / sigma2, lambda3 * (r - d)); } - - gric_result += lambda1 * d * n; - gric_result += lambda2 * k; - - return gric_result; + gric += lambda1 * d * n; + gric += lambda2 * k; + return gric; } -// Compute a generalized inverse using eigen value decomposition. -// It'll actually also zero 7 last eigen values to deal with -// gauges, since this function is used to compute variance of +// Compute a generalized inverse using eigen value decomposition, clamping the +// smallest eigenvalues if requested. This is needed to compute the variance of // reconstructed 3D points. // -// TODO(sergey): Could be generalized by making it so number -// of values to be zeroed is passed by an argument -// and moved to numeric module. -Mat pseudoInverse(const Mat &matrix) { - Eigen::EigenSolver<Mat> eigenSolver(matrix); - Mat D = eigenSolver.pseudoEigenvalueMatrix(); - Mat V = eigenSolver.pseudoEigenvectors(); - +// TODO(keir): Consider moving this into the numeric code, since this is not +// related to keyframe selection. +Mat PseudoInverseWithClampedEigenvalues(const Mat &matrix, + int num_eigenvalues_to_clamp) { + Eigen::EigenSolver<Mat> eigen_solver(matrix); + Mat D = eigen_solver.pseudoEigenvalueMatrix(); + Mat V = eigen_solver.pseudoEigenvectors(); + + // Clamp too-small singular values to zero to prevent numeric blowup. double epsilon = std::numeric_limits<double>::epsilon(); - for (int i = 0; i < D.cols(); ++i) { - if (D(i, i) > epsilon) + if (D(i, i) > epsilon) { D(i, i) = 1.0 / D(i, i); - else + } else { D(i, i) = 0.0; + } } - // Zero last 7 (which corresponds to smallest eigen values). - // 7 equals to the number of gauge freedoms. - for (int i = D.cols() - 7; i < D.cols(); ++i) + // Apply the clamp. + for (int i = D.cols() - num_eigenvalues_to_clamp; i < D.cols(); ++i) { D(i, i) = 0.0; - + } return V * D * V.inverse(); } -void filterZeroWeightMarkersFromTracks(const Tracks &tracks, +void FilterZeroWeightMarkersFromTracks(const Tracks &tracks, Tracks *filtered_tracks) { vector<Marker> all_markers = tracks.AllMarkers(); @@ -143,7 +139,7 @@ void SelectKeyframesBasedOnGRICAndVariance(const Tracks &_tracks, // http://www.cs.ait.ac.th/~mdailey/papers/Tahir-KeyFrame.pdf Tracks filtered_tracks; - filterZeroWeightMarkersFromTracks(_tracks, &filtered_tracks); + FilterZeroWeightMarkersFromTracks(_tracks, &filtered_tracks); int max_image = filtered_tracks.MaxImage(); int next_keyframe = 1; @@ -224,9 +220,9 @@ void SelectKeyframesBasedOnGRICAndVariance(const Tracks &_tracks, EstimateFundamentalOptions estimate_fundamental_options; EstimateFundamentalFromCorrespondences(x1, - x2, - estimate_fundamental_options, - &F); + x2, + estimate_fundamental_options, + &F); // Convert fundamental to original pixel space. F = N_inverse * F * N; @@ -379,7 +375,8 @@ void SelectKeyframesBasedOnGRICAndVariance(const Tracks &_tracks, Mat &jacobian = evaluation.jacobian; Mat JT_J = jacobian.transpose() * jacobian; - Mat JT_J_inv = pseudoInverse(JT_J); + // There are 7 degrees of freedom, so clamp them out. + Mat JT_J_inv = PseudoInverseWithClampedEigenvalues(JT_J, 7); Mat temp_derived = JT_J * JT_J_inv * JT_J; bool is_inversed = (temp_derived - JT_J).cwiseAbs2().sum() < diff --git a/extern/libmv/libmv/tracking/kalman_filter.h b/extern/libmv/libmv/tracking/kalman_filter.h new file mode 100644 index 00000000000..9841f0e912c --- /dev/null +++ b/extern/libmv/libmv/tracking/kalman_filter.h @@ -0,0 +1,112 @@ +// Copyright (c) 2014 libmv authors. +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. + +#ifndef LIBMV_TRACKING_KALMAN_FILTER_H_ + +#include "libmv/numeric/numeric.h" + +namespace mv { + +// A Kalman filter with order N and observation size K. +template<typename T, int N, int K> +class KalmanFilter { + public: + struct State { + Eigen::Matrix<T, N, 1> mean; + Eigen::Matrix<T, N, N> covariance; + }; + + // Initialize from row-major data; convenient for constant initializers. + KalmanFilter(const T* state_transition_data, + const T* observation_data, + const T* process_covariance_data, + const T* default_measurement_covariance_data) + : state_transition_matrix_( + Eigen::Matrix<T, N, N, Eigen::RowMajor>(state_transition_data)), + observation_matrix_( + Eigen::Matrix<T, K, N, Eigen::RowMajor>(observation_data)), + process_covariance_( + Eigen::Matrix<T, N, N, Eigen::RowMajor>(process_covariance_data)), + default_measurement_covariance_( + Eigen::Matrix<T, K, K, Eigen::RowMajor>( + default_measurement_covariance_data)) { + } + + KalmanFilter( + const Eigen::Matrix<T, N, N> &state_transition_matrix, + const Eigen::Matrix<T, K, N> &observation_matrix, + const Eigen::Matrix<T, N, N> &process_covariance, + const Eigen::Matrix<T, K, K> &default_measurement_covariance) + : state_transition_matrix_(state_transition_matrix), + observation_matrix_(observation_matrix), + process_covariance_(process_covariance), + default_measurement_covariance_(default_measurement_covariance) { + } + + // Advances the system according to the current state estimate. + void Step(State *state) const { + state->mean = state_transition_matrix_ * state->mean; + state->covariance = state_transition_matrix_ * + state->covariance * + state_transition_matrix_.transpose() + + process_covariance_; + } + + // Updates a state with a new measurement. + void Update(const Eigen::Matrix<T, K, 1> &measurement_mean, + const Eigen::Matrix<T, K, K> &measurement_covariance, + State *state) const { + // Calculate the innovation, which is a distribution over prediction error. + Eigen::Matrix<T, K, 1> innovation_mean = measurement_mean - + observation_matrix_ * + state->mean; + Eigen::Matrix<T, K, K> innovation_covariance = + observation_matrix_ * + state->covariance * + observation_matrix_.transpose() + + measurement_covariance; + + // Calculate the Kalman gain. + Eigen::Matrix<T, 6, 2> kalman_gain = state->covariance * + observation_matrix_.transpose() * + innovation_covariance.inverse(); + + // Update the state mean and covariance. + state->mean += kalman_gain * innovation_mean; + state->covariance = (Eigen::Matrix<T, N, N>::Identity() - + kalman_gain * observation_matrix_) * + state->covariance; + } + + void Update(State *state, + const Eigen::Matrix<T, K, 1> &measurement_mean) const { + Update(state, measurement_mean, default_measurement_covariance_); + } + + private: + const Eigen::Matrix<T, N, N> state_transition_matrix_; + const Eigen::Matrix<T, K, N> observation_matrix_; + const Eigen::Matrix<T, N, N> process_covariance_; + const Eigen::Matrix<T, K, K> default_measurement_covariance_; +}; + +} // namespace mv + +#endif // LIBMV_TRACKING_KALMAN_FILTER_H_ diff --git a/extern/libmv/libmv/tracking/track_region.h b/extern/libmv/libmv/tracking/track_region.h index 2ced9dd6550..be1d8ef3e03 100644 --- a/extern/libmv/libmv/tracking/track_region.h +++ b/extern/libmv/libmv/tracking/track_region.h @@ -42,7 +42,13 @@ struct TrackRegionOptions { }; Mode mode; + // Minimum normalized cross-correlation necessary between the final tracked + // positoin of the patch on the destination image and the reference patch + // needed to declare tracking success. If the minimum correlation is not met, + // then TrackResult::termination is INSUFFICIENT_CORRELATION. double minimum_correlation; + + // Maximum number of Ceres iterations to run for the inner minimization. int max_iterations; // Use the "Efficient Second-order Minimization" scheme. This increases @@ -124,6 +130,11 @@ struct TrackRegionResult { }; Termination termination; + bool is_usable() { + return termination == CONVERGENCE || + termination == NO_CONVERGENCE; + } + int num_iterations; double correlation; |