Artur Simões Rozestraten
email: artur.rozestraten@usp.br

Vânia Mara

Alves Lima

Cibele De Araújo
email: cibeleac@usp.br

Camargo Marques

Dos Santos

ARQUIGRAFIA: digital images in a Web collaborative environment

Keywords: Digital heritage, Architectural images, Image databases, Collaborative environment, Web apps

seven years a multidisciplinary research team of the University of São Paulo (USP) with the support of São Paulo Research Foundation -FAPESP (2012/24409-2) has been dedicated to designing a collaborative environment of architectural images on the Web. This collaborative environment denominated ARQUIGRAFIA allows institutional userssuch as GLAMs (Galleries, Libraries, Archives and Museums), NGOs, Universities and Research Centersto collaborate with private userssuch as students, teachers, photographers and amateursin order to build an open, public and free web digital iconographic collaborative environment on Brazilian architectures and urban spaces. The ARQUIGRAFIA research team has been analyzing the digital repository and the website databases; undertaking analyticalcritical studies of the indexing languages for Brazilian architecture images as well as of the tags proposed by the users; raising problems for the metadata accordance between systems; as well as consolidating standards which respond both to international interoperability requirements and to local needs for organization and information access. On the website or on the Android App, users can create an account and share their visual collections (photographs, drawings and videos) by uploading files, as well as indexing, geo referencing and licensing images (Creative Commons). Meanwhile, all users can organize albums, post comments and download high-resolution images with metadata. Institutional users can also ask for an institutional login that allows them to have a collective identity online with a particular name and avatar. Those users can choose, whenever they log in, if they will log as a private user or part of an institutional team. Nowadays, the main images of ARQUIGRAFIA come from the collection of the library of School of Architecture and Urbanism of the University of Sao Paulo (FAUUSP). On a technological perspective, ARQUIGRAFIA plays the role of a pilot program for a template called +GRAFIA that can offer free help for other areas of knowledge to build their own visual collaborative environments, such as a BOTANYGRAFIA dedicated to the flora, or an ARTGRAFIA, dedicated to visual arts. Conceptual and technological challenges concerning the design and the operation of ARQUIGRAFIA allows us to characterize it as an online experimental laboratory and a case study on the opportunities and the risks of digital projects on humanities based on

Introduction

ARQUIGRAFIA (http://www.arquigrafia.org.br) is an open, public and nonprofit, continuous growth collaborative environment on the Web dedicated to visual culture and critical approaches to architectural images, with a special focus on Brazilian architecture and urban spaces. The main goal of this project is to gather institutions and private users in the same internet environment, dedicated to the collaboration for the research, study and collective knowledge building on Architecture and Urbanism in Brazil and along with the Portuguese speaking communities around the world.

So far, ARQUIGRAFIA's main source of images has been the collection of the library of the School of Architecture and Urbanism of the University of Sao Paulo (FAUUSP), but the collaborative nature of the project distinguishes it from institutional image databases on the internet, precisely because it involves a heterogeneous network of collaborators, both institutional and private, who jointly contribute to the construction and continuous growth of the digital images collection.

Such nature presents several desirable characteristics for the constitution of what Tim O'Reilly (2007) calls Web 2.0, based on parameters developed by Christopher [START_REF] Alexander | A pattern language: towns, buildings, construction[END_REF]. Among these parameters, ARQUIGRAFIA emphasizes the experimental meaning of an active and collaborative participation of all users in the continuous construction of the system as an "image constellation" and also as a perpetual beta software, constituting a Web community that constructs knowledge collectively, respecting copyright, and using distinct and complementary interfaces such as a website and an Android application for smartphones.

On the Web 2.0 context, as a thematic environment dedicated to Architecture and Urbanism, ARQUIGRAFIA is one of the rare current systems with free login, free upload and download, which still allows its users to tag, georeference and assign specific license (Creative Commons) to every image from their collections.

All these characteristics are relevant when comparing ARQUIGRAFIA to other digital images databases that still operate fundamentally as Web 1.0, namely: Built Works Register (http://builtworksregistry.org); Artstor (http://www.artstor.org); GettyImages (http://www.gettyimages.com.br)

The multidisciplinary challenges of the ARQUIGRAFIAproject led to the creation of the Web Collaborative Environments Research Center (NaWeb) bringing together researchers from the School of Architecture and Urbanism of the University of São Paulo (FAU/USP), in partnership with the Institute of Mathematics and Statistics (IME/USP) and the School of de Communications and Arts (ECA/USP).

The NaWeb research group investigates aspects related to representation and architectural imagination, conservation and digitization of photographic collections, and issues related to the development of free software, dynamic social networking, as well as topics relevant to information science and ontologies.

Actually, NaWeb is a partner of the INCT (National Institute of Science and Technology) of the Future Internet for Smart Cities.

Since 2012 the ARQUIGRAFIA project has been developed by NaWeb in close cooperation with the Iconographic Material Sector of the Library of the School of Architecture and Urbanism (FAU), and this collaborative e-work is based on 3 viewpoints: the architectural critical perspectives, the library and information science and the computer science and web design approaches.

Under the architectural critical perspectives, the ARQUIGRAFIA contributes to expand and popularize the debate on architecture, cultural heritage and documentation, thus stimulating critical judgment over the iconographic representation of the Brazilian architectural and urban production. Doing so, the project proposes a public debate on the nature of collective knowledge building supported by images, related to time (present, past and future) and space (georeferenced images), that can be integrated in a real urban experience with the support of smartphones and Apps. In order to encourage users to closely observe every image and formulate esthetic judgments about buildings and urban spaces represented in photographs, ARQUIGRAFIA proposes the registration of individual impressions based on pairs of opposing qualities organized as semantic differentials such as: open/closed; internal/external; translucent/opaque; complex/simple; symmetrical/asymmetrical; horizontal/vertical.

The approach under the point of view of the Library and Information Science makes possible a closer look at some of its contemporary issues, specifically regarding the representation of images (Dell Valle Gastaminza, 1999;[START_REF] Gonzalez | O conteúdo da imagem[END_REF][START_REF] Smit | A representação da imagem. Informare: Cadernos do Programa de Pós-Graduação[END_REF], controlled vocabularies and user's participation. Here, we have discussed the knowledge organization in the Brazilian architectural domain, by analyzing the digital repository, the website databases and the analyticalcritical studies of the indexing languages and the tags proposed by the users; as well as the consolidation of the standards, which respond both to international interoperability requirements and to local needs for organization and information access.

The Computer Science allowed ARQUIGRAFIA to develop its own software based on PHP Laravel, which can be freely shared as a +GRAFIA template to support other similar initiatives for building georeferenced iconographic collaborative environments on the Internet. Since 2015 the research team has been working on an Android App now available for free download in Brazil at the Google Play Store. Since the first ARQUIGRAFIA Web version in 2010, the project has assumed its beta perpetual nature, and has defined an User-Centered Design (UCD) methodological process that still runs the web design development. At the moment ARQUIGRAFIA faces challenges related to the sustainability of a continuous growth system and explores the collaborative resources that a social network can provide such as moderators.

Methodology

The institutional images inserted in ARQUIGRAFIA weretaken from the FAUUSP Library photographic collection started back in the late 1960's with the systematic donation of students and professors' private images, aiming to build an 'Imaginary Museum' like proposed by André Malraux in 1947, on Architecture, Urbanism and Design. In order to guarantee the preservation, organization, representation, scanning and retrieval of information from the collection,it was made available on the web by the ARQUIGRAFIA team, which has promoted at a much larger scale the convergence of private and public collections, and also the continuous expansion of the collection, thanks to the web contribution of photographers, students, teachers, researchers, and people interested in architecture. Furthermore, the images register improves public based full access to stimulate the construction of an architectural visual culture. This work front involves the processesof management, organization and preservation of information, taking into account the interdisciplinary practices within the project. Some of the subjects covered in each stage were the physical photography material processing, the slide or negative scanning; the adequacy of metadata and digital resources formats and the logical treatment system for modeling data collection [START_REF] Cunha | Preservação digital o estado da arte[END_REF]International Federation of Library Associations and Institutions, 1987). Besides that, it was necessary to develop the ARQUIGRAFIA controlled vocabulary, which must include the architecture terminology, the user's natural language and the institutional indexing language [START_REF] Austin | Diretrizes para a elaboração de tesauros monolíngues[END_REF]International Standard Organization, 2000;[START_REF]ISO 704: Terminology work -principles and methods[END_REF][START_REF]Information and documentation: thesauri and interoperability with other vocabularies , part 1 Thesauri for information retrieval[END_REF][START_REF] Royan | Directrizes para materiais audiovisuais e multimedia em bibliotecas e outras instituições[END_REF]Cabre, 1995). A survey of user's new terms descriptors was undertaken and studies about the adequacy of the design content representation for computational ontologies and informationsystem-based knowledge were developed. Finally, the project has implemented the infrastructure and repositories; the archiving and backup policies; the data management policies and information retrieval.

To enable a better understanding of the collection features in quantitative and qualitative terms, for a more precise identification of treatment needs, control of costs and work schedule, a diagnosis has been made, considering a critical analysis of the amount of photographic documents, the type of media used, the format (single photograph, slide), chromia and standard dimensions of the photographic documents. We have made the identification of the principal problems for conservation such as abrasion, discoloration, deforming, wrinkling, mirroring, evidence of fungi and stains. The cleaning of the 42,000 images of the institutional collection was done mechanically with air sprayer and a non-abrasive tissue. The use of solvents was necessary only in a few slides stained or damaged by fungi [START_REF] Braga | Conservação preventiva: acondicionamento e armazenamento de acervos complexos em reserva técnica: o caso do MAE/USP[END_REF].

After the cleaning,a selection of relevant documents for the ARQUIGRAFIA has been made. We have selected 34,000 original slides, 8,000 images on paper, including color and black-and-white photographs on Brazilian buildings and urban spaces, the majority of them being unpublished. About 6,724 images from the library collection have already been catalogued and are already online. In addition to that, the ARQUIGRAFIA has 2,660 images from private users and 1,765 images from other institutional collections totalizing 11,149 images online.

The public profile of ARQUIGRAFIA included architecture students (38.6%); architects (23.4%); graduate students in other areas (10.3%); architecture professors (4.3%); photographers (4.1%). Most users are between 20 and 30 years old, have an undergraduate degree or attend the graduation courses.

Since 2013, the scanning has been made by an outsourced company using a Plustek Optic film 120 and a scanning software, SilverFast Ai Studio 8 (64-bit), which helps in the removal of dust and scratches. The generated files are about 5 MB to 4,000 dpi in TIFF, JPEG and PDF, recorded on DVDs and external hard drives. No computation colors correctionis made in the scanned images, in order to preserve the original appearance of the photographs. Thus, the marks of time (color changes, spots, saturation, etc) are respected and maintained, aiming to maintain the collection with its historical aspects.

Every single image is identified by a registration number, which enables the crosschecking and comparison between spreadsheet data and images. During the read out, each spreadsheet row is transformed into business objects used by the system. To do this transformation, The Apache ODF Toolkit (http://incubator.apache.org/odftoolkit) is used in order to offer a communication interface between the spreadsheet and the system for information mining and transformation. Then, the information storage activity lies in creating associations between the business objects and their storage in database. Once the object association is done (an author is associated to an image and this image to an address) the system uses the persistence library Hibernate (http://www.hibernate.org) to store database under Mysql (http://www.mysql.com).

It was necessary to clarify the procedures for the representation and retrieval of digital heritage, which is being made in order to ensure access to and sharing of information between all users, whether institutional or individual. We have analyzed the cataloguing standards (AACR; ISBD(NBM); CCO; CDWA), and developed a spreadsheet to integrate the required fields for the data administration in virtual environment. Then we established the set of metadata with the following elements:

• Description: Title, Classification number, Name, Country, State, City, District, Street, Image author, Picture date, Building author, Building date, Notes, Registration number date, Cataloguing date.

• Technical: Dimensions, Width, Height, Resolution, Bit depth, Color representation.

•Administrative: License (Creative Commons), Collection, Donors, Authorization term for web broadcasting.

Bearing in mind that at the ARQUIGRAFIA both personal and institutional users can insert images of collections of photos, it was necessary to do some terminology standardization work between the lists of subjects used by the library for the indexing of photographs and slides; the Controlled Vocabulary of the Integrated Library System of the University of Sao Paulo (VOCAUSP), and the list of tags developed by the team, based on dictionaries and thesauri of architecture. This terminology standardization has resulted in a list of terms used for the indexing of images, which was enriched with tags assigned by private users to their images. A survey was conducted on the keywords employed by the users in order to collect new terms that can be added to the controlled vocabulary.

Users must fill in at least the title and author of the image, country and tags to upload an image to ARQUIGRAFIA, a procedure that can be performed on the website or the App. The system suggests terms selected from the list, but the users can insert new tags in natural language. This inclusion of tags without vocabulary control is called folksonomy, social indexing or social tagging. This indexing process can contribute greatly to the creation and management of digital collections, as it is carried out in a collaborative way, distributing resources, activities, and reducing costs in a way that becomes important for the organization, retrieval and access to digital information. These tags that belong to the semantic universe of the users can enrich the vocabulary, show how the users think and retrieve the information. This could constitute another front of studies in this project. The terminological work contributes to the elaboration of a taxonomy from the tags inserted in the ARQUIGRAFIA, which are compared with the VOCAUSP, conceptualized and categorized. The expected outcome of this phase will be the ARQUIGRAFIA controlled vocabulary.

Another aspect to be addressed is the process of the indexing of institutional images that should be considered under three different aspects: the denotation, connotation and context as we can see in the example in the Figure 1. The context refers to the image production conditions and involve issues such as how, when, where and why. Therefore, to determine the subject of a picture, one should not only identify and relate what you see, but the ideas behind it, its production conditions, and if possible the author's purpose:

Context = Fair Street at Santa Efigenia bridge

From this analysis we can select the terms that best represent the concepts and translate them under what best fits the information contained in the document.

Recent results

Below, we have list the main achievements and results obtained by the project in the last two years:

•The improvement of the interaction of user impressions records regarding visible aspects of the architectures represented in photographic images based on the binomials of spatial-spatial qualities integrated as semantic differentials, expressed in synthetic infographics, still integrated to the advanced system search;

•The conclusion of the digitalization of a set of 42 thousand images, 34 thousand slides (updated number of the set actually referring to Brazilian buildings and urban spaces of the FAUUSP collection) and 8 thousand physical photographs;

• The cataloguing and uploading of more than 6,724 images from the Library Collection of FAUUSP into the ARQUIGRAFIA system with the authorizations of copyright holders, the respective Creative Commons licenses, metadata, classification and indexing;

• Improvement of image upload mechanisms that were previously performed indirectly based on Excel spreadsheets for direct upload to the online system with differentiation between cataloging / indexing forms for ordinary users (private users) and institutional users (collections) with the reuse of data inserted in an image for the next upload;

• Improvement of an imprecise date insertion mechanism for cataloging images; as well as the inclusion of a mechanism that allows the insertion of data of images of the collection, which still do not have the license of the author to be privately exhibited to the institutions that registered them, without public viewing;

• The design of autocomplete controlled lists for: complete and correct names of Brazilian architects, as well as area specific tags, based on the Controlled Vocabulary of the Integrated Library System of USP (VOCAUSP) in the areas of Architecture, Urbanism, Arts and Engineering;

• The implementation of improvements in system interaction functionalities through UCD procedures, based on gamification elements aimed at greater user engagement especially with interface elements related to collaboration, such as: notifications, news, images and comments, "follow" and "be followed" by other users. And also design for gamification, such as: leadership chart, badges, week highlights, and scores;

• The design and implementation of a bilingual landing page integrated with ARQUIGRAFIA's communication enhancement project with users, potential users and public relations;

• Full development and consolidation of the ARQUIGRAFIA software in PHP (Laravel) with proper integration with the front end with a white background;

• Code refactoring and its fluid interactions, both with the development of the Android App and the design of the template + GRAFIA;

• The development of a first version of the ARQUIGRAFIA Android App available for smartphones in the Google Play Store (since 11/11/2016), which intensified the interaction of the system with new users and the direct experience of urban spaces in Brazilian cities;

• The enlargement of the ARQUIGRAFIA iconographic base with the experimental upload of drawings and videos as a pilot for a wider digital images platform.

Current Objectives

Considering the recent results, the ARQUIGRAFIA research team deals with new short term objectives:

• Implementation of a first version of the following functionalities: system moderation integrated with game elements (gamification); Instant communication of users logged into the system; Quiz as an instrument for intensifying architectural learning from questionnaires answered by users. Such functionalities have as main objective to promote an active community around the images and its information, seeking long-term sustainability for the system;

• Follow-up for a further 6 months the online version system and its consequent critical evaluation by users according to User-Centered Design with A / B Tests and formal usability tests on the system with the listed functionalities. Statistical analysis of users' engagement metrics with the system will allow the evaluation of the impact of recent changes made on the project;

• Monitoring and analysis of the integration of new institutions into ARQUIGRAFIA, based on the dissemination of the "Manual of ARQUIGRAFIA's Technical Project Procedures";

• The full development and free public dissemination of the +GRAFIA template integrated to the improvement of the Android and IOS App and the open source diffusion of the App + GRAFIA template.

• Deepening of the research on new pertinent themes, future developments and enlargements of ARQUIGRAFIA for the next two years. • Conduct studies relating to binomials plastic-spatial qualities arranged as semantic differential seeking to define an evaluation model for images of ARQUIGRAFIA. • Set metadata from the adequacy of descriptive fields of AACR2 cataloging for updated standards as the RDA set (http://www.rda-jsc.org/rda.html); FRBR (http://www.ifla.org/publications/functional-requirements-for-bibliographicrecords) or RDA/CCO (http://cco.vrafoundation.org), which are interoperable with the web environment and allow, for example, the application of conceptual ontologies. • Conduct usability studies to evaluate the current beta version and system redesign from the critical observations made by users • Expand the iconographic base of ARQUIGRAFIA including experimental digital video, scanned drawings from the original collection (plans, sections, elevations, perspectives and details) of the FAU Library, with due procedure for metadata record • Improve the indexing and implement search tools in the system data.

Conclusion

The ARQUIGRAFIA provides the convergence of institutional (public and private) and personal collections to one single open and free access website/Android App. For the scope of knowledge organization, this specific nature provides a singular opportunity to look accurately at its contemporary issues, specifically regarding the representation of images, vocabularies, interoperability among systems and user active participation. Furthermore, the template of ARQUIGRAFIA free software system, named +GRAFIA can be replicated and adapted to other areas of knowledge beyond architecture. In order to preserve and disseminate a digital collection of Brazilian architecture, the ARQUIGRAFIA project has been building an unprecedented network -promoting interaction between many researchers -and succeeded in constituting a fruitful scientific research laboratory for the continuous construction of interdisciplinary knowledge.

Figure 1

 1 Figure 1 Santa Efigênia Bridge, São Paulo, Brazil (ARQUIGRAFIA, 1997). The denotation refers to what appears in the picture, being a descriptive reading, where the meaning denotes what will be recognized unequivocally by both the indexer and the user: Denotation =Santa Efigenia, bridge, São Paulo The connotation is what the image suggests, which refers to the emotional content of the message, giving meaning to the whole, translating religious, ideological and cultural aspects. It is when the image reading passes through the collective memory: Connotation = Bridges (any)

Over the last


published or not. The documents may come

Distributed chaos with spontaneously broken translational symmetry

Distributed chaos with spontaneously broken translational symmetry

It is shown that distributed chaos with spontaneously broken time translational symmetry (homogeneity) has a stretched exponential spectrum E(f ) ∝ exp -(f /f0) 1/2 . Good agreement has been established with a laboratory experimental data obtained at large values of Rayleigh number Ra ∼ 3 • 10 14 in thermal convection. It is also shown that finite size subsequences of decimal digits sequence of irrational numbers (such as π and e) are dominated by the distributed chaos with spontaneously broken translational symmetry (the E(f ) ∝ exp -(f /f0) 1/2 spectrum is used as an indication). The later result indicates an universal character (not related exclusively to dynamical systems) of such spectrum for the distributed chaos with spontaneously broken translational symmetry.

I. DISTRIBUTED CHAOS

Many dynamical systems with chaotic behaviour have the exponential power spectra [1]- [4]

E(f ) ∝ exp -(f /f c ) (1)
where f c = const is some characteristic frequency. Let us consider, for instance, the seminal Lorenz equations:

dx dt = σ(y -x), dy dt = rx -y -xz, dz dt = xy -bz (2)
The Eqs. ( 2) correspond to a simplified model for thermal (Rayleigh-Benard) convection in a layer of fluid, heated from below and cooled from above. Usually used values of the parameters σ = 10.0, r = 28.0, b = 8/3 result in a chaotic solution [5]. In Fig. 1 we show (in the semi-logarithmic scales) power spectrum of z-component in Eqs. (2). The spectrum was computed by the maximum entropy method. This method gives an optimal resolution for comparatively short time series

f 1/2 [s -1/2 ] ln E T (f) exp-(f/f 0 ) 1/2
Ra = 3•10 14 Pr = 300 FIG. 2: Power spectrum of temperature measured at the cell center (the data taken from the Ref. [6]). The solid straight line indicates the stretched exponential decay Eq. ( 6).

[1] (in this case 3 • 10 4 data points). The dashed straight line corresponds to Eq. (1).

In the complex cases of distributed chaos the spectra can be approximated by a weighted superposition of the exponential functions Eq. ( 1):

E(f ) ∝ ∞ 0 P (f c ) exp -(f /f c ) df c (3)
where P (f c ) is a probability distribution of f c . If the probability distribution is narrow and can be approximated by a delta-function then we have the exponential spectrum Eq. ( 1). By the Noether's theorem the energy conservation law is related to the time translational symmetry (invariance) [START_REF] Landau | Mechanics[END_REF]. When the time translational symmetry (invariance) is spontaneously broken the action I can be used as an adiabatic invariant [START_REF] Sagdeev | Nonlinear Physics: from the Pendulum to Turbulence and Chaos[END_REF]. Then for this case a relation between characteristic velocity v c and the characteristic frequency f c can be found using the dimensional considerations:

v c ∝ I 1/2 f 1/2 c (4)
f [s -1 ] E (f) exp-(f/f 0 ) 1/2
Ra = 3•10 14 Pr = 300 FIG. 3: As in Fig. 2 but in the log-log scales. The solid curve indicates the stretched exponential decay Eq. ( 6).

If the characteristic velocity is normally (Gaussian) distributed, then f c has the chi-squared (χ 2 ) distribution

P (f c ) ∝ f -1/2 c exp -(f c /4f 0 ) (5)
where f 0 is certain constant. Substituting the distribution Eq. ( 5) into integral Eq. ( 3) we obtain

E(f ) ∝ exp -(f /f 0 ) 1/2 (6)
The above discussed Lorenz system is a very simplified model for thermal convection. Let us consider real (experimental) strong thermal convection. Figure 2 shows power spectrum of temperature measured at the cell center for very large Rayleigh number Ra = 3 • 10 14 and the Prandtl number P r = 300 (experimental measurements reported in the Ref. [6]). The solid straight line is drawn in the Fig. 2 in order to indicate the stretched exponential spectrum Eq. ( 6) corresponding to the distributed chaos with spontaneously broken translational symmetry. Similar spectrum was observed for the first time in experiment reported in Ref. [7]. As it is mentioned in the Ref. [6] the inertial (scaling) range was completely suppressed by buoyancy in this situation. Actually the Eq. ( 6) covers the entire spectrum (rather wide range) as one can see in figure 3 (in the log-log scales). It should be noted that thermal convection at the high values of the Rayleigh number is usually considered as strong turbulence and chaos was taken into account at the large scale thermal winds only [14], [15]. About Hamiltonian approach to hydrodynamics see, for instance, Refs. [START_REF] Eyink | [END_REF]- [13]. It should be also noted that spontaneous breaking of the space translational symmetry (homogeneity) in wave turbulence results in a crucial change of the statistical attractor [16]. The later phenomenon is related to the Kolmogorov-Zakharov spectrum instability to the perturbations weakly breaking the space translational symmetry.

II. IRRATIONAL NUMBERS

Distribution of digits in the decimal digits sequence of irrational numbers is apparently random. We will be mainly interested in the normal numbers. For these numbers no finite set of digits occurs more frequently than any other. There is a proof that almost all (by the means of the Lebesgue measure) real numbers are normal [START_REF] Calude | Information and Randomness: An Algorithmic Perspective[END_REF], and it is believed that such important constants as π and e are normal (the rigorous proof is still absent and approach is empirical, see for instance Ref. [START_REF] Bailey | [END_REF]). In this note the decimal digits sequence will be mapped into a set of so-called telegraph signals in order to compare properties of the decimal digits sequences with those of the signals corresponding to dynamical systems. Analogous approach was used in Ref. [19] for distribution of the prime numbers.

Let us map the decimal digits sequence into telegraph signals by defining binary functions B 0 (n), B 1 (n),... B 9 (n) of natural numbers n = 1, 2, 3, ... (n enumerates places in the sequence or in a subsequence of the digits, see Fig. 4). The telegraph signal B 6 (n), for instance, corresponds to the digit 6 in the the decimal digits sequence. Such binary function takes two values +1 or -1 and changes its sign passing each digit 6 along the decimal digits sequence (all functions B 0 (n), B 1 (n),... B 9 (n) are analogously defined). Figure 4 shows a short sample of the B 6 (n) function for the decimal digits sequence of the number π (first 200 places).

Construction of these functions is rather sensitive to clustering of a digit in the decimal digits sequence, i.e. to appearance of such clusters: 66, 666, 6666 and so on. To avoid this problem let us consider modified function B6 (n). Unlike the function B 6 (n) this function is constructed after all above mentioned clusters have been collapsed (each cluster has been replaced by single digit), i.e. 66 → 6, 666 → 6, 6666 → 6 and so on, in the decimal digits sequence (all functions B0 (n), B1 (n),... B9 (n) are analogously defined). This mapping allows to compare properties of the telegraph signals with those of the signals corresponding to dynamical systems by interpretation n → t, where t is time.

III. FINITE SIZE SUBSEQUENCES

Real (stochastic) randomness imply translational symmetry (invariance) for any fixed digit (say 6) along the decimal digits sequence, i.e. appearance of a fixed digit (say 6) does not distinguish different points (places) in the decimal digits sequence (a statistical homogeneity). For finite size subsequences this translational symmetry (invariance) can be spontaneously broken.

Let us assume certain universality of the result Eq. ( 6) for the distributed chaos with spontaneously broken symmetry, so that it includes also the case under con-

0 0.1 0.2 0.3 0.4 0.5 0.6 -3 -2 -1 0 1 2 3 f 1/2 ln E(f) exp-(f/f 0 ) 1/2
1 FIG. 7: As in Fig. 5 but for the number e.

sideration (n → t). Figure 5 shows frequency spectrum E(f ) for the telegraph signal B1 (n) computed using a finite size subsequence (first 20000 places) of the decimal digits sequence of the number π. The computation was made with the maximum entropy method (this method provides optimal spectral resolution for relatively short data sets and, in particular, for the spectra caused by chaotic phenomena [1]). The semi-logarithmic scales are used in order to compare the data with the Eq. ( 6). The straight line is drawn in the Fig. 5 to indicate correspondence of the data to the Eq. ( 6). The frequency f 0 ≃ 0.01, that corresponds to period T 0 = 1/f 0 ≃ 100 in the decimal digits sequence. Figure 6 shows analogous situation for B6 (n) (all other telegraph signals B0 (n) ... B9 (n) exhibit the same properties).

All irrational numbers (with the assumption of the translational invariance) can be analogously treated and one can expect analogous results. Figure 7, for instance, shows frequency spectrum E(f ) for the telegraph signal B1 (n) computed using a finite size subsequence (first 20000 places) of the decimal digits sequence of the number e. The straight line is drawn in the Fig. 7 to indicate correspondence of the data to the Eq. ( 6). The frequency f 0 ≃ 0.01, that corresponds to period T 0 = 1/f 0 ≃ 100 in the decimal digits sequence, the same value of f 0 (or T 0 ) as for the number π. I thank C. S. Calude for comments.

  .O. Box 31155, Jerusalem 91000, Israel

FIG. 1 :

 1 FIG.1: Logarithm of power spectrum for z-component of the Eq. (2) against frequency f . The dashed straight line corresponds to Eq. (1).

FIG. 4 :

 4 FIG. 4: A short sample of the B6(n) function (first 200 places).

1 FIG. 5 : 6 FIG. 6 :

 1566 FIG.5:Frequency spectrum E(f ) for the telegraph signal B1(n) computed using a finite size subsequence (first 20000 places) of the decimal digits sequence of the number π.


P Bas

J-M Chassery
email: jean-marc.chassery@inpg.fr

B Macq

Geometrically Invariant Watermarking Using Feature Points

This paper presents a new approach for watermarking of digital images providing robustness to geometrical distortions. The weaknesses of classical watermarking methods to geometrical distortions are firstly outlined. Geometrical distortions can be decomposed into two classes: global transformations such as rotations and translations and local transformations such as the StirMark attack. An overview of existing self-synchronising schemes is then presented. Theses schemes can use periodical properties of the mark, invariant properties of transforms, template insertion, or information provided by the original image to counter geometrical distortions.

Thereafter a new class of watermarking schemes using the image content is presented. We propose an embedding and detection scheme where the mark is bound with a content descriptor defined by salient points. Three different types of feature points are studied and their robustness to geometrical transformations is evaluated to develop an enhanced detector. The embedding of the signature is done by extracting feature points of the image and performing a Delaunay tessellation on the set of points. The mark is embedded using a classical additive scheme inside each triangle of the tessellation. The detection is done using correlation properties on the different triangles. The performance of the presented scheme is evaluated after JPEG compression, geometrical attack and transformations. Results show that the fact that the scheme is robust to theses different manipulations. Finally, in our concluding remarks, we analyse the different perspectives of such contentbased watermarking scheme 1 .

I. INTRODUCTION

During the last decade, digital technologies have grown dramatically. Digital audio, video and software are widely used within home computers and open networks. Nevertheless one particular drawback of digital content is their ability to be volatile and easily processed. Digital objects may be copied, manipulated or converted easily without any control. The goal of watermarking is to embed an unnoticeable information (called a mark) in the content of media. Thus the functionality of the medium is improved without altering the format.

¡

This work was supported by the European IST Aspis project and the National RNRT Aquamars project.

Several applications of watermarking have been considered by researchers.

¢

Copyright: In this case, the mark is associated with an Identity Number. In this way, the mark identifies the owner of the content and can be used for copyright purposes (prevent illegal copies). The embedding and the detection of the mark depend on a secret key. The mark has to be robust and detectable after numerous processing treatments or attacks that preserve the original content.

¢ Database retrieval and Data hiding: In this case the mark permits the identification of the content. The mark contains a description of the content or a pointer to this description and can be used for database "classification". In this application, the robustness of the mark is not decisive but the mark has to be detected after basic format conversion.

¢ Authentication: the mark can be a fragile mark that will disappear after image manipulation. It can be used to authenticate the content and to prove that its integrity has been preserved. The function of the mark is to prove that the content has not been manipulated and consequently the robustness of the marking algorithm is not a prior achievement.

A. Problem of synchronization

The detection of the mark requires a synchronization step to locate the embedded mark in the content. Here are two scenarios that illustrate this idea: ¢ In audio, the mark is commonly detected in real time. In most practical cases, the position of the beginning of the sequence is not known and cannot be used as a reference. Consequently, the detector must pre-process the audio to know where the mark is located.

¢

The case of digital images is similar because they can undergo geometrical transformations after analog-to-digital and digital-to-analog conversion such as printing and scanning the image. Resizing and rotating are also basic manipulations in image edition and require a synchronization step for the detection of the mark.

B. Paper presentation

In this paper, our work is focused on the problem of mark synchronization in digital images. The basic idea is that, binding the signature with the content of the image, the mark could be detected when the image undergoes geometrical transformations. We select feature point detectors to represent an image content descriptor. The set of feature point permits image partitioning using a delaunay tessellation. The mark is embedded in each triangle via an affine transformation which allows the orientation of the random sequence. The detection of the mark is based on the same content analysis and is performed using a correlation criterion. The diagram of the presented watermarking scheme is depicted in Figure 1. The paper is organized as follows: the second section outlines the weaknesses of watermarking schemes against geometrical transformations and geometrical attacks. We also provide an overview of the different watermarking approaches to counter geometrical attacks. We divide the different schemes in several categories to highlight their advantages and limitations. In section 3, we describe a new class of watermarking schemes, called content-based methods, which use image descriptors to orientate the signature. We present a new method, using feature points, that embeds a pre-defined triangular pattern inside triangles in a tessellation of the image. Section 4 presents three feature points detectors and an evaluation of their robustness is presented. In section 5, we describe a basic spatial embedding process. We also present different tests with a large variety of images and different categories of geometrical transformations and compare our results with the Digimarc solution. Finally, in section 6 we outline the positive aspects and the perspectives offered by the classes of content-based approaches.

II. OVERVIEW OF CLASSICAL SELF-SYNCHRONISING TECHNIQUES

The goal of this section is to describe the problem of geometrical distortions and to give an overview of techniques countering geometrical transformations: self-synchronising schemes. We will focus this short overview on four classes of selfsynchronising techniques:

A. Effect of geometrical distortions

One major drawback of classical watermarking schemes is the lack of robustness to geometrical distortion. In classical additive (spread-spectrum) methods such as presented in [START_REF] Tirkel | Electronic water mark[END_REF][36] [START_REF] Cox | Secure spread spectrum watermarking for multimedia[END_REF] and substitutive methods such as presented in [4] [START_REF] Koch | Embedding robust labels into images for copyright protection[END_REF][25] [START_REF] Maes | Digital watermarking by geometric warping[END_REF], the image is processed as a classical array of pixels with no reference except the coordinates of each pixel. Consequently if the image undergoes a geometrical transformation, the mark in the image cannot be detected without identifying the transformation. Using an additive scheme, the correlation cannot be performed because the generated random sequence and the embedded random sequence are not synchronized. Using a substitutive scheme, the location of the marked components cannot be performed because initial locations depend on external coordinates; consequently the decoding of the mark is not possible.

Basically, two levels of geometrical distortions can be outlined:

¢

The typical geometrical transformation commonly used in image edition such as rotation, translation, cropping, and composition. These transformations are applied on the whole image, and in many ways can be easily represented by a mathematical operation. One basic solution to identify the transformation is to perform an exhaustive detection considering all possible geometrical transformations of the marked image. In this case the computing cost will drastically increase. For example, if we consider only a composition of rotation and scaling operations from ¢¡ ¤£ up to ¥ ¡ ¦¡ §£ of the image size, the processing cost is roughly multiplied by ©¨ ¡ .

¢

The other category of geometrical distortions are especially designed to desynchronise the mark without visual changes. M. Khun and F. Petitcolas [START_REF] Fabien | Attacks on copyright marking systems[END_REF] developed a benchmark called StirMark containing different attacks. One of the first developed attacks of this program is composed of local random geometrical distortions that permits us to defeat many classical watermarking schemes without visible alterations [START_REF] Dugelay | Possible counter-attacks against geometric distortions[END_REF] (cf Fig. 2).

B. Periodic insertion of the mark

One strategy to counter the problem of geometrical desynchronization is to add redundancy during the embedding process. This redundancy can be used to localize the position of the signature and to improve the detection phase. We present different methods based on a periodic insertion of the mark.

Kalker and Janseen developed a spatial spread-spectrum scheme for video wartermarking [START_REF] Kalker | A video watermarking system for broadcast monitoring[END_REF]. The authors design a periodic insertion of the mark to cope with the important problem of image shifting in video sequences. A random basis sequence of size ! " $# is repeated to provide a tilling which is added to the original image. The Delannay and Macq proposed a method to generate 2-D patterns having cyclic properties [START_REF] Delanay | Generalized 2-d cyclic patterns for secret watermark generation[END_REF] to address image shifting problems. The shape of the basic sequence is not a block but depends on two secret parameters and . This solution avoids a malicious estimation of the mark by averaging different frames. Each element of the 2D sequence is linked with its neighbourhood by a constant relation (cf Fig 3). A shifted version of the mark is consequently generated from any position of the marked image. The detection is performed by cross-correlation between the random sequence and the reordered pixels of the image. Hartung et al. applied a periodic insertion to perform synchronization and counter the StirMark attack [START_REF] Hartung | Spread spectrum watermarking: Malicious attacks and counter-attacks[END_REF]. The correlation of the mark is performed using a 4-dimensinal sliding correlator. Parameters are used to simulate geometrical transformations such as translation, rotation or scaling operations (cf Fig 4). If the mark is detected in a block, the localization of the mark in the neighbour block is initialised by the previous locations. Kutter proposed an insertion method for watermark detection after geometrical affine transforms [START_REF] Kutter | Watermarking resisting to translation, rotation and scaling[END_REF]. A periodic mark is embedded in the luminance values of the image. A cross-correlation function of the image allows the localization of the different peaks generated by the periodic mark, and consequently the identification of the transform (cf

W[0] W[N-1] W[1] W[N-2] .... W[i] W[(i+k2) mod N] W[(i+k1+k2) mod N] W[(i+k1) mod N] W[(i+k1-k2) mod N] W[(i-k2) mod N] W[(i-k1+k2) mod N] W[(i-k1) mod N] W[(i-k1-k2) mod N] ... ... ... RANDOM SEQUENCE 2D CYCLIC SEQUENCE GENERATED AROUND i

C. Template insertion

Another solution to counter geometric transformations is to identify the transformation by retrieving artificially embedded references.

Pereira and Pun proposed to embed templates in image components to identify the geometrical transformation and enable the synchronization of the mark [START_REF] Pereira | Fast robust template matching for affine resistant image watermarking[END_REF]. In this study, the geometrical transformation belongs to the class of affine transformations (i.e. RST and shearing transformations). Templates are localized in a ring corresponding to the middle frequencies of the image spectrum. Templates are generated by increasing the magnitude of selected coefficients and creating a local peak. The initial location of templates and the detected location of local maxima are matched to perform the identification of the affine transform (cf Fig. 6). One major advantage of template based approaches is their faculty to address synchronization of local and global transformations, but attacks have been developed to erase template presence [START_REF] Voloshynovskiy | Watermark template attack[END_REF].

D. Invariant transform

Another way to cope with resynchronisation problems after affine transforms is to embed the watermark in an invariant domain.

Ó Ruanaidh and Pun introduced a watermarking scheme exploiting some properties of the Fourier transform. In this scheme, mark embedding is performed using a RST (Rotation, Scaling and Translation) invariant domain [START_REF] Joseph | Rotation, scale and translation invariant spread spectrum digital image watermarking[END_REF].

Given a 2D function ¢¡ ¤£ ¦¥ £ ¨ § representing the image, the au- thors extended the Fourier transform invariance properties to cyclic translations using a log-polar mapping:

£ © ¨ ! " #© $ ¨ &% (' ) (1)
where 0 21 43 and 51 76 ¡ 98 ¥ A@ B6 . Applying the mapping, the rota- tion of the point ¡ ¤£ ¥ " § by an angle C and the scaling operation with a factor D are considered as a translation:

¡ ¤D £ ¥ D E" § BF ¡ G0 IH P EQ BD ¥ § ¡ G£ R SC UT 4" V W% P' XC ¥ £ R W% P' )C XY 2" 9C § `F ¡ G0 ¥ UY aC § Lin et al. developed another RST invariant scheme depending on the log-polar coordinates of the Fourier transform [START_REF] Lin | Rotation-, scale-, and translation-resilient public watermarking ofr images[END_REF].

A 1D signal is generated summing the log-magnitude of the 2D log-polar spectrum over a band of radii:

b ¡ ¤ § © dc fe gH ( hQ i¡ qp r s¡ ¤D e ¥ § p § ¡ Et Iu wv yx ¦¡ Et

(3)

where r i¡ GD e ¥ § represents the 2D log-polar spectrum. The authors outline that the created component b ¡ ¤ § is invariant to both translation and scaling operations while rotations generate a circular shift of the signal. The signature, generated with a mixing function, is added to b ¡ G § to create the marked image.

E. Using the original image

Non-blind watermarking schemes use the original image to detect the mark. These algorithms may use this valuable information to identify the geometrical transformation applied on the image.

Davoine et al used the original image to compensate geometrical deformations induced by the StirMark attack [START_REF] Davoine | Watermarking et résistance aux déformations géométriques[END_REF]. A regular triangular tessellation is applied on the original image and on the marked and attacked image. The compensation of geometrical distortion is performed by slightly shifting different vertices of the attacked image tessellation (cf Fig. 8). The geometrical compensation can also be done using more basic image feature such as image edges. Once the geometrical compensation has been processed, the mark can be recovered and extracted.

F. Overview remarks

We have presented different self-synchronizing schemes that allow the detection of the mark after a special category of geometrical distortions such as translations, general affine transforms or local distortions such as the StirMark attack. It is important to point out that the presented methods are not robust to each category of geometrical distortion. On one hand, periodic insertion, invariant transforms and template embedding enable synchronization after affine transforms. On the other hand, the use of the original image improves the robustness to local distortions, but the extension to affine transforms implies an increase of the computational cost. this artificial embedding can be easily removed [START_REF] Voloshynovskiy | Watermark template attack[END_REF]. The different limitations of the presented methods are summed up on Table I.

III. CONTENT BASED WATERMARKING SCHEMES

The objective of this section is to present a new class of watermarking schemes that achieve watermark recovery after geometrical transformations using image content. In particular, the design of a new method using feature points as a content descriptor is presented.

A. Previous works

Content-based watermarking schemes provide another solution to counter geometrical distortions. In this way the location of the mark is not linked with image coordinates, but with image semantics. The problem of geometrical synchronization is solved because the image content represents an invariant reference to geometrical transformations (cf Fig. 9). Content based techniques belongs to second-generation watermaking schemes defined by Kutter et al because the image's content is exploited for the embedding of the mark [START_REF] Kutter | Towards second generation watermarking schemes[END_REF]. Let us start by an overview of different content-based methods.

¢

Duric et al have proposed a method for recognizing geometrically distorted images and restoring their original appearances [START_REF] Duric | Recovering watermarks froms images[END_REF]. The restored image is used to recover watermarks that were embedded. Image's content is used, represented by feature points, to identify the geometrical transformation. The location of feature points between the original and marked/distorted image permit the identification of the transformation. Local geometric distortions are countered calculating normal displacement fields between the two images. Translation, scaling and rotations are estimated by an affine transform. The presented scheme is robust to the Stirmark attack but the recovery of the mark requires the original image or the initial locations of the feature points.

¢

Sun et al developed another watermarking method based on image feature to identify the geometrical transformation [START_REF] Sun | Recovering modified watermarked image with reference to originale image[END_REF]. Firstly, feature points are extracted from the original and the marked image. Secondly, the synchronizing scheme performs a matching between the two set of points and identify the transformation (cf Fig. 10).

¡ © ¥ ¦ ¦ § ¨© ¡ ¤£ T £ ¢ § Y ¡ ¤" T 4" ¢ § (4)
Hence, the scale factor is given by:

© ¡ £ ¡ £ (5)
where ¡ and ¡ represent respectively the average distances considered on the marked image and on the original image. The rotation angle estimate is given calculating the difference between the sums of angles in the first quadrant of the wavelet decomposition for the original ( ) and the marked image ( ¡ ):

© ¨¡ © T © § (6)
¢ Dittman et al have designed a content-based watermarking method that does not require the original image and uses self spanning pattern [START_REF] Dittmann | New approach for transformation-invariant image and video watermarking in the spatial domain: self-spanning patterns (ssp)[END_REF]. A basic pattern is represented by a polygon that is spanned over four image inherent points like image edges or corners. The other patterns are spanned around the basic pattern and each pattern carries one bit of the whole watermark (cf Fig. 11). Finally the mark detection is done after recovering feature points locations. Experimental results, presented for a large range of geometrical transformations, illustrate the fact that the presented algorithm is quite robust to geometrical distortions.

Image corners

Self spanning patterns

B. Method design

To develop a content-based method, we first have to select an appropriate tool to extract an image content descriptor. This representation has to be robust to geometric transformations. We orient our choice towards tools commonly used in pattern recognition: feature points detectors. Our first approach was initially proposed in [3]. Our proposed system can be classically dissociated into two different steps, the embedder and the detector. An overview of the different stages is summarized below:

In the embedder side: 1) Detect robust feature points in an image.

2) Generate a triangular tessellation of the image based on the set of feature points. 3) Map a triangular spread sequence (watermark) into each triangle of the tessellation via affine transform. 4) Add the mapped sequence on each triangle.

In the detector side:

1) Reconstruct the tessellation.

2) Map each triangle to the shape of the original triangular watermark. 3) Compute the correlation of each mapped triangle with the original watermark. 4) Accumulate the correlations to detect the watermark over the whole image. Consequently the next section (section IV) of this paper is devoted on an evaluation of different feature point detectors, and the content-based watermarking scheme is presented in section V.

IV. FEATURE POINTS DETECTORS

The objective of this section is to give an overview of different feature points detectors and to present a benchmark system for selecting a robust detector. It is well known that feature points detectors find salient points in natural images. These points are often located near corners and edges of the image. Feature points were first developed for computer vision and reconstruction [START_REF] Boufama | Using geometric properties for automatic object positioning[END_REF] [START_REF] Faugeras | Self-calibration of a 1d projective camera and its application to the self-calibration of a 2d projective camera[END_REF] but they are also employed in data-base retrieval as a descriptor of the image [START_REF] Loupias | Wavelet-based salient points for image retrieval[END_REF] [START_REF] Dufournaud | Matching image with different resolutions[END_REF]. We focus our study on three detectors that are commonly used in pattern recognition and vision systems.

A. Harris Detector

The Harris and Stephens detector was developed for 3-D reconstruction [START_REF] Harris | A combined corner and edge detector[END_REF]. This detector uses differential features of the image. The construction of the detector is based on a corner detection function created by Moravec [START_REF] Moravec | Obstacle avoidance and navigation in the real world by a seen robot rover[END_REF]. The response function ¢ ¤£ ¦¥ §

is calculated for a shift ¡ ¤£ ¥ " § from the central point ¡ ©¨¥ § : ¢ £ ¥ § © ¥ ¥ p r £ ¥ § T r ¥ p (7)
where r ¥ represents the luminance of the image at the coordinate ¡ !¨¥ " ! § . the function ¥ represents a rectangular window centred on ¡ ¤£ ¥ " § .

Harris reformulated the detection function using a matricial formulation.

Given:

# © r %$ 6 PT ¥ ¡ ¥ & (' C ¦r 0) ¦C ¨£ (8) 1 © r %$ 6 PT ¥ ¡ ¥ & 32 4' C ¦r 5) AC ¨" (9) 6 © # $ (10) ¡ © 1 $ (11) ¤ © ¡ # 71 § $ (12)
where $ denotes the convolution product. The detection func- tion ¢ £ ¥ § is then expressed by:

¢ £ ¦¥ § © ¡ ¤£ ¥ " § "8 ¡ G£ ¥ " § 2 9 % A@ CB 8 © D 6 £ ¦¥ § ¤ £ ¥ § ¤ £ ¦¥ § ¡ ¤£ ¦¥ § FE (13) ¢ £ ¥ §
can be considered as a local auto-correlation function of the image with a shape factor 8 . Harris and Stephens gave a new definition of the detector function of the eigenvalue G and H of the array 8 . These values are invariant by rotation and if their magnitudes are high, the local auto-correlation function is represented by a local peak. To avoid computing the eigenvalue of 8 , the new criterion is based on the trace and determinant of 8 :

I !¡ 8 § © G Y H © 6 Y ¡ (14) P RQ ¡ 8 § © G H © 6 ¡ T ¤ (15) S %T © P RQ ¡ 8 § T I ¡ 8 § (16)
where is an arbitrary constant.

Feature points extraction is achieved by applying a threshold on the response S ¤T and searching for local maxima.

¡ ¢¡ ¥ ¤£ § ¦¥ ¨ § S ¤T ¡ ©¡ ¥ £ § ' ¡ !¨¥ " ! § 1 ¥ e ¥ S ¤T ¡ ©¡ ¥ ¤£ § ! S ¤T ¡ !¨¥ " ! §
The function S T applied on lena is shown on Figure 12.

B. Other tested detectors

We have also tested two other detectors: the Achard-Rouquet [START_REF] Devars | Un detecteur de point carater-istiques sur des images multispectrales. extension vers un detecteur subpixellique[END_REF] detector and the SUSAN detector [START_REF] Smith | Susan -a new approach to low level image processing[END_REF]. The Achard-Rouquet detector is based on the fact that the angle between two gradient vectors is important around corners. The corner strength is hence calculated using cross product of the neighbour gradients.

where ¥ e represents the neighbourhood of the pixel ¡ ©¡ ¥ ¤£ § and @ denotes the cross product. Given : # © C ¦r 5) AC ¨£ (18) 1 © C ¦r 5) AC ¨" [START_REF] Harris | A combined corner and edge detector[END_REF] and developing the equation 17, the authors obtained a normalized version of the detector

© r £ v r § Y r § v fr £ T ¥ Ar £ r § v r £ r § v r £ Y v r § (20)
where v denotes the mean applied on the neighbourhood ¥ e .

The set of feature points is obtained using a threshold of the value and selecting local maximal.

The SUSAN detector is based on a geometrical observation of the image [START_REF] Smith | Susan -a new approach to low level image processing[END_REF]. SUSAN means Smallest Univalue Segment Assimilating Nucleus.

In this method, each pixel of the image, representing a nucleus, is associated with a circular mask. The mask is divided in two distinct areas, the USAN area (Univalue Segment Assimilating Nucleus) and its complement. A corner of the image is consequently represented by a local minimum of the USAN function applied on the image. The principle of this detector is illustrated on figure 13. The number of pixels that belong the USAN area allows the computation of the detector magnitude. The USAN computing is done by calculating E B¡ Gr ¥ e § .:

E B¡ Gr ¥ e § © ¥ #" %$ & ©( ) ¤ #¡ ©¡ ¥ ¤£ E¥ ¨¥ § (21)
The ¤ #¡ ¢¡ ¥ £ E¥ ¨¥ " ! § function represents the mask geometry. A feature point is consequently detected if E B¡ r ¥ e § is smaller than E GF 8 3 £ . E GF 8 3 £ representing half of the total number of pixels in the mask.

C. Detector benchmark

The next step of this study is logically to evaluate of the robustness of these different detectors. To this end, we designed a function named score that evaluates the capacity of the detector to preserve the selected points when the image undergoes a geometrical transformation or other processing. This function is defined as follows:

& fe '& [START_REF] Kalker | A video watermarking system for broadcast monitoring[END_REF] where ¨F hg denotes the number of points present in the initial image, and ¨F pi ¦q , ¨F Qr q , ¨F Ts ¦q represent respectively the number of points that have been created, destroyed and preserved after the process. This function is maximal when

¨F i ¦q © ¨F r q ©
¡ , and is in this case equal to 1.

We evaluated this function on four different images:

¢

The 512 512 lena image, is well known in image processing. This is a high-contrast image with sharp corners and textured areas.

¢

The 512 512 baboon image. This image contains a large textured area (the fur of the animal) and a homogeneous area represented by the face.

¢

The 454 652 tree image is an extremely textured image in which the geometrical singularities are visually hard to designate.

¢

The 549 748 water image belongs to the JPEG2000 database. This is an image with large homogeneous areas and its content is indistinct and poor.

The score was evaluated after registering feature points and computing the inverse transformation to compute the counts. We decided also to evaluate the function score on [START_REF] Kundur | Digital watermarking using multiresolution wavelet decomposition[END_REF] ¢ 5 scaling operations, with a 0.9 down to 0.5 factor. We performed the inverse transformation to compute the score. ¢ 5 noise additions. We added an uniform noise with peak values equal from ¡ 50 to ¡ 10 for 256 grey level images. The final score is given by calculating the mean of the different scores after each operation.

D. Enhanced Detector

We decided to use to a pre-filtering blur operation because a feature point detector is sensitive to image variation such as corners or textured areas. If the content of the image is textured or noisy, the potential number of feature points becomes important and the robustness of the detector is reduced. We used a E E mask represented by:

8 g © ¢ £ ¤ @ '@ p@ . . . . . . @ '@ p@ ¥ §¦ ¨(23)
The figure 14 represents the computed score for different sizes of E . We can see that this pre-filtering operation increases the robustness of the detectors. In the rest of this study, we decided to choose a filter which offers the best trade-off between the robustness and the processing time. A feature point is represented by a local maximum of the detector response. It is also important to define the size of the neighbourhood. If this size is too small, the distribution of the different feature points is concentrated on textured areas. If the size of neighbourhood is too large, the feature points become isolated.

To obtain an homogeneous distribution of feature points in the image, we chose to use a circular neighbourhood to avoid increasing detector anisotropy. The centre of the neighbourhood is the considered pixel. To be robust to scaling operations, the circle diameter depends on the image dimensions: P © Y © [START_REF] Keys | Cubic convolution interpolation for digital image processing[END_REF] The integers and © represent respectively the image width and height. The neighbourhood size is quantized by the value.

Figure 15 illustrates the influence of the parameter. We decided to choose a value equal to 24 to obtain an homogeneous repartition of the feature points.

E. Selecting the best detector

We calculated the detectors' scores on the four test images. These different scores are presented on figure 16. From these results we can deduce two important elements: ¢ The Harris detector is the most robust detector on each image.

¢

The detector robustness depends on the content of the image. The score is the highest for the lena image which contains sharp corners. For textured images as baboon or tree, the score is less important. The weakest result is obtained for the water image. This is mainly due to the fact that the content of this image can be greatly modified by noise addition or Jpeg compression.

V. EMBEDDING AND DETECTION SCHEMES

The objective of this section is to show how feature points are used in this content-based watermarking method. The embedding and detection scheme are presented and the performance of our method are described.

A. Embedding scheme

Let us start by an overview of the embedding part. Firstly, the mark embedding uses references provided by feature point detectors. Next, a Delaunay tessellation is employed to decompose the image into a set of disjoint triangles. The signature embedding is done by inserting a mark inside each triangle of the tessellation. We focus our choice on Delaunay tessellation because it brings important properties:

¢

The tessellation has local properties: if a vertex disappears, the tessellation is only modified on connected triangles ¢ Each vertex is associated with a stability area in which the tessellation is not modified [START_REF] Bertin | Optimization in Voronoi Diagrams[END_REF] when the vertex is moving inside this area.

¢

The computational cost is low: a Delaunay tessellation can be done using fast algorithms [START_REF] Chassery | Géométrie discrète en analyse d'images[END_REF] [START_REF] Schmitt | Algorithme rapide de maillage de delaunay dans Rd[END_REF].

The general embedding scheme is shown in figure 18. Let us decompose this scheme into different steps:

1) A random sequence ¡ is generated. The shape of this sequence is delimited by a right-angled isosceles triangle with an arbitrary size (in our tests $ ). A seed initialising the generator defines the secret key. The sequence values belong to the set T ¥ Y ¥ and the mean of sequence is zero. We chose to spread the sequence on ¥ ¥ pixel blocks.

This allows both improving the signature detection after the blurring process, and offering a better resilience to feature point positioning errors.

2) The detection of feature points using our improved Harris detector is applied to the image. We obtain a set of points

¢ © ¤£ 1 ¦¥ ¥ ¡ © ¥ ¨¨¨¥ E ¥ .
3) A Delaunay tessellation ¨© ¨ ¥ E¥ ¡ u ¡ v ¨is

¢ : P W¡ ¢ § © ¡ £ ¥ £ e ¥ £ ¨ § 1 ¢ § § ¡ £ ¥ £ e ¥ £ ©¨ § ¡ ¢ T £ T £ e T £ ©¨ § © ¥ (25)
The constructed triangle defined a Delaunay triangle. The signature detection is performed in each triangle ¨¨1 ¨.

4) An affine transform is performed on triangle to map the shape of ¨¨. The affine transform is oriented using the magnitude of each angle issued from ¨¨. We use a splinecubic interpolation during the transformation to preserve high frequencies of ¨ [31] [START_REF] Keys | Cubic convolution interpolation for digital image processing[END_REF]. The triangle ¡! is then obtained.

The affine function " allows us to transform a point ¡ ¤£ ¥ " § of the triangle ¨ into a point ¡ G£ ! ¥ " ! § of the triangle ¨! . " is defined by six real parameters 3 , F , I , 5 , and . The relation between two pairs of points is given by:

" ¡ G£ # ¥ " $ § © % £ ! " ! '& © D 3 F I 5 E % £ " (& Y % & © ! % £ " (& Y ¨ (26)
This affine transform " permits us to model geometrical transformations such as rotations, scaling operations, or shearing effects. There are six different affine transforms that map the triangle ¨ into the triangle ¡! . The selected affine transform has to be unique. Consequently, we decided to classify the different vertices of ! . We use the magni- tude of the angles to obtain a unique transformation (cf Fig 17). 5) ¨ ! is multiplied by a visual mask. This mask, named

)

, is based on the image luminance, We exploit the fact that the human eye is less sensitive to contrast in dark or bright areas than to middle luminance areas [START_REF] Kankanhalli | Content-based watermarking of images[END_REF].The signature ¨s is obtained by weighting ¨! :

¨s ¡ ¢¡ ¥ ¤£ § © G ) ¡ ©¡ ¥ ¤£ § ¨ ! ¡ ¢¡ ¥ £ § (27)
The signature power is adjusted using the real G .

6) The marked triangle is obtained adding ¨s and ¨¨: ¨ © ¨s )Y ¨¨.

7) ¨ is substituted for ¨¨.

B. Detection scheme

The detection process uses the result of the feature point detection and consequently performs a self-synchronisation of the mark. If the marked image undergoes a geometric transformation, the set of salient points mainly follows the transformation and several triangles are consequently conserved. The presence of the signature in a triangle is certified by a correlation criterion.

The detection scheme is illustrated on figure 21. We now detail the different steps of the signature detection; the three first steps are identical to the insertion scheme: 1) ¨ is generated from a random sequence depending on a secret key.

2) The detection of feature points using our improved Harris detector is applied to the image.

3) A Delaunay tessellation ¨© ¨ ¥ E¥ ¡ u ¡ v ¨is performed using image feature points. The mark is inserted in each triangle ¨¨1 ¨.

4) Each triangle ¨¨is warped into a 64 64 right-angled isosceles triangle denoted ¡ .

5) From ¢ we process a Wiener filtering using ¡ statistics to eliminate components provided by the original image. We obtain

£ ¨ : £ ¨ ¡ ¢¡ ¥ ¤£ § © ¥¤ &6 ¨ & ¡ ¢¡ ¥ ¤£ § ¤ 6 ¨ & ¡ ©¡ ¥ ¤£ § Y ¤ 6 ¢ & ¡ ¢¡ ¥ £ § 6 ¨ ¡ ©¡ ¥ ¤£ § T 8 ¤ 6 ¨ & ¡ ©¡ ¥ ¤£ § & (28)
¤ ¡ § represents the local standard variance and 8 ¦¤ ¡ § the local mean for the ¡ ©¡ ¥ ¤£ § location.

Wiener prediction can be considered as a denoising operation [START_REF] Hernandez | Statistical analysis of watermarking schemes for copyright protection of images[END_REF] and allows separation of the image components from the mark components. In case of textured areas, the signal-to-noise ratio is lower, and consequently the signature detection, computing the correlation between ¨ and ¨ , is perturbed by the image components. 6) The signature detection can be performed using two different levels. First it can be done locally by comparing the magnitude of I QP I I !¡ ¡ 8 £ ¨ § with a threshold for each triangle. The threshold depends on a false response probability. We represent the statistics in a case of a false response by a normal distribution.

A mark can only be detected according to a probability of false alarm

¢ ¨ § ¢

representing the probability of signature detection in a image which does not contain the mark. In our study, the signature is detected inside a triangle if:

I QP I I ¡ ¨ 8 £ ¨ § ! ¡ ¢ § ¢ § (29)
where the real ¡ ¢ ¨ § ¢ § represents a threshold depending on the false-alarm probability. To estimate the value of ¡ ¢ ¨ § ¢ § , we performed an estimation of the random vari- able

# ¨© I QP I I !¡ ¨ ¥ £ ¨ ¨ § assuming that © © .
With the assumption that # is represented by a sum of independent elements (due to the correlation), we decided to express the distribution of # as a gaussian law ¡ ¥ ¡ § , and ¡ representing respectively the mean and variance estimation of # . The probability density D © ¡ G" § of a gaussian element 1 is given by:

D © ¡ ¤" § © ¡ ¡ ¥ ¦@ ! T ¥ % " T " ¡ & # (30)
To ical probability densities is good (cf Fig. 20). The law of the random variable 1 is consequently given by:

¢ ¡ # u £ § © % " T " ¡ & (31)
where

¡ G" § © § W D © ¡ ¤" § (32)
Using 100 different keys for each triangle of a given tes- II).

¡ ¢ § ¢ § is then computed from £ ¡ using the relation:

¡ ¢ § ¢ § © ¨$ £ ¡ Y £ (33)
The parameter ¨corresponds to a normalized gaussian law. Table III represents different values ¡ ¢ § ¢ § depend- ing on the false alarm probability.

7) A global decision is obtained using the global sum of

I QP I I ¡ ¨ 8 £ ¨ § .
The mean of the correlation calculated for each triangle of the tessellation allows also signature detection inside the image. In the case of a value greater than a threshold, the mark is detected. We used the mean of the correlation to obtain a new statistic named :

$© ¨ ¥ "! "! "! ¥ © I pP I RI ¡ ¨ 8 £ ¨ § (34)
It is a well-known result that can be expressed by an empirical gaussian law of mean

£ $# © £ and variance £ ¡ # © £ ¡ ) ¨.
In addition, the mark can be also detected if:

! ¡ ¢ ¨ § ¢ § ¨(35)

C. Evaluation and Comparison

The objective of this section is to show the capability of the algorithm to achieve good detection efficiency after geometrical transformations and classical process. Ours tests were processed on 12 different images representing different classes of contents. The test database is depicted in Fig. 22 We tested the detector using a wide class of geometrical distortions and classical image processing operations (Jpeg compression and print and scan). Here is the list of the different process:

¢ the Stirmark distortion: this attack leads to a geometrical distortion that cannot be modelled by an affine transform on the whole image(cf section II-A). We have used the Stirmark 3.0 algorithm.

¢

Shearing transformation: we use the Gimp software to perform this transformation [START_REF] Cutts | An introduction to the gimp[END_REF]. This filter can be considered as an affine transform.

¢

Scaling transform: we perform a scaling operation of 80%.

¢ Rotation: we evaluated the robustness of the presented scheme for a rotation of ¡ t .

¢

Print and Scan: the print and scan test consists in printing the marked image on a classical laser printer and scanning it. In our test we used a 300 300 greyscale printer and a 300ppi scanner.

¢ JPEG compression: this compression scheme is one of the most used over the Internet. We have evaluated our scheme for a quality factor equal to 50%. In this case, the compressed image has blocking artefacts.

Detection results are given on table IV. They indicate whether the global detection was successfully performed on the marked image or not. A false-alarm probability equal to ¡ W has been chosen. We also present the detection result obtained using the Digimarc watermarking tool available on Photo-shop5.0. This commercial product is known for his robustness to a various category of filter. It uses template embedding to recover synchronisation after geometrical transformations [START_REF] Geoffrey | Photographic products and methods employing embedded information[END_REF].

1) StirMark: Our results illustrate the fact that the presented scheme is robust against the StirMark attack, the mark Figure 24 outlines the tessellation evolution on the marked and attacked image 2 . We can notice that the tessellation mainly follows the geometrical distortion; this permits consequently the detection of the mark.

2) Shearing transformation: The detection results (given on table IV) show the capacity of the presented method to detect the mark after the shearing transformation. Once again, the Digimarc synchronisation scheme could not handle this transformation and the embedded signature using Digimarc could not be detected. An example of the evolution of the tessellation is given on Fig 25.

3) Scaling operations: Except for the baboon image, the signature has been detected after a scaling operation of 80%. The defeat of the mark detection for the baboon image is due to the presence of a large noisy area having similar content properties (located on the fur). Such a high frequency similar pattern is a drawback for content-based feature points detectors because the detector cannot classify the different feature points. The evolution of the tessellation on the bridge image after a scaling operation of 0.8 is illustrated on Figure 26.

4) Rotations:

This test demonstrates the capacity of the presented technique to detect the signature after slight rotations ( ¡ t in the test). Furthermore it is important to point out that ¦¡ t rotations or horizontal and vertical symmetries do not modify the tessellation, and consequently the signature can be detected in these cases. Figure 27 outlines the tessellation evolution after a ¡ !t rotation on the marked image peppers.

5) Print and Scan process:

The Print and Scan test is drastic because it combines multiple attacks. Printing induces requantization of the grey-levels and a grid apparition. Scanning results in slight geometrical distortions and noise addition. Results (cf Table IV) illustrates the fact that our content based method permits the detection of the signature on the majority ¡ Triangles where the detection of the mark was detected are represented by a white centre of gravity. of the images. Once again, the feature points detector is not efficient for images having not well defined content (baboon, tank, water). Figure 28 illustrates the modification of the tessellation applied on the marked image plane after the Print and Scan process. We can notice the way the image is degraded and the tessellation modification.

6) JPEG compression:

The robustness to JPEG compression is achieved for a quality factor equal to 50%. This fact is mainly due to the use of a low-pass filter before feature points detection. Figure 29 illustrates the tessellation change after JPEG compression on the mark lena image. A few triangles of the tessellation have been modified but the mark can be detected inside preserved triangles.

VI. CONCLUDING REMARKS

We proposed in this paper a new watermarking approach based on images content. The presented technique is included in the class of second generation schemes [START_REF] Kutter | Towards second generation watermarking schemes[END_REF] which leads to numerous advantages: ¢ the original image is not needed for the detection of the mark, ¢ content-based techniques permit automatic resynchronization of the mark after both local (StirMark, shearing) and global (rotations, scaling) geometrical transformations, ¢ the orientation of the signature is carried by the content of the image and consequently cannot be erased, ¢ they don't rely on template embedding that can be easily removed [START_REF] Voloshynovskiy | Watermark template attack[END_REF]. .

Our study outlines the different advantages and the limits of this kind of methods. Contrary to the Digimarc solution, the presented technique is robust to the StirMark attack, shearing distortion, Jpeg compression and slight global transformations but the robustness of the scheme depends on the capacity of the feature point detector to preserve feature point after geometrical transformation, especially on highly textured images. The development of a content-bound techniques leads to numerous perspectives. The next step of this work is the use of content-based schemes for video objects and MPEG-4 watermarking. In this context, the content descriptor can be provided by segmentation tools. Consequently, information about the orientation and the scale of the object can be provided by analysing the object shape. This operation allows the detection of the signature after object manipulations such as rotations or scaling operations. Preliminary works are referenced in [START_REF] Bas | Robust watermarking of video objects for mpeg-4 appli-ICASSP'99[END_REF].

Fig. 1 .

 1 Fig. 1. Outline of the presented content-based watermarking sheme.

¢

  techniques using periodical sequences, ¢ techniques using templates insertions, ¢ techniques using invariant transforms, ¢ techniques using the original image.

Fig. 2 .

 2 Fig.2. Effect of the StirMark3.0 attack: the original image is on the left and the attacked image is on the right. By focusing observation on the grid, it is easy to distinguish the geometric distortions. Without the grid, the distortions are not noticeable, but this attack can defeat many watermarking schemes.

Fig. 3 .

 3 Fig. 3. Cyclic generation of the mark proposed by Delannay and Macq.

Fig. 4 .

 4 Fig. 4. On the left: the marked image is divided in blocks, the detection of the mark is performed on each block. On the right: several windows generated by the 4-parameter correlation.

FigFig. 5 .

 5 Fig. 5. Principle of the synchronization scheme provided by Kutter. The cross-correlation computation of the marked image allows the identification of the affine transform.

Fig. 6 .

 6 Fig. 6. Principle of template insertion: each template is embedded in the Fourier domain in middle frequencies of the image (upper part of the figure). The identification of the affine transform is performed after a search of template location (lower part of the figure).

( 2 )Fig. 7 .

 27 Fig.7. Composition of transforms used to obtain a rotations, translations and scaling invariant embedding domain. FFT and IFFT denote respectively the Fast Fourier Transform and its inverse. LPM and ILPM denote respectively the log-polar mapping and its inverse.

Fig. 8 .

 8 Fig. 8. Left image: original image with triangular tessellation. Right image: image attacked by StirMark after geometrical compensation. Each vertex of the tessellation is slightly moved to minimize quadratic error between each original triangle and the corresponding attacked triangle (right figure).

Fig. 9 .

 9 Fig. 9. Principle of a content based watermarking schemes.

Fig. 11 .

 11 Fig. 11. Self spanning pattern generation.

Fig. 12 .

 12 Fig. 12. Harris detector response.

Fig. 13 .

 13 Fig. 13. SUSAN detector principle.

¢ 5

 5 Jpeg compressions with a 90 £ down to 50 £ quality factor.

Fig. 14 .

 14 Fig. 14. Blurring filtering and the robustness of the Harris detector.

Fig. 15 .

 15 Fig. 15. parameter effects.

Fig. 16 .

 16 Fig. 16. Behavior of the selected detectors towards our benchmark for the different test images.

  tessellation of the set ¢ is defined to be the unique triangulation of the convex cover of ¢ such as the interior of the containing circle § B¡ £

Fig. 17 .

 17 Fig. 17. Orientation of the triangle.

Fig. 18 .

 18 Fig. 18. Embedding process in our proposed watermarking scheme.

Figure 19 Fig. 19 .

 1919 Figure 19 represents effects of Wiener filtering.

Fig. 20 .

 20 Fig. 20. Histogram of the value of correlation, in which the detection key is different from the insertion key. The results were obtained by using 100 keys per triangle. The continuous curve represents a gaussian probability density. sellation, we have computed the estimate of the mean £

8 )Fig. 21 .

 821 Fig. 21. Principle of the detection process

Fig. 23 .

 23 Fig. 23. Representation of tested geometrical distortions applied on a grid

Fig. 24 .Fig. 25 .Fig. 26 .

 242526 Fig. 24. Effect of the StirMark3.0 attack on the marked water image. Global and Local detection have succeeded.

  Template insertion can address both local and global transformations, but

		Local transformation Global transformation	notes
		robustness	robustness
	Periodic insertion	no	yes	-
	Template insertion	no	yes	can be removed
	Invariant transform	no	yes	-
	Non-blind	yes	yes	computational cost

TABLE I COMPARISON

 I OF THE PRESENTED METHODS.

  different processes.

	¢ 10 rotations with different angles (¥ ¡ ¡ t , ¥ ¡ Et , §¡ Et , ¡ t , yx ¦¡ Et , ¥ ¡ ¡ t et ¥ ¥ ¡ t , ¦¡ t , ¡ Et ). We ap-¡ Et , x ¦¡ Et ,

plied after each rotation an inverse rotation to compute the score.

TABLE III ¥

 III §¦ © FOR DIFFERENT FALSE RESPONSE PROBABILITIES.

  . Various categories of images have been chosen. Images baboon, lake, elaine, bridge include textured areas with high frequency components while the other images (plane, tank,

	plane		baboon		tank		lake			elaine		lena
	drop		car			bridge		water			peppers		boat
	Fig. 22. Images used in our tests.
			plane	baboon	tank	lake	elaine	lena	drop	car	bridge	water	peppers	boat
	Stirmark	C.B.S.	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK
		Digimarc	Defeat Defeat	Defeat Defeat Defeat Defeat Defeat Defeat Defeat Defeat	Defeat	Defeat
	Shearing	C.B.S.	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK	OK
		Digimarc	Defeat Defeat	Defeat Defeat Defeat Defeat Defeat Defeat Defeat Defeat	Defeat	Defeat
	Rot. ¢¡ ¤£

C.B.S. OK OK OK OK OK OK OK OK OK OK OK OK Digimarc OK OK OK OK OK OK OK OK OK OK OK OK Scal. 80% C.B.S. OK Defeat OK OK OK OK OK OK OK OK OK OK Digimarc OK OK OK OK OK OK OK OK OK OK OK OK Scanning C.B.S. OK Defeat Defeat OK OK OK OK OK OK Defeat OK OK Digimarc OK OK OK OK OK OK OK OK OK OK OK OK JPEG 50% C.B.S. OK OK OK OK OK OK OK OK OK OK OK OK Digimarc OK OK OK OK OK OK OK OK OK OK OK OK

Original image Marked image and and tessellation

Jpeg compression (50%)