Hierarchical image model adaptation

• US 7,596,276 B2
• Filed: 07/30/2002
• Issued: 09/29/2009
• Est. Priority Date: 08/01/2001
• Status: Active Grant

• Current Assignee: Viisage Technology AG (Advent International Corporation)
• Original Assignee: Viisage Technology AG (Advent International Corporation)
• Inventors: Rinne, Michael, Werner, Martin, Gehlen, Stefan
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US10/485,452
• Publication Number:
  US 20050013490A1
• Time in Patent Office: 2,618 Days
• Field of Search: 382224-228, 707/1, 707 3- 6, 707/104.1
• US Class Current: 382/226
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method of processing digitized picture data includes providing an hierarchical structure graph which is applied to the picture data in that, starting with the lowermost level, at least one node is processed. The provided hierarchical structure graph includes nodes, a specified number of levels, with at least one node located in each level, and edges connecting pairs of predetermined nodes of different levels and defining, for each pair of nodes, a lower father node and an upper son node. Processing of a node includes matching of its at least one picture matching model to the picture data by variation of the model parameters, determination of a matching quantity for each parameter variation, and determination of an assessment for each parameter variation. The assessment found for each parameter variation is applied as a criterion for the processing of a son node of the processed node.

Claims

1. A method of using a computing device to process digitised picture data by matching of picture matching models, comprising:

(i) provision of an hierarchical structure graph comprising;

nodes, wherein each node represents at least one parameterised picture matching model,

a specified number of levels, arranged one above the other, whereby at least one node is located in each level,

edges connecting pairs of predetermined nodes of different levels and defining, for each pair of nodes, a father node as the node in the lower level and a son node as the node in the upper level;

(ii) application of the structure graph to the picture data in that, starting with the lowermost level, at least one node is processed,

wherein the processing of a node comprises using the computing device to perform the steps of;

matching of its at least one picture matching model to the picture data by variation of the model parameters,

determination of a matching quantity for each parameter variation as a measure of the quality of the picture match, and

determination of an assessment for each parameter variation, taking into account the at least one determined matching quantity, and

wherein the assessment found for each parameter variation is applied as a criterion for the processing of a son node of the processed node and, if the criterion is fulfilled, the processing of the son node starts with the initialisation of its at least one matching model through predetermined parameters of the father node,

wherein the picture matching models comprise graphs of features which are the result of the application of predetermined filters on reference picture data,

wherein the features include jets, whereby the scaling of the filters from which the features are obtained becomes smaller from the lower levels to the upper levels in the structure graph, and

wherein the matching quantity for the parameter variations is computed according to the formula

S⁽ⁿ⁾=f⁽ⁿ⁾(P_k⁽ⁿ⁾j(k,m),P_k⁽ⁿ⁾{tilde over (j)}(k),d⁽⁰⁾(k,m),d⁽ⁿ⁾(k,m)), kε

K′

(n)⊂

K,

wherein;

j(k,m) is the jet of the picture matching model m on the node k,

{tilde over (j)}(k) is the jet of the picture on the position of the node k,

d⁽⁰⁾(k,m) is the original position of the node k of the picture matching model m,

d⁽ⁿ⁾(k,m) is the position of the node k of the picture matching model m in step n,

f⁽ⁿ⁾( . . . ) is a functional of the picture matching model jet and the picture jet at corresponding locations,

P_k⁽ⁿ⁾ represents an image of the jets j(k,m) or {tilde over (j)}(k), and

K′

(n) is a subset of the set K of all graph nodes k.

2. A method according to claim 1, in particular for the recognition of at least one object of a given object class in a picture,

whereby the structure graph includes precisely one node in each level, which at least represents one picture matching model and a lower threshold value and/or an upper threshold value is assigned to given nodes,

whereby the method is terminated with the result,

that no object of the given object class is recognised, if for a node the assessment of each parameter variation lies below the lower threshold value assigned to the node, or

that at least one object of the given object class is recognised, if for a node the assessment of at least one parameter variation lies above the upper threshold value assigned to the node or if the end node is reached.

3. A method according to claim 1 for the recognition of the orientation and/or arrangement of elements of an object of an object class in a picture, in particular for estimating the pose,

whereby the structure graph for each orientation to be recognised and/or arrangement of elements of the object exhibits at least one node with at least one picture matching model for the orientation to be recognised and/or arrangement of the elements of the object, and an upper and/or lower threshold value for the assessment of the parameter variations is assigned to given nodes,

whereby the processing of son nodes of those processed nodes is waived for which the assessment of each parameter variation lies below the lower threshold value assigned to the relevant node with the result that the corresponding orientations and/or arrangements of the elements of the object are not present in the picture,

whereby son nodes of those processed nodes are processed for which the assessment of at least one parameter variation lies between the upper and lower threshold values assigned to the node, and

whereby processing of son nodes for the parameter variations is waived whose assessment lies above the upper threshold value assigned to the relevant node with the result that the orientation and/or arrangement of the elements of the object is classified as being present in the picture which receives the best assessment on the highest fully processed level.

4. A method according to claim 1 for scene analysis through the recognition of objects of different object classes and the arrangement of the objects in a picture:

whereby the structure graph for each object class exhibits at least one node with at least one picture matching model for the object class and a lower and/or upper threshold value is assigned to given nodes for the assessment of the parameter variations,

whereby the processing of son nodes of those processed nodes is waived for which the assessment of each parameter variation lies below the lower threshold value assigned to the relevant node with the result that the associated object is classified as not being present in the picture,

whereby son nodes of those processed nodes are processed for which the assessment of at least one parameter variation lies between the lower and upper threshold values assigned to the relevant nodes, and

whereby the processing of son nodes for the parameter variations is waived whose assessment lies above the upper threshold value assigned to the relevant node with the result that the associated object is classified as being present in the picture.

5. A method according to claim 1, in which a lower threshold value is assigned to each node of the structure graph and the processing of son nodes of a node is waived if each parameter variation produces an assessment below the lower threshold value assigned to the node.

6. A method according to claim 1, in which a lower and/or an upper threshold value for given nodes is dynamically adaptable.

7. A method according to claim 1, whereby, at least partially, parameters of the processed father nodes are accepted for the processing of given nodes.

8. A method according to claim 1, whereby the assessment of the father node is taken into account for the assessment of given nodes.

9. A method according to claim 1, in which weightings, which are included in the assessment, are assigned to each picture matching model and/or each edge.

10. A method according to claim 1, in which the picture matching models of the nodes of the uppermost level are based on digitised reference picture data and/or the picture matching models of predetermined nodes are based on the picture matching models of their son nodes.

11. A method according to claim 1, in which the features comprise combinations of various types of jet.

12. A method according to claim 4 for picture compression and picture sequence compression, comprising the steps:

compressing each recognised object with a compression factor specified for the corresponding object class, whereby the control of the parameters of the compression method is based on the parameters of the results of the scene analysis, and

compressing the picture region not occupied by objects using a higher specified compression factor.

13. A method of decompressing a picture which has been compressed according to the method described in claim 12.

14. A method of substituting at least one selected object by an object representative, in particular by an avatar, comprising the steps:

recognizing the at least one selected object according to the method of claim 2,

providing reference pictures of the object representatives,

substituting the at least one selected recognised object by the object representative, whereby part of the parameters of the picture matching models may be used for the control of the object representative.

15. A method of substituting a picture background by an alternate background, comprising the steps:

providing at least one reference picture for the alternate background,

recognizing at least one object according to the method of claim 2, and

positioning of the recognized at least one object in the reference picture.

16. A method, comprising:

(i) recognizing at least one selected recognised object according to the method of claim 2,

(ii) substituting the at least one selected object by an object representative, in particular by an avatar, comprising the steps;

providing reference pictures of the object representatives,

substituting the at least one selected recognised object by the object representative, whereby part of the parameters of the picture matching models may be used for the control of the object representative; and

(iii) substituting a picture background by an alternate background, comprising the steps;

providing at least one reference picture for the alternate background,

positioning the at least one selected recognised object in the reference picture;

whereby at least one selected recognised object is substituted by an object representative and the background is substituted by the alternate background.

17. A method of visually displaying scenes processed according to claim 14, comprising the steps:

providing a data base with the object representatives and/or the reference pictures for the background.

18. A method according to claim 17, in which the object representatives comprise real objects and/or virtual objects.

19. A method according to claim 1, whereby, for the processing of individual pictures in a picture sequence, the parameters of the picture matching models are assigned initial values which use part of the parameters from the processing of previous pictures.

20. A method according to claim 19, whereby the possible variations of the parameters of the picture matching models, based on a part of the parameters from the processing of previous pictures, are restricted.

21. A method according to claim 1, in which the features comprise combinations of various types of jet.

22. A method according to claim 1, wherein the application of predetermined filters on reference picture data includes a transformation of the reference picture data.