Older posts Newer posts |
Recursive algebraic types in D
September 15, 2014
One of the things D programming language seemingly lacks is support for algebraic data types
and pattern matching on them. This is a very convenient kind of types which most functional
languages have built-in (as well as modern imperative ones like Rust or Haxe). There were
some attempts at making algebraic types on the library level in D (such as Algebraic template
in std.variant module of D's stdlib) however they totally failed their name: they don't support
recursion and hence are not algrabraic at all, they are sum types at best. What follows is
a brief explanation of the topic and a proof of concept implementation of recursive algebraic
types in D.
On Robin Hood hashing
September 13, 2014
Recently I played a bit with Robin Hood hashing, a variant of open addressing
hash table. Open addressing means we store all data (key-value pairs) in one big
array, no linked lists involved. To find a value by key we calculate hash for the key,
map it onto the array index range, and from this initial position we start to wander.
In the simplest case called Linear Probing we just walk right from the initial position
until we find our key or an empty slot which means this key is absent from the table.
If we want to add a new key-value pair we find the initial position similarly and
walk right until an empty slot is found, here the key-value pair gets stored.
Robin Hood hashing is usually described as follows. It's like linear probing,
to add a key we walk right from its initial position (determined by key's hash)
but during the walk we look at hash values of the keys stored in the table
and if we find
a "rich guy", a key whose Distance from Initial Bucket (DIB) a.k.a. Path
from Starting Location (PSL) a.k.a. Probe Count is less than the distance we've
just walked searching, then we swap our new key-value pair with this rich guy
and continue the process of walking right with the intention to find a place
for this guy we just robbed, using the same technique. This approach decreases
number of "poors", i.e. keys living too far from their initial positions and
hence requiring a lot of time to find them.
When our array is large and keys are scarce, and a good hashing function distributed
them evenly so that each key lives where its hash suggests (i.e. at its initial
position) then everything is trivial and there's no difference between linear probing
and Robin Hood. Interesting things start to happen when several keys have the same
initial position (due to hash collisions), and this starts to happen very quickly -
see the Birthday Problem. Clusters start to appear - long runs of consecutive
non-empty array slots.
For the sake of simplicity let's take somewhat exaggerated
and unrealistic case that however allows to get a good intuition of what's happening.
Imagine that when mapping hashes to array index space 200 keys landed onto [0..100]
interval while none landed onto [100..200]. Then in the case of linear probing it
will look like this:
D as a scripting language
September 12, 2014
Many of us encounter small tasks involving some file operations, text processing and
running other processes. These are usually solved using either shell or glue
languages (often called scripting languages because of this) like Python, Perl
or Ruby. Compiled statically typed languages are rarely used in such cases
because popular ones usually require too much effort to write and run a simple
script. However some static languages can actually be used here easily instead
of scripting ones, providing their usual benefits such as checking for types and
typos. Here's an example of using D in such scenario.
Earlier this year I discovered a nice tool called
TimeSnapper that sits in background
and saves everything that happens on your screen by doing screenshots on regular
time intervals. It can also collect some stats about apps you run and sites you
browse. During first month I used this feature in the demo version and proved
my suspicion that I waste way too much time on reddit and LiveJournal. ;) Later I
switched to free version of TimeSnapper that doesn't collect and report stats
but just makes the screenshots and allows playing them like a video with timeline.
This serves me as a precise visual memory so that later I can always see what happened
at certain moments. Found a weird unwanted shortcut on my desktop, what app placed it
here? Quick look at its creation time, replay what I was doing then, ah, here's
the thing I was installing at that moment. Here's a library I built on day X, but in
which project was I using it? Replay that hour, see the opened project, ah, now I
Special treatment for Deshaker
May 27, 2014
There is a nice filter for VirtualDub (supported by Video Enhancer) called Deshaker
by Gunnar Thalin which can stabilize shaky video. This filter is different from the others
because it works in two passes: first it needs to see the whole video and analyze it
(without producing a meaningful video result yet), and on the second pass it uses collected
data to actually fix the video. The data collected in first pass is stored in a file
which can be specified in filter's options. If you start analyzing another file
previously collected data is erased. This means up to recently Deshaker could not be used
in Video Enhancer's batch mode where you select many files and apply a sequence of filters
to all of them. Because in that filter sequence Deshaker will be configured for either first
or the second pass while each file requires going through both passes one right after another.
To fix this issue we've added in Video Enhancer 1.9.10 special treatment for Deshaker:
when you start processing some video file and your sequence of filters contains Deshaker
then Video Enhancer first makes one pass in preview (without compression and writing to disk)
and then immediately processes the file
again but this time automatically switching Deshaker to second pass. And if you're processing
a bunch of files then this approach applies to each of them: for each file Video Enhancer
will do two passes: quick preview with Deshaker in first pass then actual processing with
Deshaker in second pass.
Of course, if your chain of filters does not contain Deshaker then Video Enhancer works
as usual: just one pass for each file.
New Super Resolution is ready.
December 13, 2013
This year we explored ways to accelerate and improve our Super Resolution engine,
and overall research, development and testing took much more time than we anticipated
but finally the new engine is available to our users. Today we're releasing it in
a form of VirtualDub plugin. DirectShow filter
is also ready, so after we change Video Enhancer to use the new version there
will be an update for Video Enhancer too. Also, an AviSynth plugin will be released soon.
Our advances in speed allow using it in video players to upsize videos to HD in
real time on modern PCs and laptops.
Generally quality and speed depend on source video and your CPU'a abilities, but here's
an example of changes between our old VirtualDub plugin (1.0) and the new one (2.0) on
a particular file (panasonic4.avi) when upsizing from 960x540 to 1920x1080 on an old
Quad Core 2.33 GHz:
Quality, in dB of Y-PSNR (higher is better):
version old new
fast mode 41.70 42.28
slow mode 42.07 42.73
Time of upsizing 200 frames, in seconds:
version old new_rgb new_yv12
fast mode 19.6 14.4 10.3
slow mode 28.7 19.5 14.0
Version 1.0 worked only in RGB32, so for YUV the speed was about the same as for RGB.
As you may see, the new version's fast mode provides similar quality to old version's
high-quality mode but does it 2-3 times faster depending on color space. And new
version's high-quality mode is still faster than old one's fast mode.
To achieve these speed gains our SR implementation was rewritten from scratch
to work block-wise instead of frame-wise. This way it doesn't need so much memory
to store intermediate results and intermediate data never leaves CPU cache,
avoiding spending so much time on memory loads and stores. Also, we learned to
use SSE2 vector operations better. Unfortunately even in 2013 compilers
still generally suck at vectorizing code, so it requires a lot of manual work.
tags: video_enhancer super_resolution
Working with raw video data in C# with DirectShow
October 19, 2013
Too many questions arising on different forums and emails I see revolve around
one theme: how do I access actual video data in a DirectShow app? People want to
save images from their web cams, draw something in the video, analyse it, etc.
But in DirectShow direct work with raw data is encapsulated and hidden inside filters,
the building blocks out of which we build DirectShow graphs. So when dealing with DirectShow
we've got a bunch of filters on our hands and we tell them what to do but we don't
get the actual raw bytes of audio/video data, hence multiple questions, because there
isn't always a suitable filter that does exactly what you need. In some cases we're forced
to create our own filter, but that may be rather complicated and tedious. However many
cases can be solved by using one standard filter which is part of DirectShow itself:
Here's an example of using it to implement a video effect and apply it to a stream of video
from a web camera.
This short tutorial will basically repeat my previous post but this time we'll use C#
instead of C++.
Accessing raw video data in DirectShow
October 18, 2013
In DirectShow one makes multimedia apps by building graphs where nodes (called filters)
process the data (capture or read, convert, compress, write etc.) and graph's edges are streams
of multimedia samples (video frames, chunks of audio, etc.). All the work with raw data
takes place inside the filters, and the host application usually doesn't deal with video/audio
data directly, it only arranges the filters in a graph telling them what to do. This is fine
for some typical tasks when you've got all necessary filters, but sometimes there is no ready
made filter for your task and then you need to create your own filter which may be rather
tedious and complicated. However there are many cases when you only want to peek at the data,
analyse or save some part of it, you don't want a transform that changes media type, so making
your own filter is an overkill. There is a nice standard filter in DirectShow which can
give you access to raw video data (let's stick with just video for now) without creating
your own filters, it's called
MSDN says it's deprecated, but this filter is still available in all versions of Windows
including Windows 8. Even if it goes away some time in the future, recreating it will be very
easy, so your program will not need to change.
In this little tutorial I'll show how to make a small DirectShow app in C++ which takes video
stream from USB camera, applies a simple video effect (accessing raw video data) and shows it
on screen. The idea is simple: make a graph where video stream flows from the camera through
sample grabber to a video renderer. Each time a frame passes the sample grabber it calls my
callback where I manipulate with raw video data before it's sent down the stream for
Status report and plans
September 21, 2013
It's been a while since last Video Enhancer version was released. It's time to
break the silence and reveal some news and plans.
Part of the passed year
was spent on ScreenPressor-related projects for our corporate clients.
But for last several months we've been cooking our new super resolution engine.
It's not on GPU yet but we've found a way to accelerate it on CPU and use
significantly less memory. Actually, reducing memory usage is the key to
acceletarion: nowadays memory access is quite slow compared to computations,
and if you compute everything locally in small chunks that fit into cache
and don't store and read whole frames in memory several times, overall process
gets much faster. For us that meant a complete rewrite of our super resolution
engine, and this is what we did. While remaking the algorithm we had a chance
to rethink many decisions baked into it. Additional CPU cycles freed by
the acceleration could be spent to perform more computations and reach for
higher quality. So we spent several months in research: what motion estimation
method works best for our SR? Shall we work in blocks of size 16, 8 or even 4
pixels wide (the latter meaning just 2x2 blocks of original image)?
Which precision to use for each block size? What is the right way
to combine new frame with accumulated information? For motion estimation we
actually tried it all: using source code generation we generated 160 different
implementations of motion estimation and measured how well they performed
in terms of quality and speed. It turned out usual metrics for selecting
best motion compensation methods in video codecs and other applications do
not give the best results for super resolution: minimizing difference between
compensated and current frame (which works best for compression) doesn't
provide best quality in SR when compensated frame gets fused with input
frame to produce the new upsized image. Then the fusion: is our old method
really good or maybe it can be improved? We used machine learning techniques
to find the best fusion function. And found that actually it depends a lot
on source video: what works best for one video doesn't necessarily work well
for another video. We chose a weighted average for a selected set of HD videos
which means quality of the new SR engine should be higher on some videos
and possibly a bit lower on some other videos, it won't be universally
Now what it all means in terms of releases. The new SR engine is in final
testing stage now and it's a matter of days before it's released in
Video Enhancer 1.9.9 and new version of our Super Resolution plugin for
VirtualDub. Then it will also be released as AviSynth plugin, for the first
time. And then finally it will come as Adobe After Effects (and Premiere Pro,
probably) plugin. Some years ago we offered this Premiere Pro & After Effects
plugin but it hadn't updated for too long and became obsolete, current
versions of these Adobe hosts are 64-bit and cannot run our old 32-bit plugin.
Video Enhancer 1.9.9 will be a free update, and it's going to be the last
1.x version. Next release will be version 2.0 with completely different
user interface, where all effects will be visible instantly. Imagine
"Photoshop for video". Update to 2.0 will be free for those who purchased
Video Enhancer 1.9.6 or later.
We hope everything mentioned above will see the light this year.
VE 1.9.9 in September, plugins in October, VE 2.0 later.
Update: oops, our scheduling sucks as usual. YUV support and thorough
testing took much more time, the releases postponed until December.
tags: video_enhancer super_resolution
Writing AVI files with x264
Seprember 26, 2012
x264 is an excellent video codec implementing H.264 video compression standard.
One source of its ability to greatly compress video is allowing a compressed
frame to refer to several frames not only in the past but also in the future:
refer to frames following the current one. Such frames are called B-frames (bidirectional),
and even previous generation of video codecs, MPEG4 ASP (like XviD), had this feature,
so it's not particularly new. However AVI file format and Video-for-Windows (VfW)
subsystem predate those, and are designed to work strictly sequentially: frames
are compressed and decomressed in strict order one by one, so a frame can only
use some previous frames to refer to. Such frames are called P-frames (predicted).
reason AVI format does not really suit MPEG4 and H.264 video. However with some
tricks (or should I say hacks) it is still possible to write MPEG4 or H.264 stream
to AVI file, and this is what VfW codecs like XviD and x264vfw do. They buffer some
frames and then output compressed frames with some delay, sometimes combining P and B
frames in single chunks. Appropriate decoder knows this trick and restores proper
frame order so everything works fine.
Some time ago we received a complaint from a user of Video Enhancer about x264vfw:
video compressed with this codec to AVI file showed black screen when started playing
and only after jumping forward a few seconds it started to play, but with sound out
of sync. To investigate the issue I made a graph in GraphEditPlus where some video
was compressed with x264vfw and then written to an AVI file. But I also inserted
a Sample Grabber right after the compressor to see what it outputs. Here's what I got:
click to enlarge
It turned out for some reason x264vfw spitted ~50 empty frames, 1 byte in size each,
all marked as delta (P) frames. After those ~50 frames came first key frame and then
normal P frames of sane sizes followed. Those 50 empty frames which were not started
with a key frame (like it is expected to be in AVI file) created the effect: black
screen when just started playing and audio sync issue. I don't know in what version
of x264vfw this behavior started but it's really problematic for writing AVI files.
Fortunately, the solution is very simple. If you open configuration dialog of
x264vfw you can find "Zero Latency" check box. Check it, as well as "VirtualDub hack"
and then it will work properly: will start sending sane data from the first frame,
and resulting AVI file will play fine.
tags: video_enhancer directshow
Buggy VirtualDub filters
August 16, 2012
The same day I was dealing with VDFilter issue described in previous post
I ran Video Enhancer (which also uses VDFilter), picked a random VirtualDub
plugin and tried to process one file. Suddenly I've got a message telling me
about an exception arised inside that VirtualDub plugin. Most VD plugins have
been here for a while and are known for thair speed, stability and high quality,
so I immediately decided the problem was in VDFilter, our DirectShow wrapper
for those plugins. I started a debug session to find what caused the exception
and luckily the source code for that plugin was available on its web page.
The plugin is called Flip 1.1 (ef_flip.vdf from the big collection of filters by
Emiliano Ferrari). To my surprise however I've found the bug quite fast and it was
not in VDFilter, this time it was in the plugin itself. Source code of the main
routine is pretty short:
void Rotate180 (Pixel32 *dst,Pixel32 *tmp,const int pitch,const int w,const int h,
const FilterFunctions *ff)
b= dst + (h*pitch);
int alf = h/2;
if (h&1) alf++;
for (int j=0; j<alf; j++)
_memcpy (tmp,a,w*sizeof(Pixel32)); // tmp= a;
for (i=0; i<w; i++) *a--= *b++; // a=b
for (i=0; i<w; i++) *b--= *tmp++; // b=tmp
if (!(h&1)) // even lines
for (i=0; i<w; i++) *a--= *tmp++;
Take a look at the two red lines. h is the image height
and pitch here is equal to the number of Pixel32 values in one row of image, so
h*pitch is the number of pixels in whole image. At first pointer b points
to dst + (h*pitch), i.e. the first byte outside the image buffer! And then
in the loop it's being read and then incremented to point even farther from the end
of the buffer. It didn't cause crashes in VirtualDub because for some reason memory
after the image buffer always belonged to the application, however it did read garbage
there so the first line of "rotated" image should contain garbage after applying this
filter. In case of VDFilter and its use in Video Enhancer one line of memory after the
image buffer not always completely belonged to the program, so for small frames it
worked ok but with a larger frame the b pointer walked too far and caused
a segmentation fault which was caught as an exception and caused our wrapper to
show the message box.
It may be the case that author assumed pitch to be a negative value, however
this assumption doesn't look correct. Here's a quote from VirtualDub Plugin SDK:
"Bitmaps can be stored top-down as well as bottom-up. The pitch value value is positive
if the image is stored bottom-up in memory and negative if the image is stored top-down.
This is only permitted if the filter declares support for flexible formats by returning
FILTERPARAM_SUPPORTS_ALTFORMATS from paramProc; otherwise, the host ensures that the
filter receives a bottom-up orientation with a positive pitch, flipping the bitmap
beforehand if necessary."
Lessons learned: 1) some VirtualDub plugins, even very simple ones, may contain bugs.
2) pointer arithmetic requires a lot of attention to be used correctly.
Older posts Newer posts