System and method for candidate generation and new features designed for the detection of flat growths

1. A method of generating candidates from a digital image by

a computer system, comprising:

acquiring by a computer system at least one digital image;

analyzing, by the computer system, at least one point x that may lie on a polypoid structure, and determining, by the computer system, whether the point x satisfies a first predetermined set of conditions;

for each point x that satisfies the predetermined set of conditions, identifying, by the computer system, each neighbor point y within a predetermined distance of point x that satisfies a second predetermined set of conditions;

determining, by the computer system, a gradient vector v 1 for point x and identifying, by the computer system, a first half-line to which the gradient vector v 1 belongs;

determining, by the computer system, a gradient vector v 2 for point y and identifying, by the computer system, a second half-line to which the gradient vector v 2 belongs;

calculating, by the computer system, an intersection score that represents how close the first and second half-lines come to intersecting; and

identifying and outputting, by the computer system, point x as a candidate when a candidate score is greater than a predetermined value, wherein the candidate score is the sum of intersection scores for all neighbor points y.

2. The method of claim 1 , wherein determining whether a point x satisfies the first predetermined set of conditions comprises:

determining, by the computer system, that the point x is located on the air-tissue interface; and

determining, by the computer system, that the point x has a gradient magnitude greater than a predetermined gradient value.

3. The method of claim 2 , wherein determining, by the computer system, that the point x is located on the air-tissue interface further comprises determining, by the computer system, that an image intensity at the point x is greater than a first intensity threshold and less than a second intensity threshold.

4. The method of claim 1 , wherein determining whether a point y satisfies the second predetermined conditions, comprises:

determining, by the computer system, that the point y is located on the air-tissue interface;

determining, by the computer system, that the point y has a gradient magnitude greater than a predetermined gradient value;

determining, by the computer system, that the point y is located within a predetermined distance range of the point x;

determining, by the computer system, that the point y is located below the point x; and

determining, by the computer system, that an angle between gradient vector v 1 and gradient vector v 2 is within a predetermined angle range.

5. The method of claim 4 , wherein determining that the point y is located on the air-tissue interface further comprises determining that an image intensity at the point y is greater than a first intensity threshold and less than a second intensity threshold.

6. The method of claim 4 , wherein determining, by the computer system, that the point y is located below the point x further comprises determining that v 1 ·(y−x)>0.

7. The method of claim 1 , further comprising:

determining, by the computer system, that a point x identified as a candidate is within a predetermined distance of at least one neighbor point x also identified as a candidate; and

merging, by the computer system, together those points x each identified as a candidate into a single merged candidate.

8. The method of claim 7 , wherein merging, by the computer system, together those points x each identified as a candidate comprises, for each point x identified as a candidate:

initializing, by the computer system, a merged score as the candidate score of a current selected candidate point x; and

for each neighbor point x identified as a candidate, resetting, by the computer system, the merged score to the candidate score for the neighbor candidate point x if the candidate score for the neighbor candidate point x is greater than the merged score.

9. The method of claim 7 , further comprising, for each selected candidate point x, counting, by the computer system, a number N of neighboring candidate points x that are within a maximum merge distance of the selected point x and retaining those selected candidate points x for whom the number N is greater than a predetermined minimum merge count.

10. The method of claim 1 , wherein the intersection score is defined by

-

v

1

×

(

y

-

x

)



v

1

×

(

y

-

x

)



·

v

1

×

v

2



v

1

×

v

2



,

wherein v 1 is the gradient vector at point x and v 2 is the gradient vector at point y.

11. The method of claim 1 , wherein analyzing, by the computer system, at least one point x further comprises analyzing, by the computer system, all points in the digital image that may lie on a polypoid structure, and determining, by the computer system, whether each point satisfies a first predetermined set of conditions.

12. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for generating candidates from a digital image, the method comprising the steps, implemented by the computer, of:

acquiring at least one digital image;

analyzing at least one point x that may lie on a polypoid structure, and determining whether the point x satisfies a first predetermined set of conditions;

for each point x that satisfies the predetermined set of conditions, identifying each neighbor point y within a predetermined distance of point x that satisfies a second predetermined set of conditions;

determining a gradient vector v 1 for point x and identifying a first half-line to which the gradient vector v 1 belongs;

determining a gradient vector v 2 for point y and identifying a second half-line to which the gradient vector v 2 belongs;

calculating an intersection score that represents how close the first and second half-lines come to intersecting; and

identifying, and outputting, point x as a candidate when a candidate score is greater than a predetermined value, wherein the candidate score is the sum of intersection scores for all neighbor points y.

13. The computer readable program storage device of claim 12 , wherein determining whether a point x satisfies the first predetermined set of conditions comprising:

determining that the point x is located on the air-tissue interface; and

determining that the point x has a gradient magnitude greater than a predetermined gradient value.

14. The computer readable program storage device of claim 13 , wherein determining that the point x is located on the air-tissue interface further comprises determining that an image intensity at the point x is greater than a first intensity threshold and less than a second intensity threshold.

15. The computer readable program storage device of claim 12 , wherein determining whether a point y satisfies the second predetermined conditions comprises:

determining that the point y is located on the air-tissue interface;

determining that the point y has a gradient magnitude greater than a predetermined gradient value;

determining that the point y is located within a predetermined distance range of the point x;

determining that the point y is located below the point x; and

determining that an angle between gradient vector v 1 and gradient vector V 2 is within a predetermined angle range.

16. The computer readable program storage device of claim 15 , wherein determining that the point y is located on the air-tissue interface further comprises determining that an image intensity at the point y is greater than a first intensity threshold and less than a second intensity threshold.

17. The computer readable program storage device of claim 15 , wherein determining that the point y is located below the point x further comprises determining that v 1 ·(y−x)>0.

18. The computer readable program storage device of claim 12 , the method further comprising:

determining that a point x identified as a candidate is within a predetermined distance of at least one neighbor point x also identified as a candidate; and

merging together those points x each identified as a candidate into a single merged candidate.

19. The computer readable program storage device of claim 18 , wherein merging together those points x each identified as a candidate comprises, for each point x identified as a candidate:

initializing a merged score as the candidate score of a current selected candidate point x;

for each neighbor point x identified as a candidate, resetting the merged score to the candidate score for the neighbor candidate point x if the candidate score for the neighbor candidate point x is greater than the merged score.

20. The computer readable program storage device of claim 18 , the method further comprising, for each selected candidate point x, counting a number N of neighboring candidate points x that are within a maximum merge distance of the selected point x and retaining those selected candidate points x for whom the number N is greater than a predetermined minimum merge count.

21. The computer readable program storage device of claim 12 , wherein the intersection score is defined by

-

v

1

×

(

y

-

x

)



v

1

×

(

y

-

x

)



·

v

1

×

v

2



v

1

×

v

2



,

wherein v 1 is the gradient vector at point x and v 2 is the gradient vector at point y.

22. The computer readable program storage device of claim 12 , wherein acquiring at least one point x further comprises considering all points in the digital image that may lie on a polypoid structure, and determining whether each point satisfies a first predetermined set of conditions.