Hierarchical scheme for blur detection in a digital image

• US 7,519,231 B2
• Filed: 06/28/2007
• Issued: 04/14/2009
• Est. Priority Date: 04/09/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Mingjing, Zhang, Hong-Jiang, Wu, Hao
• Primary Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US11/770,433
• Publication Number:
  US 20080013861A1
• Time in Patent Office: 656 Days
• Field of Search: 382/255, 382/260, 382/286, 382/312, 382/261, 382/264, 382/274, 382/275, 382/279, 382/280, 382/282, 178/6.8, 324/77, 348/241, 375/240.18, 375/254
• US Class Current: 382/264
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20064 Wavelet transform [DWT]
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

Methods and apparatuses are provided for detecting blur within digital images using Cepstrum analysis blur detection techniques that are able to detect motion blur and/or out-of-focus blur.

Claims

1. A computer-implemented method comprising:

accessing, by an image processing device, at least a portion of a digital image; and

determining if at least said portion is blurred based on a Cepstrum analysis blur detection process that includes using a point spread function (PSF) that includes a circular averaging filter to blur at least a part of said image, wherein said PSF is used to blur a plurality of parts I_ij to produce corresponding blurred images BI_ij, where

BI_ij=real(FFT<sup>−

1</sup>(FFT(I_ij)*FFT(PSF)))

where FFT stands for Fast Fourier Transform and wherein the Cepstrum analysis includes the steps of;

dividing the image into portions;

calculating the Cepstrum of each portion;

binarizing each result;

calculating an elongation of each binary Cepstrum image; and

determining blur existence or type.

2. The method as recited in claim 1, further comprising determining an output image J_ij that includes a weighted sum of said I_ij and corresponding BI_ij.

3. The method as recited in claim 2, further comprising generating a weighting array wherein said J_ij is at least substantially equal to said I_ij in its central region and at least substantially equal to said corresponding BI_ij near at least one edge.

4. The method as recited in claim 3, wherein:

J_ij(x,y)=a(x,y)*I_ij+(1−

a(x,y))*BI_ij(x,y); and

further comprising calculating a Cepstral transform to each J_ij;

CI_ij=real(FFT<sup>−

1</sup>(log(|FFT(J_ij)|))).

5. The method as recited in claim 4, further comprising binarizing each CI_ij.

6. The method as recited in claim 5, wherein binarizing each CI_ij includes setting BCI(x,y)=1 if CI(x,y)/max(CI)>

t3, else otherwise setting BCI(x,y)=0, wherein t3 is a third threshold value.

7. The method as recited in claim 5, further comprising calculating an elongation of each resulting binarized Cepstrum image.

8. The method as recited in claim 7, wherein said elongation includes a ratio of a maximum length of a chord to a minimum length chord.

9. The method as recited in claim 7, wherein moments are used to calculate said elongation.

10. The method as recited in claim 9, further comprising determining that said image includes motion blur if more than about one third of said regions have an elongation larger than a threshold value L and the maximum difference between a corresponding principal axes is less than a threshold Δ

θ

.

11. The method as recited in claim 9, further comprising determining that said image includes out-of-focus blur if more than about one third of said regions have applicable areas that are larger than a threshold area value A and corresponding elongations that are less than a threshold value T.

12. The method as recited in claim 9, wherein an ^ijth discrete central moment μ

_ij of a region is defined by

${\mathrm{\mu <br><br>}}_{\mathrm{ij}}=\underset{\mathrm{BCI}<br><br>\left(x,y\right)=1}{\overset{}{\sum <br><br>}}<br><br>{\left(x-\stackrel{\_}{x}\right)}^i<br><br>{\left(y-\stackrel{\_}{y}\right)}^j,$

where ( x, y) is the centre of the region, and

$\stackrel{\_}{x}=\frac{1}{n}<br><br>\underset{\mathrm{BCI}<br><br>\left(x,y\right)=1}{\overset{}{\sum <br><br>}}<br><br><br><br>x<br><br><br><br>\mathrm{and}<br><br><br><br>\stackrel{\_}{y}=\frac{1}{n}<br><br>\underset{\mathrm{BCI}<br><br>\left(x,y\right)=1}{\overset{}{\sum <br><br>}}<br><br><br><br>y,$

wherein n is a total number of points contained in said region equal to an area of said region.

13. The method as recited in claim 12, wherein said elongation using moments includes an:

$\mathrm{eccentricity}=\frac{{\mathrm{\mu <br><br>}}_{20}+{\mathrm{\mu <br><br>}}_{02}+\sqrt{{\left({\mathrm{\mu <br><br>}}_{20}-{\mathrm{\mu <br><br>}}_{02}\right)}^2+4<br><br>{\mathrm{\mu <br><br>}}_{11}^2}}{{\mathrm{\mu <br><br>}}_{20}+{\mathrm{\mu <br><br>}}_{02}-\sqrt{{\left({\mathrm{\mu <br><br>}}_{20}-{\mathrm{\mu <br><br>}}_{02}\right)}^2+4<br><br>{\mathrm{\mu <br><br>}}_{11}^2}}.$

14. The method as recited in claim 12, wherein a principal axes of inertia is used to define a natural coordinate system for said region, such that

$\theta$

= 1 2 ⁢

tan - 1 ⁡

[ 2 ⁢

μ

11 μ

20 - μ

02 ] .

15. A computer-readable medium encoded with instructions that, when executed by a computing system, cause a processing unit to perform acts comprising:

determining if at least a portion of a digital image is motion blurred or out-of-focus blurred based on a Cepstrum analysis blur detection process that includes using a point spread function (PSF) to blur at least a part of said image to blur at least one boundary within said image, wherein said PSF includes a circular averaging filter, and said PSF used to blur a plurality of parts I_ij to produce corresponding blurred images BI_ij, where

BI_ij=real(FFT<sup>−

1</sup>(FFT(I_ij)*FFT(PSF)))

where FFT stands for Fast Fourier Transform and wherein the Cepstrum analysis includes the steps of;

dividing the image into portions;

calculating the Cepstrum of each portion;

binarizing each result;

calculating an elongation of each binary Cepstrum image; and

determining blur existence or type.

16. An apparatus comprising:

logic operatively configured to access digital image data and determine if at least a portion of said image is blurry using a Cepstrum analysis blur detector that uses a point spread function (PSF) to selectively blur at least one boundary within said image, wherein said PSF includes a circular averaging filter and, said PSF blurs a plurality of parts I_ij to produce corresponding blurred images BI_ij, where

BI_ij=real(FFT<sup>−

1</sup>(FFT(I_ij)*FFT(PSF)))

where FFT stands for Fast Fourier Transform and wherein the Cepstrum analysis includes the steps of;

dividing the image into portions;

calculating the Cepstrum of each portion;

binarizing each result;

calculating an elongation of each binary Cepstrum image; and

determining blur existence or type.

17. The apparatus as recited in claim 16, wherein said Cepstrum analysis blur detector determines an output image J_ij that includes a weighted sum of said I_ij and corresponding BI_ij.

18. The apparatus as recited in claim 16, wherein said apparatus includes at least one device selected from a group of devices comprising a computer, a camera, a set top box, an optical disc player, an optical disc player recorder, a portable communication device, a display device, a television set, and a projector.