This page is a part of the Computer Vision Wiki. The wiki is devoted to computer vision, especially low level computer vision, digital image analysis, and applications. The exposition is geared towards software developers, especially beginners. The wiki contains discussions, mathematics, algorithms, code snippets, source code, and compiled software. Everybody is welcome to contribute with this in mind - all links are no-follow.

From Computer Vision Wiki

In Binary Images the code was used as a mere illustration for the algorithm. Here it is the main subject. The difference in implementation is discussed. The VS solution is available upon request (e-mail: saveliev [at] marshall [dot] edu). The executable along with a few binary bitmap images is here [1]. Compare to Pixcavator [2].

The goal of this document is to explain the system structure of the Binary Analysis System. For each of the system sub modules, we will explain the goal of the module, notable functions, etc. Also, we will note differences between the system implementation and the book implementation, citing specific areas of text where necessary.

At the heart of the Image Analysis system is a set of classes located in the BinaryEngine.cpp file. These classes, as well as their functions, are declared in the BinaryEngine.h file. The classes which are part of the BinaryEngine are: CEdge, CCycle, CMemoryManager, and CBinaryAnalyzer. Within these classes, a global EdgeDirection enumeration is used.

It is very common in all of these classes that some sort of evaluation based on edge direction is needed. For better readability, a global edge enumeration was created. The Enumeration is defined as follows:

EdgeDirectionNone = 0;
EdgeDirectionRight = 1;
EdgeDirectionUp = 2;
EdgeDirectionLeft = 3;
EdgeDirectionDown = 4;

Difference:

In Binary Images, all of the edge directions are hard coded in the implementation. While the corresponding Edge Direction values are consistent in each (the text and program), the subtle change does add some clarity to program. For example, the way an edge is declared in the book is (page 2-28) int edge[4]; edge[0]=x; edge[1]=y; edge[2]=1; edge[3]=0; However, an edge in the program is declared like this: CEdge edge(X + 0, Y + 0, EdgeDirectionRight);

CEdge Class

The CEdge class provides a way to encapsulate the location of specific edges within a cycle. This includes the (X, Y) coordinate of the specific edge on the plane, as well as the direction of that edge (described above). The functions encapsulated in this class are described below.

TurnLeft() => Turns the edge direction left, depending on the current direction.
TurnRight() =>  Turns the edge direction right, depending on the current direction.
TurnBack() => Turns the edge direction backwards, depending on the current direction.
Reverse() => Moves the (X,Y) coordinate of the edge one step forward, and then turns the edge direction backwards.

Difference

In Binary Images, a lot of this functionality is implemented via functions that are decoupled from the variables of the operation. For example, to reverse an edge in the book you have to (page 6-63): int back[4]; Reverse(edge,back); However, in the program, that operation is encapsulated as a function of the C++ CEdge object. This is a common difference between C and C++ programming. CEdge back(edge); back.Reverse();

CCycle Class

The CCycle class provides an encapsulated location of a specific cycle in the image. One of the more important things to note is how the CCycle class stores difference representation of the Cycle in a linked list data structure. Each Cycle State has children and parents that can be accessed by the Next² and Prev² arrays. This way, the Cycle can be consistently updated (via merges and splits) throughout the programs computation. Also, there is another linked list, accessed by linkB and linkF, that provides links to different cycles in the image.

Active => Defines whether that Cycle is active in the computation.  Activeness is computed after a Simplify is selected.

Dim => The Dimension of the Cycle.

Area => The Area of the Cycle.

Difference

In Binary Images, the code is implemented in C, rather than C++. Because of this, the code in the book is not Object Oriented. Thus, a Cycle in the book is implemented by using Structs rather than objects. This is the books implementation (page 2-26): struct Cycle { struct Cycle next²; // it may split int Dim; // dimension // pointers to other current struct Cycle linkF, linkB; // cycles on the list, forward and back}; In the program, the code is Object Oriented, thus it is implemented with objects. Also, it should be noted that in the Book, the Cycle State linked list can only move forward (there is a Next, but not a Prev). In the program, a double linked list is used, so a Prev is available.

CMemoryManager Class

The general goal of this class is to provide a more elegant way to allocate memory to the CCycle objects. This is done because each allocated CCycle is stored in a CArray. Because of this, allocating a new Object requires some logic. Think of this class as a thin Builder class with some logic.

Difference

Because the program is implemented in C++ and the book is implemented in C, the book really had no reason to have this logic. However, due to the added functionality of the system, the program needs this class to store all allocated objects.

CBinaryAnalyzer Class

This is the class that actually does the analysis of the Binary Image. There are some functions within this class that are very important to the functionality of the system. Some of the main functions are:

GiveCycle(), GetCycle(), AttachCurrCycle(),DetachCurrCycle(), CreateCycle(), StepForward(), TraverseCycle(), SplitCycle(),   MergeCycle(), AddCell(), AddEdge(), and AddVertex().  Below is an explanation of the functionality of each.

GiveCycle()

This function assigns a given edge to a given cycle. To accomplish this, each edge is assigned an ID (determined by a hash function). Each hash value is used as an index to an array called EdgeToCycleArr. The value assigned to the index of the array is the specified Cycle.

GetCycle()

This function searches through the EdgetoCycleArr array in order to find a cycle to the specified edge. Once a cycle is found, this function iterates through the different States of that cycle in order to get the complete Cycle“ in other words, the cycle that includes any Merges or Sorts that may have been part of the computation at that point.

AttachCurrCycle()

This function attaches a specific cycle to the list of Cycles. These different cycles are accessed through linkF and linkB.

DetachCurrCycle()

This function detaches a specific cycle from the list of Cycles.

CreateCycle()

This function creates a cycle for a specified edge. The function handles all of the memory allocation, edge assignment, etc.

Difference

Binary Images does not have the following if statement in the CreateCycle() function: if (edge.Direction != EdgeDirectionNone){CEdge back(edge); back.Reverse();GiveCycle(back, pCycle);} The explanation for this code is as follows: // When a 'physical' edge is added, both 'algebraic' // edges, back and forth, are marked as // current/active. So let's mark the reversed edge as// current. This code is not in the Book.

StepForward()

The StepForward() command moves the (X,Y) coordinate one position in the direction of the EdgeDirection variable.

Difference

Binary Images's implementation of the StepForward function differs greatly from the program's implementation. As far as I can tell, these two functions accomplish the same thing, but I plan to investigate this further.

TraverseCycle()

This function traverses the entire cycle by picking a starting edge and following that edge along the outer part of the cycle until the initial edge is computed again.

Difference

Binary Images's implementation of the TraverseCycle function differs greatly from the program's implementation. As far as I can tell, these two functions accomplish the same thing, but I plan to investigate this further.

SplitCycle()

This function splits two cycles, creating two sons and adjusting the Cycle State linked list accordingly.

Difference

I don't know how much it matters, but it seems that the next[0] and next[1] assign two different cycles, depending on which version you look at (Binary Images or program). Also, the way the betti numbers are assigned is different, depending on the version.

MergeCycles()

This function merges two cycles, creating a son and adjusting the linked list accordingly.

Difference

The way the betti numbers are assigned is different, depending on the version.

AddEdge()

This function adds an edge to the in memory structure of the image. This includes deciding when to merge/split cycles with other cycles.

AddCell()

This function adds a cell, which is a collection of four points with four edges. This function does the necessary memory management and cycle assignment.

AddVertex()

This function takes and (X,Y) coordinate, makes a cycle out of it, and adds it to the in memory lookup structures.