Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

Hi all,

I am trying to find 2D similarity patterns in order to match two image 
objects...

For simplicity, I want to ask this question in terms of 1D case:

Easy cases are zeros and non-zeros:

But I still don't know the relationship between the position of the peak of 
XCORR result and the relative shifting of y that I should do in order to do 
a matching...

I mean, I know I should shift "y" a little bit in order for the best 
matching... but how much?

>> x=[0 0 0 1 1 1 0 0 0 0];
>> y=[0 0 0 0 0 0 1 1 1 1 0 0 0];
>> xcorr(x, y)

ans =

  Columns 1 through 7

    0.0000         0   -0.0000   -0.0000    0.0000   -0.0000    1.0000

  Columns 8 through 14

    2.0000    3.0000    3.0000    2.0000    1.0000    0.0000   -0.0000

  Columns 15 through 21

         0   -0.0000    0.0000         0    0.0000    0.0000   -0.0000

  Columns 22 through 25

    0.0000   -0.0000         0   -0.0000

>> x1=[1 1 1 0 0 0 0];
>> y

y =

  Columns 1 through 12

     0     0     0     0     0     0     1     1     1     1     0     0

  Column 13

     0

>> xcorr(x1, y)

ans =

  Columns 1 through 7

    0.0000    0.0000    0.0000    1.0000    2.0000    3.0000    3.0000

  Columns 8 through 14

    2.0000    1.0000   -0.0000    0.0000    0.0000    0.0000    0.0000

  Columns 15 through 21

   -0.0000   -0.0000    0.0000   -0.0000   -0.0000   -0.0000   -0.0000

  Columns 22 through 25

   -0.0000         0         0   -0.0000

>>

Now suppose the similar patterns are embedded in a noisy setting... the 
following two vectors have similar patterns of 1 2 3 4 4  ...

How do I detect such a similar pattern? How to decide how many shifts should 
my y2 have?



>> x=[1 0 1 1 2 3 4 4 1 0 1 0 1];
>> y2=[1 1 1 1 1 1 2 3 4 4 1 0 1 0 1];
>> xcorr(x, y2)

ans =

  Columns 1 through 7

    1.0000    0.0000    2.0000    1.0000    4.0000    8.0000   11.0000

  Columns 8 through 14

   15.0000   17.0000   23.0000   32.0000   42.0000   51.0000   43.0000

  Columns 15 through 21

   34.0000   26.0000   22.0000   22.0000   20.0000   16.0000   12.0000

  Columns 22 through 28

    7.0000    3.0000    2.0000    2.0000    1.0000    1.0000         0

  Column 29

    0.0000

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

lucy wrote:

> I am trying to find 2D similarity patterns in order to match two image 
> objects...

> For simplicity, I want to ask this question in terms of 1D case:

> Easy cases are zeros and non-zeros:

> But I still don't know the relationship between the position of the peak of 
> XCORR result and the relative shifting of y that I should do in order to do 
> a matching...

> I mean, I know I should shift "y" a little bit in order for the best 
> matching... but how much?

Look at dynamic programming algorithms.  They are good at doing the
shift with a weight to control how much shift to do.

Doing dynamic programming in 2D is somewhat harder, especially in
compute time, but it should be possible.

-- glen

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

Hi Lucy,

If you want to measure similarity based on maximum correlation that's 
fine but if you wanted to take into account scaling and bias, I'd 
recommend you consider using correlation coefficients instead.

In any case and concerning Matlab's xcorr. If you look at the function's 
help it says:
"(...) c = xcorr(x,y) returns the cross-correlation sequence in a length 
2*N-1 vector, where x and y are length N vectors (N>1). If x and y are 
not the same length, the shorter vector is zero-padded to the length of 
the longer vector.
(...)
The output vector c has elements given by c(m) = cxy(m-N), m=1, ..., 2N-1.
(...)"

So using your last example:

x=[1 0 1 1 2 3 4 4 1 0 1 0 1];
y2=[1 1 1 1 1 1 2 3 4 4 1 0 1 0 1];

We compute the two vectors' cross correlation z:

z = xcorr(x, y2);

According to the help, if N = max(13,15)=15 this vector z should count 
2*N - 1 = 29 elements. And the correlation value corresponding to zero 
shift will be mapped to index k0 such that k0-N=0 i.e. k0=15

k0 = k0 = max([length(x) length(y2)]);

We find and locate the max value of that cross correlation:

[m,I]=max(z);

And the amount of shift to apply to y2 in order to acheive the maximum 
cross correlation will be

shifty2 = I-k0;

i.e. -2 (two samples to the left)

Note: instead for looking for the location of the max value you in the 
cross correlation z, you could also think about computing a weighted 
average around the max value, gain some sub-sample resultion for your 
solution.

I hope this helps,
Eric.


lucy wrote:
> Hi all,
> 
> I am trying to find 2D similarity patterns in order to match two image 
> objects...
> 
> For simplicity, I want to ask this question in terms of 1D case:
> 
> Easy cases are zeros and non-zeros:
> 
> But I still don't know the relationship between the position of the peak of 
> XCORR result and the relative shifting of y that I should do in order to do 
> a matching...
> 
> I mean, I know I should shift "y" a little bit in order for the best 
> matching... but how much?
> 

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.