Author: Jo Brodie

https://twitter.com/JoBrodie same on BlueSky and other pages. Old photo!

100,000 frames – quick draw: how computers help animators create

Ben Stephenson of the University of Calgary gives us a guide to the basics of animation.

Film projector with film strip on a coloured rainbow background, from Pixabay
Film projector and film strip image by Gerd Altmann from Pixabay

Animation isn’t a new field – artists have been creating animations for over a hundred years. While the technology used to create those animations has changed immensely during that time, modern computer generated imagery continues to employ some of the same techniques that were used to create the first animations.

The hard work of hand drawing

During the early days of animation, moving images were created by rapidly showing a sequence of still images. Each still image, referred to as a frame, was hand drawn by an artist. By making small changes in each new frame, characters were created that appeared to be walking, jumping and talking, or doing anything else that the artist could imagine.

In order for the animation to appear smooth, the frames need to be displayed quickly – typically at around 24 frames each second. This means that one minute of animation required artists to draw over 1400 frames. That means that the first feature-length animated film, a 70-minute Argentinean film called The Apostle, required over 100,000 frames to create.

Creating a 90-minute movie, the typical feature length for most animated films, took almost 130,000 hand drawn frames. Despite these daunting numbers, many feature length animated movies have been created using hand-drawn images.

Drawing with data

Today, many animations are created with the assistance of computers. Rather than simply drawing thousands of images of one character using a computer drawing program, artists can create one mathematical model to represent that character, from which all of his or her appearances in individual frames are generated. Artists manipulate the model, changing things like the position of the character’s limbs (so that the character can be made to walk, run or jump) and aspects of the character’s face (so that it can talk and express emotions). Furthermore, since the models only exist as data on a computer they aren’t confined by the physical realities that people are. As such, artists also have the flexibility to do physically impossible things such as shrinking, bending or stretching parts of a character. Remember Elastigirl, the stretchy mum in The Incredibles? All made of maths.

Once all of the mathematical models have been positioned correctly, the computer is used to generate an image of the models from a specific angle. Just like the hand-drawn frames of the past, this computer- generated image becomes one frame in the movie. Then the mathematical models representing the characters are modified slightly, and another frame is generated. This process is repeated to generate all of the frames for the movie.

The more things change

You might have noticed that, despite the use of computers, the process of generating and displaying the animation remains remarkably similar to the process used to create the first animations over 100 years ago. The animation still consists of a collection of still images. The illusion of smooth movement is still achieved by rapidly displaying a sequence of frames, where each frame in the sequence differs only slightly from the previous one.

The key difference is simply that now the images may be generated by a computer, saving artists from hand drawing over 100,000 copies of the same character. Hand-drawn animation is still alive in the films of Studio Ghibli and Disney’s recent The Princess and the Frog, but we wonder if the animators of hand-drawn features might be tempted to look over at their fellow artists who use computers and shake an envious fist. A cramped fist, too, probably.

Related Magazine …

EPSRC supports this blog through research grant EP/W033615/1.

Understanding matters of the heart

Colourful depiction of a human heart
Heart image by Gordon Johnson from Pixabay

Creating accurate computer models of human organs

Ada Lovelace, the ‘first programmer’ thought the possibilities of computer science might cover a far wider breadth than anyone else of her time. For example, she mused that one day we might be able to create mathematical models of the human nervous system, essentially describing how electrical signals move around the body. University of Oxford’s Blanca Rodriguez is interested in matters of the heart. She’s a bioengineer creating accurate computer models of human organs.

How do you model a heart? Well you first have to create a 3D model of its structure. You start with MRI scans. They give you a series of pictures of slices through the heart. To turn that into a 3D model takes some serious computer science: image processing that works out, from the pictures, what is tissue and what isn’t. Next you do something called mesh generation. That involves breaking up the model into smaller parts. What you get is more than just a picture of the surface of the organ but an accurate model of its internal structure.

So far so good, but it’s still just the structure. The heart is a working, beating thing not just a sculpture. To understand it you need to see how it works. Blanca and her team are interested in simulating the electrical activity in the heart – how electrical pulses move through it. To do this they create models of the way individual cells propagate an electrical system. Once you have this you can combine it with the model of the heart’s structure to give one of how it works. You essentially have a lot of equations. Solving the equations gives a simulation of how electrical signals propagate from cell to cell.

The models Blanca’s team have created are based on a healthy rabbit heart. Now they have it they can simulate it working and see if it corresponds to the results from lab experiments. If it does then that suggests their understanding of how cells work together is correct. When the results don’t match, then that is still good as it gives new questions to research. It would mean something about their initial understanding was wrong, so would drive new work to fix the problem and so the models.

Once the models have been validated in this way – shown it is an accurate description of the way a rabbit’s heart works – they can use them to explore things you just can’t do with experiments – exploring what happens when changes are made to the structure of the virtual heart or how drugs change the way it works, for example. That can lead to new drugs.

They can also use it to explore how the human heart works. For example, early work has looked at the heart’s response to an electric shock. Essentially the heart reboots! That’s why when someone’s heart stops in hospital, the emergency team give it a big electric shock to get it going again. The model predicts in detail what actually happens to the heart when that is done. One of the surprising things is it suggests that how well an electric shock works depends on the particular structure of the person’s heart! That might mean treatment could be more effective if tailored for the person.

Computer modelling is changing the way science is done. It doesn’t replace experiments. Instead clinical work, modelling and experiments combine to give us a much deeper understanding of the way the world, and that includes our own hearts, work.

Paul Curzon, Queen Mary University of London

The charity Cardiac Risk in the Young raises awareness of cardiac electrical rhythm abnormalities and supports testing (electrocardiograms and echocardiograms) for all young people aged 14-35.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

The Dark History of Algorithms

An Arabic pattern on a crescent moon
Image by Mohammad Shahriyar from Pixabay

Zin Derfoufi, a Computer Science student at Queen Mary, delves into some of the dark secrets of algorithms past.

Algorithms are used throughout modern life for the benefit of mankind whether as instructions in special programs to help disabled people, computer instructions in the cars we drive or the specific steps in any calculation. The technologies that they are employed in have helped save lives and also make our world more comfortable to live it. However, beneath all this lies a deep, dark, secret history of algorithms plagued with schemes, lies and deceit.

Algorithms have played a critical role in some of History’s worst and most brutal plots even causing the downfall and rise of nations and monarchs. Ever since humans have been sent on secret missions, plotted to overthrow rulers or tried to keep the secrets of a civilisation unknown, nations and civilisations have been using encrypted messages and so have used algorithms. Such messages aim to carry sensitive information recorded in such a way that it can only make sense to the sender and recipient whilst appearing to be gibberish to anyone else. There are a whole variety of encryption methods that can be used and many people have created new ones for their own use: a risky business unless you are very good at it.

One example is the ‘Caesar Cipher’ which is named after Julius Caesar who used it to send secret messages to his generals. The algorithm was one where each letter was replaced by the third letter down in the alphabet so A became D, B became E, etc. Of course, it means that the recipient must know of the algorithm (sequence to use) to regenerate the original letters of the text otherwise it would be useless. That is why a simple algorithm of “Move on 3 places in the alphabet” was used. It is an algorithm that is easy for the general to remember. With a plain English text there are around 400,000,000,000,000,000,000,000,000 different distinct arrangements of letters that could have been used! With that many possibilities it sounds secure. As you can imagine, this would cause any ambitious codebreaker many sleepless nights and even make them go bonkers!!! It became so futile to try and break the code that people began to think such messages were divine!

But then something significant happened. In the 9th Century a Muslim, Arabic Scholar changed the face of cryptography forever. His name was Abu Yusuf Ya’qub ibn Ishaq Al-Kindi -better known to the West as Alkindous. Born in Kufa (Iraq) he went to study in the famous Dar al-Hikmah (house of wisdom) found in Baghdad- the centre for learning in its time which produced the likes of Al-Khwarzimi, the father of algebra – from whose name the word algorithm originates; the three Bana Musa Brothers; and many more scholars who have shaped the fields of engineering, mathematics, physics, medicine, astrology, philosophy and every other major field of learning in some shape or form.

Al-Kindi introduced the technique of code breaking that was later to be known as ‘frequency analysis’ in his book entitled: ‘A Manuscript on Deciphering Cryptographic Messages’. He said in his book:

“One way to solve an encrypted message, if we know its language, is to find a different plaintext of the same language long enough to fill one sheet or so, and then we count the occurrences of each letter. We call the most frequently occurring letter the ‘first’, the next most occurring one the ‘second’, the following most occurring the ‘third’, and so on, until we account for all the different letters in the plaintext sample.

“Then we look at the cipher text we want to solve and we also classify its symbols. We find the most occurring symbol and change it to the form of the ‘first’ letter of the plaintext sample, the next most common symbol is changed to the form of the ‘second’ letter, and so on, until we account for all symbols of the cryptogram we want to solve”.

So basically to decrypt a message all we have to do is find out how frequent each letter is in each (both in the sample and in the encrypted message – the original language) and match the two. Obviously common sense and a degree of judgement has to be used where letters have a similar degree of frequency. Although it was a lengthy process it certainly was the most efficient of its time and, most importantly, the most effective.

Since decryption became possible, many plots were foiled changing the course of history. An example of this was how Mary Queen of Scots, a Catholic, plotted along with loyal Catholics to overthrow her cousin Queen Elizabeth I, a Protestant, and establish a Catholic country. The details of the plots carried through encrypted messages were intercepted and decoded and on Saturday 15 October 1586 Mary was on trial for treason. Her life had depended on whether one of her letters could be decrypted or not. In the end, she was found guilty and publicly beheaded for high treason. Walsingham, Elizabeth’s spymaster, knew of Al-Kindi’s approach.

A more recent example of cryptography, cryptanalysis and espionage was its use throughout World War I to decipher messages intercepted from enemies. The British managed to decipher a message sent by Arthur Zimmermann, the then German Foreign Minister, to the Mexicans calling for an alliance between them and the Japanese to make sure America stayed out of the war, attacking them if they did interfere. Once the British showed this to the Americans, President Woodrow Wilson took his nation to war. Just imagine what the world may have been like if America hadn’t joined.

Today encryption is a major part of our lives in the form of Internet security and banking. Learn the art and science of encryption and decryption and who knows, maybe some day you might succeed in devising a new uncrackable cipher or crack an existing banking one! Either way would be a path to riches! So if you thought that algorithms were a bore … it just got a whole lot more interesting.

Zin Derfoufi, Queen Mary University of London

More on…

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Cognitive crash dummies

Cartoon showing a crash test dummy in a sitting position.
Car crash dummy image by OpenClipart-Vectors from Pixabay

The world is heading for catastrophe. We’re hooked on power hungry devices: our mobile phones and iPods, our Playstations and laptops. Wherever you turn people are using gadgets, and those gadgets are guzzling energy – energy that we desperately need to save. We are all doomed, doomed…unless of course a hero rides in on a white charger to save us from ourselves.

Don’t worry, the cognitive crash dummies are coming!

Actually the saviours may be people like professor of human-computer interaction, Bonnie John, and her then grad student, Annie Lu Luo: people who design cognitive crash dummies. When working at Carnegie Mellon University it was their job to figure out ways for deciding how well gadgets are designed.

If you’re designing a bridge you don’t want to have to build it before finding out if it stays up in an earthquake. If you’re designing a car, you don’t want to find out it isn’t safe by having people die in crashes. Engineers use models – sometimes physical ones, sometimes mathematical ones – that show in advance what will happen. How big an earthquake can the bridge cope with? The mathematical model tells you. How slow must the car go to avoid killing the baby in the back? A crash test dummy will show you.

Even when safety isn’t the issue, engineers want models that can predict how well their designs perform. So what about designers of computer gadgets? Do they have any models to do predictions with? As it happens, they do. Their models are called ‘human behavioural models’, but think of them as ‘cognitive crash dummies’. They are mathematical models of the way people behave, and the idea is you can use them to predict how easy computer interfaces are to use.

There are lots of different kind of human behavioural model. One such ‘cognitive crash dummies’ is called ‘GOMS’. When designers want to predict which of a few suggested interfaces will be the quickest to use, they can use GOMS to do it.

Send in the GOMS

Image showing a modern touch-screen mobile phone with colourful circular icons distributed randomly on the screen.
Smartphone gadget image by Vladislav Klimenkov from Pixabay

Suppose you are designing a new phone interface. There are loads of little decisions you’ll have to make that affect how easy the phone is to use. You can fit a certain number of buttons on the phone or touch screen, but what should you make the buttons do? How big should they be? Should you use gestures? You can use menus, but how many levels of menus should a user have to navigate before they actually get to the thing they are trying to do? More to the point, with the different variations you have thought up, how quickly will the person be able to do things like send a text message or reply to a missed call? These are questions GOMS answers.

To do a GOMS prediction you first think up a task you want to know about – sending a text message perhaps. You then write a list of all the steps that are needed to do it. Not just the button presses, but hand movements from one button to another, thinking time, time for the machine to react, and so on. In GOMS, your imaginary user already knows how to do the task, so you don’t have to worry about spending time fiddling around or making mistakes. That means that once you’ve listed all your separate actions GOMS can work out how long the task will take just by adding up the times for all the separate actions. Those basic times have been worked out from lots and lots of experiments on a wide range of devices. The have shown, on average, how long it takes to press a button and how long users are likely to think about it first.

GOMS in 60 seconds?

GOMS has been around since the 1980s, but wasn’t being used much by industrial designers. The problem is that it is very frustrating and time-consuming to work out all those steps for all the different tasks for a new gadget. Bonnie John’s team developed a tool called CogTool to help. You make a mock-up of your phone design in it, and tell it which buttons to press to do each task. CogTool then worked out where the other actions, like hand movements and thinking time, are needed and makes predictions.

Bonnie John came up with an easier way to figure out how much human time and effort a new design uses, but what about the device itself? How about predicting which interface design uses less energy? That is where Annie Lu Luo, came in. She had the great idea that you could take a GOMS list of actions and instead of linking actions to times you could work out how much energy the device uses for each action instead. By using GOMS together with a tool like CogTools, a designer can find out whether their design is the most energy efficient too.

So it turns out you don’t need a white knight to help your battery usage, just Annie Lu Luo and her version of GOMS. Mobile phone makers saw the benefit of course. That’s why Annie walked straight into a great job on finishing university.

Paul Curzon, Queen Mary University of London

More on …

Related Magazine …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Kimberly Bryant: Black Girls Code

Kimberly Bryant in 2016, Ståle Grut / nrkbeta, CC BY-SA 2.0, via Wikimedia Commons

Kimberly Bryant was born on 14 January 1967 in Memphis, Tennessee and was enthusiastic about maths and science in school, describing herself as a ‘nerdy girl’. She was awarded a scholarship to study Engineering at university but while there she switched to Electrical Engineering with Computer Science and Maths. During her career she has worked in several industries including pharmaceutical, biotechnology and energy.

She is most known though for founding Black Girls Code. In 2011 her daughter wanted to learn computer programming but nearly all the students on the nearest courses were boys and there were hardly any African American students enrolled. Kimberly didn’t want her daughter to feel isolated (as she herself had felt) so she created Black Girls Code (BGC) to provide after-school and summer school coding lessons for African American girls. BGC has a goal of teaching one million Black girls to code by 2040 and every year thousands of girls learn coding with their peers.

She has received recognition for her work and was given the Jefferson Award for Community Service for the support she offered to girls in her local community, and in 2013 Business Insider included her on its list of The 25 Most Influential African-Americans in Technology. When Barack Obama was the US President the White House website honoured her as one of its eleven Champions of Change in Tech Inclusion – Americans who are “doing extraordinary things to expand technology opportunities for young learners – especially minorities, women and girls, and others from communities historically underserved or underrepresented in tech fields.”

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Bringing people closer when they’re far away

Two children playing with a tin-can telephone, which lets them talk to each other at a distance. Picture credit Jerry Loick KONZI, CC BY-SA 4.0, via Wikimedia Commons

This article was written before the Covid pandemic led to many more of us keeping in touch from a distance…

Living far away from the person you love is tough. You spend every day missing their presence. The Internet can help, and many couples in long-distance relationships use video chat to see more of each other. It’s not the same as being right there with someone else, but couples find ways to get as much connection as they can out of their video chats. Some researchers in Canada, at the University of Calgary and Simon Fraser University, interviewed couples in long-distance relationships to find out how they use video chat to stay connected.

Nice to see you

The first thing that the researchers found is perhaps what you might expect. Couples use video chat when it’s important to see each other. You can text little messages like ‘I love you’ to each other, or send longer stories in an email, and that’s fine. But seeing someone’s face when they’re talking to you feels much more emotionally close. One member of a couple said, “The voice is not enough. The relationship is so physical and visual. It’s not just about hearing and talking.” Others reported that seeing each other’s face helped them know what the other person was feeling. For one person, just seeing his partner’s face when she was feeling worn out helped him understand her state of mind. In other relationships, seeing one another helped avoid misunderstandings that come from trying to interpret tone of voice. Plus, having video helped couples show off new haircuts or clothes, or give each other tours of their surroundings.

Hanging out on video

The couples in the study didn’t use video chat just to have conversations. They also used it in a more casual way: to hang out with each other while they went about their lives. Their video connections might stay open for hours at a time while they did chores, worked, read, ate or played games. Long silences might pass. Couples might not even be visible to each other all the time. But each partner would, every once in a while, check back at the video screen to see what the other was up to. This kind of hanging out helped couples feel the presence of the other person, even if they weren’t having a conversation. One participant said of her partner, “At home, a lot of times at night, he likes to put on his PJs and turn out all the lights and sit there with a snack and, you know, watch TV… As long as you can see the form of somebody that’s a nice thing. I think it’s just the comfort of knowing that they’re there.”

Some couples felt connected by doing the same things together in different places. They shared evenings together in living rooms far away from each other, watching the same thing on television or even getting the same movie to watch and starting it at the same time. Some couples had dinner dates where they ordered the same kind of takeaway and ate it with each other through their video connection.

Designing to connect

This might not sound like research about human-computer interaction. It’s about the deepest kind of human interaction. But good computer design can help couples feel as connected as possible. The researchers also wanted to find out how they could help couples make their video chats better. Designers of the future might think about how to make gadgets that make video chat easier to do while getting on with other chores. It’s difficult to talk, film yourself, cook and move through the house all at the same time. What’s more, today’s gadgets aren’t really built to go everywhere in the house. Putting a laptop in a kitchen or propping one up in a bed doesn’t always work so well. The designers of operating systems need to work out how to do other stuff at the same time as video. If couples want to have a video chat connection open for hours, sometimes they might need to browse the web or write a text message at the same time. And what about couples who like to fall asleep next to one another? They might need night-vision cameras so they can see their partner without disturbing their sleep.

We’re probably going to have more long- distance relationships in the future. Easy, cheap travel makes it easier to move to faraway places. You can go to university abroad, and join a company with offices on every continent. It’s an awfully good thing that technology is making it easier to stay connected with the people who are important too. Video chat is not nearly as good as feeling your lover’s touch, but when you really miss someone, even watching them do chores helps.

Paul Curzon, Queen Mary University of London

Related Magazine …

All of our free material can be downloaded here: https://cs4fndownloads.wordpress.com/

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Gary Starkweather: the laser printer and colour management

Colour wheel image by Pete Linforth from Pixabay

Gary Starkweather, born 9 January 1938, invented and developed the first laser printer. In the late 1960s he was an engineer, with a background in optics, working in the US for the Xerox company (famous for their photocopiers) and came up with the idea of using a laser beam to transfer the image to the photocopier (so that it could make lots of copies), speeding up the process of printing documents. There is a video of Gary talking about the ‘Eureka moment’ of his invention here. Laser printers are now found in offices worldwide – you may even have one at home.

He also invented colour management which is a way of ensuring that a shade of blue colour on your computer’s or phone’s screen looks the same on a TV screen or when printed out. Different devices have different display colours so ‘red’ on one device might not be the same as ‘red’ on another. Colour management is something that happens in devices behind the scenes and which translates the colour instruction from one device to produce the closest match on another. There is an International Color Consortium (ICC) which helps different device manufacturers ensure that colour is “seamless between devices and documents”.

Starkweather received an Academy Award (an Oscar) for Technical Achievement in 1994, for the work he’d done in colour film scanning. That involves taking a strip of film and converting it digitally so it can be edited on a computer.

As a nice coincidence, on the same day as his birth, in 2007, the first Apple iPhone was announced (though not available until June that year)… and all iPhones use colour management!

Jo Brodie, Queen Mary University of London

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Pepper’s Ghost: an 1860s illusion used in ‘head-up displays’

A ghostly illustration including a woman in historic garb, an ornate candlestick, a grand chair and a mirror with grey curtains pulled back.
Ghostly stage Image by NoName_13 from Pixabay

When Pepper’s Ghost first appeared on the stage as part of one of Professor Pepper’s shows on Christmas Eve, 1862 it stunned the audiences. This was more than just magic: it was miraculous. It was so amazing that some spiritualists were convinced Pepper had discovered a way of really summoning spirits. A ghostly figure appeared on the stage out of thin air, interacted with the other characters on the stage and then disappeared in an instant. This was no dark seance where ghostly effects happen in a darkened room: who knows what tricks are then being pulled in the dark to cause the effects. Neither was it modern day special effects where it is all done on film or in the virtual world of a computer. This was on a brightly lit stage in front of everyone’s eyes…

Stage setup for Pepper’s Ghost, from Wikipedia, Public Domain

Switch to the modern day and similar ghostly magic is now being used by fighter pilots. Have the military been funding X-files research? Well maybe, but there is nothing supernatural about Pepper’s Ghost. It is just an illusion. The show it first appeared in was a Science show, though it went on to amaze audiences as part of magic shows for years to come, and can still be found, for example in Disney Theme Parks, and onstage to make virtual band Gorillaz come to life.

Today’s “supernatural” often becomes tomorrow’s reality, thanks to technology. With Pepper’s ghost, 19th century magic has in fact become enormously useful 21st century hi-tech. 19th century magicians were more than just showmen, they were inventors, precision engineers and scientists, making use of the latest scientific results, frequently pushing technology forward themselves. People often think of magicians as being secretive, but they were also businessmen, often patenting the inventions behind their tricks, making them available for all to see but also ensuring their rivals could not use them without permission. The magic behind Pepper’s ghost was patented by Henry Dircks, a Liverpudlian engineer, in 1863 as a theatrical effect though it was probably originally invented much earlier – it was described in an Italian book back in 1558 by Baptista Porta.

Through the looking glass

So what was Pepper’s ghost? It’s a cliche to say that “it’s all done with mirrors”, but it is quite amazing what you can do with them if you both understand their physics and are innovative enough to think up extraordinary ways to use old ideas. Pepper’s ghost worked in a completely different way to the normal way mirrors are used in tricks though. It was done using a normal sheet of glass, not a silvered mirror at all. If you have ever looked at your image reflected in a window on a dark night you have seen a weak version of Pepper’s Ghost. The trick was to place a large, spotlessly clean sheet of glass at an angle in front of the stage between the actors and the audience. By using the stage lights in just the right way, it becomes a half mirror. Not only can the stage be seen through the glass, but so can anything placed at the right position off the stage where the glass is pointing. Better still, because of the physics of reflection, the reflected images don’t seem to be on the surface of the glass at all, but the same distance behind as the objects are in front. The actor playing the ghost would perform in a hidden black area so that he or she was the only thing that reflected light from that area. When the ghost was to appear a very strong light was shone on the actor. Suddenly the reflection would appear – and as long as they were standing the right distance from the mirror, they could appear anywhere desired on the stage. To make them disappear in an instant the light was just switched off.

Jump to the 21st century and a similar technique has reappeared. Now the ghosts are instrument panels. A problem with controlling a fighter plane is you don’t have time to look down. You really want the data you need to keep control of your plane wherever you are looking outside the plane. It needs not just to be in the right position on the screen but at the right depth so you don’t need to refocus your eyes. Most importantly you must also be able to see out of the plane in an unrestricted way…You need the Peppers Ghost effect. That is all “Head-up” displays display do, though the precise technology used varies.

Satnav systems in cars are very dangerous if you have to keep looking down to see where the thing atually means you to turn. “What? This left turn or the next one?” Use a Head-up display and the instructions can hover in front of you, out on the road where your eyes are focussed. Better still you can project a yellow line (say) as though it was on the road, showing you the way off into the distance: Follow the Yellow Brick Road … Oh and wasn’t the Wizard of Oz another great magician who used science and engineering rather than magic dust.

Paul Curzon, Queen Mary University of London (first published in 2007)

Make…

Watch…

You can download ALL of our free material here.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Making sense of squishiness – 3D modelling the natural world

Squishy raspberries image by 🌼Christel🌼 from Pixabay

Look out the window at the human-made world. It’s full of hard, geometric shapes – our buildings, the roads, our cars. They are made of solid things like tarmac, brick and metal that are designed to be rigid and stay that way. The natural world is nothing like that though. Things bend, stretch and squish in response to the forces around them. That provides a whole bunch of fascinating problems for computer scientists like Lourdes Agapito of Queen Mary, University of London to solve.

Computer scientists interested in creating 3-dimensional models of the world have so far mainly concentrated on modelling the hard things. Why? Because they are easier! You can see the results in computer-animated films like Toy Story, and the 3D worlds like Second Life your avatar inhabits. Even the soft things tend to be rigid.

Lourdes works in this general area creating 3D computer models, but she wants to solve the problems of creating them automatically just from the flat images in videos and is specifically interested in things that deform – the squishy things.

Look out the window and watch the world go by. As you watch a woman walk past you have no problem knowing that you are looking at the same person as you were a second ago – even if she becomes partially hidden as she walks behind the post box and turns to post a letter. The sun goes behind a cloud and the scene is suddenly darker. It starts to rain and she opens an umbrella. You can still recognise her as the same object. Your brain is pulling some amazing tricks to make this seem so mundane. Essentially it is creating a model of the world – identifying all the 3-dimensional objects that you see and tracking them over time. If we can do it, why can’t a computer?

Unlike hard surfaces, deformable ones don’t look the same from one still to the next. You don’t have to just worry about changes in lighting, them being partially hidden, and that they appear different from a different angle. The object itself will be a different shape from one still to the next. That makes it far harder to work out which bits of one image are actually the same as the ones in the next. Lourdes has taken on a seriously hard problem.

Existing vision systems that create 3D objects have made things easier for themselves by using existing models. If a computer already has a model of a cube to compare what it sees with, then spotting a cube in the image stream is much easier than working it out from scratch. That doesn’t really generalise to deformable objects though because they vary too much. Another approach, used by the film industry, is to put highly visible markers on objects so that those markers can be tracked. That doesn’t help if you just want to point a camera out the window at whatever passes by though.

Lourdes aim is to be able to point a camera at a deformable object and have a computer vision system be able to create a 3D model simply by analysing the images. No markers, no existing models of what might be there, not even previous films to train it with, just the video itself. So far her team have created a system that can do this in some situations such as with faces as a person changes their expression. Their next goal is to be able to make their system work for a whole person as they are filmed doing arbitrary things. It’s the technical challenge that inspires Lourdes the most, though once the problems of deformable objects are solved there are applications of course. One immediately obvious area is in operating theatres. Keyhole surgery is now very common. It involves a surgeon operating remotely, seeing what they are doing by looking at flat video images from a fibre optic probe inside the body of the person being operated on. The image is flat but the inside of the person that the surgeon is trying to make cuts in is 3-dimensional. It would be far less error prone if what the surgeon was looking at was an accurate 3D model of the video feed rather than just a flat picture. Of course the inside of your body is made of exactly the kind of squishy deformable surfaces that Lourdes is interested in. Get the computer science right and technologies like this will save lives.

At the same time as tackling seriously hard if squishy computer science problems, Lourdes is also a mother of three. A major reason she can fit it all in, as she points out, is that she has a very supportive partner who shares in the childcare. Without him it would be impossible to balance all the work involved in leading a top European research team. It’s also important to get away from work sometimes. Running regularly helps Lourdes cope with the pressures and as we write she is about to run her first half marathon.

Lourdes may or may not be the person who turns her team’s solutions into the applications that in the future save lives in operating theatres, spot suspicious behaviour in CCTV footage or allow film-makers to quickly animate the actions of actors. Whoever does create the applications, we still need people like Lourdes who are just excited about solving the fundamental problems in the first place.

Paul Curzon, Queen Mary University of London

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Watching whales well – the travelling salesman problem

Photograph of a whale's tail emerging from the deep blue sea with a tree-covered cliff behind it.
Whale tail photograph by Kevin O’Leary from Pixabay

Sasha owns a new tour company and her first tours are to the Azores, a group of volcanic islands in the Atlantic Ocean, off the coast of Portugal. They are one of the best places in the world to see whales and dolphins, so lots of people are signing up to go.

Sasha’s tour as advertised is to visit all nine islands in the Azores: São Miguel, Terceira, Faial, Pico, São Jorge, Santa Maria, Graciosa, Flores and Corvo. The holidaymakers go whale watching as well as visiting the attractions on each island, like swimming in the lava pools. Sasha’s first problem, though, is to sort out the itinerary. She has to work out the best order to visit the islands so her customers spend as little time as possible travelling, leaving more for watching whales and visiting volcanos. She also doesn’t want the tour to go back to the same island twice – and she needs it to end up back at the starting island, São Miguel, for the return flight back home.

Trouble in paradise

It sounds like it should be easy, but it’s actually an example of a computer science problem that dates back at least to the 1800s. It’s known as ‘The Travelling Salesman Problem’ because it is the same problem a salesman has who wants to visit a series of cities and get back to base at the end of the trip. It is surprisingly difficult.

It’s not that hard to come up with any old answer (just join the dots!), but it’s much tougher to come up with the best answer. Of course a computer scientist doesn’t want to just solve one-off problems like Sasha’s but to come up with a way of solving any variant of the problem. Sasha, of course, agrees – once she’s sorted out the Azores itinerary, she then needs to solve similar problems, like the day trip round São Miguel. Her customers will visit the lakes, the tea factory, the hot spring-fed swimming pool in the botanic gardens and so on. Not only that, once Sasha’s done with the Azores, she then needs to plan a wildlife tour of Florida. Knowing a quick way to do it would help her a lot.

The long way round

No one has yet come up with a good way to solve the Travelling Salesman problem though and it is generally believed to be impossible. You can find the best solution in theory of course: just try all the alternatives. Sasha could first work out how long it is if you go São Miguel, Terceira, Faial, Pico, São Jorge, Santa Maria, Graciosa, Flores, Corvo and back to São Miguel, then work out the time for a different order, swapping Corvo and Flores, say. Then she could try a different route, and keep on till she knew the length of every variation. She would then just pick the best. Trouble is, that takes forever.

Even this small problem with only 9 islands has over 20 000 solutions to check. Go up to a tour of 15 destinations and you have 43 billion calculations to do. Add a few more and it would take centuries for a fast computer running flat out to solve it. Bigger still and you find the computer would have to run for longer than the time left before the end of the universe. Hmmm. It’s a problem then.

Be greedy

The solution is not to be such a perfectionist and accept that a good solution will have to be good enough even though it may not be the absolute best. One way to get a good solution is called using a ‘greedy’ algorithm. You start at São Miguel and just go from there to the nearest island, from there to the nearest island not yet visited, and so on till you have done them all. That would probably work well for the Azores as they are in groups, so visiting the close ones in each group together makes sense. It doesn’t guarantee the best answer in all cases though.

Or just go climb a hill

Another way is to use a version of ‘hill climbing’. Here you take any old route and then try and optimise it, by just making small changes – swapping pairs of legs over, say: instead of going Faial to Pico and later Corvo to Flores try substituting Pico to Flores and Faial to Corvo, with the rest the same but in the opposite order. If the change is an improvement keep it and make later changes to that. Otherwise stick with the original. Either way keep trying changes on the best solution you’ve found so far, until you run out of time.

So Sasha may want to run a great tour company but there may not be enough time in the universe for her tours to be guaranteed perfect…unless of course she keeps them very small. After all, just visiting São Miguel and Terceira makes a great holiday anyway.

Paul Curzon, Queen Mary University of London

Related Magazine …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos