Claude Cadoz
email: claude.cadoz@imag.fr

Annie Luciani
email: annie.luciani@imag.fr

Jerome Villeneuve
email: jerome.villeneuve@imag.fr

Alexandros Kontogeorgakopoulos
email: akontogeorgakopolos@cardiffmet.ac.uk

CSAD Iannis Zannos
email: zannos@gmail.com

Jerome Villeneuve

Presence, Materiality Tangibility

Jérôme Villeneuve

Tangibility

Keywords: Presence, Materiality, Reality in Artistic Creation with Digital Technology

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

ABSTRACT

The democratization of Computer Arts and Computer Music has, due to dematerialization (virtualization) consequence of digital technologies, considerably widened the boundaries of creativity. As we are now entering a second phase that has been labeled "post-digital", we are called to reconcile this openness with notions such as embodiment, presence, enaction and tangibility. These notions are in our view inherently linked to creativity.

Here we outline some approaches to this problem under development within the "European Art-Science-Technology Network" (EASTN 1 ). Several areas of artistic creation are represented (Music, Animation, Multisensory Arts, Architecture, Fine Arts, Graphic communication, etc.). A main objective of this network is to establish common grounds through collaborative reflection and work on the above notions, using the concept of tangibility as a focal point. In this paper we describe several different approaches to the tangibility, in relation to concepts such as reality, materiality, objectivity, presence, concreteness, etc. and their antonyms. Our objective is to open a debate on tangibility, in the belief that it has a strong unifying potential but is also at the same time presents challenging and difficult to define. Here we present some initial thoughts on this topic in a first effort to bring together the approaches that arise from the different practices and projects developed within the partner institutions involved in the EASTN network.

CONTEXT

The European Art-Science-Technology Network, which is supported by the European Union under its Culture Program2 , arose from the initiative of several European institutions involved in research, technological development, creation and teaching in the field of digital technologies applied to artistic creation. These institutions are: The ACROE and the ICA Laboratory (Grenoble -

TO BE OR NOT TO BE … "TANGIBLE" 2.1 Human -Computer -Environment interactions

Our proposed starting point is the proposition that digital technologies deal with information, not with matter in a physical sense. While information requires physical media to be created, processed, transmitted, stored and preserved, it is regarded as representing something different than these media. In other words, we can consider digital computing devices as belonging to a world of information carried by symbols, "digital symbols" or bits, and processed by operations, boolean operators, applied on these symbols. This makes out the abstract and intangible character of the digital, since "touching" symbols is not possible and lies outside the metaphorical framework of the digital. Even if these symbols and operations are carried by matter (electrons, electric wires, electronic circuits), we can only experience their function and evolution indirectly (if at all). And in order to use them to achieve a predefined goal, we need to apply arbitrarily defined correspondences between the logical / symbolic and the physical / material. The issue of tangibility arises from this condition.

In order to act on the computer, the human has no other means than his/her voice, body, and gestures. Devices are needed in a way to establish links between the physical phenomena produced by voice or by gestures and the symbols of the digital domain.

The use of the results may be of two different natures. It may be direct, involving the human senses. In this case, there is a necessity for devices that establish links between digital symbols and natural perception: the hearing, the sight and the tactilo-proprio-kinesthetic (haptic) senses. It may also be indirect, or more precisely resulting in a physical transformation of something in the human's environment. In this case, the digital phenomena must be linked to devices that control energy in motors (actuators) and engines that act, modify, transform the matter in our environment. And finally -but this cannot be done entirely without the help of the human, that is to say without some links of the first type evoked above -digital processes may be controlled or at least influenced by phenomena of the physical environment. In this case, devices are needed to link the phenomena to the digital symbols. These devices are called sensors. Sensors, display devices and actuators are then necessary and complementary basic components of any system involving computer for human-computer-environment interactions.

The "interfaces" going from human action or physical environment to digital world and from digital world to human senses or to physical world, can be configured in various ways. Some characteristic cases are: -The computer and interfaces can be configured to imitate in all respects the behavior of a physical object, such as a musical instrument or a material object that we can animate. This is the case in the "Multisensory and Interactive Simulation of Physical Objects" presented below. We can say that the computer here plays the role of an "instrument". Strictly speaking, this device is not an instrument in the physical sense since it treats symbols. One could more appropriately characterize it as "metaphorical insttument". -The computer can act as tool for creating models of a physical environment in order to support creation and manipulation of abstractions. In this case the digital tool is used in a manner analogous to earlier nondigital ones, such as the symbolic techniques that are used for example in mathematics to solve equations or to perform calculations. Graphical programming environments as well as WIMP based software are commonly used as interfaces for this type of use. This type of tool can support and stimulate work on the conceptual level by providing different types of graphic representations as well as the possibility to manipulate those representations in order to configure them. In contrast to the first configuration described above, this case here cannot be metaphorically compared to an "instrument" for direct interaction with the senses, but is more akin to a tool for representing abstractions and manipulating these representat ions that accompanies and supports thinking about these abstractions. -In a third case, physical objects can be equipped with sensors and actuators to create self contained systems with their own properties and behavior, with which the human may interact. The sensors and actuators being connected to the computer are respectively inputs and outputs to and from digital processes. An underlying limitation of this configuration is that only the interface is tangible, while the processes and concepts that are specified and controlled remain hidden. -A further case, can be represented as a virtual world built inside the computer superimposed to the real world through specific visual display devices. These to see the real and the virtual worlds at the same time while actions are detected in relation with someone position or movement in the real world and then used to create or modify the virtual one. This is called "Augmented Reality" (see for example [1][2]). -And finally, the computer can control motors and various actuators of machines and devices acting on the real physical world and even transforming it.

Here, by involving robots, machine-tools, milling machines, multi-axis CNC machines and others, or 3D printers and plotters, the computer is used to act on or to transform the physical world, but also to build sophisticated objects that can then be used as instruments, tools, parts of machine, etc. and interact with human, computer or the both. These examples, can be classified into two groups, which are in a symmetrical relation to each other: The first is related to the science and technology of Human Computer Interaction, including technologies of Virtual and Augmented Reality. In this situation, the human is "real" and is interacting with the computer, which then is an "artificial world". The second is related to Robotics and Artificial Intelligence, where we can say that the computer is placed on a par with the human and plays a role, with increased functionality and performance, comparable to that of an "artificial human" interacting with the environment. These two complementary groups are pro-posed here as the two main metaphors for the analysis of man-computer-environment interactions in the present context.

We can summarize this as a triangular system between human, computer and physical environment, and with the three kinds of resulting interactions. Even if the effective and various situations involving computers are generally more complex, we can say that they are always understandable as more or less complex networks made of this basic mesh. And then we have here the global frame to approach and discuss the question of Tangibility.

A cloud of terms and concepts

Tangibility

In its simplest sense, tangibility is the property of an entity to be accessible to the sense of touch. This indicates two aspects: touch is perception, but also action. The sense of touch develops in the action of touch. In order to perceive the shape of objects, their weight, their texture, the way in which they can be shaped or deformed, we must interact with them. The "pure" Touch is a borderline case and very reduced sense. But there is also a broader sense. Figuratively, in common usage, a thing is tangible if it is real, not only imaginary, if it is defined and not vague or elusive. In the legal field, a property is tangible if it has an actual physical existence, as real estate or chattels, and therefore capable of being assigned a value in monetary terms.

In the domain of Human Computer Interaction, the term Tangibility appeared at the end of the 1990's in the expression "Tangible User Interfaces". In their paper, Ishii and Elmer [START_REF] Ishii | Tangible Bits: Towards Seamless Interfaces between People, Bits, and Atoms[END_REF] introduced the notion of "Tangible Bits", allowing users "to grasp and manipulate bits (…) by coupling the bits with everyday physical objects". This is of course a metaphor since, as said before, bits are not objects but symbols. It is important to see here that, (i) this is the everyday physical object that is tangible, not the bits, (ii) this object is not "coupled" with bits, but a (reduced) part of its properties and movements are detected (thanks to sensors) and used as input of the computer.

Reality, Materiality, Objectivity, Presence, Concretnesse, etc.

The term "Tangibility" is attractive because it is clearly an expression of a need that is not satisfied with the computer. But beyond the "buzz-word" there are important questions, and because it is polysemic it is rich and promising. It is sufficient, to give an idea of its richness, to mention some elements of the "cloud" of words to which it is often associated. A simple list of terms appearing as synonyms, and a list of opposing pairs of antonymic words, allows getting an idea.

Reality, materiality, objectivity, presence, concreteness, just to name a few, are often encountered as synonyms. But it is easy to note that they are not equivalent. For example, one thing can be real (a feeling, an emotion, suffering or joy) without being material or concrete. One thing may be present, or at least may seem present, without being real: the successful synthesis of a digital sound, for example the sound of a vibrating string with a physical modeling simulation may give the feeling, or even the certainty that a string is present where we listen to the sound, while there is no corresponding physical reality. But perhaps the term "re-presentation" (to present again) is more convenient here! It is also interesting to place each of these terms in front of those who are supposed to be their antonym. We can then discover some inherent semantic difficulties. For example, "subjective" is not necessarily synonymous with "non-objective"! And of course, crossing of couple of terms sometimes is completely meaningless: for example, "non-material", as antonym of "material", is not equivalent to "abstract" as antonym of "concrete".

It is also interesting to consider some pairs of terms, associated in some expressions, where we cannot determine if they are mutually qualifying or are antonyms. The most dramatic example (as one of the authors has shown in his book "Réalités Virtuelles" [START_REF] Cadoz | Les Réalités Virtuelles[END_REF] is "Virtual Reality" itself. It is indeed impossible (because the two uses exist) to determine whether the virtuality is here a qualifier of certain realities or if it is used as an antinomy of reality. In this case, this expression is an oxymoron, i.e. an expression which is contradictory in itself, something like "to be AND not to be" at the same time!

Enaction

It is now well understood that action generally goes with perception (and in numerous case is impossible without perception) and conversely, that perception needs almost always action. It is obvious for the gestural channel, which is both a channel for acting and sensing (by the touch and the tactilo-proprio-kinesthetic, TPK sense) and more, that the TPK sense is intrinsically an actionperception loop [START_REF] Cadoz | Le geste, canal de communication homme/machine. La communication instrumentale[END_REF]. This is a reason why we can say that the "touch" is enactive. But the enaction concept [START_REF] Bruner | Toward a theory of instruction[END_REF][START_REF] Varela | The Embodied Mind[END_REF][START_REF] Luciani | Enaction and Enactive Interfaces: a Handbook of Terms[END_REF] is wider: It concerns not only the intimate touch loop, but also, at different scales, the loops involving gestural action, auditory perception, gestural action and visual perception, gestural action and multisensory perception.

The enaction concept is then totally relevant in the discussion about tangibility. Thus, we must admit that the concept is rich and complex and that it is not possible to give an initial unambiguous definition. The meaning of "Tangibility" is a work in progress, under the large and recent development of digital technologies. We propose in the next section to try to "make this notion more tangible" by providing several specific insights based on the works of different teams and institutions, some on them being in relation with the present EASTN network.

DIFFERENT APPROACHES TO TAN-GIBILITY

Simulated matter -Evoked matter

By Annie Luciana -ICA Lab -Grenoble Institute of Technology (France)

In [START_REF] Luciani | Un nouvel espace de création pour les arts visuels : la matière simulée interactive[END_REF] Annie Luciana introduces the term of "simulated matter" as a new field to be explored by artistic creation. She showed that, since the first phase of real phenomenon observation or capture aiming to digitally represent it, a substantial reduction occurs: only specific aspects of this phenomenon, those that can actually be captured or analyzed according to specific fields of science, are selected and represented: for instance, the audio signal, the 3D spatial form, the displacement of a body into space, etc. This remark seems obvious. But it means no less than all other properties involved in the phenomenological experience of the human being in its relation with the real world were lost. Among them, a crucial one is the "physical matter", out of which things are made. Beside, the very new expansion of the possibilities open by digital instruments, they dramatically shared a common property that is "an absence", and an absence of what? "The true absence of the physical matter", as exemplified by most of 3D shape modeling software or by most of Digital Musical Instruments.

When going back from real world to perception and sensitivity by means of "re-sensorialization", this "physical matter lost" leads to two opposite tracks:

One can rematerialize 3D forms thanks to a real physical matter, as done in industrial processes such as Computer Aided Design and Manufacturing and its wide popularization through FabLabs trends. We can speak of "shaping", i.e. a mapping process of the virtual dematerialized 3D shape onto a real physical matter. This is usually done using robots to shape a given physical matter with virtual shapes. No doubt that such processes enable to considerably enlarge the variety of shapes that can be produced "by ourselves" and are a new support for artistic creation linking imaginary virtual shapes and tangible experiences of them.

Another is to integrate the modeling of a physical matter itself within the virtual objects design process. In this case, the matter is virtual, digitally simulated, and processes of sensorialization are then required which necessarily introduce: the virtual matter gestural perception, allowing to manipulate it as if it is real by the means of adequate haptic feedback systems; the visual perception of the behaviors of this virtual matter, rendering as precisely as possible dynamic properties; and the auditory perception of the acoustical matter behaviors. Here is the notion of "simulated matter", shifting the virtual digital process from "what is this thing" to "in what is this thing". However, in such a case, going back to physical matter is, if not impossible, terribly limitative, stamping such process as very different to the materializing process adopted in the first track presented above.

The philosophical arguments for the benefit of the concept of "simulated matter" are two. First, A. Luciani shows in [START_REF] Luciani | Un nouvel espace de création pour les arts visuels : la matière simulée interactive[END_REF][START_REF] Luciani | Dynamics as a common criterion to enhance the sense of Presence in Virtual environments[END_REF][START_REF] Luciani | PRESENCE: The Sense of Believability of Inaccessible Worlds[END_REF] that just a little drop of simulated matter enables to strongly evocate its materiality and, that it is not necessary to model this matter with a total physicist realism to trigger the sense of tangibility and of believability of a possible real thing. Just a kind of "thingy" is sufficient, the question being how can we discover it? Within the technical question of "simulated matter" is nested another concept, more in the field of cognition, called "evoked matter": what could be the minimum of evoked matter able to trigger the sense of believability of virtual artifacts? What could be the nature of haptic sensorialization -and more multisensory rendering -to render cognitively tangible something that it is objectively dematerialized? From what elements can we speak about "cognitive tangibility" instead of "real tangibility"? Many exciting questions that the technological as well as cognitive research will allow us to discover.

Secondly, behind this question, is the central concern for artistic creation which is of the modeling process, in other words in the discovery, the writing, the composition processes, etc. A. Luciani then assumes in [START_REF] Luciani | Dynamics as a common criterion to enhance the sense of Presence in Virtual environments[END_REF] that the notion of "simulated matter" and "evoked matter" truly opens very new ways for artistic creation, as it allows at the same time to rehabilitate the necessity of the tangibility supported by the feeling of "in what is this thing" with the infinity of the space of the virtual simulated matter, which can become a feature to be written, modeled, composed.

Multisensory and Interactive Simulation of Physical Objects

By Claude Cadoz -ACROE -Grenoble (France)

The computer is used in this approach of the ACROE-ICA Lab. in Grenoble, as a means to simulate the physical world in such a way that the human can interact with this virtual world in the same way as with the real world. If we focus on particular objects like instruments or tools for artistic creation (music, visual arts, etc.), this leads firstly to introduce devices that allow to establishing links between the gestures and digital symbols, and at the same time devices that establish links between digital symbols and hearing, sight, perception by the fingers, the hands and the body. The interaction through the gesture, which allows both emitting and receiving of information, requires special devices, which are today called gestural force feedback systems. It also requires dedicated devices to elaborate acoustic phenomena and also visible phenomena from digital electronic phenomena. They are digital / analogue converters followed by loud speakers, visual display devices, etc.

It is also necessary to program the computer to calculate, as a result of the gestural actions and with the required speed, digital sequences corresponding to mechanical, acoustic and visual phenomena. Moreover, these calculations must be achieved in such a way that all resulting perceptible phenomena behave exactly like in the case of a real physical object. This object may be defined according to a real existing object, but it may also be a chimera.

This approach is the subject of the work of ACROE and ICA laboratory (Grenoble Institute of Technology) for several decades. The recent developments in this approach put together high performance force-feedback devices developed by ACROE-ICA (the Gamma Con-sole©, a force feedback system with 24 degrees of freedom) and the GENESIS environment for creating models in the CORDIS-ANIMA language, to simulate and to play them in real time [START_REF] Cadoz | A Modular Feedback Keyboard Design[END_REF][START_REF] Cadoz | CORDIS-ANIMA : a modeling and simulation system for sound and image synthesis[END_REF][START_REF] Castagne | GENESIS: A Friendly Musician-Oriented Environment for Mass-Interaction Physical Modelling[END_REF][START_REF] Leonard | Interactive Physical Design and Haptic Playing of Virtual Musical Instruments[END_REF].

In this situation, it is legitimate to speak of tangibility if we consider the elementary meaning of this word, which is to "touch" the things. Indeed, using a forcefeedback device, we actually touch matter: the one of the mechanical part of the device. Nevertheless, what is real and material is the device, but not the "object" with which we are interacting in this multisensory way. Actually, this object doesn't exist. However, what is very important here, since it is in fact the principle and the objective of this approach, is that we have the sensation of presence of this virtual object. For example, when we simulate a vibrating string that we pluck with a simulated plectrum through a force-feedback key, producing then the sound, the moving image and the haptic feeling in our fingers, we have the conviction that the object is here, is present here.

The next question may then be: why is this important? What's the point? In fact, when we are confident that the object we have in front of us is real, that it is not only something coming from our imagination, then we are willing to consider it as a means, a tool that will help us to objectify and to express precisely our thoughts and our imagination for others. This is the way in which we behave with real instruments: as objects that are external to us and through which, when we play, we can create expressive sounds. It is under these conditions of reality and materiality that the instrument can become a kind of organic extension of us.

The principle of Multisensory and Interactive Simulation of Physical Objects is then to try to implement all conditions, whereas we are interacting with a dynamic system of symbols, to procure the conviction that we are interacting with a real object. This is not easily achievable. Indeed, if the conditions of interaction with the system are too abstract, too far away from what our gestural bodies and our sense organs are used to treat, that is at a minimum concrete physical phenomena directly producible by our gesture or perceivable by our senses, this incorporation, this embodiment does not happen, and the relationship with digital objects becomes totally different or incompatible with the finesse and richness that are necessary for expressiveness and sensitivity.

And finally, what emerges from this is that the sense of presence is not obviously related to reality. A subtle science is: how, using artifacts, to give the feeling of presence or the belief that what is in front of us is real, even if it is not true, allowing then in particular an embodiment, this last being at its turn so important and so necessary in a certain (large) part of the (artistic) creation process?

Another word can be introduced in the discussion: Objectivity. It was implicit in the previous arguments as soon as we said that we need to be sure that what we are confronted with is not only from our imagination, is not purely subjective. In order to get this, a first strategy of our cognitive system is to verify a permanency of the things while we are changing and acting ourselves.

So by comparing our voluntary actions and what varies and what remains invariant in the phenomena that we perceive in consequence of our actions, we can conclude that we have or not an object, in front of us, in an environment which is objective. This is what the Virtual Reality has achieved at its beginning (in the 1990's) in particular with the first immersive 3D visual displays, associated with 3D body movements sensors (head-mounted screen for example). While the person is moving, the computer recalculates the 3D scene in order to give to the observer the feeling that this scene is outside of him (objective) and that he is moving inside it.

In such a situation, even if the sense of presence is highly increased when we use gestural devices with force feedback, these devices are not absolutely necessary.

A large number of other strategies, often much more simple, can work very well. For example, it was already the case with the simple technique of perspective in classic drawing and painting. What is working here is a specific consistency inherent to the visual stimuli that map with those we would have in front of a real scene. If we accept to speak here yet of tangibility, we must consider that to touch the matter is not always necessary for it.

In fact, in the works of ACROE-ICA and in particular with the GENESIS software environment for musical creation, such sensory consistency is used, or more generally the paradigm of "physical metaphor". In the part of the user interface used to build the virtual objects, we allow to do this through a direct graphic manipulation of the components of the physical model on the screen. The screen is then a metaphor of a physical worktable.

Despite the fact that, in this case, there is no touch, it is this kind of "tangibility" which allows supporting and stimulating the conception, creation and construction of these "objects".

Designing and Making Digital/Physical Things by Physical/Digital Means

By Alexandros Kontogeorgakopoulos -CSAD (Cardiff School for Art and Design) -Cardiff -Wales. The world of fabrication and digital arts are nowadays easily combined and mixed through the digital fabrication revolution and the digital computation revolution [START_REF] Gershenfeld | Fab: the coming revolution on your desktop--from personal computers to personal fabrication[END_REF]: in the same moment and place we can design and build the physical object, the hardware, the software and through transducers (sensors and actuators) link the physical and the virtual world dynamically. Our belief is that the digital artists should be exposed in the physical and virtual world simultaneously. Our aim is to bring the virtual even closer together with the physical workbench.

Particularly Cardiff School of Art and Design (CSAD) strongly emphasizes and celebrates the fact that the artist (and designer) is able today probably for the first time in history to easily design, fabricate and experience simultaneously physical systems and virtual systems with the help of computer tools. Digital fabrication gives access to everyone to design and produce tangible objects. Machines for personal digital fabrication include CNC milling machines, laser cutters, 3D printers and plotters. Digital fabrication laboratories (from specialized workshops to the widespread Fab Lab network 3 ) facilitated significantly the bridge between the tangible and the intangible. Therefore the concept of tangibility is deeply related to the harmonious combination of bits and atoms in the artistic work and in the workflow: how (what and why) we make physical things digitally and how (what and why) we make digital things physically. The passage from data to things and from things to data can open up many new possibilities in artistic creation with digital technology. An interesting research, which employs digital fabrication technologies for the design and the fabrication of acoustic instruments, is the 3D printed flute [START_REF] Zoran | The 3D Printed Flute: Digital Fabrication and Design of Musical Instruments[END_REF]. Another project, which combines both 3D printed wind instruments augmented with electronic sensors and visualization algorithms, is The God Article project [START_REF] O'connell | The God Article[END_REF]. An interactive composition is currently under development by Alexandros Kontogeorgakopoulos which uses the idiosyncrasies of both the physical and the digital part of the developed wind instrument. Other examples of CSAD's creative and research projects so far are related to active haptic interactions (touch immaterial things), augmented realities (see immaterial things), sound synthesis (listen to immaterial sounds) and digital fabrication (make material things digitally) [START_REF] Berdahl | Engraving-Hammering-Casting: Exploring the Ergotic Medium for Live Musical Performance[END_REF].

We believe that materiality and virtuality will converge in our near future (if they have not converged yet!) and therefore a different concept about tangibility will emerge. It is the artists and designers roles to explore creatively through their work the interactions we have as humans with digital and physical objects, gain a sensory understanding of how code and matter can be formed and manipulated by the creative mind and the skillful hand and what tangibility means in our society today. The Fab Lab movement introduced by Neil Gershenfield [START_REF] Gershenfeld | Fab: the coming revolution on your desktop--from personal computers to personal fabrication[END_REF][START_REF] Walter-Herrmann | Fab Lab: of Machines, Makers and Inventors[END_REF] is not only a revolution related manufacturing and personal fabrication but also a means to rethink about tangibility in the digital arts.

Immediacy -intimacy and manipulation -Extension of the Tangibility metaphor

By Iannis Zannos -Ionian University -Corfu -Greece. Considering the sense of Tangible as that which can be perceived through touch, and that which can be touched, it is possible to identify two aspects which distinguish the idea of tangibility from concepts related to the other senses. These aspects are: "immediacy" (or "intimacy") and "manipulation".

The first aspect, immediacy or intimacy refers to the fact that the sense of touch relies on immediate physical contact with the perceived object, as opposed to senses such as hearing, vision or smell, which connect to the object via an intermediate medium/channel over distance. In that sense, tangibility gives us the most intimate experience of an object. Analyzing this further, one observes that experiencing objects through touch requires a different type of focusing of attention than with other senses. To know an object through touch involves active explora-3 https://www.fablabs.io/ tion of the object over time through physical movement. While vision and hearing also involve time and active focus of attention, the type of attention and the rate of flow as well as the type of information received through these senses is different than that of touch. Thus, an objective of research in tangibility is to specify these differences in greater detail and to characterize the type of information as well as the flow mechanism for receiving that information through the different sense channels.

The second aspect, "manipulation", is one in which perhaps tangibility distinguishes itself most strongly from all other modalities of the senses. Touching is our primary means of effecting changes on objects in our environment. Also, touching is the only modality that works equally in both directions: the same action of touching is at the same time an input and an output act. By comparison, the other sense channels require different means for input (hearing of sound through the ears, seeing through the eyes) and output (creating sounds through voice or other means, displaying objects visibly).

Both this and the fact that touching involves direct physical contact give tangibility a clearly prominent status among other modalities with respect to immediately affecting objects in our environment. Consequently, when looking for metaphorical extensions of tangibility as a concept, the characteristics of immediacy and manipulation provide a potent frame of reference, or a clearly perceptible point of departure.

Two approaches are proposed here to explore these metaphorical extensions.

One is by substituting through other, indirect, means for the aspects of tangibility that are lacking in other media, as is done for example in manipulation of virtual objects through gestures. The other one is to strive to imitate or create the characteristics of the tangible mode of operation in modalities that are essentially far removed from the realm of tangibility. This can mean many things. For example, it may be valuable to try and develop modes of operation on virtual programming objects in code that are as immediate as possible in their effect, and that allow one to manipulate the structure of objects as directly as possible. Detailed knowledge of the way that tangible media work can thus leads to new ways of interacting with the intangible.

Another way can be to strive to imitate or impart the (subjective) sense of the tangible through other means, in other words, to use sound or images to express experiences that belong to the realm of the tangible. The approach outlined above involves a combination of analytical, empirical and experimental/constructive activities that complement each other. If there are any new paradigms waiting to be discovered in the realm of tangibility, these can best be sought through concerted efforts.

CONCLUSION

The above presentations describe different approeaches and thoughts on the notion of tangibility. A convergence of concerns is discernible, centering on the need to combine the versatility and freedom of digital technologiese, with the immediacy and physicality of tangible interfaces. This can otherwise be described as the need to combine virtual/symbolic/intangible with real/physical/tangible aspects. This short and incomplete overview outlines various attempts to achieve this "coming back". Each of them can be characterized by, the nature, the meaning, the mode of combining the relation between the world of physical objects or objective phenomena and the world of digital symbols.

For instance, in the multisensory and interactive simulation of physical objects, there is a cognitive reference to the real world and the real matter, a digital modeling of this reference in the computer, and a "come back to reality" through digital to physical transducers and in particular the bidirectional transducers in the case of gesture.

At the other side, in designing and making digital/physical things by digital/physical means, there are two purposes. One is simply to go from the digital world, whatever the way in which it is built, to real and true material objects (made of atoms) that can be used as our ordinary objects, our tools, or even our houses. This was the purpose and the function of the first CNC machines. The second purpose is to try to dissolve the boundary between the digital world and the physical world.

This raises in a certain way the same key question as the physical objects simulation, which is, "is it actually possible?"

In the extension of the tangibility metaphor, there is a third purpose, which may combine with the previous in many ways, which is to try to give to entities which are not real, not concrete, even purely symbolic, the status and the "presence" of real or material objects that we can manipulate.

Pushed to the extreme exaggeration for the sake of argument, it raises a very interesting and intriguing question: "is it possible, and to what extent, to "touch" and "feel" abstractions?" Or, conversely, "is an abstraction not precisely characterized by the fact that it cannot be touched or felt?"

Endnotes

• ACROE (Grenoble -France), well-known as a pioneer in physical modeling for artistic creation and in design of force-feedback gestural devices and multisensory real-time simulation platforms, aiming to turn the computer into a true instrument for artistic creation. AC-ROE has also developed several computer environments for artistic creation, in particular GENESIS for computer music and MIMESIS for animated image.

• ICA Lab. (Engineering for Artistic Creation Laboratory, Grenoble -France), created at Grenoble Institute of Technology (GIT) in 1999. It is, in partnership with the ACROE, in charge of research on science and technology of artistic creation in music, animated image and multisensory arts. It is also in charge of academic teaching through the Art Science and Technology (AST) master degree's and the AST platform.

• Cardiff School of Art & Design4 (CSAD), first opened in 1865 as Cardiff School of Art is today part of Cardiff Metropolitan University. It is one of the oldest Art Schools in the UK and its undergraduate and post graduate courses includes Fine Art, Ceramics, Artist Design Maker, Textiles, Illustration, Graphic Communication, Product Design and Architectural Design and Technology. CSAD is a lead partner in the Wales Institute of Research in Art and Design and it is part of the Fab Labs collaborative global network as Cardiff Fab Lab.

• Fab Lab Barcelona5 -Advanced Architecture of Catalonia6 (Barcelona -Spain) is a cutting edge education and research center dedicated to the development of architecture capable of meeting the worldwide challenges in the construction of habitability in the early 21st century. It is one of the leading laboratories of the worldwide Fab Labs network, gathering innovative workshop equipped with small-scale and large-scale, traditional and digital, fabrication tools.

• The Center for Art and Media7 (ZKM) in Karlsruhe holds a unique position in the world. Its work combines production and research, exhibitions and events, coordination and documentation. ZKM's Institute for Music and Acoustics (IMA) is a creative hub that aims at developing new technologies in digital music such as the Klangdom, a unique 43-channel loudspeaker, and its driving software, Zirkonium. IMA also supports the creation of new compositions through artist residencies, production support and by organizing a series of concerts open to the general public.

• The Ionian University (IU) in Corfu, involves two of its departments, combining education, research and production, in this network. The Department of Audiovisual Arts (AVARTS), specialized in interactive digital arts of sound and image, photography, audio and visual design. The Music Department, which focuses with the EPHMEE (Electroacoustic Music Research and Applications Laboratory) on the study and production of original work within the field of sonic art and technology.

www.eastn.eu

ec.europa.eu/culture

Proceedings ICMC|SMC|201414-20 September 2014, Athens, Greece

cardiff-school-of-art-and-design.org

www.fablabbcn.org

www.iaac.net

www.zkm.de

Acknowledgments

The EASTN project has been funded with support from the European Commission. This publication reflects the views only of the author, and the Commission cannot be held responsible for any use which may be made of the information contained therein'


C Guillemot
email: mounira.ebdelli@inria.fr

Hierarchical super-resolution-based inpainting

Olivier Le Meur, Mounira Ebdelli, Christine Guillemot Abstract-This paper introduces a novel framework for examplar-based inpainting. It consists in performing first the inpainting on a coarse version of the input image. A hierarchical super-resolution algorithm is then used to recover details on the missing areas. The advantage of this approach is that it is easier to inpaint low-resolution pictures than high resolution ones. The gain is both in terms of computational complexity and visual quality. However, to be less sensitive to the parameter setting of the inpainting method, the lowresolution input picture is inpainted several times with different configurations. Results are efficiently combined with a loopy belief propagation and details are recovered by a singleimage super-resolution algorithm. Experimental results in a context of image editing and texture synthesis demonstrate the effectiveness of the proposed method. Results are compared to five state-of-the-art inpainting methods.

Index Terms-Examplar-based inpainting, single-image super-resolution

I. INTRODUCTION

I MAGE inpainting refers to methods which consist in filling in missing regions (holes) in an image [START_REF] Bertalmio | Image inpainting[END_REF]. Existing methods can be classified into two main categories.

The first category concerns diffusion-based approaches which propagate linear structures or level lines (so-called isophotes) via diffusion based on partial differential equations [START_REF] Bertalmio | Image inpainting[END_REF], [START_REF] Tschumperlé | Vector-valued image regularization with pdes: a common framework for different applications[END_REF] and variational methods [START_REF] Chan | Variational restoration of non-flat image features: models and algorithms[END_REF]. The diffusionbased methods tend to introduce some blur when the hole to be filled in is large. The second family of approaches concerns examplar-based methods which sample and copy best matching texture patches from the known image neighbourhood [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF], [START_REF] Drori | Fragment-based image completion[END_REF], [START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF], [START_REF] Barnes | Patch-Match: A randomized correspondence algorithm for structural image editing[END_REF]. These methods have been inspired from texture synthesis techniques [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF] and are known to work well in cases of regular or repeatable textures. The first attempt to use examplar-based techniques for object removal has been reported in [START_REF] Harrison | A non-hierarchical procedure for re-synthesis of complex texture[END_REF]. The authors in [START_REF] Drori | Fragment-based image completion[END_REF] improve the search for similar patches by introducing an a priori rough estimate of the inpainted values using a multi-scale approach which then results in an iterative approximation of the missing regions from coarse-to-fine levels. The two types of methods (diffusion-and examplarbased) can be efficiently combined, e.g. by using structure tensors to compute the priority of the patches to be filled in as in [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF]. A recent approach [START_REF] Le Meur | Super-resolution-based inpainting[END_REF] combines an examplarbased approach with super-resolution. It is a two-steps algorithm. First a coarse version of the input picture is inpainted. The second step consists in creating an enhanced resolution picture from the coarse inpainted image.

Although tremendous progress has been made in the past years on examplar-based inpainting, there still exists a number of problems. We believe that the most important one is related to the parameter settings such as the filling order and the patch size.

This problem is here addressed by considering multiple inpainted versions of the input image. To generate this set of inpainted pictures, different settings are used. The inpainted pictures are then combined yielding the final inpainted result. Notice that the inpainting algorithm is preferably applied on a coarse version of the input image; this is particularly interesting when the hole to be filled in is large. This provides the advantage to be less demanding in terms of computational resources and less sensitive to noise and local singularities. In this case the final full resolution inpainted image is recovered by using a superresolution (SR) method similarly to [START_REF] Le Meur | Super-resolution-based inpainting[END_REF]. SR methods refer to the process of creating one enhanced resolution image from one or multiple input low resolution images. These problems are then referred to as single or multiple images SR, respectively. In both cases, the problem is of estimating high frequency details which are missing in the input image(s). The proposed SR-aided inpainting method falls within the context of single-image SR.

The SR problem is ill-posed since multiple highresolution images can produce the same low-resolution image. Solving the problem hence requires introducing some prior information. The prior information can be an energy functional defined on a class of images which is then used as a regularization term together with interpolation techniques [START_REF] Dai | Softcuts: a soft edge smoothness prior for color image superresolution[END_REF]. This prior information can also take the form of example images or of corresponding LR-HR (Low Resolution -High Resolution) pairs of patches learned from a set of un-related training images [START_REF] Freeman | Example-based superresolution[END_REF] or from the input low resolution image itself [START_REF] Glasner | Super-resolution from a single image[END_REF]. This latter family of approaches is known as examplar-based SR methods [START_REF] Freeman | Example-based superresolution[END_REF]. An examplar-based super-resolution method embedding K nearest neighbours found in an external patch database has also been described in [START_REF] Chang | Super-resolution through neighbor embedding[END_REF]. Instead of constructing the LR-HR pairs of patches from a set of un-related training images, the authors in [START_REF] Glasner | Super-resolution from a single image[END_REF] extract these correspondences by searching for matches across different scales of a multi-resolution pyramid constructed from the input lowresolution image.

The proposed method builds upon the super-resolutionbased inpainting method proposed in [START_REF] Le Meur | Super-resolution-based inpainting[END_REF] which is based on examplar-based inpainting (in particular Criminisi-like approach [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]) and single-image examplar-based super- resolution [START_REF] Glasner | Super-resolution from a single image[END_REF]. The main novelty of the proposed algorithm is the combination of multiple inpainted versions of the input picture. The rationale behind this approach is to cope with the sensitivity of examplar-based algorithms to parameters such as the patch size and the filling order. Different combinations have been tested and compared. Besides this major point, different adjustments regarding examplar-based inpainting and SR methods are described such as the use of the coherence measure to constrain the candidate search [START_REF] Wexler | Space-time video completion[END_REF].

In summary, the proposed method improves on the stateof-the-art examplar-based inpainting methods by proposing a new framework involving a combination of multiple inpainting versions of the input picture followed by a single-image examplar-based SR method. Notice that the SR method is used only when the inpainting method is applied on a low resolution of the input picture.

The paper is organized as follows. In Section II, an overview of the proposed examplar-based inpainting algorithm is presented. In Section III, the details of the inpainting algorithm as well as the combination of the inpainted pictures are given. Section IV presents the super-resolution method. Experiments and comparisons with state-of-the-art algorithms are performed in Section V. Finally we conclude this work in Section VI.

II. NOTATIONS AND ALGORITHM OVERVIEW

A. Notations

The following notations are used throughout this paper:

• I is a color input 2D image:

I : Ω ⊂ R n → R m x → I(x) (1)
where n = 2 and in this case x = (x, y) represents a vector indicating spatial coordinates of a pixel p x . Ω is the generic definition domain of images. I is a color image composed of three components (m = 3).

Here, we consider the (R, G, B) color space. • I i : Ω → R represents the i th image channel of I.

• the definition domain Ω is here composed of two parts: Ω = S∪T , S being the known part of I (source region) and T the target one or unknown parts of I. • I (c) is the inpainted picture obtained by using the c th setting configuration. The setting refers to the patch's size, the size of the search window, the picture's orientation, to name a few. We consider that c is in the range 1 to M . • I ( * ) is the final inpainted picture.

• We denote by p (k)

x the pixel located at x in the image I (k) .

• ψ px is the patch centered on the pixel p x .

• ψ uk px denotes the unknown pixels of the patch whereas ψ k px denotes its known pixels. • LR and HR denote Low Resolution and High Resolution respectively. ψ HR px is a patch of high resolution. • D HR is a set of HR patches (a dictionary) which is used by the super-resolution algorithm.

B. Algorithm overview

Image completion of large missing regions is a challenging task. As presented in the previous section, there are a number of solutions to tackle the inpainting problem. In this paper, we propose a new inpainting framework relying on both the combination of low-resolution inpainting pictures method and a single-image super-resolution algorithm. In the following sections, we briefly present the main ideas of this paper and the reasons why the proposed method is new and innovative.

The proposed method is composed of two main and sequential operations. The first one is a non-parametric patch sampling method used to fill in missing regions. The inpainting algorithm is preferably applied on a coarse version of the input picture. Indeed a low-resolution picture is mainly represented by its dominant and important structures of the scene. We believe that performing the inpainting of such a low-resolution image is much easier than performing it on the full resolution. A low-resolution image is less contaminated by noise and is composed by the main scene structures. In other words, in this kind of picture, local orientation singularities which could affect the filling order computation are strongly reduced. Second, as the picture to inpaint is smaller than the original one, the computational time is significantly reduced compared to the one necessary to inpaint the full resolution image. To give more robustness, we inpaint the low-resolution picture with different settings (patch's size, filling order, etc). By combining these results, a final low-resolution inpainted picture is obtained. Results will show that the robustness and the visual relevance of inpainting is improved. The second operation is run on the output of the first step. Its goal is to enhance the resolution and the subjective quality of the inpainted areas. Given a low-resolution input image, which is the result of the first inpainting step, we recover its high-resolution using a single-image super-resolution approach. Figure 1 illustrates the main concept underlying the proposed method namely:

1) a low-resolution image is first built from the original picture; 2) an inpainting algorithm is applied to fill in the holes of the low-resolution picture. Different settings are used and inpainted pictures are combined; 3) the quality of the inpainted regions is improved by using a single-image super-resolution method.

III. MULTIPLE EXAMPLAR-BASED INPAINTING

This section aims at presenting the proposed inpainting method and the combination of the different inpainted images.

A. Examplar-based inpainting

The proposed examplar-based method follows the two classical steps as described in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]: the filling order computation and the texture synthesis. These are described in the next sections.

1) Patch priority: The filling order computation defines a measure of priority for each patch in order to distinguish the structures from the textures. Classically, a high priority indicates the presence of structure. The priority of a patch centered on p x is just given by a data and confidence term. The latter is exactly the one defined in [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]. Regarding the data term, a tensor-based [START_REF] Le Meur | Examplar-based inpainting based on local geometry[END_REF] and a sparsity-based [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF] data terms have been used. These terms are briefly described below.

The tensor-based priority term is based on a structure tensor also called Di Zenzo matrix [START_REF] Di Zenzo | A note on the gradient of a multi-image[END_REF]; this is given by:

J = m i=1 ∇I i ∇I T i (2)
J is the sum of the scalar structure tensors ∇I i ∇I T i of each image channel I i (R,G,B). The tensor can be smoothed without cancellation effects :

J σ = J * G σ where G σ = 1 2πσ 2 exp(-x 2 +y 2
2σ 2 ), with standard deviation σ. One of the main advantages of a structure tensor is that a structure coherence indicator can be deduced from its eigenvalues. Based on the discrepancy of the eigenvalues, the degree of anisotropy of a local region can be evaluated. The local vector geometry is computed from the structure tensor J σ . Its eigenvectors v 1 , v 2 (v i ∈ R n ) define an oriented orthogonal basis and its eigenvalues λ 1,2 define the amount of structure variation. The vector v 1 is the orientation with the highest fluctuations (orthogonal to the image contours), whereas v 2 gives the preferred local orientation. This eigenvector (having the smallest eigenvalue) indicates the isophote orientation. A data term D is then defined as [START_REF] Weickert | Coherence-enhancing diffusion filtering[END_REF]:

D(p x ) = α + (1 -α)exp - η (λ 1 -λ 2 ) 2 (3)
where η is a positive value and α ∈ [0, 1] (η = 8 and α = 0.01). On flat regions (λ 1 ≈ λ 2 ), any direction is favoured for the propagation (isotropic filling order). When λ 1 >> λ 2 indicating the presence of a structure, the data term is important.

The sparsity-based priority has been proposed recently by Xu et al. [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF]. In a search window, a template matching is performed between the current patch ψ px and neighbouring patches ψ p j that belong to the known part of the image. By using a non-local means approach [START_REF] Wexler | Space-time video completion[END_REF], a similarity weight w px,p j (i.e. proportional to the similarity between the two patches centered on p x and p j ) is computed for each pair of patches. The sparsity term is defined as:

D(p x ) = w px 2 × |N s (p x )| |N (p x )| (4)
where N s and N represent the number of valid patches (having all its pixels known) and the total number of candidates in the search window. When w px 2 is high, it means larger sparseness whereas a small value indicates that the current input patch is highly predictable by many candidates.

2) Texture synthesis: The filling process starts with the patch having the highest priority. To fill in the unknown part of the current patch ψ uk px , the most similar patch located in a local neighbourhood W centered on the current patch is sought. A similarity metric is used for this purpose. The chosen patch ψ * px maximizes the similarity between the known pixel values of the current patch to be filled in ψ k px and co-located pixel values of patches belonging to W:

ψ * px = arg min ψp j ∈W d(ψ k px , ψ k p j ) s.t Coh(ψ uk px ) < λ coh (5)
where d(.) is the weighted Bhattacharya used in [START_REF] Le Meur | Super-resolution-based inpainting[END_REF]. Coh(.) is the coherence measure initially proposed by Wexler et al. [START_REF] Wexler | Space-time video completion[END_REF]:

Coh(ψ uk px ) = min p j ∈S d SSD (ψ uk px , ψ uk p j ) (6)
where d SSD is the sum of square differences. The coherence measure Coh simply indicates the degree of similarity between the synthesized patch ψ uk px and original patches. Therefore, the constraint in equation ( 5) prevents pasting in the unknown regions a texture that would be too different from original textures. If none of the candidates fulfil the constraint (5), the filling process is stopped and the priority of the current patch is decreased. The process restarts by seeking the patch having the highest priority. It is interesting to note that a recent study [START_REF] Kopf | Quality prediction for image completion[END_REF] uses a similar term to predict the quality of the inpainting.

Compared to our previous work [START_REF] Le Meur | Super-resolution-based inpainting[END_REF], there is another substantial difference: we only use the best match to fill in the hole whereas a linear combination of the K most similar patches is generally performed to compute the patch ψ * px in [START_REF] Le Meur | Super-resolution-based inpainting[END_REF], [START_REF] Wexler | Space-time video completion[END_REF], [START_REF] Xu | Image inpainting by patch propagation using patch sparsity[END_REF], [START_REF] Bugeau | A comprehensive framework for image inpainting[END_REF]. In these cases, the estimated patch is then given by:

ψ * px = K i w px,p i × ψ k p i ( 7
)
where K is the number of candidates which is often adapted locally so that the similarity of chosen neighbours lies within a range (1 + α) × d min , where d min is the distance between the current patch and its closest neighbours. Different methods can be used to compute the weights. It could be based on either a non-negative matrix factorization (NMF) [START_REF] Lee | Algorithms for non-negative matrix factorization[END_REF] or a non local means filter [START_REF] Buades | A non local algorithm for image denoising[END_REF], [START_REF] Wexler | Space-time video completion[END_REF], to name a few. Combining several candidates increases the algorithm robustness. However, it tends to introduce blur on fine textures as illustrated by figure 2. In our method, only the best candidate is chosen. Its unknown parts are pasted into the missing areas. A Poisson fusion [START_REF] Pérez | Poisson image editing[END_REF] is applied to hide the seams between known and unknown parts. An α-blending is also applied to combine known parts of the candidate and the source patch (ψ k px ← αψ k px +(1-α)ψ k, * px , with α = 0.75). It gives more robustness by locally regularizing the results.

Although the proposed method is able to fill in holes in a visually pleasant fashion (as illustrated by figure 2 and9), it still suffers from problems of one-pass greedy algorithms. Indeed for most of existing approaches, the setting such as the patch size and the filling order, to name the most important factors, may dramatically impact the quality of results. To overcome this issue, we combine inpainted pictures obtained when different settings are used. In this study, we consider M = 13, meaning that the low-resolution picture is inpainted 13 times. Parameters are given in Table I: the patch size is chosen between 5 × 5, 7 × 7, 9 × 9 and 11 × 11. The filling order is computed by either the sparsity-based or the tensor-based method. The input picture can also be rotated by 180 degrees. This allows changing the filling order.

B. Combining multiple inpainted images

The combination aims at producing a final inpainted picture from the M inpainted pictures. Before delving into this subject in details, Figure 3 illustrates some inpainted results obtained for a given setting. We notice again that the setting plays an important role. To obtain the final inpainted picture, three kinds of combination have been considered. The first two methods are very simple since every pixel value in the final picture is achieved by either the average or the median operator as given below: The advantage of these operators is their simplicity. However they suffer from at least two main drawbacks. The average operator as well as the median one do not consider the neighbours of the current pixel to take a decision. Results might be more spatially coherent by considering the local neighbourhood. In addition, the average operator inevitably introduces blur as illustrated by Figure 5.

I ( * ) (p x ) = 1 M M i=1 I (i) (p x ) (8)
I ( * ) (p x ) = M ED M i=1 I (i) (p x ) (9)
To cope with these problems, namely blur and spatial consistency of the final result, the combination is achieved by minimizing an objective function. Rather than using a global minimization that would solve exactly the problem, we use a Loopy Belief Propagation which in practice provides a good approximation of the problem to be solved. This approach is described in the next section.

1) Loopy Belief Propagation: As in [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF], the problem is to assign a label to each pixel p x of the unknown regions T of the picture I ( * ) . The major drawback of the belief propagation is that it is slow especially when the number of labels is high. Komodakis and Tziritas [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF] have designed a priority Belief Propagation in order to deal with this complexity bottleneck. Indeed, the number of labels in [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF] is equal to the number of patches in the source region. Here the approach is simpler since the number of labels is rather small; a label is simply the index of the inpainted picture from which the patch is extracted. A finite set of labels L is then composed of M values (M = 13 here), going from 1 to M . This problem can be formalized with a Markov Random Field (MRF) G = (ν, ) defined over the target region T . The MRF nodes ν are the lattice composed of pixels inside T . Edges are the fourconnected image grid graph centered around each node. We denote N 4 this neighbourhood system. The labelling assigns a label l (l ∈ L) to each node/pixel p x (p x ∈ T ) so that the total energy E of the MRF is minimized (we denote by l p the label of pixel p x ) [START_REF] Boykov | Efficient approximate energy minimization via graph cuts[END_REF], [START_REF] Boykov | An experimental comparison of mincut/max-flow algorithms for energy minimization in vision[END_REF]:

E(l) = p∈ν V d (l p ) + (n,m)∈N4 V s (l n , l m ) (10)
where,

• V d (l p ) is called the label cost (or the data cost) [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF]. This represents the cost of assigning a label l p to a pixel p x . This is given by:

V d (l p ) = n∈L u∈υ I (l) (x + u) -I (n) (x + u) 2 ( 11
)
where υ is a square neighbourhood (3 × 3) centered on the current pixel. The cost increases when the dissimilarity between the current patch and colocated patches in other inpainted pictures is high. • The pairwise potential or the discontinuity cost V s (l n , l m ) is a quadratic cost function given by:

V s (l n , l m ) = λ × (l n -l m ) 2 ( 12
)
where λ is a weighting factor and is set to 100 (Figure 4 illustrates the influence of this factor). The discontinuity cost is here based on a difference between labels rather than the difference between pixel values. The minimization of the energy E over the target region T can be achieved using loopy belief propagation (LBP) [START_REF] Yedidia | Constructing free energy approximations and generalized belief propagation algorithms[END_REF] and corresponds to the maximum a posteriori (MAP) estimation problem for an appropriately defined MRF [START_REF] Blake | Visual reconstruction[END_REF]. Figure 4 illustrates the minimization of the total energy as well as the influence of the smoothness term. When λ = 0, there is no smoothness term. Some artefacts indicated by arrows are visible. When λ = 500, artefacts are visible. A good trade-off is obtained by setting the value λ to 100. On the same figure 4, the labelling convergence is given for four iterations (pictures on top of this figure represent label values, not pixel values). This illustrates the fact that the label choice is not greedy.

2) Comparison of the combination methods: Figure 5 illustrates the performance of the combination methods. As expected, when the different inpainted pictures are averaged, the reconstructed areas are blurred. The blur is less striking when the median operator is used to combine pictures. The LBP method provides the best result. The texture is well retrieved and thanks to the global energy minimization results are spatially consistent. In the following, we use the LBP method to combine low-resolution inpainted pictures.

3) Possible extensions: Two extensions of the proposed method could be also envisioned. First, rather than combining the low-resolution inpainted pictures, the best impainting picture could be selected either by a user (semisupervised inpainting) or by automatically evaluating the inpainting quality using a coherence measure as proposed in [START_REF] Kopf | Quality prediction for image completion[END_REF].

IV. SUPER-RESOLUTION ALGORITHM

Once the combination of the low-resolution inpainted pictures is completed, a hierarchical single-image superresolution approach is used to reconstruct the high resolution details of the image. We stress the point that the single-image SR method is applied only when the input picture has been downsampled for the inpainting purpose. Otherwise the SR method is not required. As in [START_REF] Freeman | Example-based superresolution[END_REF], [START_REF] Le Meur | Super-resolution-based inpainting[END_REF], the problem is to find a patch of higher-resolution from a database of examples. The main steps, illustrated in figure 6 are described below:

1) Dictionary building: consists of the correspondences between low and high resolution image patches. The unique constraint is that the high- resolution patches have to be valid, i.e. entirely composed of known pixels. In the proposed approach, high-resolution and valid patches are evenly extracted from the known parts of the image. The size of the dictionary is a user-parameter which might influence the overall speed/quality trade-off. An array is used to store the spatial coordinates of HR patches (D HR ).

Those of LR patches are simply deduced by using the decimation factor equal to 2; 2) Filling order of the HR picture: The computation of the filling order is similar to the one described in Section III. It is computed on the HR picture with the sparsity-based method. The filling process starts with the patch ψ HR px having the highest priority and which is composed of known and unknown parts. Compared to a raster-scan filling order, it allows us to start with the structures and then to preserve them; 3) For the LR patch corresponding to the HR patch having the highest priority, its best neighbour in the inpainted images of lower resolution is sought. This search is performed in the dictionary and within a local neighbourhood. Only the best candidate is kept. From this LR candidate, a HR patch is simply deduced. Its pixel values are then copied into the unknown parts of the current HR patch ψ HR px . After the filling of the current patch, the priority value is propagated and the aforementioned steps are iterated while there exist unknown areas. A Poisson and alpha-blending are again used to hide seams between known and unknown parts and to improve robustness.

Compared to [START_REF] Le Meur | Super-resolution-based inpainting[END_REF], the SR method is applied in a hierarchical manner. For instance, if the input picture of resolution (X, Y ) has been down-sampled by four in both directions, the SR algorithm is applied twice: a first time to recover the resolution ( X 2 , Y 2 ) and a second time to recover the native resolution.

V. EXPERIMENTAL RESULTS

In this section, the proposed approach is tested on a variety of natural images and compared to five state-ofthe-art inpainting methods.

A. Intrinsic performance of the proposed method

Figures 7 and8 illustrate the results of the proposed approach. A down sampling factor of 4 in both directions is used. Pictures have a resolution varying in the range 420 × 380 to 720 × 512. Figure 7 (b) gives the inpainted low-resolution picture whereas the column (c) illustrates the final result. The proposed approach faithfully recovers the texture such as the grass, the sand and the snow. Structures are also well recovered. Figure 8 presents more results which are visually plausible and pleasing in most of the cases. The less-favourable results are obtained when the hole to be filled in is rather small. In this case it might be better to reduce the down sampling factor or even to perform the inpainting at the full resolution.

B. Parameters analysis

When the proposed method, called the baseline method in the following, has been defined, we have fixed several parameters such as the number of K-NN for the inpainting (K = 1), the similarity metric (weighted Bhattacharya) and the color space (RGB). We evaluate subjectively the relevance of these choices on two pictures. Results are illustrated in Figure 9.

1) K-NN patches for inpainting: In Section III-A2, we set the number of K-NN for the examplar-based inpainting to 1 preventing blur apparition as illustrated by figure 2. However, as the inpainting is applied on a low-resolution picture, it might make sense to use more than one candidate. We compare results obtained by the baseline approach to those obtained for three different K values: 1 (baseline algorithm), 4 and 8. Results are illustrated in figure 9. Results are similar for K = 4. For K = 8, the inpainted quality is not as visually pleasing as the one obtained by the two previous settings.

2) RGB space versus Y component: The color space, used to perform the candidate search for instance, might play an important role. By using the luminance component only, results are visually less good than the baseline one, especially for the first picture.

3) SSD versus weighted Bhattacharya: Qualitatively speaking, inpainted results obtained with the weighted Bhattacharya metric are slightly better than those obtained with the SSD metric.

4) Downsampling factor equal to 2: By performing the inpainting at a higher resolution, results are not as good as those obtained by the baseline approach, especially on the first picture (first row). This could be explained by the size of the search window which should be increased for this condition.

C. Comparison with state-of-the-art methods

State-of-the-art inpainting methods are used for comparison purposes. The first one is the well known method proposed by Criminisi et al. [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]. We have used a third part implementation available on http://www.cc.gatech.edu/ ∼ sooraj/inpainting/ (we use a patch's size of 9 × 9 and a local windows search of 80 × 80). The second one is the PatchMatch method [START_REF] Barnes | Patch-Match: A randomized correspondence algorithm for structural image editing[END_REF] which is a fast algorithm for computing dense approximate nearest neighbour correspondences between patches of two image regions. This algorithm is available in Adobe Photoshop CS5. The shiftmap method [START_REF] Pritch | Shift-map image editing[END_REF] is the third algorithm considered in the test. This approach is treating inpainting as a global optimization in a multi-scale scheme. The goal is to shift pixel values from the known part of the picture to the missing part. A graph cut optimization allows finding the best mapping. Inspired by [START_REF] Pritch | Shift-map image editing[END_REF], He and Sun [START_REF] He | Statistics of patch offsets for image completion[END_REF] recently proposed a new method. The idea is to find the most important 2D offsets (displacement) in the picture. These offsets are then used to shift the input picture. The shifted images are finally combined. Method of Komodakis and Tziritas [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF] relying on priority belief propagation is also tested.

Figure 10 illustrates results of the proposed approach, Criminisi et al. [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF] and PatchMatch method [START_REF] Barnes | Patch-Match: A randomized correspondence algorithm for structural image editing[END_REF]. Our method outperforms Criminisi et al. [START_REF] Criminisi | Region filling and object removal by examplar-based image inpainting[END_REF]. Compared to PatchMatch method [START_REF] Barnes | Patch-Match: A randomized correspondence algorithm for structural image editing[END_REF], results are similar for the two first pictures and better for the two last pictures. Comparison between the proposed approach and He's method [START_REF] He | Statistics of patch offsets for image completion[END_REF], shift-map [START_REF] Pritch | Shift-map image editing[END_REF] and priority belief propagation [START_REF] Komodakis | Image completion using efficient belief propagation via priority scheduling and dynamic pruning[END_REF] is given on figure 11. The tested pictures are extracted from [START_REF] He | Statistics of patch offsets for image completion[END_REF]. Concerning the comparison between our method and He's method, results are quite similar except for the first and last pictures for which He's approach gives more visually pleasing results, although there is no obvious artefacts in our results. Regarding shift-map and BP methods (the three last rows of figure 11), artefacts are visible such as on the stone wall (fourth row) and on the waterfall (BP method on the fifth row). On these pictures, our method is more robust than shift-map and Belief Propagation methods.

D. Extension

1) Application to texture synthesis: Figure 12 presents additional results for texture synthesis. A small chunk of texture was placed into the upper left corner of an empty image. The goal is to fill in the missing parts composed here of 256 × 256 pixels in a visually plausible way. This application is interesting in itself, but it also allows showing a limitation of the proposed approach. When the texture is stochastic as illustrated by figure 12, there exist many ways to fill in the holes in a visually plausible fashion. Performing M different inpaintings and combining them would lead to a poor quality. To overcome this limitation, the input texture is inpainted just once at a low resolution. The SR method is then applied. For texture synthesis, the patch size is arbitrarily set to 9 × 9 and we down-sample the input chunk by 4 in both directions. In addition, two modifications are also brought to the algorithm. First we limit the search for the closest candidate to the input picture (here it is the original texture chunk). Second the filling order is the raster scan order.

The two first texture chunks illustrated by figure 12 are complex to synthesize. Some artefacts are visible on the first two results whereas for the two last results the synthesised texture has a very good quality.

2) Using similar images: Another extension would be to use similar images in a similar fashion to Hays and Efros [START_REF] Hays | Scene completion using millions of photographs[END_REF] and Whyte et al. [START_REF] Whyte | Get out of my picture! internetbased inpainting[END_REF]. We have adapted the proposed method to take as input the image to inpaint, similar images to the image source and an image which is used as a guide for the LBP. For that the energy of the LBP has been modified as follows:

E(l) = p∈ν V d (l p ) + (p,q)∈ν V s (l p , l q ) + p∈ν V g (l p ) (13)
where, the first term is the same as previously defined (see equation [START_REF] Dai | Softcuts: a soft edge smoothness prior for color image superresolution[END_REF]). The second term is here different since it involves pixel values rather than label values as in [START_REF] He | Statistics of patch offsets for image completion[END_REF]. This term is given by:

V s (m, n) = I (m) (p) -I (m) (q) 2 + I (n) (p) -I (n) (q) 2 (14
) with (p, q) are neighbouring pixels and m, n represent their labels. The third term V g is used to guide the labelling. It is given by: where I g is a prediction image of the unknown pixels.

V g (n) = I (n) (p) -I g (p) 2 (15)
The prediction can be obtained by a classical inpainting such as our baseline method presented in section III-A or by an diffusion-based method as illustrated in figure 13. This term is useful to select the most appropriate pixel values in the set of similar pictures: for a given pixel p, if the candidate pixel value at that location is close to the predicted one I g (p), the associate cost is low. Figure 13 illustrates this method. From an image to inpaint (topmiddle), 21 similar images were found by using Google Image search. To guide the LBP, we use the inpainted image from either our baseline inpainting method or the Navier-Stoke diffusion method [START_REF] Bertalmio | Navier-stokes, fluid dynamics, and image and video inpainting[END_REF]. These two guides coupled with the similar images already provide quite good results. Result of the method involving multiple inpainting (bottomright of figure 13) is also shown and further improves the quality. Note that rather than using similar images, it would be possible to use state-of-the-art inpainted pictures and to combine them. This kind of solution might improve performance because of the better complementary of stateof-the-art inpainting methods. It would be possible to mix results from examplar-based, diffusion-based and shift-map inpainting methods. Finally, a semi-supervised approach for which the user is able to choose the best low-resolution inpainted picture could be easily designed. In this case, it is no longer necessary to combine them.

E. Running time

Table II gives the running time of the proposed approach. Simulation has been performed on a laptop with an Intel Core i7 2.40GHz and 4Go RAM. As the proposed approach is not multithreaded, it just uses one core. In addition, no optimization was made. Table II indicates that the superresolution process is the most time-consuming step (in average it represents 80% of the total time). It is due to the template matching which is not parallelized. To improve the performance, the template matching could be replaced by an approximate nearest neighbour search [START_REF] Barnes | Patch-Match: A randomized correspondence algorithm for structural image editing[END_REF]. VI. CONCLUSION A novel inpainting approach has been presented in this paper. The input picture is first down sampled and several inpaintings are performed. The low-resolution inpainted pictures are combined by globally minimizing an energy term. Once the combination is completed, a hierarchical single image super resolution method is applied to recover details at the native resolution. Experimental results on a wide variety of images have demonstrated the effectiveness of the proposed method.

One interesting avenue of future work would be to extend this approach to the temporal dimension. Also, we plan to test other SR methods to bring more robustness to the method. But the main important improvement is likely the use of geometric constraint and higher-level information such as scene semantics in order to improve the visual relevance.

Windows executable is available on authors webpage: http://people.irisa.fr/Olivier.Le Meur/.

Fig. 1 .

 1 Fig. 1. The framework of the proposed method.

Fig. 2 . 8 Fig. 3 .

 283 Fig. 2. (a) original picture with a black hole to be filled in; (b) result obtained with a simple template matching (TM), with the linear combination of the K most similar neighbours in which weights are computed by using a non local means method (c) and by a non negative matrix factorization (d). For this example, the maximum number of neighbours is 10. (e) to (g) zoom in the inpainted part for TM, NLM and NMF, respectively.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Illustration of the energy minimization. On the top, the convergence process of the LBP is illustrated. The labelling obtained for four different iterations are also shown. The bottom images show the influence of the smoothness term for three values of λ (see equation (12)).

Fig. 6 .

 6 Fig. 6. Flowchart of the super-resolution algorithm. The missing parts of the red block are filled in by the best candidate stemming either from the dictionary or from the local neighbourhood. The top image represents the original image with the missing areas whereas the bottom one is the result of the low-resolution inpainting.

Fig. 7 .

 7 Fig. 7. Results of the proposed method. (a) input images with unknown regions; (b) inpainted low-resolution images; (c) final inpainted images (for the sake of visibility, we do not respect the down sampling factor of 4 between pictures (b) and (c)).

Fig. 8 .Fig. 9 .

 89 Fig.8. Results of proposed approach for a variety of pictures of natural content. The unknown parts in black visible on pictures of odd rows are more or less large and complex to fill in. Pictures of even rows are our results.

Fig. 12 .

 12 Fig. 12. Examples of texture synthesis. (a) chunk of texture (256 × 256) with the unknown parts in black (256 × 256); (b) Results obtained by the proposed approach.

Fig. 10 .

 10 Fig. 10. Comparison with state-of-the-art methods: (a) original pictures with unknown regions; (b) Criminisi's algorithm; (c) PatchMatch method; (d) proposed method.

Fig. 13 .

 13 Fig. 13. Extension of the proposed approach. From a set of similar images, an inpainting is performed on a low-resolution version of the input picture. The LBP uses a set of similar images (21 images here (topleft)) and a guide (if any). The SR is applied to recover the details of the missing pixels. Different guides (examplar-based or diffusion-based inpainting) can be used to drive the LBP. (*) (in the first box on the left) means that the term Vg of equation (13) is null. Bottom-up line gives other results.

  Fig. 11. Comparison with state-of-the-art results. On the three first rows: (a) original image; (b) He's results (extracted from [30]), (c) proposed approach. On the three last rows: (a) original image; (b) He's results; (c) Shift-map results [29]; (d) BP results [24] and (d) proposed approach.

TABLE I THIRTEEN

 I CONFIGURATIONS USED TO FILL IN THE UNKNOWN PARTS OF THE PICTURES.

	Setting	Parameters
		Patch's size 5 × 5
	1	Decimation factor n = 3 Search window 80 × 80
		Sparsity-based filling order
	(default)
	2	default + rotation by 180 degrees
	3	default + patch's size 7 × 7
	4	default + rotation by 180 degrees + patch's size 7 × 7
	5	default + patch's size 11 × 11
	6	default + rotation by 180 degrees + patch's size 11 × 11
	7	default + patch's size 9 × 9
	8	default + rotation by 180 degrees + patch's size 9 × 9
	9	default + patch's size 9 × 9 + Tensor-based filling order
	10	default + patch's size 7 × 7 + Tensor-based filling order
	11	default + patch's size 5 × 5 + Tensor-based filling order
	12	default + patch's size 11 × 11 + Tensor-based filling order
	13	default + rotation by 180 degrees + patch's size 9 × 9 + Tensor-based filling order

TABLE II RUNNING

 II TIME IN FUNCTION OF THE NUMBER OF MISSING PIXELS.

	Picture	Resolution	Missing	Inpainting	SR	Total
			areas	and LBP
	Elephant	480 × 320	17%	32s	1m58s	2m30s
	SnowBall	480 × 320	13%	22s	1m36s	1m58s
	Tiger	480 × 320	28%	59s	2m36s	3m35s
	Soldier	320 × 480	30%	51s	2m39s	3m30s
	Cow	600 × 400	13%	40s	2m11s	2m51s

THE RUNNING TIME IS GIVEN FOR THE LOW-RESOLUTION INPAINTINGS AND THE SUPER-RESOLUTION.