## Automated Seed Placement

One of the main problems with creating a C++ port was coding how to do seed placement. In the Ncorr *Matlab* software, the user places the seeds manually. This works well with a good GUI, but programmatically it results in some difficulties. Furthermore, the multithreaded approach used in Ncorr involves partitioning the region of interest (ROI) into multiple contiguous regions (which are computed in parallel), and therefore each partition must be seeded.

In the C++ port, I've written an automated way to place seeds. It is not completely robust, but it works pretty well for most good data sets. The way this is done is to first form a "partition diagram". The partition diagram is formed by performing a binary space partition (a recursive algorithm). At each step, the goal is to divide the area in half as best as possible. Once divided, each of the divided regions are again divided in half as best as possible in a divide and conquer type algorithm until the partitioning is finished.

The area is divided by first finding the centroid. Once the centroid is found, the major and minor axes are found by using the image moments. The algorithm attempts to split the region across a line formed at the centroid and in the direction of the *minor* axis. This will divide the region in such a way that it is more "full". Note that there are some edge cases to account for the possibility that the split region is not contiguous (look at the ncorr.cpp file for more details on how the algorithm works), but the main idea is that the split is done across the *minor* axis when possible.

An example of a ROI (using the plate hole sample set from SEM's DIC challenge) split 16 times is shown below:

By visual inspection, the regions seem pretty evenly divided and they are "full" and contiguous. Next, a signed distance array (SDA) is formed from the partition diagram. The signed distance array gives, at each point, the distance to the boundary of each partition. The SDA is basically just used to find the position of the max distance from the boundary which is a good candidate for seed positions.

The algorithm for seed position and placement in the C++ port of Ncorr calculates four seeds in each partition, and then keeps the seed with the *lowest* correlation coefficient. One of the benefits of this approach is that there are no heuristic parameters used in selection of the seed. The best seed is used as the initial input to the RG-DIC algorithm.

So, to continue the example used above, if four threads are used in the DIC algorithm, the space is initially partitioned four times. Within each of these partitions, it is again partitioned four times (equivalent to partitioning the initial ROI 16 times). Then, an SDA is formed, and the max values of the SDA are found in order to determine the redundant seed positions. Each of the seed positions use fast normalized cross correlation followed by nonlinear optimization to compute the seed. Then, the seed with the lowest correlation coefficient is selected. An example of this (using the first two images of the plate hole data set) is shown below:

The brighter regions in the SDA are points with a higher distance from the boundary of the partition, so the brightest points are used as the initial seed positions, which are shown as white squares in the rightmost plot. The rightmost plot shows how the region is partitioned four times (assuming four threads are used). Each partition has four seeds which are calculated, and the best seed position has a circle around it, which is the seed used in the DIC algorithm.

So, the end result of the above analysis is that we have been able to partition the region evenly and "fully" to split the ROI to calculate it in parallel, and we have also tested somewhat evenly spaced redundant seeds within each partition (automatically) and have found the best seed to use in the DIC analysis.