Codebrawl contest "Content-aware image cropping with ChunkyPNG" entry

README

Program is run by typing "ruby main-single.rb input.png output.png". 
The output contains the cropped image in png format.

The idea behind the algorithm is the following:
For every pixel we could define its "volatility" by finding the average of the differences of it and it's neighbors (for pixels p1 and p2 the difference would be |p1.alpha - p2alpha| + |p1.red - p2.red| + |p1.blue - p2.blue| + |p1.green - p2.green|).

After we have calculated the "volatility" for each pixel we could find the average "volatility" and by that we would determine if the picture in general is more or less volatile. 

Then we for the area/window(100px by 100px) that has the greatest absolute difference of average its volatilities and the general average volatility (|avg_volatility - current_window.avg_volatility|). By doing this, we find the area that is the noisiest in an otherwise calm picture or the area that is the calmest in an otherwise noisy picture. 

That area is then proclaimed the most interesting.

There are many possible refinements of this algorithm, and it would be interesting to add a confidence value to this algorithm, and possibly use other measures like color differentiation. 

cat.png

dog.png

duck.png

main.rb

require 'rubygems'
require 'chunky_png'

WIDTH = 100
HEIGHT = 100

class TwodimensionalArray
	def initialize(width, height)
		@width = width
		@height = height
		@array = Array.new(width)
		@array.map! {Array.new(height)}
	end
	
	def [](x, y)
		@array[x][y]
	end
	
	def []=(x, y, value)
		@array[x][y] = value
	end
	
	def width 
		@width
	end
	
	def height
		@height
	end
	
	def average
		sum = 0
		0.upto(@width-1) do |x|
			0.upto(@height-1) do |y|
				sum += @array[x][y]
			end
		end
		sum / (@width * @height)
	end
	
	def key_values
		max = min = @array[0][0]	
		sum = 0
		0.upto(@width-1) do |x|
			0.upto(@height-1) do |y|
				sum += @array[x][y]
				max = @array[x][y] if max < @array[x][y] 
				min = @array[x][y] if min > @array[x][y] 
			end
		end
		[min, sum / (@width * @height), max]
	end
	
	def neighbours(x, y, distance = 1)
		result = []
		(-distance).upto(distance) do |dx|
			(-distance).upto(distance) do |dy|				
				result << @array[x + dx][y + dy] unless ((dx == 0 && dy == 0) || (x + dx < 0) || (x + dx >= width) || (y + dy < 0) || (y + dy >= height))
			end
		end		
		result
	end
	
	def self.from_canvas(source)
		result = TwodimensionalArray.new(source.width, source.height)
		0.upto(source.width-1) do |x|
			0.upto(source.height-1) do |y|
				result[x,y] = Pixel.from_int(source.get_pixel(x, y))
			end
		end
		result
	end
end
class SumArray
	def initialize(source_array, sum_width, sum_height)
		@sum_width = sum_width
		@sum_height = sum_height
		@source_array = source_array
		cumulative_array = cumulative(source_array)
		@array = TwodimensionalArray.new(source_array.width - sum_width, source_array.height - sum_height)
		0.upto(@array.width-1) do |x|
			0.upto(@array.height-1) do |y|
				@array[x,y] = cumulative_array[x+sum_width-1,y+sum_height-1]
				@array[x,y] -= cumulative_array[x-1,y+sum_height-1] if (x-1 >= 0)
				@array[x,y] -= cumulative_array[x+sum_width-1,y-1] if (y-1 >= 0)
				@array[x,y] += cumulative_array[x-1,y-1] if ((x-1 >= 0) && (y-1 >= 0))
				@array[x,y] /= (sum_width*sum_height)						
			end
		end
	end
	
	def [](x, y)
		@array[x, y]
	end
	
	def sum_width
		@sum_width
	end
	
	def sum_height
		@sum_height
	end
	
	def max_difference
		average_contrast = @source_array.average		
		max_x = max_y = max_difference = 0;
		
		0.upto(@array.width-1) do |x|
			0.upto(@array.height-1) do |y|
				if ((@array[x,y] - average_contrast).abs > max_difference)
					max_difference = (@array[x,y] - average_contrast).abs
					max_x = x
					max_y = y
				end
			end
		end
		[max_x, max_y]
	end
	
	private
	def cumulative(source_array)
		result = TwodimensionalArray.new(source_array.width, source_array.height)
		0.upto(source_array.width-1) do |x|		
			0.upto(source_array.height-1) do |y|				
				result[x,y] = source_array[x,y]
				result[x,y] += result[x-1,y] if (x-1 >= 0)
				result[x,y] += result[x,y-1] if (y-1 >= 0)
				result[x,y] -= result[x-1,y-1] if ((x-1 >= 0) && (y-1 >= 0))				
			end
		end
		result
	end
end
class AreaOfInterest 	
	def initialize(width, height)
		@width, @height = width, height		
	end
	
	def process(source)		
		img = TwodimensionalArray.from_canvas(source)
		contrast_field = get_contrast_field(img)
		avg = contrast_field.average
		min, avg, max = contrast_field.key_values
		
		0.upto(contrast_field.width-1) do |x|
			0.upto(contrast_field.height-1) do |y|
					contrast_field[x,y] = ((contrast_field[x,y] < avg) ? min : max)				
					#contrast_field[x, y] = 0 if contrast_field[x,y] < avg
			end
		end
		area_of_interest = get_area_of_interest(contrast_field, @width, @height)				
		source.crop(area_of_interest[0], area_of_interest[1], @width, @height)
		#to_png(contrast_field)
	end	
	
	private		
	def get_area_of_interest(contrast_field, width, height)		
		SumArray.new(contrast_field, width, height).max_difference			
	end
	
	def get_contrast_field(pixel_field) 
		result = TwodimensionalArray.new(pixel_field.width, pixel_field.height)
		0.upto(pixel_field.width-1) do |x|
			0.upto(pixel_field.height-1) do |y|
				neighbours = pixel_field.neighbours(x, y)
				result[x,y] = neighbours.inject(0) {|sum, neighbour| sum += pixel_field[x, y].absolute_difference(neighbour)} / neighbours.count				
			end
		end		
		result
	end
	
	def to_png(input)
		result = ChunkyPNG::Canvas.new(input.width, input.height)
		0.upto(input.width-1) do |x|
			0.upto(input.height-1) do |y|
				result.set_pixel(x, y, input[x,y])
			end
		end
		result
	end
end
class Pixel 	
	def self.from_int(value)
		Pixel.new((value >> 24) % 0xFF, (value >> 16) % 0xFF, (value >> 8) % 0xFF, value % 0xFF)
	end

	def initialize(alpha, red, green, blue)
		@blue = blue
		@green = green
		@red = red
		@alpha = alpha
	end
	
	def red
		@red
	end

	def red=(value)
		@red = value
	end
	
	def green
		@green
	end
	
	def green=(value)
		@green = value
	end	
	
	def blue
		@blue
	end

	def blue=(value)
		@blue = value
	end

	
	def alpha
		@alpha
	end
	
	def alpha=(value)
		@alpha = value
	end
	
	def absolute_difference(another_pixel)
		(red - another_pixel.red).abs + (green - another_pixel.green).abs + (blue - another_pixel.blue).abs + (alpha - another_pixel.alpha).abs
	end
end

source = ChunkyPNG::Image.from_file(ARGV[0])
processor = AreaOfInterest.new(WIDTH, HEIGHT)
result = processor.process(source)
result.save(ARGV[1] || "output.png")

Interesting. Perhaps the best output. Not the best Ruby (attr_accessor, anyone?) and it's hard to figure out what the methodology is.

Great results, but it's very hard to read the code. This reads like Java or C++...

Nice crops. Would be nice to see at least a short explanation of the algorithm in words.