Method and system for processing a two-dimensional image in a microprocessor

• US 4,894,646 A
• Filed: 11/19/1987
• Issued: 01/16/1990
• Est. Priority Date: 03/30/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ryman, Arthur G.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US07/122,827
• Time in Patent Office: 789 Days
• Field of Search: 340/747, 340/731, 340/727, 340/723, 340/791, 364/521, 364/522
• US Class Current: 345/556
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06T 1/60 Memory management

Abstract

An image processing system and a method for manipulating images in an image processing system where each image in the system is subdivided into a plurality of sub-images which are processed independently of one another. Control of each image and sub-image is maintained by means of a view state word or table so that only those portions of an image which are being actively processed require modification of their view state. The images stored in the system are maintained in a secondary store and only portions of the image are available for manipulation at any one time in a primary store. Manipulation of sub-images is determined by a modified Least Recently Used algorithm which minimizes data swaps between the primary and secondary stores.

Claims

1. An image processing system including a display device, a first store and a second store,

means for loading digital representations of images to be displayed into said first and second stores, each said image being subdivided into a plurality of sub-images,

a table associated with each image and each sub-image, each said table associated with each image defining view characteristics for said associated image, each said table for each said sub-image defining view characteristics for said associated sub-image,

means for selecting a view of a stored image for display on said display device as a viewed image having view characteristics, said selecting means accessing said view of said stored image by selecting sub-images for display, said selecting means including means for comparing said view characteristics of said viewed image to said view characteristics of a selected sub-image and means for changing said view characteristics of said selected sub-image to the view characteristics of said viewed image before displaying said sub-image.

16. An image processing system as defined in claim 1 wherein said sub-images are stored in said second store in a compressed form.

17. An image processing system as defined in claim 1 further comprising means for indicating whether a sub-image in said primary store has been selected.

18. An image processing system as defined in claim 1 wherein said primary store has a storage capacity sufficient to store at least two sub-images.

19. An image processing system as defined in claim 1 wherein said sub-images are rectangular.

2. A method for displaying images comprising the steps of:

subdividing each image into a plurality of rectangular sub-images,

providing each image with a table containing information on the current viewing state of the image,

providing each sub-image with a table containing information on the current viewing state of the sub-image,

storing said sub-images and tables in a data storage device,

selecting and displaying a desired view of a stored image on a display device as a viewed image having a view state, said selecting and displaying comprising the following steps;

selecting a sub-image of said stored image for display,

comparing the view state of said selected sub-image to the view state of said viewed image,

altering said sub-image view state so as to conform with said viewed image view state,

displaying said sub-image in said altered view state and

repeating said selecting, comparing, altering and displaying steps for each sub-image to be displayed.

3. A method of manipulating images in a data processing system, said system including a display device, a primary store and a secondary store and means for controlling access to said primary and secondary stores, said method comprising the following steps:

subdividing each image to be stored into a plurality of rectangular sub-images,

storing said sub-images in said primary store and said secondary store, said sub-images stored in said primary store being accessible for display by said display device,

storing view status information for each image and each sub-image,

selecting a stored image to be manipulated,

creating an access list for said selected stored image, said access list identifying sub-images of said image required for performance of the manipulation,

sequentially selecting and manipulating all sub-images on said access list which are stored in said primary store,

restoring sub-images in said primary store to said secondary store when all sub-images on said access list which are in primary store have been accessed, said restored sub-images being transferred to said secondary store in an order which minimizes transfers between said primary and secondary stores,

transferring a sub-image on said access list from said secondary store to said primary store,

selecting and manipulating said most recently transferred sub-image, and

continuing said steps of transferring from said secondary store and selecting and manipulating said most recently transferred sub-image until all sub-images on said access list are manipulated.

4. A method of modifying image information in a data processing system comprising the steps of:

subdividing each image stored in said system into a plurality of rectangular sub-images;

assigning a view state to each image indicating a current state in which said image can be viewed,

assigning a view state to each sub-image, said sub-image view state indicating the state in which said sub-image is stored in said system; and

selecting a view of a stored image, said view having a view state, said selecting step comprising;

accessing a sub-image of said stored image,

comparing said view state of said accessed sub-image to the view state of said of selected view of said stored image;

modifying said accessed sub-image to change its view state to the view state of the selected view; and

repeating said accessing, comparing and modifying steps for each of those sub-images of said selected image which are to be modified.

5. A method as defined in claim 4 wherein said sub-images are stored in primary and secondary stores and said sub-images are only accessible for display and modification when stored in said primary store, said method further comprising the steps of:

providing an access list of sub-images to be modified;

accessing sub-images on said access list in accordance with a priority scheme in which sub-images in said primary store are accessed prior to accessing sub-images which require fetch and store cycles.

6. A method of manipulating images within a data processing system comprising:

subdividing each image to be stored into a plurality of sub-images,

maintaining a view state record for each image,

maintaining a view state record for each sub-image of each image,

selecting a view of a stored image, said view having a view state record,

accessing sub-images of said selected image which include areas of said stored image requiring manipulation,

comparing the view state record of each accessed sub-image with the view state record of the selected view, and

conforming each said accessed sub-image view state and view state record to the view state and view state record of said selected view.

7. A method of manipulating images as defined in claim 6 wherein said data processing system has a primary store and a secondary store, said primary store being capable of storing only a portion of an image, said method further comprising the steps of:

accessing and manipulating sub-images stored in said primary store before sub-images stored in said secondary store are accessed;

swapping sub-images in said primary store for sub-images in said secondary store after all accessing and manipulating operations have been performed on said sub-images in said primary store; and

accessing and manipulating said sub-images swapped into said primary store.

8. A method of manipulating images as defined in claim 7 wherein said primary store retains at least two sub-images.

9. A method of manipulating images as defined in claim 7 wherein said sub-images stored in said primary store have associated access indicators, each access indicator denoting how recently a sub-image has been accessed relative to other sub-images, whereby the least recently accessed sub-image may be overwritten by a sub-image swapped out from said secondary store.

10. A method of manipulating images as defined in claim 7 wherein said sub-images are accessed in an order that requires fewer swapping operations between said primary and secondary stores than would be required by accessing the subimages in a random order.

11. A method of manipulating images as defined in claim 10 wherein said sub-images in said primary store are replaced in accordance with a priority arrangement wherein sub-images in said primary store which are not on said access list and have not been modified are replaced first, sub-images not on said access list are replaced second and sub-images on said access list but not modified are replaced third.

12. A method of manipulating images as defined in claim 9 wherein said sub-images are stored in said secondary store in a compressed state.

13. A method of manipulating images as defined in claim 8 wherein said manipulating operations are selected from the group of operations including rotating an image, reflecting an image, inverting color pattern of an image, pattern filling an image, annotating an image with graphical and textual information, scaling an image and copying one image onto another image.

14. A method of manipulating images as defined in claim 8 wherein said manipulating operations can be performed on sub-images of an image in any order.

15. A method of manipulating images as defined in claim 8 wherein said sub-images are rectangular.

20. An image processing system for transforming a source image into a destination image, said source image comprising a plurality of source subimages, said destination image comprising a plurality of destination subimages, said system comprising:

a first store;

a second store;

means for loading a digital representation of the source image into the second store;

a source table associated with the source image, said source table defining the view characteristics of the source image;

a destination table associated with the destination image, said destination table defining the view characteristics of the destination image;

a source subimage table associated with each source subimage, each source subimage table defining the view characteristics of the associated source subimage;

means for loading a first source subimage from the second store into the first store;

means for comparing the view characteristics of the first source subimage in the first store with the view characteristics of the destination image and for transforming the first source subimage in the first store into at least one selected destination subimage in the first store having the view characteristics of the destination image;

means for replacing the first source subimage in the first store with a second source subimage after transforming the first source subimage; and

means for comparing the view characteristics of the second source subimage in the first store with the view characteristics of the destination image and for transforming the second source subimage in the first store into at least the one selected destination subimage in the first store having the view characteristics of the destination image.

21. A method of transforming a source image into a destination image, said source image comprising a plurality of source subimages, said destination image comprising a plurality of destination subimages, said method comprising the steps of:

providing a first store;

providing a second store;

loading a digital representation of the source image into the second store;

providing a source table associated with the source image, said source table defining the view characteristics of the source image;

providing a destination table associated with the destination image, said destination table defining the view characteristics of the destination image;

providing a source subimage table associated with each source subimage, each source subimage table defining the view characteristics of the associated source subimage;

loading at least a first source subimage from the second store into the first store;

comparing the view characteristics of the first source subimage in the first store with the view characteristics of the destination image and transforming the first source subimage in the first store into at least one selected destination subimage in the first store having the view characteristics of the destination image;

replacing the first source subimage in the first store with a second source subimage after transforming the first source subimage; and

comparing the view characteristics of the second source subimage in the first store with the view characteristics of the destination image and transforming the second source subimage in the first store into at least the one selected destination subimage in the first store having the view characteristics of the destination image.