Performance of deep metric learning depends heavily on the capability of mining hard negative examples during training. However, many metric learning algorithms often require intractable computational cost due to frequent feature computations and nearest neighbor searches in a large-scale dataset. As a result, existing approaches often suffer from trade-off between training speed and prediction accuracy. To alleviate this limitation, we propose a stochastic hard negative mining method. Our key idea is to adopt class signatures that keep track of feature embedding online with minor additional cost during training, and identify hard negative example candidates using the signatures. Given an anchor instance, our algorithm first selects a few hard negative classes based on the class-to-sample distances and then performs a refined search in an instance-level only from the selected classes. As most of the classes are discarded at the first step, it is much more efficient than exhaustive search while effectively mining a large number of hard examples. Our experiment shows that the proposed technique improves image retrieval accuracy substantially; it achieves the state-of-the-art performance on the several standard benchmark datasets.

Graph cuts-based algorithms have achieved great success in energy minimization for many computer vision applications. These algorithms provide approximated solutions for multi-label energy functions via move-making approach. This approach fuses the current solution with a proposal to generate a lower-energy solution. Thus, generating the appropriate proposals is necessary for the success of the move-making approach. However, not much research efforts has been done on the generation of “good” proposals, especially for non-metric energy functions. In this paper, we propose an application-independent and energy-based approach to generate “good” proposals. With these proposals, we present a graph cuts-based move-making algorithm called GA-fusion (fusion with graph approximation-based proposals). Extensive experiments support that our proposal generation is effective across different classes of energy functions. The proposed algorithm outperforms others both on real and synthetic problems.

Markov chain Monte Carlo (MCMC) is an elegant tool, widely used in variety of areas. In computer vision, it has been used for the inference on the Markov random field model (MRF). However, MCMC less concerned than other deterministic approaches although it converges to global optimal solution in theory. The major obstacle is its slow convergence. To come up with faster sampling method, we investigate two ideas: breaking detailed balance and updating multiple nodes at a time. Although detailed balance is considered to be essential element of MCMC, it actually is not the necessary condition for the convergence. In addition, exploiting the structure of MRF, we introduce a new kernel which updates multiple nodes in a scanline rather than a single node. Those two ideas are integrated in a novel way to develop an efficient method called scanline sampler without detailed balance. In experimental section, we apply our method to the OpenGM2 benchmark of MRF optimization and show the proposed method achieves faster convergence than the conventional approaches.

Many vision applications have been formulated as Markov Random Field (MRF) problems. Although many of them are discrete labeling problems, continuous formulation often achieves great improvement on the qualities of the solutions in some applications such as stereo matching and optical flow. In continuous formulation, however, it is much more difficult to optimize the target functions. In this paper, we propose a new method called fusion move driven Markov Chain Monte Carlo method (MCMC-F) that combines the Markov Chain Monte Carlo method and the fusion move to solve continuous MRF problems effectively. This algorithm exploits powerful fusion move while it fully explore the whole solution space. We evaluate it using the stereo matching problem. We empirically demonstrate that the proposed algorithm is more stable and always finds lower energy states than the state-of-the art optimization techniques.

Many vision problems have been formulated as energy minimization problems and there have been significant advances in energy minimization algorithms. The most widely-used energy minimization algorithms include graph cuts, belief propagation and tree-reweighted message passing. Although they have obtained good results, they are still unsatisfactory when it comes to more difficult MRF problems such as non-submodular energy functions, highly connected MRFs, and high-order clique potentials. There have also been other approaches, known as stochastic sampling-based algorithms, which include simulated annealing, Markov chain Monte Carlo and population based Markov chain Monte Carlo. They are applicable to any general energy models but they are usually slower than deterministic methods. In this paper, we propose new algorithms which elegantly combine stochastic and deterministic methods. Sampling-based methods are boosted by deterministic methods so that they can rapidly move to lower energy states and easily jump over energy barriers. In different point of view, the sampling-based method prevents deterministic methods from getting stuck at local minima. Consequently, a combination of both approaches substantially increases the quality of the solutions. We present a thorough analysis of the proposed methods in synthetic MRF problems by controlling the hardness of the problems. We also demonstrate experimental results for the photomontage problem which is the most difficult one among the standard MRF benchmark problems.

Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method for quickly finding sufficiently good solutions. To this end, we take evolutionary approaches based on a Genetic Algorithm. In this paper, we extend the evolutionary algorithm that we previously proposed in three perspectives. First, whereas the previous algorithm can be applied to only acyclic networks, we devise a modified evaluation method that works also with networks with cycles. Second, we introduce a new set of GA components that in our experiments outperforms the one used in the previous algorithm. Third, we present a new framework of the evolutionary approach, where fitness evaluation and population management are done in a decentralized manner with a limited amount of coordination. The new framework enables a network coding protocol where the resources used for coding are optimized in the setup phase as the proposed evolutionary algorithm being loaded and run at each node of the network. We demonstrate the effectiveness of our algorithms by carrying out simulations on a number of different sets of network topologies. I.