Error analysis and condition estimation of the pyramidal form of the Lucas-Kanande method in optical flow 

Error analysis and condition estimation of the pyramidal form of the Lucas-Kanande method in optical flow | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Error analysis and condition estimation of the pyramidal form of the Lucas-Kanande method in optical flow Joab Winkler This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-1804043/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Note: Please see pdf for full abstract with equations. Optical flow is the apparent motion of the brightness patterns in an image. The pyramidal form of the Lucas-Kanade (LK) method is frequently used for its computation but experiments have shown that the method has deficiencies. Problems arise because of numerical issues in the least squares (LS) problem min ||Ax-b||_2^2 , A\in \mathbb{R}^{m \times 2} and m >> 2, which must be solved many times. Numerical properties of the solution x_0 = A^{\dagger}b = (A^TA)^{-1}A^Tb of the LS problem are considered and it is shown that the property m >> 2 has implications for the error and stability of x_0. In particular, it can be assumed that b has components that lie in the column space (range) \mathcal{R}(A) of A, and the space that is orthogonal to \mathcal{R}(A), from which it follows that the upper bound of the condition number of x_0 is inversely proportional to cos theta, where theta is the angle between b and its component in \mathcal{R}(A). It is shown that this bound, a non-linear condition number and the errors in the solutions of the LS problems increase as the pyramid is descended from the top level (coarsest image) to the base (finest image), such that the optical flow computed at the base of the pyramid may be computationally unreliable.Two examples of the computation of the optical flow demonstrate the theoretical results, and the implications of these results for extended forms of the LK method are discussed. Optical flow Lucas-Kanade condition estimation Gaussian pyramid Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-1804043","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":118082791,"identity":"480c8357-9081-4ca7-91d6-e1a983143bae","order_by":0,"name":"Joab Winkler","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABE0lEQVRIie2RsUrEQBBAJyzMNhvTrljkFyYcpDrOXwkcrI2FdoqggcDaKLYW9yGWeyx4jX9wFrkm1RVaBg50ciDXJLnWYl+x7MzwdmcYgEDgHxKV3UlAJ3yvOUpkBZFT+yKOK1wWxNHpkwcYVf7oFNR7xR1RRBnXQl19TlA+N7ft21QrKZzbwiwFbYr+xiQJRU2OapWv4w+jlcBiuYB5Vmrj+hUEcUl+itrgOrL+/pxf8ApEAfqiHFfSBq9b+8O/JF+sPBxVctSIEFvHigJWPCsDjVUIfkd+gsqIs9jOu1louaBVZlXTO372aKPN685nL/I9+m7tTKvEb+rtzV2aSEO9SsVb6MnT8CLTgXwgEAgEDvwCadlRWputi6EAAAAASUVORK5CYII=","orcid":"","institution":"University of Sheffield","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"Joab","middleName":"","lastName":"Winkler","suffix":""}],"badges":[],"createdAt":"2022-06-28 13:29:21","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-1804043/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-1804043/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":23820217,"identity":"bae0c279-2b48-476b-9129-4e52dfa5b49e","added_by":"auto","created_at":"2022-07-13 16:12:12","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1284768,"visible":true,"origin":"","legend":"","description":"","filename":"winkler.pdf","url":"https://assets-eu.researchsquare.com/files/rs-1804043/v1_covered.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Error analysis and condition estimation of the pyramidal form of the Lucas-Kanande method in optical flow ","fulltext":[{"header":"Full Text","content":"This preprint is available for \u003ca href='/article/rs-1804043/latest.pdf' target='_blank'\u003edownload as a PDF\u003c/a\u003e."}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Optical flow, Lucas-Kanade, condition estimation, Gaussian pyramid","lastPublishedDoi":"10.21203/rs.3.rs-1804043/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-1804043/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eNote: Please see pdf for full abstract with equations.\u003c/p\u003e\u003cp\u003eOptical flow is the apparent motion of the brightness patterns in an image. The pyramidal form of the Lucas-Kanade (LK) method is frequently used for its computation but experiments have shown that the method has deficiencies. Problems arise because of numerical issues in the least squares (LS) problem min ||Ax-b||_2^2 , A\\in \\mathbb{R}^{m \\times 2} and m \u0026gt;\u0026gt; 2, which must be solved many times. Numerical properties of the solution x_0 = A^{\\dagger}b = (A^TA)^{-1}A^Tb of the LS problem are considered and it is shown that the property m \u0026gt;\u0026gt; 2 has implications for the error and stability of x_0. In particular, it can be assumed that b has components that lie in the column space (range) \\mathcal{R}(A) of A, and the space that is orthogonal to \\mathcal{R}(A), from which it follows that the upper bound of the condition number of x_0 is inversely proportional to cos theta, where theta is the angle between b and its component in \\mathcal{R}(A). It is shown that this bound, a non-linear condition number and the errors in the solutions of the LS problems increase as the pyramid is descended from the top level (coarsest image) to the base (finest image), such that the optical flow computed at the base of the pyramid may be computationally unreliable.Two examples of the computation of the optical flow demonstrate the theoretical results, and the implications of these results for extended forms of the LK method are discussed.\u003c/p\u003e","manuscriptTitle":"Error analysis and condition estimation of the pyramidal form of the Lucas-Kanande method in optical flow ","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2022-07-13 16:12:05","doi":"10.21203/rs.3.rs-1804043/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"09e52b1d-d3b9-4514-9506-218b931e1cd1","owner":[],"postedDate":"July 13th, 2022","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2023-02-24T13:59:22+00:00","versionOfRecord":[],"versionCreatedAt":"2022-07-13 16:12:05","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-1804043","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-1804043","identity":"rs-1804043","version":["v1"]},"buildId":"WrCJVZZCHTDjtuVLN7oU0","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}