DE60000933T2

DE60000933T2 - Verfahren zur wasserzeichenseinführung in ein bild

Info

Publication number: DE60000933T2
Application number: DE60000933T
Authority: DE
Inventors: Severine Baudry; Guyen Philippe N; Didier Nicholson; Catherine Simon
Original assignee: Thales SA
Current assignee: Thales SA
Priority date: 1999-04-23
Filing date: 2000-04-07
Publication date: 2003-08-28
Anticipated expiration: 2020-04-08
Also published as: FR2792797B1; JP4336460B2; KR20020001840A; US7058979B1; WO2000065840A1; AU3826600A; FR2792797A1; EP1173980B1; DE60000933D1; ES2188526T3; EP1173980A1; JP2002543692A; ATE229251T1; CA2367420A1

Description

Die vorliegende Erfindung betrifft ein Verfahren zum verdeckten Kennzeichnen von Bildern für die Verarbeitung und die Übertragung von Stand- oder Videobildern.
In der Telekommunikation ist das verdeckte Kennzeichnen von Bildern der Sachverhalt der Übertragung einer Information in ein Bild oder in eine Bildsequenz, ohne daß daraus wahrnehmbare Änderungen in der Komposition des Bildes oder der empfangenen Bildsequenz resultieren. Dieses Verfahren ist auch unter dem angelsächsischen Begriff "watermarking" bekannt.
Diese Definition erinnert an jene der Steganographie, auch Übertragung über einen unterschwelligen Kanal (engl. subdiminal channel) genannt, also der Technik, Nachrichten auf versteckte Art und Weise zu senden, wobei eine Information mit harmlosem Aussehen eine versteckte Nachricht enthält, die nur von den damit vertrauten Empfängern gelesen werden kann. Im Gegensatz zur Kryptographie verbirgt die Steganographie selbst die Existenz der unterschwelligen Nachricht.
Der wesentliche Unterschied zwischen dem verdeckten Kennzeichnen eines Bildes und der Steganographie besteht in der Wahl des sogenannten "überdeckenden Übertragungskanals" (engl. cover channel), d. h. der unverschlüsselten Nachricht, die die versteckte Nachricht enthält.
Bei der Steganographie kann der Absender diese Wahl selbst treffen, während sie im Fall der verdeckten Kennzeichnung vorgeschrieben ist. Die Motive für die beiden Techniken sind ebenfalls nicht dieselben, denn der Absender einer steganographischen Nachricht möchte geheime Informationen übermitteln können, ohne den Verdacht eines Wächters zu erwecken, wohingegen der Absender eines verdeckt gekennzeichneten Bildes möchte, daß die versteckte Nachricht nicht etwa ein Werk in wahrnehmbarer Weise stört und daß sie nicht einfach zerstört werden kann, wobei aber die Tatsache, daß gegebenenfalls irgendwer über das Vorhandensein einer versteckten Nachricht in einem Bild Bescheid weiß, nicht hinderlich ist, sondern im Gegenteil eine vorteilhafte Abschreckungswirkung haben kann, wenn das verdeckte Kennzeichnen beispielsweise dazu vorgesehen ist, wie ein Zeichen verwendet zu werden, das den Bildern ermöglicht, in den Genuß des Schutzes zu gelangen, der durch die Autorenrechte und insbesondere durch das Urheberrecht gewährt wird. In diesem Fall wird das verdeckte Kennzeichnen ausgeführt, indem in ein Bild oder in eine Bildsequenz eine Information eingebettet wird, die das Werk und seinen Eigentümer kenntlich macht. Das automatische Lesen der eingebetteten Information ermöglicht zu verifizieren, ob das Werk nicht etwa gesetzwidrig verbreitet worden ist oder aber ob der Autor die entsprechenden Rechte wohl wahrgenommen hat. Das verdeckte Kennzeichnen von Bildern ermöglicht außerdem eine Weiterverfolgung von Dokumenten, wenn die eingebetteten Informationen für die Person, die sie gekauft hat, charakteristisch sind, wodurch es möglich ist, bei Kopien oder unzulässiger Verbreitung automatisch den für die Tat Verantwortlichen zu erkennen.
Das gleiche gilt für alle Anwendungen der automatischen Indizierung eines Bildes oder von Bildsequenzen.
Der Vorteil der Verwendung der verdeckten Kennzeichnung besteht in der Möglichkeit, Überwachungen zu automatisieren. Angesichts der Vielfältigkeit der Übertragungskanäle ist es nämlich utopisch zu glauben, die Verbreitung von audiovisuellen Werken manuell überwachen zu können. Die verdeckte Kennzeichnung von Bildern erlaubt, dieses Problem teilweise zu lösen, in dem sie ermöglicht, von einem Werk automatisch seine Identifikationsnummer und gegebenenfalls seine Herkunft zu bestimmen, wobei es dann der Autorengesellschaft überlassen bleibt festzustellen, ob das Werk wirklich rechtmäßig verbreitet worden ist. Die Techniken der verdeckten Kennzeichnung bieten außerdem den Vorteil, daß sie weder eine Standardisierung noch vorherige Vereinbarungen z wischen den verschiedenen Akteuren benötigen - im Gegensatz zur derzeitigen Praxis des materiellen Kopierschutzes, einschließlich desjenigen für digitale Videoplatten, die auch unter der angelsächsischen Abkürzung DVD für "Digital Video Disk" bekannt sind.
Um eine Nachricht durch ein Bild übermitteln zu können, ist es notwendig, dieses auf die eine oder andere Weise zu verändern. Die durch die verdeckte Kennzeichnung vorgenommenen Modifikationen müssen jedoch eine bestimmte Anzahl von Bedingungen erfüllen, damit sie mit den Anwendungen, auf die sie abzielen, verträglich sind.
So darf die verdeckte Kennzeichnung die Bilder nicht auf sichtbare Weise verändern, um nicht die Qualität dieser zu verschlechtern. Folglich muß die Kennzeichnung unauffällig sein.
Wie weiter unten gezeigt wird, erfordern viele der in der Literatur beschriebenen Verfahren zum verdeckten Kennzeichnen für das Lesender Nachricht zusätzlich zu der Anwesenheit des modifizierten Bildes diejenige des Originals. Deswegen erscheinen diese Verfahren für den Schutz der Werke durch das Urheberrecht völlig ungeeignet, denn sie setzen voraus, daß der Autor ein Werk ausfindig gemacht hätte, daß ihm scheinbar gehört und unzulässigerweise verbreitet worden ist bevor durch das Lesen der verdeckten Kennzeichnung nachgewiesen werden kann, daß das Werk tatsächlich ihm gehört. Es ist in diesem Fall wohl schneller, die beiden Werke zu vergleichen, als eine verdeckte Kennzeichnung zu lesen... Folglich sollte für Anwendungen der automatischen "Überwachung" das Lesen einer verdeckten Kennzeichnung allein aus dem modifizierten Bild möglich sein. Die Verfahren der verdeckten Kennzeichnung, die beim Lesen beide Bilder benutzen, können jedoch für die Anwendungen der Weiterverfolgung, auf die zuvor hingewiesen worden ist, verwendet werden, wobei die Identität des Werkes dann sicher ist und die verdeckte Kennzeichnung nur ermöglicht, Auskunft über die Herkunft der betroffenen Kopie zu geben.
Das verdeckte Kennzeichnen wird zum trivialen Problem, wenn sicher ist, daß das verdeckt gekennzeichnete Bild in keiner Weise verändert wird. Es genügt dann, die niedrigstwertigen Bits der Bildelemente zu modifizieren, wobei es sich um einen völlig unsichtbaren Kunstgriff handelt, der ermöglicht, genau so viele Bits einzubetten, wie es Bildelemente gibt. Jedoch wird dieser Idealfall in der Praxis nie angetroffen, da die Bilder und insbesondere die Bildsequenzen fast immer komprimiert werden, um bei einer Übertragung eine annehmbare Übertragungsgeschwindigkeit zu erzielen oder um bei einer Speicherung Speicherplatz zu sparen. Diese Kompression kann verlustfrei sein, wie im Fall der Norm "JPEG useless", sie ist jedoch aus Gründen der Leistungsfähigkeit der Übertragung von Bildern nach den Normen JPEG und MPEG meist irreversibel. Es ist folglich zwingend, daß die verdeckte Kennzeichnung diese Transformationen überstehen kann, was um so schwieriger ist, je geringer die Datenrate ist, mit der die Kompression erfolgt. Folglich muß die Kennzeichnung hinreichend stark sein, was eine zu der vorhergehenden Bedingung der Unsichtbarkeit gegensätzliche Bedingung ist.
Außerdem ist es nicht selten, daß ein Werk insbesondere bei seiner Verbreitung verändert wird, um die Übertragung zu vereinfachen. Die Nachbearbeitung führt beispielsweise häufig ein "cropping", d. h. ein Abschneiden von Sequenzen, ein. Das Format dieser kann ebenfalls verändert werden, insbesondere beim Übergang von der amerikanischen Fernsehnorm (Bilder mit 720 · 480 Bildelementen mit 30 Hz) zum europäischen Format (Bilder mit 720 · 576 Bildelementen mit 25 Hz). Ein Resampling, um die Bilder zu strecken oder zu verkleinern, ist ebenfalls häufig.
Im Zusammenhang mit der verdeckten Markierung von Bildern stellen diese Transformationen zwei Arten von Problemen dar, einerseits sind sie im allgemeinen nicht reversibel, wobei dies selbstverständlich für ein Abschneiden aber auch für eine Bildverkleinerung gilt, denn viele Informationen gehen in den höheren Frequenzen des Bildes verloren, und andererseits ist die Transformationsbeziehung, die zwischen dem Ausgangsbild und dem transformierten Bild besteht, im allgemeinen nicht bekannt. Daraus folgt, daß die verdeckte Kennzeichnung entweder gegenüber geometrischen Transformationen invariant sein muß, oder aber von einer zusätzlichen Information begleitet sein muß, die die Synchronisierung ermöglicht. Diese Transformation kann die Form einer bestimmten verdeckten Kennzeichnung annehmen, die ermöglicht, die ausgeführte Transformation zu ermitteln.
Die Bearbeitung von digitalen Bildern und Filmen ist besonders einfach, sobald der Anwender über eine Bildbearbeitungssoftware verfügt, selbst wenn diese nur dürftig ist. Zu den einfachsten Manipulationen zählen die geometrischen Transformationen; sie bestehen insbesondere in der Ausführung von Bildschnitten, Vergrößerungen oder Verkleinerungen, der Montage mehrerer Sequenzen, dem Verbinden (Kleben) und seltener dem Drehen. Die Frequenzveränderungen sind verhältnismäßig einfach, wie auch die Farbmanipulationen, die darin bestehen, bei Filmen von Farbe zu Schwarzweiß oder umgekehrt überzugehen, Verteilungen zu transformieren usw. Außerdem muß die Möglichkeit des Übergangs von der digitalen in die analoge Form oder umgekehrt der Verfahren der Photokopie eines Bildes, der Digitalisierung von Videokassetten usw. erwähnt werden, die ein zusätzliches Rauschen sowie geometrische oder farbmetrische Verzerrungen mit sich bringen.
Außerdem soll die verdeckte Kennzeichnung widerstandsfähig gegenüber vorsätzlichen Angriffen von Piraten sein, die zum Ziel haben, die Markierung zu zerstören, um ein Werk verbreiten zu können, ohne die Autorenrechte zu bezahlen. Die Angriffsmethoden können zweierlei Art sein: Entweder bestehen sie aus Versuchen zur Umkehrung des Kennzeichnungsverfahrens, blind oder mit Hilfe der teilweisen oder vollständigen Kenntnis des Kennzeichnungsalgorithmus oder aber aus der Störung der Nachricht durch Hinzufügen von Rauschen oder beispielsweise durch eine Transformation durch Filterung. Die erste Angriffsart kann abgewehrt werden, indem Verfahren benutzt werden, die den in der Kryptographie benutzten ähneln, wobei geheime Schlüssel verwendet werden. Bei der zweiten Angriffsart muß der Pirat einen Kompromiß zwischen der Stärke der Störung und der sich daraus ergebenden Verschlechterung der Qualität eingehen. Diese Tatsache kann übrigens ausgenutzt werden, um eine gute verdeckte Kennzeichnung zu verwirklichen, indem mit einer Stärke gekennzeichnet wird, die knapp unterhalb der Sichtbarkeitsschwelle liegt, wobei das ganze Problem darin besteht, diese Schwelle genau zu bestimmen.
Schließlich soll die verdeckte Kernzeichnung von geringer Komplexität sein. Die Komplexität stellt für ein reales System ein entscheidendes Problem dar. Wenn auch mitunter das Schreiben mit Zwischenspeicherung erfolgen kann, so muß das Lesen für Überwachungsanwendungen zwangsläufig online ausgeführt werden können, wobei jedoch häufig gerade dieser Schritt die meiste Rechenzeit benötigt.
Obwohl das Gebiet der verdeckten Kennzeichnung verhältnismäßig jung ist, ist in der Literatur bereits eine große Anzahl von Lösungsansätzen vorgeschlagen worden. Diese setzen verschiedene Verfahren der verdeckten Kennzeichnung ein, die sich in Verfahren der räumlichen oder bildpunktweisen verdeckten Kennzeichnung, Verfahren der verdeckten Kennzeichnung mittels Transformierter oder Frequenztransformierter und Verfahren der verdeckten Kennzeichnung mittels Codierung einteilen lassen.
Weitere Lösungsansätze für verdeckte Kennzeichnungen vom Typ Tonsignal, Text oder synthetische Bilder, die ebenfalls untersucht worden sind, schlagen einen speziellen Algorithmus vor. Andere schlagen eine allgemeinere Formulierung des Problems insbesondere in Ausdrücken der Informationstheorie vor. Die Artikel, die sie beschreiben, versuchen, den verfügbaren Übertragungsbereich für die verdeckt gekennzeichnete Nachricht quantitativ genauer zu bestimmen. Weitere Artikel präsentieren spezifische Verfahren des Angriffs auf eine besondere oder allgemeinere Technik der verdeckten Kennzeichnung. Parallel erscheinen Formalisierungstechniken dieser Angriffe, die beispielsweise die Spieltheorie oder die Konzepte der Kryptographie und der Steganographie benutzen, wobei sie zum Ziel haben, die Entwicklung von robusteren Systemen zu ermöglichen.
Bei den Verfahren der räumlichen verdeckten Kennzeichnung erfolgt das Schreiben der Nachricht direkt auf der Ebene des Bildes, im allgemeinen durch eine Modifikation der Luminanz der Bildelemente.
Bei den Verfahren der verdeckten Kennzeichnung mittels Transformierter erfolgt das Schreiben der Nachricht in eine Transformierte des Bildes oder einer Sequenz. Die benutzten Transformierten sind im allgemeinen vom Typ Fourier- Transformierte, Cosinus-Tranformierte oder Wavelet-Transformierte.
Schließlich wird bei den Verfahren der verdeckten Kennzeichnung durch Codieren die verdeckte Kennzeichnung eingebettet, indem bestimmte Elemente, die bei einer Codierung erhalten werden, direkt modifiziert werden. Dies betrifft beispielsweise die Bewegungsvektoren bei der MPEG-Codierung, die Codierung in Blöcken oder "matching blocs" einer fraktalen Kompression usw. Die Verfahren der DCT-Codierung, entsprechend der angelsächsischen Abkürzung für "Discret Cosinus Transform", mittels Cosinus-Transformierten können ebenfalls dieser Kategorie zugerechnet werden.
Diese großen Familien können außerdem in zwei Unterfamilien eingeteilt werden, welche die Verfahren der blockweisen Codierung und die Verfahren der Bildcodierung umfassen. Bei den Verfahren der blockweisen Codierung vom Typ DCT oder beispielsweise den Verfahren der bildpunktweisen Codierung ist die Codierungseinheit der Block, in den ein Bit oder mehrere Bits eingebettet werden. Bei den Verfahren der Bildcodierung wird das verdeckte Kennzeichnen über das gesamte Bild ausgeführt, indem beispielsweise eine globale Fourier- Transformierte des Bildes verwendet wird.
Die räumlichen Verfahren gehören zu den ältesten und einfachsten. Der Vorteil dieser Verfahren besteht darin, daß sie im allgemeinen ein schnelleres Schreiben der verdeckten Kennzeichnung ermöglichen und dafür keine aufwendigen Transformationen benötigen, wie dies beispielsweise für die Verfahren der Fall ist, die auf der Fourier-Transformation beruhen. Sie sind jedoch weniger robust gegenüber Kompressionsverfahren, die auf der Berechnung der DCT- Transformierten beruhen.
Von den Verfahren zum räumlichen verdeckten Kennzeichnen beruht der "Patchwork" genannte Algorithmus von Bender, Gruhl, Morimoto, wovon eine Beschreibung in dem Artikel mit dem Titel "Techniques for Data Hiding", veröffentlicht in den SPIE Proceedings, Bd. 2420, S. 40, Februar 1995, zu finden ist, auf den Beobachtungen, daß das Auge gegenüber schwachen Veränderungen der Luminanz, insbesondere wenn diese zufällig sind und einem schwachen Rauschen ähneln, wenig empfindlich ist und daß die Mittelwerte der Luminanzen zweier Mengen von N zufällig ausgewählten Punkten "durchschnittlich" gleich sind, wenn die Anzahl N groß ist.
Bei diesem Algorithmus erfolgt das Schreiben, indem ein geheimer Schlüssel verwendet wird und n Paare von Punkten Ai und Bi mit der Luminanz ai bzw. bi auf pseudo-zufällige Weise in dem Bild gewählt werden. Die Luminanz der ausgewählten Punkte wird entsprechend den Relationen ai' = ai + 1 und bi' = bi - 1 verändert. Da die Punkte zufällig ausgewählt sind, wird die Differenz ai - bi im Mittel null sein, wenn N hinreichend groß ist. Hingegen wird die Differenz a'i - b'i im Mittel in etwa gleich 2 sein, wodurch die Decodierung möglich ist.
Um die Anfangspunkte wiederzufinden, erfolgt das Lesen mit Hilfe des geheimen Schlüssels. Eine Berechnung der Größe S = (ai - bi) ermöglicht zu entscheiden, daß das Bild verdeckt markiert ist, wenn S 2 N ist.
Dieses Verfahren ermöglicht, ein einziges Bit in das Bild einzubetten; es kann jedoch für mehrere Bits verallgemeinert werden, indem mehrere gesonderte Punktmengen ausgewählt werden. Es hat zum Vorteil, daß es eine gute Unsichtbarkeit und eine gute Widerstandsfähigkeit gegenüber Transformationen wie der Kompression, dem Hinzufügen von Rauschen usw. aufweist und dies in um so stärkerem Maße, je größer die Zahl N ist. Es besitzt außerdem aufgrund der Verteilung der Informationen eine gute Widerstandsfähigkeit gegenüber einem Schneiden des Bildes sowie gegenüber Angriffen, sofern der Schlüssel nicht bekannt ist.
Hingegen weist es die Nachteile einer geringen Widerstandsfähigkeit gegenüber geometrischen Transformationen und eines erforderlichen Kompromisses zwischen der Anzahl an einzubettenden Bits und der Widerstandsfähigkeit der Nachricht auf.
Ein anderes Verfahren, das die Amplitudenmodulation der Chrominanz verwendet, ist in dem Artikel von Kutter, Jordan, Bossen mit dem Titel "Digital Signature of Color Image Using Amplitude Modulation", veröffentlicht in den SPIE El 97, beschrieben und besteht darin, die Blaukomponente des Chrominanzsignals, für die das Auge wenig empfindlich ist, zu modifizieren und in Abhängigkeit von der Stärke der Kennzeichnung auf die Modulation des Luminanzsignals einzuwirken, wobei der Tatsache Rechnung getragen wird, daß die Retina für Kontraste stärker empfindlich ist als für die eigentliche Luminanz und das Auflösungsvermögen des Auges bei starken Luminanzen weniger gut ist. Es wird eine Abtastung im Zickzack ausgeführt, um sich von der Größe des Bildes zu befreien. Das Lesen erfolgt mit Hilfe einer linearen Voraussage. Gemäß diesem Verfahren kann die Nachricht auf robuste Weise geschrieben werden, indem das gleiche Bit mehrmals eingebettet wird. Das Abtasten im Zickzack ermöglicht, sich von der Größe des Bildes sowie von einer Synchronisierung im Fall des Abschneidens des unteren oder linken Teils des Bildes zu befreien. Das Verfahren weist außerdem eine gute Widerstandsfähigkeit gegenüber Angriffen auf. Hingegen wird die Komplexität der Berechnungen in dem Fall sehr hoch, wenn geometrische Transformationen ausgeführt werden müssen, denn dieses Verfahren erfordert eine erschöpfende Suche im Parameterraum.
Ein weiteres Verfahren zum räumlichen verdeckten Kennzeichnen, das von den Autoren Jean Francois Delaigle und Benoit Macq im Talisman Projet Report, Jan. 97, unter dem Titel "Digital Watermarking" beschrieben ist, benutzt einen Algorithmus, der das Einbetten eines Bits pro Bildblock der Größe n x n ermöglicht. Ein Block ist in zwei Gruppen von Bildelementen A und B unterteilt. Die Werte der Bildelemente der beiden Gruppen werden derart modifiziert, daß die Differenz der Mittelwerte der Luminanzen der Gruppen A und B Träger des zu übermittelnden Bits ist. Diese Modifikationen erfolgen, ohne den globalen Mittelwert der Luminanzen des Blocks zu verändern, um eine gute Unsichtbarkeit zu bewahren. Die Kennzeichnungsstärke hängt von einem Parameter I ab. Mit diesem Verfahren wird eine Widerstandsfähigkeit gegenüber einer Codierung nach der JPEG-Norm von 70% mit einer Fehlerquote von 5% für eine Luminanz der Kennzeichnung von I = 5 erhalten. Die Kennzeichnung ist für nicht sehr hohe Kennzeichnungsstärken, für I < 8, unsichtbar, und die Robustheit hängt für eine bestimmte Kennzeichnungsstärke von der Größe des Blocks ab. Jedoch weist das Verfahren einen großen Nachteil auf, der darin besteht, daß es eine geringe Widerstandsfähigkeit gegenüber geometrischen Transformationen und Angriffen vom Typ der Unterdrückung von Zeilen oder Spalten aufweist.
Die Codierungsverfahren mittels Frequenztransformierter, wie sie in der Patentanmeldung DE 19 521 969 beschrieben sind, weisen zwei Vorteile auf. Sie ermöglichen einerseits, die Kompression zu antizipieren, indem sie die Informationen der verdeckten Kennzeichnung in die Komponenten des Bildes schreiben, welche die geringsten Aussichten haben, verändert zu werden, und andererseits ermöglichen sie die Berücksichtigung der Wahrnehmungseigenschaften des menschlichen Auges, um die weniger wahrnehmbaren Komponenten stärker zu kennzeichnen.
Diese beiden Aspekte sind jedoch antithetisch, da sich die Kompressionsverfahren ja gerade auf die Wahrnehmungseigenschaften des Auges stützen.
Nach einem ersten Lösungsansatz, der von Eckhard Koch und Jian Zhao in dem Artikel mit dem Titel "Embedding Robust Labels into Images for Copyright Protection", Proc. Int. Congr. Intellectual Property Rights for Spezialized Information, Knowledge and New Technologies, Wien (Österreich), August 95, veröffentlicht worden ist, erfolgt das Schreiben der Nachricht zur verdeckten Kennzeichnung durch Modifizieren der Koeffizienten der diskreten Cosinus- Transformierten DCT unter Vorwegnahme des Quantifizierungsrauschens, das durch die Kompressionen des Bildes nach dem JPEG- oder dem MPEG-Verfahren eingeführt wird, um das Überdauern der verdeckten Kennzeichnung bei diesen Kompressionen sicherzustellen. Dieser Lösungsansatz ermöglicht, eine gute Widerstandsfähigkeit gegenüber der Kompression zu erzielen, denn das Quantifizierungsrauschen ist aufgrund der Tatsache, daß es bei der Kennzeichnung vorweggenommen worden ist, kein zufälliges Rauschen mehr. Die Widerstandsfähigkeit hängt selbstverständlich vom Quantifizierungsfaktor Q ab, der bei der Kennzeichnung verwendet worden ist. Je höher der Faktor Q ist, desto besser ist die Robustheit, jedoch auf Kosten einer Zunahme der Sichtbarkeit. Ein weiterer Vorteil des Verfahrens besteht darin, daß der Algorithmus zur verdeckten Kennzeichnung direkt in einer JPEG- oder MPEG-Codiereinrichtung gebraucht werden kann, wodurch es möglich ist, vorteilhaft die Berechnungen der DCT-Koeffizienten, die bei der Kompression ausgeführt werden, direkt zu nutzen. Die Leistungsfähigkeit des Verfahrens kann sich jedoch rapide verschlechtern, wenn die Blöcke der DCT- Koeffizienten des Bildes nicht mit den Blöcken des Ausgangsbildes übereinstimmen, was beispielsweise auftritt, wenn das Bild geringfügig verschoben worden ist; in diesem Fall ist das Quantifizierungsrauschen nicht mehr vorhersehbar.
Ein weiteres Verfahren, das von Ingemar Cox, Joe Killian, Thomson Leighton, Talal Shamoon in dem in den IEEE Trans. on Image Processing, Bd. 6, Nr. 12, Dezember 97 erschienenen Artikel mit dem Titel "Secure Spread Spectrum watermarking for Multimedia" beschrieben ist, verfolgt einen Lösungsansatz der "Bandspreizung", der beinhaltet, die Nachricht zum verdeckten Kennzeichnen in alle Frequenzkomponenten des Bildes einzubetten, nachdem die Berechnung der DCT-Koeffizienten ausgeführt worden ist, wodurch zwar die Energie der Nachricht über jeder der Frequenzen nicht nachweisbar wird, jedoch das Signal- Rausch-Verhältnis größer wird. Außerdem werden Sichtbarkeitskriterien benutzt, um die Stärke der Kennzeichnung den Frequenzkomponenten entsprechend zu gewichten. Dieses Verfahren hat zum Vorteil, daß es eine sehr gute Widerstandsfähigkeit gegenüber Kompressionen vom Typ JPEG und MPEG sowie gegenüber geometrischen Transformationen aufweist, sofern diese Transformationen bekannt sind. Das Verfahren bietet Möglichkeiten zur mehrfachen verdeckten Kennzeichnung. Es widersteht gut kolludierenden Angriffen, indem es eine Mittelung über Dokumente ausführt, die verschiedene verdeckte Kennzeichen tragen, und Störversuchen aufgrund der Tatsache, daß bei Unkenntnis der Nachricht zum verdeckten Kennzeichnen ein hinreichend starkes Rauschen an allen Frequenzen hinzugefügt werden muß, um die verdeckte Kennzeichnung zu zerstören, wodurch sich die visuelle Qualität des Bildes verschlechtert. Jedoch weist das Verfahren einen großen Nachteil auf, der darin besteht, daß das Ausgangsbild benötigt wird, um die verdeckte Kennzeichnung wieder aufzufinden, wobei diese durch Subtraktion des verdeckt gekennzeichneten, transformierten Bildes von dem transformierten Ausgangsbild erhalten wird.
Ein weiteres Verfahren, das in einem Artikel von Joseph O'Ruanaidh, Thierry Pun mit dem Titel "Rotation, Scale and Translation Invariant Digital Image Wotermarking", erschienen in den Proceedings der IEEE ICIP 97, Bd. 1, S. 536-539, Santa Barbara, beschrieben ist, besteht darin, einen Raum zu verwenden, der gegen Drehung, Verschiebung und Skalierung invariant ist, um sich von geometrischen Transformationen, die in dem Bild ausgeführt werden können, zu befreien. Dies wird erreicht, indem die Eigenschaften der Fourier-Mellin-Transformierten ausgenutzt werden. Das Verfahren hat den Vorteil, daß es eine hohe Widerstandsfähigkeit gegenüber geometrischen Transformationen aufweist, ohne eine vorangehende Synchronisierung zu benötigen. Jedoch werden die Invarianzeigenschaften der Fourier-Mellin-Transformierten nicht mehr bewahrt, wenn die Kreisschiebung durch ein "cropping" ersetzt wird. Zum anderen sind die Berechnungen, die Transformationen in einer logarithmischen Polarebene erfordern, verhältnismäßig komplex.
Ein weiteres Verfahren, das in dem Artikel von Joseph O'Ruanaidh, W. Dowling, F. Boland mit dem Titel "Phase Watermarking of Digital Images", veröffentlicht durch die ICIP 96, beschrieben ist, verwendet eine Fourier-Transformierte, wobei die Nachricht zum verdeckten Kennzeichnen mit Hilfe einer Phasenmodulation geschrieben wird. Das Verfahren hat zum Vorteil, daß es eine Widerstandsfähigkeit gegenüber JPEG- und MPEG-Kompressionsverfahren bietet. Es hat jedoch den Nachteil, daß die Phasenänderungen stärker sichtbar erscheinen als die Amplitudenmodulationen.
Ein anderes Verfahren, das in dem Artikel von Mitchell Swanson, Bin Zhu, Ahmed Tewfik mit dem Titel "Multiresolution Scene-based Video Watermarking Using Pereeptual Models", veröffentlicht im IEEE Journal on selected areas in communication, Bd. 16, Nr. 4, Mai 98, beschrieben ist, ist speziell für das verdeckte Kennzeichnen von Vidosequenzen bestimmt. Es besteht darin, in einem Raum zu arbeiten, der unter Verwendung eines Wahrnehmungsmodells durch Zerlegen in Zeit-Wavelets transformiert worden ist. Gemäß dem Verfahren wird eine Nachricht zum verdeckten Kennzeichnen mit Hilfe von zwei Schlüsseln erzeugt, wovon einer der zu übermittelnden Information entspricht und der andere mit Hilfe der ursprünglichen Videosequenz berechnet wird. Der zweite Schlüssel ermöglicht, das bekannte Problem des "gegenseitigen Sperrens" zu lösen, d. h. zu vermeiden, daß ein Pirat eine Sequenz mit seiner eigenen Nachricht verdeckt kennzeichnet und dann das zeitlich frühere Vorhandensein seiner verdeckten Kennzeichnung vorgibt. Diese Informationen werden mit Hilfe eines BBS- Generators verschlüsselt. Die Videosequenz wird dann in Szenen segmentiert, und jede Szene wird in Zeit-Wavelets zerlegt, um in den niedrigen Frequenzen die statistischen Komponenten der Szene und in den hohen Frequenzen die dynamischen Elemente dieser erscheinen zu lassen. Für jeden Wavelet-Koeffizienten wird eine räumliche Wahrnehmungsmaske berechnet, danach wird jeder Wavelet- Koeffizient durch Berechnen der DCT-Koeffizienten zerlegt, um eine Frequenzmaske zu erzeugen und eine Aufbereitung der verdeckten Kennzeichnung mit Hilfe der auf diese Weise bestimmten Masken auszuführen und sie auf die Zeit- Wavelets anzuwenden. Um beim Empfang die Nachricht der verdeckten Kennzeichnung aufzuspüren, ist es notwendig, die ursprüngliche Sequenz sowie die eingebettete Nachricht der verdeckten Kennzeichnung zu kennen. Diese kann erhalten werden, ohne daß eine Information zur zeitlichen Synchronisierung über die wiedergewonnene Sequenz erforderlich ist. Das Verfahren hat zum Vorteil, eine gute Widerstandsfähigkeit gegenüber an den Videosequenzen ausgeführten Veränderungen aufzuweisen, in subtiler Weise durch eine Verwendung von Maskierungskriterien die Sichtbarkeit zu berücksichtigen und eine große Redundanz beim Schreiben der Informationen aufzuweisen, das in mehrere Frequenzbänder erfolgt. Der Nachteil dieses Verfahrens besteht jedoch darin, daß es die Verwendung der ursprünglichen Sequenz zum Lesen der verdeckten Kennzeichnung benötigt und nur die Einbettung eines einzigen Bits erlaubt.
Bei den Codierungsverfahren wird die verdeckte Kennzeichnung eingebettet, indem bestimmte Elemente, die bei der Codierung eines Bildes erhalten werden, wie beispielsweise die Bewegungsvektoren der Codierung nach der MPEG-Norm oder die "matching blocs" der fraktalen Kompression, modifiziert werden. Diese Verfahren ermöglichen, direkt in den codierten Bildern zu arbeiten, wodurch ein schnelleres Schreiben und vor allem ein schnelleres Lesen der verdeckten Kennzeichnung möglich sind. Sie ermöglichen außerdem, besser die Störungen zu berücksichtigen, die durch die Codierung eingeführt werden. Leider kann diese Berücksichtigung bei einer weiteren Codierung mit anderen Parametern unzulänglich werden.
Ein erstes von T. Vynne, F. Jordan in einem Artikel mit dem Titel "Embedding a Digital Signature in a Video Sequence using Motion Vectors", Reprint of Special Session on copyright protection and access control for multimedia services of ICIP 96, beschriebenes Verfahren hat zum Inhalt, die Nachricht zum verdeckten Kennzeichnen durch Modifizieren der Bewegungsvektoren des MPEG- Codierungsverfahrens zu schreiben. Das Codierungsverfahren beginnt mit der Auswahl einer Gesamtheit von Blöcken in dem Bild, um die Informationen der verdeckten Kennzeichnung einzubetten, und mit einer Berechnung des optimalen Bewegungsvektors in bezug auf das vorhergehende Bild für jeden der Blöcke. Das Schreiben der Nachricht erfolgt durch Modifizieren des niedrigstwertigen Bits der Komponenten des Bewegungsvektors. Die Sichtbarkeit der verdeckten Kennzeichnung kann verringert werden, indem sichergestellt wird, daß die Varianzen der Blöcke, die mit Hilfe des ursprünglichen Bewegungsvektors und des modifizierten Bewegungsvektors erhalten werden, nahe beieinander liegen. Der Vorteil dieses Verfahrens ist, daß es ein verdecktes Kennzeichnen direkt in den Strom der MPEG-Übertragung hinein ermöglicht. Hingegen ist das Verfahren gegenüber verwendeten Bewegungsschätzfunktionen sowie einer wiederholten Codierung empfindlich.
Ein zweites Codierungsverfahren der Autoren Joan Puate, F. Jordan, das in dem Artikel mit dem Titel "Using Fractal compression Scheme to Embed a Digital Signature into an Image", Proc. SPIE Video Techniques and Software for Fullservice Networks, Oktober 96, beschrieben ist, besteht darin, eine verdeckte Kennzeichnung zu schreiben, indem die bei der fraktalen Codierung verwendeten Parameter modifiziert werden. Die Robustheit des Verfahrens hängt von der Größe der Blöcke ab, in die das Bild eingeteilt ist, um die Codierung durchzuführen. Je größer die Blöcke sind, desto robuster ist das Verfahren, aber desto weniger gut ist auch die Qualität des erhaltenen Bildes. Zum anderen ist die Berechnungszeit beträchtlich.
Das Ziel der Erfindung besteht darin, die genannten Probleme zu lösen.
Dazu hat die Erfindung ein Verfahren zum verdeckten Kennzeichnen von Bildern für die Verarbeitung und die Übertragung von Stand- und Videobildern zum Gegenstand, des Typs, der darin besteht, in die Bilder vor ihrer Übertragung durch Modifikation der charakteristischen Daten der Bilder eine Nachricht einzubetten, dadurch gekennzeichnet, daß es darin besteht, durch periodische Einbettung einer binären Matrix P in das Bild eine begleitende verdeckte Kennzeichnung vorzunehmen, um beim Empfang die Koordinaten des Ursprungs des Ausgangsbildes zu bestimmten und die Justierung der empfangenen Bilder in bezug auf diesen Ursprung zu ermöglichen, um das Lesen der eingebetteten Nachricht zu ermöglichen.
Das Verfahren gemäß der Erfindung hat zum Vorteil, daß es die Ausführung einer verdeckten Kennzeichnung ermöglicht, die gleichzeitig robust, zuverlässig und von geringer Komplexität ist.
Die verdeckte Kennzeichnung ist vollkommen unsichtbar, sogar auf qualitativ hochwertigen professionellen Einrichtungen zur Sichtdarstellung.
Im Unterschied zu den oben genannten Verfahren des Standes der Technik kann die verdeckte Kennzeichnung gelesen werden, ohne das nicht gekennzeichnete Ausgangsbild zu benötigen, wodurch es möglich ist, dieses Verfahren auf die automatische Überwachung der Verbreitung anzuwenden.
Die Kennzeichnung widersteht gut den MPEG- und JPEG- Kompressionen.
Das Verfahren der begleitenden verdeckten Kennzeichnung, das ausgeführt wird, bietet außerdem eine Widerstandsfähigkeit gegenüber Bildschnitten, was in Anbetracht der derzeitigen Videocodierungs- und Videoübertragungssysteme wichtig ist. Die geringe Komplexität dieses Algorithmus beim Lesen stellt einen sicheren Vorteil gegenüber Synchronisierungsverfahren durch erschöpfende Suche wie beispielsweise dem räumlichen Algorithmus der EPFL [1 Ecole polytechnique fédérale de Lausanne] dar.
Schließlich ermöglicht es auch, sich der Zuverlässigkeit der gelesenen Nachricht zu versichern, indem es Informationen über die Qualität dieser Nachricht liefert. Die Fehlerquote über die Endnachricht sowie die Latenzzeit der Entscheidung können parametrisiert werden, um eine Anpassung an die Beschränkungen jeder Anwendung vorzunehmen.
Weitere Merkmale und Vorteile der Erfindung werden anhand der nachfolgenden Beschreibung deutlich, die mit Bezug auf die beigefügte Zeichnung vorgenommen wurde, worin
- Fig. 1 die wichtigsten Schritte der Bearbeitung, um die Übertragung einer verdeckten Kennzeichnung eines Bildes gemäß der Erfindung zu verwirklichen, zeigt;
- die Fig. 2 und 3 eine Veranschaulichung des Verfahrens zum verdeckten Kennzeichnen mittels Codierung durch die DCT-Transformierte, das gemäß der Erfindung ausgeführt wird, zeigen;
- Fig. 4 ein Ablaufdiagramm zeigt, das die Kartierung der DCT- Koeffizienten der verdeckten Kennzeichnung, die gemäß der Erfindung über dem gesamten Bild ausgeführt wird, veranschaulicht;
- die Fig. 5 und 6 die verschiedenen Schritte des Verfahrens zum verdeckten Kennzeichnen gemäß der Erfindung in Form eines Ablaufdiagramms zeigen;
- Fig. 7 die Darstellung einer Matrix für die begleitende verdeckte Kennzeichnung gemäß der Erfindung ist;
- Fig. 8 ein Schema zeigt, welches das Prinzip des Schreibens einer begleitenden verdeckten Kennzeichnung gemäß der Erfindung zeigt;
- Fig. 9 ein Schema zeigt, welches das Prinzip des Lesens einer begleitenden verdeckten Kennzeichnung gemäß der Erfindung zeigt;
- Fig. 10 die Schritte der Nachbearbeitung, die von der Erfindung ausgeführt wird, in Form eines Ablaufdiagramms zeigt.
Das Verfahren zum verdeckten Kennzeichnen für die Übertragung von Bildern gemäß der Erfindung, das in Fig. 1 gezeigt ist, benutzt drei Algorithmen: einen Algorithmus zur verdeckten Basiskennzeichnung 1, der ermöglicht, die Nachricht der verdeckten Kennzeichnung in das Bild einzubetten, einen Algorithmus zur begleitenden verdeckten Kennzeichnung 2, der eine erneute räumliche Synchronisierung des Bildes ermöglicht, wenn dieses eine Verschiebung erfahren hat, und einen Nachbearbeitungsalgorithmus 3, der die Gewährleistung der Zuverlässigkeit der Daten, die durch Lesen der verdeckten Basiskennzeichnung 4 und der begleitenden verdeckten Kennzeichnung 5 gewonnen worden sind, ermöglicht. Diese Algorithmen können sowohl für die Bearbeitung von Standbildern als auch für die verdeckte Kennzeichnung von Videobildern angewandt werden.
Die Funktion des Algorithmus zur verdeckten Basiskennzeichnung 1 ist die Ausführung einer Modulation der DCT-Koeffizienten der transformierten Blöcke des Bildes. Vor der Ausführung dieser Transformation wird das Bild in aneinandergrenzende Blöcke der Größe N · N zerlegt, danach wird jeder der Blöcke in einen Block mit N · N Koeffizienten F(u, v) transformiert, der durch folgende bekannte Relation erhalten wird:
mit u = 0 bis N-1,
v = 0 bis N-1,
c(i) für i = 0 und
c(i) = 1 für i = 1 bis N-1.
Wie das Beispiel von Fig. 2 zeigt, läßt jeder Block 4 des Bildes mit N · N Bildelementen einen Block 5 mit N · N DCT-Koeffizienten entstehen. In einem Bildblock ist jedes Bildelement durch seine Koordinaten (x, y) in bezug auf den Ursprung des Blocks gekennzeichnet. Ebenso ist jeder Koeffizient des DCT- Blocks durch seine Koordinaten (u, v) in bezug auf den Ursprung des Blocks gekennzeichnet. Das Einbetten einer Nachricht zum verdeckten Kennzeichnen erfolgt, indem in der in den Fig. 2 und 3 dargestellten Weise bestimmte Koeffizienten, aus denen die DCT-Blöcke gebildet sind, verändert werden. Die Auswahl der Blöcke und ihrer Koeffizienten erfolgt zufällig in der in Fig. 4 gezeigten Weise mit Hilfe eines Generators für die Blockadresse 6, der in jedem der Blöcke die zu verändernden Koeffizienten bestimmt. Jedes Bit bi der einzubettenden Nachricht ist einem Block des Bildes zugeordnet. Dieses Bit wird durch Modifizieren der beiden DCT-Koeffizienten c&sub0; und c&sub1; dieses Blocks eingebettet.
Die Auswahl dieser Koeffizienten ist vom Schlüssel abhängig; sie werden im allgemeinen in den niedrigen Frequenzen des Bildes, d. h. in denjenigen, die sich in der linken unteren Ecke der Blöcke der DCT-Koeffizienten befinden, gewählt. Aus Sicherheitsgründen werden nur zwei Koeffizientenwerte c&sub0; und c&sub1; zufällig ausgewählt, wie Fig. 3 zeigt. Diese Auswahl erfolgt auf die in Fig. 4 gezeigte Weise von einem Zufallsgenerator für die Blockadressen 6, der für jedes Bit bi zwei Koeffizientenadressen (u&sub0; v&sub0;) und (u&sub1; v&sub1;) auswählt. Eine Kartierung der Paare c&sub0; und c&sub1; der ausgewählten DCT-Koeffizienten wird in einem Speicherbereich 7 abgespeichert. Das eigentliche verdeckte Kennzeichnen wird dann ausgeführt, indem die Werte der Koeffizienten c&sub0; und c&sub1; gemäß dem durch die Verarbeitungsschritte 9 bis 19 beschriebenen Verfahren, wobei diese Schritte in dem Ablaufdiagramm von Fig. 5 gezeigt sind, modifiziert werden. Nach diesem Verfahren werden die Absolutwerte der im Schritt 9 berechneten DCT-Koeffizienten jedes Koeffizientenpaares c&sub0;, c&sub1; im Schritt 10 mit einem festgelegten Schwellenwert S verglichen. Wenn das Ergebnis des im Schritt 10 ausgeführten Vergleichs nicht unterhalb der Schwelle S liegt, wird der Koeffizientenblock im Schritt 11 ausgeschlossen, und das Verfahren geht im Schritt 14 zur Analyse des Koeffizientenpaares des nächsten Blocks über. Wenn hingegen im Schritt 10 das Ergebnis des Vergleichs unterhalb der Schwelle S liegt, wird die Phase der Einbettung des Bits bi durch Modifizieren des Wertes der ausgewählten DCT-Koeffizientenpaare ausgeführt. Diese Modifikation wird durch Ausführen der Schritte 12 bis 17b verwirklicht, wobei mittels einer Funktion f jedes Koeffizientenpaar (c&sub0;, c&sub1;) auf eineindeutige Weise in ein neues Paar (c'&sub0;, c'&sub1;) transformiert wird, wobei die Funktion f die Relation c'&sub1; - c'&sub0; ≥ d beachtet. Wenn im Schritt 12 der Wert des einzubettenden Bits bi gleich 0 ist, dann nimmt der Absolutwert des Koeffizienten c&sub1; im Schritt 13a den Absolutwert c'&sub1; an, der erhalten wird, indem zu dem Absolutwert des Koeffizienten c'&sub0; ein bestimmter Zuwachswert d addiert wird. Im gegenteiligen Fall, wenn im Schritt 12 der Wert des einzubettenden Bits bi gleich 1 ist, so wird im Schritt 13b der Wert des anderen Koeffizienten c&sub0; modifiziert, wobei als Absolutwert c'&sub0; derjenige genommen wird, der durch Hinzufügen des Zuwachswertes d zu dem Absolutwert des Koeffizienten c'&sub1; erhalten wird. In den Schritten 15a und '5b werden Tests durchgeführt, um die Vorzeichen der Koeffizienten c'&sub0; und c'&sub1; zu bestimmen. Wenn das Ergebnis eines Tests 15a, 15b positiv ist, so ist das Vorzeichen, das dem Koeffizienten c'&sub0; bzw. c'&sub1; gegeben wird, positiv, hingegen wird im gegenteiligen Fall das Vorzeichen negativ, wie in den Schritten 16a, 16b und 17a, 17b dargestellt ist.
Um zu vermeiden, daß einige Bits bi unbrauchbar sein können, weil sie zu Koeffizientenwerten c&sub0;, c&sub1; führen, für welche der Test des Schritts 10 positiv ist, erfolgt die Wiederholung des Algorithmus über alle Blöcke des Bildes, was beispielsweise für ein Fernsehnormbild, das 576 Zeilen und 720 Spalten pro Halbbild umfaßt, zur Verwendung eines Nachrichtenwortes führt, das die verdeckte Kennzeichnung von 6480 Blöcken ermöglicht.
Beim Empfang erfolgt das Lesen der Nachricht der verdeckten Kennzeichnung, das im Schritt S des Ablaufdiagramms von Fig. 1 ausgeführt wird, in der in den Schritten 18 bis 22 des Ablaufdiagramms von Fig. 6 gezeigten Art und Weise durch Decodieren der Koeffizientenpaare c&sub0;, c&sub1;, die jeweils einem der Bits bi der Nachricht der verdeckten Kennzeichnung entsprechen. Im Schritt 18 wird der Absolutwert der Differenz der Absolutwerte der Koeffizientenpaare c&sub0;, c&sub1; mit dem Schwellenwert S verglichen, der beim Senden während des Einbettens des Bits bi verwendet worden ist. Wenn das Ergebnis des Vergleichs positiv ist, wird der Wert des entsprechenden Bits bi im Schritt 19 als unbestimmt betrachtet, und das Verfahren geht zur Decodierung des Koeffizientenpaares c&sub0;, c&sub1; des dem nächsten eingebetteten Bit bi+1 entsprechenden Koeffizientenblocks über. Wenn hingegen im Schritt 18 das Ergebnis des Tests negativ ist, kann der Wert des Bits bi bestimmt werden, und das Verfahren geht zur Ausführung des Schritts 20 über, der beinhaltet, die Differenz der Absolutwerte der Koeffizienten c&sub0;, c&sub1; mit dem Wert null zu vergleichen, um im Schritt 21 zu ermitteln, ob der Wert des Bits bi null ist, wenn das Ergebnis des Vergleichs im Schritt 20 positiv ist, oder um im Schritt 22 festzustellen, daß der Wert des Bits bi gleich eins ist, wenn das Ergebnis des Vergleichs im Schritt 20 negativ ist.
Das im Schritt 2 des Ablaufdiagramms von Fig. 1 dargestellte Verfahren der begleitenden verdeckten Kennzeichnung ermöglicht, durch Ausführen des Schritts 4 im Hinblick auf die Synchronisierung, beispielsweise für das Lesen einer weiteren verdeckten Kennzeichnung, die Koordinaten des Ursprungs des Ausgangsbildes zu bestimmen, wenn es von einem Empfänger empfangen und abgeschnitten oder verschoben worden ist.
Eine erste Lösung, um in diesem Fall die Ursprungskoordinaten des Bildes wieder aufzufinden, kann darin bestehen, den bekannten "Patchwork"- Algorithmus von William Bender, Daniel Gruhl und Norishige Morimoto zu verwenden, der schon erwähnt worden ist. Es genügt in diesem Fall, alle möglichen Verschiebungen zu untersuchen, die Summe S der Luminanzunterschiede der Punktepaare des Bildes zu berechnen, wobei als Ursprungskoordinaten nur diejenigen behalten werden, für welche die Summe S maximal ist. Dieses Leseverfahren ist jedoch kompliziert und zeitaufwendig.
Das Verfahren der begleitenden verdeckten Kennzeichnung gemäß der Erfindung ermöglicht, insbesondere dieses Verfahren zu vereinfachen, wobei es in effizienter Weise das Problem beseitigt, das bei der Übertragung von Standbildern oder von bewegten Bildern angetroffen wird, die im Ergebnis der beispielsweise durch die MPEG-, JPEG-Codierer oder die Aufzeichnungseinrichtungen eingeführten Bearbeitungen eine Verschiebung erfahren können. Ohne einen Anhaltspunkt für den Ursprung ist das Lesen einer verdeckten Kennzeichnung, die eine Nachricht trägt, nämlich schwierig, wenn nicht gar unmöglich.
Gemäß der Erfindung verwendet das Verfahren der begleitenden verdeckten Kennzeichnung in dem Bild eine binäre Pseudozufallsmatrix P der Größe m x m mit dem Mittelwert null, deren Autokorrelationsfunktion außerhalb des Ursprungs so schwach wie möglich ist. Wie Fig. 7 zeigt, wird diese Matrix durch Symmetrieoperationen aus einer m-Sequenz von Bits erhalten. In dem Beispiel hat das Erzeugerpolynom die Gleichung x&sup4; + x³ + 1; wobei auch andere Formen primitiver Polynome verwendet werden können. Die Matrix P wird benutzt, um ein Bild Ip in der Größe des verdeckt zu kennzeichnenden Bildes I durch periodische Wiederholung dieser auf die in Fig. 8 gezeigte Art und Weise zu erzeugen. Die Luminanzwerte I(i, j) der Bildelemente mit den Koordinaten (i, j) in dem Bild I werden modifiziert, indem auf diese eine Markierungsamplitude d Anwendung findet, die in Abhängigkeit vom Binärzustand "+1" oder "-1" der entsprechenden Bildelemente des Binärbildes Ip entsprechend den folgenden Relationen addiert oder subtrahiert wird:
I'(i, j) = I(i, j) + d, wenn Ip(i, j) = 1 (2)
I'(i, j) = I(i, j) - d, wenn Ip(i, j) = -1 (3)
In den Relationen (2) und (3) kann die Markierungsamplitude bildunabhängig gemacht werden, um die Sichtbarkeit der Kennzeichnung zu verringern.
Beim Empfang erfolgt das Lesen des verdeckt gekennzeichneten Bildes in der in Fig. 9 gezeigten Art und Weise, indem von dem empfangenen, verdeckt gekennzeichneten Bild I' eine Bildmatrix M der Größe m · m entsprechend folgender Relation erzeugt wird:
M(i, j) = I'(km + i, lm + j) (4)
was einem Summieren der Blöcke der Größe N · N des Bildes entspricht.
Es wird dann eine Berechnung der Interkorrelation zwischen der Matrix M und der binären Ursprungsmatrix P über alle möglichen Verschiebungen der Matrix M ausgeführt. Diese Berechnung erfolgt entsprechend der Relation:
S(x, y) = M(i, j)P((i + x) mod m, (j + y)mod m) (5)
mit i < m und j < m, wobei die als Ergebnis der Berechnung erhaltenen Ursprungskoordinaten x&sub0; und y&sub0; diejenigen sind, für welche die Zahl S(x&sub0;, y&sub0;) maximal ist.
Der Algorithmus der begleitenden verdeckten Kennzeichnung ermöglicht, die Ursprungskoordinaten modulo m wiederzugewinnen. Wenn m = N die Größe des Ausgangsbildes ist, liegen selbstverständlich wieder die Bedingungen für den "Patchwork"-Algorithmus des Standes der Technik vor.
Die Ausführung des Schritts 3 der Nachbearbeitung entsprechend dem Ablaufdiagramm von Fig. 1 hat zum Ziel, die Zuverlässigkeit der Daten, die aus der verdeckten Basiskennzeichnung hervorgegangen sind, insbesondere bei Anwendungen der automatischen Überwachung zu überprüfen, wenn die Übertragungsbedingungen schlecht sind, beispielsweise in dem Fall von MPEG-Übertragungen mit sehr niedriger Übertragungsgeschwindigkeit. Der benutzte Algorithmus verwendet die beim Schreiben der verdeckten Kennzeichnung eingeführte Redundanz und liefert mit Hilfe statistischer Kriterien eine Schätzung der Qualität und der Zuverlässigkeit der gelesenen Nachricht. Diese Redundanz nimmt die Form einer Redundanz innerhalb des Bildes oder einer zeitlichen Redundanz an. Die Redundanz innerhalb des Bildes kann im Fall der verdeckten Kennzeichnung von Standbildern und Videobildern ausgewertet werden. Sie beruht auf der Verwendung von Fehlerkorrekturcodes oder von Wiederholungen beim Schreiben der Nachricht. Die zeitliche Redundanz wird erhalten, indem die gleiche Nachricht in jedem Videobild wiederholt wird; sie ermöglicht, die Qualität der gelesenen Nachricht zu schätzen, wobei sie a priori eine Vorstellung von der Verteilung der Bits der gelesenen Nachricht gibt. Wird beispielsweise angenommen, daß ein einziges Bit unter zehnfacher Wiederholung in dem Bild eingebettet ist, so hat die Nachricht, wenn sie fehlerfrei gelesen wird, die Form 1111111111 oder 0000000000. Wenn nach der Übertragung die gelesene Nachricht die Form 0001000000 aufweist, bedeutet dies, daß wenigstens ein Fehler vorliegt und dann mit einem hinreichend großen Vertrauen angenommen werden kann, daß das Bit 0 gesendet worden ist. Wenn hingegen die gelesene Nachricht die Form 0111010011 aufweist, dann könnte aufgrund der Tatsache, daß sechs Bits im Zustand 1 und vier Bits im Zustand 0 sind, geschlußfolgert werden, daß das Bit 1 gesendet worden ist. Da jedoch in diesem letzteren Fall das Vertrauen in dieses Ergebnis schwächer erscheint, ist es vernünftiger, diese Schlußfolgerung nicht zu ziehen.
Eine Umsetzung dieses Algorithmus ist in dem Ablaufdiagramm von Fig. 10 veranschaulicht. In diesem Ablaufdiagramm bezeichnet S0i die Häufigkeit, mit der ein Bit bi vom Rang i der Nachricht mit dem Wert 0 gelesen worden ist, und S1i bezeichnet die Häufigkeit, mit der das gleiche Bit mit dem Wert 1 gelesen worden ist. Im Schritt 23 wird ein erster Test durchgeführt, um die Häufigkeiten S0i und S1i zu vergleichen. Wenn die Häufigkeit S0i kleiner als die Häufigkeit S1i ist, dann wird im Schritt 24 entschieden, daß es S0i Übertragungsfehler gegeben hat und daß das gesendete Bit wahrscheinlich den Wert 1 hatte; hingegen wird, wenn im gegenteiligen Fall die Häufigkeit S0i größer als die Häufigkeit S1i ist, im Schritt 25 entschieden, daß es S1i Übertragungsfehler gegeben hat und daß das gesendete Bit bi wahrscheinlich den Wert 0 hatte. Der Vertrauensgrad, der diesen Ergebnissen entgegenzubringen ist, wird dann im folgenden Schritt 27 durch einen Binomialtest dieser bestimmt, der nach dem Gesetz der binomischen Wahrscheinlichkeit von Bernouilli modelliert ist. Wenn die Qualität des Test ausreichend erscheint, wird das Bit bi im Schritt 27 für gültig erklärt, andernfalls wird es im Schritt 28 für nicht gültig erklärt. Nach Abschluß der Schritte 27 und 28 geht das System zum Test des folgenden Bits bi+1 der empfangenen Nachricht über.

Claims

1. Verfahren zum verdeckten Kennzeichnen von Bildern für die Verarbeitung und die Übertragung von Stand- oder Videobildern des Typs, der darin besteht, in die Bilder vor ihrer Übertragung durch Modifikation der charakteristischen Daten der Bilder eine Nachricht einzubetten, dadurch gekennzeichnet, daß es darin besteht, durch periodische Einbettung einer binären Matrix P in das Bild eine begleitende verdeckte Kennzeichnung (2) vorzunehmen, um beim Empfang die Koordinaten des Ursprungs des Ausgangsbildes zu bestimmen und die Justierung der empfangenen Bilder in bezug auf diesen Ursprung zu ermöglichen, um das Lesen der eingebetteten Nachricht zu ermöglichen.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die binäre Matrix für die begleitende verdeckte Kennzeichnung eine Pseudozufallsmatrix P mit Größe m · m ist, die durch Symmetrie aus einer binären m-Sequenz erhalten wird.

3. Verfahren nach einem der Ansprüche 1 und 2, dadurch gekennzeichnet, daß es darin besteht, ein Bild Ip mit der Größe des verdeckt gekennzeichneten Bildes durch periodische Wiederholung der Pseudozufallsmatrix P herzustellen und die Luminanzwerte I(i,j) von Bildelementen mit Bildkoordinaten (i,j), die zu jenen des durch periodische Wiederholung der Matrix für die begleitende verdeckte Kennzeichnung erhaltenen Bildes homolog sind, durch eine Markierungsamplitude, die für jedes Bildelement vom Wert des homologen Bildelements in dem durch periodische Wiederholung der Matrix für die verdeckte Kennzeichnung erhaltenen Bild abhängt, zu modifizieren.

4. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß es darin besteht, beim Empfang die Koordinaten des Ursprungs des Ausgangsbildes zu bestimmen, das empfangene Bild in Blöcke zu zerlegen, die Blöcke zu summieren, um eine Matrix M mit Größe m · m zu bilden, eine Korrelation zwischen der Matrix M und der binären Matrix P für die begleitende verdeckte Kennzeichnung durch sukzessive Verschiebungen der Matrix M in bezug auf die Matrix P herzustellen und als Koordinaten des Ursprungs diejenigen Koordinaten zu verwenden, für die das Korrelationsprodukt maximal ist.

5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß es darin besteht für eine verdeckte Kennzeichnung (1) eine Transformation des Bildes in Blöcke aus DCT-Koeffizienten vorzunehmen, in das Bild eine Nachricht einzubetten, indem die DCT-Koeffizienten (9, ... 22) moduliert werden, um eine adaptive Markierung vorzunehmen, um eine Unerkennbarkeit der eingebetteten Nachricht bei der Wiederherstellung des Bildes zu erzielen, und die Nachricht gegenüber Verschlechterungen durch Verwendung einer Redundanz robust zu machen.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß es darin besteht, jedem Bit bi der einzubettenden Nachricht zwei Koeffizienten eines Blocks aus DCT-Koeffizienten zuzuordnen und die Werte der beiden ausgewählten Koeffizienten in Abhängigkeit vom binären Wert des Bits der einzubettenden Nachricht zu modifizieren (10, ..., 17).

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß es darin besteht, für die Ausführung der verdeckten Kennzeichnung die Differenz der Absolutwerte der gewählten Paare von Koeffizienten in jedem Block mit einem bestimmten Schwellenwert S zu vergleichen (10), um den Absolutwert eines von beiden in Abhängigkeit vom binären Zustand des Bits der einzubettenden Nachricht zu modifizieren (13, ..., 17), wenn das Ergebnis des Vergleichs kleiner als der bestimmte Schwellenwert S ist.

8. Verfahren nach einem der Ansprüche 5 bis 7, dadurch gekennzeichnet, daß es darin besteht zum Lesen der verdeckten Kennzeichnung eines Videobildes die Paare von DCT-Koeffizienten, die den Bits der eingebetteten Nachricht entsprechen, zu decodieren, indem der Absolutwert der Differenz der Absolutwerte der Koeffizientenpaare mit dem bestimmten Schwellenwert S verglichen wird, die Differenz der Absolutwerte der Paare von Koeffizienten mit dem Wert null zu vergleichen (20), um den binären Zustand der entsprechenden eingebetteten Bits zu bestimmen, wenn das Ergebnis des Vergleichs kleiner als der Schwellenwert S ist, oder den binären Zustand der eingebetteten Bits als unbestimmt zu erklären (19), wenn das Ergebnis des Vergleichs größer als der Schwellenwert S ist.

9. Verfahren nach einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, daß es darin besteht, eine verdeckte Kennzeichnung an allen Punkten des Bildes vorzunehmen.

10. Verfahren nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, daß es darin besteht, an den empfangenen Bildern eine Nachverarbeitung (3; 23, ..., 28) vorzunehmen, um die Qualität und die Zuverlässigkeit der eingebetteten Nachricht zu schätzen, indem die Redundanz der eingebetteten Nachricht ausgenutzt wird.

11. Verfahren nach Anspruch 10, dadurch gekennzeichnet, daß es darin besteht, die verdeckte Kennzeichnungsnachricht in jedem Videobild in einer bestimmten Anzahl zu wiederholen, indem (2, 3) für jedes Bit der verdeckten Kennzeichnungsnachricht die Anzahl, in der es in einem ersten Zustand empfangen wird, mit der Anzahl verglichen wird, in der es in einem zweiten Zustand empfangen wird, und die so erhaltenen aufsummierten Werte mit einem Schwellenwert, der durch das Gesetz der binomischen Wahrscheinlichkeit von Bernouilli bestimmt ist, zu vergleichen (26).