R Merrouche

A Yekkour

Y Coppel

N Bouras

L Lamari

A Zitouni

F Mathieu

A Lebrihi

Nasserdine Sabaou
email: sabaou@yahoo.fr

Effective biosynthesis of benzoyl-pyrrothine dithiolopyrrolone antibiotic by cinnamic acid-precursor addition in culture of Saccharothrix algeriensis NRRL B-24137

Keywords: antimicrobial activity, cinnamic acid, dithiolopyrrolone antibiotics, precursor, Saccharothrix algeriensis

Significance and Impact of the Study: Dithiolopyrrolone antibiotics, known for their strong antimicrobial activities, gained greater interest after the discovery of their antitumor properties. Depending on precursors added, Saccharothrix algeriensis NRRL B-24137 has the ability to produce several dithiolopyrrolones derivatives. Since biological activities of dithiolopyrrolones are related to their variable structure, discover of new natural analogues to be therapeutically explored remains a significant framework of research. In this study, a new dithiolopyrrolone derivative was purified from the fermentation broth of S. algeriensis NRRL B-24137. This new antibiotic, characterized as benzoyl-pyrrothine dithiolopyrrolone, was induced by adding cinnamic acid, as precursor, to a semi-synthetic medium.

Introduction

Dithiolopyrrolones are a group of antibiotics that possess the unique pyrrolinonodithiole (4H- [1,2] dithiolo [4,3-b] pyrrol-5-one) skeleton linked to two variable acyl groups [START_REF] Jiang | Disulfide-and multisulfide-containing metabolites from marine organisms[END_REF]. Because of their strong activities against a variety of Gram-positive and Gram-negative bacteria, eukaryotic micro-organisms (yeast, filamentous fungi and amoeboid parasites) and tumour cells, dithiolopyrrolone derivatives gained great interest [START_REF] Webster | Bacterial metabolites[END_REF][START_REF] Li | Dithiolopyrrones: biosynthesis, synthesis and activity of unique class of disulfide-containing antibiotics[END_REF][START_REF] Merrouche | Efficiency of Saccharothrix algeriensis NRRL B-24137 and its produced antifungal dithiolopyrrolones compounds to suppress Fusarium oxysporum-induced wilt disease occurring in some cultivated crops[END_REF]. To date, approximately 30 naturally occurring dithiolopyrrolone compounds were listed and divided into three subgroups: N-methyl, N-acylpyrrothine (pyrrothine type), N-acylpyrrothine (holomycin type) and thiomarinol [START_REF] Qin | Dithiolopyrrolone natural products: isolation, synthesis and biosynthesis[END_REF]. Holomycin appeared to be active against rifamycin-resistant bacteria as well as against methicillin-resistant Staphylococcus aureus N315 [START_REF] Qin | Dithiolopyrrolone natural products: isolation, synthesis and biosynthesis[END_REF] and thiolutin potently inhibits developmental of angiogenesis in zebrafish and vascular outgrowth from tissue explants in 3D cultures [START_REF] Jia | Thiolutin inhibits endothelial cell adhesion by perturbing Hsp27 interactions with components of the actin and intermediate filament cytoskeleton[END_REF].

Results and discussion

Effect of cinnamic acid addition on kinetic of growth, antibiotics production and antimicrobial activity in S. algeriensis During the time course of fermentation in SS medium supplemented with cinnamic acid or not (control), antibiotics production, dry cell weight (DCW) and pH parameters were monitored (Fig. 2) along with the analysis of produced antibiotics (Fig. 3).

The overall antimicrobial activity expressed by the actinobacterium strain towards Bacillus subtilis ATCC 6633 and Umbelopsis ramanniana NRRL1829 started at the 7th day of fermentation (except against B. subtilis in presence of cinnamic acid which started at the 6th day) and reached a maximum between the 8th to the 10th In the context of screening novel dithiolopyrrolonesproducing micro-organisms, Saccharothrix algeriensis NRRL B-24137, a rare actinobacterium isolated from the soil of a palm grove in Southern Algeria (Lamari et al. 2002a) and published as a novel species by [START_REF] Zitouni | Saccharothrix algeriensis sp. nov., isolated from a Saharan soil[END_REF], was shown to commonly produce in complex ISP2 broth (glucose-yeast extract-malt extract) [START_REF] Shirling | Methods for characterization of Streptomyces species[END_REF] at least five dithiolopyrrolone derivatives characterized by their different N-acyl groups, namely acetyl-pyrrothine (thiolutin), senecioyl-pyrrothine, tigloyl-pyrrothine, isobutyrylpyrrothine and butanoylpyrrothine (Fig. 1) (Lamari et al. 2002a,b). Furthermore, the addition of amino acids and organic acids as precursors to the basal semi-synthetic (SS) medium containing glucose, yeast extract and several mineral sources permitted to modify the production levels of this known dithiolopyrrolones (Bouras et al. 2006a(Bouras et al. ,b, 2007)). The so called precursor directed biosynthesis (PDB) method also permitted the production of several uncommon new analogues, among which seven of them were fully characterized by mass and RMN (Fig. 1) [START_REF] Bouras | Precursor-directed biosynthesis of new dithiolopyrrolone analogs by Saccharothrix algeriensis NRRL B-24137[END_REF][START_REF] Merrouche | Dithiolopyrrolone antibiotic formation induced by adding valeric acid to the culture broth of Saccharothrix algeriensis[END_REF][START_REF] Merrouche | New dithiolopyrrolone antibiotics induced by adding sorbic acid to the culture medium of Saccharothrix algeriensis NRRL B-24137[END_REF]. In fact, addition of valeric acid in the culture medium induced the production of three new dithiolopyrrolone derivatives: formylpyrrothine, valeryl-pyrrothine and iso-valeryl-pyrrothine [START_REF] Merrouche | Dithiolopyrrolone antibiotic formation induced by adding valeric acid to the culture broth of Saccharothrix algeriensis[END_REF]. Likewise, addition of sorbic acid allowed formation of four new dithiolopyrrolone derivatives: crotonyl-pyrrothine, sorbyl-pyrrothine, 2-hexonyl-pyrrothine and 2-methyl-3-pentenyl-pyrrothine [START_REF] Merrouche | New dithiolopyrrolone antibiotics induced by adding sorbic acid to the culture medium of Saccharothrix algeriensis NRRL B-24137[END_REF].

O N S S CH 3 N H R O R: CH 3 Acetyl-pyrrothine (thiolutin) R: CH(CH 3 ) 2 Iso-butyryl-pyrrothine R: (CH 2 ) 2 -CH 3 Butanoyl-pyrrothine R: CH=C(CH 3 ) 2 Senecioyl-pyrrothine R: C(CH 3 )=CH(CH 3 ) Tigloyl-pyrrothine R: CH 2 CH 2 CH 2 CH 3 Valeryl-pyrrothine* R : CH(CH3)(CH2CH3) Isovaleryl-pyrrothine* R: H Formyl-pyrrothine* R: CH=CH(CH 3 ) Crotonyl-pyrrothine** R: CH=CH-CH=CH(CH 3 ) Sorbyl-pyrrothine** R: CH=CH-CH 2 CH 2 CH 3 2-Hexonyl-pyrrothine** R: CH=C(CH 3 )(CH 2 CH 3 ) 2-Methyl-3-pentenyl-pyrrothine**
Thus, depending on precursors added, which determine the activated organic acid (acyl-CoA) type incorporated into the pyrrothine nucleus, S. algeriensis has the ability to produce several dithiolopyrrolones derivatives. The transfert of the acyl group from acyl-CoA to pyrrothine core during dithiolopyrrolone biosynthesis was determined as linked to enzymatic activity of pyrrothine N-acyltransferase [START_REF] Chorin | Expression of pyrrothine N-acyltransferase activities in Saccharothrix algeriensis NRRL B-24137: new insights into dithiolopyrrolone antibiotic biosynthetic pathway[END_REF][START_REF] Saker | Enzymatic synthesis of dithiolopyrrolone antibiotics using cell-free extract of References[END_REF].

Since biological activities of dithiolopyrrolones are related to their variable acyl groups, the obtained structurally novel analogues could lead to discover new biologically active natural products that remain to be therapeutically exploited [START_REF] Oliva | Antimicrobial properties and mode of action of the pyrrothine holomycin[END_REF][START_REF] Li | Substituted 6-amino-4H-[1,2]dithiolo[,3-b]pyrrol-5-ones: synthesis, structureactivity relationships, and cytotoxic activity on selected human cancer cell lines[END_REF][START_REF] Li | Dithiolopyrrones: biosynthesis, synthesis and activity of unique class of disulfide-containing antibiotics[END_REF].

In this work, through spectroscopic and spectrometric analyses, biosynthesis of benzoyl-pyrrothine antibiotic (PR5 compound) was evidenced after addition of cinnamic acid in the culture medium of S. algeriensis. After subsequent production, purification and chemical characterization, the benzoyl-pyrrothine minimum inhibitory concentrations (MICs) were evaluated towards several human and plant pathogenic micro-organisms. day (Fig. 2a). The production of compound PR5 also started at the 7th day and reached a maximum after 8 to 10 days of fermentation, with a production of 0Á93 mg 1 À1 observed during the decline phase (Fig. 2b). This supplementation also triggered modification in biomass kinetic in comparison to control (Fig. 2c). The pH increased rapidly to an alkaline state after 24 h of culture (Fig. 2d).

The HPLC profile shown in Fig. 3a indicated that S. algeriensis NRRL B-24137 produces five known dithiolopyrrolones (thiolutin, iso-butyryl-pyrrothine, butanoylpyrrothine, tigloyl-pyrrothine and senecioyl-pyrrothine) in the basal SS medium (control without addition of precursors) as reported by [START_REF] Bouras | Precursor-directed biosynthesis of new dithiolopyrrolone analogs by Saccharothrix algeriensis NRRL B-24137[END_REF]. Importantly, addition of cinnamic acid to the SS medium induced the production of a new compound named PR5 at a retention time of 19Á09 min (Fig. 3b). These findings were in agreement with previous studies, which have shown for all S. algeriensis-synthesized dithiolopyrrolones (common or PDB induced) an optimal production during the idiophase with alkaline pH condition (Lamari et al. 2002a;[START_REF] Bouras | Precursor-directed biosynthesis of new dithiolopyrrolone analogs by Saccharothrix algeriensis NRRL B-24137[END_REF][START_REF] Merrouche | New dithiolopyrrolone antibiotics induced by adding sorbic acid to the culture medium of Saccharothrix algeriensis NRRL B-24137[END_REF].

Globally, S. algeriensis exhibited better antimicrobial activity after addition of cinnamic acid then the control (without cinnamic acid) with a greater anti-U. ramanniana activity (Fig. 2a). This was probably due to the effect of cumulative production of PR5 with the other known dithiolopyrrolones.

Isolation and purification of induced PR5 compound

The cinnamic acid-supplemented SS culture broth of 10 days (12 l) was extracted by dichloromethane and the yellow organic phase was concentrated to dryness. The analysis by semi-preparative HPLC showed the presence of the compound PR5, in addition to the other four dithiolopyrrolones (iso-butyryl-pyrrothine, butanoyl-pyrrothine, senecioyl-pyrrothine and tigloyl-pyrrothine). The compound PR5, which was purified after two successive re-injections in the HPLC system, appeared yellow and exhibited significant antimicrobial activity against U. ramanniana and B. subtilis. This induced compound was subject to spectroscopic and spectrometric analyses to elucidate its structure.

Elucidation of the structure of induced compound PR5

The UV-visible spectrum of the induced compound PR5 showed three absorption maxima at 207, 308 and 398 nm. The molecular weight of PR5 is M = 290 (Fig. S1).

The 1 H and 13 C NMR chemical shifts of the compound were as follow: HMBC experiment (see Fig. 4 for numbering of hydrogen and carbon atoms).

1 H NMR (CD 2 Cl 2 , 500 MHz) d 8Á20 (1H, br s, N7-H), d 7Á92 (2H, m, H10), d 7Á54 (2H, m, H11), d 7Á63 (1H, tt, J = 7Á4, J = 1Á3, H12), d 6Á75 (1H, s, H3), d 3Á40 (3H, s, NCH 3 ); 13 C NMR (CD 2 Cl 2 , 125 MHz) d 166Á7 (C, C5), d 164Á6 (C, C8), d 137Á1 (C, C3a), d 132Á8 (C, C9), d 132Á4 (C, C6a), d 132Á4 (CH, C12), d 128Á8 (CH, C11), d 127Á2 (CH,
CH), 128Á8 (CH) and 127Á2 (CH)) that was confirmed with the 2D 1 H-1 H and 1 H-13 C experiments. The dithiolopyrrolone PR5 was identified as a benzoyl-pyrrothine (Fig. 4). The details of the NMR data of the PR5 compound are found in the supporting information (Figs S2 -S6).

Through partial mass spectrum (MS) analysis, [START_REF] Bouras | Precursor-directed biosynthesis of new dithiolopyrrolone analogs by Saccharothrix algeriensis NRRL B-24137[END_REF] have already hypothesized a possible production of benzoyl-pyrrothine by using benzoic acid and cinnamic acid in the culture medium of S. algeriensis NRRL B-24137 but this putatively deduction was never confirmed. These authors also found that the production of this compound was significantly enhanced by addition of cinnamic acid in comparison to benzoic acid.

Most of the isolated dithiolopyrrolones are carboxylpyrrothine analogues of the added carboxylic acids but additionally, some unexpected dithiolopyrrolones were obtained as a result of biotransformation and the operation of new biosynthesis pathways [START_REF] Merrouche | Dithiolopyrrolone antibiotic formation induced by adding valeric acid to the culture broth of Saccharothrix algeriensis[END_REF][START_REF] Merrouche | New dithiolopyrrolone antibiotics induced by adding sorbic acid to the culture medium of Saccharothrix algeriensis NRRL B-24137[END_REF]. In our study, the addition of cinnamic acid induced production of benzoyl-pyrrothine. As a whole, these findings suggested a transformation of cinnamic acid to benzoic acid that leaded to benzoyl-pyrrothine production. This result agree with those of [START_REF] Brunati | Biotransformation of cinnamic acid and ferrulic acid with actinomycetes[END_REF], who reported the same observation about biotransformation of cinnamic acid to benzoic acid by some strain of actinomycetes. Conversion of cinnamic acid to benzoyl-CoA has been reported for the first time in Streptomyces maritimus [START_REF] Noda | Benzoic acid fermentation from starch and cellulose via a plant-like beta-oxidation pathway in Streptomyces maritimus[END_REF]; this may explain the stimulation of benzoyl-pyrrothine production in S. algeriensis when SS medium was supplemented by cinnamic acid. Furthermore, other works have suggested an enzymatic activity catalysing the incorporation of cyclic acyl group to the pyrrothine core responsible for a putative formation of benzoyl-pyrrothine in S. algeriensis [START_REF] Chorin | Expression of pyrrothine N-acyltransferase activities in Saccharothrix algeriensis NRRL B-24137: new insights into dithiolopyrrolone antibiotic biosynthetic pathway[END_REF][START_REF] Saker | Enzymatic synthesis of dithiolopyrrolone antibiotics using cell-free extract of References[END_REF]). However, these results were never confirmed since no study with RMN evidences has resulted in the final structure of the compound.

Minimum inhibitory concentrations

The MICs values of the pure antibiotic compound PR5 are shown in Table 1. The antibiotic PR5 exhibited moderate activity against fungi, yeasts and Gram-positive bacteria tested (except Staphylococcus aureus, MIC > 100 lg ml À1 ) with MICs ranging from 20 to 40 lg ml À1 . Listeria monocytogenes was the most sensitive (MIC = 4 lg ml À1 ). However, the compound PR5 showed no activity against Gramnegative bacteria (MIC > 100 lg ml À1 ). Similar antimicrobial spectrum has been observed with other S. algeriensis-produced dithiolopyrrolones derivatives (Lamari et al. 2002a;[START_REF] Merrouche | Dithiolopyrrolone antibiotic formation induced by adding valeric acid to the culture broth of Saccharothrix algeriensis[END_REF][START_REF] Merrouche | New dithiolopyrrolone antibiotics induced by adding sorbic acid to the culture medium of Saccharothrix algeriensis NRRL B-24137[END_REF].

In conclusion, from the results presented in this paper, effective S. algeriensis-induced biosynthesis of benzoylpyrrothine dithiolopyrrolone, that displayed antibacterial activities, was evidenced by adding cinnamic acid in the culture medium as precursor.

Materials and methods

Producing strain

The actinobacterium S. algeriensis NRRL B-24137 used throughout this study was grown and maintained at 4°C on slants of ISP (International Streptomyces Project) medium 2 composed of (per litre of distilled water): 4 g glucose, 10 g malt extract, 4 g yeast extract, 18 g agar and pH 7.

Culture condition

Fermentation was carried out in SS medium for antibiotic production by strain S. algeriensis NRRL B-24137. This medium consisted of (per litre of distilled water): 10 g glucose (Fisher Labosi, Elancourt, France), 2 g (NH 4 ) 2 SO 4 (Prolabo, Paris, France), 2 g NaCl (Fisher Labosi), 0Á5 g KH 2 PO 4 (Acros, Geel, Belgium), 1 g K 2 HPO 4 (Acros), 0Á2 g MgSO 4 .7H 2 O (Acros), 5 g CaCO 3 (Prolabo) and 2 g yeast extract (Difco, Detroit, MI). The 500-ml Erlenmeyer flasks containing 100 ml of medium were inoculated with 3 ml of a preculture broth of strain S. algeriensis prepared with the same medium and incubated at 30°C for 2 days. The initial pH of the medium was adjusted to 7 using 2 mol l À1 NaOH prior to autoclaving. The cinnamic acid (Fluka, Buchs, Switzerland), at a concentration of 5 9 10 À3 mol, was supplied to the basal SS medium prior inoculation. The cultures were incubated on rotary shaker (240 rev min À1 ) at 30°C for 10 days.

Assessment of pH, DCW, antibiotics production and antimicrobial activity

During the 10-days fermentation time course, changes in pH, DCWs of mycelium, and antibiotic production were examined daily. The pH value of fermentation broth was measured with a pH meter (Consort C 832; Consort, New York, NY). DCWs were determined as described by Bouras et al. (2006a) and expressed as gram per litre. The analysis of antibiotics induced by addition of cinnamic acid (at 5 9 10 À3 mol) in the SS medium was carried out by a Waters HPLC system equipped with a C18 reverse phase column (Uptisphere UP5ODB, 150 9 4Á6 mm; BioTek Instruments, Milan, Italy). The samples were analysed as described by Lamari et al. (2002b) and Bouras et al. (2006a). Briefly, the formation of new dithiolopyrrolone analog was monitored by comparison of the peak retention times and UV spectra with those of known dithiolopyrrolone standards since appearing dithiolopyrrolone products could be easily detected by HPLC analysis due to the intense absorption at 390 nm. Quantification of PR5 compound was performed using thiolutin standard calibration curve. The molar extinction coefficient (ɛ) of thiolutin is nearly the same for all others dithiolopyrrolones (ɛ 390 = 8317-9333 l mol À1 cm À1 ) as described by Lamari et al. (2002b).

Concomitantly, the antimicrobial activity in the culture broth was monitored daily during the 10-days fermentation time by the conventional agar diffusion assay (well technique) using B. subtilis ATCC 6633 and U. ramanniana NRRL1829. Each 10-mm-diameter well was filled with 0Á2 ml of supernatant. All tests were repeated two times from two separate cultures.

Extraction and purification of new induced antibiotic

Repeated fermentations (10 days) were carried out to obtain a total of 12 l of culture broth then purified according the procedure described earlier [START_REF] Merrouche | New dithiolopyrrolone antibiotics induced by adding sorbic acid to the culture medium of Saccharothrix algeriensis NRRL B-24137[END_REF].

Briefly, the culture broth was centrifuged to remove the biomass and extracted with dichloromethane (v/v) on the tenth day of fermentation (determined through the kinetic assay as the day of optimal production of new compound). The organic extract was concentrated to dryness. The crude extract was dissolved in methanol and subjected to semi-preparative HPLC purification on a Waters system using a C18 column (UP5ODB, 250 9 7Á8 mm; Waters, Milford, MA). A linear gradient of methanol-water (50-100% for 30 min) was used as the mobile phase. The elution rate was 1Á5 ml min À1 and the detection was carried out at 390 nm.

Spectroscopy and spectrometry of new induced antibiotic

These analyses were made with the pure antimicrobial compound PR5. The UV spectrum was determined with a Shimadzu UV1605 spectrophotometer (Shimadzu, Kyoto, Japan). The molecular weight of the compound was obtained by electron impact MS recorded at 70 eV with a Nermag R-10-10C spectrometer. NMR sample was prepared by dissolving the pure molecule PR5 in 600 ll of CD 2 Cl 2 . 1D and 2D 1 H and 13 C experiments were recorded on a Bruker Avance 500 spectrometer equipped with a 5 mm triple resonance inverse Z-gradient probe (TBI 1 H, 31 P, BB). All chemical shifts for 1 H and 13 C are relative to TMS using 1 H (residual) or 13 C chemical shifts of the solvent as a secondary standard. The temperature was set at 298 K. All the 1 H and 13 C signals were assigned on the basis of chemical shifts, spin-spin coupling constants, splitting patterns and signal intensities, and by using 1 H-1 H COSY45, 1 H-13 C HSQC and 1 H-13 C HMBC experiments.

Figure 1

 1 Figure 1 Structure of characterized dithiolopyrrolone antibiotics produced by Saccharothrix algeriensis NRRL B-24137. *Dithiolopyrrolones induced by adding valeric acid to semi-synthetic (SS) medium. **Dithiolopyrrolones induced by adding sorbic acid to SS medium. The other antibiotics are produced in both ISP2 and SS media with or without addition of valeric or sorbic acids.

Figure 2

 2 Figure 2 Effect of cinnamic acid addition to the semi-synthetic medium on evolution of: (a) antimicrobial activity; (b) production of a new induced dithiolopyrrolone (PR5); (c) biomass and (d) pH. ( ) Umbelopsis ramanniana NRRL1829; ( ) Bacillus subtilis ATCC 6633; ( ) SSM without adding cinnamic acid (control) and ( ) SSM with cinnamic acid at 5 9 10 À3 mol.

Figure 3

 3 Figure 3 Effect of cinnamic acid addition to the semi-synthetic medium on dithiolopyrrolones production. (a) Under standard conditions for dithiolopyrrolone production (control). (b) Addition of cinnamic acid to the fermentation broth. (c) Purification of the new compound PR5. HPLC analysis at 390 nm was done on crude extract from a 8 days-old Saccharothrix algeriensis culture. Formation of dithiolopyrrolone analogs was monitored by comparison of the peak retention times and UV (390 nm) spectra with those of known dithiolopyrrolone standards. The retention times were as follows: thiolutin, 12Á50 min; iso-butyryl-pyrrothine, 16Á80 min; butanoyl-pyrrothine, 17Á80 min; tigloyl-pyrrothine, 18Á50 min; senecioyl-pyrrothine, 18Á80 min; PR5, 19Á09 min.

Figure 4

 4 Figure 4 Structure of dithiolopyrrolone PR5 induced by adding cinnamic acid.

Table 1

 1 Minimum inhibitory concentrations (MICs) of dithiolopyrrolone antibiotic PR5 produced by Saccharothrix algeriensis

	Target micro-organisms	MIC (lg ml À1 )
	Bacillus subtilis (ATCC 6633)	40
	Bacillus coagulans (CIP 6625)	20
	Listeria monocytogenes (CIP 82110)	4
	Micrococcus luteus (ATCC 9314)	30
	Staphylococcus aureus (CIP 7625)	>100
	Agrobacterium tumefaciens (no. 2410 LB)	>100
	Escherichia coli (ATCC 10536)	>100
	Klebsiella pneumoniae (CIP 82Á91)	>100
	Salmonella enterica (CIP 81Á3)	>100
	Pseudomonas aeruginosa (CIPA22)	>100
	Aspergillus carbonarius (M333)	40
	Fusarium oxysporum f. sp. lini (Foln 3)	40
	Fusarium moniliforme (Fm1)	40
	Fusarium equiseti (Fe1)	20
	Fusarium culmorum (Fc1)	30
	Fusarium graminearum (Fg1)	40
	Umbelopsis ramanniana (NRRL 1829)	20
	Penicillium expansum (Pe1)	20
	Candida albicans (IPA 200)	30
	Saccharomyces cerevisiae (ATCC 4226)

MICs of new induced antibiotic

The MICs of the purified dithiolopyrrolone antibiotic were estimated by the conventional agar dilution method [START_REF] Oki | Pradimicins A, B and C: new antifungal antibiotic. II. In vitro and in vivo biological activities[END_REF]) towards a selection of 20 target micro-organisms. These micro-organisms were inoculated onto nutrient agar medium containing different concentrations of active compounds (1, 2, 3, 5, 8, 10, 15, 20, 25, 30, 40, 50, 60, 80 and100 lg ml À1 ). The antimicrobial activity was observed after 24-48 h incubation at 37°C for bacteria and 48-72 h incubation at 28°C for fungi and yeasts. Medium without active compound and inoculated with target micro-organisms was used as control.

Conflict of Interest

The authors declare no conflict of interest.

Supporting Information

Additional supporting information may be found online in the Supporting Information section at the end of the article:

Figure S1 Electron impact mass spectrum of PR5 compound.

Figure S2 1 H NMR of PR5 compound. Figure S3 13 C NMR of PR5 compound.

Figure S4 Result of 1 H-1 H COSY45 of PR5 compound.

Figure S5

Result of 1 H-13 C HMBC of PR5 compound.

Figure S6 Result of 1 H-13 C HSQC of PR5 compound.


Axel López

François Chaumette
email: francois.chaumette@inria.fr

Eric Marchand
email: eric.marchand@irisa.fr

Julien Pettré
email: julien.pettre@inria.fr

Character navigation in dynamic environments based on optical flow

Keywords: CCS Concepts, Computing methodologies → Modeling and simulation, Model development and analysis, Model verification and validation, Animation

Steering and navigation are important components of character animation systems to enable them to autonomously move in their environment. In this work, we propose a synthetic vision model that uses visual features to steer agents through dynamic environments. Our agents perceive optical flow resulting from their relative motion with the objects of the environment. The optical flow is then segmented and processed to extract visual features such as the focus of expansion and time-to-collision. Then, we establish the relations between these visual features and the agent motion, and use them to design a set of control functions which allow characters to perform object-dependent tasks, such as following, avoiding and reaching. Control functions are then combined to let characters perform more complex navigation tasks in dynamic environments, such as reaching a goal while avoiding multiple obstacles. Agent's motion is achieved by local minimization of these functions. We demonstrate the efficiency of our approach through a number of scenarios. Our work sets the basis for building a character animation system which imitates human sensorimotor actions. It opens new perspectives to achieve realistic simulation of human characters taking into account perceptual factors, such as the lighting conditions of the environment.

Introduction

Autonomous navigation capacities are essential for virtual characters to find their way in their environment and to move without colliding static and moving obstacles. Producing visually convincing animation requires the characters to move along realistic global navigation trajectories. The problem received a lot of attention and effort has been put to imitate the way humans form locomotion trajectories. The problem is generally addressed as an online motion control problem: given a current state (position, velocity), define the control signal that will lead the character to a desired state (a distant location), under various constraints (e.g., collision avoidance) allowing the system to form feasible human-like trajectories.

Various approaches were explored; all solutions are based on geometrical relations between the characters and the environment. This means that the terms involved in the motion control laws are relative velocities, positions or orientations, etc. This includes previous vision-based approaches [OPOD10,DMCN * 17], which have set the idea of using a virtual retina to acquire all the information required for navigation. Information is projected on the virtual retina according the most basic laws of optics, but the nature of this information is not related to vision. As for other microscopic approaches, distance and velocity terms are used, and those terms are evaluated by directly accessing the simulation database to retrieve objects features.

In contrast with previous work, our main challenge is to control characters navigation based on the visual perception of the environment, and more especially the apparent motion of objects in their visual field. To this end, we restrict our input control variables to the optical flow perceived by characters, i.e., the apparent motion of objects in the 2D image formed on their retina. The information conveyed by the optical flow is sufficient: to detect moving objects or groups of objects moving together; to estimate if objects is moving closer or further; to detect if they are on a collision course. These estimations are performed based on a limited number of visual features that serve as input variables for a set of control and navigation functions for characters. Our approach has several advantages compared to previous one. By using only visual information, and similar visual features than those used by real humans, this work is a new step forward towards simulating humans locomotion control based on vision. Also, our navigation technique could apply to any system equipped with visual perception capabilities, such as a robot equipped with a camera. This paper introduces several contributions. The first one is to establish formal relations between character motion and a set of visual features (cf. Section 5): how do the visual features change when the character motion is adjusted? Those relations are required to design motion control laws based on these visual features, which is our second contribution. We propose a set of object-related motion control functions allowing characters to move and adjust their locomotion relatively to objects (cf. Section 6): to follow one object, to avoid one object or to reach one object. Our third contribution is a set of higher level navigation controllers, which are built by composing different control functions (cf. Section 7). For example, goal-driven navigation in cluttered environments is achieved by combining a control function for object reaching and a second control function to avoid any visible obstacles. All these technical elements compose a complete navigation simulation framework.

Related Work

Steering methods received a lot of attention because of their crucial role in the animation of virtual characters. They are approached as an automatic control problem: how to control a character motion for reaching a desired state such as position in the environment given the current state of the character and the one of the environment. The simplest approach is to control character accelerations based on geometrical variables directly related to motion, such as distances, angles, relative motion, etc. Reynolds [START_REF] Reynolds | Steering behaviors for autonomous characters[END_REF] pioneered this approach by demonstrating how a character can perform most of navigation tasks in static or dynamic environments by combining elementary steering behaviors.

The case of highly dynamic environments has been more deeply explored by microscopic crowd simulators. Simulation agents move by combining the interactions they have with the environments as well as with the surrounding agents [MT01]. Plethora of solutions explore different control laws to propel agents, they however build on similar principles. Agents, represented with a punctual geometrical model, are moved while maintaining geometrical and kinematics relation with their environment. Agents may maintain distances by repulsing each other [HM95], [START_REF] Bouvier | From crowd simulation to airbag deployment: particle systems, a new paradigm of simulation[END_REF], by moving with "collision-free velocities" [PPD07], [START_REF] Van Den | Reciprocal velocity obstacles for real-time multi-agent navigation[END_REF], [START_REF] Moussaïd | How simple rules determine pedestrian behavior and crowd disasters[END_REF], by applying navigation rules [ST05], by locally optimizing timeto-collision [START_REF] Karamouzas | Universal power law governing pedestrian interactions[END_REF]. A large literature build on these approaches and explore the differences in the simulation results [WJGO * 14]. Nevertheless, all these approaches remain quite far from the sensorimotor loops by which real humans perform navigation tasks, because agents dispose of an accurate estimate of all state variables, and by the nature of the state variables used.

In the seek for higher realism of generated trajectories, more accurate biomechanics human models were explored. Instead of a simple punctual model, simulations were based on models of bipedal locomotion. For example, Bruderlin [BC89] or Boulic [BR04] provided a procedural approach to the generation of human locomotion. Singh [SKRF11] used an inverse pendulum to generate footstep sequences for crowd agents. Locomotion trajectories can also derive from a concatenation of examples of motion captured locomotion cycles, opening a large piece of literature about motion graphs [START_REF] Kovar | Motion graphs[END_REF] [LCR * 02], how to construct global trajectories on the environment [SH] or how to deal with dynamic environments [LK]. Reuse of recorded interactions is more specific however

[LCL07], [KGML12], [CC14].
Also seeking for more realism, instead of considering the mechanical aspect of human motion, one idea was to consider more accurately the perceptual system, which is the input of the human control of locomotion. Several techniques appeared in the literature to provide solution to perform navigation in an environment [RTT90], or in a crowd [OPOD10] [DMCN * 17]. Tu and Terzopoulos [TT, TR95] handle the navigation of other species like fishes. These vision-based approaches only partly reproduce the role of the human visual perception. As described by Patla [START_REF] Patla | Understanding the roles of vision in the control of human locomotion[END_REF], vision provides the required information about near and far environment that is required to regulate locomotion both at local and global levels. In this sense, previous works reproduce correctly the role of vision: information required to perform navigation (e.g., time, distances or angle derivatives values) are projected on a sort of virtual retina, which is the only input to control agents' motion. The main advantage of vision-based approaches is to implicitly consider some effect of perception on motion, such as the visibility of obstacles and goals or the relative importance of obstacles with respect to the surface they visually cover. However, none of these approaches attempt to reproduce the most basic role of the human perceptual system which is to process the visual input (images perceived by the human eyes) to extract this information.

The robotics community has explored the use of visual features in order to develop autonomous robots capable of navigating in various environments. Braillon et al [BPCL06] proposed an obstacle detection algorithm based on discrepancies of the theoretical optical flow map (due to the robot's own motion) and the actual perceived optical flow. Other approaches attempted to use optical flow itself in the control laws such as Souhila and Karim [START_REF] Souhila | Optical flow based robot obstacle avoidance[END_REF]. They showed how the focus of expansion and time-to-collision can be extracted from optical flow maps and used a flow balance strategy to navigate in an environment. Aerial robots have also used optical flow such as the model proposed by Zingg et al. [ZSWS10] where depth was estimated from flow maps. Our work differs from these in that we do not balance the optical flow and instead use the optical flow features and its properties in our control law to detect and avoid obstacles.

In this paper, our objective is to steer agents based on the most basic visual cues they can acquire from their surroundings. As a main difference with previous approaches, we fully base our agent control on the position of objects in the perceived image, as well as in the dense optical flow generated by the relative motion between the agent and the environment, whereas previous methods provided a higher-level information to agents not requiring image processing steps. The goal of such an approach, at long term, is to implicitly consider the effect of perception on the character navigation. Nowadays, existing approaches are not able to consider the effect of lighting condition or salience of obstacles because there is no effect of luminosity on the virtual perception. In this paper, our contributions are a clear step in this direction, by showing which visual features can directly be extracted by the flow of images perceived by the agents, and by showing how they can be used to steer them in static and dynamic environments.

Our approach introduces the use of optical flow in highly dynamic environments. There are a number of approaches for optical flow computation. Black [BA91] estimated optical flow by imposing constraints to the image motion and solving the problem using a stochastic approach. There are many benchmarks [BSL * 11] to test modern optical flow algorithms although it is still an open field of research. Our approach has a similar objective than active vision in robotics, the goal of which is to control a robot motion from vi-sion sensors (camera). There are many types of problems tackled through active vision [START_REF] Li | Active vision in robotic systems: A survey of recent developments[END_REF], including motion control [CH06]. However, the case of mobile robotics in highly dynamic environments has not attracted a lot of attention. In this sense, our work also contributes to the robotics field, as our steering methods are directly transferable to a robot equipped with a camera, assuming that an accurate estimate of the optical flow is available.

Overview

This section provides a global description of our framework to steer agents (characters) in dynamic environments.

Agent Model

In this section, we provide a brief description of the agent.

• Visual Sensors: Agents are equipped with a virtual camera at the front of their head (simulating eyes). This camera is capable of recording the optical flow and the depth of the scene perceived at each update. The camera is always aligned with the direction of motion of the agent. The optical flow and depth images are the only information that are provided to our algorithm regarding the perception of the environment. • Control Variables: We consider an agent with two degrees of freedom: forward acceleration ac and turning rate ωcy. Acceleration allows the agent to move faster or slower and turning rate is the angular velocity of the agent around its vertical axis, which allows the agent to change its direction of motion. Lateral motion is not considered in this model.

Algorithm Overview

Figure 1 shows the main components of the simulation loop by which each agents' motion is controlled at each time step:

• Agent Perception: in a first step, agents perceive the environment through a virtual camera set at the position of their head. From this point of view, we are interested in the apparent motion perceived on each pixel caused by the motion of obstacles relatively to the agent, i.e., the dense optical flow perceived by agents. We compute the dense optical flow for each agent synthetically, we remove its rotational component (i.e., we compensate for agent's head rotations). The computation of optical flow is detailed in Section 4. Additionally, agents record the depth in the scene corresponding to every pixel in the image. • Visual Features: the next step is to extract some features from the perceived optical flow. First, the image is segmented using the optical flow image. This allows isolating obstacles with different apparent motion (most often corresponding to different close moving obstacles). As result of the segmentation a set of objects O i , i ∈ [0.

.n] (static or moving obstacles, other agents) are detected and their corresponding pixels x j , j ∈ [0.

.N] are extracted from the background. Then, per object O i features are computed such as the position of the center g xi , the Focus of Expansion (FOE) f i , time to collision τ i and depth Z i . The relevance and computation of these features are detailed in Section 5. • Control Functions: the third step is to evaluate a set of control functions L k based on visual features and the agent's speed. Each control function relates agent's motion with a visual feature or its velocity. It is a basic element to build agents' visual-motor loops. For example, we define a control function Lt that controls the projection of geometrical points in the image which is used to perform goal reaching, this is detailed in Section 6. Other control functions may control the position of an object's focus of expansion f i by changing their velocity to adjust the object's relative motion. The set of control functions and the set of visual features agents are able to control is presented in Section 6. • Navigation Functions: the final step of the simulation loop updates agent velocity so as to locally minimize a navigation function. A navigation function allows an agent to achieve a highlevel navigation task such as reaching a goal while avoiding all the obstacles on his way, the value of which reaches zero when the task is achieved at best. Each navigation function is a combination of control functions, i.e., a high level task is formulated as a set of visual features to control. This is achieved by formulating navigation functions as a combination of control behaviors: L = ∑ α k L k , where α k weights the relative importance of each control function. This is explained in Section 7.

Mathematical Notation

In Table 1 the mathematical notations used through the paper are summarized. Through the paper all magnitudes are expressed in a coordinate frame with origin in the agent's camera, the z axis in the direction of the optical axis, y points towards the ground and x towards the right of the agent.

The coordinates of 3D and 2D points are noted as X j = (X j ,Y j , Z j ) and x j = (x j , y j ). Optical flow is noted as u j = (u j , v j ). All image points are expressed in normalized coordinates. Subindex c correspond to magnitudes specific to the agent.

Symbol Description

x j Position of pixel j in the image (2D point) X j

Position of point j in the 3D world relative to the agent (3D point, m) u j

Optical flow of pixel j (2D vector)

f i Focus of

Agent Perception

In this section, we show how optical flow is computed. Optical flow is defined as the apparent motion of objects in the visual field. For the modeling, we approximate it with the projected motion in the image plane. A dynamic observer with angular velocity ωcy perceives a point X j of an object i, with relative translational velocity v i . We neglect optical flow components due to the object's own rotation under the assumption that these rotations are small compared the other contributions. The observer will perceive optical flow [SBC96] according to the following equation,

   u j = v ix -x j v iz /Z j -ωcy x 2 j + 1 v j = v iy -y j v iz /Z j -ωcyx j y j .
(1) with (x j , y j ) = (X j /Z j ,Y j /Z j ) being the projection of X j in the image plane.

Equation (1) takes into account the angular velocity of the observer. We need to remove this contribution from the perceived flow. The reason is twofold: first, humans are able to compensate rotational component through the Vestibulo-ocular reflex [START_REF] Angelaki | Eyes on target: What neurons must do for the vestibuloocular reflex during linear motion[END_REF], and second, it allows us to define the FOE and other features de-rived from it. Then, Equation (1) is reduced to the following expression,

u j = v ix -x j v iz /Z j , v j = v iy -y j v iz /Z j .
(2)

Knowing the angular velocity of the agent, the optical flow map can be compensated to remove the rotational contribution. Figure 2 illustrates the perception of an agent and the colors of optical flow maps. In this section, we expose the relevant features encoded in an optical flow image and show their dependency with the control variables. The relation between the translational velocity and the control scheme is given by viz = -ac and vix = -vcωcy. All features presented in this section are object specific. As explained in Section 3, objects are extracted from the background in the flow image. The first step is to remove the flow generated by the ground. We assume a flat ground and knowing the agent's height h, the depth of the points belonging to the ground are given by Z(x j , y j ) = h/y j and the flow as (u j , v j ) = (x j y j , y 2 j )vc/h. Pixels matching this depth or flow values are removed. Then, we use the OpenCV library to detect discontinuities in the flow map through the Graph Segmentation algorithm [FH04]. The segmentation results in various objects, which are treated as rigid bodies. Figure 3 illustrates the various features contained in the optical flow image. Finally note that, as the motion of our agents is restricted to the horizontal plane, we focus on the x component of the features. Following figures displays visual features at the center of the vertical axis for this reason.

Visual Features

Focus of Expansion

The FOE is a per-object feature. It is defined as a point with null optical flow despite having a non-zero 3D velocity. It corresponds to a point that moves towards or away from the observer. Therefore, controlling the FOE allows us to prevent collisions. From (2) and enforcing u j = 0 and v i = 0 the FOE is expressed as,

f xi = v ix /v iz , f yi = v iy /v iz , (3)
which is the projection of the relative velocity of the object in the image.

Optical flow vectors exhibit a radial configuration around this point, which allows the FOE to be computed as the intersection of many lines. These lines are defined as supporting point x j and direction vector u j . Figure 3 illustrates the flow vectors configuration.

Equation (3) can be derived to obtain the time variation of the FOE with respect to the control variables. This results in the following expression,

ḟxi = vc v iz -f 2 xi -1 ωcy - f xi v iz ac. (4)

Time-to-collision

The time-to-collision is defined as the remaining time until an object will cross the plane perpendicular to the direction of motion of the agent. It is expressed as

τ i = -Zi viz .
From the FOE and the optical flow it is possible to compute the time-to-collision [START_REF] Tistarelli | Dynamic stereo in visual navigation[END_REF] without any 3D geometrical information nor 3D velocity. For each pixel of the object we define its distance to the FOE as ∆ j ≡ x j -f i and we obtain

τ i = ∑ j∈i ∆ j u j . (5)
It should be noted that although ∆ j and u j are pixel dependent values, τ i is not. When noise is present, in order to obtain a robust result, τ i is computed as the average for all pixels of the object as expressed in (5). Finally, τ i allows us to express the relative velocity of an agent in terms of the known information,

v i = -( f xi , f yi , 1)τ i /Z i .

Dynamics of Optical Flow

Finally, optical flow is used as a visual feature as well. The temporal derivative of (2) allows to obtaining the following expression,

u j = 2 τ i u j - vc Z j ωcy + x j Z j ac. (6)
This will be used to perform velocity alignment and following.

Control Functions

In this section we present a set of control functions L based on the visual features presented in the previous section. These functions are used to perform various tasks that allow an agent to navigate in a virtual environment. Therefore, we can update the control variables in order to minimize the value of the control functions.

Target Reaching

Control of geometrical points is a well-known problem in robotics [CH06]. It allows us to place a point (the goal) in a specific location in the image. In our framework, we want the goal tx to be placed at the center of the image. This will cause the agent to move towards it. We use the following control function,

Lt = 1 2 t 2 x , (7)
The minimum value of this function is for tx = 0 and will prevent the agent from deviating too much from the goal. The goal is a known point in space and in the image. The goal corresponds to a 3D point in space, therefore it follows (1) and its variation with the control variables is,

ṫx = tx/τt -(t 2 x + 1)ωcy. ( 8
)
In the cases where the goal is a region and not a point, tx is considered as the closest point of the region to the agent.

Collision Avoidance

As explained in Section 5.1 the FOE is the key element in preventing collisions. The geometrical point of an object that coincides with the FOE moves towards the agent resulting in a future collision. Therefore, the FOE needs to be displaced away from the object to prevent a collision. Additionally we need to take into account the size of the agent to prevent collision not only with the camera but also with the rest of the body. The control function needs to produce high values when the FOE f xi is over the object or close to g xi . To this end, we propose the following cost function,

Lav = n ∑ i I(τ i ) exp - |∆x i | σ i . ( 9
)
where ∆x i = g xif xi , σ i = wi ln(10) , being w i the width of the object plus the width of the agent projected to the image, this is illustrated in Figure 4. I(τ i ) = aτ i + b is a linear function introduced to give a higher value to objects with lower time-to-collision τ i . In our implementation we set a = -2 and b = 10 and the contribution of objects with τ i > 5s is clamped to 0.

Lav takes into account all objects that need to be avoided. The goal of this function is to separate every FOE from its respective object to obtain a collision free trajectory.

From Equations (1) and (4), ∆x i has the following dependency with the control variables,

∆x i = (g xi -f xi )/τ i + f 2 xi -g 2 xi - τ i Z i vc ωcy + τ i Z i f xi ac. (10)

Velocity Alignment

Velocity alignment consists in matching the direction of motion of the agent with a certain object. Velocity alignment is modeled as the minimization of the optical flow, being N the number of pixels of object i.

L min = 1 N 2 ∑ j∈i u j 2 , (11)
This function is intended to model a following behavior in conjunction with (13). The relation of u j with the control variables has been presented in (6).

Speed Control

Some control functions may change the speed of the agent without any limit on their own. To control this behavior a preferred speed v * c is defined, that will play the role of the default speed when no other behavior is active and will limit the range of possible values it may take. This is modeled by,

Lv = 1 2 (vc -v * c ) 2 , (12)
and from the definition of vc, vc = ac.

Alternatively, we may want to match the relative speed v iz = Zi τi between the camera and an object. This is for example useful to follow an object. To this end, we will use,

Lτ = 1 2 v 2 iz , (13)
with viz = -ac.

Navigation Functions

In this section we present how higher-level navigation tasks can be achieved by combining basic control functions. The key idea is to blend these functions to generate a navigation function L, which capture a complex behaviour, such as reaching a target while avoiding collisions with multiple objects, or following a mobile target while avoiding collision with obstacles. The general expression of a navigation function is,

L = ∑ k α k L k , (14)
where L k is a control function presented in Section 6 and α k is a parameter that controls the weight of each control function.

Our control variables are the agent's acceleration ac and angular velocity ωcy around the vertical axis. At every update step, the gradient of the navigation function is evaluated and the control variables are updated by,

ac = -λ ∂L ∂vc , ωcy = -λ ∂L ∂θ , (15)
with λ being the gradient descent step size parameter. We have empirically found that a value λ = 1 performs well.

As an example, thanks to (8) using Lt from (7) results in the control variables taking the following values, ac = 0, ωcy = -(1 + t 2

x )tx.

Results

In this section we propose two navigation functions that follow the scheme presented in Section 7 and present the trajectories generated by our algorithm when agents face different scenarios. In the two following sections, we demonstrate that the few visual features extracted from the perceived optical flow that compose our control functions are sufficient to steer characters in high level navigation tasks such as reaching destinations in dynamic environments, or following moving objects. The extraction of visual features is however performed at a computational costs, that we evaluate in Section 8.3.

Collision-free goal reaching navigation

We first demonstrate our technique in the classic situation of a character reaching a goal while avoiding the obstacles of a given environment. To model this behavior we build a navigation function combining Equations ( 7), ( 12) and ( 9). The navigation function is as follows,

L = αLt + βLv + γLav, (16)
We want to drive the goal to the center of the image to make sure we move towards it and the comfort velocity v * c = 0.15m.s -1 . In the following examples we will use α = 1, β = 0.1, γ = 1 unless otherwise specified. In collision avoidance tasks the system tends to apply a very small variation in acceleration therefore the value of β affects only how fast the speed of the agent reaches the desired speed v * c . Empirically β = 0.1 yields good results. We will later show the effect of the relative weight of α and γ.

The gradient in (15) is computed for (16) using ( 8) and (10), leading the control variables to have the following expression,

ac = -λ β(vc -v * c )+ γ ∑ i I(τ i ) exp - |∆x i | σ i sign(∆x i ) σ i -f xi τ i Z i , ωcy = -λ -αtx(t 2 x + 1)+ γ ∑ i I(τ i ) exp - |∆x i | σ i sign(∆x i ) σ i f 2 xi -g 2 xi - τ i Z i vc , (17)
which will update the simulation closing the control loop in Figure 1. We demonstrate this navigation function in static and dynamic environments.

Static Environments

In a static environment, the apparent motion of objects is only due to the agent's own motion. This causes the FOE to be at the center of the image at all times ∂ fxi ∂θ = 0, ∂ fxi ∂vc = 0 . Figure 5 shows a complex room with objects of various sizes and shapes. Our vision-based algorithm is capable to avoid any object to cross the room. Each agent takes a different route depending on its initial position because of the local optimization. As x g3 is farther away it has a greater τ i than other objects and therefore its contribution to Lav is lower. Therefore, the reaction to it takes place later in the simulation. Figure 6 shows an example of an agent in a city-like environment. Due to using the entire optical flow image the agent is capable of avoiding objects with complex geometry like the fence and of other shapes such as the tree.

Dynamic Environments

Now we let agents face other agents using the same navigation function. Therefore, the FOE of every object will depend on the motion of the corresponding agent.

Figure 7 shows a circle scenario. Six agents are arranged in a circular formation and are tasked to reach the opposite side of the circle. The symmetry of this scenario causes agents to follow the same pattern. Figure 8 shows a scene of multiple agents in a street with cars. Agents can adapt their paths to avoid both types of obstacles (cars and other agents) and are capable of crossing the street without collision.

Figure 9 shows two groups of agents tasked to reach the opposite side of the room. This scenario shows the effect of different values for γ. When it is too low (b) the agents barely adapt to other agents and some collisions occur. As γ becomes greater agents with the same goal form groups and increases the distance between them.

Following

The second navigation function involves following. We build a navigation function that models an agent following an object or another agent. Therefore, our navigation function takes into account velocity alignment and speed matching. The agents need to be able to avoid obstacles as well. Equations ( 11), ( 13) and ( 9) are thus combined resulting in the following expression,

L = αL min + βLτ + γLav, (18)
L min controls the direction of motion of the agent and Lτ controls its speed.

Agents are assigned a leader and they are tasked to follow it. Agents are drawn in blue while leaders are drawn with red color. The parameters used in this section are α = 1, β = 1, γ = 1. In this situation β affects how fast a blue agent adapts to the variation of the speed of a red agent.

Similarly as we did for (17), we derive the expression of the control variables from the navigation function in (18),

ac = -λ -β Z red τ red + γ ∑ i I(τ i ) exp - |∆x i | σ i sign(∆x i ) σ i -f xi τ i Z i , ωcy = -λ -α 2vc NZ red ∑ j∈red u j + γ ∑ i I(τ i ) exp - |∆x i | σ i sign(∆x i ) σ i f 2 xi -g 2 xi - τ i Z i vc , (19)
to update the simulation.

Figure 11 shows an agent following another one. The red agent goes through a set of way-points. Every time the red agent changes its direction to reach the next way-point the blue agent adapts its velocity to align with the one of the red agent. For higher values of α the adaptation is faster and the trajectory of the blue agent becomes similar to the trajectory of the red agent. For lower values of α the adaptation is much slower producing a different trajectory.

Figure 12 shows a situation where obstacles are in the way of the agents while following another agent. Depending on the initial conditions the agents choose different paths to perform following and avoidance.

Performance

In this section, we give indicative numbers about our approach performance. Simulations ran on a 2.17GHz Intel Core i7 processor, 16 GB of RAM, Nvidia Quadro M2000M using Unreal Engine 4 as the graphics engine.

The performance of our algorithm depends on the chosen resolution of the images. The GPU renders the flow image perceived by the agent and then they are downloaded to the CPU. The data transfer consumes a lot of time and thus we believe performance could be greatly improved with a full GPU implementation. We ran most of the simulations using a high-resolution camera 1024x1024. Under these conditions, every agent takes on average 0.48s to update. We can lower the resolution to 300x300 increasing performance to 0.03s per agent. Figure 13 shows the same scenarios shown through the paper with high and low flow resolution. High-resolution flow results in a quite straight trajectory while low resolution flows produces trajectories with higher curvature and noise due to the reduced precision in object position. In the first comparison, an agent even takes a very different path.

Figure 14 shows a comparison of trajectories of the scenario shown in Figure 9 for different resolutions and the computation time per-agent and per frame. For lower resolutions, collisions occur more often due to the reduced spatial precision. In addition, low-resolution images causes the object segmentation to be less accurate.

Discussion

The previous section demonstrates our steering approach in action. It demonstrates that using optical flow features, we are able to steer agents so that they perform navigation tasks, such as goal-directed navigation among static and dynamic obstacles. In this section, we discuss our results as well as the limitations of our approach.

Level of realism and comparison with previous approaches

Our objective is to reconsider the nature of inputs used for trajectory control, with the aim of simulating more accurately the low level processes by which human use vision to navigate. We demonstrate that few visual features are enough to steer characters in goaldirected navigation tasks performed in dynamic environments. Because some crowd simulation algorithms address similar problems, we compare some of them with our approach. Beyond the nature of input variables, the principles set by our control scheme have similarities with previous approaches: as [KSG14, DMCN * 17] we locally optimize a navigation function to control instantaneous velocity and acceleration. Also, our navigation functions have similarities with previous approaches. For example, avoidance is based on the estimation of the risk of future collision. In this sense, we are similar to the general principle of velocity-based approaches [PPD07, vdBLM08] and their many variants. Therefore, the crucial difference is the nature of variables to estimate the risk of collision. Velocity based approaches explicitly compute the future distance of closest approach. We get this estimation through the distance-between the visual center of an object with the focus of expansion of the flow generated by this object. Whilst resulting trajectories may exhibit similar properties (e.g., anticipated collision avoidance), they will not be strictly identical. We believe our system could be used to identify human sensorimotor functions that link vision and locomotion. This comparison however needs large efforts, which would first consist in acquiring visuomotor data to describe real human behaviors.

We now provide a qualitative comparison of our algorithm, and more specifically the collision avoidance function (Eq. 16), with RVO2 [START_REF] Van Den | Reciprocal n-body collision avoidance[END_REF] and the model proposed by Dutra et al [DMCN * 17]. We chose those two approaches because they are good representative of two categories of approaches: velocitybased and vision-based approach. These algorithms share many similarities with ours. All of them evaluate the future risk of collision between the character and surrounding obstacles and adjust the characters motion accordingly. Their difference resides in the way this risk is evaluated, and motion is adjusted. Obviously, the main difference is that our approach relies on the evaluation of visual features whilst previous approaches exploit geometrical relations. The following comparison highlights the difference in the generated trajectories over the example of crossing groups.

Figure 15 shows two groups of agents crossing each other to reach the opposite side of the room with various initial densities. We compare our model with the aforementioned ones. RVO2 works well in low-density scenarios however, the distance between agents of different groups is just the minimum to prevent collisions. In Dutra's model and our model, the minimum distance between agents is not fixed but rather it adapts to the density of the crowd. Dutra's model also favors many variations of speed for avoidance while in our algorithm avoidance favors a change in orientation rather than a change in the speed of an agent due to the nature of the visual feature. Our model favors following groups of agents with the same direction while in other approaches agents may follow very different paths from one another. RVO2 presents congestion issues when the initial agent-to-agent spacing is much smaller than the size of the agents. Dutra's model and ours allows a continuous rearrangement of the formation over time to minimize the congestion issue.

Figure 16 shows a comparison of the angular velocity of the agents. Our model favors small progressive adaptations, Dutra's model favors sudden adaptations with large angular velocity and RVO favors large and small adaptations alike.

Limitations and Future Work

One of the motivations in our work is to consider better the effect of visual perception on motion control. Currently the optical flow map does not consider lighting conditions however, objects that lack contrast with the background or texture, or objects that are not correctly lighted would not generate optical flow, and this lack of information would implicitly impact motion control. We still need to introduce the notion of lack of information in the control loops. When the absence of optical flow is not due to the absence of near moving objects, but the impossibility to perceive them, reaction is different (e.g., humans avoid dark areas or are unable to move normally in the dark). To solve this problem we propose to change the way we compute optical flow. A numerical approach would take into account naturally the lightning conditions in the scene improving the capabilities of our framework. This poses the challenge of obtaining high enough quality flow maps since it is usually computationally expensive. We would like to evaluate the benefit of recent techniques based on deep-learning approaches [IMS * 17] to obtain the optical flow map. We also would like to remove the need of depth information as an input to our algorithm. We believe that some assumptions can be made such as τi Zi vc = 1 2 which assumes that objects are moving at the same velocity as the agent and yet avoidance would still be robust within a certain range of object velocities.

We have demonstrated how relatively simple navigation function perform well in different scenes, made of multiple static and dynamic obstacles. We have demonstrated that our method can combine following and avoidance behaviors for example. There are many other kinds of navigation tasks we would however like to explore, for example multiple target tracking, or object interception (catching), which have also been left unexplored by previous approaches. Our algorithm relies on a cost function optimization. Depending on the scenario, we may face the problem of local minimum. This may cause the agent to collide while trying to avoid multiple objects if there is not enough room for it go through. This can be avoided by considering two objects as a single one if they are too close in the image, or also by playing on parameters value (e.g., to diminish the importance of goal reaching and let the character exploring detours). While the meaning and the tuning of our parameters is straightforward, we need to more deeply explore how our navigation generalizes and how relative weights α and γ could be automatically adapted to the visual context.

Beyond the question of behaviors and parameters, we are also interested in applying our approach to simulate the collective motion of animal species, such as birds or fishes. Our method attempts to simulate some low-level sensorimotor mechanism of human locomotion. To address more complex scenarios, we need to consider the role of other components, such as for example visual attention, and how more generally use head motion to perform visual exploration of the environment (which would address issues due to the limited field of view of agents), or the coupling with basic motion behaviors with higher level ones such as planning.

Conclusions

We presented a new agent steering approach using synthetic vision. The main contribution of this paper is to formulate a set of steering behaviors that are directly expressed with the visual features related to the optical flow generated by the motion of the agent and dynamic obstacles. We built a set of navigation functions on top of these steering behaviors to let agent autonomously perform complex navigation tasks that combine avoidance of obstacles with goal reaching. We have demonstrated that we can reproduce some results obtained by previous approaches, while, in contrast with them, we do not exploit geometrical relations between characters and their environment. This is interesting for several reasons, including the potential to support future research directions as we discussed, such as for example the identification of human perceptionaction loops. Future work also aim at considering a new range visual factors which influence human navigation, such the environment lighting conditions. Also, our approach closes a gap between Computer Graphics and Robotics. As we base on visual features only, a robot equipped with a camera and optical flow computation capabilities could be directly steered by our technique, whereas the use of previous techniques would need to map the environment so as to establish the required geometrical relations.

Figure 1 :

 1 Figure 1: Agent control loop scheme: every frame, each agent follows these steps to move in dynamic environments.

Figure 2 :

 2 Figure 2: Agents are equipped with cameras capable of recording rotationless optical flow at each frame. Color coding of the optical flow map (u j , v j ).

Figure 3 :

 3 Figure 3: Segmentation of the optical flow image from Figure 2. (top) Color image perceived by the agent. (down) Visual features extracted from optical flow. The goal t of the agent corresponds to the pink point. For every object the visual features extracted are the FOE f i (blue points), time-to-collision τ i , object center g i (orange points) and optical flow vectors (blue arrows), which exhibit a radial configuration around the FOE allowing its computation as the intersection of many lines. The pink object is a representation of the goal and does not generate any optical flow.

cFigure 4 :

 4 Figure 4: Control Functions. Each control function has a different purpose. Lav tries to separate the FOE f xi and the center of the object by more than w i . w i is the size of the object plus the size of the camera. Lt tries to place the goal tx to the center of the image.

Figure 5 :

 5 Figure 5: Agent trajectory with static obstacles. (up) Top view. Three agents need to cross the room avoiding obstacles. Various objects of different shapes and sizes are present in this scene. Agents are placed in different starting position and orientation and they choose different paths to walk out the room. (middle) Visual features perceived by one of the agents. (down) Color image perceived corresponding to the visual features.

Figure 6 :Figure 7 :

 67 Figure 6: Agent trajectory in a city-like environment with urban obstacles.

Figure 10

 10 Figure 10 shows how the cost function and goal of an agent varies over time. The cost of avoidance increases and decreases very fast as objects enter and leave the field of view. Once all obstacles are cleared goal reaching becomes dominant. The supplementary video contains additional examples to further illustrate our algorithm. We show examples of agents in various scenarios avoiding static and dynamic obstacles and walking in restricted spaces.

Figure 8 :

 8 Figure 8: Agent trajectory with complex obstacles in a city-like environment.

( a )Figure 9 :

 a9 Figure 9: Two rows of agents navigate towards the opposite side of the room avoiding each other. As γ increases, the distance between agent with different goals increases.

Figure 10 :

 10 Figure 10: Variation of the cost function (left axis) and goal tx (right axis) over time. It corresponds to the front agent of the scenario shown in Figure 5.

Figure 11 :Figure 12 :

 1112 Figure 11: Following a leader. The blue agent must follow the red one, which goes through a predefined set of way-points. We show the resulting trajectory for different values of α.

Figure 13 :

 13 Figure 13: Variation of trajectories depending on optical flow resolution. The left column shows the resulting trajectories of a 300x300 flow map resolution and the right column shows the same scenario with a 1024x1024 resolution.

  (a) (64x64) 0.003s (b) (128x128) 0.006s (c) (256x256) 0.027s (d) (512x512) 0.111s (e) (1024x1024) 0.48s

Figure 14 :

 14 Figure 14: Trajectories of the scenario shown in Figure 9 for various resolutions. Computation time is shown for every resolution.

Figure 15 :

 15 Figure 15: Lane formation. Agents are tasked to reach the opposite side of the room. (top) Agents are initially arranged in a lowdensity configuration, agent spacing is larger than agent size. (bottom) Agents are arranged in a high-density configuration, agent spacing is close to zero.

Figure 16 :

 16 Figure 16: Comparison of histograms of the angular velocity of an agent for different models: ours (left), Dutra (middle) and RVO (right). Only non-zero adaptations are being displayed.

Table 1 :

 1 Description of symbols.

Expansion (FOE) of object i (2D point) g i Position of the center of object i in the image (2D point) t Position of the target (goal) in the image v i Velocity of obstacle i relative to the agent (m/s) vc Speed of the agent (m/s) ac Acceleration of the agent (m/s 2 ) ωcy Angular velocity of the agent (rad/s) τ i Time-to-Collision with object i (s) Z i Average depth of object i with respect to the agent (m)

c 2019 The Author(s) Computer Graphics Forum c 2019 The Eurographics Association and John Wiley & Sons Ltd.