1) Increase the canvas size by a set amount or percentage
2) Vertically flip both the top and bottom sections of the original image to fill the top/bottom canvas area.
3) Horizontally flip left and right sections to fill the canvas.
Rather than trying to explain it in detail, I'm including some before and after pics (which I did in Gimp) to show what I'm trying to achieve:
BEFORE:

AFTER:

Incidentally, I'm on Linux (or OS X) using IM version 6.2.2-6
Any pointers or help with this would be greatly appreciated as I have a ton of images to process.
Thanks!!
Nick