2.1.1 Histogram Expansion

Background: I’m working my way through the book Practical Algorithms Image Analysis, and documenting my progress here. I remain WELL AWARE that I’m reinventing the wheel, and that nearly all of this is, you know, already built into Flash, but it’ll be a learnful experience.

Building on my Histogram viewer, the next task is to select a sub-range of the input intensity histogram and remap it to a full dynamic range in an output histogram, referred to by the text as “Histogram Expansion (H_E)”.

The helpful linear mapping function to stretch the interval [x_min, x_max] to cover the full [0,255] range is provided as:

Now, for this to work for color images, that function will have to be performed for each of the red, green, and blue intensity values for each pixel. Solving this through .getPixel() and .setPixel() proved to be much too slow and processor-heavy, so I made a quick PixelBender kernel to get the job done. Click through for a demo and explanation.

So the thing is, you’re not really performing a calculation on the input histogram, getting an output histogram, and then building an output image out of it (since that doesn’t really make sense), you’re just observing the input histogram to pick the [x_min, x_max] range, and then using those values to perform the calculation on the input image, clipping the available intensity levels for each pixel so that they’re either [0, x_min:x_max, 255] which gets you to the output image, which then you create a NEW histogram from so that you can observe that the calculation, in fact, had the effect of stretching out that portion of the histogram. Just go with it.

Starting out, I made a function that takes the input value (between 0 and 255) and remaps it onto the range [xmin,xmax]:

protected function StretchAlgorithm(input:int, xmin:int, xmax:int):int {
	var output:Number
	if (input < xmin) {
		output = 0;
	} else if (input > xmax ) {
		output = 255;
	} else {
		output = ((input - xmin)/(xmax-xmin))*255;
	}
	return int(output);
}

Then I wrote the larger function that scans through the image’s BitmapData() in raster order and performs this function three times for each pixel, combines the result, and sets that pixel value in an output BitmapData():

protected function HistogramStretch(input:BitmapData, xmin:int, xmax:int):BitmapData {
	var w:int = input.width;
	var h:int = input.height;
	var output:BitmapData = new BitmapData(w,h);
	input.lock();
	output.lock();

	for (var i:int = 0; i < w; ++i) {
		for (var j:int = 0; j < h; ++j) {
			var color:uint = input.getPixel(i,j);
			var red:int = StretchAlgorithm(color >> 16, xmin,xmax);
			var green:int = StretchAlgorithm(color >> 8 & 0xFF, xmin,xmax);
			var blue:int = StretchAlgorithm(color & 0xFF, xmin,xmax);
			var newColor:uint = red << 16 | green << 8 | blue;
			output.setPixel(i,j,newColor);
		}
	}
	input.unlock();
	output.unlock();

	return output;
}

For my example, I populate the xmin and xmax values by checking the position of the two sliders. Trouble is, all those .getPixel() and .setPixel() calls start bogging down my wee little MacBook Air and make everything run at maybe 2 fps. So knowing that this is precisely the kind of thing PixelBender is meant for, I came up with a Shader kernel that does it instead:

<languageVersion : 1.0;>

kernel HistogramExpansion

<   namespace : "digitologist.com";
    vendor : "Jon Thompson";
    version : 1;
    description : "A simple histogram expansion filter";
>
{
    input image4 src;
    output pixel4 dst;
    parameter int Min <
        minValue: 0;
        maxValue: 255;
        defaultValue: 0;
    >;
    parameter int Max <
        minValue: 0;
        maxValue: 255;
        defaultValue:255;
    >;

    void
    evaluatePixel()
    {
        float xmin = float(Min / 255);
        float xmax = float(Max / 255);
        float4 inputColor = sampleNearest(src,outCoord());
        dst.a = inputColor.a;
        dst.rgb = (inputColor.rgb - float3(xmin)) / (xmax-xmin);
    }
}

(I’m still only learning the ins and outs of Pixel Bender, so it took annoyingly long to get the floats vs. ints and such right, and a loooong time before I finally remembered that PB color values range from [0, 1] instead of [0,255])

This way I can just load that into Flash, store it as ExpansionShaderFilter and use .applyFilter() on the input BitmapData() thusly:

ExpansionShaderFilter.data.Min.value = [xmin];
ExpansionShaderFilter.data.Max.value = [xmax];

OutputBitmapData.applyFilter(stretchedData,new Rectangle(0,0,320,240),new Point(),new ShaderFilter(ExpansionShaderFilter));

So that’s that, an evenly-spaced stretching of a sub-range of intensity values to fill the full range of an output image. Next will be un-evenly spaced methods, like ramps or curves.