A probabilistic bitwise genetic algorithm for B-spline based image deformation estimation

Takumi Nakane, Takuya Akashi, Xuequan Lu, Chao Zhang

Abstract

Estimating non-rigid image deformation is a complex optimization problem characterized by high-dimensional search spaces. Traditional Genetic Algorithms (GAs) often struggle with premature convergence in these environments. This paper introduces a novel GA variant that replaces standard genetic operators with a Probabilistic Bitwise Operation (PBO). By modulating bit-inversion probabilities based on both individual fitness and bit significance, the proposed method maintains high genetic diversity and achieves robust convergence. Evaluated on synthetic datasets using B-spline Free-Form Deformations, the algorithm demonstrates effective estimation with low root mean square error.

Introduction

Image deformation estimation is critical for applications ranging from medical imaging to motion tracking. Modeling fluid-like, non-rigid movements typically employs 2D Free-Form Deformation (FFD) based on cubic B-splines. However, the resulting search space for optimal control point parameters is vast and prone to local optima. While Genetic Algorithms are theoretically robust global optimizers, traditional crossover and mutation operations often lead to a rapid loss of diversity, causing the population to stall at sub-optimal solutions.

Methodology

The proposed approach enhances the standard GA framework through three key innovations designed to navigate the complexities of B-spline parameterization.

Probabilistic Bitwise Operation (PBO)

The core innovation is the replacement of traditional crossover and mutation with the Probabilistic Bitwise Operation (PBO). In this scheme, individuals evolve independently. Each bit in a parameter's binary representation is assigned an inversion probability ($P_{inv}$), which is a function of the individual's fitness and the bit's significance (order).

The Probabilistic Bitwise Operation (PBO) mechanism, where bit inversion probability is determined by bit significance and individual fitness.

Lower-performing individuals are assigned higher $P_{inv}$ values to encourage broader exploration. Furthermore, Most Significant Bits (MSBs) have lower inversion probabilities than Least Significant Bits (LSBs). This allows the algorithm to perform coarse adjustments when fitness is low and fine-tune parameters as the population converges, effectively mimicking a multi-resolution search within the genetic space.

Coarse-to-Fine Strategy

To further manage complexity, the algorithm utilizes a hierarchical image pyramid. The estimation begins on low-resolution images with a sparse grid of control points. As the process progresses, the resolution increases, and the control point grid is refined, with parameters from the coarser level serving as the initial state for the finer level.

The coarse-to-fine strategy employing an image pyramid to progressively refine B-spline control points.

Annealing Selection

To balance exploration and exploitation, the authors implement an "annealing selection" rate. This rate decreases over time, controlling the number of individuals subjected to PBO in each generation, ensuring the population eventually stabilizes around the global optimum.

Experimental Results

The method was tested on a synthetic dataset featuring 10 distinct random deformations, where control points were displaced within a 3-pixel radius. The objective function minimized the Sum of Absolute Differences (SAD) between the source and target images.

Quantitative evaluation using Root Mean Square Error (RMSE) showed that the algorithm consistently achieved high accuracy, with RMSE values ranging between 2.92 and 5.10 pixels across all test cases. Qualitative results confirmed that the warped grids accurately aligned with target features, demonstrating the PBO's ability to maintain the genetic diversity required to escape local optima in high-dimensional B-spline spaces.

Conclusion

By decoupling individuals and introducing bit-sensitive inversion probabilities, the Probabilistic Bitwise Genetic Algorithm offers a robust solution for non-rigid image deformation estimation. Future work will focus on evaluating the algorithm's performance on real-world datasets with larger displacements and optimizing the computational overhead associated with the GA framework.

Summary updated

BibTeX
@inproceedings{nakane2019probabilistic,
  author = {Takumi Nakane and Takuya Akashi and Xuequan Lu and Chao Zhang},
  title = {{A probabilistic bitwise genetic algorithm for B-spline based image deformation estimation}},
  booktitle = {GECCO (Companion)},
  year = {2019},
  doi = {10.1145/3319619.3321890},
}
Figure