WO2006100357A1

WO2006100357A1 - Method for processing postal packets including managing digital impressions of the postal packets

Info

Publication number: WO2006100357A1
Application number: PCT/FR2005/051020
Authority: WO
Inventors: Olivier Desprez; Emmanuel Miette; Christophe Caillon
Original assignee: Solystic
Priority date: 2005-03-24
Filing date: 2005-12-01
Publication date: 2006-09-28
Also published as: EP1866105A1; NO20073985L; CN101124051A; JP5137813B2; ES2340699T3; DE602005019628D1; US20080149540A1; JP2008534249A; NO336046B1; DK1866105T3; ATE458557T1; PT1866105E; US7674995B2; EP1866105B1; CN101124051B; FR2883493B1; FR2883493A1

Abstract

The invention concerns a method for processing postal packets including managing digital impressions of the postal packets. In a method for processing postal packets, during a preliminary sorting of the packets, a digital image of a packet comprising an address information is formed, a digital impression (V-Id) is derived from said image which constitutes a logical identifier for the packet and the packet impression is recorded in memory corresponding to data indicating the packet address information, and during a second sorting of the packets, a digital image of a current packet is formed again (51) comprising an address information, a digital impression for the current packet is derived (52) from said image and a search is performed among the recorded impressions in the preliminary sorting for a match with the current packet impression. During the preliminary sorting, the impressions of successive packets are associated in memory with corresponding chronological serial numbers. During the second sorting, for one series of impressions of successive packets for which a match has been obtained with impressions recorded in memory a first series of corresponding chronological serial numbers is retrieved (61), for a current packet a chronological serial number estimated from said series of chronological serial number is calculated and a search for a match of the current packet impression based on said estimated chronological serial number is performed (63).

Description

Shipment processing method including management of the digital footprints of shipments

The invention relates to a method for processing postal items in which, during a first sorting pass of the items, a digital picture of a mail item containing an address information is formed, and a digital print is derived from this image. is a logical identifier for sending and is stored in memory the footprint of the sending in correspondence in particular with data indicative of the address information of the consignment and in which during a second sorting pass of sendings, one again forms a digital image of a current mailing containing address information, one derives from this image a digital fingerprint for the current mailing and one looks among the fingerprints recorded in the first sorting pass a concordance with the footprint of the current shipment including to recover by association the address data of the current shipment.

With such a method, it is no longer necessary to affix on each postal item an identification code or "chronomarch" still called "IdTag" in the current literature which may be in the form of a bar code by example because it uses instead a virtual identifier sent by the footprint of the shipment. This imprint in practice is an image signature for example with two components, one of the two components characterizing for example the global and local distributions of gray levels in the image of the shipment, the other of the two components characterizing the address information contained in the image of the sending at a non-syntactic level of analysis.

The use of digital footprints, however, poses the problem of finding a match between a current digital fingerprint and a large number of registered digital fingerprints, making it difficult to meet the real-time requirements on the one hand and on the other hand a greater likelihood of confusion in concordance search. The more the current digital fingerprint is compared to a large number of registered fingerprints, the greater the probability of detecting a match between two fingerprints corresponding to two different items. Therefore, the use of fingerprints imposes to perform the concordance search of the footprints in a limited space of exploration.

In the European patent document EP1222037, a method as defined above which uses fingerprints to identify shipments but which requires in the second sorting pass to represent at the input of the machine the items sorted in the first pass respecting a certain order so that the search of concordance of the prints is realized on a space of limited exploration. For this, the sorting outlets filled with sorted items in the first sorting pass must be identified by the machine during the representation of the items in the second sorting pass and the imprints in the memory must be organized in sequence, each sequence being allocated. to a first-pass sort output bin. In practice, such a constraint of exploitation is not tenable because it is frequent that in a sorting process in several sorting passes the relative order of the items is altered between the two sorting passes, for example following the unloading of the sorting outlets in the bins, the loading of the incoming items of the machine following the fall of a bin during a handling of the bins, as a result of a trans-shipment of bins, or at the following a jamming of the machine during the second sorting pass. The object of the invention is to propose an improved and more robust mail processing method in that it makes it possible to carry out the search for fingerprint matches without depending on the operating constraint explained above.

For this purpose, the subject of the invention is a method for processing postal items in which, during a first sorting pass of the items, a digital picture of a mail item is formed, a digital print is derived from this picture. is a logical identifier for the sending and is stored in memory the footprint of the shipment in correspondence with the data of the consignment, and wherein during a second sorting pass of the shipments, one again forms an image digital of a current shipment, it derives from this image a digital footprint for the current shipment and searched among the fingerprints recorded in the first sorting pass a concordance with the footprint of the current shipment to recover by association the data of sending, characterized in that during the first sorting pass, the fingerprints of the successive items are associated in memory with corresponding chronological order numbers, during the second sorting pass, for a series of impressions of successive current items for which has obtained a match with fingerprints stored in memory in the first sorting pass a series of corresponding chronological order numbers, a chronological order number estimated from this series of chronological order numbers is calculated for a subsequent current mailing. and performing the concordance search for the subsequent current shipment from this estimated chronological order number.

The idea underlying the invention is therefore to constitute in the memory during the first sorting pass of the fingerprints sequences corresponding to sequences of items that are likely to be repeated in whole or in part in the second pass of sorting. These fingerprint sequences can be defined on the basis of the chronological order in which the items are sent to a sorting outlet of the first sorting pass. During the second sorting pass, if the start of a mailing sequence is detected based on a detection of a corresponding fingerprint sequence, it can be predicted by an estimate calculation for a current mail position of the footprint of the current mail in an ordered sequence of fingerprints recorded in the first sorting pass.

With the method according to the invention, it is possible to perform a fingerprint matching in a limited exploration space even if the sequencing of the items in the second sorting pass is not respected.

The method according to the invention can be implemented easily on an existing postal sorting installation and can be operated in a sorting process in several passes on several sorting machines assigned to sorting centers of departure and arrival, for example .

An exemplary implementation of the method according to the invention is described in more detail below and illustrated by the drawings. This description is given as an indicative and non-limiting example of the invention.

Figure 1 very schematically illustrates a mailing. FIG. 2 schematically shows a sorting machine for implementing the method according to the invention. FIG. 3 illustrates in the form of a flowchart the flow of the method according to the invention during a first sorting pass.

Figure 4 schematically illustrates the structure of the data in memory in the sorting machine. FIG. 5 illustrates in the form of a flowchart the progress of the method according to the invention during a second sorting pass.

Figure 6 illustrates by a graph the principle of calculation in the method according to the invention.

In Figure 1, there is illustrated a postal item P having a distribution address information A. This mailing can be a simple letter or a flat object of small or large format such as a magazine, a newspaper, a catalog with plastic envelope or paper, etc ....

The postal sorting machine 1 illustrated in FIG. 2 conventionally comprises a feed inlet 2 with a magazine for loading mailpieces P and an unstacker for placing the postal items in series on the edge, a digital camera 3 for forming a picture of the surface of each shipment having the distribution address information A and a bucket carousel 4 which directs the shipments to sorting outlets each having a sorting outlet bin 5. Each sorting outlet can be equipped with several trays (typically a front and a rear tray) sorting outlet or a compartmentalized tray without departing from the scope of the invention.

FIG. 2 also shows a data processing system associated with a video-coding system 7. The systems 6 and 7 constitute an OCR address recognition system which from an image a sending P formed by the camera 3, automatically extracting or via the intervention of a video-coding operator, the address information A on the basis of which is determined a sorting destination for the sending which corresponds at a sorting outlet of the machine. In addition, the system 6 is arranged according to the invention to derive from the digital image of a transmission formed by the camera 3 a digital fingerprint which is an image signature constituting a logical identifier for sending.

FIG. 2 also shows a system similar to the system 6 but which is part of another sorting machine 10, this system 9 being connected in communication for example by a network of telecommunication 8 to the system 6 for an application of the method according to the invention to a sorting process in several sorting passes on several sorting machines.

The method according to the invention applies to the automatic sorting of items in which shipments are first sorted in one or more sorting centers said departure, and after grouping, are sorted again in another sorting center said arrival which may be distant from the starting sorting centers.

FIGS. 3 and 5 illustrate an example of implementation of the method according to the invention in the case of sorting in two passes on the same sorting machine such as machine 1.

Referring to FIG. 3, in an initial step 11 of a first sorting pass, postal mailpieces P are injected into the sorting machine P through the feed inlet 2. The postal items P are unstacked and conveyed in series on edge to the digital camera 3. In step 12, a digital image is formed of a transmission comprising the distribution address A.

In step 13, the system 6 undertakes an automatic recognition of the address information A by OCR and at the same time derives from the digital image of the sending a digital fingerprint V-Id serving as a logical identifier for the consignment.

In step 14, if step 13 has obtained a unique address information by automatic address recognition by OCR, is recorded in memory in step 16 data representative of the address information in correspondence with the V-Id digital footprint of the shipment.

If in step 14 the automatic address recognition by OCR gives a partial result, that is to say an address information equivocal, or no result, the image of the sending is transmitted to the video system coding 7 for an extraction of the address information by a video coding operator (step 15), whereupon the data representative of the address information and the digital fingerprint are recorded in correspondence with memory in the memory. step 16.

In the method according to the invention, in step 16, each consignment is assigned a chronological order number NO which is stored in memory in correspondence with the footprint of the item. Each order number can be constituted for example by the juxtaposition of a sorting center number assigned to the sorting center in which the sorting machine 1 is located, a sorting machine number assigned to the sorting machine. in which the sending is sorted, a sort output tray number assigned to the sort output bin in which the mail is directed and a chronological index assigned to the mailing.

In practice, this index is for example the value of a counter associated with a sorting output bin and which is initialized when a first shipment is sent to the bin and which is incremented by one unit each time that a new shipment is sent to the ferry. In this way, each shipment is assigned a unique order number NO.

In FIG. 3, the structure of the database in which the digital printout V-Id, the serial number NO and the address data of sending (not shown).

In step 18, the shipment is conveyed to the corresponding sorting outlet of the machine and is unloaded in the bin of this associated sorting outlet.

The process symbolized by steps 12 to 18 is repeated for each mailpiece depilated at the input of the machine. At the end of the first sorting pass, a logical grouping of the records is carried out if necessary in the database 17 so as to group the fingerprints of the items in sequence.

In particular, in the database 17, the prints are grouped and ordered in series by sorting center, by machine and by tray according to the order in which the items are stored in each sort output bin.

FIG. 4 partially shows two fingerprint sequences. The first sequence comprises a series of V-Id imprints which are respectively associated with chronological order numbers 01407600 to 01407640 assigned to items numbered "00" to "40" stored in the bin "076" of the sorting machine "40". »Of the sorting center

"01". The second sequence comprises another series of V-Id fingerprints which are respectively associated with chronological order numbers.

014008600 to 014008640 assigned to items numbered "00" to "40" stored in the bin "086" of the sorting machine "40" of the sorting center

"01". It should be understood that the database 17 is prepared for a second pass and is organized so that the fingerprints are recorded in sequence following the progression of the chronological order numbers. Without departing from the scope of the invention, the imprints can be recorded so as to constitute sequences which are each assigned to two or more trays.

In FIG. 5, the steps of the method according to the invention are illustrated during a second sorting pass.

Shipments in the first pass sorting outlets 5 are again entered into the sorting machine 1 and are unstacked to be conveyed in series on edge toward the camera 3.

In step 51, a digital image of the surface of a current mail item containing the address information A is again formed and in step 52 a V-Id print is again derived for the current mail from of his digital image, called current imprint.

In step 52, in addition to the current mail item, a send IP passing index, said current crossing index, is also attributed. In other words, we count the successive shipments and we give the current mail a number of passage (ranging from 1 to n ...). In step 54, for the current mail, an estimated chronological order number NO is calculated. According to the invention, this calculation is performed by linear approximation from a series of chronological order numbers stored in memory in a data list 53 called list of prediction data. At the start of the second sort pass, this list of prediction data is empty.

To better understand the principle of the calculation is shown in the graph of Figure 6, an abscissa axis on which are entered through-indexes sending IP 374 to 405 which correspond to the passage in the second pass of the 374 ^th to 405 ^th items for which a hash V_Id was extracted in step 52. It was reported on the y-axis, examples of chronological serial numbers attributed to NO in the first pass items, here of items stored in bins numbered "76" and "86".

The linear approximation calculation consists, from a series of send passing index / chronological sequence number pairs (IP, NO) illustrated by a cross in FIG. 6, to be determined by an equation system the coefficients a, b of a straight line (NO = a, IP + b) such that D1 or D2 so that a chronological sequence number NO placed on this line can be calculated on the basis of a current IP crossing index.

In the method according to the invention, the dispersion of the passage index / chronological sequence number numbers recorded in the prediction data list 53 is further measured using a measure such that the root squared error EQM which makes the object of step 56.

At the beginning of the second sort pass, since there are not yet enough pass index / sequence number couples in the prediction data list 53, step 56 proceeds directly to step 57 in which the current fingerprint is searched for a match with a fingerprint recorded in the database 17 by completely scanning the entire database 17.

If a match is not obtained at step 58, the current send is sent to a reject output.

If a concordance is obtained in step 58, the address data of the consignment as well as the chronological sequence number associated with the imprint are recovered from the database 17 from this concordant footprint.

In step 60, the current send is directed to a corresponding sorting output, and in step 61, the forwarding index / chronological sequence number associated with the first signal is recorded in the prediction data list 53. current shipment. For example, for the postal item whose IP crossing index is 374, it has detected a match of its digital fingerprint with the digital fingerprint stored in the database 17 whose serial number NO is 014008628 ( see Figure 4).

The process of steps 51-61 as described above is thus repeated for successive current items and if for example five successive current items (approximately 1/20 ^th of the storage capacity of a sorting outlet bin) was obtained respectively five fingerprint matches, there was formed in the prediction data list 53, after the fifth current send, a series of five pairs passing index / chronological order number.

Now for a subsequent current sending (for example the sending of a passage index equal to 379 in FIG. 6) succeeding the transit index shipments 374 to 378, a linear approximation of the last five is carried out in step 54. couples passage index / number in chronological order recorded in the prediction data list 53 and coefficients of a line such as D1 are obtained.

In step 56, the difference between the points constituted by the last five pairs of position index / chronological order number of the prediction list 53 is measured with respect to the line D1, for example by means of a measurement EQM squared error.

If at step 56, the measured RMSE is greater than a certain threshold value, the process proceeds to step 57 as described above. If at step 56, the squared error mean measured EQM is zero (equal to zero), i.e. the series of the last five pairs passing index / chronological order number recorded in the list of data 53 are aligned perfectly on a line such as D1, the process is continued in step 62 by calculating for the current passage index (here the index 379) the estimated chronological order number which corresponds to the line D1 in the example the estimated chronological order number is 8633, and a fingerprint matching search is performed in step 63 between the current fingerprint and the fingerprints contained in an exploration space of the database. data 17 constituted by the vicinity of the fingerprint associated with the estimated chronological order number. This exploration neighborhood may for example be limited to about forty fingerprints located on either side of this associated fingerprint in the database 17.

In the case where, in step 56, the measured squared mean EQM is zero, the coefficients a and b of the straight line obtained at 54 are stored. It is understood that, in the case of a zero MSE, it has been found in FIG. second sorting pass a sequence of mailings, called perfect sequence, in which five successive items are in the same chronological order as in the first sorting pass. The passing index / chronological sequence number constituting the perfect sequence are shown in FIG. 4 by the reference SP and in FIG. 6 by the line D1. Moreover, for any new zero MSE measurement, the coefficients a and b will be replaced in memory.

If there is a match between the current fingerprint and one of the scan space fingerprints in step 64, the current mail is directed to a corresponding sorting output in step 60 and the same. step 61 we put to day the list of prediction data 53 with the pair passing index / chronological order number of this current shipment. Note that in the example, for the passage index 379, the chronological order number of the matched fingerprint is 8634 while the estimated chronological order number is 8633.

If in step 64 no fingerprint matches are found in the exploration space, a complete scan of the database 17 in step 57 is performed to search for a match. footprints as indicated above. Subsequently, the sending may be directed to a reject output (steps 58 and 59) or may be directed to a sorting output (step 60) with updating of the prediction data list 53 (step 61). .

Now if in step 56, the measured squared mean error EQM is lower than said certain threshold (5 for example) but is not zero, according to the method of the invention, the current passage index two is calculated for chronological order numbers estimated in step 65. This case is illustrated in FIG. 6 for the current passage index 386. The first order number is calculated for the current passage index (386) from the memorized coefficients a and b of the straight line D1, in the example the corresponding chronological order number on the line D1 is 8640. The second chronological order number is calculated from a line D2 obtained by linear approximation (step 54) of the last five pairs position index / chronological order number of the prediction data list 53. In the example, the second corresponding chronological order number on the line D2 is 8638.

In step 66, therefore, the difference between the first and second calculated chronological order number is measured and if this difference is less than or equal to a certain threshold, the process proceeds to step 63 by a concordance search. of fingerprints on an exploration space centered around the first calculated chronological order number and if this deviation is greater than said threshold, the process continues in step 57 by a search of fingerprint matches on the set of In practice, the threshold value in step 66 may be equal to 2.

In the example, the difference between the first (8640) and second (8638) calculated chronological order number is two. Therefore, in step 63, a search is sought for the chronological order number 8640 in the database 17. If no match is found in step 64 the process continues in step 57.

In the case where a match has been found at one of steps 58 or 64, the sending is directed in step 60 to the corresponding sorting output and the prediction data list 53 is updated at the same time. step 61.

In the example, in step 61, the current transition index pair 386 and chronological order number 8641 are recorded in the prediction data list 53, a concordance between the current digital footprint and the footprint in the database 17 having the serial number 8641 having been determined at one of steps 58 or 64 of the method.

With the method according to the invention, it is therefore possible to perform a fingerprint matching search on a limited exploration space even if the items are injected into the machine in the second sorting pass without respecting the sequencing.

The method according to the invention applies in the same way to a sorting pass subsequent to the second sorting pass as well as sorting passes made on different machines. In the latter case, the databases 17 formed on the different sorting machines in the first pass are transferred by a telecommunication network such as 8 to a second pass sorting machine where they are grouped together to constitute fingerprints like described above.

Claims

1 / Method of processing postal items in which, during a first sorting pass of the items, forming (12) a digital image of a shipment, this image is derived (15) from a digital impression (V-Id ) which is a logical identifier for the sending and is stored in memory the stamp of the sending in correspondence with the data of the consignment and in which during a second sorting pass of the shipments, one forms (51) again a digital image of a current shipment, one derives (52) of this image a digital footprint for the current shipment and one searches among the fingerprints recorded in first sorting pass a concordance with the footprint of the current shipment to recover by association the data of the consignment, characterized in that during the first sorting pass, the imprints of the successive items are associated (16) in memory with corresponding chronological order numbers (NO), during the second sort pass, we get (61) for a series of prints of successive shipments for which a record has been obtained with impressions stored in memory in the first sorting pass of a series (S1.S2) of corresponding chronological order numbers, one calculates (62.65) for a current shipment a chronological serial number estimated from this series of chronological order numbers and the concordance search (63) is performed with the stamp of the current shipment from this estimated chronological order number.

2 / A method according to claim 1, wherein the calculation of the estimated number of chronological order consists of a linear approximation.

3 / A method according to claim 2, wherein one computes (65) two serial numbers by linear approximation from two series of impressions of successive mailings and measures a difference between the two calculated chronological order numbers. . 4 / A method according to one of claims 1 to 3, wherein the concordance search is performed among the fingerprints recorded first sort pass in an exploration space centered around the fingerprint associated with a chronological order number calculated.

5 / A method according to one of claims 1 to 4, wherein the postal items are directed to sorting output bins of a sorting machine and wherein the chronological order is the loading order of the items in the sorting outlets.

6 / A method according to one of claims 1 to 5, wherein the serial number consists of the juxtaposition of a sort center number, a sorting machine number, a tray number sort output and a chronological index.

11 A mail sorting machine arranged to implement the method according to one of the preceding claims.