Technologies

Memoization is a computing optimization technique that is used to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs. Traditional memoization techniques have mostly failed to deliver tangible performance improvement in practice due to the generality of the techniques and lack of a priori knowledge about the characteristics of the input data or algorithms.

University of Waterloo researchers have developed a new computational performance technique, referred to as “window memoization” that is focussed on image processing algorithms. The technique works by minimizing the number of redundant computations performed on an image by identifying similar neighbourhoods of pixels in the image and skipping the redundant computations. As the window memoization technique has been designed for the unique characteristics of image processing algorithms, the technique is easy to implement and delivers significant image processing speed improvement. In software implementation, window memoization achieves typical speedups in the range from 1.2x (e.g. ultrasound image processing) to a maximum factor of 40x (e.g. industrial inspection applications). In hardware (FPGA) implementation, the typical and maximum speedup factors are 1.6 and 1.8, respectively, with 40% less hardware area in comparison to conventional optimization techniques.