Image analysis – Image transformation or preprocessing – Walsh – hough – or hadamard transform
Reexamination Certificate
2001-01-04
2004-11-30
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image transformation or preprocessing
Walsh, hough, or hadamard transform
C382S190000, C382S199000, C345S418000
Reexamination Certificate
active
06826311
ABSTRACT:
TECHNICAL FIELD
The present invention relates in general to object detection and tracking, and more particularly to a methods and arrangements for use in detecting visible features using a Hough Transform.
BACKGROUND
Applications for automatic digital object detection and tracking, image registration, pattern recognition and computer vision analysis are becoming increasingly important for providing new classes of services to users based on assessments of the object's presence, position, trajectory, etc. These assessments allow advanced and accurate digital analysis (such as pattern recognition, motion analysis, etc.) of the objects in a scene, for example, objects in a sequence of images of a video scene. Plural objects define each image and are typically nebulous collections of pixels, which satisfy some property.
These pixels are often the result of some logical operation, such as, e.g., filtering, equalization, edge or feature detection, that is applied to the raw input image data. Hence, objects typically occupy one or more regions within each image. In a video scene, these objects may change their relative position in subsequent images or frames depicting the video scene. These objects are considered moving objects, which form motion within a video scene and can be automatically detected and tracked with various techniques.
The Hough Transform is a well-known computer vision algorithm that can be implemented to robustly detect a wide variety of features such as lines, circles, and anything else that can be readily parameterized or otherwise cast in terms of a discrete popularity algorithm. Unfortunately, the Hough transform tends to be computationally intensive. Many personal computer (PC) microprocessors are unable to provide the requisite processing capability usually associated with the Hough Transform. This is more true for video that often requires frame rates of about twenty frames or more per second, novel user interfaces using computer vision such as the puppeteering of avatars in online scenarios (e.g., during massively multiplayer games, virtual teleconferencing, and the like), and feature extraction for subsequent image processing (e.g., image registration).
Thus, to support such capabilities there is a need for improved methods and arrangements that support the use of Hough transforms, and/or any similar transform. Preferably, the improved methods and arrangements will be suitable for implementation in a PC or like device, and/or otherwise realizable in a cost effective package.
SUMMARY
The above stated needs and other are met by various improved methods and arrangements that, in accordance with certain aspects of the present invention, leverage the dedicated hardware of a graphics circuit (e.g., a 3D graphics accelerator card, etc.) to provide a portion of the data processing associated with the Hough transform.
This may be accomplished, for example, by gathering observations that can be mapped into a parameter space of a desired feature or features, quantizing the parameter space of the desired feature(s), and allocating an accumulator and initializing it to zero for each discrete quantized parameter combination. Then, for each observation incrementing all of the accumulators that correspond to parameter combinations that might have produced the observation, and finding maxima in the quantized parameter array.
Per the various methods and arrangements provided herein, these basic processes are selectively performed by a general-purpose processor along with the dedicated hardware of the graphics circuit. By way of example, in certain implementations the dedicated graphics hardware provides an alpha-blending capability that can be leveraged to record votes associated with the Hough Transform.
REFERENCES:
patent: 5054098 (1991-10-01), Lee
patent: 5220621 (1993-06-01), Saitoh
patent: 5430810 (1995-07-01), Saeki
patent: 5801970 (1998-09-01), Rowland et al.
patent: 5864779 (1999-01-01), Fujimoto
patent: 5960371 (1999-09-01), Saito et al.
patent: 6111993 (2000-08-01), Matsunaga
patent: 6263089 (2001-07-01), Otsuka et al.
patent: 6496187 (2002-12-01), Deering et al.
Hsiang-Ling Li and Chaitali Chakrabarti (Hardware Design of a 2-D Motion Estimation System based on the Hough Transform, IEEE 1998).
Lee & Hayes PLLC
Mehta Bhavesh M.
Microsoft Corporation
Patel Kanji
LandOfFree
Hough transform supporting methods and arrangements does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hough transform supporting methods and arrangements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hough transform supporting methods and arrangements will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3337366