Compute the most background & common color in an image

[renchap]

We recently added support for libvips in Mastodon, to replace our ImageMagick usage.

We needed a way to extract the background color for images, as well as the most used color, because we adapt the viewing UI to those.

The implementation is here: https://github.com/mastodon/mastodon/blob/main/lib/paperclip/color_extractor.rb#L76

You also have the IM implementation in the same file for reference.

We based this on a comment / gist from @jcupitt but we found some small issues with edge cases. You can see the discussion here for more context: mastodon/mastodon#30090 (comment)

If you are interested in the whole vips implementation, you can look at this PR: mastodon/mastodon#30090
Based on advice by @lovell, we switched to ffmpeg to process animated GIFs, as vips do not support them properly at the moment.

Is there a better / more efficient way to write this code?

[jcupitt]

Hi @renchap,

Yes, we've been following that PR with interest. Nice work! Would you like one of us to look through the code for possible improvements?

We've added a "developer checklist" to the 8.16 docs:

https://github.com/libvips/libvips/blob/master/doc/Developer-checklist.md

It might be worth a quick look.

I'll have a look at your background and dominant colour code.

we switched to ffmpeg to process animated GIFs, as vips do not support them properly at the moment.

libvips has had good GIF support since 8.13, I think. Though ffmpeg is a fine choice of course.

[renchap]

Would you like one of us to look through the code for possible improvements?

Sure, this is always appreciated!

It looks like there's a PR at mastodon/mastodon#30569 to upgrade libvips from 8.10.5 (December 2020) to the latest 8.15.2, which would then allow GIF resizing/thumbnailing without *magick.

We only support VIPS 8.13, because we want to block unsafe loaders.

This PR is to update our official container image from the stock Debian package (8.14 with too much dependencies) to 8.15 with only the dependencies we want.

we switched to ffmpeg to process animated GIFs, as vips do not support them properly at the moment.

libvips has had good GIF support since 8.13, I think. Though ffmpeg is a fine choice of course.

Not for animated GIFs I think? We need to handle those, and the only way we found was to resize every frame, then reconstruct the image. libvips/libvips#2668 is still open for resizing animated GIFs.

[jcupitt]

Not for animated GIFs I think?

It should work fine -- by default it'll just do frame zero, but pass n=-1 and it'll do all frames.

john@banana ~/pics $ /usr/bin/time -f %M:%e convert 3198.gif -resize 128x128 x2.gif
170232:10.48
john@banana ~/pics $ /usr/bin/time -f %M:%e vipsthumbnail 3198.gif[n=-1] -o x.gif --size 128
56576:2.21
$ /usr/bin/time -f %M:%e ffmpeg -hide_banner -v warning -i 3198.gif -filter_complex "[0:v] scale=128:-1:flags=lanczos,split [a][b]; [a] palettegen=reserve_transparent=on:transparency_color=ffffff [p]; [b][p] paletteuse" x3.gif
79372:0.59
john@banana ~/pics $ ls -l x*.gif
-rw-rw-r-- 1 john john 1062852 Jun  7 13:55 x2.gif
-rw-rw-r-- 1 john john  974588 Jun  7 13:59 x3.gif
-rw-r--r-- 1 john john 1193725 Jun  7 13:55 x.gif

Looking at the output gifs, libvips is probably the best quality, though ffmpeg is similar. imagemagick is noticeably worse. ffmpeg has the smallest output size, libvips has marginally the lowest memory use, ffmpeg is the fastest by a good distance.

libvips is reoptimising the palette, maybe ffmpeg is not and that explains the difference in CPU time? But I've not checked.

[jcupitt]

The n=-1 feature works for all animated images, so webp etc. too. Hopefully for animated PNG soon.

[Gargron]

Hi @jcupitt, resize works on animated GIFs with n=-1, but not when the crop option is used.

[jcupitt]

Ah, yes, that's true, for crop you'd need to split to pages, crop, resize and rejoin, as you say.

[jcupitt]

but we found some small issues with edge cases.

For distinguishing blues, you need to extract that (x, y) pixel as a vector and run max a second time. I'll make an example.

Something else you could do to improve it would be to blur the image slightly before doing the binning. This will make the histogram less noisy and should mean a more stable result. But the improvement would probably be small in practice.

You can run this in sequential mode, that would help too.

What value do you typically use for BINS?

[ClearlyClaire]

We're currently using BINS = 10, scanning the vector to extract multiple matches is definitely possible, but it would also be pretty awkward, as we'd have to remember which colors we've already selected.

[jcupitt]

Hi @ClearlyClaire, nice to meet you!

Now I look at the code more carefully, you're already doing this -- you have getpoint() to get the pixel vector from the histogram image, then find_index to find the z (blue) which contains the maximum value. So I think your code is working.

I made a tiny test program:

#!/usr/bin/ruby

require "vips"

BINS = 16

def rgb_from_xyv(image, x, y, v)
  pixel = image.getpoint(x, y)
  z = pixel.find_index(v)
  r = (x + 0.5) * 256 / BINS
  g = (y + 0.5) * 256 / BINS
  b = (z + 0.5) * 256 / BINS
  [r, g, b]
end

def palette_from_image(image)
  histogram = image.hist_find_ndim(bins: BINS)
  _, colors = histogram.max(size: 10, out_array: true, x_array: true, y_array: true)

  colors['out_array'].map.with_index do |v, i|
    x = colors['x_array'][i]
    y = colors['y_array'][i]

    rgb_from_xyv(histogram, x, y, v)
  end.reverse
end

image = Vips::Image.new_from_file(ARGV[0], access: :sequential)
hist = palette_from_image(image)

puts("hist = #{hist}")

And I see:

$ ./mastodon.rb ~/pics/k2.jpg
hist = [[56.0, 56.0, 72.0], [8.0, 8.0, 8.0], [40.0, 40.0, 72.0], [248.0, 248.0, 248.0], [40.0, 40.0, 56.0], [56.0, 56.0, 56.0], [72.0, 56.0, 72.0], [56.0, 40.0, 72.0], [40.0, 40.0, 24.0], [232.0, 248.0, 248.0]]

ie. the dominant colour is [56.0, 56.0, 72.0], which seem right, from stepping though the process.

I tested with:

$ vips hist_find_ndim k2.jpg x.v --bins 16
$ vips max x.v --size 10 --out-array --x-array --y-array
36250 38784 41021 47482 54575 57936 60979 75699 95407 232563 
14 2 3 4 3 2 15 2 0 3 
15 2 2 3 3 2 15 2 0 3 
232563.000000

Then looked through the histogram image with vipsdisp (it can display these things at least semi-sensibly, and show all the values in the file).

https://github.com/jcupitt/vipsdisp

nip2 can be useful for developing libvips code, but it's a big, complicated thing and hard to get to grips with. I'm trying to make a simpler gtk4 version now, but it's not ready yet.

https://github.com/libvips/nip2

[ClearlyClaire]

Hi!
Consider the following (highly artificial) image:

$ ./mastodon.rb test.png
hist = [[8.0, 8.0, 8.0], [248.0, 104.0, 8.0], [248.0, 104.0, 8.0], [248.0, 104.0, 8.0], [248.0, 104.0, 8.0], [104.0, 104.0, 8.0], [104.0, 104.0, 8.0], [104.0, 104.0, 8.0], [104.0, 104.0, 8.0], [8.0, 8.0, 24.0]]

You can see that out of the 9 most present colors, only 3 are represented, and 2 are repeated multiple times because they happen to have exactly the same frequency as other colors which only differ in the blue component.

[jcupitt]

🤦 I see what you mean, we could have one pixel containing two maxima.

You could add all v, r, g, b for a pixel, then sort by v and take the top 10. Perhaps:

#!/usr/bin/ruby

require "vips"

BINS = 16

def rgb_from_xyv(image, x, y)
  pixel = image.getpoint(x, y)
  pixel.map.with_index do |v, z|
    r = (x + 0.5) * 256 / BINS
    g = (y + 0.5) * 256 / BINS
    b = (z + 0.5) * 256 / BINS
    [v, r, g, b]
  end
end

def palette_from_image(image)
  histogram = image.hist_find_ndim(bins: BINS)
  _, colors = histogram.max(size: 10, out_array: true, x_array: true, y_array: true)

  maxima = colors['out_array'].map.with_index do |v, i|
    x = colors['x_array'][i]
    y = colors['y_array'][i]
    rgb_from_xyv(histogram, x, y)
  end.flatten(1).sort { |a, b| b[0] - a[0] }.slice(0, 10)
end

image = Vips::Image.new_from_file(ARGV[0], access: :sequential)
hist = palette_from_image(image)

puts("hist = #{hist}")

[ClearlyClaire]

Yeah, that is a bit cumbersome but I think this would work, after deduplication. Thanks!

[jcupitt]

@ClearlyClaire I had a facepalm moment yesterday -- a very simple fix is to use bandunfold to unfold the bands dimension into the x dimension. This takes a 3x3 RGB image like this:

RGB RGB RGB
RGB RGB RGB
RGB RGB RGB

And unfolds it to a 9x3 mono image like this:

R G B R G B R G B 
R G B R G B R G B 
R G B R G B R G B 

Now you can run max on the mono image and it won't miss anything. Use x % 3 and x // 3 to turn the x position back into a bin number.

#!/usr/bin/ruby

require "vips"

BINS = 16

def palette_from_image(image)
  histogram = image.hist_find_ndim(bins: BINS).bandunfold()
  _, colors = histogram.max(size: 10, out_array: true, x_array: true, y_array: true)

  maxima = colors['out_array'].map.with_index do |v, i|
    x = colors['x_array'][i]
    y = colors['y_array'][i]
    
    r = BINS / 2 + BINS * (x / BINS)
    g = BINS / 2 + BINS * y
    b = BINS / 2 + BINS * (x % BINS)

    [v, r, g, b]
  end.sort { |a, b| b[0] - a[0] }
end

image = Vips::Image.new_from_file(ARGV[0], access: :sequential)
hist = palette_from_image(image)

puts("hist = #{hist}")

Quite a bit less crazy.

[ClearlyClaire]

Oh, I wasn't aware of bandunfold! This is a really nice simplification, thank you!

[jcupitt]

Yes, it's nice because it doesn't move any pixels around, just changes the way they are addressed. So it's a "free" operation (just a pointer copy).