# US 10,321,159 B2 · Apparatus and method of performing fourier transform

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,321,159 B2
- Document ID: US10321159B2
- Status: Granted
- Kind: B2
- Application number: 15/218,243
- Filed: 2016-07-25
- Published: 2017-03-02
- Granted: 2019-06-11
- Earliest claimed: 2015-08-27
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Hojung Kim; Hoon Song; Hongseok Lee
- Web page: https://patentgrep.com/patent/US10321159B2

## CPC

- H04N 19/60: using transform coding
- G03H 1/0808: {Methods of numerical synthesis, e.g. coherent ray tracing [CRT], diffraction specific}
- G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm}
- H04N 19/42: characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation (H04N19/635 takes precedence)
- G03H 2210/30: 3D object
- G03H 2226/02: Computing or processing means, e.g. digital signal processor [DSP]
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G03H: HOLOGRAPHIC PROCESSES OR APPARATUS (holograms, e.g. point holograms, used as ordinary optical elements G02B5/32; producing stereoscopic or other three-dimensional effects G02B30/00; diffraction-grating systems G02B27/44; systems using moiré fringes G02B27/60; optical logic elements G02F3/00; stereo-photography G03B35/00; photosensitive materials or processes for photographic purposes G03C; {stereo-photographic or similar processes G03C9/00}; apparatus for processing exposed photographic materials G03D; analogue computers performing mathematical operations with the aid of optical elements G06E3/00; authentication by radiation, of concealed information carried by holograms or diffraction gratings G06K19/16; holographic storage G11B7/0065, G11C13/04; {stereoscopic or other three dimensional effects in television systems H04N13/00})
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of performing a Fourier transform includes generating first data by performing a one-dimensional (1D) fast Fourier transform (FFT), on data having rows and columns, in a row direction; generating second data by performing the 1D FFT, on a portion of the first data, in a column direction; and storing a portion of the second data.

## Claims

### Claim 1

A method of performing a Fourier transform on an image data, the method comprising:
generating a first image data by performing a one-dimensional (1D) Fast Fourier Transform (FFT), on the image data having rows and columns, in a row direction;
storing a portion of the first image data;
generating a second image data by performing the 1D FFT, on the portion of the first image data, in a column direction;
storing a portion of the second image data; and
outputting the portion of the second image data to display a final image,
wherein the generating the first image data comprises completing the 1D FFT on the rows of the image data in the row direction when the portion of the first image data is generated,
wherein the generating the second image data comprises completing the 1D FFT on columns of the portion of the first image data in the column direction when the portion of the second image data is generated,
wherein the portion of the first image data comprises a low frequency component from among the first image data, and
wherein the portion of the second image data comprises a low frequency component from among the second image data.

### Claim 2 (depends on 1)

The method of claim 1, wherein the portion of the first image data is based on a portion of columns of the first image data.

### Claim 3 (depends on 1)

The method of claim 1, wherein the storing the portion of the second image data comprises storing a portion of rows of the second image data in a buffer.

### Claim 4

A method of performing a Fourier transform on an image data, the method comprising:
generating a first image data by performing a one-dimensional (1D) Fast Fourier Transform (FFT), on the image data having rows and columns, in a column direction;
storing a portion of the first image data in a memory;
generating a second image data by performing the 1D FFT, on the portion of the first image data, in a row direction;
storing a portion of the second image data; and
outputting the portion of the second image data to display a final image,
wherein the generating the first image data comprises completing the 1D FFT on the columns of the image data in the column direction when the portion of the first image data is generated,
wherein the generating the second image data comprises completing the 1D FFT on rows of the portion of the first image data in the row direction when the portion of the second image data is generated,
wherein the portion of the first image data comprises a low frequency component from among the first image data, and
wherein the portion of the second image data comprises a low frequency component from among the second image data.

### Claim 5

An image processing apparatus for performing a Fourier transform, the image processing apparatus comprising:
at least one processor configured to execute processor-executable instructions, the processor comprising:
a first core configured to generate a first image data by performing a one-dimensional (1D) Fast Fourier Transform (FFT), on an image data having rows and columns, in a row direction;
a memory configured to store a portion of the first image data;
a second core configured to generate a second image data by performing the 1D FFT, on the portion of the first image data, in a column direction; and
a buffer configured to store a portion of the second image data, and output the portion of the second image data to display a final image,
wherein the generating the first image data comprises completing the 1D FFT on the rows of the image data in the row direction when the portion of the first image data is generated,
wherein the generating the second image data comprises completing the 1D FFT on columns of the portion of the first image data in the column direction when the portion of the second image data is generated,
wherein the portion of the first image data comprises a low frequency component from among the first image data, and
wherein the portion of the second image data comprises a low frequency component from among the second image data.

### Claim 6 (depends on 5)

The image processing apparatus of claim 5, wherein the portion of the first image data corresponds to a portion of columns of the first image data.

### Claim 7 (depends on 5)

The image processing apparatus of claim 5, wherein the portion of the second image data corresponds to a portion of rows of the second image data.

### Claim 8

An image processing apparatus for performing a Fourier transform, the image processing apparatus comprising:
at least one processor configured to execute processor-executable instructions, the at least one processor comprising:
a first core configured to generate a first image data by performing a one-dimensional (1D) Fast Fourier Transform (FFT), on an image data having rows and columns, in a column direction;
a memory configured to store a portion of the first image data from among the first image data;
a second core configured to generate a second image data by performing the 1D FFT, on the portion of the first image data, in a row direction; and
a buffer configured to store a portion of the second image data, and output the portion of the second image data to display a final image,
wherein the generating the first image data comprises completing the 1D FFT on the columns of the image data in the column direction when the portion of the first image data is generated,
wherein the generating the second image data comprises completing the 1D FFT on rows of the portion of the first image data in the row direction when the portion of the second image data is generated,
wherein the portion of the first image data comprises a low frequency component from among the first image data, and
wherein the portion of the second image data comprises a low frequency component from among the second image data.

### Claim 9 (depends on 1)

A non-transitory computer-readable recording medium having recorded thereon a computer program, which, when executed by a computer, causes the computer to perform the method of claim 1.

### Claim 10

An image processing apparatus for performing a Fourier transform, the image processing apparatus comprising:
at least one processor configured to execute processor-executable instructions, the at least one processor comprising:
N first cores, wherein N being a natural number of 2 or greater, configured to generate a first image data by performing a one-dimensional (1D) Fast Fourier Transform (FFT), on an image data having an N×M matrix form, wherein M being a natural number of 2 or greater, in a row direction;
a memory configured to store L columns of the first image data, wherein L being a natural number smaller than M;
L second cores configured to perform the 1D FFT on the L columns of the first image data to generate a second image data, in a column direction; and
a buffer configured to store a portion of the second image data output by the L second cores, and output the portion of the second image data to display a final image,
wherein the generating the first image data comprises completing the 1D FFT on the rows of the image data in the row direction when the portion of the first image data is generated,
wherein the generating the second image data comprises completing the 1D FFT on columns of the portion of the first image data in the column direction when the portion of the second image data is generated,
wherein the portion of the first image data comprises a low frequency component from among the first image data, and
wherein the portion of the second image data comprises a low frequency component from among the second image data.

### Claim 11 (depends on 10)

The image processing apparatus of claim 10, wherein the N first cores respectively perform an M-point FFT.

### Claim 12 (depends on 10)

The image processing apparatus of claim 10, wherein the L second cores respectively perform an N-point FFT.

### Claim 13 (depends on 10)

The image processing apparatus of claim 10, further comprising a First IN, First Out (FIFO) buffer configured to store the first image data and output L columns selected from M columns of the first image data to the memory.

### Claim 14 (depends on 10)

The image processing apparatus of claim 10, further comprising an interleaving buffer configured to output the L columns of the first image data, received from the memory, to the L second cores, respectively.

### Claim 15

An image processing apparatus for performing a Fourier transform, the image processing apparatus comprising:
at least one processor configured to execute processor-executable instructions, the at least one processor comprising:
first cores configured to generate a first image data by performing a one-dimensional (1D) Fast Fourier Transform (FFT), on an image data having rows and columns, in a column direction;
a memory configured to store a portion of the first image data;
second cores configured to generate a second image data by performing the 1D FFT, on the portion of the first image data, in a row direction; and
a buffer configured to store a portion of the second image data, and output the portion of the second image data to display a final image,
wherein a number of the first cores corresponds to a number of columns of the image data, and a number of the second cores corresponds to a number of rows of the portion of the first image data,
wherein the generating the first image data comprises completing the 1D FFT on the columns of the image data in the column direction when the portion of the first image data is generated,
wherein the generating the second image data comprises completing the 1D FFT on rows of the portion of the first image data in the row direction when the portion of the second image data is generated,
wherein the portion of the first image data comprises a low frequency component from among the first image data, and
wherein the portion of the second image data comprises a low frequency component from among the second image data.