Mingwen Dong, Nischal Ashok Kumar, Yiqun Hu, Anuj Chauhan, Chung-Wei Hang, Shuaichen Chang, Lin Pan, Wuwei Lan, Henghui Zhu, Jiarong Jiang, Patrick Ng, Zhiguo Wang. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

A mixture of multinomial logits (MMNL) generalizes the single logit model, which is commonly used in predicting the probabilities of different outcomes. While extensive algorithms have been developed in the literature to learn MMNL models, theoretical results are limited. Built on the Frank-Wolfe (FW) method, we propose a new algorithm that learns both mixture weights and component-specific logit parameters with provable convergence guarantees for an arbitrary number of mixtures. Our algorithm utilizes historical choice data to generate a set of candidate choice probability vectors, each being close to the ground truth with a high probability. We further provide a sample complexity analysis to show that only a polynomial number of samples is required to secure the performance guarantee of our algorithm. Finally, we conduct simulation studies to evaluate the performance and demonstrate how to apply our algorithm to real-world applications.

In this work we propose a novel and compact Neighbor Reconstruction Method (NRM) which is a unified pre-processing method for graph-based sparse spectral algorithms. This method is conducted by vector operations on a central point and its corresponding neighbor points. NRM generates new neighbor points which can capture the local space structure of the central point more appropriately than original neighbor points. With NRM, a large number of sparse spectral based nonlinear feature extraction and selection algorithms gain significant improvement. Specifically, we embedded NRM to several classical algorithms, Local Linear Embedding (LLE) [1], Laplacian Eigenmaps (LE) [2] and Unsupervised Feature Selection for Multi-cluster Data (MCFS) [3], with accuracy improvement of up to 7%, 2.6%, 2.4% on ORL, CIFAR 10, and MINST data sets respectively. We also apply NRM to a Super Resolution algorithm, A+ [5], and obtain 0.12dB improvement than original method.

Simple nearest neighbor classification fails to exploit the additional information in image sets. We propose self-regularized nonnegative coding to define between set distance for robust face recognition. Set distance is measured between the nearest set points (samples) that can be approximated from their orthogonal basis vectors as well as from the set samples under the respective constraints of self-regularization and nonnegativity. Self-regularization constrains the orthogonal basis vectors to be similar to the approximated nearest point. The nonnegativity constraint ensures that each nearest point is approximated from a positive linear combination of the set samples. Both constraints are formulated as a single convex optimization problem and the accelerated proximal gradient method with linear-time Euclidean projection is adapted to efficiently find the optimal nearest points between two image sets. Using the nearest points between a query set and all the gallery sets as well as the active samples used to approximate them, we learn a more discriminative Mahalanobis distance for robust face recognition. The proposed algorithm works independently of the chosen features and has been tested on gray pixel values and local binary patterns. Experiments on three standard data sets show that the proposed method consistently outperforms existing state-of-the-art methods.

Image-To-Class (I2C) distance is a novel distance used for image classification and has successfully handled datasets with large intra-class variances. However, it uses Euclidean distance for measuring the distance between local features in different classes, which may not be the optimal distance metric in real image classification problems. In this article, we propose a distance metric learning method to improve the performance of I2C distance by learning per-class Mahalanobis metrics in a large margin framework. Our I2C distance is adaptive to different classes by combining with the learned metric for each class. These multiple per-class metrics are learned simultaneously by forming a convex optimization problem with the constraints that the I2C distance from each training image to its belonging class should be less than the distances to other classes by a large margin. A subgradient descent method is applied to efficiently solve this optimization problem. For efficiency and scalability to large-scale problems, we also show how to simplify the method to learn a diagonal matrix for each class. We show in experiments that our learned Mahalanobis I2C distance can significantly outperform the original Euclidean I2C distance as well as other distance metric learning methods in several prevalent image datasets, and our simplified diagonal matrices can preserve the performance but significantly speed up the metric learning procedure for large-scale datasets. We also show in experiment that our method is able to correct the class imbalance problem, which usually leads the NN-based methods toward classes containing more training images.

In this paper we present a salient object detection model from an over-segmented image. The input image is initially segmented by the mean-shift segmentation algorithm and then over-segmented by a quad mesh to even smaller segments. Such segmented regions overcome the disadvantage of using patches or single pixels to compute saliency. Segments that are similar and spread over the image receive low saliency and a segment which is distinct in the whole image or in a local region receives high saliency. We express this as a color compactness measure which is used to derive saliency level directly. Our method is shown to outperform six existing methods in the literature using a saliency detection database containing images with human-labeled object contour ground truth. The proposed saliency model has been shown to be useful for an image retargeting application.

We propose an efficient and robust solution for image set classification. A joint representation of an image set is proposed which includes the image samples of the set and their affine hull model. The model accounts for unseen appearances in the form of affine combinations of sample images. To calculate the between-set distance, we introduce the Sparse Approximated Nearest Point (SANP). SANPs are the nearest points of two image sets such that each point can be sparsely approximated by the image samples of its respective set. This novel sparse formulation enforces sparsity on the sample coefficients and jointly optimizes the nearest points as well as their sparse approximations. Unlike standard sparse coding, the data to be sparsely approximated are not fixed. A convex formulation is proposed to find the optimal SANPs between two sets and the accelerated proximal gradient method is adapted to efficiently solve this optimization. We also derive the kernel extension of the SANP and propose an algorithm for dynamically tuning the RBF kernel parameter while matching each pair of image sets. Comprehensive experiments on the UCSD/Honda, CMU MoBo, and YouTube Celebrities face datasets show that our method consistently outperforms the state of the art.

Detection of salient motion in a video involves determining which motion is attended to by the human visual system in the presence of background motion that consists of complex visuals that are constantly changing. Salient motion is marked by its predictability compared to the more complex unpredictable motion of the background such as fluttering of leaves, ripples in water, dispersion of smoke, and others. We introduce a novel approach to detect salient motion based on the concept of “observability” from the output pixels, when the video sequence is represented as a linear dynamical system. The group of output pixels with maximum saliency is further used to model the holistic dynamics of the salient region. The pixel saliency map is bolstered by two region-based saliency maps, which are computed based on the similarity of dynamics of the different spatiotemporal patches in the video with the salient region dynamics, in a global as well as a local sense. The resulting algorithm is tested on a set of challenging sequences and compared to state-of-the-art methods to showcase its superior performance on grounds of its computational efficiency and ability to detect salient motion.

Classification based on image sets has recently attracted great research interest as it holds more promise than single image based classification. In this paper, we propose an efficient and robust algorithm for image set classification. An image set is represented as a triplet: a number of image samples, their mean and an affine hull model. The affine hull model is used to account for unseen appearances in the form of affine combinations of sample images. We introduce a novel between-set distance called Sparse Approximated Nearest Point (SANP) distance. Unlike existing methods, the dissimilarity of two sets is measured as the distance between their nearest points, which can be sparsely approximated from the image samples of their respective set. Different from standard sparse modeling of a single image, this novel sparse formulation for the image set enforces sparsity on the sample coefficients rather than the model coefficients and jointly optimizes the nearest points as well as their sparse approximations. A convex formulation for searching the optimal SANP between two sets is proposed and the accelerated proximal gradient method is adapted to efficiently solve this optimization. Experimental evaluation was performed on the Honda, MoBo and Youtube datasets. Comparison with existing techniques shows that our method consistently achieves better results.

We propose `Contour Code', a novel representation and binary hash table encoding for multispectral palmprint recognition. We first present a reliable technique for the extraction of a region of interest (ROI) from palm images acquired with non-contact sensors. The Contour Code representation is then derived from the Nonsubsampled Contourlet Transform. A uniscale pyramidal filter is convolved with the ROI followed by the application of a directional filter bank. The dominant directional subband establishes the orientation at each pixel and the index corresponding to this subband is encoded in the Contour Code representation. Unlike existing representations which extract orientation features directly from the palm images, the Contour Code uses a two stage filtering to extract robust orientation features. The Contour Code is binarized into an efficient hash table structure that only requires indexing and summation operations for simultaneous one-to-many matching with an embedded score level fusion of multiple bands. We quantitatively evaluate the accuracy of the ROI extraction by comparison with a manually produced ground truth. Multispectral palmprint verification results on the PolyU and CASIA databases show that the Contour Code achieves an EER reduction upto 50%, compared to state-of-the-art methods.

We propose a new method for video retargeting, which can generate spatial-temporal consistent video. The new measure called spatial-temporal naturality preserves the motion in the source video without any motion analysis in contrast to other methods that need motion estimation. This advantage prevents the retargeted video from degenerating due to the propagation of the errors in motion analysis. It allows the proposed method to be applied on challenging videos with complex camera and object motion. To improve the efficiency of the retargeting process, we retarget video using a 3D shift map in low resolution and refine it using an incremental 2D shift map in higher resolution. This new hierarchical framework, denoted as hybrid shift map, can produce satisfactory retargeting results while significantly improving the computational efficiency.

Saliency detection is useful for high level applications such as adaptive compression, image retargeting, object recognition, etc. In this paper, we introduce an effective region-based solution for saliency detection. We first use the adaptive mean shift algorithm to extract superpixels from the input image, then apply Gaussian Mixture Model (GMM) to cluster superpixels based on their color similarity, and finally calculate the saliency value for each cluster using compactness metric together with modified PageRank propagation. This solution is able to represent the image in a perceptually meaningful way and is robust to over-segmentation. It highlights salient regions with full resolution, well-defined boundary. Experimental results show that both the adaptive mean shift and the modified PageRank algorithm contribute substantially to the saliency detection result. In addition, the ROC analysis demonstrates that our approach significantly outperforms five existing popular methods.

We formulate the problem of salient object detection in images as an automatic labeling problem on the vertices of a weighted graph. The seed (labeled) nodes are first detected using Markov random walks performed on two different graphs that represent the image. While the global properties of the image are computed from the random walk on a complete graph, the local properties are computed from a sparse k-regular graph. The most salient node is selected as the one which is globally most isolated but falls on a locally compact object. A few background nodes and salient nodes are further identified based upon the random walk based hitting time to the most salient node. The salient nodes and the background nodes will constitute the labeled nodes. A new graph representation of the image that represents the saliency between nodes more accurately, the "pop-out graph" model, is computed further based upon the knowledge of the labeled salient and background nodes. A semisupervised learning technique is used to determine the labels of the unlabeled nodes by optimizing a smoothness objective label function on the newly created "pop-out graph" model along with some weighted soft constraints on the labeled nodes.

We formulate the problem of salient region detection in images as Markov random walks performed on images represented as graphs. While the global properties of the image are extracted from the random walk on a complete graph, the local properties are extracted from a k-regular graph. The most salient node is selected as the one which is globally most isolated but falls on a compact object. The equilibrium hitting times of the ergodic Markov chain holds the key for identifying the most salient node. The background nodes which are farthest from the most salient node are also identified based on the hitting times calculated from the random walk. Finally, a seeded salient region identification mechanism is developed to identify the salient parts of the image. The robustness of the proposed algorithm is objectively demonstrated with experiments carried out on a large image database annotated with “ground-truth” salient regions.

Many multimedia applications can benefit from recognizing image content. It requires a robust and discriminative representation of objects, especially in the situation of only a few training samples available. In this paper, we present a new approach to integrate the advantages of bag-of-words model and part-based model for image recognition. Each image is encoded as a hierarchical word image (HWI), which contains not only visual appearance but also spatial information. The object parts are then located and represented in HWI. Finally, the part-based star model (SM) is used to learn the object model and recognize the test images. It is shown that our proposed approach can detect more accurate part candidates and significantly improve the performance of original part-based model for object recognition.

In this paper, we propose a large margin framework to learn the local instance-to-class distance function using local patch-based feature vectors, which satisfies the property that distance from instance to its own class should be less than the distance to other class. This instance-to-class distance is modeled as the weighted combination of the distance from every patch in test image to its nearest patch in training class, where the weight is learned through the above learning phase. We evaluate the proposed method on human action datasets and compare with related methods. It is shown that the proposed method achieves promising performance and improves the efficiency.

We present a robust salient region detection framework based on the color and orientation distribution in images. The proposed framework consists of a color saliency framework and an orientation saliency framework. The color saliency framework detects salient regions based on the spatial distribution of the component colors in the image space and their remoteness in the color space. The dominant hues in the image are used to initialize an expectation-maximization (EM) algorithm to fit a Gaussian mixture model in the hue-saturation (H-S) space. The mixture of Gaussians framework in H-S space is used to compute the inter-cluster distance in the H-S domain as well as the relative spread among the corresponding colors in the spatial domain. Orientation saliency framework detects salient regions in images based on the global and local behavior of different orientations in the image. The oriented spectral information from the Fourier transform of the local patches in the image is used to obtain the local orientation histogram of the image. Salient regions are further detected by identifying spatially confined orientations and with the local patches that possess high orientation entropy contrast. The final saliency map is selected as either color saliency map or orientation saliency map by automatically identifying which of the maps leads to the correct identification of the salient region. The experiments are carried out on a large image database annotated with ldquoground-truthrdquo salient regions, provided by Microsoft Research Asia, which enables us to conduct robust objective level comparisons with other salient region detection algorithms.

This paper presents an efficient and effective solution for retrieving image near-duplicate (IND) from image database. We introduce the coherent phrase model which incorporates the coherency of local regions to reduce the quantization error of the bag-of-words (BoW) model. In this model, local regions are characterized byvisual phraseof multiple descriptors instead of visual word of single descriptor. We propose two types of visual phrase to encode the coherency in feature and spatial domain, respectively. The proposed model reduces the number of false matches by using this coherency and generates sparse representations of images. Compared to other method, the local coherencies among multiple descriptors of every region improve the performance and preserve the efficiency for IND retrieval. The proposed method is evaluated on several benchmark datasets for IND retrieval. Compared to the state-of-the-art methods, our proposed model has been shown to significantly improve the accuracy of IND retrieval while maintaining the efficiency of the standard bag-of-words model. The proposed method can be integrated with other extensions of BoW.

In the past few years, there has been increased research interest in detecting previously unidentified events from Web resources. Our focus in this paper is to detect events from the click-through data generated by Web search engines. Existing event detection algorithms, which mainly study the news archive data, cannot be employed directly because of the following two unique features of click-through data: 1) the information provided by click-through data is quite limited; 2) not every query issued to a Web search engine corresponds to an event in the real world. In this paper, we address this problem by proposing an effective algorithm which Detects Events from ClicK-through data DECK. We firstly transform click-through data to the 2D polar space by considering the semantic dimension and temporal dimension of queries. Robust subspace estimation is performed to detect subspaces such that each subspace consists of queries of similar semantics. Next, we prune uninteresting subspaces which do not contain queries corresponding to real events by simultaneously considering the respective distribution of queries along the semantic dimension and the temporal dimension in each subspace. Finally, events are detected from interesting subspaces using a nonparametric clustering technique. Compared with an existing approach, our experimental results based on real-life data have shown that the proposed approach is more accurate and effective in detecting real events from click-through data.

This paper presents an efficient and effective solution for retrieving Image Near-Duplicate (IND). Different from traditional methods, we analyze the local dependencies among region descriptors in a spatial-scale space. Such local dependencies in spatial-scale space(LDSS) encodes not only visual appearance but also the spatial and scale co-occurrence of them. The local dependencies are integrated over all spatial locations and multiple scales to form the image representation, which is invariant to spatial transformation and scale change. We evaluate our proposed LDSS method for IND retrieval using an existing benchmark as well as a new dataset extracted from the keyframes of TRECVID corpus. Compared to the state-of-the-art results, local dependencies in spatial-scale space(LDSS) approach has been shown to significantly improve the accuracy of IND retrieval.

Although most of existing research usually detects events by analyzing the content or structural information of Web documents, a recent direction is to study the usage data. In this paper, we focus on detecting events from Web click-through data generated by Web search engines. We propose a novel approach which effectively detects events from click-through data based on robust subspace analysis. We first transform click-through data to the 2D polar space. Next, an algorithm based on Generalized Principal Component Analysis (GPCA) is used to estimate subspaces of transformed data such that each subspace contains query sessions of similar topics. Then, we prune uninteresting subspaces which do not contain query sessions corresponding to real events by considering both the semantic certainty and the temporal certainty of query sessions in each subspace. Finally, various events are detected from interesting subspaces by utilizing a nonparametric clustering technique. Compared with existing approaches, our experimental results based on real-life click-through data have shown that the proposed approach is more accurate in detecting real events and more effective in determining the number of events.

We describe a method to extract visual attention regions in images by robust subspace analysis from simple feature like intensity endowed with scale adaptivity in order to represent textured areas in an image. The scale adaptive descriptor is mapped onto clusters in linear spaces. A new subspace estimation algorithm based on the Generalized Principal Component Analysis (GPCA) is proposed to estimate multiple linear subspaces. The visual attention of each region is calculated using a new region attention measure that considers feature contrast and spatial geometric properties. Compared with existing visual attention detection methods, the proposed method directly measures global visual attention at the region level as opposed to pixel level.

We present an event-driven video adaptation system in this paper. Events are detected by audio/video analysis and annotated by the description schemes (DSs) provided by MPEG-7 multimedia description schemes (MDSs). And then, adaptation take account of users' preference of events and network characteristic to adapt video by event selection and frame dropping as following three steps: 1) the event information is parsed from MPEG-7 annotation XML file together with bitstream to generate generic bitstream syntax description (gBSD), 2) users' preference, network characteristic and adaptation QoS (AQoS) are considered for making adaptation decision, 3) adaptation engine automatically parses adaptation decisions and gBSD to achieve adaptation. Different from most existing adaptation work, the system adapts video by interesting events according to users' preference. To achieve a generic adaptation solution, the system is developed following MPEG-7 and MPEG-21 standards. gBSD based adaptation avoids complex video computation. 30 students from various departments test the system with satisfaction. Although, the system is tested on basketball video adaptation so far, it is easy to extend to other video domains

In this paper, we present an event-on-demand (EoD)video adaptation system. The proposed system supports users in deciding their events of interest and considers network conditions to adapt video source by event selection and frame dropping.Firstly, events are detected by audio/video analysis and annotated by the description schemes (DSs)provided by MPEG-7 Multimedia Description Schemes (MDSs). And then, to achieve a generic adaptation solution, the adaptation is developed following MPEG-21 Digital Item Adaptation (DIA)framework. We look at early release of the MPEG-21 Reference Software on XML generation and develop our own system for EoD video adaptation in three steps:1) the event information is parsed from MPEG-7 annotation XML file together with bitstream to generate generic Bitstream Syntax Description (gBSD). 2) Users' preference, Network Characteristic and Adaptation QoS (AQoS) are considered for making adaptation decision. 3) adaptation engine automatically parses adaptation decisions and gBSD to achieve adaptation.Unlike most existing adaptation work, the system adapts video of events with interest according to users' preference. Implementation following MPEG-7 and MPEG-21 standards provides a generic video adaptation solution. gBSD based adaptation avoids complex video computation. 30 students from various departments were invited to test the system and their responses has been positive.

Visual attention is obtained through determination of contrasts of low level features or attention cues like intensity, color etc. We propose a new texture attention cue that is shown to be more effective for images where the salient object regions and background have similar visual characteristics. Current visual attention models do not consider local contextual information to highlight attention regions. We also propose a feature combination strategy by suppressing saliency based on context information that is effective in determining the true attention region. We compare our approach with other visual attention models using a novel average discrimination ratio measure.

Detecting visually attentive regions of an image is a challenging but useful issue in many multimedia applications. In this paper, we describe a method to extract visual attentive regions in images using subspace estimation and analysis techniques. The image is represented in a 2D space using polar transformation of its features so that each region in the image lies in a 1D linear subspace. A new subspace estimation algorithm based on Generalized Principal Component Analysis (GPCA) is proposed. The robustness of subspace estimation is improved by using weighted least square approximation where weights are calculated from the distribution of K nearest neighbors to reduce the sensitivity of outliers. Then a new region attention measure is defined to calculate the visual attention of each region by considering both feature contrast and geometric properties of the regions. The method has been shown to be effective through experiments to be able to overcome the scale dependency of other methods. Compared with existing visual attention detection methods, it directly measures the global visual contrast at the region level as opposed to pixel level contrast and can correctly extract the attentive region.

The upcoming MPEG-21 standard proposes a general framework for augmented use of multimedia services in different network environments, for various users with various terminal devices. In the context of image adaptation, terminals with different screen size limitation require the multimedia adaptation engine to adapt image resources intelligently. Saliency map based visual attention analysis provides some intelligence for finding the attention area within the image. In this paper, we improved the standard MPEG-21 metadata driven adaptation engine by using enhanced saliency map based visual attention model which provides a mean to intelligently adapt JPEG2000 image resolution for different terminal devices with varying screen size according to human visual attention.