O Lezoray

C Meurie
email: cyril.meurie@inrets.fr

A Elmoataz

Graph-based ordering scheme for color image filtering

Keywords: Ordering of vectors, color, filtering, mathematical morphology, median, graph, Hamiltonian path

This paper presents a graph-based ordering scheme of color vectors. A complete graph is defined over a filter window and its structure is analyzed to construct an ordering of color vectors. This graph-based ordering is constructed by finding a Hamiltonian path across the color vectors of a filter window by a two-step algorithm. The first step extracts, by decimating a minimum spanning tree, the extreme values of the color set. These extreme values are considered as the infimum and the supremum of the set of color vectors. The second step builds an ordering by constructing a Hamiltonian path among the vectors of color vectors, starting from the infimum and ending at the supremum. The properties of the proposed graph-based ordering of vectors are detailed. Several experiments are conducted to assess its filtering abilities for morphological and median filtering.

Introduction

Color image processing is a very important area of research which belongs to the processing of multichannel images [START_REF] Lukac | Color Image Processing: Methods and Applications[END_REF][START_REF] Pitas | Multivariate ordering in color image filtering[END_REF][START_REF] Plataniotis | Color Image Processing and Applications[END_REF] . A large number of nonlinear image filters have been initially developed for the processing of gray-scale images. It is now admitted that a direct extension of these algorithms to color images by a componentwise approach is not suitable since it neglects the correlation that exists between the color channels of a natural image. Moreover, this can produce color shifts or other artifacts [START_REF] Lambert | Filtering and segmentation: the specificity of color images[END_REF] . To address this problem, a vectorial processing of color images is preferable.

Nonlinear filters such as median or morphological filters require the pixels contained in a filter window to be ordered. Since there is no natural ordering for vector data, their extension to color images is not straightforward. The definition of an ordering of color vectors is therefore of high interest for processing color images [START_REF] Lukac | Color Image Processing: Methods and Applications[END_REF][START_REF] Lukac | Vector filtering for color imaging[END_REF] since it can be used for image filtering, edge detection, spatial interpolation, etc [START_REF] Lukac | Color Image Processing: Methods and Applications[END_REF] .

In this paper, a new graph-based approach to the ordering of color vectors is presented. A complete graph is defined over a filter window and its structure is analyzed to construct an ordering of color vectors. This graph-based ordering is constructed by finding a Hamiltonian path [START_REF] Diestel | Graph Theory[END_REF] across the color vectors of a filter window by a two-step algorithm. The first step extracts, by decimating a minimum spanning tree, the extreme values of the color set. These extreme values are considered as the infimum and the supremum of the set of color vectors. The second step builds an ordering by constructing a Hamiltonian path among the vectors of color vectors, starting from the infimum and ending at the supremum.

The rest of this paper is organized as follows. In the next section, an overview of multivariate ordering of vectors is presented and various schemes for ordering vectors are described. In Section 3, these schemes are compared according to their abilities for color morphological or median filtering. In Section 4, after having recalled basic definitions on weighted graphs, the proposed graph-based ordering of color vectors is described. Results and discussion are presented in Section 5. In the final section, some concluding remarks are made.

Multivariate ordering of vectors

To process multivariate data such as color vectors, the three main multivariate orderings of vectors are the pre-order, the partial order and the total order. Before the description of these orderings, we provide definitions of the relations used to characterize an ordering of vectors [START_REF] Hanbury | Mathematical Morphology on the Unit Circle: with applications to hues and to oriented textures[END_REF][START_REF] Vertan | A clustering approach to vector mathematical morphology[END_REF][START_REF] Lezoray | A graph approach to color mathematical morphology[END_REF] . Definition 1. Let R be a binary relation on a given set A.

• R is reflexive if ∀x ∈ A, xRx, • R is transitive if ∀x, y, z ∈ A, xRy and yRz ⇒ xRz, • R is anti-symmetric if ∀x, y ∈ A, xRy and yRx ⇒ x = y. Definition 2. A binary relation R on a set A is a pre-order if R is reflexive and transitive. Definition 3. A binary relation R on a set A is a partial order if R is reflexive, transitive and anti-symmetric. Definition 4. A binary relation R on a set A is a total order if R is a partial order and if ∀x, y ∈ A, xRy or yRx.

Therefore, a complete ordering on a set A is an ordering where any pair of vectors can be ordered (e.g. the binary relation ≤ on R). A multivariate image can be represented by the mapping Z l → R p where l is the image dimension and p the number of channels. Let W = {x k ∈ Z l ; k = 1, 2, . . . , N } design a filter window of finite length N where x 1 determines the position of the filter window (i.e. x 1 occupies the central location in the filter window). From W one therefore gets a set

{x 1 , x 2 , • • • , x N } of N p-dimensional vectors: x i = {x 1 i , x 2 i , • • • , x p i }, x i ∈ R p .
A classical way to define an ordering relation between vectors is to use a transform 9 h from R p into R q followed by the natural ordering on each dimension of R q . With h : R p → R q , and x → h(x) then ∀(

x i , x j ) ∈ R p × R p , x i ≤ x j ⇔ h(x i ) ≤ h(x j ).
When h is bijective, this corresponds to defining a space filling curve that goes through each point of the R p space just once and thus induces a total ordering. According to these definitions, we can review some several possible types of multivariate orderings of vectors as it has been done by Barnett 5 . The ones we present are the marginal, the reduced and the conditional orderings. We recall their principles here.

• In the marginal ordering, vectors are ordered in each dimension independently (q = p, h = Identity). This order is a partial ordering and it is now admitted that this approach is not satisfactory since it can produce new vectors which do not belong to the initial set. • In the reduced ordering, q = 1 and h denotes a chosen distance metric which differentiates the possible reduced ordering schemes. Each vector is reduced to a scalar and the vector data are sorted according to the obtained scalar values. A classical way to define the h transform is to use a cumulative distance. This type of ordering is very popular and is used for color vector median filters for instance [START_REF] Lukac | Color Image Processing: Methods and Applications[END_REF][START_REF] Lukac | A taxonomy of color image filtering and enhancement solutions[END_REF] . This order is a pre-order. • In the conditional (or lexicographic) ordering, the vectors are ordered according to a hierarchical order of the components. Therefore, q = 1 and h : R p → R, x i → x k i with k adaptively determined. For two vectors x i and x j , one has:

x i ≤ x j    x 1 i < x 1 j , or x 1 i = x 1 j , and, x 2 i < x 2 j or • • • x 1 i = x 1 j , and, x 2 i = x 2 j • • • x p i < x p j
This ordering is a total ordering of vectors but it introduces a strong dissymmetry between the components.

Since processing multivariate data is of interest in many research areas (e.g. color or multi spectral image processing), a wide range of different schemes for ordering vectors can be found in literature [START_REF] Angulo | Unified morphological color processing framework in a lum/sat/hue representation[END_REF][START_REF] Astola | Vector median filters[END_REF][START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF][START_REF] Comer | Morphological operations for colour image processing[END_REF][START_REF] Hanbury | Mathematical morphology in the HLS colour space[END_REF][START_REF] Iwanowski | Morphological interpolation and color images[END_REF][START_REF] Köppen | Pareto-morphology for color image processing[END_REF][START_REF] Louverdis | A new approach to morphological color image processing[END_REF][START_REF] Ortiz | Comparative study of vectorial morphological operations in different color spaces[END_REF][START_REF] Ortiz | Use of the hue/saturation/intensity color spaces to the morphological[END_REF][START_REF] Peters | Mathematical morphology for angle valued images[END_REF][START_REF] Pitas | Multivariate ordering in color image filtering[END_REF][START_REF] Talbot | Complete ordering and multivariate mathematical[END_REF][START_REF] Tsalides | Vector ordering and morphological operations for colour image processing[END_REF][START_REF] Vardavoulia | A new vector median filter for colour image processing[END_REF] . Most of these works rely on modified lexicographic ordering schemes since this is the only true total ordering relation commonly used in literature. However, another total ordering of color vectors, called the bit-mixing ordering, has been proposed by Chanussot [START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF] . The bit-mixing is based on the binary representation of each component of the considered vector x. If the p components of x are coded with b bits each, the p • b available bits are blended together to build the p • b bits long scalar value h(x) [START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF][START_REF] Lambert | Extending mathematical morphology to color image processing[END_REF] .

The considered transform h can then be written as follows:

h(x) = b k=1 2 p•(b-k) p i=1 2 (p-i) x i⊲k
where x i⊲k denotes the k th bit of the i th component of x. In the case of color images, p = 3, b = 8. In the context of space filling-curves, it is worth mentioning the works of Regazonni [START_REF] Regazzoni | A new approach to vector median filtering based on space filling curves[END_REF][START_REF] Stringa | A classical morphological approach to color image filtering based on space filling curves[END_REF] where a given curve is defined for median filtering. We do not consider that issue of constructing a space filling curve on all the space R p . We will see in Section 4.2 that an equivalent notion (the Hamiltonian path) can be used to construct an ordering of color vectors.

Ordering and filtering

One very important field of application of multivariate image processing and in particular color images is filtering [START_REF] Pitas | Multivariate ordering in color image filtering[END_REF][START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF][START_REF] Lukac | Color Image Processing: Methods and Applications[END_REF][START_REF] Plataniotis | Color Image Processing and Applications[END_REF] . In this section, we focus on the link between ordering color vectors and filtering (morphological [START_REF] Ronse | Why mathematical mophology needs complete lattices[END_REF][START_REF] Goutsias | Morphological operators for image sequences[END_REF] or median [START_REF] Lukac | Vector filtering for color imaging[END_REF][START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF] ). Morphological or median filters are usually based on specific orderings of color vectors which have advantages and disadvantages. We give details about both in the sequel.

Vector morphological filters

Mathematical morphology is a nonlinear approach to image processing which relies on a fundamental structure, the complete lattice L. A complete lattice is defined such that 31 :

• An ordering relation ≤ is defined over L, • For every finite subset K of L, there exists a supremum ∨K and an infimum ∧K.

A marginal approach can be used, but a purely vectorial approach is preferable. Indeed, with a marginal approach, the supremum and the infimum do not always belong to the lattice and false colors can appear [START_REF] Chanussot | Total ordering based on space filling curves for multivalued morphology[END_REF] . Another constraint to the definition of morphological filters is therefore to impose that the supremum and the infimum of a given set do belong to this one. Total orderings are thus usually considered for color morphological operators. In this frame, the main orderings of color vectors are the lexicographic ordering [START_REF] Hanbury | Mathematical morphology in the HLS colour space[END_REF][START_REF] Angulo | Unified morphological color processing framework in a lum/sat/hue representation[END_REF] and the bit-mixing ordering 6 which are total orderings and which both fulfill all the requirements of the complete lattice L.

The lexicographic ordering is however strongly dissymmetric and most of the ordering of color vectors decisions are taken on the level of the first component which implies the attribution of a priority to the components. This provides operators the behavior of which is not homogeneous in a color space. The choice of the priority component being difficult [START_REF] Angulo | Morphological coding of color images by vector connected filters[END_REF][START_REF] Ortiz | Comparative study of vectorial morphological operations in different color spaces[END_REF][START_REF] Angulo | Morphological color processing based on distances. Application to color denoising and enhancement by centre and contrast operators[END_REF] , this can be alleviated by considering perceptual color spaces based on Luminance/Hue/Saturation [START_REF] Angulo | Unified morphological color processing framework in a lum/sat/hue representation[END_REF][START_REF] Louverdis | A new approach to morphological color image processing[END_REF] where the ordering is more natural from a human perception point of view. Even if this ordering has drawbacks, this is the most commonly used and it has been studied by several authors for morphological filtering [START_REF] Iwanowski | Morphological interpolation and color images[END_REF][START_REF] Louverdis | A new approach to morphological color image processing[END_REF][START_REF] Ortiz | Use of the hue/saturation/intensity color spaces to the morphological[END_REF][START_REF] Peters | Mathematical morphology for angle valued images[END_REF][START_REF] Talbot | Complete ordering and multivariate mathematical[END_REF][START_REF] Tsalides | Vector ordering and morphological operations for colour image processing[END_REF][START_REF] Vardavoulia | A new vector median filter for colour image processing[END_REF] .

The bit-mixing ordering enables to limit the dissymmetry between the components. However, since it is based on an interlacing of bits, it is reduced to operate in color spaces where components are described by integers, which is not the case of a lot of color spaces. The bit-mixing ordering was therefore mainly conceived to operate in the RGB color space.

Once an ordering of color vectors is defined, one can apply the two main morphological operations that is to say the erosion ǫ and the dilatation δ. Regardless the ordering scheme, the color erosion (ǫ) and dilatation (δ) over a filter window W centered on x are given by: ǫ(x) = {y : y = ∧W } and δ(x) = {y : y = ∨W } where ∨ and ∧ are respectively the supremum and the infimum of a set. Other morphological operators can be obtained by composition of these elementary operations: the opening (γ = δǫ) and the closing (ϕ = ǫδ) for instance.

Vector Median Filters

The most popular vector filter is the Vector Median Filter (VMF) [START_REF] Lukac | A taxonomy of color image filtering and enhancement solutions[END_REF] introduced by Astola [START_REF] Astola | Vector median filters[END_REF] . We do not detail the state of the art on vector median filters since it is out of the scope of this paper and excellent reviews can be found in [START_REF] Lukac | Color Image Processing: Methods and Applications[END_REF][START_REF] Lukac | A taxonomy of color image filtering and enhancement solutions[END_REF][START_REF] Lukac | Vector filtering for color imaging[END_REF][START_REF] Plataniotis | Color Image Processing and Applications[END_REF] . Such vector filters are based on the ordering of vectors in a filter window W . Each vector x k ∈ W is associated with a distance measure:

R k = N i=1 x k -x i γ for k = 1, 2, . . . , N where x k -x i γ quantifies the Minkowski distance between two vectors x k -x j γ = p i=1 x i k -x i j γ 1 γ
where γ designs the chosen norm which is usually the Euclidean one (γ = 2). The VMF output is the sample x (1) associated with the minimal aggregated distance:

x (1) = arg min xi∈W R i
According to the distance between two vectors, it is possible to differentiate the techniques operating on the vector distance domain [START_REF] Lukac | A taxonomy of color image filtering and enhancement solutions[END_REF] , the angular domain [START_REF] Trahanias | Directional processing of color images: Theory and experimental results[END_REF] or their combinations 13 .

Discussion

The first observation is that reduced orderings used for vector median filters are not adapted to morphological filtering since they do not define a complete lattice. They are however adapted to any type of multivariate image and to any color space. The second observation is that the ordering schemes used for morphological processing are usually total orderings, but they have the main drawback of being suited to only one given color space: RGB for the bit-mixing ordering and IHSL [START_REF] Hanbury | Mathematical morphology in the HLS colour space[END_REF] for the lexicographic ordering. Moreover, these ordering schemes cannot be used to perform morphological operations on multivariate images. For the bit-mixing ordering, we are limited to integers and to the number of bits available to code an integer. For the lexicographic ordering, the dominant role of the first component is difficult to overcome except in a perceptual color space such as IHSL. The final observation is that all the usual orderings of vectors have disadvantages; we would like to have one ordering of vectors the basis of which is enough general to permit morphological and median filtering on vectors of arbitrary dimensions.

Graph-based Ordering

In this section, we propose a graph-based alternative to the classical approaches to ordering the vectors of color vectors.

Preliminaries on graphs

We provide some basic definitions on graph theory [START_REF] Diestel | Graph Theory[END_REF] . A graph G is a couple G = (V, E) where V is a finite set of vertices and E is a subset

E ⊆ V × V .
The elements of V are the vertices of the graph and the elements of E are the edges of the graph. Two vertices u and v in a graph are adjacent if the edge (u, v) exists in E, the two vertices being then called neighbor vertices.

The degree δ(v) of a vertex v is the number of edges incident to the vertex. δ : V → N is defined as δ(v) = |u ∼ v| where | • | denotes the cardinal of a set. The relation u ∼ v denotes the set of vertices u connected to the vertex v via the edges (u, v) ∈ E: u is a neighbor adjacent vertex of v. If a vertex has a unity degree, it is called a leaf.

A path p is a set of vertices p = (v 1 , v 2 , • • • , v k ) such
as there is an edge for each two successive vertices of the path: ∀i ∈ [1, k[, the edge (v i , v i+1 ) ∈ E. The length of a path corresponds to its number of edges. A path is simple if an edge is covered only once. A path is Hamiltonian if it uses all the vertices exactly once (this problem is NP-complete). A complete graph is a graph where an edge connects every pair of vertices. A complete graph with n vertices has n(n -1)/2 edges and the degree of each vertex is (n -1).

A graph is connected when for every pair of vertices u and v there is a path in which v 1 = u and v k = v. A graph is undirected when the set of edges is symmetric, i.e., for each edge (u, v) ∈ E, we have also (v, u) ∈ E. In the rest of this paper, we consider only simple graphs for which maximum one edge can link two vertices. These simple graphs are always assumed to be connected and undirected [START_REF] Diestel | Graph Theory[END_REF] . A graph, as defined above, is said to be weighted if it is associated with a weight function

w : E → R + satisfying w(u, v) > 0 if (u, v) ∈ E, w(u, v) = 0 if (u, v) /
∈ E and w(u, v) = w(v, u) for all edges in E since we consider undirected graphs.

We can now define the space of functions on graphs. Let H(V ) denote the Hilbert space of real-valued functions on vertices, in which each f : V → R + assigns a real value f (v) to each vertex v. A function f in H(V ) can be thought as a column vector in R |V | . Similarly, one can define H(E) the space of real-valued functions on edges, in which each one g : E → R + assigns a real value to each edge e.

A tree is a connected acyclic simple graph. A spanning tree of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. A minimum spanning tree (MST) is then a spanning tree with weight less than the weight of every other spanning tree. Therefore, a minimum spanning tree T (G) of a graph G is a weighted connected graph T (G) = (V ′ , E ′ ) where the sum of the weights

(u,v)∈E ′ w(u, v) is minimum.
For a graph G of n vertices, its MST T (G) has exactly (n -1) edges. The MST can be efficiently computed in O(|E|log|V |) using Prim's algorithm with appropriate data structures.

Graphs and Ordering of vectors

As previously mentioned, there is an equivalence: (total ordering on R p )⇔(bijective application h : R p → R)⇔(space filling curve in R p ) We recall that a space filling curve is a curve that goes through each point of the space just once. Therefore, if the space is represented by a connected graph, we also have the equivalence: (space filling curve in R p )⇔(Hamiltonian path on R p ). Usual definitions of space filling curves [START_REF] Stringa | A classical morphological approach to color image filtering based on space filling curves[END_REF][START_REF] Regazzoni | A new approach to vector median filtering based on space filling curves[END_REF] in R p use curves (e.g. a Peano scan) which are independent of the image spatial structure and therefore they do not respect topology. Indeed, finding an optimal Hamiltonian path is too difficult (NPcomplete) to be directly solved on R p : for a graph of n vertices, there are (n -1)! possible Hamiltonian paths. In this paper, we take a Hamiltonian path point of view of the ordering of vectors. However, we propose to dynamically construct such a Hamiltonian path on a filter window W rather on the complete space R p .

To a given filter window W , we can associate a complete graph the vertices of which correspond to the vectors of W . This corresponds to a function f ∈ H(V ), f : V → W which associates a color vector x ∈ W to each vertex. Similarly, we can associate a weight to each edge of the graph, w ∈ H(E), w :

E → R + . Classically, we consider w(u, v) = f (u) -f (v) 2 .
In this paper, we just focus on color images (p = 3) but the principle remains the same for higher dimensions. To illustrate our approach, we use a reference image (figure 1, a painting by Joan Miro called "The singer") in color mathematical morphology which was introduced by Hanbury 2,11,17 . In the sequel, we illustrate our new graph-based ordering approach of color vectors on a predefined filter window W of this image (specified by the zoomed and surrounded area in the top right of figure 1).

Inf and Sup extraction

As previously mentioned, to define a Hamiltonian path over a filter window W , we consider the complete graph G 0 over W . Since it is difficult to find an optimal Hamiltonian path on G 0 among all the (|W | -1)! different possibilities, we propose to approximate this path. Instead of trying to directly define the Hamiltonian path, we begin by extracting its bounds (∧ and ∨).

Let T 0 = T (G 0 ) denote the MST of G 0 . An MST being a generalization to higher dimensions of a one-dimension sorted list [START_REF] Ch | Color edge detection using the minimal spanning tree[END_REF] , we can use its structure to find candidate bounds of the Hamiltonian path. A vertex v of a Hamiltonian path is one of its bounds if δ(v) = 1: it is a leaf. We use this principle to extract them. Let N 0 = {u|δ(u) = 1, u ∈ T 0 } denote the leaves of T 0 . The vertices in N 0 are the only candidates for bounds of the Hamiltonian path. Since most of the time |N 0 | > 2, N 0 has to be reduced to only two elements. To that aim, we iterate the same process on the complete graph constructed over the vertices of N 0 until |N i | = 2 with i the iteration number.

To sum it up, to extract the bounds of a Hamiltonian path, the principle can be described as follows:

i ← 0 Construct the complete graph G i over the filter window W Repeat T i = T (G i ) N i = {u|δ(u) = 1, u ∈ T i } Construct the complete graph G i+1 over the vertices of N i i ← i + 1 until (|N i-1 | = 2) T i = G i N i = {u ∈ T i }
At the end of the process, N i = {u, v} contains two vertices considered as bounds of the Hamiltonian path. However, one still has to define which one of these two vertices is the ∨ (respectively the ∧). The ∧ is identified as the closest vertice to a reference color x ref [START_REF] Hanbury | Mathematical morphology in the HLS colour space[END_REF][START_REF] Soria-Frisch | The fuzzy integral as similarity measure for a new color morphology[END_REF] which is usually black:

∨ = arg max v∈Ni f (v), x ref 2 and ∧ = arg min v∈Ni f (v), x ref 2
The use of a reference color is not new and was proposed by Soria-Frisch in [START_REF] Soria-Frisch | The fuzzy integral as similarity measure for a new color morphology[END_REF] and Hanbury for the IHSL color space [START_REF] Hanbury | Mathematical morphology in the HLS colour space[END_REF] .

Computing the MST of a graph is O(|E|log|V |) and O(N 2 logN ) on a complete graph since |V | = |W | = N . One then iterates the process on the complete graph built from the leaves of the MST. There is no bound on the number of leaves of an MST for p > 2 (see in [START_REF] Steele | On the number of leaves of a euclidean minimal spanning tree[END_REF] ), we therefore have determined an experimental upper bound of this number. For a complete graph built over a filter window of size N , an upper bound of the number of leaves of the MST is ⌈N/2⌉ where ⌈•⌉ denotes the smallest integer upper than the operand. This means that, at each iteration, the number of surviving vertices is divided by two (this is an upper bound). One then can prove that the complexity of this step is O( N 3 2 logN ).

(a) G 0 (b) T 0 (c) G 1 (d) T 1 (e) G 2

Ordering of vectors construction

Once the two bounds of the Hamiltonian path have been determined, the complete Hamiltonian path can be constructed. On the filter window W under consideration, a Hamiltonian path p = (v 1 , v 2 , • • • , v k ) must respect the following properties:

• The length of p is |W | = N , • Its bounds are leaves i.e. δ(v 1 ) = δ(v k ) = 1, • v 1 = ∧ and v k = ∨, • The other vertices have a degree of 2: ∀v ∈ {v 2 , • • • , v k-1 }, δ(v) = 2.
The construction of the Hamiltonian path we propose is based on the nearest neighbor principle on the initial complete graph G 0 . To determine the nearest neighbor u of a vertex v we consider the weight of the edge w(u, v) but also the saliency of the neighbor u. The saliency of a vertex quantifies its global importance in the set of MST which where generated during the inf and sup extraction. It is defined as follows:

∆(v) = imax i=0 (i + 1) • δ(T i , v) where δ(T i , v) = δ(v), v ∈ T i
where i corresponds to an iteration number in the Hamiltonian path bounds extraction and i max the total number of iterations. The bounds v 1 and v N have the highest saliences. Otherwise, the saliency of a vertex is all the more important when it survives in the successive T i . For instance, the saliency of the top left pixel v j of the filter window in figure 2

(a) is ∆(v j ) = 1 • δ(T 0 , v j ) + 2 • δ(T 1 , v j ) + 3 • δ(T 2 , v j ) = 1 • 1 + 2 • 1 + 3 • 1 = 6
The construction of the Hamiltonian path is O(N 2 ) and can then be summarized as follows:

       v 1 = ∧ and v N = ∨ v j+1 = arg min u∼vj u / ∈{v1,••• ,vj } (w uvj ∆(u)) ∀j = 1, • • • , (N -2)
Figure 3 illustrates the construction of the ordering of vectors of W as a Hamiltonian path: on the complete graph G 0 (Figure 3

Evaluation and discussion

In this section, we evaluate the four orderings of vectors detailed in the previous sections, namely the reduced ordering based on distances, the lexicographic ordering, the bit mixing ordering and the proposed graph-based ordering.

Ordering schemes comparison

First, to see the influence of each ordering scheme, we apply each of them on the filter window W of figure 1. Results are shown in figure 4. The first row presents the filter window W . Other rows show the results for the different orderings of vectors.

As it was previously noticed, the marginal approach creates some color artifacts Fig. 4. Comparison of several schemes for ordering vectors on a filter window (from figure 1). Each color is indexed in the filter window (top row). These indexes are superimposed for all the ordering schemes (-indicates that the color vector does not belong to the filter window).

(appearance of false colors). One can however note that this is not visually obvious.

For the lexicographic ordering, several permutations of the color channels have been studied to assess the dominant role of the first channel. In this case, considering the Green channel as dominant provides better results but this might not be the case for another filter window. For the reduced ordering, the chosen distance between vectors has high influence on the final ordering: some visually close color can be far away one from the other in the ordering. The bit-mixing ordering is very close to the lexicographic RGB ordering which assesses the fact that the way the bits are mixed still involves dissimetry. The graph-based ordering is visually satisfying and very close to the lexicographic GRB ordering (only two permutations).

We now analyze the computational complexity of the different ordering schemes for a given filtering window W of size N to obtain a complete ordering of the vectors. With usual sorting algorithms, the lexicographic ordering computational complexity is O(N 2 ) and the bit-mixing ordering computational complexity is O(N 2 ). The reduced ordering based on distances computational complexity is O(N 2 ). The graph-based ordering computational complexity is O( N 3 2 logN ).

Morphological Filtering

In this subsection, we only consider the lexicographic, the bit mixing and the graphbased orderings for morphological filtering. Figure 5 presents a comparison of the considered orderings of vectors for the two main morphological operations: the erosion (ǫ) and the dilatation (δ).

The considered color space is RGB, the filter window is a 3 × 3 square and the reference color for the graph-based ordering is black. In figure 5, few differences can be noticed between the three orderings of vectors. For the erosion the results look similar for the three orderings except for the lexicographic ordering in the red areas of the image. The disadvantages of the lexicographic ordering which gives a dominant role to the first component is well observed in red areas of figure 5(a). The same observation can be made for the lexicographic dilatation in figure 5(d). The bit mixing ordering performs good for the erosion but it is less good than the other two orderings for the dilatation: the bit mixing is very sensitive to the small color variations in the background of the image.

The reference color used in the graph-based ordering has an influence on the determination of the ∨ and the ∧. Usually one will take black as a reference color, however for some special considerations, it might be interesting to use another color. We have performed an erosion in the RGB color space with different reference colors: black, red, green, blue and yellow. All the results are presented in figure 6(a)-(e), each column of the first row corresponds to a reference color. The first row gives an erosion of figure 1 with the five different reference colors. To illustrate the differences between the obtained results, we first computed the difference between the original image and black erosion (figure 6(f)). This gives an idea of the modifications made by the erosion in the image. To see the influence of the reference color, the differences between black erosion and the other reference color erosions are computed. The differences between the obtained erosions are given in figure 6(g)-(j). As expected, changing the reference color changes the way the erosion acts on some colors since it favors the colors close to the reference: look at the eye of the singer for the red erosion and the yellow elongated pattern (bottom right) for the blue erosion. This becomes quite clear for the result of yellow erosion: the majority of the colors of the image are closer to yellow than to black and this last color tends to disappear in yellow erosion.

Median Filtering

In this subsection, we consider the abilities of the different orderings for median filtering. The aim here is not to conceive an efficient noise filtering operator but to study the influence of the ordering on median filtering. For comparison, the reduced ordering based on distances is considered as the reference. This enables us to perform filtering with VMF, BVDF or DDF operators. To compare the different orderings of vectors, a standard image is considered and is presented in figure 7 (similar results were obtained on other standard images). The experiments were conducted in the RGB color space with three different orderings: reduced ordering based on distances, graph ordering and bit mixing ordering. The original test images have been corrupted by impulse noise expressed as 19 :

x i,j = v with probability p v o i,j with probability 1p v where i, j characterize the sample position, o i,j is the original sample, x i,j represents the sample from the noisy image, p v is a corruption probability and v = (v R , v G , v B ) is a noise vector of intensity random values. For the experiments, the considered degree of the impulse noise corruption p v has ranged from 0% to 30%. To evaluate the achieved results, objective criteria as Mean Absolute Error (MAE), Mean Square Error (MSE) and Normalized Color Differece (NCD) have been used [START_REF] Lukac | Adaptive vector median filtering[END_REF] . Figure 8 presents the results of the first conducted experimentation with a VMF filtering for the different orderings. Each figure presents an objective criterion according to the level of noise corrupting the image. It is easy to see that the orderings of vectors can be classified in the following way according to their impulse noise median filtering abilities: reduced ordering based on distances, graph ordering, bit mixing ordering. The bit mixing is the least suitable ordering and the graph ordering has a behavior similar to reduced ordering for small quantities of impulse noise.

We have led the same experiments with a BVDF filtering for the reduced ordering based on distances and the graph ordering and we got the same type of curves (not shown here for the sake of brevity) than for the VMF assessing the superiority of the reduced ordering. It is worth noting that to obtain a BVDF with the graph ordering, one has only to change the weighting of the edges between the vertices of the graph: w(u, v) = θ(f (u), (v)) where θ(x i , x j ) represents the angle between the two color vectors x i and x j . We then compare the DDF filtering scheme with a reduced ordering and a graph ordering (w(u, v) = θ(f (u), (v)) f (u)f (v) 2 ). Results are shown in figure 9. One can see on all the curves that, for the DDF filtering, the graph ordering always provides better results than the reduced ordering. This comes to the conclusion that the graph ordering we propose in this paper is suitable for median filtering but the weights of the edges in the initial graph have to be carefully determined. This brings our graph ordering approach closer to the problem of the determination of weights in weighted median filtering [START_REF] Lukac | Selection weighted vector directional filters[END_REF][START_REF] Lukac | Generalized selection weighted vector filters[END_REF] .

To give a visual illustration of the differences between the different orderings of vectors, figure 10 The best visual results, as expected from the curves in figures 8 and 9, are obtained by the VMF with reduced ordering. One can also notice the better performance of graph ordering while using both distance and direction for weighting the edges of the graph.

As for morphological filtering, the reference color x ref used in the differentiation of the ∨ and the ∧ can have some influence on median filtering. Figure 11 graph-based ordering and different reference colors among red, green, blue, cyan, yellow, purple, black and white. This influence is studied in the presence of impulse noise. As shown in figure 11, the reference color does not have a lot of influence on the results and black as color reference is sufficient in most of the cases. As noise increases the best reference color can change (cyan in this case). However, changing the reference color still does not make it possible to outperform the vector median filtering with reduced ordering based on distances.

Conclusion

A new ordering of vectors based on the construction of a Hamiltonian path across the pixels of a filtering window has been proposed. A Hamiltonian path is equivalent to a space filling curve and we dynamically construct such a path on a given filter window. The proposed method is based on a two-step analysis of the color vectors within a filter window. The first step extracts the two extreme vectors of a set of color vectors. Starting from the minimum spanning tree of a complete graph defined on a filter window, an iterative selection of candidate vectors is performed. The latter is based on the degree of the vertices of the graph. From these two vectors, a Hamiltonian path is constructed on the complete graph representing the filter window. The proposed ordering has the advantage of being directly applicable to vectors of any dimensions and is suited for morphological or median filtering. However, the filtering abilities of a median filter based on the proposed graphordering are less efficient those of a classical vector median filter. The proposed ordering of vectors opens a new way of ordering color vectors via graph-theoretical algorithms. Future research will be about the reduction of the complexity of the proposed vector ordering because it is higher than that of usual algorithms.

Fig. 1 .

 1 Fig. 1. Test image for morphological filtering operations.

Fig. 2 .

 2 Fig. 2. The graphs G i and T i in the different steps of the algorithm for Hamiltonian path bounds extraction. For each T i , the vertices degrees are superimposed. T 2 is not shown here.

Figure 2

 2 Figure 2 presents the different steps of the algorithm. The complete graph G 0 is constructed over the filter window W (Figure 2(a)) and its MST T 0 is computed (Figure 2(b)). A new complete graph G 1 Figure 2(c)) is constructed over the leaves of T 0 and its MST T 1 is computed (Figure 2(d)). Finally, A complete graph G 2 of two vertices is obtained (Figure 2(e)). With x ref as black, the ∨ is the top left pixel of W and ∧ the bottom middle one.

  Figure 3 illustrates the construction of the ordering of vectors of W as a Hamiltonian path: on the complete graph G 0 (Figure 3(a), with vertices saliences superimposed), one obtains the path depicted by figure 3(b).

Fig. 3 .

 3 Fig. 3. (a) The graph G 0 with vertices saliences ∆(v) superimposed and (b) the constructed Hamiltonian path.

  Fig. 5. ǫ and δ with different orderings on the figure 1.

Fig. 6 .

 6 Fig. 6. Influence of the reference color on the graph ordering for an erosion.

Fig. 7 .

 7 Fig. 7. Test color image.

  presents a zoomed area of the Parrots image (figure 7(c)). The zoomed area (figure 10(e)) has been corrupted by 15% of impulse noise (figure 10(a)) and filtered first by a VMF with reduced ordering (figure 10(b)), graph ordering (figure 10(c)), or bit mixing ordering (figure 10(d)) and then by a DDF with reduced ordering (figure 10(f)) or graph ordering (figure 10(g)).

Fig. 8 .

 8 Fig. 8. VMF Error Measures (MSE, MAE and NCD) with different orderings having the respective following curve colors: blue for bit mixing, green for graph and red for reduced.

Fig. 9 .

 9 Fig. 9. DDF Error Measures (MSE, MAE and NCD) with different orderings.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. 15% impulse noise filtered output with a VMF and a DDF and different vector ordering schemes.

Acknowledgements

This work was supported by the University of Caen Low Normandy under grants of FEDER and FNADT funds and by the ANR foundation under grant ANR-06-MDCA-008-01/FOGRIMMI


Christophe Charrier
email: christophe.charrier@unicaen.fr

Gilles Lebrun
email: gilles.lebrun@unicaen.fr

Olivier Lezoray
email: olivier.lezoray@unicaen.fr

A color image quality assessment using a reduced-reference image machine learning expert

Keywords: Machine Learning, HVS, Classification, Image quality

INTRODUCTION

In language abuse, there often is an amalgam between the terms quality and fidelity. For the Artist, the concept of quality would be what the concept of fidelity would be to the forger. The Artist generally works starting from the concepts, impressions related to their social environment and/or professional and places himself in an existing artistic current(relation Master-student) or in the new current that he creates. The works carried out are thus regarded as original, and the experts speak about the quality of the works. Behind this approach, one realizes that to the word quality, the concept of originality is associated. Who has never found themselves on front of a work which left him perplex while his neighbor was filled with wonder? It is enough to saunter in the museums to see this phenomenon. Thus one qualifies the quality of a work according to his conscience and his personal sensitivity presets from his economic and social environment. Thus, many internal subconscious scales are implied when looking at an object for the first time, the human observer is able to say if what he sees is pleasant or not. Then he just makes one classification of the perception of this object according to the feeling he has in two categories: "I like" or "I don't like".

Such an ability to classify the visual feelings is indeniably to put in relation with the inherent conscience of each human being. The conscience is related to what Freud calls "the perception-conscience system". It concerns a peripheral function of the psychic apparatus which receives information from the external world and those coming from the memories and the internal feelings of pleasure or displeasure. The immediate character of this perceptive function involves an unability for the conscience of keeping a lasting trace of this information. It communicates them to the preconscience, place of a first setting in memory. The conscience perceives and transmits significant qualities. Freud employs formulae like "index of perception, of quality, of reality " to describe the content of the operations of the perception-conscience system. Thus, perception is to be regarded as one of the internal scales of a process driving to an overall quality assessment of an object or an image.

Any designed quality metrics (including or not Human Visual System features) tends to make as well as any human observer, i.e., one tries to clone the Human Visual System. Until now, to develop a quality metric, the usually applied scheme consists in performing 1) a color space transformation to obtain decorrelated color coordinates and 2) a decomposition of these new coordinates towards perceptual channels. An error is then estimated for each one of these channels. The final quality score is obtained by pooling these errors in both spatial and frequential domain. Nevertheless, the pooling stage is based on the use of the Minkowski error metric. Recent studies [START_REF] Wang | Structural approaches to image quality assessment[END_REF] have shown that this summation does not perform well even if it is the most widely used. One can obtain the same Minkowski value for two different distorted images while the visual quality drastically differs from one distorted image to the other. This can be explained by the fact that the implicit assumption of this metric is that all signal samples are independant. Yet, this is not the case when one uses perceptual channels. When applying an "error pooling" of the obtained estimated errors within each perceptual channels, the Minkowski metric fails to generate a good final score.

Furthermore, it can be very hard to interpret the difference of quality for two images whose scores are very close, since they are obtained from measures that usually do not integrate all the degradation measures and that those degradation are not necessary located in the same area of the image.

One main observation can be formulated: the need to obtain a final quality score is not the best way to quantify the quality. Actually, in the recommendations given by the UIT, 2 the human observers have, for example, to choose a quality class from a scale containing five notes from Very bad (1) to Excellent (5). Those notes characterize the quality of the reconstructed images. That way, the human observers only make one classification or categorization. This is the way investigated in this paper. No final score is computed, only the final quality class is given with an associated a posteriori probability. The latter yields us to make final decision concerning degraded color images for with the quality class is close to the frontier between two contiguous classes.

In this paper, the quality measure is based on a learned classification process in order to respect the one of human observers. [START_REF] Charrier | Selection of features by a machine learning expert to design a color image quality metric[END_REF] Instead of computing a final note, our method classifies the quality using the quality scale recommended by the UIT. This quality scale contains 5 ranks ranginng from 1 (the worst quality) to 5 (the best quality). The selected class of the proposed method represents the opinion score OS. That way, a machine learning expert, providing a final class number is designed.

THE PROPOSED APPROACH

Selection of the classifier

From all existing classification schemes, a Support Vector Machine (SVM)-based technique has been selected due to high classification rates obtained in previous works, [START_REF] Lebrun | Fast pixel classification by SVM using vector quantization, tabu search and hybrid color space[END_REF] and to their high generalization abilities.

The SVMs were developed by Vapnik et al. [START_REF] Vapnik | Statistical Learning Theory[END_REF] and are based on the structural risk minimization principle from statistical learning theory. SVMs express predictions in terms of a linear combination of kernel functions centered on a subset of the training data, known as support vectors (SV).

Given the training data S = {(x i , y i )} i={1,...,m} , x i ∈ R n , y i ∈ {-1, +1}, SVM maps the input vector x into a high-dimensional feature space H through some non linear mapping functions φ : R n → H, and builds an optimal separating hyperplane in that space. The mapping operation φ(•) is performed by a kernel function K(•, •) which defines an inner product in H. The separating hyperplane given by a SVM is: w•φ(x)+b = 0. The optimal hyperplane is characterized by the maximal distance to the closest training data. The margin is inversely proportional to the norm of w. Thus computing this hyperplane is equivalent to minimize the following optimization problem:

V (w, b, ξ) = 1 2 w 2 + C m i=1 ξ i (1)
where the constraint ∀ m i=1 : This optimization is a convex quadratic programming problem. Its whole dual 5 is to maximize the following optimization problem:

y i [w • φ (x i ) + b] ≥ 1-ξ i , ξ i ≥
W (α) = m i=1 α i - 1 2 m i,j=1 α i α j y i y j K (x i , x j ) (2) subject to ∀ m i=1 : 0 ≤ α i ≤ C , m i=1 y i α i = 0.
The optimal solution α * specifies the coefficients for the optimal hyperplane w * = m i=1 α * i y i φ (x i ) and defines the subset SV of all support vector (SV). An example x i of the training set is a SV if α * i ≥ 0 in the optimal solution. The support vectors subset gives the binary decision function h:

h(x) = sign(f (x)) with f (x) = i∈SV α * i y i K (x i , x) + b * (3)
where the threshold b * is computed via the unbounded support vectors 5 (i.e., 0 < α * i < C). An efficient algorithm SMO (Sequential Minimal Optimization) [START_REF] Platt | Fast Training of Support Vector Machines using Sequential Minimal Optimization[END_REF] and many refinements [START_REF] Collobert | SVMTorch: Support vector machines for large-scale regression problems[END_REF][START_REF] Chang | LIBSVM: a library for support vector machines[END_REF] were proposed to solve dual problem. SVM being binary classifiers, several binary SVM classifiers are induced for a multi-class problem. A final decision is taken from the outputs of all binary SVM. 9

SVM model selection

Kernel function choice is critical for the design of a machine learning expert. Radial Basic Function (RBF) kernel function is commonly used with SVM. The most important reason is that RBF functions work like a similarity measure between two examples. As no a priori knowledge exists on the relative importance of each feature s k , the classical RBF function has been extended in order to reflect this fact and the kernel function has been defined as follow

K β (s i , s j ) = exp(- n k=1 β k (s k i -s k j ) 2 /r 2 ) ( 4
)
where s k i is the k th feature of the i th image. To have efficient SVM inducers, a parameter tuning process has to be realized. This procedure is the so-called model selection. The selection of the SVM hyper-parameter (C), the radius of RBF function (r) has been realized by using cross-validation. In this paper, β k could only take binary value and modelize if the s k feature is used or not. When β k values are not fixed by human priors, they are determined by using a feature selection paradigm. The quality of a subset of features for the design of a binary SVM is measured by its recognition performance. This corresponds to a wrapper feature selection approach. [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] SVMs being binary classifiers, multi-class decision using SVMs are usually implemented by combining several two-classes SVM decision. Several combination schemes of binary classifiers exist. [START_REF] Hsu | A comparison of methods for multiclass support vector machines[END_REF] Two schemes are used: 1) the common One-Versus-All (OVA) scheme and 2) a second one designed to take into account the existing Rank Ordering (RO) between the classes. Let t i = {t i,1 , . . . , t i,nc } be a class map vector to transform a n c classes problem to a binary problem with t i,j ∈ {+1, -1}. t i,j means that in the i th binary problem, images initially located in class j now belong to the class t i,j . Let f i (•) and h i (•) respectively be the SVM output and the SVM decision function obtained by training it on the i th binary problem. Tables 1 and2 respectively give binary problems transformation used in OVA and RO combination schemes. t 1 and t 5 transformation in OVA scheme are identical to t 1 and t 4 (class label switch is not significant) in RO scheme. The difference is concentrated to the others binary class maps. In the RO scheme, the information about the class label rank is preserved, but this is not true when using the OVA scheme (i.e. ∀c 1 , c 2 :

t i,c1 > t i,c2 → c 1 > c 2 ).
Moreover, discriminative function corresponding to t 2 , t 3 or t 4 map in OVA is more difficult to realize when excellent and very bad images are merged in the same class and are used to identify quite good images.

Table 1. Binary problems transformation use in One-Versus-All combination scheme

class t 1 t 2 t 3 t 4 t 5 5 +1 -1 -1 -1 -1 4 -1 +1 -1 -1 -1 3 -1 -1 +1 -1 -1 2 -1 -1 -1 +1 -1 1 -1 -1 -1 -1 +1
The binary problem transformation is the first part of a combination scheme. A final decision must be taken from all binary decision functions. Many combination strategies can be used to obtain the final decision. [START_REF] Hsu | A comparison of methods for multiclass support vector machines[END_REF] The majority Table 2. Binary problems transformation use the Rank Ordering combination scheme

class t 1 t 2 t 3 t 4 5 +1 +1 +1 +1 4 -1 +1 +1 +1 3 -1 -1 +1 +1 2 -1 -1 -1 +1 1 -1 -1 -1 -1
vote criterium is the usual way to do this. Let

V j (x) = n b i=1 LO 1 (h i (x), t i,j
) the number of votes for the class j (n b is the number of binary decision function in a specific combination scheme, and LO 1 is defined in the next section).

The multiclass decision function D using majority vote is:

D(x) = arg max 1≤j≤nc (V j (x)
) (when conflicts exist, the SVM output is used to break it).

SELECTION OF THE FEATURES VECTOR

As a classification process is used, one has to design a set of features that will be used by the machine learning expert. That way, the class of the quality is obtained from a reduced reference image.

Yet, there are four types of attributes contained in that set: 1) full-reference image SVH-based features and 2) full-reference image features where a reference image is needed and 3) no-reference images SVH-based features and 4) no-reference images features for which no reference image is needed. Actually, when a human observer judges the quality of an image, it is not obvious that he takes its decision only making comparison between the reference image and the reconstruced one. Probably for some degradations, only the perception of those ones are implied. In addition, internal scales imply within the final decision is not entirely well-known.

full-reference image SVH-based features

When using full-reference image features, both original and degraded images are first subject to a transformation towards an antogonist luminance chrominance color space. The aim of such transformation is to take into account the spatial-frequency sensitivity of the SVH. The latter analyzes input signals by averaging a set of radial and orientation selective channels. Two questions may have to be asked to implement this sensitivity. The first one concerns the choice of the colorimetric decomposition. For the luminance component the most used decomposition are from Daly, [START_REF] Daly | A visual model for optimizing the design of image processing algorithm[END_REF] Watson 12 and the Lubin's one. [START_REF] Lubin | Digital Images and Human Vision, ch. The use of psychophysical data and models in the analysis of display system performance[END_REF] The two first are characterized by a diadic radial selectivity (five one octave bandwidth channels) and a constant angular selectivity. The main difference is situated around the value of the bandwith: 30 degrees for Daly's model and 45 degrees for the Watson's one. Lubin's decomposition needs seven radial bands and four orientations. For the chrominance component, the same decomposition is applied with fixed maximal frequency that is different for the C 1 axis from the C 2 axis.

The second question is linked to the choice of linear transformation to apply. Actually this one has to meet many properties such as the radial and angular selectivity, the linear phasis, a minimal recovery between adjacent channels, and so on. Only one transformation meets all the required properties: the Cortex Transform. [START_REF] Watson | The cortex transform: Rapid computation of simulated neural images[END_REF] Then, for each one of the resulting images (one luminance image and txo chrominance images) a local contrast is computed for each point of the three images. Then pooling those measures a global contrast score is generated.

Color space transformation

The perception of color differences in RGB is highly nonuniform. The study of perceptual uniformity concerns numerical differences that correspond to color differences at a perceptibility threshold (just noticeable differences, or JNDs). [START_REF] Sharma | Digital color imaging[END_REF] In its second sense, color difference refers to color components where brightness has been removed. Actually, the Human Visual System has poor response to spatial detail in colored areas of the same luminance, compared to its response to luminance spatial detail. [START_REF] Finlayson | Color in perspective[END_REF] The easiest way to remove brightness information to form two color channels is to subtract it. The luma (luminance) component already contains a large fraction of the green information from the image, so it is standard to form the other two components by subtracting luma from nonlinear blue (to form B-Y) and by subtracting luma from nonlinear red (to form R-Y). These are called chroma. Various scale factors are applied to (B-Y) and (R-Y) for different applications.

From all existing opponent color spaces, the Krauskopf 16 one is selected. This coordinates system is computed from the LMS primaries that correspond to the HVS cone responses. The coordinates L , M and S represent the non-linear values due to the non-linear processing of the HVS. This transformation is obtained using 1) a logarithm function or 2) a power raise of 1/3. To compute those three non linear components, one need to apply a non linear transfer function (known to be the gamma function) to each of the component of the RGB color space. Then from those new components R', G' and B', one compute the XYZ transformation. [START_REF] Wyszecki | Color Science: Concepts and Methods, Quantitative Data and Formulae[END_REF] Then the LMS color space is obtained by apply a 3 × 3 matrix transformation on the three XYZ components corresponding to the Simth-Pokorny matrix. [START_REF] Vienot | Digital video color maps for checking the legibility of displays by dichromats[END_REF]

Cortex Filter decomposition

It is well known that the HVS analyzes the visual input by a set of channels, each of them being selectively sensitive to a restricted range of spatial frequencies and orientations. Several psychophysical experiments have been conducted by different researchers to characterize these channels. Currently, two transforms are often used. The cortex transform introduced by Daly [START_REF] Daly | The visible differences predictor: An algorithm for the assessment of image fidelity[END_REF] uses a radial frequency selectivity that is symmetric on a log frequency axis with bandwidths nearly constant at one octave. Their decompositions consist in one isotropic low-pass and three bandpass channels. The angular selectivity is constant and is equal to 45 degrees. Many different filters have been proposed as approximations to the multi-channel representation of visual information in the HVS. In this paper, a radial selectivity filter and a angular selectivity filter are used that are combined to obtain the cortex filter. Then, the reconstructed image is filtered with each cortex filter in order to obtain 31 filtered images.

Dom filter

The dom filters-d ifference of mesa-are generated by computing a difference between two consecutive mesa filters:

Dom i (u, v) = M i-1 (u, v) -M i (u, v), (5)
where u and v are the cartesian spatial frequencies. The mesa filter M i (u, v) is a low-pass filter of radial frequencies generated from the initial mesa filter M 0 (u, v) given by:

M 0 (u, v) = γ f 0 2 exp -π ωγ f 0 2 ⊗ ω 2f 0 (6)
where

ω 2 = u 2 + v 2 .
The function

ω 2f0
represents a 2D gate function with circular symmetry, centered to 0 with a radius equal to f 0 . γ is an attenuation parameter, linked to the standard deviation σ 0 og the Gaussian by σ 0 = 1 √ 2π f0 γ . The mesa filter of index i can be expressed by:

M i (u, v) = M 0 (τ i u, τ i v) (7)
where ∫ i is a scale factor given by τ i = i-1 j-1 τ j . From eq. 7, a set of K filters can be generated from the initial filter M 0 by reducing the cut frequency of the obtained filter by the factor τ .

Fan filter

The fan filters model the orientation attibutes of spatial frequency selectivity. This is obtained by applying a Gaussian diffusion on an ideal angular filter. From the vertical direction, this evolution is given by

M ′ 0 (u, v) = H(v) ⊗ γ b exp(-πγ 2 b v 2 ) ( 8
)
where H(v) is the echelon filter, γ b is an attenuation parameter. As the echelon filter has no variation on the axis u, the convolution can be expressed: For an orientation θ, the echelon filter is:

M ′ 0 (u, v) = F(γ b , v) = v -∞ exp(-πγ 2 b ω 2 )dω (9)
M ′ θ (u, v) = F(γ b , (v cos θ -u sin θ)). (10)
The fan filter corresponding to the k th direction is given by:

f an k,θ (u, v) = M ′ θk (u, v) -M ′ θk+1 (u, v) (11)
Cortex filter The cortex filters are simply the product of a dom filter and a fan filter in the frequency domain :

Cortex k,θ,i (u, v) = dom i (u, v).f an k,θ (u, v) (12)
The image is then filtered by each one of the cortex filter to obtain a set of subimages a k,θ,i (u, v) defined by

a k,θ,i (u, v) = Cortex k,θ,i (u, v).S(u, v)
where S(u, v) represents the image spectrum.

Each one of those images corresponds to the structural content of the image with respect to the frequency and the orientation.

Figure 1(a) shows the layout of all dom and fan filters in the spatial frequency plane. The series of arabic numbers specifies the fan filters. The center band orientation of the filter desinged by the number 6 is 90 degrees or -90 degrees. Each fan filter covers a range of 30 degrees. After six sequential fan filters, the same order repeats.

The series of roman numbers represents the dom filters at different frequency levels. The lower the serial roman number of the dom filter is, the lower the frequency range it resides in. Each frenquency band covers a range of one octave in the frequency domain. The first ring I is a non directional low-pass channel. Figure 1 presents an example of a cortex filter obtained by combination of a dom filter and a fan one. Thus, when a domand a fan filter are applied together, information od a certain frequency range and a certain orientation can be filtered out from the source image.

Contrast masking

Then, from each one of those filtered images, a contrast masking score is computed.

To obtain a good definition of the masking contrast, one have to take into account together the spatial and frequential resolution. Peli [START_REF] Peli | Contrast in complex images[END_REF] has proposed such a model known as the limited band local contrast. This contrast is local since it quantifies the human observer's sentivitity to the luminance variation with respect to the local mean luminance. In addition, it is a limited band contrast since the degradation perception depends on its spectral location. When using the above mentionned cortex decomposition, one has to take into account both angular and radial to define the limited band local contrast such as:

c i,j (u, v) = L i,j (u, v) i-1 k=0 card(l) l=0 L i k,l (u, v) (13)
where L ij (u, v) and c i,j (u, v) respectively specifies the luminance and the contrast located to the coordinates (u, v) of the i th radial channel and the j th angular sector. card(l) represents the number of angular sectors of the k th radial band.

Then, the perceived errors are modeled by the contrast masking for one spatial frequency and orientation channel and one spatial location, into a single objective score for each one of the 31 filtered image.

From this step, 31 scores, labeled to as feature s i , are available and integrated within the feature vector.

full-reference image features 3.2.1. Structural criteria

In addition, the three criteria integrated in the metric proposed by Wang and Bovik 21 are added to the vector. These criteria are 1) a luminance distorsion, 2) a constrast distortion and 3) a structure comparison. The authors proposed to represent an image as a vector in an image space. In that case, any image distortion can be interpreted as adding a distortion vector to the reference image vector. In this space, the two vectors that represent luminance and contrast changes span a plane that is adapted to the reference image vector. The image distortion corresponding to a rotation a such a plane by an angle can be interpreted as the structural change.

The luminance comparison is defined as

l(I, J) = 2µ I µ J + C 1 µ 2 I µ 2 J + C 1 ( 14
)
where µ I and µ J respectively represent the mean intensity of the image I and J, and C 1 is a constant avoiding instability when µ 2 I + µ 2 J ≈ 0. According to the Weber's law, the magnitude of a just-noticeable luminance change δL is proportional to the background luminance L. In that case, µ I = αµ J , where α represents the ratio of the luminance of the distorted signal relative to the reference one. The luminance comparison can be now defined as

l(I, J) = 2αµ 2 I + C 1 (1 + α 2 )µ 2 I + C 1 (15)
The contrast distortion measure is defined in a similar form:

cd(I, J) = 2σ I σ J + C 2 σ 2 I σ 2 J + C 2 ( 16
)
where C 2 is a non negative constant, and σ I (resp. σ J ) represents the standard deviation .

The structure comparison is performed after luminance substraction and contrast normalization. The structure comparison function is defined as:

s(I, J) = 2σ I,J + C 3 σ 2 I σ 2 J + C 3 (17)
where

σ IJ = 1 N -1 N i=1 (I i -µ i )(J i -µ J )
, and C 3 is a small constant. s(I, J) can take negative values which is interpreted as local image structures inversion.

color criteria

Two local descriptors based on visual attention are used. [START_REF] Trémeau | Quantitative description of image distorsions linked to compression schemes[END_REF] Those descriptors are not ponctually defined in I(x, y) but with respect to the mean value µ(x, y) of neigborhood V of the pixel (x, y) . I M (ci) (x, y) and I m (ci) (x, y) respectively represent the maximal and minimal value of the c i axis within V for the image I at the pixel located to (x, y).

The two used features are:

1. local chrominance that measures the sensitivity of an observer to color degradation within a uniform area. The calculation of this descriptor is performed in the L * a * b * color space.

2. local colorimetric dispersion that measures the spatio-colorimetric dispersion in each one of the two color images. This comparison which is performed over a neighborhood.

These descriptors have been defined according to the same scale ranging from 0 to 1 ; 0 corresponding to the most noticeable differences and 1 corresponding to the least noticeable difference.

No-reference image SVH-based features 3.3.1. Blockiness measures

The measure of blocking artefact has an important weight in the final judgment of the image quality. Blocking artefact results from a visible block structure appearing in reconstructed images. This is mainly due to the blockbased compression algorithms used to compressed images.

Many techniques to quantify blockiness effects have been proposed. Yet, these techniques require to have access to the original image. In our case, three no-reference blockiness metrics have been used: 1) the Wang et al. one,, [START_REF] Wang | Blind measurement of blocking artifacts in images[END_REF] 2) the one developed by Vlachos [START_REF] Vlachos | Detection of blocking artifacts in compressed video[END_REF] and 3) the blockiness measure as defined by Wu and Yuen. [START_REF] Wu | A generalized block-edge impairment metric for video coding[END_REF] Wang et al. model the blocky image as a non-blocky image interfered with a pure blocky signal. To estimate the blockiness of an image M B , they assume that the vertical M Bv and th horizontal M B h effects are of the same importance, and the relationship between M B and both

M Bv and M B h effects is M B = (M Bv + M B h )/2.
In order to define the two effects, they apply a 1-D FFT to the horizontal and vertical difference signals. From these signals, the average horizontal and vertical power spectra is computed. Peaks in these spectra are then identified by their locations in the spectra. The power spectra of non-blocky images is approximated by applying a median filter on these curves. The final blockiness measure is then computed as the difference between the resulting power spectra and the peaks location.

In the Vlachos's model, the used algorithm is based on the cross-correlation of subsmapled images. The original image is first decomposed in 8 × 8 size blocks. Every generated sub-image contains one specefic pixels from each original blocks. Eight sub-images are generated as follows: 1) four sub-images are generated from the four corner pixels of each blocks and 2) four other sub-images are constructed from four neighboring pixels in the top left corner of each block. Then, the cross-correlations from the former four sub-images are normalized by the computed cross-correlations of the latter four sub-images to score the blockiness measure.

For Wu and Yuen the blockiness measure is based on the vertical and horizontal differences between the columns and the rows all 8 × 8 boundaries. The mean and the standard deviation obtained from adjacent blocks to each boundary are respectively used to define weight respectively dedicated to perceptual luminance effects and texture masking effects. Then, the final blockiness measure is obtained from the latter measure normalized by the mean of the same measures computed at non-boundary columns and rows.

Blurriness measure

Blur in an image is due to the attenuation of high spatial frequencies in the image. It is characterized by a smearing of sharp edges and a general loss of details. This artefact commonly occurs during a compression process.

To measure the blurry effect on an image, one first have to detect edges. In order to detect edges in a color image, the Cumani edge detector 26 is used on the color image expressed in the Krauskopf space. Then an opening operator from mathematical morphology is applied on the resulting thresholded image in order to remove noise and non-important edges. Then, taking into account the gradient orientation, a measure of blurriness is performed along the actual local edges. To measure the width of a located edge, one used the Achromatic component and seeds obtained from the former edge image. Then both local maximum and local minimum are extracted from the achromatic image and correspond to luminance extrema closest to the edge seed. The difference between the location of those two extrema is computed to define the width of the edge. Finally the global blurriness measure is obtained by averaging the local blurriness measure over all detected edges.

No-reference image features

As no-reference image features, one has used three of the objectives features used by Gastaldo et al. to provide an objective assessment of JPEG compressed image using neural networks. [START_REF] Gastaldo | No-reference quality assessment of JPEG images by using CBP neural networks[END_REF] The three features are expressed from a color correlogram that allows us to have information about the spatial correlation of color changes with distance. The used features are:

1. Energy, that corresponds to a summation of all squared elements of the color correlogram,

MEASURE OF PERFORMANCE

Two datasets are realized from 227 different JPEG2000 compressed image versions of 25 initial images in the LIVE image database. [START_REF]LIVE Image Quality Assessment Database[END_REF] The 38 factors given in the previous section are computed for each compressed image. 25 To measure the efficient of machine learning expert, three coherence measures M are defined from three loss functions LO:

M a = 1 - 1 m m i=1 LO a (D(i), Q MOS (i)) (18)
where D(i) is the quality decision from machine learning expert for the image i and Q MOS (i) represents the MOS for the image i. a ∈ {1, 2, 3} corresponds to the loss function used. The three loss functions are the following:

LO 1 (y 1 , y 2 ) = 0 if y 1 = y 2 1 else ( 19
)
LO 2 (y 1 , y 2 ) = 0 if |y 1 -y 2 | ≤ 1 1 else (20) LO 3 (y 1 , y 2 ) = 0 if y 1 = y 2 m my 2 else ( 21
)
where m y2 corresponds to the number of images labelled to as class y 2 in the reference dataset. M 1 is a classical measure of recognition rate. M 2 measures the rank coherence of a quality decision prediction. For example, if excellent or quite good is image quality prediction and its associated Q MOS is good, then this small difference in appreciation could be tolerated, but not for a bad or very bad quality prediction. Particularly, when observing the Q OS values, for many images 90% of the observers select 2 classes (3 sometimes) which are very close in terms of their ranking. From this remark, the importance of the M 2 measure is highlighted. M 3 is a measure that takes into account the relative proportion of each quality class in a dataset. This permits to verify that low representative class are not discarded by classifier. This effect could artificially increase both M 1 and M 2 measures, but it is a kind of over-fitting effect which must be avoided. A great difference between the M 1 and the M 3 measure could detect this effect.

Before measuring the efficiency of machine learning expert, we have measured how each observer is confident with Q MOS . To doing this, the Q OS of each observer is used as a decision function D with respect to the three coherence measures M . Tables 4 and5 respectively show statistical informations on the Q MOS observer s confidences obtained from the training set and the test one. Those results show that the observer's opinion have a great variability. This variability is greatly independent of the used dataset. The M 2 confidence measure shows that divergence with Q MOS rarely exceeds one class for the raking order (even for an observer which is the most faraway from the Q MOS reference). The Machine Learning Expert (MLE) is built using the two binary SVM combination schemes defined in the previous section. To measure the influence of the used features, four experiments have been realized for each combination scheme with: 1) all full-reference features, 2) a feature selection from all full-reference features, 3) all no-reference features and 4) a feature selection from all no-reference features. For experiments 2) and 4), the most relevant features are selected by using the best-first-search algorithm 29 in a wrapper feature selection approach. [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] Due to the small size of the training set, a model selection for each binary SVM involved in the MLE is performed by a leave-one-out cross-validation (LOO-CV) measure. For speed-up LOO-CV evaluation with each binary SVM, especially when a feature selection is realized, a specific alpha seeding SVM method is used. [START_REF] Lebrun | Speed-up LOO-CV with SVM classifier[END_REF] For each of the eight designed MLE, coherence measures are computed from the training and the test one. The obtained results are summarized in Tables 6 and7.

When comparing the results from Table 5 and Table 7, one observes that the efficiency of ours MLEs is good. When considering the full-reference columns of Table 7, our MLEs are more coherent with the Q MOS than the average selection of the observers (Table 5). The MLE summarizes very well the mean behaviour of the observers, especially when the M 2 measure is observed. Then, all the errors of final class prediction measured by M 1 or M 3 criterion on the test set correspond to a choose of the quality class which differs from the Q MOS with no more than one class. Statistics shown in table 4 and 5 present the same similarity for human beings. That way, our MLEs are in concordance with the human being's prediction.

When comparing no-reference columns to full-reference columns, it could be observed a fewer decrease of the MLEs efficiency. No-reference MLEs remains good quality predictor. Especially, when observing M 2 measure and also taking into account that no-reference problem is more difficult than full-reference problem.

For the two reference problems, the M 3 measures show that our MLE does not neglect the few representative classes. Moreover, our RO combination scheme is more sensitive to the ranking order information and could improve MLEs when M 1 and M 3 measures are considered. That combination scheme could also improve MLEs with M 2 mesure under the no-reference problem. When a feature selection is realized with full-reference features (no-reference features), in average only 4.2 and 3.5 ( 2.6 and 2.75) features are respectively used by binary classifiers in the OAA and the RO combination schemes. From the Table 7, the M 2 measure show that efficient MLEs could be produce by using few features, expecially on full-reference problem. Even if, using both M 1 and M 2 one observes taht MLEs are less efficients. However, the small dataset size does not allow us to conclude more on relevance or irrelevance status of some features with a high confidence for the two reference problems. On way to overcome this problem could be the use of an efficient bootstrap technique as used in genomic problems. [START_REF] Ambroise | Selection bias in gene extraction on the basis of microarray gene-expression data[END_REF]

CONCLUSION

A color image quality metric based on Machine Learning Expert is introduced. The MLE only learns on 1) the MOS of the observers and 2) several human visual system features to characterize the quality of color images. The used features are no-reference characteristics and full-reference features. One observes that the obtained results only using the no-reference features are close to those obtained only using full-reference features to predict the final image quality. The MLE can modelize with a great efficiency the mean behaviour of the observers. The efficiency of the MLE is deeply linked to the design of a good similarity measure. In this paper, the construction of such a measure is based machine learning approach. The obtained results shows that this kind of strategy is a new promising way to investigate the image quality measure. Atually, it is more natural for human beings to classifiy the quality of a color image than to score it.

In future works, to each decision taken by the classifier an a posteriori probability will be associated in order to define a meta-classifier by combining multi-model classifiers.

  0 requires that all training examples are correctly classified up to some slack ξ and C is a parameter allowing trading-off between training errors and model complexity.

Figure 1 .

 1 Figure 1. Example of cortex filter obtained from the product of radial and orientation filters.

2 .

 2 Information Entropy correponding to amount of information bringing by the color correlogram 3. Coefficient of homogeneity indicating the degree data approximates the Guttman implicatory scales. It measures the consistency of data matrices Therefore the final feature vector contains 42 attributes (s i ) i∈[1,...,42] .

Table 3 .

 3 initial images are used as reference for the computation of those factors. First dataset of 116 compressed images defines the training set used to learning phase of the machine expert. Second dataset of 111 remaining compressed images defines the test set used to evaluate the efficiency of the machine learning expert. Respectively 29 and 25 observers give an opinion score for images in training and test set. Opinion scores and mean opinion score of observers are converted to quality scale of the UIT and are respectively noted Q OS and Q MOS . The table 3 illustrates the percentage of images in each quality class category in function of observer s Q MOS and dataset. Percentage of images in each quality class.

	QMOS class	1	2	3	4	5
	Training set 12.9% 39.7% 25.9% 16.4%	5.1%
	Testing set	13.5% 36.1% 14.4% 24.3% 11.7%

Table 4 .

 4 Observers statistics of coherence measures for the training set.

	Mean	min	Max
	M 1 0.558 ± 0.078 0.405 0.698
	M 2 0.989 ± 0.019 0.914 1.000
	M 3 0.594 ± 0.057 0.462 0.669

Table 5 .

 5 Observers statistics of coherence measures for the test set.

	Mean	min	Max
	M 1 0.529 ± 0.103 0.324 0.712
	M 2 0.975 ± 0.026 0.909 1.000
	M 3 0.550 ± 0.090 0.396 0.706

Table 6 .

 6 Table 7: MLE coherence measures using the training set.

		full-reference			no-reference
	all-features	feature selection	all-features	feature selection
	OVA	RO	OVA	RO	OVA	RO	OVA	RO
	M 1 0.922 0.922 0.870	0.888	0.991 0.802 0.853	0.870
	M 2 1.000 1.000 1.000	1.000	1.000 1.000 1.000	1.000
	M 3 0.880 0.880 0.753	0.844	0.986 0.659 0.811	0.840

Table 7 .

 7 Table 8: MLE coherence measures using the test set.

		full-reference			no-reference
	all-features	feature selection	all-features	feature selection
	OVA	RO	OVA	RO	OVA	RO	OVA	RO
	M 1 0.730 0.747 0.703	0.712	0.504 0.703 0.558	0.504
	M 2 1.000 1.000 1.000	1.000	0.973 1.000 0.892	0.982
	M 3 0.689 0.727 0.686	0.697	0.419 0.651 0.444	0.399