Efficient way to determine whether a Vix.Vips.Image is a single color?

Questions / Help
1

I have the following code to check whether a certain Vix.Vips.Image consists only of a single colour:

defmodule Spritesheet do
  def single_color_tile?(%Vix.Vips.Image{} = image) do
    initial_colour = Image.get_pixel!(image, 0, 0) |> dbg()
    coordinates =
      for x <- 0..(Image.width(image) - 1), y <- 0..(Image.height(image) - 1), do: {x, y}
    Enum.all?(coordinates, fn {x, y} -> Image.get_pixel!(image, x, y) == initial_colour end)
  end
end

It works, but it is slow: Checking a 128x128 px image takes a few seconds. The following testcases need 7 seconds to finish on my machine.

  describe "single_color_tile?" do
    test "all transparent black" do
      assert Spritesheet.single_color_tile?(Image.new!(128, 128, color: [0, 0, 0, 0]))
    end

    test "all solid green" do
      assert Spritesheet.single_color_tile?(Image.new!(128, 128, color: [0, 255, 0, 255]))
    end

    test "red solid circle on transparent background" do
      refute Spritesheet.single_color_tile?(
               Image.new!(16, 16, color: [0, 0, 0, 0])
               |> Image.Draw.circle!(7, 7, 7, color: [255, 0, 0, 255])
             )
    end
  end

I was initially quite hopeful that I could trick Image.dominant_color into computing this, but I probably missunderstand the purpose of that function: For me it only returns colours that are not part of the given image:

> Image.new!(1, 1, color: [0, 0, 0, 0])  |> Image.dominant_color!(bins: 1) 
[128, 128, 128]
> Image.new!(1, 1, color: [0, 0, 0, 0])  |> Image.dominant_color!(bins: 16)
[8, 8, 8]
> Image.new!(1, 1, color: [0, 0, 0, 0])  |> Image.dominant_color!(bins: 255)
[1, 234, 1]

Is there a builtin Image function that I am overlooking? Or a way to access the raw image data for more efficient iteration?

2

Not sure if this would be faster, but you could create a separate image in the color of that first pixel and then run the diffing apis of the image library.

3

A few seconds for 16,000 values seems kinda slow even for Elixir. Why is that function so slow?

The docs actually specifically say not to loop over it and to use extract_area instead.

There’s probably also a function to just dump the entire thing into a list. Or better operate over the raw pixel data as a binary? (I don’t know this library.)

4

The docs actually specifically say not to loop over it and to use extract_area instead.

extract_area returns an image, so I would be back at square one.

5

Oh I see, well that’s not very helpful!

Seems there’s an Image.write_to_tensor/1 function which should allow you to get a binary with a known format. Then you can pattern match through the binary and check the raw pixels. I imagine that would be significantly faster.

6

Generating a second image is an interesting idea. It seems that I can use the :ae metric of compare to figure whether the images are pixel perfectly identical.

I would normally expect this to be slower, as the vast majority of my images will not be a single color and Enum.all? can return early. But as the limiting factor seems to be the number of function calls … I am curious and will report back.

7

Returning early has no benefit if operations are faster batched than iterated. The overhead of doing many NIF calls is one you want to avoid.

The tensor option might be interesting though as Nx might have means of doing the “check if all are the same” code you currently have in elixir for a tensor, again to apply as a single operation.

1 Like
8

I didn’t have the time to dig into the tensor way yet, but misusing my testcases as a benchmark yields “this might be good enough” type of results:

  * test single_color_tile?(img, get_pixel) all transparent black (1598.5ms) [L#166]
  * test single_color_tile?(img, get_pixel) all solid green (1592.9ms) [L#170]
  * test single_color_tile?(img, get_pixel) red solid circle on transparent background (4.8ms) [L#174]
  * test single_color_tile?(img, image_compare) all transparent black (5.1ms) [L#166]
  * test single_color_tile?(img, image_compare) all solid green (4.0ms) [L#170]
  * test single_color_tile?(img, image_compare) red solid circle on transparent background (2.4ms) [L#174]
9

Image.histogram sounds promising; you’d compute it and then check that only one “bin” of the result in each band is nonzero.

I say “promising” because the docs say it returns a 255x255 image but don’t give an example of how that’s computed…

1 Like
10

I suspect this is the pragmatic way and probably how I would approach it. Here’s an example:

def single_color?(image) do
  target_color = Image.get_pixel!(image, 0, 0)
  diff = Image.Math.equal!(image, target_color)
  Image.Math.min!(diff) == Image.Math.max!(diff) 
end

This takes 2ms on my aging iMac Pro for an image of 128x128 and 4ms for an image of 512x512 despite that being 16 times more pixels. It’s 39ms for a 5000x5000 image.

Per @akash-akya solution below (where his all? operator also uses libvips’s min/1 and max/1 under the covers), you could also write:

def single_color?(image) do
  use Image.Math

  target_color = Image.get_pixel!(image, 0, 0)
  Image.Math.min!(image == target_color) == 255.0
end
3 Likes
12

I’ll look into this. It may be a side effect of either (a) the underlying histogram used to drive this process or (b) the affect of the alpha band in your source image. Here’s some examples that appear to work correctly so maybe it’s an edge case when the color is 0?

iex> Image.new!(1, 1, color: [1, 1, 1])  |> Image.dominant_color!(bins: 256)
[1, 1, 1]
iex> Image.new!(1, 1, color: [3, 3, 3])  |> Image.dominant_color!(bins: 256)
[3, 3, 3]
iex> Image.new!(1, 1, color: [128, 128, 128])  |> Image.dominant_color!(bins: 256)
[128, 128, 128]

Its slow primarily because each call to Image.get_pixel!/3 results in a NIF call.

Secondly, images in libvips are demand-driven which means that transformation pipelines are executed as required to generate the resulting pixels. This is very time and space efficient overall - but it does mean there is no guarantee that all pixels are rendered and in memory (although that can be forced when required). Thats likely not the issue here thought - the first point will dominant.

It’s useful to think of images as being like lazy tensors. Set operations will win every time. libvips has a lot of optimised code (pipelining, SIMD instructions, …) for these.

3 Likes
13

Yes, thats definitely one approach. You still need to check each of the other bins to check if there are no values. And you need to select the right number of bins - which would depend on the colourspace of the source image.

Thats one reason why I would use the solution I proposed: its easier to support images of different colourspaces.

I’ll see how I can improve the documentation for Image.histogram/2 as well, thanks for the prompt.

4 Likes
14

FWIW I can’t really fault Image for not having more detail, the docs for the underlying VIPS function are equally vague. The best mention I could find of what shape hist_find returns was in a side document that still leaves the definition of “a histogram” as “1xn OR nx1”

1 Like
15

Libvips has highly efficient relational operations. Vix has these as normal operation, as well as as operators which are much easier to read and write.

alias Vix.Vips.{Operation, Image}

# Selectively import needed operators for cleaner syntax
use Vix.Operator, only: [==: 2, all?: 2]

{:ok, img} = Image.new_from_file("image.jpg")
reference_pixel = Image.get_pixel!(img, 0, 0)

if all?(img == reference_pixel, true) do
  IO.puts("All pixels match reference")
else
  IO.puts("Image contains different pixels")
end

Performance: ~50ms for a 5000Ă—5000 JPEG.

These operations short-circuit on first mismatch, making them extremely efficient for images that aren’t uniform. The comparison stops immediately when a different pixel is found rather than scanning the entire image.

6 Likes