Elastic-image-matching弹性图像匹配大学毕业论文外文文献翻译及原文

　　毕 业 设 计（论文） 外 文 文 献 翻 译

　　文献、资料中文题目：弹性图像匹配

　　文献、资料英文题目：Elastic image matching 文献、资料来源：

　　文献、资料发表（出版）日期：

　　院 （部）：

　　专 业：

　　班 级：

　　姓 名：

　　学 号：

　　指导教师：

　　翻译日期： 2017.02.14

　　In image recognition, a common problem is to match two given 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 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 image 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 solvable 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. 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 algorithms––e.g. for pattern recognition purposes––are 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 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 matching

　　Among the varieties of matching algorithms,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, two distance functions are needed,one acting on gray values dg：→N , measuring the match in gray values, and one acting on displacement differences dd:ZZ→N , measuring the distortion introduced by the matching. For these distance

　　functions we assume that they are monotonous functions (computable in polynomial time) of the commonly used squared Euclid-ean distance, i.e dg(g1,g2)=f1(||g1-g2||)and dd(z)=f2(||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 :→.

　　Measure:

　　c（A,B,f）=?dg(Aij,Bf(i,j))

　　(i,j)????

　　+

　　(i,j)?{1,???,M?1}??d(i,j)?{1,???,M?1}??d(?f((i,j)?(1,0))?(f(i,j)?(1,0))) +

　　d(i,j)??{1,???,M-1}(i,j)???{1,???,M-1}d??(f((i,j)?(0,1))?(f(i,j)?(0,1)))

　　Goal:minfc(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 identity 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 following

　　Question: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 definition 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 dgconstant, the minimum is given by the identity mapping and for ddconstant, the minimum can be determined by sorting 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 image matching in general.We choose the matching problem of Uchida and Sakoe (1998) to complete the definition of the problem. 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 by choosing the functions f1,f2 as e.g.

　　?0,x?2,f1=id，f2(x)=step(x):=? M?M?(10G),x?2.

　　3. Reduction from 3-SAT

　　3-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={C1，,CK} on a set of variables X={x1，xL} such that each ckconsists of 3 literals for k=1，K .Each literal is a variable or the negation of a variable.

　　Question:Is there a truth assignment for X which satisfies each clause ck, 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 and the set of variables X .Two vert ices ckand x1are adjacent iff ckinvolves x1orxL.

　　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 formulaФ 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 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 components

　　For the reduction from 3-SAT we need 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,crossings, 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 the‘background ’color.

　　We will depict possible 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 displacements

　　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 symbols◇and□. Given 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 different 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. one 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 and 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 the‘true’truth value, if the displacement is 1 pixel in the direction of the connector and as carrying the‘false’ truth value, if the displacement is -1 pixel in the 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 2