Automatic video logo detection and removal

Most commercial television channels use video logos, which can be considered a form of visible watermark, as a declaration of intellectual property ownership. They are also used as a symbol of authorization to rebroadcast when original logos are used in conjunction with newer logos. An unfortunate side effect of such logos is the concomitant decrease in viewing pleasure. In this paper, we use the temporal correlation of video frames to detect and remove video logos. In the video-logo-detection part, as an initial step, the logo boundary box is first located by using a distance threshold of video frames and is further refined by employing a comparison of edge lengths. Second, our proposed Bayesian classifier framework locates fragments of logos called logo-lets. In this framework, we systematically integrate the prior knowledge about the location of the video logos and their intrinsic local features to achieve a robust detection result. In our logo-removal part, after the logo region is marked, a matching technique is used to find the best replacement patch for the marked region within that video shot. This technique is found to be useful for small logos. Furthermore, we extend the image inpainting technique to videos. Unlike the use of 2D gradients in the image inpainting technique, we inpaint the logo region of video frames by using 3D gradients exploiting the temporal correlations in video. The advantage of this algorithm is that the inpainted regions are consistent with the surrounding texture and hence the result is perceptually pleasing. We present the results of our implementation and demonstrate the utility of our method for logo removal.     

Towards coalgebraic behaviourism

In this paper we show that it is possible to model observable behaviour of coalgebras independently from their internal dynamics, but within the general framework of representing behaviour by a map into a “final” coalgebra.In the first part of the paper we characterise Set-endofunctors F with the property that bisimilarity of elements of F-coalgebras coincides with having the same observable behaviour. We show that such functors have the final coalgebra of a rather simple nature, and preserve some weak pullbacks. We also show that this is the case if and only if F-bisimilarity corresponds to logical equivalence in the finitary fragment of the coalgebraic logic.In the second part of the paper, we present a construction of a “final” coalgebra that captures the observable behaviour of F-coalgebras. We keep the word “final” quoted since the object we are going to construct need not belong to the original category. The construction is carried out for arbitrary Set-endofunctor F, throughout the construction we remain in Set, but the price to pay is the introduction of new morphisms. The paper concludes with a hint to a possible application to modelling weak bisimilarity for coalgebras.     

Improving children’s reading comprehension and use of strategies through computer-based strategy training

In this study, the attention–selection–organization–integration–monitoring (ASOIM) model, revised from Mayer’s [Mayer, R. E. (1996). Learning strategies for making sense out of expository text: The SOI model for guiding three cognitive processes in knowledge construction. Educational Psychology Review, 8, 357–371] SOI model of text comprehension, was used as a foundation to design a multi-strategy based system, which was named Computer Assisted Strategy Teaching and Learning Environment (CASTLE). CASTLE aims to enhance learners’ abilities of using reading strategies and text comprehension. The effects of CASTLE on students with different reading abilities were empirically evaluated. 130 sixth graders took part in an 11-week computer-based reading strategies course. The results show that CASTLE helps to enhance the students’ use of strategies and text comprehension at all ability levels.     

Matching typed and untyped realizability

Realizability interpretations of logics are given by saying what it means for computational objects of some kind to realize logical formulae. The computational objects in question might be drawn from an untyped universe of computation, such as a partial combinatory algebra, or they might be typed objects such as terms of a PCF-style programming language. In some instances, one can show that a particular untyped realizability interpretation matches a particular typed one, in the sense that they give the same set of realizable formulae. In this case, we have a very good fit indeed between the typed language and the untyped realizability model — we refer to this condition as (constructive) logical full abstraction.We give some examples of this situation for a variety of extensions of PCF. Of particular interest are some models that are logically fully abstract for typed languages including non-functional features. Our results establish connections between what is computable in various programming languages and what is true inside various realizability toposes. We consider some examples of logical formulae to illustrate these ideas, in particular their application to exact real-number computability.     

Algorithmic approach to the consecutive retrieval property

Ghosh's consecutive retrieval property (CR property) not only represents an elegant file organization, but also raises the problem of how to construct such a file with this property. Ghosh used ann ×m 0–1 incidence matrix, wheren is the number of records andm is the number of queries, as a tool for constructing a file with the CR property. In this paper the rows and columns of the incidence matrix are restricted to unique 0–1 patterns. It is found that such a unique incidence matrix cannot have the CR property if the number of rows is greater than 2m–1. This upper bound can be used to generatem(2m–1) columns, which form all the matrices with the CR property that may correspond to the given matrix. Two algorithms are presented which map the columns of the given incidence matrix to these columns with consecutive l's. A proposed implementation in terms of data base design is also presented.     

An intelligent content-based image retrieval methodology using transfer learning for digital IP protection

Trademarks are used by companies to help customers identify products or services using images or logos in addition to slogans, words, names, sounds, smells, color, and motions. Trademark logos are widely distributed through advertising and published through online media websites and social networks such as Facebook, Pinterest, and Flicker. The intellectual property (IP) rights of the trademark owners have strong legal protection when registered with international intellectual property platforms such as the US Patent and Trademark Office and the World Intellectual Property Office. Using a registered trademark without prior consent of the owner may result in intellectual property infringement with severe legal consequences under civil or criminal law. Companies invest large capital resources in protecting their trademark from being copied or misused in ways that confuse the customers or steal market share. This research focuses on trademark (TM) logo image retrieval systems used in the cyber marketplaces to identify similar TM logo images online automatically and intelligently. The methodology developed for TM logo similarity measurement is based on content-based image retrieval. Content retrieval reduces the gap between high-level semantic interpretation of human vision and the low-level features processed by the machine. The proposed transfer learning methodology uses embedded learning with triplet loss to fine-tune a pre-trained convolutional neural network model. The Logo-2K+ large-scale logo dataset is re-organized and divided into the top 70% as the training set and the remaining 30% as the testing set. The results show that the novel transfer learning approach is developed and demonstrated in this research for the intelligent automatic detection of similar TM logo images with high accuracy. The verification experiments (trained with 7625 logos and tested with 3221 logos) demonstrates that the Recall@10 of the test set can reach 95% using the advanced convolutional neural network model (VGG19) adjusted with the novel transfer learning methodology.     

Logo detection with extendibility and discrimination

Logos are specially designed marks that identify goods, services, and organizations using distinguished characters, graphs, signals, and colors. Identifying logos can facilitate scene understanding, intelligent navigation, and object recognition. Although numerous logo recognition methods have been proposed for printed logos, a few methods have been specifically designed for logos in photos. Furthermore, most recognition methods use codebook-based approaches for the logos in photos. A codebook-based method is concerned with the generation of visual words for all the logo models. When new logos are added, the codebook reconstruction is required if effectiveness is a crucial factor. Moreover, logo detection in natural scenes is difficult because of perspective tilt and non-rigid deformation. Therefore, this study develops an extendable, but discriminating, model-based logo detection method. The proposed logo detection method is based on a support vector machine (SVM) using edge-based histograms of oriented gradient (HOGE) as features through multi-scale sliding window scanning. Thereafter, anti-distortion affine scale invariant feature transform (ASIFT) is used for logo verification with constraints on the ASIFT matching pairs and neighbors. The experimental results using the public Flickr-Logo database confirm that the proposed method has a higher retrieval and precision accuracy compared to existing model-based methods.

     

Strong feedback cyclization for systems over rings

For nonnecessarily reachable systems over a commutative ring R, we define a strong form of feedback cyclization (FC). With this natural generalization of the FC property we obtain a feedback reduced form for systems over strong FC rings (i.e. rings for which every system verifies the FC property). In the particular case of reachable single input systems, this gives the usual control canonical form of Bumby et al. [Remarks on the pole-shifting problem over rings, J. Pure Appl. Algebra 20 (1981) 113–127]. Also it is proved that a commutative ring with 1 in its stable range has the strong FC property if and only if it has the UCU property, which is the natural parallel form of the result given by Brewer et al. [Pole assignability in polynomial rings, power series rings and Prüfer domains, J. Algebra 106 (1987) 265–286] for the reachable case. Many classes of rings which were known to be FC rings are in fact strong FC rings, but there are FC rings which are not strong FC rings.     

Type-based Initialization Analysis of a Synchronous Data-flow Language

One of the appreciated features of the synchronous data-flow approach is that a program defines a perfectly deterministic behavior. But the use of the delay primitive leads to undefined values at the first cycle; thus a data-flow program is really deterministic only if it can be shown that such undefined values do not affect the behavior of the system.This paper presents an initialization analysis that guarantees the deterministic behavior of programs. This property being undecidable in general, the paper proposes a safe approximation of the property, precise enough for most data-flow programs. This analysis is a one-bit analysis — expressions are either initialized or uninitialized — and is defined as an inference type system with sub-typing constraints. This analysis has been implemented in the Lucid Synchrone compiler and in a new Scade-Lustre prototype compiler. It gives very good results in practice.     

Type-based initialization analysis of a synchronous dataflow language

One of the appreciated features of the synchronous dataflow approach is that a program defines a perfectly deterministic behavior. But the use of the delay primitive leads to undefined values at the first cycle; thus a dataflow program is really deterministic only if it can be shown that such undefined values do not affect the behavior of the system.This paper presents an initialization analysis that guarantees the deterministic behavior of programs. This property being undecidable in general, the paper proposes a safe approximation of the property, precise enough for most dataflow programs. This analysis is a one-bit analysis – expressions are either initialized or uninitialized – and is defined as an inference-type system with subtyping constraints. This analysis has been implemented in the Lucid Synchrone compiler and in a new Scade-Lustre prototype compiler at Esterel Technologies. The analysis gives very good results in practice.     

Adequate Sets of Temporal Connectives in CTL

An adequate set of temporal connectives for CTL is a subset of the logic's temporal connectives that is sufficient to express equivalents for all CTL formulas.In this paper, a characterization of all such adequate sets is presented. Specifically, it is shown that a subset of CTL's temporal connectives is adequate if and only if it contains one of {AX, EX}, one of {EG, AF, AU}, and EU.The proof requires, among other things, the analysis of a certain class of models, the reflexive models. These models have the desirable property that several connectives become redundant, thus simplifying the analysis.     

Fuzzy identity based signature with applications to biometric authentication

We introduce a new cryptographic primitive which is the signature analog of fuzzy identity based encryption (FIBE). We call it fuzzy identity based signature (FIBS). It possesses similar error-tolerance property as FIBE that allows a user with the private key for identity ω to decrypt a ciphertext encrypted for identity ω′ if and only if ω and ω′ are within a certain distance judged by some metric. We give the definition and security model of FIBS and present the first practical FIBS scheme. We prove that our scheme is existentially unforgeable against adaptively chosen message attack in the standard model. To our best knowledge, this primitive was never considered in the identity based signature before. FIBS is of particular value for biometric authentication, where biometric identifiers such as fingerprints, iris, voice and gait are used in human identification. We demonstrate the applicability of our construction to secure biometric authentication.     

One-way functions and circuit complexity

A finite function f is a mapping of {0, 1}ⁿ into {0, 1}^m{#}, where “#” is a symbol to be thought of as “undefined.” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f_i(x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f_i(x) = y. A family of functions f_i(x) can be evaluated if some family of polynomial-size circuits with input x can compute f_i(x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP co-UP are equal. A family of functions f_i is one-way for constant depth circuits if f_i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f_i⁻¹ cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.     

Games with Uniqueness Properties

For two-player games of perfect information such as Checkers, Chess, and Go we introduce uniqueness properties. A game position has a uniqueness property if a winning strategy—should one exist—is forced to be unique. Depending on the way that winning strategy is forced, a uniqueness property is classified as weak, strong, or global. We prove that any reasonable two-player game G is extendable to a game G ^* with the strong uniqueness property for both players, so that, e.g., QBF remains PSPACE-complete under this reduction. For global uniqueness, we introduce a simple game over Boolean formulas with this property, and prove that any reasonable two-player game with the global uniqueness property is reducible to it. We show that the class of languages that reduce to globally unique games equals Niedermeier and Rossmaniths unambiguous alternation class UAP, which is in an interesting region between FewP and SPP.     

The balance problem of min–max systems is co-NP hard

Min–max systems are timed discrete event dynamic systems containing min, max and plus operations. A min–max system is balanced if it admits a global cycle time (generalized eigenvalue) for every possible assignment of parameters. This paper proves that the testing of the balance property for min–max systems is co-NP hard by showing that the test of inseparability is co-NP hard. The latter result is established on a new complexity result, namely, that the testing of existence of non-trivial fixed points for monotone Boolean functions is NP-complete.     

The zero divisor problem of multivariable stochastic adaptive control

Stochastic adaptive minimum variance control algorithms require a division by a function of a recursively computed parameter estimate at each instant of time. In order that the analysis of these algorithms is valid, zero divisions must be events of probability zero. This property is established for the stochastic gradient adaptive control algorithm under the condition that the initial state of the system and all finite segments of its random disturbance process have a joint distribution which is absolutely continuous with respect to Lebesgue measure. This result is deduced from the following general result established in this paper: a non-constant rational function of a finite set of random variables {x₁},x_n} is absolutely continuous with respect to Lebesgue measure if the joint distribution function of {x₁,…,x_n} has this property.     

Completeness and Counter-Example Generations of a Basic Protocol Logic: (Extended Abstract)

We give an axiomatic system in first-order predicate logic with equality for proving security protocols correct. Our axioms and inference rules derive the basic inference rules, which are explicitly or implicitly used in the literature of protocol logics, hence we call our axiomatic system Basic Protocol Logic (or BPL, for short). We give a formal semantics for BPL, and show the completeness theorem such that for any given query (which represents a correctness property) the query is provable iff it is true for any model. Moreover, as a corollary of our completeness proof, the decidability of provability in BPL holds for any given query. In our formal semantics we consider a “trace” any kind of sequence of primitive actions, counter-models (which are generated from an unprovable query) cannot be immediately regarded as realizable traces (i.e., attacked processes on the protocol in question). However, with the aid of Comon-Treinen's algorithm for the intruder deduction problem, we can determine whether there exists a realizable trace among formal counter-models, if any, generated by the proof-search method (used in our completeness proof). We also demonstrate that our method is useful for both proof construction and flaw analysis by using a simple example.     

Uq(sl(2)) Satisfies a Bernstein Duality

It is well known that in some cases the functorExt_R^μ( − , R) defines a duality between module categories. In earlier papers we studied when this duality can be represented by a bimodule and have characterized when this happens. In this paper, using some computational methods of noncommutative Gröbner bases in the construction of projective resolutions of irreducible finite-dimensional representations, we show new examples of algebras satisfying this property.     

Weakly useful sequences

An infinite binary sequence x is defined to be

(i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and

(ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x.

Juedes, Lathrop, and Lutz [Theorectical Computer Science 132 (1994) 37] proved that every weakly useful sequence is strongly deep in the sense of Bennett [The Universal Turing Machine: A Half-Century Survey, 1988, 227] and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the martingale diagonalization technique of Lutz [SIAM Journal on Computing 24 (1995) 1170] with a new technique, namely, the construction of a sequence that is “computably deep” with respect to an arbitrary, given uniform reducibility. The abundance of such computably deep sequences is also proven and used to show that every weakly useful sequence is computably deep with respect to every uniform reducibility.

Combining Local and Global Model Checking

The verification process of reactive systems in local model checking [1,7] and in explicit state model checking is[13,15] on-the-fly. Therefore only those states of a system have to be traversed that are necessary to prove a property. In addition, if the property does not hold, than often only a small subset of the state space has to be traversed to produce a counterexample. Global model checking [6,23] and, in particular, symbolic model checking [4,22] can utilize compact representations of the state space, e.g. BDDs [3], to handle much larger designs than what is possible with local and explicit model checking. We present a new model checking algorithm for LTL that combines both approaches. In essence, it is a generalization of the tableau construction of [1] that enables the use of BDDs but still is on-the-fly.