J Marocco

E Hache

F Lamareille

Spectral classification of emission-line galaxies from the Sloan Digital Sky Survey II. A supplementary diagnostic for AGNs using the D n (4000) index

Keywords: Galaxies: active, Galaxies: high-redshift, Galaxies: Seyfert, Galaxies: fundamental parameters

Aims. In this paper we present a classification of emission-line galaxies at intermediate and high redshifts (0.5 z 1.0 for optical spectra, z 2.5 for near-infrared spectra), using the D n (4000) index as a supplementary diagnostic. Our goal is to complement the diagnostic based only on emission-line ratios from the blue part of the spectra, which suffer from some limitations for the classification of Seyfert 2 and composite galaxies. Methods. We used a sample of 89 379 galaxies with a good signal-to-noise ratio from the Sloan Digital Sky Survey (data release 7). Using the classification scheme presented in Paper I, we classified these galaxies with a diagnostic diagram involving the [OIII]λ 5007/Hβ and [OII]λ λ 3726 + 3729/Hβ emission-line ratios. Then we derived a supplementary diagnostic involving D n (4000) to improve this classification, in the regions where objects of different types are mixed. To show the validity of our spectral classification we established success-rate and contamination charts, then we compared our results to those obtained with the reference classification that was scheme obtained also using Hα, [NII]λ 6584, and [SII]λ λ 6717+6731 emission lines. Results. We show that our supplementary classification based on the D n (4000) index allows to separate unambiguously star-forming galaxies from Seyfert 2 in the region where they were mixed in Paper I. It also significantly reduces the region where star-forming galaxies are mixed with composites.

Introduction

There are several existing types of emission-line galaxies: the two main classes are star-forming galaxies (hereafter SFG) and active galactic nuclei (hereafter AGN). Emission lines are observed in star-forming galaxies because gas is ionized by new hot stars. In contrast, AGN galaxies contain a supermassive blackhole, and their emission lines come from gas ionization by the light emitted from their accretion disk. AGN can be classified in several types, but we only consider narrow-line AGNs, which can be confused with SFG, i.e. Seyfert 2 galaxies and LINERs (low-ionization nuclear emission-line region). We do not consider Seyfert 1 galaxies because they can be easily distinguished from SFGs by their wide Balmer emission lines. A third class of emission-line galaxies is what we call "composites". Composites show emission lines which are due both to recent star formation and to an AGN.

To classify emission-line galaxies, one may use two diagnostic diagrams depending on the redshift range: the first one is known as the BPT diagnostic (Baldwin et al. 1981), later studied by Kewley et al. (2001) who used it to separate AGN from SFG thanks to theoretical models. Kauffmann et al. (2003a) revised Kewley's work and allowed going deeper into the classification process by showing a third type of galaxies called composites. It was then again revised by Kewley et al. (2006), who improved the classification of AGNs into Seyfert 2 and LINERs. This diagnostic uses log([OIII]λ 5007/Hβ ) vs. log ([NII]λ 6583/Hα) and log([OIII]λ 5007/Hβ ) vs. log ([SII]λ λ 6717 + 6731/Hα) diagrams and may be used up to z 0.5 with optical spectrographs. Other diagnostics have been used in the past in the same diagrams (Heckman 1980;Veilleux & Osterbrock 1987;Ho et al. 1997). We use Kewley et al. (2006) as a reference since it is the latest widely used diagnostic and is based on the biggest sample. We refer the reader to Kewley et al. (2006), Constantin & Vogeley (2006), and references herein for comparisons of these diagnostics. See also Groves et al. (2006) for a specific discussion on low-metallicity AGNs.

The second diagnostic was originally proposed by Tresse et al. (1996) and studied later by Rola et al. (1997). This diagnostic is useful at intermediate and high redshift when some emission lines used in the BPT diagnostic are no longer observed by getting red-shifted out of spectrographs. Lamareille et al. (2004, hereafter L04) established a classification using empirical demarcation lines in the diagnostic diagram showing log ([OIII]λ 5007/Hβ ) vs. log ([OII]λ λ 3726 + 3729/Hβ ), which may be used up to z 1.0 with optical spectrographs, or even at z 2.5 with near-infrared spectrographs(where optical diagnostics cannot be used). In Paper I (Lamareille 2010), one of us proposed revised equations for the classification that we use in this paper. We know that the Lamareille (2010, hereafter L10) diagnostic implies a loss of Seyfert 2 galaxies, because of the region where Seyfert 2 and SFGs get mixed. As discussed in Paper I, the L10 diagnostic also cannot unambiguously separate composites from SFGs or LINERs. The goal of this paper is to try to solve these two limitations with a different approach. Following the idea under the "DEW" diagnostic introduced by Stasińska et al. (2006), we use the D n (4000) index to derive a supplementary diagnostic. Yan et al. (2011) have already derived a similar new diagnostic based on U -B restframe colors. Compared to the present paper, it does suffer from the following limitations. It is based on rest-frame colors whose calculation may suffer from biases from imperfect k-correction at high redshift (unless such colors are integrated directly from the spectra), it does not provide a distinction between Seyfert 2 galaxies and LINERs, and it does not provide a way to isolate at least a fraction of composite galaxies. Conversely, that diagnostic has the advantage of only relying on the detection of [OIII]λ 5007 and Hβ emission lines.

Our goal is to provide a diagnostic that can be used to classify intermediate-or high-redshift emission-line galaxies as closely as possible to local universe studies. The older L04 diagnostic has already been used in various studies, such as star formation rates (Maier et al. 2009), metallicities (Mouhcine et al. 2006;Lamareille et al. 2006a), AGN populations (Bongiorno et al. 2010), gamma ray burst hosts (Savaglio et al. 2009), and clusters (Loubser et al. 2009). Results provided in Paper I and here may be used to revise spectral classification of emissionline galaxies in intermediate redshift optical galaxy redshift surveys such as VVDS (Le Fèvre et al. 2005;Garilli et al. 2008), zCOSMOS (Lilly et al. 2009), DEEP2 (Davis et al. 2003), GDDS (Abraham et al. 2004), GOODS (Balestra et al. 2010), and others. We hope it will also serve as a reference for ongoing or future high-redshift surveys involving future spectrographs: in the optical, MUSE on VLT (Bacon et al. 2010) or DIORAMAS on EELT (Le Fèvre et al. 2010); or in near-infrared (at z 2.5), EMIR on GTC (Garzón et al. 2006;Contini et al. 2005), KMOS on VLT (Sharples et al. 2006), MOSFIRE on Keck (McLean et al. 2008).

It is worth mentioning here as a warning that Stasińska et al. (2008) demonstrate that a fraction -whose value is still uncertain -of the galaxies classified as LINERs or composites by emission-line diagnostics may be actually "retired" galaxies. Ionization in such galaxies would be produced by post-AGB stars and white dwarfs. The reader should therefore be aware that galaxies that we refer to as LINERs or composites might not contain an AGN. Cid Fernandes et al. (2011) have derived a diagnostic that isolates this class of "retired" galaxies. This diagnostic is based on Hα and [NII]λ 6583 emission lines. It is, however, beyond the scope of this paper to derive a similar diagnostic that can be used on higher redshift spectra, but it may be the goal of a future work.

This paper is organized as follows. We first present the data and how we selected them (Sect. 2), then we summarize of existing classification schemes (Sect. 3). In Sect. 4, we discuss the limits of the L10 and DEW diagnostics. Finally we present our supplementary diagnostic in Sect. 5.

Data selection

We used a sample of 868 492 galaxies from the SDSS (Data Release 7, Abazajian et al. 2009, available at: http:// www.mpa-garching.mpg.de/SDSS/DR7/) with redshifts between 0.01 and 0.3. Actually the sample originally contained measurements for 927 552 different galaxies, but there are 109 219 duplicate spectra (twice or more), so we averaged these duplicated measurements in order to increase the signal-to-noise ratio, and filtered out those that do not increase the averaged signal-to-noise ratio. Among others, these data contain measurements of the equivalent widths of the following emission lines: [OIII]λ 5007, [OII]λ λ 3726+3729, [NII]λ 6583, [SII]λ λ 6717+6731, Hβ , Hα, and [NeIII]λ 3969. Balmer emission-line measurements were automatically corrected for any underlying absorption. The spectral coverage of SDSS is 3800-9200 Å, and the mean resolution of the spectra 1800 λ /△λ 2200. We also retrieved the value of the D n (4000) index (Balogh et al. 1999), which were measured on emission-line subtracted spectra.

We filtered our data for a specific signal-to-noise ratio (in equivalent width) greater than five in order to keep the same selection as in Paper I, also eliminating data with positive equivalent width, which would involve absorption lines. We did not apply this selection to the [NeIII]λ 3969, which is only used as an optional measurement in the DEW diagnostic. This finally leads to 89 379 galaxies. All classifications and plots presented in this paper were processed by the "JClassif" software, part of the "Galaxie" pipeline available at: http://www.ast.obs-mip. fr/galaxie/.

Throughout this paper, as in Paper I, all emission line ratios are equivalent width ratios rather than flux ratios. This is done to eliminate any dependence that may exist (mainly for the [OII]/Hβ emission line ratio) between the derived diagnostic and the dust properties of the sample. Indeed, equivalent width ratios are sensitive not to dust attenuation, but only to the ratio between continuum fluxes below each lines. Considering [OII] and Hβ , this parameter should not evolve strongly between galaxies with similar properties in the diagnostic diagrams, even if they are at different redshifts, keeping the consistency of the diagnostics (see also Lamareille et al. 2006b;Pérez-Montero et al. 2009).

Existing classification schemes

K06 diagnostic

As in Paper I, we use the a simplified version of the diagnostic from Kewley et al. (2006, hereafter K06)

L10 diagnostic

The L10 diagnostic has been defined in Paper I. We summarize here the main equations, but we refer the reader to Paper I for details. The first equation separates SFGs from AGNs: Seyferts 2 are above this line. Then, we define a region where some Seyfert 2 (26% of them) are mixed with a majority of SFGs (21.5% contamination by Seyfert 2). This region, called "SFG/Sy2", is located below Eq. 4 and above the line

log ([OIII]/Hβ ) = 0.30. ( 6
)
Finally, we define the region where most of the composites fall (64% of them), even if this region is dominated by SFGs (79%) and also contains some LINERs (2%). This region, called "SFG-LIN/comp", can be located by the two following inequalities:

log ([OIII]/Hβ ) ≤ -(x -1) 2 -0.1x + 0.25, (7) log ([OIII]/Hβ ) ≥ (x -0.2) 2 -0.60, (8)
with x = log ([OII]/Hβ ). Unlike in Paper I, we now divide the "SFG-LIN/comp" region for clarity into "SFG/comp" and "LIN/comp" regions, and the separation between SFG and LINERs is done according to Eq. 4.

DEW diagnostic

The DEW diagnostic has been proposed by Stasińska et al. (2006) and involves the DEW diagnostic diagram, showing the D n (4000) index vs. the maximum (in absolute value) of the equivalent widths of [OII] and [NeIII] emission lines. We separate AGNs from SFGs using

D n (4000) = -0.15x ′ + 1.7, (9)
with x ′ = log (max (EW[OII], EW[NeIII])) + 1, where AGNs are above this line. This diagnostic is based the D n (4000) index being an indicator of the mean age of the stellar populations. Thus, it is indeed useful to separate galaxies that are dominated by older stars (AGNs) from galaxies dominated by younger stars (SFGs). The DEW diagnostic also considers that the [NeIII] emission line may be stronger than the [OII] emission line in AGNs. Thus, it should be used as a good additional tracer for AGNs in low signal-to-noise ratio surveys.

Summary

Figure 1 shows how the different types of galaxies (according to K06) appear in the high-redshift diagrams (top panels) and how the high redshift classifications appear back in one of the K06 diagnostic diagrams (bottom panels). In all panels, SFG are plotted in blue, Seyfert 2 in green (except in the bottom-right panel where green points stand for all types of AGNs), LINERs in cyan, and composites in magenta. The L10 diagnostic (left panels) implies several regions where different types of galaxies get mixed. Seyfert 2 region and LINERs region are now quite well defined, but we see composites falling in the SFGs and LINERs regions. Most of the composites fall in the region of the L10 diagnostic called SF-LIN/comp(marked by the dashed contour corresponding to Eqs. 7 and 8). SFGs and Seyfert 2 are now separated quite well, but still there is a small region of the L10 diagnostic, called SF/Sy2, where they get mixed. In the bottomleft panel, it seems that most of the SF/Sy2 galaxies belong to the K06 SFG region, and that a large number of SFG/comp galaxies belong to K06 SFG region. LIN/comp galaxies seem to appear half/half in the K06 composites and LINERs regions.

We now the compare K06 and DEW classifications (right panels). We see that all K06 LINERs are correctly classified as AGNs in the DEW diagnostic. Most of K06 Seyfert 2 galaxies lie in the DEW AGN region as well, so that is quite satisfying. However composites are shared in DEW SFG and AGN regions, which confirms that composites are sort of hybrids between AGNs and SFGs, also in terms of stellar populations. Thus they obviously cannot be isolated in the DEW diagnostic. We emphasize that the definition of SFG and AGN galaxies used in Stasińska et al. (2006) is slightly different from the K06 scheme: it is based on the long-dashed curve shown in the bottom-right panel of Fig. 1 (Eq. 11 of their paper). The DEW diagnostic is designed to exclude only pure SFGs without any AGN contribution, while according to Stasińska et al. (2006) galaxies classified as SFG by K06 (and by us) would allow up to 3% AGN contribution. Composites would allow up to 20% AGN contribution.

Indeed in the bottom-right panel, a non-negligible number of DEW AGNs actually belong to the K06 SFG or composite regions.However, we also note conversely that a non-negligible number of DEW SFGs contaminate the K06 composite and AGN regions. The DEW diagnostic actually fails to completely exclude all pure SFGs.

Limits of the L10 and DEW classifications

Success and contamination charts

The success chart consists in classifying galaxies from our sample according to the reference, then associating a probability for each type of galaxy (AGN, composite, or SFG) to be classified correctly in the new diagnostic. The contamination chart is based on the same principle as the success chart, except this time we classify galaxies according to the new diagnostic, and then we calculate the probability that the galaxies classified as one type are actually of that same type according to the reference. shows the success chart of the L10 diagnostic. It reveals a relatively satisfying spread of composite galaxies and AGNs inside the different types defined. Table 2 shows the associated contamination chart. We notice quite good efficiency, i.e. low contam-ination by other types, in the L10 SFG, Seyfert 2, and LINER regions.

If we take a look at AGNs, we notice that almost 60% of K06 Seyfert 2 galaxies are successfully classified as L10 Seyfert 2. Moreover 26% belong to the L10 SFG/Sy2 region, which would give us a total of more than 85% of K06 Seyfert 2 galaxies being classified as Seyfert2 with the L10 diagnostic. However, the contamination chart shows that the L10 SFG/Sy2 region is actually made up of only 21% K06 Seyfert 2, which means it cannot be used to reliably look for additional Seyfert 2 galaxies in highredshift samples. The Seyfert 2 region itself shows a very low contamination (13%) by other types.

Most K06 LINERs (74%) are also successfully classified as L10 LINERs, and 17% belong to the L10 LIN/comp region. That gives a global success rate of 91% for LINERs. As already stated in Paper I, these results are much better than results produced by the former L04 diagnostic; however, the contamination by composites in the LIN/comp region is not negligible. Only 40% of the L10 LIN/comp objects actually are K06 LINERs, and 57% are K06 composites. That gives a global 37% contamination in the union of the L10 LINERs and LIN/comp regions. Finally we confirm the conclusion of Paper I from these two tables, which is that the L10 diagnostic is very efficient for SFGs. If we consider the union of the L10 SFG, SFG/Sy2, and SFG/comp regions, the success rate is 99.7% and the contamination by other types only 16%. This low contamination by composite galaxies and AGNs, in particular in the SFG/Sy2 and SFG/comp regions, has been shown to not critically bias SFG studies such as metallicity. Lamareille et al. (2009), for instance, performed such tests using the L04 diagnostic, i.e. with an even more contamination by AGNs in the SFG region.

Tables 3 and4 show the success and contamination charts of the DEW diagnostic. Again, the results are very good for SFGs with a 95% success rate, and only an 8% contamination, less than for L10. Still, this better contamination chart for SFGs does not drastically reflect a worse success rate for AGNs. The success rate is indeed 80% for Seyfert 2 and 98% for LINERs. The DEW has in fact greater ability to separate SFGs from AGNs than standard diagnostic diagrams as in K06 or L10 classifications. However, the main limitations of the DEW diagnostic clearly appear from the contamination chart regarding DEW AGNs. The DEW AGN region is actually made up of only 37% K06 AGNs. There is indeed a high contamination by 18% K06 SFGs, much higher than with the L10 diagnostic (less than 3% in the Seyfert 2 and LINERs regions). Moreover, the DEW AGN region is contaminated by 45% K06 composites, to be compared to 30% for the L10 LINERs, and only 1% for the L10 Seyfert 2. As one can see in Fig. 1, composites get completely confused with Seyfert 2 and LINERs in the DEW diagnostic, while they are rather confused with SFGs in the L10 diagnostic. We do note that this contamination is explained mainly by the fact that Stasińska et al. (2006) use a different definition of SFGs and AGN galaxies (as discussed in Sect. 3.4 above). Indeed, in DEW diagnostic's philosophy, it should not be considered as a "contamination" but as a "contribution" of an AGN to star-forming galaxies. Finally, the DEW diagnostic does not allow any distinction between Seyfert 2 and LINERs.

Regarding the classification of SFGs, we conclude that one should use the L10 diagnostic for its very high success rate and DEW diagnostic for its lower contamination. About AGNs, both advantages of the L10 and DEW diagnostic diagrams may be put together to provide a better diagnostic, which is the goal of the present paper. We emphasize that we did not use the DEW diagnostic itself for our own classification. We only used the DEW diagram to derive a new diagnostic where it is needed (see Sect. 4.2 below).

AGN counts

In order to explore the limitations of L10 and DEW classifications of AGNs better, we now count the number of AGNs (Seyfert 2 and LINERs) as a function of the ionization state, roughly given by the log ([OIII]/Hβ ) emission-line ratio. To achieve this test, we divide the K06 or L10 diagnostic diagrams in equal horizontal slices, and then in each slice we count the number of AGNs. Figure 2 shows the absolute and difference counts (relative to K06) obtained with, from left to right, the following classifications: L04, DEW, L10, and the present paper's diagnostic (see Sect. 5 below). In each panel, the results are compared to the actual count of AGNs according to the reference K06 diagnostic.

We confirm, as stated in Paper I, that the L04 diagnostic tends to underestimate the amount of AGNs, even when including L04 candidate AGNs, and that a very high number of AGNs (mainly LINERs) are lost in this diagnostic. However, we can put this effect into context thanks to Fig. 2, as we see that it only becomes significant for log ([OIII]/Hβ ) 0.9, or log ([OIII]/Hβ ) 0.7 if we include candidate AGNs. For AGNs with a high ionization state, the L04 diagnostic indeed gives perfect results.

Figure 2 also shows that DEW and L10 classifications are doing quite well by following the K06's curve almost exactly for log ([OIII]/Hβ ) 0.25. In both cases, we notice an underestimate of the number of AGNs for 0.25 log ([OIII]/Hβ ) 0.7, where this effect is more significant for the L10 diagnostic than for the DEW diagnostic. Nevertheless, the DEW diagnostic clearly overestimates the number of AGNs in low ionization states, i.e. mainly LINERs (log ([OIII]/Hβ ) 0.25). In this region, the L10 diagnostic, in contrast, satisfyingly follows the K06's curve, with a small underestimate.

Unfortunately, including the SFG/Sy2 and LIN/comp regions does not help. It makes a peak of galaxies at log ([OIII]/Hβ ) ≃ 0.4 appear that does not fit the reference profile, while in a lower ionization state the number of AGNs is now clearly overestimated. Those two effects are from the high contamination of the L10 SFG/Sy2 region by K06 SFGs and of the L10 LIN/comp region by K06 composites.

The supplementary M11 diagnostic

Figure 3 shows four regions where galaxies of different types (according to the reference K06diagnostic) are confused in the log ([OIII]λ 5007/Hβ ) vs. log ([OII]λ λ 3726 + 3729/Hβ ) diagram. It shows also in its center and right panels how these galaxies behave in the D n (4000) vs. max (EW[OII], EW[NeIII]) diagram. From top to bottom, the four studied regions are SFG/Sy2, SFG/comp, another SFG/comp region not defined in the L10 diagnostic but where a non negligible number of the composites (25%) are still mixed with SFGs, and LIN/comp.

The SFG/Sy2 region

In the L10 SFG/Sy2 region (see Fig. 3 Seyfert 2 would fall above this line, SFG below.The slope and zero point of this line have been optimized by minimizing on a grid the following function:

χ 2 = (1 -S A ) 2 + (1 -S B ) 2 + (C A ) 2 + (C B ) 2 , ( 11
)
where S A , S B , C A , C B are the success rate for AGN above the defined line, the success rate for SFG below the line, the contamination by SFG above the line, and the contamination by AGN below the line (all values between 0 and 1), respectively. Indeed, we want to maximize the success rates and minimize the contamination at the same time above and below the defined line.

The grid is done in 0.01dex steps in both slope and zero point.

To minimize computer time, limits on this grid are defined by eye.

We have established the success of our new diagnostic in the L10 SFG/Sy2 region (see Table 5). This chart shows that our demarcation line works almost perfectly and can be used in that area. We have now correctly classified almost all actual Seyfert 2 in our sample: 97% of those in the L10 SFG/Sy2 region are classified as Seyfert 2. Given that 59% of the K06 Seyfert 2 in the whole sample were already correctly classified, and 26% of them classified as L10 SFG/Sy2, this increases the global success rate to 85%. This is the best success rate one can obtain by combining L10 and DEW diagrams. The contamination in the SFG/Sy2 region is made of 3.1% SFGs above the line defined by Eq. 10 and 0.9% Seyfert 2 below it.

The SFG/comp region

The L10 SF/comp (see Fig. 3 second line) contain composites, SFGs, and very few LINERs. Following the optimization procedure explained above, we find the following equation which separate as many SFGs as possible from composites: .4, (12) where SFGs are below this line. Since SFGs dominate the sample, the region below this line is composed of 98% SFGs. Conversely, the region above this line is still a mix between SFGs (59%), composites (36%), and a few LINERs (4%). We again applied the optimization procedure but now only consider the latest region, in order to isolate pure composites as much as possible. We obtain:

D n (4000) = -0.11×log(max (EW[OII], EW[NeIII]))+1
D n (4000) = -0.17×log(max (EW[OII], EW[NeIII]))+1.75, ( 13
)
where composites are above the line, SFG/comp below it (i.e. between the two lines).

Tables 6 and7show the success chart and the contamination chart of the supplementary M11 diagnostic, in the L10 SFG/comp region. From all the K06 SFGs present in this region, 64% are now correctly classified as SFGs, another 36% being still ambiguously classified as SFG/comp.It is unfortunately impossible to increase this success rate without misclassifying too many K06 composites as SFGs. Only 14% of K06 composites could be isolated. Newly isolated SFGs are not significantly contaminated by K06 composites (2%), and neither are the newly isolated composites by K06 SFGs (6%). The majority of the K06 of composites (81%) are still ambiguously classified

Additional region of composites mixed with SFGs

We define a last region where K06 composites are mixed with K06 SFGs in the L10 diagnostic. It is located below the SFG/Sy2 region, and above log ([OIII]λ 5007/Hβ ) > -0.4, excluding the SFG/comp region (see Fig. 3 third line). Even though we can see that these K06 SFGs are mostly spread over the bottom right of the DEW diagnostic diagram and K06 composites are slightly above, there is still a small area where they get together. Following the same optimization procedure as above, we first fit the optimized demarcation line between pure SFGs and SFGs mixed with composites: 72, (14) where SFGs are below this line. As in previous section, the region above this line contains a mix of SFGs (25%) and composites (75%). In this region, we fit another optimized demarcation line between pure composites and composites mixed with SFGs: .66, (15) where composites are above this line, and SFG/comp below it (i.e. between the two lines). We finally add the remaining mixed galaxies to the SFG/comp type.

D n (4000) = 0.44 × log(max (EW[OII], EW[NeIII])) + 0.
D n (4000) = -0.37×log(max (EW[OII], EW[NeIII]))+1
Tables 6 and9 show the success and contamination charts of the supplementary M11 diagnostic in this last region. Of all K06 SFGs present in this region, 92% are now correctly classified, and another 5% are ambiguously classified as SFG/comp. We Indeed, one may argue that LINERs are more concentrated on the top and composites on the bottom of the diagram, so we propose a straight line at D n (4000) ≈ 1.75 as a separation. Using this line we find, however, 61% LINERs and 39% composites above, 28% and 72% below respectively, which is unsatisfactory. Thus, we do not update the LIN/comp region as in Paper I.

Discussion

Figure 4 shows our supplementary M11 diagnostic combined with L10 diagnostic, in one of the standard K06 diagnostic diagrams. The left panel looks pretty good: SFGs Seyfert 2, LINERs, and some composites lie almost perfectly in the correct corresponding regions of this diagram. In contrast, the right hand panel shows the limitations: objects that are still ambiguously classified or as SFG/comp or as LIN/comp. Anyway, comparing Fig. 4 to the bottom left hand panel of Fig. 1, we see a clear improvement. Tables 10 and11 establish new contamination and success charts in order to get a more precise measurement of this improvement. Success chart shows that 1% of K06 SFG are classified in a region where they are not supposed to be. K06 composites are predominantly found in the SFG/comp region (51%) than in the composite region (23%). This is an improvement over Paper I, but it shows that neither the L10 nor the DEW diagrams are really good at identifying composites at high redshift. K06 Seyfert 2 galaxies and LINERs have a high success rate (respectively 85% and 74%), which is for Seyfert 2 galaxies a really good improvement compared to Paper I. For K06 LINERs, the success rate increases to 91% including the LIN/comp, but one has to be aware that this region is actually made of only 39% K06 LINERs and is dominated by 57% K06 composites.

Nevertheless, one can conclude from the contamination chart that SFGs, Seyfert 2, and LINERs are not significantly contaminating each other. The main contamination comes in all cases One could worry about aperture effects. Indeed, SDSS spectra are based on 3" fibers. This may end in overestimated D n (4000) values for close objects where only the central bulge is covered by the fiber. However, one can see in Fig. 3 that only objects with D n (4000) < 1.5 could change their classification with a significant aperture effect. Looking at Fig. 16 in Kauffmann et al. (2003b), we see that those objects do not actually suffer from a strong aperture effect. We conclude that our diagnostic is not biased by this effect.

Finally, we invite the reader to take a look at the right hand panels of Fig. 2. It shows the AGN counts obtained with our new supplementary M11 diagnostic combined with L10 diagnostic. We clearly see that the diagnostic derived in the present paper is the one that follows the reference K06 curve more accurately. There are still problems for log ([OIII]/Hβ ) 0.25, which is normal since we did not manage to change the classification of LINERs by adding the DEW diagnostic diagram.

Conclusion

By adding the M11 diagnostic to the L10 diagnostic derived in Paper I, we now have a very good classification of emission-line galaxies that can be used on high-redshifts samples. The main improvements compared to Paper I are -The unambiguous classification of objects in the former SFG/Sy2 region as SFGs or Seyfert 2. -The unambiguous classification of some of the objects in the SFG/comp region as SFGs or composites (where no composites at all were found in Paper I). -A better definition of the SFG/comp region, which leaves fewer possible composites not flagged as such. We emphasize again that this region is in any case dominated by SFGs.

No improvements could have been done in the LIN/comp region, which is left unchanged compared to Paper I. In order to use the diagnostic derived in this paper, one should follow these steps.

1. Classify objects in the log ([OIII]λ 5007/Hβ ) vs.

log ([OII]λ λ 3726 + 3729/Hβ ) with the L10 diagnostic derived in Paper I (see also equations in Sect. 3.2). 2. Classify objects falling in the SFG/Sy2 region as SFGs or Seyfert 2 using Eq. 10. 3. Isolate objects falling the the SFG/comp region as (a) SFGs using Eq. 12, and (b) composites using Eq. 13. 4. Define a new SFG/comp region inside the SFG region using log ([OIII]λ 5007/Hβ ) > -0.4, so inside this new region, isolate (a) SFGs using Eq. 14, and (b) composites using Eq. 15.

In both points (3) and (4) above, objects not classified as SFGs or composites remain of the ambiguous SFG/comp type. We invite the reader to look at the "JClassif" software (available at: http://www.ast.obs-mip.fr/galaxie/), which performs these steps automatically on any sample, as well as other classification schemes. Table 11 may be used as a probability chart showing whether each type in our diagnostic is one of the K06 reference types. However, we warn the reader that the relative proportions of SFGs, composites and AGNs in each regions of our diagnostic diagrams may evolve with redshift compared to the SDSS sample. Finally, we note that it is possible to upgrade this classification to higher redshifts where [OIII]λ 5007 and Hβ emission lines get red-shifted out of the spectra (1.0 z 1.5 on optical spectra). To that goal one may use the equations provided by Pérez-Montero et al. (2007), which convert [NeIII]λ 3869 and Hδ to [OIII]λ 5007 and Hβ .

  log ([OIII]/Hβ ) = 0.11/[log([OII]/Hβ ) -0.92] + 0.85, (4) where AGNs are above this curve. The second equation separates Seyfert 2 from LINERs in the AGN region: log ([OIII]/Hβ ) = 0.95 × log([OII]/Hβ ) -0.40.(5)

Figure 1 .

 1 Figure 1. Summary of existing schemes for the classification of emission-line galaxies at high redshift. Top: results of the reference diagnostic (Kewley et al. 2006) are shown in the log([OIII]λ 5007/Hβ ) vs. the log ([OII]λ λ 3726 + 3729/Hβ ) diagram (left) and in the D n (4000) vs. max (EW[OII], EW[NeIII]) diagram (right). The code is blue: SFG; green: Seyfert 2; cyan: LINERs; magenta: composites. Bottom: The results of the high-redshift classifications are shown in the standard log([OIII]λ 5007/Hβ ) vs. log([NII]λ 6583/Hα) diagram. Left: the L10 diagnostic (Lamareille 2010). Right: the DEW diagnostic (Stasińska et al. 2006). Same color code as above except green: stands for all AGNs in the bottom-right panel; light blue: SFG/comp; yellow: LIN/comp; orange: SF/Sy2.In bottom-right panel, the long dashed line is the boundary between SFG and AGN used by Stasińska et al. (2006).

  top), K06 Seyfert 2 and SFGs are confused. It is unfortunately obvious in the bottomleft panel that the DEW diagnostic does not separate the two classes of objects correctly in the L10 SFG/Sy2 region. We thus propose a new demarcation line to separate K06 Seyfert 2 from SFGs, valid only in the L10 SFG/Sy2 region, with the equation D n (4000) = 0.22 × log(max (EW[OII], EW[NeIII])) + 0.97.(10)

Figure 2 .

 2 Figure 2. Comparison between the number of AGNs (Seyfert 2 and LINERs) counted with different calibrations at high redshift, as a function of log([OIII]λ 5007/Hβ ). From left to right, the calibrations used are L04, DEW, L10 (paper I), and the present paper. Top panels show absolute counts. Bottom panels show difference counts. In each panel, the reference counts established with the K06 diagnostic are shown in red, and the counts obtained with the high-redshift diagnostic are shown in black. The gray dashed lines show the results when including "candidate" regions, i.e. for L04, L10, and the present paper's classifications: candidate AGNs region; SFG/Sy2 and LIN/comp regions; LIN/comp region.

Figure 3 .

 3 Figure 3. Left: In the log ([OIII]λ 5007/Hβ ) vs. log ([OII]λ λ 3726 + 3729/Hβ ) diagram, the different regions where galaxies of different types are mixed (color-code according to the reference K06 diagnostic). The curves are the ones from the Lamareille (2010) diagnostic. Center and right: The same points as in the associated left panels, but now in the D n (4000) vs. max (EW[OII], EW[NeIII]) diagram. For clarity, we plot the different types in two panels.The solid lines show the adopted demarcation lines (see text for details). The dashed line in top-right panels is the separation adopted by Stasińska et al. (2006).

Figure 4 .

 4 Figure 4. Results of the new diagnostic derived in the present paper in the standard log([OIII]λ 5007/Hβ ) vs. log([NII]λ 6583/Hα) diagram. For clarity, only SFGs, AGNs and composites are shown in the left panel, while SFG/comp and LIN/comp are shown in the right panel. Same color code as in Fig. 1.

Table 1 .

 1 Success chart of the L10 diagnostic, where numbers are the probability that a given reference K06 type goes in a given L10 type. * union of the LINERs and LIN/comp regions.

			reference K06 classification
	L10 classification	SFG	Composites Seyfert 2 LINERs
	total	100	100	100	100
	Seyfert 2	0.08	0.19	59.27	3.81
	SFG/Sy2	3.94	1.13	26.25	0.12
	SFG	40.24	27.79	5.90	2.44
	SFG/comp total SFG *	55.47 99.65	55.15 84.07	0.14 32.28	2.93 5.50
	LINERs	0.17	6.94	8.00	73.51
	LIN/comp total LIN * *	0.11 0.27	8.81 15.74	0.44 8.44	17.18 90.70

* union of SFG/Sy2, SFG, and SFG/comp regions. *

Table 1

 1

Table 2 .

 2 Contamination chart for the L10 diagnostic, where numbers are the probability that a given L10 type actually is any of the reference K06 types. * union of the LINERs and LIN/comp regions.

			reference K06 classification
	L10 classification total	SFG	Comp. Seyfert 2 LINERs
	Seyfert 2	100	2.73	1.29	86.71	9.28
	SFG/Sy2	100	74.05	4.30	21.48	0.17
	SFG	100	86.90	12.17	0.55	0.38
	SFG/comp total SFG *	100 100	82.96 84.10	16.72 14.38	0.01 1.19	0.32 0.34
	LINERs	100	2.28	19.40	4.80	73.51
	LIN/comp total LIN * *	100 100	3.37 2.61	56.57 30.68	0.61 3.53	39.46 63.18
	* union of SFG/Sy2, SFG, and SFG/comp regions.

*

Table 3 .

 3 Success chart for DEW diagnostic

			reference K06
	DEW	SFG	Composites Seyfert 2 LINERs
	total	100	100	100	100
	SFG	94.95	38.08	20.24	2.16
	AGN	5.05	61.92	79.76	97.84

Table 4 .

 4 Contamination chart for DEW diagnostic

				reference K06
	DEW total	SFG	Composites Seyfert 2 LINERs
	SFG	100	91.56	7.44	0.85	0.15
	AGN	100	17.94	44.57	12.32	25.17

Table 5 .

 5 Success chart for the supplementary M11 diagnostic in the L10 SFG/Sy2 region.

		reference K06
	M11	SFG	Seyfert 2
	total	100	100
	SFG	99.10	3.10
	Seyfert 2	0.90	96.90

Table 6 .

 6 Success chart for the supplementary M11 diagnostic in the L10 SFG/comp region.

			reference K06
	M11	SFG	LINERs composites
	total	100	100	100
	SFG	63.69	3.47	5.31
	composites	0.19	70.14	13.95
	SFG/comp 36.12	26.39	80.74

Table 7 .

 7 Contamination chart for the supplementary M11 diagnostic in the L10 SFG/comp region.

			reference K06
	M11	total	SFG	LINERs composites
	SFG	100	98.30	0.02	1.67
	composites	100	5.85	8.21	85.93
	SFG/comp	100	68.81	0.19	31.00

Table 8 .

 8 Success chart for the supplementary M11 diagnostic in the additional region of the L10 diagnostic where SFG are mixed with composites.

		reference K06
	M11	SFG	composites
	total	100	100
	SFG	92.10	12.69
	composites	2.90	61.97
	SFG/comp	5.00	25.34
	as SFG/comp. The best reason to use this diagram is clearly for
	isolating SFGs. The SFG/comp region is now made of 69% K06
	SFGs and 31% K06 composites, which is more balanced than in
	Paper I (respectively 83% and 17%).

Table 9 .

 9 Contamination chart for the supplementary M11 diagnostic in the additional region of the L10 diagnostic where SFG are mixed with composites.Figure 3 (bottom) shows the LIN/comp region of the L10 diagnostic in the DEW diagnostic diagram. It is clear that this diagram cannot be used to isolate LINERs cleanly from composites.

			reference K06
	M11	total	SFG	composites
	SFG	100	96.39	3.61
	composites	100	14.50	85.30
	SFG/comp	100	42.08	57.92
	also managed to isolate 62% of the K06 composites falling in
	this region, which is an improvement compared to the L10 diag-
	nostic. Conversely, 12% of the K06 composites are now unfor-
	tunately misclassified as SFGs. This is still an improvement : we
	recall that 100% of the K06 composites in this region used to be
	classified as SFGs with the L10 diagnostic. Most of them (62%)
	are now classified as composite galaxies, and another 25% are
	still ambiguously classified as SFG/comp. The composites de-
	fined in this region are contaminated by 15% K06 SFGs, which
	may not be neglected. The SFG/comp galaxies defined in this re-
	gion are made of approximately half K06 SFGs (42%) and half
	K06 composites (58%).
	5.4. The LIN/comp region

Table 10 .

 10 Overall success chart for the L10 and M11 diagnostics.

			reference K06
	L10/M11	SFG	Composites Seyfert 2 LINERs
	total	100	100	100	100
	SFG	77.97	8.92	0.92	0.10
	SFG/comp	20.99	50.97	0.47	0.98
	composites	0.66	23.44	5.46	4.30
	Seyfert 2	0.12	0.93	84.71	3.93
	LINERs	0.17	6.94	8.00	73.51
	LIN/comp	0.11	8.81	0.44	17.18
	total SFG 1	98.96	59.88	1.39	1.08
	total LINERs 2	0.27	15.74	8.44	90.70
	total comp. 3	21.75	83.22	6.38	22.46
	1 SFG+SFG/com
	2 LINERs+LIN/comp
	3 composites+SFG/comp+LIN/comp.

Table 11 .

 11 Overall contamination chart for the L10 and M11 diagnostics. 33% in the SFG/comp region, 19% in the LINERs region, and 57% in the LIN/comp region. It is conversely very low in the SFG and Seyfert 2 regions.

				reference K06
	L10/M11	total	SFG	Composites Seyfert 2 LINERs
	SFG	100	97.68	2.26	0.05	0.01
	SFG/comp	100	66.81	32.89	0.07	0.23
	composites	100	11.02	79.77	3.99	5.23
	Seyfert 2	100	2.73	4.42	86.20	6.66
	LINERs	100	2.28	19.40	4.80	73.51
	LIN/comp	100	3.37	56.57	0.61	39.46
	total SFG 1	100	75.83	15.37	3.30	5.50
	total LINERs 2	100	2.61	30.68	3.53	63.18
	total comp. 3	100	53.67	41.63	0.68	4.02
	1 SFG+SFG/com
	2 LINERs+LIN/comp
	3 composites+SFG/comp+LIN/comp.
	from composites:

J. Marocco et al.: Spectral classification of emission-line galaxies from the Sloan Digital Sky Survey

Acknowledgements. F.L. thanks "La cité de l'espace" for financial support while this paper was being written. The data used in this paper were produced by a collaboration of researchers (currently or formerly) from the MPA and the JHU. The team is made up of Stéphane Charlot (IAP), Guinevere Kauffmann and Simon White (MPA), Tim Heckman (JHU), Christy Tremonti (Max-Planck for Astronomy, Heidelberg -formerly JHU), and Jarle Brinchmann (Sterrewach Leiden -formerly MPA). All data presented in this paper were processed with the JClassif software, part of the Galaxie pipeline. We thank the referee for useful corrections and suggestions for improving the paper.

Funding for the SDSS and SDSS-II has been provided by the Alfred P. Sloan Foundation, the Participating Institutions, the National Science Foundation, the U.S. Department of Energy, the National Aeronautics and Space Administration, the Japanese Monbukagakusho, the Max Planck Society, and the Higher Education Funding Council for England. The SDSS Web Site is http://www.sdss.org/.

The SDSS is managed by the Astrophysical Research Consortium for the Participating Institutions. The Participating Institutions are the American Museum of Natural History, Astrophysical Institute Potsdam, University of Basel, University of Cambridge, Case Western Reserve University, University of Chicago, Drexel University, Fermilab, the Institute for Advanced Study, the Japan Participation Group, Johns Hopkins University, the Joint Institute for Nuclear Astrophysics, the Kavli Institute for Particle Astrophysics and Cosmology, the Korean Scientist Group, the Chinese Academy of Sciences (LAMOST), Los Alamos National Laboratory, the Max-Planck-Institute for Astronomy (MPIA), the Max-Planck-Institute for Astrophysics (MPA), New Mexico State University, Ohio State University, University of Pittsburgh, University of Portsmouth, Princeton University, the United States Naval Observatory, and the University of Washington.


Preamble

<tiger2/> is an XML format serializing the ISO meta-model for syntactic annotations defined in the SynAF1 framework. The format is based on the TigerXML format developed as part of the German TiGer Treebank annotation project2 . The focus in <tiger2/> is on the ability to flexibly express all manner of syntactic annotation structures, including multiple, possibly conflicting, typed annotation nodes and edges with arbitrary annotation names expressing both constituent and dependency trees with modern, standard conformant mechanisms.

Graph structure

In <tiger2/> annotations are represented in a graph structure. The graph structure can be described as G=(V, E) with: a set of nodes V and a set of edges E with e=(v ∈ V, v ∈ V) ∈ E A graph represents a bundle of interrelated nodes and edges. It is not specified which parts of a primary text are covered by a single graph: a graph can cover e.g. a sentence, a sub-sentence, a chapter or a whole text.

Nodes and Edges are more or less placeholders for linguistic annotations. An annotation is in general an attribute-value-pair. In <tiger2/> we used two kinds of nodes 1) terminal-nodes and 2) nonterminal-nodes.

A terminal-node represents the reference to the primary data. As we will see later on, this can be a direct reference to a text-span or an indirect one to other xml-elements in e.g. a MAF-file (Morphosyntactic Annotation Framework, see http://atoll.inria.fr/~clerger/MAF/html/index.html).

Terminal nodes are represented by the <t>-element and are grouped together in a <terminals>element.

A Nonterminal node is an inner node, referring directly or indirectly to a terminal node. It is represented by the <nt>-element and belongs to the surrounding element <nonterminals>.

An Edge always has to have a source and a target. Both of them can be either a terminal or a nonterminal-node. In <tiger2/> an edge is represented by the <edge>-element and its source is given by the surrounding element. This means that an <edge>-element always has to be a child-element of a <t> or an <nt> element. The target is given by the @target attribute and must refer to a node in the same XML-document.

Example 1 shows the <tiger2/> representation of the graph structure:

Primary data and token representation

In <tiger2/> there are different possibilities to represent primary data and tokens. Tokens and primary data can either be included in the <tiger2/>-document (inline representation), or they can be referred to, being contained in another file (standoff representation). The inline representation makes it possible to have all data in just one <tiger2/>-document, whereas the standoff representation enables one to refer to other formats, for instance a MAF file containing tokens and wordForms.

Both options are possible and the decision is largely made based on the needs of the corpus.

Inline representation:

The benefit of the inline representation is that you can find all elements of a corpus in just one <tiger2/>-document, making it easier for humans to read it and for machines to process it. To go this way you can encode the primary data as part of the terminal-nodes. This can be done by using the @word attribute of the <t>-element. An example is given by example 2.

Example 2 shows two terminal-nodes, representing two tokens. The first token contains the word "two", the second token contains the word "words". The order of the tokens is given by the order of the xml-elements. In this case it means that the word "two" is followed by the word "words" in the primary data.

However it should be pointed out that this representation is not primary-data-preserving. This means, that we loose some information about the primary data when representing a primary text in this representation. On the one hand the inline representation does not care about whitespaces between tokens, and on the other hand untokenized parts of the primary data will be lost. Take a look at examples 3 and 4.

Example 1: graph structure <graph xml:id="s1_g1"> <terminals> <t xml:id="s1_t1"/> <t xml:id="s1_t2"/> </terminals> <nonterminals> <nt xml:id="s1_nt1"> <edge xml:id="s1_e1" target="#s1_t1" /> <edge xml:id="s1_e2"target="#s1_t2" /> </nt> </nonterminals> </graph> Example 2: graph structure <t xml:id="s1_t1" word="two"/> <t xml:id="s1_t2" word="words"/>

In example 3 and 4 one can see that it is not possible to resolve whether there was a whitespace between the tokens or not. In the case of token "s1_t1" and "s1_t2" there was one, whereas in the case of punctuations like in tokens "s1_t3?" and "s1_t4" there was none. An unrepresented text span like the word "a" will be lost.

Because of the restrictions of XML-attributes, another problem occurs: reserved signs like an angle bracket ("<") can not be represented inside an xml-attribute-value. Therefore one has to escape the angle bracket with "<", see example 5.

When interpreting the primary-data in the case of example 5, it is not possible to resolve whether the origin text contains an angle bracket ("<") or the literal escaping ("<").

Standoff representation

The aforementioned problems can be avoided by using a standoff representation. In <tiger2/> you can refer to other files containing the tokens or even higher structures e.g. wordForms. You can do this using the @corresp attribute of the terminal-nodes. The @corresp attribute replaces the @word attribute and contains a reference in XPointer syntax to another resource, for example a MAF-file. You either can use the @word or the @corresp attribute. Example 6, 7 and 8 show the use of the standoff representation via the @corresp attribute.

Example 3: primary data

This is a sample.

Example 4: inline representation <t xml:id="s1_t1" word="This"/> <t xml:id="s1_t2" word="is"/> <t xml:id="s1_t4" word="sample"/> <t xml:id="s1_t5" word="."/> ,3,3))"/> ... <wordForm xml:id="wf_1" lemma="we" tokens="t1"/> <wordForm xml:id="wf_2" lemma="can" tokens="t2"/> Example 6, 7 and 8 contains excerpts of three different files, first an excerpt of a file containing the primary text, second a MAF file containing the tokenisation and an aggregation of tokens to wordForms and third an excerpt of the <tiger2/> document refering the MAF-document.

Typing of nodes and edges

Nodes and edges can also be given types in <tiger2/>. A type is a special kind of annotation and is represented by the @type attribute contained in a <t>, <nt> or <edge> element. In example 9 we use the @type attribute to give a more special semantic meaning to the terminal nodes "s1_t1", "s1_t2", the nonterminal-node "s1_nt1" and the edges "s1_e1", "s1_e2" and "s1_e3". The example shows the wordForm "house-builder", in which the node house is seen as a direct object dependent of builder, a deverbal noun heading a synthetic compound. The non-terminal node for "housebuilder" may be given a special type to analyze it as a morphological compound, as opposed to a syntactic phrase. Similarly, the dependency edge is given the type "dep" to distinguish it from the constituency edges in the graph.

The domain of possible @type values is not defined by <tiger2/> and is therefore the responsibility of an interpreting tool. For a more specific definition of a @type value you can define the domain of the values via an annotation with a <feature> element as we will show in the section Using the @type attribute. If you do not use the @type attribute inside a <t>, <nt> or <edge>-element, they will be implicitly set to a default value. In the case of an edge the type will be set to "prim" (a primary edge), in the case of a terminal-node it will be set to "t" and in the case of a nonterminal-node it will be set to "nt". If you want to specify the domain for @type attributes, it is not possible to override the semantics of the three default values. The @type attribute is also used for the declaration of the domain for annotation-names and the domain for annotation-values as we show in section Annotations.

Example 8: example.tiger2 <terminals> <t xml:id="s9_1" corresp="example.maf#wf_1" /> <t xml:id="s9_2" corresp="example.maf#wf_2"> </terminals> Example 9: using type for <t>, <nt> and <edge>-element ... <t xml:id="s1_t1" word="house-" type="morpheme" /> <t xml:id="s1_t2" word="builder" type="morpheme"> <edge xml:id ="s1_e1" type= "dep" target="#s1_t1" label="obj"/> </t> ... <nt xml:id="s1_nt1" type="wordform"> <edge xml:id ="s1_e2" type="comp" target="#s1_t1" /> <edge xml:id ="s1_e3" type="comp" target="#s1_t2" /> </nt>

Annotations

Annotations are realized as attribute-value-pairs and can be appended to nodes and edges. The name of an annotation is given by the name of an XML attribute and the annotation value is given by its XML attribute value. In general in <tiger2/> there are no restrictions for setting names or values for annotations depending on specific linguistic schools. Therefore you are free to append any attributevalue-pair to a <t>, <nt> or <edge> element. The only restriction is given by reserved attributes of <tiger2/> for example @type, @word, @corresp and @domain. These attributes have fixed semantics and cannot be overridden.

Example 10 shows the annotation mechanism for nodes and edges.

In example 10 we show a word "I", annotated with the part-of-speech annotation "PP" and the lemma-annotation "I". Neither "pos" nor "lemma" is reserved -they also can be named "part-ofspeech" or "lem" or any other non-reserved name. The terminal "s1_t1" is headed by a nonterminal "s1_nt1" being annotated with the categorical annotation nominal phrase. The edge "s1_e1" corresponding "s1_nt1" and "s1_t1" also gets an annotation ("label='HD'"), which means the nonterminal acts as a head for the terminal.

Domain declaration

In <tiger2/> it is necessary to define a domain for annotation names, this must be done in the header section of <tiger2/>, namely in the <annotations> element inside the element <head>. This domain is referred to by the annotation name inside the node or edge. For example let us take a look again at example 10. The declaration of the domain for annotation-names can appear as shown in example 11.

The mapping between the annotation name and the domain declaration is done by resolving the e-mail: tiger2@lists.hu-berlin.de homepage: http://korpling.german.hu-berlin.de/tiger2/ HUBerlin-IDSL/INRIA

Example 10: annotation of a <t>, <nt> and <edge>-element <terminals> <t id="s1_t1" word="I" lemma="I" pos="PP"/> ... </terminals> <nonterminals> <nt id="s1_nt1" cat="NP"> <edge xml:id="s1_e1" label="HD" target="s1_t1"/> </nt> ...

</nonterminals>

Example 11: domain declaration for annotation-names and annotation-values <head> <annotations> <feature xml:id="f1" name="pos" domain="t" /> <feature xml:id="f2" name="lemma" domain="t" /> <feature xml:id="f3" name="cat" domain="nt"/> <feature xml:id="f4" name="label" domain="edge"/> </annotations> </head> name of the XML attribute of the annotation and the @name attribute of the element <feature>. The attribute @domain specifies that the declared feature is applicable for just the given kind of <tiger2/> elements. In the given example, this means, that the feature declarations for "pos" and "lemma" can only be used by <t> elements, "cat" only can be used by <nt> elements and "label" can only be used by <edge> elements. The attribute @domain is optional and need not be set. If it is not set it means that the feature declaration is available for all three kinds of elements.

Feature values

Not only domains for annotation names can be declared in <tiger2/>, but also domains for annotation values. Declaring a domain for annotation values can be done by using the <value> element inside the <feature> element. The <value> element has a @name attribute, identifying the value name and also working as an anchor for annotation values. The element can contain a text, which acts as a description for the annotation-value. Example 12 shows the use of an annotation value domain declaration. In the case of example 12 the set of possible values for an annotation value with the annotationname "pos" only contains a "PP" element, standing for a personal pronoun. In this case no other values are possible for this annotation for terminal nodes. To increase the set of possible annotation values just add further <value> elements to the <feature> element. The number of possible annotation values is not limited. If there are no <value> elements given inside a <feature> element, the set of annotation values is not defined and can be any string. In this case, a validation of annotation values will not take place. This is very useful in case of lemma annotations, for which it is not possible to define the domain of possible annotation values

DCR references

Often domain declarations are not only interesting for one corpus or just one project, they are interesting for a whole community. Therefore several data category registries have evolved. The most popular one is the ISOCat (see: http://www.isocat.org/). When using <tiger2/> you can benefit from the power and the community creating the registries, by making a reference from your domain declaration to the registries. To support this we provide the attribute @datcat, defined via the namespace "http://www.iso.org/ns/DCR". This attribute can be used in <feature> and <value> elements. This can improve the usefulness of your corpus, thanks to a much better understanding of the annotations used. Example 13 shows the use of the @datcat attribute. e-mail: tiger2@lists.hu-berlin.de homepage: http://korpling.german.hu-berlin.de/tiger2/ HUBerlin-IDSL/INRIA

Example 12: referencing domains for annotation-name and annotation-value <head> <annotations> <feature xml:id="f2" name="pos" domain="t"> <value xml:id="f2_1" name="PP">Personal pronoun</value> </feature> </annotations> </head> ... <terminals> <t id="s1_t1" word="I" pos="PP"/> </terminals>

In example 13 we use a terminal covering the word "I", which is annotated by part-of-speech annotation having the value personal pronoun. The domain for the annotation name and annotation value is declared in the <annotations> element, as already seen in the examples above. But in this example we use the @datcat attribute to refer to the ISOCat system. The annotation name is not only declared by mentioning it in the <tiger2/> document, but also in the common registry. Therefore you do not necessarily need a description inside the <value> element, because it is given by the ISOCat entry, though <tiger2/> does not prohibit using both.

Using the @type attribute

If you need a finer granularity for the declaration of annotation domains, you can use the @type attribute inside the <t>, <nt> and <edge> element. As already mentioned in the section Typing of nodes and edges, this attribute on the one hand types the given element and on the other hand represents a correspondence to the declaration of the annotation-domain. The element <feature> also contains an optional @type attribute, with which you can constrict the set of nodes and edges using the annotation domain. Example 14 shows this mechanism.

In example 14 the domain of the annotation name for terminal "s1_t1" is defined by the feature "f2". The @type attribute guarantees that the feature only declares an annotation name domain for terminals of the type "wordform". A terminal without this type cannot be corresponded to in that e-mail: tiger2@lists.hu-berlin. Example 14: using the @type attribute for annotation domain declaration <head> <annotations> <feature xml:id="f2" type="wordform" name="lemma" domain="t"> <value xml:id="f2_1" name="PP">Personal pronoun</value> </feature> </annotations> </head> ... <terminals> <t id="s1_t1" word="I" type="wordform" lemma="I" pos="PP"/> </terminals> domain. If no @type attribute is given in the <feature> element, the domain works for all elements respecting the domain declaration (<t>, <nt> or <edge> elements).

As we already mentioned in the section Typing of nodes and edges, in <tiger2/> it is also possible to declare the domain for types. The mechanism to do so is the same as for declaring annotation values, namely via the <feature> and <value> element. Example 15 shows the declaration of the domain for types.

In example 15 we declared the domain for types, by adding an entry for the type "compound". Note that if you declare such a domain, it is not possible to have non-declared values in the @type attribute of the corresponding element (<t>, <nt> or <edge>). This enables the validation of the @type attribute. The default types "t" for domain t, "nt" for domain nt and "prim" for domain edge, are implicitly given and do not have to be declared explicitly.

Grouping

Several graphs can be grouped by a segment, which is a semantic unit. For example, a segment can stand for a sentence, a paragraph and so on. A segment is represented in <tiger2/> via the <s> element. Such a segment must contain at least one graph, the upper limit of graphs is not bound. Example 16 shows the containment:

A corpus or sub-corpus (as described in the section Corpus-structure) can contain an unbounded number of segments.

Corpus-structure

In <tiger2/> you can represent a whole corpus structure containing several sub-corpora in just one <tiger2/> document. But in each <tiger2/> document you can represent just one root corpus represented by the <corpus> element. The corpus element must specify the format version of the data using the @tiger_version attribute. A corpus structure or more precisely a subcorpus can be e-mail: tiger2@lists.hu-berlin.de homepage: http://korpling.german.hu-berlin.de/tiger2/ HUBerlin-IDSL/INRIA

Example 15: declaration of domain for the @type attribute <feature xml:id="f3" name="type" domain="nt"> <value xml:id="f2_1" name="compound"> a unit of text, which acts as a kind of word </value> ...

</feature>

Example 16: grouping mechanism via <s> element <s xml:id="s1"> <graph xml:id="s1_g1"/> <graph xml:id="s1_g2"/> ... </s> <s xml:id="s2"> <graph xml:id="s2_g1"/> <graph xml:id="s2_g2"/> ... </s>

http://www.tc37sc4.org/document.php?p=tc37sc4_list_total.txt&search_text=SynAF&project_category=on

http://www.ims.uni-stuttgart.de/projekte/TIGER/ e-mail: tiger2@lists.hu-berlin.de homepage: http://korpling.german.hu-berlin.de/tiger2/ HUBerlin-IDSL/INRIA

e-mail: tiger2@lists.hu-berlin.de homepage: http://korpling.german.hu-berlin.de/tiger2/ HUBerlin-IDSL/INRIA

created by using the <subcorpus> element inside the <corpus> element. @tiger_version is inherited by subcorpora and should not be specified individually for each subcorpus. The <subcorpus> element is a recursive structure and enables one to create an unbounded depth of subcorpora.

Example 17 shows the corpus-structure in <tiger2/>.

Example 17 shows a corpus "c1" containing in total 3 subcorpora. Two of them ("c2" and "c4") are directly contained in "c1", and "c3" is directly contained in "c2" and therefore indirectly contained in "c1".

Meta-annotations

A corpus or subcorpus can be annotated by meta-annotations. Using meta-annotations differs from the way nodes and edges are annotated. In the case of meta-annotations in <tiger2/> we give a fixed set of possible meta-annotations. Meta-annotations are limited to the header of a corpus or subcorpus. They can be identified by the enclosing element <meta>. These meta-annotations comes form the TigerXML-format and are usable for the <corpus> and the <subcorpus> element. The possible meta-annotations are the following ones: name, author, date, description, format and history. A meta-annotation is represented by an XML element with the same name, containing the value as text inside the element. Example 18 shows the use of meta-annotations.


Nicolas Lermé
email: nicolas.lerme@lipn.univ-paris13.fr

Lucas Létocart
email: lucas.letocart@lipn.univ-paris13.fr

François Malgouyres

Reduced graphs for min-cut/max-flow approaches in image segmentation

Keywords: image segmentation, min-cut/max-flow, graph reduction

In few years, min-cut/max-flow approach has become a leading method for solving a wide range of problems in computer vision. However, min-cut/max-flow approaches involve the construction of huge graphs which sometimes do not fit in memory. Currently, most of the max-flow algorithms are impracticable to solve such large scale problems. In this paper, we introduce a new strategy for reducing exactly graphs in the image segmentation context. During the creation of the graph, we test if the node is really useful to the max-flow computation. Numerical experiments validate the relevance of this technique to segment large scale images.

Introduction

Graph cuts provide a global optimization method based on max-flow/min-cut for solving a wide range of problems encountered in computer vision. Since pioneer work of Greig et al. [START_REF] Greig | Exact Maximum A Posteriori Estimation for Binary Images[END_REF], the graph cuts have recently known a quick development with the arrival of a fast max-flow algorithm [START_REF] Boykov | An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision[END_REF].

At the same time, the resolution of images acquired by digital devices increase constantly. In biomedical imaging, high-resolution data can involve massive graphs containing millions of nodes, which do not fit in memory. For these instances, global optimization methods such as graph cuts are impractical due to memory requirements, even using implicit graph representation.

To overcome this problem, a parallelized max-flow algorithm yielding nearlinear speedup with the number of processors has been proposed [START_REF] Delong | A Scalable Graph-Cut Algorithm for N-D Grids[END_REF]. This algorithm is able to segment large volumes while keeping optimality on solutions but remains less effective than standard graph cuts on small graphs. On the other side, some authors have also proposed heuristics based on multiresolution schemes [START_REF] Lombaert | A Multilevel Banded Graph Cuts Method for Fast Image Segmentation[END_REF][START_REF] Sinop | Accurate Banded Graph Cut Segmentation of Thin Structures Using Laplacian Pyramids[END_REF]. These algorithms reduce drastically speed and memory usage but fail to recover thin structures in images. Other heuristics [START_REF] Li | Lazy Snapping[END_REF][START_REF] Cigla | Region-based image segmentation via graph cuts[END_REF] use adjacency graphs. Results highly depend both on the image structure and the low-level segmentation algorithm.

In the present work, we propose an algorithm for reducing exactly graphs. In section 2, we review the graph cuts framework. Next, our approach is detailed in section 3 and compared to standard graph cuts in section 4.

Relashionship between images and min-cut/max-flow problem

An image can be defined by a pair (P, I) consisting of a finite discrete set P ⊂ Z d (d > 0) of points (pixels in Z 2 , voxels in Z 3 , etc.) and a function I that maps each point p ∈ P to a value I(p) in some value space. Usually, P corresponds to a rectangle. For an image, we can construct the associated directed weighted graph G = (V, E, c) consisting of a set of nodes V = P ∪ {s, t}, a set of edges E and a positive weighting function c : V 2 → R + defining the edge capacity. We distinguish two special nodes of V: the source node s specifying the "object" terminal and the sink node t specifying the "background" terminal. Furthermore, we split the set of edges E in two disjoint sets E n and E t denoting respectively n-links (neighborhood links) and t-links (terminal links). Next, we associate a neighborhood N (p) to any point p ∈ P. In this setting, we will use the following neighborhoods:

N 0 (p) = {q : d i=1 |q i -p i | = 1} ∀p ∈ P, N 1 (p) = {q : |q i -p i | ≤ 1 ∀1 ≤ i ≤ d} ∀p ∈ P,
where p i denote the i th coordinate of the point p. For instance, each pixel has 4 and 8 neighbors in 2D, 6 and 26 neighbors in 3D and finally 8 and 80 neighbors in 4D4 . In the sequel, the terms "connectivity 0" and "connectivity 1" will correspond respectively to the use of a N 0 and N 1 neighborhood.

In [START_REF] Boykov | Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images[END_REF], Boykov and Jolly showed that the image segmentation problem can be efficiently solved by minimizing a Markov Random Field of the form:

E(u) = β • p∈P E p (u p ) + p,q∈P q∈N (p) E p,q (u p , u q ), (1)
where u ∈ {0, 1} P . As usual, the data fidelity term E p (.) forces u p to fit the input data while the smoothness term E p,q (.) penalize neighboring pixels p and q if they have different labels. According to [START_REF] Kolmogorov | What Energy Functions Can Be Minimized Via Graph Cuts?[END_REF], the minimizer of the energy (1) corresponds to a min-cut in a graph and can be efficiently computed by the algorithm described in [2]5 .

Reducing graphs

As we have seen before, the memory usage for segmenting high-resolution data by graph cuts can be prohibitive. Nevertheless, we can observe that most of the nodes are useless because they are not traversed by any flow. Clearly, only a small part of nodes is used during the max-flow computation. When reducing such a graph, one would like to extract the smallest possible graph

G ′ = (V ′ , E ′ , c
) from G while keeping a solution u ′ identical or very close to u. Ideally, we want to maximize the reduction rate ρ = 1 -|V ′ | |V| s.t. u ≃ u ′ . However, the method for determining G ′ also needs to be fast and this rules out the resolution of such an optimization problem. Before describing our method for building G ′ , let us introduce some terminology. In accordance with the graph construction given in [START_REF] Kolmogorov | What Energy Functions Can Be Minimized Via Graph Cuts?[END_REF], we consider (without loss of generality) that a node is linked to at most one terminal, i.e:

(s, p) ∈ E t ⇒ (p, t) ∈ E t , ∀p ∈ P.
Z B = {z + b | b ∈ B, z ∈ Z} = z∈Z B z .
We also define, for any Z ⊂ P, the maximal amount of flow coming in and out through the n-links by

P in (Z) = p ∈Z,q∈Z q∈N (p) c(p, q), P out (Z) = p∈Z,q ∈Z q∈N (p) c(p, q).
Finally, we define the maximum amount of flow passing through the t-links and the flow orientation by

A(Z) = p∈Z |c(p)|, O(Z) = p∈Z sign(c(p)),
where sign(t) = 1 if t > 0, 0 if t = 0 and -1 otherwise. Let B ⊂ Z d , in order to build G ′ , we remove from the nodes of G any Z ⊂ P such that either

O( Z B ) = +| Z B | and A( Z B \ Z) ≥ P out ( Z B ), or O( Z B ) = -| Z B | and A( Z B \ Z) ≥ P in ( Z B ). (2)
As an illustration of those conditions, notice for instance that the last condition implies that all the flow that might come in the region Z B comes from its boundary and can be absorbed by the band Z B \ Z. Building such sets Z is done by testing each individual pixels of Z. In order to do so, we establish (in a forthcoming paper) that the conjunction of conditions (2) for every z ∈ Z implies (2) for Z. Considering B, a square window of size (2r + 1) (r > 0) centered at the origin, a more conservative test for

z ∈ Z is    c(q) ≥ +δ ∀q ∈ B z or c(q) ≤ -δ ∀q ∈ B z , (3)
where δ = P (B) (2r+1) 2 -1 , with P (B) = max(|{(p, q), p ∈ Z, q ∈ Z and p ∈ N (q)}|, |{(p, q), p ∈ Z, q ∈ Z and q ∈ N (p)}|).

If all the capacities of the n-links are smaller than 1 (which is true for most interesting energies) and (3) holds, the inegality (2) holds for Z = {z}. Then, G ′ is determined by the set of nodes V ′ = {p ∈ P not satisfying (3)}∪{s, t}. We have theoretical and empirical evidence suggesting that this graph reduction provides an exact solution. Morever, the condition ( 3) is simple and a straightforward implementation has a worst-case complexity of O(|B|). Decomposing this test along the d dimensions yields an algorithm with complexity O(1), except for image borders.

Experimental results

This section compares the performance of standard graph cuts and our method in terms of speed and memory with the Boykov/Jolly [START_REF] Boykov | Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images[END_REF] energy model. Experiments are performed on an Athlon Dual Core 6000+ 3GHz with 2GB RAM for segmenting 2D/ 3D images in connectivity 1. Times are averaged over 10 runs.

Introduced in [START_REF] Boykov | Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images[END_REF], this model has quickly become a standard in applications. From a user viewpoint, it consists of marking some parts of the image as "object" and "background". For more information, we refer the reader to [START_REF] Boykov | Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images[END_REF]. These results compare time and memory usage between standard graph cuts and our method for segmenting 3 real images. The second image represents an abdominal CT with a pulmonary tumor while the third image shows brain cells.

In these experiments, the model's parameters are optimized for better visualization. The window radius is chosen such that memory usage is minimized. For all images, the amount of allocated memory for the graph is reduced by a factor ranging from 3.8x to 9.4x. For the first image, our algorithm is 1.6x faster and require 8x less memory while getting exactly the same result. Moreover, altough the graphs induced by the volumes "ct-thorax" and "cells" do not fit in memory (estimated values) when no reduction is performed, we observe that our algorithm is able to segment them in less than 1 minute. We can notice that we obtain the same conclusions for all the images tested (more than 100).

Also, we summarize

  the capacities of the t-links at any node p ∈ P by c(p) = c(s, p)-c(p, t). For any B ⊂ Z d and p ∈ P, we denote by B p the set translation of B by the point p: B p = {b + p | b ∈ B}. Moreover, for Z ⊂ P and B ⊂ Z d , we define the dilation of Z by B as:

Typically, larger neighborhood systems yield better results but increase running times and memory consumptions.

An implementation of the max-flow algorithm is freely available at http://www.cs.cornell.edu/People/vnk/software.html