Antoine Vacher

Anissa Amar

Franck Camerel

Yann Molard

Camille Latouche

Thierry Roisnel

Vincent Dorcet

Abdou Boucekkine

Huriye Akdas-Kiliç

Mathieu Achard

Modulation of emission properties of phosphine-sulfonate ligand containing copper complexes playing

Introduction

Since the seminal independent observations of Boudin [1a] on eosin and Lewis [1b] on fluorescein of a second long-lived luminescence in viscous/rigid media, delayed fluorescence has attracted a lot of interests. This temperature dependent phenomenon is not limited to organic molecules and reexamination of this concept by McMillin with well-defined copper complexes demonstrated that the emission processes arise from the two close S 1 and T 1 excited states leading to the so-called Thermally Activated Delayed Fluorescence (TADF), thus allowing the development of organic and inorganic materials to harvest both singlet and triplet excitons. [2,3,1d] Owing to their possible application in OLEDs as sensor and due to the low cost and abundancy of first row transition metal complexes, copper complexes exhibiting TADF and/or phosphorescence have received a lot of interest as promising alternatives to triplet harvesters based on precious metals. [4,[START_REF]HRMS-ESI: (C 18 H 14 O 3 IPSCu)[END_REF] Thus, lots of attention has been paid to a careful design of various cationic and neutral mono-, di-and multi-nuclear cuprous complexes to tune their photophysical properties and to minimize geometry distortion in the excited state. [2][3][4][START_REF]HRMS-ESI: (C 18 H 14 O 3 IPSCu)[END_REF][6][7][8][9][10][11] In contrast cuprate complexes have been far less investigated and usually led to halo bridged coordination polymers [12] . Noteworthy that due to the side presence of Cu(I) in copper perovskite defects, this material exhibit green photoluminescence. [13] In our quest to develop sustainable approaches to obtain efficient and photoresponsive luminescent molecules, [14] in this article, we present the preparation of various original neutral copper(I) and cuprates(I) complexes arising from the treatment of phosphine-benzenesulfonic acids with solvents and metal salts. Photophysical properties of the synthesized complexes are also investigated.

Results and discussions

Complex Cu-2 (Scheme 1) was easily synthesized from our Cu-1 [14a] complex after removal of the coordinated methanol molecules under vacuum followed by the addition of acetonitrile. This simple reaction affords colourless crystals of Cu-2 in 76% isolated yield. Interestingly, whereas X-ray structure determination highlights the formation of a tetracoordinated mononuclear copper(I) complex bearing two acetonitrile ligands along with 2 lattice acetonitrile molecules restricting rotation of one exocyclic P-Ph bond (Figure 1 and Figure S3), NMR analyses in CD 3 CN and cyclic voltammetry demonstrate the presence of a dimer in acetonitrile solution (Figure S1;S2). The nature of the phosphine plays an important role on the formation of the bi-and mono-nuclear species in the solid state. Replacement of the Murray ligand in Cu-1 by the a. Univ Rennes, Institut des Sciences Chimiques de Rennes-UMR 6226, ScanMat-UMS2001, F-35000 Rennes (France). E-mail : abdou.boucekkine@univ-rennes1.fr; huriye.akdas@univ-rennes1.fr; mathieu.achard@univ-rennes1.fr sterically hindered Drent ligand L2-H [15] (Scheme 2) known to shield the metallic centre resulted in the formation of an unstable species in methanol. In contrast to this result, when the reaction was conducted in acetonitrile moderately stable Cu-3 was isolated as a mononuclear complex. Interestingly, when the reaction was carried out with our previously t-Bu based phosphine-sulfonate precursor L4-H, [16] we were able to isolate a dinuclear copper(I) complex where the coordinated oxygen atoms play the role of bridging ligands to form a diamond core four membered metallacycle Cu-5 reminiscent to the observation of a dimer form from Cu-2 in acetonitrile. The crystal structures for all the synthesized complexes confirm the crucial pyramidal trigonal planar geometry on the copper metallic centres (Figure 1). [17,18] The synthesized colourless complexes exhibit photoluminescence in the solid state (Table 1). The spectrum envelopes are broad and featureless for complexes from Cu-1 to Cu-5 at room temperature and consistent with emission from the 3 MLCT state. We observed that the emission bands of complexes containing acetonitrile ligands are broader and occur in the yellow region, whereas the methanol containing complexes emit in the blue-green area (Table 1). Compared to the complexes Cu-1, Cu-2 and Cu-3 featuring aryl phosphine-sulfonate chelates, the alkyl phosphine-sulfonate containing complexes Cu-4 and Cu-5 afforded lower emission quantum yield. Notably, the flat dinuclear Cu-5 species with the shortest Cu-Cu distance (3.34 Å) where π-π stacking interaction occurs between the MeCN ligand and the Ar-SO 3 moiety letting the exocyclic P-C bonds unrestricted led to the weakest emissive complex with a dual emission presumably arising from 3 MLCT and 3 CC excited states or a vibronic fine structure from a single excited state (Table 1). [10c,19] The presence of both solvent lattice and ligand in the corresponding structures suggests reduced vibrational quenching and prevents structural relaxation upon excitation. DFT computations have been performed using the B3PW91 functional [20][21][22] together with the LANL2DZ basis set [START_REF] Dunning | Methods of Electronic Structure Theory SE -1[END_REF] augmented with polarization functions using the gaussian09 program. [START_REF] Frisch | [END_REF] Solvent effects (MeOH) were considered using implicit solvent (PCM) [25] together with explicit molecules in the calculations. The frontier MOs of the complex Cu-1 are depicted in Figure 2. The HOMO and HOMO-1, which are very close in energy (-5.96 vs. -5.88 eV), are rather similar and exhibit a strong 3d orbital metallic character (>52%) as well as HOMO-2 and HOMO-3. On the opposite, the LUMO and LUMO +1, which are also quasidegenerate, are clearly localized on the P-Ph 3 moieties. Considering the UV-vis spectra, compound Cu-1 exhibits an absorption in solution (MeOH) at 260 nm. In Table 2, are given the results of the TD-DFT computations of its electronic spectrum, namely the wavelengths and oscillator strengths as well as the transitions involved in the excitations, using the B3PW91 functional and the CAM-B3LYP one. [25][26] As it can be seen in Table 2 the computed absorption wavelength using the CAM-B3LYP functional compares well with the observed one.

On the contrary the B3PW91 computation overestimates the absorption wavelength This result is not surprising since the involved transitions are HOMO-1 → LUMO and HOMO → LUMO+1 which possess a long distance charge transfer MLCT character which are more accurately described by the range separated functional CAM-B3LYP. These HOMO to LUMO transitions are assigned to be metal to ligand charge-transfer (MLCT) confirming the previous assignment and the crucial role of solvent molecules. (vide supra). Depending on the complex, the presence of uncoordinated solvent molecules in the crystal structure led to mechanosensitive species. While Cu-1, Cu-3 and Cu-4 (Figure S7) are relatively stable in powder form compared to their crystal forms without any changes in their emission properties at room temperature, complex Cu-2 loses after several minutes its emissivity upon grinding with a red shift of its emission (Figure S3, S4). Elemental analysis of room temperature vacuum dried Cu-2 corroborates dimer formation. Additionally, thermal gravimetric analysis of crystals Cu-2 highlights noticeable mass loss at room temperature within 5 minutes (Figure S5). Interestingly, a slight increase of temperature showed an endothermic phenomenon and a significant 11% mass loss at 55 °C. Taken together below 65°C, 14% mass loss suggests the loss of acetonitrile molecules on Cu-2 including one coordinated solvent molecule responsible for the decrease of emissivity. [27] Interestingly, an unexpected phenomenon at 73 °C shows the additional loss of some acetonitrile ligand on the putative dimer leading to a new bright green emissive species. [27]  calc. (nm) Noteworthy that and in contrast to Cu-1, [14a] Cu-3 and Cu-4, reversible photoluminescence is not observed with powdered Cu-2 after the addition of small amount of acetonitrile. In fact, redissolution followed by crystallization is required to fully restore Cu-2 luminescent properties. [28] Coordinated solvent molecules on the resulting complexes Cu-1 to Cu-5 allow the development of tunable luminescent complexes which might be useful for sensing of solvent molecules via reversible photoluminescence. [5,14a,19,27] The drawback of this concept for other applications lies in the long time stability of some complexes towards slow degradation owing to the loss of solvent molecules. This would lead to the modification of the structural environment around the metallic center increasing vibrational quenching as well as structural distortion upon excitation. One way to solve this issue lies in the rigidification of the molecular scaffold by tailoring the electrostatic forces between the charged copper species and a metallic or an organic salt. Thus, taking advantage on the haloand cyano-cuprate chemistry, Cu-1 was next treated with metal salts. [12] Reaction of Cu-1 with an excess of potassium iodide at room temperature led to the precipitation of the mixed cuprate A 2 MLX 3 Cu-6 as a dianion in 80% yield (Scheme 3). X-ray structural determination highlights the formation of Cu-6 as a 2D-layered material with a minimal Cu-Cu distance of 6.9 Å (Figure 3, Figure S20). During the reaction of DPPBS L1-K with Cu-1 complex in boiling methanol almost quantitative precipitation of the monoanionic cuprate AML 2 X 2 Cu-7 was obtained. Importantly, in both cases, the iodides do not play the role of bridging ligands and the photoluminescent properties of Cu-6 and Cu-7 are not sensitive to grinding or drying. For the three-air stable neutral and -ate complexes Cu-1, Cu-6 and Cu-7 in their powdered form, the emission lifetime increases around ten times from 298K to 78K (Table 1 and Figure 4). The long emission lifetimes and high quantum yields exclude prompt fluorescence phenomena. The decay curves are largely monoexponential at 78K (Figure S9, S16, S19). Together with temperature increase, the decay times decrease for the three complexes and become biexponential for dimer Cu-1 and Cu-7.

Noteworthy that the emission spectra for Cu-1, Cu-6 and Cu-7 were not narrowed upon cooling which tend to exclude energy transfer between Cu-1 dimers or Cu-6 polymer or via other nonradiative processes (Figure 4). [12c] Whereas emission of Cu-7 was , interestingly, red-shifted upon cooling, equivalent to about 742 cm -1 (0.09 eV) peak to peak, no noticeable modification of the emission wavelength was observed with Cu-1. Furthermore, one should notice that even a slight blue shift was observed with Cu-6. Owing to the slightly low-lying T 1 triplet state, copper complexes exhibiting TADF are usually characterized by a red shift in emission upon cooling. Nevertheless, similar absence of red shift were reported independently by Osawa and by Yersin, which do not exclude TADF processes. [17,29] Emission decay profile for Cu-1 suggests that the pure triplet state τ(T 1 ) is reached below 78K. Small 𝛥 values were obtained by fitting the sigmoid decay curves 𝐸 𝑆 1 -𝑇 1 which strongly support phosphorescence at low temperature and the occurrence of both phosphorescence and TADF processes upon temperature increase (Table 1). [8a] The biexponential decays for Cu-1 and Cu-7 tends to support these results. The monoexponential decay for Cu-6 suggests essentially overlap due to fast equilibration processes owing to its rigid structure. This could prevent vibrational quenching or deactivation through structural distortion from the tetrahedral to quasi-square-planar coordination geometry (Figure 4). [17,19,29]

Conclusions

In conclusion, we prepared various photoluminescent copper(I) and cuprate(I) complexes by modification of the solvent or the metallic salt with water as the only side product of the overall synthesis. These results pave the way on the preparation of a true library of photoluminescent neutral and anionic complexes by varying the nature of the chelate, the solvent/gas or the metallic salt at the first or second stage of the synthesis to tune their optical properties. The use of other L,X chelating ligands with cuprates might afford interesting materials. Oxidation of the cuprates is underway in our laboratories.

Experimental General considerations

All reactions were carried out under argon atmosphere using Schlenk tube techniques. Unless stated, reagents were purchased from commercial sources and used as received. Acetonitrile, was dried using a MBraun Solvent Purification System. Methanol HPLC grade was degassed and used as received. NMR spectra were recorded at room temperature on a Bruker Avance (400 MHz) spectrometer and reported in ppm. Data are reported as follows: s=singlet, d=doublet, t=triplet, q=quartet, m=multiplet, br=broad. Coupling constants are reported in Hz. 13 C NMR spectra were recorded at 100.6 MHz on the same spectrometer and reported in ppm.

Synthesis of Cu-2

Cu-1 (200 mg, 0.22 mmol) was added to a Schlenk tube and stirred at 60°C under vacuum for 30 mins. The Schlenk was cooled at room temperature followed by the addition of acetonitrile (4 mL). The resulting mixture was then heated under stirring to dissolve the precipitate. The solution was then cooled at room temperature and then at -22 °C to afford colorless crystals of Cu-2. The solution was removed and the crystals of Cu-2.2CH 3 CN (190 mg, 76%) were kept under argon atmosphere. In contrast to the crystal structure, NMR analyses and cyclic voltammetry support predominance of a dimer in acetonitrile solution. [START_REF]The resulting mixture was heated at 60°C overnight. After cooling at room temperature, the solution was removed by cannulation and the white precipitate was dried under vacuum to give Cu[END_REF] H NMR (400 MHz, CD 3 CN): δ 8. 13-8.05 (m, 1H), 7.54-7.26 (m, 12H), 7.01 (t, J= 7.4 Hz, 1H), 2.15 (s, 3H); 31 P {1H} NMR (162 MHz, CD 3 CN): -11.07; 13 C {1H} NMR (100 MHz, CD 3 CN): δ 152.1 (d, J= 18.5 Hz), 135.6 (s), 134.3, 134.2, 134.0, 131.0, 130.7, 130.5, 129.6 (d, J= 9.2 Hz), 128.6 (d, J= 5.4 Hz). Elemental analysis for room temperature dried Cu-2-CH 3 CN, theoretical: C, 53.87, H, 3.84, N, 3.14, S, 7.19, measured: C, 53.71, H, 3.88, N, 3.01, S, 7.27.

Synthesis of Cu-3

Drent ligand 2-{bis(2-methoxyphenyl)phosphino}benzenesulphonic acid L2-H (135 mg, 0.33 mmol) and Cu 2 O (24 mg, 0.16 mmol) were added in a Schlenk tube under an atmosphere of argon followed by the slow addition of degassed acetonitrile under stirring. Then, the resulting mixture was stirred for one hour at room temperature. The white precipitate was dissolved by the addition of extra acetonitrile followed by cannulation and concentration to afford colorless crystals of Cu-3 (73 mg, 40%). [START_REF]The resulting mixture was heated at 60°C overnight. After cooling at room temperature, the solution was removed by cannulation and the white precipitate was dried under vacuum to give Cu[END_REF] H NMR (400 MHz, CD 3 CN): δ 8.10 (ddd, J= 7.8, 4.7, 1.4 Hz, 1H), 7.51-7.44 (m, 3H), 7.30 (td, J= 7.6, 1.4 Hz, 1H), 7.03 (dd, J= 8.3, 5.2 Hz, 2H), 6.97-6.88 (m, 3H) (d, J= 30.8 Hz), 128.6 (d, J= 6.6 Hz), 121.7 (d, J= 6.1 Hz), 120.7 (d, J= 35 Hz), 111.9 (d, J= 3.5 Hz), 56.2 (s). Elemental analysis for Cu-3.1CH 3 CN, theoretical: C, 52.47, H, 4.31, N, 3.99, S, 6.09, measured: C, 52.15, H, 4.10, N, 3.77, S, 5.74.

Synthesis of Cu-4

{tert-Butyl-4-Me-phenylphosphino}benzenesulfonic acid L3-H (100 mg, 0.29 mmol) and Cu 2 O (22 mg, 0.15 mmol) were added in a Schlenk tube under an atmosphere of argon followed by the slow addition of degassed methanol under stirring. Then, the resulting mixture was stirred for one hour at room temperature. The white precipitate was dissolved by the addition of methanol and moderate heating followed by cannulation. The resulting solution was concentrated to give air sensitive colorless crystals of Cu-4 (71 mg, 52%). [START_REF]The resulting mixture was heated at 60°C overnight. After cooling at room temperature, the solution was removed by cannulation and the white precipitate was dried under vacuum to give Cu[END_REF] H NMR (400 MHz, CD 3 OD): δ 8.12 (ddd, J= 8. 1, 4.3 Hz, 1H), 7.66-7.62 (m, 1H), 7.55 (ddd, J= 10.1, 6.3, 3.4 Hz, 2H), 7.43-7.34 (m, 4H), 3.35 (s, 6H), 2.42 (s, 3H), 1.33 (d, J= 15.5 Hz, 9H); 31 P {1H} NMR (162 MHz, CD 3 OD): -14.15. Elemental analysis for Cu-4.2CH 3 OH, theoretical: C, 47.85, H, 6.88, S, 6.08, measured: C, 47.64, H, 5.33, S, 7.06.

Synthesis of Cu-5

{tert-Butyl-phenylphosphino}benzenesulfonic acid L4-H (100 mg, 0.3 mmol) and Cu 2 O (22 mg, 0.15 mmol) were added in a Schlenk tube under an atmosphere of argon followed by the slow addition of degassed methanol under stirring. Then, the resulting mixture was stirred for one hour at room temperature. The white precipitate was dissolved by the addition of methanol followed by cannulation and evaporated under vacuum at 60°C to yield a white precipitate. Addition of acetonitrile followed by concentration afforded colorless crystals of Cu-5 dimer (60 mg, 45%). [START_REF]The resulting mixture was heated at 60°C overnight. After cooling at room temperature, the solution was removed by cannulation and the white precipitate was dried under vacuum to give Cu[END_REF] H NMR (400 MHz, CD 3 CN): δ

Scheme 1 .Scheme 2 .

 12 Scheme 1. Facile access to the acetonitrile containing mononuclear complex Cu-2 from the methanol containing dimer Cu-1.

Figure 1 .

 1 Figure 1. X-ray structures of Cu-2.2CH 3 CN; Cu-3.1CH 3 CN; Cu-4; Cu-5. lattice solvent molecules and hydrogens have been omitted for clarity. CCDC 1857809, CCDC 1857826, CCDC 1857827 and CCDC 1857812 contain the supplementary crystallographic data for Cu-2, Cu-3, Cu-4 and Cu-5.

Figure 2 :

 2 Figure 2: frontier MO diagram of complex Cu-1.

1 →

 1 LUMO (41%)

  Scheme 3. Preparation of the anionic and dianionic complexes Cu-7 and Cu-6 from Cu-1.

Figure 3 .

 3 Figure 3. Simplified X-ray structures of cuprates Cu-6.2MeOH (left) and Cu-7.(right) Hydrogen atoms as well as K-I contacts have been omitted for clarity. CCDC 1533360 and CCDC 1533368 contains the supplementary crystallographic data for Cu-6 and Cu-7.

Figure 4 .

 4 Figure 4. Emission spectra at 78K and 298K of Cu-1 (left), Cu-6 (middle) and Cu-7 (right) and emission decay profiles at different temperatures.

Table 1

 1 Experimental and calculated optical data.

	Complex k Cu-1 λ abs (nm) a λ em (nm) 78K 298K Φ b  (s) c 78 K 298 K 244, 290,330 515 515 0.51 57 2;9 (2.99)	170.10 3	59	0.139	0.05
	Cu-2			568	0.34		2.0	170.10 3
	Cu-3			550	0.40
	Cu-4			522	0.12
	Cu-5	230,280		560;600	0.06
	Cu-6	262,298,320,362	508	515	0.60	76	8	75.10 3	76	0.048	0.10
	Cu-7	262, 298, 474	593	568	0.10	107	1;10 (3.0)	33.10 3	105	0.080	0.07

r (298K) [s -1 ] τ(T 1 ) [µs] d τ(S 1 ) [µs] d ΔE (S1-T1) [eV] d a in solid state at 298K. b in solid state at 298K. c number in parenthesis corresponds to av=(B1/(B1+B2)) 1+(B2/(B1+B2)) 2, in which B1 and B2 are relative amplitude for 1 and 2, respectively. d Calculated from the fit of the decay curves with the equation provided in ref. 8a.

Table 2 :

 2 TD-DFT computed UV-vis in solution (MeOH) of Cu-1. Computed oscillator strengths are given in square brackets.

Acknowledgements

The authors thank the University of Rennes1 for financial support of this project. We acknowledge the HPC resources of CINES and of IDRIS under the allocations 2017 and 2018-[x2016080649] made by GENCI. A. B., H. A. K. and M. A. thanks O. Mongin and J. Rocherulle for helpful assistance.

Conflicts of interest

There are no conflicts of interest to declare


Even Entem

Amal Dev Parakkat

Loïc Barthe

Ramanathan Muthuganapathy

Marie-Paule Cani

Automatic structuring of organic shapes from a single drawing

Introduction

Contour drawings are commonly used for shape depiction. They are both easy to create and easy to interpret for a human and thus it makes them a convenient and expressive solution for visual communication. They are found in children's books, advertisements, technical books, and more. In contrast, these drawings are difficult for a computer to interpret. They usually depict silhouette curves and internal contours as well as expressive strokes, and they may represent fully visible, selfoccluding, or locally hidden regions.

Many contour drawings are directly authored in vector graphics applications or are easily converted to a compatible representation using vectorization tools. Automatically decomposing them into distinct and simple structural parts, layered in depth (as in Figure 1 (b)), permits users to edit and manipulate the drawings intuitively by rescaling, moving, rotating, copying, and pasting parts without the need for intricate manual modifications and corrections which would otherwise be required for such operations.

In this paper, we present an automated geometric method for extracting apparent structure and depth layers from clean contour line-drawings. We assume that the input drawing is intended to represent an organic shape, i.e., any free-form 3D solid with smooth connections between its 3D structural parts. The extracted depth-ordered structure is similar to the collection of blobs that artists sometimes use to temporarily define the construction lines and volumes of the shape they want to depict (see results of a web image search with the terms "tutorial drawing construction animals").We record additional information, namely, where these volumes blend together and where contours should be erased. This information can then be used for both current and nearby views editing to achieve new poses such as in Figure 1 (c). Although view-dependency may prevent the structure from being complete relative to the actual structure of the 3D depicted shape, we claim that it is still a useful reference for editing the current drawing to depict nearby postures or viewpoints.

The input drawing may be composed of silhouette curves as well as different categories of internal and external curves. They include internal open contours connected to silhouette curves, e.g., the contours of the feather groups in Figure 1 (a). Regions in the drawing that are demarcated by silhouette curves may also include a number of internal regions depicting parts, possibly lying on top of one another, such as the eye of the swan in Figure 1. Highly ambiguous curves, such as disconnected internal curves and connected external open curves, are considered in our work as decorative curves. We also detect and discard internal elements that fail to define their own silhouettes (see Section 3.2).

Our three contributions towards solving structuring and layering problems for drawings are as follows:

• We describe a simple and efficient method for the aesthetic closing of part contours. This method provides a consistent solution when disconnected endpoints are not explicitly defined in the input drawing (Section 4).

• We introduce the radial variation metric (RVM), a novel part-aware metric for complex 2D drawings, inspired by the volumetric shape image used for shape segmentation of 3D models [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF]. Its variation along the medial axis of parts in a drawing enables the identification of salient connections between parts (Section 5).

• We describe a recursive algorithm enabling the successive identification of parts in a complex sketch and their assignment to depth-layers (Section 6). The key insight lies in processing the possible junction zones between the identified parts in a specific order based on the types of contours involved. This enables us to handle cases of multiple connected internal contours forming a tree-like structure, as can be observed for the swan wing in Figure 1.

The structure and layering information we obtain can be used to represent and edit the input sketch in current or nearby views.

We also demonstrate the automatic conversion of the sketch into a Vector Graphics Complex (VGC), a structure that eases the computational and manual editing of vector drawings, and that readily allows for manipulation, editing, and animation (Section 7).

In Section 8, we discusses two of the possible applications of our system, namely the creation of cardboard articulated puppets and of 3D models from a sketch.

Related work

Recovering the structural parts of 3D objects in 2D vector contour drawings is a long standing and complex problem. This is due to the lack of information required for the unambiguous and automated shape understanding of most drawings. For instance, the understanding of the main features in a drawing is often based on contextualized interpretations.

Given that a drawing is only composed of lines, several approaches have been proposed to identify which visual mechanisms are used to help interpret the drawn lines in terms of self-consistent shapes and contours [START_REF] Singh | Visual representation of contour and shape[END_REF]. Several methods address specific aspects of this complex process and techniques have been developed to evaluate them on well-defined data sets. Alternatively, more practical approaches aim at providing actionable interpretation methods by leveraging knowledge about particular object classes and relying on Gestalt principles.

One such Gestalt principle, the principle of closure -how our visual system tends to perceive the missing parts of curves or contours -has been used by algorithms to complete hidden and subjective contours [START_REF] Ullman | Filling-in the gaps: The shape of subjective contours and a model for their generation[END_REF][START_REF] Nitzberg | The 2.1-D sketch[END_REF][START_REF] Williams | Perceptual completion of occluded surfaces[END_REF]. Many solutions rely on plausible, visually appealing curves such as Minimum Energy Curves (MEC) [START_REF] Horn | The curve of least energy[END_REF] that maximize the curve smoothness, and Minimum Variation Curves (MVC) [START_REF] Moreton | Minimum curvature variation curves, networks, and surfaces for fair free-form shape design[END_REF] that generate fair solutions. Our technique uses a variation of the latter with the aim of efficiently generating aesthetic curves.

Our approach is also inspired by the fact that the human visual system tends to segment a complex shape into simpler parts. Shape segmentation problems have been tackled for a very long time. Pioneering work relied on the branches of the skeletal representation of 2D shapes for inferring segmentation [START_REF] Blum | Shape description using weighted symmetric axis features[END_REF]. Observing that the quality of the correspondence between branches and depicted shape parts drops as the complexity of the object rises, subsequent work rather made use of maxima of negative curvature on the contour to identify part boundaries and focused on trying to disambiguate pairing between such boundary elements [START_REF] Richards | Inferring threedimensional shapes from two-dimensional silhouettes[END_REF][START_REF] Latecki | Convexity rule for shape decomposition based on discrete contour evolution[END_REF]. Shape segmentation then became a classical problem for both 2D and 3D shapes. The surveys by Yang et al. [START_REF] Yang | A Survey of Shape Feature Extraction Techniques[END_REF] and Shamir [START_REF] Shamir | A survey on mesh segmentation techniques[END_REF] present a detailed study of these methods Fully accepted general solutions do not yet exist, and segmentation remains an area of active research even for the 2D case [START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF][START_REF] Carlier | The 2d shape structure dataset: A user annotated open access database[END_REF][START_REF] Leonard | A 2d shape structure for decomposition and part similarity[END_REF]. In parallel, interactive sketch segmentation and/or completion methods based on human input were proposed to fill in drawings [START_REF] Pessoa | Filling-in: From perceptual completion to cortical reorganization[END_REF], to select layers for shape manipulation [START_REF] Igarashi | Apparent layer operations for the manipulation of deformable objects[END_REF], to segment sketchy drawings [START_REF] Noris | Smart scribbles for sketch segmentation[END_REF] or to simplify them [START_REF] Mi | Abstraction of 2d shapes in terms of parts[END_REF][START_REF] Liu | Closure-aware sketch simplification[END_REF].

In this work, we build on, or draw inspiration from, a number of the processing steps introduced for 2D [START_REF] Giesen | The scale axis transform[END_REF] and 3D [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF] shape segmentation. However, our goal is to automatically segment complex sketches with not only contours but with internal silhouettes as well. Indeed, internal silhouettes are great perceptual conveyors of shape, as shown by their extensive use for ex-pressive depictions of 3D models and high-reliefs [START_REF] Decarlo | Suggestive contours for conveying shape[END_REF][START_REF] Eisemann | A visibility algorithm for converting 3d meshes into editable 2d vector graphics[END_REF][START_REF] Kunsberg | Critical contours: An invariant linking image flow with salient surface organization[END_REF]. Therefore, taking them into account is essential for being able to segment a larger variety of drawings.

This new goal brings us to prior work in the area of sketchbased modeling, where a number of methods relied on the analysis of complex sketches to infer a 3D shape or a 2.5D high relief from a single sketch, e.g., [START_REF] Karpenko | Smoothsketch: 3d free-form shapes from complex sketches[END_REF][START_REF] Cordier | Free-form sketching of self-occluding objects[END_REF][START_REF] Xu | True2form: 3D curve networks from 2D sketches via selective regularization[END_REF][START_REF] Yeh | Interactive high-relief reconstruction for organic and double-sided objects from a photo[END_REF]. Most methods in the area built on a priori knowledge (or contextual information) in order to resolve ambiguities -such as requiring exact symmetric shapes [START_REF] Cordier | Sketching of mirror-symmetric shapes[END_REF], being restricted to garments [START_REF] Turquin | A sketchbased interface for clothing virtual characters[END_REF] or to side views of animals [START_REF] Entem | Modeling 3d animals from a side-view sketch[END_REF] or requesting 3D information such as a 3D skeleton from the user [START_REF] Bessmeltsev | Modeling character canvases from cartoon drawings[END_REF]. Others methods obtained great results by relying on interactive user annotations for helping to infer high-reliefs from photos or drawings [START_REF] Rivers | 2.5d cartoon models[END_REF][START_REF] Sýkora | Ink-and-ray: Bas-relief meshes for adding global illumination effects to hand-drawn characters[END_REF][START_REF] Bui | 3d-look shading from contours and hatching strokes[END_REF][START_REF] Yeh | Interactive high-relief reconstruction for organic and double-sided objects from a photo[END_REF].

Closer to our goal, interpreting drawings of general organic shapes (ie. smooth 3D solids) depicting all visible silhouettes including cusps was tackled by Karpenko's pioneering work [START_REF] Karpenko | Smoothsketch: 3d free-form shapes from complex sketches[END_REF] in the context of 3D modeling from a sketch. To this end, drawn lines were represented as networks of oriented curves, enabling the authors to identify holes and to propose a reconstruction method for hidden silhouettes indicated by Tjunctions. While we build on this work, we chose not to ask the user for the orientation of contours, thus interpreting a twocircle drawing of a torus as two superposed spheres. We focus instead on extending the handling of internal curves beyond cusps, enabling us to handle more complex suggestive contours as well as extra decorative elements.

In summary, we provide the first fully automatic method able to extract structural parts from cartoon drawings of organic shapes. We provide in Section 7 a detailed comparison between our results and those of previous work, by re-using a number of their examples.

Finally, we note that our method outputs a layered structure of parts locally ordered in depth, so as to ease the subsequent editing of the drawing. Different structures and representations have been developed to handle partial depth orderings [START_REF] Wiley | Representation of interwoven surfaces in 2 1 /2d drawing[END_REF][START_REF] Wiley | Druid: Use of crossing-state equivalence classes for rapid relabeling of knot-diagrams representing 2 1 /2D scenes[END_REF][START_REF] Dalstein | Vector graphics complexes[END_REF]. In this work we output results in the VGC format [START_REF] Dalstein | Vector graphics complexes[END_REF], and we choose to define a self-consistent global depth ordering of the shape parts. The extracted structure is view-dependent (there is no structure inferred for parts that are completely occluded, for instance), and the rule that treats in-ternal silhouettes as distinct cases may lead to occasional surprises. For example, the pupil of the cat's eye in Figure 2 is in fact a hole inside the eye, and thus its correct manipulation would require an intersection operator with the eye region to not protrude out of it.

Overview

Our method decomposes an input drawing into a set of 'structural parts', layered in depth, and computes the location of hinges enabling the pose and the animation of the drawn model. The decomposition is based on connected internal silhouettes and inner closed contours in the drawings, which provide explicit indicators of part layering; the resulting parts are intended to be meaningful for artists as shape-defining-volume silhouettes, and can be used for editing and posing in nearby views.

This section introduces the terminology we use throughout the paper, defines the assumptions we make on the input drawing, and presents the main features of our algorithm.

Terminology and assumptions

The input of our method is a vector line-drawing D defined in the (x, y) plane as a set C of parametric curves that may only intersect at their endpoints. The drawing may be either directly created in this form or obtained from a rasterized drawing using a vectorization algorithm [START_REF] Noris | Topology-driven vectorization of clean line drawings[END_REF] and then cutting curves at all intersections. Parametric curves are also uniformely sampled as polylines for some of the further processing. In the following, we therefore refer to points along the curves in C as samples.

As in Smoothsketch [START_REF] Karpenko | Smoothsketch: 3d free-form shapes from complex sketches[END_REF], our algorithm is designed to handle contour-drawings of smooth, closed shapes, which we refer to as organic shapes. However, to be able to handle a larger category of drawings, we also allow them to include specific categories of decorative curves such as those often used in cartoon drawing.

Therefore, our algorithm includes a mechanism for the automatic detection of contour curves within C. Since we are not asking for any additional information (such as contour orientations) from the user, we assume that the depicted shapes have no surface-to-surface contact, have genus 0, and are not selfoverlapping (e.g., no animal's tail passing under and behind the body and forming a new background region).

We use the following terminology throughout the paper (see Figure 2): Contour: A contour is a curve in C that corresponds to a silhouette of the depicted 3D shape, i.e. to points where the normal to the shape is orthogonal to the viewpoint. The contour graph is the planar graph structure formed by the contours and their intersections. Suggestive contour: A suggestive contour is an internal curve within a region R of the drawing, connected with tangent continuity to its external contour (and thus forming a Tjunction). Such curves are used in drawings to partially depict the visible contour of a structural part.

Region: A region R is a 2D connected component of
Note that this definition is slightly different from the one found in the literature, since our term is in between the concepts of suggestive contours [START_REF] Decarlo | Suggestive contours for conveying shape[END_REF] and of cusps [START_REF] Karpenko | Smoothsketch: 3d free-form shapes from complex sketches[END_REF], to better match what we observed in typical line drawings.

Decorative elements: These include all curves in D that are not visible contours of the depicted shape, but can instead represent ornamental details, 1D elements such as hair, or strokes used to represent bas-relief carvings. In our case, a curve is considered as a decorative curve if it falls in any of the following categories:

• Inner isolated subgraphs that do not contain external contours when processed as independent input drawings (in purple in Figure 2). Although they might contain or actually be inner contours, such subgraphs are highly ambiguous. We leave interpreting and processing them for future work. • Inner trees of curves that are connected to the external contour of a region, but without tangent continuity (blue curves in Figure 2) • Trees of curves located outside of the region they are connected to (green curves in Figure 2, which we call hair).

In our method, the decorative curves are identified and ignored in further contour processing, but are kept in the description of the corresponding to-be-segmented part.

Processing pipeline

Let G be the contour graph, the planar half-edge graph defined by the curves C that constitute the input drawing D. As in standard planar graph processing, each half-edge corresponds to a given orientation of a curve. If half-edges are part of a closed contour, they are considered to lie respectively in the interior and in the exterior of the corresponding face cycle of the Fig. 3. Processing pipeline: The input is (a) and the output is (h) with partial depth ordering (here depicted in exploded view). Note that our algorithm successfully decomposes the petal even in the absence of a suggestive contour (see the top left petal in (h)). This holds because our decomposition relies on the measurement of salient transition between two different regions and not on the presence of suggestive contours.

graph. In the remainder of this section we use both "edge" and "curve" to denote the edges of G, depending on context.

The goal of our method is to process G in order to extract and progressively refine the set P of 2D structural parts of D, as well as the associated partial depth ordering PO P expressing their relative depths. More precisely, P is defined as:

P = {P i = (e i , S i , O i )}
, where e i is the external silhouette contour (as a list of edges) of P i and where S i (respectively O i ) is the subgraph of G corresponding to the suggestive contours (respectively, the decorative elements) located within P i , or attached to it.

Our processing pipeline, detailed below, is depicted in Figure 3. Starting with an initial set of silhouette-complete parts extracted at the initialization stage, our algorithm recursively decomposes each part into simpler parts and updates PO P accordingly. This is done until none of the parts in P has any suggestive contour left (for all i, S i is empty).

Initialization:

We aim at initializing P to a first set of structural parts, such as the heart of the flower versus the part with all its petals in Figure 3 or the head versus the ears and the nose of the head in Figure 2 (a), and to set PO P to the corresponding partial depth ordering. This involves completing the contours of partially hidden parts, such as the ears. Although this decomposition and figure completion problem was already solved in the past [START_REF] Williams | Perceptual completion of occluded surfaces[END_REF], this was for drawings only depicting silhouette outlines of occluded surfaces. To handle more complex cases of cartoon drawings with decorative lines such as the whiskers in Figure 2 (b), we extend the original method into a four-stage process:

First, if G contains any vertex v of valence 4 or more (such as vertices where the whiskers of the cat cross the head's contour in Figure 2 (b)), we convert G into a non-planar graph by dissociating the curves at v, enabling us to further process the whiskers as decorative elements attached to the nose. This is done based on the Gestalt rule of continuity, as follows: For each vertex v of valence 4 or more with adjacent edges in G that correspond to pairs of tangent-continuous curves, we join each pair of curves at v into a single curve. This disconnects the pairs of curves from each other, enabling them to be attached to different structural parts. A constraint is also set to prevent more than one pair of merged curves from being interpreted as a contour curve in further processing, since this would violate our hypotheses of organic shape depiction (e.g., two overlapping circles do not correspond to any valid contour of organic shape, and are thus interpreted as a single 2D region crossed by a closed decorative curve). After this stage, any connected component of G that still contains a vertex of valence larger than 3 is considered in its whole as a decorative element, since a set of curves that connect without any tangent continuity cannot include silhouettes of smooth organic shapes.

Then, we process each remaining connected component CC j of G to separate contour curves from curves corresponding to the associated suggestive silhouettes or decorative elements.

Since the input drawing is supposed to contain no selfoverlapping part, this can be done by simply moving every edge whose half-edges both belong to the same face cycle (ie. lie in the same 2D region) from CC j to another subgraph A j , which gathers candidate edges for either S i or O i . Note that this operation may split CC j into smaller connected components, since the edges moved to A j may include bridges between different subgraphs. In this case, CC j and the corresponding A j are split into smaller subgraphs. We decide to which sub-connected component the bridge sub-graph should be associated to by looking at its tangent continuity with the neighboring curves: We insert the bridge into the A k set associated with the subgraph CC k of CC j to which it has tangent continuity at one of its endpoints (e.g., a suggestive curve partially hidden by the contour of an inner part). If there is tangent continuity at both ends, the decision is taken at random. If there is none, the bridge is considered as a decoration and is attached to the subgraph corresponding to the contour of the region where it lies.

At this stage, each CC j should only contain contour edges (for instance, the drawing in Figure 2 (a) is split into two connected components, namely (1) the nose and (2) the head plus ears, where only black curves remain). This enables us to use the existing algorithm in [START_REF] Williams | Perceptual completion of occluded surfaces[END_REF] to split then into structural parts, by using T-junctions to identify partially hidden parts (such as the ears) and smoothly complete their contours. Failure cases of this algorithm and other limitations will be discussed in Section 7.

In contrast with previous work, we use our own efficient solution, presented in Section 4, to compute closure curves. All resulting parts P i are stored in P together with their contour edges e i . The corresponding partial depth ordering information is added to PO P . We also add temporary depth relations with the remaining connected components, depending on the number and order of intersections with each other component to reach the background of the drawing with a line (parts with the same number of intersections being considered to have the same depth level).

In a final stage, the set S i of suggestive contours of each part P i is extracted from the set A j associated to its former connected component CC j , by selecting curves with smooth Tjunctions with contours e i and that lie within P i . The other curves in A j connected to e i are classified as decorative elements and added to O i . Lastly, every curve in other A k sets that were initially crossing any of the current contour curves are stored in the set O k of the part in which it is located since they no longer can be contours.

The set of parts P is now ready for further decomposition.

Recursive part decomposition:

The core of the algorithm is a procedure that decomposes P into parts that are themselves decomposed recursively if possible.

This enables us to process complex suggestive contours indicating embedded parts, such as the wing of the swan in Figure 1: The full wing is extracted first and is then recursively split into partially overlapping parts. The recursive loop proceeds as follows:

For each part P in P, we identify the salient potential junction region zones between parts, and iterate from best-to-worst until a valid pair (P a , P b ) of parts is identified. Missing contours are then inferred for P a and P b (see Figure 3 (g)) and the depth ordering relation between them is added to PO. P a and P b are added to the list of parts P, enabling us to recursively apply this process until no further decomposition is possible (Figure 3 (h)).

This recursive decomposition method raises three challenges, leading to our three key technical contributions:

(1) The description of a robust method for completing the contours of the extracted parts in a perceptually valid way.

(2) The design of an effective metric for identifying the regions of possible junction between the parts of a 2D shape.

In contrast with previous work, the 2D shapes we process may include suggestive contours, which are not constrained to come in even numbers, or to be short cusps.

(3) The definition of an order in which to process the identified alternative solutions for segmentation into parts.

This order is important for extracting consistent parts as it enables us to reuse the same algorithm in a recursive fashion.

Our aesthetic and efficient contour completion is presented in Section 4 and we discuss our new metric for identifying junctions in Section 5. Section 6 details our recursive structuring algorithm. It makes use of our new metric and completion method, with an emphasis on the priority order we set for processing possible junctions.

Aesthetic and efficient contour completion

In this section, we present the completion method we use for closing contours of both partially occluded structural parts (initialization step) and of parts extracted during recursive part decomposition. Although not proved to be the best possible perceptual completion method, our solution is simple, efficient, and produces adequate results in practice.

Scale-Invariant MVC

We first note that perceptually pleasing contour completion is a different problem than completing illusory contours [START_REF] Williams | Perceptual completion of occluded surfaces[END_REF]. We seek to find aesthetic curves that are appropriate for the editing and subsequent animation of the drawing, during which hidden or omitted contour segments may become visible. In the literature, both curves minimizing the total curvature (i.e. "smooth" curves, MEC's) and curves minimizing the total variation of curvature (i.e., "fair" curves, MVC's) have been proposed as possible solutions to the problem. We choose to use MVC's because they tend to form more circular arcs; these are particularly well suited to organic shapes.

Let A and B be the two endpoints of the open contour to be connected, along with corresponding unit tangent directions T A and T B as shown in Figure 4 (a). Our goal is to generate a perceptually plausible curve between A and B that best matches an inferred silhouette for the resulting part.

We define the curve connecting these two input points as follows. Let B AB be a Bézier cubic curve connecting A and B, defined by the four control points (A, P 1 , P 2 , B), and whose tangents are aligned along the unit vectors T A and T B , i.e., P 1 = A+c 1 T A , and P 2 = B+c 2 T B . We optimize the free parameters c 1 and c 2 in order to minimize a "fairness energy" i.e. a variation of the SIMVC energy originally introduced by Moreton [START_REF] Moreton | Minimum curvature variation curves, networks, and surfaces for fair free-form shape design[END_REF]. Let C(s) be a parametric 2D curve with curvature κ(s). Then the SIMVC energy [START_REF] Moreton | Minimum curvature variation curves, networks, and surfaces for fair free-form shape design[END_REF] is defined as:

E SIMVC-Moreton = ds 3 dκ(s) ds 2 ds ( 1
)
where ds 3 is the product of a regularization factor ds / B -A 3 and a scale-invariance factor B -A 3 . This regularization factor relies on the cube of the scalerelative arc length of the curve. We increase the regularization factor's exponent from 3 to 5 in order to reward slightly shorter curves. This avoids cases where closure curves would slightly jut out from the desired boundaries. We thus propose to minimize the following energy:

E SIMVC = ds 5 B -A 2 dκ(s) ds 2 ds (2)
As in Equation 1 the first term makes the curves scaleinvariant. The use of Bézier curves guarantees that the curve lies in the convex hull of its control points and is therefore well suited to interactive sampling and intersection queries. The choice to optimize its parameters with the SIMVC functional produces a scale-invariant result.

In practice, we use the standard Gauss-Kronrod quadrature [START_REF] Kronrod | Nodes and weights of quadrature formulas: sixteen-place tables[END_REF] to numerically integrate the different integral terms. Powell's method [START_REF] Powell | An efficient method for finding the minimum of a function of several variables without calculating derivatives[END_REF] is used for minimizing E SIMVC .

Efficient implementation

Given that the completion curves we compute are invariant to scaling, translation and rotation, there remain only two configuration parameters, namely θ and ϕ. They are the oriented angles formed by the two tangents with respect to a line between the two points to be connected, as shown in Figure 4 (a). The SIMVC energy of our curve defined as a function of these two parameters is continuous and smooth in the sub-space of non self-intersecting curves, as shown in Figure 4 (b). This enables us to precompute a table of the different SIMVC Bézier cubic curves, with their SIMVC energy and parameters c 1 and c 2 , as a function of θ and ϕ. Parameters can then be interpolated, with either bilinear or bicubic interpolation, to provide both an approximated curve and good initial parameters for the final curve computation, leading to an important speedup of the gradient descent with two variables.

In practice, we use Bézier curves for easily detecting invalid contours that occurs when the closures for partially occluded or partially occluding parts protrude outside the union of the related parts. To avoid unintended intersections we rotate tangents, at the points to be connected, inwards and by a small angle, keeping the misalignment of tangents almost imperceptible. During our experiments, we chose a rotation of 2 degrees.

Extracting Regions of Possible Junction within a Part

While previous work already addressed the segmentation of 2D shapes into perceptually salient parts, these methods do not tackle the segmentation of shapes carrying extra structural information in the form of suggestive contours. This is the problem we are addressing here.

Regions of possible junction

In the remainder of this paper, we define a region of possible junction as a region where the drawing of a part exhibits a perceptual change, enabling it to be divided into two parts in a perceptually consistent way.

We define junction boundaries as being the portions of the part contours that delimit such a junction. These portions can either be a point (e.g., the open end of a suggestive contour) or a contour segment, as will be the case when the exact point where the segmentation should occur is unclear.

Among the common approaches to 2D shape segmentation that we review in Section 2, computing junction boundaries as the segments of the contour of maximal negative curvature cannot capture approximate regions such as those indicated by the orange and blue junction boundary in Figure 5 (a), since the blue one is not a curvature maximum and thus would not be detected. Similarly, segmentation methods that directly make use of the branches of a skeletal representation such as the Medial-Axis Transform to identify parts, also fail in a number of cases, as shown in Figure 5 (b,c). Fortunately, such correspondence between a Medial-Axis branch and a structural part remains generally true for foreground structural parts delimited by suggestive contours, such as the middle part in Figure 5 (b). The solution we describe below therefore builds on skeletal representations, while being based on a new metric. Our new parts-aware metric is inspired by a similar metric [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF] developed for 3D shape segmentation. In particular, it makes use of a Surfacic Shape Image, a modified 2D version of the Volumetric Shape Image (VSI) introduced in [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF]. However, we tailor this more specifically to our problem, as detailed below.

Radial Variation Metric

We define the Surfacic Shape Image (SSI) as a signature of silhouette visibility from a given point of view inside a part of the input drawing (see Figure 6). A signature SSI i is defined as a set of m distances l k i between closest points p k 0,i and p k 1,i to the point i in the k th direction of a pre-defined uniformly sampled set of m directions. From 60 to 100 directions per set are used for the different examples in this paper. Both external contours and internal contours are considered at this step, while decorative curves are discarded.

Similar to the 3D case, the local change of SSI (differential of SSI) between two neighboring points can be used to detect a region of possible junction between two structural shape parts. We propose to compute this differential between points A and B as follows:

∆(SSI) A,B = 1 k w k,A,B m k=1 w k,A,B l k A -l k B B -A (3)
where

l k i = p k 1,i -p k 0,i (4)
Discontinuities near open ends of suggestive contours as depicted in Figure 6 generate outliers. To tackle this problem, we fit a Gaussian to the distribution of such values (as in [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF]) using the weights w k defined as follows:

w k,A,B =        e -(d k,A,B -u) 2 /(2σ 2 ) , if d k,A,B < u + 2σ 0, if d k,A,B >= u + 2σ (5)
where d k,A,B = l k Al k B / B -A , u is the mean of the d k,A,B 's, and σ the standard deviation.

Note that in contrast to [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF], l k Al k B is not squared in Equation [START_REF] Ullman | Filling-in the gaps: The shape of subjective contours and a model for their generation[END_REF], in order to make the equation more linear. In addition, we regularize this term by dividing it by the distance ( B -A ) between neighboring points of view. This allows for similar results whatever the sampling resolution at which this measure is used. Thus ∆(SSI) tends to be scale-invariant for high resolutions when there is no discontinuity of visibility. Let us now define a part-aware metric built on the SSI. Note that we cannot reuse the method introduced by Liu et al. [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF], where the distance used to segment a 3D mesh was defined as the integral of the VSI distance along a geodesic path between vertices. Indeed, in our case, there is no 3D surface to support and define the actual shortest path between two facing vertices on opposite sides of a shape. Therefore, our approach identifies salient parts by defining a 2D Part-Aware metric along the curves of a specific skeleton, called the salient skeleton (Sskeleton), as described below.

We initialize the S-skeleton of a shape part as the medial axis of the region bounded by the external contour and the suggestive contours of this part, as shown in Figure 5 (b). Decorative curves are discarded. As usual, it is defined as the locus of the disks of a Medial-Axis Transform (MAT ) which are the maximal disks that do not intersect the set of contours (see Figure 3). For the S-skeleton to only reflect the main shape features, we proceed in a fashion similar to the Scale-Axis Transform [START_REF] Giesen | The scale axis transform[END_REF]. The goal is to locally remove small disks by considering those that can be covered by others in a version of the MAT with larger radii. The final result can be realized by computing the MAT of the grown shape defined by the union of scaled up disks from the initial MAT , and then scaling down the radii. However for reasons of computational efficiency and simplicity, we choose to iteratively remove disks from branch extremities in the grown MAT that are covered by others and then scale down the radii of the remaining disks (in practise, we use a scaling factor of 1.3). This avoids several computations leading to similar results. Additionally, the associated contour points of these removed disks are given to the nearest remaining neighboring disk in order to keep a mapping between contours and the Sskeleton.

Given that the drawing represents the silhouettes of a volumetric, organic shape, the S-skeleton is a good candidate for extracting structural information about salient parts. We should however take care of correctly assigning curves in the drawing to the different branches of the S-skeleton. To achieve this, we represent the curves in the drawing, as well as the S-skeleton itself, using half-edges. This enables us to assign the duplicate vertices on two sides of a suggestive contour to different branches of the S-skeleton (see Figure 7).

Our new 2D part-aware metric called radial variation metric (d SSI ) is defined over the S-skeleton as the integral of the SSI differential (Equation ( 3)) along the shortest path joining two vertices of the S-skeleton. Let M A and M B be two vertices of the S-skeleton and E be the set of edges of the shortest path between them. d SSI is then defined as:

d SSI (M A , M B ) = e∈E ∆(SSI) e (6)
The last point is the sampling rate used along the S-skeleton. We note that the contribution of the salient discontinuity ∆(SSI) in region of possible junctions is related to the number of rays included in the parallax angle of a discontinuity location seen from neighbor points. We tried two alternative sampling methods to correctly measure this contribution along the S-skeleton. The first uses a uniform spacing, relative to the drawing size (in practice 0.5% of the drawing's height) while the second uses a dynamic spacing relative to local Medial-Axis disk radii (in practice 0.02 * local radius). While the first method better matches perceptual principles, the second one improves the processing of small details. The results presented in this paper have been generated using the first method for better readability of figures. We emphasize that even though the measure extends to the continuous case where there is no discontinuity, the resolution of the SSI sample points should not be higher than the one of the input polylines so as not to reflect the lack of curvature of the polylines (otherwise a wave like pattern would emerge).

Region of possible junction detection

With the S-skeleton S being computed from a medial axis transform, each edge e ∈ S is associated with two facing portions of the contours, i.e. the segments or point of the contours that could be generated by drawing discs from this specific edge of the skeleton. This enables us to use the S-skeleton to define both regions of possible junction (the regions we are looking for) and the junction boundaries that delimit them on the contours.

We initialize regions of possible junction as the 2D regions corresponding to segments of the S-skeleton with d SSI values over a threshold k (see Figure 7 (b)). Thanks to the scaleindependent nature of the metric, a single threshold value k is used regardless of the scale of the input drawing (we use k = 0.45 for all our results). These segments are stored using lists of edges of the S-skeleton. Since sharp extremities of structural parts may correspond to large-but-irrelevant d SSI values, we remove them in a second pass: Starting from S-skeleton extremities, we iteratively remove edges while their d SSI values decrease. Increases in d SSI values due to noise can lead to unwanted decomposition of pointy ends, but are mostly avoided by smoothing the d SSI values along the S-skeleton first. Due to the nature of the SSI, sampling points near the middle of a radially symmetric transition will yield low d SSI values compared to other transitions as illustrated in Figure 8. However, we note that the negative curvature cues on both sides are implicitly given by the diamond shape formed between the junction zones (Figure 8 (a)). We merge these regions of possible junction if the distances d C0 and d C1 between the junctions zones along contours are both inferior to the distance d M along the S-skeleton, and inferior to the half of the average radius of the Medial-Axis disks of the junctions zones.

Recursive decomposition

Given the general methods that we have described for closing contours and for extracting regions of possible junction within a structural part, we now detail how a given part is decomposed, i.e., how its regions of possible junction are prioritized, and how the corresponding parts are extracted and completed.

Prioritizing regions of possible junction

Decomposing a part not only requires extracting possible junction regions between parts, but also assigning them a prioritized order. We achieve this via a classification of regions of possible junction, depending on the type of contour segments that contributed to this specific part of the S-skeleton. Since they are defined by segments of the S-skeleton, each region of possible junction comes together with a pair of junction boundaries (the associated parts of the contours, possibly reduced to a point) found on each side of the skeleton. Regions of possible junction are classified as follows, based on the nature of this pair of junction boundaries (see Figure 9): 1. Two segments of suggestive contours, that do not belong to the same tree of internal silhouettes: The junction is either classified (SF, SF) and (SB, SB), depending on whether the suggestive contour's curves (a set of half edges) correspond to a front (occluding) or to a back (occluded) part of the shape. The occluding side is given by the T-junction properties. 2. A pair formed by an external contour segment and a suggestive contour segment: We only consider the case when the suggestive contour side corresponds to the front of the shape, denoted as (C, SF). 3. Two portions of the external contour: the junction is classified (C, C).

If a curve segment in a pair spans different types of contours, the associated region of possible junction is subdivided. Regions that do not fit into the categories described above (in pink in Figure 9) are discarded, since they have a bounding contour on one side and an occluding one on the other, and this case is not handled by our decomposition. This classification is used to select the salient parts to be extracted at each stage of the recursive part decomposition algorithm described in Section 3.2: (SF, SF), (SB, SB), (C, SF) and (C, C) regions of possible junction are respectively given highest to lowest priority. This enables us to give priority to parts that are unambiguously in front of their neighbors, such as for the bottom-right part of the flower in Figure 3, before processing partially occluded parts and those with weaker depth clues. Fig. 10. Adding relative depth information along a suggestive contour, illustrated here for the case of a complex curve forming a tree. As shown here, the numbering must be made in forward or backward fashion depending on the root T-junction.

Processing complex suggestive contours

In addition to the sorting order we just defined, parts defined by (C, SF) junctions need to be given a priority order. This enables us to handle cases where the suggestive contour forms a tree of branching curves, such as the swan's wing in Figure 1.

Let us look at the similar shapes on Figure 10: parts with high label values on the edges need to be extracted first, since they embed the other ones. This enables us to extract the full wing, which can then be progressively decomposed into three consistent parts.

Given that suggestive contours represent internal silhouettes of volumetric parts of a shape that smoothly blend with the parent part, they should have a G 1 continuous junction to the silhouette they are attached to (see Figure 10). The side of this smooth junction indicates which part comes above the rest. Therefore:

1. If the connection point with the external contour is only C 0 , the curve tree is re-classified as decoration. 2. If G 1 continuity is detected, we use a traversal of the suggestive contour from the connection point to the open end, on the side of the G 1 continuous curve in order to enumerate and prioritize these half edges for decomposition. 3. During the traversal of the tree, only suggestive contours that demarcate a part that is on the same side as the occluder at the root T-junction are allowed. Other contours are left-out as decorative strokes and are not processed by our algorithm.

Note that even in the case of complex suggestive contours that form a tree as in Figure 10, the suggested part is always on the same side of the curve, given that the organic shape hypothesis would otherwise be violated.

Part decomposition method

Decomposing a shape part at a given region of possible junction always involves generating two contours for closing the two resulting parts. We use the terms front closure and back closure to refer to the closure curve that closes the parts lying at the front and back, respectively, given the depth clues provided by the suggestive contours. To decompose a part, we first generate the two closure curves for all the junctions having the highest priority, using specific algorithms for each type of region of possible junction, as detailed below. If either of the resulting closure curves intersects the shape contour or if the front closure curve intersects a decoration curve, the current junction is discarded. Finally, the junctions that result in most plausible closure, as defined by the minimal sum of their closure curves' energy, are selected for the decomposition. The resulting parts are created and included in the partial depth set P according to their classification as a front or back closure curve.

Note that the two newly created parts may have overlaps between their respective closure curves, but this is valid since they are each assigned a different depth layer. To assign such depth in the case of (C, C) region of possible junction without a relative depth cue, e.g., the bottom-right petal of the flower in Figure 3, we use the convention that the largest shape part should be in front, which is often the best choice when the resulting parts are to be animated.

While inferring the closure of a part given two endpoints and the associated tangent vectors is easy (Section 4), and can be done for connecting two suggestive contours (SF, SF) and (SB, SB) regions of possible junction, the connections in the (C, SF) and (C, C) cases are much more challenging. Indeed, the best pairs of contour points in the region of possible junction zone should be computed for the front and back closure curves. Our methods for solving these two cases are presented next.

Contour / Suggestive contour (C,SF) closure

Given that we are in the case where the suggested part is on top, we compute all the possible closure curves that join the tip of the suggestive contour to the sample points on the facing contour segment in order to generate the front closure (Figure 11 (b)). We also generate all the possible closure curves joining the contour segment with the T-junction at the base of the suggestive contour tree (Figure 11 (c)). Keeping only pairs of closure curves whose tips on the contour are not farther from each other than the blending radius, we select the most plausible pair of closure curves of minimal energy using the sum of their SIMVC energies (Equation 2). This enables us to efficiently select the best pair of closure curves among the n 2 possible choices.

For this task we must define an adapted sampling rate to explore the space of possible closure curves. This is done by first computing a blending radius defined as the average of the radii at the two ends of the region of possible junctions along the Sskeleton. Based on the blending radius, corner segments (part of the curve where the curvature is larger than the blending radius) are identified (orange curve segments in Figure 11(a)). For each corner segment, sampling points are assigned at the beginning and end of the segment, and two possible tangents are associated with each curve depending on which of the two closure curves is being computed (Figure 11 (b) and (c)). Other contour parts are regularly sampled with a distance between consecutive samples equal to the half of the blending radius. Curves that intersect contours are eliminated. c) the same closing procedure is applied to the other region, therefore the suggestive contour's T-junction is used instead of its extremity; d) resulting closure curves.

For each such sample point we store the incoming (or outgoing) tangent vectors, with a small tilt outwards (or inwards) in order to avoid undesired intersection. When dealing with suggestive contours that could be considered as big cusps (Figure 12 (a)), the front closure is processed normally (Figure 12 (b)) while for the back closure, we extend the relevant transition contour (Figure 12 (c)). The transition contour is extended by following its associated S-skeleton branch until either an extra branch is encountered, or the facing contour is a neighbor of the T-junction. This produces the result exposed in Figure 12 (d).

Contour / Contour (C,C) closure

We sample the boundaries of the regions of possible junction in the same way as for the (C, SF) case. The two closure curves' extremities may be located anywhere on these segments. With n sample points on both contours, a naive method would lead to n 2 possible curves to generate for each of the parts, and thus to n 4 pairs of closure curves to evaluate. To reduce the complexity back to n 2 , we only consider the pairs of closure curves between a given pair of points.

In this case, we use a variation on the energy for selecting the most plausible pair of curves. Rather than selecting the shortest closures, we wish to favor a decomposition with an overlap that is close to the middle of the region of possible junction. Doing so ensures that curved parts such as a cat's tail is regularly decomposed regardless of the small variations in thickness. Therefore, we use the energy Ê of the two curves to select the best closing pair, defined as:

Ê =         1 + (1 -a 0 0.5 * l 0 ) 2 l 0 + (1 -a 1 0.5 * l 1 ) 2 l 1 l 0 + l 1         (E 0 SIMVC + E 1 SIMVC )
with l i = a i + b i and a i , b i the junction boundary segments arc lengths shown in Figure 13, E 0 SIMVC and E 1 SIMVC the energies of the closure curves.

We also wish to reward the use of corners over a solution with two circular arcs forming a circle since it has an energy close to zero. Thus valid closures that use a sample at a corner as an implicit end point are given priority.

2D decomposition results

We now present our decomposition results and illustrate some applications in Section 8. Our method, its results and applications are also presented in the accompanying video.

Qualitative results

Figures 1, 3, 15, 22, 25 and 26 show a variety of shape decomposition and layering results that are automatically computed by our method. In Figure 25, we reused drawings from a recent paper [START_REF] Bessmeltsev | Modeling character canvases from cartoon drawings[END_REF], showing that our method achieves the structuring and layering of such drawings without the need of any extra information, whereas a user-defined 3D skeleton was used in the original paper. Figures 1 and15 (top-right) show even more challenging cases where some of the suggestive contours form a chain of T-junctions, requiring the labeling method of Section 6.2 in order to be properly processed. Figure 26 shows results computed on cat drawings found on the web using a simple query and vectorized using Adobe Illustrator. Fig. 15. Results on drawings of a cartoonish man, a tree and a pig. The two legs of the man are seen from a special view, thus the surface contact is classified as a decorative element. Warmer colors are in the foreground.

Quantitative results

Computational times range from a few seconds for the dog head of Figure 14, which includes a number of decorative curves and only three overlapping, structural regions, to a few minutes for complex drawings such as the swan of Figure 1. See Table 1. The flower is the one of Figure 3, which shows all the decomposition steps plus the final results, and the cat is the one on Figure 22. This table enables us to emphasizes the benefits of the optimization method we proposed for contour completion (Section 4.2), enabling to reduce computational time by a factor 5 or 6 in challenging cases such as the swan and the cat.

Figure

Validation

Segmentation in depth ordered structural parts is a fundamental first step for many further applications, from editing vector drawings with robust completion of partially hidden parts, to 2D animation and sketch-based 3D modeling.

We first tested our method with two applications in mind: the conversion of the input drawing into a Vector Graphics Complex [START_REF] Dalstein | Vector graphics complexes[END_REF] that then enables easy and meaningful 2D editing, and 2D vector animation. Figure 14 shows an example of meaningful editing of a drawing. Posing and animation results are shown respectively in Figure 1 and in the supplemental video. The decomposition of the wing of the swan may not fit the perceived structure for every viewer, but wings are not known to be easily animatable in 2D.

Applications

In addition of helping in animating static sketches, our method can be used in a variety of applications. In this section, we present two of them: cardboard puppetery and part-based 3D modeling.

Cardboard puppetry

Puppetry is an art-form that has existed for a very long time. Given a set of shapes, characters can be crafted by taking the range of possible motion into account [START_REF] Megaro | Chacra: An interactive design system for rapid character crafting[END_REF]. Puppet manipulation can then either be made by manually posing puppets or by using rod-like structures as is done in traditional shadowpuppetry. However this type of puppetry requires the input parts to be simple, non-intersecting shapes. If the input itself is a complicated single sketch, then it has to be converted into small pieces to be handled by such approaches.

In our application, puppets are made of articulated parts that can be posed by a user. Once the input sketch is automatically divided into parts using our method, it can be appropriately connected and manipulated. However, though our technique provides structuring and layering information of the decomposed parts, it must be extended to provide the appropriate hinge locations in order to generate a fully connected puppet.

We propose to connect two overlapping structures by placing a hinge enabling the appropriate flawless rotation. We propose a simple heuristic to identify a consistent hinge position. For given intersecting structures, the area of intersection is computed and the maximal radius circle fitting inside this intersection is found. The hinge is then placed at the center of this circle. Figure 17 shows two intersecting shapes, the intersection region and the computed maximal radius circle.

Since our objective is to create fully-connected puppets, each extracted part should be connected to the part on which it rests. After each step of recursive part decomposition, the maximal radius circle lying in the intersection area of the extracted part along with the parent part is computed and shown as a suggested hinge position for the user. Various puppets fabricated and connected with our technique are shown in Figure 16. Maximal radius circles (black colored circles) along with hinge positions (red colored dots) are shown in the second column of Figure 16.

Part-based 3D modeling

From a given 2D sketch, several methods are able to reconstruct a corresponding 3D model. These algorithms are generally designed to support only simple curves as input. In addition to complicating the interpretation of the 3D shapes, the use of complex sketches with internal contours as input also requires special techniques to infer depth information between the model parts. We propose a method to automate this 3D modeling procedure by decomposing sketches with connected inner contours into inflatable parts that are positioned in depth afterward. Our current implementation makes use of the recent algorithm of Parakkat et al. [START_REF] Parakkat | Sketch and shade: An interactive assistant for sketching and shading[END_REF] for seeks of simplicity. Indeed implicit surfaces [START_REF] Entem | Modeling 3d animals from a side-view sketch[END_REF] would have been an excellent choice too, and would have led to smoother results. The inflation algorithm from [START_REF] Parakkat | Sketch and shade: An interactive assistant for sketching and shading[END_REF] is modified as follows:

1. The pixels lying on the outer boundary of the sketch are extracted and used to create a point set S .

2. A Delaunay triangulation of S is computed.

3. The Delaunay triangulation is restricted inside the sketch, similarly to [START_REF] Methirumangalath | A unified approach towards reconstruction of a planar point set[END_REF]. This procedure removes Delaunay triangles located outside the shape.

4. Each non-boundary triangle edge is converted to a circle and is stitched with its neighbours [START_REF] Parakkat | Sketch and shade: An interactive assistant for sketching and shading[END_REF] to generate a 3D inflation of the part.

5.

A uniform sampling is applied to smooth the reconstructed model.

Figure 18 illustrates the various steps of the inflation algorithm. Figures (a) to (e) respectively show an input sketch, its Delaunay triangulation, the removal of the outside Delaunay triangles, the mesh inflation and the result after smoothing.

The inflation algorithm is separately applied to each individual, decomposed part. In our implementation, a fast user intervention is then required to set the relative depth value of each inflated part. This simple user interaction could be automated using the depth assignment procedure presented by Entem et al. [START_REF] Entem | Modeling 3d animals from a side-view sketch[END_REF]. Figure 19 shows several sketches with their 3D reconstructions. It has to be noted that, since the occluded legs (cat and rabbit) are anatomically incorrect, the symmetric copies of the foreground legs have been used to create the 3D models.

Table 2 shows the time taken for creating 3D models and assigning depths. The generated shapes assume circular limbs and do not include more complex anatomic details. Additional user interaction would be required to improve the quality of the final shapes. Table 2. Time taken for 3D modeling of parts and their depth arrangement.

Discussion

Our method for structuring complex drawings performs as expected in most cases. We point out that once a drawing is processed, the union of the extracted parts does not necessarily exactly correspond to the initial outline since the blending between parts is not conserved. However, it is very similar and it would be possible to retrieve a similar outline by representing the parts' contours as iso-contours of 2D scalar fields and blending them together. Scalar fields with skeleton could also allow for easy directional rescaling of structural parts to allow for illusory 3D rotations. For instance, this extension could be used to improve the animation of our swan's wings.

In some cases, a valid drawing may be ambiguous and gives rise to several different interpretations. This is the case for the example in Figure 20, where the shape could either be interpreted as a boxing glove (b) or as a snail head protruding out of the shell (c). Our method will output a single result in such cases, the one in (c), because of the way we process complex suggestive contours. Some curves that would be processed naturally by a human as contours are not processed when there is no T-junction such as for the beak of the bird in Figure 1.

Lastly, similarly to the metric in [START_REF] Liu | A part-aware surface metric for shape analysis[END_REF], our d SSI metric could also be used to define a distance between two points of the contour, which we would define as the d SSI distance between their two corresponding S-skeleton's vertices. In future work we wish to explore the possible applications of this new metric to contour drawings.

Comparison with previous work

The closest work we can compare with is SmoothSketch [START_REF] Karpenko | Smoothsketch: 3d free-form shapes from complex sketches[END_REF]. While they look for a plausible completion of the hidden contour hinted by cusps, we instead use the facing contour to smoothly wrap a curve around the hypothetical 3D shape as shown in Figure 21. We emphasize that the segment of our hidden closure that is near the T-junction is a plausible hidden contour. Thus, our method could benefit figural completion of cusps in SmoothSketch's failure cases. However, we think that both this algorithm and ours should be used in a complete application since hidden contour completion is more meaningful than our decomposition for the case of cusps that are small relative to the local thickness of the shape, and specific cases such as the swan's wing.

The recursivity of our decomposition hides some perceptual information such as similarity, grouping, symmetry. In the paw example in Figure 21(c,d), we perceive the similarity and symmetry of the fingers. However our algorithm first decomposes the foreground finger, and considers the two others as a whole, thus the background finger is eventually perceived as big as the middle one once the first is extracted. Designing a global method from our recursive one is a non trivial problem since the closures are interdependent in many cases.

We also show results on inputs from [START_REF] Entem | Modeling 3d animals from a side-view sketch[END_REF] in Figure 22 (top, middle). Though the segmentation is similar, our initialization step cannot complete complex hidden contours. This limitation would locally require a completion similar to the one used in [START_REF] Sýkora | Ink-and-ray: Bas-relief meshes for adding global illumination effects to hand-drawn characters[END_REF] but it is non trivial to combine this method with figural completion to be able to complete parts with distinct visible regions in the absence of distinct similarities between these regions such as color or grouping annotations. However our algorithm tackles the case of parts hinted by single suggestive contours as shown in Figure 22 (bottom).

Limitations

Even though our method gives good results in most cases, we have a few limitations as well. One main problem is the cyclic arrangement of parts over one another. Figure 23(a) shows an example in which the petals are overlapping in a cyclic fashion. In this case, layering cannot be done using the proposed method and our part decomposition phase fails. Since we are assuming that the occlusion results in either T-junctions or cusps, the more complex junctions are not processed in the current system.

Many limitations are found in the initialization step, when drawings carry ambiguities at curve intersections, notably when T-junctions are not well defined either due to special view or surface contact as in Figure 23 (b,c) and Figure 26 (2,3), or misleading because the hypothetical occluded contour is in fact a texture change as in Figure 23 (e, left). The latter limitation can be manually worked around by erasing a part of the stroke as in Figure 23 (e, right).

Future Work

Our current method can be improved in various ways. One of them is to include user interventions to solve ambiguous cases (recognize whether two concentric circles represent two spheres or a torus), and to do assisted segmentation as in [START_REF] Sýkora | Ink-and-ray: Bas-relief meshes for adding global illumination effects to hand-drawn characters[END_REF]. Another interesting direction is to use decorative curves as suggestive contours. Figure 24 shows a case in which the decorative curve represents a suggestive curve and our method would ignore it. In terms of applications, a first interesting avenue for future work would be to extend our work from animated puppets to 2D vector animation, in order to produce animated results such as the manually created flying swam example at the bottom of Figure 1 (c). To achieve this, in addition to the method for com-puting hinges we already discussed, an automatic mechanism to clean and blend 2D contours of animated subshapes should be provided. This could be done with the help of 2D implicit contours and specially designed combination operators for curves. Note that beyond local blending, the main challenge here is to automatically remove the non-salient parts of the contours of overlapping parts, while ensuring temporal coherence. In this context, the 3D reconstructions we already provided could serve as a 3D intermediate representation. It could also allow us to apply out-of-plane rotations to limbs and to change the viewpoint in animated sketches, two cases in which the silhouettes and occlusions between shape parts need to be recomputed.

Lastly, 3D shape reconstruction from a 2D sketch would benefit from automatic depth inference, which we could do using the amount of overlap between shape parts. Decoration curves could then be projected back onto the 3D model. Moreover, our current 3D reconstruction method could be improved by smoothly blending parts thanks to implicit modeling, similarly to what was done in [START_REF] Entem | Modeling 3d animals from a side-view sketch[END_REF][START_REF] Bessmeltsev | Modeling character canvases from cartoon drawings[END_REF] in a more constrained case.

Conclusion

We presented the first automatic method able to use complex inner contours in the analysis and recursive decomposition of drawings that represent smooth shapes. Our decomposition method outputs a structure of closed 2D shapes layered in depth. It relies on the inference and progressive refinement of a partial depth tree to store depth information. A new metric Fig. 22. Results on two drawings from [START_REF] Entem | Modeling 3d animals from a side-view sketch[END_REF] and the third is the second drawing minus two suggestive contours, a case that their algorithm could not handle. Red dotted curves are contours that make our initialization stage fail (they are manually removed before further processing). computed along a skeleton was proposed to detect salient parts of complex drawings including internal silhouette curves. We introduced a new, perception-based criterion for selecting the most salient possible junction regions, prioritizing them, and using them to recursively segment a shape into parts. An efficient implementation of curve closures using a variation of the Scale-Invariant MVC functional was defined for closing the extracted parts, hidden or salient. Lastly, we managed to keep most parameters scale-invariant, enabling us to achieve structural decomposition of drawings with different resolutions of features.

Many applications can benefit from our method. As we have illustrated, it enables organic sketches to be easily edited in a meaningful way. Subdivision and depth layering makes the model ready for simple 2D animations. As discussed in Section 8, the decomposition algorithm aids in part-based 3D shape modeling, a domain where complex sketches with a variety of Fig. 24. An input where a suggestive contour is not connected to the outer contour and thus misclassified as a decorative element in our initializaton step. We would like to use it as a possible segment of a foreground closure in future works. Fig. 25. Results on three drawings also used in [START_REF] Bessmeltsev | Modeling character canvases from cartoon drawings[END_REF], except that we removed the hat of the character. Warmer colors are in the foreground.

internal contours were never considered so far. As future work, we also plan to further ease 2D animation of complex sketches by developing an automatic mechanism to locally clean and blend part contours at each animation step, in order to enable smooth transitions between silhouette curves where and when needed.

Fig. 1 .

 1 Fig. 1. An illustration of the steps of our automatic structuring and layering system. (a) The input drawing. (b) Structure analysis and part-completion estimate the constituent parts and their layering. The arrows represent the partial depth ordering ("over" relation). (c) Manipulation of the depth ordering as desired (top), followed by the union of these elements composed with the original internal contours to produce a new drawing (bottom).

Fig. 2 .

 2 Fig. 2. Stroke classification. Red curves are suggestive contours; green curves are hair; blue and purple curves are part of non-hair decorative elements. The remaining contours, in black, are part of the external silhouettes of shape parts.

Fig. 4 .

 4 Fig.4. To optimize the computation of our SIMVC curves, we precompute a table of the energies and associated parameters that the curve can take as a function of the two angles θ and ϕ defined in (a). We illustrate the sampled function SIMVC energy values and compare them with the MEC energy that minimized total curvature.

Fig. 5 .

 5 Fig. 5. (a) A maximal negative curvature (in orange) suggests the presence of a junction boundary on the contour but its counter-part boundary (in blue) does not exhibit any maximum, which avoids the detection of a boundary. (b) S-skeleton of a part (in blue), i.e. Medial-Axis considering internal silhouettes: the lower structural part is not captured, while the middle part at the top is. (c) Processed Medial-Axis of the external contour of (b), where no branch is associated with the top structural part.

Fig. 6 .

 6 Fig. 6. Example of SSI for points M A (resp. M B ) constructed by measuring the local reaches r k A (resp. r k B ) in the kth direction of a uniformly sampled set of m directions (here m = 3). Some discontinuities of reach are present and shown here as green arrows.

Fig. 7 .

 7 Fig. 7. (a) Computed d SSI between vertices of each edge of the S-skeleton of a part, and represented for each skeleton edge as the size of an orthogonal segment passing through the center of this edge (values are squared for visibility). (b) regions of possible junction (in grey).

Fig. 8 .

 8 Fig. 8. (a) A region of possible junction misidentified as two junctions due to radial symmetricity of the shape at the center of the transition (in near radial directions to the Medial-Axis). Both are merged before further processing. (b) A more common case of region of possible junction with no merging necessary.

Fig. 9 .

 9 Fig. 9. of possible junction: (SF, SF) in dark blue, (SB, SB) in cyan, (C, SF) in green, (C, C) in orange, discarded regions in pink.

Fig. 11 .

 11 Fig.11. Part decomposition at a region of possible junction. a) junction boundaries in this case are described by an external contour at the bottom and a red suggestive contour at the top. The external contour is uniformly sampled into a set of points and their associated pair of tangents. Corner segments (orange) samples are given two points instead of one to handle proper connection where curvature is the highest. b) all the closure curves corresponding to pairs of one sample point from the contour and the suggestive contour extremity are computed and their plausibility is evaluated for closing the rightmost part. Curves that intersect contours are eliminated. c) the same closing procedure is applied to the other region, therefore the suggestive contour's T-junction is used instead of its extremity; d) resulting closure curves.

Fig. 12 .

 12 Fig. 12. (a) Example of a suggestive contour comparable to a cusp requiring a (C,SF) closure. (b) The front closure unknown end-point is searched along the blue contour part defined by the identified region of possible junction. (c) The transition is extended for the back closure. (d) Result of the decomposition with parts sharing a wide part of contour.

Fig. 13 .

 13 Fig.[START_REF] Larsson | Identifying perceptually salient features on 2d shapes[END_REF]. For (C, C) closures we define a new coefficient for Ē based on the samples' positions relative to their respective sampling contours as defined in Section 6.5.

Fig. 14 .

 14 Fig. 14. Dog head example, and some editing by manipulating the extracted parts.

Fig. 16 .

 16 Fig.[START_REF] Pessoa | Filling-in: From perceptual completion to cortical reorganization[END_REF]. Fabrication of articulated puppets from a single sketch: With a simple extension, we can use our system to suggest hinge positions between appropriate parts in order to fabricate cardboard puppets. This figure shows the input sketches and hinge positions along with various poses of puppets we fabricated from them.

Fig. 17 .

 17 Fig. 17. (left) Two sample intersecting curves, (middle) intersection region and (right) maximum radius circle lying inside the area of intersection.

Fig. 18 .

 18 Fig. 18. (a) Input sketch, (b) Delaunay triangulation, (c) Result after restricted Delaunay, (d) triangulation inflation, (e) final 3D model after uniform sampling.

Figure

  Figure Fox Bunny Character Cat Modeling time(secs) 4.31 4.09 3.997 5.162 Ordering time(secs) 75 96 20 92

Fig. 19 .

 19 Fig.[START_REF] Mi | Abstraction of 2d shapes in terms of parts[END_REF]. 3D modeling from a single, complex organic sketch. the resulting model is first depicted from the drawing viewpoint and then from various views.

Fig. 20 .

 20 Fig. 20. An ambiguity of interpretation. Our algorithm can only produce the result (c) while (b) would also be a perceptually plausible result.

Fig. 21 .

 21 Fig. 21. Comparison of our results (b,d) with SmoothSketch's failure cases (a,c).

Fig. 23 .

 23 Fig. 23. Different limitation cases of the initialization step (b, c, d, e) and recursive decomposition algorithm (a).

Fig. 26 .

 26 Fig.[START_REF] Cordier | Free-form sketching of self-occluding objects[END_REF]. Results for three drawings found on the first results page of Google Images with the following search terms: "cat line drawing". The second result has been produced with salience threshold parameter that is more sensitive than the one used for all the other examples. The third example is subject to three limitations: 1) non trivial hidden part completion; 2) badly defined T-junction; 3) 4-valence vertex.

Table 1 .

 1 Computational times without (T1) versus with (T2) the optimization of contour completion described in Section 4.2. It can be seen that our optimization method enables us to reduce computational time by a factor of 3 to 6.

	Dog Flower Swan Cat
	T1 (in seconds) 19.1 26.4	708.1 520.1
	T2 (in seconds) 7.2	9.8	134.0 85.0

Acknowledgments

A preliminary version of this paper was published at the Expressive 2018 conference. We wish to thank all the anonymous reviewers of our work for their valuable comments. Many thanks to Michiel van de Panne and to John Hughes for proofreading previous versions of ths paper. This work was partly funded by the ERC advanced grant EXPRESSIVE.