Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / First Aid / November 2005

Tip: Looking for answers? Try searching our database.

Arrays not big enough

Thread view: 
Rudiga - 26 Oct 2005 12:40 GMT
Hi

I wonder if anyone might be able to help. The program I am writing for my
dissertation is to process pictures against the previous one, i.e frames of
a video clip. I have run into a problem when comparing the RGB values for
each pixal against the last one as I am unable to store it all in any kind
of datastructure.

For example, i want to find the Standard deviation of the Red value for a
specific pixal in a 10 sec video clip, i would process each frame, store the
Red value in an array and then repeat until the end of the clip.

e.g

for (int x = 0; x < picWidth; x++) {

   for (int y = 0; y < picHeight; y++) {

       for(int i = 0; i < frames; i++){

       } // end each frame

   } // end y

} // end x

This method works (ie is more memory efficient) if i do one pixal at a time
and cycle the frame on the inner loop like above, however that requires more
calls to the hdd, ie for every pixal of every image. Therefore this takes
forever to calculate, therefore impractical.

By having the frame on the outer part of the loop would solve the speed
issue, ie reducing the calls to the hdd, but i have no way of storing all
the images in memory as it is too big.

Can anyone suggest any method to solve this problem?

Thankyou
Martin
Rudiga - 26 Oct 2005 12:53 GMT
Oh and also, I wanted to find the median of each pixal over a set of frames,
which causes a problem as i need to store each value for each pixal in order
to choose the median pixal value.

> Hi
>
[quoted text clipped - 35 lines]
> Thankyou
> Martin
Roedy Green - 26 Oct 2005 13:23 GMT
>By having the frame on the outer part of the loop would solve the speed
>issue, ie reducing the calls to the hdd, but i have no way of storing all
>the images in memory as it is too big.

You might look at memory mapped files, and work on keeping your
pokings from hopping all over.

The way the Gimp handles this is with tiles, but that would probably
count as a datastructure.

Perhaps split the image into squares, one square per file. Then just
read a corresponding pair of files into RAM, and do your calculation,
then move on to the next pair. To make life easy on yourself put some
slop around each image so you don't have to do fine needlework on the
edges.

You can do efficient bit fiddling by using longs and binary operators.
Look also into java.util.BitSet.

see http://mindprod.com/jgloss/binary.html

Just a hunch you might find this idea fun to play with..

Instead of RGB bits like this rrrrrrrrggggggggbbbbbb

interdigitate them:
rgbrgbrgbrgbrgbrgbrgbrgb

or convert them to HSB.

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Eric Sosman - 27 Oct 2005 17:35 GMT
Rudiga wrote On 10/26/05 07:40,:
> Hi
>
[quoted text clipped - 30 lines]
> issue, ie reducing the calls to the hdd, but i have no way of storing all
> the images in memory as it is too big.

   Mean and standard deviation are easy, because you don't
need to have all the samples present at the same time: you
can process an entire frame updating a couple of per-pixel
totals, then throw the frame away and move to the next.

   In a follow-up you said you're also interested in the
median, which is a bit trickier but still tractable.  Since
the color components for each pixel have a very restricted
range (0<=R<256), you could just count the number of times
each possible R value appeared at each pixel position and then
figure out the median (or other quantiles) after processing
all the frames.

   If maintaining 256 counters per color component per pixel
is too much, and if an estimate is acceptable instead of an
exact median, various approximate-median algorithms exist.
One that I've used is by Raj Jain and Imrich Chlamtac: "The
P**2 Algorithm for Dynamic Calculation of Quantiles and
Histograms Without Storing Observations," CACM volume 28
number 10 (October 1985), pages 1076-1085.

   Roedy Green's suggestion of breaking the images into
suitably-sized tiles can be used in conjunction with any of
these techniques.

Signature

Eric.Sosman@sun.com

Oliver Wong - 27 Oct 2005 22:10 GMT
>    If maintaining 256 counters per color component per pixel
> is too much, and if an estimate is acceptable instead of an
[quoted text clipped - 3 lines]
> Histograms Without Storing Observations," CACM volume 28
> number 10 (October 1985), pages 1076-1085.

   I'm not familiar with the paper cited above, but if you memory is a
problem and you're satisfied with an approximate mean, then a simple
algorithm would be to break up the possible values into chunkier bands
(perhaps 0-32,33-64,65-96,etc.), and store how many times a pixel value
falls in those bands, histogram style, and report the median to be the
center of the band with the most values.

   - Oliver
Eric Sosman - 01 Nov 2005 17:35 GMT
Oliver Wong wrote On 10/27/05 17:10,:

>>   If maintaining 256 counters per color component per pixel
>>is too much, and if an estimate is acceptable instead of an
[quoted text clipped - 10 lines]
> falls in those bands, histogram style, and report the median to be the
> center of the band with the most values.

   Almost, but what you describe approximates the mode
(or one of them), not the median.

   As for the mean, there's no reason to settle for an
approximation: computing the exact mean (within the limits
of numerical precision) is cheap.

Signature

Eric.Sosman@sun.com

Boudewijn Dijkstra - 27 Oct 2005 19:51 GMT
> Hi
>
[quoted text clipped - 30 lines]
> issue, ie reducing the calls to the hdd, but i have no way of storing all
> the images in memory as it is too big.

You don't need to store all the images.  To calculate the standard deviation
of all red values in a range of frames, you perform four stages.  In the first
stage, you iteratively load each frame and add the red values to a special
'sum-image' with increased bit depth.  In the second stage, you calculate the
average value of each dot using the sum-image.  In the third stage you make a
second pass over all the images to calculate the variance of each dot using
the average-image.  The fourth stage is simply to take the square root of the
variances, to obtain the standard deviation of each dot.
Nigel Wade - 28 Oct 2005 11:30 GMT
>> Hi
>>
[quoted text clipped - 39 lines]
> the average-image.  The fourth stage is simply to take the square root of the
> variances, to obtain the standard deviation of each dot.

There's no need to process the images twice, once should be sufficient. To
calculate the mean and variance you require sigma(x) and sigma(x squared)
[writing equations in ASCII is not ideal...]. Both these quantities can be
calculated on a single pass.

For non-complex data the mean is
 sigma(x)/N,

and the variance is
((sigma(x squared) - (sigma(x)*sigma(x)/N)) / (N-1)

So you only need to have 2 "frames", one to store sigma(x) for each pixel and
another to store sigma(x squared) for each pixel. These need to have sufficient
dynamic range to hold the summations.

Signature

Nigel Wade, System Administrator, Space Plasma Physics Group,
           University of Leicester, Leicester, LE1 7RH, UK
E-mail :    nmw@ion.le.ac.uk
Phone :     +44 (0)116 2523548, Fax : +44 (0)116 2523555



Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.