[CSDb] - User Forums - Converting animation into lossy charset

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Converting animation into lossy charset - how ?

2015-07-12 12:14

Oswald

Registered: Apr 2002
Posts: 5094

Converting animation into lossy charset - how ?

I've always wondered how an algorithm decides how far is a char from another. any pointers ?

... 38 posts hidden. Click here to view all posts....

2015-07-12 17:12

Krill

Registered: Apr 2002
Posts: 2980

Quoting Oswald

I'm just lazy to mess with FFT totally new territory for me, altho i know what its basically, but its a totally different thing when you have to code it (or make some alien code to work)

Actually, playing around with libjpeg for this purpose and maybe hacking it to produce 256 characters doesn't sound like a half-bad idea to me.

Groepaz, what's your verdict? And algorithm, please do tell us some details of what you did so far! :)

2015-07-12 17:35

algorithm

Registered: May 2002
Posts: 705

I wont post everything here. But for a quick insight into the basics of what I am doing. please read the manual of one of my tools here

https://www.dropbox.com/s/ygmfp8nd0o4z35m/CSAM%20Super%20-%20Ma..

2015-07-12 18:21

chatGPZ

Registered: Dec 2001
Posts: 11386

Quote:

Groepaz, what's your verdict?

i have not yet seen anything lossy on C64 that i liked (sorry algo) and i dont think i can make it better either :) (and i dont find it an interesting subject in the first place)

2015-07-12 18:23

ChristopherJam

Registered: Aug 2004
Posts: 1409

FWIW, both the zoomer in Effluvium and the animated ball in Jam Ball 2 use variations on k-means clustering, with a fair amount of tweaking.

Basics are explained at https://en.wikipedia.org/wiki/K-means_clustering where each observation X corresponds to an 8x8 tile from one of the source images. (or, in Effluvium's case, an L shaped tile that covers three chars..)

I tend to work in greyscale until I have a decent dictionary, then dither that to hires or multicolor before requantising the frames to the final character set. For Jam Ball 2 I actually built dictionary of somewhere around 260-265 entries, as several of the final entries merged once I dropped to one bit per pixel.

A JPEG style DCT means you can start with comparing overall luminance and low frequency components, but really that's mostly a speed optimisation. A simple sum of squared differences works pretty well, and at one bit per pixel that turns out to just be a count of the pixels that are different.

2015-07-12 18:24

JackAsser

Registered: Jun 2002
Posts: 2014

Oswald: The technique is called clustering. The algorithm below is naive and extremely slow. Finding the optimal solution is NP-complete. You need to cut corners, but just to give you an idea:

1) Generate all possible chars the animation has. It can be millions depending on how long it is etc.

2) You need to keep track of the frequencies, i.e. how often is a particular char used.

3) You need to create a function which calculate the difference between two characters and give a score. 0 == equal. >0 != equal. A method could be using least squares (https://en.wikipedia.org/wiki/Least_squares) or so.

4) Loop until your charset is x characters long.
4.1) Find all character pairs.
4.2) Generate an intermediate char. F.e. by averaging the two, or so.
4.3) Calculate the visual impact if you should pick that intermediate char by looking up in your frequency tables.
4.4) Pick the pair with the lowest possible visual impact and replace the two source chars with the intermediate char. Delete the source chars from the charset and update the frequencies.

Eon later you will have your clustered charset. This is how the rotator work in Mekanix. How the horizontal twister in Amplifire work etc.

2015-07-12 19:27

Oswald

Registered: Apr 2002
Posts: 5094

suprisingly good considering it basically only counts and compares set pixels yet.