Recherche avancée

Sur d’autres sites (4365)

• Basic Video Palette Conversion

  20 août 2011, par Multimedia Mike — General, Python

  How do you take a 24-bit RGB image and convert it to an 8-bit paletted image for the purpose of compression using a codec that requires 8-bit input images ? Seems simple enough and that’s what I’m tackling in this post.

  Ask FFmpeg/Libav To Do It
  Ideally, FFmpeg / Libav should be able to handle this automatically. Indeed, FFmpeg used to be able to, at least at the time I wrote this post about ZMBV and was unhappy with FFmpeg’s default results. Somewhere along the line, FFmpeg and Libav lost the ability to do this. I suspect it got removed during some swscale refactoring.

  Still, there’s no telling if the old system would have computed palettes correctly for QuickTime files.

  Distance Approach
  When I started writing my SMC video encoder, I needed to convert RGB (from PNG files) to PAL8 colorspace. The path of least resistance was to match the pixels in the input image to the default 256-color palette that QuickTime assumes (and is hardcoded into FFmpeg/Libav).

  How to perform the matching ? Find the palette entry that is closest to a given input pixel, where "closest" is the minimum distance as computed by the usual distance formula (square root of the sum of the squares of the diffs of all the components).

  
  
  

  That means for each pixel in an image, check the pixel against 256 palette entries (early termination is possible if an acceptable threshold is met). As you might imagine, this can be a bit time-consuming. I wondered about a faster approach...

  Lookup Table
  I think this is the approach that FFmpeg used to use, but I went and derived it for myself after studying the default QuickTime palette table. There’s a pattern there— all of the RGB entries are comprised of combinations of 6 values — 0x00, 0x33, 0x66, 0x99, 0xCC, and 0xFF. If you mix and match these for red, green, and blue values, you come up with 6 * 6 * 6 = 216 different colors. This happens to be identical to the web-safe color palette.

  The first (0th) entry in the table is (FF, FF, FF), followed by (FF, FF, CC), (FF, FF, 99), and on down to (FF, FF, 00) when the green component gets knocked down and step and the next color is (FF, CC, FF). The first 36 palette entries in the table all have a red component of 0xFF. Thus, if an input RGB pixel has a red color closest to 0xFF, it must map to one of those first 36 entries.

  I created a table which maps indices 0..215 to values from 5..0. Each of the R, G, and B components of an input pixel are used to index into this table and derive 3 indices ri, gi, and bi. Finally, the index into the palette table is given by :

    index = ri * 36 + gi * 6 + bi
  

  For example, the pixel (0xFE, 0xFE, 0x01) would yield ri, gi, and bi values of 0, 0, and 5. Therefore :

    index = 0 * 36 + 0 * 6 + 5
  

  The palette index is 5, which maps to color (0xFF, 0xFF, 0x00).

  Validation
  So I was pretty pleased with myself for coming up with that. Now, ideally, swapping out one algorithm for another in my SMC encoder should yield identical results. That wasn’t the case, initially.

  One problem is that the regulation QuickTime palette actually has 40 more entries above and beyond the typical 216-entry color cube (rounding out the grand total of 256 colors). Thus, using the distance approach with the full default table provides for a little more accuracy.

  However, there still seems to be a problem. Let’s check our old standby, the Big Buck Bunny logo image :

  
  
  Distance approach using the full 256-color QuickTime default palette
  
  
  Distance approach using the 216-color palette
  
  
  Table lookup approach using the 216-color palette
  

  I can’t quite account for that big red splotch there. That’s the most notable difference between images 1 and 2 and the only visible difference between images 2 and 3.

  To prove to myself that the distance approach is equivalent to the table approach, I wrote a Python script to iterate through all possible RGB combinations and verify the equivalence. If you’re not up on your base 2 math, that’s 2²⁴ or 16,777,216 colors to run through. I used Python’s multiprocessing module to great effect and really maximized a Core i7 CPU with 8 hardware threads.

  So I’m confident that the palette conversion techniques are sound. The red spot is probably attributable to a bug in my WIP SMC encoder.

  Source Code
  Update August 23, 2011 : Here’s the Python code I used for proving equivalence between the 2 approaches. In terms of leveraging multiple CPUs, it’s possibly the best program I have written to date.

  PLAIN TEXT

  PYTHON :

  1. # !/usr/bin/python
  2.  
  3. from multiprocessing import Pool
  4.  
  5. palette = []
  6. pal8_table = []
  7.  
  8. def process_r(r) :
  9.  counts = []
  10.  
  11.  for i in xrange(216) :
  12.   counts.append(0)
  13.  
  14.  print "r = %d" % (r)
  15.  for g in xrange(256) :
  16.   for b in xrange(256) :
  17.    min_dsqrd = 0xFFFFFFFF
  18.    best_index = 0
  19.    for i in xrange(len(palette)) :
  20.     dr = palette[i][0] - r
  21.     dg = palette[i][1] - g
  22.     db = palette[i][2] - b
  23.     dsqrd = dr * dr + dg * dg + db * db
  24.     if dsqrd <min_dsqrd :
  25.      min_dsqrd = dsqrd
  26.      best_index = i
  27.    counts[best_index] += 1
  28.  
  29.    # check if the distance approach deviates from the table-based approach
  30.    i = best_index
  31.    r = palette[i][0]
  32.    g = palette[i][1]
  33.    b = palette[i][2]
  34.    ri = pal8_table[r]
  35.    gi = pal8_table[g]
  36.    bi = pal8_table[b]
  37.    table_index = ri * 36 + gi * 6 + bi ;
  38.    if table_index != best_index :
  39.     print "(0x%02X 0x%02X 0x%02X) : distance index = %d, table index = %d" % (r, g, b, best_index, table_index)
  40.  
  41.  return counts
  42.  
  43. if __name__ == ’__main__’ :
  44.  counts = []
  45.  for i in xrange(216) :
  46.   counts.append(0)
  47.  
  48.  # initialize reference palette
  49.  color_steps = [ 0xFF, 0xCC, 0x99, 0x66, 0x33, 0x00 ]
  50.  for r in color_steps :
  51.   for g in color_steps :
  52.    for b in color_steps :
  53.     palette.append([r, g, b])
  54.  
  55.  # initialize palette conversion table
  56.  for i in range(0, 26) :
  57.   pal8_table.append(5)
  58.  for i in range(26, 77) :
  59.   pal8_table.append(4)
  60.  for i in range(77, 128) :
  61.   pal8_table.append(3)
  62.  for i in range(128, 179) :
  63.   pal8_table.append(2)
  64.  for i in range(179, 230) :
  65.   pal8_table.append(1)
  66.  for i in range(230, 256) :
  67.   pal8_table.append(0)
  68.  
  69.  # create a pool of worker threads and break up the overall job
  70.  pool = Pool()
  71.  it = pool.imap_unordered(process_r, range(256))
  72.  try :
  73.   while 1 :
  74.    partial_counts = it.next()
  75.    for i in xrange(216) :
  76.     counts[i] += partial_counts[i]
  77.  except StopIteration :
  78.   pass
  79.  
  80.  print "index, count, red, green, blue"
  81.  for i in xrange(len(counts)) :
  82.   print "%d, %d, %d, %d, %d" % (i, counts[i], palette[i][0], palette[i][1], palette[i][2])

• The 11th Hour RoQ Variation

  12 avril 2012, par Multimedia Mike — Game Hacking, dreamroq, Reverse Engineering, roq, Vector Quantization

  I have been looking at the RoQ file format almost as long as I have been doing practical multimedia hacking. However, I have never figured out how the RoQ format works on The 11th Hour, which was the game for which the RoQ format was initially developed. When I procured the game years ago, I remember finding what appeared to be RoQ files and shoving them through the open source decoders but not getting the right images out.

  I decided to dust off that old copy of The 11th Hour and have another go at it.

  
  
  

  Baseline
  The game consists of 4 CD-ROMs. Each disc has a media/ directory that has a series of files bearing the extension .gjd, likely the initials of one Graeme J. Devine. These are resource files which are merely headerless concatenations of other files. Thus, at first glance, one file might appear to be a single RoQ file. So that’s the source of some of the difficulty : Sending an apparent RoQ .gjd file through a RoQ player will often cause the program to complain when it encounters the header of another RoQ file.

  I have uploaded some samples to the usual place.

  However, even the frames that a player can decode (before encountering a file boundary within the resource file) look wrong.

  Investigating Codebooks Using dreamroq
  I wrote dreamroq last year– an independent RoQ playback library targeted towards embedded systems. I aimed it at a gjd file and quickly hit a codebook error.

  RoQ is a vector quantizer video codec that maintains a codebook of 256 2×2 pixel vectors. In the Quake III and later RoQ files, these are transported using a YUV 4:2:0 colorspace– 4 Y samples, a U sample, and a V sample to represent 4 pixels. This totals 6 bytes per vector. A RoQ codebook chunk contains a field that indicates the number of 2×2 vectors as well as the number of 4×4 vectors. The latter vectors are each comprised of 4 2×2 vectors.

  Thus, the total size of a codebook chunk ought to be (# of 2×2 vectors) * 6 + (# of 4×4 vectors) * 4.

  However, this is not the case with The 11th Hour RoQ files.

  Longer Codebooks And Mystery Colorspace
  Juggling the numbers for a few of the codebook chunks, I empirically determined that the 2×2 vectors are represented by 10 bytes instead of 6. Now I need to determine what exactly these 10 bytes represent.

  I should note that I suspect that everything else about these files lines up with successive generations of the format. For example if a file has 640×320 resolution, that amounts to 40×20 macroblocks. dreamroq iterates through 40×20 8×8 blocks and precisely exhausts the VQ bitstream. So that all looks valid. I’m just puzzled on the codebook format.

  Here is an example codebook dump :
  

  ID 0x1002, len = 0x0000014C, args = 0x1C0D
    0 : 00 00 00 00 00 00 00 00 80 80
    1 : 08 07 00 00 1F 5B 00 00 7E 81
    2 : 00 00 15 0F 00 00 40 3B 7F 84
    3 : 00 00 00 00 3A 5F 18 13 7E 84
    4 : 00 00 00 00 3B 63 1B 17 7E 85
    5 : 18 13 00 00 3C 63 00 00 7E 88
    6 : 00 00 00 00 00 00 59 3B 7F 81
    7 : 00 00 56 23 00 00 61 2B 80 80
    8 : 00 00 2F 13 00 00 79 63 81 83
    9 : 00 00 00 00 5E 3F AC 9B 7E 81
    10 : 1B 17 00 00 B6 EF 77 AB 7E 85
    11 : 2E 43 00 00 C1 F7 75 AF 7D 88
    12 : 6A AB 28 5F B6 B3 8C B3 80 8A
    13 : 86 BF 0A 03 D5 FF 3A 5F 7C 8C
    14 : 00 00 9E 6B AB 97 F5 EF 7F 80
    15 : 86 73 C8 CB B6 B7 B7 B7 85 8B
    16 : 31 17 84 6B E7 EF FF FF 7E 81
    17 : 79 AF 3B 5F FC FF E2 FF 7D 87
    18 : DC FF AE EF B3 B3 B8 B3 85 8B
    19 : EF FF F5 FF BA B7 B6 B7 88 8B
    20 : F8 FF F7 FF B3 B7 B7 B7 88 8B
    21 : FB FF FB FF B8 B3 B4 B3 85 88
    22 : F7 FF F7 FF B7 B7 B9 B7 87 8B
    23 : FD FF FE FF B9 B7 BB B7 85 8A
    24 : E4 FF B7 EF FF FF FF FF 7F 83
    25 : FF FF AC EB FF FF FC FF 7F 83
    26 : CC C7 F7 FF FF FF FF FF 7F 81
    27 : FF FF FE FF FF FF FF FF 80 80
  

  Note that 0x14C (the chunk size) = 332, 0x1C and 0x0D (the chunk arguments — count of 2×2 and 4×4 vectors, respectively) are 28 and 13. 28 * 10 + 13 * 4 = 332, so the numbers check out.

  Do you see any patterns in the codebook ? Here are some things I tried :

  • Treating the last 2 bytes as U & V and treating the first 4 as the 4 Y samples :
    
    
    
  • Treating the last 2 bytes as U & V and treating the first 8 as 4 16-bit little-endian Y samples :
    
    
    
  • Disregarding the final 2 bytes and treating the first 8 bytes as 4 RGB565 pixels (both little- and big-endian, respectively, shown here) :
    
    
    
  • Based on the type of data I’m seeing in these movies (which appears to be intended as overlays), I figured that some of these bits might indicate transparency ; here is 15-bit big-endian RGB which disregards the top bit of each pixel :
    
    
    

  These images are taken from the uploaded sample bdpuz.gjd, apparently a component of the puzzle represented in this screenshot.

  Unseen Types
  It has long been rumored that early RoQ files could contain JPEG images. I finally found one such specimen. One of the files bundled early in the uploaded fhpuz.gjd sample contains a JPEG frame. It’s a standard JFIF file and can easily be decoded after separating the bytes from the resource using ‘dd’. JPEGs serve as intraframes in the coding scheme, with successive RoQ frames moving objects on top.

  However, a new chunk type showed up as well, one identified by 0×1030. I have never encountered this type. Where could I possibly find data about this ? Fortunately, iD Games recently posted all of their open sourced games at Github. Reading through the code for their official RoQ decoder, I see that this is called a RoQ_PACKET. The name and the code behind it are both supremely unhelpful. The code is basically a no-op. The payloads of the various RoQ_PACKETs from one sample are observed to be either 8784, 14752, or 14760 bytes in length. It’s very likely that this serves the same purpose as the JPEG intraframes.

  Other Tidbits
  I read through the readme.txt on the first game disc and found this nugget :

          g)      Animations displayed normally or in SPOOKY MODE
                  SPOOKY MODE is blue-tinted grayscale with color cursors, puzzle
  
                  and game pieces.  It is the preferred display setting of the
  
                  developers at Trilobyte.  Just for fun, try out the SPOOKY
  
                  MODE.
  

  The MobyGames screenshot page has a number of screenshots labeled as being captured in spooky mode. Color tricks ?

  Meanwhile, another twist arose as I kept tweaking dreamroq to deal with more RoQ weirdness : After modifying my dreamroq code to handle these 10-byte vectors, it eventually chokes on another codebook. These codebooks happen to have 6-byte vectors again ! Fortunately, I was already working on a scheme to automatically detect which codebook is in play (plugging the numbers into a formula and seeing which vector size checks out).

• FFMPEG Undefined Reference to 'avcodoec_open2' in C++

  12 avril 2012, par ALM865

  I have an error when compiling one of my C++ programs after updating the FFMPEG library from 0.8 to 'ffmpeg version git-2012-04-12-277f20c'

  The error I get when I make my program is as follows :

  -------- begin --------
  
  Linking: Analysing_Server
  
  ./source/Encoding_Thread.o: In function `CEncoding_Thread::do_work()':
  
  /home/Analyser/source/Encoding_Thread.cpp:155: undefined reference to `avcodec_open2'
  
  collect2: ld returned 1 exit status
  
  make: *** [Analysing_Server] Error 1

  The relevant lines of my Make file is similar to running g++ as below :

  g++ test2.cpp -lavformat -lavcodec -lavutil -D__STDC_CONSTANT_MACROS

  A stripped down version of my relevant CPP code that throws the error is :

  #include 
  
  #include  
  
  
  
  #define LOG_OUT_STREAM_BUFF_SIZE  200000
  
  
  
  
  
  extern "C"  {
  
    /* The ffmpeg library is completely written in C, so we need to tell the C++ compiler that so it links correctly. */
  
    #include "stdint.h"
  
    #include "libavcodec/avcodec.h"
  
    #include "libavutil/mathematics.h"
  
    #include "libswscale/swscale.h"
  
    #include "libavfilter/avfilter.h"
  
  
  
    int avcodec_open2(AVCodecContext *avctx, AVCodec *codec, AVDictionary **options);
  
    int avcodec_encode_video2(AVCodecContext *avctx, AVPacket *avpkt, const AVFrame *frame, int *got_packet_ptr);
  
  }
  
  
  
  uint8_t m_outbuf[2][LOG_OUT_STREAM_BUFF_SIZE];
  
  unsigned int m_out_size[2];
  
  unsigned int m_OutBuffer_ID[2];
  
  unsigned int m_Buffer_ID; /* This is just a uniqueish stamp we give to each buffer so we can tell when they change.. */
  
  
  
  AVCodecContext * m_CodecContex;
  
  AVCodec * m_codec;
  
  struct SwsContext *m_img_convert_ctx;
  
  
  
  unsigned char* m_DataBuff;
  
  
  
  int Output_Width, Output_Height;
  
  int Output_Bitrate;
  
  
  
  
  
  int main(void) {
  
    //New version of FFMPEG calls this in avcodec_register_all
  
    //avcodec_init();
  
  
  
    /* register all the codecs */
  
    avcodec_register_all();
  
  
  
    /* Initalise the encoder */
  
    m_codec = avcodec_find_encoder(CODEC_ID_MP2);
  
  
  
    if (!m_codec) {
  
      printf("Encoding codec not found\n");
  
    }
  
  
  
    /* init the pointers.. */
  
    m_CodecContex = NULL;
  
  
  
    /* Default values.. */
  
    Output_Width = 1600;
  
    Output_Height = 1200;
  
    Output_Bitrate = 600000;
  
  
  
    /* Create/setup the Codec details.. */
  
    //Changed to work with new FFMPEG
  
    m_CodecContex = avcodec_alloc_context3(m_codec);
  
    avcodec_get_context_defaults3(m_CodecContex, m_codec);
  
  
  
    /* put sample parameters */
  
    m_CodecContex->bit_rate = Output_Bitrate;
  
    /* resolution must be a multiple of two */
  
  
  
    m_CodecContex->width = Output_Width;
  
    m_CodecContex->height = Output_Height;
  
    /* frames per second */
  
    m_CodecContex->time_base= (AVRational){1,25};
  
  
  
    m_CodecContex->gop_size = 10; /* emit one intra frame every ten frames */
  
    m_CodecContex->max_b_frames=1;
  
    m_CodecContex->pix_fmt = PIX_FMT_YUV420P; /* must be YUV for encoding.. */
  
  
  
  
  
    AVDictionary * RetunedAVDic;
  
  
  
    /* open it */
  
    //Changed to work with new FFMPEG
  
    if (avcodec_open2(m_CodecContex, m_codec, &RetunedAVDic) < 0) {
  
        printf("could not open codec");
  
    }
  
  }

  Unfortunately the example under 'doc/examples/decoding_encoding.c' that comes with FFMPEG no longer works because all the functions that it uses are now depreciated. My code is based on the example code and worked fine with FFMPEG 0.8 but does not compile with the newest version of FFMPEG. I have changed some of the depreciated functions to their newer versions but it still doesn't compile.

  Does anyone know why I am getting this error ? or does anyone have a link to an example like 'doc/examples/decoding_encoding.c' using the newest version of FFMPEG ?