# What image-processing techniques are ideal for this particular shift/scale invariant template matching?

A problem I had originally discussed here has evolved, and might have gotten a little simpler as I studied it in some more and attained new information.

Bottom line, I would like to be able to detect this pattern shown here, using computer-vision/image-processing techniques. As you can see, the ideal pattern is made up of four 'pings'. The object-recognition should be:

• Shift Invariant
• Horizontally, the image will be cyclical. (ie, Push to the right, comes out on the left, and vice-versa).
• (Fortunately) Vertically, it is not cyclical. (ie,Push to either top or bottom and it will stop).
• Scale Invariant (The pings can vary in 'thickness' as you can see.)

I could go on and on about it but I have attached images covering what I mean, please see below:

Of course, they can also be at a different 'scale', as can be seen from this family:

And finally, here are some 'realistic' scenarios of what I might actually receive, where there would be noise, the rows might 'fade' as you go towards the bottom, and of course, the image will have plenty of spurious lines, artifacts, etc.

And of course, as a grand finale, there is the distinct possibility of this 'extreme' scenario:

So once again, I would like to ask for some guidance on what computer-machine-vision techniques I should utilize here in order to best detect the occurance of my pattern, where I need to be shift and scale invariant as you can see, and also be able to get decent results for the realistic scenarios. (Good news is that I DONT need it to be rotationaly invariant). Only idea I have been able to come up with thus far is a 2-D correlation.

I should add, that in reality, I do NOT have colored images - I will just get a martix of numbers, so I suppose we are talking about 'greyscale'.

P.S. For what its worth I will probably be using open C V.

EDIT # 1:

Based on the comments, I have added the details you requested here:

For characteristics defining the data, we can assume the following:

• Horizontal length of each ping can vary, but I know the upper and lower bounds of it. YES for anything within this bound, NO for anything outside. (Example, I know the length of the pings can be anywhere between 1 and 3 seconds, for example).

• All pings need to be 'visible' for YES, however, last row can be missing, and still want to say 'YES'. Otherwise NO.

• Vertical length, (the 'thickness') of each ping can vary, but again, also know upper and lower bound. (Similar to what you see in those images). YES for anything within that bound. NO for anything outside.

• Height between each ping should always be the same for YES. If they are not, then NO. (Example, you can see how all the pings are of the same height relative to each other, ~110 on the vertical axis). So so 110 +/- 5 can be a YES, anything else has to be NO.

I think thats about it - but let me know what else I can add... (Also, everything shown here should register as a YES, btw).

• What do you mean when you say detect this pattern shown here ? Are you just interested in isolating red/yellow line or do you actually want expression that computes relationship between such lines. Only finding lines could only require some thresholding or segmentation. What do you really want? – Dipan Mehta Mar 14 '12 at 18:51
• @DipanMehta Sorry for the confusion. What I want to do is this: First off dont pay attention to the colors, (its just the say they were plotted), what I will have is just a matrix of numbers, so greyscale. Second thing, since there are no colors, I only just care about the 'pattern' you see there with the 4 pings you are seeing repeat. So the detector will see variants of that image template as shown in the images above, and say 'yes, this pattern exists'. Sorry for confusion, let me know if I can clarify anything else. Thanks! – Spacey Mar 14 '12 at 19:30
• Ok, so you if i understand correctly, given that there is first line on top, you want to find out if the balance also are in the same place. if so, you would conclude that pattern exists! Right? – Dipan Mehta Mar 15 '12 at 2:02
• @DipanMehta Yes basically, be able to detect if the pattern shown above exists, robust enough to deal with scale invariance, and robust enough to deal with shift invariance. Does that make sense? Thanks, – Spacey Mar 15 '12 at 6:29
• What I'm getting it is whether you have access to the source data in the actual system that you're working on. If you do, then there may be a better approach that operates on the original data directly instead of the intermediate spectrogram format that you've zeroed in on. – Jason R Mar 25 '12 at 15:56

Broadly speaking there are two primary approaches to solving this problem:

a. template matching or
b. matching with a parameterized model.

Personally, given the simplicity of the model, i would prefer the second approach for this problem.

Step 1: Identify the ping blobs

As a first step, extract the "Boxes" - essentially the yellow/blue squares. A simplest method here could be to just threshold the image. There doesn't seem to be much variations in the background except that as the noise increases it tends to be quite similar to the pings. Hence, the threshold can be global across the image - and i think you will be able to get a decent threshold that would work across the images. The threshold, however, should be smart so you can use something like Otsu's method. See this and this for more reference.

Improvement of the blocks

One of the good thing you can do to remove spurious points which looks similar to ping foreground where as some pixels inside the pings are also blue. You need here a morphological operation called "Opening". Here is one of the reference from HIPR. These type of operations requires smart shape that helps preserving similar shapes and removing others. In your case you can choose horizontal lines. By the end of this, you have background and foreground pixels neatly separating the pings without touching each other.

Step 2: Mark/Register blocks

Now that you have got the cleanest possible blobs, time to mark them as 1,2,3,4 or A,B,C,D etc. This is usually accomplished by what is called some simple algorithm. Run through each pixel and if it is touching with any marked region, and is also foreground then assign it to that segment else create a new one. If you happen to find more than 4 important segments you need to choose the most relevant ones. Apply some heuristic here rather than any theoretical algorithm.

Step 3: Modeling of parameters

Now, once we get most likely top 4 candidates of the 4 corresponding pings, you can identify the bounding boxes - essentially the top left and bottom right corners (or left and right most pixels, as well as top and bottom rows of the blob). Find the bounding box, you can fined centroid the of each ping box.

Hence you can have four centroids $C_i \text{ where } i \in \{1,2,3,4\}$ Based on the description, the absolute location of $C_1$ can be arbitrary. However, following to $C_1$, the other centroids should be within certain range,

hence inter centroid distances can now be calculated:

$$C_{1i}[x,y] = \{ C_1[x] - C_i[x], C_1[y] - C_i[y] \}$$

The other critical parameter is the length of the pings - which is $L_i \text{ where } i \in \{1,2,3,4\}$

Essentially you have 8 parameter vecoter:

$$1. \{ C_1[x],C_1[y] \} \\ 2..4 C_{1i}[x,y] \\ 5..8 L_i \\$$

Step 4: Classification
In the last step, now we need to have classification whether there is a ping-pattern yes or no.

For something like this, you can have a nice Bayesian classifier framework.

There are two Hypothesis you have

H0 : The ping pattern exist.
H1 : The ping pattern doesn't exist

Now, i am putting only 1 parameter $C_{1,i}[x]$ case here but you can extend this.

First of you study a lot of images where you know they belong to the image. Now, you can plot various histograms or apply some method of density estimation method. Read Pattern Classification by Duda Hart.

For simplicity you found that in cases where pings are present, the density function of parameter $C_{1,i}[x]$ is Gaussian with $\mu = 20, \sigma = .1$ The sigma being small here could imply that there cannot be so much variations from the original.

This is actually conditional probability of $C_{1,i}$ given $H0$ is true. So you have values $P[ C_{1,i}[x] | H0 ]$

Now, from the test data

$P[ H0 | C_{1,i}[x] =x_1]$ is = given the reading of $C_1[x]$ being $x_1$, what is the probability of $H0$ ?

Hence, you can compute

$$P[ H0 \space | C_{1,i}[x] ] = { P[ C_{1,i}[x] | H0 ] * P[H0] \over {P[ C_{1,i}[x]] } }$$

You need to combine this expression for the vector expression and need to fill in a lot of effort for exactly putting the parameter estimation to be done. But i am leaving you with basic approach here.

Please do your own math, this will be lengthy, but should be still quite intuitive.

Once, you combine expression, if $P[H0 | \text{all parameters}] > 1/2$ then the ping pattern exists.

EDIT
Since you are already defining the specific criteria of 110 +/- 5 pixels, the last step can be simpler. You probably don't quite need to calculate all these probabilities if your classification criteria is fixed.

• Thank you very much! I will have to digest this and get back to you. – Spacey Mar 25 '12 at 15:56

This problem seems to me like the pulse repetition interval detection + estimation problem. I'll need to develop this answer over time, but the sort of algorithms that work well in that problem are maximum likelihood on a lattice.

• Thank you, yes I will be glad to hear your thoughts on this. In the meantime I will look over your link. – Spacey Mar 25 '12 at 15:57
• Peter, have you had any time to think about this as you mentioned? I would be interested in hearing your thoughts on the matter. – Spacey May 7 '12 at 14:54
• Just started tinkering again (April was a write-off). I could be mistaken: the way Clarkson's paper formulates the problem is different... let me dig a bit more. – Peter K. May 9 '12 at 12:36