JP7612412B2 - IMAGE PROCESSING APPARATUS, IMAGE PROCESSING METHOD AND PROGRAM FOR IMAGE PROCESSING APPARATUS - Google Patents

Description

The present invention relates to an image processing device, an image processing method for an image processing device, and a program.

When performing image processing using computers or logic circuits, random numbers are sometimes required. There are two main types of random numbers: true random numbers, which are generated by observing physical phenomena, and pseudo-random numbers, which use a specific algorithm to output values that appear random.

Although pseudorandom numbers are not truly random, because the algorithm is fixed, it is easier to check the quality of the random numbers than with true random numbers. For example, the quality of random numbers can be checked using statistical random number testing methods, such as NIST SP800-22. Therefore, as long as you can confirm that the quality matches the application, there is no problem in using pseudorandom numbers instead of true random numbers.

Pseudorandom numbers also have the advantage of being reproducible. Reproducibility is the property of being able to regenerate the same pseudorandom number sequence. Therefore, if you have an application that requires you to use the same random number sequence multiple times, with true random numbers you would need to store the entire sequence, whereas with pseudorandom numbers you would only need to regenerate it.

There are two main types of pseudo-random numbers: pseudo-random numbers that can be used in encryption, and general pseudo-random numbers that are not used for other purposes. Pseudo-random numbers that can be used in encryption have high quality random numbers, but they are usually generated slowly. Since high quality random numbers are not necessary in image processing, pseudo-random numbers for encryption purposes are not usually used in image processing, and general, simple pseudo-random numbers are used instead.

One simple pseudorandom number algorithm is the linear feedback shift register. Although the linear feedback shift register does not have the quality required for encryption as is, it can be used alone for general random number applications such as image processing. Another example of a pseudorandom number algorithm is Xorshift (see, for example, Non-Patent Document 1).

For example, Patent Document 1 describes a method for enlarging an image by adding pixels to the input image and scattering the added locations using pseudo-random numbers, thereby making the points where the image pattern changes due to the added pixels less noticeable.

Patent document 2 describes a method for preventing multiple pseudo-random number generating circuits from generating the same random numbers by setting different seed values (initial values) for the multiple pseudo-random number generating circuits.

Patent document 3 describes a method of generating different pseudorandom numbers by setting the same initial value to multiple pseudorandom number generating circuits, but changing the position at which the pseudorandom numbers are extracted from the pseudorandom number sequence for each pseudorandom number generating circuit.

Patent Document 4 and Patent Document 5 describe methods for calculating the value of a linear feedback shift register when the phase of the shift register is arbitrarily advanced.

Patent No. 6066955 Japanese Patent Application Publication No. 5-206793 JP 2009-151429 A JP 2003-345246 A Japanese Patent Application Publication No. 11-4144

Marsaglia, "Xorshift RNGs" (2003)

However, in the method of Patent Document 3, when dividing an image into multiple blocks and generating pseudo-random numbers for each block, it is necessary to generate a large number of pseudo-random numbers in a pseudo-random number sequence. Furthermore, Patent Documents 4 and 5 describe a method of advancing the phase, but do not disclose the circuit configuration required for image processing in which an image is divided into multiple blocks, such as how to hold multiple seed values or the timing of generating seed values.

The objective of the present invention is to make it possible to generate multiple seed values in a short time based on a single seed value, so that the pseudo-random number sequences for image processing of each of the multiple blocks into which an image is divided do not collide.

The image processing device of the present invention has a seed value generation means for generating a plurality of seed values for a plurality of blocks into which an image is divided based on one seed value, a pseudo-random number generation means for generating a pseudo-random number sequence for each of the plurality of blocks based on the plurality of seed values for the plurality of blocks, and an image processing means for image processing each of the plurality of blocks into which the image is divided using the pseudo-random number sequence for each of the plurality of blocks, wherein the seed value generation means generates a plurality of pseudo-random numbers as the plurality of seed values, skipping a predetermined number from the pseudo-random number sequence generated by the pseudo-random number generation means based on the one seed value, and changes the predetermined number by changing some bits of one of the plurality of seed values to other bits .

According to the present invention, multiple seed values can be generated in a short time based on one seed value, so that the pseudo-random number sequences for image processing of each of the multiple blocks into which an image is divided do not collide.

FIG. 1 illustrates an example of the configuration of an image processing device. FIG. 2 illustrates an example of the configuration of a pseudo-random number generating unit; FIG. 13 is a diagram showing the transition of values in a shift register. FIG. 13 is a diagram illustrating the process contents of a seed value generating unit. 13 is a diagram for explaining the processing content of a pseudo-random number sequence skip unit. FIG. FIG. 13 is a diagram illustrating an example of the configuration of a pseudo-random number sequence skip unit. FIG. 2 illustrates an example of the configuration of a pseudo-random number generating unit; 13 is a diagram for explaining the processing content of a pseudo-random number sequence skip unit. FIG. 1 is a flowchart illustrating a pseudorandom number generation method of Xorshift. FIG. 2 illustrates an example of the configuration of a pseudo-random number generating unit; FIG. 1 is a diagram illustrating an example of the configuration of a linear feedback shift register. FIG. 13 is a diagram illustrating an example of dividing an input image into a plurality of blocks. FIG. 13 is a diagram showing pixel insertion positions. FIG. 13 is a diagram showing pixel insertion positions.

Figure 11 is a circuit diagram showing an example of the configuration of a linear feedback shift register that generates pseudorandom numbers. Each register of the shift register 1101 holds one bit, so that it can hold five bits in total. When one bit is input from the left, the bit being held is shifted by one. The exclusive-OR calculator 1102 inputs several bits of the shift register 1101, and outputs one bit as the result of the exclusive-OR of the input bits. Each time the shift register 1101 shifts once, one bit of the pseudorandom number is output.

The linear feedback shift register is configured to generate a pseudorandom number with a maximum period. The period of the pseudorandom number depends on the number of bits that the shift register 1101 can hold and the bits input to the exclusive OR calculator 1102. If the number of bits in the shift register 1101 is N, the number of bit states that the shift register 1101 can express is 2 ^N . However, if all the bits in the shift register 1101 are 0, the bits in the shift register 1101 will always be 0, so excluding this one pattern, the number of bit states that the shift register 1101 can express is 2 ^N -1. Therefore, 2 ^N -1 is the maximum period of the pseudorandom number. The input to the exclusive OR calculator 1102 is configured so that the period of the bit state represented by the shift register 1101 is 2 ^N -1. As a result, the period of the pseudorandom number also becomes 2 ^N -1.

Pseudo-random numbers can be used in image processing. Pseudo-random numbers can be used in image processing to make moire and changes in image patterns that occur when enlarging, reducing, or halftoning image data less noticeable. For example, to enlarge an image, pixels are added to the input image. Normally, when pixels are added, the image pattern changes at the location where the addition is made. Therefore, if the pixel addition points are fixed, the points of change in the image pattern that occur at the locations where the pixels were added will be concentrated in one place and stand out. Therefore, by using pseudo-random numbers to spread out the addition points, the points of change in the image pattern due to the addition of pixels can be made less noticeable.

Figure 12 shows an example of dividing an input image into multiple blocks. By performing image processing for each block, it is possible to process multiple blocks in parallel and change the magnification ratio for each block. However, in order to perform image processing for each block, pseudo-random numbers also need to be generated for each block.

Figure 13 shows an example of pixel insertion positions when using the same pseudo-random numbers for each block in Figure 12 to insert pixels. If the same seed value (initial value) is used for each block and the same pseudo-random number sequence is generated for each, pixels will be inserted at the same positions in all blocks. Because pixels are inserted at the same positions in all blocks, changes in the image pattern occur periodically, which may be recognized as a pattern.

For this reason, it is better to use a different pseudo-random number sequence for each block. By setting different seed values (initial values) for multiple pseudo-random number generating circuits, it is possible to prevent the same random numbers from being generated by multiple pseudo-random number generating circuits. However, even if a different seed value is set for each block, because pseudo-random number sequences have a finite period, there is a possibility that the pseudo-random number sequences of multiple blocks may partially collide.

Figure 14 shows an example of pixel insertion positions when the pseudo-random number sequences of multiple blocks partially collide. Because the pseudo-random number sequences of multiple blocks partially collide, the pixel insertion positions of the multiple blocks partially overlap. As a result, the same pattern occurs where multiple blocks overlap. This causes the image pattern to change periodically, which may be recognized as a pattern.

To reliably avoid partial collisions of pseudo-random number sequences like the one above, for example, the same initial value is set for multiple pseudo-random number generating circuits, but the position from which the pseudo-random numbers are extracted from the pseudo-random number sequence is changed for each pseudo-random number generating circuit, thereby avoiding collisions of pseudo-random numbers.

However, when there are a large number of blocks, there is an issue that the amount of calculations required to generate pseudo-random numbers increases. For example, if there are 1,000 blocks, it is necessary to generate 1,000 pseudo-random numbers of the pseudo-random number sequence to extract one pseudo-random number from the pseudo-random number sequence. In image processing, a pseudo-random number may be required for each pixel, so it is necessary to generate pseudo-random numbers with a small amount of calculations while preventing collisions of pseudo-random numbers between blocks.

Another method for avoiding collisions is to store multiple seed values that will not collide in advance, and generate a pseudo-random number sequence using the stored seed values before the start of image processing. However, if non-colliding seed values are generated in advance and all are stored externally, it will require an increase in the number of circuits to store the seed values externally, and it will take time to write the seed values stored externally to the image processing circuit. For example, if there are 1,000 seeds, 1,000 external storage circuits will be required, and if it takes 100 cycles per seed value to write to the image processing circuit, it will take 100,000 cycles to write all the seed values.

To solve the above problem, an embodiment is described below that can generate pseudo-random numbers in a short time during image processing for each block without the need to set seed values for each of the multiple blocks from the outside.

(First embodiment)
1 is a diagram showing an example of the configuration of an image processing device 100 according to the first embodiment. The image processing device 100 has an image processing circuit 101, a pseudo-random number generating unit 102, a plurality of seed value holding units 103, a seed value setting unit 104, a seed value generating unit 105, and a pseudo-random number sequence skip unit 106. An image processing method of the image processing device 100 will be described below.

The image processing circuit 101 performs image processing that requires pseudo-random numbers, such as image enlargement and reduction. The image processing circuit 101 receives an input image, divides the input image into multiple blocks, performs image processing on each block, and outputs an output image.

The pseudo-random number generating unit 102 has a linear feedback shift register and generates a pseudo-random number sequence. The multiple seed value holding units 103 each hold a seed value of a pseudo-random number sequence required for image processing of multiple blocks of an input image. For example, if the image processing circuit 101 divides the image into a maximum of 1024 blocks, the number of seed value holding units 103 is 1024.

The seed value setting unit 104 sets a seed value in one of the multiple seed value holding units 103. This seed value is a seed value required for one of the multiple blocks. When the seed value generation unit 105 confirms that the seed value setting unit 104 has written a seed value in one of the multiple seed value holding units 103, it generates seed values required for other blocks based on the seed value and writes them in the other seed value holding units 103. The pseudo-random number sequence skip unit 106 is used by the seed value generation unit 105 to generate seed values.

Figure 2 is a diagram showing an example of the configuration of the pseudorandom number generating unit 102 in Figure 1. The pseudorandom number generating unit 102 is configured, for example, with a Fibonacci linear feedback shift register. The pseudorandom number generating unit 102 has a shift register 201 and an exclusive OR operator 202.

The shift register 201 is composed of a 31-bit register, and when one bit is input from the left, the bits in all registers are shifted one bit to the right, and the bit that overflows from the right is output as a pseudo-random number. The exclusive-OR calculator 202 inputs the output bit of the shift register 201 and bits from some of the 31-bit registers of the shift register 201. The exclusive-OR calculator 202 then outputs one bit to the first-stage register of the shift register 201 as the result of the exclusive-OR of the input bits. This allows the pseudo-random number generator 102 to generate 31-bit pseudo-random numbers.

3 is a diagram showing the transition of the bit value of the shift register 201 when the Fibonacci linear feedback shift register implemented in the pseudo-random number generator 102 is operated. The seed value 301 represents the initial value of the shift register 201. The transition value 302 represents how the bit value of the shift register 201 transitions when random number generation is repeated once, twice, three times, ..., 2 ³¹ -2 times. The seed value 301 and the transition value 302 are all different values. The transition value 303 is the transition value for the 2 ³¹ -1th time, and becomes the same value as the seed value 301 for the first time in the 2 ³¹ -1th time. The transition value 304 represents the transition value after the 2 ^31st time, and becomes the same value as the transition value 302. In other words, the shift register 201 generates values with periodicity, and repeatedly generates a sequence with 2 ³¹ -1 values represented by the seed value 301 and the transition value 302 as one period.

Since shift register 201 is a 31-bit register, the upper limit of the number of numbers that shift register 201 can represent is 2 ³¹ . However, if all bits are 0, the bit value does not change and therefore it cannot be used to generate random numbers, so the actual upper limit is 2 ³¹ -1. Furthermore, the length of one cycle of bit value transition in shift register 201 is also 2 ³¹ -1. In other words, Figure 3 shows that, from seed value 301 to the 2 ³¹ -1th transition value 303, shift register 201 has gone through all 2 ³¹ -1 values that it can take as values, and then returned to the initial value.

From the above, we can see the following. No matter what seed value 301 is selected, the shift register 201 will have either the seed value 301 or the transition value 302, so the random number sequence generated will only be generated in the order shown in Figure 3.

In other words, the following can be seen regarding seed value 301. First, if the two seed values are the same, the same transition will result, and the same pseudo-random number sequence will be generated. Also, even if the two seed values are different, if two close values are used as seed values in the sequence represented by seed value 301 and transition value 302, the pseudo-random number sequences generated will partially match. Note that using two close values as seed values means that the distance between the seed values is shorter than the number of pseudo-random numbers required for image processing of each block.

When such pseudo-random number sequences collide in image processing, the image processing results for each block may partially match, which may be recognized as a pattern.

To avoid this, this embodiment aims to prevent collisions between the pseudo-random number sequences of each block by setting the seed values of each block to values that are sufficiently separated on the sequence indicated by the seed value 301 and the transition value 302. Setting the seed values of each block to values that are sufficiently separated means setting values that are spaced apart more widely than the maximum number of pseudo-random numbers required for image processing of each block. For example, if a maximum of 1 million pseudo-random numbers are required for each block, collisions can be prevented by setting the seed value interval of each block to 2 million.

Figure 4 is a flowchart showing a processing method of the seed value generation unit 105 of Figure 1. In step S401, the seed value setting unit 104 writes a 31-bit seed value to one of the multiple seed value holding units 103. The seed value generation unit 105 waits for the seed value setting unit 104 to finish writing the 31-bit seed value, and when finished, proceeds to step S402.

In step S402, the seed value generation unit 105 reads the 31-bit seed value written in step S401 from the seed value holding unit 103. Next, in step S403, the seed value generation unit 105 instructs the pseudo-random number sequence skip unit 106 to execute processing, and obtains a seed value for the next block. Next, in step S404, the seed value generation unit 105 writes the seed value obtained in step S403 into another one of the multiple seed value holding units 103.

Next, in step S405, the seed value generation unit 105 determines whether or not all necessary seed values have been written to all seed value holding units 103. If all seed values have not been written, the seed value generation unit 105 returns to step S403 and repeats the processing of seed values for other blocks, and if all seed values have been written, ends the processing of the flowchart in FIG. 4. In this way, the seed value generation unit 105 can cause multiple seed values corresponding to multiple blocks of the input image to be held in multiple seed value holding units 103.

Figure 5 is a diagram for explaining the processing method of the pseudorandom number sequence skip unit 106 in Figure 1. Figure 5 shows the processing contents calculated by the pseudorandom number sequence skip unit 106. The pseudorandom number sequence skip unit 106 is a circuit that outputs a value when the bit value of the linear feedback shift register of the pseudorandom number generation unit 102 shown in Figure 2 is shifted a predetermined number of times. For example, the pseudorandom number sequence skip unit 106 is implemented to output a value after shifting only 2 million times. The input value 501 is the initial 31-bit value of the linear feedback shift register of the pseudorandom number sequence skip unit 106. The exclusive OR operator 502 performs the same processing as the exclusive OR operator 202 in Figure 2. The transition value 503 represents the same value as the result of shifting the bits of the shift register 201 of the pseudorandom number generation unit 102 shown in Figure 2. The output value 504 is the bit value after shifting the bit value of the linear feedback shift register of the pseudorandom number sequence skip unit 106 and generating the transition value 503 2 million times.

Looking at Figure 5, we can see that the only operation between the input value 501 and the output value 504 is the exclusive OR operator 502. In other words, the equation expressing each bit value of the output value 504 can be expressed only by each bit of the input value 501 and the operation of the exclusive OR operator 502.

The formula that only involves the operation of the exclusive OR calculator 502 can be transformed into a simpler formula by modifying the formula. The operations of the exclusive OR calculator 502 are commutative and associative, so the order of calculations can be changed as desired. Furthermore, when an even number of identical values are collected and the exclusive OR is calculated, the result is 0. And the exclusive OR of a certain value and 0 does not change the value, so 0 can be ignored. In other words, all bit values that appear an even number of times in the formula can be ignored. Similarly, all bit values that appear an odd number of times in the formula can be ignored except for one. In other words, the formula that calculates each bit value of the output value 504 can be reduced to a formula that only involves taking the exclusive OR of several selected bit values of the input value 501 without duplication.

Figure 6 is a diagram showing an example of the configuration of the pseudo-random number sequence skip unit 106 in Figure 1. The pseudo-random number sequence skip unit 106 has 31 1-bit calculation units 601. Each of the 31 1-bit calculation units 601 has an exclusive OR operator 604.

The 1-bit calculation unit 601 inputs a 31-bit input value 602 and outputs a 1-bit output value 605. Each of the 31 1-bit calculation units 601 calculates 31 1-bit output values 605.

The input value 602 is a 31-bit input value. The mask 603 selects only some of the bits of the 31-bit input value 602, outputs the selected bits to the exclusive-or calculator 604, and sets the other bits to 0 and outputs them to the exclusive-or calculator 604. The exclusive-or calculator 604 calculates the exclusive-or of the bit values output by the mask 603, and outputs the calculation result as a 1-bit output value 605.

When the bits selected by the mask 603 are fixed, the mask 603 may simply be a wire, and the exclusive-or calculator 604 may calculate the exclusive-or of only the bits connected by the mask 603. As another example of the configuration of the mask 603, the bits selected by the mask 603 may be changed from the outside, so that the interval between each seed value can be changed.

As another example of the configuration of the mask 603, the mask 603 and the exclusive OR calculator 604 can be configured to process one bit at a time, and the one-bit output value 605 can be calculated over 31 cycles. In this case, the number of cycles required for the calculation of the pseudo-random number sequence skip unit 106 increases, but the circuit scale can be further reduced.

In FIG. 6, the pseudo-random number sequence skip unit 106 is configured with 31 1-bit calculation units 601, but as another configuration example, it may be configured with only one 1-bit calculation unit 601. In this configuration, the process of the 1-bit calculation unit 601 is repeatedly executed 31 times to calculate a 31-bit output value 605, which is the same result as in FIG. 6.

As described above, the seed value setting unit 104 writes the 31-bit seed value of the first block to the first seed value holding unit 103 among the multiple seed value holding units 103. After that, the seed value generation unit 105 reads the 31-bit seed value of the first block from the first seed value holding unit 103. Then, the seed value generation unit 105 outputs the 31-bit seed value of the first block to the pseudo-random number sequence skip unit 106 and instructs the calculation of the 31-bit seed value of the second block. As shown in FIG. 5, the pseudo-random number sequence skip unit 106 inputs the 31-bit seed value of the first block as an input value 501, and after 2 million bit shifts, outputs the seed value of the second block to the seed value generation unit 105 as an output value 504. The seed value generation unit 105 writes the seed value of the second block to the second seed value holding unit 103. The interval between the seed value of the first block and the seed value of the second block is 2 million times.

Next, the seed value generation unit 105 outputs the 31-bit seed value of the second block to the pseudo-random number sequence skip unit 106, and instructs it to calculate the 31-bit seed value of the third block. As shown in FIG. 5, the pseudo-random number sequence skip unit 106 inputs the 31-bit seed value of the second block as an input value 501, and after 2 million bit shifts, outputs the seed value of the third block to the seed value generation unit 105 as an output value 504. The seed value generation unit 105 writes the seed value of the third block to the third seed value holding unit 103. The interval between the seed value of the second block and the third seed value is 2 million times.

The seed value generation unit 105 similarly uses the pseudo-random number sequence skip unit 106 to write the 31-bit seed values of all blocks to all seed value storage units 103. The interval between seed values of adjacent blocks is 2 million times.

For the first block of the input image, the image processing circuit 101 reads the seed value of the first block from the first seed value holding unit 103, outputs the seed value of the first block to the pseudo-random number generating unit 102, and instructs the pseudo-random number generation. Then, as shown in FIG. 3, the pseudo-random number generating unit 102 sets the seed value of the first block as the seed value 301 in the shift register 201, generates, for example, one million pseudo-random numbers, and outputs, for example, the one million pseudo-random numbers to the image processing circuit 101. The image processing circuit 101 performs image processing, such as image enlargement/reduction processing, on the first block of the input image, and generates and saves an output image of the first block.

Next, for the second block of the input image, the image processing circuit 101 reads the seed value of the second block from the second seed value holding unit 103, outputs the seed value of the second block to the pseudo-random number generating unit 102, and instructs the pseudo-random number generating unit 102 to generate pseudo-random numbers. Then, as shown in FIG. 3, the pseudo-random number generating unit 102 sets the seed value of the second block as the seed value 301 in the shift register 201, generates, for example, one million pseudo-random numbers, and outputs, for example, the one million pseudo-random numbers to the image processing circuit 101. The image processing circuit 101 performs image processing, such as image enlargement/reduction processing, on the second block of the input image using, for example, the one million pseudo-random numbers, and generates and saves an output image of the second block.

In the same manner, the image processing circuit 101 performs image processing using pseudo-random numbers on each of the third through last blocks of the input image, and generates and saves output images of the third through last blocks. The image processing circuit 101 then integrates the output images of all blocks and outputs the integrated output image.

The pseudo-random number generator 102 can prevent collisions between pseudo-random number sequences in each block of the input image because the interval between seed values of adjacent blocks is 2 million times. The image processing circuit 101 can, for example, prevent overlapping of pixel insertion positions in each block of the input image, and prevent the occurrence of patterns due to periodic changes in the image pattern.

As described above, the seed value setting unit 104 sets one seed value for one seed value holding unit 103. The seed value generation unit 105 uses the pseudo-random number sequence skip unit 106 to generate multiple seed values for multiple blocks into which the input image is divided, based on the single seed value set by the seed value setting unit 104. The pseudo-random number generation unit 102 is a pseudo-random number generation unit, and generates a pseudo-random number sequence for each of the multiple blocks based on the multiple seed values for the multiple blocks. The image processing circuit 101 is an image processing unit, and performs image processing on each of the multiple blocks into which the input image is divided, using the pseudo-random number sequence for each of the multiple blocks.

The seed value generation unit 105 generates multiple pseudo-random numbers by skipping a predetermined number of pseudo-random numbers from the pseudo-random number sequence generated by the pseudo-random number generation unit 102 based on the above-mentioned one seed value, as multiple seed values. The predetermined number is a number greater than the maximum number of pseudo-random numbers used by the image processing circuit 101 for image processing of each block.

The multiple seed values include the one seed value. The seed value setting unit 104 writes the one seed value to one seed value holding unit 103. The seed value generation unit 105 writes the seed values other than the one seed value of the multiple seed values to the other seed value holding units 103.

The pseudorandom number generator 102 generates pseudorandom numbers by performing an exclusive OR operation based on the seed value as shown in Fig. 2. The seed value generator 105 uses the pseudorandom number sequence skip unit 106 to perform an exclusive OR operation on some bits of one of the multiple seed values as shown in Fig. 6, thereby generating another of the multiple seed values.

The pseudo-random number sequence skip unit 106 has a plurality of 1-bit calculation units 601. Each of the plurality of 1-bit calculation units 601 is a bit operation unit that performs an exclusive OR operation on some bits of one of the plurality of seed values to generate one bit of another of the plurality of seed values.

The pseudo-random number sequence skip unit 106 may repeat the process of generating one bit of another of the plurality of seed values by performing an exclusive OR operation on some bits of one of the plurality of seed values. The pseudo-random number sequence skip unit 106 can also change the predetermined number by changing some bits of one of the plurality of seed values to other bits.

In this way, in this embodiment, the seed value generation unit 105 can adjust the interval between seed values held in the seed value holding unit 103. The maximum number of pseudo-random numbers that need to be generated for each seed value can be estimated based on the size of each block, etc., so if the interval between seed values is made wider than that maximum number, it is possible to prevent collisions between the pseudo-random number sequences used in each block.

When the seed value setting unit 104 sets the first seed value, the seed value generation unit 105 can use the pseudo-random number sequence skip unit 106 to automatically generate multiple seed values that do not collide with each other in the pseudo-random number sequence. This eliminates the need to externally set seed values for each of the multiple blocks into which the input image is divided, and allows pseudo-random numbers for image processing of each block to be generated in a short time.

Second Embodiment
The image processing device 100 according to the second embodiment has the same configuration as that of the first embodiment shown in Fig. 1, but the pseudo-random number generating unit 102 is configured with a Galois linear feedback shift register. Even in the case of the Galois linear feedback shift register, the pseudo-random number sequence skip unit 106 can be realized with the configuration shown in Fig. 6 of the first embodiment.

Figure 7 is a diagram showing an example of the configuration of the pseudorandom number generation unit 102 according to the second embodiment. The pseudorandom number generation unit 102 has multiple exclusive OR operators 701 and a shift register 702. The exclusive OR operator 701 inputs 2 bits and outputs a 1-bit result of the exclusive OR of the 2 input bits. The shift register 702 has 31 registers, each of which holds 1 bit, and the entire register holds a 31-bit value. However, several exclusive OR operators 701 are inserted between the 31-bit registers of the shift register 702. The exclusive OR operator 701 takes the exclusive OR of 1 bit input from the previous register and 1 bit output from the output end (right end) of the shift register 702, and outputs 1 bit to the next register. This allows the pseudorandom number generation unit 102 to generate a 31-bit pseudorandom number.

Figure 8 corresponds to Figure 5 of the first embodiment, and is a diagram for explaining the processing method of the pseudo-random number sequence skip unit 106. However, Figure 8 only shows one stage of Figure 5. An input value 801 is the initial 31-bit value of the Galois linear feedback shift register of the pseudo-random number sequence skip unit 106. An exclusive-OR operator 802 performs the same processing as the exclusive-OR operator 701 in Figure 7. A transition value 803 represents the same value as the result of shifting the bits of the shift register 702 in Figure 7.

As can be seen from FIG. 8, the pseudo-random number sequence skip unit 106 of this embodiment performs only the operation of the exclusive OR operator 802. In other words, similar to the results discussed in FIG. 5 of the first embodiment, the pseudo-random number sequence skip unit 106 of this embodiment can also be implemented with the configuration of FIG. 6.

Third Embodiment
The image processing device 100 according to the third embodiment has the same configuration as that of the first embodiment shown in Fig. 1, but the pseudo-random number generating unit 102 is configured with Xorshift. Even in the case of Xorshift, the pseudo-random number sequence skip unit 106 can be realized with the configuration shown in Fig. 6 of the first embodiment.

Figure 9 is a flowchart showing an example of the pseudo-random number generation process of Xorshift in the pseudo-random number generator 102. Here, the variable y is a 32-bit unsigned integer. The variable y represents one value in the pseudo-random number sequence. By the process in Figure 9, the value of the variable y is updated to the value of the next pseudo-random number.

In step S901, the pseudo-random number generation unit 102 takes the exclusive OR of the value of variable y and the value obtained by shifting the value of variable y 13 bits to the left, and assigns the result to variable y. In step S902, the pseudo-random number generation unit 102 takes the exclusive OR of the value of variable y and the value obtained by shifting the value of variable y 17 bits to the right, and assigns the result to variable y. In step S903, the pseudo-random number generation unit 102 takes the exclusive OR of the value of variable y and the value obtained by shifting the value of variable y 5 bits to the left, and assigns the result to variable y. In this way, variable y is generated as a pseudo-random number. Note that in the process of FIG. 9, bits that fall outside the 32-bit range as a result of the left or right shift are ignored.

Figure 10 is a diagram showing the pseudo-random number generation process of Xorshift shown in Figure 9 using an exclusive OR calculator 1002. Figure 10 is also a diagram showing an example of the configuration of the pseudo-random number generator 102 according to this embodiment.

Pseudo-random number value 1001 represents the current 32-bit pseudo-random number value. The pseudo-random number generator 102 uses the circuit in FIG. 10 to determine the next pseudo-random number value 1005 based on the current pseudo-random number value 1001. The exclusive-OR calculator 1002 performs an exclusive-OR operation. The variable 1003 represents the variable y resulting from the calculation in step S901. The variable 1004 represents the variable y resulting from the calculation in step S902. The pseudo-random number value 1005 represents the variable y resulting from the calculation in step S903.

The processing contents of the pseudo-random number sequence skip unit 106 according to this embodiment can be realized by repeating the processing of FIG. 10 as shown in FIG. 5. Looking at FIG. 10, it can be seen that the calculation of the pseudo-random number sequence skip unit 106 of this embodiment is performed only by the exclusive OR operator 1002. In other words, like the first embodiment, the pseudo-random number sequence skip unit 106 of this embodiment can also be implemented with the configuration of FIG. 6.

Other Embodiments
The present invention can also be realized by a process in which a program for implementing one or more of the functions of the above-described embodiments is supplied to a system or device via a network or a storage medium, and one or more processors in a computer of the system or device read and execute the program. The present invention can also be realized by a circuit (e.g., ASIC) for implementing one or more of the functions.

The above embodiments are merely illustrative examples of how the present invention may be implemented, and the technical scope of the present invention should not be interpreted in a limiting manner based on these embodiments. In other words, the present invention can be implemented in various forms without departing from its technical concept or main features.

100 Image processing device, 101 Image processing circuit, 102 Pseudo-random number generation unit, 103 Seed value holding unit, 104 Seed value setting unit, 105 Seed value generation unit, 106 Pseudo-random number sequence skip unit

Claims (12)

a seed value generating means for generating a plurality of seed values for a plurality of blocks obtained by dividing an image based on one seed value;
a pseudo-random number generating means for generating a pseudo-random number sequence for each of the plurality of blocks based on a plurality of seed values for the plurality of blocks;
an image processing means for performing image processing on each of a plurality of blocks obtained by dividing the image, using a pseudo-random number sequence for each of the plurality of blocks;
The image processing device is characterized in that the seed value generation means generates a plurality of pseudo-random numbers, which are generated by skipping a predetermined number from a pseudo-random number sequence generated by the pseudo-random number generation means based on the one seed value, as the plurality of seed values, and changes the predetermined number by changing some bits of one of the plurality of seed values to other bits . The image processing device according to claim 1, characterized in that the predetermined number is a number greater than the maximum number of pseudorandom numbers used by the image processing means for image processing of each block. The image processing device according to claim 1 or 2, further comprising a seed value setting means for setting the one seed value. the plurality of seed values includes the one seed value,
The seed value setting means writes the one seed value,
4. The image processing apparatus according to claim 3, wherein the seed value generating means writes a seed value other than the one seed value among the plurality of seed values. The pseudo-random number generating means generates pseudo-random numbers by performing an exclusive OR operation based on the seed value;
The image processing device according to any one of claims 1 to 4, characterized in that the seed value generation means generates another of the plurality of seed values by performing an exclusive-OR operation on some bits of one of the plurality of seed values. The seed value generating means includes a plurality of bit operation means,
6. The image processing device according to claim 5, wherein each of the plurality of bit operation means generates one bit of another of the plurality of seed values by performing an exclusive OR operation on some bits of one of the plurality of seed values. The image processing device according to claim 5, characterized in that the seed value generating means performs an exclusive OR operation on some bits of one of the plurality of seed values, thereby repeating a process of generating one bit of another of the plurality of seed values multiple times. 8. The image processing device according to claim 1, wherein the pseudo-random number generating means generates the pseudo-random numbers using a Fibonacci linear feedback shift register. 8. The image processing device according to claim 1 , wherein the pseudo-random number generating means generates the pseudo-random numbers using a Galois linear feedback shift register. 8. The image processing device according to claim 1 , wherein the pseudo-random number generating means generates Xorshift pseudo-random numbers. a seed value generating step of generating a plurality of seed values for a plurality of blocks obtained by dividing the image based on one seed value;
a pseudorandom number generating step of generating a pseudorandom number sequence for each of the plurality of blocks based on a plurality of seed values for the plurality of blocks;
and an image processing step of performing image processing on each of a plurality of blocks obtained by dividing the image, using a pseudo-random number sequence for each of the plurality of blocks;
an image processing method for an image processing device, characterized in that in the seed value generation step, a plurality of pseudo-random numbers are generated as the plurality of seed values by skipping a predetermined number from the pseudo-random number sequence generated based on the one seed value in the pseudo-random number generation step, and the predetermined number is changed by changing some bits of one of the plurality of seed values to other bits . A program for causing a computer to function as each of the means of the image processing device according to any one of claims 1 to 10 .

Images