US 6,356,647 B1Grant
Hough transform based method of estimating parameters
Issue Date:2002-03-12
•77 Claims
•7 Drawing Sheets
Abstract
A Hough transform based method of estimating N parameters a=(a1, . . . , aN) 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 a1, a2, . . . by calculating partial derivatives dHi=MH(Y,an)/Man,iof the total support for a parameter estimate anwith respect to each of the parameters aiand evaluating the calculated partial derivatives for taking a new an+1; and wherein, in the evaluating of the partial derivatives, the partial derivatives dHiare first scaled by multiplying by scaling factors dependent on the spatial extension of the region to produce scaled partial derivatives dHNi.
Metadata
Assignee
- Telefonaktiebolaget LM Ericsson
Inventors
- Miroslaw Bober
- Josef Kittler
Application Information
Application Number:US 09/227,346
Filing Date:1999-01-08
Priority Date:1996-07-19
Art Unit:7
Classifications
IPC:
G06K 900
Field of Search:
38210038223638210438210538210738218138217138217338217238219038228135613901
Patent Drawings (7 sheets)
Description
[0002] This application is a continuation of Ser. No. PCT/SE97/01293 filed Jul. 18, 1997.
Technical Field
[0003] The present invention relates to a method and a device for simultaneous motion estimation and segmentation of digitized images, in particular moving pictures.
Background of the Invention and Prior Art
[0004] In compression of digitized motion pictures the use of motion estimation is a widely used and powerful tool. One commonly used technique for motion estimation is Block Matching (BM) and variants, see for instance A. N. Netravali, B. G. Haskell “Digital Pictures Representation, Compression and Standards”, Planum Press, ISBN 0-306-44917-X.
[0005] Block matching techniques usually make the following assumptions:
[0006] 1) A block moves with translational motion in the image plane.
[0007] 2) There is only one moving object within a block.
[0008] 3) The intensities of the pixels are preserved in time.
[0009] There are several problems with the block Matching technique and its variants:
[0010] i) They give an erroneous estimate if a block covers several moving objects or uncovered background.
[0011] ii) They are sensitive to noise in the input frames.
[0012] iii) The accuracy of the estimate is generally poor, especially if no sub-pixel matching is performed. If subpixel matching is performed the technique is computationally expensive and real-time implementation is difficult to obtain.
[0013] iv) The estimate is poor for blocks moving with non-translatory motion.
[0014] v) The estimates are sensitive to illumination changes.
[0015] Other frequently used techniques for motion estimation are based on phase-correlation. Their deficiencies are similar to the ones of block matching, i.e. a poor estimate accuracy and robustness to noise, and inability to cope with complex motions, i.e. non-translational and multimodal motions.
[0016] Another possible technique is to perform motion estimation based on an image which as been segmented into regions. The image can for example be segmented into regions of slowly varying intensity.
[0017] A region based technique, which is conceptually based on the Hough transform and uses Robust Statistical Kernels has been presented in the papers M. Bober and J. Kittler, “Robust Motion Analysis”, in the CVPR Conference proceedings, 1994, pages 947-952; M. Bober and J. Kittler, “Estimation of Complex Multi-modal Motion: An Approach based on Robust Statistics and Hough Transform”, Proceedings of the British Machine Vision Conference, 1993 pages 239-248 and M. Bober and J. Kittler, “Estimation of general multimodal motion: an approach based on robust statistics and Hough transform”, Image and Vision Computing, 1994, vol 12, No 12, pages 661-668, which are incorporated herein by reference.
[0018] This method performs simultaneous motion estimation and segmentation by iteratively maximising the support defined by a sum of errors weighted by a robust kernel between two regions: one in a reference frame and the other in the consecutive frame. The position and size of the reference block are arbitrary; whereas the position of the consecutive region is determined by a geometric transformation of the reference block. This prior art technique is also illustrated by the flow diagram in FIG. 8, which shows how input frames are low-pass filtered in a block 801. Then a coarse resolution is set in a block 803, and motion parameters are initialised in a block 805. Thereafter derivatives are calculated in a block 807, which are used for updating the estimate in a block 809. Based on the estimate a new scale is computed in a block 811. After this it is checked in block 813 if the path has retraced. If that condition is false the process returns to the block 807, else a new check is made in a block 815 if the finest resolution is reached. If that is the case the process is terminated in a block 819, and else the resolution is changed to a finer resolution in a block 817 and then the process returns to the block 807.
[0019] The parameters of the transformation which maximise the support measure are assumed to describe the motion of the block or image. According to the prior art technique described in the papers by M. Bober and J. Kitler, cited above, the statistical properties of the transformed frame difference are computed after each iteration and the shape of the kernel function is adjusted accordingly.
[0020] Contributions to the support measure from pixels with large motion compensation errors are weighted down or removed by the robust kernel. Such pixels usually belong to objects moving independently or a covered/occluded background and are termed outliers. Thus, a mechanism for simultaneous motion estimation and segmentation is introduced by the robust kernel.
[0021] The technique described in the above cited prior art papers solved some of the problems associated with the block matching and correlation-based techniques. Hence, the technique can cope with non-translatory motions, e.g. affine models, and with multiple moving objects within a block. However, the technique still exhibits several deficiencies, such as failing to converge for regions with complicated motions and still being computationally expensive.
Summary of the Invention
[0022] It is an object of the present invention to overcome the problems associated with the prior art technique and to increase its robustness and the quality of the motion segmentation.
[0023] This object is obtained by adding new steps and by modification of some parts of the prior art technique.
[0024] In particular, the invention aims at solving the problems with the convergence of the prior art technique as described in the above cited papers by M. Bober and J. Kittler, and to increase the computational efficiency thereof. According to the invention, a modified gradient-based search technique is used and the centre of the coordinate system is placed in the centre of the region, image or block, where the estimation is applied. The use of such modified gradients, i.e. gradients scaled by different factors reduce the number of iterations needed, and thus also the complexity of the technique. It also improves the convergence, i.e. the modified search is more likely to converge to the true motion parameters.
[0025] Further, the median absolute deviation is used in the prior art technique as scale estimate. This has turned out to cause problems with convergence and accuracy. When there is only one moving object within a block, during iterations on finer resolutions, the values of scale become very small and many pixels, which are not outliers, are removed from the estimation process. To overcome this deficiency, a small constant is added to the MAD (Median Absolute Deviation) estimate of scale.
[0026] Further, in the prior art technique, the scale of residual errors has to be recomputed after each update of motion parameters. This has been found to be very inefficient, and the efficiency of the method has been found to be significantly improved by introducing the following modification. When iterations proceed on the coarse resolution in the parameter space, the scale is updated after each step. However, on finer resolutions, i.e. subpixel resolution in case of a translational motion model, the scale is only updated every k steps, k being an integer greater than one.
[0027] Moreover, the optimisation on the discrete grid, as described in the prior art, does not specify how to select a good starting point for the interations after a change of resolution in the parameter space. The description only defines the condition for change of the resolution in the parameter space when the path retraces. It has now been found that if during iterations, a record of the point in the parameter space corresponding to the lowest value of the error function is saved and used as the starting point at finer resolution, a significant improvement of the computational efficiency is obtained.
[0028] In addition, a good iteration termination condition is not stated in the prior art. However, it has been found that the iteration can be terminated, and provide a good result when one of the following conditions is fulfilled:
[0029] i) the number of iterations at a given resolution exceeds the iteration threshold, or
[0030] ii) the value of the median estimate of scale is below the scale threshold, or
[0031] iii) the path is retraced on the finest resolution:
[0032] Furthermore, the speed and convergence of the prior art technique have been found to be possible to improve, e.g. for sequences with large motion. In order to improve the speed and convergence, a hybrid scheme where the initial estimate at coarse resolution is determined by a non-iterative technique, such as the phase-based technique, can be used. That is, first at the low resolution stage a fast non-iterative technique is used. Then, at the medium or fine resolution stages the modified Hough Transform using Robust Statistical Kernels is used.
[0033] Further, the prior art technique is only applied to a block, i.e. regions of rectangular size, and the centre of the coordinate system is placed in the corner of the image. However, it has been found that the framework is not limited to block shaped regions, but can be extended to regions of any shape. In the latter case, the placement of the centre of the coordinate system however becomes crucial for the performance of the technique. It has been found that by using the centre of gravity of the reference region as the origin of the coordinate system, a good performance is obtained.
[0034] Further, in the prior art technique, it is not specified what the specific resolution for motion parameters a1. . . a6 nor what the relation between parameters should be. A solution to this problem is to relate the resolution in parameter space to the maximum displacement which the estimator is expected to estimate and to the size of the region.
[0035] Finally, the accuracy of the prior art technique has been found to be improved by prefiltering the initial image with a low-pass filter, preferably Gaussian shaped, and then storing the resulting image in an array with increased dynamic range. All successive processing is performed on the images stored with increased dynamic range.
[0036] The technique can employ any parametric motion model. It is particularly suited to be used in:
[0037] 1) a translational motion model, that is:
[0038] dx=a1
[0039] dy=a2
[0040] 2) a four-parameter motion model, that is:
[0041] dx=a1x−a2y+a3
[0042] dy=a2x+a1y+a4
[0043] 3) an affine motion model, that is:
[0044] dx=a1x+a2y+a3
[0045] dy=a4x+a5y+a6
[0046] Where dx, dy are the components of the displacement vector d=(dx, dy) for a pixel at location (x, y), and where a=(a1. . . a6) are the motion parameters.
Description of the Figures
[0047] The present invention will now be described in more detail by way of a non-limiting embodiment, and with reference to the accompanying drawings, in which:
[0048] FIG. 1 is a general block diagram.
[0049] FIG. 2 shows the steps involved in the proprocessing block of FIG. 1.
[0050] FIG. 3 shows the Robust Hough Transform Block of FIG. 1 in more detail.
[0051] FIGS. 4aand 4bshow different segmentations of an image and the position of the coordinate system.
[0052] FIGS. 5a-5dshow the operation of a parameter space memory, and the decision mechanism.
[0053] FIG. 6 shows an example how the resolutions in the image and parameter space are changed.
[0054] FIG. 7 is an example of the value of k's for various combinations of resolutions.
[0055] FIG. 8 is a general flow diagram of the prior art technique.
Description of a Preferred Embodiment
[0056] FIG. 1 depicts a general block diagram of the technique. It consists of three main processing blocks to which consecutive images are fed:
[0057] a Preprocessing Block (PB) 101,
[0058] a Robust Hough Transform Block (RHTB) 103, and
[0059] a Postprocesing Block (PPB) 105
[0060] The steps involved in these processing blocks will be explained in more detail below.
[0061] FIG. 2 illustrates the steps carried out in the preprocessing block 101. Firstly, several consecutive digitized images 201 are low-pass filtered by a low-pass filtering module (LPM) 203, where the filter used preferably is Gaussian shaped, and the result is stored with increased dynamic resolution.
[0062] Thus, the LPM 203 performs low-pass filtering (smoothing) of the images. For example, the images are convolved with two separable 3 tap filters having the coefficients {¼, ½, ¼} in the x and y directions. The number of times the image passes the filter depends on the image resolution, for example 2 passes for QCIF and three passes for a CIF resolution can be used. If the input image is integer valued and represented by 8 bpp, the output image from the low-pass filter is float valued, due to the fact that the filter coefficients are float valued.
[0063] For example, the input image grey-levels are stored as 8 bits as in the case shown by FIG. 2, i.e. dynamic range 0-255, then the low-pass filtered image is stored as a 12 bits image, i.e. an image having 12 bpp, in a memory 207, whereby the information of the float values of the float valued output image can be used in the further processing.
[0064] Secondly, a Gaussian pyramid formed by images subsampled to different spatial resolutions (Srn, . . . , Sr2, Sr1) is constructed, where Sr1 is the original spatial resolution. This is performed by recursive filtering in the LPM module 203 and subsampling of each of the images in the subsampling module (SSM) 205. The results of the subsampling (se, sf), i.e. the subsampled versions at different spatial resolutions (Sr2, . . . , Srn) of the original images are stored in corresponding memories. Thus, as illustrated in the figure, first the low-pass filtered image (sc) is subsampled in the SSM module 205. The result (se) is stored in a memory 209. The subsampled image (sd) is also fed back to the LPM module 203 and low-pass filtered again, subsampled and stored in a memory 211. The process can then continue in this manner until a desired number of resolutions is obtained.
[0065] A Gaussian pyramid is constructed by recursively subsampling the low-pass filtered image by a factor of 1, both horizontally and vertically, i.e. the value of a certain pixel within a 1×1 block is selected to represent the entire 1×1 block. The process of filtering and subsampling is performed (n−1) times, where n is the number of resolutions in the pyramid. Any pixel from the 1×1 block can be chosen to represent the subimage at different degrees of resolution. However, the choice should be consistent, e.g. the upper left pixel can be chosen.
[0066] The number of spatial resolutions used (n) depends on the initial resolution of the image and the expected range of motion. For example, for the Common Interchange Format (CIF) image size two resolutions could be used (n=2), and a subsampling factor equal to four (l=4).
[0067] Motion estimation and segmentation take place in the Robust Hough Transform Block (RHTB), which is illustrated in FIG. 3. The following procedure can be applied either to the entire image, see FIG. 4a, or to several regions of arbitrary shape (A,B,C, . . . ) one at a time, as shown in FIG. 4b. The initial segmentation into regions can be based on image intensity (colours) or motion based segmentation calculated by the RHT technique from previous frames can be used. The Robust Hough Transform Block 103 comprises a Hough Transform Module (HTM) 301, a Decision Module (DM) 303, a Control Module (CM) 305 and a Scale Estimation Module (SEM) 311.
[0068] The control module 305 has an overall control of the estimation process and performs the following tasks:
[0069] Selection of the initial values of the parameters used in the estimation process, namely the spatial resolution of the images (Sr) and the initialisation value for motion parameters (Sp). The initial spatial resolution is set by means of the switch sw1 controlled by the CM module 305 via a signal on the line (sw). Depending on which spatial resolution is set by the CM module 305 the images corresponding to that particular spatial resolution (Sr) are fed to the HTM module 301 on the line (sg). The initialisation value for motion parameters is sent to the DM 303 on a line (sp).
[0070] Changes to the spatial resolution of images used for estimation during the iterative process. Once the estimation at spatial resolution (sr) is completed, which is detected by the DM module 303, a signal from the DM 303 is issued on the line (so) to the CM module. The CM module 305 then checks for a termination condition. If a condition is fulfilled, the estimation process is completed. Otherwise, images at a finer spatial resolution are selected by means of signalling on the line (sw) to the switch sw1, and the process then continues.
[0071] Deciding when the estimate of scale (su) should be updated and informing the SEM module 311 via signal (st) to recalculate the scale. The CM module 305 counts the number of iterations, each iteration is signalled via line (so) from the DM module 303, and compares the count with a threshold, which is depending on both the current spatial resolution (Sr) and the current parameter resolution (Pr).
[0072] The decision at which spatial resolution the estimation should start depends on whether any a priori information on motion of the region is available.
[0073] The estimation usually starts at a coarse or medium spatial resolution, i.e. at resolution Srn, where n>1, unless a motion parameter initialisation value (sr) is available. The initialisation value sr may be based on the estimate from a neighbouring block or region, or other motion estimator may be used to obtain a coarse estimate of motion. When initialisation is available, the estimation may start at the coarsest (Srn), medium (Sr (n−1), . . . , Sr2) or finest spatial resolution (Sr1).
[0074] The DM module 303 performs two tasks:
[0075] 1) it selects the resolution in the parameter space (Pr), and
[0076] 2) it controls the iterative process by updating the values of motion parameters and detecting the termination condition.
[0077] The HTM module 301 computes the value of support (sk) as described in M. Bober and J. Kittler, “Robust Motion Analysis”, in the CVPR Conference proceedings, 1994, pages 947-952, and the derivatives (s1) of the support surface (Hough surface) for a given value of motion parameters (sm), which are provided by the Decision Module (DM) 303. Values of support (sk) and derivatives (s1), which preferably are scaled according to the paragraphs below, are passed back to the Decision Module DM 303 for analysis. The DM module updates the estimate of value of the motion parameters (sm) and detects the termination condition which is signalled on the line (so) to the CM module 305.
[0078] The motion analysis usually starts on a coarse resolution in the parameter space (Pr). The motion parameters (sm) are initially set to either no-motion case or to some initialisation value (sp). The DM module 303 decides on the update of the motion parameters, i.e. the next position in the parameter space as illustrated by FIG. 5c. This decision is based on the value of the partial derivatives dHion line (s1) calculated by the HTM module 301 as:
[0079] dHi=∂H(, a)/∂ai
[0080] The values of each partial derivatives dHiis scaled by means of factors, which are dependent on the spatial extension of a current region, and in a preferred embodiment factors, t1, t2, t3, t4and t5, computed as follows are used in the different models as described below.
[0081] t1=Σ(pε|x+y|; t2=Σ(pε|x−y|; t3=Σ(pε1; t4=Σ(pε|x|; t5=Σ(pε|y|
[0082] where is a set of all pixels included in the estimation, that is all pixels, p=(x, y), from a region except outliers, and x and y being the pixel location in the x and y directions of a coordinate system. The scaled derivatives dHNiare then computed as follows:
[0083] For the translational motion case, no scaling is performed.
[0084] For the four parameter motion model case:
[0085] dHN1=dH1/t1; dNH2=dH2/t2; dHN3=dH3/t3dHN4=dH4/t3
[0086] and for the affine motion model:
[0087] dHN1=dH1/t4; dHN2=dH2/t5; dHN3=dH3/t3dHN4=dH4/t4; dHN5=dH5/t5; dHN6=dH6/t3
[0088] By performing the scaling of the partial derivatives in the manner shown above, a much faster and more reliable convergence is obtained.
[0089] This is due to the fact that if un-scaled derivatives are used, the search tend to favour (be more sensitive to) certain parameters, i.e. a1, a2for the four parameter motion model and a1, a2, a4, and a5for the affine model. These parameters are over-compensated, i.e. they are changed very often and the search routine has to perform many iterations in order to return to the optimal values.
[0090] There is also an alternative scaling procedure which has been proved to produce good results and which is more computationally efficient. In this alternative procedure each partial derivative dHiis scaled by a factor corresponding to the current resolution in the parameter space, in particular a multiplication with the current resolution riin the parameter space for the corresponding parameter ai.
[0091] dHNi=dHi*ri
[0092] Such scaling is then performed instead of the above described scaling with the factors t1-t5.
[0093] The scaled partial derivatives form a gradient vector vd=(dHN1, . . . , dHNj) in the parameter space, see FIG. 5c. There are 3 possible decisions on update in each component of motion vector. These decisions are: increase, no change or decrease the value of a component. Thus, there are 3N−1 possible directions, N being the number of motion model parameters, since there must be at least one change. For example for the translational motion model (N=2) there are 8 possible decisions.
[0094] A set of basis vectors {b1, . . . , bs}, where s=3N−1, is constructed, each vector being associated with one possible direction. Each vector bi=(b1i, . . . , bNi), where N=2 for the translational motion model, N=4 for the four parameter motion model and N=6 for the affine model, is constructed as follows. The component b1ihas a value of −1, 0, or 1 depending on whether the decision involves decrease, no change, or increase in the corresponding component of the motion vector a=(a1, . . . , ). Each vector biis then normalised so that the norm equals 1. FIG. 5dshows all vectors bifor the translational motion model. For example, for the four parameter motion model and the following decision: [a1—no change, a2—increase, a3—decrease a4—no change], the corresponding vector bi=w*(0, 1, −1, 0) where
[0095] w=1/sqrt (02+12+(−1)2+02)
[0096] In each iteration the best decision is selected, that is the one which maximises the scalar product of vd and bi, i.e. maximises the following expression:
[0097] Mi=vd·bi
[0098] The HTM module 301 also provides an Outlier Map 307 and a Transformed Frame Difference Map (TFD) 309. The values of the TFD Map 309 (si) are passed to the SEM module 311, which calculates a scale of residual errors (su), if requested by the CM module 305. The scale of the residual errors does not have to be recomputed after each iteration step. By calculating and updating the value of the scale every k steps, where k is an integer greater than one, the computation complexity can be reduced. The value of the parameter k depends on the resolution in the parameter space and suitable values for k are shown on FIG. 7, and will be further discussed below.
[0099] Also, in order to improve the speed and convergence, a hybrid scheme where the initial estimate at coarse resolution is determined by a non-iterative technique, such as the phase-based technique, can be used. That is, first at the low, coarse resolution stage a fast non-iterative technique is used. Then, at the medium or finest resolution stages the modified Hough Transform using Robust Statistical Kernels is used.
[0100] The Segmentation Map, i.e. the Outlier Map 307 is a binary image with a symbol, indicating if the pixel is considered to be an inlier or outlier, attached to each pixel.
[0101] Whether a pixel is an inlier or an outlier depends on the value of the TFD map 309 for that pixel and the current value of the scale estimate (su). The TFD map is a float valued image with the transformed frame difference for each pixel calculated for the current value of motion parameters (sm).
[0102] In order to determine if a pixel is an outlier, the following operations are performed in a preferred embodiment. The absolute value (abs) of the TFD value for a given pixel is compared to the current value of the scale estimate. If abs(TFD-value) is greater than 3 * the scale estimate (sca), where sca is defined below, the point is considered an outlier, else it is considered to be an inlier.
[0103] A Parameter Space Memory, which is a part of the DM module, records all positions visited in the parameter space and the corresponding support. Each new position in the parameter space is checked against this list, shown in FIG. 5b. If this position has already been visited, i.e. the positions for which calculations have been made, see positions s3, s7 in FIG. 5a, this fact is detected by the decision module, and a change of the resolution in parameter space follows, i.e. to a finer resolution.
[0104] Estimation continues at a finer resolution, starting from a position with the greater support, that is position s5 in the case shown. The starting position has been shown to be very important for the performance of the technique and by using the point having the greatest support as a starting point the performance is increased. The CM module 305 decides whether to continue motion estimation on a sequence with finer spatial resolution Sr. Once the finest resolution is reached, this fact is signalled to the control module 305 (CM) via a signal (so). The process is terminated if one of the following criteria is fulfilled:
[0105] the processing on the finest spatial resolution Sr1 is completed, or
[0106] if the number of iterations on the fine resolution exceeds the iteration threshold, or
[0107] if the value of the median estimate of scale as defined hereinafter is below the scale threshold.
[0108] For example, the values of the thresholds can be selected as:
| Iteration threshold | 200 iterations | |
| Scale threshold | 0.35 grey-level | |
[0109] where 0 denotes black and 255 denotes white in the grey-scale.
[0110] If continuation is selected, motion parameters from the coarser spatial resolution are transformed to the finer resolution and used as initialisation parameters (sp).
[0111] The optimisation search for the maximum in the parameter space is performed iteratively, and during the optimisation process motion parameters can only take discrete values. Such an optimisation process is herein referred to as an optimisation on a discrete grid. The coarseness of the discrete grid, i.e. the resolution in the parameter space, can be different for different motion parameters. The maximum displacement of an object, object size and the resolution in the parameter space should preferably be related as explained in the following paragraph.
[0112] The following tables show the preferred values for the different parameters, which have been found to provide good convergence, for a translational, four parameter motion model and affine motion model.
| Translational motion model: |
[0113] where d [pixels] is the displacement, i.e. the maximum translation for any pixel from the region, or maximum expected pixel displacement, for example most coding techniques limit such displacement to 16 pixels for CIP images, and M [pixels] is the average pixel distance from the centre of the coordinate system calculated for all pixels within a region. An example how the resolutions in the image (Srn) and parameter space (Prn) are changed is shown in FIG. 6. This example assumes the translational motion model, with two spatial resolutions Sr1—original resolution, and Sr2—the original image subsampled by four.
[0114] In the example there are four resolutions in the parameter space: Pr1 equal to 1.25, Pr2 equal to 0.25, Pr3 equal to 0.05 and Pr4 equal to 0.01. The estimation starts at coarse resolutions both in the image space (Sr2) and in the parameter Space (Pr1), shown at position 1 on the graph. In the next step, the resolution in the parameter space is increased to 0.25 (Pr2), shown at position 2. Since this is the finest resolution in the parameter space for this spatial resolution (Sr2), the estimation at this spatial resolution is completed. This fact is signalled on line (so) to the Control Module CM 305 which decides whether to continue the estimation on a finer resolution in the image space. In the example the estimation process continues at spatial resolution Sr1, positions 3, 4 and 5, after the CM module 305 has signalled to the switch sw1 via the line (sw) that the spatial resolution Sr1 now is to be fed to the HTM module 301.
[0115] The SEM module 311 recomputes the scale of residual errors at each request on the request line (st) from the Decision Module 303. The scale can be updated after every iteration or each k iterations, where k can vary depending on the spatial and parameter resolution. The estimate of scale, i.e. the scale of residual errors, is calculated as the Median Absolute Deviation (MAD) as defined in M. Bober and J. Kittler, “Robust Motion Analysis”, in the CVPR Conference proceedings, 1994, pages 947-952, and increased by a constant C, i.e.: scale estimate: sca=1.48 * median(|ε(di)−median(ε(di)|)+C
[0116] The value of the constant C is preferably 0.3, which by means of experiments has been found to be a suitable value. The maximum value of the scale estimate is usually around 10, but can theoretically be more, when the estimation starts and has a lower limit at C, which in this example is equal to 0.3.
[0117] FIG. 7 illustrates an example of the values of k's for various combinations of the resolutions in the image space Sr and in the parameter space Pr. The estimate of scale is returned to the HTM module, through the signal (su).
[0118] Once the estimation is terminated by the CM module 305, the estimator in the HTM module 301 outputs the motion parameters (sh) and the Outlier map (sj). The outlier map is analyzed for large spatially coherent region(s) of outliers. The presence of such regions signals multiple motions. If motion of such remaining regions is of interest, the estimation process can be restarted solely for these remaining region(s). The analysis for large spatially coherent region(s) is performed by means of majority filtering, which works in the following manner:
[0119] First a window size is chosen, in the preferred case a window size of 3×3 or 5×5 is chosen.
[0120] Then this window is centred around each pixel in the image and the number of outliers within the window is counted.
[0121] If the number of outliers is greater than half of the number of pixels in the window, i.e. greater than 4 or 12 for the 3×3 or 5×5 window, respectively, then the considered pixel is determined to be an outlier and is labelled accordingly.
[0122] Else the pixel is labelled inlier.
[0123] The inlier region is usually the largest one and the estimated motion parameters correspond to its motion.
[0124] Finally, it has been found that the framework as described herein is not limited to block shaped regions, but can be extended to regions of any shape. However, in the latter case, the placement of the centre of the coordinate system has turned out to be crucial for the performance of the technique. It has been found that by using the centre of gravity of the reference region as the origin of the coordinate system, good performance is obtained.
[0125] In the technique, the optimisation procedure becomes very fast. This is due to the fact that an exhaustive search, which is used for instance by Block Matching techniques, is avoided. The proposed modifications improve speed and convergence of the technique. The accuracy of the final estimate is also improved. Some of the changes make real time implementation feasible. The technique described herein has a broad use in the image compression and coding domain.
Claims
What is claimed is:
1. A Hough transform based method of estimating N parameters a=(a1, . . . .aN) 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 a1, a2, . . by calculating partial derivatives dHi=MH(Y, an)/Man,iof the total support for a parameter estimate anwith respect to each of the parameters a1and evaluating the calculated partial derivatives for taking a new an+1, wherein, in the evaluating of the partial derivatives, the partial derivatives dHiare first sealed by multiplying by scaling factors dependent on the spatial extension of the region to produce sealed partial derivatives dHNi.
2. The method of claim 1, wherein for a four-parameter motion model according to:
dx=a1x−a2Yi y+a3
dy=a2x+a1y+a4
dHN1=dH1/t1; dHN2=dH2/t2
dHN3=dH3/t3; dHN4=dHN4=dH4/t3
t1=φ(p0Y)*x+y*; t2=φ(p0Y) *x−y*; t3=φ(P0Y)1;
where dx, dy are components of a displacement vector d=(dx,dy) for apixel at a location (x, y), the scaled partial derivatives are calculated as follows:
where the factors t1-t3are computed as follows:
where Y is a set of all pixels in the region Y.
3. The method of claim 1, wherein for an affine motion model according to:
dx=a1x+a2y+a3
dy=a4x+a5y+a6
dHN1=dH1/t4; dHN2=dH2/t5; dHN3=dH3/t3
dHN4=dH4/t4; dHN5=dH5/t5; dHN5=dH6/t3
t3=φ(p0Y)1; t4=φ(p0Y)*x*; t5=φ(p0Y) *y*
where dx, dy are components of a displacement vector d=(dx,dy) for a pixel at a location (x, y), the scaled partial derivatives are calculated as follows:
where the factors t3-t5are computed as follows:
where Y is a set of all pixels included in the region Y.
4. The method of claim 1 comprising the additional step of selecting a resolution riin the parameter space for each of the parameters ai, 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=(dHN1, . . . , dHNN) of the scaled partial derivatives for the parameter estimate anis formed and is multiplied by normalized vectors b1, . . . , b2to form quantities Mj=vd X bi, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate anto 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 an+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 riin the parameter space for each of the parameters aiof 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 riare 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 ribeing 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 ri.
9. The method of claim 4, wherein in the step of selecting resolutions riin 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 riin the parameter space for each of the parameters ai, 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 rito 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 riof 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=(ai, . . . . ,aN) 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 riin the parameter space for each of the parameters aiof 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 a1, a2, . . . , each parameter estimate being a point in the grid, wherein after making each of the steps of the iterative process, the resolutions riare 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 riare 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=(a1. . . . , aN) 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 riin the parameter space for each of the parameters aiof 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 rito 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 a1, a2, . . . , each parameter estimate being a point in the grid.
24. A Hough transform based method of estimating N parameters a=(a1, . . . , aN) 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 riin the parameters pace for each of the parameters aiof 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 a1, a2, . . . , 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 riof the parameters.
26. A Hough transform based method of estimating N parameters a=(ai, . . . aN) 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 riin the parameter space for each of the parameters aiof 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 ai, a2, . . . , 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=(a1, . . . , aN) 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 riin the parameter space for each of the parameters aiof 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 a1, a2, . . . , 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 ti.
29. A Hough transform based method of estimating N parameters a=(a1, . . . . ,aN) 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 r1in the parameter space for each of the parameters a1of 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 a1, a2, . . . . , 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=(a1, . . . .,aN) 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 riin the parameter space for each of the parameters aiof 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 a1, a2, . . . , 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=(a1, . . . ., aN) 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 riin the parameter space for each of the parameters aiof 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 a1, a2, . . . , 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=(a1, . . . ,aN) 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 riin the parameter space for each of the parameters aio 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 a1, a2, . . . , each parameter estimate being a point in the grid,
wherein, in the step of selecting resolutions riin 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=(a1, . . . ,aN) 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 a1, a2, . . . .
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=(a1, . . . ,aN) 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 riin the parameter space for each of the parameters aiof 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 a1, a2, . . . , each parameter estimate being a point in the grid, by calculating partial derivatives dHi=MH(Y, an)/Man,iof the total support for a parameter estimate anwith respect to each of the parameters aiand evaluating the partial derivatives for taking new an+1, wherein, in the evaluating of the partial derivatives, the partial derivatives dHiare first scaled by multiplying by scaling factors ti, the scaling factors having values corresponding to the resolution riin the parameter space, so that the scaled partial derivatives are dHNi=dHiA ri.
38. The method of claim 37, wherein, in the evaluating of the partial derivatives, a gradient vector vd=(dHN1, . .. , dNHN) o the scaled partial derivatives for the parameters estimate anis formed and is multiplied by normalized vectors b1, . . . , bSto form quantities M1=vd X bi, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate anto 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 an+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 riin the parameter space for each of the parameters aiof 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=(a1, . .. , aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values apand for calculating partial derivatives dHi=MH(Y,ap)/Map,iof the total support for parameter values apwith respect to each of the parameters ai,
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 anin a series of parameter estimates ai, a2, . . . ., 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 anand evaluating the received calculated partial derivatives for selecting a new parameter estimate an+1to 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 dHiby 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:
dx=a1x−a2y+a3
dy=a2x+a1y+a4
dHN1=dH1/t1; dHN2=dH2/t2
dHN3=dH3/t3; dHN4=dH4/t3
t1=φ(p0Y)*x+y*; t2=φ(p0Y)*x−y*; t3=φ(p0Y)1;
where dx, dy are components of a displacement vector d=(dx,dy) representing the displacement of a pixel in the first image at coordinates x, y in the coordinate system to new coordinates in the following image, the decision module is arranged to calculate the scaled partial derivatives to be used in the evaluating as follows:
the factors t1-t3computed as follows:
where Y is a set of all pixels in the region Y in the first image.
42. The device of claim 40, wherein for an affine motion model according to:
dx=a1x+a2y+a3
dy=a4x+a3y+a6
dHN1=dH1/t4; dHN2=dH3/T3; dHN3=dH3/T3
dHN4=dH4/t4; dHN5=dH5/t5; dHN8=dH8/t3
t3=φ(p0Y)1; t4=φ(p0Y)*x*; t5=φ(p0Y)*y*
where dx, dy are components of a displacement vector d=(dx,dy) representing the displacement of a pixel in the first image at coordinates x, y in the coordinate system to new coordinates in the following image, the decision module is arranged to calculate the scaled partial derivatives to be used in the evaluating as follows:
the factors t3-t5computed as follows:
where Y is a set of all pixels included in the region Y in the first image.
43. The device of claim 40, wherein the decision module is arranged to select a resolution riin the parameter space for each of the parameters ai, 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=(dHN1, . . . , dHNN) of the scaled partial derivatives for the parameter estimate anselected in the step and to multiply the gradient vector by normalized vectors b1, . . . , bsto form quantities Mj=vd X bi, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate anto all neighbouring points in the grid, and taking the neighboring point having the maximum vale of said quantities to be the parameter estimate an+1to 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 riin the parameter space to a finer resolution for each of the parameters ai, 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 rito 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 ribeing 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 riof 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 ti.
49. The device of claim 43, wherein the decision module is arranged to select, in selecting resolutions riin 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 tiin the parameter space for each of the parameters ai, 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=(a1, . . . . , aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameters values ap,
a decision module connected to the Hough transform module, the decision module;
selecting a resolution riin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . . , 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 rito 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 rito smaller values only after every k:th step, where k is an integer >1.
62. A device for estimating values of N parameter a=(a1, . . . . ,aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values ap,
a decision module connected to the Hough transform module, the decision module:
selecting a resolution riin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . . , 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 riof the parameters.
64. A device for estimating values of N parameters a=(a1, . . . ,aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values ap,
a decision module connected to the Hough transform module, the decision module,
selecting a resolution riin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . . , 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 ri.
67. A device for estimating values of N parameters a=(a1, . . . . , aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values ap,
a decision module connected to the Hough transform module, the decision module;
selecting a resolution rii the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . . , 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=(a1, . . . ,aN) 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,ap) as a sum of values of an error function for pixels in the region Y and for parameter values ap,
a decision module connected to the Hough transform module, the decision module;
selecting a resolution riin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . , 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=(a1, . . . , a2) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values ap,
a decision module connected to the Hough transform module, the decision module:
selecting a resolution riin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . , 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=(a1, . . . , aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values ap,
a decision module connected to the Hough transform module, the decision module:
selecting a resolution tiin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . , 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=(a1, . . . , aN) 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,ap) 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 anin a series of parameter estimates a1, a2, . . . , 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 an+1to 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=(a1, . . . ,aN) 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,ap) as a sum of values of an error function for the intensities at pixels in the region Y and for parameter values apand for calculating partial derivatives dHi=MH(Y,ap)/Map,iof the total support for parameter values apwith respect to each of the parameters ai,
a decision module connected to the Hough transform module, the decision module,
selecting a resolution riin the parameter space for each of the parameters ai, 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 anin a series of parameter estimates a1, a2, . . . , 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 anand evaluating the received calculated partial derivatives for selecting a new parameter estimate an+1to 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 dHiby multiplying them by scaling factors having values corresponding to the resolutions riin the parameter space, so that the scaled partial derivatives are dHNi=dHiA ri.
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=(dHN1, . . . . , dHNN) of the sealed partial derivatives for the parameter estimate anselected in the step and to multiply the gradient vector by normalized vectors b1, . . . . , bsto form quantities Mj=vd X bl, the normalized vectors obtained by normalizing vectors extending in the N-dimensional parameter space from the parameter estimate anto all neighbouring points in the grid, and taking the neighbouring point having the maximum vale of said quantities to be the parameter estimate ap+1to 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 riin the parameter space to a finer resolution for each of the parameters ai, 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.
Patent Citations (5)
Non-Patent Literature (9)
- Signals Systems and Computers, “Recursive Hough Transform Tracking For Sonar Motion Estimation”, vol. 1, 1988, pp. 440-444.Applicant
- Electrical and Computer Engineering, “Detecting corenrs using the ‘patchy’ Hough transform”, 1994, vol. 2, pp. 576-579.Applicant
- Image and Vision Computing, vol. 12, No. 10, Dec. 1994, Miroslaw Bober et al., “Estimation of complex multimodal motion: an approach based on robust statistics and Hough transform,” pp. 661-668.Applicant
- Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Jun. 21-23, 1994, (Seattle, Washington, USA), Miroslaw Bober et al., “Robust Motion Analysis,” pp. 947-952.Applicant
- Signal Processing: Image Communication, vol. 6, No. 6, 1995, Amichay Amitay et al., “Global-motion estimation in image sequences of 3-D scenes for coding applications,” pp. 507-520.Applicant
- Proceedings of the Pacific Rim Conference on Communications, Computers and Signal Processing, May 19-21, 1993, (Victoria, British Columbia, Canada), Hidonby Ida et al., “Extraction of Motion from Spatio-Temporal Image Using the 3-Dimensional Hough Transform,” pp. 174-177.Applicant
- Visual Communication and Image Processing '91: Visual Communication, Nov. 11-13, 1991, (Boston, Massachusetts, USA), Shigeyoshi Nakajima et al., “Three-dimensional motion analysis and structure recovering by multistage Hough transform,” pp. 709-719.Applicant
- Proceedings of the Fifth International Conference on Computer Vision, 1995, Cambridge, Mass., Tina Yu Tian et al., “Recovering 3-D Motion of Multiple Objects Using Adpative Hough Transform,” pp. 284-289.Applicant
- Pattern Recognition Letters, vol. 16, No. 9, Sep. 1995, Jukka Heikkonen, “Recovering 3-D motion parameters from optical flow field using randomized Hough transform,” pp. 971-978.Applicant