Julien R Serres

Stéphane Viollet

Insect-inspired vision for autonomous vehicles

Keywords: Bio-inspired sensors, Biomimicry, Bionics, Biorobotics, Bioinspired robotics

Compound eyes are an endless source of inspiration for developing visual sensors • Visual stabilization of robot's flight attitude controlled by artificial ocelli • Ultraviolet celestial cue-based navigation works efficiently under all weather conditions • Combining blurry vision with retinal micro-movements makes robots' visual tracking hyperacute

Abstract: Flying insects are being studied these days as if they were agile micro air vehicles fitted with smart sensors, requiring very few brain resources. The findings obtained on these natural fliers have proved to be extremely valuable when it comes to designing compact low-weight artificial optical sensors capable of performing visual processing tasks robustly under various environmental conditions (light, clouds, contrast). Here we review some outstanding bio-inspired visual sensors, which can be used for either detecting motion in the visible spectrum or controlling celestial navigation in the ultraviolet spectrum and for attitude stabilisation purposes. Biologically inspired visual sensors do not have to comprise a very large number of pixels: they are able to perform both short and long range navigation tasks surprisingly well with just a few pixels and a weak resolution.

Introduction

Insects are definitely an endless source of inspiration for scientists designing innovative sensors. Findings on the nocturnal butterfly's compound eye with its superimposed optics [START_REF] Borst | Drosophila's view on insect vision[END_REF] have been used, for example, to design gradedindex (GRIN) lenses. Studies on the halteres forming the fly's rate gyros [START_REF] Hengstenberg | Biological sensors: Controlling the fly's gyroscopes[END_REF] have inspired what was probably the first micro rate gyroscope based on a vibrating part, which was subjected to the Coriolis force in order to measure the angular speed [START_REF] Droogendijk | Towards a biomimetic gyroscope inspired by the fly's haltere using microelectromechanical systems technology[END_REF]. New photonic structures for energy-saving and healthcare applications have recently been developed based on studies on the black butterfly (Pachliopta aristolochiae) [START_REF] Radwanul H Siddique | Bioinspired phase-separated disordered nanostructures for thin photovoltaic absorbers[END_REF]. Arthropods' and insects' visual systems have also inspired dedicated visual sensors and small, highly efficient optical sensors with which to equip aerial robots [START_REF] Franceschini | Small brains, smart machines: from fly vision to robot vision and back again[END_REF]. In this review, it is proposed to describe some insect-inspired visual sensors which have been used in robotic applications, especially for performing autonomous navigation and flight stabilization tasks. Although we focus here on insects' vision, it is worth noting that many other studies [START_REF] Friedrich | Frontiers in sensing: from biology to engineering[END_REF][START_REF] Raharijaona | Insect inspired visual motion sensing and flying robots[END_REF], such as those on mantis shrimps in particular [START_REF] Daly | Dynamic polarization vision in mantis shrimps[END_REF][START_REF] York | Bioinspired polarization imaging sensors: From circuits and optics to signal processing algorithms and biomedical applications[END_REF], have led to the production of some outstandingly efficient optical sensors.

Smart bio-inspired sensors

Artificial compound eyes and motion sensors

In the field of artificial optical design, since the lens diameter is usually much larger than the light wavelength, the light diffraction is not taken into consideration. The inter pixel angle, defined as ∆φ = d f , where d is the pixels' pitch and f is the focal length, and ∆ρ is the acceptance angle given by the width of the Gaussian angular sensitivity at half height (∆ρ ≈ ∆φ), can be obtained by slightly defocusing the lens. Two artificial compound eyes have been developed, using either inorganic semiconductor photoreceptors comprising 630 pixels, where ∆φ = ∆ρ = 4.2 • [21],mimicking the Drosophila melanogaster 's compound eye (Fig. 1a), or organic photodiodes comprising 256 pixels, where ∆φ = 11 • and ∆ρ = 9.7 • [START_REF] Young | Digital cameras with designs inspired by the arthropod eye[END_REF], mimicking the fire ant's Solenopsis fugax compound eye (Fig. 1b).

The CurvACE artificial compound eye was developed in the framework of a European project (2009-2013; www.curvace.org, [START_REF] Floreano | Miniature curved artificial compound eyes[END_REF]).This functional prototype with its 630 pixels (forming 630 artificial ommatidia) gave a wide field of view (180 • x 60 • ) in a large range of lighting conditions and weights ∼ 2-gram [START_REF] Floreano | Miniature curved artificial compound eyes[END_REF]. A pair of CurvACE sensors was mounted on board an 80-gram micro flying robot called BeeRotor [START_REF] Expert | Flying over uneven moving terrain based on optic-flow cues without any need for reference frames or accelerometers[END_REF] for performing both ground and ceiling avoidance tasks. A minimalistic version of this artificial compound eye containing only three photoreceptors set under a common lens, weighing only 2 mg and detecting movements in two dimensions at rates of up to 300 Hz with an ultra low current consumption of only 0.444 mA, has also been constructed [START_REF] Pericet-Camara | An artificial elementary eye with optic flow detection and compositional properties[END_REF] (Fig. 2d).

A recent optic flow sensor based on the M 2 APix retina (M 2 APix stands for Michaelis-Menten Auto-adaptive Pixel [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelismenten auto-adaptive pixels sensitive to small and large changes in light[END_REF], Fig. 1c) can auto-adapt in a 7-decade lighting range and responds appropriately to step changes of up to ±3 decades [START_REF] Mafrica | Minimalistic optic flow sensors applied to indoor and outdoor visual guidance and odometry on a car-like robot[END_REF][START_REF] Vanhoutte | Time-of-travel methods for measuring optical flow on board a micro flying robot[END_REF]. These pixels do not saturate thanks to the normalization process performed by Very Large Scale Integration (VLSI) transistors [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelismenten auto-adaptive pixels sensitive to small and large changes in light[END_REF]; this advantage is due to the intrinsic properties of the Michaelis-Menten equation [START_REF] Richard | The effects of background illumination on the photoresponses of red and green cones[END_REF] on which these pixels are based. Comparisons between the characteristics of auto-adaptive Michaelis-Menten and Delbrück pixels [START_REF] Delbruck | Adaptive photoreceptor with wide dynamic range[END_REF] under identical lighting conditions (i.e., with the pixels integrated into the same retina) showed that the Michaelis-Menten pixels gave better performances in terms of their dynamic sensitivity and minimum contrast detection levels [START_REF] Mafrica | A bio-inspired analog silicon retina with michaelismenten auto-adaptive pixels sensitive to small and large changes in light[END_REF].

Algorithms of several kinds have been developed for computing local motion, which have resulted in various hardware implementations including templates, time-of-travel, feature tracking, edge counting, edge correlation devices and the Hassenstein-Reichardt correlator [START_REF] Chao | A survey of optical flow techniques for robotics navigation applications[END_REF][START_REF] Richard Jd Moore | Autonomous mav guidance with a lightweight omnidirectional vision sensor[END_REF][START_REF] Xu | Analog VLSI implementation of wide-field integration methods[END_REF], as well as some software implementations [START_REF] Chao | A survey of optical flow techniques for robotics navigation applications[END_REF][START_REF] Vanhoutte | Time-of-travel methods for measuring optical flow on board a micro flying robot[END_REF]. However, analog VLSI motion sensors significantly reduce micro flying robots' power consumption and payload while increasing the bandwidth, thus improving both the precision and the accuracy of the onboard optic flow measurements.

Artificial ocelli

Ocelli are visual sensors which are present in the dorsal part of many insects's heads (Fig. 2a). The word ocellus means a little eye. One to three ocelli can be found, at different points on the top of insects' heads [START_REF] Holger | Ocelli[END_REF]. Ocelli usually consist of three elementary eyes having a lens with a relatively large diameter (ranging from 100µm to 500µm) and a small focal length. Because of the large aperture and the resulting f-number N of the lens (N = f D , where f is the focal length and D is the diameter of the aperture), ocelli can detect low light levels, but the lens is positioned in such a way that the image projected onto the photoreceptors is always under-focused. The exact function of the ocelli has not yet been elucidated, but behavioural experiments on flies have shown that the ocelli are involved in head stabilisation processes [START_REF] Hengstenberg | Multisensory control in insect oculomotor systems. Visual Motion and its Role in the Stabilization of Gaze[END_REF][START_REF] Schuppe | Optical properties of the ocelli of calliphora erythrocephala and their role in the dorsal light response[END_REF], and electrophisiological recordings on dragonflies have even shown that the second-order neuron (L-neuron) directly connected to the photoreceptors may be sensitive to preferred motion in ultraviolet light [START_REF] Berry | The mapping of visual space by dragonfly lateral ocelli[END_REF]. In short, the ocelli are closely involved in the stabilization reflexes responsible for controlling the fly's body rotation (on the pitch and roll axes) and the head orientation (in gaze control processes). Ocellar signals are fused with compound eye signals [START_REF] Matthew M Parsons | Sensor fusion in identified visual interneurons[END_REF] but the ocelli are faster than the compound eyes because a much smaller number of neural processing layers are involved in the processing of the ocellar signals transmitted to the descending neurons [START_REF] Graham | Sensory systems and flight stability: what do insects measure and why?[END_REF]. On the basis of results obtained in biological studies, several artificial ocelli have been developed and tested. Chahl and Mizutani (2012) developed a biomimetic eye composed of 4 pairs of photodiodes which were sensitive to ultraviolet and green lights [START_REF] Chahl | Biomimetic attitude and orientation sensors[END_REF] (Fig. 2c). Artificial ocelli were used by the latter authors to stabilize the roll movements of a small unmanned aerial (fixed wing) vehicle [START_REF] Chahl | Biomimetic attitude and orientation sensors[END_REF]. [START_REF] Gremillion | Biomimetic sensing and modeling of the ocelli visual system of flying insects[END_REF][START_REF] Gremillion | Bio-inspired modeling and implementation of the ocelli visual system of flying insects[END_REF] developed an analog ocellar sensor composed of four photodiodes with a response range of 350-1050 nm, which was used to estimate the pitch and roll movements of an aerial robotic platform [START_REF] Gremillion | Biomimetic sensing and modeling of the ocelli visual system of flying insects[END_REF][START_REF] Gremillion | Bio-inspired modeling and implementation of the ocelli visual system of flying insects[END_REF] (Fig. 2b). Fuller et al. presented a method of stabilizing a micro flying insect by means of an ocelli-inspired sensor (Fig. 2b) to ob-tain angular velocity feedback (instead of attitude feedback) and used this method to stabilize an insect-scale robot in short take-off flights [START_REF] Sawyer B Fuller | Controlling free flight of a robotic fly using an onboard vision sensor inspired by insect ocelli[END_REF].

Celestial compass inspired by insects'dorsal rim area

To be able to travel long distances, insects have to keep a constant heading relative to a stable reference point [START_REF] Wehner | Astronavigation in insects[END_REF]. Desert ants (Cataglyphis fortis) are able to home with a high level of accuracy, based on their knowledge of their heading acquired when exploring the environment [START_REF] Wehner | Astronavigation in insects[END_REF]. Locusts [START_REF] Mappes | Behavioral analysis of polarization vision in tethered flying locusts[END_REF], flies [START_REF] Timothy L Warren | Flying drosophila melanogaster maintain arbitrary but stable headings relative to the angle of polarized light[END_REF][START_REF] Peter T Weir | Anatomical reconstruction and functional imaging reveal an ordered array of skylight polarization detectors in drosophila[END_REF], bees [START_REF] Rossel | Navigation by bees using polarized skylight[END_REF][START_REF] Rossel | Polarization vision in bees[END_REF], ants and dung beetles [START_REF] Dacke | Animal behaviour: insect orientation to polarized moonlight[END_REF] are equipped with an outstandingly efficient optical compass, which is sensitive to the polarized light caused by the atmospheric scattering of the sunlight. The scattering of the sunlight within the Earth's atmosphere produces a polarization pattern across the sky. Solar radiations remain unpolarized until their entry into the atmosphere, where scattering interactions with atmospheric constituents induce the partially linear polarization of the skylight [START_REF] Kinsell | Polarization and Intensity of Light in the Atmosphere[END_REF]. Insects possess photoreceptors in the dorsal region of their eye (the dorsal rim area, DRA) that are specialized in detecting the pattern of polarized skylight [START_REF] Labhart | Specialized photoreceptors at the dorsal rim of the honeybee's compound eye: polarizational and angular sensitivity[END_REF][START_REF] Wehner | Astronavigation in insects[END_REF][START_REF] Peter T Weir | Anatomical reconstruction and functional imaging reveal an ordered array of skylight polarization detectors in drosophila[END_REF]. The first robotic application of the desert ants' DRA was presented in [START_REF] Lambrinos | An autonomous agent navigating with a polarized light compass[END_REF] (Fig. 3a). Chu et al. developed a smaller compass consisting of 6 photodiodes topped by linear polarizers set 60 • apart [START_REF] Chu | Construction and performance test of a novel polarization sensor for navigation[END_REF]. A pair of polarized-light sensors of this kind were tested under a clear sky (Fig. 3b): the accuracy of these polarized-light sensors was found to be within ±0.2 • [START_REF] Wang | A novel autonomous real-time position method based on polarized light and geomagnetic field[END_REF]. A version of the polarization sensor shown in Fig. 3b, composed of just a single unit, which was recently mounted on board a quadrotor (Fig. 3d), gave promising performances: indoor accuracy 0.2 • , outdoor accuracy less than 2 • , and output refresh signal 10 Hz [START_REF] Zhi | A novel attitude determination system aided by polarization sensor[END_REF]. A polarization-based photodetector involving a bilayer nanowire was recently developed and tested under artificial blue lighting, giving a mean error of only ±0.1 • once a polynomial fitting process had been applied [START_REF] Chu | Integrated polarization dependent photodetector and its application for polarization navigation[END_REF]. Other applications of wire grid micro-polarizers have been developed, some of which involve various angles of polarization (in regular steps of 45 • ) [START_REF] Salmah B Karman | Bioinspired polarized skylight-based navigation sensors: A review[END_REF]. Bio-inspired approaches have also been adopted with cameras in the visible range [START_REF] Fan | Design and calibration of a novel camera-based bio-inspired polarization navigation sensor[END_REF] along with the polarization model developed in [START_REF] Lambrinos | A mobile robot employing insect strategies for navigation[END_REF]. The brand new celestial sensor recently developed by the French Biorobotics group in Marseille is composed of two polarization units (POLunits) consisting of only two UV light sensors topped with actuated rotating linear sheet polarizers (Fig. 3c). This approach makes it possible to greatly reduce the number of pixels, but at the expense of the temporal resolution, which is limited by the mechanical rotational speed. This sensor mimicks the UV-sensitivity of the ant's photoreceptors and the log ratio of two orthogonal POL-units, as previously proposed in the Labhart's locust-based model [START_REF] Labhart | Polarization-opponent interneurons in the insect visual system[END_REF]. In addition, this insect-based compass, which is highly reliable and suitable for performing navigation tasks in various meteorological contexts [START_REF] Dupeyroux | A bio-inspired celestial compass applied to an ant-inspired robot for autonomous navigation[END_REF], is able to determine its heading angle with great precision: the median error recorded was only 2.9 • when the sky was slightly cloudy, and 1.9 • in the case of an overcast sky [START_REF] Dupeyroux | A bio-inspired celestial compass for a hexapod walking robot in outdoor environment[END_REF]. Several artificial celestial compass sensors have been produced for robotic and autonomous navigation purposes [START_REF] Dupeyroux | A hexapod walking robot mimicking navigation strategies of desert ants cataglyphis[END_REF][START_REF] Lambrinos | An autonomous agent navigating with a polarized light compass[END_REF][START_REF] Lambrinos | A mobile robot employing insect strategies for navigation[END_REF][START_REF] Zhi | A novel attitude determination system aided by polarization sensor[END_REF].

Fly-inspired hyperacute sensor

The accuracy (acuity) of a contrasting object's angular position measurements depends directly on the position sensor's optical resolution. The acuity of a compound eye might therefore be expected to be relatively poor in comparison with that of the human camerular eye, which contains several million photoreceptors (i.e., pixels). This would be true without the existence of the fly's active visual processing system based on retinal micro vibrations. Since the 1970s, several studies have shown that active retinal micro movements occur in flies, but the exact function of these micro movements and how they contribute to improving the visual acuity have not yet been established [START_REF] Viollet | Vibrating makes for better seeing: from the fly's micro-eye movements to hyperacute visual sensors[END_REF]. However, several authors have integrated micro movements of this kind into their artificial visual sensors, and the results obtained have shown that they were able to locate a contrasting target with much greater accuracy (up to 700-fold) than that achieved using optical systems alone [START_REF] Franceschini | Small brains, smart machines: from fly vision to robot vision and back again[END_REF][START_REF] Viollet | Vibrating makes for better seeing: from the fly's micro-eye movements to hyperacute visual sensors[END_REF]. Thanks to this hyperacuity, it was recently established using a biorobotic approach that a contrasting moving target (moving hands) could be located on a textured background and the distance travelled by a micro robot flying above a textured plane could be measured by processing the visual signals conveyed by the 40 ommatidia in a vibrating artificial compound eye [START_REF] Colonnier | A small-scale hyperacute compound eye featuring active eye tremor: application to visual stabilization, target tracking, and short-range odometry[END_REF]. The presence of hyperacuity has not yet been clearly determined in insects, but a highly counter-intuitive principle in which coarse and blurry vision (due to the Gaussian angular sensitivities of the photoreceptors) is combined with vibration seems to be able to give a more accurate perception of the world.

Insect-based visual guidance

Several ethological experiments have suggested that flying insects rely heavily on optic flow to avoid obstacles and directly control their flight speed in the presence of wind disturbances or changes in the configuration of the environment, as well as to achieve a smooth landing [START_REF] Egelhaaf | Motion as a source of environmental information: a fresh view on biological motion computation by insect brains[END_REF][START_REF] Julien | Optic flow-based collision-free strategies: From insects to robots[END_REF][START_REF] Mandyam | Visual control of navigation in insects and its relevance for robotics[END_REF]. The magnitude of the translational optic flow component is inversely proportional to the distance, which enables flying insects to spontaneously sense the environmental configuration. Two main models have been developed to explain how insects detect the optic flow: the Hassenstein-Reichardt correlator [START_REF] Hassenstein | Systemtheoretische analyse der zeit-, reihenfolgen-und vorzeichenauswertung bei der bewegungsperzeption des rüsselkäfers chlorophanus[END_REF] and the time-of-travel model [START_REF] Franceschini | Small brains, smart machines: from fly vision to robot vision and back again[END_REF]. Although the optic flow is not only used by flying insects [START_REF] Sarmiento | Insights on obstacle avoidance for small unmanned aerial systems from a study of flying animal behavior[END_REF][START_REF] Julien | Optic flow-based collision-free strategies: From insects to robots[END_REF], it has been frequently used in biologically inspired robots to equip them with insect-inspired vision for both short and long range navigation purposes [START_REF] Julien | Optic flow-based collision-free strategies: From insects to robots[END_REF][START_REF] Mandyam | Visual control of navigation in insects and its relevance for robotics[END_REF][START_REF] Strydom | Bioinspired principles applied to the guidance, navigation and control of uas[END_REF].

Conclusion

The latest advances in the field of insect-like robots will enable roboticists to test biological hypotheses on the scale of insects in order to check whether their hypotheses hold true in the physical world [START_REF] Duhamel | Biologically inspired optical-flow sensing for altitude control of flapping-wing microrobots[END_REF][START_REF] Sawyer B Fuller | Controlling free flight of a robotic fly using an onboard vision sensor inspired by insect ocelli[END_REF][START_REF] Farrell | Altitude estimation and control of an insect-scale robot with an onboard proximity sensor[END_REF][START_REF] Palossi | Ultra low power deep-learningpowered autonomous nano drones[END_REF][START_REF] Shyy | Aerodynamics, sensing and control of insect-scale flappingwing flight[END_REF]. The expanding set of roles for which robots have been designed means that they will be able to operate in the near future in many contexts such as cluttered and confined environments including buildings, warehouses, industrial plants, performance halls, urban canyons and forests. In these complex environments, autonomous vehicles will require redundant sensors to improve the reliability of their autopilots. The data transmitted by bio-inspired sensors could therefore usefully complement the existing measurements provided by classical sensors such as global positioning systems and magnetometers.

Figure 1 :

 1 Figure 1: (a) The first artificial compound eye constructed in the framework of the CurvACE European project (www.curvace.org) [21]. Photographic credit: Floreano Dario. This 2-gram sensor includes a matrix of auto-adaptive pixels (630 Delbrück pixels), each of which is covered by a micro lens forming a juxtaposed set of small cylindrically curved elementary eyes, which are comparable in number to the eyes of the fruit fly Drosophila.(b) The first 256-pixel artificial compound eye, which is a moulded piece of poly(dimethylsiloxane) (PDMS) elastomer carrying an array of 16 x 16 convex microlenses covering an area of 14.72mm x 14.72 mm [52]: this number is similar to the number of microlenses present in the eyes of the fire ant Solenopsis fugax. Courtesy from John Roger, University of Illinois and Beckman Institute. (c) The M 2 APix optic flow sensor is composed of 12 Michaelis-Menten pixels (top) and 12 Delbrück pixels (bottom). Adapted from [36].

Figure 2 :

 2 Figure 2: (a) Top view of the wasp's head Poliste from Wikimedia commons (Photographic credit Assafn (2008) under license CC-BY-SA 3.0). Ocelli (a group of 3 small eyes) forming a triangle on the dorsal part of the Poliste bee's head (Poliste's head width: 3.6mm). (b) Picture of a 25-mg ocelliinspired sensor with four phototransistors arranged in a pyramid at the top of an insect-like flying robot called Robobee. Courtesy from Swayer B. Fuller, University of Washington, Seattle, USA. See [23] for details. (c) Artificial ocelli composed of 8 photodiodes (four ultraviolet/green pairs). The sensor identifies the horizon based on the polarization of the sky. Adapted from [4]. Photographic credits: Javaan Chahl and Akiko Mizutani. (d) Picture of a photoreceptor triplet mounted on the PCB surface. Adapted from [43]. Photographic credits: Ramon Pericet-Camara and Floreano Dario, Laboratory of Intelligent Systems, EPFL.

Figure 3 :

 3 Figure 3: (a) The Sahabot 2 robot (2000) with its ant-inspired compass from [35] by permission of Elsevier. (b) Device based on two polarization sensors measuring the heading from [58] under CC-BY License, 2015. (c) Hexabot robot equipped with a pair of UV-polarized light sensors forming a celestial compass from [15]. Photographic credits: Julien Dupeyroux, The Institute of Movement Sciences, CNRS/Aix Marseille University, 2017. (d) Implementation of an extended Kalman filter on board a quadrotor for incorporating the polarization sensor into a conventional attitude determination system, from [64] under CC-BY license, 2018.

Acknowledgements

The authors thank J. Diperi and M. Boyron for their technical support and J. Blanc for improving the English manuscript. This research was supported by the French Defense Agency (DGA), CNRS, Aix-Marseille University, Provence-Alpes-Côte d'Azur région and the French National Research Agency (ANR) via the IRIS and Equipex/ Robotex projects.


Imen Lassoued
email: lassoued.imen@yahoo.fr

Ezzeddine Zagrouba
email: ezzeddine.zagrouba@fsm.rnu.tn

Youssef Chahir
email: chahir@unicaen.fr

A new method using moments correlation for action change detection in videos

Keywords: Action change, correlation matrix, Pose representation False negative False negative Derivative distances vs Frame Indice Frame Indice Derivative distances

Automated characterization of human actions plays an important role in video indexing and retrieval for many applications. Action change detection is considered among the most necessary element to ensure a good video description. However, it is quite challenging to achieve detection without prior knowledge or training. Usually humans are practicing different actions in the same video and their silhouettes give significant information for characterizing human poses in each video frame. We have developed an approach based on pose descriptors of these silhouettes, cross correlations matrices and Kullback-Leibler distance to detect action changes. In this paper, we will focus firstly on the specific problem of change detection in videos. After that, the proposed approach for action change detection will be detailed and tested on Weizman dataset. Finally, experimental results has been analyzed and showed the good performance of our approach.

I. INTRODUCTION

Action change detection is a key parameter in video identification and recognition domains. Currently, most works on the temporal processing of videos separate sequences into shots, i.e. groups of frames filmed from the same camera or viewpoint. This segmentation in shots is not efficient and not suitable for video action recognition and classification domain because action can be practiced in one or more shots. Furthermore, a shot is a technical unit that is often characterized by a short duration and does not really take into account the progress of the action. In this paper, we have developed a new method for action change detection based on a correlation matrix between descriptors of poses of silhouette and the global video. To describe silhouette poses we have used 2D Krawtchouk moments. We have used also a spatiotemporal Krawtchouk moments proposed in our previous work [START_REF] Tumminello | Kullback-Leibler distance as a measure of the information filtered from multivariate data[END_REF] to describe a global video.

The remainder of this paper is organized as follows. Section II will present an overview of existing methods for change detection in videos. In the third section, the different steps of the proposed method based on correlation matrix and poses representation will be described. Section IV will be dedicated to experimental results and analysis. In the last section, conclusion and perspectives will be given.

II. STATE OF THE ART

The technology for organizing and searching images and videos based on their content is still an open research domain. This is especially true in multimedia applications where the difficulty of searching and editing data is often the largest cost factor. Detecting scene, shot or action changes in videos is the first step of extracting content-based information from sequences. In the following, we present some works that deal with action, scene and shot change detection problems.

In dynamic scene analysis, motion detection is often tied to change. Literatures present several approaches for scene segmentation problem. Proposed approach in [START_REF] Rasheed | Detection and representation of scenes in videos[END_REF] consists to transform scene segmentation into a graph partitioning problem. A shot similarity graph is constructed, where each node represents a shot and edges between shots depict their similarity based on color and motion information. Authors in [START_REF] Hanjalic | Automated high-level movie segmentation for advanced video-retrieval systems[END_REF], propose a detecting boundary method based on logical story units by linking similar shots and connecting overlapping links. Key frames for different shots are merged into a larger image and the similarity between shots is computed by comparing these shot images. They use also, approach proposed in [START_REF] Yeung | Segmentation of videos by clustering and graph analysis[END_REF] and a transition graph which is divided into connected subgraphs representing the scenes. Authors in [START_REF] Zhai | Video scene segmentation using Markov chain Monte Carlo[END_REF] propose a method that uses Markov chain Monte Carlo to determine scene boundaries.

Action change detection is the input for many works such as videos actions classification, indexation and retrievals. Literatures show that scene and shots are usually used for video segmentation. Actions in videos are becoming as a mean for video segmentation. Guo in [START_REF] Guo | Action change detection in video by covariance matching of silhouette tunnels[END_REF] proposes a method based on silhouettes framework for action representation and comparison. He uses a non-parametric statistical framework to learn the distribution of the distance between covariance descriptors.

III.PROPOSED APPROACH

The developed approach is composed of several steps represented by Fig. 1. First, human silhouettes are extracted in 978-1-4673-2679-7/12/$31.00 ©2012 IEEE the space-time volumes. Then, we compute poses descriptors and a global video descriptor. The next step consists to calculate a Kullback-Leibler distances between cross correlation matrices of previous descriptors. Finally, we applied a learning algorithm to detect different action change frames.

Figure 1. General architecture for the proposed approach

A. Pose representation and description in space time volume

Human action in a video is composed by a set of poses in different frames. Each action is made by the repetition of a series of poses represented by silhouettes. We choose 2D Krawtchouk moments to describe a silhouette pose in each frame. In fact, Krawtchouk moments are considered as a good form descriptor [START_REF] Yap | Image Analysis by Krawtchouk Moments[END_REF][START_REF] Gautschi | Orthogonal Polynomials: Computation and Approximation[END_REF] and give good results in object recognition domain. We define the n-th order of Krawtchouk polynomial in the variable x as described in [START_REF] Yap | Image Analysis by Krawtchouk Moments[END_REF].

• • (•; • ! • ) = "(-1) $ • $ =0 ( • -1) •-$ ( •-$ ! • -• )( $ • )
(1) Where 0 ≤ n ≤ N x and p x ∈ (0, 1)

( $ • ) = { 1 &' $ =0 •(• -1)..(•-$ +1) $ ! &' $ ≥1 (2)
The set S = {K n (x; p x , N x )} has (N x +1) Krawtchouk polynomials witch satisfy a discrete orthogonality relation of the form

" +(•; , , ! , ) ! ,=0 -& (•; , , ! , )-$ (•; , , ! , ) = .(&, $) (3) Where .(&, $) = ℎ(&, • , ! , )0 &$ (4)
Where i, j = 1 ...Nx and w (x; p x , N x ) is a weight function in x and h is a function depending on i:

+(•; , , ! , ) = ( • ! • ) , (1 -, ) ! -, (5)
δij is the Kronecker delta function and

ℎ(&; • , ! , ) = 1 ( & ! , ) ( , 1-, ) & (6)
The conventional method of avoiding numerical fluctuations for moment computations is by means of normalization by the norm. The normalized Krawtchouk polynomials with respect to the norm K n (x; p, N) is defined as:

-• 1 (•; , !) = -• (•; , !) 23(•; , !) (7)
The set of weighted Krawtchouk polynomials K n (x; p, N) is defined by:

-• 1 (•; , !) = 4 +(• ; , ,! ,) ℎ(•, , ,! , ) -• (•; , , ! , ) (8)
The orthogonality condition becomes

0 •5 = ∑ -• 1 (•; , !)-5 1 (•; , !) ! •=0 (9)
Krawtchouk moments have the interesting property of being able to extract local features of an image. The Krawtchouk moments of order (m+n) in terms of weighted Krawtchouk polynomials, for an image with intensity function, f(x,y) is defined as: Ki (i : 0 to n)

Global video descriptor

Cross correlation matrix XCRi

XCRi, XCRi+1

Kullback-Leibler distances between all XCRi, XCRi+1

Learning algorithm application

Actions change frames

Human silhouettes from video

• •• = ! • " (#; $ 1 , %) ! • " (&; $ 2 , ') ' &=0 % #=0 *(#, &) (10)
The parameters N and M are substituted with N-1 and M-1 respectively to match the NxM pixel points of an image.

B. Pose correlation with a global video

We use a cross correlation 'XCR' to study the correlation for each pose relative to global video sequences. To compute cross correlation, we apply the 2D Krawtchouk moment descriptor for each pose. Spatio-temporal Krawtchouk descriptor [START_REF] Lassoued | Video Action Classification: A New Approach combining Spatio-temporal Krawtchouk Moments and Laplacian Eigenmaps[END_REF] are used to describe global silhouettes volume of video.

Cross correlation is a standard method of estimating the correlation degree between each silhouette pose and a global volume of video. Consider two series x(i) and y(i) where x(i) is the descriptor vector for each pose and y(i) is the descriptor vector of the global silhouettes volume. {i=0,1,2...N-1, N is the descriptor vector length. The cross correlation XCR at delay d is defined as [START_REF] Bourke | Cross correlation[END_REF] +,-=

∑ [(#(/)-•# ) * (&(/-2)-•& )] / 3∑ (#(/)-•# ) 2 / 4∑ (&(/-2)-•& ) / 2 (11)
Cross correlation is a measure of similarity between two different non-identical signals. They detect the presence of one signal in another signal. In our case, XCR gives an idea on the correlation of different poses with the global video. If the same signal is buried in both signals, it will be reinforced in the cross correlation function, whereas the noise which is uncorrelated will be reduced. We use different computing XCR to characterize each silhouette pose in video sequence.

C. Silhouette similarity metric

The metric Kullback-Leibler has been chosen to measure distance between pose descriptors in each frame. Kullback-Leibler distance is very good in quantifying the amount of information present in a sample correlation matrix with respect to an hypothetical reference model. Kullback-Leibler distance has been used previously in probability domain and Tumminello and al [START_REF] Tumminello | Kullback-Leibler distance as a measure of the information filtered from multivariate data[END_REF] compute its analytical form. They show that it gives very good results when applied for measurement between correlation matrices. We define the Kullback-Leibler metric as described in [START_REF] Tumminello | Kullback-Leibler distance as a measure of the information filtered from multivariate data[END_REF].

5(XCR 1 ||XCR 2 ) = XCR 1 (/) log 6 XCR 1 (/) XCR 2 (/) 7 • /=1 = [-XCR 1 (/)589 (XCR 2 (/)) • /=1 -(-XCR 1 (i)log (XCR 1 (/))] ( 11
)
Where n is lines number in cross correlation matrix.

It is noted that the Kullback-Leibler distance takes into account the statistical nature of correlation matrices. Indeed l(XCR 1 || XCR 2 ) is well defined only when matrices XCR 1 and XCR 2 are positive definite. This property is not common to other measures of distance between matrices which are based generally on isomorphism between the matrix space and a vector space.

D. Action change detection algorithm

The developed approach for action change detection is based on the spatio-temporal volumes of human silhouettes. In this work, we have supposed that actions persist for some time and they are not changing rapidly and suddenly. The first step in the process of action change detection is to form a first learning set to detect the first action. This set contains the "M" first frames in video. In the second step, we compute pose descriptors presented previously for each silhouette in the video. A descriptor for the global sequence is also computed. After that, we calculate correlation matrices between the global video descriptor and each silhouette pose descriptor. The Kullback-Leibler distances 'D' between these correlation matrices are determinate. The Next step consists of computing the derivative in time of the matrix distance 'D' to appear peaks changes. The Last step is to apply training algorithm from the frame number (M+1). The next learning set begins just after action change detection frame and contains 'M' frames.

Below, we present the training algorithm for detecting frames of action change.

Change_gpe : change detection frames

Input: d(N) derivative distances between different correlation matrix

For each frame 'j' from M+1 to N

K= learning set: first M frames after detecting change

If( d j> max (K) + epsilon) Change_gpe+ = dj Endif

K= [dj+1….dj+M]

III. Experimental results

A. Weizmann Dataset

The action change process was evaluated on a publicly available benchmark dataset of human action: "Weizmann dataset" (Fig. 2). This dataset composed by 90 low resolution videos (180 * 144, 50 fps) where 9 persons performs 10 actions (bend, jack, jump, jump in place, run, side, skip, walk, wave1hand et wave2hand) .

B. Experimental process

In order to test the performance of the developed approach, we concatenate a series of videos with a time continuous camera.

Illustrative example of concatenated videos is shown in Figure 2. We use the subtraction method described in [START_REF] Kim | Real-time Foreground-Background Segmentation using CodebookModel[END_REF] to obtain moving object silhouettes (silhouette tunnels). Then, we aligned the centroid of individual 2D silhouettes to compensate global object displacements. Precision of detected action boundaries depends on the length of action segments and pose descriptor precision. Clearly, a good descriptor of silhouette poses and a large segment length reduce the uncertainty of action boundary location. We applied our action change detection algorithm using 30 frames for a training set. A careful choice of training set frames number is essential for the performance of our algorithm. We created 9 video sequences test containing single-person practicing several actions. We concatenate all video sequences where the same person is practicing different actions. We have taken the same measures used in [START_REF] Guo | Action change detection in video by covariance matching of silhouette tunnels[END_REF] in order to do comparison with our approach.

Two measures has been used for action detection errors:

• False negative: Frame does not contain action change will be considered as a frame contain action change • False positive: Frame containing action change will be considered as a frame that does not contain it.

Figure 3 shows a curve describing the derivative of the distance matrix 'D' vs frames index for "Daria Weizmann video action". The derivative allows to appear peaks change in videos.

After applying proposed approach to the nine videos action tests, we observe that, our approach has detected all action changes frames in the video, Obtained false positive rate is null. But in some videos, frames do not contain action change they were considered as a frame containing action change. For example the "Daria video" test contain two false negative frames (see figure 3).

VI. Conclusion

In this paper, a new method for action change detection in video has been proposed. This method is based on cross correlation measures between silhouette poses and global video descriptor. We describe each pose using 2D Krawtchouk moments. We develop a training algorithm for detecting frames of action change. The approach was tested with a video sequences containing single-person practicing several actions created from the Weizmann dataset. Experimental results show that our approach detect all action changes in most tested videos.

Figure 2 .

 2 Figure 2. Example of sequences containing human practicing three successive actions: Walk, Run and jack

Figure 3 .

 3 Figure 3. Derivatives distances between poses descriptors vs frames of videos


Imen Lassoued
email: lassoued.imen@yahoo.fr

Ezzeddine Zagrouba
email: ezzeddine.zagrouba@fsm.rnu.tn

Youssef Chahir

Video Action Classification: A New Approach combining Spatio-temporal Krawtchouk Moments and Laplacian Eigenmaps

Action classification and recognition is a challenging research area that has significant applications in computer vision domain including robotics, video surveillance, human-computer interaction and multimedia retrieval. Action classification domain uses a large variety of approaches. This paper proposes a new approach for video actions classification based on extension of Krawtchouk moments in spatio-temporal domain . In fact, Krawtchouk moments have interesting properties for describing structural and temporal information of a time varying video sequence.The proposed approach is composed of three main steps. First, the original video is transformed into a spatiotemporal volume of images. Then, silhouettes of human in movement are extracted from these images to define a 3D shape. In the third step, higher order spatio-temporal Krawtchouk moments are applied to the obtained 3D shapes and Laplacian eigenmaps is used to achieve dimension reduction for different moments vectors . Finally, we use SVM algorithm and computed descriptors to classify actions in videos. This new approach has been validated on the two video datasets Weizmann and KTH. Experimental results show a good classification rate compared to other approaches using different descriptors.

I. INTRODUCTION

Advancing automatic human-action classification methods is of relevance to both scientific and industrial communities. Applications of action classification algorithms include surveillance, video indexing and summarization, etc. However, despite significant efforts by the computer-vision community, human-action classification is still an open problem. Indeed, many works were interested by events or actions in videos and use it as an index for classification and retrieval. Action classification consists to classify action of human detected in a given video. In this paper, a new approach of video action classification using extension of Krawtchouk moments into spatio-temporal domain is presented. These moments are computed for each spatio-temporal silhouettes volumes witch describe a human action. the remainder of this paper is organized as follows . Section I will present an overview of existing methods for action classification and recognition. In the second section, the different steps of the proposed method based on spatio-temporal krawtchouk moments and Laplacien eigenmmaps will be described. Section III will be dedicated to experimental results and analysis. In the last section, conclusion and perspectives will be given .

II. RELATED WORKS

Human action classification and recognition have been studied extensively in recent years and several techniques have been developed for this purpose.These techniques can be organized in two main categories.The first class is based on global image descriptors while the second class uses silhouette descriptors

A. Global image descriptors based methods

There are many existing works in action recognition which are based on global features of images such as optical flow, gradient histogram and intensity. Zelnik-Manor and Irani [START_REF] Zelnik-Manor | Event-Based Analysis of Video[END_REF] used marginal histograms of spatio-temporal gradients at multiple temporal scales to cluster video events. Wu [START_REF] Wu | Templated-based Action Recognition: Classifying Hockey Players Movement[END_REF] developed an algorithm to automatically extract figure-centric stabilized images from the tracking system. He also proposed to use Decomposed Image Gradients (DIG) which can be computed by decomposing the image gradients into four channels to classify the person's actions. Efros and al [START_REF] Efros | Recognizing Action at a Distance[END_REF] have proposed a descriptor based on blurred optical flow measurements and have applied it to recognize actions on ballet, tennis and football datasets. Dollar and al [START_REF] Dollar | Behavior recognition via sparse spatio-temporal features[END_REF] have characterized behaviors through spatio-temporal feature points, in which a behavior was described in terms of the types and locations of feature points present. Song and al [START_REF] Song | Unsupervised learning of human motion[END_REF] have represented an action by 40 curves derived from the tracking results of five body parts using a cardboard people model. Positions, angles and velocities of body parts have been used to establish motion descriptors by Yacoob and al [START_REF] Yacoob | Parameterized modeling and recognition of activities[END_REF]. Ali and Aggarwal [START_REF] Ali | Segmentation and recognition of continuous human activity[END_REF] have used angles inclinations of the torso, the lower and upper parts of legs as features to recognize activity. For this class of methods, the recognition results depend greatly on the recording conditions. Features tracking is complex due to the large variability in the shape and articulation of human body.In particular, perfect limb tracking is not yet well solved.

B. silhouettes descriptors based methods

Many researches in action classification are oriented to human silhouette-based methods [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF][START_REF] Weinland | Motion history volumes for free viewpoint action recognition[END_REF]. In fact, human actions can be characterized as motion of human silhouettes sequence over time . Gorelick et al [START_REF] Gorelick | al Actions as Space-Time Shapes[END_REF] consider human actions as a three-dimension shape induced by silhouettes in the space-time volume and use properties of the Poisson equation solution to extract space-time features such as local spacetime saliency, action dynamics, shape structure and orientation. Guo and al [START_REF] Guo | Action Recognition in Video by Covariance Matching of Silhouette Tunnels[END_REF],have considered action as a temporal sequence of local shape-deformations of object silhouette centroid. Each action is represented by the empirical covariance matrix of 13-dimensional normalized geometric feature vectors that capture the shape of the silhouette tunnel. Kellokumpu et al. [START_REF] Kellokumpu | Human activity recognition using sequences of postures[END_REF] proposed a human activity recognition method from sequences of postures. Sminchisescu et al [START_REF] Sminchisescu | Conditional models for contextual human motion recognition[END_REF] recognized human motions by discriminative conditional random field (CRF) and maximum entropy Markov models(MEMM).they used an image descriptors composed by shape context and pairwise edge features extracted on the silhouette. Recent vision techniques use frequently human silhouette extraction from videos especially in the imaging setting with fixed cameras. Our approach belongs to this class of method which is based on moving silhouette III. PROPOSED APPROACH Researchers have exploited invariant moments in pattern recognition [START_REF] Flusser | Moments and Moment Invariants in Pattern Recognition[END_REF]. Moments which are scalar quantities used to characterize a function and to capture its significant features. Moments have been widely used in statistics for description of shapes. Literature [START_REF] Flusser | Moments and Moment Invariants in Pattern Recognition[END_REF][START_REF] Priyal | A study on static hand gesture recognition using moments[END_REF]show that Zernike and Krawtchouk moments are the most used in shape representation and recognition. Many studies [START_REF] Priyal | A study on static hand gesture recognition using moments[END_REF]show that recognition rate is better by using krawtchouk moments than Zernike moments. some works used Zernike moments to describe human silhouettes and video features for action classification [START_REF] Costantini | Space-time Zernike Moments and Pyramid Kernel Descriptors for Action Classification[END_REF][START_REF] Lassoued | An Efficient Approach for Video Action Classification Based on 3D Zernike Moments[END_REF]. In the proposed approach, our contribution is propose a novel descriptor extending 3D Krawtchouk moments computed for space-time silhouettes volume to describe and classify actions in videos.

Architecture of the proposed approach is composed of several steps represented by Fig. 1. First, human silhouettes are extracted in the space-time volumes. Then, we compute action descriptor using Krawtchouk moments and Laplacian eigenmaps. In the last step, different videos are classified by SVM algorithm.

A. Space-time volume extraction

To extract silhouettes from a video sequence, we applied a foreground segmentation using the Codebook background subtraction method described in [START_REF] Fihl | Tracking of Individuals in Very Long Video Sequences[END_REF][START_REF] Kim | Real-time Foreground-Background Segmentation using CodebookModel[END_REF]. This method has been shown to be robust in handling both foreground camouflage and shadows. This is achieved by separating intensity and chromaticity in the background model. Moreover, the used Fig. 1. General architecture for the proposed approach background model is multi modal and multi layered which is considered as advantage to model moving backgrounds. To obtain a good background subtraction quality over time, it is essential to update the background model.Fihl and al [START_REF] Fihl | Tracking of Individuals in Very Long Video Sequences[END_REF]propose two different update mechanisms to handle rapid and gradual changes. We can use a diverse set of input sequences from both indoor and outdoor scenes by using this robust background subtraction method.

B. Action descriptor computing

We propose a novel descriptor extended of a 3D Krawtchouk moments computed for space-time silhouette volumes extracted from videos in previous step. We first describe the formulation of the Krawtchouk moments in three dimensions, and then introduce the generalization to the spacetemporal domain.

1) 3D Krawtchouk moments : The Krawtchouk polynomials play an important role in coding, graph and group theories [START_REF] Yap | Image Analysis by Krawtchouk Moments[END_REF][START_REF] Gautschi | Orthogonal Polynomials: Computation and Approximation[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF], they form an important family of orthogonal polynomials. We define the n-th order Krawtchouk polynomial in the variable x as described in [START_REF] Yap | Image Analysis by Krawtchouk Moments[END_REF].

K n (x; p x , N x ) = n j=0 (-1) j (p x -1) n-j N x -x n -j x j
(1) Where 0 ≤ n ≤ N x ; p x ∈ (0, 1)

x j = x(x-1)...(x-j+1) j! if j ≥ 1 1 if j = 0 (2)
The set S = {K n (x; p x , N x )} N n=0 has N x + 1 Krawtchouk polynomials witch satisfy a discrete orthogonality relation of the form :

N x=0 w(x; p x , N x )K i (x; p x , N x )K j (x; p x , N x ) = Ψ(i, j) (3)
Where

Ψ(i, j) = h(i; p x , N x )δ ij ( 4
)
Where i, j = 1, ...N x and w(x; p x , N x ) is a weight function in x and h is a function depending on i:

w(x; p x , N x ) = N x x p x (1 -p x ) Nx-x (5)
δ ij is the Kronecker delta function and

h(i; p x , N x ) = 1 N x i 1 -p x p x i (6) K 0 (x; p x , N x ) is the constant polynomial 1 and K 1 (x; p x , N x ) = N x (p x -1) -p x x.
For simplicity, we note K n (x) ≡ K n (x; p x , N x ), then we can obtain the following recurrence relation:

K i+1 (x) = 1 p x (N x -i) * Φ(x) (7)
where

Φ(x) = ([p x (N x -i)+i(1-p x )-x]K i (x)-i(1-p x )K i-1 (x)) (8)
2) Spatio-temporal Krawtchouk moments : In this work, we are interested in the orthonormality condition, so we define the orthonormal Krawtchouk polynomial by

Kn (x; p x , N x ) = w(x; p x , N x ) h(n; p x , N x ) K n (x; p x , N x ) (9)
Krawtchouk moments, unlike Zernike and Legendre moment, belong to class of discrete orthogonal moments.we describe our extension of the Krawtchouk moments in (2d+t).Their use discriminate the original behaviours and minimize the computational time and complexity of the classifier. 2d+t Krawtchouk moment of order (n+m+1) of the function f are obtained from the weighted Krawtchouk polynomials as follows:

ςv nml = Nx x=0 Ny y=0 Nt t=0
Kn,m,l f (x, y, t) [START_REF] Ali | Segmentation and recognition of continuous human activity[END_REF] where Kn,m,l = Kn (x; p x , N x ) Km (y; p y , N y ) Kl (t; p t , N t )

the projection of any 2d+t function f(x,y,t) can be completely reconstructed using the Krawtchouk moments as follows:

f (x, y, t) = Nx x=0 Ny y=0 Nt t=0 Kn,m,l ςnml (12)
We used these moments as a spatio-temporal feature of any video expressed as a function f(x,y,t). We recall that f(x,y,t) is a discrete binary volume. The parameters N x ,N y and N t are in correlation with the dimensions of the binary volume in video. Each video can be expressed by a weighted undirected graph G = (V,E,w), where V ={v 1 ,v 2 ,...,v n } is the set of all voxels (2d+1) of the video. f(v) is represented by a triplet {x, y, t} ∈ R 3 and the ε-neighborhood of v is defined by

N ε (v) = {v ∈ V, f (u) = (x, ý, t)} (13)
Where

|x -x| ≤ ε x ,|y -ý| ≤ ε y , |t -t| ≤ ε t
Many references [START_REF] Saradha | A Hybrid Feature Extraction Approach for Face Recognition Systems[END_REF][START_REF] Shutler | Statistical gait recognition via temporal moments[END_REF] show that lower orders of Krawtchouk moments allow capturing low spatial frequencies features of different images in video. The lower orders of Krawtchouk moments store informations for a specific region-of-interest in images while higher orders are used to capture high spatial frequencies features. Padam and al [START_REF] Priyal | A study on static hand gesture recognition using moments[END_REF] and B.Bayrakta and al [START_REF] Bayraktar | A numerical recipe for accurate image reconstruction from discrete orthogonal moments[END_REF] show that high orders of Krawtchouk moment give more precise information about silhouette reconstruction and classification. That's why, it is interesting to compute higher orders Krawtchouk moments to try to describe more precisely changes in silhouettes poses in extracted volumes. Thus, our descriptor vector f(v) of each video become :

f (v) = ςv nml if n + m + l ≤ s (14)
The next step after computing descriptor vector f(v) for each space time volume is to use Laplacian eigenmaps to find a lowdimensional data representation for each video by preserving local properties of descriptor vector f(v).

C. Laplacian Eigenmaps

Laplacian Eigenmaps (LE) method allow to reduce dimensionality of a given dataset [START_REF] Belkin | Laplacian Eigenmaps for Dimensionality Reduction and Data Representation[END_REF]. As with any data reduction method, the problem is that given a set of x 1 , ..., x M of M points in R l ,find a set of point y 1 , ..., y m in R n (n << l) where yi represents xi. Let y = (y 1 , y 2 , y 3 ...y m ) T , this objective is to minimize the following function:

Π ij Π ij = ij W ij (y i -yj) 2 (15)
Where W ij is defined as:

W ij = exp -||x i -x j || 2 2σ if i &j are connected 0 otherwise (16)
This weight function W ij ensures that points close to each other assigned a large weight while points further apart assigned a smaller weight. Since this function decreases exponentially, points mapped further apart incur a heavier penalty [START_REF] Belkin | Laplacian Eigenmaps for Dimensionality Reduction and Data Representation[END_REF][START_REF] Ghanbari | A Graph-Laplacian-Based Feature Extraction Algorithm for Neural Spike Sorting[END_REF]. The LE algorithm has the following steps:

• First step: The Euclidean distance matrix is computed ||x ix j || 2 , then n nearest neighbours are connected. i.e. if node j is among the n nearest neighbours of i then nodes i and j are connected. • Second step: Weight matrix is computed according to eq.( 16).

• Third step: for the connected component, the generalized eigenvalues and eigenvectors are computed.

Lf = λDf ( 17
)
Where λ is the eigenvalue and f is the corresponding eigenvector With

D ii = j W ij ( 18
)
Laplacien Matrix

L = D -W ( 19
)
• Forth Step: The eigenvectors are sorted according to their eigenvalues:

0 = λ 0 ≤ λ 1 ≤ λ 2 ≤ ...λ m ( 20
)
• Final Step: The mapping of x i into the lower m dimension space is then given by (f 1 (i), ..., f m (i)). Ignoring the first eigenvector f 0 which corresponds to the eigenvalue 0. There are two parameters to be determined in the Laplacian eigenmaps dimension reduction algorithm, namely n and σ. It is reported in [START_REF] Ghanbari | A Graph-Laplacian-Based Feature Extraction Algorithm for Neural Spike Sorting[END_REF][START_REF] Ghanbari | Graph-Spectrum-Based Neural Spike Features for Stereotrodes and Tetrodes[END_REF] that choosing n=12 and σ =1 give a better cluster separation. Finally, Laplacian eigenmaps dimension reduction was limited to four dimensions .

D. SVM classification

To classify actions in videos, many works are proposed using several attributes such as neurones networks [START_REF] Baccouche | Une approche neuronale pour la classification d'actions de sport par la prise en compte du contenu visuel et du mouvement dominant[END_REF], GMM [START_REF] Cao | ACTION DETECTION USING MULTIPLE SPATIAL-TEMPORAL INTEREST POINT FEATURES[END_REF], etc. The most used classifier is SVM because it demonstrates efficient results. SVM is a powerful classifier used successfully in many pattern recognition problems. Consider the problem of separating the set of training data (x 1 , y 1 ), (x 2 , y 2 ), ...(x m , y m ) into different classes where x i ∈ R N , is a feature vector and y i are the different classes. Support Vector Machines are designed for binary classification. When dealing with several classes, as in object recognition and image classification, one needs an appropriate multiclass method. Different possibilities has been proposed in [START_REF] Pontil | Support vector machines for 3-d object recognition[END_REF]. We choose the algorithm named 'one against the others' witch construct n hyperplanes and n is the number of classes. Each hyperplane separates one class from the other classes. This references [START_REF] Pontil | Support vector machines for 3-d object recognition[END_REF][START_REF] Blanz | Comparison of view-based object recognition algo-rithms using realistic 3d models[END_REF] detail the different steps of computing the one against the others SVM multiclass classifier.

IV. EXPERIMENTAL RESULTS

A. Experimentation process

The proposed approach was evaluated on two publicly available benchmark datasets Weizmann and KTH. Experimentation begins by segmenting each video of the dataset in the space-time volume. Then, the associated silhouettes are extracted. Space-time Krawtchouk moments are computed for each silhouette volumes to characterize video. Some preliminary experimentation have been performed and they show that order 100 of Krawtchouk moment was sufficient to have a good description of silhouette volumes. After that, Laplacian eigenmaps was applied for a computed space time Krawtchouk moment to reduce dimension of vectors. In the experiment, we have selected (1/3) of the silhouette series from each action category to form the training set for SVM machine and the remaining videos are used as a test set. The outputs of SVM classifier give the corresponding classes of actions.

B. Experimental results on Weismann dataset

Weizmann dataset is composed by 81 low resolution videos (180 * 144) where 9 persons perform 9 different actions (running, bending, waving with one hand, jumping in place,Jack, jumping, walking, skip, and waving with two hands). Each video clip contains one subject performing a single action. Illustrative examples for each action are shown in Fig. 2.

Experimental results using spatio-temporal Krawtchouk moments are shown by the confusion matrix in Fig. 3. Fig. 4 presents the confsion matrix using spatio-temporal Krawtchouk moments with Laplacian Eigenmaps. The designations used in the Fig. 3 ane Fig. 4 are: a1=" walk ", a2=" run ", a3="skip", a4="jack", a5="jump", a6="jump in place", a7="wave with one hand", a8= "wave with two hands", and a9="bend".these results show that spatio-temporal Krawtchouk moments is effectively for actions characterization,we have a good experimental results with a mean accuracy of 90%. In addition, the use of laplacian eigenmaps to reduce dimensionality of the representative vectors improves the classification rate and the mean accuracy becomes 91.55% . Some confusion are observed in the classification results and this can be caused by similarities found between some actions of the dataset. Fig. 5 shows experimental results on weizmann dataset for several methods of action classification. The comparison shows that our approach achieves accuracy at 91, 55%. So, it is considered among the best methods. This results show the good efficiency of Krawtchouk moment to characterize global space-time shapes. Method Accuracy(%) Gorelick & al [START_REF] Gorelick | al Actions as Space-Time Shapes[END_REF] 97, 5% P roposed approach 91.55 lassoued & al [START_REF] Lassoued | An Efficient Approach for Video Action Classification Based on 3D Zernike Moments[END_REF] 90.4% Dhillon & al [START_REF] Zelnik-Manor | Event-Based Analysis of Video[END_REF] 88.55% Dollar & al [START_REF] Dollar | Behavior recognition via sparse spatio-temporal features[END_REF] 86.7% Niebles & al [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] 72.8% L.Zelnik -Manor & al [START_REF] Dhillon | Combining appearance and motion for human action classification in videos[END_REF] 58.91% Method Accuracy(%) Kim & al [START_REF] Tae-Kyun | Tensor Canonical Correlation Analysis for Action Classification[END_REF] 95.3% P roposed approach 93.83 Costantini & al [START_REF] Costantini | Space-time Zernike Moments and Pyramid Kernel Descriptors for Action Classification[END_REF] 91.3% lassoued & al [START_REF] Lassoued | An Efficient Approach for Video Action Classification Based on 3D Zernike Moments[END_REF] 88.7% Dollar & al [START_REF] Dollar | Behavior recognition via sparse spatio-temporal features[END_REF] 81.17% Niebles & al [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] 81.50% Schuldt & al [START_REF] Shutler | Statistical gait recognition via temporal moments[END_REF] 71.72%

Comparison between KTH accuracy of different classification methods

Krawtchouk moments with Laplacian Eigenmaps. The following designations: A1=" boxing ", A2=" hand clapping ", A3="hand waving," A4="jogging," A5="running", A6="walking". Results show that, there is many confusions between running and jogging. This can be explained by a quite similar video sequences even naked eye cannot fully distinguish the difference between these actions. Fig. 9 shows experimental results on KTH dataset for several methods of action classification. The presented methods are based on Zernike moments [START_REF] Lassoued | An Efficient Approach for Video Action Classification Based on 3D Zernike Moments[END_REF][START_REF] Costantini | Space-time Zernike Moments and Pyramid Kernel Descriptors for Action Classification[END_REF], histogram representations of the local space-time interest points [START_REF] Dollar | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Shutler | Statistical gait recognition via temporal moments[END_REF]and PLSA [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF]. The comparison shows that our approach achieves accuracy at 93, 33%. So, it is considered among the best methods. This results show the good efficiency of Krawtchouk moment to characterize global space-time shapes.

V. CONCLUSION

In this paper, we have developed a new approach for video actions classification and characterization based on a compact descriptor for spatio-temporal silhouettes. This descriptor uses a new instance of Krawtchouk moment in spatio-temporal domain to characterize actions of persons. The approach was tested on the KTH and Weizmann datasets and experimental results show a good classification rate compared to other classification methods in the literature. Our future work will deal with evaluation of this method on more realistic datasets. We will also integrate and evaluate the performance of this work in the framework of video indexing and retrieval.

Fig. 2 .

 2 Fig. 2. Actions of Weizmann dataset.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Confusion matrix of Weizmann dataset using Krawtchouk moments.

Fig. 5 .

 5 Fig. 5. Comparison between weizmann accuracy of different classification methods

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig. 6. Actions of the KTH dataset

Fig. 9 .

 9 Fig. 9.Comparison between KTH accuracy of different classification methods


A Bekkari
email: a_bekkari@yahoo.fr

S Idbraim

K Housni
email: khalidhousni@yahoo.fr

D Mammass
email: mammass@univ-ibnzohr.ac.ma

Y Chahir

Classification of high resolution urban satellite Images combining SVM and Graph Cuts

Keywords: Graph Cuts, Satellite image, Space and spectral information, SVM

The classification of remotely sensed images knows a large progress seen the availability of images of different resolutions as well as the abundance of the techniques of classification. Moreover a number of works showed promising results by the fusion of spatial and spectral information. For this purpose we propose a methodology allowing to combine this two information to refine an SVM classification, The approach uses graph cuts to improve the SVM algorithm, as graph cuts introduce spatial domain information of the image that is lacking in the SVM.

The proposed approach is tested on common scenes of urban imagery. The experimental results show satisfactory values and are very promising.

I. INTRODUCTION

With the commercial emergence of the optical satellite images of sub-metric resolution (Ikonos, Quickbird) the realization as well as the regular update of numerical charts with large scales becomes accessible and increasingly frequent. The classification of such images is similar to that of other types of images, it follows the same principle, and it is a method of analysis of data that aims to separate the image into several classes of interest, in order to gather the data in homogeneous subsets, which show common characteristics. It aims to assign to each image's pixel a label what it represents in a scene (a zone of vegetation, a water zone, etc) [START_REF] Samson | Contribution à la classification des images satellitaires par approche variationnelle et équations aux dérivées partielles[END_REF].

Several techniques exist, in this work, we use SVM. This method is actually no more than an algorithm of training and classification. It is about a problem of optimization that makes possible the separation of a field into two or several classes. The problem consists in transforming the space in which one works in another space known as large-sized and inside of which we will establish a separation in various classes. The passage from one space to another is carried out according to some mathematical transformations that use the nonlinear functions, called kernel functions.

The proposed method consists in combining space and spectral information to obtain a better classification, we start with a spectral classification with SVM. Then, we apply the Graph Cuts approach which takes in account the space dimensions of the classification. Experimental results are provided and comparisons with morphological approach applied to the spectral classification are made to illustrate that the method is able to find better class.

This paper is organized as follows. In the second section, we give outlines on the used classifier: Support Vector Machines (SVM). In the section 3, the used Graph Cuts approach is described. In Section 4, the results are presented with numerical evaluation. Finally, conclusions are given in Section 5.

II. SPECTRAL CLASSIFICATION WITH SVM

The support vectors machines (SVM) [START_REF] Fauvel | Spectral and Spatial Classification of Hyperspectral Data Using SVMs and Morphological Profiles[END_REF]- [START_REF] Sujeevan | Apprentissage à base de Noyaux Sémantiques pour le Traitement de Données Textuelles[END_REF] introduced by Vapnik is a technique of construction of optimal hyperplanes separating N classes and which provides a continuous function of discrimination. Data are projected in a deployed space of large dimension (space of Hilbert) in order to define a linear separation in this space, before returning back to the initial space. The choice of separation: hyperplane which classifies the data correctly (when it is possible) and which is "as far as possible from all the examples" [START_REF] Bousquet | Introduction au Support Vector Machines (SVM)[END_REF] as shown in Fig. 1. We consider the dual problem by introducing the multipliers of Lagrange for each constraint. Here for example there is a constraint of learning that gives us a problem of quadratic programming of dimension N (the number of examples). With the Hessian Matrix: (x i x j ) i;j .

(3)

We have the following property and decision function ( 4) Where corresponds to the closest points not-null. As error of treatment one introduces variables ' ressort' to soften the constraints, and one penalizes by the going beyond the constraint.

(5)

In the not-separable case the dual problem will have the same form, the only difference is the upper limit on α. Instead of seeking a hyperplane in input data, we access to an intermediate space of representation of great dimension. Several cores are used with the most frequent SVM methods. In our case we have used a polynomial kernel. [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] The result image of this stage of spectral classification will be refined by the application of the Graph Cuts.

III. GRAPH CUTS APPROACH.

Graph Cuts can be used to conveniently minimize energies often used in computer vision. In this section we give a quick summary [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF].

A. The minimized energy

The main idea of a graph cuts is to bring back the problem of minimization of energy to a problem of minimal cut in a graph.

Graph Cuts finds the optimal solution to a binary problem. However when each pixel can be assigned to many labels, finding the solution can be computationally expensive. For the following type of energy, a series of graph cuts can be used to find a convenient local minimum:

¦ ¦ ∈ = = + = + = i N j n i j i j i p i i i smooth data x x V x D E E x E .. 1 1 ) , ( ) ( ) ( (10)
Where E smooth is a piecewise smoothness term, E data is a data term, P is the set of pixels in the image, V (x i , y j ) is a smoothness penalty function to impose a spatial consistency, D(x i ) is a data penalty function and (X p ) p=1... n is a vector of variables in finite space L (L for label). Every pixel is associated with a variable X i . N i designate the set of the neighbors of the pixel i, and the construction of graph is done as follows:

Each pixel P ij in the image corresponds to a node V ij in the graph. Two additional nodes are the source and the sink, respectively the object and the background. Each node (pixel) is linked to its neighbors by edges n-link (neighbor), with connectivity chosen, and whose capacities depend on differences in intensity. Each node (pixel) is also connected by edges t-link to the terminals (source and sinks) Fig. 2. A cut C of graph G (V, E) is a partition of the vertices V into two sets, such that the terminals belong to each set. In combinatorial optimization, the cost of a cut is usually defined as the sum of the weights corresponding to the edges it serves [START_REF] Boykov | Graph Cuts and Efficient N-D Image Segmentation[END_REF] as is formulated in equation 11.

( 1 1 ) In our case, one is going to use the algorithm alphaexpansion, this algorithm permits to minimize the energy E on a finite set of labels L and a class V called penalty metric. V is metric on the space labeled L if it satisfies:

V (α, β) =0 ⇔ α = β ou V (α, β) 0 ⇔ α β V (α, β) = V (β, α) >0 V (α, β) <= V (α,Ȗ) + V (Ȗ,β) (12)

B. Minimization algorithm

The main idea of the alpha-expansion algorithm is to successively segment all α and non-α pixels with graph cuts and the algorithm will change the value of α at each iteration. The algorithm will iterate through each possible label for α until it converges.

At each iteration, the α region Pα can only expand. This changes somehow the way to set the graph weights. Also when two neighboring nodes do not currently have the same label, an intermediate node is inserted and links are weighted so they are relative to the distance to the α label.

IV. EXPERIMENTATIONS AND RESULTS

A. Data

We used two multispectral satellite images (Quickbird) represented in figure 4 (a), with respective size 240 by 360 pixels and 500 by 280 pixels. The idea for a good spectral classification of the pixels is to directly give the image's pixels value as input data of the classifier.

We have as at last, for each image, two files "TrainFile.dat" and "TestFile.dat" containing respectively 8 516 and 8 451 individuals (pixels) for learn, 86 400 and 140 000 individuals for test (to classify), and divided on the following classes:

B. Results

In this section we present the results obtained, first, with the SVM classifier. Thereafter, we show the interest of the use of the Graph Cuts to refine the result of the classification. We have used the toolbox "Support Vector Machine toolbox Version 2.51 (January 2002) of Anton Schwaighofer [START_REF] Schwaighofer | Support Vector Machine toolbox Version 2[END_REF] (Institute for Theoretical Computer Science of Graz in Austria)" implemented in Matlab, with RBF kernel; but the results were not satisfactory, so we used SVM light wich is an implementation of Support Vector Machines (SVMs) in C language [START_REF]Complexity Reduction in Multivariate Data[END_REF] with RBF kernel.

To these images ( At first sight, we note that we have a great difference between the results; the classification resulting from combining SVM-Graph cut is visually more satisfactory than those of SVM and SVM-Morphological operations since it is less noisy, while in the SVM classification we have an effect of salt and pepper. The resulting SVM-Graph Cut matches well with an urban land cover map in terms of smoothness of the classes, also it represents more connected classes. For the SVM-Graph Cut method a total accuracy of 96.05% was achieved, slightly higher than the accuracy of 92.45% derived by the SVM-Morphological operations classification and of 87.22% derived by the SVM classification (detailed in the following table) V. CONCLUSION

In this paper, we have presented a methodology which makes it possible to combine space and spectral information to refine the classification of multispectral satellite images. The application of this methodology gives more satisfactory results, however it remains to improve even more these results. In future work, to achieve this goal, we will be concentrating on the study of the cores in order to determine which is appropriate one for this type of classification.

This work was funded by CNRST Morocco and CNRS France Grant under "Convention CNRST CRNS" program.

Figure 1 .

 1 Figure 1. The optimal hyperplane separating two classes

( 6 )

 6 And the solution is[START_REF]Complexity Reduction in Multivariate Data[END_REF] The problem and its solution depend only on the scalar products . Rather than to choose the non-linear transformation , we choose a function called kernel function witch represents a scalar product in intermediate space representation and the examples distribution in this space.

Figure 2 .

 2 Figure 2. Construction of graph for a 3x3 image with the connectivity V8. Each pixel corresponds to a node, and all pixel nodes are connected to the source and the sink.

Figure 3 .

 3 Figure 3. Generalization to a multi-objects. (a) A Graph G = (V, E), with multiple terminals 1,….., k (b) A multi-way cut on G.

  (1-b) and (2-b) in Fig. 4) we have applied the morphological operations: opening and closing, what gives us the result images (1-c) and (2-c) in Fig. 4, and then we apply Graph cut approach to the same images what gives us the result images (1-d) and (2-d) that are represented in Fig 4.

Figure 4 .

 4 Figure 4. (1-a) and (2-a) original images, (1-b) and (2-b) result by SVM classification, (1-c) and (2-c) result by classifier SVM ameliorated by the morphological approach, (1-d) and (2-d) result by classifier SVM ameliorated by the graph cuts approach.

TABLE I .

 I

		Different classes
	Class N° Class color
	1	Asphalte
	2	Green area
	3	Tree
	4	Soil
	5	Building
	6	Shadow

TABLE II

 II

	.	TOTAL ACCURACY ACHIEVED BETWEEN TESTED IMAGES
	Method	Image 1-a fig 4 Image 2-a fig 4
	SVM	87.56%	86.88%
	SVM-Graph Cut	96.13%	95.97%
	SVM-Morphological	94.32%	90.58%
	operations


Stéphane Grenier

K J Thomas

J P Hill

U Staub

Y Bodenthin

M Garcia-Fernandez

V Scagnoli

V Kiryukhin

S.-W Cheong

B G Kim

M García-Fernández

J M Tonnerre

Direct observation of oxygen superstructures in manganites

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

MnO3, we observe a 2p charge ordering described by alternating hole-poor and hole-rich MnO planes that is consistent with some of recent predictions.

Fascinating macroscopic properties may emerge from the electronic and magnetic orderings in doped 3d metal oxides. In cuprates, charge and spin stripes could be relevant to high-T C superconductivity [1] whereas the colossal magnetoresistance in manganites is fundamentally related to the stability of the correlated orderings of polarons, charges, orbitals and spins [START_REF] Chatterji | Colossal Magnetoresistive Manganites[END_REF]. The relationship between the orderings and the transport properties has been adressed both theoretically and experimentally focusing on the 3d metal atoms, often neglecting the ligands' degrees of freedom. However, the active states are not ionic 3d metal orbitals, but, rather hybridized metal 3d -oxygen 2p states, therefore an ordering of the oxygens must equivalently accompany an ordering of the metals. In cuprates, the role of the oxygen atom is now always considered and, taking a recent example, the ordering of hole-doped oxygens was directly observed and discussed in the context of the stripes [START_REF] Rusydi | [END_REF].

In manganites, an electronic ordering on oxygens has not been detected yet, although recent experiments have suggested a crucial role of the O atoms in the correlated orderings on Mn atoms. X-ray spectroscopy of Mn atoms has revealed a small charge disproportionation, emphasizing the inadequacy of the traditional model of strongly localized charge ordering (Mn 4+ /Mn 3+ ) [4]. The conductivity was also found related to the oxygen electronic configuration [5], and it was proposed that the oxygen atom bridges an electron between two Mn atoms of nearly the same valence, coupling them magnetically [6]. Actually, these results point out the role of the 2p-3d hybridization in determining the magnetic exchange couplings and conductivity, the traditional picture being the one where the atomic 3d orbitals define exchange magnetic pathways between Mn atoms, the oxygen 2p states being filled.

Meanwhile, new theoretical models beyond the Mncentered description also suggested that oxygen superstructures play an important role in determining the ground states. Ferrari et al. [7] explained the insulating behavior of the charge/orbitally orded half-doped system by an ordering of O holes -"oxygen stripes" of varying valences (incidentally, having the same periodicity as the Mn orbital ordering). Efremov et al. [8] proposed that the charge ordering could correspond to a charge density wave (CDW) that is either Mn-centered or O-centered, and that an intermediate CDW (an intermediate O-Mn charge transfer) would potentially give both ferromagnetism and ferroelectricity. Also, Volja et al. [9] insisted on the relevance of the Mn charge ordering concept, if the hybridization with the hole-doped O atoms is properly considered.

Experiments that directly probe the oxygen contribution to the ordered states provide essential feedback to these theoretical models. In this Letter, we show that O K-edge resonant diffraction spectra reveal the oxygen superstructures in manganites. We first report the direct observation of the orbital ordering of hole-doped, hybridized, O 2p-states in a Mn-centered, Mn-orbitally ordered manganite, Bi 1-x Ca x MnO 3 (x = 0.69). Second, we report the charge ordering on the oxygen in La 7 8 Sr 1 8 MnO 3 ; our observations confirm the stacking of alternate hole-rich and hole-poor planes. In both cases, the O states are directly related to the Mn states, emphasizing the hybridized nature of the active states involved in the electronic orderings.

Bi 0.31 Ca 0.69 MnO 3 (BCMO) is representative of the Mn-centered orbitally ordered CDW phase, which is usually described as Mn stripe order. This phase is robust in manganites, from half-doping to x = 0.8 [START_REF] Chatterji | Colossal Magnetoresistive Manganites[END_REF]. The CDW exhibits polaronic sites (Mn 3+ ) placed as far as possible from each other, with an antiferro order of the valence orbital, while Mn 4+ sites are isotropic [10] (Fig. 1). As the doping increases, the polaron density diminishes, and a larger orbital ordering periodicity is obtained (Λ ≈ 17 Å for BCMO), which is large enough to diffract soft x-rays near the O K-edge (λ = 23.4 Å at 530 eV). BCMO orders below T OO = 250 K. The second system, La 7 8 Sr

1 8 MnO 3 ' b a BCMO LSMO z=1/2 z=0 z=1 z=3/2 z=0 ! k ! ' k' " Q # #
FIG. 1: Simplified orderings in BCMO and LSMO. Closed circles represents polaronic Mn 3+ atoms, open circle are Mn 4+ and small circles are the O sites; the orbital ordering in BCMO is also shown. The structure in the a-b plane of BCMO repeats in adjacent planes, while LSMO planes alternate between being hole-rich (z=0 and 1) and hole-poor (z=1/2 and 3/2) [11]; for clarity the oxygens are represented in the first plane only. The scattering geometry is indicated, ψ is the azimuthal angle, σ and π are the two polarization components.

(LSMO), exhibits several phase transitions upon cooling. At T OO1 ≈ 280 K, a polaronic insulating orbital ordering takes place. Then, the system becomes a metallic ferromagnet at T C ≈ 180 K but finally stabilizes below T OO2 ≈ 150 K as an insulating ferromagnet. It was recently demonstrated that the OO1 to OO2 transition corresponds to a rearrangement of the polarons in a larger unit cell [11]. Here, we directly probed the electronic ordering that accompanies the polaron rearrangement allowing the test of two recent models for the electronic structures (described below).

The BCMO compound was prepared by the flux technique and LSMO by the floating zone technique; both samples were characterized by hard x-ray diffraction. The crystals were cut and polished with the normal to the surface along [010] for BCMO, and along [001] for LSMO. We refer to the Pbnm orthorhombic notations for the unit cell.

The data were collected at the SIM beamline of the Swiss Light Source using the RESOXS set-up built for soft x-ray diffraction and reflectivity in ultra high vacuum [12]. The experiments were performed as in conventional diffraction but with the incident energy varied through the O K-edge whilst moving the diffractometer angles to maintain the diffraction condition. The O Kedge corresponds to the photoelectric transition of a 1s electron to unoccupied orbitals ψ n . This transition is accounted for in the scattering factor by the overlap integral ε• ψ * n (r)rψ O 1s (r)dr, ε being the photon polarization. The resonant and the Thomson scattering factors are then weighted by the crystallographic phase-factor at the selected Bragg reflection, F (Q, ω) = j f j (Q, ω)e iQ•rj , ω being the energy of the photon and the energy between ψ n and ψ O 1s [START_REF]Resonant Anomalous X-Ray Scattering, Theory and Applications[END_REF]. By sweeping the incident photon energy through the O K-edge, a resonant reflection provides evidence of the periodicity of unoccupied states ψ n from and above the Fermi level (ε f ). The states probed are those without an even symmetry relatively to the oxygen 1s orbital ψ O 1s (which is even), as easily seen from the overlap integral. Near ε f , those may be O 2p's, or orbitals from nearby atoms with some projection on the oxygens (e.g. 3d), or orbitals made of a hybridization of the two. Farther above ε f , the states are more delocalized and may not carry an information on the electronic structure but rather on all surrounding atoms, i.e. a structural information. We also measured azimuthal scans (record of the reflection intensity while rotating the crystal in a plane normal to Q) which allow one to rotate the polarization of the photon relatively to the atoms thereby probing different directions of the unoccupied states (ψ 2px ,...). We could select the two incident polarizations, namely σ or π, perpendicular to and within the scattering plane, respectively (Fig. 1), the detector integrating photons of both polarizations.

Fig. 2a shows the O K-edge RXD spectrum at the (0 0.31 0) superstructure reflection we found in BCMO, for π and σ incident polarizations. No scattering is observed outside a narrow energy range (1.1 eV) at the edge of the absorption spectrum (given by the fluorescence yield). We observed equal spectra for the two incident polarizations. As has been discussed elsewhere [10] this implies that the scattering process is one in which the polarization of the photon is rotated, of the type σ → π or π → σ, that is, with zero σ → σ and π → π scattering. The incommensurability of this reflection is observed to vary with temperature, stabilizing at about 0.31 r.l.u., below T OO (Fig. 2b). A final observation, from Fig. 2c, is the extinction of the reflection when the polarization of the incident photon is perpendicular to the ordered (a, b) plane.

The first observation indicates a resonant superstructure reflection from an ordering of the very first unoccupied states from ε f projected on the O atoms (ψ O 1s ), with the propagation Q = 0.31 r.l.u, corresponding to the periodicity of the Mn orbital ordering [10]. Following earlier analysis of the absorption data [START_REF] Ju | [END_REF], the comparison with the fluorescence yield allows us to identify the ordered states as the 2p states hybridized with the 3d. The narrow spectral width observed reflects the width of the (unoccupied) hybridized band. The second observation demonstrates that there is no charge ordering on O atoms at this wave vector. Indeed, a CDW of this periodicity would scatter in the σ → σ channels, which is absent on this reflection to within the uncertainty of our measurements. Furthermore, a charge order scatters at all azimuthal angles [15,16], at odds with the data. These three observations prove that the O 2p states are holedoped and show orbital ordering, and not charge ordering at this propagation vector. Therefore, the data exclude a direct extension of the model of oxygen stripes, with the FIG. 2: a) The (0 0.31 0) superstructure reflection, corrected from fluorescence but not for self-absorption; nevertheless, the intensity is zero off the O K-edge. b) Temperature dependence of the peak position at the phase transition. c) Azimuthal dependence displaying a two-fold symmetry with a maximum with the incident polarization along a, and zero along c, taken at 528.75 eV, T=200K. periodicity of the Mn orbital ordering, from half-doping [7] to this high doping.

The observation of 2p orbital ordering makes intuitive sense in light of the 2p -3d hybridization and the earlier observation of this same orbital ordering, but projected on the Mn atoms (ψ 2p ), at the Mn 2p ↔ 3d L-edge [10]. Specifically, these states are centered on the polaronic Mn atoms, with a configuration depicted in Ref. [9,17] clearly exhibiting the unoccupied 2p ordering on the four O surrounding the polaronic Mn. In agreement with this model, our results demonstrate the charge transfer nature of the compound and the coupling between the O and Mn orbital ordering.

We now turn to La 7 8 Sr 1 8 MnO 3 . Fig. 3a shows the RXD spectra of the (00 1 2 ) superstructure reflection at the O K-edge for two incident polarizations. Previous studies have already reported the unusual stacking that doubles the unit cell along c below T OO2 [18]; the present data also reveals a specific 2p-state reordering (Fig. 3a andb). The fluorescence yields (proportional to mf ) and the RXD spectra are different for the two polarizations, the differences provide evidence of an anisotropy of the unoccupied O states near ε f . The main characteristic of the 2p ordering is identified by considering the azimuthal FIG. 3: a) RXD spectra of the (00 1 2 ) reflection at the O K -edge of La dependence of the reflection. The azimuthal scan never goes to zero; it has a cos 2 + const dependence (Fig. 3c). A tensorial analysis of the resonant scattering permits to easily identify the origin of the two terms [16]: The constant term is due to a net difference in the total charge carried by the oxygens on different planes, whereas the sinusoidal dependence is due to the relative direction of the polarization of the photon with the anisotropic O electronic structure.

The diffraction vector (0 0 1 2 ) corresponds to the net difference in scattering, hence to a net difference in holes, from planes separated by ∆z = 1; a charge ordering at the (0 0 1 2 ) vector provides a strong constraint to the theoretical models for the charge ordering pattern. The models by Korotin et al. [19] and by Geck et al. [11] both propose that hole-rich and hole-poor Mn planes alternates along c but with different stacking orders. In MnO3, σ → σ + π channels, T = 30 K. The O nearedge (≈ 530 eV) and the Mn L III/II -edges (≈ 640 and ≈ 652 eV) probe the active states near ε f , while the region between 535 and 560 eV correspond to states that are delocalized (high energy from ε f ). Inset shows the diffraction peak at 576 eV, emphasizing the existence of the reflection far above the edge.

Geck's model every other planes are identical when projected on the c axis: they should not give the charge order scattering we observe. In Korotin's model, three successive hole-rich planes alternate with one hole-poor plane. Such order should give rise to a strong charge order signal on the O atoms because of the hybridization, as we observe. We note that only Geck's model explains reflections with a planar component observed elsewhere [11].

Scattering is observed at this wave-vector for energies well above the O K-edge (Fig. 4). Increasing the energy from the near-edge, the photoelectron probes states that are more delocalized, thus more sensitive to the crystal structure due to band structure effects. These features signal presence of lattice distortions accomodating the charge ordering on oxygen atoms. At higher energy, the Mn L-edges correspond to the direct probe of the states nearby ε f , like the O near-edge, but probed by the Mn 2p electrons and thus projected on the Mn atoms. Some of the near ε f hybridized states are probed at both edge, projected on O and Mn, respectively. The intensities at both near-edges in Fig. 4 provide the relative scattering strength of each atoms which should help determine the hybridization, charge transfer and overlap, between the O and Mn orbitals.

In conclusion, resonant x-ray diffraction at the O Kedge has been used to detect the electronic superstructures of the 2p states near ε f in two manganites. In Bi 0.31 Ca 0.69 MnO 3 , we show evidence of an orbital ordering of hole-doped hybridized 2p -3d, and contradict O charge stripes with the same propagation vector as the Mn orbital ordering. In La 7 8 Sr 1 8 MnO 3 , the data provided evidence of a charge ordering on the O atoms with the (0 0 1 2 ) propagation vector, corresponding to a specific plane stacking with differing hole concentrations. The orderings on O atoms are not experimentally dissociated from the orderings on the Mn atoms, in both compound, emphasizing the hybridized nature of the orbitals near ε f . Quantification of the hole densities and of the 2p-3d hybridization requires ab initio calculations of the ground state and the excited state using dedicated formalisms (the excited state has a strong Coulomb potential in a core shell and an extra electron in the valence shell). The RXD technique can also be chemically-sensitive to the magnetic moment, therefore these results suggest potential measurements of magnetic superstructures on the oxygens. Thus, the RXD data open a view on the 2p-3d states, the magnetic exchange couplings between 3d metals and on the electronic superstructures at play in this strongly correlated system.

7 8 1 8

 71 FIG.3: a) RXD spectra of the (001 2 ) reflection at the O K -edge of La 7 8 Sr 1 8 MnO3, with two incident polarizations, T = 30 K. ψ ≈ 90 • . b) Temperature dependence of the reflection. c) Azimuthal dependence at 529.2 eV, σ → σ + π channels, compared to a cos 2 +const. function (solid line), 0 • is σ incident polarization along b, 90 • along a.

FIG

  FIG. 4:RXD spectrum of the (00 1 2 ) reflection of La 7 8 Sr 1 8

We benefitted from the excellent support of the staff on X11MA-SLS, PSI. M.G.-F. thanks the Swiss National Science Foundation. This work was also supported by US Dept of Energy, Division of Materials Science, under contract No. DE-AC02-98CH10886. We thank J. Debray and S. Garaudée of the Institut Néel for excellent technical assistance.