Method and system for generating polygonal boundary definitions for image objects
View Patent ↗Image objects within two-dimensional images are identified by locating boundary points that describe line segments that define a polygon outlining each object. Processing follows lines of pixels between boundary points to determine whether additional pixels are a part of the same image object by reference to a discriminator, such as color. Boundary points are thus identified for contiguous pixels and contiguous lines. Arm-like regions are identified by recursive analysis in a similar manner. The resulting boundary point list may serve to identify the image object, such as for labeling or tagging in web-based manuals, catalogs, and so forth.
1. A method for determining boundaries of image objects visible in a digitized two-dimensional image, the method comprising:
(a) identifying a first pixel of the image object as a target pixel;
(b) identifying additional pixels adjacent to the target pixel along line in a desired direction from the target pixel based upon a common quality between the pixels until a boundary pixel of the image object is reached;
(c) identifying a further boundary pixel in another line adjacent to but offset orthogonally from the line of step (b) by reference to the boundary pixel;
(d) repeating steps (b) and (c) using the further boundary pixel of step (c) as the target pixel of step (b) until no further adjacent pixels of the image object are identified; and
(e) storing lists of the left and right boundary pixels; and
(f) reversing either the left or right boundary pixel lists and concatenating the two to produce a single boundary pixel list that defines a series of line segments that describe a polygon outlining the image object.
2. The method of claim 1 , wherein the first pixel is a boundary pixel of the image object.
3. The method of claim 1 , wherein the desired direction is horizontal.
4. The method of claim 1 , further comprising identifying boundary pixels of contiguous, occluded regions of the image object by identifying pixels of lines adjacent to a line of identified image object pixels and repeating steps (b) and (C) using any one of the pixels of the line of identified image object pixels as the target pixel for such contiguous, occluded regions.
5. The method of claim 1 , further comprising reducing the boundary pixel list by eliminating intermediate pixels on the list lying in a line between other pixels on the list.
6. The method of claim 1 , further comprising reducing the boundary pixel list by eliminating pixels representing vertices of triangles defined by three sequential pixels on the list.
7. The method of claim 1 , wherein the common quality is color.
8. A method for determining boundaries of image objects visible in a digitized two-dimensional image, the method comprising:
(a) identifying a first boundary pixel of the image object at a upper leftmost position in the image object;
(b) identifying additional pixels of the image object in a first row with the first boundary pixel based upon a common quality between the pixels until a rightmost boundary pixel of the image object is reached in the first row;
(c) identifying a rightmost boundary pixel in a second row beneath the first row;
(d) identifying additional pixels of the image object in the second row based upon the common quality between the pixels until a leftmost boundary pixel of the image object is reached in the second row;
(e) identifying an additional leftmost boundary pixel of the image object in a third row beneath the second row;
(f) repeating steps (b) through (e) for the third and all lower rows until no further pixels of the image object are identified; and
(g) storing a list of the boundary pixels.
9. The method of claim 8 , wherein the first pixel is a boundary pixel of the image object.
10. The method of claim 8 , further comprising identifying boundary pixels of contiguous, occluded regions of the image object by identifying pixels of lines adjacent to a line of identified image object pixels and sequentially identifying boundary pixels of such contiguous occluded regions.
11. The method of claim 10 , wherein the boundary pixels of the contiguous, occluded regions are identified recursively during identification of the boundary pixels of a main image object region.
12. The method of claim 8 , further comprising reducing the boundary pixel list by eliminating intermediate pixels on the list lying in a line between other pixels on the list.
13. The method of claim 8 , further comprising reducing the boundary pixel list by eliminating pixels representing vertices of triangles defined by three sequential pixels on the list.
14. The method of claim 8 , wherein the common quality is color.
15. A method for determining boundaries of image objects visible in a digitized two-dimensional image, the method comprising:
identifying a first boundary pixel of the image object and additional pixels of the image object in a line with the first boundary pixel based upon a common quality between the pixels until a second boundary pixel is identified at an end of the line opposite the first boundary pixel; and
sequentially identifying image boundary pixels in adjacent lines of the image by identifying adjacent pixels in lines based upon the common quality; and
storing a list of the boundary pixels.
16. The method of claim 15 , further comprising identifying boundary pixels of contiguous, occluded regions of the image object by identifying pixels of lines adjacent to a line of identified image object pixels and sequentially identifying boundary pixels of such contiguous occluded regions.
17. The method of claim 16 , wherein the boundary pixels of the contiguous, occluded regions are identified recursively during identification of the boundary pixels of a main image object region.
18. The method of claim 15 , further comprising reducing the boundary pixel list by eliminating intermediate pixels on the list lying in a line between other pixels on the list.
19. The method of claim 15 , further comprising reducing the boundary pixel list by eliminating pixels representing vertices of triangles defined by three sequential pixels on the list.
20. The method of claim 15 , wherein the common quality is color.