Copyright © 2014 by Intelligent Systems Laboratory, Computer Science Department, Technion - Israel Institute of Technology, Haifa 3200003, Israel. All rights reserved


TheGrue.org

An Information Based Measure Of Grouping Quality

An Information Based Measure Of Grouping Quality

By: E. A. Engbers, M. Lindenbaum and A. W. M. Smeulders

Grouping is an essential process of computer vision. However, measurement of grouping result is not straightforward and is often heuristic.  We propose here a measure of grouping quality which is based on the following observation: the grouping result provides some information about the true, unknown, grouping and reduces its uncertainty. 

 

  

  

This uncertainty is evaluated by the number of queries required to specify the true grouping. The number of queries is evaluated by an automatic procedure which generates queries about a given hypothesized grouping, and answers them using the ground truth. The queries are homogeneity queries which specify some region in the image and ask whether it all belongs to the same group/object. The process terminates once the queries suffice to specify the ground truth. The number of queries is returned as a measure of hypothesis non-informativeness.

Following a probabilistic characterization and considering the given grouping result to be a random variable, gives a precise meaning to the uncertainty of the true grouping, using common information theory terms like surprise and entropy.

The uncertainty based measure does not rely on arbitrary preferences, and, as our experiments show, it is also consistent with human judgment more than the common set difference method. The utility of the proposed method is demonstrated by its usage as a benefit function in the optimization of a grouping algorithm.

For more details see the paper "An information based method for grouping quality".

 

An Information Based Measure Of Grouping QualityAn Information Based Measure Of Grouping QualityAn Information Based Measure Of Grouping QualityAn Information Based Measure Of Grouping Quality

 The query generating algorithm is composed of three stages.

In the preprocessing stage the data is represented in a way that reduces the number of queries. This stage does not generate queries and does not require the oracle (and the ground truth).

Then come the split stage where every hypothesized group is recursively subdivided until every part is homogeneous.

Finally, queries related to merges of parts are asked, to ensure that the hypothesis is not over-segmented.

The algorithm is described in detail in the paper "An information based method for grouping quality". Here we just bring an illustration of its operation.

The preprocessing stage deals only with the hypothesis image (it does not need queries from the oracle).

It builds a tree so that every leaf is a homogeneous rectangle (that is, all pixels associated with the leaf belong to the same group in the hypothesized grouping). The particular partition aims to get parts which are as large as possible, and prefers that two children of the same node will be associated with adjacent region, but is otherwise heuristic. We found that the particular construction does not influence the number of queries substantially.

 

 Example For The Hypothesis Image

An Information Based Measure Of Grouping Quality

 

 

  

The tree is built by examining regions and splitting them if they are not homogeneous. The white rectangle marks the region that is tested. If it is homogeneous (with respect to the hypothesis - marked by green frame) the algorithm moves to the next region. If it is not (marked by a cross in the rectangle), then the region is subdivided:

An Information Based Measure Of Grouping Quality