waashk/dblp huggingface dataset:
regular texture analysis as statistical model selection. an approach to the analysis of images of regular texture is proposed in which lattice hypotheses are used to define statistical models. these models are then compared in terms of their ability to explain the image. a method based on this approach is described in which lattice hypotheses are generated using analysis of peaks in the image autocorrelation function, statistical models are based on gaussian or gaussian mixture clusters, and model comparison is performed using the marginal likelihood as approximated by the bayes information criterion (bic). experiments on public domain regular texture images and a commercial textile image archive demonstrate substantially improved accuracy compared to two competing methods. the method is also used for classification of texture images as regular or irregular. an application to thumbnail image extraction is discussed.
three dimensional curvilinear structure detection using optimally oriented flux. this paper proposes a novel curvilinear structure detector, called optimally oriented flux (oof). oof finds an optimal axis on which image gradients are projected in order to compute the image gradient flux. the computation of oof is localized at the boundaries of local spherical regions. it avoids considering closely located adjacent structures. the main advantage of oof is its robustness against the disturbance induced by closely located adjacent objects. moreover, the analytical formulation of oof introduces no additional computation load as compared to the calculation of the hessian matrix which is widely used for curvilinear structure detection. it is experimentally demonstrated that oof delivers accurate and stable curvilinear structure detection responses under the interference of closely located adjacent structures as well as image noise.
co-recognition of image pairs by data-driven monte carlo image exploration. we introduce a new concept of `co-recognition' for object-level image matching between an arbitrary image pair. our method augments putative local region matches to reliable object-level correspondences without any supervision or prior knowledge on common objects. it provides the number of reliable common objects and the dense correspondences between the image pair. in this paper, generative model for co-recognition is presented. for inference, we propose data-driven monte carlo image exploration which clusters and propagates local region matches by markov chain dynamics. the global optimum is achieved by a guiding force of our data-driven sampling and posterior probability model. in the experiments, we demonstrate the power and utility on image retrieval and unsupervised recognition and segmentation of multiple common objects.
scene segmentation for behaviour correlation. this paper presents a novel framework for detecting abnormal pedestrian and vehicle behaviour by modelling cross-correlation among different co-occurring objects both locally and globally in a given scene. we address this problem by first segmenting a scene into semantic regions according to how object events occur globally in the scene, and second modelling concurrent correlations among regional object events both locally (within the same region) and globally (across different regions). instead of tracking objects, the model represents behaviour based on classification of atomic video events, designed to be more suitable for analysing crowded scenes. the proposed system works in an unsupervised manner throughout using automatic model order selection to estimate its parameters given video data of a scene for a brief training period. we demonstrate the effectiveness of this system with experiments on public road traffic data.
action recognition with a bio-inspired feedforward motion processing model: the richness of center-surround interactions. here we show that reproducing the functional properties of mt cells with various center---surround interactions enriches motion representation and improves the action recognition performance. to do so, we propose a simplified bio---inspired model of the motion pathway in primates: it is a feedforward model restricted to v1-mt cortical layers, cortical cells cover the visual space with a foveated structure and, more importantly, we reproduce some of the richness of center-surround interactions of mt cells. interestingly, as observed in neurophysiology, our mt cells not only behave like simple velocity detectors, but also respond to several kinds of motion contrasts. results show that this diversity of motion representation at the mt level is a major advantage for an action recognition task. defining motion maps as our feature vectors, we used a standard classification method on the weizmann database: we obtained an average recognition rate of 98.9%, which is superior to the recent results by jhuang et al. (2007). these promising results encourage us to further develop bio---inspired models incorporating other brain mechanisms and cortical layers in order to deal with more complex videos.
learning from real images to model lighting variations for face images. for robust face recognition, the problem of lighting variation is considered as one of the greatest challenges. since the nine points of light (9pl) subspace is an appropriate low-dimensional approximation to the illumination cone, it yielded good face recognition results under a wide range of difficult lighting conditions. however building the 9pl subspace for a subject requires 9 gallery images under specific lighting conditions, which are not always possible in practice. instead, we propose a statistical model for performing face recognition under variable illumination. through this model, the nine basis images of a face can be recovered via maximum-a-posteriori (map) estimation with only one gallery image of that face. furthermore, the training procedure requires only some real images and avoids tedious processing like svd decomposition or the use of geometric (3d) or albedo information of a surface. with the recovered nine dimensional lighting subspace, recognition experiments were performed extensively on three publicly available databases which include images under single and multiple distant point light sources. our approach yields better results than current ones. even under extreme lighting conditions, the estimated subspace can still represent lighting variation well. the recovered subspace retains the main characteristics of 9pl subspace. thus, the proposed algorithm can be applied to recognition under variable lighting conditions.
locating facial features with an extended active shape model. we make some simple extensions to the active shape model of cootes et al. [4], and use it to locate features in frontal views of upright faces. we show on independent test data that with the extensions the active shape model compares favorably with more sophisticated methods. the extensions are (i) fitting more landmarks than are actually needed (ii) selectively using two- instead of one-dimensional landmark templates (iii) adding noise to the training set (iv) relaxing the shape model where advantageous (v) trimming covariance matrices by setting most entries to zero, and (vi) stacking two active shape models in series.
higher dimensional affine registration and vision applications. affine registration has a long and venerable history in computer vision literature, and extensive work have been done for affine registrations in ℝ2 and ℝ3. in this paper, we study affine registrations in ℝ m for m > 3, and to justify breaking this dimension barrier, we show two interesting types of matching problems that can be formulated and solved as affine registration problems in dimensions higher than three: stereo correspondence under motion and image set matching. more specifically, for an object undergoing non-rigid motion that can be linearly modelled using a small number of shape basis vectors, the stereo correspondence problem can be solved by affine registering points in ℝ3n . and given two collections of images related by an unknown linear transformation of the image space, the correspondences between images in the two collections can be recovered by solving an affine registration problem in ℝm, where m is the dimension of a pca subspace. the algorithm proposed in this paper estimates the affine transformation between two point sets in ℝm. it does not require continuous optimization, and our analysis shows that, in the absence of data noise, the algorithm will recover the exact affine transformation for almost all point sets with the worst-case time complexity of o(mk 2), k the size of the point set. we validate the proposed algorithm on a variety of synthetic point sets in different dimensions with varying degrees of deformation and noise, and we also show experimentally that the two types of matching problems can indeed be solved satisfactorily using the proposed affine registration algorithm.
image segmentation in the presence of shadows and highlights. the segmentation method proposed in this paper is based on the observation that a single physical reflectance can have many different image values. we call the set of all these values a dominant colour. these variations are caused by shadows, shading and highlights and due to varying object geometry. the main idea is that dominant colours trace connected ridges in the chromatic histogram. to capture them, we propose a new ridge based distribution analysis (rad) to find the set of ridges representative of the dominant colour. first, a multilocal creaseness technique followed by a ridge extraction algorithm is proposed. afterwards, a flooding procedure is performed to find the dominant colours in the histogram. qualitative results illustrate the ability of our method to obtain excellent results in the presence of shadow and highlight edges. quantitative results obtained on the berkeley data set show that our method outperforms state-of-the-art segmentation methods at low computational cost.
a pose-invariant descriptor for human detection and segmentation. we present a learning-based, sliding window-style approach for the problem of detecting humans in still images. instead of traditional concatenation-style image location-based feature encoding, a global descriptor more invariant to pose variation is introduced. specifically, we propose a principled approach to learning and classifying human/non-human image patterns by simultaneously segmenting human shapes and poses, and extracting articulation-insensitive features. the shapes and poses are segmented by an efficient, probabilistic hierarchical part-template matching algorithm, and the features are collected in the context of poses by tracing around the estimated shape boundaries. histograms of oriented gradients are used as a source of low-level features from which our pose-invariant descriptors are computed, and kernel svms are adopted as the test classifiers. we evaluate our detection and segmentation approach on two public pedestrian datasets.
constructing category hierarchies for visual recognition. class hierarchies are commonly used to reduce the complexity of the classification problem. this is crucial when dealing with a large number of categories. in this work, we evaluate class hierarchies currently constructed for visual recognition. we show that top-down as well as bottom-up approaches, which are commonly used to automatically construct hierarchies, incorporate assumptions about the separability of classes. those assumptions do not hold for visual recognition of a large number of object categories. we therefore propose a modification which is appropriate for most top-down approaches. it allows to construct class hierarchies that postpone decisions in the presence of uncertainty and thus provide higher recognition accuracy. we also compare our method to a one-against-all approach and show how to control the speed-for-accuracy trade-off with our method. for the experimental evaluation, we use the caltech-256 visual object classes dataset and compare to state-of-the-art methods.
graph decompositions and secret sharing schemes. in this paper, we continue a study of secret sharing schemes for access structures based on graphs. given a graph g, we require that a subset of participants can compute a secret key if they contain an edge of g otherwise, they can obtain no information regarding the key. we study the information rate of such schemes, which measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, which is the ratio between the secret size and the arithmetic mean of the size of the shares. we give both upper and lower bounds on the optimal information rate and average information rate that can be obtained. upper bounds arise by applying entropy arguments due to capocelli et al [10]. lower bounds come from constructions that are based on graph decompositions. application of these constructions requires solving a particular linear programming problem. we prove some general results concerning the information rate and average information rate for paths, cycles and trees. also, we study the 30 (connected) graphs on at most five vertices, obtaining exact values for the optimal information rate in 26 of the 30 cases, and for the optimal avebage information rate in 28 of the 30 cases.
cryptanalysis of rsa with private key less than . we show that if the private exponent d used in the rsa public-key cryptosystem is less than n0:292 then the system is insecure. this is first improvement over an old result of wiener showing that when d < n0:25 the rsa system is insecure. we hope our approach can be used to eventually improve the bound to d < n0:5.
aggregate and verifiably encrypted signatures from bilinear maps. an aggregate signature scheme is a digital signature that supports aggregation: given n signatures on n distinct messages from n distinct users, it is possible to aggregate all these signatures into a single short signature. this single signature (and the n original messages) will convince the verifier that the n users did indeed sign the n original messages (i.e., user i signed message mi for i = 1, . . . , n). in this paper we introduce the concept of an aggregate signature, present security models for such signatures, and give several applications for aggregate signatures. we construct an efficient aggregate signature from a recent short signature scheme based on bilinear maps due to boneh, lynn, and shacham. aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size in secure routing protocols such as sbgp. we also show that aggregate signatures give rise to verifiably encrypted signatures. such signatures enable the verifier to test that a given ciphertext c is the encryption of a signature on a given message m. verifiably encrypted signatures are used in contract-signing protocols. finally, we show that similar ideas can be used to extend the short signature scheme to give simple ring signatures.
two attacks on reduced idea. in 1991 lai, massey and murphy introduced the ipes (improved proposed encryption standard), later renamed idea (international data encryption algorithm). in this paper we give two new attacks on a reduced number of rounds of idea. a truncated differential attack on idea reduced to 3.5 rounds and a differential-linear attack on idea reduced to 3 rounds. the truncated differential attack contains a novel method for determining the secret key.
public-key encryption in a multi-user setting: security proofs and improvements. this paper addresses the security of public-key cryptosystems in a "multi-user" setting, namely in the presence of attacks involving the encryption of related messages under different public keys, as exemplified by håstad's classical attacks on rsa. we prove that security in the single-user setting implies security in the multi-user setting as long as the former is interpreted in the strong sense of "indistinguishability," thereby pin-pointing many schemes guaranteed to be secure against håstad-type attacks. we then highlight the importance, in practice, of considering and improving the concrete security of the general reduction, and present such improvements for two diffie-hellman based schemes, namely el gamal and cramer-shoup.
efficient proofs that a committed number lies in an interval. alice wants to prove that she is young enough to borrow money from her bank, without revealing her age. she therefore needs a tool for proving that a committed number lies in a specific interval. up to now, such tools were either inefficient (too many bits to compute and to transmit) or inexact (i.e. proved membership to a much larger interval). this paper presents a new proof, which is both efficient and exact. here, "efficient" means that there are less than 20 exponentiations to perform and less than 2 kbytes to transmit. the potential areas of application of this proof are numerous (electronic cash, group signatures, publicly verifiable secret encryption, etc ...).
batch diffie-hellman key agreement systems and their application to portable communications. rsa (rivest, shamir and adleman) is today's most popular public key encryption scheme. batch-rsa (due to fiat) is a method to compute many (n/log22(n), where n is the security parameter) rsa decryption operations at a computational cost approaching that of one normal decryption. it requires that all the operations use the same modulus, but distinct, relatively prime in pairs, short, public exponents. a star-like key agreement scheme could use such a system to slash computational complexity at the center. we show a real life example of such a system - secure portable telephony. unfortunately, in this system batch-rsa cannot be employed effectively, due to a delay component which arises from the nature of rsa key exchange. we show that mathematical ideas similar to fiat's can lead to a batch-diffie-hellman key agreement scheme, that does not suffer such delay and is comparable in efficiency to batch-rsa. we prove that with some precautions, this system is as hard to break as rsa with short public exponent. in practice our method improves processing time at the center by a factor of 6 to 17 when compared to (non-batch) diffie-hellman schemes with full-size exponents and moduli in the practical range. smaller improvements (on the order of 1.6 to 3) are obtainable when compared to a diffie-hellman scheme employing abbreviated exponents.
the exact security of digital signatures - how to sign with rsa and rabin. we describe an rsa-based signing scheme which combines essentially optimal efficiency with attractive security properties. signing takes one rsa decryption plus some hashing, verification takes one rsa encryption plus some hashing, and the size of the signature is the size of the modulus. assuming the underlying hash functions are ideal, our schemes are not only provably secure, but are so in a tight way-- an ability to forge signatures with a certain amount of computational resources implies the ability to invert rsa (on the same size modulus) with about the same computational effort. furthermore, we provide a second scheme which maintains all of the above features and in addition provides message recovery. these ideas extend to provide schemes for rabin signatures with analogous properties; in particular their security can be tightly related to the hardness of factoring.
how to broadcast a secret. a single transmitter wishes to broadcast a secret to some subset of his listeners. he does not wish to perform, for each of the intended recipients, a separate encryption either of the secret or of a single key with which to protect the secret. a general method for such a secret broadcasting scheme is proposed. it is based on "k out of n" secret sharing. an example using polynomial interpolation is presented as well as a related vector formulation.
on the development of a fast elliptic curve cryptosystem. in this paper, we look at the development of a high speed elliptic curve cryptosystem based on a 40 mhz. motorola m68030 processor and a high speed optimal normal basis coprocessor for the ground field gf(2155). the advantage of this system is the relatively small block size required for high security applications such as key management and digital signatures. in addition, the design is very compact and efficient and can be easily fit onto a standard smart card wafer (the coprocessor core requires less than 1.sq.mil. or < 48% of the area available on a smart card).
captcha: using hard ai problems for security. we introduce captcha, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a captcha can be used to solve an unsolved artificial intelligence (ai) problem. we provide several novel constructions of captchas. since captchas have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard ai problems for security purposes allows us to advance the field of artificial intelligence. we introduce two families of ai problems that can be used to construct captchas and we show that solutions to such problems can be used for steganographic communication. captchas based on these ai problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels.
foiling birthday attacks in length-doubling transformations - benes: a non-reversible alternative to feistel. for many cryptographic primitives, e.g., hashing and psendorandom functions & generators, doubling the output length is useful even if the doubling transformation is not reversible. for these cases, we present a non-reversible construction based on a belies network, as an alternative to the traditional feistel construction (which is the basis of des). assuming that a given primitive behaves likc an n-bit to n-bit random function, we present a length-doubling scheme that yields a 2n-bit to 2n-bit function that provably requires ω(2n) queries to distinguish with θ(1) probability from a truly random function of that length. this is true even if the adversary is of unlimited computing power arid is allowed to query the function adaptively. oiir construction is minimal in the sense that omitting any operation makes the resulting network susceptible to birthday attacks using o(2n/2) queries. feistel networks also use truly random n-bit functions to achieve 2n- bit functions. luby and rackoff [16] showed that 3 and 4 round feistel networks require ω(2n/2) queries to distinguish with θ(1) probability from truly random. we show that these bounds are tight by showing that these networks are susceptible various types of birthday attacks using o(2n/2) queries.
short discrete proofs. we show how to produce short proofs of theorems such that a distrusting verifier can be convinced that the theorem is true yet obtains no information about the proof itself. the proofs are non-interactive provided that the quadratic residuosity bit commitment scheme is available to the prover and verifier. for typical applications, the proofs are short enough to fit on a floppy disk.
non supersingular elliptic curves for public key cryptosystems. for public key cryptosystems multiplication on elliptic curves can be used instead of exponentiation in finite fields. one attack to such a system is embedding the elliptic curve group into the multiplicative group of a finite field via weilpairing; calculating the discrete logarithm on the curve by solving the discrete logarithm in the finite field. this attack can be avoided by constructing curves so that every embedding in a multiplicative group of a finite field requires a field of very large size.