/wpc/ - Weekly Programming Challenge

Previous Thread (Cross-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 (Cross-thread) (Draw a picture using random shapes)
Week 2 (Cross-thread) (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
ghostbin.com/paste/txzsg
arxiv.org/pdf/1209.1960.pdf
git.fuwafuwa.moe
twitter.com/NSFWRedditImage

...

Great job!

lol literally no one cares about your thread

havent made the thread before

i prefer it to talking about cell phones, distros, and theorycrafting programming languages personally :-)

How come you're posting in every single one of them then

So, order all pixel by H, S, L, split into N equal size groups, find mean of every group in HSL space. Looks interesting.

I think it's a good idea. Keep at it boss

whats ur favourite cell phone, watch, distro, programming language and why is it the one I'm using?

I'm too much of a brainlet to even know where to start for this challenge desu

start by loading an image and accessing it's pixels and each pixels rgb value.

...

b

That would look so much better with dithering.

The picture is meant to demonstrate the palette. Dithering would go directly against that.

Well that's a dumb challenge. I figured it would've been to create something useful.

so use dithering in your code..

anyone stopping you?

Creating a palette that represents a picture is useful.

A palette that would be best for dithering is going to be different, even with same color count, and its colors are likely going to look like they have little to do with original image. Making a palette like that is a different problem entirely.

Which one is more useful? I'd say former, because dithering is not useful anymore, since we can have all the colors we want.

somebody do this picture

>You're encouraged

would a cute girl succ my pepe?

...

oh fuugg

now this one

...

this is so cool

so i think you're manually specifying 3 to 6 colors? how do you choose which colors to sample? just random pixels?

Ewwwwwwwwwww

I know I'm a bit late but for the first challenge How did you get a list of the colours? I actually made a list but I could probably just randomly select a pixel from the original image couldn't I?

My code is here.

github.com/AUTOMATIC1111/randdraw

I convert colors in picture from RGB to LAB colorspace (this step is optional if you want to write your own implementation), and then I do k-means clustering the way I described in this

as said, added with a palette, no sorting

Do you think you should be able to do a thing as simple as posting one (1) singular picture with a palette to go with it?

It will look better and converge faster if you produce a unique list (set) of colors. You only need to do it once so don't worry about the speed.

I'm finally done challenge 1! 10,000,000 iterations takes 1.6 seconds. I'm only drawing a horizontal line of varying length though.

if you create a unique list the color that's used for 1 pixel has as much chance as being selected as a color that covers half the image.
better to just pick a random pixel from the image.

Not bad. You should try larger shapes, and with thin horizontal line it almost looks like original picture with noise over it.

I'm curious, what are you doing for your initial clusters?

That's exactly the point. Those small regions that have unique colors that are not used else in the picture are usually rather important for the picture.

Yeah, I had it hardcoded at only 10. Just realised. It increase the runtime by a lot too which shows how horrible the implementation is. It now does a line of random length between 1 and 64.

I'll need to implement a set because I was getting the unique colours but it took way too long for me to ignore.

First cluster is picked at random.
Each next cluster is picked as the color that has largest distance to its closest cluster.

...

Needs a bit more work, it looks like, color 8 is just few pixels in your picture, and doesn't really correspond to anything in original pic.

Just sort the pixel array and remove the duplicates. You can use any (consistent) order that you want, but lexicographic is probably the easiest to implement if you're doing it from scratch. If you're using python the default sorting function should do the trick.

I always do this by putting the data into a map and then reading keys from the map.

Hey Sup Forums, new to programming, heres what I did for conways game of life in c :
It works as intended, but are there and bad practices I am using?
Thankyou!
ghostbin.com/paste/txzsg

so you loop different k-means starting with random centroids and the input the result into another iteration?

No, this operation is done before the first iteration starts.

It would be a lot more readable if you add some whitespace. I think neighbor calculation would look much better in a separate function.

>Each next cluster is picked as the color that has largest distance to its closest cluster.
How then can you now the cluster composition before running k-means? I am Confucius.

>now
*know

I pick one at random. Then I find the point that is furthest from the one I picked. Now I have two clusters. If I need another one, I go through remaining points and for each calculate the distance to the closest of (two) existing clusters. I pick that point that has largest calculated distance. It becomes the third cluster. I repeat this until I have as many clusters as I want, then I start iterations.

ok I get it now. Thanks.

maybe it's best to do half the iterations normally then do the last half with unique colors, that way larger regions get done fast, and the small details later

Don't forget to post comparisons for us if you decide to play around with that.

Turns out it's called Maximin method: arxiv.org/pdf/1209.1960.pdf

Instead of choosing the first cluster at random have you tried choosing the most numerous?

The most numerous what?

The color that appears more often in the original image.

>>As an example here a palette created by my program, with 5 colors.
10 == 5

Also I had an epiphany.
Right now we are passing to k-means 3 values of color (RGB or LAB) thus finding clusters in 3D color space. This way the structure of the original pic is destroyed but its clusters are there clear to see to anyone with eyes!!!!! Lets pass to k-means also the colors coordinates on the original pic. This way we are clustering in a 5D space that takes into account the color spatial distribution on the original image.

>lets
>we
Why don't you do it first and post how well it actually works?

This was considered in the first thread about this challenge.
>

Why waste time reinventing Gimp's posterize filter?

>practicing programming is a waste of time

...

You can practice doing something else, obviously.

>You can practice doing something else, obviously.
Well, we aren't. Obviously.

This is a hobbyist thread.

Because it's fun? Pretty much all the tasks that we've done so far have already been "done" by other programs or libraries. But doing them yourself, and trying new ideas is really satisfying and rewarding.

I guess we could always turn these threads into a circlejerk about which programming language is the best instead of you know, actually programming.

>uding the smiley with a carat nose

Well I implemented it any way just to check for myself and It worse by a lot.
This does my head in. I was pretty sure this would improve the palette considerably. I really would like an explanation as to why it does not work if anyone got any.

Try this image with 3 colors.

I get this palette.
white is overwhelming everything.

same but without coords

For me, results look different. Here is without coordinates.

And here is with coordinates. L is 0-100, A/B are from -128 to 128, and x/y are from 0 to 100.

This one with coordinates is the same as without.

Here's the kind of picture that's supposed to create the desired effect. There are three shades of green and two shades of red. The hope is that with coordinates in clustering, out of 4 colors in palette, we'll get two reds, one white and one green.

Somehow, exactly this result is included without coordinates included.

Same but I don't normalize anything.
I don't see any mistake on my side.
Are you sure you are doing it right because I don't think normalizing should have such drastic effect.

This is with coordinates included. There is another shade of white, but it's unused. Too bad.

I think you should. Here is the same picture for me, but without normalization.
In fact, that, that's the result of applying palette created with 5-dimensional k-means to the picture. There is another way to approach this, and it's to use locations/colors directly from clustering. Hold on, I might be able to do this.

Here it is. Without normalization. Toppest of keks right there.

This is with colors normalized to 0-200.

0-150

Man, these topics are always cool. Love seeing the results. Great job, everyone.

And here is my magnus opus, a video demonstrating the effect of adding coordinates to clustering colors. Each frame corresponds to different normalization value for coordinates. In first frame, x and y are normalized to 0, which means x and y are always 0 for k-means, and the clustering is done without coordinates. In last frame, x and y are normalized to 300. Remaining frames go linearly from 0 to 300.

ITT Sup Forums gets A E S T H E T I C

This is cool af. Post your code when it's finished, I'd love to see it.

Same, really enjoying these threads lately. Always really cool to see what people come up with.

btw any good user made sites that i can host my projects on?

...

github.com/AUTOMATIC1111/randdraw

Github?

>Github?
i want something comfy

...

What is your method for measuring comfiness?

upload the files to pomf clones :^)

git.fuwafuwa.moe

Fucked up Dithering

I wish there was a how to:
For this because I have 0 idea how any kind of image stuff works or what thing is need to download for my language

...

So? What's the problem? Is google blocked in your country?

Wow, you're like an asshole type.

Check out the previous threads, they can give you a bit of insight on how to get started and what you'd need to implement.

It's often helpful to write down what each part of your program should do and to google solutions for each step. For instance, if a part of your program needs to load an image, then find out what libraries are available in your language that can do that.

Do you wish that there was a how to written in this thread for every language about how to work with images in it?