MOTION ANALYSIS ON THE MICRO GRAINED ARRAY PROCESSOR

Motion analysis plays a key role in video coding (e.g., video telephon e, MPEG, HDTV) and computer vision systems (e.g., image segmentation, structure from motion). Motion estimation methods can be classified in to three groups - matching-based, gradient-based, and frequency-based methods. The block matching algorithm (BMA) has been widely used for r egion matching in image coding, for example in MPEG (Motion Picture Ex pert's Group). Optical flow computation based on the spatio-temporal c onstraint equation has been broadly used in image segmentation to comp ute each pixel's velocity on a moving object. For both of these tasks, dedicated ASIC systems have been developed and widely used. Unfortuna tely, such systems have the disadvantage of restricted adaptability. T he Micro Grained Array Processor (MGAP), which is a fine-grained, mesh -connected, SIMD array processor being developed at Penn State Univers ity, can provide a more regular, flexible, and efficient approach for solving, in real time, these two important computations. In this paper , we propose a new data flow scheme for an efficient, systolic, full-s earch BMA on programmable array processors so that we can process as m any adjacent template blocks as possible in unison in order to reduce the data memory accesses. In particular we present an efficient implem entation of the BMA on the MGAP. As a result, the BMA for the MPEG SIF video format (352 X 240 pixels) with a block size of 16 X 16 pixels, a displacement range of 16 pixels, and frame rate of 30 frames/sec can be computed at real-time processing rates on the MGAP. We also show a real-time mapping to the MGAP of the optical flow computation for ima ges of size 256 X 256 pixels. (C) 1997 Academic Press Limited.