Bio

George graduated from the Saint Petersburg State University of Engineering and Economics in 2007 with a BA in information systems.

His current areas of interest are computer science and biology. His work is focused on simulation modeling of neurogenesis processes and biological evolution.

During his free time, George runs, listens to music, reads sci-pop books and is trying to study MOOC.

Computational Essay

Cell Receptors »

Project: Image Processing and Graph Reconstruction

Goal of the project:

Reconstruction of the structure of the graph represented in the image. In the best case, the algorithm should be able to reconstruct all graphs. The first prototype should be able to recognize simple undirected graphs.

Summary of work:

This work was divided into three parts.

Part I: vertices identification. Usually vertices are represented as centroids. Our test images have different colors for vertices and edges. We selected the ChanVeseBinarize function to divide an image into images that contain only vertices and only edges. DominantColors is essential for ChanVeseBinarize. When the image has been divided, the ComponentMeasurements function usage is the best way to extract coordinates of centroids.

Part II: edge detection. We decided to use Parallelogram to cover the region between two centroids. There is no data about the region that contains an edge, so we made all possible parallelograms between all vertices to cover the possible regions. This excessive method can produce much noise, for example, when two edges lie on one line. ImageMeasurement was very helpful to get various types of information from the image. We needed only the mean of the region covered by every parallelogram. AlphaChannel of the image helps to achieve a better mean of every region. So we had the pairs of vertices and the means of all pixels inside parallelograms that connect the vertices. If the mean value converges to 1.0, the area becomes white colored, so an edge is then detected! We made a function that compares the mean with the fixed value and filters the pairs of vertices.

Part III: visual check and graph reconstruction. After successful vertices and edge detection, we needed to make sure that this data was correct. We used HighlightImage with parallelograms of the edges found. If it all looks good, we can use Graph with the given list of pairs and apply GraphLayout to what we want.

Results and future work:

The graph is reconstructed and a user is able to use it in computations. The algorithm works only with simple graphs and requires the user’s manual control. The directions of future research might be in computer vision and machine learning domains. The main goal for future work is to be able to detect directed graphs and graphs with curved edges.