Jamie's Blog

The ramblings of a programmer with a little too much time on his hands

Tag: creativity (Page 1 of 2)

Code Project: RGB to Y’UV

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Jargon

In case you don’t know what they mean, I’ve included the following list of jargon terms and rough descriptions of them.

RGB = Red, Green, Blue

YUV = similar to RGB, except that luma (Y) and chroma (U and V) are stored

Sources?

Most of the information for this post came from the Wikipedia article on YUV. You can visit it here: [LINK]

RGB? YUV?

Last week, a friend of mine wanted to meet in the city centre and go for a nosey around the TV stores. He’d recently bought his own place, and is decorating it and looking for a new TV.

While we were walking around “Electronics-Company-That-Isn’t-Named-After-A-Spicy-Food-At-All”, we spotted the Sony and LG LED TVs. I got to wondering whether TV transmissions are still sent in YUV, and whether those same signals were converted to RGB before being displayed on screen.

When I got home, I decided that I should look into YUV and see just how it works. I didn’t actually get around to reading about YUV until this afternoon, but when I did it made sense.

The human eye is more sensitive to changes in brightness, rather than certain colours. So, why  not send the luma (brightness) information and the chroma (colour difference) information?

Back in the days of blank and white TV, all that the TV broadcasters had to send was the luma (brightness) information. As colour TV was invented, top boffins thought that the best (read: “way that requires less bandwidth over the air”) way to send the colour information was the extend the model of just sending luma information, this time including chroma information.

The best way to understand this is to see it. Luckily, Wikipedia have an amazing example. In the following picture (click to enlarge):

  • The top image is how it is displayed on screen in any picture browser
  • The second (blank and white) image is the luma data for the image
  • The third (mostly blue and green) image is the U chroma data for the image
  • The forth (mostly yellow and orange) images is the V chroma data for the image
An image along with its Y', U, and V components.

Images via Wikipedia

They could have ditched the older system of just sending luma, and gone with a purely RGB system. However, this would have required the transmitters to send redundant, extra data over the airwaves. Plus, the older blank and white TV sets would no longer have worked. If a blank and white TV is used, then it simply ignores the UV portion of a received signal.

Also, the data being sent can be compressed before sending over the airwaves. In fact, the video portion of digital broadcasts are compressed in (almost) the same way. Because the human eye is more sensitive to changes in brightness, the chroma differences can be compressed (sampled fewer times), thus reducing the bandwidth.

Why Are You Telling Me All Of This, Jamie?

Basically, one of the ways that I can tell if I understand something that I’ve just learnt is to test myself in some way.

Ever wondered why you have exams in most of your classes?

Also, this links into my (very basic) teacher training:

  • Teach something to the student(s)
  • Get the student(s) to tell you what you’ve just taught them in their own words

Anyway, I’ve tested myself by taking what I’ve learnt about the RGB to YUV conversion and created a small C program that converts RGB to YUV.

At the minute it only converts a set of user inputted strings that represent the RGB values and returns their YUV equivalents.

My browsers built in spell check system is telling me that “inputted” isn’t a word. I’m sure that it is. In fact, a whole slew of Internet resources tells me that it is.

Anyway, onto the code. I wont write any more information about the code than this (as everything else should be included in the comments for my code, hopefully):

I compiled this on MS Windows 7 x64, with MiNGW’s gcc with the following options/command:

gcc <path to source file> -o RGB.exe -O2

/*
 * Project Name:        	RGB to Y'UV
 * Solution Name:		RGB to Y'UV
 * Original creation date:	19/11/2011
 * Edit date:			18/01/2013
 * Programmer name:		Jamie Taylor (aka "GaProgMan")
 * File name:			YUV.c
 * 
 * Purpose of the project:
 *	I was reading through a wikipedia article on
 * 	the differences between YUV and RGB and found it
 * 	very interesting.
 * 		For those who don't know, YUV is a colour
 * 	space - a way of storing colour for digital images,
 * 	film and TV. It focuses on storing Luma
 * 	(brightness - as Y') and two chrominance (colour
 * 	- as U and V) values.
 * 		Most video and still images are stored  in
 * 	this format, as it takes into account the Human
 * 	eye's ability to perceive differences in brightness
 *	at higher definition than differences in colour. This
 * 	greatly reduces the data bandwidth required to send
 * 	and receive images and film in this format.
 * 		This short program explores the mathematical
 * 	formulae used to convert colour data from the RGB
 * 	colour space to the Y'UV colour space.
 * 		For an in-depth description Y'UV, RGB and
 * 	the formulae used, please see the following
 * 	website:
 * 			http://en.wikipedia.org/wiki/YUV
 * 
 * Formulae used:
 *	To convert from RGB to Y'UV, the following
 * 	will be used:
 * 			Y' = W[r]R + W[g]G + W[b]B
 * 			U = U[max] * (B - Y') / (1 - W[b])
 * 			V = V[max] * (R - Y') / (1 - W[r])
 * 		Where:
 * 			W[r] = 0.299
 * 			W[b] = 0.114
 * 			W[g] = 1 - W[r] - W[b] = 0.587
 * 			U[max] = 0.436
 * 			V[max] = 0.615
 * 		Note:- I have placed square brackes around
 * 	the letters in the formulae that are written in
 * 	subscript. This is to make it easier for the
 * 	reader.
 *
 *	GNU Copyright information
 *	Copyright 2011 Jamie Taylor <jamie@taylorj.org.uk>
 *
 *	This program is free software; you can redistribute
 *	it and/or modify it under the terms of the GNU General
 *	Public License as published by the Free Software
 *	Foundation; either version 2 of the License, or (at
 *	your option) any later version.
 *
 *	This program is distributed in the hope that it will
 *	be useful, but WITHOUT ANY WARRANTY; without even the
 *	implied warranty of MERCHANTABILITY or FITNESS FOR A
 *	PARTICULAR PURPOSE.  See the GNU General Public
 *	License for more details.
 *
 *	You should have received a copy of the GNU General
 *	Public License along with this program; if not, write
 *	to the Free Software Foundation, Inc., 51 Franklin
 *	Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/

/* included libraries */
#include <stdio.h>

/* Constants that will be used for RGB to Y'UV */
#define WEIGHTEDRED	0.299
#define WEIGHTEDGREEN	0.587
#define WEIGHTEDBLUE	0.114
#define UMAX		0.436
#define VMAX		0.615

/* function declarations */
void convertFromRGB ();

/* global variables */
float redValue;
float greenValue;
float blueValue;
float yPrime;
float uValue;
float vValue;

int main () {

  /* read values for RGB into memory */
  printf("Please input a value for RED:");
  scanf("%f", &redValue);
  printf("Please input a value for GREEN:");
  scanf("%f", &greenValue);
  printf("Please input a value for BLUE:");
  scanf("%f", &blueValue);

  /* convert RGB to Y'UV */
  convertFromRGB();

  /*display results */
  printf("\nFor the RGB input (%.2f, %.2f, %.2f),\n",
    redValue, greenValue, blueValue);
  printf("The following Y'UV is outputted (%.2f, %.2f, %.2f)",
    yPrime, uValue, vValue);
  return 0;
}

void convertFromRGB (){
  /* 
   * implement formula:
   * Y' = W[r]R + W[g]G + W[b]B
   */
  yPrime = (WEIGHTEDRED * redValue) +
    (WEIGHTEDGREEN * greenValue) +
    (WEIGHTEDBLUE * blueValue);

  /*
   * implement formula:
   * U = U[max] * (B - Y') / (1 - W[b])
   */
  uValue = UMAX * ((blueValue - yPrime)
    / (1 - WEIGHTEDBLUE));

  /*
   * implement formula:
   * V = V[max] * (R - Y') / (1 - W[r])
   */
  vValue = VMAX * ((redValue - yPrime)
    / (1 - WEIGHTEDRED));
}

One last thing: If you’re going to compile and run this yourself, remember to put a blank line at the end of the source code. It’s ANSI C, after all.

When I added my source code to this page, it had the blank line at the end. But when I previewed the page, the blank line was pruned from the code viewer provided by WordPress.  But if you click on either “View source” or “Copy to clipboard” (when hovering over the source code black), you’ll get the code with the blank line at the end.

Until next time,

J – “Soul, peace and chicken grease” (as my brother says)

Random Quotes Generator Screenshot

Random Quote Generator

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

So, I was looking through some of my old hobby code today and happened on an old quote generator. It’s a neat little (the executable weighs in at 24Kb) C# program that provides the user with a random quote from some of my favourite TV shows.

Random Quotes Generator Screenshot

A screen-grab of my Random Quote generator showing a picture of Professor Ueda Jiro and a quote from the TV show Firefly

The Algorithm

  1. Find a text file called “Quotes.txt”
  2. Load each line in the text file into an element in an array
  3. Display a standard Windows form with a picture and a text box.
  4. When the user pressed the “Generate Quote” button, ‘randomly’ pick one and display it in the text box.

The Code

The code itself is pretty simple. It compiles on .NET 2.0.50727 and will only run with a text file called “Quotes.txt” located in the same folder as the executable.
[gist https://gist.github.com/4569288 /]

For those wanting to compile this code, you’ll need to provide Visual Studio with a JPEG image. In the original solution, I called this image “Dontokoi!” (as this is the catchphrase of the character in the image). Without this image, I doubt that the program will execute correctly.

Post Mortem

Aside from the above comment about the image being required for compilation, I did notice another potential problem with the program.

For some reason, apostrophes (‘) aren’t rendered correctly when the accompanying text file is encoded in anything but UTF-8. Since I know very little about text file encoding and the default way that the .NET libraries import text into a string array and the way that .NET draws this text into a text box, I can only assume that the problem is related to the formatting of the text file (saved, using Notepad++).

Either that, or it’s related to one of the settings within the Visual Studio IDE itself. I do remember that, around this time, I was attempting to compile all of my code with direct support for Unicode, so maybe that’s it.

I’m not sure, to be honest. But I am planning on opening the solution file (at some point) and having a good look around. The reason I haven’t opened the solution file at the minute is because I don’t own a copy of Visual Studio; which makes opening a Visual Studio file quite difficult.

Here’s a link to a zip of the entire solution, in case you wanted to take a look (The executable is in Bin/Release along with an old Quotes text file) [LINK]

Until next time,

J

Problem Six – In C

EDIT (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

 

Reading a comment on my most recent post, I felt that I could optimise my code for Project Euler’s Problem Six. So, I went away and read up on the information provided by Kristan (in the comments section), and decided that I’d give it a go… in C.

There were a few reasons for switching to C, the biggest was that I only have a C compiler installed on this machine (a minimal install of MingW), another being that I’m a little more informed about the optimisation options (which I didn’t use for this project) that gcc provides.

Anyway, on with the code.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Algorithm

Based on my code from the previous version of this project, and the knowledge provided by Kristan and The Internet at large, I’ve used a slightly different algorithm this time around. I’ve covered the algorithm in the comments section for my code, though. So, I guess you should just scroll down and read that.

I’m not a massive fan of providing information twice, in the same format. That and redundancy. That and redundancy

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

By the way, I compiled this code with the following command:

gcc “Problem_Six_In_C.c” -o “Problem_Six_In_C.exe” -Wall

A simple problem with an extremely simple, now optimised,  solution.

Here’s a link to the c file: LINK

Until next time,

J

Sums and Squares – Or: How I Solved Project Euler Problem 6

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 6 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The Algorithm

There’s only one way to solve this problem.

This one is real simple – dependant on your understanding of Mathematics – assuming you can understand Square Numbers.

It’s a two step approach:

  1. Sum (add up) all of the squares of the numbers between 1 and 100
  2. Sum all of the numbers between 1 and 100, then square the answer
  3. Then find the difference between them (subtract one from the other)

There’s a slight problem with this method, though. Skipping ahead – and, hopefully teaching you all a little about speed-of-light Maths – we get:

There is a well known story about Karl Friedrich Gauss when he was in elementary school. His teacher got mad at the class and told them to add the numbers 1 to 100 and give him the answer by the end of the class. About 30 seconds later Gauss gave him the answer.
The other kids were adding the numbers like this:
1 + 2 + 3 + . . . . + 99 + 100 = ?
But Gauss rearranged the numbers to add them like this:
(1 + 100) + (2 + 99) + (3 + 98) + . . . . + (50 + 51) = ?
If you notice every pair of numbers adds up to 101. There are 50 pairs of numbers, so the answer is 50*101 = 5050.  Of course Gauss came up with the answer about 20 times faster than the other kids.

That version of the story comes, courtesy of Dr. Math. The actual story has been around for… well, since the days of Karl Friedrich Gauss

Anyway, skipping to the end, we find that the sum of all the numbers from 1 to 100 comes out at 5050. A quick calculation tells us that 5050 squared (5050 * 5050) is 25,502,500. Quite a big number, wouldn’t you say?

That’s fine, but logic tells me that the other number I’m working out (the sum of the squares) will be huge, compared to this one. So, and int just wont do it.

Dependant on your system, an int can store a value between +2,147,483,647 and – 2,147,483,646 (32 bit)

So because of this, potentially, massive answer, I decided to code this by using an unsigned long long (sometimes called a long int) type.

Again, dependant on your system, an unsigned long long can store a value between 0 and +4,294,967,295 (32bit)

Of course, I’m running 62 bit, so the maximum values that these two variable types can hold are doubled. But that’s not the point.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:


A simple problem with a simple solution.

Here’s a link to the cpp file: LINK

Until next time,

J

Pining For Primes – Or: How I Solved Project Euler Problem 5

Edit (18/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly

This is a solution to problem 5 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.

The original problem reads like this:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The Algorithm

Firstly, there are two ways to solve this problem. One involves brute force, and one requires a little savvy.

Technically, there are a whole bunch of ways to solve this problem – dependant on your understanding of Mathematics. Hopefully, both of these methods will be simple enough to follow – assuming you can understand Prime Numbers.

The brute force check goes like this:

  1. Start at n, check this against all numbers in m
  2. If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
  3. If not, add 1 to n and start again.

“n” starts at 1 (this is the smallest positive number that will divide by all the numbers from 1 to 20)

“m” starts at 1 and goes only as far as 20 (this is the series of numbers that “n” has to divide by)

That’s it.

The smarter algorithm goes like this:

  1. Start with n at 2520
  2. If n divides evenly (i.e there is no remainder) by all the numbers in m, stop. This is the answer
  3. If not, add 2520 to n and start again.

This method assumes that you recognise a few things from the problem statement. Let’s take another look:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Since the numbers between 1 and 20 contain all the numbers between 1 and 10 (1, 2, 3, 4, 5, 6, 7, 8, 9 & 10), some of the work is done for us. We can assume that, since 2520 is evenly divisible by all numbers between 1 and 10, that it must be evenly divisible by all the numbers between 1 and 20.

This algorithm speeds up execution exponentially. Instead of going through every positive integer between 1 and he final answer, we can jump in steps of 2520.

The Code

I’m not going to spend time explaining the code, since it contains enough information in the comments (within the code itself) and in the description of the algorithm above.

So, without further ado, here is the finished code:

And there you have it, another problem solved (and optimised) in minutes.

Until next time,

J

Scripts and Stuff

Two weeks back – June 21st to be exact – I wrote a post about my new chair, an amazing cheesecake that my brother made, and that I had been re-writing some old scripts. Here is a link to the exact post: LINK

In that post, I’d said that I might end up posting some of my old scripts online (once they had been re-formatted and re-worked a little). It’s not perfect, but I’m going to share one of them with you all, today.

Conception

Back in 2008, after a series of life changing events (albeit small on most people’s scales), a friend of mine came to me and said:

Why don’t we write a sit-com?

My initial reaction was trepidation. I wasn’t entirely sure I could write a long enough script for an entire episode of anything, let alone making it funny. But after talking through our ideas, we hit upon a sort of combined life experience that we felt we could share.

You see, my friend Simon is a very funny chap, and I like to think that I’m very funny when around him, too. We’d both been through some heavy stuff, and we felt the need to expunge ourselves of the experiences. Through writing, we could learn to live with them.

One of the caveats with using our own experience, was that we would craft the main characters after ourselves. Names, details, experiences, friends, they would all come from our own existences. After all, a writer should write what they know about… or some such nonsense.

Inspiration

Reading through this script, it’s not difficult to see that we where inspired by the work of Simon Pegg, Jessica Hynes (nee Stevenson) and Edgar Wright on Spaced.

In fact, there’s a reference to spaced on the first page of the script.

We’d both recently re-watched the entirety of Spaced and the first two films in the Blood and Ice Cream Trilogy (“Shaun of the Dead” and “Hot Fuzz”). At the time, the third film was only being speculated about.

The Name

The name came to me while I was eating out at a Nando’s. One of the waiters there – a friend of mine called Carl – was taking my order, typing it into his touch screen device. Except that he wasn’t using his finger to enter the details, he was tapping away with his pen.

Presumably because everything in this city seems to be covered in grime. Sometimes, I feel as though I’m living in one of the cleaner areas of Ankh-Morpork

He was struggling with some specific character or item on the screen, tapping it more than a few times before the device accepted his input command.

Oh, I’m using the wrong end of the pen, here. That’s why.

Instantly, I saw myself talking to my friend Alex about my life:

I feel like I’m writing my biography, but with the wrong end of the pen.

The Content

So, we’d decided that we would be the main characters in it (we were more than OK with not playing ourselves, though). This meant that we had to come up with story lines we would find ourselves in, in reality. This meant that we’d have to pick secondary characters that we’d likely be friends (and enemies) with in real life. This also meant that our main characters had to have a similar obsession with video games, movies and TV shows as we did.

So, we decided that the main content would be about the two of us sharing a house. Me being a graduate, and Simon being an undergraduate. My friend Alex would appear, as she is like a big sister to me. Marc, one of Simon’s friends, would appear as he seems quite laid back.

Recent Re-Writes

I’ve only made minor changes to the script in the recent re-writes. Changing things like names of characters, spelling errors, and setting them out into a standard three act structure.

These were my first scripts, after all, and they were created more as a stream of consciousness, than a planned out series of scenes.

That’s pretty much all that I’ve changed. That and the layout.

Why Share?

I’m sharing the first script in the hopes that I can get some dialogue going about it, see what people think is good, what needs changing, what needs removing, etc.

Obviously, I hold and retain the copyright on this script, the characters and the idea for the show. But feel free to peruse the scripts and tell me what you think.

One final note: I know very little about the American TV rating system, but this script would definitely not pass the PG-13 bar. In the UK, it’s be a 12 or 15 rated script, I think. Which should tell you that it’s potentially Not Safe For Work.

Without further ado, here is a working link to the first script. Tell me what you think. LINK

Until next time,

J

FizzBuzz

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

Firstly, I realise that I’m not the best developer in the world. I can, certainly, hold my end up in C++; read a lot of C and understand it; work my way through a C# listing with confidence; understand enough of an assembly listing to VERY vaguely get what it’s doing.

Secondly, I’ve been using twitter and the blog-o-sphere for a few weeks now, to try and figure out what’s missing from my virtual tool kit (if you like) of developer skills. So far, the answer has been a resounding “Experience is better than a degree”

For instance, Gaven Woolery over at #AltDevBlogADay mentions that (and I’m paraphrasing):

In this age, with the relative ease of access to both online and offline tutorials/books/whatever, and the relatively un-homogeneous structure of Computer Science degrees in most Higher Education facilities, what’s the point of going to [University] for 4 years, and racking up a large debt, when you can just learn all of that at home?

Here’s a link to the original article : Link

This all is beginning to make sense to me. Don’t get me wrong, I thoroughly enjoyed my studies at University. But there where a few modules (known as classes to some) that were better studied at home, or in the labs than sat in a lecture theatre. Then again, there were modules that required that level of theoretical understanding.

I like to think of Computer Science being a perfect marriage between both vocational and non-vocational training.

This leads me onto something that Richard Banks blogged about in the middle of 2009: Some “Developers” Just Can’t Develop. Basically, his argument is for testing new recruits DURING the interview process. Something I have taken part in for some (not all) of my interviews.

I remember during one interview, in the middle of a question even, the interviewer got up and asked me to write some code “it can be in any language you want, even psuedo code,” to copy two strings

Because of my experience, I can certainly see what Richard is talking about. The cost of hiring the wrong person can be crippling. That being said, he links to a post from early 2007 (a year before I graduated, for those who want to know) by Jeff Atwood called “Why Can’t Programmers.. Program?”

The main thrust of Jeff’s post is to promote the idea of using a standardised test during interview processes to find out if the candidate is “good enough.” That being a completely subjective term (some companies require different skills from their employees, especially graduates), he even goes on to say:

Like me, the author [of, yet another post] is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

The post Jeff refers to mentions a test that is used by some professionals to see if a candidate can solve “simple” tasks.

FizzBuzz

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Fain enough, that’s quite easy. One for loop and three checks. Easy.

Most good programmers should be able to write out on paper a program which does this in a under a couple of minutes. Want to know something scary? The majority of comp sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.

What!? How is that possible?

I really hope that the teaching of programming has improved since 2007, otherwise graduates haven’t got a chance of getting that juicy development role they tell themselves they deserve.

In fact, I think it has improved. At least, my experience of the teaching of programming seems to have been quite an amazing one and I’ll prove it to you.

Taking that basic task, I created a solution with 17 lines (including white space) in, roughly, 3 minutes (damned keyboard’s too stiff) that solves this problem; and it goes a little something like this:

I usually have extra newlines in there for formatting and clarity. But I think it looks just as good without them.

There you have it.  A solution to a simple problem in less time then a “self-proclaimed senior programmer” and, dare I say it, an elegant solution, too?

J

Video Compression

Edit (19/01/2013)

I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.

What of What?

A few months back, I was thinking of applying for a job relating to video technologies. The company wanted someone with “experience working with video compression techniques with regards to software development.” As with everything relating to software development, this got me curious. How does video compression work? Why do we need to compress video? What are the most widely used compression techniques?

Well?

I’m only going to answer (and party, so) the second question in this post:

Why do we need to compress video?

This is simple. Otherwise we would run out of storage space for digital video. I’ll explain.

Storage Space

OK, so storage space is slowly become less of a problem (I still remember my first 1GB hard drive, back in the days of 3.5″ floppy discs, well before USB memory sticks. Before USB, even). But that’s only because we’re gradually increasing the quality of the footage we shoot. It wasn’t so long ago that the first 3D cameras came out, before that it was HD cameras, before that it was digital cameras.

Of course, I’m talking about cameras that are dedicated to shooting video here, but the same principle applies to digital stills cameras, too.

Our need to take pictures, static or otherwise, at higher and higher resolutions is creating greater need for more and more storage space and better, more efficient compression methods. Eventually we’ll get to a point where we can capture near-to-real-life resolution, and the storage space needed will be astronomical (by today’s standards), but that’s more than 20 years off at the very least.

Why Does Video Take Up So Much Space?

Do you remember taught that animation (of any kind) is a bunch of still images that are played together in a sequence? The images are displayed, one after the other, quick enough that our brains to put them together as one image – usually at, around 24 – 60 images every second. That means that when you’re watching a piece of video footage, you’re actually watching 20 – 60 images every second.

Animation is actually seen as a “Mind Hack” by those in the Neuroscience (Brain Science) community, but since it’s so common place now, many lay-people (I.E not connected with Neuroscience) don’t think of it as such.

Each of those images has to be stored somewhere and, depending on the resolution – the number of pixels (Picture Elements, the individual “dots” that make up the picture) – that can be anywhere from 20Kb to 15Mb per image.

Two things to note here:

  1. When talking about images, we use the measure of bits, not bytes. This is because we store image data in bit, and  text data in bytes. When stored as text, the character “a” takes up 1 byte of memory in a computer; which is 8 bits.
  2. I’m not including audio here, as the audio is actually stored separately in all video formats.

With, on average, 25 images per second of footage taking up 15Mb of storage space, you’re going to run out of space very quickly.

How Quickly?

Well, suppose that you’re taking video at 640 pixels wide by 480 pixels high with a colour depth of 24 (that means 8 bits representing each of the colours Red, Green and Blue). This would give you an overall value of 7Mb per image.

This is what the phrase “MegaPixel” means. It is a measure of how many pixels are captured by a stills camera when you hit the shutter button.

So, a camera that takes stills at 7 mega pixels COULD take images that are 640 pixels wide by 480 pixels high at 24 bits per pixel. But that’s just confusing the matter.

At 25 images per second, a full minute of footage would take up about 10.3Gb of storage. That’s more than one dual layer DvD, for a single second of video footage. Again this isn’t counting the audio.

And that’s less than standard definition, too!

Understanding is Key

In an effort to understand why video compression is tantamount to film production I did what I do best.

OK, second best.

All right, third best.

Is that even a term?

I’ve written a very short program that calculates how much storage space is required for a video taken at any resolution, colour depth, frame rate and length. All of these variables are provided by the user.

It’s a really simple bit of code, so there are no checks on what the user is entering, it’s assumed that the user is entering valid data. So long as the user enters valid data, the program will calculate the amount of storage space required for the video footage taken at that resolution and colour depth provided.

It’s written in C, one of the most powerful programming languages there is, and my second favourite (after C++). It should be easy to read whether you’re a programmer or not. It’ll need a little extra code to run, dependant on your OS environment, and you’ll need to compile it, too.

The Code

At the minute, I’ve commented out the code for user input. That’s because the code is in it’s initial testing stages. For now, if you run the above code, it’ll tell you how much storage space is required for a video taken at 640*480 pixels, at 24bit colour depth, at 25 frames a second with a total duration of 1 hour.

Give it a go, and tell me what you think.

For those who don’t write software or can’t program, here’s a break down of what it does:

  • 640 (width) * 480 (height) = 307,200 (pixels per frame)
  • 307,200 (pixels per frame) * 24 (colour depth) = 7,372,800 (bits per frame)
  • 7,372,800 (bits per frame) * 25 (frames per second) = 184,320,000 (bits per 1 second of film)
  • 184,320,000 (bits per 1 second of film) * 3600 (number of seconds in 1 hour) = 663,552,000,000  (the size of the resultant video file in bits)
  • 663,552,000,000 is roughly 632,812.50 MB for 1 hour of video.
  • This doesn’t take into account the audio

J

AABA and The Blues

AABA?

Over the past few months I’ve been watching, rather religiously, Brentalfloss’ Lyrics 101 series. Although, I haven’t taken part in the assignments directly, I’ve been using these amazing videos to enhance my own writing skills.

For those who don’t know what I’m talking about, here’s an embed for the first in the series. I’d recommend them to anyone, even if you’re not interested in writing lyrics they can give you a valuable insight into the world of song writing.

Side note: be sure to check out his “With lyrics” series, as he’s a really talented musician/song writer

Based on these videos, I’ve been able to recognise the AABA structure in ~80% of the songs I listen to on a regular basis. I think this is a great thing, because I’m able to start thinking about why certain words where chosen for certain rhyme, and how story telling works as an art form. Being an amateur writer, this is enormously helpful.

Let Them Talk

For those who didn’t know, Hugh Laurie (AKA Dr. House, AKA M’colleague to Mr. Stephen Fry, AKA The Prince Regent, AKA Bertram Wilberforce “Bertie” Wooster) has recently recorded a blues album. This is amazing news, not only am I a fan of Hugh’s output as an actor, but I’m a massive fan of the Blues as a genre of music.

My Mind, You Don’t Know It

When I fired up my PC yesterday and loaded iTunes, I was confronted with a message telling me that my pre-order was ready for downloading. Naturally, I clicked “OK”. Part of me wished there was a “F*ck YEAH!” button, alas there wasn’t. About 25 seconds later, the entire 3 track single had been downloaded.

I clocked the download at, around, 8Mbits per second; which is mighty quick – pretty much my maximum download speed, too. Thank you Apple for providing exceptional servers.

After I’d downloaded them, then stripped them of the DRM (I wont tell you how, but there’s a hidden feature that does it for you. At least there is on the Windows version, I’m not sure about the Mac version), and saved the album art (I’ve been stung by the “damaged iTunes library” bug too many times) I plugged my outer ear headphones in and started it playing.

My god, this man knows how to write a good blues song.

And that was just after the first track.

For Free? Really?

After listening to the tracks, I went to the website (clickable here). It turns out that there’s a fourth track available for free download (you’ve just gotta give the server your email address to get the download link. Otherwise the web spiders would get a hold of it, and his PR team wouldn’t know how many people had downloaded it); which I did. After a few seconds I received an email from the team, with a link to a zip file. I downloaded that, un-zipped and listened to a DRM free, mp3 file – Warner Bros. got it right, for once.

Oh, hell yeah!

This one’s a little more jazzy. I can’t say for certain which type of jazz, as I’m not a massive jazz aficionado (I’m into the big band era stuff, and Miles Davis, though). It’s a little more laid back, and sounds really good. It sounds like Hugh recorded the piano and vocals at the same time, too – which is not the norm for music these days – aside from a few notable exceptions, of course.

Structure, It’s What You Need

All of that happened yesterday. Today, on the way home, I was listening to the single again. One of the songs on there (which is “quite ballsy,” as my brother puts it) is about how the Bible shouldn’t be taken as literally as some people do. Listening to it, I realised that not only does the song have an AABA structure, but the verses do, too. I’ll show ya:

The following quote contains copyrighted material. It is used under Fair Use. No copyright infringement is implied by using the following quote. The lyrics remain copyright of Warner Bros. Publishing / Hugh Laurie, 2011.

Methuselah lived 900 years / Methuselah lived 900 years / But who calls that livin’ / When no gal will give in / To a man who’s 900 years?

Did you spot it?

I’ll go through it line then.

Methuselah lived 900 years

An A line – setting up you’re idea, storyline or characters. In this instance, Hugh is telling us about the oldest character in the Hebrew Bible (also known as the Tanakh to Jewish people, or The Old Testament in Christian terms).

Methuselah lived 900 years

The second line a second A line – telling the same story, typically in a different way. All that Hugh is doing is telling us about Methuselah in the same way, again. But this is standard fare for Blues, use the first line again rather than write a different first line.

But who calls that livin’ / When no gal will give in,

A pair of lines representing the B, also known as an A’ – giving up a small respite from the original story or idea, but feeding into the final A. Hugh is giving us a rest from the opening two A lines, and asking us a question about Methuselah: What kind of life did Methuselah have? Why would he have wanted to live for 900 years? Can you imagine living for 900 years?

To a man who’s 900 years,

Yet a third A – telling us the same story or idea but in yet a different way. Hugh brings us back to his original statement, both re-enforcing the story of Methuselah (He was 900 years, don’t you know? … Well, technically, he got to 969 years. Can you imagine that?) and posing his question again. He uses the idea of how boring it must have gotten for Methuselah, being 900 years old, having seen the world, no doubt his body would be in terrible shape as we’re only designed to last a maximum of 80-100 years, and imagining that he would be denied sex on account of his age and the condition of his body (sex being something that some people see as defining their entire existence).

Whoa! Hold On A Second

OK, so I’m not a scholar of music – in fact, I never took a single music lesson in my life, and we didn’t even have a music teacher at my high school. I’m just extrapolating from these lyrics and the information that’s available out there (on The Internet and in books on lyric composition) with my own knowledge and experience, and mixing that with my interpretation of the lyrics.

Also it should be noted that, during the B section of the song, Hugh notes:

Again, the following quote contains copyrighted material. It is used under Fair Use. No copyright infringement is implied by using the following quote. The lyrics remain copyright of Warner Bros. Publishing / Hugh Laurie, 2011.

I take’s that gospel / Whenever it’s poss’ble / But always with a grain of salt.

Which is, basically, Hugh saying that he’s a believer, but some parts shouldn’t be taken literally; which makes sense to me.

I’d like to hear what you guys think about this. Give me some feedback. Does my opinion of these lyrics follow with yours? Let me know what you think.

J

5 Years in the Making

The Problem

Five years ago, I created a software project in C#. The goal was to create a clone of an old computer game called Gorillas. For those who don’t know abut this game, click this link for an article on The Wiki. Most people would have played a variant of this game based around cannons, though.

I’d got the game 90% complete in my time budget. The only things that where missing were textures (I was still only a baby programmer back then), and aiming code.

My not so elegant code for aiming was terrible, to say the least. By pressing left, right, up or down the player could change the position of the projectile (in this case, a banana). When the player pressed the fire button, the banana would be fired out in a straight line from it’s current position. For some reason, I’d felt that I would never be able to put code in that would make this aiming process simple.

Anyone who’s played the original (be it in tank of gorilla form) will know how to use the aiming system: Right to decrease the trajectory and Left to increase it. Simple.

For some reason, my brain couldn’t figure out how this was done. I tried and tried my hardest, but I couldn’t visualise it. At one point, I ended up trying to program a semi circle of points that could be selected by the user, but that went as well as this sentence seems to have done.

The Solution

Last night I was snuggled up in bed, watching an episode of Seinfeld. The episode ended, I turned the DvD player off, then got back into bed and started to fall asleep. All of a sudden the following image popped into my head.

 

Mario and Tanooki are used via Fair Use. No copyright infringment is meant. Both are copyrighted by Nintendo

At first I wasn’t sure what to make of it. Then, I figured out why the axis are there.

Pressing left will decrease the X value, but increase the Y value. Pressing right will increase the X value but decrease the Y value.

Both X and Y have pre-set limits, X can only be between 5 – 20 units in front of Tanooki and Y can only be between 5 – 20 units above Tanooki, for example.

This algorithm will successfully move the projectile (assuming you show it) around your gorilla (or tank, or Tanooki) along a quarter circle in front of it. In pseudocode it might look something like this:

[sourcecode language=”cpp”]
int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;

// game code in here

switch (key) {
case left:
//without any bounds checking
projectileXPos–;
projectileYPos++;
break;
case right:
//without any bounds checking
projectileXPos++;
projectileYPos–;
}
[/sourcecode]

Calculating the Angle

So, you’re projectile is moving around the character in a quarter circle arc; which is great. But now you want to be able to fire along the correct trajectory? That’s really simple to work out.

If you look back at the image of Tanooki you’ll see a Greek symbol near his face. For those who aren’t familiar, this is symbol is called Theta and in trigonometry it represents an unknown angle. To calculate this angle we’re going to use something called SoH, CaH, ToA.

Copyrighted by processing.org. Used via Fair Use

If you look back again (what’s with all this looking?) at Tanooki, you might be able to see a triangle forming – the X axis and the trajectory forming the adjacent and the Hypotenuse.

We know all three values for the sides of this triangle (we actually only know two, but a quick bit of trig will calculate the Hypotenuse for us), so we can use any part of SoH CaH ToA to work out the angle.

We’ll use ToA for now, as we know both the Adjacent (X value) and the Opposite (Y value). But we could use either, if we worked out the Hypotenuse.

Again with pseudocode, it could look like this:

[sourcecode language=”cpp”]
#include <math.h>

int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;
double opposite, adjacent, firingAngle;

// working out the angle

switch (key) {
case fire:
opposite = projectileYPos – player.GetYPos();
adjacent = projectileXPos – player.GetXPos() ;
firingAngle = tan(opposite/adjacent);
}
[/sourcecode]

To calculate the Hypotenuse, all you would have to do is basic Pythagoras. Again, in pseudocode it might look like this:

[sourcecode language=”cpp”]
#include <math.h>

int projectileXPos, projectileYPos;
int upperLimitX, upperLimitY = 20;
double opposite, adjacent, hypotenuse;

// working out the hypotenuse

opposite = projectileYPos – Player.GetYPos();
adjacent = projectileXPos – player.GetXPos();
hypotenuse = sqrt((opposite * opposite) + (adjacent * adjacent));
[/sourcecode]

Why Five Years

I know that this is really simple trig, and I know that the code for it is also really simple. For some reason, though it never crossed my mind to code it this way. I have no idea what prompted this “Eureka moment” for me last night, but I’m really glad that it did. Since then, I’ve been finding simple solutions to other coding problems.

I suppose my problem was, at that time, my whole life revolved around that one problem; as such, and to coin an old phrase, I couldn’t see the wood for the trees.  My best advice for anyone confronting a problem with no, obvious solution – regardless of whether it’s coding or math or life or whatever – is this:

Take a step back from it, and look at it from another angle.

If that doesn’t work walk away from it completely. Some of my other problems have actually been solved by me taking a break and going for a long walk.

If all else fails, watch something like Seinfeld.

I’ve found that, Seinfeld is my Plan Nine From Outer Space.

Anyone who has seen a few episodes of the X-Files will know what I mean there.

There’s that little going on, that my sub-concious mind can, and does, wander. This enables me to find the solutions without even thinking about the problems, while still enjoying the show.

More proof, if anyone needed it, that Larry David is a genius

Page 1 of 2