M Omidvar

S Carré
email: carre@cstb.fr

M Ribardière
email: mickael.ribardiere@univ-poitiers.fr

D Meneveaux
email: daniel.meneveaux@univ-poitiers.fr

K Bouatouch
email: kadi.bouatouch@irisa.fr

Radiance cache optimization for global illumination

Keywords: Global illumination, radiance caching, BRDF

Radiance caching methods have proven efficient for global illumination. Their goal is to compute precisely illumination values (incident radiance or irradiance) at a reasonable number of points lying on the scene surfaces. These points, called records, are stored in a cache used for estimating illumination of other points in the scene. Unfortunately, with records lying on glossy surfaces, the irradiance value alone is not sufficient to evaluate the reflected radiance; each record should also store the incident radiance for all incident directions. Memory storage can be reduced with projection techniques using spherical harmonics or other basis functions. These techniques provide good results with low shininess BRDFs. However, they get impractical for shininess of even moderate value since the number of projection coefficients increase drastically. In this paper, we propose a new radiance caching method, that handles highly glossy surfaces, while requiring a low memory storage. Each cache record stores a coarse representation of the incident illumination thanks to a new data structure called Equivalent Area light Sources (EAS ), capable of handling fuzzy mirror surfaces. In addition, our method proposes a new simplification of the interpolation process since it avoids the need for expressing and evaluating complex gradients.

Optimisation de cache de luminance en éclairage global

Résumé :

La simulation d'éclairage est un processus qui s'avère plus complexe (temps de calcul, coût mémoire, mise en oeuvre complexe) pour les matériaux brillants que pour les matériaux lambertiens ou spéculaires. Afin d'éviter le calcul coûteux de certains termes de l'équation de luminance (convolution entre la fonction de réflexion des matériaux et la distribution de luminance de l'environnement), nous proposons une nouvelle structure de données appelée Source Surfacique Équivalente (SSE). L'utilisation de cette structure de données nécessite le pré-calcul puis la modélisation du comportement des matériaux soumis à divers types de sources lumineuses (positions, étendues). L'exploitation d'algorithmes génétiques nous permet de déterminer les paramètres des modèles de BRDF, en introduisant une première source d'approximation. L'approche de simulation d'éclairage utilisée est basée sur un cache de luminance. Ce dernier consiste à stocker l'éclairement incident sous forme de SSE en des points appelés enregistrements. Durant la simulation d'éclairage, l'environnement lumineux doit également être assimilé à un ensemble de sources surfaciques équivalentes (en chaque enregistrement) qu'il convient de définir de manière dynamique. L'approche des Sources Surfaciques Équivalentes est particulièrement intéressante pour des matériaux rugueux ou pour les matériaux très brillants placés dans des environnements relativement uniformes. L'utilisation de SSE a permis de réduire considérablement à la fois le coût mémoire et le temps de calcul.

Mots clés : Éclairage global, cache de luminance, BRDF 1 Objectif Dans le but de créer des images photo-réalistes, pour des scènes contenant des objets spéculaires et diffus, on utilise des algorithmes d'illumination globale tels que : suivi de chemin, lancer de photon, Monte-Carlo, Metropolis etc. Ces méthodes peuvent générer des images entachées de bruit, nécessitant un temps de calcul très important et certaines sont dépendantes de la position du point de vue. Afin de générer des images de synthèse dépourvues de bruit et nécessitant un temps de calcul raisonnable, des méthodes utilisant un cache ont été proposées, elles s'exécutent en deux phases : pré-calcul d'un cache suivi d'une phase de rendu. Le cache consiste en un ensemble de points de la scène (visibles par la caméra, et appelés dorénavant enregistrements) pour lesquels un calcul de l'éclairage incident est stocké. Dans le cas où le cache enregistre l'éclairement incident [?], il permet de ne calculer que la composante diffuse indirecte, il s'agit donc d'un cache d'éclairement (irradiance cache). Si on veut calculer la composante directionnelle (spéculaire rugueuse ou glossy) indirecte, alors un enregistrement appartenant à une surface brillante (glossy) doit stocker la luminance incidente provenant de plusieurs directions. C'est l'objectif de la méthode de cache de luminance (radiance cache) proposée par Krivanek et al. [?]. Cette méthode projette les luminances incidentes dans une base de fonctions harmoniques sphériques afin de réduire le coût de stockage. Quant il s'agit de prendre en compte des lobes spéculaires (de Phong ou Lafortune), même moyennement fins (exposant de Phong allant jusqu'à 40 ou 50), le nombre de coefficients de projection devient très important, ce qui nécessite une capacité mémoire considérable pour stocker ces coefficients. Pour un exposant de Phong supérieur à 100, le nombre de coefficients devient prohibitif ainsi que les calculs associés lors des calculs de gradients de ces paramètres.

Notre objectif est de proposer une méthode d'illumination globale utilisant un cache mais capable de prendre en compte des objets très brillants (avec un exposant de Phong valant jusqu'à 200) et ne nécessitant pas une capacité de stockage importante tout en proposant un temps de caclul raisonnable. Notre approche se base sur ce que nous appelons les sources surfaciques équivalentes (SSE) et que nous décrivons plus dans ce document. basées cache est que les enregistrements calculés pour une position de la caméra peuvent être utilisés pour une autre position de la caméra, ce qui permet une balade interactive dans une scène [?].

Ces méthodes basées cache présentent des limites lorsqu'il s'agit de prendre en compte des objets brillants. Pour résoudre ce problème, on pourrait recourir à des méthodes utilisant un échantillonnage par importance Monte Carlo [?, ?, ?], la méthode de Metropolis [?] ou la carte de photons (photon mapping) [?]. Malheureusement, ces méthodes sont très gourmandes en temps de calcul.

Pour réduire la quantité de calcul, d'autres méthodes basées cache de luminance et prenant en compte les surfaces brillantes on été proposées.

Rappelons que le principe de cache d'éclairement se décompose en deux étapes. La première consiste à remplir la cache en sélectionnant des points, appelés enregistrements, pour lesquels l'éclairement est calculé en fonction de la position de la caméra. La seconde étape, qui correspond au rendu, interpole les valeurs d'éclairement mises en cache pour calculer l'éclairement en d'autres points vus à partir de la caméra. Pour les enregistrements se trouvant sur les surfaces brillantes, la valeur de l'éclairement n'est pas suffisante pour reconstruire la luminance réfléchie en ces points. Étant donné le caractère brillant des surfaces, chaque enregistrement doit stocker la luminance incidente pour toute direction d'incidence. Křivánek et al.

[?] stockent cette information directionnelle de luminance en la projetant dans un espace de fonctions de base hémisphériques (harmoniques hémisphériques) [?]. Cet algorithme est appelé cache de luminance. La méthode cache de luminance a été améliorée de différentes manières au cours de la dernière décennie [?, ?, ?]. Gassenbauer et al.

[?] propose une méthode fondée sur le cache de luminance et n'utilisant pas de fonctions de base. Dans cette méthode, les informations directionnelles de luminance incidente sont calculées par échantillonnage par importance sur la base de la BRDF en fonction des angles d'observation, puis stockées dans chaque enregistrement, ce qui permet de calculer plus efficacement la luminance pour les surfaces brillantes. Mais cette méthode a plusieurs limites : premièrement la taille important de mémoire utilisée pour la mise en cache des enregistrements, deuxièmement la marge d'erreur importante de cette méthode lors que les matériaux sont très brillants, et troisièmement, comme les enregistrements calculés dépendent de la position de la caméra, on peut avoir besoin d'effectuer des calculs supplémentaires pour augmenter l'information stockée dans les enregistrements ce qui s'avère très coûteux en temps de calcul et en mémoire.

Notons que les méthodes de cache de luminance [?, ?] sont limitées à des matériaux de faible brillance, c'est à dire pour des exposants de Phong ne dépassant pas 50. En outre, dans le cas de la méthode de Křivánek et al. un grand nombre de coefficients d'harmoniques sphériques est nécessaire, ce qui augmente à la fois le temps de calcul, et la taille mémoire.

Notre but est de proposer une méthode de cache de luminance capable de considérer des objets très brillants, c'est à dire avec des lobes de réflexion très fins, tout en ne nécessitant qu'une mémoire de stockage raisonnable. Chaque enregistrement contient une représentation grossière de la luminance incidente grâce à une nouvelle structure de données appelée Sources Surfaciques équivalentes (SSE). Notre méthode exploite au maximum la cohérence de transfert de lumière dans la scène afin de réduire considérablement les temps de calcul. Rappelons que la base mathématique sur la cohérence du transfert lumineux a été présentée dans [?, ?, ?].

Aperçu de la méthode

Afin de calculer une image, pour une position et une orientation de la caméra, on lance des rayons (rayons primaires) depuis la position de l'observateur à travers chaque pixel du plan image et en direction de la scène. Pour chaque intersection avec un objet dans la scène on cherche si le point d'intersection P se trouve ou non dans la zone d'influence d'un ou de plusieurs enregistrements. Si tel est le cas, on utilise les données stockées dans ces enregistrements pour calculer la luminance réfléchie dans la direction de l'observateur, sinon on crée un nouvel enregistrement au point d'intersection P .

Un nouvel enregistrement, en un point P , est calculé de la manière suivante. On lance des rayons depuis P dans plusieurs directions incidentes associées à l'hémisphère (Fig. 1) placé au dessus de P . Pour évaluer la luminance incidente associée à chaque rayon échantillon on peut utiliser plusieurs approches : tracé de photons, tracé de chemins bidirectionnel, etc.

Pour calculer la luminance réfléchie dans une direction donnée, en un point enregistrement P et en tout point se trouvant dans son voisinage, on utilise les luminances incidentes calculées, celles-ci étant stockées dans la structure enregistrement. Ces données nécessitent une grande capacité mémoire, d'où l'utilisation de techniques de projection dans une base de fonctions harmoniques sphériques [?]. Mais pour des lobes de Phong ayant un exposant supérieur à 100 le nombre de coefficients de projection devient prohibitif. C'est pourquoi nous proposons une méthode basée sur les SSE (Source Surfacique Equivalente).

Chacune des directions incidentes en un enregistrement P intersecte la scène en un point x i . Ces points sont regroupés (Clustering) en fonction de certains critères décrits ci-après. Le résultat est ensemble de groupes (Clusters) de points x i . Chaque groupe comprend des points x i voisins et est représenté par une surface qui éclaire P . Cette surface est appelée Source Surfacique Équivalente ou SSE dorénavant. Pour calculer de la luminance réfléchie L r en un point x dans la direction ω r on doit évaluer l'intégrale suivante :

P0

L r (x, ω r , λ) = Ω L(x, ω i , λ)f r (x, ω i , ω r , λ) cos(θ i )d(ω i ), (1)
où Ω est l'hémisphère centré autour de la position x, ω i la direction incidente, θ i l'angle entre ω i et la normale à la surface en x, f r la BRDF (Bidirectional Reflectance Distribution Function) qui nous permet d'établir le lien entre la lumière incidente et la lumière réfléchie(Fig. 1 ). Cette intégrale est particulièrement longue à évaluer car elle doit prendre en compte la luminance provenant de toutes les directions d'incidence. En effet, la seule valeur d'éclairement n'est pas suffisante, car il faut disposer de la distribution angulaire de luminance incidente provenant de l'environnement. Dans l'idéal il faudrait garder en mémoire les luminances incidentes provenant d'un nombre élevé de directions incidentes (associées aux rayons incidents de l'hémisphère), mais en pratique cela est impossible à cause du coût mémoire et du coût de calcul. C'est pourquoi nous proposons de regrouper les directions incidentes (aussi appelées tirages puisque nous tirons des échantillons de direction qui sont des rayons).

Notre méthode est décrite par l'algorithme 1. La création d'un enregistrement peut être réalisée de deux façons. La première consiste à échantillonner en point toutes les surface de la scène, ces points seront les enregistrements. Cette approche est indépendante du point de vue est permet un déplacement interactif dans la scène. La seconde approche est dépendante du point de vue. On ne calcule que des enregistrements visibles à partir de la caméra. Ces enregistrements correspondent à des pixels échantillonnées sur le plan d'image. La première solution sera utilisée pour la visualisation interactive, par contre dans cette partie nous utilisons la deuxième approche pour décrire notre méthode (comme indiqué dans l'algorithme 1 lignes 2 .. 19). Notons que notre méthode de cache de luminance pourrait être utilisée dans la première approche.

Source Surfacique Équivalente (SSE)

Afin de simplifier l'équation de luminance 1, on peut réécrire la formule sous la forme de la somme de plusieurs intégrales dans laquelle la luminance incidente en un point x (L(x, ω i , λ)) est quasi constante (Fig. 2). Nous avons donc : x P ← Tracer-Rayon-Caméra(j); Calcul-Luminance-Pixel(C, j); Collection des Publications Internes de l'Irisa ©IRISA Donc chaque angle solide Ω j représente un source surfacique équivalente. Nous faisons l'hypothèse que L(x, ω i , λ) est constante sur Ω j (on nommera ce terme L j (x) ), donc on peut le sortir de l'intégrale, ce qui donne :

L r (x, ω r , λ) = n j=1 Ωj L(x, ω i , λ)f r (x, ω i , ω r , λ) cos(θ i )d(ω i ) (2)
26: end for P0 Ω 6 Ω 0 Ω 1 Ω 2 Ω 3 Ω 5 Ω 7 Ω 4
L rj (x, ω r , λ) L j (x) Ωj f r (x, ω i , ω r , λ) cos(θ)d(ω i ) (3)
Connaissant l'équation de l'éclairement E(λ) définie en fonction de la luminance incidente L j (x, ω i , λ) nous avons :

E j (λ) = Ωj L j (x, ω i , λ) cos(θ)d(ω i ) (4)
Donc avec l'hypothèse de départ (luminance quasi constante dans un angle solide Ω j ) nous obtenons :

E j (λ) L j (x) Ωj cos(θ)d(ω i )
On peut donc déduire la valeur de la luminance en fonction de l'éclairement

L j (x) E j (λ) Ωj cos(θ)d(ω i ) (5)
avec les equations 5 et 3 on obtient :

L rj (x, ω r , λ) E j (λ) Ωj cos(θ)d(ω) Ωj f r (x, ω i , ω r , λ) cos(θ)d(ω i ) (6) L ri (x, ω r , λ) E i (λ) * Ωj f r (x, ω i , ω r , λ) cos(θ i )d(ω i ) Ωj cos(θ)d(ω i ) (7)
Deuxième partie de la formule 7, fait intervenir un terme qui correspond à la BRDF moyenne évaluée dans l'angle solide Donc en chaque enregistrement P on stocke les SSE calculées à partir de P (algorithm 1 ligne 16). Ces SSE permettent de calculer la luminance réfléchie en un enregistrement et aux points voisins. Donc on définit la BRDF moyenne F r , dépendant de l'angle solide Ω et de la direction de réflexion ω r (image 4), par : Comme on voit dans l'équation 8 le calcul de F r est indépendant de l'éclairage de la scène, donc on peut la pré-calculer et le tabuler.

P0 Ω 7 Ω 1 Ω 2 Ω 3 Ω 4 Ω 6 Ω 8 Ω 5
F r (Ω j , ω r ) = Ωj f r ( ω i , ω r , λ) cos(θ)d(ω i ) Ωj cos(θ)d(ω i ) (8) P0 Ω 2 θ 2
5 Précalcul de la BRDF moyenne F r Pour évaluer la BRDF moyenne nous avons besoin de pré-calculer la résultat de l'équation 8 pour toutes les directions de réflexion ω r , pour chaque angle solid (Ω, ω i ) défini par sa position et sa valeur.

Afin d'effectuer l'interpolation de la BRDF moyenne pour les valeurs intermédiaires de Ω j , θ j et des positions intermédiaires de ω r nous avons choisi de projeter les BRDF moyennes, calculées grâce à l'équation précédente, dans une base de fonction.L'interpolation consiste alors à interpoler les coefficients de projection.

Afin de pouvoir modéliser les différents types de matériaux (isotrope et anisotrope), on a donc choisi le modèle de lobe de Lafortune [?, ?] et d'interpoler les coefficients des différentes lobes (C x , C y , C z , n).

Projection

Dans le cas de BRDF isotrope un angle solide Ω j est défini par sa valeur en stéradian et par l'angle θ j entre l'axe de l'angle solide et la normale en un point d'une surface (Fig. 4,5 ). La projection, dans une base de fonctions de type lobe de Lafortune, est décrite par l'algorithme 2 et la (Fig 5).

La Projection des valeurs de BRDF moyennes ( F r ) dans des base de fonctions est effectuée par un programme d'algorithme génétique [?]. Chaque élément T ab[i][j] du tableau T ab (algorithm 2 ligne 8) représente les coefficients de projection d'une BRDF moyenne définie pour un angle solide Ω j et un angle d'élévation θ i , tel que : for each valeur de l'angle solide Ω j do 3:

θ i = i * π 2 * N , i ∈ ]0...N ] Ω j = j * 2π(1 -sin(θ i )) M , j ∈ ]0...M ]
for each chaque direction de réflexion ω r do 4:

Fr ← Calculer-BRDF-moyenne(Ω j , θ i , -→ ω ); // eq. 8

5:

end for 6:

// Algorithme Génétique end for 10: end for Dans le cas d'une base de fonctions de type Lafortune les coefficients de projection sont les paramètres des lobes du modèle de Lafortune. Pour les valeurs intermédiaire de Ω j et θ j on utilise une interpolation linéaire des coefficients.

Utilisation

Comme expliqué précédemment, pour calculer la luminance réfléchie dans chaque direction on a besoin de connaître les luminances incidentes (equation 1) en un point, ce qui est très coûteux en termes de mémoire et de temps de calcul. C'est pourquoi nous utilisons plutôt les SSE (Source Surfacique Équivalent) définies par l'équation 7.

Une fois les BRDF moyennes ( F r ) tabulées on peut exprimer la luminance en un point x dans une direction ω r tel que:

L r (x, ω r , λ) n i=1 E i (λ) * F t r (Ω i , ω i , ω r , x) (9)
les valeurs de F r résultent de l'interpolation des valeur de F t r tabulées.

Collection des Publications Internes de l'Irisa ©IRISA

Coefficient de brillance 40

Pour les exemples présentés ici on compare la résultat de l'équation 8 pour un matériau de type modified Phong avec une coefficient de brillance de 40

Ce qui donne comme résultat :

f r = n+2
2 * π cos(α) n où α est l'angle entre la réflexion miroir et le vecteur de réflexion R, et n est egal à 40.

Dans la tableau 1, on voit bien la grande précision de la projection dans une base de fonctions de type lobe, et dans la tableau suivant (tableau 2, sur la deuxième coupe du lobe, la projection suit bien les variations des données.

Collection des Publications Internes de l'Irisa ©IRISA Comme expliqué dans la section 5.2, à partir de l'équation 9 pour calculer l'apport d'une SSE dans une direction donnée on a besoin de connaître l'angle solide de la SSE(Ω i ), ω i qui est défini par la position de la SSE et enfin l'éclairement dû à la SSE. L'objectif de cette section est de montrer comment générer les SSE à partir du tirage des rayons (représentant les directions d'incidence) échantillonnant l'hémisphère

Génération d'arbre

L'objectif est de regrouper les rayons lancé dans différentes directions de l'hémisphère (ces rayons seront dorénavant appelés aussi tirages) en construisant un arbre tel qu'illustré par la figure 7a. Sur cette figure les points sont les projections des directions incidentes (tirages initiaux) de l'hémisphère sur la base de l'hémisphère qui est un disque. L'objectif est de subdiviser ce disque en plusieurs zones de façon récursive dans le but de créer un arbre à partir des tirages initiaux. Nous verrons qu'un parcours de cet arbre permettra de générer les SSE. Dans le cas d'un tirage uniforme (échantillonnage uniforme de l'hémisphère) on utilise une méthode de parcours de l'arbre récursive et déterministe. Comme on le voit dans les figures 7b et 7d la calotte centrale est à chaque fois subdivisée en six secteurs égaux (les zones périphériques) et un élément central (la calotte centrale). Les secteurs sont subdivisés en quatre à chaque subdivision comme on peut le voir dans la figure 7c. En continuant cette subdivision de façon récursive jusqu'à un certain niveau, on obtient un arbre où chaque noeud a quatre ou six fils et les feuilles qui regroupent un ensemble des tirages représentant l'éclairement et angle solid des tirages, et chaque noeud englobe les tirages de ses fils. Chaque tirage (une direction d'incidence) est représenté par un angle solide élémentaire égal à Ω i = 2π/nb t où nb t est nombre des tirages, sa position et son éclairement égal à :

E(λ) L(x, ω i , λ) * 2π/nb t * cos(θ)
Pour chaque noeud de l'arbre (SSE) on calcule les données suivantes : son éclairement (E), son angle solide Ω, sa position P os et sa normale N N . Ces données sont calculées à l'aide des formules suivantes où : N est utilisé pour Noeud et SN pour les noeuds fils (ou Sous Noeud).

E(N ) = i E(SN i ) Ω(N ) = i Ω(SN i ) P os(N ) = i P os(SN i ) * E(SN i ) i E(SN i ) N N = i N SNi * E(SN i ) i E(SN i )
La normale ( N N ), associée à une SSE, permet de calculer les variations de l'éclairement et de l'angle solide en tout point de la zone d'influence de l'enregistrement associé à la SSE (voir section 6.4). Une fois notre arbre créé on va choisir quel noeud de notre l'arbre on veut garder, on appelle cette étape de travail le regroupement. Pour cela, on compare la luminance réfléchie par l'enregistrement avec ses deux SSEs avec celles situées K niveaux plus bas (ici deux niveaux plus bas, contenus dans le rectangle rouge) dans l'arbre et cela pour plusieurs directions de réflexion. Cette comparaison est effectuée en évaluant une erreur relative RMSE (entre la luminance obtenue avec les SSE du rectangle vert et celle obtenue avec les SSE contenues dans le rectangle rouge). Cette erreur est normalisée avec la moyenne des luminances réfléchies avec les SSE représentées par les sous-noeuds. Cette erreur sera appelée 1 . Tant que 1 est plus grand que le seuil défini, on doit descendre dans l'arbre, mais pour choisir le noeud à subdiviser (du rectangle vert), on calcule l'erreur 2 qui est la somme des différences aux moindres carrés entre les luminances réfléchies par chaque noeud (du rectangle vert) et celles de ses sous-noeuds (se trouvant dans le rectangle rouge), puis on raffine le noeud avec la plus grande erreur 2 . Ceci est illustré par la figure 10.

Regroupement

On répète de manière itérative ce processus de raffinement tant que l'erreur 1 est plus grande que le seuil d'erreur défini par l'utilisateur.

Collection des Publications Internes de l'Irisa ©IRISA Le résultat de ce parcours permet de sélectionner un ensemble de noeuds de l'arbre de tirages qui seront les SSE associées à chaque enregistrement composant le cache.

Pour déterminer des SSEs, pour les enregistrements spéculaires et diffus, on utilise différents critères d'erreur. Pour les matériaux brillants on utilise la luminance réfléchie dans plusieurs directions pour calculer l'erreur de regroupement alors que pour les matériaux diffus, étant donné que la luminance réfléchie ne varie pas avec la direction, on utilise une autre façon de calculer l'erreur qui sera présentée plus tard.

Matériaux spéculaires Erreur du regroupement ( 1 (CV(RMSE)))

Il s'agit dans cette section de donner l'expression de l'erreur de regroupement 1 évoquée ci-dessus. L'erreur du regroupement est évaluée en calculant les luminances, duee à toutes les SSEs sélectionnées, réfléchies dans plusieurs directions avec celles dites de référence.

Pour une direction de réflexion ω r et en un enregistrement P 0 , la luminance Lr SSEs (P 0 , ω r , λ) due à des noeuds SSE est donnée par l'équation 9 :

Lr SSEs (P 0 , ω r , λ) = nbN i Lr Ni (P 0 , ω r , λ), (10)
où Lr Ni (P 0 , ω r , λ) est la luminance due à un noeud SSE.

lr ref (P 0 , ω r , λ) = nbSN i Lr SNi (P 0 , ω r , λ), (11)
où Lr SNi (P 0 , ω r , λ) est la luminance apportée par un sous-noeud SN i L'erreur est 1 est égale à :

erreur 1 (λ) = nb_ωr i Lr ref i (P 0 , ω ri , λ) -Lr regroupement i (P 0 , ω ri , λ) 2 nb_ω r Lr ref (12)
Soit 1 la composante Y , dans l'espace de couleur (X, Y, Z), associée à erreur 1 (λ). Tant que 1 est supérieure à un seuil donné on parcourt l'arbre en profondeur pour sélectionner les SSE induisant le moins d'erreur, ce qui correspond à raffiner les regroupements des SSE.

Erreur au niveau d'un noeud (SSE)( 2 )

Pour calculer l'erreur correspondant à chaque noeud on compare la luminance réfléchie due à ce noeud à la somme des luminances réfléchies dues à ses sous-noeuds de N niveaux plus bas. On calcule la luminance Lr SSE (P 0 , ω ri , λ) du noeud que l'on compare avec avec la luminance Lr SN s (P 0 , ω ri , λ) due à ses sous-noeuds SNs avec la formule 9, donc :

Lr SN s (P 0 , ω r , λ) = nb_SN j Lr SNj (P 0 , ω r , λ) (13)
L'erreur au niveau de noeud est par :

erreur 2 (λ) = nb_ωr i (Lr SN s i (P 0 , ω ri , λ) -Lr SSE i (P 0 , ω ri , λ)) 2 (14)
Soit 2 la composante Y , dans l'espace de couleur (X, Y, Z), associée à erreur 2 (λ).

Matériaux diffus

Dans le cas de matériaux diffus le raffinement de SSE procède par évaluer l'erreur 2 avant de calculer l'erreur 1 .

Erreur au niveau d'un noeud (SSE)( 2 ):

Dans le cas de BRDF diffuse, 2 ne peut être calculé à l'aide de l'équation 14 car la luminance réfléchie a la même valeur quelle que soit la direction de réflexion. C'est pourquoi nous proposons une autre façon de l'évaluer.

Collection des Publications Internes de l'Irisa ©IRISA Soit E N (λ) le spectre d'un noeud N représentant une SSE et E SNi (λ) ceux de ses fils (K niveaux plus bas dans l'arbre). L'expression de 2 est définie par :

erreur 2 (λ) = nb_SN i ((E N (λ) * Y SNi -E SNi (λ)) 2 , où E N (λ) = E(λ)/Y N , Y N et Y SNi sont respectivement les luminances correspondant aux spectres E N (λ) et E SNi (λ).
2 est composante Y , dans l'espace de couleur (X, Y, Z), associée à erreur 2 (λ).

Erreur de regroupement ( (CV(RMSE))): Donc notre pourcentage d'erreur est :

1 = n i 2 2i n Y , (15)
Où Y est la luminance associée à l'éclairement de l'enregistrement (éclairement de la racine de l'arbre des tirages) et 2i est l'erreur 2 du noeud i (représentant la SSE i sélectionnée au niveau courant lors du parcourt de l'arbre).

Algorithme:

Sélection_SSE(Arbre, P rof , n, τ ) { Pour chaque Noeuds N i , de profondeur P rof faire i 2 =Calcul_espilon_2(N i , n) Ajout_SSE(N i , T SSE ) FinPour 1 = Calcul_espilon_1(T SSE , n) Tant que ( 1 > τ ) faire N m =Noeud_Max_epsilon_2(T SSE ) Ôter(N m , T SSE ) Pour chaque noeud N f fils de N m faire f 2 =Calcul_espilon_2(N f , n) Ajout_SSE(N f , T SSE ) FinPour 1 = Calcul_espilon_1(T SSE , n) FinTant que }
Une fois l'arbre des tirage déterminé, on fait appel à la fonction Sélection_SSE(Arbre, P rof , n, τ ) dont le rôle est de calculer les SSE et les stocker dans un tableau T SSE . Les paramètres de cette fonction sont :

• Arbre : l'arbre des tirages,

• Prof : profondeur (fixée par l'utilisateur) à partir de laquelle on commence à déterminer les SSE,

• n : utilisé pour le calcul de 2 entre le noeud courant (N i ou N f dans l'algorithme) et ses sous-noeuds situées n niveaux plus bas dans l'arbre, ainsi que pour le calcul de 1 .

• τ : seuil au delà duquel les SSE sont raffinées.

La fonction Ajout_SSE(N, T SSE ) a pour objectif d'insérer un noeud SSE dans le tableau T SSE dans lequel sont stockées les SSE courantes sélectionnées. La fonction Ôter(N, T SSE ) permet de retirer un noeud SSE du tableau T SSE .

Résultat

Nous montrons dans cette section la luminance réfléchie par un enregistrement dans un ensemble de directions ω r . Chaque pixel correspond à une direction de réflexion Fig. 13 Pour des lobes très fins la luminance n'est significative que dans une petite portion de l'image alors qu'elle est très faible ailleurs. C'est pourquoi nous avons utilisé un facteur multiplicatif. Pour calculer les images références on utilise un tirage uniforme et la BRDF de Lafortune et on évalue l'intégrale suivante :

L r (x, ω r , λ) = Ω L i (x, ω i , λ)f r (x, ω i , ω r , λ) cos(θ i )d(ω i ) (16)
En utilisant la méthode de Monte-Carlo on obtient :

L r (x, ω r , λ) = 2π/nb T nb T i=1 L i (x, ω i , λ)f r (x, ω i , ω r , λ) cos(θ i ), (17)
où nb T est le nombre total de tirages. Pour calculer des images de chaque étape du raffinement de notre arbre, on utilise l'équation 9.

Comme on peut le constater dans le tableau (tab 7), pour des matériaux peu brillants quelques SSE (environ une douzaine) suffisent pour calculer la luminance réfléchie dans toutes les directions avec une bonne precision, et quand les Collection des Publications Internes de l'Irisa ©IRISA Table 7: Exemple pour différents matériaux : luminance réfléchie dans des différentes directions. Les image de la première colonne sont des images de référence calculées comme expliqué déjà avec l'équation 17. Ensuite les résultat de notre méthode, avec différents nombres de SSE (nb SSE ), sur les lignes paires on voit les images de différence en fausse couleur. De haut vers le bas : les matériaux sélectionnés deviennent de plus en plus brillants (n est lle coefficient de brillance) 15). On veut exprimer la luminance d'un point P se trouvant dans la zone d'influence de P . On a besoin de calculer la nouvelle direction incidente ( ω i ) et aussi la variation de l'éclairage et l'angle solide dans la zone d'influence de l'enregistrement (Fig. 15). Soit E i l'éclairement de la SSE et d la distance de l'enregistrement P à la SSE . Ainsi, pour le point P' l'éclairement E et le nouvel angle solide Ω , sous lequel P voit la SSE, seront approchés par les équations suivantes : :

Référence

P Ω θ P' Ω' θ' C N N' N''
I = C -P d 2 =< I . I >= ||I || 2 I = ||I || cos(θ ) =< I . N > cos(α ) =< I . N > E = E * d 2 d 2 * cos(θ ) cos(θ) * cos(α ) cos(α) (18)
Ω = Ω * d 2 d 2 * cos(θ ) cos(θ) * cos(α ) cos(α) (19)
La luminance réfléchie au point P est calculée en utilisant l'équation 9 en prenant comme angle solide et éclairement les valeurs de Ω et E , ainsi que la nouvelle position de la SSE par rapport à P . Pour accélérer les calculs au moment de création d'enregistrement on peut précalculer :

coef = d 2 cos(θ) * cos(α)
pour chaque SSE, ce qui permet d'évaluer rapidement dans la zone d'influence de l'enregistrement les valeurs de :

E = E * coef * cos(θ ) * cos(α ) d 2 (20)
et Les autres scènes sont composées de matériaux haute fréquence qui ne peuvent pas être traités par RC. Les statistiques de rendu pour toute les scènes sont présentées dans le tableau 10.

Ω = Ω * coef * cos(θ ) * cos(α ) d 2 (

Scène test Matpreview

Le scène Matpreview (figure 9) se compose d'un objet sphérique brillant (modèle de Phong avec différents coefficients de brillance) se trouvant sur un plan diffus texturé. La source de lumière est une carte d'environnement haute fréquence. Toutes les contributions lumineuses (directe et indirecte) sont stockées dans les enregistrements. Environ 3700 enregistrements sont créés sur la sphère brillante tandis que 6700 enregistrements ont été calculés pour l'ensemble de la scène. Malgré la configuration d'éclairage difficile pour une méthode de mise en cache (carte d'environnement de haute fréquence, enregistrements contenant les composantes directes et indirectes), notre technique fournit de bons résultats et les artefacts sont difficilement visibles. Notre méthode réussit à reproduire le reflet de l'échiquier sur l'objet sphérique brillant même avec un coefficient de brillance élevé de 200.

Collection des Publications Internes de l'Irisa ©IRISA Table 9: Exemple de différents matériaux pour la scène Matpreview. La première colonne présente des images de référence calculées par la méthode de suivi de chemin. Les résultats de notre méthode sont donnés dans la colonne de milieu. Les images de différence en fausse couleur se trouvent sur la colonne de droite.

Référence

Résultat différence N = 40 Ref.

Res

Res Diff.

Diff.

Figure 1 :

 1 Figure 1: Exemple d'une scène et distribution des rayons dans l'hémisphère (tirages)

  Interpoler les contributions des enregistrements en utilisant des SSE25:

Figure

  Figure 2: Regroupement de tirages.

Figure 3 :

 3 Figure 3: Regroupement des tirages pour la création de SSE.

Figure 4 :

 4 Figure 4: Exemple d'une scène avec une seule SSE. Ici pour calculer la luminance réfléchie au point P 0 on a besoin de connaître l'angle solide Ω et l'angle d'incidence θ associé à la SSE.

C

  x , C y , C z , n ← Projeter(toutes les valeurs Fr ); 8: Stocker C x , C y , C z , n dans un tableau T ab; 9:

5. 3 Figure 5 :

 35 Figure 5: Exemple de résultat de l'équation 8 pour un angle solide Ω et un angle d'incidence θ

  (a) Exemple de la première coupe du lobe (b) Exemple de la deuxième coupe du lobe

Figure 6 :

 6 Figure 6: Deux différentes coupes

Table 1 :

 1 Exemple d'un matériau pré-calculé avec N=40, chaque ligne correspond à un angle solide, et chaque colonne à son positionnement pour la calcul de F r pour différents ω r . En abscisse la variation du l'angle ω r dans le plan du découpe 6a et en ordonnée le résultat de l'équation 8. En rouge les valeurs exactes et en bleu les valeurs données par le résultat de notre projection Internes de l'Irisa ©IRISA

  de brillance 100Ici nous représentons un matériau de type Phong modifié avec un coefficient de brillance égal à 100 : les tableaux (tab.3,tab.4), on voit que avec un angle solide (Ω = π/30) il y a un petit décalage entre les résultats de projection et les résultats de référence. Table 4: Exemple d'un matériau pré-calculé avec N=100, coupe V 2 de brillance 200 Ici nous représentons un matériau de type Phong modiifié avec un coefficient de brillance égal à 200 f r = 202 2 * π cos(α) 200 Table 5: Exemple d'un matériau pré-calculé avec N=200 les tableaux (tab.5,tab.6), on voit que la projection est assez bonne même pour un matériau à forte brillance (lobe très fin).

Table 6 :Figure 7 :

 67 Figure 7: Découpage du disque représentant la la projection orthogonale de l'hémisphère en fonction des tirage projetés sur le disque : Fig.a tirage initial.Fig.b premier niveau de découpage (en calotte centrale et des secteurs (les zone périphérique).Fig.c découpage des secteurs. Fig.d redécoupage de la calotte centrale. En rouge : évolution de la calotte centrale. En gras : celle d'un des secteurs

Figure 8 :

 8 Figure 8: Exemple d'un arbre correspondant à Fig.7

  L'objectif est de regrouper des noeuds de l'arbre (c'est à dire regrouper des sources surfaciques équivalentes SSE) associés à un enregistrement. Pour cela on effectue un parcours descendant de l'arbre des tirages (Fig8) déjà créé, et on applique un critère permettant de regrouper de noeuds en SSE.Pour définir notre sélection de SSE on commence par la racine de notre l'arbre et ensuite on descend jusqu'à arriver à niveau où le critère de précision est respecté. Nous avons défini plusieurs critères d'erreur à minimiser.

Figure 9 :

 9 Figure 9: Étape de regroupement : les noeuds entourées en vert sont notre sélection SSE (N ), les noeuds entourées en rouge sont les sous-noeuds (SN ) situées deux niveaux plus bas dans l'arbre.

Figure 10 :

 10 Figure 10: Étape suivante de regroupement : tant que l'erreur de notre sélection est supérieure du seuil demandé (τ ) on descend dans l'arbre du côté la branche contenant la noeuds induisant la plus grande erreur. Les noeuds entourés en vert sont notre sélection SSE et ce entourées en rouge sont les sous-noeuds de deux niveaux plus bas.

Figure 11 :

 11 Figure 11: Exemple de raffinement de l'arbre : on continue notre descend et mis à jour notre sélection de SSE et ses sous-noeuds jusqu'au trouver l'erreur plus petite que le seuil demandé (τ ).

Figure 13 :

 13 Figure13: En haut à gauche : configuration de la scène et position de l'enregistrement x p dans la scène. En haut à droite : image "fisheye" depuis la position d'enregistrement. En bas à gauche : courbes des RMSE pour différents exposants de Phong en fonction du nombre de SSE. En bas à droite projection d'une direction de reflexion sur la base de l'hémisphère.

Figure 14 :

 14 Figure 14: Comparaisons qualitatives, pour divers exposants n de la BRDF de Phong modifié, entre notre approche avec SSE (ligne du bas) et les harmoniques hémisphériques utilisées dans la méthode de radiance caching originale (RC) [?] (ligne du haut). Les fausses couleurs illustrent la différence avec une solution de référence (rouge représentant des différences élevées et bleu foncé des différences faibles). Pour chaque résultat, la taille mémoire est indiquée en kilo octet.

Figure 15 :

 15 Figure 15: exemple des variations d'une SSE dans la zone d'influence d'un enregistrement

  Figure 16: Comparaison entre notre approche et RC avec la scène Matpreview, éclairée par une carte d'environnement. Les enregistrements stockent l'éclairement direct et indirect pour les deux méthodes, la taille d'un enregistrement est mentionnée en kilo-octets. Les statistiques complètes sont résumées dans le tableau 10.

  d'environnement (modèle de ciel clair). Malgré le faible nombre de SSE par enregistrement (50 par enregistrement en moyenne) notre méthode réussit à reproduire des effets d'éclairage complexes, tels que la réflexion du soleil sur le chrome du camping-car.

Figure 19 :

 19 Figure 19: Le scène camping-car éclairée avec une carte d'environnement. Notre méthode rend les matériaux brillants sans artefact visuel. Chaque enregistrement stocke les éclairages indirectes et directes de la carte d'environnement. La carrosserie et le chrome du camping-car sont constitués d'un matériau défini par un modèle de Phong avec une brillance de 100, tandis que les verres ont une brillance de 200.

Table 2 :

 2 Exemple d'un matériau pré-calculé avec N=40, chaque ligne correspond à un angle solide, et chaque colonne à son positionnement pour la calcul de F r pour différents ω r . En abscisse la variation du l'angle ω r dans le plan du découpe 6b et en ordonnée le résultat de l'équation 8. En rouge les valeurs exactes et en bleu les valeurs données par le résultat de notre projection

  La luminance réfléchie de référence lr ref (P 0 , ω r , λ) est celle due aux sous-noeuds(SN ) (noeuds fils situés n niveaux plus bas) :

	(a) lobe de réflexion correspondant à	(b) lobes de réflexion correspondant à	(c) différence entre le lobe résultant
	une SSE	des sous-noeuds (en couleur) avec leur	du noeud 12a et la somme des sous-
		somme en noir	noeuds 12b
	Figure 12: Exemple d'erreur de noeuds(SSE)( 2 )
	Collection des Publications Internes de l'Irisa ©IRISA

  Comparaison avec les harmoniques hémisphériques:Dans la figure14, nous comparons la luminance réfléchie obtenue par notre méthode et la méthode proposée par Křivánek et al.[?] à l'aide des harmoniques hémisphériques. Pour les deux méthodes, nous utilisons la configuration de scène illustrée dans la figure 13 ainsi que le même nombre de rayons incidents par enregistrement. Pour une qualité d'image fixe (RMSE équivalente), nous comparons également la taille mémoire en fonction de l'exposant n du modèle de Phong modifié. À l'exception des BRDFs basses fréquences (n = 5), dont la taille mémoire des enregistrements est à peu près équivalente pour chacune des méthodes, notre approche permet d'obtenir des résultats de meilleure qualité pour un coût mémoire beaucoup plus faible. En outre, la distribution des erreurs est plus lisse avec les SSE puisque les harmoniques hémisphériques produisent des effets d'ondulation. Calcul de la variation de luminance autour d'un enregistrement Étant donné un ensemble d'enregistrements constituant le cache l'objectif maintenant est d'évaluer la luminance réfléchie en un point situé dans la zone d'influence d'un enregistrement. Pour cela, il faudrait exprimer la variation la luminance d'un enregistrement dans sa zone d'influence. Soit une SSE C et un enregistrement P (Fig.

	6.4
	Collection des Publications Internes de l'Irisa ©IRISA

Table 8 :

 8 21)Dans les expressions 18 et 19 on suppose que la visibilité des SSE à partir de deux points voisins ne varie pas. Comme perspective de travaille il serait intéressant d'introduire un gradient de visibilité. Description de la scène indiquant les valeurs de l'exposant du modèle de Phong modifié, le type d'éclairage utilisés stocké dans les enregistrements, l'indication si la comparaison avec des harmoniques hémisphériques (RC) est possible, le nombre moyen de SSE par enregistrement, le nombre d'enregistrements brillants, le nombre total d'enregistrements ainsi que la taille totale de la structure de données en mégaoctets.Nous comparons les résultats obtenus avec notre méthode à des images de référence générées avec la méthode de suivi de chemin (PT)[?]. Pour PT, 50k rayons sont tracés par pixel. Notre méthode a été mise en oeuvre dans la plate-forme de rendu Mitsuba [?]. Nous avons utilisé le processus de mise en cache et la création d'enregistrements de Mitsuba. Nous avons seulement ajouté des fonctions pour le calcul des SSE et l'interpolation. Aussi, pour les images calculées à l'aide de Radiance caching [?] (RC) nous avons implémenté cette méthode dans Mitsuba en utilisant la bibliothèque d'origine [?]. Pour toutes nos scènes de test, le rayon de la zone d'influence d'un enregistrement est calculé comme étant la distance minimale des objets à partir d'une position de l'enregistrement, comme dans [?]. La luminance incidente à un enregistrement est calculée à l'aide d'un suivi de chemin PT. Pour obtenir une estimation précise de l'éclairement associé à chaque SSE, 4k échantillons (directions d'incidence) sont générés sur l'hémisphère stratifié. Nous avons également utilisé la technique de neighbor clamping proposé par Krivanek et al. [?] et qui permet de régler la valeur des rayon des zones d'influence des enregistrements en fonction de la visibilité. Notons aussi que ces mêmes paramètres sont utilisés pour la méthode RC.Pour démontrer la capacité de notre méthode à générer des effets de lumière complexes en raison de surfaces très brillantes, nous avons rendu cinq scènes avec des caractéristiques spécifiques d'éclairage (voir la table 8). Pour chaque scène, la qualité visuelle des résultats obtenus est comparée à une référence calculée avec PT. Les différences sont présentées avec des images en fausses couleur à l'aide d'une distance géométrique définie dans l'espace RV B. Nous comparons notre méthode avec RC pour les deux scènes apparaissant dans les figures 16 et 17. Ces scènes contiennent des BRDF de Phong modifié avec un exposant de brillance n inférieur à 100, puisque RC ne peut pas être utilisé pour les matériaux avec n plus élevé[?]. Les paramètres communs aux deux méthodes (SSE et RC) ont toujours été initialisés avec les mêmes valeurs.

	scène	exposants Phong	Éclairage	RC	SSE moy. /enr.	# enr. brillants	# Total enr.	Taille (Mo)
	Matpreview	40 / 100	Tous (Direct Haut Freq.)	Oui	185 / 392	2.5 k / 2.3 k	5.6 k	19.1 / 36.6
	Dragon	20 / 80 / 100	Indirect	Oui	188	16.8 k	24.3 k	126
	Cornell	40 / 100 / 200	Indirect	Non	300	3.8 k	10.7 k	45.6
	Campervan	100 / 200	Tous	Non	50	25.8 k	36.4 k	51.6
	Kitchen	200	Indirect	Non	115	15 k	31 k	69
	6.5 Résultats

Table 10 :

 10 Comparaison avec l'algorithme de Radiance Caching (RC) : dans chaque cas, notre méthode offre de meilleurs résultats (plus basse RM SE) avec des enregistrements de taille mémoire inférieure et un rendu plus rapide.Le scène Dragon (Figure17) est composée d'une pièce cubique dont le mur du fond a une valeur de brillance n égale à 20. À l'intérieur de cette pièce se trouvent un cube ( n = 100 ) et un dragon (n = 80) .En général, notre méthode surpasse la méthode originale RC. Les enregistrements avec SSE nécessitent deux fois moins de mémoire. Notre représentation de la luminance incidente à l'aide des SSE permet de créer moins d'enregistrements sans compromettre la qualité visuelle tout en réduisant le temps de rendu. Cela est vrai pour les matériaux très brillants (n = 100) mais aussi pour les matériaux modérément brillants ( scène Matpreview dans la figure16). De plus, nos rendu ne sont pas soumis à des artefacts dus à des effets d'ondulation souvent visibles avec des harmoniques hémisphériques, comme visible sur le cube de la scène Dragon dans la figure17.Le scène Cornell Box (Figure18), est composée d'une pièce cubique dont le mur du fond a une valeur de brillance égale à 100. À l'intérieur de cette pièce se trouvent deux cubes, la valeur de brillance du plus grand cube est égale à 200 alors qu'elle est de 40 pour le plus petit. On remarque que notre méthode gère bien les différentes réflexions dans la scène, entre autre celle du petit cube sur le grand cube. Le fait d'augmenter le nombre moyen de SSE, jusqu'à 300 par enregistrement sur une surface brillante, supprime les artefacts visuels dans les coins et sur les réflexions sans toutefois augmenter le nombre global d'enregistrements ( 3806 enregistrements brillants parmi 10770 pour l'ensemble de la scène 18). Figure 18: Scène Cornell Box (éclairage indirect uniquement) avec des matériaux brillants associé au mur du fond (100), le grand cube (200) et le petit cube (40). Au milieu, des gros plans de la zone encadrée en rouge montrent la qualité des résultats lorsqu'on augmente le nombre de SSE. L'erreur globale RM SE diminue considérablement lorsque le nombre de SSE augmente.La scène camping-car (figure19) est rendu avec 25800 enregistrements brillants parmi un total de 36378. Le grand nombre d'enregistrements est dû aux détails géométriques et à une distance minimale très petite utilisée pour déterminer le rayon de la zone d'influence d'un enregistrement. Les enregistrements stockent les contributions directes et indirectes de la carte

			Matpreview (Figure 16)		Dragon (Figure 17)
		Phong n = 40	Phong n = 100
		RC	SSE	RC	SSE	RC	SSE
	# enr. brillant	2740	2585	3103	2348	20000	16800
	taille enr. (Ko)	14.4	7.4	30.3	15.6	14.4	7.5
	Mémoire utilisée (Mo)	39.4	19.1	94	36.6	288	126
	durée du rendu	20 min. 12 min. 30 min. 16 min.	2.5 h.	2 h.
	RM SE	0.04	0.03	0.06	0.03	0.06	0.04
	Scène Dragon
	Discussion avec la comparaison RC

Collection des Publications Internes de l'Irisa ©IRISA Collection des Publications Internes de l'Irisa ©IRISA

État de l'artL'entrée d'un système de génération d'images réalistes est une description complète d'un monde virtuel. Celui-ci se compose de la géométrie des objets, des propriétés des matériaux de ces objets, de leurs positions dans la scène ainsi que des caractéristiques des sources lumineuses. Afin de créer une image du monde virtuel nous avons besoin de calculer la quantité de lumière entrant dans une caméra virtuelle positionnée dans la scène. La lumière pénètre dans l'appareil directement à partir des sources de lumière, mais aussi indirectement comme elle est réfléchie ou réfractée par les objets de la scène. La prise en compte de l'interaction entre la lumière et les objets dont les matériaux sont complexes (tels que les surfaces brillantes) est appelée illumination globale (IG), et constitue l'objectif principal de la synthèse d'image réaliste. La base mathématique fondamentale pour la synthèse d'images réalistes est l'équation de rendu[?]. L'équation de rendu décrit le bilan énergétique dans la scène. Pour résoudre l'équation de rendu, une approche basée sur la méthode des éléments finis peut être utilisée, il s'agit de la méthode de radiosité [?, ?]. Les algorithmes de radiosité se sont révélés très efficaces, en particulier pour des scènes relativement simples avec des surfaces parfaitement diffuses.Cependant, pour des environnements complexes avec une grande quantité de matériaux brillants, les algorithmes de radiosité ne sont pas pratiques en termes d'espace mémoire et de temps de calcul et ne considèrent que des matériaux parfaitement diffus. D'autres approches permettant de résoudre l'équation de rendu sont basées sur les méthodes de Monte Carlo. Au lieu de résoudre l'équation de rendu directement, elles expriment sous une forme simple, la solution de l'équation de rendu même dans le cas de plusieurs dimensions. Parmi ces méthodes de Monte Carlo on peut citer: le lancer de rayon distribué (distribued ray tracing) [?], le suivi de chemin (path tracing) [?], ainsi que le suivi de chemin bidirectionnel (bidirectional path tracing [?, ?], etc. Ces méthodes se sont révélées robustes et peuvent être appliquées à tout type de matériau. Cependant ces algorithmes produisent des images avec un bruit perceptible qui pourrait être supprimé en augmentant le nombre d'échantillons (rayons, trajets des rayons, les photons, etc), ce qui est malheureusement très coûteux en temps de calcul. En outre, ces méthodes n'exploitent pas la cohérence entre différents chemins de lumière générés à partir des sources de lumière. Afin d'exploiter cette cohérence d'autres algorithmes ont été proposés [?, ?, ?]. Il s'agit des méthodes de cache d'éclairement ou de luminance. Elle permettent d'éliminer tout bruit tout en diminuant le temps de calcul.Elles consistent à calculer l'éclairement ou la luminance incidente ainsi que le gradient (d'éclairement ou de luminance) en un faible nombre de points sur les surfaces de la scène, de stocker ces valeurs dans un cache (ensemble des enregistrements), puis d'utiliser le cache pour calculer la luminance en tout autre point de la scène. Cette idée a été proposée par Ward et al. [?, ?] afin de calculer la composante diffuse globale tandis que les composantes brillante (glossy) et spéculaire indirectes sont calculées dans une seconde étape par lancer de rayon. Un autre avantage de ces méthodes

Collection des Publications Internes de l'Irisa ©IRISA

SSE RC

ko 14.4 ko

Scène Boule1

La scène comprend une boule diffuse texturée (couleur rouge et vert) sur un sol brillant. Elle est éclairée par une carte d'environnement (Fig . 11). Un enregistrement ne stocke que l'éclairage indirect.

Dans cette scène on voit que notre méthode calcule avec precision les variations de la luminance sur une surface diffuse courbe (sphère) sans avoir à utiliser des gradients de rotation. En outre le reflet de la sphère sur le plan brillant ne présente pas d'artefacts.

Collection des Publications Internes de l'Irisa ©IRISA

Scène Boule2

La scène comprend une boule brillante sur un sol diffus texturé (couleur rouge et vert). Elle est éclairée par une carte d'environnement (Fig . 12). Ces deux objets sont entourés par quatre murs. Un enregistrement ne stocke que l'éclairage indirect.

Dans cette scène on voit que notre méthode calcule avec precision les variations de la luminance sur une surface brillante courbe (sphère) sans avoir à utiliser des gradients de rotation. les reflets du plan texturé sur la sphère brillante sont bien rendus.

Collection des Publications Internes de l'Irisa ©IRISA


Thomas Hassan
email: thomas.hassan@checksem.fr

Rafael Peixoto

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Aurlie Bertaux
email: aurelie.bertaux@iut-dijon.u-bourgogne.fr

Nuno Silva

Semantic HMC for Big Data Analysis

Keywords: classification, multi-classify, Big-Data, ontology, semantic technologies, machine learning

Analyzing Big Data can help corporations to improve their efficiency. In this work we present a new vision to derive Value from Big Data using a Semantic Hierarchical Multi-label Classification called Semantic HMC based in a nonsupervised Ontology learning process. We also proposea Semantic HMC process, using scalable Machine-Learning techniques and Rule-based reasoning.

I. INTRODUCTION

Nowadays, discovering knowledge and insights over web data is a major task for most corporations to increase their competitiveness. Determining the value of information relative to a particular customer is a complex task addressed by the business intelligence/data-mining field [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]. In the context of Big Data, this task is even more challenging, due to its characteristics. An increasing number of Vs has been used to characterize Big Data [START_REF] Chen | Big Data: A Survey[END_REF], [START_REF] Hitzler | Linked data, big data, and the 4th paradigm[END_REF]: Volume, Velocity, Variety and Value. Volume concerns the large amount of data that is generated and stored through the years by social media, sensor data, etc [START_REF] Chen | Big Data: A Survey[END_REF]. Velocity concerns both to the production and the process to meet a demand because Big Data is not only a huge volume of data but it must be processed quickly. Variety relates to the various types of data composing the Big Data. These types include semi-structured and unstructured data representing 90% of his content [START_REF] Syed | The Future Revolution on Big Data[END_REF] such as audio, video, webpage, and text, as well as traditional structured data, etc. Value measures how valuable the information to a Big Data consumer is. Value is the most important feature of Big Data and his raison dłtre because if data dont have value then is useless. An IDC report [START_REF] Gantz | Extracting value from chaos[END_REF] proposes the value extraction from very large volumes of a wide variety of data, by enabling the high-velocity capture, discovery, and/or analysis. Sheth [START_REF] Sheth | Transforming Big Data into Smart Data[END_REF] proposes deriving Value via harnessing the challenges posed by Volume, Variety, and Velocity using semantic techniques and technologies. This requires organized ways to harness and overcome the four V-challenges by using metadata and employ semantics and intelligent processing. Our aim is to extract Value from Big Data by harnessing a huge Volume and Variety of data that change constantly (Velocity) by using a novel unsupervised ontology learning process based on HMC called Semantic HMC. Hierarchical Multi-Label Classification (HMC) is the combination of Multi-Label classification and Hierarchical classification [START_REF] Bi | Multi-label classification on tree-and DAGstructured hierarchies[END_REF]. In HMC, the items can be assigned to different hierarchical paths and simultaneously may belong to different class labels in the same hierarchical level [START_REF] Bi | Multi-label classification on tree-and DAGstructured hierarchies[END_REF]. The ontology [START_REF] Studer | Knowledge engineering: Principles and methods[END_REF] plays a key role in defining terms and meanings used to represent the knowledge, reducing the gap between the users and the HMC process. This paper does not aim to improve the state of the art in multi-classification, nor the automatic hierarchy construction. Instead it proposes a scalable process to semantically learn the ontology by adopting scalable machine learning processes and Rule-based reasoning [START_REF] Urbani | QueryPIE: Backward Reasoning for OWL Horst over Very Large Knowledge Bases[END_REF] to classify the data items and therefore extract value from Big Data. The contributions of this work are twofold:

• Scalable ontology learning process based on HMC (Semantic HMC).

• Big Data Analysis using a Semantic HMC. The rest of the paper covers three sections. The second section describes how to use the Semantic HMC to extract value from Big Data. The third section describes the Semantic HMC process proposal. Finally, the last section draws conclusions and suggests further research.

II. USING SEMANTIC HMC TO DERIVE VALUE IN BIG DATA CONTEXT

Our approach is to exploit value from very large volumes of data that are in constant generation using a Semantic HMC approach. The Semantic HMC process learns the Tbox (Taxonomy and Rules) part of the ontology from the huge Volume and Variety of initial data. Once this learning phase is finished, the classification system incrementally learns the Tbox from the new incoming items (Abox) to provide and respond to the Velocity (and the others V) dimension(s). The result of this Semantic HMC process is a rich ontology with the items (instances) classified according to the learned concept hierarchy (i.e. the taxonomy of the ontology). Corporations recurrently use concept hierarchies as taxonomies to represent their valuable information [START_REF] Lambe | Organising knowledge: taxonomies, knowledge and organisational effectiveness[END_REF]. Our vision is to use the concept hierarchies from corporations to validate the value of the learned ontology for a specific corporation (Fig. 1).

Higher similarity between the concept hierarchy of the learned ontology and the concept hierarchy used by a corporation suggest better alignment between the HMC results and the corporations knowledge and goals. Consequently, data items classified as valuable concepts ultimately present better value to the corporation than those not matching the corporations concepts.

III. SEMANTIC HMC PROCESS

Our Semantic HMC process is generic for a large Variety of unstructured data items (e.g. text, images) and scalable for a large Volume of data. The process is unsupervised such that no previously labeled/classified examples or rules to relate the data items with the labels exist. The label (i.e. concepts) hierarchy and the rules are automatically learned from the data through scalable Machine Learning techniques. To infer the most specific concepts for each data item and all subsuming concepts we use rule-based reasoning that exhaustively applies a set of rules to a set of triples to infer conclusions [START_REF] Urbani | QueryPIE: Backward Reasoning for OWL Horst over Very Large Knowledge Bases[END_REF], i.e. the items classifications. This Rule-based reasoning approach allows the parallelization and distribution of work by large clusters of inexpensive machines through Big Data technologies as Map-reduce [START_REF] Dean | MapReduce : Simplified Data Processing on Large Clusters[END_REF]. Web Scale Reasoners [START_REF] Urbani | Three Laws Learned from Web-scale Reasoning[END_REF] currently uses Rule-Based reasoning to reach high scalability by load parallelization and distribution, thus addressing the Velocity and Volume dimensions of Big Data. This proposed process consists of 5 individually scalable steps (Fig. 2) matching the requirements of Big Data processing:

• Indexation parses and creates an index of data items.

• Vectorization calculates term-frequency vectors of the indexed items.

• Hierarchization creates a concept hierarchy based on term frequency.

• Resolution creates the reasoning rules to relate data items with the hierarchy concepts based on term frequency.

• Realization first populates the ontology with items and then for each item determines the most specific hierarchy concept and all his subsuming concepts.

A. Indexation

The indexation step parses and index data items. As one of our main focus points is the scalability of the architecture, the indexation is a mandatory step. Each item type has its specific parser to efficiently retrieve useful information for the other steps reducing the Limited Context Analysis problem. The Limited Content Analysis problem [START_REF] Lops | Content-based recommender systems: State of the art and trends[END_REF][14] is defined by the difficulty in extracting reliable automated information from various content (e.g. text, images, sound, etc.), which can greatly reduce the quality of the classifications. By reducing the Limited Content Analysis we improve the Semantic HMC capability to handle more Variety of data.

B. Vectorization

The vectorization step vectorizes the terms in the indexed items by calculating two types of term frequency vectors :

• Term frequency in each item using the frequency of a term in an item measured by TF-IDF. TF-IDF uses the frequency of a term in an item (TF) and the inverse number of items in which the term appears (IDF) [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF].

• Term frequency in all items using the appearing frequency of a term in all documents [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF]. The following steps use the term vectors calculated in this step to learn the concepts Hierarchy and the Rules.

C. Hierarchization

The hierarchization step will select relevant terms as relevant concepts and also will generate the broader-narrower relations between these concepts. To select the concepts in the hierarchy, a quality measure must be used. There are several methods for creating hierarchical relations between concepts including [START_REF] De Knijff | Domain taxonomy learning from text: The subsumption method versus hierarchical clustering[END_REF], [START_REF] Meijer | A Semantic Approach for Extracting Domain Taxonomies from Text[END_REF]:

• Hierarchical clustering that starts with one cluster and progressively merges clusters that are closest.

• Subsumption methods that construct the concept broadernarrower relations based on the co-occurrence of concepts.

Any of these methods can be used to create the hierarchical relations. The advantages and drawbacks of each method is deeply studied in [START_REF] De Knijff | Domain taxonomy learning from text: The subsumption method versus hierarchical clustering[END_REF].

D. Resolution

The resolution process will create the ontology rules used to relate the hierarchy concepts and the items using the term-frequency vectors. The rules creation process will use thresholds as proposed in [START_REF] Werner | Using DL-Reasoner for Hierarchical Multilabel Classification applied to Economical e-News[END_REF] to select the most relevant terms for each hierarchy concept that will be used in the rules. The main difference is that instead of translating the rules into logical constraints of an ontology captured in Description Logic, these rules will be translated into rules in the Semantic Web Rule Language (SWRL). The main interest in using SWRL rules is to reduce the reasoning effort, thus improving the scalability and performance of the system. We aim to use a huge amount of simple SWRL rules that will be applied to the ontology in order to classify items.

E. Realization

The realization phase will populate the learned concept hierarchy with data items. First the ontology is populated with new items to label in an assertion level (Abox). To do the classification/labeling of the items, the SWRL Rules generated in the Resolution step are used. Then a Rule-Based inference engine will use the SWRL rules and the hierarchy to infer the most specific concepts for each data item and all subsuming concepts. This leads to a multi-label classification of the documents based in a hierarchy of labels (Hierarchical Multi-label Classification).

IV. CONCLUSION

In this paper we present our vision to extract value from Big Data using a Semantic HMC process and propose a scalable five-step architecture to automatically classify unstructured items. We use machine learning to learn an ontology with SWRL rules to automatically classify items of Big Data. The Semantic HMC process prototype is under development and we expect to show the implementation and results in further work. Our current work consists in evaluating the resulting ontology, considering three different aspects: the process scalability (performance), the quality of the hierarchy, and the quality of the classification process (i.e. concept tagging of items).

Fig. 1 .

 1 Fig. 1. Value extraction for corporations

Fig. 2 .

 2 Fig. 2. Semantic HMC Process

ACKNOWLEDGMENT

This project is founded by the company Actualis SARL, the French agency ANRT and through the Portuguese COMPETE Program under the project AAL4ALL (QREN13852).


Mehwish Alam
email: mehwish.alam@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Defining Views with Formal Concept Analysis for Understanding SPARQL Query Results

Keywords: Formal Concept Analysis, SPARQL Query Views, Lattice-Based Views, SPARQL, Classification

SPARQL queries over semantic web data usually produce list of tuples as answers that may be hard to understand and interpret. Accordingly, this paper focuses on Lattice-Based View Access (LBVA), a framework based on FCA. This framework provides a classification of the answers of SPARQL queries based on a concept lattice, that can be navigated for retrieving or mining specific patterns in query results. In this way, the concept lattice can be considered as a materialized view of the data resulting from a SPARQL query.

Introduction

At present, Web has become a potentially large repository of knowledge, which is becoming main stream for querying and extracting useful information. In particular, Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] provides a method for publishing structured data in the form of RDF resources. These RDF resources are interlinked with each other to form a cloud. SPARQL queries are used in order to make these resources usable, i.e., queried. In some cases, queries in natural language against standard search engines can be simple to use but sometimes they are complex and may require integration of data sources. Then the standard search engines will not be able to easily answer these queries, e.g., Currencies of all G8 countries. Such a complex query can be formalized as a SPARQL query over data sources present in LOD cloud through SPARQL endpoints for retrieving answers. Moreover, users may sometimes execute queries which generate huge amount of results giving rise to the problem of information overload [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF]. A typical example is given by the answers retrieved by search engines, which mix between several meanings of one keyword. In case of huge results, user will have to go through a lot of results to find the interesting ones, which can be overwhelming without any specific navigation tool. Same is the case with the answers obtained by SPARQL queries, which are huge in number and it may be harder to extract the most interesting patterns. This problem of information overload raises new challenges for data access, information retrieval and knowledge discovery w.r.t web querying.

Accordingly, this paper proposes a new approach based on Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF])s. It describes a lattice-based classification of the results obtained by SPARQL queries by introducing a new clause VIEW BY in SPARQL query. This framework, called Lattice-Based View Access (LBVA), allows the classification of SPARQL query results into a concept lattice, referred to as a view, for data analysis, navigation, knowledge discovery and information retrieval purposes. This new clause VIEW BY which enhances the functionality of already existing GROUP BY clause in SPARQL query by adding sophisticated classification and Knowledge Discovery aspects. Here after, we describe how a lattice-based view can be designed from a SPARQL query. Afterwards, a view is accessed for analysis and interpretation purposes which are totally supported by the concept lattice. In case of large data only a part of the lattice [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF] can be considered for the analysis. In this way, this paper investigates also the capabilities of FCA to deal with semantic web data.

The intuition of classifying results obtained by SPARQL queries is inspired by web clustering engines [START_REF] Carpineto | A survey of web clustering engines[END_REF] such as Carrot24 . The general idea behind web clustering engines is to group the results obtained by query posed by the user based on the different meanings of the terms related to a query. Such systems deal with unstructured textual data on web. By contrast, there are some studies conducted to deal with structured RDF data. In [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF], the authors introduce a clause Categorize By to target the problem of managing large amounts of results obtained by conjunctive queries with the help of subsumption hierarchy present in the knowledge base. By contrast, the VIEW BY clause generates latticebased views which provide a mathematically well-founded classification based on formal concepts and an associated concept lattice. Moreover, it also paves way for navigation or information retrieval by traversing the concept lattice and for data analysis by allowing the extraction of association rules from the lattice. Such data analysis operations allow discovery of new knowledge. Additionally, unlike Categorize By, VIEW BY can deal with data that has no schema (which is often the case with linked data). Moreover, VIEW BY has been evaluated over very large set of answers (roughly 100,000 results) obtained over real datasets. In case of larger number of answers, Categorize By does not provide any pruning mechanism while this paper describes how the views can be pruned using iceberg lattices.

The paper is structured as follows: Section 2 introduces a motivating example. Section 3 gives a brief introduction of the state of the art while Section 4 defines LBVA and gives the overall architecture of the framework. Section 5 discusses some experiments conducted using LBVA. Finally, Section 6 concludes the paper.

Motivation

In this section we introduce a motivating example focusing on why LOD should be queried and why the SPARQL query results need classification. This scenario will continue in the rest of the paper. Let us consider that a query Q searching for museums where the exhibition of some famous artists is taking place along with the location of the museum. Here, we do not discuss the interface aspects and we will assume that SPARQL queries are provided. A standard query engine is not adequate for answering such kind of questions and a direct query over LOD will give better results. One of the ways to obtain such an information is to query LOD through its SPARQL endpoint. This query will generate a huge amount of results, which will need further manual work to group the interesting links.

Background

Linked Open Data

Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] is the way of publishing structured data in the form of RDF graphs. Given a set of URIs U, blank nodes B and literals L, an RDF triple is represented as t

= (s, p, o) ∈ (U ∪ B) × U × (U ∪ B ∪ L)
, where s is a subject, p is a predicate and o is an object. A finite set of RDF triples is called as RDF Graph G such that G = (V, E), where V is a set of vertices and E is a set of labeled edges and

G ∈ G, such that G = (U ∪ B) × U × (U ∪ B ∪ L).
Each pair of vertices connected through a labeled edge keeps the information of a statement. Each statement is represented as subject, predicate, object referred to as an RDF Triple. V includes subject and object while E includes the predicate.

SPARQL 5 is the standard query language for RDF. In the current work we will focus on the queries containing SELECT clause. Let us assume that there exists a set of variables V disjoint from U in the above definition of RDF, then (U ∪ V) × (U ∪ V) × (U ∪ V) is a graph pattern called a triple pattern. If a variable ?X ∈ V and ?X = c then c ∈ U . Given U , V and a triple pattern t a mapping µ(t) would be the triple obtained by replacing variables in t with U . [[.]] G takes an expression of patterns and returns a set of mappings. Given a mapping µ : V → U and a set of variables W ⊆ V , µ is represented as µ |W , which is described as a mapping such that dom(µ |W ) = dom(µ) ∩ W and µ |W (?X) = µ(?X) for every ?X ∈ dom(µ) ∩ W . Finally, the SPARQL SELECT query is defined as follows: Definition 1. A SPARQL SELECT query is a tuple (W, P ), where P is a graph pattern and W is a set of variables such that W ⊆ var(P ). The answer of (W, P ) over an RDF graph G, denoted by [[(W, P )]] G , is the set of mappings:

[[(W, P )]] G = {µ |W |µ ∈ [[P ]] G }
In Definition 1, var(P ) is the set of variables in pattern P and W is the set of variables in SELECT clause. Here, P includes the triple patterns containing variables. This triple pattern is then evaluated against the RDF Graph G given as [[P ]] G . It returns a set of mappings with respect to the variables in var(P ). Finally a projection over µ is done w.r.t. the variables in W . The projected set of mappings obtained as represented as µ |W . Further details on the formalization and foundations of RDF databases are discussed in [START_REF] Arenas | Foundations of rdf databases[END_REF].

Example 1. Continuing the scenario in section 2, following is the SPARQL query: This query retrieves the list of museums along with the artists whose work is exhibited in a museum along with the location of a museum. Lines 5 and 6 retrieve information about the artists whose work is displayed in some museum. More precisely, the page containing the information on a museum (?museum) is connected to the page of the artists (?artist) through a page on the work of artist (?painting) displayed in the museum. In order to integrate these three resources, two predicates were used dbpedia-owl:museum and dbpprop:artist. An excerpt of the answers obtained by Group by clause is shown below: The problem encountered while browsing such an answer is that there are too many statements to navigate through. Even after using the GROUP BY clause the answers are not organized in any ordered structure. By contrast, the clause VIEW BY activates the LBVA framework, where the user will obtain a classification of the statements as a concept lattice where statements are partially ordered (see Figure 1a). To obtain the museums in UK displaying the work of Goya, all the museums displaying the work of Goya can be retrieved and then the specific concept containing Goya and UK is obtained by navigation. The answer obtained is National Gallery in the example.

Formal Concept Analysis (FCA)

As the basics of Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] are well known, we only introduce some of the concepts which are necessary to understand this paper. FCA is a mathematical framework used for a number of purposes, among which classification and data analysis, information retrieval and knowledge discovery [START_REF] Carpineto | Concept data analysis -theory and applications[END_REF]. In some cases we obtain a huge number of concepts. In order to restrict the number of concepts, iceberg concept lattices can be used [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF]. Iceberg concept lattices contain only the top most part of the lattice. Along with iceberg lattices a stability index [START_REF] Kuznetsov | On stability of a Formal Concept[END_REF] is also used for filtering the concepts. The stability index shows how much the concept intent depends on particular objects of the extent.

FCA also allows knowledge discovery using association rules. An implication over the attribute set M in a formal context is of the form B 1 → B 2 , where B 1 , B 2 ⊆ M . The implication holds iff every object in the context with an attribute in B 1 also has all the attributes in B 2 . For example, when (A 1 , B 1 ) ≤ (A 2 , B 2 ) in the lattice, we have that B 1 → B 2 . Duquenne-Guigues (DG) basis for implications [START_REF] Guigues | Familles minimales d'implications informatives résultant d'un tableau de données binaires[END_REF] is the minimal set of implications equivalent to the set of all valid implications for a formal context K = (G, M, I). Actually, the DG-basis contains all information lying in the concept lattice.

4 Lattice-Based View Access

SPARQL Queries with Classification Capabilities

The idea of introducing a VIEW BY clause is to provide classification of the results and add a knowledge discovery aspect to the results w.r.t the variables appearing in VIEW BY clause. Let Q be a SPARQL query of the form Q = SELECT ?X ?Y ?Z WHERE {pattern P} VIEW BY ?X then the set of variables V = {?X, ?Y, ?Z} 6 . According to the definition 1 the answer of the tuple (V, P ) is represented as [[({?X, ?Y, ?Z}, P )]] = µ i where i ∈ {1, . . . , k} and k is the number of mappings obtained for the query Q. For the sake of simplicity, µ |W is given as µ. Here, dom(µ i ) = {?X, ?Y, ?Z} which means that µ(?X) = X i , µ(?Y ) = Y i and µ(?Z) = Z i . Finally, a complete set of mappings can be given as {{?X → X i , ?Y → Y i , ?Z → Z i }}.

The variable appearing in the VIEW BY clause is referred to as object variable7 and is denoted as Ov such that Ov ∈ V . In the current scenario Ov = {?X}. The remaining variables are referred to as attribute variables and are denoted as Av where Av ∈ V such that Ov ∪ Av = V and Ov ∩ Av = ∅, so, Av = {?Y, ?Z}.

Example 2. Following the example in section 2, an alternate query with the VIEW BY clause can be given as: Here, V ={?museum, ?artist, ?country} and P is the conjunction of patterns in the WHERE clause then the evaluation of [[({?museum, ?artist, ?country} , P )]] will generate the mappings shown in Table 1. Accordingly, dom(µ i ) = {?museum, ?artist, ?country}. Here, µ 1 (?museum) = M usee d ′ Art M oderne, µ 1 (?artist) = P ablo P icasso and µ 1 (?country) = F rance. We have Ov = {?museum} because it appears in the VIEW BY clause and Av = {?artist, ?country}. Figure 1a shows the generated view when Ov = {?museum} and in Figure 1b, we have; Ov = {?artist} and Av = {?museum, ?country}.

Designing a Formal Context of Answer Tuples

The results obtained by the query are in the form of set of tuples, which are then organized as a many-valued context.

Obtaining a Many-Valued Context (G, M, W, I): As described previously, we have Ov = {?X} then µ(?X) = {X i } i∈{1,...,k} , where X i denote the values obtained for the object variable and the corresponding mapping is given as {{?X → X i }}. Finally, G = µ(?X) = {X i } i∈{1,...,k} . Let Av = {?Y, ?Z} then M = Av and the attribute values W = {µ(?Y ), µ(?Z)} = {{Y i }, {Z i }} i∈{1,...,k} . The corresponding mapping for attribute variables are {{?Y → Y i , ?Z → Z i }}.

In order to obtain a ternary relation, let us consider an object value g i ∈ G and an attribute value w i ∈ W then we have (g i , "?Y ′′ , w i ) ∈ I iff ?Y (g i ) = w i , i.e., the value of g i for attribute ?Y is w i , i ∈ {1, . . . , k} as we have k values for ?Y .

Obtaining Binary Context (G, M, I): Afterwards, a conceptual scaling used for binarizing the many-valued context, in the form of (G, M, I). Finally, we have G = {X i } i∈{1,...,k} , M = {Y i } ∪ {Z i } where i ∈ {1, . . . , k} for object variable Ov = {?X}. The binary context obtained after applying the above transformations to the SPARQL query answers w.r.t to object variable is called the formal context of answer tuples and is denoted by K tuple .

Example 3. In the example Ov = {?museum}, Av = {?artist, ?country}. The answers obtained by this query are organized into a many-valued context as follows: the distinct values of the object variable ?museum are kept as a set of objects, so G = {M useeduLouvre, M useodelP rado, . . . }, attribute variables provide M = {artist, country}, W 1 = {Raphael, LeonardoDaV inci, . . . } and W 2 = {F rance, Spain, U K, . . . } in a many-valued context. The obtained manyvalued context is shown in Table 2. Finally, the obtained many-valued context is conceptually scaled to obtain a binary context shown in Table 3. The organization of the concept lattice is depending on the choice of object variable and the attribute variables. Then, to group the artists w.r.t the museums where their work is displayed and the location of the museums, the object variable would be ?artist and the attribute variables will be ?museum and ?country. Then, the scaling can be performed for obtaining a formal context. In order to complete the set of attribute, domain knowledge can also be taken into account, such as the the ontology related to the type of artists or museums. This domain knowledge can be added with the help of pattern structures, an approach linked to FCA, on top of many-valued context without having to perform scaling. For the sake of simplicity, we do not discuss it in this paper.

Museum

Building a Concept Lattice

Once the context is designed, the concept lattice can be built using an FCA algorithm.There are some very efficient algorithms that can be used [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF][START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF]. However, in the current implementation we use AddIntent [START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF] which is an incremental concept lattice construction algorithm. In case of large data iceberg lattices can be considered [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF]. The use of VIEW BY clause activates the process of LBVA, which transforms the SPARQL query answers (tuples) to a formal context K tuples through which a concept lattice is obtained which is referred to as a Lattice-Based View. A view on SPARQL query in section 2, i.e, a concept lattice corresponding to Table 3 is shown in Figure 1a.

Interpretation Operations over Lattice-Based Views

A formal context effectively takes into account the relations by keeping the inherent structure of the relationships present in LOD as object-attribute relation. When we build a concept lattice, each concept keeps a group of terms sharing some attribute (i.e., the relationship with other terms). This concept lattice can be navigated for searching and accessing particular LOD elements through the corresponding concepts within the lattice. It can be drilled down from general to specific concepts or rolled up to obtain the general ones which can be further interpreted by the domain experts. For example, in order to search for the museums where there is an exhibition of the paintings of Caravaggio, the concept lattice in Figure 1(a) is explored levelwise. It can be seen that the paintings of Caravaggio are displayed in Musee du Louvre, Museo del Prado and National Gallery. Now it can be further filtered by country, i.e., look for French museums displaying Caravaggio. The same lattice can be drilled down and Musee du Louvre as an answer can be retrieved. Next, to check the museums located in France and Spain, the roll up operation from the French Museums to the general concept containing all the museums with Caravaggio's painting can be applied and then the drill down operation to Museums in France or Spain displaying Caravaggio can be performed. The answer obtained will be Musee du Louvre and Museo del Prado.

A different perspective on the same set of answers can also be retrieved, meaning that the group of artists w.r.t museums and country. For selecting French museums according to the artists they display, the object variable will be Ov = {?artist} and attribute variables will be Av = {?museum, ?country}. The lattice obtained in this case will be from Artist's perspective (see Figure 1b). Now, it is possible to retrieve Musee du Louvre and Musee d'Art Moderne, which are the French museums and to obtain a specific French museum displaying the work of Leonardo Da Vinci a specific concept can be selected which gives the answer Musee du Louvre.

FCA provides a powerful means for data analysis and knowledge discovery. VIEW BY can be seen as a clause that engulfs the original SPARQL query and enhances it's capabilities by providing views which can be reduced using iceberg concept lattices. Iceberg lattices provide the top most part of the lattice filtering out only general concepts. The concept lattice is still explored levelwise depending on a given threshold. Then, only concepts whose extent is sufficiently large are explored, i.e., the support of a concept corresponds to the cardinal of the extent. If further specific concepts are required the support threshold of the iceberg lattices can be lowered and the resulting concept lattice can be explored levelwise.

Knowledge Discovery: Among the means provided by FCA for knowledge discovery, the Duquenne-Guigues basis of implications takes into account a minimal set of implications which represent all the implications (i.e., association rules with confidence 1) that can be obtained by accessing the view i.e., a concept lattice. For example, implications according to Figure 1(a) state that all the museums in the current context which display Leonardo Da Vinci also display Caravaggio (rule: Leonardo Da Vinci → Caravaggio). It also says that only the museums which display the work of Caravaggio display the work of Leonardo Da Vinci Such a rule can be interesting if the museums which display the work of both Leonardo Da Vinci and Caravaggio are to be retrieved. The rule Goya, Raphael, Caravaggio → Spain suggests that there exists a museum which have works of Goya, Raphael, Caravaggio only in Spain, more precisely Museo Del Prado. (These rules are generated from only the part of SPARQL query answers shown as a context in Table 3).

Experimentation

The experiments were conducted on real dataset. Our algorithm is implemented in Java using Jena8 platform and the experiments were conducted on a laptop with 2.60 GHz Intel core i5 processor, 3.7 GB RAM running Ubuntu 12.04. We extracted the information about the movie with their genre and location using SPARQL query enhanced with VIEW BY clause. The experiment shows that even though the background knowledge (ontological information) was not extracted the views reveal the hidden hierarchical information contained in the SPARQL query answers and can be navigated accordingly. Moreover, it also shows that useful knowledge is extracted from the answers through the the views using DG-Basis of implications. We also performed quantitative analysis where we discussed about the sparsity of the semantic web data. We also tested how our method scales with growing number of results. The number of answers obtained by YAGO were 100,000. The resulting view kept the classes of movies with respect to genre and location.

YAGO

The construction of YAGO ontology is based on the extraction of instances and hierarchical information from Wikipedia and Wordnet. In the current experiment, we sent a query to YAGO with the VIEW BY clause.

PREFIX rdf: http://www.w3.org/1999/02/22-rdf-syntax-ns# PREFIX yago: http://yago-knowledge.org/resource/ SELECT ?movie ?genre ?location WHERE { ?movie rdf:type yago:wordnet movie 106613686 . ?movie yago:isLocatedIn ?location . ?movie rdf:type ?genre . } VIEW BY ?movie While querying YAGO it was observed that the genre and location information was also given in the ontology. The first level of the obtained view over the SPARQL query results over YAGO kept the groups of movies with respect to their languages. e.g., the movies with genre Spanish Language Films. However, as we further drill down in the concept lattice we get more specific categories which include the values from the location variable such as Spain, Argentina and Mexico. There were separate classes obtained for movies based on novels which were then further specialized by the introduction of the country attribute as we drill down the concept lattice. Finally with the help of lattice-based views, it can be concluded that the answers obtained by querying YAGO provides a clean categorization of movies by making use of the partially ordered relation between the concepts present in the concept lattice.

DG-Basis of Implications: DG-Basis of Implications for YAGO were calculated. The implications were filtered in three ways. Firstly, pruning was performed naively with respect to support threshold. Around 200 rules were extracted on support threshold of 0.2%. In order, to make the rules observable, the second type of filtering based on number of elements in the body of the rules was applied. All the implications which contained one item set in the body were selected. However, if there still are large number of implications to be observed then a third type of pruning can be applied which involved the selection of implications with different attribute type in head and body, e.g., in rule#1 head contains United States which is of type country and body contains the wikicategory. Such kind of pruning helps in finding attribute-attribute relations.

Table 4 contains some of the implications. Calculating DG -Basis of implications is actually useful in finding regularities in the SPARQL query answers which can not be discovered from the raw tuples obtained. For example, rule#1 states that RKO picture films is an American film production and distribution company as all the movies produced and distributed by them are from United States. Moreover, rule#2 says that all the movies in Oriya language are from India. This actually points to the fact that Oriya is one of many languages that is spoken in India. This rule also tells that Oriya language is only spoken in India. Rule#3 shows a link between a category from Wikipedia and Wordnet, which clearly says that the wikicategory is more specific than the wordnet category as remake is more general than Film remakes.

Impl. ID Supp. Implication 1.

96 wikicategory RKO Pictures films → United States 2.

46 wikicategory Oriya language films → India 3.

64 wikicategory Film remakes → wordnet remake

Evaluation

Besides the qualitative evaluation of LBVA, we performed an empirical evaluation. The characteristics of the dataset are shown in Table 5. These concepts were pruned with the help of iceberg lattices and stability for qualitative analysis.

The plots for the experimentation are shown in Figure 2. Figure 2(a) shows a comparison between the number of tuples obtained and the density of the formal context. The density of the formal context is the proportion of pairs in I w.r.t the size G × M . It has very low range for both the experiments, i.e., it ranges from 0.14% to 0.28%. This means in particular that the semantic web data is very sparse when considered in a formal context and deviates from the datasets usually considered for FCA (as they are dense). Here we can see that as the number of tuples increases the density of the formal context is decreasing which means that sparsity of the data also increases.

We also tested how our method scales with growing number of results. The number of answers obtained by YAGO were 100,000. Figure 2(b) illustrate the execution time for building the concept lattice w.r.t the number of tuples obtained. The execution time ranges from 20 to 100 seconds, it means that the the concept lattices were built in an efficient way and large data can be considered for these kinds of experiments. Usually the computation time for building concept lattices depends on the density of the formal context but in the case of semantic web data, as the density is not more than 1%, the computation completely depends on the number of objects obtained which definitely increase with the increase in the number of tuples (see Table 5).

No. of Tuples

Conclusion and Discussion

In LBVA, we introduce a classification framework based on FCA for the set of tuples obtained as a result of SPARQL queries over LOD. In this way, a view is organized as a concept lattice built through the use of VIEW BY clause that can be navigated where information retrieval and knowledge discovery can be performed. Several experiments show that LBVA is rather tractable and can be applied to large data.

For future work, we are interested in extending the VIEW BY clause by including the available background knowledge of the resources using the formalism of pattern structures [START_REF] Ganter | Pattern structures and their projections[END_REF]. Moreover, we intend to use implications for completing the background knowledge. We also intend to use pattern structures with a graph description for each considered object, where the graph is the set of all triples accessible w.r.t reference object.

  Fig. 1: Lattice-Based Views w.r.t Museum's and Artist's Perspective .

Fig. 2 :

 2 Fig. 2: Experimental Results.

Table 1 :

 1 Generated Mappings for SPARQL Query Q

	SELECT ?museum ?artist ?country WHERE {
	?museum rdf:type dbpedia-owl:Museum .
	?museum dbpedia-owl:location ?city .
	?city dbpedia-owl:country ?country .
	?painting dbpedia-owl:museum ?museum .
	?painting dbpprop:artist ?artist}
	VIEW BY ?museum
		?museum	?artist	?country
	µ1 Musee d'Art Moderne Pablo Picasso France
	µ2 Museo del Prado	Raphael	Spain
	. . .	. . .	. . .	. . .

Table 2 :

 2 Many-Valued Context (Museum).

			Artist			Country
	Musee du Louvre		{Raphael, Leonardo Da Vinci, Caravaggio}	{France}
	Musee d'Art Moderne	{Pablo Picasso}		{France}
	Museo del Prado		{Raphael, Caravaggio, Francisco Goya}	{Spain}
	National Gallery	{Leonardo Da Vinci, Caravaggio, Francisco Goya} {UK}
			Artist			Country
	Museum	Raphael Da Vinci Picasso Caravaggio Goya France Spain UK
	Musee du Louvre	×	×	×	×
	Musee d'Art Moderne		×		×
	Museo del Prado	×		×	×	×
	National Gallery		×	×	×	×

Table 3 :

 3

Formal Context K tuple w.r.t ?museum.

Table 4 :

 4 Some implications from DG-Basis of Implication (YAGO)

Table 5 :

 5 Characteristics of Datasets (YAGO)

		|G| |M | No. of Concepts
	20%	3657 2198	7885
	40%	6783 3328	19019
	60%	9830 4012	31264
	80%	12960 4533	43510
	100%	15272 4895	55357

http://project.carrot2.org/index.html

As W represents set of attribute values in the definition of a many-valued formal context, we represent the variables in select clause as V to avoid confusion.

The object here refers to the object in FCA.

https://jena.apache.org/