Abstract:
An apparatus for identifying postage stamps automatically includes one or more scanners for detecting the various colors which are present at predetermined regions on the stamp proper and associated circuitry which receives the color signals and derives from them a feature vector which represents the color distribution over the scanned area. A plurality of feature vectors which define the color distribution associated with known stamps is stored in a memory. A comparator compares the feature vector of the stamp being examined to the prestored feature vectors and determines the identity of the stamps.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a mail processing apparatus, and more particularly, to an apparatus for itentifying postage stamps based on identifying the color information contained in the stamps. 
     2. Prior Art 
     An automatic mail processing apparatus has been developed in which a postage stamp affixed on a mail article is detected and the type of the detected stamp is identified so as to determine the type of the mail article (ordinary mail or express mail) and whether or not the appropriate postage is affixed. According to the prior art, postage stamps are generally detected according to one method based on the luminescence of luminescent stamps, such as fluorescent or phosphorescent stamps. Another method relies on a special mark printed on each stamp, and yet a further method relies on detecting the predetermined color of each type of stamp. However, the first method has a disadvantage in that the cost of producing the stamps is increased, and the other methods suffer from a problem in that the design of the postage stamps is limited. 
     In Japan, each regular postage stamp has a frame of a specific color associated with its postage, and this specific color frame is detected to determine the type of the postage stamp. This method also restricts the design of the stamps. All stamps including commemorative stamps must have a specific color frame. Stamps having no specific color frame cannot be detected in the prior art processing apparatus. 
     SUMMARY OF THE INVENTION 
     Accordingly, it is an object of the present invention to provide an apparatus for identifying postage stamps which does not impose any limitation on the design of the stamps. 
     According to the present invention, there is provided a postage stamp identifying apparatus, in which color characteristic patterns of the stamp are extracted as a feature vector from a stamp, and the detected color characteristic pattern of the stamp is compared with each of standard color characteristic patterns prepared beforehand for known stamps. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows predefined portions on a stamp to be used for color characteristic pattern extraction performed in accordance with the present invention. 
     FIG. 2(a) is an enlarged view of one portion of FIG. 1. 
     FIG. 2(b) shows distribution of weights in the portion of FIG. 2(a). 
     FIG. 3 illustrates a block diagram of a first embodiment of the present invention. 
     FIG. 4 illustrates an arithmetic circuit associated with the first embodiment shown in FIG. 3. 
     FIG. 5 illustrates distribution of weights employed in a convolution circuit in the first embodiment shown in FIG. 3. 
     FIG. 6 illustrates the convolution circuit in the first embodiment shown in FIG. 3. 
     FIG. 7 illustrates a latch circuit in the convolution circuit shown in FIG. 6. 
     FIG. 8 illustrates a featuring circuit in the first embodiment shown in FIG. 3. 
     FIG. 9 illustrates a judging circuit in the first embodiment shown in FIG. 3. 
     FIG. 10 illustrates a distance calculating circuit in FIG. 9 in which Mahalanobis&#39; distance is used. 
     FIG. 11 illustrates a featuring circuit in a second embodiment of the present invention. 
     FIG. 12 illustrates distribution of weights employed in a third embodiment of the present invention. 
     FIG. 13 illustrates a block diagram of a third embodiment of this invention. 
     FIG. 14 illustrates a block diagram of a fourth embodiment of the present invention. 
     FIG. 15 illustrates a diagram of a fifth embodiment of the present invention. 
     FIG. 16 illustrates a diagram of a sixth embodiment of the present invention. 
     FIG. 17 illustrates a diagram for extracting red (R), green (G) and blue (B) components from an output of a scanning means. 
     FIG. 18 illustrates a diagram of a scanner which extracts respective color distribution signals at different positions on a stamp. 
     FIG. 19 illustrates a diagram of a seventh embodiment of the present invention in which line sensor arrays are employed as a sensor. 
     FIG. 20 illustrates a diagram for explaining the operation of the seventh embodiment shown in FIG. 19. 
     FIG. 21 illustrates a diagram of an eighth embodiment of the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The function of the present invention will be described below by referring to FIGS. 1, 2(a) and 2(b). In the present invention, the image of a postage stamp is divided into several image portions p, as shown in FIG. 1, and the color distribution in each image portion is described by color moment in the color space so as to identify the stamp pattern. 
     The method of calculating the color moment in each image portion will now be described by referring to FIGS. 2(a) and 2(b). An image at a position (x, y) is detected by a sensor having n spectral sensitivities, and the sensor generates signals f 1  (x, y), f 2  (x, y), . . . , f i  (x, y), . . . , f n  (x, y) (i=1, . . . , n). Generally, a color sensor has sensitivities of red light (R), green light (G), and blue light (B), and the outputs of the sensor, f 1 , f 2 , and f 3 , are therefore signals representing a red image R(x, y), a green image G(x, y), and a blue image B(x, y). At this point, the color moment M k  (x 0 , y 0 ) (k=1, . . . , m) of the image portion p whose center is at (x 0 , y 0 ) is defined by the following Expression (1): ##EQU1## where S 0  is a region occupied by the image portion p, and ω(x-x 0 , y-y 0 ) is a weight in case the center is at (x 0 , y 0 ). The weight is generally higher near the center and lower near the periphery, as shown in FIG. 2(b). 
     As can be seen from the above definition, if ##EQU2## and ρ 1  =1, γ 1  =β 1  =0; M 1  (x 0 , y 0 ) represents a weighted average of the red image centered at (x 0 , y 0 ). Similarly, if ρ 2  =0, γ 2  =1, β 2  =0, and ρ 3  =γ 3  =0, β 3  =1; M 2  (x 0 , y 0 ) and M 3  (x 0 , y 0 ) represent weighted averages of the green image and blue image, respectively. ##EQU3## 
     In order to make the color moments M 4  and M 5  uncorrelated to the color moments M 1 , M 2 , the color moments M 3 , M 4  and M 5  are made to be the variance of the red image and the covariances of the green and blue images, respectively, and are set by: 
     
         M.sub.4 &#39;(x.sub.0, y.sub.0)≡M.sub.4 (x.sub.0, y.sub.0)-M.sub.1.sup.2 (x.sub.0, y.sub.0) 
    
     
         M.sub.5 &#39;(x.sub.0, y.sub.0)≡M.sub.5 (x.sub.0, y.sub.0)-M.sub.2 (x.sub.0, y.sub.0)M.sub.3 (x.sub.0, y.sub.0)              (2) 
    
     In consequence, the color distribution for the image portion centered on (x, y) is expressed by the following features: 
     
         {g.sub.i }(j=1, . . . , 5) 
    
     where g 1  (x, y)=M 1  (x, y), g 2  (x, y)=M 2  (x, y), g 3  (x, y)=M 3  (x, y), g 4  (x, y)=M 4  &#39;(x, y), and g 5  (x, y)=M 5  &#39;(x, y). 
     If the image is divided into five image portions p, as shown in FIG. 1, and the entire image is expressed as a set of color distributions of these image portions, the color distribution of the entire image can be expressed in the same way by a feature vector: 
     
         {h.sub.j }(j=1, . . . , 25), ##EQU4## 
    
     To identify N types (kinds) of postage stamps using the feature vector, N features vectors, {h j  } corresponding to the respective stamp patterns of N type are extracted beforehand and stored as reference (dictionary) feature vectors {h j   l  } (l=1, . . . , N). The distance d l  between the feature vector {h j  } obtained by scanning unknown stamp and the dictionary feature vectors {h j   l  }, is then calculated. 
     Any of known methods employed in general pattern recognition apparatuses can be employed to calculate the distance d l . If the distance is calculated by using Euclidean distance in the feature vector space, the following expression is calculated: ##EQU5## Similarly, if Mahalanobis&#39; distance is employed, the following expression is calculated: 
     
         d.sub.l.sup.2 ≡(h-h.sup.l).sup.t S.sub.l.sup.-1 (h-h.sup.l) (5) 
    
     where h and h l  are the column vectors of {h j  } and {h j   l  }, and S l  is the covariance matrix of {h j  } which have been obtained beforehand by scanning various known stamp patterns. 
     If there is a stamp of the l-type with the image input position (x&#39;, y&#39;) as the center thereof, the distance d l  becomes a very small value. Therefore, a threshold value T l  is set for each type of stamps, and the following condition is checked to detect the presence of l-type of the stamp centered on the position (x&#39;,y&#39;): 
     
         d.sub.l &lt;T.sub.l                                           (6) 
    
     In addition, when Mahalanobis&#39; distance is employed, any variation in the feature vector is included in the distance, and a threshold value T l  can therefore be made a constant which does not vary in accordance with the type of stamp. 
     Although any set of components defining the feature vector {h j  } can be selected depending on how color moment is selected, it is effective to normalize the color moment in terms of change in the amount of light of the illumination. Illumination of the scanner varies with time, and the brightness of the illumination supplied when a dictionary feature vector is extracted may be different from that supplied when an unknown postage stamp is scanned. This variation in brightness changes the color moment, reducing the recognition accuracy. Accordingly, in order to prevent such disadvantage the feature vector can be normalized by using the brightnesses of the components, as follows: ##EQU6## where M 1 , M 2  and M 3  are, respectively, averages of M 1 , M 2  and M 3  at their respective center positions, and are expressed by: ##EQU7## 
     The above normalization decreases degree of freedom, and, as a result, the feature vector {h j  }(j=1, . . . , 20) of the entire image can be determined as follows: ##EQU8## The distance d l  between the feature vectors {h j  } and {h j  l} is then defined in the same manner as that in Expressions (4) and (5) so as to identify the stamp pattern by Expression (6). 
     Further, more accurate recognition is possible by utilizing color moments of higher order beyond the first order and the second order described above. On the other hand, if the stamp pattern to be detected is not very complicated, it is possible to identify a stamp pattern by using the color moment of first order, i.e., the weighted averages of primary colors R, G and B. In this case, only linear weighted average of the R, G, and B color signals are employed, and it is not therefore necessary to perform the convolution operation of Expression (1). Furthermore, in this case, equivalent result of the weighted average calculation is easily obtained by seting up a scanner out of focus. 
     A first embodiment of the present invention will now be described with reference to FIG. 3. A stamp pattern 1  is scanned by a sensor 2 and band channels employed in the embodiment for imaging are R (red), G (green), and B (blue). Three primary color signals R, G, and B which are generated by the sensor 2 are digitzed for picture elements, and are input to an arithmetic circuit 3. The arithmetic circuit 3 calculates the product portion of Expression (1), i.e., 
     
         R(x, y).sup.ρ k·G(x, y).sup.γ k·B(x, y).sup.β k                                           (10) 
    
     for each picture element. For example, the arithmetic circuit 3 outputs the following five values: 
     
         R(x, y) when ρ.sub.1 =1, γ.sub.1 =β.sub.1 =0, 
    
     
         G(x, y) when ρ.sub.2 =0, γ.sub.2 =1, β.sub.2 =0, 
    
     
         B(x, y) when ρ.sub.3 =γ.sub.3 =0, β.sub.3 =1, 
    
     
         R(x, y).sup.2 when ρ.sub.4 =2, γ.sub.4 =β.sub.4 =0, and 
    
     
         G(x, y)·B(x, y) when ρ.sub.5 =0, γ.sub.5 =β.sub.5 =1. 
    
     The arithmetic circuit 3 is constructed as shown in FIG. 4. In arithmetic circuit 3, the R, G, and B signals are simply passed through. However, the R 2  and G.B signals are respectively calculated by multiplier 301 and multiplier 302 before being output from arithmetic circuit 3. The signals from arithmetic circuit 3 are supplies to respective convolution circuits 4. Each convolution circuit 4 multiplies the corresponding signal by the weights ω shown in FIG. 5, and adds up these products. 
     The arrangement of each convolution circuit 4 will now be described in detail by referring to FIGS. 5 to 7. In the illustrated embodiment, thirty-seven signal values of thirty-seven picture elements in the image portion are weighted by W 1 , W 2 , . . . , W 37  as shown in FIG. 5 and added to obtain a value for a signal value of the picture element at the center of the image portion. Each convolution circuit 4 is constructed as shown in FIG. 6. Convolution circuit 4 includes latch circuits 401, labeled L 1  to L 37 . Each latch circuit retains the signal value of one picture element in synchronism with the scanning of the stamp pattern. Further, each latch circuit 401 is constructed as shown FIG. 7. In FIG. 7, each picture element signal value is retained in a latch 4011, and is output to the subsequent latch circuit. A multiplier 4013 multiplies the picture element signal value by the corresponding weight (W 1 , W 2 , . . . , W 37 ) stored in a weight storage 4012. 
     When the entire stamp pattern is scanned sequentially in the manner shown by an arrow in FIG. 5, the output signal is sequentially supplied to the latch circuits L 37  to L 1  as the scanning proceeds. When the first picture element signal value has been retained in the latch circuit L 1 , the latch circuits L 1  to L 37  have retained respective picture element signal values. Then, these picture element signal values are multiplied with the respective weights shown in FIG. 5 and the multiplied results of each line are supplied to respective adders 403. The added results of respective lines are supplied to an adder 404. Delay circuits 402 are provided to adjust the timing of picture elements signals over two lines. For example, the delay circuit D 1  in FIG. 6 delays signals for a time T 1  +T 2  relating to FIG. 6 during which the scanning shifts from the position W 3  to the position W 4 . Consequently, the adder 404 adds up all the weighted picture element signal values and outputs the result of the previously defined Expression (1). 
     Referring back to FIG. 3, color moments M 1  to M 5  from the convolution circuits 4 correspond to the color distribution of one image portion (for example, the one centered on (x 0 , y 0 )) shown in FIG. 1. In order to identify the stamp pattern by the feature vector {h j  } shown in Expression (3) which is produced from the five image portions shown in FIG. 1, the color moments M 1  to M 5  must each be delayed by a time which corresponds to the distance among the image portions. These operations are carried out by delay circuits 5. Consequently, color moments M 1  to M 5  obtained for each image portion are supplied to a featuring circuit 6. In the present embodiment, if these color moments are employed as they are as the feature vector, the featuring circuit 6 can be eliminated. However, the color moments M 4  and M 5  are transformed into the other color moments M 4  &#39; and M 5  &#39; which are uncorrelated with the color moments M 1  to M 3  , as described previously, and the featuring circuit 6 calculates Expression (2) to obtain the feature vector {h j  }. As shown in FIG. 8, the featuring circuit 6 includes multipliers 601 and subtractors 602, and each pair of one multiplier and one subtractor perform the calculations of Expressions (2) for each image portion. 
     A judging circuit 7 determines a distance between the feature vector {h j  } obtained from a scanned stamp pattern and the dictionary feature vectors {h j   l  } (l=1, 2, . . . , N) of known previously stored stamp patterns, and thereby identifies the stamp and outputs a recognition signal. The judging circuit 7 is constructed as shown in FIG. 9. In this Figure, the feature vector {h j  } is supplied to distance calculation circuits 701, and these circuits 701 calculate squares of the distance d l   2  with respect to respective dictionary feature vectors, i.e., known stamp pattern by Expression (4) or (5). Comparing circuits 702 compare the respective thus-obtained distances with corresponding threshold values. The comparing circuits 702 delivers output signals when Expression (6) is satisfied. The encoder 703 detects which comparing circuit 702 has delivered the output signal, and delivers the recognition signal representative of an identified stamp. 
     FIG. 10 illustrates an example of a distance calculating circuit 701 in which a Mahalanobis&#39; distance is calculated. In FIG. 10, a dictionary storage 7011 stores the dictionary feature vector {h j   l  } of l-type stamp, and a matrix storage 7012 stores the inverse matrix S l   -1  of the covariance matrix for the dictionary feature vector. As described above, the stored dictionary feature vector {h j   l  } and the inverse matrix S l   -1  are previously obtained by scanning the known stamp of the l-type. Subtraction circuit 7013 delivers the difference between the feature vector {h j  } and the dictionary feature vector {h j   l  } on element-to-element basis. An inner product calculation circuit 7014 calculates the inner products of the subtraction results the matrixes stored in the matrix storage circuits 7012. To simplify the explanation, FIG. 10 shows a matrix storage means of five matrixes. However, in the given example, S l   -1  is a 25×25 matrix, and calculations of the inner products of 25 matrixes are required in practice. Consequently, vectors having the components of the number of matrixes are obtained, and an inner product calculation circuit 7015 obtains the inner products of these vectors and the outputs of the subtraction circuits 7013 so as to obtain d l   2 . 
     A second embodiment of the present invention is described below. In the second embodiment, the feature vector {h j  } is normalized by Expression (7) and the normalized feature vector is applied to the distance calculation. The arrangement of this embodiment is the same as that of the first embodiment of FIG. 3 except for the featuring circuit 6. FIG. 11 shows the construction of the featuring circuit 6 employed in the second embodiment. Similarly to the first embodiment, multiplier 601 and subtractor 602 obtain color moments M 1  to M 3  and M 4  &#39; and M 5  &#39; for each image portion in FIG. 1 from the input color moment M 1  to M 5 . Averaging circuits 603 calculate the averages M 1  to M 3  of M 1  to M 3  of all the image portions on the bases of Expression (8). These averages are used for normalization. First order normalization circuits 604 determine g 1  to g 3  for each image portion by dividing M 1  to M 3  by M 1  to M 3 , as shown by Expression (7). Second order normalization circuits 605 determine g 4  and g 5  by dividing M 4  &#39; by M 1  twice, and by dividing M 5  &#39; by M 2  and M 3 , respectively. 
     In the second embodiment, since the degree of freedom of the feature vector is decreased by the normalization, the feature vector corresponding to the position (x 0 , y 0 ) is eliminated, and the feature vector {h j  } containing elements g 1  to g 20 , which are shown in Expression 9, is obtained. The construction of other parts of this embodiment is therefore the same as that of the first embodiment shown in FIG. 3. However, it is to be noted that in the case of using the Mahalanobis&#39; distance, the distance calculation circuit 701 is constructed such that the size of the matrix storage 7012 corresponds to the number of elements in the feature vector. 
     A third embodiment of the present invention will be described by reference to FIG. 13. In this embodiment, color moments of higher-order are not required. The present embodiment may be realized by eliminating the convolution of R 2  and G·B components in the first embodiment. However, in the third embodiment, instead of performing the complicated calculations of the convolution for R, G, and B primary color signals, the same function is performed by modifying a optical scanning part. Namely, a stamp pattern is optically defocused relative to the sensor, i.e., a scanner is disposed out of focus, so that weighting operation shown in FIG. 12 can be easily performed. 
     The operation of the third embodiment is as follows. In FIG. 13, when a sensor 2 scans a stamp pattern 1, the sensor outputs R, G, and B color signals as image data. At this time, since the stamp pattern relative to the sensor 2 is out of focus, color moments M 1 , M 2  and M 3  for each image portion can therefore be obtained without calculations of convolution. The delay circuits 5 delay the M 1  to M 3  to obtain color moments for all the image portions which are in a fixed positional relationship to one another, and the feature vector {h j  } is produced. The feature vector {h j  } in then supplied to the judging circuit 7 to identify the stamp pattern. 
     A fourth embodiment of the present invention is described below, in which the feature obtained in the third embodiment is normalized before being supplied to the judging circuit. FIG. 14 shows a structure of the fourth embodiment. A featuring circuit 6 is added to the structure shown in FIG. 13 to carry out the normalization. The featuring circuit 6 calculates g 1  to g 3  indicated by Expression (7) for each image portion. Therefore, the featuring circuit 6 of the fourth embodiment is realized by eliminating circuit elements for processing the color moments M 4  and M 5  in the featuring circuit 6 shown in FIG. 11 (including the multipliers 601 and subtractors 602). 
     A fifth embodiment of the present invention is described referring to FIG. 15. In the third embodiment of FIG. 13, the sensor 2 senses only one portion at a time, and simultaneous observation of a plurality of the image portions is virtually realized with the aid of the delay circuits 5. In the fifth embodiment, this can be realized by actually using a plurality of color sensors, as illustrated in FIG. 15. In the figure, respective sensors 8 sense the corresponding image portions. Five sets of primary color signals delivered from the respective defocused sensors 8 are supplied to a judging circuit 7 as the feature vector {h j  }. The judging circuit 7 is constructed as shown in FIG. 9. 
     A sixth embodiment of the present invention shown in FIG. 16 is described below. The operation of this embodiment is exactly the same as that of the fifth embodiment except that normalization is applied. A featuring circuit 6 is therefore added to the structure shown in FIG. 15. The feature vector {h j  } is obtained through the featuring circuit 6 in the same manner as in the fourth embodiment, and the feature vector {h j  } is processed in the same manner. 
     FIG. 17 shows a structure for extracting R, G, and B color signals from one scanning output. In FIG. 17, light from the scanned surface is supplied through a lens 9 to splitters 10 and 11, each for separating light having a predetermined wavelength. Light of R component, B component, and G component separated by the splitters 10 and 11 are respectively supplied to photoelectric elements 12, 13 and 14 so as to deliver R, B and G color signals. 
     In the embodiments shown in FIGS. 3, 13, and 14, scanning operation consists of horizontal scanning and vertical scanning. A mechanical scanning mirror or a line sensor is employed for horizontal scanning, while a mechanism for shifting a surface to be scanned is employed for vertical scanning. 
     In the embodiments shown in FIGS. 15 and 16, five sensors simultaneously sense corresponding image portions on the stamp during a scanning. In these cases, conventional scanning mechanisms can be employed to carry out such scanning, and FIG. 18 shows one example thereof. Light from a scanned surface 2 is supplied through a lens 9 and a mirror 15 to five sensors 16. The mirror 15 is turned about the center thereof to horizontally scan the surface, and the scanned surface is shifted in the vertical direction. 
     FIG. 19 shows a seventh embodiment in which scanning is performed by a line sensor. In this embodiment, three sensor arrays are employed to carry out the horizontal scanning electronically. The surface to be scanned as mechanically moved for vertical scanning. The sensor arrays 17, 18 and 19 are the line sensor arrays which produce red, green and blue color signals, respectively. To this end, the sensor arrays receive red, green, and blue light components from a scanning line L, respectively. The output signals of the sensor arrays are digitized by corresponding A/D converters 20. Generally, a line sensor includes a large number of sensing elements, for example, 256 sensing elements. In this embodiment, delay circuits 21 to 24 are also employed to virtually sense five image portions. 
     The operation of these delay circuits is described by referring to FIG. 20. The x-marks 27 to 31 in this figure indicate the center positions of five image portions. Assuming that the stamp pattern is scanned in the direction shown by the arrow, the position 27 is sensed when the sensor array is located relatively at a location 32. If outputs of the sensing elements in the sensor array are transferred from the left side to the right side, width d 1  in the sensor array is scanned while the sensor array is located at the location 32. The surface to be scanned is then shifted while the sensor array continues to be scanned horizontally. This moves the sensor array relatively from the location 32 to the location 33. Width d 2  of the sensor array is then scanned to sense the position 28. The delay circuit 21 delays the outputs of the sensor array by a time which corresponds to this duration. Similarly, the delay circuit 22 delays the outputs by a time during which width d 3  from the position 28 to the position 29 is scanned, and the delay circuit 23 delays the outputs by a time during which width d 4  from the position 29 to the position 30 is scanned. Further, the delay circuit 24 delays the outputs by a time during which width d 5  is scanned and the sensor array is vertically scanned from the relative location 33 to the relative location 34. In this period, width d 6  is scanned. These delay circuits 21 to 24 ensure the similar effect performed by the previous embodiments. 
     Distance calculation circuits 25 and comparing circuits 26 operate in the same way as shown in FIG. 9. A control circuit 27 receives the detection signal from the comparison portions 26, and outputs recognition signal. The control circuit 27 also produces horizontal control signals for the sensor arrays 17 to 19 and a vertical control signal for vertically driving the surface. 
     FIG. 21 shows an eighth embodiment in which a normalization circuit 6 in further added. In the embodiments shown in FIGS. 19 and 21, if an plane sensor array is employed instead of the line sensor array, both horizontal and vertical scanning can be performed electrically.