US 7,889,923 B1Granted

System and method for sparse histogram merging

AssigneeAdobe Systems Incorporated

InventorsNathan A. Carr, Gavin S. P. Miller

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for merging histograms may include generating a histogram for a region of an image, the histogram including bucket values representing a count of pixels having the same pixel value or a weighting dependent on the pixels. The method may include maintaining an array of values indicating non-zero histogram entries for a group of bucket values (e.g., a count of non-zero bucket values in the group or a bitmask indicating if each bucket value is non-zero). A sparse histogram for which such an array exists may be merged with a second histogram. Merging the histograms may include not merging any bucket values in the group if the associated array value is zero, and merging some or all of the bucket values if it is non-zero. The methods disclosed may be implemented by program instructions executing in parallel on CPU(s) or GPUs.

Claims30

Dependent claims

A method, comprising:

performing by one or more computers:
generating a histogram for a region of an input image, wherein the histogram comprises a plurality of bucket values, each dependent on values of pixels in the region;
generating an array comprising a plurality of array values, each associated with one or more of the plurality of bucket values, and each dependent on the plurality of bucket values;
merging the histogram with a second histogram to produce a third histogram, wherein the second histogram comprises a second plurality of bucket values, each bucket value in the second plurality of bucket values dependent on values of pixels in a second region in a same way as corresponding bucket values in the histogram, wherein said merging comprises:
for each non-zero array value, merging at least one of the one or more of the plurality of bucket values associated with the non-zero array value with a corresponding bucket value of the second histogram to generate a third bucket value for a corresponding bucket of the third histogram;
for each array value of zero, including bucket values of the second plurality of bucket values corresponding to the one or more of the plurality of bucket values associated with the array value of zero in buckets of the third histogram;
and
rendering a second image dependent on bucket values in the third histogram.

5 more elements

A system, comprising:

one or more processors;
and
a memory coupled to the one or more processors;
wherein the memory is configured to store program instructions executable by the one or more processors to implement:
generating a histogram for a region of an input image, wherein the histogram comprises a plurality of bucket values, each bucket value being dependent on values of pixels in the region;
generating an array comprising a plurality of array values, each associated with one or more of the plurality of bucket values, and each being dependent on the plurality of bucket values;
merging the histogram with a second histogram to produce a third histogram, wherein the second histogram comprises a second plurality of bucket values, each bucket value in the second plurality of bucket values being dependent on values of pixels in a second region in a same way as corresponding bucket values in the histogram, wherein said merging comprises:
for each non-zero array value, merging at least one of the one or more of the plurality of bucket values associated with the non-zero array value with a corresponding bucket value of the second histogram to generate a third bucket value for a corresponding bucket of the third histogram;
for each array value of zero, including bucket values of the second plurality of bucket values corresponding to the one or more of the plurality of bucket values associated with the array value of zero in buckets of the third histogram;
and
rendering a second image dependent on bucket values in the third histogram.

8 more elements

A non-transitory, computer-readable storage medium, storing program instructions that when executed on one or more computers cause the one or more computers to perform:

generating a histogram for a region of an input image, wherein the histogram comprises a plurality of bucket values, each bucket value being dependent on values of pixels in the region;
generating an array comprising a plurality of array values, each associated with one or more of the plurality of bucket values, and each being dependent on the plurality of bucket values;
merging the histogram with a second histogram to produce a third histogram, wherein the second histogram comprises a second plurality of bucket values, each bucket value in the second plurality of bucket values being dependent on values of pixels in a second region in a same way as corresponding bucket values in the histogram, wherein said merging comprises:
for each non-zero array value, merging at least one of the one or more of the plurality of bucket values associated with the non-zero array value with a corresponding bucket value of the second histogram to generate a third bucket value for a corresponding bucket of the third histogram;
for each array value of zero, including bucket values of the second plurality of bucket values corresponding to the one or more of the plurality of bucket values associated with the array value of zero in buckets of the third histogram;
and
rendering a second image dependent on bucket values in the third histogram.

4 more elements

Dependencies are inferred from the claim text.