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

The use of stochastic gradient descent-based search procedures is one of the most reliable approaches for fragment searching on the image. However, these procedures provide a small search range making it necessary to divide the image into multiple areas, each of which has its own procedure. In addition, there is a problem of defining the area consisting the fragment. If all procedures perform the same number of iteration providing the necessary reliability of the searc, it leads to high computational cost. The fragment area selection requires the use of a selection criterion, e.g. the maximum of the correlation coefficient, which further increases the amount of computation. There is an algorithm aimed to reduce the computational complexity. It is based on control of multiple procedures, where at each ite-ration the priority is given to the procedure having the highest value of a priority function. The algorithm step includes the iteration by the leading procedure and computation of its priority function followed by the definition of a new leading procedure. The fragment is said to be at the arear where the estimation procedure has the defined number of iterations. In general, it is unknown whether the image contains the fragment. Thus, the procedure has to check the hypotheses of fragment absence and the fragment area is chosen only if the hypothesis is declined. When testing the hypothesis of the first and the second type of error can occur. A classical approach is the likelihood ratio being computed for each of the studied area and compared with a threshold. However, finding the joint probability density of all procedures is extremely difficult since the procedures operating in different subdomains execute a different number of iterations. For the algorithm a criterion for testing the hypothesis of the absence of the fragment is proposed which allows comparing estimation procedures with different number of iterations. The total number of iterations done by all the procedures before the leading procedure overcome the threshold value is chosen as the numerical criterion of fragment absence hypothesis test. This hypothesis test is a simple test: if none of the procedures did not fulfill the threshold number of iterations for the critical number of steps of the algorithm, the study area does not contain the desired fragment. The formulas that allow to find the parameters of the algorithm (the number of iterations for the leading procedures and the number of steps of the algorithm) with the required level of type 1 and type 2 errors are obtained. Conditions of the decision on the absence of the fragment on the image is found. The formulas use the probability distribution function and the threshold value for the number of iterations of the leading procedure.

 

1. Cypkin JA.Z. Informacionnaja teorija identifikacii. M.: Nauka. Fizmatlit. 1995. 336 s.
2. Zitova B., Flusser J. Image registration methods: a survey // Image and vision computing. 2003. V. 21. № 11. P. 977−1000.
3. Tashlinskijj A.G. Ocenivanie parametrov prostranstvennykh deformacijj posledovatelnostejj. Uljanovsk: UlGTU. 2000. 131 s.
4. Tashlinskii A. Computational Expenditure Reduction in Pseudo-Gradient Image Parameter Estimation // Proceeding of Computational Scince - ICCS. Part II. Berlin: Springer. 2003. V. 2658. P. 456−462.
5.  Szeliski R. Image alignment and stitching: A tutorial // Technical Report MSR-TR-2004-92. Microsoft Research. 2004. 93 p.
6.  Pankova T.L., Reznik A.L. EHffektivnost algoritmov precizionnogo sovmeshhenija cifrovykh izobrazhenijj // Avtometrija. 1991. № 5. S. 39−43.
7. Tashlinskii A.G. and 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.
8. Tashlinskijj A.G., Muratkhanov D.S. Strukturnaja optimizacija algoritmov ocenivanija parametrov geometricheskikh deformacijj izobrazhenijj // Prilozhenie k zhurnalu «Fizika volnovykh processov i radiotekhnicheskikh sistem». 2001. S. 102−110.
9. Koroljuk V.S. i dr. Spravochnik po teorii verojatnostejj i matematicheskojj statistike. M.: Nauka. 1985. 640 s.
10. Muratkhanov D.S. Strukturnaja optimizacija algoritmov pri ocenivanii geometricheskikh deformacijj izobrazhenijj // Trudy III Vseros. nauchno- praktich. konf. «Sovremennye problemy sozdanija i ehkspluatacii radiotekhnicheskikh sistem».  Uljanovsk: UlGTU. 2001. S. 129−131.