Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fully Vectorized Histogram Algorithm

IP.com Disclosure Number: IPCOM000036563D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 4 page(s) / 120K

Publishing Venue

IBM

Related People

Karp, AH: AUTHOR [+2]

Abstract

Image processing requires computationally intensive manipulation of very large amounts of byte-oriented data. It would be desirable to take advantage of a vector processor to improve the response time when solving image processing problems.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 4

Fully Vectorized Histogram Algorithm

Image processing requires computationally intensive manipulation of very large amounts of byte-oriented data. It would be desirable to take advantage of a vector processor to improve the response time when solving image processing problems.

Image processing of Landsat, medical, and other byte-mapped data requires operations of very large megabyte arrays. (A "standard" Landsat scene requires 320 megabytes to store.) The unit of information in these arrays, called a "pixel", is normally stored as one byte. Typical image displays can present 1024x1024 or 1024x1280 pixel images, each of which may be represented by three bytes
(3.6 megabytes total).

One commonly used operation in image analysis is making a histogram of the pixel values present in the image. Presented here is a fully vectorized algorithm for generating such a histogram that may substantially reduce the time required on some vector processors.

Two problems arise in the attempt to use a vector processor to generate a histogram. The first is a more general problem relating to most attempts to process 1-byte data. Vector processors usually operate on 4-byte integers, as well as 4- and 8-byte floating point numbers. Hence, they do not usually operate on individual 1-byte quantities in vector mode. The second problem is more specific to histogram generation, though it arises frequently whenever image data is used as a subscript. The normal histogram calculation is performed in FORTRAN as follows: CHARACTER*1 IPIX(N)

INTEGER*4 I4, I, N, HGM(0:255)

DO 10 I = 1,N

I4 = IPIX(I) ! Copy 1 byte of image

data to I4

HGM(I4) = HGM(I4) + 1 ! Generate the histogram

counts

10 CONTINUE

This program cannot be vectorized. Attention is focused on the case when several pixels have the same value. If two pixels have the same value, then two vector elements will refer to the same word in storage. When this happens, copies of the same word will be loaded into separate vector elements, incremented, and returned to memory. Because there is no control to assure this process will be properly synchronized, there is no guarantee that the histogram will be computed properly. Therefore, the code must be run in scalar mode.

The invention consists of two parts. The first part consists of unpacking the pixels from 1-byte to n-byte elements which can be handled by the vector processor. The second part addresses the problem of multiple updates of th...