US5537491A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Analyzing an image or other data to obtain a stable number of groups
Assignee: Xerox Corp
•
Filing: 1993-11-24
•
Granted: 1996-07-16
•
Expires: 2013-11-24
Abstract
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.
Inventors
- 👤 James V. Mahoney
- 👤 Satyajit Rao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 20:09
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/10; G06V30/14; G06V30/148; G06V30/15
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
231 words
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.
Claim 2
Independent Claim
231 words
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.
Claim 3
Dependent Claim
30 words
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.
Claim 4
Dependent Claim
56 words
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.
Claim 5
Dependent Claim
25 words
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.
Claim 6
Dependent Claim
14 words
The method of claim 4 in which the minimum number of groups is one.
Claim 7
Dependent Claim
14 words
The method of claim 4 in which the minimum number of groups is two.
Claim 8
Dependent Claim
58 words
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.
Claim 9
Dependent Claim
55 words
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.
Claim 10
Dependent Claim
20 words
The method of claim 8 in which the reference criterion requires a value item indicating a value that is ON.
Claim 11
Dependent Claim
20 words
The method of claim 8 in which the reference criterion requires a value item indicating a value that is OFF.
Claim 12
Dependent Claim
124 words
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.
Claim 13
Dependent Claim
51 words
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.
Claim 14
Dependent Claim
51 words
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.
Claim 15
Dependent Claim
52 words
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.
Claim 16
Dependent Claim
58 words
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.
Claim 17
Dependent Claim
27 words
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.
Claim 18
Dependent Claim
16 words
The method of claim 16 in which the grouping data define groups that segment the image.
Claim 19
Dependent Claim
155 words
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.
Claim 20
Dependent Claim
75 words
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.
Claim 21
Dependent Claim
100 words
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.
Claim 22
Dependent Claim
29 words
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.
Claim 23
Dependent Claim
27 words
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.
Claim 24
Dependent Claim
25 words
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.
Claim 25
Dependent Claim
174 words
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.
Claim 26
Dependent Claim
119 words
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.
Claim 27
Dependent Claim
176 words
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.
Claim 28
Dependent Claim
164 words
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.
Claim 29
Dependent Claim
82 words
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.
Claim 30
Dependent Claim
83 words
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.
Claim 31
Dependent Claim
93 words
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.
Claim 32
Dependent Claim
179 words
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.
Claim 33
Dependent Claim
179 words
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.
Claim 34
Dependent Claim
80 words
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.
Claim 35
Dependent Claim
17 words
The machine of claim 32 in which the input image circuitry is connected for receiving facsimile transmissions.
Claim 36
Dependent Claim
64 words
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.
Claim 37
Dependent Claim
13 words
The machine of claim 31 in which the machine is a fax server.
Claim 38
Dependent Claim
12 words
The machine of claim 31 in which the machine is a copier.
Claim 39
Dependent Claim
258 words
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.
Claim 40
Dependent Claim
258 words
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.
Claim 41
Independent Claim
517 words
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.
Claim 42
Independent Claim
517 words
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.
Claim 43
Independent Claim
313 words
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.
Claim 44
Independent Claim
313 words
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.
References Cited (Backward Citations)
US5268773A
Cited
US5239596A
Cited
US5263120A
Cited
US5280367A
Cited
US5261010A
Cited
US5268774A
Cited
US5282061A
Cited
US5321767A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |