In multi-armed bandit problems, IMED (for Indexed Minimum Empirical Divergence) is an algorithm developed in 2015 by Junya Honda and Akimichi Takemura. It is the first algorithm proved to be asymptotically optimal respect to the problem-dependant Lai–Robbins lower bound for distributions in ( − ∞ , 1 ] {\displaystyle (-\infty ,1]} . == Multi-armed bandit problem == The Multi-armed bandit problem is a sequential game where one player has to choose at each turn between K {\displaystyle K} actions (arms). Behind every arm a {\displaystyle a} there is an unknown distribution ν a {\displaystyle \nu _{a}} that lies in a set D {\displaystyle {\mathcal {D}}} known by the player (for example, D {\displaystyle {\mathcal {D}}} can be the set of Gaussian distributions or Bernoulli distributions). At each turn t {\displaystyle t} the player chooses (pulls) an arm a t {\displaystyle a_{t}} , he then gets an observation X t {\displaystyle X_{t}} of the distribution ν a t {\displaystyle \nu _{a_{t}}} . === Regret minimization === The goal is to minimize the regret at time T {\displaystyle T} that is defined as R T := ∑ a = 1 K Δ a E [ N a ( T ) ] {\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\mathbb {E} [N_{a}(T)]} where μ a := E [ ν a ] {\displaystyle \mu _{a}:=\mathbb {E} [\nu _{a}]} is the mean of arm a {\displaystyle a} μ ∗ := max a μ a {\displaystyle \mu ^{}:=\max _{a}\mu _{a}} is the highest mean Δ a := μ ∗ − μ a {\displaystyle \Delta _{a}:=\mu ^{}-\mu _{a}} N a ( t ) {\displaystyle N_{a}(t)} is the number of pulls of arm a {\displaystyle a} up to turn t {\displaystyle t} The player has to find an algorithm that chooses at each turn t {\displaystyle t} which arm to pull based on the previous actions and observations ( a s , X s ) s < t {\displaystyle (a_{s},X_{s})_{s
Nanosemantics
Nanosemantics Lab is a Russian IT company specializing in natural language processing (NLP), computer vision (CV), speech technologies (ASR/TTS) and creation of interactive dialog interfaces, particularly chatbots and virtual assistants, based on artificial intelligence (AI). The company uses neural network platforms, including its own-made platform PuzzleLib which works on Russian-made microprocessor architecture Elbrus and Russia-based Astra Linux operating system. The company was founded in 2005 by Igor Ashmanov and Natalya Kaspersky. == Profile == The company was one of the first on Russian market to develop dialog interfaces for different branches of businesses, as well as to support community of AI developers. The company's most demanded product, as for beginning of the 2020s, is the automated "online advisers", functioning as chat bots, made for helping customers with usage of commercial products. In 2009 the company released an online service called iii.ru, where visitors were able to create their own AI-based virtual personalities entitles "infs" (for free). A visitor was able to train its own "inf" and let them chat to other "live" visitors as well with other "infs". More than 2.3 million of "infs" were created and trained by visitors over several years. Nanosemantics Lab maintains its own linguistic programming language for AI development called Dialog Language (DL). Popular social networks and instant messaging services may be used as base platforms. Nanosemantics' AI bots support different types of businesses: banks and financial services, telecommunications, retail, travel and automobile industry, home appliances production, etc. Among its solutions, Nanosemantics lists projects for various companies and institutions, among them VTB, Beeline, MTS, Sberbank, Higher School of Economics, Webmoney, Gazpromneft, Rostelecom, Ford Motors, Ministry of Health of the Russian Federation and others. The company uses the term "inf" for naming its numerous types of chat bots. The term was coined by co-founder Igor Ashmanov, head of Ashmanov & Partners. A 2014 scholarly research at Higher School of Economics, called "Basics of Business Informatics", states that such "infs", when used at business, may lower load on employees, collect statistics useful for understanding market demand and also may increase customer loyalty by providing fast and informative answers due to usage of large databases. The same research describes Nanosemantics' project for Russian branch of Ford Motors company, when AI capabilities were used for promoting the car model Ford Kuga. The research pointed out that within 2 months since beginning, the promo-website conducted 47774 talks of visitors with the specialized "inf", which indicated several hundred thousand of questions and the longest chat lasted for 3 hours 10 minutes. One-year promo campaign showed that 28.6% of people who made pre-orders talked to an "inf". In 2016 Nanosemantics launched a SaaS platform aimed at creating customized virtual assistants by users. The company's flagship product is considered to be Dialog Operating System (DialogOS), a professional corporate platform for creating intellectual voice and textual bots. It has its own linguistic programming language for creation of flexible scenarios and ready-studied neural natural language processing modules that are able to understand human interlocutors. In 2021 the company presented technology called NLab Speech ASR which contains a set of neural-networking algorithms for processing audio signals and analysis of texts that were trained and calibrated using speech-based big data marked up manually. The technology allows speed of processing of data up to "6 real-time factor" and precision values in noisy audio data may exceed 82%. In March 2022 the technology was included in Russia's Joint Registry for Russian Programs for Computers and Databases. As well, another technology was included: NLab Speech TTS, which is text-to-speech system that produces synthesized speech from printed text. == Joint projects == Nanosemantics participates in Ashmanov & Partners' projects related to AI. Since 2014, it helps in development of hardware "personal assistant" called Lexy, a solution similar to Amazon Alexa and the analogues. In August 2019 it was announced that Nanosemantics is going to participate in creation of open operating system for creating automated voice assistants. The project was called SOVA (Smart Open Virtual Assistant) and received investment of 300 million roubles (~$4,6 million) from Russian state-maintained National Technological Initiative. The company maintains long-term partnerships with Skolkovo Innovation Center (resident of IT cluster), branch association "Neuronet" and Yandex. Together with USA-based startup Remedy Logic, Nanosemantics has developed a medical diagnostic system for finding, using AI, spinal pathologies in tomography images of human bodies. Among them: central, foraminal and lateral lumbar stenosis, hernias, arthrosis. The system offers options of treatment. Since August 2021 the company is the resident of Technology Valley of Moscow State University. Also in 2021, Nanosemantics became a member of Committee on Artificial Intelligence within the Russian Association of Software Developers "Native Soft". The company states as one of its missions support of initiatives aimed at preservation and development of the Russian language. In May 2021, together with Pushkin Institute, the company created a chat bot called Phil, that explains to Russian people meaning of different Russian neologisms, and offers synonyms for them. Bot's vocabulary contains more than 500 neologisms, as well the bot can give advice on jargonisms and other types of specific words. Also in 2021, Nanosemanics Lab has signed the first-ever Russian "Codex of ethics of artificial intelligence". It establishes guidelines for ethical behavior of businesses that implement AI-based solutions. === IT contests === The company regularly organizes All-Russian Turing Test competitions for IT developers. Some of these events are co-organized with Microsoft. During the competitions, judges randomly choose virtual interlocutor and have a short conversation with them. They have to determine if a human or a machine is talking to them. An interlocutor may be either a bot or its human creator or operator. The results are measured in per cent of judges that were successfully convinced by a machine that it was a human. In 2021 Nanosemantics took part in federal project "Artificial Intelligence" by National Technological Initiative. In December 2021 the company together with state enterprise "Resource Center of Universal Design and Rehabilitation Technologies" (RCUD-RT) held an all-Russian hackathon aimed at development of AI solutions for medicine. During 3 days, participants created several training programs for patients with speech disorders. In April 2022, another hackathon by Nanosemantics was held together with MIREA – Russian Technological University. Students were participating and trying to generate algorithms for voice deepfakes. 17 teams contested in creation of software that generated artificial voice of a certain person. == Recognition == Since its foundation, Nanosemantics Lab has received a number of recognitions and awards. Among them are several professional ROTOR awards for the website iii.ru (created in 2009). The website gives the general public the means to create and train virtual assistants, which can then be used on a website or integrated into social networks. In 2013, a virtual assistant called Dana, created for Beeline Kazakhstan, was awarded with professional prize "Crystal Headset" in nomination "the best applying of technology". In 2015, the RBTH international media service included Nanosemantics in its list of "Top 50 Startups" in Russia. In 2016, the company received Russian state-maintained award called Runet Prize in two nominations: "State and Society" and "Technology and Innovation". In 2021, in Velikiy Novgorod, Nanosemantics team has won a hackathon aimed at finding means of discovering corruption schemes in Russian laws. In February 2022 the company won another contest by National Technological Initiative, called "Prochtenie", aimed at creation of AI systems for checking schoolchildren's school essays. The Nanosemantics team was awarded 20 million rubles for "overcoming technological barrier" in contest dedicated to English language, and 12 million for 1st place in special nomination "Structure" in Russian-language essay contest.
Pronunciation assessment
Automatic pronunciation assessment uses computer speech recognition to determine how accurately speech has been pronounced, instead of relying on a human instructor or proctor. It is also called speech verification, pronunciation evaluation, and pronunciation scoring. This technology is used to grade speech quality, for language testing, for computer-aided pronunciation teaching (CAPT) in computer-assisted language learning (CALL), for speaking skill remediation, and for accent reduction. Pronunciation assessment is different from dictation or automatic transcription, because instead of determining unknown speech, it verifies learners' pronunciation of known word(s), often from prior transcription of the same utterance; ideally scoring the intelligibility of the learners' speech. Sometimes pronunciation assessment evaluates the prosody of the learners' speech, such as intonation, pitch, tempo, rhythm, and syllable and word stress, although those are usually not essential for being understood in most languages. Pronunciation assessment is also used in reading tutoring, for example in products from Google, Microsoft, and Amira Learning. Automatic pronunciation assessment can also be used to help diagnose and treat speech disorders such as apraxia. == Intelligibility == Intelligibility refers to how well a learner's utterance is understood by a listener, rather than how much it sounds like a native speaker. This is separate from measures of fluency, such as so-called "Goodness of Pronunciation" (GoP) scores, which estimate how closely an utterance aligns with those of native speakers. Intelligibility is widely regarded as the most important communicative goal in pronunciation teaching and assessment. For example, in the Common European Framework of Reference for Languages (CEFR) assessment criteria for "overall phonological control", intelligibility outweighs formally correct pronunciation at all levels. Studies in applied linguistics have shown that accent reduction does not always increase intelligibility because listeners can often comprehend heavily accented speech without difficulty. Pronunciation assessment systems often rely on acoustic methods such as GoP which compare learner speech to reference models to produce phoneme-level scores, which are in turn aggregated to produce word and phrase scores. While these methods are effective for identifying deviations from native speakers' utterances, they do not effectively measure how understandable speech is to human listeners. Intelligibility is influenced by broader linguistic and contextual factors such as stress placement, speech rate, and coarticulation, which are not represented in purely segmental scores. The earliest work on pronunciation assessment avoided measuring genuine listener intelligibility, a shortcoming corrected in 2011 at the Toyohashi University of Technology, and included in the Versant high-stakes English fluency assessment from Pearson and mobile apps from 17zuoye Education & Technology, but still missing in 2023 products from Google Search, Microsoft, Educational Testing Service, Speechace, and ELSA. Assessing authentic listener intelligibility is essential for avoiding inaccuracies from accent bias, especially in high-stakes assessments; from words with multiple correct pronunciations; and from phoneme coding errors in machine-readable pronunciation dictionaries. In 2022, researchers found that some newer speech-to-text systems, based on end-to-end reinforcement learning to map audio signals directly into words, produce word and phrase confidence scores (from 10-25ms audio frame logit aggregation) closely correlated with genuine listener intelligibility. Others have been able to assess intelligibility using Levenshtein or dynamic time warping distance measures from Wav2Vec2 representation of good speech. Further work through 2025 has focused specifically on measuring intelligibility. A 2025 study of 42 pronunciation and speech coaching apps (32 mobile and 10 web) found that none offered intelligibility assessment. Instead, most provided only segmental and accent-focused scoring. About two-thirds of the apps provided some form of specific pronunciation feedback, usually with phonetic transcriptions, but accompanied by visual cues (such as animations of the vocal tract or the lips and tongue from the front) in only about 5% of the apps. Less than a third provided feedback on learner perception of exemplar speech. == Evaluation == Although there are as yet no industry-standard benchmarks for evaluating pronunciation assessment accuracy, researchers occasionally release evaluation speech corpuses for others to use for improving assessment quality. Such evaluation databases often emphasize formally unaccented pronunciation to the exclusion of genuine intelligibility evident from blinded listener transcriptions. As of mid-2025, state of the art approaches for automatically transcribing phonemes typically achieve an error rate of about 10% from known good speech. The International Speech Communication Association (ISCA) 2025 Workshop on Speech and Language Technology in Education (SLaTE) administered a Speak & Improve Challenge: Spoken Language Assessment and Feedback, introducing benchmarks for evaluating pronunciation assessment and remediation systems across languages, accents, and learner populations. The challenge emphasized cross-lingual generalization and alignment with human intelligibility judgments, for more robust and interpretable assessment systems. Ethical issues in pronunciation assessment are present in both human and automatic methods. Authentic validity, fairness, and mitigating bias in evaluation are all crucial. Diverse speech data should be included in automatic pronunciation assessment models. Combining human judgments, especially blinded transcriptions from a wide diversity of listeners, with automated feedback can improve accuracy and fairness. Second language learners benefit substantially from their use of widely available speech recognition systems for dictation, virtual assistants, and AI chatbots. In such systems, users naturally try to correct their own errors evident in speech recognition results that they notice. Such use improves their grammar and vocabulary development along with their pronunciation skills. The extent to which explicit pronunciation assessment and remediation approaches improve on such self-directed interactions remains an open question. Similarly, automatic dictation results have been shown to reflect intelligibility about as well as human scorers. == Recent developments == During 2021–22, a smartphone-based CAPT system was used to sense articulation through both audible and inaudible signals, providing feedback at the phoneme level. Some promising areas for improvement which were being developed in 2024 include articulatory feature extraction and transfer learning to suppress unnecessary corrections. Other interesting advances under development include "augmented reality" interfaces for mobile devices using optical character recognition to provide pronunciation training on text found in user environments. In 2024, audio multimodal large language models were first described as assessing pronunciation. That work has been carried forward by other researchers in 2025 who report positive results. Subsequently, researchers demonstrated pronunciation scoring by providing a language model with textual descriptions of speech, including the speech-to-text transcript, phoneme sequences, pauses, and phoneme sequence matching; this approach can achieve performance similar to multimodal LLMs that analyze raw audio while avoiding their higher computational cost. In 2025, the Duolingo English Test authors published a description of their pronunciation assessment method, purportedly built to measure intelligibility rather than accent imitation. While achieving a correlation of 0.82 with expert human ratings, very close to inter-rater agreement and outperforming alternative methods, the method is nonetheless based on experts' scores along the six-point CEFR common reference levels scale, instead of actual blinded listener transcriptions. Further promising work in 2025 includes assessment feedback aligning learner speech to synthetic utterances using interpretable features, identifying continuous spans of words for remediation feedback; synthesizing corrected speech matching learners' self-perceived voices, which they prefer and imitate more accurately as corrections; and streaming such interactions. On January 21, 2026, Educational Testing Service's TOEFL iBT high-stakes English language test, required by US university admissions and employers from English as a foreign language applicants more often than all other internet-based tests combined, changed its speaking assessments. While official rubrics claim that the new scoring will be based primarily on intelligibility, the new test's technical description indicates that it ju
PatchMatch
PatchMatch is an algorithm used to quickly find correspondences (or matches) between small square regions (or patches) of an image. It has various applications in image editing, such as reshuffling or removing objects from images or altering their aspect ratios without cropping or noticeably stretching them. PatchMatch was first presented in a 2011 paper by researchers at Princeton University. == Algorithm == The goal of the algorithm is to find the patch correspondence by defining a nearest-neighbor field (NNF) as a function f : R 2 → R 2 {\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} ^{2}} of offsets, which is over all possible matches of patch (location of patch centers) in image A, for some distance function of two patches D {\displaystyle D} . So, for a given patch coordinate a {\displaystyle a} in image A {\displaystyle A} and its corresponding nearest neighbor b {\displaystyle b} in image B {\displaystyle B} , f ( a ) {\displaystyle f(a)} is simply b − a {\displaystyle b-a} . However, if we search for every point in image B {\displaystyle B} , the work will be too hard to complete. So the following algorithm is done in a randomized approach in order to accelerate the calculation speed. The algorithm has three main components. Initially, the nearest-neighbor field is filled with either random offsets or some prior information. Next, an iterative update process is applied to the NNF, in which good patch offsets are propagated to adjacent pixels, followed by random search in the neighborhood of the best offset found so far. Independent of these three components, the algorithm also uses a coarse-to-fine approach by building an image pyramid to obtain the better result. === Initialization === When initializing with random offsets, we use independent uniform samples across the full range of image B {\displaystyle B} . This algorithm avoids using an initial guess from the previous level of the pyramid because in this way the algorithm can avoid being trapped in local minima. === Iteration === After initialization, the algorithm attempted to perform iterative process of improving the N N F {\displaystyle NNF} . The iterations examine the offsets in scan order (from left to right, top to bottom), and each undergoes propagation followed by random search. === Propagation === We attempt to improve f ( x , y ) {\displaystyle f(x,y)} using the known offsets of f ( x − 1 , y ) {\displaystyle f(x-1,y)} and f ( x , y − 1 ) {\displaystyle f(x,y-1)} , assuming that the patch offsets are likely to be the same. That is, the algorithm will take new value for f ( x , y ) {\displaystyle f(x,y)} to be arg min ( x , y ) D ( f ( x , y ) ) , D ( f ( x − 1 , y ) ) , D ( f ( x , y − 1 ) ) {\displaystyle \arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}} . So if f ( x , y ) {\displaystyle f(x,y)} has a correct mapping and is in a coherent region R {\displaystyle R} , then all of R {\displaystyle R} below and to the right of f ( x , y ) {\displaystyle f(x,y)} will be filled with the correct mapping. Alternatively, on even iterations, the algorithm search for different direction, fill the new value to be arg min ( x , y ) { D ( f ( x , y ) ) , D ( f ( x + 1 , y ) ) , D ( f ( x , y + 1 ) ) } {\displaystyle \arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}} . === Random search === Let v 0 = f ( x , y ) {\displaystyle v_{0}=f(x,y)} , we attempt to improve f ( x , y ) {\displaystyle f(x,y)} by testing a sequence of candidate offsets at an exponentially decreasing distance from v 0 {\displaystyle v_{0}} u i = v 0 + w α i R i {\displaystyle u_{i}=v_{0}+w\alpha ^{i}R_{i}} where R i {\displaystyle R_{i}} is a uniform random in [ − 1 , 1 ] × [ − 1 , 1 ] {\displaystyle [-1,1]\times [-1,1]} , w {\displaystyle w} is a large window search radius which will be set to maximum picture size, and α {\displaystyle \alpha } is a fixed ratio often assigned as 1/2. This part of the algorithm allows the f ( x , y ) {\displaystyle f(x,y)} to jump out of local minimum through random process. === Halting criterion === The often used halting criterion is set the iteration times to be about 4~5. Even with low iteration, the algorithm works well.
PropBank
PropBank is a corpus that is annotated with verbal propositions and their arguments—a "proposition bank". Although "PropBank" refers to a specific corpus produced by Martha Palmer et al., the term propbank is also coming to be used as a common noun referring to any corpus that has been annotated with propositions and their arguments. The PropBank project has played a role in research in natural language processing, and has been used in semantic role labelling. == Comparison == PropBank differs from FrameNet, the resource to which it is most frequently compared, in several ways. PropBank is a verb-oriented resource, while FrameNet is centered on the more abstract notion of frames, which generalizes descriptions across similar verbs (e.g. "describe" and "characterize") as well as nouns and other words (e.g. "description"). PropBank does not annotate events or states of affairs described using nouns. PropBank commits to annotating all verbs in a corpus, whereas the FrameNet project chooses sets of example sentences from a large corpus and only in a few cases has annotated longer continuous stretches of text. PropBank-style annotations often remain close to the syntactic level, while FrameNet-style annotations are sometimes more semantically motivated. From the start, PropBank was developed with the idea of serving as training data for machine learning-based semantic role labeling systems in mind. It requires that all arguments to a verb be syntactic constituents and different senses of a word are only distinguished if the differences bear on the arguments. Due to such differences, semantic role labeling with respect to PropBank is often a somewhat easier task than producing FrameNet-style annotations.
Blackmagic Design
Blackmagic Design Pty Ltd is an Australian company that develops digital cinema technology and manufactures professional video production hardware and software. Headquartered in South Melbourne, it is known for producing high-end digital movie cameras and a range of broadcast and post-production equipment. The company also develops software applications, including the DaVinci Resolve application for non-linear video editing, color correction, color grading, visual effects, and audio post-production. == History == Blackmagic Design Pty Ltd was founded on 7 September 2001 by Grant Petty. Its first product, DeckLink, introduced in 2002, was a video capture card for macOS that supported uncompressed 10-bit video, marking a shift toward professional-grade yet affordable video workflows. Subsequent versions—including the DeckLink 2, Pro SDI, HD Plus, and Multibridge—added capabilities such as color correction, Windows support, and compatibility with major editing software like Adobe Premiere Pro, to broaden the product's appeal. At the 2012 NAB Show, Blackmagic announced its first Cinema Camera, a digital movie camera. Blackmagic made several acquisitions over the next decade. In 2009, it acquired da Vinci Systems, known for its color-grading tools. In 2010, it acquired Echolab's ATEM switcher line, in 2014, it added eyeon Software (developer of the Blackmagic Fusion compositing software) and London's Cintel (film scanning and restoration), and in 2016, it acquired Fairlight, an audio technology company known for its CMI synthesizers as well as mixing consoles. == Products == List of all products developed by the company. Editing, Color Correction and Audio Post Production DaVinci Resolve (free version) and DaVinci Resolve Studio (paid version), computer software for non-linear video editing, color correction, color grading, visual effects, and audio post-production. Audio/Video Controller Consoles: Editor Keyboard, Speed Editor, DaVinci Resolve Replay Editor, Micro Panel, Mini Panel, DaVinci Resolve Micro Color Panel, Advanced Panel, Fairlight Console Channel Fader, Fairlight Console Channel Control, Fairlight Console LCD Monitor, Fairlight Console Audio Editor, Fairlight Desktop Audio Editor, Fairlight Desktop Console, Fairlight Audio Interface Cintel Film Scanner (Generations 1-3) Live Production Home Streaming: ATEM Mini, ATEM Mini Pro/ISO, ATEM Mini Extreme, ATEM Mini Extreme ISO (The ATEM Mini series has both HDMI and SDI variants) Production Switchers: ATEM 1,2 & 4 M/E Constellation HD, ATEM 1,2 & 4 M/E Constellation 4K, ATEM Constellation 8K, ATEM 1,2 & 4 M/E Production Studio 4K, ATEM Television Studio HD8 & HD8 ISO Switcher & Camera Controllers: ATEM Camera Control Panel, ATEM 1 M/E Advanced Panel, ATEM 2 M/E Advanced Panel, ATEM 4 M/E Advanced Panel Chroma Keyers: Ultimatte 12 HD Mini, Ultimatte 12 HD, Ultimatte 12 4K, Ultimatte 12 8K Recording and Storage: HyperDeck Studio HD Mini, HyperDeck Studio HD Plus, HyperDeck Studio HD Plus, HyperDeck Studio 4K Pro, HyperDeck Extreme 8K HDR, HyperDeck Extreme 4K HDR, HyperDeck Extreme Control, HyperDeck Shuttle HD, Duplicator 4K, MultiDock 10G, Video Assist 7" 12G HDR, Video Assist 5" 12G HDR Capture and Playback UltraStudio: 3G, HD Mini, 4K Mini, 4K Extreme 3 DeckLink (PCIe cards): Mini Recorder, Mini Monitor, Mini Monitor 4K, Mini Recorder 4K, Duo 2 Mini, Duo 2, Quad 2, SDI 4K, Studio 4K, 4K Extreme 12G, 8K Pro, Quad HDMI Recorder Network Storage Cloud Store Cloud Pod Broadcast Converters Micro Converter: BiDirectional SDI/HDMI 3G wPSU, HDMI to SDI 3G wPSU, SDI to HDMI 3G wPSU, BiDirectional SDI/HDMI 3G, HDMI to SDI 3G, SDI to HDMI 3G Mini Converters: Audio to SDI, Optical Fiber 12G, SDI Multiplex 4K, Quad SDI to HDMI 4K, SDI Distribution 4K, SDI to Analog 4K, Audio to SDI 4K, SDI to Audio 4K, HDMI to SDI 6G, SDI to HDMI 6G Teranex Mini: SDI Distribution 12G, SDI to HDMI 12G, Audio to SDI 12G, SDI to Analog 12G, SDI to HDMI 8K HDR, SDI to DisplayPort 8K HDR 2110 IP Converters Routing and Distribution Videohub
Mean shift
Mean shift is a non-parametric feature-space mathematical analysis technique for locating the maxima of a density function, a so-called mode-seeking algorithm. Application domains include cluster analysis in computer vision and image processing. == History == The mean shift procedure is usually credited to work by Fukunaga and Hostetler in 1975. It is, however, reminiscent of earlier work by Schnell in 1964. == Overview == Mean shift is a procedure for locating the maxima—the modes—of a density function given discrete data sampled from that function. This is an iterative method, and we start with an initial estimate x {\displaystyle x} . Let a kernel function K ( x i − x ) {\displaystyle K(x_{i}-x)} be given. This function determines the weight of nearby points for re-estimation of the mean. Typically a Gaussian kernel on the distance to the current estimate is used, K ( x i − x ) = e − c | | x i − x | | 2 {\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}} . The weighted mean of the density in the window determined by K {\displaystyle K} is m ( x ) = ∑ x i ∈ N ( x ) K ( x i − x ) x i ∑ x i ∈ N ( x ) K ( x i − x ) {\displaystyle m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i}}{\sum _{x_{i}\in N(x)}K(x_{i}-x)}}} where N ( x ) {\displaystyle N(x)} is the neighborhood of x {\displaystyle x} , a set of points for which K ( x i − x ) ≠ 0 {\displaystyle K(x_{i}-x)\neq 0} . The difference m ( x ) − x {\displaystyle m(x)-x} is called mean shift in Fukunaga and Hostetler. The mean-shift algorithm now sets x ← m ( x ) {\displaystyle x\leftarrow m(x)} , and repeats the estimation until m ( x ) {\displaystyle m(x)} converges. Although the mean shift algorithm has been widely used in many applications, a rigid proof for the convergence of the algorithm using a general kernel in a high dimensional space is still not known. Aliyari Ghassabeh showed the convergence of the mean shift algorithm in one dimension with a differentiable, convex, and strictly decreasing profile function. However, the one-dimensional case has limited real world applications. Also, the convergence of the algorithm in higher dimensions with a finite number of the stationary (or isolated) points has been proved. However, sufficient conditions for a general kernel function to have finite stationary (or isolated) points have not been provided. Gaussian Mean-Shift is an Expectation–maximization algorithm. == Details == Let data be a finite set S {\displaystyle S} embedded in the n {\displaystyle n} -dimensional Euclidean space, X {\displaystyle X} . Let K {\displaystyle K} be a flat kernel that is the characteristic function of the λ {\displaystyle \lambda } -ball in X {\displaystyle X} , In each iteration of the algorithm, s ← m ( s ) {\displaystyle s\leftarrow m(s)} is performed for all s ∈ S {\displaystyle s\in S} simultaneously. The first question, then, is how to estimate the density function given a sparse set of samples. One of the simplest approaches is to just smooth the data, e.g., by convolving it with a fixed kernel of width h {\displaystyle h} , where x i {\displaystyle x_{i}} are the input samples and k ( r ) {\displaystyle k(r)} is the kernel function (or Parzen window). h {\displaystyle h} is the only parameter in the algorithm and is called the bandwidth. This approach is known as kernel density estimation or the Parzen window technique. Once we have computed f ( x ) {\displaystyle f(x)} from the equation above, we can find its local maxima using gradient ascent or some other optimization technique. The problem with this "brute force" approach is that, for higher dimensions, it becomes computationally prohibitive to evaluate f ( x ) {\displaystyle f(x)} over the complete search space. Instead, mean shift uses a variant of what is known in the optimization literature as multiple restart gradient descent. Starting at some guess for a local maximum, y k {\displaystyle y_{k}} , which can be a random input data point x 1 {\displaystyle x_{1}} , mean shift computes the gradient of the density estimate f ( x ) {\displaystyle f(x)} at y k {\displaystyle y_{k}} and takes an uphill step in that direction. == Types of kernels == Kernel definition: Let X {\displaystyle X} be the n {\displaystyle n} -dimensional Euclidean space, R n {\displaystyle \mathbb {R} ^{n}} . The norm of x {\displaystyle x} is a non-negative number, ‖ x ‖ 2 = x ⊤ x ≥ 0 {\displaystyle \|x\|^{2}=x^{\top }x\geq 0} . A function K : X → R {\displaystyle K:X\rightarrow \mathbb {R} } is said to be a kernel if there exists a profile, k : [ 0 , ∞ ] → R {\displaystyle k:[0,\infty ]\rightarrow \mathbb {R} } , such that K ( x ) = k ( ‖ x ‖ 2 ) {\displaystyle K(x)=k(\|x\|^{2})} and k is non-negative. k is non-increasing: k ( a ) ≥ k ( b ) {\displaystyle k(a)\geq k(b)} if a < b {\displaystyle a