Creating a graph from a image and using Djikstra to find the best path
Explicação em português
https://www.canva.com/design/DAG51upKvTg/RuAzwRUSbGXxnpSzzuEkkg/view?utm_content=DAG51upKvTg&utm_campaign=designshare&utm_medium=link2&utm_source=uniquelinks&utlId=hc2992b2a68
----------------------------------------------------------------------------------------
🚀 Technologies
*Java -programming language
*Java Swing - GUI framework for visualization
*AWT (Abstract Window Toolkit) - graphics engine
*ImageIO - Reading and writing image files
*Custom Graph Algorithms - Pathfinding and segmentation
----------------------------------------------------------------------------------------
✨ Features
🖼️ Image Processing: Converts images to graph representations
🎯 Automatic Marker Detection: Identifies the start(green) and the end(red)
🔗 Region Segmentation: Uses Union-Find algorithm to group connected components on the graph
🗺️ Pathfinding: Implements Dijkstra's algorithm for shortest path
🎨 Visualization: Color-coded region display with random coloring
📊 Interactive GUI: Real-time animation and information display
⏱️ Performance Metrics: Execution time tracking
----------------------------------------------------------------------------------------
🔄 The Process
- Image Loading & Preprocessing
2. Marker Detection
-Green pixels → Start point
-Red pixels → End point
3. Region Segmentation
Union-Find algorithm connects adjacent pixels
-connect regions = pixels with the same RGB sum
Generates segmented matrix
4. Graph Construction
Regions become graph vertices
Adjacent regions create edges
Distance between region centers as edge weights
5. Pathfinding
Dijkstra's algorithm finds shortest path
Animated visualization of the path discovery
----------------------------------------------------------------------------------------
🛠️ How I Built It
*Main.java
-Application controller
-workflow manager
*LendoUmaImagem.java
-Image reader (with Image.IO)
-RGB matrix converter (hexadecimal -> binary)
*ProcessandoImagem.java
-matrix preprocessing
-binarization through RGB sum (three-dimensional matrix -> two-dimensional matrix)
*AlgoritmoUnionFind.java
-Region segmentation (every connected segment with the same RGB sum have it own value)
-Union-Find
*Grafo.java
-Graph construction (every adjascent point with different value became an edge)
-Dijkstra's algorithm (use the distance between the central point of each vertice)
*telaNova.java
-Swing-based GUI
-animation (using the Dijkstra's result)
*VariaveisGlobais.java
-Global state management
----------------------------------------------------------------------------------------
📚 What I Learned
-Technical Skills:
*Graph Theory
Practical implementation of Union-Find and Dijkstra
*Image Processing
RGB manipulation, pixel analysis, matrix operations
*Java Swing
Building interactive desktop applications
*Software Architecture
Modular design and separation of concerns
-Problem-Solving Insights:
*Handling large image matrix efficiently
*Debugging complex graph algorithms
*Creating intuitive visualizations for algorithmic processes
*Managing state across multiple processing stages
----------------------------------------------------------------------------------------
🔧 How It Can Be Improved
*Error Handling
create more areas to handle error (with Try and Catch)
*Performance Optimizations
Optimize memory usage in matrix operations
Optimize the code flow
*Support for multiple image formats (JPG, BMP, etc.)
*Support images with a gradient
*let the user define the weight of each vertice
*Exportable reports and statistics
*UI/UX Improvements
create a interactive panel to choose the image
Progress indicators for long operations
----------------------------------------------------------------------------------------
🏃♂️ Running the Project
Prerequisites:
Java 17 or higher
Maven (for dependency management)
Installation & Setup:
-Clone the repository
-Compile the project
-Prepare image directory
-Run the application
Usage Instructions:
1.Launch the application
2.Select an image from the numbered list on the terminal
3.Use the GUI buttons to:
View the processed graph
See element information
Watch pathfinding animation
How to create a functional images:
-Include only one green and red point
-Use PNG format
-Ensure good contrast between regions and same RGB value
-Recommended size: 500x500 pixels
Design.sem.nome.2.mp4
----------------------------------------------------------------------------------------
José Miguel Milani
Status: finished
For questions or contributions, please open an issue or submit a pull request!