Hervé Goëau

Pierre Bonnet
email: pierre.bonnet@cirad.fr

Alexis Joly

Vera Bakic

Daniel Barthelemy
email: daniel.barthelemy@cirad.fr

Nozha Boujemaa
email: boujemaa@inria.fr

Jean-François Molino
email: jean-francois.molino@ird.fr

The ImageCLEF 2013 Plant Identification Task

Keywords: ImageCLEF, plant, leaves, leaf, flowers, fruits, bark, stem, species, retrieval, images, collection, identification, fine-grained classification, evaluation, benchmark

The ImageCLEFs plant identification task provides a testbed for a system-oriented evaluation of plant identification about 250 species trees and herbaceous plants based on detailed views of leaves, flowers, fruits, stems and bark or some entire views of the plants. Two types of image content are considered: SheetAsBackgroud which contains only leaves in a front of a generally white uniform background, and NaturalBackground which contains the 5 kinds of detailed views with unconstrained conditions, directly photographed on the plant. The main originality of this data is that it was specifically built through a citizen sciences initiative conducted by Tela Botanica, a French social network of amateur and expert botanists. This makes the task closer to the conditions of a realworld application. This overview presents more precisely the resources and assessments of task, summarizes the retrieval approaches employed by the participating groups, and provides an analysis of the main evaluation results. With a total of twelve groups from nine countries and with a total of thirty three runs submitted, involving distinct and original methods, this third year task confirms Image Retrieval community interest for biodiversity and botany, and highlights further challenging studies in plant identification.

Introduction

Convergence of multidisciplinary research is a key to answer profound challenges of humanity related to health, biodiversity or sustainable energy. The integration of life sciences and computer sciences has a major role to play towards managing and analyzing cross-disciplinary scientific data at a global scale. More specifically, building accurate knowledge of the identity, geographic distribution and uses of plants is essential if agricultural development is to be successful and biodiversity is to be conserved. Unfortunately, such basic information is often only partially available for professional stakeholders, scientists and citizens, and often incomplete for ecosystems that possess the highest plant diversity. A noticeable consequence, expressed as the taxonomic gap, is that identifying plant species is usually impossible for the general public, and often a difficult task for professionals, such as farmers or wood exploiters and even for the botanists themselves. The only way to overcome this problem is to speed up the collection and integration of raw observation data, while simultaneously providing to potential users an easy and efficient access to this botanical knowledge. In this context, content-based visual identification of plant's images is considered as one of the most promising solution to help bridging the taxonomic gap. Evaluating recent advances of the Image Retrieval community on this challenging task is therefore an important issue. This paper presents the plant identification task that was organized for the third year running within ImageCLEF 6 [10] dedicated to the system-oriented evaluation of visual based plant identification. Like previous year, the task is more related to a retrieval task instead of a pure classification task in order to consider a ranked list of retrieved species rather than a single brute determination. Visual content was being the main available information but with additional information including contextual meta-data (author, date, locality name and geotag, names at different taxonomic ranks) and some EXIF data. Each year try to take to the next level the challenge to a more realistic scenario by covering progressively one entire flora at the scale of one wide region like France. After two years focused exclusively on leaves mainly from Mediterranean tree species, the task focused this year on 250 species of herbs and trees species living in France with different views or organs of plants: photographs of flowers, fruits, barks, leaves and the entire view of the plants. Finally, it was two types of content which were considered: a SheetAsBackground category containing scans and scan-like photographs of leaves in a front of a generally white uniform white background, and a NaturalBackground with most of the time a cluttered natural background of the 5 types of organs. The main originality of this data is that it was specifically built through a citizen sciences initiative conducted by Tela Botanica7 , a French social network of amateur and expert botanists. This makes the task closer to the conditions of a real-world application: (i) organs of the same species are coming from distinct plants living in distinct areas and with at distinct growing stages, (ii) pictures and scans are taken by different users that might not used the same protocol to collect the leaves and/or acquire the images, (iii) pictures and scans are taken at different periods in the year.

2 Task resources 2. [START_REF]The icl plant leaf image dataset[END_REF] The Pl@ntView dataset Building effective computer vision and machine learning techniques is not the only side of the taxonomic gap problem. Speeding-up the collection of raw observation data is clearly another crucial one. The most promising approach in that way is to build real-world collaborative systems allowing any user to enrich the global visual botanical knowledge [START_REF] Goëau | Visual-based plant species identification from crowdsourced data[END_REF]. To build the evaluation data of Image-CLEF plant identification task, we therefore set up a citizen science project around the identification of common woody species covering the Metropolitan French territory. This was done in collaboration with Tela Botanica social network and with researchers specialized in computational botany. Technically, images and associated tags were collected through a crowd-sourcing web applications [START_REF] Goëau | Visual-based plant species identification from crowdsourced data[END_REF], [13] and were all validated by expert botanists. Several cycles of such collaborative data collection and taxonomical validation occurred. Scans of leaves were the first type of pictures collected thanks to the work of active contributors from Tela Botanica since the summer 2009. The idea of collecting only scans of leaves first was to initialize training data with limited noisy background and to focus on plant variability rather than mixed plant and view conditions variability. This allowed to collect a first dataset of 2228 scans over 55 species. A first public crowd-sourcing web application8 was then opened in October 2010 and additional data were collected up to March 2011. The new collected images were either scans, or photographs with uniform background (referred as scan-like photos), or unconstrained photographs with natural background. It involved besides 15 new species from the previous set of 55 species. In April 2011 a new version of the web application has opened 9 and the acquisition protocol was extended to 4 more types of views with a natural background mentioned below, and focusing to the same limited set of species. During the last two years, members from Tela Botanica contribute regularly every month on more and more species, the final ambition being to cover the entire vascular French flora (around 6000 species) with numerous pictures of different plant organs, with numerous plant observations spread all over France at different growing stages photographed by a crowd of photographers, introducing slowly over the months great visual and morphological variabilities. However, for each year task, we decided to limit the number of species in the task by keeping only the most populated ones in terms of images and plant observations. This is why like the first year we decided to focus again only on leaves during the ImageCLEF 2012 Plant Identification task with a number of 125 species, because at the time of the task we didn't collected sufficiently pictures of complementary organs. This year, we decided to propose to add these complementary views while we added to the previous dataset Pl@ntLeaves 125 new more species more focusing on herbaceous plants than threes in order to cover more diversity of the French flora. Complementary views concerning flowers, fruits, stems and entire views associated to previous species and previous plant observations yet contained in the 2012 dataset were also added. Finally, the Pl@ntView dataset used within ImageCLEF2013 plant task contained 26077 images collected by 327 distinct contributors: 11031 for the SheetAsBackground category and 15046 for the Na-turalBackground (in more details 16% of leaves, 18% of flowers, 8% of fruits, 8% of stems and 8% of entire plant). The figure 2.1 gives some examples illustrating the type of views, but illustrating also the fact that a species does not contain systematically at least one image for each organ.

Pl@ntView metadata

Each image of Pl@ntView dataset is associated with the following meta-data:

-IndividualPlantID: plant observation identifier -Date: date and time of plant observation -Type: SheetAsBackground or NaturalBackground -Content: Flower, Fruit), Leaf, Stem or Entire -Taxon: full taxon name according the botanical database[4](Regnum, Class, Subclass, Superorder, Order, Family, Genus, Species) -ClassId : species identifier -VernacularNames: English common name -Author name of the author of the picture -Organization name of the organization of the author -Locality locality name (a district or a country division or a region) -GPSLocality GPS coordinates of the locality.

Concerning the locality information, note that sometimes the GPS can be very imprecise when the locality was not mentioned: in this case we used the GPS coordinates of the district or the country division or a region, according to the level of information available. Metadata is stored in independent xml files, one for each image. Additional but partial meta-data information can be found in the image's EXIF, and might include the camera or the scanner model, the image resolution and dimension, the optical parameters, the white balance, the light measures, etc.

About other plant datasets

A crucial added-value of this collection over older ones used in the literature (such as Swedish [START_REF] Söderkvist | Computer Vision Classification of Leaves from Swedish Trees[END_REF], ICL [START_REF]The icl plant leaf image dataset[END_REF], Flavia [START_REF] Wu | A leaf recognition algorithm for plant classification using probabilistic neural network[END_REF] or Smithsonian [START_REF] Agarwal | First steps toward an electronic field guide for plants[END_REF]), is that it was built in a collaborative manner, through a citizen sciences initiative, and in collaboration with a well established social network specialized in botany. This makes it closer to the conditions of a real-world application: (i) pictures of organs of the same species are coming from distinct plants living in distinct areas (ii) pictures and scans are taken by different users that might not used the same protocol to collect the leaves and/or acquire the images (iii) pictures and scans are taken at different periods in the year. Intra-species visual variability and view conditions variability are therefore more stressed-out. In the end, this makes our identification challenge much more realistic but also more complex. We can mention here two other challenging datasets, the OxfordFlower [START_REF] Nilsback | A visual vocabulary for flower classification[END_REF] dataset, and the MobileFlora [5] one, which are indirectly built in a collaborative manner through web crawling but without (or very partially), contextual information like the author, the location, the date, etc. They unfortunately also come with a set of drawbacks or unrealistic properties: (i) they include only flower images (ii) they focus on the most represented species on the web rather than the most represented in a given area (iii) the definition of the taxonomic classes is not rigorous (sometimes genus, sometimes species, sometimes nothing well defined). Finally, the plant branch of the huge crowdsourced dataset ImageNet [START_REF] Deng | ImageNet: A Large-Scale Hierarchical Image Database[END_REF] could be interesting for our problem but it unfortunately contains too much errors, noisy classes and too sparse tags (typically about the type of view or the depicted organ).

Pl@ntViews variability

The ImageCLEF 2012 overview [START_REF] Goëau | The ImageCLEF 2012 plant identification task[END_REF] provided numerous illustrations of the wide visual variability of the leaves. We present here more visual variability concerning the new introduced organs.

Flower There is a great diversity within flowers and it is an intensive subject of studies by botanists since the flower is often the key for identify a species. Flowers of the dataset can be categorized according to the color (see figure 2), the symmetry (see figure 3), the number of petals (see figure 4) and the size (see figure 5). Most of the time one species is associated to one category, but there are exceptions like in figure 6 where for one same species the flowers can have different colors.

Besides this first categorisation, botanists studied the Brown White Green Rose Blue Yellow inflorescence, i.e. the internal structure of the flower and the organisation of the flowers on a plant. Species from a same taxonomical group generally share a same organization, and thus a same visual appearance. Figure 7 gives all the type of inflorescence contained in the dataset. Some type of inflorescence can be very noticeable and very typical of a group of species. However, at the opposite some very distinct groups of species in the taxonomical hierarchy can have a very distinct visual appearance, but sharing a same type of inflorescence.

Fruit The fruit is the transformation of the flower and it can be also categorized into distinct types. The figure 8 shows the great diversity of type of fruits that are represented through the 250 species of the Pl@ntView dataset. The different modes of dissemination gives a second complementary and interesting way to show the visual diversity of the fruits in the dataset. Indeed, a same mode of dissemination of (even very) distinct species involves generally some same morphological features. For instance, for the endozoochory dissemination (seed dispersal by animals) the fruits are generally colored for attracting birds for instance.

Stem

The stem is generally a difficult plant sub-part for identifying a species, maybe because the visual information is mainly expressed with the texture, less by the color and or the shape. Age of the plant is second difficulty for analysing the stem, more precisely for the trees and theirs barks. Through the collaborative process, the dataset contains for numerous species, different plants at different ages and fill partially the wide diversity of the barks. The figure 10 shows a representative example for the species Robinia pseudo-acacia with young and old trees: more the tree is young more it has some thorns as a strategy of defence. Entire The entire view is maybe the most difficult view for identifying with precision a species, because this kind of view generally does not contain sufficiently information, and because a same species can have a very different general appearance depending to the geographical and climatic conditions. However, more the plant is small (young or intrinsically small), more the "useful" organs for identification are visible. The figure 11 shows one big tree of Magnolia grandiflora L. where it is very difficult or even impossible for identifying the pant if we look the entire view. The second plant is a small herbaceous species of Gentiana pneumonanthe L. where we can see that the flower is very visible on the entire view for identification.

Species Flower Entire

Magnolia grandiflora L.

Gentiana pneumonanthe L. 3 Task description

Training and Test data

The precise goal of the task was to retrieve the correct species among the top k species of a ranked list of returned species, one list for each image of a test dataset. Participants received a first training set of annotated images in order to explore different techniques and train their system. Six weeks later participants received the test set containing images without species labels, but with the view type, organ type, author, organization and plant identifier tags. Then, 2 months later, participants were allowed to submit up to 4 run files, most of the time related to variations of the same method. A particular attention was paid when splitting the data into training and test subsets to avoid any bias. Several pictures in the dataset might actually depict the same individual plant (or neighboring plants) observed in the same conditions (same person, day, device, lightening conditions, etc.). Randomly splitting images in a nave way would therefore favor having such near-duplicate images in both the training and the test subsets, making the recognition much more easy. To avoid this bias, we therefore performed our random split at the observation level rather than at the image level thanks to associated metadata (observation id when available, author, date, etc.

Task objective and evaluation metric

According to similar concerns, the primary metric used to evaluate the submitted runs uses a two-stage average of raw image scores, one at the observation level (i.e. we compute the average score of all images belonging to the same observed plant), and one at the user level (i.e. we average the scores of the observations of a given user). A flat mean would actually have introduce some new bias with regard to a real world identification system. Indeed, as the dataset was built in a collaborative manner, it appears that few contributors often provide much more pictures than many other contributors who provided few (long tail distribution). Since we want to evaluate the ability of a system to provide correct answers to any user, we rather measure the mean of the average classification score per author. Furthermore, some authors sometimes provided many pictures of the same individual plant (to enrich training data with less efforts). Since we want to evaluate the ability of a system to provide the correct answer based on a single plant observation, we also decided to average the classification rate on each individual plant. The raw image score itself is computed for each test image as the inverse of the rank of the correct species in the list of retrieved species.

More formally, our primary metric was defined as the following average score S:

S = 1 U U u=1 1 P u Pu p=1 1 N u,p Nu,p n=1 s u,p,n (1)
U : number of users (who have at least one image in the test data) P u : number of individual plants observed by the u-th user N u,p : number of pictures taken from the p-th plant observed by the u-th user s u,p,n : score between 1 and 0 equals to the inverse of the rank of the correct species for the n-th picture taken from the p-th plant observed by the u-th user It is important to notice that while making the task more realistic, the normalized classification score also makes it more difficult. Indeed, it works as if a bias was introduced between the statistics of the training data and the one of the test data. It highlights the fact that bias-robust machine learning and computer vision methods should be preferred to train such real-world collaborative data. Finally, to isolate and evaluate the impact of the image acquisition type (Sheet-AsBackground, NaturalBackground, a normalized classification score S was computed for each type separately. Participants were therefore allowed to train distinct classifiers, use different training subsets or use distinct methods for each data type.

Participants and techniques

With 12 finalist groups coming from all around the world over 9 countries and 33 submitted runs, the 2013 edition of the task confirmed its increasing attractiveness (respectively 10 and 11 groups crossed the finish line in 2011 and 2012) although its complexity was higher (with heterogeneous view types). Participants were mainly academics, specialized in computer vision and multimedia information retrieval. We list below the participants and give a brief overview of the techniques they used in their runs. We remind here that ImageCLEF benchmark is a system-oriented evaluation and not a deep or fine evaluation of the underlying algorithms. Readers interested by the scientific and technical details of any of these methods should refer to the ImageCLEF 2013 working notes of each participant (referenced below): AGSPPR (3 runs) [START_REF] Zhang | Agsppr at imageclef 2013 plant identification task[END_REF], China. AGSPPR team focused their work on the SheetAsBackground category and submitted 3 runs using distinct visual features and approaches: a global shape feature (i.e. the leafs area length of major axis and length of minor axis), SIFT features (run 2), and an extension of the CENTRIST approach (CENsus Transform hISTogram []) called SPACT designed for reducing the number of descriptors with a PCA algorithm (run 3). For run 1 and 3, they used a multiclass Support Vector Machine (SVM) classifier with a radial basis kernel function, while they used a pure matching approach for the 2nd run. A two-stage late fusion scheme is then apply to combine the image response lists of the different modalities and of the different types of view. Metadata was also successfully used (in run 2), in particular the date for the flower category and the plant observation identifiers (to share the query images of the same plant). LAPI (1 run) [START_REF]Has an image classification approach any chance at all (in plant classification)?[END_REF], Romania. LAPI team proposed to exploit a complex approach for image description based on contour extraction, curve partitioning and abstraction. They suggest that their approach is a "structural alternative" to the prevailing gradient-based features (e.g. SIFT). Contrary to other teams, they considered a more difficult task by automatically recognizing the view type before recognizing the plant species. They used a classical Linear Discriminant Analysis (LDA) as classifier for both the view type recognition and the species prediction.

LIRIS REVES (2 runs) [START_REF] Cerutti | Late information fusion for multi-modality plant species identification[END_REF], France. ReVes team used the same supervised model-based segmentation strategy than the one they used during the 2012 leaforiented campaign and tried to extend it to the other types of view (although it was more difficult to build a priori shape models of that organs). They used a late fusion approach to combine the decisions of the classifiers of each modality as well as to combine the multiple images of a given individual plant when this occurred in the query set. They finally attempted to use the geo-tags available in the metadata by interpolating them thanks to external climatic data. MICA (3 runs) [START_REF] Le | Imageclef2013 plant identification mica[END_REF], Vietnam. MICA team experimented 3 distinct approaches. Run 1 used a GIST descriptor with a k-nearest neighbors rule on all types of view. Run2 was based on the same approach but with additional color and texture features for the Flower and Entire types of view. Run3 used a Bag of visual Words (BoW) approach based on SURF local features and an "un-sharp masking" pre-processing step to filter some background information.

Classification was achieved through a multi-class SVM.

NLAB UTOKYO (3 runs) [START_REF] Nakayama | Nlab-utokyo at imageclef 2013 plant identification task[END_REF], Japan. NLAB participant focused his work on visual features learning for building accurate image descriptions. A set of local features, mostly SIFT variations and a Self Similarity descriptor, were densely extracted in each picture according to a regular grid and then "augmented" with a supervised polynomial embedding technique taking into account neighboring local features. Further, these locally embedded and augmented features were encoded into a global Fisher Vector representation which allows an accurate classification with any linear classifier. In this work, linear logistic regression models were used. An independent classifier was trained for each raw descriptor and a late-fusion based an average log-likelihood of posterior probabilities was used to merge independent classifier results.

SABANCI-OKAN (1 run) [24]

, Turkey. This team submitted only one run using distinct features for the two categories. For the SheetAsBackground category, an automatic segmentation was performed using edge preserving morphological simplification by means of area attribute filters, followed by an adaptive threshold. Then, a variety of shape and texture features were extracted (the same than the ones used during the 2012 campaign). For the NaturalBackground category, a set of global features was extracted: HSV color auto-correlograms, weigthed-saturation hue histogram and other texture descriptors, depending on the considered organ. For the Flower, Fruit and Entire view types only color features were used, while for the Stem view type, texture features were used after a segmentation preprocessing step. The dates provided in the metadata were also exploited for the three first view types (that are likely to be more time dependent). Classification was performed through independent SVM classifiers, one for each view type.

SCG USP (4 runs), Brazil. This team submitted one run with a fully automatic approach (run 1) and three other ones runs involving human assistance for a background/foreground segmentation. More precisely, training pictures were segmented with the semi-supervised Grabcut algorithm, while test images were manually segmented. Then, numerous features were extracted: Gabor, LBP, fractal, geometrical features. The final classification step was performed with a LDA classifier, except for the 3rd run where a SVM classifier was used. Only the 4th run tried to train independent classifiers (i.e. one for each view type).

UIAC (3 runs) [START_REF] Serba | Combining image retrieval, metadata processing and naive bayes classification at plant identification[END_REF], Romania. Unlike the other groups, UAIC explored the strategy of integrating additional external training data to boost their performances. They actually crawled 507 additional pictures from Wikimedia Commons with relevant annotations. And this confirms the difficulty of collecting dense and accurate data specific to a given flora. From the technological point of view, they used the LIRe (Lucene Image Retrieval) engine and, after preliminary tests, they selected the Joint Composite Descriptor (JCD). The LIRe engines gives for each test image a list of training images where a candidate species potentially appears several times. Thus, they used 3 distinct approaches of combination in order to obtain a single score for each species: a max operator, a normalized sum, and a naive Bayes classifier. The results were further refined and ranked based on GPS metadata, author names and organization tags, assuming that certain authors and organizations would have a greater interest in certain plant species. Table 2 attempts to summarize the methods used at different stages (feature, classification, subset selection,...) in order to highlight the main choices of participants. This table should be used in next section on result analysis, in order to see if there are some common techniques which tend to lead to good performances.

Results

Global analysis

We present here an overview of the official results of the task and discuss the main findings. SheetAsBackground: Table 3 and figure 12 present the identification scores of the 33 submitted runs for the SheetAsBackground category. As expected, results on scans and scan-like images of leaves are generally higher than the photographs of the NaturalBackground category. The Sabanci Okan teams reached the highest scores of 0.607 with an approach mainly centered on leaf shape boundary features. Using contour-based approaches is confirmed to be an effective strategy by the good performances of the Inria PlantNet group and the Liris team. Interestingly, one team which used a more generic approach in computer vision (the NLabUTokyo team working with Fisher Vector representations), also obtained very good identification scores whereas they used exactly the same technique for the NaturalBackground category. Other teams who attempted to use non-contour based approaches obtained significantly lower scores.

Compared to the raw identification scores obtained during the 2012 campaign, we only noticed a slight increase (0.607 vs 0.58 for scans and 0.55 for scan-like). But it is important to remark that the task itself was more complex in several aspects: (i) scans and scan-like pictures have been merged in a single category (ii) the number of species was increased from 115 (scans) or 83 (scan-like) to 126 this year (iii) test images themselves were more complex (weaker lighting conditions, more shadows, more old dried leaves and less uniform background. NaturalBackground: Table 4 and figure 13 present the identification scores of the 33 submitted runs for the NaturalBackground category. As expected, results are significantly lower than the SheetAsBackground category due to the noisy backgrounds and clutter effects. The highest scores, obtained by the NLabU-Tokyo team, reached equivalent values than the 2012 task, but without any human assistance in the workflow, contrary to last year best runs that involved semi-automatic segmentation mechanisms. This is even more remarkable given that their approach was purely based on the visual content contrary to the second best run of the task (by Inria Plantnet team) which did make use of the date and the plant identifier tags. The contribution of using the metadata can be observed by comparing this run with the second best one of that team (Inria Plantnet run 1) that was purely based on visual data. Overall, the runs of these two teams represent the head of the pack with six (or even seven) runs clearly outperforming the other runs. Entire Flower Fruit Leaf Stem Nat. NlabUTokyo Run 3 run3 0,297 0,472 0,311 0,275 0,253 0,393 Inria PlantNet Run 2 plantnet inria run2 0,274 0,494 0,26 0,272 0,24 0,385 NlabUTokyo Run 2 run2 0,273 0,484 0,259 0,273 0,285 0,371 Inria PlantNet Run 1 plantnet inria run1 0,254 0,437 0,249 0,24 0,211 0,353 NlabUTokyo Run 1 all siftcopphsv cca 0,236 0,423 0,209 0,269 0,276 0,341 Inria PlantNet Run 3 plantnet inria run3 0,216 0,421 0,238 0,195 0,176 0,325 Inria PlantNet Run 4 plantnet inria run4 0,15 0,327 0,137 0,165 0,171 0,245 Sabanci Okan Run 1 Sabanci-Okan-Run1 0,174 0,223 0,194 0,049 0,106 0,181 DBIS Run 2 DBISForMaT run2 train2012 svm Scan12 Photo4 -1 4 0,102 0,264 0,082 0,034 0,095 0,159

DBIS Run 3

DBISForMaT run3 cross-val2013 svm feature4 con-fig60 1 2 3 0,109 0,256 0,079 0,035 0,095 0,158 DBIS Run 4 DBISForMaT run4 cross-val2013 svm feature5 con-fig80 Photo14 1 3 3 0,152 0,206 0,104 0,027 0,042 0,141 UAIC Run 4 run wiki max 1 0,09 0,136 0,12 0,08 0,128 0,127 DBIS Run 1 DBISForMaT run1 train2012 svm Scan4 Photo2 1 2 3 0,067 0,168 0,1 0,052 0,103 0,12 UAIC Run 1 run wiki sum 3 0,089 0,109 0,132 0,093 0,104 0,119 UAIC Run 2 run author10 GSP10 lire80 0,092 0,105 0,127 0,096 0,11 0,117 Liris ReVeS Run 2 LirisReVeS run2 0,026 0,102 0,082 0,161 0,166 0,092 Liris ReVeS Run 1 LirisReVeS run1 0,021 0,098 0,081 0,151 0,153 0,089 UAIC Run 3 run lire naivebayes 0,068 0,055 0,111 0,049 0,102 0,081 Vicomtech Run 1 outputCLEFTestMean 0,095 0,117 0 0 0,1 0,081 Vicomtech Run 2 outputCLEFTestMax 0,091 0,116 0 0 0,094 0,08 LAPI Run 1 LAPI run1 0,026 0,073 0,025 0,084 0,043 0,058 Mica Run 2 MICA-run2 0,016 0,086 0,048 0,014 0,014 0,053 Mica Run 3 Run3 0,016 0,013 0,048 0,11 0,014 0,042 SCG USP Run 3 SCG USP run3 0,017 0,025 0,042 0,047 0,054 0,03 I3S Run 1 new 100 0,017 0,023 0,041 0,038 0,025 0,026 I3S Run 2 new2 100 0,017 0,023 0,041 0,038 0,025 0,026 SCG USP Run 1 SCG USP run1 0,02 0,026 0,027 0,02 0,037 0,025 SCG USP Run 2 SCG USP run2 0,027 0,029 0,02 0,018 0,019 0,025 Mica Run 1 MICA-run1 0,016 0,013 0,048 0,014 0,014 0,023 SCG USP Run 4 SCG USP run4 0,019 0,014 0,022 0,031 0,021 0,017 AgSPPR Run 1 AgSPPR run1 0 0 0 0 0 0 AgSPPR Run 2 AgSPPR run2 0 0 0 0 0 0 AgSPPR Run 3 AgSPPR run3 0 0 0 0 0 0 Table 4. Normalized and detailed cores for each run for the NaturalBackground. HA=humanly assisted, Auto=full automatic. by most participants were significantly more accurate on that image type. This confirms the botanical expertise on the important role of flowers in the identification mechanisms as this organ was historically used as the primary one to distinguish species between each others (for flowering plants of course). This is good news that computer vision methods go in the same direction. Besides the Flower category, there was no clear second best organ or view type. Stem images provided surprisingly good results relatively to the botanist knowhow. Bark morphology is actually not considered as a the most accessible identification criterion for non-specialists. The texture itself is for instance highly correlated with the age of the plant. Identification results on the Entire plant views are also rather surprising regarding their higher complexity and variability. Overall, an important remark is that the ranking of the runs did not change much from an organ to another one, fostering the idea that generic methods might solve heterogeneous fine-grained classification problems. Metadata: Regarding the use of metadata, two runs (Sabanci Okan run 1 and Inria Plantnet run 2) exploited successfully the date for improving the results. Using the observation date complementary to the visual content was a simple and efficient way to obtain a gain of up to 4 points on the Flower view type (thanks to the relatively short flourishing period of many species). Inria Plantnet run number 2 exploited also the observation identifier tag in order combine the results of the query images coming from the same plant. But since the whole NaturalBackground test dataset did contain only a few plant observations with multiple images, the impact of using this tag is much lower than the impact of using the date field. On the other side, this multiple-image strategy was much more beneficial for the SheetAsBackground category as a significant number of plants were represented by several images (leaves used for scans are actually more likely to be collected in mass from the same plant). The runs of Inria In particular, Liris teams proposed to use the raw GPS data of the training set complementary to external environmental data in order to interpolate them and build coarse species distribution maps. These maps where used afterwards to prune the species returned by the visual search and keep only the most probable ones. Unfortunately, the results do not show a great improvement over the purely visual runs of these teams. This can be explained by the fact that the database doesn't yet contain enough numerous and dense observations to build an accurate geographic repartition of the species. Also, the geo-localization data is partially noisy due to heterogeneous precisions in the localization (points, cities, departments). Finally, the UAIC team tried to explore author and organization tags assuming that an authors or a group of author from a same organizations have more interest on specific groups of species. However the results did not show clearly some gain by using these user informations. None of teams neither explored the hierarchical taxonomy structure, nor the common names, which could be source of improvements. External data: UAIC explored the strategy of integrating additional external training data to boost their performances. They focused their search on Wikimedia Commons which contain more and more reliable contents related to species of life in general. They managed to crawl 507 additional pictures which is fine but clearly not sufficient to make a strong difference compared to tens of thousands of images in the training set. This confirms the difficulty of collecting dense and accurate data, specific to a given flora, and with relevant annotations (like organ and view type).

Impact of the global training strategy: Whereas some of the teams used a classical leave-one-image-out strategy cross-validate their training, some other ones used a more sophisticated leave-one-plant-out strategy that is closer to the real-world problem evaluated by the task. This second option seems to have take benefits to the teams using it, namely Sabanci Okan, NLabUTokyo, Liris ReVes and Inria Plantnet. Indeed, they all mentioned that they did not split images from the same individual plant in the training set, in order to avoid overfitting problems (images of the same plant can actually be very similar).

Back to purely visual approaches: I3S and MICA teams experimented, at least through one run, a standard approach in image categorization with SIFT or SURF features, visual bag of words (BoW) representations and SVM multiclass. MICA team obtained intermediate scores contrary to I3S team. Explanations for this difference, can be that MICA use of preprocessing step for unsharp mask of Leaf images from SheetAsBackground and NaturalBackground (see figure12 MICA run 3 and I3S runs where scores are very different on Leaf ). The more recent approach in image categorization based on Fisher Vector (FV) representations, which can be see as an extension of BoW, showed a clear gain regarding to the BoW runs as we can see with the 3 NLabUTokyo runs and the Plantnet Inria run 4 on the NaturalBackground category. NLabUTokyo obtained the best scores, maybe because they capture local spatial information by enriching dense local descriptors with polynomials, contrary to the Inria Plantnet run where patch are extracted around Harris corners and descriptors are directly embedded in Fisher Vector representations. Moreover NLabUTokyo used also a late fusion where classifiers are trained independently for each descriptor, while Inria Plantnet run 4 used an intermediate fusion by concatenating FV representations from the different type of descriptors. Besides, late fusion is also are shared approach for the best runs of Inria Plantnet team.

The fact that NLabUTokyo runs obtained almost the best results for all subcategories, confirms the idea that FV representation is a successful generic approach in spite of different type of visual contents. It is important to notice that the run 2 obtained close scores to the best one (run 3) without considering subcategory tags, which show that views tags are may be not essential for succeeding the task. This is an important conclusion since image tagging is an heavy process with users. However, this generic approach is not the most efficient on SheetAsBackground compared to contour based approaches dedicated to leaf shape analysis. This may show that generic approaches like the one used by the NLabUTokyo team is dependent to the background, and that through a dense grid patch extraction, their system learn a contextual information off the background. In particular this can be observed with the Fruit subcategory where NLabUTokyo run 3 outperforms other methods: fruits are generally small elements in the pictures difficult to capture, and also these organs appear often after the leafage, thus we can suppose these cluttered backgrounds have a non negligible contribution in the species contribution.

Performances per morphological features

Like in the previous working note with the leaf [START_REF] Goëau | The ImageCLEF 2012 plant identification task[END_REF], we try here to present some complementary results by analysing some morphological features, more precisely on the sexual organs which are the flower and the fruit. Beyond the methods used, we try to analyse which feature, which kind of flower or fruit is intrinsically more difficult than the others. The figure 20 shows detailed results by category of color. The graph to the left shows the proportion of image test by color used for computing and displaying the graph to the right. Results in this second graph are sorted in a decreasing order of mean performance over all the submitted run (except the AgSPPR's runs which not really participate to the NaturalBackground ). One can notice that the two most represented colors, the yellow and the white (more than 50% of the database) are not the ones which enables the best results, maybe rigthly because there is more species and thus more confusions and ambiguity. Green flowers, which is not so rare, seem to be the most difficult color maybe because it expresses no color in a sense and thus it is a difficult information to capture, notably if the flowers hidden with a background of leafage or grass. Similarly, the brown flowers may also be very confused with barks for trees where flowers appear before leaves, which can explain the performances on this color. The figure 21 attempts to give a complementary perspective of results about flower according to the inflorescence structure as mentioned in section 2.4. First of all we can see that the inflorescence categories are strongly unbalanced in terms of image number. Thus the best scores obtained by Cyathium, Panicle, Umbel and to a lesser extent Umbel, Captitulum and Solitary are no very representative for making some relevant conclusions on these types of inflorescences. Concerning the most representative ones the Cyme seems to be the type where the runs performed the best on average. The figure 22 gives the results according to the fruit type. As for the Fig. 21. Detailed results by inflorescence type inflorescence, unfortunately, some types of fruits are not well represented in the dataset like Silique, Cone, Folicle and to a lesser extent Legume. Even if this last type of fruit is not so well represented, it is interesting to note that all teams seem to have the best scores on Legume because the associated species are from a very large family of plants called Fabaceae which is spread all other the world. Then, it is difficult to highlight one type of fruit over the others, because there is always one best method at the same score around 0.4. We have just to note that the Samara (like "helicopters" from maple for instance) seem to be clearly the most difficult type of fruit, even when we look at the best run (not over 0.2). This paper presented the overview and the results of ImageCLEF 2013 plant identification testbed following the two previous one in 2011 and 2012. The number of participants increased from 8 to 12 groups showing an increasing interest in applying multimedia search technologies to environmental challenges. This year the challenge climb one step by considering multiple type of view and organs of plants while the number of species increased from 125 to 250 species and plant observations densely covered the French territory. Results are encouraging by scaling state-of-the-art plant recognition technologies to a real-world application with thousands of species might still be a difficult task. Despite increasing difficulties on SheetAsBackground images and the number of species, scores are high and show that leaf analyses is still the best way for identifying a plant, even if collecting new scans is more difficult than shooting photographs. Performances obtained on NaturalBackground category of unconstrained pictures of plant organs are very encouraging especially for the Flower when we look detailed results and where best methods can compete with scores SheetAs-Background. It corroborates a well-know usage of botanists for identifying plants and this is good news in a sense that computer vision methods go in the same direction. An interesting conclusion is that these good results on NaturalBackground images are obtained with generic visual classification technique without any specificity related to plants. With the emergence of more and more plant identification apps [2] [6], [5], [START_REF][END_REF] and the ecological urgency to build real-world and effective identification tools, we believe that the detailed results and conclusions of the task will be of high interest for the computer vision and machine learning community.

Fig. 1 .

 1 Fig. 1. Examples from the two categories and the five subcategories. Species does not contain systematically at least one image for each organ.

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Color variability of flowers.

Fig. 5 .

 5 Fig. 5. Sizes of flowers.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Color variability of flowers from one same species (Iris lutescens Lam.).

Fig. 8 .Fig. 9 .

 89 Fig. 8. Fruit types.

Fig. 10 .

 10 Fig. 10. The visual diversity of the bark of the Robinia pseudoacacia.

Fig. 11 .

 11 Fig. 11. The entire views for herbaceous species and three are very different. The smaller one has the possibility to show useful organs for identification.

Fig. 12 .

 12 Fig. 12. Scores for SheetAsBackground category.

Fig. 13 .

 13 Fig. 13. Scores for NaturalBackground category.

  Detailed results: Figures 17, 14

  , 18,19,16, and figure 15 display the identification scores for each view type separately (still for the NaturalBackground category). It shows that the average identification scores are significantly boosted by the good performances obtained on the flower images. Most techniques used Run name runfilename

Fig. 14 .

 14 Fig. 14. Detailed scores for Flower subcategory.

Fig. 15 .

 15 Fig. 15. Detailed scores for NaturalBackground subcategories.

Fig. 16 .

 16 Fig. 16. Detailed scores for Stem subcategory.

Fig. 17 .

 17 Fig. 17. Detailed scores for Entire subcategory.

Fig. 18 .

 18 Fig. 18. Detailed scores for Fruit subcategory.

  Plantnet and Liris ReVes teams exploited successfully this information for the SheetAsBackground category. As the previous years, several teams, like Liris Reves or UIAC, attempted to exploit the geo-localization information in order to refine candidate species list.

Fig. 19 .

 19 Fig. 19. Detailed scores for Leaf subcategory.

Fig. 20 .

 20 Fig. 20. Detailed results by flower color. The graph to the left represent the proportions of the tested images used for computing the detailed results in the graph to the right.This second graph gives the minimum, the median, the mean and the maximum scores over all the submitted runs for each flower color.

Fig. 22 .

 22 Fig. 22. Detailed results by fruit type.

Table 1 .

 1 ). Numerous images of the different views were automatically integrated in the training dataset since the associated plant observations were yet integrated last year task with the leaves. The training data finally resulted in 20985 images while the test data resulted in 5092 images. Detailed statistics of the composition of the training and test data are provided in Table 1. Composition of the training and test data

			Images Plants Authors Species
	SheetAsBackground	Train Test	9781 1250	732 150	36 14	126 70
	NaturalBackground	Train Test	11204 3842	2553 2454	176 229	244 238
	Entire	Train Test	1455 694	955 567	104 107	234 177
	Flower	Train Test	3521 1233	1328 970	127 142	233 203
	Fruit	Train Test	1387 520	512 302	64 77	156 103
	Leaf	Train Test	13285 2040	1046 420	73 68	210 143
	Stem	Train Test	1337 605	629 408	38 35	131 77
	All	Train Test	20985 5092	11204 3842	176 229	250 241

  DBIS (4 runs)[20], Germany. DBIS team runs are based on global visual features and a multiclass SVM classifier. These participants experimented numerous (early) combinations of about thirty global features, in order to select the best combination for each type of view. The selected features are predominantly based on color (Auto Color Correlogram, Border Interior Color, Color Histogram, Color Layout, Color Structure, EdgeHistogram, tamura, CEDD, FCTH). They also experimented several SVM parameters in order to boost theirs results. I3S (2 runs)[START_REF] Issolah | Sift, bow architecture and one-against-all support vector machines[END_REF], France. I3S team used a popular approach in the field of image classification: they extracted SIFT features in order to produce Bag of visual Words (BoW), one BoW vector by picture, from a 1000 visual words dictionary (built with kMeans clustering algorithm). BoW's are then exploited to train species model with SVM classifiers, one for each species and type of view. Species prediction of test images are produced with a one-against-all procedure. INRIA PLANTNET (4 runs)[START_REF] Bakić | Inria's participation at imageclef 2013 plant identification task[END_REF], France. For the SheetAsBackground category, after a basic Otsu segmentation, INRIA team used multiscale triangle representations, alone and combined with other shape-based descriptors (Directional Fragment Histogram and shape parameters). In addition, multi-image queries were considered, by using images belonging to the same plant observation in order to boost the results. For the NaturalBackground category, all the 4 submitted runs are based on local features (SURF, Fourier, rotation invariant Local Binary Patterns, Edge Orientation Histogram, weighted RGB and HSV

histograms). The last one uses a multi-cue Fisher Vector embedding [] with a one-against-all multiclass SVM classifier. The three first runs use Hamming embedding and hash-based approximate knn matching: all local features are hashed, indexed and searched in separate indices (one for each each type of view and type of feature) and retrieved images are scored by the number of matches.

Table 2 .

 2 Approaches used by participants. In training subset column, All means that the 2 categories where not distinguished, while Cat. means it is the case, and Subcat. means that the sub-categories (Flower, Fruit, Leaf, Stem, Entire) were considered for the NaturalBackground category. Column IP indicates if participants avoid to split images from a same Individual Plant during evaluation on training dataset.

	Team	Segmentation	Features	Classification	Train	Metadata IP
					subsets
	AGSPPR	√ (run 1)	SPACT, SIFT, global shape	Multiclass SVM with a radial basis func-tion kernel	Cat.
				(run 1&3). Matching approach (run2).
			Auto Color Correlogram, Border Inte-
	DBIS	×	rior Color, Color Histogram, Color Lay-out, Color Structure, Edge Histogram,	Distinct kernels by run for Multiclass SVM (RBF, polynomial, sigmoid)	Subcat. ×	×
			Tamura, CEDD, FCTH.
	I3S	×	SIFT + BOW	One against all Mutliclass SVM, linear kernel	Subcat. ×	×
	IINRIA PLANTNET LAPI LIRIS REVES	Otsu (Sheet, and run 3 for Natural with an abort cri-terion × Semi-supervised segmentation	Sheet: Multiple triangular representa-tions eventually combined with DFH de-scriptors and shape parameters Natural: Harris-like key points + SURF, LBP, weighted RGB, HSV, Fourier, EOH contour extraction with Canny + curve partitioning and abstraction + PCA Bagging features: Lab colors, Gabor wavelets, SURF Shape: centered moment, eccentricity, Hu/Zernike moments	Large Scale Matching approaches with late fusion schema or One against all multiclass SVM clas-sifier applied to Fisher Vectors Linear Discriminant Analysis Naive distance based classification	Flowering date, Indi-vidual plant ids Subcat. × Subcat. GPS with plant ids climate area Subcat. extension, Individual	× √ ×
			Gist (run1, 2), Color and texture his-
	MICA	Auto	togram (run2 flower, entire), SURF + Bow (run3)	SVM	Cat. (?) ×	×
	NLAB UTOKYO	×	dense grid SIFT, C-SIFT, Opponent-SIFT, HSV-SIF, self-similarity SSIM + polynomial embedding + Fisher Vec-tor Sheet: variety of contour based fea-	Linear Logistic Regression, late fusion	All., Cat., Subcat.	×	√
			tures, texture (Fourrier), color descrip-
	SABANCI-OKAN	Auto	tors, edge background/foreground his-Natural: HSV color auto-correlograms, togram.	SVM classifiers	fruit) Subcat. date (flower,	√
		run1: auto, run	weigthed-saturation hue histogram,
	SCG USP	2-3-4: manual for test, semi for train	Gabor, LBP, fractal, geometrical	LDA or SVM (run3)	Subcat. (only	GPS	×
					run4)
	UIAC VICOM-TECH	× color segmentation trace transform, shape relationship Joint Composite Descriptor	image result list fusion with max or sum operator, or naive bayesian approach Linear SVM 1-vs-all multi-class strategy All All	GPS, thor, organi-au-zation ×	× ×

Table 3 .

 3 Normalized classification scores for each run for the SheetAsBackground. HA=humanly assisted, Auto=full automatic.

http://www.imageclef.org/2013

http://www.tela-botanica.org/

it is closed now, but a newer a application can be found at http://identify.plantnetproject.org/en/base/plantscan

[START_REF]Has an image classification approach any chance at all (in plant classification)?[END_REF] http://identify.plantnet-project.org/fr/

Acknowledgements

This work was funded by the Agropolis fundation through the project Pl@ntNet (http://www.plantnet-project.org/) and the EU through the CHORUS+ Coordination action (http://avmediasearch.eu/). Thanks to all participants. Thanks to Jennifer Carré, Violette Roche and all contributors from Tela Botanica. Thanks to Souheil Selmi from Inria and Julien Barbe from Amap for their help.


C ¸agdas ¸bilen

Gilles Puy

Rémi Gribonval

Laurent Daudet

Balancing Sparsity and Rank Constraints in Quadratic Basis Pursuit

Keywords: Compressed sensing, blind calibration, phase estimation, phase retrieval, lifting

We investigate the methods that simultaneously enforce sparsity and low-rank structure in a matrix as often employed for sparse phase retrieval problems or phase calibration problems in compressive sensing. We propose a new approach for analyzing the trade off between the sparsity and low rank constraints in these approaches which not only helps to provide guidelines to adjust the weights between the aforementioned constraints, but also enables new simulation strategies for evaluating performance. We then provide simulation results for phase retrieval and phase calibration cases both to demonstrate the consistency of the proposed method with other approaches and to evaluate the change of performance with different weights for the sparsity and low rank structure constraints.

I. INTRODUCTION

Compressed sensing is a theoretical and numerical framework to sample sparse signals at lower rates than required by the Nyquist-Shannon theorem [START_REF] Donoho | Compressed Sensing[END_REF]. More precisely, a K-sparse source vector x ∈ C N is sampled by a number M of linear measurements

y i = m ′ i x, i = 1, . . . , M (1)
where m 1 , . . . , m M ∈ C N are known measurement vectors, and . ′ denotes the conjugate transpose operator. A related problem to the compressive sensing recovery is the phase retrieval problem, which occurs in imaging techniques such as optical interferometric imaging for astronomy. In this problem, one has only access to the magnitude of the measurements

z i = |y i | 2 = m ′ i xx ′ m i , i = 1, . . . , M
, where m 1 , . . . , m M are vectors of the Fourier basis. Reconstructing the original signal from such magnitude measurements is a phase retrieval problem and seems more challenging than simply recovering x from y i . Nevertheless, Candès et al. have recently showed [START_REF] Candès | Phase Retrieval via Matrix Completion[END_REF], [START_REF] Candès | PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming[END_REF] that x could be recovered exactly by solving a convex optimization problem with a number of measurements, M > N , essentially proportional to N . Instead of directly looking for a signal vector x, the method relies on finding a positive semi-definite matrix X xx ′ of rank-one such that |y i | 2 = m ′ i Xm i for all i = 1, . . . , M . When estimating XS, the measurement constraint becomes linear and Candès et al. propose to solve the following convex optimization called the Phaselift (PL) to recover X:

XPL = arg min Z Tr(Z) (2)
subject to Z 0

|y i | 2 = m ′ i Zm i , i = 1, .
. . , M The trace norm Tr(•) favors the selection of low rank matrices among all the ones satisfying the constraints. Let us acknowledge that this phase retrieval problem was also previously studied theoretically in, e.g., [START_REF] Balan | On signal reconstruction without phase[END_REF], [START_REF] Balan | Fast algorithms for signal reconstruction without phase[END_REF], but a larger number of measurements is needed for reconstruction of the original signal with the technique therein (M ∝ N 2 instead of M ∝ N ). Note also that several simple iterative algorithms such as the one described in [START_REF] Gerchberg | A practical algorithm for the determination of the phase from image and diffraction plane pictures[END_REF] have been proposed to estimate the signal x from magnitude measurements, however there is in general no guarantee that such algorithms converge.

When the measured vector x is sparse, a modification of this so-called Phaselift approach was then proposed by Ohlsson et al. [START_REF] Ohlsson | Compressive Phase Retrieval from Squared Output Measurements via Semidefinite Programming[END_REF], [START_REF] Ohlsson | CPRL-An Extension of Compressive Sensing to the Phase Retrieval Problem[END_REF]. This new approach is called Compressive Phase Retrieval via Lifting (CPRL) or Quadratic Basis Pursuit [START_REF] Ohlsson | Quadratic Basis Pursuit[END_REF] and consists in solving the problem in 2 with the addition of a cost term that penalizes non-sparse matrices. This extra term allows them to reduce the number of magnitude measurements needed to accurately recover the sparse signals. The convex optimization becomes

XCPRL = arg min Z Tr(Z) + λ Z 1 (3) subject to Z 0 |y i | 2 = m ′ i Zm i , i = 1, . . . , M
, where λ > 0. The authors also provide bounds for guaranteed recovery of this method using a generalization of the restricted isometry property. Note that conditions on the number of measurements for accurate reconstruction of sparse signals by this approach when the measurements are drawn randomly from the normal distribution are also available in [START_REF] Li | Sparse Signal Recovery from Quadratic Measurements via Convex Programming[END_REF].

Recently we have shown that the Quadratic Basis Pursuit approach can be extended to solve a whole different class of problems, namely the phase calibration in compressive sensing [START_REF] Bilen | Blind Phase Calibration in Sparse Recovery[END_REF]. The phase calibration problem is defined as signal recovery when the measurements are contaminated with unknown phase shifts as in

y i,ℓ = e jθi m ′ i x ℓ i = 1, . . . , M, θ i ∈ [0, 2π) (4)
In this case, we can define the cross measurements, g i,k,ℓ as

g i,k,ℓ y i,k y ′ i,ℓ i = 1, . . . , M (5) k, ℓ = 1, . . . , L = e jθi m ′ i x k x ′ ℓ m i e -jθi (6) = m ′ i X k,ℓ m i X k,ℓ x k x ′ ℓ ∈ C N ×N (7)
and we can also define the joint signal matrix X

∈ C LN ×LN X    x 1 . . . x L    x x ′ 1 • • • x ′ L x ′ =    X 1,1 • • • X 1,L . . . . . . . . . X L,1 • • • X L,L    (8)
which is rank-one, hermitian, positive semi-definite and sparse when the input signals, x ℓ , are sparse. Therefore the joint matrix X can be recovered with the semi-definite program

Phase-Cal:

X = arg min Z f λ (Z) (9)
subject to Z 0 g i,k,ℓ = m ′ i Z k,ℓ m i i = 1, . . . , M k, ℓ = 1, . . . , L where
f λ (Z) Tr(Z) + λ Z 1 (10)
It can be noted that when L = 1 the optimization problem in (9) becomes identical to (3) even though the originating problems are completely different. An important parameter in both (3) and ( 9) is the parameter λ which determines the weight between the sparsity and low rank structure constraints. Recently it is suggested in [START_REF] Oymak | Simultaneously Structured Models with Application to Sparse and Low-rank Matrices[END_REF] that the joint use of sparsity inducing objective function, i.e. ℓ 1 norm, along with low rank inducing objective function, i.e. the trace norm, would not necessarily improve the recovery performance and for each example one of the constraints is sufficient. However it is not known for which examples each norm is more suitable. Therefore an ambiguity related to λ is the range of values for λ that leads to the best recovery performance in different problems. For real valued systems, the bounds on M and λ for the CPRL recovery are investigated in [START_REF] Li | Sparse Signal Recovery from Quadratic Measurements via Convex Programming[END_REF] where sufficient conditions for perfect recovery is given as (assuming x 2 = 1 without loss of generality) λ > √ K x 1 + 1, λ < N 2 /4 and M > C 0 λ 2 log N where C 0 is a constant. However similar to bounds shown for compressive sensing, these bounds are also far from tight and experimental results suggest that there is a large room for improvement.

In this report we propose a new approach to numerically determine the range of values for the parameter λ in quadratic basis pursuit problems. The proposed approach is derived analytically from the quadratic basis pursuit formulation by taking advantage of the convex nature of the problem. It is shown that the proposed approach gives empirically consistent results with the quadratic basis pursuit while providing bounds on the parameter λ for best recovery performance that lead to interesting insights for the phase calibration and sparse phase retrieval problems.

Algorithm 1 P-Cal-λ: Determine if perfect recovery of x is possible and find upper and lower bounds on λ

1: Set recovery ← false, λ low ← 0, λ up ← ∞ 2: Perform optimization to find D0 given x, m 1 , . . . , m M 3: if G( D0 ) ≤ 0 then 4: return (recovery, λ low , λ up ) 5: end if 6: Perform optimization to find D-1 given x, m 1 , . . . , m M 7: if G( D-1 ) ≤ 0 then 8:
return (recovery, λ low , λ up ) 9: else 10:

λ low ← 1 G( D-1)
11: end if 12: Perform optimization to find D1 given x, m 1 , . . . , m M 13: if G( D1 ) < 0 then 14:

λ up ← -1 G( D1) 15: end if 16: if λ low < λ up then 17:
recovery ← true 18: end if 19: return (recovery, λ low , λ up )

II. AN ALGORITHM TO DETERMINE THE BOUNDS ON λ

Instead of finding theoretical bounds on λ as in [START_REF] Li | Sparse Signal Recovery from Quadratic Measurements via Convex Programming[END_REF], we propose to numerically determine the range of values for λ for which perfect recovery is guaranteed given x. An algorithm to determine if the perfect recovery is possible as well as the upper and lower bounds on the parameter λ for given x and [m 1 , . . . , m M ] is shown in Algorithm 1 (P-Cal-λ). The term Dp in Algorithm 1 represents the result of the optimization

Dp arg min Z G(Z) (11) subject to m ′ i Z k,ℓ m i = 0, i = 1, . . . , M Tr(Z) = p, k, ℓ = 1, . . . , L Z = E a b ′ b C E ′ , a ∈ R, b ∈ C LN -1 C 0, C ∈ C LN -1×LN -1
where E is defined with the eigen-decomposition of X xx ′ such that X = EΛE ′ . The function G(.) is defined as

G(Z) Z Ω ⊥ X 1 + Real{ sign(X), Z ΩX } (12)
where the function sign(.) operating on every element of the matrix is

sign(Z) Zi,j |Zi,j | if Z i,j = 0 0 if Z i,j = 0 (13)
In order to clarify how the Algorithm 1 is derived, let us first define the matrix subspaces Ω X and Ω ⊥ X as

Ω X = {Z ∈ C LN ×LN |Z i,j = 0 if X i,j = 0} Ω ⊥ X = {Z ∈ C LN ×LN |Z i,j = 0 if X i,j = 0} and let Z ΩX and Z Ω ⊥
X indicate the projections of matrix Z onto Ω X and Ω ⊥ X respectively.

Theorem 1:

For a given x = [x ′ 1 . . . x ′ L ] ′ ∈ C LN , X xx ′ having the eigen-decomposition X = EΛE ′ ,
the result X of the optimization Phase-Cal is equal to X if and only if all of the following conditions are satisfied:

C1: if G 1 < 0, then λ < - 1 G 1 (14) C2: G -1 > 0 (15) C3: λ > 1 G -1 (16) C4: G 0 > 0 ( 17
)
where G p = G(D p ) and D p is defined as

D p arg min Z G(Z) (18) subject to m ′ i Z k,ℓ m i = 0, i = 1, . . . , M Tr(Z) = p, k, ℓ = 1, . . . , L Z = E a b ′ b C E ′ , a ∈ R, b ∈ R(C) C 0, C ∈ C LN -1×LN -1
given that R(C) represents the range of matrix C and

Z k,ℓ    Z (k-1)N +1,(ℓ-1)N +1 • • • Z (k-1)N +1,ℓN . . . . . . . . . Z kN,(ℓ-1)N +1 • • • Z kN,ℓN    (19)
In order to prove Theorem 1 we shall first establish a few observations. Let us define the cone S X such that

S X = {A|X + cA 0, ∃c > 0} (20) Lemma 1: For a given x = [x ′ 1 . . . x ′ L ] ′ ∈ C LN , X = xx ′ having the eigen-decomposition X = EΛE ′ , the matrix ∆ E a b ′ b C E ′ where b ∈ C LN -1 , C ∈ C LN -1×LN -1 is in S X if and only if C 0, a ∈ R and b ∈ R(C)
where R(.) represents the range of the matrix.

Proof of Lemma 1: Let us assume that ∆ ∈ S X , then by definition

∃c 0 ∈ R + , such that ∀u ∈ C, ∀v ∈ C LN -1 , ∀c ∈ (0, c 0 ], [u ′ v ′ ] X + cE a b ′ b C E ′ u v ≥ 0 (21) ⇒ [u ′ v ′ ] ∆ + c a b ′ b C u v ≥ 0 (22) ⇒ [u ′ v ′ ] x 2 2 + ca cb ′ cb cC u v ≥ 0 (23) ⇒|u| 2 ( x 2 2 + ca) + cu ′ b ′ v + cuv ′ b + cv ′ Cv ≥ 0 (24)
The first necessary condition for (24) is that

x 2 2 + ca ≥ 0 ∀c ∈ (0, c 0 ] ⇒ a ≥ -x 2 2 c 0 , a ∈ R (25)
Following (24), we have

( x 2 2 + ca) u + cb ′ v x 2 2 + ca 2 2 - cb ′ v x 2 2 + ca 2 2 + cv ′ Cv ≥ 0 (26) ⇒ v ′ Cv - cv ′ bb ′ v x 2 2 + ca ≥ 0, ∀v, ∀c ∈ (0, c 0 ] (27) ⇒ C - cbb ′ x 2 2 + ca 0, ∀c ∈ (0, c 0 ] (28)
The second and third necessary conditions implied by (28) are

C 0 (29) b ′ v = 0 ∀v satisfying Cv = 0 ⇒ b ∈ R(C) (30)
More strict conditions can be derived assuming C has the eigen-decomposition

C = FΛ C Λ ′ C F ′ , Λ C = Diag( λ C,1 , . . . , λ C,LN -1
) and without loss of generality representing b as

b =FΛ C s, s ∈ C LN -1 (31) =FΛ C s ΩC , Ω C {a|a i = 0 if λ C,i = 0} (32) ⇒ C- cbb ′ x 2 2 + ca = FΛ C Λ ′ C F ′ - cFΛ C s ΩC s ′ ΩC Λ ′ C F ′ x 2 2 + ca 0 (33) ⇒ v′ v - c x 2 2 + ca |v ′ s ΩC | 2 ≥ 0, ∀v ∈ C LN -1 (34) v Λ ′ C F ′ v ⇒ 1 - c x 2 2 + ca v′ s ΩC |v| 2 ≥ 0, ∀v ∈ C LN -1 (35) ⇒ 1 - c x 2 2 + ca s ΩC 2 2 ≥ 0 (36) ⇒ s ΩC 2 2 ≤ a + x 2 2 c ∀c ∈ (0, c 0 ] (37)
Given c 0 , the three necessary conditions are a ∈ R, C 0 and b ∈ R(C) as shown in (25), (29) and (30). It can also be shown that given ∆, a constant, c 0 , can be chosen to ensure ∆ ∈ S X considering the conditions in (25) and (37) provided that a ∈ R, C 0 and b ∈ R(C).

Lemma 2: The matrix X is not the global (or local) minimum of the optimization Phase-Cal if and only if ∃∆ ∈ C LN ×LN satisfying all three of the following conditions:

C1: m ′ i ∆ k,ℓ m i = 0, i = 1, . . . , M, k, ℓ = 1, . . . , L (38) C2: ∆ ∈ S X (39) C3: Tr(∆) + λ G(∆) ≤ 0 ( 40
)
where ∆ k,ℓ is defined similar to (19). Corollary 1: The matrix X is the global minimum of the optimization Phase-Cal if and only if

Tr(∆) + λ G(∆) > 0, ∀∆ satisfying C1 and C2 ( 41
)
Proof of Lemma 2: If X is not the global minimum of the optimization Phase-Cal, then by definition ∃W 0, W = X such that

f λ (W) ≤ f λ (X) (42) g i,k,ℓ = m ′ i W k,ℓ m i , i = 1, . . . , M, k, ℓ = 1, . . . , L (43)
Using (42) and convexity of the function

f λ f λ (W) ≤ f λ (X + c∆) ≤ f λ (X), 0 < c ≤ 1 (44) ∆ W -X
Considering that X satisfies the measurements (g i,k,ℓ = m ′ i X k,ℓ m i , i = 1, . . . , M, k, ℓ = 1, . . . , L), (43) easily leads us to C1 such that

m ′ i (W -X) k,ℓ m i = 0, i = 1, . . . , M, k, ℓ = 1, . . . , L (45) ⇒m ′ i ∆ k,ℓ m i = 0, 0 < c ≤ 1 (46)
Note that (44), (46) and the fact that X + c∆ 0, 0 < c ≤ 1 due to convexity of the space of positive semi-definite matrices easily implies X not being a local minimum when a global minimum W exists as expected by the convexity of the optimization Phase-Cal. ∆ ∈ S X (C2) is also implied by definition given that X + c∆ 0, 0 < c ≤ 1.

Continuing from (44)

f λ (X + c∆) ≤ f λ (X) (47)
⇒ lim c→0 + f λ (X + c∆) -f λ (X) c ≤ 0, 0 < c ≤ 1 (48) ⇒ lim c→0 + 1 c Tr(X + c∆) + λ X + c∆ 1 -Tr(X) -λ X 1 ≤ 0 (49) ⇒ lim c→0 + 1 c c Tr(∆) + λ sign(X + c∆), X + c∆ -λ X 1 ≤ 0 (50)
Note that sign(X + c∆), X + c∆ = i,j sign(X i,j + c∆ i,j )(X i,j + c∆ i,j ) (51)

and for small enough c, each term of (51) can be reduced to

sign(X i,j + c∆ i,j )[X i,j + c∆ i,j ] =        c ∆ i,j Imag sign( ∆i,j Xi,j ) φ(X i,j , c∆ i,j ) +|X i,j | + c|∆ i,j | Real sign( ∆i,j Xi,j ) X i,j = 0 c|∆ i,j | X i,j = 0 (52)
where φ(X i,j , c∆ i,j )

Imag sign

Xi,j +c∆i,j Xi,j

Real sign

Xi,j +c∆i,j Xi,j

Considering

lim c→0 + φ(X i,j , c∆ i,j ) = 0 (54)
and

|∆ i,j | Real sign ∆ i,j X i,j = Real ∆ i,j sign(X ′ i,j ) (55)
the term in (50) then reduces to

lim c→0 + 1 c c Tr(∆) + λ sign(X + c∆), X + c∆ -λ X 1 ≤ 0 (56) ⇒ lim c→0 + 1 c c Tr(∆) + λ X 1 + c ∆ Ω ⊥ X 1 + c Real { sign(X), ∆ ΩX } -λ X 1 ≤ 0 (57) ⇒ lim c→0 + 1 c c Tr(∆) + cλ ∆ Ω ⊥ X 1 + cλ Real { sign(X), ∆ ΩX } ≤ 0 (58) ⇒ Tr(∆) + λ ∆ Ω ⊥ X 1 + λ Real { sign(X), ∆ ΩX } = Tr(∆) + λ G(∆) ≤ 0 (59)
which is exactly C3. Hence existence of a global minimum W = X implies C1, C2 and C3. Similarly, it can also easily be shown that conditions C1, C2 and C3 are sufficient for X not being the minimum of the convex optimization Phase-Cal.

Proof of Theorem 1: Following the Corollary 1, in order to have X as a unique solution to optimization Phase-Cal, we must have

Tr(∆) + λ G(∆) > 0 (60) ∀∆ satisfying m ′ i ∆ k,ℓ m i = 0, i = 1, . . . , M ∆ ∈ S X , k, ℓ = 1, . . . , L
or equivalently

Tr(∆) + λ G(∆) > 0 (61) ∀∆ satisfying m ′ i ∆ k,ℓ m i = 0, i = 1, . . . , M, k, ℓ = 1, . . . , L ∆ = E a b ′ b C E ′ , a ∈ R, b ∈ R(C) C 0, C ∈ C LN -1×LN -1
as suggested by Lemma 1. Since given a ∆ satisfying (61) c∆, c > 0 also satisfies (61), Tr(∆) can be fixed without loss of generality. Therefore (61) can be considered in three cases:

• Case 1: Tr(∆) = 1 (61) can be satisfied for all Tr(∆) > 0 provided that

Tr(∆) + λ G(∆) > 0 (62) ∀∆ s.t. m ′ i ∆ k,ℓ m i = 0, i = 1, . . . , M, k, ℓ = 1, . . . , L Tr(∆) = 1 ∆ = E a b ′ b C E ′ , a ∈ R, b ∈ R(C) C 0, C ∈ C LN -1×LN -1 which is satisfied if λ G(D 1 ) > -1. Therefore if G(D 1 ) < 0, we must have λ < -1 G(D1)
, and if G(D 1 ) ≥ 0 no limitation on λ is needed (C1).

• Case 2: Tr(∆) = -1 Similar to Case 1, (61) can be satisfied for all

Tr(∆) < 0 provided that λ G(D -1 ) > 1. Consequently, λ G(D -1 ) > 1 only if G(D -1 ) > 0 (C2) and λ > 1 G(D-1) (C3). • Case 3: Tr(∆) = 0
As in Case 1 and 2, (61) can be satisfied for all Tr(∆) = 0 provided that λ G(D 0 ) > 0. As a result, λ G(D 0 ) > 0 only if G(D 0 ) > 0 (C4). Combining all three cases, (61) can be satisfied given that C1, C2, C3 and C4 are satisfied. Similarly it can be shown that the conditions C1, C2, C3 and C4 are sufficient for (61) to be true which concludes the proof of the Theorem 1.

Remark 1: Defining the sets S D and S D as

S D = A|A = E a b ′ b C E ′ , a ∈ R, b ∈ R(C), C 0 C ∈ C LN -1×LN -1 (63)
S D = A|A = E a b ′ b C E ′ , a ∈ R, b ∈ C LN -1 , C 0 C ∈ C LN -1×LN -1 (64)
we can observe that D p ∈ S D , Dp ∈ S D and S D ⊂ S D. As a result, we can conclude that 1)

G( Dp ) = G(D p ) if Dp ∈ S D 2) If Dp / ∈ S D , then G( Dp ) ≤ G(D p
) and the bounds on λ computed through Theorem 1 with Dp can only be tighter than or equal to that of the bounds obtained with D(p). The optimization problem defined in (18) for a given set of m i , the transform E and the constant p ∈ R is difficult to handle due to the non-linear nature of the constraints specifically introduced by the requirement ∈ R(C). In order to simplify the optimization, one can omit this criteria and instead solve [START_REF] Bilen | Blind Phase Calibration in Sparse Recovery[END_REF]. Since the resulting bounds will be tighter as explained above, the results are guaranteed to be valid for determining viable range of λ for perfect reconstruction.

Following the Theorem 1 and Remark 1, it is straightforward to show that for a given set of sparse input signals and the measurement matrix, Algorithm 1 (P-Cal-λ) can be used to determine whether perfect recovery is possible as well as the upper and lower bounds on the parameter λ.

III. EXPERIMENTAL RESULTS

In order to demonstrate the performance of the proposed algorithm P-Cal-λ, the upper and lower bounds on the parameter λ in the optimization method Phase-Cal have been estimated for different numbers of input signals, L ∈ {1, 3, 6}, each with size N = 100. The measurement vectors and the non-zero entries of the input signals are randomly generated from an i.i.d. normal distribution. The positions of the K nonzero coefficients of the input signals, x ℓ , are chosen uniformly at random in {1, . . . , N }. The number of non-zero entries, K, of each input signal, x ℓ , and the number of measurements, M , are varied such that the performance under different sparsity levels, ρ K/M ∈ {0.05, 0.1, 0.15, 0.2, 0.25}, are observed for one under-complete and one over-complete set of measurements such that δ M/N ∈ {0.6, 1.2}. In order to observe the bounds on λ for perfect recovery, the optimization in [START_REF] Bilen | Blind Phase Calibration in Sparse Recovery[END_REF] is performed for p = 1, -1, 0 and the bounds on λ are computed as described in Algorithm 1 (P-Cal-λ) using 10 independently generated input signals, x. Lowest upper bound and highest lower bound are selected among these 10 experiments as the viable range for λ for a given ρ and δ.

The maximum lower bound for λ among these 10 experiments as a function of ρ are shown in Figures 1a-1b for δ = 0.6 and δ = 1.2 respectively. It can be observed from Figures 1a and1b that the benefit of increasing the number of input signals mainly appears when M > N as the recovery is possible for a broader range of λ and ρ. For the significant majority of the simulations, λ is found to have no upper bound (G 1 > 0), and therefore the upper bounds are not shown. For most of the simulations that resulted in a feasible range of λ for perfect recovery, the optimization result, Dp , is observed to be in S D , which affirms that the bounds found on λ for each simulation are tight.

The probabilities of recovering the signals, empirically estimated by the percentage of successful recovery during these simulations, are displayed in Figures 1c-1d. These probabilities are often displayed in phase transition diagrams in compressive sensing recovery scenarios when evaluating different algorithms, as in [START_REF] Bilen | Blind Phase Calibration in Sparse Recovery[END_REF], [START_REF] Bilen | Convex Optimization Approaches for Blind Sensor Calibration using Sparsity[END_REF] for the optimization Phase-Cal. In order to demonstrate that the proposed approach accurately estimates the performance, the probabilities of recovery of Phase-Cal as reported in [START_REF] Bilen | Convex Optimization Approaches for Blind Sensor Calibration using Sparsity[END_REF] (which are consistent with the results in [START_REF] Bilen | Blind Phase Calibration in Sparse Recovery[END_REF]) are also shown in Figures 1c-1d. It can be observed that the reported probabilities of both methods closely match for every simulation scenario.

IV. CONCLUSIONS

We have proposed a novel approach for evaluation of convex minimization methods used in phase retrieval and phase calibration problems. The proposed method, P-Cal-λ, not only provides an alternative approach to evaluating the performance of the discussed optimization methods (CPRL and Phase-Cal), but also helps finding tight bounds on the optimization parameter for perfect recovery 1 .

For the evaluation of performance of an optimization method such as Phase-Cal or CPRL, using the approach P-Cal-λ has several advantages compared to monte carlo simulations performed directly by evaluating the optimization method itself. Firstly, the P-Cal-λ algorithm determines not only the possibility of successful recovery with the optimization, but also the bounds on the parameter λ for ensuring the perfect recovery when possible. Secondly, it provides a better way to deal with the convergence issues in practical simulations. When the optimization method Phase-Cal (or CPRL) is directly performed in simulations, perfectly accurate result may not be reached within a limited time due to slow convergence, even though perfect reconstruction would have been possible with a relaxed time constraint. However when P-Cal-λ is used to evaluate the performance, early termination of the optimization most often affects the accuracy of the bounds on λ but not the accuracy of determining whether perfect recovery is possible or not. Lastly, even though the order of computational complexity of the optimization approaches in ( 9) and ( 11) are comparable, the algorithm P-Cal-λ can be performed quickly for many cases for which the recovery is not possible. This is due to the fact that finding a point that results in a negative objective function (rather than the point minimizing it) is sufficient for determining the unsuccessful recovery (for the optimization in lines 3 and 7 of P-Cal-λ).

The experimental results on the bounds of the parameter λ shows that this parameter can be chosen to be very large to maximize the chances of perfect recovery. Furthermore, the fact that there is no upper bound on λ for almost all the simulated scenarios suggests that the same recovery performance can be reached without minimizing the trace in Phase-Cal (and CPRL) and minimization of ℓ 1 -norm is sufficient. This suggestion is consistent with the analysis provided in [START_REF] Oymak | Simultaneously Structured Models with Application to Sparse and Low-rank Matrices[END_REF], which states that for the recovery of a given signal, only one of the components (trace and the ℓ 1 -norm) of the objective function in Phase-Cal (and CPRL) is needed. The results with our approach simply shows that this component is almost always the ℓ 1 -norm. The performance of ℓ 1 -norm only optimization is reported in [START_REF] Bilen | Convex Optimization Approaches for Blind Sensor Calibration using Sparsity[END_REF] which further verifies this conclusion. Furthermore our experiments also showed that minimizing the ℓ 1 -norm leads to a faster convergence (in terms of the number of iterations) than minimizing the objective function with both the trace and the ℓ 1 -norm.

  Lower bound for λ, δ = 1.2 Probability of recovery, δ = 1.2

Fig. 1 :

 1 Fig. 1: (P-Cal-λ) The lower bound on λ, (a)-(b), and the estimated probability of perfect recovery, (c)-(d), for N = 100 with respect to ρ K/M and L. The solid lines indicate the results obtained through P-Cal-λ whereas dashed lines in (c)-(d) indicate the empirical probability of recovery presented in [13] obtained by Phase-Cal.

The codes for the MATLAB R implementations of the proposed method has been provided in http://hal.inria.fr/docs/00/96/02/72/TEX/Calcodesv2.0.rar

This work was partly funded by the Agence Nationale de la Recherche (ANR), project ECHANGE (ANR-08-EMER-006) and by the European Research Council, PLEASE project (ERC-StG-2011-277906). LD is on a joint affiliation between Univ. Paris Diderot and Institut Universitaire de France.