Rapid shake detection using a cascade of quad-tree motion detectors

1. A method of detecting shake of a camera, comprising:

capturing an image with the camera;

determining a magnitude of a motion from at least the image;

where the determined magnitude of motion is not larger than a first threshold, determining the camera to be stable;

where the determined magnitude of motion is larger than the first threshold, determining if a magnitude of motion for each of a number of blocks of the image is larger than at least one further threshold; and

determining the shake of camera based on a number of blocks having a magnitude of motion exceeding the at least one further threshold,

wherein the at least one further threshold comprises a second threshold associated with a first block, and a third threshold associated with a second block whose size is not larger than the first block, and

wherein the at least one further threshold comprises the second threshold associated with a quadtree level 2 number of blocks, and the third threshold associated with a quadtree level 3 number of blocks.

2. A method according to claim 1 , wherein the first threshold is smaller than the at least one further threshold.

3. A method according to claim 1 , wherein the motion between corresponding blocks in the image is computed from correlation of image projection profiles.

4. A method according to claim 3 , wherein the image projection profiles comprise a sum of image intensities along a projection direction of the image projection profiles.

5. A method according to claim 3 , wherein the image projection profiles comprise a sum of image gradient magnitudes along a projection direction of the image projection profiles.

6. A method according to claim 3 , wherein the image projection profiles are complex with a real component and an imaginary component being one of (i) a sum of image intensities along a projection direction of the image projection profiles, and (ii) a sum of image gradient magnitudes along the projection direction.

7. A method according to claim 3 , wherein the image projection profiles are pre-computed for quadtree blocks at a finest level, from which image projection profiles for quadtree blocks at coarser levels are derived.

8. A method of determining stability of a camera, comprising:

capturing an image with the camera;

(A) determining a magnitude of motion for each of a number of blocks of a current sub-division of the image;

(B) determining a number of blocks having magnitudes of motion not larger than a magnitude threshold associated with the current sub-division, and where the determined number is greater than or equal to a region threshold associated with the number of blocks in the current sub-division, (i) determining the camera to be stable, or otherwise (ii) dividing the current sub-division of the image into a further sub-division, and repeating steps (A) and (B) upon the further sub-division,

wherein the sub-division is a global cascading quad-tree sub-division, and

wherein after three traversals of step (B) the camera is not determined to be stable, the camera is deemed to be unstable.

9. A method according to claim 8 wherein step (A) is performed at least twice.

10. Apparatus for detecting shake of a camera, the apparatus comprising:

an input for an image captured with the camera;

a processor coupled to the input and configured to:

determine a magnitude of a motion from at least the image, and where the determined magnitude of motion is not larger than a first threshold, determining the camera to be stable; and

where the determined magnitude of motion is larger than the first threshold, determining if a magnitude of motion for each of a number of blocks of the image is larger than at least one further threshold, and determining the shake of camera based on the number of blocks having a magnitude of motion exceeding the at least one further threshold,

wherein the at least one further threshold comprises a second threshold associated with a first block, and a third threshold associated with a second block whose size is not larger than the first block, and

wherein the at least one further threshold comprises the second threshold associated with a quadtree level 2 number of blocks, and the third threshold associated with a quadtree level 3 number of blocks.

11. Apparatus according to claim 10 wherein the apparatus is one of (i) formed within the camera, (ii) a computing device to which the camera can be coupled, and (iii) a server computer to which the camera couples via a network, and the input includes a memory into which the image captured from the camera is stored.