java - getstructuringelement - Implementación más rápida de desenfoque gaussiano

getstructuringelement opencv java

Question

¿Cómo se implementa el algoritmo de desenfoque gaussiano más rápido posible?

Voy a implementarlo en Java, por lo que las soluciones GPU están descartadas. Mi aplicación, planetGenesis , es multiplataforma, así que no quiero JNI .

Answer 1

1. Encontré Quasimondo: Incubator: Processing: Fast Gaussian Blur . Este método contiene muchas aproximaciones, como el uso de números enteros y tablas de búsqueda en lugar de flotantes y divisiones de coma flotante. No sé cuánta aceleración hay en el código Java moderno.

2. Fast Shadows on Rectangles tiene un algoritmo aproximado usando B-splines .

3. El algoritmo de desenfoque gaussiano rápido en C # afirma tener algunas optimizaciones geniales.

4. Además, Fast Gaussian Blur (PDF) de David Everly tiene un método rápido para el procesamiento de desenfoque gaussiano.

Probaría los distintos métodos, los compararía y publicaría los resultados aquí.

Para mis propósitos, he copiado e implementado el método básico (procese el eje XY de forma independiente) y el método Fast Gaussian Blur de David Everly de Internet. Difieren en los parámetros, por lo que no pude compararlos directamente. Sin embargo, este último pasa por un número mucho menor de iteraciones para un gran radio de desenfoque. Además, este último es un algoritmo aproximado.

Answer 2

Consideraría usar CUDA o algún otro kit de herramientas de programación de GPU para esto, especialmente si quiere usar un kernel más grande. Si eso falla, siempre habrá ajustes manuales en el ensamblaje.

Answer 3

Dave Hale de CWP tiene un paquete minejtk, que incluye un filtro gaussiano recursivo (método Deriche y método Van Vliet). La subrutina de Java se puede encontrar en https://github.com/dhale/jtk/blob/0350c23f91256181d415ea7369dbd62855ac4460/core/src/main/java/edu/mines/jtk/dsp/RecursiveGaussianFilter.java

El método de Deriche parece ser muy bueno para el desenfoque gaussiano (y también para los derivados de Gauss).

Answer 4

Debería usar el hecho de que un núcleo gaussiano es separable, es decir, puede expresar una convolución 2D como una combinación de dos convoluciones 1D.

Si el filtro es grande, también puede tener sentido utilizar el hecho de que la convolución en el dominio espacial es equivalente a la multiplicación en el dominio de la frecuencia (Fourier). Esto significa que puede tomar la transformada de Fourier de la imagen y el filtro, multiplicar los resultados (complejos) y luego tomar la transformada de Fourier inversa. La complejidad de la FFT (Transformada rápida de Fourier) es O (n log n), mientras que la complejidad de una convolución es O (n ^ 2). Además, si necesita desenfocar muchas imágenes con el mismo filtro, solo necesitará tomar la FFT del filtro una vez.

Si decides utilizar una FFT, la biblioteca de FFTW es una buena opción.

Answer 5

En 1D:

La difuminación usando casi cualquier kernel repetidamente tenderá a un kernel gaussiano. Esto es lo genial de la distribución gaussiana, y es por eso que a los estadísticos les gusta. Así que elija algo con lo que sea fácil difuminar y aplíquelo varias veces.

Por ejemplo, es fácil desenfocarse con un kernel en forma de caja. Primero calcule una suma acumulativa:

y(i) = y(i-1) + x(i)

entonces:

blurred(i) = y(i+radius) - y(i-radius)

Repite varias veces.

O puede ir y venir unas cuantas veces con una variedad de filtros IIR , estos son igualmente rápidos.

En 2D o superior:

Desenfoque en cada dimensión, una tras otra, como dijo DarenW.

Answer 6

Es probable que desee la imagen borrosa, que es mucho más rápido. Vea este enlace para obtener un excelente tutorial y un código C para copiar y pegar .

Answer 7

Hay varios métodos rápidos para gauss blur de datos 2d. Lo que debes saber

1. Este es un filtro separable, por lo que solo se requieren dos convoluciones de 1d.
2. Para núcleos grandes, puede procesar una copia reducida de la imagen y una copia superior.
3. Se puede hacer una buena aproximación con filtros de múltiples casillas (también separables), (puede ajustarse el número de iteraciones y tamaños de kernel)
4. Existe un algoritmo de complejidad O (n) (para cualquier tamaño de kernel) para una aproximación precisa de Gauss mediante filtro IIR.

Su elección depende de la velocidad requerida, la precisión y la complejidad de la implementación.

Answer 8

He convertido la implementación de Ivan Kuckir de un desenfoque Gaussiano rápido que usa tres pasadas con desenfoque de caja lineal para Java. El proceso resultante es O (n) como lo ha declarado en su propio blog . Si desea obtener más información acerca de por qué la borrosidad de la caja de 3 tiempos se aproxima al desenfoque gaussiano (3%), mi amigo puede ver el desenfoque de la caja y desenfoque gaussiano .

Aquí está la implementación de Java.

@Override
public BufferedImage ProcessImage(BufferedImage image) {
int width = image.getWidth();
int height = image.getHeight();
int[] pixels = image.getRGB(0, 0, width, height, null, 0, width);
int[] changedPixels = new int[pixels.length];
FastGaussianBlur(pixels, changedPixels, width, height, 12);
BufferedImage newImage = new BufferedImage(width, height, image.getType());
newImage.setRGB(0, 0, width, height, changedPixels, 0, width);
return newImage;
}
private void FastGaussianBlur(int[] source, int[] output, int width, int height, int radius) {
ArrayList<Integer> gaussianBoxes = CreateGausianBoxes(radius, 3);
BoxBlur(source, output, width, height, (gaussianBoxes.get(0) - 1) / 2);
BoxBlur(output, source, width, height, (gaussianBoxes.get(1) - 1) / 2);
BoxBlur(source, output, width, height, (gaussianBoxes.get(2) - 1) / 2);
}
private ArrayList<Integer> CreateGausianBoxes(double sigma, int n) {
double idealFilterWidth = Math.sqrt((12 * sigma * sigma / n) + 1);
int filterWidth = (int) Math.floor(idealFilterWidth);
if (filterWidth % 2 == 0) {
filterWidth--;
}
int filterWidthU = filterWidth + 2;
double mIdeal = (12 * sigma * sigma - n * filterWidth * filterWidth - 4 * n * filterWidth - 3 * n) / (-4 * filterWidth - 4);
double m = Math.round(mIdeal);
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
result.add(i < m ? filterWidth : filterWidthU);
}
return result;
}
private void BoxBlur(int[] source, int[] output, int width, int height, int radius) {
System.arraycopy(source, 0, output, 0, source.length);
BoxBlurHorizantal(output, source, width, height, radius);
BoxBlurVertical(source, output, width, height, radius);
}
private void BoxBlurHorizontal(int[] sourcePixels, int[] outputPixels, int width, int height, int radius) {
int resultingColorPixel;
float iarr = 1f / (radius + radius);
for (int i = 0; i < height; i++) {
int outputIndex = i * width;
int li = outputIndex;
int sourceIndex = outputIndex + radius;
int fv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex]);
int lv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex + width - 1]);
float val = (radius) * fv;
for (int j = 0; j < radius; j++) {
val += Byte.toUnsignedInt((byte) (sourcePixels[outputIndex + j]));
}
for (int j = 0; j < radius; j++) {
val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex++]) - fv;
resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
outputPixels[outputIndex++] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
}
for (int j = (radius + 1); j < (width - radius); j++) {
val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex++]) - Byte.toUnsignedInt((byte) sourcePixels[li++]);
resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
outputPixels[outputIndex++] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
}
for (int j = (width - radius); j < width; j++) {
val += lv - Byte.toUnsignedInt((byte) sourcePixels[li++]);
resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
outputPixels[outputIndex++] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
}
}
}
private void BoxBlurVertical(int[] sourcePixels, int[] outputPixels, int width, int height, int radius) {
int resultingColorPixel;
float iarr = 1f / (radius + radius + 1);
for (int i = 0; i < width; i++) {
int outputIndex = i;
int li = outputIndex;
int sourceIndex = outputIndex + radius * width;
int fv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex]);
int lv = Byte.toUnsignedInt((byte) sourcePixels[outputIndex + width * (height - 1)]);
float val = (radius + 1) * fv;
for (int j = 0; j < radius; j++) {
val += Byte.toUnsignedInt((byte) sourcePixels[outputIndex + j * width]);
}
for (int j = 0; j <= radius; j++) {
val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex]) - fv;
resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
outputPixels[outputIndex] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
sourceIndex += width;
outputIndex += width;
}
for (int j = radius + 1; j < (height - radius); j++) {
val += Byte.toUnsignedInt((byte) sourcePixels[sourceIndex]) - Byte.toUnsignedInt((byte) sourcePixels[li]);
resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
outputPixels[outputIndex] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
li += width;
sourceIndex += width;
outputIndex += width;
}
for (int j = (height - radius); j < height; j++) {
val += lv - Byte.toUnsignedInt((byte) sourcePixels[li]);
resultingColorPixel = Byte.toUnsignedInt(((Integer) Math.round(val * iarr)).byteValue());
outputPixels[outputIndex] = (0xFF << 24) | (resultingColorPixel << 16) | (resultingColorPixel << 8) | (resultingColorPixel);
li += width;
outputIndex += width;
}
}
}

Answer 9

He visto varias respuestas en diferentes lugares y las estoy recogiendo aquí para poder tratar de rodearlas y recordarlas para más adelante:

Independientemente del enfoque que utilice, filtre las dimensiones horizontales y verticales por separado con filtros 1D en lugar de usar un solo filtro cuadrado.

• El enfoque estándar "lento": filtro de convolución
• Pirámide jerárquica de imágenes con resolución reducida como en SIFT
• La caja repetida se vuelve borrosa motivada por el Teorema del Límite Central. The Box Blur es fundamental para la detección de rostros de Viola y Jones, donde lo llaman una imagen integral si no recuerdo mal. Creo que las características similares a Haar usan algo similar, también.
• Stack Blur : una alternativa basada en colas en algún lugar entre los enfoques convolucionales y de desenfoque de cajas
• Filtros IIR
  • Derich filtro ( Wikipedia ) segundo orden filtro IIR
  • van Vliet filtro No sé nada sobre este
  • Bessel filtra aunque hay cierto debate sobre estos

Después de revisar todos estos, me recuerda que las aproximaciones simples y pobres a menudo funcionan bien en la práctica. En un campo diferente, Alex Krizhevsky descubrió que ReLU es más rápido que la función sigmoidea clásica en su innovadora AlexNet, aunque a primera vista parecen ser una aproximación terrible al Sigmoid.

Answer 10

Intente usar Desenfoque de cuadro de la manera en que lo hice aquí: Aproximación al desenfoque gaussiano utilizando Desenfoque de cuadro ampliado

Esta es la mejor aproximación.

Al utilizar Imágenes integradas puede hacerlo aún más rápido.
Si lo haces, comparte tu solución.

Answer 11

Los deportistas matemáticos probablemente lo sepan, pero para cualquier otra persona ...

Debido a una buena propiedad matemática del gaussiano, puede desenfocar una imagen en 2D rápidamente ejecutando primero un desenfoque gaussiano 1D en cada fila de la imagen, luego ejecute un desenfoque 1D en cada columna.

Answer 12

Luché con este problema para mi investigación y probé un método interesante para una rápida difuminación Gaussiana. Primero, como se mencionó, es mejor separar el desenfoque en dos desenfoques 1D, pero dependiendo de su hardware para el cálculo real de los valores de píxel, puede calcular previamente todos los valores posibles y almacenarlos en una tabla de búsqueda.

En otras palabras, precalcule cada combinación de Gaussian coefficient * input pixel value . Por supuesto, tendrá que discretizar sus coeficientes, pero solo quería agregar esta solución. Si tiene una suscripción IEEE , puede leer más en Desenfoque rápido de imágenes usando la Tabla de búsqueda para la extracción de características en tiempo real .

Finalmente, terminé usando CUDA :)

Answer 13

Para radios de desenfoque más grandes, intente aplicar una borrosidad de cuadro tres veces. Esto se aproximará muy bien a un desenfoque gaussiano, y será mucho más rápido que un verdadero desenfoque gaussiano.

Answer 14

Respondiendo a esta vieja pregunta con nuevas bibliotecas que se han implementado ahora (a partir de 2016), porque hay muchos avances en la tecnología GPU con Java.

Como se sugiere en algunas otras respuestas, CUDA es una alternativa. Pero java tiene soporte de CUDA ahora.

Biblioteca IBM CUDA4J: proporciona una API Java para gestionar y acceder a dispositivos, bibliotecas, núcleos y memoria de la GPU. Con estas nuevas API, es posible escribir programas Java que administren las características de los dispositivos GPU y descarguen trabajos a la GPU con la comodidad del modelo de memoria Java, excepciones y administración automática de recursos.

Jcuda: enlaces de Java para NVIDIA CUDA y bibliotecas relacionadas. Con JCuda es posible interactuar con el tiempo de ejecución de CUDA y la API de controladores de los programas de Java.

Aparapi: permite a los desarrolladores de Java aprovechar la potencia de cómputo de los dispositivos GPU y APU ejecutando fragmentos de código paralelos de datos en la GPU en lugar de limitarse a la CPU local.

Algunas bibliotecas de enlaces Java OpenCL

https://github.com/ochafik/JavaCL : enlaces de Java para OpenCL: una biblioteca de OpenCL orientada a objetos, basada en enlaces de bajo nivel generados automáticamente

http://jogamp.org/jocl/www/ : enlaces de Java para OpenCL: una biblioteca de OpenCL orientada a objetos, basada en enlaces de bajo nivel generados automáticamente

http://www.lwjgl.org/ : enlaces de Java para OpenCL: enlaces de bajo nivel generados automáticamente y clases de conveniencia orientadas a objetos

http://jocl.org/ : enlaces Java para OpenCL: enlaces de bajo nivel que son una asignación 1: 1 de la API original de OpenCL

Todas estas bibliotecas anteriores ayudarán a implementar Gaussian Blur más rápido que cualquier implementación en Java en la CPU.

Answer 15

SOLUCIÓN ÚLTIMA

Estaba muy confundido por tanta información e implementaciones, que no sabía en cuál debería confiar. Después de que me di cuenta, decidí escribir mi propio artículo. Espero que te ahorre horas de tiempo.

Desenfoque gaussiano más rápido (en tiempo lineal)

Contiene el código fuente, que (espero) es corto, limpio y fácilmente regrabable en cualquier otro idioma. Por favor vote, para que otras personas puedan verlo.

Answer 16

• Paso 1: Desdibujo Gaussiano SIMD 1-dimensional
• Paso 2: transponer
• Paso 3: repite el paso 1

Se realiza mejor en bloques pequeños, ya que una transposición de imagen completa es lenta, mientras que una transposición de bloque pequeño se puede hacer extremadamente rápido usando una cadena de PUNPCKs ( PUNPCKHBW, PUNPCKHDQ, PUNPCKHWD, PUNPCKLBW, PUNPCKLDQ, PUNPCKLWD ).