Mario Hildebrandt
email: hildebrandt@iti.cs.uni-magdeburg.de

Andrey Makrushin
email: makrushin@iti.cs.uni-magdeburg.de

Kun Qian
email: kqian@iti.cs.uni-magdeburg.de

Jana Dittmann
email: dittmann@iti.cs.uni-magdeburg.de

Visibility Assessment of Latent Fingerprints on Challenging Substrates in Spectroscopic Scans

Keywords: Forensics, latent fingerprints, UV-VIS spectroscopy, fingerprint visibility assessment

Our objectives for crime scene forensics are to find the substrates on which finger traces are visible in limited ranges of the electromagnetic spectrum using UV-VIS reflection spectroscopy and to determine the optimal ranges in the interval from 163 to 844 nm. We subjectively assess the visibility of fingerprints within detailed scans with a resolution of 500 ppi and compare the results with those of an automatic visibility assessment based on the streakiness score. Ten different substrates are evaluated, each with three fingerprints from different donors. Streakiness score is confirmed to be a suitable fingerprint visibility indicator on non-structured substrates. We identify two substrates, namely metallic paint and blued metal, on which ridge lines become visible exclusively in UV range from 200 to 400 nm and from 210 to 300 nm correspondingly.

Extended Abstract

As the most common form of trace evidence left at crime scenes, latent fingerprints pose the most challenges for forensic experts [START_REF] Champod | Fingerprints and other ridge skin impressions[END_REF]. Since they are present rather often yet invisible unless brought out with chemical and/or physical processes designed to enhance the visibility of fingerprint residues [START_REF] Swgfast) | Scientific Working Group on Friction Ridge Analysis, Study and Technology[END_REF] (e.g. fuming, powdering, or deposition of chemical reagent), it is important to identify substrate dependent technique or reagent and the appropriate processing sequence for successful enhancement. In today's crime scene forensics three kinds of substrate properties are known [START_REF] Swgfast) | Scientific Working Group on Friction Ridge Analysis, Study and Technology[END_REF][3]: 1) porous substrates (e.g. paper) are absorbent and provide good adhesion for latent fingerprints; 2) non-porous substrates (e.g. glass) do not absorb, so latent fingerprints on such substrates are more susceptible to damage; 3) semi-porous substrates (e.g. glossy cardboard) both resist and absorb fingerprint residue, so it may or may not soak in depending on its viscosity as well as on the absorbent properties of the substrates. Since substrates have different characteristics regarding the absorption of fingerprint residues and light reflection, different fingerprint development techniques are required. On challenging substrates these techniques have an invasive na-ture as they involve applying alien substances on the fingerprint residue, thus causing the potential risk of compromising the evidence. Hence, various non-invasive approaches are developed to visualize latent fingerprints, e.g. by using various sensors and light sources [START_REF] Bleay | Fingerprint Source Book[END_REF], or Chromatic White Light (CWL) sensors [START_REF] Makrushin | Advanced techniques for latent fingerprint detection and validation using a CWL device[END_REF][5] [START_REF] Hildebrandt | Benchmarking contact-less surface measurement devices for fingerprint acquisition in forensic investigations: results for a differential scan approach with a chromatic white light sensor[END_REF]. It is common that substrates reflect specular light differently depending on the wavelength of the light source. This effect can be used to render fingerprint residues visible and to acquire them in detailed scans. However, inherent properties of substrates (e.g. translucency or structure) might interfere with the scanning, making the identification of the substrate of crucial importance.

We apply the spectroscopic acquisition with a lateral resolution of 500 ppi in the range from 163 to 844 nm on latent fingerprints deposited on ten substrates and then assess the fingerprint visibility in those detailed scans subjectively and by calculating the streakiness scores [START_REF] Makrushin | Visibility enhancement and validation of segmented latent fingerprints in crime scene forensics[END_REF].

In the subjective visibility evaluation of the fingerprint a label corresponding to its suitability for forensic investigations is assigned. In particular, we distinguish between four classes of fingerprint visibility: 1) invisible, i.e. fingerprint is not perceptible for the naked eye; 2) weak pattern, i.e. fingerprint is partially visible but not usable for forensic investigations; 3) fair pattern, i.e. fingerprint is visible but covered by the substrate's texture or structure, and this usually requires longer investigation time; 4) perfect pattern, i.e. fingerprint can be easily segmented using binarization.

The streakiness score S [START_REF] Makrushin | Visibility enhancement and validation of segmented latent fingerprints in crime scene forensics[END_REF] is used as the objective visibility measure. However, in contrast to [START_REF] Makrushin | Visibility enhancement and validation of segmented latent fingerprints in crime scene forensics[END_REF] we do not use substrate specific filters therefore achieve fully automatic processing. The basic idea is assigning S to determine the visibility of the fingerprint at each particular wavelength. Since S is the relative number of pixels in ridge lines in a binarized fingerprint pattern, its value rests in the interval [0, 1], where 0 denotes a completely invisible fingerprint pattern and 1 a perfectly visible one. It relies on the assumption that a fingerprint forms a striated pattern consisting of local ridge-valley patterns with constant frequencies and directions. A preprocessing in the Fourier domain is applied to enhance the ridge-valley pattern, afterwards an enhancement based on the approach from [START_REF] Hong | Fingerprint Image Enhancement: Algorithm and Performance Evaluation[END_REF] is applied. The first step consists of multiplying the Fourier representation with a ring filter around its origin (see [START_REF] Wu | Image quality measures for fingerprint image enhancement[END_REF]) followed by a zero-mean normalization. The second step consists of estimating local orientations and a corresponding reliability map, both based on gradients. Furthermore, local frequencies are determined for reliable orientations. This is the foundation for locally applying corresponding Gabor filters for the enhancement of the ridge pattern. At last, the filtered image is binarized to calculate the streakiness score.

As a benchmark, we adapt the concept of differential images from [START_REF] Hildebrandt | Benchmarking contact-less surface measurement devices for fingerprint acquisition in forensic investigations: results for a differential scan approach with a chromatic white light sensor[END_REF] to eliminate possible interference introduced by the substrate and compare the visibility of fingerprints on original and differential images. On cooperative substrates the fingerprint visibility on original and differential images is expected to be equal. On challenging substrates with a constant reflection the originally invisible fingerprints become visible in differential scans. On challenging substrates with a random reflection the visibility is not expected to increase. The original approach subtracts the data from the same area of the substrate without a fingerprint. In our proposed approach, the image with the fingerprint is divided by the values from the images without the fingerprint:

The intensity image I(λ w ) at one particular wavelength λ w in the interval [163, 844]nm with wЄ[0, 2047] can be determined by I(λ w )=R(λ w )•S(λ w )•Sens(λ w ), where R(λ w ) is the reflection of the measured material, S(λ w ) is the spectral distribution of the light source, and Sens(λ w ) is the sensitivity of the spectrometer. Then R(λ w ) can be divided into the reflection of the substrate R s (λ w ) and the specific absorption and fluorescence of the fingerprint residue R f (λ w ). By performing a division of I(λ w ) by the spectral data from a reference scan I ref (λ w ), S(λ w ) and Sens(λ w ), as well as R s (λ w ) are eliminated, leading to an enhanced contrast.

In total we evaluate ten substrates that are common at crime scenes as summarized in Table 1, each with three fingerprints from different donors. The substrates are divided into the classes cooperative, moderate and challenging based on observations for the CWL sensor [START_REF] Hildebrandt | Benchmarking contact-less surface measurement devices for fingerprint acquisition in forensic investigations: results for a differential scan approach with a chromatic white light sensor[END_REF]. On cooperative non-structured and non-textured substrates we can assume the following ranges streakiness scores S for the subjective visibility classes: S<0.1 indicates an invisible fingerprint, 0.1<S<0.3 usually corresponds with a weak pattern, 0.3<S<0.5 indicates a fair pattern which probably contains smeared areas, S>0.5 indicates a good to perfect fingerprint visibility. However, since we do not apply substrate specific filters those ranges do not apply on moderate and challenging substrates because higher values of streakiness scores are likely to be caused by surface properties. On cooperative substrates (white furniture surface, glass and 5 Euro cent coin) the UV-VIS spectroscopy images yield satisfactory visibility throughout the entire spectrum with S exceeding 0.5. On copy paper the images are equally unusable as those captured using a CWL sensor. On beech veneer the visibility is identical with that on CWL images. On non-metallic paint, brushed stainless steel and golden oak veneer the visibility is slightly worse than that of a CWL sensor. The calculation of S on structured surfaces (beech veneer, golden oak veneer, and brushed stainless steel) makes no sense since the streakiness of a surface dominates that of a fingerprint. Most notably, the spectrometer acquires a perfect fingerprint image within the UV band on metallic paint, whereas the transparent layer causes non-deterministic noise while using a CWL sensor [START_REF] Hildebrandt | Benchmarking contact-less surface measurement devices for fingerprint acquisition in forensic investigations: results for a differential scan approach with a chromatic white light sensor[END_REF]. Here, S yields 0.7 between 200 and 400nm and 0.05 for the spectrum of visible light. This can be explained by the fact that the covering transparent paint is non-transparent for UV radiation. On blued metal, fresh fingerprints are slightly visible in the UV band, which is an improvement compared to a CWL sensor.

The important conclusion is that the streakiness score generally reflects judgments of human experts about the fingerprint visibility. However, in order to extract meaningful streakiness scores a substrate specific preprocessing is necessary.

Table 1 .

 1 Substrates, integration times and subjective evaluation results of original and differential images (*** -perfect, ** -good, * -weak, and o -invisible fingerprint pattern)

	Substrate Integra-	Original image	Differential image	Compari-
		tion					son to
		time	Wavelength	Quality Wavelength	Quality	CWL [9] Substrate
		(ms)	range (nm)		range (nm)			property
	White							non-porous,
	furniture							cooperative
	surface	100	163-844	***	163-844	***	identical
	Metallic							non-porous,
	paint	100	200-385	***	195-385	***	better	challenging
								non-porous
	Glass	50	210-710	***	200-844	***	identical	cooperative
	Copy						identi-	porous,
	paper	250	220-250	*	220-250	**	cal/better	challenging
	5 Euro						identical	non-porous
	cent coin 100	220-520	***	220-844	***	/better	cooperative
	Blued							semi-porous,
	metal	500	210-300	*	210-300	**	better	challenging
	Non-							non-porous,
	metallic						identical	challenging
	paint	250	163-844	O	200-220	*/**	/worse
	Brushed							non-porous,
	stainless							moderate
	steel	100	163-844	*/**	210-270	**	worse
	Beech							non-porous,
	veneer	100	163-844	**	163-844	***	identical	moderate
	Golden							non-porous,
	oak							moderate
	veneer	250	163-844	o/*	163-844	o/*	worse

Acknowledgement

The authors wish to thank Michael Ulrich for the list of common substrates from crime scenes. The work in this paper has been funded in part by the German Federal Ministry of Education and Science (BMBF) through the Research Program under Contract No. FKZ: 13N10818.


Mario Hildebrandt
email: hildebrandt@iti.cs.uni-magdeburg.de

Jennifer Sturm
email: sturm@iti.cs.uni-magdeburg.de

Jana Dittmann
email: dittmann@iti.cs.uni-magdeburg.de

Claus Vielhauer
email: vielhauer@fh-brandenburg.de

Creation of a Public Corpus of Contact-Less Acquired Latent Fingerprints without Privacy Implications

Keywords: Forensics, latent fingerprints, public data set, privacy aspects

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Extended Abstract

In biometrics and forensics evaluations of new and existing techniques are very important in order to determine error rates especially when such methods are used e.g. for authentication systems or for the analysis of evidence. In forensics the Daubert challenge [START_REF] Dixon | Changes in the Standards for Admitting Expert Evidence in Federal Civil Cases Since the Daubert Decision[END_REF] comprises several factors that can be assessed by a judge prior to admitting evidence in court. Furthermore, researchers need to show that their proposed methods pose an advance in science and technology. Here, public data sets help compareing the evaluation results with each other without any bias. However, especially biometric data need to be considered in most cases as personal data [2]. Thus, it is covered by privacy regulations and data protection acts. Moreover, the possibility of replicating biometric traits or traces can increase the risk for identity theft [START_REF] Kiltz | Printed fingerprints: a framework and first results towards detection of artificially printed latent fingerprints for forensics[END_REF]. Hence, in some legislations, such as in Germany [3], the public usage of biometric data sets is challenging since certain rights must be granted to the person concerned. Furthermore, it is expected that the reform of the European data protection legislation will strengthen individual rights as well [START_REF]How does the data protection reform strengthen citizens' rights?[END_REF], leading to higher barriers in creating and using public biometric data sets. In contrast to similar fields such as biometric systems where biometric data and templates can be transferred and stored in an encrypted or obfuscated manner (e.g. in fingerprint authentication [START_REF] Barni | Privacy-preserving fingercode authentication[END_REF]) to ensure privacy, an access to the original raw fingerprint data is necessary for research purposes and various evaluations. Moreover, in forensics an access to the fingerprint image is necessary because the examiner is responsible for a final decision.

We address this challenge by proposing a data set of contact-less acquired printed artificially created latent fingerprints for the evaluation of forensic techniques. In doing so, we want to generate latent fingerprints as realistic as possible while retaining the ability to detect them as motivated by Kiltz et al. [START_REF] Kiltz | Printed fingerprints: a framework and first results towards detection of artificially printed latent fingerprints for forensics[END_REF]. To avoid any privacy implications artificial fingerprint patterns are generated using SFinGe [START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF] and afterwards printed using a Canon Pixma iP4950 ink-jet printer with the technique of Schwarz [START_REF] Schwarz | An amino acid model for latent fingerprints on porous surfaces[END_REF]. The intention of SFinGe is the creation of fingerprints for the evaluation of biometric systems. For that, it is supported to add noise, distortions and sensor influences. However, in forensics latent fingerprints can be found on various substrates that potentially require the acquisition with different sensors. The printing process ensures that the fingerprint pattern can be applied to a broad variety of such substrates and thus creating realistic conditions for forensic investigations. In our first experiments, the samples are digitized using a Keyence VK-x110 series confocal laser scanning microscope which captures topography and intensity data using a laser and color data by using a CCD camera. Furthermore, a color-intensity image is generated by combining the color data and the laser data. Since this measurement device stores the digitized trace within a proprietary format, we convert the image data for the public database into simple binary objects consisting of an 8 bit header with the width and the height of the data field followed by either a field of 32 bit little endian floating point values for topography and laser intensity data or 32 bit ARGB values for color and color-intensity data. This allows for analyzing the data with various tools. The four binary objects are accompanied with a meta-data file with the sensor and its parameters which are necessary for the interpretation of the data.

In our poster, we show and discuss the challenges of the creation of the data set on the foundation of 50 samples. In particular, the reproducibility of the printing results and the overall realism of the acquired fingerprints need to be further enhanced in order to replace real biometric traces from the human. The reproducibility of the printing results is primarily affected by the reliability of the printing process. Nozzles or the entire print head tend to be clotted [START_REF] Kiltz | Printed fingerprints: a framework and first results towards detection of artificially printed latent fingerprints for forensics[END_REF] since the artificial sweat has different properties than the manufacturer ink. The realism of the printed latent fingerprints trace is also negatively affected by this effect leading to a visible pattern of amino acid dots instead of continuous ridge line impressions. Hence, in order to address those challenges, we propose a work around to enhance the ridge clarity within the digitized data which connects neighboring dots to create continuous ridges. The method applies a hit or miss operator as a first processing step leading to a binarized image of multiple dots of amino acid. In the second step a triangulation is used to connect the dots. A threshold for the maximum distance between dots is applied to avoid connecting dots between different ridges. The result is a binarized fingerprint pattern similar to the original sample. However, this approach would likely not work on non-smooth or textured surfaces due to the surface noise. Furthermore, such a processing is unsuitable to achieve realistic traces.

For quality measurement, we adapt a correlation based measure from [START_REF] Sturm | High quality training materials to detect printed fingerprints: Benchmarking three different aquisition sensors producing printing templates[END_REF] to determine whether the digitized trace and the original pattern are sufficiently similar. It is based on the Pearson product-moment correlation coefficient of the images. However, this requires an exact alignment and scaling of the data.

In future work the reliability of the printing process and the realism of the printed patterns need to be increased in order to create usable data sets for forensic sciences.

Acknowledgement

The work in this paper has been funded in part by the German Federal Ministry of Education and Science (BMBF) through the Research Program under Contract No. FKZ: 13N10818 and FKZ: 13N10816.


Jutta Hämmerle-Uhl

Michael Pober

Andreas Uhl
email: andreas.uhl@sbg.ac.at

Towards a Standardised Testsuite to Assess Fingerprint Matching Robustness: The StirMark Toolkit -Cross-Feature Type Comparisons

We propose to establish a standardised tool in fingerprint recognition robustness assessment, which is able to simulate a wide class of acquisition conditions, applicable to any given dataset and also of potential interest in forensic analysis. As an example, StirMark image manipulations (as being developed in the context of watermarking robustness assessment) are applied to fingerprint data to generate test data for robustness evaluations, thereby interpreting certain image manipulations as being highly related to realistic fingerprint acquisition conditions. Experimental results involving three types of fingerprint features and matching schemes (i.e. correlation-based, ridge feature-based, and minutiaebased) applied to FVC2004 data underline the need for standardised testing and a corresponding simulation toolset.

Introduction

One of the big issues in fingerprint recognition is robustness of recognition accuracy against sample image quality degradation [START_REF] Alonso-Fernandes | Fingerprint recognition[END_REF][START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF]. The performance of a fingerprint recognition system is usually heavily affected by fingerprint image quality. A wide variety of factors influence the quality of a fingerprint image: Skin conditions (e.g. , dryness, moisture, dirt, cuts and bruises), sensor conditions (e.g. , dirt, noise, size), and other acquisition conditions like user cooperation or crime scene preservation in forensic settings, etc. Some of these factors are inevitable and some of them change over time. Poor quality images often result in spurious and missed features, therefore decreasing the recognition accuracy of the overall system.

However, the different levels at which fingerprint features are extracted [START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF] and the different feature types extracted at these levels influence the impact of quality degradations on recognition performance in various ways. Moreover, there is interplay among different types of feature extraction and acquisition technology / conditions such that it is not clear a priori which type of feature extraction is favourable under which conditions. Therefore, it is essential to provide reliable methodology to comparatively assess fingerprint recognition robustness under varying conditions. This issue is classically tackled from two sides: First, benchmarking frameworks have been established, which facilitate a common evaluation basis with standardised protocols for various fingerprint recognition algorithms, see e.g. the fingerprint verification contests (FVC [START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF]), independent suggestions like [START_REF] Noviyanto | A comparison framework for fingerprint recognition methods[END_REF], and the BioSecure evaluation framework [START_REF] Alonso-Fernandes | Fingerprint recognition[END_REF]. Second, usually these frameworks rely on the establishment of test data which are used to compare the different algorithms on a common basis. A very good example, specifically focusing onto the robustness issue, are the FVC data sets. FVC2002 (only i) & iv)) and FVC2004 data have been acquired in a way to introduce higher intraclass variation by i) putting the finger at slightly different vertical position, ii) applying low or high pressure against the sensor, iii) exaggerating skin distortion and rotation, and iv) drying or moistening fingers. For FVC2006, the population was chosen to be more heterogeneous, including manual workers and elderly people.

While the availability of these and similar datasets is a significant achievement, the data collection and database establishment is tedious work. Moreover, if additional acquisition conditions should be considered which have not been included into the original dataset, re-enrolment is required, involving complicated procedures for getting the original people back to enrolment. Also, it is hard to compare the different quality degradations from dataset to dataset (e.g. FVC, MCYT, BIOMET, MSU), since usually, there is no standardised manner to generate the acquisition conditions applied. Therefore, the experimental results of recognition algorithms in case applied to different datasets are hardly comparable and the results shown in many papers are difficult to interpret.

A strategy to cope with the various problems of generating natural datasets is to generate synthetic fingerprints, the SFinGe [START_REF] Cappelli | Synthetic fingerprint generation[END_REF] being the most well known tool for doing this. The generated fingerprints have proven to be highly realistic and serve as a sensible tool to generate large datasets for benchmarking. While SFinGe also allows to apply some manipulations to the images, e.g. noise insertion, translations, rotations and uses a skin deformation model, a simulation of specific sensor types is not foreseen.

In the area of robust watermarking, a similar situation could be observed -while of course the notion of robustness is different in watermarking (means basically the ability of embedded data to withstand common image manipulations or unspecific attacks), the general problem was of comparable nature: Each watermarking scheme presented was evaluated on a specific dataset, where especially the types of introduced image manipulations and their respective extent to prove robustness varied from paper to paper, thus making a comparison of techniques impossible. To cope with the situation, standardised benchmark toolsets consisting of a collection of parameterisable image manipulations have been created, including StirMark [START_REF] Kutter | Fair evaluation methods for image watermarking systems[END_REF] and CheckMark [START_REF] Meerwald | Attacks, applications and evaluation of known watermarking algorithms with Checkmark[END_REF]. This enabled developers and authors to apply these manipulations to publicly available datasets thus making their results comparable.

In recent work [START_REF] Hämmerle-Uhl | Towards standardised fingerprint matching robustness assessment: The stirmark toolkit -cross-database comparisons with minutiae-based matching[END_REF], we have proposed to establish a standardised tool in fingerprint recognition robustness assessment, which is able to simulate a wide class of acquisition conditions, applicable to any given dataset. As an example, StirMark image manipulations have been applied to fingerprint data to generate test data for robustness evaluations. Since these manipulations can be applied to any dataset, the effect of manipulations on data originating from different sensors and acquisition conditions can be studied with respect to recognition accuracies of the algorithms used. Contrasting to previous work [START_REF] Hämmerle-Uhl | Towards standardised fingerprint matching robustness assessment: The stirmark toolkit -cross-database comparisons with minutiae-based matching[END_REF], where experiments have been restricted to fingerprint matchers of minutiae type, here we focus on fingerprint matchers relying on very different fea-ture types and compare the obtained results. Additionally, different distortion types are investigated as compared to [START_REF] Hämmerle-Uhl | Towards standardised fingerprint matching robustness assessment: The stirmark toolkit -cross-database comparisons with minutiae-based matching[END_REF].

In Section 2, we explain the StirMark image manipulations and discuss the interpretation of those procedures in the context of fingerprint acquisition and quality, respectively. Section 3 briefly reviews the fundamental ideas behind three very different types of fingerprint feature extraction and matching techniques which are subsequently used in experiments. Experimental results are presented in Section 4 where we shortly describe the employed FVC2004 dataset and experimental conditions with respect to evaluation protocols. Finally, we present fingerprint verification results generated on the FVC2004 dataset processed with a set of StirMark image manipulations with increasing strength. Section 5 concludes the paper.

The StirMark Toolkit

The StirMark Benchmark is a generic benchmark test for evaluating the robustness of digital image watermarking methods, developed by Fabien A. P. Petitcolas et al. [START_REF] Kutter | Fair evaluation methods for image watermarking systems[END_REF][START_REF] Petitcolas | Attacks on copyright marking systems[END_REF]. The basic idea behind the robustness tests in the StirMark benchmark is, that a digital watermark within an image can be attacked and possibly rendered useless, by introducing small, ideally imperceptible perturbations into the marked image. To be suitable for application in a common generic benchmark, the specific types of perturbations are pre-defined and the respective intensity is adjustable via a given set of parameters. The corresponding software is currently available "StirMark Benchmark 4.0" at http: //www.petitcolas.net/fabien/watermarking/stirmark/. A related, also watermarking-robustness focused toolset is CheckMark [START_REF] Meerwald | Attacks, applications and evaluation of known watermarking algorithms with Checkmark[END_REF] which could be used by analogy, however, it is less well supported.

In the following, we describe the set of StirMark image manipulations that has been selected for this study. We explain the way each manipulation is defined, how it is parameterised to achieve varying strength of the manipulation, and we discuss which realistic fingerprint acquisition condition could be modelled by applying the manipulation to fingerprint sample images. Thus, only a subset of the complete range of StirMark tests is used, which simulate "natural" perturbations -in other words, tests, whose influence on fingerprint images creates perturbed versions thereof, that resemble cases appearing in real-life fingerprint application scenarios. It has to be noted that we do not consider all manipulations even if they would be suitable candidates -e.g. , JPEG compression, although contained in the StirMark suite, is not applied here since there have been quite some studies focusing on the effects of JPEG compression in fingerprint recognition [START_REF] Funk | Evaluation of image compression algorithms for fingerprint and face recognition systems[END_REF][START_REF] Mascher-Kampfer | Comparison of compression algorithms' impact on fingerprint and face recognition accuracy[END_REF]. Example images shown have been generated by applying StirMark tests with increasing intensity to a sample image taken from the FVC2004 database DB1 (see Section 4.1).

Additive Noise is introduced to the input image. The amount of noise is adjustable and can range from "none" to "completely random image", controlled by a single parameter, ranging from 0 to 100. Fig. 1 shows examples for increasing noise content.

This test is intended to simulate noise, that might "naturally" appear in fingerprint sample images. Possible causes for this kind of noise could be actual dust on the contact area during acquisition of the imprint, graining caused by the acquisition equipment itself (sensor noise) or any other kind of systematic error introduced during processing, transmission and/or storage of the collected images (e.g. a grainy surface the latent fingerprint has been taken off can cause noise in forensics).

Median Cut Filtering This test applies a median cut filter to the input image. The size of the filter mask can be set (height and width of the filter take the same value and only odd-valued dimensions are accepted), the upper limit is a size of 15, thus resulting in a 15 × 15 filter. Fig. 2 shows examples for medium filter sizes. The Median Cut Filtering test is used to simulate smudgy fingerprints, as they are common in real-life applications, for example when the fingertip is too moist during the acquisition by the scanner. The result is a certain amount of blur to the image, but additionally it also corrupts the clarity of the ridge-and-furrow structure of the imprint.

Remove Lines and Columns This tests removes rows and columns from a given image at the specified frequency k -"remove 1 line in every k lines." It has to be noted that the line removal operation naturally also reduces the size of the output image. Fig. 4 illustrates the effect of this test when applied to fingerprint images.

This test aims to simulate errors in fingerprint images, that occasionally occur during fingerprint acquisitions, in case the scanner is not able to read the fingerprint in its entirety, but misses/skips certain lines. Especially sweep sensors are prone to this kind of complications. Two corresponding examples can be found in Fig. 3.a. Rotation is a very typical, not to say -omnipresent -challenge for fingerprint matching, as in very few cases a finger will be presented twice in exactly the same orientation to the contact area during image acquisition. Thus, this test provides the means for comparison of the rotational alignment capabilities of the various fingerprint matchers.

Affine Transformation is a generic manipulation for arbitrary affine image transformations. The user specifies the parameters a, . . . , f of the inverse transformation matrix of the form:

x y = a b c d x y + e f
The application of affine transformations to fingerprint images is intended to simulate distortions of the entire finger imprint, that can appear in real-life situations during the fingerprint acquisition, depending on the way, the finger is pressed on the contact area. As special cases, we consider shearing and stretching.

Stretching A certain stretching might appear in the finger imprint, when the amount of force applied while pressing the finger on the contact area is large or larger than usual. Considering the forensic scenario, stretching of a fingerprint appears if the finger was imprinted on a soft or flexible surface.

Shearing in Y-direction is parameterised by setting b = e = f = 0 and a = d = 1, while configurations 1 -6 set c to the values {0.05, 0.10, 0.15, 0.20, 0.25, 0.30}. Configurations 1, 4, and 6 are shown in Fig. 7. A shearing effect can occur, when the force that is exercised while pressing the finger on the contact area is not exerted perpendicular to this area. For example, when the finger is presented, with the user pushing rather in direction to the upper-right corner of the sensor, than straight downwards.

Small Random Distortions The StirMark test. Being a combination of several basic manipulations (i.e. random minor geometric distortion followed by resampling and interpolation, a transfer function to emulate analog/digital converter imperfections, global "bending", high frequency displacement, and JPEG compression), this test originally aims to simulate a resampling process, i.e. the errors introduced when printing an image

Fingerprint Feature Types and Matching

An interesting question is to ask if a certain type of fingerprint feature extraction method has particular strong points or weaknesses when dealing with a specific type of acquisition condition. In order to get a sensible answer we will consider significantly different types of fingerprint feature extraction schemes, based on the discriminative characteristics fingerprint do contain [START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF]. On a global level, the overall ridge flow structure with the embedded singular points (i.e. loops, whorls, deltas) can be perceived. Going into more detail, looking at the ridge and furrow structure in the fingerprint from a more localised point of view, then characteristics like orientation and frequency of the local ridge flow can be observed. On a local level, details of the ridge shapes themselves can be determined. The most important ones are ridge endings and ridge bifurcations which are subsumed in the term minutiae. Looking even closer at a fingerprint, then also diminutive intra-ridge features are detectable -the finger's sweat pores. However, their respective pattern can only be determined in sufficiently good quality in high-resolution fingerprint images of 1000dpi and above. Now depending on which type of features is used to determine similarity, fingerprint matching approaches can be classically categorised into one of the following classes:

Correlation-Based Matcher These approaches use the fingerprint images in their entirety, the global ridge and furrow structure of a fingerprint is decisive. Images are correlated at different rotational and translational alignments, image transform techniques may be utilised for that purpose. Ridge Feature-Based Matcher Matching algorithms in this category likewise deal with the overall ridge and furrow structure in the fingerprint, yet in a localised manner. Characteristics like local ridge orientation or local ridge frequency are used to generate a set of appropriate features representing the individual fingerprint. Minutiae-Based Matcher The set of minutiae within each fingerprint is determined and stored as list, each minutia being represented (at least) by its location and direction. The matching process then basically tries to establish an optimal alignment between the minutiae sets of two fingerprints to be matched, resulting in a maximum number of pairings between minutiae from one set with compatible ones from the other set.

The minutiae-based approach is the most common and most widely used method for fingerprint matching. Of course, there also exist fingerprint matching algorithms, that combine some or all of the above listed techniques (termed hybrid), aiming to combine the particular strong points of each individual approach into a single, more precise matcher (e.g. by using minutiae alignment to compensate for rotation and translation but use ridge-based features for actual matching [START_REF] Ross | A hybrid fingerprint matcher[END_REF]).

As a representative of the correlation-based matcher type we use a custom implementation of the phase only correlation (POC) matcher [START_REF] Koichi | A fingerprint matching algorithm using phase-only correlation[END_REF]. The POC of two images is computed by calculating the normalised cross spectrum (or cross-phase spectrum) from the DFT of the two images. The POC is then obtained by taking the inverse DFT of the normalised cross spectrum. Properties like shift invariance, brightness invariance, and high immunity to noise make POC an interesting candidate for biometric matching since template alignment is eased.

The algorithm first conducts rotational alignment by computing POC for rotated fingerprints in a range of ±20 • with a step-width of 1 • , employing bi-cubic interpolation. The rotated version with the highest POC response is used in subsequent matching. Displacement alignment is performed according to the position of the POC peak as computed before, subsequently probe and gallery images are cropped to the common area of intersection (containing fingerprint data), as the non-overlapping regions lead to uncorrelated noise in the POC function. Finally, a band-limited version of the POC is computed. The idea is to limit the frequency spectrum involved in matching to only those areas, that are strongly related with the actual fingerprint information -especially the inherent elliptical frequency band originating from the ridge pattern -thereby excluding the interfering components in the high frequency areas. The final matching score is then established by summing up the P highest peaks (Ito et al. suggest P = 2, while we found P = 1 to perform better for two out of three databases) of the bandlimited POC function. It has to be noted that fingerprint enhancement as used in the subsequent algorithm [START_REF] Hong | Fingerprint image enhancement: Algorithm and performance evalution[END_REF] also improves matching results for two out of three databases and is used correspondingly.

As a representative of the ridge feature-based matcher type we use a custom implementation of the fingercode approach (FC) [START_REF] Jain | Filterbank-based Fingerprint matching[END_REF], in particular we follow improvements as suggested by Ross et al. [START_REF] Ross | Fingerprint matching using feature space correlation[END_REF][START_REF] Ross | A hybrid fingerprint matcher[END_REF] and de Sa et al. [START_REF] De Sá | Improved fingercode matching function[END_REF] which avoid the usage of a circular tessellation around a core point, and partially apply the fingerprint enhancement strategy as suggested by Hong et al. [START_REF] Hong | Fingerprint image enhancement: Algorithm and performance evalution[END_REF].

As a first stage, normalisation is applied by pixel-wise adjusting the gray-levels to obtain an image with pre-specified mean and variance. Based on the output of a Marr-Hildreth operator, a least square estimate of the local ridge orientation in blocks of 16 × 16 pixels is established subsequently. A low-pass filter is used to smoothen the result which is called orientation image. The normalised fingerprint image and the orientation image are used to create the frequency image, representing the local ridge frequency. In an oriented window the x-signature is calculated per block by projecting the respective gray-level values of the normalised image onto the length of the window which is placed in a direction orthogonal to the ridge orientation of the block. The frequency can be determined by taking the reciprocal of the average distance between peaks in the x-signature. Interpolation of invalid blocks (i.e. those where the x-signature did not form a discrete sinusoidal-shape wave) is done with a discrete Gaussian kernel. Contrasting to the original papers, we use high frequency together with a check of an admissible dynamic range as criteria to determine blocks which actually represent useful fingerprint texture, thus declared foreground blocks to be further used in matching.

For actual feature extraction, a Gabor filter bank consisting of eight separate Gabor filters, each oriented at a different constant angle is convolved with the image, examining the varying responses of the ridges and furrow structure to the differently oriented filters. This results in eight distinct filtered images for each of which a standard deviation in a 16 × 16 neighbourhood is computed per pixel, the union over all eight images is called Standard Deviation Map. If the fingerprint image is intended for database registration (i.e. enrolment), this map is subsampled by a factor of 16 to generate ridge feature images, the union of which is called Ridge Feature Map. Translational alignment is achieved by computing correlations among differently displaced ridge feature images in the Fourier domain and compensating the shift identified by maximal correlation, rotational alignment is done by storing ridge feature maps of rotated fingerprint versions in an angular range of [-20 • , +20 • ] with a step-width of 1 • , and again taking the version with the maximal correlation. The matching score is obtained by computing Euclidian distance among aligned ridge feature map entries.

As a representative of the minutiae-based matcher type we use mindtct and bozorth3 from the "NIST Biometric Image Software" (NBIS) package (available at http:// fingerprint.nist.gov/NBIS/) for minutiae detection and matching, respectively. mindtct generates several image quality maps and binarises the fingerprint images as a first step. Subsequently, minutiae are detected in admissible areas by detecting specified pixel patterns, followed by false minutiae removal and minutiae quality assessment. bozorth3 is designed to be rotation and translation invariant and provides a matching score based on traversing certain inter-fingerprint compatibility tables.

A comparison of the three fingerprint recognition schemes with respect to recognition performance on the three "natural" FVC2004 databases (without StirMark manipulations being applied) is provided in the subsequent subsection.

Experiments

We first provide details about the employed FVC2004 data set. Subsequently, experimental results are presented and discussed, covering questions of robustness of recognition accuracy against various StirMark manipulations and in particular a comparison of the behaviour of the different feature types in that respect.

Experimental Settings

We employ three out of four databases provided for the FVC2004 [START_REF] Maio | FVC2004: Third Fingerprint Verification Competition[END_REF] as shown in Table 1, each with 500dpi resolution (DB3 with 512 dpi). It does not make too much sense to include the fourth dataset of FVC2004 (although it would be possible in principle of course) since it consists of synthetically generated fingerprint images (SFinGe [START_REF] Cappelli | Synthetic fingerprint generation[END_REF] was used). In order to model real-life distortions for these data, a much more sensible way would be to apply respective distortion "operations" already during the generation process of the synthetic fingerprints instead of applying them ex post to the final data.

The procedure for performance evaluation is basically the same in all FVCs, from 2000 to 2006. We follow this specification by conducting all genuine tests and the required impostor tests for DB1, DB2, and DB3, thereby obtaining FNMR and FMR as required. Finally, equal error rate (EER) is determined and used as measure for recognition accuracy to compare different settings. Table 1 also shows the result when applying the three considered feature types to the FVC2004 test data without having applied any StirMark manipulations, but already within the StirMark framework.

It can be clearly seen that the ranking of the three feature types is heavily dependent on the used dataset. Each type of feature extraction is ranked first for a single dataset, while only FC is never ranked third. Only when considering DB2, the performance is really close.

Experimental Results

Fig. 9.a shows the influence of additive noise on recognition performance considering DB2. Especially for a higher degree of noise content FC clearly shows the best robustness, POC is also better compared to NBIS for this setting, but clearly inferior to FC. In Fig. 9.b we see that the situation changes when considering a different dataset, DB3 in this example. NBIS recognition results are hardly affected even by a significant amount of noise, entirely contrasting to the results obtained on DB2. Also, the ranking between FC and POC is swapped, POC results are also quite stable while FC recognition accuracy severely suffers from high noise content.

It is also interesting to note that on unperturbed data, FC is superior to POC, while POC is getting clearly superior under the influence of more noise being present. This effect underlines the need for systematic robustness testing in a feature-type comparative manner.

This example overall shows that even feature-type ranking results with respect to robustness achieved on a specific database cannot be generalised but need to be verified for each single dataset. This nicely illustrates the general need for systematic testing and evaluation tools. Fig. 10.a shows robustness results with respect to median cut filtering on DB1, which is another example that ROC performance on unperturbed data cannot predict robustness properties. While NBIS is clearly superior to POC on the original data, it gets inferior when introducing significant mean cut filtering. In Fig. 10.b very high stability of NBIS and FC against line removal is shown, while POC suffers considerably in case the amount of missing lines is increasing.

One of the most important robustness issues is fingerprint rotation, since this effect is omnipresent in sample acquisition. Fig. 11 The first thing to note is the excellent robustness of NBIS against rotation for both datasets. FC and POC are both affected, however, the extent of result degradation is much larger for DB2 as compared to DB1. For example, based on experimental results obtained on DB1, one would have predicted EER≈12.5 for POC on DB2 under 20 • rotation, in fact we observe EER to be 18.08 which almost doubles EER as compared to not manipulated data. Again, the need for dedicated testing for each sensor type is confirmed.

Affine transformations also model a class of very important acquisition conditions. Table 2 shows the catastrophic effect of stretching in a single dimension only. No feature extraction type can handle this type of distortion in a sufficient degree. Obviously, there is need to introduce stretching robustness into feature sets.

Shearing robustness as illustrated in Fig. 12.a is shown to be much better as compared to stretching. Apart from very strong distortions, NBIS and FC can handle shear- Finally, robustness results against a combination of manipulations are shown in Fig. 12.b. These rather localised distortions can be handled quite well by NBIS and FC, at least up to some medium extent. POC, similar to its sensitivity against affine transformations, exhibits steadily increasing EERs for increasing strength of the distortions.

Conclusion

We have employed the StirMark benchmark testsuite to generate large scale test data to assess robustness of fingerprint recognition schemes in various acquisition conditions. Experimental results confirm a significant variability of robustness properties across different types of fingerprint feature extraction schemes and across different datasets considered. For example, we have observed significant impact of Median Cut Filtering and Affine transforms like Stretching and Shearing for almost all feature types and datasets, while Noise Insertion is tolerated well by some feature types (FC and POC on DB1 and NBIS and POC on DB3) but leads to considerable impact for all techniques on DB2. As compared to our previous work [START_REF] Hämmerle-Uhl | Towards standardised fingerprint matching robustness assessment: The stirmark toolkit -cross-database comparisons with minutiae-based matching[END_REF] where only minutiae-based matching schemes have been compared, we see even larger variability in this present work when comparing matching results relying on entirely different feature extraction schemes.

These results underline the need for a standardised tool in fingerprint recognition robustness assessment, which is able to simulate a wide class of acquisition conditions, applicable to any given dataset.

While we have motivated the interpretation of several image manipulations contained in the StirMark benchmark as being closely related to a wide class of fingerprint acquisition conditions (including some forensic settings), these experiments only represent a first step. In fact, the aim is to establish a benchmark explicitly designed for systematic fingerprint recognition robustness evaluations, where these current StirMark based results can serve as first guidelines to model actual fingerprint acquisition conditions more accurately.

Fig. 1 .

 1 Fig. 1. Examples for the Additive Noise test, applied to an image from DB1 (ID 91 2).

Fig. 2 .

 2 Fig. 2. Examples for the Median Cut Filtering test, applied to an image from DB1 (ID 91 2).

Fig. 3 .

 3 Fig. 3. Examples for distortions from actual acquisition problems.

Fig. 4 .

 4 Fig. 4. Examples for the Remove Lines test, applied to an image from DB1 (ID 91 2).

Rotation

  rotates the image by a given angle, the set of angular values that will be inspected in the experiments is {-20 • , -15 • , -10 • , -5.5 • , -5 • , 7 • , 7.5 • , 13 • , 18 • , 20 • }. Examples for rotations of -15 • , -5.5 • , and 20 • can be seen in Fig. 5.

Fig. 5 .

 5 Fig. 5. Examples for the Rotations Lines test, applied to an image from DB1 (ID 91 2).

  in X-direction is parameterised by setting b = c = e = f = 0 and d = 1, while configurations 1 -8 set a to the values {1.035, 1.070, 1.105, 1.140, 1.175, 1.210, 1.280, 1.350}. Configurations 1, 5, and 8 are shown in Fig. 6.

Fig. 6 .

 6 Fig. 6. Examples for the Affine Transformations -Stretching in X-Direction test, applied to an image from DB1 (ID 91 2).

Fig. 7 . 2 Fig. 8 .

 728 Fig. 7. Examples for the Affine Transformations -Shearing in Y-Direction test, applied to an image from DB1 (ID 91 2).

Fig. 10 .

 10 Fig. 10. EERs for robustness tests conducted on sample image databases DB1 and DB2, respectively.

Fig. 12 .

 12 Fig. 12. EERs for robustness tests conducted on sample image databases DB1 and DB2, respectively.

Table 1 .

 1 Details on the fingerprint images in the three employed FVC2004 databases and EERs for the considered fingerprint recognition schemes when applied to the original, "undistorted" sample image databases.

	Sensor Type	Model	Image Size NBIS (%) FC (%) POC (%)
	DB1 Optical	CrossMatch V300	640 × 480 14.81	12.54 22.60
	DB2 Optical	Digital Persona U.are.U 400 328 × 364 11.12	9.60	9.69
	DB3 Thermal Sweep Atmel FingerChip	300 × 480	6.68	8.98	15.07

  compares the results for DB1 and DB2. EERs for Rotation test conducted on sample image databases.

	Rotation NBIS (%) FC (%) POC (%)	Rotation NBIS (%) FC (%) POC (%)
	unperturbed 14.81	12.54 22.60	unperturbed 11.12	9.60	9.69
	-15	13.00	14.74 24.34	-15	11.00	14.13 14.22
	-5.5	12.94	12.90 22.67	-5.5	11.28	12.04 10.89
	13	13.05	13.63 23.79	13	10.59	13.57 13.01
	20	13.41	15.44 26.18	20	10.94	16.27 18.08
		(a) DB1		(b) DB2
	Fig. 11.

Table 2 .

 2 EERs for Affine Transformations -Stretching in X-Direction test conducted on sample image database DB3.

		Configuration NBIS (%) FC (%) POC (%)
		unperturbed	6.68	8.98	15.07
			2	7.70	10.99 23.89
			4	11.13	13.90 31.72
			6	14.14	17.98 37.20
			8	23.38	25.79 42.69
	ing quite well, while POC exhibits steadily decreasing EERs for an increasing amount
	of shearing.
	Configuration NBIS (%) FC (%) POC (%)	Factor NBIS (%) FC (%) POC (%)
	unperturbed	14.81	12.54 22.60	unperturbed 11.12	9.60	9.69
	1	13.85	12.57 22.64	0.6	10.78	12.42 10.89
	2	13.88	12.76 24.79	1.0	11.35	12.34 11.49
	3	14.88	13.30 27.43	1.8	11.75	12.40 13.23
	4	16.26	14.15 29.90	2.6	12.57	12.61 16.34
	5	17.96	14.71 37.73	3.4	13.23	13.57 19.00
	6	21.46	15.82 40.22	4.2	14.82	14.05 21.96
	(a) Shearing in Y-Direction		(b) Small Random Distortions


Edward Caprin

Yan Zhang

SocACL: An ASP-Based Access Control Language for Online Social Networks

Keywords: Answer Set Programming, Online Social Networks, privacy, access control, Attribute-Based Access Control

Online Social Networks (OSNs), such as Facebook, encourage their users to disclose significant amounts of personal information to facilitate connecting and sharing content with other users. This has resulted in some OSNs holding vast amounts of information about their users; all of which is readily available via their profile page. As such, OSNs are particularly vulnerable to privacy breach attacks. With the impact these breaches varying from simply embarrassing the user, to negatively influencing the decision of a potential employer, identity theft and even physical harm it is important that these breaches are addressed. In this research we approach privacy management in OSNs as an access control problem, proposing a fine-grained, formal Attribute-Based Access Control (ABAC) language; SocACL (Social Access Control Language). SocACL is based on Answer Set Programming (ASP) and allows for policy specification using the most abundant sources of information available in OSNs; user attributes and relationships.

Introduction

Online Social Networks (OSNs), such as Facebook and LinkedIn, encourage their users to disclose significant amounts of personal information to facilitate connecting and sharing content with other users. This has resulted in some OSNs holding vast amounts of information about their users; all of which is readily available via their profile page. As such, OSNs are particularly vulnerable to privacy breach attacks [START_REF] Gao | Security Issues in Online Social Networks[END_REF]. With the impact these breaches varying from simply embarrassing the user, to negatively influencing the decision of a potential employer, identity theft and even physical harm it is important that these breaches are addressed. OSN operators have responded to privacy concerns by providing user customisable privacy settings. However, these have proven ineffective, often resulting in settings that do not reflect the intentions of the user [START_REF] Madejski | A Study of Privacy Settings Errors in an Online Social Network[END_REF]. This is in part due to the coarse-grained nature of the information on which these settings are based. In this research we approach privacy management in OSNs as an access control problem, proposing a fine-grained, formal Attribute-Based Access Control (ABAC) language; SocACL (Social Access Control Language). SocACL is based on Answer Set Programming (ASP) and allows for policy specification using the most abundant sources of information available in OSNs; user attributes and relationships.

Suppose we have some hypothetical OSN with a member Alice that has a coworker Bob (eq. ( 1)) and considers this relationship non-sensitive. She is envious of people enrolled at the prestigious University of Learning (eq. ( 2)), treating this attribute as non-sensitive and a non-primary instance.

alice says Me • relationship • coworker • bob : ns;

(1)

alice says Me • envious • Other : ns • np if Other • enrolled • "UoL"; (2)
Below we find the ASP translation of eq. ( 1) and ( 2) respectively. For eq. ( 3) and ( 4) arity 1 denotes the principal providing this attribute. In eq. ( 4) arity 1, 4, and 5 of "enrolled" are underscores, the anonymous variable of DLV used as a placeholder for values that do not matter for this rule. Meaning that for "enrolled" it does not matter who provides this attribute (arity 1). Arities 4 and 5 are the SF and PIF respectively, since these are used only by the SocACL negotiation process it does not matter what their values are when used as decision criteria.

relationship(alice, alice, bob, coworker, ns).

(3) envious(alice, alice, Other, ns, np) ← enrolled( , Other, "UoL", , ). ( 4)

Related Work and Conclusion

With relationships an integral part of any OSN there have been various access control framework proposals based on them. Relationship-Based Access Control (ReBAC) [START_REF] Fong | Relationship-based access control: protection model and policy language[END_REF] and its supporting language specifies policies in terms of the accessors relationship with the owner. ReBAC's modelling of relationships differs from that of SocACL. ReBAC relationships can be composed from "smaller" relationships, e.g. "grandparent" can be composed from "parent parent", which can also be inverted. With SocACL allowing for distance based relationships these compositions pose a problem; is "grandparent" a 1st-or 2nd-degree relationship? Instead, SocACL allows for indirect relationships to be expressed as a sequence of direct relationships at each "hop". Furthermore, SocACL relationships can be used in conjunction with attributes and the aggregate operations count, sum, min and max. This allows for rules such as Allow access to "friends", with red hair, which have 5 "friends" in common with me; something not possible with ReBAC.

In SocACL we have an access control language with features tailored to OSNs. SocACL utilises the two most abundant sources of information in OSNs as decision criteria; information about the user and their relationships with others.

Answer Set Programming (ASP)

The semantics of SocACL is defined as a translation to ASP. ASP is a form of declarative programming well suited to representing domain specific knowledge [START_REF] Zhang | Knowledge Representation, Reasoning and Declartive Problem Solving[END_REF], making it ideal for capturing the wide range of features found in OSNs. An ASP program is a finite set of rules that describes some set of knowledge and are used with inference engines, such as DLV [START_REF] Leone | The dlv system for knowledge representation and reasoning[END_REF], to generate sets of conclusions that can be inferred from the program called answer sets, on which we base SocACL's policy evaluation system.

SocACL EBNF

NAMEs start with a lowercase letter and can contain letters, numbers and underscores, while VARs start with a uppercase letter. SUB and OBJ is a NAME or VAR that identifies a subject or an object. SF and PIF are the sensitivity flag and primary instance flag, respectively. These are used during the SocACL negotiation process, which is not covered in this paper.


Sabah A Jassim
email: sabah.jassim@buckingham.ac.uk

Face Recognition from Degraded Images -Super Resolution Approach by Non-Adaptive Image-Independent Compressive Sensing Dictionaries

Keywords: Compressive Sensing, Super-resolution, RIP dictionaries, Face recognition, CS classifiers

In recent years, the emergence of the new paradigm of compressive sensing (CS) has led to the development of innovative image/signal processing and analysis tools that can be exploited to efficiently deal with serious challenges in pattern recognitions. This paper is concerned with the use of CS tools and dictionaries for face recognition, and in particular when dealing with uncontrolled conditions, e.g. faces captured at a distance in surveillance scenarios or in post-rioting forensic, whereby the images are severely degraded/blurred and of low-resolution. We present the results of our recent investigations 1 into the construction of over-complete dictionaries that recover super-resolved face images from any input low-resolution degraded face image. These results demonstrate that non-adaptive image-independent implicitly designed dictionaries that guarantee the recovery of sparse signals achieve face recognition accuracy levels and yield significant recognition rates that are as good as if not better than those achieved by a recently proposed image-based learnt dictionaries. We shall also show that a variety of random dictionaries known to satisfy the Restricted Isometry Property (RIP), achieve similar accuracy rates, and thereby removing the need for training images. The high quality of the super-resolved images provides great potential for forensics and crime/terrorism fighting.

Introduction

Automatic face recognition in uncontrolled conditions and in particular when dealing with surveillance tasks is far from reliable due to the degraded nature of captured images. Image resolution enhancement is deemed necessary for face recognition, where the camera is at a distant from imaged face yielding small low resolution, blurred and low-quality image for matching. Image degradation results from a variety of recording conditions: subject on the move, unstable sensors, out of focus optical system, or abnormal weather and atmospheric conditions such as thermal waves.

Recognising faces when matching low-resolution (LR) degraded small images against a gallery of high-resolution good size face images, is traditionally dealt with by preprocessing procedures primarily using the so called super-resolution methods which aims to reconstruct a higher resolution version of the LR image. Hennings-Yeomans et al [START_REF] Hennings-Yeomans | Simultaneous super-resolution and feature extraction for recognition of low-resolution faces[END_REF] proposed to perform super-resolution and recognition simultaneously. The performance of this method depends on the training database. He and Zhang in [START_REF] He | Face super-resolution reconstruction and recognition from lowresolution image sequences[END_REF] have developed an SR technique that constructs a high-resolution face image, from a sequence of low-resolution images, to be processed by Gabor feature based recognition.

The emergence of compressive sensing (CS) theory and sparse representation has led to a plethora of image/signal processing and analysis tools that can be exploited to efficiently deal with serious challenges in pattern recognitions including the face recognition in uncontrolled conditioned. In particular, the development of efficientminimization procedures to obtain sparse solutions of certain underdetermined linear systems has led to the emergence of new SR schemes that aim recover high quality super-resolved images from low resolution degraded images ( [START_REF] Zeyde | On Single Image Scale-Up using Sparse-Representation[END_REF], [START_REF] Yang | Image super-resolution as sparse representation of raw image patches[END_REF], [START_REF] Yang | Image super-resolution via sparse representation[END_REF], [START_REF] Yang | Face hallucination via sparse coding[END_REF], & [START_REF] Wang | Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis[END_REF]). Such approaches are motivated by the fact that images in general, and more so degraded ones, can be well-approximated by a sparse expansion in terms of suitable bases such as wavelets. Yang et al in [START_REF] Yang | Image super-resolution as sparse representation of raw image patches[END_REF], [START_REF] Yang | Image super-resolution via sparse representation[END_REF] proposed a method to reconstruct superresolved image from a single low-resolution image using a pair of overcomplete dictionaries and whose columns are constructed, through a learning process, from a number of randomly selected patches of high and low resolution training datasets of face images. This pair of image-trained dictionaries is referred to as the LD system.

In this paper, we briefly discuss CS dictionary construction for various purposes in pattern recognition, but our main focus will on CS based image SR approach for face recognition in uncontrolled conditions. We shall demonstrate that non-adaptive dictionaries, implicitly constructed without using images, perform as well as the LD dictionary, if not better. We introduce an implicit approach to CS dictionary construction, an example of which was developed by the author's team at Buckingham, and investigate its performance in comparison to that of the LD scheme as well as a number of different random dictionaries in terms of the quality of their super-resolved images, face recognition accuracy and CS relevant statistical parameters. For completion, we also present the performance of a non-CS based iterative SR method [START_REF] Al-Hassan | Enhancing face recognition at a distance using super resolution[END_REF] and of matching in low-resolution.

The rest of the paper is organized as follows. Sections 2 and 3 provide a brief review of Super resolution and Compressive Sensing respectively. In section 4, we shall discus a recently designed CS approach to image RS using different types of dictionaries, and discuss the properties of these dictionaries that are relevant to the recovery of a sparse signal from a down-sampled degraded version of images. In section 5, we shall conduct experiments to compare the performance of a known face recognition scheme when applied to super-resolved mages using the different types of dictionaries as well as to the original LR images. In the conclusion, section 6, we shall briefly describe the contribution of the paper and also highlight benefits of using certain types of implicitly constructed CS dictionaries conclusions.

Super Resolution

Super-resolution (SR) is an inverse problem used as a pre-processing technique to recover a high-resolution (HR) image from one or more low-resolution (LR) images. Generally, SR techniques to obtain a HR image from an observed LR input image y may be modelled as a solution the matrix equation:

(1) where is a point-spread function with a blurring effect, is a down sampling function, and is additive noise. Various traditional non-CS based super-resolution techniques have been developed, and the most common of these are variants of the Iterative Back Projection (IBP) SR scheme which can super-resolve a single or multiple input LR image(s). The standard single LR image IBP scheme generates the initial HR image x 0 simply by decimating the pixels of the LR image y and using Bicubic interpolation. At the nth iteration, n>0, an error image x e of the size of the x (n-1) image is calculated by: (1) convoluting the x (n-1) image with an appropriate degradation function, (2) down sample the resulting image to obtain y (n) , and (3) x e is obtained from (y-y (n) ) by up-sampling. The nth iteration output the nth version of the HR image simply by calculating x (n) = (x (n-1) + x e ), which represents the back projection of the difference (y-y (n) ) onto x (n-1) . The iteration procedure terminates either when the energy of the error term (y-y (n) ) is reduced below a certain threshold or the number of iterations reached a fixed maximum number. In [START_REF] Makwana | Single Image Super-Resolution VIA Iterative Back Projection Based Canny Edge Detection and a Gabor Filter Prior[END_REF], interesting variants of the IBP have been proposed that simply pack-project additional terms in each iteration, representing high frequency information in x 0 . These variants include the use of Canny edge information and the Gabor filter to preserve edges in different directions.

The main challenge in recovering is the modelling of the unknown blurring function. Gaussian functions with different blurring effect have been considered as a suitable model for use in SR procedures, but they do not reflect severe degradation conditions seen in surveillance scenarios. A suitable model can be based on the use of atmospheric turbulence functions of different strengths (i.e. degradation functions that model environmental conditions caused by variation in temperature, wind speed and exposure time) which extends the effect of the Gaussian functions. In the frequency domain such functions are of the form:

( ) ( ) ⁄ (2)
where is a constant that reflects severity of blurring. We label degradation as severe if ; mild (similar to most Gaussian blurring functions) if ; and low if , Figure 8 illustrates the effect for different values of . In what follows, we shall adopt this model of degradation for a number of k values in these ranges to test performance of face recognition from LR images.

Compressive Sensing

Compressive sensing, also known as sparse recovery, is a novel paradigm of signal sampling that greatly relaxes the stringent limitations of the conventional Shannon-Nyquist Sampling Theorem, for signals that can be can be approximated by a sparse expansion in terms of a suitable basis. Image compression tools (e.g. JPEG and JPEG2000) use a DCT or wavelet transforms to obtain different approximately sparse representation of any input image. The concatenation of 2 bases one constructed from wavelet functions and the other from sinusoid functions is expected to be of benefits for image processing/analysis tasks, [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF]. Each of these bases provides. The underlying principle of CS is that the number of linear measurements needed to reconstruct a compressed signal should be proportional to the compressed size of the signal, not the uncompressed size. The central challenge for CS is the construction of preferably nonadaptive relatively small number of linear measurements that can guarantee the reconstruction of a sparse or approximately sparse signal. Such a set of linear measurements are represented by rows of an over complete dictionary, [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF], i.e. an mxn matrix whose columns form a spanning set of m-dimensional vectors to be used to decompose the signal. Dictionaries generalize vector space basis, and are represented by overcomplete matrices, ( ) whose columns are expected to form a pool of bases. In this case, any vector in can have multiple representations in terms of the different bases each capturing different features perhaps at different scales. A main premise of this work is that good CS dictionaries can be constructed implicitly from certain pools of bases by concatenation.

Once a suitable underdetermined dictionary { } is created, the main step in CS based tools is then the recovery of the sparsest solution of the equation:

, where is the observed vector, i.e. finding ̂ such that:

̂ ‖ ‖ ‖ ‖ (3)
This -minimization problem, known as the (P 0 ) problem, is computationally NPhard. If x is sparse and D is suitably selected, then we can find a unique solution of the -minimisation (P 1 ) problem:

̂ ‖ ‖ ‖ ‖ (4)
This is a convex optimisation problem which is amenable to linear programming. Note that, if x is small, then the Least Square (LS) method can be used to solve the corresponding the -minimisation (P 2 ) problem: However, the LS solution is not desired in many applications such as when x is spiky. Therefore, the use of the -minimisation to recover the solution of (P 0 ) problem have been the subject of intense investigations. Bruckstein et al, [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF], discuss two basic questions about (P 0 ): [START_REF] Hennings-Yeomans | Simultaneous super-resolution and feature extraction for recognition of low-resolution faces[END_REF] Under what conditions, does it have a unique solution? and (2) Given a feasible solution, is there a simple test to verify that is a global minimizer? We now discuss the dependence of these uniqueness requirements on certain parameters and properties of the matrix D. This theorem provides an efficient strategy, that we adopt here, for the implicit construction of suitable CS-dictionaries by concatenating certain sets of bases.

An m x n dictionary D satisfies the Null Space Property (NSP) of order k if for each size k set   {1,…,n} and nonzero vector z Ker(D), where is obtained from z by making 0 all coordinates not indexed by A  {1,…,n}.

Theorem 2: ([12]

) An mxn dictionary D satisfies NSP of order k iff every k-sparse solution x can be recovered by ℓ 1 -minimization. // It is not difficult to show that if D satisfies NSP of order k then every k columns of D are linearly independent. Consequently, NSP of order 2k guarantee uniqueness by Theorem 1 while Theorem 2 then showing the way of recovering the sparsest solution.

Candes and Tao, [START_REF] Candes | Near-Optimal Signal Recovery from Random Projections: Universal Encoding Strategies?[END_REF], introduced Restricted Isometry Property (RIP) as sufficient for -recovery: an dictionary D, satisfy the RIP of order if there is a constant 0 < δ k < 1, such that for any -sparse signal

( )‖ ‖ ‖ ‖ ( )‖ ‖ (5)
The smallest δ k is called the restricted Isometry constant (RIC) of order , and if satisfies RIP of order , then any -columns sub-matrix of D must be well-conditioned, [START_REF] Baraniuk | A simple proof of the restricted isometry property for random matrices[END_REF]. The condition number of a matrix is the ratio of its maximum to the minimum singular values. Checking this property for all 2k-columns submatrices is computationally infeasible as it requires exhaustive check of all ( ) submatrices. The statistical version of the restricted Isometry property (STRIP) provides a computationally easier to check version of the RIP property. It requires computation of condition numbers of sufficiently large uniformly randomly selected such submatrices. Gan et al [START_REF] Gan | Analysis of the statistical restricted isometry property for deterministic sensing matrices using Stein's method[END_REF], developed a STRIP performance bound in terms of the mutual coherence of the dictionary which is an indicator of the dependence between columns of the matrix. The coherence of a matrix provides information about the likelihood of guaranteed recovery of the sparse solution, and is defined as the largest absolute normalized inner product of pairs of columns , i.e.

, z z

c 1 1    A z ( ) |〈 〉| ‖ ‖ ‖ ‖ (6)
It is not difficult to show that if D is a dictionary with unit column vector and coherence μ then D satisfies RIP of order k with δ k ≤ (k -1)μ, (see [START_REF] Gan | Analysis of the statistical restricted isometry property for deterministic sensing matrices using Stein's method[END_REF]). When , the coherence value has been shown, [START_REF] Gan | Analysis of the statistical restricted isometry property for deterministic sensing matrices using Stein's method[END_REF], to be bounded below by √ , which is reasonably tighter than the Welch bound √ ( ) .

Due to unfeasibility of exhaustive search, we shall follow a statistical sampling approach when estimating the strength of RIP of the various dictionaries in terms of the condition number and coherence, or when testing for linear independence of the 2k columns submatrices of the dictionary. There are a number of efficient sparse recovery algorithms that have been developed including the Homotopy method (LARS) and the Iteratively Reweighted Least Square method (IRLA), [START_REF] Fornasier | Compressive Sensing[END_REF].

CS-based Superresolution

Here, we briefly describe a recently developed CS-based method to super-resolve low resolution degraded images which uses underdetermined dictionaries that are assumed to satisfy RIP. We list a number of approaches to dictionary construction including the LD approach, random constructions, and a new construction strategy that is independent of training images but designed to implicitly be of full sparke. We shall test the strength of RIP, as described above, for the constructed dictionaries and use the corresponding pairs of dictionaries to reconstruct super resolved images from low resolution degraded face images.

CS approach for image SR

It requires the use of 2 CS dictionaries: a Low resolution matrix D L of size 100x512 and a High resolution matrix D H of size 25x512. The input to this scheme is a degraded low row resolution small image Lr, and the output is super-resolved to double the size image that is meant to be of "high quality". The Lr image is resized by decimating its pixels and Bi-cubic interpolation to obtain double the size image LR which is still degraded. Three more versions of the LR image are created by applying 3 spatial filters to highlights edges in different directions. These four images are subdivided into blocks of size 5, and the pixel values in the 4 versions are turned into a column vector of 100=4x25 by concatenation. In order to avoid the appearance of blocking artefacts, the LR image will be subdivided into overlapping blocks.

Initialise a HR image of the same size of the LR image for the super-resolved image. The 5x5 blocks are then processed iteratively as follows:

1. Let y be corresponding 100-dimensional vector.

2. Find the sparse solution z of the underdetermind equation y = D L z 3. Calculate the 25-dimentional HR patch x using the matrix multiplication x = D H z , 4. Back-projection the 2-dimensional 5x5 version of x onto the existing HR. In the rest of this section we describe the pairs of Dictionaries D L and D H for the various dictionary construction strategies adopted in this paper.

The Image-based Learnt Dictionary

This construction was proposed by Yang et al, (see [START_REF] Yang | Image super-resolution as sparse representation of raw image patches[END_REF]. [START_REF] Yang | Image super-resolution via sparse representation[END_REF], & [START_REF] Yang | Face hallucination via sparse coding[END_REF]) and used for superresolution based face recognition. It is based on learning dictionaries using patches from a large training set of high resolution images of good quality that exhibit similar statistical characteristics of the pattern recognition task under investigation. We shall refer to this construction as LD dictionary. The D H and D L dictionaries are created as follows:

1. A sufficiently large number of high resolution (HR) images (here Face images) are selected and each divided into patches of 5x5 pixels. Patches overlap.

2. Randomly sampling raw patches from a training HR images, and each selected patch is transformed into a normalised vector that is added as a column to the D H .

3. Generate a set LR of blurred versions of the HR images, and create 3 other filtered versions, and the columns of D L are constructed in a similar way as in above, but by concatenating the patches from the LR images and their 3 filtered version. Again the columns are to be normalised.

Random Dictionaries

CS randomly constructed measurement matrices that satisfy the Restricted Isometry Condition include Gaussian, Toeplitz and Circular random Matrices. For Gaussian Random Matrix (GRM), the entries of the CS matrix of size are independently sampled from a normal distribution ( ), the -norm was used to normalize each columns in the dictionary. In order to recover super resolved image from a single LR image for face recognition via sparse representation, two overcomplete dictionaries , of size and respectively have been generated from a zero mean Gaussian distribution with variance . Toeplitz-Circular Random measurement matrix (TCRM) are another class of RIP dictionaries that have been widely used. Bajwa et al. [START_REF] Bajwa | Toeplitz-Structured Compressed Sensing Matrices[END_REF], have shown that Toeplitzstructured matrices are sufficient to recover undersampled sparse signals. Toeplitz and Circular matrices of the size are respectively of the form:

[ ],
and [ ] For image reconstruction, and are generated as TCRM matrices, where the first row consists of standard Gaussian random variables, and the rest of the rows are permuted versions of the first row as shown above.

Iteratively Constructed Full Spark Dictionaries

Full-sparke dictionaries is class of full row rank overcomplete where so that each m-columns sub-matrix is a basis of . Here we describe an example on how to construct such matrices by starting with an invertible mxm matrix and iteratively appending a set of image independent linearly independentcolumn vectors in while maintaining the full sparke property after every addition. One way to maintain the full sparke is to insist that every new column can only be generated by the full columns of the previous inserted submatrices. In this, paper we present a simple example of such a dictionary, but in the future we shall investigate algebraic construction method using group finite actions on Our example of full sparke dictionaries, referred to as LID, is of the form:

[ ( )] For i=1,..., k+1, the are distinct real numbers >1, and

( )
.

Note that k = n/m and the last sub-matrix of D is simply the first (n-km) columns. Then, the LID dictionary is obtained from the following matrix after normalising its columns using the -norm.

For our experimental purposes we the LID high-dictionary D H is generated from using integers . For simplicity, the low-dictionary D L was created from a Standard Gaussian Random Matrix (GRM).

Comparison of RIP parameters for Different D H dictionaries

Here we present some comparisons of the "strength" of the RIP for the LD and LID dictionaries. Whenever exhaustive search is infeasible we conducted a statistical testing by taking random sample of 100 cases. To test for full sparke property, we evaluated the determinants, as indicator of linear independence, for more than a hundred randomly selected sample of submatrices of the corresponding D H dictionaries. Although in theory, the LD dictionary may statistically satisfy NSP of order 12, Figure 1 shows that the determinant of most 25x25 submatrices is so small (almost zero) and hence the full sparke property is not satisfied. In contrast, figure 2 confirm that the LID is indeed fully sparke. The next experiment to calculate another RIP indicator, namely the condition number of 25x25 submatrices of 4 of the DH dictionaries for LD, LID. GRM and theT-CRM. These condition numbers are expected to be bounded by RIC of order 2k, with k=12. Table 1, below, displays the mean and standard deviation the condition numbers for 100 randomly selected submatrices and the condition number of the full size matrix. These results again demonstrate that the overcomplete LID dictionary is wellconditioned in comparison to all others for the various submatrices but for the full matrix GRM and TCRM have similar condition numbers that are better than the LID. Moreover, the condition number of the LD is extremely large for all cases, which make these dictionaries very ill conditioned.

Another test relates to calculating the row-rank and coherence values for the various dictionaries. It is well known that the highest sparsity recovered signal for any dictionary = (1+ row rank)/2, and coherence  must satisfy 0.2 =1/m ≤  ≤ 1. Again, results in Table 2 highlight the superiority of the LID dictionary. Finally, in order to test the viability of the CS-based SR scheme, we compared the visual quality of large set of SR enhanced images obtained from the application of the various discussed dictionaries, as well as the IISR scheme and interpolation methods. The results of the visual inspection reveal that there is little difference in the quality of the recovered HR image using the various dictionaries, but a noticeable improvement that can be noticed in SR methods, including IISR, over the lowresolution images and interpolation methods at every level of degradation. Figure 3, below, show one example but this pattern was repeated over all the images. PSNR valuescalculated between the output SR image and the original images confirm the same pattern, but we omit these results. Unsurprisingly and regardless of the method used in the SR procedure, the quality of SR images decreases as the level of blurring increases. With increased level of blurring there is no difference in image quality obtained by different dictionary methods. But the dictionary methods produced slight improvement on the IISR method, and superiority over the interpolation methods at every level of blurring.

Face Recognition -Experimental Results

In this section, we shall compare the performance of face recognition using the corresponding super-resolved images. We test the performance of different dictionary methods as well as a state-of -the art methods to reconstruct super resolved face image from a single LR image with different magnification blur. The image sets were sampled from a publically available face database and, comparisons recognition rates presented with matching in low-resolution domain. We use a simple but efficient wavelet-based face recognition scheme, whereby the training as well the matching image are wavelet decomposed to level 3 and each of the each of the subbands at level 3 (i.e. LL3, HL3, LH3 and HH3) is used as a face feature vector and Euclidian distance is used for matching against the face feature vectors of the templates.

To test the performance of the wavelet face recognition schemes post the CS-based SR preprocessing schemes, we used face images from the Extended Yale B database. This database consists of frontal-face images of individuals. The cropped and normalized face images were captured under various laboratorycontrolled lighting conditions. For each subject, we selected the P00A+00E+00 image for the gallery set and the other images for testing. To construct LD that depends on images, three images for each subject were selected from the well-lit face images in set 1 that were not included in the gallery/test images.

To simulate face recognition under the recording condition of low resolution degraded quality images, we first apply the degradation function defined by equation 2for different values of k on the high resolution images in the reasonably lit sets (1 and 2) of the database. The low resolution degraded Lr images are finally obtained by down-sampling the degraded images by a factor of 2.

Each test Lr face image is first super-resolved using each of the built dictionaries, the IISR scheme or simply by up-sampling and interpolation.

For feature extraction, on the resulting HR templates as well as the SR-resolved test images, we use the Z-score normalized coefficients of the the subbands of the Haar wavelet decomposed face images at level three. Matching will be based on the City Block distance between a probe image and a gallery image.

The experimental results are shown in Figure 5 for the different subbands and differently illuminated sets of images. The various charts display the accuracy rate at each level of degradation function. As can be seen, there is no significant difference in identification accuracy rates, between the different dictionaries methods. Moreover, the accuracy rates seem to be maintained at the same level for different degradation level. In comparisons to the method of matching the LR images with down-sampled gallery images, the performance of the dictionary based methods are far more superior and much more apparent as the image quality deteriorates from mild to severe degradation. However, the picture is surprisingly different for mild image degradation (i.e. k 1 < 0.7) when we use the HL3 or HH3 subband as feature vectors for set 1 images which are recorded in a slightly better illumination condition. Note that the full set of experiments, part of which are not included here, indicate similar patterns of performance, i.e. a much better accuracy are achieved by all the dictionaries than that achieved by the various interpolation methods such as nearest, bilinear and Bi-cubic and the difference in performance increases as the of degradation get more severe.. The observed pattern of variation in the performance of face recognition, using different sub-bands is consistent with known results for wavelet-based face recognition without degradation reported in the literature, (see [START_REF] Al-Obaydy | On using high-definition body worn cameras for face recognition from a distance[END_REF]). For this work we also conducted face recognition for exactly the same conditions on resolution and blurring but using the Principle Component Analysis technique (PCA). The results exhibit similar patterns and are omitted here.

Conclusion

We have studied the RIP property for random, and not so random, constructions of CS related overcomplete dictionaries as well as an existing dictionary that trained on a set of high-resolution face images. These dictionaries were used to generate super resolved image with the aim of using for face recognition in uncontrolled conditions where the input is degraded blurred LR image with a wide range of degradation. This results effectively support the use of SR based techniques that employ CS dictionaries for recovering super-resolved images that are suitable for face recognition. More importantly, that there is no need for using image sets for training dictionaries, because non-adaptive dictionaries perform equally well if not better in some cases. In an attempt to find possible explanation, we conducted a number of tests of numerical matrix parameters relevant to the RIP condition. We note that the learning imagebased dictionary is highly ill conditioned and far from satisfying the RIP related conditions discussed in the literature. Perhaps the use of image patches with the same statistical parameters of general face image patches compensate for the lack of RIP properties.

Further studies are needed to test other implicit construction of RIP dictionaries. Indeed, we have developed a new method which aims to implicitly satisfy the known bounds on singular values. Such approaches can be exploited to use RIP dictionaries for revocable face biometric instead of the traditional random projection.



  The sparke an mxn matrix D, denoted by sp(D) is the minimum number of linearly dependent columns of D. It is clear that sp(D)≤ m+1. Equality occurs when D has a full row rank, and then D is said to be of full sparke. Theorem 1: (see[START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF]) If every (sp(D)-1) columns of D are linearly independent then every (sp(D)/2)-sparse x can be recovered uniquely from . //

Figure1.

  Figure1. Determinant of submatrices from the High-resolution LD Dictionary Figure2. Determinant of submatrices from the High-resolution LID dictionary

Figure 3 .

 3 Recognition accuracy rates using different dictionaries and in comparisons with matching in low-resolution

Figure 4 .

 4 Figure 4. Super Resolved image by different SR methods and well non-interpolation methods

Table 1 .

 1 Mean and Standard deviation for CN for a hundred random sub-matrices of different sizes.

					Dictionaries
	submatrices		LID		LD		GRM		TCRM
		mean	std	mean	std	mean	std	mean	std
	25x25	3.08	3.14	3.34E+16	1.79 E+17	279.36	597.79	85.19	155.68
	Full matrix	1.977		1.00E+15		1.43		1.453

Table 2 .

 2 Row-rank and Coherence

	Determinant
	1 11 21 31 41 51 61 71 81 91 101

Conducted as part of the PhD research project of Nadia Al-Hassan supervised jointly with Harin Sellahewa.