Abstract:
The invention relates to a textural parameter extractor for classification or learning. Four (4) simple 2D optimum masks independent of image, are applied to four adjacent pixels in order to diagonize the associated covariance matrice. The first three (3) central moments, namely absolute deviation, standard deviation and skewness for each transformed image constitute a feature vector of twelve (12) components for classification purposes. Parallel and Sequential structures are also presented for fast textural feature extractor applications.

Description:
BACKGROUND OF THE INVENTION 
     (A) Field of the Invention 
     The present invention relates to a digital circuit for textural feature extraction or texture classification. 
     (B) Description of Prior Art 
     In recent years many different techniques have been proposed for texture classification. 
     The classical Gray Tone Spatial Dependence Matrices GTSDM as disclosed in an article by R. M. Haralick, K. Shannugan, I. Dinstein, entitled &#34;TEXTURAL FEATURES FOR IMAGE CLASSIFICATION&#34;, IEEE Trans. Syst., Man. Cybern, vol. SMC 8, pp. 10-621, November 1983, is perhaps one of the most popular algorithms for texture feature extraction. However, because of its voluminous data requirements, the method becomes economically unfeasible for high speed applications. 
     In an article entitled &#34;Texture Energy Measures&#34; by Kenneth I. Laws, in Proc. Image Understanding Workshop, pp. 47-51, November 1979, Laws teaches the use of some filters of dimension 3×3 or 5×5 for matching edges, spots, lines, ripple, etc. Although good results have been obtained, this approach is heuristic. The filter set is either uncomplete or not mutually orthogonal. 
     In a recent article by Michael Unser, entitled &#34;Sum and Difference Histograms for texture classification&#34;, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 1, pp. 118-125, January 1986, Unser introduces the sum and the difference transformations for a pair of picture elements along a given direction. These transformations reduce the computational time and memory storage requirements compared to the Gray Tone Spatial Dependence Matrices (GTSDM). However, this method is conceptually equivalent to the GTSDM one by using a pair of picture elements. 
     SUMMARY OF INVENTION 
     It is a feature of the present invention to provide an optimal textural feature extractor by using a class of two dimensional four (4) picture elements. 
     Another feature of the invention is to provide a real time device for extraction and storage of texture parameters. 
     A still further feature of the invention is to provide a fast and effective device for texture classification. 
     According to the above features from a broad aspect, the present invention comprises a processing system and a method of analyzing textural features of a texture image, such as on the CRT of a computer terminal. The system comprises a calculator circuit for producing four picture transformed signals which are mutually uncorrelated. Deviation and moment calculators analyze each of the transformed signals by measuring the three central moments thereof and generating signal parameters representative of the texture image. A processing circuit is utilized in classification mode for calculating discriminent functions from the signal parameters assumed to be normally distributed. 
    
    
     A preferred embodiment of the present invention will now be described with reference to examples illustrated in the accompanying drawings in which; 
     FIGS. 1A and 1B illustrate the rectangle of four (4) picture elements for texture analysis; 
     FIG. 2 illustrates, in block form, a calculation of the optimum masks; 
     FIG. 3 is a block diagram of a pixel deviation calculator for each mask output; 
     FIG. 4 is a block diagram of a generator of the first three (3) central moments for classification; 
     FIG. 5 is a block diagram of the proposed real time parameter extractor for texture classification, and 
     FIG. 6 is a block diagram of another proposed texture parameter extractor using sequential calculation techniques. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     Referring now to the drawings, FIGS. 1A and 1B describe the class of four (4) picture elements (pixels) used for texture analysis. In general, the chosen pixels form a rectangle as illustrated in FIG. 1B. A special but important case, described in FIG. 1A, is the square of four (4) adjacent pixels namely A, B, C, and D. For the sake of simplicity the following covariance matrix will be given only for the special case of adjacent pixels. 
     Let (X(i,j); i=1, . . . , I; j=1, . . . , J) be a two dimensional stationary and ergodic random field, in which the discrete variable X(i,j) represents intensity of pixel (i,j). The covariance matrix associated with the four (4) chosen pixels given by: ##EQU1## and a, b, c represent three normalized covariances appropriate to a pair of random variables X(i+p, j+q) and X(i,j). 
     The covariance matrix C in equation (1) can be diagonalized by the following matrix: ##EQU2## 
     In other words, the four new random variables Y 1 , Y 2 , Y 3  and Y 4  resulted from the Walsh Hadamard transform (4) of four chosen pixels, are uncorrelated. One has the following properties: ##EQU3## 
     Furthermore, it is well known that the Walsh Hadamard functions are orthonormal and complete. 
     The transformed random variable Y 1 , Y 2 , Y 3  and Y 4  can be obtained by the following equation: ##EQU4## where A, B, C, and D are the four chosen pixel intensities. 
     Referring now to the drawings, FIG. 2 illustrates a real time calculator for the optimum masks, i.e., equation (7). This calculator 200 consists of eight (8) combiners 201, 202, 203, 204, 205, 206, 207 and 208. The calculator parallel inputs are A, B, C, D. The outputs of the four combiners 201, 202, 203 and 204 are respectively: A+B, A-B, C+D, C-D which are in turn the inputs in an appropriate manner, of the combiners 205, 206, 207 and 208. The optional division by 2 at each output of the last four combiners can be accomplished by rounding off, i.e. forgetting the output least significant bit. 
     The Walsh Hadamard equation (7) yields four (4) pictures of transformed signals or coefficients Y k  (i,j); k=1, . . . , 4; i=1, . . . , I; j=1, . . . , J. 
     In order to reduce this amount of information for storage and/or classification, the following measures shall be obtained for each random variable Y k  : ##EQU5## where the mean Y k  and M number of textural pixels to be considered are given respectively by: ##EQU6## 
     In other words, equations (8), (9), (10) describe the first three (3) central moments of the transformed image first order histogram. Since the four (4) chosen pixels contain already 2D information, our experience has shown that, contrary to existent techniques, it is not necessary to deal with (space/time consuming) second-order distributions for obtaining good results (about 99% for correct classification). 
     FIGS. 3 and 4 illustrate the necessary calculation for the first three central moments of each transformed random variable Y k . 
     Referring now to the drawings, FIG. 3 describes a block-diagram of a real time transformed pixel deviation calculator. Let the indice t denote the present frame or the present texture image; consequently t-1 identifies the previous frame. The pixel deviation calculator output 303 is given by: 
     
         Z.sub.k (i,j; t-1)=Y.sub.k (i,j; t-1)-Y.sub.k (t-1)        (13) 
    
     the common term in equations (8), (9), (10) in which the indice t-1 has been omitted. 
     In order to obtain the pixel deviation Z k  (i,j), it is necessary to calculate firstly the mean Y k  given by equation (11). Thus, the real time pixel deviation calculator 300 in FIG. 3 has two (2) inputs 301 and 302, namely Y k  (i,j;t) and Y k  (i,j; t-1) which correspond respectively to the present and the previous frame. The calculator 300 consists mainly of an accumulator 310, an averager 320, a latch 330 and a subtractor 340. The accumulator 310 contains a combiner 311 and a D flipflop register 312. The register output is sent, in feedback, to the combiner 311. The averager 320 represents a rounding-off function if M, the number of considered pixels, equals exactly 2 m , where m in turn is an integer. In other cases, for example: M=48×48=9×2 8  the averager consists of a rounding and a ROM. 
     The accumulator 310 and the averager 320 are used to calculate the mean Y k  (t) while the latch 330 preserves the previous mean Y k  (t-1). Finally, the subtractor 304 yield the pixel deviation Z k  (i,j;t-1) from two inputs Y k  (i,j;t-1) and Y k  (t-1). 
     FIG. 4 illustrates a generator block-diagram for the first three (3) central moments D 1k , D 2k , D 3k  given in equations (8), (9), (10). The generator 400 contains three (3) parallel branches 410, 420, 430 which calculate respectively the moments D 1k , D 2k , D 3k . In general, each branch consists of a read only memory (ROM), an accumulator, an averager, and a latch. The ROM 1, 2 and 3 labelled 411, 421, 431 are used respectively for the following operations absolute value, power of 2 (square) and cubic power analysis. 
     The accumulators 412, 422, 432 are similar to that 310 in FIG. 3 previously described. The latches 414, 424, 434 are used for holding the calculated moments. 
     In order to avoid the truncation or overflow problem the following table summarizes element bit length in function of moment order p. 
     
         __________________________________________________________________________BIT LENGTH OFAccum.     Latch  ROM 4kl                  Accum.p Y.sub.k310  330 Z.sub.k            Output                  4k2     D.sub.P.sbsb.k__________________________________________________________________________1 n+2n+2+m     n+2 n+3            n+2   n+2+m   n+22 n+2n+2+m     n+2 n+3            2(n+2)                  2(n+2)+m                          2(n+2)3 n+2n+2+m     n+2 n+3            3(n+2)+1                  3(n+2)+1+m                          3(n+2)+1__________________________________________________________________________ 
    
     where n denotes the pixel bit length and m is the smallest integer greater or equal to log M/log 2. 
     Referring to the drawings, FIG. 5 describes the proposed configuration for real time texture parameter extraction. It contains principally a frame delay 550, two (2) line &amp; pixel delays 100, two (2) optimum mask calculators 200, four (4) transformed pixel deviation calculators 300, four (4) moment generators and a micro-processor 500 for texture classification and/or learning. As previously mentioned, it is necessary to obtain the mean value Y k  before the calculation of transformed pixel deviation. It is the &#34;raison d&#39;etre&#34; of frame delay 550. In fact, if the input 502 denotes the texture image of the present frame X(i,j;t), its output 501 will be X(i,j;t-1) the previous texture image. The line and pixel delays 100 are used to obtain necessary parallel outputs for mask calculators 200. The outputs 504 are A(i,j;t), B(i,j;t), C(i,j;t) and D(i,j;t) defined in FIG. 1 while those 503 are A(i,j;t-1), B(i,j;t-1), C(i,j;t-1), D(i,j;t-1). The optimum mask calculators 200 are described already in FIG. 2. Their outputs are Y k  (i,j;t) and Y k  (i,j;t- 1) respectively for 506 and 505 in which k=1, 2, 3, 4. The pixel deviation calculators 300 and moment generators 400 are described in FIG. 3 and FIG. 4. The generator outputs 511, 512, 513, 514 give twelve (12) parameters D pk  ; p=1, 2, 3; k=1, 2, 3, 4; &#34;representing&#34; the texture image. The parameters are sent to a suitable micro-processor for classification mode or learning. 
     Firstly, the micro-processor converts the twelve received parameters D pk  to another set of twelve parameters, namely d pk  : ##EQU7## and defines the following feature vector d 
     
         d=[d.sub.11, d.sub.21, d.sub.31, d.sub.12, . . . , d.sub.34 ].sup.T (17) 
    
     Our experiences have shown that good results can be obtained by assuming the feature vector be multivariate normal distributed for a given texture w j  and therefore by using the maximum likelihood decision rule. Thus, in classification mode, the micro-processor calculates the following discriminant function 
     
         Δ.sub.j (d)=(d-m.sub.j).sup.T ·R.sup.-1 ·(d-m.sub.j)+log |R.sub.j |    (18) 
    
     for each texture w j  which is known a priori in the learning mode. 
     The micro-processor classifies the considered texture to be class w i  if: ##EQU8## 
     In the learning mode, for K texture samples of class w j , the micro-processor estimates the distribution parameters: m j , R j  by the following equations: ##EQU9## 
     Then it calculates the inverse matrix R j   -1  and log |R j  | which are useful in the classification phase. 
     In some applications where the &#34;real time&#34; is not truly a critical factor it should be economically effective to extract the texture features in a sequential manner. FIG. 6 illustrates a proposed block diagram of such a sequential extractor. Referring to the drawings, texture image 601 is sent firstly to a frame grabber 600 which holds the image at least for the computation time. The frame grabber output is connected to line and pixel delays 100 which produces necessary parallel outputs 603 for mask calculator 200. The multiplexer 620 selects only one output Y k  (i,j) of mask calculator in order to calculate its three (3) associated parameters D pk . When this calculation is finished, multiplexer 620 will select another mask calculator output and so on. The multiplexer output 605 is sent to a sequential parameter calculator 700. This device is designed to obtain firstly the mean Y k  which will be held by latch 670 for subsequent calculation and then by a sequential manner the three parameters D 1k , D 2k , D 3k  associated to Y k  (i,j). These parameters will be sent to the micro-processor 500 via latch 660. Thus the multiplexer 640 has to select Y k  (i,j) 605 for the first phase of computation and ROM output 608 for the three other phases. The ROM 630 is a combination of ROM 411, 421, 431 described in FIG. 4. The sub-block 650 is the accumulator 532 and the averager 433. The timing and control 710 produces necessary signals specially for multiplexers 620, 640, ROM 630, latches 660, 670. 
     The proposed sequential extractor, FIG. 6, is 16 times slower than the parallel extractor illustrated in FIG. 5. There are, of course, other configurations using the same principle, which give a performance between these two speeds or slower. 
     It should be worthwhile to present herewith some classification results of twelve different texture images taken from P. Brodatz&#39;s album &#34;Textures - A Photographic Album for Artists and Designers&#34; Dover NY 1966. 
     
         ______________________________________Correct classification results (leaving one out strategy)                      Pairwise sums &amp;      Proposed masks  Pairwise sums &amp;k          Proposed parameters                      differences usingTexture    (12)            the same parameterssize       Proposed            (24)(pixel)    ML       KNN        ML   KNN______________________________________34 × 32      .935     .790       .835 .71148 × 48      .973     .838       .928 .75464 × 64      .990     .847       .948 .782______________________________________ 
    
     From this experience, the texture size k is preferably chosen to be 4096 for reasons of performance and implementation. Furthermore, the proposed maximum-likelihood (ML) classification yields better results than K-nearest-neighbor (KNN) method. Finally, the proposed masks using twelve parameters of first order distribution gives good performance. Several reasons could explain this behavior: firstly, these masks extract intrinsically two dimensional local features; secondly, these features are uncorrelated and can thus be precisely characterized by moments of their first order distribution.