How to get smooth transitions between colors while keeping sharp edges?

Question

I am trying to smooth out images of colored wave forms while trying to keep sharp edges.

Example of a source image:

I've had some limited success using surface blur, while the transitions between each color is smoother I am loosing sharpness on edges:

Is there a technique, filter of effect I could employ to get such result ?

EDIT

here's the result thanks to @boblet

EDIT 2

I've found a pseudo-alternative that somewhat achieves the same goal though it's not as pretty.

The thing is to draw gradient lines with the middle color (0.5) being a little darker.

Actually this is the poor man's alternative until I can get hold of the surface blur algorithm which doesn't seem as easy to implement as it sounds.

Answer 1

Paint.net and Gimp

Below is a detailed example of how to do this in Photoshop. However, both Gimp and paint.net have the same capabilities, though the tools have slightly different names.

The Gimp equivalent to Photoshops magic wand tool is Fuzzy select. You should be able to achieve the same result.

photoshop.

Select the white background with the magic wand tool You do this by first clicking on the top part of the white, hold shift and then select the bottom part.

Right click, and choose select inverse from the menu.

Choose the blur tool,

and blur your colours into each other to your hearts content.