Method and apparatus for determining boundaries of graphic regions

• US 4,788,538 A
• Filed: 04/24/1987
• Issued: 11/29/1988
• Est. Priority Date: 11/17/1986
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: Lotus Development Corporation (International Business Machines Corporation)
• Inventors: Gross, William T., Rolfe, David A., Klein, Stephen A., Gross, Lawrence S.
• Primary Examiner(s): Brigance, Gerald L.
• Application Number:
  US07/042,161
• Time in Patent Office: 585 Days
• Field of Search: 340/703, 340/706, 340/709, 340/710, 340/723, 340/728, 340/747, 340/789
• US Class Current: 345/418
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

The present invention provides apparatus and methods for determining the boundaries of arbitrarily shaped regions on a computer display system having a central processing unit (CPU). The CPU is coupled to a display having a plurality of selectively enabled and disabled display elements arranged in a matrix, whereby each display element is identified by a unique X,Y address. A memory coupled to the CPU includes a plurality of memory cells, wherein the cells correspond to a display element on the display. An initial X,Y address is selected on the display by a user employing a cursor control to identify an area on the display where the boundaries of a region are to be determined. The initial X,Y address selected by the user is defined as a seed cell. The CPU determines if the initial seed cell corresponds to a disabled memory cell and blank (disabled) display element, and in such event increments the initial X,Y address to search outwardly a predetermined maximum distance to adjacent memory cells until an enabled (non-blank) cell is located. This enabled cell is set as a new seed cell. The CPU then searches radially outward in M directions from the new seed cells X,Y address for N consecutive disabled (blank) memory cells and sets in each of these directions the last non-blank (enabled) memory cell prior to the N consecutive disabled cells, as boundary cells. An initial rectangular region is defined through at least two of these boundary cells, and the CPU determines if P consecutive rows and columns of blank (disabled) memory cells bound the initial rectangular region. If not, the CPU selectively extends the boundaries of the initial rectangular region in X and Y directions until the region is bounded by P consecutive rows and columns of disabled cells. Accordingly, the boundaries of a region on a display are determined.

Claims

1. A computer display system having a central processing unit (CPU) coupled to display means including a display, said display having a plurality of selectively enabled and disabled display elements arranged in a matrix, such that each display element is identified by a unique X, Y address, comprising:

memory means coupled to said CPU for storing a plurality of binary quantities, each of said binary quantities disposed in a memory cell corresponding to a display element, said binary quantities defining regions on said display;

cursor control means coupled to said CPU for selecting an initial X, Y address on said display, and corresponding memory cell in said memory means, to identify an area on said display where the boundaries of a region are to be determined, said initial cell being defined as a seed cell;

logic means coupled to said CPU for determining if said initial X, Y address corresponds to a disabled memory cell, and in such event said logic means incrementing said initial X, Y address to search outwardly to adjacent memory cells until an enabled cell is located, said enabled cell then being defined as the new seed cell;

said CPU searching radially outward in M directions from the X, Y address of said seed cell for N consecutive disabled memory cells, and said logic means setting in each of said directions, the last enabled memory cell prior to said N consecutive disabled cells, as boundary cells;

said logic means defining an initial rectangular region through at least two of said boundary cells;

said logic means determining if P consecutive rows and columns of disabled memory cells bound said initial rectangular region, said CPU selectively extending the boundaries of said initial region in X and Y directions until said region is bounded by P consecutive rows and columns of disabled cells;

whereby the boundaries of a region on said display are determined.

2. The computer display system as defined by claim 1, further including input means coupled to said CPU for inputting into said memory means data representative of at least one region comprising a plurality of binary quantities.

3. The computer display systems as defined by claim 2, wherein said logic means searches outwardly by spiraling said search from said seed cell.

4. The computer display system as defined by claim 3, wherein M is equal to eight (8) directions extending radially from said seed cell.

5. The computer display system as defined by claim 4, wherein said initial rectangular region is defined through the uppermost left and lowermost right boundary cells.

6. The computer display system as defined by claim 5, wherein N is equal to two (2) disabled memory cells.

7. The computer display system as defined by claim 6, wherein P is equal to two (2) consecutive rows and columns of disabled cells.

8. The computer display system as defined by claim 7, wherein input means comprises a keyboard.

9. A method for determining the boundaries of a region on a computer controlled display system, said display system including a central processing unit (CPU) coupled to a display, said display having a plurality of selectively enabled and disabled display elements arranged in a matrix, such that each display element is identified by a unique X, Y address, comprising the steps of:

providing memory means coupled to said CPU for storing a plurality of binary quantities, each of said binary quantities disposed in a memory cell corresponding to a display element, said binary quantities defining regions on said display;

positioning a cursor using cursor control means coupled to said CPU for selecting an initial X, Y address on said display, and corresponding memory cell in said memory means, to identify an area on said display where the boundaries of a region are to be determined, said initial cell defined as a seed cell;

determining if said initial X, Y address corresponds to a disabled memory cell, and if so, incrementing said initial X, Y address to search outwardly to adjacent memory cells until an enabled cell is located and setting said located enabled cell as the new seed cell;

searching radially outward in M directions from the X, Y address of said seed cell for N consecutive disabled memory cells, and setting, for each of said directions, the last enabled memory cell prior to said N consecutive disabled cells as boundary cells;

defining an initial rectangular region through at least two of said boundary cells;

determining if P consecutive rows and columns of disabled memory cells bound said initial rectangular region, and selectively extending the boundaries of said initial regions in X and Y directions until said region is bounded by P consecutive rows and columns of disabled cells;

whereby the boundaries of a region on said display are determined.

10. The method as defined by claim 9, further including the step of inputting at least one region comprising a plurality of binary quantities into said memory means.

11. The method as defined by claim 10, wherein said step of searching outwardly for an enabled memory cell comprises the step of:

searching all immediately adjacent memory cells to said seed cell by spiraling said search from said seed cell.

12. The method as defined by claim 11, wherein M is equal to eight (8) directions extending radially from said seed cell.

13. The method as defined by claim 12, wherein said initial rectangular region is defined through the uppermost left and lowermost right boundary cells.

14. The method as defined by claim 13, wherein N is equal to two (2) consecutive disabled memory cells.

15. The method as defined by claim 14, wherein P is equal to two (2) consecutive rows and columns of disabled cells.

16. A method for determining the boundaries of a region on a computer display, said display having a plurality of display cells identified by X, Y addresses on said display, each of said cells being selectively filled with data or left blank, comprising the steps of:

providing memory means coupled to a central processing unit (CPU) and said display, for storing data for display in a memory cell corresponding to a display cell, said data defining regions on said display;

positioning a cursor using cursor control means coupled to said CPU for selecting an initial display cell on said display, and corresponding memory cell in said memory means, to identify an area on said display where the boundaries of a region are to be determined, said initial display cell defined as a seed cell;

determining if said initial seed cell corresponds to a blank display cell and memory cell, and if so, incrementing said initial X, Y address to search outwardly to adjacent cells until a filled cell is located, and setting said located filled cell as the new seed cell;

searching radially outward in M directions from the X, Y address of said seed cell for N consecutive blank cells, and setting, for each of said directions, the last filled cell prior to said N consecutive empty cells as boundary cells;

defining an initial rectangular region through at least two of said boundary cells;

determining if P consecutive rows and columns of empty cells bound said initial rectangular region, and selectively extending the boundaries of said initial region in X and Y directions until said region is bounded by P consecutive rows and columns of empty cells;

whereby the boundaries of a region on said display are determined.

17. The method as defined by claim 16, further including the step of inputting data comprising at least one region into said memory means.

18. The method as defined by claim 17, wherein said step of searching outwardly for an filled memory cell comprises the step of:

searching all immediately adjacent memory cells to said seed cell by spiraling said search from said seed cell.

19. The method as defined by claim 18, wherein M is equal to eight (8) directions extending radially from said seed cell.

20. The method as defined by claim 19, wherein said initial rectangular region is defined through the uppermost left and lowermost right boundary cells.

21. The method as defined by claim 20, wherein N is equal to two (2) consecutive disabled memory cells.

22. The method as defined by claim 21, wherein P is equal to two (2) consecutive rows and columns of disabled cells.

23. A computer display system having a central processing unit (CPU) coupled to display means including a display, said display having a plurality of display cells identified by X,Y addresses on said display, each of said cells being selectively filled with data or left blank, comprising:

memory means coupled to said CPU for storing data for display in a memory cell corresponding to a display cell, said data defining regions on said display;

cursor control means coupled to said CPU for selecting an initial display cell on said display, and corresponding memory cell in said memory means, to identify an area on said display where the boundaries of a region are to be determined, said initial display cell defined as a seed cell;

said CPU determining if said initial seed cell corresponds to a blank display cell and memory cell, and if so, incrementing said initial X,Y address to search outwardly to adjacent cells until a filled cell is located, and setting said located filled cell as the new seed cell;

said CPU searching radially outward in M directions from the X,Y address of said seed cell for N consecutive blank cells, and setting, for each of said directions, the last filled cell prior to said N consecutive empty cells as boundary cells;

said CPU defining an initial rectangular region through at least two of said boundary cells, and determining if P consecutive rows and columns of empty cells bound said initial rectangular region, and selectively extending the boundaries of said initial region in X and Y directions until said region is bounded by P consecutive rows and columns of empty cells;

whereby the boundaries of a region on a display are determined.

24. The computer display system as defined by claim 23, further including input means coupled to said CPU for inputting into said memory means data representative of at least one region comprising a plurality of binary quantities.

25. The computer display systems as defined by claim 24, wherein said logic means searches outwardly by spiraling said search from said seed cell.

26. The computer display system as defined by claim 25, wherein M is equal to eight (8) directions extending radially from said seed cell.

27. The computer display system as defined by claim 26, wherein said initial rectangular region is defined through the uppermost left and lowermost right boundary cells.

28. The computer display system as defined by claim 27, wherein N is equal to two (2) disabled memory cells.

29. A computer display system having a central processing unit (CPU) coupled to display means including a display, said display having a plurality of selectively enabled and disabled display elements arranged in a matrix, such that each display element is identified by a unique X, Y address, comprising:

memory means coupled to said CPU for storing a plurality of binary quantities, each of said binary quantities disposed in a memory cell corresponding to a display element, said binary quantities defining regions on said display;

cursor control means coupled to said CPU for selecting an initial X, Y address on said display, and corresponding memory cell in said memory means, to identify an area on said display where the boundaries of a region are to be determined, said initial cell being defined as a seed cell;

logic means coupled to said CPU for determining if said initial X,Y address corresponds to a disabled memory cell, and in such event said logic means incrementing said initial X, Y address to search outwardly a pre-determined maximum distance to adjacent memory cells until an enabled cell is located, said enabled cell then being defined as the new seed cell;

said CPU searching radially outward in M directions from the X, Y address of said seed cell for N consecutive disabled memory cells, and said logic means setting in each of said directions, the last enabled memory cell prior to said N consecutive disabled cells, as boundary cells;

said logic means determining the maximum and minimum values of X, Y coordinates of said boundary cells and said seed cell, and defining maximum (X_MAX, Y_MIN) and minimum (X_MIN, Y_MIN) initial points from said maximum and minimum values, respectively;

said logic means defining an initial rectangular region through said maximum and minimum points;

said logic means determining if P consecutive rows and columns of disabled memory cells bound said initial rectangular region, said CPU selectively extending the boundaries of said initial region in X and Y directions until said region is bounded by P consecutive rows and columns of disabled cells;

whereby the boundaries of a region on said display are determined.

30. The computer display system as defined by claim 29, wherein M is equal to 8, and radial vectors are defined from said seed cell X, Y coordinate (X_s Y_s) to each of said boundary cells, said vectors being numbered A through H clockwise, beginning from the positive X axis.

31. The computer display systems as defined by claim 30, wherein said initial maximum and minimum points are defined by the following expression:

Maximum Point (X_MAX, Y_MAX);

Where

space="preserve" listing-type="equation">X.sub.MAX =MAX(X.sub.S, X.sub.H, X.sub.A, X.sub.B)

space="preserve" listing-type="equation">Y.sub.MAX =MAX(Y.sub.S, Y.sub.B, Y.sub.C, Y.sub.D)

Minimum Point (X_MIN, Y_MIN);

Where

space="preserve" listing-type="equation">X.sub.MIN =MIN(X.sub.S, X.sub.D, X.sub.E, X.sub.F)

space="preserve" listing-type="equation">Y.sub.MIN =MIN(Y.sub.S, Y.sub.F, Y.sub.G, Y.sub.H)

32. A method for determining the boundaries of a region on a computer controlled display system, said display system including a central processing unit (CPU) coupled to a display, said display having a plurality of selectively enabled and disabled display elements arranged in a matrix, such that each display element is identified by a unique X, Y address, comprising the steps of:

providing memory means coupled to said CPU for storing a plurality of binary quantities, each of said binary quantities disposed in a memory cell corresponding to a display element, said binary quantities defining regions on said display;

positioning a cursor using cursor control means coupled to said CPU for selecting an initial X, Y address on said display, and corresponding memory cell in said memory means, to identify an area on said display where the boundaries of a region are to be determined, said initial cell defined as a seed cell;

determining if said initial X, Y address corresponds to a disabled memory cell, and if so, incrementing said initial X, Y address to search outwardly a predetermined maximum distance to adjacent memory cells until an enabled cell is located and setting said located enabled cell as the new seed cell;

searching radially outward in M directions from the X, Y address of said seed cell for N consecutive disabled memory cells, and setting, for each of said directions, the last enabled memory cell prior to said N consecutive disabled cells as boundary cells;

defining maximum (X_MAX, Y_MAX) and minimum (X_MIN, Y_MIN) initial points from the maximum and minimum X, Y values of said boundary cells and said seed cell, respectively;

defining an initial rectangular region through said initial maximum and minimum points;

determining if P consecutive rows and columns of disabled memory cells bound said initial rectangular region, and selectively extending the boundaries of said initial regions in X and Y directions until said region is bounded by P consecutive rows and columns of disabled cells;

whereby the boundaries of a region on said display are determined.

33. The method as defined by claim 32, further including the stop of inputting at least one region comprising a plurality of binary quantities into said memory means.

34. The method as defined by claim 33, wherein M is equal to 8, and radial vectors are defined from said seed cell X, Y coordinate (X_s Y_s) to each of said boundary cells, said vectors being numbered A through H clockwise, beginning from the positive X axis.

35. The computer display systems as defined by claim 34, wherein said initial maximum and minimum points are defined by the following expression:

Maximum Point (X_MAX, Y_MAX);

Where

space="preserve" listing-type="equation">X.sub.MAX =MAX(X.sub.S, X.sub.H, X.sub.A, X.sub.B)

space="preserve" listing-type="equation">Y.sub.MAX =MAX(Y.sub.S, Y.sub.B, Y.sub.C, Y.sub.D)

Minimum Point (X_MIN, Y_MIN);

Where

space="preserve" listing-type="equation">X.sub.MIN =MIN(X.sub.S, X.sub.D, X.sub.E, X.sub.F)

space="preserve" listing-type="equation">Y.sub.MIN =MIN(Y.sub.S, Y.sub.F, Y.sub.G, Y.sub.H).