Ctrl+K

Graph Matching

7. Graph Matching#

7.1. Practical Session 1.3: Graph Matching: Hungarian Algorithm or Munkres Algorithm#

7.2. Introduction#

The Hungarian Algorithm, developed by Harold Kuhn in 1955, is an optimization algorithm that solves the assignment problem in polynomial time \(O(n^3)\). This algorithm finds the optimal way to assign n tasks to n workers, minimizing the total cost of the assignments.

The name “Hungarian” comes from the fact that it was based on the earlier works of two Hungarian mathematicians: Dénes König and Jenő Egerváry.

7.3. Problem Definition#

Given:

  • A cost matrix C of size n×n where C[i,j] represents the cost of assigning worker i to task j

  • The goal is to find an optimal assignment that minimizes the total cost

  • Each worker can be assigned to exactly one task and each task must be assigned to exactly one worker

7.4. Basic Principles#

The algorithm works by transforming the cost matrix through a series of steps:

  1. Row and column reductions to create zeros

  2. Finding a maximum matching using these zeros

  3. Creating additional zeros if needed by modifying the matrix

7.5. Pseudocode#

FUNCTION HungarianAlgorithm(cost_matrix):
    # Step 1: Row Reduction
    FOR each row in cost_matrix:
        min_value = minimum value in row
        subtract min_value from each element in row

    # Step 2: Column Reduction
    FOR each column in cost_matrix:
        min_value = minimum value in column
        subtract min_value from each element in column

    WHILE optimal assignment not found:
        # Step 3: Cover zeros with minimum lines
        lines = find_minimum_lines_to_cover_zeros()
        
        IF number of lines equals n:
            optimal assignment found
            BREAK
        
        # Step 4: Create additional zeros
        min_uncovered = find_minimum_uncovered_value()
        FOR each uncovered element:
            subtract min_uncovered
        FOR each element covered twice:
            add min_uncovered

    # Step 5: Find optimal assignment
    assignment = zeros_matrix(n,n)
    FOR each marked zero in final matrix:
        assignment[row,col] = 1
    
    RETURN assignment

7.6. Algorithm Steps in Detail#

  1. Matrix Reduction

    • Subtract row minima

    • Subtract column minima

    • This creates at least one zero in each row and column

  2. Zero Covering

    • Find minimum number of lines to cover all zeros

    • If number of lines equals matrix dimension, solution found

    • Otherwise, proceed to step 3

  3. Matrix Modification

    • Find smallest uncovered value

    • Subtract it from all uncovered elements

    • Add it to elements covered twice

    • This creates new zeros

  4. Optimal Assignment

    • Select zeros such that each row and column has exactly one selected zero

    • These selections represent the optimal assignments

7.7. Time Complexity#

  • Overall complexity: \(O(n^3)\)

  • Space complexity: \(O(n^2)\)

  • Where n is the dimension of the cost matrix

This algorithm guarantees finding an optimal solution to the assignment problem, making it a fundamental tool in operations research and combinatorial optimization.

7.8. Exercise#

In the previous session, we learned about graph construction methods for matching keypoints in images. In this session, we will implement the Hungarian Algorithm to solve the assignment problem in graph matching. We will use the keypoints extracted from images to create a cost matrix and find the optimal assignment of keypoints between two images.

7.8.1. Exercise 1: Implement the Hungarian Algorithm for Graph Matching#

Implement the Hungarian Algorithm to find the optimal assignment of keypoints between two images, using the cost matrix created from the Euclidean distances between keypoints, and you must use the scipy.optimize.linear_sum_assignment function to solve the assignment problem.

import numpy as np
from PIL import Image
import scipy.io as sio
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay 
from scipy.optimize import linear_sum_assignment

def load_and_preprocess_images(img_path1, img_path2, mat_path1, mat_path2):
    """
    Carga y preprocesa pares de imágenes y sus keypoints
    """
    return img1, img2, kpts1, kpts2
def delaunay_triangulation(kpt):
    """
    Generate adjacency matrix based on Delaunay triangulation
    """
    return A

def simple_spatial_matching(kpts1, kpts2):
    """
    Realiza matching entre puntos usando distancia euclidiana y algoritmo húngaro optimizado
    
    Args:
        kpts1: Array de keypoints del primer grafo (2xN)
        kpts2: Array de keypoints del segundo grafo (2xN)
    
    Returns:
        matching: Matriz binaria donde matching[i,j]=1 indica correspondencia entre puntos
    Hints:
        - Primero deberás crear una matriz de costes basada en distancias euclidianas,
        cuyo tamaño será (n1, n2) donde n1 y n2 son el número de keypoints en cada grafo.
        - Seguidamente, deberás rellenar dicha matriz con las distancias euclidianas entre
        los keypoints de ambos grafos.
        - A continuación, deberás aplicar el algoritmo húngaro usando la función linear_sum_assignment, que recibe la matriz de costes y devuelve los índices de los puntos emparejados.
        - Finalmente, deberás crear una matriz de matching a partir de los índices obtenidos.

    """
    return matching

def visualize_matching_full(img1, img2, kpts1, kpts2, adj_matrix1, adj_matrix2, matching):
    """
    Visualiza el matching completo entre dos grafos
    """

7.8.2. Exercise 2: Visualize the Optimal Assignment#

Visualize the optimal assignment by connecting the matched keypoints with lines on the images.

_images/duck_matching_full_bueno.png

Fig. 7.1 Visualizing the Duck Images with Keypoints, Delaunay Triangulation and Matching (Good Result)#

_images/duck_matching_full_malo.png

Fig. 7.2 Visualizing the Duck Images with Keypoints, Delaunay Triangulation and Matching (Bad Result)#

7.8.3. Exercise 3: Evaluate the Matching Results#

Finally, we ask you to extract the accuracy of the matching results. The accuracy is defined as the number of correctly matched keypoints divided by the total number of keypoints. As you know, you have 5 categories of images, so you should evaluate the accuracy for each category, and create a csv file with the results of each category, reporting the mean accuracy for each category and the standard deviation.

Contents