Jan Eric Kyprianidis

John Collomosse

Tinghuai Wang

Tobias Isenberg

State of the 'Art': A Taxonomy of Artistic Stylization Techniques for Images and Video

Keywords: Image and Video Stylization, Non-photorealistic Rendering (NPR), Artistic Rendering. !

This paper surveys the field of non-photorealistic rendering (NPR), focusing on techniques for transforming 2D input (images and video) into artistically stylized renderings. We first present a taxonomy of the 2D NPR algorithms developed over the past two decades, structured according to the design characteristics and behavior of each technique. We then describe a chronology of development from the semi-automatic paint systems of the early nineties, through to the automated painterly rendering systems of the late nineties driven by image gradient analysis. Two complementary trends in the NPR literature are then addressed, with reference to our taxonomy. First, the fusion of higher level computer vision and NPR, illustrating the trends toward scene analysis to drive artistic abstraction and diversity of style. Second, the evolution of local processing approaches toward edge-aware filtering for real-time stylization of images and video. The survey then concludes with a discussion of open challenges for 2D NPR identified in recent NPR symposia, including topics such as user and aesthetic evaluation.

INTRODUCTION

A S the advent of photography stimulated artistic diversity in the late 19 th century, so did the successes of photorealistic computer graphics in the early nineties motivate alternative techniques for rendering in non-photorealistic styles. Two decades later, the field of non-photorealistic rendering (NPR) has expanded into a vibrant area of research covering a plethora of expressive rendering styles for the visual communication: exploded diagrams [START_REF] Li | Automated generation of interactive 3D exploded view diagrams[END_REF], false color [START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF], [START_REF] Reinhard | Colour transfer between images[END_REF], and artistic styles such as painterly [START_REF] Bousseau | Video watercolorization using bidirectional texture advection[END_REF], [START_REF] Zeng | From image parsing to painterly rendering[END_REF] and constrained palette rendering [START_REF] Mould | Stylized black and white images from photographs[END_REF], [START_REF]Artistic thresholding[END_REF]. It is this latter category of artistic rendering (AR) that forms the subject of this survey; specifically, techniques focusing on artistic stylization of two-dimensional content (photographs and video) to which we refer as image-based artistic rendering (IB-AR).

IB-AR's origins reach back to seminal works exploring the emulation of traditional artistic media and styles [START_REF] Curtis | Computer-generated watercolor[END_REF], [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF], [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF], [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF], [START_REF] Salisbury | Orientable textures for image-based pen-and-ink illustration[END_REF]. Today, IB-AR has diversified into a highly cross-disciplinary activity, which builds upon computer vision (CV), perceptual modeling, human computer interaction (HCI), and computer graphics. Many classic IB-AR problems have been found to closely relate to longstanding problems in computer graphics or computer vision; for example, video cartooning [START_REF]Stroke surfaces: Temporally coherent non-photorealistic animations from video[END_REF], [START_REF] Wang | Video tooning[END_REF] and its relationship to video matting and automated rotoscoping [START_REF] Agarwala | Keyframe-based tracking for rotoscoping and animation[END_REF]. In many cases computer graphics problems have benefited from or motivated entirely new computer vision research. Similarly, the goal of much IB-AR researchthat of producing a creative or artistic tool-demands a careful, user-led HCI design process.

Despite several years of discipline convergence and the resulting improvements in aesthetic quality and diversity, there have been few surveys of the IB-AR literature in the past decade. Common references for IB-AR are the texts of Gooch and Gooch [START_REF] Gooch | Non-photorealistic Rendering[END_REF] and Strothotte and Schlechtweg [START_REF] Strothotte | Non-photorealistic Computer Graphics[END_REF], both of which surveyed pre-2000 techniques (Sec. 3). The majority of other survey material takes the form of conference tutorials; yet these primarily focus upon illustrative visualization [START_REF] Ma | Recent advances in non-photorealistic rendering for art and visualization[END_REF] or NPR for 3D graphics and games [START_REF] Mcguire | Stylized rendering in games[END_REF]. This survey follows up a recent tutorial [START_REF] Collomosse | Artistic stylization of images and video[END_REF] by some of the authors at Eurographics 2011, prior to which the most recent major conference tutorials on the topic were by Hertzmann et al. [START_REF] Ma | Recent advances in non-photorealistic rendering for art and visualization[END_REF] in 2003 and Green et al. [START_REF] Green | Non-photorealistic rendering[END_REF] in 1999. Also, a number of web-based curated bibliographies are available via Reynolds [START_REF] Reynolds | Stylized depiction in computer graphics[END_REF] (to 2004), Schlechtweg [START_REF] Schlechtweg | NPR literature[END_REF] (to 2007), and Stavrakis [145].

This article delivers a comprehensive view of the IB-AR landscape, covering classical and contemporary techniques while offering two perspectives. First, we provide an up-to-date taxonomy of IB-AR techniques in which algorithms are grouped according to the family of techniques used (e. g., nonlinear filters, region segmentation) or design characteristics (e. g., local greedy, or global optimization approaches to rendering).

Second, we present IB-AR's development in chronological order, from the early nineties to the modern day (c. 2011), to reflect the contemporaneous development of techniques clustered together in our taxonomy; for example local methods, followed later by global methods. We first document 'classical' (pre-2000) IB-AR and so introduce the key concepts and algorithms that continue to underpin and influence more contemporary methods (Sec. 3). These classical algorithms focused on the strokebased rendering (SBR) paradigm [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF], [START_REF]Tutorial: A survey of stroke-based rendering[END_REF] with increasing Fig. 1. Chronology of IB-AR development. From the semi-automated SBR systems of the early nineties, to increasingly automated systems drawing upon image processing. Later the aesthetic gamut is enhanced through more sophisticated computer vision and edge-aware filtering. Recently attention returns to user interaction, raising new questions around the evaluation of aesthetics and usability. levels of automation and sophistication in stroke placement and driven by low-level image processing (typically the Sobel operator).

Next, we describe how the early convergence of computer graphics and image processing developed, enabling IB-AR to draw increasingly upon the more sophisticated image analysis offered by contemporary computer vision algorithms (Sec. 4). One consequence of the increasingly sophisticated interpretation or 'parsing' of the image was a divergence from SBR to alternative forms of rendering primitives: the use of regions and tiles which, in turn, unlocked greater diversity in the gamut of styles available to IB-AR. In line with the trend toward more complex image analysis, we also observe IB-AR to be defined increasingly as a goaldirected task-drawing upon global optimization rather than local approaches. Although these goals were initially defined at the low level of image artifacts (e. g., image gradient), the description of these goals later evolved to include higher level concepts such as perceptual salience measures and even emotional or 'affective' contexts.

In parallel with the trend toward more sophisticated scene analysis, IB-AR benefited from the emerging popularity of anisotropic and edge-preserving forms of filters in computer graphics (Sec. 5). On the one hand, such operations lacked high-level image 'understanding', limiting their artistic gamut to painterly, sketchy, and cartoon styles. On the other hand, their simplicity led to real-time speeds on GPU hardware, making them practical for video processing-and applicable to footage (e. g., water, smoke, fur) that is otherwise challenging to parse using vision methods such as segmentation.

Concluding, we catalog a number of challenges that remain outstanding in IB-AR (Sec. 6).

TAXONOMY OF IB-AR TECHNIQUES

Early prototype IB-AR systems followed the SBR paradigm and synthesized artistic renderings by incrementally compositing virtual brush strokes whose color, orientation, scale, and ordering were derived from semi- [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF] or fully automated processes [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF], [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF], [START_REF] Treavett | Statistical techniques for the automated synthesis of non-photorealistic images[END_REF]. The aesthetics of the output generated by a SBR algorithm is, therefore, a function of both the media simulation applied to render each brush stroke and the process by which strokes are positioned and their attributes are set (referred to hereafter as the stroke placement algorithm). Although sometimes described simultaneously in early IB-AR papers, the problems of media emulation and stroke placement may be considered de-coupled. The curved spline strokes placed by Hertzmann's [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] algorithm could be rendered by sweeping various brush models along their trajectories, to emulate thick oil paint, crayon, charcoal, or pastel, to name but a few different media. It is, therefore, not surprising that IB-AR has evolved in parallel with increasingly sophisticated media emulation models; from simple simulations of hairy brushes [START_REF] Strassmann | Hairy brushes[END_REF] to full multi-layered models of pigment diffusion and bi-directional transfer between brush and canvas [START_REF] Curtis | Computer-generated watercolor[END_REF].

A detailed exposition of media simulation warrants a survey in its own right, but in this work we focus only on the problem of stroke placement, or more generally, the placement of artistic rendering primitives (regions, strokes, stipples, tiles). We also survey nonlinear filters that introduce an anisotropy that conveys the impression of stroke placement. Accordingly, our taxonomy avoids the categorization of IB-AR purely in terms of media (painterly, sketch, cartoon shading) and instead clusters the space of IB-AR algorithms by the elementary rendering primitive or stylization mechanism employed. We then expand the lower branches of the taxonomy by considering similarities in the nature of the algorithm; local approaches vs. global arrangement strategies, or approaches that address the rendering of outlines vs. the interior of image regions.

Stroke-based Rendering (SBR)

SBR algorithms cover a 2D canvas with atomic rendering primitives according to some process or desired end goal, designed to simulate a particular style. In many SBR algorithms these primitives are the eponymous virtual brush stroke, but the definition of SBR has diversified to primitives including tiles, stipples and hatch marks [START_REF]Tutorial: A survey of stroke-based rendering[END_REF].

Brush Stroke Techniques

The most prevalent form of IB-AR are perhaps SBR algorithms using either short dabs of paint, or long curved brush strokes as rendering primitives. The process of covering the canvas can be categorized broadly as local or global. Local approaches typically drive stroke placement decisions based on the pixels in the spatial neighborhood of the stroke; this can be explicit in the algorithm (e. g., image moments within a window [START_REF] Shiraishi | An algorithm for automatic painterly rendering based on local source image approximation[END_REF], [START_REF] Treavett | Statistical techniques for the automated synthesis of non-photorealistic images[END_REF]) or implicit due to a prior convolution (e. g., Sobel edges). An alteration to the image would thus affect only strokes in the locality. Global methods optimize the placement of all strokes to minimize some objective function. Various strategies have been applied from snake relaxation [START_REF]Paint by relaxation[END_REF], to evolutionary algorithms [START_REF]Genetic paint: A search for salient paintings[END_REF], and Monte-Carlo optimization [START_REF] Szirányi | Optimization of paintbrush rendering of images by dynamic MCMC methods[END_REF]. In all cases the desired objective relates to retention of detail, for example, encouraging maximal retention of visual detail [START_REF]Paint by relaxation[END_REF], [START_REF] Szirányi | Optimization of paintbrush rendering of images by dynamic MCMC methods[END_REF] using low-level operators (e. g., Sobel gradient) or higherlevel measures such as image salience to retain only perceptually important detail [START_REF]Genetic paint: A search for salient paintings[END_REF].

On the more heavily populated 'local' branch of the SBR taxonomy, we partition algorithms into user-assisted and automatic processes-the former typically pre-dating the latter, pointing to a trend toward automation postnineties. The mechanism behind the automation can, as with 'global' SBR, be divided into lower-and higher-level analysis according to the definition of the 'importance' field that guides the emphasis of features in the artwork. In the parallel SBR branch of semi-automated (i. e., userassisted) algorithms, the low/high-level distinction is again mirrored; with early techniques relying on image filters to orient brush strokes [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF] and later work-predating automated measures for emphasis-using gaze trackers to directly harness the perceptual measures inherent in the human visual system [START_REF] Santella | Abstracted painterly renderings using eye-tracking data[END_REF]. In some recent automated algorithms, stroke placement is influenced by even higher-level contextual parameters such as emotion and mood [START_REF] Colton | Emotionally aware automated portrait painting[END_REF], [START_REF] Shugrina | Empathic painting: Interactive stylization using observed emotional state[END_REF]. Most recently, there has been a trend back toward interaction, producing semi-automated tools for painterly video that enable keyframing of the fields used to arrange strokes [START_REF] Kagaya | Video painting with space-timevarying style parameters[END_REF], [START_REF] Lin | Painterly animation using video semantics and feature correspondence[END_REF], [START_REF] O'donovan | AniPaint: Interactive painterly animation from video[END_REF].

For automatic techniques, a clear distinction can be made between those operating over images versus video content. Video extensions of SBR are non-trivial as strokes must not scintillate (flicker) and their motion must match the underlying video content. In the SBR branch of the taxonomy this problem has largely been addressed-though by no means solved-using optical flow. Elsewhere, nonlinear filters and segmentation have been applied.

Mosaicking, Tiling and Stippling

A further sub-category of SBR aims to approximate the image using a medium other than colored pixels or paint, packing image regions with a multitude of atomic rendering primitives. The techniques approximate the image content by either (i) stippling, the distribution of small points (stipples) often for the purpose of tonal depiction; (ii) hatching, the use of line patterns or curves for the same; and (iii) mosaicking algorithms that pack small tiles together.

Stippling IB-AR techniques are closely related to digital half-toning and dithering algorithms that locally approximate regions using dot patterns, either with the sole goal of representing a local brightness or with an additional artistic intent [START_REF]Artistic halftoning: Between technology and art[END_REF]. Many early half-toning techniques developed heuristically informed greedy strategies for populating regions with stipples to avoid artifacts due to aliasing. Such techniques operate at either single or multiple scales, placing dots using local decision making. This culminated most recently in techniques designed to emphasize image structure [START_REF] Pang | Structure-aware halftoning[END_REF], following the trend toward perceptual analysis in SBR. In contrast to half-toning, stippling does not simply decide whether to use a black or a white pixel on a regular grid but tries to place larger dots, with the shared goal to represent the brightness and to (typically) avoid visible patterns. Early stippling used a number of brush-based techniques [START_REF] Deussen | Floating points: A method for computing stipple drawings[END_REF]. However, much as local SBR painterly approaches evolved into global relaxation approaches, so image stippling began to adopt a more global strategy for stipple placement. Recently, goals in stippling are to capture and replicate aspects of the stippling style of artists [START_REF] Kim | Stippling by example[END_REF], [START_REF] Martín | Scale-dependent and example-based grayscale stippling[END_REF] or to be able to reproduce non-repetitive patterns [START_REF] Kopf | Recursive Wang tiles for real-time blue noise[END_REF]. A smaller subset of IB-AR explored the approximation of images using lines and curves. Aside from dedicated image-based hatching approaches [START_REF] Salisbury | Interactive pen-and-ink illustration[END_REF], some techniques grow labyrinthian patterns using spacefilling curves [START_REF] Dafner | Context-based space filling curves[END_REF] or reaction diffusion processes [START_REF] Pedersen | Organic labyrinths and mazes[END_REF] that adapt to the intensity of the image.

Artistic mosaicking algorithms are closely related to packing problems, and so are approached almost universally as global optimization problems. While packing strategies vary widely, they can be categorized into those obeying purely spatial or spatio-temporal constraints. The latter are especially challenging since a balance must be maintained between a faithful approximation of frame content and the introduction of flicker (temporal incoherence) due to frequent update of the tile or glyph chosen to represent a particular spatial region.

Region-based Techniques

Much as SBR in the 1990s relied increasingly on lowlevel image processing (e. g., intensity gradient, moments, optical flow), a trend post-2000 was the emergence of mid-level computer vision in IB-AR. Segmentation is frequently incorporated as step toward parsing image structure, enabling the adaptation of rendering according to the content in regions. In some techniques, SBR algorithms are applied to render the interiors of regions independently [START_REF] Gooch | Artistic vision: Painterly rendering using computer vision techniques[END_REF], [START_REF] Shugrina | Empathic painting: Interactive stylization using observed emotional state[END_REF], [START_REF] Wang | Video stylization for digital ambient displays of home movies[END_REF]. However, the use of regions as rendering primitives in their own right has also given rise to additional styles including cartoon 'flat' shading [START_REF]Stroke surfaces: Temporally coherent non-photorealistic animations from video[END_REF], [START_REF] Wang | Video tooning[END_REF], new materials such as stained glass [START_REF] Mould | A stained glass image filter[END_REF], [START_REF] Setlur | Automatic stained glass rendering[END_REF], felt [START_REF] O'donovan | Felt-based rendering[END_REF], and even emulation of abstract artistic styles [START_REF]Cubist style rendering from photographs[END_REF].

For images, we categorize region-based approaches into those considering the arrangement of rendering primitives (e. g., strokes) within the interiors of regions and those manipulating shape, form, and composition of regions. A further category explores techniques based on image pyramids. Various interactive techniques (human gaze-trackers [START_REF] Decarlo | Stylization and abstraction of photographs[END_REF], importance maps [START_REF] Bangham | The art of scale-space[END_REF]) are used to browse a region containment hierarchy constructed by segmenting successively lower resolution versions of the source image. An image can be rendered at a high level of abstraction by drawing only coarse large regions near the top of the hierarchy, or particular regions can be rendered in greater detail at lower levels. This enables local control over the level of detail. Such methods were among the first region-based IB-AR algorithms and are significant by being among the first to consider perceptual importance.

The consideration of regions in IB-AR has also benefited video stylization, offering an alternative to SBR techniques dependent on optical flow. Video segmentation is a well-studied problem in computer vision and is broadly separated into two categories: techniques that segment frames independently and associate regions over time (2D+t) and those segmenting video as a spatiotemporal (x, y, t) volume (3D). Both methodologies have seen applications to IB-AR for the purpose of cartooning or otherwise stylizing the appearance of video. All techniques share the observation that once video has been coherently segmented into regions (a non-trivial problem), the problem of hatching, sketching, or painting with temporal coherence can be solved by attaching strokes to a rigid [START_REF]Stroke surfaces: Temporally coherent non-photorealistic animations from video[END_REF] or deforming [START_REF] Agarwala | Keyframe-based tracking for rotoscoping and animation[END_REF] region. This frames the problem of IB-AR as one of automated rotoscoping. Finally, when considering regions, it is possible to track and analyze the motion of objects. This gives rise to a complementary form of video stylization-that of artistically manipulating object motion.

Example-based Rendering

Most IB-AR algorithms encode a set of heuristics, typically emulating artistic practice with the goal of faithfully depicting a prescribed style. A complementary approach to IB-AR-example-based rendering pioneered by Hertzmann et al. [START_REF] Hertzmann | Image analogies[END_REF]-learns the mapping between an exemplar pair: a source image and an artist's rendering of that image. The learned mapping can then be applied to render arbitrary images in the exemplar style.

Example-based rendering (EBR) can be categorized as performing either texture or color transfer. Color EBR typically performs a piecewise mapping between the color histograms of two images to effect a nonphotorealistic recoloring. Often there is only weak enforcement of spatial coherence in the color mapping process. By contrast, texture-based EBR shares similarities with patch-based texture in-filling techniques [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF], [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF], which seek to fill holes in images by searching for visually similar patches elsewhere in the image. However, in the case of EBR the patches are not matched within the source image to be rendered but instead within the exemplar source image. The corresponding patch from the exemplar artistic image is then pasted into place in the output rendering. As with texture in-filling, a careful balance must be maintained between fidelity of the patch matching and the spatial coherence in the rendering.

Image Processing and Filtering

Many image processing filters have been explored for IB-AR but few have been recognized so far to produce interesting results from an artistic point of view. This is probably because these filters are often concerned with the restoration and recovery of photorealistic imagery. By contrast, IB-AR generally aims for simplification.

Among the filtering approaches to IB-AR, we distinguish two major categories depending on the domain the techniques operate on. The first is the classical spatial domain where the gray or color value of a pixel is replaced based on the values of its neighboring pixels. Most approaches that have been derived from classical image processing techniques fall into this category. In the second category, techniques operate in the gradient domain [START_REF] Agrawal | Gradient domain manipulation techniques in vision and graphics[END_REF], a relatively sparsely researched area of IB-AR. In the spatial domain, most techniques are automatic processes. Therefore, we subdivide techniques operating in this domain by their type of output; either outlines or stylization of solid areas. Techniques creating outlines can be further classified by the type of edge detector used. We adopt the usual distinction between first and second order derivative methods.

Techniques modifying areas or image regions are further classified into edge-preserving smoothing approaches that employ some form of anisotropic diffusion [START_REF] Weickert | Anisotropic Diffusion in Image Processing[END_REF], approaches based on local image statistics, and approaches based on morphological filtering. Techniques based on the bilateral filter fall into the anisotropic diffusion category since the bilateral filter can be interpreted as fast filter-based approximation of anisotropic diffusion. While fast isotropic variants of the bilateral filter have seen application elsewhere in graphics, IB-AR variants of the bilateral filter were developed to focus on increased quality of separable approximations [START_REF] Kyprianidis | Image abstraction by structure adaptive filtering[END_REF] and focused on the enhancement of anisotropic image structures [START_REF] Kang | Shape-simplifying image abstraction[END_REF].

CLASSICAL STYLIZATION ALGORITHMS

IB-AR arguably began to gain momentum in the early 1990s with semi-automated paint systems such as Haeberli's [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF] that enabled photos to be transformed into impressionist-like paintings with minimal labor. People would click on a photo, each click prompting the generation of a virtual brush stroke of the underlying image color. The introduction of noise prior to this process results in stroke color variation reminiscent of an impressionist painting. Haeberli's system [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF] was motivated by a desire to enrich digital painting by automating the color selection process (reducing the 'time to palette'). Yet the longer-term significance of this work has been to introduce the paradigm of an artificial painting as an ordered list of strokes-whose attributes may be derived partially or fully from photorealistic source content. This concept of stroke-based rendering (SBR) [START_REF]Tutorial: A survey of stroke-based rendering[END_REF] underpins almost all of the IB-AR work developed in the nineties, which sought increasingly to automate and to enhance the sophistication of stroke placement.

Local Algorithms for Stroke Placement

Haeberli's framework [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF] automates the selection of stroke color, and for non-circular brush strokes can also decide stroke orientation by painting strokes orthogonal to the intensity gradient in the source image. However, the system relies upon the user to determine the order and Fig. 3. Adapting Haeberli's framework [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF] to randomly assign stroke size and order leads to loss of salient detail [START_REF] Haggerty | Almost automatic computer painting[END_REF] and motivated later the use of image processing operators for stroke placement.

scale of strokes. The size and sequencing of stroke overpainting is crucial to producing results with an acceptable aesthetic and without any loss of salient detail. An early attempt to automate Haeblerli's pipeline is described by Haggerty [START_REF] Haggerty | Almost automatic computer painting[END_REF] using pseudo-random stroke size and painting order. With this solution strokes can be painted at sizes disproportionate to the features they represent. Also, large strokes painted in non-salient regions may over-paint nearby finer-scale strokes. Both result in a loss of detail in the painting (Fig. 3).

Early Pen-and-Ink Hatching Algorithms

Early semi-automated systems for rendering in pen-andink and cross-hatched styles follow a similar pattern of development. Salisbury et al. [START_REF] Salisbury | Interactive pen-and-ink illustration[END_REF] developed a semiautomated hatching system that oriented textures according to the underlying image gradients, much as Haeberli's oriented brush strokes [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF]. A multi-scale extension of the system [128] offered aesthetic improvements in the viewing of hatching patterns at multiple scales. Regionbased editing and manipulation of the underlying image gradient was later introduced by Salisbury et al. [START_REF] Salisbury | Orientable textures for image-based pen-and-ink illustration[END_REF], enabling discontinuities and swirl effects to be manually introduced, improving tool expressiveness.

Early Painterly Rendering Algorithms

The first automatic solution to IB-AR described in full detail within the literature was a painterly rendering tool proposed by Litwinowicz [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF]. This system placed rectangular brush strokes at regular intervals on the canvasretaining a random painting order but introducing the innovation of clipping strokes to thresholded Sobel edges in the source image. Strokes are rectangular, and oriented using Sobel gradients as done previously [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF], [START_REF] Haggerty | Almost automatic computer painting[END_REF]. The clipping process results in crisp edges that mitigate against strokes from unimportant regions over-painting more important regions. A further contribution was the interpolation of image gradient within flat, near textureless regions. Such regions result in spurious gradient directions, which create a chaotic orientation of strokes. Litwinowicz applied thin-plate splines to interpolate stroke orientation from strokes at strong edges. Later, Hays and Essa [52] adopted a similar technique for interpolation in their video painting algorithm.

Most subsequent SBR algorithms follow Litwinowicz's [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF] approach; driving the stroke placement as a function of the Sobel gradient. A notable exception is Treavett and Chen's [START_REF] Treavett | Statistical techniques for the automated synthesis of non-photorealistic images[END_REF] adoption of image moments computed local to each pixel. Analogous to the behavior of gradient-based approaches, their algorithm paints rectangular strokes orthogonal to the direction of maximal variance (i.e., the minor eigenvector).

Local Coarse-to-fine IB-AR Algorithms

Constant-sized rectangular strokes, even after clipping, generate an artificial regularity that could degrade the resulting aesthetic. Hertzmann [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] was the first to address this issue by proposing curved brush strokes of multiple sizes. The algorithm operates over a low-pass pyramid-a successive Gaussian blurring of the source image at increasing scales. Each scale of the pyramid corresponds to a layer in the painting; the coarsest scale is painted as the first layer with large strokes. Successively finer scales of the pyramid are painted with proportionately smaller strokes. In each iteration of the layer painting process, strokes are placed according to the gradient information at the stroke's position. However, if the image content in a given neighborhood does not differ significantly from the corresponding region in the coarser scale, then no strokes are placed there. Thus large coarse strokes often remain visible in flatter areas, whereas fine strokes appear around edge detail.

The use of curved brush strokes was a further key innovation of this technique. Given a starting or seed pixel, a sequence of spline control points is generated by iteratively hopping between pixels normal to the direction of the image gradient (Fig. 4). The pixel hopping process terminates when a significant change in color occurs or a predefined maximum length is reached. The resulting sequence of control points are rendered using a piecewise cubic β-spline, with color averaged from the visited pixels. A thick brush stroke along the spline can then be produced, either by sweeping a circular brush along its trajectory or by following a triangulation scheme based on normals to the spline trajectory. The latter enables texturing or bump-mapping of the stroke to produce a convincing oil-paint effect [START_REF]Fast paint texture[END_REF]. Alternatively, more sophisticated brush-canvas models may be driven by the spline trajectories, e. g., to create watercolor effects [START_REF] Curtis | Computer-generated watercolor[END_REF].

Hertzmann's algorithm [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] has influenced many subsequent IB-AR approaches incorporating coarse-tofine rendering [START_REF] Hays | Image and video based painterly animation[END_REF], [START_REF]Paint by relaxation[END_REF], [START_REF] Lin | Painterly animation using video semantics and feature correspondence[END_REF], [START_REF] Shugrina | Empathic painting: Interactive stylization using observed emotional state[END_REF], [START_REF] Zeng | From image parsing to painterly rendering[END_REF]. Shiraishi and Yamaguchi [START_REF] Shiraishi | An algorithm for automatic painterly rendering based on local source image approximation[END_REF] also extended the image moment-based painterly technique of Treavett and Chen [START_REF] Treavett | Statistical techniques for the automated synthesis of non-photorealistic images[END_REF] to operate in multiple passes using windows of decreasing size. Multi-resolution rendering image analysis was adopted soon afterwards by half-toning algorithms that similarly distributed rendering primitives (stipples or short lines) across a low-pass pyramid [START_REF] Streit | Importance driven halftoning[END_REF]. Until this time, most stippling algorithms had focused on single-scale local decision-making for stroke placement [START_REF] Ostromoukhov | Pseudo-random halftone screening for colour and black&white printing[END_REF], [START_REF] Ostromoukhov | Rotated dispersed dither[END_REF] (much as early SBR did [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF]). The curve tracing algorithm became a common approach for stroke placement [START_REF]Genetic paint: A search for salient paintings[END_REF], [START_REF] Hays | Image and video based painterly animation[END_REF], [START_REF] Zeng | From image parsing to painterly rendering[END_REF]. Moreover, the curve tracing process may be considered an approximation to an Euler integration scheme, common in flow field visualization. This is significant because many of the image filtering approaches to IB-AR developed in more recent years (Sec. 5) adapted a similar approach to perform, for instance, line integral convolution (LIC) [START_REF] Cabral | Imaging vector fields using line integral convolution[END_REF] guided by a smoothed vector field.

Video Stylization

The extension of SBR to video stylization is non-trivial, since independent per-frame rendering of the image sequence will result in a distracting flickering or scintillation in the animation. This arises either due to noise in the source imagery, exacerbated by differential-based operators (such as the Sobel filter) that drive the stroke placement, or due to non-determinism introduced by the IB-AR algorithm itself. Holding the stroke placement constant according to the first frame removes this issue, but leaves the viewer with the impression of content moving behind frosted glass (coined by Meier [START_REF] Meier | Painterly rendering for animation[END_REF] as the shower door effect). It is, therefore, desirable that:

1) the motion of brush strokes both matches the motion of the underlying video content, and 2) the animated sequence is flicker free. If both of these properties are satisfied, then the stylized animation is said to be temporally coherent. Flicker is a particularly sensitive issue in painterly animation [START_REF] Hertzmann | Painterly rendering for video and interaction[END_REF] and in video stylization more broadly where temporal coherence remains an open challenge (Sec. 6).

Litwinowicz's seminal paper [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF] also contributed the first extension of an IB-AR painting algorithm to video. The algorithm places constant-sized rectangular strokes upon the first frame (as per Sec. 3.1.2), and translates those strokes to new locations according to an estimate of the optical flow between frames. A secondary process is introduced to govern stroke density because, over time, stroke motion may result in regions becoming too densely or too sparsely populated. The solution is to perform a Delaunay triangulation over stroke centers, and to identify bounded regions that fall below or exceed an area threshold. In the case of overly dense regions, strokes are deleted at random until the density reaches acceptable levels. In the case of sparsely populated regions, strokes are similarly introduced at random locations within the region. The rendering order of strokes is maintained between frames to reduce flicker and, when strokes are added, they are assigned a random ordering within the list of existing strokes.

When a reliable optical flow estimate is available, the technique performs well. However, forward propagation causes errors in the flow estimate to accumulate. This creates flicker and causes strokes to drift unnaturally across the rendered frames. This is especially noticeable in flat areas where optical flow tends to perform poorly. The approach was applied in the movie What Dreams May Come, winning an Academy Award in 1999. Green et al. [START_REF] Green | Non-photorealistic rendering[END_REF] report that over 1000 man-hours of manual correction to optical flow fields were required to produce the short painterly scenes in the movie. Nevertheless, optical flow features as a key component of many video painting algorithms [START_REF] Bousseau | Video watercolorization using bidirectional texture advection[END_REF], [START_REF] Hays | Image and video based painterly animation[END_REF], [START_REF] Lu | Interactive painterly stylization of images, videos and 3D animations[END_REF], [START_REF] Park | Motion map generation for maintaining the temporal coherence of brush strokes[END_REF], [START_REF] Wang | Video stylization for digital ambient displays of home movies[END_REF].

In the late nineties real-time optical flow was impractical, leading Hertzmann and Perlin [START_REF] Hertzmann | Painterly rendering for video and interaction[END_REF] to present an alternative video painting technique amenable to interactive rendering: a "Living Painting." They proposed the use of frame differencing to identify regions exhibiting significant change over time. By subtracting and thresholding consecutive video frames, a map of changed areas requiring repainting is produced. Hertzmann's [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] curved stroke rendering algorithm (Sec. 3.2) is used to render the first frame, and to 'paint over' the regions exhibiting large changes in subsequent frames.

A limitation of most SBR algorithms is that stroke placement decisions have to be performed in sequential order, making parallelization difficult. Notable examples addressing this issue are Lu et al.'s [START_REF] Lu | Interactive painterly stylization of images, videos and 3D animations[END_REF] modeling of stroke placement using a stochastic process and interactive SBR techniques like Schlechtweg et al.'s [134] RenderBots system and the work by Schwarz et al. [START_REF] Schwarz | Modeling with rendering primitives: An interactive nonphotorealistic canvas[END_REF], which like Renderbots, also relies upon autonomous agents interacting in parallel.

VISION FOR STYLIZATION

An increasing reliance upon local image processing techniques (predominantly the Sobel gradient operator) was instrumental in transforming the interactive IB-AR systems of the early nineties into fully automatic rendering systems. Continuing this trend towards deeper image analysis, a major trend post-nineties was the tendency to rely increasingly upon higher-level computer vision to guide artistic rendering. This trend began with the adoption of mid-level computer vision methods, specifically the use of image segmentation.

Perceptual Measures for Stylization

DeCarlo and Santella [START_REF] Decarlo | Stylization and abstraction of photographs[END_REF] were among the first to apply image segmentation in IB-AR. Images were segmented using a variant of mean-shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], [START_REF] Meer | Edge detection with embedded confidence[END_REF] at multiple downsampled resolutions. A scale-space hierarchy was formed by identifying regions at a coarse scale that overlapped and shared color similarity with regions at the adjacent finer scale. This hierarchical representation enabled an image to be rendered in a highly abstract form (using coarse regions from the top of the pyramid), or for certain regions to be locally decomposed into finer grain regions by descending the hierarchy. The process was driven by gaze tracking. The viewer was presented with the source image, and the duration and location of their fixations recorded. The level of rendering detail within each region of the image was determined (Fig. 5). The regions were rendered using flat color shading, with a smoothed black outline derived from Canny edges. A similar hierarchical rendering system was developed by Bangham et al. [START_REF] Bangham | The art of scale-space[END_REF] using a 2D extension of sieves-an alternative form of scale space arising from morphological erosion and dilation at varying spatial scales. Sieves are advantageous due to their preservation of sharp corners and discontinuities, which are lost in a Gaussian scale space. Bangham et al. use a binary mask rather than gaze to indicate region importance.

The use of perceptual importance to drive emphasis in IB-AR marked a departure from the image gradient driven algorithms of the late nineties. Such techniques scaled strokes in inverse proportion to edge magnitude and so conserved all fine (i. e., high frequency) detail in the painting unless interactively down weighted, e. g., using manually specified masks [START_REF]Paint by relaxation[END_REF]. By emphasizing only the perceptually important detail, IB-AR began to more closely emulate the practice of artists, who depict only the salient detail of a scene whilst abstracting away extraneous detail.

While Decarlo and Santella harnessed the power of the human visual system to generate their importance maps, a number of IB-AR algorithms were developed using fully automated measures of salience to drive emphasis in renderings. The first example of such an approach [START_REF] Collomosse | Painterly rendering using image salience[END_REF] used a local algorithm to place strokes, scaled and ordered in inverse proportion to image salience. Salience b c a Fig. 6. Global optimization algorithms for painting. (a) Curved β-spline stroke paintings produced by Hertzmann's greedy algorithm [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] and global optimization [START_REF]Paint by relaxation[END_REF]. Note the improvements in precision for all edge detail. (b)-(c) Global optimization for painting using GA [START_REF]Genetic paint: A search for salient paintings[END_REF] guided by a salience field (manually damped in region B). Note the difference in emphasis between the non-salient shrubbery and the salient sign detail; enlargement for region A compares against source (upper) and Litwinowicz's [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF] method (lower).

was correlated with rarity, by identifying outliers within a distribution of Gaussian derivatives of varying scale and orientation. This definition was later extended to take visibility and local image features into account [START_REF]Genetic paint: A search for salient paintings[END_REF].

Artistic Rendering as a Global Optimization

Most IB-AR algorithms in the late 1990s treated painting as a local process: pixels in the image are examined in turn and strokes placed according to various heuristics. Although the image might be processed repeatedly at different scales (producing successive coarse-to-fine layers of strokes [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF], [START_REF] Hertzmann | Painterly rendering for video and interaction[END_REF], [START_REF] Shiraishi | An algorithm for automatic painterly rendering based on local source image approximation[END_REF]), once a particular stroke is placed there is no subsequent adjustment of its position or attributes to improve the painting in a global sense. Each stroke is placed according to information in its local spatial neighborhood only. By contrast, global approaches to IB-AR iteratively optimize the position of rendering elements (e.g. brush strokes, or stipples) to minimize some objective function defined to describe the 'optimality' according to one or more heuristics. Although such an IB-AR approach was first mentioned by Haeberli [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF], it was not until a decade later that the first algorithmic solution was described for painterly rendering [START_REF]Paint by relaxation[END_REF].

Global Approaches to SBR: Brush-based

Hertzmann [START_REF]Paint by relaxation[END_REF] extended his local curved stroke painterly algorithm [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] by treating each stroke as an active contour or snake. A snake is a piecewise curve, whose control points are iteratively updated to minimize an energy function. The energy function for a snake is a weighted sum of 'internal' energy parameters, guarding against sharp discontinuities or 'kinks' appearing along the curve and 'external' energy parameters. For example, the original snakes algorithm [START_REF] Kass | Snakes: Active contour models[END_REF] moves the curve incrementally closer to an edge over time by minimizing the distance between the curve and edges in the image. In Hertzmann's optimization [START_REF]Paint by relaxation[END_REF], a single painting is created from the source photograph and iteratively updated to converge toward an aesthetic ideal. Strokes are placed in their initial positions on the canvas using the existing curved stroke painting algorithm [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF]. An iterative optimization phase then begins in which snake strokes are added, deleted, or moved over the canvas to minimize the objective function evaluating painting quality. A high quality painting is deemed to be one that matches the source image as closely as possible, using a minimal number of strokes but covering the maximum area of canvas in paint. The objective function is a weighted summation assessing the current painting P with respect to these attributes:

E app (P) = ω 1 width ∑ x=1 height ∑ y=1 |P(x, y) -G(x, y)| (1) E area (P) = ω 2 ∑ S∈P Area(S) (2)
E nstr (P) = ω 3 • (strokes in P)

(3)

E cov (P) = ω 4 • (unpainted pixels in P) (4)
The weights ω 1..4 control the influence of each quality attribute and are determined empirically. The first term E app reflects how closely the painting depicted by the strokes resembles the source image. The other energy terms refer to area of strokes (E app ), number of strokes (E nstr ), and coverage of the canvas (E cov ). Expression S ∈ P refers to all strokes comprising painting P. Summing the areas of strokes in Eq. ( 2) yields a value analogous to the quantity of paint used in the painting. A similar model of stroke redundancy was presented in the global approach of Szirányi et al. [START_REF] Szirányi | Optimization of paintbrush rendering of images by dynamic MCMC methods[END_REF], using a Monte-Carlo Markov Chain (MCMC) optimization.

Fig. 6(a) demonstrates the improvements in stroke accuracy obtained using optimization. However, the high level of detail returned within the painting can cause the rendering to tend back toward photorealism and is inconsistent with the selective process by which artists emphasize salient detail. Collomosse and Hall [START_REF]Genetic paint: A search for salient paintings[END_REF] make use of a genetic algorithm (GA) to search the space of possible paintings, locating the 'optimal' painting for a given photograph. The optimality criterion measures the correlation between detail in the painting and the salience map of the source image (Fig. 6(b)). Optimization techniques have been also applied to nonpainterly styles, for example, Agarwala's 'Snake-Toonz' technique for rendering cartoons semi-automatically from video using snakes [START_REF] Agarwala | SnakeToonz: A semi-automatic approach to creating cel animation from video[END_REF]. To form a set of closed regions, the initial video frame is interactively annotated by a user with curves that are 'snapped' to adjoin neighboring curves. The regions are tracked over time by iteratively relaxing the snakes on each video frame and flat-shaded to create a cartoon appearance.

Global strategies for rendering became increasingly common in IB-AR as the processing of input footage increased in sophistication; especially tiling and packing IB-AR algorithms that create mosaic art (Sec. 4.4).

Global Approaches to SBR: Tonal Depiction

A purely tonal IB-AR depiction is achieved using stippling. Although placing stipple dots is inherently a spatially local process, a number of algorithms seek to selectively enhance their output according to more global constraints. Such constraints reflect the behavior of stipple artists who strive for a globally even distribution of stipple dots that still reflects the local gray value of the image to be represented. The earliest stipple techniques achieved this goal using Lloyd's method [START_REF] Lloyd | Least squares quantization in PCM[END_REF], [START_REF] Mccool | Hierarchical Poisson disk sampling distributions[END_REF], which computes the Voronoi diagram of a point distribution and then moves each dot to its respective Voronoi region's center of mass. After iterating this process a number of times, the point distribution becomes even; and thus Lloyd's method yields better results than a straightforward randomized dart throwing. Lloyd's method, however, does not take grey values into account and, thus, was used initially only in a local, brush-based manner [START_REF] Deussen | Floating points: A method for computing stipple drawings[END_REF]. Secord [START_REF] Secord | Weighted Voronoi stippling[END_REF] solved this problem by introducing weighted Voronoi-based stippling to enable a global and automatic processing (Fig. 7(a)). This method was later extended to shapes beyond simple points [START_REF] Dalal | A spectral approach to NPR packing[END_REF], [START_REF] Hiller | Beyond stippling-Methods for distributing objects on the plane[END_REF], [START_REF] Secord | Fast primitive distribution for illustration[END_REF].

One issue with Lloyd's method [START_REF] Lloyd | Least squares quantization in PCM[END_REF], [START_REF] Mccool | Hierarchical Poisson disk sampling distributions[END_REF] is that it introduces a regularity of stipple dot placement, leading to visual artifacts such as lines or circles (Fig. 7(a)) which are typically avoided by artists [START_REF] Hodges | The Guild Handbook of Scientific Illustration[END_REF]. These artifacts can be mitigated in IB-AR by adding randomness as done, e. g., by the RenderBots algorithm [134]. In practice, however, random noise can only partially remove artifacts. A better way to avoid the patterns is to employ non-repetitive stippling (Fig. 7(b)). Kopf et al. [START_REF] Kopf | Recursive Wang tiles for real-time blue noise[END_REF] employ non-repetitive Wang tiling, compute an even distribution per tile, and describe how to seamlessly match the distributions of neighboring tiles. The result is an artifact-free distribution that also facilitates zooming into the stipple images. When stippling in a more advanced animated fashion (e. g., in videos), however, it is also important to ensure that the stipples follow the depicted objects, which was achieved, for example, by Vanderhaeghe et al. [START_REF] Vanderhaeghe | Dynamic Point Distribution for Stroke-based Rendering[END_REF].

In addition to globally uniform coverage, researchers have guided stipple distributions according to perceptual salience or image structure. Qu et al. [START_REF] Qu | Richnesspreserving manga screening[END_REF], for example, preserve the visual richness of color photographs by applying a range of stippling and related bitonal techniques to different regions in the image. In an even more local approach, Mould [START_REF]Stipple placement using distance in a weighted graph[END_REF] proposes a path search within a weighted regular graph that represents the image in order to place stipple dots on chains to represent meaningful edges in the image. In a later approach, Li and Mould [START_REF] Li | Structure-preserving stippling by priority-based error diffusion[END_REF] use a priority-based error diffusion technique to place those stipples first that represent and preserve the image's structure best. A related sub-domain of stippling deals with the specific subject domain of human faces in which it is particularly important to preserve certain structures. Inspired by hand-made hedcut illustrations, several approaches have addressed this issue [START_REF] Kim | Feature-guided image stippling[END_REF], [START_REF] Kim | Automated hedcut illustration using isophotes[END_REF], [START_REF] Son | Structure grid for directional stippling[END_REF], aiming to place the stipple dots so as to introduce visible artifacts, in order to emphasize and support the shape of the depicted faces. By contrast, most stippling algorithms seek to minimize such artifacts-and in this sense such techniques are related to image-based hatching approaches [115], [START_REF] Salisbury | Orientable textures for image-based pen-and-ink illustration[END_REF] that also take structure into account in placing marks.

For many classes of greyscale image content, the above stippling methods generate aesthetically acceptable distributions. However, these may not be representative of those human artists would generate. Therefore, another recent trend in stippling is to use example-based approaches. Kim et al. [START_REF] Kim | Stippling by example[END_REF] generate stipple dot distributions with the same statistical properties as those created by artists. While their approach is able to handle sparse point distributions well, it does have issues with point densities in which stipple dots start to merge. To address this issue, Martín et al. [START_REF] Martín | Scale-dependent and example-based grayscale stippling[END_REF] treat the stipples not simply as black dots but use greyscale dot scans and aim to reproduce stippling at the correct output resolution. They base the distribution on a globally applied half-toning technique and resort to randomness to avoid the appearance of a grid. The approach achieves satisfactory stipple merging, with distributions matching that of manual stippling [START_REF] Maciejewski | Measuring stipple aesthetics in hand-drawn and computer-generated images[END_REF]. The use of learnable rather than procedurally prescribed artistic models as in these last two techniques has seen increased adoption within IB-AR. We now describe this area of example based rendering in greater detail. to learn the analogous transformation A → A such that new source images B might be transformed into artistic renderings B in the same visual style as A . There are two main approaches to such example-based rendering (EBR): methods seeking to perform texture transfer (typically performed by modulating the luminance channel) and those focusing on color transfer leaving texture constant.

Rendering by Example

Texture by Analogy

The majority of artistic EBR algorithms focus on the transfer of artistic texture, and borrow from the nonparametric patch-based methods used for texture synthesis and photo in-painting. Such methods (e. g., due to Efros et al. [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF], [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF]) in-fill from the edges of 'holes' in an image-iteratively copying patches from elsewhere in the image that share similarity with adjacent texture. Typically such methods seek to minimize pixel difference locally at the copied patch and more globally within the image using a smoothness constraint.

In Hertzmann et al.'s image analogy work [START_REF] Hertzmann | Image analogies[END_REF], a mapping is learned between patches in A and corresponding patches in A . Approximate nearest-neighbor (ANN) is then used to look up each patch in B and replace with the corresponding patch in A . PCA is used to reduce the dimensionality of the search, which can be time-consuming for ANN over large dimensions (patch sizes). Only the normalized luminance channel is considered. The global smoothness prior enforced in this framework resembles that of Ashikhmin [START_REF] Ashikhmin | Fast texture transfer[END_REF]. A recent extension of image analogies incorporates edge orientation to influence patch choice [START_REF] Lee | Directional texture transfer[END_REF], echoing the gradient alignment strategies of SBR algorithms. Stippling patterns have also been learned and applied through example (see Sec. 4.2.2). In recent work, Zhao et al. [170] learn stroke patterns for the domain specific task of portrait painting by example.

Due to their application in texture synthesis, photorealistic EBR algorithms have attracted significant attention over the past decade. A number of extensions to animated sequences have been presented for general video [START_REF] Schödl | Video textures[END_REF], [START_REF] Wei | Fast texture synthesis using tree-structured vector quantization[END_REF]. Video EBR is challenging due to the problem of constraining patch choice to satisfy not only local and global spatial coherence terms but also temporal coherence. Hashimoto et al. [START_REF] Hashimoto | Creating various styles of animations using example based filtering[END_REF], for example, adopt optical flow as a guide to propagate choices over time.

Color Transfer

Manipulating color tone can affect the mood of an artistically rendered image, and forms a useful addition to the IB-AR toolbox. The majority of color transfer techniques are based on modifying the color histogram of a target image to resemble that of a source. Typically, this is performed in an (idealized) de-correlated space such as CIELab. Early approaches model the histogram as unimodal, equalizing the mean and variance of the source and target image (either as three 1D per-channel operations [START_REF] Reinhard | Colour transfer between images[END_REF] or in 3D space [START_REF] Neumann | Color style transfer techniques using hue, lightness and saturation histogram matching[END_REF]). More sophisticated approaches adapt to edges by considering image gradients [START_REF] Xiao | Gradient-preserving color transfer[END_REF] or perform matching of the histogram at multiple scales [START_REF] Pouli | Progressive color transfer for images of arbitrary dynamic range[END_REF].

Region-based IB-AR Algorithms

Initially proposed by DeCarlo and Santella [START_REF] Decarlo | Stylization and abstraction of photographs[END_REF] as a mechanism for interactive abstraction of photographs (Sec. 4.1), image segmentation has become a cornerstone of many automatic IB-AR algorithms that make rendering decisions based on mid-level structure parsed from the image. The ability to harness structural representations of image content led to greater diversity of style (unlocking styles such as stained glass rendering or compositional artwork such as pseudo-Cubism). Arguably, aesthetics were also open for improvement as style and emphasis could be controlled at a higher level (e. g., regions) rather than in response to low-level features.

Region Painting and Texturing

The earliest region-based IB-AR algorithms focused on painterly rendering and were essentially SBR algorithms that used the shape of the region rather than an image gradient field (as common in pre-2000 SBR) to guide the placement of strokes [START_REF] Gooch | Artistic vision: Painterly rendering using computer vision techniques[END_REF], [START_REF] Kolliopoulos | Image Segmentation for Stylized Non-Photorealistic Rendering and Animation[END_REF]. This produces visually distinct stroke patterns for each homogeneous region, often corresponding to distinct semantic objects in the image. Gooch and Gooch extracted the medial axis of each region and placed strokes along paths aligned to this axis [START_REF] Gooch | Artistic vision: Painterly rendering using computer vision techniques[END_REF]. Kollioupoulus used PCA to determine the principal axis of each 2D region and painted brush strokes parallel to this axis [START_REF] Kolliopoulos | Image Segmentation for Stylized Non-Photorealistic Rendering and Animation[END_REF]. Santella and DeCarlo [START_REF]Visual interest and NPR: An evaluation and manifesto[END_REF] painted regions with Hertzmann's curved brush stroke algorithm [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF] using the image gradient but controlled the level of detail in the rendering using an eye tracker (Sec. 4.1). Shugrina et al. [START_REF] Shugrina | Empathic painting: Interactive stylization using observed emotional state[END_REF] filled region interiors with brush strokes aligned with the principal axis but placed brush strokes on the region boundaries for outlines.

The systems described so far only make use of the color and gradient information within regions. They do not leverage the semantic value of the segmentation, i. e., that image regions map approximately to objects. Zeng et al. [START_REF] Zeng | From image parsing to painterly rendering[END_REF] described a region-based painterly rendering system that classifies texture within regions. The classification drives the type of stroke placed, based on a pre-digitized database of stroke textures from real brushwork mapped to each texture category. In the 'Sisley' system [START_REF] Zhao | Sisley the abstract painter[END_REF], the perceptual relevance of regions was analyzed to selectively abstract the structure of painterly renderings through geometric warping.

Regions have been rendered with more diverse approaches than SBR alone. Mould [START_REF] Mould | A stained glass image filter[END_REF] and later Setlur and Wilkinson [START_REF] Setlur | Automatic stained glass rendering[END_REF] rendered regions with textures to produce a stained glass effect. The latter method sought to classify source image texture within a region, which then drove database selection of a characteristic glass texture used to render that region. In this sense, the technique may be considered a forerunner of the material classification described in Zeng et al.'s [START_REF] Zeng | From image parsing to painterly rendering[END_REF] painterly system. IB-AR algorithms generating mosaicked effects are frequently based on an initial image segmentationtreating rendering as a packing problem (Sec. 4.5.1).

In contrast to algorithms seeking to fill regions with small primitives such as tiles or strokes, a further class of algorithm applies fill effects within regions. Straightforward cartoon or 'flat-shaded' effects may be produced by uniformly filling regions with the mean color of underlying content [START_REF]Stroke surfaces: Temporally coherent non-photorealistic animations from video[END_REF], [START_REF] Decarlo | Stylization and abstraction of photographs[END_REF], [START_REF] Wang | Video tooning[END_REF] and optionally vectorizing and rendering the boundaries. Variants of flat shading using only black and white were presented by Xu and Kaplan [START_REF]Artistic thresholding[END_REF] and sought to depict the underlying image tone whilst discouraging connected regions of similar tone. A greedy optimization is used to solve a 2-class map coloring problem. Multi-pass (coarse to fine) global optimization approaches to black and white region shading were presented by Mould and Grant [START_REF] Mould | Stylized black and white images from photographs[END_REF]. Anisotropic shading effects have also been explored such as felting [START_REF] O'donovan | Felt-based rendering[END_REF] or color sketching [START_REF] Wen | Color sketch generation[END_REF].

Deformation and Composition

Although most region-based IB-AR algorithms focus on the shading or texturing of regions, some manipulate geometry for artistic effect. Song et al. [START_REF] Song | Arty shapes[END_REF] classify regions into one of several canonical shapes and replace regions with those shapes to create a simplified shape rendering resembling a paper cut out. Region deformation was also employed to warp regions into superquadric shapes reminiscent of Cubist renderings [START_REF]Cubist style rendering from photographs[END_REF]. This work also re-arranges the position of regions in order to create abstract compositions; arguably styles such as Cubism could not be generated without region-based analysis. Shape simplification was also explored by Mi et al. [START_REF] Mi | Abstraction of 2D shapes in terms of parts[END_REF] through decomposition into parts rather than substitution with simpler shapes [START_REF] Song | Arty shapes[END_REF].

Region Tiling and Packing Algorithms

A considerable volume of IB-AR literature addresses the arrangement of a multitude of small tiles (from regular shapes to irregular pictograms) to form artistic representations. These mosaicking algorithms are typically phrased as optimization problems seeking to maximize coverage of a 2D region, whilst minimizing tile overlap. The tile placement is content-aware, penalizing solutions that misalign tiles to cross edges in the image. A spatial coherence term is often introduced to encourage smoothly varying scale and orientation over the tiled region.

Photo and Video Mosaics

The recti-linear tiling of small image thumbnails to approximate a larger image (so called photomosaics) were among the earliest form of synthetic mosaic, inspired by early physical macro-artwork such as Dali's Abraham Lincoln. Thumbnails are often chosen to have a semantic connection to the larger image being created, as in Dali's work. The IB-AR literature describes optimized search strategies for expedited rendering of photomosaics [START_REF] Battiato | Artificial Mosaic by Gradient Vector Flow[END_REF] as well as alternative optimization strategies such as evolutionary search [START_REF] Ciesielski | Evolution of animated photomosaics[END_REF]. Klein et al. [76] extended photomosaics to video, updating elements of the mosaic to approximate video content whilst penalizing frequent changes of a given tile to prevent flicker. Work approximating images with irregular tiles (e. g., jigsaw image mosaics [START_REF] Kim | Jigsaw image mosaics[END_REF]) can be considered extensions of photomosaicking.

Voronoi Methods

The earliest mosaic-like renderings relied on Voronoi diagrams constructed from points randomly seeded over the image [START_REF] Haeberli | Paint by numbers: Abstract image representations[END_REF]. Each Voronoi region was shaded with the mean color of the underlying image. Dobashi et al. [START_REF] Dobashi | A method for creating mosaic images using Voronoi diagrams[END_REF] modified this approach to iteratively relax the position of the Voronoi seeds to better approximate the image using a mean-squared error (MSE) between the source and rendered image. However, the greedy nature of the optimization (iteratively moving seeds within an 8connected neighborhood) led to loss of detail in image areas exhibiting local minima. Several more sophisticated optimization strategies based on Voronoi diagrams evolved from this early work. Faustino et al. [START_REF] Faustino | Simple adaptive mosaic effects[END_REF] place regular tiles instead of relying on Voronoi segments but guide tile placement using Voronoi regions. Voronoi seeds are scattered more heavily along image edges, leading to increased granularity in areas of high-frequency detail. The tiles are scaled in proportion to image size to preserve detail. Grundland et al. [START_REF] Grundland | Stylized multiresolution image representation[END_REF] form Voronoi segments according to both edge strength and image intensity.

Packing and Tessellation methods

Hausner et al. [START_REF] Hausner | Simulating decorative mosaics[END_REF] were the first to address irregular tile shapes through an energy minimization scheme for shape packing. Kim et al.'s [START_REF] Kim | Jigsaw image mosaics[END_REF] jigsaw image mosaics (JIM) extended this approach using an active contour based optimization scheme to minimize the energy function to allow moderate tile deformation. The JIM energy function is a weighted summation of a color term (penalizing deviation of the mosaic from the source image), a gap term (penalizing spaces between tiles), an overlap term (penalizing tile overlap), and a deformation term (penalizing deformation of tiles). The optimization process identifies the contours of tile boundaries initially via a centroidal Voronoi diagram and, treating these contours as a mesh of snakes, relaxes the contours to minimize the JIM energy function. Branch and bound heuristics are used to improve search efficiency (Fig. 9(d)). Orchard and Kaplan [START_REF] Orchard | Cut-out image mosaics[END_REF] describe a fast technique for mosaicking images with irregular tiles, capable also of cropping partial regions from the image database to use as tiles. The work follows up on an earlier specific case of irregular tiling: calligraphic (text) packing [START_REF] Xu | Calligraphic packing[END_REF].

Stylization through text packing was further considered in recent work by [START_REF] Maharik | Digital micrography[END_REF]. Orchard and Kaplan's [START_REF] Orchard | Cut-out image mosaics[END_REF] speedup leverages the FFT for cross-correlation between tiles and underlying content. The frequency domain was also leveraged by Dalal et al. [START_REF] Dalal | A spectral approach to NPR packing[END_REF] to deliver an efficient packing method rather than to match tiles. The technique extends the earlier algorithm of Smith et al. [START_REF] Smith | Animosaics[END_REF]; and whilst slightly slower, allows affine transformation of the tiles during optimization leading to tighter mosaic arrangements. Hurtut et al. [START_REF] Hurtut | Appearance-guided synthesis of element arrangements by example[END_REF] combined the principles of texture modeling and mosaicking to learn statistical distributions of tiles. Their mosaics are sparse tile distributions drawn from a set of tile types (e. g., stars, lines, spirals). Given a sample distribution, their system is able to learn the relative densities and spacings of a mosaic and synthesize similar distributions. Further optimization strategies using graph-cut were also explored by Liu et al. [START_REF] Liu | Generating Classic Mosaics with Graph Cuts[END_REF] (Fig. 9(b)).

Computer Vision for Video Stylization

A major goal in video stylization is temporal coherence; requiring video to exhibit minimal flicker and the rendering primitives (e. g., strokes) to move with the underlying video content. The issue of temporal coherence is discussed in the context of 3D animation in [START_REF] Bénard | State-of-the-Art Report on Temporal Coherence for Stylized Animations[END_REF]. Early algorithms for 2D video stylization were based on per-pixel analysis using optical flow and frame differencing (Sec. 3.3). Temporal incoherence is common in such algorithms [START_REF] Hertzmann | Painterly rendering for video and interaction[END_REF], [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF] since stroke placement decisions are being made on a spatially (per-pixel) and temporally (per-frame) local basis. Higher-level analysis of visual structure, e. g., through computer vision can lead to improved coherence. We now survey two categories of post-nineties algorithms: techniques based on optical flow and segmentation-based methods. A third branch of the video stylization literature applying nonlinear filtering is discussed in Sec. 5.

Visual Stylization through Optical Flow

Approaches that employ optical flow to stylize video were revisited by Hays and Essa [START_REF] Hays | Image and video based painterly animation[END_REF]. To mitigate against temporal incoherence arising from flow estimates, strokes were categorized as weak or strong; the latter in edge areas where gradients are higher. Strong strokes were propagated forward over time as by Litwinowicz [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF] and their orientations used as the basis for interpolating a dense gradient field over the image. Thus, so long as the motion of strong strokes varied smoothly, stroke orientation also varied smoothly. Park and Yoon [START_REF] Park | Motion map generation for maintaining the temporal coherence of brush strokes[END_REF] adopted a similar strong-weak categorization. As with all approaches, the regularization of stroke density must be addressed. Hays and Essa's [START_REF] Hays | Image and video based painterly animation[END_REF] further innovation was to introduce a smooth fade-in/out by varying the opacity of strokes as they were added and deleted, so suppressing flicker.

Bousseau et al. [START_REF] Bousseau | Video watercolorization using bidirectional texture advection[END_REF] described an algorithm for rendering watercolor video, adapting the texture advection approaches used in scientific visualization to render flow fields. In this system, blended texture patches were moved not only forward but also backward in time using a bi-directional estimate of optical flow. This mitigated against the cumulative errors inherent in the forward propagation strategies of prior approaches.

Visual Stylization through Segmentation

Segmentation is now a common component in IB-AR, and by leveraging a similar mid-level representation for video, the consistent motion of strokes within an object can be enforced. This offers improved coherence over estimating the motion of each pixel independently, as optical flow can be unreliable in untextured regions, e. g. object interiors. Region-based representations are also amenable to stylization in a broader gamut of styles, offering the option of stylizing object motion. However, these benefits come at the cost of generality; not all object are amenable to segmentation (e. g., smoke or water).

Video segmentation approaches can be categorized into spatio-temporal (3D) analysis, and frame-to-frame segmentation (2D+t) creating associations between regions over time (Fig. 10). Wang et al. [START_REF] Wang | Video tooning[END_REF] presented video tooning, an interactive stylization system following the 3D model. The system is underpinned by an anisotropic extension of mean-shift to video. The system over-segments the video volume into many partial object fragments, grouped by a user. These groups are drawn over and the drawings rotoscoped to deform automatically with the group's exterior boundary. Collomosse et al. [START_REF]Stroke surfaces: A spatio-temporal framework for temporally coherent nonphotorealistic animations[END_REF], [START_REF]Stroke surfaces: Temporally coherent non-photorealistic animations from video[END_REF] adopted the complementary (2D+t) segmentation model in stroke surfaces. Regions were associated over time using a space-time region adjacency graph that pruned sporadic association to improve stability. Cross-sections through the resulting space-time surfaces are sampled at each frame and rendered to form strokes depicting the boundaries of regions. Similar to Wang et al. [START_REF] Wang | Video tooning[END_REF], interaction facilitates a correction of the segmentation.

Painterly and cartoon effects were demonstrated by filling regions with strokes and textures that deform coherently with the boundary. Both Wang et al. [START_REF] Wang | Video tooning[END_REF] and Collomosse et al. [START_REF]Stroke surfaces: Temporally coherent non-photorealistic animations from video[END_REF] echo the automated rotoscoping work of Agarwala et al. [START_REF] Agarwala | Keyframe-based tracking for rotoscoping and animation[END_REF], which demonstrates similar attachment of rendering primitives to deforming regions. These works indicate the equivalence of automated rotoscoping to the video SBR problem. Recent work by Wang et al. [START_REF] Wang | Video stylization for digital ambient displays of home movies[END_REF] combines both segmentation and optical flow in a 2D+t framework. The system uses a multi-label graph-cut approach to segment individual video frames, propagating labeling priors forward in time with an optical flow variant.

Semi-automated video painting systems have recently been developed and can be considered to be advanced rotoscoping tools, permitting both high-level control over groupings of strokes whilst also allowing fine-grain modification of stroke detail. Lin et al. [START_REF] Lin | Painterly animation using video semantics and feature correspondence[END_REF] and, recently, O'Donovan and Hertzmann [START_REF] O'donovan | AniPaint: Interactive painterly animation from video[END_REF] developed systems that enable video to be interactively segmented into layers, each of which is populated with strokes. As with Agarwala et al. [START_REF] Agarwala | Keyframe-based tracking for rotoscoping and animation[END_REF], stroke positions deform with the supporting layer and may be dampened to reduce flicker. In the system of Kagaya et al. [START_REF] Kagaya | Video painting with space-timevarying style parameters[END_REF], the video is first segmented into spatial-temporal coherent regions. Users can assign style and orientation parameters as key frames to these regions to be then interpolated over space-time.

Motion Stylization

Video analysis at the region level enables not only consistent rendering within objects, but also facilitates the analysis of object motion. This motion may then be stylized using a variety of motion emphasis cues borrowed from classical animation such as mark-making (speedlines, ghosting, or 'skinning' lines) and deformation [START_REF] Lasseter | Principles of traditional animation applied to 3D computer animation[END_REF].

Automated methods to generate speed-lines in video require camera motion compensation, as the camera typically pans to track objects. This can be approximated by estimating inter-frame homographies. Points on trailing object edges may be sampled over time and visualized as speed-lines [START_REF] Collomosse | Video analysis for cartoon-style special effects[END_REF]. Chenney et al. [START_REF] Chenney | Simulating cartoon style animation[END_REF] presented early work automatically deforming objects to emphasize motion. This work introduced the 'squash and stretch' effect, scaling 3D objects along their trajectories. A similar effect can be applied to 2D video using non-uniform scaling performed within a curvilinear basis along the object's trajectory [START_REF] Collomosse | Video analysis for cartoon-style special effects[END_REF]. Other distortions warping the object according to velocity or acceleration emphasized drag or inertia. Liu et al. [START_REF] Liu | Motion magnification[END_REF] segment video into distinctly moving layers using unsupervised clustering of motion vectors, and perform similar warps. Animators frequently manipulate the timing and trajectory of object motion to introduce 'snap' into an action and this effect has also been incorporated into deformation models [START_REF] Collomosse | Video analysis for cartoon-style special effects[END_REF], [START_REF] Wang | The cartoon animation filter[END_REF].

IMAGE PROCESSING AND FILTERING

Many of the techniques described in the previous sections are infeasible for real-time rendering and cannot be trivially adapted for multi-core CPUs or GPUs. Image processing techniques performing local filtering operations provide an interesting alternative since parallelization and GPU implementations are straightforward in most cases. Moreover, a number of filtering techniques have been shown to perform with reasonable temporal coherence when processed frame by frame. These advantages, however, come at the expense of style diversity afforded by higher-level interpretation of content.

Bilateral Filter and Difference of Gaussians

A fully automatic pipeline for the stylization of cartoon renderings based on images and videos was first proposed in the seminal work by Winnemöller et al. [START_REF] Winnemöller | Real-time video abstraction[END_REF]. Their pipeline employs the bilateral and difference of Gaussians (DoG) filter and contains several influential ideas that other researchers later built upon. Computation of the bilateral filter [START_REF] Paris | Bilateral filtering: Theory and applications[END_REF] is comparatively expensive, leading Winnemöller et al. to iteratively apply a separable implementation of the bilateral filter. Although this brute force separation is prone to horizontal and vertical artifacts, it provides a reasonable trade-off between quality and speed, enabling real-time processing on consumer GPUs at the time. In addition, smooth quantization of the luminance channel in CIELab space is performed to achieve a strong cartoon-like effect similar to cel shading. While previous work mainly focused on extracting zero crossings, Winnemöller et al. showed that comparatively simple thresholding of the DoG filter leads to artistically appealing results. Moreover, in a recent survey, Winnemöller [START_REF] Winnemöller | XDoG: Advanced image stylization with eXtended difference-of-Gaussians[END_REF] showed the versatility of the DoG filter and how a large variety of NPR effects can be created by properly adjusting parameters.

A schematic overview of a generalized form of the Winnemöller et al. [START_REF] Winnemöller | Real-time video abstraction[END_REF] pipeline is shown in Fig. 11. In [START_REF]Flow-based image abstraction[END_REF], [START_REF] Kyprianidis | Image abstraction by structure adaptive filtering[END_REF], [START_REF] Winnemöller | Real-time video abstraction[END_REF]. After the conversion to CIELab, the input is iteratively abstracted using the bilateral filter. First, 1-2 bilateral filter iterations suppress noise, and outlines are extracted from the intermediate result using a DoG filter. Further iterations of the bilateral filter are performed, with luminance quantization applied afterwards. DoG edges and the output of the luminance quantization are then composited, followed by optional sharpening by warping and smoothing of the edges.

the original pipeline the local orientation estimation step was not present. This step was added later to adapt the bilateral and DoG filter to the local image structure [START_REF] Kang | Coherent line drawing[END_REF], [START_REF]Flow-based image abstraction[END_REF], [START_REF] Kyprianidis | Image abstraction by structure adaptive filtering[END_REF]. Also not present were the iterative application of the DoG filter [START_REF] Kang | Coherent line drawing[END_REF] and the final smoothing pass to further reduce aliasing of edges. The introduction of the flow-based DoG filter [START_REF] Kang | Coherent line drawing[END_REF], [START_REF]Flow-based image abstraction[END_REF], [START_REF] Kyprianidis | Image abstraction by structure adaptive filtering[END_REF] increased the quality of the produced outlines and made the warp-based sharpening step of the original pipeline less important and obsolete in later work (Fig. 12(a)-(c)).

The bilateral filter smoothes low-contrast regions while preserving high-contrast edges, but may fail for highcontrast images where either no abstraction is performed or salient visual features may be removed. The latter effect can also be observed in low-contrast images. Furthermore, iterative filtering may blur edges resulting in a washedout appearance (Fig. 12(d)). These limitations can be alleviated by overlaying the output of the bilateral filter with outlines of the DoG filter. Accordingly, the bilateral filter is rarely applied independently for IB-AR. Another possibility is to use a more sophisticated edgepreserving filtering approach, such as weighted least squares (WLS) [START_REF] Farbman | Edge-preserving decompositions for multi-scale tone and detail manipulation[END_REF]. The next section discusses a further popular approach.

Kuwahara Filter

An interesting class of edge-preserving filters that perform comparatively well on high-contrast images are variants of the Kuwahara filter [START_REF] Kuwahara | Processing of ri-angiocardiographic images[END_REF]. Based on local area flattening, these filters properly remove detail in highcontrast regions and protect shape boundaries in lowcontrast regions, resulting in a roughly uniform level of abstraction across the image (Fig. 12(e)). The original Kuwahara filter divides the local filter neighborhood into four rectangular subregions that overlap by one pixel. For all subregions, the variance-the sum of the squared distances to the mean-is computed and the response of the filter is then defined as the mean of a subregion with minimum variance. This subregion selection avoids averaging between differently colored regions for corners and edges. For flat or homogeneous regions the variances of different subregions are very similar. Therefore, a subregion with minimum variance is generally not welldefined and highly unstable in the presence of noise. For small filter sizes, the Kuwahara filter produces reasonable results. For IB-AR, however, comparatively large filter sizes are necessary to achieve an abstraction, resulting in noticeable artifacts. These are due to the unstable subregion selection and rectangular subregions.

Several methods address these limitations. The first approach suitable for applications in IB-AR is the generalized Kuwahara filter by Papari et al. [START_REF] Papari | Artistic edge and corner enhancing smoothing[END_REF], which introduces two important ideas. First, the rectangular subregions are replaced with smooth weighting functions that are constructed over sectors of a disc such that their sum yields a 2D Gaussian and neighboring weighting functions overlap smoothly. Using these weighting functions, the weighted mean and weighted variance can be computed for every sector. Second, a the subregion selection is replaced by taking the weighted sum of the weighted means of the sectors.

For highly anisotropic image regions, the flattening effect applied by the generalized Kuwahara filter is typically too aggressive, resulting in blurred anisotropic structures. Moreover, pixels tend to form clusters proportional to the filter size. The anisotropic Kuwahara filter by Kyprianidis et al. [START_REF] Kyprianidis | Image and video abstraction by multi-scale anisotropic Kuwahara filtering[END_REF], [START_REF] Kyprianidis | Image and video abstraction by anisotropic Kuwahara filtering[END_REF] addresses these issues by replacing the weighting functions defined over sectors of a disc with weighting functions defined over ellipses. By adapting shape, scale, and orientation of these ellipses to the local structure of the input, artifacts are avoided. Directional image features are also better emphasized, resulting in sharper edges and the enhancement of anisotropic image features such as hair or fur.

Diffusion and Shock Filter

Osher and Rudin [START_REF] Osher | Feature-oriented image enhancement using shock filters[END_REF] as well as Weickert [160] recognized the artistic merit of shock filtered imagery, but the work of Kang and Lee [START_REF] Kang | Shape-simplifying image abstraction[END_REF] was the first to apply diffusion in combination with shock filtering for IB-AR. Mean curvature flow (MCF), which evolves isophote curves under curvature speed in normal direction, is chosen as diffusion method, resulting in simplified isophote curves with regularized geometry. In contrast to other popular edge-preserving smoothing techniques, MCF smooths not only irrelevant color variations while protecting region boundaries but also simplifies the shape of those boundaries. However, it also creates blurred edges, leading Kang and Lee [START_REF] Kang | Shape-simplifying image abstraction[END_REF] to perform de-blurring with a shock filter after some MCF iterations, which helps to preserve edges. From an aesthetic point of view, shock filtered MCF is typically too aggressive and does not preserve directional image features. Therefore, Kang and Lee [START_REF] Kang | Shape-simplifying image abstraction[END_REF] constrained the MCF using a vector field to penalize [START_REF] Paris | Bilateral filtering: Theory and applications[END_REF]. (e) Anisotropic Kuwahara filter [START_REF] Kyprianidis | Image and video abstraction by anisotropic Kuwahara filtering[END_REF]. (f) Shape-simplifying image abstraction [START_REF] Kang | Shape-simplifying image abstraction[END_REF]. (g) Coherence-enhancing filtering [START_REF] Kyprianidis | Image and video abstraction by coherence-enhancing filtering[END_REF].

diffusion that deviates from the local image structure (Fig. 12(f)). MCF and its constrained variant contract isophote curves to points. For this reason, important image features must be protected by a user-defined mask. A further limitation is that the technique is not stable against small changes in the input and, therefore, not suitable for perframe video processing. In order to avoid these problems, Kyprianidis and Kang [START_REF] Kyprianidis | Image and video abstraction by coherence-enhancing filtering[END_REF] combine curvature-preserving flow-guided smoothing and shock filter-based sharpening orthogonal to the flow, but instead of modeling the process by a PDE, approximations that operate as a local neighborhood filter are used. This improves stability and so suitability for per-frame video processing (Fig. 12(g)).

Morphological Filtering

Mathematical morphology (MM) provides a set-theoretic approach to image analysis and processing. Fundamental operations in MM are dilation and erosion. For grayscale images, dilation is equivalent to a maximum filter and erosion corresponds to a minimum filter. From these, other operators can be derived-notably opening and closing. These are related to order-statistics filters and applying opening and closing in sequence results in a smoothing operation that is often referred to as morphological smoothing.

Morphological smoothing is applied in Bousseau et al.'s [START_REF] Bousseau | Interactive watercolor rendering with temporal coherence and abstraction[END_REF], [START_REF] Bousseau | Video watercolorization using bidirectional texture advection[END_REF] work on watercolor rendering and in Bangham's et al.'s [START_REF] Bangham | The art of scale-space[END_REF] oil paintings to simplify input images and videos before rendering. In the case of video, Bousseau et al. [START_REF] Bousseau | Video watercolorization using bidirectional texture advection[END_REF] use a spatio-temporal kernel aligned to the motion trajectory derived from optical flow. Applying opening and then closing generally results in a darkened result. Since watercolor paintings typically have light colors, Bousseau et al. [START_REF] Bousseau | Video watercolorization using bidirectional texture advection[END_REF] proposed to swap the order of the morphological operators and apply closing followed by opening. Because opening and closing are dual, this is equivalent to inverting the output of morphological smoothing applied to the inverted image.

Papari and Petkov [START_REF] Papari | Continuous glass patterns for painterly rendering[END_REF] described another technique that applied morphological filtering in the context of IB-AR. Motivated by glass patterns and similar to line integral convolution (LIC) [START_REF] Cabral | Imaging vector fields using line integral convolution[END_REF], they performed a onedimensional dilation in form of a maximum filter over noise along the integral curves defined by a vector field. In contrast to LIC, this technique is more capable of producing thick piecewise constant coherent lines with sharp edges, resulting in a stronger brush-like effect. Moreover, it can also be applied to color images by using the location of the first maximum noise value along the integral curve as a look-up position.

Some morphological operators can be efficiently implemented by using distance transforms. Criminisi et al. [START_REF] Criminisi | Geodesic image and video editing[END_REF] recently demonstrated that edge-sensitive smoothing based on the generalized geodesic distance transform (GGDT) can be used for the creation of cartoon-style abstractions. The image is first clustered into a fixed number of colors. Then, for every pixel the probability of the pixel's value belonging to a certain cluster is defined. These probabilities form a soft mask to which the GGDT is applied. The output is then defined as the weighted sum of the cluster's mean values where the weights are defined based on the corresponding distances.

Gradient Domain Techniques

In recent years, gradient domain methods have become very popular in computer vision and computer graphics [START_REF] Agrawal | Gradient domain manipulation techniques in vision and graphics[END_REF]. The basic idea behind such methods is to construct a gradient field representing the result. Since such constructed fields are rarely conservative the result needs to be found as an approximation by solving an optimization problem (Poisson's equation).

Orzan et al. [START_REF] Orzan | Structurepreserving manipulation of photographs[END_REF] were the first to apply gradient domain image editing for IB-AR. Using scale-space analysis, they extracted a multi-scale Canny edge representation with lifetime and best scale information, which is used to define the gradient field and allows for image operations such as detail removal and shape abstraction. Moreover, line drawings can be extracted from the multi-scale representation and overlaid with the reconstructed image. A limitation of the technique is that handling contrast is problematic and requires correction. Besides being computationally expensive, this technique is also known not to create temporally coherent output for video.

Bhat et al. [START_REF] Bhat | GradientShop: A gradient-domain optimization framework for image and video filtering[END_REF] have presented a robust optimization framework that allows for the specification of zero-order (pixel value) and first-order (gradient value) constraints over space and time. The resulting optimization problem is solved using a weighted least squares solver. By using temporal constraints, the framework is able to create temporally coherent video output. The framework makes use of several computationally expensive techniques such as steerable filters and optical flow and currently limited to offline processing.

FUTURE CHALLENGES

Over the past two decades, IB-AR has delivered many high-quality expressive rendering algorithms and interactive systems. Several high-quality symposia have also emerged, notably Non-Photorealistic Animation and Rendering (NPAR, established in 2000) and Computational Aesthetics (CAe, established in 2005). As the field gathered momentum, researchers sought to identify the key emerging challenges. David Salesin identified seven Grand Challenges in a keynote delivered at NPAR 2002. We first recap these for the record, as many relate to IB-AR and still remain relevant. The challenges were phrased as seven research questions:

1) Algorithmic Aesthetics. How can we quantify success and how can aesthetic 'beauty' be defined? 2) Abstraction. How do you capture the 'essence' of an object, image, or painterly style? The reduction of an image to a sketch or structure was discussed. 3) Visualization. How can you use NPR to communicate information most effectively? 4) Interactivity. How can you develop automated tools that support creativity and the artist? 5) Artistic Turing Test. Can you make artistic computer images and animations that are indistinguishable from those created by hand? 6) New Art Forms. Can NPR be used to create some entirely new and original forms of art? 7) Naming the Field. In a closing aside, Salesin voiced the views of many that NPR is an unfortunately broad term. A decade later, nevertheless, it is still the dominant label for the field [START_REF] Gooch | Viewing progress in non-photorealistic rendering through Heinlein's lens[END_REF]. Artistic rendering or Artistic stylization is also in common parlance, whilst illustrative visualization is being used for approaches in Salesin's third challenge.

Salesin's challenges were revisited at NPAR 2010 by Gooch et al. [START_REF] Gooch | Viewing progress in non-photorealistic rendering through Heinlein's lens[END_REF], demonstrating progress by citing work contributing to each research question. They express the view that (6) remains the most promising direction; that NPR should "not just imitate and emulate styles of the past but create styles for the future." They also observe that Salesin's research questions regarding definitions of aesthetics and the artistic Turing test should be given equal weight in terms of new artistic styles emerging as a consequence of NPR. Examples of such artwork cited include Draves' Electric Sheep [START_REF] Draves | The Electric Sheep screen-saver: A case study in aesthetic evolution[END_REF].

Further positions regarding directions for NPR were presented at NPAR 2010 by DeCarlo and Stone [START_REF] Decarlo | Visual explanations[END_REF] and Hertzmann [START_REF] Hertzmann | Non-photorealistic rendering and the science of art[END_REF]. DeCarlo and Stone's discussion focused on visual explanations, that IB-AR can enhance communication by simplification through structural abstraction. This echoes the trend towards perceptually grounded IB-AR [START_REF]Genetic paint: A search for salient paintings[END_REF], [START_REF]Visual interest and NPR: An evaluation and manifesto[END_REF] and the original motivations for NPR in the early 1990s where NPR and visualization shared common roots, e. g., Strothotte et al.'s [START_REF] Strothotte | How to render frames and influence people[END_REF] transmitted vs. transputed image. Structural abstraction algorithms, for example, are an emerging trend in IB-AR [START_REF] Mi | Abstraction of 2D shapes in terms of parts[END_REF], [START_REF] Song | Arty shapes[END_REF].

Evaluation

DeCarlo and Stone [START_REF] Decarlo | Visual explanations[END_REF], Hertzmann [START_REF] Hertzmann | Non-photorealistic rendering and the science of art[END_REF], and Gooch et al. [START_REF] Gooch | Viewing progress in non-photorealistic rendering through Heinlein's lens[END_REF] all revisit the important issue of aesthetic evaluation in IB-AR. Almost one decade since Salesin's panel discussion of this problem, few papers present structured methodologies for evaluation. This is increasingly important as many traditional styles are now covered in early IB-AR papers and researchers need to either innovate new styles [START_REF] Gooch | Viewing progress in non-photorealistic rendering through Heinlein's lens[END_REF] or demonstrate that their work improves over prior art. In some cases (e. g., animation flicker), it is practical to objectify improvement. However, in most papers, evaluation relates to aesthetics only, in the form of a subjective side-by-side visual comparison. While some researchers had previously looked at evaluating single aspects of IB-AR such as aesthetics (e. g., [START_REF] Healey | Perception and painting: A search for effective, engaging visualizations[END_REF]), Isenberg et al. [START_REF] Isenberg | Non-photorealistic rendering in context: An observational study[END_REF] were the first to present a concrete methodology for gathering data on participants' views on artistic renderings, proposing an unconstrained pile sort of renderings based on user preference. In doing so, they also drew conclusions with respect to some of Salesin's challenges such as the artistic Turing test by examining techniques that largely did not pass at the time. Evaluation work more closely aligned with Salesin's visual communication challenge was proposed by Gooch et al. [START_REF] Gooch | Human facial illustrations: Creation and psychophysical evaluation[END_REF] and Winnemöller et al. [START_REF] Winnemöller | Real-time video abstraction[END_REF] in their portrait abstractions. It was shown that abstracted faces were more quickly recognized than photorealistic imagery, implying improved comprehension through IB-AR. Methodologies have been developed to evaluate specific aspects of IB-AR such as visual interest [START_REF]Visual interest and NPR: An evaluation and manifesto[END_REF] and stippling aesthetics [START_REF] Maciejewski | Measuring stipple aesthetics in hand-drawn and computer-generated images[END_REF]. However, no gold standard methodology has emerged for NPR evaluation.

Interaction

Although a few IB-AR systems of the early nineties cited their motivation as emulating the artist (i. e., passing the artistic Turing test), the frequently stated motivation of contemporary IB-AR work is to retain human creativity and to deliver useful tools and new artistic media. As IB-AR has matured to improve the quality and sophistication of output, the field has begun to positively impact the creative industries. Early IB-AR examples include tools that created painterly effects in the movie What Dreams May Come (1998), and Rotoshop, which was used to propagate painted contours with motion in the movies Waking Life (2001) and A Scanner Darkly (2008). This increased uptake has motivated the development of effective interactive systems for working with IB-AR techniques. Thus, the trend towards automation that started with basic image-processing in the 1990s, through to increasingly sophisticated computer vision in the mid-2000s, is now trending back toward interactive techniques [START_REF] Grubert | Interactive stroke-based NPR using hand postures on large displays[END_REF], [START_REF] Kagaya | Video painting with space-timevarying style parameters[END_REF], [START_REF] O'donovan | AniPaint: Interactive painterly animation from video[END_REF]. This trend also reflects the limitations of contemporary computer vision and shows that, by carefully designing minimal but well-placed interaction, a high-quality automated visual effects workflow can result. As such, the need for evaluation in NPR goes beyond automated assessments of aesthetics to ensure the creation of effective tools for artists.

Hertzmann [START_REF] Hertzmann | Non-photorealistic rendering and the science of art[END_REF] reflects on both the usability and aesthetic aspects of evaluation in his position paper, and also notes that automated evaluation of aesthetics is useful not only in comparing results but also in global optimization approaches to IB-AR [START_REF]Genetic paint: A search for salient paintings[END_REF], [START_REF]Paint by relaxation[END_REF], [START_REF] Kovács | Creating animations combining stochastic paintbrush transformation and motion detection[END_REF] where an objective function capturing some definition of aesthetic 'beauty' must be maximized. However, aesthetics by its nature is challenging to capture through an 'objective' function and such a definition is not certain to appeal to people in the general case.

The drive toward creative tools for IB-AR implies a closer collaboration with artists and end-users. Yet, few demonstrate any collaboration or validation with creative professionals. Addressing this is especially important if, as Gooch et al. [START_REF] Gooch | Viewing progress in non-photorealistic rendering through Heinlein's lens[END_REF] suggest, IB-AR's priority is to develop new artistic media and tools. Carroll's Task-Artifact Cycle [START_REF] Carroll | The task-artifact cycle[END_REF] reminds us that users often apply new tools in ways unintended by the designer, generating tasks to be supported in further development. Collaboration with end-users is essential in closing this cycle. More generally, there is potential to draw upon HCI's best practice in structured user-studies for requirement elicitation (e. g., design ethnography) or in co-operative evaluation of the resulting tools. Connections could be forged with research communities studying computational creativity and evolutionary art. Such fields study aesthetics and separately contribute toward Salesin's measure of 'beauty.'

Technical directions

The technical direction of algorithmic research in IB-AR is challenging to predict for a longer term but may develop in the direction of several established mid-term trends. IB-AR has evolved from image processing toward more sophisticated interpretations of image structure (Sec. 4). However, output remains essentially a stylized version of the source. Analysis of scene structure could enable manipulation of imagery at the composition level. Initial forays into composition indicate the potential of extending the gamut of IB-AR to include abstract styles such as Cubism [START_REF]Cubist style rendering from photographs[END_REF], Futurism [START_REF] Hall | RTcams: A new perspective on nonphotorealistic rendering from photographs[END_REF] and nonlinear projection [START_REF] Durand | An invitation to discuss computer depiction[END_REF]. The manipulation of global structure for abstraction has also been explored recently [START_REF] Zhao | Sisley the abstract painter[END_REF]. Willats and Durand [162] clearly differentiate between such renderings and current IB-AR when writing about the distinction between spatial and depictive systems. Abstract visual art is only one potential beneficiary of structural analysis. Portraits are an example of subject matter currently rendered poorly by general purpose stylization algorithms since they are particularly sensitive to distortion or detail loss in facial regions. Imposing high-level models of faces may mitigate this problem and facilitate convincing caricatures and other high-level manipulations [START_REF] Tresset | Generative portrait sketching[END_REF], [170].

A long-standing challenge in video IB-AR is that of temporal coherence (Sec. 4.6). Nonlinear, edge-aware filtering has been shown to be robust to noise and to generalize over wider classes of footage than computer vision-based methods. However, the gamut of styles achievable by filtering methods is limited to cartoon or painterly styles. By contrast, video stylization approaches based on computer vision can perform more aggressive abstraction through mid-level scene parsing (e. g., segmentation) at the cost of generality. There is a tendency for complex image processing decisions to become less stable in the presence of noise. Ensuring stability of vision-based video stylization remains a largely unsolved problem in automatic IB-AR-in most practical cases relying upon user-assisted markup of footage [START_REF] Lin | Painterly animation using video semantics and feature correspondence[END_REF], [START_REF] O'donovan | AniPaint: Interactive painterly animation from video[END_REF] (which can also be desirable in the context of a creative tool). Nevertheless, maximizing temporal coherence while minimizing user correction and manual labor remains a difficult compromise.

A further trend is toward increased realism in media modeling that one might provocatively call the photorealism in NPR. The scope of this survey has necessarily focused on the algorithms for abstraction that drive the placement of rendering primitives. However, overall aesthetics are heavily influenced by media realism, especially in the emulation of traditional artistic styles. Taking painting as an example, strokes have evolved from rectangular stamps [START_REF] Litwinowicz | Processing images and video for an impressionist effect[END_REF], to textured curved splines [START_REF]Painterly rendering with curved brush strokes of multiple sizes[END_REF], to bump-mapped splines [START_REF]Fast paint texture[END_REF], and even to digitized real brushes selected from a database according to image texture [START_REF] Zeng | From image parsing to painterly rendering[END_REF]. Although this paper has focused on image and video stylization algorithms, complementary research directions investigating media modeling and interactive creative tools remain highly active. Inevitably, as IB-AR and the applications drawing these areas continue to mature, so too will the simulations of artistic media and tool sets that support them.

Fig. 2 .

 2 Fig. 2. Taxonomy of IB-AR techniques.

Fig. 4 .

 4 Fig. 4. Illustrating the coarse to fine rendering and curved path tracing components of Hertzmann's painting algorithm [55].

Fig. 5 .

 5 Fig. 5. Interactive abstraction system of Decarlo and Santella [29]. Images are segmented in a scale-space pyramid (top-left). The viewer's gaze is drawn to particular image regions; these regions are locally decomposed into finer segments traversing the pyramid (bottom). Outlines are smoothed and superimposed to delineate region boundaries (top-right).

Fig. 7 .

 7 Fig. 7. Stippling examples: (a) Secord's [137] approach (2000 dots); (b) Kopf et al.'s [78] non-repetitive stippling (7700 dots).

Fig. 8 .

 8 Fig. 8. Image analogies extend patch based texture in-filling techniques to match between a source image and its artistic rendering. Images are rendered in analogous styles using the learned mapping.

Fig. 9 .

 9 Fig. 9. Mosaicking algorithms aim to tightly pack tiles without overlap. (a) A greedy approach to tiling [6]. (b) Tiling by global graph-cut based optimization [92]. (c) Mosaicking with regular [51] and (d)-(e) irregular overlapping tiles [73], [110].

Fig. 10 .

 10 Fig. 10. Video stylization driven by coherent segmentation. (a) 3D approach. (b) 2D+t approach. (c) Cartoon and painterly styles arising from rotoscoping the coherent regions [157]. (d) Example of coherent painterly rendering [157].

Fig. 11 .

 11 Fig.11. Generalized pipeline for creating cartoon-like effects by local filtering[START_REF]Flow-based image abstraction[END_REF],[START_REF] Kyprianidis | Image abstraction by structure adaptive filtering[END_REF],[START_REF] Winnemöller | Real-time video abstraction[END_REF]. After the conversion to CIELab, the input is iteratively abstracted using the bilateral filter. First, 1-2 bilateral filter iterations suppress noise, and outlines are extracted from the intermediate result using a DoG filter. Further iterations of the bilateral filter are performed, with luminance quantization applied afterwards. DoG edges and the output of the luminance quantization are then composited, followed by optional sharpening by warping and smoothing of the edges.

Fig. 12 .

 12 Fig. 12. Left: Different results that were all created with the generalized cartoon pipeline. (a) Thresholded output of the separable implementation of the flow-based DoG [82]. (b) Flow-based DoG with XDoG thresholding [163]. (c) Cartoon-style abstraction generated with bilateral and flow-based DoG filter [70], [82]. Right: A selection of popular image abstraction techniques. (d) Bilateral filter (4 iterations)[START_REF] Paris | Bilateral filtering: Theory and applications[END_REF]. (e) Anisotropic Kuwahara filter[START_REF] Kyprianidis | Image and video abstraction by anisotropic Kuwahara filtering[END_REF]. (f) Shape-simplifying image abstraction[START_REF] Kang | Shape-simplifying image abstraction[END_REF]. (g) Coherence-enhancing filtering[START_REF] Kyprianidis | Image and video abstraction by coherence-enhancing filtering[END_REF].

Acknowledgments:

The authors would like to thank the anonymous reviewers for their constructive feedback.