String matching for images

So what is pattern matching, and why should anyone care about it?

First picture: Two individuals who don’t care about pattern matching (Pom’s the mainly white one, and Tiddles is the mainly black one (names have been changed to protect the innocent…)

Image

Pattern matching is important because it’s at the heart of the digital revolution. Google made its fortune largely from the simplest form of pattern matching. Computers can’t manage the more complex forms of pattern matching yet, but humans can handle them easily. A major goal in computer science research is finding a way for computers to handle those more complex forms of pattern matching. A major challenge in information management is figuring out how to split a task between what the computer does and what the human does.

So, there are good reasons for knowing about pattern matching, and for trying to get a better understanding of it.

As for what pattern matching is: the phrase is used to refer to several concepts which look similar enough to cause confusion, but which are actually very different from each other, and which have very different implications.

We’ll start with a couple of pictures and three questions about them, to illustrate the core concepts involved in the different meanings of pattern matching.

Second picture: Unconcern about pattern matching

Image

Question 1: Are the first and second pictures identical copies of the same image?

It’s not a trick question: the answer is obvious to us humans, and also easy for a computer to answer. Those photos aren’t identical; they’re different from each other.

That sounds pretty trivial, until you try a different pair of images. Ignoring minor issues of background shade, are these two copies of the same photo of a chess pawn, or are they photos of two different pawns from the same set?

Third picture: Just in case you thought nothing could care less than Tiddles and Pom…

Image

That’s a much harder question for a human to answer, but an easy one for a computer to answer: they’re copies of the same photo. So why does the change in image make it so much harder for a human to answer, when the underlying question is the same? That’s what we’ll be looking at in this article.

The second and third questions involve identifying a couple of other issues that we need to keep clearly distinct, and that we’ll return to in later articles.

Question 2: What type of animals are shown in the first two photos?

That’s an easy one for a human to answer, but extremely difficult for a computer to answer – only highly specialist software would have any significant chance of answering it correctly; the animals are cats.

This type of pattern matching involves identifying the category to which an item belongs – in this case, the category of “cat”.

The third question brings in a different type of pattern matching.

Question 3: Tiddles and Pom are from the same litter. Two of their sisters have very similar markings to them. Does Picture 2 feature Tiddles and Pom, or does it show two different cats from the ones in picture 1?

That’s a hard question for a human to answer, and a hard question for a computer to answer. It involves identifying specific individuals, as opposed to identifying the category to which they belong. These are two very different processes.

We’ll re-examine these types of pattern matching in later articles. For now, we’ll return to the issues involved in answering the first question in this article.

Just how can you, or a computer, tell whether two images are the same as each other or not?

One way of answering this question is by string matching.

String matching

A string, in this context, is a string of symbols. A sentence can be viewed as a string of symbols (in this case, letters); a number can be viewed as a string of digits. And a picture can be viewed as a string of coloured rectangles. Here’s how that works.

Picture 4: Cubist house on island

Image

Picture 5: Cubist house on island

Image

Question: Are Picture 4 and Picture 5 identical or not?

We can answer that question by comparing the images line by line, just the same way that we could compare two lines of text by putting one above each other. That reduces the problem to a much more manageable size.

Here’s what the top line of squares looks like in the two images, with the top line for Picture 4 above the top line for Picture 5.

Image

They’re identical.

Here, in contrast, is what happens when you put the lower window row from Picture 4 about the corresponding row from Picture 5.

Image

If you look closely at the blueish window squares representing the window on the right (three squares in from the end) you realise that they’re actually different shades of blue. (Depending on your monitor, you might need to look at the image from different angles to make the difference apparent.) The upper set of squares has two window squares that are identical in colour to each other; the lower set doesn’t. Here are the two different squares from Picture 4 and Picture 5 without any distracting background.

Image

The human eye is very easily misled by the image background, and overwhelmed by volume of detail, but a computer isn’t; it just plods methodically along, comparing one pair of squares at a time, unaffected by background or boredom.

The photos of the chess pawn above can be compared to each other using just the same process as we used to compare the pictures of the two houses. A computer treats a photo as a set of rectangles just like the ones in pictures above, only with much tinier rectangles, and with a lot more of them – tens or hundreds of thousands for a medium-size image, and millions for a large or high-detail image.

So that’s how you can compare two images to see if they’re identical, using string matching. If you’re a copyright lawyer trying to show that someone has pirated an image from your website, or a fraud investigator checking whether a document is not what it should be, that approach can be invaluable. For everyday life, though, it’s not usually a huge issue for most of us.

However, you can use exactly the same process to compare two sets of text, and that method is at the heart of Google and a huge amount of software around the world. Paradoxically, explaining how that works is more complicated than explaining how to compare two images. That will be the topic of the next article about pattern matching in strings, which takes us into how search engines work, and also into issues involved in dyslexia, among other things.

Gordon Rugg

Advertisements

About searchvisualizer

We welcome debate and disagreement, but not abuse, trolling or thread derailment. We reserve the time-honoured right of blog owners and moderators to be arbitrary, capricious and autocratic in our wielding of the ban hammer. Gordon Rugg is a former timberyard worker, archaeologist and English lecturer who ended up in computer science via psychology. He’s the same Gordon Rugg who did the Voynich Manuscript work, and the books with Marian Petre about research. He’s co-inventor of the Search Visualizer.
This entry was posted in About SV, background theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s