Mathematical Image Generator (#191)

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

The three rules of Ruby Q.:

  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 Q. 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 T. 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::PI * ?)
Math.cos(Math::PI * ?)
(? + ?)/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:

depth: 3
red: Math.sin(Math::PI * Math.cos(Math::PI * y * x))
green: Math.sin(Math::PI * (Math.sin(Math::PI * y)) ** 3)
blue: (Math.cos(Math::PI * Math.cos(Math::PI * 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!

On Fri, Feb 6, 2009 at 5:59 PM, Daniel M. [email protected] wrote:

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)))))

On Fri, Feb 6, 2009 at 10:25 AM, Sander L. [email protected]
wrote:

The depth is how many layers of functions to combine. The bottom layer

You’re right, I’m sorry for my error. Here is an updated link:

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.

Di Mo wrote:

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” ?

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…

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::PI * ?)”, “Math.cos(Math::PI * ?)”,
“(? + ?)/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::PI * ((Math.cos(Math::PI * y) + y * y)/2 + y * x *
y * y)/2)) ** 3”

On Sun, Feb 8, 2009 at 9:33 PM, Daniel M. [email protected] wrote:

@functions = [“Math.sin(Math::PI * ?)”, “Math.cos(Math::PI * ?)”,

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

Daniel M. wrote:

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 :on_size
 evt_paint :on_paint
 evt_idle :on_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, :on_render

 save_bt = Button.new(self, :label => "Save Image")
 butt_sz.add save_bt, 0, Wx::RIGHT, 8
 evt_button save_bt, :on_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],
:pos => [50, 50])
sb = create_status_bar(1)
evt_update_ui sb, :on_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

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 F. provides a desktop application (using wxRuby) 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 image with zero and less cutoff

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 H.
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 F.
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 F.'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 H.
@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
.

# Alex F.
# 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 - 1).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

After running several several iterations Lars’s code was always about
one second faster. I believe this is due to the single eval in place
of the multiple (196,608) Proc#calls. Note that this is on Ruby
1.8.6 and may have different results on 1.9.1.

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. Another possible
technique would be to use ruby2c, or something like it, to create
a C method instead of using Procs or eval.

Let us bask in the beauty of these majestic behemoths, these gentle
giants of the deep:

Christmas box magic
spironator
winter's delight
nebulogue
crystal cavern of the paraboloids
beam and bend

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.


Lars H.

“If anyone disagrees with anything I say, I am quite prepared not only
to
retract it, but also to deny under oath that I ever said it.” -Tom
Lehrer

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)


Lars H.

“If anyone disagrees with anything I say, I am quite prepared not only
to
retract it, but also to deny under oath that I ever said it.” -Tom
Lehrer