Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2797033002:
ChromeOS color extraction - only look at a maximum of 10k pixels in the (Closed)
|
Created:
3 years, 8 months ago by Evan Stade Modified:
3 years, 8 months ago CC:
chromium-reviews Target Ref:
refs/heads/master Project:
chromium Visibility:
Public. |
DescriptionChromeOS color extraction - only look at a maximum of 10k pixels in the
input image.
The pixels that are chosen are evenly distributed throughout the image.
This proved to be more effective than limiting the color space (i.e. the
number of unique colors).
On at least one large sample wallpaper and my workstation, this reduces
runtime from hundreds of ms to <10ms.
BUG=687852
Review-Url: https://codereview.chromium.org/2797033002
Cr-Commit-Position: refs/heads/master@{#462892}
Committed: https://chromium.googlesource.com/chromium/src/+/b4c4b3509fdf1bc0f8a8c355cc83eb21fc5118eb
Patch Set 1 #Patch Set 2 : oops #
Total comments: 2
Messages
Total messages: 24 (14 generated)
+bruthig would be good to run the testing set with this change to verify nothing gets noticeably worse.
Description was changed from ========== ChromeOS color extraction - only look at a maximum of 10k pixels in the input image. The pixels that are chosen are evenly distributed throughout the image. This proved to be more effective than limiting the color space (i.e. the number of unique colors). BUG=687852 ========== to ========== ChromeOS color extraction - only look at a maximum of 10k pixels in the input image. The pixels that are chosen are evenly distributed throughout the image. This proved to be more effective than limiting the color space (i.e. the number of unique colors). BUG=687852 ==========
estade@chromium.org changed reviewers: + bruthig@chromium.org
estade@chromium.org changed reviewers: + jamescook@chromium.org
+jamescook, ptal Since the feature is not on by default yet, I feel empowered to make this optimization and try to determine later if it's too lossy for our liking. I would still like to test this against the whole set of sample wallpapers but it doesn't need to block the change, and it would be good to start collecting data to verify that this addresses the majority of the slow cases we're seeing in UMA.
LGTM. Speed is a great feature. https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.cc File ui/gfx/color_analysis.cc (right): https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.c... ui/gfx/color_analysis.cc:374: // prime number to reduce the chance of picking an unrepresentative sample. Good idea.
The CQ bit was checked by estade@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by estade@chromium.org
estade@chromium.org changed reviewers: + thakis@chromium.org
+thakis for owners
The CQ bit was checked by estade@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Description was changed from ========== ChromeOS color extraction - only look at a maximum of 10k pixels in the input image. The pixels that are chosen are evenly distributed throughout the image. This proved to be more effective than limiting the color space (i.e. the number of unique colors). BUG=687852 ========== to ========== ChromeOS color extraction - only look at a maximum of 10k pixels in the input image. The pixels that are chosen are evenly distributed throughout the image. This proved to be more effective than limiting the color space (i.e. the number of unique colors). On at least one large sample wallpaper and my workstation, this reduces runtime from hundreds of ms to <10ms. BUG=687852 ==========
lgtm, but I don't understand the prime: https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.cc File ui/gfx/color_analysis.cc (right): https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.c... ui/gfx/color_analysis.cc:374: // prime number to reduce the chance of picking an unrepresentative sample. On 2017/04/07 14:05:47, James Cook wrote: > Good idea. I'm too dense to understand why the divisor being a prime number helps here. Can you expand on this? My take would've been that if you walk the image with a fixed stride, you can always end up with an unrepresentative sample (put red pixels on the pixels you hit, make all other pixels white, and your thing will always pick red even if the image is mostly white). This might be good enough in practice, but I don't see how the prime helps. (If you want to not have this kind of error, you could pick 10000 numbers between 0 and pixel_count at random, then sort them so you don't thrash the cache when you walk them, and collect those randomly-chosen pixels.)
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 2017/04/07 15:33:23, Nico wrote: > lgtm, but I don't understand the prime: > > https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.cc > File ui/gfx/color_analysis.cc (right): > > https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.c... > ui/gfx/color_analysis.cc:374: // prime number to reduce the chance of picking an > unrepresentative sample. > On 2017/04/07 14:05:47, James Cook wrote: > > Good idea. > > I'm too dense to understand why the divisor being a prime number helps here. Can > you expand on this? My take would've been that if you walk the image with a > fixed stride, you can always end up with an unrepresentative sample (put red > pixels on the pixels you hit, make all other pixels white, and your thing will > always pick red even if the image is mostly white). This might be good enough in > practice, but I don't see how the prime helps. > > (If you want to not have this kind of error, you could pick 10000 numbers > between 0 and pixel_count at random, then sort them so you don't thrash the > cache when you walk them, and collect those randomly-chosen pixels.) yes, you could, that's why it reduces the chance rather than removes the chance. My assumption would be that in practice you might have an image with vertical stripes, e.g. the first n pixels of each row are red and the next m pixels are green. If the image is 1000 pixels wide and you step by exactly 10k you'd only ever see red.
On 2017/04/07 16:27:49, Evan Stade wrote: > On 2017/04/07 15:33:23, Nico wrote: > > lgtm, but I don't understand the prime: > > > > https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.cc > > File ui/gfx/color_analysis.cc (right): > > > > > https://codereview.chromium.org/2797033002/diff/20001/ui/gfx/color_analysis.c... > > ui/gfx/color_analysis.cc:374: // prime number to reduce the chance of picking > an > > unrepresentative sample. > > On 2017/04/07 14:05:47, James Cook wrote: > > > Good idea. > > > > I'm too dense to understand why the divisor being a prime number helps here. > Can > > you expand on this? My take would've been that if you walk the image with a > > fixed stride, you can always end up with an unrepresentative sample (put red > > pixels on the pixels you hit, make all other pixels white, and your thing will > > always pick red even if the image is mostly white). This might be good enough > in > > practice, but I don't see how the prime helps. > > > > (If you want to not have this kind of error, you could pick 10000 numbers > > between 0 and pixel_count at random, then sort them so you don't thrash the > > cache when you walk them, and collect those randomly-chosen pixels.) > > yes, you could, that's why it reduces the chance rather than removes the chance. > My assumption would be that in practice you might have an image with vertical > stripes, e.g. the first n pixels of each row are red and the next m pixels are > green. If the image is 1000 pixels wide and you step by exactly 10k you'd only > ever see red. hmm, let me rephrase that --- if the image is 2500 pixels wide and 1000 pixels tall and your divisor is 10k, you are stepping by 250, which seems like a very round number and susceptible to failing on striped images, borders, etc. If your divisor is 10007, you're stepping by 249, which would only be susceptible to weird diagonal striping. I assume that prime numbers divide less evenly into most real-world pixel counts. Perhaps not the best safeguard but it's a cheap one. The random pixels idea is a good one except I'd like this algorithm to be deterministic. We'll soon verify that in practice this heuristic, although lossy, is acceptable.
The CQ bit was checked by estade@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 20001, "attempt_start_ts": 1491583177805390,
"parent_rev": "a7c962cd009df5796428aa072e9a41603526ca71", "commit_rev":
"b4c4b3509fdf1bc0f8a8c355cc83eb21fc5118eb"}
Message was sent while issue was closed.
Description was changed from ========== ChromeOS color extraction - only look at a maximum of 10k pixels in the input image. The pixels that are chosen are evenly distributed throughout the image. This proved to be more effective than limiting the color space (i.e. the number of unique colors). On at least one large sample wallpaper and my workstation, this reduces runtime from hundreds of ms to <10ms. BUG=687852 ========== to ========== ChromeOS color extraction - only look at a maximum of 10k pixels in the input image. The pixels that are chosen are evenly distributed throughout the image. This proved to be more effective than limiting the color space (i.e. the number of unique colors). On at least one large sample wallpaper and my workstation, this reduces runtime from hundreds of ms to <10ms. BUG=687852 Review-Url: https://codereview.chromium.org/2797033002 Cr-Commit-Position: refs/heads/master@{#462892} Committed: https://chromium.googlesource.com/chromium/src/+/b4c4b3509fdf1bc0f8a8c355cc83... ==========
Message was sent while issue was closed.
Committed patchset #2 (id:20001) as https://chromium.googlesource.com/chromium/src/+/b4c4b3509fdf1bc0f8a8c355cc83... |
