Discovery of accurate and far more efficient algorithm for point set registration problems

March 05, 2020


A point set registration problem is a task using two shapes, each consisting of a set of points, to estimate the relationship of individual points between the two shapes. Here, a "shape" is like a human body or face, which is similar to another body or face but exhibits morphological diversity. Taking the face as an example: the center position of the pupil of an eye varies depending on individuals but can be thought to have a correspondence with that of another person. Such a correspondence can be estimated by gradually deforming one shape to be superimposable on the other. Estimation of the correspondence of a point on one shape to a point on another is the point set registration problem. Since the number of points of one shape could be millions, estimation of correspondence is calculated by a computer. Nonetheless, up to now, even when the fastest conventional method was used, it took a lot of time for calculation for registration of ca. 100,000 points. Thus, algorithms that could find a solution far faster without affecting accuracy have been sought. Furthermore, preliminary registration before automated estimation was a prerequisite for the conventional calculation method, so algorithms that do not need preliminary registration are desirable.


Prof. Osamu Hirose, a young scientist at Kanazawa University, has been working on this problem. In his study, a completely new approach has been taken; a point set registration problem is defined as maximization of posterior probability*1) in Bayesian statistics*2) and the smoothness of a displacement field*3) is defined as a prior probability*4). As a result, a new algorithm has been discovered that can find a solution of a typical point set registration problem even without sufficient preliminary registration. In addition, by replacing some calculations of this algorithm with approximation, point set registration problems can be solved drastically faster than conventional methods. For example, for two point sets consisting of ca. 100,000 points each (leftmost in Figure 1), application of the present method was successful in completing highly accurate registration within 2 min, while the fastest method that was publicly available took about three hours. Also, as shown in Figure 2, the proposed method successfully registered the "dragon" dataset, where both point sets were composed of 437,645 points each. The computing time was roughly 20 min. Although the present high-speed calculation uses approximations, the accuracy of registration is not reduced to a discernible extent, as demonstrated by numerical experiments.

By using the algorithm, new CG characters can be automatically created, and thereby, it can be a labor-saving technique for CG designers. Figure 3 shows an example application of the algorithm. Source shape (a) and target shape (b) were obtained from a public database and used as input of the algorithm. Shape (c) is the result of the first registration, showing that the source shape became similar to the target shape with characteristics of the source shape retained. Shape (d) is the result of the second registration, showing the source shape to be deformed closer to the target shape. The video summary of this research is available at the following website: [].

[Future prospects]

The importance of point set registration problems is due to their wide range of applications in the fields of computer graphics (CG) and computer vision. Personal authentication by face recognition used on smartphones can be interpreted as an application of point set registration. Further, blending the 3-dimensional shape of certain two persons, called "morphing," can be performed through point set registration. In addition, there is a well-known study that enabled restoration of a 3-dimensional face model of the late Audrey Hepburn from a single picture, which used a technique that can be interpreted as point set registration. Therefore, since point set registrations having a wide variety of applications can now be performed at a very high speed with high accuracy, it is expected that the method established in this study will be used as a core technology in this research field.

On the other hand, the method could be further improved. Although it is remarkably faster than the conventional method, calculation speed may become a problem when the number of points in a point set reaches millions. Prof. Hirose is further developing methods to enable calculation of such a large point set registration problem within several minutes. Preliminary results show great promise for successful further developments.

*1) Maximization of posterior probability

The probability of a hypothesis being true after observing some outcomes is called the posterior probability. In Bayesian statistics, the best possible hypothesis is determined by finding the one that maximizes the posterior probability.

*2) Bayesian statistics

A category of statistics that introduces a prior probability, playing a role in prior knowledge for improving an inference from data.

*3) Smoothness of displacement field

The assumption that displacement vectors to define a shape deformation gradually become parallel as the distance between points decreases. It has been known from the early phase of this research field that this assumption remarkably improves accuracy of registration.

*4) Prior probability

A type of probabilities used in Bayesian statistics. It can be interpreted as the probability of a hypothesis being true without observations, and it plays a role in prior knowledge reinforcing an inference. In this study on point set registration problems, smoothness of displacement field is introduced as a prior probability.

Kanazawa University

Related Algorithm Articles from Brightsurf:

CCNY & partners in quantum algorithm breakthrough
Researchers led by City College of New York physicist Pouyan Ghaemi report the development of a quantum algorithm with the potential to study a class of many-electron quantums system using quantum computers.

Machine learning algorithm could provide Soldiers feedback
A new machine learning algorithm, developed with Army funding, can isolate patterns in brain signals that relate to a specific behavior and then decode it, potentially providing Soldiers with behavioral-based feedback.

New algorithm predicts likelihood of acute kidney injury
In a recent study, a new algorithm outperformed the standard method for predicting which hospitalized patients will develop acute kidney injury.

New algorithm could unleash the power of quantum computers
A new algorithm that fast forwards simulations could bring greater use ability to current and near-term quantum computers, opening the way for applications to run past strict time limits that hamper many quantum calculations.

QUT algorithm could quash Twitter abuse of women
Online abuse targeting women, including threats of harm or sexual violence, has proliferated across all social media platforms but QUT researchers have developed a sophisticated statistical model to identify misogynistic content and help drum it out of the Twittersphere.

New learning algorithm should significantly expand the possible applications of AI
The e-prop learning method developed at Graz University of Technology forms the basis for drastically more energy-efficient hardware implementations of Artificial Intelligence.

Algorithm predicts risk for PTSD after traumatic injury
With high precision, a new algorithm predicts which patients treated for traumatic injuries in the emergency department will later develop posttraumatic stress disorder.

New algorithm uses artificial intelligence to help manage type 1 diabetes
Researchers and physicians at Oregon Health & Science University have designed a method to help people with type 1 diabetes better manage their glucose levels.

A new algorithm predicts the difficulty in fighting fire
The tool completes previous studies with new variables and could improve the ability to respond to forest fires.

New algorithm predicts optimal materials among all possible compounds
Skoltech researchers have offered a solution to the problem of searching for materials with required properties among all possible combinations of chemical elements.

Read More: Algorithm News and Algorithm Current Events is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to