Split-remerge method for eliminating processing window artifacts in recursive hierarchical segmentation

A method of eliminating processing window artifacts occurring in a segmentation of data with spatial characteristics comprising the steps of:

• (a) implementing a recursive segmentation algorithm on the data thereby assigning data pixels comprising the data into regions, in a fashion that divides the data into subsections;
• (b) for pixels along a seam between data subsections determining whether a first pixel is more similar to its current region or to the region of a second pixel across the seam;
• (c) if the first pixel is determined to be more similar to the region of the second pixel across the seam by a predetermined threshold factor, then the second pixel's region is designated as a candidate region for assignment of the first pixel;
• (d) comparing a first region to every other region and if the similarity between a pair of regions a predetermined threshold then designating each of the pair of regions as a candidate region of the other;
• (e) for each first region with a candidate region, computing the similarity of pixels in the first region to the first region and to candidate regions of the first region;
• (f) if a pixel in the first region is more similar to a candidate region, designating said pixel as a split pixel;
• (g) if merges between spatially adjacent and non-adjacent regions have equal relative importance then merging the pixels designated as split pixels into the regions to which those split pixels are most similar;
• (h) if merges between spatially adjacent regions have greater importance than non-adjacent regions then designating each split pixel adjacent to a seam as contagious;
• (i) if a first split pixel not designated as contagious is most similar to a candidate region not designated as contagious, merging the first split pixel into that most similar candidate region;
• (j) if either the first split pixel or the most similar candidate region is designated as contagious, then designating both as contagious and deferring consideration of their merger at the present level of recursion;
• (k) returning to step (b) at a higher level of recursion until the top recursion level or a suitably small number of regions is achieved.

A method of eliminating window artifacts during the processing of a data set of pixels with spatial characteristics, wherein the data set is recursively divided into subsections and segmented into a plurality of regions comprising the steps of beginning below a top level of recursion and:

• (a) identifying first pixels along boundaries of the subsections at the current level of recursion;
• (b) designating the identified first pixels that are more similar to a second pixel along an adjacent boundary of another subsection as having a candidate region set including the second pixel's region;
• (c) setting each identified first pixel with a non-empty candidate region set as a separate region and designating each such region as a contagious region;
• (d) for each first region computing the dissimilarity of the first region with every other region and if the dissimilarity is less than a threshold value then including such other similar region in a candidate region set for the first region;
• (e) if a first region with a non-empty candidate region set is a contagious region then designating the most similar region of that first region's candidate region set as contagious;
• (f) if at the top recursion level, removing all contagious designations from regions;
• (g) if a first region is not contagious and the most similar region in its candidate region set is not contagious, then merging the first region and most similar candidate region;
• (h) unless at the top recursion level, returning to step (a) at a higher level of recursion until the number of regions is less than a predetermined number.

A computer software product for eliminating window artifacts in recursive segmentation of data with spatial characteristics wherein the computer software product comprises software instructions that enable a computer to perform predetermined operations and a computer readable medium bearing the software instructions, wherein the predetermined operations include:

• (a) implementing a recursive segmentation algorithm on the data thereby assigning data points comprising the data into regions, in a fashion that divides the data into subsections;
• (b) for points along a seam between data subsections determining whether a first point is more similar to its current region or to the region of a second point across the seam;
• (c) if the first point is determined to be more similar to the region of the second point across the seam by a predetermined threshold factor, then designating the second point's region as a candidate region for assignment of the first point;
• (d) comparing a first region to every other region and if the similarity between a pair of regions exceeds a predetermined threshold, then designating each of the pair of regions as a candidate region of the other;
• (e) for each first region with a candidate region, computing the similarity of points in the first region to the first region and to candidate regions of the first region;
• (f) if a point in the first region is more similar to a candidate region, designating said point as a split point;
• (g) if merges between spatially adjacent and non-adjacent regions have equal relative importance then merging the points designated as split points into the regions to which those split points are most similar;
• (h) if merges between spatially adjacent regions have greater importance than non-adjacent regions then designating each split point adjacent to a seam as contagious;
• (i) if a first split point not designated as contagious is most similar to a candidate region not designated as contagious, merging the first split point into that most similar candidate region;
• and
• (j) if either the first split point or the most similar candidate region is designated as contagious, then designating both as contagious and deferring consideration of their merger at the present level of recursion;

A computer system for eliminating window artifacts in recursively segmented data with spatial characteristics wherein the computer system comprises:

• a processor;
• and
• a memory that stores software instructions that are executed by the processor, the software instructions comprising:
• (a) implementing a recursive segmentation algorithm on the data thereby assigning data pixels comprising the data into regions, in a fashion that divides the data into subsections;
• (b) for pixels along a seam between data subsections determining whether a first pixel is more similar to its current region or to the region of a second pixel across the seam;
• (c) if the first pixel is determined to be more similar to the region of the second pixel across the seam by at least a predetermined threshold factor, then designating the second pixel's region as a candidate region for assignment of the first pixel;
• (d) comparing a first region to every other region and if the similarity between a pair of regions exceeds a predetermined threshold then designating each of the pair of regions as a candidate region of the other;
• (e) for each first region with a candidate region, computing the similarity of pixels in the first region to the first region and to candidate regions of the first region;
• (f) if a pixel in the first region is more similar to a candidate region, designating said pixel as a split pixel;
• (g) if merges between spatially adjacent and non-adjacent regions have equal relative importance then merging the pixels designated as split pixels into the regions to which those split pixels are most similar;
• (h) if merges between spatially adjacent regions have greater importance than non-adjacent regions then designating each split pixel adjacent to a seam as contagious;
• (i) if a first split pixel not designated as contagious is most similar to a candidate region not designated as contagious, merging the first split pixel into that most similar candidate region;
• and
• (j) if either the first split pixel or the most similar candidate region is designated as contagious, then designating both as contagious and deferring consideration of their merger at the present level of recursion;