|
  
Next:Summary Up: Model-Based Mining of Previous:Combining results from searching
Model Revision
This section examines one model revision algorithm [5] to illustrate the process of revising the feature
space using feedback from the user and the ground truth results. In this algorithm, a linear transform of the features is modified by the user's feedback. A gradient (steepest descent) method is employed to
ensure rapid convergence, which makes the approach suitable for an interactive query environment. We assume that an image database consists of a set of N feature vectors. Each feature vector has n
dimensions. The feature vectors potentially represent a combination of color, texture and shape information. The user starts a query by selecting a particular query image, region, or object. The corresponding
feature vector is extracted from the example, and the K best matches are retrieved using a Euclidean metric. The K
results whose feature vectors are closest to the target feature vectors are then returned to the user for visual inspection or further processing. The user specifies a refinement by selecting  of the K matches that are most similar to the desired
match and reissuing the query. Based upon this feedback, the linear or nonlinear transform matrix is modified to better approximate the user's evaluation of similarity. A second set of matches is found and
returned to the user. The user selects the  best matches and again reissues the query. This process is
repeated until either the result set converges, or the user stops the process. If the set of the feature vectors selected by the user up to step (i-1) is denoted as  , then 
where  is the set of feature vectors selected during step
i. The vectors that are NOT selected up to step i-1 is  , then 
where  is the set of feature vectors rejected during step i. Algorithm The algorithm [5] for iterative refinement using nonlinear multidimensional scaling is as
follows:
- Performing similarity search on a feature vector, v, retrieving the K most similar results in the feature space. Set i=1.
- Initialize
 and  to those vectors which are considered to be similar. Also initialize  and 
to those vectors that are not considered to be similar. If the number of vectors is less than a prescribed threshold, set  , where  is a fixed increment. Return to step 1.
- Perform the rescaling, described in the previous subsection, based on two classes of vectors:
 and  where include all the vectors that are considered similar, while include all the vectors that are considered to be no similar (or irrelevant). Consequently, the class label for is 1, while the class label for is 2.
- Perform similarity search in the scaled feature space. The results are assigned either to set containing similar (or relevant) results or to set containing dissimilar (or irrelevant) results.
- Update and as follows
  - if the difference between and is less than a prescribed threshold, a equilibrium has been reached and exit.
- set i=i+1, and return to step 3.
Next:Summary Up: Model-Based Mining of Previous:Combining results from searching |
