圖像匹配是NP完全問題外文文獻翻譯

1、Elastic image matching AbstractOne fundamental problem in image recognition is to establish the resemblance of two images. This can be done by searching the best pixel to pixel mapping taking into account monotonicity and continuity constraints. We show that this problem is NP-complete by reduction

2、from 3-SAT, thus giving evidence that the known exponential time algorithms are justified, but approximation algorithms or simplifications are necessary.Keywords: Elastic image matching; Two-dimensional warping; NP-completeness1. IntroductionIn image recognition, a common problem is to match two giv

3、en images, e.g. when comparing an observed image to given references. In that pro-cess, elastic image matching, two-dimensional (2D-)warping (Uchida and Sakoe, 1998) or similar types of invariant methods (Keysers et al., 2000) can be used. For this purpose, we can define cost functions depending on

4、the distortion introduced in the matching and search for the best matching with respect to a given cost function. In this paper, we show that it is an algorithmically hard problem to decide whether a matching between two images exists with costs below a given threshold. We show that the problem imag

5、e matching is NP-complete by means of a reduction from 3-SAT, which is a common method of demonstrating a problem to be intrinsically hard (Garey and Johnson, 1979). This result shows the inherent computational difficulties in this type of image comparison, while interestingly the same problem is so

6、lvable for 1D sequences in polynomial time, e.g. the dynamic time warping problem in speech recognition (see e.g. Ney et al., 1992). This has the following implications: researchers who are interested in an exact solution to this problem cannot hope to find a polynomial time algorithm, unless P=NP.

7、Furthermore, one can conclude that exponential time algorithms as presented and extended by Uchida and Sakoe (1998, 1999a,b, 2000a,b) may be justified for some image matching applications. On the other hand this shows that those interested in faster algorithmse.g. for pattern recognition purposesare

8、 right in searching for sub-optimal solutions. One method to do this is the restriction to local optimizations or linear approximations of global transformations as presented in (Keysers et al., 2000). Another possibility is to use heuristic approaches like simulated annealing or genetic algorithms

9、to find an approximate solution. Furthermore, methods like beam search are promising candidates, as these are used successfully in speech recognition, although linguistic decoding is also an NP-complete problem (Casacuberta and de la Higuera, 1999).2. Image matchingAmong the varieties of matching al

10、gorithms,we choose the one presented by Uchida and Sakoe(1998) as a starting point to formalize the problem image matching. Let the images be given as(without loss of generality) square grids of size MM with gray values (respectively node labels)from a finite alphabet &=1，G. To define the problem, t

11、wo distance functions are needed,one acting on gray values ：&N , measuring the match in gray values, and one acting on displacement differences d:ZZN , measuring the distortion introduced by the matching. For these distance functions we assume that they are monotonous functions (computable in polyno

12、mial time) of the commonly used squared Euclid-ean distance, i.e d(g,g)=f(|g-g|)and d(z)=f(|z|) monotonously increasing. Now we call the following optimization problem the image matching problem (let =1，M ).Instance: The pair( A ; B ) of two images A and B of size MM .Solution: A mapping function f

13、:.Measure:c（A,B,f）= + + Goal:minc(A,B,f).In other words, the problem is to find the mapping from A onto B that minimizes the distance between the mapped gray values together with a measure for the distortion introduced by the mapping. Here, the distortion is measured by the deviation from the identi

14、ty mapping in the two dimensions. The identity mapping fulfills f(i,j)=(i,j),and therefore，f(i,j)+(x,y)=f(i,j)+(x,y)The corresponding decision problem is fixed by the followingQuestion:Given an instance of image matching and a cost c, does there exist a mapping f such that c(A,B,f)c?In the definitio

15、n of the problem some care must be taken concerning the distance functions. For example, if either one of the distance functions is a constant function, the problem is clearly in P (for dconstant, the minimum is given by the identity mapping and for dconstant, the minimum can be determined by sortin

16、g all possible matching for each pixel by gray value cost and mapping to one of the pixels with minimum cost). But these special cases are not those we are concerned with in imagematching in general.We choose the matching problem of Uchida and Sakoe (1998) to complete the definition of the problem.

17、Here, the mapping functions are restricted by continuity and monotonicity constraints: the deviations from the identity mapping may locally be at most one pixel (i.e. limited to the eight-neighborhood with squared Euclidean distance less than or equal to 2). This can be formalized in this approach b

18、y choosing the functions f,f as e.g.f=id，f(x)=step(x):=3. Reduction from 3-SAT3-SAT is a very well-known NP-complete problem (Garey and Johnson, 1979), where 3-SAT is defined as follows:Instance: Collection of clauses C=C，,C on a set of variables X=x，x such that each cconsists of 3 literals for k=1，

19、K .Each literal is a variable or the negation of a variable.Question:Is there a truth assignment for X which satisfies each clause c, k=1，K ?The dependency graph D（）corresponding to an instance of 3-SAT is defined to be the bipartite graph whose independent sets are formed by the set of clauses C an

20、d the set of variables X .Two vert ices cand xare adjacent iff cinvolves xor.Given any 3-SAT formula U, we show how to construct in polynomial time an equivalent image matching problem l（）=（A(),B()）; . The two images of l（）are similar according to the cost function （i.e.f:c(A(),B(),f）0) iff the form

21、ula is satisfiable. We perform the reduction from 3-SAT using the following steps: From the formula we construct the dependency graph D（）. The dependency graph D（） is drawn in the plane. The drawing of D（）is refined to depict the logical behaviour of , yielding two images（A(),B()） .For this, we use

22、three types of components: one component to represent variables of , one component to represent clauses of , and components which act as interfaces between the former two types. Before we give the formal reduction, we introduce these components.3.1. Basic componentsFor the reduction from 3-SAT we ne

23、ed five components from which we will construct the in-stances for image matching , given a Boolean formula in 3-DNF, respectively its graph. The five components are the building blocks needed for the graph drawing and will be introduced in the following, namely the representations of connectors,cro

24、ssings, variables, and clauses. The connectors represent the edges and have two varieties, straight connectors and corner connectors. Each of the components consists of two parts, one for image A and one for image B , where blank pixels are considered to be of thebackground color.We will depict poss

25、ible mappings in the following using arrows indicating the direction of displacement (where displacements within the eight-neighborhood of a pixel are the only cases considered). Blank squares represent mapping to the respective counterpart in the second image.For example, the following displacement

26、s of neighboring pixels can be used with zero cost:On the other hand, the following displacements result in costs greater than zero:Fig. 1 shows the first component, the straight connector component, which consists of a line of two different interchanging colors,here denoted by the two symbolsand. G

27、iven that the outside pixels are mapped to their respective counterparts and the connector is continued infinitely, there are two possible ways in which the colored pixels can be mapped, namely to the left (i.e. f(2,j)=(2,j-1) or to the right (i.e. f(2,j)=(2,j+1),where the background pixels have dif

28、ferent possibilities for the mapping, not influencing the main property of the connector. This property, which justifies the name connector , is the following: It is not possible to find a mapping, which yields zero cost where the relative displacements of the connector pixels are not equal, i.e. on

29、e always has f(2,j)-(2,j)=f(2,j)-(2,j),which can easily be observed by induction over j.That is, given an initial displacement of one pixel (which will be 1 in this context), the remaining end of the connector has the same displacement if overall costs of the mapping are zero. Given this property an

30、d the direction of a connector, which we define to be directed from variable to clause, we can define the state of the connector as carrying thetruetruth value, if the displacement is 1 pixel in the direction of the connector and as carrying thefalse truth value, if the displacement is -1 pixel in t

31、he direction of the connector. This property then ensures that the truth value transmitted by the connector cannot change at mappings of zero cost. Image A image B mapping 1 mapping 2Fig. 1. The straight connector component with two possible zero cost mappings.For drawing of arbitrary graphs, clearl

32、y one also needs corners,which are represented in Fig. 2.By considering all possible displacements which guarantee overall cost zero, one can observe that the corner component also ensures the basic connector property. For example, consider the first depicted mapping, which has zero cost. On the oth

33、er hand, the second mapping shows, that it is not possible to construct a zero cost mapping with both connectorsleavingthe component. In that case, the pixel at the position marked? either has a conflict (that is, introduces a cost greater than zero in the criterion function because of mapping misma

34、tch) with the pixel above or to the right of it,if the same color is to be met and otherwise, a cost in the gray value mismatch term is introduced. image A image B mapping 1 mapping 2Fig. 2. The corner connector component and two example mappings.Fig. 3 shows the variable component, in this case wit

35、h two positive (to the left) and one negated output (to the right) leaving the component as connectors. Here, a fourth color is used, denoted by .This component has two possible mappings for the colored pixels with zero cost, which map the vertical component of the source image to the left or the ri

36、ght vertical component in the target image, respectively. (In both cases the second vertical element in the target image is not a target of the mapping.) This ensures1 pixel relative displacements at the entry to the connectors. This property again can be deducted by regarding all possible mappings

37、of the two images.The property that follows (which is necessary for the use as variable) is that all zero cost mappings ensure that all positive connectors carry the same truth value,which is the opposite of the truth value for all the negated connectors. It is easy to see from this example how vari

38、able components for arbitrary numbers of positive and negated outputs can be constructed. image A image B Image Cimage DFig. 3. The variable component with two positive and one negated output and two possible mappings (for true and false truth value).Fig. 4 shows the most complex of the components,

39、the clause component. This component consists of two parts. The first part is the horizontal connector with a bend in it to the right.This part has the property that cost zero mappings are possible for all truth values of x and y with the exception of two false values. This two input disjunction，can

40、 be extended to a three input dis-junction using the part in the lower left. If the z connector carries afalse truth value, this part can only be mapped one pixel downwards at zero cost.In that case the junction pixel (the fourth pixel in the third row) cannot be mapped upwards at zero cost and the

41、two input clause behaves as de-scribed above. On the other hand, if the z connector carries a true truth value, this part can only be mapped one pixel upwards at zero cost,and the junction pixel can be mapped upwards,thus allowing both x and y to carry a false truth value in a zero cost mapping. Thu

42、s there exists a zero cost mapping of the clause component iff at least one of the input connectors carries a truth value. image Aimage B mapping 1(true,true,false) mapping 2 (false,false,true,)Fig. 4. The clause component with three incoming connectors x, y , z and zero cost mappings for the two ca

43、ses(true,true,false)and (false, false, true).The described components are already sufficient to prove NP-completeness by reduction from planar 3-SAT (which is an NP-complete sub-problem of 3-SAT where the additional constraints on the instances is that the dependency graph is planar),but in order to

44、 derive a reduction from 3-SAT, we also include the possibility of crossing connectors. Fig. 5 shows the connector crossing, whose basic property is to allow zero cost mappings if the truthvalues are consistently propagated. This is assured by a color change of the vertical connector and a flexible

45、middle part, which can be mapped to four different positions depending on the truth value distribution.image Aimage Bzero cost mappingFig. 5. The connector crossing component and one zero cost mapping.3.2. ReductionUsing the previously introduced components, we can now perform the reduction from 3-S

46、AT to image matching .Proof of the claim that the image matching problem is NP-complete:Clearly, the image matching problem is in NP since, given a mapping and two images A and B ,the computation of c（A,B,f）can be done in polynomial time. To prove NP-hardness, we construct a reduction from the 3-SAT

47、 problem. Given an instance of 3-SAT we construct two images A and B , for which a mapping of cost zero exists iff all the clauses can be satisfied.Given the dependency graph D ,we construct an embedding of the graph into a 2D pixel grid, placing the vertices on a large enough distance from each oth

48、er (say 100（K+L） ).This can be done using well-known methods from graph drawing (see e.g.di Battista et al.,1999).From this image of the graph D we construct the two images A and B , using the components described above.Each vertex belonging to a variable is replaced with the respective parts of the

49、 variable component, having a number of leaving connectors equal to the number of incident edges under consideration of the positive or negative use in the respective clause. Each vertex belonging to a clause is replaced by the respective clause component,and each crossing of edges is replaced by th

50、e respective crossing component. Finally, all the edges are replaced with connectors and corner connectors, and the remaining pixels inside the rectangular hull of the construction are set to the background gray value. Clearly, the placement of the components can be done in such a way that all the c

51、omponents are at a large enough distance from each other, where the background pixels act as an insulation against mapping of pixels, which do not belong to the same component. It can be easily seen, that the size of the constructed images is polynomial with respect to the number of vertices and edg

52、es of D and thus polynomial in the size of the instance of 3-SAT, at most in the order （K+L）.Furthermore, it can obviously be constructed in polynomial time, as the corresponding graph drawing algorithms are polynomial.Let there exist a truth assignment to the variables x，x, which satisfies all the

53、clauses c，c. We construct a mapping f , that satisfies c（f,A,B）=0 as follows.For all pixels (i, j ) belonging to variable component l with A（i，j）not of the background color,set f（i，j）=（i，j-1）if xis assigned the truth value true , set f（i，j）=（i，j+1）, otherwise. For the remaining pixels of the variabl

54、e component set A（i，j）=B（i，j），if f（i，j）=（i，j）, otherwise choose f（i，j）from (i,j+1),(i+1,j+1),(i-1,j+1)for xfalse respectively from (i,j-1),(i+1,j-1),(i-1,j-1) for x true ,such that A（i，j）=B（f（i，j）. This assignment is always possible and has zero cost, as can be easily verified.For the pixels（i，j）bel

55、onging to (corner) connector components,the mapping function can only be extended in one way without the introduction of nonzero cost,starting from the connection with the variable component. This is ensured by the basic connector property. By choosing f（i，j）=（i,j）for all pixels of background color,

56、 we obtain a valid extension for the connectors. For the connector crossing components the extension is straight forward, although hereas in the variable mappingsome care must be taken with the assign ment of the background value pixels, but a zero cost assignment is always possible using the same s

57、cheme as presented for the variable mapping.It remains to be shown that the clause components can be mapped at zero cost, if at least one of the input connectors x , y , z carries a true truth value.For a proof we regard alls even possibilities and construct a mapping for each case. In the descripti

58、on of the clause component it was already argued that this is possible,and due to space limitations we omit the formalization of the argument here.Finally, for all the pixels（i，j）not belonging to any of the components, we set f（i，j）=（i，j）thus arriving at a mapping function which has c（f，A，B）=0。as all colors are preserved