In the paper "Flocks, Herds, and Schools: A Distributed Behavioral Model" by Craig W. Reynolds, he describes 'boids', an animal flocking/schooling approach.

We can implement something similar for determining the direction of the lines.

The paper describes how 'boids' attempt to implement natural animal behaviour, such as velocity matching, collision avoidance, and flock centering. We will try to implement such logic for the regions and ensure that 'similar' regions will align the direction of their contour lines.

Flocking

We will only implement a small component of the flocking algorithm. Unlike boids in motion, our regions are not in motion. Our regions are defined by the following characteristics: pixels composing the region, the average colour, the average intensity, and the adjacent regions.

For our implementation, we want adjacent regions that are 'similar' to have the same line contour directions. This would make it easier to visually identify similar regions.

To support this, we need the following:

1. Adjacency map for each region.
2. Properties map for each region that stores: average colour, average intensity, and line direction.

Adjacency map

We already produce an adjacency map. We can reuse that data structure. We generate the in the finishedImagedSLIC->genAdjacencyMap().

:( It turns out our region adjacency map was for the end points of lines, not for the actual regions.

Need to implement Region Adjacency map again. There is already a library to perform this transformation: https://vcansimplify.wordpress.com/2014/07/06/scikit-image-rag-introduction/

Average region intensity

We already produce the Average intensity map. This is generated quite early in the process: main --> SLICImage. However, in the current process we generate the Average intensity map based on the image produced from the Semantic Segmentation mask and the original greyscale image.

This needs to be changed. We need to utilize the original greyscale image to determine the Average Intensity Map.

** Changed to generate Intensity based on the original Greyscale image.

Average region colour

Utilize the same algorithm for determining the average region intensity to calculate the average region colour.

** Have the average region colour.

Colour difference

Now that we have the data structures, we need to effectively compare the colour differences between the regions. According to wiki, RGB is not the best colour space to determine the perceptual distance between different colours. CIELab is a the better choice for comparing the colour distance: https://en.wikipedia.org/wiki/Color_difference.

There is a package named colorMath that implements the deltaE: http://hanzratech.in/2015/01/16/color-difference-between-2-colors-using-python.html

Questions about CIELab:

1. Can we utilize the CIELab for segmentation?
   Answer: Attempting to segment using CIELab did not work very well. I suspect the SLIC algorithm expects to use RGB, not CIELab.

Direction flocking algorithm

We have all the components we need:

1. Region Adjacency
2. Region intensity
3. Region CIELab colour
4. Region direction based on Structure Tensor

Now need to iterate through each region and adjust angle appropriately.

In the original flocking algorithm, they simulated the following behaviours:

1. Collision avoidance
2. Velocity matching
3. Flock Centering

We can implement similar logic with minor changes:

1. Collision avoidance will be Difference Avoidance. Regions will repel each other if they are sufficiently different.
2. Velocity matching will be angle matching. Regions that are similar will attempt to match angles.
3. Flock centering is really a duplicate of Velocity matching in our case. Can it be used in a different manner to add value?

Averaging angles

Averaging angles can be problematic. Here are potential options: https://www.themathdoctors.org/averaging-angles/

The algorithm does a decent job of calculating the average angle. However, the algorithm doesn't consider both directions of the angles.

Each angle vector has two directions, the positive and negative direction. So when determining the average between two different angles, we need to take the average of the two closer directions.

May be able to use this option: https://stackoverflow.com/questions/1878907/the-smallest-difference-between-2-angles. This does work.

Now we can determine the minimal difference between two angles.

Determining which regions should adjust their angle

One we determine the colour differences between the regions, we have to select which regions will update their angle. The naive approach is to select some static value. However, this approach will not work generically across the board as the static threshold will likely be different for every image / segmentation.

Another approach is to calculate all the differences between the regions and then determine the 20th percentile. All regions that have differences below the 20th percentile are candidates for changing their angle.

Attraction has been implemented of region angles with similar colours.

Repel

Repel will be implemented similar to the Attraction. We will calculate the 80th percentile of all the adjacent region differences. Regions that have difference greater than the 80th percentile will be a candidate for the Repel operation.

The Repel operation will push the current region's angle will be averaged with the angle perpendicular to the adjacent region's angle.

**Repel functionality implemented.

Results of Attract / Repel

The algorithm currently implemented will check all adjacent regions. For each adjacent region, we calculate the colour difference. If the colour difference is below a certain threshold, the region angles will "attract" or attempt to align. If the colour difference is above a certain threshold, the region angles will "repel", or more specifically the current region will move toward the perpendicular angle of the adjacent region.

Results for Stripes

The results for stripes lines illustrates some failings with this approach. The "PRE" image is the initially generated lines generated based purely on the Structure Tensor information.

There are several observations:

1. The angles of the PRE lines are only based on the Structure Tensor information. The lines follow the contour of the lines relatively well.
2. The angles of the POST image have indeed rotated. However, some of regions along the dark lines rotated.

Our theory is that the Repel functionality caused the problem. Looking at the partition below, we have 9 regions.

Let us start with regions D, E, and F having horizontal lines. These regions also have similar colour values. Regions A, B, C, G, H, and I have different colour values from D, E, and F.

When we apply the Attract/Repel algorithm, the following will happen:

1. Region A will have two adjacent regions: B and D. It will be attracted to B and repelled by D.
2. Region B will have three adjacent regions: A, C, and E. It will be attracted to A and C while being repelled by E.
3. Region C will have two adjacent regions: B and F. It will be attracted to B and repelled by F.
4. Region D will have three adjacent regions: A, E, and G. It will be attracted to E and repelled by A and G.
5. Region E will have 4 adjacent regions: B, D, F, and H. It will be attracted to D and F, but repelled by B and H.
6. Region F will have 3 adjacent regions: C, E, and I. It will be attracted to E, but repelled by C and I.

With that information, we now consider several cases:

Case 1: A, B, C, G, H, and I start horizontal. D, E, and F start horizontal.

Region D

Because it is attracted to region E, it will have a force trying to keep it horizontal. However, regions A and G will be repelling forces. Since regions A and G are horizontal, the repel effect will attempt to make region E vertical. Over time, assuming nothing else changes, region E would approach some angle between vertical and horizontal.

Region E

Region E will be attracted by D and F and will attempt to keep it horizontal. Regions B and H will attempt to repel region E and force it to be vertical. Over time, region E would end up with angle 45 degrees.

Case 2: A, B, C, G, H, and I start vertical. D, E, and F start horizontal.

Region D

Region D would be attracted to Region E and will attempt to keep it horizontal. However, regions A and G would repel region D. Since regions A and G are vertical, they would try to force region E to be horizontal. This is a stable situation for region E.

Region E

Region E would be attracted by D and F, keeping it horizontal. Regions B and H will repel region E, keeping it horizontal. Again, this is a stable situation.

Unfortunately, we will not always have two sets of regions that have perpendicular angles. With any other combination of angles, the results will fall between case 1 and case 2.

More complex example

The examples above is somewhat simplistic. Here is another example. Region A would have four supporting regions that would reinforce its angle while it only has two regions that repel it. As a result, Region would retain its angle. Regions F and G would forced to a perpendicular angle.

Priority

One option to prevent deadlock is apply some form of priority.

Intensity priority

When performing the repel operation, we can utilize the region intensity as the priority value. If the intensity of the current region is darker than the intensity of the adjacent region, do not adjust the angle of the current region. However, if the intensity of the adjacent region is darker than the current region, adjust the angle of the current region.