/wpc/ - Weekly Programming Challenge

Previous Thread The only general on Sup Forums that actually programs. :^)

This week: Image Quantization

>Given a source image and a number, create and output to user a palette with this many colors in it. The requirement is if you would use that palette to draw the picture anew, the result should look good. I don't think I can pose the problem in a more strict way than that.
>As an example here a palette created by my program, with 5 colors.
>A more difficult version of the problem would be to have the program automatically detect the needed number of colors.

You're encouraged to find ways to make the problem easier or more difficult depending on your skill level.

Post results and share bits of code.

>Previous Challenges (Will throw this in a pastebin or github repo when I get around to it):
Week 1 (Draw a picture using random shapes)
Week 2 (Conway's Game of Life)

>Other places to find challenges / things to do:
rosettacode.org/
projecteuler.net/

Other urls found in this thread:

github.com/AUTOMATIC1111/randdraw/blob/master/CIEDE2000.cpp
paste.pound-python.org/show/AK3xyoBVZHtrUoOW4qlw/
twitter.com/SFWRedditVideos

what am i doing wrong?

You again girl?
Do you want to be my gf now?

Not the same OP mate, you're going to have to ask him instead. I just used his image for the OP.

What solution are you trying to implement?

k-means but with fixed amount of iterations

I just now realized the possibility of the most simple implementation in style of challenge 1:

1. generate a palette with random colors.
2. paint the picture with it.
3. change one color in the palette to a random one.
4. paint the picture with it.
5. compare the picture to original.
6. If the picture with changed color in the palette is NOT closer to original the previous one, revert the color change.
7. go to 3.
Stop anytime

Why fixed? Doesn't converge? Are you using your own implementation?

Maybe.

tbf it's not really a challenge if you don't do anything and use code made by someone else. You don't learn anything or get any better if you use libraries

>using stdio.h
>2017

Here, for comparison, is my k-means solution. Of course, k-means finished in split second, while the random approach ran for minutes.

Please don't. Libraries are fine. You may not like it, but making a stink about in the thread makes it worse for everyone involved.

>Import everything
>Do a coding spaghetti monster
>Oh yea I'm so good at this
>Self-written code Top kek this so easy
You babies are pathetic. Going easy mode in challenges

I'm just starting challenge one and know I need to use Euclidean distance but I'm confused how. Obviously I can use the RGB values for a single pixel but I need to take the entire line/shape into account. Is it as simple as adding each pixel's distance together?

don't use euclidean distance, manhattan produces better results.

yeah just add each pixels distance together.

this produces the best results for me

diff += (abs(rA-rB) + abs(gA-gB) + abs(bA-bB))

I wrote everything from scratch. Posted a link to github multiple times. I don't even use image library, I work with BMP files instead.

>Wrote everything from scratch
Whats this?
github.com/AUTOMATIC1111/randdraw/blob/master/CIEDE2000.cpp

Isn't that basically bruteforcing the problem in a really inefficient way? lol

Basically. You want:
sqrt((r2 - r1)^2 + (g2 - g1)^2 + (b2 - b1)^2)

for each pixel comparison, then you sum the values along the shape you're doing the comparison and determine which value is greater.

It's worth noting you're going to get better performance if you use manhattan or cityblock distance over euclidean. It's less computationally expensive for practically the same result.

You can start by outputting to stdout for each cluster the color, the number of pixels in it, and average distance.

It's not used. You need to pass --colordist=CIE2000 to program to enable it, and it doesn't even improve overall quality.

Yes. Just like with challenge 1.

Tons, if not most people in these threads have been doing the algorithms from scratch, it wouldn't be challenging or fun otherwise.

how do i correctly choose the first means? Is it a random color of the input image or a mean of n random values?

The most simple approach is to just pick k random different colors from the image.

In my program, I pick one at random, and for each next, I find the color in the image that has the largest distance it its closest cluster.

so to initialize i have to compute a random mean and cant 'seed' it with a random color from the image?

What the fuck guys. I just started learning C# this semester, all I've programmed so far is a form that takes like 3 inputs and outputs a number. How the fuck do you expect me to do this shit? Where do I even start? Just ahhhhhhhhh reeeeeeeeeeee!!

I don't think you understood what I wrote correctly. Neither of two options I offer include averaging anything. You find the color that's most distant from its nearest cluster, and use that color as a center of a new cluster. The first color is chosen randomly, a single pixel from a picture, and also does not involve calculating mean of anything. You can use that color as a seed.

So help me:

1. create list of all colors (R,G,B)
2. init N clusters with a random color from 1. as "mean"
3. for all colors: compute distance from current color to "mean color" to all clusters
4. add this color to the cluster with the smallest distance
5. compute mean of all clusters
6. repeat 3 - 5 until cluster sizes dont change

Am i correct?

>6. repeat 3 - 5 until cluster sizes dont change
Originally, it's "mean color" for every cluster does not change, or the change is too small to be considered one.

Otherwise, yes.

Doing exactly this i get this shit.

The color hue does never change however

user, I...

It's possible that your implementation is not entirely correct. Post your code.

Here's how iterations for this picture look for me.

Has anyone else tried doing cyclic cellular automation from challenge 2? It looks really cool.

Ouch. This will work but it is basically maximum bruteforce. I also bet that among all solutions it will be the one to take the most time.

Well, not exactly; I know at least one modification to that algorithm that will make it run thousands+++ times longer - at step 3, change all colors instead of one.

As evidence that k-means is not always the best solution I present the following.

This one is is a mix between grouping RGB colors and Euclidean Distance sieves. No k-means used.

This is one is k-means on LAB colors.
I won't post k-means on RGB because it is worse than this.

This one is a mix of the two previous ones but fully in LAB space.

It initially groups colors and does a bit of Euclidean distance to reduce the number of representative colors and then used k-means of that smaller color space.

You have unused brown in 6 color version.

Here is k-means LAB for me. Personally, I think it looks better than your first picture. With windows painted green.

fug

It is not unused. It is in Yotsuba's shoulders.

In the first picture you posted?

yes.

Post a full-size 6-color version for comparison.

While we're at it, you have two shades of black in the bottom left corner of your picture, while your palette only has one.

That is an artifact of reusing the script from challenge one. Where the initial temp picture is all black. Just picture the darkest color there. I could pass an initial color but I don't think it is worth it.

Still, though, post a full resolution PNG of your 6 color version for comparison.

...

Welp. I guess I'll try to and reconstruct the image with your colors and calculate the distance to original for both your and my versions later.

I guess it is objective. You pic up two shades of blue while I sacrifice one to pick up the brown.

You mean subjective.

...

>we andy warhol now

after you get the reduced colors, set them to something else manually

>using the smiley with the carat nose
>using the square root with the carat nose

>why does the jew try and self insert into everything, a-am i right guys?

bump

lmao I spent almost an hour trying to debug my kmeans code trying to figure out why I was getting completely wrong colours that weren't even in the source, and it turns out I had my variables mixed up as rbg instead of rgb.

Here's the code if anyone was curious. Probably not the most efficient way to do it, but it wasn't nearly as difficult to do as I thought it would be.

paste.pound-python.org/show/AK3xyoBVZHtrUoOW4qlw/

I'm finding that it generally tends to favour 'brownish' tones though (unless I've done something wrong), and not colors that are actually visually appealing.

t h i c c

What is going to be the next challenge?

Not what, when. Next Friday.

I've got a pretty fun idea for Friday, if no has decided to make a thread I'll make one.

Well, here's how your palette looks when mapped to picture but using LAB colorspace. Green window gone. Thank god.

I SWEAR TO GOD

are you using manhattan instead of euc? just a random guess

Euclidean, lab color space.

This is too complicated for me.
digits decide my project

it's only as complicated as you make it, user. you can choose to write everything from scratch, or pick libraries to alleviate certain burdens.

i didnt actually try the image on my own. first result that disappointed me desu

takes 8 to get the hair. i told myself i'd stop working on this htough :-)

higher res

Took more time to draw a proper explanation of my result its a easy way to do it
as you can see its based on colors dithering methodology but replacing dithering by a threshold to force the number of colors and

replacing those colors with a sum of the underneath original ones!
Using light on the original will move the colors selected' as the threshold move too, nasty fix on the output if darkning is used you have to counterbalance for a better output.

...

Would you like to post a picture and a palette to go along with it so we can see how good your approach is?

Maybe tomorrow I'm really busy right now.
Sorry.
My bad, You'll have to do it yourself ! Take that picture free of charge I took it myself as a present for you today and consolation prize.

How do you compute the average color?

You are not making sense.

Who needs clustering algorithms when you choose the right color space?
#!/usr/bin/env ruby
require 'open3'
require 'matrix'

def fmod(a, b)
a -= b while a > b
a
end

def rgb2hsl(rgb)
r, g, b = rgb
max = rgb.max
min = rgb.min
c = max - min
h =
if c.zero?
0
elsif max == r
fmod((g - b) / c, 6)
elsif max == g
(b - r) / c + 2
elsif max == b
(r - g) / c + 4
end
h *= 60
l = (min + max) / 2
s = [0, 1].include?(l) ? 0 : c / (1 - (2 * l - 1).abs)
[h, s, l]
end

def hsl2rgb(hsl)
h, s, l = hsl
c = (1 - (2 * l - 1).abs) * s
h /= 60
x = c * (1 - (fmod(h, 2) - 1).abs)
r, g, b =
case h
when 0..1
[c, x, 0]
when 1..2
[x, c, 0]
when 2..3
[0, c, x]
when 3..4
[0, x, c]
when 4..5
[x, 0, c]
when 5..6
[c, 0, x]
end
m = l - c / 2
r += m
g += m
b += m
[r, g, b]
end

out, _err, _st = Open3.capture3('pngtopam', ARGV[0])
n = ARGV[1].to_i
header = "P6\n600 450\n255\n"
unpacked = out.unpack("A#{header.length}C*")
raise 'wrong' unless unpacked[0] == header
colors =
unpacked.drop(1)
.map { |x| x / 255.0 }
.each_slice(3)
.map { |rgb| rgb2hsl(rgb) }
.sort
res =
colors.each_slice(colors.length / n)
.map do |slice|
avg = slice.map(&Vector.method(:elements)).inject(:+) / slice.length
hsl2rgb(avg.to_a).map { |x| (x * 255).to_i }
end
print "P3\n#{n} 1\n255\n"
res.each { |rgb255| print rgb255.join(' '), "\n" }

This isn't actually as good as clustering, of course, but the result is still pretty competitive IMO.

a single bump for visibility