Consider a piece of information printed on paper and scanned in the form of an image. The printer, scanner, and the paper naturally form a communication channel, where the printer is equivalent to the sender, scanner is equivalent to the receiver, and the paper is the medium of communication. The channel created in this way is quite complicated and it maps 2D input patterns to 2D output patterns. Inter-symbol interference is introduced in the channel as a result of printing and scanning. During printing, ink from the neighboring pixels can spread out. The scanning process can introduce interference in the data obtained because of the finite size of each pixel and the fact that the scanner doesn't have infinite resolution. Other degradations in the process can be modeled as noise in the system. The scanner may also introduce some spherical aberration due to the lensing effect. Finally, when the image is scanned, it might not be aligned exactly below the scanner, which may lead to rotation and translation of the image. In this work, we present a coding scheme for the channel, and possible solutions for a few of the distortions stated above. Our solution consists of the structure, encoding and decoding scheme for the code, a scheme to undo the rotational distortion, and an equalization method. The motivation behind this is the question: What is the information capacity of paper. The purpose is to find out how much data can be printed out and retrieved successfully. Of course, this question has potential practical impact on the design of 2D bar codes, which is why encodability is a desired feature. There are also a number of other useful applications however. We could successfully decode 41.435 kB of data printed on a paper of size 6.7 X 6.7 inches using a Xerox Phasor 550 printer and a Canon CanoScan LiDE200 scanner. As described in the last chapter, the capacity of the paper using this channel is clearly greater than 0.9230 kB per square inch. The main contribution of the thesis lies in constructing the entire system and testing its performance. Since the focus is on encodable and practically implementable schemes, the proposed encoding method is compared with another well known and easily encodable code, namely the repeat accumulate code.

En raison du développement et de la disponibilité des appareils d'impression et de numérisation, le nombre de documents contrefaits augmente rapidement. En effet, les documents de valeur ainsi que les emballages de produits sont de plus en plus ciblés par des duplications non autorisées. Par conséquent, différents éléments de sécurité (hologrammes, encres, papiers) ont été proposés pour prévenir ces actions illégales. Dans cette thèse, nous nous concentrons sur les éléments de sécurité imprimés qui offrent un haut niveau de sécurité et qui possèdent une mise en œuvre et une intégration simple. Nous présentons comment générer de nouveaux éléments de sécurité qui visent à protéger les documents de valeur et les emballages contre des processus de duplication non autorisés. Ces éléments nous permettent en outre de stocker une grande quantité d'informations cachées.La caractéristique principale de ces éléments de sécurité est leur sensibilité au processus d'impression et de numérisation. Cette sensibilité est obtenue à l'aide de motifs texturés spécifiques. Ces motifs sont des images binaires qui possèdent une structure sensible aux processus d'impression, de numérisation et de copie. Nous définissons les critères spécifiques qui doivent être respectés lors du choix de ces motifs texturés. La quantité d'information encodée dans l'image augmente avec le nombre de motifs texturés utilisées.En complément, nous proposons dans ce mémoire d'améliorer la robustesse de la détection des modules, pour tous les codes graphiques, par l'utilisation d'une nouvelle mesure d'erreur quadratique moyenne pondérée. L'utilisation de cette nouvelle mesure nous a permis d'augmenter de façon significative le taux de reconnaissance des modules lorsqu'ils sont utilisés dans des codes à barres standard à haute densité. Enfin, nous étudions expérimentalement plusieurs phénomènes : le processus physique d'impression et de numérisation, la séparation du bruit du scanner de celui de l'imprimante et les changements de couleurs après processus d'impression et de numérisation. Nous concluons à partir de cette étude expérimentale, que le processus d'impression et de numérisation ne peut pas être modélisé comme un loi Gaussienne. Nous mettons en avant que ce processus n'est ni blanc ni ergodique au sens large. / Due to the development and availability of printing and scanning devices, the number of forged/counterfeited valuable documents and product packages is increasing. Therefore, different security elements (holograms, inks, papers) have been suggested to prevent these illegal actions. In this thesis, we focus on printed security elements that give access to a high security level with an easy implementation and integration. We present how to generate several novel security elements that aim to protect valuable documents and packaging against unauthorized copying process. Moreover, these security elements allow us to store a huge amount of hidden information.The main characteristic of these security elements is their sensitivity to the print-and-scan process. This sensitivity stems from the use of specific textured patterns. These patterns, which are binary images, have a structure that changes during the printing, scanning and copying processes. We define new specific criteria that ensures the chosen textured patterns to have the appropriate property. The amount of additional information encoded in the patterns increases with the number of patterns used.Additionally, we propose a new weighted mean squared error measure to improve the robustness of module detection for any high density barcodes. Thanks to this measure, the recognition rate of modules used in standard high density barcodes after print-and-scan process can be significantly increased. Finally, we experimentally study several effects: the physical print-and-scan process, separation of scanner noise from printer noise and changes of colors after print-and-scan process. We conclude, from these experimental results, that the print-and-scan process cannot be considered as being a Gaussian process. It has been also highlighted that this process is neither white nor ergodic in the wide sense.

Un nombre incalculable de documents est imprimé, numérisé, faxé, photographié chaque jour. Ces documents sont hybrides : ils existent sous forme papier et numérique. De plus les documents numériques peuvent être consultés et modifiés simultanément dans de nombreux endroits. Avec la disponibilité des logiciels d’édition d’image, il est devenu très facile de modifier ou de falsifier un document. Cela crée un besoin croissant pour un système d’authentification capable de traiter ces documents hybrides. Les solutions actuelles reposent sur des processus d’authentification séparés pour les documents papiers et numériques. D’autres solutions reposent sur une vérification visuelle et offrent seulement une sécurité partielle. Dans d’autres cas elles nécessitent que les documents sensibles soient stockés à l’extérieur des locaux de l’entreprise et un accès au réseau au moment de la vérification. Afin de surmonter tous ces problèmes, nous proposons de créer un algorithme de hachage sémantique pour les images de documents. Cet algorithme de hachage devrait fournir une signature compacte pour toutes les informations visuellement significatives contenues dans le document. Ce condensé permettra la création de systèmes de sécurité hybrides pour sécuriser tout le document. Ceci peut être réalisé grâce à des algorithmes d’analyse du document. Cependant ceux-ci ont besoin d’être porté à un niveau de performance sans précédent, en particulier leur fiabilité qui dépend de leur stabilité. Après avoir défini le contexte de l’étude et ce qu’est un algorithme stable, nous nous sommes attachés à produire des algorithmes stables pour la description de la mise en page, la segmentation d’un document, la reconnaissance de caractères et la description des zones graphiques. / An innumerable number of documents is being printed, scanned, faxed, photographed every day. These documents are hybrid : they exist as both hard copies and digital copies. Moreover their digital copies can be viewed and modified simultaneously in many places. With the availability of image modification software, it has become very easy to modify or forge a document. This creates a rising need for an authentication scheme capable of handling these hybrid documents. Current solutions rely on separate authentication schemes for paper and digital documents. Other solutions rely on manual visual verification and offer only partial security or require that sensitive documents be stored outside the company’s premises and a network access at the verification time. In order to overcome all these issues we propose to create a semantic hashing algorithm for document images. This hashing algorithm should provide a compact digest for all the visually significant information contained in the document. This digest will allow current hybrid security systems to secure all the document. This can be achieved thanks to document analysis algorithms. However those need to be brought to an unprecedented level of performance, in particular for their reliability which depends on their stability. After defining the context of this study and what is a stable algorithm, we focused on producing stable algorithms for layout description, document segmentation, character recognition and describing the graphical parts of a document.