4. Thumbnail Optimization

Once the time and the information attributes are computed for the visual, audible, and audiovisual elements, the job of the optimizer is to produce the best thumbnail by selecting a combination of elements that can be displayed in a given time. The best thumbnail is one that maximizes the total information content of the thumbnail and can be displayed in the given time. The total information content of the thumbnail is the sum of the information content of the selected elements. Let the information content of an element e be denoted by I(e), and the time required to display by t(e). An element e belongs to either the set of visual elements E_v, or the set of audible elements E_a, or the set of audiovisual elements E_av. While displaying a visual element, an audible element can be played, and therefore overlap in time.

In this paper we give a strict priority to the visual elements in creating thumbnail. This means that we create a partial thumbnail by selecting elements from the set of visual elements and the set of audiovisual elements satisfying the display time constraint, such that the total information content in the partial thumbnail is maximized. The resulting optimization problem is maximize

subject to		(1)
	x(e) ∈ {0,1} for all e ∈ Ev ∪ Eav

where the x(e) are the optimization variables, and T is the given display time. For an element e, x(e)=1 means it is selected to be in the thumbnail, and, x(e)=0 means it is not selected. Let x*(e) be the solution to the optimization problem. After the partial thumbnail is created the time for which the audio channel is free T is calculated by

The audible elements are chosen by solving another optimization problem similar to (1),

maximize
subject to		(2)
	x(e) ∈ {0,1} for all e ∈ Ea

Thus by solving this two stage optimization problem we obtain the Multimedia Thumbnail.

The above optimization problems can be seen as a ′0-1 knapsack' problem, which is a hard combinatorial optimization problem [7]. If we relax the constraints x(e)∈{0,1} to 0 ≤ x(e) ≤ 1, then the optimization problem becomes much easier to solve.

The solution to the optimization problem (1) -after approximation- is

• sort the elements e ∈ E_v ∪ E_av according to the ratio I(e)/t(e) in descending order, i.e.,
  
  where m is the number of elements in E_v ∪ E_av
• find the integer k such that
  
• select element e_i, i.e., x(e_i) = 1, if i ≤ k, otherwise not (x(e_i) = 0).

For practical purposes this approximation works well to the problem in (1), as we expect the individual elements to have much shorter display time than the total display time.

By dividing visual, audible, and audiovisual document elements into three separate sets, instead of just two for visual and audible, we can better model the optimization of synchronized visual and audible data. Also note that even though the optimization problem takes into account only time constraint, the display and the application constraints indirectly affect the solution, as these constraints affect the information and time attributes of the elements.