## Warning: package 'ggplot2' was built under R version 3.6.2

Step 1 Gaussian kernal convolition

Because the following method I use will be sensitive to the noise, I use gaussian kenal convolution to smooth the graph. I iterate it for four times.

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

Step 2 Sobel Gradient

I use sobel operator to calculate the gradient of graph, in x axis and y axis.

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

Step 3, Find the edge

If the gradient for one point is the local maximum for its neighbor at that direction (for simplicity, we only use 8 possible directions), then this point will be regarded as an edge point, otherwise, the gradient will be regarded as zero.

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

Step 4, Possible edge

For those with biggest 50 gradients, they will be regarded as “hard edges”; denote the maximal garident as \(g_{max}\), then those with gradient bigger than \(\lambda g_{max}\) will be regarded as “soft edges”, because we are not quite sure about them.

Then we will searching the possible edge from “hard edges”, and the “soft edges” which are the neighborhoods of “hard edges” will be regarded as new “hard edges”. Searching stops when all the “hard edges” have been counted.

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

Step 5, Smooth the edge

We use median kernal to smooth the edges selected above. (This step is time consuming in real application and not necessary)

Time complexity: \(O(N^2*c)\), where c is the time spent on sorting and getting the median for 9 points, space complexity: \(O(N^2)\)

Step 6 Simple inference about inner points

For an ideal closed smooth curve, if we travel from left to right, then:

when we are outside the curve/circle, we have gone through the curve for odds times

when we are inside the curve/circle, we have gone through the curve for even times.

Of course, sometimes when there exists noise, we will get some band regions that we are not quite sure.

(Another possible method is using Breadth First Search to traverse all the points inside, starting from an insdie point. But under some condition the curve is not closed, thus I don’t apply this in the end. )

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

Step 7 Possible inner point, grow until meeting the outer points or edge

Since there are some band regions we are not sure, we will apply the similar method (in step 4, finding possible edges) to find possible inner points, the growing will stop when we meet outer points or edge.

And after growing is ended, we will delete the edge points from our curve sets in case of getting a too big curve.

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

## [1] 0.2417528

Step 8, Grow with inference

And we allow the graph to “grow” twice:

For every point, we will calculate its probability of belonging to two groups:

\[ \pi_1 \propto \frac{1}{1 + (x_{ij}-\mu_1)^2},\pi_0 \propto \frac{1}{1 + (x_{ij}-\mu_0)^2}, \pi_1 + \pi_2 = 1\]

For points classifies as group 1 (inside), it has \(\pi_0\) to switch group.

For points which are neighborhoods of inside group and classifies as group 0 (outside), it has \(\pi_1\) to switch group.

Time complexity: \(O(N^2 \times t)\) , where t = 2 is the repeat time, space complexity: \(O(N^2)\)

Step 9, Smooth the final result

We only choose the points with at least three inside points neighborhood as our final result, which is also not necessary. But it is helpful to get a smooth result.

Time complexity: \(O(N^2)\) , space complexity: \(O(N^2)\)

Visualization

For \(\mu_1 = 2\), \(\mu_0 =0\), sd = 1:

## mean absolute value: 0.126884