不變矩陣視覺模式識別英文文獻翻譯

1、visual pattern recognition by moment invariantsming-kuei hu, senior member, iresummaryin this paper a theory of two-dimensional moment invariants for planar geometric figures is presented. a fundamental theorem is established to relate such moment invariants to the well known algebraic invariants. c

2、omplete systems of moment invariants under translation, similitude and orthogonal transformations are derived. some moment invariants under general two-dimensional linear transformations are also included.both theoretical formulation and practical models of visual pattern recognition based upon thes

3、e moment invariants are discussed. a simple simulation program together with its performance are also presented. it is shown that recognition of geometrical patterns and alphabetical characters independently of position, size and orientation can be accomplished. it is also indicated that generalizat

4、ion is possible to include invariance with parallel projection.i. introductionrecognition of visual patterns and characters independent of position, size, and orientation in the visual field has been a goal of much recent research. to achieve maximum utility and flexibility, the methods used should

5、be insensitive to variations in shape and should provide for improved performance with repeated trials. the method presented in this paper meets all these conditions to some degree.of the many ingenious and interesting methods so far devised, only two main categories will be mentioned here: 1) the p

6、roperty-list approach, and 2) the statistical approach, including both the decision theory and random net approaches 1. the property-list method works very well when the list is designed for a particular set of patterns. in theory, it is truly position, size, and orientation independent, and may als

7、o allow for other variations. its severe limitation is that it becomes quite useless, if a different set of patterns is presented to it. there is no known method which can generate automatically a new property-list. on the other hand, the statistical approach is capable of handling new sets of patte

8、rns with little difficulty, but it is limited in its ability to recognize patterns independently of position, size and orientation.this paper reports the mathematical foundation of two dimensional moment invariants and their applications to visual information processing 2. the results show that reco

9、gnition schemes based on these invariants could be truly position, size and orientation independent, and also flexible enough to learn almost any set of patterns.in classical mechanics and statistical theory, the concept of moments is used extensively; central moments, size normalization, and princi

10、pal axes are also used. to the authors knowledge, the two-dimensional moment invariants, absolute as well as relative, that are to be presented have not been studied. in the pattern recognition field, centroid and size normalization have been exploited3-5 for “preprocessing.” orientation normalizati

11、on has also been attempted5 .the method presented here achieves orientation independence without ambiguity by using either absolute or relative orthogonal moment invariants. the method further uses “moment invariants” (to be described in iii) or invariant moments (moments referred to a pair of uniqu

12、ely determined principal axes) to characterize each pattern for recognition.section ii gives definitions and properties of two dimensional moments and algebraic invariants. the moment invariants under translation, similitude, orthogonal transformations and also under the general linear transformatio

13、ns are developed in section iii. two specific methods of using moment invariants for pattern recognition are described in iv. a simulation program of a simple model (programmed for an lgp-30), the performance of the program, and some possible generalizations are described in section v.ii. momentsand

14、algebraic invariantsa.a uniqueness theorem concerning moments in this paper, the two-dimensional (p + q)th order moments of a density distribution function (x,y) are defined in terms of riemann integrals as if it is assumed that (x,y) is a piecewise continuous therefore bounded function, and that it

15、 can have nonzero values only in the finite part of the xy plane; then moments of all orders exist and the following uniqueness theorem can be proved.uniqueness theorem: the double moment sequence mpq is uniquely determined by (x,y); and conversely, (x,y) is uniquely determined by mpq .it should be

16、noted that the finiteness assumption is important; otherwise, the above uniqueness theorem might not hold.b. characteristic function and moment generating function the characteristic function and moment generating of (x,y) may be defined, respectively, as in both cases, u and v are assumed to be rea

17、l. if moments of all orders exist, then both functions can be expanded into power series in terms of the moments mpq as follows:both functions are widely used in statistical theory. if the characteristic function (u,v) which is essentially the fourier transform of (x,y) is known, (x,y) may be obtain

18、ed from the following inverse fourier transform, the moment generating function m(u,v) is not as useful in this respect, but it is convenient for the discussion in section iii. the close relationships and differences between (u,v) and m(u,v) may be seen much more clearly, if we consider both as spec

19、ial cases of the two-sided laplace transform of (x,y),where s and t are now considered as complex variables.c. central momentsthe central moments upq are defined as(8) whereit is well known that under the translation of coordinates,the central moments do not change; therefore, we have the following

20、theorem.theorem: the central moments are invariants under translation.from (8), it is quite easy to express the central moments in terms of the ordinary moments. for the first four orders we havefrom here on, for the simplicity of description, all moments referred to are central moments, and upq wil

21、l be simply expressed asand the moment generating function m(u, v) will also be referred to central moments.d. algebraic forms and invariantsthe following homogeneous polynomial of two variables u and v, is called a binary algebraic form, or simply a binary form, of order p. using a notation, introd

22、uced by cayley, the above form may be written asa homogeneous polynomial i(a) of the coefficients is an algebraic invariant of weight w, ifwhere ap0，a0p are the new coefficients obtained from substituting the following general linear transformation into the original form (14).if w = 0, the invariant

23、 is called an absolute invariant; if w 0 it is called a relative invariant. the invariant defined above may depend upon the coefficients of more than one form. under special linear transformations to be discussed in section iii, may not be limited to the determinant of the transformation. by elimina

24、ting a between two relative invariants, a nonintegral absolute invariant can always be obtained.in the study of invariants, it is helpful to introduce another pair of variables x and y, whose transformation with respect to (16) is as follows:the transformation (17) is referred to as a cogredient tra

25、nsformation, and (16) is referred to as a contragredient transformation. the variable x, y are referred to as covariant variables, and u, v as contravariant variables. they satisfy the following invariant relation the study of algebraic invariants was started by boole, cayley and sylvester more than

26、 a century ago, and followed vigorously by others, but interest has gradually declined since the early part of this century. the moment invariants to be discussed in section iii will draw heavily on the results of algebraic invariants. to the authors knowledge, there was no systematic study of the m

27、oment invariants in the sense to be described.iii. moment invariantsa. a fundamental theorem of moment invariantsthe moment generating function with the exponential factor expanded into series form isinterchanging the integration and summation processes, we haveby applying the transformation (17) to

28、 (19), and denoting the coefficients of x and y in the transformed factor (ux+vy) by u and v, respectively, or equivalently by applying both (16) and (17) simultaneously to (19) we obtainwhere is the absolute value of the jacobian of the transformation (17), and ml(u, v) is the moment generating fun

29、ction after the transformation.if the transformed central moments , upq are defined asthen we havein the theory of algebraic invariants, it is well known that the transformation law for the a coefficients in th algebraic form (14) is the same as that for the monomials, xv-ryr, in the following expre

30、ssion:from (19), (20), (21) and (23), it can be seen clearly that the same relationship also holds between the pth order moments and the monomials except for the additional factor 1/j. therefore, the following fundamental theorem is established. fundamental theorem of moment invariants: if the algeb

31、raic form of order p has an algebraic invariant,then the moments of order p have the same invariant but with the additional factor 1/j, this theorem holds also between algebraic invariants containing coefficients from two or more forms of different orders and moment invariants containing moments of

32、the corresponding orders.b. similitude moment invariantsunder the similitude transformation, i.e., the change of size,each coefficient of any algebraic form is an invariantwhere 01 is not the determinant. for moment invariants we haveby eliminating ol between the zeroth order relation, and the remai

33、ning ones, we have the following absolute similitude moment invariants:c. orthogonal moment invariantsunder the following proper orthogonal transformation or rotation: we havetherefore, the moment invariants are exactly the same as the algebraic invariant,s. if we treat the moments as the coefficien

34、ts of an algebraic formunder the following contragredient transformation:then we can derive the moment invariants by the following algebraic method. if we subject both u, 0 and u, v to the following transformation:then the orthogonal transformation is converted into the following simple relations,by

35、 substituting (36) and (37) into (34), we have the following identities:where ipo, . . . , i, and igo, * . . , i&, are the corresponding coefficients after the substitutions. from the identity in u and v, the coefficients of the various monomials up-rvr on the two sides must be the same. therefore,t

36、hese are (p + 1) linearly independent moment invariants under proper orthogonal transformations, and =ei which is not the determinant of the transformation.from the identity of first two expressions in (38), it can be seen that ir,p-r is the complex conjugate of ip-r,r ,it may be noted that these (p

37、+1). is are linearly independent linear functions of the us, and vice versa.for the following improper orthogonal transformation, i.e., rotation and reflection:similarly, we have andwhere ip0,，i0p and ipo,，i0p are the same as those given by (40).the orthogonal invariants were first studied by boole,

38、 and the above method was due to sylvester6.d. a complete system of absolute orthogonal moment invariantsfrom (39) and (43), we may derive the following system of moment invariants by eliminating the factor ei:for the second-order moments, the two independent invariants arefor the third-order moment

39、s, the three independent invariants area fourth one depending also on the third-order moments only isthere exists an algebraic relation between the above four invariants given in (45) and (46). the first three given by (45) are absolute invariants for both proper and improper rotations but the last

40、one given by (46) is invariant only under proper rotation, and changes sign under improper rotation. this will be called a skew invariant. therefore it is useful for distinguishing “mirror images.”one more independent absolute invariant may be formed from second and third order moments as follows:fo

41、r pth order moments, p= 4 we have p/2, the integral part of p/2, invariantsif p is even, we also have and also combined with (p - 2)th order moments, we have p/2 - 1 invariantscombined with second-order moments, if p = odd we haveif p = even7,therefore we always have (p + 1) independent absolute inv

42、ariants. by changing the above sums into differences, we can also have the skew invariants. all the independent moment invariants together form a complete system, i.e., for any given invariant; it is always possible to express it in terms of the above invariants. the proof is omitted here.e. moment

43、invariants under general linear transformationsfrom the theory of algebraic invariants under the general linear transformations (17), it is known that the factor a is the determinant of the transformation. for linear transformations, j is also the determinant. for simplicity, let a, b, c and a, 6, c

44、, d denote the second and third order moments, then we may write the following two binary forms in terms of these moments asfrom the theory of algebraic invariants, we have the following four algebraically independent invariants,of weight w = 2, 6, 4 and 6, respectively. for the zeroth order moment,

45、 we havewith the understanding that 2 = j2, the following four absolute moment invariants are obtained,there also exists a skew invariant,8 i5, of weight 9 depending on the moments a, b, c and a, b, c, d. this also may be normalized aswhere /j indicates the sign of the determinant. this invariant co

46、ntains thirty monomial terms, and it is not algebraically independent. by counting the number of relations among the moments and the number of parameters involved, it can be shown that four is the largest number of independent invariants possible for this case. various methods have been developed in

47、 finding algebraic invariants, and many invariants have been worked out in detail. in case extension to higher moment invariants are required, the known results for algebraic invariants will be of great help.iv. visual information processing and recognitiona. pattern characterization and recognition

48、 any geometrical pattern or alphabetical character can always be represented by a density distribution function (x,y), with respect to a pair of axes fixed in the visual field. clearly, the pattern can also be represented by its two-dimensional moments, mpq, with respect to the pair of fixed axes. s

49、uch moments of any order can be obtained by a number of methods. using the relations between central moments and ordinary moments, the central moments can also be obtained. furthermore, if these central moments are normalized in size by using the similitude moment invariants, then the set of moment

50、invariants can still be used to characterize the particular pattern. obviously, these are independent of the pattern position in the visual field and also independent of the pattern size.two different ways will be described in the next two sections to accomplish orientation independence. in these ca

51、ses, theoretically, there exist either infinitely many absolute moment invariants or infinitely many normalized moments with respect to the principal axes. for the purpose of machine recognition, it is obvious that only a finite number of them can be used. in fact, it is believed only a few of these

52、 invariants are necessary for many applications. to illustrate this point, a simple simulation program, using only two absolute moment invariants, and its performance will be described in section v.b. the method of principal axesin (39) and (40), let p = 2, we have the following moment invariants,if

53、 the angle 0 is determined from the first equation in (58) to make u11=0, then we havethe x, y axes determined by any particular values of 0 satisfying (59) are called the principal axes of the pattern. with added restrictions, such as u20u02 and u300, can be determined uniquely. moments determined

54、for such a pair of principal axes are independent of orientation.if this is used in addition to the method described in the last section, pattern identification can be made independently of position, size and orientation.the discrimination property of the patterns is increased if higher moments are

55、also used. the higher moments with respect to the principal axes can be determined with ease, if the invariants given by (39) and (40) are used. these relations are also useful in other ways. as an illustration, for p = 3 we have the two remaining relations, which are the complex conjugate of these

56、two, are omitted here. if and the four third moments are known, the same moments with respect to the principal axes can be computed easily by using the above relations. there is no need of transforming the input pattern here. in the above method, because of the complete orientation independence prop

57、erty, it is obvious that the numerals “6” and “9” can not be distinguished. if the method is modified slightly as follows, it can differentiate “6” from “9” while retaining the orientation independence property to a limited extent. the value of is still determined by(59), but it is also required to

58、satisfy the condition 45 degrees. the use of third order moments in this case is also essential.if the given pattern is of circular symmetry or of n-fold rotational symmetry, then the determination of by (59) breaks down. this is due to the fact that both the numerator and the denominator are zero for such patterns. as an example, assume that the pattern is of 3-fold rotational symmetry, i.e., if the pattern is turned 2/3 radian