[FFmpeg-devel] Mixture of homographies video stabilization

Matthew Lai matthewlai at google.com
Mon Aug 6 17:49:00 EEST 2018 

Sorry the matrices are actually 3x3, and most of the time will be spent on
solving a 8x9 * 9x1 = 0 systems. And then all the feature points will have
to be multiplied by the 9x1 matrix reshaped into 3x3.

The math is here:
https://www.uio.no/studier/emner/matnat/its/UNIK4690/v16/forelesninger/lecture_4_3-estimating-homographies-from-feature-correspondences.pdf

Multiplying 3x3 matrices is trivial, but SVD isn't. SVD is the standard
approach to decompose a homography matrix. I have not looked into
alternative approaches.

Cool! Will see re. ME. It's likely to be the performance-limiting part, and
it would be nice to run that on GPU.

On Fri, Aug 3, 2018 at 8:27 PM Michael Niedermayer <michael at niedermayer.cc>
wrote:

> On Fri, Aug 03, 2018 at 01:29:27PM +0100, Matthew Lai wrote:
> > Hi Michael,
> >
> > The operations needed are multiplications, SVD, inversion, scaling, and
> > additions, as far as I can tell. Convolutions would probably also be
> > useful. They are certainly possible to implement directly, but it's
> > unlikely that any naive implementation will be within an order of
> magnitude
> > in performance to an optimized BLAS library. That may or may not matter
> - I
> > don't have a good idea of where the performance bottlenecks will be yet.
> > The matrices are 4x4.
>
> How do you intend to organize the data for these 4x4 matrices ?
> i mean if you have a rather large number of them and pass them all
> together to an external lib which then sends them to the GPU to process
> that should be faster than some native implementation (which would be CPU
> based presumably)
> OTOH one matrix at a time i dont see how the use of an external lib would
> make
> any sense.
> matrix addition, subtraction and scaling are just adding or scalin the
> 16 elements. i would expect a naive implementation to beat a external lib
> as long as both do at on the CPU. Because an external lib has to work with
> any NxM sized matrix we would implement this for just 4x4 so its trivial
> to fully unroll the loop or just do 4 load, add, store in SIMD or even
> skip the load/store and keep things in SIMD registers.
> about SVD. do you really need SVD? I mean is that the correct tool here and
> not just slower than alternatives ?
> These 4x4 matrixes are general matrixes or these have some other properties
> like being positive definite of something ?
> I guess i should read the paper, i might do that later ...
>
>
>
>
> >
> > Motion estimation is one way, but most state of the art implementations
> > don't use it because it's too noisy (motion from low contrast regions).
> > Most use something like a corner detector to find sharp feature points,
> and
> > track them (this can potentially be implemented using motion estimation,
> > but only around those points).
>
> Thats what i meant. The area that you want to matchup could use the
> existing
> code or share something with it.
> Other people had previously complained loudly about duplication of ME code.
> And while its not always possible to avoid "duplication", i think this
> should
> be looked into if it can be done in this case.
>
> thx
>
>
> >
> > Matthew
> >
> > On Fri, Aug 3, 2018 at 2:05 AM Michael Niedermayer
> <michael at niedermayer.cc>
> > wrote:
> >
> > > On Thu, Aug 02, 2018 at 05:24:08PM +0100, Matthew Lai wrote:
> > > > Ah ok thanks! I'm surprised no one has need a linear algebra
> library. I
> > > > guess there's OpenCV and people use it to do the heavy lifting?
> > > >
> > > > Will look into the API more.
> > >
> > > alot ot linear algebra we needed has been implemented directly.
> > > Some of it is shared and available from libavutil, like lls.*
> > >
> > > Can you elaboarte what exact linear algebra operations are needed?
> > > also what amounts of data (matrix types/sizes) and speed requirements
> this
> > > has
> > >
> > > Also IIUC (please correct me if iam wrong) this uses motion estimation
> > > at one step. IIRC ronald and others) want motion estimation to be
> > > factored and shared and not duplicated. The current motion estimation
> is
> > > in libavcodec/motion_est*.
> > >
> > > Thanks
> > >
> > > >
> > > > Thanks
> > > > matthew
> > > >
> > > > On Thu, Aug 2, 2018 at 3:31 PM Paul B Mahol <onemda at gmail.com>
> wrote:
> > > >
> > > > > On 8/2/18, Matthew Lai <matthewlai-at-google.com at ffmpeg.org>
> wrote:
> > > > > > Hello!
> > > > > >
> > > > > > I want to write a more advanced video stabilizer for libavfilter
> (*),
> > > > > > implementing the algorithm described here -
> > > > > >
> > > > >
> > >
> https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37744.pdf
> > > > > > The focus of the paper is rolling shutter removal, but it builds
> on
> > > top
> > > > > of
> > > > > > another algorithm that does full frame stabilization, and the new
> > > > > algorithm
> > > > > > does that as well.
> > > > > >
> > > > > > This is the algorithm used in YouTube's stabilizing filter, and
> is
> > > state
> > > > > of
> > > > > > the art. Adobe calls it Warp Stabilizer (it's the same thing as
> far
> > > as I
> > > > > > can tell from public information anyways).
> > > > > >
> > > > > > 3 questions:
> > > > > > 1. Is there a linear algebra library already in use? I didn't see
> > > > > anything
> > > > > > in configure, but would be surprised if none of the existing
> filters
> > > work
> > > > > > with matrices?
> > > > >
> > > > > There is no such library here used. There are indeed video/audio
> > > > > filters that work with matrices.
> > > > >
> > > > > > 2. Is there anything to watch out for re. a high frame delay
> (say a
> > > few
> > > > > > hundred frames)? Looking at the API, I don't see a callback to
> flush
> > > out
> > > > > > remaining frames when input frames are finished? Is doing it in
> two
> > > > > passes
> > > > > > the only option?
> > > > >
> > > > > It is handled internally, there are two internal APIs, activate
> one and
> > > > > legacy.
> > > > > With legacy you can flush frames when you receive last frame from
> > > input.
> > > > > With newer, activate API, its similar.
> > > > >
> > > > > > 3. doc/writing_filters.txt says only slice threading is
> available.
> > > That's
> > > > > > not really possible with this filter, but frame threading is.
> Can I
> > > just
> > > > > > buffer frames internally (which I need to do anyways to smooth
> out
> > > > > motion),
> > > > > > and do my own threading?
> > > > >
> > > > > You could do it.
> > > > >
> > > > > >
> > > > > > * vid.stab is good for what it does, but it only does rotation
> and
> > > > > > translation, and doesn't handle zoom, perspective distortion, or
> > > rolling
> > > > > > shutter. This means it's limited when it comes to things like
> scuba
> > > > > diving
> > > > > > videos, where the camera is filming the seabed at a small
> distance
> > > and at
> > > > > > an angle.
> > > > > >
> > > > > > Thanks!
> > > > > > Matthew
> > > > > > _______________________________________________
> > > > > > ffmpeg-devel mailing list
> > > > > > ffmpeg-devel at ffmpeg.org
> > > > > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> > > > > >
> > > > > _______________________________________________
> > > > > ffmpeg-devel mailing list
> > > > > ffmpeg-devel at ffmpeg.org
> > > > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> > > > >
> > > > _______________________________________________
> > > > ffmpeg-devel mailing list
> > > > ffmpeg-devel at ffmpeg.org
> > > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> > >
> > > --
> > > Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
> > >
> > > It is dangerous to be right in matters on which the established
> authorities
> > > are wrong. -- Voltaire
> > > _______________________________________________
> > > ffmpeg-devel mailing list
> > > ffmpeg-devel at ffmpeg.org
> > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> > >
> > _______________________________________________
> > ffmpeg-devel mailing list
> > ffmpeg-devel at ffmpeg.org
> > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>
> If you fake or manipulate statistics in a paper in physics you will never
> get a job again.
> If you fake or manipulate statistics in a paper in medicin you will get
> a job for life at the pharma industry.
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel at ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>

More information about the ffmpeg-devel mailing list