FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Improving Lodepng

 
Post new topic   Reply to topic     Forum Index -> Scrapple
View previous topic :: View next topic  
Author Message
smjg



Joined: 29 Sep 2004
Posts: 41

PostPosted: Sat Sep 15, 2007 7:23 pm    Post subject: Improving Lodepng Reply with quote

There's been a brief discussion on the newsgroup about the possibility of improving Lodepng to support arbitrary chunks and the like. I'm now bringing the subject here.

I've fixed up the chunk ordering code - it now covers all PNG 1.2 chunks that have ordering rules. (I haven't committed the update yet.)

Now, we need an implementation strategy. Lutger mentioned the idea of a delegate-oriented interface; how to fit this into the design is something to consider.

But there are really two aspects towards supporting arbitrary chunks: preserving them and enabling the user to manipulate them. I think the simplest way to do this would be to add an array of chunks to the PngInfo structure, which would hold any chunks that aren't handled by Lodepng.

Thoughts?

Stewart.
Back to top
View user's profile Send private message
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Sun Sep 16, 2007 4:43 am    Post subject: Reply with quote

Hi Stewart, thanks for fixing the ordering rules, I just started looking at lodepng again. Chunk.opCmp is used by the encoder by the way, to sort an array of chunks.

In addition to preserving and editing, there is also the aspect of being able to parse chunks that lodepng knows nothing about. I have thought of these implementations:

1) Provide an optional delegate parameter to decode that is called *only* for each unknown chunk.
2) Return an array of all chunks, either in PngInfo or as an out / ref parameter
3) Provide an editor class, possibly with an interface like sax handling of xml?
4) For encoding there should be a corresponding solution: pass an array of Chunks to be written, a delegate that is called to retrieve the next chunk or a class.

I think a delegate oriented interface has the benefit of fitting better with a possible later implementation of streaming and progressive display, and it does not provoke the GC. On the other hand, for encoding it would be convenient to just dump your chunks in an array and let lodepng sort them out, but this again does not mesh well with streaming.

At the moment I would favor 1) for the decoder and implement an editor class in a different module, which has the advantage of being much more flexible and keeping loading / saving simple.

What do you think?

EDIT: with regard to preserving, there is also the question of what lossless means to think about. For example, the decoding does not remember whether text was compressed or how chunks are split. The encoder can ditch an alpha channel if it is fully opaque or replace it with with a colorkey, etc. I'm not sure what is the desirable thing to do here.
Back to top
View user's profile Send private message
smjg



Joined: 29 Sep 2004
Posts: 41

PostPosted: Sun Sep 16, 2007 11:39 am    Post subject: Reply with quote

Lutger wrote:
Hi Stewart, thanks for fixing the ordering rules, I just started looking at lodepng again. Chunk.opCmp is used by the encoder by the way, to sort an array of chunks.

I see now. You use D's built-in sort. I'm surprised if this works considering how buggy the comparator was. Even so, because the ordering is partial, it's probably wrong to try using .sort on it. Moreover, .sort isn't guaranteed to be stable (DMD's implementation isn't, for a start), and this will prove fatal if multiple IDAT chunks are ever going to be put into the chunk list.

Lutger wrote:
In addition to preserving and editing, there is also the aspect of being able to parse chunks that lodepng knows nothing about. I have thought of these implementations:

1) Provide an optional delegate parameter to decode that is called *only* for each unknown chunk.

And do what with chunks that this delegate doesn't process?

Lutger wrote:
2) Return an array of all chunks, either in PngInfo or as an out / ref parameter

So you think it should contain all chunks, whether Lodepng handles them or not?

Lutger wrote:
3) Provide an editor class, possibly with an interface like sax handling of xml?

I'm not familiar with sax, so I can't really comment on it.

Lutger wrote:
4) For encoding there should be a corresponding solution: pass an array of Chunks to be written, a delegate that is called to retrieve the next chunk or a class.

I'm not sure how the latter would work....

Lutger wrote:
I think a delegate oriented interface has the benefit of fitting better with a possible later implementation of streaming and progressive display, and it does not provoke the GC.

How do you work that out?

Lutger wrote:
On the other hand, for encoding it would be convenient to just dump your chunks in an array and let lodepng sort them out, but this again does not mesh well with streaming.

At the moment I would favor 1) for the decoder and implement an editor class in a different module, which has the advantage of being much more flexible and keeping loading / saving simple.

What do you think?

I suppose it depends on how well an editor class can fit into Lodepng. The library ought to remain cohesive enough to have been worth doing as part of the library rather than as a whole new library.

Lutger wrote:
EDIT: with regard to preserving, there is also the question of what lossless means to think about. For example, the decoding does not remember whether text was compressed or how chunks are split. The encoder can ditch an alpha channel if it is fully opaque or replace it with with a colorkey, etc. I'm not sure what is the desirable thing to do here.

Nor am I. The PNG spec has rules for editors to follow, but doesn't address this issue.
Back to top
View user's profile Send private message
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Mon Sep 17, 2007 2:26 am    Post subject: Reply with quote

smjg wrote:
Lutger wrote:
Hi Stewart, thanks for fixing the ordering rules, I just started looking at lodepng again. Chunk.opCmp is used by the encoder by the way, to sort an array of chunks.

I see now. You use D's built-in sort. I'm surprised if this works considering how buggy the comparator was. Even so, because the ordering is partial, it's probably wrong to try using .sort on it. Moreover, .sort isn't guaranteed to be stable (DMD's implementation isn't, for a start), and this will prove fatal if multiple IDAT chunks are ever going to be put into the chunk list.


Yes, using .sort was probably not a good idea, it worked for the limited cases in the encoder. Please do commit your fix though.

smjg wrote:
Lutger wrote:
1) Provide an optional delegate parameter to decode that is called *only* for each unknown chunk.

And do what with chunks that this delegate doesn't process?


Nothing, the idea is that as a user, you can process public or private chunks lodepng doesn't handle. It is up to the user to store them (see below). Convenience methods could be provide in a seperate module.

smjg wrote:
Lutger wrote:
2) Return an array of all chunks, either in PngInfo or as an out / ref parameter

So you think it should contain all chunks, whether Lodepng handles them or not?


Yes. This should be in addition to the handling of unknown chunks. It would probably sit in it's own module, lodepng.Edit. My idea is that this allows one to 1) cheaply and easily preserve the original data (since these chunks just slice the original data) and 2) possibly edit metadata without decoding.


smjg wrote:
Lutger wrote:
I think a delegate oriented interface has the benefit of fitting better with a possible later implementation of streaming and progressive display, and it does not provoke the GC.

How do you work that out?


Streaming I'm not sure of, and if it will work for lodepng. Minimal GC provocation is already in place, depending on if the user provides a large enough buffer and on the source image there are just a few or even zero GC allocations.

...

You are probably right about that a class based design might be inconsistent though.

Here is an example of what I have in mind how it would look like with delegates. This decodes an image and saves chunks unknown by lodepng, looks for the tIME chunk and then encodes the whole thing again:
Code:

    ubyte[] source = cast(ubyte[]) ( (new File(args[1])).read() );

    Chunk[] chunkList;
    void handleChunks(Chunk chunk)
    {
        if (chunk.typeString() == "tIME")
            with(chunk)
                Stdout.format("Last time modified: {3}-{2}-{0}{1} {4}::{5}::{6}",
                              data[0], data[1], data[2], data[3], data[4], data[5], data[6]).newline;
        chunkList ~= chunk;
    }
    PngInfo pngInfo;
    auto pixels = source.decode(pngInfo, &handleChunks);
    auto result = pixels.encode(pngInfo, chunkList);
Back to top
View user's profile Send private message
smjg



Joined: 29 Sep 2004
Posts: 41

PostPosted: Mon Sep 17, 2007 6:06 pm    Post subject: Reply with quote

Lutger wrote:
Yes, using .sort was probably not a good idea, it worked for the limited cases in the encoder. Please do commit your fix though.

Done. I hope you don't mind, but I've added some experimental code (commented out for now) that makes use of an afterIDAT member. It would probably work without it, but depending on the algorithm we use (an adaptation of insertion sort strikes me as something that would work quite well), afterIDAT may reduce the number of comparisons performed.

Lutger wrote:
Here is an example of what I have in mind how it would look like with delegates. This decodes an image and saves chunks unknown by lodepng, looks for the tIME chunk and then encodes the whole thing again:
Code:

    ubyte[] source = cast(ubyte[]) ( (new File(args[1])).read() );

    Chunk[] chunkList;
    void handleChunks(Chunk chunk)
    {
        if (chunk.typeString() == "tIME")
            with(chunk)
                Stdout.format("Last time modified: {3}-{2}-{0}{1} {4}::{5}::{6}",
                              data[0], data[1], data[2], data[3], data[4], data[5], data[6]).newline;
        chunkList ~= chunk;
    }
    PngInfo pngInfo;
    auto pixels = source.decode(pngInfo, &handleChunks);
    auto result = pixels.encode(pngInfo, chunkList);

I see. So effectively, the application would maintain a chunk list, thereby allowing some to be omitted to save memory.
Back to top
View user's profile Send private message
Lutger



Joined: 25 May 2006
Posts: 91

PostPosted: Thu Dec 20, 2007 5:38 am    Post subject: Reply with quote

Well it's been way too long and for that I apologize. Thank you Stewart for the bugfixes and advise, I've changed sorting to insertion sort and implemented a very basic method for handling chunks. It needs some work still, I hope to get to it these winter holidays.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Scrapple All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group