Archive | June 2014

Choosing a lisense for the Bayes Project

Licensing is a topic that very few people talk about during the development of a project but it’s still important. This Blog post talks a bit about licenses in general and shows why the MIT license was used for the Bayes Project.

Why need a licence

For a project to function correctly in an open source environment it needs lots of things. In the previous Blog post some of those things were stated. They were the usage of a versioning control system, the usage of conventions such as PEP8, and development of tests using a unit test framework. There was also one thing that was not mentioned in the last post which is the development of documentation, but that should go without saying!

Anyway, one big important thing in any open source project is the license. Licensing a project is very important because if anyone is going to be using the project, or contributing to said project in the first place, they need to know what they can and can’t do.

Before applying a license one should know what happens if the code doesn’t have any license with it. According with US law any software that doesn’t have a license can not be used, or downloaded, it’s source can’t be seen by anyone, etc. I don’t know how this applies outside of US, but that is mostly irrelevant since this project is already under the GitHub Terms of Service, which, quoting the source, “allow[s] other GitHub users some rights. Specifically, you allow others to view and fork your repository”. And this happens simply because the project gets hosted at GitHub.

But having the project just on GitHub is not enough. We still need an open source license in case we want to distribute this project outside of GitHub and in case this projects gets used by other projects. The various open source licenses must now be considered.

Open Source licenses

As one should expect, there are many open source licenses that can be used in an open source project. To name a few, there is the GNU GPL, GNU LGPL, MIT, BSD, among some other more specific ones, like the Python Software Foundation License, Boost license, zlib license, etc. For this project one of these licenses should be picked. The more specific ones should be ignored, even the Python Software Foundation License should be ignored because that license is used in the distribution of the Python project itself. Some projects written developed in Python fall under this license because they can be later integrated with Python itself, which is not the case with the Bayes project (name really needs changing).

One of the licenses that can be used is the GNU GPL license. This is undoubtedly the most used license and recognized by almost anyone. The license states that any source code or associated files of software distributed under it must be made available to anyone. It also states that anyone can modify the software and redistribute it. If someone does redistribute the software, with or without modifications, then the person must also grant these same freedoms as the original.

Any software under GPL must grant the same basic freedoms and can’t be used in a project that is not GPL. Meaning that one can’t take part of some GPL program and shove it into a non GPL program, like for example, taking the Linux Kernel using it in the development of a whole new operating system and selling that operating system never providing it’s source. Can’t be done.

The GNU LGPL license is a bit different. It allows the usage of a project under the LGPL license in Software that can be under other licenses and even be proprietary. There is an interesting article in at gnu.org about why one should not use LGPL for a library. Link for it.

The MIT license is less restrictive then GPL and LGPL. A project using this license can “(…) deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software”. A warranty is also provided stating that “in no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the software.”

In the end the MIT license was chosen because it is simple, not very much restrictive and can be later used in projects with other licenses.

Implementation of a Library for Probabilistic Calculus

Probabilities, Algorithms and Complexity

It is quite common in subjects like Artificial Intelligence, Machine Learning and Decision Theory, that problems which deal with uncertainty show up. This is because these problems deal with settings that are only partially observable, or systems that are simply too complex to be explained by an approach like First Order Logic or Propositional Logic.

To deal with uncertainty the concept of Probabilities is introduced. A probability is basically an assign degree of belief given to some proposition. A proposition is represented using a Random variable.

One of the many applications of probabilities is in Bayesian Networks. Bayesian Networks can be thought of as a direct acyclic graph where each node represents a proposition about some setting. That proposition is seen as a Random Variable, and each node in the network has a conditional probability associated with it. That distribution is the probability of the node’s variable given it’s parent.

Off course, Bayesian Networks are but one example. Probabilities are used in many different contexts and the algorithms that can be applied to it are vast. These calculations and algorithms are not exactly trivial, meaning that they are not easily calculated by hand or using the default constructs and data structures of many programming languages.

The problem of representing an arbitrary big multi variable probability distribution can be non trivial by itself, let alone thinking about all the possible operations over them, like, multiplication between distributions, computing the marginals, expected values, implementing algorithms like elimination ask, among other things. A simple way should exist to deal with these problems.

This is the main motivation for the development of this project. To provide an efficient yet simple to use Python library that abstracts all the intricacies of operations between factors and lets the user implement complex algorithms over them.

Efficient Yet Simple

To make things efficient will be the subject of a whole new blog post. To make things simple will be stated now.

So the main problem is representing Random Variables and Probability Distributions. After that we thing about all the algorithms, functions that can be implemented over these distributions, things like random variables that change over time, among other things.

To represent a Random Variable in this library one simple does:

X = factor.RandVar("X", [True, False])

The first argument of the constructor of the class RandVar is a string. That string is the name of this variable, in this case X. The second argument is the domain of the variable. In this case X is a binary variable which can take the value True or False.

Besides binary variables we can have arbitrary big variables. Suppose:

Y = factor.RandVar("Y", list(range(100)))

A random variable with a domain with size 100.

From this we need a distribution for the variables. For example:

X = factor.RandVar("X", [True, False])
Y = factor.RandVar("Y", [True, False])
x_dist = factor.Factor([X], [0.2, 0.8])
y_dist = factor.Factor([Y], [0.9, 0.1])

So above we have two binary variables, X and Y, and their distributions. For example, the probability of X being True is 0.2, that is, P(X = True) = 0.2. The probability of Y being False is 0.1, P(Y = False) = 0.1.

So we can create distributions for one variable. How about two? If we suppose X and Y are independent, we can just multiply them:

# P(X, Y) = P(X)P(Y)
xy_dist = x_dist.mult(y_dist)

If not we just do it like we did the others:

xy_dist = factor.Factor([X, Y], [0.1, 0.2, 0.3, 0.4])

In here we have to vectorize the matrix that would represent the distribution P(X, Y). That is where the usage of this library is not so simple. But trust me, it is the only thing.

A simple method needs to be implement to circumvent this. I already have a few ideas, but nothing very solid yet.

From here we can get a lot of operations going, such as, the marginal of X in a join distribution:

x_dist = xy_dist.marginal(X)

Instantiating a variable with some value, P(X = True, Y), is done like this:

vec = xy_dist.instVar(X, True)

Off course, the same things are similar with many variables in a distribution. Suppose similar operations in a distribution with four variables, P(X, Y, Z, W):

xy_dist = xyzw.margianl([X, Y])
xy_dist = xyzw.instVar([X, Y], [True, False])

Without continuing too much further into implementations, here is a link for an example with a Bayesian Network implementation.

There are many plans for the future of this projects, both in things to be implemented and things where it is going to be used. Development shall continue.

The Project

The project is being developed using Git has a version control system, off course. It’s source is hosted at GitHub. For future contributions one is expected to be able to use this platform.

Like many programming languages, Python allows many ways to do the same thing. You can use different indentation spaces in the same file, space the functions and classes definitions with a different number of newlines, among other small details.

Problem is, if these details don’t follow some convention, the code files end up being a big ugly joint of code instead of an eye appealing project. This can be a problem if someone wants to participate in a project and has to deal with some very confusing code. Not to mention that some Python projects end up having some portions in Python 2 and other’s in Python 3, which gives many problems in the future.

To avoid this, we convention that the project needs to follow the PEP8 standard, and be written only in Python 3.

To end, I’ve participated in far to many projects that have no notion of unit tests. I am not having this now. This project will have to have unit tests implemented for everything. To work with these tests we use nosetests. A simple testing framework.

Sobel Filter

Intro

Recently I came across a project for a course at my college that dealt with the Sobel Operator. The project should be implemented using the MIPS instruction set and it should execute in a MIPS simulator. I found the theme to be an interesting one and wanted to implement the algorithm, but because and because working with low level assembly languages just takes to long I decided to implement the same algorithm using the C programming language. Maybe I’ll extend the program in the future for other filters.

The results are in Github.

About the Filter

The way the project is suppose to be implemented by my colleagues uses a different algorithm from the one used in this project. The one used in this project is simply the one in Wikipedia.

To start, we take the RGB image and calculate it’s gray representation. The way that is done is that we take the three values for RGB of each pixel and calculate its gray equivalent using the following formula:

G = 0.30*R + 0.59*G + 0.11*B.

This can be thought of has a sort of weighted average between the three values. Note how much more important the Green value is as opposed to the other two. The is not done by chance, it is actually because the human eye sees Green better then the other colors.

After this step the two sobel operators are going to be used. I don’t know to much about the operators so I won’t spent to much time on them regarding the theory behind it all. I’ll just say that there are two operators, an horizontal and a vertical one. They are:

    -1 0 1       1  2  1
H = -2 0 2  V =  0  0  0
    -1 0 1      -1 -2 -1

The objective now is to perform a convolution operation between the gray image and each operator. The operations are going to give two new images, one which is the result of the convolution with the horizontal operator and the other with the vertical operator. Those images are going to be referred to by Gh and Gv.

Having both images we now calculate each pixel of the contour image by summing the power of every pixel of Gh and Gv and calculating it’s square root, like this:

G = sqrt(pow(Gh, 2) + pow(Gv, 2)).

The result is a gray image that can be written to a file and converted to a PNG, or JPG, or any other file format using the command:

convert -size 512x512 -depth 8 img_out.gray img_out.png

Implementing

Algorithm

This algorithm has two inputs and an output. The inputs are an RGB image and it’s size, while the output is just a gray image with the contours of the input image. The size of the image is actually composed of two values, width and height.

An RGB image is a sequence of bytes, where every three bytes represent the Red, Green and Blue values of a pixel. And RGB image has no other information besides the value of every pixel, so the size of the image needs to be keep some other way. To convert a PNG or JPG image to RGB just use the convert tool from ImageMagick.

convert img.png img.rgb

Borders

The way the convolution is made may confuse some people due to it’s lack of definition with the borders of the image. To illustrate the problem, see the following definition for the convolution, which is usually defined in this situation.

convolution

The P_{x, y} represents a pixel in the gray image with coordinates x, y. S is one of the sobel operators. R is the resulting value of the convolution. Note that R is an integer value, not a matrix.

Lets visualize what happens when we superimpose a part of the gray image around the pixel that is getting calculated and the sobel operator during convolution.

convcenter

Where is the problem with the border? Lest do the same things we did before, but lets pick a pixel of the image that is in the border, say the left border.

convborder

Has you can see three pixels are missing from neighborhood of the central pixel. But the convolution still has to be made. We can consider that there are three imaginary pixels which value is 0. Like this the convolution works. Instead of 0 we could pick any other value, ignore the parcel all together, or even consider the pixels in the right border for these calculations. I picked to equaling hem to o because it becomes simple to implement it like that. Also, the end result of what we see in the contour image is mostly irrelevant, so we should spend to much time thinking about this.

Note that the same situation arises in the other borders and in the corners.

The algorithm which makes the convolution for one pixel of the image gets the sobel operator and a 3×3 matrix as input. That 3×3 matrix is a matrix in which the central element is the pixel it self, and the other elements are the neighbors of that pixel. To construct this matrix a simple function called makeOpMem is used.

The function starts by trying to understand if the central pixel is in one of the borders. Note that a pixel in one corner is in two border at the same time, for example, if the pixel is the top left corner, then the pixel is in the left and top border at the same time.

The function then produces four boolean variables, bottom, top, left, and right. What follows next are the assignments:

op_mem[0] = !bottom && !left  ? buffer[cindex-width-1] : 0;
op_mem[1] = !bottom           ? buffer[cindex-width]   : 0;
op_mem[2] = !bottom && !right ? buffer[cindex-width+1] : 0;

op_mem[3] = !left             ? buffer[cindex-1]       : 0;
op_mem[4] = buffer[cindex];
op_mem[5] = !right            ? buffer[cindex+1]       : 0;

op_mem[6] = !top && !left     ? buffer[cindex+width-1] : 0;
op_mem[7] = !top              ? buffer[cindex+width]   : 0;
op_mem[8] = !top && !right    ? buffer[cindex+width+1] : 0;

So, for example, the first line of this code assign the buffer[cindex-width-1] to op_mem[0] if the pixel is not the one in the bottom left corner, otherwise it assign the 0 value to it. The second line does something similar if the pixel is not located in the second line, ans so on. The line with op_mem[4] only assign the value of buffer[cindex] because that is the value of the central pixel, that always exists, no matter the location.

This is not the best method regarding the algorithm speed. There cold be things that are way better then this because this way calculates 9 values for every pixel, where better ways could save those values shift them around and maybe save some cycles. But this method is simple to understand and implement.

Data Type

The program reads the RGB file to an array of bytes exactly has it is in the file. The byte data type specified in here is simple a typedef for an unsigned char, like this:

typedef unsigned char byte;

This definition is used for two reasons. First, each value of an RGB element of a pixel is an integer number, but it’s always a number between 0 and 255. One byte is made out of 8 bits. The minimum value that can be represented with 8 bits is, of course, 0 and the greatest value is 2^8 – 1 = 255. This is the range we want.

An integer in C doesn’t take only one byte, it takes a word. The extra space it takes to represent a single integer in C goes beyond the 0-255 range we want. So instead of of using the int data type we use the char data type, which only occupies 1 byte.

But why unsigned data type? Like specified before, the 8 bits can represent a number up to 255. But because of a thing called two’s_complement the leftmost bit doesn’t contribute to the number itself but to its sign. If that bit is 1, then the other bits are read as a negative number. If it is 0, the bits are read as a positive number. This also makes the range of one byte go from -128 to 127, which is not good for us.

By specifying that we want an unsigned value, every bit in the char represents the number it self, so it’s range goes from 0 to 255. Because we just consider that writing byte is just so much better then writing unsigned char, we do the typedef.

Compiling and Running

The Makefiles used in this project are very simple and were all written from scratch without the use of other tools. Maybe in the future the auto tools will be used. This will offer the advantage of having a more conventional build process and also the possibility of running the make install option to actually install the program in the system.

As of this version, after compiling an executable is created in the src directory called sobel. To execute the program, run is run with a few arguments, the specification for those arguments are described in the README file.

Note that the program will overwrite any existing files, if they are specified in the arguments.

Source Files

The source files in this project are the following.

file_operations.c
file_operations.h
macros.h
main.c
sobel.c
sobel.h

The file_operations.c and .h files only implement two functions that are used to read and write the image files. The sobel.c and sobel.h implement every function used in the calculation of the edge detection algorithm.

The main.c file only has one main function that work out the arguments of the program. The macros.h file only contains the typedef for the byte data type and macro for the size of a sobel operator.