Pattern Linguistic Analysis Invariant for Plane Transformations

FATTER!; 1..I!:Gt.;IS:IC ANALYSIS Il\VARIAN':' FOR PLANE TRAJiSFORl·:A':'I or;s

J. C. Simon and A. Checroun

Institut de Programmatior. 9, quai Saint Bernard PARIS 5e

Pattern analysis using syntactic methods is discussed briefly to introduce the ideas of the linguistic nature of the attritutes and of possi· ble invariance properties versus usual geometrical trans format ions.

A linguistic operator invariant for projec­ tions fro~ plane to plane is proposed and applied to the analysis of point patterns X. From knowled ge of the operator "result" or "attribute", it is possible to obtain tte convex envelope, reconsti­ tute X, compare X to another pattern X' and more generally, to obtain the possible co~~or. subpat­ terns. This last process shellS that a threshold exists, under wtich a pattern comparison is not reliable.

Linguistic operators invariant for plane simi­ larities are alsc considered.

§ 1 . n;:·RODUC~IOJ;

I. 1. FOR:-IALIZATIOJ; OF !'A~TERH RECOGIHTIOJ; OPERA~ro:; s

Except f or some very simple recognitions,many "recogr,iti on levels" have t o be distinguished in a pattern recognition preble~.

Recognition operations have t o be performedto get fror.-1 one level to the next. Host of the time, they may be described under a comrnor. forn.aliza­ tion :

• a . Let a patter:; X be a set of "primitive" pat­ terns, eacl'. of which has a~ to which are associated nu.,.,erical values .
• One or more analysis operators & operate on X through algorit~~s ; the~ of & is uX .
• c . A recognition decision is performed by compa­ ring lly with information previ o'..lsC.y stored. If this pnase is successful, a pattern "feature" is extracted. This feature has a ~ ; nurr.eri cal values may be associ ated with it.

The recognized features are the nev primitive patterns. Their set is the pattern on vhich the operators of the next level will operate.

~his scheme is valid obviously for the firs t level extraction of simple features where X is the set of samples obtained through a measuring instru ment such as a~ optical or acoustical device. Most of the time, the operators & are linear operators. For example, let X be a one dimensional "signal", i is the name of the primitive measure or sample, x . the numerical value associ ated vith it.

1 Let 8. be t!·,e operator such that the result p j=q The operators ~ are defined by the set of numerical.values (a 1 ,a.· · :·a ). The result uf is the numer1cal value obta1ne8 by a translat1or, cf p units and a scalar multiplication. Digital fil­ ters, neurone nets and Perceptrons make use of such linear operators.

The recognition decision is taken according to the numerical value of ~· Usually if ui is greater than a threshold u 0 , the feature corres­ pending to & is recognized.

Such a process is easi ly extended to images, i.e. two dimensional signals .

1.2. SYNTACTIC OR LINGUISTIC OPERATORS

It has been realized for quite a time that li near operators alone are not able to take into ac count structural relationships in patterns.

At the beginning of the 1960's a number cf au thors such a s Eden ( 1), (2), Minsky ( 5 ), Narasimhan ( 6), Kirsch ( 4), advocated a "description-prcces­ sing" of pattern, thus starting a ne;; "syntactic" approach to pattern recogn ition problems of higher coll'.plexity. Quoting FU and SWAIJ; (3), whc recently reviewed the state of the art :

"Syntactic pattern recognition is an att er.-.r·­ to adapt the techniques of formal language tt,eory which provides both a notation (grammar) and a~. analysis mechanism (parsing) t c the probl em of re presenting and analysing patterns ... Syntactic analysis can proceed only if a gra~atica: modt: for the data generation and I or ana:ysis pro2ess can be f ormul ated (Tr.is does not necessari:y ir.-.­ ply that the data is actually generated by a me­ chanism which opera~es ir. the sar.1e ....,ay a~ the ;. .. :> ­ del ). A related practical preble~ is the aevelo~­ ment of efficient analysis proced~re s ba~e~ �~ the grammatical model. 'The availa'::j,e li:ter&:c:re concerning syntactic pat terr: rec og~.:: i x. deal~ a: most excl usively "'i th the fcrn:ulat ior. of gr!i!:'_-cat i cal models , although the develcpr.-,ent of ana.lysi.:o: algorithms is currently recei ving more at t er.t ior · .'.'

This ne;; approach is a subject of considerat~ interest among pattern recognitio~ specialists. ~evertheless, the practical res~lts i~ the a~a:y­ sis field de not see~ ur t o the expectatic~s .

In fact s:,'ntactic techniques are successfo.:2., says Kirsch, only if the generative gramma:- is fully kno-.m. But, as for natural lang·c1ages, there are some do·..tbts about the exi st ence cf sJc!·. "CHOHSKY-like" grammars for images, eve~, ;.·;tf. the improvements provided ·oy the "wet. gran.,-.a r s" prcpc sed by Pfaltz and Rosenfeld (7) .

We would like to retain two feature s of the syntactic approach :

• Give up the interpretation cf the processei quantities as numerical values, ccnsi:ie r tr.er.-. rather as words of a langua1;e wit!; l.'hi cL nu..,-.e rical values may be assoc iated.
• Try to find "rules" valid f or a large cl11ss of pat terns.

Accordingly, cor.1ine back to cur forr.!il i ~::-. , l.'e propose t o consider analysis operator s t cf a li~ g~isti c and invaria~t nGture

• The result ~ is to be one or more words bui lt on the alphabet consisting of the names of tr.e primiti ve patterns. For this purpose a formal generative grammar is not absolutely necessary, as long as an algorithm giving an appropriate result can be found. This algori­ thm, called the analysis operator, should be implemented, of course, by a computer program. The pattern X will be the variable data set of this progr~.
• The result ~ is to be invariant under some transformations of the set X, corresponding to some geometrica: transformations of the analysed o~j ect. This "ir.variance concept" un· derlies the syntactic pattern methods, though pr~vious authors do not seen to emphasize its relevance .

The recognition decision will be taken by com paring the~ with some stored information (1.1. phase c). We will see lat er ex~ples of how th1s phase can be implemer.ted.

I. 3. RE.V.AP.KS

1. O:.~r formalism can te compared witt: the one pro pooed by ·Fu and Swain ~ - ; . Fer thee a 3eneralized ~:z-:-j :a:::tic Fcma:is:t (CSF ) :.1til.izes :

• A ~eneralized Syntacti; ~le~ent ( ~SE ) , which is a construct consis: ir.g of t··o parts : a :1a ~e and an attrit':lte lis: , · ... ·!'".ich is a set ;-r-­ :::cdifiers or variable properties.
• A �e~eralize~ Syntactic Frc iucticn (GSF) , whici: is a rule specif';ing how a syntactic e~ement is composed fro~ or generateE ether :yn:actic elements. Usual ly the syntactic el< ments generated are "r=1ore primitives".

7hus, a set X cf primitive patterns can be co~pared tc a GS£, an analysis operator & to a GSF with the difference t hat now the res·.J.lts are "less primitive" element$, _ "res:..:.lt" and''attrib·..lte'' being equivalent wor ds.

Our terminology see:!:S :~:e re general, ceing also appropriate for the filtering or sifting proces­ ses . One could in fact assert ti:at in terms of tr.e cor.-.p"J.ter states there is no basic difference, only the se~antic differs.

·~o st ress the fact that no generative grammar i s implied by our operators , we ;;ould prefer to call them "linguistic" rat r.er than syntactic.

2. An instr=ent provides numerical results or sarr.pl es ; a name is given to each sample and a n·..;.'!lber of· numerical valu~s. For exar.1ple, in a reti na the cell of name i gives an intensity of numeri cal value z . . The coordinates o f cell i are the nu 1

• merical values xi, yi. Thus an "elementary measu-

re" is defined by i, x., y., z . . 'l'he set of these meas·..:res is the first ~att~rn, 1 each "elementary I:leas:.:.re" being a "primitive pattern". This level will te called the first level. It is already a ''fea:~J.re level", if Wle consijer that the "ele~en­ tary ~easures · " are the "results" of some "physical operators". But usually we cannot modify the qua­ lities of these physical operators. This proper­ ty could be used as a way to define the "outer vorld" or "universe" ...

The second level is reached, most of the ti­ me by the use of linear operators or filters. Th~ se simple operators have no invariance properties They are thus successful only for invariant sub­ patterns. Elements of lines, strokes or line eros sings are examples of such subpatterns invariant for many transformations ; thus may be explained the limited success of ·~erceptron-like machines" for complex patterns, composed of these simple features.

1. The object of this paper is to propose some "invariant linguistic operators" usually effecti­ ve f or reaching the next level. They apply to two dimensional signals or images. The envisioned geo metrical transformations are plane to plane tran~ formations . One is for plane projections, the other for plane similarities.

§II. LI:IGUIS':'IC ANALYSIS OPEP.ATORS HIVARIANT FOR PLANE PROJECTIONS

II. 1. DEFINITIONS

Let the pattern be composed of "primitives" of names A 0 , A 1 , A 2 , ··. Ai, .. . An, to which are associated numerical values (x 0 ,:, 0 ), ... (xi,yi ) ... These primitives may be the " features" of the se· cond level. The numerical values xi, yi are the coordinates of tne "center" of features A .. Let these "points Ai" be in a plane n. 1

Let us establish one of them as privileged, for example. Ai A 0 defines a· di rection. Starting from this direction, let us r otate a vector around Ai in a given manner. This vector will en· counter the other points A. in a certain order.

J Noting this order we can o~tain an n-word on the alp!;abet {A) of the name s , starting by A. 1

From all the points except A 0 , a word such as ui may be obtained. Let us name UX this set of n words of n letters.

A projection from plane IT to plane IT' trans­ forms the word A 0 , A 1 , A 2 ... An into A 0, Al, A2 ··. A~. It is easily verified that the set of n words UX,obt ained from the new pattern X' by the same algorithm, is derived from UX by substituting A! for A .. 1 1

Thus the operator & implemented by the propo sed algorithm is invariant for a plane proj ection . It is easy to verify that a plane simi larity, a rotation for example, does cot modify the n words en her.

Remarks

l. Let the projection from plane to plane be a "parallel projection", i.e. the center of projec tion be at infinity. Let G be the center of gra­ vity of the primitive points Ai, which may be weighted by numerical values zi.

G', the projection of G, is still the center of gravity of the projected points. The quality is invariant for the proposed transformation. Thus for these parallel projections, G may be selected a7 the "privileged n + l point" A 0 of an n-points pl.cture.

2. Let A 0 be at infinity. This means that the starting direction of the rotating analysis vector is the same for all the n points Ai. Let us consider the projections from one plane to another kee ping at infinity the projection of A 0 · In other words, this means that A 0 is the point at infinity on the intersection line of the two considered pla nes. For the new plane, the starting direction of the rotating analysis vector is the same for all projected points. It is the projection of the star ting direction in the former plane. We will res - trict ourselves to such transformations in t~pro posed application examples.

II.2. PRACTICAL APPLICATION TO IMAGES

Let us take for the common starting direction of the rotating vector, the direction of the x axes (horizontal right). The rotation sense is taken counter clockwise.

Let {A 1 , A 2 , ..· An} be the alphabet of names of the primitives. The partial result obtained from pojnt Ai will be written down as

n words such as u. form an n X n matrix : the "result Ux". Thi~ result is inva:z:iant for the

envisioned plane projections.

Any monotone increasing function of the vector angle results in obtaining the u .. Let q be the size of the computer register inl.which is stored the angle of A. A. with the horizontal axes. Let l. J x andy be the A. A. projections on the horizon­ J. J tal and vertical axes, An easily computed two 1 s complement function .P (A .lA . ) is

J l.

Such a function ~ covers the available compu· ter numerical range. It orders the angles with a very high discrimination.

N. B. This precision may be superfluous ; as will be seen later, it may be useful to decide. that t'Wo points Px· Ae are seen "in line" from a point Ai, in other words that the angles of vectors Ai ~ and A. A with a fixed direction are the same. ·x J. e This is achieved by reducing the function op pre­ cision.

The figures 1-X and 1-Y display ill'.ages X and Y of 8 primitive points. A, E, ... H. The corres pending results are given by Fig. 2-X and 2-Y.

The Y image has points "in line". This is re­ corded in the 8 x 8 matrix by setting a number after the letter. For instance E and Care in li· ne with A, also H and F ; C and A are in line with E, F and A with H, cf. Fig. 2-Y.

l

:,

t

"

t'

l

r, t1

A

h

c

Fig. 1-Y

f-

il

P.err.arks

1. A change in t he ~ ang:llar ong1n of the rotating ar,a:!.ysis vector usually transform UX : a :ircdar perm·..::ation of the n - 1 letters in a li ne af:er <;he first may occ'c.lr.

Ar. image r otation i n the plane would int r od:.: ­ ce such perm'c.ltations. The considered operator is no<; r~tation invariant. Why then use such an ope · rater rather than the more general one introd'c.lced? Because, ty compar ing two unknown figures, the cor :e s ponder.~e betw~en the poi ~ts A 0 has to be kno~ ~n genera~ thls 1s not feas~bl e.

!he proposition of taking the center of gravi ty as the point A 0 is quite interesting , but it

restricts the plane ~rejections to parallel pro - jecticr.s. On the other hand by us ing the parallel origin direction vector we wi ll te able t o c om~a ­ r e fig·.:.res with different nU!!lber of primitive points and al so to obtain the convex envelope. 7his wc;.W.d net be possible by using the "center of gra·1ity" origin :nethod. Anyway, the invar iance to rotation may be of real value for some proble~s and this process is wor th studying al so .

2. If A 0 1s at infinity, the image can be scanned from A 0 , in the saJile sense that the r otating vee­

tor s ' sense. Here this scanning i s made by a hori zcnt al :!.ine, the ordinate of which dec reases from +«>to - oo. Tr:·..:s :he n primi tive points are put in a certain order. We adopt t his orde r for the first celu::u; of the n X n mat rix UX , which is then ·.miquely defined ; cf . Fig. 2-X and 2-Y.

II.3. SGME PROPERTIES DEDUCED FROM UX

The UX matrix, invariant for plane projections preserving the horizontal direction, is used t o re cognize l arge pattern classes.

Already some properties of t he analysed image may be deduced from VX alone . For inst ance it is

possible to state the sense cf any three pointed triangle or t o decide if any four pointed quadri­ l ateral is convex or not.

The convex envelope

A most interesting property is the abil ity to find the convex envelope , i.e. the points on

A b ,; [ lC.2HlFl il tl fl ,, 1: H f- c t.l [) A h c ~ !; F '1 c A b ... t H t' t) F q A c ~ f ~ H E I ) c 1117" ( , H ,: G 1- 1: f c .\ r H H " F 1 t..2C !.'· 1: r "

Fig. 2-Y

which a convex polygon can be built such that all the other image points are inside this polygon. Let two points ~ Ae be such that :

1. In the line starting at Ak' called the~ line the point immediately after Ak is Ae.

b. The Ae line t erminates with ~·

It is easy to demonstrate that Ak and Ae are elements of the convex envelope, and that Ae imme diately follows ~ on the envelope for the adop­ ted rotating sense.

The next point Am on the enve l ope is such that it is the point following Ak in the Ae line. If Ak is the last point in the Ae line, Am is the second (c ircular permutation property) .

All the envelope points are obtained through this algorithm, continuing so as to find again the first point Ak.

For instance, going back to the eight primi ti ve points image of Fig . 1-X, the UX of which is displayed in Fig. 2-X , it is very easy to ob~.ain any UX corresponding t o any ~artial image, dedu -

ced from t he or iginal image by suppressing a num­ ber of points. Fig. 3 gives the en·:elopes of ima­ ges deduced f r om Fi g. 1-X. One line gives the points , the line underneath the con·1ex envelope points. For the tot al image A E .. . H, the envelo­ pe is C A B G H F.

S~lected points o f Fig. 1-X , foll owed by the con ­ vex envelope points.

Rebuilding the image from UX

A matrix UX ' being the result of the analysis operator &, is it possible to obta in again the primitive image X from UX ?

Let us recall that the interest of UX is not an information reduction from the primitive infer mation of one image, but that a UX is the same for a class of patterns, modulo a "geometrical" transformation e, such as has been envisi oned.

Even more, some image "deformations" do not modify Ux. Let us cons ider a pattern X of n points, the n (n- 1 ) half-lines joining two points A. , A. , the n horizontal half-lines joining a l J point Ai with the point A 0 at infinity. If none 2 . . . of these n half l1nes crosses an 1mage po1nt ~ during a "deformation" transform .II., obviously the result UX will ·be unchanged. Such a deformation .II. may alter the primitive pattern shape considera­ bly. Thus any image rebuilt from UX may differ from the original image X not only by a transformation e, but also by a deformation .II.. The convex envelope of any subpattern may be obtained from UX. This facility is used to rebuild a pattern X' from UX . The envelope points are put evenly on a circle in their order. The matrix UX indicates the regions, defined by a number of straight half-lines, where the other points should be. The set of these other points is ordered in order of decreasing freedom. The first points in this order, thus those with the minimum number of constraints, are put first at the barycenter of the surface where they should be set according to Ux: An impossibility may occur before the set is exhausted . The process is then started again after a random variation of the positions of the points.

f.

~ ·.

~·

~ · Cli' \lllt.l Ji · . J, , I'

f I ; ·. '·· S

/1

t

..

r.

.I

:.

J

'·

L

(,

L

Though we are quite convinced t hat this is not the best idea, successive iterations of thi s process usually increases the number of points that can be disposed of according to Uv.

·'

,.

,,

.,. ~

,, ..

.,

· ·

·

·

*

·

~

·:~

:,,

,..

, .

..

Fig. 4' shows the reconst:i:tutior. of the pat­ tern in Fig. 4. All but point F are set of a total of thirteen. The convex envelope is A C J M I B. The matrix UX does not give any indication of the envelope shape, the ignorance of which leads then to an important deformation of the two patterns.

Fig. 51 gives the reconstruction of Fig. 5 pat tern from UX. Out of 38 points, only 30 can be

set. This number seems a practical limit.

Though it is interesting to try to rebuild a pattern from UX' it is not at all the aim of the process, which is principally for pattern identi­ fications. Nevertheless it shows how different two patterns with the same operator attribute UX may be.

II.4. PATTERN IDENTIFICATION FROM UX

The identification of two patterns X andY, having the same number n of points, is quite sim­ ple.

Let

The two patterns X andY are "equivalent",i.e. may be deduced one from the other by a transfor­ mation e and eventually a deformation ~. if there exists a bij ective application f : A. ~B . l J

suer. that UX is r- 1 : B . ~ A .. transformed in Uy, and inversely : J 1

The application is defined son of the first columns of UX readily by compari­ and Uy· Then the

verificatio~ of correspondence is made on the ma­ trix lines. For instance, let X and Y be the pat terns of Fig. 1-X and 1-Y. _ 1

The application f and f are

Using the defined r, a complete corresponden­ ce c~not be established between these two lines. We decide that these patterns are not equivalent.

If points are "in line", they may be exchanged during the identification operation.

The discrimination between two patterns of n points is quite high. It depends of course on the ang·JJ.ar precision·, which may be reduced : two points A. , A. of a pattern are "in line" from a 1 J point ~ if the angle (A. Ak, A. A ) is smaller ·lt 1 1 e than f in absolute value. Thus classes are defined in the Ai line. Points may be interchanged inside a class. A similar process has been tested for the distance operator (cf . paragraph III and J. C. Simon, A. Checroun and C. Roche (9), (10)) we call it "parenthesizing".

Finding common equivalent subpatterns

Let X and Y be two patterns, lxl and IYI be the number of primitive points. The analysis ope­ rator & provides UX and Uy. From the knowleqge of UX and UY is it possible to find two subpat­ terns Z and Z' such that Z ~X and Z' ~ Y, izl · iz'l, and f: Uz ~ UZ" r- 1 : U7., ~ Uz1(Jin

other words, by suppressing a number of points in each pattern is it possible to find two subpat terns satisfying the former correspondence algo­ rithm.?

Let us; show the process on an example. Let X be a pattern of 6 points, Fig . 6-X; Y be a pat­ tern of 8 points, Fig. 6-Y. Let us examine first if X can be found entirely embedded in Y, (thus X = Z).

Refering to UX and Uy, the correspondence of certain points is obviously impossible (*). For example, FX' Dy.

Let us test the possible Y points correspon­ ding to the point CX. From the first column, only Ay, By, Cy may correspond. We shall see that By cannot be a CX correspondent.

If f : C ~ B, B should be found in all five rectangular domains of Uy displayed below : the B position in uy has to be close to the c position in UX. In the chosen example B is only in four do mains and thus B cannot be a C correspondent by r.

• (*) When there is some doubt about the points' origin, an index X or Y will state the origin from the X or Y pattern.

Let us ex~ne to see if C may be a B corres­ pondent by r- : B ... C ; the point C should be ir. five of the seven rectangular domains. As the po,nt C is in si¥ of these domains, B may be a r- correspondent of C.

After this example, let us give the general conditions, and let UX(i, j) be a letter of UX, Uy(k, 1) be a letter of UY.

1. First column correspondence

Sup(1, lzl - lxl + i)~ k ~ inf( IYI,IYI - lzl + i) ( lzl is the number of points of the possible par­ tial pattern).

2. An X point exists also in other columns of UX' let IJ and v be its coordinates, such that UX(i, 1) · UX(IJ, v). Each point UX(IJ, v) determines a rectangular domain in UY' defined by t and s The conditions on t are :

And s must satisfy

Sup(2, IZI - lxl + v) <; s <; inf( IYI,IYI - Jzl + v) lx l - 1 such domains are defined in Uy . r : UX(i, 1) ... Uy(k, 1) is possible if Uy(k, 1) is at least in lzl - 1 of these domains.

Correspondence matrices MZ can then be obtained. Let us represent them for the example. A"o " signifies that at least one of the correspondences is impossible, a·1-that both are possible according to the preceding rules.

~ shows that the correspondence is not possible for any Z, Z' such that lzl = 6.

Many sets of 5 points in X and Y are candida­ tes for correspondence. Nevertheless this corres­ pondence has to be verified also by the algor i t hm described for two patterns having the same number of points.

For instance F C B D A of pattern X is equiva lent to the Y subpatterns G B E C D, G A E C D, G B E H D, G A E H D, B E H C F, G B H C D, G A H C D, G B E F D.

Of course the process may be applied to a pat tern X itself to find all the equivalent subpat ­ terns Z C X. For example in the pattern X of Fig. 6-X, F C B D A and F C E D A are equivalent .

Let X and Y be two patterns, chosen at random but having a fixed number of points : Jxl = n 1 , IYI · n 2 . It is interesting to use the process t o

find the possible equivalent subpatterns . A sharp threshold in the number z of equivalent subpat­ tern points is found experimentally . For instance, let n 1 · 6, n 2 · 8. Table I gives the test results ; the first line gives the number z of sub pattern points.

The five other lines give the number of equi­ V4lent z subpatterns for five different couples of random patterns X, Y.

7able I , n 1 = 6 , n 2 = 6

If n 1 = n 2 = 10, out of o couples of random X, ~, r.c sut-pattern is fc ·z.d for z ~ 8. If z = 7, s·.:·q :atterns are focx1 only f :. r 3 couples o ~,;.t of ~ . I f~~ 7, many subpacterr.s are al~ays found.

4r. approximate value of! , average of z, is giver. by

:~is :-.as t c t e csr.:pa!"e C. ~ : · ... ·:-.at ..,e f .: 1 ..l.nd by :: :1ear !"'i:.te:"i:.g o f sa.::-.;::.e .: :; c :.s:; i~a.ges, cf . .._7 . C . .: i ~c :-. ar.d C:. ·: a::::.::.er e.;:;: ~8) . A s!'".a:-p : :-.:-eshs :::i exis:s ·..:.;.ie!" · ... ·:-.ic:. c::e ~a:.,r consi:ier t r. a.: the exa..-niried. pa:te!"!l is ":--. :: ise".

§:: r . A :.r:~� ~..! : ~:rc A::.~. :.;·.: :~ -:r ::::= . .:...:- :5. ::;·;A.R:A:;: r-: ~ sr~-~:::....;.nr:· r ::: :::

i.e: A 1 A 2 . .. An t-e t :-. e r. 11 :;:- : ir.ts" o f a pa": ­ :ern X as definej in §r: . 1. Fr~= one of these , Ai ~: r :. ~sta~:e, a;. order ~~ :~e re~ai ~i~g Ii - ~ ~ : : :-. :s =.a:; ·ue defined b:.· t !"~e euc lid:a:. ~i stances t e:~ee~ Ai and ot ter ~cints A ~ .

~e: v . te the w=ri ~ttai~ei tt~s l

~et vX te : r.e set cf t~e ~ ~o rds v . . This set l !::ay t e ordereJ. ar:::l t e re_rreser::e:i ty ar. r. X n ma­ tr i x as befcre. To i~tr2~~:e a~ c r1er on the po ~n:s Ai :r.emselves :any pr2cesses may te propose1. For instar.ce let G be the ce~ter 2 f gravity, :r.e poi nts Ai may be set in t r.e order of tr.eir i~ c reasi~g eucliiian dista~: e fro~ G. This o r der , wr.icr. then defines firs t cclu:"..r. of the rr.atrix VI., is ir.deper.dar.t c f si:::.ilari~ie s , as the wcrd vi it· se2.f. h:t, if ce:-tain pc ints are missing , this or­ d~r ~ay be al:ered by displac e~ent of t he ce~ter of ,;;ra;·ity. Ano t~.er ~sef ·~ or:ier or. the points Ai i s ct :ained ty s~eering a line paral le! : 0 a direc t: cn ; bt.~.t t~er. a r o:a:ion · .. :culd ind".lce a circ'.l.lar permutation on the lines of the-matrix VX.

III.2. COMPARISON WITH A FORMERLY PROPOSED METHOD

This operator has to be compared to ~hat al­ ready has been proposed, cf. J. C. Simon and al. (9) . ( 10) .

In that method all the distances bet~eeen t~o points of a pattern X ~ere ordered giving a uni­ que ordered set D. The reader is refered to the publication ( 10) for a detailed description of the comparison bet~een t~o patterns of the ~ number of points.

~defining a variable distance prec1s1on e, classes are introduced on the ordered set D. They are represented by "parenthesis". During the assignment algorithm betveen t~o sets D and D', letters can be taken indifferently inside a class. This method, called "parenthesizing", al­ lo~s some flexibility in the comparison bet~een t~o patterns. Let us summarize the results :

If e = 0 the assignment is generally impossi­ ble ; if e is large enough, the assignnent is undetermined. T-wo situati ons may arise :

(a ) If e < e1 assig=ent is impossible, If e1 ~ e ~ e2 assignment is ur.ique, If e2 < e assign:r.ent is undetermined.

It ) If e < e3

If e ;;;. e, assigmnent is irr.possitle , assigr.ment is ·.mdetermined.

In sit ua: ion ( a ) ' the two patterns are said t o be comEara'.Jle to the Erecisi on e1.

In situati on (b ) . the t~o patterns are said to te different.

e 1 is of an order of :nagnitude smaller than e 2 and e 3 , ~hich are of the same orC.er of magni­ tude. Again a threshold is found, above which a 1ecision cannot be taken ~ith security.

The "parenthesizing process" can also be in­ troduced for the ne~ operators proposed i n this paper. It ~ould introduce some degree of freedom in t he comparison, often necessary fro~ the very nature of the pa:tern "points". The proposed rr.e:hods are useful after the first level recogni tion ; then a "point " represents in fact the cen ­ ter of gravity of a detected characteristic fea ­ tu~e, thus it may vary to a certain extent.

A drawback of the first proposed ~ethod, cf . ( 10 ) , is that the compari son bet~een t~o pat­ terns of different numbers of points is not prac ­ t i cal. Agiic, accord.ing to the nature of the "points", it seems likely that t~o compared pat­ terns may have a di fferent nuober of points.

We believe that the opt.imum solution ~ill be found by a combination of the t~o ideas : compa­ rison of t~o patterns having a different number of points and vari able Erecision, thus parenthe­ sizing. The first performed experiments sho~ that a threshold exists and that it is a function of the angular or distance prec1s1on e and of th~ number z of the possible common subpattern. Under this threshold, comparison is not performed with security.

A pattern X being given and the ordered set D obtained, it is easy to deduce vX from D. The knowledge of vX alone does not allow obtaining D. Nevertheless it is easy to supplement vX for that purpose.

The reconstruction of a pattern from the know ledge of D or vX is possible and easi er than the reconstruction performed from the §II ~·

The pattern is obtained modulo a possible si­ milarity. Some deformations may also be introdu­ ced ; these deformations are usually much smaller than for the distance operators .

From t he VX results the search for common sub patterns may be performed with algorithms similar to those described in §II .4 . They will be publi­ shed later.

§IV. CONCLUSIONS

A generalisation of the analysis operators may be proposed. Let X be a "pat tern" made of n "elementary patterns",

To an elementary pattern of name Ai, quali fi­ cati ves xi, y i, zi ... may be associated. The ana­ lysis operator & delivers n attributes u. from X. l They are obtained with a real function .P (A . I A. ) J l defined with the A. and A. qualificatives. The J l n - 1 elementary pattern names are ordered in a way such that if .P (A. I A.) <.p (A_ I A.), A. is J l 'lt l J before A- in the word u. beginning by A. · A word 'lt l l ui defines an "order from Ai". Ordering the ele - men"ary patterns names by some other way, an n X n matrix UX is finally obtained. This matrix is usually invariant for many geometrical transforms tions of the image.

Comparison between two patterns X and Y is performed using the matrices UX and Uy·

Prospective remarks

1. From the words ui' partial order is induced on the set of the elementary pattern coupl es {A . A. }. From this order a "clustering hierar l J chy" in the sense of Jardine or Benzecri is obtained . Thi s hierarchy may be useful for comparing patterns.
2. Many .P (A. I A. ) functions may be used, par - J l ticularly distances, satisfying the usual distance criteria. For instance, if the Ai patterns have masses mi, then d2 . . d (A., A.) = _..!.J_ if the Ai are st ra: ght 1 J mi mj lines li of relative angle aij' then i .. 1. 1 . l J l 2 cos a .. l J et c .. .

Acknowledgement

The authors wi sh to acknowl edge the parti cipa­ tion of graduate students : Andre, Galland, Gelly, Renard.

REFERD'CES

• ( 1) M. Eder. "On the formalizat ion of Ha~d·ri ting". Proceeding of Sympos i a i:-. Applied math, 12, pp. 83-BE , A:: . Math . Soc., Providence, R. I., 1961 .
• M. Eden "Handwriting and Pattern Recog:;;. tion". IRE Trans. on Inf . Theory , !, pp. 160-166, 1963.
• (3 ) K. S. Fu and P. H. Swai n : "On syntactic Pattern Recognition". 3rd Symposia on Computers and Inf. Science, COINS 1969. Bal Harbour, Fla, Dec . 18-20, 1969.
• R. A. Kirsch : "Computer Interpretation of English Text and Picture Patterns " IEEE. Trans. on Elect. Computers, EC-13, pp. 363-376, 1964.
• ( 5) M. Minsky : "Steps towards Artifid.al Intelli gence". Proc. IRE, .!!.2., # 1, Jan. ~961.
• ( 6) R. Narasimhan : "Labeling Schemata and Syntac tic Descriptions of Pictures", In formation and Control, 7, pp. 151179, 1964. -

1. J. L. Pfalz and A. Rosenfeld : "Web Grammars". Prcc. of the Int. Joint Conf. on Art. Int. (IJCAI) May 1969.
2. ( 8) J. C. Simon and J. Camillerapp : "Recherche d'une Forme dans un Fond". C. R. Ac. Sc., Serie A,~. pp. 946-949, 16 Decembre 1968.
3. J. C. Simon, A. Checroun and C. Roche : "Com paraison des Formes Independantes des Deplacements, Homotheties et petites Deformations". C. R. Ac. Sc., Series A, 21Q, pp. 1,607-1,609 15 Juin 1970.
4. ( 10) J. C. Simon, A. Checroun and C. Roche : "A Me thad of Comparing two Patterns Inde pendent of possible Transformations a.'ld small Distorsions". IEEE Sympo sium on syntactic pattern recogni tion. Cticago , oct . 1970. ~o be p~bl~sted in Pattern Recognition Jo"-rr:al.