Об оптимизации алгоритма построения стационарного потока на ориентированном графе
Аннотация
В работе рассмотрен метод получения классификационного признака изображений, основанный на построении стационарного потока на графе, построенном по данному изображению. На основании начального и стационарного потоков вычисляется взвешенная энтропия, которая рассматривается как классификационный признак. В работе рассмотрены различные подходы к оптимизации данного алгоритма. Один из предложенных подходов состоит в делении исходного изображения на некоторое число областей, вычисления для которых можно производить независимо друг от друга на разных ядрах процессора. Второй подход основан на разбиении изображения на ячейки заданного размера и построении графа, вершинам которого сопоставлены эти ячейки. Третий подход состоит в использовании в представлении данных так называемых неизменяемых коллекций, позволяющих проводить распараллеливание без синхронизации. Приведены сравнительные результаты численных экспериментов.
Литература
[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
Материал публикуется под лицензией:
