| |
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....
|
| |
4mat
Registered: May 2010
Posts: 66 |
I think my petscii converter does a simple tally per 8x8 grid against the char rom, then picks the highest scoring char. Good thing is if you use a custom char set it'll always pick something regardless of the size. (in Party Bit the credit pictures were done with a 6 char font) Doing colour pics was a bit more involved, I went with a threshold level around the rgb values in the pic and compared against the palette's rgb. (Probably should have used luminance as well but I didn't) |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
Quoting 4matI think my petscii converter does a simple tally per 8x8 grid against the char rom, then picks the highest scoring char. Good thing is if you use a custom char set it'll always pick something regardless of the size. Matching against an existing set of chars makes the problem a lot easier, i think. Generating an "optimal" set of arbitrary chars, on the other hand... :) |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
Quoting OswaldI'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! :) |
| |
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.. |
| |
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) |
| |
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. |
| |
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. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
suprisingly good considering it basically only counts and compares set pixels yet.
 |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
holy cow, least squares and k-means makes me wanna code FFT. respect guys you can understand and implement that :) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
another bug ironed, quite puzzling, I only compare pixels at te same place, if not distance = +1. the result is much better than expected.
 |
| Previous - 1 | 2 | 3 | 4 | 5 - Next |
