Scene model generation from video for use in video processing

A method of generating and utilizing a three-dimensional cube-based scene model from a sequence of video frames, comprising the steps of:

• separating background data from foreground data for each of said frames;
• using an estimate of relative observer motion, projecting each frame onto a coordinate system used in generating said scene model;
• and
• mapping each point on the edge of a frame, F, through M−1, the inverse of observer motion estimation matrix M, to convert said point to a point in scene model coordinates;
• and
• for each cube face of the scene model to which an edge point of F is mapped, performing the following sub-steps:
• finding a box bounding all edge points of F mapped to said cube face;
• and
• for each point, (x,y) within said box, performing the following sub-sub-steps:
• mapping a vector defined by (x,y,FL), where FL is a focal length of said observer, through M to convert the vector to an image coordinate (a,b);
• using interpolation to determine a pixel value for (a,b) in F;
• and
• placing said pixel value for (a,b) at (x,y).

A method of generating and utilizing a three-dimensional cube-based scene model from a sequence of video frames, comprising the steps of:

• separating background data from foreground data for each of said frames;
• using an estimate of relative observer motion projecting each frame onto a coordinate system used in generating said scene model;
• merging the background data of the frame with the scene model;
• reprojecting said scene model to an image, comprising the sub-steps of:
• for each point (x,y) in said image, performing the sub-sub-steps of:
• mapping a vector (x,y,FL), where FL is a focal length of said observer, through M−1, the inverse of an observer motion estimation matrix M, to obtain a vector V in the coordinate system of the cube-based scene model;
• transforming V to a point (a,b) on a cube face in the scene model;
• using interpolation to find a pixel value at the point (a,b);
• and
• placing the pixel value corresponding to point (a,b) at the point (x,y) in said image.

A method of generating and utilizing a three-dimensional scene model from a sequence of video frames, comprising the steps of:

• separating background data from foreground data for each of said frame;
• using an estimate of relative observer motion, projecting each frame onto a coordinate system used in generating said scene model;
• and
• merging the background data of the frame with the scene model, wherein said scene model is based on a three-dimensional surface;
• detecting whether or not a current focal length in a frame has changed relative to a previous focal length of a previous frame, comprising the sub-steps of:
• choosing a point on the right edge of a frame;
• converting said point to a point in a coordinate system of said three-dimensional surface;
• choosing a corresponding point on the left edge of said frame, said corresponding point having a row coordinate in common with said point on the right edge of the frame;
• converting said corresponding point to a point in the coordinate system of said three-dimensional surface;
• determining the size of an angle between vectors formed by connecting said points converted to points in the coordinate system of said three-dimensional surface with the origin of the coordinate system;
• and
• if said angle differs from that corresponding to said previous frame in an amount exceeding a particular value, determining that the focal length has changed;
• and if said detecting step determines that the focal length has changed, creating a new scene model layer corresponding to the current focal length.

A method of compressing and decompressing digital video data obtained from a video source, comprising the steps of:

• decomposing said digital video data into an integral sequence of frames obtained from said video source and corresponding to a single observer;
• computing a relative position and orientation of said observer based on a plurality of corresponding points from a plurality of frames of said sequence of frames;
• classifying motion by said observer;
• identifying regions of a video image corresponding to said digital video data containing moving objects and designating such objects as foreground objects;
• designating the remaining portions of said video image as background;
• encoding said foreground objects separately from said background;
• encoding said background by generating a three-dimensional cube-based scene model, comprising the following sub-steps:
• using an estimate of observer motion, projecting each frame onto a coordinate system used in generating said scene model;
• and
• merging the portion of said digital video data of said frame corresponding to said background with said scene model;
• detecting whether or not a current focal length in a frame has changed relative to a previous focal length of a previous frame, comprising the sub-steps of:
• choosing a point on the right edge of a frame;
• converting said point to cube coordinates;
• choosing a corresponding point on the left edge of said frame, said corresponding point having a row coordinate in common with said point on the right edge of the frame;
• converting said corresponding point to cube coordinates;
• determining the size of an angle between vectors formed by connecting said points converted to cube coordinates with the origin of said cube coordinates;
• and
• if said angle differs from that corresponding to said previous frame in an amount exceeding a particular value, determining that the focal length has changed;
• and if said detecting step determines that the focal length has changed, creating a new scene model layer corresponding to the current focal length.

A method of compressing and decompressing digital video data obtained from a video source, comprising the steps of:

• decomposing said digital video data into an integral sequence of frames obtained from said video source and corresponding to a single observer;
• computing a relative position and orientation of said observer based on a plurality of corresponding points from a plurality of frames of said sequence of frames;
• classifying motion by said observer;
• identifying regions of a video image corresponding to said digital video data containing moving objects and designating such objects as foreground objects;
• designating the remaining portions of said video image as background;
• encoding said foreground objects separately from said background;
• and
• encoding said background by generating a three-dimensional cube-based scene model, comprising the following sub-steps:
• using an estimate of observer motion, protecting each frame onto a coordinate system used in generating said scene model;
• and
• mapping each point on the edge of a frame, F, through M−1, the inverse of observer motion estimation matrix M, to convert said point to a point in scene model coordinates;
• and
• for each cube face of the scene model to which an edge point of F is mapped, performing the following sub-steps:
• finding a box bounding all edge points of F mapped to said cube face;
• and
• for each point, (x,y) within said box, performing the following sub-sub-steps:
• mapping a vector defined by (x,y,FL), where FL is a focal length of said observer, through M to convert the vector to an image coordinate (a,b);
• using interpolation to determine a pixel value for (a,b) in F;
• and
• placing said pixel value for (a,b) at (x,y).

A method of compressing and decompressing digital video data obtained from a video source, comprising the steps of:

• decomposing said digital video data into an integral sequence of frames obtained from said video source and corresponding to a single observer;
• computing a relative position and orientation of said observer based on a plurality of corresponding points from a plurality of frames of said sequence of frames;
• classifying motion by said observer;
• identifying regions of a video image corresponding to said digital video data containing moving objects and designating such objects as foreground objects;
• designating the remaining portions of said video image as background;
• encoding said foreground objects separately from said background;
• and
• encoding said background by generating a three-dimensional cube-based scene model, comprising the following sub-steps:
• using an estimate of observer motion, projecting each frame onto a coordinate system used in generating said scene model;
• and
• merging the portion of said digital video data of said frame corresponding to said background with said scene model;
• reprojecting said scene model to an image, comprising the sub-steps of:
• for each point (x,y) in said image, performing the sub-sub-steps of:
• mapping a vector (x,y,FL), where FL is a focal length of said observer, through M−1, the inverse of an observer motion estimation matrix M, to obtain a vector V in the coordinate system of the cube-based scene model;
• transforming V to a point (a,b) on a cube face in the scene model;
• using interpolation to find a pixel value at the point (a,b);
• and
• placing the pixel value corresponding to point (a,b) at the point (x,y) in said image.

A method of compressing and decompressing digital video data obtained from a video source, comprising the steps of:

• decomposing said digital video data into an integral sequence of frames obtained from said video source and corresponding to a single observer;
• computing a relative position and orientation of said observer based on a plurality of corresponding points from a plurality of frames of said sequence of frames;
• classifying motion by said observer;
• identifying regions of a video image corresponding to said digital video data containing moving objects and designating such objects as foreground objects;
• designating the remaining portions of said video image as background;
• encoding said foreground objects separately from said background;
• encoding said background by generating a three-dimensional scene model, comprising the following sub-steps:
• using an estimate of observer motion, projecting each frame onto a coordinate system used in generating said scene model;
• and
• merging the portion of said digital video data of said frame corresponding to said background with said scene model, wherein said scene model is based on a three-dimensional surface;
• detecting whether or not a current focal length in a frame has changed relative to a previous focal length of a previous frame, comprising the sub-steps of:
• choosing a point on the right edge of a frame;
• converting said point to a point in a coordinate system of said three-dimensional surface;
• choosing a corresponding point on the left edge of said frame, said corresponding point having a row coordinate in common with said point on the right edge of the frame;
• converting said corresponding point to a point in the coordinate system of said three-dimensional surface;
• determining the size of an angle between vectors formed by connecting said points converted to points in the coordinate system of said three-dimensional surface with the origin of the coordinate system;
• and
• if said angle differs from that corresponding to said previous frame in an amount exceeding a particular value, determining that the focal length has changed;
• and if said detecting step determines that the focal length has changed, creating a new scene model layer corresponding to the current focal length.

A computer system capable of generating and utilizing a three-dimensional cube-based scene model from a sequence of video frames, comprising:

• a computer, including:
• storage means;
• input/output means;
• and
• processing means;
• and
• software means, programmed on a medium readable by said computer, comprising:
• means for separating background data from foreground data for each of said frames;
• means for projecting each of said frames onto a coordinate system used in generating said scene model, said means for projecting using an estimate of relative motion of an observer;
• means for merging the background data of the frame with the scene model;
• means for detecting whether or not a current focal length in a frame has changed relative to a previous focal length of a previous frame, comprising:
• means for choosing a point on the right edge of a frame;
• means for converting said point to cube coordinates;
• means for choosing a corresponding point on the left edge of said frame, said corresponding point having a row coordinate in common with said point on the right edge of the frame;
• means for converting said corresponding point to cube coordinates;
• means for determining the size of an angle between vectors formed by connecting said points converted to cube coordinates with the origin of said cube coordinates;
• and
• means for determining that the focal length has changed if said angle differs from that corresponding to said previous frame in an amount exceeding a particular value;
• and
• means for creating a new scene model layer corresponding to the current focal length if said means for detecting determines that the focal length has changed.

A computer system capable of generating and utilizing a three-dimensional cube-based scene model from a sequence of video frames, comprising:

• a computer, including:
• storage means;
• input/output means;
• and
• processing means;
• and
• software means, programmed on a medium readable by said computer, comprising:
• means for separating background data from foreground data for each of said frames;
• means for projecting each of said frames onto a coordinate system used in generating said scene model, said means for projecting using an estimate of relative motion of an observer;
• means for mapping each point on the edge of a frame, F, through M−1, the inverse of observer motion estimation matrix M, to convert said point to a point in scene model coordinates;
• and
• means for processing each cube face of the scene model to which an edge point of F is mapped, comprising:
• means for finding a box bounding all edge points of F mapped to said cube face;
• and
• means for manipulating each point, (x,y) within said box, comprising:
• means for mapping a vector defined by (x,y,FL), where FL is a focal length of said observer, through M to convert the vector to an image coordinate (a,b);
• interpolation means for determining a pixel value for (a,b) in F;
• and
• means for placing said pixel value for (a,b) at (x,y).

A computer system capable of generating and utilizing a three-dimensional cube-based scene model from a sequence of video frames, comprising:

• a computer, including:
• storage means;
• input/output means;
• and
• processing means;
• and
• software means, programmed on a medium readable by said computer, comprising:
• means for separating background data from foreground data for each of said frames;
• means for projecting each of said frames onto a coordinate system used in generating said scene model, said means for projecting using an estimate of relative motion of an observer;
• and
• means for merging the background data of the frame with the scene model,
• said software means further comprising:
• means for reprojecting said scene model to an image, comprising:
• means for processing each point (x,y) in said image, comprising:
• means for mapping a vector (x,y,FL), where FL is a focal length of said observer, through M−1, the inverse of an observer motion estimation matrix M, to obtain a vector V in the coordinate system of the cube-based scene model;
• means for transforming V to a point (a,b) on a cube face in the scene model;
• interpolation means for finding a pixel value at the point (a,b);
• and
• means for placing the pixel value corresponding to point (a,b) at the point (x,y) in said image.

A computer system capable of generating and utilizing a three-dimensional scene model from a sequence of video frames, comprising:

• a computer, including:
• storage means;
• input/output means;
• and
• processing means;
• and
• software means, programmed on a medium readable by said computer, comprising:
• means for separating background data from foreground data for each of said frames;
• means for projecting each of said frames onto a coordinate system used in generating said scene model, said means for projecting using an estimate of relative motion of an observer;
• and
• means for merging the background data of the frame with the scene model, wherein said scene model is based on a three-dimensional surface;
• means for detecting whether or not a current focal length in a frame has changed relative to a previous focal length of a previous frame, comprising:
• means for choosing a point on the right edge of a frame;
• means for converting said point to a point in a coordinate system corresponding to said three-dimensional surface;
• means for choosing a corresponding point on the left edge of said frame, said corresponding point having a row coordinate in common with said point on the right edge of the frame;
• means for converting said corresponding point to a point in the coordinate system corresponding to said three-dimensional surface;
• means for determining the size of an angle between vectors formed by connecting said points converted to points in the coordinate system corresponding to said three-dimensional surface with the origin of the coordinate system corresponding to said three-dimensional surface;
• and
• means for determining that the focal length has changed if said angle differs from that corresponding to said previous frame in an amount exceeding a particular value;
• and
• means for creating a new scene model layer corresponding to the current focal length if said means for detecting determines that the focal length has changed.