Gradient based method for providing values for unknown pixels in a digital image

• US 5,875,040 A
• Filed: 12/04/1995
• Issued: 02/23/1999
• Est. Priority Date: 12/04/1995
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Matraszek, Tomasz Andrzej, Cok, David Roy, Gray, Robert Terry
• Primary Examiner(s): Vu, Kim Yen
• Assistant Examiner(s): Williams, Kimberly A.
• Application Number:
  US08/566,544
• Time in Patent Office: 1,177 Days
• Field of Search: 382/203, 382/199, 382/205, 382/254, 382/190, 382/195, 358/453, 358/428, 358/447
• US Class Current: 358/453
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: H04N 23/81 for suppressing or minimising disturbance in the image signal generation
• CPC Class Codes: H04N 5/253 Picture signal generating by scanning motion picture films or slide opaques, e.g. for telecine scanning details therefor H04N3/36 ; standard conversion therefor H04N7/0112

Abstract

A method of correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively. The method comprises:

a) searching for edges in a non-defect region of the image adjacent to the defect region by: (i) comparing relative pixel parameters in the non-defect region with a predetermined tolerance to locate a sequence of pixels representing an edge segment the members of which have relative parameters within the tolerance and which sequence is within a predetermined distance of the defect region; and (ii) comparing the length of an edge segment with a minimum length to identify as an edge a segment with at least the minimum length;

b) generating at least one pixel signal for the defect region based on the signal of at least one non-defect pixel lying in a direction from the defect pixel which is determined by the direction of an edge.

An apparatus for performing the method and a computer usable medium containing computer code for performing the method, are also provided.

Claims

1. A method for correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the method comprising:

a) searching for edges in a non-defect region of the image adjacent to the defect region by;

(i) comparing relative pixel parameters in the non-defect region with a predetermined tolerance to locate in the non-defect region a series of adjacent pixels representing an edge segment the members of which have relative parameters within the tolerance and which series is within a predetermined distance of the defect region; and

(ii) comparing the of the edge segment within a minimum length to identify as an edge a segment with a least the minimum length;

b) generating at least one pixel sign for the defect region based on the signal of at least one non-defect pixel lying in a direction from the defect pixel which is determined by the direction of an edge; and

c) replacing the defect pixel signal with the generated pixel signal.

2. A method according to claim 1 wherein the pixel parameters of the detected edge include parameters which define edge shape.

3. A method according to claim 1 wherein pixel parameters are compared by first generating a gradient field for the non-defect region and wherein the relative pixel parameters compared are relative gradient attributes.

4. A method according to claim 1 wherein the searching for edge segments is repeated in each of a plurality of local non-defect regions which are adjacent to and around the same defect region.

5. A method according to claim 1 wherein, if at least two edges are identified:

(i) the difference in pixel parameters of the ends of the edges adjacent to the defect region are compared with a predetermined tolerance; and

(ii) pixel signals are generated for defect region pixels lying on a line connecting the two ends which meet the foregoing tolerance, which signals are based on at least one pixel signal of the two detected edges.

6. A method according to claim 5 wherein the line connecting the two ends is a straight line.

7. A method according to claim 5 wherein a parameter representative of pixel signals in a region adjacent to at least a first side of one edge is compared with the parameter representative of pixel signals in a region adjacent to a corresponding first side of the other edge, and pixel signals for the defect region are generated between the two ends based on at least one pixel signal of the two detected edges only if the difference in those parameters are within a predetermined tolerance.

8. A method according to claim 7 wherein a parameter representative of pixel signals in a region adjacent to a second side of a detected edge are compared with the parameter representative of pixel signals in a region adjacent to a corresponding second side of another detected edge, and pixel signals for the defect region are generated between the two ends based on at least one pixel signal of the two detected edges only if the difference in the first side parameters and the difference in the second side parameters are both within a predetermined tolerance.

9. A method according to claim 5 wherein a line connecting the two ends is modeled based on the shape of the two edges.

10. A method according to claim 1 additionally comprising:

comparing the distance between a defect region pixel and a detected edge, with a threshold;

for a defect region pixel not within the threshold, generating a pixel signal by;

allocating a plurality of line segments through the defect pixel, wherein each said line segment is composed of the defect pixel and the non-defect pixels about said selected defect pixel;

determining at least one representative model of the non-defect pixel signals along each said line segment;

determining the deviation of the non-defect pixel signals along each said line segment from the model corresponding to the line segment;

selecting the line segment having the lowest deviation which does not intersect a detected edge; and

determining corrected pixel signals for said selected defect pixel based on at least one of the non-defect pixel signals in said selected line segment.

11. A method according to claim 1 additionally comprising scanning an image.

12. A method of claim 1 additionally comprising determining an edge direction prior to step (b).

13. A method of correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the method comprising:

a) searching for edges in a non-defect region of the image adjacent to the defect region by;

(i) generating a gradient field for the non-defect region;

(ii) comparing gradients of the pixels to locate a start pixel in the non-defect region which has a gradient magnitude exceeding a preselected threshold;

(iii) comparing at least relative directional gradient attributes in the non-defect region with a predetermined tolerance to locate in the non-defect region series of adjacent pixels each series representing an edge segment, each series extending in at least one direction from the start pixel, the members of which have at least relative directional gradient attributes within the predetermined tolerance and which series is within a predetermined distance of the defect region;

(iv) comparing the length of the edge segments with a minimum length to identify as edges those edge segments with at least the minimum length;

b) if at least two edges are found, comparing their relative directions and magnitudes with predetermined tolerances;

c) generating pixel signals for the defect region between respective ends of two edges which have relative directions and magnitudes within the predetermined tolerances, which signals are based on at least one pixel signal of the two edges; and

d) replacing defect pixel signals with the generated pixel signals.

14. A method according to claim 13 wherein the non-defect region which is searched for edges is comprised of a plurality of local non-defect regions disposed about the defect region, each local non-defect region being searched in turn for an edge, and wherein the start pixel for each local non-defect region is the pixel with the highest gradient magnitude in that local image area.

15. A method of correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the method comprising:

a) searching a non-defect region of the image adjacent to the defect region to locate in the non-defect region series of adjacent pixels each series representing an edge segment, and comparing the length of each segment with a predetermined minimum length to locate as edges those segments of at least the minimum length;

b) searching for a geometric primitive by comparing at least one geometric parameter of a set of the edges with a geometric constraint corresponding to a geometric primitive, a geometric primitive being detected when the set at least meets the geometric constraint;

c) generating pixel signals for defect region pixels each based on the signal of at least one non-defect pixel lying on a predictor line having a direction which has been-determined by the direction of at least one part of a detected geometric primitive; and

d) replacing defect pixel signals with the generated pixel signals.

16. A method according to claim 15 wherein each series of adjacent pixels representing edge segments is detected by:

(i) generating a gradient field for the non-defect region;

(ii) comparing at least one relative gradient attribute of pixels in the non-defect region with at least one predetermined tolerance to locate a series of adjacent pixels the members of which have at least one relative gradient attribute within the predetermined tolerance.

17. A method according to claim 16 wherein gradient magnitudes of the pixels are first compared to locate a start pixel in the non-defect region which has a gradient magnitude exceeding a preselected threshold, and the series of adjacent pixels is located which extends in at least one direction from the start pixel.

18. A method according to claim 16 wherein the geometric primitive is composed of straight line segment edges.

19. A method according to claim 15 wherein, for at least two edges of the set which meets the geometric constraint, a parameter representative of pixel signals in a region adjacent to at least a first side of one edge of the set is compared with the parameter representative of pixel signals in a region adjacent to a corresponding first side of the other edge of the set, a geometric primitive being detected only if the difference in those parameters is within a predetermined tolerance.

20. A method according to claim 19 wherein a parameter representing pixel signals in a region adjacent to a second side of one edge of the set is compared with the parameter representing pixel signals in a region adjacent to a corresponding second side of the other edge of the set, a geometric primitive being detected only if the difference in the first side parameters and the difference in the second side parameters are both within predetermined tolerances.

21. A method according to claim 20 wherein the parameter representing pixel signals compared in the regions adjacent to the sides are average signals.

22. A method according to claim 19 wherein the parameter representing pixel signals compared in the regions adjacent to the sides are average signals.

23. A method according to claim 15 additionally comprising, for a defect region pixel:

allocating a plurality of line segments through the defect pixel, wherein each said line segment is composed of the defect pixel and non-defect pixels about said selected defect pixel;

if there is at least one line segment with a minimum number of non-defect pixels on either side of the defect pixel then comparing the distance between the defect pixel and the nearest part of a detected primitive, with a threshold distance;

if the distance is beyond the threshold distance, then;

determining at least one representative model of the non-defect pixel signals along each said line segment;

determining the deviation of the non-defect pixel signals along each said line segment from the model corresponding to the line segment;

selecting the line segment having the lowest deviation which does not intersect an part of a detected primitive; and

determining corrected pixel signals for said selected defect pixel based on at least one of the non-defect pixel signals in said selected line segment.

24. A method according to claim 23 wherein, if there is no line segment with the minimum number of non-defect pixels on either side of the defect pixel, or the distance between the defect pixel and the nearest part, in the map, of a detected primitive is within the threshold, then a corrected pixel signal for the defect pixel is determined based on the signal of at least one non-defect pixel lying on a predictor line through the defect pixel having a direction determined by the direction of a neighboring part of at least one detected geometric primitive in the edge map.

25. A method according to claim 15 wherein the geometric parameter is the intersection angle of two edges in the map, and the geometric constraint is a range of intersection angles of two edges.

26. A method according to claim 15 wherein:

the locations of the edges together define an edge map and wherein, prior to generating pixel signals, a detected geometric primitive is extracted by extending or reducing, in the map, one or more edges of the detected primitive so that they intersect in the same pattern as the primitive, or by replacing in the map the edges detected as a primitive with one or more new edges representing the primitive.

27. A method according to claim 26 wherein a signal for a defect pixel is generated based on the signal of at least one non-defect pixel lying on a predictor line extending through the defect pixel and having a direction determined by the direction of a neighboring part of a detected geometric primitive in the edge map.

28. A method according to claim 27 wherein the predictor line is parallel to the neighboring part.

29. A method according to claim 26 additionally comprising:

comparing the distance between a defect region pixel and the nearest part of a detected primitive in the edge map, with a threshold distance;

for a defect region pixel beyond the threshold distance, generating a pixel signal by;

allocating a plurality of line segments through the defect pixel, wherein each said line segment is composed of the defect pixel and the non-defect pixels about said selected defect pixel;

determining at least one representative model of the non-defect pixel signals along each said line segment;

determining the deviation of the non-defect pixel signals along each said line segment from the model corresponding to the line segment;

selecting the line segment having the lowest deviation which does not intersect a part, in the map, of a detected primitive; and

determining corrected pixel signals for said selected defect pixel based on at least one of the non-defect pixel signals in said selected line segment.

30. A method according to claim 26 wherein, prior to searching for a geometric primitive:

(i) for at least one edge intersecting the defect region, the direction of a defect part of that edge is determined based on the direction of the edge;

(ii) searching a non-defect region of the image adjacent to the defect region for a series of adjacent pixels in the non-defect region representing an edge segment extending from a first non-defect pixel intersected by the defect part of the edge, and comparing the length of such a series with a predetermined minimum length to locate as a defect exit part of the edge a series of at least the minimum length; and

(iii) when a defect exit part is located, the at least one edge, its corresponding defect part and defect exit part are added to the edge map as a connected edge, or when a defect exit part is not located the edge and its defect part are added to the edge map as a not connected edge.

31. A method according to claim 30 wherein the series of adjacent pixels representing edge segments are detected by:

(i) generating a gradient field for the non-defect region;

(ii) comparing gradient magnitudes of the pixels to locate a start pixel in the non-defect region which has a gradient magnitude exceeding a preselected threshold;

(iii) comparing at least one relative gradient attribute of pixels in the non-defect region with at least one predetermined tolerance to locate a series of adjacent pixels the members of which have at least one relative gradient attribute within the predetermined tolerance.

32. A method according to claim 15 wherein the digital image signal represents a scanned image.

33. A method of correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the method comprising:

a) searching a non-defect region of the image adjacent to the defect region for sequences of pixels representing edge segments, and comparing the length of each segment with a predetermined minimum length to locate as edges those segments of at least the minimum length the locations of the edges together defining an edge map;

b) searching for a geometric primitive by comparing at least one geometric parameter of a set of edges with a geometric constraint corresponding to a geometric primitive, a geometric primitive being detected when the set at least meets the geometric constraint;

c) generating pixel signals for defect region pixels each based on the signal of at least one non-defect pixel lying on a predictor line having a direction determined by the direction of at least one part of a detected geometric primitive; and

d) replacing defect pixel signals with the generated pixel signals;

wherein, prior to searching for a geometric primitive;

(i) for at least one edge intersecting the defect region, the direction of a defect part of that edge is determined based on the direction of the edge;

(ii) searching a non-defect region of the image adjacent to the defect region for a sequence of adjacent pixels in the non-defect region representing an edge segment extending from a first non-defect pixel intersected by the defect part of the edge, and comparing the length of such a sequence with a predetermined minimum length to locate as a defect exit part of the edge a sequence of at least the minimum length; and

(iii) when a defect exit part is located, the at least one edge, its corresponding defect part and defect exit part are added to the edge map as a connected edge, or when a defect exit part is not located the edge and its defect part are added to the edge map as a not connected edge;

and wherein, prior to searching for a geometric primitive, an edge thinning is performed on the edges in the edge map by;

(i) locating a set of matched edges, where edges match when they are within a predetermined angle tolerance and distance of a selected one of the edges of the set;

(ii) selecting the best edge of the set which is the strongest connected edge, if any, or if none, is the strongest not connected edge of the set, where the strength of the edge is defined by the average gradient magnitude of the pixels of the edge, and deleting the remainder of the edges of the set from the edge map.

34. A method according to claim 33 wherein, following edge thinning, in searching for a geometric primitive all intersecting edges which are not part of any geometric primitive, are removed from the edge map.

35. A method according to claim 34 wherein edge thinning is performed on all edges in the edge map, and next searching for a geometric primitive is performed until all edges have been processed.

36. A method of correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the method comprising:

a) searching a non-defect region of the image adjacent to the defect region for sequences of pixels representing edge segments, and comparing the length of each segment with a predetermined minimum length to locate as edges those segments of at least the minimum length;

b) searching for a geometric primitive by comparing at least one geometric parameter of a set of the edges with a geometric constraint corresponding to a geometric primitive, a geometric primitive being detected when the set at least meets the geometric constraint;

c) generating pixel signals for defect region pixels each based on the signal of at least one non-defect pixel lying on a predictor line having a direction determined by the direction of at least one part of a detected geometric primitive; and

d) replacing defect pixel signals with the generated pixel signals;

wherein the locations of the edges together define an edge map and wherein, prior to generating pixel signals, a detected geometric primitive is extracted by extending or reducing, in the map, one or more edges of the detected primitive so that they intersect in the same pattern as the primitive, or by replacing in the map the edges detected as a primitive with one or more new edges representing the primitive;

and wherein the signal generated for a defect pixel within a predetermined distance of a plurality of neighboring parts of a detected geometric primitive in the edge map is determined by;

first determining estimated pixel signals for the defect pixel based on at least one non-defect pixel lying on each of the predictor lines passing through the defect pixel, and

then determining a final pixel signal which is a weighted sum of estimated pixel signals, each estimated pixel signal being weighted in an inverse relationship to the distance between the predictor line and the corresponding geometric primitive part.

37. An apparatus for correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the apparatus comprising a programmed computer with a memory for storing the source image, the programmed computer having:

a) means for searching for edges in a non-defect region of the image adjacent to the defect region by;

(i) comparing relative pixel parameters in the non-defect region with a predetermined tolerance to locate in the non-defect region a series of adjacent pixels representing an edge segment the members of which have relative parameters within the tolerance and which series is within a predetermined distance of the defect region; and

(ii) comparing the length of an edge segment with a minimum length to identify as an edge a segment with at least the minimum length;

b) means for generating at least one pixel signal for the defect region based on the signal of at least one non-defect pixel lying in a direction from the defect pixel which is determined by the direction of the edge; and

c) means for replacing a defect pixel signal with the generated pixel signal.

38. An apparatus for correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, comprising a programmed computer with a memory for storing the source image, the programmed computer having:

a) means for searching a non-defect region of the image adjacent to the defect region to locate in the non-defect region series of adjacent pixels each series representing an edge segment, and comparing the length of each segment with a predetermined minimum length to locate as edges those segments of at least the minimum length;

b) means for searching for a geometric primitive by comparing at least one geometric parameter of a set of edges with a geometric constraint corresponding to a geometric primitive, a geometric primitive being detected when the set at least meets the geometric constraint;

c) means for generating pixel signals for defect region pixels each based on the signal of at least one non-defect pixel lying on a predictor line having the direction determined by the direction of at least one edge of a detected geometric primitive; and

d) means for replacing defect pixel signals with the generated pixel signals.

39. A computer program product, comprising a computer readable storage medium including program means for correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the program means comprising:

a) means for searching for edges in a non-defect region of the image adjacent to the defect region by;

(i) comparing relative pixel parameters in the non-defect region with a predetermined tolerance to locate in the non-defect region a series of adjacent pixels representing an edge segment the members of which have relative parameters within the tolerance and which series is within a predetermined distance of the defect region; and

(ii) comparing the length of an edge segment with a minimum length to identify as an edge a segment with at least the minimum length;

b) means for generating at least one pixel signal for the defect region based on the signal of at least one non-defect pixel lying in a direction from the defect pixel which is determined by the direction of the edge; and

c) means for replacing the defect pixel signal with the generated pixel signal.

40. A computer program product, comprising a computer readable storage medium with program means for correcting one or more defect pixels in a defect region of a source image, which image has both the defect pixels and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the program means comprising:

a) means for searching a non-defect region of the image adjacent to the defect region to locate in the non-defect region series of adjacent pixels each representing an edge segment, and comparing the length of each segment with a predetermined minimum length to locate as edges those segments of at least the minimum length;

b) means for searching for a geometric primitive by comparing at least one geometric parameter of a set of edges with a geometric constraint corresponding to a geometric primitive, a geometric primitive being detected when the set at least meets the geometric constraint;

c) means for generating pixel signals for defect region pixels each based on the signal of at least one non-defect pixel lying on a predictor line having a direction determined by the direction of at least one edge of a detected geometric primitive; and

d) means for replacing defect pixels signal with the generated pixel signals.

41. A method of correcting at least one defect pixel in a defect region of a source image, which image has both the defect pixel and non-defect pixels each of which is represented by at least one defect pixel signal and non-defect pixel signal, respectively, the method comprising:

allocating a plurality of line segments through a selected defect pixel, wherein each said line segment is composed of the defect pixel and non-defect pixels about said selected defect pixel;

determining at least one representative model of the non-defect pixel signals along each said line segment;

determining the deviation of the non-defect pixel signals along each said line segment from the model corresponding to the line segment;

determining at least one dominant direction of the local gradient field;

selecting at least one line segment based on a figure of merit;

calculating an estimated pixel signal for the defect pixel based on at least one non-defect pixel for each selected line segment;

generating a final pixel signal which is a weighted sum of estimated pixel signals with weights proportional to figures of merit of the selected line segments, wherein the figure of merit is a value which increases with decreased deviation of the non-defect pixels along the selected line segment, and increases with the alignment of the line segment with the dominant directions of the local gradient field and

replacing the defect pixel signal with the generated pixel signal.