Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-08-27
2002-04-09
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Template matching
C707S793000
Reexamination Certificate
active
06370270
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to applications involving sampling of objects, such as images, or placement or arrangement of objects, such as sensors, using Low Discrepancy sequences, wherein the use of Low Discrepancy sequences provides improved efficiency. The present invention includes, but is not limited to, methods for sampling images, acquiring image statistics, locating a known object in an image, estimating the motion of objects in successive acquired images, determining placement locations of sensors or other objects, and determining points to be used in a grid/mesh design.
DESCRIPTION OF THE RELATED ART
In many applications it is necessary or desired to sample an image to generate sample pixels which characterize the image, rather than using every pixel of the image. These sample pixels can then be used in performing calculations and comparisons associated with the image. Sampling an image may be very advantageous in applications such as pattern matching, image reconstruction, and motion estimation.
In addition, many applications require placement of multiple objects, such as sensors, within a given area. Here it is greatly desirable to optimally place the sensors for best coverage of the area, i.e., to place the sensors in locations which maximize reception. This allows usage of a lesser number of sensors to cover an area, thus reducing cost.
Prior art techniques for sampling an image and for determining placement locations for objects have utilized either a homogeneous sampling, such as grid-based sampling, or have utilized random points or pixels within the placement or image area. However, each of the above prior art techniques operates to select a subset of the total available pixels or total possible locations which does not necessarily best represent or characterize the image or placement objectives.
For example, an improved system and method is desired for characterizing an image with a fewer number of sample pixels. Image characterization is used, for example, in performing correlation based pattern matching. Pattern matching applications often apply an image sampling method to characterize the temple image with a lesser number of sample pixels. Pattern matching applications are used to find instances of the template image or image object in a larger target image. Examples of pattern matching applications include machine vision applications such as process monitoring, feedback control, and laboratory automation; image and video compression; and jitter compensation in video cameras; among others.
Many other operations require and/or desire a more efficient characterization of images. Examples include methods of acquiring image statistics, such as mean gray-level value or standard deviation of gray-levels, methods for locating a known object in an image, methods for estimating the motion of objects in successive acquired images, and methods for color matching, among others. Therefore, an improved system and method is desired for characterizing an image. More particularly, an improved system and method is desired for characterizing or selecting samples or pixels from a template image which best represent the template image with the fewest samples possible.
As discussed above, in many applications it is desired to determine the optimal placement locations for sensors within a given area. For example, a CCD (charge coupled device) sensor in a camera comprises an array of light sensitive electronic capacitors (CCD sensor elements) that are typically placed in a grid based pattern. If fewer CCD sensors elements could be used, the cost of the CCD sensor would be lessened. Placement of CCD sensor elements according to a uniform grid or random placement procedure may not provide the optimal locations for the sensors. Therefore an improved method is desired for determining the placement locations for CCD sensor elements. Other applications where the optimal placement of sensors is desired include the placement of temperature sensors and microphones in a planar array, as well as placement of transmitters/receivers (sensors) for radar, sonar, topography, and magnetic resonance imaging applications.
Meshes are used in many engineering applications including mechanical, structural, and design applications. Prior art methods typically use a grid based mesh, wherein the vertices of the mesh are placed according to a grid pattern. If a fewer number of vertices is used, while achieving substantially the same results, computer memory, time, and other resources are reduced. Therefore an improved method for determining mesh vertices is desired.
Therefore, improved systems and methods are desired for optimally sampling objects, such as pixels in an image; for optimally placing or arranging objects, such as sensors; and for optionally determining locations of vertices in a grid or mesh design.
SUMMARY OF THE INVENTION
The present invention comprises a system and method for improved image characterization, object placement, and mesh design utilizing Low Discrepancy sequences. The present invention may be applied specifically to methods of image characterization, pattern matching, acquiring image statistics, object location, image reconstruction, motion estimation, object placement, sensor placement, and mesh design, among others. While these applications are discussed specifically and in detail, they are not intended to limit the use of Low Discrepancy sequences in other applications.
In a first embodiment, the present invention comprises a system and method for performing image characterization using Low Discrepancy sequences. The image characterization is preferably performed in a computer system. The image is received by and/or stored in the computer system and comprises a first plurality of pixels. The system and method comprises sampling the image using a Low Discrepancy sequence, also referred to as a quasi-random sequence, to determine a plurality of sample pixels in the image which characterize the image. The Low Discrepancy sequence is designed to produce sample points which maximally avoid one another, i.e., the distance between any two sample points is maximized. Also, the Low Discrepancy sequence sampling results in fewer points and provides a better characterization of the image than a random sequence sampling or a uniform sampling. Examples of the Low Discrepancy sequence include Halton, Sobol, Faure, and Niederreiter sequences.
Pattern matching is one embodiment in which image characterization using Low Discrepancy sequences may provide a significant increase in efficiency. In a pattern matching application, a template image is received and/or stored in the computer system and comprises a first plurality of pixels. According to one pattern matching embodiment, the system and method first comprises sampling the template image using a Low Discrepancy sequence, as described above. The sampling or characterization of the template image is preferably performed off-line prior to receipt of a target image. Thus the sampling or characterization of the template image is preferably not constrained by real time requirements. After the template image is sampled or characterized, the target image is preferably acquired by the computer system, through a camera or any other image capture method. The method then performs pattern matching using the sample pixels of the template image and the target image to determine zero or more locations of the template image in the target image.
Image characterization using Low Discrepancy sequences may also be used in other applications, such as acquiring image statistics, locating a known object in an image, estimating motion vectors indicating movement of objects in successive images, image reconstruction, image compression, and color matching, among others.
In a second embodiment, the present invention comprises a system and method for optimally placing sensors in a 2D array. In this embodiment, a computer system generates a Low Discrepancy sequence for the desired placement application. The computer system then selects l
DeKey Samson
Nair Dinesh
Vazquez Nicolas
Wenzel Lothar
Azarian Seyed
Hood Jeffrey C.
Johns Andrew W.
National Instruments Corporation
LandOfFree
System and method for sampling and/or placing objects using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for sampling and/or placing objects using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for sampling and/or placing objects using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2916590