| View previous topic :: View next topic |
| Author |
Message |
A.Leopold
Guest
|
 Posted: Tue Oct 28, 2008 9:56 pm Post subject: Template Matching with subpixesl accuracy |
 |
|
Dear all,
I>m implementing template matching in my current project.
So far, it looks fine. The algorithm is based on the
normalized correlation coefficent ( NCC ). Therfor I cycle through
the image ( pixel by pixel ) and calculate the NCC together with the
template image.
If NCC is 'high' I found the position of the template in the image. (
pixel - accuracy )
Now I ask myself: How can I achieve subpixel accuracy?
Any ideas or experience with that?
Thanks |
|
| |
|
 Back to top |
Peter
Guest
|
| Posted: Wed Oct 29, 2008 1:35 am Post subject: Re: Template Matching with subpixesl accuracy |
|
|
"A.Leopold" <andreas.leopold@himt.de> schrieb im Newsbeitrag
news:490743a0$1@news.arcor-ip.de...
[quote]Dear all,
I>m implementing template matching in my current project.
So far, it looks fine. The algorithm is based on the
normalized correlation coefficent ( NCC ). Therfor I cycle through
the image ( pixel by pixel ) and calculate the NCC together with the
template image.
If NCC is 'high' I found the position of the template in the image. (
pixel - accuracy )
Now I ask myself: How can I achieve subpixel accuracy?
Any ideas or experience with that?
Thanks
[/quote]
I>ll try to explain for the one-dimensional case, the two-dimensional case
is a straightforward extension.
Let>s assume that you have a series of discrete match scores. Near a maximum
(global or local) you could fit a parabola through three points (f(x) =
ax^2+bx+c). Yo>ve got three unknowns a, b and c, and you>ve got three points
that allow you to solve the resulting system of three equations. Now you
need to differentiate to get f'(x)=2ax+b and set this to zero, because this
is the criterium for a maximum (or minimum). Solve this for x and you>ve got
your sub-pixel position. Of course the result needs to be within the
interval of the three points you>ve started with, otherwise it>s
meaningless. Finally you repeat this for every adjacent three points until
you>ve got all your maxima.
In two dimensions you do the same, but you work with a patch of nine points.
Also you have a paraboloid which you need to fit (you>ve got more points
than unknowns in this case, so you could do a least squares error
minimization). Then you differentiate the paraboloid in x and y directions,
and set both partial derivatives to zero to find the top of the paraboloid.
Of course you could also use a library like NGI www.ngi-central.org or
others, which does all that and more for you.
Peter |
|
| |
|
| Back to top |
A.Leopold
Guest
|
| Posted: Wed Oct 29, 2008 1:46 pm Post subject: Re: Template Matching with subpixesl accuracy |
|
|
Peter schrieb:
[quote]"A.Leopold" <andreas.leopold@himt.de> schrieb im Newsbeitrag
news:490743a0$1@news.arcor-ip.de...
Dear all,
I>m implementing template matching in my current project.
So far, it looks fine. The algorithm is based on the
normalized correlation coefficent ( NCC ). Therfor I cycle through
the image ( pixel by pixel ) and calculate the NCC together with the
template image.
If NCC is 'high' I found the position of the template in the image. (
pixel - accuracy )
Now I ask myself: How can I achieve subpixel accuracy?
Any ideas or experience with that?
Thanks
I>ll try to explain for the one-dimensional case, the two-dimensional case
is a straightforward extension.
Let>s assume that you have a series of discrete match scores. Near a maximum
(global or local) you could fit a parabola through three points (f(x) =
ax^2+bx+c). Yo>ve got three unknowns a, b and c, and you>ve got three points
that allow you to solve the resulting system of three equations. Now you
need to differentiate to get f'(x)=2ax+b and set this to zero, because this
is the criterium for a maximum (or minimum). Solve this for x and you>ve got
your sub-pixel position. Of course the result needs to be within the
interval of the three points you>ve started with, otherwise it>s
meaningless. Finally you repeat this for every adjacent three points until
you>ve got all your maxima.
In two dimensions you do the same, but you work with a patch of nine points.
Also you have a paraboloid which you need to fit (you>ve got more points
than unknowns in this case, so you could do a least squares error
minimization). Then you differentiate the paraboloid in x and y directions,
and set both partial derivatives to zero to find the top of the paraboloid.
Of course you could also use a library like NGI www.ngi-central.org or
others, which does all that and more for you.
Peter
Dear Peter,[/quote]
thank you for your reply. NGI looks fine, I>ll have a deeper look at it.
Mathematically your solution is clear. But I have another problem.
( Probaly I misunderstand something basicly ):
After my calculation of the NCC I have a 1-DIM signal/vector containing
all calculated NCC values ( range:[-1,+1] ) and I know for each NCC value
the (x,y)-position. Let>s assume, there is only one match in the image.
So there is only one position in the NCC-vector where its value is
(nearly) 1.0.
( All other values are smaller ) And I know it>s (x,y)-position.
Let>s say it>s position is (x_i, y_i)
Now I do not understand, why I should fit a parabola, using the points:
( x_i-1, y_i-1 )
( x_i, y_i )
( x_i+1, y_i+1 )
and determing the maximum of the derivative. In my opinion, the maximum
of that parabola would be ( x_i, y_i ) ...
I hope, I could descibe my problem.
Thanks,
// leo |
|
| |
|
| Back to top |
Peter
Guest
|
| Posted: Wed Oct 29, 2008 3:14 pm Post subject: Re: Template Matching with subpixesl accuracy |
|
|
"A.Leopold" <andreas.leopold@himt.de> schrieb im Newsbeitrag
news:490822d4$1@news.arcor-ip.de...
[quote]
....
Mathematically your solution is clear. But I have another problem.
( Probaly I misunderstand something basicly ):
After my calculation of the NCC I have a 1-DIM signal/vector containing
all calculated NCC values ( range:[-1,+1] ) and I know for each NCC value
the (x,y)-position. Let>s assume, there is only one match in the image.
So there is only one position in the NCC-vector where its value is
(nearly) 1.0.
( All other values are smaller ) And I know it>s (x,y)-position.
Let>s say it>s position is (x_i, y_i)
Now I do not understand, why I should fit a parabola, using the points:
( x_i-1, y_i-1 )
( x_i, y_i )
( x_i+1, y_i+1 )
and determing the maximum of the derivative. In my opinion, the maximum
of that parabola would be ( x_i, y_i ) ...
I hope, I could descibe my problem.
Thanks,
// leo
[/quote]
x_i is a discrete integer coordinate, in>t it? Only in rare circumstances
(when working with synthetic images) the maximum of the parabola would be at
the integer coordinate. It is much more likely, that the maximum of the
parabola is in between two integer coordinates.
Let>s make a contrived example, using -x^2+11x-30. This gives the three
points (4, -2), (5, 0) and (6,0). Assume you don>t know the formula above
and these are the points you>ve got from your NCC (ignore that -2 is outside
the range for the moment). Where is the maximum of a continuous curve fit
through these three points? It must be somewhere between 5 and 6, right?
If you differentiate and solve as described, you end up with a result of
5.5, which would correspond to the desired position with sub-pixel accuracy.
I hope this makes it clearer. |
|
| |
|
| Back to top |
A.Leopold
Guest
|
| Posted: Wed Oct 29, 2008 5:09 pm Post subject: Re: Template Matching with subpixesl accuracy |
|
|
Peter schrieb:
[quote]"A.Leopold" <andreas.leopold@himt.de> schrieb im Newsbeitrag
news:490822d4$1@news.arcor-ip.de...
....
Mathematically your solution is clear. But I have another problem.
( Probaly I misunderstand something basicly ):
After my calculation of the NCC I have a 1-DIM signal/vector containing
all calculated NCC values ( range:[-1,+1] ) and I know for each NCC value
the (x,y)-position. Let>s assume, there is only one match in the image.
So there is only one position in the NCC-vector where its value is
(nearly) 1.0.
( All other values are smaller ) And I know it>s (x,y)-position.
Let>s say it>s position is (x_i, y_i)
Now I do not understand, why I should fit a parabola, using the points:
( x_i-1, y_i-1 )
( x_i, y_i )
( x_i+1, y_i+1 )
and determing the maximum of the derivative. In my opinion, the maximum
of that parabola would be ( x_i, y_i ) ...
I hope, I could descibe my problem.
Thanks,
// leo
x_i is a discrete integer coordinate, in>t it? Only in rare circumstances
(when working with synthetic images) the maximum of the parabola would be at
the integer coordinate. It is much more likely, that the maximum of the
parabola is in between two integer coordinates.
Let>s make a contrived example, using -x^2+11x-30. This gives the three
points (4, -2), (5, 0) and (6,0). Assume you don>t know the formula above
and these are the points you>ve got from your NCC (ignore that -2 is outside
the range for the moment). Where is the maximum of a continuous curve fit
through these three points? It must be somewhere between 5 and 6, right?
If you differentiate and solve as described, you end up with a result of
5.5, which would correspond to the desired position with sub-pixel accuracy.
I hope this makes it clearer.
Dear Peter,[/quote]
yes, it>s clearer now ;) I think your suggestion is the best way. I will
implement
it next week and I>m looking forward to the subpixel-results!
Thanks a lot!
// leo |
|
| |
|
| Back to top |
|
