Linux Text To Speech with Saved Audio

In my last blog post I described a procedure to find a forgotton PIN for 10 digit mechanical lock boxes where you enter a specific sequence of button presses to efficiently test all the combinations. The generated sequence was supplied in the form of a text file, and although this works, it's a little cumbersome moving your eyes between the buttons and paper all the time. It occurred to me that this would be a lot easier if the numbers were read to me. I then imagined how easy it would be if I had a pair of headphones and the instruction in an audio file on my phone. This seemed like the perfect application for a text to speech application and Linux.

After a little bit of research I decided to use the eSpeak speech synthesizer. It has many options for different voices for different languages and countries and allows quite a bit of customisation of the the way the text is read.

The command below that converts the text in "lockbox.txt" to audio in "lockbox.wav" uses the english voice (-ven), pronounces capital letters in a certain way (-k20), leaves a certain gap between words (-g4), reads back at a certain words per minutes (-s90), and  has a certain pitch (-p29). It's that easy!

espeak -ven -k20 -g4 -s90 -p20 -f lockbox.txt -w lockbox.wav

Before processing the file I made some slight alterations to it by replacing some of the commands in the lock box opening sequence. Originally the commands were zero thought nine, open, and clear. I replaced open with test as it was only one syllable and easier to hear.  It's also important to leave spaces between numbers otherwise it will read 11 as "eleven" instead of "one one".

Here is the instructional WAV file converted to an MP3.  It goes for 30 minutes or so and with a little bit of practice you should be able to follow along at that speed.  If you can't, that's fine, just slow the speed down in your music player.  If you screw up just go back 15 or twenty seconds to catch up.

For the YouTube fans out there, here is another version. It might possibly be the most boring and monotonous video on YouTube. That's my speciality though :-)

To be serious though I'd like to try eSpeak on a Raspberry Pi.  I think it'd be great to read out status updates and events.  Compared to some of the other synthesized voices I've heard it's actually pretty good.

Find & Copy Files While Adding The MD5 Hash To The Filename

Today I thought I'd show you a small script I'm using to decommission an old computer.  To make sure important files weren't deleted I wrote a BASH script that finds all files on a drive with a certain extension and copies them to an external drive.  This works well but sometimes two different files have the same name.  To make sure one doesn't overwrite the other, the file name is appended to its MD5 hash.  I know MD5 has security issues, but it's fine for this.

#!/bin/bash

find /mnt/sda3 -iname '*.pdf' -o -iname '*.svg'|while read line; do
    fname=$(basename "$line")
    md5=$(md5sum "$line" | awk '{print $1}')
    echo "'$line'"
    echo "'$md5'"
    cp -n "$line" /mnt/sdb1/"$md5""$fname"
done

The find command specifies the file types to look for, and where to look, in this case /mnt/sda3.  A while loop then processes each result by copying the file to an external drive (/mnt/sdb1) and changing it's name by adding the md5 hash to the front of it.  Copy is set to not overwrite any duplicate file names quietly. That's fine.  Two files with the same name and MD5 hash are exactly the same so you don't need both copies.

The script is written in BASH because I'm using a live version of Linux to recover the files on the computer.  It's an old Windows computer, but I'd rather do this with Puppy Linux than Vista.  Anyway, if you plan on using the script, do some small tests first.

Controlling a USB Relay with a Raspberry Pi

I love the Raspberry Pi.  It allows me to prototype ideas quickly and without too much effort, but one thing I despise is the GPIO.  Maybe despise is too harsh, but it's a clunky way to interface electronics to what is for all intents and purposes a striped down personal computer.  Don't get me wrong, the GPIO needs to be there and I've made use of it before, but if I want to quickly prototype something I have to spend time figuring out how to use it and then I've got jumper wires all over the place.  I much prefer to use devices that are connected to the USB port.  They can be easily reused on other computers and the final solution is much neater.

Recently I've been toying around with a project that needs to switch a load on and off.  It's a low voltage LED light so nothing too complicated, and I have no problem figuring out how to switch the load via a transistor connected to one of the GPIO pins, but everything gets messy and then I have to do up a small prototype board to mount the parts on.  You know what would come in handy?  A USB controlled relay.  Unsurprisingly someone has already thought of that, they're all over eBay and Aliexpress, some are controlled as USB HID devices and some use the good ol' USB to UART method.  I bought a couple of the USB to UART style devices from www.lctech-inc.com to play around with, and at $10 AUD each it's not worth my time to come up with a custom solution.

Top Side of PCB

There's not much to the module.  As you can see above it's what you'd expect.  A USB connector, a relay, a set of terminal, and a few electronic components.  When plugged in, you send commands to it over a virtual com port to turn the relay on and off.  There are two status LEDs, one to indicate the device has power and another to indicate the relay is active.  Couldn't be easier.

PCB Mounted Relay

The Songle relay used seems to be the de-facto standard in this area of the market.  It's a standard NC/NO relay that can be switched by applying 5 Volts to the coil.  The data sheet isn't too clear but requires 90 mA or less to actuate the relay.  The contact resistance of 100 milliOhm isn't the worst I've seen either.

Between coil & contact - 1500VAC 50/60HZ (1 minute)

Between contacts - 1000VAC 50/60HZ (1 minute)

The relay is sufficiently rated for mains voltage use and has adequate isolation, but I wouldn't use it.  I don't like running mains voltage through random crap I bought off eBay.  Besides that, even if the relay is rated for 10 Amps, I'd be surprised if the tracks on the PCB (hidden under the relay) are up to the job.  The connector definitely looks like it's not rated for that much current.  Based on that, this device will only be used for low voltage medium current applications.

CH340T USB to Serial Controller

As mentioned before, the relay is controlled by sending commands over a USB to serial converter.  In this case a CH340T IC is used.  The only data sheet I could find for this chip was in Chinese and wasn't very helpful.  The Raspberry Pi has the drivers by default and I've read that the latest versions of Windows do as well.  Disappointingly, the serial number of the devices aren't set or are unable to be read in Linux.  This has the side effect that you can't connect two of these relays to a computer and deterministically know which relay is which.  In Linux, if two devices are plugged in at once they enumerate at /dev/ttyUSB0 and /dev/ttyUSB1, but you can't be certain that they enumerate in the same order if you reboot.  I'd hoped that I'd be able to tell them apart by reading the serial number of the USB devices, but as they aren't set, no luck.  It doesn't really matter, I only need to use one of them, but if I did need to use 2 devices I could buy a two relay board.

Edit - Bingo.  I think I've found a way to do it by using the physical mapping of the ports.

pi@raspberrypi ~ $ ls -l /dev/ttyUSB0
crw-rw---T 1 root dialout 188, 0 Jul 22 19:46 /dev/ttyUSB0

pi@raspberrypi ~ $ ls -l /sys/dev/char/188:0
lrwxrwxrwx 1 root root 0 Jul 22 20:01 /sys/dev/char/188:0 -> ../../devices/platform/bcm2708_usb/usb1/1-1/1-1.3/1-1.3.1/1-1.3.1.3/1-1.3.1.3:1.0/ttyUSB0/tty/ttyUSB0

pi@raspberrypi ~ $ lsusb -t
/:  Bus 01.Port 1: Dev 1, Class=root_hub, Driver=dwc_otg/1p, 480M
    |__ Port 1: Dev 2, If 0, Class=hub, Driver=hub/5p, 480M
        |__ Port 1: Dev 3, If 0, Class=vend., Driver=smsc95xx, 480M
        |__ Port 3: Dev 5, If 0, Class=hub, Driver=hub/4p, 480M
            |__ Port 1: Dev 7, If 0, Class=hub, Driver=hub/4p, 480M
                |__ Port 3: Dev 20, If 0, Class=vend., Driver=ch341, 12M
                |__ Port 4: Dev 10, If 0, Class=stor., Driver=usb-storage, 480M
            |__ Port 3: Dev 8, If 0, Class=vend., Driver=r8712u, 480M
        |__ Port 5: Dev 9, If 0, Class=HID, Driver=usbhid, 1.5M

The 1-1.3.1.3:1.0 string describes the physical layout of the USB device.  The device is plugged into port three of the first hub which is plugged into port one of the second hub which is plugged into the Raspberry Pi on port 3.  I've highlighted the important bits to make it a bit clearer.  BTW The reason I use two hubs is because I have a USB 3.0 hub connected to the Pi and the USB 1.0 USB to serial converter needs to be connected to a USB 2.0 hub for the pi to see it.  It's a bug with the Pi.

Bottom Side of PCB

The quality of the board isn't too bad.  All the SMT parts that are automatically placed have nice clean solder joints, but the hand soldered through hole parts leave a lot to be desired.  There's a lot of flux residue on the board and the pads are too small causing the solder to ball up on the leads resulting in weak joints.  I have to give them points for routing out an isolation slot in the board though.

Operation is pretty self evident.  The SOT-23 transistor Q1 is used to apply current to the coil of the relay.  If you look at the top of the board there's also a reverse biased diode placed across the relay coil to stop back EMF spikes.

IC with Markings Scratch Off

The IC on the top handles the USB to serial conversion, but the serial commands still need to be interpreted and used to control the relay.  I assume the IC on the bottom side of the board with its markings removed is some sort of micro-controller to do this.

Controlling the relay is dead simple

You first need to configure the serial port at 9600 baud with a character size of 8 bits.

stty -F /dev/ttyUSB0 speed 9600 cs8

Then you send the command (in hex of course) A0 01 00 A1 to close the contacts

echo -n -e '\xA0\x01\x00\xA1' > /dev/ttyUSB0

Then you send the command A0 01 01 A2 to open the contacts.

echo -n -e '\xA0\x01\x01\xA2' > /dev/ttyUSB0

Testing the Relay

I think these are great for prototyping.  Not only can I use this on a Raspberry Pi, I can use it on a desktop computer or possibly a phone or tablet (not tested).  It's also great for people that are coming from the software world who may not be comfortable interfacing with the GPIO port of the Pi.  They can plug it in and deal with what they know best (software), and within a few minutes control devices like fans, pumps, lights or whatever else you could imagine.

Raspberry Pi USB Webcam Testing

This post will unfortunately be very short.  I was playing around with a webcam connected to a Raspberry Pi, and just as I was starting to make headway I got sick.  I was using a Logitech C525 to take still images.

Logitech C525

I got far enough into the project to realize that the camera didn't have enough resolution for what I wanted to do.  So I need to look at other options.

Just to document what I've done I'll include the commands I was using here.  fswebcam was used to take the still images and uvcdynctrl is used to configure the camera, but it's poorly documented and I'm still trying to figure out how to use it.  You may need to install packages to use these commands.

fswebcam  -r 1920x1080 -s brightness=70% -s gain=50% -S 10 test.jpg
uvcdynctrl -L a.txt
uvcdynctrl -s "Focus (absolute)" 220

I promise I'll do better next week.

Simple Data Backup with Paper Based QR Codes

Let's say you have some important data you want to protect, how do you do it?  The obvious answer is encryption, this then leaves you with the smaller but more manageable problem of protecting the key.  This is really important though, if you loose the key, the data becomes useless.  So it's not uncommon to back it up.  How you want to safeguard the key and where you want to store it aren't the subject of this post, what I want to talk about is a method to ensure the longevity of the data and medium you store it on that's also dead easy to recover.  (It looks hard, but it really isn't)

The first thing to consider when thinking about backups is the medium.  If you archived data on a 5.25 inch floppy 20 years ago, you might have a hard time recovering that today.  First you have to find a disk drive to read the information, then you have to hope that the information stored on the magnetic media hasn't degraded, then you need to be able to read the format of the recovered file.  This doesn't just apply to magnetic media.  To quote the National Archive of Australia about the preservation of physical media:

Recordable CDs and DVDs, USB keys and various forms of flash memory have doubtful long-term reliability and are subject to format and software obsolescence.

So what do you do?  The least worst solution is to store the data on paper.  Print it out and put it somewhere safe.  If you want a bit more safety, print out multiple copies and put them in different locations, it's up to you.  If you want to get all tin foil hat, you could split the data into n pieces that only require k parts to reassemble using Shamir's Secret Sharing algorithm.  For example split the key into 6 parts that only require any 4 pieces to reassemble, then store each portion in a different location.  I'll leave that for another time.    The point is, paper has proven that it can stand the test of time if stored with even the slightest bit of care.  You also don't need need specialised equipment to read it (although it helps).

Once you decide to store the data on paper then comes the question of how you plan to do this.  If the file is binary data you can't just print it as there'll be non printable characters, and unless you choose the right font it can be hard to tell the difference between characters.  E.g. | l 1.  You could print a hex dump of the file, but if you need to recover the file re-entering that data could be a very long process.  The easiest way is to use bar codes, QR codes to be exact.  The ubiquity of QR codes leads me to believe that a major catastrophe will  have to befall humanity before we forget how to read them.  Even if it has to be done by hand, I think they're a stable format.

The process to go from file to printed QR codes and back again is surprisingly simple when you use the right tools.  There are solutions like PaperBack that accomplish a similar goal, but it seems to use it's own barcode format and doesn't use a standard like a QR code.  That brings long term reliability into question.  The method I propose is listed below and uses software with functions that can be performed manually or easily reproduced with other software.

I decided to test this out using a live USB of the TAILS operating system.  The file I've backed up is an example Keepass database I created.  Start by installing the required tools.


    sudo apt-get update
    sudo apt-get install zbar-tools imagemagick qrencode

QRencode is used to create QR codes from terminal input, and that's what we'll be using it for.

Zbar-tools is a flexible easy to use barcode reader that can decode bar codes from an image or webcam.  We're going to use it to scan the data back into the computer.

ImageMagick is like the Swiss army knife of Linux image editing.  This will be used to combine 6 barcodes onto one page ready for printing.

 

Create the Barcodes

Next the input file will be encoded in base 64 format.  This probably isn't needed as QR codes are capable of encoding 8-bit binary data.  I just do it to be safe.  What I did actually wastes space, so do what works best for you.

    base64 keyfile.kdb > keyfile.64

The file is then split into a series of smaller files that can be converted to QR codes.  You can only fit so much data into a QR code.  A couple thousand bytes depending on your encoding and level of error correction.  Once again, use your judgement.

    split -n 6 keyfile.64 Passwords_kdb_64

Encode each portion of the split file as a QR code.  The -l H option gives the maximum amount of error correction in case the bar code is damaged.  I've processed all files using a command line loop.  This is something to generally avoid.

    for file in ./Passwords_kdb_64*; do qrencode -l H -o $file.png < $file; done

We'll then combine 6 QR codes into one image containing 3 rows of 2 codes with the filenames under each code.  If you have more than 6 bar codes don't worry about it, imagmagick will create as many output images as you need.

    montage -label '%f' *.png -geometry '1x1<' -tile 2x3 Passwords_kdb_64.png

Resulting QR codes storing a password database

Recover the Original Data

Scan each of the QR codes in order using zbarcam and redirect the output to a file.  Each code is on a new line with a header identifying the type of code scanned.  The new lines and headers need to be removed.  This was done manually.

    zbarcam > keyfile.64

The last step is to convert the base 64 encoded file back to the original binary file.

    base64 -d keyfile.64 > keyfile.kdb

There you have it, file to QR code and back again.  What I like about this method is that even if all the software used to create the final output image disappears, the encoded data can still be recovered as long as you can decode a QR code and convert a file from base64 back to binary.  Both of these processes are widely known.

You can find all the associated files below.

Anatomy of a Code 128 Bar Code

I've been playing around with bar codes recently, specifically the Code-128 variant.  I'm looking at this particular type because it has some interesting capabilities, the one that interests me the most is the ablity to encode all 128 ASCII characters.  This may seem innocuous, but when you think about how most bar code scanners are connected to computers you'll see the problem. We'll get to that later.

Firstly how do you generate a bar code?  Once again Linux comes to the rescue.  A command called barcode is quite powerful (but hard to google, don't use common names for programs).  It can generate a postscript file containing a wide range of bar code formats.  For example, I've encoded a message with the command below.

barcode -b '103 34 100 65 82 0 67 79 68 69 83 0 65 82 69 0 70 85 78 1 98 77 26 13 9' -e 128raw -o blog.ps

Sample Bar Code

I've used the 128raw mode because it gives me more flexibility and allows me to enter special characters.  If we decode that message using the on-line service at zxing.org we can see the text.  Note that there is a carriage return in the bar code, this places the smiley emoticon on the next line.  You can try to decode it using your phone, but you may not be able to get a good image off the screen.  Some bar code apps don't seem to implement the full standard either, so it may not recognise the carriage return.

Decoded bar code message

So what you say.  Hold your horses I'm getting there.  The decimal numbers I used on the command line can be seen in the results above in hexadecimal.  The program also automatically adds a parity symbol and a stop symbol to the bar code, these are the last two numbers, 1e and 6a.  The parity symbol is calculated by multiplying the code for each symbol by it's zero referenced position in the bar code and then adding them together along with the code for the first symbol.  This is then divided by 103 and the remainder is the parity symbol.  For example.

103 + 1x34 + 2x100 + 3x65 + 4x82 + 5x0 + 6x67 + 7x79 + 8x68 + 9x69 + 10x83 + 11x0 + 12x65 + 13x82 + 14x69 + 15x0 + 16x70 + 17x85 + 18x78 + 19x1 + 20x98 + 21x77 + 22x26 + 23x13 + 24x9 = 15274

15274 / 103 = 148 remainder 30.

This means the parity symbol is 30 or 1E in hex.

Code-128 is extensive, it has three code sets to select from.  The start symbol you select decides which set you use.  Later on in the bar code you can switch to other code sets with a special control symbol.  This can be permanent, like using caps lock on a keyboard, or it can be for the next character only, sort of like the shift key.  I've used both methods in my sample bar code above.

In the image below I've broken down the bar code into sections explaining what each part does.  The patterns for each symbol can be found online, they aren't related to the code number, they've been selected using a specific set of guidelines.  So it's basically a look-up table situation.

The bar code starts and ends with a empty area known as the quiet zone.  The rest is pretty self explanatory.  You should probably check out the Wikipedia page for Code 128 bar codes.  It has a great table of all the code sets.

I've put the pdf of the image below here.  It might be a bit easier to read.  If you open, rotate, and enlarge it so it fill most of your screen, you should be able to scan it with your phone.  It works for me.

Anatomy of a Code 128 Bar Code

So why is this interesting?  Does it have to be?  Most bar code readers connected to computers are seen as a simple keyboard input device.  They don't sanitise their input at all, why would they, they're only expecting numbers and the occasional letter right?  Well, with code-128 you have all the ASCII control characters at your disposal.  I've tried this on the Symbol MC3090 (the bane of my existence) and it recognises and executes the escape and carriage return symbols without hesitation.  I haven't tried the other control characters.  I should also mention that most scanners add a carriage return after each scan, kind of like how you enter data into a text field and press enter to go further.  With just these two symbols you can automate processes with a specially crafted bar code, kind of like the USB rubber ducky that +Hak5 sell.  I don't want to use this for nefarious purposes, I just want to use it to automate some mind numbing tasks, but you could imagine situations like below are possible.

XKCD - Exploits of a mum

Probability of Collecting Multiple Full Sets

Well, it's that time again.  One of the large supermarket chains has released yet another set of collector cards.  This time there are 42 cards to collect compared to the 108 cards of the last campaign, and I thought it'd be interesting to explore some the statistics of cards collecting.  In my last post on this topic, Probability of Collecting a Full Set, I looked at the expected number of cards you need to collect on average before you have a full set of cards.  I suggest reading that article for some background on the problem before preceding any further.

All caught up?  Good.  The question I'm posing this time is how many cards you need to collect on average before you have multiple complete sets?  The inspiration for this question came from hearing about families with multiple children trying to collect a set of cards for each child.  Of course this once again assumes that the trading of cards to other people is disallowed.

Like my first article about this, I initially thought that I had a handle on the problem and the answer would be easy, and once again the maths kicked my butt.  I scraped through by the skin of my teeth last time, but not this time.  I originally thought that the probability of collecting two sets of cards could be found by finding the probability of collecting one set of cards, multiplied by the probability of collecting further sets from the left over cards.  It seems logical, but after running a few quick simulations it was obvious I was wrong.  The problem lies in the fact the the left over cards are not an even distribution.

So, where to now?  Google.  It took some time to find but I eventually found that the problem was called the "double dixie cup problem" and was only solved  by Newman and Shepp in 1960.  I found a good run-down of the problem at http://www.brynmawr.edu/math/people/anmyers/PAPERS/SIGEST_Coupons.pdf that gets me close to solving it analytically, but I just didn't have the time to fully absorb it.  So I listened to that little engineer buried deep inside and decided to cheat by using a Monte Carlo simulation.  Near enough is good enough.  I suppose it's not technically cheating but it does feel a little dirty.

The files associated with this post are located here.  They're a bit rough, but they were only used for working.

Octave was good enough for the job.  It was simple to write a script that repeatedly drew cards and counted how many full sets were drawn.  My simulation was for randomly drawing 1 to 1000 cards and seeing how many full sets of 42 cards were collected.  Each of these simulations was run 10000 times.  The results are shown below.

The Probability of collecting at least n full sets of 42 cards

The familiar shape from the previous article can be seen here.  The noise from the Monte Carlo simulation can also be seen on the graphs.  The results match what I expect.  For example if you were to collect 200 cards, it would be highly unlikely you would have 3 sets (0%), there's a slim chance you'd have 2 sets (10%), but you'd almost certainly have one complete set (90%).  But what is the expected value for a certain number of sets?   This is where things get a little dodgy.  Because of the noise in the simulation it's possible to have negative probabilities in the probability mass function.  (yes I know that it should be a stem plot, but I find it easier to see what's going on this way)  The main point is that a negative probability doesn't make much sense.  The plots below should be a series of smooth humps.  If the Monte Carlo simulation was run for 10 times longer we would get close to approximating a smooth plot.  Even thought the data doesn't make sense it should still be able to be used to approximate the expected value.

The expected number of cards needed to collect 1,2,3,4,5 sets was calculated.

1 set  - 182 cards - 182 cards per set

2 sets - 264 cards - 132 cards per set

3 sets - 337 cards - 112 cards per set

4 sets - 404 cards - 101 cards per set

5 sets - 468 cards -  93 cards per set

As the number of sets to collect increases, I suspect that the number of cards per set would approach a limit of 42 cards per set.

As a sanity check we can analytically calculate the expected number of cards to collect for one set using the equation from the previous post. nH(n), where H represents the harmonic number of n.  42 H(42) = 181.7 this agrees with the result from the Monte Carlo simulation.

So what's the point of all this?  Although it may seem a daunting task to collect a set of cards (you need to collect 182 on average) when you pool resources with other people the number of cards you need to collect decreases.  This can be accomplished within a family or by gathering a group of people to trade with.

Generating a Captcha from the Linux Command Line

I've been playing around with OCR software lately, Tesseract, gOCR, and Ocropus.  I'd like to get all the developers together in a room and lock them in until they come out with something awesome.  Each program has features that I'd like to see in combined package, but for now I'll work with what I have.

Anyway, this post is a bit of a tangent to the whole goal of OCR, recognising text.  Thinking about how to make the job of an OCR program harder can lead to a deeper understanding of the recognition process.  The leading technology to beat OCR is the captcha.  Those annoying little blurred words you have to read to gain access to forums and other sites.  They're there to prove you're a human and not a spam bot.  Through a combination of geometric distortions and filters it makes text hard for computers to read but not humans.

Anyway, for the hell of it I thought it would be nice to be able to generate them from the command line.  So here's what I came up with.  You'll need imagemagick installed as well.

I've put everything together in a script located here.
captcha.sh

Plain text is generated first.

convert -background white -fill black -font FreeSerif-Bold -pointsize 36 label:'all work and\nno play\nmakes Grant\na dull boy' test.png

Text

A wave is added to the text.  Ideally the magnitude and wavelength of the wave would be randomised per line, but a simple uniform wave will do a reasonable job as well.

convert test.png -background white -wave 4x55 test2.png

Wave added

A blur is added to text.

convert test2.png -blur 0x1 test3.png

Blur added

A photocopy filter is then added.  This helps to segment some of the letters.
The photocopy filter was found at www.imagemagick.org/discourse-server/viewtopic.php?f=1&t=14441&start=0

convert test3.png -colorspace gray -contrast-stretch 4%x0% \( +clone -blur 0x3 \) +swap -compose divide -composite -blur 0x1 -unsharp 0x20 test4.png

Photocopy effect added

Command Line Mail Merge For Wedding Invitations With Perl

Recently I've been occupied making wedding invitations, so I haven't really done anything too technical, but during this task I did come across a nice little command line trick that could come in handy.

I like to lay out documents like wedding invitations in Libre Impress, it's basically the open source answer to PowerPoint.  You might think it's weird to do layout like this in a presentation program, but it's simple and it allows me to exactly control text and graphics and how they're positioned on the page.  The one drawback this method has is that I can't find a way to import a guest list into a template and generate a final document, basically a mail merge, but there is a pretty easy work around using the command line.

The invitations I want are really basic.  They're text only and approximately one third the size of an A4 page.  They do however need to be personalised, which makes things a little harder but not impossible.  The first step is to complete one invitation and use a generic place holder for the name of the guest.  Use something that won't appear somewhere else in the file.  I'm using the string GuestName. This invitation is then copied to fit 3 onto the page.  You then duplicate this page as many times as you need to so that there are enough invitations in the file.

For this process to work the file needs to be saved in the flat open document format, fodp.  The format is xml based and is easily read, but you need to use the flat version that's uncompressed.  That way the place holder string, GuestName, is in the file in plain text.

Template Invitation

I've mocked up a quick invitation to demonstrate the process.  I've put a few Easter eggs in the invitation mainly just to amuse myself.

Template Invitation

The next thing you need is a guest list.  A simple text file will suffice.  For this I've created a file that contains three people.  Each person is on a separate line.

guests.txt

Alice

Bob

Eve

What's needed now is a way to replace the place holder string GuestName with names from the guests file.  Each time a string GuestName is found it needs to be replaced with a different guest from the guests file.  It turns out that following perl command is ideal for this.

perl -pe 's/GuestName/chomp($r=<STDIN>);$r/ge' Template.fodp < Guests.txt > Invitations.fodp

I'm still learning how it all works but I'll try and explain the command.

the e option allows the command to be entered on the command line

the p option loops over the command and prints the result

the s command is used to replace the string GuestName with chomp($r=<STDIN>);$r

chomp($r=<STDIN>);$r reads a line from the standard input, the Guest.txt file, and removes the newline character at the end.

the g option means do a global search and replace

the e option indicates to evaluate the replace expression

This is the result.  The place holder has been replaced with the name of the guest.

Final Invitation

I can then use the Invitations.fodp file to generate a pdf and then print out the invitations.  There's one thing to point out though.  Just because a GuestName string is first on the page it doesn't mean it's first in the file.  So the input order may not be maintained exactly, it can be done, but you just need to be aware of it.  For me the order doesn't matter so I'm not concerned about it.

Using Latex To Add Page Numbers and a Binding Offset to PDF Files

I spent the weekend getting my tax documents in order (yeah I know, I live a pretty extreme life).  I like to assemble them into a single PDF file of about 100 pages and keep a digital copy and a produce a bound printed copy.  The bound version is easy to make notes on and show to others.  That's all well and good, but sometimes when binding the printed version, the holes are punched through important information on the side of the pages.  Adding a binding offset solves this problem.

A binding offset is an area on the side of the page that's kept clear for the holes to be punched through.  Offsetting the pages isn't enough though, they also need to be scaled to fit into the smaller area available.  In my case I print on both sides of the paper, this complicates things further as well.  It means the binding offset needs to alternate between the left and right sides of the page on consecutive pages.

I thought that this was pretty much impossible unless you used professional tools, but I soon found out it's ridiculously easy in LaTeX.  While I was at it, I decided to add page numbering to the output file as well.

Below I'll go though a quick exaggerated demonstration of what I mean.  I've started by looking at the 2nd and 3rd pages of a 3 page document.  The page on the left covers the extents of the page.

Example document

After being processed the output file now contains an area in the middle of the page to allow binding.  The page numbers are also added to the bottom of the page opposite the binding area.

Binding offset and page numbers added

The LaTeX file I used to generate the output is below.  It by no means covers all possible situations, PDF files can get complex, and this could break one of the more esoteric features of the standard, so I recommend testing it first.  It worked perfectly for me though.

The code below is also just a starting point, you could also include pages from other PDF files or put multiple pages on one page, it's a highly customisable tool.  This however should be enough of a framework to get you started.  I'm still learning all the tricks myself.

% pdfbind.tex

\documentclass[10pt,a4paper,twoside]{report}
\usepackage[final]{pdfpages}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm]{geometry}
\usepackage{fancyhdr}

\pagestyle{fancy}
\fancyhead{}                       % clear header
\fancyfoot{}                       % clear footer
\fancyfoot[LE,RO]{\Large\thepage}  % add page numbers to pages

% remove bars from top and bottom of page
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}

\begin{document}
\includepdfset{offset=42mm 0cm, pagecommand=\thispagestyle{fancy}}
\includepdf[fitpaper=true,scale=0.6,pages=-]{PDFInputFile.pdf}
\end{document}


Most Efficient Way To Carry Exact Sub 5 Dollar Change in Australian Currency

A quick blog post today.  I wanted to know the most efficient way to carry change with me.  I'm a little OCD and I sometimes like to be able to pay with exact money.  It's easy to get to multiples of 5 dollars with notes, so all we need to know is the combinations of coins you would need to carry to give change up to 5 dollars.  The smallest denomination of Australian currency is the 5 cent coin.  This means that I need to be able to give any amount of change from 5c to 495c in 5c intervals with any combination of coins selected.

The code for today's post can be found here.

I defined efficiency using two metrics, least coins and least weight.  Finding the combination of coins was relatively easy.  I started by finding the combinations of minimum coins with an Octave script.  It took a while and I had to make some optimizations to speed it up, but it got there in the end.  I tried to do the same thing with the minimum weight calculations but it took too long.  So I ported the code over to C++ and made a "purse" class to track the weight of coins in the purse.  This sped up the process significantly.  The results are listed below.

Weight of Australian coins according to the reserve bank

$2    6.60 g

$1    9.00 g

50c  15.55 g

20c  11.30 g

10c   5.65 g

5c    2.83 g

Minimum coins needed to give exact sub $5 change

2x$2, 1x$1, 1x50c, 2x20c, 1x10c, 1x5c

2x$2, 1x$1, 1x50c, 1x20c, 2x10c, 1x5c

1x$2, 2x$1, 1x50c, 2x20c, 1x10c, 1x5c

1x$2, 2x$1, 1x50c, 1x20c, 2x10c, 1x5c

Minimum weight of coins to give exact sub $5 change

2x$2, 1x$1, 1x50c, 0x20c, 4x10c, 1x5c

2x$2, 1x$1, 1x50c, 1x20c, 2x10c, 1x5c

By a happy coincidence there is an intersection between the two groups.  The following combination satisfies the minimum weight and minimum coins condition.  8 coins and 63.18 g.

2x$2, 1x$1, 1x50c, 1x20c, 2x10c, 1x5c

Most Efficient Way To Carry Exact Sub 5 Dollar Change in Australian Currency

It might only be a fraction of a gram but it's one of those things I just have to know even though it doesn't really matter.

Harmonic Elimination PWM Comparison and Uses

I've been doing a series about how to calculate the switching times of harmonic elimination PWM waveforms and I thought it was time to compare HEPWM to another method and look at how it can be used.  To catch up on the theory so far, have a look at the rest of the series.

Fourier Series of a Quarter-Wave Symmetric Pulsed Waveform 

Fourier Series of Harmonic Elimination PWM Waveforms

Octave Code For Generating Harmonic Elimination PWM Waveforms

All the code for this post can be found here.

A simple well known method for generating PWM waveforms is to compare a sawtooth wave to the desired signal and set the value of the PWM waveform high whenever the signal is higher than the sawtooth wave.  It gives reasonably good results, but I'd like to know how it compares to the HEPWM method when it comes to controlling harmonics.  When you're switching power loads there will be switching losses.  Ideally you want to minimise the amount of switching you do, but it comes with the price of not being able to control harmonic distortion as well.  It's one of those engineering trade-offs you have to make based on your design.  So to be fair and compare apples with apples, both the PWM and HEPWM waveforms below each have 40 switching transitions per cycle.  This means that switching losses should be equal and we can compare them using other metrics.

A half cycle of the PWM waveform is generated as mentioned above.  This and an inverted copy of it are concatenated to produce a full wave.

Although the generated waveform is inverted (my bad) it's hard to tell it apart from the HEPWM wave below.  Upon closer inspection you can see that the switching times are different, but on first glance everything looks the same.

Below is the real test.  The HEPWM waveform knocks out the harmonics right up to the 20th harmonic, whereas the basic PWM signal only kills the harmonics up to the 10th before they start creeping up.  This may be fine for what you're doing, but if you absolutely need to control certain harmonics, HEPWM is the way to go.  It might mean that your output filter is cheaper, or lighter, or takes up less space.  If you need to control a specific harmonic, HEPWM can do it.  It may be an issue with EMC you have to take care of.  If for some reason the geometry of the enclosure you're using is letting a certain frequency through, taking care of that in software rather than adding more shielding is going to save yourself a headache.

HEPWM also allows you to easily control the magnitude of the output while controlling harmonics.  If you're making a power inverter, ideally you want to run at nearly full magnitude to get the most out of your design, but you can still trim the output if you need to.  The graph below shows how you can pre-compute switching time for different magnitudes.  While running, the magnitude can be changed by selecting the set of switching times for the desired output magnitude.

HEPWM has some disadvantages, it's only useful in situations where you can pre-calculate the waveform.  It's not going to work with a signal like audio.  It's suited to power inverters and other niche applications where you want to reduce harmonics of a simple waveform like 50/60 Hz mains power.  It may not be for everything, but when the situation does call for it you've now got the right tool for the job.

To learn more I encourage you to read this thesis by Yu Yang.  It gives an overview of some other switching techniques and goes into a little more depth on some of the details.

Evaluation of New HEPWM Patterns in HVDC Applications - Bad Link

Cached backup I have of the above file.

Probability of Collecting a Full Set

The frenzy surrounding the Aussie Animal cards promotion got me thinking.  How many randomly collected cards would you need to collect before you had the whole set?  More specifically, if you were randomly given n cards what's the probability of having the full set.  I'm going to use the 108 card Aussie Animal set as an example.

All the files associated with this post can be found here.

When I initially came up with the idea for this post I thought it would be easy.  Turns out I was wrong.  A couple of quick simulations showed my understanding of the problem wasn't right, but after a little research I was back on track.  It did take me 2 days though.

The problem is mathematically the same as a well known problem called The Coupon Collector's Problem.  In this context the problem can be restated in the following way:

"Suppose that there are k different coupons, equally likely, from which coupons are being collected with replacement.  What's the probability that after n sample trials the complete set of k coupons is collected."

The formula to calculate this is deceptively simple.

There are k^n different ways to select the coupons. The next step is to figure out how many of those result in a complete set being collected.  I'm still getting my head around this, but it comes down to something called Stirling numbers of the second kind that equal the number of ways to partition a set of n objects into k non-empty subsets.  This suits the problem.  The collected coupons need to partitioned into k sets and none of these sets can be empty, i.e. the coupon hasn't been collected.  This number is represented as S(n,k).  This number has to multiplied by k!, as there are this many ways to arrange the sets.

This is where things got hard, I tried GNU Octave to calculate the results but as there was no built in function I tried to roll my own. I used an explicit formula for S(n,k) but that required numbers like 1000! to be calculated.  A number this large is just too big for Octave to handle.  I came up with a way to do all the calculations using the log of the number, but there was a precision problem for low values of n. Although with more time I could have got it working, I scrapped it and moved to Maxima, a computer algebra system that uses arbitrary precision (should have started there).  A couple of lines of code later I had my result.  The data was imported into Libre Calc to graph the solution.

Back to the Aussie Animal cards.  I've chosen a couple of data points to illustrate the how hard it can be to collect the set.

n = 200,    P = 8.99E-11

n = 400,    P = 0.0620

n = 600,    P = 0.662

n = 800,    P = 0.938

n = 1000,    P = 0.990

After collecting 600 cards you still only have a 66.2% chance that you've collected a set.

The expected value of how many cards you need to collect before you have a set is given by the formula nH(n), where H(n) is the harmonic number of n.  In our case this is equivalent to 108*H(108) = 568.5  To double check this, the Probability Density Function of the above data was generated to manually calculate the Expected number.  I get 557.  Given it was done in a spreadsheet with low precision data only up to n=1000, I'm pretty happy they agree that much.

This shows that without trading cards with other people it can be difficult to collect an entire set.  It assumes that all cards are equally likely and independent.  This may not be the case but it's not unreasonable to assume it is.

I'm glad I tackled this problem, learning about Stirling numbers made it worthwhile.  I now have another mathematical tool under my belt.  Would've been nice to have heard about them in statistics class, but there's only so much you can cover.

Octave Code For Generating Harmonic Elimination PWM Waveforms

I've finally sorted out the code to generate PWM waveforms that you'd use to control an electronic device such as an H-bridge driver.  I must warn you this is engineering coding, error checking is non existent, and things may be a little rough around the edges, but it'll get you started on a version for your specific problem.  It should also be noted that some problems can't be solved.  If the magnitudes are set too high you could end up in a situation where there is more power in the waves spectrum than can be in the actual waveform.  In that case the solver will do its best to minimise the objective function but it won't actually find a solution.

The code will generate a waveform that you can scale to the desired frequency.  By entering two vectors, one containing the harmonics of the output waveform that you want to control, and the second containing the magnitude of the harmonics, a set of switching times will be returned.  It's also important to remember that all even harmonics are automatically zeroed due to the quarter-wave symmetry of the waveform.

As a demonstration I've generated the example waveform below that sets the first harmonic magnitude to 0.5 and all odd harmonics up to the 31st to zero.

The code for this demonstration can be found here.

HEPWM Waveform

The FFT of the above waveform is shown below.

FFT of a HEPWM Waveform

Although the magnitude of the first harmonic is set to 0.5 the FFT shows two peaks of 0.25.  This is due to the nature of the FFT showing positive and negative frequency.  These combine to give the 0.5 magnitude.  All the harmonics up to the 31st are however zeroed.

There are still a couple aspects of this method I'd like to investigate, but all the heavy lifting is done and we can get into some practical aspects of the process.

Making Detecting the Angle of Rotated Text More Robust

In my last post I demonstrated how to find the angle of rotated printed text using image processing.  I also mentioned a couple of ways to make the process more robust.  In this post I'll expand on what I meant with a demonstration.

The code and image files associated with this post can be found here.

The basis for this method is that we are only looking for large values in the Radon Transform, this indicates a feature like a line or row of text.  We are also looking for bright features in the gradient of the transform.  This indicates the transition point between a row of text and the white space below it.  By masking out lower values in these two steps, the data points that are more relevant should be highlighted.

The process starts out exactly the same as in my first demonstration, we need to generate the radon transform of the input image.

Radon Transform from 70 to 110 degrees

As before, a gradient of the radon transform also needs to be calculated.

Vertical Image Gradient

This is where things start to change.  A binary mask is generated from the radon transform.  This will only show bright points in the transform and remove other points that are most likely false positives.  The threshold has been set to 20 percent of the maximum value in the radon transform.  A permissive value but it still removes a lot of false positives.

Thresholded Radon Transform

The same process is applied to the gradient image using a a threshold of 10 percent of the maximum value of the gradient.

Thresholded Gradient Image

The two masks are then applied to the original Radon transform by multiplying the masks with the transform.

Masked Radon Transform

I've created the false colour image below to help demonstrate the process a little better.  The red channel of the image is the mask from the original radon transform.  The Green channel is the mask generated from the gradient image.  The Blue channel is the original Radon Transform.  The only areas that will be visible in the final masked image are areas where the two masks align.  This means that the red and green channel will coincide and create a yellow pixel.  This means the only sections visible in the final image are those that are shades of yellow.  As the intensity of the blue Radon Transform becomes brighter it will turn the yellow pixel white.  (click to enlarge the image)

Coloured Transform

As before the images are vertically sumed to create an array of intensities.  The peak intensity will be the rotation angle of the text.  As a comparison, I've show the intensity arrays for the masked and unmasked versions of the process below.

Gradient Intensity vs Text Rotation Angle - Unmasked

Gradient Intensity vs Text Rotation Angle - Masked

The magnitude of the peaks in the graphs above doesn't matter, what's important is the ratio of the peak to the next largest feature.  In the unmasked version the peak is around 74000 and the next largest peak is around 34000, a ratio of about 2.2.  In the masked version the peak is around 29000 and the next largest peak is around 7000, a ratio of about 4.1.  This make picking the correct feature a lot easier and gives more confidence in the result, which as before comes out at 0.6 degrees.

This is by no means the best that could be done.  I picked the threshold values out of thin air.  They could be determined by trial and error for a particular type of document or they could be dynamic and adjust to the input image.  I'll leave that as an exercise for the reader :-)