In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input. A non-deterministic Büchi automaton, later referred to just as a Büchi automaton, has a transition function which may have multiple outputs, leading to many possible paths for the same input; it accepts an infinite input if and only if some possible path is accepting. Deterministic and non-deterministic Büchi automata generalize deterministic finite automata and nondeterministic finite automata to infinite inputs. Each are types of ω-automata. Büchi automata recognize the ω-regular languages, the infinite word version of regular languages. They are named after the Swiss mathematician Julius Richard Büchi, who invented them in 1962. Büchi automata are often used in model checking as an automata-theoretic version of a formula in linear temporal logic. == Formal definition == Formally, a deterministic Büchi automaton is a tuple A = ( Q , Σ , δ , q 0 , F ) {\textstyle A=(Q,\Sigma ,\delta ,q_{0},\mathbf {F} )} that consists of the following components: Q {\textstyle Q} is a finite set. The elements of Q {\textstyle Q} are called the states of A {\textstyle A} . Σ {\textstyle \Sigma } is a finite set called the alphabet of A {\textstyle A} . δ : Q × Σ → Q {\textstyle \delta \colon Q\times \Sigma \to Q} is a function, called the transition function of A {\textstyle A} . q 0 {\textstyle q_{0}} is an element of Q {\textstyle Q} , called the initial state of A {\textstyle A} . F ⊆ Q {\textstyle \mathbf {F} \subseteq Q} is the acceptance condition. A run i _ = i 0 i 1 i 2 ⋯ ∈ Σ ω {\displaystyle {\underline {i}}=i_{0}i_{1}i_{2}\cdots \in \Sigma ^{\omega }} is an infinite string of inputs of A {\displaystyle A} . By calling δ {\displaystyle \delta } recursively, we can extend it to a function δ ω : Σ ω → Q ω {\displaystyle \delta ^{\omega }:\Sigma ^{\omega }\to Q^{\omega }} . A state q ∈ Q {\displaystyle q\in Q} is said to occur infinitely often for a run i _ {\displaystyle {\underline {i}}} when the set { n ∈ N ∣ δ ω ( i _ ) n = q } {\displaystyle \{n\in \mathbb {N} \mid \delta ^{\omega }({\underline {i}})_{n}=q\}} is infinite. Let I n f ( i _ ) {\displaystyle \mathrm {Inf} ({\underline {i}})} be the set of states occurring infinitely often for i _ {\displaystyle {\underline {i}}} . The language of A {\displaystyle A} is then the set of runs of A {\displaystyle A} in which at least one of the infinitely-often occurring states is in F {\textstyle \mathbf {F} } ; in symbols: L ( A ) = { i _ ∈ Σ ω ∣ I n f ( i _ ) ∩ F ≠ ∅ } . {\displaystyle L(A)=\{{\underline {i}}\in \Sigma ^{\omega }\mid \mathrm {Inf} ({\underline {i}})\cap \mathbf {F} \neq \varnothing \}.} In a (non-deterministic) Büchi automaton, the transition function δ {\textstyle \delta } is replaced with a transition relation Δ {\textstyle \Delta } that returns a set of states, and the single initial state q 0 {\textstyle q_{0}} is replaced by a set I {\textstyle I} of initial states. Generally, the term Büchi automaton without qualifier refers to non-deterministic Büchi automata. For more comprehensive formalism see also ω-automaton. == Closure properties == The set of Büchi automata is closed under the following operations. Let A = ( Q A , Σ , Δ A , I A , F A ) {\displaystyle A=(Q_{A},\Sigma ,\Delta _{A},I_{A},{F}_{A})} and B = ( Q B , Σ , Δ B , I B , F B ) {\displaystyle B=(Q_{B},\Sigma ,\Delta _{B},I_{B},{F}_{B})} be Büchi automata and C = ( Q C , Σ , Δ C , I C , F C ) {\displaystyle C=(Q_{C},\Sigma ,\Delta _{C},I_{C},{F}_{C})} be a finite automaton. Union: There is a Büchi automaton that recognizes the language L ( A ) ∪ L ( B ) . {\displaystyle L(A)\cup L(B).} Proof: If we assume, w.l.o.g., Q A ∩ Q B {\displaystyle Q_{A}\cap Q_{B}} is empty then L ( A ) ∪ L ( B ) {\displaystyle L(A)\cup L(B)} is recognized by the Büchi automaton ( Q A ∪ Q B , Σ ∪ Σ , Δ A ∪ Δ B , I A ∪ I B , F A ∪ F B ) . {\displaystyle (Q_{A}\cup Q_{B},\Sigma \cup \Sigma ,\Delta _{A}\cup \Delta _{B},I_{A}\cup I_{B},{F}_{A}\cup {F}_{B}).} Intersection: There is a Büchi automaton that recognizes the language L ( A ) ∩ L ( B ) . {\displaystyle L(A)\cap L(B).} Proof: The Büchi automaton A ′ = ( Q ′ , Σ , Δ ′ , I ′ , F ′ ) {\displaystyle A'=(Q',\Sigma ,\Delta ',I',F')} recognizes L ( A ) ∩ L ( B ) , {\displaystyle L(A)\cap L(B),} where Q ′ = Q A × Q B × { 1 , 2 } {\displaystyle Q'=Q_{A}\times Q_{B}\times \{1,2\}} Δ ′ = Δ 1 ∪ Δ 2 {\displaystyle \Delta '=\Delta _{1}\cup \Delta _{2}} Δ 1 = { ( ( q A , q B , 1 ) , a , ( q A ′ , q B ′ , i ) ) | ( q A , a , q A ′ ) ∈ Δ A and ( q B , a , q B ′ ) ∈ Δ B and if q A ∈ F A then i = 2 else i = 1 } {\displaystyle \Delta _{1}=\{((q_{A},q_{B},1),a,(q'_{A},q'_{B},i))|(q_{A},a,q'_{A})\in \Delta _{A}{\text{ and }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ and if }}q_{A}\in F_{A}{\text{ then }}i=2{\text{ else }}i=1\}} Δ 2 = { ( ( q A , q B , 2 ) , a , ( q A ′ , q B ′ , i ) ) | ( q A , a , q A ′ ) ∈ Δ A and ( q B , a , q B ′ ) ∈ Δ B and if q B ∈ F B then i = 1 else i = 2 } {\displaystyle \Delta _{2}=\{((q_{A},q_{B},2),a,(q'_{A},q'_{B},i))|(q_{A},a,q'_{A})\in \Delta _{A}{\text{ and }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ and if }}q_{B}\in F_{B}{\text{ then }}i=1{\text{ else }}i=2\}} I ′ = I A × I B × { 1 } {\displaystyle I'=I_{A}\times I_{B}\times \{1\}} F ′ = { ( q A , q B , 2 ) | q B ∈ F B } {\displaystyle F'=\{(q_{A},q_{B},2)|q_{B}\in F_{B}\}} By construction, r ′ = ( q A 0 , q B 0 , i 0 ) , ( q A 1 , q B 1 , i 1 ) , … {\displaystyle r'=(q_{A}^{0},q_{B}^{0},i^{0}),(q_{A}^{1},q_{B}^{1},i^{1}),\dots } is a run of automaton A' on input word w {\textstyle w} if r A = q A 0 , q A 1 , … {\displaystyle r_{A}=q_{A}^{0},q_{A}^{1},\dots } is run of A {\textstyle A} on w {\textstyle w} and r B = q B 0 , q B 1 , … {\displaystyle r_{B}=q_{B}^{0},q_{B}^{1},\dots } is run of B {\textstyle B} on w {\textstyle w} . r A {\textstyle r_{A}} is accepting and r B {\textstyle r_{B}} is accepting if r ′ {\textstyle r'} is concatenation of an infinite series of finite segments of 1-states (states with third component 1) and 2-states (states with third component 2) alternatively. There is such a series of segments of r ′ {\textstyle r'} if r ′ {\textstyle r'} is accepted by A ′ {\textstyle A'} . Concatenation: There is a Büchi automaton that recognizes the language L ( C ) ⋅ L ( A ) . {\displaystyle L(C)\cdot L(A).} Proof: If we assume, w.l.o.g., Q C ∩ Q A {\displaystyle Q_{C}\cap Q_{A}} is empty then the Büchi automaton A ′ = ( Q C ∪ Q A , Σ , Δ ′ , I ′ , F A ) {\displaystyle A'=(Q_{C}\cup Q_{A},\Sigma ,\Delta ',I',F_{A})} recognizes L ( C ) ⋅ L ( A ) {\displaystyle L(C)\cdot L(A)} , where Δ ′ = Δ A ∪ Δ C ∪ { ( q , a , q ′ ) | q ′ ∈ I A and ∃ f ∈ F C . ( q , a , f ) ∈ Δ C } {\displaystyle \Delta '=\Delta _{A}\cup \Delta _{C}\cup \{(q,a,q')|q'\in I_{A}{\text{ and }}\exists f\in F_{C}.(q,a,f)\in \Delta _{C}\}} if I C ∩ F C is empty then I ′ = I C otherwise I ′ = I C ∪ I A {\displaystyle {\text{ if }}I_{C}\cap F_{C}{\text{ is empty then }}I'=I_{C}{\text{ otherwise }}I'=I_{C}\cup I_{A}} ω-closure: If L ( C ) {\displaystyle L(C)} does not contain the empty word then there is a Büchi automaton that recognizes the language L ( C ) ω . {\displaystyle L(C)^{\omega }.} Proof: The Büchi automaton that recognizes L ( C ) ω {\displaystyle L(C)^{\omega }} is constructed in two stages. First, we construct a finite automaton A ′ {\textstyle A'} such that A ′ {\textstyle A'} also recognizes L ( C ) {\displaystyle L(C)} but there are no incoming transitions to initial states of A ′ {\textstyle A'} . So, A ′ = ( Q C ∪ { q new } , Σ , Δ ′ , { q new } , F C ) , {\displaystyle A'=(Q_{C}\cup \{q_{\text{new}}\},\Sigma ,\Delta ',\{q_{\text{new}}\},F_{C}),} where Δ ′ = Δ C ∪ { ( q new , a , q ′ ) | ∃ q ∈ I C . ( q , a , q ′ ) ∈ Δ C } . {\displaystyle \Delta '=\Delta _{C}\cup \{(q_{\text{new}},a,q')|\exists q\in I_{C}.(q,a,q')\in \Delta _{C}\}.} Note that L ( C ) = L ( A ′ ) {\displaystyle L(C)=L(A')} because L ( C ) {\displaystyle L(C)} does not contain the empty string. Second, we will construct the Büchi automaton A ″ {\textstyle A''} that recognize L ( C ) ω {\displaystyle L(C)^{\omega }} by adding a loop back to the initial state of A ′ {\textstyle A'} . So, A ″ = ( Q C ∪ { q new } , Σ , Δ ″ , { q new } , { q new } ) {\displaystyle A''=(Q_{C}\cup \{q_{\text{new}}\},\Sigma ,\Delta '',\{q_{\text{new}}\},\{q_{\text{new}}\})} , where Δ ″ = Δ ′ ∪ { ( q , a , q new ) | ∃ q ′ ∈ F C . ( q , a , q ′ ) ∈ Δ ′ } . {\displaystyle \Delta ''=\Delta '\cup \{(q,a,q_{\text{new}})|\exists q'\in F_{C}.(q,a,q')\in \Delta '\}.} Complementation:
Integreat
Integreat (former project name: Refguide+) is an open source mobile app that provides local information and services tailored to refugees and migrants coming to Germany. The content is maintained by local organizations, such as local governments or integration officers, and made available in locally relevant languages. It was developed by Tür an Tür - Digitalfabrik gGmbH (formerly Tür an Tür - Digital Factory gGmbH) in Augsburg together with a team of researchers and students from the Technical University of Munich. == History == In 1997, the Augsburg association "Tür an Tür", which has been working for refugees since 1992, published the brochure "First Steps", which answers local everyday questions. Since addresses and contact persons change quickly, some information is already outdated after a few weeks. Students of business informatics at the Technical University of Munich therefore developed the app Integreat within eight months together with the association and the social department of the city of Augsburg. The app was then also used by other cities and districts within months. As of February 3, 2022, information is available at 72 locations, including Munich, Dortmund, Nuremberg and Augsburg. == Mode of action == Refugees need information on areas such as registration, contact persons, health care, education, family, work and everyday life. Integreat seeks to provide refugees with this information by allowing them to select their geographic location and receive locally relevant information. This information is available offline once the app is opened so it can be used without an internet connection. In addition, the content is translated into the native languages of refugees and migrants to facilitate access. The content is licensed with a CC BY 4.0 license to facilitate collaboration and translation between content creators and dissemination of the content. Integreat is now being used for a broader migrant audience and says it can also support professionals, volunteers, and counseling centers. == Comparable mobile apps == Other mobile apps that are likewise intended to provide initial orientation for refugees include the app Ankommen, a joint project of the Federal Office for Migration and Refugees, the Goethe-Institut, the Federal Employment Agency and the Bavarian Broadcasting Corporation, which is intended as a companion for the first few weeks in Germany, and the Welcome App, a company-sponsored non-profit initiative for information about Germany and asylum procedures with a regional focus, and a book by the Konrad Adenauer Foundation (KAS) and Verlag Herder with a corresponding app Deutschland - Erste Informationen für Flüchtlinge (Germany - First Information for Refugees) as a companion for Arabic-speaking refugees in Germany.
AlphaGo Zero
AlphaGo Zero is a version of DeepMind's Go software AlphaGo. AlphaGo's team published an article in Nature in October 2017 introducing AlphaGo Zero, a version created without using data from human games, and stronger than any previous version. By playing games against itself, AlphaGo Zero: surpassed the strength of AlphaGo Lee in three days by winning 100 games to 0; reached the level of AlphaGo Master in 21 days; and exceeded all previous versions in 40 days. Training artificial intelligence (AI) without datasets derived from human experts has significant implications for the development of AI with superhuman skills, as expert data is "often expensive, unreliable, or simply unavailable." Demis Hassabis, the co-founder and CEO of DeepMind, said that AlphaGo Zero was so powerful because it was "no longer constrained by the limits of human knowledge". Furthermore, AlphaGo Zero performed better than standard deep reinforcement learning models (such as Deep Q-Network implementations) due to its integration of Monte Carlo tree search. David Silver, one of the first authors of DeepMind's papers published in Nature on AlphaGo, said that it is possible to have generalized AI algorithms by removing the need to learn from humans. Google later developed AlphaZero, a generalized version of AlphaGo Zero that could play chess and shōgi in addition to Go. In December 2017, AlphaZero beat the 3-day version of AlphaGo Zero by winning 60 games to 40, and with 8 hours of training it outperformed AlphaGo Lee on an Elo scale. AlphaZero also defeated a top chess program (Stockfish) and a top Shōgi program (Elmo). == Architecture == The network in AlphaGo Zero is a ResNet with two heads. The stem of the network takes as input a 17x19x19 tensor representation of the Go board. 8 channels are the positions of the current player's stones from the last eight time steps. (1 if there is a stone, 0 otherwise. If the time step go before the beginning of the game, then 0 in all positions.) 8 channels are the positions of the other player's stones from the last eight time steps. 1 channel is all 1 if black is to move, and 0 otherwise. The body is a ResNet with either 20 or 40 residual blocks and 256 channels. There are two heads, a policy head and a value head. Policy head outputs a logit array of size 19 × 19 + 1 {\displaystyle 19\times 19+1} , representing the logit of making a move in one of the points, plus the logit of passing. Value head outputs a number in the range ( − 1 , + 1 ) {\displaystyle (-1,+1)} , representing the expected score for the current player. -1 represents current player losing, and +1 winning. == Training == AlphaGo Zero's neural network was trained using TensorFlow, with 64 GPU workers and 19 CPU parameter servers. Only four TPUs were used for inference. The neural network initially knew nothing about Go beyond the rules. Unlike earlier versions of AlphaGo, Zero only perceived the board's stones, rather than having some rare human-programmed edge cases to help recognize unusual Go board positions. The AI engaged in reinforcement learning, playing against itself until it could anticipate its own moves and how those moves would affect the game's outcome. In the first three days AlphaGo Zero played 4.9 million games against itself in quick succession. It appeared to develop the skills required to beat top humans within just a few days, whereas the earlier AlphaGo took months of training to achieve the same level. According to Epoch.ai, training cost 3e23 FLOPs. For comparison, the researchers also trained a version of AlphaGo Zero using human games, AlphaGo Master, and found that it learned more quickly, but actually performed more poorly in the long run. DeepMind submitted its initial findings in a paper to Nature in April 2017, which was then published in October 2017. == Hardware cost == The hardware cost for a single AlphaGo Zero system in 2017, including the four TPUs, has been quoted as around $25 million. == Applications == According to Hassabis, AlphaGo's algorithms are likely to be of the most benefit to domains that require an intelligent search through an enormous space of possibilities, such as protein folding (see AlphaFold) or accurately simulating chemical reactions. AlphaGo's techniques are probably less useful in domains that are difficult to simulate, such as learning how to drive a car. DeepMind stated in October 2017 that it had already started active work on attempting to use AlphaGo Zero technology for protein folding, and stated it would soon publish new findings. == Reception == AlphaGo Zero was widely regarded as a significant advance, even when compared with its groundbreaking predecessor, AlphaGo. Oren Etzioni of the Allen Institute for Artificial Intelligence called AlphaGo Zero "a very impressive technical result" in "both their ability to do it—and their ability to train the system in 40 days, on four TPUs". The Guardian called it a "major breakthrough for artificial intelligence", citing Eleni Vasilaki of Sheffield University and Tom Mitchell of Carnegie Mellon University, who called it an impressive feat and an “outstanding engineering accomplishment" respectively. Mark Pesce of the University of Sydney called AlphaGo Zero "a big technological advance" taking us into "undiscovered territory". Gary Marcus, a psychologist at New York University, has cautioned that for all we know, AlphaGo may contain "implicit knowledge that the programmers have about how to construct machines to play problems like Go" and will need to be tested in other domains before being sure that its base architecture is effective at much more than playing Go. In contrast, DeepMind is "confident that this approach is generalisable to a large number of domains". In response to the reports, South Korean Go professional Lee Sedol said, "The previous version of AlphaGo wasn’t perfect, and I believe that’s why AlphaGo Zero was made." On the potential for AlphaGo's development, Lee said he will have to wait and see but also said it will affect young Go players. Mok Jin-seok, who directs the South Korean national Go team, said the Go world has already been imitating the playing styles of previous versions of AlphaGo and creating new ideas from them, and he is hopeful that new ideas will come out from AlphaGo Zero. Mok also added that general trends in the Go world are now being influenced by AlphaGo's playing style. "At first, it was hard to understand and I almost felt like I was playing against an alien. However, having had a great amount of experience, I’ve become used to it," Mok said. "We are now past the point where we debate the gap between the capability of AlphaGo and humans. It’s now between computers." Mok has reportedly already begun analyzing the playing style of AlphaGo Zero along with players from the national team. "Though having watched only a few matches, we received the impression that AlphaGo Zero plays more like a human than its predecessors," Mok said. Chinese Go professional Ke Jie commented on the remarkable accomplishments of the new program: "A pure self-learning AlphaGo is the strongest. Humans seem redundant in front of its self-improvement." == Comparison with predecessors == == AlphaZero == On 5 December 2017, DeepMind team released a preprint on arXiv, introducing AlphaZero, a program using generalized AlphaGo Zero's approach, which achieved within 24 hours a superhuman level of play in chess, shogi, and Go, defeating world-champion programs, Stockfish, Elmo, and 3-day version of AlphaGo Zero in each case. AlphaZero (AZ) is a more generalized variant of the AlphaGo Zero (AGZ) algorithm, and is able to play shogi and chess as well as Go. Differences between AZ and AGZ include: AZ has hard-coded rules for setting search hyperparameters. The neural network is now updated continually. Chess (unlike Go) can end in a tie; therefore AZ can take into account the possibility of a tie game. An open source program, Leela Zero, based on the ideas from the AlphaGo papers is available. It uses a GPU instead of the TPUs recent versions of AlphaGo rely on.
Jakub Pachocki
Jakub Pachocki (born 1991) is a Polish computer scientist and former competitive programmer. He is best known as OpenAI's chief scientist and for his role in overseeing development of GPT-4. == Background == Pachocki was born in 1991 in Gdańsk, Poland. In high school, he was a six-time finalist of the Polish Olympiad in Informatics. In 2009, he qualified for the International Olympiad in Informatics, winning a silver medal. Pachocki obtained his undergraduate degree in Computer Science from the University of Warsaw. He represented his university at the International Collegiate Programming Contest with his team winning a gold medal and coming second place overall in 2012. In the same year he was also the champion of the Google Code Jam. From 2011 to 2012, Pachocki worked at Facebook as a software engineering intern. Pachocki attended graduate school at Carnegie Mellon University, where he obtained his PhD under the supervision of Gary Miller. == Career == After graduation, Pachocki did postdoc work at Harvard University and Simons Institute for the Theory of Computing. === OpenAI === In 2017, Pachocki joined OpenAI. In 2021, he became OpenAI's research director where he led the development of GPT-4 and OpenAI Five. In May 2024, he became chief scientist after his mentor Ilya Sutskever left the company. OpenAI CEO Sam Altman has called Pachocki "easily one of the greatest minds of our generation". == Competitive programming achievements == International Olympiad in Informatics: Silver medal (2009) International Collegiate Programming Contest World Finals: Gold medal (second place overall in 2012) Google Code Jam: Champion (2012), Third place (2011) Facebook Hacker Cup: Second place (2013) TopCoder Open Algorithm: Second place (2012) A more comprehensive list of achievements can be found at the Competitive Programming Hall Of Fame website.
HTK (software)
HTK (Hidden Markov Model Toolkit) is a proprietary software toolkit for handling HMMs. It is mainly intended for speech recognition, but has been used in many other pattern recognition applications that employ HMMs, including speech synthesis, character recognition and DNA sequencing. Originally developed at the Machine Intelligence Laboratory (formerly known as the Speech Vision and Robotics Group) of the Cambridge University Engineering Department (CUED), HTK is now being widely used among researchers who are working on HMMs.
Template matching
Template matching is a technique in digital image processing for finding small parts of an image which match a template image. It can be used for quality control in manufacturing, navigation of mobile robots, or edge detection in images. The main challenges in a template matching task are detection of occlusion, when a sought-after object is partly hidden in an image; detection of non-rigid transformations, when an object is distorted or imaged from different angles; sensitivity to illumination and background changes; background clutter; and scale changes. == Feature-based approach == The feature-based approach to template matching relies on the extraction of image features, such as shapes, textures, and colors, that match the target image or frame. This approach is usually achieved using neural networks and deep-learning classifiers such as VGG, AlexNet, and ResNet.Convolutional neural networks (CNNs), which many modern classifiers are based on, process an image by passing it through different hidden layers, producing a vector at each layer with classification information about the image. These vectors are extracted from the network and used as the features of the image. Feature extraction using deep neural networks, like CNNs, has proven extremely effective has become the standard in state-of-the-art template matching algorithms. This feature-based approach is often more robust than the template-based approach described below. As such, it has become the state-of-the-art method for template matching, as it can match templates with non-rigid and out-of-plane transformations, as well as high background clutter and illumination changes. == Template-based approach == For templates without strong features, or for when the bulk of a template image constitutes the matching image as a whole, a template-based approach may be effective. Since template-based matching may require sampling of a large number of data points, it is often desirable to reduce the number of sampling points by reducing the resolution of search and template images by the same factor before performing the operation on the resultant downsized images. This pre-processing method creates a multi-scale, or pyramid, representation of images, providing a reduced search window of data points within a search image so that the template does not have to be compared with every viable data point. Pyramid representations are a method of dimensionality reduction, a common aim of machine learning on data sets that suffer the curse of dimensionality. == Common challenges == In instances where the template may not provide a direct match, it may be useful to implement eigenspaces to create templates that detail the matching object under a number of different conditions, such as varying perspectives, illuminations, color contrasts, or object poses. For example, if an algorithm is looking for a face, its template eigenspaces may consist of images (i.e., templates) of faces in different positions to the camera, in different lighting conditions, or with different expressions (i.e., poses). It is also possible for a matching image to be obscured or occluded by an object. In these cases, it is unreasonable to provide a multitude of templates to cover each possible occlusion. For example, the search object may be a playing card, and in some of the search images, the card is obscured by the fingers of someone holding the card, or by another card on top of it, or by some other object in front of the camera. In cases where the object is malleable or poseable, motion becomes an additional problem, and problems involving both motion and occlusion become ambiguous. In these cases, one possible solution is to divide the template image into multiple sub-images and perform matching on each subdivision. == Deformable templates in computational anatomy == Template matching is a central tool in computational anatomy (CA). In this field, a deformable template model is used to model the space of human anatomies and their orbits under the group of diffeomorphisms, functions which smoothly deform an object. Template matching arises as an approach to finding the unknown diffeomorphism that acts on a template image to match the target image. Template matching algorithms in CA have come to be called large deformation diffeomorphic metric mappings (LDDMMs). Currently, there are LDDMM template matching algorithms for matching anatomical landmark points, curves, surfaces, volumes. == Template-based matching explained using cross correlation or sum of absolute differences == A basic method of template matching sometimes called "Linear Spatial Filtering" uses an image patch (i.e., the "template image" or "filter mask") tailored to a specific feature of search images to detect. This technique can be easily performed on grey images or edge images, where the additional variable of color is either not present or not relevant. Cross correlation techniques compare the similarities of the search and template images. Their outputs should be highest at places where the image structure matches the template structure, i.e., where large search image values get multiplied by large template image values. This method is normally implemented by first picking out a part of a search image to use as a template. Let S ( x , y ) {\displaystyle S(x,y)} represent the value of a search image pixel, where ( x , y ) {\displaystyle (x,y)} represents the coordinates of the pixel in the search image. For simplicity, assume pixel values are scalar, as in a greyscale image. Similarly, let T ( x t , y t ) {\textstyle T(x_{t},y_{t})} represent the value of a template pixel, where ( x t , y t ) {\textstyle (x_{t},y_{t})} represents the coordinates of the pixel in the template image. To apply the filter, simply move the center (or origin) of the template image over each point in the search image and calculate the sum of products, similar to a dot product, between the pixel values in the search and template images over the whole area spanned by the template. More formally, if ( 0 , 0 ) {\displaystyle (0,0)} is the center (or origin) of the template image, then the cross correlation T ⋆ S {\displaystyle T\star S} at each point ( x , y ) {\displaystyle (x,y)} in the search image can be computed as: ( T ⋆ S ) ( x , y ) = ∑ ( x t , y t ) ∈ T T ( x t , y t ) ⋅ S ( x t + x , y t + y ) {\displaystyle (T\star S)(x,y)=\sum _{(x_{t},y_{t})\in T}T(x_{t},y_{t})\cdot S(x_{t}+x,y_{t}+y)} For convenience, T {\displaystyle T} denotes both the pixel values of the template image as well as its domain, the bounds of the template. Note that all possible positions of the template with respect to the search image are considered. Since cross correlation values are greatest when the values of the search and template pixels align, the best matching position ( x m , y m ) {\displaystyle (x_{m},y_{m})} corresponds to the maximum value of T ⋆ S {\displaystyle T\star S} over S {\displaystyle S} . Another way to handle translation problems on images using template matching is to compare the intensities of the pixels, using the sum of absolute differences (SAD) measure. To formulate this, let I S ( x s , y s ) {\displaystyle I_{S}(x_{s},y_{s})} and I T ( x t , y t ) {\displaystyle I_{T}(x_{t},y_{t})} denote the light intensity of pixels in the search and template images with coordinates ( x s , y s ) {\displaystyle (x_{s},y_{s})} and ( x t , y t ) {\displaystyle (x_{t},y_{t})} , respectively. Then by moving the center (or origin) of the template to a point ( x , y ) {\displaystyle (x,y)} in the search image, as before, the sum of absolute differences between the template and search pixel intensities at that point is: S A D ( x , y ) = ∑ ( x t , y t ) ∈ T | I T ( x t , y t ) − I S ( x t + x , y t + y ) | {\displaystyle SAD(x,y)=\sum _{(x_{t},y_{t})\in T}\left\vert I_{T}(x_{t},y_{t})-I_{S}(x_{t}+x,y_{t}+y)\right\vert } With this measure, the lowest SAD gives the best position for the template, rather than the greatest as with cross correlation. SAD tends to be relatively simple to implement and understand, but it also tends to be relatively slow to execute. A simple C++ implementation of SAD template matching is given below. == Implementation == In this simple implementation, it is assumed that the above described method is applied on grey images: This is why Grey is used as pixel intensity. The final position in this implementation gives the top left location for where the template image best matches the search image. One way to perform template matching on color images is to decompose the pixels into their color components and measure the quality of match between the color template and search image using the sum of the SAD computed for each color separately. == Speeding up the process == In the past, this type of spatial filtering was normally only used in dedicated hardware solutions because of the computational complexity of the operation, however we can lessen this complexity b
Maia and Marco
Maia and Marco are artificial intelligence used by GMA Network. Unveiled in 2023, they are used to fulfill the role of sports newscasters. == Background == Maia and Marco are artificial intelligence (AI) which take the form of three-dimensional human avatars. Maia makes use of a female avatar while Marco uses a male likeness. They have aesthetic features that are typical to Filipino showbusiness personalities. Among the technologies used in making and operating the AI include image generation, text-to-speech AI voice synthesis/generation, and deep learning face animation. They are also demonstrated to be bilingual, being able to speak in English and Tagalog (Filipino). == Use == The AI pair was unveiled by GMA Network on September 24, 2023, for their coverage of Season 99 of the National Collegiate Athletic Association (NCAA). Fulfilling the role of sports newscasters, Maia and Marco would join GMA's courtside human reporters. The AI pair are scheduled to appear four times a month on GMA's digital media platforms. They will not appear in traditional television broadcast. == Reception == The launch of the Maia and Marco was met with strong reactions. Various journalists and other personalities across the Philippine media industry expressed concern that their employment be at risk with the introduction of AI. The quality of the AI ability to emulate human behavior was characterized by critics as "soulless". GMA responding to concerns has stated that the AI would complement rather than replace its live human journalists including sportscasters. The National Union of Journalists of the Philippines urged dialogue among its peers in the newsroom on policy on how to use AI, which the group acknowledge as "inevitable".