How to detect if an image is pixelated

Question

There is a question like this asked on SO earlier: Detecting a pixelated image in python and also on quora

I'm trying to find out whether an image uploaded by a user can be detected as 'pixelated'. By pixelated I mean images like these: In my case I don't have access to the original (non-pixelated) version.

My approach:

Not sure how effective this approach would be but if I could get RGB of each pixel in the image and then compare it to its neighbors to see if they are similar then I could detect that the image is pixelated? I can get the RGB of pixels but don't know how to go about comparing them to their neighbors.

Are there algorithms for doing something like this available already? Are there some other approaches I could take? I'm not bound to any specific language.

Answer 1

This is going to be problematic, there are many ways to pixelate images. Even using a single method, you can have it arbitrarily rotated. In theory this rotation shouldn't affect methods like Hough, but in practice it does because you cannot have perfectly rasterized lines at arbitrary angles. My approach is simplistic, it is not going to work every time (it will probably fail most of time), but you really have to better define what you want to do. Are you going to tell the user: "hey, your image is pixelated, I don't want it" ? What you want to do is not clear, the scope is not clear too.

So here is the approach. Split your image into its color channels, your example one is a palleted GIF but that can be easily seen as a RGB image. If it is a grayscale then you mostly like have one channel, that is fine. If your image have an alpha channel, either blend it or ignore it. With this separated color channels, apply a morphological gradient in each one, binarize each one by Otsu (since it is automatic, relatively good, easily available), and combine the n binary channels into one by adding them. The morphological gradient will give a high response for strong edges (including noise), and the binarization step will keep them. Now you remove components that are too small and do a thinning to get one-pixel-wide edges. Here is what we get with your example image after these steps:

f = Import["http://www.caughtinthefire.com/wp-content/uploads/2009/03/\
     fireworks-pixelate-02.gif"]
split = Binarize[ImageSubtract[Dilation[#, 1], Erosion[#, 1]]] & /@ 
  ColorSeparate[f, "RGB"]
thin = Thinning[SelectComponents[Fold[ImageAdd, split[[1]], split[[2 ;;]]], 
  "Count", # > 10 &]]

Now we proceed to detect the lines in this thinned binary image. The expectation is that it will form many rectangular areas when the image is pixelated, but there is no guarantee that we can actually form these rectangular areas. Supposing we can, consider each of these areas as a connected component. Then if we perform a simply component analysis as: if the ratio between the area of its convex hull and the area of its bounding box is greater than some value, then this area is a rectangular area. If we end up with many rectangular areas, then you say your image is pixelated (but actually there is no confidence on saying such thing). Next we see the original image with the detected lines overlaid, at right we see the connected components (points that are not black) that remain after considering the analysis mentioned using a ratio > 95%. In this case, there were 542 connected components in total, which were reduced to 483. This means nearly 90% of the components are rectangular. You could also take into consideration the area of the remaining components, or combine this analysis with other ones, but I'm not doing this here.

lines = ImageLines[thin, 0.05, Method -> "RANSAC"];
Show[f, Graphics[{Thick, Blue, Line /@ lines}]] (* The left image above. *)
blank = Image[ConstantArray[255, Reverse@ImageDimensions[thin]]];
blankcc = ImagePad[Binarize[Image[Show[blank, 
  Graphics[{Thick, Black, Line /@ lines}]]]], 1, Black]
ccrect = SelectComponents[MorphologicalComponents[blankcc], {"BoundingBoxArea", 
  "ConvexArea"}, #2/#1 > 0.95 &];
Colorize[ccrect, ColorFunction -> "DarkRainbow"] (* The right image above. *)

This is your indication of "pixelated".

Here are other results considering other images. This is always a sequence of three images in this order: original, result as above without changing anything, result as above after changing the threshold for line detection.

Everything detected as rectangular. But a threshold of 0.05 for line detection is too high here, after reducing it to 0.01 we get a better division of the components.

Next we consider an image which is outside of what we expect, so we end up with very few components. There is no threshold for line detection that will give a greater amount of rectangular components, so the third image is empty (or fully black, since no component remains).

Lastly, a pixelation where the squares are rotated. The process for generating the following image might have been different than the one used in the example image, but I have no idea since I'm not the author. The right image is the result of raising the line threshold to 0.08. The problem here is that the regions are relatively large, which I wouldn't consider for detection of pixelated images.

Answer 2

Some approaches:

1) Implement canny or other edge detection and vary the edge threshold to see if the result is a grid. A grid can be detected by applying Hough line detector to the resulting edge image. See (2) below.

2) (This is really thresholding the image before edge detection; also suggest smoothing image with median filter or other noise removal filter). Scan from left to right and at each pixel color change assign either black or white to the pixel. Continue with black/white until the color changes and toggle from black to white or white to black. If pixelated you will end up with a grid like image. You can run a standard line detection on the iamge (which you can do for 1 as well) and see if the slopes of the resulting lines are vertical and parallel and if the lines are fairly equidistant. There are sample line detection algorithms on the internet (even Java implementations).

This website has references to line detection and edge detection algorithms.

EDIT: In response to question from mmgp (+1 for the challenge, I like that!), this is what I did with the sample image in the question: 1) Edge detection 2) Gray-scale 3) Hugh-transform (high threshold) Attached is the hugh-transform output. By evaluating all lines that have horizontal/vertical slope and computing distance between them, a grid pattern can be discerned. This does not automatically mean the image is pixelated (a chess board would show up as pixelated). There can be false positives.

Answer 3

Here is a fairly simple approach which could work:

1. Subtract the image from a copy translated by 1 pixel in both x, and y.
2. Sum the pixels in columns and rows (I only show columns below).
3. Figure out the frequency and standard deviation of the peak positions.
4. If the standard deviation is below some threshold then the image is pixellated.

Your image after step 1:

Showing a clear grid pattern. Now if we sum the pixels columnarly we get:

Now if we can figure out the regularity of the peak column spacing, and use this as a threshold to determine if the image is pixelated or not.

Here is some quick and rough python code, to give an idea of an approach:

import numpy as np
import Image, ImageChops

im = Image.open('fireworks-pixelate-02.gif')    
im2 = im.transform(im.size, Image.AFFINE, (1,0,1,0,1,1))
im3 = ImageChops.subtract(im, im2)
im3 = np.asarray(im3)
im3 = np.sum(im3,axis=0)[:-1]
mean = np.mean(im3)
peak_spacing = np.diff([i for i,v in enumerate(im3) if v > mean*2])
mean_spacing = np.mean(peak_spacing)
std_spacing = np.std(peak_spacing)
print 'mean gap:', mean_spacing, 'std', std_spacing

Output:

mean gap: 14.6944444444 std: 3.23882218342

Low std = pixelated image

This unpixelated image:

Has a corresponding graph like this:

yeilding a much higher std:

mean gap: 16.1666666667 std: 26.8416136293

Note here, that the "mean gap" is meaningless becuase the std is much higher.

Hopefully this is enough to illustrate that this approach could work quite nicely.