Author Topic: Prizm image compressing algorithm  (Read 7073 times)

0 Members and 1 Guest are viewing this topic.

Ashbad

  • Guest
Prizm image compressing algorithm
« 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:



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:

Code: [Select]
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


Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Prizm image compressing algorithm
« Reply #1 on: May 24, 2011, 11:03:56 pm »
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
« Last Edit: May 25, 2011, 01:48:05 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55942
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Prizm image compressing algorithm
« Reply #2 on: May 25, 2011, 01:07:56 am »
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)
Now active at https://discord.gg/cuZcfcF (CodeWalrus server)

Offline z80man

  • Casio Traitor
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 977
  • Rating: +85/-3
    • View Profile
Re: Prizm image compressing algorithm
« Reply #3 on: May 25, 2011, 05:00:32 am »
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

List of stuff I need to do before September:
1. Finish the Emulator of the Casio Prizm (in active development)
2. Finish the the SH3 asm IDE/assembler/linker program (in active development)
3. Create a partial Java virtual machine  for the Prizm (not started)
4. Create Axe for the Prizm with an Axe legacy mode (in planning phase)
5. Develop a large set of C and asm libraries for the Prizm (some progress)
6. Create an emulator of the 83+ for the Prizm (not started)
7. Create a well polished game that showcases the ability of the Casio Prizm (not started)

Ashbad

  • Guest
Re: Prizm image compressing algorithm
« Reply #4 on: May 25, 2011, 09:35:41 am »
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 :)

Offline JosJuice

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1344
  • Rating: +66/-14
    • View Profile
Re: Prizm image compressing algorithm
« Reply #5 on: May 25, 2011, 09:44:21 am »
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.

Ashbad

  • Guest
Re: Prizm image compressing algorithm
« Reply #6 on: May 25, 2011, 09:52:03 am »
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.

Offline JosJuice

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1344
  • Rating: +66/-14
    • View Profile
Re: Prizm image compressing algorithm
« Reply #7 on: May 25, 2011, 09:54:23 am »
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?

Offline fxdev

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 177
  • Rating: +34/-6
    • View Profile
Re: Prizm image compressing algorithm
« Reply #8 on: May 25, 2011, 01:16:55 pm »
Maybe interesting: The Prizm's OS tells me it has native zlib support.
« Last Edit: May 25, 2011, 01:18:28 pm by cfxm »

Ashbad

  • Guest
Re: Prizm image compressing algorithm
« Reply #9 on: May 25, 2011, 01:41:55 pm »
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.

Ashbad

  • Guest
Re: Prizm image compressing algorithm
« Reply #10 on: May 25, 2011, 06:08:44 pm »
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:

Code: [Select]
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:

Code: [Select]
Currently chosen file  :--  C:\Users\Adam\Desktop\kitty.bmp
Size of Bitmap file    :--  4158 bytes

File that was input:



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.

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Prizm image compressing algorithm
« Reply #11 on: May 25, 2011, 06:58:22 pm »
How large are the decompression binaries?
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Ashbad

  • Guest
Re: Prizm image compressing algorithm
« Reply #12 on: May 25, 2011, 08:09:45 pm »
How large are the decompression binaries?

At the moment, zero bytes :P

Ashbad

  • Guest
Re: Prizm image compressing algorithm
« Reply #13 on: May 26, 2011, 06:49:15 pm »
well, IRB was lying to me, it doesn't absorb anything.  However, quite fixed up with this:

Code: [Select]
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.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55942
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Prizm image compressing algorithm
« Reply #14 on: June 03, 2011, 08:44:43 pm »
I don't understand that stuff much, but how large would a complex 8 bit 16x16 sprite be, for example?
Now active at https://discord.gg/cuZcfcF (CodeWalrus server)