On the Algorithm Optimization for Calculation a Stationary Flow on an Oriented Graph
Abstract
A method for obtaining the classification attribute of images based on the construction of a stationary flow on a graph constructed from a given image is considered. Weighted entropy, which is considered as a classification attribute, is calculated by the initial and stationary flows. Various approaches for optimizing this algorithm are considered in the paper. One of the proposed approaches is to divide the original image into a number of areas, the calculations for which can be performed independently from each other on different processor cores. The second approach is based on splitting the image into cells of a given size and constructing a graph whose vertices are associated with these cells. The third approach is to use in the data representation the so-called immutable collections that allow parallelization without synchronization. Comparative results of numerical experiments are presented.
References
[2] N. B. Ampilova, I. V. Romanovskii, and E. I. Petrenko, “O maksimizatsii entropii pri lineinykh ogranicheniyakh” [On the maximization of entropy under linear constraints], In Trudy Mezhdunarodnoi nauchnoi konferentsii “Kosmos, astronomiya i programmirovanie,” Saint-Petersburg, Russia, 2008, pp. 181–185 (in Russian).
[3] A. Batyukov, “Analiz tsifrovykh izobrazhenii, osnovannyi na postroenii statsionarnogo potoka na grafe” [Analysis of digital images based on the construction of a stationary flow on a graph], Vestnik Sankt-Peterburgskogo universiteta. Seriya 10. Prikladnaya matematika, informatika, protsessy upravleniya, no. 2, pp. 115–122, 2015 (in Russian).
[4] A. M. Batyukov, “Klassifikatsiya izobrazhenii biomeditsinskikh preparatov adaptirovannym dlya parallel'nykh vychislenii algoritmom postroeniya statsionarnogo potoka” [Classification of images of biomedical preparations adapted for parallel computations by the algorithm for constructing a stationary flow], In Sbornik trudov Mezhdunarod noi konferentsii “Aktual'nye problemy prikladnoi matematiki, informatiki i mekhaniki,” Moscow, Russia, 2015, pp. 39–43 (in Russian).
[5] L. M. Bregman, “Dokazatel'stvo skhodimosti metoda G.V. Sheleikhovskogo dlya zadachi s transportnymi ogranicheniyami” [Proof of the convergence of the method Sheleikhovsky for a problem with transport restrictions], Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki, vol. 7, no. 1, pp. 147–156, 1967 (in Russian).
[6] L.M. Bregman, “Relaksatsionnyi metod nakhozhdeniya obshchei tochki vypuklykh mnozhestv i ego primenenie dlya resheniya zadach vypuklogo programmirovaniya” [Relaxation method for finding a general point of convex sets and its application to solving convex programming problems], Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki,. vol. 7, no. 3, pp. 620–631, 1967 (in Russian).
[7] T. H. Cormen, Algoritmy: postroenie i analiz [Algorithms: construction and analysis], 2nd. ed., Moscow, Russia: Williams, 2006 (in Russian).
[8] G. V. Sheleikhovskii, Kompozitsiya gorodskogo plana kak problema transporta [Composition of the urban plan as a problem of transport], Moscow, Russia: Giprogor, 1946 (in Russian).
[9] N. B. Ampilova, V. D. Sergeev, and I. P. Soloviev, “On the method of digital image analysis based on the construction of a stationary flow on graph,” Humanities and Science University Journal , no. 22, pp. 29–36, 2016.
[10] “Classes to support functional-style operations on streams of elements, such as map-reduce transformations on collections” in Java™ Platform Standard Ed. 8 [Online], Available: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html
This work is licensed under a Creative Commons Attribution 4.0 International License.
