A multiple video stream capture and encoding apparatus produces compressed data that represents multiple video streams capturing a common scene. Images from multiple video streams are analyzed to identify image color segments that are encoded into a composite graph data structure. Corresponding image segments across the multiple video streams are also identified and represented by one node in the composite graph data structure. The composite graph data structure also includes links between pairs of nodes that describe the relationship between the image segments associated with those nodes. The composite graph data structure is updated to represent changes to the image segments in the multiple video streams over time. The composite graph data structure is used to create compressed encoded data for storage and/or transmission.