Vincent Jaouen

Julien Bert

Nicolas Boussion

Hadi Fayad

Mathieu Hatt

Senior Member, IEEE Dimitris Visvikis

Image enhancement with PDEs and nonconservative advection flow fields

Keywords: Image enhancement, Image sharpening, Denoising, Partial differential equations, Shock filter, Anisotropic diffusion

We propose a new method for the progressive enhancement of images degraded by noise and blur using shock filters. The originality of our approach lies in the iterative exploitation of nonconservative edge based force fields normally designed for segmentation to determine both locations and amplitudes of the sharpening action. The proposed Nonconservative Shock Filter (NCSF) produces images with strong discontinuities that can be used as an additional pre-processing step to facilitate higher level tasks such as edge detection or segmentation. NCSF is especially useful when coupled with an anisotropic diffusion equation in noisy configurations. Using the proposed method, edges that are not well defined prior to filtering can be iteratively recovered. We show processing results on various types of images, focusing on medical transrectal ultrasound and brain PET imaging.

I. INTRODUCTION

I NITIATED by the non-local means algorithm [1], image denoising techniques aiming at solving the known additive white Gaussian noise (AWGN) model have improved considerably over the past decade, mainly thanks to patch-based approaches. State-of-the-art techniques include block matching and 3D filtering (BM3D) and its variants [START_REF] Dabov | Image denoising by sparse 3-D transform-domain collaborative filtering[END_REF], [START_REF]BM3D image denoising with shape-adaptive principal component analysis[END_REF], spatially adaptive iterative singular-value thresholding (SAIST) [START_REF] Dong | Nonlocal image restoration with bilateral variance estimation: A low-rank approach[END_REF], Non-Local Bayes [START_REF] Lebrun | A nonlocal bayesian image denoising algorithm[END_REF], or online dictionary learning using patches [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] or patch groups [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF]. It was recently suggested that modern approaches could be close to reaching a theoretical limit in terms of minimization of the mean square error (MSE) [START_REF] Levin | Natural image denoising: Optimality and inherent bounds[END_REF], [START_REF] Chatterjee | Is denoising dead?[END_REF], to the point that a recent publication claims that "to a large extent, removal of zero-mean white additive Gaussian noise from an image is a solved problem in image processing" [START_REF] Romano | The little engine that could: Regularization by denoising (red)[END_REF].

This statement however concerns natural photographic images with high levels of details, at which are devoted most efforts in the image processing community. Other types of images such as medical images, which typically present less details and more noise, are likely to have more room for improvement towards these theoretical bounds [START_REF] Chatterjee | Is denoising dead?[END_REF]. Moreover, alongside noise, medical images are often affected by additional distortions. These include blur, insufficient contrast between regions of interest or artifacts that further complicate higher level processing tasks such as edge detection or segmentation. In these cases, noise suppression is not sufficient and application-specific image alteration is needed. One rather use in this context the concept of image enhancement [START_REF] Gonzalez | Digital Image Processing[END_REF], which can be considered as an intermediate processing level between denoising (where mild modification of the original image occurs), and segmentation (where image regions are fully abstracted into independent objects). Among various application contexts, image enhancement may be required in medical images where objects of interest (organs, tumors...) are large compared to the field of view and in which smaller details are artificial or irrelevant for the task at hand. For example, appropriate pre-processing techniques that render macroscopic features more visible may be of practical interest for facilitating user guided image analysis tasks and automated segmentation or co-registration between different imaging modalities. The appropriateness of an enhancement method is entirely dependent on the targeted application, and the ultimate judge of the performance of an enhancement technique is often the user [START_REF] Gonzalez | Digital Image Processing[END_REF]. This is in contrast to the restoration of images corrupted by a known degradation model, where methods can be validated using full-reference image quality metrics based on distances to clean images, such as signal-to-noise ratio (SNR) or structural similarity [START_REF] Zhang | Adaptive bilateral filter for sharpness enhancement and noise removal[END_REF].

In this paper, we focus on the common requirement of sharpening image edges while smearing out noise and irrelevant details. We propose a new partial differential equation (PDE)-based filtering formulation by coupling a nonlinear diffusion term and a new regularized shock filter term. By exploiting nonconservative edge flow fields normally designed for active contour segmentation, we iteratively estimate the locations of shocks, that can yield improved sharpening effects. Following a recent work [START_REF] Prada | Unconditionally stable shock filters for image and geometry processing[END_REF], we also reformulate the action of shock filtering as an advection process of the image intensities embedded in external vector fields, allowing for fast approximations of the proposed scheme.

Images obtained after processing with the proposed method compare favorably to state of the art approaches according to both subjective evaluation and quantitative evaluation metrics. In the present case, we focus on edge detection, image sharpness, and segmentation accuracy with application to transrectal medical ultrasound (TRUS) images, as well as the improvement of partial volume corrected positron emission tomography (PET) brain images.

The rest of the article is organized as follows. In the next section, we present current PDE-based approaches for image enhancement and their limitations. Section III describes the proposed shock filter based on nonconservative fields. The validation setup used in our experiments in described in section IV. Results are presented in section V. Finally, conclusions are drawn in section VI.

II. BACKGROUND

In this section, we briefly discuss partial differential equations in image processing and describe related PDE-based enhancement approaches using shock filters.

A. Partial differential equations in image processing

Unlike patch-based approaches that rely on self-similarities of local patches across the image domain, pixel-based regularizers such as Tikhonov [START_REF] Vogel | Computational methods for inverse problems[END_REF], Mumford-Shah [START_REF] Mumford | Optimal approximations by piecewise smooth functions and associated variational problems[END_REF] or total variation (TV) regularization methods [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] rely on the hypothesis that images obey to global generic priors, such as piecewise constancy or piecewise linearity. These priors are often expressed under the variational framework, where the solution image corresponds to the minimization of an energy integrated across the image domain [START_REF] Chan | Image processing and analysis: variational, PDE, wavelet, and stochastic methods[END_REF].

Most developments in image regularization were made during the 1990s using regularizing PDEs, where image evolution towards a solution is understood as an iterative gradient descent scheme for solving the Euler-Lagrange equation associated with the corresponding variational problem [START_REF] Weickert | Anisotropic diffusion in image processing[END_REF], [START_REF] You | Behavioral analysis of anisotropic diffusion in image processing[END_REF]. Since the seminal work on anisotropic diffusion [START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF], PDE schemes have become a field on their own, and many proposed regularizing PDEs do not necessarily derive from a variational formulation. Under the framework of PDEs, various terms can be combined to obtain different and simultaneous desired effects for the targeted application. Due to this modular nature, they can lead to a wide variety of outputs, ranging from low-level denoising to super-resolution or image segmentation, and are well-adapted to image enhancement [START_REF] Tschumperle | Diffusion PDEs on vector-valued images[END_REF], [START_REF] Nadernejad | PDEs-based method for image enhancement[END_REF]. Such schemes allow equally for an easy extension to vector-valued images like color or multimodal images [START_REF] Tschumperle | Vector-valued image regularization with PDEs: A common framework for different applications[END_REF]- [START_REF] Jaouen | 4DGVFbased filtering of vector-valued images[END_REF]. For these reasons, while PDEs are generally considered less effective than patch-based approaches for natural image denoising due to their general tendency to smear out image details [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF], they are still popular for medical imaging applications [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF]- [START_REF] Ramos-Llordén | Anisotropic diffusion filter with memory based on speckle statistics for ultrasound images[END_REF].

B. Shock filter

A popular edge sharpening scheme using PDEs is the shock filter (SF), a nonlinear hyperbolic operator that restores shocklike patterns (i.e. sharp discontinuities) in blurred signals. Its general PDE formulation is :

I t = -S (L(I)) ∇I s.t. I 0 = I, (1)
where subscript • t denotes partial derivative with respect to Euler time t, L(I) is a signed edge indicator function and S is a sign-preserving function of this edge response. In the original formulation of the SF [START_REF] Osher | Feature-oriented image enhancement using shock filters[END_REF], S(x) = sign(x) and L = I ηη , where η is the direction of the image gradient, so that shocks are recovered around the zero-crossings of the second directional derivative along the gradient direction. This scheme is extremely unstable due to the sensitivity of the second derivative to noise. For this reason, a PDE scheme in which a Gaussian regularized SF term is coupled to mean curvature flow was previously proposed [START_REF] Alvarez | Signal and image restoration using shock filters and anisotropic diffusion[END_REF] :

I t = -S(G σ * I ηη ) ∇I + cI ξξ s.t. I 0 = I, ( 2
)
where ξ is the direction perpendicular to the gradient direction η (isophote direction), G σ is a Gaussian kernel of scale σ and * is the convolution operation. A SF term was incorporated [START_REF] Gilboa | Regularized shock filters and complex diffusion[END_REF] in the complex diffusion framework [START_REF] Gilboa | Image enhancement and denoising by complex diffusion processes[END_REF] to regularize the solution without making use of Gaussian convolution and allowing for a progressive increase of the sharpening effect along with diffusion time. The sign preserving function S(x) = sign(x) was also replaced by a softer version S(x) = 2 arctan(ax)/π to favour sharpening near edges in a nonlinear fashion controlled by parameter a. The use of the tanh function [START_REF] Xiao | Adaptive shock filter for image super-resolution and enhancement[END_REF] or fuzzy memberships functions [START_REF] Duan | A Novel Framework for Shock Filter Using Partial Differential Equations[END_REF] were also proposed in recent papers.

Recently, an unconditionnally stable approximation of the SF was proposed [START_REF] Prada | Unconditionally stable shock filters for image and geometry processing[END_REF] following the observation that its action can be rewritten as the advection of the image intensity values along the flow lines of the (irrotational) vector field:

u = 1 2 ∇ ∇I 2 . (3)
In the context of fast processing of surface meshes, this new formulation is used to approximate the shock filter for any Euler time t by back-tracing image values along the flow lines of u. Despite providing improved performance in noisy configurations over the original SF formulation, all of these methods use regularized versions of the image second derivative as the signed edge response. In this context, robustness to noise can only be improved through increased smoothing, e.g. by using larger values of scale σ in eq. ( 2) or by smoothing the advection field in eq. ( 3) [START_REF] Prada | Unconditionally stable shock filters for image and geometry processing[END_REF]. Such smoothing can only be performed at the expense of smearing out weak edges in the image, which is not desirable, especially in medical images.

C. Relationship with active-contour external forces

The vector field u of eq. ( 3) is, up to a factor 1/2, the gradient of the scalar edge map ∇I 2 . This is the classical conservative (i.e. irrotational) edge-based force-field (EBF) used for active contour segmentation [START_REF] Kass | Snakes: Active contour models[END_REF]. This observation is of interest as it allows for a natural connection between shock filtering and the vast amount of work made on EBF in the active contours literature [START_REF] Xu | Snakes, shapes, and gradient vector flow[END_REF]- [START_REF] Ghosh | A nonconservative flow field for robust variational image segmentation[END_REF]. Considerable progress in active contour segmentation were indeed made by overcoming the drawbacks of conservative forces such as eq. (3) with nonconservative alternatives, i.e. forces that cannot be expressed as gradients of a scalar potential. For example, the popular Gradient Vector Flow (GVF) method was proposed to increase robustness to noise, provide better capture range and allow active contours to progress into narrow concavities formed by objects in the image. Other similar approaches include the Generalized GVF (GGVF, [START_REF]Generalized gradient vector flow external forces for active contours[END_REF]) and the Vector Field Convolution (VFC). One of the most desirable properties shared by these new flow fields is their ability to preserve perceptual boundaries of the objects, i.e. gaps in the image that are connected visually by the human visual system [START_REF] Xu | Snakes, shapes, and gradient vector flow[END_REF], [START_REF]Generalized gradient vector flow external forces for active contours[END_REF]. This can be exploited for better restoration of weak or invisible edges when applied to image enhancement with shock filters.

In the following, we propose a PDE framework for image enhancement using SF based on nonconservative edge-based force fields. Our contribution is threefold. First, the proposed Nonconservative Shock Filter scheme (NCSF) takes advantage of the recalculation of edge-based forces along the iterative process to better identify locations of shocks, yielding stable and accurate image sharpening enhancement. Secondly, we reformulate NCSF as an advection process, extending a recent work [START_REF] Prada | Unconditionally stable shock filters for image and geometry processing[END_REF] to the nonconservative case and thereby enabling efficient schemes for single-channel and vector-valued image enhancement. Finally, we propose to couple the NCSF effect to anisotropic diffusion for the simultaneous denoising and sharpening of highly degraded images.

We note that the use of GVF fields as edge indicator function for shock filtering was proposed by earlier [START_REF] Yu | GVF-based anisotropic diffusion models[END_REF]. A similar idea was proposed for the suppression of mixed noise by coupling GVF-based shock filtering with a median filter [START_REF] Ghita | A new GVF-based image enhancement formulation for use in the presence of mixed noise[END_REF]. A coupled anisotropic diffusion and shock filter scheme for the restoration of vector-valued images was also proposed recently [START_REF] Jaouen | 4DGVFbased filtering of vector-valued images[END_REF] using generalizations of GVF to the multi-channel case [START_REF] Jaouen | Variational segmentation of vector-valued images with gradient vector flow[END_REF]. However, in all these works, the field is computed prior to filtering and is not part of the filtering process, acting as a static vectorial edge map. This may be not optimal in noisy configurations where edges are ill-defined. Moreover, the relationship between advection and shock filtering is not taken into consideration.

In the next section, we describe the proposed NCSF scheme and show how a regularization method can take advantage of a dynamic use of edge flow fields along the iterative process to improve filtering results for noisy configurations.

III. PROPOSED METHOD

A. Dynamic Nonconservative Shock Filtering (NCSF)

We describe our iterative PDE scheme for image sharpening with shock filters based on nonconservative edge-based force (EBF) fields. Let I(x) : x ∈ R n → R be a n-dimensional image defined on a discrete grid x of the image domain. Let F t (x) be an EBF field computed dynamically at each Euler time step t of the iterative process and oriented toward edges. F t is normalized such that all vectors have unit norm. The general formulation of the proposed shock filter is:

I t (x) = -P(x) ∇I s.t. I 0 = I, (4)
where P(x) = F t (x), ∇I(x) is the scalar projection of F t onto the unit gradient vector ∇I = ∇I/ ∇I of direction η, and •, • is the dot product. Fig. 1 illustrates the action of the proposed shock filter on a sigmoidal signal in the 1D case. The EBF field is oriented toward the inflection point (i.e. edge in 2D/3D images). A step signal is iteratively recovered by increasing or decreasing the signal intensity with strength |P(x)| × ∇I dt, where dt is the Euler time step. This formulation differs from previous GVF-based shock filtering developments [START_REF] Yu | GVF-based anisotropic diffusion models[END_REF], where the sign of the projection P is used only as a replacement for the sign of the second derivative to increase or decrease signal values around the inflection point [START_REF] Yu | GVF-based anisotropic diffusion models[END_REF]. Shocks are here recovered proportionally to the degree of colinearity between the gradient direction and the EBF field. This ensures that well-defined edges, identified by the co-alignment of gradient and EBF, are enhanced with more strength. Moreover, the field is dynamically recomputed at each Euler time t, so that the estimation of the edge location is refined along the iterative process. This last property is especially useful when SF is coupled to a denoising scheme, as discussed in section III-B.

The proposed scheme implies that the EBF field F t is recomputed at each Euler step. For this reason, the use of computationally expensive flow fields such as GVF is impractical. Instead, in this work, we use Vector Field Convolution (VFC) EBF fields [START_REF] Li | Active contour external force using vector field convolution for image segmentation[END_REF]. VFC vector fields are similar to those produced with GVF, however their computation is much faster, requiring only n convolutions in n-dimensional images, which make them well adapted to the proposed iterative approach. We briefly recall here their formulation. A VFC field is obtained by convolving a scalar edge map f t of image I at Euler time t with a Vector Field Kernel (VFK):

F t = f t * K, ( 5
)
where K is the VFK, a vector kernel whose vectors point toward its center r 0 with decreasing magnitude m(r) = r -γ as a function of the distance r to r 0 . In this work, we set f t as the squared Euclidean norm of the gradient

f t = ∇I 2 .
The VFK shape is controlled by two parameters : kernel radius s and vector attenuation parameter γ. Fig. 2 shows two example VFK of size s = 5 with γ = 2.2 and γ = 2.8. The kernel shape is crucial to the filtering output, as it rules the detection of weak edges in the image. Using low values of γ increases robustness to noise, at the expense of smearing out weak edges which are then lost for recovery. Conversely, strong values of γ must be used to recover weak edges, at the expense of higher sensitivity to noise [START_REF] Li | Active contour external force using vector field convolution for image segmentation[END_REF]. This is the classical conflict between edge detection and robustness to High values of γ increase sensitivity to local weak edges but also yield more sensitivity to isolated noise noise, which are contradictory by nature [START_REF] Acton | Piecewise and local image models for regularized image restoration using cross-validation[END_REF]. This problem can be alleviated using approaches that combine both edge sharpening and denoising, which is the object of the next section.

B. Regularized NCSF for noisy images (NCRSF)

Under eq. ( 4), the SF acts throughout the image domain anywhere the gradient is non-zero. This includes noisy flat regions where, in principle, no sharpening should occur. It is however generally preferable to sharpen only edges while removing noise in homogeneous regions. This can be done by coupling SF to anisotropic diffusion, as originally proposed by Alvarez and Mazorra [START_REF] Alvarez | Signal and image restoration using shock filters and anisotropic diffusion[END_REF]. To this end, we couple the proposed EBFbased SF to a denoising approach in an Advection-Diffusion-Reaction (ADR) scheme. We use the oriented laplacians formalism, which decomposes anisotropic diffusion in terms of independent diffusions along the gradient and isophote directions [START_REF] Tschumperle | Vector-valued image regularization with PDEs: A common framework for different applications[END_REF].

In n-dimensional images, let η be the gradient direction and ξ i , i = (2, ..., n) be the orthogonal directions to η that span the hyperplane tangent to the local isophote. The proposed coupled ADR scheme for simultaneous denoising and sharpening of noisy images (NCRSF for Non-Conservative Regularized Shock Filter) is expressed as:

I t = c η (N )I ηη + n i=2 c ξ (N )I ξiξi + λ I 0 -I -P(x) I η . ( 6
)
The first two terms in equation ( 6) respectively correspond to the nonlinear diffusion of image intensities along the gradient and isophote directions, weighted by diffusion coefficients c η and c ξ , two decreasing functions of a scalar edge detector N (x) [START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF]. The third term is a reaction term [START_REF] Kornprobst | Image coupling, restoration and enhancement via PDE's[END_REF], controlled by parameter λ, that helps preventing the solution from diverging too far from the initial image I 0 . The last term is the proposed EBF-based SF term. In singlechannel images, I η = ∇I .

In the proposed approach, the recalculation of the vector field F t at each time step enables to enhance edge detection along the process. This property is especially useful in noisy configurations where the initial edge-based field is ill-defined. The use of a static field has been considered as an advantage because it provides numerical stability [START_REF] Yu | GVF-based anisotropic diffusion models[END_REF]. However, it also limitates the edge detection task to the accuracy of the static initial field, which can lead to erroneous sharpening of flat regions.

To illustrate the action of the proposed coupled ADR scheme, Fig. 3 shows a 100×100 grayscale image representing 4 disks of variable contrast (Fig. 3a) blurred with a Gaussian filter of scale σ b = 3 pixels and corrupted with additive white Gaussian noise (AWGN) of standard deviation σ = 10 (Fig. 3b). The second row compares the EBF field computed on the noisy image and the one obtained with the proposed scheme after 150 iterations. The advantage of recomputing the field is emphasized on the lower contrast disks for which the gradient signal is weak. Because initial EBF vectors are almost random (Fig. 3c), enhancement approaches that rely on this noisy information [START_REF] Yu | GVF-based anisotropic diffusion models[END_REF] would perform poorly. On the contrary, the recalculation of the field using the proposed scheme produced more coherent orientations of the EBF vectors for all four disks (Fig. 3d). This can be assessed quantitatively by comparing the angular difference between EBF vectors obtained on the noise-free image and the ones obtained after processing. We define the pixelwise angular error D of an EBF vector F to some reference ground-truth EBF field F 0 as:

D(F 0 , F ) := cos -1 F 0 , F F 0 F . (7)
By analogy with a metric proposed for color constancy assessment [START_REF] Hordley | Re-evaluating colour constancy algorithms[END_REF], we define an estimator of EBF field quality as the median value of the angular error distribution. We call this full-reference measure median angular error (MAE). field on the less noisy processed image. Thanks to the use of VFC, the computational overload of such recalculation is moderate. As an example, in this image, 150 iterations of a finite-difference scheme implementation of the approach take 0.32s, against 0.21s without recalculation of the field on a 3 GHz Intel i7 processor.

C. Extension to vector-valued images

Vector-valued (VV) images such as color, multispectral or hyperspectral images can be enhanced with the proposed scheme by processing each of their channel independently, i.e. using a marginal approach. However, it is generally preferable to couple channel evolution, e.g. to reduce the production of false colors in color images, due to unbalanced enhancement between channels [START_REF] Tschumperle | Vector-valued image regularization with PDEs: A common framework for different applications[END_REF], [START_REF] Brox | Nonlinear structure tensors[END_REF]. In the VV case, the gradient direction η and its corresponding amplitude I η are not well defined. Simple averaging of the gradient in the channels is not satisfying, as opposite gradient directions in two channels would cancel each other without meaning [START_REF] Brox | Nonlinear structure tensors[END_REF].

To avoid this effect, the multi-channel case is handled using the local structure tensor (ST) formalism [START_REF] Zenzo | A note on the gradient of a multi-image[END_REF]. The ST, also known as the second-order moment matrix, or Di Zenzo matrix is a symmetric and positive semidefinite n-by-n matrix. For p-channel images, it is expressed as the sum of the covariance matrices of the gradient in the different channels :

J ρ = G ρ * p k=1 ∇I k (∇I k ) T , (8)
where I k denotes the k-th channel of I, • T is the transposition operator and G ρ is a regularizing Gaussian kernel of scale ρ. We follow Di Zenzo's analysis [START_REF] Zenzo | A note on the gradient of a multi-image[END_REF], where the gradient of a VV image, or vector gradient, is obtained from the eigendecomposition of the ST. The vector gradient direction η is the direction of the eigenvector associated with the principal eigenvalue, while the remaining eigenvectors (ξ 2 , ..., ξ n ) span the hyperplane tangent to the local isophote.

The vector gradient magnitude is obtained by combining the eigenvalues of the ST [START_REF] Weickert | Anisotropic diffusion in image processing[END_REF]. In this work, we use the trace of the tensor as an edge detector as proposed in previous works for color image enhancement [START_REF] Tschumperle | Diffusion PDEs on vector-valued images[END_REF] :

N V = Tr(J ρ ) (9)
We obtain a VFC field for VV images F V by convolving the squared contrast N 2

V with a vector field kernel, as proposed in the context of image segmentation [START_REF] Jaouen | Vector-based active surfaces for segmentation of dynamic PET images[END_REF]. Similarly to the scalar case, the proposed ADR scheme is achieved by coupling the evolution of each channel I k under:

I k t =c η (N V )I k ηη + n i=2 c ξ (N V )I k ξiξi + λ I k 0 -I k -P V (x) I k η , (10)
where P V is the projection of F t V onto the unit vector gradient direction η:

P V = F t V , I k η / I k η . (11)

D. Relationship with advection

As noted recently by Prada and Kazhdan [START_REF] Prada | Unconditionally stable shock filters for image and geometry processing[END_REF], if the signed edge response is L(I) = (∇I) T H∇I

∇I

, where H is the Hessian, the classical shock filter can be expressed as:

I t = - 1 2 ∇ ∇I 2 , ∇I , (12)
which describes the advection of image I along the vector field 1 2 ∇ ∇I 2 . Similarly, we approximate EBF-based shock filtering by advecting the values of I for any Euler time t + dt along the flow lines of the vector field F t . Due to the fact that the EBF field is smooth and well aligned in homogeneous regions, such advection will also lead to the denoising of nonedge pixels. Fig. 6 shows the effect of the proposed advection scheme on the mandrill grayscale image for various time steps dt at fixed Euler time t = 6.4. For all step values, the image was denoised and its edges were sharpened, showing mild increase of the root mean square error (RMSE) for larger steps when compared to the arbitrary reference result obtained with dt = 0.05 .

IV. VALIDATION SETUP

The evaluation of image enhancement is generally subjective or, if used as a pre-processing stage, specific to the task at hand [START_REF] Gonzalez | Digital Image Processing[END_REF]. This is in contrast with image restoration, which can be assessed quantitatively using full-reference image quality metrics such as signal-to-noise ratio (SNR) or root mean square error (RMSE) [START_REF] Zhang | Adaptive bilateral filter for sharpness enhancement and noise removal[END_REF]. Although the maximization of such quantities is not a primary objective, there is in general some overlap between the effects of restoration and enhancement (e.g. both may denoise the image). Full-reference metrics can therefore be used in conjunction with application-specific evaluation to assess the effect of the proposed approach. Provided the targeted application can be evaluated objectively using image quality metrics, the relative improvement of these metrics due to pre-processing can also indirectly assess the interest of the method.

In the next section, we show how our approach can facilitate several tasks such as image restoration, edge detection, image sharpening or segmentation in various imaging contexts. We describe in the following the datasets and the associated quantitative evaluation metrics that we used in our experiments.

We start by studying the effect of the filter on a noisy one-dimensional signal. We then investigate the value of our approach in two different types of medical images. First, we consider the enhancement of TRUS images with the aim of facilitating automatic contour-based prostate segmentation. We then focus on the enhancement of partial volume corrected brain PET images. Although the proposed NCRSF approach is not specifically tailored for image restoration, it can perform satisfyingly in this regard on heavily distorted images. Additional results in the context of natural image restoration using NCRSF on images corrupted by heavy noise and blur can be found in the supplemental material of this article, alongside comparisons with other restoration approaches.

A. One-dimensional case

We studied the simplified and controlled scenario of a one-dimensional sigmoidal signal degraded by heavy additive white Gaussian noise (AWGN). The Matlab code necessary to reproduce the results of this section was released online 1 .

1) Signal description: The studied sigmoid S(t) is expressed as:

S(t) = 1 π arctan 4π t - 1 2 + 1 2 . ( 13
)
An additive white Gaussian noise of variance σ n = 0.4 2 was added to S(t). Our objective was to recover a step signal around the inflection point at t = 1/2. We limited our study to the interval -1 2 , 3 2 , and discretized the signal into 10 3 samples (Fig. 8a).

2) Comparative evaluation: In this 1D example, we compared the proposed NCRSF filter to the Coupled Complex Diffusion and Shock Filtering (CDSF) scheme of Gilboa, Sochen and Zeevi [START_REF] Gilboa | Regularized shock filters and complex diffusion[END_REF]. CDSF is, like NCRSF, a PDE-based approach that couples anisotropic diffusion and regularized shock filter and is arguably the work closest to ours in its formulation. It is based on complex diffusion [START_REF] Gilboa | Image enhancement and denoising by complex diffusion processes[END_REF], where the diffusion in the gradient direction and shock filtering strength are controlled by a time-dependent complex parameter λ. The real part of λ decreases with Euler time in order to progressively reduce diffusion in the gradient direction and increase shock filter strength along iterations. We set the parameters of both CDSF and NCSF models so as to maximize the SNR between the filtered signal and the idealized step edge.

3) Quantitative metrics: We studied three objective quantitative metrics. The SNR with respect to the idealized step signal was used to assess restoration. The maximum gradient amplitude ∇S max was used to evaluate sharpness recovery. Finally, the total variation TV was considered to evaluate the piecewise constantness of the output. The TV is defined as:

TV = 3 2 -1 2 |∂ t S(t)|dt (14)
and is equal to 1 for the true step signal.

1 http://stockage.univ-brest.fr/ ∼ vjaouen/tip2018/ B. Enhancement of TRUS images 1) Dataset description: TRUS imaging is largely employed for the evaluation of prostate diseases and plays an important role in most prostate therapy setups such as high intensity focus therapy or brachytherapy. Although TRUS has many advantages such as real-time capability and low cost, the produced images suffer from important limitations.

Ultrasound images (US) are affected by various degradations including low contrast, blur and speckle noise, making the accurate identification of anatomical structures difficult. To increase SNR, most US-dedicated image filters take into account the multiplicative nature of speckle noise in their formulation [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF]. Similar noise statistics can be found in other domains such as optical coherence tomography or radar imaging, with related efforts to tackle this issue [START_REF] Cheng | Speckle reduction in 3d optical coherence tomography of retina by a-scan reconstruction[END_REF]- [START_REF] Kafieh | Three dimensional data-driven multi scale atomic representation of optical coherence tomography[END_REF]. Speckle noise is however not the only difficulty encountered in TRUS imaging. Depending on probe quality, acquisition parameters and, to a lesser extent, patient anatomy, the gland volume can be difficult to segment automatically. One of the most problematic degradation is the weakness of the prostate boundaries, a problem that cannot be addressed only through denoising (i.e. in the present case, despeckling). For this reason, automatic segmentation of the prostate is a very challenging task even for state of the art techniques [START_REF] Li | Segmentation of prostate from ultrasound images using level sets on active band and intensity variation across edges[END_REF], [START_REF] Jaouen | Prostate Volume Segmentation in TRUS using Hybrid Edge-Bhattacharyya Active Surfaces[END_REF]. The consensus in the prostate segmentation community is therefore that edge information alone is not sufficient to perform accurate prostate segmentation [START_REF] Ghose | A survey of prostate segmentation methodologies in ultrasound, magnetic resonance and computed tomography images[END_REF].

To remain generic and widely applicable, the proposed NCRSF approach is not specifically tailored to address the multiplicative nature of the noise. Nevertheless, we show in the remainder of this section that such a method can be effective for improving prostate segmentation and edge detection in TRUS.

In our experiments, we used a set of 14 images from patients with prostate cancer obtained before undergoing prostate brachytherapy treatment at the Brest University Hospital, Brest, France. For all images, contours of the gland were manually delineated in all slices by an expert radiation oncologist to provide reference results for edge detection and segmentation experiments.

2) Comparative evaluation: PDEs are popular among the ultrasound imaging community for facilitating edge detection and segmentation [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF]. One of the reasons for this popularity is their ability to explicitly adapt the filtering effect to the characteristics of speckle noise. The Speckle Reducing Anisotropic Diffusion (SRAD) [START_REF] Yu | Speckle reducing anisotropic diffusion[END_REF], where the scalar diffusion coefficient is controlled in a nonlinear way by the local coefficient of variation, was proposed to address this issue. This can be considered as the generalization of the isotropic Lee filter to the nonlinear case [START_REF] Lee | Digital image enhancement and noise filtering by use of local statistics[END_REF]. A truly anisotropic variant of SRAD (i.e. not only nonlinear), oriented SRAD (OSRAD) using a matrix-based formulation which decouples diffusion along the gradient and isophote directions was proposed [START_REF] Krissian | Oriented speckle reducing anisotropic diffusion[END_REF]. In a comprehensive comparative study between despeckling filters [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF], OSRAD was shown to perform better than SRAD. Recently, a new matrix-based anisotropic diffusion equation coupled to a delay differential equation [START_REF] Ramos-Llordén | Anisotropic diffusion filter with memory based on speckle statistics for ultrasound images[END_REF] using an adaptive Voltera-type memory mechanism [START_REF] Cottet | A Volterra type model for image processing[END_REF] based on speckle statistics (ADMSS) to better preserve relevant structural information in medical images was proposed, obtaining better results that OSRAD. In our experiments, we compared our NCRSF approach to SRAD and ADMSS using the implementation provided by the authors2 , 3 . While the objective of this section is to compare the effects of local PDE filters, we also include quantitative results obtained using SAR-BM3D4 [START_REF] Parrilli | A nonlocal sar image denoising algorithm based on llmmse wavelet shrinkage[END_REF], a popular adaptation of the BM3D patch-based denoising method [START_REF] Dabov | Image denoising by sparse 3-D transform-domain collaborative filtering[END_REF] to speckle noise that generally performs satisfyingly in speckle ultrasound images [START_REF] Zhang | Comparison of despeckle filters for breast ultrasound images[END_REF].

3) Quantitative metrics: We evaluated the proposed approach using metrics commonly found in ultrasound imaging for image quality assessment [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF]: Pratt's Figure Of Merit (PFOM) [START_REF] Pratt | Digital Signal Processing[END_REF], Structural similarity (SSIM) [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF], Contrastto-noise ratio (CNR), as well as a more recent metric for sharpness assessment, the S 2 sharpness score [START_REF] Vu | S3: A Spectral and Spatial Measure of Local Perceived Sharpness in Natural Images[END_REF].

Given two binary edge maps X and Y , where Y is the ground truth, the PFOM returns a number between 0 and 1 that measures the similarity between edges, both in terms of detection and pixel displacement. It is defined as:

PFOM(X, Y) = 1 max(N X , N Y ) N X i=1 1 1 + αd 2 i , ( 15
)
where N X and N Y are respectively the number of detected and actual edge pixels, d i denotes the distance from the ith-detected edge pixel to the nearest actual edge and α is a scaling constant set to 1/9. Edge maps were obtained by binarizing the gradient magnitude maps above the 95 th percentile, which corresponds to the average percentage of pixels belonging to the prostate boundaries in the ground truth images. While the Canny filter is often used for PFOM [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF], scores were considerably better in our dataset with this simple thresholding, regardless of the method used.

The SSIM measure is defined as:

SSIM(X, Y ) = (2µ 1 µ 2 + C 1 )(2σ 12 + C 2 ) (µ 2 1 + µ 2 2 + C 1 )(σ 2 1 + σ 2 2 + C 2 ) (16)
where µ 1 , µ 2 are local means of reference and test images, σ 1 , σ 2 are the corresponding local standard deviations and σ 12 is the covariance between X and Y . Constants C 1 and C 2 are set as specified in the Matlab r2016a implementation of the metric. As it is often the case for clinical image evaluation, no distortion-free ground truth images were available. The reference image used for SSIM was the original unprocessed image as proposed in previous studies [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF]. In this case, the SSIM score provides an indication of to what extent original structures were preserved with respect to the noisy input and thus cannot be considered as an image restoration metric. The CNR is defined as :

CNR = |µ 1 -µ 2 | σ 2 1 + σ 2 2 , ( 17
)
where µ 1 and σ 2 1 are the mean and variance of a small region of interest and µ 2 and σ 2 2 are the mean and variance of a homogeneous region of similar dimensions in the background.

In the ultrasound image dataset, we selected small rectangular regions of approximatively 5 mm 2 (or 15 × 15 pixels) in the background and in the foreground. The S 2 spatial sharpness score is a total variation-based metric for natural image sharpness assessment. For an image scaled between 0 and 1, the local total variation (LTV) v(x) of each pixel x is first computed as:

v(x) = 1 4 i,j |x i -x j |, ( 18
)
where the absolute difference is taken between all the pixels in a 2×2 local patch at x. To further attest the performance of the proposed method for edge detection in ultrasound images in a segmentation context, we segmented the prostate gland using an edge-based level set active contour. We compared our segmentation results to those obtained on raw images, SRAD-filtered and ADMSS-filtered images. The active contour model used in our experiments is briefly described in the next lines.

Let C(t) be an active contour defined as the zero level-set of a 2D function φ(x, t) defined across the image domain. The evolution equation of φ according to curvature motion and edge-based external forces is expressed as:

φ t (x) = α [κ(x) |∇φ(x)|] -β [F edge (x) • ∇φ(x)] , ( 19
)
where κ is the curvature of φ, F edge is an EBF field and α, β are parameters that control the respective strengths of curvature motion and edge-based forces. The EBF field F edge is a VFC field based on the squared image gradient magnitude. Images were prepared by centering and cropping the field of view around the prostate. For all methods and all images, we initialized C(t = 0) to a rectangle centered around the prostate and at equal distance of the image boundaries (dotted white contour in Fig. 11). We then let the contour evolve according to eq. ( 19) by considering equal parameters for all tested images and compared the segmentation result (Fig. 11, in yellow) to its ground truth (Fig. 11, in red) using the Jaccard similarity coefficient [START_REF] Jaccard | Distribution de la flore alpine dans le bassin des dranses et dans quelques régions voisines[END_REF] and the Mean Absolute Distance (MAD), which expresses the average distance between the segmented surface and ground truth [START_REF] Gerig | Valmet: A new validation tool for assessing and improving 3D object segmentation[END_REF]. Active contour parameters (number of iterations, α, β, VFK kernel shape) and filter parameters were optimized so as to produce the best average Jaccard score for the tested method on a training dataset of 3 additional TRUS images not included in our evaluation dataset.

C. Enhancement of partial volume corrected PET images

We also performed experiments on partial-volume corrected brain PET images. Because of the scanner point spread function (PSF) of limited spatial resolution and several intrinsic physical factors, PET images suffer from partial volume effects (PVE). PVE are responsible for blur and fuzzy transitions between areas of different radiotracer uptakes, as well as inaccurate quantification (under or over estimation) due to spill-in and spill-out effects [START_REF] Soret | effect in PET tumor imaging[END_REF]. It is generally required to correct for PVE prior to analyzing PET data, a process known as partial volume correction (PVC) [START_REF] Erlandsson | A review of partial volume correction techniques for emission tomography and their applications in neurology, cardiology and oncology[END_REF]. PVC is especially useful in quantitative analysis, as uncorrected PET images may lead to standardized uptake values of poor clinical interpretability [START_REF] Soret | effect in PET tumor imaging[END_REF]. This is however a difficult and ill-posed problem, and most state of the art PVC methods rely on accurate segmentation of co-registered anatomical data obtained from modalities such as MRI or CT [START_REF] Boussion | A multiresolution image based approach for correction of partial volume effects in emission tomography[END_REF], [START_REF] Thomas | The importance of appropriate partial volume correction for PET quantification in Alzheimer's disease[END_REF]. These methods rely on the strong assumption that PET functional regions and anatomical regions coincide. If this assumption cannot be made, or in the absence of availability of accurate co-segmentation of anatomical data, deconvolution approaches like the Richardson-Lucy and the reblurred Van Cittert algorithms are typically considered [START_REF] Tohka | Deconvolution-based partial volume correction in Raclopride-PET and Monte Carlo comparison to MR-based method[END_REF]. While alleviating the need for anatomical information, these methods are however less efficient at PVC than anatomical-based methods, as they amplify image noise [START_REF] Boussion | Incorporation of wavelet-based denoising in iterative deconvolution for partial volume correction in whole-body PET imaging[END_REF], [START_REF] Le Pogam | Denoising of pet images by combining wavelets and curvelets for improved preservation of resolution and quantitation[END_REF] and are generally not capable of fully recovering image sharpness [START_REF] Erlandsson | A review of partial volume correction techniques for emission tomography and their applications in neurology, cardiology and oncology[END_REF]. In the following, we show how the proposed NCSF shock filtering scheme can be employed to enhance deconvolution-based PVC results.

1) Image description: We evaluated our approach using the PET-SORTEO database [START_REF] Reilhac | PET-SORTEO: a Monte Carlo-based Simulator with high count rate capabilities[END_REF]. PET-SORTEO is an open database of highly realistic Monte Carlo simulations of labelled brain PET images that aims at providing reliable ground truth for the validation of PET-dedicated algorithms. The database contains 15 patient brain PET simulated images derived from actual magnetic resonance scans. In our experiments, we focus on the static [ 18 F]-FDG study, showing two functional regions corresponding to differences in uptake of [ 18 F]-FDG between cortical gray matter and white matter (Fig. 7, first column). These images were reconstructed into 128 × 128 × 63 voxels using a filtered back-projection algorithm, leading to high PVE throughout the field of view and relatively low noise levels (Fig. 7, second column).

A partial-volume corrected PET image (the input of the proposed NCSF approach) was obtained using the Reblurred Van Cittert (RVC) algorithm. RVC is an iterative approach that seeks a solution, in the least squares sense, to the following minimization problem:

I b -H * Ĩ , (20)
where I b is the blurred image, Ĩ is the deconvolved image and H is a blur kernel (usually Gaussian), whose PSF is assumed to be known and spatially invariant. An estimate of Ĩ is obtained by the following iterative scheme:

Ĩk+1 = Ĩk + α H * (I b -H * Ĩk ) , (21)
where Ĩk is the corrected image after k iterations and α is a step parameter, usually set around 1.5 [START_REF] Tohka | A monte carlo study of deconvolution algorithms for partial volume correction in quantitative pet[END_REF]. RVC parameters were set so as to minimize the mean square error with respect to the ground truth image. The parameters obtained (α = 1.5; Gaussian PSF of full width at half maximum 9.1 × 9.1 × 9.3 mm 3 ) were found to be in agreement with values reported in a previous PET-SORTEO study for another tracer, using a different optimization strategy [START_REF] Tohka | A monte carlo study of deconvolution algorithms for partial volume correction in quantitative pet[END_REF]. The last column of Fig. 7 shows the RVC outputs corresponding to these two patients. While contrast is increased, functional boundaries remain substantially blurred and noise levels are amplified.

Our objective was to show that NCSF can enhance the quality of the RVC-based partial volume corrected output. In this experiment, NCSF parameters were set equally for all images and optimized so as to maximize on average the SSIM with respect to the ground truth reference.

2) Quantitative metrics: Alongside SSIM, we quantified PET image enhancement using application-specific metrics. A parameter of interest in PET quantification is the gray to white-matter activity ratio R, equal to 2.72 in the ground truth images. R was detemined for each image by averaging activity within the two ground truth labelled regions. Sharpness recovery was assessed by the average gradient magnitude inside the brain ∇I max and by the S 2 index.

V. RESULTS

A. One-dimensional signal Fig. 8a compares the effect of CDSF and NCRSF on the one-dimensional sigmoidal signal S(t). Corresponding quantitative metrics are provided in Table I. Note that the TV of the clean sigmoid is not exactly 1 due to the interval restriction. While both methods successfully denoise the signal, NCRSF was better at recovering the step edge around the inflection point at t = 1/2. This result is highlighted in Fig. 8b that shows the corresponding gradient amplitude of CDSF and NCRSF, with a maximum gradient amplitude about 5 times higher in the case of NCRSF at the inflection point (0.36 for NCRSF against 0.07 for CVDS). The signal was significantly flatter far from the edge with most gradient energy concentrated near the step edge. The TV was also closer to unity (NCRSF: TV= 1.02, CVDS: TV= 1.32), showing fewer spurious gradient signal within the flat regions.

A likely explanation for the better performance of NCRSF is that both shock filtering and diffusion are acting on the signal, In the following, we show results in the more complex context of multidimensional medical images.

B. Ultrasound images

Fig. 9 shows filtering results for SRAD, ADMSS and NCRSF in two transaxial B-mode TRUS images of our clinical dataset (first and third columns). The prostate can be globally described as an hypoechoic medium, showing as a dark, "walnut-shaped" region surrounded by a brighter, more echoic medium. The dots appearing in the unprocessed and SRAD images correspond to artificial grid points superimposed onto the original image. All filters showed substantial denoising capability with different properties. ADMSS tended to better preserve the aspect of the original image, including the smoothness of its edges. The ADMSS filtered images also preserved textural information irrelevant for the contour-based segmentation, showing heterogeneous features throughout the gland due to calcifications. Both SRAD and NCRSF showed better edge-enhancing properties, with a better contrast between background and foreground for NCRSF, alongside with stronger denoising and flattening of the gland. The better behavior of NCRSF for prostate edge detection is stressed on the binary edge maps obtained using an automatic gradientbased edge detector (second and fourth columns). Edges coincide more clearly with the prostate boundaries, with less spurious gradients owing to noise or smaller artifacts. Fig. 10 shows the corresponding S 2 sharpness maps of the images from the first column of Fig. 9. Because the S 2 score is sensitive to noise, the original image shows high sharpness values throughout the field of view. This measure is indeed sensitive to noise, due to global increase of total variation in noisy images. Nevertheless, we find the visualization of sharpness maps useful even in noisy images, where they provide an easy qualitative understanding of which image regions show strong edges, consistently with the sharpness perceived by the observer. In the NCRSF-filtered image, sharp regions mostly coincide with true prostate edges, contrarily to SRAD or ADMSS. Still, some edges belonging to the prostate could not be recovered in difficult regions for which no gradient was detected. These visual observations are further attested by the quantitative metrics calculated on the 14 TRUS images of the dataset shown in Table II. The better similarity between the ADMSS output and the original image is confirmed, showing a higher SSIM score. SAR-BM3D altered the least the original unprocessed image, with a SSIM score of 0.75 ± 0.04 on average, at the expense of lower edge detection capability and contrast recovery. Both PFOM and CNR values were higher when using NCRSF, consistently with higher edge detection accuracy. This suggests that edge-based segmentation of the prostate can be facilitated by prefiltering images using the proposed approach. To support this statement, Table III shows the Jaccard and MAD segmentation results obtained using unprocessed, SRAD-, ADMSS-, SAR-BM3D-and NCRSF-filtered images. Segmentation metrics were higher (increased Jaccard values and smaller MAD) when NCRSF was used as a pre-processing stage, which is consistent with the edge detection results obtained. While being very efficient at denoising and having some edge-enhancing properties due to inverse diffusion behavior around edges [START_REF] Yu | Speckle reducing anisotropic diffusion[END_REF], despeckling filters such as SRAD, ADMSS cannot make the edges sufficiently sharp to yield satisfying segmentation results with edge-based approaches.

Image edges are often deemed unuseable in the TRUS segmentation literature, and region-based approaches based on image statistics are often preferred [START_REF] Finn | Echocardiographic speckle reduction comparison[END_REF]. However, results obtained with the proposed NCRSF scheme suggest that edge information can be exploited to obtain meaningful segmenta- tion results provided the image is appropriately pre-processed.

C. Partial volume corrected brain PET images

Partial volume corrected images of the PET-SORTEO database were processed using the proposed NCSF shock filtering scheme, referred to as RVC+NCSF in the following. For these 3D images, computation time was about 25 seconds on average on a Core i7 CPU using 45 iterations of an explicit finite difference scheme. Fig. 12 shows representative filtering results in transaxial PET slices for patients P05 and P08. From visual inspection, RVC+NCSF images were significantly sharper than RVC alone, showing more acute functional boundaries between gray and white matter. Fig. 13 further supports this statement by comparing one-dimensional profiles in the vicinity of the left thalamic nucleus along the line overlaid in the first column of Fig. 12. Ground truth, RVC and original profiles are also shown, as well as results obtained by applying NCSF directly to the original PET image. Whereas RVC partially recovered lost activity and increased image contrast, it was not able to form a step edge at the thalamic boundary and images remained significantly blurred. NCSF being a total variation preserving filter, it did not change the extremal values of the original PET image. Nevertheless, it significantly increased image sharpness by fully recovering a step edge at the thalamus boundary, similarly to 1D results presented in section V-A. RVC+NCSF, by taking advantage of the deconvolution of RVC, better recovered the gray to white matter activity contrast while taking advantage of the proposed shock filter to obtain a sharp functional boundary of one voxel width.

Average quantitative results obtained across the entire dataset are presented in Table IV and confirm these qualitative observations. The SSIM score showed an increase of 15% on average when compared to RVC (0.186 ± 0.005 against 0.162 ± 0.004), suggesting additional image restoration capability. The perceived sharpness was increased substantially increased, with a 72% increase of the maximum brain gradient amplitude, and a 240% increase of the S 2 score between RVC and RVC+NCSF. The gray-to-white matter activity also showed a moderate increase compared to its value in the original PET image (+11.6% for RVC against +15.2% for RVC+NCSF).

Deconvolution based partial volume correction like the

Van Cittert method are standard in PET image processing pipelines. However, they are usually not able to fully recover image sharpness and tend to amplify image noise. We showed that PET image analysis can benefit from additional post-processing using the proposed nonconservative shock filtering scheme, both visually and quantitatively. The NCSF-filtered images show stronger gradient signal between functional regions and flatter profiles within regions when compared to results obtained with RVC only.

In the PET-SORTEO database, partial volume effects (i.e. blur and quantitative bias) are the main cause of image degradation. Images show only mild levels of noise due to the strong regularization induced by the filtered backprojection reconstruction algorithm. We thus focused on the shock filtering part of the scheme (ie. NCSF and not NCRSF). However, iterative reconstructions using methods such as ordered subset expectation maximization (OSEM) are now preferred in the PET community. While yielding more accurate image quantification, they generally induce more noise in the data. In that case, a coupled regularization and shock filtering method using NCRSF would likely improve results over NCSF only.

VI. CONCLUSION

We have proposed a new method for the progressive restoration of images degraded by noise and blur using shock filters. The proposed NCSF approach exploits nonconservative edge based force fields that were normally designed for segmentation. By iteratively refining edge localization, it produces images with strong discontinuities that facilitate higher level tasks such as edge detection or segmentation. NCSF is especially useful when coupled with an anisotropic diffusion framework in noisy configurations (NCRSF), as edges that are not well defined prior to filtering can be iteratively recovered. Results on various types of medical images (ultrasound and PET) were used to evaluate the performance and the genericity of the proposed enhancement approach.

Fig. 1 .

 1 Fig. 1. Effect of the proposed NCSF on a sigmoidal 1D signal. Shocks are recovered around the inflection point at x = 0 (red dot) with strength proportional to |P(x)| × ∇I (vertical arrows), where P(x) is the degree of co-alignment between F t and ∇I.

Fig. 2 .

 2 Fig. 2. VFK kernel used for VFC calculation. Vectors point toward its center r 0 with decreasing intensity. (a) s = 5, γ = 2.2. (b) s = 5, γ = 2.8. High values of γ increase sensitivity to local weak edges but also yield more sensitivity to isolated noise

Fig. 3 .Fig. 4 .

 34 Fig. 3. Shock filter action on a synthetic disks image corrupted with Gaussian blur and AWGN noise

Fig. 5 .

 5 Fig. 5. Top row: processing result using the proposed NCRSF scheme on a color image corrupted by Gaussian blur and AWGN. Bottom row: magnified region marked in red. (b) Independent sharpening of each channel produces false colors at the location of shocks. (c) Coupled sharpening using the structure tensor-based EBF field restores sharpness without producing false colors. Better viewed in electronic version.

Fig. 5

 5 Fig. 5 illustrates the effect of the proposed ADR filtering for VV images on the 512 × 512 monument color image of the CSIQ database [51]. The clean image was blurred with a Gaussian filter of scale 2 pixels and corrupted with zero-mean AWGN of standard deviation σ n = 35. When channels are processed independently (Fig. 5b), false colors appear around locations of shocks. Under the proposed coupled VV scheme (fig 5c), noise is suppressed efficiently without producing false colors.

40 Fig. 6 .

 406 Fig. 6. Approximation of NCSF filtering for the 512 × 512 mandrill image for different values of Euler time step dt (CPU time in brackets). Image values are advected along the flow lines of the VFC field F t dt. Processed images with coarse time steps are hard to distinguish visually from reference dt = 0.05

  Since blurred image edges tend to have a low LTV, the maximum value of v(x) in b × b overlapping superblocks, with b > 2, gives a spatial map of the local sharpness of an image at scale b. The S 2 index is obtained by averaging the 1% highest pixel values of the spatial map.

Fig. 7 .

 7 Fig. 7. Example transaxial PET slices in patients P05 and P08 of the PET-SORTEO database. Left: ground truth reference. Middle: original PET image. Right: partial volume correction with RVC.

  From top to bottom: Clean sigmoid, Noisy sigmoid, CDSF[START_REF] Gilboa | Image enhancement and denoising by complex diffusion processes[END_REF] and proposed NCRSF. Gradient amplitudes for CDSF and NCRSF. Maximum gradient amplitude near the step edge is more than 5 times higher for NCRSF.

Fig. 8 .

 8 Fig. 8. Recovery of a step signal from a noisy sigmoid in the 1D case.

Fig. 9 .

 9 Fig.9. Example processing results for axial TRUS images of two patients of our clinical dataset and corresponding edge maps. From top to bottom: clinical image, SRAD[START_REF] Yu | Speckle reducing anisotropic diffusion[END_REF], ADMSS[START_REF] Ramos-Llordén | Anisotropic diffusion filter with memory based on speckle statistics for ultrasound images[END_REF] and proposed NCRSF filter.

Fig. 10 .

 10 Fig.10. Effect of the filtering on perceived image sharpness in a TRUS image using TV-based S 2 sharpness map with block size 8[START_REF] Vu | S3: A Spectral and Spatial Measure of Local Perceived Sharpness in Natural Images[END_REF]. NCRSF sharpened regions mainly coincide with true prostate edges.

Fig. 11 .

 11 Fig. 11. Effect of the coupled ADR scheme on active contour segmentation of the prostate. Initial state is in dotted white, manual ground truth in red, segmentation result in yellow.

Fig. 12 .

 12 Fig. 12. Example enhancement of deconvolution-based partial volume correction results for patient P05 and P08 of the PET-SORTEO database. Left: RVC only. Right: RVC+NCSF.

Fig. 13 .

 13 Fig.[START_REF] Prada | Unconditionally stable shock filters for image and geometry processing[END_REF]. Activity profiles across the left thalamic nucleus for patients P05 and P08 along the line overlaid in Fig.12.

TABLE II QUANTITATIVE

 II SCORES FOR THE TRUS IMAGE DATASET (n = 14)

		SSIM	PFOM	CNR
	Noisy	1	0.13±0.02 0.91±0.62
	SRAD	0.39±0.03 0.17±0.03 1.26±0.85
	ADMSS	0.47±0.08 0.18±0.05 1.16±0.88
	SAR-BM3D	0.75±0.04	0.16±0.03 1.02±0.70
	NCRSF	0.30±0.02	0.27±0.05 1.41±0.99

TABLE III SEGMENTATION

 III SCORES FOR THE TRUS IMAGE DATASET (n = 14)

		Jaccard	MAD (mm.)
	Original	0.72±0.06	2.89±0.60
	SRAD	0.77±0.09	2.43±0.88
	ADMSS	0.77±0.11	2.32±1.17
	SAR-BM3D 0.75±0.07	2.63±0.71
	NCRSF	0.85±0.05	1.54±0.53

TABLE IV QUANTITATIVE

 IV SCORES FOR THE PET SORTEO DATABASE (n = 15) 186±0.005 0.65±0.02 12.31±0.42 1.59±0.02

		SSIM	S 2	∇I max	R
	True	1.0	1.0	18.46±1.86	2.72
	Orig.	0.101±0.003 0.20±0.00	3.99±0.12	1.38±0.01
	RVC	0.162±0.004 0.27±0.01	7.17±0.31	1.54±0.01
	RVC+NCSF 0.

https://sites.google.com/site/gramosllorden/admss

http://viva-lab.ece.virginia.edu/downloads.html

http://www.grip.unina.it/research/80-sar-despeckling/

ACKNOWLEDGMENT

This work was partly supported by the French ANR within the Investissements d'Avenir program (Labex CAMI) under reference ANR-11-LABX-0004 (Integrated project CAPRI).


Imen Bouhlel
email: imen.bouhlel@gredeg.cnrs.fr

Charley M Wu

Nobuyuki Hanaki

Robert L Goldstone

Sharing is not erring: Pseudo-reciprocity in collective search

Keywords: Collective search, information sharing, pseudoreciprocity

Information sharing in competitive environments may seem counterintuitive, yet it is widely observed in humans and other animals. For instance, the open-source software movement has led to new and valuable technologies being released publicly to facilitate broader collaboration and further innovation. What drives this behavior and under which conditions can it be beneficial for an individual? Using simulations in both static and dynamic environments, we show that sharing information can lead to individual benefits through the mechanisms of pseudoreciprocity, whereby shared information leads to by-product benefits for an individual without the need for explicit reciprocation. Crucially, imitation with a certain level of innovation is required to avoid a tragedy of the commons, while the mechanism of a local visibility radius allows for the coordination of self-organizing collectives of agents. When these two mechanisms are present, we find robust evidence for the benefits of sharing-even when others do not reciprocate.

Introduction

In a competitive environment, it may seem counterintuitive to share information about a new innovation (which could be copied) or the location of resources (which could be stolen). Yet unrestricted sharing of information is widely observed in both human and animal behavior. The open-source software movement is a prominent example of this behavior, where rather than privately monetizing economically viable innovations, they are shared in order to foster broader collaboration and further innovation, leading to benefits for the public good. Yet do the individuals who share also themselves benefit? What drives this behavior and how can we understand it through the mechanisms of social cooperation and collective search behavior?

In ecology, it has been observed that many species share information via mass recruitment systems when foraging for resources, whereby successful foragers send signals (e.g., sounds or pheromone trails) to help locate resources. For example, the American Cliff Swallow has a unique call used only when it finds air-borne food [START_REF] Brown | Foodsharing signals among socially foraging cliff swallows[END_REF]. The call is an unrestricted social signal to other Cliff Swallows which does not only benefit kin (i.e., no kin selection mechanisms). Rather, the individual welfare of each Cliff Swallow is improved by the recruitment of peers towards the search effort, since the collective performs better at tracking prey than any lone individual. More generally, this behavior-common in different animal populations-is known as pseudo-reciprocity [START_REF] Connor | Pseudo-reciprocity: investing in mutualism[END_REF][START_REF] Clutton-Brock | Cooperation between non-kin in animal societies[END_REF][START_REF] Torney | Signalling and the evolution of cooperative foraging in dynamic environments[END_REF], meaning altruistic behavior, such as sharing information, can generate "byproduct" benefits that improve individual fitness without the need for explicit reciprocation. Thus, pseudo-reciprocity in Cliff Swallows is thought to be mainly driven by the sparse and dynamic distribution of resources in the environment [START_REF] Brown | Foodsharing signals among socially foraging cliff swallows[END_REF], which makes individual search very difficult, although in general the mechanisms are not well understood.

Forms of Cooperation

The study of human cooperation has revealed different levels of mechanisms that can lead to altruistic behavior [START_REF] Rand | Human cooperation[END_REF], such as direct or indirect reciprocity. Direct reciprocity requires repeated interactions and conditional strategies (i.e., cooperate or defect), where the evolution of cooperation depends on the likelihood of future interactions [START_REF] Axelrod | The evolution of cooperation[END_REF][START_REF] Rand | Human cooperation[END_REF]. Thus, altruistic actions are explained by the expectation of reciprocity from peers in future interactions, conditional on one's own behavior. Indirect reciprocity extends this expectation of future reciprocity further, through reputation-based systems, whereby cooperative behavior is viewed as a type of social signaling to third-parties [START_REF] Nowak | Upstream reciprocity and the evolution of gratitude[END_REF]. Thus, maintaining a positive reputation can have "downstream" effects, making it more likely for third-parties to cooperate, even if there have been no previous history of interactions.

Both direct and indirect reciprocity can be understood as forms of impure altruism [START_REF] Andreoni | Giving with impure altruism: Applications to charity and ricardian equivalence[END_REF], whereby altruistic behavior is explained through the expectation of future reciprocation within a self-interested, utility-maximization framework, and has been applied to game theory in public good games [START_REF] Andreoni | Impure altruism and donations to public goods: A theory of warm-glow giving[END_REF][START_REF] Falk | A theory of reciprocity[END_REF][START_REF] Nowak | Evolution of indirect reciprocity[END_REF], but less so to collective search contexts. In contrast, pseudo-reciprocity, can be understood as an investment in other individuals in order to acquire or enhance by-product benefits, without the need for explicit reciprocation [START_REF] Leimar | By-product benefits, reciprocity, and pseudoreciprocity in mutualism[END_REF][START_REF] Čače | Agent based modelling of communication costs: Why information can be free[END_REF]. The sharing of information about the solution to a problem or the location of resources can benefit the sharer, because it can lead others to copy and improve on the original information, which can aid the original sharer as a by-product benefit.

For instance, in the case of the Cliff Swallow [START_REF] Brown | Foodsharing signals among socially foraging cliff swallows[END_REF], the individual who signals for others gains byproduct benefits through the recruitment of peers, regardless of whether or not they also signal in the future [START_REF] Connor | Altruism among non-relatives: alternatives to the prisoner's dilemma[END_REF], since recruitment immediately aids in the tracking and acquisition of food1 . Importantly, this entails that pseudoreciprocity can operate in systems without repeated interactions or reputation systems [START_REF] Torney | Signalling and the evolution of cooperative foraging in dynamic environments[END_REF], which is not the case for direct or indirect reciprocity. While both forms of impure altruism have been greatly studied in game-theory [START_REF] Dufwenberg | A theory of sequential reciprocity[END_REF][START_REF] Fehr | Altruistic punishment in humans[END_REF][START_REF] Milinski | Reputation helps solve the tragedy of the commons[END_REF][START_REF] Lotem | Evolution of cooperation between individuals[END_REF][START_REF] Nowak | The dynamics of indirect reciprocity[END_REF], there exist relatively little study of pseudo-reciprocity in human behavior (although considerably more in animal behavior [START_REF] Brown | Foodsharing signals among socially foraging cliff swallows[END_REF][START_REF] Connor | Pseudo-reciprocity: investing in mutualism[END_REF][START_REF] Wilkinson | Information transfer at evening bat colonies[END_REF].

The Role of the Environment in Collective Search

In a collective search task, one must learn to balance the exploration of yet unknown solutions, while also exploiting existing knowledge in order to yield immediate returns. This frames the exploration-exploitation dilemma, where different environments can demand a different ratio of exploration to exploitation [START_REF] Barkoczi | Collective search on rugged landscapes: A cross-environmental analysis[END_REF]. The relative effectiveness of different search strategies can be drastically altered by changing one of many aspects of the task environment, such as the complexity of the problem space [START_REF] Mason | Propagation of innovations in networked groups[END_REF], the connectivity of the communication network [START_REF] Barkoczi | Social learning strategies modify the effect of network structure on group performance[END_REF][START_REF] Lazer | The network structure of exploration and exploitation[END_REF][START_REF] Mason | Propagation of innovations in networked groups[END_REF][START_REF] Mason | Collaborative learning in networks[END_REF], the type of social information being communicated [START_REF] Wisdom | Social learning strategies in networked groups[END_REF], and the learning strategies of each individual agent [START_REF] Barkoczi | Social learning strategies modify the effect of network structure on group performance[END_REF]. However, one aspect taken for granted in these previous collective-search paradigms, is that information is always freely given, whereas in many real world situations agents make an explicit decision to either share or withhold information. We examine how different task environments and behavioral mechanisms influence the adaptiveness of freely sharing information.

Goals and Scope

In which environments will we find stable benefits for freely sharing information, and where will we fail to find it? We present multi-agent simulations of a competitive search task in n-dimensional search spaces, with both static and dynamic reward structures. Agents are given a limited search horizon to search for rewards, with different populations of agents containing different mixtures of either sharers or nonsharers. We focus on four main mixtures (All sharers, No sharers, Free-rider, and Free-giver) in order to determine for any given agent whether or not it is better to share or to withhold information from others. We use a competitive search context, whereby agents who choose the same location in the search space must split the reward between them. In the static simulation, we use a fitness landscape where the reward is a monotonically decreasing function of the distance from a randomly selected global optimum. In the dynamic simulation, the reward function is similar, but the global optimum follows a random walk, moving on each trial.

Static Simulations

We present a mathematical framework for studying the benefits of sharing information in a competitive search context. We use multi-agent simulations to implement this framework, and present simulation results across a variety of different environmental structures.

The search task involves k agents searching for rewards on an n-dimensional environment, where each dimension d in 1, 2, 3, ..., n can take any positive or negative integer value. The task takes place over T = 100 trials, where at each time t ∈ [1, T ], all agents individually make a decision about where to search for rewards, and then whether or not to share that information with other agents (see Information Sharing). Altogether, we vary the number of agents k ∈ [4, 10], the number of dimensions of the search space n ∈ [5, 15], the innovation rate p c ∈ {0, 0.5, 1}, the visibility radius r ∈ {0, 1, 2}, and the mixture of sharing strategies (All sharers, No sharers, Freerider, and Free-giver).

Fitness function

Each search decision is represented as a vector

x t = [d t 1 , ..., d t n ],
where the resulting payoff y t = f (x t ), is given by the inverse Manhattan distance between the global optimum M and x t :

f (x t ) = 2 1 + x t -M 1 • 100 (1)
with Laplace smoothing used to prevent division by zero and rescaled by a factor of 100. The global maximum of the environment at time t is represented by M = [D 1 , ..., D n ], which is drawn from a uniform distribution U(1,10).

The competitive nature of the task is represented by splitting earned payoffs between agents who make the same search decision on a specific trial (i.e., subtractive resources). Let P t = [x t1 , ..., x tk ] represent the matrix containing all k-agents' search decisions at time t. For each agent i, let C(x ti ) be the number of rows in P t matching x ti ,

C(x ti ) = ∑ j δ(x ti , x t j ), (2)
where δ(x ti , x t j ) = 1 if x ti = x t j , and 0 otherwise. Thus, C(x ti ) = 1 when x ti is unique, otherwise, C(x ti ) > 1. Thus, each agent earns reward R(x ti ) = y ti C(x ti ) , where R(x ti ) = y ti when no splitting of rewards occurs.

Individual Search

At trial t = 1, all agents start with a random location sampled from a uniform distribution U(1,10). For all subsequent trials, each agent i has access to the history of previous observations O ti , which includes both individually acquired observations o ti = {x li , R(x li )} t-1 l=1 and socially observed data s ti , where {x l j , R(x l j )} is contained in s ti if agent i observed agent j's ( j = i) information at trial l < t (see Information Sharing). Contingent on O ti , we use a local search strategy where the agent selects the search decision that had previously yielded the largest reward, x * ti = argmax x li,l∈[1,t-1] R(x li ), and then innovates on that solution by modifying each value in x * ti by a discrete value in {-1, 0, 1}. We define the Innovation rate as the probability p c ∈ {0, 0.5, 1} with which the agent innovates on the search decision x * ti . On each trial the agent innovates with probability p c , where otherwise x * ti is copied verbatim. If the agent innovates, then we draw from a Binomial distribution centered on zero c t im ∼ B 2, 1 2 -1 for each dimension of the search problem m = 1, ..., n. Intuitively, half of the time c t im = 0, meaning there is no change along that dimension, while changes of both -1 or +1 are equally likely, each with probability 0.25. Thus, when innovation occurs, the search decision at t + 1 is defined as:

x (t+1)i = x * ti + [c t i1 , ..., c t in ] (3)

Information Sharing

We consider four different mixtures of sharers and nonsharers in the collective. No sharers and All sharers are cases where there is a homogeneous mixture of strategies, with either all agents or no agents sharing information. In the Freerider and Free-giver conditions, there is a single heterodox agent who acts in contradiction to the rest of the collective. The Free-rider agent is one who withholds information while all others share, and the Free-giver agent is one who shares information, even though all others withhold information. In all cases, sharing information broadcasts both the location x ti and the earned reward R(x ti ) to all other agents. We use differences in performance across these four conditions to examine the individual benefits of sharing when the behaviors of all others are fixed. By comparing the performance differences between the Free-rider agent and any given agent of the All sharer agents, we observe if there exist individual benefits of sharing when others also share. Similarly, we can compare individual performance differences between the Free-giver agent and any of the No sharer agents to observe the benefit of sharing when others don't share. Environments where sharing is beneficial at both levels provide evidence of pseudo-reciprocity, whereby sharing confers benefits without the need for explicit reciprocation.

Visibility Radius

In addition to explicitly shared information, we also implement a Visibility Radius defined as r ∈ {0, 1, 2} where localized clusters of agents have free access to information about each other's current solution and rewards. For any two agents i = j, agent j is visible to agent i at trial t if the Chebyshev distance between x ti and x t j :

D Chebyshev (x ti , x t j ) = max m |d t im -d t jm | (4)
is smaller than the Visibility Radius r. Intuitively, Chebyshev distance is also referred as "chessboard distance", since it is the minimum number of moves needed by a king to go from one square to another. If agent j is visible to agent i at trial t, then information about the current search decision and reward is automatically shared: {x t j , R(x t j )} ∈ s (t+1)i . The visibility radius is an important coordination mechanism that allows for localized transmission of information, whereas the explicit decision to either share or withhold information operates for all distances greater than r. Crucially, given the high dimensionality and size of the search space, it is very unlikely for any two agents to fall within the same visibility radius without explicit information sharing.

Results

Across each combination of environmental parameters, we conducted 10,000 simulations and computed the mean payoff over trials for each individual agent. In Figure 1 we show heat maps of the simulation results, where the color of each tile represents the net individual benefit of sharing. In Figure 1a, we compute the net benefit of sharing (when others share) as the difference between the mean payoff for a random agent from the All sharers condition and the mean payoff of a Freerider agent. Thus, red values indicate a net benefit of sharing, while blue values indicate a net cost of sharing. In Figure 1b we run the same analysis, but compute the net benefit of sharing (when others don't share) as the difference between the mean payoff for a Free-giver agent and a random agent from the No sharers condition. Again, red values indicate a net benefit of sharing, while values indicate a net cost. In both cases (when others share and when they do not), we find benefits for sharing information. Benefits of sharing. Overall, we found evidence that sharing information can be a beneficial strategy, so long as peers copy with some level of innovation and in the presence of a visibility radius. Benefits were found both with and without reciprocation. Interestingly, the relative benefits of sharing when others don't share (Free-giver vs. No sharers) were far larger than when others also share (All sharers vs. Free-rider), likely due to diminishing returns as the collective becomes more saturated with social information (see Fig 2). Thus, sharing information without explicit reciprocation leads to the largest net benefit, whereas any potential disadvantages to sharing when others share is entirely reversed by the mechanisms of innovation and the visibility radius. Number of agents and size of the environment. As long as there are innovators (p c = 0), we find that larger collectives reap larger benefits of sharing when exploring larger environments. Moreover, larger visibility increases these benefits in larger environments. Hence, the potential disadvantages of overcrowding are washed out by the advantages of social coordination through pseudo-reciprocity. Sharing when others don't share

Figure 1: Static simulation results. We simulated 10,000 replications for each combination of environmental parameters (number of agents, number of dimensions, innovation rate and visibility radius) crossed with each of the four scenarios (all sharers, no sharers, freerider, and free-giver). a) Sharing when others share. The color of each tile shows the difference in the mean agent payoffs, comparing an agent who shares when others also share (all sharers) and an agent who withholds information when others share (free-rider). Red values indicate a net benefit of sharing, white indicates no difference, and blue indicates a net disadvantage. We see that all negative sideeffects of sharing disappear when both innovation and visibility are present. b) Sharing when others don't share. Colors show the difference in mean agent payoffs, comparing an agent who shares when no one else shares (free-giver) and an agent who withholds information along with everyone else (no sharers). We see that both innovation and visibility support the benefits of sharing, although here we see stronger benefits, with a linear relationship between the number of agents and number of dimensions that leads to maximal benefits.

Innovation and visibility. Sharing information for others to imitate can be beneficial, as long as imitation also involves some level of innovation. Thus, Roger's Paradox [START_REF] Rendell | Rogers paradox recast and resolved: population structure and the evolution of social learning strategies[END_REF], whereby social information can sometimes reduce mean fitness leading to a tragedy of the commons, only holds in our simulations when innovation is zero (Fig. 1). Additionally, Figure 2 shows the effect of the visibility radius on trial-by-trial performance, where we fix the number of agents (k = 10), the size of the environment (n = 7), and set the innovation rate to p c = 0.5. Here we see that by introducing a visibility radius, the maladaptiveness of sharing when others also share (comparing free-rider to all sharers) becomes non-existent, creating no benefit to withholding information (i.e., free-riding). Moreover, the visibility radius even more dramatically reverses the performance difference between sharing while others don't (free-giver) and when no Each line is either a random agent drawn from the all sharers or no sharers condition, or specifically the heterodox agent in the free-rider and free-sharer conditions. Across different visibility radii, we see how the maladaptiveness of sharing (left panel) disappears, and transforms into an adaptive benefit. With a visibility of 1, the benefits of free-riding are reduced to zero, while the reversal for free-giving is much more dramatic and confers much larger rewards than the counter-factual case of withholding information (i.e,. no sharer).

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
social learning takes place (no sharers). Whereas without a visibility radius, being a free-giver is a maladaptive strategy, we find a stark reversal when the visibility radius is introduced, where free-giving dramatically increases individual fitness, and even begins to approach the performance levels of the all-sharers condition. In our simulations, we find that both innovation and visibility are essential mechanisms that facilitate the adaptiveness of pseudo-reciprocity by creating conditions where sharing information confers by-product benefits to the individual-without the need for reciprocation.

Dynamic Simulations

We adapted the static simulations so that the global maximum changes over time. The global maximum at time t is then defined by M t = [D t 1 , ..., D t n ]. We define Environmental change as the probability p e ∈ {0.25, 0.5, 0.75} with which the global maximum changes at each time t. If the environment changes, then each dimension D t m is updated using:

D t m = D t-1 m + e t m ( 5
)
where e t m ∼ B 2, 1 2 -1, is a Binomial distribution centered on zero. Thus, environmental change operates on the same mechanism as used by agents in individual search.

In order to account for the decreasing validity of past observations in a dynamically changing environment, we introduce a Discount rate parameter γ ∈ {0.5, 0.6, 0.7, 0.8, 0.9} to discount the memory of previous rewards as a function of elapsed time, where smaller values of γ result in harsher discounting. Similar to temporal discounting, observations of past rewards R ti are discounted by : R(

x ti ) = γ τ • R(x ti ) (6)
where R(x ti ) is the discounted reward observation and τ is the elapsed time between the observation and the current time. Visibility: 2 0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9 Visibility: 2 0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9 Here we fixed the number of agents (k = 10) and the number of dimensions (n = 7) to more freely explore differences in the dynamic environment parameters. We simulated 10,000 replications for each combination of the remaining environmental parameters (innovation rate, visibility radius, environmental change, and discount factor), crossed with each of the four scenarios (all sharers, no sharers, free-rider, and free-giver). a) Sharing when others share. Both innovation and visibility are robust to differences in rates of environmental change, and mediate net benefits of sharing when others also share. A strong environmental change rate also generally amplifies the net benefit of sharing. b) Sharing when others don't share. The benefits of sharing are observed as soon as innovation and visibility are positively valued, and are amplified by small discount rates (resulting in faster decay rates). Moreover, with a high level of innovation (p c = 2) and visibility (r = 2), we see the strongest net benefits for sharing out of all simulations presented.

Thus, in the dynamic simulations the local search strategy innovates on the search decision that has the largest discounted reward, x * ti = argmax x li,l∈[1,t-1] R(x li ). In our dynamic simulations, we fix the number of agents and the size of the environment (k = 10; n = 7) to the combination that yielded one of the highest benefits of sharing in the static analysis, while exploring the influence of environmental change p e and the discount rate γ, along with innovation rate and visibility radius. Our goal is to find whether the sharing benefits observed in the static environment are robust to temporal dynamics in a changing environment.

Results

Across each combination of environmental parameters and each of the four mixtures of sharers, we conducted 10,000 simulations and computed the mean payoff over trials for or specifically the heterodox agent in the free-rider and free-sharer conditions. Innovation increases the performance, and visibility increases the benefits of free giving. With positive values for both innovation and visibility radius, we find that there is never any disadvantage to sharing, either when others also share (all sharers vs. free-rider) or when others don't (free-giver vs. no sharers).

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
each individual agent, identical to the static simulations. Again, we find evidence of benefits for sharing information (Fig 3), both with and without reciprocation. While we see smaller benefits of sharing when others also share compared to the static simulations (Fig 3a), we still find that any net disadvantages of sharing are reversed into either a net benefit or a cost-free outcome when innovation and the visibility radius are present. In the case of sharing without reciprocation (Fig 3b ), we find even stronger benefits of sharing than in the static simulations for particularly high innovation and visibility.

Environmental change and discount rate. We observe the largest benefits of sharing in slower changing environments. Indeed, coordination of search through sharing social information is even more crucial in tracking changing rewards. However, rapidly changing environment can quickly become too difficult for any mixture of sharing strategies. We also don't see any strong relationships between the discount rate and the rate of environmental change, suggesting that discounting past observations by itself is insufficient for adapting to a changing environment. Instead, the mechanisms of innovation and visibility played a far larger role in shaping the adaptiveness of either sharing or withholding information.

Innovation and visibility. We replicate the main finding from the static simulations, showing that both innovation and visibility are key ingredients for fostering pseudo-reciprocity. Each ingredient has a distinct directed effect: high innovation increases the mean performance of all agents as soon as the population contains a majority of sharers, whereas high visibility increases the individual benefits of sharing in populations where only one agent shares (Fig. 4). In dynamic environments, we find a larger benefit for sharing when others don't share (see Fig. 4b) when we increase the visibility radius from 1 to 2 This indicates a need for more dispersed collectives of agents in changing environments, with coordination operating over larger distances. When both innovation and local visibility are present, we find that the benefits of sharing can be even larger than in the static case.

General Discussion

We investigated the rationality of sharing information in a competitive search context using agent-based modeling.

Agents searched for rewards through n-dimensional environments using a local search strategy, while information about observations could either be shared with the collective or withheld. The competitive context was induced by agents being forced to equally split rewards if they chose the same location. Across both static and dynamic reward environments, we found evidence that sharing information can enhance individual performance without the need for reciprocation, operating on the as yet poorly-understood mechanisms of pseudoreciprocity. Our environmental analysis of 2,700 different environments found two essential mechanisms that facilitated the benefits of sharing. Firstly, we found that sharing information for others to imitate can prove beneficial so long as imitation also involves some level of innovation. Secondly, we found that a visibility radius (allowing free information from peers within a limited distance) acted as an essential coordination device, facilitating the creation of by-product benefits for sharing. Crucially, the unrestricted sharing of information acts as a recruitment mechanism, where the visibility radius allows for small localized collectives to cooperatively find better rewards. One limitation of our study is that we only investigate environments with a single global maximum, whereas differences in the search environments can induce different demands on the exploration-exploitation trade-off (Barkoczi et al., 2016). Indeed, highly rugged fitness landscapes may cause shared information to be a burden rather than boon, misleading individuals or collectives to explore sub-optimal local maxima of the search space. In the future, we would also look at the influence of different types of social networks governing the flow of shared information [START_REF] Lazer | The network structure of exploration and exploitation[END_REF][START_REF] Mason | Collaborative learning in networks[END_REF], along with a wider variety of individual search strategies that more closely resemble human search behavior [START_REF] Wu | Exploration and generalization in vast spaces[END_REF].

Conclusion

While there have been many studies on collective search, they all typically assume free access to social information, without considering the decision to either share or withhold information. In this study, we find that even in a competitive search context, sharing information can prove beneficial, in both static and dynamic reward environments. This is one of the first studies to look at the environmental conditions that support pseudo-reciprocity in a competitive search context, whereby shared information can lead to by-product benefits for an individual without the need for reciprocation. This work is one of the first steps towards understanding the ecological rationality of the open source movement through the lens of a coordination system that does not require either reputation or repeated interactions.

Figure 2 :

 2 Figure2: Learning curves. Mean score for 10,000 replications using k = 10 agents and n = 7 dimensions, and with innovation rate p c = 0.5. Each line is either a random agent drawn from the all sharers or no sharers condition, or specifically the heterodox agent in the free-rider and free-sharer conditions. Across different visibility radii, we see how the maladaptiveness of sharing (left panel) disappears, and transforms into an adaptive benefit. With a visibility of 1, the benefits of free-riding are reduced to zero, while the reversal for free-giving is much more dramatic and confers much larger rewards than the counter-factual case of withholding information (i.e,. no sharer).

Figure 3 :

 3 Figure3: Dynamic simulation results. Here we fixed the number of agents (k = 10) and the number of dimensions (n = 7) to more freely explore differences in the dynamic environment parameters. We simulated 10,000 replications for each combination of the remaining environmental parameters (innovation rate, visibility radius, environmental change, and discount factor), crossed with each of the four scenarios (all sharers, no sharers, free-rider, and free-giver). a) Sharing when others share. Both innovation and visibility are robust to differences in rates of environmental change, and mediate net benefits of sharing when others also share. A strong environmental change rate also generally amplifies the net benefit of sharing. b) Sharing when others don't share. The benefits of sharing are observed as soon as innovation and visibility are positively valued, and are amplified by small discount rates (resulting in faster decay rates). Moreover, with a high level of innovation (p c = 2) and visibility (r = 2), we see the strongest net benefits for sharing out of all simulations presented.

Figure 4 :

 4 Figure 4: Learning curves. Mean score for 10,000 replications using k = 10 agents and n = 7 dimensions, and with environmentalchange p e = 0.25 and discount rate γ = 0.8. Each line is either a random agent drawn from the all sharers or no sharers condition, or specifically the heterodox agent in the free-rider and free-sharer conditions. Innovation increases the performance, and visibility increases the benefits of free giving. With positive values for both innovation and visibility radius, we find that there is never any disadvantage to sharing, either when others also share (all sharers vs. free-rider) or when others don't (free-giver vs. no sharers).

A crucial mechanism is that each Cliff Swallow has free, visual information about the location of nearby peers, thus allowing for localized coordination (see Visibility Radius).