Вопрос или проблема
Графические визуализаторы, такие как Graphviz, могут взять формальное представление узлов и рёбер графа и создать из них изображение. Какую программу или библиотеку программирования можно использовать для обратной задачи; то есть для распознавания изображения графа и получения его формального представления? Меня интересует программное обеспечение для распознавания как битмап-изображений, так и более простая задача распознавания графа из SVG, который следует стандартной структуре. В любом случае, ограничения на внешний вид графа допустимы. Также мне требуется только извлечение связей между узлами и рёбрами, а не других элементов, таких как текстовые метки узлов.
Это можно сделать с помощью OpenCV и некоторого пользовательского кода на C или Python (это не очень распространённая задача).
Ответы на этот вопрос очень хорошо объясняют, как это сделать на C.
Для готового решения можете взглянуть на NEFI:
В Mathematica есть встроенная функция под названием MorphologicalGraph.
Программное обеспечение для анализа изображений с открытым исходным кодом Fiji также может это делать. Примерные шаги:
- Сглаживание изображения, если потребуется
- Применение порогового значения, чтобы сделать изображение бинарным
- Обработка -> Бинарное -> Скелетизация
- Анализ -> Скелет -> Анализ скелета, отметьте Показать подробную информацию. Когда появится таблица, сохраните её в формате CSV.
Если ваше изображение является векторной графикой (например, SVG), вы можете конвертировать его в PDF с помощью rsvg-convert и загрузить на Graph Harvester (прямая ссылка, короткая ссылка). Части исходного кода доступны на GitHub.
Если у вас есть только битмап, вы можете использовать этот скрипт на Python, чтобы преобразовать его в формат graph6 и graphml. Однако иногда он создаёт некорректные графы:
| Преобразовано корректно ✅ | Преобразовано в неверный граф ❌ |
|---|---|
 |
 |
.
Ответ или решение
Обратная визуализация графов — это задача, которая, в отличие от создания изображения графа из его формального представления, требует распознавания структуры графа из изображения, чтобы затем создать его формальное представление. Существует несколько методов и инструментов, которые позволяют решить эту задачу, в том числе использование библиотек обработки изображений, таких как OpenCV, а также специализированные программные решения и готовые библиотеки.
Теория
Задача обратной визуализации графов отличается от прямой визуализации тем, что здесь мы имеем дело не с готовым структурированным набором данных о вершинах и ребрах графа, а с его изображением. Такая задача требует применения алгоритмов компьютерного зрения и обработки изображений для идентификации элементов графа — вершин и рёбер, а также для определения связей между ними. Наиболее сложным аспектом этого процесса является правильная интерпретация графа в условиях, когда изображение может быть неточным, с искажениями, или содержать шуми, которые усложняют распознаванием формы и контуров.
Пример
Классическим примером применения алгоритмов для обратной визуализации графов является использование библиотеки OpenCV. Она предоставляет множество инструментов для предобработки изображений, таких как фильтрация, бинаризация и морфологические преобразования. Например, можно применить алгоритм скелетизации, который превращает изображение в однопиксельные линии, представляющие собой рёбра графа, после чего уже возможно выделение узлов графа и связи между ними.
Также стоит отметить проект NEFI, который является более комплексным решением для обратной визуализации графов, предоставляющим как функционал обработки изображений, так и возможности для анализа и извлечения структуры графа.
Применение
Применение перечисленных инструментов начинается с предобработки изображения для улучшения его качества и устранения шума. Используя OpenCV, вы можете, например, использовать гауссово или медианное сглаживание для снижения шумов, а затем применять бинарное пороговое преобразование, чтобы выделить контуры. Далее алгоритмы скелетизации и анализа скелета позволяют извлечь основные структуры графа.
Если ваша задача связана векторными изображениями, например, в формате SVG, более подходящим решением может быть использование инструмента Graph Harvester, который позволяет конвертировать SVG в формальное представление графа, предварительно преобразовав его в формат PDF с помощью rsvg-convert.
Для работы с растровыми изображениями решения могут включать использование скриптов на Python для конвертации изображений в форматы graph6 и graphml. Однако следует учитывать, что такие инструменты могут иногда выдавать неточные результаты, что требует дополнительной ручной валидации и коррекции.
В заключение, задача обратной визуализации графов требует комплексного подхода, включающего методы обработки изображений и анализа структур графов. Открытые библиотеки, такие как OpenCV, специализированные проекты, такие как NEFI и Graph Harvester, позволяют автоматизировать значительную часть работы, но в сложных случаях возможны ошибки, которые потребуют от специалиста ручной обработки и коррекции результатов.