Tyler O'Neal, Staff Editor

Japanese discovery of accurate, far more efficient algorithm for point set registration problems creates dragons

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, the 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{module INSIDE STORY} this problem. In his study, a completely new approach has been taken; a point set registration problem is defined as the maximization of posterior probability) in Bayesian statistics) and the smoothness of a displacement field) is defined as a prior probability). As a result, a new algorithm has been discovered that can find a solution to 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. This animation shows the evolution of shape deformation, resulting from the application of the algorithm to the dragon dataset. As for the armadillo dataset, the red shape before optimization was created by nonlinear deformation of the blue shape. Both point sets are composed of 437,645 points each.

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: {media id=237,layout=solo} 

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 the 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.

NC State builds tool for US Army to expedite military evacuation of civilians during crisis

Tyler O'Neal, Staff Editor

A new computational model could be used to expedite military operations aimed at evacuating civilians during disaster response or humanitarian relief.

Researchers at North Carolina State University, with funding from the U.S. Army, designed a new model to help planners and logisticians determine what needs to be where and at what time in order to complete evacuation as quickly as possible. This includes where vehicles need to be when, and routing alternatives as well as supply requirements by location over time for food, water, and shelter.

"What sets this tool apart from other models is that it is designed for use in both planning and during operations," said Brandon McConnell, the corresponding author of a paper on the new model and a research assistant professor in NC State's Edward P. Fitts Department of Industrial and Systems Engineering. "In terms of specificity, we're talking about where a given truck will be at any point in time during an operation." {module INSIDE STORY}CAPTION Family members representing installations and commands throughout US Forces Korea board a CH-47 Chinook Helicopter Daegu Air Base, Republic of Korea, Nov. 3, 2016, for noncombatant exercise Courageous Channel. CREDIT (Photo Credit: Staff Sgt. Joseph Moore)

The research, published in the Journal of Defense Analytics and Logistics, focuses on noncombatant evacuation operations in the Republic of Korea; however, it could be used in a wide variety of scenarios.

"The tool will need fine-tuning before it can be implemented -- it would benefit from a user-friendly interface, for one thing -- but it highlights the potential that operational models have for helping the military achieve its objectives both in or out of wartime," said Dr. Joseph Myers, mathematical sciences division chief at the Army Research Office, an element of U.S. Army Combat Capabilities Development Command's Army Research Laboratory.

The Army Research Office funded this research through a short-term innovation research grant that explores proof-of-concept ideas in a nine-month period.

The authors said this research will provide military logistics planners with capabilities that are currently lacking in prevalent logistics planning tools. The project lays the mathematical and operations research foundation for the development of a network-based model that captures routing alternatives and characterizes the solutions to conduct capacity planning and resiliency analysis in near-real-time.

"There is a tremendous amount of complexity associated with the Army's South Korea noncombatant evacuation mission, and that presents a great opportunity for investigation and improvement," said U.S. Army Capt. John Kearby, first author of the paper and a former NC State graduate student. "The goal of this research was, and is, to encourage the development of better and more robust evacuation plans."

Kearby is currently a U.S. Military Academy instructor but previously served in Korea as an engineer company commander.

"The existing simulation models are both sophisticated and detailed -- they have been valuable tools for helping us study operations like these," McConnell said. "However, they're not designed to respond to rapidly changing scenarios. The new model can operate in near-real-time, making it operationally relevant. After all, even the best plans need at least minor modifications during execution."

How a new quantum approach can develop faster algorithms to deduce complex networks

Tyler O'Neal, Staff Editor

Scientists conduct numerical simulations on complex networks to gain insight into a powerful quantum mechanics-inspired algorithm

Our world has no dearth of complex networks--from cellular networks in biology to intricate web networks in technology. These networks also form the basis of various applications in virtually all fields of science, and to analyze and manipulate these networks, specific "search" algorithms are required. But, conventional search algorithms are slow and, when dealing with large networks, require a long computational time. Recently, search algorithms based on the principles of quantum mechanics have been found to vastly outperform classical approaches. One such example is the "quantum walk" algorithm, which can be used to find a specific point or a "vertex" on a given N-site graph. Instead of simply going through neighboring vertices, the quantum walk approach employs probabilistic estimations based on the quantum mechanical theory, which drastically reduces the number of steps required to find the objective. To achieve this, before moving from one point to another, an operation called "oracle call" needs to be performed repeatedly to adjust the probability values in the quantum system representation. One main issue is to understand the relationship between the optimal computational time of the oracle call and the structure of the network, as this relationship is well understood for standard shapes and bodies, but it remains unclear for complex networks. Digging deeper into the intricacies of these networks in an effort to develop more efficient Quantum Algorithms{module INSIDE STORY}

In a new study published in Physical Review A, a team of scientists at Tokyo University of Science, led by Prof Tetsuro Nikuni, dug deeper into the intricacies of these networks to develop more efficient quantum algorithms. Prof Nikuni explains, "Many real-world systems, such as the World Wide Web and social/biological networks, exhibit complex structures. To fully explore the potential of these network systems, developing an efficient search algorithm is crucial."

To begin with, the scientists looked into the "fractal properties" (geometrical properties of figures that seem to infinitely replicate their overall shape) of networks. The researchers focused on some basic fractal lattices (structures with a fractal network), such as "Sierpinski gasket," "Sierpinski tetrahedron," and "Sierpinski carpet," to try to find out the relationship between the number of vertices (nodes of the network) and the optimal computational time in a quantum walk search. To this end, they performed numerical simulations with over a million vertices and checked whether the results were in line with previous studies, which proposed a mathematical law or a "scaling law" to explain this relationship.

The researchers found that the scaling law for some fractal lattices varied according to their spectral dimension, confirming the previous conjecture for other lattices. Surprisingly, they even found that the scaling law for another type of fractal lattice depends on a combination of its intrinsic characteristics, again showing that the previous conjecture on the optimal number of oracle calls might be accurate. Prof Nikuni says, "It may indeed be a fact that the quantum spatial search on fractal lattices is surprisingly subject to combinations of the characteristic quantities of the fractal geometry. It remains an open question as to why the scaling law for the number of oracle calls is given by such combinations." With this understanding, the team even proposed a new scaling hypothesis, which slightly differs from the ones proposed earlier, to gain more insight into different fractal geometries of networks.

The research team hopes that, with their findings, quantum searches will become easier to analyze experimentally--especially with recent experiments performing quantum walks on physical systems like optical lattices. The wide applicability of quantum algorithms on fractal lattices highlights the importance of this study. Owing to its exciting findings, this study was even selected as "Editor's suggestion" in the February 2020 issue of Physical Review A. Optimistic about the results and with future research directions laid out, Prof Nikuni concludes, "We hope that our study further promotes the interdisciplinary study of complex networks, mathematics, and quantum mechanics on fractal geometries."