Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1998-02-20
2001-04-10
Mehta, Bhavesh (Department: 2721)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S276000, C345S440000
Reexamination Certificate
active
06215915
ABSTRACT:
RESERVATION OF COPYRIGHT
The disclosure of this patent document contains material that is subject to copyright protection. The owner thereof has no objection to facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The human mind is uncannily adept at identifying patterns and images. It can readily recognize most objects, regardless of how they are oriented. Thus, even those young of years or lacking in mental capacity can recognize a familiar piece of candy at any angle of presentation.
What comes to the mind so easily can be painstakingly difficult to teach a computer. Machine vision is one example. Software engineers have long labored to program these machines to identify objects in digital images. Though these efforts have paid off, the going has been slow. It is fair to estimate that billions of lines of programming instructions have been thrown away in the effort.
Discarded along the way were the early machine vision programs that were each written for a specific application. These programs were abandoned as modular programming came to the fore. Software engineering, in general, and machine vision, in particular, benefitted from the new thinking. Libraries were developed containing hundreds of small, reusable image analysis algorithms that could be invoked on a mix-and-match basis. Relying on these, software engineers began to construct shorter, more reliable and more easily debugged programs.
Common to these libraries is the so-called affine transformation tool, which resizes and rotates images. It is typically used in preprocessing, to prepare an image for automated analysis by other machine vision tools.
Affine transforms can be used, for example, to simplify the recognition of part numbers stamped on articles on a conveyor belt. Once the overall position and orientation of each part is determined, e.g., using coarse image processing techniques, an affine transform is applied to “artificially” rotate and size the region expected to contain the stamping. That portion of the image can then be interpreted through the use of character recognition software. The use of an affine transform in this manner is preferable, for example, to physically moving and reorienting the article, e.g., with a robotic arm.
Conventional prior art techniques suggest that affine transforms can be accomplished by mapping a source image into a destination image in a single pass. For every pixel location in the destination image, a corresponding location in the source image is identified. In a simplistic example, every pixel coordinate position in the destination image maps directly to an existing pixel in the source. Thus, for example, the pixel at coordinate (4,10) in the source maps to coordinate (2,5) in the destination; the pixel at (6,10) in the source, to (3,5) in the destination; and so on.
Reality is not so easy. Rarely do pixels in the source map directly to pixel positions in the destination. Thus, for example, a pixel at coordinate (4,10) in the source may map to a location (2.5, 5.33) in the destination. This can be problematic insofar as it requires interpolation to determine appropriate pixel intensities for the mapped coordinates. In the example, an appropriate intensity might be determined as a weighted average of the intensities for the source pixel locations (2,5), (3,5), (2,6), and (3,6).
The interpolation of thousands of such points is time consuming, even for a computer. Conventional affine transform tools must typically examine at least four points in the source image to generate each point in the destination image. This is compounded for higher-order transformations, which can require examination of many more points for each interpolation.
Although prior art has suggested the use of multiple passes (i.e., so-called separable techniques) in performing specific transformations, such as rotation, no suggestion is made as to how this might be applied to general affine transforms, e.g., involving simultaneous rotation, scaling, and skew.
Accordingly, an object of this invention is to provide improved systems for image processing and, more particularly, improved methods and apparatus for general affine transformation, e.g., for the simultaneous rotation, translation and scaling of images.
Another object of the invention is to provide such methods and apparatus as permit rapid analysis of images, without undue consumption of resources.
Still another object of the invention is to provide such methods and apparatus as are readily adapted to implementation conventional digital data processing apparatus, e.g., such as those equipped with commercially available superscalar processors—such as the Intel Pentium MMX or Texas Instruments C80 microprocessors.
SUMMARY OF THE INVENTION
The foregoing objects are among those attained by the invention, which provides methods and apparatus for separable, general affine transformation. Thus, the invention permits an image to be concurrently rotated, scaled, translated, skewed, sheared, or otherwise transformed via a sequence of one-dimensional transformations (or passes). In an exemplary aspect, the invention provides methods for general affine transformation of an image in two dimensions by generating an “intermediate” image via affine transformation of the source along a first axis. The intermediate image is then subjected to affine transformation along a second axis, e.g., perpendicular to the first. The resultant image may be used in place of that which would be produced by a single two-dimensional transformation of the source image (e.g., in a single pass).
According to related aspects of the invention, there are provided methods as described above in which the first one-dimensional transformation determines a mapping between coordinates in the intermediate image and those in the source image. Preferably, the coordinates in the intermediate image lie at integer coordinate positions, e.g., coordinate positions such as at (1, 1), (1, 2), and so forth. Though the mapped locations in the source image do not necessarily lie at integer coordinate positions, they advantageously include at least one integer coordinate, e.g., coordinate positions such as (1, 1.5), (2, 4.25), (3, 3.75), and so forth.
Once the mappings of the first one-dimensional transformation are determined (or after each one has been determined), the method determines an intensity value for the pixel at each coordinate in the intermediate image. This is done by interpolating among the intensities of the pixels in the region neighboring the corresponding or mapped coordinate in the source image. Because the coordinate locations in the intermediate image are generated in sequences along a first axis, and because the mapped locations have at least one integer coordinate, interpolations are greatly simplified.
With the second one-dimensional transformation, the method similarly determines a mapping between pixel coordinates in a destination image and those of the intermediate image. This transformation proceeds as described above, albeit with sequences of coordinate locations that vary along a second axis, e.g., orthogonal to the first.
According to further aspects of the invention, general affine transformations are effected in accord with the mathematical relation:
[
x
s
y
s
]
=
M
·
[
x
d
y
d
]
+
[
x
o
y
o
]
M
=
[
e
11
e
12
e
21
e
22
]
where
(x
d
, y
d
) represents a coordinate in the destination image;
(x
s
, y
s
) represents a coordinate in the source image;
(x
o
, y
o
) is an offset to be effected by the transformation; and
M is a transformation matrix.
According to further aspects of the invention, the transformation matrix M is decomposed into left and right triangular matrices (otherwise referred to as upper and lower matrices, U and L, respectively) in accord with the following mathematical relation:
M
=
L
·
U
[
e
11
e
12
e
21
e
22
]
=
[
l
11
0
l
21
l
22
Cognex Corporation
Mehta Bhavesh
Patel Kanji
Powsner David J.
Weinzimmer Russ
LandOfFree
Image processing methods and apparatus for separable,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing methods and apparatus for separable,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing methods and apparatus for separable,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2474442