Image analysis based on location sampling

• US 5,416,851 A
• Filed: 07/30/1991
• Issued: 05/16/1995
• Est. Priority Date: 07/30/1991
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Huttenlocher, Daniel P., Wayner, Peter C.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/737,956
• Time in Patent Office: 1,386 Days
• Field of Search: 382/18, 382/20, 382/9, 382/21, 382/22, 382/39, 382/68
• US Class Current: 382/196
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/184 by analysing segments intersecting the pattern

Abstract

An image is analyzed by random or pseudorandom sampling. Information about attributes such as skew, typeface, and character size and spacing is obtained by measuring a characteristic at a number of sampled locations and combining the results to obtain a measure of the characteristic for the image. The number of sampled locations is smaller than the number of locations in the image, but is large enough to achieve a degree of statistical significance. The sampled locations can be selected by obtaining a random or pseudorandom number indicating a candidate location and then applying a criterion to determine whether the candidate location is an appropriate starting point for the measurement. For example, the criterion can be that the location must be a pixel within a character or must be a pixel of a given color at an edge. The measurement can indicate a distance from each sampled location in each of a number of directions, such as the distance to an edge. The distances can be combined to obtain data indicating a distribution, such as by averaging. An image can be divided into segments, each of which has a prominent value for a characteristic being measured, by first dividing the image into starting segments, then sampling the starting segments to measure the characteristic, and then grouping the starting segments into larger segments based on the measurements. The starting segments can be rectangles or, for an image with words, can be segments that each include a word or a paragraph.

Claims

1. An image processing method;

the method operating on image data, the image data defining an image that includes a first number of locations, the image having an image characteristic relative to each of the locations;

the method measuring the image characteristic for the image to a degree of statistical significance;

the method comprising steps of;

for each of a second number of locations in the image, operating on the image data to obtain respective sample result data, each location'"'"'s sample result data measuring the image characteristic relative to the location;

each location'"'"'s sample result data indicating a measurement in a direction extending from the location;

the direction being the same for each location;

each of the second number of locations being selected by;

randomly obtaining location data indicating one of the locations in the first number of locations;

the location data being randomly obtained in a way that can obtain data indicating any of the first number of locations and that would, over a sufficiently large group of locations, indicate locations evenly distributed among the first number of locations; and

applying a criterion to the image data to determine whether to select the location indicated by the location data as one of the second number of locations; and

combining the respective sample result data of the second number of locations to obtain image result data for the direction;

the second number being smaller than the first number but sufficient that the image result data measure the image characteristic for the image to the degree of statistical significance.

5. The method of claim 1 in which each location is a pixel.

6. The method of claim 1 in which the substep of randomly obtaining location data includes a substep of randomly or pseudorandomly producing the location data.

7. The method of claim 1 in which the image data include, for each location in the image, a respective data item;

the substep of applying a criterion to the image data includes a substep of accessing the location'"'"'s data item.

8. The method of claim 7 in which each location'"'"'s data item indicates whether the location has a first color or a second color, the substep of applying the criterion further comprising a substep of determining whether the location'"'"'s data item indicates that the location has the first color.

9. The method of claim 8 in which each of the second number of locations has two or more neighboring locations in the image, the substep of applying the criterion further comprising substeps of:

accessing the respective data items of the location'"'"'s neighboring locations; and

determining whether the respective data item of any of the neighboring locations indicates that the neighboring location has the second color so that the location is at an edge between the first color and the second color.

2. An image processing method;

the method operating on image data, the image data defining an image that includes a first number of locations, the image having an image characteristic relative to each of the locations;

the method measuring the image characteristic for the image to a degree of statistical significance;

the method comprising steps of;

for each of a second number of locations in the image, each of which is randomly selected, operating on the image data to obtain respective sample result data, each location'"'"'s sample result data measuring the image characteristic relative to the location;

each location'"'"'s sample result data including, for each of a set of two or more directions extending from the location, a respective data item; and

combining the respective sample result data of the second number of locations to obtain image result data;

the second number being smaller than the first number but sufficient that the image result data measure the image characteristic for the image to the degree of statistical significance;

the step of combining the respective sample result data comprising a substep of combining, for each of the set of two or more directions, the respective data items to obtain a respective direction data item.

3. The method of claim 2 in which each of the respective data items in each location'"'"'s sample result data indicates a distance, each direction data item being an average of distances indicated by the direction'"'"'s respective data items.

4. An image processing method;

the method operating on image data, the image data defining an image that includes a first number of locations, the image having an image characteristic relative to each of the locations;

the method measuring the image characteristic for the image to a degree of statistical significance;

the method comprising steps of;

for each of a second number of locations in the image, operating on the image data to obtain respective sample result data, each location'"'"'s sample result data measuring the image characteristic relative to the location;

each location'"'"'s sample result data indicating a measurement in a direction extending from the location;

the direction being the same for each location;

the locations in the second number of locations being selected by;

for each location in the first number of locations, using the image data to obtain criterion data indicating whether the location meets a criterion; and

using the criterion data to randomly obtain location data indicating locations in the second number of locations;

the location data being randomly obtained in a way that can obtain data indicating any of the locations that are indicated to meet the criterion and that would, over a sufficiently large group of locations, indicate locations evenly distributed among locations that are indicated to meet the criterion; and

combining the respective sample result data of the second number of locations to obtain image result data for the direction;

the second number being smaller than the first number but sufficient that the image result data measure the image characteristic for the image to the degree of statistical significance.

10. The method of claim 4 in which the image data include, for each location in the image, a respective data item;

the method further comprising a step of operating a processor having a plurality of processing units, each with respective local memory, to store each location'"'"'s data item in a respective processing unit'"'"'s local memory;

the substep of using the image data to obtain criterion data being performed by operating the respective processing units of all the locations in parallel so that each of the processing units operates on the data item stored in the respective local memory to produce criterion data indicating whether it is the respective processing unit of a location that meets the criterion;

the substep of using the criterion data to randomly obtain location data comprising a substep of;

operating the processor to produce processing unit data indicating, for the second number of locations, the respective processing units;

each of the second number of locations being a location whose respective processing unit produced criterion data indicating that the location meets the criterion.

11. The method of claim 4 in which the substep of using the criterion data to randomly obtain location data includes a substep of randomly or pseudorandomly producing candidate location data indicating candidate locations.

12. An image processing method;

the method operating on image data, the image data defining an image that includes a number of locations, the image having an image characteristic relative to each of the locations;

the method comprising;

two or more steps of obtaining sample result data, each step of obtaining sample result data comprising substeps of;

randomly or pseudorandomly producing respective location data indicating a respective location in the image;

the location data being randomly or pseudorandomly obtained in a way that can obtain data indicating any of the locations in the image and that would, over a sufficiently large group of locations, indicate locations evenly distributed among the locations in the image; and

operating on the image data to obtain respective sample result data measuring the image characteristic relative to the respective location indicated by the respective location data;

the sample result data indicating a measurement in a direction extending from the location;

the direction being the same for each step of obtaining sample result data; and

a step of combining the respective sample result data of the respective locations to obtain combined result data for the direction.

15. The method of claim 12 in which each location is a pixel.

16. The method of claim 12 in which each step of obtaining sample result data further comprises a substep of applying a criterion to the image data to determine whether to obtain respective sample result data for the respective location indicated by the respective location data.

17. The method of claim 16 in which the image data include, for each location in the image, a respective data item;

the substep of applying the criterion including a substep of accessing the respective location'"'"'s data item.

18. The method of claim 17 in which each location'"'"'s data item indicates whether the location has a first color or a second color, the substep of applying the criterion further comprising a substep of determining whether the respective location'"'"'s data item indicates that the respective location has the first color.

19. The method of claim 18 in which each step'"'"'s respective location has two or more neighboring locations in the image, the substep of applying the criterion further comprising substeps of:

accessing the respective data items of the respective location'"'"'s neighboring locations; and

determining whether the respective data item of any of the neighboring locations indicates that the neighboring location has the second color so that the respective location is at an edge between the first color and the second color.

13. An image processing method;

the method operating on image data, the image data defining an image that includes a number of locations, the image having an image characteristic relative to each of the locations;

the method comprising;

two or more steps of obtaining sample result data, each step of obtaining sample result data comprising substeps of;

randomly or pseudorandomly producing respective location data indicating a respective location in the image; and

operating on the image data to obtain respective sample result data measuring the image characteristic relative to the respective location indicated by the respective location data;

each step'"'"'s sample result data including, for each of a set of two or more directions extending from the respective location, a respective data item; and

a step of combining the respective sample result data of the respective locations to obtain combined result data;

the step of combining the respective sample result data comprising a substep of combining, for each of the set of two or more directions, the respective data items to obtain a respective direction data item.

14. The method of claim 13 in which each of the respective data items in each location'"'"'s sample result data indicates a distance, each direction data item indicating a distribution of distances indicated by the direction'"'"'s respective data items.

20. An image processing method;

the method operating on image data, the image data defining an image that includes a number of locations, the image having an image characteristic relative to each of the locations;

the method comprising;

a step of operating on the image data to produce, for each of a set of two or more initial segments of the image, respective initial segment data defining the initial segment;

for each initial segment, two or more steps of obtaining sample result data, each step of obtaining sample result data comprising substeps of;

randomly or pseudorandomly producing respective location data indicating a respective location in the initial segment; and

operating on the initial segment'"'"'s initial segment data to obtain respective sample result data measuring the image characteristic relative to the respective location indicated by the respective location data;

the respective sample result data indicating a measurement in a direction extending from the respective location;

the direction being the same for each step of obtaining sample result data; and

for each initial segment, a step of combining the respective sample result data of locations in the initial segment to obtain combined result data for the direction; and

a step of using the combined result data of the initial segments to produce, for a group of the initial segments, grouped segment data defining a larger segment that includes the initial segments in the group.

21. The method of claim 20 in which the image data includes a respective data item for each of the locations in the image;

each initial segment'"'"'s initial segment data including a respective data item for each location in the initial segment.

22. The method of claim 20 in which each initial segment is a rectangle.

23. The method of claim 20 in which the image includes lines of text, each line of text including words, each initial segment including one of the words.

24. The method of claim 20 in which each of the initial segments includes a respective number of locations;

the steps of obtaining sample data including a respective number of steps for each initial segment;

each initial segment'"'"'s number of steps being smaller than the respective number of locations but sufficient that the initial segment'"'"'s combined result data measure the image characteristic for the initial segment to a degree of statistical significance.

25. The method of claim 20 in which each location is a pixel.