Edge detection using the Sobel operator

In image processing, a lot of useful information in an image is contained in the edges of objects, and edge detection is a process of separating the object edges and the rest of the image (objects themselves and their environments). Obtained information can then be used for further analysis, such as detection of faces, boundaries, or other image processing procedures such as superresolution (e.g. deciding whether to continue a gradient or place a sharper border between new pixels could depend on whether an edge is being processed).

Edge detection applied on a CGI image

Edge detection applied on a CGI image

The goal of an edge detection algorithm is to identify the pixels that are more likely to belong to an edge. This can be accomplished by setting the pixels which the algorithm deems belong to an edge to 0, and those that do not, to 255, on a grayscale image (or just converting it to a black and white bit string). The end result of the mentioned filtering process can be seen in the first image.

In the Sobel procedure, determining how likely a pixel belongs to an edge is based on the fact that the rate of change in brightness along edges of objects tends to be higher. The gradient for brightness is taken for every pixel in the image, in the form of a 2-dimensional vector (change in X axis, and Y axis), and the magnitude of that gradient vector corresponds with the likeliness of the pixel being a part of an edge.

The Sobel operator is used for calculating the gradient vector (the rate of change for a point, with a direction) for each pixel. Concretely, it involves iterating over every pixel in the image, and using the following two matrices to calculate the X and Y components of the gradient vector:

sobmasks

Matrices for calculating the gradient components

The center cell represents the current pixel, and other cells represent neighboring ones. The outermost layer of pixels (from [0, 0] to [width-1, 0] and [0, height-1], etc) is problematic, since they do not have a full neighborhood. In my implementation they are ignored, since a single layer of pixels should not carry that much information and can thus be discarded.

For each position in the image, the values of the pixels covered by a matrix (pixel at current position + neighboring pixels) are multiplied by the coefficients in each cell of the matrix (each pixel by its respective cell), and added to a sum. Depending on the matrix, these sums represent the X and Y components of the gradient vector.

Above matrices work on a rather simple principle. First, the center cell has a coefficient of 0 that represents the pixel being processed. Since the algorithm is interested in finding the rate of change of that pixel in respect to its neighborhood, the pixel’s own value can be ignored, because it has no direction information (it will be used in the next step for calculating the gradient of the right pixel, though). The two center-horizontal outer cells have values of -2 and +2 respectively, because their pixels are the closest to the current one on the X axis. The sign signifies direction.

For example, if there was a row of pixels under the matrix with values of [255, 255, 255] (top and bottom rows ignored for simplicity), the X component of the gradient vector would be 0. And that makes sense because the rate of change for the center pixel really is 0 – its two neighbors have the same value (this can be visualized by two physical forces of the same quantity dragging an object in two opposite directions – the object doesn’t change its velocity). If it was [255, 0, 255], it would still be zero, because the rate of change in both directions on the X axis is the same – but for both the left and the right pixels, it could hold a non-zero value.

The same method is used for calculating the Y component, and afterwards, the magnitude of the gradient vector can either be approximated by adding up the absolute values of the components, or calculated with the proper formula (Pythagoras’ theorem), to get the final value of the edge quality for that pixel. A low magnitude means the pixel is less likely to be a part of an edge. To get the final result (first image in post), where the edges are concretely identified or visualized, one only needs to set a threshold for the magnitudes of the gradients, over which the pixels are declared a part of an edge, and under which, the pixels are declared part of either the background, or the object itself.

The step before applying the threshold filter

The step before applying the threshold filter

Robot Evolution

Robot Evolution is an application that uses genetic algorithms to evolve and optimize virtual walking poly-pedal robots. The robots are 2D geometric constructions of rectangles that are connected by virtual motors which apply torque to these rectangles, making them move.

In this post I wont really explain how genetic algorithms work nor go into detail about our application, but rather just gloss over the most important features, present some results, and explain them.

Here’s an example of an evolved galloping robot:

walker1

The application was developed by Luka Bubalo and Jan Corazza (blog author).

Some of the features include:

  1. Presenting evolution in real-time, with an interactive user interface
  2. Persisting simulation results and chromosomes into files, loading previous results
  3. Parallelization of simulations across arbitrary many threads
  4. Rich configuration with a Java properties file

I’ve also made a neat logo for it:

logo2

This is an update to my earlier post, Machine Evolution (ME). The name of the application has, obviously, been changed, but so has the idea behind it.

Most importantly, we’ve severely tightened our problem space to walking robots only. The reason for that was because the deadline of the competition we’ve been aiming at was getting really close, and of course as we’ve started designing the details of the application, it became increasingly apparent that we wouldn’t be able to meet the deadline with such an enthusiastic approach.

Thus, it was decided to switch the language from C++ to Java (seems like a recurring theme on this blog), and of course impose the above restrictions. However I still believe that’s only the natural evolution of an idea.

This is the GUI of the application:ui

But it can also be ran on servers:

onServer

rtevo.jar threads on a Linux VPS

The configuration is done via a Java properties file which provides for really simple key-value bindings that the application can natively read. Here’s an example of a configuration file:

Here’s some data we collected recording the performance of the fittest unit (robot) in each generation (performance is measured in meters passed):

Evidently performance increases with the number of generations.

The different levels of intensity in random fluctuation in these graphs are due to different selection mechanisms, used to promote units from one generation to the next one.

The first graph shows the usage of plain proportional selection (also called roulette wheel), which makes the chromosomes from a previous generation proportionally present in the current one according to their fitness. For example, if a unit accounted for roughly 50% of overall distance passed in a population (an obviously superior robot), then the algorithm would assign each new unit a chance of 50% to have it as a parent – thus, instead of there being only one sample, roughly half the units would now inherit from the superior one.

The method of proportional selection can be illustrated like this:

roulette_wheel

a is a random number, the colored cells represent units, and their length is proportional to the fitness of the unit

The reason proportional selection seems to fluctuate so drastically is the fact that the method does not guarantee that a fit unit would be represented at all in the following generation – there are merely higher and lower chances, but no guarantees. In the above example of a superior robot, it would be completely possible for it to not be included at all (and usually the chance for that is very high since no unit actually has 50% of the population score, but rather  around 1/(number of units in generation))! We will try mitigating this effect by increasing population sizes.

The second graph is an example of a hybrid selection mechanism – combining truncation selection and proportional selection. This method guarantees that the top 10% will always pass on to the next generation (truncating the top), thus reducing the fluctuation effects only to minor mutations. The rest of the 90% of the generation gets filled proportionally.

The actual evaluation of the fitness is a rather delicate procedure, from my perspective at least. The entire population is divided into N simulations, and each simulation is independent from the other. The simulations are then parallelized and left alone to crunch numbers with the physics engine JBox2D. After their calculations are done, the results are aggregated together, so the next generation can be computed (using the above selection mechanisms).

Parallelization can be visualized like this:

parallel

As the image demonstrates, threads are recycled between simulations. It’s also important to note that it is not possible to concurrently compute two different generations due to the fact that each generation is conditioned by the one before it (with the exception of gen #1 which is randomly generated).

The main thread takes the most successful unit from the last generation and creates a another sandboxed simulation for it. This simulation is presented to the user in real time, and its results are discarded (i.e. not measured at all).

We use tools from the Java Concurrent package for parallelization, and Swing for 2D graphics and the UI.

Robot Evolution is open source (MIT license), and can be found on GitHub: https://github.com/corazza/rtevo. Documentation is public and can be found on Google Drive.

You can download the program here. It is a 7-zipped file containing the JAR (with all the dependencies baked in) and a configuration file.

Run the program like this:

java -jar rtevo.jar configuration.properties

You can edit the configuration file to suit your needs.

Manipulating Java class loading mechanisms

I’m working as an intern at the moment, and I was tasked with creating an evaluator for Java for an online competition. It’s essentially supposed to execute code sent by the competitors using JUnit (and a security framework, of course), and return some results – the final implementation is supposed to be a web application which would allow users to submit JAR files with their classes to the server and display a ranking and/or their individual points and test results.

The first problem that had to be solved was dynamically loading and unloading classes in the Java runtime, and that is what this post is about. However, this introduced a number of other problems as well – mostly due to the nature of the Java class loading system and the requirements of the application itself.

This is an example of a very simple class being tested:

And this is the JUnit test:

The default implementation of K always fails this test, obviously. However, the evaluator is supposed to provide alternative implementations of K (each of them found in separate JAR files), and test them as well.

This is not something done regularly in Java, and was problematic, because I wasn’t used to this way of thinking: that there can be multiple classes all sharing the same fully qualified name, coexisting in parallel or even one after another, in the same runtime. However, these kinds of situations are possible because classes are not only identified by their fully qualified names, but also the classloaders that loaded them.

I thought initially that this would be a solution to my problem. For each submission, I could just create a new classloader, load the class, and then have it tested. But it’s not that simple at all!

First of all, class loaders in Java exist in a hierarchy – each classloader has a single parent class loader, all the way up to the bootstrap one, which doesn’t have a parent and is implemented natively. It’s difficult (yet not impossible) to create an isolated classloader that would work by itself and just load the classes it was told to load. Which means that the class loaders created programmatically in order to load some class can end up not being the ones who loaded it! This is due to the hierarchy and the implementation of the ClassLoader#loadClass() method. The default behavior is to simply delegate the loading to the parent classloader – and proceed to actually load it only if every node in the chain up to the root one had not succeeded. Modifying this behavior is discouraged – and custom implementations are supposed to override the ClassLoader#findClass() method that is actually supposed to load and define a class as loaded by this class loader (which, by default, just throws a ClassNotFoundException) instead (since this fits most uses people would even have for custom class loaders).

This can be demonstrated in the following snippet of code:

This is the output when the code is ran:

What’s going on?

It is evident that the static initializer gets called only once. From there, it can be concluded, that the class K was loaded once – when it was first needed in the 32nd line (exactly when a class is loaded depends on the JVM implementation). In the 40th line, where URLClassLoader is requested to load the class once more, and then in the 42nd line where an instance of that loaded class is requested, the static initializer is not called again – because URLClassLoader had only returned the already loaded com.yannbane.snippets.K class from its parent. Furthermore, it’s obvious that the implicitly loaded class and the programmatically loaded one are the same because com.yannbane.snippets.K#getNumObjects() returned 2, and not one.

Why was this a problem? Well, if the classes that I tried to load all had the same fully qualified names, and were not in fact loaded by my class loader, but rather delegated further up, they would end up being discarded as already loaded by the ClassLoader#findLoadedClass() method (at the beginning of loadClass(), source line 312).

To solve this, I had to somehow selectively filter all the requests for the classes that I wanted to load programmatically, and delegate all other requests which couldn’t be found in URL sources.

The second issue was the fact that was impossible to change the classloader of some class at runtime (and it wouldn’t do me any good either). The classloader which loaded (more specifically, called ClassLoader#defineClass() on the bytecode) the class was set as its current classloader – and all the references in this class will be loaded by it.

These two facts implied that in order to get the JUnit test to load the specific classes sent by the users, it was necessary for the test itself to be loaded and defined by my custom classloader.

I had to create a custom classloader that would extend URLClassLoader, which is able to load classes found in JAR files (in the above example the URL sources were empty so it behaved just like a regular classloader). Then, the URLs pointing to the JAR file of the user’s class(es), and to the root package of the project would be set for it. Lastly, the loadClass() method had to be overridden with custom logic: load first, delegate later. This meant that the custom classloader would first try to find the requested class in its own URL resources, and only when it failed to find one would it delegate the search to its parent.

The result is this simple piece of code to execute a test on a custom class from a JAR file:

This is the source code of my ReverseURLClassLoader which I’ve written:

The algorithm is simple:

  1. Check if class already loaded by this classloader, if so, return it (ln. 20)
  2. If not, try to find the class in URL sources (JAR of the user) and return it (ln. 24)
  3. If failed, call URLClassLoader#loadClass() which delegates to parent classloader (ln. 26)

I’m still working on the project, as I’m yet to implement the most important logic, the web application, and security, so I’m likely to post another article or two about it.

Artificial Intelligence

The field of artificial intelligence, abbreviated as AI, has been quite turbulent and ever-changing in its scope since its creation. This essay deals with its inception, transition from idealistic to pragmatic, history, development, crises, touches the current state of the art, and concludes with a thought on where the future of AI research lies.

In order to understand artificial intelligence, it is important to grasp the historical context that birthed it. Although humans have dreamt of creating intelligent, artificial beings almost as long as they’ve been recording history, it was not until WWII, that the conditions were ripe for actually expanding and formalizing machine intelligence. It had all started with the need to design machines capable of responding to external feedback, and adjusting themselves to it. Norbert Wiener, a professor from the United States, created an automatic flak control system during WWII, that adjusted itself according to input and feedback from a radar – which was tremendously important to our understanding of intelligent and adaptable systems. Weiner believed that most of what we think of as intelligent behavior, is in fact a result of feedback mechanisms, and this principle led to the development of feedback theory.

Although these early attempts had touching points with contemporary AI, and were somewhat in the spirit of it, it is most commonly thought that AI requires actual digital computers in order to advance, and outside of this brief mention of mechanical systems, this essay mostly concentrates on digital efforts.  Thus it can be safely said that artificial intelligence, as a branch of computer science, was started in 1956 at the Dartmouth summer AI conference. The fathers of AI that attended this conference are John McCarthy, Marvin Minsky, Allen Newell, and Herbert Simon, while McCarthy coined the actual term in 1955.

One of the most important early contributions to this field, although not directly tied to AI, was the invention of the Lisp programming language by John McCarthy in 1958. Lisp was one of the pillars of the academic AI community, and still bears a great presence in some altered forms. Another great accomplishment was the creation of SHRDLU in 1968 – a natural language processing program that was capable of manipulating virtual geometrical objects by processing and following commands written in English.

In its earliest stages, AI was closely bound to the academic community, and its goals and promoters were unrealistically optimistic – for example, Minsky, on numerous occasions, had stated that the ultimate goal of AI, creating a general intelligence much alike to human’s, would be achieved in less than a dozen years. Such promises, and the failure to meet them, led to large government funding cuts and near-disappearance of corporate funding – this era was dubbed the first AI winter and lasted throughout the seventies.

Another large sub-field or approach in AI was also experiencing severe issues at the time of the first AI winter – connectionism – which dealt with achieving artificial intelligence by means of distributed networks of nodes and links, much alike biological neurons. As many other techniques, it was first hailed as a solution to most problems AI faced (understanding natural language, general intelligence, et cetera), but was quickly proven not to be as promising as it was advertised. Minsky and Papert detailed various problems that this approach faced in their 1968 book titled “Perceptrons”.

After such a devastating period in the seventies, the entire field had gone through a second era of enthusiasm and commercial success, following the rise of expert systems, programs that are well-suited for providing expert knowledge and solving problems in a specific domain, such as helping with diagnoses. Another phenomenon that could be observed was the second rise of connectionism. Most importantly, many of the initial problems of the technique were solved – like the inability to approximate nonlinear functions – by algorithms such as backpropagation, which  improved upon the original idea and gave it the much needed space to expand.

However, this period came to an end as well. Again, funding was running shorter and shorter, results didn’t meet the expectations, and general stagnation ensued – but the beginnings of a new trend could be observed: commercialization and practicalization of the techniques and research topics. The former goals of creating a general intelligence, and the enthusiasm for the field, mostly due to lack of understanding of how complex intelligence really was and unrealistic expectations, were waning.

Today, AI has completed its unstable period of constant overly-optimistic enthusiasm, and affirmed its place amongst other disciplines permanently. However, it has also completed the aforementioned transition into the commercial and the pragmatic. The academic community has created a powerful toolbox for the IT industry to utilize, and AI is currently being used in many aspects of our lives: cars can learn, our phones can learn, Google learns about your interests and provides better search results (and ads) accordingly – and soon due to the rise of hypercheap electronics and robotics, we will have more real-life interactions with intelligent machines.

However, there are still ambitious projects that aim to create “hard”, or artificial general intelligence. This is because such endeavors are finally becoming less idealistic and utopian, and more practical. One very promising example is the OpenCog project – an open source initiative based in Hong Kong that is currently experimenting with intelligent Nao robots, and creating a comprehensive free/libre open source C++ AI framework around their work.

Essentially, there are currently three further directions that research into AGI could take. The first one, which is what OpenCog is doing, is based around crafting a specific framework which consists of different algorithms, data structures, and techniques, both already developed and new, that operates on some kind of knowledge base while adapting itself to the environment. The second approach uses evolution and connectionism in order to achieve its goal. This is the course that one of my projects has taken – the basic idea is that if intelligence had once arisen via evolution, as it did with humans (and some other mammals and animals), then it could happen again – except this time, humans would be simulating the environment in which evolution takes place. The main problem of this approach is that it’s simply very computationally expensive, and greatly depends on the initial conditions and the basic rules that we’ve set up. The third and the most direct approach would be directly simulating a biological brain. The problem here is that the desired emergent behavior could depend on seemingly unrelated processes in our brain’s biochemistry (or even quantum physics), that we either don’t know about yet, or some phenomena that we deem irrelevant for the simulation by mistake from ignorance.

Maybe the answer is held in the combination of these three approaches. Only two things are certain: AI is here to stay, and only the tip of the iceberg has been reached.

Machine Evolution (ME)

Me and my friend are working on something quite interesting, a program that optimizes designs of various machines: vehicles, drones, ground robots, etc.

The idea is to use a physics framework in order to evaluate how well-suited a machine is to some goal, on some terrain.

The main algorithm spawns many randomly generated candidate machines into a single generation, and then evaluates all the members of that generation – by simulating all the units’ operations on the same terrain. After the evaluation process, each machine is assigned a numerical value that describes its performance. The program then proceeds to generate a new generation, based on the previous one’s best performers.

Thus, our hypothesis is that useful traits in these machines would propagate, and that the population would gradually evolve to some optimal form (or multiple optimal forms, aka species).

The current plan is to use neural networks as a control mechanism, and employ neuroevolution in order to evolve the behavioral part of our population (as opposed to just the structure, which by itself, is useless).  And as mentioned previously, one of the goals is to be able to distribute and parallelize the computation across multiple processors or computers in a network.  This is possible due to the fact that each of the simulations is a self-contained operation without any side-effects. We can parallelize the computation within a single generation because of this – but we cannot be computing multiple generations at the same time, since each generation depends on the one before it, and conditions the one after it.

The project is of course open source and available on GitHub: https://github.com/corazza/rtevo.

The new website

My new web setup finally seems to be settled, and it’s been fun hacking it all up together… I’ve gone through several configurations in the last week, in fact.

First, I transferred my domain yannbane.com from GoDaddy (registered through Blogger, i.e. Google) to Namecheap, which just seemed like a simpler solution because I didn’t have to deal with any Google Apps business. I also registered yannbane.net and yannbane.org, which now both redirect to my root domain.

That was the uninteresting part… The cool part of my new setup is that I finally have my own server, via DigitalOcean. They offer one virtual private Linux server, with full root access, and 20GB of SSD storage, only for $5 a month (which is the most basic plan). SSD storage means that I can pretty much dynamically create and destroy the servers on demand, clone them, etc.

At first, I tried the nginx web server. It’s pretty simple and more efficient than Apache, but I had issues with it, so I just stuck with Apache. My server is currently running Ubuntu 13.04, with LAMP.

I’ve set up this WordPress blog, and more interestingly, an ownCloud server – which has already proven itself to be extremely useful. Essentially it’s like Dropbox or Google Drive (plus even more cloud applications, not just storage), except you’re in complete control of your data and the entire platform – since it’s all running on your server and is free (and open source) software.  Before WordPress I was processing Markdown files into a static website and uploading them via rsync, which I’ve found too cumbersome and limited. The software I used for that was Jekyll.

GNU/Linux infographics

I’ve created two infographics with the intent of helping newbies with choosing the right GNU/Linux distro. The content is practically the same in both, but the second one has some graphical improvements that aren’t my own work.

The posters along with other information can be found in this git repo: https://github.com/yannbane/ForNewbies.

 

Graviton has been finished

I’m a bit late with this post, as finishing Graviton and my paper had happened a few weeks ago already… It doesn’t matter though, here are some of my results.

orbits_regular

New features include:

  1. Fourth order Runge-Kutta integrator
  2. 3D mathematics instead of 2D
  3. Minimal mode with no graphics
  4. Orbit display
  5. More bodies and accurate data from HORIZONS in the default solar_system file
  6. A user module and a primitive event system, where the user may override various event handlers for information extraction and custom reports
  7. Enhanced reports (ETA calculation, important dates (beginning, end), timers, extensible via the user module)
  8. Improved control over the simulation (via CLI arguments)
  9. Tested saving methods

In addition to all these new features, I’ve ran a lot of test for an astronomy project of mine. One of the tests I’ve ran was simulating from the year 2006, 23 years, into the year 2029, in order to compare my results (the distance between Earth and the asteroid 99942 Apophis) with NASA’s. In short, it seems like my work is pretty solid, as I’ve my results deviate from NASA’s only by 0.505%.

The code is a complete mess, though, and has to be reworked. I blame Python.

How to: Steam on Linux (Debian 7.0)

Today I’ve successfully, and without much trouble, installed Steam on my Debian Wheezy PC.

This goes without saying, but honestly, I never thought I’d see the day. Running Half Life nice and smooth… On Linux. Wow.

Although there were really no actual problems with the installation process, there were some annoyances, so I’ve decided to compile a short list of steps that you should follow in order to use Steam on Debian. Please note that these only solve problems which I myself have encountered, and that they are usually solved for you if you use Ubuntu.

The list is quite short, but I’ll keep adding more items to it. Make sure you read through all of them though, because they might not be in the order of occurrence!

  1. Download: steam_latest.deb
  2. InstallationAfter you have downloaded “steam_latest.deb” into your ~/Downloads directory or wherever, open up a terminal, execute cd ~/Downloads and then just invoke the Debian package manager in order to install it: sudo dpkg -i steam_latest.deb.
  3. Missing dependenciesThe installation will probably fail, and complain about missing dependencies. In order to fix issues like this one, not just with Steam but with any package you’re installing manually, run sudo apt-get -f install.
  4. Wrong architectureIt’s quite possible that you’re running a x64 (64 bit) system, like I am. The current Steam Debian package only supports the x86 (32 bit), and you will have to enable i386 (fancy Intel name for 32 bit) packages. Don’t worry, Linux handles both architectures flawlessly, and your 64 bit programs keep using 64 bit libraries.To add the i386 arch execute: sudo dpkg –add-architecture i386 && sudo apt-get update and wait for it to finish. You should now be able to install Steam.
  5. Missing GLIBC_2.5This is quite an annoying one, that I encountered just after the installation.
    1. cd
    2. mkdir steamlibs
    3. nano .bashrc Add the following lines:
    4. wget http://security.ubuntu.com/ubuntu/pool/main/e/eglibc/libc6_2.15-0ubuntu10.2_i386.deb
    5. dpkg -x libc6_2.15-0ubuntu10.2_i386.deb /tmp/libc/
    6. mv /tmp/libc/lib/i386-linux-gnu/* ${STEAMLIBS}

  6. No sound in gameWhen I first started Half Life, it was muted. I’m using ALSA as the sound server, however, so this fix will not work for PulseAudio users (who shouldn’t have the problem in the first place).
    1. Quit Steam.
    2. Execute sudo nano /usr/bin/steam.
    3. Get to the bottom of the page, and add export SDL_AUDIODRIVER=alsa before the last comment (line starting with a ‘#’).
    4. Run Steam again and your games should have audio.

  7. Running Steam from a desktop launcher (at least in Xfce)
    1. Right click on desktop
    2. Create launcher…
    3. Start writing “Steam” into the name box, and then select it from the suggestion.
    4. Create

    Try to run it! I doesn’t work, does it? Well, neither did mine, but I’ve figured out how to fix it:

    1. sudo mousepad /usr/bin/steam
    2. After the line that begins with a ‘#!’ (shebang) add:
    3. Completely quit Steam.
    4. Try your new launcher.

Xfce is a nice and minimal desktop environment for your Linux system. I suggest you try it.

  • Uninstalling SteamIf it so happens that you don’t want Steam on your computer anymore, you can uninstall it with sudo dpkg -r steam. This will not remove the previously added i386 arch, to do so, execute sudo dpkg –remove-architecture i386.

F.A.Q.

  1. Q: does Steam run background processes even after I quit it? A: No! If you want to check, do this: ps -e | grep steam.