Frédéric Lefèvre
email: frederic.lefevre@insa-lyon.fr

Stéphane Lips

Romuald Rullière

Jean-Baptiste Conrardy

Martin Raynaud

Jocelyn Bonjour

FLAT PLATE HEAT PIPES: FROM OBSERVATIONS TO THE MODELING OF THE CAPILLARY STUCTURE

Keywords: confocal microscopy, grooves, meshes, electronic cooling, meniscus

This paper presents a synthesis of observations made inside six different flat plate heat pipes (FPHPs). Silicon and copper systems with different capillary structures and sizes are studied. They are hermetically sealed on their upper face with a transparent plate, which enables liquid-vapor interface observations. A confocal microscope is used to measure the liquid film shapes inside the systems and describe the meniscus curvature radius from the evaporator to the condenser. Physical mechanisms, including the boiling limit and the effect of the interfacial shear stress, involved in different capillary structures such as grooves or meshes are discussed. Experimental results are compared to an analytical model describing both the liquid and vapour flows inside the FPHP and coupled to an analytical solution for the wall temperature. The capillary structure is modeled by considering the permeability and the equivalent thermal conductivity of a porous medium. The comparison between the model and the experimental data makes possible the estimation of the physical properties of the capillary structure. These experimental parameters are introduced in the model to estimate the performance of the heat pipe in a real application with several electronic components.

INTRODUCTION

The interest in the use of heat pipes for thermal management of electronic components is recognized for both aerospace and terrestrial applications, especially with increasing heat flux requirements. In many applications, heat pipes are circular and are used to transport heat from one single heat source to one single heat sink. Flat plate heat pipes (FPHP) have the same function, but offer a wide cross-section, which enables the reduction of their thickness without reducing their thermal performance. They are particularly interesting when several heat sources have to be cooled, such as several electronic components on an electronic card. The thermal performance of a FPHP depends mainly on the capillary structure, which is usually made of grooves, meshes or sintered powder. FPHP can also be realized using several micro heat pipes placed parallel one to each other at a small distance.

Flat plate heat pipes (FPHP) have been widely studied in the last fifteen years, especially for their applications to electronic cooling [START_REF] Lallemand | Micro/mini heat pipes for the cooling of electronic devices[END_REF][START_REF] Vasiliev | Micro and miniature heat pipes -Electronic component coolers[END_REF]. Although the literature on FPHP is abundant, experimental papers are relatively rare and most of the time do not provide measurements inside these systems, but only surface temperature measurements. Besides, theoretical works are generally focused on capillary-driven flows and thermal models in ideal conditions, i.e. the system being optimally filled with liquid [START_REF] Faghri | Thermal characteristics of conventional and flat miniature axially grooved heat pipes[END_REF][START_REF] Kim | Analytical and experimental investigation on the operational characteristics and the thermal optimization of a miniature heat pipe with a grooved wick structure[END_REF][START_REF] Lefèvre | Prediction of the temperature field in flat plate heat pipes with microgrooves -Experimental validation[END_REF].

Since a few years, we developed experimental benches to visualize the flow in the capillary structure of FPHPs closed with transparent plates. Different capillary structures were studied (grooves with constant or variable width, crossed grooves, grooves covered with screen meshes, meshes) for FPHPs made of copper or silicon. Depending on the applications, we tested FPHPs with different sizes and different evaporator, condenser and adiabatic areas. The behavior of those systems filled with various working fluids were studied for different filling ratios and a wide range of applied heat fluxes.

Confocal microscopy has been used with varying degrees of success (depending on various parameters such as the size of the capillary structure, the heat flux applied at the evaporator, …) to characterize the liquid-vapor interface in the capillary structure [START_REF] Rullière | Prediction of the maximum heat transfer capability of two-phase heat spreaders -Experimental validation[END_REF]Lips et al., 2010a,b,c and2011) and thin films of condensation on the groove fins [START_REF] Lefèvre | Confocal microscopy applied to capillary film measurements in a radial flat plate heat pipe made of silicon[END_REF]. Such measurements had never been provided before although they are necessary to validate most of the theoretical works published on FPHP [START_REF] Lefèvre | Prediction of the temperature field in flat plate heat pipes with microgrooves -Experimental validation[END_REF][START_REF] Revellin | Experimental validation of an analytical model for predicting the thermal and hydrodynamic capabilities of flat micro heat pipes[END_REF]. Temperature measurements are indeed not sufficient to validate hydrodynamic models that depend mostly on the meniscus curvature radius variation from the condenser to the evaporator. Furthermore, the temperature field in flat heat pipes depends on the thickness of thin films in both the condensing and evaporating areas (Lips et al., 2010a). Thus, the curvature radius of the menisci is a key parameter in both hydrodynamic and thermal models of heat pipes.

While confocal microscopy has been very useful to characterize FPHPs, visual observations have been sufficient to describe different physical phenomena of high importance to understand how FPHPs work. In the first sections of this paper, a synthesis of our observations is presented as well as what they have brought to the knowledge on these systems.

Frontiers in Heat Pipes

Available at www.HeatPipeCentral.org Physical phenomena involved in FPHPs are complex: evaporation and condensation phenomena, in presence of thin liquid films, in capillary geometries, and possibly boiling heat transfer. Models including such a complex physic are useful for the understanding but not convenient for engineering applications. In this paper, we also present results obtained with a very simple model [START_REF] Lefèvre | Coupled thermal and hydrodynamic models of flat micro heat pipes for the cooling of multiple electronic components[END_REF], in which the FPHP is characterized by its geometrical parameters, the properties of the capillary structure (permeability, equivalent thermal conductivity and effective radius), and the thermophysical properties of the wall and the working fluid. This model is particularly convenient for engineers since it enables the calculation of both the 3D temperature field and the capillary limit of a FPHP used to cool several electronic components (or any kind of heat sources) and several heat sinks, whatever their locations and their heat transfer rate.

In the last section of the article, the model is compared to experiments realized with a FPHP in order to estimate the permeability and the equivalent thermal conductivity of its capillary structure. The estimated properties are compared to analytical classical laws of the literature. Finally, these experimental parameters are introduced in the model to simulate the cooling of a real electronic card with several electronic components.

EXPERIMENTAL BENCHES DEVELOPED TO STUDY FPHPs

This section presents the physical and geometrical characteristics of different FPHPs and the associated experimental benches that were developed to characterize these systems.

Six different flat plate heat pipes

Six flat plate heat pipes, with different sizes and capillary structures have been tested. They are hermetically sealed on their upper face with a transparent plate, which enables liquid-vapor interface observations. Five of them are made of copper and one of silicon. In all cases, temperature sensors are located in the wall to measure the temperature field in working conditions.

FPHP 1, shown in Fig. 1, is made of a copper plate of thickness 1.5 mm and surface 267×115 mm² [START_REF] Lefèvre | A flat plate heat pipe with screen meshes for the cooling of electronic components[END_REF][START_REF] Lefèvre | Experimental investigations of flat plate heat pipes with screen meshes or grooves covered with screen meshes as capillary structure[END_REF]. The capillary structure, of dimensions 230 × 90 mm 2 , is made of one or two CuSn 325 square screen mesh layers. The capillary screen meshes are plated against the copper plate by means of a coarse screen mesh, which creates the vapor space (Fig. 2). The heat source is a thick resistor film of dimensions 55.1×96.5 mm 2 and resistance 90.6 . Two different heat sinks were tested: either two aluminum radiators (140×170 mm 2 ), cooled by natural convection of air at ambient temperature were screwed to each extremity of the heat pipe by thermal wedge locks or water heat exchangers of heat transfer area 30 × 90 mm 2 were plated against the wall also at each extremity.

FPHP 2 (Fig 3) is made of 109 longitudinal micro-grooves, machined in a copper plate of dimensions 230×90 mm 2 [START_REF] Rullière | Prediction of the maximum heat transfer capability of two-phase heat spreaders -Experimental validation[END_REF][START_REF] Lefèvre | Prediction of the temperature field in flat plate heat pipes with microgrooves -Experimental validation[END_REF]. Unlike classical FPHP applications, in which the heat source is small compared to the adiabatic and the heat sink regions, this FPHP has been tested with a large heat source (190×90 mm 2 ), a small heat sink (30×90 mm 2 ) and a small adiabatic region (10×90 mm 2 ). The application was the cooling of fuel cells. Each groove has a square cross-section of height and width equal to 400 µm. The distance between two grooves is equal to 400 µm. Good thermal performance was obtained with FPHP 2 in horizontal and in vertical favorable positions, but it was not able to work in unfavorable tilted position because capillary pressure induced by the grooved capillary structure was too low to overcome the hydrostatic pressure drop in vertical position. In order to overcome this limit, screen meshes were plated against the grooves [START_REF] Lefèvre | Experimental investigations of flat plate heat pipes with screen meshes or grooves covered with screen meshes as capillary structure[END_REF] to increase the capillary pressure gradient while preserving the high permeability of the grooves. FPHP 3 is similar to FPHP 2, but the grooves are covered by two layers of meshes (Fig. 4). FPHP 4 is also made of copper with the same grooves as FPHP 2 [START_REF] Lips | Nucleate boiling in a flat grooved heat pipe[END_REF]2010). Compared to the previous systems, the dimensions are close to those encountered in electronic cooling applications (overall dimensions of 70×90 mm², evaporator and condenser area of 20×90 mm² and 30×90 mm² respectively).

The fifth heat pipe, FPHP 5, of dimensions 72×68 mm², is shown in Fig. 5. It is made of 85×90 crossed micro-grooves (that can also be viewed as an array of posts) machined in a copper plate. As for FPHP 2, 3 and 4, each groove has a square cross section (400×400 μm²) and the distance between two grooves is equal to 400 μm.

The sixth and last heat pipe, FPHP 6 (Fig. 6) is made of silicon. Its capillary structure, of diameter 50 mm, is etched on a silicon wafer of 3 100 mm diameter and 525 µm thickness. It is made of 72 radial microgrooves that are connected by crossed grooves at the centre of the device. The etching depth is equal to 200 µm. The radial grooves have a rectangular cross-section whose width varies from 670 µm at the periphery to 110 µm at the connection with the crossed grooves. These crossed grooves have a width equal to 100 µm and they are separated by fins of same width, which creates a network of 300 small posts of 100×100 µm 2 .

Confocal Microscopy

Capillary phenomena, evaporation, and condensation in micro channels have been the focus of many experimental papers these last years. In a heat pipe, these phenomena are linked together and cannot be studied separately. Therefore, it is difficult to perform measurements in such a device. For example, micro-PIV is not helpful in heat pipes because the process of insemination is not convenient. Indeed, any particles introduced in the liquid would be blocked at the evaporator because of their non evaporative nature. Among classical techniques for film thickness measurement applied to micro-scale two-phase flow systems (Tibiriça et al., 2009), confocal microscopy appears to be the most appropriate to characterize FPHPs.

The confocal microscope is a STIL Micromesure 2 system. The optical sensor has a nominal measuring range of 350 µm. The working distance is about 13 mm. The maximum measuring angle for specular reflection is about 27°. The optical sensor velocity is about 1 mm.s -1 , which is fast enough for not thermally disturbing the measurement. Once the top of the groove is detected by the sensor, the liquid-vapor interface is recorded. The resulting data are used to estimate the curvature of the surface.

mm

Fig. 6 Picture of FPHP 6 [START_REF] Lefèvre | Confocal microscopy applied to capillary film measurements in a radial flat plate heat pipe made of silicon[END_REF] Optical principles of confocal microscopy are described in Fig. 7. A white light point source is imaged by a lens that has not been corrected for chromatic aberration on a series of monochromatic point images in the measurement space. The reflected light passes back through the lens and is directed towards a spectral detector by a partially reflecting mirror. The spectral analysis of the collected lights that are separated by a spatial filter enables the location of the surface to be measured. The monochromatic light having the highest intensity corresponds to the surface to be measured.

Fig. 7 Schematic diagram of confocal microscopy

SYNTHESIS OF THE OBSERVATIONS INSIDE THE CAPILLARY STRUCTURE OF THE FPHPs

Examples of measurements

Fig. 8 presents an example of measurement obtained with FPHP 6, filled with methanol, in the condenser area. Two grooves are visualized. The width of the grooves and the fins are about 400 µm and 800 µm, respectively (the scale on the y axis is 100 times lower than that on the x axis). This example shows that confocal microscopy permits to measure both the meniscus curvature radius inside the grooves and the condensate film on the fins. This last measurement is not possible with FPHPs made of copper. Indeed, the reflection of white light on a copper surface is larger than on silicon surface. As a result, the intensity of the reflected light is so high compared to that of the light reflected on the liquid-vapor interface that the focalization on the liquid film is not accurate enough for proper measurements. With silicon, the intensity of the reflected light is lower, which enables this measurement.

In example of Fig. 8, the thin condensate film thickness is lower than 5 µm. Circles that fit the experimental data are plotted. The radius of curvature is found to be 1.08 mm in the grooves and 12.4 mm on the fins. The curvatures between these zones are reversed. Therefore, the Young-Laplace law yields to the conclusion that the liquid pressure is higher than the vapor pressure on the fins and lower than the vapor pressure in the grooves. It has to be noted that, from our measurements, the transition between the two films looks abrupt. Thus, a very small region shall be present where the curvature changes from a constant positive value to a constant negative value. Such measurements are useful to understand evaporation and condensation processes that highly depend on the shape of the liquid-vapour interface (Lips et al., 2010a).

For FPHP 6, the microscope was not useful to measure the menisci in the part of the capillary structure where groove widths are to small (< 150 µm). Indeed, for such small grooves, the slope of the meniscus at the junction with the grooves is higher than the maximum measuring angle of the optical sensor. This is a real limitation of this measurement method.

Slope change

Fig. 8 Liquid-vapor interface FPHP 6 [START_REF] Lefèvre | Confocal microscopy applied to capillary film measurements in a radial flat plate heat pipe made of silicon[END_REF] Confocal microscopy has also been used to measure the liquid-vapor interface in crossed-grooves (FPHP 5). Fig. 9 presents a measurement obtained at the junction between two grooves. The top of the fins is not homogeneous because of the copper roughness. The liquid-vapor interface is smoother and has a saddle shape. As the measurement of the confocal microscope is punctual, the surface is obtained by moving the FPHP with a motorized table along x and y directions.

The surface curvature is identified from the experimental data. The capillary pressure P cap is deduced from the Young-Laplace law. The measurement method can be validated in non working conditions, with the FPHP being tilted. In such conditions, the capillary pressure is theoretically equal to the hydrostatic pressure of the liquid. Fig. 10 presents the capillary pressure measured for FPHP 5 filled with methanol and with FC72, with an inclination angle with respect to the horizontal equal to 5° and 2.5° respectively. Solid lines are the hydrostatic pressures. A good agreement is observed between experimental and theoretical results. The accuracy of the method is evaluated to be of the order of 1 Pa.

Synthesis of the information brought by the observations

FPHP 2 and FPHP 4 have been studied in different experimental conditions [START_REF] Rullière | Prediction of the maximum heat transfer capability of two-phase heat spreaders -Experimental validation[END_REF]Lips et al., 2010b) in order to obtain a significant experimental database. Experimental parameters are the vapor space thickness (1 mm, 1.6 mm and 2 mm), the inclination, the filling ratio, the heat flux transferred by the system (between 0.5 Wcm -2 and 3 Wcm -2 ) and the working fluid (N-pentane or methanol).

Fig. 11 presents the comparison between this database and a hydrodynamic model based on the balance equations and the Young-Laplace law [START_REF] Lips | Physical mechanisms involved in grooved flat heat pipes: experimental and numerical analyses[END_REF]. To facilitate and reduce the presentation of the hydrodynamic measurements, the experimental results obtained by confocal microscopy are presented in the form of the mean capillary pressure gradient ΔP cap /Δx in the adiabatic zone. The uncertainty of the capillary pressure gradient is given for each experiment. In all the cases, a good agreement is observed between experimental and numerical results. The numerical model tends to slightly overestimate the capillary pressure gradient in the system. The mean relative error of the model is about 15 %.

In theoretical models developed in the literature, shear stress calculation is often viewed as the most important parameter for pressure drop calculations. In the present model, the liquid-wall and vapor-wall shear stresses are calculated with a classical approach in laminar conditions [START_REF] Faghri | Thermal characteristics of conventional and flat miniature axially grooved heat pipes[END_REF]. In Fig. 11, interfacial shear-stress has been calculated considering the liquid as motionless for the vapor, but in all these experimental conditions, neglecting the interfacial shear stress does not change significantly the results [START_REF] Lips | Physical mechanisms involved in grooved flat heat pipes: experimental and numerical analyses[END_REF], even with a small vapor space (1 mm). It has to be noted that these experimental conditions are close to those encountered in the literature [START_REF] Lallemand | Micro/mini heat pipes for the cooling of electronic devices[END_REF].

While interfacial shear stress has not a strong influence on FPHP performance, experimental results obtained by confocal microscopy with FPHP 4 show that FPHP performance is strongly influenced by both the filling ratio and the vapor space thickness (Lips et al., 2010). A small vapor space thickness induces liquid retention in the FPHP corners and sides and thus reduces the thermal resistance of the system. Nevertheless, the meniscus curvature radius at the condenser decreases with the decrease of the vapor space thickness, which reduces the maximum capillary pressure of the FPHP. As an example, a vapor space of 1 mm leads to a 35 % decrease of the maximum capillary pressure with respect to a very large vapor space thickness.

Fig. 11 Comparison between experimental and numerical hydrodynamic results [START_REF] Lips | Physical mechanisms involved in grooved flat heat pipes: experimental and numerical analyses[END_REF] Confocal microscopy is well adapted to characterize FPHP but visual observations are sufficient to describe different physical phenomena of high importance to understand how FPHP works. For example, nucleate boiling (Fig. 12) has been observed in various configurations for relatively small heat fluxes [START_REF] Lips | Nucleate boiling in a flat grooved heat pipe[END_REF][START_REF] Lefèvre | Experimental investigations of flat plate heat pipes with screen meshes or grooves covered with screen meshes as capillary structure[END_REF].

Fig. 12

Example of boiling phenomenon in the evaporator of FPHP 4 [START_REF] Lips | Nucleate boiling in a flat grooved heat pipe[END_REF] For FPHP 4, filled with methanol, nucleate boiling was observed for heat fluxes higher than 3 W/cm² and until 18 W/cm². Unexpectedly, this phenomenon does not prevent the working of the system and conversely increases its thermal performance. An experiment conducted in non horizontal orientation [START_REF] Lips | Physical mechanisms involved in grooved flat heat pipes: experimental and numerical analyses[END_REF] showed that the presence of nucleate boiling in the system does not constitute a limit as it is generally stated in the literature. In all cases, dryout of the evaporator is due to the capillary limit. All these investigations have been made under normal gravity conditions. But heat pipes are often used in space applications: it would be interesting to perform identical tests under micro gravity, in order to determine if the conclusions of this study can be extended to this case. In any case, a better understanding of these phenomena is necessary, particularly to theoretically predict the operation limit in case of nucleate boiling. Nucleate boiling was also observed in FPHP 5 and 6 for similar heat fluxes. Conclusions were the same. For FPHP 2, this phenomenon was not observed because the evaporator area is very large and thus capillary limit was observed for heat fluxes lower than 1 Wcm -2 , before the onset of nucleate boiling.

On the contrary, the performance of the heat pipe obtained with the association of grooves and meshes (FPHP 3) is not as high as one could expect [START_REF] Lefèvre | Experimental investigations of flat plate heat pipes with screen meshes or grooves covered with screen meshes as capillary structure[END_REF] regarding the capillary limit. Indeed, while this capillary structure enables to work in tilted unfavourable position, which was not possible with the grooved heat pipe (FPHP 2), a clear nucleate boiling limitation is observed for rather small heat fluxes (~ 0.4 W/cm²). This dryout is brutal and takes place on all the surface of the FPHP, which was not the case for FPHP2 when the capillary limit was encountered. This dryout is probably due to the rapid expansion of bubbles, which grow between the screen mesh layer and the grooves, rather than outside of it, because of the capillary pressure barrier imposed by the meshes. As a result, bubble growth pushes away the liquid from the grooves. As the screen mesh layers are not able to drain the liquid on the entire surface, the capillary structure suddenly dries out after the boiling incipience.

The observations made inside FPHPs have increased considerably the knowledge on these systems. Confocal microscopy enables to measure the vapor and liquid pressure difference along the capillary structure. These measurements, associated with temperature measurements enable the estimation of the thermophysical properties of the capillary structure by comparison with an appropriate model.

AN ANALYTICAL MODEL FOR THE COOLING OF MULTIPLE ELECTRONIC COMPONENTS

This section presents a 2D analytical solution for both the liquid and vapor flows inside a FPHP coupled to a 3D analytical solution for the temperature inside the FPHP wall. The thermal model is able to calculate the part of the heat flux transferred only by heat conduction in the wall from the heat transferred by change of phase.

Equations of the model

The model was already described in previous articles [START_REF] Lefèvre | Coupled thermal and hydrodynamic models of flat micro heat pipes for the cooling of multiple electronic components[END_REF][START_REF] Revellin | Experimental validation of an analytical model for predicting the thermal and hydrodynamic capabilities of flat micro heat pipes[END_REF] to which the reader should refer for further details.

The geometry of the FPHP is shown in Fig. 13. It consists of a flat plate of a × b rectangular dimensions. The electronic components and the heat sinks can be located anywhere on the FPHP and have different heat transfer rates. The rest of the surface is adiabatic. The wall of the FPHP is made of a material of thermal conductivity  s and its height is equal to c. The capillary structure is modeled by considering a porous medium of permeability K, thermal conductivity  p and height H p . The liquid inside the porous medium has a dynamic viscosity  l , a heat conductivity  l and a density  l . The equivalent thermal conductivity of both the liquid and the porous medium is equal to  eq . The vapor space height is equal to H v , and  v and  v are the vapor thermal conductivity and dynamic viscosity, respectively. The thermal properties are supposed to be constant. They are calculated at the saturation temperature T sat .

The 3D heat conduction equation is solved in steady state by considering adiabatic conditions in x = 0, x = a, y = 0 and y = b. In z = c, a heat flux, which depends on the location and the heat transfer rate of the heat sources and the heat sinks is imposed. In z = 0, a Fourier boundary conditions is considered with a heat transfer coefficient function of both the thickness and the thermal conductivity of the capillary structure. By considering these boundary conditions, the temperature field T(x,y,z) in the wall of the FPHP can be expressed by Fourier's series:

                  b y n a x m A C z y x T m n mn   cos cos ) , , ( 0 0 1 (1)
where C 1 is a constant and A mn are functions of the location and of the power of the heat sources and heat sinks. They also depend on the thickness and the equivalent thermal conductivity of the capillary structure.

Wall( s ) Electronic components Heat sinks b a 0 x 0 y A A Capillary structure (K, µ l ,  l,  eq ) Vapor space (µ v ,  v ) H v H p A-A z x 0 c
Fig. 13 Schematic of the FPHP for the model [START_REF] Lefèvre | Coupled thermal and hydrodynamic models of flat micro heat pipes for the cooling of multiple electronic components[END_REF] Once the temperature field is calculated, it is possible to calculate the evaporation and condensation mass flow rates at each point of the system by deriving the temperature field in z = 0. A 2D hydrodynamic model, based on Darcy's law and on mass balance equations, is used to calculate the liquid and vapor velocities and pressures in the capillary structure. The velocities are equal to zero in x = 0, x = a, y = 0 and y = b. By considering these boundary conditions, the pressure field for both the liquid and the vapor, can also be expressed by Fourier's series:

                  b y n a x m B C y x P m n mn   cos cos ) , ( 0 0 2 (2)
where C 2 is a constant depending on  l ,  l and K for the liquid and  v ,



v and H v for the vapor. B mn are functions derived from the thermal model.

The maximum heat transfer capability of the FPHP is obtained when the maximum capillary pressure is equal to the sum of the pressure drops in the liquid P l and the vapor P v and the hydrostatic pressure P g that can be either positive or negative, depending on the location of the heat sources and the heat sinks:

g v l cap P P P P        (3)
The capillary pressure can be calculated using the following classical expression [START_REF] Faghri | Thermal characteristics of conventional and flat miniature axially grooved heat pipes[END_REF], which results from the Young-Laplace law:

eff cap r P  2   (4)
where r eff is the effective pore radius and  is the surface tension of the fluid.

Estimation of the permeability and the equivalent thermal conductivity by comparison with experimental data

The comparison between the model and experimental data enables the estimation of both the permeability and the equivalent thermal conductivity of the capillary structure. When temperature measurements are available along the FPHP wall, the thermal conductivity is obtained when the model fits the experimental data. One can note that if the distance between the heat sources and the heat sinks is high enough, it is possible to differentiate the thermal conductivity at the condenser and at the evaporator [START_REF] Revellin | Experimental validation of an analytical model for predicting the thermal and hydrodynamic capabilities of flat micro heat pipes[END_REF] using the same model. When pressure measurements (deduced from confocal microscopy measurements) are available, the permeability is obtained when the model fits the experimental data. Otherwise, an estimation of the permeability can be obtained by considering the heat transfer rate for which the dryout of the evaporator is reached. If the maximum capillary pressure of the capillary structure is known, an estimation of the permeability is obtained when the sum of the pressure drops in the liquid and the vapour, which is a function of the permeability, is equal to the capillary pressure.

As an example, we present in this section the comparison between the model and experimental results obtained with FPHP 1 [START_REF] Lefèvre | Experimental investigations of flat plate heat pipes with screen meshes or grooves covered with screen meshes as capillary structure[END_REF]. The capillary structure is made of two CuSn 325 square screen mesh layers. The FPHP is filled with methanol. The heat source of surface 55.1×96.5 mm 2 is located in the middle of the FPHP. Two water heat exchangers of surface 30×90 mm 2 are located on each side of the system (Fig. 14).

Water heat exchangers

Heat source (30 × 90 mm 2 )

Fig. 14 Locations of the heat sink and the heat source on the FPHP 1 Fig. 15 presents the temperature profile in horizontal orientations for a heat transfer rate equal to 15 W. Fig. 16 presents the maximal temperature difference between the heat source and the heat sinks in horizontal orientation vs. the heat transfer rate of the heat source. Linear characteristics are obtained until a threshold heat transfer rate of 82 W. Below this value, the thermal resistance is equal to 0.14 K/W and can be compared to the thermal resistance of the copper plate alone (0.62 K/W).

In the model, the thickness of the capillary structure is set to 140 µm, which corresponds to twice the thickness of a CuSn mesh screen layers. The maximum capillary pressure is calculated with Eq. ( 4) by considering that the effective radius is equal to half the distance w between two fibers (Fig. 2). For methanol, P cap is equal to about 2000 Pa. In the model, the permeability is adjusted until the pressure drops in the liquid and the vapor, calculated for the threshold heat transfer rate of 82 W, is equal to the capillary pressure. The permeability of the meshes is estimated to 0.5510 -10 m².

For a mesh with a fiber diameter equal to d and a distance between two fibers equal to w (Fig. 2), the permeability K can be expressed as [START_REF] Faghri | Thermal characteristics of conventional and flat miniature axially grooved heat pipes[END_REF]:

               w d N Nd d K 1 4 05 . 1 1 1 122 2 3 2     (5)
where  is the porosity. For this mesh, d = 35 µm and w = 42 µm. Thus, the permeability calculated with Eq. ( 5) is equal to 0.1810 -10 m², which is 3 times lower than that estimated experimentally. Q (W) Fig. 16 Maximal temperature difference vs. heat transfer rate; horizontal location [START_REF] Lefèvre | Experimental investigations of flat plate heat pipes with screen meshes or grooves covered with screen meshes as capillary structure[END_REF] Fig. 17 presents an example of the comparison between the model and the measured temperatures for a heat flux of 82 W. The equivalent thermal conductivity that fits at best the experimental data is equal to 0.23 W/mK. It has to be noted that this equivalent thermal conductivity is close to that of methanol ( = 0.2 W/mK). For a mesh with a fiber diameter equal to d and a distance between two fibers equal to w (Fig. 2), the equivalent thermal conductivity depends on both the liquid and the mesh thermal conductivities  l and  s [START_REF] Faghri | Thermal characteristics of conventional and flat miniature axially grooved heat pipes[END_REF]:

            s l s l s l s l l eq                      ) 1 ( ) 1 ( (6)
The equivalent thermal conductivity calculated with Eq. ( 6) is equal to 0.44 W/mK, which is twice higher than that estimated experimentally. The permeability estimated experimentally is 3 times higher than that calculated theoretically while the experimental equivalent thermal conductivity is 2 times lower. Both discrepancies can be partly explained by an underestimation of the real thickness of the screen meshes. Indeed, as the screen meshes are not sintered to the wall, the contact with the wall is most likely imperfect, which leads to an increase of the actual thickness of the capillary structure. However, the underestimation of the real thickness of the capillary structure is not sufficient to explain such important differences. The reliability of the usual laws for both the permeability and the equivalent thermal conductivity can be questioned, as it was already questioned for grooved capillary structures [START_REF] Revellin | Experimental validation of an analytical model for predicting the thermal and hydrodynamic capabilities of flat micro heat pipes[END_REF]. Lips et al (2010a) also showed experimentally that the usual laws strongly overestimate the equivalent conductivity of longitudinal grooves. data (Q = 82 W;  eq = 0.23 W/mK) Finally, these different comparisons show that there is a real need for accurate equivalent thermal conductivity correlations for the different capillary structures encountered in practice. It has to be noted that for crossed grooves, Lips et al (2010c) could not compare their experimental thermal conductivity to such a theoretical law because no correlation is available in the literature for this kind of geometry. On the other hand, Lips et al (2010c and2011) showed that satisfactory models are available for the determination of the permeability for grooved capillary structures. However, the present study emphasizes that it is not the case for capillary structure made of metallic meshes.

Fig. 18 presents the equivalent thermal conductivity of the capillary structure as a function of the heat transfer rate Q. These results have been calculated by comparing the analytical model to the experimental data of Fig. 16. The equivalent thermal conductivity is rather constant for heat transfer rates between 45 W and 82 W. It decreases beyond 82 W, due to the beginning of the dryout of the capillary structure. For increasing heat fluxes from Q = 0 W to Q = 45 W, the thermal conductivity increases from a very small value (0.07 W/mK) to a constant value, which can be explained by a slight overfilling for small heat fluxes. Heat transfer rate (W) Fig. 18 Equivalent thermal conductivity versus power (estimated from experimental results of Fig. 16)

Application to the cooling of several electronic components

Fig. 19 presents the temperature field for the FPHP in horizontal orientation with three heat sources and two heat sinks located on its shorter edge. The properties of the capillary structure are those estimated in the previous sections, i.e. an equivalent thermal conductivity equal to 0.23 Wm -1 K -1 and a permeability of 0.5510 -10 m². The heat sink size and location are the same as the water heat exchangers on each side of the FPHP. The total heat transfer rate is equal to 75 W and is supposed to be equally distributed into 2 dissipative components of area 1010 mm² each and one dissipative component of area 2020 mm². The maximum temperature difference reaches 20 K. Just as an illustration, one can note that an aluminum plate (=165 Wm -1 K -1 ) of thickness 13 mm (i.e. more than 4 times thicker than a FPHP of 3 mm) would present the same thermal performance (Fig. 20). The maximum temperature is reached under the small heat sources, where the heat flux is the highest.

CONCLUSIONS

A synthesis of observations made inside the capillary structure of six different flat plate heat pipes (FPHPs) has been presented. Measurements of the liquid-vapor interface have been provided using confocal microscopy. This non intrusive technique enables the measurements of liquid film of very small thickness (down to 2 µm). These results are very useful to understand the physical mechanisms inside FPHPs that are generally characterized only with temperature measurements, the system being opaque. The results were used to validate FPHP models. The effect of the interfacial shear stress was found to be negligible in all the experimental conditions. On the contrary, we showed that the vapor space thickness has a major influence on the liquid distribution inside the system and thus the thermal performances of FPHPs. It was also shown that nucleate boiling does not constitute an operating limit in grooved heat pipe as it is generally stated in the literature. On the contrary, when meshes are plated against a grooved capillary structure, a strong boiling limit is observed for rather small heat fluxes.

The comparison with an analytical model shows that the equivalent thermal conductivity of the meshes is close to the thermal conductivity of the methanol. This result is not as high as one could expect in comparison with theoretical results. On the contrary, the permeability estimated experimentally is higher than that calculated theoretically. This result confirms that new laws have to be developed to better describe both the permeability and the equivalent conductivity of any kind of capillary structures. Hydrodynamic and thermal simulations show the ability of the flat plate heat pipe to cool several electronic components located on a printed circuit board. The maximum heat transfer rate in horizontal location is around 80 W for a 0.2 m long card.

Fig. 1 Fig. 2 Fig. 3

 123 Fig. 1 Schematic of FPHP 1 (Lefèvre et al., 2012); length in mm

Fig. 4 Fig. 5

 45 Fig. 4 Schematic of FPHP 2 (grooves) or FPHP 3 (grooves and meshes)

Fig. 9

 9 Fig.9Liquid-vapor interface in FPHP 5 (dimensions in m)(Lips et al., 2010c)

  Fig. 15 Temperature field for a heat transfer rate of 15 W in horizontal location

Fig. 17

 17 Fig. 17 Comparison between the analytical model and experimental

Fig. 19

 19 Fig. 19 Temperature field on the FPHP with 3 electronic components

Fig. 21

 21 Fig.21presents the liquid pressure field inside the screen meshes. The maximum pressure difference inside the capillary structure is lower than 1700 Pa, which is below the capillary limit (2000 Pa).

Fig. 21

 21 Fig. 21 Liquid pressure in the screen meshes

  P pressure (Pa) Q heat transfer rate (W) r eff effective radius (m) T temperature (K) w distance between two fibers (m) x, y, z coordinates (m)


Xavier Dolques
email: xavier.dolques@inria.fr

Marianne Huchard

Florence Le Ber
email: florence.leber@engees.unistra.fr

Clémentine Nebut

Relational Data Exploration by Relational Concept Analysis

is an extension to FCA considering several contexts with relations between them. Often used to extend the knowledge that can be learned with FCA, RCA also meets the issue of combinatorial explosion. The initial specification of RCA implies a monotonic growth of the number of concepts and an exhaustiveness of all the concepts that can be obtained when a fixed point is reached. In this position paper we propose a different specification of RCA that permits an interactive exploration of the data by letting the choice of the user for each step. This change will permit to handle richer relational data in a more flexible way by restraining the relations explored at each step hence reducing the number of created concepts.

Introduction

Relational Concept Analysis (RCA) [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF] is based on iterative use of the classical Formal Concept Analysis algorithm to handle relational data: formal objects are described with formal attributes, and with their relationships with formal objects. Because RCA groups formal objects using relationships to formal objects at any distance, it often comes with a combinatorial explosion, and patterns of interest are difficult to extract from the huge set of built concepts. Various strategies can be used to cope with this complexity, including separating the initial formal object sets into smallest ones after a first analysis, or introducing queries [START_REF] Azmeh | Querying relational concept lattices[END_REF]. Here we focus on the use of RCA to interactively explore data by letting the user choosing at each step of the iteration of FCA which contexts (formal and relational) he or she would like to use.

The context of this research is the FRESQUEAU project 4 which aims at developing new methods for studying, comparing and exploiting all the parameters available concerning streams and water areas. In this project, different approaches of knowledge discovery (including FCA) are tested and combined in order to better assess the ecological functioning of such hydrosystems.

In this paper we first outline the RCA process to highlight potential variation points that would promote exploration. Then we conclude with a short discussion.

The RCA algorithm

Algorithm 1 outlines the main steps followed by RCA to build groups of objects by considering attributes and object-object relations [START_REF] Huchard | Relational concept discovery in structured datasets[END_REF]. The input of RCA is a Relational Context Family RCF = (K, R) composed of n object-attribute contexts

K i = (O i , A i , I i ), i in 1.
.n, and m object-object contexts R j , j in 1..m.

1: proc Multi-Fca( In: (K, R) a RCF, 2: Out: L array [1..n] of lattices) 3: p ← 0 ; halt ← false 4: for i from 1 to n do 5:

L 0 [i] ← Build-Lattice(K 0 i ) 6: while not halt do 7:

p + + 8:

for i from 1 to n do 9:

K p i ← Extend-Rel(K p-1 i , L p-1 ) 10: L p [i] ← Update-Lattice(K p i ,L p-1 [i]) 11: halt ← i=1,n Isomorphic(L p [i], L p-1 [i])
Algorithm 1: The RCA process For R j ⊆ O i × O j , we call O i the domain and O j the range. The initialization step (Lines 4-5) consists in building, for all i in 1..n, the lattice L 0 [i] associated with the context K i .

At step p:

-Extend-Rel appends to K i the relations obtained by scaling object-object relations for which K i is the domain. The scaling consists in including the object-object relations as relational attributes. They are obtained using the concepts of the lattices of step p -1 and a scaling operator (i.e. ∃, ∀). For example, if the scaling operator ∃ is chosen for scaling a given relation R j , R j columns are replaced by attributes of the form ∃R j : C, where C is a concept in the lattice built upon objects of the range of R j at step p -1. An object o of the domain of R j owns ∃R j :

C if R j (o) ∩ Extent(C) = ∅.
-Update-Lattice updates the lattices of step p -1 in order to produce, for i in 1..n, the lattice L p [i], associated with K i concatenated to all scaled object-object contexts with K i domain.

The algorithm stops when a fix-point is obtained: a lattice family isomorphic to the lattice family obtained at the previous step is obtained and leaves unchanged concept extents.

The advantage of such a process is that the obtained concepts have in their intent relations to other concepts in addition to classical attributes. Those relations permit the extraction of patterns built from several interconnected concepts as shown in [START_REF] Dolques | From transformation traces to transformation rules: Assisting model driven engineering approach with formal concept analysis[END_REF] and [START_REF] Dolques | Fixing generalization defects in UML use case diagrams[END_REF] that could not be easily obtained with the classical process of Formal Concept Analysis.

However, one problem of such a process is the potential difficulty to apprehend the result. In past work in the domain of Model Driven Engineering, data extracted from models of medium size have been easily handled by RCA. Nevertheless in a context of data mining the data are of a different scale. Especially when only small patterns are needed while many relations connect the objects and these relations form a cyclic entity-relationship diagram, the result will appear hard to understand by a human due to the number of concepts to consider simultaneously and the computation time will be considered as a handicap. In such cases, we think it will be more practical to have a kind-of exploratory approach.

Table 1 shows main possible variations on the algorithm to go towards an exploratory approach. We have enumerated the variation points of the algorithm that could affect the result by changing the contexts considered at each step. We have proposed for each variation point an alternative scenario from the process previously described that involves the user by asking him or her to perform selections. All those variations or only a subset of them can be applied depending on the granularity needed.

Table 1. Variations for the exploratory approach initialization step, L4-5 Build lattices for selected object-attribute contexts concatenated to selected object-object contexts.

Extend-Rel, L9

Rather than using all relations and scaling all objectobject relations, select a subset of the RCF and scaling operators for each selected object-object context. Note: lattices for ranges of the selected object-object relations should have been calculated in a previous step (not necessarily p -1). At this step, object-attribute contexts can also be selected and the corresponding lattice can be built. Update-Lattice, L10 Only the lattices for the selected relations are updated.

halt, L11

The decision is left to the expert when to stop (or the fix-point is obtained)

Conclusion and discussion

In this position paper, we have outlined an exploratory approach for assisting the use of Relational Concept Analysis in a way that would better fit a data mining process. We have several motivations for disturbing the original RCA process: to go faster to a relevant result by calculating less lattices (preferably lattices of interest), to cope with the inherent complexity of mining relational data, or to let the expert guiding the discovery process based on his/her intuition and the knowledge patterns that appear on-the-fly. In our current approach, the data are given by experts, so we don't use exploration in the sense of [START_REF] Rudolph | Relational exploration: combining description logics and formal concept analysis for knowledge specification[END_REF], unless the data exploration. Many questions are raised by this way of extracting concepts from relational data. Initialization of the process has an impact for the later discovered structures. It can accelerate the process, if the selected object-object relations contain the main information for the expert, or reversely, it can discard the expert from the relevant information. Nevertheless, the most serious problem comes from the fact that going step-by-step leads to a non-monotonic concept construction and one could build several cases where the process diverges (iterates between recurrent configurations). In the original RCA process, when the fix-point is attained, lattices of the two last steps are isomorphic, thus when a concept references another through a relational attribute, the latter can be found in the same step appropriate lattice. But in the exploratory process we propose, when a concept references another through a relational attribute, the latter is in a lattice of a previous step and may itself reference a concept in a previous step, etc. We should find solutions for presenting the expert information easy to interpret these situations. Nevertheless, we think that such an exploratory approach should be more practical than the "brute force" that iterates until the fix-point and gives results that an expert will hardly understand.

This work was partly funded by french contract ANR11_MONU14.[START_REF] Huchard | Relational concept discovery in structured datasets[END_REF] http://engees-fresqueau.unistra.fr/


Querying and specific relational schemes Erratic RCA Growth process Conclusion and perspectives RCA -Initial Lattice building At the beginning, only the object-attribute contexts are used to build the foundation of the concept lattice family RCA Relational Concept Analysis Querying and specific relational schemes Erratic RCA Growth process Conclusion and perspectives RCA -Introducing relations as relational attributes Because basilic, ham, mozzarella, olive and tomato are connected via producedIn to Concept_28 extent basilic, ham, mozzarella, olive, tomato own the relational attribute ∃producedIn.Concept_28

RCA

Relevant implications

In Pizzas: contains at least an ingredient produced in Switzerland ⇒ contains at least an ingredient produced in Norway

Relational Context Family (RCF)

A RCF F is a pair (K , R) with:

K is a set of object-attribute contexts K i = (O i , A i , I i ) R is a set of object-object contexts R j = (O k , O l , I j ),
(O k , O l ) are the object sets of formal contexts (K k , K l ) ∈ K 2 I j ⊆ O k × O l K k is the source/domain context, K l is the target/range context. we may have K k = K l .

Pizza RCF For each relational context

K = K People , K Pizza , K Ingredient , K Country R = R eats , R contains , R producedIn ,
R j = (O k , O l , I j ), a scaled context R * j = (O k , A, I j ) is created.
A is a set of relational attributes a = S R j .C, where C is in the concept set of a lattice built on objects of O l , denoted by

L n l I j contains (o, a) iff S(R j (o), Extent(C)) is true.
S is a scaling operator, the most used are: The homogeneity of concept descriptions is kept: all attributes are considered as binary (even relational attributes).

S ∃ (R j (o), Extent(C)) is true iff R j (o) ∩ Extent(C) = ∅. S ∀∃ (R j (o), Extent(C)) is true iff R j (o) ⊆ Extent(C) ∧ ∃x ∈ R j (o), x ∈ Extent(C) RCA Operator Attribute form Condition Universal (narrow) ∀ r : c r (o) ⊆ Ext(c) Covers ⊇ r : c r (o) ⊇ Ext(c) Existential (wide) ∃ r : c r (o) ∩ Ext(c) = ∅ Universal strict ∀∃ r : c r (
Standard algorithms for building concept lattices can be directly reused.

RCA

After the relational scaling, the scaled relations are concatenated to the appropriate object-attribute relation (same object domain). This forms new relations (one per object set) which describe the objects by their classical attributes and their relational attributes. Concept lattices are built using these relations. A relational query with variables

- → v is an expression ϕ( - → v )
, which is a conjunction of relational query atoms involving variables of V and objects in O i , where i ∈ {1...n}.

RCA

We search for people, pizzas, ingredients and a country s.t. the country is Italy, people eat the pizzas, which contain ingredients produced in the country P K People (q people ) ∧ P K Pizza (q pizza ) ∧ P K Ingredient (q ingredient ) ∧ P K Country (q country ) ∧ P Italy (q country ) ∧ P eats (q people , q pizza ) ∧ P contains (q pizza , q ingredient ) ∧ P producedIn (q ingredient , q country ) RCA An example of a modified object-attribute context Variables are added as new objects, here q-person is added in K People . It may have attributes depending from the query.

I People

Amedeo Flavia Dagrun Lars Uma

Amedeo × Flavia × Dagrun × Lars × Uma × q-person

RCA

An example of a modified object-object context

We look for people (q-people) connected to pizzas (q-pizzas)

Dronning Kampanje Margherita Marinara Norwegian Regina q-pizza Amedeo × × Flavia × Dagrun × × Lars × Uma × × q-person X

RCA

Answers are below the concept introducing q-people.

We see patterns in answers (e.g. similar consumer profiles Lars-Uma; Flavia-Dagrun) RCA Answers for pizzas are below the concept introducing q-pizza.

Specific relational schemes

In a sense, when we choose a RCF, we choose a relational scheme allowing to search data with a specific idea in mind.

Relation

Step 1

Step 2 We denote this step by: Animals+lives(Places)+moves(TMotion_T1form) -> TAnimals_T3form Pre-clustering a dataset for scalability An example of a unique dataset (object-attribute context)

Step 3 . . . eats ∀ r : c ∃ r : c ∃ r : c ∃ r : c contains ≥ n r : c ∀ r : c ∃ r : c ∃ r : c producedIn ≥ n r : c ∀ r : c ∃ r : c ∃ r : c hasForNational ∃ r : c ∀ r : c ∃ r : c ∃ r : c . .
1 2 3 4 z1 × z2 × z3 × a1 × a2 × a3 × b1 × b2 × b3 × c1 × c2 × c3 × c4 × c5 × c6 × d1 × × d2 × × d3 × ×
× z2 × z3 × a1 × a2 × a3 × b1 × × b2 × × b3 × × c1 × c2 × c3 × c4 × c5 × c6 × d1 × × d2 × × d3 × × RCA 1 z1 × z2 × z3 × 2 a1 × a2 × a3 × 3 b1 × b2 × b3 × 4 c1 × c2 × c3 × c4 × c5 × c6 × 1 2 3 4 d1 × × d2 × × d3 × × I r

  o) ⊆ Ext(c) and r (o) = ∅ Qualified cardinality restriction ≥ n r : c r (o) ⊆ Ext(c) and |r (o)| ≥ n Cardinality restriction ≥ n r : L |r (o)| ≥ n RCA Some properties of relational scaling:

  including: class model constructions, use case model reengineering, model transformations learning, analyzing and fixing bad smells in software, component architecture extraction, Web services classification ... Artificial Intelligence including: ontology constructions, data mining Making RCA practical We can play with the scaling operators On specific (small parts of the) contexts, we can add queries We can apply RCA on part of the RCF, and stop at a given step We can observe the growth of (inferred) knowledge as an indicator /astronomy.swin.edu.au/ gmackie/humour.html RCA Relational Concept Analysis Querying and specific relational schemes Erratic RCA Growth process Conclusion and perspectives Relational queries Consider this query: We search for people, pizzas, ingredients and a country s.t. the country is Italy, people eat the pizzas, which contain ingredients produced in the country The answers are the tuples we can read from the schema, e.g. < Flavia, Marinara, Olive, Italy > < Dagrun, Marinara, Olive, Italy > < Amedeo, Regina, Mozza, Italy > (etc.) Work with Z. Azmeh, A. Napoli, M.A. Rouane-Hacène, P. Valtchev RCA With FCA/RCA, we may add two interesting views: classify the answers (group answers concerning Flavia and Dagrun because they are based on the marinara pizza) classify all objects to understand their relations w.r.t. the query Lars' preferences are not very far away from those of Uma, both like the Norwegian pizza; besides the Dronning pizza is not very different from the Norwegian pizza most of the pizzas which are answers contain tomato RCA Approach Expressing the relational query to navigate the lattices A companion guiding algorithm with user interaction

I

  Food + I eatenBy (TAnimals_T 6form) ∃We will denote this kind of data by: Food+eatenBy(at a step, ex. 2I Food + I eatenBy (TAnimals_T 6form)∃ the lattice Motion reduced to a concept, ex. 3 I Animals + I lives + I moves(TMotion)

  R hasCitizen Ingredient , A Ingredient , I Ingredient ) Here object (rows) are described by identifiers (columns), more relevant attributes can be used Pizza , O Ingredient , I contains )

		Relational Concept Analysis Relational Concept Analysis
	Querying and specific relational schemes Querying and specific relational schemes
				Erratic RCA Erratic RCA
			Growth process Growth process
		Conclusion and perspectives Conclusion and perspectives
	Example of object-attribute context K Ingredient Example of object-object context R contains
	K Ingredient = (O I Ingredient basilic R contains = (O I contains Dronning chicken Kampanje cream Margherita ham Marina mozzarella Norwegian mushroom Regina	basilic basilic × ×	chicken chicken × ×	cream cream × × × ×	ham ham × × ×	mozzarella mozzarella × × ×	mushroom mushroom × × ×	olive olive × ×	tomato tomato × × ×	salmon salmon ×	swisscheese swisscheese × × ×
	olive							×
	tomato								×
	salmon									×
	swisscheese										×
						RCA RCA

RCA At a further step ... basilic, ham, mozzarella, olive, tomato grouped because they own the relational attribute ∃producedIn.Concept_28 RCA At a further step ... Dronning, Regina, Margherita and Marinara are connected via contains to Concept_40 extent several connection strengths: All are connected to at least one italian ingredient; Margherita and Marinara are besides connected only to italian ingredients; Margherita and Regina are connected to more than 3 italian ingredients, etc. RCA At a further step ... Dronning, Regina, Margherita and Marinara are grouped, they own ∃contains.Concept_40 RCA Alternatively ... Margherita and Marinara are grouped, they own ∀contains.Concept_35 (in the whole process the concept numbers change, this is explained later) RCA Relational scaling is the process by which links are established between objects and concepts.

Italy Binary predicates associated with a Relational Context Family Let

	Two main implementations
	By looking in each lattice for the searched relational attributes
	By classifying variables of the query

RCA

Unary predicates associated with a formal context

We associate with a formal context K several unary predicates P K : to express that an object o belongs to the formal object set O P a : to express that an object o owns a specific attribute a ∈ A E.g. P K People P us consider a RCF (K, R). To every r ij relation in R, we associate a binary predicate P r ij : to express that a pair of objects is connected via the relation E.g. P eats RCA Definition (Relational query) Let V denote a finite set of variables. A relational query atom is: either an expression P(v 1 ) where v 1 is a variable from V and P a unary predicate associated with a formal context in K, or P r ij (v 1 , v 2 ), where v 1 and v 2 are two variables from V or a variable and an object of O i , i ∈ {1...n}, and P r ij is a binary predicate associated with a relation r ij in R.

  : at one step, several scaling operators can be applied to the same relational context (giving several scaled contexts based on a same

	Relational Concept Analysis Relational Concept Analysis Relational Concept Analysis Relational Concept Analysis
	Querying and specific relational schemes Querying and specific relational schemes Querying and specific relational schemes Querying and specific relational schemes
	Erratic RCA Erratic RCA Erratic RCA Erratic RCA
	Growth process Growth process Growth process Growth process
	Conclusion and perspectives Conclusion and perspectives Conclusion and perspectives Conclusion and perspectives
	Outline Strange animals Erratic RCA Erratic RCA
	. To discover for example: . . . People that eat only pizza containing at least n ingredients . . . . . . produced in Norway Relational Concept Analysis Querying and specific relational schemes Erratic RCA Growth process Variations on the RCA algorithm to focus step-by-step on part of the data for scalability to launch the process in specific cases An example for giving some insight See Xavier Dolques' talk for more details I Motion geek city pizza I lives lake forest city flamingo × flying squirrel × geek × Imoves fly walk flamingo × flying squirrel × geek × I offers artemia lichen pizza lake forest city × by relational scaling geek × × × When a lattice exists on a set of objects: introduce relations with flying squirrel × × geek × × × An example of approach Successively choose a set of objects, and introduce the relations this set of objects is a domain When no lattice exists on a set of objects: introduce relations without relational scaling I Animals + I lives + I moves lives:lake lives:forest lives:city moves:fly flamingo × flying squirrel × × × × × flamingo I Animals + I lives + Imoves lives:lake lives:forest lives:city moves:fly moves:walk moves:walk walk flying squirrel forest lichen Introduce relation without relational scaling fly I Animal flamingo I Places lake I Food artemia Building a lattice at a step, ex. 1 Introduce relation with relational scaling
	Countries where at least one national eats at least one pizza that contains at least one food produced in Italy Conclusion and perspectives I eatenBy TMotion_T1form, TAnimals_T1form, TPlaces_T1form, TFood_T1form We will denote this kind of data by: flamingo flying squirrel geek artemia × Animals+lives(Places)+moves(Motions)
	relational context) http://www.cafepress.com/+labyrinth+greeting_cards lichen pizza We denote this step by: Animals+lives(Places)+moves(Motions) -> TAnimals_T6form × ×
	RCA RCA RCA RCA RCA RCA RCA RCA

Note

RCA

For the rest of the example, these lattices are denoted

  inspired by experiments in IS applications done with: B. Amar, A. Osman Guedi, A. Miralles, C. Nebut, T. Libourel RCA On the pizza example, successive steps show the growth of conceptual knowledge

	Relational Concept Analysis Relational Concept Analysis Relational Concept Analysis
	Querying and specific relational schemes Querying and specific relational schemes Querying and specific relational schemes
	Erratic RCA Erratic RCA Erratic RCA
	Growth process Growth process Growth process
	Conclusion and perspectives Conclusion and perspectives Conclusion and perspectives
	Outline Observing the concept lattice growth in RCA
	Lessons we can draw: Relational Concept Analysis step 0.
	concepts emerge step-by-step, only a partial view is given, which is interesting in an interactive process to understand how data are connected and concept formation Querying and specific relational schemes propagates
	we have to pay attention to possible on non-monotonic lattice concept formation Erratic RCA we may converge more rapidly (on other examples) applied to evolving datasets, to understand evolution of the step 1.
	to pre-cluster data before RCA construction Growth process Applications, interpretation of the lattices and perspectives: see Xavier's Talk step 2.
	Conclusion and perspectives
	step 3.
	RCA RCA RCA RCA

RCA http://astronomy.swin.edu.au/ gmackie/humour.html work

Pre-clustering a dataset for scalabilityAlternative view on same data, by dividing the dataset and the links


Christophe Lohou

Julien Dehos

An automatic correction of Ma's thinning algorithm based on P -simple points

Keywords: topology preservation, thinning algorithm correction, surface skeleton

published or not. The documents may come

An automatic correction of Ma's thinning algorithm based on P -simple points

Christophe Lohou, Julien

Introduction

In the image processing framework, thinning is a technique which extracts skeletons from objects. Such a representation has the advantage of being compact while conserving important features of objects like topology and geometry. Thinning has many applications such as compression, analysis and recognition [START_REF] Reniers | Skeleton-based hierarchical shape segmentation[END_REF]]. In a binary image, objects are represented by black points. The complement is represented by white points. Thinning consists of changing black points to white. It is generally done in successive iterations of deletions. Removing a point should preserve certain properties like topology. This leads to the essential notion of a simple point: a simple point is a point which can be removed without changing topology [START_REF] Kong | Digital topology: Introduction and survey[END_REF]].

The literature gives several kinds of 3D thinning algorithms. Parallel thinning algorithms proceed by removing black points in parallel. Implemented on appropriate computers, such algorithms can efficiently achieve thinning. The problem is that the notion of a simple point is not powerful enough to garantee topology preservation in this context. For example, consider an object made of two neighboring points. Both points are simple but removing them both does change topology. This problem cannot occur by sequential processing because the deletion of the first point makes the second point become non-simple. To solve this problem, Bertrand has proposed the notion of P -simple points [Bertrand(1995a)]: a point of a set P is P -simple if it is simple when any subset of P is removed. Parallel thinning algorithms removing P -simple points have been proposed [Bertrand(1995b), [START_REF] Lohou | A 3D 12-subiteration thinning algorithm based on P -simple points[END_REF], [START_REF] Lohou | A 3D 6-subiteration curve thinning algorithm based on P -simple points[END_REF], [START_REF] Lohou | Two symmetrical thinning algorithms for 3D binary images, based on P -simple points[END_REF]]. Such algorithms have remarkable topology-preserving property.

In this paper we propose another application of P -simple points: ensuring topology preservation of an existing parallel thinning algorithm. In [Ma(1995)], Ma proposes a 3D parallel thinning algorithm. This algorithm is one of the few thinning algorithms able to preserve surfaces and is used as a reference [Palágyi(2008), [START_REF] Lohou | Two symmetrical thinning algorithms for 3D binary images, based on P -simple points[END_REF]]. In [Lohou(2008)], one of the authors gives an object whose topology is not preserved by Ma's algorithm. This proves that the algorithm fails to preserve topology, which it should do. Here, we propose a topology preserving algorithm by using P -simple points to repair Ma's algorithm. As far as we know, this is the first time P -simple points are used to automatically correct an image operator.

This paper is organized as follows. Section 2 gives some basic notions of Digital Topology and presents P -simple points. Section 3 shows how to use P -simple points in a thinning algorithm. In section 4, we propose such an algorithm to correct Ma's. Section 5 gives some results and section 6 concludes.

Basic notions of Digital Topology

Neighborhoods and connected components

A point x ∈ Z 3 is defined by (x 1 , x 2 , x 3 ) with x i ∈ Z. We consider the three neighborhoods:

N 26 (x) = {x ′ ∈ Z 3 : max[|x 1 -x ′ 1 |, |x 2 -x ′ 2 |, |x 3 -x ′ 3 |] ≤ 1}, N 6 (x) = {x ′ ∈ Z 3 : |x 1 -x ′ 1 |+ |x 2 -x ′ 2 |+ |x 3 -x ′ 3 | ≤ 1}, and N 18 (x) = {x ′ ∈ Z 3 : |x 1 -x ′ 1 |+ |x 2 -x ′ 2 |+ |x 3 -x ′ 3 | ≤ 2} ∩ N 26 (x). We define N * n (x) = N n (x) \ {x}.
We call respectively 6-, 18-, 26-neighbors of x the points of x is not P -simple for X.

N * 6 (x), N * 18 (x) \ N * 6 (x), N * 26 (x) \ N * 18 (x). Such points are represented in Fig. 1 (a). Let X ⊆ Z 3 . The points belonging to X (resp. X, the complement of X in Z 3 ) are called black points (resp. white points). Axis and orientations used in this paper are given in Fig. 1 (b).

Two points x and y are said to be n-adjacent if y ∈ N * n (x) (n = 6, 18, 26). An n-path is a sequence of points x 0 , . . . , x k , with x i n-adjacent to x i-1 and 1 ≤ i ≤ k. If x 0 = x k , the path is closed. Let X ⊆ Z 3 . Two points x ∈ X and y ∈ X are n-connected if they can be linked by an n-path included in X. The equivalence classes relative to this relation are the n-connected components of X. The presence of an n-hole is detected whenever there is a closed n-path in X that cannot be deformed, in X, into a single point (see [START_REF] Kong | A digital fundamental group[END_REF]], for further details). In order to have a correspondence between the topology of X and that of X, we have to consider two different kinds of adjacency for X and for X [START_REF] Kong | Digital topology: Introduction and survey[END_REF]]: if we use an n-adjacency for X, we have to use another n-adjacency for X. In this paper, we only consider (n, n) = (26, 6).

Simple points and topological numbers

Let X ⊆ Z 3 . A point x ∈ X is said to be n-simple for X if its deletion does not "change the topology" of the image, in the sense that there is a bijection between the components and the holes of X and X and the ones of X \ {x} and X ∪ {x} (see [START_REF] Kong | A digital fundamental group[END_REF]] for a precise definition). In the following, we write x is simple instead of x is simple for X. In Fig. 2 (a), we may verify that x is simple. In Fig. 2 (b), X is a single connected component whereas X \ {x} is made of two connected components ({a, c} and {b}), therefore the topology of X is not preserved by the deletion of x, i.e. x is not simple.

The set composed of all n-connected components of X is denoted by C n (X). The set of all n-connected components of X and n-adjacent to a point x is denoted by C x n (X). Let #X denote the number of elements which belong to X. The topological numbers relative to X and x are the two numbers [Bertrand(1994)

]: T 6 (x, X) = #C x 6 (N * 18 (x) ∩ X) and T 26 (x, X) = #C x 26 (N * 26 (x) ∩ X) (in fact, T 26 (x, X) = #C 26 (N * 26 (x) ∩ X), since any 26- connected component of black points in N * 26 (x)
is inevitably 26-adjacent to x). These numbers lead to a very concise characterization of 3D simple points [START_REF] Malandain | Fast characterization of 3D simple points[END_REF], [START_REF] Bertrand | A new characterization of threedimensional simple points[END_REF]]:

x ∈ X is 26-simple if and only if T 26 (x, X) = 1 and T 6 (x, X) = 1. For example, in Fig. 2 (a), the points of N * 26 (x) ∩ X (resp. N * 18 (x) ∩ X) make a single 26-connected (resp. 6-connected and 6-adjacent to x) component. Thus (T 26 (x, X), T 6 (x, X)) = (1, 1); therefore x is simple. In Fig. 2 (b), N * 26 (x) ∩ X is constituted by two 26-connected components ({a, c} and {b}). N * 18 (x) ∩ X is made of a single 6-connected component 6-adjacent to x. Thus, we have, (T 26 (x, X), T 6 (x, X)) = (2, 1); therefore x is not simple.

P -simple points

This section recalls the definition of P -simple points and several properties of such points [Bertrand(1995a)].

In the following, we consider a subset X of Z 3 , a subset P of X and a point x of P . Definition 1 The point x is P -simple for X if for each subset S of P \ {x}, x is 26-simple for X \ S.

For example, in Fig. 2 (c), P = {x, a}. We may verify that x is simple for X \ {a}; therefore x is P -simple. In Fig. 2 (d), P = {x, a}. With S = {a}, we may verify that x is not simple for X \ S; therefore x is not P -simple.

We have the remarkable property that any algorithm removing subsets composed solely of P -simple points is garanteed to keep the topology unchanged [Bertrand(1995a)].

The following proposition permits to locally characterize P -simple points [START_REF] Bertrand | [END_REF]].

Proposition 1 The point x is P -simple if and only if:

       T 26 (x, X \ P ) = 1, T 6 (x, X) = 1, ∀y ∈ N * 26 (x) ∩ P, ∃z ∈ X \ P such that z is 26-adjacent to
x and to y, ∀y ∈ N * 6 (x) ∩ P, ∃z ∈ X and ∃t ∈ X such that {x, y, z, t} is a unit square.

For example, in Fig. 2 (c), x is P -simple because it concurs with the four conditions of Proposition 1. In Fig. 2 (d), x is not P -simple because the first condition is not satisfied (T 26 (x, X \ P ) = 2). In both examples, Proposition 1 makes it possible to consider only a few points around x to determine whether x is P -simple or not.

Thinning algorithms based on P -simple points

Let us consider an algorithm which removes P -simple points in parallel, in successive iterations. Since some points are deleted during an iteration, this algorithm thins objects. A skeleton is obtained when no more points can be removed. As shown in the previous section, removing subsets composed of solely P -simple points guarantees to keep the topology unchanged. Consequently, topology preservation, which is one of the most important features of a thinning algorithm, is automatically proved for such algorithms.

Algorithm 1 : P-SimpleThinningAlgorithm(X, C) → X 1: repeat 2:
{parallel labelling of points which belong to P } 3:

P ← ∅ 4:
for each point x in X, in parallel, do end for 15: until no points are deletable Algorithm 1 gives such an algorithm; where C denotes the condition a point x of X should satisfy to belong to P (the set of candidate points to deletion). Each iteration is composed of two passes. Thanks to P -simple points, the algorithm can examine points in parallel. Furthermore, using the local characterization of P -simple points (Proposition 1), the algorithm can consider limited neighborhoods. It is thus well-suited for parallel machines.

Algorithm 1 does not explain how to determine P (the set of candidate points for deletion). In [Bertrand(1995a)], Bertrand proposes that P contains the simple points of X to obtain a certain kind of skeleton.

Figure 3: The templates of Ma's algorithm. A point p satisfies a template if each disc is a black point, each circle is a white point, at least one square is a white point and at least one diamond is a white point.

A new thinning algorithm correcting Ma's algorithm

In the previous section, we have recalled how P -simple points can be used to conceive thinning algorithms. We now suggest a new application of P -simple points: to correct an existing thinning algorithm which fails to preserve topology. Indeed, a lot of parallel thinning algorithms (including Ma's algorithm) are based on "local" templates. Basically, they consist of removing in parallel and in successive iterations, all the points matching one of the given templates. A skeleton is obtained when no more points can be removed. However, when a templates-based thinning algorithm is proposed, its topology preservation should be proven afterward. This is very difficult because it implies considering a great number of configurations in a greater neighborhood than the N 26 neighborhood of the considered point. Thus, giving an analytical proof is difficult and computing the correctness of the algorithm cannot be done in reasonnable time using actual computers. That's why an error can be made easily, when a templates-based thinning algorithm is conceived. This is what has occured with Ma's algorithm. A correction could be made by changing the initial templates but, once again, proof has to be given, which leads us to the previously mentioned difficulties. In this section, we explain how to use P -simple points to correct, in a simple and effective manner, a templates-based thinning algorithm which fails to preserve topology.

Study of Ma's algorithm

This algorithm has been proposed in [Ma(1995)]. It is a 3D parallel thinning algorithm based on templates requiring access of up to 30 points to decide whether a point is deletable or not.

In [Ma(1995)], Ma gives the following definitions and rules:

• A black point is called border point if it is 6-adjacent to a white point.

• Definition 1.1: Let p be a black point of a 3D image. Then p is called an edge point if p has exactly one black 26-neighbor in N * 26 (p) or in any of the three orthogonal 3 × 3 planes containing p; p is called a non-edge point if it is not an edge point.

• Suppose p is a point in a 3D image. Let s(p), w(p) and d(p) be the south, west and down neighbors of p, respectively.

• Rule 2.1: Suppose all four corners of a unit lattice square are to be deleted. Then the corner with the smallest sum of coordinates is preserved if and only if it is non-simple after the other three corners are deleted.

• Let Ω be the set of all rotations and reflections of all three configurations (shown in Fig. 3). For each element T of Ω, a black point p is said to satisfy T if [it satisfies the corresponding template and]1 all of the following conditions are satisfied: parallel delete black point that satisfies Ω and is not preserved by Rule 2.1 3: until no points are deleted In [Lohou(2008)], it is shown that Ma's algorithm does not always preserve topology. Now, we propose an algorithm which corrects this problem.

       p is a non-edge

Our proposal

In section 3, we proposed a generic parallel thinning algorithm (Algorithm 1). First, this algorithm detects, in parallel, the points which verify a condition C. These points compose the set P . Then, the algorithm deletes P -simple points in parallel among the points of P .

To correct Ma's algorithm, we propose to remove P -simple points in parallel in successive iterations where P is precisely the set of points which would be deleted by Ma's algorithm. This is equivalent to Algorithm 1 where the condition C is "the point satisfies Ω and is not preserved by Rule 2.1".

Checking Rule 2.1 for a point x requires us to determine if some neighbors of x are to be deleted. This can be done by checking whether they satisfy Ω or not. This method means accessing a larger neighborhood of x (see [START_REF] Lohou | A 3D 12-subiteration thinning algorithm based on P -simple points[END_REF]] for further details). To avoid this, we can first find the points that satisfy Ω and, in another pass, determine which ones are preserved by Rule 2.1. This algorithm, denoted by LD09, is given in Algorithm 3.

Algorithm 3 : LD09(X) → X 1: repeat 2:
{parallel labelling of points which belong to P ′ } 3:

P ′ ← ∅ 4:
for each point x in X, in parallel, do end for 22: until no points are deletable LD09 is indeed a correction of Ma95. First, it removes P -simple points only, which ensures topology preservation. And finally, it can delete only the same points as Ma95. This use of P -simple points implies that LD09 preserves topology. On the contrary, a correction based only on a modification of the initial templates would have required a difficult and error-prone proof of the topology preservation.

We may notice that other algorithms can be derived from LD09. For instance, Rule 2.1 may be checked in the same time as the P -simpleness, which makes it possible to bypass the specific pass. Another algorithm can be defined by letting P be the set of points which match the templates and then removing P -simple points which are non-edge points and non-border points. We are currently working on these points and a few other ones [START_REF] Dehos | Analysis of new thinning algorithms derived from Ma's algorithm using P -simple points[END_REF]

Results

We have compared Ma's algorithm and ours thanks to 5 small synthetic objects, 5 large objects obtained by voxelisation and 1 object obtained by medical imagery (see Table 1. Some of these objects are depicted in Fig. 4. We have found that 3 objects have the same number of deleted points with both algorithms (for instance, letterD and Tz2), 8 objects have more deleted points with Ma's algorithm and no object has more deleted points with our algorithm. Furthermore, 6 objects have the same number of iterations with both algorithms (for instance, Bull), one object has more iterations with Ma's algorithm and 4 objects have more iterations with our algorithm (for instance, vertebra).

If we apply these algorithms to the same object, we can get different results after the first iteration, because LD09 removes some but not always all of the points removed by Ma95. Thus, the next iteration happens on different objects therefore the final results are difficult to compare. By its conception, our algorithm cannot delete more points of a given object than Ma's algorithm, during one iteration (columns 3 and 4 of Table 1. According to our tests, our algorithm generally deletes less points and performs more iterations than Ma's. However, we cannot prove anything from this. For example, as mentioned before, one object of our database is thinned by less iterations with our algorithm than with Ma's.

Fig. 5 shows the result of both algorithms applied to an object of the database. The initial object (a) is a dolphin obtained by voxelisation. The skeletons given by Ma's algorithm (b) and ours (c) are quite similar. However, we can see on their respective close-ups (d) and (e), that Ma's algorithm does not preserve the topology whereas ours does. For example, in (d), the stamp 1 depicts a voxel which is disconnected from the skeleton by Ma's algorithm. In the same way, the stamp 2 shows a hole created by the algorithm. We can see on (e) that our algorithm does not have these problems. From another viewpoint (f), we can notice that, like Ma's skeleton (g), our skeleton (h) presents medial faces. Finally, if the skeletons have common points (i), they also have points which are unique to themselves (j, k).

Conclusion

Up until now, P -simple points have been used to develop new topology-preserving thinning algorithms. In this paper, thanks to P -simple points, we have proposed an automatic correction of a templates-based thinning algorithm which fails to preserve topology. Like this latter, our algorithm allows us to extract medial-face skeletons. However, our algorithm ensures topology preservation. To our knowledge, it is the first time Psimple points are used for such an application. Our algorithm could be seen as a correcting patch for current applications using Ma's algorithm.

Figure 1 :Figure 2 :

 12 Figure 1: (a): The 6-neighbors (triangles), 18-neighbors (diamonds) and 26-neighbors (crosses) of x. (b): Axis and orientations.

Figure 5 :

 5 Figure 5: Result of both algorithms applied to a same object. (a): Initial object (1 202 772 black points). (b): Skeleton obtained with Ma's algorithm (1 153 121 deleted points in 60 iterations, 49 651 remaining points). (c): Skeleton obtained with our algorithm (1 150 230 deleted points in 61 iterations, 52 542 remaining points). (d): Close-up of (b). (e): Close-up of (c). (f): Another viewpoint of (a). (g): (b) from the same viewpoint as (f). (h): (c) from the same viewpoint as (f). (i): Intersection of (b) and (c) (45 967 points). (j): Difference between (b) and (c) (3 684 points). (k): Difference between (c) and (b) (6 575 points).

  This algorithm works by iterations. Each iteration is composed of two passes (find black points satisfying Ω; delete points not preserved by Rule 2.1). During a pass, points can be considered in parallel.

	Algorithm 2 : Ma95
	1: repeat
	2:
	point,
	if p is a north border point, then s(s(p)) is a black point,
	if p is a east border point, then w(w(p)) is a black point,
	if p is a up border point, then d(d(p)) is a black point.

A black point p is said to satisfy Ω if p satisfies any element in Ω.

Using these definitions, Ma gives the Algorithm 2, denoted by Ma95.

Table 1 :

 1 ]. Six of the objects used for our tests. Comparison between Ma95 and LD09 applied to the 6 objects depicted in Fig.4.

	bull	cobra	knot	letterD	Tz2	vertebra
	Figure 4: Object Black Deleted points	Deleted points	Iterations
		points (first iteration)	(total)
			Ma95 LD09	Ma95	LD09 Ma95 LD09
	bull	424 346 31 344 31 290 399 207 395 099	42	42
	cobra	89 890 18 924 18 922	80 626	79 962	10	11
	knot	231 239 35 572 35 542 212 503 210 972	14	14
	letterD	2 079	1 281	1 281	1 665	1 665	3	3
	Tz2	4 299	1 739	1 739	3 879	3 873	6	7
	vertebra 180 161 23 042 23 034 162 715 161 215	24	25

not mentioned in the original article

Acknowledgments

We are grateful to Professor Gilles BERTRAND (ESIEE, Université Marne-la-vallée, France) for our numerous discussions about P -simple points applied to thinning algorithms, to Romain JACQUINOT (IUT Le Puy-en-Velay, Université d'Auvergne, France) for rendering the images of 4 and 5 and to Susan ARBON for help in preparing this paper.