Abstract
In this paper, we present a new performance improvement method ‘exact window memoization’ for local image processing algorithms. Window memoization is a technique that uses the advantage of memoization method and data redundancy on images to minimize the amount of redundant computations by reusing the previous result, and it leads to achieve speedup of computation performed. In the tolerant window memoization, a part of pixels is eliminated to increase the probability of similar windows in entire of image, but it causes an accuracy loss in the results. In our new proposed method, the benefit of inter-pixel redundancy in images is used where the neighboring pixels are correlated, and window memoization technique is applied to windows where the MSBs part of pixels are same, and also the trivial computations of identical pixels in the neighborhood of windows are eliminated. In this new method, accuracy is preserved in the results as well as speedup computation performance is achieved when compared with the current window memoization technique. We have also presented a performance method to predict speedup achievement in the newly proposed method using inverse difference moment (IDM) as one of the statistical parameters of the gray-level co-occurrence matrix. We have developed this method on software and applied to Median and Kirsch edge detection filter on 512 × 512 of pixels images. The typical speedup computational performance compared with conventional method in an image with an IDM range between 0.5 and 0.6 in the median filter was 1.45× and for Kirsch edge detection was 1.61×.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alvarez, C., Corbal, J., Valero, M.: Fuzzy memoization for floating-point multimedia applications. IEEE T. Comput. 54(7), 922–927. doi:10.1109/Tc.2005.119 (2005)
Brugger, C., Dal’Aqua, L., Varela, J.A., De Schryver, C., Sadri, M., Wehn, N., Klein, M., Siegrist, M.: A quantitative cross-architecture study of morphological image processing on CPUs, GPUs, and FPGAs. In: Computer applications and industrial electronics (ISCAIE), 2015 IEEE Symposium on, 12–14 April 2015, pp. 201–206 (2015)
Ding, Y.H., Li, Z.Y.: Operation reuse on handheld devices (extended abstracts). Lang. Compil. Parallel Comput. 2958, 273–287. doi:10.1007/978-3-540-24644-2_18 (2004)
Gonzalez, R.C., Woods, R.E.: Digital image processing, 3rd edn. Prentice Hall, Upper Saddle River (2012)
Haas, B., Coradi, T., Scholz, M., Kunz, P., Huber, M., Oppitz, U., Andre, L., Lengkeek, V., Huyskens, D., Van Esch, A., Reddick, R.: Automatic segmentation of thoracic and pelvic CT images for radiotherapy planning using implicit anatomic knowledge and organ-specific segmentation strategies. Phys. Med. Biol. 53(6), 1751–1771 (2008). doi:10.1088/0031-9155/53/6/017
Haralick, R.M., Shanmuga.K, Dinstein, I.: Textural features for image classification. IEEE T. Syst. Man. Cyb. Smc3(6), 610–621. doi:10.1109/Tsmc.1973.4309314 (1973)
Hartley, T.D.R., Catalyurek, U., Ruiz, A., Igual, F., Mayo, R., Ujaldon, M.: Biomedical image analysis on a cooperative cluster of GPUs and multicores. In: Paper presented at the ACM international conference on supercomputing 25th anniversary volume, Munich, Germany (2015)
Hodge, A.C., Fenster, A., Downey, D.B., Ladak, H.M.: Prostate boundary segmentation from ultrasound images using 2D active shape models: optimisation and extension to 3D. Comput. Meth. Prog. Bio. 84(2–3), 99–113 (2006). doi:10.1016/j.cmpb.2006.07.001
Hughes, J.: Lazy memo-functions. Lect. Notes Comput. Sci. 201, 129–146 (1985)
Jain, A.K.: Image Data-compression—a review. P IEEE 69(3), 349–389. doi:10.1109/Proc.1981.11971 (1981)
Khalvati, F.: Computational redundancy in image processing, Ph.D. thesis, University of Waterloo (2008)
Khalvati, F., Aagaard, M.D.: Window memoization: an efficient hardware architecture for high-performance image processing. J Real Time Image Process. 5(3), 195–212 (2013). doi:10.1007/s11554-009-0128-y
Khalvati, F., Aagaard, M.D., Tizhoosh, H.R.: Accelerating image processing algorithms based on the reuse of spatial patterns. Can. Conf. Electr. Comput. Eng., 172–175 (2007). doi:10.1109/CCECE.2007.50
Khalvati, F., Kianpour, M., Tizhoosh, H.: Cascaded window memoization for medical imaging. In: Iliadis, L., Maglogiannis, I., Papadopoulos, H. (eds.) Artificial intelligence applications and innovations, vol. 364. IFIP Advances in information and communication technology, pp. 275–284. Springer, Heidelberg (2011)
Khalvati, F., Aagaard, M.D., Tizhoosh, H.R.: Window memoization: toward high-performance image processing software. J Real Time Image Process. 10(1), 5–25 (2015). doi:10.1007/s11554-012-0247-8
Kirsch, R.A.: Computer determination of constituent structure of biological images. Comput Biomed Res 4(3), 315. doi:10.1016/0010-4809(71)90034-6 (1971)
Michie, D.: Memo functions and machine learning. Nature 218(5136), 19. doi:10.1038/218019a0 (1968
Richardson, S.E.: Exploiting trivial and redundant computation. In: Computer arithmetic, 1993. Proceedings., 11th symposium on, 29 Jun–2 Jul 1993, pp. 220–227 (1993)
Sboner, A., Mu, X.J., Greenbaum, D., Auerbach, R.K., Gerstein, M.B.: The real cost of sequencing: higher than you think! Genome Biol 12(8). doi:10.1186/Gb-2011-12-8-125 (2011) (Artn 125)
Shen, J.P., Lipasti, M.H.: Modern processor design: fundamentals of superscalar processors, 1st edn. McGraw-Hill Higher Education, Boston (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Farzmahdi, M., Luo, R. Exact window memoization: an optimization method for high-performance image processing. J Real-Time Image Proc 16, 491–503 (2019). https://doi.org/10.1007/s11554-015-0560-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11554-015-0560-0