{'fraction_non_alphanumeric': 0.032775972118886325, 'fraction_numerical': 0.007126913889650311, 'mean_word_length': 4.505065746928217, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analyzing spatially-varying blur

Blur is caused by a pixel receiving light from multiple scene points, and in many cases, such as object motion, the induced blur varies spatially across the image plane. However, the seemingly straight-forward task of estimating spatially-varying blur from a single image has proved hard to accomplish reliably. This work considers such blur and makes two contributions: a local blur cue that measures the likelihood of a small neighborhood being blurred by a candidate blur kernel; and an algorithm that, given an image, simultaneously selects a motion blur kernel and segments the region that it affects. The methods are shown to perform well on a diversity of images.


Introduction
Blur refers to image degradation caused by a pixel recording light from multiple scene points, and its common causes include camera shake, defocus, and object motion. Blur is characterized by a "kernel", or point-spread function (PSF), and when the cause of blur is defocus or object motion, the kernel typically changes across the image plane. Such spatially-varying blur is much harder to analyze than its uniform counterpart, and as a result, most methods for estimating spatially-varying blur require multiple images, an initial segmentation, or something else to augment the seemingly meager information available in a single photo.
The limited success with spatially-varying blur lies in stark contrast to recent advances with uniform blur. In the latter case, one can now reliably estimate and reverse the effects of blur through a variety of methods, even when the (spatially-uniform) kernel is of a complex, nonparametric form [4,11,12,14,17,20]. The difference in the spatially-varying case is that blur must be inferred locally, using many fewer observations than are available in a large, uniformly-blurred image. And this means that one must use stronger image models to be able to extract the required information from a reduced set of measurements. Figure 1. What's moving ? Given an image with motion blur, we seek to infer the blur kernel and the region it affects. The image on the right shows a segmentation of the blurred object in the image, and an estimate of the blur kernel generated by our algorithm. This paper presents a novel cue for analyzing blur locally and reasoning about non-uniform cases. Starting with a standard sub-band decomposition (a "local Fourier transform"), we introduce a probability model for unblurred natural images that is simple enough to "play well" with the decomposition but powerful enough for accurate inference. This gives us a robust and efficient likelihood measure for a small image window being blurred by a given kernel.
This cue is then applied to the problem of segmenting motion-blurred regions from otherwise sharp images and simultaneously selecting the blur kernel acting on the affected region. We evaluate this approach using a diverse collection of images that each contain a single moving object. It yields satisfactory estimates of the blur kernel in most cases, and as suggested in Fig. 1, it is able to obtain useful segmentations when combined with color information.

Related work
Inferring the point spread function from a blurred image requires simultaneously reasoning about the PSF and the latent sharp image on which it operates. To address the problem, one must define the family of blur kernels to be considered as well as a model-often probabilistic in nature-for sharp images. Existing methods differ in terms of the types of blur they consider, the input they assume, and whether or not they consider spatial variation.
When the blur is spatially-uniform, one has the good fortune of being able to accumulate evidence across the entire image plane, and as a result, one can afford to consider a very general class of blur kernels. In this context, a variety of recent techniques have shown that it is possible to recover completely non-parametric (i.e., tabulated) blur kernels, such as those induced by camera shake, from as little as one image [4,11,12,14,17,20]. One general insight that is drawn from this work is that instead of simultaneously estimating the blur kernel and a single sharp image that best explain a given input, it is often preferable to first estimate the blur kernel as that which is most likely under a distribution of sharp images. Levin et al. [17] refer to this process as "MAP k estimation", and we will use it here.
Blur caused by motion or defocus often varies spatially in an image, and in these cases, one must infer the blur kernels using local evidence alone. To succeed at this task, most methods consider a reduced family of blur kernels (e.g., one-dimensional box filters), and they incorporate more input than a single image. When two or more images are available, one can exploit the differences between blur and sensor noise [22] or the required consistency between blur and apparent motion [1,2,5,6] or blur and depth [9,10]. As an alternative to using two or more images, one can use a single image but assume that a solution to the foreground/background matting problem is given as input [7,8,13]. Finally, one may be able to use a single image, but with special capture conditions to exaggerate the effect of the blur, as is done in [16] with a coded aperture (and additional user input) for estimating defocus blur that varies spatially with scene depth.
More related to our work is the pioneering effort of Levin [15], who also considers single-image input without pre-matting. The idea is to segment an image into blurred and non-blurred regions and to estimate the PSFs by exploit differences in the distribution of intensity gradients within the two types of regions. These relatively simple image statistics allow compelling results in some cases, but they fail dramatically in others. One of the primary motivations of our work is to understand these failures and to develop stronger computational tools to eliminate them.

Modeling Blur
We use y[n] to represent an observed image, with n ∈ R 2 indicating the location of a pixel. Let x[n] be the corresponding latent sharp image, that is, the image that would have been captured in the absence of any blur or noise. The images x and y are assumed to be related by where z is sensor noise and k n is the spatially-varying blur kernel acting at pixel location n. We assume z to be white Gaussian noise: Our goal is to estimate the blur kernels k n . This problem is under-determined even when the kernel does not change from point to point, and allowing spatial variation adds considerable complexity. We need to make some assumptions to proceed, and one assumption we will make is that the kernel is constant in any local neighborhood. This turns out to be a reasonable assumption in most cases, but as we will see, it limits our ability to obtain localized boundaries based on blur information alone.

Sub-band Decomposition
Blur is naturally analyzed in the frequency domain, and when the blur is uniform over an image (k n = k), the convolution theorem lets us simplify the analysis by "diagonalizing" (1) with the Fourier transform: where ω ∈ [−π, π] 2 and Y (ω), X(ω), K(ω) and Z(ω) are Fourier transforms of x, y, k and z respectively. However, when the blur kernel varies spatially, the signals x[n] and y [n] are no longer related by convolution, and a global Fourier transform is of limited utility. Instead, we require a localized frequency representation. Let w[n] ∈ {0, 1} be a symmetric window function with limited spatial support, and let {f i } be a set of filters: with frequencies ω i ∈ R 2 . The choice of {ω i } i will depend on the window size, and it can be made to keep the filters orthogonal. Thus, we assume Applying these filters to an image x yields the corresponding responses . For any location n, the set of values {x i [n]} i can be imagined as the Fourier decomposition of a window centered at that location.
When k n is constant in neighborhood of size equal or greater than the support of w, (1) and (4) can be combined: This is similar to the spatially-uniform case (3)  , with the actual observed coefficient magnitudes for two windows containing the blurred and sharp edges (red and blue lines respectively, corresponding to the windows shown in (a)). We see that while the observed magnitudes match the "shapes" of their corresponding expected spectra, they are scaled differently based on the contrast of the edges. (c) An evaluation of the Gaussian and GSM prior-based likelihoods in (9) and (11) to classify both windows correctly as being blurred or not-blurred. A window is classified as blurred if the log of the ratio is above 0. We can see that while the GSM-based likelihood yields the correct classification for both edges, there is no single value of σ 2 g for which both windows are classified correctly, i.e. for which the blue and red curves are below and above 0 respectively. a slightly larger neighborhood-equal to the support of w plus that of k-be independent and identically distributed as N (0, σ 2 ). Then it is easy to show that the transform coefficients {x i [n]} i and {y i [n]} i are also distributed as zeromean Gaussians with variances given by Therefore, as an analogue to the diagonalization in (3), convolution with k independently scales the variance of each coefficient y i [n] so that it can be related directly to the corresponding coefficient x i [n] of the latent sharp image. Because of this analogy, we will refer to the set of transform coefficients of the blur kernel,

Prior on Sharp Images
Since the problem of estimating the blur kernels k n from the input image y is under-determined, we need a statistical prior model for the latent sharp image x to constrain the problem. We will then use this prior in conjunction with a MAP k estimation approach [17] to derive expressions for p({y i [n]} i |k): the likelihood that the blur kernel at n is k.

Gaussian
A natural choice for an image prior might be a Gaussian distribution on image gradients. Specifically, if ∇ is a derivative filter in a particular direction, Since (5) is linear in x we can write Combining (7) and (8) with the fact that the noise is white Gaussian (2), and using our expressions for variance (6), we can derive the following expression for the likelihood of the observed coefficients {y ∇ i [n]} i when k n = k: where σ 2 ki is the blur spectrum as per (6) and σ 2 zi are the filtered noise coefficients. These coefficients can be written as simple scaled versions of the noise variance, using reasoning similar to (6). A Gaussian prior has the virtue of simplicity and the likelihood in (9) can be computed easily in closed form. Moreover, despite the fact that empirical distributions of gradients in natural images have significantly heavier tails than a Gaussian distribution, the model has been used with some amount of success for blur estimation in the absence of spatial variation [17].
Unfortunately, it is far less useful when dealing with spatially-varying blur. This is illustrated in Fig. 2 using a toy one-dimensional "image" that contains a low-contrast edge that is not blurred, and a high-contrast edge that is blurred by a box filter k. We assume that the kernel k is known, and our task is to decide, by looking at the spectrum in each local window of the input image, whether that window was blurred by k or was not blurred at all (or equivalently, was blurred by an impulse). The top of part (b) in the figure shows the spectra of the two blur kernels (k and the impulse). Figure 2(c) shows the likelihood ratio for different values of the sharp image model parameter σ g , and it shows that the Gaussian-based likelihood model (9) is never able to classify both windows correctly. That is, we can choose the model parameter to correctly classify one or the other, but not both simultaneously. Intuitively, this results from the fact even if we can reasonably expect the mean square gradient values of an entire sharp image to be close to σ 2 g , the same is not true within different small windows of that sharp image whose statistics can change quite dramatically.
To gain further insight, we can look at the local spectra of the input image around the two edges, as depicted in the bottom of Fig. 2(b). We see that while the magnitudes of the spectra match the shapes of the two blur kernel spectra, their relative scales are very different. The classification fails, then, because the simple Gaussian-based likelihood model (9) involves absolute variance values, at a scale that is fixed and determined by the choice of our image prior model parameter σ 2 g . Viewed another way, the likelihood term is adversely affected by the difference in contrast between the two edges, and this prevents it from being able to make a decision based purely on how sharp they are.
In the next section, we introduce an alternate image prior model that specifically aims at capturing edge sharpness distinct from edge contrast. It is a heavy-tailed distribution that has the advantage of being reasonably tractable computationally within the sub-band representation.

Gaussian Scale Mixture
Instead of choosing a single Gaussian with variance σ 2 g , we model gradients in an image using an infinite mixture of zero-mean Gaussian distributions having a continuous range of variances. Additionally, we 'tie together' the scale parameters within each spatial neighborhood η. Formally, (10) where s is the scale parameter and p s (s) is a probability distribution on s which we choose to be uniform in the set S = (0, s max ). Note that conditioned on s, the image gradients in neighborhood η are i.i.d, and the marginal distribution of any single gradient x ∇ [n] has heavier tails than a Gaussian distribution. This is a slight variation of a Gaussian Scale Mixture (GSM), and GSM-based priors have been used previously to model natural images [21] for denoising [18] and deconvolution [23]. If we choose the size of the neighborhood η to be equal to or greater than the sum of the supports of the window w and blur kernel k, we can derive an expression for the likelihood analogous to the simple Gaussian case of the previous section: (11) Comparing this to (9), we see that the likelihood term integrates over all possible values of the variance (or scale) s in a window, as opposed to relying on a single choice σ 2 g . Returning to the toy example of Fig. 2, this has the effect of making the likelihood more agnostic to the absolute magnitudes of the local spectra, and allows it to latch on to the shape of the spectrum instead. As shown in Fig. 2(c), the GSM prior leads to a correct classification of the two edges.
One drawback of (11) is that it is significantly more expensive to compute due to the integration over S. However, we find that the integrand-the likelihood of coefficients conditioned on any particular sis a product of exponentials and typically behaves as an impulse on s. That is, the conditional likelihood typically has a sharp peak at an "optimal" choice of s and is negligible for all other values. So we can approximate it using The optimal valueŝ that maximizes the conditional likelihood in the above equation must satisfŷ and can be found using fixed point iterations. Convergence is typically quick for low values of σ 2 z . If the solutionŝ lies outside the set S, it can be appropriately clipped and then used to compute (12).

Detecting Motion
In the previous sections, we introduced a local blur cue that allows the efficient computation of a robust likelihood measure (12) for a given window in the image being blurred by a candidate kernel. We now describe an algorithm that uses this cue to simultaneously segment a motion-blurred region of an image and determine the blur kernel that affects this region. This is useful because the blur kernel contains direct information about the orientation and speed (relative to exposure time) of moving objects [1,2,5,6]. In the following, we assume that all of the motion-blurred regions of the input image are corrupted by the same kernel.
For a given image y[n], every pixel is either part of the stationary sharp "background" or the motion-blurred "foreground". Therefore, k n ∈ {k 0 , k m } where k 0 , chosen to either be an impulse (i.e. no blur at all) or a mild defocus blur, corresponds to the blur kernel acting on the stationary regions of the image , and k m is the motion-blur kernel. Our task is to estimate k m and to assign a label I[n] to every location, where I[n] = 0 if k n = k 0 and 1 otherwise.
The motion blur kernel k m is in turn assumed to be one of a discrete set of possible candidates, corresponding to horizontal or vertical box filters of certain lengths. (These correspond roughly to horizontal or vertical object motion with fixed velocity.) Formally, where b hl is a horizontal "box" filter of length (corresponding to number of pixels the object moved during exposure) l, i.e., b vl is a similarly defined vertical box filter, and {l 1 , . . . l L } is the set of lengths we wish to select from.  (16) where ∇ h , ∇ v are horizontal and vertical gradient filters, and {f ih } i , {f iv } i correspond to sub-band decompositions based on horizontal and vertical 1-D windows w h and w v . The first step is to select the motion blur kernel, k m , and in order to do so, we need to derive an expression for the likelihood p m (b) . = p(k m = b). If b is horizontal, then the coefficients y h i [n] should be explained either by b or k 0 , and the coefficients in the orthogonal direction y v i [n] should all be explained by k 0 (i.e. they are not affected by the motion blur). The converse is true if b is vertical, and this reasoning leads us to define

Selecting the Kernel
The blur kernel k m can then be chosen amongst the candidate set in (14) to maximize this likelihood p m (·).

Segmentation
Once the kernel k m has been chosen, the next step is to do a segmentation by assigning the labels I[n] for each location. While the relative likelihoods of the sub-band coefficients under k 0 and k m could be used to do the segmentation, best results are obtained when these are combined with statistical distributions for object and background color into an MRF model as used in traditional segmentation.
Similar to the approach in [19], we choose the labels l[n] as the solution to an energy minimization problem. We define a "Gibbs" energy function to capture the blur likelihoods, color distributions, and a spatial smoothness constraint on I[n] as (18) where θ f , θ b are the sets of parameters for the color distributions of the moving object and stationary background, C n and B n encode the likelihoods of I[n] from blur and color information respectively, α is a scalar parameter that controls the relative contribution of the two, and V n,n (·, ·) enforces smoothness by favoring the same label assignments at all pairs P of neighboring locations.
B n (I[n]) is defined in terms of the likelihoods from our blur model: The color of pixels in the moving object and background are each modeled as a (discrete) mixture of Gaussians, parameterized by θ f and θ b respectively. C n is then defined as where γ is a scalar that corresponds to the penalty for making different label assignments to neighboring pixels. The labeling I[n] can be initialized based on B n alone, and then we employ an iterative scheme to minimize the energy E in (18). In each iteration, we estimate the optimal parameters θ f and θ b using expectation-maximization (EM), and then assign I[n] using graph cuts [3].
Image B n C n B n + αC n Figure 3. Contributions of blur and color models to segmentation. While the blur model suffers from localization problems because of defined window sizes, the color model by itself is unable to distinguish between blurred and stationary objects that look similar. The two, however, compliment each other and when combined in an MRF model with smoothness constraints, give good quality segmentations (see Fig. 5).

Experiments
In this section, we test the algorithm with a variety of images, each captured with a point-and-shoot or cell-phone camera. Each image contains a single motion-blurred object, and we are interested in evaluating our method's ability to choose the correct orientation and length for the blur kernel and segment the blurred object.

Implementation Details
Both the horizontal and vertical sub-band transforms were defined in terms of windows of length W = 61. The filters {f ih } and {f iv } were then generated with ω i equal to the corresponding 1-D set of frequencies 2πu/W , u ∈ {1, . . . 15}. The gradient filters ∇ were defined simply as [−1, 1] (in the appropriate direction), i.e. the gradient values corresponded to the finite differences between neighboring pixels.
For the blur length, we searched over the discrete set of integers from 4 to 15 pixels. Larger lengths can be handled by downsampling the image to an appropriate resolution. For segmentation, the object and foreground RGB color vectors were modeled as mixtures of 4 and 6 Gaussians respectively. All choices of parameters (including σ 2 z , α and γ) were kept fixed for all images.
To evaluate the real-world applicability of the algorithm, a diverse set of images were captured using various devices, including a mid-level digital SLR, a consumer point-shoot Horizontal,4 Vertical, 7 Vertical, 7 Horizontal, 11 Figure 4. Crops of the blurred images from a few images with the corresponding detected blur length and orientation. The detected orientation matches the apparent motion direction, and images that are qualitatively more blurred have larger detected lengths.
camera and a cell phone cameras. Since the algorithm was run on the JPEG images, a tone scale correction was done, assuming a standard gamma of 2.2, to recover the linear intensities for computing the blur likelihoods. All images were scaled down to be roughly 550 pixels wide. These images and a MATLAB implementation of the algorithm can be downloaded from the project page at http://www.eecs.harvard.edu/˜ayanc/svblur/.

Results
We first qualitatively evaluate the ability of the algorithm to choose the correct orientation and length for the motion blur kernel k m . In Fig. 4, we show close-ups of moving objects (see Fig. 5 for full images) and the corresponding selected blur kernels. The algorithm correctly determines whether the motion is horizontal or vertical, and for objects that appear to have more significant blur it selects larger kernel lengths. Figure 5 shows the full segmentation results for a set of images, as well as the relative likelihoods from the blur model alone. We find that the algorithm does well on this diverse set of real world images, despite approximate assumptions about noise variance, gamma correction, etc. It is also able to detect the blurred regions even in cases of relatively minor motion (see images 2 and 5) and is fairly robust even in cluttered backgrounds (see image 4). In some cases however, some regions are incorrectly marked blurred because of color similarities to the blurred object (image 2), or erroneous estimates from B n (image 4, where the blur model "sees" soft shadows as blurred edges). Supplemental material on the project website linked above contains more detailed results, including results on other images.
Our MATLAB implementation of the algorithm takes roughly 4 minutes to compute the sub-band coefficients of an image, compute the likelihoods under all candidate blur kernels, choose k m , and evaluate the blur energy B n . The full segmentation, which includes iterations to estimate the color distributions using EM and label assignments using graph cuts, takes an additional 12 minutes. These execution times were recorded for a 600 × 450 image using a machine with a 2.8GHz Pentium processor and 1GB of RAM.

Conclusion
We propose a new local cue for analyzing spatiallyvarying blur. It involves a sub-band decomposition to isolate the "local frequency" components of an image, and a prior image model based on a Gaussian Scale Mixture to handle the variation in gradient statistics among local windows of a single image. Combined, these allow one to efficiently compute the likelihood of a particular window in an image being blurred by a candidate kernel, and this likelihood conveniently incorporates a preference for sharp edges without being adversely affected by the natural variation in edge contrast that occurs in a typical image.
We use the proposed likelihood measure to determine the orientation and degree of motion in images with moving objects, and by combining them with color information, we show that one can obtain reasonable segmentations of the objects. Our segmentations are hard, and an immediate direction to explore is computing soft mattes instead. The boundaries of moving objects are linear combinations of a blurred foreground and a sharp background, and it is likely that the proposed blur machinery can be used to enhance reasoning about such mattes that would otherwise be obtained using color information alone.
More broadly, while the proposed tools have been used to analyze motion blur, they are general enough to handle any instance of spatially-varying blur. For example, for defocus blur where the kernel changes with scene depth, one can imagine using the framework in [16] but doing away with the requirement for special capture conditions by using the proposed likelihood measure in (12) instead of cues from a coded aperture.