Beschreibung

Verfahren zur Identifizierung von zu sortierenden Sendungen

Die Erfindung betrifft ein Verfahren zur Identifizierung von zu sortierenden Sendungen nach dem Oberbegriff des Anspruches 1.

In einzelnen Schritten einer Postsortierung werden unter- schiedlichste Informationen, insbesondere Zustellinformationen, aus den zu bearbeitenden Sendungen extrahiert, die für die deren Bearbeitung benötigt werden. Diese sind insbesondere Informationen über den Zustellort der Sendung. Einige dieser Informationen werden nicht nur einmalig, sondern in un- terschiedlichen Sortierstufen mehrfach benötigt. Um Sendungen effizient verarbeiten zu können, werden diese Informationen nach der ersten Erfassung in einer Datenbank gespeichert. Um diese Informationen später einer Sendung wieder zuordnen zu können, wird sie mit einem eindeutigen ID-Code (ID = Identifizierung) wie einem Barcode bedruckt. Mit Hilfe dieses ID-Codes können gespeicherte Daten zu jedem beliebigen Zeitpunkt einer Sendung wieder zugeordnet werden. Voraussetzung dafür ist z.B. ein Barcodeleser, der den ID-Code einer Sendung ermittelt und anhand des Codes die zugehörigen Infor- mationen aus der Datenbank abruft.

Der Einsatz von Barcodelesern verursacht hohe einmalige aber auch hohe laufende Kosten in einer Postsortiermaschine. Zum einen werden dazu Barcodedrucker und -leser benötigt, die re- gelmäßig gewartet und mit Tinte befüllt werden müssen. Zum anderen müssen in Plastik verpackte Sendungen mit speziellen Detektoren erkannt und mit Labein versehen werden, um ein Aufbringen von Barcodes überhaupt zu ermöglichen.

Das Lesen von Zustelladressen in unterschiedlichen Sortierstufen zur Bearbeitung aller Sendungen ist sehr zeitaufwendig

und aufgrund des hohen zu sortierenden Postaufkommens in der Praxis nicht denkbar.

üblicherweise ist das Postaufkommen sehr hoch, was eine große Menge zu speichernder ZustellInformationen und somit zu unterscheidender Sendungen zur Folge hat. Eine sichere Identifikation innerhalb z.B. eines nationalen Suchraumes ist dabei nahezu aussichtslos . Insbesondere treten häufig Sendungen auf, die sich in ihrer Struktur kaum unterscheiden und somit leicht verwechselbar sind.

In EP 1 222 037 Bl ist ein Verfahren bekannt, das eine erste Einschränkung des Suchraumes für Sendungen bewirkt und somit eine weitere Identifikation von zu sortierenden Sendungen mittels eines bildbasierten Verfahrens erleichtert. Dabei wird eine physische Reduktion des Suchraumes in einem Post- sortierprozess eingesetzt.

Der Erfindung liegt die Aufgabe zugrunde, ein schnelles und sicheres Verfahren zur Identifizierung von Sendungen anzugeben .

Dabei sollte das Verfahren auch möglichst hohe qualitative Sortiereigenschaften gewährleisten.

Erfindungsgemäß wird die Aufgabe durch die Merkmale des Anspruches 1 gelöst.

Dabei wird ein Verfahren zur Identifizierung von zu sortierenden Sendungen vorgeschlagen, bei welchem erfindungsgemäß die Sendungen nach einer Extraktion eines Merkmals gruppiert werden, welches durch einen minimalen Erkennungsaufwand und durch eine hohe Diskriminierungsfähigkeit bezüglich des aktuellen Suchraumes bedingt/gekennzeichnet ist.

In anderen Worten wird ein Merkmal adaptiv derart ausgewählt, dass gegenüber anderen möglichen verwendbaren Merkmalen und deren Erkennungsaufwand die Erkennung dieses Merkmals schnei-

ler erfolgt und sich eine damit verbundene Suchraumeinschränkung ergibt .

Außerdem können anstelle eines Merkmals mehrere Merkmale der Sendung extrahiert werden, welche sich durch einen minimalen Erkennungsaufwand und eine hohe Diskriminierungsfähigkeit auszeichnen. Dadurch wird bei der Sortierung die Qualität der Identifizierung wesentlich erhöht bzw. gesichert. Aufgrund des niedrigen Aufwands zur Erkennung dieser Merkmale bleibt das erfindungsgemäße Verfahren trotz der Vielzahl von verwendeten, jedoch leicht erkennbaren Merkmalen schnell.

Bei der Suchraumeinschränkung der Sendungen werden die erkennbaren Merkmale je nach Erkennungsaufwand und ihrer Dis- kriminierungsfähigkeit hierarchisch angeordnet, derart dass zunächst ein erstes Merkmal mit niedrigem Erkennungsaufwand und hoher Diskriminierungsfähigkeit und anschließend ein zweites Merkmal mit höherem Erkennungsaufwand und hoher Diskriminierungsfähigkeit bezüglich des eingeschränkten Suchrau- mes zur Identifizierung der Sendung verwendet wird.

Das erste Merkmal kann mindestens ein globales Sendungsmerkmal umfassen, vorzugsweise eine Information über Farbigkeit, Form, Größe, Struktur, Textur der Sendung und/oder weitere sendungsabhängige Eigenschaften. Dadurch wird z.B. eine erste gruppenförmige Suchraumeinschränkung bei der Sortierung von

Sendungen rasch gewährleistet, sowie gleichzeitig eine erste Zuordnung und Registrierung dieser Gruppen festgelegt. Ferner wird ein einzelnes Merkmal wie einem Barcode oder einer Zustellanschrift in unterschiedlichen Sortierungsstufen zunächst nicht verwendet. Dafür wird/werden ein oder mehrere

Merkmale verwendet, das/die zusätzlich zügige Erkennungen von Postsendungen bei gleichzeitiger Suchraumeinschränkung ermöglicht (en) .

Weiterhin kann das zweite oben zitierte Merkmal zumindest ein auf der Sendung lokal angeordnetes Merkmal umfassen, welches sich nun auf einen Bereich der Sendung bezieht, vorzugsweise eine Briefmarke, ein Barcode, ein Stempelaufdruck, ein Text- feld, ein Logo, ein Symbol, ein Werbeausdruck, ein Bild, etc. Das zweite Merkmal dient der finalen Identifikation der Sendung oder ihrer Rückweisung.

Insbesondere wird das zweite Merkmal zur Vereinzelung von mittels des ersten Merkmals gruppenförmig sortierten Sendun- gen verwendet. Unter dem Begriff „eines ersten und zweiten

Merkmals" sind auch eine „erste und zweite Gruppe von Merkmalen" zu verstehen. Beispielsweise wird zunächst die Farbe und die Form der Sendung als erstes Merkmal und anschließend die Briefmarke und ein Werbeausdruck als zweites Merkmal erkannt, da diese Merkmale strategisch zur optimalen Identifikation von gruppierten bzw. vereinzelten Sendungen oder zur Zurückweisung von Sendungen führen.

Als erstes und/oder zweites Merkmal kann ebenfalls ein Merk- malsdatensatz (bzw. -vektor wie unten beschrieben) verwendet werden .

Zur Ablegung und Zuordnung eines verwendeten erkennbaren ersten Merkmals wird ein einfacher Merkmalsvektor verwendet, bei welchem z.B. die Zuordnung in Abhängigkeit des Erkennungsauf- wands und der Diskriminierungsfähigkeit (steigend/absteigend) erfolgt.

Dafür muss auch der Erkennungsaufwand und die Diskriminie- rungsfähigkeit in Abhängigkeit von einem adaptiven Strategienprotokoll ermittelt werden, bei welchem für einen Suchraum relevante Merkmale verwendet und für diesen Suchraum nicht oder schlecht diskriminierende Merkmale ausgeschlossen werden.

Solche Strategienprotokolle werden für den aktuellen Suchraum ermittelt ijnd bei der Identifikation von Sendungen in späteren Sortierphasen abgerufen und eingesetzt.

Insbesondere können dafür z.B. die zweiten Merkmale in einem markierten und strukturierten Graph eingetragen werden, welcher zusätzlich die Lage der Merkmale sowie ggf. weitere diskriminierende Merkmale wiedergibt.

Daher kann eine neue Technologie zum Einsatz kommen, welche die Zuordnung von einer Sendung zu den zugehörigen gespeicherten Informationen ohne Verwendung eines speziell aufgedruckten ID-Codes ermöglicht. Dazu werden dabei eindeutige sendungs- und/oder bildhafte Merkmale aus der Sendung extra- hiert. Diese dienen als Schlüssel für den zugehörigen Datenbankeintrag im Sortierprozess und sollen somit eine Zuordnung von Sendung und Sendungsdaten gewährleisten. Im Folgenden wird dieser Schlüssel auch als Merkmalsdatensatz bezeichnet.

Im ersten Sortierschritt werden für jede Sendung bildhafte Merkmale extrahiert und parallel zu weiteren extrahierten Sendungsdaten in der Datenbank gespeichert. Sind die Merkmalsdatensätze aller zu bearbeitenden Sendungen erfasst, so werden sie bezüglich ihres ξrkennungsaufwandes und ihres Dis- kriminierungsaufwandes analysiert. Dabei wird für den gesamten Suchraum ein adaptives Strategienprotokoll ermittelt, dass den Einsatz der ermittelten Merkmale vorgibt. Sollen die extrahierten Sendungsdaten einer Sendung wieder zugeordnet werden, so muss für die aktuelle Sendung der Merkmalsdaten- satz berechnet und der korrespondierende Merkmalsdatensatz in der Datenbank bestimmt werden. Im Gegensatz zu einem ID-Code unterliegt ein solcher Merkmalsdatensatz bestimmten Schwankungen. Die Merkmalsdatensätze unterschiedlicher Bilder aber von ein und derselben Sendung müssen nicht zwangläufig exakt übereinstimmen, jedoch wird durch den Einsatz spezieller Abstandsmetriken eine sichere Identifikation gewährleistet.

Bei den hohen Anforderungen der Postsortierung werden folgεn de weitere Vorteile des Verfahrens ebenfalls gewährleistet:

- Robustheit aufgrund der Verwendung mehrerer ggf. redundan- ter erkennbarer Merkmale,

- hohe Identifikationsraten mit extrem niedrigen Erkennungsraten,

- mögliche effektive Rückweisungen von Sendungen,

- Echtzeitfähigkeit, d.h. das Vorliegen des Identifikations- ergebnisses innerhalb einer definierten Zeit von wenigen Millisekunden,

- Verwendung von Merkmalen, die eine bestimmte Speicherkapazität nicht überschreiten, als eine Voraussetzung für den Einsatz eines solchen Verfahrens in der Postsortierung.

Vorteilhafte Ausgestaltungen der Erfindung sind ebenfalls in den Unteransprüchen dargelegt.

Anschließend wird die Erfindung in einem Ausführungsbeispiel anhand der Zeichnungen erläutert.

Dabei zeigen

FlG 1 Merkmalsdatensatz einer Sendung bestehend aus zwei Arten von erkennbaren Merkmalen,

FIG 2 Gruppierung von Sendungen anhand ausgewählter Merkmale,

FIG 3 Hierarchischer Aufbau des Identifikationsver- fahrens zur schrittweisen Reduktion des Suchraums .

FlG 1 zeigt ein Merkmalsdatensatz einer Sendung bestehend aus zwei Arten von erkennbaren Merkmalen: den globalen Sendungs- merkmale featurel, feature2, ... featureN (z.B. Textur, Far-

be, Größe, etc.) und den lokalen Merkmale roiO_featureO, ..., roiO_featureM, roil_featureO, ..., roil_featureM, roi2_featureO, ... , roi2_featureM, roi3_featureO, ... , roi3_featureM in hier vier strategisch gewählten Bereichen roiO, roil, roi2, roi3 der Sendung. In FIG 1 kann als einer der Bereiche roiO, roil, roi2, roi3 z.B. eine Briefmarke definiert werden, da dieser Bereich sehr einfach zu lokalisieren und zu erkennen ist. Die globalen Sendungsmerkmale und die lokalen Merkmale bilden einen charakteristischen, sen- dungsbeschreibenden Merkmalsdatensatz. Zwischen den lokalen Merkmalen bestehen die Beziehungen relation_i_j (i, j=0, 1, 2, 3 mit i≠j ) , über welche die Identifikation über lineare Kombination bzw. Zuordnung von Merkmalsvektoren der lokalen Merkmalen verfeinert bzw. besser gesichert werden kann.

Um große Sendungsmengen sicher und effizient bildhaft identifizieren zu können, muss der Suchraum schrittweise eingeschränkt werden. Der frühzeitige Ausschluss von Sendungen aus dem Bearbeitungsprozess vereinfacht und beschleunigt die I- dentifikation einer Sendung und erlaubt den Einsatz komplexer Methoden für schwer unterscheidbare Sendungen. Zur Reduktion des Suchraumes werden im Allgemeinen zunächst einfach zu bestimmende und robuste Merkmale verwendet. Anschließend kann die Struktur einer Sendung genauer analysiert werden.

Aus diesem Grund werden wie, in FIG 1 dargestellt, die zwei Arten von Merkmalen unterschieden:

- ein oder mehrere globalen Sendungsmerkmale, die allgemeine Informationen über die Farbigkeit, Form, Größe, Struktur und/oder Textur einer Sendung beinhalten und leicht zu extrahieren sind und

- ein oder mehrere lokale Merkmale, die sich auf bestimmte Regionen einer Sendung beziehen und diese und ihre Relationen zueinander näher beschreiben.

FIG 2 zβicrt eine GruDDierung von Sendungen anhand ausgewählter Merkmale. Mittels der globalen Sendungsmerkmale feature4 und feature7 soll eine schnelle Reduktion des Suchraumes er- folgen. Dazu werden Sendungen, die sich anhand der ausgewählten Merkmale feature4 und feature7 ähneln in Gruppen bzw. Clustern clusterl und cluster2 zusammengefasst . Sendungen innerhalb eines solchen Clusters können dann mit Hilfe komplexer Methoden analysiert werden. Von entscheidender Bedeutung für die Identifikation einer Sendung ist neben der Auswahl geeigneter Merkmale die Repräsentation der Merkmale. Globale Merkmale werden durch einen Merkmalsvektor dargestellt. Diese Repräsentation bildet die Basis für Verfahren zum Clustern bzw. zur Gruppierung und zum Aufbau einer Hie- rarchie von Identifikationsverfahren.

Die lokalen Merkmale beschreiben interessierende Regionen einer Sendung genauer. Interessierende Regionen können unterschiedlicher Art sein. Im Allgemeinen sind es strukturell oder inhaltlich zusammenhängende Gebiete eines Sendungsbildes. Dabei kann es sich um typisch postalische Objekte wie Briefmarken, Barcodes, Stempelaufdrucke, Textfelder jeglicher Art, Logos, Symbole, Werbeaufdrucke oder aber auch beliebige andere z.B. bildhafte Objekte handeln. Diese Regionen können durch allgemeine bildhafte Merkmale oder durch typbezogene

Merkmale beschrieben werden. Ziel ist eine typorientierte Beschreibung zur besseren Unterscheidbarkeit von Sendungen. So können beispielsweise für Textregionen andere Merkmale zum Einsatz kommen als für Regionen, die ein Symbol enthalten. Neben dieser Beschreibung ist auch die Lage der Regionen innerhalb der Sendung und zueinander ein wichtiges Merkmal . Zusammengefasst kann mit Hilfe der lokalen Merkmale die Struktur einer Sendung in einem bestimmten Kontext sehr abstrakt aber auch sehr detailliert beschrieben werden. Eine optimale Repräsentation dieser Art von Merkmalen bietet ein struktu-

rierter und markierter Graph, der bereits in FIGl verdeutlicht wurde.

Die Kopplung beider Merkmalsrepräsentationen mit den zugehö- rigen globalen und lokalen Merkmalen bzw. Merkmalvektoren stellt den Merkmalsdatensatz einer Sendung dar, der sie abstrahiert beschreibt. Für jede zu bearbeitende Sendung muss ein solcher Merkmalsdatensatz bestimmt und in einer Datenbank abgelegt werden.

Mit Hilfe der beschriebenen Merkmale kann eine Hierarchie von Identifikationsverfahren ermittelt werden. Dabei werden zunächst die berechneten Merkmalsdatensätze aller Sendungen betrachtet. Mittels spezieller Verfahren werden die Merkmale oder Gruppen von Merkmalen auf ihre Diskriminierungsfähigkeit hin untersucht und entsprechend ihrer Bedeutung sortiert . Durch spezielle Verfahren, insbesondere Clusteralgorithmen wird eine an den aktuellen Suchraum adaptierte Hierarchie von Identifikationsverfahren erzeugt. FIG 2 zeigt beispielhaft das Ergebnis einer solchen Clusterung.

Diese Hierarchie wird in FIG 3 durch einen Entscheidungsbaum repräsentiert. Ein solcher Baum besteht aus markierten Knoten, Kanten und Blättern mit den folgenden Eigenschaften:

Knoten:

Jeder Knoten method4, method7 in dem Baum repräsentiert einen Cluster gemäss FIG 2 bei Identifizierung der globalen Sen- dungsmerkmalen feature4, feature7 , der beim Durchlaufen des Baumes schrittweise verfeinert bzw. reduziert wird. Des Weiteren ist jeder Knoten mit einem Identifikationsverfahren gekoppelt, mit dessen Hilfe der Weg zur nächsten Ebene des Baumes bestimmt werden kann.

Blatt:

^, ToHgS Blatt Cluster! +COItI ¹ ^XSX IP.ethod, ClilS tSr2 + COITlpl2X ITϊSthod repräsentiert dann den finalen Suchraum und enthält alle Sendungen, die sich entsprechend der zugehörigen globalen Merk- male ähneln.

Jedes Blatt ist entweder mit einer komplexen Identifikationsstrategie verknüpft oder repräsentiert eine Rückweisung re- ject .

Kante:

Jeder Knoten besitzt mindestens einen markierten Ausgang in- tervalOO, intervalOl, intervalO2, eise d.h. eine Kante, der zum nächsten verfeinerten Suchraum bzw. zur Rückweisung re- ject führt.

Im Allgemeinen wird somit die Identifikation einer Sendung zurückgeführt auf eine Suche in der berechneten Hierarchie. Eine solche Hierarchie ist immer an den initialen Suchraum adaptiert. Ergebnis dieser Identifikation ist entweder ein reduzierter Suchraum oder eine Rückweisung der aktuellen Sendung.

Im final reduzierten Suchraum wird nun die komplexe Identifikationsstrategie eingesetzt. Dazu wird auf die Graphrepräsen- tation zurückgegriffen. Der Graph der zu bearbeitenden Sendungen muss mit denen der infrage kommenden Sendungen verglichen und auf deren ähnlichkeit hin untersucht werden. Dazu müssen einzelne Regionen auf ihre ähnlichkeit hin unter Beachtung der Lagerelationen untersucht werden. Mit Hilfe spe- zieller Abstandsmetriken kann dann die ähnlichkeit bestimmt werden. Eine solche komplexe Strategie, die eine Sendung im finalen Suchraum identifizieren soll, ist nicht zwangsläufig auf das beschriebene Verfahren beschränkt. Es können unterschiedlichste Merkmale und Identifikationsstrategien einge- setzt werden, die sehr detailliert sind und somit eine Sendung sehr exakt beschreiben.

Abschließend müssen die berechneten Distanzen analysiert und

den.

Generell ermöglicht dieser Ansatz die Verwendung für den aktuellen Suchraum relevanter Merkmale und den Ausschluss nicht diskriminierender Merkmale. Diese können in unterschiedlichen Suchräumen unterschiedlich sein. Es erfolgt somit immer eine Adaption auf den aktuellen Suchraum, was zu einer zeitlichen und qualitativen Optimierung der Identifikation führt.