5 ms·

Image color replacement with numerical optimization

78 points by andersource 5y ago

danuker 5y ago
Very interesting! They look a bit surreal, as if inverted maybe.
- andersource 5y ago
  Thanks! Yeah, I think one thing the simplistic optimization is missing is preserving the "texture" of the image. There are various numeric ways to represent textures so this is something that potentially could be added to the objective, it was out of scope for the project though. Might give it a try some day!
tyingq 5y ago
A more pedestrian imagemagick script that uses a "fuzz value" that's a number of degrees on a hue wheel instead: http://www.fmwconcepts.com/imagemagick/replacecolor/index.php http://www.fmwconcepts.com/imagemagick/replacecolor/index.ph...
kirillcool 5y ago
"Flowers replaced to red" looks like it also tinted the whole sky red. In general, all the image captions imply that the algorithm is able to identify objects (flowers, ice cream scoop, shirt) and only change that object's color.
- andersource 5y ago
  > "Flowers replaced to red" looks like it also tinted the whole sky red. That's true, to me at least it looks like in the original image the sky has a yellow undertone so I think it makes sense
- bluetwo 5y ago
  Yes, what he is really doing is what's known in photography and video as "color grading". where you narrow or short the hues used in an image.
maurits 5y ago
Pretty clever. Somewhat related, if you want to match the colours of an entire image to an other, you can use optimal transport [1] Unrelated, the author has a very nice take on generating the organic grid from Oskar Stålberg’s Townscaper game [2]. [1]: https://codimd.math.cnrs.fr/s/2eRBqV9zl https://codimd.math.cnrs.fr/s/2eRBqV9zl [2]: https://andersource.dev/2020/11/06/organic-grid.html https://andersource.dev/2020/11/06/organic-grid.html
- vanderZwan 5y ago
  Here is a JavaScript implementation by Fil: https://observablehq.com/@fil/sliced-optimal-transport https://observablehq.com/@fil/sliced-optimal-transport
- andersource 5y ago
  Thanks! The optimal transport is really cool!
- lostinthefield 5y ago
  As someone who's not trained in math, what does "optimal transport" mean?
  - dandelany 5y ago
    Let’s say we have 12 iron mines with known amounts of iron ore supply, and 10 steel foundries with known amounts of demand. For each (mine, foundry) pair, there is a known cost of shipping the ore from point A to B. Which mines should send how much ore to which foundries? AIUI, that is the general “optimal transport problem”. Now replace ore with colors and it applies to the problem above :)
- Doxin 5y ago
  re: link #2 While that is a much simpler solution and quite a nice writeup, it doesn't quite solve the problem that townscaper poses. For that it needs to be infinitely expandable, which is quite a different feat.
adampk 5y ago
Sorry for the noob question but reading through this I can't make sense of why this is the desired transformation: "Desired transformation: σ(σ(IT)N)" What is I, T, and N?
- andersource 5y ago
  Hey! I is the flattened image (i.e., a matrix where each row represents the RGB values of a single pixel) T and N are some matrices, basically of appropriate dimensions such that the transformation you quoted results in an image of the same shape as the original and also such that we can optimize certain objectives with respect to the variables that define the transformation. The why this is the desired transformation is a tricky question, it's definitely not the only and quite probably not the best way to formulate this problem - just the first way that I tried and worked reasonably well. I tried to explain my intuition for this in the article after the definition.
  - adampk 5y ago
    Really appreciate the response thank you, great article! So is "T" and "N" conventionally used in numerical optimization as the transform "variables" (like X and Y are in calculus)?
    - andersource 5y ago
      Gladly! > So is "T" and "N" conventionally used in numerical optimization as the transform "variables" (like X and Y are in calculus)? Not really, numerical optimization offers a general toolbox for various problems, which are usually defined based on domain-specific notation and concepts. So the concept of a transformation like the one described in the article is not general to numerical optimization, but specific to the optimization being done here. That being said, when talking about techniques, theorems and algorithms in numeric optimization there are conventions. So you usually move between the more theory-oriented notation to a domain-specific notation (in the article I mostly used the domain-specific, lazy notation I chose). Bear in mind that my perspective is not very academic so I might feel less strongly about (and be less aware of) rigorous mathematical conventions.
pajko 5y ago
Also there is https://www.cs.huji.ac.il/~yweiss/Colorization/ https://www.cs.huji.ac.il/~yweiss/Colorization/ Had implemented a Khoros filter box based on this for my Computer Graphics class back then.

78 points by andersource 5y ago

danuker 5y ago

Very interesting! They look a bit surreal, as if inverted maybe.

andersource 5y ago
Thanks! Yeah, I think one thing the simplistic optimization is missing is preserving the "texture" of the image. There are various numeric ways to represent textures so this is something that potentially could be added to the objective, it was out of scope for the project though. Might give it a try some day!

tyingq 5y ago

A more pedestrian imagemagick script that uses a "fuzz value" that's a number of degrees on a hue wheel instead: http://www.fmwconcepts.com/imagemagick/replacecolor/index.php http://www.fmwconcepts.com/imagemagick/replacecolor/index.ph...

kirillcool 5y ago

"Flowers replaced to red" looks like it also tinted the whole sky red. In general, all the image captions imply that the algorithm is able to identify objects (flowers, ice cream scoop, shirt) and only change that object's color.

andersource 5y ago
> "Flowers replaced to red" looks like it also tinted the whole sky red. That's true, to me at least it looks like in the original image the sky has a yellow undertone so I think it makes sense
bluetwo 5y ago
Yes, what he is really doing is what's known in photography and video as "color grading". where you narrow or short the hues used in an image.

maurits 5y ago

Pretty clever. Somewhat related, if you want to match the colours of an entire image to an other, you can use optimal transport [1] Unrelated, the author has a very nice take on generating the organic grid from Oskar Stålberg’s Townscaper game [2]. [1]: https://codimd.math.cnrs.fr/s/2eRBqV9zl https://codimd.math.cnrs.fr/s/2eRBqV9zl [2]: https://andersource.dev/2020/11/06/organic-grid.html https://andersource.dev/2020/11/06/organic-grid.html

vanderZwan 5y ago
Here is a JavaScript implementation by Fil: https://observablehq.com/@fil/sliced-optimal-transport https://observablehq.com/@fil/sliced-optimal-transport
andersource 5y ago
Thanks! The optimal transport is really cool!
lostinthefield 5y ago
As someone who's not trained in math, what does "optimal transport" mean?
- dandelany 5y ago
  Let’s say we have 12 iron mines with known amounts of iron ore supply, and 10 steel foundries with known amounts of demand. For each (mine, foundry) pair, there is a known cost of shipping the ore from point A to B. Which mines should send how much ore to which foundries? AIUI, that is the general “optimal transport problem”. Now replace ore with colors and it applies to the problem above :)
Doxin 5y ago
re: link #2 While that is a much simpler solution and quite a nice writeup, it doesn't quite solve the problem that townscaper poses. For that it needs to be infinitely expandable, which is quite a different feat.

adampk 5y ago

Sorry for the noob question but reading through this I can't make sense of why this is the desired transformation: "Desired transformation: σ(σ(IT)N)" What is I, T, and N?

andersource 5y ago
Hey! I is the flattened image (i.e., a matrix where each row represents the RGB values of a single pixel) T and N are some matrices, basically of appropriate dimensions such that the transformation you quoted results in an image of the same shape as the original and also such that we can optimize certain objectives with respect to the variables that define the transformation. The why this is the desired transformation is a tricky question, it's definitely not the only and quite probably not the best way to formulate this problem - just the first way that I tried and worked reasonably well. I tried to explain my intuition for this in the article after the definition.
- adampk 5y ago
  Really appreciate the response thank you, great article! So is "T" and "N" conventionally used in numerical optimization as the transform "variables" (like X and Y are in calculus)?
  - andersource 5y ago
    Gladly! > So is "T" and "N" conventionally used in numerical optimization as the transform "variables" (like X and Y are in calculus)? Not really, numerical optimization offers a general toolbox for various problems, which are usually defined based on domain-specific notation and concepts. So the concept of a transformation like the one described in the article is not general to numerical optimization, but specific to the optimization being done here. That being said, when talking about techniques, theorems and algorithms in numeric optimization there are conventions. So you usually move between the more theory-oriented notation to a domain-specific notation (in the article I mostly used the domain-specific, lazy notation I chose). Bear in mind that my perspective is not very academic so I might feel less strongly about (and be less aware of) rigorous mathematical conventions.

pajko 5y ago

Also there is https://www.cs.huji.ac.il/~yweiss/Colorization/ https://www.cs.huji.ac.il/~yweiss/Colorization/ Had implemented a Khoros filter box based on this for my Computer Graphics class back then.