Método de dividir el espacio multidimensional según la distribución de datos coordinados
Descripción general
 Aunque la división espacial se realiza como un medio para resolver diversos problemas de optimización no lineal en el espacio multidimensional, se realizó a expensas de la precisión o el tiempo con la estructura de datos convencional tal como está. Está dirigido a hacerlo con la memoria de ahorro y alta velocidad, manteniendo una alta precisión. ] Al organizar los datos de coordenadas en una dimensión en lugar de en una matriz multidimensional, se reduce el acceso innecesario a áreas sin coordenadas y se reorganiza en una matriz dimensional cada vez que se realiza una división de espacio, El rango de exploración necesario para el procesamiento estadístico para la división se minimiza.
Campo técnico
La presente invención es un método ventajoso en términos de mayor precisión, ahorro de memoria o mayor velocidad en comparación con el método convencional cuando se comprueba la distribución de datos en el espacio multidimensional, optimizando y distribuyendo datos en la computadora. Por ejemplo, es efectivo en los siguientes campos.
 Mejore la calidad de la imagen, especialmente en la escena de visualización de color limitada de imágenes a todo color.
 Aprendizaje no lineal Hemos acelerado el problema del aprendizaje utilizando la red RCE convencional, la red neuronal, el algoritmo genético (GA), etc. Como una posibilidad, previsión del precio de las acciones, por ejemplo. Estime la probabilidad de divorcio según la hipótesis astrológica. Previsión a largo plazo en el pronóstico del tiempo. Examen de entrada en una compañía de ventas de crédito. Se puede aplicar a un dispositivo para discriminar si es una belleza de una imagen o similar.
 Geometría computacional, problema de vendedor ambulante. Por ejemplo, acelere el movimiento del taladro en la placa de circuito impreso. Además, problema de optimización geográfica P1. Por ejemplo, optimización de publicación de buzón.
Antecedentes de la técnica
En los campos que se ocupan de la optimización no lineal en el espacio multidimensional, hay procesamiento de imágenes, aprendizaje no lineal, geometría computacional, etc. En cada uno, había un dispositivo para acelerar dividiendo el espacio multidimensional. Como documento relacionado,
1) aprendizaje no lineal
Documento 1) La red RCE se introdujo en 'interfaz' antes de 1989. Es como una red neuronal de tipo autoorganizada simplificada, se agregan datos de aprendizaje, y cada vez que se produce el resultado de la predicción y la discrepancia de datos real, se agrega una esfera en el espacio multidimensional, se cambia el radio de la esfera . Sin embargo, como esto es demasiado simplista y no se puede ajustar el peso para cada eje, me preocupaba abordar el problema de dos o más dimensiones, y después de eso, en enero de 1990, comencé Bayesiano Estoy escribiendo sobre las estadísticas y el método utilizando la divergencia de Kalvac en la comunicación de la computadora personal. Sin embargo, lo que se realizó en ese momento fue un espacio unidimensional.
Referencia 2) 'Ciencia matemática' alrededor de 1992, 'Interfaz' Además, Hiroaki Kitano en 'Algoritmo genético', Algoritmo genético utilizando la ecuación de regresión múltiple binaria y secundaria como elemento de procesamiento (PE) Estoy escribiendo un articulo Debido a las limitaciones de los criterios de MDL, se unifica a la ecuación de regresión binaria de segundo orden binario, por lo que hay muchas partes donde se desperdicia el tiempo de cálculo. Además, toma demasiado tiempo porque depende demasiado de los elementos accidentales más de lo necesario.
2) Base de datos
Literatura 3) 'Interfaz' En el número anterior y posterior a agosto de 1990, para la recuperación de bases de datos, un pequeño método para acelerar la búsqueda en múltiples términos dividiendo y dividiendo recursivamente el espacio multidimensional en dos Un artículo estaba en eso.
3) Literatura en pantalla de color limitada (a veces el término color sustractivo, la cuantización del color a veces se usa). Tenga en cuenta que la pantalla de color limitado significa organizar colores más representativos en la porción de color con alta frecuencia de uso en el espacio de color al utilizar el hecho de que los colores utilizados para la imagen a todo color no son uniformes y están sesgados, Este es un método para aproximar una imagen con un pequeño número de bits, como 8 bits en lugar de 24 bits, al reemplazar el color vecino en la imagen original con el color representativo.
Documento 4), pero hay un artículo que el método de visualización de color que puede reflejar la preferencia del diseñador especificando el área importancia de 'Diario de televisión' 1991/1, en lugar de los algoritmos que van de un espacio de color dividido en dos limita, básicamente, Es un algoritmo para agregar colores frecuentes a colores representativos, y no hay ningún programa que use este tipo de algoritmo y logre una buena calidad de imagen. Los autores también parecen apuntar a la velocidad más que a la calidad de la imagen con el video como objetivo final. Dado que se hizo posible procesar con una precisión creciente con la aceleración de acuerdo con la presente invención, se eliminan los contornos falsos que aparecen en la pantalla de 256 colores, a menos que se manejen imágenes de gran tamaño de aproximadamente 1200 * 900, Incluso cuando se solicita una alta calidad de imagen, el procesamiento interactivo humano se vuelve innecesario. El método de visualización de color limitada no es una forma o el método de dividir el espacio en dos puede realizar la mejor calidad de imagen. Entre ellos, la presente invención realiza mejoras en este método.
Referencia 5) 'Algoritmo de partición de heterogeneidad por Heckbert' para el 'manual de análisis de imágenes' (para la división mediana,
Tarea de solución
La presente invención está concebida para satisfacer todo el consumo de memoria, precisión y velocidad.
1) Alinee coordenadas, frecuencias y datos de clasificación en una dimensión.
1) Dado que los datos tienen una matriz unidimensional en el momento de la división del espacio, la memoria no se desperdicia.
2) La velocidad no difiere mucho más que restar una gran matriz multidimensional porque solo pasa por los punteros 1 o 2 veces. Incluso en el caso de establecer datos de coordenadas en la memoria, no tiene que sacrificar memoria, velocidad y precisión porque solo coloca los datos originales en una matriz unidimensional del tamaño requerido. En la escena para obtener un histograma unidimensional para cada eje para determinar el punto de división, dado que solo se escanean los datos de coordenadas necesarios y se vuelve a calcular la información estadística, no se desperdicia el tiempo.
3) El procesamiento de reordenamiento aumenta, pero si se suma, será más rápido. Dado que las muestras reales no dispuestos en todos los puntos en los puntos de rejilla, en comparación con los algoritmos que posee los datos en una matriz multidimensional, la memoria que necesita ser asegurado incluso, para ser escaneada para la memoria procesamiento estadístico También es muy reducido. Simultáneamente con dividir el espacio en dos, la sección correspondiente en la matriz unidimensional también se divide en dos, de modo que el procesamiento para examinar los puntos a dividir a continuación se puede minimizar. En comparación con un algoritmo que crea un índice multidimensional grueso y le salta punteros desde la estructura de la lista, se reduce la cantidad de datos a escanear, y es más fácil escanear una matriz unidimensional que seguir la estructura de la lista. Entonces se vuelve más rápido.
Ejemplo 1) Programa para realizar una visualización de color limitada (color reducido) a una alta calidad de imagen
1.1) Los datos de coordenadas tienen una matriz unidimensional de estructuras
En el caso de la reducción de color, el espacio a dividir es el espacio de color. El sistema de coordenadas no está limitado a RGB, pero es concebible usar YIQ o Luv. Además, cuando se usa RGB, al ponderar G, R, B en orden, se pueden reducir los contornos falsos. Cuando los mismos datos de coordenadas aparecen repetidamente en datos de coordenadas multidimensionales que se convierten en la imagen original, es necesario un preprocesamiento para examinar la frecuencia del mismo color. En esta etapa, se examina la frecuencia de las muestras para cada coordenada en el espacio de color utilizando una estructura de datos convencional, como una matriz multidimensional, una combinación de una matriz multidimensional y una lista, y un hash para administrar la duplicación. Después de eso, todos los datos de coordenadas se organizan en una dimensión.
DESCRIPCIÓN DETALLADA DE LAS FORMAS DE REALIZACIÓN PREFERIDAS
Efecto de la invención
Cuando se aplica a la visualización de colores limitada para llevar a cabo seleccionar los mejores 256 colores en 16 millones de colores, una mejora significativa se observa, en el antiguo algoritmo, en el 10000 color equivalente de calidad de imagen, decenas de miles a cientos de miles de colores equivalente de Casi la optimización límite se puede hacer sin sacrificar el tiempo. Estudié más de 20 tipos de programas que usan la paleta de optimización, pero incluso cuando se compara con un programa extremadamente lento, obtuvo una alta calidad de imagen debido a la diferencia en comparación con la que tiene aproximadamente la misma velocidad o más. Además, como resultado de aplicarlo al problema del vendedor itinerante en el espacio euclidiano bidimensional, se puede obtener una solución aproximada de aproximadamente el error de aproximadamente el 25% en un tiempo más corto que antes de obtener una solución de error aproximada de aproximadamente el 40%. Incluso cuando se aplica a la selección de modelos estadísticos no lineales multidimensionales basados ​​en AIC, la parte que se basa en métodos heurísticos como GA es limitada, por lo que la velocidad aumenta y la capacidad de memoria necesaria para mantener el resultado de aprendizaje También disminuyó bruscamente.
BREVE RESUMEN DE LA INVENCIÓN
Figura 2 Al dividir con el primer componente principal
Escaneado innecesario que ocurre cuando no se divide en un plano no perpendicular al eje de la Figura 3
Figura 4 Al dividir por múltiples ecuaciones de regresión múltiple
Figura 5 Cuando se aplica al problema del vendedor viajero
Reclamo
Reivindicación 1 Un método para dividir secuencialmente un espacio multidimensional según una distribución de datos de coordenadas incluye 1) organizar los datos de coordenadas en una sola dimensión, 2) ordenar los datos de coordenadas dentro de un área dividida Un método en el que se agrega el procesamiento de reorganización para que los datos de coordenadas se posicionen en una región continua incluso en una matriz unidimensional.
En el método de visualización de color limitada de una imagen a todo color, en cuanto al método de dividir secuencialmente el espacio de color de acuerdo con la distribución de color, 1) organice los datos de coordenadas y la frecuencia de forma unidimensional, 2) , Un método de reorganización para que los datos de coordenadas en las mismas regiones divididas divididas se posicionen en la región continua incluso en una matriz unidimensional.
Reivindicación 3 Un método de aprendizaje y predicción de un ejemplo anterior se refiere a un método para dividir sucesivamente un espacio multidimensional de acuerdo con la distribución de datos de coordenadas en un espacio multidimensional abarcado por una variable explicativa: 1) 2) Un método de reorganización para que los datos de coordenadas en la misma región individual segmentada estén ubicados en la región continua incluso en una matriz unidimensional cada vez que se divide la región.
En un método para resolver un problema que puede ser reducido a un problema del viajante (TSP) en la reivindicación 4 el espacio euclidiano, las coordenadas de un punto dado que se deben pasar, como para reducir la suma de los cuadrados de los errores del centro de gravedad de la región , 1) los datos de coordenadas están dispuestos en una dimensión, 2) cada vez que se divide el área, los datos de coordenadas en el mismo área dividida dividida también son continuos en una matriz unidimensional Cómo reorganizar para que esté ubicado en el área.
Dibujo :
Application number :1997-006755
Inventors :松岡肇
Original Assignee :松岡肇