Sunday, October 15, 2017

ABC Logo Lissajous Curve

Over the last couple of days I've seen a few people mention how similar the ABC Australian logo is to the new Disney Movies Anywhere service. I don't know much about the legal side of things, but I thought an explanation of why the ABC logo looks the way it does might be interesting.

The shape of logo is called a Lissajous figure or curve. The shape is generated by a parametric equation where the x and y coordinates are sinusoidal.  The frequency and phase relationship between the two equations for x and y determine the shape.  In the case of the ABC logo, the frequency of the y coordinate is 3 times that of the x coordinate and there is a 90 degree phase shift (I'll clarify this later) applied the y equation.

$$$x=cos(t)$$$ and $$$y=cos(3t+\pi/2)$$$

To make things clearer I've put together an animation. As the vertical bar sweeps across the screen it will intersect the x and y equations. The y coordinate is projected across and the x coordinate is projected across and up. The Lissajous figure is drawn where the project lines intersect.

Tracing a 3:1 Lissajous Curve x=cos(t)  y=cos(3t + $$$\pi$$$/2)
The phase shift is also very important to the shape. In the animation below you can see how the it changes as the phase shift is cycled across all possible values from 0 to $$$2\pi$$$.

Changing the phase relationship of a Lissajous Curve x=cos(t) y =cos(3t + $$$\delta$$$)
These curves aren't just a mathematical curiosity, they have a real world application. They used to be a very important tool for broadcast engineers. If two signals are feed into an oscilloscope (a tool that plots electrical waveforms) while it's in x-y mode, the Lissajous curve on the screen will reveal things about the signals.

The first thing to notice is that the number of horizontal and vertical lobes indicates the ratio of the frequencies. If the ratio of frequencies is rational (can be expressed as the ratio of two integers) the curve will be stationary. If not, it will slowly rotate like the second animation. If the two signal are meant to be locked together so that one is exactly 3 times the other like in the example above but the curve rotates, you know there's a problem. The rotation rate of the curve tells the engineer the deviation from the desired frequency. There are simple lookup tables like the one below that show what the curves should look like for a given phase shift and frequency ratio.

Frequency Ratios and Phase Differences

Earlier I said I'd elaborate on phase shift. The main thing to note is that you are working with two different frequencies.  1 degree of phase shift on one signal will take a different amount of time to 1 degree of phase shift on the other.  So it's important to not just note that there is a phase shift of 30 degrees, you have to specify what waveform you are referring to.  That's why a lot of the table results may be different from what you measure.  In a mathematical sense, it also makes a difference if you are talking about sine or cosine signal as one is a phase shifted version of the other.

Just to clear up another thing as well. The second animation is generated by plotting a waveform frame and then changing the phase an repeating this process. This is what makes it rotate. By chance though, this is exactly what you would see if the frequencies weren't locked together. A time varying phase is no different to making a small deviation to the frequency.

Wednesday, August 16, 2017

Suburban Fulfilment Centre

A few weeks ago I was thinking about online grocery fulfilment and different ways of getting stock to customers faster. I had some ideas about the form factor of the facilities involved and thought I'd write about what I'm calling the Suburban Fulfilment Centre (SFC).

There are many important factors that add up to make a good online shopping experience, but when you strip away everything else, customers want a service that is fast, has a large range of products, and has reasonable fees. An important way to accomplish this is to do something that I call "tightening the loop". The time between a customer buying something and the stock being replenished and available for reorder needs to be as small as possible. It's important to have stock for customers to buy, but if you don't have a stock quickly flowing in to replace it you've failed.

Unlike regular parcel delivery, grocery shipments have some constraints that makes the process more challenging. Parts of the order need to be refrigerated, and some parts have a short shelf life. You can't just put a bottle of milk and some bananas in a box with some bubble wrap and ship it across the country in a cost effective manner. These constraints mean you need to have a supply of stock close to the final destination. If you're astute, you may have noticed that I just described a grocery store. Let's play with that idea.

What's really needed is a supermarket that's able to supply a much larger range, but keeping the online shopping model at the forefront of the planning. Around my local area a lot of 5 storey apartments are being built and I started to wonder if these could fill the roll. If an fulfilment centre with the exact same external appearance was built with a ground level drive-through, the only noticeable difference would be traffic to and from the centre. It would blend into the surrounding area and supplant current facilities that don't fit into the surrounds. To explore the idea, I selected a local set of apartments to study and run some numbers on.

Apartment Building
Apartment Building
To further illustrate the idea, I've included some screenshots from StreetView of a storage company in Brisbane with a McDonald's wedged underneath it. The drive-though runs under the building and is similar to what I pictured for an ideal pick up location.

Drive Through
Ground Level Drive Through
Although I've been talking about a drive through for customers picking up orders, it would also serve as a loading dock for receiving stock and dispatching orders that get delivered directly to customers. Obviously there needs to be separation of different kinds of traffic for safety reasons, but there would be multiple drive-through lanes and when needed, one could be shut down and isolated for a delivery or dispatch.

Drive Through
Ground Level Drive Through
So how much space do we have to play with? The apartment shown above has a gross floor area of 419 m².

Floor Plan
Apartment Floor Plan
The height of the levels 1 to 4 is 11.2 meters. This gives us a volume of 4700 m³. But what does that actually mean? How much range can we fit in that volume?

Apartment Elevation
Apartment Height
Let's look at the floor plan of a supermarket and do some visualisation exercises. It should be immediately obvious that there is a lot of unused floor space, what's not seen is that of the space that is utilised a lot of it is empty space. Next time you go shopping look at the displays and imagine what would happen if all the shelving suddenly vanished. How big would the pile of stock on the floor be? Typically shelves are utilised fully side to side, but vertically they might be only 70% full, and front to back they might be only 70% full on average. Therefore it's not outrageous to suggest that volumetrically, the shelves are only half full.

Floor Plan
Supermarket Floor Plan
How much does a supermarket hold though. Let's do some Fermi approximation.

10 aisles × 2 meters high × 1 meter wide × 15 meters long × half full = 150 m³

Let's say that the grocery department holds two thirds of all the stock in a store.  This means that in total a store holds 225 m³ of product.

Just as a sanity check, that's equivalent to the volume of 92 × 1.8 m high Australian pallets. From my experience that sounds about right to fill a store from empty.

Another important number to remember is that an average supermarket stocks about 15 thousand different items. This would mean that each item on average occupies about 15 L of space. That may seem wrong but some items need much more and some need a lot less, and remember this is the raw volume of the stock, not shelf space.

Let's look at how much space a purpose built fulfilment facility uses. The image below is of a supermarket dark store without customers. This makes it easier to fulfil online orders by staff manually picking individual orders.  As you can see though, not much of the facility is actually occupied. It's a giant waste of space. I can understand why they've done it though. It's a cheap and easy way to get started with online fulfilment without going all in automating the process. I'm still surprised that going all in is questioned. Amazon did it and look at how well it worked out for them.

Current Dark Store Layout
I keep talking about wasted space but what's the alternative? The system in the animation below is an automated tote storage and retrieval system by Dematic. There's wasted space in this example but the design can be optimised to use a lot more space of a building. It transfers the stock to a picking station where an operator assembles orders. This configuration is referred to as a goods to person solution, which means operators don't have to walk to assemble orders. It also reduces bending, reaching, and lifting.

The other important advantage of this is that each tote is traceable and for perishable food, its use by date is also known and action can be taken to clear the stock before it's wasted.

Tote storage system
Dematic Multi-Shuttle System
Some items are so small that they may only fill part of a tote, in these cases a divider is used. In some cases items are too large to fit and will need to be stored in a bulk handling area. Over time a manufacturer may also alter their products to be tote friendly as it may offer a cost saving.

Tote storage system
Dematic Multi-Shuttle System
Let's circle back to the concept of the suburban fulfilment centre with a 4700 m³ volume. Let's say only one third of it is used for a stock management system like the one by Dematic above, and of that third only one half of it is full. That's a raw stock volume of  783 m³. If each item takes up 15 L of space that means the building can hold about 52 thousand items. There's a lot of assumptions in my calculations and the number could be much higher or lower but I think it's worth investigating further. Especially when you take into consideration that extra items above what would normally be stocked in a supermarket would most likely take less space due to lower demand.

Each SFC doesn't need to hold the full range a service offers either. It may only need to hold 30 thousand core items and 20 thousand supplemental items. There may be multiple facilities reasonably close to each other that may hold different supplemental items and a few times a day small vans move stock between them.

The SFC would also be used to supply nearby retail spaces of the company with low demand items. that are a bit esoteric. Ask yourself if a supermarket really needs that many packets of black dye on the shelf or are they only there because that's how many come in a box. It's a waste of space and it's money sitting on the shelf.

Another consideration is the capacity of the drive through. If two lanes are open for 14 hours a day and a pick up take 2 minutes, that's 840 customers per day at capacity.  If they each take a 200 L trolley load that's 168 m³ of stock per day which the facility can easily hold.

I do actually have a serious reason for thinking about this problem. The less interaction staff have with stock the better. At the moment it's common practice for stock to arrive in store on a pallet like the one seen below. Think about that for a moment, at the warehouse people manually assemble these pallets and at the store people manually disassemble them. The only outcome of this process is people with injuries from a lifetime of manual labour. Finding meaningful replacement work for these people is important but I believe that a company has a moral obligation to minimise injuries where possible.

Pallet of stock

Finally to give you an idea of what the inside of what one of these facilities look like, the animation below is of a warehouse that does basically the same thing, only with pallets. Nothing I'm talking about is new, it's just a scaled down version of what's currently happening.

44m High, 12000 pallet, Jungheinrich High Rack Warehouse
I should point out that all ideas are my own and not those of my employer.  I've also purposefully used images publicly available online instead of using my own.

Saturday, August 5, 2017

Riveting Plywood to Metal

Today I'll give you a quick rundown of my experiment riveting aluminium to plywood.

2.8 mm Plywood Riveted to 1.4 mm Aluminium
If you've read my blog before you may know I like boxes and storage solutions.  I made some prototype storage boxes last year out of 19 mm pine and plywood, and since then they have been used quiet a lot.  The main problem I have with them is they are heavy, use more material than is really needed, and are complicated to make.  I wanted to simplify things and for inspiration I turned to an ammunition case that I have from 1958.  It's made from ply and is riveted together with metal edges.  All the components themselves are not specifically strong, but when assembled the case is rather sturdy.

Ammunition Box
Ammunition Box
I happened to find some brass rivets on AliExpress that are used for material, you may be wearing some now. Have a look at your jeans.  The type I purchased are called double capped, meaning they have flat rivets on both sides.  They consist of a cap and post that are pressed together.

Brass Rivet Cap
I ordered these because they were listed as 10 mm long.  I thought that this would mean I could join materials up to 10 mm (leaving room for compression of course).  Unfortunately I was mistaken. The length of the post is 10 mm but this only leaves 8.5 mm space for materials, and after compression of the rivets only about 5-6 mm are feasible.

Brass Rivet Post
Rivet Test Compression
For my test I planned to join some 6 mm ply to a piece of aluminium angle, but because the rivets are smaller than I planned I used 3 mm plywood.  Two 3 mm holes were drilled into the aluminium and the posts were inserted. A hole slightly larger (about 3.75 mm) was drilled in the ply, the caps inserted and the the rivets clipped together. For the final compression step no fancy tools were used. They were placed in a vice and I squashed the hell out of them.

The results speak for themselves. I think they look awesome and they will not budge.
Aluminium Side
The dark wood and brass look nice together gives the strength I need. I think I'm on to something.
Plywood Side
I'm not actually building a box in this post. This is just a test, and besides I don't think the size of box I want to make will work with 3 mm ply. I need slightly bigger rivets. So now we wait the standard 2 or 3 weeks for a shipment from China. :-(

There are plenty of designs for storage boxes that may be better than mine, but what I'm aiming for is a good strength to weight ratio box that can be easily assembled by people at home without exotic materials and tools.  The idea is that if you want a box you go and buy some ply and metal and use rivets you've purchased.

Friday, June 16, 2017

Merge A Data Set With A Template File To Generate Output Files

For something I'm working on I need to be able to create a large number of files by filling in fields in a template file with entries from a data set. You'd think that would be easy with Linux but I couldn't find a way to do it. (This will be where people tell me a thousand different ways to do it) I didn't think what I wanted was complicated so I wrote SimpleMerge to take care of it. It is a basic Python script that takes data from a tab delimited data file and fills in data fields in a template file.

The first row of the data file are the field identifiers to find and replace and the other rows are just data. This file can be easily generated from a spreadsheet program. The template file contains the structure of the file you intend to create, just with field identifiers in the place of real data.

I haven't done extensive testing on the program but it seems to work fine.  It handles UTF-8 file encoding and maintains the line endings of the template file for both UNIX and Windows systems. The following command generates the two files File1.txt and File2.txt as seen in the block diagram below. template.txt Data.txt

Block Diagram
Simple Merge Block Diagram
You can use this method on any file really, even SVG files.  Hint hint wink wink.  You can go from this template file.....

Periodic Table Symbols
SVG Template

to this in a matter of minutes. Just by replacing colour and three text fields.

Periodic Table Symbols
Generated Images

I make no guarantee as to how well this works. So my advice is to back things up before using it. Have fun.
Get The Code!

Saturday, June 3, 2017

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

Grace Kelly
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.
Grace Kelly
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
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.

Stipple Error
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!
I wish I had the time to do an even deeper dive on this type of problem.

Saturday, May 20, 2017

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.