Followup to: Restoring the structure.
Graph restoration procedure only uses structural contexts of known scene graphs. Thus, there is no need to preserve individual scenes. Instead, the set of all structural contexts of all known scenes should be summarized directly. Context-matching only looks at labels of nodes, so identities of nodes in known scenes are also irrelevant. For example, if a certain structural context is frequently present in known scenes, this fact can be represented without keeping separate copies and without keeping track of which scenes this context is present in.
If structural contexts are sufficiently small, and if elements of scene graph encode sufficient amount of information about its local structure using special labels and multilevel representation, structural contexts themselves can be further simplified. I’ll call these simplified structural contexts maps, to avoid confusion with more general notion of context. A map consists only of a central label and a set of weighted support labels, and it doesn’t encode a subgraph. Maps are created from structural contexts by measuring the distance from central node to other nodes, and discarding the remaining structure, keeping only information about labels. Similar maps are joined together, with weights of the summary reflecting the weights in the originals and frequencies of their elements.
Maps are matched against the structural context in current scene (a subgraph that is not simplified). When matched maps strongly indicate that a certain label should be added to the current structural context, either a new node with this label is created, or an edge connects central node of structural context with another node that already has that label. If edge needs to be created between nodes that are not central in the current structural context, it’ll have to wait until one of these nodes becomes a center of another structural context. It nodes with the same label are located close together, they need to be looked at from different maps to attract different structure. Step by step, this more limited algorithm can also restore structures from known scenes. The structure restoration from unstructured maps is supported by the structure of current scene. Structural contexts guide both the search among maps extracted from known scenes and application of their elements.
Taken together, maps can be considered local pattern-completion rules, that get applied to the current scene, with the rules having the best match (and better track record) acting first.
Another interesting consequence of representing known scenes in form of maps is that it becomes possible to represent the current scene the same way. If set of known scenes consists of only a single scene, the process of structure restoration will recreate that same scene, even if it starts from a single node. So, while scene restoration ostensibly requires supporting explicit graph, to act as a framework on which maps grow the structure, that graph can be shattered on small simplified fragments when it’s not explicitly required. Current scene can be represented by a set of its maps. A similar approach was originally used by connectionists to represent structured knowledge as an unordered set of atomic symbols, with symbols encoding local neighborhoods of structure. For example, a string of letters in natural language can be encoded using a set of n-grams.
Thus, both known scenes and the current scene can be represented by an overall set of maps, with maps constituting the current scene marked as salient maps. To launch the structure restoration process, first salient maps are used to restore the current scene, and then the rest of the maps are used to build on it.
