Relaxation Labelling

relaxation_labelling.py

import numpy as np
import copy


def label_wise_vector(mat, y, x):
    """
    From a list of matrices of the image constructs a vector containing
    values at the index (y, x) of the matrices
    """
    prob_vec = []
    for label_mat in mat:
        prob_vec.append(label_mat[y, x])
    return prob_vec


def normalise_over_labels(mat):
    """
    Normalises values of each pixel in each matrix of label over all labels
    """
    norm_mat = copy.deepcopy(mat)
    for y in xrange(norm_mat[0].shape[0]):
        for x in xrange(norm_mat[0].shape[1]):
            norm_factor = np.sum(label_wise_vector(norm_mat, y, x))
            for label_idx in xrange(len(norm_mat)):
                norm_mat[label_idx][y, x] /= norm_factor
    return norm_mat


def contextual_support(compat, from_prob):
    """
    Calculates contextual support from object with probabilities from_prob
    return to_support as the contextual support
    """
    no_labels = len(from_prob)
    to_support = np.zeros(no_labels)
    for to_idx in xrange(no_labels):
        # $q_j^s(a_i:\lambda_l)=\sum^m_{k=1}r\left((a_i:\lambda_l),(a_j:\lambda_k)\right)P^s(a_j:\lambda_k)$
        for from_idx in xrange(no_labels):
            to_support[to_idx] += compat[to_idx, from_idx] * \
                    from_prob[from_idx]
    return to_support


def contextual_support_matrix(mat, compat):
    """
    Generates support from each pixel to the any pixel for each label
    """
    support_mat = [np.zeros(mat[0].shape) for _ in xrange(len(mat))]
    for (y, x), _ in np.ndenumerate(mat[0]):
        prob_vec = label_wise_vector(mat, y, x)
        support_vec = contextual_support(compat, prob_vec)
        for label_idx in xrange(len(support_mat)):
            support_mat[label_idx][y, x] = support_vec[label_idx]
    return support_mat


def relaxation_labelling(mat, compat, cij_generator):
    """
    Iterative ralaxation labelling algorithm
    Arguments:
    mat -- current iteration, formatted as a list of matrices, each matrix
    is probabilities of pixels on the image being assigned this particular
    label
    compat -- the compatibility matrix, where the row and column order must
    match the order of labels in mat
    cij_generator -- a generator/function that provides values of pixel
    coordinates that current pixel support, as well as the corresponding
    weight values
    Returns the next iteration, which is a list of matrices matching mat's
    struture
    """
    no_labels = len(mat)
    next_mat = [np.zeros(mat[0].shape) for _ in xrange(no_labels)]
    support_mat = contextual_support_matrix(mat, compat)
    for (from_y, from_x), val in np.ndenumerate(mat[0]):
        for (to_y, to_x), cij in cij_generator(
                from_y, from_x, mat[0].shape):
            for label_idx in xrange(no_labels):
                # $Q^s(a_i:\lambda_l)=\sum^n_{j=1}C_{ij}$
                # $P^{s+1}(a_i:\lambda_l)=P^s(a_i:\lambda_l)Q^s(a_i:\lambda_l)$
                # then normalise over all labels $\lambda_k$
                next_mat[label_idx][to_y, to_x] += \
                        cij * mat[label_idx][to_y, to_x] * \
                        support_mat[label_idx][from_y, from_x]
    return normalise_over_labels(next_mat)

relaxation_labelling_answers.py

from relaxation_labelling import relaxation_labelling
from itertools import product
import numpy as np

def cij_coef(from_y, from_x, shape):
    """
    A generator that iterates adjacent pixels and the weight for the pixel,
    which gives 1 if both pixels are adjacent
    """
    for (d_y, d_x) in product(xrange(-1, 2), xrange(-1, 2)):
        to_y = from_y + d_y
        to_x = from_x + d_x
        if to_y == from_y and to_x == from_x:
            continue
        if to_y >= shape[0] or to_x >= shape[1]:
            continue
        if to_y < 0 or to_x < 0:
            continue
        yield (to_y, to_x), 1
    else:
        return

def solve_relaxation_labelling(data, compat):
    edge = np.array(data)
    not_edge = np.array(edge)
    for idx, val in np.ndenumerate(not_edge):
        not_edge[idx] = 1 - val
    compat = np.array(compat)
    iterations = [[not_edge, edge]]
    for iter_idx in xrange(2):
        iterations.append(relaxation_labelling(
                iterations[iter_idx], compat, cij_coef))
    return iterations

def solve_question_2_a():
    """
    Answer to Question 2(a)
    Returns all values obtained within the first two iterations
    data -- the provided part of the image
    compat -- the compatibility matrix
    """
    data = [[0.0, 0.0, 0.0, 0.0, 0.0],
            [0.0, 0.1, 0.1, 0.1, 0.0],
            [0.0, 0.1, 0.9, 0.0, 0.0],
            [0.0, 0.1, 0.0, 0.0, 0.0],
            [0.0, 0.0, 0.0, 0.0, 0.0]]
    compat = [[1.0, 1.0], [1.0, 1.0]]
    return solve_relaxation_labelling(data, compat)

def solve_question_2_b():
    data = [[0.0, 0.0, 0.0, 0.0, 0.0],
            [0.0, 0.0, 0.0, 0.0, 0.0],
            [0.0, 0.0, 1.0, 0.0, 0.0],
            [0.0, 0.0, 0.0, 0.0, 0.0],
            [0.0, 0.0, 0.0, 0.0, 0.0]]
    compat = [[1.0, 1.0], [1.0, 2.0]]
    return solve_relaxation_labelling(data, compat)

def solve_question_2_c():
    data = [[0.0, 0.0, 0.0, 0.0, 0.0],
            [0.0, 0.1, 0.1, 0.1, 0.0],
            [0.0, 0.1, 1.0, 0.1, 0.0],
            [0.0, 0.1, 0.1, 0.1, 0.0],
            [0.0, 0.0, 0.0, 0.0, 0.0]]
    compat = [[1.0, 1.0], [1.0, 2.0]]
    return solve_relaxation_labelling(data, compat)

def test_values():
    data = [[0.0, 0.0, 1.0, 1.0, 1.0],
            [0.0, 0.0, 1.0, 1.0, 1.0],
            [0.0, 0.0, 1.0, 1.0, 1.0],
            [0.0, 0.0, 1.0, 1.0, 1.0],
            [0.0, 0.0, 1.0, 1.0, 1.0]]
    compat = [[1.0, 1.0], [1.0, 2.0]]
    return solve_relaxation_labelling(data, compat)

def pretty_print(iterations):
    for idx, curr_iter in enumerate(iterations):
        print 'Iteration %d' % idx
        print curr_iter[1]

if __name__ == '__main__':
    print 'test'
    pretty_print(test_values())
    print '2(a)'
    pretty_print(solve_question_2_a())
    print '2(b)'
    pretty_print(solve_question_2_b())
    print '2(c)'
    pretty_print(solve_question_2_c())