Intelligent watermarking of long streams of document images

Vellasques, Eduardo (2013). Intelligent watermarking of long streams of document images. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (2MB) | Prévisualisation
Prévisualisation	PDF Télécharger (2MB) | Prévisualisation

Résumé

Digital watermarking has numerous applications in the imaging domain, including (but not limited to) fingerprinting, authentication, tampering detection. Because of the trade-off between watermark robustness and image quality, the heuristic parameters associated with digital watermarking systems need to be optimized. A common strategy to tackle this optimization problem formulation of digital watermarking, known as intelligent watermarking (IW), is to employ evolutionary computing (EC) to optimize these parameters for each image, with a computational cost that is infeasible for practical applications. However, in industrial applications involving streams of document images, one can expect instances of problems to reappear over time. Therefore, computational cost can be saved by preserving the knowledge of previous optimization problems in a separate archive (memory) and employing that memory to speedup or even replace optimization for future similar problems.

That is the basic principle behind the research presented in this thesis. Although similarity in the image space can lead to similarity in the problem space, there is no guarantee of that and for this reason, knowledge about the image space should not be employed whatsoever. Therefore, in this research, strategies to appropriately represent, compare, store and sample from problem instances are investigated. The objective behind these strategies is to allow for a comprehensive representation of a stream of optimization problems in a way to avoid re-optimization whenever a previously seen problem provides solutions as good as those that would be obtained by reoptimization, but at a fraction of its cost. Another objective is to provide IW systems with a predictive capability which allows replacing costly fitness evaluations with cheaper regression models whenever re-optimization cannot be avoided.

To this end, IW of streams of document images is first formulated as the problem of optimizing a stream of recurring problems and a Dynamic Particle Swarm Optimization (DPSO) technique is proposed to tackle this problem. This technique is based on a two-tiered memory of static solutions. Memory solutions are re-evaluated for every new image and then, the re-evaluated fitness distribution is compared with stored fitness distribution as a mean of measuring the similarity between both problem instances (change detection). In simulations involving homogeneous streams of bi-tonal document images, the proposed approach resulted in a decrease of 95% in computational burden with little impact in watermarking performace. Optimization cost was severely decreased by replacing re-optimizations with recall to previously seen solutions.

After that, the problem of representing the stream of optimization problems in a compact manner is addressed. With that, new optimization concepts can be incorporated into previously learned concepts in an incremental fashion. The proposed strategy to tackle this problem is based on Gaussian Mixture Models (GMM) representation, trained with parameter and fitness data of all intermediate (candidate) solutions of a given problem instance. GMM sampling replaces selection of individual memory solutions during change detection. Simulation results demonstrate that such memory of GMMs is more adaptive and can thus, better tackle the optimization of embedding parameters for heterogeneous streams of document images when compared to the approach based on memory of static solutions.

Finally, the knowledge provided by the memory of GMMs is employed as a manner of decreasing the computational cost of re-optimization. To this end, GMM is employed in regression mode during re-optimization, replacing part of the costly fitness evaluations in a strategy known as surrogate-based optimization. Optimization is split in two levels, where the first one relies primarily on regression while the second one relies primarily on exact fitness values and provide a safeguard to the whole system. Simulation results demonstrate that the use of surrogates allows for better adaptation in situations involving significant variations in problem representation as when the set of attacks employed in the fitness function changes.

In general lines, the intelligent watermarking system proposed in this thesis is well adapted for the optimization of streams of recurring optimization problems. The quality of the resulting solutions for both, homogeneous and heterogeneous image streams is comparable to that obtained through full optimization but for a fraction of its computational cost. More specifically, the number of fitness evaluations is 97% smaller than that of full optimization for homogeneous streams and 95% for highly heterogeneous streams of document images. The proposed method is general and can be easily adapted to other applications involving streams of recurring problems.

Titre traduit

Tatouage intelligent de quantités massives de documents numérisés

Résumé traduit

Le tatouage des images de documents sert plusieurs applications telles que l’authentification et la détection de documents numériques falsifiés. L’insertion d’un marqueur nécessite l’ajustement de plusieurs paramètres qui sont dépendants du contenu de chaque image. Le choix de la meilleure solution résulte du compromis à faire entre la qualité de l’image tatouée et la robustesse aux attaques du processus de marquage. Les systèmes de tatouage basés sur les algorithmes d’optimisation évolutionnaires sont appelés systèmes de tatouage intelligents (IW – IntelligentWatermarking). Le principal désavantage de ces systèmes est le coût computationnel prohibitif pour une utilisation grande échelle. L’approche adoptée dans cette thèse est de considérer une quantité massive de documents numériques à tatouer comme un flux de problèmes d’optimisation récurrents à traiter. Le système proposé est basé sur le concept de mémoire, qui permet de conserver une représentation des problèmes d’optimisation qui ont déjà été résolus afin de trouver rapidement une bonne solution pour une nouvelle image à tatouer.

L’approche adoptée dans cette thèse consiste à formuler le processus de tatouage d’un flux d’images de documents comme une séquence de problèmes d’optimisation récurrents. L’objectif principal de cette thèse est de concevoir un système de tatouage intelligent, doté de la capacité d’apprendre incrémentalement dans le temps les caractéristiques des problèmes d’optimisation à traiter. L’utilisation de la connaissance acquise dans le temps permettra de choisir une solution satisfaisante sans recourir systématiquement au processus d’optimisation qui est très coûteux en temps de calcul.

Pour être en mesure d’atteindre cet objectif, nous avons étudié plusieurs types de représentation en mémoire afin de traiter efficacement une quantité importante de documents à tatouer, tout en minimisant le coût computationnel. Pour ce faire, les stratégies proposées permettent de regrouper les problèmes d’optimisation de même nature en classes dans l’espace des paramètres. Un mécanisme de détection de changement permet alors de trouver rapidement en mémoire une bonne solution sans recourir au processus coûteux de l’optimisation des paramètres effectué sans connaissance a priori du problème à résoudre.

Dans un premier temps, le processus de tatouage d’un flux de documents numériques a été formulé comme une séquence de problèmes d’optimisation récurrents. Une nouvelle méthode basée sur le DPSO (Dynamic Particle Swarm Optimization) permet de résoudre efficacement ce type de problèmes d’optimisation récurrents. La technique proposée repose sur une mémoire associative qui est composée de plusieurs classes de solutions obtenues sur les images déjà traitées. Un mécanisme de détection de changement basé sur la distribution des valeurs de fitness des solutions en mémoire permet de vérifier rapidement si le problème d’optimisation en cours a déjà été résolu. Dans l’affirmative, alors une bonne solution est trouvée avec une fraction du coût computationnel requis pour une optimisation complète. Sinon, le processus d’optimisation est activé et la mémoire associative est mise à jour afin de tenir compte de cette nouvelle information. La performance du système proposé évaluée sur une base d’images binaires homogène permet de diminuer de 95% le coût computationnel tout en conservant la même qualité de solutions obtenues par le processus d’optimisation activé sur chaque image à tatouer.

Dans un deuxième temps, le problème du choix d’une représentation mémoire plus compact a été adressé. Cette fois les solutions individuelles sont remplacées par une représentation basée sur une modélisation de l’espace des paramètres. Les mixtures de gaussiennes (GMM – Gaussian Mixture Models) sont ajustées à partir de toutes les solutions évaluées par le PSO en cours d’évolution. Les GMMs sont très efficaces pour représenter les classes de problèmes d’optimisation de même nature. La mise en oeuvre des mécanismes de gestion de la mémoire à long terme est simple, efficace, et consomme très peu de mémoire. Cette fois le mécanisme de détection de changement repose sur un échantillonnage de l’espace des paramètres du problème en cours de traitement et sur une mesure de similarité entre la distribution des fitness mesurées et celles mémorisées par la modélisation GMM pour chaque classe. Les résultats de simulation montrent que cette approche est plus flexible que celle basée sur les solutions individuelles conservées en mémoire. De plus, la performance obtenue sur des images de documents hétérogènes est nettement améliorée comparée à la méthode basée sur les solutions individuelles.

Finalement, la version complète du système proposé intègre à la modélisation GMM un mécanisme de régression afin de diminuer le coût computationnel requis lorsque le système de tatouage intelligent ne trouve pas une solution adéquate en mémoire, et qu’il doit obligatoirement activer le processus d’optimisation PSO. La stratégie consiste à remplacer l’évaluation coûteuse de la fitness par une estimation basée sur la modélisation GMM. Ce type d’approche est appelée surrogate-based optimization dans la littérature. La méthode proposée repose sur deux niveaux de prédiction ce qui permet dans le pire des cas de trouver une bonne solution même si la modélisation du problème d’optimisation est imprécise. L’impact de ce mécanisme de prédiction sur le coût computationnel requis pour l’optimisation des paramètres de l’algorithme de tatouage est significatif et celui-ci permet une diminution globale du coût computationnel sur des images hétérogènes.

En résumé, le système de tatouage intelligent proposé dans cette thèse est bien adapté pour l’optimisation d’un flux de problèmes d’optimisation récurrents. La qualité des solutions obtenues sur des bases d’images de documents homogènes et hétérogènes est équivalente à l’optimisation systématique sur chaque image avec PSO. En plus, le coût computationnel est réduit en moyenne de 97% sur des images homogènes et de 95% sur des images fortement hétérogènes. La méthode proposée est générale et peut être adaptée facilement pour l’optimisation de problèmes d’optimisation récurrents.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy" Bibliogr. : f. [211]-220.
Mots-clés libres:	Tatouage numérique. Optimisation mathématique. Rupture (Statistique). bitonal, détection de changement, dynamique, essaim, évolutionnaire, gaussien, image, intelligent, iw, mélange, particule, régression, tatouage.
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Sabourin, Robert
Codirecteur:	Codirecteur Granger, Éric
Programme:	Doctorat en génie > Génie
Date de dépôt:	18 févr. 2013 17:24
Dernière modification:	10 mars 2017 22:26
URI:	https://espace.etsmtl.ca/id/eprint/1131

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt