Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
2001-07-23
2003-06-24
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Applications
Motion or velocity measuring
C382S209000, C382S280000
Reexamination Certificate
active
06584213
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to digital signal pattern matching and more specifically some embodiments of the invention relate to methods and apparatus for matching segments across multiple related images.
Digital signal pattern matching involves a plurality of multi-dimensional digital signals and is a process of matching all or part of one or more of the signals to all or part of another one or more of the signals. For example, where the digital signals represent digitized images and the plurality relates to a sequence of digital images, a digital signal matching process might be used to identify corresponding portions of the images between two images that have a known relationship. One such relationship is where the digital images in the plurality form a timed sequence such as a video sequence and the two images that are being processed are two adjacent in time images.
Matching is often used to detect motion in the video sequence, by identifying an object in the scene captured in one digital image, identifying that same object in another scene and noting the position change from one image to the other. For example, where the video sequence being processed is a football game, the process might be used to detect the motion of an object such as a football. It should be noted that the matching processes described herein are not limited to actual objects in the scene, but might reference portions of objects. For example, in a video sequence of a beach ball having several solid colored portions of differing colors might be processed with each different colored portion being treated as a different object.
An image frame can be divided up into a plurality of segments such that each pixel is associated with exactly one segment, or in some cases with a small number of segments where a pixel is judged to be on a border of the image where a small number of segments meet. Typically, a segment is a portion of a digital signal wherein the pixel color values are substantially uniform. Several methods of dividing an image frame into segments according to the pixel color values of the image frame are described in Prakash II. As used herein, a segment is a portion of the image frame or frames that is a contiguous region having a relatively small amount of color variation throughout. For example, one image frame might include a region where the color values of the pixels in that region are all blue or variations of blue such that the region can be identified as a segment.
In the general case of motion matching, a segment of one image is identified from one digital signal representing an image frame and matched to a corresponding segment or portion of another image represented by another digital signal. The matching process, in this example, might consider the blue region (mentioned above) a segment and seek to match that segment with a similar blue region in another image frame.
While it need not be the case, matching is often an attempt to “track” a segment in a video sequence as it moves within the frame window of the video sequence. Thus, digital signal pattern matching can be used in various applications such as video compression, medical imaging and object tracking. For example, a digital image processor can determine how a segment moved from one image frame of a video sequence to the next image frame of the video sequence by noting the position of a segment in a first image frame, extracting that segment and matching it against a second image frame, noting the position of a corresponding (matched) segment found in the second image frame and using the difference between the positions as an indication of motion. Often, the motion between two frames of an N-dimensional sequence is described as an N-dimensional vector. Thus, where the video sequence is a sequence of two-dimensional images, the motion of a segment S can be expressed by the two-dimensional vector u
S
=(x
S
, y
S
), where x
S
is the relative displacement of the segment in the horizontal direction and y
S
is the relative displacement of the segment in the vertical direction. Typically, the units of measurement for the displacements are in pixels.
One known method for digital signal pattern matching is the exhaustive search method. This computationally expensive method involves comparing a segment from a first frame against the pixels of a second image frame at each possible location of the corresponding segment in the second image frame, within a limited search area. This method is computationally expensive because the pixel color values (usually organized in a N-dimensional array, where N is the dimension of the images) of the segment are compared to candidate corresponding pixels about as many times as there are pixels in the second image frame.
Logically, this process can be described as follows. Suppose one of the pixels of the segment (or any other pixel with a fixed relationship to one or more of the pixels of the segment) is designated the segment reference pixel and one of the pixels of the image frame to which the segment is to be matched is designated the frame reference pixel. Then, each step of comparing is a process of overlaying the segment reference pixel on the frame reference pixel and then performing a calculation such as a sum of the differences of overlaying pixels. This step is then repeated for each possible frame reference pixel until the corresponding segment, or a best choice for the corresponding segment, is identified.
Where the calculation is the sum of the differences of overlaying pixels, the sum will be zero if an exact match occurs, i.e., if the segment is positioned over the image frame such that each pixel in the segment overlays a pixel in the image frame having the same pixel color value as the pixel in the segment. An acceptable match occurs when the sum of the absolute values of the differences (referred to herein as the L
l
norm) is less than or equal to some threshold. Lower L
l
norms indicate better matches.
The widely used video compression method of the Moving Picture Experts Group (MPEG) attempts to match segments comprising blocks of 16×16 pixels by placing each block at each possible location within an image frame, or portion thereof, and subtracting the pixel values. Once again, a match occurs when the sum of the absolute values of the differences between the pixel values is close to or equal to zero.
In other embodiments of the state of the art, the matching routines are not limited to the L
l
norm. Any form of minimizing norm is sufficient. This is mathematically known as the L
p
norm where P≧1.
The exhaustive search method is described below with reference to
FIGS. 1A and 1B
. In those figures, different colors are represented by different cross-hatching. Referring to
FIG. 1A
, a segment
10
has been identified and is to be matched against an image frame
11
(shown in FIG.
1
B).
FIG. 1B
shows an image frame
11
containing six segments, labeled segment
12
, segment
14
, segment
16
, segment
18
, segment
20
and segment
22
(the background).
In the matching process, segment
10
is overlaid on image frame
11
at a given position and the color values of each pixel of segment
10
are subtracted from the values of corresponding pixels in image frame
11
. In order to subtract pixel values, we assume a monochromatic image with linear color values; i.e., the difference between a pixel value of 30 and 31 is the same as the difference between a pixel value of 80 and 81. The monochromatic image is a function of the various color components of the original image. In another embodiment, motion matching routines are separately applied to each color component of the original image. Multiple possible matches can be generated in this manner. In this case, the intersection of the results is taken in order to determine the correct match. When the segment
10
is directly over a matching segment (segment
12
, in this case) of image frame
11
, then the sum of the absolute values of the differences will be zero or close t
Fodor Eniko
Prakash Adityo
Ratner Edward
Albert Philip H.
Mehta Bhavesh M.
Pulsent Corporation
Tabatabai Abolfazl
Townsend and Townsend / and Crew LLP
LandOfFree
Motion matching method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Motion matching method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion matching method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3152045