The effectiveness of pattern-match searching for the fragment on image using set of pseudo-gradient procedures covering all initial image by their workplaces is studied. Procedures control is managed to reduce computational expenses and based on analysis of penalty function and giving priority of making next iteration to procedure that has minimum value of penalty. It is considered that required fragment belongs to the domain that has a procedure which is reached prescribed limit of iterations. If it is prior unknown if there is any required fragments on the initial image, the hypothesis of their absence should be tested. If the hypothesis is not confirmed than the scan for domains with fragments should be performed. Concerning there are fragments on the image the missing probabilities are found using penalty function and limit of iterations. Herein, the proposal is considered for single and multiple required fragments.
contain some kind of testting the hypothesis of absence of fragments. During testing process there can be first P(
Let us consider the probability PER of wrong choice of image domain with fragment in case it is on the image. Also the probability of making an error selecting k > 1 domains when there are k identical fragments on the image, for example, images of equal objects (biological or technical) will be considered. Taking into account differences in search processes for single or multiple fragments these processes would be investigated separately.
PF 1 P(
P = PF PER + 1 PF P(
Image Processing, Geoinformation Technology and Information Security / L.Sh. Biktimirov, A.G. Tashlinskii
Let image (or just part of it) where should be found the fragment is divided to N domains and there is just one of them to contain required fragment. Let's find error probability of that domain identification PER . Assume that goal function and PF of PGP are pre-defined. Let us call « x+ » value of PF X for the procedure in domain with fragment and « x » in domain without fragment.
If there are only two domains then domain without fragment will be chosen if its procedure will be first to make T iterations, i.e. xТ < x+ , where xТ is equal to PF value on T th iteration. Here, second procedure may perform from 1 to T 1 iterations. Then, if value of PF on T th iteration is equal to x0 , to assume that choice is wrong it should be two conditions simultaneously: PF of the procedure in domain with required fragment exceed x0 and in domain without fragment PF value should be equal to x0 . Proposing that these events are independent the probability of wrong choice will equal to: x0 PER = wxТ+ dx wxТ dx .
x0 0
But value of x0 is prior unknown and wrong choice probability generally is equal to probability that on T th iteration xТ+ > xТ
PER = wxТ 1 F xТ+dx = wxТ+F xТ dx ,
0 0 x where F xТ = wxТ dx is integrated distribution function.
0
It should be noticed that densities of distribution parameters [14] estimated by procedure and in this context are relative. Proposing that initial parameters' approximation for procedure in fragment's domain gets worst convergence in work range of procedure PER will be the upper limit of wrong fragment choice's probability.
If number of separated domains is equal to N , than assuming independence of procedure's PF (taking into account (
wx+ and wx are depending on initial approximation of search
The assumed restriction about PF independence is not strict cause samples from domains that don't have a fragment have weak correlation with samples from fragment.
In previous case the required domain was assumed domain with procedure achieved limit of T iteration first of all others. Here, to provide low error probability of fragment's search with high signal/noise ratio it is necessary to specify large number of iterations. It is possible to decrease error probability with low T choosing several domains where procedures made limit of the iterations. Then probability of occurrence of domain with fragment among chosen domains increases. But it is not true for probability of right choice of the fragment.
There are criteria allowing to identify the fragment with low error probability, such as above mentioned maximum of correlation index that can be calculated on whole image, or extremes of information-theoretical measures of images similarity [15]. But using such criteria causes large computational expenses. Moreover, if image is divided into a lot of search domains and computing resources are strictly limited using of these criteria is not reasonable. But for small number of domains (for example, two) using these criteria is acceptable. On this basis, the probability of location the fragment among n domains where corresponding procedures firstly made prescribed limit of iterations.
If local samples to estimate all procedure’s goal function value are independent and suppose best value of PF has domain without fragment a random event, than task may be reduced to Bernoulli scheme. So for probability PE(nR) of missing domain with fragment during choice n domains with procedures first reached prescribed limit of iterations using binomial law it can be written:
N 1 PE(nR) = wxТ+ CiN 1F xТ 1 F xТ N i1dx ,
0 i=n
Where C N 1 is a number of combinations from N 1 of i elements. It should be noticed that cause number of
i
investigating domains in general is less than general number of domains of separated image ( n << N ) so it is reasonable to use
next expression:
(
n1 PE(nR) = wxТ+ 1 C N 1F xТ 1 F x N i1
0 i=0 i Т dx . iteration when choosing one(solid-line curve) and two (dashed-line curve) domains. Calculation carried out for relay-type PGP with working range requiring to split two different-size images on 36 (curve 1 and 2) and 625 domains (curve 3 and 4). Initial parameters of mismatch were equal to 6 steps of parallel shift and 20 degrees of turn. q 1 was computed as a ratio of incomplete Bq(N n,n) = x N n11 xn1dx and complete B(N n, n)= xN n11 xn1dx 0 0 beta-functions [16], where q = 1 FPT ψ . Hence while representing complete beta-function through gamma-function [17] will get
BN n,n = Γ N nΓ n Γ N
, PN-10 i n 1=
q Γ N x N n11 xn1dx 0 Γ N nΓ n
It is obvious from graphs that if n = 2 probability PE(nR) is essentially low. For example, if N = 36 and T =1000 probability of error in choice depending to situation n = 1 is decreasing by 5.5 times, and if T = 2000 – by 9 times. In this case, of course, computational expenses are increasing too.
Let’s consider probability of missing at least one of domains with fragments location during search position of k >1 similar fragments. In this case it should be at a minimum k procedures to make limit number of T iterations. Same as before, it will be considered that presence of the fragments is known in advance.
In particular, in case n = k similar to (
P(k) = 1 PE(kR) = 1 wk xТ+ 1 1 F x N 1 dx ,
0 Т where wk x means probability density function for maximum of k PF’s values of procedures from domains with fragments.
Т
To decrease probability of missing fragments the number of domains to choose can be more than the number of required
fragments ( n > k ). In this case probability PERjk of missing j domains with fragments from k considering ratio (
PERjK = wk xТ+ 1 nCiN k F xТ+ 1 F xТ N k i dx ,
0 i=0 1 F xТ+ j 1 F k j 1xТ+ j k Fx+ is probability density function of j th ranged by maximum PF
Т k procedures in domains with fragments i = 1, k .
One of the class of the algorithms to search fragment on the image by template is based on the PGP. But these procedures have relatively small working range of search that makes it necessary to split the image into array of domains each of them i s containing own procedure. Here is a task about finding domains with required fragments. If all search procedures are working in same conditions and will make equal number of iterations than it require huge computational expenses. To reduce these expenses the algorithm of managing ensemble of PGP [12] can be used. In this case on the each step priority of making next iteration is giving to procedure that has best value of some penalty function. Domains with procedures made prescribed limit of iterations first are chosen as a required ones (probably containing fragments).
If it is prior unknown if there are required fragments on the image it is necessary to test the hypothesis about absence of
fragments with prescribed error probabilities of first and second types. This issue and statistical criteria of hypothesis validity
are considered in papers [13, 18]. If the hypothesis is rejected then choosing domains of fragments’ location carried out. In this
case error probability of choosing domains of fragment’s location is a conditional probability and with prescribed second -type
error probability in general determines by expression (
Probability of wrong choice assuming there are required fragments on the initial image depends on their count. If there is
only one fragment and procedure then probability of wrong choice of domain with fragment determines by expression (
If required fragments is more than one and each of them has corresponding one search procedure then probability of case
when all procedures of domains with objects will make limited number of iterations first determines by expression (
The study was carried out with financial support of the RFBR grant 16-01-00276.