GSoC 2019: CGAL - Shape Regularization

Project Overview

I participated in 2019 Google Summer of Code (GSoC) by creating the Shape regularization package for the Computational Geometry Algorithms Library (CGAL) project by implementing the Generalized Global Regularization algorithm from the article “KIPPI: Kinetic Polygonal Partitioning of Images” written by Jean-Philippe Bauchet and Florent Lafarge at Inria. Development for the package for CGAL was carried out under the supervision of Dr. Dmitry Anisimov. The package comes with classes that work on a given set of 2D segments.

About GSoC

Google Summer of Code 2019 was a 12 week, full time, remote, paid internship with regular evaluation of the participant’s work every 4 weeks. I designed, implemented, tested and documented the package under the direction of my mentor Dr. Dmitry Anisimov.

Shape Regularization Overview

The algorithm works as follows:

  1. Computes neighbors of each item in the data set;
  2. Computes objective function values among these neighbors;
  3. Solves the quadratic programming problem utilizing the Operator Splitting Quadratic Program (OSQP) solver;
  4. Sorts items into groups based on the regularized objective function values;
  5. Updates items within each regularized group.

If the item type is a 2D segment, the package provides a few classes to reorient and realign them:


Usage Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Shape_regularization.h>
 
using Kernel = CGAL::Simple_cartesian<double>;
 
using FT        = typename Kernel::FT;
using Point_2   = typename Kernel::Point_2;
using Segment_2 = typename Kernel::Segment_2;
using Segments  = std::vector<Segment_2>;
 
using NQ = CGAL::Shape_regularization::Segments::Delaunay_neighbor_query_2<Kernel, Segments>;
using AR = CGAL::Shape_regularization::Segments::Angle_regularization_2<Kernel, Segments>;
using QP = CGAL::Shape_regularization::OSQP_quadratic_program<FT>;
using Regularizer = 
  CGAL::Shape_regularization::QP_regularization<Kernel, Segments, NQ, AR, QP>;
 
int main() {
 
  Segments segments = {
    Segment_2(Point_2(0.0, 0.0), Point_2(1.0, -0.1)),
    Segment_2(Point_2(1.0, 0.0), Point_2(1.0,  1.0)),
    Segment_2(Point_2(1.0, 1.0), Point_2(0.0,  1.1)),
    Segment_2(Point_2(0.0, 1.0), Point_2(0.0,  0.0))
  };
 
  NQ neighbor_query(segments);
  neighbor_query.create_unique_group();
  AR angle_regularization(
    segments, CGAL::parameters::all_default());
  angle_regularization.create_unique_group();
  
  QP quadratic_program;
  Regularizer regularizer(
    segments, neighbor_query, angle_regularization, quadratic_program);
  regularizer.regularize();
 
  std::cout << "* number of modified segments = " << 
    angle_regularization.number_of_modified_segments() << std::endl;
}

Skills Applied

Technologies used: C++11, git, CMake, Doxygen, OSQP solver.
Concepts used: Object-Oriented Design, Generic Programming, Quadratic Programming.

Feel free to take a look at my code, GSoC2019 proposal, final submission and commit history, final report and the documentation.