Domain Decomposition for Variational Optical-Flow Computation

Abstract—We present an approach to parallel variational op-tical-flow computation by using an arbitrary partition of the image plane and iteratively solving related local variational problems as-sociated with each subdomain. The approach is particularly suited for implementations on PC clusters because interprocess commu-nication is minimized by restricting the exchange of data to a lower dimensional interface. Our mathematical formulation supports various generalizations to linear/nonlinear convex variational approaches, three-dimensional image sequences, spatiotemporal regularization, and unstructured geometries and triangulations. Results concerning the effects of interface preconditioning, as well as runtime and communication volume measurements on a PC cluster, are presented. Our approach provides a major step toward real-time two-dimensional image processing using off-the-shelf PC hardware and facilitates the efficient application of variational approaches to large-scale image processing problems. Index Terms—Domain decomposition, image processing, optical flow, parallel computation, partial differential equations, substruc-turing, variational techniques