DE60123685T2

DE60123685T2 - Digitalsignalsegmentationbestimmung für Wasserzeichensignaleinführung und zugehörige Einführung

Info

Publication number: DE60123685T2
Application number: DE60123685T
Authority: DE
Inventors: Eric Nguyen
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2000-01-11
Filing date: 2001-01-09
Publication date: 2007-08-30
Anticipated expiration: 2021-01-10
Also published as: US6819774B2; FR2803676A1; DE60123685D1; JP2001326811A; EP1117071B1; EP1117071A1; US7283643B2; US20050018876A1; US20010016049A1

Description

Die Erfindung betrifft ein Verfahren zum Bestimmen einer Segmentierung eines Satzes von Koeffizienten, die zumindest einen Teil eines digitalen Bildes darstellen, um einen Satz von Wasserzeichenmarkierungssignalen einzufügen und zu entnehmen, und auf ein zugehöriges Verfahren zum Einfügen und Entnehmen dieser Wasserzeichenmarkierungssignale.
In gleicher Weise betrifft sie eine Vorrichtung zum Bestimmen einer Segmentierung eines Satzes von Koeffizienten, die zumindest einen Teil eines digitalen Bildes darstellen, um einen Satz von Wasserzeichenmarkierungssignalen einzufügen und zu entnehmen, und auf eine zugehörige Vorrichtung zum Einfügen und Entnehmen dieser Wasserzeichenmarkierungssignale.
Die Erfindung liegt allgemein auf dem technischen Gebiet der Wasserzeichenmarkierung von digitalen Bildern, insbesondere von Stehbildern.
Digitale Wasserzeichenmarkierungsdaten ermöglichen ein Schützen dieser Daten, beispielsweise durch Assoziieren von Urheberrechtsinformationen mit diesen oder durch Transportieren von hinzugefügten Wertdaten, wie Metadaten.
Das Wasserzeichenmarkieren umfasst in seiner allgemeinen Wirkweise ein Einfügen einer unauslöschlichen Wasserzei chenmarkierung in digitale Daten ähnlich dem Codieren von zusätzlichen Informationen in den Daten.
Das Decodieren dieser zusätzlichen Informationen ermöglicht beispielsweise ein Prüfen der eingefügten Urheberrechtsinformationen.
Diese eingefügte Wasserzeichenmarkierung muss folglich zur gleichen Zeit nicht wahrnehmbar, gegenüber bestimmten auf das digitale Bild wirkenden Verzerrungen robust sein und zu einer zuverlässigen Erfassung in der Lage sein.
Bei einer konventionellen Vorgehensweise besteht eine übliche Technik des Einfügens eines Wasserzeichenmarkierungssignals in ein digitales Bild aus einer Verwendung eines Modulationsmodells, in dem zumindest ein das digitale Bild darstellender Teilsatz von Koeffizienten gemäß diesem Modell unter Verwendung eines Gewichtungskoeffizienten moduliert wird.
Es sei ein zumindest einen Teil eines digitalen Bildes darstellender Satz von Koeffizienten X = {X_i, 1 ≤ i ≤ N} und ein Wasserzeichenmarkierungssignal der Größe P ≤ N sei w = {w_j, 1 ≤ j ≤ P} ein Pseudo-Zufalls-Signal von bekannter Verteilung und fehlendem Mittelwert, wobei die Einsetzformel lautet: X'j = Xj + b.αj.wj. mit 1 ≤ j ≤ P,wobei {X_j, 1 ≤ j ≤ P} ein Teilsatz des Satzes von Koeffizienten X, b ein Informationsbit und α_j ein Gewichtungskoeffizient sei, der auch Modulationsamplitude genannt wird.
Die Erfassung des Wasserzeichenmarkierungssignals besteht dann aus einem Erfassen, ob die Pseudo-Zufalls-Sequenz w in einen Satz von Koeffizienten eingefügt wurde, oder nicht. Diese Erfassung wird ohne ein Verwenden des Originalbildes ausgeführt und kann auf einer standardisierten statistischen Prüfung beruhen, die ein Berechnen einer Erfassungswahrscheinlichkeit ermöglicht.
Eine derartige Einfügungstechnik ermöglicht durch Einfügen eines Wasserzeichenmarkierungssignals ein Einfügen eines einzelnen Informationsbits, da die Antwort der Erfassungseinrichtung binär (ja/nein) ist. Typischerweise wird zum Einfügen eines binären Signals entweder b = 1 oder b = –1 abhängig davon verwendet, ob der Wert des einzufügenden Bits 0 oder 1 beträgt.
Um eine größere Anzahl von Informationsbits in das digitale Bild einzufügen, insbesondere wenn ein Code von C Bits erforderlich ist, der beispielsweise den Namen oder die Adresse des Eigentümers oder Autor des Bildes angibt, ist es erforderlich, das vorstehend beschriebene Einfügungsverfahren so viele Iterationen durchlaufen zu lassen, wie einzufügende Informationsbits vorliegen.
Es ist mit anderen Worten erforderlich, C Teilsätze von Koeffizienten auszuwählen und die Modulation dieser Teilsätze durch Auswählen von C Wasserzeichenmarkierungssignalen zu bewirken.
Vorzugsweise werden bestimmte Teilsätze von Koeffizienten ausgewählt, so dass die Modulationen einander nicht überlagert sind, was mit der Erfassung interferieren oder unerwünschte visuelle Effekte verursachen könnte.
Folglich steht ein Auswählen einer Partitionierung der das digitale Bild darstellenden Koeffizienten in C bestimmte Teilsätze in Frage, von denen jeder ein Informationsbit führt.
Es sind Verfahren zum von dem Inhalt des digitalen Bildes unabhängigen, beliebigen Partitionieren des Satzes von Koeffizienten bekannt.
Die Druckschrift Kutter u. a.: "TOWARDS SECOND GENERATION WATERMARKING SCHEMES", proceedings of 6th international conference on image processing, 24. Oktober 1999, (1999-10-24) bis 28. Oktober 1999 (1999-10-28), Seiten 320 bis 323, offenbart ein Wasserzeichenmarkierungsmodell, das den Ort von Bildmerkmalen zum Durchführen einer Segmentierung mit Voronoi-Diagrammen verwendet.
Der Inhalt des Bildes ist jedoch nicht räumlich homogen, was zu ungleichen Erfassungswahrscheinlichkeiten für die erfassten Bits führt, und folglich zu einer globalen Fehlerwahrscheinlichkeit bei der eingefügten Nachricht, die nicht minimal sein kann. Es ist deshalb von Vorteil, eine Partitionierung zu bestimmen, die an das Bild angepasst ist. Ist es in diesem Fall erwünscht, eine vorbestimmte Anzahl C von Wasserzeichenmarkierungsbits einzufügen, ist ebenso ein Minimieren einer Fehlerwahrscheinlichkeit zum Zeitpunkt der Entnahme der Wasserzeichenmarkierungssignale erforderlich.
Der Zweck der Erfindung liegt im Vorschlagen eines Verfahrens zum Bestimmen einer Partitionierung des mit einer Wasserzeichenmarkierung zu versehenden Signals, bei gleichzeitiger Minimierung einer Fehlerwahrscheinlichkeit bei der Erfassung der vorbestimmten Anzahl von Wasserzeichenmarkierungssignalen.
Zu diesem Zweck schlägt die Erfindung ein wie in dem beiliegenden Patentanspruch 1 dargelegten Verfahren vor.
Es ist somit möglich, eine Segmentierung eines Satzes von Koeffizienten in bestimmte Bereiche zu bewirken, was eine adaptive Partitionierung bewirkt, die eine Fehlerwahrscheinlichkeit bei der Erfassung der vorbestimmten Anzahl von Wasserzeichenmarkierungssignalen minimiert.
Gemäß einer bevorzugten Ausgestaltung der Erfindung ist der Satz von Koeffizienten ein Satz von transformierten Koeffizienten, die sich aus einer Raumfrequenztransformation eines digitalen Bildes ergeben. Diese Art von Transformation wird bei der Bildverarbeitung häufig verwendet.
Gemäß einer weiteren bevorzugten Ausgestaltung der Erfindung werden die akzeptablen Segmentierungen durch eine Baumsegmentierung der zumindest einen Teil eines Bildes darstellenden Koeffizienten erhalten.
Gemäß einer weiteren bevorzugten Ausgestaltung der Erfindung werden die akzeptablen Segmentierungen durch Segmentieren der zumindest einen Teil des Bildes darstellenden Koeffizienten in einen quaternären Baum erhalten.
Diese Implementierung ist schnell und weist eine niedrige Berechnungskomplexität auf.
Gemäß einer bevorzugten Ausgestaltung der Erfindung ist jedes der Wasserzeichenmarkierungssignale mit einem Wasserzeichenmarkierungsbit assoziiert, und ist die Fehlerwahrscheinlichkeit bezüglich der Erfassung der Wasserzeichenmarkierungssignale die Wahrscheinlichkeit des Begehens von zumindest einem Fehler bezüglich eines Bits während der Erfassung der Wasserzeichenmarkierungsbits.
Gemäß einer bevorzugten Ausgestaltung der Erfindung enthält die Minimierung der Fehlerwahrscheinlichkeit eine Maximierung einer trennbaren Menge bzw. Größe, und wird die ausgewählte Segmentierung durch Abschneiden bzw. Ausästen einer Baumsegmentierung erhalten.
Gemäß einer bevorzugten Ausgestaltung der Erfindung besteht die (Neben-)Bedingung des Minimierungsschritts darin, dass die Kardinalität der Bereiche der ausgewählten Segmentierung größer oder gleich der Kardinalität des Satzes von Wasserzeichenmarkierungssignalen ist.
Gemäß einer bevorzugten Ausgestaltung der Erfindung umfasst das Verfahren zum Bestimmen einer Segmentierung einen Schritt des Anwendens einer Verzerrung bei dem Satz von Koeffizienten vor dem Schritt des Erzeugens eines Satzes von akzeptablen Segmentierungen.
In diesem Ausführungsbeispiel umfasst das Verfahren insbesondere die Schritte:

– Erzeugen einer zentrierten Pseudo-Zufalls-Sequenz (w), die in der Größe der Kardinalzahl des Satzes von Koeffizienten gleicht, und die aus zentrierten Pseudo-Zufalls-Untersequenzen gebildet ist,
– Modulation des Satzes von Koeffizienten durch die zentrierte Pseudo-Zufalls-Sequenz, um dasselbe Informationsbit bei dem Satz von Koeffizienten einzufügen, und
– Anwenden einer Verzerrung bei dem Satz von Koeffizienten vor dem Schritt des Erzeugens eines Satzes von akzeptablen Segmentierungen.

Dieses Ausführungsbeispiel ermöglicht eine Steigerung der Robustheit einer eingefügten Wasserzeichenmarkierung gegenüber verschiedenen Nachverarbeitungen, die das Bild durchläuft.
Gemäß einer bevorzugten Ausgestaltung der Erfindung enthält das Verfahren ebenso die Anzeige der Fehlerwahrscheinlichkeit bezüglich aller Wasserzeichenmarkierungssignale.
Diese Fehlerwahrscheinlichkeit gibt die Robustheit der Einfügung der Wasserzeichenmarkierungssignale an.
Die Erfindung betrifft ebenso ein Verfahren zum Einfügen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, in ein digitales Bild, dadurch gekennzeichnet, dass es ein Verfahren zum Bestimmen einer Segmentierung wie vorstehend beschrieben und einen Schritt des Einfügens der Wasserzeichenmarkierungsbits durch Modulation der Koeffizienten jeweiliger Bereiche der Segmentierung enthält.
Gemäß einer bevorzugten Ausgestaltung der Erfindung werden die Bereiche in einer vorbestimmten Reihenfolge während des Einfügeschritts betrachtet.
Die Erfindung bezieht sich ebenso auf ein Verfahren zum Entnehmen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, aus einem digitalen Bild, dadurch gekennzeichnet, dass es ein Verfahren zum Bestimmen einer Segmentierung wie vorstehend beschrieben und einen Schritt des Entnehmens der Wasserzeichenmarkierungsbits enthält.
In gleichem Maße bezieht sich die Erfindung auf eine wie in dem beiliegenden Patentanspruch 12 dargelegte Vorrichtung.
Die Erfindung betrifft ebenso eine Vorrichtung zum Einfügen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, in ein digitales Bild, dadurch gekennzeichnet, dass sie eine Vorrichtung zum Bestimmen einer Segmentierung wie vorstehend beschrieben und eine Einrichtung zum Einfügen von Wasserzeichenmarkierungsbits durch Modulation der Koeffizienten jeweiliger Bereiche der Segmentierung enthält.
Gemäß einer bevorzugten Ausgestaltung der Erfindung ist die Einfügeeinrichtung eingerichtet, um die Bereiche in einer vorbestimmten Reihenfolge zu betrachten.
Die Erfindung betrifft ebenso eine Vorrichtung zum Entnehmen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, aus einem digitalen Bild, dadurch gekennzeichnet, dass sie eine Vorrichtung zum Bestimmen einer Segmentierung wie vorstehend beschrieben und eine Einrichtung zum Entnehmen der Wasserzeichenmarkierungsbits enthält.
Die Bestimmungs-, Einfüge- und Entnahmevorrichtungen weisen Einrichtungen zum Implementieren der vorstehend beschriebenen Ausgestaltungen auf.
Die Erfindung betrifft ebenso einen Computer, eine digitale Bildverarbeitungsvorrichtung, einen digitalen Drucker, eine Abtastvorrichtung, eine digitale Photographievorrichtung und eine digitale Kamera, die zum Implementieren des Verfahrens zum Bestimmen einer Partitionie rung und des erfindungsgemäßen Einfügeverfahrens eingerichtet sind, und/oder eine erfindungsgemäße Vorrichtung zum Bestimmen einer Partitionierung oder einer erfindungsgemäßen Einfügevorrichtung umfassen.
Diese Vorrichtungen zum Bestimmen einer Partitionierung, zum Einfügen und zum Entnehmen weisen dieser Computer, diese Abtastvorrichtung, diese digitale Photographievorrichtung und diese digitale Kamera Ausgestaltungen und Vorteile auf, die jenen unter Bezugnahme auf die Verfahren des Bestimmens einer Partitionierung und des Einfügens ähneln, die sie implementieren.
Eine Speichereinrichtung oder ein Informationsträger, der durch einen Computer oder einen Mikroprozessor gelesen werden kann, der womöglich entfernbar in den letzteren eingegliedert ist, oder nicht, umfasst Abschnitte von Softwarecodes oder Programmanweisungen, die zum Implementieren der Schritte des erfindungsgemäßen Verfahrens des Bestimmens einer Partitionierung oder des Einfügens eingerichtet ist, wenn die Speichereinrichtung oder der Informationsträger in einen Mikroprozessor oder Computer implementiert sind.
Die Ausgestaltungen und Vorteile der Erfindung ergeben sich klarer aus einem Lesen eines bevorzugten Ausführungsbeispiels, das durch die beiliegenden Zeichnungen verdeutlicht ist. Es zeigen:
1 eine allgemeine Zeichnung einer Vorrichtung zum Einfügen eines Wasserzeichenmarkierungssignals in ein digitales Bild,
2 schematisch eine Spektralzerlegung, die zum Zeitpunkt der Einfügung eines Wasserzeichenmarkierungssignals implementiert ist,
3 eine Blockdarstellung einer Vorrichtung, die zum Implementieren des Verfahrens zum Bestimmen einer Partitionierung und/oder Einfügung gemäß der Erfindung eingerichtet ist,
4 ein erstes Ausführungsbeispiel des Verfahrens zum Bestimmen einer Partitionierung eines digitalen Bildes und zur Wasserzeichenmarkierungssignaleinfügung gemäß der Erfindung,
5 ein Frequenzunterband des digitalen Bildes und eine zugehörige Baumsegmentierung,
6 ein Ausführungsbeispiel eines Verfahrens zum Suchen einer Partitionierung, das in dem Verfahren gemäß 4 enthalten ist,
7 die ausführliche Suche nach einer Partitionierung, die in dem Verfahren gemäß 6 enthalten ist,
8 ein Ausführungsbeispiel eines Wasserzeichenmarkierungssignal-Entnahmeverfahrens,
9 ein zweites Ausführungsbeispiel des Verfahrens zum Bestimmen einer Partitionierung eines digitalen Bildes und zur Wasserzeichenmarkierungssignaleinfügung gemäß der Erfindung, und
10 das zweite Ausführungsbeispiels des Verfahrens zum Bestimmen einer Partitionierung eines digitalen Bildes und zur Wasserzeichenmarkierungssignaleinfügung gemäß der Erfindung.
Das in 1 gezeigte ausgewählte Ausführungsbeispiel ist eine Vorrichtung zum Einfügen eines Wasserzeichenmarkierungssignals in einen Satz von Koeffizienten, die ein digitales Bild IM darstellen.
Dieses digitale Bild IM ist in einem Speicher 1 gespeichert und kann durch einen Satz von Koeffizienten entweder im Raumbereich oder in einem transformierten Bereich einer Raumfrequenznatur dargestellt werden, wobei die Koeffizienten im letzteren Fall hybrid sind, d. h. sowohl in dem Raumbereich als auch in dem Frequenzbereich befindlich sind. Eine derartige Darstellung des Bildes wird beispielsweise durch Verwenden eines Unterbands erhalten, das sich aus einer Raumfrequenzzerlegung des Bildes ergibt, beispielsweise eine diskrete Wavelet-Zerlegung.
Hierbei wird die Einfügung des Wasserzeichenmarkierungssignals durch eine Technik des Einfügens durch Spektrumspreizen durch Modulation der Koeffizienten einer Raumfrequenzdarstellung des Bildes bewirkt, die durch eine Raumfrequenztransformation des digitalen Bildes IM erhalten sind.
Es ist möglich, beispielsweise eine diskrete Wavelet-Zerlegung S zu verwenden, die schematisch in 2 gezeigt ist. Diese Raumfrequenzzerlegung ist auf dem Gebiet der Bildverarbeitung wohlbekannt, und nachstehend ist lediglich die Wirkweise dargelegt. Sie ermöglicht es, das Bild in Frequenzunterbänder zu unterteilen und Hybridkoeffizienten zu erhalten, das heißt Spektralkoeffizienten, die ebenso im Raum befindlich sind, hier in der Ebene des Bildes.
Das Bild IM besteht aus einer Reihe von digitalen Abtastungen. Das Bild IM wird beispielsweise durch eine Reihe von Bytes dargestellt, wobei jeder Bytewert ein Bildelement des Bildes IM darstellt, das ein Bild mit 256 Graustufen sein kann.
Die Mehrfachauflösungs-Spektralzerlegungseinrichtung besteht aus einer Schaltung zum Zerlegen in Unterbänder oder einer Analyseschaltung, die durch einen Satz von Analysefiltern ausgebildet ist, die jeweils mit Dezimierungseinrichtungen um den Faktor 2 assoziiert sind. Diese Zerlegungsschaltung filtert das Bildsignal IM in zwei Richtungen in Unterbänder von niedrigen Raumfrequenzen und hohen Raumfrequenzen. Die Schaltung weist mehrere sukzessive Analyseeinheiten zum Zerlegen des Bildes IM in Unterbänder gemäß mehreren Auflösungsstufen auf.
Das Bild IM ist hierbei beispielhaft in Unterbänder mit einer Zerlegungsstufe von 3 zerlegt.
Eine erste Analyseeinheit empfängt das Bildsignal IM und filtert dieses durch zwei digitale Filter, jeweils Tiefpass und Hochpass, in einer ersten Richtung, beispielsweise horizontal. Nach Durchlaufen von Dezimierungseinrichtungen um den Faktor 2 werden die sich ergebenden gefilterten Signale wiederum durch zwei Filter, jeweils Tiefpass und Hochpass, in einer zweiten Richtung gefiltert, beispielsweise vertikal. Jedes Signal durchläuft noch ein Mal eine Dezimierungseinrichtung um den Faktor 2. Dann werden bei der Ausgabe dieser ersten Analyseeinheit vier Unterbänder LL₁, LH₁, HL₁ und HH₁ mit der höchsten Auflösung bei der Zerlegung erhalten.
Das Unterband LL₁ enthält die Komponenten von niedriger Frequenz in beiden Richtungen des Bildsignals IM. Das Unterband LH₁ enthält die Komponenten von niedriger Frequenz in einer ersten Richtung und von hoher Frequenz in einer zweiten Richtung des Bildsignals IM. Das Unterband HL₁ enthält die Komponenten von hoher Frequenz in der ersten Richtung und die Komponenten von niedriger Frequenz in der zweiten Richtung. Schließlich enthält das Unterband HH₁ die Komponenten von hoher Frequenz in beiden Richtungen.
Eine zweite Analyseeinheit wiederum filtert das niederfrequente Unterband LL₁, um auf die gleiche Weise vier Unterbänder LL₂, LH₂, HL₂ und HH₂ mit einer mittleren Auflösungsstufe bei der Zerlegung bereitzustellen. Eine dritte Analyseeinheit filtert dann das niederfrequente Unterband LL₂, um vier Unterbänder LL₃, LH₃, HL₃ und HH₃ mit der niedrigsten Auflösung bei dieser Zerlegung bereitzustellen.
Auf diese Weise werden zehn Unterbänder und drei Auflösungsstufen erhalten. Die Anzahl von Auflösungsstufen und folglich von Unterbändern kann natürlich abweichend ausgewählt werden.
Natürlich können andere Arten von Spektraltransformation verwendet werden, wie beispielsweise blockweise diskrete Kosinus- oder Sinustransformation. Unterbänder werden dann durch Zusammengruppieren von Koeffizienten von transformierten Blöcken mit dem gleichen Spektralindex ausgebildet.
Im Allgemeinen werden Frequenzunterbänder durch Bilden eines Satzes von Raumfrequenzkoeffizienten erhalten, in die ein Wasserzeichenmarkierungssignal eingefügt werden kann.
Somit kann hierbei eines der Unterbänder betrachtet werden, um die Einfügung eines Wasserzeichenmarkierungssignals zu bewirken. Dieses Unterband stellt somit einen Satz von Koeffizienten XX mit einer Größe von beispielsweise NN bereit.
Es sei XX = {XX_i, 1 ≤ i ≤ NN} der Satz von Koeffizienten, die dieses Unterband des digitalen Bildes IM darstellen.
Natürlich könnte ein Teilsatz von Koeffizienten dieses Satzes XX betrachtet werden, der lediglich einen Teil des Unterbandes darstellt.
Zur Einfügung eines Wasserzeichenmarkierungssignals in diesem Satz von Koeffizienten XX umfasst eine Technik ein Einfügen eines Pseudo-Zufalls-Signals, und spreizt dessen Spektrum, um dieses Signal für eine spektrale oder statistische Analyse unerfassbar zu machen.
Es sei w = {w_j, 1 ≤ j ≤ P} ein Wasserzeichenmarkierungssignal der Größe P ≤ NN ein Pseudo-Zufalls-Signal mit einer bekannten Verteilung und fehlendem Mittelwert. Die üblichsten Verteilungen sind die binäre Verteilung {–1, 1}, die uniforme Verteilung über [–1, 1] und eine zentrierte, standardisierte Gauß-Verteilung N (0, 1).
Die Einsetzformel lautet: XX'i = XXj + b.αj.wj mit 1 ≤ j ≤ Pwobei {XX_j, 1 ≤ j ≤ P} ein Teilsatz des Satzes von Koeffizienten XX, b ein Informationsbit und α_j ein Gewich tungskoeffizient ist, der ebenso Modulationsamplitude genannt wird. Die Gewichtungskoeffizienten α_j werden derart bestimmt, dass die Änderung der Signale XX_j in die Signale XX'_j nach einer Wiederherstellung des Bildes nicht sichtbar ist.
Der Satz S = {XX_j, 1 ≤ j ≤ P} wird auch Träger zum Einfügen eines Informationsbits genannt.
Um ein Signal einzufügen, das durch mehrere Informationsbits gebildet werden kann, ist es nützlich, eine Partitionierung des Satzes von Koeffizienten zu bewirken, um die Anzahl von Bereichen oder Einfügungsträgern zu bestimmen, die in diesem Satz zur Verfügung stehen. Dann wird ein Informationsbit in jeden Bereich eingefügt. Die Partitionierung wird in dem betrachteten Unterband und ebenso in den anderen Unterbändern bewirkt.
Dafür empfängt die erfindungsgemäße Einfügevorrichtung 2 das gespeicherte Bild und weist eine Schaltung 11 zum Segmentieren des Bildes in einen Satz von akzeptablen Segmentierungen auf. Die Schaltung 11 ist mit einer Schaltung 12 zum Auswählen einer Segmentierung unter den akzeptablen Segmentierungen verbunden. Die Funktionsweise der Schaltung 12 ist nachstehend mittels Flussdiagrammen beschrieben, die das durch diese Schaltung verwendete Verfahren darstellen.
Die Vorrichtung weist vorzugsweise eine Einrichtung zum Anzeigen einer Fehlerwahrscheinlichkeit auf, die nachstehend offenbart ist.
Die Schaltung 12 ist mit einer Einfügeschaltung 13 verbunden, die eine Nachricht von C Bits in das durch die Schaltung 12 zugeführte segmentierte Bild einfügt. Die geeignete Einfügeeinrichtung 13 ist konventionell und ermöglicht ein Einfügen durch Modulation der verschiedenen Wasserzeichenmarkierungsbits bei den durch die Schaltung 12 bestimmten unterschiedlichen Einfügungsmedien.
Die Vorrichtung 2 ist mit einer Schaltung 3 zum Verwenden eines wasserzeichenmarkierten Bildes verbunden.
Die Schaltung 3 hängt von der gewünschten Anwendung ab. Die Funktionsweise der Vorrichtung 2 ist nachstehend mittels Algorithmen beschrieben, die das zugehörige Verfahren darstellen.
Es sei darauf hin gewiesen, dass eine Vorrichtung zum Entnehmen eines Wasserzeichenmarkierungssignals, das durch die vorstehend beschriebenen Vorrichtung in ein digitales Bild eingefügt ist, der Vorrichtung 2 ähnlich ist mit Ausnahme der Schaltung 13, die dann durch eine Entnahmeschaltung ersetzt ist.
Die Gesamtheit dieser Einfügevorrichtung 2 kann in einen Computer 10 oder eine Photographievorrichtung, eine digitale Abtastvorrichtung, eine digitale Kamera oder eine Kommunikationsvorrichtung integriert werden.
Ein derartiger Computer ist gemäß 3 gezeigt. Alle vorstehend beschriebenen Einrichtungen der Einfügevorrichtung 10 sind in einem Mikroprozessor 100, einem Festwertspeicher 102 (ROM, „Read Only Memory"), der zum Speichern eines Programms zum Bestimmen einer Partitionierung und zum Einfügen eines Wasserzeichenmarkierungssignals durch Modulation eingerichtet ist, und einem Speicher 103 mit wahlfreiem Zugriff (RAM, „Random Access Memory") eingegliedert, der Register enthält, die zum Speichern von während dem Laufen des Programms modifizierten Variablen eingerichtet ist.
Natürlich kann die Vorrichtung 11 zum Bestimmen einer Partitionierung und die Einfügeeinrichtung 12, die mit der Leseeinrichtung 13 assoziiert ist, in getrennte Computer eingegliedert werden, die dem gemäß 3 Gezeigten ähnlich sind.
Der in den Computer 10 integrierte Mikroprozessor 100 kann mit verschiedenen Peripheriegeräten verbunden sein, beispielsweise einer digitalen Kamera 107 oder einem Mikrophon 111, um mit Wasserzeichenmarkierungen zu versehende digitale Dokumente zu empfangen und zu speichern.
Die digitale Kamera 107 ermöglicht merklich eine Zuführung von Bildern, die durch Einfügen eines Wasserzeichenmarkierungssignals zu authentifizieren sind.
Dieser Computer 10 weist eine Kommunikationsschnittstelle 112 auf, die mit einem Kommunikationsnetzwerk 113 verbunden ist, um jedwede mit Wasserzeichenmarkierungen zu versehenden Bilder zum empfangen.
Der Computer 10 weist ebenso eine Dokumentenspeichereinrichtung auf, wie eine Festplatte 108, oder ist mittels eines Diskettenlaufwerks 109 zum Zusammenarbeiten mit einer entfernbaren Dokumentenspeichereinrichtung eingerichtet, wie Disketten 110. Die Disketten 110 sind beispielsweise Disketten, CD-ROMs oder DVD-ROMs.
Diese feste oder entfernbare Speichereinrichtung kann ebenso den Code des erfindungsgemäßen Einfügeverfahrens enthalten, das auf der Festplatte 108 gespeichert wird, wenn es erst ein mal durch den Mikroprozessor 100 gelesen ist.
Als Variante kann das Programm, das der Einfügevorrichtung ein Implementieren der Erfindung ermöglicht, in dem Festwertspeicher 102 gespeichert sein.
Bei einer zweiten Variante kann das Programm mittels des Kommunikationsnetzwerks 113 empfangen werden, um wie vorstehend beschrieben gespeichert zu werden.
Der Computer 10 weist ebenso einen Schirm 104 auf, der beispielsweise ermöglicht, als eine Schnittstelle mit einem Benutzer mittels der Tastatur 114 oder anderer Einrichtungen zu dienen.
Die Zentraleinheit 100 führt die Anweisungen aus, die sich auf die Implementierung der Erfindung beziehen. Bei Inbetriebnahme werden die Programme und Verfahren, die sich auf die Erfindung beziehen und in einem nichtflüchtigen Speicher, beispielsweise dem Festwertspeicher 102, gespeichert sind, in den Speicher 103 mit wahlfreiem Zugriff transferiert, der dann den ausführbaren Code der Erfindung sowie die zum Implementieren der Erfindung erforderlichen Variablen enthält. Dieser Speicher 103 mit wahlfreiem Zugriff enthält unterschiedliche Register zum Speichern der zum Laufen des Programms erforderlichen Variablen.
Ein Kommunikationsbus 101 unterstützt eine Kommunikation zwischen den verschiedenen Unterelementen des Computers 10 oder der damit verbundenen. Die Darstellung des Busses 101 ist nicht einschränkend, und der Mikroprozessor 100 ist merklich in der Lage, Anweisungen zu jedwedem Unter element direkt oder mittels eines weiteren Unterelementes zu kommunizieren.
4 zeigt ein erstes Ausführungsbeispiel eines erfindungsgemäßen Verfahrens zum Bestimmen einer Partitionierung eines Satzes von Daten und zum Einfügen eines Wasserzeichenmarkierungssignals in den Satz von Daten.
Das erfindungsgemäße Verfahren ist in der vorstehend beschriebenen Vorrichtung implementiert und enthält Schritte E1 bis E5.
Der Algorithmus zum Bestimmen einer Partitionierung und zum Einfügen eines Wasserzeichenmarkierungssignals kann zur Gänze oder teilweise in jedweder Informationsspeichereinrichtung gespeichert werden, die zu einem Zusammenarbeiten mit dem Mikroprozessor in der Lage ist. Diese Speichereinrichtung kann durch einen Computer oder einen Mikroprozessor gelesen werden. Diese Speichereinrichtung ist in die Vorrichtung integriert, oder nicht, und kann entfernbar sein. Sie kann beispielsweise ein Magnetband, eine Diskette oder eine CD-ROM (Festspeicherkompaktdiskette) enthalten.
Das Verfahren zum Bestimmen einer Partitionierung und zum Einfügen eines Wasserzeichenmarkierungssignals wird bei einem digitalen Bild IM angewendet.
Dieses Verfahren ermöglicht auf eine adaptive Weise ein Bewirken einer Partitionierung des Bildes in bestimmte Bereiche durch Minimieren einer Fehlerwahrscheinlichkeit bei der Erfassung einer vorbestimmten Anzahl von Wasserzeichenmarkierungssignalen. Diese Fehlerwahrscheinlichkeit ist die Wahrscheinlichkeit des Begehens von zumindest einem Fehler bezüglich eines Bits im Laufe der Erfassung der in das Bild eingefügten Bits.
Schritt E1 ist die Transformation des Bildes IM in M Signale von Frequenzunterbändern. Diese Transformation wird beispielsweise durch eine Spektralzerlegung vom Typ diskrete Wavelet-Zerlegung (DWT, „Discrete Wavelet Decomposition") durchgeführt.
Auf diese Weise wird ein Satz von Spektralkoeffizienten erhalten, der das digitale Bild IM darstellt. Diese Spektralkoeffizienten sind in Frequenzunterbändern verteilt, wie in 2 schematisch gezeigt. Bei diesem Beispiel wird das Bild IM in zehn Unterbänder S1 bis S10 zerlegt, die gemäß drei Auflösungsstufen verteilt sind. Natürlich kann sich die Anzahl von Unterbändern und Auflösungsstufen unterscheiden.
Als Variante können andere Arten von Transformationen verwendet werden, beispielsweise eine blockweise diskrete Kosinustransformation.
Die Segmentierung von jedem der Unterbänder in einen quaternären Baum ist nachstehend als nächstes betrachtet. Ein jeder Bereich der Segmentierung ist mit einem Knoten in dem Baum assoziiert. Wie gemäß 5 gezeigt, zieht ein Knoten N_i,k,j, der als Elternknoten bezeichnet wird, für ein gegebenes Unterband Si vier so genannte Kindknoten nach sich. Der quaternäre Baum weist eine vorbestimmte Tiefe k_max auf, die hierbei gleich 3 ist. Für eine gegebene Tiefenstufe k werden die Knoten ebenso durch einen Parameter j indiziert, dessen Maximalwert 4^k-1 von der Tiefe k abhängt.
Enthält der quaternäre Baum alle denkbaren Knoten bei der vorbestimmten Tiefe, dann wird er als vollständig bezeichnet. Der gemäß 5 beispielhaft gezeigte Baum wurde durch Ausästen aus dem vollständigen Baum erhalten.
Die Minimierung der Fehlerwahrscheinlichkeit bei der Erfassung einer vorbestimmten Anzahl von Wasserzeichenmarkierungssignalen ist der Maximierung bezüglich aller zulässigen Segmentierungen äquivalent zu dem Ausdruck: QP = Σ₁ bis CR (QP_i,k,j) unter der Nebenbedingung, dass CR größer oder gleich C ist. In dem vorstehend beschriebenen Ausdruck bezeichnet QP_i,k,j den Beitrag von jedem der Knoten N_i,k,j und ist nachstehend ausführlich beschrieben, und bezeichnet CR die Kardinalität der Segmentierung einer betrachteten Segmentierung.
Der nachfolgende Schritt E2 ist die Berechnung des Beitrags QP_i,k,j von jedem der Knoten N_i,k,j, wobei k zwischen 1 und k_max variiert und j zwischen 1 und 4^k-1 variiert, der quaternären Baumstrukturen für alle Unterbänder Si, wobei i zwischen 1 und M variiert.
Der Beitrag QP_i,k,j eines Knotens N_i,k,j ist gleich log (1 – PFA), wobei PFA („probability of false alarm") die Fehlalarmwahrscheinlichkeit für den betrachteten Knoten darstellt.
Die Fehlalarmwahrscheinlichkeit ist eine Fehlererfassungswahrscheinlichkeit, die der Wahrscheinlichkeit entspricht, dass entschieden wurde, dass eine Einfügung vorlag, obwohl keine Einfügung stattfand. Zu diesem Zweck wird ein standardisierter Hypothesentest betrachtet, beispielsweise jener, der in dem Artikel „A method for signature casting on digital images" von I. Pitas, I.C.I.P. proceedings, Seiten 215 bis 218, September 1996 beschrieben ist. Dieser standardisierte Hypothesentest wird in dem Bereich berechnet, der dem momentanen Knoten N_i,k,j entspricht. Zur Berechnung dieses Hypothesentests wird die vorstehend beschriebene Einfügung vorzugsweise unter Verwendung einer Wasserzeichenmarkierungssequenz w_j simuliert, die identisch mit der Sequenz ist, die zum Einfügungszweck verwendet wird. Das Ergebnis des Hypothesentests ist eine Variable q, die einer normalen auf 0 zentrierten Vorschrift und mit gleichförmiger Varianz in dem Fall unterliegt, in dem keine Einfügung stattfand. Die Testvariable q unterliegt einem normalen Gesetz mit gleichförmiger Varianz und mittelwertbehaftet, wenn eine Einfügung stattfand. Für einen gegebenen Variablenwert q ist die Fehlalarmwahrscheinlichkeit hierbei durch eine Bereichsberechnung unter der auf 0 zentrierten normalen Vorschrift zwischen dem Abszissenbetragswert von q und unendlich definiert.
Der nachfolgende Schritt E3 ist das Suchen nach der besten Segmentierung der Unterbänder, um eine Anzahl C von Wasserzeichenmarkierungssignalen einzufügen. Die beste Segmentierung bedeutet hierbei eine Segmentierung, die die zuvor definierte Größe QP maximiert oder auf eine äquivalente Weise die Fehlerwahrscheinlichkeit bezüglich aller akzeptablem Segmentierungen minimiert, und unter der Ungleichungsnebenbedingung, dass die Kardinalität der besten Segmentierung größer oder gleich der Kardinalität C aller Wasserzeichenmarkierungssignale ist.
Es ist ein Fall einer Optimierung mit Nebenbedingungen, deren Lagrange'sche Formulierung lautet wie folgt: Es ist erforderlich, die Segmentierung R* bezüglich aller akzeptablem Segmentierungen zu suchen, um den folgenden Ausdruck zu maximieren:
Σ_i=1 bis CR QP_i,k,j + λCR, wobei λ ein Lagrange-Multiplikator größer oder gleich Null ist, der sich auf die Ungleichungsnebenbedingung bezieht, und CR die Kardinalität der betrachteten Segmentierung ist.
Dies läuft auf ein Suchen des besten quaternären Baums hinaus, der den vorstehend beschriebenen Ausdruck für jedes Unterband maximiert. Da die Lagrange'sche trennbar ist, ist es hinreichend, den quaternären Baum durch sukzessives Vergleichen der mit den Elternknoten assoziierten Lagrange'schen mit den mit den Kindknoten assoziierten Lagrange'schen gemäß einem aufsteigenden Ansatz auszuästen, das heißt beginnend von der tiefsten Stufe.
Es wird beispielsweise die Lagrange'sche (QP_i,2,1 + λ) des Elternknotens N_i,2,1 mit der Lagrange'schen der Kindknoten (QP_i,3,1 + QP_i,3,2 + QP_i,2,3 + QP_i,3,4 + 4λ), was gleich der Summe der elementaren Lagrange'schen ist. Ist die Lagrange'sche des Elternknotens größer als jene des Kindknotens, dann werden die Kinderknoten ausgeästet. Ist demgegenüber die Lagrange'sche der Kindknoten größer als jene des Elternknotens, dann werden die Kinderknoten beibehalten (ein Vorgang des „Teilens").
Schritt E3 besteht aus einem sukzessiven Aufrufen des Algorithmus gemäß 6, der nachstehend beschrieben ist, für Lagrange-Multiplikatorwerte λ, die durch Dichotomie ausgewählt sind, bis eine Konvergenz auf einen Wert λ* vorliegt.
Der Wert λ* ist jener, der ermöglicht, eine Kapazität aufzuweisen, die sich der Anzahl C von einzufügenden Wasserzeichenmarkierungssignalen so nahe wie möglich annähert. Eine Suche durch Dichotomie ist hinreichend, da diese Kapazität eine monotone Funktion von λ ist. Die Optimierung bezüglich λ hält entweder bei einem Maximal-Iterationsanzahlkriterium oder bei einem Abstandskriterium der durch die Anzahl C erhaltenen Kapazität an.
Das Ergebnis dieses Schrittes ist eine Segmentierung von jedem der Unterbänder. Die Segmentierungen sind durch einen Satz von Boole'schen Werten definiert, die für jeden Knoten angeben, ob der Knoten Kinder aufweist, oder nicht.
Der nachfolgende Schritt E4 ist die Einfügung der C Wasserzeichenmarkierungssignale in das segmentierte Bild gemäß der zuvor definierten Segmentierung. Diese Einfügung ist konventionell und wird wie vorstehend beschrieben ausgeführt. Ein jedes Wasserzeichenmarkierungssignal, das einem Wasserzeichenmarkierungsbit entspricht, wird in einen Jeweiligen der Bereiche der Segmentierung eingefügt.
Dafür werden die Unterbänder in einer vorbestimmten Reihenfolge verarbeitet, beispielsweise durch ansteigende Auflösung, was ermöglicht, die ersten Bits mit größerer Robustheit einzufügen. Für ein gegebenes Unterband werden die Bereiche ebenso in einer vorbestimmten Reihenfolge verarbeitet. Die gleiche Reihenfolge wird bei der Decodierung zum Auffinden der eingefügten Bits verwendet.
Der nachfolgende Schritt E5 ist die Transformation, die die Umgekehrte zu jener bei Schritt E1 ausgeführten ist, um das wasserzeichenmarkierte Bild IM' aufzubauen.
6 zeigt ein ausführliches Ausführungsbeispiel des zuvor beschriebenen Schritts E3 in Form eines Schritte E31 bis E41 enthaltenden Algorithmus.
Als Ergebnis von Schritt E2 stehen die Beiträge QP_i,k,j aller Knoten N_i,k,j der quaternären Baumzerlegungen von allen Unterbändern S1 bis SM zur Verfügung.
Es ist ein Verwenden aller Unterbänder der Zerlegung möglich, um darin Wasserzeichenmarkierungsdaten einzufügen, oder um einen Teilsatz dieser Unterbänder auszuwählen. Die zweite Möglichkeit weist den Vorteil auf, dass sie ermöglicht, Unterbänder zu beseitigen, die die Fehlerwahrscheinlichkeit in großem Maß erhöhen, wenn das Wasserzeichenmarkierungssignal entnommen wird. Im Allgemeinen sind derartige Unterbänder Unterbänder von hoher Energie, die für ein „natürliches" digitales Bild die Unterbänder von niedriger Auflösung sind.
Deshalb ist nachstehend betrachtet, dass für ein in M Frequenzunterbänder zerlegtes Bild 2^M Möglichkeiten der Auswahl von Unterbändern unter den M Unterbänder existieren, das heißt 2^M Konfigurationen.
Schritt E 31 ist eine Initialisierung zum Betrachten einer ersten Konfiguration unter den 2^M möglichen Konfigurationen. Die Konfigurationen sind durch eine Variable K referenziert, die hierbei auf den Wert 1 gesetzt ist.
Der nachfolgende Schritt E32 ist eine Initialisierung einer Kapazität Kapa(λ, K) und einer Wahrscheinlichkeitsfunktion QPr(λ, K) für die momentane Konfiguration K. Diese beiden Größen sind hierbei auf 0 gesetzt. Die Wahrscheinlichkeitsfunktion QPr(λ, K) ist gleich log (1 – P(K)), wobei P(K) die Fehlerwahrscheinlichkeit bei der Erfassung der Nachricht der Länge Kapa(λ, K) in der betrachteten Konfiguration ist.
Der nachfolgende Schritt E33 ist eine Initialisierung zum Setzen einer Variablen i auf 1, um ein erstes Unterband Si in der Zerlegung zu betrachten. Die Unterbänder werden in einer Reihenfolge betrachtet, die jedwede Reihenfolge sein kann, aber vorbestimmt ist.
Der nachfolgende Schritt E34 ist eine Prüfung zum Bestimmen, ob das momentane Unterband zu der momentanen Konfiguration K gehört.
Fällt die Antwort positiv aus, dann folgt nach diesem Schritt E35, der ein Suchen der besten Segmentierung des momentanen Unterbands Si ist. Dieser Schritt ist nachstehend ausführlich beschrieben. Er führt zu einer Kapazität Kapa(λ, i) und zu einer Fehlerwahrscheinlichkeitsfunktion QPr(λ, i) für das momentane Unterband Si.
Die Kapazität Kapa(λ, K) und die Fehlerwahrscheinlichkeitsfunktion QPr(λ, K) für die momentane Konfiguration K sind jeweils gleich der Summe der Kapazitäten und der Summe der Fehlerwahrscheinlichkeitsfunktionen aller Unterbänder, die zu der Konfiguration K gehören. Der Wert der Kapazität Kapa(λ, K) wird durch Addition der letzten berechneten Kapazität Kapa(λ, i) zu der momentanen Kapazität Kapa(λ, K) aktualisiert. In gleicher Weise wird die Fehlerwahrscheinlichkeitsfunktion QPr(λ, K) durch Addition der letzten berechneten Fehlerwahrscheinlichkeitsfunktion QPr(λ, i) zu der momentanen Fehlerwahrscheinlichkeitsfunktion QPr(λ, K) aktualisiert.
Fällt die Antwort in Schritt E34 negativ aus, dann folgt dem letzteren Schritt E36, so wie nach Schritt E35 Schritt E36 folgt. Schritt E36 ist eine Prüfung zum Bestimmen, ob alle Unterbänder in der Zerlegung geprüft wurden.
Fällt die Antwort negativ aus, dann folgt nach diesem Schritt Schritt E37, um ein nachfolgendes Unterband zu betrachten. Nach Schritt E37 folgt der zuvor beschriebene Schritt E34.
Fällt die Antwort in Schritt E36 positiv aus, dann wurden alle Unterbänder der momentanen Konfiguration berücksichtigt. Nach Schritt E36 folgt dann Schritt E38, der die Speicherung der Kapazitäts-Kapa(λ, K) und der Fehlerwahrscheinlichkeitsfunktions-QPr(λ, K)-werte für die momentane Konfiguration K ist.
Der nachfolgende Schritt E39 ist eine Prüfung zum Bestimmen, ob alle Konfigurationen verarbeitet wurden. Fällt die Antwort negativ aus, dann folgt nach diesem Schritt Schritt E40, um eine nachfolgende Konfiguration zu betrachten. Nach Schritt E40 folgt dann der vorstehend beschriebene Schritt E32.
Fällt die Antwort in Schritt E39 positiv aus, dann wurden alle Konfigurationen verarbeitet, und nach diesem Schritt folgt Schritt E41, in dem die Konfiguration K* bestimmt wird, die den maximalen Lagrange-Wert ergab. Dann steht für einen gegebenen Lagrange-Multiplikatorwert λ die optimale Konfiguration K*, deren Kapazität Kapa(λ, K*) und deren Fehlerwahrscheinlichkeitsfunktion QPr(λ, K*) zur Verfügung.
Es sei darauf hingewiesen, dass Schritt E3 die iterative Suche nach dem Wert λ* enthält, der ermöglicht, eine Kapazität nahe der Anzahl C von einzufügenden Wasserzeichenmarkierungssignalen zu erhalten.
Am Ende von Schritt E3 steht der Wert QPr(λ*, K*) zur Verfügung, der ein Berechnen der Fehlerwahrscheinlichkeit: P = 1 – e^QPr(λ*,K*) ermöglicht. Dieser Wert ermöglicht ein Auswerten der Robustheit der Einfügung, und wird angezeigt.
Der Schritt E35 des Suchens der besten Segmentierung des momentanen Unterbandes Si ist nachstehend unter Bezugnahme auf 7 ausführlich beschrieben.
Dieser Schritt enthält Unterschritte E350 bis E363.
Schritt E350 ist eine Initialisierung, bei der alle Knoten der maximalen Stufe k_max in dem momentanen Unterband betrachtet werden. Die Kapazität Kapa(λ, i) des momentanen Unterbandes Si wird auf ihren Maximalwert initialisiert, das heißt 4^kmax-1. Die Fehlerwahrscheinlichkeitsfunktion QPr(λ, i) wird auf einen Wert initialisiert, der gleich der Summe der Beiträge QP_i,k,j der Knoten der Stufe k_max des momentanen Subbandes ist.
Es wird für jeden Knoten ebenso eine Bool'sche Variable B_i,k,j initialisiert, die von dem Wert des Lagrange-Multiplikators λ abhängt. Die Bool'sche Variable gibt an, dass der Knoten ausgeästet wurde, wenn sie gleich dem Wert „wahr" ist, und das er nicht ausgeästet wurde, wenn sie bei dem Wert „falsch" ist. Der Satz von Bool'schen Werten des momentanen Unterbandes ermöglicht es, die Segmentierung dieses Unterbandes zu identifizieren.
Bei diesem Schritt werden die Werte der Bool'schen Variablen auf den Wert „wahr" für die Knoten auf der Stufe k_max und auf den Wert „falsch" für die anderen Stufen initialisiert.
Die Kapazitäten Kapa_i,k,j, die den Beitrag in Bit-Anzahlen von jedem der Knoten angeben, werden für die Knoten auf der Stufe k_max auf 1 initialisiert.
Die Beiträge QPr_i,k,j, die den Beitrag von jedem der Knoten zu der Funktion angeben, die die Fehlerwahrscheinlichkeit QPr(λ) darstellt, werden auf die jeweiligen Werte von QP_i,k,j für die Knoten der Tiefe k_max initialisiert.
Der nachfolgende Schritt E351 ist eine Initialisierung zum Betrachten der Stufe k_max – 1.
Der nachfolgende Schritt E352 ist eine Initialisierung einer Bool'schen Variable KENNUNG auf den Wert „falsch". Die Variable KENNUNG gibt an, dass auf der momentanen Stufe zumindest eine Ausästungsentscheidung stattfand, falls sie sich bei dem Wert „wahr" befindet.
Der nachfolgende Schritt E353 ist eine Initialisierung zum Betrachten des ersten Knotens N_i,k,1 der momentanen Stufe.
Der nachfolgende Schritt E354 ist die Berechnung der Eltern-Lagrange'schen JP_i,k,j und der Kind-Lagrange'schen JF_i,k,j des momentanen Knotens N_i,k,j gemäß der Formel: JPi,k,j = QPi,k,j + λ, JFi,k,j = Σj(Qpri,k+1,j + λ*Kapai,k+i,j), wobei die Summe bezüglich aller Kindknoten des momentanen Knotens berechnet wird.
Der nachfolgende Schritt E355 ist der Vergleich der Eltern-Lagrange'schen JP_i,k,j und der Kind-Lagrange'schen JF_i,k,j des momentanen Knotens N_i,k,j.
Ist die Eltern-Lagrange'sche größer als die Kind-Lagrange'sche, dann folgt nach Schritt E355 Schritt E356, in dem der momentane Knoten ausgeästet wird. Die nachstehenden Variablen werden aktualisiert: Bi,k,j = „wahr" Kapai,k,j = 1 QPri,k,j = QPi,k,j Kapa(λ, i) = Kapa(λ, i) + 1 – Σj Kapai,k+1j QPr(λ, i) = QPr(λ, i) + QPi,k,j – Σj QPr(i,k,j),wobei die Summen bezüglich der Kinder des momentanen Knotens N_i,k,j berechnet werden.
In dem nachfolgenden Schritt E357 wird die Variable KENNUNG auf den Wert „wahr" gesetzt, um anzugeben, dass der Knoten ausgeästet wurde.
Ist die Eltern-Lagrange'sche kleiner als die Kind-Lagrange'sche, dann folgt nach Schritt E355 Schritt E358, in dem die nachstehenden Variablen aktualisiert werden: Kapai,k,j = Σj Kapai,k+i,j QPri,k,j = Σj QPri,k+i,j,wobei die Summen bezüglich der Kinder des momentanen Knotens N_i,k,j berechnet werden.
Nach Schritten E357 und E358 folgt Schritt E359, der eine Prüfung zum Nachprüfen ist, ob alle Knoten der momentanen Stufe verarbeitet wurden.
Fällt die Antwort negativ aus, dann folgt nach diesem Schritt Schritt E360, um einen nachfolgenden Knoten zu betrachten. Nach Schritt E360 folgt der zuvor beschriebene Schritt E354.
Fällt die Antwort in Schritt E359 positiv aus, dann folgt nach diesem Schritt Schritt E361, der eine Prüfung zum Nachprüfen ist, ob der Wert der Variablen KENNUNG bei dem Wert „falsch" ist.
Fällt die Antwort in Schritt E361 negativ aus, dann folgt nach diesem Schritt Schritt E362, der eine Prüfung zum Bestimmen ist, ob die momentane Stufe Stufe 1 ist. Fällt die Antwort positiv aus, dann wurden alle Stufen verarbeitet, und wird die Verwendung dieses Algorithmus beendet.
Fällt die Antwort in Schritt E362 negativ aus, dann folgt nach diesem Schritt E363, bei dem die Stufe, die unmittelbar tiefer als die momentane Stufe ist, betrachtet wird. Nach diesem Schritt folgt der zuvor beschriebene Schritt E352.
Unter Bezugnahme auf 8 ist das erfindungsgemäße Verfahren zum Entnehmen des in das Bild IM eingefügten Wasserzeichenmarkierungssignals beschrieben.
Dieses Verfahren ist in Form eines Schritte E11 bis E14 enthaltenden Algorithmus implementiert.
Schritte E11 bis E13 sind jeweils den zuvor beschriebenen Schritten E1 bis E3 ähnlich, und werden für ein Bild IM* bewirkt, das zum Entnehmen einer Nachricht von C Bits gedacht ist, die in der Lage war, in dieses eingefügt zu werden.
Es sei darauf hingewiesen, dass in Schritt E12 die Einfügung für die Berechnung der Werte QP_i,k,j nicht simuliert wird, da hierbei das Bild bearbeitet wird, in dem angenommen ist, dass die Wasserzeichenmarkierungssignale eingefügt wurden.
Am Ende von Schritt E13 steht eine Segmentierung des Bildes IM* zur Verfügung. Die Fehlerwahrscheinlichkeit in der erfassten Nachricht steht ebenso zur Verfügung. Dieser Wert vermittelt ein Maß der Zuverlässigkeit der bewirkten Erfassung, und er wird angezeigt.
Der nachfolgende Schritt E14 ist die Entnahme der C Wasserzeichenmarkierungsbits. Diese Entnahme ist konventionell und enthält eine Prüfung des Vorzeichens des Hypothesentestergebnisses q, das in Schritt E12 berechnet ist, bezüglich jeden Bereichs der in Schritt E13 erhaltenen Segmentierung.
9 zeigt ein zweites Ausführungsbeispiel eines erfindungsgemäßen Verfahrens zum Bestimmen einer Partitionierung eines Satzes von Daten und zum Einfügen eines Wasserzeichenmarkierungssignals in den Satz von Daten.
Das erfindungsgemäße Verfahren ist in der vorstehend beschriebenen Vorrichtung implementiert und enthält Schritte E21 bis E28.
Schritte E21 und E25 bis E28 sind jeweils den zuvor beschriebenen (4) Schritten E1 bis E5 ähnlich. Jene Schritte sind nachstehend nicht ausführlich beschrieben.
Dieses Verfahren ermöglicht auf eine adaptive Weise ein Bewirken einer Partitionierung des Bildes in bestimmte Bereiche durch Minimierung einer Fehlerwahrscheinlichkeit bei der Erfassung einer vorbestimmten Anzahl von Wasserzeichenmarkierungssignalen. Diese Fehlerwahrscheinlichkeit ist die Wahrscheinlichkeit des Begehens von zumindest einem Fehler bezüglich eines Bits im Laufe der Erfassung der in das Bild eingefügten Bits.
In diesem zweiten Ausführungsbeispiel umfasst das Verfahren zum Bestimmen einer Partitionierung einen Schritt des Anwendens einer Verzerrung bei dem Satz von modulierten Koeffizienten vor einem Schritt des Berechnens des Beitrags QP_i,k,j von jedem der Knoten N_i,k,j. Es wird bei dem Satz von modulierten Koeffizienten eine vorbestimmte Verzerrung angewendet, und um die Berechnung der Beiträge QP_i,k,j nach dieser Vorverzerrung derart auszuführen, dass es möglich ist, die Erfassung der Wasserzeichenmarkierungssignale zu garantieren, die in einer Partitionierung der Koeffizienten für eine vorbestimmte Verzerrung eingefügt sind. Diese Vorverzerrung kann bei einem Satz von modulierten Koeffizienten in einem einzelnen Schritt angewendet werden, und muss nicht bei jedem Knoten N_i,k,j in der Partitionierung reiteriert werden.
Schritt E21 ist die Transformation des Bildes IM in M Signale von Frequenzunterbändern. Diese Transformation wird beispielsweise durch eine Spektralzerlegung vom Typ diskrete Wavelet-Zerlegung (DWT) durchgeführt.
Schritt E22 erzeugt eine zentrierte Pseudo-Zufalls-Sequenz w, die in der Größe gleich der Kardinalzahl des Satzes von Koeffizienten ist, die ein Bild darstellen, hierbei gleich N. Wie nachstehend ausführlich beschrieben, wird diese Pseudo-Zufalls-Sequenz aus zentrierten Pseudo-Zufalls-Untersequenzen gebildet, die durch Blöcke bestimmt sind.
Nach Schritten E21 und E22 folgt Schritt E23, der eine Modulation des Satzes von Koeffizienten X durch die zentrierte Pseudo-Zufalls-Sequenz ist, um das gleiche Informationsbit in diesen Satz von Koeffizienten einzufügen.
Der nachfolgende Schritt E24 ist eine Anwendung einer Verzerrung D („Distortion"), die ermöglicht, die Robustheit der eingefügten Wasserzeichenmarkierueg in dem Fall von bestimmten Arten von Verzerrung bereitzustellen und zu garantieren, typischerweise eine Komprimierung des digitalen Bildes zu dessen Speicherung.
Dieser Schritt des Anwendens einer Verzerrung ermöglicht tatsächlich eine vorbestimmte Verzerrung über dem Satz von modulierten Koeffizienten zu simulieren. Hierbei umfasst er, wann immer die Koeffizienten des Satzes X Spektralkoeffizienten sind, eine umgekehrte Spektraltransformation des Satzes von modulierten Koeffizienten, um ein wasserzeichenmarkiertes Bild, eine Anwendung einer Verzerrung bei diesem wasserzeichenmarkierten Bild und eine Spektraltransformation des wasserzeichenmarkierten Bildes zu erhalten, um den Satz von modulierten Koeffizienten nach einer Verzerrung wiederzuholen.
Nachstehend ist Schritt E24 ausführlich beschrieben.
Der nachfolgende Schritt E25 ist die Berechnung des Beitrags QP_i,k,j von jedem Knoten N_i,k,j, wobei k zwischen 1 und k_max variiert, und j zwischen 1 und 4^k-1 variiert, der quaternären Baumstrukturen für alle Unterbänder Si, wobei i zwischen 1 und M variiert.
Der nachfolgende Schritt E26 ist das Suchen nach der besten Segmentierung der Unterbänder, um eine Anzahl C von Wasserzeichenmarkierungssignalen einzufügen.
Das Ergebnis dieses Schritts ist eine Segmentierung von jedem Unterband. Die Segmentierungen sind durch einen Satz von Bool'schen Werten definiert, die für jeden Knoten angeben, ob der Knoten Kinder aufweist, oder nicht.
Der nachfolgende Schritt E27 ist die Einfügung der C Wasserzeichenmarkierungssignale in das segmentierte Bild gemäß der zuvor definierten Segmentierung. Diese Einfügung ist konventionell und wird wie vorstehend beschrieben ausgeführt. Jedes Wasserzeichenmarkierungssignal, das einem Wasserzeichenmarkierungsbit entspricht, wird in einen jeweiligen Bereich der verarbeiteten Segmentierung in einer vorbestimmten Reihenfolge eingefügt. Die gleiche Reihenfolge wird bezüglich der Decodierung zum Auffinden der eingefügten Bits verwendet.
10 zeigt das Verfahren gemäß 9. Ein Satz von Spektralkoeffizienten X ist erhalten, der das digitale Bild IM darstellt. Diese Spektralkoeffizienten sind bei Vollendung der Zerlegungsstufe E21 in Frequenzunterbändern verteilt, wie per Diagramm gemäß 10 angegeben. Die Größe des Satzes von Koeffizienten X ist gleich N = M·M für ein quadratisches Bild. Dasselbe Verfahren kann offensichtlich bei einem rechteckigen Bild angewendet werden.
In diesem Ausführungsbeispiel der Erfindung enthält das Verfahren eine Stufe E22 des Erzeugens einer zentrierten Pseudo-Zufalls-Sequenz der Größe N, die gleich der Kardinalzahl N des Satzes von Koeffizienten X ist, die das Bild IM darstellen.
Es sei w = {w_mn, 0 ≤ m, n ≤ M} diese Pseudo-Zufalls-Sequenz.
Diese Pseudo-Zufalls-Sequenz w ist aus zentrierten Pseudo-Zufalls-Untersequenzen w^j gebildet.
Die Pseudo-Zufalls-Sequenz kann als die Zusammenführung der Pseudo-Zufalls-Untersequenzen w^j angesehen werden.
Hierbei ist die zentrierte Pseudo-Zufalls-Sequenz w aus Pseudo-Zufalls-Untersequenzen w^j von identischer Größe A = L·L gebildet, die einem Einheitsblock genannten Block des Satzes von Koeffizienten X entspricht. Hierbei entspricht die Größe dieser Einheitsblöcke der Größe der Knoten N_i,k,j für k = k_max mit einer minimalen Anzahl von Koeffizienten. Offensichtlich können die Pseudo-Zufalls-Untersequenzen w^j voneinander hinsichtlich der Größe abweichen. Diese Ausgestaltung ist insbesondere in einer quaternären Baumstruktur vorteilhaft, wenn die Partitionierung durch Kombinieren von Blöcken aus einer initialen Segmentierung des Bildes in Einheitsblöcke der Größe L L gelöst wird. Der vollständige Baum entspricht dann der maximalen Partitionierung des Bildes, der aus Knoten der Größe L·L aufgebaut ist.
Beispielsweise ist L = 8 gewählt.
Die Pseudo-Zufalls-Sequenz w ist dann die Zusammenführung von N/64 Pseudo-Zufalls-Untersequenzen w^j, die Einheitsblöcke bilden.
Bei jedem Einheitsblock muss erfindungsgemäß eine zentrierte Pseudo-Zufalls-Sequenz von vordefinierter Verteilung (Gauß, uniform usw.) auf der Grundlage einer Funktion abhängig von einem geheimen Schlüssel K bei dem Unterband i und bei dem Index j von jedem Einheitsblock erzeugt werden. Dieser Schlüssel kann f(K, i, j) genannt werden. Es ist dann erforderlich sicherzustellen, dass in der Praxis der Mittelwert des Signals w^j über jeden Einheitsblock exakt gleich 0 ist.
Ein erstes Verfahren zum Erzeugen einer derartigen zentrierten Pseudo-Zufalls-Sequenz besteht im Zentrieren der Sequenz auf eine deterministische Weise durch Symmetrisierung. Dieses Verfahren ist zum Erzeugen einer Pseudo-Zufalls-Untersequenz von gerader Größe A geeignet.
In diesem Fall wird jede zentrierte Pseudo-Zufalls-Untersequenz w^j durch Erzeugen einer Hälfte A/2 der Pseudozufallsabtastungen der Untersequenz über einen Pseudo-Zufalls-Zahlengenerator von bekannter zentrierter Verteilung und durch Symmetrisierung der so erzeugten Pseudozufallsabtastungen erstellt, um die andere Hälfte A/2 der Abtastungen der Untersequenz w^j zu erhalten.
Für eine eindimensionale Sequenz wird deshalb ein Satz von Abtastungen der Größe A/2 {w₁, 1 ≤ 1 ≤ A/2} erzeugt, und dieser Satz wird symmetrisch gestaltet, um die andere Hälfte der Abtastungen {w₁ = –w_A-1, A/2 < 1 ≤ A} zu erhalten.
Um den Zufallscharakter der so erhaltenen Sequenz zu verstärken, kann bei dem Satz von erhaltenen Abtastungen {w₁, 1 ≤ 1 ≤ A} durch Verwendung eines geheimen Schlüssels eine Permutation ausgeführt werden.
Ein zweites Verfahren zum Erzeugen einer zentrierten Pseudo-Zufalls-Sequenz besteht im Erstellen einer jeden zentrierten Pseudo-Zufalls-Untersequenz w^j durch Erzeugen von Pseudozufallsabtastungen über einen Pseudo-Zufalls-Zahlengenerator und durch Umverteilen der Summe dieser über jeder Abtastung erzeugten Pseudozufallsabtastungen.
Somit wird zuallererst unter Verwendung des geheimen Schlüssels f(k, i, j) eine Sequenz von Pseudozufallsabtastungen derselben Größe A wie der Einheitsblock erzeugte, d. h. {w₁, 1 ≤ 1 ≤ A} wird erzeugt.
Als nächstes wird die exakte Summe dieser Abtastungen berechnet:
Dann wird diese Summe SS_j über die Abtastungen umverteilt, um eine zentrierte Pseudo-Zufalls-Sequenz zu erhalten, das heißt eine mit einer Summe, die exakt gleich 0 ist.
Somit wird w^j = {w₁ – SS_j/A, 1 ≤ 1 ≤ A} erhalten.
Die Pseudo-Zufalls-Sequenz w ist somit aus der Zusammenführung der zentrierten Untersequenzen w^j derart zusammengestellt, dass die Partitionierung eines Satzes von modulierten Koeffizienten durch die zentrierte Pseudo-Zufalls-Sequenz w Teilsätze von Koeffizienten ergibt, die ebenso durch zentrierte Pseudo-Zufalls-Untersequenzen moduliert sind.
Offensichtlich können andere Techniken zum Erzeugen zentrierter Pseudo-Zufalls-Sequenzen verwendet werden.
Wie gemäß 10 gezeigt, wird der Schritt E23 der Modulation des Satzes von Koeffizienten durch die zentrierte Pseudo-Zufalls-Sequenz w dann implementiert, um ein Informationsbit bei dem Satz von Koeffizienten einzufügen, die aus der Spektralzerlegung stammen.
In der Praxis wird der Satz von Koeffizienten in einen Arbeitsspeicher kopiert, beispielsweise den Speicher 103 mit wahlfreiem Zugriff gemäß 3, um das Bild I nicht direkt zu markieren.
Das gleiche Informationsbit wird in den Satz von Koeffizienten moduliert, beispielsweise ist hierbei b = 1, gemäß der Modulationsformel: X'j = Xi + αjwj mit 0 ≤ i ≤ N
Die Gewichtungsamplitude α_j wird auf die übliche Weise gewählt, um die Unsichtbarkeit des eingefügten Informationsbits zu garantieren.
Es kann ein konstanter Gewichtungskoeffizient für alle Koeffizienten verwendet werden, so dass α_j = α_v für alle i, wobei der Wert des Gewichtungskoeffizienten α_v gleich einem maximalen Wert, der die Nicht-Wahrnehmbarkeit der Wasserzeichenmarkierung sicherstellt, zur Modulation des Satzes von Koeffizienten, die das digitale Bild darstellen, ist.
Es kann nützlich sein, die Tatsache auszunutzen, dass das Bildsignal selbst ein Maskieren der Modulation ermöglicht.
Zu diesem Zweck ist es für jeden zu modulierenden Koeffizienten X_i möglich, einen Gewichtungskoeffizienten gemäß einer Regel der Form α_i = k_i·α_v zu verwenden, wobei k_i ein Modulationsfaktor ist, der von den Koeffizienten abhängt, die in der Umgebung des fraglichen Koeffizienten situiert sind, und α_v gleich dem maximalen Wert des Gewichtungskoeffizienten ist, der die Nicht-Wahrnehmbarkeit der Wasserzeichenmarkierung für die Modulation des Satzes von Koeffizienten sicherstellt.
Somit wird jeder Koeffizient als eine Funktion des lokalen Inhalts des Bildes moduliert, was ermöglicht, die Amplitude der Modulation zugunsten der Erfassbarkeit lokal zu erhöhen.
Es ist in diesem Ausführungsbeispiel der Erfindung vorzugsweise erwünscht, eine Partitionierung bei einem nachverarbeiteten Bildsignal anzuwenden, um Robustheit vor der eingefügten Wasserzeichenmarkierung gegenüber verschiedenen Nachverarbeitungen zu erhalten, die das Bild IM durchläuft.
Um dies zu erreichen, wird in dem Verzerrungsschritt E24 bei dem Satz von modulierten Koeffizienten eine Verzerrung angewendet.
Mittels der Modulation der Koeffizienten in einem einzelnen Vorgang auf der Grundlage einer zentrierten Pseudo-Zufalls-Sequenz kann der Verzerrungsschritt E24 lediglich einmal bei Bestimmung einer Partitionierung implementiert werden, im Gegensatz zu den Techniken, in denen jeder Unterbereich von Koeffizienten unabhängig von dem anderen moduliert wird, und die Verzerrung bei jeder Stufe der Partitionierung angewendet werden muss.
Dies ist umso vorteilhafter, da hierbei der Schritt E24 des Anwendens einer Verzerrung die folgenden Unterschritte enthält, wie gemäß 10 gezeigt:

– umgekehrte Spektraltransformation E24a des Satzes von modulierten Koeffizienten X'_i, um ein wasserzeichenmarkiertes Bild zu erhalten;
– geeignetes Anwenden E24b der Verzerrung bei dem wasserzeichenmarkierten Bild; und
– Spektraltransformation E24c des wasserzeichenmarkierten Bildes, um einen Satz von modulierten Koeffizienten nach der Verzerrung zu erhalten.

Die angewendeten Verzerrungen sind Verzerrungen, die den Wert des Bildelements ändern, ohne die Geometrie des Bildes zu ändern, wie beispielsweise die Hinzufügung von Rauschen, Ändern des Kontrasts, der Komprimierung, eine Tiefpass- oder Hochpass-Filterung.
Es wird hierbei eine Komprimierung des Bildes gemäß dem JPEG-Standart (für die Joint Photographic Expert Group) mit spezifiziertem Qualitätsfaktor Q betrachtet, wobei typischerweise Q = 75 per Voreinstellung für eine JPEG-Komprimierung ist.
In der Praxis wird hierbei eine umgekehrte Unterbandtransformation, z. B. eine Wavelet-Transformation DWT^-1 angewendet, dann eine Komprimierung, nach der eine Dekomprimierung des Bildes folgt, und schließlich wieder eine Vorwärts-Wavelet-Transformation.
Wie zuvor beschrieben, ist Schritt E25 die Berechnung des Beitrags QP_i,k,j von jedem Knoten N_i,k,j. Diese Berechnung wird mit Pseudo-Zufalls-Sequenzen zur Unterstützung N_i,k,j durchgeführt, die die Zusammenführung von Pseudo- Zufalls-Untersequenzen sind, die verwandten Einheitsblöcken zur Unterstützung N_i,kmax,j entsprechen.
Schritte E27 und E28 sind vorstehend beschrieben.
Die Erfindung ist natürlich in keiner Weise auf die beschriebenen und gezeigten Ausführungsbeispiele eingeschränkt, sondern umfasst im Gegenteil jedwede Variante innerhalb des Fachwissens des Fachmanns.
Es ist insbesondere möglich, den Satz von Wasserzeichenmarkierungssignalen in den Originalbildelementbereich ohne jedwede Transformation in dem Unterband einzufügen.
Wird insbesondere eine Transformation in einem Unterband bewirkt, dann ist es möglich, die für die Einfügung verwendeten Unterbänder vorab zu bestimmen, beispielsweise durch Beseitigen der Unterbänder von hoher Energie.
Es ist ebenso möglich, einen andere Erfassungsfehlermessung zu verwenden. Diese Messung führt vorzugsweise zu einer Formulierung, die von dem Optimierungsproblem mit Nebenbedingungen trennbar ist, um in der Lage zu sein, die gleiche Art von Algorithmus bei einer quaternären Baumstruktur zu verwenden.
Es ist ebenso möglich, jedwede andere Art von Baumsegmentierung zu verwenden.
Es ist ebenso möglich, Wasserzeichenmarkierungsdaten in ein digitales Bild einzufügen, wobei die Einfügung die Schritte umfasst:

– Einbetten der Wasserzeichenmarkierungsdaten in bestimmte Bereiche, die einen Teil des digitalen Bildes bilden, und
– Bestimmen der bestimmten Bereiche derart, dass jeder der bestimmten Bereiche ein vorbestimmtes Erfassungsfehlerkriterium erfüllt.

Es ist ebenso möglich, Wasserzeichenmarkierungsdaten in ein digitales Bild einzufügen, wobei die Einfügung die Schritte umfasst:

– Einbetten der Wasserzeichenmarkierungsdaten in bestimmte Bereiche, die einen Teil des digitalen Bildes bilden, und
– Bestimmen der bestimmten Bereiche derart, dass jede Größe der bestimmten Bereiche ein vorbestimmtes Fehlererfassungskriterium erfüllt.

Claims

Verfahren zum Bestimmen einer Segmentierung in bestimmte Bereiche eines Satzes von zumindest einen Teil eines Bilds (IM) darstellenden Koeffizienten, um einen Satz von Wasserzeichenmarkierungssignalen mit einer vorbestimmten Kardinalität einzufügen oder zu entnehmen, dadurch gekennzeichnet, dass es die Schritte umfasst: – Erzeugen (E2) eines Satzes von akzeptablen Segmentierungen, die durch eine Baumsegmentierung des Satzes von Koeffizienten erhalten werden, – Berechnen (E3), für jede akzeptable Segmentierung, einer Fehlerwahrscheinlichkeit bezüglich der Erfassung der in jede akzeptable Segmentierung eingefügten Wasserzeichenmarkierungssignale, und – Auswählen (E3) von zumindest einer Segmentierung in dem Satz von akzeptablen Segmentierungen durch Minimieren, bei allen akzeptablen Segmentierungen, der Fehlerwahrscheinlichkeit, die einer Bedingung bei der Anzahl von Bereichen der ausgewählten Segmentierung unterzogen ist, hinsichtlich der vorbestimmten Kardinalität (C).
Verfahren zum Bestimmen einer Segmentierung gemäß Anspruch 1, dadurch gekennzeichnet, dass der Satz von Koeffizienten ein Satz von transformierten Koeffizienten ist, die sich aus einer Raumfrequenztransformation (E1) eines digitalen Bilds ergeben.
Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 oder 2, dadurch gekennzeichnet, dass die akzeptablen Segmentierungen durch eine quaternäre Baumsegmentierung von allen zumindest einen Teil eines Bilds darstellenden Koeffizienten erhalten werden.
Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass jedes der Wasserzeichenmarkierungssignale mit einem Wasserzeichenmarkierungsbit assoziiert ist, und dadurch, dass die Fehlerwahrscheinlichkeit bezüglich der Erfassung der Wasserzeichenmarkierungssignale die Wahrscheinlichkeit des Begehens von zumindest einem Fehler bezüglich eines Bits während der Erfassung der Wasserzeichenmarkierungsbits ist.
Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass die Minimierung der Fehlerwahrscheinlichkeit eine Maximierung einer trennbaren Menge enthält, und dadurch, dass die ausgewählte Segmentierung durch Abschneiden einer Baumsegmentierung erhalten wird.
Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass die Bedingung des Minimierungsschritts darin besteht, dass die Anzahl von Bereichen der ausgewählten Segmentierung größer oder gleich der Kardinalität (C) des Satzes von Wasserzeichenmarkierungssignalen ist.
Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass es einen Schritt (E24) des Anwendens einer Verzerrung bei dem Satz von Koeffizienten vor dem Schritt (E25) des Er zeugens eines Satzes von akzeptablen Segmentierungen umfasst.
Verfahren zum Bestimmen einer Segmentierung gemäß Anspruch 7, dadurch gekennzeichnet, dass es die Schritte umfasst: – Erzeugen (E22) einer zentrierten Pseudozufallssequenz (w), die in der Größe der Kardinalzahl (N) des Satzes von Koeffizienten gleicht, und die aus zentrierten Pseudozufallssubsequenzen (w^j) gebildet ist, – Modulieren (E23) des Satzes von Koeffizienten durch die zentrierte Pseudozufallssequenz (w), um dasselbe Informationsbit bei dem Satz von Koeffizienten einzufügen, und – Anwenden (E24) einer Verzerrung bei dem Satz von Koeffizienten vor dem Schritt (E25) des Erzeugens eines Satzes von akzeptablen Segmentierungen.
Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, dass es ebenso die Anzeige der Fehlerwahrscheinlichkeit (P) bezüglich aller Wasserzeichenmarkierungssignale enthält.
Verfahren zum Einfügen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, in ein digitales Bild, dadurch gekennzeichnet, dass es ein Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 9 und einen Schritt (E4) des Einfügens der Wasserzeichenmarkierungsbits durch Modulation der Koeffizienten jeweiliger Bereiche der Segmentierung enthält.
Einfügeverfahren gemäß Anspruch 10, dadurch gekennzeichnet, dass die Bereiche in einer vorbestimmten Reihenfolge während des Einfügeschritts betrachtet werden.
Verfahren zum Entnehmen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, aus einem digitalen Bild, dadurch gekennzeichnet, dass es ein Verfahren zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 1 bis 9 und einen Schritt (E14) des Entnehmens der Wasserzeichenmarkierungsbits enthält.
Vorrichtung zum Bestimmen einer Segmentierung in bestimmte Bereiche eines Satzes von zumindest einen Teil eines Bilds (IM) darstellenden Koeffizienten, um einen Satz von Wasserzeichenmarkierungssignalen mit einer vorbestimmten Kardinalität einzufügen, dadurch gekennzeichnet, dass sie aufweist: – eine Einrichtung (11) zum Erzeugen eines Satzes von akzeptablen Segmentierungen durch eine Baumsegmentierung der Koeffizienten, – eine Einrichtung (12) zum Berechnen, für jede akzeptable Segmentierung, einer Fehlerwahrscheinlichkeit bezüglich der Erfassung der in jede akzeptable Segmentierung eingefügten Wasserzeichenmarkierungssignale, und – eine Einrichtung (12) zum Auswählen einer Segmentierung in dem Satz von akzeptablen Segmentierungen durch Minimieren, bei allen akzeptablen Segmentierungen, der Fehlerwahrscheinlichkeit, die einer Bedingung bei der Anzahl von Bereichen der ausgewählten Segmentierung unterzogen ist, hinsichtlich der vorbestimmten Kardinalität (C)
Vorrichtung zum Bestimmen einer Segmentierung gemäß Anspruch 13, dadurch gekennzeichnet, dass sie zum Betrachten eines Satzes von Koeffizienten, der ein Satz von transformierten Koeffizienten ist, die sich aus einer Raumfrequenztransformation eines digitalen Bilds ergeben, eingerichtet ist.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 oder 14, dadurch gekennzeichnet, dass Erzeugungseinrichtung zum Bestimmen der akzeptablen Segmentierungen durch eine quaternäre Baumsegmentierung von allen zumindest einen Teil eines Bilds darstellenden Koeffizienten eingerichtet ist.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 15, dadurch gekennzeichnet, dass sie zum Assoziieren eines Wasserzeichenmarkierungsbits mit jedem der Wasserzeichenmarkierungssignale eingerichtet ist, und dadurch, dass die Berechnungseinrichtung zum Betrachten der Fehlerwahrscheinlichkeit bezüglich der Erfassung der Wasserzeichenmarkierungssignale als die Wahrscheinlichkeit des Begehens von zumindest einem Fehler bezüglich eines Bits während der Erfassung der Wasserzeichenmarkierungsbits eingerichtet ist.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 16, dadurch gekennzeichnet, dass die Auswahleinrichtung, um die Fehlerwahrscheinlichkeit zu minimieren, zum Maximieren einer trennbaren Menge und zum Auswählen einer Segmentierung durch Abschneiden einer Baumsegmentierung eingerichtet ist.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 17, dadurch gekennzeichnet, dass die Auswahleinrichtung zum Implementieren einer Bedingung eingerichtet ist, die darin besteht, dass die Anzahl von Bereichen der ausgewählten Segmentierung größer oder gleich der Kardinalität (C) des Satzes von Wasserzeichenmarkierungssignalen ist.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 18, dadurch gekennzeichnet, dass sie eine Einrichtung zum Anwenden einer Verzerrung bei dem Satz von Koeffizienten umfasst.
Vorrichtung zum Bestimmen einer Segmentierung gemäß Anspruch 19, dadurch gekennzeichnet, dass sie umfasst: – eine Einrichtung zum Erzeugen einer zentrierten Pseudozufallssequenz (w), die in der Größe der Kardinalzahl (N) des Satzes von Koeffizienten gleicht, und die aus zentrierten Pseudozufallssubsequenzen (w^j) gebildet ist, – eine Einrichtung zum Modulieren des Satzes von Koeffizienten durch die zentrierte Pseudozufallssequenz (w), um dasselbe Informationsbit bei dem Satz von Koeffizienten einzufügen, und – eine Einrichtung zum Anwenden einer Verzerrung bei dem Satz von Koeffizienten.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 20, dadurch gekennzeichnet, dass sie ebenso eine Einrichtung zum Anzeigen der Fehlerwahrscheinlichkeit (P) bezüglich aller Wasserzeichenmarkierungssignale aufweist.
Vorrichtung zum Einfügen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, in ein digitales Bild, dadurch gekennzeichnet, dass sie eine Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 21 und eine Einrichtung (13) zum Einfügen der Wasserzeichenmarkierungsbits durch Modulation der Koeffizienten jeweiliger Bereiche der Segmentierung enthält.
Einfügevorrichtung gemäß Anspruch 22, dadurch gekennzeichnet, dass die Einfügeeinrichtung zum Betrachten der Bereiche in einer vorbestimmten Reihenfolge eingerichtet ist.
Vorrichtung zum Entnehmen von Wasserzeichenmarkierungssignalen, die jeweils mit Wasserzeichenmarkierungsbits assoziiert sind, aus einem digitalen Bild, dadurch gekennzeichnet, dass sie eine Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 21 und eine Einrichtung zum Entnehmen der Wasserzeichenmarkierungsbits enthält.
Vorrichtung zum Bestimmen einer Segmentierung gemäß einem der Ansprüche 13 bis 21, dadurch gekennzeichnet, dass die Erzeugungs-, Berechnungs- und Auswahleinrichtung umfasst sind in: – einem Mikroprozessor (100), – einem Festwertspeicher (102), der ein Programm zum Verarbeiten der Daten enthält, und – einem Speicher (103) mit wahlfreiem Zugriff, der Register enthält, die zum Aufzeichnen von während dem Ablaufen des Programms modifizierten Variablen eingerichtet sind.
Einfügevorrichtung gemäß einem der Ansprüche 22 bis 23, dadurch gekennzeichnet, dass die Erzeugungs-, Berechnungs-, Auswahl- und Einfügeeinrichtung umfasst sind in: – einem Mikroprozessor (100), – einem Festwertspeicher (102), der ein Programm zum Verarbeiten der Daten enthält, und – einem Speicher (103) mit wahlfreiem Zugriff, der Register enthält, die zum Aufzeichnen von während dem Ablaufen des Programms modifizierten Variablen eingerichtet sind.
Entnahmevorrichtung gemäß Anspruch 24, dadurch gekennzeichnet, dass die Erzeugungs-, Berechnungs-, Auswahl- und Entnahmeeinrichtung umfasst sind in: – einem Mikroprozessor (100), – einem Festwertspeicher (102), der ein Programm zum Verarbeiten der Daten enthält, und – einem Speicher (103) mit wahlfreiem Zugriff, der Register enthält, die zum Aufzeichnen von während dem Ablaufen des Programms modifizierten Variablen eingerichtet sind.
Gerät zum Verarbeiten eines digitalen Bilds, dadurch gekennzeichnet, dass es eine Vorrichtung zum Bestimmen einer Partitionierung gemäß einem der Ansprüche 13 bis 21 umfasst.
Gerät zum Verarbeiten eines digitalen Bilds, dadurch gekennzeichnet, dass es eine Vorrichtung zum Einfügen eines Wasserzeichenmarkierungssignals gemäß einem der Ansprüche 22 bis 23 umfasst.
Gerät zum Verarbeiten eines digitalen Bilds, dadurch gekennzeichnet, dass es eine Vorrichtung zum Entnehmen eines Wasserzeichenmarkierungssignals gemäß Anspruch 24 umfasst.