Recherche avancée

Sur d’autres sites (11564)

• The problems with wavelets

  27 février 2010, par Dark Shikari — DCT, Dirac, Snow, psychovisual optimizations, wavelets

  I have periodically noted in this blog and elsewhere various problems with wavelet compression, but many readers have requested that I write a more detailed post about it, so here it is.

  Wavelets have been researched for quite some time as a replacement for the standard discrete cosine transform used in most modern video compression. Their methodology is basically opposite : each coefficient in a DCT represents a constant pattern applied to the whole block, while each coefficient in a wavelet transform represents a single, localized pattern applied to a section of the block. Accordingly, wavelet transforms are usually very large with the intention of taking advantage of large-scale redundancy in an image. DCTs are usually quite small and are intended to cover areas of roughly uniform patterns and complexity.

  Both are complete transforms, offering equally accurate frequency-domain representations of pixel data. I won’t go into the mathematical details of each here ; the real question is whether one offers better compression opportunities for real-world video.

  DCT transforms, though it isn’t mathematically required, are usually found as block transforms, handling a single sharp-edged block of data. Accordingly, they usually need a deblocking filter to smooth the edges between DCT blocks. Wavelet transforms typically overlap, avoiding such a need. But because wavelets don’t cover a sharp-edged block of data, they don’t compress well when the predicted data is in the form of blocks.

  Thus motion compensation is usually performed as overlapped-block motion compensation (OBMC), in which every pixel is calculated by performing the motion compensation of a number of blocks and averaging the result based on the distance of those blocks from the current pixel. Another option, which can be combined with OBMC, is “mesh MC“, where every pixel gets its own motion vector, which is a weighted average of the closest nearby motion vectors. The end result of either is the elimination of sharp edges between blocks and better prediction, at the cost of greatly increased CPU requirements. For an overlap factor of 2, it’s 4 times the amount of motion compensation, plus the averaging step. With mesh MC, it’s even worse, with SIMD optimizations becoming nearly impossible.

  At this point, it would seem wavelets would have pretty big advantages : when used with OBMC, they have better inter prediction, eliminate the need for deblocking, and take advantage of larger-scale correlations. Why then hasn’t everyone switched over to wavelets then ? Dirac and Snow offer modern implementations. Yet despite decades of research, wavelets have consistently disappointed for image and video compression. It turns out there are a lot of serious practical issues with wavelets, many of which are open problems.

  1. No known method exists for efficient intra coding. H.264′s spatial intra prediction is extraordinarily powerful, but relies on knowing the exact decoded pixels to the top and left of the current block. Since there is no such boundary in overlapped-wavelet coding, such prediction is impossible. Newer intra prediction methods, such as markov-chain intra prediction, also seem to require an H.264-like situation with exactly-known neighboring pixels. Intra coding in wavelets is in the same state that DCT intra coding was in 20 years ago : the best known method was to simply transform the block with no prediction at all besides DC. NB : as described by Pengvado in the comments, the switching between inter and intra coding is potentially even more costly than the inefficient intra coding.

  2. Mixing partition sizes has serious practical problems. Because the overlap between two motion partitions depends on the partitions’ size, mixing block sizes becomes quite difficult to define. While in H.264 an smaller partition always gives equal or better compression than a larger one when one ignores the extra overhead, it is actually possible for a larger partition to win when using OBMC due to the larger overlap. All of this makes both the problem of defining the result of mixed block sizes and making decisions about them very difficult.

  Both Snow and Dirac offer variable block size, but the overlap amount is constant ; larger blocks serve only to save bits on motion vectors, not offer better overlap characteristics.

  3. Lack of spatial adaptive quantization. As shown in x264 with VAQ, and correspondingly in HCEnc’s implementation and Theora’s recent implementation, spatial adaptive quantization has staggeringly impressive (before, after) effects on visual quality. Only Dirac seems to have such a feature, and the encoder doesn’t even use it. No other wavelet formats (Snow, JPEG2K, etc) seem to have such a feature. This results in serious blurring problems in areas with subtle texture (as in the comparison below).

  4. Wavelets don’t seem to code visual energy effectively. Remember that a single coefficient in a DCT represents a pattern which applies across an entire block : this makes it very easy to create apparent “detail” with a DCT. Furthermore, the sharp edges of DCT blocks, despite being an apparent weakness, often result in a “fake sharpness” that can actually improve the visual appearance of videos, as was seen with Xvid. Thus wavelet codecs have a tendency to look much blurrier than DCT-based codecs, but since PSNR likes blur, this is often seen as a benefit during video compression research. Some of the consequences of these factors can be seen in this comparison ; somewhat outdated and not general-case, but which very effectively shows the difference in how wavelets handle sharp edges and subtle textures.

  Another problem that periodically crops up is the visual aliasing that tends to be associated with wavelets at lower bitrates. Standard wavelets effectively consist of a recursive function that upscales the coefficients coded by the previous level by a factor of 2 and then adds a new set of coefficients. If the upscaling algorithm is naive — as it often is, for the sake of speed — the result can look quite ugly, as if parts of the image were coded at a lower resolution and then badly scaled up. Of course, it looks like that because they were coded at a lower resolution and then badly scaled up.

  JPEG2000 is a classic example of wavelet failure : despite having more advanced entropy coding, being designed much later than JPEG, being much more computationally intensive, and having much better PSNR, comparisons have consistently shown it to be visually worse than JPEG at sane filesizes. Here’s an example from Wikipedia. By comparison, H.264′s intra coding, when used for still image compression, can beat JPEG by a factor of 2 or more (I’ll make a post on this later). With the various advancements in DCT intra coding since H.264, I suspect that a state-of-the-art DCT compressor could win by an even larger factor.

  Despite the promised benefits of wavelets, a wavelet encoder even close to competitive with x264 has yet to be created. With some tests even showing Dirac losing to Theora in visual comparisons, it’s clear that many problems remain to be solved before wavelets can eliminate the ugliness of block-based transforms once and for all.

• Taking submissions for encoder comparison

  8 mai 2010, par Dark Shikari — Uncategorized

  With VP8 supposedly going to come out in about 2 weeks, it’s time to get a rough idea as to the visual state of the art in terms of encoders. Accordingly, I’m doing a small visual codec comparison in which we will take a few dozen encoders, encode a single test clip, and perform score-based visual tests on real humans using a blind test. There will be no PSNR or SSIM results posted.

  See the doom9 thread for more information and feel free to submit streams for your own encoders. I’m particularly interested in some newer proprietary encoders for which I wouldn’t be able to get the software for due to NDAs or similar (such as VP8, Sony Blu-code, etc) — but for which I would be able to get a dump of the decoded output.

• Monster Battery Power Revisited

  28 mai 2010, par Multimedia Mike — Python, Science Projects

  So I have this new fat netbook battery and I performed an experiment to determine how long it really lasts. In my last post on the matter, it was suggested that I should rely on the information that gnome-power-manager is giving me. However, I have rarely seen GPM report more than about 2 hours of charge ; even on a full battery, it only reports 3h25m when I profiled it as lasting over 5 hours in my typical use. So I started digging to understand how GPM gets its numbers and determine if, perhaps, it’s not getting accurate data from the system.

  I started poking around /proc for the data I wanted. You can learn a lot in /proc as long as you know the right question to ask. I had to remember what the power subsystem is called — ACPI — and this led me to /proc/acpi/battery/BAT0/state which has data such as :

  present :                 yes
  capacity state :          ok
  charging state :          charged
  present rate :            unknown
  remaining capacity :      100 mAh
  present voltage :         8326 mV
  

  "Remaining capacity" rated in mAh is a little odd ; I would later determine that this should actually be expressed as a percentage (i.e., 100% charge at the time of this reading). Examining the GPM source code, it seems to determine as a function of the current CPU load (queried via /proc/stat) and the battery state queried via a facility called devicekit. I couldn’t immediately find any source code to the latter but I was able to install a utility called ’devkit-power’. Mostly, it appears to rehash data already found in the above /proc file.

  Curiously, the file /proc/acpi/battery/BAT0/info, which displays essential information about the battery, reports the design capacity of my battery as only 4400 mAh which is true for the original battery ; the new monster battery is supposed to be 10400 mAh. I can imagine that all of these data points could be conspiring to under-report my remaining battery life.

  Science project : Repeat the previous power-related science project but also parse and track the remaining capacity and present voltage fields from the battery state proc file.

  Let’s skip straight to the results (which are consistent with my last set of results in terms of longevity) :

  
  
  

  So there is definitely something strange going on with the reporting— the 4400 mAh battery reports discharge at a linear rate while the 10400 mAh battery reports precipitous dropoff after 60%.

  Another curious item is that my script broke at first when there was 20% power remaining which, as you can imagine, is a really annoying time to discover such a bug. At that point, the "time to empty" reported by devkit-power jumped from 0 seconds to 20 hours (the first state change observed for that field).

  Here’s my script, this time elevated from Bash script to Python. It requires xdotool and devkit-power to be installed (both should be available in the package manager for a distro).
  

  PLAIN TEXT

  PYTHON :

  1. # !/usr/bin/python
  2.  
  3. import commands
  4. import random
  5. import sys
  6. import time
  7.  
  8. XDOTOOL = "/usr/bin/xdotool"
  9. BATTERY_STATE = "/proc/acpi/battery/BAT0/state"
  10. DEVKIT_POWER = "/usr/bin/devkit-power -i /org/freedesktop/DeviceKit/Power/devices/battery_BAT0"
  11.  
  12. print "count, unixtime, proc_remaining_capacity, proc_present_voltage, devkit_percentage, devkit_voltage"
  13.  
  14. count = 0
  15. while 1 :
  16.   commands.getstatusoutput("%s mousemove %d %d" % (XDOTOOL, random.randrange(0,800), random.randrange(0, 480)))
  17.   battery_state = open(BATTERY_STATE).read().splitlines()
  18.   for line in battery_state :
  19.     if line.startswith("remaining capacity :") :
  20.       proc_remaining_capacity = int(line.lstrip("remaining capacity : ").rstrip("mAh"))
  21.     elif line.startswith("present voltage :") :
  22.       proc_present_voltage = int(line.lstrip("present voltage : ").rstrip("mV"))
  23.   devkit_state = commands.getoutput(DEVKIT_POWER).splitlines()
  24.   for line in devkit_state :
  25.     line = line.strip()
  26.     if line.startswith("percentage :") :
  27.       devkit_percentage = int(line.lstrip("percentage :").rstrip(’\%’))
  28.     elif line.startswith("voltage :") :
  29.       devkit_voltage = float(line.lstrip("voltage :").rstrip(’V’)) * 1000
  30.   print "%d, %d, %d, %d, %d, %d" % (count, time.time(), proc_remaining_capacity, proc_present_voltage, devkit_percentage, devkit_voltage)
  31.   sys.stdout.flush()
  32.   time.sleep(60)
  33.   count += 1