Automatic browsing path generation to present image areas with high attention value as a function of space and time

• US 7,471,827 B2
• Filed: 10/16/2003
• Issued: 12/30/2008
• Est. Priority Date: 10/16/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xie, Xing, Ma, Wei-Ying, Zhang, Hong-Jiang, Hao, Liu
• Primary Examiner(s): SETH, MANAV
• Assistant Examiner(s): Daley, Clifton G
• Application Number:
  US10/688,471
• Publication Number:
  US 20050084136A1
• Time in Patent Office: 1,902 Days
• Field of Search: 382/107, 382115-161, 382190-208, 345/419, 345/629
• US Class Current: 382/173
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents

Abstract

Systems and methods for automatic generation of a browsing path across image content to present areas with high attention value are described. In particular, an image is modeled via multiple visual attentions to create a respective set of attention objects for each modeled attention. The attention objects and their respective attributes are analyzed to generate a browsing path to select ones of the attention objects. The browsing path is generated to optimize the rate of information gain from the attention objects as a function of information unit cost in terms of time constraints associated with multiple image browsing modes.

Claims

1. A method comprising:

modeling an image with respect to multiple visual attentions to generate a respective set of attention objects (AOs) for each attention of the visual attentions;

analyzing the attention objects and corresponding attributes to optimize a rate of information gain as a function of information unit cost in terms of time associated with multiple image browsing modes; and

responsive to analyzing the attention objects, generating a browsing path to select ones of the attention objects, wherein generating the browsing path further comprises creating the browsing path in view of a perusing image-browsing mode as follows;

splitting one or more large AOs of the AOs into smaller AOs;

combining AOs in close proximity to one another into one or more attention groups;

arranging the attention groups in decreasing order based on respective attention values;

for each attention group of the attention groups;

selecting the attention group as a starting point;

for each path of all possible paths from the starting point;

calculating a total browsing time and an information fidelity; and

if the information fidelity is smaller than a browsing time threshold, discarding the path;

selecting a non-discarded path having a smallest browsing time as the browsing path, the browsing path connecting each of the attention groups.

2. A method as recited in claim 1, wherein the multiple visual attentions are based on saliency, face, and text attention models.

3. A method as recited in claim 1, wherein the image browsing modes comprise a perusing mode and a skimming mode.

4. A method as recited in claim 1, wherein the select ones have relatively greater information fidelity as compared to different ones of the attention objects.

5. A method as recited in claim 1, wherein the corresponding attributes for each attention object of the attention objects comprise a minimal perceptible time (MPT) for display of subject matter associated with the attention object, and wherein the method further comprises calculating the MPT as a function of:

a number of words in the subject matter;

whether the subject matter is for presentation to a viewer in a perusing image browsing mode or a skimming image browsing mode;

user preferences; and

/or,

display context.

6. A method as recited in claim 1, wherein modeling further comprises:

creating a visual attention model for the image, the visual attention model being generated according to

{AO_i}={(ROI_i, AV_i, MPS_i, MPT_i)}, 1≦

i≦

N; and

,

wherein AO_i, represents an i^th AO within the image, ROI_i represents a region-of-interest of AO_i, AV_i represents an attention value of AO_i, MPS_i represents a minimal perceptible size of AO_i, MPT_i represents a minimal perceptual time for display of subject matter associated with the AO_i, and, N represents a total number of AOs modeled from the image.

7. A method as recited in claim 1, wherein the browsing path comprises a number of successive path segments described as follows:

P={P_i}={(SP_i,EP_i,SR_i,ER_i,T_i)}, 1≦

i≦

N, and

wherein P_i represents an i^th path segment, SP_i represents a starting point of P_i, EP_i corresponds to an ending point of P_i, SR_i is a starting resolution of P_i, ER_i is an ending resolution of P_i, and T_i is a time cost for scrolling from SP_i to EP_i.

8. A method as recited in claim 1, wherein generating the browsing path further comprises creating the browsing path as a function of a fixation state or a shifting state.

9. A method as recited in claim 1, wherein generating the browsing path further comprises calculating an information fidelity for each AO, the information fidelity being a function of an attention value (AV) and the minimal perceptible time (MPT) for display of subject matter associated with the AO.

10. A method as recited in claim 1:

wherein each AO is a respective information block and wherein the image (I) is a modeled as a set of M×

N evenly distributed information blocks I_ij as follows;

I={I_ij}={(AV_ij,r_ij)}, 1≦

i≦

M,1≦

j≦

N,r_ij ε

(0,1),

wherein (i, j) corresponds to a location at which the information block I_ij is modeled according to a visual attention, AV_ij is a visual attention value of I_ij, r_ij is the spatial scale of I_ij, representing the minimal spatial resolution to keep I_ij perceptible; and

,

wherein generating the browsing path further comprises calculating an information fidelity (f_RSVP) for each AO, the information fidelity being calculated as follows for respective ones of the information blocks I_ij;

$f_{\mathrm{RSVP}}<br><br>\left(I,T\right)={\int <br><br>}_0^T<br><br>\underset{I_{\mathrm{ij}}\in <br><br>I_{\mathrm{RSVP}}<br><br>\left(t\right)}{\sum <br><br>}<br><br>{\mathrm{AV}}_{\mathrm{ij}}<br><br>u<br><br>\left(r<br><br>\left(t\right)-r_{\mathrm{ij}}\right)<br><br>d<br><br>t,I_{\mathrm{RSVP}}<br><br>\left(t\right)\subseteq <br><br>I;<br><br>\mathrm{and}$

wherein I_RSVP(t) is a subset of the information blocks and varies with time (T) and

$r<br><br>\left(t\right)=\underset{I_{\mathrm{ij}}\in <br><br>I_{\mathrm{RSVP}}<br><br>\left(t\right)}{\max }<br><br>r_{\mathrm{ij}}\le <br><br>\min <br><br>\left(\frac{{\mathrm{Width}}_{\mathrm{Screen}}}{{\mathrm{Width}}_{I_{\mathrm{RSVP}}<br><br>\left(t\right)}},\frac{{\mathrm{Height}}_{\mathrm{Screen}}}{{\mathrm{Height}}_{I_{\mathrm{RSVP}}<br><br>\left(t\right)}}\right),$

which varies with space.

11. A method as recited in claim 1, further comprising:

detecting user intervention during automatic playback of the browsing path;

responsive to detecting the user intervention;

recording all AOs S_r of the AOs that have not been browsed;

identifying all AOs S_m of the AOs browsed during the user intervention;

regenerating the browsing path based on S_r-S_m; and

responsive to regenerating the browsing path and determining that there is at least a lull in user intervention, automatically navigating the browsing path.

12. A computer-readable medium comprising computer-program instructions executable by a processor for:

modeling an image with respect to multiple visual attentions to generate a respective set of attention objects (AOs) for each attention of the visual attentions, the AOs representing respective regions of the image;

analyzing the attention objects and corresponding attributes to in view of a model for human browsing behavior, the model comprising fixation and shifting states, in the fixation state an interesting region of the regions is exploited for information, in the shifting state one region of the regions is replaced with another region of the regions as a function of image view manipulation operations comprising scrolling or tabbing operations, and wherein the corresponding attributes for each attention object of the AOs comprise a minimal perceptible time (MPT) for display of subject matter associated with the attention object; and

responsive to the analyzing, optimizing a rate of information gain in terms of space as a function of information unit cost in terms of time associated with the model for human browsing behavior to generate a browsing path to select ones of the attention objects;

wherein the computer-program instructions for optimizing further comprise instructions for determining the rate of information gain R as follows;

$R=\frac{G}{T_B+T_w},$

wherein, G is a total net amount of objectively valuable information gained as determined via information fidelity determinations, T_B is a total amount of time spent on shifting between subsequent fixation areas (AOs), T_W represents an exploiting cost, which is a total duration of the MPTs used while in a fixation state.

13. A computer-readable medium as recited in claim 12, wherein the multiple visual attentions are based on saliency, face, and text attention models.

14. A computer-readable medium as recited in claim 12, wherein the select ones have relatively greater information fidelity as compared to different ones of the attention objects.

15. A computer-readable medium as recited in claim 12, wherein the computer-program instructions further comprise instructions for generating the browsing path as a number of successive path segments as follows:

P={P_i}={(SP_i,EP_i,SR_i,ER_i,T_i)}, 1≦

i≦

N, and

wherein P_i represents an i^th path segment, SP_i represents a starting point of P_i, EP_i corresponds to an ending point of P_i, SR_i is a starting resolution of P_i, ER_i is an ending resolution of P_i, and T_i is a time cost for scrolling from SP_i to EP_i.

16. A computer-readable medium as recited in claim 12, wherein the computer-program for generating the browsing path further comprise instructions for calculating an information fidelity for each AO, the information fidelity being a function of an attention value (AV) and the minimal perceptible time (MPT) for display of subject matter associated with the AO.

17. A computer-readable medium as recited in claim 12, wherein each AO is a respective information block, and wherein the computer-program instructions further comprise instructions for:

representing the image (I) as a set of M×

N evenly distributed information blocks I_ij as follows;

I={I_ij}={(AV_ij,r_ij)}, 1≦

i≦

M,1≦

j≦

N,r_ij ε

(0,1),

wherein (i, j) corresponds to a location at which the information block I_ij is modeled according to a visual attention, AV_ij is a visual attention value of I_ij, r_ij is the spatial scale of I_ij, representing the minimal spatial resolution to keep I_ij perceptible; and

,

generating the browsing path further by calculating an information fidelity (f_RSVP) for each AO as follows for respective ones of the information blocks I_ij;

$f_{\mathrm{RSVP}}<br><br>\left(I,T\right)={\int <br><br>}_0^T<br><br>\underset{I_{\mathrm{ij}}\in <br><br>I_{\mathrm{RSVP}}<br><br>\left(t\right)}{\sum <br><br>}<br><br>{\mathrm{AV}}_{\mathrm{ij}}<br><br>u<br><br>\left(r<br><br>\left(t\right)-r_{\mathrm{ij}}\right)<br><br>d<br><br>t,I_{\mathrm{RSVP}}<br><br>\left(t\right)\subseteq <br><br>I;<br><br>\mathrm{and}$

wherein I_RSVP(t) is a subset of the information blocks and varies with time and

$r<br><br>\left(t\right)=\underset{I_{\mathrm{ij}}\in <br><br>I_{\mathrm{RSVP}}<br><br>\left(t\right)}{\max }<br><br>r_{\mathrm{ij}}\le <br><br>\min <br><br>\left(\frac{{\mathrm{Width}}_{\mathrm{Screen}}}{{\mathrm{Width}}_{I_{\mathrm{RSVP}}<br><br>\left(t\right)}},\frac{{\mathrm{Height}}_{\mathrm{Screen}}}{{\mathrm{Height}}_{I_{\mathrm{RSVP}}<br><br>\left(t\right)}}\right),$

which varies with space.

18. A computer-readable medium as recited in claim 12, wherein the computer-program instructions further comprise instructions for optimizing the rate of information gain R either by maximizing information fidelity or by minimizing time cost.

19. A computer-readable medium as recited in claim 12, wherein the computer-program instructions further comprise instructions for optimizing the rate of information gain R in the shifting mode as follows:

$\begin{array}{ccc}\mathrm{Given}& T_P\le <br><br>{\mathrm{\lambda <br><br>}}_T,& \underset{P}{\mathrm{Max}}<br><br>\left\{f_p<br><br>\left(I,T_P\right)\right\},\end{array}$

wherein, T_p represents a total amount of time spent for fixation and shifting in the browsing path P, λ

_T is a threshold of maximal time cost, and I represents the image.

20. A computer-readable medium as recited in claim 12, wherein the computer-program instructions further comprise instructions for optimizing the rate of information gain R in the shifting mode as follows:

$\begin{array}{ccc}\mathrm{Given}& f_P<br><br>\left(I,T_P\right)\ge <br><br>{\mathrm{\lambda <br><br>}}_{\mathrm{AV}},& \underset{P}{\mathrm{Min}}<br><br>\left\{T_P\right\},\end{array}$

wherein, T_p represents a total amount of time spent for fixation and shifting in the browsing path P, λ

_AV represents a minimal attention value or information percentage for attainment.

21. A computer-readable medium as recited in claim 12, further comprising:

detecting user intervention during automatic playback of the browsing path;

responsive to detecting the user intervention;

recording all AOs S_r of the AOs that have not been browsed;

identifying all AOs S_m of the AOs browsed during the user intervention;

regenerating the browsing path based on S_r-S_m; and

responsive to regenerating the browsing path and determining that there is at least a lull in user intervention, automatically navigating the browsing path.

22. A computing device comprising a processor coupled to a memory, the memory comprising computer-program instructions executable by the processor for:

modeling an image with respect to multiple visual attentions to generate a respective set of attention objects (AOs) for each attention of the visual attentions, the AOs representing respective regions of the image;

analyzing the attention objects and corresponding attributes to in view of a model for human browsing behavior, the model comprising fixation and shifting states, in the fixation state an interesting region of the regions is exploited for information, in the shifting state one region of the regions is replaced with another region of the regions as a function of image view manipulation operations comprising scrolling or tabbing operations, and wherein the corresponding attributes for each attention object of the AOs comprise a minimal perceptible time (MPT) for display of subject matter associated with the attention object; and

responsive to the analyzing, optimizing a rate of information gain in terms of space as a function of information unit cost in terms of time associated with the model for human browsing behavior to generate a browsing path to select ones of the attention objects;

wherein the computer-program instructions for optimizing further comprise instructions for determining the rate of information gain R as follows;

$R=\frac{G}{T_B+T_w},$

wherein, G is a total net amount of objectively valuable information gained as determined via information fidelity determinations, T_B is a total amount of time spent on shifting between subsequent fixation areas (AOs), T_W represents an exploiting cost, which is a total duration of the MPTs used while in a fixation state.

23. A computing device as recited in claim 22, wherein the multiple visual attentions are based on saliency, face, and text attention models.

24. A computing device as recited in claim 22, wherein the select ones have relatively greater information fidelity as compared to different ones of the attention objects.

25. A computing device as recited in claim 22, wherein the computer-program instructions further comprise instructions for generating the browsing path as a number of successive path segments as follows:

P={P_i}={(SP_i,EP_i,SR_i,ER_i,T_i)}, 1≦

i≦

N, and

wherein P_i represents an i^th path segment, SP_i represents a starting point of P_i, EP corresponds to an ending point of P_i, SR_i is a starting resolution of P_i, ER_i is an ending resolution of P_i, and T_i is a time cost for scrolling from SP_i to EP_i.

26. A computing device as recited in claim 22, wherein the computer-program for generating the browsing path further comprise instructions for calculating an information fidelity for each AO, the information fidelity being a function of an attention value (AV) and the minimal perceptible time (MPT) for display of subject matter associated with the AO.

27. A computing device as recited in claim 22, wherein each AO is a respective information block, and wherein the computer-program instructions further comprise instructions for:

representing the image (I) as a set of M×

N evenly distributed information blocks I_ij as follows;

I={I_ij}={(AV_ij,r_ij)}, 1≦

i≦

M,1≦

j≦

N,r_ij ε

(0,1),

wherein (i, j) corresponds to a location at which the information block I_ij is modeled according to a visual attention, AV_ij is a visual attention value of I_ij, r_ij is the spatial scale of I_ij, representing the minimal spatial resolution to keep I_ij perceptible; and

,

generating the browsing path further by calculating an information fidelity (f_RSVP) for each AO as follows for respective ones of the information blocks I_ij;

$f_{\mathrm{RSVP}}<br><br>\left(I,T\right)={\int <br><br>}_0^T<br><br>\underset{I_{\mathrm{ij}}\in <br><br>I_{\mathrm{RSVP}}<br><br>\left(t\right)}{\sum <br><br>}<br><br>{\mathrm{AV}}_{\mathrm{ij}}<br><br>u<br><br>\left(r<br><br>\left(t\right)-r_{\mathrm{ij}}\right)<br><br>d<br><br>t,I_{\mathrm{RSVP}}<br><br>\left(t\right)\subseteq <br><br>I;<br><br>\mathrm{and}$

wherein I_RSVP(t) is a subset of the information blocks and varies with time and

$r<br><br>\left(t\right)=\underset{I_{\mathrm{ij}}\in <br><br>I_{\mathrm{RSVP}}<br><br>\left(t\right)}{\max }<br><br>r_{\mathrm{ij}}\le <br><br>\min <br><br>\left(\frac{{\mathrm{Width}}_{\mathrm{Screen}}}{{\mathrm{Width}}_{I_{\mathrm{RSVP}}<br><br>\left(t\right)}},\frac{{\mathrm{Height}}_{\mathrm{Screen}}}{{\mathrm{Height}}_{I_{\mathrm{RSVP}}<br><br>\left(t\right)}}\right),$

which varies with space.

28. A computing device as recited in claim 22, wherein the computer-program instructions further comprise instructions for optimizing the rate of information gain R either by maximizing information fidelity or by minimizing time cost.

29. A computing device as recited in claim 22, wherein the computer-program instructions further comprise instructions for optimizing the rate of information gain R in the shifting mode as follows:

$\begin{array}{cc}\mathrm{Given}<br><br><br><br>T_P\le <br><br>{\mathrm{\lambda <br><br>}}_T,& \underset{P}{\mathrm{Max}}<br><br>\left\{f_p<br><br>\left(I,T_P\right)\right\},\end{array}$

wherein, T_p represents a total amount of time spent for fixation and shifting in the browsing path P, λ

_T is a threshold of maximal time cost, and I represents the image.

30. A computing device as recited in claim 22, wherein the computer-program instructions further comprise instructions for optimizing the rate of information gain R in the shifting mode as follows:

$\begin{array}{cc}\mathrm{Given}<br><br><br><br>f_P<br><br>\left(I,T_P\right)\ge <br><br>{\mathrm{\lambda <br><br>}}_{\mathrm{AV}},& \underset{P}{\mathrm{Min}}<br><br>\left\{T_P\right\},\end{array}$

wherein, T_p represents a total amount of time spent for fixation and shifting in the browsing path P, λ

_AV represents a minimal attention value or information percentage for attainment.

31. A computing device as recited in claim 22, further comprising:

detecting user intervention during automatic playback of the browsing path;

responsive to detecting the user intervention;

recording all AOs S_r of the AOs that have not been browsed;

identifying all AOs S_m of the AOs browsed during the user intervention;

regenerating the browsing path based on S_r-S_m; and

responsive to regenerating the browsing path and determining that there is at least a lull in user intervention, automatically navigating the browsing path.

32. A method comprising:

modeling an image with respect to multiple visual attentions to generate a respective set of attention objects (AOs) for each attention of the visual attentions;

analyzing the attention objects and corresponding attributes to optimize a rate of information gain as a function of information unit cost in terms of time associated with multiple image browsing modes; and

responsive to analyzing the attention objects, generating a browsing path to select ones of the attention objects, the browsing path being a trade off of time for space or space for time;

wherein generating the browsing path further comprises creating the browsing path in view of a skimming image-browsing mode as follows;

splitting one or more large AOs of the AOs into smaller AOs;

combining AOs in close proximity to one another into one or more attention groups;

arranging the attention groups in decreasing order based on respective attention values;

for each attention group of the attention groups;

selecting the attention group as a starting point;

calculating a total browsing time and information fidelity for each path of all possible paths from the starting point; and

if the total browsing time is greater than a browsing time threshold, discarding the path;

selecting a non-discarded path having a largest information fidelity as the browsing path, the browsing path connecting each of the attention groups.