Edge detection with Linear CCD

[technovm]

I have a 256 pixel linear ccd. I need to detect edges, i need a fast algorithm to for edge detection with minimum number of calculations. My processor is not powerfull enough.

The material whose edge is to be detected is highly reflective. It would be great if there is some information on lighting, currently using LED lighting and i am controlling the intensity of the LED with PWM.

I am getting a curved output with white background, cosine effect. How do I eliminate it?

What is the effect of introducting an aperature between the two lenses?

 

[andre_luis]

Hi technovm,

Search for Sobel algorithm.

+++

 

[technovm]

As i have mentioned i have a linear array. What operator do i use?

 

[_pv]

I have a 256 pixel linear ccd. I need to detect edges, i need a fast algorithm to for edge detection with minimum number of calculations. My processor is not powerfull enough.

What is "not powerful enough" in terms of MIPS, MHz, anything?
What accuracy do you need?

Correct and slow way is to calculate correlation function of your signal and function you are looking for (step function in simple case). And then find the position of maximum of correlation function. This also could be done in different ways depending on required accuracy: just take position of maximum value, or approximate around maximum with some polynom(parabolic) and calculate maximum position analytically.
Let's say edge is smooth in area of about 30 pixels, then such calculation would require just: 256 * 30 = 8k multiplications with accumulation, and 256 compartions in order to find maximum.

Fast way is to calculate derivative, filter it a little bit, and then locate maximum of this derivative.
something like:

#define K 10
int Calc(int * d){
  int y0 = 0, y1 = 0, max = 0, pos = 0;
  for (int i = 1; i < 256; i++){
    y1 = y0 + (d[i] - d[i-1] - y0) / K;
    y0 = y1;
    if (y1 > max) {max = y1;pos = i;}
  }
return pos;  
}

Or combining both could improve accuracy with a little overhead: at first locate maximum by finding point with maximum derivative, then calculate correlation function in range of few pixels around in order to get more precise result.

I am getting a curved output with white background, cosine effect. How do I eliminate it?

Subtract it

 

[technovm]

What is "not powerful enough" in terms of MIPS, MHz, anything?
What accuracy do you need?

Correct and slow way is to calculate correlation function of your signal and function you are looking for (step function in simple case). And then find the position of maximum of correlation function. This also could be done in different ways depending on required accuracy: just take position of maximum value, or approximate around maximum with some polynom(parabolic) and calculate maximum position analytically.
Let's say edge is smooth in area of about 30 pixels, then such calculation would require just: 256 * 30 = 8k multiplications with accumulation, and 256 compartions in order to find maximum.

Fast way is to calculate derivative, filter it a little bit, and then locate maximum of this derivative.
something like:

#define K 10
int Calc(int * d){
  int y0 = 0, y1 = 0, max = 0, pos = 0;
  for (int i = 1; i < 256; i++){
    y1 = y0 + (d[i] - d[i-1] - y0) / K;
    y0 = y1;
    if (y1 > max) {max = y1;pos = i;}
  }
return pos;  
}

Or combining both could improve accuracy with a little overhead: at first locate maximum by finding point with maximum derivative, then calculate correlation function in range of few pixels around in order to get more precise result.


Subtract it

Thanks for your reply.

I am using 24 MIPS processor, with built in 16bit SAR 1MSPS ADC. I need atleast 12 bit accuracy.

I need atleast 150 readings per second of the whole picture.

I have the following questions:
1. How do i find the corelation function?
2. How to select value of K?
3. How to reduce the the cosine effect? Subtract what?

Thanks.

 

[keith1200rs]

Whenever I have done edge detection with line CCDs I have often done it using a comparator on the CCD output. You need good control of the illumination and/or exposure time and good optics to get a sharp edge. You can also digitise the data from an ADC and interpolate at the triggering point. Good optics are essential.

Keith

 

[technovm]

Whenever I have done edge detection with line CCDs I have often done it using a comparator on the CCD output. You need good control of the illumination and/or exposure time and good optics to get a sharp edge. You can also digitise the data from an ADC and interpolate at the triggering point. Good optics are essential.

Keith

Thanks, can you suggest ebooks, papers or anything for lighting and optics design for linear ccd cameras for edge detection.

 

[_pv]

Thanks for your reply.
I need atleast 12 bit accuracy.
I need atleast 150 readings per second of the whole picture.
I have the following questions:
1. How do i find the corelation function?
2. How to select value of K?
3. How to reduce the the cosine effect? Subtract what?

I meant the accuracy in terms of position of edge detection error. Theoretically this could be done even with 1bit adc i.e. comparator
625 cycles per pixel should not be a problem for edge detection. Even video mpeg encoding requires less operations per pixel.

1. C(t) = sum (X * Y[i-t]) by i,
2. This is simplest IIR filter and K is somewhat like time constant of this LP filter, frequencies below Fs/K would pass, or if you like it is just like analog RC filter with time constant of K/Fs.
But if you have very strict requirements on accuracy and reproducibility of your measurements, probably FIR filters would be better, as it have linear phase response, but it requires more calculations.
3. if it is constant all the time then just measure it before once with uniformly illuminated detector and then subtract this offset from the data each time. if it is not, then you could approximate your the data with some cosine or polynomial function and subtract it.
But actually it should not be subtracted, but all the data should be divided by A*cos(B*(x - 127)), x - pixel position, just select proper A and B constants.
And proper edge detection algorithm should not be affected by some smooth background.

 

[keith1200rs]

Thanks, can you suggest ebooks, papers or anything for lighting and optics design for linear ccd cameras for edge detection.

I have never had to design the optics myself - I have always had someone else do that. I have just had to process the signals from the CCD (usually 2048 pixel ones).

Keith.