MD Suzanne Lesage

Isabelle Le Ber

Christel Condroyer

MD Emmanuel Broussolle

Audrey Gabelle

Stéphane Thobois

Florence Pasquier

Karl Mondon

Patrick Dion

Daniel Rochefort

Guy Rouleau

MD Alexandra Dürr

Prof Alexis Brice
email: alexis.brice@upmc.fr

MD Y Agid

PhD M Anheim

PhD A.-M Bonnet

MD M Borg

PhD J.-C Corvol

PhD A Destée

PhD F Durif

PhD C Duyckaerts

PhD ; S Klebe

PhD P Krack

PhD E Lohmann

MD M Martinez

PhD P Pollak

PhD O Rascol

PhD F Tison

PhD C Tranchant

MD M Vérin

PhD F Viallet

MD M Vidailhet

C9ORF72 repeat expansions are a rare genetic cause of parkinsonism Running head: C9ORF72 repeat expansion in parkinsonism

Keywords: parkinsonism, C9ORF72, dementia ALS = amyotrophic lateral sclerosis, CBDS = corticobasal degeneration syndrome, CI = confidence intervals, FAB = Frontal assessment battery, FTLD = frontotemporal lobar degenerations, LRRK2 = Leucine

3/ Lesage_BRAIN-2012-01461 The recently identified C9ORF72 gene accounts for a large proportion of amyotrophic lateral sclerosis and frontotemporal lobar degenerations. Since several forms of these disorders are associated with parkinsonism, we hypothesized that some patients with Parkinson's disease or other forms of parkinsonism might carry pathogenic C9OFR72 expansions. Therefore, we looked for C9ORF72 repeat expansions in 1,446 parkinsonian unrelated patients consisted of 1,225 clinically diagnosed with Parkinson's disease, 123 with progressive supranuclear palsy, 21 with corticobasal degeneration syndrome, 43 with Lewy body dementia and 25 with multiple system atrophy-parkinsonism. Of the 1,446 parkinsonian patients, five carried C9ORF72 expansions: three patients with typical Parkinson's disease, one with corticobasal degeneration syndrome and another with progressive supranuclear palsy. This study shows that: i) although rare, C9ORF72 repeat expansions may be associated with clinically typical Parkinson's disease, but also with other parkinsonism; ii) in several patients, parkinsonism was dopa-responsive and remained pure, without associated dementia, for more than 10 years; iii) interestingly, all C9ORF72 repeat expansion carriers had positive family histories of parkinsonism, degenerative dementias or amyotrophic lateral sclerosis. This study also provides the tools for identifying parkinsonian patients with C9ORF72 expansions, with important consequences for genetic counseling.

Introduction

Parkinson's disease (PD) is common in the aging population, ranking second in prevalence after Alzheimer's disease. The prevalence of this condition is age-dependent, affecting more than 1% of persons over the age of 65 years, but this rate is increased to 4-5 % by the age of 85 years [START_REF] De Lau | Epidemiology of Parkinson's disease[END_REF]. PD is a clinical motor syndrome with variable combinations of akinesia, rigidity, rest tremor, and postural instability, linked to a characteristic pattern of neurodegeneration of dopaminergic neurons, particularly in the substantia nigra pars compacta and the presence of intraneuronal cytoplasmic inclusions, known as Lewy bodies, in surviving dopaminergic neurons. In addition, cognitive dysfunction is frequent in PD [START_REF] Barton | Clinical validation of movement disorder society-recommended diagnostic criteria for Parkinson's disease with dementia[END_REF] and also in atypical forms of parkinsonism such as Lewy body dementia (LBD), progressive supranuclear palsy (PSP), and corticobasal degeneration syndrome (CBDS). A GGGGCC repeat expansion in C9ORF72 was recently reported to be the most common genetic cause of amyotrophic lateral sclerosis (ALS) and frontotemporal lobar degenerations (FTLD) [START_REF] Dejesus-Hernandez | Expanded GGGGCC hexanucleotide repeat in noncoding region of C9ORF72 causes chromosome 9p-linked FTD and ALS[END_REF][START_REF] Renton | A hexanucleotide repeat expansion in C9ORF72 is the cause of chromosome 9p21-linked ALS-FTD[END_REF]. Since the clinical and neuropathological features of ALS, neurodegenerative dementias and parkinsonism overlap, we looked for C9ORF72 repeat expansions in 1,446 parkinsonian unrelated patients.

Subjects and Methods

Subjects

The study included a total of 1,446 unrelated patients: 1,225 clinically diagnosed with PD, 123 with PSP, 21 with CBDS, 43 with LBD and 25 with multiple system atrophyparkinsonism (MSA-P) (Table 1).

Patients with PD were recruited through the French network for the study of Parkinson's disease Genetics (PDG). PD was diagnosed according to the UK Parkinson's Disease Society 6/ Lesage_BRAIN-2012-01461 Brain Bank (PDSBB) clinical diagnostic criteria [START_REF] Hughes | Accuracy of clinical diagnosis of idiopathic Parkinson's disease: a clinico-pathological study of 100 cases[END_REF]. Most (>80%) PD patients fulfilled the criteria for definite PD: at least 2 of 3 cardinal signs (akinesia and/or rigidity and/or tremor) and a positive and sustained response to levodopa therapy. PSP [START_REF] Litvan | Clinical research criteria for the diagnosis of progressive supranuclear palsy (Steele-Richardson-Olszewski syndrome): report of the NINDS-SPSP international workshop[END_REF], CBDS [START_REF] Boeve | Corticobasal degeneration and its relationship to progressive supranuclear palsy and frontotemporal dementia[END_REF], LBD (McKeith et al., 2005), and MSA [START_REF] Gilman | Second consensus statement on the diagnosis of multiple system atrophy[END_REF] were diagnosed according to the international consensus diagnosis criteria.

Patients underwent standard neurological examinations, including the Unified Parkinson's Disease Rating scale (UPDRS) [START_REF] Goetz | Movement Disorder Society-sponsored revision of the Unified Parkinson's Disease Rating Scale (MDS-UPDRS): scale presentation and clinimetric testing results[END_REF], the Hoehn and Yahr scale [START_REF] Hoehn | Parkinsonism: onset, progression, and mortality[END_REF], to evaluate patients' motor disability, response to levodopa, and the Mini Mental State Examination (MMSE) [START_REF] Folstein | Mini-mental state". A practical method for grading the cognitive state of patients for the clinician[END_REF], Frontal assessment battery (FAB) [START_REF] Dubois | The FAB: a frontal Assessment Battery at bedside[END_REF], Wisconsin Card Sorting Test (WCST) [START_REF] Heaton | A manual for the Wisconsin Card Sorting Test[END_REF] and Mattis Dementia Rating Scale (MDRS) [START_REF] Mattis | Mental status examination for organic mental syndrome in the elderly patient[END_REF] to evaluate cognitive function.

Patients with a positive family history were defined as individuals with at least one first degree relative with a confirmed diagnosis of typical PD or other neurodegenerative disorders including parkinsonism, degenerative dementias or ALS. Of note, 40% of the 1,225 PD patients included in the study reported family histories of classical PD; this is because they were selected in an effort to enrich the cohort in individuals who might have more genetic susceptibility factors. Four percent had family histories of other neurodegenerative disorders (Table 1). All the 1,225 unrelated PD patients were excluded for the common Leucine-rich repeat kinase 2 (LRRK2) G2019S mutation. All index cases compatible with autosomal dominant PD were excluded for SNCA multiplications (n = 340); patients compatible with autosomal recessive PD (n = 60) as well as sporadic cases (n = 420), with an age at onset ≤50 years were excluded for PARK2, PARK6 and PARK7.

Control subjects, 445 Caucasians, mostly of French descent (174 males, 271 females, mainly spouses) without family histories of parkinsonism and excluded for the LRRK2 G2019S mutation, were examined at age 64.9±8.5 years (range 51-89).

7/ Lesage_BRAIN-2012-01461 Local ethics committees approved the study and written informed consent was obtained from all participants.

Methods

Genomic DNA from all participants was obtained from venous blood using standard protocols. The GGGGCC repeat expansions in the first intron of C9ORF72 were searched for, using the repeat primed PCR reaction adapted from [START_REF] Renton | A hexanucleotide repeat expansion in C9ORF72 is the cause of chromosome 9p21-linked ALS-FTD[END_REF]. In short, 80 ng of genomic DNA were mixed with 14 µl FastStart PCR Master-Mix (Roche Diagnostics), 0.18 mM 7-deaza-dGTP (Roche Diagnostics), Q solution (Qiagen Inc.), 7% dimethyl sulfoxide (DMSO), 0.9 mM Mgcl 2 , 0.7 µM reverse primer consisting of four GGGGCC repeats and an anchor tail (TACGCATCCCAGTTTGAGACGGGGGCCGGGGCCGGGGCCGGGG), 1.4 µM 6FAM-fluorescent forward primer located 280 base pairs 3' prime to the repeat sequence (AGTCGCTAGAGGCGAAAGC) and 1.4 µM anchor primer corresponding to the anchor tail of the reverse primer (TACGCATCCCAGTTTGAGACG). A touchdown PCR cycling protocol was used in which the initial annealing temperature was lowered from 70°C to 56°C in 2°C increments with a 3 minute-extension in each cycle [START_REF] Renton | A hexanucleotide repeat expansion in C9ORF72 is the cause of chromosome 9p21-linked ALS-FTD[END_REF]. Fragment length analysis was performed on an ABI 3730 genetic analyzer (Applied Biosystems), and data analyzed using Peak Scanner software version v1.0 (Applied Biosystems).

To determine the accurate sizing of the non-expanded allele and score all alleles in heterozygous or homozygous state, we performed a classical FAM-fluorescent PCR assay, using previously described primers [START_REF] Renton | A hexanucleotide repeat expansion in C9ORF72 is the cause of chromosome 9p21-linked ALS-FTD[END_REF]. To determine the mean number of C9ORF72 hexanucleotide repeats in non-mutation carriers, we summed the number of repeats on both non-expanded alleles.

To confirm the size of the largest expanded alleles, we performed a Southern blot analysis of DNA from the putative C9ORF72 expansion carriers and also from patients with an 8/Lesage_BRAIN-2012-01461 intermediate length hexanucleotide repeat-containing allele for whom DNA was available.

Briefly, ten µg of genomic DNA extracted from blood were digested with MboI restriction endonuclease (New England Biolabs) and the digested samples were separated on a 0.8% agarose gel in 1x TBE buffer at 1V/cm overnight. DNA was alkali-transferred onto a GeneScreen Plus filter (NEN Life Sciences Products Inc) according to the manufacturer's protocol. A double labeled probe (NeBlot kit New England Biolabs, [a-32P]dATP and [a-32P]dCTP 3000ci/mmol, PerkinElmer) corresponding to chromosome 9 position 27,573,698-27,573,938 in the hg19 assembly was hybridized to blots in modified Church and Gilbert hybridization buffer (0.5 M NaH2PO4/Na2HPO4, pH 6.8, 7% SDS, 1 mM EDTA, 1% BSA) at 65°C overnight [START_REF] Church | Genomic sequencing[END_REF]. Blot membranes were then washed two times at room temperature and twice at 65°C in 40 mM NaH2PO4/Na2HPO4, pH 6.8, 1% SDS.

Films were exposed at -80°C against an intensifying screen for two or more days.

Results

A total of 1,446 patients with parkinsonism, including 1,225 clinically diagnosed with PD and 464 healthy controls were successfully genotyped with both assays to study the C9ORF72 repeat in all patients: a repeat-primed PCR to identify expansion carriers and a classical fluorescent PCR to allow the accurate sizing of the non-expanded allele.

Five of the 1,446 patients with parkinsonism showed the typical sawtooth tail pattern detected by repeat-primed PCR analysis [START_REF] Renton | A hexanucleotide repeat expansion in C9ORF72 is the cause of chromosome 9p21-linked ALS-FTD[END_REF], characteristic of C9ORF72 repeat expansions in the pathogenic size (≥ 60 repeat units) (Fig. 1A) and a single peak and potentially unamplifiable repeat expansions detected by fluorescent fragment length PCR analysis (Fig. 1B) (Table 2). The presence of these large expanded alleles was further confirmed on Southern blots (Fig. 1C), which showed additional expanded alleles >12 kilobases in size in the five patients with parkinsonism. Although we confirmed the presence 9/Lesage_BRAIN-2012-01461 of repeat expansions by Southern blot, significant repeat size heterogeneity resulting in a smear on the blot complicated accurate sizing of the repeats in the five patients and the positive control (FTLD patient with a C9ORF72 expansion).

In the subgroup of 1,225 PD patients, there were three carriers of C9ORF72 repeat expansions (0.2%, 95% confidence intervals (CI) 0.09-0.7) who had isolated parkinsonian symptoms at onset. Ages at onset ranged from 29 to 64 years. In the first patient (PD1 Although these three patients were clinically diagnosed with typical PD, they all had family histories of atypical PD, degenerative dementias or ALS (Fig. 2). No expansions were identified in patients with family histories of typical PD.

We also found a C9ORF72 repeat expansion in a PSP patient (PD4) with parkinsonism, gazepalsy and dementia (1/123, 0.8%, 95% CI 0.2-4.4), and in a CBDS patient (PD5) with left akinetic rigid parkinsonism, upper limb dystonia, orofacial apraxia, anarthric speech and 10/Lesage_BRAIN-2012-01461 frontal lobe syndrome (1/21, 5%, 95% CI 1.1-22.8) (Table 2). In addition, two patients with PSP, aged 59 (PD6) and 74 at onset (PD7), had intermediate repeat lengths of 26 and 30, respectively (Fig. 1). Both patients presented typical features of isolated PSP, including parkinsonism, supranuclear gaze palsy, postural instability early in the disease course, dysarthria and mild frontal dementia.

No expansions were found in patients with MSA-P or with LBD or in controls. The average C9ORF72 repeat number was 4.5±3.3 (range 2-22) in the 445 control subjects.

Discussion

In a recent study, 35% of patients with C9ORF72 expansions developed parkinsonism within the first two years after onset of FTD and ALS [START_REF] Boeve | Characterization of frontotemporal dementia and/or amyotrophic lateral sclerosis associated with the GGGGCC repeat expansion in C9ORF72[END_REF]. Using a stepwise protocol according to previously described methods, combining fluorescent fragment length, repeatprimed PCR and Southern blot analyses [START_REF] Dejesus-Hernandez | Expanded GGGGCC hexanucleotide repeat in noncoding region of C9ORF72 causes chromosome 9p-linked FTD and ALS[END_REF], we have now identified disease-causing repeat expansions in a subset of patients from a large cohort with different forms of parkinsonism, extending the clinical phenotype associated with these expansions from degenerative dementias including Alzheimer's disease (Majounie et al., 2012a) and ALS to parkinsonism. Two patients had typical PD for many years (5 to 8) before cognitive deficits or dementias developed; one patient had no cognitive deficits, 12 years after PD onset. This study shows that: i) although rare, C9ORF72 repeat expansions may be associated with clinically typical PD, but also with PSP and CBDS; ii) the parkinsonism could be levodoparesponsive and, as in PD, remains pure, without associated cognitive deficits or dementias for more than 10 years; iii) interestingly, all C9ORF72 mutation carriers had positive family histories of parkinsonism, degenerative dementias or ALS. Among the patients with positive family histories, the proportion of patients with expansions in C9ORF72 reached 6% (3/47, We also identified two PSP patients with intermediate numbers of GGGGCC repeats, ranging from 26 to 30. Notably, a 29-hexanucleotide repeat allele was found in a patient from a Dutch c9FTLD/ALS family [START_REF] Simón-Sánchez | The clinical and pathological phenotype of C9ORF72 hexanucleotide repeat expansions[END_REF] suggesting that intermediate alleles might be pathogenic in patients with PSP. Of note, the maximum size of the repeat in most controls was reported not to exceed 24 units [START_REF] Dejesus-Hernandez | Expanded GGGGCC hexanucleotide repeat in noncoding region of C9ORF72 causes chromosome 9p-linked FTD and ALS[END_REF][START_REF] Renton | A hexanucleotide repeat expansion in C9ORF72 is the cause of chromosome 9p21-linked ALS-FTD[END_REF][START_REF] Gijselinck | A C9orf72 promoter repeat expansion in a Flanders-Belgian cohort with disorders of the 20/Lesage_BRAIN-2012-01461 frontotemporal lobar degeneration-amyotrophic lateral sclerosis spectrum: a gene identification study[END_REF][START_REF] Rutherford | Length of normal alleles of C9ORF72 GGGGCC repeat do not influence disease phenotype[END_REF][START_REF] Sabatelli | C9ORF72 hexanucleotide repeat expansions in the Italian sporadic ALS population[END_REF]. In our study and that of [START_REF] Millecamps | Phenotype difference between ALS patients with expanded repeats in C9ORF72 and patients with mutations in other ALS-related genes[END_REF], repeat lengths ranged from 2 to 23 in the control group of French origin (n>600). Although, the repeat size in our patients was clearly larger than in ethnically matched control subjects and their ages at onset were in the range observed in typical patients with C9ORF72 repeat expansions, we cannot completely exclude that the observed repeat expansions and the presence of typical PD are unrelated (i.e. the patients have two different neurological diseases). A recent study in a large cohort of 781 Caucasian PD cases, one third of which reported family histories of PD, failed to identify any pathogenic hexanucleotide expansions in C9ORF72, although a patient with typical PD harbored a marginally 38-GGGGCC hexanucleotide repeat allele (Majounie et al., 2012b). Large multi-centre studies worldwide are needed to determine the frequency of C9ORF72 mutations in idiopathic PD, particularly when positive family histories of parkinsonism, degenerative dementias or ALS are present.

The present study, therefore, suggests that patients with PD or other parkinsonian syndromes, particularly when a family history of other neurodegenerative disorders is present, should be screened for C9ORF72 expansions. This provides the tools for identifying potential carriers with important consequences for genetic counseling.

12/Lesage_BRAIN-2012-01461 17/Lesage_BRAIN-2012-01461 19/Lesage_BRAIN-2012-01461

  degeneration syndrome, LBD = Lewy body dementia, MSA-P = multiple system atrophy-parkinsonism, PD = Parkinson's disease, PSP = progressive supranuclear palsy.

  , ALS = amyotrophic lateral sclerosis, CBDS = corticobasal degeneration syndrome, DD = disease duration, FAB = Frontal assessment battery, FTLD = frontotemporal lobar degenerations, LL = Lower limb, MMSE = Mini mental status examination, na = not available, P = Parkinsonism, PD = Parkinson's disease, PSP = progressive supra-nuclear palsy, R = rigidity, T = rest tremor, UL = upper limb. a UPDRS Part III motor "on/off" score = Unified Parkinson's Disease Rating Scale rated under/off treatment with levodopa at evaluation time.

Figure 1

 1 Figure 1 Molecular genetic analyses of hexanucleotide repeat expansions in the seven

Figure 2

 2 Figure 2 Pedigree structures of families with repeat expansions that had family histories of

  ), parkinsonism began at age 48 with bilateral rest tremor and akinesia. At age 54, she developed axial rigidity and a severe gait disorder. She showed cognitive deficits (MMSE score 25/30) at age 56 and died at 59. The second patient (PD2) developed a levodopa-responsive akinetic rigid syndrome and asymmetric lower limb dystonia at age 64. She developed dyskinesias, visual hallucinations under dopamine agonists and a mild cognitive deficit at age 69 that had no effect on her autonomy in daily life (MMSE 26/30; FAB 15/18). The third patient (PD3) developed left hemi-parkinsonism at age 29 with upper limb rest tremor, akinesia, rigidity and dystonia (UPDRS III: 17/108; Hoehn and Yahr: 1.5/5). Her parkinsonian symptoms worsened progressively; dopamine agonists were partially effective. At age 34, she had motor fluctuations and dyskinesias (UPDRS III off medication: 37/108; Hoehn and Yahr: 2/5). Before deep brain stimulation, at age 37, her FAB score was 18/18, her MMSE 27/30, her WCST 18/20 and her MDRS 138/144. At 40, she had no dementia, nor psychiatric signs. She is still working as a secretary.

Table 1 Demographic and clinical characteristics of patients with parkinsonism and C9ORF72 expansion carriers

 1 Other neurodegenerative disorders include parkinsonism, degenerative dementias or ALS.

	Parkinsonian disorders	PD	LBD	PSP	CBDS	MSA-P
	Patients, n	1235 a	43	123	21	25
	Sex, M/F	734/501	31/12	65/58	12/9	16/9
	Age at disease onset, years	48.3±12.5	63.6±11.9	64.1±8.2	64.2±8.8	56.3±13.2
	(range)	(6-86)	(34-83)	(40-79)	(50-80)	(35-81)
	Age at examination, years	56.8±13.1	71.1±10.0	67.8±9.8	67.8±8.5	63.7±14.7
	(range)	(14-87)	(43-85)	(44-83)	(52-82)	(36-87)
	Dementia (%)	10	100	100	100	54
	Patients with family histories of other	47 (4)	11 (26)	15 (12)	7 (33)	17 (68)
	neurodegenerative disorders b , n (%)
	C9ORF72 expansion carriers, n	3	0	1	1	0
	Expansion carriers with family histories of	6	0	7	14	0
	other neurodegenerative disorders b (%)
	a 40% of the patients had family histories of typical PD.

b

Acknowledgments

We are grateful to the patients and their families. We thank Merle Ruberg for critical reading of the manuscript, the DNA and Cell Bank of the CRICM for sample preparation, Agnès Camuzat and Léna Guillot-Noel for technical assistance.

Funding

This work was supported by PSP-France Association, France-Parkinson Association. A.D. and A.B. were supported by the French Agency for Research (ANR) program grants. 13/Lesage_BRAIN-2012-01461


Oulfat Amin

Marie-Laure Fardeau

Odile Valette

Agnès Hirschler-Réa

Valérie Barbe

Claudine Médigue

Benoit Vacherie

Bernard Ollivier

Philippe N Bertin

Alain Dolla

Genome Sequence of the Sulfate-Reducing Bacterium Desulfotomaculum hydrothermale Lam5 T

Here, we report the draft genome sequence of Desulfotomaculum hydrothermale, a sulfate-reducing, spore-forming bacterium isolated from a Tunisian hot spring. The genome is composed of 2.7 Mb, with a G؉C content of 49.48%, and it contains 2,643 protein-coding sequences.

M embers of the genus Desulfotomaculum are sulfate-reducing, spore-forming Gram-positive bacteria that are widely distributed within mesothermic and thermal ecosystems [START_REF] Kuever | Genus II. Desulfotomaculum C[END_REF]. Evidence of their presence in terrestrial geothermal hot springs has been obtained several times using molecular approaches (2), but only three species of this genus have been isolated so far, the most recent being Desulfotomaculum hydrothermale [START_REF] Haouari | Desulfotomaculum hydrothermale sp. nov., a thermophilic sulfate-reducing bacterium isolated from a terrestrial Tunisian hot spring[END_REF]. Here, we report the first draft genome sequence of a Desulfotomaculum species isolated from a terrestrial hot spring in Tunisia: D. hydrothermale. The strain was shown to reductively detoxify arsenate [As(V)], in the presence of pyruvate as an electron donor, without evidence for any respiration using As(V) as a terminal electron acceptor [START_REF] Haouari | Desulfotomaculum hydrothermale sp. nov., a thermophilic sulfate-reducing bacterium isolated from a terrestrial Tunisian hot spring[END_REF]. Because arsenic is known to be present in hot springs (4), information regarding the genome sequence of D. hydrothermale may be useful in understanding the As-detoxifying process developed in Desulfotomaculum species.

A Sanger/pyrosequencing hybrid approach was used for the whole-genome sequencing. A shotgun library was constructed with 10-kb fragments of genomic DNA in vector pCNS (derived from pSU). Sequencing with vector-based primers was carried out using the ABI 3730 Applera sequencer, and a total of 6,421 reads (~1.6-fold coverage) were analyzed and assembled with Newbler (a Roche assembler), with 341,086 single reads (~26-fold coverage) and 106,386 mate-paired 8-kb reads obtained with Genome Sequencer version FLX and Titanium (Roche Applied Science), respectively. The finishing step was achieved by using primer walks, PCRs, and in vitro transposition technologies. For quality assessment, 5,501,511 (36-nucleotide) Illumina reads (~70-fold coverage) were mapped using Soap1 (http://soap.genomics.org.cn/) on the 16 consensus contigs. The draft genome sequence consists of 2,706,432 bases with a GϩC content of 49.48%, and it contains 2,643 candidate protein-encoding genes, in addition to 60 tRNA and 3 16S rRNA genes.

The mechanism of microbe-mediated metal reduction, studied mainly in Geobacter and Shewanella species, involves c-type cytochromes [START_REF] Weber | Microorganisms pumping iron: anaerobic microbial iron oxidation and reduction[END_REF][START_REF] Beliaev | MtrC, an outer membrane decahaem c cytochrome required for metal reduction in Shewanella putrefaciens MR-1[END_REF]. For Desulfotomaculum reducens, it has been hypothesized that an integral membrane multiheme c-type cytochrome (Dred_0700-0701) is involved in the reduction of metals such as Fe(III) and U(VI) [START_REF] Junier | The genome of the gram-positive metal-and sulfate-reducing bacterium Desulfotomaculum reducens strain MI-1[END_REF]. Inspection of the draft genome sequence of D. hydrothermale suggests the absence of c-type cytochromes and the absence of an identified ortholog of Dred_0700-0701, even though the strain is able to reduce Fe(III) to Fe(II) [START_REF] Haouari | Desulfotomaculum hydrothermale sp. nov., a thermophilic sulfate-reducing bacterium isolated from a terrestrial Tunisian hot spring[END_REF]. Metal reduction in this strain would use a different pathway, which needs to be specified. The D. hydrothermale genome encodes an arsenite resistance protein (DESHYv2_110039) that exhibits homology to the intrinsic membrane protein ArsB [START_REF] Prakash | The ion transporter superfamily[END_REF]. A gene (DESHYv2_110038) encoding a transcriptional regulator belonging to the AsrR family [START_REF] Wu | The ArsR protein is a trans-acting regulatory protein[END_REF] was found immediately upstream from asrB. Even if no homolog to the arsenate reductase gene asrC [START_REF] Messens | Arsenate reduction: thiol cascade chemistry with convergent evolution[END_REF] has been identified so far, this gene cluster could be of great importance for arsenite reduction and for the tolerance capacity of this strain.

Insights into the arsenite resistance process of Desulfotomaculum species could be gained through comparative genomics and biochemical analyses of the arsenite resistance mechanisms, which are in progress in our laboratories.

Nucleotide sequence accession numbers. The whole-genome shotgun project has been deposited at DDBL/EMBL/Genbank under the accession no. CAOS01000001 to CAOS01000016.

Genome Announcements 2 genomea.asm.org January/February 2013 Volume 1 Issue 1 e00114-12

ACKNOWLEDGMENTS

Financial support came from the Université de Strasbourg (UDS), the Consortium National de Recherche en Génomique (CNRG), and the CNRS.


Hedi Tabia

David Picard

Hamid Laga

Philippe-Henri Gosselin

Compact Vectors of Locally Aggregated Tensors for 3D shape retrieval

Keywords: (according to ACM CCS): H, 3, 3 [ Information storage and retrieval]: Information Search and Retrieval-I, 5, 4 [Pattern recognition]: Applications -

During the last decade, a significant attention has been paid, by the computer vision and the computer graphics communities, to three dimensional (3D) object retrieval. Shape retrieval methods can be divided into three main steps: the shape descriptors extraction, the shape signatures and their associated similarity measures, and the machine learning relevance functions. While the first and the last points have vastly been addressed in recent years, in this paper, we focus on the second point; presenting a new 3D object retrieval method using a new coding/pooling technique and powerful 3D shape descriptors extracted from 2D views. For a given 3D shape, the approach extracts a very large and dense set of local descriptors. From these descriptors, we build a new shape signature by aggregating tensor products of visual descriptors. The similarity between 3D models can then be efficiently computed with a simple dot product. We further improve the compactness and discrimination power of the descriptor using local Principal Component Analysis on each cluster of descriptors. Experiments on the SHREC 2012 and the McGill benchmarks show that our approach outperforms the state-of-the-art techniques, including other BoF methods, both in compactness of the representation and in the retrieval performance.

Introduction

Databases of 3D models available in the public domain have created the need for shape analysis and retrieval algorithms capable of finding similar shapes in the same way a search engine responds to text and image queries. State-of-the-art 3D model retrieval methods [TV08] often start by extracting local features and descriptors, then aggregating the features into compact signatures, and finally compare the signatures with standard distances. Recently, Bag of Features (BoF) representations, that have been widely adopted by the computer vision community for image retrieval and scene understanding, are gaining popularity in 3D shape analysis and retrieval [START_REF] Bronstein | Shape google: Geometric words and expressions for invariant shape retrieval[END_REF][START_REF] Godil | Visual similarity based 3d shape retrieval using bag-of-features[END_REF]TDVC10]. One of the advantages of using BoF representations [JPD * 12] is that one can benefit from the rich literature of powerful local descriptors, such as SIFT [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF], Histogram of Oriented Gradients (HoG) [DT05], and many others [MS05]. Second, BoF rep-resentations can be compared with standard distance measures. Third, although BoF vectors can have large dimensions when used for retrieval in large databases [JPD * 12], they are often sparse and inverted lists can be used to implement efficient search [JPD * 12, SZ03]. BoF-based approaches start by building a dictionary of K visual words from a set of training samples. The visual words are usually obtained by k-means clustering of the local features extracted from all the 3D models in the training set. Each 3D model is then represented with the statistics of the distribution of the visual words in the 3D model. These vector representations can be compared with standard distances, and be subsequently used by robust classification methods such as Support Vector Machines. Most of BoF-based 3D retrieval techniques proposed so far in the literature represent a 3D model with a vector of frequencies of occurrences of visual words [LG09, OOFB08, LGS10, TCF10, [START_REF] Bronstein | Shape google: Geometric words and expressions for invariant shape retrieval[END_REF][START_REF] Lavoué | Combination of bag-of-words descriptors for robust partial shape retrieval[END_REF]. This corresponds to 0-order statistics of the distribution of c The Eurographics Association 2013. the visual words. In this paper, we explore the usage of highorder statistics and show that this enables the computation of compact descriptors while outperforming 0-order statistics in terms of retrieval and classification performance.

Our approach starts with the extraction of dense features from each shape. The advantage of using dense descriptors, in contrast to few descriptors computed at sparse locations, is well acknowledged by the computer vision community as it enables efficient 3D model retrieval and classification. The gain in performance comes at the expense of significant increase in computation time and memory requirement. In this paper we study and evaluate four descriptor aggregation procedures, namely: (1) the standard BoF approach based on 0order statistics, (2) the Vectors of Locally Aggregated Tensors (VLAT) method [START_REF] Negrel R | Using spatial pyramids with compacted vlat for image categorization[END_REF], which sums tensor products of the local descriptors, (3) Principal Component Analysis (PCA)-based VLAT descriptors, which reduce the size of the dictionary while improving further their discrimination power, and (4) we propose to further increase the compactness of the reduced-size signature by projection in a well chosen sub-dimensional space. Our evaluation of these approaches on 3D generic shapes and on 3D non-rigid shapes show that aggregation with high order statistics significantly outperforms standard BoF approaches both in terms of retrieval performance and in terms of compactness of the representation. The remainder of the paper is organized as follows. In section 2, the related works are presented. In section 3, the method is detailed. Then, in Section 4 the experiments are presented. Conclusions and future developments (Section 5) end the paper.

Related work

While Bag of Features approaches are very popular in 2D image analysis, few works have been introduced for 3D object recognition. Most of them are straightforward extension of the 2D approaches to 3D data. Existing approaches differ in the type of local features used in the construction of the visual vocabulary, and in the way these features are aggregated into signatures. Some of the approaches represent a 3D model by a set of 2D views which are indexed using bags of 2D SIFT features [OOFB08, LGS10]. Other techniques use features extracted directly on the surface of 3D shapes. Liu et al. [LZQ06] and Li and Godil [START_REF] Godil | Exploring the bag-of-words method for 3d shape retrieval[END_REF] use Spin Image descriptors computed on a dense set of feature points uniformly sampled on the surface of the 3D model. Toldo et al. [START_REF] Toldo R | The bag of words approach for retrieval and categorization of 3D objects[END_REF] segment the shape into regions and describe each region with several descriptors. A 3D shape is then modeled as a histogram of sub-parts occurrences. Segmentation-based BoF have the advantage of capturing some semantics of the shapes. Tabia et al. [START_REF] Tabia | Three-dimensional object retrieval based on vector quantization of invariant descriptors[END_REF] represent each 3D object as a vector of weighted occurrences of features. In all these works, spatial relationships between features are lost in the construction of the signatures. Lavoue [START_REF] Lavoué | Combination of bag-of-words descriptors for robust partial shape retrieval[END_REF] and Bronstein et al. [START_REF] Bronstein | Shape google: Geometric words and expressions for invariant shape retrieval[END_REF] add spatial relationships to take into account the spatial information between feature points. Most of BoF-based 3D retrieval approaches focus on the type of features and little attention is given to the way these features are aggregated into signatures. Consequently the BoF vector that results from the representation is of very high dimension, particularly when dealing with large-scale databases. Our main contribution in this paper is a new step for descriptor aggregation into compact signatures, while improving the high discrimination power of the descriptor. The challenge in using dictionary-based approaches is to find a good tradeoff between discrimination power, the size of the descriptor, and the scalability to large object databases. First, most of the methods used in 3D retrieval represent a 3D model with a histogram of frequency of occurrences of the visual words in the model. This is a direct adaptation from the basic BoF approach used by the computer vision and pattern recognition communities for image retrieval and categorization [SZ03]. To the best of our knowledge, other variants of BoF approaches have never been applied to the problem of 3D model retrieval. For example, these methods have been generalized using coding/pooling schemes, and achieve good performances in image categorization with the same feature size, using Locality-constrained Linear Coding (LLC) [WYY * 10]. Representing a 3D model with a vector of frequencies of occurrences of the visual word corresponds to 0-order statistics of the distribution of the visual words. In this paper, we explore the usage of high order statistics. The most popular method is the Fisher Vectors (FV) [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]. FV describes how the set of descriptors deviates from an average distribution of descriptors, modeled by a parametric generative model, usually a Gaussian Mixture Model. The FV achieves better results than BoF approaches [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF], but at the cost of a larger index and higher search time. Jerge et al. [JPD * 12] proposed a set of approximation and compression techniques so that FV can be used on large image datasets. Negrel et al. [START_REF] Negrel R | Using spatial pyramids with compacted vlat for image categorization[END_REF] build efficient signatures by linearizing the kernel function on bags. A Kernel function on bags aims at computing a similarity analog to votebased systems, but with respect to Mercer's condition. Their huge computational complexity can be highly reduced using linearization techniques based on tensors, called Vectors of Locally Aggregated Tensors (VLAT). VLAT performances are comparable to Fisher Vectors [START_REF] Negrel R | Using spatial pyramids with compacted vlat for image categorization[END_REF]. The size of the dictionary produced by VLAT can be significantly reduced using Compact VLAT [NPG12a].

In this paper, we study for the first time the performance of these different variants of BoF techniques on 3D model retrieval tasks. We will show that Vectors of Locally Aggregated Tensors (VLAT) and Principal Component Analysisbased VLAT outperform significantly the standard BoF techniques in terms of retrieval performance. We propose also Compact VLAT, which reduces significantly the size of the shape descriptor, and show that it achieves relatively good performance which makes it suitable for broad classification c The Eurographics Association 2013.

Method overview

Figure 1 gives an overview of the proposed method. First in a pre-processing step, we normalize the models to ensure that the extracted descriptors are invariant to translation and scale. Then, we render depth maps of the object from n views uniformly sampled on the surface of a bounding unit sphere. We represent each depth map as a collection of dense Histogram of Oriented Gradients (HoG) descriptors. HoG have the advantage of being compact and easy to compute. We then build a shape signature by aggregating the descriptors using the BoF paradigm. In this paper we explore and evaluate various BoF schemes, namely: (1) the standard BoF approaches, which describe a 3D shape as a vector of frequencies of occurrences of the visual words, (2) the Vector of Locally Aggregated Tensors (VLAT), which have been originally proposed for image analysis [NPG12a]. They have the advantage of being compact and efficient for large-scale image retrieval, (3) we further reduce the size of descriptors constructed with VLAT, while improving further their discrimination power, by using Principal Component Analysis (PCA) on the VLAT vectors, and (4) finally, we proposed a new version called compact VLAT, which builds a compact vector and show that it is suitable for rough classification of 3D shapes. The methods proposed in this paper have several advantages. They are invariant to rigid transformations and some articulated deformations and are robust to geometrical and topological noise. They are robust to the level of tessellation of 3D models. They handle any type of 3D shape representations as long as depth images can be rendered. The important deviation from the state-of-the-art is that they rely on compact dictionaries (256 or 512 visual words) but achieve significantly better performance than classical BoF methods.

Dense feature extraction

Prior to feature extraction, we need to proceed to a robust normalization of pose and scale of the 3D objects in order to remain invariant to two geometrical transformations (translation, scaling). Here, we do not perform the pose normalization for rotation because the locations of local features are completely ignored in our method. For the center and the scale, we use the smallest enclosing sphere [START_REF] Godil | Visual similarity based 3d shape retrieval using bag-of-features[END_REF]. The use of the smallest enclosing sphere has several advantages: it is fast to compute, it allows the maximization of the model size inside the unit sphere. We represent a 3D object with a set of depth maps captured by virtual cameras distributed uniformly around the object, see Figure 2. In order to capture all the important features of the object, we use a large number of views (80 in our implementation) and capture depth images of size 256 × 256. From the depth images, we extract a dense set of HoG descriptors on a dense regular grid. Every two pixels we compute one HoG descriptor at four different scales (16 × 16, 24 × 24, 32 × 32 and 40 × 40 pixels). We then obtain a large unordered set of local descriptors.

Let B i = {b ir , r = 1 . . . n} be the set of descriptors extracted from the depth images of model i. Unlike [LGS10], we do not maintain a separate set of descriptors for each view. Instead, we put all the descriptors in a single bag and use them to build our compact dictionary. This makes the descriptor invariant to rotations of the 3D model. Also, given a sufficiently large number of views and a densely sampled HoG descriptors, we insure that the most important features of an object are captured by the representation. One method to map the set of descriptors into a single vector that can be used for indexation is the Bag of Features analysis to build compact yet very discriminative shape signatures using a small dictionary size.

VLAT: Tensor based aggregation

Let B i = {b ir } and B j = {b jr }, r = 1 . . . n, be two bags of features representing the sets of descriptors in two 3D shapes i and j. An effective method to compute the similarity between two bags is based on kernel functions. Thanks to mathematical properties like Mercer conditions, these kernel functions on bags can be used with many powerful kernelbased learning techniques. The novelty in this paper is that we consider a kernel function on bags for each cluster c:

K(B i , B j ) = ∑ c K B (B ic , B jc ) (1)
with B ic = {b icr }r the descriptors of model i that belong to cluster c. K B is a kernel on the bags B ic and B jc , which we define as the sum of Gaussian kernels on each pair of descriptors belonging to B ic and B jc .

K B (B ic , B jc ) = ∑ r,s e -1 σ 2 ||bicr-b jcs || 2 (2)
Computing a Gaussian kernel on each pair of descriptors is computationally prohibitive, especially for large bags (O(n 2 ) for a dictionary of size n). Thus our second idea is to linearize the Kernel functions on bags. To do so, we first normalize all the descriptors to have a unit length. Then we expand it using Taylor series, and finally linearize the kernel function using tensor products: When stopped at p = 2, the expansion corresponds to the second order statistics of the set B ic . To extends the range of the similarity measure, we propose to center the obtained tensors by the mean tensors of each cluster c. The mean and tensors of the cluster have been learned during the dictionary construction. We proceed as follows;

K B (B ic , B jc ) = e -2 σ 2 ∑ r,s
• First, we compute the mean descriptor µc and mean tensor matrix Tc of each cluster c:

µc = 1 |c| ∑ i ∑ r b icr (3) Tc = 1 |c| ∑ i ∑ r (b icr -µc)(b icr -µc) T (4)
where |c| is the number of descriptors in cluster c and b icr are the descriptors of model i that belong to c. The quantities µc and Tc provide statistical summaries of the shape cluster and capture the main variabilities. • Next, for every 3D model i we compute one feature per cluster c. We compute a tensor T ic as an aggregation of the centered tensors of centered descriptors:

T ic = ∑ r (b irc -µ c )(b icr -µ c ) -Tc (5)
where µ c is the center of cluster c. We flatten the matrix T ic into a feature vector x ic , the descriptor of the 3D shape i with respect to cluster c. • Finally, we concatenate all the vectors x ic of object i to form a single feature X i = {x ic }, c = 1 . . . n, where n is the size of the dictionary. X i is called the VLAT signature of model i.

For best performance, we perform a normalization step of the X i signature.

∀ j, X i [ j] = sign (X i [ j]) |X i [ j] | α , (6)
V i = X i X i (7)
With α = 0.05 typically. VLAT performs very good results in similarity search and automatic indexing of 3D objects with linear metric, but leads to large feature vectors. The size of VLAT features is n d × d, where n is the number of clusters and d is the dimension of the descriptor.

PCA-based VLAT (PVLAT)

To reduce the dimension of the VLAT descriptor, we perform a tensor decomposition using Takagi's factorization:

Tc = AcDcA c ( 8
)
Where Dc is a real non-negative diagonal matrix containing the eigenvalues of Tc and Ac is unitary composed of eigenvectors of Tc. Then we project the centered descriptors belonging to c on the eigenvectors:

b icr = A c (b icr -µ c ). (9)
We can then deduce form equation 5 the new signature called PVLAT of the model i in cluster c as the sum of tensors of projected descriptors b icr belonging to cluster c, centered by Dc:

T ic = ∑ r b icr b icr -Dc. ( 10
)
Similar to VLAT, we concatenate and normalize each cluster signature. The size of the final PVLAT signature depends on the number of eigenvector selected in each cluster.

Compact PCA-based VLAT (CPVLAT)

We propose to further reduce the size of the PVLAT signature while retaining its discriminative power. Given a set S of N 3D models, we compute the Gram matrix G of PVLAT signatures:

G i, j = V i V j , i, j ∈ S (11)
Then, we compute the eigenvalues and eigenvectors of the Gram matrix G. Then, we compute a low rank approximation of G. We denote by Lt the matrix with the t largest eigenvalues on the diagonal:

Lt = diag (λ 1 ...λt ) , (12)
and we denote by Λt the matrix of the first t eigenvectors:

Ut = [Λ 1 ...Λt ] , (13)
We can then define Gt as an approximation of G:

Gt = Ut Lt U t (14)
Then, we compute the projectors of PVLAT signatures in approximated subspace:

Pt = VUt L -1/2 t (15) with V = [V 1 ...V N ]
is the matrix of PVLAT signatures. This method is analogous to Kernel-PCA using a dot product Kernel. For each 3D model, we compute the projection of PVLAT in the sub-space as:

Y i = P t V i (16)
Y i contains an approximate and low dimensional version of V i . The subspace defined by the projectors preserves most of the similarity even for very small dimension because the PVLAT optimization has concentrated the information in a small number of dimensions. One can notice that this procedure is analogous to that of a kernel PCA with a linear kernel.

Experiments and results

In our method implementation, for each 3D shape in the dataset, we capture a set of depth maps from different view points. To generate this set of depth maps for a model, we create 2D projections from multiple viewpoints. These viewpoints are equally spaced on the unit sphere. In our current implementation, we use 80 depth maps. Actually, each model was normalized for size by rescaling it so that the average Euclidean distance from points on its surface to the center of mass is 0.5. Then, all models were normalized c The Eurographics Association 2013.

for translation by moving their center of mass to the origin. Then, for each depth map, we extract HOG features on a dense grid, one HOG feature every two pixels, with four different scales 16 × 16, 24 × 24, 32 × 32 and 40 × 40 pixels. For dictionary construction, we use the K-Means Algorithm. To evaluate our method, we used two different 3D model databases. The first one is the SHREC 2012 Generic 3D Shape Retrieval benchmark [LGA * 12] which is a standard shape benchmark widely used in shape retrieval community. The dataset contains 1200 three-dimensional models, classified into 60 object categories based mainly on visual similarity. We also present our results on a non-rigid database, the Mcgill dataset provided by Siddiqi et al. [SZM * 08] for articulated 3-D models. It contains 255 objects divided into ten classes (Ant, Crabs, Hands, Humans, Octopuses, Pliers, Snakes, spectacles, Spiders and Teddy). Each class contains similar 3D shapes under a variety of poses. We conducted four different experiments. In the first one (Table 1), we evaluate the performance of the three proposed signatures and analyze the effect of the dictionary size on their performances. In the second experiment (Table 2), we compare the performance of the proposed signatures to standard bag of features ones. In the Third experiment, we compare our methods to state-of-the-art methods benchmarked in SHREC 2012 [LGA * 12]. Finally, we investigate the robustness of the proposed PVLAT signature against non-rigid transformations. The first three experiments were conducted on the SHREC 2012 [LGA * 12] dataset. In the last experiment we describe results on the McGill dataset. To objectively evaluate our method we use a statistical tool provided by the SHREC 2012 and the McGill datasets to compare 3-D retrieval methods. Given a classification and a distance matrix computed with any shape matching algorithm, a suite of tools produces statistics and visualizations that facilitate the evaluation of the match results. It includes five evaluation metrics, namely: the Nearest Neighbor (NN), First-tier (1-Tier), Second-tier (2-Tier), E-Measures and Discounted Cumulative Gain (DCG). We also report the precision-recall graph.

Generic shapes

We first show the contribution of the VLAT, PVLAT and CPVLAT signatures to retrieval performance on generic 3D shapes from SHREC2012 [LGA * 12]. From Table 1, we see that our signatures have the same behaviour with dictionary size change. Proposed signatures are fairly stable when moving from 256 to 512 visual words. We can also see from Table 1 that the PVLAT based method performs the best, followed by the PCVLAT and the VLAT one. We observe a gain of 5.75% between VLAT and PVLAT which highlights the improvements brought by the signature optimization. Note that the size of the VLAT feature is n × d × d, with n the number of clusters and d the size of descriptors. That means, when d = 128 and n = 512, the size of the VLAT signature is 8M. When using the PVLAT, the size of the signature is reduced according to the number of eigenvector selected in each cluster. For the CPVLAT, the size of the signature depends on the low rank approximation of the Gram matrix. Here, we drastically reduce its dimension by keeping only 128 dimensions. So that, the final CPVLAT size is set to 128. Table 2 shows the performance of our method compared to standard BoF approach. We can clearly see that our method achieves significantly better retrieval performance. With only a dictionary of size 512 our method achieves 0.83 in the Nearest Neighbour measure against 0.68 for a standard BoF with a dictionary of 16384 visual words.

Table 3 shows a comparative evaluation of our method and five other methods presented in [LGA * 12]. As one can see our method performs better than LSD-sum, 3DSP and ZFDR. The DG1SIFT performs the best, followed by DVD+DB. Note that DG1SIFT combines three different methods for descriptor sampling: dense regular sampling, random sampling, and one global SIFT descriptor. DG1SIFT also uses the BoF paradigm, with a vocabulary size exceeding 13k, which is much higher than the approach we propose in this paper. These experiments show that our approach achieves good retrieval performances on standard 3D databases, while using a compact signature with few hundreds of dimensions. This makes our approach suitable for retrieval in web-scale databases. Figure 3 presents the Precision vs Recall plots of our method and the state of the art methods from [LGA * 12]. It is interesting to notice that our method and the ZFDR one present quite comparable performances, however our method's precision is slightly higher for low recall values. Our method clearly outperforms LSDsum and 3DSP methods.

Articulated Shapes

In order to evaluate the performance of our 3D shape retrieval approach on non-rigid 3D models, we use the McGill Articulated Shape Benchmark database. We have compared the performance of the PVLAT method with three recent algorithms on the McGill Database: Hybrid BoW approach from [START_REF] Lavoué | Combination of bag-of-words descriptors for robust partial shape retrieval[END_REF], the graph-based approach from Agathos et al.

[APP * 09] and the hybrid 2D/3D approach from Papadakis et al. [PPT * 08]. Table 4 presents the retrieval performance of the three algorithms compared to our PVLAT method. From this table, one can notice that the graph-based algorithm [APP * 09] performs the best. This is because of the robustness of the structural representation used in the algorithm against the articulation deformations. However, not only the computation complexity of graph matching algorithms, graph based representation have a limited discriminating power when searching for generic shapes, because only topology is taken into account. Moreover, for graph based methods, minor changes in topology may result in significant differences in similarity. So that, they cannot be applied to arbitrary meshes, because topological problems like holes disturb the computation of the effective structure of the objects. Although the PVLAT method does not con- sider the structural information of the shape, it obtains very comparable results to the graph-based algorithm and slightly better than the two other algorithms. The robustness of the PVLAT under non-rigid shapes can be probably due to the local HOG feature's robustness against the small isometric transformations.

Conclusion

We have presented a novel approach to generic 3D object retrieval using feature vectors constructed from local descrip-tors of object depth maps. In our approach, the descriptors are aggregated using Vectors of Locally Aggregated Tensors technique which showed to be a good approximation of insightful similarity measures between descriptors. We further reduce their size using Principal Component Analysis (PCA) on the VLAT vectors, while improving further their discrimination power. We also propose to increase the compactness of the reduced-size signature by projection in a well chosen sub-dimensional space. This subspace is obtained by a low rank approximation of the Gram matrix on a training set. The approach has been evaluated on two standard 3D shape retrieval benchmarks, demonstrating the method is suitable for generic shapes and produces very high retrieval accuracy even with presence of non-rigid transformations. A lot of future work remains. As the proposed signatures are very powerful and highly compacted, we plan to test it on web-scale datasets.

Figure 1 :

 1 Figure 1: Method overview: First we compute depth images of the model captured from cameras localized on the unit sphere. Then, local features (e.g. HoG) are extracted from the images. Finally, we compute the VLAT signature using deviations between covariance matrices of the codebook and covariance matrices of the descriptors.

  (BoF) [SZ03]. It involves the construction of a visual codebook (visual words) and the count of occurrences of these words in the 3D model. Applying in a straightforward manner the traditional BoF paradigm to 3D models that are represented with a large and dense set of descriptors will result in large dictionaries. We propose to use Vectors of Locally Aggregated Tensors (VLAT) recently proposed in [NPG12a] for image c The Eurographics Association 2013.

Figure 2 :

 2 Figure 2: Example of 3D models from the McGill (models in the two first rows) and the Shrec12 (models in the two other rows) data-sets. The first column shows renderings of the models, while the other columns show depth images extracted randomly from the corresponding models.

⊗

  p b icr , ∑ s ⊗ p b jcs with ⊗ p x the tensor product of order p of the vector x.

Figure 3 :

 3 Figure 3: Precision recall graph for our approach on the SHREC 2012 dataset compared to state-of-the-art graphs.

Table 1 :

 1 Proposed method performances with respect to the dictionary size.

	c The Eurographics Association 2013.

Table 2 :

 2 Comparison with Bag of Features.

Table 3 :

 3 Comparison with state-of-the-art methods as reported in the shape retrieval context SHREC 2012 [LGA * 12] .

	Methods	NN	1-Tier	2-Tier	e-Measure	DCG
	DG1SIFT [LGA * 12]	0.879	0.661	0.799	0.576	0.871
	PVLAT	0.8342	0.4844	0.6234	0.4421	0.7807
	DVD+DB [LGA * 12]	0.831	0.496	0.634	0.450	0.785
	ZFDR [LGA * 12]	0.818	0.491	0.621	0.442	0.776
	CPVLAT	0.8133	0.3628	0.4323	0.3105	0.6821
	VLAT	0.7767	0.4074	0.5158	0.3654	0.7173
	3DSP_L3_200_hik [LGA * 12]	0.708	0.361	0.481	0.335	0.679
	LSD-sum [LGA * 12]	0.517	0.232	0.327	0.224	0.565
	Methods		NN	1-Tier 2-Tier	DCG
	Graph-based algorithm [APP * 09]	0.976	0.741	0.911	0.933
	PVLAT		0.969	0.658	0.781	0.894
	Hybrid BoW algorithm [Lav12]	0.957	0.635	0.790	0.886
	Hybrid 2D/3D algorithm [PPT * 08] 0.925	0.557	0.698	0.850

Table 4 :

 4 Results on McGill dataset. [DT05] DALAL N., TRIGGS B.: Histograms of oriented gradients for human detection. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) -Volume 1 -Volume 01 (2005), CVPR '05, pp. 886-893. 1

c The Eurographics Association 2013.Tabia et al. / Compact Vectors of Locally Aggregated Tensors for 3D shape retrieval

Acknowledgements

This work has been partly supported by the Culture3DCloud project. Hamid Laga is supported by the South Australian State Government through its Premiers Science and Research Fund.