Radiotekhnika
Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS


Тел.: +7 (495) 625-9241

 

Computational complexity of searching for a fragment pattern on an image using a variety of managed procedures

Keywords:

L.Sh. Biktimirov – Assistant, Department «Radio Engineering», Ulyanovsk State Technical University
E-mail: linarbiktimirov@rambler.ru
A.G. Tashlinskii – Dr. Sc. (Eng.), Professor, Head of Department «Radio Engineering», Ulyanovsk State Technical University
E-mail: tag@ulstu.ru


One of the classes of search algorithms based on the fragment reference in the image is based on the use of recurrent pseudo-gradient procedures that provide a relatively small search working range, which requires splitting the image of large sizes into a number of small regions, each of which has its own procedure. Ensuring the required authenticity of the fragment identification is achieved by a predetermined threshold number of iterations, but the problem arises of determining the region in which the fragment is located.
For images of large sizes, the execution of all the search procedures by the threshold number of iterations leads to large computational costs. To reduce computational costs, an algorithm is proposed for controlling a number of procedures, the working areas of which cover the image under study. The management is based on the analysis of the chosen penalty function of the procedures and the granting of priority to the execution of the next iteration of the procedure with a minimum penalty. In this case, the «step of the algorithm» includes the operations of performing the procedure with the least penalty of the next iteration, calculating a new penalty and determining the next procedure with a minimum penalty. The criterion for identifying an area containing the desired fragment is the achievement of a given threshold number of iterations of one of the procedures.
In the paper, the average computational costs of the algorithm are analyzed in comparison with the costs that are required to achieve the same result without using procedural management. For this purpose, discrete probability distributions of the number of iterations obtained by the procedures for the situations of presence and absence of the desired fragment are obtained. Using the distributions obtained and assuming the independence of procedural penalties, expressions are found that determine the mathematical expectation of computational costs. At the same time, the restriction on the independence of fines is not rigid, since in the general case the samples of the image regions without the fragment are weakly correlated with the sample images of the fragment.
Examples of discrete distributions of the number of iterations for simulated images with a correlation function close to Gaussian are given. It is shown that the use of the considered control principle by a variety of search procedures leads to a significant reduction in computing costs. In this case, the cost advantage increases with the number of managed procedures. So, in the example above, on the hundredth iteration with 50 search procedures, the gain was 1.7 times, at 200 – 2.8 times, at 1000 – 5.6 times.

References:
  1. Ipatov Yu.A., Kreveczkij A.V. Modelirovanie metodov obnaruzheniya i prostranstvennoj lokalizaczii gruppovy'x tochechny'x ob''ektov // Nauka. Texnologii. Proizvodstvo. 2014. № 2. S. 7−11.
  2. Gerasimova N.I., Verxoturova A.E'. Poisk fragmenta izobrazheniya s ispol'zovaniem nejronnoj seti Koxonena // Sb. nauchny'x trudov «Informaczionny'e texnologii v nauke, upravlenii, soczial'noj sfere i mediczine». Tomsk: TPU. 2014. Ch. 1. S. 68−70.
  3. Chambon S., Crouzil A. Dense matching using correlation: new measures that are robust near occlusions // British Machine Vision Conference, Norwich, Great Britain. 2003. V. 1. P. 143−152.
  4. Czy'pkin Ya.Z. Informaczionnaya teoriya identifikaczii. M.: Nauka. Fizmatlit. 1995. 336 s.
  5. Zitova B., Flusser J. Image registration methods: a survey // Image and vision computing. 2003. V. 21. № 11. P. 977−1000.
  6. Tashlinskij A.G. Oczenivanie parametrov prostranstvenny'x deformaczij posledovatel'nostej. Ul'yanovsk: UlGTU. 2000. 131 s.
  7. Szeliski R. Image alignment and stitching: A tutorial // Technical Report MSR-TR-2004-92. Microsoft Research. 2004. 93 p.
  8. Tashlinskii A.G. Pseudogradient Estimation of Digital Images Interframe Geometrical De-formations / Vision Systems: Segmentation & Pattern Recognition. 2007. Vienna (Austria): I Tech Education and Publishing. P. 465−494.
  9. Zhukova A.V., Voronov S.V. Analiz e'ffektivnosti primeneniya korrelyaczionny'x mer v kachestve czelevy'x funkczij v rekurrentny'x proczedurax privyazki izobrazhenij // Radioe'lektronnaya texnika. 2016. № 9. S. 11−16.
  10. Voronov S.V., Tashlinskii A.G. Efficiency analysis of information theoretic measures in image registration // Pattern recognition and image analysis. 2016. V. 26. № 3. P. 502−505.
  11. Tashlinskii A.G., Muratkhanov D.S. Structural Optimization of Pseudogradient Algorithms for Measuring Interframe Image Deformations // Pattern Recognition and Image Analysis. 2003. V. 13. № 1. P. 177−178.
  12. Biktimirov L.Sh., Tashlinskij A.G. Oczenka veroyatnosti otsutstviya iskomogo fragmenta na izobrazhenii dlya algoritma s upravleniem mnozhestvom proczedur poiska // Radiotexnika. 2016. № 9. S. 6−10.

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio