473,581 Members | 2,875 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Stratified random sampling with random_shuffle ?

Dear cpp-ians,

I want to apply a stratified sampling on an image. Following simplified
example will explain my problem.

The original image I with nrows and ncols is now a vector V of length
(nrow x ncol) and every element of the vector contians its pixel value.

vector float V [nrow * ncol] ;

This means that:
- the first ncol elements = first row of my image
- the elements between ncol and 2*ncol = the second row of my image
and so on ...

Now I want to select a stratified pixel of this vector and sample every
pixel till all pixels are sampled once. In the image it would
correspond to divide my image into small blocks and take a pixel of
each block iteratively till all pixels are done.

If I random_shuffle my vector and start at the beginning V till the end
I perform a random sampling, but I now want to add a certain order in
it so it corresponds to stratified random sampling. Is there anyone
with ideas on how I should do this?

Thanx in advance and kind regards,
Stef

Jul 23 '05 #1
1 4714
On 14 Apr 2005 02:55:06 -0700, "steflhermi tte"
<st************ ***@agr.kuleuve n.ac.be> wrote:
Dear cpp-ians,
[...]The original image I with nrows and ncols is now a vector V of length
(nrow x ncol) and every element of the vector contians its pixel value.

vector float V [nrow * ncol] ;
[...]Now I want to select a stratified pixel of this vector and sample every
pixel till all pixels are sampled once. In the image it would
correspond to divide my image into small blocks and take a pixel of
each block iteratively till all pixels are done.

If I random_shuffle my vector and start at the beginning V till the end
I perform a random sampling, but I now want to add a certain order in
it so it corresponds to stratified random sampling. Is there anyone
with ideas on how I should do this?

As random_shuffle will completely re-order the vector, the original
neighbor relation will be completely lost. I suggest creating a
"StratifiedVect or", whose indexing operator returns a
StratifiedVecto r::Block, which could represent the sequence of
elements in a block from the original vector (like a gslice_array).

template <typename _Scalar,
typename _Container=std: :vector<_Scalar > >
class StratifiedVecto r {
public:
StratifiedVecto r(_Container&,
size_t block_width, size_t block_height);
//define class Block, iterator &c.
...
};

You could then apply random_shuffle to each block. Alternatively,
define Block::sample() which returns a random element of a Block; if
you don't want repeats, Block::sample could internally use a random
sequence of indices. Depending on how you implemented
StratifiedVecto r, every block could use have their own sequence for
Block::sample or share a common one. Shuffling within each block will
produce a random sequence for each block but preserve the
stratification. A random shuffling of a StratifiedVecto r will produce
a random sequence of blocks and thus also preserve stratification.

You could then have two loops, the outer over block indexes and the
inner over the (random) sequence of blocks. Within the inner loop,
take the pixel within the current block. Note that with this
approach, having a different random sequence of blocks for each inner
loop is as expensive as shuffling V (which is what would be
happening). Example:

StratifiedVecto r<float> StratV(V, block_width, block_height);
//following shuffles could be done in StratifiedVecto r's
//constructor. If you provide a Block::sample, shuffling within
//blocks is unnecessary.
for (size_t i=0; i < StratV.size(); ++i) {
random_shuffle( StratV[i].begin(),
StratV[i].end());
}
random_shuffle( StratV.begin(), StratV.end());

size_t block_size=bloc k_width*block_h eight;
for (size_t pixel_i=0; pixel_i < block_size; ++pixel_i) {
/* if you want a different sequence of blocks for each inner loop,
perform random_shuffle here rather than before the outer loop.
Expensive. */
//random_shuffle( StratV.begin(), StratV.end());
for (size_t block_i=0; block_i < StratV.size(); ++block_i)
{
/*Test is for blocks in the last row or column. If block_height
divides nrow and block_width divides ncol, the test can be
skipped.*/
if (pixel_i < StratV[block_i].size()) {
foo(StratV[block_i][pixel_i]);

/*self-sampling version; Block::sample() returns a random
element. If you use Block::sample, remove the above loop
which shuffles each block */
//foo(StratV[block_i].sample());
}
}
}

Alternatively, you could shuffle sequences of indices rather than
blocks or pixels. Producing different random sequences of blocks is
less expensive with this approach, but the extra index vectors are
more space expensive and indirection through them is more time
expensive. Also, each block must use the same random index sequence.
Example:

StratifiedVecto r<float> StratV(V, block_width, block_height);
vector<size_t> SV_idxes(StratV .size());
for (sizt_t i=0; i<SV_idxes.size (); ++i) {
SV_idxes[i]=i;
}
/* could also shuffle SV_idxes inside the outer 'for' loop */
random_shuffle( SV_idxes.begin( ), SV_idxes.end()) ;
vector<size_t> Pixel_idxes(blo ck_width * block_height);
for (sizt_t i=0; i<Pixel_idxes.s ize(); ++i) {
Pixel_idxes[i]=i;
}
random_shuffle( Pixel_idxes.beg in(), Pixel_idxes.end ());
for (size_t pixel_i=0; pixel_i < block_size; ++pixel_i) {
/* if you want a different sequence of blocks for each inner loop,
perform random_shuffle here rather than after creating
SV_idxes. */
//random_shuffle( SV_idxes.begin( ), SV_idxes.end()) ;
for (size_t block_i=0; block_i < SV_idxes.size() ; ++block_i)
{
/*Test is for blocks in the last row or column. If block_height
divides nrow and block_width divides ncol, the test can be
skipped.*/
if (Pixel_idxes[pixel_i] < StratV[SV_idxes[block_i]].size()) {
foo(StratV[SV_idxes[block_i]][Pixel_idxes[pixel_i]]);

/* Self-sampling version. If you use Block::sample() , remove
Pixel_idexes and loop which shuffles it. */
//foo(StratV[block_i].sample());
}
}
}
You could also combine the two approaches by shuffling within each
block and shuffling indices of StratifiedVecto r. This way, each block
will have a different random sequence and shuffling the sequence of
blocks isn't too expensive.

Note StratV.size() equals:
ceil(static_cas t<float>(nrow)/block_height)
*ceil(static_ca st<float>(ncol)/block_width);
If you know block_width and block_height will always be divisors of
nrow and ncol, you can use solely integer arithmetic in
StratifiedVecto r::size().

Kanenas
Jul 23 '05 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
2249
by: Bart Nessux | last post by:
I am using method 'a' below to pick 25 names from a pool of 225. A co-worker is using method 'b' by running it 25 times and throwing out the winning name (names are associated with numbers) after each run and then re-counting the list and doing it all over again. My boss thinks that 'b' is somehow less fair than 'a', but the only thing I...
21
23124
by: Andreas Lobinger | last post by:
Aloha, i wanted to ask another problem, but as i started to build an example... How to generate (memory and time)-efficient a string containing random characters? I have never worked with generators, so my solution at the moment is: import string import random random.seed(14)
5
2891
by: Ross MacGregor | last post by:
I have a very simple yet complicated problem. I want to generate a random list of indices (int's) for a container. Let's say I have a container with 10 items and I want a list of 3 random indices for that container. So I need to generate 3 unique numbers from integer range . There seems to be no simple and efficient way to do this. Any...
5
2217
by: Artyom | last post by:
Hi everybody! Here's the problem: I have an array of 4 integer elements and they must be initialized by random numbers from 0 to 9 that shouldn't repeat. I tried many things, but some elements (for example, first and third ones) continue repeating. Can you propose an algorithm that solves this? Thank you!
16
2109
by: glowfire | last post by:
Please, somebody help me with this program! We have a deck of 52 cards and we shuffle the deck by choosing a random card out of the deck placing it back in the deck at some random place. Repeat it 500 times and then consider the deck shuffled. Choose a hand of 5 cards from the top of the deck. Count the number of hands which have...
2
3281
by: Nelis Franken | last post by:
Good day. Thanks for the previous help on binding member functions to use as predicates for STL functions (original example applied to sort()). The technique to use Boost's bind() works well, except when used with STL's random_shuffle(). The following code demonstrates a working call (on sort()) and a call that generates an error (on...
1
2782
by: Generic Usenet Account | last post by:
I had a need to create my own RandomNumberGenerator class, for use with random_shuffle (I did not want the same sequence generated each time). I looked up an example provided by Nicolai M. Josuttis, in his fantastic book : The C++ Standard Library - A Tutorial and Reference (http://www.josuttis.com/libbook/). Here is what he had: class...
7
2773
by: bipi | last post by:
Dear all, I found function rand(), it can create random number but this function can not define the range of number which I want to get it, such as, I want to get random number in the range from 0 to 100 . Please help me, Many thanks,
1
4633
by: helezem | last post by:
pls cud any one help me with a program that generates samples randomly using simple random sampling
0
7876
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7804
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8310
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7910
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
1
5681
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5366
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3809
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3832
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
0
1144
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.