Resources Contact Us Home
Browse by: INVENTOR PATENT HOLDER PATENT NUMBER DATE
 
 
System and method for sparse histogram merging
7889923 System and method for sparse histogram merging
Patent Drawings:Drawing: 7889923-10    Drawing: 7889923-11    Drawing: 7889923-12    Drawing: 7889923-13    Drawing: 7889923-14    Drawing: 7889923-15    Drawing: 7889923-16    Drawing: 7889923-17    Drawing: 7889923-18    Drawing: 7889923-3    
« 1 2 »

(16 images)

Inventor: Carr, et al.
Date Issued: February 15, 2011
Application: 11/756,402
Filed: May 31, 2007
Inventors: Carr; Nathan A. (Santa Clara, CA)
Miller; Gavin S. P. (Los Altos, CA)
Assignee: Adobe Systems Incorporated (San Jose, CA)
Primary Examiner: Do; Anh Hong
Assistant Examiner:
Attorney Or Agent: Kowert; Robert C.Meyertons, Hood, Kivlin, Kowert & Goetzel, P.C.
U.S. Class: 382/168; 382/169; 382/172
Field Of Search: 382/168; 382/169; 382/128; 382/305; 382/261; 382/271; 382/172; 382/130; 345/424; 378/28; 702/182; 702/185; 707/999.1
International Class: G06K 9/00
U.S Patent Documents:
Foreign Patent Documents:
Other References: US. Appl. No. 11/749,862, filed May 17, 2007. cited by other.
U.S. Appl. No. 11/756,409, filed May 31, 2007. cited by other.
Weiss, "Fast Median and Bilateral Filtering," ACM Transactions on Graphics, vol. 25 , Issue 3 (Jul. 2006), Proceedings of ACM SIGGRAPH 2006, pp. 519-526. cited by other.
Paris, et al, "A Fast Approximation of the Bilateral Filter Using a Signal Processing Approach," Proceedings of the European Conference on Computer Vision, 2006. cited by other.
Terdiman, "Radix Sort Revisited," 2000, http://www.codercorner.com/RadixSortRevisited.html. cited by other.
Huang, "A Fast Two-Dimensional Median Filtering Algorithm," Acoustics, Speech, and Signal Processing [see also IEEE Transactions on Signal Processing], IEEE Transactions, vol. 27, Issue 1, Feb. 1979, pp. 13-18. cited by other.
Williams, "Pyramidal Parametrics", Computer Graphics, vol. 17, No. 3, July 1983, pp. 1-11. cited by other.
Crow, "Summed-Area Tables for Texture Mapping," Computer Graphics, vol. 18, No. 3, Jul. 1984, pp. 207-212. cited by other.
Giovanni Garibotto, Livio Lambarelli, "Fast on-line Implementation of Two-Dimensional Median Filtering," Electronics Letters, vol. 15, No. 1, Jan. 4, 1979, pp. 24-25. cited by other.
Huttunen, H. & Yli-Harja, O., "Fast Algorithm for Updating the Local Histogram of Multidemensional Signals," Proceedings 1999 International Symposium on Nonlinear Theory and Its Applications (NOLTA '99), Hilton Waikoloa Village, Hawaii, USA, Nov.28-Dec. 2, 1999, pp. 65-68. cited by other.
U.S. Appl. No. 11/292,184, filed Nov. 29, 2005. cited by other.
U.S. Appl. No. 12/323,009, filed Nov. 25, 2008. cited by other.
Fredo Durand and Julie Dorsey, "Fast bilateral filtering for the display of high-dynamic-range images," ACM Transactions on Graphics (TOG), Proceedings of the 29th annual conference on computer graphics and interactive techniques SIGGRAPH '02, vol.21, issue 3. cited by other.
Qimei Hu, et al. "Mutli-scale edge detection with bilateral filtering in apiral architecture," Proceedings of the Pan-Sydney area Workshop on Visual Information Processing VIP '05, publisher: Australian Computer Society, Inc. cited by other.









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.
Claim: What is claimed is:

1. 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 bucketvalues, 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 thehistogram 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 asame 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 acorresponding 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 theone 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.

2. The method of claim 1, wherein each of the bucket values comprises a count of pixels in the region having a same pixel value.

3. The method of claim 1, wherein each of the bucket values comprises a weighting dependent on at least one of: values of pixels in the region and locations of pixels within the region.

4. The method of claim 1, wherein each of the array values comprises a count of non-zero bucket values included in the one or more of the plurality of bucket values associated with the array value.

5. The method of claim 1, wherein said 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 comprises merging all of the oneor more of the plurality of bucket values associated with the non-zero array value with a corresponding bucket value of the second histogram.

6. The method of claim 1, wherein each of the array values comprises a bitmask indicating whether each of the one or more of the plurality of bucket values associated with the array value is non-zero.

7. The method of claim 6, wherein said 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 comprises merging a bucket valueassociated with the non-zero array value with a corresponding bucket value of the second histogram if and only if the bitmask indicates that the bucket value is non-zero.

8. The method of claim 6, further comprising determining which of the one or more of the plurality of bucket values associated with the array value are non-zero by locating a first non-zero bit in the bitmask.

9. The method of claim 1, wherein said 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 comprises adding the at leastone of the associated one or more of the plurality of bucket values associated with the non-zero array value and the corresponding bucket value of the second histogram.

10. The method of claim 1, further comprising: in response to a change in a bucket value in the histogram, determining if an array value associated with the bucket value should be changed; and in response to determining that the bucket valueshould be changed, updating the array value to reflect the change in the bucket value.

11. The method of claim 10, wherein said determining if an array value associated with the bucket value should be changed comprises: determining if the change in the bucket value comprises a change in the bucket value from a value of zero to anon-zero value; and in response to determining that the change in the bucket value comprises a change in the bucket value from a value of zero to a non-zero value, updating the array value to indicate that an additional non-zero bucket value is includedin the one or more of the plurality of bucket values associated with the array value.

12. The method of claim 10, wherein said determining if an array value associated with the bucket value should be changed comprises: determining if the change in the bucket value comprises a change in the bucket value from a non-zero value to avalue of zero; and in response to determining that the change in the bucket value comprises a change in the bucket value from a non-zero value to a value of zero, updating the array value to indicate that one fewer non-zero bucket value is included inthe one or more of the plurality of bucket values associated with the array value.

13. 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 histogramfor 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 ormore 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 atleast 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; foreach 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 asecond image dependent on bucket values in the third histogram.

14. The system of claim 13, wherein each of the bucket values comprises a count of pixels in the region having a same pixel value.

15. The system of claim 13, wherein each of the bucket values comprises a weighting dependent on at least one of: values of pixels in the region and locations of pixels within the region.

16. The system of claim 13, wherein each of the array values comprises a count of non-zero bucket values included in the one or more of the plurality of bucket values associated with the array value.

17. The system of claim 13, wherein said 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 comprises merging all of theone or more of the plurality of bucket values associated with the non-zero array value with a corresponding bucket value of the second histogram.

18. The system of claim 13, wherein each of the array values comprises a bitmask indicating whether each of the one or more of the plurality of bucket values associated with the array value is non-zero.

19. The system of claim 18, wherein said 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 comprises merging a bucketvalue associated with the non-zero array value with a corresponding bucket value of the second histogram if and only if the bitmask indicates that the bucket value is non-zero.

20. The system of claim 18, wherein the program instructions are further executable by the one or more processors to implement determining which of the one or more of the plurality of bucket values associated with the array value are non-zeroby locating a first non-zero bit in the bitmask.

21. The system of claim 13, wherein said 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 comprises adding the at leastone of the associated one or more of the plurality of bucket values associated with the non-zero array value and the corresponding bucket value of the second histogram.

22. The system of claim 13, wherein the program instructions are further executable by the one or more processors to implement: in response to a change in a bucket value in the histogram, determining if an array value associated with the bucketvalue should be changed; and in response to determining that the bucket value should be changed, updating the array value to reflect the change in the bucket value.

23. The system of claim 22, wherein said determining if an array value associated with the bucket value should be changed comprises: determining if the change in the bucket value comprises a change in the bucket value from a value of zero to anon-zero value; in response to determining that the change in the bucket value comprises a change in the bucket value from a value of zero to a non-zero value, updating the array value to indicate that an additional non-zero bucket value is included inthe one or more of the plurality of bucket values associated with the array value; determining if the change in the bucket value comprises a change in the bucket value from a non-zero value to a value of zero; and in response to determining that thechange in the bucket value comprises a change in the bucket value from a non-zero value to a value of zero, updating the array value to indicate that one fewer non-zero bucket value is included in the one or more of the plurality of bucket valuesassociated with the array value.

24. 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 thehistogram 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, andeach 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 ofbucket 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 ofbucket 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 ofthe 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 thirdhistogram.

25. The storage medium of claim 24, wherein each of the bucket values comprises a count of pixels in the region having a same pixel value or a weighting dependent on at least one of: values of pixels in the region and locations of pixels withinthe region.

26. The storage medium of claim 24, wherein each of the array values comprises a count of non-zero bucket values included in the one or more of the plurality of bucket values associated with the array value or a bitmask indicating whether eachof the one or more of the plurality of bucket values associated with the array value is non-zero.

27. The storage medium of claim 24, wherein said 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 comprises merging allof 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.

28. The storage medium of claim 24, wherein said 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 comprises merging abucket value associated with the non-zero array value with a corresponding bucket value of the second histogram if and only if the array value indicates that the bucket value is non-zero.

29. The storage medium of claim 24, wherein said 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 comprises adding theat least one of the associated one or more of the plurality of bucket values associated with the non-zero array value and the corresponding bucket value of the second histogram.

30. The storage medium of claim 24, wherein when executed on one or more computers the program instructions further cause the one or more computers to perform: in response to a change in a bucket value in the histogram, determining if an arrayvalue associated with the bucket value should be changed; and in response to determining that the bucket value should be changed, updating the array value to reflect the change in the bucket value; wherein said determining if an array value associatedwith the bucket value should be changed comprises: determining if the change in the bucket value comprises a change in the bucket value from a value of zero to a non-zero value; in response to determining that the change in the bucket value comprises achange in the bucket value from a value of zero to a non-zero value, updating the array value to indicate that an additional non-zero bucket value is included in the one or more of the plurality of bucket values associated with the array value; determining if the change in the bucket value comprises a change in the bucket value from a non-zero value to a value of zero; and in response to determining that the change in the bucket value comprises a change in the bucket value from a non-zerovalue to a value of zero, updating the array value to indicate that one fewer non-zero bucket value is included in the one or more of the plurality of bucket values associated with the array value.
Description:
 
 
  Recently Added Patents
Plants and seeds of corn variety CV335662
Coordinate measuring device and method for measuring with a coordinate measuring device
Churn prediction and management system
Error recovery storage along a memory string
Critical word forwarding with adaptive prediction
Adaptive block pre-fetching method and system
Method of controlling semiconductor device, signal processing method, semiconductor device, and electronic apparatus
  Randomly Featured Patents
Detection device
Image processor having recording paper cutting control
Medical waste handling system
Electrode structure including a rod comprising refractory metal and having a greater thermal conductivity material
Probes and methods for testing electrical circuits
Tennis elbow support comprising tendon pad
Photogrammetric plotting apparatus
System and method for data source flattening
Chassis of seat for an office chair
Software agent-based architecture for data relocation