[QUIZ] Mathematical Image Generator (#191)

[Daniel Moore]

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2. Support Ruby Quiz by submitting ideas and responses
as often as you can! Visit: <http://rubyquiz.strd6.com>

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Mathematical Image Generator (#191)

This week's quiz is about the generation of images based on
mathematical functions. The red, green, and blue values at each point
in the image will each be determined by a separate function based on
the coordinates at that position.

Here are some functions to get started:

Math.sin(Math:I * ?)
Math.cos(Math:I * ?)
(? + ?)/2
? * ?
(?) ** 3

The question marks represent the parameters to the functions (x, y, or
another function). The x and y values range between 0 and 1: the
proportion of the current position to the total width or height.

Feel free to add your own functions, but keep in mind that they work
best when the inputs and output are between -1 and 1.

Example Output:

http://strd6.com/?attachment_id=145

depth: 3
red: Math.sin(Math:I * Math.cos(Math:I * y * x))
green: Math.sin(Math:I * (Math.sin(Math:I * y)) ** 3)
blue: (Math.cos(Math:I * Math.cos(Math:I * y))) ** 3

The depth is how many layers of functions to combine. The bottom layer
is always x or y. Depth 3 is where things begin to get a little bit
interesting, but 5 and higher is much more exciting.

Performance can be an issue with so many computations per pixel,
therefore the solution that performs quickest on a 1600x1200 image
with depth of 7 will be the winner of this quiz!

Good luck!

 

[Sander Land]

Example Output:

http://strd6.com/?attachment_id=145

depth: 3
red: Math.sin(Math:I * Math.cos(Math:I * y * x))
green: Math.sin(Math:I * (Math.sin(Math:I * y)) ** 3)
blue: (Math.cos(Math:I * Math.cos(Math:I * y))) ** 3

The depth is how many layers of functions to combine. The bottom layer
is always x or y. Depth 3 is where things begin to get a little bit
interesting, but 5 and higher is much more exciting.

The link to the example output is dead.
Also, I don't get what you mean by 'depth' exactly.

I can see the red: as either
depth 2: somecomplicatedfunction( times(x, y) )
or
depth 5: sin( times( pi, cos( times(pi, times(x,y)))))

 

[Daniel Moore]

The link to the example output is dead.
Also, I don't get what you mean by 'depth' exactly.

I can see the red: as either
depth 2: somecomplicatedfunction( times(x, y) )
or
depth 5: sin( times( pi, cos( times(pi, times(x,y)))))

You're right, I'm sorry for my error. Here is an updated link:
http://strd6.com/?p=146

My explanation of function depth is also somewhat confusing. If anyone
sees what I'm getting at and wants to try and help me out with another
explanation please do! Let me try again in the meantime:

Function depth is more of a tree depth in this circumstance. Some
functions take two parameters, some take one parameter. So depth of 0
would be either x or y. Depth 1 would be any of the following:

(x + x)/2
(x + y)/2
sin(PI * x)
sin(PI * y)
cos(PI * x)
...

Depth 2 could be:

(sin(PI * x) + x * y)/2

Part of the difficulty in this quiz is composing functions of
different arity. Hopefully this explanation clears things up a little.

Thanks for bringing this up and if you have any further questions
please continue to ask.

 

[Albert Schlef]

My explanation of function depth is also somewhat confusing. If anyone
sees what I'm getting at and wants to try and help me out with another
explanation please do! Let me try again in the meantime:

Does "depth" equal "the number of times 'x' (or 'y') appears in the
expression" ?

 

[Sean Mehan]

And is this before or after collection?

2x + x + 5x = 8x, has one term of x at degree 1.

2x^2 -x + 4x^2 + x = 6x^2, has one term of x at degree 2 and none at
degree 1....

 

[Alex Fenton]

## Mathematical Image Generator (#191)

This week's quiz is about the generation of images based on
mathematical functions. The red, green, and blue values at each point
in the image will each be determined by a separate function based on
the coordinates at that position.
....


Performance can be an issue with so many computations per pixel,
therefore the solution that performs quickest on a 1600x1200 image
with depth of 7 will be the winner of this quiz!

I think for a pure speed competition, we'd need a standard set of
functions, a reference image, a defined way to translate -1..1 values to
colour intensities (eg 0..255).

But it seemed like a fun one, so below is my offering: a little desktop
(wxRuby) program for generating these maths images interactively.

Type the r, g and b functions into the boxes, then click "Render" to
update. "Save Image" saves the current image to TIF, PNG or BMP.

If there's an error in a function, a cross mark appears next to it;
hover over the cross mark to get a hint about the problem.

On my system, using Ruby 1.9, it renders the default image at 800 x 600
in about 2.85s. Since the speed is pretty much proportional to the total
pixels, I'd guess about 11.5s for a 1600x1200 image. Interestingly, this
is one where Ruby 1.9 makes a big difference.

a

__________

require 'wx'
include Wx
include Math

# A canvas that draws and displays a mathematically generated image
class MathsDrawing < Window
# The functions which return the colour components at each pixel
attr_writer :red, :green, :blue
# The time taken to render, whether re-rendering is needed, and the
# source image
attr_reader :render_time, :done, :img

def initialize(parent)
super(parent)
# Create a dummy image
@default_image = Image.new(1, 1)
@default_image.data = [255, 255, 255].pack('CCC')
@img = @default_image

@red = lambda { | x, y | 1 }
@green = lambda { | x, y | 1 }
@blue = lambda { | x, y | 1 }

@done = true

evt_size n_size
evt_paint n_paint
evt_idle n_idle
end

# Paint the image on the screen. The actual image rendering is done in
# idle time, so that the GUI is responsive whilst redrawing - eg, when
# resized. Painting is done by quickly rescaling the cached image.
def on_paint
paint do | dc |
draw_img = @img.scale(client_size.x, client_size.y)
dc.draw_bitmap(draw_img.convert_to_bitmap, 0, 0, true)
end
end

# Regenerate the image if needed, then do a refresh
def on_idle
if not @done
@img = make_image
refresh
end
@done = true
end

# Note to regenerate the image if the canvas has been resized
def on_size(event)
@done = false
event.skip
end

# Call this to force a re-render - eg if the functions have changed
def redraw
@done = false
end

# Actually make the image
def make_image
size_x, size_y = client_size.x, client_size.y
if size_x < 1 or size_y < 1
return @default_image
end

start_time = Time.now
# The string holding raw image data
data = ''
x_factor = size_x.to_f
y_factor = size_y.to_f

# Input values from the range 0 to 1, with origin in the bottom left
size_y.downto(0) do | y |
the_y = y.to_f / y_factor
0.upto(size_x - 1) do | x |
the_x = x.to_f / x_factor
red = @red.call(the_x, the_y) * 255
green = @green.call(the_x, the_y) * 255
blue = @blue.call(the_x, the_y) * 255
data << [red, green, blue].pack("CCC")
end
end
img = Image.new(size_x, size_y)
img.data = data
@render_time = Time.now - start_time
img
end
end

# A helper dialog for saving the image to a file
class SaveImageDialog < FileDialog
# The image file formats on offer
TYPES = [ [ "PNG file (*.png)|*.png", BITMAP_TYPE_PNG ],
[ "TIF file (*.tif)|*.tif", BITMAP_TYPE_TIF ],
[ "BMP file (*.bmp)|*.bmp", BITMAP_TYPE_BMP ] ]

WILDCARD = TYPES.map { | type | type.first }.join("|")

def initialize(parent)
super(parent, :wildcard => WILDCARD,
:message => 'Save Image',
:style => FD_SAVE|FD_OVERWRITE_PROMPT)
end

# Returns the Wx identifier for the selected image type.
def image_type
TYPES[filter_index].last
end
end

# A Panel for displaying the image and controls to manipulate it
class MathsPanel < Panel
# Set functions to some nice initial values
RED_INITIAL = "cos(x)"
GREEN_INITIAL = "cos(y ** x)"
BLUE_INITIAL = "(x ** 4) + ( y ** 3 ) - (4.5 * x ** 2 ) + ( y * 2)"

# Symbols to show correct and incorrect functions
TICK = "\xE2\x9C\x94"
CROSS = "\xE2\x9C\x98"

attr_reader :drawing

def initialize(parent)
super(parent)
self.sizer = VBoxSizer.new
# The canvas
@drawing = MathsDrawing.new(self)
sizer.add @drawing, 1, GROW

sizer.add Wx::StaticLine.new(self)

# The text controls for entering functions
grid_sz = FlexGridSizer.new(3, 8, 8)
grid_sz.add_growable_col(1, 1)

grid_sz.add StaticText.new(self, :label => "Red")
@red_tx = TextCtrl.new(self, :value => RED_INITIAL)
grid_sz.add @red_tx, 0, GROW
@red_err = StaticText.new(self, :label => TICK)
grid_sz.add @red_err, 0, ALIGN_CENTRE

grid_sz.add StaticText.new(self, :label => "Green")
@green_tx = TextCtrl.new(self, :value => GREEN_INITIAL)
grid_sz.add @green_tx, 0, GROW
@green_err = StaticText.new(self, :label => TICK)
grid_sz.add @green_err, 0, ALIGN_CENTRE

grid_sz.add StaticText.new(self, :label => "Blue")
@blue_tx = TextCtrl.new(self, :value => BLUE_INITIAL)
grid_sz.add @blue_tx, 0, GROW
@blue_err = StaticText.new(self, :label => TICK)
grid_sz.add @blue_err, 0, ALIGN_CENTRE

# Buttons to save and render
grid_sz.add nil
butt_sz = HBoxSizer.new
render_bt = Button.new(self, :label => "Render")
butt_sz.add render_bt, 0, Wx::RIGHT, 8
evt_button render_bt, n_render

save_bt = Button.new(self, :label => "Save Image")
butt_sz.add save_bt, 0, Wx::RIGHT, 8
evt_button save_bt, n_save

# Disable the buttons whilst redrawing
evt_update_ui(render_bt) { | evt | evt.enable(@drawing.done) }
evt_update_ui(save_bt) { | evt | evt.enable(@drawing.done) }
grid_sz.add butt_sz

# Add the controls sizer to the whole thing
sizer.add grid_sz, 0, GROW|ALL, 10

on_render
end

# Update the functions that generate the image, then re-render it
def on_render
@drawing.red = make_a_function(@red_tx.value, @red_err)
@drawing.green = make_a_function(@green_tx.value, @green_err)
@drawing.blue = make_a_function(@blue_tx.value, @blue_err)
@drawing.redraw
end

# Display a dialog to save the image to a file
def on_save
dlg = SaveImageDialog.new(parent)
if dlg.show_modal == ID_OK
@drawing.img.save_file(dlg.path, dlg.image_type)
end
end

# A function which doesn't do anything
NULL_FUNC = lambda { | x, y | 1 }

# Takes a string source +source+, returns a lambda. If the string
# source isn't valid, flag this in the GUI static text +error_outlet+
def make_a_function(source, error_outlet)
return NULL_FUNC if source.empty?
func = nil
begin
# Create the function and test it, to check for wrong names
func = eval "lambda { | x, y | #{source} }"
func.call(0, 0)
rescue Exception => e
error_outlet.label = CROSS
error_outlet.tool_tip = e.class.name + ":\n" +
e.message.sub(/^\(eval\):\d+: /, '')
return NULL_FUNC
end

error_outlet.label = TICK
error_outlet.tool_tip = ''
func
end
end

class MathsFrame < Frame
def initialize
super(nil, :title => 'Maths drawing',
:size => [400, 500],
os => [50, 50])
sb = create_status_bar(1)
evt_update_ui sb, n_update_status
@panel = MathsPanel.new(self)
end

def on_update_status
if @panel.drawing.done
pixels = @panel.drawing.client_size
msg = "[#{pixels.x} x #{pixels.y}] drawing completed in " +
"#{@panel.drawing.render_time}s"
status_bar.status_text = msg
end
end
end

App.run do
MathsFrame.new.show
end

 

[Daniel Moore]

I'm still not doing a very good job of explaining this. One more
attempt, this time by a coding example.

CAUTION: Spoiler! If you want to generate random functions on your own
do not read further. This implements the function generation, not
anything specific to image generation.

Here is a class that will generate string representations of functions
given a specified depth. Feel free to use or modify this class in your
solutions.

class FunctionMaker
def initialize()
@functions = ["Math.sin(Math:I * ?)", "Math.cos(Math:I * ?)",
"(? + ?)/2", "? * ?", "(?) ** 3"]
end

# Create a string representation of a function at the given
def create_function(depth)
#if depth is 0, return either x or y randomly
if depth == 0
return "x" if rand > 0.5
return "y"
end

#grab a random function from the list
function = @functions[rand(@functions.length)]

#for each instance of ? in the function, replace with a function
at the next shallower depth
return function.gsub("?") { create_function(depth - 1) }
end
end

Usage:
fm = FunctionMaker.new
fm.create_function(5)
=> "(Math.sin(Math:I * ((Math.cos(Math:I * y) + y * y)/2 + y * x *
y * y)/2)) ** 3"

 

[Sander Land]

@functions = ["Math.sin(Math:I * ?)", "Math.cos(Math:I * ?)",

I think this is what caused the confusion, at least for me. You
consider "Math.sin(Math:I * ?)" one depth level extra instead of
two.

 

[Lars Haugseth]

This is my first quiz submission. Any comments appreciated.

I opted for RMagick to generate the image from raw pixels. There
might be faster options (GD?), but the time spent converting pixel
values to an image and writing this to file is negligible compared
to actually generating the pixels, especially when the functions
get more complex.

I found I could shave some time off the pixel generation by wrapping
the whole iteration process inside a single eval instead of calling
functions (or worse, doing an eval) for each iteration.

$ cat gen_image.rb
#!/usr/bin/env ruby

require 'rubygems'
require 'RMagick'


class FunctionGenerator

def initialize
@functions = []
end

def <<(function)
@functions << function
end

def random_function_of_depth(depth)
if depth == 0
['x', 'y', '-x', '-y'][rand(4)]
else
function = @functions[rand(@functions.size)]
function.gsub('expr') { random_function_of_depth(depth - 1) }
end
end
end


class ImageGenerator

include Math

# Functions for red, green and blue
attr_accessor :red, :green, :blue

# Generate image and store to file
def generate_image(filename, width, height)
@width = width
@height = height
generate_pixels
store_image(filename)
end

private

# Generate pixels of image
def generate_pixels
@pixels = ""
eval <<"."
0.upto(@height - 1) do |y_pos|
y = (y_pos.to_f / @height)
0.upto(@width - 1) do |x_pos|
x = (x_pos.to_f / @width)
@pixels << (127.99 + 127.99 * #{@red}).to_i.chr
@pixels << (127.99 + 127.99 * #{@green}).to_i.chr
@pixels << (127.99 + 127.99 * #{@blue}).to_i.chr
end
end
..
end

# Store generated image to file
def store_image(filename)
image = Magick::Image.new(@width, @height)
image.import_pixels(0, 0, @width, @height, 'RGB', @pixels)
image.opacity = 0
image.write(filename)
end

end


func_gen = FunctionGenerator.new
func_gen << '(expr + expr) / 2'
func_gen << '(expr) ** 3'
func_gen << 'expr * expr'
func_gen << 'sin(expr * PI)'
func_gen << 'cos(expr * PI)'

image_gen = ImageGenerator.new
image_gen.red = func_gen.random_function_of_depth(4)
image_gen.green = func_gen.random_function_of_depth(4)
image_gen.blue = func_gen.random_function_of_depth(4)
puts "r: #{image_gen.red}"
puts "g: #{image_gen.green}"
puts "b: #{image_gen.blue}"
image_gen.generate_image('image.png', 800, 800)

 

[Daniel Moore]

This week's quiz was about creating interesting mathematical images
using randomly generated formulae. Visit
http://rubyquiz.strd6.com/quizzes/191/#summary to view the summary
with images included.

The overall architecture of the application is straightforward:
* generate (or accept as input) mathematical formulae
* compute the RGB values for each pixel
* output an image

Lars's solution provides a simple shell script which randomly
generates formulae of depth 4 and saves image out as a png file.
Lars's solution also makes it easy to add custom functions to the
generator by pushing them on to an array.

Alex Fenton provides a desktop application (using [wxRuby][1]) that
allows for custom input of formulae and can save the images in
multiple formats. If you are interested in learning wxRuby do examine
Alex's solution as it provides a good example of a wxRuby application
and is well commented.

The two solutions provided slightly different conversions from
function results to pixel colors. Alex's treated everything <= 0 as 0,
while Lars mapped -1 to 0 and 1 to 255, with 0 being 128 (on an 8-bit
RBG scale). This causes some images to appear wildly different,
observe:

![image with zero at midrange][2a] ![image with zero and less cutoff][2b]


One aspect of the challenge was to generate the images quickly. Here
are the results of the submissions using ruby-prof to benchmark.

ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]
width: 256
height: 256
r: cos(sin((sin(-x * PI)) ** 3 * PI) * PI)
g: (sin(((-y + y) / 2) ** 3 * PI)) ** 3
b: ((cos(-x * y * PI) + cos(cos(y * PI) * PI)) / 2 + sin(x * PI) *
cos(y * PI) * x * -x * sin(x * PI)) / 2

Lars Haugseth
Total: 6.860000
%self total self wait child calls name
44.61 6.86 3.06 0.00 3.80 256
Integer#upto-1 (ruby_runtime:0}
18.95 1.30 1.30 0.00 0.00 1179648 Float#*
(ruby_runtime:0}
6.71 0.46 0.46 0.00 0.00 327680 Math#cos
(ruby_runtime:0}
5.25 0.36 0.36 0.00 0.00 393216 Float#+
(ruby_runtime:0}
4.96 0.34 0.34 0.00 0.00 327680 Math#sin
(ruby_runtime:0}
4.23 0.29 0.29 0.00 0.00 262400 Float#/
(ruby_runtime:0}
3.50 0.24 0.24 0.00 0.00 196608 Float#**
(ruby_runtime:0}
3.21 0.22 0.22 0.00 0.00 196608 String#<<
(ruby_runtime:0}
2.92 0.20 0.20 0.00 0.00 262144 Float#-@
(ruby_runtime:0}
2.33 0.16 0.16 0.00 0.00 196608 Integer#chr
(ruby_runtime:0}
1.90 0.13 0.13 0.00 0.00 196608 Float#to_i
(ruby_runtime:0}
1.46 0.10 0.10 0.00 0.00 65792 Fixnum#to_f
(ruby_runtime:0}
0.00 6.86 0.00 0.00 6.86 1 Integer#upto
(ruby_runtime:0}
0.00 6.86 0.00 0.00 6.86 1 Kernel#eval
(ruby_runtime:0}
0.00 0.00 0.00 0.00 0.00 257 Fixnum#-
(ruby_runtime:0}
0.00 6.86 0.00 0.00 6.86 1
ImageGenerator#generate_pixels (solution.rb:48}


Alex Fenton
Total: 7.800000
%self total self wait child calls name
41.15 5.90 3.21 0.00 2.69 196608 Proc#call
(ruby_runtime:0}
15.13 1.18 1.18 0.00 0.00 1179648 Float#*
(ruby_runtime:0}
12.18 7.79 0.95 0.00 6.84 256 Integer#upto
(ruby_runtime:0}
6.28 0.62 0.49 0.00 0.13 65536 Array#pack
(ruby_runtime:0}
4.23 0.33 0.33 0.00 0.00 262400 Float#/
(ruby_runtime:0}
4.10 0.32 0.32 0.00 0.00 327680 Math#cos
(ruby_runtime:0}
3.85 0.30 0.30 0.00 0.00 327680 Math#sin
(ruby_runtime:0}
3.72 0.29 0.29 0.00 0.00 262144 Float#-@
(ruby_runtime:0}
3.33 0.26 0.26 0.00 0.00 196608 Float#**
(ruby_runtime:0}
2.31 0.18 0.18 0.00 0.00 196608 Float#+
(ruby_runtime:0}
1.67 0.13 0.13 0.00 0.00 196608 Float#to_int
(ruby_runtime:0}
1.15 0.09 0.09 0.00 0.00 65794 Fixnum#to_f
(ruby_runtime:0}
0.90 0.07 0.07 0.00 0.00 65536 String#<<
(ruby_runtime:0}
0.00 7.80 0.00 0.00 7.80 1
Integer#downto (ruby_runtime:0}
0.00 7.80 0.00 0.00 7.80 1
MathsDrawing#make_image (solution.rb:74}
0.00 0.00 0.00 0.00 0.00 257 Fixnum#-
(ruby_runtime:0}

When I first ran the benchmark I noticed a discrepancy in the number
of times that various Float and Math methods were called. It turns out
that Alex Fenton's solution was computing one extra row of pixels. I
corrected this for the results. Here are the sections of code that
were used in the benchmark:

# Lars Haugseth
@pixels = ""
eval <<"."
0.upto(@height - 1) do |y_pos|
y = (y_pos.to_f / @height)
0.upto(@width - 1) do |x_pos|
x = (x_pos.to_f / @width)
@pixels << (127.99 + 127.99 * #{@red}).to_i.chr
@pixels << (127.99 + 127.99 * #{@green}).to_i.chr
@pixels << (127.99 + 127.99 * #{@blue}).to_i.chr
end
end

 

[Lars Haugseth]

No one got really crazy with performance and created a lookup table
for trigonometric functions, but that may be one way to save cycles,
especially when creating much larger images.

After I posted my code here, I did some quick experimentations involving
"caching" of sub-expressions not involving x as a factor by calculating
those outside the inner loop, storing them in a hash and looking up the
value from the hash inside the inner loop. However, in my experience it
was faster to actually compute the simple expressions (Math.sin(y),
y * y, etc.) than looking them up in a hash. I guess such caching could
speed things up a little if one was to cache more complex expressions
involving just one of the dimensions, but I deemed it too much effort
for too little gain to investigate further.

Thank you Daniel.