Quentin Bammey

Tina Nikoukhah

Marina Gardella

Rafael Grompone Von Gioi

Miguel Colom

Jean-Michel Morel

Non-Semantic Evaluation of Image Forensics Tools: Methodology and Database

We propose a new method to evaluate image forensics tools, that characterizes what image cues are being used by each detector. Our method enables effortless creation of an arbitrarily large dataset of carefully tampered images in which controlled detection cues are present. Starting with raw images, we alter aspects of the image formation pipeline inside a mask, while leaving the rest of the image intact. This does not change the image's interpretation; we thus call such alterations "non-semantic", as they yield no semantic inconsistencies. This method avoids the painful and often biased creation of convincing semantics. All aspects of image formation (noise, CFA, compression pattern and quality, etc.) can vary independently in both the authentic and tampered parts of the image. Alteration of a specific cue enables precise evaluation of the many forgery detectors that rely on this cue, and of the sensitivity of more generic forensic tools to each specific trace of forgery, and can be used to guide the combination of different methods. Based on this methodology, we create a database and conduct an evaluation of the main state-of-the-art image forensics tools, where we characterize the performance of each method with respect to each detection cue. Check qbammey.github.io/trace for the database and code.

GALILEO: How would it be if your Highness were now to observe these impossible as well as unnecessary stars through this telescope? THE MATHEMATICIAN: One might be tempted to reply that your telescope, showing something which cannot exist, may not be a very reliable telescope, eh?

Introduction

Digital images play an extensive role in our lives and forgeries are present everywhere [START_REF] Farid | Photo Forensics[END_REF]. Creating visually realistic image alterations is easy. Yet each modification of the image imprints traces onto it, that are cues of the tampering. Some forgery detection tools aims at detecting a specific trace in a suspicious image by finding local inconsistencies, while other methods, usually learning-based, are more generic. Semantic analysis of an image can provide hints, but the rigorous proof of a forgery should not be Work funded by French Ministère des Armées -Direction Générale de l'Armement and Région Île-de-France. (g) Noiseprint [START_REF] Cozzolino | Noiseprint: A cnnbased camera model fingerprint[END_REF] result (h) ManTraNet [START_REF] Wu | Mantra-net: Manipulation tracing network for detection and localization of image forgeries with anomalous features[END_REF] result solely semantic. The situation is akin to the dilemma arising from the observations of Galileo, which contradicted the knowledge of his time. In the words of Bertolt Brecht [START_REF] Brecht | The Life of Galileo[END_REF]:

The telescope could have been unreliable, indeed, and a scientific inquiry on the instrument could have been justified. However, concluding, as the Mathematician does, that the telescope was unreliable just based on the contents of the observations is not prudent. Similarly, the proof of a forgery must be based on image traces, not on semantic arguments, because the semantics of an image are usually the purpose and not the means of a forgery. Image forensics algorithms are mainly evaluated by their performance in benchmark challenges. This practice has several limitations: in many cases, the same database is split into training and evaluation data. As a consequence, algorithms are trained and evaluated on images that have gone through similar image processing pipelines, forgery algorithms and anti-forensic tools. Hence, there is no guarantee that such learning-based methods will work in the wild, where those parameters vary much more. Regardless of the variety of the training set, the question arises of whether the forgeries are being detected by trained detectors for semantic reasons, or because of local inconsistencies in the image.

With these considerations in mind, we propose a methodology and a database to evaluate image forensic tools on images where authentic and forged regions only differ in the traces left behind by the image processing pipeline. Using this methodology, we create the Trace database by adding various forgery traces to raw images from the Raise [START_REF] Dang-Nguyen | Raise: A raw images dataset for digital image forensics[END_REF] dataset, as shown in Fig. 1. This procedure avoids the difficulties of producing convincing and unbiased semantic forgeries, which often requires manual work. We create several datasets, each of which corresponding to a specific pipeline inconsistency, such as a different noise level or compression pattern. This gives us insight into the sensitivity of forensic tools to specific traces, and thus highlights the complementarity of different methods.

Our contribution is twofold: 1. we create a database of "fake" images with controlled inconsistencies in their formation pipeline, 2. using this database, we conduct an evaluation of existing forensic tools.

Related Works

There is a large literature on image forensics, starting from the seminal work of Farid [START_REF] Farid | Photo Forensics[END_REF]. Some methods focus on the detection of a specific tampering attack such as copy-move or splicing, but the most classic forgery detection methods aim at detecting local perturbations of the traces left in the image by the processing chain. Such local disruptions hint at a local forgery. To do so, these methods strive to suppress image content and highlight intrinsic artefacts left by demosaicking, JPEG encoding, etc. [START_REF] Alin | Statistical tools for digital forensics[END_REF]. These forgery detection methods can therefore be grouped by their specifically-targeted traces, which we now briefly review.

Noise-level-based methods analyse the noise model of images (see Section 3) to find regions with a different amount of noise, that could result from tampering. Mahdian and Saic [START_REF] Mahdian | Using noise inconsistencies for blind image forensics[END_REF] perform local wavelet-based noise level estimation using a median absolute deviation estimator. Lyu et al. [START_REF] Lyu | Exposing region splicing forgeries with blind local noise estimation[END_REF] relies on the kurtosis concentration phenomenon. More recently, Noisesniffer [START_REF] Gardella | Noisesniffer: a fully automatic image forgery detector based on noise analysis[END_REF] defines a background stochastic model enabling the detection of local and statistically-significant noise anomalies. These methods can potentially detect a relatively wide variety of forgeries, as each can alter the noise level. Detecting the specific image demosaicing algorithm (see Section 3) has not been attempted since the 2005 pioneer paper by Popescu and Farid [START_REF] Popescu | Exposing digital forgeries in color filter array interpolated images[END_REF], conceived at a time where those algorithms were simpler and easier to distinguish, although some generic noise-pattern analysis method can distinguish different algorithms given large enough regions [START_REF] Cozzolino | Noiseprint: A cnnbased camera model fingerprint[END_REF]. However, detecting the mosaic pattern has received more extensive coverage. Choi et al. [START_REF] Choi | Cfa pattern identification of digital cameras using intermediate value counting[END_REF] used the fact that sampled pixels were more likely to take extremal values, while Shin et al. [START_REF] Shin | Color filter array pattern identification using variance of color difference image[END_REF] noticed that they had a higher variance. Bammey et al. [START_REF] Bammey | An adaptive neural network for unsupervised mosaic consistency analysis in image forensics[END_REF] combined the translation invariance of convolutional neural networks with the periodicity of the mosaic pattern to train a self-supervised network into implicitly detecting demosaicing artefacts. Because demosaicing artefacts lie in the high frequencies, they are lost under a strong JPEG compression or when the image has been downsampled. As such, they are usually best used on high-quality images.

JPEG compression leaves blocking effects and quantization of the DCT coefficient of each block. JPEG forensic tools can thus be divided into two categories. BAG [START_REF] Li | Passive detection of doctored jpeg image via block artifact grid extraction[END_REF] and CAGI [START_REF] Iakovidou | Content-aware detection of jpeg grid inconsistencies for intuitive image forensics[END_REF] analyse blocking artefacts, while other methods analyse the DCT coefficients. More precisely, CDA [START_REF] Lin | Fast, automatic and fine-grained tampered jpeg image detection via dct coefficient analysis[END_REF] and I-CDA [START_REF] Bianchi | Improved dct coefficient analysis for forgery localization in jpeg images[END_REF] are based on the AC coefficient distributions, while FDF-A [START_REF] Amerini | Splicing forgeries localization through the use of first digit features[END_REF] is based on the first digit distribution of AC coefficients. Zero [START_REF] Nikoukhah | Jpeg grid detection based on the number of dct zeros and its application to automatic and localized forgery detection[END_REF] counts the number of null DCT coefficients in all blocks and deduces the grid origin. These methods can only work when the forgery was done after a first JPEG compression. And when this is the case, they usually yield very good results.

In the past few years, multi-purpose tools were proposed to detect inconsistencies from multiple traces simultaneously. Splicebuster [START_REF] Cozzolino | Splicebuster: A new blind image splicing detector[END_REF] uses the co-occurences of noise residuals as local features revealing tampered image regions. Noiseprint [START_REF] Cozzolino | Noiseprint: A cnnbased camera model fingerprint[END_REF] extends on Splicebuster and uses a Siamese network trained on authentic images to extract the noise residual of an image, which is then analysed for inconsistencies. ManTraNet [START_REF] Wu | Mantra-net: Manipulation tracing network for detection and localization of image forgeries with anomalous features[END_REF] is a bipartite end-to-end network, trained to detect image-level manipulations with one part, while the second part is trained on synthetic forgery datasets to detect and localise forgeries in the image. Finally, Self-consistency [START_REF] Huh | Fighting fake news: Image splice detection via learned self-consistency[END_REF] analysis also uses a Siamese network with the goal of detecting whether two patches have been processed with the same pipeline. They make use of N-Cuts segmentation [START_REF] Shi | Normalized cuts and image segmentation[END_REF] to automatically cluster and detect relevant traces of forgeries. With these methods, exhaustiveness is theoretically possible. However, results are not self-explanatory and those method's decisions are harder to justify. Furthermore, learning-based methods can be limited by the training data, and may fail to generalize well in uncontrolled scenarios.

There is also considerable literature proposing datasets for the evaluation of forensic tools. An early example is the Columbia Dataset [START_REF] Ng | A data set of authentic and spliced image blocks[END_REF], which only contains spliced 128 × 128 grayscale blocks for which no masks are provided. New benchmarks were proposed in 2009 with CA-SIA V1.0 and V2.0 [START_REF] Dong | Casia image tampering detection evaluation database[END_REF]. These datasets included splicing and copy-move attacks, with a total of 8000 pristine images and 6000 tampered images. Post-processing was introduced as a counter-forensics technique. MICC F220 and F2000 datasets [START_REF] Amerini | A SIFT-based forensic method for copy-move attack detection and transformation recovery[END_REF] as well as the IMD dataset [START_REF] Christlein | An evaluation of popular copy-move forgery detection approaches[END_REF] provide further benchmarks for copy-move detection. These datasets were constructed in an automatic way. While the first two randomly select the region of the image to be copy-pasted, IMD dataset performed snippets extraction. Other datasets adressing copy-move forgeries with postprocessing counter attacks are also available [START_REF] Tralic | Comofodnew database for copy-move forgery detection[END_REF][START_REF] Wen | Coverage -a novel database for copy-move forgery detection[END_REF].

Image forgery-detection challenges are another source of benchmark datasets. The National Institute of Standards and Technology (NIST) organizes, since 2017, an annual challenge for which different datasets are released [START_REF] Guan | Mfc datasets: Large-scale benchmark datasets for media forensic challenge evaluation[END_REF]. It includes automatically and manually generated forgeries of considerable variety, and can thus be useful to evaluate image forgery detection in uncontrolled scenarios.

Some datasets aim at performing forgeries imperceptible to the naked eye. A good example is the Korus dataset [START_REF] Korus | Evaluation of random field models in multi-modal unsupervised tampering localization[END_REF][START_REF] Korus | Multi-scale analysis strategies in prnu-based tampering localization[END_REF] which contains 220 pristine images and 220 handmade tampered images targeting object removal or insertion.

The recent DEFACTO dataset [START_REF] Mahfoudi | Defacto: Image and face manipulation dataset[END_REF] is constructed on the MSCOCO dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] and includes a wide range of forgeries such as copy-move, splicing, inpainting and morphing. Semantically meaningful forgeries are generated automatically but with several biases such as copy-pasting objects in the same axis or only performing splicing with simple objects.

Most recent forgery-detection datasets start from pristine images and perform several sorts of forgeries on them [START_REF] Zheng | A survey on image tampering and its detection in real-world photos[END_REF]. Since the creation of early datasets [START_REF] Dong | Casia image tampering detection evaluation database[END_REF][START_REF] Hsu | Detecting image splicing using geometry invariants and camera characteristics consistency[END_REF][START_REF] Ng | A data set of authentic and spliced image blocks[END_REF], the number of tampering techniques has increased to include new ones such as colorization [START_REF] Castro | A dataset of 1050-tampered color and grayscale images (cg-1050)[END_REF], inpainting [START_REF] Castro | A dataset of 1050-tampered color and grayscale images (cg-1050)[END_REF][START_REF] Mahfoudi | Defacto: Image and face manipulation dataset[END_REF] and morphing [START_REF] Mahfoudi | Defacto: Image and face manipulation dataset[END_REF][START_REF] Zhou | Twostream neural networks for tampered face detection[END_REF]. Post-processing and counter-forensic techniques have been increasingly used to produce visually imperceptible forgeries; but such approaches may also introduce detectable traces.

Efforts have also been made to automatically obtain large datasets. Yet, the resulting forged images are either seman- tically incorrect [START_REF] Amerini | A SIFT-based forensic method for copy-move attack detection and transformation recovery[END_REF][START_REF] Christlein | An evaluation of popular copy-move forgery detection approaches[END_REF] or biased [START_REF] Mahfoudi | Defacto: Image and face manipulation dataset[END_REF]. Both scenarios pose problems for training neural networks, which risk overfitting on the forgeries' methods and semantic content.

The variety of forgery methods makes the evaluation of forensic tools difficult to interpret, as the performance depends on the suitability of the detection tool for the specific forgery method. In quantitative experiments, using multiple datasets, and especially datasets with varied forgeries, helps assess the quality of a forensic tool. However, those results also become harder to interpret. On the other hand, while results using the proposed database will not be reflective of uncontrolled scenarios, they help precisely identify which traces a forensic tool can and cannot detect.

Image formation pipeline

Figure 2 summarises the image processing pipeline [START_REF] Delbracio | Mobile computational photography: A tour[END_REF] and shows how the noise curves change at its different steps.

Raw image acquisition

The value at each pixel can be modelled as a Poisson random variable [START_REF] Foi | Practical poissonian-gaussian noise modeling and fitting for single-image raw-data[END_REF]. Noise vari-ance at this step thus follows an affine relation σ 2 = A+Bu where u is the intensity of the ideal noiseless image and A and B are constants (see Fig. 2). Furthermore, given the nature of the noise sources at this step, noise can be accurately modelled as uncorrelated, meaning that noise at one pixel is not related with the noise at any other pixel.

Demosaicing Most digital cameras are equipped with a single sensor array. In order to obtain a colour image, a colour filter array (CFA) is placed in front of the sensor to split incident light components according to their wavelength. The raw image obtained from the sensor therefore is a mosaic containing a single colour component per pixel: red, green, or blue. Demosaicing methods interpolate the missing colours at each pixel to reconstruct a full colour image. After demosaicing (Fig. 2), each channel has a different noise curve, and noise becomes spatially correlated.

Colour Correction In order to obtain a faithful representation of the colours as perceived by the observer, white balance adjusts colour intensities in such a way that achromatic objects from the real scene are rendered as such [START_REF] Losson | From the Sensor to Color Images[END_REF]. This is done by scaling each channel separately, thus also scaling differently the noise level of each channel. Given that the relationship between stimulus and human perception is logarithmic [START_REF] Gt Fechner | Elemente der psychophysik, breitkopf und härtel[END_REF], cameras then apply a power law function to the intensity of each channel. After this step, known as gamma correction, the noise level is no longer monotonously increasing with the intensity.

JPEG compression

The JPEG image standard is the most popular lossy compression scheme for photographic images [START_REF] Gregory | The jpeg still picture compression standard[END_REF]. The image goes through a colour space transformation and each channel is partitioned into non-overlapping 8 × 8-pixel blocks. The type-II discrete cosine transform (DCT) is applied to each of these blocks. The resulting coefficients are quantized according to a table and the coefficients are then compressed without additionnal loss. Due to the cancellation of high-frequency coefficients, the noise is reduced after compression.

The Proposed Methodology

We created a database of "forged" images which leaves the semantics of the images intact. The overall idea of our method is to take a raw image, process it with two different pipelines, and merge the two processed images as follows: the first image is used for the authentic region and the second image for the "forged" area determined by a mask, as can be seen in Fig. 1. As a base we use the RAISE-1k dataset [START_REF] Dang-Nguyen | Raise: A raw images dataset for digital image forensics[END_REF], which contains one thousand pristine raw images of varied categories, taken from three different cameras. We note that the variety of source cameras is not important to our database, as we erase the previous camera traces by downsampling the image, then resimulate the whole image processing pipeline ourselves, as explained Figure 3: Details of the same image with forgeries made using the two masks. On the left, the endomask coincides with the image's structure, here a tree. The forgery is less conspicuous than on the right where the exomask is in the sky, where the borders do not coincide with the images' content. below. Furthermore, our open source generation code can be applied on any other source of images, to automatically generate arbitrarily large quantities of "forged" images.

Methodology for the creation of the database A raw image already contains noise, furthermore its pixels are all sampled in the same CFA pattern. In order to reduce the noise and eliminate the CFA pattern, we start by downsampling each image by a factor 2. This enables us to choose the amount of noise to be added, and to mosaic the image in any of the four possible patterns. Once the image has been downsampled, we process the image with two different pipelines. The two images are then merged as explained above.

Forgery masks For each image we construct two different kinds of masks, which we shall call endomasks and exomasks. Since inconsistencies in the image processing pipeline are usually most visible at the border of the forgery, endomasks are obtained as regions of a segmentation of the image. To do this, we segment the original images with EncNet [START_REF] Zhang | Context encoding for semantic segmentation[END_REF]. For each image, we take a pixel at random, and select the image region it belongs to. We accept the mask if its size is less than half the image's, otherwise we pick another pixel until we find a suitable mask. This ensures that each image has only one forgery, whose size is at most half the image's. Using such endogenous masks or endomasks corresponding to a region of the segmented image ensures almost invisible forgeries. Indeed their borders are natural image borders, as shown in Fig. 3.

The exomasks are instead unrelated to the image's content. To determine them, we start by pairing the images of the dataset according to their endomasks' sizes. Then, the Endomask Image Exomask endomask of each image is used as the exogenous mask, or exomask, of its paired image. Using a mask from another image ensures that the mask is not linked to the image's semantic. The chosen pairing enables comparisons separately on each image, as the size of the masks is similar. See Fig. 4 for examples of endo-and exomasks.

Multiple datasets One of our goals is to determine which inconsistencies each forensic tool is sensitive to. Changes in the image processing pipeline, done at different steps of the chain, lead to different inconsistencies (see Section 3).

In consequence, we created five specific datasets, each of which features a specific change in the image processing pipeline. For each image, we started by randomly choosing the three parameters that are used for this image across all datasets:

• The mosaic pattern, chosen among the four possible offsets of the camera's Bayer pattern.

• The demosaicing algorithm, chosen randomly among those available in the LibRaw library [1].

• The gamma-correction power.

The gamma correction is the same for both regions of the image, and the mosaic pattern is the same except for the CFA Grid, CFA Algorithm and Hybrid datasets. For each image, both the endo-and exomasks, constructed as explained above, are the same across all datasets.

Raw Noise Level dataset In this dataset we add random noise to each raw image before processing it. As pointed out in Section 3, noise variance in raw images follows a linear relation given by σ 2 = A + Bu, where A and B are constants and u is the noiseless image. We start by randomly selecting two different pairs of constants (A 0 , B 0 ) and (A 1 , B 1 ), in a range that ensures the resulting images look natural. Both images are then processed with the same pipeline. This dataset mimics the inconsistencies in noise models that could be found in spliced images.

CFA Grid dataset In this dataset we only change the mosaic pattern of the forged image inside the mask. Thus, the original image and the forged one would be identical if not for their mosaic grid origins. This kind of trace may appear (with probability 3 4 ) when the forgery was an internal copy-move.

CFA Algorithm dataset In this dataset, the two processing pipelines use different demosaicing algorithms. The demosaicing pattern is chosen independently for each pipeline. Thus there is a 1 4 chance that they are aligned. A new mosaic pattern is also randomly chosen, thus having a 3 4 chance of being different from the one of the main image. This dataset represents the change in the mosaic that would occur from splicing, as two different images most likely do not share the same demosaicing algorithms, and the alignment of their patterns after splicing is random.

JPEG Grid dataset

In this dataset we only change the compression grid origin. Similarly to the CFA Grid dataset, if the forgery is an internal copy-move, the JPEG grid of the forged region is different from the grid in the authentic region, with probability 63 64 . The JPEG compression quality used in both pipelines is then chosen randomly, keeping the values in a range that is typical of most compressed images and challenging enough for JPEG-based algorithms.

JPEG Quality dataset In this dataset, both the authentic and forged regions are processed with the same pipeline, except for the JPEG compression which is done in the two regions with different quality factors, again chosen uniformly between 75 and 100. Like with the CFA Algorithm dataset or the JPEG grid data, a new JPEG grid pattern is also randomly chosen, which has a 63 64 chance of being different from the main region's grid. This dataset simulates the effect of the splicing of an image onto another, both images being compressed at different quality factors.

The hybrid dataset One could argue that although generic learning-based forensics tools may not be able to point out a single inconsistency in an image, they might be best suited to find multiple inconsistencies stacked together. Clearly, a splicing may introduce joint inconsistencies in noise level, JPEG encoding and demosaicing; while a direct copy-move can introduce alterations in the JPEG and CFA grids. To investigate such possibilities, in addition to the five specific datasets described above, we created a sixth, hybrid dataset. In this dataset, forgeries combine noise, demosaicing and/or JPEG compression traces. At least two of those traces are altered in each images.

See the supplementary materials for more details on the parameters selection.

Experiments

Evaluated methods

We used the constructed database to conduct an evaluation of image forensics tools. We tested both classic and SOTA forgery detection methods pertaining to different traces: noise-level-based detection methods Noisesniffer [START_REF] Gardella | Noisesniffer: a fully automatic image forgery detector based on noise analysis[END_REF], Lyu [START_REF] Lyu | Exposing region splicing forgeries with blind local noise estimation[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF] and Mahdian [START_REF] Mahdian | Using noise inconsistencies for blind image forensics[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF]; CFA-grid detection methods Bammey [START_REF] Bammey | An adaptive neural network for unsupervised mosaic consistency analysis in image forensics[END_REF], Shin [START_REF] Shin | Color filter array pattern identification using variance of color difference image[END_REF] and Choi [START_REF] Bammey | Image Forgeries Detection through Mosaic Analysis: the Intermediate Values Algorithm[END_REF][START_REF] Choi | Cfa pattern identification of digital cameras using intermediate value counting[END_REF]; JPEG-based methods Zero [START_REF] Nikoukhah | Jpeg grid detection based on the number of dct zeros and its application to automatic and localized forgery detection[END_REF], CAGI [START_REF] Iakovidou | Content-aware detection of jpeg grid inconsistencies for intuitive image forensics[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF], FDF-A [START_REF] Amerini | Splicing forgeries localization through the use of first digit features[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF], I-CDA [START_REF] Bianchi | Improved dct coefficient analysis for forgery localization in jpeg images[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF], CDA [START_REF] Lin | Fast, automatic and fine-grained tampered jpeg image detection via dct coefficient analysis[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF] and BAG [START_REF] Li | Passive detection of doctored jpeg image via block artifact grid extraction[END_REF][START_REF] Zampoglou | Large-scale evaluation of splicing localization algorithms for web images[END_REF], as well as generic methods Splicebuster [START_REF] Cozzolino | Splicebuster: A new blind image splicing detector[END_REF], Noiseprint [START_REF] Cozzolino | Noiseprint: A cnnbased camera model fingerprint[END_REF], ManTraNet [START_REF] Wu | Mantra-net: Manipulation tracing network for detection and localization of image forgeries with anomalous features[END_REF] and Self-Consistency [START_REF] Huh | Fighting fake news: Image splice detection via learned self-consistency[END_REF].

Evaluation Metrics

We evaluated the results of these methods using the Matthews correlation coefficient (MCC) [START_REF] Matthews | Comparison of the predicted and observed secondary structure of t4 phage lysozyme[END_REF]. This metric varies from -1 for a detection that is complementary to the ground truth, to 1 for a perfect detection. A score of 0 represents an uninformative result and is the expected performance of a random classifier. The MCC is more representative than the F1 and IoU scores [START_REF] Chicco | Ten quick tips for machine learning in computational biology[END_REF][START_REF] Chicco | The advantages of the matthews correlation coefficient (mcc) over f1 score and accuracy in binary classification evaluation[END_REF], partly as it is less dependant on the proportion of positives in the ground truth, which is especially important given the large variety of forgery mask sizes in the database.

The MCC was computed for each image, and then averaged over each dataset. As most surveyed methods do not provide a binary output but a continuous heatmap, we weighted the confusion matrix using the heatmap. See the supplementary materials for more details, as well as for the score tables with the F1 and IoU metrics.

Results

The complete results are given in Table 1. Visualization of the detection by several methods on one image across all datasets can be seen in Figure 5. In the CFA and JPEG datasets, state-of-the-art methods that focus on those specific traces, such as Bammey [START_REF] Bammey | An adaptive neural network for unsupervised mosaic consistency analysis in image forensics[END_REF] for CFA and ZERO [START_REF] Nikoukhah | Jpeg grid detection based on the number of dct zeros and its application to automatic and localized forgery detection[END_REF] for JPEG, perform much better than generic tools. This is partly expected, as those methods aim to detect exactly this specific trace. This observation is more nuanced in the Noise Level dataset where, depending on the type of mask considered, Noisesniffer [START_REF] Gardella | Noisesniffer: a fully automatic image forgery detector based on noise analysis[END_REF] and Self-Consistency [START_REF] Huh | Fighting fake news: Image splice detection via learned self-consistency[END_REF] achieve the best results. Indeed, exomasks cover a wider range of intensities enabling a better comparison between noise models, which is exploited by Noisesniffer. Also, half of the forgeries present in this database are undetectable for this method since it is only able to detect forgeries having lower noise levels.

On the hybrid dataset, the scores of the specific methods are lower than on the specific datasets. For the JPEGbased methods, this is explained by the fact that one sixth of this dataset does not feature JPEG compression traces. For the CFA and Lyu and Mahdian noise-based methods, this is made worse by the fact that JPEG compression alters the previous noise and demosaicing artefacts, as shown in Fig. 2. In particular, CFA-based methods are notoriously weak on JPEG images, since JPEG compression removes the high frequencies, in which mosaic artefacts lie. This can be seen in Fig. 5, where the CFA-based method Bammey cannot make any prediction on the hybrid image, where the main and forged region were compressed with quality factors of 93 and 75, respectively.

While multi-purpose forensic methods can, to some extent, detect noise-level inconsistencies, in the demosaicing algorithm and in the JPEG quality, they are blind to shifts in both the JPEG and CFA grids. This is not entirely surprising; with the exception of Splicebuster, the tested generic tools are based on mostly-convolutional neural networks, which are invariant to translation. Although Noiseprint [START_REF] Cozzolino | Noiseprint: A cnnbased camera model fingerprint[END_REF] adapts its training scheme to be able to detect shifts in periodic patterns, it cannot see the demosaicing and JPEG compression grids, although it is sensitive to JPEG quality inconsistencies and to some extent to demosaicing algorithm changes as well.

Most methods perform similarly on the endomask and exomask datasets. Two notable exceptions are Noisesniffer which underperforms on endomasks, and Self-Consistency, which works much better on endomasks. Both observations are easily explained: the noise model is better estimated by Noisesniffer on a flat region. The same explanation is valid for Noiseprint, which also loses performance with endomasks. In contrast, Self-consistency's content-awareness is lost when segmenting forgeries with exomasks. Regardless of the dataset considered, the scores obtained by all of the methods have a high standard deviation with respect to their mean value. This suggests that, given a dataset, the scores in each individual image are not concentrated around the mean but rather spread on a large range of values. Hence, even for methods having low scores, some good detections are likely to happen.

Dataset

Discussion

Most methods yield similar results on exo-and endomasks. While one kind is usually sufficient, comparing the results on both shows some methods are content-aware.

The goal of this evaluation was not to rank different methods, but to offer a rigorous insight on the capabilities of each. Knowing to which kind of inconsistencies forensic tools are sensitive helps understand and explain its detec-CFA Grid CFA Algorithm JPEG Grid JPEG Quality Hybrid Splicebuster [START_REF] Cozzolino | Splicebuster: A new blind image splicing detector[END_REF] Bammey [START_REF] Bammey | An adaptive neural network for unsupervised mosaic consistency analysis in image forensics[END_REF] ZERO [START_REF] Nikoukhah | Jpeg grid detection based on the number of dct zeros and its application to automatic and localized forgery detection[END_REF] Noiseprint [START_REF] Cozzolino | Noiseprint: A cnnbased camera model fingerprint[END_REF] ManTraNet [START_REF] Wu | Mantra-net: Manipulation tracing network for detection and localization of image forgeries with anomalous features[END_REF] Figure 5: Visualization of the results of several methods for one image on all the datasets. Some methods, such as Noiseprint or Bammey, correctly detect the forgeries in the relevant images, but tend to make noise-like false detections in the images for which they cannot see the forgery. Automatically selecting the relevant detections of an algorithm would make it easier to use without needing interpretation. The image and mask can be seen in Fig. 1.

tions in uncontrolled cases, and can help efforts to combine different methods. In that sense, the proposed database is complementary to more traditional databases.

Even though many methods can yield decent scores, the standard deviations of theses scores over all images of the same dataset is often very high. Even though algorithms perform well on many forgeries, they also often yield false positives that require interpretation to be distinguished from true detections, such as Fig. 1. This phenomenon is further evidenced in the supplementary material. This is a critical point for many methods, as it makes them usable only to a trained eye.

Conclusion

Image forensics datasets are usually grouped according to forgery types (eg. splicing, inpainting, or copy-moves), and do not separate the semantic content from the actual traces left by the forgery. In this paper, we proposed to remove the semantic value of forgeries and to focus only on the traces. We designed a methodology to automatically create image "forgeries" that leave no semantic traces, by introducing controlled changes in the image processing pipeline. We built datasets by focusing on noise-level inconsistencies, mosaic and JPEG artefacts, and conducted an evaluation of some image forensics tools using this dataset.

Although we focused on three kinds of changes in the forgeries, the same methodology can be applied to more traces, including PRNU inconsistencies, multiple compression, or image manipulations such as resampling. In fact, we can address all forgeries where two different camera pipelines are involved. This includes copy-move, splicing and some methods of inpainting. Further work would incorporate other traces, such as those left by synthesis methods. Although not surveyed here, the same methodology can be applied to study robustness of detection under adverse events such as global JPEG compression, by passing the images through compression before analysis. Our images were not post-processed, except for inconsistencies linked to JPEG compression. This makes it easy to assess the robustness to any kind of post-processing. Note that there are no authentic images in the dataset. Testing the frequency of false positives is for now complementary to the proposed methodology, but could be included in further work by comparing the response of forensic tools to the forged images and their authentic counterparts, otherwise-processed with the same pipeline.

Our method can transform automatically large sets of images into forged images with fully controlled tampering cues and no bias that might cause overfitting. Besides evaluation of existing image forensics tools, this methodology could also be used to train forgery detection methods, although care would be needed so as not to overfit if using the same methodology for both training and evaluation.

  (a) Raw image (b) Forgery mask: M (c) Pipeline 0: P0 (d) Pipeline 1: P1 (e) Forgery: F = MP0 + MP1 (f) Residual |F -P0|

Figure 1 :

 1 Figure 1: Different image formation pipelines are applied to the same RAW image to obtain two images, that are combined to obtain a forged image. The authentic and forged regions present different camera pipeline traces, but are otherwise perfectly coherent. The last row shows the result of two forensic tools on this image.

Figure 2 :

 2 Figure 2: Evolution of the noise curves when passing through the successive steps of a (simplified) image processing pipeline.

Figure 4 :

 4 Figure 4: For each image, we use an endomask (left) taken from the image's segmentation, and an exomask (right) taken from another image and thus decorrelated from the image's contents. The last two images were paired during mask creation, thus the endomask of each becomes the exomask of the other.

Table 1 :

 1 Results of different state-of-the-art forensics tools on our six datasets, using the Matthews Correlation Coefficient (MCC), detailed in Sec. 5.2. The methods, on the left, are grouped by categories. As a baseline, a random classifier is expected to yield a score of 0. The mean of the MCC scores over each image of the dataset, as well as the standard deviation in parentheses, are shown for the exogenous mask and endogenous mask datasets. Grayed-out numbers represent results of methods on datasets that are irrelevant to said methods. The best two scores are underlined for each database.

			Noise Level	CFA Grid	CFA Algorithm	JPEG Grid	JPEG Quality	Hybrid
	Noise-level-based	Noisesniffer [21] Lyu [33] Mahdian [34]	0.128 (0.228) 0.128 (0.228) -0.008 (0.070) 0.091 (0.198) 0.091 (0.198) -0.011 (0.073) 0.010 (0.090) 0.010 (0.090) 0.002 (0.093) 0.007 (0.137) 0.007 (0.137) 0.010 (0.157) 0.046 (0.146) 0.046 (0.146) 0.005 (0.082) 0.055 (0.171) 0.055 (0.171) 0.023 (0.159)	0.029 (0.153) 0.005 (0.111) 0.002 (0.094) 0.009 (0.159) 0.039 (0.128) 0.057 (0.183)	-0.007 (0.076) -0.009 (0.082) 0.000 (0.089) 0.007 (0.148) 0.005 (0.086) 0.014 (0.146)	0.052 (0.179) 0.020 (0.140) 0.002 (0.091) 0.013 (0.156) 0.036 (0.132) 0.052 (0.180)	0.098 (0.210) 0.098 (0.210) 0.061 (0.182) 0.061 (0.182) 0.012 (0.097) 0.012 (0.097) 0.018 (0.150) 0.018 (0.150) 0.055 (0.158) 0.055 (0.158) 0.067 (0.191) 0.067 (0.191)
	CFA-based	Bammey [4] Shin [41] Choi [5, 11]	0.007 (0.084) 0.021 (0.153) 0.007 (0.101) 0.004 (0.123) 0.026 (0.025) 0.030 (0.018)	0.682 (0.329) 0.682 (0.329) 0.665 (0.349) 0.665 (0.349) 0.104 (0.166) 0.104 (0.166) 0.099 (0.171) 0.099 (0.171) 0.603 (0.203) 0.603 (0.203) 0.575 (0.191) 0.575 (0.191)	0.501 (0.427) 0.501 (0.427) 0.491 (0.429) 0.491 (0.429) 0.085 (0.172) 0.085 (0.172) 0.084 (0.179) 0.084 (0.179) 0.420 (0.208) 0.420 (0.208) 0.385 (0.210) 0.385 (0.210)	0.023 (0.095) 0.018 (0.107) -0.002 (0.042) -0.001 (0.043) 0.015 (0.109) 0.029 (0.091) 0.133 (0.288) 0.133 (0.288) 0.020 (0.100) 0.128 (0.290) 0.128 (0.290) 0.015 (0.109) -0.005 (0.058) -0.006 (0.059) 0.012 (0.114) 0.012 (0.114) 0.001 (0.002) -0.001 (0.003) 0.156 (0.114) 0.156 (0.114) -0.001 (0.002) 0.001 (0.001) 0.139 (0.116) 0.139 (0.116)
		Zero [38]	0.000 (0.000) 0.000 (0.000)	0.000 (0.000) 0.000 (0.000)	0.000 (0.000) 0.000 (0.000)	0.796 (0.349) 0.796 (0.349) 0.756 (0.387) 0.756 (0.387)	0.732 (0.413) 0.732 (0.413) 0.708 (0.421) 0.708 (0.421)	0.638 (0.451) 0.638 (0.451) 0.624 (0.453) 0.624 (0.453)
		CAGI [25]	0.004 (0.045) 0.003 (0.052)	0.000 (0.027) 0.000 (0.042)	0.002 (0.033) 0.001 (0.044)	0.038 (0.077) 0.038 (0.077) 0.023 (0.077) 0.023 (0.077)	0.044 (0.080) 0.044 (0.080) 0.028 (0.082) 0.028 (0.082)	0.031 (0.071) 0.031 (0.071) 0.021 (0.073) 0.021 (0.073)
	JPEG-based	FDF-A [3] I-CDA [6]	0.031 (0.139) -0.004 (0.087) 0.014 (0.169) -0.015 (0.139) 0.000 (0.000) 0.000 (0.000) 0.000 (0.000) 0.000 (0.000)	-0.003 (0.085) -0.017 (0.139) 0.000 (0.000) 0.000 (0.000)	0.226 (0.242) 0.226 (0.242) 0.216 (0.265) 0.216 (0.265) 0.416 (0.417) 0.416 (0.417) 0.423 (0.408) 0.423 (0.408)	0.228 (0.249) 0.228 (0.249) 0.216 (0.273) 0.216 (0.273) 0.422 (0.407) 0.422 (0.407) 0.414 (0.414) 0.414 (0.414)	0.203 (0.244) 0.203 (0.244) 0.187 (0.264) 0.187 (0.264) 0.381 (0.407) 0.381 (0.407) 0.385 (0.408) 0.385 (0.408)
		CDA [31]	-0.001 (0.034) 0.000 (0.055) -0.004 (0.068) -0.003 (0.098)	0.000 (0.052) -0.005 (0.097)	0.485 (0.339) 0.485 (0.339) 0.449 (0.351) 0.449 (0.351)	0.474 (0.344) 0.474 (0.344) 0.442 (0.350) 0.442 (0.350)	0.401 (0.360) 0.401 (0.360) 0.378 (0.354) 0.378 (0.354)
		BAG [29]	0.000 (0.015) 0.002 (0.029)	0.006 (0.078) 0.025 (0.164)	0.009 (0.079) 0.026 (0.164)	0.232 (0.461) 0.232 (0.461) 0.227 (0.459) 0.227 (0.459)	0.229 (0.458) 0.229 (0.458) 0.223 (0.455) 0.223 (0.455)	0.171 (0.430) 0.171 (0.430) 0.161 (0.430) 0.161 (0.430)
	Multi-purpose tools	0.127 (0.200) 0.127 (0.200) -0.001 (0.069) -0.001 (0.069) 0.108 (0.232) 0.108 (0.232) 0.002 (0.114) 0.002 (0.114) 0.049 (0.091) 0.049 (0.091) 0.000 (0.040) 0.000 (0.040) 0.032 (0.099) 0.032 (0.099) -0.004 (0.065) -0.004 (0.065) 0.082 (0.323) 0.082 (0.323) 0.028 (0.261) 0.028 (0.261) -Consistency [24] 0.154 (0.429) Noiseprint [14] ManTraNet [45] Self-0.154 (0.429) 0.077 (0.393) 0.077 (0.393) 0.099 (0.188) 0.099 (0.188) 0.003 (0.085) 0.003 (0.085) Splicebuster [13] 0.100 (0.217) 0.100 (0.217) 0.012 (0.157) 0.012 (0.157)	0.066 (0.149) 0.066 (0.149) 0.060 (0.179) 0.060 (0.179) 0.074 (0.169) 0.074 (0.169) 0.053 (0.165) 0.053 (0.165) 0.036 (0.270) 0.036 (0.270) 0.082 (0.403) 0.082 (0.403) 0.075 (0.157) 0.075 (0.157) 0.072 (0.202) 0.072 (0.202)	0.013 (0.087) 0.013 (0.087) 0.016 (0.140) 0.016 (0.140) 0.004 (0.023) 0.004 (0.023) 0.000 (0.043) 0.000 (0.043) 0.011 (0.262) 0.011 (0.262) 0.060 (0.386) 0.060 (0.386) 0.005 (0.083) 0.005 (0.083) 0.006 (0.135) 0.006 (0.135)	0.178 (0.248) 0.178 (0.248) 0.138 (0.279) 0.138 (0.279) 0.095 (0.164) 0.095 (0.164) 0.086 (0.171) 0.086 (0.171) 0.078 (0.335) 0.078 (0.335) 0.151 (0.440) 0.151 (0.440) 0.084 (0.175) 0.084 (0.175) 0.082 (0.220) 0.082 (0.220)	0.153 (0.230) 0.153 (0.230) 0.128 (0.261) 0.128 (0.261) 0.112 (0.169) 0.112 (0.169) 0.107 (0.176) 0.107 (0.176) 0.138 (0.370) 0.138 (0.370) 0.246 (0.425) 0.246 (0.425) 0.101 (0.192) 0.101 (0.192) 0.099 (0.215) 0.099 (0.215)


Terahertz technology (between 0.1 and 4 THz) is now a well-established tool to achieve contact-free and non-destructive testing (NDT). Among the technologies, THz CT and phase retrieval are emerging techniques which have been investigated during the last decade. Thus, in this presentation, we focus on the analyze capabilities from 3D reconstructed volumes of a complex object obtained by a real time-THz imaging system. We demonstrate that images obtained are compatible with an automated processing composed of: i) an ad-hoc segmentation, extracting the sample from the background and reconstruction noise ii) a component labelling, iii) a skeletonization, providing additional meta-data about the sample morphology. We also present how we can assess to phase information of the object by phase retrieval from intensity measured in a volumetric grid.

.

I. INTRODUCTION

erahertz Computed Tomography (THz CT) is an emerging technique providing 3D visualization of an object from its set of radiographs acquired at different viewing angles. The low absorption and large penetration depth of transmitted THz wave led to a sufficient contrast allowing the reconstruction of volumes, imaging the internal structure of transparent objects [START_REF] Guillet | Review of terahertz tomography techniques[END_REF]. These materials (such as plastics, wood or paper) are troublesome to inspect with other tomographic techniques such as X-Rays. But to access to the object properties, deep data processing of images is necessary to get rid of some artefact induced by physical effect but also numerical calculation [START_REF] Balacey | Advanced Processing Sequence for 3-D THz Imaging[END_REF]. Nevertheless, THz-CT remains extremely time-consuming to obtain a relevant graphical depiction requiring several hours of measurements for a 3D tomographic reconstruction. This tedious process is far from matching with the required framerate targeted for quality control or non-destructive testing applications. To face this limitation, research groups and cutting-edge technology centers have developed a variety of compact and uncooled terahertz matrix sensors based on several technological advances, from micro-bolometer integration to semi-conductors hetero-structures. In this presentation, we will describe two experimental achievements : THz tomography and advanced data processing implementation for 3D rendering and terahertz phase retrieval from a set of axially separated diffractive intensity distributions which is a promising singlebeam computational imaging technique that ensures the obtention of high spatial resolutions and phase wave fronts. These two results were obtained using real time THz apparatus.

II. EXPERIMENT

We used a bolometric camera for full-field imaging to assess a diffraction field or radiographies. In a straightforward transmission configuration, such a recording setup of the subsequent intensity profiles, should simply be completed by the illumination source, and eventual beam-shaping elements. In this work, we employed a Lytid's teracascade 1000 QCL source. In order to overcome the limiting artifacts induced by the high coherence of such THz QCL sources, and ensure the versatility of the imaging system, the homogeneous illumination in the object plane is performed via a combination of fast beam steering centering purposes, as well [START_REF] Perraud | A Versatile Illumination System For Real-Time Terahertz Imaging[END_REF]. For tomography experiment, the sample is positioned onto a rotation stage and acquisitions were performed in real time. We performed reflection and transmission imaging of two samples: three dried leaves and a PE plate. We automated various visualization techniques based on time-domain data and frequency domain as illustrated in Fig1. Moreover, we improved skeletonization module for complex 3D structure. The projection set is processed by a tomographic algorithm to reconstruct a 3D volume of the scanned object. In the tomogram, the 3D structure of the sample is revealed thanks to proportionality between the intensity of each reconstructed voxel with the overall attenuation encountered by the THz radiation at the corresponding position in the sample. In the THz range, this attenuation is mainly proportional to the extinction coefficient (neglecting optical effects). We used a regularized 3D implementation of the THz Ordered Subsets Convex (THz-OSC) algorithm. For diffractive imaging process, a multiple-plane phase retrieval is an efficient approach. It relies on the measurements of a set of axially separated transverse intensity distributions. Similar to the competing holographic techniques, it also makes use of processing algorithms adapted from methodologies developed in the visible frequency range. The most popular algorithms are single-beam multiple intensity reconstruction (SBMIR) and the transport of intensity equation. This multiple plane approach is characterized by the extreme simplicity of the object illumination setup and guarantees better convergence compared to single-plane phase retrieval algorithms, but the recording of the diffraction patterns often remains time-consuming. We will present two new algorithms that were investigated namely the algorithm of unordered propagation and the algorithm of data self-extrapolation, abbreviated as SBMIR-U and SBMIR-S correspondingly [START_REF] Chopard | Single-scan multiplane phase retrieval with a radiation of terahertz quantum cascade laser[END_REF]. The distinctive feature of SBMIR-U is the use of intensity distributions in a stochastic order. It was previously shown in a P.Mounaix IMS UMR CNRS 5218, Bat A31 , 351 cours de la libération 33405 Talence Cedex Advanced Data Processing For Tomography and 3D Rendering With Terahertz Waves T visible range phase retrieval that this algorithm may accelerate the convergence and allows to reduce the required number of intensity patterns to use as an input data. The second algorithm, SBMIR-S, implements the extrapolation of the wavefield outside the spatially limited registration area, which allows to improve the resolution in the object plane.

III. DATA PROCESSING

IV. RESULT Indeed, an image, that would take several hours to be recorded using a raster scan approach, is instantaneously available through full-field imaging. More specifically, considering the 25 FPS frame rate and 240x320 array size, a recording rate of 1.9210 6 pixel .s-1 is achieved. Through this real-time recording improvement, a full sinogram recording is easily obtained under 1 minute. An example of this fast-recording process where a triple leaf has been investigated at 2.5 THz. A single-frame illumination, scaled to the leaf size was used as to take advantage of the full frame rate of the TZCAM sensor while allowing for a proper power density. A rotation speed of 25°.s-1 allowed for a total 360° sinogram recording in under 15 second with a projection every degree. The OSC [START_REF] Recur | Ordered subsets convex algorithm for 3D terahertz transmission tomography[END_REF], specifically designed for a convergence over few projections, necessary in the case of focused point tomography, is applied. Thanks to the skeletonization and the set of orthonormal planes extracted along the graph, we can compute several dimension statistics and report on fig 3c the 3D structure of the sample .

For diffractive imaging , one can aim to simply illuminate the sample with a collimated beam of suitable diameter, then retrieving the transmitted diffracted field in a selection of planes along . An optimal proximity of the first recording plane with respect to the sample can then be expected as to ensure the collection of diffracted high spatial frequency components. Large numerical aperture focusing is then possible. First, from such intensity data sets, the unsorted SBMIR algorithm has been considered for the retrieval of the phase information and the focused reconstruction on the object plane..

Fig 3 : Sample used in the experiment and reconstructed image

This technique allows to minimize required measurement time and simplify the process of data acquisition. Single-scan detection ensures the collection of an exhaustive dataset that provides substantial flexibility in the post-processing extraction steps of the wavefront. SBMIR-S is especially relevant in case of spatially limited diffraction patterns utilization. Selfextrapolation allows to recreate the data beyond the registration area, in places where the scattered field was located but not measured, which, in turn, leads to resolution enhancement of the focused in the object plane distribution.

For SBMIR-S investigation, intensity patterns were employed, cropped to area 4 times smaller than the original size. The corresponding Fresnel numbers have been also reduced by the same factor [START_REF] Chopard | Single-scan multiplane phase retrieval with a radiation of terahertz quantum cascade laser[END_REF]. In this case unmodified SBMIR have not ensured the convergence. By the SBMIR-S algorithm the cropped distributions were extrapolated to the initial size, thereby providing the same resolution as conventional SBMIR did with the use of uncropped intensity patterns. SBMIR-S algorithm is relevant for measurements in the raster scanning mode. With its implementation it is possible to reduce the registration area, and, respectively, the measurement time.

Fig. 1

 1 Fig. 1 Data and image processing sequences implemented

Fig. 2

 2 Fig. 2 Selection of 2D projections, recorded in real-time, (b) recorded sinogram relative to the central recording plane, (c)Skeleton of the leave reconstructed by terahertz tomography

  V. CONCLUSION Real time THz CT has been demonstrated . An advance 3D data processing renders the 3D reconstructed sample with an automated component labelling, a skeletonization step which provides additional meta-data about the sample morphology. Concerning lens less imaging, optimized SBMIR algorithms of unordered propagation and self-extrapolation have been investigated in THz phase retrieval for the first time. SBMIR-U allowed to reduce the number of used intensity patterns and to obtain the same resolution. It provided faster convergence in retrieval from data of near-field Fresnel diffraction zone. SBMIR-S allowed to improve the resolution in retrieval from intensity distributions characterized by low Fresnel numbers. It is especially relevant to use in a raster scanning mode.


domain: math info

text:
Theo Van Uem

GENERALIZED FIVE PERSON HAT GAME

come

Introduction

Hat puzzles were formulated at least since Martin Gardner's 1961 article [START_REF] Gardner | The 2nd Scientific American Book of Mathematical Puzzles & Diversions[END_REF]. They have got an impulse by Todd Ebert in his Ph.D. thesis in 1998 [START_REF] Ebert | Applications of recursive operators to randomness and complexity[END_REF]. Buhler [START_REF] Buhler | Hat tricks[END_REF] stated: "It is remarkable that a purely recreational problem comes so close to the research frontier". Also articles in The New York Times [START_REF] Robinson | Why mathematicians now care about their hat color, The New York Times[END_REF], Die Zeit [START_REF] Blum | Denksport für Hutträger[END_REF] and abcNews [START_REF] Poulos | Could you solve this 1 million hat trick?[END_REF] about this subject got broad attention. This paper studies generalized Ebert's hat problem (symmetric and asymmetric): five distinguishable players are randomly fitted with a colored hat (two colors available), where the probabilities of getting a specific color may be different, but known to all the players. All players guess simultaneously the color of their own hat observing only the hat colors of the other four players. It is also allowed for each player to pass: no color is guessed. The team wins if at least one player guesses his or her hat color correctly and none of the players has an incorrect guess. Our goal is to maximize the probability of winning the game and to describe winning strategies. The symmetric two color hat problem (equal probabilities for each color) with N = 2 k -1 players is solved in [START_REF] Ebert | On the autoreducibility of random sequences[END_REF], using Hamming codes, and with N = 2 k players in [START_REF] Cohen | Covering Codes[END_REF] using extended Hamming codes. Burke et al. [START_REF] Burke | A puzzle to challenge genetic programming[END_REF] try to solve the symmetric hat problem with N = 3, 4, 5, 7 players using genetic programming. Their conclusion: The N -prisoners puzzle (alternative names: Hat Problem, Hat Game) gives evolutionary computation and genetic programming a new challenge to overcome. Lenstra and Seroussi [START_REF] Lenstra | On hats and other covers[END_REF] show that in the symmetric case of two hat colors, and for any value of N , playing strategies are equivalent to binary covering codes of radius one. Combining the result of Lenstra and Seroussi with Tables for Bounds on Covering Codes [START_REF] Kéri | Tables for bounds on covering codes[END_REF], we get: N 2 3 4 5 6 7 8 9 K(N, 1) 2 2 4 7 12 16 32 62 K(N, 1) is smallest size of a binary covering code of radius 1. Maximum probability for Ebert's symmetric Hat Game is 1 -K(N,1)

2 N . Lower bound on K(9, 1) was found in 2001 by Östergård-Blass, the upper bound in 2005 by Östergård. Krzywkowski [START_REF] Krzywkowski | On the hat problem, its variations, and applications[END_REF] describes applications of the hat problem and its variations, and their connections to different areas of science. Krzywkowski [START_REF] Krzywkowski | A more colorful hat problem[END_REF], section 3, gives an optimal solution of the symmetric three person three color hat problem. Johnson [START_REF] Johnson | [END_REF] ends his presentation with an open problem: If the hat colors are not equally likely, how will the optimal strategy be affected? We will answer this question for five persons and two colors and our method gives also interesting results in the symmetric case. In section 2 we define an adequate set. In section 3 we obtain results for the asymmetric five player, two color Hat Game. In section 4 we do the same for the symmetric Hat Game. In all situations all players know the underlying probabilities of each player.

Adequate sets

In this section we have N players and q colors. The N persons in our game are distinguishable, so we can label them from 1 to N . We label the q colors 0, 1, .., q -1. The probabilities of the colors are fixed and known to all players. The probability that color i will be on a hat is p i (i ∈ {0, 1, .., q -1}, q-1 i=0 p i = 1). Each possible configuration of the hats can be represented by an element of

B = {b 1 b 2 . . . b N |b i ∈ {0, 1, . . . , q -1} , i = 1, 2.., N }. The Scode represents what the N different players sees. Player i sees q-ary code b 1 ..b i-1 b i+1 ..b N with decimal value s i = i-1 k=1 b k .q N -k-1 + N k=i+1 b k .q N -
k , a value between 0 and q N -1 -1. Let S be the set of all Scodes: S = {s 1 s 2 . . . s

N |s i = i-1 k=1 b k .q N -k-1 + N k=i+1 b k .q N -k , b i ∈ {0, 1, . . . , q -1}, i = 1, 2, . . . , N }.
Each player has to make a choice out of q + 1 possibilities: 0='guess color 0', 1='guess color 1', . . . ., q -1 ='guess color q -1', q='pass'. We define a decision matrix D = (a i,j ) where i ∈ {1, 2, .., N }(players); j ∈ {0, 1, .., q N -1 -1}(Scode of a player); a i,j ∈ {0, 1, .., q} . The meaning of a i,j is: player i sees Scode j and takes decision a i,j (guess a color or pass). We observe the total probability (sum) of our guesses. For each b 1 b 2 . . . b N in B with n i times color i (i = 0, 1, . . . , q -1, q-1 i=0 n i = N ) we have:

CASE b 1 b 2 . . . b N (Scode player i: s i = i-1 k=1 b k .q N -k-1 + N k=i+1 b k .q N -k ) IF a 1,s 1 ∈ {q, b 1 } AND a 2,s 2 ∈ {q, b 2 } AND ... AND a N,s N ∈ {q, b N } AND NOT (a 1,s 1 = a 2,s 2 = • • • = a N,s N = q) THEN sum=sum+p n 0 0 .p n 1 1 . . . p n q-1 q-1 .
Any choice of the a i,j in the decision matrix determines which CASES b 1 b 2 . . . b N have a positive contribution to sum (we call it a GOOD CASE) and which CASES don't contribute positive to sum (we call it a BAD CASE). Any GOOD CASE has at least one a i,j not equal to q. Let this specific a i,j have value b i 0 . Then our GOOD CASE generates q -1 BAD CASES by only changing the value b i 0 in any value of 0, 1, .., q -1 except b i 0 . Let A be the set of all BAD CASES (given a decision matrix D), then B -A is the set of all GOOD CASES such that for each element x in B -A there are (q -1) elements in A which are equal to x up to one fixed position. We call A an adequate set in relation to B -A and the decision matrix D. The definition of adequate set is the same idea as the concept of strong covering, introduced by Lenstra and Seroussi [START_REF] Lenstra | On hats and other covers[END_REF]. The number of elements in an adequate set will be written as das (dimension of adequate set). Adequate sets are generated by an adequate set generator (ASG) We have implemented an ASG in VBA/Excel (see Appendix A). Given an adequate set, we obtain a decision matrix D = (a i,j ) by the following procedure. Procedure DMG (Decision Matrix Generator): Begin Procedure For each element in the adequate set:

• Determine the q-ary representation b 1 b 2 . . . b N • Calculate Scodes s i = i-1 k=1 b k .q N -k-1 + N k=i+1 b k .q N -k ( i=1,.
.,N) • For each player i: fill decision matrix with a i,s i = b i (i=1,..,N), where each cell may contain several values.

Matrix D is filled with BAD COLORS. We can extract the GOOD COL-ORS by considering all a i,j with q -1 BAD COLORS and then choose the only missing color. In all situations with less than q -1 BAD COLORS we pass. When there is an a i,j with q BAD COLORS all colors are bad, so the first option is to pass. But when we choose any color, we get a situation with q -1 colors. So in case of q BAD COLORS we are free to choose any color or pass. The code for pass is q, but in our decision matrices we prefer a blank, which supports readability. The code for 'any color or pass will do' is defined q + 1, but in our decision matrices we prefer a . End Procedure.

Decision matrices are generated by an Decision Matrix Generator (DMG).We have implemented a DMG in VBA/Excel (see Appendix B).

Asymmetric five person Hat Game

Theorem 1. In asymmetric five person (two color) hat game we have maximal probability Ψ (5, p) of winning the game:

(1)

Ψ (5, p) =        1 -p + 2p 2 -2p 3 + p 5 (0 ≤ p ≤ √ 2 -1) 5p -10p 2 + 6p 3 + p 4 -p 5 ( √ 2 -1 ≤ p ≤ 0.5) 1 -2p + 4p 2 -4p 4 + p 5 (0.5 ≤ p ≤ 2 - √ 2) 1 -2p + 6p 2 -8p 3 + 5p 4 -p 5 (2 - √ 2 ≤ p ≤ 1)
with optimal decision matrices: CASE 0.5 < p ≤ 2 -√ 2:

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 * 1 1 0 0 0 * 1 CASE 2 - √ 2 ≤ p < 1:
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

1 * 0 0 0 1 1 * 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0
( means: any color or pass; stars are independent)

Proof. We run the application ASG with parameters N =5, p=0.55 and das=7. This yields 320 adequate sets. When we sort these sets by probability, we get 12 different classes (see Appendix C where we show the first element of each class). The adequate set and the number of zero's in each element in an adequate set are independent of p. We note the following structure in Appendix C: 012345 probability 024001 2pq 4 + 4p 2 q 3 + p 5 022210 2pq 4 + 2p 2 q 3 + 2p 3 q 2 + p 4 q 111310 q 5 + pq 4 + p 2 q 3 + 3p 3 q 2 + p 4 q 013210 pq 4 + 3p 2 q 3 + 2p 3 q 2 + p 4 q 102310 q 5 + 2p 2 q 3 + 3p 3 q 2 + p 4 q 012310 pq 4 + 2p 2 q 3 + 3p 3 q 2 + p 4 q 120130 q 5 + 2pq 4 + p 3 q 2 + 3p 4 q 013201 pq 4 + 3p 2 q 3 + 2p 3 q 2 + p 5 012220 pq 4 + 2p 2 q 3 + 2p 3 q 2 + 2p 4 q 031021 3pq 4 + p 2 q 3 + 2p 4 q + p 5 013111 pq 4 + 3p 2 q 3 + p 3 q 2 + p 4 q + p 5 100420 q 5 + 4p 3 q 2 + 2p 4 q

Figure 1 shows the dominance relations between this 12 different classes. 2)+b( 3)+b( 4)+b(5) ≥ a(0)+a( 1)+a( 2)+a( 3)+a( 4)+a( 5)

The last inequality may be omitted (we have das ≥ das). The dominance relation is transitive. The arrows A,B,C and D needs some attention. We use as symbol for dominance. A: 022210 111310 If p > q > 0 then -q 5 + pq 4 + p 2 q 3 -p 3 q 2 = -q 5 + pq 4 + p 2 q 3 -p 3 q 2 = -q 2 (p -q) 2 < 0 B and C: 102310 120310 and 013201 031021 if p>q >0 then -2pq 4 + 2p 2 q 3 + 2p 3 q 2 -2 p 4 q = -2pq(p -q) 3 < 0 D: If 2 -√ 2 < p < 1 then 022210 024001 and if 0.

5 < p < 2 - √ 2 then 024001 022210 -2p 2 q 3 + 2p 3 q 2 + p 4 q -p 5 = p 2 2p 3 -9p 2 + 8p -2 = p 2 (2p -1) p 2 -4p + 2 = p 2 (2p -1) (p -2 - √ 2)(p -2 + √
2) Let Ψ (N, p) be the maximum probability of correct guessing. If 2 -√ 2 < p < 1 then 022210 024001 and

Ψ (5, p) = 1 -2pq 4 + 2p 2 q 3 + 2p 3 q 2 + p 4 q = 1 -2p + 6p 2 -8p 3 + 5p 4 -p 5
If 0.5 < p < 2 -√ 2 then 024001 022210 and

Ψ (5, p) = 1 -2pq 4 + 4p 2 q 3 + p 5 = 1 -2p + 4p 2 -4p 4 + p 5
By changing the roles of p and q we get: (1) Graph of Ψ (5, p): We remark: minimum is at ( 1 2 , 25 32 ) and Ψ (5, p)

is not differentiable at 1 2 , √ 2 -1 and 2 - √ 2.
When N =5 we have 320 adequate sets. Using the program ASG p=0.55 das=7 we get after sorting on sum: when 0.5 < p < 2 -√ 2 we have 10 optimal adequate sets. Using the program ASG p=0.9 das=7 we get after sorting on sum: when 2 -√ 2 < p < 1 we have 30 optimal adequate sets. When p = 2 -√ 2 : 40 optimal adequate sets (the union of the two foregoing adequate sets). Using procedure DMG , we give the first element in each case: CASE 0.5 < p < 2 -√ 2 : adequate set {0,7,11,19,28,29,30}; Use: DMG p=0.55 to obtain the decision matrices. Note: players 1,2,3 have same strategy; players 4 and 5 also. CASE 2 -√ 2 < p < 1 : adequate set {1,6,14,22,24,27,29};

Use DMG to obtain the decision matrices. Note: players 1,2 have same strategy, players 3,4 also; player 5 has her own strategy. CASE p = 2 -√ 2: we get the union of 10 optimal sets in case of 0.5 < p < 2 -√ 2 and 30 optimal sets in case of 2 -√ 2 < p < 1 .

We call two solutions isomorphic when we can transform one solution to the other by renumbering the players. Observing all 40 decision matrices and making use of the positions (players) of the stars in these matrices, we get the result in Appendix D, where the column STARS gives the positions of the two stars and the column CYCLES gives the renumbering to obtain the same solution. This can be verified by writing each adequate set in the binary representation and then applying the cycles. Appendix D shows that there are only two non-isomorphic solutions (these two solutions can't be isomorphic for isomorphic sets have always the same probability).

The last point here is to convince ourselves that any adequate set with das>7 doesn't yield better solutions. The last inequality may be omitted (we have b ≥ a -(a -b).) These dominance relations are implemented as procedure dom() in ASG.

Run the program ASG with das=8,9,. . . 32. where we have 5 calls to dom() (see figure 1; we omitted the S patterns, for they are detected by the procedure). No (dominant) adequate sets are found. Conclusion: das = 7 is optimal and {(022210), (024001)} dominates all adequate sets.

3.1. Computational complexity. We consider the number of strategies to be examined to solve the hat problem with N players and two colors. Each of the N players has 2 N -1 possible situations to observe and in each situation there are three possible guesses: white, black or pass. So we have (3 2 N -1 ) N possible strategies. Krzywkowski [START_REF] Lenstra | On hats and other covers[END_REF] shows that is suffices to examine (3 2 N -1 -2 ) N strategies. The adequate set method has to deal where {i 1 , i 2 , .., i das } with 0 ≤ i 1 < i 2 < .. < i das ≤ 2 N -1.

The number of strategies for fixed das is the number of subsets of dimension das of {0,1,. . . , 2 N -1}:

2 N das . But we have to test all possible values of das. So the correct expression is:

das 2 N das = 2 (2 N ) .
To get an idea of the power of the adequate set method, we compare the number of strategies (brute force, Krzywkowski and adequate set method):

N das (3 2 N -1 ) N (3 2 N -1 -2 ) N 2 (2 N ) 5 7 1.50E+38 2.50E+33 4.29E+09 4

. Symmetric two color five person Hat Game

In this section with five persons the two colors have the same probability: p = q = 1 2 . Theorem 2. The maximal probability for symmetric five person two color Hat Game is 25 32 . All 12 non-isomorphic optimal decision matrices are given in Appendices E and F.

Proof. Running ASG with any value of p gives 320 adequate sets. When p = 0.5 all these sets are optimal (with probability 25 32 ). We split the 320 sets in 12 probability classes (see section 3). In Appendices E and F we give the first element of each class, the decision matrix and the number of isomorphic elements in each class, where isomorphic sets can be detected in the same way (STARS, CYCLES) as in section 3. All 320 decision matrices are generated by procedure DMG .

Figure 1 .

 1 Figure 1. Dominance relations

  Let b = das(b()), a = das(a()). When e = a -b ≥ 0 then we delete the 'cheapest' a -b elements from a(), which gives a 'cheaper' situation. We get: b(0)≥ a(0)-e b(0)+b(1) ≥ a(0)+a(1)-e ... ... b(0)+b(1)+b(2)+b(3)+b(4)+b(5) ≥ a(0)+a(1)+a(2)+a(3)+a(4)+a(5)-e

  The 12 probability classes generates 12 non-isomorphic decision matrices.

		Appendix D. Q=2, N=5, two isomorphic sets
	No.	adequate sets						STARS		CYCLES
	1	0	7	11	19	28	29	30	45	(1)
	2	0	7	13	21	26	27	30	35	(34)
	3	0	7	14	22	25	27	29	34	(35)
	4	0	7	15	23	25	26	28	12 (14)(25)
	5	0	11	13	22	23	25	30	25	(24)
	6	0	11	14	21	23	26	29	24	(25)
	7	0	11	15	21	22	27	28	13 (14)(35)
	8	0	13	14	19	23	27	28	23 (24)(35)
	9	0	13	15	19	22	26	29	14	(15)
	10	0	14	15	19	21	25	30	25	(24)
	1	1	6	14	22	24	27	29	12	(1)
	2	1	6	15	23	24	26	28	34 (13)(24)
	3	1	10	14	20	23	26	29	13	(23)
	4	1	10	15	20	22	27	28	24	(14)
	5	1	12	14	18	23	27	28	14	(24)
	6	1	12	15	18	22	26	29	23	(13)
	7	2	5	13	21	24	27	30	12	(45)
	8	2	5	15	23	24	25	28	35 (13)(25)
	9	2	9	13	20	23	25	30	13	(23)
	10	2	9	15	20	21	27	28	25	(15)
	11	2	12	13	17	23	27	28	15	(25)
	12	2	12	15	17	21	25	30	23	(13)
	13	3	4	11	19	24	29	30	12	(35)
	14	3	4	15	23	24	25	26	45 (14)(25)
	15	3	7	8	19	20	29	30	13	(23)
	16	3	7	11	12	16	29	30	23	(13)
	17	3	8	15	20	21	22	27	45 (14)(25)
	18	3	12	13	14	16	23	27	45 (14)(25)
	19	4	9	11	18	23	25	30	14	(24)
	20	4	9	15	18	19	26	29	25	(15)
	21	4	10	11	17	23	26	29	15	(25)
	22	4	10	15	17	19	25	30	24	(14)
	23	5	7	8	18	21	27	30	14	(24)
	24	5	7	10	13	16	27	30	24	(14)
	25	5	8	15	18	19	22	29	35 (13)(25)
	26	5	10	11	14	16	23	29	35 (13)(25)
	27	6	7	8	17	22	27	29	15	(25)
	28	6	7	9	14	16	27	29	25	(15)
	29	6	8	15	17	19	21	30	34 (13)(24)
	30	6	9	11	13	16	23	30	34 (13)(24)