300 random spheres added and normalized

As part of my PhD research I had to implement discrete Sibson interpolation , to do some nifty interpolation. Sibson interpolation is a scheme based on areas of Voroni regions which can be quite complex. But for the discrete case Park et al presents a nice and simple scheme.

1. For each pixel find the nearest neighbor ( of the points you are interpolating between)
   1. Draw a circle with radius = distance(this, nearest neighbor)
2. Normalize, divide each raster color with the number of circles that contributed.

The first, and very importantly functional, implementation of the circle drawing routine was a simple double loop. It worked, but it nagged me that it was slow and it seemed like a fun problem. So I went home an wrote a small program to draw circles and test the speed. The top image show such a case.

You can find the code on github:  https://github.com/jtpedersen/draw-circles

I made a small test framework just to have some fun trying to optimize the drawing. The authors of the paper use a shader and somewhat similar to this transforms each point into a quad and only draws within the circle. I needed to do it on CPU for now.

Drawing 512^2 random circles in this manner takes my laptop around 10 seconds.  It is obviously to slow and inefficient. The method it self is not good, as it access the same pixels multiple times to addColor. So the first trick was to turn it in to a two-stage algorithm. First note where each circle starts and ends on each row.  Now the central loop does not depend on the area but the circumference of the circle.  The second stage is scanning through the temporary buffer and accumulating the results.

To calculate the start and end point we scan the y axis and for each row we determine the x-offset. The formula for the circle is (x – x0)^2 + (y-yo)^2 = r^2. We can assume x0 and y0 is zero, the circle is centered at (0,0) for the calculation and then do the offset calculation afterwards. Since we now y we just have to solve for x, diff = sqrt(r^2-x^2). In the extra buffer we then store color at (y, xo -diff) and -color ar (y, xo+diff+1), so scanning is adding the value in the extra buffer into an accumulator and writing it into the same place in  output buffer. I also made a version with two extra buffers, one for enterPixel the other for exit, but this is not necessary.

The circumference of circles, before the scan.

Even though this is a two-stage algorithm it is much faster. It is down to  655 msec. For the case with 512^2 random circles. It is worth noting that the radius of the circles is restricted to 10% of the width of the image, as this seemed like a fairly large value, yet still realistic.

I could not come up with a better algorithm, maybe you can?

A little complexity analysis. Assume that worst case is all circles have a radius that is so large that we have to paint all pixels in a n*n grid. The naive version will then for m updates do m * n^2 and the smarter version will only do m * 2 *n + n^2 work. if we assume that m ~ n^2 we have that the naive algorithm runs in O(n^2 * n^2) = O(n^4) and the smart in just O( n^2 * 2 * n + n^2) = O(n^3).

Since I ran out of good ideas I went for the next best thing, trying to optimize. This would be the ideal time to start a profiler, I like Kcachegrind. But i had inserted timings and an idea of a culprit, the square root. So I did the next best thing commented the line out and observed the incredible speed up. Down to 200 msec. However we still have to calculate the value.

There are clever algorithms for integer square root, but I did have the advantage of knowing the range and that it was rather small. All values would be less than the largest radius^2, for these test cases that would be < (512 * .1)^2 = 2621.4< 2^13 = 8192. So the simple thing to try was to use a lookup table low and behold we are up to 277 msec but we actually calculate the right value.

Since memory access is always best to do in order and the randomness of the input really destroys locality, i thought that it could be interesting to see what would happen if the points were in order. So as i quick hack i sorted the points based on the y coordinate of the center of the circles. This cut off another 100 msecs and yet sorting took only 20 msecs, so a net gain of 80 msecs. (for the interpolation case the input will actually be sorted)

This is where i stopped, but what should be the next step? I compile with gcc and use -O3. I quick look at the assembly shows that gcc uses sse instructions, but this could perhaps be pursued? I initially thought that i could get a speed up from scanning in parallel, but my timings says that scanning only takes few msecs. I would like to parallelize the setting the values, but it is not as trivial as there are obvious concurrency issues. Maybe just a mutex pr row and everything would be fine.

Anyhow down from 10 secs to just shy of .2 sec is quite alright in my book. Could it be improved? What would be the next step? generate all events (start /stop) put them in a list, sort and scan through this instead of a n*n buffer?

It was the ability to change what prefix to remove. As i live in Denmark, whenever i make a call on a land-line there is no reason to dial +45, which is the danish country code. Actually the plus is converted into 00 as well.

But Eli needed the prefix 08 to be removed.

And i guess that there are a lot of other prefixes that could be removed and + shouldn’t always be converted to 00. So I decided to implement this feature.

Whats new

• It now remembers your settings
• It possible to choose a prefix to remove
• its possible to decide what + should be replaced by.
• I slapped a GPL V3 license on it

The files

dtmfdialer jad file

dtmfdialer jar file

dtmfdialer source code

Unfortunately it wasn’t just a 5 min hack. There were two major challenges.

Persistence

In J2me access to the filesystem is restricted and requires all sorts of security permissions, but every application has access to a “RecordStore”. The RecordStore (RMS) only allows byte[] to be stored, so you have to marshall/unmarshall every piece of data at quite a low level. I haven’t persisted any data in the first version, as this is indeed tedious to work with. But not having persistence for a prefix remover functionality wouldn’t be of any use. You would have to enter the same data every time you used the application and then it would be faster to just edit the number to call.

Netbeans mobility pack

It was supposed to be so eays.

But the floweditor somehow did mess up and didn’t generate the code, so the flow diagram and the sourcecode were out of sync, and i didn’t see any way to “resync”/”regenerate code/diagram”. This was cause for a lot of frustrations.

Originally i made it with netbeans so compiling and editing the generated code were best done in netbeans. But if i ever were to mess with it again i would seriosly consider “porting” it to J2me Polish or just “vanillia” j2me. As i really really don’t like the netbeans editor.

update : Eli found a bug in the prefix substitution, i fixed and uploaded the new version (June 27, 2009, 21:17)

The project as it looks so far :
I ordered a set with steppers, motor-control and psu from ebay, and I’m waiting for it to arrive(The seller said 10-12 days, so maybe if I am lucky next week). It should be 1.7NM motors and a more or less “plug’n’play” set.

I intend to drive the motors using a old computer running linuxcnc. linuxcnc looks real neat, but might prove to be hard to set up.

The construction

I am looking at two set of plans at the moment

How-to-Make-a-Three-Axis-CNC-Machine-Cheaply

This was the building plan that made me decide that this was a possible task. But there are some issues with the construction I don’t like, especially that it uses belts. They are hard to find and they are not cheap.

JGRO’s plans

This is a free diy plan. it can be found here : http://www.cncroutersource.com/cnc-router-plans.html

It uses threaded rod instead of belts. And the overall construction looks simpler.

Materials

Although I do want to do “fabbing” using a extruder at first I think that there will be enough work for a couple of days getting the mechanics and electronics up and running. Just as there is a lot to learn about g-code and all sorts of 3dmodelling.

To begin with I want to cut using a dremel tool, maybe a more powerful spindle(?) to be able to cut wood – if I have enough power in the steppers.

You might ask what do you want to make / “fab” with a 3 axis cnc machine?  I can come up with a lot of different small things like “coat hanger”, “coffee filter”, “PCBs” but I guess that it just boils down to: ” I think its a very fascinating technology and want to play with it”

I googled around but weren’t able to find such a utility. But i did find cli-sip client pjsua, based on pjsip. Its posible to use it in conjunction with a shell script.

Scripting

jacob@vps:~./control.sh sip:108329@foobar.com "wake up you lazy bastard!"
Is the basic usage i wanted to have. In order to get this functionality there are two steps.

Generating wav file

I ust use text2wave, from festival, which is available as a package on ubuntu.
echo $2 | text2wave - -o message.wav

$2 to use the second argument, and pipe it to text2wave. Let text2wave read sdtin and output a file message.wav

Call and play the wav file

pjsua_app --config-file=test.conf --play-file message.wav $1
Here the magic is in the conf file. Its a rather straightforward to use, and the documentation is good.

# we don't want the host's audio device
--null-audio
# SIP parameters
--realm domain.com
--registrar sip:number@domain.dk # DNS SRV, or FQDN
--username USERNAME
--password PASS
# default of 55 will be rejected as being too short by sipX
--reg-timeout 3600
# auto-answer all calls with "200 OK"
--auto-answer 200
# automatically loop incoming RTP to outgoing RTP
--auto-loop
# mix WAV file into the audio stream
--auto-play
--auto-loop
--duration=60

This is based on a config file i found somewhere, can’t remember where. There a a lot of other options, pjsua handles nat quite nicely as well. It was easy to test it at my homebox, behind a router, just be sure to set an external ip address.

Now this will call and play the message, but it wont stop pjsua. It will just sit around waiting for someone to call. I couldn’t find any nice way to handle this, but since pjsua reads stdin for commands, it possible to pipe commands to it.
echo "sleep 60000 q" | pjsua_app --config-file=test.conf --play-file message.wav $1
So sleep for 60 seconds, then accept the next input from stdin, the “q”uit command.

Generally this configuration is set for 1 minute, it might be necessary to tweak this.

Frustrations

There is/were a bug in the tarball, that meant that it wouldn’t run if it couldn’t find a soundcard, since it should run on a vps this is quite annoying. But in the svn version its solved, so if you want to do something like this, use the svn version. Other than this installation is straightforward.

When working with cron, remember to use full paths. In the control.sh script the better solution were to add a cd working directory, in order to have all the paths correct. This were quite annoying to debug, as the script would run from the shell. And just fail when added to the crontab. Furthermore mails from crontab were delayed, so i couldn’t see the output. I did get someone to look over my shoulder and spot the bug.

That doesn’t mean that i haven’t been coding small hacks, just that i haven’t posted them. But now is probably a good time to show some of the stuff.

As the title suggest it has something to do with processing.org. I have been using processing on and off for some time. Its is really nice when you want to make a quick hack, or as its called in processing a “sketch”.

In no particular order here is some of the fun stuff made using processing.

General remarks

The following sketches and their sourcecode have served as small hacks, hence don’t expect nice comments or optimal algorithms…

shrinkImage

It is possible to remove the line from a picture representing the least amount of information. The algorithm evaluates every pixels “weight” as the absolute difference between the different color channels (r,g,b). And then finds the “lightest path” from the bottom to the top.

This means that “prominent features” won’t be removed or change size when shrinking the image. Here the definition of “prominent features” is high difference in colors between the neighboring pixels.

Have a look at shrinkImage

Room for optimizations :

Eventhough its quite quick at calculating the weights and finding the lightest path, it does so in every iteration. Letting it use a bit more memory and just recalculate the changes when removing a line should speed it up. I found a huge speedup when just having an array with the weights from the last and current line, when calculation the path, so not only would saving all weights require a bit more memory it would also slow down the first calculation. But I’m sure it would give a significant speed up in the next iterations, and a lot of +-1 frustrations

helloFoo

There a some quick getting to know processing hacks, this is one off the. helloFoo

One of the very cool things about processing is the ability to use openGL, so originally this sketch uses openGL. But applets and openGL isn’t exactly the best combination. It can be done, but since it doesn’t work for me (firefox, linux openJDK JRE) i just converted it to standard java graphics. And the effort required to do this, is remove an import and don’t say setup(400,400, OPENGL) but just setup(400,400). This is trivially true the other way around. If you want to use openGL its quite easy.

The sketch is just bouncing balls, when going away from openGL I reduced the size and number of balls, in order to get a decent animation speed.

FooIII

Again used openGl originally FooIII

Some satellites rotating around some satellites rotating around some ….

sndHello

yes sketches tend to have silly names : sndHello

From Clifford Pickovers  book : Computers, Pattern, Chaos, and Beauty – graphics from an unseen world (p 39 section 4.3 snowflakes from   sound)
Draw symmetrically and in “polar form” the fft of the sound, hence creating snowflakes based on the sound.
Music by David Rovics
Choppy sound I had some problems with the sound when run as an applet. You might have better luck using the jar directly or by downloading the sourcecode and running it with processing

Slit-scanning

The former applet relied on an external library for the sound, ther are quite a few libraries available. I did use GSvideo to hook up my crappy webcam and do some video effects. I experimented with slit-scanning in different ways.Unfortunately this won’t run as an applet and it might only run on Linux.

By creating a cube of the images, where the z-axis represents time, its possible to play back different parts of the movie from different layers in time. Which makes for some quite interesting and dizzing effects.

For example a time buble where playback is delayed around a “bulge in the timespace continuum” :s (a video of some guy playing with it (timebuble1.avi) some sourcecode for a similar effect where the mouse pointer moves the buble (TimeCube.pde) another more “traditional slitscan” (CamWarpTime.pde) .

In general there is plenty of room to fiddle with the code, there a functions like selectSlice or initQueues where its decided how to slice time. its great fun to play with..

The very short desctiption :

inspiration from an example of homogeneous coordinates in my linear algebra book and lectures about lineartransforms.

There is a jar, with sourcecode, if you want to se it “live” or twiddle with it.

tegneri

I made have generated quite some random attractors.

Now I need to find the most beautiful ones, and I need your help!

I have created a voting system, where 3 attractors line up and you select the best one. The votes are then accumulated and and overall top 10 is generated.

Strange Attractor wars

It is heavily inspired by kittenwars.com.

I have been hacking away on this far to long. But expect an article with more details on Strange attractors and probably more features in the “war” application. (like top 100, biggest looser, most victorious etc).

Now just go and make some votes

I got around to hacking some code together for a simple DTMF dialer on the mobile.

Its functional and simple. Enter a number, click ok and it will play the correct sequence of tones. It’s even possible to tweak the duration and pauses.

I have only tested it on my own Nokia 6300, but as far as I can tell it should run on most java enabled mobile phones.

Here are the jad and jar files. If you want to run the program download them to your mobile and have fun.

• dtmf jad
• dtmf jar

At the moment it converts + to 00 and removes +45, as this is appropriate for a danish setting.

Here is the sourcecode if you need to make changes.

DTMF sourcecode

Using Netbeans

I used netbeans 6.0.1 and it was a mixed pleasure. Creating the the flow using a drag’n’drop interface, is well nice for something small and simple as this, but I found that it soon got frustrating. There’s no API to look in, and you have to use the mouse all the time.

This is the basic flow of the midlet. It was very quick to set this up, and it were indeed a pleasure to start with. Somewhere along the way a made a mistake, which the flowdesigner and codegenerator couldn’t handle. And no matter what I tried I couldn’t get rid of it, I knew exactly what i was. I had misnamed a variable and managed to let the generated code go into a never-ending recursion. (something along the lines of: private TextField foo() { return new TextField(Foo);} ). But no matter what I tried it just wouldn’t get back to normal. In the end I just created a new project, remade the flow stuff to what you see above, and copied a few functions over.

And the flowdesigner is quick to work with, but I get a nagging suspicion that if you are going to make something a little more complicated than this it will be an annoyance. You might know exactly where and what to change in the source code, but do you remember where to point, click and edit in the designerinterface? Another critique is that even when you know what to do, your workflow gets abruptted by having to constantly shift hands between keyboard and mouse.

To Netbeans defence i must say that I am used to using Eclipse, and changing to another IDE is in it self a frustrating experience. Whats the shortcut for blah, where do I set this. And its quite possible that I just didn’t know enough about Netbeans structure and shortcuts to feel at home.

Credit goes out to : openclipart.org for the image of the phone and dialabc for the soundfiles.

image from the museum.

From the leaflet: “Welcome as a patient to the Psychiatric Hospital”
About the Psychiatric Hospital

The highly regarded Copenhagen architect, Gotlieb Bindsboll, built the Jyske Asylum in the middle of the 19th Century. The inspiration for the building, with its crow step gables and many beautiful courtrooms, was taken from the typical Danish manor houses. Its position, with views over the Århus bay was in keeping with the contemporary view of the healing benefits of beauty. The hospital became known as a model institution for the treatment of the mentally ill, also on a European scale. The first part of the hospital was completed in 1852 and it was extended several times over the next fifty years.

The phone is from 1951 1955 and the “electronics” looks aged but in surprisingly good condition. My first plan for it were to gut it, and put a more modern telephone inside, so I could use it for voip. But when I saw that it were in good condition, I thought it would be a shame to kill it entirely.

So I wanted to see whether it would be possible to use it as it is.

For the voip connection i have a PAP2T linksys adaptor (pap), its quite simple to work with. Plug in power and ethernet cable and configure it with a voip service-provider. Initially I used a normal phone to make sure that i had a working setup, before trying to get the rotary phone to work. The normal phone were quite easy to setup and it “just works”.

For the rotary phone there is still some difficulties. But i have managed to get something to work, and I am working on the rest.

First of all i had to change to paps power output to maximum, else it wouldn’t ring the bells. I am still in the process of fiddling with settings for impedance and/or input gain. The problem is that the microphone volume is very low, and if I just turn the input gain up it turns up for the noise as well. It isn’t a problem for me as i have a crisp and clear sound, but apparently it’s a pain to whomever I am talking to. So something has to be done.

Then there is the dialing. A rotary phone dials by using pulse dialing, which in essence means that it disconnects/hangs up, in short intervals as a method of counting the numbers. But any modern voip-adaptor (at least a cheap one) can only function using DTMF. That’s were sending different tones means different numbers. Which basically means that it is enough to send the correct sequence of tones into the microphone in order to dial a number.

I had seen some applets for dialling they did work with the modern telephone, but the rotary phone with its microphone troubles had to get something more. I had success using “DTMF-dial” (from the ubuntu repositories), because it was possible to tweak the duration of tones and pauses.

Next step, as holding the phone to the PC-speaker every time i need to make a phone call, is not an option, were to make a midlet, that’s a mobile applet. A java program for the mobile. Using the mobile as a dialer may seem awkward, but it already holds all my contacts and the voip is a great deal cheaper. I have a midlet at the moment that is at the proof of concept stage. It can dial and I am able to take a number from my address-book dial it using DTMF. It still needs a bit of polishing, but its mostly cosmetic, maybe a list of recent calls would be a nice feature to implement.

soon to come:

• Nice pictures of the phone, and the electronics.
• Some software for DTMF dialing on the mobile and a bit about devolping a simple mobile application in netbeans.

The first flash assignment were to create a picture slide show, with captions and a soundtrack. Using the Adobe flash gui its very easy, drag and drop “programming”.

But as Richard Stallman says “its not a matter of convenience, but of ethics”. So I went looking for replacements. In another course I had no problems using octave instead of matlab, so should this be any different? Yes, unfortunately it seems that its very difficult to get the needed features in free software, well at least in the given timeframe.

HaXe is able to compile to swf, as well as doing a lot of other nifty stuff. I just learnt about it recently from this video.

I didn’t manage to make the entire assignment, (yet?) in haxe, but i did make this :
flash presentation(5MB+)

UPDATE

I did manage to add sound and captions.

So how did I do it?

Well first of all i installed haxe and swfmill. Haxe is able to use the actionsscript api and swfmill can create resources so your are able to refference them in you haxe code.Here is the recipe i used to create this slideshow.

1. create a xml file for swfmill, in order to create a resources for the haxe code.This i something like

 <movie width="480" height="480" framerate="25">

   <frame>

      <library><clip id="img1" import="library/newton001Slide_.png"/>

unfortunately swfmill isn’t able to add sound to a library, so that had to be loaded directly from a file. I had some trouble getting it to function on the server but i think that adding “-D network-sandbox” to the haxe compilation might have done something. ???

2. run swfmill, thats swfmill simple slides.xml slides.swf

now i had linkage names for the image files, and could add them to the movieClip.

3. Create file SlideShow.hx

The main part. The basic haxe syntax is pretty straightforward, but since it uses the actionscript api it were mostly a question of getting a hang of actionscript. I did however strugle a bit with making a anonymous function, for the sounds onLoad. I used “static inline function sndStart(succes){…}” , its a wee bit diffrent than what i would do in java. but it works.

3. compile.

make a “make file” for haxe, compile.hxml

-swf test.swf

-main SlideShow

-swf-lib slides.swf

-swf-header 480:480:25:FFFFFF

-D network-sandbox

The last part -D is a conditional flag and as far as i can tell it shouldn’t do anything, but a saw it in Fmp3PlayerHx and when i added it the sound seemed to work from the server, using a URL :s :s

4. run haxe compile.hxml

5. display the pretty result. (try not to go crazy when wordpress decides to help you format the html code….), at first i tried embedding the flash in this post, but wordpress kept on changing the code, apparently if you add code and have newlines between the tags it throws in a couple og <p> tags …..

Now its on a separate page, then you don’t have to download the 5 mb flash file just to view the page, and I can use wordpress with out getting too frustrated.

sourcecode slideShow.hx

The music is “the free software song” this version is by Jono Bacon , and I personally prefer it to the version by Richard Stallman