A thing or two about the Fourier Transform

Recently I have been reading up on frequency domain image processing. I am still just beginning to understand how it works. Over the last few weeks I have been trying to understand the ** Fourier Transform **. Although the gist of  Fourier Series is easy to understand from its formula, that of the Fourier Transform isn’t (to me at least). This blog post describes the Fourier Transform as I understood it, along with some helpful diagrams. I am using NumPy and matplotlib for plotting. As a reference for all the equations mentioned in this post, I am using Digital Image Processing (3rd Edition).

The Fourier Series

I haven’t done any digging into its theory, but the formula for Fourier Series is pretty straight forward. Given f has a period of T

f(t) = \sum\limits_{n=-\infty}^\infty c_{n} e^{i\frac{2 \pi n}{T}}

where

c_n = \frac{1}{T} \int\limits_{\frac{-T}{2}}^{\frac{T}{2}} f(t)e^{-i\frac{2 \pi n}{T}}

for
n = 0,\pm 1, \pm2, .....

To simplify this, we can replace \omega=\frac{2\pi}{T} . f now becomes.

f(t) = \sum\limits_{n=-\infty}^\infty  c_n e^{i \omega n}

Using Euler’s Formula

f(t) = \sum\limits_{n=-\infty}^\infty  c_n (cos(n \omega t) + i. sin(n \omega t))

We can say that, f is now exactly equal to an infinite sum of certain sines and cosines. The Wikipedia Page has some pretty nice visualizations of the concept.

The Discrete Fourier Transform

This is what took me a while to understand. The discrete fourier transform, is derived from the Fourier Transform. Given a discrete function f whose M samples have been collected, we have.

F(u) = \sum\limits_{x=0}^{M-1} f(x)e^{-i\frac{2\pi u x}{M}}

for

u = 0, 1, 2, ..., M -1

As you can see, the function f of x is transformed into the function F of u .
We can get f back by the inverse Fourier Transform

f(x) = \frac{1}{M} \sum\limits_{u=0}^{M-1} F(u)e^{i\frac{2\pi u x}{M}}
for
x = 0, 1, 2, ... , M -1

Although the relationship of f and F is mathematically proven, the underlying meaning was not immediately apparent to me. What puzzled me was, why F is computed at all, and how can it tell us anything about f . The way I looked at it to understand it better is as follows.

Let
\omega = \frac{2\pi}{M}

f(x) = \frac{1}{M} \sum\limits_{u=0}^{M-1} F(u)e^{i\omega u x}

Using Euler’s formula we have

f(x) = \frac{1}{M}[{F(0).(cos(0) + i.sin(0)) + F(1).(cos(1\omega x) + i.sin(1\omega x)) + F(2).(cos(2\omega x) + i.sin(2\omega x)) + ...} ]

From the above equation, it is clear why the Fourier Transform is important. The function F , has given us coefficients to express f as a sum of sines and cosines. I will try to demonstrate this with some code. I wrote a small helper function to help me input curves. The following function taken an image of a curve drawn in black on white and saves it into a .npy file. You will need the scikit-image library to use this.

from skimage import io, color, util
from matplotlib import pyplot as plt

pylab.rcParams['figure.figsize'] = (8.0, 8.0)

def img2curve(imgfile, arrayfile):
    """ Converts an image of a curve into numpy array and saves it"""

    img = io.imread(imgfile)
    img = color.rgb2gray(img)
    img = util.img_as_ubyte(img)
    array = np.zeros((img.shape[1], ))

    for r in range(img.shape[0]):
        for c in range(img.shape[1]):
            if img[r, c] < 128:
                array[c] = img.shape[0] - r
    np.save(arrayfile, array)

def show_curve(array):
    """ Plots real and imaginary parts of an array """

    ax = plt.subplot(111)
    ax.set_xlim(0, len(array))
    ax.set_ylim(-10, len(array))
    plt.plot(np.real(array), color='blue')
    plt.plot(np.imag(array), color='red')

Original Image

img = io.imread("curve.png")
io.imshow(img)

image

Derived Curve

img2curve("curve.png", "curve.npy")
curve = np.load("curve.npy")
show_curve(curve)

curve

If you’d like to, you can download the original image and the curve.npy file.

Computing the DFT

We will compute the discrete fourier transform using NumPy’s np.fft.fft method and observe the first 5 terms.

curve_fft = np.fft.fft(curve)
print curve_fft[:5]

curve_fft is our function F as described above. Applying the inverse transform to curve_fft should give us back curve exactly. But let’s see what happens by considering an element in F at a time. First we take only F(0) and apply the inverse transform by using np.fft.ifft.

Contribution of F(0)

t_0(x) = \frac{1}{M}[F(0).(cos(0) + i.sin(0))]

tmp = curve_fft.copy()
tmp[1:] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F0

As you can see, it is a real constant shown in blue.

Contribution of F(1)

t_1(x) = \frac{1}{M}[F(1).(cos(1\omega x) + i.sin(1\omega x))]

tmp = curve_fft.copy()
tmp[2:] = 0
tmp[0:1] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F1

Contribution of F(2)

t_2(x) = \frac{1}{M}[F(2).(cos(2\omega x) + i.sin(2\omega x))]

tmp = curve_fft.copy()
tmp[3:] = 0
tmp[0:2] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F2

Contribution of F(0), F(1) and F(2)

t_0(x) + t_1(x) + t_2(x)

tmp = curve_fft.copy()
tmp[3:] = 0

array = np.fft.ifft(tmp)
show_curve(array)

F123

As you can see the resultant curve is trying to match the original curve. The imaginary part in red, will eventually get zeroed out when all the terms of F are considered.

Fourier Transform in action

The code snippet below generates successive images of contribution of each term in F . In nth still, the blue and red lines show the real and imaginary part of the curve so far, and the dotted lines show the contribution of F(n) .

import numpy as np
from matplotlib import pyplot as plt

curve = np.load("curve.npy")
curve_fft = np.fft.fft(curve)

result = np.zeros_like(curve, dtype=np.complex)

for i in range(curve_fft.shape[0]):


    tmp = np.zeros_like(curve, dtype=np.complex)
    tmp[i] = curve_fft[i]

    tmp_curve = np.fft.ifft(tmp)
    result += tmp_curve

    fig = plt.figure()
    ax = plt.subplot(111)
    ax.set_xlim(0, len(curve))
    ax.set_ylim(-10, len(curve))

    plt.plot(np.real(result), color='blue')
    plt.plot(np.imag(result), color='red')

    plt.title("Adding F(%d)" % i)
    plt.plot(np.real(tmp_curve), 'r--', color='blue')
    plt.plot(np.imag(tmp_curve), 'r--', color='red')

    fig.savefig('out/' + str(i) + ".png")

I ran the command

avconv -f image2 -r 1 -i %d.png -r 20 fft.mp4

to generate the final video.

As I understand DFT more, I’ll keep posting. Till then, thanks for reading.

Advertisements

Normalized Cuts on Region Adjacency Graphs

In my last post I demonstrated how removing edges with high weights can leave us with a set of disconnected graphs, each of which represents a region in the image. The main drawback however was that the user had to supply a threshold. This value varied significantly depending on the context of the image. For a fully automated approach, we need an algorithm that can remove edges automatically.

The first thing that I can think of which does something useful in the above mention situation is the Minimum Cut Algorithm. It divides a graph into two parts, A and B such that the weight of the edges going from nodes in Set A to the nodes in Set B is minimum.

For the Minimum Cut algorithm to work, we need to define the weights of our Region Adjacency Graph (RAG) in such a way that similar regions have more weight. This way, removing lesser edges would leave us with the similar regions.

Getting Started

For all the examples below to work, you will need to pull from this Pull Request. The tests fail due to outdated NumPy and SciPy versions on Travis. I have also submitted a Pull Request to fix that. Just like the last post, I have a show_img function.

from skimage import graph, data, io, segmentation, color
from matplotlib import pyplot as plt
from skimage.measure import regionprops
from skimage import draw
import numpy as np


def show_img(img):

    width = img.shape[1]/75.0
    height = img.shape[0]*width/img.shape[1]
    f = plt.figure(figsize=(width, height))
    plt.imshow(img)

I have modified the display_edges function for this demo. It draws nodes in yellow. Edges with low edge weights are greener and edges with high edge weight are more red.

def display_edges(image, g):
    """Draw edges of a RAG on its image

    Returns a modified image with the edges drawn. Edges with high weight are
    drawn in red and edges with a low weight are drawn in green. Nodes are drawn
    in yellow.

    Parameters
    ----------
    image : ndarray
        The image to be drawn on.
    g : RAG
        The Region Adjacency Graph.
    threshold : float
        Only edges in `g` below `threshold` are drawn.

    Returns:
    out: ndarray
        Image with the edges drawn.
    """

    image = image.copy()
    max_weight = max([d['weight'] for x, y, d in g.edges_iter(data=True)])
    min_weight = min([d['weight'] for x, y, d in g.edges_iter(data=True)])

    for edge in g.edges_iter():
        n1, n2 = edge

        r1, c1 = map(int, rag.node[n1]['centroid'])
        r2, c2 = map(int, rag.node[n2]['centroid'])

        green = 0,1,0
        red = 1,0,0

        line  = draw.line(r1, c1, r2, c2)
        circle = draw.circle(r1,c1,2)
        norm_weight = ( g[n1][n2]['weight'] - min_weight ) / ( max_weight - min_weight )

        image[line] = norm_weight*red + (1 - norm_weight)*green
        image[circle] = 1,1,0

    return image

To see demonstrate the display_edges function, I will load an image, which just has two regions of black and white.

demo_image = io.imread('bw.png')
show_img(demo_image)

ncut_demo_6_0

Let’s compute the pre-segmenetation using the SLIC method. In addition to that, we will also use regionprops to give us the centroid of each region to aid the display_edges function.

labels = segmentation.slic(demo_image, compactness=30, n_segments=100)
labels = labels + 1  # So that no labelled region is 0 and ignored by regionprops
regions = regionprops(labels)

We will use label2rgb to replace each region with its average color. Since the image is so monotonous, the difference is hardly noticeable.

label_rgb = color.label2rgb(labels, demo_image, kind='avg')
show_img(label_rgb)

ncut_demo_10_0

We can use mark_boundaries to display region boundaries.

label_rgb = segmentation.mark_boundaries(label_rgb, labels, (0, 1, 1))
show_img(label_rgb)

ncut_demo_12_0

As mentioned earlier we need to construct a graph with similar regions having more weights between them. For this we supply the "similarity" option to rag_mean_color.

rag = graph.rag_mean_color(demo_image, labels, mode="similarity")

for region in regions:
    rag.node[region['label']]['centroid'] = region['centroid']

label_rgb = display_edges(label_rgb, rag)
show_img(label_rgb)

ncut_demo_14_0

If you notice above the black and white regions have red edges between them, i.e. they are very similar. However the edges between the black and white regions are green, indicating they are less similar.

Problems with the min cut

Consider the following graph

minumum_cut

The minimum cut approach would partition the graph as {A, B, C, D} and {E}. It has a tendency to separate out small isolated regions of the graph. This is undesirable for image segmentation as this would separate out small, relatively disconnected regions of the image. A more reasonable partition would be {A, C} and {B, D, E}. To counter this aspect of the minimum cut, we used the Normalized Cut.

The Normalized Cut

It is defined as follows
Let V be the set of all nodes and w(u,v) for u, v \in V be the edge weight between u and v

NCut(A,B) = \frac{cut(A,B)}{Assoc(A,V)} + \frac{cut(A,B)}{Assoc(B,V)}
where
cut(A,B) = \sum_{a \in A ,b \in B}{w(a,b)}

Assoc(X,V) = cut(X,V) = \sum_{x \in X ,v \in V}{w(x,v)}

With the above equation, NCut won’t be low is any of A or B is not well-connected with the rest of the graph. Consider the same graph as the last one.

ncut

We can see that minimizing the NCut gives us the expected partition, that is, {A, C} and {B, D, E}.

Normalized Cuts for Image Segmentation

The idea of using Normalized Cut for segmenting images was first suggested by Jianbo Shi and Jitendra Malik in their paper Normalized Cuts and Image Segmentation. Instead of pixels, we are considering RAGs as nodes.

The problem of finding NCut is NP-Complete. Appendix A of the paper has a proof for it. It is made tractable by an approximation explained in Section 2.1 of the paper. The function _ncut_relabel is responsible for actually carrying out the NCut. It divides the graph into two parts, such that the NCut is minimized. Then for each of the two parts, it recursively carries out the same procedure until the NCut is unstable, i.e. it evaluates to a value greater than the specified threshold. Here is a small snippet to illustrate.

img = data.coffee()

labels1 = segmentation.slic(img, compactness=30, n_segments=400)
out1 = color.label2rgb(labels1, img, kind='avg')

g = graph.rag_mean_color(img, labels1, mode='similarity')
labels2 = graph.cut_normalized(labels1, g)
out2 = color.label2rgb(labels2, img, kind='avg')

show_img(out2)

ncut_demo_28_0

NCut in Action

To observe how the NCut works, I wrote a small hack. This shows us the regions as divides by the method at every stage of recursion. The code relies on a modification in the original code, which can be seen here.

from skimage import graph, data, io, segmentation, color
from matplotlib import pyplot as plt
import os

#img = data.coffee()
os.system('rm *.png')
img = data.coffee()
#img = color.gray2rgb(img)

labels1 = segmentation.slic(img, compactness=30, n_segments=400)
out1 = color.label2rgb(labels1, img, kind='avg')

g = graph.rag_mean_color(img, labels1, mode='similarity')
labels2 = graph.cut_normalized(labels1, g)

offset = 1000
count = 1
tmp_labels = labels1.copy()
for g1,g2 in graph.graph_cut.sub_graph_list:
    for n,d in g1.nodes_iter(data=True):
        for l in d['labels']:
            tmp_labels[labels1 == l] = offset
    offset += 1
    for n,d in g2.nodes_iter(data=True):
        for l in d['labels']:
            tmp_labels[labels1 == l] = offset
    offset += 1        
    tmp_img = color.label2rgb(tmp_labels, img, kind='avg')
    io.imsave(str(count) + '.png',tmp_img)
    count += 1

The two components at each stage are stored in the form of tuples in sub_graph_list. Let’s say, the Graph was divided into A and B initially, and later A was divided into A1 and A2. The first iteration of the loop will label A and B. The second iteration will label A1, A2 and B, and so on. I used the PNGs saved and converted them into a video with avconv using the command avconv -f image2 -r 1 -i %d.png -r 20 demo.webm. GIFs would result in a loss of color, so I made webm videos. Below are a few images and their respective successive NCuts. Use Full Screen for better viewing.

Note that although there is a user supplied threshold, it does not have to vary significantly. For all the demos below, the default value is used.

Colors Image

colors

During each iteration, one region (area of the image with the same color) is split into two. A region is represented by its average color. Here’s what happens in the video

  • The image is divided into red, and the rest of the regions (gray at this point)
  • The grey is divided into a dark pink region (pink, maroon and yellow) and a
    dark green ( cyan, green and blue region ).
  • The dark green region is divided into light blue ( cyan and blue ) and the
    green region.
  • The light blue region is divided into cyan and blue
  • The dark pink region is divided into yellow and a darker pink (pink and marron
    region.
  • The darker pink region is divided into pink and maroon regions.

Coins Image

coins

   

Camera Image

camera

   

Coffee Image

coffee

   

Fruits Image

apples group fruit vegetable isolated on white

   

Baby Image ( Scaled )

baby

   

Car Image

car

scikit-image RAG Introduction

Humans possess an incredible ability to identify objects in an image. Image processing algorithms are still far behind this ability. Segmentation is the process of dividing an image into meaningful regions. All pixels belonging to a region should get a unique label in an ideal segmentation.

The current segmentation functions in scikit-image are too fine grained and fall closer to superpixel methods, providing a starting point for segmentation. Region Adjacency Graphs (RAGs) are a common data structure for many segmentation algorithms. As part of GSoC this year I am implementing RAGs for scikit-image. The current HEAD of scikit-image’s master branch contains my RAG implementation based on Networkx from my recent Pull Request. In the example below, we will see how Region Adjacency Graphs (RAGs) attempt to solve the segmentation problem.Please note that you need the latest master branch of scikit-image to run the following code.

Getting Started

We define the function show_img in preference to the standard call to imshow to set nice default size parameters.
We start with coffee, a nice fresh image of a coffee cup.

from skimage import graph, data, io, segmentation, color
from matplotlib import pyplot as plt
from skimage.measure import regionprops
from skimage import draw
import numpy as np


def show_img(img):
    width = 10.0
    height = img.shape[0]*width/img.shape[1]
    f = plt.figure(figsize=(width, height))
    plt.imshow(img)

img = data.coffee()
show_img(img)

rag_demo_2_0

Over Segmentation

We segment the image using SLIC algorithm. The SLIC algorithm will
assign a unique label to each region. This is a
localized cluster of pixels sharing some similar property, in this case their
color. The label of each pixel is stored in the labels array.

regionprops helps us compute various features of these regions. We will be
sing the centroid, purely for visualization.

labels = segmentation.slic(img, compactness=30, n_segments=400)
labels = labels + 1  # So that no labelled region is 0 and ignored by regionprops
regions = regionprops(labels)

The label2rgb function assigns a specific color to all pixels belonging to one
region (having the same label). In this case, in label_rgb each pixel is
replaces with the average RGB color of its region.

label_rgb = color.label2rgb(labels, img, kind='avg')
show_img(label_rgb)

rag_demo_6_0
Just for clarity, we use mark_boundaries to highlight the region boundaries.
You will notice the the image is divided into more regions than required. This
phenomenon is called over-segmentation.

label_rgb = segmentation.mark_boundaries(label_rgb, labels, (0, 0, 0))
show_img(label_rgb)

rag_demo_8_0

Enter, RAGs

Region Adjacency Graphs, as the name suggests represent adjacency of regions
with a graph. Each region in the image is a node in a graph. There is an edge
between every pair of adjacent regions (regions whose pixels are adjacent). The
weight of between every two nodes can be defined in a variety of ways. For this
example, we will use the difference of average color between two regions as
their edge weight. The more similar the regions, the lesser the weight between
them. Because we are using difference in mean color to compute the edge weight,
the method has been named rag_mean_color.

rag = graph.rag_mean_color(img, labels)

For our visualization, we are also adding an additional property to a node, the
coordinated of its centroid.

for region in regions:
    rag.node[region['label']]['centroid'] = region['centroid']

display_edges is a function to draw the edges of a RAG on its corresponding
image. It draws edges as green lines and centroids as yellow dots.
It also accepts an argument, thresh. We only draw edges with weight below this threshold.

def display_edges(image, g, threshold):
    """Draw edges of a RAG on its image

    Returns a modified image with the edges drawn.Edges are drawn in green
    and nodes are drawn in yellow.

    Parameters
    ----------
    image : ndarray
        The image to be drawn on.
    g : RAG
        The Region Adjacency Graph.
    threshold : float
        Only edges in `g` below `threshold` are drawn.

    Returns:
    out: ndarray
        Image with the edges drawn.
    """
    image = image.copy()
    for edge in g.edges_iter():
        n1, n2 = edge

        r1, c1 = map(int, rag.node[n1]['centroid'])
        r2, c2 = map(int, rag.node[n2]['centroid'])

        line  = draw.line(r1, c1, r2, c2)
        circle = draw.circle(r1,c1,2)

        if g[n1][n2]['weight'] < threshold :
            image[line] = 0,1,0
        image[circle] = 1,1,0

    return image

We call the function with thresh = infinity so that all edges are drawn. I
myself was surprised with the beauty of the following output.

edges_drawn_all = display_edges(label_rgb, rag, np.inf )
show_img(edges_drawn_all)

rag_demo_16_0
png

Let’s see what happens by setting thresh to 29, a value I arrived at with
some trial and error.

edges_drawn_29 = display_edges(label_rgb, rag, 29 )
show_img(edges_drawn_29)

index2

Alas, the graph is cut

As you can see above, the RAG is now divided into disconnected regions. If you
notice, the table above and to the right of the dish is one big connected
component.

Threshold Cut

The function cut_threshold removes edges below a specified threshold and then
labels a connected component as one region. Once the RAG is constructed, many similar
and more sophisticated strategies can improve the initial segmentation.

final_labels = graph.cut_threshold(labels, rag, 29)
final_label_rgb = color.label2rgb(final_labels, img, kind='avg')
show_img(final_label_rgb)

index
Not perfect, but not that bad I’d say. My next steps will be to implement better algorithms to process the RAG after the initial segmentation.These include the merging predicates mention here and N-cut.

Graph based Image Segmentation

My GSoC project this year is Graph based segmentation algorithms using region adjacency graphs. Community binding period is coming to an end. I have experimented a bit with Region Adjacency Graphs (RAGs) and Minimum Spanning Trees (MSTs) with this ugly piece of Python code.  I will try to describe in brief what I plan to do during this GSoC period.

 

Region Adjacency Graphs

Certain image segmentation algorithms have a tendency to over segment an image. They divide a region as perceived by humans into two or more regions. This is because they tend to favor small regions of similar color. But in the real world one object might have different shades of the same color or different colors all together. Here is an example using SLIC. In broad terms SLIC is k-means done on (X,Y, Z ) color space

 

Lena and her SLIC

We consider each of these regions as a vertex in a graph. Each region is connected to all the regions that touch it. Similar regions are joined with an edge of less weight. Dissimilar regions are joined with edges oh high weight. One measure of dissimilarity might be difference in the mean color. See the below example.

RAG for Lena

 

Processing The Region Adjacency Graphs

If we remove the edges with higher weights in an appropriate manner, the regions remaining connected would belong to the same object. Thus in this case the face, the hat, the hair might be finally one connected subgraph of regions. Over the next two weeks I will try to take an over segmented image and build its RAG. As a proof of concept of the underlying data structures and algorithms I will apply a threshold and remove the edges with weights higher than it. Later on I will move onto to more complicated selection procedures including N-cut and if my MST experiments yield good results an MST based procedure.

 

VigRedis – The Story Behind

Around 2 months ago I started writing code for the Exotel Tech Challenge. The objective was to implement a Redis clone with a small subset of its commands. Redis is a hugely popular in memory data store. The code I have written is nowhere close to matching Redis, but it serves as a conceptual proof the underlying data structures and I/O logic. And not to forget, it passes the test-cases ( which I wrote myself ). I call my in memory data store ( sort of ) VigRedis. VigRedis implements a few commands that Redis supports : GET, SET, GETBIT, SETBIT, ZADD, ZRANGE, ZCARD, ZCOUNT, SAVE.

The Source

https://github.com/vighneshbirodkar/vigredis

Limitations

To start of I would like to mention the limitations of VigRedis.

  • No Pipelining – Requests/commands to VigRedis cannot be pipelined. The client has to send a command and wait for the response before it can safely begin transmitting the next one. I avoided this due to the complexities involved in buffer management and parsing required to support this.
  • ZADD – Supports only a single score-member pair.
  • ZRANGE – Duplicate keys are not sorted in lexicographical order.
  • ZCOUNT – Bracket notation is not supported.
  • No Eventloop VigRedis does all its tasks in a predetermined sequence, so occasionally there might be a client whose response will be delayed because some data structure maintenance is being done ( eg : increasing hash table size ).

Dependencies

None whatsoever. VigRedis compiles on any standard Linux distribution with the gcc compiler. No external libraries are required. The test-cases require python-nose to be installed.

Why C ?

In the beginning I had to make a choice as to what language to use to implement VigRedis. Probably if I had chosen Python, I would have written 10 times less code. Python had its powerful built-in data types which would significantly reduce my work. But while starting out I did not have the complete picture of the set of operations that need to be done to support. I knew that the moment I started doing any computationally intensive task using Python, it would imply a serious slow down. With C there is always an assurance that your program will be reasonably fast provided that it is algorithmically sound. More than that I wanted to know if I could build the required data structures from the ground up. Being a Computer Science student, I have been studying about hash tables, linked lists, dynamic arrays for a while now. Being able to implement them in a practical way ( space and time complexity wise ) using nothing but C primitives is an achievement ( in my own little world 🙂 ). And I can claim that I can fully understand what’s going on behinds the scenes.

A few Comparisons

In the beginning I tried comparing my dictionary data structure with Python’s. When Python creates an empty dictionary it allocates 8 slots. I ensured my code did the same ( see this line ). I tried inserting and retrieving a large number of keys. I noticed that my dictionary was faster than Pythons, but only upto a million keys. After 10,00,000 keys, Pythons dictionary kept getting faster than mine. But I wasn’t surprised ( Me v/s Guido van Rossum, Guido van Rossum wins )

Then I ran a few tests over the local network by executing speed.py. The results are shown below. The first execution was with VigRedis listening on the port and the second was with Redis.

performace

Although the test favors me I wouldn’t get too enthusiastic because if the requests were pipelined Redis would surely be the winner. And artificial benchmarks like these rarely reflect real world scenarios.

Data Structures

VigRedis uses two important data structures.

Dictionaries

See dict.c. This is a dynamically resizing hash table. Broadly speaking dictionaries can map strings to strings, doubles or pointers. Collisions are handled by chaining, see list.c.

SkipLists

See skip_list.c.These are a slightly modified version of this paper. I came across them while going through Redis‘ source code. A good explanation can be found in this video. SkipLists are ordered by score and hold strings as values.

Ordered Sets

See set.c. Ordered sets store strings sorted by the assigned score. An Ordered Set internally uses a dictionary and a skiplist. The skiplist orders strings by their scores and the dictionary handles duplicate score-member pairs.

Behind the Scenes

A short summary of how I have handled some important tasks

I/O

Simultaneous I/O with multiple clients is implemented using select(). Each client after connections is dynamically allocated a buffer which is scanned for a predefined characters to detect the end of a command. You can find the implementation on this line.

Command Parsing

The parsing of commands is done using strtok(). See handler.c.

GET,SET,GETBIT,SETBIT

These commands are handled by a single instance of the dictionary object. See kv_dict.

Key Expiry

Keys are stored with increasing oder of expiry time in expiry_list. This is a skiplist object. Expired keys are removed using dict_delete_expired.

ZADD,ZRANGE,ZCOUNT,ZCARD

These commands are handled using set_dict, which is a dictionary mapping strings to ordered set objects.

SAVE

Saving and loading of data is managed using a naive file format. See dump.c. A line starting with one space is a key-value entry.A line staring with two spaces is a set-score-member entry.

Unit Tests

Running unit tests requires python-nose


sudo apt-get install python-nose
cd tests/
nosetests -v

The tests cases cover the most basic command usage. The same test cases produce identical results when used with Redis as well.

Final Thoughts

VigRedis was a tremendous experience. Too bad that it will mostly just lie around githubmost likely never to be touched again. It still contains many bugs which might be just lurking around and might have escaped my testing. No matter how buggy or limited it is in terms of its functionality, this is exactly how I feel right now.

victory-baby-2