Interpretación inaceptable Lectura Transparente .png Pixel by Pixel

Estoy creando una herramienta que detecta sprites en una hoja de sprites y convierte cada sprite encontrado en una nueva image Buffenetworking. Este process funciona, pero es prohibitivamente lento con ciertos formattings de image, principalmente imágenes transparentes, como esta:

Kenney's Game Assets - Animal Pack - Round

( Activos del juego de Kenney – Paquete de animales )

He creado un perfil de mi código y he determinado que la gran mayoría, en más del 99% del time de mi aplicación, se gasta solo en este método debido a las muchas llamadas a getRGB() .

 private fun findContiguousSprite(image: BuffenetworkingImage, startingPoint: Point, backgroundColor: Color): List<Point> { val unvisited = LinkedList<Point>() val visited = arrayListOf(startingPoint) unvisited.addAll(neighbors(startingPoint, image).filter { Color(image.getRGB(it.x, it.y)) != backgroundColor }) while (unvisited.isNotEmpty()) { val currentPoint = unvisited.pop() val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y)) if (currentColor != backgroundColor) { unvisited.addAll(neighbors(currentPoint, image).filter { !visited.contains(it) && !unvisited.contains(it) && (Color(image.getRGB(it.x, it.y)) != backgroundColor) }) visited.add(currentPoint) } } return visited.distinct() } 

He intentado optimizar el process de extracción de colors rgb como se ve en la pregunta Java: get matriz de píxeles de la image accediendo al búfer de datos ráster de la image, pero esto falla en las versiones más nuevas de Java con java.lang.ClassCastException: java.awt.image.DataBufferInt cannot be cast to java.awt.image.DataBufferByte .

Otros obstáculos incluyen el boxeo innecesariamente innecesario de colors, como en la línea Color(image.getRGB(it.x, it.y)) != backgroundColor . Sin embargo, mientras que image.getRGB() regresa por defecto en el espacio de color RGBA, background.rgb solo devuelve el espacio de color sRGB.

Pregunta: ¿Cómo puedo mejorar el performance de la lectura de una BuffenetworkingImage especialmente en el caso de imágenes transparentes? ¿Por qué es tan rápido con casi cualquier otra image .png que arrojo, excepto por estos?

Nota: Si bien el código está en Kotlin, acepto Java o cualquier otro lenguaje JVM como respuesta.

Volcado de código: en caso de que quiera la sección completa del código:

 private fun findSpriteDimensions(image: BuffenetworkingImage, backgroundColor: Color): List<Rectangle> { val workingImage = image.copy() val spriteDimensions = ArrayList<Rectangle>() for (pixel in workingImage) { val (point, color) = pixel if (color != backgroundColor) { logger.debug("Found a sprite starting at (${point.x}, ${point.y})") val spritePlot = findContiguousSprite(workingImage, point, backgroundColor) val spriteRectangle = spanRectangleFrom(spritePlot) logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}") spriteDimensions.add(spriteRectangle) workingImage.erasePoints(spritePlot, backgroundColor) } } return spriteDimensions } private fun findContiguousSprite(image: BuffenetworkingImage, startingPoint: Point, backgroundColor: Color): List<Point> { val unvisited = LinkedList<Point>() val visited = arrayListOf(startingPoint) unvisited.addAll(neighbors(startingPoint, image).filter { Color(image.getRGB(it.x, it.y)) != backgroundColor }) while (unvisited.isNotEmpty()) { val currentPoint = unvisited.pop() val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y)) if (currentColor != backgroundColor) { unvisited.addAll(neighbors(currentPoint, image).filter { !visited.contains(it) && !unvisited.contains(it) && (Color(image.getRGB(it.x, it.y)) != backgroundColor) }) visited.add(currentPoint) } } return visited.distinct() } private fun neighbors(point: Point, image: Image): List<Point> { val points = ArrayList<Point>() val imageWidth = image.getWidth(null) - 1 val imageHeight = image.getHeight(null) - 1 // Left neighbor if (point.x > 0) points.add(Point(point.x - 1, point.y)) // Right neighbor if (point.x < imageWidth) points.add(Point(point.x + 1, point.y)) // Top neighbor if (point.y > 0) points.add(Point(point.x, point.y - 1)) // Bottom neighbor if (point.y < imageHeight) points.add(Point(point.x, point.y + 1)) // Top-left neighbor if (point.x > 0 && point.y > 0) points.add(Point(point.x - 1, point.y - 1)) // Top-right neighbor if (point.x < imageWidth && point.y > 0) points.add(Point(point.x + 1, point.y - 1)) // Bottom-left neighbor if (point.x > 0 && point.y < imageHeight - 1) points.add(Point(point.x - 1, point.y + 1)) // Bottom-right neighbor if (point.x < imageWidth && point.y < imageHeight) points.add(Point(point.x + 1, point.y + 1)) return points } 

Primera optimization

Impulsado por el comentario de @Durandal, decidí cambiar mi ArrayList a HashSet. También encontré una forma de preservar los valores alfa usando un constructor alternativo para Color, Color(rgb, preserveAlpha) . Ahora ya no necesito boxear getRGB() antes de comparar los dos valores.

 private fun findContiguousSprite(image: BuffenetworkingImage, point: Point, backgroundColor: Color): List<Point> { val unvisited = LinkedList<Point>() val visited = hashSetOf(point) unvisited.addAll(neighbors(point, image).filter { image.getRGB(it.x, it.y) != backgroundColor.rgb }) while (unvisited.isNotEmpty()) { val currentPoint = unvisited.pop() val currentColor = image.getRGB(currentPoint.x, currentPoint.y) if (currentColor != backgroundColor.rgb) { unvisited.addAll(neighbors(currentPoint, image).filter { !visited.contains(it) && !unvisited.contains(it) && image.getRGB(it.x, it.y) != backgroundColor.rgb }) visited.add(currentPoint) } } return visited.toList() } 

Esto procesó la image de arriba en 319ms . ¡Increíble!

Usar contains en una ArrayList o LinkedList tiene complejidad O (n). Esto puede convertirse rápidamente en una gran sobrecarga, considerando que está haciendo muchas llamadas a contains () en su filter. La complejidad de la búsqueda visitada.contiene () crece con el tamaño de la image procesada (más píxeles para visitar y más píxeles visitados, convirtiendo la complejidad en O (n ^ 2)).

La forma más sencilla de networkingucir este costo es usar un tipo de colección que contenga un resumen rápido; como O (1) en el caso de HashSet. La semántica Set también se ajusta a sus requisitos un poco mejor que las lists, ya que entiendo que las collections visitadas / no visitadas no deben permitir duplicates. Como Sets no permite duplicates por contrato, algunos de los controles de contenido explícito pueden eliminarse; en los lugares que desee responder al evento del punto que se agrega primero, también puede hacer uso del resultado boolean que el método add () da (verdadero cuando el elemento no estaba presente y se agregó).

Si bien el boxeo / unboxing cuesta algo de time, es un costo lineal. La networkingucción de la sobrecarga del boxeo requerirá bastantes cambios en el código y "solo" obtendrá una aceleración de factor constante. Las collections estándar no funcionan con primitivas (sin el autoboxing que desea evitar en primer lugar). Si bien hay collections de terceros de propósito especial (se me ocurre Trove) que manejan primitivas sin boxeo. Solo iría de esta manera si fuera absolutamente necesario, cambiar a types primitivos donde sea posible haría que tu código sea más largo y algo más ofuscado.

  • Gradle. Kotlin: ¿es posible crear tareas dinámicas ("en vuelo")?
  • ¿Por qué Kotlin no puede anular el método del operador List <*>?
  • Cómo analizar JSON desde una url usando Kotlin en Android?
  • Kotlin suprime 'la condición es siempre verdadera'
  • ¿Por qué el signo más debe estar al final de la línea en lugar de al principio en la línea siguiente?
  • OnComplete nunca se llamó con toSortedList () y groupBy ()
  • La animation no funciona al save en la database?
  • Cómo aplicar el tipo genérico con la interoperabilidad de Kotlin
  • Kotlin: ¿Por qué el más / less unario no puede inferir el tipo genérico de la asignación?
  • iniciar bash con contacto como vCard en cadena
  • Kotlin getter setter sin campo