Доброе утро / день / вечер.
Итак, наш курс структур данных дал нам задание сегментировать изображение в оттенках серого в java, используя следующий алгоритм:
Вход: полутоновое изображение с P пикселей и числом R
Выход: изображение, сегментированное на R области
1. Сопоставьте изображение с первичным взвешенным графом.
2. Найдите MST графа.
3. Разрежьте MST по R - 1 наиболее дорогостоящим ребрам.
4. Назначьте средний вес вершин дерева каждой вершине в каждом дереве в лесу
5. Сопоставьте разделение с изображением сегментации
Дело в том, что они просто бросили нас в темноту. Они дали нам пакет jgraph, с которым у нас не было абсолютно никакого опыта (мы его никогда не изучали), практически говоря: «Иди и учись». Ничего нового.
Я собираюсь сделать это, создав класс для объектов vertix, который содержит координаты пикселя в дополнение к его значению, чтобы я мог добавить каждый из них как в график, так и в 2D-массив. Впоследствии я использовал массив для добавления взвешенных ребер между соседними вершинами, потому что java не может сказать, где в графе вершина на самом деле находится без ребер.
Впоследствии я использовал упакованный метод Краскала для минимальных остовных деревьев и arrayylist, чтобы обойти защищенный статус весов ребер в дереве следующим образом:
ArrayList<WeightedEdge> edgeList = new ArrayList<>(height*width*3);
KruskalMinimumSpanningTree mst4 = new KruskalMinimumSpanningTree(map4);
Set<DefaultWeightedEdge> edges = mst4.getSpanningTree().getEdges();
for (DefaultWeightedEdge edge : edges) {
edgeList.add(new WeightedEdge(edge, map4.getEdgeWeight(edge)));
}
edgeList.sort(null);
for (int i = 0; i < n; i++) {
map4.removeEdge(edgeList.get(edgeList.size()-1).getEdge());
}
Итак, теперь, когда я вырезал (R-1) самые дорогие ребра в графе, у меня должен остаться лес. И вот здесь я попал в очередной тупик. Как заставить программу проходить каждое дерево? Насколько я понимаю, мне нужен общий алгоритм обхода для посещения каждого дерева и присвоения среднего значения каждой вершине. Эта проблема? В пакете нет общего алгоритма обхода. И нет способа идентифицировать отдельные деревья.
Идею действительно легко понять и реализовать на бумаге. Проблемы заключаются только в том, что все это кодируется на java.
Извините, если это было беспорядочно или слишком долго, но я просто на грани своего остроумия и физических возможностей. Заранее спасибо.