A Projection Method on Measures Sets

Abstract

We consider the problem of projecting a probability measure $\pi$ on a set ${\mathcal {M}}_N$ of Radon measures. The projection is defined as a solution of the following variational problem:

$$\begin{aligned} \inf _{\mu \in {\mathcal {M}}_N} \Vert h\star (\mu - \pi )\Vert _2^2, \end{aligned}$$

where $h\in L^2(\Omega )$ is a kernel, $\Omega \subset {\mathbb {R}}^d$, and $\star$ denotes the convolution operator. To motivate and illustrate our study, we show that this problem arises naturally in various practical image rendering problems such as stippling (representing an image with N dots) or continuous line drawing (representing an image with a continuous line). We provide a necessary and sufficient condition on the sequence $({\mathcal {M}}_N)_{N\in {\mathbb {N}}}$ that ensures weak convergence of the projections $(\mu ^*_N)_{N\in {\mathbb {N}}}$ to $\pi$. We then provide a numerical algorithm to solve a discretized version of the problem and show several illustrations related to computer-assisted synthesis of artistic paintings and drawings.

1 Introduction

Digital halftoning consists of representing a grayscale image with only black and white tones [30]. For example, a grayscale image can be approximated by a variable distribution of black dots over a white background. This technique, called stippling, is the cornerstone of most printing digital inkjet devices. A stippling result is displayed in Fig. 1b. The lion in Fig. 1a can be recognized from the dotted image shown in Fig. 1b. This is somehow surprising, since the differences between the pixel values of the two images are far from zero. One way to explain this phenomenon is to invoke the multiresolution feature of the human visual system [8, 24]. Figure 1c and d are blurred versions of Fig. 1a and 1b, respectively. These blurred images correspond to low-pass versions of the original ones and are nearly impossible to distinguish.

Fig. 1

Explanation of the stippling phenomenon. Images a and b are similar, while the norm of their difference is large. Images c and d are obtained by convolving a and b with a Gaussian of variance equal to 3 pixels. After convolution, the images cannot be distinguished

Assuming that the dots correspond to Dirac masses, this experiment suggests placing the dots at locations $p_1, \ldots , p_N$ corresponding to the minimizer of the following variational problem:

$$\begin{aligned} \min _{(p_1,\ldots ,p_N)\in \Omega ^N} \left\| h\star \left( \pi - \frac{1}{N}\sum _{i=1}^N \delta _{p_i}\right) \right\| _2^2, \end{aligned}$$

(1)

where $\Omega \subset {\mathbb {R}}^2$ denotes the image domain, $\delta _{p_i}$ denotes the Dirac measure at point $p_i\in {\mathbb {R}}^2$, $\pi$ denotes the target probability measure (the lion), and h is a convolution kernel that should depend on the point spread function of the human visual system. By letting

$$\begin{aligned} {\mathcal {M}}(\Omega ^N)=\left\{ \mu = \frac{1}{N} \sum _{i=1}^N \delta _{p_i}, \ (p_i)_{1\le i\le N}\in \Omega ^N\right\} \end{aligned}$$

(2)

denote the set of N-point measures, problem (1) rereads as a projection problem:

$$\begin{aligned} \min _{\mu \in {\mathcal {M}}(\Omega ^N)} \left\| h\star (\pi - \mu ) \right\| _2^2. \end{aligned}$$

(3)

This variational problem is a prototypical example that motivates our study. As explained later, it is intimately related to recent works on image halftoning by means of attraction–repulsion potentials proposed in [14, 26, 28]. In references [10–12], this principle is shown to have far-reaching applications ranging from numerical integration, quantum physics, economics (optimal location of service centers) or biology (optimal population distributions).

In this paper, we extend this variational problem by replacing ${\mathcal {M}}(\Omega ^N)$ with an arbitrary set of measures denoted by ${\mathcal {M}}_N$. In other words, we want to approximate a given measure $\pi$ by another measure in the set ${\mathcal {M}}_N$. We develop an algorithm that is shown to converge to critical points of this projection problem in a general setting.

To motivate this extension, we consider a practical problem: how to perform continuous line drawing with a computer? Continuous line drawing is a starting course in all art courses. It consists of drawing a picture without ever lifting the pencil from the page. Figure 2 shows two drawings obtained with this technique. It is also used in marketing, quilting designs, steel wire sculptures, connect the dot puzzles, etc. A few algorithms were already proposed in [5, 15, 20, 32, 33]. We propose an original solution that consists of setting ${\mathcal {M}}_N$ as a space of pushforward measures associated with sets of parameterized curves.

Apart from the two rendering applications discussed above, the proposed methodology has potential for diverse applications in fields such as imaging, finance, biology, etc. As an application example, the interested reader can have a look at our recent preprint on the generation of sampling schemes in magnetic resonance imaging [6].

Fig. 2

Two examples of continuous line drawing. a A sketch of Marylin Monroe by Pierre Emmanuel Godet (http://pagazine.com/) using a continuous line. A close inspection reveals that the line represents objects and characters. b Meisje met de Parel, Vermeer 1665, represented using a spiral with variable width. Realized by Chan Hwee Chong (http://www.behance.net/Hweechong)

The rest of this paper is structured as follows. We first describe the notation and some preliminary remarks in Sect. 2. We propose a mathematical analysis of the problem for generic sequences of measures spaces $({\mathcal {M}}_N)_{N\in {\mathbb {N}}}$ in Sect. 3. We propose a generic numerical algorithm in Sect. 4 and derive some of its theoretical guarantees. In Sect. 5, we study the particular problem of continuous line drawing from a mathematical perspective. Finally, we present some results in image rendering problems in Sect. 6.

2 Notation and Preliminaries

In this paper, we work on the measurable space $(\Omega ,\Sigma )$, where $\Omega ={\mathbb {T}}^d$ denotes the torus ${\mathbb {T}}^d={\mathbb {R}}^d / {\mathbb {Z}}^d$. An extension to other spaces such as ${\mathbb {R}}^d$ or $[0,1]^d$ is feasible but requires slight adaptations. Since drawing on a donut is impractical, we will set $\Omega =[0,1]^d$ in the numerical experiments.

The space of continuous functions on $\Omega$ is denoted by ${\mathcal {C}}(\Omega )$. The Sobolev space $(W^{m,p}([0,T]))^d$, where $m\in {\mathbb {N}}$, is the Banach space of d dimensional curves in $\Omega$ with derivatives up to the m-th order in $L^p([0,T])$. Let ${\mathcal {M}}_\Delta$ denote the space of probability measures on $\Omega$, i.e., the space of nonnegative Radon measures p on $\Omega$ such that $p(\Omega )=1$. Throughout the paper, $\pi \in {\mathcal {M}}_\Delta$ will denote a target measure. Let ${\mathcal {M}}$ denote the space of signed measures on $\Omega$ with bounded total variation; that is, $\mu = \mu _+ - \mu _-$, where $\mu _+$ and $\mu _-$ are two finite nonnegative Radon measures and $\Vert \mu \Vert _{TV} = \mu _+(\Omega ) + \mu _-(\Omega ) < \infty$.

Let $h:\Omega \rightarrow {\mathbb {R}}$ denote a continuous function. Let $\mu \in {\mathcal {M}}$ denote an arbitrary finite signed measure. The convolution product between h and $\mu$ is defined for all $x\in \Omega$ by:

$$\begin{aligned} \mu \star h (x)&:=\int _{\Omega } h(x-y) \hbox {d}\mu (y) \nonumber \\&= \mu (h(x-\cdot )). \end{aligned}$$

(4)

In the Fourier space, the convolution (4) translates to, for all $\xi \in {\mathbb {Z}} ^d$ (see e.g., [16]),

$$\begin{aligned} \widehat{\mu \star h}(\xi )&= \hat{\mu }(\xi ) \hat{h}(\xi ), \end{aligned}$$

where $\hat{\mu }$ is the Fourier–Stieltjes series of $\mu$. The Fourier–Stieltjes series coefficients are defined for all $\xi \in {\mathbb {Z}} ^d$ by

$$\begin{aligned} \hat{\mu }(\xi ) :=\int _{\Omega } e^{-2i\pi \langle \xi , x\rangle } \,d\mu (x). \end{aligned}$$

We recall the Parseval formula

$$\begin{aligned} \int _{\Omega } |h(x)|^2 \,\hbox {d}x = \sum _{\xi \in {\mathbb {Z}}^d} \left| \hat{h}(\xi )\right| ^2. \end{aligned}$$

Let $J:{\mathbb {R}}^n\rightarrow {\mathbb {R}}$ denote a function and $\partial J$ its limiting-subdifferential (or simply subdifferential) [1, 22]. Let $C\subseteq {\mathbb {R}}^n$ denote a closed subset. The indicator function of C is denoted by $i_C$ and defined by

$$\begin{aligned} i_C(x) = \left\{ \begin{array}{ll} 0 &{} \text {if } x\in C, \\ +\infty &{} \text {otherwise.}\end{array}\right. \end{aligned}$$

The set of projections of a point $x_0\in {\mathbb {R}}^n$ on C is denoted by $P_C(x_0)$ and defined by

$$\begin{aligned} P_C(x_0) = \mathop {\mathrm {Arg\, min}}_{x\in C} \Vert x-x_0\Vert _2^2. \end{aligned}$$

The notation $\mathop {\mathrm {Arg\, min}}$ stands for the whole set of minimizers, while $\mathop {\mathrm {arg\, min}}$ denotes one of the minimizers. Note that $P_C$ is generally a point-to-set mapping except if C is convex closed, since the projection on a closed convex set is unique. The normal cone at $x\in {\mathbb {R}}^n$ is denoted by $N_C(x)$. It is defined as the limiting-subdifferential of $i_C$ at x. A critical point of the function $J+i_C$ is a point $x^*$ that satisfies $0\in \partial J(x^*) + N_C(x^*)$. This condition is necessary (but not sufficient) for $x^*$ to be a local minimizer of $J+i_C$.

3 Mathematical Analysis

Let

$$\begin{aligned} {\mathcal {N}}_{h}(\mu ) :=\Vert h\star \mu \Vert _2. \end{aligned}$$

(5)

In this section, we study some basic properties of the following projection problem:

$$\begin{aligned} \min _{\mu \in {\mathcal {M}}_N} {\mathcal {N}}_h(\pi - \mu ), \end{aligned}$$

(6)

where $({\mathcal {M}}_N)_{N\in {\mathbb {N}}}$ denotes an arbitrary sequence of measures sets in ${\mathcal {M}}_\Delta$.

3.1 Norm Properties

We first study the properties of ${\mathcal {N}}_h$ on the space ${\mathcal {M}}$ of signed measures with bounded total variation. The following proposition shows that it is well defined provided that $h\in {\mathcal {C}}(\Omega )$.

Proposition 1

Let $h\in {\mathcal {C}}(\Omega )$ and $\mu \in {\mathcal {M}}$. Then $h\star \mu \in L^2(\Omega )$.

Proof

Since $\Omega$ is bounded, it is enough to show that $h\star \mu \in L^\infty (\Omega )$. Moreover, $\Vert h\Vert _{\infty }$ is finite since h is continuous on a bounded set. Hence $\forall x\in \Omega$, $|h\star \mu (x)| \le \Vert \mu \Vert _{TV} \Vert h\Vert _\infty <+\infty$. $\square$

Remark 1

In fact, the result holds true for weaker hypotheses on h. If $h\in {\mathcal {L}}^\infty (\Omega )$, the set of bounded Borel measurable functions, $h\star \mu \in L^2(\Omega )$ since

$$\begin{aligned} \forall x\in \Omega , \ |h\star \mu (x)| \le \Vert \mu \Vert _{TV} \left( \sup _{x\in \Omega } |h(x)|\right) <+\infty . \end{aligned}$$

Note that the $L^\infty$-norm is defined with an $\mathrm {ess}\sup$, while we used a $\sup$ in the above expression. We stick to $h\in {\mathcal {C}}(\Omega )$ since this hypothesis is more usual when working with Radon measures.

The following proposition gives a necessary and sufficient condition on h ensuring that ${\mathcal {N}}_{h}$ defines a norm on ${\mathcal {M}}$.

Proposition 2

Let $h\in {\mathcal {C}}(\Omega )$. The mapping ${\mathcal {N}}_{h}$ defines a norm on ${\mathcal {M}}$ if and only if all Fourier series coefficients $\hat{h}(\xi )$ are nonzero.

Proof

Let us assume that $\hat{h}(\xi )\ne 0, \; \forall \xi \in {\mathbb {Z}}^d$. The triangle inequality and absolute homogeneity hold trivially. Let us show that $\mu \ne 0 \Rightarrow {\mathcal {N}}_{h}(\mu )\ne 0$. The Fourier series of a nonzero signed measure $\mu$ is nonzero, so that there is $\xi \in {\mathbb {Z}}^d$ such that $\hat{\mu }(\xi ) \ne 0$. According to our hypothesis, $\hat{h}(\xi ) \ne 0$, hence $\widehat{\mu \star h}(\xi ) \ne 0$ and ${\mathcal {N}}_{h}(\mu )\ne 0$.

On the contrary, if there exists $\xi _0\in {\mathbb {Z}}^d$ such that $\hat{h}(\xi _0)=0$, the nonzero measure defined through its Fourier series by

$$\begin{aligned} \hat{\mu }(\xi )=\left\{ \begin{array}{ll} 1 &{} \text {if } \xi =\xi _0, \\ 0 &{} \text {otherwise}, \end{array}\right. \end{aligned}$$

satisfies ${\mathcal {N}}_{h}(\mu )=0$ and belongs to ${\mathcal {M}}$. $\square$

From now on, owing to Proposition 2, we will systematically assume - sometimes without mentioning - that $h\in {\mathcal {C}}(\Omega )$ and that $\hat{h}(\xi )\ne 0$, $\forall \xi \in {\mathbb {Z}}^d$. Finally, we show that ${\mathcal {N}}_{h}$ induces the weak topology on ${\mathcal {M}}$. Let us first recall the definition of weak convergence.

Definition 1

A sequence of measures $(\mu _N)_{N\in {\mathbb {N}}}$ is said to weakly converge to $\mu \in {\mathcal {M}}$ if

$$\begin{aligned} \lim _{N\rightarrow \infty } \int _\Omega f(x)d\mu _N(x) = \int _{\Omega } f(x) d\mu (x) \end{aligned}$$

for all continuous functions $f:\Omega \rightarrow {\mathbb {R}}$. The shorthand notation for weak convergence is

$$\begin{aligned} \mu _N \underset{N\rightarrow \infty }{\rightharpoonup } \mu . \end{aligned}$$

Proposition 3

Assume that $h\in {\mathcal {C}}(\Omega )$ and that $\hat{h}(\xi )\ne 0$, $\forall \xi \in {\mathbb {Z}}^d$. Then for all sequences $(\mu _N)_{N\in {\mathbb {N}}}$ in ${\mathcal {M}}$ satisfying $\Vert \mu _N\Vert _{TV}\le M <+\infty , \; \forall N\in {\mathbb {N}}$,

$$\begin{aligned} \lim _{N\rightarrow \infty }{\mathcal {N}}_{h}(\mu _N) =0 \quad \Leftrightarrow \quad \mu _N\underset{N\rightarrow \infty }{\rightharpoonup } 0. \end{aligned}$$

Proof

Let $\left( \mu _N \right) _{N\in {\mathbb {N}} }$ be a sequence of signed measures in ${\mathcal {M}}$.

If $\mu _N \rightharpoonup 0$, then $\hat{\mu }_N(\xi ) = \mu _N(e^{i2\pi \langle \xi , \cdot \rangle }) \rightarrow 0$ for all $\xi \in {\mathbb {Z}}^d$. Since $|\hat{\mu }_N(\xi ) \hat{h}(\xi )| \le 2 M |\hat{h}(\xi )|$ for all $\xi \in {\mathbb {Z}}^d$ and $\displaystyle \sum _{\xi \in {\mathbb {Z}}^d} |2 M \hat{h}(\xi )|^2 < \infty$, dominated convergence yields that ${\mathcal {N}}_{h}(\mu _N) \rightarrow 0$.

Conversely, assume that ${\mathcal {N}}_{h}(\mu _N) \rightarrow 0$. Since the $\mu _N$ are bounded, there are subsequences $\mu _{N_s}$ that converge weakly to a measure $\nu$ that depends on the subsequence. We have to prove that $\nu = 0$ for all such subsequences. Since ${\mathcal {N}}_{h}(\mu _N) \rightarrow 0$, we have $\hat{\mu }_N(\xi ) \rightarrow 0$ for all $\xi \in {\mathbb {Z}}^d$. Therefore, $\hat{\nu }(\xi ) = 0, \; \forall \xi \in {\mathbb {Z}}^d$. This is equivalent to $\nu =0$ (see, e.g., [16, p.36]), ending the proof. $\square$

3.2 Existence of Solutions

The first important question one may ask is whether problem (6) admits a solution or not. Proposition 4 provides sufficient conditions for existence to hold.

Proposition 4

If ${\mathcal {M}}_N$ is weakly compact, then problem (6) admits at least a solution. In particular, if ${\mathcal {M}}_N$ is weakly closed and bounded in TV-norm, problem (6) admits at least a solution.

Proof

Assume ${\mathcal {M}}_N$ is weakly compact. Consider a minimizing sequence $\mu _n \in {\mathcal {M}}_N$. By compactness, there is a $\mu \in {\mathcal {M}}_N$ and a subsequence $(\mu _{n_k})_{k\in {\mathbb {N}}}$ such that ${\mu _{n_k}} \underset{k\rightarrow +\infty }{\rightharpoonup } \mu$. By Proposition 3, ${\mathcal {N}}_h$ induces the weak topology on any TV-bounded set of signed measures, so that $\displaystyle \lim _{k\rightarrow \infty } {\mathcal {N}}_h(\pi - \mu _k) = {\mathcal {N}}_h(\pi - \mu )$.

Since closed balls in TV-norms are weakly compact, any weakly closed TV-bounded set is weakly compact. $\square$

A key concept that will appear in the continuous line drawing problem is that of pushforward or empirical measure [4] defined hereafter. Let $(X,\gamma )$ denote an arbitrary probability space. Given a function $p:X\rightarrow \Omega$, the empirical measure associated with p is denoted by $p_*\gamma$. It is defined for any measurable set B by

$$\begin{aligned} p_*\gamma (B)&:=\gamma (p^{-1}(B)), \end{aligned}$$

where $\gamma$ denotes the Lebesgue measure on the interval [0, 1]. Intuitively, the quantity $p_*\gamma (B)$ represents the “time” spent by the function p in B. Note that $p_*\gamma$ is a probability measure since it is positive and $p_*\gamma (\Omega )=1$. Given a measure $\mu$ of kind $\mu =p_*\gamma$, the function p is called the parameterization of $\mu$.

Let ${\mathcal {P}}$ denote a set of parameterizations $p:X\rightarrow \Omega$ and ${\mathcal {M}}({\mathcal {P}})$ denote the associated set of pushforward-measures:

$$\begin{aligned} {\mathcal {M}}({\mathcal {P}}) :=\{ \mu = p_*\gamma , p\in {\mathcal {P}} \}. \end{aligned}$$

In the rest of this section, we give sufficient conditions so that a projection on ${\mathcal {M}}({\mathcal {P}})$ exists. We first need the following proposition.

Proposition 5

Let $(p_n)_{n\in {\mathbb {N}}}$ denote a sequence in ${\mathcal {P}}$ that converges to p pointwise. Then $({p_n}_*\gamma )_{n\in {\mathbb {N}}}$ converges weakly to $p_*\gamma$.

Proof

Let $f\in {\mathcal {C}}(\Omega )$. Since $\Omega$ is compact, f is bounded. Hence dominated convergence yields $\int _{X} f(p_n(x)) - f(p(x)) d\gamma (x) \rightarrow 0$. $\square$

Proposition 6

Assume that ${\mathcal {P}}$ is compact for the topology of pointwise convergence. Then there exists a minimizer to problem (6) with ${\mathcal {M}}_N={\mathcal {M}}({\mathcal {P}})$.

Proof

By Proposition 4, it is enough to show that ${\mathcal {M}}({\mathcal {P}})$ is weakly compact. First, ${\mathcal {M}}({\mathcal {P}})$ is bounded in TV-norm since it is a subspace of probability measures. Consider a sequence $(p_n)_{n\in {\mathbb {N}}}$ in ${\mathcal {P}}$ such that the sequence $({p_n}_*\gamma )_{ n\in {\mathbb {N}}}$ weakly converges to a measure $\mu$. Since ${\mathcal {P}}$ is compact for the topology of pointwise convergence, there is a subsequence $(p_{n_k})_{k\in {\mathbb {N}}}$ converging pointwise to $p\in {\mathcal {P}}$. By Proposition 5, the pushforward-measure $p_*\gamma =\mu$ so that $\mu \in {\mathcal {M}}({\mathcal {P}})$ and ${\mathcal {P}}$ is weakly closed. $\square$

3.3 Consistency

In this section, we consider a sequence $({\mathcal {M}}_N)_{N\in {\mathbb {N}}}$ of weakly compact subsets of ${\mathcal {M}}_\Delta$. By Proposition 4, there exists a minimizer $\mu _N^*\in {\mathcal {M}}_N$ to problem (6) for every N. We study conditions on $({\mathcal {M}}_N)_{N\in {\mathbb {N}}}$ that ensure consistency, i.e., $\mu ^*_N \underset{N\rightarrow \infty }{\rightharpoonup } \pi$. In the case of image rendering, it basically means that if N is taken sufficiently large, the projection $\mu ^*_N$ and the target image $\pi$ will be indistinguishable from a perceptual point of view.

In order to evaluate distances between $\mu _N^*$ and $\pi$, the most natural metric is the minimized norm ${\mathcal {N}}_h(\mu ^*_N-\pi )$. However, its analysis is easy in the Fourier domain, whereas all measures sets in this paper are defined in the space domain. We therefore prefer to use another metrization of weak convergence, given by the transportation distance. Moreover, we will see in Theorem 1 that the transportation distance defined below dominates ${\mathcal {N}}_h$.

Definition 2

The $L^1$ transportation distance, also known as Kantorovitch or Wasserstein distance, between two measures with same TV norm is given by

$$\begin{aligned} W_1(\mu , \nu ) :=\inf _{c} \int \left||x - y \right||_1 \mathrm {d}c(x,y), \end{aligned}$$

where the infimum runs over all couplings of $\mu$ and $\nu$, that is, the measures c on $\Omega \times \Omega$ with marginals satisfying $c(A ,\Omega ) = \mu (A)$ and $c(\Omega , A) = \nu (A)$ for all Borelians A.

Equivalently, we may define the distance through the dual, that is the action on Lipschitz functions:

$$\begin{aligned} W_1(\mu , \nu ) = \sup _{f : Lip(f) \le 1} \mu (f) - \nu (f). \end{aligned}$$

(7)

We define the point-to-set distance as

$$\begin{aligned} W_1( {\mathcal {M}}_N, \pi ) :=\inf _{\mu \in {\mathcal {M}}_N} W_1(\mu ,\pi ). \end{aligned}$$

Obviously this distance satisfies:

$$\begin{aligned} W_1( {\mathcal {M}}_N, \pi ) \le \delta _N :=\sup _{\pi \in {\mathcal {M}}_\Delta } \inf _{\mu \in {\mathcal {M}}_N} W_1(\mu ,\pi ). \end{aligned}$$

(8)

Theorem 1

Assume that $h\in {\mathcal {C}}(\Omega )$ denote a Lipschitz continuous function with Lipschitz constant L. Then

$$\begin{aligned} {\mathcal {N}}_h(\mu -\pi ) \le L W_1(\mu , \pi ) \end{aligned}$$

(9)

and

$$\begin{aligned} {\mathcal {N}}_h(\mu ^*_N - \pi ) \le L W_1( {\mathcal {M}}_N, \pi ) \le L \delta _N. \end{aligned}$$

(10)

Proof

Let $\tau _x:h(\cdot )\mapsto h(x-\cdot )$ denote the symmetrization and shift operator. Let us first prove inequality (9):

$$\begin{aligned} \Vert h\star (\mu - \pi ) \Vert _2^2&= \int _{\Omega } \left[ h\star (\mu - \pi ) (x) \right] ^2\, \hbox {d}x \\&= \int _{\Omega } \left| \mu (\tau _x h) - \pi (\tau _x h) \right| ^2 \, \hbox {d}x \\&\le |\Omega | L^2 W_1^2(\mu , \pi ), \end{aligned}$$

where we used the dual definition (7) of the Wasserstein distance to obtain the last inequality.

Let $\mu _N$ denote a minimizer of $\displaystyle \inf _{\mu \in {\mathcal {M}}_N} W_1(\mu ,\pi )$. If no minimizer exists, we may take an $\epsilon$-solution with arbitrary small $\epsilon$ instead. By definition of the projection $\mu _N^*$, we have

$$\begin{aligned} {\mathcal {N}}_h(\mu _N^*-\pi ) \le {\mathcal {N}}_h(\mu _N-\pi ) \le W(\mu _N,\pi ) \le \delta _N. \end{aligned}$$

(11)

$\square$

Even though the bound (10) is pessimistic in general, it provides some insight into which sequences of measures spaces allow a fast weak convergence.

3.4 Application to Image Stippling

In order to illustrate the proposed theory, we first focus on the case of N-point measures ${\mathcal {M}}(\Omega ^N)$ defined in Eq. 2. This setting is the standard one considered for probability quantization (see [13, 18] for similar results). As mentioned earlier, it has many applications including image stippling. Our main results read as follows.

Theorem 2

Let h denote an L-Lipschitz kernel. The set of N-point measures ${\mathcal {M}}(\Omega ^N)$ satisfies the following inequalities:

$$\begin{aligned} \delta _N = \sup _{\pi \in {\mathcal {M}}_\Delta } \inf _{\mu \in {\mathcal {M}}(\Omega ^N)} W_1(\mu ,\pi ) \le \left( \frac{\sqrt{d}}{2}+1 \right) \frac{1}{N^{1/d}-1} \end{aligned}$$

(12)

and

$$\begin{aligned} \sup _{\pi \in {\mathcal {M}}_\Delta } \inf _{\mu \in {\mathcal {M}}(\Omega ^N)} {\mathcal {N}}_h(\mu - \pi ) \le L \left( \frac{\sqrt{d}}{2}+1 \right) \frac{1}{N^{1/d}-1}. \end{aligned}$$

(13)

As a direct consequence, we get the following corollary.

Corollary 1

Let ${\mathcal {M}}_N={\mathcal {M}}(\Omega ^N)$ denote the set of N-point measures. Then there exist solutions $\mu ^*_N$ to the projection problem (6). Moreover, for any L-Lipschitz kernel $h\in {\mathcal {C}}(\Omega )$:

• i) $\mu _N^*\underset{N\rightarrow \infty }{\rightharpoonup } \pi$.

• ii) ${\mathcal {N}}_h(\mu ^*_N - \pi ) = {\mathcal {O}}\left( L N^{-\frac{1}{d}} \right) .$

Proof

We first evaluate the bound $\delta _N$ defined in (8). To this end, for any given $\pi$, we construct an explicit sequence of measures $\mu _0, \ldots , \mu _N$, the last of which is an N-point measure approximating $\pi$.

Note that ${\mathbb {T}}^d$ can be thought of as the unit cube $[0,1)^d$. It may therefore be partitioned in $C^d$ smaller cubes of edge length 1 / C with $C=\lfloor N^{1/d}\rfloor$. We let $(\omega _i)_{1\le i \le C^d}$ denote the small cubes and $x_i$ denote their center. We assume that the cubes are ordered in such a way that $\omega _i$ and $\omega _{i+1}$ are contiguous.

We define $\displaystyle \mu _0 = \sum _{i=1}^{C^d} \pi (\omega _i)\delta _{x_i}$. The measure $\mu _0$ satisfies

$$\begin{aligned} W_1(\pi , \mu _0)&\leqslant \frac{1}{2} \sup _i \text {Diameter}(\omega _i) \\&\leqslant \frac{\sqrt{d}}{2}\lfloor N^{1/d} \rfloor ^{-1} \\&\leqslant \frac{\sqrt{d}}{2}\frac{1}{N^{1/d}-1}, \end{aligned}$$

but is not an N-point measure since $N \pi (\omega _i)$ is not an integer.

To obtain an N-point measure, we recursively build $\mu _l$ as follows:

$$\begin{aligned} \mu _l(\{x_l\})&= \frac{1}{N} \left\lfloor { N \mu _{l-1}(\{x_l\}) }\right\rfloor , \\ \mu _l(\{x_{l+1}\})&= \mu _{l-1}(\{x_{l+1}, x_l\}) - \frac{1}{N} \left\lfloor {N \mu _{l-1}(\{x_l\}) }\right\rfloor \\&\qquad \text {if}\; l\le (1/C)^d-1, \\ \mu _l(\{x_i\})&= \mu _{l-1}(\{x_i\}) \text { if } i\notin \{l, l+1\}. \end{aligned}$$

We stop the process for $l=(1/C)^d$ and let $\tilde{\mu }= \mu _{(1/C)^d}$. Notice that $N\mu _l(x_i)$ is an integer for all $i\leqslant l$ and that $\mu _l$ is a probability measure for all l. Therefore, $\tilde{\mu }$ is an N-point measure. Moreover;

$$\begin{aligned} W_1(\mu _l, \mu _{l+1})&\leqslant \frac{1}{N} \Vert x_l - x_{l+1}\Vert _2 \\&\leqslant \frac{1}{N(N^{1/d}-1)}. \end{aligned}$$

Since the transportation distance is a distance, we have the triangle inequality. Therefore,

$$\begin{aligned} W_1(\pi , \tilde{\mu })&\le W_1(\pi , \mu _0) + \sum _{l=1}^N W_1(\mu _{l-1}, \mu _l), \\&= \frac{\sqrt{d}}{2}\frac{1}{N^{1/d}-1} + N\frac{1}{N(N^{1/d}-1)} \\&= \left( \frac{\sqrt{d}}{2}+1 \right) \frac{1}{N^{1/d}-1}. \end{aligned}$$

The inequality (13) is a direct consequence of this result and Proposition 1.

We now turn to the proof of Corollary 1. To prove the existence, first notice that the projection problem (6) can be recast as (1). Let $p=(p_1,\ldots ,p_N) \in \Omega ^N$. The mapping $p\mapsto \left\| h\star \left( \pi - \frac{1}{N}\sum _{i=1}^N \delta _{p_i}\right) \right\| _2^2$ is continuous. Problem (1) therefore consists of minimizing a finite dimensional continuous function over a compact set. The existence of a solution follows. Point ii) is a direct consequence of Theorem 1 and bound (13). Point i) is due to the fact that ${\mathcal {N}}_h$ metrizes weak convergence, see Proposition 3. $\square$

4 Numerical Resolution

In this section, we propose a generic numerical algorithm to solve the projection problem (6). We first draw a connection with the recent works on electrostatic halftoning [26, 28] in Sect. 4.1. We then recall the algorithm proposed in [26, 28] when ${\mathcal {M}}_N$ is the set of N-point measures. Finally, we extend this principle to arbitrary measures spaces and provide some results on their theoretical performance in Sect. 4.3.

4.1 Relationship to Electrostatic Halftoning

In a recent series of papers [12, 14, 26, 28], it was suggested to use electrostatic principles to perform image halftoning. This technique was shown to produce results having a number of nice properties such as few visual artifacts. Motivated by preliminary results in [26], the authors of [28] proposed to choose the N points locations $p=(p_i)_{1\le i \le N}\in \Omega ^N$ as a solution of the following variational problem:

$$\begin{aligned} \min _{p\in \Omega ^N} \underbrace{\frac{1}{2N^2}\sum _{i=1}^N \sum _{j=1}^N H(p_i - p_j)}_{\text {Repulsion potential}} - \underbrace{\frac{1}{N}\sum _{i=1}^N \int _{\Omega } H(x - p_i) \,\hbox {d}\pi (x)}_{\text {Attraction potential}}, \end{aligned}$$

(14)

where H was initially defined as $H(x) = \left\| x\right\| _2$ in [26, 28] and then extended to a few other functions in [12]. The attraction potential tends to attract points towards the bright regions of the image (regions where the measure $\pi$ has a large mass), whereas the repulsion potential can be regarded as a counter-balancing term that tends to maximize the distance between all pairs of points. Deriving an algorithm to solve problem (14) with good precision can be seen as a generalization of Thomson’s problem [29], which belongs to Smale’s list of mathematical questions to solve for the 21st century [27].

Proposition 7 below shows that this attraction–repulsion problem is actually equivalent to the projection problem (6) on the set of N-point measures defined in (2). We let ${\mathcal {P}}^*$ denote the set of solutions of (14) and ${\mathcal {M}}({\mathcal {P}}^*)=\{\mu = \frac{1}{N}\sum _{i=1}^N \delta _{p_i^*},\ p^*\in {\mathcal {P}}^*\}$. We also let ${\mathcal {M}}^*$ denote the set of solutions to problem (6).

Proposition 7

Let $h\in {\mathcal {C}}(\Omega )$ denote a kernel such that $|\hat{h}|(\xi ) > 0, \; \forall \xi \in {\mathbb {Z}}^d$. Define H through its Fourier series by $\hat{H}(\xi ) = |\hat{h}|^2(\xi )$. Then problems (6) and (14) yield the same solutions set:

$$\begin{aligned} {\mathcal {M}}^*={\mathcal {M}}({\mathcal {P}}^*). \end{aligned}$$

Proof

First, note that since H and h are continuous, both problems are well defined and admit at least one solution. Let us first expand the $L^2$-norm in (6):

$$\begin{aligned} \frac{1}{2}\Vert h\star (\mu - \pi ) \Vert _2^2&= \frac{1}{2}\langle h\star (\mu -\pi ), h\star (\mu - \pi ) \rangle \\&= \frac{1}{2} \langle H\star (\mu -\pi ), \mu - \pi \rangle \\&= \frac{1}{2} \left( \langle H\star \mu , \mu \rangle - 2 \langle H\star \mu , \pi \rangle + \langle H\star \pi , \pi \rangle \right) . \end{aligned}$$

Therefore,

$$\begin{aligned} \mathop {\mathrm {Arg\, min}}_{\mu \in {\mathcal {M}}_N} \frac{1}{2} \Vert h\star (\mu -\pi )\Vert _2^2 = \mathop {\mathrm {Arg\, min}}_{\mu \in {\mathcal {M}}_N} \frac{1}{2} \left( \langle H\star \mu , \mu \rangle - 2 \langle H\star \mu , \pi \rangle \right) . \end{aligned}$$

To conclude, it suffices to remark that for a measure $\mu$ of kind $\mu =\frac{1}{N}\sum _{i=1}^N \delta _{p_i}$,

$$\begin{aligned}&\frac{1}{2} \left( \langle H\star \mu , \mu \rangle - 2 \langle H\star \mu , \pi \rangle \right) \\&= \frac{1}{2N^2}\sum _{i=1}^N \sum _{j=1}^N H(p_i - p_j) - \frac{1}{N}\sum _{i=1}^N \int _{\Omega } H(x - p_i) \,\hbox {d}\pi (x). \end{aligned}$$

$\square$

Remark 2

It is rather easy to show that a sufficient condition for h to be continuous is that $H\in {\mathcal {C}}^{3}(\Omega )$ or H be Hölder continuous with exponent $\alpha >2$. These conditions are, however, strong and exclude kernels such as $H(x) = \Vert x\Vert _2$.

From Remark 1, it is actually sufficient that $h\in {\mathcal {L}}^\infty (\Omega )$ for ${\mathcal {N}}_h$ to be well defined. This leads to less stringent conditions on H. We do not discuss this possibility further to keep the arguments simple.

Remark 3

Corollary 1 sheds light on the approximation quality of the minimizers of attraction–repulsion functionals. Let us mention that consistency of problem (14) was already studied in the recent papers [10–12]. To the best of our knowledge, Corollary 1 is stronger than existing results since it yields a convergence rate and holds true under more general assumptions.

Though formulations (6) and (14) are equivalent, we believe that the proposed one (6) has some advantages: it is probably more intuitive, shows that the convolution kernel h should be chosen depending on physical considerations, and simplifies some parts of the mathematical analysis such as consistency. However, the set of admissible measures ${\mathcal {M}}(\Omega ^N)$ has a complex geometry, and this formulation as such is hardly amenable to numerical implementation. For instance, ${\mathcal {M}}(\Omega ^N)$ is not a vector space, since adding two N-point measures usually leads to (2N)-point measures. On the other hand, the attraction–repulsion formulation (14) is an optimization problem of a continuous function over the set $\Omega ^N$. It therefore looks easier to handle numerically using non-linear programming techniques. This is what we will implement below, following previous works [26, 28].

4.2 The Case of N-point Measures

In this section, we develop an algorithm specific to the projection on the set of N-point measures defined in (2). This algorithm generates stippling results such as in Fig. 1. In stippling, the measure is supported by a union of discs, i.e., a sum of diracs convoluted with a disc indicator. We simply have to consider the image deconvoluted with this disc indicator as $\pi$ to include stippling in the framework of N-point measures. We will generalize this algorithm to arbitrary sets of measures in the next section. We assume without further mention that $\hat{H}(\xi )$ is real and positive for all $\xi$. This implies that H is real and even. Moreover, Proposition 7 implies that problems (6) and (14) yield the same solutions sets. We let $p=(p_1,\ldots ,p_N)$ and set

$$\begin{aligned} \tilde{J}(p) :=\underbrace{\frac{1}{2N^2}\sum _{i=1}^N \sum _{j=1}^N H(p_i - p_j)}_{F(p)} - \underbrace{\frac{1}{N}\sum _{i=1}^N \int _{\Omega } H(x - p_i) \,\hbox {d}\pi (x)}_{\tilde{G}(p)}. \end{aligned}$$

(15)

The projection problem therefore rereads as

$$\begin{aligned} \min _{p\in \Omega ^N} \tilde{J}(p). \end{aligned}$$

(16)

For practical purposes, the integrals in $\tilde{G}(p)$ first have to be replaced by numerical quadratures. We let $G(p)\simeq \tilde{G}(p)$ denote the numerical approximation of $\tilde{G}(p)$. This approximation can be written as

$$\begin{aligned} G(p) = \frac{1}{N}\sum _{i=1}^N \sum _{j=1}^n w_j H(x_j-p_i)\pi _j, \end{aligned}$$

where n is the number of discretization points $x_j$ and $w_j$ are weights that depend on the integration rule. In particular, since we want to approximate integration with respect to a probability measure, we require that

$$\begin{aligned} \sum _{j=1}^n w_j \pi _j = 1. \end{aligned}$$

In our numerical experiments, we use the rectangle rule. We may then take $\pi _j$ as the integral of $\pi$ over the corresponding rectangle. After discretization, the projection problem therefore rereads as

$$\begin{aligned} \min _{p\in \Omega ^N} J(p):=F(p) - G(p). \end{aligned}$$

(17)

The following result [1, Theorem5.3] will be useful to design a convergent algorithm. We refer to [1] for a comprehensive introduction to the definition of Kurdyka–Łojasiewicz functions and to its applications to algorithmic analysis. In particular, we recall that semi-algebraic functions are Kurdyka–Łojasiewicz [19].

Theorem 3

Let $K : {\mathbb {R}}^n \rightarrow {\mathbb {R}}$ be a ${\mathcal {C}}^1$ function whose gradient is L-Lipschitz continuous, and let C be a nonempty closed subset of ${\mathbb {R}}^n$. Given $\varepsilon \in \left( 0,\frac{1}{2L}\right)$ and a sequence of stepsizes $\gamma ^{(k)}$ such that $\varepsilon< \gamma ^{(k)} < \frac{1}{L}-\varepsilon$, we consider a sequence $(x^{(k)})_{k\in {\mathbb {N}}}$ that complies with

$$\begin{aligned} x^{(k+1)} \in P_C\left( x^{(k)} - \gamma ^{(k)} \nabla K (x^{(k)}) \right) , \text{ with } x^{(0)}\in C. \end{aligned}$$

(18)

If the function $K+i_C$ is a Kurdyka–Łojasiewicz function and if $(x^{(k)})_{k\in {\mathbb {N}}}$ is bounded, then the sequence $(x^{(k)})_{k\in {\mathbb {N}}}$ converges to a critical point $x^*$ in C.

A consequence of this important result is the following.

Corollary 2

Assume that H is a ${\mathcal {C}}^1$ semi-algebraic function with L-Lipschitz continuous gradient. Set $0<\gamma <\frac{N}{3L}$. Then the following sequence converges to a critical point of problem (17):

$$\begin{aligned} p^{(k+1)} \in P_{\Omega ^N}\left( p^{(k)} - \gamma \nabla J (p^{(k)}) \right) , \text{ with } p^{(0)}\in \Omega ^N. \end{aligned}$$

(19)

If H is convex, $0<\gamma <\frac{N}{2L}$ ensures convergence to a critical point.

Remark 4

The semi-algebraicity is useful to obtain convergence to a critical point. In some cases, it might however not be needed. For instance, in the case where C is convex and closed, it is straightforward to establish the decrease of the cost function assuming only that $\nabla J$ is Lipschitz. Nesterov in [23, Theorem 3] also provides a convergence rate in ${\mathcal {O}}\left( \frac{1}{\sqrt{k+1}}\right)$ in terms of objective function values.

Proof

First notice that J is semi-algebraic as a finite sum of semi-algebraic functions.

Function J is ${\mathcal {C}}^1$ by the Leibniz integral rule. Let $\partial _k$ denote the derivative with respect to $p_k$. Then, since H is even,

$$\begin{aligned} \partial _k F(p) = \frac{1}{N^2}\sum _{i=1}^N \nabla H(p_k-p_i) \end{aligned}$$

(20)

and

$$\begin{aligned} \partial _k G(p) = -\frac{1}{N} \sum _{j=1}^n w_j \nabla H(x_j-p_k) \pi _j. \end{aligned}$$

(21)

For any two sets of N points $p^{(1)}=(p_k^{(1)})_{1\leqslant k \leqslant N},\ p^{(2)}=(p_k^{(2)})_{1\leqslant k \leqslant N}$:

$$\begin{aligned} \Vert \nabla F(p^{(1)}) - \nabla F (p^{(2)})\Vert _2^2&=\sum _{k=1}^N \Big \Vert \partial _k F(p^{(1)}) - \partial _k F(p^{(2)})\Big \Vert _2^2 \\&=\frac{1}{N^4}\sum _{k=1}^N \Big \Vert \sum _{i=1}^N \nabla H (p_k^{(1)}-p_i^{(1)}) - \nabla H (p_k^{(2)}-p_i^{(2)})\Big \Vert _2^2 \\&\leqslant \frac{1}{N^4}\sum _{k=1}^N \Big ( \sum _{i=1}^N L \Vert p_k^{(1)}-p_i^{(1)}- (p_k^{(2)}-p_i^{(2)})\Vert _2 \Big )^2 \\&\leqslant \frac{L^2}{N^4}\sum _{k=1}^N \Big ( \sum _{i=1}^N \Vert p_k^{(1)}- p_k^{(2)}\Vert _2+\Vert p_i^{(1)}-p_i^{(2)}\Vert _2\Big )^2 \\&\leqslant \frac{L^2}{N^4}\sum _{k=1}^N N \Big ( \sum _{i=1}^N \big (\Vert p_k^{(1)}- p_k^{(2)}\Vert _2+\Vert p_i^{(1)}-p_i^{(2)}\Vert _2\big )^2\Big ) \\&\leqslant \frac{2L^2}{N^3}\sum _{k=1}^N \sum _{i=1}^N \Vert p_k^{(1)}- p_k^{(2)}\Vert _2^2+\Vert p_i^{(1)}-p_i^{(2)}\Vert _2^2 \\&=\frac{4L^2}{N^2}\Vert p^{(1)}-p^{(2)}\Vert _2^2, \end{aligned}$$

and

$$\begin{aligned} \Vert \nabla G(p^{(1)}) - \nabla G (p^{(2)})\Vert _2^2=&\sum _{k=1}^N \Big \Vert \partial _k G(p^{(1)}) - \partial _k G(p^{(2)})\Big \Vert _2^2 \\ =&\frac{1}{N^2}\sum _{k=1}^N\Big \Vert \sum _{j=1}^n w_j \pi _j \big (\nabla H (p_k^{(1)}-x) - \nabla H (p_k^{(2)}-x)\big ) \Big \Vert _2^2 \\ \leqslant&\frac{1}{N^2}\sum _{k=1}^N \Big (\sum _{j=1}^n w_j \pi _j L \Vert p_k^{(1)}-p_k^{(2)}\Vert \Big )^2 \\ =&\frac{L^2}{N^2} \Big (\sum _{j=1}^{n} w_j \pi _j\Big ) \Vert p^{(1)}-p^{(2)}\Vert _2^2 \\ =&\frac{L^2}{N^2} \Vert p^{(1)}-p^{(2)}\Vert _2^2. \end{aligned}$$

Finally,

$$\begin{aligned}&\Vert \nabla J(p^{(1)}) - \nabla J (p^{(2)})\Vert _2 \\&\leqslant \Vert \nabla F(p^{(1)}) - \nabla F (p^{(2)})\Vert _2 + \Vert \nabla G(p^{(1)}) - \nabla G (p^{(2)})\Vert _2 \\&\leqslant \Big (\frac{2L}{N} + \frac{L}{N} \Big ) \Vert p^{(1)}-p^{(2)}\Vert _2 = \frac{3L}{N} \Vert p^{(1)}-p^{(2)}\Vert _2. \end{aligned}$$

Now, if we assume that H is convex and ${\mathcal {C}}^2$ (this hypothesis is not necessary, but simplifies the proof), then F and G are also convex and ${\mathcal {C}}^2$. We let $\nabla ^2 F$ denote the Hessian matrix of F. Given the previous inequalities, we have $0\preccurlyeq \nabla ^2 F \preccurlyeq \frac{2L}{N}\mathrm {Id}$ and $0\preccurlyeq \nabla ^2 G \preccurlyeq \frac{L}{N}\mathrm {Id}$. Hence, the largest eigenvalue in magnitude of $\nabla ^2(F-G)$ is bounded above by $\frac{2L}{N}$.

Moreover, the sequence $(x^{(k)})_{k\in {\mathbb {N}}}$ is bounded since $\Omega ^N$ is bounded. $\square$

4.3 A Generic Projection Algorithm

We now turn to the problem of finding a solution of (6), where ${\mathcal {M}}_N$ denotes our arbitrary measures set. In the previous section, it was shown that critical points of $J+i_{\Omega ^N}$ could be obtained with a simple projected gradient algorithm under mild assumptions. Although this algorithm only yields critical points, they usually correspond to point configurations that are visually pleasing after only a few hundreds of iterations. For instance, the lion in Fig. 1b was obtained after 500 iterations. Motivated by this appealing numerical behavior, we propose to extend this algorithm to the following abstract construction:

• 1. Approximate ${\mathcal {M}}_N$ by a subset ${\mathcal {A}}_n$ of n-point measures.

• 2. Use the generic Algorithm (18) to obtain an approximate projection $\mu _n^*$ on ${\mathcal {A}}_n$.

• 3. When possible, reconstruct an approximation $\mu _N\in {\mathcal {M}}_N$ of a projection $\mu _N^*$ using $\mu _n^*$.

To formalize the approximation step, we need the definition of Hausdorff distance.

Definition 3

The Hausdorff distance between two subsets X and Y of a metric space (M, d) is

$$\begin{aligned} {\mathcal {H}}_d(X,Y) := \max \left\{ \sup _{x\in X} \inf _{y \in Y} d(x,y), \sup _{y\in Y} \inf _{x \in X} d(y,x) \right\} . \end{aligned}$$

In words, two sets are close if any point in one set is close to at least a point in the other set. In this paper, the relevant metric space is the space of signed measures ${\mathcal {M}}$ with the norm ${\mathcal {N}}_h$. The corresponding Hausdorff distance is denoted by ${\mathcal {H}}_{{\mathcal {N}}_h}$.

The following proposition clarifies why controlling the Hausdorff distance is relevant to design approximation sets ${\mathcal {A}}_n$.

Proposition 8

Let ${\mathcal {A}}_n$ and ${\mathcal {M}}_N$ be two TV-bounded weakly closed sets of measures such that ${\mathcal {H}}_{{\mathcal {N}}_h}({\mathcal {A}}_n, {\mathcal {M}}_N) \le \varepsilon$. Let $\mu _n^*$ be a projection on ${\mathcal {A}}_n$. Then there is a point $\mu _N \in {\mathcal {M}}_N$ such that ${\mathcal {N}} _h(\mu _n^* - \mu _N) \le \varepsilon$ and $\displaystyle {\mathcal {N}}_h(\pi - \mu _N) \le \inf _{\mu \in {\mathcal {M}}_N} {\mathcal {N}}_h(\pi - \mu ) + 2 \varepsilon$.

Corollary 3

If $\displaystyle \lim _{n\rightarrow \infty }{\mathcal {H}}_{{\mathcal {N}}_h}({\mathcal {A}}_n ,{\mathcal {M}}_N) = 0$, then $(\mu _n^*)_{n\in {\mathbb {N}}}$ converges weakly along a subsequence to a solution $\mu _N^*$ of problem (6).

Proof

We first prove Proposition 8. Since ${\mathcal {A}}_n$ and ${\mathcal {M}} _N$ are bounded weakly closed, by Proposition 4, there exists at least one projection $\mu _n^*$ on ${\mathcal {A}}_n$ and one projection $\mu _N^*$ on ${\mathcal {M}}_N$.

Moreover, since ${\mathcal {A}}_n$ and ${\mathcal {M}} _N$ are bounded weakly closed, they are also closed for ${\mathcal {N}} _h$, so that the infimum in the Hausdorff distances are attained. Hence there exists $\mu _n\in {\mathcal {A}}_n$ such that ${\mathcal {N}}_h(\mu _n-\mu _N^*)\le {\mathcal {H}}_{{\mathcal {N}}_h}({\mathcal {A}}_n, {\mathcal {M}}_N) \le \varepsilon$ and $\mu _N \in {\mathcal {M}}_N$ such that ${\mathcal {N}} _h(\mu _N - \mu ^*_n) \le \varepsilon$. The proposition follows from the triangle inequality:

$$\begin{aligned} {\mathcal {N}}_h(\mu _N -\pi )&\le {\mathcal {N}} _h(\mu _N - \mu _n^* ) + {\mathcal {N}}_h( \mu _n^* - \pi ) \\&\le \varepsilon + {\mathcal {N}} _h(\mu _n - \pi ) \\&\le \varepsilon + {\mathcal {N}} _h(\mu _n - \mu _N^*) + {\mathcal {N}}_h(\mu _N^* - \pi )\\&\le {\mathcal {N}}_h(\mu _N^* - \pi ) + 2 \varepsilon . \end{aligned}$$

For the corollary, let us consider the sequence $(\mu ^*_n)_{n\in {\mathbb {N}}}$ as n tends to infinity. Since all $\mu _n$ are in ${\mathcal {M}}_\Delta$, which is weakly compact, we have a subsequence that converges to $\mu _\infty ^*$. Since ${\mathcal {N}}_h$ is a metrization of weak convergence on ${\mathcal {M}}_N$, this $\mu _\infty ^*$ is indeed a solution to problem (6):

$$\begin{aligned} {\mathcal {N}}_h(\mu _\infty ^* - \pi )&= \lim _{n\rightarrow \infty } {\mathcal {N}}_h(\mu _n^* - \pi ) \\&= \inf _{\mu \in {\mathcal {M}}_N} {\mathcal {N}}_h(\pi - \mu ). \end{aligned}$$

$\square$

To conclude this section, we show that it is always possible to construct an approximation set ${\mathcal {A}}_n\subseteq {\mathcal {M}}(\Omega ^n)$ with a control on the Hausdorff distance to ${\mathcal {M}}_N$. Let ${\mathcal {M}}_N^\epsilon$ denote an $\epsilon$-enlargement of ${\mathcal {M}}_N$ w.r.t. the ${\mathcal {N}}_h$-norm; i.e.,

$$\begin{aligned} {\mathcal {M}}_N^\epsilon =\cup _{\mu _N \in {\mathcal {M}}_N} \{\mu \in {\mathcal {M}}_\Delta , {\mathcal {N}}_h(\mu -\mu _N) \le \epsilon \}. \end{aligned}$$

(22)

We may define an approximation set ${\mathcal {A}}_n^\epsilon$ as follows:

$$\begin{aligned} {\mathcal {A}}_n^\epsilon ={\mathcal {M}}(\Omega ^n) \cap {\mathcal {M}}_N^\epsilon . \end{aligned}$$

(23)

For sufficiently large n, this set is nonempty and can be rewritten as

$$\begin{aligned} {\mathcal {A}}_n^\epsilon =\left\{ \mu = \frac{1}{n}\sum _{i=1}^n \delta _{p_i}, \ \text { with } p=(p_i)_{1 \le i \le n} \in {\mathcal {P}}_n^\epsilon \right\} , \end{aligned}$$

(24)

where the parameterization set ${\mathcal {P}}_n^\epsilon$ depends on ${\mathcal {M}}_N$ and $\epsilon$. With this discretization of ${\mathcal {M}}_N$ at hand, one can then apply (at least formally) the following projected gradient descent algorithm:

$$\begin{aligned} p^{(k+1)} \in P_{{\mathcal {P}}_n^\epsilon }\left( p^{(k)} - \gamma \nabla J (p^{(k)}) \right) , \text{ with } p^{(0)}\in {\mathcal {P}}^\epsilon _n. \end{aligned}$$

(25)

The following proposition summarizes the main approximation result.

Proposition 9

Assume that h is L-Lipschitz. Set $\epsilon = \left( \frac{\sqrt{d}}{2} + 1 \right) \frac{L}{n^{1/d}-1}$ and ${\mathcal {A}}_n = {\mathcal {A}}_n^{\epsilon }$. Then

$$\begin{aligned} {\mathcal {H}}_{{\mathcal {N}}_h}\left( {\mathcal {A}}_n, {\mathcal {M}}_N\right) = {\mathcal {O}}\left( Ln^{-1/d}\right) . \end{aligned}$$

Proof

By construction, ${\mathcal {A}}_n$ satisfies

$$\begin{aligned} \sup _{\mu _n\in {\mathcal {A}}_n} \inf _{\mu _N\in {\mathcal {M}}_N} {\mathcal {N}}_h(\mu _n-\mu _N) \le \epsilon . \end{aligned}$$

Let $\mu _N$ be an arbitrary measure in ${\mathcal {M}}_N$. By inequality (12), there exists $\mu _n\in {\mathcal {M}}(\Omega ^n)$ such that ${\mathcal {N}}_h(\mu _n-\mu _N)\le \epsilon$. Therefore $\mu _n$ also belongs to ${\mathcal {A}}_n^\epsilon$. This shows that

$$\begin{aligned} \sup _{\mu _N\in {\mathcal {M}}_N} \inf _{\mu _n\in {\mathcal {A}}_n} {\mathcal {N}}_h(\mu _n-\mu _N) \le \epsilon . \end{aligned}$$

$\square$

The approximation process proposed (23) is nonconstructive since it does not provide any explicit formula for ${\mathcal {P}}_n^\epsilon$. Moreover, ${\mathcal {P}}^\epsilon _n$ can be an arbitrary set and the projection on ${\mathcal {P}}^\epsilon _n$ might not be implementable. We will provide constructive approximations for specific measures spaces in Sect. 5.

5 Application to Continuous Line Drawing

In this section, we concentrate on the continuous line drawing problem described in the introduction. We first construct a set of admissible measures ${\mathcal {M}}_T$ that is a natural representative of artistic continuous line drawings. The index T represents the time spent to draw the picture. We then show that using this set in problem (6) ensures existence of a solution and weak convergence of the minimizers $\mu _{T}^*$ to any $\pi \in {\mathcal {M}}_\Delta$. We finish by designing a numerical algorithm to solve the problem and analyze its theoretical guarantees.

5.1 Problem Formalization

Let us assume that an artist draws a picture with a pencil. The trajectory of the pencil tip can be defined as a parameterized curve $p:[0,T]\rightarrow \Omega$. The body, elbow, arm and hand are subject to nontrivial constraints [21]. The curve p should therefore belong to some admissible parameterized curves set denoted ${\mathcal {P}}_T$. In this paper, we simply assume that ${\mathcal {P}}_T$ contains curves with bounded first- and second-order derivatives in $L^q([0,T])$. More precisely, we consider the following sets of admissible curves:

• 1. Curves with bounded speed:

  $$\begin{aligned} {\mathcal {P}}_T^{1,\infty } = \Big \{ p\in (W^{1,\infty }([0,T]))^d,\ p([0,T]) \subset \Omega , \Vert \dot{p}\Vert _\infty \le \alpha _1\Big \}, \end{aligned}$$

  where $\alpha _1$ is a positive real.

• 2. Curves with bounded speed and acceleration:

  $$\begin{aligned} {\mathcal {P}}_T^{2,\infty } = \Big \{ p\in (W^{2,\infty }([0,T]))^d,\ p([0,T]) \subset \Omega , \Vert \dot{p}\Vert _\infty \le \alpha _1,&\\ \ \Vert \ddot{p}\Vert _\infty \le \alpha _2 \Big \},&\end{aligned}$$

  where $\alpha _1$ and $\alpha _2$ are positive reals. This set models rather accurately kinematic constraints that are met in vehicles. It is obviously a rough approximation of arm constraints.

• 3. The proposed theory and algorithm apply to a more general setting. For instance, they cover the case of curves with derivatives up to an arbitrary order bounded in $L^q$ with $q\in [1,\infty ]$. We let

  $$\begin{aligned} {\mathcal {P}}_T^{m,q} = \Big \{ p\in (W^{m,q}([0,T]))^d,\ p([0,T]) \subset \Omega ,&\\ \forall i\in \{1,\ldots ,m\},\ \Vert p^{(i)}\Vert _q \le \alpha _i\Big \},&\end{aligned}$$

  where $(\alpha _i)_{i=1\ldots m}$ are positive reals. This case will be treated only in the numerical experiments to illustrate the variety of results that can be obtained in applications.

Note that all above mentionned sets are convex. The convexity property will help deriving efficient numerical procedures.

In the rest of this section, we consider the following projection problem:

$$\begin{aligned} \inf _{\mu \in {\mathcal {M}}\left( {\mathcal {P}}_T^{m,q} \right) } {\mathcal {N}}_h(\mu -\pi ), \end{aligned}$$

(26)

with a special emphasis on the set ${\mathcal {M}}\left( {\mathcal {P}}_T^{m,\infty }\right)$ since it best describes standard kinematic constraints. This problem basically consists of finding the “best” way to represent a picture in a given amount of time T.

5.2 Existence and Consistency

We first provide existence results using the results derived in Sect. 3 for $q=\infty$.

Theorem 4

For any $m\in {\mathbb {N}}^*$, Problem (26) admits at least one solution in ${\mathcal {M}}\left( {\mathcal {P}}_T^{m,\infty } \right)$.

Proof

From Proposition 6, it suffices to show that ${\mathcal {P}}_T^{m,\infty }$ is compact for the topology of pointwise convergence.

Let $(p_n)_{n\in {\mathbb {N}}}$ be a sequence in ${\mathcal {P}}_T^{m,\infty }$ that converges pointwise to p. Since $p_n$ is in $W^{m,\infty }$, its $(m-1)$-th derivative is Lipschitz continuous. By definition of ${\mathcal {P}}_T^{m,\infty }$, the $p^{(m-1)}_n$ are both uniformly bounded by $\alpha _{m-1}$ and $\alpha _m$-Lipschitz, hence equicontinuous. Next, by Ascoli’s theorem, up to taking a subsequence, $p_n^{(m-1)}$ uniformly converges to a continuous $p^{(m-1)}$. Integrating yields that $p^{(i)}_n \rightarrow p^{(i)}$ uniformly for all $i \le m-1$, so that $\left||p^{(i)} \right||_{\infty } \le \alpha _i$ for $i \le m-1$. Finally, a limit of L-Lipschitz functions is also L-Lipschitz, so that $\left||p^{(m)} \right||_{\infty } \le \alpha _m$. Hence $p \in {\mathcal {P}}_T^{m,\infty }$, ending the proof. $\square$

Let us now turn to weak convergence.

Theorem 5

Let T be an arbitrary positive real. Let $\mu _T^* \in {\mathcal {M}}\left( {\mathcal {P}}_T^{m,\infty }\right)$ denote any solution of Problem (26). Then, for any Lipschitz kernel $h\in {\mathcal {C}}(\Omega )$:

• i) $\mu _T^* \underset{T\rightarrow \infty }{\rightharpoonup } \pi$,

• ii) ${\mathcal {N}}_h(\mu ^*_T - \pi ) = {\mathcal {O}}\left( T^{-\frac{m}{m(d+1)-1}} \right)$.

Proof

Let us consider a function $u: [0,1] \rightarrow {\mathbb {R}}$ such that:

• The m-th derivative is bounded by $\alpha _m$; that is, $\left||u^{(m)} \right||_{\infty } \le \alpha _m$.

• For all integers $i \in \{1, \ldots ,m-1\}$, endpoint values are zero; that is, $u^{(i)}(0) = u^{(i)}(1) = 0$.

• Start point is zero; that is, $u(0) = 0$.

• Endpoint is positive; that is, $u(1) = C > 0$.

Let x and y in $\Omega$, such that $\Vert x-y\Vert _2 = C r^m$, and let $\tau _{xy}$ be the unit vector from x to y. Then, for r small enough, the function $s[x,y]: t \mapsto x + \tau _{xy} u(\frac{t}{r})$ belongs to ${\mathcal {P}}_T^{m,\infty }$, with all its first $(m-1)$ derivatives zero at its endpoints. The condition r small enough is for controlling the norm of the i-th derivatives for $i \le m-1$, which scale as $r^{m-i}$.

Now, let us split $\Omega = [0,1]^d$ into $N^d$ small cubes $\omega _i$. We may order them such that each $\omega _i$ is adjacent to the next cube $\omega _{i+1}$. We write $x_{i}$ for the center of $\omega _i$. We now build functions $s \in {\mathcal {P}}_T^{m,\infty }$ by concatenating paths from $x_i$ to $x_{i+1}$ and waiting times in $x_i$:

$$\begin{aligned}&0 = t_1^1 \le \cdots \le t_{i-1}^2 \le t_i^1 \le t_i^2 \le t_{i+1}^1 \le \cdots \le t_{N^d}^2 = T, \\&t_i^2 - t_i^1 = \left( \frac{1}{NC}\right) ^{\frac{1}{m} }, \\&s(t) = \left\{ \begin{array}{ll} x_i &{} \qquad \text {if}\quad t_i^1 \le t \le t_i^2, \\ s[x_i,x_{i+1}](t - t_i^2) &{} \qquad \text {if}\quad t_i^2 \le t \le t_{i+1}^1, \\ \end{array} \right. \end{aligned}$$

under the condition $T \ge T_N :=(N^d - 1) \left( \frac{1}{NC}\right) ^{\frac{1}{m} }$, that is to say that we have enough time to loop through all the cube centers.

Now let $\pi \in {\mathcal {M}} _{\Delta }$. We may choose $t_i^2 - t_i^1 \le T\pi (\omega _i)$ for all i. Then, we may couple $\pi$ and $s_* \gamma _T$ with $c(x_i, \omega _i) = \frac{t_i^2 - t_i^1}{T}$. Since the small cubes have radius $\sqrt{d}/N$ and the big one has radius $\sqrt{d}$, we obtain

$$\begin{aligned} W_1 (\pi , s_{*} \gamma _T)&\le \frac{\sqrt{d}}{2N} \sum _i \frac{t_i^2 - t_i^1}{T} + \sqrt{d} \sum _{i < N^d} \frac{t_{i+1}^1 - t_i^2}{T} \\&= \frac{\sqrt{d}}{2N} \frac{T - T_N}{T} + \sqrt{d} \frac{T_N}{T}. \end{aligned}$$

In particular, taking $N = T^{\frac{m}{m(d+1) - 1} }$, we find that $W_1\left( {\mathcal {M}}\left( {\mathcal {P}}_T^{m, \infty }\right) , \pi \right) = O \left( T^{- \frac{m}{m(d+1) - 1} } \right)$; hence $\bigcup _T {\mathcal {M}}\left( {\mathcal {P}}_T^{m, \infty }\right)$ is weakly dense in ${\mathcal {M}}_\Delta$. $\square$

5.3 Numerical Resolution

We now turn to the numerical resolution of problem (26). We first discretize the problem. We set $\Delta t:= \frac{T}{N}$ and define discrete curves s as vectors of ${\mathbb {R}}^{N\cdot d}$. We let $s(i)\in {\mathbb {R}}^d$ denote the curve location at discrete time i, corresponding to the continuous time $i\Delta t$.

We define $D_1:{\mathbb {R}}^{N\cdot d} \rightarrow {\mathbb {R}}^{N\cdot d}$, the discrete first-order derivative operator, as follows:

$$\begin{aligned} (D_1 s) (i) =&\frac{1}{\Delta t}\left\{ \begin{array}{ll} 0&{} \text{ if } i=1, \\ s(i)-s(i-1) &{} \text{ if } i\in \{2, \ldots , N\}. \\ \end{array} \right. \end{aligned}$$

In what follows, $D_i$ denotes a discretization of the derivative operator of order i. In the numerical experiments, we set $D_2=-D_1^*D_1$.

We define $P_N^{m,q}$, a discretized version of ${\mathcal {P}}_T^{m,q}$, as follows:

$$\begin{aligned} P_N^{m,q}=\big \{s \in {\mathbb {R}}^{N\cdot d}, \text{ such } \text{ that } \forall i\in \{1,\ldots N\},\ s(i) \in \Omega , \end{aligned}$$

(27)

$$\begin{aligned} \text{ and } \forall j\in \{1, \ldots , m \}, \ \Vert D_j s \Vert _q \leqslant \alpha _j \big \}. \end{aligned}$$

(28)

Here, $\Vert \cdot \Vert _q$ is defined by: $\displaystyle \Vert x\Vert _q=\left( \sum _{i=1}^{N\cdot d}\Vert x_i\Vert _2^q\right) ^{\frac{1}{q}}$ for $q\in [1,+\infty )$ and $\displaystyle \Vert x\Vert _\infty =\max _{1\leqslant i\leqslant N\cdot d} \Vert x_i\Vert _2$.

The measures set ${\mathcal {M}}({\mathcal {P}}_T^{m,q})$ can be approximated by the set of N-point measures ${\mathcal {M}}(P_N^{m,q})$. From Corollary 3, it suffices to control the Hausdorff distance ${\mathcal {H}}_{W_1}({\mathcal {M}}({\mathcal {P}}_T^{m,q}), {\mathcal {M}}(P_N^{m,q}))$, to ensure that the solution of the discrete problem (6) with ${\mathcal {M}}_N={\mathcal {M}}(P_N^{m,q})$ is a good approximation of problem (26). Unfortunately, the control of this distance is rather technical and falls beyond the scope of this paper for general m and q. In the following proposition, we therefore limit ourselves to the case $m=1, q=\infty$.

Proposition 10

${\mathcal {H}}_{W_1}({\mathcal {M}}({\mathcal {P}}_T^{1,\infty }), {\mathcal {M}}(P_N^{1,\infty })) \leqslant \alpha _1\frac{T}{N}$.

Proof

• 1. Let us show that $\displaystyle \sup _{\mu \in {\mathcal {M}}({\mathcal {P}}_T^{1,\infty })} \inf _{\tilde{\mu }\in {\mathcal {M}}(P_N^{1,\infty })} W_1(\mu , \tilde{\mu }) \leqslant \frac{\alpha _1 T}{N}$.

  Let $\mu \in {\mathcal {M}}({\mathcal {P}}_T^{1,\infty })$, and denote by $p \in {\mathcal {P}}_T^{1,\infty }$ a parameterization such that $\mu =p_* \gamma$. Define $\displaystyle \tilde{\mu }=\frac{1}{N} \sum _{i=0}^{N-1} \delta _{p\left( \frac{i T}{N}\right) }$. Then a parameterization of $\tilde{\mu }$ is defined by $s(i)=p\left( \frac{iT}{N}\right)$. Moreover, for $i\in \{2, \ldots N\}$, $\displaystyle |(D_1 s)(i)|=\frac{1}{\Delta t}\left| p\left( \frac{iT}{N}\right) -p\left( \frac{(i-1)T}{N}\right) \right| = \frac{1}{\Delta t}\left| \int _{\frac{(i-1)T}{N}}^{\frac{iT}{N}}\dot{p}(t)\,\hbox {d}t\right| \leqslant \frac{1}{\Delta t}\int _{\frac{(i-1)T}{N}}^{\frac{iT}{N}}|\dot{p}(t)|\,\hbox {d}t \leqslant \alpha _1$. Therefore $s\in P_N^{1,\infty }$.

  Let us consider the transportation map coupling the curve arcs between times $(i-1)\frac{T}{N}$ and $i\frac{T}{N}$ and the Diracs at $p\left( i\frac{T}{N}\right)$. Then $\displaystyle W_1(p_*\gamma ,s_*\gamma )\leqslant \sum _{i=1}^N \frac{1}{N} \sup _{(i-1)\frac{T}{N} \leqslant t \leqslant i\frac{T}{N}}\left\| s(t)-s\left( (i-1)\frac{T}{N}\right) \right\| \leqslant \alpha _1 \frac{T}{N}$.

• 2. Let us fix $\mu \in {\mathcal {M}}\left( P_N^{1,\infty }\right)$, and let $s\in P_N^{1,\infty }$ such that $s_*\gamma = \mu$. We set $p(0)=s(1)$, and

  

  Since $s \in \Omega ^N$ and $\Omega$ is convex, $p([0,T])\subset \Omega$. Moreover, p is continuous and piecewise differentiable. Finally, for $i\in \{1,\ldots , N-1\}$ and $t\in \big ]\frac{iT}{N}, \frac{(i+1)T}{N}\big ]$, $\dot{p}(t)=\frac{1}{\Delta t}\left( s(i+1)-s(i)\right) =D_1(s)(i)$. Therefore, $\Vert \dot{p}\Vert _\infty \leqslant \alpha _1$, ensuring that $p \in {\mathcal {P}}_T^{1,\infty }$. With the same coupling as above, we have $W_1(p_*\gamma ,s_*\gamma )\leqslant \alpha _1 \frac{T}{N}$, which ends the proof.

$\square$

To end up, let us describe precisely a solver for the following variational problem:

$$\begin{aligned} \inf _{\mu \in {\mathcal {M}}\left( {\mathcal {P}}_T^{1,\infty } \right) } {\mathcal {N}}_h(\mu -\pi ). \end{aligned}$$

(29)

We let ${\mathcal {M}}^*$ denote the set of minimizers and ${\mathcal {P}}^*$ denote the associated set of parameterizations.

Remark 5

The implementation of Algorithm 1 requires computing the gradients (20) and (21) and computing a projection on $P_N^{1,\infty }$. Both problems are actually nontrivial.

Fig. 3

Projection of the lion image onto $P_N^{1,\infty }$ with $N=8000$. The figure depicts $s^{(k)}$ with several values of the iterate k in Algorithm 1

Fig. 4

Decay of the cost function J for the three experiments depicted in Fig. 3. We represent $\log _{10}(J(k)-m)$ for $k\le 400$, where m is the mimimal value of J during the first 30,000 iterations

Fig. 5

Projection of Meisje met de Parel, Vermeer 1665, onto $P_N^{1,\infty }$ with $N=150,000$. The figure depicts $s^{(10,000)}$ obtained with Algorithm 1

Fig. 6

Projection of the lion image onto $P_N^{m,q}$ with $N=8000$, $m\in \{1,2\}$, and $q\in \{1,2,\infty \}$

Fig. 7

Projection of Marylin image, onto the set: $\displaystyle {\mathcal {C}}=\{ p\in (W^{2,\infty }([0,T]))^2, \sup _{i\in [1,N]}\left( \Vert D_1 p(i)\Vert _2 \right) \le \alpha _1, \sup _{i\in [1,N]}\left( \Vert D_2 p(i)\Vert _2 \right) \le \alpha _2\}$, with $N=100,000$. The figure depicts $s^{(10,000)}$ obtained with Algorithm 1

The naive approach to compute the gradient of F consists in using the explicit formula (20). This approach is feasible only for a small amount of points N (less than 1000) since its complexity is ${\mathcal {O}} \left( N^2\right)$. In our numerical experiments, we therefore resort to fast summation algorithms [17, 25] commonly used in particles simulation. This part of the numerical analysis is described in [28], and we do not discuss it in this paper.

The set $P_N^{1,\infty }$ and more generally the sets $P_N^{m,q}$ are convex for $q\in [1,\infty ]$. Projections can be computed using first-order iterative algorithms for convex functions. In our numerical experiments, we use accelerated proximal gradient descents on the dual problem [3, 23, 31]. A precise description is given in [7].

6 Results

To illustrate the results, we focus on the continuous line drawing problem discussed throughout the paper. It is performed using Algorithm 1. In the following experiments, we set H as a smoothed $L^1$-norm. This is similar to what was proposed in the original halftoning papers in [26, 28].

We first concentrate on the projection onto $P_N^{1,\infty }$. In Fig. 3, we show the evolution of the curve $s^{(k)}$ across iterations, for different choices of $s^{(0)}$. After 30,000 iterations, the evolution seems to be stabilized. The cost function during the 400 first iterations is depicted in Fig. 4 for the three different initializations. As can be seen, the curve evolves toward a satisfactory representation of the lion, whatever the initialization. This is a very nice feature that is somehow surprising since our algorithm simply consists of minimizing a highly nonconvex function with a first-order method.

In Fig. 5, we show the projection onto $P_N^{1,\infty }$ of the famous Meisje met de Parel painting (Girl with a Pearl Earring), after 10,000 iterations. To really see the precision of the algorithm, we advise the reader to blink the eyes or to take a printed version of the paper away. From a close distance, the curves or points are visible. From a long distance, only the painting appears.

To finish, we consider projections onto more general measure spaces, such as ${\mathcal {M}}\left( {\mathcal {P}}_T^{m,q}\right)$. In Fig. 6, we show different behaviors for different $m\in \{1,2\}$ and $q\in \{1,2,\infty \}$. We also show a large-scale example with a picture of Marylin Monroe in Fig. 7.

7 Conclusion

We analyzed the basic properties of a variational problem to project a target Radon measure $\pi$ on arbitrary measures sets ${\mathcal {M}}_N$. We then proposed a numerical algorithm to find approximate solutions of this problem and gave several guarantees. An important application covered by this algorithm is the projection on the set of N-point measures, which is often called quantization and appears in many different areas such as finance, imaging, biology, etc. To the best of our knowledge, the extension to arbitrary measures set is new and opens many interesting application perspectives. As examples in imaging, let us mention open topics such as the detection of singularities [2] (e.g., curves in 3D images) and sparse spike deconvolution in dimension d [9].

To finish, let us mention an important open question. We provided necessary and sufficient conditions on the sequence $({\mathcal {M}}_N)_{N\in {\mathbb {N}}}$ for the sequence of global minimizers $(\mu ^*_N)_{N\in {\mathbb {N}}}$ to weakly converge to $\pi$. In practice, finding the global minimizer is impossible, and we can only expect to find critical points. One may therefore wonder whether all sequences of critical points weakly converge to $\pi$. An interesting perspective to answer this question is the use of mean-field limits [10].