Hough transform based method of estimating parameters

• US 6,356,647 B1
• Filed: 01/08/1999
• Issued: 03/12/2002
• Est. Priority Date: 07/19/1996
• Status: Expired due to Fees

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Bober, Miroslaw, Kittler, Josef
• Primary Examiner(s): Patel, Jayanti K.
• Application Number:
  US09/227,346
• Time in Patent Office: 1,159 Days
• Field of Search: 382/100, 382/236, 382/104, 382/105, 382/107, 382/181, 382/171, 382/173, 382/172, 382/190, 382/260-265, 382/281, 356/139.01
• US Class Current: 382/107
• CPC Class Codes: G06T 7/269 using gradient-based methods

Abstract

A Hough transform based method of estimating N parameters a=(a₁, . . . , a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method including: determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y; determining the motion parameters a that give the total support a minimum value; the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . by calculating partial derivatives dH_i=MH(Y,a_n)/Ma_n,i of the total support for a parameter estimate a_n with respect to each of the parameters a_i and evaluating the calculated partial derivatives for taking a new a_n+1; and wherein, in the evaluating of the partial derivatives, the partial derivatives dH_i are first scaled by multiplying by scaling factors dependent on the spatial extension of the region to produce scaled partial derivatives dHN_i.

Claims

1. A Hough transform based method of estimating N parameters a=(a₁, . . . .a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

determining the motion parameters a that give the total support a minimum value using a Hough transform, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . by calculating partial derivatives dH_i=MH(Y, a_n)/Ma_n,i of the total support for a parameter estimate a_n with respect to each of the parameters a₁ and evaluating the calculated partial derivatives for taking a new a_n+1, wherein, in the evaluating of the partial derivatives, the partial derivatives dH_i are first sealed by multiplying by scaling factors dependent on the spatial extension of the region to produce sealed partial derivatives dHN_i.

2. The method of claim 1, wherein for a four-parameter motion model according to:

3. The method of claim 1, wherein for an affine motion model according to:

4. The method of claim 1 comprising the additional step of selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values, and in the step of determining the motion parameters a that give the total support a minimum value, each parameter estimate taken to be a point in the grid.

5. The method of claim 4, wherein, in the evaluating of the partial derivatives, a gradient vector vd=(dHN₁, . . . , dHN_N) of the scaled partial derivatives for the parameter estimate a_n is formed and is multiplied by normalized vectors b¹, . . . , b² to form quantities M^j=vd X bⁱ, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate a_n to all neighbouring points in the grid, and the neighbouring point having the maximum vale of said quantities is taken to be the next parameter estimate a_n+1.

6. The method of claim 4, wherein, after the step of determining the motion parameters a that give the total support a minimum value, a finer resolution r_i in the parameter space for each of the parameters a_i of motion is selected, and thereafter the step of determining the motion parameters a that give the total support a minimum value is executed again for the finer resolution and the grid of points given thereby.

7. The method of claim 4, wherein, after making each of the steps of the iterative process, the resolutions r_i are set to values smaller than the values used in the step until the resolutions, in the setting thereof, have achieved predetermined values, and in the following steps the resolutions r_i being set to smaller values only after every k steps, where k is an integer <

1.

8. The method of claim 4, wherein in steps of the iterative process, a median estimate of scale is calculated for use in the step of determining the total support, the median estimate of scale calculated in every k:

th step of the iterative process, k being an integer ≧

1, k being dependent on a current spatial resolution of the pixels and the current parameter resolutions r_i.

9. The method of claim 4, wherein in the step of selecting resolutions r_i in the parameter space, the resolutions are selected to have a relation to an expected maximum value of displacement of pixels from the region Y in the first image to the following image and to the size of the region.

10. The method of claim 9, comprising the additional steps of:

after the step of determining a parameter estimate, selecting a second spatial resolution in which the first and following images are represented by the pixels, and then again executing the steps of determining the total support and of determining the motion parameters,

wherein the relation of the resolutions in the parameter space is preserved in the steps that are again executed.

11. The method of claim 1 comprising the additional steps of:

selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values, and

determining, before determining the motion parameters a in an iterative process, parameter estimates of the motion parameters a in a non-iterative process, each parameter estimate taken to be a point in the grid,

thereafter setting the resolutions r_i to values smaller than the values used in the previous step of determining,

in the step of determining the motion parameters a in the iterative process, each parameter estimate being taken to be a point in the grid.

12. The method of claim 1, wherein the iterative process is stopped when the number of steps in the iterative process exceeds an iteration threshold.

13. The method of claim 4, wherein the iterative process is stopped when the number of steps in the iterative process exceeds an iteration threshold dependent on a current spatial resolution of the pixels and the current resolutions r_i of the parameters.

14. The method of claim 1, wherein in steps of the iterative process, a median estimate of scale is calculated for use in the step of determining the total support, the iterative process stopped when the value of the median estimate of scale is below a scale threshold.

15. The method of claim 14, wherein the median estimate of scale is calculated in every step of the iteration process or in every k:

th step of the iterative process, k being an integer <

1.

16. The method of claim 1, wherein the iterative process is stopped when in the iterative process the same steps as before are taken.

17. The method of claim 1, wherein in steps of the iterative process, a median estimate of scale is calculated for use in the step of determining the total support, the median estimate of scale being calculated as a median absolute derivation (MAD) robust estimate of scale to which a positive constant is added.

18. The method of claim 17, wherein the positive constant is equal to 0.3.

19. The method of claim 1, wherein the region Y has an arbitrary shape, a centre of the coordinate system for the pixels being chosen as the centre of gravity of the region.

20. The method of claim 1, comprising the additional step of first prefiltering the first and following images by a low-pass filter giving the prefiltered first and following images a dynamic range that is larger than the dynamic range of the first and following images, using the prefiltered first and following images in the steps of determining the total support and of determining the motion parameters.

21. The method of claim 20, wherein, in the step of first prefiltering, the first and following images are filtered using a Gaussian shape filter.

22. A Hough transform based method of estimating N parameters a=(a_i, . . . . ,a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid, wherein after making each of the steps of the iterative process, the resolutions r_i are set to values smaller than the values used in the step until the resolutions, in the setting thereof, have achieved predetermined values, and in the following steps the resolution r_i are set to smaller values only after every k;

th step, where k is an integer <

1.

23. A Hough transform based method of estimating N parameters a=(a₁. . . . , a_N) of motion o a region Y in a first image to a following image, the first and following images represented, i a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining parameter estimates of the motion parameters a in a non-iterative process, each parameter estimate taken to a point in the grid,

thereafter setting the resolution r_i to values smaller than the values used in the previous step,

determining the total support N(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid.

24. A Hough transform based method of estimating N parameters a=(a₁, . . . , a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of;

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameters pace for each of the parameters a_i of motion, the selected resolution giving a grid of pints in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid, wherein the iterative process is stopped is stopped when the number of steps made in the iterative process exceeds an iteration threshold.

25. The method of claim 24, wherein the iteration threshold is selected to be dependent on a current spatial resolution of the pixels and the current resolutions r_i of the parameters.

26. A Hough transform based method of estimating N parameters a=(a_i, . . . a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a_i, a₂, . . . , each parameter estimate being a point in the grid, wherein in steps of the iterative process, a medium estimate of scale is calculated for use in the step of determining the total support, the iterative process stopped when the value of the medium estimate of scale is below a scale threshold.

27. The method of claim 26, wherein the median estimate of scale is calculated in every step of the iteration process or in every k:

th step of the iterative process, k being an integer <

1.

28. A Hough transform based method of estimating N parameters a=(a₁, . . . , a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid, wherein in steps of the iterative process, a median estimate of scale is calculated for use in the step of determining the total support, the median estimate of scale calculated in every k;

th step of the iterative process, k being an integer ≧

1, k being dependent on a current spatial resolution of the pixels and the current parameter resolutions t_i.

29. A Hough transform based method of estimating N parameters a=(a₁, . . . . ,a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r₁ in the parameter space for each of the parameters a₁ of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . . , each parameter estimate being a point in the grid, wherein the iterative process is stopped when in the iterative process the same steps as before are taken.

30. A Hough transform based method of estimating N parameters a=(a₁, . . . .,a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid, wherein in steps of the iterative process, a median estimate of scale is calculated for use in the step of determining the total support, the median estimate of scale being calculated as a median absolute deviation (MAD) robust estimate of scale to which a positive constant is added.

31. The method of claim 30, wherein the positive constant is equal to 0.3.

32. A Hough transform based method of estimating N parameters a=(a₁, . . . ., a_N) of motion of a region Y in a first image of a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid, wherein a centre of the coordinate system for the pixels is chosen as the centre of gravity of the region.

33. A Hough transform based method of estimating N parameters a=(a₁, . . . ,a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i o motion, the selected resolution giving a grid of pints in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid,

wherein, in the step of selecting resolutions r_i in the parameter space, the resolutions are selected to have a relation to an expected maximum value o displacement of pixels from the region Y in the first image to the following image and to the size of the region.

34. The method of claim 33, comprising the additional steps of:

after the step of determining a parameter estimate, selecting a second spatial resolution in which the first and following images are represented by the pixels, and then again executing the steps of determining the total support and of determining the motion parameters,

wherein the relation of the resolutions in the parameter space is preserved in the steps that are again executed.

35. A Hough transform based method of estimating N parameters a=(a₁, . . . ,a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

prefiltering the first and following images by a low-pass filter giving the prefiltered first and following images a dynamic range that is larger than the dynamic range of the first and following images,

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y of the prefiltered first and following images,

determining the motion parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . .

36. The method of claim 35, wherein, in the step of first prefiltering, the first and following images are filtered using a Gaussian shape filter.

37. A Hough transform based method of estimating N parameters a=(a₁, . . . ,a_N) of motion of a region Y in a first image to a following image, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the method comprising the steps of:

determining the total support H(Y,a) as a sum of the values of an error function for the intensities at pixels in the region Y,

selecting a resolution r_i in the parameter space for each of the parameters a_i of motion, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining the parameters a that give the total support a minimum value, the determining being made in steps of an iterative process moving along a series of parameter estimates a₁, a₂, . . . , each parameter estimate being a point in the grid, by calculating partial derivatives dH_i=MH(Y, a_n)/Ma_n,i of the total support for a parameter estimate a_n with respect to each of the parameters a_i and evaluating the partial derivatives for taking new a_n+1, wherein, in the evaluating of the partial derivatives, the partial derivatives dH_i are first scaled by multiplying by scaling factors t_i, the scaling factors having values corresponding to the resolution r_i in the parameter space, so that the scaled partial derivatives are dHN_i=dH_i A r_i.

38. The method of claim 37, wherein, in the evaluating of the partial derivatives, a gradient vector vd=(dHN₁, . .. , dNH_N) o the scaled partial derivatives for the parameters estimate a_n is formed and is multiplied by normalized vectors b¹, . . . , b^S to form quantities M¹=vd X bⁱ, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate a_n to all neighbouring points in the grid, and the neighbouring point having the maximum vale of said quantities is taken to be the next parameter estimate a_n+1.

39. The method of claim 37, wherein, after the step of determining the motion parameters a that give the total support a minimum value, a finer resolution r_i in the parameter space for each of the parameters a_i of motion is selected, and thereafter the step of determining the motion parameters a that give the total support a minimum value is executed again for the finer resolution and the grid of points given thereby.

40. A device for estimating values of N parameters a=(a₁, . .. , a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixel in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p and for calculating partial derivatives dH_i=MH(Y,a_p)/Ma_p,i of the total support for parameter values a_p with respect to each of the parameters a_i,

a decision module connected to the Hough transform module, the decision module determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a_i, a₂, . . . ., providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports and the calculated partial derivatives for the parameter estimate a_n and evaluating the received calculated partial derivatives for selecting a new parameter estimate a_n+1 to be used in the following step,

wherein the decision module in the evaluating is arranged to use scaled partial derivatives obtained from the received calculated partial derivatives dH_i by multiplying them by scaling factors independent on the spatial extension of the region Y.

41. The device of claim 40, wherein for a four-parameter motion model according to:

42. The device of claim 40, wherein for an affine motion model according to:

43. The device of claim 40, wherein the decision module is arranged to select a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values, and to select, in executing each of the steps of the iterative process, a parameter estimate as a point in the grid.

44. The device of claim 43, wherein the decision module is arranged to form, in each step of the iterative process, in the evaluating of the partial derivatives, a gradient vector vd=(dHN₁, . . . , dHN_N) of the scaled partial derivatives for the parameter estimate a_n selected in the step and to multiply the gradient vector by normalized vectors b¹, . . . , b^s to form quantities M^j=vd X bⁱ, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate a_n to all neighbouring points in the grid, and taking the neighboring point having the maximum vale of said quantities to be the parameter estimate a_n+1 to be selected in the next step.

45. The device of claim 43, wherein the decision module is arranged to select, after having determined the parameters a that give the total support a minimum value, the resolution r_i in the parameter space to a finer resolution for each of the parameters a_i, and to thereafter again determine the motion parameters a that give the total support a minimum value for the finer resolution, using the grid of points given thereby.

46. The device of claim 45, wherein the decision module is arranged to set, after making each of the steps of the iterative process, the resolutions r_i to values smaller than the values used in the step until the resolutions, in the setting thereof, have achieved predetermined values, and in the following steps the resolutions r_i being set to smaller values only after every k:

th step of the iterative process, where k is an integer >

1.

47. The device of claim 43, further comprising a control module connected to the decision module, the decision module arranged to signal each step of the iterative process to the control module, and the control module arranged compare the number o steps in the iterative process to an iteration threshold and to stop the iterative process when the number of steps exceeds the iteration threshold, the iteration threshold being dependent on a current spatial resolution of the pixels and the current resolution r_i of the parameters.

48. The device of claim 43, further comprising a scale estimation module connected to the Hough transform module and to the decision module, the scale estimation module arranged to calculate, at requests from the decision module, for steps of the iterative process, a value of a median estimate of scale and to communicate the calculated value of the median estimate of scale to the Hough transform module for use in determining the total supports, the decision module arranged to compare the calculated value of the median estimate of scale to a scale threshold and to stop the iterative process stopped hen the value of the median estimate of scale is smaller than the scale threshold, the decision module arranged to send requests to the scale estimation module for calculating the value of the median estimate of scale in every k:

th step of the iterative process, k being an integer ≧

l, k taken to be dependent on a current spatial resolution of the pixels and the current parameters resolutions t_i.

49. The device of claim 43, wherein the decision module is arranged to select, in selecting resolutions r_i in the parameter space, the resolutions to have a relation to an expected maximum value of displacement of pixels from the region Y in the first image to the following image and to the size of the region.

50. The device of claim 49, wherein the decision module is arranged to select, after determining a parameter estimate, a second spatial resolution in which the first and following images are represented by the pixels, and then again executing in the iterative process the steps of determining the total support and of determining the motion parameters, and to preserve the relation of the resolutions in the parameter space in the steps that are again executed.

51. The device of claim 40, wherein the decision module is arranged

to select a resolution t_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

to thereafter determine, before determining the motion parameters a in an iterative process, a parameter estimate of the parameters a in a non-iterative process taking the parameter estimate be a point in the grid,

to thereafter set the resolutions n to values smaller than the values used in the previous step of determining and to thereafter execute in the iterative process the determining of the parameters a taking in each step the parameters estimates to be a point in the grid.

52. The device of claim 40, further comprising a control module connected to the decision module, the decision module arranged to signal each step of the iterative process to the control module, and the control module arranged compare the number of steps in the iterative process to an iteration threshold and to stop the iterative process when the number of steps exceeds the iteration threshold.

53. The device of claim 40, further comprising a scale estimation module connected to the Hough transform module and to the decision module, the scale estimation module arranged to calculate, at requests from the decision module, for steps of the iterative process, a value of a median estimate of scale and to communicate the calculated value of the median estimate of scale to the Hough transform module for use in determining the total supports, the decision module arranged to compare the calculated value of the median estimate of scale to a scale threshold and to stop the iterative process stopped when the value of the median estimate of scale is smaller than the scale threshold.

54. The device of claim 53, wherein the decision module is arranged to send requests to the scale estimation module for calculating the value of the median estimate of scale in every step of the iteration process or in every k:

th step of the iterative process, k being an integer >

1.

55. The device of claim 40, wherein the decision module is arranged to store, for each step of iterative process, the estimated values of the parameters and to stop the iterative process when in the iterative process the same steps as before are taken.

56. The device of claim 40, further comprising a scale estimation module connected to the Hough transform module and to the decision module, the scale estimation module arranged to calculate, at requests from the decision module, for steps of the iterative process, a value of a medium estimate of scale and to communicate the calculated value of the median estimate of scale to the Hough transform module for use in determining the total supports, the median estimate of scale being calculated as a median absolute deviation (MAD) robust estimate of scale to which a positive constant is added.

57. The device of claim 56, wherein the scale estimate module is arranged to used a value of the positive constant equal to 0.3.

58. The device of claim 40, further comprising a control module connected to the Hough transform module and the decision module, the control module setting for the region Y a centre of the coordinate system for the pixels as the centre of gravity of the region.

59. The device of claim 40, further comprising a low-pass filtering module connected to the first memory means, the low-pass filtering module arranged to prefilter the first and following images by a low-pass filter and to store the prefiltered first and following images in the first memory means, the low pass-filtering module giving the prefiltered first and following images a dynamic range larger than the dynamic range of the first and following images, the Hough-transform module arranged to use the stored prefiltered first and following images in the steps of determining the total support.

60. The device of claim 59, wherein, the low-pass filtering module is arranged to use as the low-pass filter a Gaussian shape filter.

61. A device for estimating values of N parameters a=(a₁, . . . . , a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameters values a_p,

a decision module connected to the Hough transform module, the decision module;

selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports, and

setting, after making each of the steps of the iterative process, the resolutions r_i to values smaller than the values used in the step until the resolutions, in the setting thereof, have achieved predetermined values, and in the following steps setting the resolutions r_i to smaller values only after every k;

th step, where k is an integer >

1.

62. A device for estimating values of N parameter a=(a₁, . . . . ,a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p,

a decision module connected to the Hough transform module, the decision module;

selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports, and

a control module connected to the decision module, the decision module arranged to signal each step of the iterative process to the control module, and the control module arranged to compare the number of steps in the iterative process to an iteration threshold and to stop the iterative process when the number of steps exceeds the iteration threshold.

63. The device of claim 62, wherein the control module is arranged to select the iteration threshold to be dependent on a current spatial resolution of the pixels and the current resolutions r_i of the parameters.

64. A device for estimating values of N parameters a=(a₁, . . . ,a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p,

a decision module connected to the Hough transform module, the decision module,

selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports, and

a scale estimation module connected to the Hough transform module and to the decision module, the scale estimation module arranged to calculate, at requests from the decision module, for steps of the iterative process, a value of a median estimate of scale and to communicate the calculated value of the median estimate of scale to the Hough transform module for use in determining the total supports, the decision module arranged to compare the calculated value of the median estimate o scale to a scale threshold and to stop the iterative process stopped when the value of the median estimate of scale is smaller than the scale threshold.

65. The device of claim 64, wherein the decision module is arranged to send requests to the scale estimation module for calculating the value of the median estimate of scale in every step of the iteration process or in every k:

th step of the iterative process, k being an integer >

1.

66. The device of claim 65, wherein the decision module is arranged to take k as an integer ≧

1, k being dependent on a current spatial resolution of the pixels and the current parameter resolution r_i.

67. A device for estimating values of N parameters a=(a₁, . . . . , a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p,

a decision module connected to the Hough transform module, the decision module;

selecting a resolution r_i i the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports, and

wherein the decision module is arranged to store, for each step of iterative process, the parameter estimates and to top the iterative process when in the iterative process the same steps as before are taken.

68. A device for estimating values of N parameters a=(a₁, . . . ,a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for pixels in the region Y and for parameter values a_p,

a decision module connected to the Hough transform module, the decision module;

selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports, and

a scale estimate module connected to the Hough transform module and to the decision module, the scale estimation module arranged to calculate, at requests from the decision module, for steps of the iterative process, a value of a median estimate of scale and to communicate the calculated value of the median estimate of scale to the Hough transform module for use in determining the total supports, the median estimate of scale being calculated as a median absolute deviation (MAD) robust estimate of scale to which a positive constant is added.

69. The device of claim 68, wherein the scale estimation module is arranged to used a value of the positive constant equal to 0.3.

70. The device for estimating values of N parameters a=(a₁, . . . , a₂) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinates system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p,

a decision module connected to the Hough transform module, the decision module;

selecting a resolution r_i in the parameter space for each of the parameters a_i, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports, and

a control module connected to the Hough transform module and the decision module, the control module setting for the region Y a centre of the coordinate system for the pixels as the centre of gravity of the region.

71. A device for estimating values of N parameters a=(a₁, . . . , a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p,

a decision module connected to the Hough transform module, the decision module;

selecting a resolution t_i in the parameter space for each of the parameters a_i, the resolutions selected to have a relation to an expected maximum value of displacement of pixels from the region Y in the first image to the following image and to the size of the region, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports.

72. The device of claim 71, wherein the decision module is arranged to selected, after determining a parameter estimate, a second spatial resolution in which the first and following images are represented by the pixels, and then again executing in the iterative process the steps of determining the total support and of determining the motion parameters, and to preserver the relation of the resolutions in the parameter space in the steps that are again executed.

73. A device for estimating values of N parameters a=(a₁, . . . , a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a low-pass filtering module connected to the first memory means, the low-pass filtering module arranged to prefilter the first and following images by a low-pass filter and to store the prefiltered first and following images in the first memory means, the low pass-filtering module giving the prefiltered first and following images a dynamic range larger than the dynamic range of the first and following images,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of n error function for the intensities at pixels in the region Y using the stored prefiltered first and following images,

a decision module connected to the Hough transform module, the decision module determining values of the parameters a that give the total support a minimum value, the determining being made in an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . , providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports evaluating the received calculated partial derivatives for selecting a new parameter estimate a_n+1 to be used in the following step.

74. The device of claim 73, wherein the low-pass filtering module is arranged to use as the low-pass filter a Gaussian shape filter.

75. A device for estimating values of N parameters a=(a₁, . . . ,a_N) of motion of a region Y in a first image to a following image, the region having a spatial extension, the first and following images represented, in a first spatial resolution, by intensities at pixels having coordinates in a coordinate system, the device comprising:

first memory means for storing the intensities at the pixels in the first spatial resolution,

a Hough transform module connected to the first memory means for determining total supports H(Y,a_p) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values a_p and for calculating partial derivatives dH_i=MH(Y,a_p)/Ma_p,i of the total support for parameter values a_p with respect to each of the parameters a_i,

a decision module connected to the Hough transform module, the decision module,

selecting a resolution r_i in the parameter space for each of the parameters a_i, the resolutions selected to have a relation to an expected maximum value of displacement of pixels from the region Y in the first image to the following image and to the size of the region, the selected resolution giving a grid of points in the N-dimensional space of possible parameter values,

determining values of the parameters a that give the total support a minimum value, the determining being made n an iterative process, the decision module executing steps, selecting in each step a parameter estimate a_n in a series of parameter estimates a₁, a₂, . . . , the parameter estimates selected as points in the grid, providing the selected parameter estimate to the Hough transform module and receiving therefrom the determined total supports and the calculated partial derivatives for the parameter estimate a_n and evaluating the received calculated partial derivatives for selecting a new parameter estimate a_n+1 to be used in the following step;

wherein the decision module in the evaluating is arranged to use scaled partial derivatives obtained from the received calculated partial derivatives dH_i by multiplying them by scaling factors having values corresponding to the resolutions r_i in the parameter space, so that the scaled partial derivatives are dHN_i=dH_iA r_i.

76. The device of claim 75, wherein the decision module is arranged to form, in each step of the iterative process, in the evaluating of the partial derivatives, a gradient vector vd=(dHN₁, . . . . , dHN_N) of the sealed partial derivatives for the parameter estimate a_n selected in the step and to multiply the gradient vector by normalized vectors b¹, . . . . , b^s to form quantities M^j=vd X b^l, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate a_n to all neighbouring points in the grid, and taking the neighbouring point having the maximum vale of said quantities to be the parameter estimate a_p+1 to be selected in the next step.

77. The device of claim 75, wherein the decision module is arranged to select, after having determined the parameters a that give the total support a minimum value, the resolution r_i in the parameter space to a finer resolution for each of the parameters a_i, and to thereafter again determine the motion parameters a that give the total support a minimum value for the finer resolution, using the grid of points given thereby.