Generating Stippled Images with Stiptacular

A few weeks ago I posted about how to generate stippled images from regular input images. The code was garbage at the time so I've improved it and posted it for people to use or learn from.  I only just remembered why I started this project. I found the StippleGen program from EvilMadScientist (EMS) but it was written in the processing development environment which I didn't have much luck with. I thought it'd be great to have a Python version out there as well and along the way added my own tweaks.

• Better initial distribution of seed points via a PseudoHilbert Curve
• Dithering to make points distribute more evenly
• A term that sets how much points are attracted to darker areas

Since I'm using trying to replicate the work of EMS It thought I'd use their test image of Grace Kelly. Their interface is beautiful and has a few bells and whistles that mine doesn't because I figured that I could do any pre-processing in something like GIMP.

Grace Kelly test image 943x834

For an initial test I'll use 2000 points with 5 rounds of dithering and 5 rounds without dithering.  The simplest way to think of the adjustment parameter is like a contrast setting.  In this case it is three. This will cube the value of each pixel and re-scale all the data to a 0-255 range.

number_of_points = 2000
dot_radius = 2.5
non_dithering_iterations = 5
dithering_iterations = 5
adjustment_parameter = 3

Processing the image with the above settings took about 90 seconds and produces the following SVG file.

Large Grace Kelly test image - 2000 points

To demonstrate another quirk I noticed, take a look at the smaller image below.  It contains the same number of dots as the image above.  As a matter of fact, it's the exact same image just scaled down. However the dots start to look more like a face. So scale is important.  If I were to do an 8 foot print of this for a wall in my house it wouldn't look that good because I couldn't get far enough away from it for the image to emerge. I would need to use more points.

Small Grace Kelly test image - 2000 points

The image below uses 30000 points and takes about 25 minutes to generate. Writing this in something like C would help a lot..  Calculating the centroids of the Voronoi regions can be done in parallel to speed things up as well.

Grace Kelly test image - 30000 points

You may notice that some of the darker regions look a little strange. This is caused by points aligning, as can be seen in the close up below. This can be solved by reducing the number of points, dropping the adjustment parameter so the area isn't so crowded, performing more dithering steps, or just enlarging the source image before processing.

Alignment artefacts

.

Get the Code!

You'll also need to install the PseudoHilbert Curve Module for Stiptacular to work.  It's a dependency that I'd like to eventually remove, but for now it's needed.

The posts below are my train of thought while developing this script.  It may help if you get a bit lost.

Voronoi Stippling
Entry and Exit Points for Space Filling Paths on a Grid
Hilbert Curve Generation With Lookup Tables
Converting Binary to Gray Code with XOR
Calculating Hilbert Curve Coordinates
Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 1
Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 2
Efficient Centroid Calculation for Discrete Areas
Generating Seed Points For Voronoi Stippling
Generating Stippled Images with Stiptacular

Here's a picture of a Atlantis during the STS-132 shuttle launch made of 30000 points. To infinity and beyond!

STS-132

I wish I had the time to do an even deeper dive on this type of problem.

Reflection, Transmission, and Attenuation of a Propagating Electromagnetic Pulse

I've been toying around with some old code from uni that models a propagating electromagnetic field, and I thought I'd do some simulations to illustrate how fields propagate and interact with matter.  Usually I'd include the code I used to do the simulations, but as it was for an assignment I don't know if I should.  Do your own homework kids :-).  However if you need more info don't be afraid to ask.

Each simulation is of a gaussian pulse in free space propagating from the left impacting a lossy dielectric shown in green.  The simulations are in 1D making thing easy and are analogous to a signal propagating in a transmission line.

The relative permittivity of the material in all simulations is 7, so let's say it's rubber.  For the first simulation I've set the conductivity to 0 S/m, this means it's lossless.

The are several things to observe in the animation below.  The initial interaction with the material creates a transmitted and reflected wave.  The reflected portion is inverted, this happens when an electromagnetic wave crosses an interface from a low to high dielectric material.  It can also be seen that the speed of the wave decreases as it travels through the material.  Anyone familiar with transmission lines would be familiar with this and know it as velocity factor.   The velocity factor is equal to the inverse square root of the relative dielectric constant.  In this case that's equal to 37.8 percent.  The wave continues on and is transmitted and reflected again.  This time the reflection isn't inverted, this is because the wave is travelling from a high dielectric material to a low one. The transmitted portion of this wave increases at this point, which seems counter intuitive, but you have to remember we're looking at the electric field, not the power flow which is also related to the dielectric constant of the material.

Electromagnetic wave impacting a lossless dielectric

The reflection diagram helps to visualise the propagation of the wave.  White indicates positive waves, while black indicates negative waves.  Time progresses as you go down the graph.  The change in velocity of the wave in the dielectric medium is evident here.

Electromagnetic wave impacting a lossless dielectric

For this simulation I have set the conductivity to 10 S/m.  It's not a metal but it's conductive enough to demonstrate some things.  To give a point of comparison, sea water is 4.8 S/m.   Basically the wave is completely reflected.  A small portion of it is transmitted but it quickly dissipates.  It also gives me a chance to tell you how I remember how a wave is reflected from a conductor.  Electric field is analogous to voltage, and because a conductor effectively short circuits the wave, the electric field at the interface has to be zero.  If the material in the simulation was a perfect electric conductor this is the behaviour we would see.  For the electric field to be zero the reflected wave has to be the negative of the incident wave.  When these are added you end up with zero electric field at the boundary.  So the electric field of a wave reflected from a conductor is inverted.

Electromagnetic wave impacting a high loss dielectric

Electromagnetic wave impacting a high loss dielectric

For the final simulation I've set the conductivity to 0.15 S/m.  Lets say it's a conductive rubber of some sort.  The simulation allows us to see the how the wave is attenuated as it travels through the material.  Some does make it through, but it's reduced in magnitude.

Electromagnetic wave impacting a lossy dielectric

Electromagnetic wave impacting a lossy dielectric

Using a Spacetime Diagram to Understand the Frequency Shift of Doppler Radar

I recently did a tear down of a cheap doppler radar module that I'd bought on ebay.  It's used to sense the speed of an object by measuring the frequency shift of a radar signal that bounces off it.  When it came time to work out the speed, I found out that my initial understanding of the problem was wrong.  I had trouble getting a intuitive picture of how the signal was changed until I drew a few diagrams.  They helped me a lot and I thought they might be able to help someone else visualise Doppler radar frequency shift.

Get the PDF here

Page1

Page 2

Doppler Radar Module

I've been doing a bit research into speed signs after I spotted one at the local university.  Initially it wasn't clear how they worked, but after a bit of googling it became clear they were radar based.  Normally I'd be happy and leave at that, but when you can get a simple Doppler radar module from eBay for under ten dollars, I had to have one to play around with.

Radar Module

They're nothing special, they have a limited range and aren't too accurate, so they can't be used to fine someone for speeding because it wouldn't stand up legally.  They can however be used for purposes like letting drivers know if they're doing over the speed limit, if you are under the speed limit you get a smiley face.  Something I initially thought wouldn't work, but it turns out to be rather effective.  Recently they've started appearing in our local area around schools where the speed limit drops from 60 km/h to 40 km/h between the hours of 2pm and 4pm on school days and they seem to be making a difference.

Image Source - http://www.couriermail.com.au/questnews/north/earn-a-smiley-face-by-slowing-down-as-you-drive-or-ride-past-newmarket-state-school/story-fn8m0rl4-1226647642745

If you're unaware of how Doppler radar speed measurement works it's pretty simple.  The device transmits a radio signal at a particular frequency, as that signal is reflected off a moving object its frequency is slightly changed.  The unit measures this reflected signal and uses the frequency difference between the transmitted and received signals to determine the speed of the object.  This usually occurs in the microwave region.  My module for instance operates at around 10 GHz.  The specs according to eBay are below.

Transmitter

Frequency : 10.525GHz
Frequency Setting Accuracy : 3MHz
Power Output (Min.) : 13dBm EIRP
Operating Voltage : +5V +/- 0.25V
Operating Current (CW): 60mA max, 37mA typical
Harmonic Emissions: -10dBm

Receiver

Sensitivity (10dB S/N ratio) in 3Hz to 80Hz band width : -86dBm
Noise in 3Hz to 80Hz band width : 10μV
Antenna Gain : 8dBi
E Plane 3dB Beamwidth : 36'.
H Plane 3dB Beamwidth: 72'

eBay specs
There wasn't a data sheet for this module, but this one I found on Google seems to be an exact match.

Now you know the principle behind it, back to the radar module.  The bottom of the board is mostly ground plane with two patch antennas, the one on the left is the transmitter an the one on the right is the receiver.  I think the two areas without solder mask in the middle of the ground plane are low inductance paths to ground for the transistor in the oscillator.

Radar Module Bottom Side

RF and microwave in general is something I don't know a lot about, but I think I can work out the general operation of the board.  Of course with the frequency of operation in the 10 GHz neighbourhood the board is covered with the obligatory microstrip stubs and filters.  I'd love to learn how that stuff works but for now it's akin to magic.  The transistor on the bottom right of the board appears to be the oscillator.  I can't find out much about the white cylindrical block, but according to http://www.shfmicro.com/gunn.htm it appears to be a Barium-titanate "puck" to stabilise the frequency.  Given the topography of the circuit, it looks to be part of the feed-back circuit of the oscillator even though it doesn't seem to be electrically connected to the circuit.  I'm going to put that down to some sort of RF coupling, or as I call it jiggery pokery.

EDIT:  A helpful commenter has informed me that the white object is a dielectric resonator.  Things make more sense now.

The output of the oscillator goes up to the middle on the left and off to the transmitting antenna.  It's also fed to what I believe to the mixer located near the centre.  The mixer also receives an input from the receiving antenna on the right.  The output is fed to IF signal at the top left.  This in theory should contain a signal close to DC and a frequency close to 20 GHz.  I doubt the 20 GHz will  make it out though, it's possibly already filtered out by the radial stub near the top of the board.  The PCB material will also play a part.  Given the price of the module it's like to have high dielectric losses at high frequencies.

Radar Module Top Side

The top of the board is covered with an aluminium shielding can that has what appears to be a tuning slug that is aligned with the white object on the board.

Shielding Can with Tuning Slug

Microwave Transistor

Possible Frequency Stabilizer

Mixer

Board hooked up for testing.  5 Volt DC applied, signal output is displayed on an oscilloscope.

5 volt supply connected, output to oscilloscope

I initially started testing it by moving a piece of plastic toward and away from the PCB, I quickly realised that it wasn't going to reflect microwaves and wouldn't work.  (What was I thinking).  Luckily I had a sheet of aluminium checker plate lying around.

Checker Plate

That did the job.  The signal below is the result as I moved the sheet toward the device.  The frequency will be proportional to the speed and the magnitude will be related to the size of the reflecting object and its distance from the module.  As a side note the module uses 40 mA in standard operation.

Radar Module Output as Metal Plate Approaches it

Let's just take a quick estimate of the signal above.  Near the centre of the plot the period of the waveform is around 5ms, giving a frequency of 200 Hz.

Example Doppler Equations

3 m/s corresponds to what I would have estimated the speed to be.  It's not exact, but with a bit of work it could make something interesting.  I don't have anything in mind, but something may come to me.  One thing that is cool however is amateur radio operators modulating the current of the transmitter to vary the output frequency to transmit radio signals over 20 miles.  Have a look here for more information. http://www.shfmicro.com/gunn.htm

Testing Transmission Line Theory On A Roll Of Coaxial Cable

I recently bought a roll of coaxial cabling to do some work at my grandmother's place and thought I could use it to experimentally confirm transmission line theory.  It's one of those topics that you do a lot of reading about, but you may never actually encounter in the real world.  I can still remember when I was told about transmission lines and everything became clear.  Of course a voltage couldn't appear instantaneously at the end of a cable. Information can't travel faster than the speed of light.  The signal has to travel along the cable and to make things more interesting can get reflected depending on how the cable is terminated.  I've done the math, I've done the simulations, but I still want to do the experiment.

My experiment isn't anything fancy.  I terminated the roll of coaxial cable with an f connector and connected it to an oscilloscope via an adapter and a BNC tee.  The other side of the tee was then conencted to a function generator outputting a 10 volt pulse.  The other end of the coaxial cable wasn't terminated, so in theory the pulse should reach the end of the cable and be completely reflected.  The waveform on the scope was observed to see if this happened.  I'm not trying to take super accurate measurements, I only want to get a quick overview of the physics involved.

Test Set-up

If the experiment is simplified it can be represented as the following schematic.  A function generator with a 50 ohm output impedance is connected to a coaxial cable with a 75 ohm characteristic impedance.

Experiment Schematic

I'm not sure of the quality of my cable, from what I've heard it's average to good.  It's suitable for cable television installations, so I guess it's not designed for extremely long runs, but should give decent results.

305m Reel of Quad Shield RG6 Coaxial cable

Below is the output of the generator without the cable connected.  The peak voltage of the pulses is around 10 volts and they also have relatively short rise and fall times.

Generator Output. No-load

After the cable was connected a second pulse appears, this is assumed to be the reflection of the initial pulse.  The magnitude of the first pulse is also reduced due to the loading of the cable.  As the signal is applied to the cable energy starts to flow down it.  The rate at which the energy flows down the cable can be replicated by replacing it with a resistor equal to it's characteristic impedance.  This forms a simple voltage divider with the function generator's output impedance.  The cable voltage would be equal to Vin*Zo/(Zo+Rg) = 10*75/(75+50) = 6 Volts.  This agrees with the observed voltage of the initial peak in the screen shot below.

The magnitude of the reflected pulse is a little bit beyond this experiment.  Theoretically it can be calculated, but I think it needs to be simulated for a real world application like this.  Simple calculations assume an ideal conductor, whereas in reality the conductor is non uniform an has imperfections.  This creates small impedance mismatches all along the cable causing transmission and and reflection at each point.  I think this is measured by the Structural Return Loss (SRL).  I suspect that this is the reason the pulses have rising tops.  As the pulse travels down the cable a portion of the signal is continually reflected back to the generator.  I can't be sure without some simulations but I think this is what is happening.

Initial Pulse and Reflected pulse

There's another experiment that can be easily done with this arrangement.  The velocity factor of the coaxial cable can be calculated.  This is how fast the signal travels down the cable as a fraction of the speed of light.  From the waveform below it can be seen that the elapsed time between the rising edge of the initial pulse and the the rising edge of the reflected pulse is 2.4 us.  As the pulse had to do a round trip on a 305 m length of cable we know it travelled 610 m.  This gives a velocity of 250000 km/s.  As a fraction of the speed of light this is equal to 85%, closely agreeing with the 82% value from the cable's datasheet, also shown below.  This confirms that the second pulse is the reflection.

Round Trip Time

Cable Data Sheet

Another phenomenon to observe is what happens when the transmitted pulse overlaps the reflected pulse. This is show in the waveform below.  As the duration of the pulse is increased, it will collide with the reflected pulse.  As the reflected and initial pulses collide they add constructively.  There are 3 distinct sections to the plot below.  The first section is the initial pulse, the second section is the sum of the initial and reflected pulse and the third section is only the reflected pulse.

Reflected Pulse colliding with Transmitted pulse

I like doing small tests like this.  Experimentally confirming physics principles is useful as it shows the difference between ideal models and the real world.  An interesting quirk like the structural return loss of the cable is something I wouldn't have known about without actual taking measurements.

Testing Capacitors From a Dead Modem

A couple weeks back I started having problems with my ADSL2+ internet connection.  A lot of dropouts and slow downloads, and at times speeds lower than dial-up.  I knew what my connection was capable of, before the problems started I was getting around 14 Mb/s downloads and after it was around 3 Mb/s at best, so I knew that the distance from the phone exchange had nothing to do with my issues.

After several phone calls to my provider, TPG, and going though their frustrating isolation tests and checking cables they confirmed that there was fault on the line and they'd send a technician out to investigate.  While waiting, I decided to replace the modem.  It was old and I wanted to make sure that the problem wasn't on my end.  After removing the old modem and setting up the new one, the connection was still slow, so I decided to reconnect the old one until the issue was sorted.  After turning it on all I got was flashing lights.  I'd had this problem before, leave the modem on for a couple of minutes, power cycle it, and it would start working.  This time, no luck, it just wouldn't start.  I put the new modem back in and threw the old one in the corner for the time being.  I suspected the capacitors in it were dead.

Old NetComm NB6Plus4W modem

Old NetComm NB6Plus4W modem

Old NetComm NB6Plus4W modem

After the technician came out and fixed the line fault, I still didn't have a decent connection.  One more phone call to TPG and things were back to normal.  The last phone call involved a troubleshooting step that required me to plug my phone line into the network port to reset my firmware.  Yeah, it sounded dodgy to me too, there can be over 100 V on the phone line when ringing, but after two weeks of almost no internet connection I was willing to sacrifice a modem on the off chance it'd work.  I figured the designers of these things anticipate that at some point someone would accidentally plug the phone line into the network port and there would be appropriate protection in place.  Surprisingly this worked.  It doesn't sit well with me though.

I still don't know what the real problem with the connection was, it's unusual for two things to fail at once.  If I had to guess, I'd say that the suspected dead capacitors in the modem created noise on the line that caused it to switch to a low speed profile.  As for TPG finding a fault and getting it fixed, if you look long enough you'll find something wrong and something to fix, but to be honest I don't really know, I'm just happy things are working again.  That old modem was bugging me though, I needed to know what went wrong.  Time for a tear down.

Let's go through and see what does what on the PCB.

1. Power supply.  It takes a 12V AC input, rectifies and filters it to about 15.5 Volts DC.  Two MP1410 step down converters provide 1.8 and 3.3 Volt rails
2. Ethernet sockets and associated isolation transformers.  I suppose plugging in a phone cable wouldn't actually hurt the device
3. USB input.  You can see the traces coming out of it and heading to the main processor
4. Phone line input and transformer
5. Broadcom BCM5325EKQMG Ethernet switch
6. 7805 5 Volt regulator and Broadcom 6301KSG ADSL line driver
7. Elpida DS1216AGTA 128 Mbit SDRAM - working memory
8. Broadcom BCM6348KPBG single chip ADSL2+ controller
9. Samsung k8d3216UBC 32 Mbit Flash Memory - non volatile memory to hold software
10. Broadcom BCM4318KFBG 802.11 b/g transceiver
11. Skyworks SE2521A60 Wireless LAN front end.  Power amplifier and associated RF functions

Modem PCB Top Side

What's underneath? Nothing much, just some passives and transistors by the look of it.  At the top of the board you can see where heat from the main processor on the other side has discoloured the PCB over time.

Modem PCB Bottom Side

My initial assessment of why the modem stopped working was that the electrolytic capacitors had dried out and weren't doing their job any more.  I based this diagnosis on what I knew about the modem.  It was at least 4 years old and had operated pretty much non stop since then.  With a maximum power draw of 12W and only passive cooling, it did get quite warm.  These are perfect conditions for capacitor failure either by an increase in their ESR or by a decrease in value.  I also suspected bad caps when I tried to start it and the lights on the front kept flashing in a manner that indicated that it was powering up but a power glitch caused it to reset and start again.  From a cursory visual inspection it seemed this was the case.  Everywhere I looked I saw bulging capacitors, a sure sign of a capacitor on it's last legs.  One of them was positioned right against the heat sink of a voltage regulator.  I suppose that was to keep it warm if it got cold.  Facepalm.

Bulging Capacitor

Bulging Capacitor

Bulging Capacitor

Bulging Capacitor

Bulging Capacitor

After seeing the state of the capacitors I decided to test them to see what kind of condition they were really in.  I removed 5 to test their capacitance and ESR values.  I don't have any equipment designed to specifically measure capacitor parameters so I thought I'd see what I could do with what was lying around.

Using the information found on Geoff Graham's Measuing ESR page I thought I could put together a quick and easy way to test capacitor ESR.  All that was needed was to apply a quick voltage pulse to a capacitor under test through a resistor.  Any ESR will cause the voltage across the capacitor to immediately rise but will be too fast to charge the capacitor.  The size of the voltage step can be used to calculate the capacitor's ESR. This is when I found out my function generator is pretty much useless.  It can't do pulses, only square waves with duty cycles above 50%.  So I scrapped that idea and built a tester myself with an old development board and a few components out of my junk box.

An AVR development board was used to create the waveforms required for testing.  Its output was connected to a logic inverter on some perf board.  The inverter gives a better rise time, giving a nice sharp transition to drive the capacitor under test.  A buffer would be better but I didn't have one, so I used the inverter and then inverted the pulse in software.  One more stage is needed though, the logic inverter doesn't have a large enough drive current to charge the capacitor fast enough.  To fix that a transistor push-pull stage was put on the output to increase the current capacity.

Micro-controller Driven Test Rig

Before testing the ESR of the capacitors I thought I'd see if their values had degraded much.  I started by testing a 22uF tantalum control capacitor that I was reasonably sure was in good working order.  For this test I set the development board to generate a square wave with a period of 500 ms.  By taking measurements from the charge discharge curve of the capacitor through a 100 ohm resistor I could determine the capacitor's value.

22uF Tantalum Control Capacitor Under Test

RC Step Response 22 uF capacitor, 100 ohm resistor

RC Step Response 22 uF capacitor, 100 ohm resistor

The voltage across a capacitor in an RC circuit when driven with a step response can be described by the following equation.

As the resistor and capcitor are driven from a push pull BJT output stage the capacitor will never get to 0 volts.  This doesn't matter though, you just have to consider the change in voltage of the step and the change in voltage of the capacitor. With a bit of rearrangement it can be shown that the time taken for the capacitor voltage to rise 50% of the step voltage is equal to.

We know the resistor value, we can measure the time, this means we can calculate the capacitance.

From the scope screen shot above it can be seen that the capacitor takes about 1.5 ms to reach the 50% voltage point when charged through a 100 ohm resistor.  This gives a capacitance of about 21.6 uF which is in agreeance with the components markings.  So I know my test rig gives usable results. By no means are they accurate or precise, but they give me an idea of what's happening.  Now to test the five capacitors from the modem.  I've shown screen shots of one of the tests below.

2200uF Electrolytic Capacitor Under Test

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

Capacitor Number	Capacitor Value (uF)	Temperature Rating (C)	Step Size (V)	50% rise time (us)	Calculated Capacitance (uF)
1	2200	105	4.1	275	3.96
2	1000	105	3.7	600	8.65
3	1000	85	3.8	200	2.88
4	1000	85	3.8	350	5.04
5	2200	105	3.8	2000	28.8

The results weren't great.  None of the capacitors really followed a standard exponential RC charge discharge curve.  No matter how much I turned the timebase down I couldn't see a step caused by ESR. It was more of an asymptotic curve.  I think there's more going on here than just an increase in ESR or a drop in value.  Although I don't think it's entirely valid, the previous formula was applied to calculate the capacitance.

Maybe an LCR meter could give me a better idea, but one thing is certain, capacitors that big shouldn't charge that fast.  Although the I think the calculated capacitance is probably wrong because the situation is more complex than I first thought, they definitely shouldn't be that low.

I could have tried replacing the capacitors, but decent quality parts would be pricey and I was in the market for a modem with more flexibility.  The modem I bought to replace this one is only a stop gap.  In time I'd like to get a modem from a company like Billion with a built in VPN.  This would allow me to use a mobile device more securely when I'm on the go.

What's clear is that the capacitors in the modem have definitely failed.  It does seem to be a common problem with this model.  This would cause the voltage rails to become unstable, causing soft failures at first followed by more obvious symptoms like complete failure of the device.  This was most likely caused by spending extended periods at high temperatures.  Although some of the capacitors probably had too low of a temperature rating for a passively cooled device with no heatsinks that operated in a city where 40 degree days aren't uncommon, they did last a significant amount of time, and any attempt to improve the lifetime of the modem with better components, active cooling, or more heatsink would have increased its price tag.