Geometrical Pattern Feature Extraction by Projection on Haar Orthonormal Basis

1 - PATTERN CLASSIFICATION

The classifica~ion of a set of patterns is a problem that appears in very many fields. In the most simple case the number of different clas­ ses possible is known a priori ; this is the case, for example, of printed characters of a given ty­ pe. But in general their number is unknown.

In a general way, the problem of classi­ f ication is the following : being given a set of patterns one makes certain measurements on these patterns and wants to determine subsets which are, with respect to these measurements, internally as similar. as possible and externally as dissimilar as possible. More formally, we have to define a partition of the set of patterns ; that is, a set of sub-sets which are mutually exclusive and col­ lectively exhaustive. It is not always possible to reach this ideal goal, sometimes the sub-sets are

GEOMETRICAL PATTERN FEATURE EXTRACTION 13Y PROJECTION ON HAAR ORTHONORMAL BASIS

Lucien A. GERARDIN

Jacques FLA.MENT

Research Director Research Engineer

Corporate Research Center - THOMSON-CSF

Corbeville, 91 - ORSAY- France

internally similar and externally dissimilar but neither exclusive nor exhaustive.

The logic diagram of figure 1. schema­ tizes the ideal proceedure for defining such a partition. One uses a set of distance values (or similarity coefficients) in the form of a train­ gular matrix ; each distance (or similarity) being attached to a pair of pattern independently of the order in which one considers these patterns. The distances are to be evaluated from the rough data available on these patterns. If, in making the evaluation, one does not lose information the distance matrix will exactly represent the initial date. Unhappily this is rarely so. Moreover actual patterns are very often composite, the distance between two composite patterns is not very signi­ ficant and it is necessary to extract first the elementary components of composite patterns.

2 - FEATURE EXTRACTION

In all that follows we will especially consider geometrical or more exactly topological patterns. A good example is a meteorological map. In this latter case, we are interested by ombi­ lical points (either highest or lowest atmosphe­ ric pressure), and by evolution of these points. The problem to be solved is to summarize first the actual pattern by a set of features and af­ ter to classify a set of such maps.

For this kind of pattern, it is possible

to associate with each patternS a certain cha­ racteristic function s which contains all the rough datf available concerning that pattern. The energy jEs2 dE associated with this characteristic function is finite because the actual pat­ terns are of finite dimensions. The set of cha­ racteristic functions s constitute a Hilbert spa­ ce ~ and it is possible to define on~ a base orthonormal function fi so that :

Thus i t is natural to use as operators G. the group of scalar products which are the pro­ j~ctions of pattern on the base ~i· and to define the main features gi of the pattern S by :

The set of coefficients gi is conver­ gent and we have the Parseval equal1ty for a cer­ tain base of orthonormal functions called total (and complete if the set is finite)

The above property is interesting as it permits evaluation of that which we might call the quali­ ty of pattern features extraction : the right si­ de of the relation measures the pattern energy, we can evaluate as a function of the rank i to which we have carried the analysis what is the percentage of the energy of the pattern summed up in the set of i first computed features gi by calculating the sum of their squares and decide to stop the analysis when the summation corres­ ponds to 80 or 90 % of the total energy of the pattern to be summed up.

If it is possible to use distance bet­ ween two patterns s(E) andcr-(E), this quantity is the sum of the squares of the differences of the corresponding coefficients gi and ~i

This type of analysis is extremely classic ; the Fourier transformation is a particular case us ing the orthogonal properties of circular functions. Two spatial or temporal functions are identical if they have the same spectrum and we can compa­ re several functions by calculating the sum of the squares of differences between the frequency components ; the greater this sum is the more dis­ tinct the functions will be. In place of the cir­ cular functions one also uses the orthogonal po­ lynomials of Tchebicheff, Legendre, Hermite, Jacobi, Laguerre, etc. Bases are more or less efficiency ; theoritically, the best efficiency is achieved with a Karhunen-Loeve base of ortho­ gonal eigen-functions [6]. But, from a practical point of view it is sometimes preferable to use more classic orthogonal bases.

In a first part of our study, we have used a base of orthonormal functions deduced from Hermite's polynomials to characterize geometric unidimensional patterns of the Morse type si­ gnals dot-dash-space [3). The use of Hermite's polynomials for pattern recognition has been proposed by G.E. LOWITZ [4]. We have poi nted outthe interest of this proceedure but also the discrepancy between the di scontinuous character of the patterns to be summed up and the conti­ nuous aspect of the Hermite Functi ons. In other words, an Hermite base is a bad one to summari­ ze rough date if one admits that these rough data are essentially linked to the discontinui­ ties of s.

It is more normal to think of using bases of discontinuous orthonormal functions which permit a priori a better analysis there­ fore a smaller information loss ; thus we can define the distances between patterns which will have more sense.

3 - HAAR 1 S ORTHONORMAL BASE

Haar's functions (2] constitute an example of such a base. Thei r use in pattern recognition proceedures has already been envi­ saged [1). Therefore our study has been modified and Hermites functions have been replaced by Haar 1 s functions.

The goal is the automated analysis of maps. But, it is too difficult to front-attack this problem and we have used first the same one dimensional patterns as before.

Without losing anything of the gene­ r ality one can, because the monodimensional pat­ terns to be analysed are of finite energy and therefore of finite dimensions "lead the study in the normalized r ange 0.1. Haar's 2n functions of the nth order are defined as follows (see fi­ gure 2).

where~= 2-n- 1 and k = 1, 2, ··· , 2n.

The amplitude 2n/ 2 result of normali­ zation necessity :

and we really have the orthogonality relation­ ship :

For each level n there exists 2n Haar functions and therefore 2n pattern features at the level n.

4 - NUMERICAL EXAMPLES

The interest in using a base of Haar's orthonormal functions is brought out in the exam­ ples that follow.

Some of the analyzed patterns are re­ presented in figure 3. The amplitude can only take but two values 0 or h, h being such that the total energy of the pattern will be unity on the norma­ lized range (0,1).

Figures 4, 5, 6 represent the Haar spectrum up to the 5th order, which is 63 coef­ ficients per pattern. From this we can deduce a certain number of properties which are the follo­ wing (for the unidimensional patterns analyzed).

• a ) a coefficient equal to 0 over a given inter­ val signifies that over that interval the fea­ ture representing the signal is a constant, null or not or that it is symetrical relative to the mean of that interval.
• a positive coefficient signifies that on the first half of the interval the signal is longer than on the second half, this indicates that at least a discontinuity exists over the interval. A negative coefficient leads to the inverse con­ clusions.
• if all the coefficients are nuls to the Mth order, and if the sum of the squares of the coef­ ficients calculated up to then is equal to the energy contained in the signal all the other coefficients of an order greater than M will be nuls, the calculated coefficients exactly sum up the pattern.
• ) . ..J -J-1 d as soon as the quantity~= 2 - J being the order of the Haar function - is less than the smallest interval appearing in the pattern, only the discontinuities will appear. This pro­ perty is very important because it permits to

state that from a certain number N, which is unknown a priori because we don't know the pat­ tern, only the discontinuities remain ; which clearly appears in the examples shown.

e) the accuracy with which we represent the pattern is linked to the value of the interval, i.e. to the order of the Haar function where the analysis has reached.

Therefore it is possible to recons­ truct the pattern from the coefficients of the N order, taking into account the discontinuities appearing on the intervals of a lenght greater than 2-N-1. As an example this is shown in fi­ gure 7 : at the 5th ordefi of the Haar functions the 5th, 10th, 13th, 18t , 23rd and 26th coef­ ficients are different from zero, the interval lenght for this order is 1/32, thus we know that the pat{grn presents a discontinuity for the 5th, 10 , 13th, 18th, 23rd and 26th interval of the reconstructed pattern of figure. 7.

The extraction of the main features of a monodimensional geometric pattern by pro­ jection on a Haar orthonormal base is then a pro­ ceedure that permits a very small information loss. In this way we can make the comparisons between structures, on one hand by considering the number of discontinuities brought out at the ·order where one has stopped and on the other hand by considering the value of the coefficients. For example, the patterns of figure 4. are very close to each other and have just two disconti­ nuities, they are symetrical in relation to the middle of the interval (0.1). These properties appear in the values of the coefficients which are symetrical in relation to 0.5.

If th~ patterns to be analyzed have not the noiseless character of figure 3. but they are deformed, for example, by the presence of noise, the analysis will remain valid. As we can see in figures 6, 8 and 9 the nuls coeffi­ cients are no longer nuls, but certain of the most characteristic amongst them stand out clear­ ly from the background noise of the others. The pattern signal to noise level is roughly 17 dB.

5 - CONCWSION

The classification of a set of patterns by the projection on a total base of orthonormal functions permits to summarize the patterns in an efficient manner ; on the condition of choo­ sing a base matched to the properties of the patterns which concern the classification. In

\

the case of geometric patterns where the discon­ tinuities pl~ an essential role, the use of Haar 1 s functions appears to be ve~ promising as we have seen in the examples given above in the particular case of monodimensional patterns. We must add that Haar's functions are particu­ larly well adapted to computation by digital computer.

For actual bidimensional patterns such as maps, it is possible to use either bidimen­ sional Haar's function or a topological descrip­ tion of bidimensional space onto monodimensional one [5]. We are t~ing to evaluate what is the most efficient.