How is the photoshop cutout filter implemented?

Question

Photoshop has a lot of cool artistic filters, and I'd love to understand the underlying algorithms.

One algorithm that's particularly interesting is the Cutout filter (number 2 at the link above).

It has three tunable parameters, Number of Levels, Edge Simplicity, and Edge Fidelity. Number of levels appears to drive a straightforward posterization algorithm, but what the other sliders do technically eludes me.

I would think that they're doing something related to Vornoi diagrams or k-means partitionion, but poking around on wikipedia hasn't resulted in anything that maps obviously to what Photoshop is doing, especially considering how fast the filter renders itself.

Is there any source for technical descriptions of the Photoshop filters? Alternatively, do you have any thoughts about how this particular filter might be implemented?

Answer 1

From tinkering with it I've found out that:

• it's deterministic
• it doesn't do any kind of pixel based posterization to achieve final effect
• it probably doesn't use any kind of pixel based edge detection, it seems to work rather with areas then edges.
• it calculates the shapes closed polygons to draw (some of the polygon edges might overlap with image edges).
• when the edges of polygons are known then color of each area enclosed in edges (not necessarily belonging to one polygon) is colored with average color of pixels of original image that area covers.
• edge of polygon can intersect with itself. Especially visible for high edge simplicity.
• as 'line simplicity' drops, the number of polygon edges increases, but also number of polygons increases.
• edge fidelity influences line polygon edge count but does not influence polygon count
• high edge fidelity (=3) causes single polygon to have very long and very short edges at the same time, low fidelity (=1) causes single polygon to have all edges roughly the similar length
• high edge simplicity and low edge fidelity seem to prefer polygons anchored at edges of image, even at cost of sanity.

Altogether it looks like simplified version of Live Trace algorithm from Adobe Illustrator that uses polygons instead of curves.

... or maybe not.

Answer 2

Maybe not exactly what you are looking for, but if you like knowing how filters work, you could check out the source code of GIMP. I can't say if GIMP has an equivalent of cutout filter you mentioned, but it's worth taking a look if you are truly interested in this field.

Answer 3

The number of levels seems to resemble how cell-shading is done and this is how I'd implement that part in this case: you simply take this histogram of the image and divide it into the "No. of levels" amount of sections then calculate an average for each section. Each color in the histogram will then use that average in stead of their original color.

The other two parameters require some more thinking but 'Edge simplicity' seems to detonate the number of segments the shapes are build up off. Or rather: the number of refinements applied to some crude Image Segmentation Algorithms. The fidelity slider seems to do something similar; it probably controls some kind of threshold for when the refinements should take place.

This might help

Answer 4

Edge detection is usually a Sobel or Canny filter then the edges are joined together with a chain code.
Look at something like the OpenCV library for details

Answer 5

I'm not sure it could be some kind of cell shading, but it also looks like a median filter with a very big kernel size or which was applied several times.

The edge simplicity/fidelity might be options which help decide whether or not to take in account an adjacent pixel (or one which falls inside the kernel) based on difference of color with the current pixel.

Answer 6

I imagine it's probably some thresholding, edge-detection (Sobel/Canny/Roberts/whatever) and posterisation.