Source: http://www.google.com/patents/US5428725?dq=6076065
Timestamp: 2014-03-14 02:25:07
Document Index: 599025660

Matched Legal Cases: ['art 32', 'art 32', 'art 32', 'art 32', 'art 32', 'art 32', 'art 92', 'arts 92', 'art 92']

Patent US5428725 - System for performing coordinate transformation of source image data - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsAn image data processing system which includes an image memory and an image processor for performing coordinate transformation of source image data expressed by two dimensional coordinates. The image processor includes image memory in which data of source and destination images are stored, a coordinate...http://www.google.com/patents/US5428725?utm_source=gb-gplus-sharePatent US5428725 - System for performing coordinate transformation of source image dataAdvanced Patent SearchPublication numberUS5428725 APublication typeGrantApplication numberUS 08/098,420Publication dateJun 27, 1995Filing dateJul 27, 1993Priority dateJun 14, 1989Fee statusLapsedPublication number08098420, 098420, US 5428725 A, US 5428725A, US-A-5428725, US5428725 A, US5428725AInventorsKouji Fukuda, Hideo Haruta, Masatoshi Hino, Kazutaka Itou, Kazuo SugaiOriginal AssigneeHitachi Asahi Electronics Co., Ltd., Hitachi Microsoftware Systems, Inc., Hitachi, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (4), Non-Patent Citations (2), Referenced by (8), Classifications (11), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetSystem for performing coordinate transformation of source image dataUS 5428725 AAbstract An image data processing system which includes an image memory and an image processor for performing coordinate transformation of source image data expressed by two dimensional coordinates. The image processor includes image memory in which data of source and destination images are stored, a coordinate calculator which calculates at least x and y addresses at a position of a pixel in the source image on the basis of x and y addresses at a position of an associated pixel in the destination image, an interpolation calculator which calculates a pixel value of the destination pixel position through interpolation of source pixel values in the vicinity of the corresponding position in the source image, and a cache apparatus which holds therein part of the pixel values of the source image stored in the image memory, wherein the x and y addresses of the corresponding pixel position of the source image are used as tag and as an index for the cache apparatus respectively, whereby the high rate of the cache apparatus can be increased and the entire processing speed of the image data processing system can be increased.
What is claimed is: 1. An image data processing system for performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising:image memory means for storing the source and destination image data; and an image data processor for transforming the source image data stored in the image memory means and storing the transformed data into the image memory means, the image data processor comprising:coordinate calculating means for scanning a pixel position represented by DX and DY in a destination image, and calculating a memory address of said pixel position in the destination image, a pixel position represented by SX and SY in a source image which is to be transferred to said pixel position in the destination image by a transformation process, and a memory address of said pixel position in the source image; cache memory means for storing the source image data read from said memory address of said pixel position in the source image calculated by the coordinate calculating means with said pixel position represented by SX and SY in the source image; data write control means for writing the image data into the memory address of said pixel position in the destination image calculated by said coordinate calculating means; and cache control means for controlling the cache memory means so that if the source image data at said pixel position in the source image which is to be transferred to said pixel position in the destination image has already been stored in the cache memory means, the source image data is read from the cache memory means in response to said pixel position represented by SX and SY in the source image, and used to make the destination image. 2. An image data processing system for performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising:image memory means for storing the source and destination image data; and an image data processor for transforming the source image data stored in the image memory and storing the transformed data into the image memory means, the image data processor comprising:data read control means for controlling the image memory means so that the source image data is read from the image memory means in response to a memory address; coordinate calculating means for scanning a pixel position in a source image, and calculating a memory address of said pixel position represented by SX and SY in the source image, a pixel position in a destination image represented by DX and DY to which said pixel position in the source image is to be transferred by a transformation process, and a memory address of said pixel position in the destination image; cache memory means for storing the destination image data which are to be written into the image memory means at said memory address of said pixel position in the destination image calculated by the coordinate calculating means, storing with said pixel position represented by DX and DY in the destination image; and cache memory control means for controlling the cache memory so that, if old data before updating the image memory means represented by the DX and DY of the destination image where new data to be written into the image memory means is present in the cache memory means, the old data is updated with image data newly written into the cache memory means, if old data represented by DX and DY of the destination image where new data to be written into the image memory means is not present in the cache memory means, the image data which is to be newly written into the image memory means is newly stored into the cache memory means with the coordinate values DX and DY, but before updating the cache memory means, if old different coordinate values and data for writing into different coordinate values are already present in the newly stored position of the cache memory means, the old values already present are written into a position pointed to by said different coordinate values before updating the cache memory means with new coordinate values and new data, and when finishing a coordinate transformation from the source image to the destination image, all data in the cache memory means but not yet written into the image memory means are written into the image memory means. 3. An image data processing method of performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising the steps of:scanning a pixel position represented by DX and DY in a destination image, and calculating a memory address of said pixel position in the destination image, a pixel position represented by SX and SY in a source image which is to be transferred to said pixel position in the destination image by a transformation process, and a memory address of said pixel position in the source image; storing the source image data read from said memory address of said pixel position in the source image into a cache memory means with said pixel position represented by SX and SY in the source image; writing the image data into the memory address of said pixel position in the destination image; and if source image data at said pixel position in the source image which is to be transferred to said pixel position in the destination image has already been stored in the cache memory means, reading the source image data from the cache memory means in response to said pixel position represented by SX and SY in the source image, and using it to generate a destination data, and if the source image data at said pixel position in the source image which is to be transferred to said pixel position in the destination image has not yet been stored in the cache memory means, reading the source image data from the image memory means, writing it into the cache memory means, and using it to generate the destination data. 4. An image data processing method of performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising the steps of:scanning a pixel position represented by SX and SY in the source image, and calculating a memory address of said pixel position in the source image, a pixel position represented by DX and DY in the destination image to which said pixel position in the source image is to be transferred by a transformation process, and a memory address of said pixel position in the destination image; reading the source image data from an image memory means in response to the memory address of said pixel position in the source image; storing the destination image data which are to be written into the image memory means into a cache memory means, storing with said pixel position represented by DX and DY in the destination image; and if old data before updating the image memory represented by DX and DY of the destination image where new data to be written into the image memory means is present in the cache memory means, updating old data with image data newly written into the cache memory means, if old data represented by DX and DY of the destination image where new data to be written into the image memory means is not present in the cache memory means, newly storing the image data which is to be newly written into the image memory means into the cache memory means with the coordinate values represented by DX and DY, but before updating the cache memory means, if old different coordinate values and data for writing into different coordinates are already present in a newly storing position of the cache memory means, writing the old values already present in a position pointed by said different coordinates before updating the cache memory means with new coordinates and new data, and when finishing a coordinate transformation from the source image to the destination image, writing all data in the cache memory means, but not yet written into the image memory means, into the image memory means. 5. An image data processing system for performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising:image memory means for storing the source and destination image data; and, an image data processor for transforming the source image data stored in the image memory and storing the transformed data into the image memory means, the image data processor comprising:coordinate calculating means for scanning a pixel position represented by DX and DY in a destination image, and calculating a memory address of said pixel position in the destination image, a pixel position represented by SX and SY in a source image which is to be transferred to said pixel position in the destination image by a transformation process, and a memory address of said pixel position in the source image; cache memory means for storing the source image data read from said memory address of said pixel position in the source image calculated by the coordinate calculating means with said pixel position represented by SX and SY in the source image; data write control means for writing the image data into a memory address of said pixel position in the destination image calculated by said coordinate calculating means; and, cache control means for controlling the cache memory means in response to source coordinate values represented by SX and SY calculated by the coordinate calculating means, wherein lower bits of SX and lower bits of SY are used as an index and higher bits of SX and higher bits of SY are used as a tag whereby geometrically near parts of the source image can be stored in the cache simultaneously. 6. The image data processing system according to claim 5, wherein coordinate transformation in the coordinate calculating means is affine transformation.
9. An image data processing system for performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising:image memory means for storing the source and destination image data; and, an image data processor for transforming the source image data stored in the image memory and storing the transformed data into the image data processor comprising:data read control means for controlling the image memory means so that the source image data is read from the image memory means in response to a memory address; coordinate calculating means for scanning a pixel position in a source image, and calculating a memory address of said pixel position represented by SX and SY in the source image, a pixel position in a destination image represented by DX and DY to which said pixel position in the source image is to be transferred by a transformation process, and a memory address of said pixel position in the destination image; cache memory means for storing the destination image data which are to be written into the image memory means at said memory address of said pixel position in the destination image calculated by the coordinate calculating means with said pixel position represented by DX and DY in the destination image; and cache memory control means for controlling the cache memory means in response to the destination coordinate values represented by DX and DY calculated by said coordinate calculating means, wherein lower bits of DX and lower bits of DY are used as an index and higher bits of DX and higher bits of DY are used as a tag whereby geometrically near parts of the destination image can be stored in the cache simultaneously. 10. The image data processing system according to claim 9, wherein coordinate transformation in the coordinate calculating means is affine transformation.
13. An image data processing method of performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising the steps of:scanning a pixel position represented by DX and DY in a destination image, and calculating a memory address of said pixel position in the destination image, a pixel position represented by SX and SY in a source image which is to be transferred to said pixel position in the destination image by a transformation process, and a memory address of said pixel position in the source image; storing the source image data read from said memory address of said pixel position in the source image into a cache memory means, storing with said pixel position represented by SX and SY in the source image; writing the image data into a memory address of said pixel position in the destination image; and, when storing the image data in the cache memory means, respond to source coordinate values represented by SX and SY, use lower bits of SX and lower bits of SY as an index and use higher bits of SX and higher bits of SY as a tag whereby geometrically near parts of the source image can be stored in the cache simultaneously. 14. An image data processing method of performing coordinate transformation about a pixel position of image data between source image data and destination image data, comprising the steps of:scanning a pixel position represented by SX and SY in a source image, and calculating a memory address of said pixel position in the source image, a pixel position represented by DX and DY in a destination image to which said pixel position in the source image is to be transferred by a transformation process, and a memory address of said pixel position in the destination image; reading the source image data from an image memory means in response to a memory address of said pixel position in the source image; storing the destination image data which are to be written into the image memory means into a cache memory means with said pixel position represented by DX and DY in the destination image; and, when storing the destination image data in the cache memory means, respond to destination coordinate values represented by DX and DY, use lower bits of DX and lower bits of DY as an index and use higher bits of DX and higher bits of DY as a tag so that geometrically near parts of the destination image can be stored in the cache simultaneously. Description
BACKGROUND OF THE INVENTION The present invention generally relates to image data processing systems and, more particularly, to an image data processing system which can minimize the frequency of access to an image memory in processing of an image data.
A system for taking part of zone of an image into a processor for rotation processing is discussed, for example, in the Preliminary Publication titled "Am 95c 76 (A.M.D.). Orthogonal Rotation Processor (ORP)", #09332. Rev. B. Amendment/O (September, 1987). In this system, however, it has been impossible to process an ordinary image because it only handles every 90
The first-mentioned related art system is defective in that no consideration is paid to the frequency of access to the image memory and thus it is impossible to further increase the processing speed of the entire system. The second related art system is disadvantageous in that the processing of this system is limited to every 90 it is impossible to use the system for ordinary image processing.
SUMMARY OF THE INVENTION It is an object of the present invention to provide an image data processing system which can minimize the frequency of access to an image memory in processing ordinary image data, thus realizing an increased processing speed of the entire system.
BRIEF DESCRIPTION OF THE DRAWINGS FIGS. 1A and 1B schematically show diagrams for explaining the operation of an image cache used in a first embodiment of the present invention;
DESCRIPTION OF THE PREFERRED EMBODIMENTS Specific embodiments of the image data processing system of the present invention will be described with reference to the attached drawings.
A structure of an image memory 21 in the present embodiment is shown in FIG. 3A, from or into which 16 pixels (one word) at positions (16n, m) to (16n+15,m) (where n and m are integers) are intended to be read or written at the same time. In this embodiment, monochrome one bit per pixel image memory system is expected. An address in the image memory 21 with respect to a word containing a pixel (x, y) (where x and y are integers) is expressed in the form of BA+y containing the source image and a zone containing the destination image are different in the base address BA and base width BW, and symbol [ ] means to represent an integral part of a real number.
Referring to FIG. 4, there is shown a block diagram of an embodiment of an image data processor 31 realizing the present embodiment, which processor includes an affine transformation part 32 and a microprocessor 33 for controlling the affine transformation part 32. The microprocessor 33, is located in the image processor 31, which is different from a microprocessor for the system, and which functions to control the image processor 31. In the present embodiment, the affine transformation part 32, when activated by the microprocessor 33, prepares a destination image data having a size corresponding to 16 pixels (horizontal pixels (vertical (l=DB-DT being calculated in the microprocessor 33 and set in the register within the affine transformation part 32).
DSA=DBA+DYO
Thereafter, microprocessor 33 waits for the input of an end interrupt from the affine transformation part 32 (step 48). The microprocessor 33, when receiving the end interrupt, adds 16 to DXO (step 49). This is for the purpose of processing the next area located on the right side of the area 13D by the microprocessor 33, because the affine transformation part 32 only generates an image data corresponding to such an area of 16 pixels (horizontal) FIG. 2B. The microprocessor 33 judges whether or not the next position (DXO, DYO) is located within the destination processing region 15D (step 50). This is attained by comparing DXO with DR, and when a relationship DXO≦DR is satisfied, by determining that the next position is within the region 15D. When the position (DXO, DYO) is within the region 15D, the microprocessor 33 returns to the step 44; when the position is outside the region 15D, the microprocessor 33 stops the image processor (step 51).
MASK=(SYP&amp;gt;SB)+([SY]&amp;lt;ST)+(SYP&amp;gt;SR)+([SX]&amp;lt;SL)                 (6)
The operation of the image cache means 32b will next be described with reference to FIG. 8, FIG. 9, and FIGS. 1A and 1B. In FIG. 8 and FIGS. 1A and 1B, the image cache means 32b includes an image cache 2 which comprises 64 corresponding to 64 pixels which is also included in the image cache means 32b, comprises 64 tags and V (valid) bits, each tag and each V bit corresponding to an area of 16 bits (horizontal) following values are sent from the address calculator 32a (refer to FIG. 4) to the image cache means 32b (refer to FIG. 3C).
The hit test method of the image cache 2 will be explained in connection with FIG. 1A. A single tag 4 and a single V bit 5 are designated respectively by an x address of 2.sup.4 -3.sup.5 bits and a y address of 2.sup.0 -2.sup.5, and the value of tag 4 is compared at a comparator CMP 7 with an x address of 2.sup.6 -2.sup.12 and a y address of 2.sup.6 -2.sup.12. When the comparator 7 finds a coincidence therebetween and the V bit is "1", the image cache 2 determines to be an image cache hit and an AND circuit 8 outputs "1", so that a bit 6 designated by an x address of the image cache 2 of 2.sup.0 -2.sup.5 and a y address of 2.sup.0 -2.sup.5 becomes valid. If not, the image cache 2 issues an image memory read request.
How to write pixel values from the image memory to the image cache 2 will be explained by referring to FIG. 1B. Pixel values corresponding to one word read out from the image memory are written into a 16-bit zone 9 represented by x addresses of 2.sup.4 -2.sup.5 bits and y addresses of 2.sup.0 -2.sup.5 bits and y addresses of 2.sup.0 -2.sup.5 bits on the image cache 2. Simultaneously with this operation, the x address of 2.sup.6 -2.sup.12 bits and the y address of 2.sup.6 -2.sup.12 bits are written into the tag 4 represented by the x address of 2.sup.4 -2.sup.5 bits and the y address of 2.sup.0 -2.sup.5 bits and corresponding V bit 5 is set.
An image processor realizing the present embodiment is shown, in a block diagram, by reference numeral 91 in FIG. 13. An affine transformation part 92 included in the image processor 91, when activated by a microprocessor 93, transforms an image of a size corresponding to 16 pixels (horizontal) the microprocessor 93). In the present embodiment, to this end, in order to transform an image of a size corresponding to several words in the horizontal direction, the microprocessor 93 activates the affine transformation parts 92 several times. An image memory bus controller 95 arbitrates between a source image data read request from an address calculator 92a, a data read request to a destination image region and a destination image data write request from an image cache means 92b. An input buffer means 94 accumulates pixel values corresponding to one word read from an image memory (not shown) and sends them to the affine transformation part 92 on a pixel-after-pixel basis.
Explanation will then be made as to the image cache means 92b by referring to FIGS. 15 to 17. The image cache 2 in FIGS. 15, 17A, 17B and 17C, which comprises a 64 pixels. The address array 1 comprises a total of 64 bits, each tag and each V bit corresponding to a zone of the image cache 2 corresponding to 16 bits (horizontal) following values are provided from the address calculator 92a to the image cache means 92b.
Explanation will be made as to how the image cache performs the hit test with reference to FIG. 17A. First, a tag 4 and a V bit 5 are designated respectively in terms of an x address of 2.sup.4 -2.sup.5 bits and a y address of 2.sup.0 -2.sup.5 bits. The value of the tag is compared at a comparator 7 with x addresses of 2.sup.6 -2.sup.12 bits and y addresses of 2.sup.6 -2.sup.12 bits. If a coincidence is found at the comparator and the V bit is "1", then a cache hit is determined, and the pixel value I is written at a position of the image cache specified by an x address of 2.sup.0 -2.sup.5 bits and a y address of 2.sup.0 -2.sup.5 bits.
Explanation will next be made as to swap out pixel values corresponding to one word from the image cache to the image memory by referring to FIG. 17B. When a cache mishit is determined and V=1, a pixel values 9 of the corresponding one word of the image cache 2 are written to the word addressed by X and Y addresses defined as follows. An x address of 2.sup.4 -2.sup.5 bits and a y address of 2.sup.0 -2.sup.5 on the image memory are equal to DX of 2.sup.4 -2.sup.5 bits and DY of 2.sup.0 -2.sup.5 respectively, and the x addresses of 2.sup.6 -2.sup.12 bits and the y addresses of 2.sup.6 -2.sup.12 bits are equal to the tag designated by the DX of 2.sup.4 -2.sup.5 bits and the DY of 2.sup.0 -2.sup.5 bits. Simultaneosuly with the writing into the word designated by the image memory address corresponding to the image logical address, the corresponding V bit 5 is lowered.
How to write a word from the image memory into the image cache will be explained by referring to FIG. 17C. Pixel values corresponding to one word read from the image memory are written into the 16-bit zone 9 designated by the x address of 2.sup.4 -2.sup.5 bits and the y address of 2.sup.0 -2.sup.5 bits on the image cache. Simultaneously with this writing operation, the x address of 2.sup.6 -2.sup.12 bits and the y address of 2.sup.6 -2.sup.12 bits are written into the corresponding tag 4 to set the V bit 5.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4797836 *Nov 19, 1986Jan 10, 1989The Grass Valley Group, Inc.Image orientation and animation using quaternionsUS5131080 *Dec 20, 1990Jul 14, 1992Hewlett-Packard CompanyGraphics frame buffer with RGB pixel cacheUS5276778 *Jun 4, 1990Jan 4, 1994Ezel, Inc.Image processing systemJPS63129476A * Title not available* Cited by examinerNon-Patent CitationsReference1"Am95C76 Orthogonal Rotation Processor (ORP)", #09332 Rev. B, Amendment/0, Sep. 1987.2 *Am95C76 Orthogonal Rotation Processor (ORP) , 09332 Rev. B, Amendment/0, Sep. 1987.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5680150 *Nov 23, 1994Oct 21, 1997Canon Kabushiki KaishaImage processing method and apparatusUS5734384 *Oct 15, 1996Mar 31, 1998Picker International, Inc.Cross-referenced sectioning and reprojection of diagnostic image volumesUS5749089 *Nov 26, 1996May 5, 1998Fujitsu LimitedCache-memory system having multidimensional spread cacheUS5812146 *Nov 25, 1997Sep 22, 1998Canon Kabushiki KaishaImage processing apparatus using compressed data processingUS6405288 *Aug 10, 1999Jun 11, 2002Via Technologies, Inc.Method and system for controlling the memory access operation by central processing unit in a computer systemUS6606554Sep 27, 2001Aug 12, 2003Siemens Information & Communication Mobile LlcMethod and apparatus for defining location coordinatesUS6697081 *Oct 12, 2000Feb 24, 2004Yamaha CorporationImage processing method and device, and storage medium storing a program thereforWO1999059069A1 *Apr 20, 1999Nov 18, 1999Hachmann UlrichCache memory for two-dimensional data fields* Cited by examinerClassifications U.S. Classification345/648, 345/562, 358/1.16, 345/557, 345/531International ClassificationG06F12/08, G06T3/60Cooperative ClassificationG06F12/0875, G06T3/606European ClassificationG06T3/60M, G06F12/08B14Legal EventsDateCodeEventDescriptionAug 14, 2007FPExpired due to failure to pay maintenance feeEffective date: 20070627Jun 27, 2007LAPSLapse for failure to pay maintenance feesJan 10, 2007REMIMaintenance fee reminder mailedSep 30, 2002FPAYFee paymentYear of fee payment: 8Oct 30, 1998FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google