TreeBuilder is actually what I ended up doing, but it really felt and looked ugly. I'm really shocked Mechanize doesn't already do this already in its link extraction. I mean a Mechanize::Image class exists. There's no reason to "textify" anything when you could just include a reference to a Mechanize::Image object.
Thanks though everybody :)