Omnimaga
Calculator Community => Casio Calculators => Topic started by: Ashbad on May 24, 2011, 09:15:36 pm
-
I'm currently working on an algorithm that, similar to PNG-related formats, is lossless when a picture is rendered. I will start by explaining the format of a normal 24-bit bitmap image, and how one can quickly access the actual picture data and dimensions, and then go into depth on how far I've decided on how compression routines will work.
On-Computer Absorption, Compression, and Padding (ACP phase)
In a bitmap file, the chunks of data we are most concerned with are, and how large the values are:
- The offset from the beginning of the file the raw image data is documented 0x0A bytes from the beginning of the file (32bit)
- The size of the DIB header after the normal BMP header's size (non-inclusive) is 0x0E bytes from the beginning of the file (32bit)
- Width of bitmap is 0x12 bytes from beginning (32bit)
- Height of bitmap is 0x16 bytes from the beginning (32bit)
- We can check to see if input file is 24bit encoded by checking to see if byte 0x1C == 0x1800 (16bit)
- Size of raw pixel data is in 0x22 (this includes 4-byte alignment pads)
some notes:
- The format of a WINDOWSDIB bitmap file is in the order BMP_HEADER, DIB_HEADER, and RAWDATA. The BMP_HEADER and DIB_HEADER always start in static locations
- The end of the file can be marked as (beginning + *(beginning+0x0A) + *(beginning+0x22))
- each 'row' of pixels MUST be a multiple of 4, so if the lines are not aligned to that, there will be extra padding bytes with the value 0x00 inserted
This is good information for simply scanning a bitmap file for the data within, and I almost have a Ruby script up and working that will absorb the entire bitmap's raw data minus the paddings into a array from which it can be loaded into an ACPNG file format (Ashbad Compressed Prizm Networks Graphic file -- the file format pioneer has the first pick for the name :D) and then padded into a Prizm-C compatible 'const char NAME[] = {' format that can be inserted into a source file as regular picture data.
Actual Compression Concerns and Ideals
The style of compression planned for uses a lossless Pixel-Prediction algorithm that I almost have perfected for theoretical decently fast rendering and high compression rates (which can only be estimated, and not be said for sure, until I go into intensive testing mode). This method is very similar to what low-standard PNG images use, and can be summed up by this ripped picture from wikipedia -- the pixel X's value is predicted by the values of A,B,C, and D:
(http://upload.wikimedia.org/wikipedia/commons/3/39/Pixel-prediction.svg)
Another feature is palette indexing, for pictures with or less than 256 colors. This is tightly wrapped indexing, so if a picture has something like 126 colors, it would be based on a 7 bit palette with 126 entries. Or, a better example (let's use a value 127 < # < 255 for an 8 bit example) a picture with 192 colors would have 8 bit indexing, but would still be more compressed than a picture with 250 colors because it would support only 192 colors. I may have it later so you can still specify indexing for #ofcolors with 9-11 bit values, but the compression with this technique would be drastically less obvious, rising sub-exponentially at each bit level added.
The point of all of these measures (and a few I didn't mention yet) is to get an image file as small as technologically possible without any color loss -- that's why PNG-based compressions are generally more of a pain to write than 92% reducing JPEG compressions :P If you want an educated guess on how compressed a picture would be with this, I'll take Kerm's obliter8 title screen with a ~160K data size he regularly publically laments about. I assume from looking at the image itself it contains around 200-250 colors total, which with a indexing table would drop it to 80K instantly, no losses. The prediction method is much harder to predict to the many factors that relate output size and input size, such as size, bit depth and (surprisingly) width and height. Though, making a good guess, it'll knock off at least an additional 30% from where we were, bringing his title screen down to a more reasonable ~60K size, knocking already 100K of the top.
However, if I use advanced deflation and line-based predictions, along with other features I haven't looked into much yet, it could drop to ~35K. Yay Kerm's title screen! :)
Prizm-C routine to convert ACPNG data to nomal bitmap format
I haven't worked on it nearly as much, but the actual routine that renders ACPNG data will function with the following format, subject to change:
unsigned char Render_ACPNG_Data(void*datapointer, short x, short y, char mode, void*additional_args = 0);
inputs: pointer to ACPNG data, x position to render to in VRAM, y position to render to in VRAM, 8 bit value mode for how to render, optional pointer to additional arguments to communicate with the decompressor directly (mostly for debugging and possibly for getting info on data and such)
outputs: obvious.
Quite possible Specifications of the actual Prizm-C routine:
- estimated 1-5K function code size
- estimated 6-8 times slower rendering than normal graphical data
- estimated 1-24 hours Kerm will be happy I made a routine that will lower his title screen size
besides the silly last one, the specs are actual estimates I theorize will be a result, and will most likely not be subject to change.
Questions, Comments, "I WANNA HELP", etc.
feel free to post anything described in the sub-title's below or email me at a s h b a d . a l v i n @ g m a i l . c o m (remove spaces obviously :P AND DO NOT REPEAT IT HERE WITHOUT SPACES.)
~Ashbad
-
Looks nice. One question I have is why you don't just use PNG format? No offense, but it's kind of a pain to have to run images through a converter every time you edit them. That algorithm has also already been extensively bug tested to eliminate edge effects and achieve high compression ratios, which would presumably reduce your debugging load. Just curious.
Anyway, can't wait to see how this turns out. :)
PS: Please try to keep the file extension down to three letters so the Prizm's file system can handle it.
EDIT: Forgot the word "edit" :P
-
Image compression would be nice. I bet a lot of people will appreciate this when making complex games with like 300 sprites like RPGs (I can't imagine how much space graphics in Chrono Trigger must take)
-
This is useful because with Obliterate, about 5/6 of the file size is image data. Actually with my ongoing shell project I was planning on adding shell calls for compresses image formats. The idea is that you would pass the filename of an image or a pointer to it and the shell would then return a pointer to the converted 16 bit image. There would only be one argument necessary as the the x and y values can be determined from header. Formats that I want to include are .png .gif .jpg and .bmp
-
Qwerty: im basically using 90% of the .png format already, im just adding in a few things to make compression of data of utmost importance, while normal png files are balanced between speed and size. However, good concerns, and thanks :)
Also, the prizm's file type can only support up to 3 letters? O.o that actually doesn't matter here, but thanks for the info. ACPNG images arent in files, its actual data that can be inserted into a program :)
Also, z80man, that sounds awesome :)
-
Qwerty: im basically using 90% of the .png format already, im just adding in a few things to make compression of data of utmost importance, while normal png files are balanced between speed and size. However, good concerns, and thanks :)
Then why not use PNG? Speed is still important, and making a format that's almost like PNG would be pretty unnecessary if we can just use PNG.
Also, the prizm's file type can only support up to 3 letters? O.o
Yep.
-
PNG rendering isn't made for speed and optimization in the least. Most rendering algorithms like the Adam7 routine would be way too slow for a device with onoy a 29MHz speed. However, its quite fine on a 1GHz machine. But that's not what we're working with. And, my rendering routine also has to be fast, and common PNG formats and rendering scripts are much too large.
The PNG format I'm playing with will be perfect for the Prizm.
-
PNG rendering isn't made for speed and optimization in the least. Most rendering algorithms like the Adam7 routine would be way too slow for a device with onoy a 29MHz speed. However, its quite fine on a 1GHz machine. But that's not what we're working with. And, my rendering routine also has to be fast, and common PNG formats and rendering scripts are much too large.
The PNG format I'm playing with will be perfect for the Prizm.
Ah, okay. And it's supposed to be for use inside programs only?
-
Maybe interesting: The Prizm's OS tells me it has native zlib support.
-
PNG rendering isn't made for speed and optimization in the least. Most rendering algorithms like the Adam7 routine would be way too slow for a device with onoy a 29MHz speed. However, its quite fine on a 1GHz machine. But that's not what we're working with. And, my rendering routine also has to be fast, and common PNG formats and rendering scripts are much too large.
The PNG format I'm playing with will be perfect for the Prizm.
Ah, okay. And it's supposed to be for use inside programs only?
yeah, it'll be similar to how source coder 2.0 handles images into normal bitmap Prizm-compatible data.
-
Wow, I lost all of my absorption source.. and then I rewrote it 10 time more optimized using methods from an updated 'file.c' module :)
source code so far:
class BitmapFile
directory = nil
openedfile = nil
EXTENSION = "bmp"
def initialize(directory)
@directory = directory.chomp.to_s
if @directory.rpartition(".")[2] != EXTENSION
puts 'Exiting -- not a bitmap!!'
exit
end
end
def getdir
return @directory
end
def openfile
@openedfile = File.new(@directory, "r")
end
def closefile
@openedfile.close
end
def getsize
return File.size(@directory)
end
end
currentfile = BitmapFile.new("C:\\Users\\Adam\\Desktop\\kitty.bmp")
currentfile.openfile
object = 255
absorbed_file = Array.new(currentfile.getsize, object)
currentfile.getdir.each_byte {|byte|
absorbed_file[byte] = byte
}
currentfile.closefile
puts 'Currently chosen file :-- ' << currentfile.getdir
puts 'Size of Bitmap file :-- ' << absorbed_file.length.to_s << ' bytes';puts
OUTPUT:
Currently chosen file :-- C:\Users\Adam\Desktop\kitty.bmp
Size of Bitmap file :-- 4158 bytes
File that was input:
(http://img.removedfromgame.com/imgs/kitty.bmp)
This proves that this optimized version is fully functional and that the computer part is coming along well. I'll work on outputting the data in Prizm-C format tonight, and then tomorrow add in the actual compression code.
-
How large are the decompression binaries?
-
How large are the decompression binaries?
At the moment, zero bytes :P
-
well, IRB was lying to me, it doesn't absorb anything. However, quite fixed up with this:
class BitmapFile
directory = nil;openedfile = nil #non-standards
EXTENSION = "bmp" #constants
sizeoffile = nil #standards
def initialize(directory)
@directory = directory.chomp.to_s
if @directory.rpartition(".")[2] != EXTENSION
puts 'Exiting :-- not a bitmap!!';exit;end
@sizeoffile = File.size? @directory
if @sizeoffile == nil;puts 'Exiting :-- file doesn\'t exist!';exit;end
end
#non-implied get methods
def getdir;return @directory;end
def getbyte(specific_byte);return IO.read(@directory, 1, specific_byte);end
def getsizeofile;return @sizeoffile;end
end
currentfile = BitmapFile.new("C:\\Users\\Adam\\Desktop\\kitty.bmp")
absorbed_file = Array.new(currentfile.getsizeofile) {|byte_index|
byte_index = currentfile.getbyte(byte_index).bytes.to_a
}
puts 'Currently chosen file :-- ' << currentfile.getdir
puts 'Size of Bitmap file :-- ' << absorbed_file.length.to_s << " bytes\n"
now that it FINALLY works like it's supposed to, we're all good it seems for now. It puts me back a day, but oh well.
-
I don't understand that stuff much, but how large would a complex 8 bit 16x16 sprite be, for example?
-
Excuse, but what's that source code? I don't reconize any languages i Know...
-
Ruby I think, since that was Ashbad's favorite language.
-
I use a simple compression by using a color swatch, and size of all bitmaps is divided by 2 (plus some bytes for the color swatch). It work fine :)
-
Colored gravity Duck FTW