Reverse engineer “Regal” algorithm

[matteodelabre]

Note that this is probably covered by patents, so we may want to not do that. A shallow search returned patent US20170148372A1 that looks like it’s describing a ghosting-reduction algorithm that may well be the so-called Regal algorithm. Quoting from the patent (emphasis mine):

“Voltage signals applied to neighboring pixels can impact the optical state of the null state pixels, forming artifacts that can be carried to subsequent images. For example, a voltage signal may not be applied to a pixel that remains as part of a text character from one image to a subsequent image because it undergoes a black state to black state transition (B→B). This may reduce flashiness of the display by applying voltage signals only to pixels that change state between subsequent images. Although flashiness may be reduced, light edge artifacts can arise by such a drive scheme. For a pixel experiencing a null state transition, voltage signals applied to neighboring pixels may affect the optical state of the null state pixel, such as by impacting the distribution of electrophoretic medium of the pixel undergoing the null state transition and creating an undesired change in its optical state. A pixel identified to remain in a black state during a transition may have a lighter optical state because of one or more neighboring pixels undergoing a black state to white state transition. These “blooming events” may occur at the edges of Objects displayed in an electro-optic display, such as the edges of text characters, and may be carried over to subsequent image transitions. Pixels having a lighter optical state may become surrounded by pixels displaying a black optical state in a subsequent image transition, forming light edge artifacts in the image that may be more apparent to a viewer of the display than if the light pixels are on the edge of an object. Accordingly, aspects of the present application relate to identifying pixels that are likely to negatively impact the visual aesthetics of the content displayed based on prior transitions of pixel neighboring the pixel of interest, and applying suitable corrective signals when appropriate to reduce or eliminate such negative impact.”

This patent was filled in 2012 and granted this year, with expiration set to 2033. Basically, we’ll need to find our own method to achieve ghosting reduction (or wait a few decades to revisit this issue).

[tadfisher]

Note that nothing in a patent is enforceable except for the Claims section at the bottom. Everything else is fluff or explanatory, but only the claims comprise the actual patent.

[matteodelabre]

That’s a very good point @tadfisher. While I definitely don’t have the required expertise to tell exactly what is claimed in that patent, it seems to cover the following ghosting-reduction method: for each pixel that goes through a null transition (for example, a black pixel that remains black in the next update), count the number of neighboring pixels that go e.g. from black to white, and apply a corrective signal if that number crosses a certain threshold. It’s pretty broad. Also, since the patent itself references “Regal” in its main text, this is probably not the patent for Regal itself.

[matteodelabre]

Some new findings: it is possible that mode no. 3 is to be used for REGAL. It is almost identical to mode no. 2, but adds a few new transitions from/to intensity states 29 and 31. Specifically, it might be that those special odd intensity states are used to correct ghosting when certain conditions are met.

[LoganDark]

Note that this is probably covered by patents, so we may want to not do that.

Something being patented shouldn't mean anything as long as waved isn't used in any commercial software. The most that is warranted, I suppose, is an easy "off" switch for the patented algorithms (compile-time option?).

[Eeems]

Note that this is probably covered by patents, so we may want to not do that.

Something being patented shouldn't mean anything as long as waved isn't used in any commercial software. The most that is warranted, I suppose, is an easy "off" switch for the patented algorithms (compile-time option?).

I would highly recommend you speak with a lawyer before giving legal advice.

From my limited understanding of patents in North America, commercial vs non-commercial doesn't matter, as both can damage the long-term business value of what is being patented.

I'm not a lawyer, so don't take what I'm saying as legal advice. Seek out a lawyer who is an expert in patent law in your jurisdiction to see what applies to you.

https://opensource.stackexchange.com/a/5487

When an invention is patented, the patent owner has exclusive rights to use that invention for the duration of the patent term, within the jurisdiction where the patent was issued. In general, there isn't any special exception for non-commercial usage. However, patent law is a national affair, and there might be such rules in some countries.

[LoganDark]

From my limited understanding of patents in North America, commercial vs non-commercial doesn't matter, as both can damage the long-term business value of what is being patented.

The thing is I'm not sure what exactly is the long-term business value of a piece of open-source software like this. It's highly unlikely that E-Ink or reMarkable would choose to enforce a patent here, but...

Many modern open source licenses (GPLv2, GPLv3, Apache License 2.0) include an automatic patent grant

...I wasn't aware that GPLv3 included a patent grant (this is somewhat more important than the "slippery slope" argument). Since waved is GPLv3, and you can't grant rights to a patent that you don't have rights for yourself, I guess that settles it pretty clearly.

I would highly recommend you speak with a lawyer before giving legal advice.

Sorry.

[LoganDark]

At least for something that is not "legal advice", and assuming @matteodelabre's paraphrasing of the patent claims are mostly correct, it's possible to avoid "counting" neighboring pixels if you do something else, like accumulating an estimate of the error in each pixel and applying a correction when that error exceeds a certain threshold. (Though it's possible that's still what's covered in the patent, but it's worth a try I guess...)

The error estimate could even be derived by looking at the waveforms that are being used for neighboring pixels, not just the transition - in fact you could probably accumulate error for every single pixel this way (even the ones being updated), and that could potentially improve direct-update behavior (imagine if waved generated its own waveforms based on where pixels are and what their error is estimated to be??). These are just dumb ideas of mine since I have no idea how e-ink panels work, maybe it's harder to come up with waveforms than that (and maybe you need a lot more data and a lot more panels to test with in order to do so).

Highly unlikely to do much about ghosting since I'm sure E-Ink has been iterating on much more advanced algorithms for years, but this is just for keeping pixels where they are when the surrounding areas are updated, I think?