Active semiotic system for image and video understanding by robots and unmanned vehicles, methods and apparatus

{
  "publication_number": "US2007239314A1",
  "country": "US",
  "kind": "A1",
  "title": "Active semiotic system for image and video understanding by robots and unmanned vehicles, methods and apparatus",
  "abstract": "An active semiotic system that is able to create implicit symbols and their alphabets from features, structural combination of features, objects and, in general sense, patterns; create models with explicit structures that are labeled with said implicit symbols, and derive other models in the same format by means of diagrammatic- and graph transformations. The invention treats vision as a part of larger system that converts visual information into special knowledge structures that drive vision process, resolve ambiguity and uncertainty via feedback projections, and provide image understanding that is an interpretation of visual information in terms of such knowledge models. Mechanisms of image understanding, including mid- and high- level vision are presented as methods and algorithms of said active semiotic system, where they are special kinds of diagrammatic and graph transformations. In the invention, the derived structure and not the primary view is a subject for recognition. Such recognition is not affected by local changes and appearances of the object from a set of similar views, and a robot or unmanned vehicle can interpret images and video similar to human beings for better situation awareness and intelligent tactical behavior.",
  "claims": [
    "1. An active semiotic system for image and video understanding by robots and unmanned vehicles, comprising a semiotic engine, low-level image processing services module, behavior planning services module, plurality of sensor and active vision controllers.",
    "2. The system of claim 1, wherein a semiotic engine comprises active diagrammatic model memory, linker, loader, activation manager, plurality of persistent implicit symbols and their alphabets, plurality of persistent diagrams and reference links, and plurality of engines for knowledge acquisition, derivation, and recognition.",
    "3. The system of claim 1, wherein low-level processing module comprises plurality of visual and object buffers.",
    "4. The system of claim 1, wherein behavior planning services module comprises plurality of behavior request controllers, tactical game engine as a planner/predictor, and situation awareness and control reporter.",
    "5. The system of claim 2, wherein an implicit symbol represents a pattern, and can be obtained as a solution to a local pattern recognition problem with a finite number of possible patterns.",
    "6. The system of claim 2, wherein an alphabet of implicit symbol represents a set that contains a finite number of possible patterns.",
    "7. A data structure wherein elements of the set of claim 6 are represented dually: as distributed continuous quantities, where each of said quantities has a core area and allows for overlapping with other quantities excluding their core area, and wherein metric relationships between their cores reflect measure of distinctiveness between the said elements; and as discrete values with their relationships.",
    "8. Method of conversion continuous quantitative parameters into their qualitative representation as mapping between continuous and discrete components of data structure of claim 7.",
    "9. Method of obtaining predefined alphabets of implicit symbols of color according to claims 5, 6, and 7 from a color space.",
    "10. Method of obtaining predefined alphabets of implicit symbols of line orientation according to claims 5, 6, and 7 from the range of angles 0°-360°.",
    "11. Method of obtaining predefined alphabets of implicit symbols of surface orientation accordingly claims 5, 6, and 7 from the sphere of all possible normal angles to surface.",
    "12. A data structure, which describes a diagrammatic knowledge model of a system, wherein structural components of said diagrammatic model is coded explicitly in the dual form of connected graph and distributed continuous quantities; each of said quantities has a core area and allows for overlapping with other quantities including their core areas, and wherein topological and spatial relations between said elements reflect relationships between said elements of said modeled structure; and as discrete values wherein relationships between them are represented with a graph-type structure wherein nodes of the graph represent said elements of said diagrammatic knowledge model; and wherein elements of the said diagrammatic model are labeled with implicit symbols of claims 5, 6, and 7.",
    "13. A data structure wherein relations between the implicit symbols of claims 5, 6, and 7 are represented as metric or spatial values and coded with another set of implicit symbols that denote character of relations between the implicit symbols of claims 5, 6, and 7.",
    "14. A data structure of claim 7 wherein all possible metric and spatial relations between the continuously represented elements of data structures of claim 12 are represented with implicit alphabet of claim 6.",
    "15. A data structure wherein data structure of claim 7 is associated with an implicit symbol of claim 5 that stands for said particular structure of claim 7.",
    "16. A data structure wherein data structure of claim 12 is associated with an implicit symbol of claim 5 that stands for said particular structure of claim 12.",
    "17. Activation manager of claim 2 that is an executive computer program, which comprises: means for assigning active state to a particular data structure of claims 15 and 16; means for assigning inactive state to a particular data structure of claims 15 and 16. means for assigning active state to a particular element of data structure of claims 15 and 16; means for assigning inactive state to a particular element of data structure of claims 15 and 16. means for assigning active state to a particular link or association; means for assigning inactive state to a particular link or association; means for activating said data structure or its element from the associated with it implicit symbol; means for activating associated implicit symbol from the associated said data structure or its element.",
    "18. Apparatus for processing activated data structures and their elements and links of claims 15, 16 in the active diagrammatic memory of claim 2 comprising: means for selection of relevant data structures of claims 15, 16 from the plurality of all possible said data structures of claims 15, 16 via elements and links of said structures that were activated previously; means for activation said selected data structures by activation manager of claim 17; means for loading said activated data structures into active diagrammatic memory of claim 2 by loader of claim 2; means for linking elements of said activated data structures with linker of claim 2; means for sequentially activating neighbor elements of said linked structures with activation manager of claim 17; means for linking initial activated element with final activated element, which is equivalent to a closure link for mathematical proof and reflex link in neurophysiology; means for linking simultaneously activated elements with linker of claim 2.",
    "19. Derivation engine of claim 2 that is an executive computer program, which derives new diagrammatic knowledge models, and comprises: means for creating new data structures of claims 15, 16 from the ones that are loaded into active diagrammatic memory; means for verification of newly created data structures for contradiction to other relevant data structures of claims 15, 16 within the plurality of said data structures accumulated in the system.",
    "20. Knowledge acquisition engine of claim 2 that is an executive computer program, which comprise: means for storing new data structures of claims 15, 16 that were created in the claims 18, 19 within the plurality of persistent diagrams and reference links of claim 2 and within the plurality of implicit symbols and their alphabets of claim 2; means for creation of data structures of claims 15, 16 that were converted from different formats supplied by a human-computer input interface, and storing them within the plurality of persistent diagrams and reference links of claim 2 and within the plurality of implicit symbols and their alphabets of claim 2; means for copying data structures of claims 15, 16 from another semiotic engines in the same format and storing them within the plurality of persistent diagrams and reference links of claim 2 and within the plurality of implicit symbols and their alphabets of claim 2.",
    "21. Recognition engine of claim 2 that is an executive computer program, which recognizes patterns and activates appropriate implicit symbols and their alphabets, and comprises: means for recognition of structural and statistical patterns; means for activating appropriate implicit symbol, which stands for this pattern, and its alphabet; means for creation of new implicit symbol within an existing alphabet, in case if such pattern cannot be recognized with any of existing symbols, but an alphabet for similar patterns exists within the plurality of persistent implicit symbols and their alphabets; means for creating a new implicit alphabet and new implicit symbol within said alphabet, in case if such pattern cannot be recognized with any of existing symbols, but no alphabet for similar patterns exists within the plurality of persistent implicit symbols and their alphabets.",
    "22. Method of creation of implicit alphabet of claim 7, which comprises the steps of: selecting a finite set of entities that are supposed to be represented with implicit symbols of an implicit alphabet; training recognition engine of claim 21 to recognize these entities; creating a computer model of an empty distributed space; mapping said distributed space to the outputs of said recognition engine, in which case said space become split by overlapping regions with non-overlapping cores that represent recognized entities, wherein spatial relations between said cores reflect degrees of similarities between recognized patterns; mapping cores to appropriate discrete elements from the set that represent implicit symbols in the qualitative part of the said created data structure.",
    "23. Method of updating implicit alphabet with another implicit symbol of claim 7, which comprises the steps of: adding another implicit symbol to a finite set of entities that are supposed to be represented with implicit symbols of said implicit alphabet; training recognition engine of claim 21 to recognize the new pattern which is represented with a new implicit symbol; re-mapping distributed part of the alphabet to the outputs of said recognition engine as it done in method of claim 22; mapping the core of newly created region to newly added discrete element of the set that represent implicit symbols in the qualitative part of the said data structure.",
    "24. Method of association of a data structure of claim 7 or claim 12 with implicit symbol of claim 5, which comprises linking of said data structure to an implicit symbol of an implicit alphabet of claim 6 with linker of claim 2.",
    "25. Method of creating new diagrammatic models of claim 15 from a set of said diagrammatic models in the active diagrammatic memory of claim 2, which comprises the steps of: creating topological connection in the new system model with: a) linking nodes in the discrete part of said diagrammatic models with linker of claim 2 according to implicit symbols of nodes and rules of linking that can be specified explicitly with another diagrammatic model, or implicitly coded in the system; b) using rules of clustering and separating in the continuous part according to criteria of similarity; creating implicit symbol for a newly created structure, adding it to a new or existing implicit alphabet according to methods of claims 22, 23; associating newly created data structure with its implicit symbol as in method of claim 24.",
    "26. Method of splitting a diagrammatic model of claim 12 that resides in active diagrammatic model memory of claim 2 into smaller ones, which comprises the steps of: splitting discrete part of said diagrammatic model into substructures by splitting element set and topological connections; splitting continuous part; adding newly created models to the plurality of persistent diagram models and reference links; adding implicit symbols that stand for the new data structures to the appropriate implicit alphabets according to the method of claim 23.",
    "27. Method of compression of diagrammatic model, which comprises the steps of: creating implicit symbol from the repeated structural components of diagrammatic model with recognition engine of claim 21; splitting diagrammatic model according to method of claim 26; replacing structures with reference to their symbol according to method of claim 24.",
    "28. Method of decompression of diagrammatic model by replacing nodes labeled with implicit symbols by the diagrammatic models that implicit symbols stand for, which comprises the steps of: activating diagrammatic model from their implicit symbols; loading them into the active diagrammatic memory; removing nodes with their implicit symbols; linking loaded structures within initial diagrammatic model.",
    "29. Method of derivation of new diagrammatic models with graph transformations, wherein certain structural components of diagrammatic model are replaced with other structural components according to the rules of structural transformations, wherein each rule is defined as a conditional or unconditional replacement of one implicit symbol with another one, comprising the steps of: compressing structural pattern that have to be replaced, accordingly to the method of claim 27; replacement with a new implicit symbol accordingly to the rule of replacement; decompression with new structure accordingly to method 29.",
    "30. Method of derivation of new diagrammatic models that describe regularity in the initial diagrammatic model, which comprises the steps of: creating implicit symbol from the repeated structures of diagrammatic model; creating new diagrammatic model that reflects topology of the compressed part of the structure, wherein elements are said implicit symbols of the repeated structures and are linked in the same way; adding this newly created model to initial model according to the method of claim 25; repeating the steps above on the resulted diagrammatic model until some regularity exists.",
    "31. Method of mathematical proof based on said diagrammatic models, which comprises the steps of: finding if exists a topological path between the elements of model, which should be equivalent; linking said initial and final elements with a closure link, using linker of claim 2.",
    "32. Method of compression or decompression diagrammatic model using method of claim 29 and replacement rule obtained from a different diagrammatic model with method of claim 31, wherein initial set of elements is replaced with the final one.",
    "33. An apparatus for emulation of a full scale real-world knowledge system, wherein said system comprise knowledge base from facts and rules, context system, world (system) model, model inference engine, knowledge inference engine, simulation engine, and real world interface; said apparatus comprising semiotic engine of claim 2, and low-level image processing services module of claim 2.",
    "34. Active vision system that comprise elements of claim 33, behavior planning services module, interfaces to motion and navigation controllers, and sensors and active vision controllers, wherein the process of interpretation of content of visual buffer creates situation awareness in the form of diagrammatic ecological model of visual scene that is labeled with implicit symbols of objects, regions, and surfaces; said diagrammatic ecological model is mapped back to visual buffer, and can generate requests to said plurality of motion and navigation controllers for changing position of the robot or unmanned vehicle, and requests to said plurality of sensor and active vision controllers for panning, tilting, and zooming of visual sensors for changing the content of visual buffer in order to disambiguate visual information for completing model of visual scene and achieving the largest possible degree of situation awareness.",
    "35. An apparatus for processing data in visual buffer of claim 3, which is a computer program or a parallel hardware implementation of said computer program comprising active vision system of claim 34; means for mapping ecological constraints to the visual buffer and identification and implicit labeling of ecologically important elements of visual scene such as ground plane, horizon, and perspective; means for identification and implicit labeling of orientation lines, basic planes and surfaces; means for assigning relative distances and spatial order in visual buffer; means for visual context creation; means for creation of scene diagram; situation awareness controller which provides active vision system with requests for saccadic motion of visual sensors and attention for processing of particular regions of interest; means for providing said saccadic motion and attention; means for tracking salient objects; means for centering object in the region of attention; means for placing region of attention into object buffer from claim 3, wherein said visual object or region is recognized or identified and its implicit symbol provides implicit labeling of scene diagram, which is mapped back to said visual buffer.",
    "36. An apparatus for processing data in object buffer of claim 3, which is a computer program or a parallel hardware implementation of said computer program comprising: active vision system of claim 34; region of interest (ROI) controller, which coordinates with mechanism of visual buffer the process of keeping analyzed object or region in the center of said object buffer; means for separation of figure from ground; means for identification of said object or region by its components and context, especially if it is occluded or poorly visible; means for creation of object signature or region texture signature; means for deriving class signature - derivative structure from object signature or region texture signature; means for recognition of said object, texture and class signatures; means for provides implicit labeling of scene diagram with implicit symbols of said object, or region. A data structure for processing data in visual and object buffers, which is based on the informational model of cortical supercolumn that covers the set of visual features in a local part of visual and object buffer, and said structure has distributed part with a core in the center, and discrete part which comprises links to implicit symbols of claim 5 in implicit alphabets of claim 6.",
    "37. A data structure of claim 36 that allows for overlapping its distributed part excluding core with a neighbor data structure of claim 36 of the same level, and overlapping including core with a data structure of claim 36 that is considered to be a on a higher hierarchical level of spatial hierarchy thus covering a larger region.",
    "38. A data structure, which is a qualitative analog of number system, wherein neighboring data structures of claim 37 are approximately of the same size at the same level of hierarchy, while they are hierarchically connected to another data structure of claim 37 of the next spatial level that covers larger area of visual or object buffer",
    "39. An apparatus for processing visual information in the visual buffer of claim 2 upon data structure of claim 38, which is a computer program comprising: means for hierarchical clustering of visual information; means for grouping and separation upon the relational difference of values in perceptual symbols; means of linking data structures of claim 38 into meaningful diagrammatic model structures of claim 16.",
    "40. An active vision system of claim 34, wherein said sensors and active vision controller is equipped with means of disambiguation of sensor orientation relatively to the earth surface such as gravitational sensors.",
    "41. Method of interpreting visual buffer in the active vision system of claim 40 accordingly to the principles of ecological optics, comprising the steps of: splitting visual buffer into logical zones with different values of visual information on the scale from “near” to “far”, and creating an implicit alphabet of such zones; assigning meaning of “ground plane” and “near” zone to the lower level of data structures of claim 37 that reside in the very bottom of visual buffer; finding line of horizon; assigning meaning of “far” to the data structures of claim 37 that locate near the horizon line; finding orientation lines and perspective; assigning relative distances to visual scene and labeling visual buffer with implicit labels of implicit alphabet of zones.",
    "42. Method of separation of figure from ground that uses interaction of visual and object buffer in the active vision system of claim 40, and comprises the steps of: finding a region of interest in the visual buffer wherein an object or region resides; centering region of interest to the center of found object or region; rough separation of figure from ground with data structures of claim 36; placing object or region into object buffer; final separation of figure from ground with smaller fine grained data structures of claim 36 using additional separation criteria, supplied with semiotic engine.",
    "43. Method of finding and narrowing down a region wherein object or region resides in the visual buffer, which comprises the steps of: finding largest data structures of claim 3 7 in the data structure of claim 3 8 wherein analysis show presence of features of said object or region, while the other data structures of claim 37 do not show any features that might indicate presence of said object or region; taking into consideration only data structures of claim 37 of lower level of data structure of claim 38, which are connected to the to the data structures of claim 37 of higher level that indicates presence of features of said object or region; repeating previous steps down to lowest level; a) in case of an object, which has rigid body: linking obtained data structures of claim 37 of lowest level wherein object features are found with linker of claim 2 into a coherent structure that represents a form of rigid body; finding center of said coherent structure; placing said centered region into object buffer for further analysis by semiotic engine of claim 2; b) in case of a textured region wherein obtained data structures of claim 37 might become disconnected on the lower levels as they now represent textons of said texture: linking obtained data structures of claim 37 of lowest level wherein features of said textons are found into a coherent structure that represents a pattern of connection between textons or a texture gradient with help of linker of claim 2; finding center of said coherent structure; placing said centered coherent structure that represents an object or a textured region into the object buffer for further analysis by semiotic engine of claim 2.",
    "44. Method of creation of object form signature in the form of hierarchically clustered spatial tree in the object buffer, comprising the steps of: loading obtained visual information from method of claim 43 into object buffer, which utilizes for analysis of visual information a hierarchical data structure of claim 38; logical hierarchical clustering of data structures of claim 37 starting from lowest level of data structure of claim 38; obtained shape tree logically describes form of the object and can serve as object signature with relative proportions of the object form, and can be supplied for further analysis into semiotic engine.",
    "45. Method of fusion of implicit symbols that belong to implicit alphabets of different features within the object buffer, wherein lower level data structures of claim 38 store references to implicit symbols that denote different features of visual information, such as the ones obtained from methods of claims 8, 9, 10, 11, and 41, this providing better criteria for logical analysis by semiotic engine from claim 2.",
    "46. Method of deriving invariant class signatures from data structures obtained by methods of claims 44 and 43, wherein derivation is produced by a semiotic engine of claim 2, using methods data structures and engines of claims 15 - 32, and creates graph-like invariant class signatures that can be recognized or identified with said semiotic engine, and implicit symbol will be assigned to a particular place in scene diagram, which is a part of situation awareness model.",
    "47. An apparatus for holistic recognition or identification by parts of a target or an object, which is a computer program comprising: means of holistic recognition based on recognition engine of claim; means for perceptual grouping and gestalt processing based on method of claim 30 that can be produced by semiotic engine; means of identification of object by its parts and or spatial context that can be produced by semiotic engine; means of changing region of interest from the entire object to it's part or component, wherein the same processes and data structures can be used for recognition or identification of said object's part and component.",
    "48. Active vision system of claim 40 with semiotic engine, wherein while robot or unmanned vehicle is moving, frames of video stream that are taken at different times appear in the plurality of visual buffers for revealing changes of a single diagrammatic model of visual scene that changes slowly than primary information in said video stream and allows for mapping back to the said video buffers",
    "49. Method of creation of situation awareness model for the unmanned vehicle or robot, wherein the system equipped with active vision system of claim 40 creates a scene diagram, converting visual information from primitive features to its implicit semantic description on the manner of “puzzle”, wherein empty slots are filled with help of context information, and ambiguity and uncertainty in visual information is resolved on every level of processing with feedback from higher level knowledge that is provided with semiotic engine and active vision mechanisms of claim 48.",
    "50. An apparatus, which is computer software and hardware that give to a robot or unmanned vehicle functionality that usually require a crew of people in manned vehicles, comprising plurality of active vision systems with semiotic engines of claim 48 for carrying different tasks, and one shared top-level semiotic engine of claim 2, which coordinates said plurality of active vision systems with semiotic engines of claim 48, providing robot or unmanned vehicle with more effective and intelligent tactical behavior."
  ],
  "cpc": [
    "G06N 3/008",
    "G06V 10/454"
  ],
  "assignees": [
    "KUVICH GARY"
  ],
  "filing_date": "2006-05-18",
  "publication_date": "2007-10-11",
  "priority_date": "2006-04-07",
  "application_number": "US-41919906-A",
  "family_id": "38576464",
  "citations": [
    "US2002095276A1",
    "US2004093122A1",
    "US2004153212A1",
    "US2005197739A1",
    "US2005222713A1",
    "US2006126918A1",
    "US2007078564A1",
    "US5579444A",
    "US6879946B2"
  ]
}