Определение особенностей в изображениях с помощью кластерного анализа

1. Наименьший кластер — минимальное количество точек, необходимое для рассмотрения группы точек кластера.
2. Cluster Distance — Максимальное расстояние между двумя точками, чтобы они были «плотными», чтобы их можно было рассмотреть для включения в кластер.

1. Возьмите каждую непосещенную точку изображения в пространстве исходного изображения
2. Отметьте точку как посещенную, а затем найдите все соседние точки
3. Соседние точки определяются путем вычисления расстояния между данной точкой и всеми остальными точками и сохранения только тех из них, которые находятся в пределах расстояния кластера.
4. Тогда, если у нас будет больше соседних точек, чем размер самого маленького кластера, мы обнаружим, что у нас новый кластер!
5. Создайте новый кластер и добавьте его в наш список кластеров, а затем добавьте указанную точку изображения в новый кластер.
6. Теперь мы можем расширить наш недавно созданный кластер!
7. Отсюда мы начинаем исследовать каждую точку изображения, с которой наша данная точка изображения плотно связана. В основном, пришло время проследить за сухарями до конца дороги.
8. Теперь давайте перейдем ко всем соседним точкам, которые мы еще не посещали, и добавим их в наш список «связанных точек изображения, которые необходимо исследовать».
9. Используя этот список, мы будем отслеживать точки, с которых мы начали, а также любые новые, которые необходимо изучить. Когда мы найдем точки, которые соответствуют нашим критериям, мы добавим их в наш текущий кластер.
10. Мы также должны пометить эти точки как поставленные в очередь для посещения, чтобы они не добавлялись в наш список несколько раз и тратили время.
11. Теперь, пока у нас еще есть соединенные точки изображения, которые нужно исследовать
12. Возьмите один из них, и если он еще не посещен, давайте начнем наш визит!
13. Начните визит, отметив точку изображения как посещенную
14. Добавьте эту точку в наш кластер
15. Найдите все соседние точки изображения для этой точки изображения, которая сама является соседней точкой изображения для точки изображения, которую мы получили на шаге 1! Сложно много?
16. Добавьте все эти новейшие соседние точки изображения в наш список «связанных точек изображения, которые необходимо исследовать», ЕСЛИ:
    
    1. Они еще не посещались
    2. Они еще не стоят в очереди для посещения
    3. Их больше, чем наименьший размер кластера.
17. Поскольку мы добавляем точки изображения в список «связанных точек изображения, которые необходимо исследовать», пометьте их как «Очередь для посещения».

public class ImagePoint
{
    public bool Visited;
    public int X;
    public int Y;
    public byte R;
    public byte G;
    public byte B;
    public byte A;

    public bool AlreadyFoundCandidates;
    public bool QueuedForVisit;

    public double DistanceTo(ImagePoint other_point)
    {
        return Math.Sqrt(
                Math.Pow(other_point.R - this.R, 2)
            + Math.Pow(other_point.G - this.G, 2)
            + Math.Pow(other_point.B - this.B, 2)
            + Math.Pow(other_point.A - this.A, 2)
            + Math.Pow(other_point.X - this.X, 2)
            + Math.Pow(other_point.Y - this.Y, 2));
    }
}

private static IEnumerable<DensityCluster> GetImageClusters(List<ImagePoint> original_image_space, double cluster_distance, int smallest_cluster)
{
    var clusters = new List<DensityCluster>();
    foreach (var image_point in original_image_space.Where(x => !x.Visited))
    {
        Console.WriteLine("Finding cluster for image point @ ({0}, {1})", image_point.X, image_point.Y);
        image_point.Visited = true;
        var neighboring_points = FindNeighboringPointsFor(original_image_space, image_point, cluster_distance);
        if (neighboring_points.Count >= smallest_cluster)
        {
            var cluster = new DensityCluster();
            clusters.Add(cluster);

            cluster.Add(image_point);

            Console.WriteLine("Added to cluster... searching around @ ({0}, {1})", image_point.X, image_point.Y);

            ExpandCluster(cluster, original_image_space, neighboring_points, cluster_distance, smallest_cluster);
        }
    }

    clusters = clusters.Where(x => x.Points.Count >= smallest_cluster).ToList();
    return clusters;
}

private static void ExpandCluster(DensityCluster cluster,
                                    IEnumerable<ImagePoint> original_image_space,
                                    IEnumerable<ImagePoint> neighboring_points,
                                    double cluster_distance,
                                    int smallest_cluster)
{
    foreach (var neighboring_point in neighboring_points)
        neighboring_point.QueuedForVisit = true;

    var connected_image_points_to_be_examined = new Stack<ImagePoint>(neighboring_points.Where(x => !x.Visited));
    while (connected_image_points_to_be_examined.Count > 0)
    {
        var connected_image_point_to_be_examined = connected_image_points_to_be_examined.Pop();
        if (!connected_image_point_to_be_examined.Visited)
        {
            connected_image_point_to_be_examined.Visited = true;
            cluster.Add(connected_image_point_to_be_examined);
            var distant_neighbor_image_points = FindNeighboringPointsFor(original_image_space,
                                                                            connected_image_point_to_be_examined,
                                                                            cluster_distance);
            if (distant_neighbor_image_points.Count >= smallest_cluster)
            {
                foreach (
                    var distant_neighbor_image_point in
                        distant_neighbor_image_points.Where(x => !x.Visited && !x.QueuedForVisit))
                {
                    distant_neighbor_image_point.QueuedForVisit = true;
                    connected_image_points_to_be_examined.Push(distant_neighbor_image_point);
                }
            }
        }
    }
}

public static IList<ImagePoint> FindNeighboringPointsFor(IEnumerable<ImagePoint> image_points, ImagePoint image_point, double cluster_distance)
{
    return image_points.Where(x => x.DistanceTo(image_point) <= cluster_distance).ToArray();
} 

public static void CreateComponentImages(IEnumerable<DensityCluster> clusters, int image_width, int image_height, string filepath_to_save_component_images_to)
{
    var counter = 0;
    foreach (var cluster in clusters)
    {
        Console.WriteLine("Saving cluster {0} to file", counter);
        using (var image = new Bitmap(image_width, image_height))
        {
            foreach (var image_point in cluster.Points)
            {
                image.SetPixel(image_point.X, image_point.Y,
                                Color.FromArgb(image_point.A, image_point.R, image_point.G, image_point.B));
            }

            image.Save(
                filepath_to_save_component_images_to + "_group_" + counter + ".bmp");
        }
        counter++;
    }
}

Что можно сделать лучше?

Мой алгоритм занимает порядка нескольких часов для работы с любым изображением среднего размера. Некоторое простое профилирование показало, что моя опора на 

image_points.Where (x => x.DistanceTo (image_point) <= cluster_distance) .ToArray ()

Там, где находится узкое место (на самом деле в выражении Where). Если у кого-то есть какие-то конкретные советы о том, как я могу кэшировать эти данные, чтобы уменьшить время выполнения, я весь в ушах. (РЕДАКТИРОВАТЬ: очевидно, что использование KD-Tree значительно помогает при поиске ближайшего соседа, как этот.

Окончательные результаты!

В качестве финального теста я запустил алгоритм для этого мема:

 

И вот несколько примеров изображений, на которые оно было разбито:

Кусочек круговой диаграммы

 

Водяной знак мема:

Вот и все! Спасибо за чтение!