ANALYSIS AND DATA PROCESSING SYSTEMS
Print ISSN: 2782-2001
Online ISSN: 2782-215X
The paper considers methods of reducing the number of operations while performing a digital image filtration. An image filter algorithm is based on the mathematical operation called two-dimensional convolution. The peculiarities of using a two-dimensional convolution for image filtration include a possibility of filter factor preprocessing and a big difference between the number of points in an image and kernel of the image filter. The authors analyze well-known methods of decomposition of two-dimensional convolution into several convolutions with fewer numbers of points as applied to image filtration. To compare a cost of the methods, we derived formulas to evaluate of the number of operations required to calculate a reaction of the image filter for one point (pixel). Using these formulas, we found methods with a minimal cost for various kernel sizes. Based on the results obtained, we conclude that the two-dimensional convolution method based on the decomposition of convolution into 9 half-size convolutions is quite appropriate for implementing image filters with a kernel size larger or equal to 5×5. Reducing the number of required operations when applying the decomposition with a 5×5 kernel gives 16 %, 7×7 – 27 %, 9×9 – 31 %. On the basis of the decomposition of a two-dimensional convolution in the paper, it is possible to increase the speed of some image processing algorithms when an image is divided into several blocks with a size corresponding to the filter kernel.
Altman Evgenii A.
Zakharenko Elena I.
Vaseeva Tatiana V.
1. Al'tman E.A., Anan'eva N.G., Tikhonova N.A. Primeneniealgoritmovkomp'yuternogozreniyadlyadetektirovaniyaob"ektovnazheleznodorozhnompereezde[Application algorithms of computer vision for оbject detection on the railway crossing]. IzvestiyaTranssiba– Journal of Transsib Railway Studies, 2016, no. 1 (25), pp. 70–76.
2. Gonzalez R.C., Woods R.E.Digital image processing. New York, NY, Pearson, 2007(Russ. ed.: Gonsales R., Vuds R. Tsifrovayaobrabotkaizobrazhenii. 3rd ed. Moscow,Tekhnosfera Publ., 2012. 1104 p.).
3. Rabiner L.R., Gold B. Theory and application of digital signal processing. Englewood Cliffs, N.J., Prentice-Hall, 1975 (Russ. ed.: Rabiner L., Gould B. Teoriyaiprimenenietsifrovoiobrabotkisignalov. Moscow, Mir Publ., 1978. 848 p.).
4. Blahut R.E. Fast algorithms for digital signal processing. Reading, MA, Addison Wesley, 1985 (Russ. ed.: Bleikhut R. Bystryealgoritmytsifrovoiobrabotkisignalov.Moscow, Mir Publ., 1989. 448 p.).
5. Lukin A. Vvedenie v tsifrovuyuobrabotkusignalov (matematicheskieosnovy)[Introduction to digital signal processing (mathematical foundations)]. Moscow, MSU Publ., 2002. 44 p.
6. Naito Y., Miyazaki T., Kuroda I. A fast full-search motion estimation method for programmable processors with a multiply-accumulator.IEEE International Conference on Acoustics, Speech and Signal Processing, 1996, vol. 6, pp. 3221–3224.
7. Al'tman E.A., Zakharenko E.I. Bystryialgoritmvychisleniyadvumernoikorrelyatsiidlyavideoobrabotki[Fast algorithm for calculating two-dimensional correlation for video processing]. DokladyTomskogogosudarstvennogouniversitetasistemupravleniyairadioelektroniki – Proceedings of Tomsk State University of Control Systems and Radioelectronics, 2015, no. 2 (36), pp. 119–124.
8. Mou Z.J., Duhame P. Fast FIR filtering: algorithms and implementations.Signal Processing, 1987,vo1. 13, no. 4,pp. 377–384.
9. Kalinovskii I.A., Spitsyn V.G. Primeneniepolinomial'nykhpreobrazovaniidlyabystrogovychisleniyadvumernykhsvertok[Application of polynomial transforms for fast 2D convolutions]. Vychislitel'nyemetodyiprogrammirovanie: novyevychislitel'nyetekhnologii – Numerical Methods and Programming,2016,vol. 17, no. 3, pp. 197–201.
10. Gol'denberg L.M., Matyushkin B.D., Polyak M.N. Tsifrovayaobrabotkasignalov: spravochnik[Digital signal processing: reference book]. Moscow,Radio isvyaz' Publ., 1985. 312 p.
11. Gruzman I.S., Kirichuk V.S., Kosykh V.P., Peretyagin G.I., Spektor A.A. Tsifrovayaobrabotkaizobrazhenii v informatsionnykhsistemakh[Digital processing of images in information systems]. Novosibirsk, NSTU Publ., 2002. 352 p.
12. Blahut R.E.Theory and practice of error control codes.Reading, MA, Addison-Wesley, 1984 (Russ. ed.: Bleikhut R. Teoriyaipraktikakodov, kontroliruyushchikhoshibki.Moscow, Mir Publ., 1986. 576 c.).
13. Huang T.S., ed.Two-dimensional digital signal processing. Berlin, New York, Springer-Verlag, 1981 (Russ. ed.: Bystryealgoritmy v tsifrovoiobrabotkeizobrazhenii: preobrazovaniyaimediannyefil'try. Ed. by T.S. Khuang.Moscow, Radio isvyaz' Publ., 1981. 224 p.).
14. Madisetti V.K. The digital signal processing handbook.Vol. 1.2nd ed. Boca Raton, FL, CRC Press, 2009.904 p.
15. Shapiro L.G., Stockman G.C.Computer vision. Upper Saddle River, N.J., Prentice-Hall, 2001 (Russ. ed.: Shapiro L., Stokman Dzh. Komp'yuternoezrenie.Moscow, Binom. Laboratoriyaznanii Publ., 2006.752 p.).
Altman E.A., Zakharenko E.I., Vasеeva T.V. Primenenie metoda razlozheniya dvumernoi svertki pri realizatsii tsifrovykh fil'trov [Аpplication of the decomposition method of two-dimensional convolution in implementing digital filters]. Nauchnyi vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universiteta – Science bulletin of the Novosibirsk state technical university, 2017, no. 4 (69), pp. 95–104. doi: 10.17212/1814-1196-2017-4-95-104.
