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 <mich...@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 > <mich...@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 <one...@gmail.com> > wrote: > > > > > > > > > On 8/2/18, Matthew Lai <matthewlai-at-google....@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@ffmpeg.org > > > > > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > > > > > > > > > > > _______________________________________________ > > > > > ffmpeg-devel mailing list > > > > > ffmpeg-devel@ffmpeg.org > > > > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > > > > > > > > > _______________________________________________ > > > > ffmpeg-devel mailing list > > > > ffmpeg-devel@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@ffmpeg.org > > > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > > > > > _______________________________________________ > > ffmpeg-devel mailing list > > ffmpeg-devel@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@ffmpeg.org > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
