EP0913208B1 - Method and arrangement for determining distribution information - Google Patents

Description

The invention relates to a method and an arrangement for Determination of distribution information according to the generic terms of independent claims.

The addresses are used to determine the distribution information of shipments in processing machines, in particular sorting machines with OCR systems, read. Not from the OCR system read programs are on video slots of a video coding system shown and coded manually. A video coding system can be in a pool configuration with multiple letter sorting systems be connected. All of them are different Machine-generated images from non-machine read letters (OCR rejects) on a system of video coding stations according to certain requirements for the purpose of video coding to distribute, with both an equal distribution the load, as well as a defined prioritization of certain Machines can be requested.

According to the known state of the art e.g. DE-A-4324255, that of all processing machines on-line images of the programs through a central administration, e.g. B. an image controller managed and at the request of a video coding station switched the requesting video coding place. On-line Images are understood to be those related to the subject Time in a mechanical runtime distance of the processing machines are located. The runtime distances are required for the shipments on-line, d. H. with one machine pass encode automatically or manually via video coding to be able to. The result of the coding becomes a machine-readable Code printed on the shipments in subsequent machines can be read.

Due to the way in which coding orders are assigned to the Video coding stations for the various processing machines the image controller controls the load of each individual machine and the load distribution in the entire system pool.

The disadvantage of this solution is the fact that all coding requirements the video coding stations via a single instance, the image controller, which runs under high load Bottleneck effect can cause any coding request a video coding station from the central image controller must be processed. In Fig. 3 is the principle of the central Image management shown with Image Controller.

The invention specified in independent claims 1 and 10 the underlying problem is therefore a process and to create an associated arrangement, while at the same time Request images of the processing machines by the Video coding stations for manual coding a clearance realize with reduced waiting times.

Advantageous refinements are set out in the subclaims the invention, so to form the ranking values, for inclusion a random number in the selection of the processing machine according to the ranking value, handling different Coding modes.

• keine zentrale Verwaltungsinstanz für die Zuordnung und Verteilung von Bildern
• kein Flaschenhalseffekt unter Hochlast möglich
• nur sehr wenige Software-Komponenten
• kontinuierliche, gleichförmige Lastverteilung auf alle Maschinen und Codierplätze
• eigenstabil
• einfache Einbeziehung von Off-Line-Sendungen und unterschiedlichen Codiermodi

In summary, the solution according to the invention has the following advantages over previous centralized approaches:

• no central administration for the allocation and distribution of images
• no bottleneck effect possible under high load
• very few software components
• continuous, uniform load distribution on all machines and coding stations
• inherently stable
• easy inclusion of off-line programs and different coding modes

FIG 1

eine Prinzipdarstellung der erfindungsgemäßen Anordnung mit dezentraler Bildverwaltung,

FIG 2

den Ablauf beim Austausch der histogrammähnlich dargestellten Füll standsinformationen und

FIG 3

eine Prinzipdarstellung einer Anordnung gemäß Stand der Technik mit zentraler Bildverwaltung.

In one embodiment, the invention is explained in more detail with reference to the drawing. Show:

FIG. 1

2 shows a basic illustration of the arrangement according to the invention with decentralized image management,

FIG 2

the process of exchanging the fill level information displayed in a histogram-like manner and

FIG 3

a schematic representation of an arrangement according to the prior art with central image management.

Each sorting machine ILV has an OCR system and a local one Image management unit LIC, which is the on-line or off-line Manages images. The sorting machine ILV and all video coding stations are connected to each other via a network. 1 shows the arrangement in decentralized image management.

1.Bestimmung der Bildverwaltungseinheit, von der das nächste Bild angefordert werden soll

2.Bildanforderung (Image Request) an die entsprechende Bildverwaltungseinheit

3.Empfangen der Bilddaten und des zugehörigen Bild-Descriptors von der angesprochenen Anlage

4.Codierung des Bildes

5.Zurücksenden des Codierergebnissen zur Bildverwaltungseinheit.

The principle of the solution according to the invention is based on the fact that each video coding station independently determines the machine from which it requests the next picture to be processed. The decision about this is derived from status information which is made available to the video coding stations in a suitable manner by all processing machines involved. The following cycle for the image request of a video coding station is derived from this:

1.Determine the image management unit from which the next image should be requested

2. Image request to the corresponding image management unit

3. Receiving the image data and the associated image descriptor from the addressed system

4.Coding the picture

5. Return the coding result to the image management unit.

For the determination of the processing machine from which the Each processing machine delivers the next picture to be requested status information at cyclical intervals about the level of the transit time, e.g. in form of a Histogram-like level information H.

The mechanical transit time is in the processing machine's shipment stream arranged in front of a barcode printer and has the task of automatic distribution information recognition (OCR) as well as the one required for video coding Ensure delay time. The shipment deduction (Substance input / feeder) at the entrance of the runtime route controlled by a controller so that at a maximum Total throughput the online rate is maximized. The online rate is the relative proportion of shipments within the Residence time in the runtime route could be coded.

To calculate the level information displayed in a histogram-like manner H become equidistant intervals, for example 1 second and the respective number of Shipments of a section of the transit time the corresponding Assigned entries. Diagram 1 shows a snapshot level information displayed in a histogram-like manner H a 12 second runtime distance at the time ti. As can be seen, the runtime interval is up to 4 programs at the 1st second, 6 from the 1st to the 2nd second Shipments etc. in the transit time. In the example it is Runtime route completely filled.

The runtime route transports the consignments continuously. The model of the level information displayed in a histogram-like manner is time-discrete. The sampling (update) rate of the histogram-like level information is determined in a suitable ratio to the transport speed, the shipment parameters, shipment length and gap, and the size of the equidistant intervals. In the exemplary embodiment, the update rate and the size of the equidistant intervals are 1 second each. Diagram 1: Level information for a 12-hour runtime distance at time ti. Runtime [s] 1 2 3 4 5 6 7 8th 9 10 11 12 Number of Sdg 4 6 7 9 7 2 8th 9 10 9 6 3

The shipments are through a feeder, substance input or called feeder, fed into the runtime route. After passing through the runtime route, they arrive in the sorting area the letter sorting system, e.g. an order of Sorting compartments that are controlled via switches. The Passing through the shipments takes place through the transit time according to the FiFo principle (first in, first out). Hence the Assignment of the level information displayed in a histogram-like manner Go through H from left to right.

1. Jede Briefsortieranlage bestimmt für die nicht durch den OCR gelesenen Sendungen zyklisch eine histogrammähnlich dargestellte Füllstandsinformation H(ti) der Laufzeitstrecke mit der Aktualisierungsrate Ra [1/sec]. Diese Darstellung repräsentiert den Sendungsfüllstand zwischen den Zeitpunkten ti und ti+1.

2. Die histogrammähnlich dargestellten Füllstandsinformationen Hj (ti) aller j Maschinen werden in zyklischen Abständen unter den Sortiermaschinen ausgetauscht, so daß jede Maschine die gesamte Information über die Füllstände aller Maschinen besitzt. Auf diese Weise kann ein Videocodierplatz die Zustandsinformation aller Maschinen von jeder beliebigen Maschine abfragen und daraus die Entscheidung ableiten, von welcher Anlage das nächste Bild anzufordern ist.

3. Aus den histogrammähnlich dargestellten Füllstandsinformationen H (ti) der Laufzeitstrecke werden Rangordnungswerte für jede Anlage berechnet. Die Rangordnungswerte Ri sind z.B. positive ganze Zahlen. Die Relationen der Beträge der Rangordnungswerte repräsentieren die Verhältnisse der Füllstände der beteiligten Anlagen.

4. Die Videocodierplätze erhalten zu definierten Zeitpunkten, die sie selbst bestimmen, die jeweils aktuellen Rangordnungswerte aller Maschinen. Die aktuellen Rangordnungswerte beinhalten im Vergleich zu den Bilddaten nur verhältnismäßig kleine Datenmengen und können daher unmittelbar nach dem Abschluß eines Codiervorgangs vom Videocodierplatz angefordert werden. Alternativ kann dieses mit der Übertragung der Bilder gekoppelt werden, d.h. wenn ein Videocodierplatz ein Bild von einer Bildverwaltungseinheit anfordert, können zusätzlich zu den Bilddaten auch die aktuellen Rangordnungswerte aller Anlagen übertragen werden. Damit wird die Anzahl der erforderlichen Messages reduziert.

5. Jeder Videocodierplatz bestimmt für jedes neu anzufordernde Bild durch einen individuellen Entscheidungsprozeß, von welcher Anlage das nächste Bild angefordert wird. Dazu werden die aktuellen Rangordnungswerte Ri verwendet. Erfindungsgemäß werden die Rangordnungswerte so mit einem gleichverteilten Zufallsprozeß Z überlagert, daß die Wahrscheinlichkeit Pi des Bildrequests von einer bestimmten Maschine i proportional der relativen Größe des betreffenden Rangordnungswertes Ri entsprechend Formel (I) wird. Ri (I)   Pi = RiΣ Ri Die Zufallsüberlagerung für den Entscheidungsprozeß, von welcher Anlage das nächste Bild angefordert wird, ist notwendig, um zu vermeiden, daß alle Videocodierplätze zu einem Zeitpunkt von der Sortieranlage Bilder anfordern, die den maximalen Rangordnungswert besitzen. Dies wäre sonst möglich, da alle Videocodierplätze prinzipiell zu einer Zeit die gleiche Information über den Sendungs-Füllstand der Sortieranlagen in Form der histogrammähnlich dargestellten Füllstandsinformation H (ti) der Laufzeitstrecke haben. Weiterhin sorgt die Zufallsüberlagerung für eine möglichst gleichförmige Lastverteilung zwischen allen Videocodierplätzen und den Sortiermaschinen gemäß der Rangordnung.

6. Die Rangordnungswertbestimmung und Zufallsprozeßüberlagerung werden so gestaltet, daß

• die On-Line-Rate maximiert,
• der Gesamtanlagendurchsatz maximiert wird.
  Für die Rangordnungswertbestimmung kommen sowohl lineare als auch nichtlineare Überlagerungen von Funktionen zwischen der Laufzeit Di der Laufzeitstrecke und der betreffenden Anzahl von Sendungen Ni in dem betrachteten Laufzeitstreckensegment in Betracht. So kann in einem einfachen Fall der Rangordnungswert als Summe aller Füllstände, d.h. der Gesamtzahl der in der Laufzeitstrecke befindlichen Sendungen bestimmt werden (IIa). In einem anderen Ansatz kann die aktuelle Position linear oder nichtlinear in den Rangordnungswert eingehen (IIb und IIc). Andererseits kann nur ein relevanter (aber variabler) Teil der Laufzeitstrecke für die Rangordnungswertbestimmung herangezogen werden, wie z.B. in (IId), wo nur die letzten io Positionen, die ungleich Null Füllstände aufweisen, herangezogen werden. In (IIe) schließlich werden nur die Quadrate der letzten Positionen für die Rangordnungswertberechnung verwendet.
  
  
  
  
  

The procedure for decentralized image management is described below.

1. Each letter sorting system cyclically determines a histogram-like fill level information H (ti) for the transit time with the update rate Ra [1 / sec] for the mail items not read by the OCR. This representation represents the consignment fill level between the times ti and ti + 1.

2. The histogram-like level information Hj (ti) of all j machines is exchanged at cyclic intervals among the sorting machines, so that each machine has all the information about the level of all machines. In this way, a video coding station can query the status information of all machines from any machine and derive the decision from which system the next picture is to be requested from.

3. Ranking values for each system are calculated from the fill level information H (ti) of the transit time, which is similar to the histogram. The ranking values Ri are, for example, positive integers. The relationships of the amounts of the ranking values represent the ratios of the fill levels of the plants involved.

4. The video coding stations receive the current ranking values of all machines at defined times that they determine themselves. The current ranking values contain only relatively small amounts of data in comparison to the image data and can therefore be requested from the video coding station immediately after a coding process has been completed. Alternatively, this can be coupled with the transmission of the images, ie if a video coding station requests an image from an image management unit, the current ranking values of all systems can also be transmitted in addition to the image data. This reduces the number of messages required.

5. Each video coding place determines for each new picture to be requested by an individual decision process from which system the next picture is requested. The current ranking values Ri are used for this. According to the invention, the ranking values are superimposed with a uniformly distributed random process Z in such a way that the probability Pi of the image request from a specific machine i is proportional to the relative size of the relevant ranking value Ri according to formula (I). Ri (I) Pi = Ri Σ Ri The random overlay for the decision-making process as to which system the next picture is requested from is necessary in order to avoid that all video coding places request pictures from the sorting plant at a time which have the maximum ranking value. Otherwise, this would be possible, since all video coding stations in principle have the same information about the consignment fill level of the sorting systems at one time in the form of the fill level information H (ti) of the transit time distance, which is represented in a histogram-like manner. The random overlay also ensures that the load distribution between all video coding stations and the sorting machines is as uniform as possible in accordance with the ranking.

6. The ranking value determination and random process overlay are designed in such a way that

• maximizes the online rate,
• the overall plant throughput is maximized.
  Both linear and non-linear superpositions of functions between the transit time Di of the transit time segment and the relevant number of mail items Ni in the considered transit time segment are considered for the ranking value determination. In a simple case, the ranking value can be determined as the sum of all fill levels, ie the total number of items in the transit time (IIa). In another approach, the current position can be linear or non-linear in the ranking value (IIb and IIc). On the other hand, only a relevant (but variable) part of the runtime distance can be used for the ranking value determination, such as in (IId), where only the last io positions that have non-zero fill levels are used. Finally, in (IIe) only the squares of the last positions are used for the ranking value calculation.
  
  
  
  
  

Prioritization is desirable in certain operating cases (e.g. if a machine is filled with online mail becomes). The necessary uneven distribution of the load of the Machines can be ranked by an additional factor be achieved, the factors accordingly the priority of each machine.

For each coding mode required, the local Image management units a histogram-like Level information managed and shared with the others communicated local image management units. Will the Video coding stations operated in different coding modes, so everyone just demands the ranking values relevant to his fashion from a local image management unit and determines the sorting machine from which the next picture is requested.

The decentralized image management method according to the invention requires that the histogram-like level information H (ti) cyclically among the local involved Image management units LIC1 to LIC4 are exchanged.

2 shows the principle in which the fill level information Hist from one to the next local image management unit LIC1 - LIC4 is passed on. Every image management unit LIC gives the LIC received from the other image management units information displayed similar to a histogram and complements them with your own updated values. This approach comes with a minimum of information exchanged (Messages).

In this way, after a message circulation, all local Image management units LIC the same level of information. After the data comparison, each local image management unit calculates LIC the ranking values according to the same calculation rule Ri for every system. These are then from the video coding stations queried if necessary.

The goal of random overlay is to make a decision for the selection of one for the next picture request at the Based on the list of the current ranking values Ri. According to the invention, a random decision is made the one corresponding to the relations of the ranking values Ri Plant selection probability guaranteed.

The random overlay can be implemented as follows:
In a random process, a positive integer between 1 and N is generated. In accordance with the calculated ranking values Ri of the machines, an interval Li corresponding to the relative rank Ri is defined for each machine (ILV system). (III) Li = N * Rj Σ Ri

The intervals Li are successively defined by lower and upper threshold values Si0 and Si1, which are determined according to recursion rule (IV) and (V): (IV) Sj0 = S (j-1) 1 + 1 with S (j = 0) 1 = 0 (V) Sj1 = S (j-1) 1 + N * Rj Σ Ri

Then an evenly distributed random number between 1 and N generated, the machine j is selected if the random number falls in the interval Lj.

1.Bestimmung aller Rangwerte Ri

2.Bestimmung der Intervalle mit den Schwellwerten Sj0 und Sj1 für alle Maschinen j nach (IV) und (V)

3.Bestimmung einer Zufallszahl Z zwischen 1 und N

4.Bestimmung der Maschine j, für die gilt: Sj0 <= Z <= Sj1

The selection of the machine from which the next image is requested according to the decentralized image management approach is summarized according to the following scheme:

1.Determination of all ranking values Ri

2.Determination of the intervals with the threshold values Sj0 and Sj1 for all machines j according to (IV) and (V)

3. Determination of a random number Z between 1 and N.

4.Determination of machine j, for which the following applies: Sj0 <= Z <= Sj1

A pool configuration consisting of three sorting machines M1, M2 and M3 is considered as an example. The histogram-like fill level information of the transit times H1, H2 and H3 are known at time t1 and are shown in the following assignment table. sorting machine D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 M1 (t1) 2 3 4 5 6 7 3 0 0 0 0 0 M2 (t1) 3 4 5 6 7 8th 9 5 6 3 0 0 M3 (t1) 4 5 6 5 4 0 0 0 0 0 0 0

und bewertet bei entsprechender Wahl von io das Quadrat des höchsten Histogramm-Index mit einer Belegung ungleich Null. Die quadratische Wichtung bewirkt, daß mit steigender Verweildauer einer Sendung in der Laufzeitstrecke das 'Gewicht' progressiv ansteigt. Dies ist in Hinblick auf eine Maximierung der On-Line-Rate vorteilhaft, d.h. die Bilder, die uncodiert die Laufzeitstrecke passieren, werden minimiert.A simple non-linear approach for the ranking value calculation of the exemplary embodiment is according to (IIe)

and, if io is selected accordingly, evaluates the square of the highest histogram index with a non-zero assignment. The quadratic weighting means that the 'weight' increases progressively as the duration of a shipment in the transit time increases. This is advantageous in terms of maximizing the on-line rate, ie the images that pass the runtime path uncoded are minimized.

R1(t1) = 49

R2(t1) = 100

R3(t1) = 25

The decisive indices for the ranking are D7 for M1, D10 for M2 and D5 for M3. This results in the ranking values at time t1:

R1 (t1) = 49

R2 (t1) = 100

R3 (t1) = 25

Intervall 1: S10 = 1 bis S11 = 28

Intervall 2: S20 = 29 bis S21 = 86

Intervall 3: S30 = 87 bis S31 = 100

This gives the three intervals:

Interval 1: S10 = 1 to S11 = 28

Interval 2: S20 = 29 to S21 = 86

Interval 3: S30 = 87 to S31 = 100

N = 100 was assumed. Now by one evenly distributed random process a number between 1 and 100 determined, e.g. 73, then sorting machine 2 becomes the next one Image requested because the number 73 contained 2 in the interval is.

Shipments from the runtime of a sorting machine run out without the coding result being ready Off-line broadcasts. The pictures of these programs are in the local image management units saved. The saved Off-line pictures become the video coding stations on their Transfer request if there are no online images in the Runtime route are available.

The number of stored off-line items in a processing machine ILV can be similar to histogram in addition Level information shown as an offline ranking value can be used to optimize the off-line coding.

Claims (10)

1. Method for determining distribution information which is located on the surface of items of mail processed in a plurality of processing machines (ILV), in which, in each processing machine, images of surfaces of items of mail containing the distribution information are recorded and the distribution information is automatically read and, following unambiguous detection of the distribution information during FIFO buffering of the items of mail in a mechanical run-time section, these are in each case provided with an appropriate code, and in which the items of mail with distribution information which is not unambiguously detected automatically are encoded manually, by the images with this distribution information being transmitted to at least one video encoding station (VCD) and encoded there, characterized in that

   in each processing machine (ILV), the images of the items of mail whose distribution information has not been unambiguously detected automatically during the FIFO buffering of the items of mail are stored and managed,

   in each processing machine, at regular time intervals, an item of status information Hi relating to the filling level of the mechanical run-time section is generated at equidistant times over the entire storage time period,

   this status information Hi about the run-time sections is interchanged regularly between the processing machines (ILV),

   from the current status information Hi, in each processing machine (ILV) rank order values Ri are determined at regular intervals in accordance with standard rules, the respective rank order value depending on the magnitude of the filling level of the mechanical run-time sections,

   each video encoding station (VCD) requests the current rank order values Ri of all the processing machines as required from any processing machine and, from these rank order values Ri, carries out a randomly superimposed selection, in accordance with standard rules, of the processing machine from which the next image with the distribution information to be encoded is requested, the current rank order values Ri having superimposed on them an individual random process such that the probability of the image request is proportional to the relative magnitude of its rank order values Ri.
2. Method according to Claim 1, characterized in that the rank order value Ri is the sum of the items of mail Ni located in the run-time section at the current time

   
3. Method according to Claim 1, characterized in that the rank order value Ri is formed from the sum of the items of mail located in the run-time section at the various delay times, weighted with the duration of the delay Di.
4. Method according to Claim 3, characterized in that the duration of the delay Di is incorporated linearly in the rank order value Ri.
5. Method according to Claim 3, characterized in that the duration of the delay Di is incorporated nonlinearly in the rank order value Ri.
6. Method according to Claim 1, characterized in that only the items of mail located in the run-time section for a relatively long time are used to determine the rank order value.
7. Method according to Claims 1 to 6, characterized in that a machine-related weighting factor is additionally incorporated in the rank order value.
8. Method according to Claims 1 to 7, characterized in that, in order to select the processing machine (ILV) from which the next image is requested by the respective video encoding station (VCD), a random number is formed in the respective video encoding station in a numerical range which is the same for all video encoding stations, the random number range is subdivided into intervals which are assigned to the processing machines and whose magnitude is determined by the rank order values, and the image is requested from the processing machine in whose associated numerical range the random number lies.
9. Method according to Claims 1 to 8, characterized in that, in the case of video encoding stations operated in different encoding modes, the management of the images, the formation of the rank order values and the selection of the processing machines are carried out separately in accordance with items of mail for the various modes.
10. Arrangement for determining distribution information which is located on the surface of items of mail, comprising a plurality of processing machines (ILV) which in each case comprise an image recording apparatus for surfaces of items of mail having distribution information from separated items of mail, an OCR system, connected thereto, for automatic distribution information detection and encoding, a mechanical run-time section, in which the items of mail to be processed are buffered in accordance with a FIFO rule after the images have been recorded, in order to determine and to encode the distribution information in this time, and a barcode printer for the encoded distribution information, and comprising one or more video encoding stations, connected to the processing machines via a network, for the manual encoding of the distribution information not detected unambiguously by the OCR system, characterized in that

    each processing machine (ILV) has an image management unit (LIC) for the images of the items of mail located in the run-time section whose distribution information has not been detected unambiguously by the OCR system,

    all the image management units (LIC) are connected to one another and to the video encoding stations (VCD) via the network,

    in each image management unit (LIC), the times of the items of mail running into the associated run-time section are registered and, from this, at regular time intervals, status information Hi about the filling level of the run-time sections is formed via the delay run time, and this status information Hi from the image management units (LIC) of all the processing machines is interchanged regularly amongst them via the network, so that the status information Hi relating to all the image management units (LIC) is present in each image management unit (LIC),

    in each image management unit (LIC), at regular intervals, rank order values Ri are determined from all the status information in accordance with standard rules, the respective rank order value Ri depending on the magnitude of the filling level of the run-time section and

    each video encoding station (VCD) requests the current rank order values Ri of all the processing machines (ILV) via the network as required from the image management unit (LIC) of any processing machine (ILV) and, from these rank order values Ri, in accordance with standard rules, carries out a randomly superimposed selection of the processing machine (ILV) from which the next image with the distribution information to be encoded is requested, the current rank order values Ri having superimposed on them an individual random process such that the probability of the image requests is proportional to the relative magnitude of their rank order value Ri.

Images