Background

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.

Description of the invention

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.

The initial development focus has been on exploiting the computational
redundancy of single image slices (i.e. intra-frame redundancy). More recent development efforts have extended the technique to exploit the “inter-frame” redundancy in medical image volume data sets. Adding this extra inter-frame dimension had led to even faster image processing performance. Additionally a GUI-based application has been developed that partially automates the steps required to embed the window memoization technique into an existing image processing algorithm.

Advantages

  • Runtime optimization that is scalable across various machine platforms
  • In software, 1.2 to 40 times speedups of processing time
  • In hardware, 1.6 to 1.8 times speedups with 40 per cent less hardware area

Potential applications

  • Machines vision system
  • Medical imaging processing
  • Smart phone image processing
  • Industrial inspection

Printable PDF
 

Image Processing Optimization

Reference

8810-7264

Patent status

Issued U.S. 9,076,240 and PCT
patent application

Stage of development

Proof-of-principle studies in progress
Seeking industrial partner for medical imaging processing
Studies for additional markets are
on-going

Contact

Scott Inwood
Director of Commercialization
Waterloo Commercialization Office
519-888-4567, ext. 33728
sinwood@uwaterloo.ca
uwaterloo.ca/research