Member, SAIEE, Member, IEEE Craig S Carlson

Aurélie Deroubaix

Clement Penny

Senior Member, IEEE Michiel Postema
email: michiel.postema@wits.ac.za

On the Attenuation of Ultrasound by Pure Black Tattoo Ink

Keywords: Carbon black, C65 acoustics, high-frequency sonication, diagnostic ultrasound, particle detection, tattoo detection, hydrophobic nanoparticles

Black tattoo ink comprises hydrophobic carbon black nanoparticles. We hypothesized that black tattoo ink demonstrates transient dynamic activity in an ultrasound field. Brightness-mode sonography was performed on cylindrical receptacles of different bore diameters, filled with black tattoo ink, water, saline, or air, using pulsed ultrasound with center frequencies of 13 MHz and 5 MHz.

The scattering from black ink itself lasted less than ten minutes. At 13-MHz sonication, a transient drop in sound speed was observed, as well as a transient lessening of scattering from distal phantom tissue. The linear acoustic attenuation coefficient of pure black ink was measured to be 0.15±0.01 dB cm -1 MHz -1 , equal to whole blood.

Low-intensity ultrasonic tattoo removal would be of interest as an alternative to techniques that damage surrounding tissue.

I. INTRODUCTION

T ATTOOS have been under investigation for their role in society [START_REF] Armstrong | Career-oriented women with tattoos[END_REF][START_REF] French | Are tattoos associated with employment and wage discrimination? Analyzing the relationships between body art and labor market outcomes[END_REF], in physical health [START_REF] Long | Infectious complications of tattoos[END_REF][START_REF] Kazandjieva | Tattoos: dermatological complications[END_REF][START_REF] Kluger | Tattoos, inks, and cancer[END_REF][START_REF] Hutton Carlsen | Patients with tattoo reactions have reduced quality of life and suffer from itch: Dermatology Life Quality Index and Itch Severity Score measurements[END_REF], and even in mental health [START_REF] Grumet | Psychodynamic implications of tattoos[END_REF][START_REF] Carroll | Tattoos and body piercings as indicators of adolescent risk-taking behaviors[END_REF]. Ultrasonic imaging has been used to monitor dermatological tattoo complications [START_REF] Hutton Carlsen | High-frequency ultrasound imaging of tattoo reactions with histopathology as a comparative method: introduction of preoperative ultrasound diagnostics as a guide to therapeutic intervention[END_REF][START_REF] Serup | Diagnostic tools for doctor's evaluation of tattoo complications[END_REF]. In addition to laser ablation [START_REF] Kuperman-Beade | Laser removal of tattoos[END_REF], ultrasound has also been experimentally applied for tattoo removal [START_REF] Hazlewood | Enhanced laser surface ablation with an integrated photoacoustic imaging and high intensity focused ultrasound system[END_REF][START_REF] Serup | High-frequency (20 MHz) high-intensity focused ultrasound: new ablative method for color-independent tattoo removal in 1-3 sessions. An open-label exploratory study[END_REF]. The high-intensity focussed ultrasound used for this purpose ablates the tissue in or near the transducer focus, irrespective of the presence of ink. To date, no studies have investigated the acoustic properties of tattoo ink particles themselves and their response to an incident lowamplitude sound field.

The most common tattoo color is black [START_REF] Eklund | Laser tattoo removal, precautions, and unwanted effects[END_REF][START_REF] Jacobsen | Carbon black nanoparticles and other problematic constituents of black ink and their potential to harm tattooed humans[END_REF]. As the vast majority of tattoo-related medical complaints result from black tattoo ink [START_REF] Jacobsen | Carbon black nanoparticles and other problematic constituents of black ink and their potential to harm tattooed humans[END_REF][START_REF] Høgsberg | High prevalence of minor symptoms in tattoos among a young population tattooed with carbon black and organic pigments[END_REF], this type of ink is the primary focus in tattoo modification and removal. Black tattoo ink comprises carbon black nanoparticles [START_REF] Høgsberg | Tattoo inks in general usage contain nanoparticles[END_REF][START_REF] Humphries | Determination of the thermal and physical properties of black tattoo ink using compound analysis[END_REF]. As carbon black nanoparticles demonstrate transient dynamic activity in an ultrasound field [START_REF] Postema | High-speed footage shows transient ultrasonic nucleation of different hydrophobic particles in suspension[END_REF], we hypothesize that black tattoo ink exhibits similar behavior. The purpose of this study is to investigate transient and steady-state behavior of black tattoo ink under sonication.

Although an early study on the interaction of ultrasound and carbon black was applied to the identification of components for smart battery recycling [START_REF] Postema | Ultrasonic identification technique in recycling of lithium ion batteries[END_REF], our primary long-term purpose with the present study is to deposit acoustic energy into particles suitable for superficial human injection, thereby directly heating the particles and indirectly the surrounding tissue. This might facilitate sonic tattoo removal at low, nondestructive acoustic intensities.

Numerous studies have been dedicated to the experimental determination of the sound-absorbing properties of biological tissue [START_REF] Bamber | Ultrasonic attenuation in fresh human tissues[END_REF][START_REF] Duck | Physical Properties of Tissue: A Comprehensive Reference Book[END_REF][START_REF] Secomski | Estimation of hematocrit by means of attenuation measurement of ultrasonic wave in human blood[END_REF][START_REF] Calor-Filho | Measurement of the ultrasonic attenuation coefficient of human blood plasma during clotting in the frequency range of 8 to 22 MHz[END_REF][START_REF] Patterson | Experimental measurements of ultrasound attenuation in human chest wall and assessment of the mechanical index for lung ultrasound[END_REF], tissue-mimicking phantoms [START_REF] Yoshida | Measurement on ultrasonic attenuation coefficient of tissue mimicking materials[END_REF][START_REF] Farrer | Characterization and evaluation of tissue-mimicking gelatin phantoms for use with MRgFUS[END_REF], salty water [START_REF] Chen | Speed of sound in NaCl, MgCl 2 , Na 2 SO 4 , and MgSO 4 aqueous solutions as a function of concentration, temperature, and pressure[END_REF][START_REF] Kleis | Dependence of speed of sound on salinity and temperature in concentrated NaCl solutions[END_REF], and combinations thereof [START_REF] Franceschini | Ultrasound characterization of red blood cell aggregation with intervening attenuating tissue-mimicking phantoms[END_REF]. Although their structures may appear solid, from a physics point of view, most tissues studied in medical ultrasonography are considered fluids [START_REF] Postema | Fundamentals of Medical Ultrasonics[END_REF].

Sound absorption in fluids can be mainly attributed to viscous and thermal damping. The viscous damping corresponds to the friction associated with the relative motion of the particles. The viscous damping coefficient in fluids is proportional to the squared transmission frequency. Thermal damping is the mechanism whereby a fraction of the energy carried by the propagating wave is converted into heat by thermoelasticity. In most liquids and solids, the thermal damping coefficient can be neglected, but in gases it accounts for roughly a third of the total damping [START_REF] Postema | Fundamentals of Medical Ultrasonics[END_REF]. Consequently, bulk fluid absorbs sound better if there is gas presence. If the gas presence is transient, so must the absorption. Hydrophobic particles in suspension have a gaseous surrounding layer, referred to as a void [START_REF] Attard | Nanobubbles and hydrophobic attraction[END_REF]. This void is compressible. Just like all other compressible entities, hydrophobic particles in suspension can oscillate, move, attract, and repel each other under the influence of sound, owing to so-called Bjerknes forces [START_REF] Leighton | The Acoustic Bubble[END_REF].

Hydrophobic carbon black nanoparticles are only transiently acoustically active [START_REF] Postema | Ultrasound homogenises suspensions of hydrophobic particles[END_REF]. Some of these particles have been observed to lose their surrounding voids whilst oscillating. Once dehydrophobised, they appeared to remain inactive in an ultrasound field [START_REF] Postema | High-speed footage shows transient ultrasonic nucleation of different hydrophobic particles in suspension[END_REF]. Consequently, we speculate, that the state of hydrophobicity must influence the thermal damping of ultrasound propagating through the fluid. The voids, once released, become free gas microbubbles. These must dissolve within milliseconds [START_REF] Postema | Fundamentals of Medical Ultrasonics[END_REF]. The presence of freely oscillating microbubbles must influence the speed of sound in the medium [START_REF] Leighton | The Acoustic Bubble[END_REF].

The ultrasonic transmission frequencies used in [START_REF] Postema | High-speed footage shows transient ultrasonic nucleation of different hydrophobic particles in suspension[END_REF][START_REF] Postema | Ultrasound homogenises suspensions of hydrophobic particles[END_REF] were 45 kHz and 1 MHz. These frequencies were much lower than the resonance frequencies of the particles under sonication. To exploit Bjerknes forces for actual physical manipulation of nanoparticles, one would need to sonicate at a frequency much closer to the resonance frequencies of the particles [START_REF] Postema | Fundamentals of Medical Ultrasonics[END_REF].

The resonance frequency of a hydrophobic particle can be estimated from [START_REF] Kudo | Asymmetric oscillations of endoskeletal antibubbles[END_REF], where the optically observed radius of a particle in suspension, which includes the void, is taken for the outer radius, and the dry particle radius is taken for the inner radius. It is noted that the derivation of the oscillating and translating dynamics of a spherically symmetric hydrophobic particle is identical to that of an antibubble [START_REF] Johansen | Lagrangian formalism for computing oscillations of spherically symmetric encapsulated acoustic antibubbles[END_REF]. It is also noted that the largest particles in a population contribute most to the acoustic response of that population [START_REF] Leighton | The Acoustic Bubble[END_REF]. In a preliminary study, the acoustic conditions for tattoo removal were modeled assuming ink particle sizes greater than 50 µm [START_REF] Teng | Ultrasound: An Alternative Solution to Removing Tattoos[END_REF]. This assumption is, for some inks, a factor of 1000 off, as black ink particles may be as small as 40 nm in diameter [START_REF] Høgsberg | Tattoo inks in general usage contain nanoparticles[END_REF][START_REF] Grant | Tattoo ink nanoparticles in skin tissue and fibroblasts[END_REF]. Using atomic force microscopy, the diameters of black ink particles were measured to have a mode of 0.24 µm [START_REF] Grant | Tattoo ink nanoparticles in skin tissue and fibroblasts[END_REF]. The largest black ink particle had a diameter of 0.97 µm [START_REF] Grant | Tattoo ink nanoparticles in skin tissue and fibroblasts[END_REF].

To determine which ultrasonic frequency to use in our experiments, we needed to measure the size distribution of the black ink particles in solution and to compute the corresponding resonance frequencies.

In this study, ultrasound images from a diagnostic scanner were recorded from black tattoo ink contained in various receptacles, with a focus on the variation of backscattering over time from the ink and from distal scatterers.

II. MATERIALS AND METHODS

Zuper Black pigment dispersion (INTENZE Products, Inc., Rochelle Park, NJ, USA) was used for black ink. Undiluted black ink was measured to have a density of 1313 kg m -3 .

For size distribution estimation, bright-field microscopy images were captured of a 0.01% dilution of Zuper Black using the bright-field component of a ZEISS LSM 780 confocal laser scanning microscope with an alpha Plan-Apochromat 63×/1.40 NA Oil CorrM27 objective lens (Carl Zeiss AG, Oberkochen, Germany) [START_REF] Deroubaix | Monitoring of intracellular localization of Hepatitis B virus P22 protein using Laser Scanning Confocal Microscopy and Airyscan[END_REF].

Figure 1 shows the size distribution histogram and a graph of the particle resonance frequency as a function of its diameter. The mode of the diameters measured was 0.29 µm and the largest diameter was 1.14 µm. Dividing the dry particle mode from [START_REF] Grant | Tattoo ink nanoparticles in skin tissue and fibroblasts[END_REF] by the mode measured from our wet ink particles, and dividing the largest particle diameter from [START_REF] Grant | Tattoo ink nanoparticles in skin tissue and fibroblasts[END_REF] by our largest wet particle diameter yielded 0.24 µm 0.29 µm ≈ 0.97 µm 1.14 µm ≈ 0.8. Thus, the resonance frequencies were computed from [35, eq. 1], approximating the inner-to-outer diameter ratio by 0.8. Our largest particle had a resonance frequency of 15 MHz. All other ink particles had greater resonance frequencies than 15 MHz. To be certain that all particles oscillated in anti-phase with respect to the incident sound field [START_REF] Postema | Fundamentals of Medical Ultrasonics[END_REF], we chose operating frequencies slightly less, at 13 MHz, and substantially less, at 5 MHz.

Our ultrasonic experiments were carried out in a Perspex container of 580×235×65 (mm) 3 internal dimensions, which was filled with degassed water. A line drawing of the experimental setup is shown in Figure 2. The setup had been designed for optically observing microscopic biomaterials under sonication [START_REF] Nathan | Ultrasonic Blood Fractionation[END_REF][START_REF] Smalberger | Ultrasound-Assisted Cell Eradication[END_REF].

Either an HFL38 13-6 MHz linear probe or a C60 5-2 MHz curvilinear probe of a SonoSite R M-Turbo R sonography device (FUJIFILM SonoSite, Inc., Bothell, WA, USA) was clamped in the length direction of the container. The sonography device was operating in either intima-media thickness (IMT) or nerve (Nrv) brightness mode. IMT was the default operating mode for the 13-6 MHz probe; Nrv was the default operating mode for the 5-2 MHz probe. The ultrasound penetration depths of the 13-6 MHz probe and the 5-2 MHz probe were set to 6.0 cm and 6.6 cm, respectively.

The sonography device converted two-way travel times to one-way radial distances assuming c t =1540 m s -1 for the speed of sound in tissue. It compensated for tissue attenuation by amplifying the backscattered signal by 0.3 dB cm -1 MHz -1 by default [START_REF] Duck | Physical Properties of Tissue: A Comprehensive Reference Book[END_REF][START_REF] Haar | Ultrasonic imaging: safety considerations[END_REF]. In both operating modes, the mechanical and thermal indices had fixed values of 0.6 and 0.1, respectively. Automatic image adjustments had been switched off.

Two tissue-mimicking phantom receptacles with empty cylindrical wells were manufactured according to the method in [START_REF] Bude | An easily made, low-cost, tissue-like ultrasound phantom material[END_REF]. A picture of one of the phantom receptacles and its dimensions is shown in Figure 3.

The phantom material was measured to have a density of 1025 kg m -3 , a speed of sound of approximately 1500 m s -1 , and a linear attenuation coefficient of 0.35 dB cm -1 MHz -1 . A phantom receptacle was placed in the container such that one of its sides touched the probe surface.

Other receptacles used in this study were CUPROPHAN R RC55 cellulose capillaries (Membrana GmbH, Wuppertal, Germany) with a 200-µm bore diameter and an 8-µm wall thickness, and RS PRO silicone transparent Silicone Tubing (RS Components (SA), Midrand, South Africa) with a 0.50mm bore diameter.

Whilst the phantom receptacles were at a fixed position in the container, our most modest receptacles were manually held between 0.6 cm and 1.3 cm in front of the 13-6 MHz probe. For these receptacles, the ultrasound penetration depth was adjusted to 1.8 cm.

The phantom receptacle wells were filled with pure (undiluted) ink using a syringe. The silicone tubes were filled with a 25% dilution using a syringe and the capillaries were filled with a 25% dilution using capillary action. These receptacles were used for calibration and illustration purposes. As the ink had been diluted, these experiments were not used for quantification. For control experiments, receptacles filled with degassed Braamfontein tap water, Reitzer's Distilled Water (Reitzer Pharmaceuticals, Kempton Park, South Africa), SABAX Pour Saline 0,9% (Adcock Ingram Critical Care (Pty) Ltd, Midrand, South Africa), phantom tissue, and air were used.

Sonication continued for ten minutes after each filling, during which images were recorded.

The experiments with the phantom receptacles took place over two consecutive days, the experiments with the other receptacles took place on two separate days. A total of 553 brightness-mode still-frames were recorded using the ultrasound scanner internal storage.

Image processing was done using MATLAB R (The Math-Works, Inc., Natick, MA, USA). In all images recorded, the axial backscattering profiles were extracted on an 8-bit gray scale, after which the absolute peak scatter amplitudes, corresponding to the proximal and distal receptacle interfaces, were measured. In selected images, the mean of the axial scattering from the far field, distal to the last interface, was measured.

The linear acoustic attenuation coefficients of the media under investigation were computed, correcting for tissue attenuation compensation of the device [START_REF] Haar | Ultrasonic imaging: safety considerations[END_REF] and taking into account the geometric spreading of a point scatterer and a dual interface system with opposing reflection coefficients [START_REF] Attenborough | A pocket-sized introduction to acoustics[END_REF]:

e 2f c [α n (r 2 -r 1 )-α t (r 2 -r 1 )] = p 1 p 2 r 1 r 2 (1+R n )(1-R n ), (1)
where f c is the center frequency of the ultrasound pulse, p 1 is the proximal peak, p 2 is the distal peak, r 1 is the axial distance to the proximal interface, r 1 is the perceived distance to the proximal interface, r 2 is the axial distance to the distal interface, r 2 is the perceived distance to the distal interface, α n is the acoustic attenuation coefficient of medium n, α t is the average attenuation coefficient in soft tissue [START_REF] Duck | Physical Properties of Tissue: A Comprehensive Reference Book[END_REF], and R n is the pressure reflection coefficient at the proximal interface, given by

R n = ρ n c n -ρ φ c φ ρ n c n + ρ φ c φ , (2)
in which c n is the speed of sound in medium n, c φ is the speed of sound in the phantom material, ρ n is the density of medium n, and ρ φ is the density of the phantom material. The units of the attenuation coefficients computed were converted from [Np m -1 MHz -1 ] to [dB cm -1 MHz -1 ] by multiplication by a factor 2000 log 10 e.

A change in the speed of sound in the well medium must result in a change in the perceived distance to the distal interface. The time-dependent speed of sound of medium n was computed using

c n (t) = r 2 -r 1 r 2 (t) -r 1 c t . (3)
The speed of sound directly measured from (3) was evaluated, knowing that, at a given distance r 1 , for a probe with source function A r 0 , the ratio of scattered amplitudes from the proximal interface

p 1,n+1 (t) p 1,n = Ar0 r1 e 2fc(αtr 1 -α φ r1) |R n+1 (t)| Ar0 r1 e 2fc(αtr 1 -α φ r1) |R n | = R n+1 (t) R n (4)
must equal the ratio of reflection coefficients for different well media, yielding The influence of nucleation on the attenuation coefficient was estimated by substituting the mean gray level distal of the distal interface for p 2 in (1) and multiplying the right-hand side by

p 1,n+1 (t) p 1,n = ρ n+1 c n+1 (t) -ρ φ c φ ρ n c n -ρ φ c φ . (5)
(1 + R n )(1 -R n )
once more, adding an extra transmission interface. Note that r 2 is not changed, as the size of the well has not changed.

To confirm the receptacle parameters, distilled water was used in control experiments in the wells.

III. RESULTS AND DISCUSSION

Figure 4 shows 13-MHz brightness-mode scans of a phantom receptacle well with a 40-mm bore diameter and their respective axial profiles. The bright spots inside the circular areas in frames (a-d) indicate scatterers inside the black ink. The number of scatterers decreased over time, but a few are still visible in frame (d).

The axial backscatter of the ink-filled well shows first peaks at a 1-cm axial distance with 8-bit gray levels rising from 84 (a) to 152 (d). These peaks correspond to the proximal phantom-well interface. The second peaks, at a 5-cm axial distance, correspond to the distal phantom-well interface. These second-peak values rose from 199 to 215 during the 7 01 image sequence. Although not visible with the naked eye, the perceived distance between the peaks is 0.16 mm less between frames (c) and (d), indicating a change in the speed of sound. From (3), it followed that the speed of sound of ink was 1621 m s -1 in (a) and 1627 m s -1 in (d).

The axial backscatter of the water-filled well had a proximal peak gray levels of 67 and a distal level of 244. Substituting the values obtained from (3) into the right-hand side of (4) resulted in a reflection coefficient ratio between ink (d) and water (f) of -2.25. The ratio of proximal peaks in (d) and (e) was 2.27. Thus, compared to the level from ink, this low proximal amplitude of distilled water can be attributed to the difference in reflection coefficients. Although the density of nucleating ink could not be measured directly, it could be computed from (5), using (4) as pressure-ratio input. The density of nucleating ink was computed to be around 1200 kg m -3 in frame (a). Knowing the steady-state density of black ink, this result means that gas comprises 9% of the volume fraction of nucleating ink. This indicates that the cavitation activity is very dynamic.

The device compensation for tissue attenuation created a 16-dB amplification between the two interfaces. Therefore, the scattering from nucleation is actually not just taking place in the distal part of the well cross section, but over the whole cross section. This is supported by the gradient of the gray level as a function of r inside the well. The higher distal peak levels in frames (a-d) and (f) are also explained from the lack of attenuation of both media compared to the tissue attenuation compensation. The ink distal peak was portrayed 20 dB higher, the distilled water peak 32 dB. The reflection coefficient played only a minor role in the distal peak amplitude:

|R n |(1 + R n )(1 -R n ) is +2 dB for ink and -1 dB for distilled water.
Another indicator of cavitation dynamics is the mean gray level distal to the distal interface. In frames (a-d), the mean distal gray level gradually rose from 96 in (a) to 111 in (d). The mean distal gray level of distilled water (f) was 201. Here, the transmission coefficient played a minor role in the scattered amplitude of a phantom speckle:

(1+R n ) 2 (1-R n ) 2 is -2 dB
for ink and +1 dB for distilled water. These are, however, negligible compared to the device amplification. Therefore, both media have an increased distal gray level, depending on their own attenuation coefficient. As the phantom material itself had an attenuation coefficient slightly higher than that used for tissue compensation, the gray level in (e) gradually declined with distance r according to e -2(α φ -αt)fcr , in addition to the geometric decline according to r -1 . Cavitation activity was also reflected by the attenuation coefficient itself. The attenuation coefficient had increased to approximately 0.2 dB cm -1 MHz -1 in frames (a-d). Its steady state-value was 0.15±0.01 dB cm -1 MHz -1 , measured in a subsequent image sequence, 13 31 later (not shown).

The attenuation coefficient of the carbon black pigment dispersion in steady-state, 0.15 dB cm -1 MHz -1 , corresponds to the attenuation coefficient of whole blood [START_REF] Duck | Physical Properties of Tissue: A Comprehensive Reference Book[END_REF] and is just 0.02 dB cm -1 MHz -1 less than the attenuation coefficient of testes [START_REF] Bamber | Ultrasonic attenuation in fresh human tissues[END_REF]. The attenuation coefficient found for distilled water was 0.00±0.01 dB cm -1 MHz -1 , which corresponds to the literature value of 0.002 dB cm -1 MHz -1 [START_REF] Franceschini | Ultrasound characterization of red blood cell aggregation with intervening attenuating tissue-mimicking phantoms[END_REF]. Our attenuation coefficient for saline, 0.02±0.02, corresponds to the literature value 0.01 dB cm -1 MHz -1 [START_REF] Franceschini | Ultrasound characterization of red blood cell aggregation with intervening attenuating tissue-mimicking phantoms[END_REF]. The steady-state speeds of sound were measured to be 1639 m s -1 of ink; of saline 1568 m s -1 , and 1480 m s -1 of distilled water.

Figure 5 shows 5-MHz brightness-mode scans of a phantom receptacle well with a 28-mm bore diameter and their respective axial profiles. Although nucleation activity was visible in the circular areas in frames (a-d), the speed of sound in the ink was not observed to change, nor the attenuation coefficient, which remained steady at 0.15±0.01 dB cm -1 MHz -1 at this frequency. As the sonicating frequency was approximately one third of the resonance frequency, only stable cavitation and dissolution were to be expected in this acoustic regime.

The device amplification between the two interfaces was 6 dB for ink and 7 dB for saline (f). Contrary to the results at 13-MHz sonication, here the geometric and reflection contribu-tions could not be neglected. The total signal amplification was 3 dB for ink and 8 dB for saline. This amplification is clearly visible at distances greater than the distal interface. The axial cross section from the well filled with phantom material shows a steady decline, supporting the slight difference in attenuation with respect to the device compensation.

In the tubes and capillaries, the ink had been diluted to 25% to make flow into the receptacle possible. Scattering from ink particles inside these receptacles was not observed. Therefore, the influence of dilution on the transient nature and the quantity of acoustic scatterers could not be established. Figure 6 shows brightness-mode scans of capillaries with a 0.20-mm bore diameter and their respective axial profiles.

As the wavelength of the 13-MHz ultrasound in water, approximately 0.12 mm, is less than the diameter of the capillary, two capillary walls should be visible if the acoustic impedance difference is sufficiently high. The axial backscattering in the ink-filled capillary had peak 8-bit gray levels of 95 and 114, respectively. The acoustic impedance difference was high enough to make both capillary walls visible. The peak-to-peak distance of 0.28 mm approximated the capillary width.

The backscattering of the water-filled capillary had a peak gray level of 68. Here, no separate walls were visible. This cannot be attributed to the capillary being outside the elevation plane, as the 0.22-mm outer capillary diameter is substantially less than the transducer elevation. The contribution to the acoustic response can be fully attributed to the cellulose material, as the medium inside the capillary was the same as outside. The backscattering of the air-filled capillary had one peak level of 233. Here, separate walls were not visible either. The long axial scattering zone of 0.99 mm (gray level threshold of 20) is explained from the linear oscillating dynamics of the air trapped in the capillary, which responded to the incident sound field. The resonance frequency of the air-filled capillary was less than 50 kHz, too far from the incident sound field frequency to cause any other dynamic effect [START_REF] Postema | Fundamentals of Medical Ultrasonics[END_REF].

These results show that there was a clear acoustic impedance difference between water and black ink. Thus, the black ink acted as a reflector, although it was in 25% dilution. This outcome limits absolute quantification from distal scatterers, as the transmitted ultrasound pulse may have changed when passing through an inked region.

IV. CONCLUSIONS

In this study, brightness-mode sonography was performed on ink-filled receptacles, using pulsed ultrasound with center frequencies of 13 MHz and 5 MHz.

The attenuation coefficient of ink was measured to be 0.15±0.01 dB cm -1 MHz -1 , of saline 0.02±0.02 dB cm -1 MHz -1 , and of distilled water 0.00±0.01 dB cm -1 MHz -1 . The speed of sound of tattoo ink in steady-state was measured to be 1639 m s -1 , of saline 1568 m s -1 , and of distilled water 1480 m s -1 .

Transient scattering from the ink was observed. Backscattering from distal phantom materials was amplified by the presence of carbon black.

The speed of sound in ink was observed to drop to transiently to 1621 m s -1 for less than ten minutes during 13-MHz sonication, but not during 5-MHz sonication. The drop in speed at 13-MHz sonication may be attributed to strong, yet transient, cavitation activity, as the resonance frequency of the largest hydrophobic carbon black nanoparticles is 15 MHz. This finding is useful for the potential deposition of acoustic energy into tattoos with the purpose of modifying them.

Fig. 1 .

 1 Fig. 1. Size distribution of Zuper Black pigment dispersion (histogram) and particle resonance frequency as a function of the diameter (curve), with an inlay of a bright-field microscopy image of a 0.01% dilution of Zuper Black at 63× magnification.

Fig. 2 .

 2 Fig. 2. Line drawing of the experimental setup, consisting of a burette clamp and stand (a), water, whose level is indicated by a blue dashed line (b), a £1 coin for scale (c), a tissue-mimicking phantom receptacle (d), an ultrasound probe (e), and a Perspex container (f).

Fig. 3 .

 3 Fig. 3. Top view of the tissue-mimicking phantom receptacle with two cylindrical wells. Dimensions are in mm.

Fig. 4 .

 4 Fig. 4. Brightness-mode scans at a 13-MHz ultrasound frequency of a phantom receptacle well filled with black ink (a-d), phantom material (e), and distilled water (f); and corresponding axial backscattering profiles [8-bit gray scale] as a function of perceived distance [cm]. Time stamps are relative to (a). The green dot corresponds to the right-hand side of the probe.

Fig. 5 .

 5 Fig. 5. Brightness-mode scans at a 5-MHz ultrasound frequency of a phantom receptacle well filled with black ink (a-d), phantom material (e), and saline (f); and corresponding axial backscattering profiles [8-bit gray scale] as a function of perceived distance [cm]. Time stamps are relative to (a). The green dot corresponds to the right-hand side of the probe.

Fig. 6 .

 6 Fig. 6. Brightness-mode scans of capillaries filled with black ink (a), degassed water (b), and air (c); and their respective axial backscattering profiles on an 8-bit gray scale. The green dot corresponds to the right-hand side of the probe.

ACKNOWLEDGMENTS

The sonography equipment was kindly supplied by High Tech Medical, Randburg, South Africa. Laser scanning confocal microscopy was performed at the Life Sciences Imaging Facility of the University of the Witwatersrand, Johannesburg.

x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The Big Lebowski x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The Big Lebowski x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The Big Lebowski x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The Big Lebowski x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The Big Lebowski x x x x x x x x x x x x x x x x x x x x x x x x x x x x


Ashley D Gritzman
email: a.gritzman@eie.wits.ac.za

Michiel Postema
email: michiel.postema@wits.ac.za

David Milton Rubin
email: david.rubin@wits.ac.za

Vered Aharonson
email: vered.aharonson@wits.ac.za

Threshold-based outer lip segmentation using support vector regression

Keywords: Lip reading, support vector regression (SVR), histogram threshold, shape-based adaptive thresholding (SAT)

HAL is

Introduction

The shape and movement of human lips convey valuable visual information for automatic lip reading, emotion recognition, biometric speaker identification, and virtual face animation. Extraction of accurate visual information from the lips typically involves three stages: face detection; location of the region of interest; and lip segmentation.

Recent lip segmentation techniques employed machine learning and deep learning, demonstrating segmentation accuracies around 98% [START_REF] Zhang | Spatiotemporal fusion based convolutional sequence learning for lip reading[END_REF][START_REF] Guan | Lip image segmentation in mobile devices based on alternative knowledge distillation[END_REF][START_REF] Guan | Lip image segmentation based on a fuzzy convolutional neural network[END_REF][START_REF] Nascimento | One shot segmentation: unifying rigid detection and non-rigid segmentation using elastic regularization[END_REF]. Deep learning methods are inherently computationally intensive, compared to colour-based segmentation. The low complexity of colour-based segmentation has resulted in a renewed interest [START_REF] Spyridonos | Multi-threshold lip contour detection[END_REF].

Colour-based segmentation techniques alone are prone to false contour detection, due to low chromatic and luminance contrast between lips and skin [START_REF] Cheung | A cooperative learning-based clustering approach to lip segmentation without knowing segment number[END_REF].

Model-based segmentation techniques use previous knowledge of lip shape to construct a lip model by iteratively matching to an image and minimising a cost function. While usually invariant to translation, rotation, scale, and illumination, these techniques remain susceptible to variations in speaker appearance [START_REF] Zheng | Facial feature localization based on an improved active shape model[END_REF][START_REF] Wang | An automatic lipreading system for spoken digits with limited training data[END_REF]. Optimisation is also computationally expensive and it is affected by real-time performance [START_REF] Saeed | Combining edge detection and region segmentation for lip contour extraction[END_REF].

Hybrid segmentation techniques combine elements from colour-and model-based categories [START_REF] Saeed | Combining edge detection and region segmentation for lip contour extraction[END_REF]. They attempt to reduce the computational burden of modelbased techniques by first obtaining a rough estimate using colour-based techniques, and then fitting a lip shape model (LSM) [START_REF] Gritzman | Automatic computation of histogram threshold for lip segmentation using feedback of shape information[END_REF].

This study proposes a a hybrid algorithm, referred to as shape-based adaptive thresholding (SAT). SAT acts as an extension to colour-based lip segmentation. The new algorithm constructs a model for the segmentation errors, rather than for the lip contours, and employs support vector regression (SVR) that uses this model to guide threshold selection.

Methods

The algorithm consists of two stages, both of which were implemented using MATLAB R (The MathWorks, Inc., Natick, MA, USA). The first stage is a one-time pre-training, displayed in Figure 1. The training is performed on a set of segmented-lips image pairs. One image in the pair contains the lips contours estimated by a colour-based lip-segmentation algorithm. The second image contains the ground-truth lips contours, which is usually a manually-marked outline. All images are binary, where the mouth region is white. The training produces a mapping of the image-pairs unto a segmentation errors graph. The graph includes a userselected boundary line that separates the successfulsegmentations region from the unsuccessful one. The second stage is an optimisation process, shown in Figure 2. Its inputs are the segmentation errors graph that was trained at stage 1 and a binary image after colour-based lip-segmentation. The algorithm infers the segmentation error of the input image using the segmentation-errors graph. If the segmentation error resides in the successful-segmentations region, the lips-contour estimation is accepted. If the segmentation error resides in the successful-segmentations region, the algorithm searches for a new threshold. The optimisation process iteratively employs the new threshold in the colour-based segmentation, infers the segmentation error, and searches for a minimum error.

Training of the segmentation error model

During stage 1, augmentation was employed by performing the threshold-based segmentation four times for each image in the training set. The four runs used four different thresholds and thus provided a larger training set and a wider range of performance. Each image was paired with a ground truth image for the lips contour. All images were coded into binary images containing the lip region in white and the skin region in black. A segmentation error was calculated for each input pair, between the threshold-estimated image and its ground truth image. The segmentation error values for the training set pairs were divided into three classes of perfect, good and bad segmentation regions. The threshold value between these regions could be arbitrarily set. The abels attached to the thresholdestimated images were "perfect", "good" and "bad".

Fourteen geometric features are extracted from the threshold-estimated images. Feature normalisation was performed to account for size and distance attribute which may be dependant on the physical characteristics of the subject, the proximity to the camera, and the zoom of the camera. These attributes were normalised using reference quantities. The features and their normalisation references are listed in Table 1. All features were centred and scaled by calculating their z-score. Linear discriminant analysis was used to reduce the fea- ture set from the three classes into two eigenvectors. An -SVR model was trained on the datasets of 2-dimensional eigenvectors to estimate the segmentation error [START_REF] Smola | A tutorial on support vector regression[END_REF]. A radial basis function kernel was used, as well as the LIBSVM library [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF]. To prevent overfitting of the model to the training data, a 10-fold cross-validation was performed, using the mean square error measure. The model parameters C and γ were optimised using a grid search approach with crossvalidation [START_REF] Hsu | A practical guide to support vector classification[END_REF].

Adaptive thresholding

The second stage was performed to optimise the segmentation thresholds. The input photos were subjected to colour-based thresholding. Feature extraction and reduction was performed on each image, after which An optimisation objective function was defined by the thresholding and all subsequent image-processing steps performed during this stage. The objective function was minimised using Direct Search. A set of points was polled around a current threshold [START_REF] Lewis | Direct search methods: then and now[END_REF]. If and only if the poll was successful, i.e., the objective function had a new value less than the previous step, the current threshold would replace the previous.

Evaluation

We used automatic thresholding for the colour-based segmentation [START_REF] Gritzman | Automatic computation of histogram threshold for lip segmentation using feedback of shape information[END_REF], which employed Otsu's discriminant, a nonparametric and unsupervised maximisation of the separability of the lip-pixels and non-lip pixels [START_REF] Otsu | A threshold selection method from graylevel histograms[END_REF]. The dataset to train and test our algorithm included 895 images of 112 different subjects, from the AR Face Database [START_REF] Martinez | The AR face database[END_REF] and their corresponding groundtruth images [START_REF] Ding | Features versus context: an approach for precise and detailed detection and delineation of faces and facial features[END_REF]. The ground truth had been obtained from manual markings of the lip contours by three independent human judges [START_REF] Ding | Features versus context: an approach for precise and detailed detection and delineation of faces and facial features[END_REF]. The markings of the outer lip contours included 20 points, while the markings of the inner lip contours included only 8. In this study, we concentrated on the outer lip markings. The markings of the outer lips were interpolated and coded into a binary image similar to the outputs of the thresholding algorithm.

The 112 database subjects were randomly divided into two groups: 60% in the training group, and 40% in the test group. The training dataset included 544 images and the test dataset included 351 images, from the subjects in the training group and test group, respectively.

The performance of the algorithm was evaluated using two analyses: SE interference performance and threshold optimisation performance. SE inference performance examined the reliability of the SE model, the output of stage 1. The accuracy of identifying poor segmentations for different criteria was quantified using receiver operating characteristic (ROC) curves. The ROC curves depicted the true positive (correctly accepted) segmentations rate vs. the false positive (incorrectly accepted) rate of the images in the test set. The true positive rate is defined as TP/(TP+FN), the false positive rate by FP/(TN+FP), in which FN is the number of lip pixels classified as skin pixels, FP is the number of skin pixels classified as lip pixels, TN is the number of skin pixels classified as skin pixels, TP is the number of lip pixels classified as lip pixels. Precision and recall were computed for each criterion.

Threshold optimisation performance examined the accuracy of the adaptive threshold. The criterion that produced the best trade-off between precision and recall was selected and employed. The algorithm performance was quantified for the 351 test images using two metrics: the segmentation error

SE = FP + FN 2 × (TP + FN) × 100% (1)
and the overlap OL = 2 × TP TP + TN + FP + FN × 100%.

(2) SE yields the difference, in number of pixels, between the actual and ground-truth images, relative to the number of lip pixels in the ground-truth area [START_REF] Martinez | The AR face database[END_REF]. OL is the percentage overlap between the segmented lip region and ground-truth lip contour. Perfect lip segmentation thus returns OL = 100% and SE = 0%.

Results and Discussion

Figure 3 illustrates the optimisation process. This ex-Fig. 3 An example of SE inferred and corresponding thresholds used, for 17 consecutive polls. Two successful polls are highlighted by a green •. The contours computed after segmentation of polls 1-10 are represented by green lines, superimposed on the original lip photo.

ample was chosen since the image is a challenging one, with facial hair, low contrast between lips and skin, and low illumination. The initial threshold segmentation at poll 1 had an SE of 44.8% and an inferred SE of 26.1%, qualifying it for optimisation according to the segmentation integrity criterion. At poll 2, the threshold was increased from 0.31 to 0.56, which resulted in the exclusion of part of the mouth after segmentation. This stringent threshold resulted in a high number of false negative lip pixels. The inferred SE improved decreased from 26.1% at poll 1 to 19.8%, corresponding to a successful poll. At poll 3, the threshold decreases back to 0.31, the inferred SE increased from 19.8% to 26.1%, indicating an unsuccessful poll. At poll 4, the threshold was set at 0.435, and the inferred SE dropped to 3.49%, corresponding to a successful poll. The segmentation image of poll ( 4) closely follows the lower lip contour and has minor deviations from the upper lip contour. From poll 5 on, the inferred SE of 3.49% from poll 4 did not decrease; thus the threshold of 0.435 was selected as final threshold value. The actual SE at poll ( 4) is 8.5%, which indicates a decrease of 81% compared to the initial SE of 44.8%

Figure 4 shows four typical examples of photos that were selected for optimisation and decreased their SE after the optimised threshold selection. The optimised threshold visibly shows better matches of the outer lip contours than colour-based segmentation alone. Figure 5 presents the ROC of the performance of all test images in stage 1 and three subsets thereof. The area under curve of 0.86 of all data demonstrates good performance. True positive rates of 0.7 and less were correlated to low false positive rates of 0.2 and less. The subsets depict higher true positive rates correlating to these low positive rates. A tradeoff integrity Fig. 5 ROC curves of all test images in stage 1 (a) and of three subsets of test images (b). The blue line represents all test images (AOC=0.86), the red line represents test images with SE between 10% and 15% (AOC=0.83), the yellow line represents test images with SE between 15% and 20% (AOC=0.87), and the purple line represents test images with SE greater than 20% (AOC=1.00). criterion of 10% resulted in the performance depicted in the confusion matrix of Table 2. The matrix reveals that the SE inference failed to accept 28.4% of the images and accepted only 2.35% of the images that needed to be optimised. These properties are reflected in the performance metrics for this matrix, of 88.3% recall and 37.9% precision. The performance of the algorithm compared to colour-based thresholding alone is presented in Table 3. The table shows that without exception, the algorithm decreased SE and increased OL compared to colourbased segmentation alone. Especially the regimes of SE<5% and OL>95% demonstrate a drastic increase of the number images after running the algorithm.

The average SE of the baseline algorithm was reduced by 15.1% for the entire test set, and by 23.1% for the subset of images that were selected for optimisation by the segmentation integrity criterion. The difference stems from the fact that the full test set contains images that need no optimisation and their SE therefore did not change. A trade-off is involved in selecting the segmentation integrity criteria. The 10% criterion used in this study provided a recall of 88.3%, indicating a miss rate of 11.7%. This resulted in poor segmentations that did not continue to the optimisation stage, and hence did not improve by the optimisation. This miss-detection impacted the average accuracy of our algorithm. The partial ROC curves imply that the very poor segmentations, SE of 20% or more reidentified better than the moderately-poor segmentations of 15% and less. The precision of the acceptance criteria yielded that 37.9% of the images selected for optimisation actually need optimisation. This low precision does not necessarily reduce the accuracy of the algorithm, since unnecessary optimisations may even improve segmentation accuracy. The low precision does, however, incur a computational cost due to good segmentations undergoing unnecessary optimisation. Our examples hint that our algorithm may be particularly efficient for images that present challenging conditions: facial hair, low contrast between lips and skin, and inconsistent illumination.

The proposed algorithm can be grouped under the hybrid colour-based and shape-based segmentation algorithms. The segmentation error model and the inferred segmentation error computation essentially use shape features. Comparison to previous hybrid segmentation and to machine learning lip segmentation algorithms is challenging. Different algorithms were employed on different image datasets, used different preprocessing and in some cases used different performance metrics. The average SE and OL of our algorithm for the subset of images selected for optimisation were 6.50% and 93.5%, respectively. These values are higher than the results of the hybrid approach published in [START_REF] Saeed | Combining edge detection and region segmentation for lip contour extraction[END_REF] of 14.0% and 87.2%, respectively, and the results published in [START_REF] Cheung | A cooperative learning-based clustering approach to lip segmentation without knowing segment number[END_REF] of 8.40% and 90.80%, respectively.

The algorithm proposed in this study selected a new threshold for a colour-based discrimination of the lips from the skin area through minimisation of segmentation error. It trained a segmentation error model from a training set of labelled images and provides an inferred segmentation error for unlabelled images. A segmentation integrity criterion was imposed on the inferred SE and either accepted the colour-based segmentation or proceeded to new threshold selection. The current study evaluated the algorithm's performance in comparison to colour-based segmentation alone. Our algorithm might thus serve as an extension to any colour-based segmentation method.

Conclusions

An algorithm was designed to improve the segmentation accuracy of colour-based lip segmentation. The results portrayed a significant improvement in both segmentation error and overlap. It has been proven effective in challenging mouth image conditions including facial hair obscuring the lips, and low contrast between the lips and skin. The simplicity of the algorithm might enable fast computing for real-time applications.

Fig. 1

 1 Fig. 1 Algorithm stage 1: Training of the segmentation error model.

Fig. 2

 2 Fig. 2 Algorithm stage 2: Adaptive thresholding.

Fig. 4

 4 Fig. 4 Four typical examples of color-based segmentation (a) and optimised segmentation using the segmentation error model (b). The contours computed after segmentation are represented by green lines, superimposed on the original lip photos.

Table 1

 1 Features extracted from each IMAGE and their corresponding normalisation references.

	Mouth shape feature	Reference
	Area	IMAGE area
	Perimeter	IMAGE perimeter
	Centroid horizontal axis	IMAGE width
	Centroid vertical axis	IMAGE height
	Major axis length	IMAGE diagonal
	Minor axis length	IMAGE diagonal
	Bounding box horizontal axis IMAGE width
	Bounding box vertical axis	IMAGE height
	Width	IMAGE width
	Height	IMAGE height
	Distance transform mean	IMAGE diagonal
	Distance transform STD	IMAGE diagonal
	Eccentricity	centre of IMAGE
	Orientation	horizontal line

Table 2

 2 SE inference confusion matrix of an SE decision boundary of 10%.

		Inferred pass Inferred fail
	Actual pass 51.9%	28.4%
	Actual fail	2.3%	17.4%

Table 3

 3 Cumulative frequency table containing SE cumulative distribution values and OL cumulative distribution values.

	SE range Thresholded (%) Optimised (%)
	< 5%	11.3	27.4
	< 10%	61.0	73.8
	< 15%	86.3	90.5
	< 20%	92.9	96.4
	OL range Thresholded (%) Optimised (%)
	> 95%	8.9	24.4
	> 90%	56.0	75.0
	> 85%	82.7	90.5
	> 80%	91.1	95.8

Acknowledgements

This study has been supported by the National Research Foundation of South Africa Grant Numbers 97742 and 127102. It has been based on a Doctoral project [18].


Motasem Alrahabi
email: almoatasem.alrahabi@psuad.ac.ae

Opinion Mining from Arabic Quotations

Keywords: H.2.8 [Database Management]: Database Applications: Data mining, H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing: Linguistic processing, H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval: Information filtering, I.2.7 [Artificial Intelligence]: Natural Language Processing: Text analysis Algorithms, Experimentation, Languages Direct reported speech, opinion mining and sentiment analysis, Arabic language, semantic categorization, rule-based system

We present a contribution to the Arabic Opinion Mining area with the development of a new system for quotations detection and categorization. Our approach differs from the existing work by proposing an operational tool that enables search for keywords in the categorized quotations. The categorization is performed with a rule-based system and is based on the reporting markers' meaning. The system end-user interface enables two query types within the categorized quotations: searching for keywords in the part containing eventually the quotation source (reporting clause) or in the part concerning the topic (reported clause). Our system was applied to process a corpus of Arabic newspaper articles. Both evaluations were carried out with the following results: 88 of recall and 93 of precision for the identification task; 85 or recall and a 93 of precision for the categorization task. The system is publicly accessible on the web site (http://e-quotes.net).

INTRODUCTION

The Reported Speech (RS) is an important linguistic phenomenon which is characterized by its syntactic structure: a matrix clause, containing usually a reporting marker, and a subordinate clause that embeds the conveyed information [START_REF] Bergler | Semantic Dimensions in the Field of Reporting Verbs[END_REF]. Among the various forms of RS (direct speech, indirect paraphrases, direct speech introduced by "that"…), we are particularly interested in the direct RS or quotations. Many text mining applications use quotations to analyze, organize and summarize information because they are a major vehicle of communication in the news genre. We believe that a system that automatically identifies and categorizes quotations would enable readers, journalists and researchers to place news in the context of all comments made on a given topic, and especially to know how these comments were interpreted and reported in the media.

Our work is a contribution in this direction since we aim to automatically detect and categorize Arabic quotations according to semantic and enunciative criteria. For this purpose, we rely on the reporting markers that specifically denote a verbal communication (reporting verbs and their derived gerunds or nouns…). These markers are usually used by the enunciator in order to report the quotation, to exhibit the speaker's attitude and eventually to indicate his own position towards the reported content. Let us consider this sentence:

أوباما اعترف الحظ ولحسن " العالميين السالم و األمن ضمان على لوحدها أميركا ة قدر بعدم ."

Fortunately, Obama acknowledged "the inability of the United States to ensure international peace and security alone."

the different elements are analysed as follows:

Element Label أوباما Obama Source (speaker)

اعترف Admit Reporting marker + Speaker modality marker الحظ ولحسن Fortunately

Enunciator modality marker Our primary contributions making our current research significant are: i) Developing linguistic resources (markers and rules) to identify and categorize quotations from texts in Arabic; ii) creating a simple and operational working implementation which allows the user to directly query the annotated corpus by both classical and semantic criteria.

The remainder of this paper is organized as follows: we first show how difficult Opinion analysis from quotations can be ( §2). We then describe our proposed method ( §3) and give an overview of the system ( §4). In ( §5), we present evaluation results and discuss them. We present in ( §6) the related work and finally, in ( §7) we draw our conclusions and future work.

OPINION MINING CHALENGES FROM DIRECT REPORTED SPEECH

The RS is a standardized way to relate opinion, sentiment or attitude expression of a certain Source regarding a certain Target.

Inspired by Banfield, Uspensky and Quirk, [START_REF] Wiebe | Tracking point of view in narrative[END_REF] considers that Subjectivity refers to aspects of language used to express opinions, feelings, evaluations, and speculations, including sentiments. Therefore, from a computational point of view, current researches distinguishe between subjectivity and objectivity in opinions along with determining these elements: Opinion polarities which tell us whether the opinion's orientation or valence is positive, neutral, negative or, sometimes, mixed; the opinion strength (attitude's degree, i.e., low, medium, high); opinion holder (the people who express opinion), and opinion target (the object of this opinion).

Nevertheless, characterizing the opinions and sentiments analysis from quotations remains challenging for at least these three reasons: the target, the source and the expressed opinion:

 Target: in Opinion Mining (OM) over movie, product or book reviews, the target or topic is clearly identified. On the contrary, the target in news articles is not a concrete object [START_REF] Pang | Opinion mining and sentiment analysis[END_REF] because when a text is argumentative and when it opposes different points of view on a topic, journalists may span larger subject domains, more complex event descriptions and a whole range of targets [START_REF] Balahur | Sentiment analysis in the news[END_REF]. Thus, identifying a concrete target that can be resolved back to named entities does not work for quotations [START_REF] O'keefe | An Annotated Corpus of Quoted Opinions in News Articles[END_REF], because quotes may not necessarily mention the debate topic (implicit targets), and there may be many relevant targets for a single topic (mixed speeches, selective and partial targets).  Source: the opinion source (holder) identification aims to extract entities that express opinions in texts [START_REF] Lun-Wei | Identification of Opinion Holders[END_REF]. There are many major challenges in the task of automatically attributing each quote to its correct speaker [START_REF] Pareti | The independent encoding of Attribution Relations[END_REF]. Sometimes, the source may not be located near the quotation, so syntactic parsing named entity recognition may be necessary. The use of pronouns is also common, such that anaphora and coreference resolution are needed to determine the name of the source. In the case of quotations, a source can be a title or role (Prime Minister); personal name (Vladimir Poutine); pronominal reference (she said…); anonymous (a passenger, a witness…), etc.. The source of quotation is not always explicitly mentioned, as in the following cases in Arabic: For Arabic language, several challenges complicate the opinion source identification [START_REF] Elarnaoty | A Machine Learning Approach For Opinion Holder Extraction Arabic Language[END_REF]: the lack of resources, the high inflectual nature of Arabic language, the variant sources of ambiguity, the rich metaphoric script usage and the absence of robust Arabic parser that understand the sentence structure [START_REF] Habash | Introduction to Arabic Natural Language Processing, Synthesis Lectures on Human Language Technologies[END_REF].

اآلتي
 Expressed opinion: most work on OM has been carried out on subjective text types such as blogs and product or movie reviews where individuals express their opinions quite freely. On the contrary, the position of the journalist in relation to what s/he reports in newspaper articles is often more subtle [START_REF] Balahur | Opinion mining on newspaper quotations[END_REF], because the authors of newspaper articles try to make their articles to look objective concerning the topics they are covering. In these cases opinion or sentiment is most of the time not expressed explicitly in the text. This issue makes it often hard to directly identify sentiment in the news. However, journalists continue to keep a large flexibility to exhibit their attitude in relation to what they are reporting: it goes for instance by highlighting some facts while omitting others, but especially by the choice of words to introduce the RS, to show his own point of view and to describe the position of the different actors of the original utterance situation.

For all these reasons, OM from quotations may not guarantee perfect results. Our current aim in this study is not trying to tackle all of these complex issues, but to focus our efforts on the last point (expressed opinion) for Arabic language, i.e. how a quotation is reported and interpreted by the enunciator?

THE PROPOSED APPROACH

We describe here the different aspects of our approach for quotations identification and categorization.

First, we distinguish between the opinions expressed within the reported content (inside quote, the speaker's opinion) and those attributed directly to the enunciator. For this purpose, we refer in our analysis to the observable reporting markers (which are lexically expressed) in order to categorize quotations and distinguish between the speaker opinion and the enunciator opinion. In the enunciative approach [START_REF] Johansson | Enonciation: French pragmatic approach(es)[END_REF], [START_REF] Desclés | Enonciateur, locuteur, médiateur[END_REF], the enunciator (utterer) is the entity that reports the whole speech (generally the author), whereas the speaker (or locutor) is the last source or holder of the speech. For instance, when enunciator uses the verb to claim, he reports the purpose of the speaker, in addition, he shows his own position by doubting the speaker's credibility.

Semantic categorization

Moreover, our added value is that the analysis covers a larger scale of phenomena which are not easily classifiable when using only the categories of positive and negative.

The enunciator can use the mechanism of RS not only to reproduce the original utterance, but also to interpret it and to give other information using at least three types of markers:

 Reporting markers such as according to, to confirm, declaration, etc.  Modality markers (modalizers) that indicate: o the position of the enunciator towards the speech act (unfortunately she admitted..) or towards its specifications (by adding this short / unacceptable comment… ); o the intersubjective relation: X criticizes Y, X encourages Y, X informs Y, etc. o the attitude of the speaker: He said, fawning / with skepticism… / He cries… / She whispers…  circumstantial information that clarify the original utterance speech act: spatio-temporal and audience settings [START_REF] Bergler | Semantic Dimensions in the Field of Reporting Verbs[END_REF], theme or topic (concerning /about…), communication medium (He said in a letter…). The corpus examination1 allowed us to identify more than 150 reporting markers [START_REF] Alrahabi | Direct Reported Speech in multilingual texts: Automatic annotation and semantic categorization[END_REF], which have been manually listed and stored with their derived forms. We organized these markers in several dozens of categories and sub-categories into a semantic map (linguistic ontology) where we have taken into consideration intersubjective, semantic and discursive parameters:  the axis "Good -Bad": criticize, encourage, threat…  the axis "True -False": confirm, deny, believe…  the axis "Information": declare, explain, diffuse…  the axis "Will": order, decide, solicit…  the axis "Speech organization": add, answer, summarize..  … For our current experiment, we only covered from this semantic map the "Good -Bad" axis. This part contains two categories and it is organized as follows:

Markers and structures of Direct RS

Direct RS can be expressed in various ways. We consider, on the formal level, that a quotation is any kind of speech delimited by meta-characters (the typographical signs of quotation) and introduced by, at least, one reporting marker referring to an act of communication, whether the speaker is explicitly defined or not. By convention, we consider the quotation span as a verbatim transcription of the source utterance, despite the existence of rare cases where the quoted words are not certainly attributed to the speaker, as in: Has he really said "…" ? / He did not say "…" / He probably said "…", or in the following case: The position of each element within a text can vary and, except the quoted words, all other parameters are optional.

SYSTEM OVERVIEW

In this section, we describe the system pipeline configuration and how it is deployed in practice. For processing resources, we use EXCOM-2 [START_REF] Alrahabi | EXCOM : Plate-forme d'annotation sémantique de textes multilingues[END_REF], a rule-based system that performs annotations by using surface markers and heuristic rules. Annotated texts are then indexed for rapid retrieval at query time with Solr search engine platform.

Corpus preparation

Technically, to annotate a corpus, EXCOM-2 needs one pretreatment phase of segmentation (splitting). It helps in determining the search fields for linguistic markers, and the textual snippets which are to be annotated. This consists in defining by heuristic rules the boundaries of sections, titles, paragraphs and sentences. For this, all corpus documents have to be normalized and converted to raw texts files in UTF-8 encoding002E

Annotation: Quotations recognition and categorization

EXCOM-2 algorithm is based on the Contextual Exploration (CE) method [START_REF] Desclés | Contextual Exploration Processing for Discourse Automatic Annotations of Texts[END_REF]; the tool does not deal with any preliminary morphosyntactic analysis or named entities recognition. The starting point of the system is the corpus preparation and its core is the semantic annotation task. In our perspective, we consider two types of surface markers: indicators and clues. The presence of a potential marker [START_REF] Wiebe | Learning subjective language[END_REF] in the search space triggers the associated CE rules, and then, additional markers (clues) are searched in a specified context. If all the rule conditions are satisfied, the segment specified by the rule is annotated. For our processing, we consider quotations marks as indicators and reporting markers as clues.

Different types of rules can be implemented in EXCOM-2, depending on the research space or the type of markers (linguistic units, regular expressions, text structure tags…). The tool enables to use the already annotated segments, to use the text structure (titles, paragraphs…), to sort the rules according to their importance and to use negative clues that cancel certain rules.

For our task, the annotation of each semantic category requires the creation of three rules on average. A basic version of EXCOM-2 is available online at this address: http://www.excom.fr/.

Indexing and Web Interface

For the information retrieval module, we use a typical Vector Space Model based system (Apache Solr) and we store all annotated XML documents in an inverted index that enables flexible search for keywords in all quotations of the corpus.

E-Quotes end-user web interface supports search in many different ways:

 Search for keywords in all identified quotations;  Search for keywords in specific identified and categorized quotations. For example, search for a word in a negative quotation and more especially in a negative quotation that has the value « accusation »;  Search for keywords in the reporting clause or in the reported clause of a specific category of quotations. Since we do not proceed to the recognition of speakers or targets, the last feature allows user to find answers to such a question:

What is the <opinion> of a <speaker> about a <subject>?

where the parameters <speaker> and <subject> are specified by users as combination of keywords or entities. The list of <opinion> categories is extracted from the semantic map. The system supports also boolean combinations of multiple fields, i.e. AND, OR, NOT.

EVALUATION

We conducted two evaluations by computing traditional measures in order to test the capacity of our system to identify and to categorize quotations. We also performed a detailed analysis of error cases introduced by our system and their root causes.

Quotations Recognition Evaluation

We randomly selected out 21 new documents from online newspaper articles which include more than 1000 sentences and 25000 words. Topics covered in these articles are mostly political, economic, social news and events. We then annotated these texts with EXCOM-2 that identified exactly 271 quotations. In parallel, we asked an expert (journalist) to read the selected articles and to highlight manually only the snippets she judges as quotations.

After the comparison, we obtained the following results: 88 for Recall and 93 for Precision.

Identification task results analysis

We conducted a manual inspection over all evaluation documents to identify detection errors. Here are the Recall result analysis:

-The value of silence is due to the fact that some markers are not yet covered by our resource base:

 Nominal markers and gerunds derived from reporting verbs: declaration, by saying…).  Passive construction markers like: ي سم قيل, / It was said …  Self-quotation markers: مسامعنا الى /...انتهى We have heard… -The quotation is introduced by some markers indicating the speaker's attitude but that are not reporting markers:

أكتافهم فيهزون المعنيون أما مسالمين أشخاص سوى هنا ليس "أنظروا مبالين: غير المجتمع مصلحة أجل من ينشطون " . Concerned people shake their shoulders, without caring: "look, there is no one but peaceful persons who work for the sake of their society".

Concerning the Precision rate, we can mention the cases of misguiding quotation marks and the polysomic reporting markers.

-A large number of noise is usually caused by the presence of misguiding quotation marks (quotation marks that do not surround quotes). Example:

االسرائيلية المنظمة لكن رواية د يؤك ا تقريرا نشرت "بيتسالم" االنسان لحقوق الفلسطينيين العيان شهود .

But the Israeli human rights organization "B'Tselem" published a report confirming the Palestinian eyewitnesses'

version. -In Arabic, the surface forms are generally polysemics [START_REF] Dichy | Morphosyntactic Specifiers to be associated to arabic lexical entries-Methodological and theorical aspects[END_REF],

especially the forms that have a three-letter root ( علق, بين, عبر, .)...شرح This difficulty is due to the morphological ambiguity in Arabic, caused, above all, by the absence of vocalization, the agglutination and the relatively free word order in a sentence.

Here is an example for wrongly assigned quotation, caused by the presence of a polysemic reporting marker )نقلت( in the context of misguiding quotation marks:

ونقلت سيارات وطبية إغاثية "مواد للمنظمة التابعة االغاثة إلى " المدينة داخل .
The cars of the Relief Organization have transported « relief and medical materials » to the center of the city.

We also mention the difficulty of nested quotation marks, where a quotation can contain another one. This case can produce errors in the annotation.

Quotations Categorization Evaluation

To obtain a preliminary assessment of the categorization task, we carried out a limited evaluation, mostly to guide our future efforts. Thus, we simplified the annotators' task by only testing if a given quotation belongs or not to the main categories: Positive, Negative or Neutral. A deeper evaluation layer could be certainly necessary to determine the sub-category of a given one.

For this second evaluation, we annotated with EXCOM-2 a new set of data and selected randomly 20 annotated quotations from each category of the speaker's opinion. We then obtained 60 mixed annotated quotations.

Three Arabic native speakers with language-related academic background tagged each quotation and decide whether the text snippet (reporting clause) is being talked about in a positive or in a negative light, or if the statement is rather neutral. For this, we decided to hide the contents of the quotes (reported clause) to ensure that annotators will judge based only the words of the enunciator, without mixing with the words of the speaker. The conflicts of tagging were resolved using majority voting principle and the average final agreement is 87% between annotators. The system achieved a Recall value of 85 and a Precision value of 93.

Categorization task results analysis

Taking into account the complexity of the analysis, we consider the overall results to be rather good.

The major difficulty encountered in the categorization task is the mixed and nested opinions [START_REF] Wiebe | Learning subjective language[END_REF]. In fact, different cases are envisaged:

 Same source (speaker), several opinion markers. In the following example, the quotation should be annotated as definition and denunciation: وقد استنكر هذا النار إطالق الفلسطينيون المسؤولون وه وسم "رصاص الشمس صوب ". Palestinian reponsibles have condemned the shooting and called it as "bullets directed towards the sun".

 Different sources, different opinion markers. Here's an example: األسلحة بإرسال "أوباما" تصريح األعلى العسكري المجلس قائد وصف ا جدا" شجاع "تصريح بأنه للمعارضة . The commander of the Supreme Military Council described the declaration "Obama" to send weapons to the opposition as "a very brave declaration". It's difficult here to decide automatically to which speaker attribute this or that opinion. We need to refine our linguistic analysis in order to improve the attribution rules and to have better results.

RELATED WORKS

Quotation extraction has been previously approached using different techniques and for several languages. But, to our knowledge, there are only few operational systems that detect quotations from Arabic texts, and even less for the opinion mining task from quotations [START_REF] Korayem | Subjectivity and Sentiment Analysis of Arabic: A Survey, in Advanced Machine Learning Technologies and Applications[END_REF].

NewsExplorer [START_REF] Pouliquen | Automatic Detection of Quotations in Multilingual News[END_REF] is developed in the European Commission's Joint Research Centre 2 . This tool detects quotations from multilingual live news feeds, including Arabic. The system is able to extract quotes, the name of the entity making the quote and also entities mentioned in the quote. According to the authors, the system recognizes quotations only if it successfully detects three parts: the speaker name, the reporting verb and the quotation. For each person in the system's database, the most recent quotations from and about the person are listed on this person's dedicated information page. For the English language evaluation, the system aimed for high precision (87.5%) at the expense of low recall, as their data contained many redundant quotes. [START_REF] Krestel | Minding the Source: Automatic Tagging of Reported Speech in Newspaper Articles[END_REF] propose a quotation extraction and attribution tool from English newspapers. The system is implemented in GATE and combines a lexicon of 53 common reporting verbs and a handbuilt grammar to detect constructions that match 6 general lexical patterns. The authors evaluate their work on 7 newspaper articles from the WSJ, which contain 133 quotations. For the detection of reporting verb and source, the system achieved a recall value of 2 http://press.jrc.it/NewsExplorer 0.79 and a precision value of 1.00, thus an F-measure of 0.88. For quotation span detection the results are: 99% of precision and 74% of recall.

Google's InQuotes application3 allows users to search for quotes made -in English -by a small selected set of politicians. The webbased interface is structured in topics and displays side-by-side quotes from two actors. Users can search for any keywords in the search area and quotes containing the keywords would be returned. They do not enable search on the speaker itself other than from the selected set, and no implementation details is published about this system.

[21] describe SAPIENS, a system that relies on a deep linguistic processing chain (NE extraction, anaphora resolution, deep parsing…) in order to extract quotations from French news with their author and context. The evaluation was carried out both for the span of the quotation and for the correctness of the author. The evaluation found that 19 out of 40 quotes had a correct span and author, while a further 19 had an incorrect author, and 4 had an incorrect span.

We can observe that most of the prior approaches deliberately choose to focus on the more frequent syntactic structures and on limited lists of reporting markers. In the other hand, all these works carry out a pre-recognition of quotations' sources (holders or speakers) and retain only the quotations where the speaker is identified unambiguously. Finally, none of these systems applies linguistic and semantic analysis like we do in order to categorize automatically quotations according only to the reporting markers.

CONCLUSION AND FUTUR WORKS

Our system makes the semantic information explicit and accessible for end-users. We demonstrated it by adapting the standard IR technologies (i.e. keywords queries matched against bag-of-words document representation) to semantically tagged natural texts. By indexing semantic annotations using such a keyword search engine, we provide a highly scalable and fast semantic search capability by enabling users to search for quotes made by a particular person or about an entity. Each quotation is categorized according to the opinion of the source (speaker) and eventually to that of the enunciator.

The used method is simple and does not require morpho-syntactic pre-processing or NER. For the categorization task we achieve a recall rate of 83% and a precision of 98%.

As future work, we envision to do the following:  Extend the lexical resources with new markers like adjectives (doubtful, boring…); adverbs (finally, unfortunately…) and gerunds (laughing, shouting…). This allows to have more fine-grained categorization and to analyze the intensity of opinions (strong, medium or weak…).  Evaluate the impact of using markers that modify the polarity of an expressed opinion such as valence shifters (negations, intensifiers… [START_REF] Polanyi | Contextual valence shifters[END_REF]), connectives or even modals.  Classify the content of quotes (the reported clause). This feature will give us a complete vision of the polarity of each quotation. Using a classifier could also help us to assign topic tags to each quote.

 Extend the analysis of RS in Arabic and cover indirect, mixed and unmarked RS forms [START_REF] Pareti | Automatically Detecting and Attributing Indirect Quotations[END_REF].  Last, integrate the annotation module as a webservice that can be automatically queried by the user interface in order to directly process new submitted documents in different formats. The application is publicly available at the address: http://equotes.net.

  يص "ال يقول: لزواجها يتقدم الذي الشاب حال ولسان الدهر". أفسد ما العطار لح It's as if the young man said: "the perfumer cannot fix what time has spoiled" Here are some examples of the several different possible constructions in Arabic with verbal, nominal or adverbial reporting markers: or more intermediate entities can be part of the transmission chain between utterer and speaker. We call this entity the "transmitter" (T):I heard from T that X said…/ According to T, X said… Thus, we can formalize a quotation (Q) by this general formula:

Figure 1 .

 1 Figure 1. General architecture of E-Quotes.

Figure 2 .

 2 Figure 2. E-Quotes homepage.

Table 1 . Selected semantic categories Enunciator's opinion Speaker's opinion

 1

	Neg.	Pos	Neutr.	Neg.	Pos.	Neutr.
	Claim	…	Disengagement	Humiliation	Apololgy	Observation
	…		…	Complaint	Praise	Definition
				Criticism	Encourag nt	Declaration
				Mockery	…	Transmission
				Accusation		…
				Contestation
				…

Our corpus is a collection from internet-based Arabic media (Al-Jazeera, BBC Arabic, CNN Arabic, Al-Nahar, Arabic LMD…).

http://labs.google.com/inquotes/ (deprecated).