Image analysis – Image segmentation
Reexamination Certificate
2002-01-31
2004-02-10
Johns, Andrew W. (Department: 2621)
Image analysis
Image segmentation
C382S286000
Reexamination Certificate
active
06690823
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to processing image and video data. More particularly, the present invention relates to partitioning an area of an image or video frame into sub-areas.
2. Description of the Background Art
In image and video processing, it is often desirable to divide an area of an image into sub-areas to facilitate processing. For example, for discrete cosine transform (DCT) processing, an image is typically divided into blocks, and DCT is applied to those blocks. When more specific shape information regarding regions within an image is available, then it makes sense to take advantage of the shape information, for example, for coding efficiency, improved filtering, matching, and so on. However, sometimes such regions may be too large or awkwardly shaped to process efficiently. Dividing such large or awkwardly shaped regions into sub-regions that reflect some of the geometric information available regarding the region would be highly desirable.
One example where such large or awkwardly shaped regions often arises is segment-based motion compensation where exposed areas are created. For example, as an object or segment moves from frame to frame, previously hidden areas become exposed. These exposed areas are typically arbitrarily-shaped and non-uniform. Hence, encoding exposed areas is problematic and typically rather inefficient. A solution dealing with exposed areas may also have wider applicability to other similar or related tasks in image processing.
SUMMARY
In accordance with one embodiment of the invention, a processing method and apparatus is provided for partitioning areas of an image. The partitioning creates sub-areas in shapes and sizes that may be effectively dealt with and efficiently compressed. The partitioning advantageously divides an arbitrarily shaped area by “pinching,” “slicing,” and/or “cleaving” the area into manageable sub-areas to facilitate further processing. Such pinching, slicing, and/or cleaving may be applied to the area in any order.
In accordance with another embodiment of the invention, a processing method and apparatus is provided for partitioning a bounded area into sub-areas by determining pinch cuts located in narrow regions near rapid changes in area width, and dividing the area into sub-areas separated by the pinch cuts. The pinch cuts advantageously facilitate further processing by separating either a narrow region from a wide region or two wide regions from each other.
In accordance with another embodiment of the invention, a processing method and apparatus is provided for placing slice cuts to partition a bounded two-dimensional area. The method and apparatus determines a medial axis comprising at least one medial line segment approximately midway between two boundary line segments, and places the slices approximately perpendicular to the medial line segment and spaced approximately evenly along the medial line segment. The slice cuts advantageously divide elongated areas into sub-areas that are typically more efficient to further process.
In accordance with another embodiment of the invention, a method and apparatus is provided for processing points in a bounded area to locate a medial axis. The method and apparatus determines a nearest boundary point outside the area corresponding to each point inside the area, finds adjacent points inside the area which have different corresponding nearest boundary points separated by at least a threshold arc length, generates paths between said adjacent points with different corresponding nearest boundary points, and locates the medial axis from amongst said paths. Locating a medial axis advantageously facilitates determination of the pinch and slice cuts for partitioning arbitrarily-shaped areas.
In accordance with another embodiment of the invention, an electronically-implemented method and apparatus is provided for processing a bounded two-dimensional area in an array of points to determine, for each point inside the area, a nearest boundary point outside the area as measured by Euclidean distances. This technique based on Euclidean distances may be considered to be superior to prior techniques based on Manhattan distances. The Euclidean distances advantageously facilitate locating the medial axis.
REFERENCES:
patent: 4183013 (1980-01-01), Agrawala et al.
patent: 4896279 (1990-01-01), Yoshida
patent: 5319720 (1994-06-01), Yokoyama et al.
patent: 5889892 (1999-03-01), Saito
patent: 6307964 (2001-10-01), Lin et al.
patent: WO 00/64167 (2000-10-01), None
patent: WO 00/77735 (2000-12-01), None
John C. Russ, The image processing handbook; pp. 463-465, 1995, CRC Press, Inc., Boca Raton, Florida.
Holt Gary R.
Kita David B.
Ratner Edward
Johns Andrew W.
Okamoto & Benedicto LLP
PTS Corporation
LandOfFree
Method and apparatus for partitioning an arbitrarily-shaped... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for partitioning an arbitrarily-shaped..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for partitioning an arbitrarily-shaped... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3336418