Skip to content
BranchesTags

Repository files navigation

SeamCraft

C++17 SFML Platform Compiler License Milestone

An interactive desktop application for content-aware image resizing using Seam Carving and Dijkstra's Algorithm.

Features • Visual Demo • Pipeline & Architecture • Controls • Algorithms • Build Guide • Contributing

GitHub Repository Topics

Recommended GitHub repository tags: cplusplus • sfml • seam-carving • dijkstra-algorithm • image-processing • computer-vision • content-aware-image-resizing • graph-algorithms • desktop-application • cpp17 • sobel-filter • algorithms

Overview

SeamCraft is a modular, educational C++17 application designed to demonstrate the fundamentals of Content-Aware Image Resizing (Seam Carving). Unlike traditional scaling or cropping (which distort or discard important visual content), seam carving identifies and removes dynamic "seams"—paths of least visual importance traversing from the top of the image to the bottom.

The project is currently at Milestone 6, supporting interactive image loading, Sobel energy calculation, grayscale energy map rendering, pixel graph generation, Dijkstra shortest-path seam detection, live seam overlay visualization, dynamic single-seam carving, continuous auto-carving, and sequential PNG export.

Visual Demonstration

Live Seam Carving in Action

Seam Carving Demo

Step-by-Step Seam Carving Pipeline

1. Original Image 2. Sobel Energy Map 3. Dijkstra Shortest Seam
Original Image Energy Map Seam Overlay
Input photo loaded with aspect-ratio fitting High energy = edges/details; Low energy = smooth areas Optimal red seam (lowest total energy path)

Pipeline & Architecture

1. Seam Carving Processing Pipeline

flowchart TD
    A[Input Image: PNG / JPG] --> B[Grayscale Luminance Conversion]
    B --> C[Sobel Operator: Horizontal & Vertical Gradients]
    C --> D[Energy Map: E = sqrt Gx² + Gy²]
    
    D --> E1[Min-Max Normalization]
    E1 --> E2[Grayscale Energy Visualization]
    
    D --> F[Pixel Graph Construction: W x H Nodes]
    F --> G[Dijkstra Shortest Path Solver]
    G --> H[Minimum-Energy Vertical Seam]
    
    H --> I1[Seam Overlay Renderer: Red Path]
    H --> I2[Seam Remover: Shift Pixels Left]
    
    I2 --> J[Carved Image: Width - 1]
    J -->|Loop for Continuous Auto-Carving| B
    J -->|Save with 'P' Key| K[Export to assets/output/carved_xxx.png]
Loading

2. Modular System Architecture

SeamCraft strictly enforces the Single Responsibility Principle. Classes are decoupled; high-level orchestration and state management are handled solely by the Application class.

graph TD
    App[Application Orchestrator]
    
    App --> Win[Window<br/><i>SFML RenderWindow, Events & Frame Rate</i>]
    App --> ImgMgr[ImageManager<br/><i>Loads, caches, resets, scales & saves images</i>]
    App --> ECalc[EnergyCalculator<br/><i>Computes 2D Sobel energy map</i>]
    App --> ERender[EnergyRenderer<br/><i>Normalizes & renders grayscale energy texture</i>]
    App --> PGraph[PixelGraph<br/><i>Constructs directed vertical DAG from energy map</i>]
    App --> DSolver[DijkstraSolver<br/><i>Finds shortest seam via min-heap priority queue</i>]
    App --> SRender[SeamRenderer<br/><i>Generates red seam overlay sprite</i>]
    App --> SRemover[SeamRemover<br/><i>Removes seam pixels & shifts adjacent rows</i>]
    App --> TFD[tinyfiledialogs<br/><i>Native cross-platform open dialog picker</i>]
Loading

3. Pixel Graph Connectivity (Vertical Seam Topology)

Each pixel at coordinate $(x, y)$ corresponds to a unique graph node nodeId = y * width + x. Directed edges connect downward to its 3 immediate neighbors in row $y + 1$:

graph TD
    P["Pixel (x, y)<br/>Node ID: y * W + x"]
    DL["(x - 1, y + 1)<br/>Down-Left"]
    D["(x, y + 1)<br/>Down"]
    DR["(x + 1, y + 1)<br/>Down-Right"]

    P -->|"Weight: Energy(x-1, y+1)"| DL
    P -->|"Weight: Energy(x, y+1)"| D
    P -->|"Weight: Energy(x+1, y+1)"| DR
Loading

Edge weights correspond to the energy value of the destination pixel.

Features

  • Interactive Desktop Window: Responsive 1200x800 SFML 3.0.2 window running at 60 FPS.
  • Image Format Support: Load, display, and resize standard PNG, JPG, and JPEG images.
  • Native File Dialog: Cross-platform open file picker via vendored tinyfiledialogs.
  • Smart Aspect Ratio Scaling: Centers images and scales down large images without distorting aspect ratios or upscaling smaller images.
  • Sobel Energy Calculation: Computes 2D floating-point energy maps using perceptual luminance and 3x3 Sobel gradient kernels.
  • Energy Map Visualizer: Real-time min-max normalized grayscale rendering toggled on demand.
  • Pixel Graph Engine: Deterministic $O(1)$ coordinate-to-node mapping and vertical graph construction.
  • Dijkstra Shortest Path Finder: Computes the global minimum-energy vertical seam using a min-heap priority queue with lazy deletion.
  • Automated Seam Validation: Automatically verifies seam length, boundary rows, and adjacent column transitions ($|\Delta x| \le 1$).
  • Live Seam Overlay: Bright red overlay aligned with the active image sprite.
  • Interactive Seam Carving: Step-by-step width reduction with the C key.
  • Continuous Auto-Carve Mode: Real-time progressive seam removal with the Space key.
  • Image Export: Save carved images with sequential auto-numbering (assets/output/carved_001.png) using the P key.
  • Original Image Reset: Instant revert to original uncarved image with the R key.

Controls

Key Action Description
O Open Image Opens a native file dialog to select a PNG, JPG, or JPEG image.
R Reset Image Restores the image back to its original state and dimensions.
E Toggle Energy Map Toggles between the original image and the normalized grayscale energy map.
S Toggle Seam Overlay Shows or hides the bright red minimum-energy seam overlay.
C Carve Single Seam Removes the active vertical seam, reducing image width by 1 pixel.
Space Continuous Auto-Carve Starts / stops continuous seam carving at fixed intervals.
P Save Carved Image Exports the current carved image to assets/output/carved_XXX.png.

Algorithmic Deep Dive

1. Energy Calculation (Sobel Filter)

To identify unimportant pixels, each pixel's energy is calculated from its local gradient:

  1. Grayscale Luminance: $$\text{Luminance}(x, y) = 0.299 \cdot R + 0.587 \cdot G + 0.114 \cdot B$$

  2. Sobel Convolutions: $$K_x = \begin{bmatrix} -1 & 0 & +1 \ -2 & 0 & +2 \ -1 & 0 & +1 \end{bmatrix}, \quad K_y = \begin{bmatrix} -1 & -2 & -1 \ 0 & 0 & 0 \ +1 & +2 & +1 \end{bmatrix}$$

  3. Gradient Magnitude (Energy): $$E(x, y) = \sqrt{G_x(x, y)^2 + G_y(x, y)^2}$$

Boundary pixels outside the image bounds utilize replicated border padding.

2. Energy Map Normalization

Floating-point energy values are linearly mapped to 8-bit grayscale ($0 \text{ to } 255$) using min-max normalization:

$$\text{Gray}(x, y) = \text{round}\left( 255 \times \frac{E(x, y) - E_{\min}}{E_{\max} - E_{\min}} \right)$$

3. Pixel Graph Representation

  • Node Indexing: $$\text{nodeId} = y \times W + x$$ $$x = \text{nodeId} \pmod W, \quad y = \lfloor \text{nodeId} / W \rfloor$$

  • Directed Edges: For each pixel $(x, y)$, directed edges exist to valid pixels $(x - 1, y + 1)$, $(x, y + 1)$, and $(x + 1, y + 1)$.

  • Edge Weight: Weight equals the energy value of the destination node: $$w(u, v) = \text{Energy}(v)$$

4. Dijkstra Shortest-Path Seam Search

  1. Initialization: Seed all top-row nodes ($y = 0$) into a min-heap priority queue with initial distance $d[u] = \text{Energy}(u)$.
  2. Relaxation: Settle nodes in order of lowest tentative distance. For each neighbor $v$: $$\text{if } d[u] + w(u, v) &lt; d[v] \implies d[v] = d[u] + w(u, v), \quad \text{predecessor}[v] = u$$
  3. Termination: Extract the bottom-row node ($y = H - 1$) with the lowest cumulative distance.
  4. Reconstruction: Backtrack along the predecessor array from the chosen bottom node to the top row to construct the ordered seam array.

5. Seam Removal

To shrink the image width by 1 pixel:

  • Allocate a new image buffer of dimensions $(W - 1) \times H$.
  • For each row $y \in [0, H-1]$ and seam position $x_{\text{seam}}$:
    • Copy pixels $x &lt; x_{\text{seam}}$ directly: $\text{dst}(x, y) = \text{src}(x, y)$.
    • Shift pixels $x \ge x_{\text{seam}}$ one column left: $\text{dst}(x, y) = \text{src}(x + 1, y)$.
  • Recompute energy map, rebuild pixel graph, and solve for the new shortest seam.

Tech Stack & Prerequisites

  • Language: C++17
  • Graphics & Windowing: SFML 3.0.2
  • Toolchain: MSYS2 UCRT64 (GCC 16.1.0, GDB)
  • File Dialog: tinyfiledialogs (vendored C library)
  • Platform: Windows 11
  • IDE: Visual Studio Code

Installing Prerequisites (MSYS2 UCRT64)

Open the MSYS2 UCRT64 terminal and run:

pacman -S --needed mingw-w64-ucrt-x86_64-gcc mingw-w64-ucrt-x86_64-gdb mingw-w64-ucrt-x86_64-sfml

Folder Structure

SeamCraft/
├── assets/
│   ├── icons/
│   ├── images/
│   │   ├── demonstration.gif
│   │   ├── energy_map.png
│   │   ├── original.jpg
│   │   ├── sample.png
│   │   └── seam.png
│   └── output/
│       └── .gitkeep
├── docs/
│   └── AI_CONTRIBUTING_GUIDE.md
├── include/
│   ├── Application.hpp
│   ├── DijkstraSolver.hpp
│   ├── EnergyCalculator.hpp
│   ├── EnergyRenderer.hpp
│   ├── ImageManager.hpp
│   ├── PixelGraph.hpp
│   ├── SeamRenderer.hpp
│   ├── SeamRemover.hpp
│   └── Window.hpp
├── src/
│   ├── Application.cpp
│   ├── DijkstraSolver.cpp
│   ├── EnergyCalculator.cpp
│   ├── EnergyRenderer.cpp
│   ├── ImageManager.cpp
│   ├── main.cpp
│   ├── PixelGraph.cpp
│   ├── SeamRenderer.cpp
│   ├── SeamRemover.cpp
│   └── Window.cpp
├── third_party/
│   └── tinyfiledialogs/
│       ├── tinyfiledialogs.c
│       └── tinyfiledialogs.h
├── .gitignore
├── BUILD.md
├── CONTRIBUTING.md
├── LICENSE
├── PROJECT_PLAN.md
└── README.md

How to Build

Using MSYS2 UCRT64 Terminal / PowerShell:

mkdir -p build
gcc -std=c99 -g -c third_party/tinyfiledialogs/tinyfiledialogs.c -o build/tinyfiledialogs.o
g++ -std=c++17 -Wall -Wextra -pedantic -g src/main.cpp src/Application.cpp src/DijkstraSolver.cpp src/Window.cpp src/ImageManager.cpp src/EnergyCalculator.cpp src/EnergyRenderer.cpp src/PixelGraph.cpp src/SeamRenderer.cpp src/SeamRemover.cpp build/tinyfiledialogs.o -Iinclude -Ithird_party/tinyfiledialogs -lsfml-graphics -lsfml-window -lsfml-system -lcomdlg32 -lole32 -o build/SeamCraft.exe

Running the Application:

./build/SeamCraft.exe

Ensure C:\msys64\ucrt64\bin is in your system PATH so SFML runtime DLLs can be located.

VS Code Integration:

  • Press Ctrl + Shift + B to compile using the preconfigured task.
  • Press F5 to start debugging with GDB.

See BUILD.md for full configuration details.

Roadmap

  • Milestone 1: Project foundation and SFML window architecture
  • Milestone 2: Image loading, aspect ratio scaling, reset, and error handling
  • Milestone 3: Sobel energy calculation engine and grayscale visualization
  • Milestone 4: Pixel graph construction with deterministic node IDs and vertical connectivity
  • Milestone 5: Dijkstra shortest-path seam algorithm and live red overlay renderer
  • Milestone 6: Vertical seam removal, continuous auto-carving, and sequential PNG export
  • Milestone 7: Target width/dimension resizing
  • Milestone 8: Smooth removal animation, UI polish, and performance optimizations

See PROJECT_PLAN.md for the full milestone progress.

Contributing

Contributions are welcome! Please read CONTRIBUTING.md and docs/AI_CONTRIBUTING_GUIDE.md for architectural guidelines, code standards, and workflow practices.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Author

Ojas Sugur

Built as part of a deep dive into graph algorithms, image processing, and content-aware image resizing using modern C++.

About

A visualization tool for seam carving that models an image as a graph and uses Dijkstra's algorithm to find and animate the minimum-energy seam during content-aware image resizing.

Resources

Readme
MIT license

Contributing

Contributing
Activity

Stars

2 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages