Count sketch is a type of dimensionality reduction that is particularly efficient in statistics, machine learning and algorithms. It was invented by Moses Charikar, Kevin Chen and Martin Farach-Colton in an effort to speed up the AMS Sketch by Alon, Matias and Szegedy for approximating the frequency moments of streams (these calculations require counting of the number of occurrences for the distinct elements of the stream). The sketch is nearly identical to the Feature hashing algorithm by John Moody, but differs in its use of hash functions with low dependence, which makes it more practical. In order to still have a high probability of success, the median trick is used to aggregate multiple count sketches, rather than the mean. These properties allow use for explicit kernel methods, bilinear pooling in neural networks and is a cornerstone in many numerical linear algebra algorithms. == Intuitive explanation == The inventors of this data structure offer the following iterative explanation of its operation: at the simplest level, the output of a single hash function s mapping stream elements q into {+1, -1} is feeding a single up/down counter C. After a single pass over the data, the frequency n ( q ) {\displaystyle n(q)} of a stream element q can be approximated, although extremely poorly, by the expected value E [ C ⋅ s ( q ) ] {\displaystyle {\mathbf {E}}[C\cdot s(q)]} ; a straightforward way to improve the variance of the previous estimate is to use an array of different hash functions s i {\displaystyle s_{i}} , each connected to its own counter C i {\displaystyle C_{i}} . For each i, the E [ C i ⋅ s i ( q ) ] = n ( q ) {\displaystyle {\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)} still holds, so averaging across the i range will tighten the approximation; the previous construct still has a major deficiency: if a lower-frequency-but-still-important output element a exhibits a hash collision with a high-frequency element even for one of the s i {\displaystyle s_{i}} hashes, n ( a ) {\displaystyle n(a)} estimate can be significantly affected. Avoiding this requires reducing the frequency of collision counter updates between any two distinct elements. This is achieved by replacing each C i {\displaystyle C_{i}} in the previous construct with an array of m counters (making the counter set into a two-dimensional matrix C i , j {\displaystyle C_{i,j}} ), with index j of a particular counter to be incremented/decremented selected via another set of hash functions h i {\displaystyle h_{i}} that map element q into the range {1..m}. Since E [ C i , h i ( q ) ⋅ s i ( q ) ] = n ( q ) {\displaystyle {\mathbf {E}}[C_{i,h_{i}(q)}\cdot s_{i}(q)]=n(q)} , averaging across all values of i will work. == Mathematical definition == 1. For constants w {\displaystyle w} and t {\displaystyle t} (to be defined later) independently choose d = 2 t + 1 {\displaystyle d=2t+1} random hash functions h 1 , … , h d {\displaystyle h_{1},\dots ,h_{d}} and s 1 , … , s d {\displaystyle s_{1},\dots ,s_{d}} such that h i : [ n ] → [ w ] {\displaystyle h_{i}:[n]\to [w]} and s i : [ n ] → { ± 1 } {\displaystyle s_{i}:[n]\to \{\pm 1\}} . It is necessary that the hash families from which h i {\displaystyle h_{i}} and s i {\displaystyle s_{i}} are chosen be pairwise independent. 2. For each item q i {\displaystyle q_{i}} in the stream, add s j ( q i ) {\displaystyle s_{j}(q_{i})} to the h j ( q i ) {\displaystyle h_{j}(q_{i})} th bucket of the j {\displaystyle j} th hash. At the end of this process, one has w d {\displaystyle wd} sums ( C i j ) {\displaystyle (C_{ij})} where C i , j = ∑ h i ( k ) = j s i ( k ) . {\displaystyle C_{i,j}=\sum _{h_{i}(k)=j}s_{i}(k).} To estimate the count of q {\displaystyle q} s one computes the following value: r q = median i = 1 d s i ( q ) ⋅ C i , h i ( q ) . {\displaystyle r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.} The values s i ( q ) ⋅ C i , h i ( q ) {\displaystyle s_{i}(q)\cdot C_{i,h_{i}(q)}} are unbiased estimates of how many times q {\displaystyle q} has appeared in the stream. The estimate r q {\displaystyle r_{q}} has variance O ( m i n { m 1 2 / w 2 , m 2 2 / w } ) {\displaystyle O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})} , where m 1 {\displaystyle m_{1}} is the length of the stream and m 2 2 {\displaystyle m_{2}^{2}} is ∑ q ( ∑ i [ q i = q ] ) 2 {\displaystyle \sum _{q}(\sum _{i}[q_{i}=q])^{2}} . Furthermore, r q {\displaystyle r_{q}} is guaranteed to never be more than 2 m 2 / w {\displaystyle 2m_{2}/{\sqrt {w}}} off from the true value, with probability 1 − e − O ( t ) {\displaystyle 1-e^{-O(t)}} . === Vector formulation === Alternatively Count-Sketch can be seen as a linear mapping with a non-linear reconstruction function. Let M ( i ∈ [ d ] ) ∈ { − 1 , 0 , 1 } w × n {\displaystyle M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}} , be a collection of d = 2 t + 1 {\displaystyle d=2t+1} matrices, defined by M h i ( j ) , j ( i ) = s i ( j ) {\displaystyle M_{h_{i}(j),j}^{(i)}=s_{i}(j)} for j ∈ [ w ] {\displaystyle j\in [w]} and 0 everywhere else. Then a vector v ∈ R n {\displaystyle v\in \mathbb {R} ^{n}} is sketched by C ( i ) = M ( i ) v ∈ R w {\displaystyle C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}} . To reconstruct v {\displaystyle v} we take v j ∗ = median i C j ( i ) s i ( j ) {\displaystyle v_{j}^{}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)} . This gives the same guarantees as stated above, if we take m 1 = ‖ v ‖ 1 {\displaystyle m_{1}=\|v\|_{1}} and m 2 = ‖ v ‖ 2 {\displaystyle m_{2}=\|v\|_{2}} . == Relation to Tensor sketch == The count sketch projection of the outer product of two vectors is equivalent to the convolution of two component count sketches. The count sketch computes a vector convolution C ( 1 ) x ∗ C ( 2 ) x T {\displaystyle C^{(1)}x\ast C^{(2)}x^{T}} , where C ( 1 ) {\displaystyle C^{(1)}} and C ( 2 ) {\displaystyle C^{(2)}} are independent count sketch matrices. Pham and Pagh show that this equals C ( x ⊗ x T ) {\displaystyle C(x\otimes x^{T})} – a count sketch C {\displaystyle C} of the outer product of vectors, where ⊗ {\displaystyle \otimes } denotes Kronecker product. The fast Fourier transform can be used to do fast convolution of count sketches. By using the face-splitting product such structures can be computed much faster than normal matrices.
Machine learning in video games
Artificial intelligence and machine learning techniques are used in video games for a wide variety of applications such as non-player character (NPC) control, procedural content generation (PCG) and deep learning-based content generation. Machine learning is a subset of artificial intelligence that uses historical data to build predictive and analytical models. This is in sharp contrast to traditional methods of artificial intelligence such as search trees and expert systems. Information on machine learning techniques in the field of games is mostly known to public through research projects as most gaming companies choose not to publish specific information about their intellectual property. The most publicly known application of machine learning in games is likely the use of deep learning agents that compete with professional human players in complex strategy games. There has been a significant application of machine learning on games such as Atari/ALE, Doom, Minecraft, StarCraft, and car racing. Other games that did not originally exists as video games, such as chess and Go have also been affected by the machine learning. == Overview of relevant machine learning techniques == === Deep learning === Deep learning is a subset of machine learning which focuses heavily on the use of artificial neural networks (ANN) that learn to solve complex tasks. Deep learning uses multiple layers of ANN and other techniques to progressively extract information from an input. Due to this complex layered approach, deep learning models often require powerful machines to train and run on. ==== Convolutional neural networks ==== Convolutional neural networks (CNN) are specialized ANNs that are often used to analyze image data. These types of networks are able to learn translation invariant patterns, which are patterns that are not dependent on location. CNNs are able to learn these patterns in a hierarchy, meaning that earlier convolutional layers will learn smaller local patterns while later layers will learn larger patterns based on the previous patterns. A CNN's ability to learn visual data has made it a commonly used tool for deep learning in games. === Recurrent neural network === Recurrent neural networks are a type of ANN that are designed to process sequences of data in order, one part at a time rather than all at once. An RNN runs over each part of a sequence, using the current part of the sequence along with memory of previous parts of the current sequence to produce an output. These types of ANN are highly effective at tasks such as speech recognition and other problems that depend heavily on temporal order. There are several types of RNNs with different internal configurations; the basic implementation suffers from a lack of long term memory due to the vanishing gradient problem, thus it is rarely used over newer implementations. ==== Long short-term memory ==== A long short-term memory (LSTM) network is a specific implementation of a RNN that is designed to deal with the vanishing gradient problem seen in simple RNNs, which would lead to them gradually "forgetting" about previous parts of an inputted sequence when calculating the output of a current part. LSTMs solve this problem with the addition of an elaborate system that uses an additional input/output to keep track of long term data. LSTMs have achieved very strong results across various fields, and were used by several monumental deep learning agents in games. === Reinforcement learning === Reinforcement learning is the process of training an agent using rewards and/or punishments. The way an agent is rewarded or punished depends heavily on the problem; such as giving an agent a positive reward for winning a game or a negative one for losing. Reinforcement learning is used heavily in the field of machine learning and can be seen in methods such as Q-learning, policy search, Deep Q-networks and others. It has seen strong performance in both the field of games and robotics. === Neuroevolution === Neuroevolution involves the use of both neural networks and evolutionary algorithms. Instead of using gradient descent like most neural networks, neuroevolution models make use of evolutionary algorithms to update neurons in the network. Researchers claim that this process is less likely to get stuck in a local minimum and is potentially faster than state of the art deep learning techniques. == Deep learning agents == Machine learning agents have been used to take the place of a human player rather than function as NPCs, which are deliberately added into video games as part of designed gameplay. Deep learning agents have achieved impressive results when used in competition with both humans and other artificial intelligence agents. === Chess === Chess is a turn-based strategy game that is considered a difficult AI problem due to the computational complexity of its board space. Similar strategy games are often solved with some form of a Minimax Tree Search. These types of AI agents have been known to beat professional human players, such as the historic 1997 Deep Blue versus Garry Kasparov match. Since then, machine learning agents have shown ever greater success than previous AI agents. === Go === Go is another turn-based strategy game which is considered an even more difficult AI problem than chess. The state space of is Go is around 10^170 possible board states compared to the 10^120 board states for Chess. Prior to recent deep learning models, AI Go agents were only able to play at the level of a human amateur. ==== AlphaGo ==== Google's 2015 AlphaGo was the first AI agent to beat a professional Go player. AlphaGo used a deep learning model to train the weights of a Monte Carlo tree search (MCTS). The deep learning model consisted of 2 ANN, a policy network to predict the probabilities of potential moves by opponents, and a value network to predict the win chance of a given state. The deep learning model allows the agent to explore potential game states more efficiently than a vanilla MCTS. The network were initially trained on games of humans players and then were further trained by games against itself. ==== AlphaGo Zero ==== AlphaGo Zero, another implementation of AlphaGo, was able to train entirely by playing against itself. It was able to quickly train up to the capabilities of the previous agent. === StarCraft series === StarCraft and its sequel StarCraft II are real-time strategy (RTS) video games that have become popular environments for AI research. Blizzard and DeepMind have worked together to release a public StarCraft 2 environment for AI research to be done on. Various deep learning methods have been tested on both games, though most agents usually have trouble outperforming the default AI with cheats enabled or skilled players of the game. ==== Alphastar ==== Alphastar was the first AI agent to beat professional StarCraft 2 players without any in-game advantages. The deep learning network of the agent initially received input from a simplified zoomed out version of the gamestate, but was later updated to play using a camera like other human players. The developers have not publicly released the code or architecture of their model, but have listed several state of the art machine learning techniques such as relational deep reinforcement learning, long short-term memory, auto-regressive policy heads, pointer networks, and centralized value baseline. Alphastar was initially trained with supervised learning, it watched replays of many human games in order to learn basic strategies. It then trained against different versions of itself and was improved through reinforcement learning. The final version was hugely successful, but only trained to play on a specific map in a protoss mirror matchup. === Dota 2 === Dota 2 is a multiplayer online battle arena (MOBA) game. Like other complex games, traditional AI agents have not been able to compete on the same level as professional human player. The only widely published information on AI agents attempted on Dota 2 is OpenAI's deep learning Five agent. ==== OpenAI Five ==== OpenAI Five utilized separate long short-term memory networks to learn each hero. It trained using a reinforcement learning technique known as Proximal Policy Learning running on a system containing 256 GPUs and 128,000 CPU cores. Five trained for months, accumulating 180 years of game experience each day, before facing off with professional players. It was eventually able to beat the 2018 Dota 2 esports champion team in a 2019 series of games. === Planetary Annihilation === Planetary Annihilation is a real-time strategy game which focuses on massive scale war. The developers use ANNs in their default AI agent. === Supreme Commander 2 === Supreme Commander 2 is a real-time strategy (RTS) video game. The game uses Multilayer Perceptrons (MLPs) to control a platoon’s reaction to encountered enemy units. Total of four MLPs are used, one for each platoon type: land, naval
Cooperative coevolution
Cooperative Coevolution (CC) in the field of biological evolution is an evolutionary computation method. It divides a large problem into subcomponents, and solves them independently in order to solve the large problem. The subcomponents are also called species. The subcomponents are implemented as subpopulations and the only interaction between subpopulations is in the cooperative evaluation of each individual of the subpopulations. The general CC framework is nature inspired where the individuals of a particular group of species mate amongst themselves, however, mating in between different species is not feasible. The cooperative evaluation of each individual in a subpopulation is done by concatenating the current individual with the best individuals from the rest of the subpopulations as described by M. Potter. The cooperative coevolution framework has been applied to real world problems such as pedestrian detection systems, large-scale function optimization and neural network training. It has also be further extended into another method, called Constructive cooperative coevolution. == Pseudocode == i := 0 for each subproblem S do Initialise a subpopulation Pop0(S) calculate fitness of each member in Pop0(S) while termination criteria not satisfied do i := i + 1 for each subproblem S do select Popi(S) from Popi-1(S) apply genetic operators to Popi(S) calculate fitness of each member in Popi(S)
Hyperion Cantos
The Hyperion Cantos is a series of science fiction novels by Dan Simmons. The title was originally used for the collection of the first pair of books in the series, Hyperion and The Fall of Hyperion, and later came to refer to the overall storyline, including Endymion, The Rise of Endymion, and a number of short stories. More narrowly, inside the fictional storyline, after the first volume, the Hyperion Cantos is an epic poem written by the character Martin Silenus covering in verse form the events of the first two books. Of the four novels, Hyperion received the Hugo and Locus Awards in 1990; The Fall of Hyperion won the Locus and British Science Fiction Association Awards in 1991; and The Rise of Endymion received the Locus Award in 1998. All four novels were also nominated for various science fiction awards. == Works == === Hyperion (1989) === First published in 1989, Hyperion has the structure of a frame story, similar to Geoffrey Chaucer's Canterbury Tales and Giovanni Boccaccio's Decameron. The story weaves the interlocking tales of a diverse group of travelers sent on a pilgrimage to the Time Tombs on Hyperion. The travelers have been sent by the Hegemony (the government of the human star systems), the All Thing, and the Church of the Final Atonement, alternately known as the Shrike Church, to make a request of the Shrike. As they progress in their journey, each of the pilgrims tells their tale. === The Fall of Hyperion (1990) === This book concludes the story begun in Hyperion. It abandons the storytelling frame structure of the first novel, and is instead presented primarily as a series of dreams by John Keats. === Endymion (1996) === The story commences 274 years after the events in the previous novel. Few main characters from the first two books are present in the later two. The main character is Raul Endymion, an ex-soldier who receives a death sentence after an unfair trial. He is rescued by Martin Silenus and asked to perform a series of rather extraordinarily difficult tasks. The main task is to rescue and protect the daughter of Brawne Lamia (one of the main characters of Hyperion), Aenea, a messiah coming from the time period just after the first books via time travel. The Catholic Church has become a dominant force in the human universe and views Aenea as a potential threat to their power. The group of Aenea, Endymion, and A. Bettik (an android) evades the Church's forces on several worlds through use of the Consul's spaceship, ending the story on Earth. === The Rise of Endymion (1997) === This final novel in the series finishes the story begun in Endymion, expanding on the themes in Endymion, as Raul and Aenea battle the Church and meet their respective destinies. === Short stories === The series also includes three short stories: "Remembering Siri" (1983, included almost verbatim in Hyperion) "The Death of the Centaur" (1990) "Orphans of the Helix" (1999) == Development == The Hyperion universe originated when Simmons was an elementary school teacher, as an extended tale he told at intervals to his young students; this is recorded in "The Death of the Centaur", and its introduction. It then inspired his short story "Remembering Siri", which eventually became the nucleus around which Hyperion and The Fall of Hyperion formed. After the quartet was published came the short story "Orphans of the Helix". "Orphans" is currently the final work in the Cantos, both chronologically and internally. The original Hyperion Cantos has been described as a novel published in two volumes, published separately at first for reasons of length. In his introduction to "Orphans of the Helix", Simmons elaborates: Some readers may know that I've written four novels set in the "Hyperion Universe"—Hyperion, The Fall of Hyperion, Endymion, and The Rise of Endymion. A perceptive subset of those readers—perhaps the majority—know that this so-called epic actually consists of two long and mutually dependent tales, the two Hyperion stories combined and the two Endymion stories combined, broken into four books because of the realities of publishing. == Influences == Much of the appeal of the series stems from its extensive use of references and allusions from a wide array of thinkers such as Teilhard de Chardin, John Muir, Norbert Wiener, and to the poetry of John Keats, the famous 19th-century English Romantic poet, Norse mythology, and the monk Ummon. A large number of technological elements are acknowledged by Simmons to be inspired by elements of Out of Control: The New Biology of Machines, Social Systems, and the Economic World. The Hyperion series has many echoes of Jack Vance, explicitly acknowledged in one of the later books. The title of the first novel, "Hyperion", is taken from one of Keats's poems, the unfinished epic Hyperion. Similarly, the title of the third novel is from Keats' poem Endymion. Quotes from actual Keats poems and the fictional Cantos of Martin Silenus are interspersed throughout the novels. Simmons goes so far as to have two artificial reincarnations of John Keats ("cybrids": artificial intelligences in human bodies) play a major role in the series. == Setting == Much of the action in the series takes place on the planet Hyperion. It is described as having one-fifth less gravity than Earth standard. Hyperion has a number of peculiar indigenous flora and fauna, notably Tesla trees, which are essentially large electricity-spewing trees. It is also a "labyrinthine" planet, which means that it is home to ancient subterranean labyrinths of unknown purpose. Most importantly, Hyperion is the location of the Time Tombs, large artifacts surrounded by "anti-entropic" fields that allow them to move backward through time. In the fictional universe of the Hyperion Cantos, the Hegemony of Man encompasses over 200 planets. Faster than light communications technology, Fatlines, are said to operate through tachyon bursts. However, in later books it is revealed that they operate through the Void Which Binds. The Farcaster network was given to humanity by the TechnoCore and again it was another use of the Void Which Binds that allowed this instantaneous travel between worlds. The Hawking Drive was developed by human scientists, allowing the faster than light travel which led to the Hegira (from the Arabic word هجرة Hijra, meaning 'migration'). The Gideon drive, a Core-provided starship drive, allows for near-instantaneous travel between any two points in human-occupied space. The drive's use kills any human on board a Gideon-propelled starship; thus, the technology is only of use with remote probes or when used in conjunction with the Pax's resurrection technology. The resurrection creche can regenerate someone carrying a cruciform from their remains. Treeships are living trees that are propelled by ergs (spider-like solid-state alien being that emits force fields) through space. === The Shrike === The region of the Tombs is also the home of the Shrike, a menacing half-mechanical, half-organic four-armed creature that features prominently in the series. It appears in all four Hyperion Cantos books and is an enigma in the initial two; its purpose is not revealed until the second book, but is still left nebulous. The Shrike appears to act both autonomously and as a servant of some unknown force or entity. In the first two Hyperion books, it exists solely in the area around the Time Tombs on the planet Hyperion. Its portrayal is changed significantly in the last two books, Endymion and The Rise of Endymion. In these novels, the Shrike appears effectively unfettered and protects the heroine Aenea against assassins of the opposing TechnoCore. Surrounded in mystery, the object of fear, hatred, and even worship by members of the Church of the Final Atonement (the Shrike Cult), the Shrike's origins are described as uncertain. It is portrayed as composed of razorwire, thorns, blades, and cutting edges, having fingers like scalpels and long, curved toe blades. It has the ability to control the flow of time, and may thus appear to travel infinitely fast. The Shrike may kill victims in a flash or it may transport them to an eternity of impalement upon an enormous artificial 'Tree of Thorns,' or 'Tree of Pain' in Hyperion's distant future. The Tree of Thorns is described as an unimaginably large, metallic tree, alive with the agonized writhing of countless human victims of all ages and races. It is also hinted in the second book that the Tree of Thorns is actually a simulation generated by a mystical interface which connects to human brains via a strong and pulsing (as if it were alive) cord. The name Shrike seems a reference to birds of the shrike family, a family of birds that impales their victims on thorns, spines, or twigs. === Worlds and Systems === In the fictional universe of the Hyperion Cantos, the Hegemony of Man encompasses over 200 planets. The following planets appear or are specifically mentioned in the Hyperion Cantos. Planets of
Federation of International Robot-soccer Association
The Federation of International Robot-soccer Association (FIRA) is an international organisation organising competitive soccer competitions between autonomous robots. The matches are usually five-a-side. == History == In 1996 and 1997, this competition was known as MiroSot and was held in Daejeon, Korea. The 1996 competition offered a challenging arena to the younger generation and researchers working with autonomous mobile robotic systems. From 1998 through 2008, it was called the FIRA Cup, and in 2009, it became the FIRA RoboWorld Cup & Congress. The 15th RoboWorld Cup was held at Amrita Vishwa Vidyapeetham, Bangalore, India in September 2010. In 2013, it took place in Kuala Lumpur, Malaysia. The championship started on August 24, 2013, and ended on August 29. At that time, it involved five categories: Micro-Robot Soccer Tournament, Amire, Naro, Simulated Robot, Android, Robo and Humanoid Robot. It attracted teams from Singapore, Indonesia, Taiwan, India, China, South Korea, the United Kingdom, Mexico, Canada, Russia and Malaysia. 80 teams from 11 countries participated. In 2018, the competition had 277 teams participating from 12 countries. === Past Events === == FIRA RoboWorld Cup & Congress == This competition has 4 leagues: FIRA AIR, FIRA Sports, FIRA Challenges, and FIRA Youth. Each league has its own competitions, and each competition can have several events. === FIRA AIR === The FIRA AIR league has two associated competitions, Autonomous Race and Emergency Service. === FIRA Sports === The FIRA Sports league has four associated competitions, HuroCup, RoboSot, SimuroSot, and AndroSot. This the robot soccer league. HuroCup consists of single events for bipedal humanoid robots. The events are: archery, sprint, marathon, united soccer, obstacle run, long jump, spartan race, marathon, weightlifting, and basketball. There is an all-round competition for the single robot that performs the best overall. === FIRA Challenges === The FIRA Challenges league has three associated competitions, Autonomous Cars, Autonomous Cars Simulation, Innovation and Business. === FIRA Youth === The FIRA Youth league has six associated challenges, Sport Robots, HuroCup Junior, CityRacer, DRV_Explorer, Cliff Hanger, and Mission Impossible.
Kernel (image processing)
In image processing, a kernel, convolution matrix, or mask is a small matrix used for blurring, sharpening, embossing, edge detection, and more. This is accomplished by doing a convolution between the kernel and an image. Or more simply, when each pixel in the output image is a function of the nearby pixels (including itself) in the input image, the kernel is that function. == Details == The general expression of a convolution is g x , y = ω ∗ f x , y = ∑ i = − a a ∑ j = − b b ω i , j f x − i , y − j , {\displaystyle g_{x,y}=\omega f_{x,y}=\sum _{i=-a}^{a}{\sum _{j=-b}^{b}{\omega _{i,j}f_{x-i,y-j}}},} where g ( x , y ) {\displaystyle g(x,y)} is the filtered image, f ( x , y ) {\displaystyle f(x,y)} is the original image, ω {\displaystyle \omega } is the filter kernel. Every element of the filter kernel is considered by − a ≤ i ≤ a {\displaystyle -a\leq i\leq a} and − b ≤ j ≤ b {\displaystyle -b\leq j\leq b} . Depending on the element values, a kernel can cause a wide range of effects: The above are just a few examples of effects achievable by convolving kernels and images. === Origin === The origin is the position of the kernel which is above (conceptually) the current output pixel. This could be outside of the actual kernel, though usually it corresponds to one of the kernel elements. For a symmetric kernel, the origin is usually the center element. == Convolution == Convolution is the process of adding each element of the image to its local neighbors, weighted by the kernel. This is related to a form of mathematical convolution. The matrix operation being performed—convolution—is not traditional matrix multiplication, despite being similarly denoted by . For example, if we have two three-by-three matrices, the first a kernel, and the second an image piece, convolution is the process of flipping both the rows and columns of the kernel and multiplying locally similar entries and summing. The element at coordinates [2, 2] (that is, the central element) of the resulting image would be a weighted combination of all the entries of the image matrix, with weights given by the kernel: ( [ a b c d e f g h i ] ∗ [ 1 2 3 4 5 6 7 8 9 ] ) [ 2 , 2 ] = {\displaystyle \left({\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}}{\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}\right)[2,2]=} ( i ⋅ 1 ) + ( h ⋅ 2 ) + ( g ⋅ 3 ) + ( f ⋅ 4 ) + ( e ⋅ 5 ) + ( d ⋅ 6 ) + ( c ⋅ 7 ) + ( b ⋅ 8 ) + ( a ⋅ 9 ) . {\displaystyle (i\cdot 1)+(h\cdot 2)+(g\cdot 3)+(f\cdot 4)+(e\cdot 5)+(d\cdot 6)+(c\cdot 7)+(b\cdot 8)+(a\cdot 9).} The other entries would be similarly weighted, where we position the center of the kernel on each of the boundary points of the image, and compute a weighted sum. The values of a given pixel in the output image are calculated by multiplying each kernel value by the corresponding input image pixel values. This can be described algorithmically with the following pseudo-code: for each image row in input image: for each pixel in image row: set accumulator to zero for each kernel row in kernel: for each element in kernel row: if element position corresponding to pixel position then multiply element value corresponding to pixel value add result to accumulator endif set output image pixel to accumulator corresponding input image pixels are found relative to the kernel's origin. If the kernel is symmetric then place the center (origin) of the kernel on the current pixel. The kernel will overlap the neighboring pixels around the origin. Each kernel element should be multiplied with the pixel value it overlaps with and all of the obtained values should be summed. This resultant sum will be the new value for the current pixel currently overlapped with the center of the kernel. If the kernel is not symmetric, it has to be flipped both around its horizontal and vertical axis before calculating the convolution as above. The general form for matrix convolution is [ x 11 x 12 ⋯ x 1 n x 21 x 22 ⋯ x 2 n ⋮ ⋮ ⋱ ⋮ x m 1 x m 2 ⋯ x m n ] ∗ [ y 11 y 12 ⋯ y 1 n y 21 y 22 ⋯ y 2 n ⋮ ⋮ ⋱ ⋮ y m 1 y m 2 ⋯ y m n ] = ∑ i = 0 m − 1 ∑ j = 0 n − 1 x ( m − i ) ( n − j ) y ( 1 + i ) ( 1 + j ) {\displaystyle {\begin{bmatrix}x_{11}&x_{12}&\cdots &x_{1n}\\x_{21}&x_{22}&\cdots &x_{2n}\\\vdots &\vdots &\ddots &\vdots \\x_{m1}&x_{m2}&\cdots &x_{mn}\\\end{bmatrix}}{\begin{bmatrix}y_{11}&y_{12}&\cdots &y_{1n}\\y_{21}&y_{22}&\cdots &y_{2n}\\\vdots &\vdots &\ddots &\vdots \\y_{m1}&y_{m2}&\cdots &y_{mn}\\\end{bmatrix}}=\sum _{i=0}^{m-1}\sum _{j=0}^{n-1}x_{(m-i)(n-j)}y_{(1+i)(1+j)}} === Edge handling === Kernel convolution usually requires values from pixels outside of the image boundaries. There are a variety of methods for handling image edges. Extend The nearest border pixels are conceptually extended as far as necessary to provide values for the convolution. Corner pixels are extended in 90° wedges. Other edge pixels are extended in lines. Wrap The image is conceptually wrapped (or tiled) and values are taken from the opposite edge or corner. Mirror The image is conceptually mirrored at the edges. For example, attempting to read a pixel 3 units outside an edge reads one 3 units inside the edge instead. Crop / Avoid overlap Any pixel in the output image which would require values from beyond the edge is skipped. This method can result in the output image being slightly smaller, with the edges having been cropped. Move kernel so that values from outside of image is never required. Machine learning mainly uses this approach. Example: Kernel size 10x10, image size 32x32, result image is 23x23. Kernel Crop Any pixel in the kernel that extends past the input image isn't used and the normalizing is adjusted to compensate. Constant Use constant value for pixels outside of image. Usually black or sometimes gray is used. Generally this depends on application. === Normalization === Normalization is defined as the division of each element in the kernel by the sum of all kernel elements, so that the sum of the elements of a normalized kernel is unity. This will ensure the average pixel in the modified image is as bright as the average pixel in the original image. === Optimization === Fast convolution algorithms include: separable convolution ==== Separable convolution ==== 2D convolution with an M × N kernel requires M × N multiplications for each sample (pixel). If the kernel is separable, then the computation can be reduced to M + N multiplications. Using separable convolutions can significantly decrease the computation by doing 1D convolution twice instead of one 2D convolution. === Implementation === Here a concrete convolution implementation done with the GLSL shading language :
Cruel World of Dreams and Fears
Cruel World of Dreams and Fears is the debut album from Ukrainian-born Czech black metal artist Draugveil, released independently on 13 June 2025. The album became notable among metal fans due to its cover, featuring Draugveil in a suit of armour and corpse paint, and lying in a field of red roses. The cover was the subject of parodying internet memes, as well as accusations of using artificial intelligence (AI) to make it. These claims were later expanded to suggest that AI was used to make the album's music. == Memes and AI accusations == Upon the album being released on YouTube on the channel Black Metal Promotion, the album attracted attention due to its cover, depicting Draugveil lying in a field of roses, dressed in armour, wearing corpse paint and having a sword stuck in the ground. Some compared it to covers where other artists are lying on the ground, such as Michael Jackson's Thriller, Luther Vandross's Give Me the Reason, and the UK cover of Lionel Richie's You Are. Critics of the album, however, suggested that AI was used to make the cover. This was partly due to suggestions that the rose stems in the picture come out from the ground in an unrealistic way. This later resulted in claims from some fans that AI was also used to produce the music, and later the lyrics and vocals. These claims began on a Facebook page entitled "AI Generated Nonsense", which was later deleted. No definitive evidence, however, was produced to back these claims. Derek McArthur, a journalist for Glasgow-based newspaper The Herald, wrote: "The music is in line with what one would expect from a one-man black metal project in the vein of Judas Iscariot and Burzum, but then if AI was asked to create music in a black metal style, that is probably what it would decide to generically produce and spit out." Draugveil's reaction to the claims was: "Let people decide." The result of the claims of AI has led to some writers to claim that artists in the future will have to prove they are human to be taken seriously, and that members of the public will be increasing doubt as to whether creative works are produced by either humans or AI. == Track listing ==