Split and shift methodologyOvercoming hardware limitations on cellular processor arrays for image processing

Abstract

This thesis addresses the so-called Split and Shift (S&S) methodology. This methodology is intended to deal with the implementation of kernels of sizes that overflow the physically implemented resources (local connections and weighting circuits) on synchronous Cellular Processor Arrays (CPA), including the realization of large neighborhood operations and/or the reduction of the available hardware in order to drop the area consumption. Two main goals are pursed in the development of the methodology, namely 1) minimum penalty at processing time and 2) absolutely no penalty at functional level. The work presents different techniques and guidelines for the methodology application and introduces a Figure of Merit (FoM) to evaluate them by relating area gains with time penalty. Together with a shape analysis over a well known kernel library we propose more adequate weighting circuits configurations and justify the classical choice of NEWS (North-East-West-South) connectivity. To validate the methodology we realize several estimates over actual physical implementations and we propose the realization over CPAs of the spin filters, SIFT (Scale Invariant Feature Transform) and SURF (Speeded-Up Robust Features) algorithms. A more in-depth trade-off analysis is realized over the implementation of the Pixel Level Snakes (PLS) algorithm.