Recherche avancée

Sur d’autres sites (5668)

• 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])

• Adjusting The Timetable and SQL Shame

  16 août 2012, par Multimedia Mike — General, Python, sql

  My Game Music Appreciation website has a big problem that many visitors quickly notice and comment upon. The problem looks like this :

  
  
  

  The problem is that all of these songs are 2m30s in length. During the initial import process, unless a chiptune file already had curated length metadata attached, my metadata utility emitted a default play length of 150 seconds. This is not good if you want to listen to all the songs in a soundtrack without interacting with the player page, but have various short songs (think “game over” or other quick jingles) that are over in a few seconds. Such songs still pad out 150 seconds of silence.

  So I needed to correct this. Possible solutions :

  1. Manually : At first, I figured I could ask the database which songs needed fixing and listen to them to determine the proper lengths. Then I realized that there were well over 1400 games affected by this problem. This just screams “automated solution”.
  2. Automatically : Ask the database which songs need fixing and then somehow ask the computer to listen to the songs and decide their proper lengths. This sounds like a winner, provided that I can figure out how to programmatically determine if a song has “finished”.

  SQL Shame
  This play adjustment task has been on my plate for a long time. A key factor that has blocked me is that I couldn’t figure out a single SQL query to feed to the SQLite database underlying the site which would give me all the songs I needed. To be clear, it was very simple and obvious to me how to write a program that would query the database in phases to get all the information. However, I felt that it would be impure to proceed with the task unless I could figure out one giant query to get all the information.

  This always seems to come up whenever I start interacting with a database in any serious way. I call it SQL shame. This task got some traction when I got over this nagging doubt and told myself that there’s nothing wrong with the multi-step query program if it solves the problem at hand.

  Suddenly, I had a flash of inspiration about why the so-called NoSQL movement exists. Maybe there are a lot more people who don’t like trying to derive such long queries and are happy to allow other languages to pick up the slack.

  Estimating Lengths
  Anyway, my solution involved writing a Python script to iterate through all the games whose metadata was output by a certain engine (the one that makes the default play length 150 seconds). For each of those games, the script queries the song table and determines if each song is exactly 150 seconds. If it is, then go to work trying to estimate the true length.

  The forgoing paragraph describes what I figured was possible with only a single (possibly large) SQL query.

  For each song represented in the chiptune file, I ran it through a custom length estimator program. My brilliant (err, naïve) solution to the length estimation problem was to synthesize seconds of audio up to a maximum of 120 seconds (tightening up the default length just a bit) and counting how many of those seconds had all 0 samples. If the count reached 5 consecutive seconds of silence, then the estimator rewound the running length by 5 seconds and declared that to be the proper length. Update the database.

  There were about 1430 chiptune files whose songs needed updates. Some files had 1 single song. Some files had over 100. When I let the script run, it took nearly 65 minutes to process all the files. That was a single-threaded solution, of course. Even though I already had the data I needed, I wanted to try to hand at parallelizing the script. So I went to work with Python’s multiprocessing module and quickly refactored it to use all 4 CPU threads on the machine where the files live. Results :

  • Single-threaded solution : 64m42s to process corpus (22 games/minute)
  • Multi-threaded solution : 18m48s with 4 CPU threads (75 games/minute)

  More than a 3x speedup across 4 CPU threads, which is decent for a primarily CPU-bound operation.

  Epilogue
  I suspect that this task will require some refinement or manual intervention. Maybe there are songs which actually have more than 5 legitimate seconds of silence. Also, I entertained the possibility that some songs would generate very low amplitude noise rather than being perfectly silent. In that case, I could refine the script to stipulate that amplitudes below a certain threshold count as 0. Fortunately, I marked which games were modified by this method, so I can run a new script as necessary.

  SQL Schema
  Here is the schema of my SQlite3 database, for those who want to try their hand at a proper query. I am confident that it’s possible ; I just didn’t have the patience to work it out. The task is to retrieve all the rows from the games table where all of the corresponding songs in the songs table is 150000 milliseconds.
  

  sql

  < view plain text >

  1. CREATE TABLE games
  2.   (
  3.    id INTEGER PRIMARY KEY AUTOINCREMENT,
  4.    uncompressed_sha1 TEXT,
  5.    uncompressed_size INTEGER,
  6.    compressed_sha1 TEXT,
  7.    compressed_size INTEGER,
  8.    system TEXT,
  9.    game TEXT,
  10.    gme_system TEXT default NULL,
  11.    canonical_url TEXT default NULL,
  12.    extension TEXT default "gamemusicxz",
  13.    enabled INTEGER default 1,
  14.    redirect_to_id INT DEFAULT -1,
  15.    play_lengths_modified INT DEFAULT NULL) ;
  16. CREATE TABLE songs
  17.   (
  18.    game_id INTEGER,
  19.    song_number INTEGER NOT NULL,
  20.    song TEXT,
  21.    author TEXT,
  22.    copyright TEXT,
  23.    dumper TEXT,
  24.    length INTEGER,
  25.    intro_length INTEGER,
  26.    loop_length INTEGER,
  27.    play_length INTEGER,
  28.    play_order INTEGER default -1) ;
  29. CREATE TABLE tags
  30.   (
  31.    game_id INTEGER,
  32.    tag TEXT NOT NULL,
  33.    tag_type TEXT default "filename") ;
  34. CREATE INDEX gameid_index_songs ON songs(game_id) ;
  35. CREATE INDEX gameid_index_tag ON tags(game_id) ;
  36. CREATE UNIQUE INDEX sha1_index ON games(uncompressed_sha1) ;

• Different filesizes for images generated using octave and python

  22 février 2017, par Lakshay Garg

  I am using python (scikit-image) and octave to generate 200 images as follows

  Python3

  import numpy as np
  
  from skimage.io import imsave
  
  
  
  images = [255*np.ones((100,100), dtype=np.uint8),  # white
  
               np.zeros((100,100), dtype=np.uint8)]  # black
  
  
  
  for i in range(200): # save alternating black and white images
  
      imsave('%04d.png'%(i+1), images[i%2])

  Octave

  pkg load image;
  
  
  
  im1 = 255*ones(100,100); # white
  
  im2 = zeros(100,100);    # black
  
  for i=1:200
  
      name = sprintf('%04d.png', i);
  
      if mod(i,2) == 0
  
          imwrite(im1, name);
  
      else
  
          imwrite(im2, name);
  
      end
  
  end

  Next, I use ffmpeg to generate two videos (alternating white and black frames) from these two sets of images using the following command

  ffmpeg -r 10 -loglevel quiet \
  
         -i ./%04d.png -c:v libx264 \
  
         -preset ultrafast -crf 0 ./out.mkv

  1. Sizes of image files generated by both these codes are different.

     • Octave white : 192 bytes, black : 98 bytes
     • Python white : 120 bytes, black : 90 bytes

  2. Sizes of video files generated from these octave and python images are significantly different from each other.

     • Octave filesize : 60 kilobytes
     • Python filesize : 116 kilobytes

  Why do we have this apparently very strange behavior ?

  EDIT

  Since it was suggested that the behavior might be dues to octave and python using different bit-depths to store the images, I changes the octave code to use 8 bit numbers

  im1 = uint8(255*ones(100,100)); # white
  
  im2 = uint8(zeros(100,100));    # black

  and now the image file sizes are nearly the same

  • Octave white : 118 bytes, black : 90 bytes
  • Python white : 120 bytes, black : 90 bytes

  but the problem is still the same for video files, octave : 60K, python : 116K