ABSTRACT
Block matching is a widely used method for stereo vision, visual tracking, and video compression. Many fast algorithms for block matching have been proposed in the past, but most of them do not guarantee that the match found is the globally optimal match in a search range. This paper presents a new fast algorithm based on the winner-update strategy which utilizes an ascending lower bound list of the matching error to determine the temporary winner. Two lower bound lists derived by using partial distance and by using Minkowski's inequality are described. The basic idea of the winner-update strategy is to avoid, at each search position, the costly computation of the matching error when there exists a lower bound larger than the global minimum matching error. The proposed algorithm can significantly speed up the computation of the block matching because: 1) computational cost of the lower bound we use is less than that of the matching error itself; 2) an element in the ascending lower bound list will be calculated only when its preceding element has already been smaller than the minimum matching error computed so far; 3) for many search positions, only the first several lower bounds in the list need to be calculated. Our experiments have shown that, when applying to motion vector estimation for several widely-used test videos, 92% to 98% of operations can be saved while still guaranteeing the global optimality. Moreover, the proposed algorithm can be easily modified either to meet the limited time requirement or to provide an ordered list of best candidate matches. Our source codes of the proposed algorithm are available at http://smart.iis.sinica.edu.tw/html/winup.html.
ABSTRACT
In this work, we propose a model of a content-based image retrieval system by using the new idea of combining a color segmentation with relationship trees and a corresponding tree-matching method. We retain the hierarchical relationship of the regions in an image during segmentation. Using the information of the relationships and features of the regions, we can represent the desired objects in images more accurately. In retrieval, we compare not only region features but also region relationships.
ABSTRACT
The block-matching method plays an important role in displacement field estimation due to its simplicity, achievement of long-range motion, and robustness to noise. In this paper, a single-layer feedback neural network model is proposed that enhances block matching, estimates the displacement field, and simultaneously performs image segmentation from consecutive images. In this paper, image segmentation is defined as partitioning each image into a set of moving objects and the background. For any two consecutive images, a neural network is created that learns the connection relationship of the pixels in an object from the displacement field and stores the relationship in the network. A modified block matching is used to compute a more accurate displacement field by utilizing the segmentation information embedded in the neural network. The displacement vector at the edge of an object or occluding boundary is hard to estimate, but the proposed model performs satisfactorily because it learns and uses the connection information. Furthermore, a flood-fill algorithm is used to compute the dense displacement field more efficiently and correctly than the exhaustive search does. The most important aspect of this paper is that image segmentation is performed simultaneously with the displacement-field estimation by the neural-network model. The novel idea of the work is to embed the segmentation information (connection relations) in the neural network and to perform the displacement-field estimation and image segmentation simultaneously. Two methods for retrieving segmentation information from the neural network with any two consecutive images are also presented.
