Force an Average on an Image

Question

Write a program that takes in a standard truecolor image and a single 24-bit RGB color (three numbers from 0 to 255). Modify the input image (or output a new image with the same dimensions) such that its average color is exactly the single color that was input. You may modify the pixels in the input image in any way you like to achieve this, but the goal is to make the color changes as visually unnoticeable as possible.

The average color of an RGB image is really a set of three arithmetic means, one for each color channel. The average red value is the sum of the red values across all the pixels in the image divided by the total number of pixels (the image area), rounded down to the nearest integer. The green and blue averages are calculated in the same way.

This Python 2 (with PIL) script can compute the average color of most image file formats:

from PIL import Image
print 'Enter image file'
im = Image.open(raw_input()).convert('RGB')
pixels = im.load()
avg = [0, 0, 0]
for x in range(im.size[0]):
    for y in range(im.size[1]):
        for i in range(3):
            avg[i] += pixels[x, y][i]
print 'The average color is', tuple(c // (im.size[0] * im.size[1]) for c in avg)

^{(There are similar average color programs here, but they don't necessarily do the exact same calculation.)}

The main requirement for your program is that for any input image, its corresponding output's average color must exactly match the color that was input - as judged by the Python snippet or some equivalent code. The output image must also have the exact same dimensions as the input image.

So you could technically submit a program that simply colors the entire input the specified average color (because the average would always be that color), but this is a popularity contest - the submission with the highest number of votes will win, and such a trivial submission will not get you many upvotes. Novel ideas like taking advantage of quirks in human vision, or shrinking the image down and drawing a colored border around it will (hopefully) get you votes.

Note that certain combinations of average colors and images necessitate extremely noticeable color changes. For example, if the average color to match were black (0, 0, 0), any input image would need to be made completely black because if any pixels had non-zero values, they would make the average non-zero as well (barring round-off errors). Keep such limitations in mind when voting.

Test Images

Some images and their default average colors to play around with. Click for full sizes.

A. average (127, 127, 127)

^{From fejesjoco's Images with all colors answer. Found original on his blog.}

B. average (62, 71, 73)

^{Yokohama. Provided by Geobits.}

C. average (115, 112, 111)

^{Tokyo. Provided by Geobits.}

D. average (154, 151, 154)

^{Escher's Waterfall. Original.}

E. average (105, 103, 102)

^{Mount Shasta. Provided by me.}

F. average (75, 91, 110)

^{The Starry Night}

Notes

• The exact input and output formats and image file types your program uses does not matter much. Just make sure it is clear how to use your program.
• It is probably a good idea (but not technically a requirement) that if an image already has the goal average color, it should be output as is.
• Please post test images with the average color input as either (150, 100, 100) or (75, 91, 110), so voters can see the same inputs across different solutions. (Posting more examples than this is fine, even encouraged.)

Answer 1

Python 2 + PIL, simple colour scaling

from PIL import Image
import math

INFILE = "street.jpg"
OUTFILE = "output.png"
AVERAGE = (150, 100, 100)

im = Image.open(INFILE)
im = im.convert("RGB")
width, height = prev_size = im.size
pixels = {(x, y): list(im.getpixel((x, y)))
          for x in range(width) for y in range(height)}

def get_avg():
    total_rgb = [0, 0, 0]

    for x in range(width):
        for y in range(height):
            for i in range(3):
                total_rgb[i] += int(pixels[x, y][i])

    return [float(x)/(width*height) for x in total_rgb]

curr_avg = get_avg()

while tuple(int(x) for x in curr_avg) != AVERAGE:
    print curr_avg   
    non_capped = [0, 0, 0]
    total_rgb = [0, 0, 0]

    for x in range(width):
        for y in range(height):
            for i in range(3):
                if curr_avg[i] < AVERAGE[i] and pixels[x, y][i] < 255:
                    non_capped[i] += 1
                    total_rgb[i] += int(pixels[x, y][i])

                elif curr_avg[i] > AVERAGE[i] and pixels[x, y][i] > 0:
                    non_capped[i] += 1
                    total_rgb[i] += int(pixels[x, y][i])

    ratios = [1 if z == 0 else
              x/(y/float(z))
              for x,y,z in zip(AVERAGE, total_rgb, non_capped)]

    for x in range(width):
        for y in range(height):
            col = []

            for i in range(3):
                new_col = (pixels[x, y][i] + 0.01) * ratios[i]
                col.append(min(255, max(0, new_col)))

            pixels[x, y] = tuple(col)

    curr_avg = get_avg()

print curr_avg

for pixel in pixels:
    im.putpixel(pixel, tuple(int(x) for x in pixels[pixel]))

im.save(OUTFILE)

Here's a naïve approach which should serve as a good baseline. At each iteration, we compare our current average with the desired average, and scale the RGB of each pixel by the according ratio. We have to be a bit careful though, for two reasons:

• Scaling 0 still results in 0, so before we scale we add something small (here 0.01)

• RGB values are between 0 and 255, so we need to adjust the ratio accordingly to make up for the fact that scaling capped pixels doesn't do anything.

The images save as PNG because saving as JPG seems to mess up the colour averages.

Sample output

(40, 40, 40)

(150, 100, 100)

(75, 91, 110), Starry Night palette

Answer 2

C++, gamma correction

This does a brightness adjustment of the image using a simple gamma correction, with the gamma value determined separately for each component to match the target average.

The high level steps are:

1. Read image and extract histogram for each color component.
2. Perform a binary search of the gamma value for each component. A binary search is performed on the gamma values, until the resulting histogram has the desired average.
3. Read the image a second time, and apply the gamma correction.

All image input/output uses PPM files in ASCII. Images were converted from/to PNG using GIMP. The code was run on a Mac, image conversions were done on Windows.

Code:

#include <cmath>
#include <string>
#include <vector>
#include <sstream>
#include <fstream>
#include <iostream>

static inline int mapVal(int val, float gamma)
{
    float relVal = (val + 1.0f) / 257.0f;
    float newRelVal = powf(relVal, gamma);

    int newVal = static_cast<int>(newRelVal * 257.0f - 0.5f);
    if (newVal < 0)
    {
        newVal = 0;
    }
    else if (newVal > 255)
    {
        newVal = 255;
    }

    return newVal;
}

struct Histogram
{
    Histogram();

    bool read(const std::string fileName);
    int getAvg(int colIdx) const;
    void adjust(const Histogram& origHist, int colIdx, float gamma);

    int pixCount;
    std::vector<int> freqA[3];
};

Histogram::Histogram()
  : pixCount(0)
{
    for (int iCol = 0; iCol < 3; ++iCol)
    {
        freqA[iCol].resize(256, 0);
    }
}

bool Histogram::read(const std::string fileName)
{
    for (int iCol = 0; iCol < 3; ++iCol)
    {
        freqA[iCol].assign(256, 0);
    }

    std::ifstream inStrm(fileName);

    std::string format;
    inStrm >> format;
    if (format != "P3")
    {
        std::cerr << "invalid PPM header" << std::endl;
        return false;
    }

    int w = 0, h = 0;
    inStrm >> w >> h;
    if (w <= 0 || h <= 0)
    {
        std::cerr << "invalid size" << std::endl;
        return false;
    }

    int maxVal = 0;
    inStrm >> maxVal;
    if (maxVal != 255)
    {
        std::cerr << "invalid max value (255 expected)" << std::endl;
        return false;
    }

    pixCount = w * h;

    int sumR = 0, sumG = 0, sumB = 0;
    for (int iPix = 0; iPix < pixCount; ++iPix)
    {
        int r = 0, g = 0, b = 0;
        inStrm >> r >> g >> b;
        ++freqA[0][r];
        ++freqA[1][g];
        ++freqA[2][b];
    }

    return true;
}

int Histogram::getAvg(int colIdx) const
{
    int avg = 0;
    for (int val = 0; val < 256; ++val)
    {
        avg += freqA[colIdx][val] * val;
    }

    return avg / pixCount;
}

void Histogram::adjust(const Histogram& origHist, int colIdx, float gamma)
{
    freqA[colIdx].assign(256, 0);

    for (int val = 0; val < 256; ++val)
    {
        int newVal = mapVal(val, gamma);
        freqA[colIdx][newVal] += origHist.freqA[colIdx][val];
    }
}

void mapImage(const std::string fileName, float gammaA[])
{
    std::ifstream inStrm(fileName);

    std::string format;
    inStrm >> format;

    int w = 0, h = 0;
    inStrm >> w >> h;

    int maxVal = 0;
    inStrm >> maxVal;

    std::cout << "P3" << std::endl;
    std::cout << w << " " << h << std::endl;
    std::cout << "255" << std::endl;

    int nPix = w * h;

    for (int iPix = 0; iPix < nPix; ++iPix)
    {
        int inRgb[3] = {0};
        inStrm >> inRgb[0] >> inRgb[1] >> inRgb[2];

        int outRgb[3] = {0};
        for (int iCol = 0; iCol < 3; ++iCol)
        {
            outRgb[iCol] = mapVal(inRgb[iCol], gammaA[iCol]);
        }

        std::cout << outRgb[0] << " " << outRgb[1] << " "
                  << outRgb[2] << std::endl;
    }
}

int main(int argc, char* argv[])
{
    if (argc < 5)
    {
        std::cerr << "usage: " << argv[0]
                  << " ppmFileName targetR targetG targetB"
                  << std::endl;
        return 1;
    }

    std::string inFileName = argv[1];

    int targAvg[3] = {0};
    std::istringstream strmR(argv[2]);
    strmR >> targAvg[0];
    std::istringstream strmG(argv[3]);
    strmG >> targAvg[1];
    std::istringstream strmB(argv[4]);
    strmB >> targAvg[2];

    Histogram origHist;
    if (!origHist.read(inFileName))
    {
        return 1;
    }

    Histogram newHist(origHist);
    float gammaA[3] = {0.0f};

    for (int iCol = 0; iCol < 3; ++iCol)
    {
        float minGamma = 0.0f;
        float maxGamma = 1.0f;
        for (;;)
        {
            newHist.adjust(origHist, iCol, maxGamma);
            int avg = newHist.getAvg(iCol);
            if (avg <= targAvg[iCol])
            {
                break;
            }
            maxGamma *= 2.0f;
        }

        for (;;)
        {
            float midGamma = 0.5f * (minGamma + maxGamma);

            newHist.adjust(origHist, iCol, midGamma);
            int avg = newHist.getAvg(iCol);
            if (avg < targAvg[iCol])
            {
                maxGamma = midGamma;
            }
            else if (avg > targAvg[iCol])
            {
                minGamma = midGamma;
            }
            else
            {
                gammaA[iCol] = midGamma;
                break;
            }
        }
    }

    mapImage(inFileName, gammaA);

    return 0;
}

The code itself is fairly straightforward. One subtle but important detail is that, while the color values are in the range [0, 255], I map them to the gamma curve as if the range were [-1, 256]. This allows the average to be forced to 0 or 255. Otherwise, 0 would always remain 0, and 255 would always remain 255, which might never allow for an average of 0/255.

To use:

1. Save the code in a file with extension .cpp, e.g. force.cpp.
2. Compile with c++ -o force -O2 force.cpp.
3. Run with ./force input.ppm targetR targetG target >output.ppm.

Sample output for 40, 40, 40

Note that the images for all the larger samples are included as JPEGs since they exceed the SE size limit as PNGs. Since JPEG is a lossy compression format, they may not exactly match the target average. I have the PNG version of all files, which matches exactly.

Sample output for 150, 100, 100:

Sample output for 75, 91, 110:

Answer 3

Python 2 + PIL

from PIL import Image
import random
import math

SOURCE = 'input.png'
OUTPUT = 'output.png'
AVERAGE = [150, 100, 100]

im = Image.open(SOURCE).convert('RGB')
pixels = im.load()
w = im.size[0]
h = im.size[1]
npixels = w * h

maxdiff = 0.1

# for consistent results...
random.seed(42)
order = range(npixels)
random.shuffle(order)

def calc_sum(pixels, w, h):
    sums = [0, 0, 0]
    for x in range(w):
        for y in range(h):
            for i in range(3):
                sums[i] += pixels[x, y][i]
    return sums

def get_coordinates(index, w):
    return tuple([index % w, index // w])

desired_sums = [AVERAGE[0] * npixels, AVERAGE[1] * npixels, AVERAGE[2] * npixels]

sums = calc_sum(pixels, w, h)
for i in range(3):
    while sums[i] != desired_sums[i]:
        for j in range(npixels):
            if sums[i] == desired_sums[i]:
                break
            elif sums[i] < desired_sums[i]:
                coord = get_coordinates(order[j], w)
                pixel = list(pixels[coord])
                delta = int(maxdiff * (255 - pixel[i]))
                if delta == 0 and pixel[i] != 255:
                    delta = 1
                delta = min(delta, desired_sums[i] - sums[i])

                sums[i] += delta
                pixel[i] += delta
                pixels[coord] = tuple(pixel)
            else:
                coord = get_coordinates(order[j], w)
                pixel = list(pixels[coord])
                delta = int(maxdiff * pixel[i])
                if delta == 0 and pixel[i] != 0:
                    delta = 1
                delta = min(delta, sums[i] - desired_sums[i])

                sums[i] -= delta
                pixel[i] -= delta
                pixels[coord] = tuple(pixel)

# output image
for x in range(w):
    for y in range(h):
        im.putpixel(tuple([x, y]), pixels[tuple([x, y])])

im.save(OUTPUT)

This iterates through each pixel in a random order, and reduces the distance between each component of the color of the pixel and 255 or 0 (depending on whether the current average is less or greater than the desired average). The distance is reduced by a fixed multiplicative factor. This is repeated until the desired average is obtained. The reduction is always at least 1, unless the color is 255 (or 0), to ensure that the processing does not stall once the pixel is close to white or black.

Sample output

(40, 40, 40)

(150, 100, 100)

(75, 91, 110)

Answer 4

Java

An RNG based approach. A bit slow for large input images.

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.*;

import javax.imageio.ImageIO;


public class Averager {
    static Random r;
    static long sigmaR=0,sigmaG=0,sigmaB=0;
    static int w,h;
    static int rbar,gbar,bbar;
    static BufferedImage i;
    private static File file;
    static void upRed(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getRed()==255)return;
        sigmaR++;
        c=new Color(c.getRed()+1,c.getGreen(),c.getBlue());
        i.setRGB(x, y,c.getRGB());
    }
    static void downRed(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getRed()==0)return;
        sigmaR--;
        c=new Color(c.getRed()-1,c.getGreen(),c.getBlue());
        i.setRGB(x, y,c.getRGB());
    }
    static void upGreen(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getGreen()==255)return;
        sigmaG++;
        c=new Color(c.getRed(),c.getGreen()+1,c.getBlue());
        i.setRGB(x, y,c.getRGB());
    }
    static void downGreen(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getGreen()==0)return;
        sigmaG--;
        c=new Color(c.getRed(),c.getGreen()-1,c.getBlue());
        i.setRGB(x,y,c.getRGB());
    }
    static void upBlue(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getBlue()==255)return;
        sigmaB++;
        c=new Color(c.getRed(),c.getGreen(),c.getBlue()+1);
        i.setRGB(x, y,c.getRGB());
    }
    static void downBlue(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getBlue()==0)return;
        sigmaB--;
        c=new Color(c.getRed(),c.getGreen(),c.getBlue()-1);
        i.setRGB(x,y,c.getRGB());
    }
    public static void main(String[]a) throws Exception{
        Scanner in=new Scanner(System.in);
        i=ImageIO.read(file=new File(in.nextLine()));
        rbar=in.nextInt();
        gbar=in.nextInt();
        bbar=in.nextInt();
        w=i.getWidth();
        h=i.getHeight();
        final int npix=w*h;
        r=new Random(npix*(long)i.hashCode());
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                Color c=new Color(i.getRGB(x, y));
                sigmaR+=c.getRed();
                sigmaG+=c.getGreen();
                sigmaB+=c.getBlue();
            }
        }
        while(sigmaR/npix<rbar){
            upRed();
        }
        while(sigmaR/npix>rbar){
            downRed();
        }
        while(sigmaG/npix<gbar){
            upGreen();
        }
        while(sigmaG/npix>gbar){
            downGreen();
        }
        while(sigmaB/npix<bbar){
            upBlue();
        }
        while(sigmaB/npix>bbar){
            downBlue();
        }
        String k=file.getName().split("\\.")[0];
        ImageIO.write(i,"png",new File(k="out_"+k+".png"));
    }
}

Tests:

(40,40,40)

(150,100,100)

(75,91,110)