Analyzing an image or other data to obtain a stable number of groups

• US 5,537,491 A
• Filed: 11/24/1993
• Issued: 07/16/1996
• Est. Priority Date: 11/24/1993
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mahoney, James V., Rao, Satyajit
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/158,053
• Time in Patent Office: 965 Days
• Field of Search: 382/1, 382/27, 382/34, 382/36, 382/37, 382/55, 382/100, 382/205, 382/218, 382/224, 382/226, 382/258
• US Class Current: 382/218
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques

Abstract

To group items in an array, gap data are obtained indicating gaps between items. The gap data are used to obtain threshold data, which are then used to obtain grouping data. The gaps could, for example, be distances between items in a two-dimensional array or differences between values at which items occur in a one-dimensional array. The threshold data indicate a threshold. The threshold would produce a number of groups of the items that is stable across a range of thresholds, and the range of thresholds meets a criterion for largeness of a range. The criterion can require, for example, that the range be larger than the stable range of thresholds of any other number in a set of numbers of groups. The threshold can be obtained iteratively by applying a candidate threshold for each iteration. The candidate thresholds can be incremented, and the iterations can be counted to find a number of groups meeting the criterion. Or the candidate thresholds can be increased by differences between gaps, and a running sum of threshold ranges can be used to find a number of groups meeting the criterion. The threshold can also be obtained directly by finding the largest difference between gap extents and obtaining a threshold within the largest difference. Many types of grouping can be performed, including spatial clustering, segmentation of partially bounded regions, segmentation by local width, and global and local similarity grouping.

Claims

1. A method of operating a machine that includes:

image input circuitry for obtaining data defining images as input;

memory for storing data; and

a processor connected for receiving data defining images from the image input circuitry and for accessing the memory;

the method comprising;

operating the processor to receive input image data from the image input circuitry, the input image data defining an input image;

operating the processor to use the input image data to obtain initial array data;

the initial array data defining an initial array of value items, each value item indicating a value;

storing the initial array data in the memory;

operating the processor to access the initial array data in the memory and to use the initial array data to obtain gap data indicating one or more gaps between value items in the initial array;

operating the processor to use the gap data to obtain threshold data indicating a threshold;

each gap indicated by the gap data being above or below the threshold;

the threshold data indicating a threshold that would produce a number of groups of the value items;

the number of groups being stable across a range of thresholds;

the range of thresholds meeting a criterion for largeness of a range; and

operating the processor to use the threshold data to obtain grouping data indicating a grouping of the value items in the initial array.

2. The method of claim 1 in which the grouping data indicate groups of value items, each group meeting a transitive closure criterion subject to the threshold in the initial array.

3. The method of claim 1 in which the number of groups of the value items is one of a set of numbers of groups;

the criterion for largeness of a range requiring that the range of thresholds be larger than a range of thresholds across which any other number of groups in the set is stable.

4. The method of claim 3 in which the numbers in the set of numbers of groups are all greater than a minimum number of groups.

5. The method of claim 4 in which the minimum number of groups is one.

6. The method of claim 4 in which the minimum number of groups is two.

7. The method of claim 1 in which the gap data indicate, for each value item in the initial array, a distance;

the threshold data indicating a threshold gap value;

the act of operating the processor to use the threshold data to obtain grouping data comprising;

comparing the threshold gap value with each distance indicated by the gap data.

8. The method of claim 1 in which the initial array includes a set of value items that indicate values that meet a reference criterion;

the gap data indicating, for each value item in the initial array, a distance to another value item that is in the set of value items that meet the reference criterion.

9. The method of claim 8 in which the reference criterion requires a value item indicating a value that is ON.

10. The method of claim 8 in which the reference criterion requires a value item indicating a value that is OFF.

11. The method of claim 1 in which the act of operating the processor to use the threshold data to obtain grouping data comprises:

obtaining thresholded data that indicate a set of the value items in the initial array;

each value item in the set having a distance to another value item that meets a reference criterion;

the distances of all the value items in the set meeting a comparison criterion in relation to the threshold;

the set of value items including two or more subsets of value items, each subset meeting a transitive closure criterion subject to the threshold in the initial array; and

using the thresholded data to obtain the grouping data by obtaining, for each subset of value items, a group identifier.

12. The method of claim 11 in which the thresholded data include a binary value for each value item in the initial array, the comparison criterion requiring a value item'"'"'s distance to be above the threshold;

each value item'"'"'s binary value being ON if the value item'"'"'s distance is above the threshold.

13. The method of claim 11 in which the thresholded data include a binary value for each value item in the initial array, the comparison criterion requiring a value item'"'"'s distance to be below the threshold;

each value item'"'"'s binary value being ON if the value item'"'"'s distance is below the threshold.

14. The method of claim 11 in which the thresholded data include a binary value for each value item in the initial array, each value item'"'"'s binary value indicating whether the value item'"'"'s distance meets the comparison criterion;

the transitive closure criterion requiring a subset of value items to be a connected component.

15. The method of claim 11 in which the initial array data define an image that includes pixels, each value item in the initial array being a pixel value;

the grouping data defining a version of the image indicating, for each value item that is in a group of value items defined by the thresholded data, the group'"'"'s identifier.

16. The method of claim 15 in which the value items in the initial array define connected components;

the grouping data defining groups that cluster the connected components.

17. The method of claim 16 in which the grouping data define groups that segment the image.

18. The method of claim 1 in which values of a parameter define the initial array;

the method further comprising, before the act of storing initial array data;

operating the processor to obtain parameter data indicating a set of values of the parameter; and

operating the processor to use the parameter data to obtain the initial array data;

each value item in the initial array indicating, for one of the values of the parameter, whether its value is in the set of values indicated by the parameter data;

the act of operating the processor to use the initial array data to obtain gap data comprising;

using the initial array data to obtain difference data indicating a difference between adjacent values of the parameter for which value items in the initial array indicate that their values are in the set of values indicated by the parameter data; and

using the difference data to obtain the gap data.

19. The method of claim 18 in which the act of operating the processor to use the threshold data to obtain grouping data comprises:

using the initial array data and the threshold data to obtain, for each value item in the initial array that indicates that its value is in the set of values, a group identifier that identifies a group that includes the value item; and

using the group identifiers to obtain the grouping data.

20. The method of claim 19 in which the parameter data indicate, for each position in a parameter array, a value of the parameter;

the parameter data indicating values that are in the set of values for a set of the positions;

the act of using the group identifiers to obtain the grouping data comprising;

for each position in the set of positions, using the value indicated for the position by the parameter data and the group identifiers to obtain a group identifier for the position;

the grouping data indicating a group identifier for each position in the set of positions.

21. The method of claim 20 in which the parameter data define an image;

the grouping data defining a version of the image indicating, for each position, a group identifier.

22. The method of claim 20 in which the parameter is an attribute of features in images, each value of the parameter indicating a value of the attribute.

23. The method of claim 22 in which the attribute is area, elongation, aspect ratio, width, horizontal center of area, vertical center of area, or orientation.

24. The method of claim 1 in which the gap data indicate a gap for each value item in the initial array;

the act of operating the processor to use the gap data to obtain threshold data comprising;

performing a sequence of iterations, the iterations including a first iteration and a number of following iterations, each following iteration having a preceding iteration, each iteration having threshold candidate data indicating a candidate threshold, the threshold candidate data of each following iteration indicating a candidate threshold that is greater than the preceding iteration'"'"'s candidate threshold;

each iteration comprising;

using the iteration'"'"'s threshold candidate data to obtain thresholded data, the thresholded data indicating, for each value item in the initial array, whether the gap indicated by the gap data for the value item is above or below the iteration'"'"'s candidate threshold;

the thresholded data defining a number of groups of the value items in the initial array; and

using the iteration'"'"'s thresholded data to obtain group count data indicating the number of groups defined by the thresholded data.

25. The method of claim 24 in which the act of operating the processor to use the gap data to obtain threshold data further comprises:

using the iterations'"'"' group count data to obtain subsequence length data indicating a number of iterations in each subsequence of iterations with group count data indicating equal numbers of groups; and

using the subsequence length data to obtain the threshold data;

the threshold data indicating the candidate threshold of an iteration with group count data indicating a first number of groups;

the subsequence length data indicating that a subsequence of iterations with group count data indicating the first number of groups includes a range of thresholds that meets the criterion for largeness of a range.

26. The method of claim 24 in which each following iteration further comprises:

using the preceding iteration'"'"'s threshold data to obtain the following iteration'"'"'s threshold data, the following iteration'"'"'s threshold data indicating a threshold that is greater than the preceding iteration'"'"'s threshold by a gap difference, the gap difference being a difference between gaps indicated by the gap data between which no indicated gaps occur;

the act of operating the processor to use the gap data to obtain threshold data further comprising;

using the iterations'"'"' group count data to obtain threshold range data indicating a range of thresholds in each subsequence of iterations with group count data indicating equal numbers of groups; and

using the threshold range data to obtain the threshold data;

the threshold data indicating the candidate threshold of an iteration with group count data indicating a first number of groups;

the threshold range data indicating that a subsequence of iterations with group count data indicating the first number of groups includes a range of thresholds that meets the criterion for largeness of a range.

27. The method of claim 1 in which the gap data indicate a gap for each value item in the initial array;

the act of operating the processor to use the gap data to obtain threshold data comprising;

using the gap data to obtain largest difference data, the largest difference data indicating, for the gaps indicated by the gap data, a largest difference between gaps between which no indicated gaps occur;

the largest difference occurring between a lower gap and an upper gap; and

using the largest difference data to obtain the threshold data, the threshold data indicating a threshold that is above the lower gap and below the upper gap;

the act of operating the processor to use the threshold data to obtain grouping data comprising;

using the initial array data to obtain distance data indicating a distance for each value item in the initial array; and

using the threshold data and the distance data to compare the threshold to each value item'"'"'s distance.

28. The method of claim 27 in which the gap data indicate, for value items in the initial array that meet a foreground neighbor border criterion, a distance to a near neighbor in the initial array;

the distance data indicating a distance to a near neighbor for each value item in the initial array;

the act of operating the processor to use the threshold data to obtain grouping data further comprising;

grouping value items together that have distances that are below the threshold.

29. The method of claim 27 in which the gap data indicate, for value items in the initial array that meet an opposing foreground neighbor border criterion, a distance to a near neighbor in the initial array;

the distance data indicating a distance to a near neighbor for each value item in the initial array;

the act of operating the processor to use the threshold data to obtain grouping data further comprising;

grouping value items together that have distances that are above the threshold.

30. The method of claim 27 in which the gap data indicate, for value items in the initial array that meet an opposing background neighbor border criterion, a distance to a near neighbor in the complement of the initial array;

the distance data indicating a distance to a near neighbor in the complement of the initial array for each value item in the initial array;

the act of operating the processor to use the threshold data to obtain grouping data further comprising;

grouping value items together that have distances that are above the threshold.

31. A machine comprising:

memory for storing data; and

a processor connected for accessing data stored in the memory;

the data stored in the memory comprising initial array data defining an initial array of value items, each value item indicating a value;

the data stored in the memory further comprising instruction data indicating grouping instructions the processor can execute;

the processor, in executing the grouping instructions;

accessing the initial array data in the memory and using the initial array data to obtain gap data indicating one or more gaps between value items in the initial array;

using the gap data to obtain threshold data indicating a threshold;

each gap indicated by the gap data being above or below the threshold;

the threshold data indicating a threshold that would produce a number of groups of the value items;

the number of groups being stable across a range of thresholds;

the range of thresholds meeting a criterion for largeness of a range; and

using the threshold data to obtain grouping data indicating a grouping of the value items in the initial array.

32. The machine of claim 31 in which the machine further comprises input image circuitry for obtaining data defining images as input;

the instruction data further indicating image processing instructions the processor can execute;

the processor further, in executing the image processing instructions;

receiving input image data from the image input circuitry, the input image data defining an input image; and

using the input image data to obtain the initial array data and providing the initial array data to the memory.

33. The machine of claim 32 in which the input image circuitry is connected for receiving facsimile transmissions.

34. The machine of claim 31 in which the machine is an image processing server;

the image processing server being connected to a network for receiving requests for image processing operations;

the network including the image input circuitry;

the instruction data further indicating request handling instructions the processor can execute;

the processor, in executing the request handling instructions, determining whether to execute the grouping instructions.

35. The machine of claim 31 in which the machine is a fax server.

36. The machine of claim 31 in which the machine is a copier.

37. An article of manufacture for use in a machine that includes:

a storage medium access device for accessing a medium that stores data;

memory for storing data;

the data stored in the memory comprising initial array data defining an initial array of value items, each value item indicating a value; and

a processor connected for receiving data from the storage medium access device and also connected for accessing data in the memory;

the article comprising;

a storage medium that can be accessed by the storage medium access device when the article is used in the machine; and

data stored by the storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine;

the stored data comprising instruction data indicating instructions the processor can execute;

the processor, in executing the instructions;

accessing the initial array data in the memory and using the initial array data to obtain gap data indicating one or more gaps between value items in the initial array;

using the gap data to obtain threshold data indicating a threshold;

each gap indicated by the gap data being above or below the threshold;

the threshold data indicating a threshold that would produce a number of groups of the value items;

the number of groups being stable across a range of thresholds;

the range of thresholds meeting a criterion for largeness of a range; and

using the threshold data to obtain grouping data indicating a grouping of the value items in the initial array.

38. A method of performing image processing by operating a machine;

the machine including;

image input circuitry for obtaining data defining images as input; and

a processor connected for receiving data defining images from the image input circuitry;

the method comprising;

operating the processor to receive input image data from the image input circuitry, the input image data defining an input image;

the input image including pixels and features, each feature including a set of the pixels;

operating the processor to use the input image data to obtain parameter image data;

the parameter image data indicating, for each pixel in the input image, a value for a parameter that is an attribute of features in the input image;

operating the processor to use the parameter image data to obtain threshold data and one-dimensional array data;

the one-dimensional array data defining a one-dimensional array of value items, each value item indicating, for a value of the parameter, whether at least one of the pixels in the input image has the value;

the threshold data indicating a threshold that would produce a number of groups of the value items;

the number of groups being stable across a range of thresholds;

the range of thresholds meeting a criterion for largeness of a range;

the act of using the parameter image data comprising;

using the parameter image data to obtain gap data indicating one or more gaps between values of the parameter that occur in the parameter image data; and

using the gap data to obtain the threshold data;

each gap indicated by the gap data being above or below the threshold indicated by the threshold data;

operating the processor to perform a series of iterations, each iteration handling a value item in the one-dimensional array;

for each iteration after a first iteration in the series, the value item handled by the iteration being advanced by one from the item handled by an immediately preceding iteration;

each iteration;

obtaining a distance count for the value item handled by the iteration;

each value item'"'"'s distance count indicating a distance within the one-dimensional array to a value item indicating that at least one of the pixels in the input image has the item'"'"'s value; and

if the value item handled by the iteration indicates that at least one of the pixels in the input image has the item'"'"'s value, obtaining a group identifier for the value item;

the act of obtaining a group identifier comprising;

if the distance count of the immediately preceding value item is above the threshold, obtaining a new group identifier for the value item; and

if the distance count of the immediately preceding value item is below the threshold, obtaining a group identifier for the value item that is the same as a most recently obtained group identifier; and

operating the processor to use the group identifiers of the value items to obtain grouped parameter image data;

the grouped parameter image data including, for each pixel for which the parameter image data indicates a non-zero value, the group identifier for the value item in the one-dimensional array for the pixel'"'"'s value.

39. A method of performing image processing by operating a machine;

the machine including;

image input circuitry for obtaining data defining images as input; and

a processor connected for receiving data defining images from the image input circuitry;

the method comprising;

operating the processor to receive input image data from the image input circuitry, the input image data defining an input image;

the input image including pixels and features, each feature including a set of the pixels;

operating the processor to use the input image data to obtain parameter image data;

the parameter image data indicating, for each pixel in the input image, a value for a parameter that is an attribute of features in the input image;

operating the processor to use the parameter image data to obtain threshold data and distance image data;

the distance image data indicating, for each pixel in the input image, a distance to a near neighbor;

the threshold data indicating a threshold that would produce a number of groups of the features;

the number of groups being stable across a range of thresholds;

the range of thresholds meeting a criterion for largeness of a range;

the act of using the parameter image data comprising;

using the parameter image data to obtain distance data indicating one or more distances between pixels in the input image; and

using the distance data to obtain the threshold data;

each distance indicated by the distance data being above or below the threshold indicated by the threshold data;

operating the processor to use the threshold data and the distance image data to obtain groups image data indicating, for each pixel, whether it is above or below the threshold;

the act of operating the processor to use the threshold data and the distance image data comprising;

comparing the threshold indicated by the threshold data with each pixel'"'"'s value indicated by the distance image data.